Making Parallel Packet Switches Practical

Okafor Uchenna

doi:10.56201/ijemt.vol.12.no3.2026.pg211.222

📄 Download Paper

Making Parallel Packet Switches Practical

Okafor Uchenna

Abstract

A parallel packet switch is a switch in which the memories run slower than the line rate. Arriving packets are spread (or load-balanced) packet-by-packet over multiple slower-speed packet switches. It is already known that with a speedup of, a PPS can theoretically mimic a FCFS output-queued (OQ) switch. However, the theory relies on a centralized packet scheduling algorithm that is essentially impractical because of high communication complexity. In this paper, we attempt to make a high-performance PPS practical by introducing two results. First, we show that small co-ordination buffers can eliminate the need for a centralized packet scheduling algorithm, allowing a full distributed implementation with low computational and communication complexity. Second, we show that without speedup, the resulting PPS can mimic an FCFS OQ switch within a delay bound.

References

S. Iyer, A. Awadallah, N. McKeown, “Analysis of a packet switch with memories running slower than the line rate,” in Proc. IEEE INFOCOM ‘00, pp.529-537. C. Clos, “A study of non-blocking switching networks,” Bell Systems Technical Journal 32, 1953. [3] http://www.rambus.com. Hari Adiseshu, Guru Parulkar, and George Varghese, “A reliable and scalable striping protocol,”. in Proc. ACM Sigcomm 1996. J. Turner, “Design of a broadcast packet switching network,” IEEE Trans. on Communications, pp. 734-743, June 1988. I. Widjaja, A. Leon-Garcia, “The helical switch: A multipath ATM switch which preserves cell sequence,” IEEE Trans. on Communications, Vol. 42, no. 8, pp. 2618-2629, Aug 1994. F. Chiussi, D. Khotimsky, S. Krishnan, “Generalized inverse multiplexing of switched ATM connections,” in Proc. IEEE Globecom ‘98 Conference. The Bridge to Global Integration, Sydney, Australia, Nov. 1998. F. Chiussi, D. Khotimsky, S. Krishnan, “Advanced Frame Recovery in Switched Connection Inverse Multiplexing for ATM,” in Proc. ICATM ‘99 Conference, Colmar, France, Jun. 1999. P. Fredette, “The past, present, and future of inverse multiplexing,” IEEE Communications, pp. 42-46, April 1994. J. Duncanson, “Inverse multiplexing”, IEEE Communications, pp. 34- 41, April 1994. J. Frimmel, “Inverse multiplexing: Tailor made for ATM,” Telephony, 231(3), pp 28-34, July 1996. Bandwidth ON Demand INteroperability Group. Interoperability Requirements for Nx56/64 kbit/sCalls, September 1992. S. Chuang, A. Goel, N. McKeown, B. Prabhakar, “Matching output queueing with a combined input/output-queued switch,” IEEE J.Sel. Areas in Communications, Vol. 17, no. 6, pp. 1030-1039, June 1999. B. Prabhakar and N. McKeown, “On the speedup required for combined input and output queued switching,” Automatica, Vol. 35, pp. 1909-1920, December 1999. P. Krishna, N. Patel, A. Charny, R. Simcoe, “On the speedup required for work-conserving crossbar switches,” IEEE J.Sel. Areas in Communications, Vol. 17, no. 6, pp. 1057- 1066, June 1999. [16] I. Stoica and H. Zhang, “Exact emulation of an output queuing switch by a combined input and output queuing switch,” in Proc. IEEE IWQoS ‘98, Napa, CA, May 1998. [17] R. L. Cruz, “A Calculus for Network Delay,” Part I. IEEE Transactions on Information Theory, vol 37, January, 1991, 114-131.

Making Parallel Packet Switches Practical

Abstract

References

More Articles from INTERNATIONAL JOURNAL OF ENGINEERING AND MODERN TECHNOLOGY