High performance wide-area overlay using deadlock-free routing

ABSTRACT

Overlay networks as the communication medium in parallel and distributed applications have gained prominence, especially in Grid environments. However, providing both throughput performance and reliable communication on overlays have been given little attention. The core of this problem is that intermediate nodes have limited buffer memory, while the forwarding throughput must yield Gbps. Yet, implementing a naive flow control can deadlock the overlay. Thus, high performance flow control on overlays is a critical concern in heterogeneous wide-area networks, where input/output link throughput can vary significantly. We propose an overlay scheme that couples TCP connections and fixed intermediate buffer memory while adapting deadlock-free routing for our overlay routing in heterogeneous wide-area networks. Our scheme eliminates memory overflows at forwarding nodes by fixed buffer memory and deadlocks via a deadlock-free routing algorithm that resolves adaptation challenges for heterogeneous wide-area networks. Our overlay construction and routing optimizations account for underlying network latency and bandwidth information. Simulation on 13 clusters (515 nodes) and evaluation on 7 clusters (170 nodes) show that our deadlock-free routing poses negligible overhead in comparison to deadlock-unaware routing, and comparably with direct communication. We further demonstrate that for certain collective communications, our overlay even out-performs direct communication by mitigating or completely avoiding network contention. We show this on systems ranging from a single-switch cluster with 36 nodes to a Grid environment with 4 clusters and 291 nodes.

REFERENCES

• 1: DAS-3. http://www.cs.vu.nl/das3.
• 2: Grid5000. https://www.grid5000.org.
• 3: InTrigger. http://www.intrigger.jp.
• 4: Planetlab. http://www.planet-lab.org.
• 5: Y. Amir, B. Awerbuch, C. Danilov, and J. Stanton. Global Flow Control for Wide Area Overlay Networks: a Cost-Benefit Approach. In OPENARCH 2002: Proceedings of the 5th IEEE Conference on Open Architectures and Network Programming, pages 155--166. IEEE Computer Society, 2002.
• 6: Y. Amir and C. Danilov. Spines. http://www.spines.org.
• 7: Y. Amir and C. Danilov. Reliable Communication in Overlay Networks. In DSN 2003: Proceedings of the 33rd Annual IEEE International Conference on Dependable Systems and Networks, pages 511--520. IEEE Computer Society, June 2003.
• 8: David Andersen , Hari Balakrishnan , Frans Kaashoek , Robert Morris, Resilient overlay networks, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 9: J. K. Antonio, Concurrent Communication in High-Speed Wide Area Networks, IEEE Transactions on Parallel and Distributed Systems, v.5 n.3, p.264-273, March 1994 [doi>10.1109/71.277791]
• 10: B. Awerbuch , Y. Azar , S. Plotkin, Throughput-competitive on-line routing, Proceedings of the 1993 IEEE 34th Annual Foundations of Computer Science, p.32-40, November 03-05, 1993 [doi>10.1109/SFCS.1993.366884]
• 11: Nanette J. Boden , Danny Cohen , Robert E. Felderman , Alan E. Kulawik , Charles L. Seitz , Jakov N. Seizovic , Wen-King Su, Myrinet: A Gigabit-per-Second Local Area Network, IEEE Micro, v.15 n.1, p.29-36, February 1995 [doi>10.1109/40.342015]
• 12: Dah-Ming Chiu , Miriam Kadansky , Radia J. Perlman , John Reynders , Guy Steele , Murat Yuksel, Deadlock-Free Routing Based on Ordered Links, Proceedings of the 27th Annual IEEE Conference on Local Computer Networks, p.62-71, November 06-08, 2002
• 13: W. J. Dally , H. Aoki, Deadlock-Free Adaptive Routing in Multicomputer Networks Using Virtual Channels, IEEE Transactions on Parallel and Distributed Systems, v.4 n.4, p.466-475, April 1993 [doi>10.1109/71.219761]
• 14: W. J. Dally , C. L. Seitz, Deadlock-Free Message Routing in Multiprocessor Interconnection Networks, IEEE Transactions on Computers, v.36 n.5, p.547-553, May 1987 [doi>10.1109/TC.1987.1676939]
• 15: K. Kar, S. Sarkar, and L. Tassiulas. A Simple Rate Control Algorithm for Maximizing Total User Utility. INFOCOM 2001: Proceedings of the 20th Annual Joint Conference of the IEEE Computer and Communications Societies, 1:133--141, 2001.
• 16: 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
• 17: Michihiro Koibuchi , Akira Funahashi , Akiya Jouraku , Hideharu Amano, L-Turn Routing: An Adaptive Routing in Irregular Networks, Proceedings of the 2001 International Conference on Parallel Processing, p.383-392, September 03-07, 2001
• 18: G. Kola and M. Livny. DiskRouter: A Flexible Infrastructure for High Performance Large Scale Data Transfers. Technical Report Technical Report CS-TR-2003-1484, University of Wisconsin, 2003.
• 19: Srisankar Kunniyur , R. Srikant, End-to-end congestion control schemes: utility functions, random losses and ECN marks, IEEE/ACM Transactions on Networking (TON), v.11 n.5, p.689-702, October 2003 [doi>10.1109/TNET.2003.818183]
• 20: G.-I. Kwon and J. W. Byers. ROMA: Reliable Overlay Multicast with Loosely Coupled TCP Connections. In INFOCOM 2004: Proceedings of the 23rd Conference of the IEEE Communications Society, pages 385--395, March 2004.
• 21: S.-J. Lee, S. Banerjee, P. Sharma, P. Yalagandula, and S. Basu. Bandwidth-Aware Routing in Overlay Networks. In INFOCOM 2008. Proceedings of the 27th IEEE International Conference on Computer Communications, pages 1732--1740, April 2008.
• 22: Jason Maassen , Henri E. Bal, Smartsockets: solving the connectivity problems in grid computing, Proceedings of the 16th international symposium on High performance distributed computing, June 25-29, 2007, Monterey, California, USA [doi>10.1145/1272366.1272368]
• 23: S. Naganuma, K. Takahashi, H. Saito, T. Shibata, K. Taura, and T. Chikayama. Improving Effciency of Network Bandwdith Estimation Using Topology Information (in Japanese). In SACSIS '08: Proceedings of the Annual IPSJ Synposium on Advanced Computing Systems and Infrastructures, pages 359--366. IPSJ, 2008.
• 24: Akihiro Nakao , Larry Peterson , Andy Bavier, A routing underlay for overlay networks, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863958]
• 25: Akihiro Nakao , Larry Peterson , Andy Bavier, Scalable routing overlay networks, ACM SIGOPS Operating Systems Review, v.40 n.1, January 2006 [doi>10.1145/1113361.1113372]
• 26: Hiroshi Nakashima, T2K Open Supercomputer: Inter-university and Inter-disciplinary Collaboration on the New Generation Supercomputer, Proceedings of the International Conference on Informatics Education and Research for Knowledge-Circulating Society (icks 2008), p.137-142, January 17-17, 2008 [doi>10.1109/ICKS.2008.6]
• 27: Hideo Saito , Kenjiro Taura, Locality-aware Connection Management and Rank Assignment forWide-area MPI, Proceedings of the Seventh IEEE International Symposium on Cluster Computing and the Grid, p.249-258, May 14-17, 2007 [doi>10.1109/CCGRID.2007.68]
• 28: Jose C. Sancho , Antonio Robles , Jose Duato, An Effective Methodology to Improve the Performance of the Up*/Down* Routing Algorithm, IEEE Transactions on Parallel and Distributed Systems, v.15 n.8, p.740-754, August 2004 [doi>10.1109/TPDS.2004.28]
• 29: M. D. Schroeder, A. D. Birrell, M. Burrows, H. Murray, R. M. Needham, T. L. Rodeheffer, E. H. Satterthwaite, and C. P. Thacker. Autonet: a High-Speed, Self-Configuring Local Area Network Using Point-to-Point Links. IEEE Journal on Selected Areas in Communications, 9:1318 -- 1335, 1991.
• 30: Tatsuya Shirai , Hideo Saito , Kenjiro Taura, A fast topology inference: a building block for network-aware parallel processing, Proceedings of the 16th international symposium on High performance distributed computing, June 25-29, 2007, Monterey, California, USA [doi>10.1145/1272366.1272369]
• 31: G. Urvoy Keller and E. W. Biersack. A Congestion Control Model for Multicast Overlay Networks and its Performance. In NGC 2002: Proceedings of the 4th International Workshop on Network Group Communication, October 2002.
• 32: L. Xu, K. Harfoush, and I. Rhee. Binary Increase Congestion Control (BIC) for Fast Long-Distance Networks. INFOCOM 2004: Proceedings of the 23rd Conference of the IEEE Communications Society, 4:2514--2524, March 2004.
• 33: A. Young, J. Chen, Z. Ma, A. Krishnamurthy, L. Peterson, and R. Y. Wang. Overlay Mesh Construction Using Interleaved Spanning Trees. In INFOCOM 2004: Proceedings of the 23th Conference of the IEEE Communications Society, March 2004.

INDEX TERMS

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

General Terms:
Algorithms, Design, Performance

Keywords:
bandwidth, collective communication, deadlock-free routing, grids, overlays, parallel applications