Packet pacing in small buffer optical packet switched networks

ABSTRACT

In the absence of a cost-effective technology for storing optical signals, emerging optical packet switched (OPS) networks are expected to have severely limited buffering capability. To mitigate the performance degradation resulting from small buffers, this paper proposes that optical edge nodes "pace" the injection of traffic into the OPS core. Our contributions relating to pacing in OPS networks are three-fold: first, we develop real-time pacing algorithms of poly-logarithmic complexity that are feasible for practical implementation in emerging high-speed OPS networks. Second, we provide an analytical quantification of the benefits of pacing in reducing traffic burstiness and traffic loss at a link with very small buffers. Third, we show via simulations of realistic network topologies that pacing can significantly reduce network losses at the expense of a small and bounded increase in end-to-end delay for real-time traffic flows. We argue that the loss-delay tradeoff mechanism provided by pacing can be instrumental in overcoming the performance hurdle arising from the scarcity of buffers in OPS networks.

REFERENCES

• 1: Rajiv Ramaswami , Kumar N. Sivarajan, Optical networks: a practical perspective, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2001
• 2: Chunming Qiao , Myungsik Yoo, Optical burst switching (OBS) - a new paradigm for an optical Internet, Journal of High Speed Networks, v.8 n.1, p.69-84, March 1999
• 3: Imrich Chlamtac , Viktória Elek , Andrea Fumagalli , Csaba Szabó, Scalable WDM access network architecture based on photonic slot routing, IEEE/ACM Transactions on Networking (TON), v.7 n.1, p.1-9, Feb. 1999 [doi>10.1109/90.759310]
• 4: S. Yao, S. Dixit, and B. Mukherjee, "Advances in photonic packet switching: An overview," IEEE Commun. Mag., vol. 38, no. 2, pp. 84-94, Feb. 2000.
• 5: A. Carena, "OPERA: An optical packet experimental routing architecture with label swapping capability," J. Lightw. Tech., vol. 16, no. 12, pp. 2135-2145, Dec. 1998.
• 6: C. Guillemot, "Transparent optical packet switching: The European ACTS KEOPS project approach," J. Lightw. Tech., vol. 16, no. 12, pp. 2117-2134, Dec. 1998.
• 7: D. Hunter, "WASPNET: A wavelength switched packet network," IEEE Commun. Mag., vol. 37, no. 3, pp. 120-129, Mar. 1999.
• 8: D. Wonglumson, "HORNET: A packet switched WDM network: Optical packet transmission and recovery," IEEE Photon. Tech. Lett., vol. 11, no. 12, pp. 1692-1694, Dec. 1999.
• 9: L. Dittmann, "The European IST project DAVID: A viable approach toward optical packet switching," IEEE J. Sel. Areas Commun., vol. 21, no. 7, pp. 1026-1040, Sep. 2003.
• 10: H. Park, E. F. Burmeister, S. Bjorlin, and J. E. Bowers, "40-Gb/s optical buffer design and simulations," presented at the Numerical Simulation of Optoelectronic Devices (NUSOD) Conf., Santa Barbara, CA, Aug. 2004.
• 11: D. Hunter, M. Chia, and I. Andonovic, "Buffering in optical packet switches," J. Lightw. Tech., vol. 16, no. 12, pp. 2081-2094, Dec. 1998.
• 12: S. L. Danielsen, P. B. Hansen, and K. E. Stubkjaer, "Wavelength conversion in optical packet switching," J. Lightw. Tech., vol. 16, no. 12, pp. 2095-2108, Dec. 1998.
• 13: V. Eramo and M. Listani, "Packet loss in a bufferless optical WDM switch employing shared tunable wavelength converters," J. Lightw. Tech., vol. 18, no. 12, pp. 1818-1833, Dec. 2000.
• 14: F. Forghierri, A. Bononi, and P. R. Prucnal, "Analysis and comparison of hot-potato and single-buffer deflection routing in very high bit rate optical mesh networks," IEEE Trans. Commun., vol. 43, no. 1, pp. 88-98, Jan. 1995.
• 15: S. Yao, B. Mukherjee, S. J. B. Yoo, and S. Dixit, "A unified study of contention-resolution schemes in optical packet-switched networks," J. Lightw. Tech., vol. 21, no. 3, pp. 672-683, Mar. 2003.
• 16: A. Vishwanath and V. Sivaraman, "Routers with very small buffers: Anomalous loss performance for mixed real-time and TCP traffic," presented at the IEEE IWQoS, Enschede, Netherlands, Jun. 2008.
• 17: A. Vishwanath, V. Sivaraman, and G. N. Rouskas, "Are bigger optical buffers necessarily better?," presented at the IEEE INFOCOM Student Workshop, Phoenix, AZ, Apr. 2008.
• 18: J. Naor, A. Rosen, and G. Scalosub, "Online time-constrained scheduling in linear networks," presented at the IEEE INFOCOM 2005, Miami, FL, Mar. 2005.
• 19: M. Adler, S. Khanna, R. Rajaraman, and A. Rosen, "Time-constrained scheduling of weighted packets on trees and meshes," Algorithmica, vol. 36, no. 2, pp. 123-152, 2003.
• 20: M. Adler, A. L. Rosenberg, R. K. Sitaram, and W. Unger, "Scheduling time-constrained communication in linear networks," Theoretical Comp. Sci., vol. 35, no. 6, pp. 599-623, 2002.
• 21: 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
• 22: Halima Elbiaze , Tulin Atmaca, Traffic Management in Multi-service Optical Network, Proceedings of the First International Conference on Networking-Part 1, p.348-357, July 09-13, 2001
• 23: V. Sivaraman, D. Moreland, and D. Ostry, "Ingress traffic conditioning in slotted optical packet switched networks," presented at the ATNAC 2004, Sydney, Australia, Dec. 2004.
• 24: 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
• 25: M. Enachescu, Y. Ganjali, A. Goel, N. McKeown, and T. Roughgarden, "Routers with very small buffers," presented at the IEEE INFOCOM, Barcelona, Spain, Apr. 2006.
• 26: Amogh Dhamdhere , Constantine Dovrolis, Open issues in router buffer sizing, ACM SIGCOMM Computer Communication Review, v.36 n.1, January 2006 [doi>10.1145/1111322.1111342]
• 27: Yashar Ganjali , Nick McKeown, Update on buffer sizing in internet routers, ACM SIGCOMM Computer Communication Review, v.36 n.5, October 2006 [doi>10.1145/1163593.1163605]
• 28: James D. Salehi , Shi-Li Zhang , Jim Kurose , Don Towsley, Supporting stored video: reducing rate variability and end-to-end resource requirements through optimal smoothing, IEEE/ACM Transactions on Networking (TON), v.6 n.4, p.397-410, Aug. 1998 [doi>10.1109/90.720873]
• 29: S. Sen, J. Rexford, J. Dey, J. Kurose, and D. Towsley, "Online smoothing of variable-bit-rate streaming video," IEEE Trans. Multi-media , vol. 2, pp. 37-48, Mar. 2000.
• 30: R. Chang, M. Chen, J. Ho, and M. Ko, "An effective and efficient traffic-smoothing scheme for delivery of online VBR media streams," in Proc. IEEE INFOCOM, New York, NY, Mar. 1999, pp. 447-454.
• 31: G. Cao, W. Feng, and M. Singhal, "Online variable-bit-rate video traffic smoothing," Comput. Commun., vol. 26, no. 7, pp. 639-651, 2003.
• 32: Yishay Mansour , Boaz Patt-Shamir , Ofer Lapid, Optimal smoothing schedules for real-time streams (extended abstract), Proceedings of the nineteenth annual ACM symposium on Principles of distributed computing, p.21-29, July 16-19, 2000, Portland, Oregon, United States [doi>10.1145/343477.343511]
• 33: V. Sivaraman, D. Moreland, and D. Ostry, "A novel delay-bounded traffic conditioner for optical edge switches," presented at the IEEE HPSR 2005, Hong Kong, May 2005.
• 34: V. Sivaraman, H. ElGindy, D. Moreland, and D. Ostry, "Packet pacing in short buffer optical packet switched networks," presented at the IEEE INFOCOM, Barcelona, Spain, Apr. 2006.
• 35: D. Ferrari and D. Verma, "A scheme for real-time channel establishment in wide-area networks," IEEE J. Sel. Areas Commun., vol. 8, no. 3, pp. 368-379, Apr. 1990.
• 36: D. Verma, H. Zhang, and D. Ferrari, "Guaranteeing delay jitter bounds in packet switching networks," in Proc. TRICOMM, Chapel Hill, NC, Apr. 1991, pp. 35-46.
• 37: L. Georgiadis, R. Guérin, and A. Parekh, "Optimal multiplexing on a single link: Delay and buffer requirements," IEEE Trans. Inf. Theory, vol. 43, no. 5, pp. 1518-1535, Sep. 1997.
• 38: Vijay Sivaraman , Mario Gerla, End-to-end delay service in high-speed packet networks using earliest deadline first scheduling, University of California, Los Angeles, 2000
• 39: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 40: F. P. Preparata, An optimal real-time algorithm for planar convex hulls, Communications of the ACM, v.22 n.7, p.402-405, July 1979 [doi>10.1145/359131.359132]
• 41: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 42: M. H. Overmars and J. van Leeuwan, "Maintenance of configuration in the plane," J. Comput. Syst. Sci., vol. 23, pp. 166-204, 1981.
• 43: I. Norros, "On the use of fractional Brownian motion in the theory of connectionless traffic," IEEE J. Sel. Areas Commun., vol. 13, no. 6, pp. 953-962, Aug. 1995.
• 44: D. Ostry, "Synthesis of accurate fractional Gaussian noise by filtering," IEEE Trans. Inf. Theory, vol. 52, no. 4, pp. 1609-1623, Apr. 2006.
• 45: D. Careglio, J. Pareta, and S. Spadaro, "Optical slot dimensioning in IP/MPLS over OPS networks," presented at the WOAN 2003 Conf., Zagreb, Croatia, Jun. 2003.
• 46: T. McDermott and T. Brewer, "Large-scale IP router using a high-speed optical switch element," J. Optical Netw., vol. 2, no. 7, pp. 229-240, Jul. 2003.
• 47: Kihong Park , Walter Willinger, Self-Similar Network Traffic and Performance Evaluation, John Wiley & Sons, Inc., New York, NY, 2000
• 48: A. Elwalid, D. Mitra, and R. H. Wentworth, "A new approach for allocating buffers and bandwidth to heterogeneous, regulated traffic in an ATM node," IEEE J. Sel. Areas Commun., vol. 13, no. 11, pp. 1115-1127, Aug. 1995.
• 49: A. I. Elwalid and D. Mitra, "Design of generalized processor sharing schedulers which statistically multiplex heterogeneous QoS classes," presented at the IEEE INFOCOM'99, New York, NY, Mar. 1999.
• 50: Jean Walrand , Pravin Varaiya, High-performance communication networks (2nd ed.), Morgan Kaufmann Publishers Inc., San Francisco, CA, 1999
• 51: Z. Fan and P. Mars, "Accurate approximation of cell loss probability for self-similar traffic in ATM networks," IEE Electron. Lett., vol. 32, no. 19, pp. 1749-51, Sep. 1996.
• 52: R. R. Bahadur and R. R. Rao, "On deviations of the sample mean," Ann. Math. Statist., pp. 1015-1027, 1960.
• 53: Z. Rosberg and D. Ostry, "Fractional wavelength OCS based on the golden ratio," presented at the ICTON, Athens, Greece, Jun. 2008.
• 54: CAIDA Packet Length Distributions. [Online]. Available: http://www. caida.org/analysis/AIX/plen_hist/
• 55: T. Percival, An Introduction to CeNTIE. [Online]. Available: http:// www.centie.org/docs/CeNTIE-web-intro.ppt
• 56: L. Tančcevski, "Optical routing of asynchronous, variable length packets," IEEE J. Sel. Areas Commun., vol. 18, no. 10, pp. 2084-2093, Oct. 2000.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.5 Local and Wide-Area Networks
          Subjects: High-speed (e.g., FDDI, fiber channel, ATM)

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network communications
      C.2.6 Internetworking
          Subjects: Routers
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.4 Model Validation and Analysis
      I.6.6 Simulation Output Analysis

General Terms:
Design, Performance, Theory

Keywords:
optical packet switch, small buffers, traffic burstiness, traffic pacing