Efficient Variable Length Block Switching Mechanism

  • Jaidhar C.D. Department of Computer Science and Engineering National Institute of Technology Tiruchirappalli – 620 015, India
  • A.V Reddy Department of Computer Applications National Institute of Technology Tiruchirappalli – 620 015, India

Abstract

Most popular and widely used packet switch architecture is the crossbar. Its attractive characteristics are simplicity, non-blocking and support for simultaneous multiple packet transmission across the switch. The special version of crossbar switch is Combined Input Crossbar Queue (CICQ) switch. It overcomes the limitations of un-buffered crossbar by employing buffers at each crosspoint in addition to buffering at each input port. Adoption of Crosspoint Buffer (CB) simplifies the scheduling complexity and adapts the distributed nature of scheduling. As a result, matching operation is not needed. Moreover, it supports variable length packets transmission without segmentation. Native switching of variable length packet transmission results in unfairness. To overcome this unfairness, Fixed Length Block Transfer mechanism has been proposed. It has the following drawbacks: (a) Fragmented packets are reassembled at the Crosspoint Buffer (CB). Hence, minimum buffer requirement at each crosspoint is twice the maximum size of the block. When number of ports are more, existence of such a switch is infeasible, due to the restricted memory available in switch core. (b) Reassembly circuit at each crosspoint adds the cost of the switch. (c) Packet is eligible to transfer from CB to output only when the entire packet arrives at the CB, which increases the latency of the fragmented packet in the switch. To overcome these drawbacks, this paper presents Variable Length Block Transfer mechanism. It does not require internal speedup, segmentation and reassembly circuits. Using simulation it is shown that proposed mechanism is superior to Fixed Length Block Transfer mechanism in terms of delay and throughput.

References

[1] M. J. Karol, M. G. Hluchyj and S. P. Morgan, Input Versus Output Queuing on a Space-Division Packet Switch, IEEE Transactions on Communications, Vol. 35, pp. 1347–1356, 1987.
http://dx.doi.org/10.1109/TCOM.1987.1096719

[2] T. Anderson, S. Owicki, J. Saxe and C. Thacker, High Speed Switch Scheduling for Local Area Networks, ACM Transactions on Computer Systems, Vol. 11, pp. 319–352, 1993.
http://dx.doi.org/10.1145/161541.161736

[3] N. McKeown, The iSLIP Scheduling Algorithm for Input-Queued Switches, IEEE/ACM Transactions on Networking, Vol. 7, pp. 188–201, 1999.
http://dx.doi.org/10.1109/90.769767

[4] D. N. Serpanos and P. I. Antoniadis, FIRM: A Class of Distributed Scheduling Algorithms for High-Speed ATM Switches with Multiple Input Queues, Proceedings of the IEEE INFOCOM, pp. 548–555, 2000.
http://dx.doi.org/10.1109/infcom.2000.832228

[5] H. J. Chao and J. S. Park, Centralized Contention Resolution Schemes for A Large-Capacity Optical ATM Switch, Proceedings of the IEEE ATM Workshop, 1998.
http://dx.doi.org/10.1109/atm.1998.675103

[6] Y. L. S. Panwar and H. J. Chao, On the Performance of a Dual Round-Robin Switch, Proceedings of the IEEE INFOCOM, pp. 1688–1697, 2001.

[7] N. McKeown, V. Anantharam and J. Walrand, Achieving 100% Throughput in an Input-Queued Switch, Proceedings of the IEEE INFOCOM, pp. 296–302, 1996.
http://dx.doi.org/10.1109/infcom.1996.497906

[8] A. Mekkittikul and N. McKeown, A Starvation-free Algorithm for Achieving 100% Throughput in an Input-Queued Switch, Proceedings of the IEEE ICCCN, pp. 226–231, 1996.

[9] G. Keridis and N. McKeown, Output-buffer ATM Packet Switching for Integrated Services Communication Networks, Proceedings of the IEEE International Conference on Communications, Montreal, Canada, 1997.

[10] E. Rathgeb, T. Theimer and M.Huber, Buffering Concepts for ATM switching networks, Proceedings of the IEEE GLOBECOM, pp. 1277–1281, 1988.
http://dx.doi.org/10.1109/glocom.1988.26034

[11] A. K. Gupta, L. O. Barbosa and N. D. Georganas, 16£16 Limited Intermediate Buffer Switch Module for ATM Networks, Proceedings of the EEE GLOBECOM, pp. 939-943, 1991.
http://dx.doi.org/10.1109/glocom.1991.188518

[12] A. L. Gupta and N. D. Georganas, Analysis of a packet switch with input and output buffers and speed constraints, Proceedings of the IEEE INFOCOM, pp. 694–700, 1999.

[13] A. K. Gupta, L. O. Barbosa and N. D. Georganas, Limited Intermediate Buffer Switch Modules and their Interconnection Networks for B-ISDN, Proceedings of the IEEE International Conference on Communications, pp. 1646–1650, 1992.
http://dx.doi.org/10.1109/icc.1992.268014

[14] M. Lin and N. McKeown, The Throughput of a Buffered Crossbar Switch, IEEE communications Letters, Vol. 9, pp. 465–467, 2005.
http://dx.doi.org/10.1109/LCOMM.2005.1431173

[15] M. Nabeshima, Performance Evaluation of a Combined Input and Crosspoint Queued Switch, IEICE Transactions on Communications, Vol. E83-B, pp. 737–741, 2000.

[16] T. Javid, R. Magil and T. Hrabik, A High Throughput Scheduling Algorithm for a Buffered Crossbar Switch Fabric, Proceedings of the IEEE International Conference on Communications, pp. 1586– 1591, 2001.
http://dx.doi.org/10.1109/icc.2001.937187

[17] R. R. Cessa, E. Oki, Z. Jing and H. J. Chao, CIXB-1 Combined Input-One Cell-Crosspoint-Buffered Switch, Proceedings of the IEEE Workshop on High Performance Switching and Routing, pp. 324– 329, 2001.

[18] H. T. Kung and R. Morris, Credit-Based Flow Control for ATM Networks, IEEE Network Magazine, Vol. 9, pp. 40–48, 1995.
http://dx.doi.org/10.1109/65.372658

[19] K. Yoshigoe and K.J. Christensen, An Evaluation to Crossbar Switches with Virtual Output Queuing and Buffered Cross points, IEEE Network, Vol. 17, pp. 48–56, 2003.
http://dx.doi.org/10.1109/MNET.2003.1233917
Published
2007-09-01
How to Cite
C.D., Jaidhar; REDDY, A.V. Efficient Variable Length Block Switching Mechanism. INTERNATIONAL JOURNAL OF COMPUTERS COMMUNICATIONS & CONTROL, [S.l.], v. 2, n. 3, p. 269-278, sep. 2007. ISSN 1841-9844. Available at: <http://univagora.ro/jour/index.php/ijccc/article/view/2359>. Date accessed: 09 aug. 2020. doi: https://doi.org/10.15837/ijccc.2007.3.2359.

Keywords

Crossbar switch, Un-buffered Crossbar switch, Buffered Crossbar switch, Combined Input Crossbar Queue switch