On design of bandwidth scheduling algorithms for multiple data transfers in dedicated networks

ABSTRACT

The significance of high-performance dedicated networks has been well recognized due to the rapidly increasing number of large-scale applications that require high-speed data transfer. Efficient algorithms are needed for path computation and bandwidth scheduling in dedicated networks to improve the utilization of network resources and meet diverse user requests. We consider two periodic bandwidth scheduling problems: multiple data transfer allocation (MDTA) and multiple fixed-slot bandwidth reservation (MFBR), both of which schedule a number of user requests accumulated in a certain period. MDTA is to assign multiple data transfer requests on several pre-specified network paths to minimize the total data transfer end time, while MFBR is to satisfy multiple bandwidth reservation requests, each of which specifies a bandwidth and a time slot. For MDTA, we design an optimal algorithm and provide its correctness proof; for MFBR, we prove it to be NP-complete and propose a heuristic algorithm, Minimal Bandwidth and Distance Product Algorithm (MBDPA). Extensive simulation results illustrate the performance superiority of the proposed MBDPA over a greedy heuristic approach and provide valuable insight into the advantage of periodic bandwidth scheduling over instant bandwidth scheduling.

REFERENCES

• 1: Terascale Supernova Initiative (TSI). http://www.phy.ornl.gov/tsi.
• 2: Terascale High-Fidelity Simulations of Turbulent Combustion with Detailed Chemistry. http://scidac.psc.edu.
• 3: National Leadership Computing Facility (NLCF). http://www.ccs.ornl.gov/nlcf.
• 4: UCLP: User Controlled LightPath Provisioning. http://phi.badlab.crc.ca/uclp.
• 5: Enlightened Computing. http://www.enlightenedcomputing.org.
• 6: DRAGON: Dynamic Resource Allocation via GMPLS Optical Networks. http://dragon.maxgigapop.net.
• 7: JGN II: Advanced Network Testbed for Research and Development. http://www.jgn.nict.go.jp.
• 8: Geant2. http://www.geant2.net.
• 9: OSCARS: On-demand Secure Circuits and Advance Reservation System. http://www.es.net/oscars.
• 10: HOPI: Hybrid Optical and Packet Infrastructure. http://networks.internet2.edu/hopi.
• 11: GENI: Global Environment for Network Innivations. http://www.geni.net.
• 12: bbcp. http://www.slac.stanford.edu/~abh/bbcp.
• 13: Tsunami. http://newsinfo.iu.edu/news/page/normal/588.html.
• 14: Z. Cao, Z. Wang, and E. Zegura. Performance of hashing-based schemes for internet load balancing. volume 1, pages 332--341 vol. 1, 2000.
• 15: C. Cetinkaya and E. Knightly. Opportunistic traffic scheduling over multiple network paths. volume 3, pages 1928--1937 vol. 3, Mar. 2004.
• 16: CHEETAH: Circuit-switched High-speed End-to-End Transport ArcHitecture, http://www.ece.virginia.edu/cheetah.
• 17: R. Cohen, N. Fazlollahi, and D. Starobinski. Graded channel reservation with path switching in ultra high capacity networks. In Proc. of Broadnets, San Jose, CA, 2006.
• 18: S. Floyd, HighSpeed TCP for Large Congestion Windows, RFC Editor, 2003
• 19: S. Ganguly, A. Sen, G. Xue, B. Hao, and B. Shen. Optimal routing for fast transfer of bulk data files in time-varying networks. In Proc. of IEEE Int. Conf. on Communications, 2004.
• 20: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 21: S. Gorinsky and N. Rao. Dedicated channels as an optimal network support for effective transfer of massive data. In INFOCOM 2006 Workshop on High-Speed Networks, 2006.
• 22: W. Grimmell and N. Rao. On source-based route computation for quickest paths under dynamic bandwidth constraints. Int. J. on Foundations of Computer Science, 14(3):503--523, 2003.
• 23: Y. Gu, X. Hong, M. Mazzucco, and R. L. Grossman. SABUL: A high performance data transfer protocol, 2004. submitted to IEEE Communications Letters.
• 24: R. Guerin and A. Orda. Networks with advance reservations: the routing perspective. In Proc. of the 19th IEEE INFOCOM, 2000.
• 25: Eric He , Jason Leigh , Oliver Yu , Thomas A. DeFanti, Reliable Blast UDP: Predictable High Performance Bulk Data Transfer, Proceedings of the IEEE International Conference on Cluster Computing, p.317, September 23-26, 2002
• 26: E. He, P. Primet, and M. Welzl. A survey of transport protocols other than "standard" tcp. Global Grid Form Report GFD-I.055.
• 27: Yunyue Lin , Qishi Wu, On design of bandwidth scheduling algorithms for multiple data transfers in dedicated networks, Proceedings of the 4th ACM/IEEE Symposium on Architectures for Networking and Communications Systems, November 06-07, 2008, San Jose, California [doi>10.1145/1477942.1477970]
• 28: M. H. Phùng , K. C. Chua , G. Mohan , M. Motani , T. C. Wong , P. Y. Kong, On ordered scheduling for optical burst switching, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.48 n.6, p.891-909, 19 August 2005 [doi>10.1016/j.comnet.2004.l1.021]
• 29: N. Rao, W. Wing, S. Carter, and Q. Wu. Ultrascience net: Network testbed for large-scale science applications. IEEE Communications Magazine, 43(11):s12--s17, 2005. An expanded version available at www.csm.ornl.gov/ultranet.
• 30: N. Rao, Q. Wu, S. Carter, W. Wing, D. G. A. Banerjee, and B. Mukherjee. Control plane for advance bandwidth scheduling in ultra high-speed networks. In INFOCOM 2006 Workshop on Terabits Networks, 2006.
• 31: Sartaj Sahni , Nageshwara Rao , Sanjay Ranka , Yan Li , Eun-Sung Jung , Nara Kamath, Bandwidth Scheduling and Path Computation Algorithms for Connection-Oriented Networks, Proceedings of the Sixth International Conference on Networking, p.47, April 22-28, 2007 [doi>10.1109/ICN.2007.27]
• 32: B. Shen, B. Hao, and A. Sen. On multipath routing using widest pair of disjoint paths. In Proc. of Workshop on High Performance Switching and Routing, pages 134--140, 2004.
• 33: R. Stewart , Q. Xie , K. Morneault , C. Sharp , H. Schwarzbauer , T. Taylor , I. Rytina , M. Kalla , L. Zhang , V. Paxson, Stream Control Transmission Protocol, RFC Editor, 2000
• 34: M. Veeraraghavan, H. Lee, E. Chong, and H. Li. A varying-bandwidth list scheduling heuristic for file transfers. In Proc. of IEEE Int. Conf. on Communications, 2004.
• 35: Q. Wu and N. Rao. A class of reliable udp-based transport protocols based on stochastic approximation. In Proc. of the 24th IEEE INFOCOM, Miami, Florida, Mar. 13--17 2005.
• 36: Q. Wu and N. Rao. Protocol for high-speed data transport over dedicated channels. In Proc. of the 3rd Int. Workshop on Protocols for Fast Long-Distance Networks, pages 155--162, Feb. 3--4 2005.
• 37: Y. Xiong, M. Vandenhoute, and H. Cankaya. Control architecture in optical burst-switched wdm networks. IEEE J. on Selected Areas in Communications, 18(10):1838--1851, Oct 2000.
• 38: Zhi-Li Zhang , Zhenhai Duan , Lixin Gao , Yiwei Thomas Hou, Decoupling QoS control from core routers: a novel bandwidth broker architecture for scalable support of guaranteed services, Proceedings of the conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, p.71-83, August 28-September 01, 2000, Stockholm, Sweden
• 39: X. Zheng, A. Mudambi, and M. Veeraraghavan. Frtp: Fixed rate transport protocol -- a modified version of sabul for end-to-end circuits. In Proc. of Broadnets, 2004.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.5 Local and Wide-Area Networks

General Terms:
Algorithms, Design, Performance

Keywords:
bandwidth scheduling, control plane, dedicated network