A fast topology inference: a building block for network-aware parallel processing

ABSTRACT

Adapting to the network is the key to achieving high performance for communication-intensive applications, including scientific computing,data intensive computing, and multicast, especially in Grid environments. This paper investigates an approach of representing network as a tree of participating hosts and switches matching or approximating their physical topology, and describes a fast, non-intrusive, and portable algorithm for inferring such a topology. This representation and the proposed inference algorithm serves as a key to building network-aware applications in a portable manner. The algorithm is based solely on RTTs of small packets between end hosts; it does not rely on popular but not universally available protocols such as trace route and SNMP. Another benefit is that it can handle all layers of network uniformly without any a priori knowledge of cluster configurations. The required number of measurements is O(Nd) in certain idealizing assumptions made for the purpose of analysis, where N is the number of participating processes and d the diameter of the network, which is usually small in real networks. In our experimental environment, the inference algorithm built a topology of 64 hosts in a single cluster in 4 seconds and and that of 256 hosts across 4 clusters in 15 seconds. It is able to not only identify clusters within a Grid, but also to partially identify the Layer 2 topology within a cluster. This is important for optimizing bandwidth-limited operations such as broadcast. We built several network-aware applications upon the inference system, including efficient bandwidth measurements and long message broadcasts. The topology is used to schedule as many measurements as possible in parallel without competing on shared links. We were able to build a bandwidth map of 256 hosts across 4 clusters in 27 seconds.

REFERENCES

• 1: Oliver Aumage , Guillaume Mercier, MPICH/MADIII: a Cluster of Clusters Enabled MPI Implementation, Proceedings of the 3st International Symposium on Cluster Computing and the Grid, p.26, May 12-15, 2003
• 2: Richard Black , Austin Donnelly , Cedric Fournet, Ethernet Topology Discovery without Network Assistance, Proceedings of the Network Protocols, 12th IEEE International Conference on (ICNP'04), p.328-339, October 05-08, 2004
• 3: Yuri Breitbart , Minos Garofalakis , Ben Jai , Cliff Martin , Rajeev Rastogi , Avi Silberschatz, Topology discovery in heterogeneous IP networks: the NetInventory system, IEEE/ACM Transactions on Networking (TON), v.12 n.3, p.401-414, June 2004 [doi>10.1109/TNET.2004.828963]
• 4: Azer Bestavros , John W. Byers , Khaled A. Harfoush, Inference and Labeling of Metric-Induced Network Topologies, IEEE Transactions on Parallel and Distributed Systems, v.16 n.11, p.1053-1065, November 2005 [doi>10.1109/TPDS.2005.138]
• 5: Mark Coates , Rui Castro , Robert Nowak , Manik Gadhiok , Ryan King , Yolanda Tsang, Maximum likelihood network topology identification from edge-based unicast measurements, ACM SIGMETRICS Performance Evaluation Review, v.30 n.1, June 2002
• 6: Mark Coates , Michael Rabbat , Robert Nowak, Merging logical topologies using end-to-end measurements, Proceedings of the 3rd ACM SIGCOMM conference on Internet measurement, October 27-29, 2003, Miami Beach, FL, USA [doi>10.1145/948205.948230]
• 7: Mathijs den Burger , Thilo Kielmann , Henri E. Bal, TOPOMON: A Monitoring Tool for Grid Network Topology, Proceedings of the International Conference on Computational Science-Part II, p.558-567, April 21-24, 2002
• 8: Mathijs den Burger , Thilo Kielmann , Henri E. Bal, Balanced Multicasting: High-throughput Communication for Grid Applications, Proceedings of the 2005 ACM/IEEE conference on Supercomputing, p.46, November 12-18, 2005 [doi>10.1109/SC.2005.15]
• 9: Benoit Donnet , Philippe Raoult , Timur Friedman , Mark Crovella, Efficient algorithms for large-scale topology discovery, ACM SIGMETRICS Performance Evaluation Review, v.33 n.1, June 2005
• 10: N. Duffield, J. Horowitz, F. L. Presti, and D. Towsley. Multicast topology inference from measured end-to-end loss. IEEE Transactions in Information Theory, 48: 26--45, 2002.
• 11: Edgar Gabriel , Michael Resch , Thomas Beisel , Rainer Keller, Distributed Computing in a Heterogeneous Computing Environment, Proceedings of the 5th European PVM/MPI Users' Group Meeting on Recent Advances in Parallel Virtual Machine and Message Passing Interface, p.180-187, September 07-09, 1998
• 12: Toshiyuki Imamura , Yuichi Tsujita , Hiroshi Koide , Hiroshi Takemiya, An Architecture of Stampi: MPI Library on a Cluster of Parallel Computers, Proceedings of the 7th European PVM/MPI Users' Group Meeting on Recent Advances in Parallel Virtual Machine and Message Passing Interface, p.200-207, January 2000
• 13: Nicholas T. Karonis , Brian Toonen , Ian Foster, MPICH-G2: a Grid-enabled implementation of the Message Passing Interface, Journal of Parallel and Distributed Computing, v.63 n.5, p.551-563, May 2003 [doi>10.1016/S0743-7315(03)00002-9]
• 14: Thilo Kielmann , Rutger F. H. Hofman , Henri E. Bal , Aske Plaat , Raoul A. F. Bhoedjang, MagPIe: MPI's collective communication operations for clustered wide area systems, Proceedings of the seventh ACM SIGPLAN symposium on Principles and practice of parallel programming, p.131-140, May 04-06, 1999, Atlanta, Georgia, United States
• 15: Bruce Lowekamp , David O'Hallaron , Thomas Gross, Topology discovery for large ethernet networks, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.237-248, August 2001, San Diego, California, United States
• 16: Bruce B. Lowekamp , Brian Tierney , Les Cottrell , Richard Hughes-Jones , Thilo Kielmann , Martin Swany, Enabling Network Measurement Portability Through a Hierarchy of Characteristics, Proceedings of the Fourth International Workshop on Grid Computing, p.68, November 17-17, 2003
• 17: G. Shao, F. Berman, and R. Wolski. Using Effective Network Views to Promote Distributed Application Performance. In Proceedings of the 1999 International Conference on Parallel and Distributed Processing Techniques and Applications, pages 2649--2656, 1999.
• 18: Skitter. http://www.caida.org/tools/measurement/skitter.
• 19: Rich Wolski , Neil T. Spring , Jim Hayes, The network weather service: a distributed resource performance forecasting service for metacomputing, Future Generation Computer Systems, v.15 n.5-6, p.757-768, Oct. 1999 [doi>10.1016/S0167-739X(99)00025-4]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Distributed applications

General Terms:
Algorithms, Measurement, Performance

Keywords:
broadcast, measurements, topology inference