ATM switch architectures based on deflection routing are here examined, described in terms of a general switch model and compared with regards to their internal operations. Their common feature is the availability of multiple I/O paths through a multistage unbuffered interconnection network where conflicts for the same interstage link are dealt with by deflecting packets onto the wrong path. The main engineering parameter of the architecture, that is the number of network stages that provides a given packet loss performance is studied in depth. In particular it is found that basically all the examined architectures have a complexity on the order of N log₂ N in the range of switch size of usual interest. Furthermore it has been possible to rank the architectures with comparable complexity based on the loss performance they provide. The Shuffleout switch turns out to behave better than other architectures previously known as providing an optimal performance.

References

1 J. Hui, E. Arthurs, A broadband packet switch for integrated transport. IEEE J. on Selected Areas in Commun., Vol. SAC-5, No. 8, Oct. 1987, pages 1264–1273.
10.1109/JSAC.1987.1146650
Web of Science® Google Scholar
2 Y. S. Yeh, M. G. Hluchyj, A. S. Acampora, The knockout switch: a simple, modular architecture for high-performance packet switching. IEEE J. on Selected Areas in Commun., Vol. SAC-5, No. 8, Oct. 1987, pages 1274–1283.
Web of Science® Google Scholar
3 A. Huang, S. Knauer, Starlite: a wideband digital switch. Proc. of GLOBECOM 84, Atlanta, GA, Nov. 1984, pages 121–125.
Google Scholar
4 J. Turner, Design of a broadcast packet switching network. IEEE Trans, on Commun., Vol. COM-36, No. 6, June 1988, pages 734–743.
10.1109/26.2794
Web of Science® Google Scholar
5 T. Szymanski, S. Shaikh, Markov chain analysis of packet-switched banyans with arbitrary switch sizes, queue sizes, link multiplicities and speedups. Proc. of INFOCOM 89, Ottawa, Canada, April 1989, pages 960–971.
Google Scholar
6 S. Gianatti, A. Pattavina, Performance analysis of ATM banyan networks with shared queueing: Part I - Random offered traffic. IEEE/ACM Trans, on Networking, Vol. 2. No. 4, Aug. 1994, pages 398–410.
10.1109/90.330420
Web of Science® Google Scholar
7 J. N. Giacopelli, J. J. Hickey, W. S. Marcus, W. D. Sincoskie, M. Littlewood, Sunshine: a high performance self-routing broadband packet switch architecture. IEEE J. on Selected Areas in Commun., Vol. 9, No. 8, Oct. 1991, pages 1289–1298.
10.1109/49.105175
Web of Science® Google Scholar
8 T. T. Lee, A modular architecture for very large packet switches. IEEE Trans, on Commun., Vol. 38, No. 7, July 1990, pages 1097–1106.
10.1109/26.57507
Web of Science® Google Scholar
9 A. Pattavina, An ATM switch architecture for provision of integrated broadband services. IEEE J. on Selected Areas in Commun., Vol. 9, No. 9, Dec. 1991, pages 1537–1548.
10.1109/49.108689
Web of Science® Google Scholar
10 W. E. Denzel, A. P. J. Engbersen, I. Iliadis, G. Karlsson, A highly modular packet switch for Gbit/s rates. Proc. of Int. Switching Symp., Yokohama, Japan, Oct. 1992.
Google Scholar
11 A. Pattavina, Switching Theory, Architectures and Performance in Broadband ATM networks. John Wiley & Sons, 1998.
Google Scholar
12 M. Decina, P. Giacomazzi, A. Pattavina, Shuffle interconnection networks with deflection routing for ATM switching: the Open-Loop Shuffleout. Proc. of 15–th Int. Teletrqffic Congress, Copenhagen, Denmark, June 1991, pages 27–34.
Google Scholar
13 M. Decina, P. Giacomazzi, A. Pattavina, Shuffle interconnection networks with deflection routing for ATM switching: the Closed-Loop Shuffleout. Proc. of INFOCOM 91, Bal Harbour, FL, April 1991, pages. 1254–1263.
Google Scholar
14 R. Zarour, H. T. Mouftah, Bridged shuffle-exchange network: a high performance self-routing ATM switch. Proc. of ICC 93, Geneva, CH, June 1993, pages 696–700.
Google Scholar
15 R. Zarour, H. T. Mouftah, The closed bridged shuffle-exchange network: a high performance self-routing ATM switch. Proc. of GLOBECOM 93, Houston, TX, Nov. 1993, pages 1164–1168.
Google Scholar
16 R. Y. Awdeh, H. T. Mouftah, Design and performance analysis of an output-buffering ATM switch with complexity of O (N log, N). Proc. of ICC 94, New Orleans, LA, May 1994, pages 420–424.
Google Scholar
17 D. H. Lawrie, Access and alignment of data in an array processor. IEEE Trans, on Computers, Vol. C-24, No. 12, Dec. 1975, pages 1145–1155.
10.1109/T-C.1975.224157
Web of Science® Google Scholar
18 S. Urushidani, A high performance self-routing switch for broadband ISDN. IEEE J. on Selected Areas in Commun., Vol. 9, No. 8, Oct. 1991, pages 1194–1204.
10.1109/49.105166
Web of Science® Google Scholar
19 L. R. Goke, G. J. Lipovski, Banyan networks for partitioning multiprocessor systems. Proc. of First Symp. on Computer Architecture, Dec. 1973, pages 21–30.
Google Scholar
20 S. C. Liew, T. T. Lee, N log N dual shuffle-exchange network with error correcting routing. IEEE Trans, on Commun., Vol. 42, No. 2–4, Feb.-Mar. 1994, pages 754–766.
10.1109/TCOMM.1994.577104
Web of Science® Google Scholar
21 F. A. Tobagi, T. Kwok, F. M. Chiussi, Architecture, performance and implementation of the tandem banyan fast packet switch. IEEE J. on Selected Areas in Commun., Vol. 9, No. 8, Oct. 1991, pages 1173–1193.
10.1109/49.105165
Web of Science® Google Scholar
22 C-L. Wu, T-Y. Feng, On a class of multistage interconnection networks. IEEE Trans, on Comput., Vol. C-29, No. 8, Aug. 1980, pages 694–702.
10.1109/TC.1980.1675651
Web of Science® Google Scholar
23 H. J. Siegel, R. J. McMillen, The multistage cube: a versatile interconnection network. IEEE Computer, Vol. 14, No. 12, Dec. 1981, pages 65–76.
10.1109/C-M.1981.220298
Web of Science® Google Scholar
24 F. Masetti, A. Pattavina, C. Sironi, The ATM Shuffleout switching fabric: design and implementation issues. European Trans, on Telecommun. and Related Technol, Vol. 3, No. 2, Mar.-Apr. 1992, pages 157–165.
10.1002/ett.4460030211
Web of Science® Google Scholar

Volume10, Issue6

November–December 1999

Pages 571-583

Survey of Architectures and Performance of ATM Switches Based on Deflection Routing

Abstract

References

References

Information

About Wiley Online Library

Help & Support

Opportunities

Connect with Wiley

Survey of Architectures and Performance of ATM Switches Based on Deflection Routing

Abstract

References

References

Related

Information