Interconnection Networks This chapter is the first of three chapters devoted to the study of network theory. The basic concepts of the interconnection networks are briefly outlined here. The aim is to introduce the terminology and define the properties that characterize an interconnection network. These networks will be described independently from the context in which they could be used, that is either a circuit switch or a packet switch. The classes of rearrangeable networks investigated in Chapter 3 and that of non-blocking networks studied in Chapter 4 will complete the network theory. . | Switching Theory Architecture and Performance in Broadband ATM Networks Achille Pattavina Copyright 1998 John Wiley Sons Ltd ISBNs 0-471-96338-0 Hardback 0-470-84191-5 Electronic Chapter 2 Interconnection Networks This chapter is the first of three chapters devoted to the study of network theory. The basic concepts of the interconnection networks are briefly outlined here. The aim is to introduce the terminology and define the properties that characterize an interconnection network. These networks will be described independently from the context in which they could be used that is either a circuit switch or a packet switch. The classes of rearrangeable networks investigated in Chapter 3 and that of non-blocking networks studied in Chapter 4 will complete the network theory. The basic classification of interconnection network with respect to the blocking property is given in Section where the basic crossbar network and EGS pattern are introduced before defining classes of equivalences between networks. Networks with full interstage connection patterns are briefly described in Section whereas partially connected networks are investigated in Section . In this last section a detailed description is given for two classes of networks namely banyan networks and sorting networks that will play a very important role in the building of multistage networks having specific properties in terms of blocking. Section reports the proofs of some properties of sorting networks exploited in Section . . Basic Network Concepts The study of networks has been pursued in the last decades by researchers operating in two different fields communication scientists and computer scientists. The former have been studying structures initially referred to as connecting networks for use in switching systems and thus characterized in general by a very large size say with thousands of inlets and outlets. The latter have been considering structures called interconnection networks .
