Chuyển đổi lý thuyết P2

Interconnection NetworksThis 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. ...
Nội dung trích xuất từ tài liệu:
Chuyển đổi lý thuyết P2 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 NetworksThis chapter is the first of three chapters devoted to the study of network theory. The basicconcepts of the interconnection networks are briefly outlined here. The aim is to introduce theterminology and define the properties that characterize an interconnection network. Thesenetworks will be described independently from the context in which they could be used, thatis either a circuit switch or a packet switch. The classes of rearrangeable networks investigatedin Chapter 3 and that of non-blocking networks studied in Chapter 4 will complete the net-work theory. The basic classification of interconnection network with respect to the blocking property isgiven in Section 2.1 where the basic crossbar network and EGS pattern are introduced beforedefining classes of equivalences between networks. Networks with full interstage connectionpatterns are briefly described in Section 2.2, whereas partially connected networks are investi-gated in Section 2.3. In this last section a detailed description is given for two classes ofnetworks, namely banyan networks and sorting networks, that will play a very important rolein the building of multistage networks having specific properties in terms of blocking.Section 2.4 reports the proofs of some properties of sorting networks exploited in Section 2.3.2.1. Basic Network ConceptsThe study of networks has been pursued in the last decades by researchers operating in twodifferent fields: communication scientists and computer scientists. The former have beenstudying structures initially referred to as connecting networks for use in switching systems andthus characterized in general by a very large size, say with thousands of inlets and outlets. Thelatter have been considering structures called interconnection networks for use in multiprocessorsystems for the mutual connection of memory and processing units and so characterized by areasonably small number of inlets and outlets, say at most a few tens. In principle we could say54 Interconnection Networksthat connecting networks are characterized by a centralized control that sets up the permuta-tion required, whereas the interconnection networks have been conceived as based on adistributed processing capability enabling the set-up of the permutation in a distributed fash-ion. Interestingly enough the expertise of these two streams of studies have converged into aunique objective: the development of large interconnection networks for switching systems inwhich a distributed processing capability is available to set up the required permutations. Thetwo main driving forces for this scenario have been the request for switching fabrics capable ofcarrying aggregate traffic on the order of hundreds of Gbit/s, as typical of a medium-sizebroadband packet switch, and the tremendous progress achieved in CMOS VLSI technologythat makes the distributed processing of interconnection networks feasible also for very largenetworks. The connection capability of a network is usually expressed by two indices referring to theabsence or presence of traffic carried by the network: accessibility and blocking. A network hasfull accessibility when each inlet can be connected to each outlet when no other I/O connec-tion is established in the network, whereas it has limited accessibility when such property doesnot hold. Full accessibility is a feature usually required today in all interconnection networkssince electronic technology, unlike the old mechanical and electromechanical technology,makes it very easy to be accomplished. On the other hand, the blocking property refers to thenetwork connection capability between idle inlets and outlets in a network with an arbitrarycurrent permutation, that is when the other inlets and outlets are either busy or idle and arbi-trarily connected to each other. An interconnection network, whose taxonomy is shown in Table 2.1, is said to be:• Non-blocking, if an I/O connection between an arbitrary idle inlet and an arbitrary idle out- let can be always established by the network independent of the network state at set-up time.• Blocking, if at least one I/O connection between an arbitrary idle inlet and an arbitrary idle outlet cannot be established by the network owing to internal congestion due to the already established I/O connections.Depending on the technique used by the network to set up connections, non-blocking net-works can be of three different types:• Strict-sense non-blocking (SNB), if the network can always connect each idle inlet to an arbi- trary idle outlet independent of the current network permutation, that is independent of the already established set of I/O connections and of the policy of connection allocation.• Wide-sense non-blocking (WNB), if the network can always connect each idle inlet to an arbitrary idle outlet by preventing blocking network states through a proper policy of allo- cating the connections.• Rearrangeable non-blocking (RNB), if the network can always connect each idle inlet to an arbitrary idle outlet by applying, if necessary, a suitable internal rearrangement of the I/O connections already established.Therefore, only SNB networks are free from blocking states, whereas WNB and RNB net-works are not (see Table 2.1). Blocking states are never entered in WNB networks due to asuitable ...