Analysis of a transmission scheduling algorithm for supporting bandwidth guarantees in bufferless networks

ABSTRACT

In a network of bufferless packet multiplexers, the user-perceived capacity of an ingress-egress tunnel (connection) may degrade quickly with increasing path length. This is due to the compounding of transmission blocking probabilities along the path of the connection, even when the links are not overloaded. In such an environment, providing users (e.g., client ISPs) with tunnels of statistically guaranteed bandwidth may limit the network's connection-carrying capacity.In this paper, we introduce and analyze a transmission-scheduling algorithm that employs randomization and traffic regulation at the ingress, and batch scheduling at the links. The algorithm ensures that a fraction of transmissions from each connection is consistently subject to small blocking probability at every link, so that these transmissions are likely to survive long paths. For this algorithm, we obtain tight bounds on the expectation and tail probability of the blocking rate of any ingress-egress connection. We compare the bounds to those obtained using the FCFS link-scheduling rule. We find that the proposed scheduling algorithm significantly improves the network's connection-carrying capacity.In deriving the desired bounds, we develop an analytic framework for stochastically comparing network-wide routing and bandwidth allocation scenarios with respect to blocking in a packet multiplexer. The framework enables us to formally characterize the routing and bandwidth allocation scenarios that maximize the expected blocking rate along the path of a tagged connection.

REFERENCES

• 1: Guido Appenzeller , Isaac Keslassy , Nick McKeown, Sizing router buffers, Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications, August 30-September 03, 2004, Portland, Oregon, USA
• 2: Y. Chen, C. Qiao, and X. Yu. Optical burst switching: A new area in optical networking research. IEEE Network, 18(3):16--23, May 2004.
• 3: M. Elhaddad, R. Melhem, and T. Znati. Supporting bandwidth guarantees in buffer-limited networks. Technical report, University of Pittsburgh. http://www.cs.pitt.edu/~elhaddad/BCN/.
• 4: Mahmoud Elhaddad , Rami Melhem , Taieb Znati, Decoupling Packet Loss from Blocking in Proactive Reservation-Based Switching, Proceedings of the First International Conference on Broadband Networks (BROADNETS'04), p.92-101, October 25-29, 2004 [doi>10.1109/BROADNETS.2004.28]
• 5: S. Floyd, HighSpeed TCP for Large Congestion Windows, RFC Editor, 2003
• 6: S. Floyd and V. Jacobson. Traffic phase effects in packet-switched gateways. Journal of Internetworking: Practice and Experience, 3(3):115--156, September, 1992.
• 7: Tom Kelly, Scalable TCP: improving performance in highspeed wide area networks, ACM SIGCOMM Computer Communication Review, v.33 n.2, April 2003 [doi>10.1145/956981.956989]
• 8: Han S. Kim , Ness B. Shroff, Loss probability calculations and asymptotic analysis for finite buffer multiplexers, IEEE/ACM Transactions on Networking (TON), v.9 n.6, p.755-768, December 2001 [doi>10.1109/90.974529]
• 9: Jim Kurose, On computing per-session performance bounds in high-speed multi-hop computer networks, Proceedings of the 1992 ACM SIGMETRICS joint international conference on Measurement and modeling of computer systems, p.128-139, June 01-05, 1992, Newport, Rhode Island, United States
• 10: Chengzhi Li , Edward W. Knightly, Coordinated multihop scheduling: a framework for end-to-end services, IEEE/ACM Transactions on Networking (TON), v.10 n.6, p.776-789, December 2002 [doi>10.1109/TNET.2002.805024]
• 11: M. Parulekar and A. M. Makowski. Tail probabilities for a multiplexer with self-similar traffic. In IEEE INFOCOM, 1996.
• 12: A. Pattavina. Architectures and performance of optical packet switching nodes for IP networks. Journal of Lightwave Technology, 23(3):1023--1032, March 2005.
• 13: J. Ramamirtham and J. Turner. Time sliced optical burst switching. In IEEE INFOCOM, 2003.
• 14: Martin Reisslein , Keith W. Ross , Srinivas Rajagopal, A framework for guaranteeing statistical QoS, IEEE/ACM Transactions on Networking (TON), v.10 n.1, p.27-42, February 2002 [doi>10.1109/90.986511]
• 15: Ugo Mocci , Jorma Virtamo , James Roberts, Broadband Network Traffic: Performance Evaluation and Design of Broadband Multiservice Networks: Final Report of Action Cost 242, Springer-Verlag New York, Inc., Secaucus, NJ, 1999
• 16: J. W. Roberts and J. T. Virtamo. The superposition of periodic cell arrival streams in an ATM multiplexer. IEEE Trans. Commun., 39(2):298--303, Feb. 1991.
• 17: S. M. Ross. Stochastic Processes. John Wiley & Sons, Inc., second edition, 1996.
• 18: G. Shrimali, I. Keslassy, and N. McKeown. Designing packet buffers with statistical guarantees. In IEEE Hot Interconnects XII, Stanford, CA, 2004.
• 19: Y. Xiong, M. Vandenhoute, and H. Cankaya. Control architecture in optical burst-switched WDM networks. IEEE journal on selected areas in communications, 18(10):1838--1851, October 2000.
• 20: M. Yoo, M. Jeong, and C. Qiao. A high speed protocol for bursty traffic in optical networks. In SPIE'97 Conf. For All-Optical Networking: Architecture, Control, and Management Issues, pages 79--90, 1997.