Gebali F. Analysis Of Computer And Communication Networks

Подождите немного. Документ загружается.

13.16 Virtual Routing/Virtual Queuing (VRQ) Switch 501

Fig. 13.14 The virtual

routing/virtual queuing

(VRQ) high-performance

switch

Dedicated

Input Buffers

Module 1

1 N

Module N

Virtual

Output Queues

Dedicated

Backplane Buses

...

itself remains in the input buffer. The buffer storage requirements for the output

queues are modest since they store pointer information, which is small in size com-

pared to the size of the packets stored in the input buffers.

When a pointer is selected from an output queue, the location of the correspond-

ing packet is determined and the packet is selected to access the SF. We call this

mode of operation output-driven routing, which never leads to SF contention. The

classic or usual way of accessing the SF is called input-driven routing, which is

guaranteed to lead to contention as we have seen in each switch design we have

studied so far.

Let us see how the VRQ switch is able to overcome all the limitations of earlier

designs:

1. Traffic management, scheduling, and congestion control are all distributed

among the input and output ports. This allows more time for the algorithms to

complete their operations and for the designer to implement more sophisticated

algorithms.

2. The HOL problem is completely eliminated because the VRQ switch is output

driven and not input driven.

3. The input buffers operate at the line rate and each output queue needs to process

at most N pointers which is much more simpler than processing N packets.

4. Packets are stored at the inputs in regular memory, not FIFO memory, which is

more simpler to implement.

5. There is great freedom in configuring the output queues. The queues could

be constructed based on a per-connection basis, per-input basis, or per-service

class basis.

6. Data broadcast is very simple to implement and no extra copies of a packet need

to be stored.

502 13 Switches and Routers

Table 13.2 Switch types

capable of supporting the

different switch features

Feature Input Output Shared VRQ

QoS support X X X

HOL elimination X X

Scheduling support X X X

Broadcast support X X

Memory speed X X

Scalability X X

Contentionless SF X X

7. An incoming packet does not leave its location in the input buffer until it

is ready to be moved through the switch. This reduces power and storage

requirements.

8. Internal blocking is completely removed since each input port has its own ded-

icated bus.

9. Output blocking is completely removed since each output port is able to process

all the pointers that arrive to it.

10. The backplane buses operate at the line rate in a bit-serial fashion with no need

whatsoever for internal speedup or use of parallel data lines.

11. The switch fabric is contentionless since it is based on a matrix of dedicated

buses that are output driven.

Table 13.2 summarizes the desirable features to be supported by a switch and

switch type that can support these features. From the table, we see that both the

shared buffer switch and the VRQ switch can easily implement most of the func-

tionalities of a high-speed switch. The performance results in Chapter 15 show that

indeed both the shared buffer switch and the VRQ switch perform the best compared

to all the other switch types.

Problems

Networking

13.1 What are the main components of a computer network?

13.2 Give examples of communication links used in computer networks and in

other types of networks (e.g., cable TV, radio, telephone, etc.)

13.3 Give examples of network software used at the different layers of the net-

work.

13.4 What is a core switch and an edge switch?

13.5 What are the main performance parameters of a link in a computer network?

13.6 Why should users in a network share the links even though this reduces the

quality of service offered?

Problems 503

Media Access Techniques

13.7 What are the main multiplexing techniques that allow users to share links?

13.8 Explain the two main types of TDMA and state the advantages and disad-

vantages of each.

13.9 What types of random assignment MAC protocols could be used to guarantee

fair access to the medium in a reasonable time delay?

13.10 Develop a model for the access probability of a user in a TDMA system

supporting N users where all users have equal priority and each time frame

has m available slots. What is the throughput of each user and the average

time delay?

13.11 Assume a TDMA system with a fixed priority protocol in which each user

has a priority equal to its index. Derive an expression for the probability of

accessing the medium for any user. Based on that, find the average delay that

each user experiences and the average throughput for each user.

13.12 Explain the two main types of SDMA and state the advantages and disadvan-

tages of each.

13.13 Explain how cellular phone technology uses both SDMA and FDMA or

SDMA and CDMA.

13.14 Explain how fixed assignment and random assignment could be used in

FDMA.

13.15 Explain CDMA and explain how fixed assignment and random assignment

could be used.

Circuit and Packet Switching

13.16 Explain the two main types of packet switching.

13.17 What are the advantages and disadvantages of circuit switching?

13.18 What are the important characteristics of circuit switching?

13.19 Explain the steps necessary to establish a path in circuit switching.

13.20 What are the advantages and disadvantages of packet switching?

13.21 Derive expressions for channel usage efficiency for the case of packet switch-

ing using datagram versus virtual circuit switching. Assume each packet for

datagram is composed of n

header/trailer bytes and n

payload bytes. For

virtual circuit switching, assume n

header/trailer bytes, n

payload bytes,

and n

bytes required for call establishment and tear down.

13.22 Explain what is meant by virtual circuit switching.

13.23 What are the advantages and disadvantages of virtual circuit switching?

Packet Switching Hardware

13.24 Explain the functions performed by a hub.

13.25 What is a passive hub?

13.26 What is an intelligent hub?

504 13 Switches and Routers

13.27 What is a switching hub?

13.28 Explain the functions performed by a switch.

13.29 Explain the functions performed by a bridge.

13.30 Explain the functions performed by a router.

13.31 Explain the functions performed by a gateway.

Switch Components

13.32 What are the two main architectural components in a switch?

13.33 Explain the functions performed by the datapath section of a switch.

13.34 Explain the functions performed by the control section of a switch.

13.35 Explain the main components of a switch and the functions performed by

each component.

13.36 One of the necessary components of a switch is the FIFO. How can this be

implemented using an ordinary one-ported random-access memory?

13.37 One of the necessary components of a switch is a CAM (content-addressable

memory). Discuss how a CAM could be implemented using specialized

hardware or using a random-access memory or groups of random-access

memories.

Switch Functions

13.38 What are the main tasks performed by a switch?

Input Queuing Switch

13.39 Explain the basic operation of input queuing switch.

13.40 What is the head of line (HOL) problem in input queuing switches?

13.41 In input queuing switch, it was mentioned that HOL problem leads to re-

duced throughput and increased packet loss probability. Suppose a window-

ing scheme is used to examine w packets at the head of the queue instead of

only one. How can this scheme preserve the packet sequence?

13.42 What are the advantages of input queuing switches?

13.43 What are the disadvantages of input queuing switches?

13.44 What are the potential sources of packet loss in input queuing switches?

13.45 Explain how a per-connection scheduling scheme can be implemented in an

input queuing switch.

Output Queuing Switch

13.46 Explain the basic operation of output queuing switch.

13.47 What are the advantages of output queuing switches?

13.48 What are the disadvantages of output queuing switches?

13.49 What are the potential sources of packet loss in output queuing switches?

Problems 505

13.50 Explain how a per-connection scheduling scheme can be implemented in an

output queuing switch.

Shared Buffer Switch

13.51 Explain the basic operation of shared buffer switch.

13.52 What are the advantages of shared buffer switches?

13.53 What are the disadvantages of shared buffer switches?

13.54 What are the potential sources of packet loss in shared buffer switches?

13.55 In shared buffer switches, it was mentioned that the shared buffer must per-

form many read and write operations per time step. Discuss how this can be

implemented using a bank of one-ported memories that is accessible by all

inputs and outputs of the switch.

13.56 Explain how a per-connection scheduling scheme can be implemented in a

shared buffer switch.

13.57 Assume a protocol is devised to evenly distribute packets between two

buffers (A and B) as follows:

1. Start with n packets (assume n even).

2. Pick a packet at random and move it to the other buffer.

3. The state of the system is the number of packets in buffer A.

Study the long-term performance of this protocol.

Multiple Input Queuing Switches

13.58 Explain how a per-connection scheduling scheme can be implemented in a

multiple input queuing switch.

13.59 Explain the basic operation of a virtual output queuing (VOQ) switch.

13.60 What are the advantages of virtual output queuing switch?

13.61 What are the disadvantages of virtual output queuing switch?

Multiple Output Queuing Switches

13.62 Explain the basic operation of a multiple output queuing switch.

13.63 What are the advantages of multiple output queuing switch?

13.64 What are the disadvantages of multiple output queuing switch?

13.65 Explain how a per-connection scheduling scheme can be implemented in an

multiple output queuing switch.

Virtual Routing/Virtual Queuing (VRQ) Switch

13.66 Explain the basic operation of virtual routing/virtual queuing (VRQ) switch.

13.67 Discuss the advantages and disadvantages of the VRQ switch.

13.68 What is meant by virtual routing in the VRQ switch?

506 13 Switches and Routers

13.69 How is broadcast operation implemented in the VRQ switch?

13.70 What is meant by “input-driven” and “output-driven” operation in a switch?

13.71 Why does input-driven switching suffer from contention?

13.72 Why is output-driven switching contentionless?

References

1. J. Warland and R. Varaiya, High-Performance Communication Networks, Moragan Kaufmann,

San Francisco, 2000.

2. W. Stallings, Data and Computer Communications, Fourth edition, Prentice Hall, New Jersey,

1994.

3. W. Stallings, Data and Computer Communications, Fifth edition, Prentice Hall, New Jersey,

1998.

4. A.V. Aho, J.E. Hopcroft, and J.D. Ullman, Data Structures and Algorithms, Addison-Wesley,

Reading, Massachusetts, 1983.

5. R. Sedgewick, Algorithms, Addison-Wesley, Reading, Massachusetts, 1984.

6. S. Baase, Computer Algorithms, Addison-Wesley, Reading, Massachusetts, 1983.

7. A.S. Tanenbaum, Computer Networks, Prentice Hall PTR, Upper Saddle River, New Jersey,

1996.

8. N. McKeown and T.E. Anderson, “A quantitative comparison of iterative scheduling al-

gorithms for input-queued switches”, Computer Networks and ISDN Systems, vol. 30,

pp. 2309–2326, 1998.

9. M. Karol, M. Hluchyj, and S. Morgan, “Input versus output queuing on a space division

switch”, IEEE Transactions on Communications, vol. 35, pp. 1347–1356, 1987.

10. M.G. Hluchyj and M.J. Karol, “Queuing in high-performance packet switching”, IEEE J. Se-

lected Areas in Communications, vol. 6, pp. 1587–1597, 1988.

11. F. Elguibaly, A. Sabaa, and D. Shpak, “A new shift-register based ATM switch”, The First An-

nual Conference on Emerging Technologies and Applications in Communications (ETACOM),

Portland, Oregon, pp. 24–27, May 7–10, 1996.

12. F. Elguibaly and S. Agarwal, “Design and performance analysis of shift register-based ATM

switch”, IEEE Pacific Rim Conference on Communications, Computers and Signal Process-

ing, Victoria, British Columbia, pp. 70–73, August 20–22, 1997.

13. A. Sabaa, F. Elguibaly, and D. Shpak, “Design and modeling of a nonblocking input-buffer

AT M sw i tc h” , Canadian Journal of Electrical & Computer Engineering, vol. 22, no. 3,

pp. 87–93, 1997.

Chapter 14

Interconnection Networks

14.1 Introduction

Interconnection networks form the switching fabric part of any switch. The capa-

bilities and characteristics of the interconnection network have a direct influence on

the resulting performance of the switch. We review in this chapter the different types

of switching networks and derive analytic expression for their performance.

14.2 Network Design Parameters

An interconnection network (IN) is also known as the switching fabric (SF). We

shall use the two terms interchangeably. The main purpose of the SF is to provide

full connectivity between the inputs and the outputs of the switch with reasonable

hardware and delay. In that sense, the input and output ports share the SF as a

common communication resource and, as such, conflicts may arise that have to be

resolved using some contention-resolving technique or arbitration protocol. There

are several arbitration protocols and each impacts the performance of the switch.

Reference [1] reviews and models five protocols and explains how they can be im-

plemented in hardware.

Because of logistics and office building code limitations, the maximum practical

number of ports in a central office switch is 16–128. Backbone or core switches and

routers deal with even smaller number of very high-speed links. Thus the switch

size in core routers could be between 8 and 32, according to references [2, 3].

14.2.1 Network Performance

Different interconnection networks have varying performance features due to the

design decisions employed. Throughput depends on the type of network used

and the number of input and output ports it can support. Packet loss probability

also depends on the type of network since this determines the number of paths

that can be simultaneously established to reduce the amount of buffer occupancy.

F. Gebali, Analysis of Computer and Communication Networks,

DOI: 10.1007/978-0-387-74437-7

14,



Springer Science+Business Media, LLC 2008

507

508 14 Interconnection Networks

Fault tolerance is the ability of the network to operate even in the presence of faulty

links or internal components. Gradual degradation of performance is desirable so

that the operators have a chance of isolating and replacing the faulty component.

Hot insertion is the ability to replace faulty components without having to halt, or

rest, the entire system.

14.2.2 Network Hardware

Synchronization and clock speed determine whether data will move within the SF in

a synchronous or an asynchronous manner. As the switching fabric gets bigger and

the operating speed increases, it becomes very difficult to synchronize the whole

system to a single clock with little skew. Further, the clock lines supporting the

fast clock transitions will consume power and will result in system noise. On the

other hand, asynchronous data transmission will require more control lines and more

sophisticated data transfer protocols.

Complexity includes several aspects such as: (a) how many bits of a packet will

move from one location to another within the SF in once clock cycle; (b) the number

and type of packages or boards required to implement the SF; (c) the number of I/O

pins per chip which impact the overall price and reliability of the system; (d) the

routing algorithm required to establish a path between an input and an output. This

routing algorithm might be simple and distributed among all the components of

the interconnection network or it could require complex operations and need to be

centralized thereby slowing down the whole system.

Power consumption is intimately dependent on the level of chip integration used,

amount of inter-chip communication, and the operating speed. Total power con-

sumed will determine the size, price, cooling, and weight of the required power

supply.

Modularity implies the SF is built from a small number of modules.

Hierarchy and partitionability are the ability to divide the SF into subsystems

that might simplify the task of building and operating the system.

Communication between the modules and the chips will have an impact on the

speed and power consumption of the SF and also on the size and reliability of the

switch.

14.2.3 Scalability Issues

Number of input and output ports might have an upper limit due to the way the SF

was built. Increasing that number might require complete rewiring and use of other

basic modules. Alternatively, increasing the number of I/O ports in some SFs might

degrade the performance or might not be feasible from a hardware point of view

due, for example, to pin limitations of the chips.

Operating speed of the SF might have an upper limit dictated by the way the

SF operates. For example, if communication is required between all the input ports

14.4 Time Division Multiple Access (TDMA) 509

to decide which one gains access to the shared memory, say, then the larger the

network, the slower this operation will become which will in turn reduce the overall

throughput.

14.3 Classification of Networks

A detailed classifications for interconnection networks can be found in [4]. A broad

classification of networks could be based on the protocol used to provide access

to the users to the shared medium—this is also called media access control (MAC).

Section 13.3 on page 479 provided a detailed discussion of the possible media access

control schemes. However, as in [5] and [6], we classify a switch fabric based on

time division multiplexing or space-division multiplexing which we discuss in the

following sections.

14.4 Time Division Multiple Access (TDMA)

In time division multiple access (TDMA), the communication medium gives sole

access to the communication medium for a short amount of time. Time division

requires a communication medium be shared among all the users (packets in our

case). The shared medium could be a bus that joins all the inputs and outputs or it

could be a wireless channel, as in the case of satellite communications and cellular

telephones. Simultaneous requests lead to contention or corruption of data and a

contention resolution protocol is used to resolve these conflicts. A shared medium

has a maximum bandwidth that is determined by the channel used. For the case of

a shared bus, the maximum bandwidth is set by the electrical drive capability of the

bus drivers and the physical length of the bus. For the case of a wireless channel, the

channel bandwidth is determined by the frequency and power restrictions of wireless

and any channel impairment such as noise and fading. Many routers and multiport

bridges are shared media switches with bandwidth limitations of 800 Mbits/s to

3.2 Gbits/s [2].

We classify TDMA into two types: static assignment and random assignment,

which we discuss next.

14.4.1 Static-Assignment TDMA

Constant bit rate traffic is efficiently served by the static-assignment protocol. In

that scheme, time is broken into frames and each frame is divided into slots. Each

user is assigned a certain slot in each frame. Figure 14.1(a) shows such a scheme

where five users are assumed to share the medium. Each user is guaranteed access

to the medium even when there is no data to send. Static-assignment techniques do

not work well for bursty traffic or mixed traffic with long idle times since either the

510 14 Interconnection Networks

Fig. 14.1 Time division

switching: (a) Static

assignment. (b) Random

assignment

(a)

Time

Frame n

+ 1

(b)

5442

1254

Time

Frame n Frame n

+ 1

2345

medium will be grossly underutilized or the access time will be large. Examples of

static-assignment networks include the token ring and the telephone network trunk

lines.

14.4.2 Random Assignment TDMA

This is also known as statistical multiplexing in packet switching. Bursty traffic is

efficiently served by the random-assignment protocol. Figure 14.1(b) shows such a

scheme where again five users are assumed to share the medium. At a given time

step, all users with data to send compete to access that slot and only one winner gains

access and the others wait for the next slot. As a result, idle sources do not interfere

with active users but access time now is not guaranteed and could be long at times

of heavy traffic. Random assignment techniques do not work well for constant bit

rate traffic since the access time will be needlessly large. An important aspect of

random assignment schemes is the arbitration protocol used to resolve contention

among the competing users and assign the channel to one user. Reference [1] dealt

with five types of common arbitration protocols and their distributed hardware im-

plementation.

From the above, we see that time division multiplexing is characterized by low

bandwidth assigned for each user. On the other hand, it requires little hardware

resources since the interconnection network comprises one shared medium which

requires a small wiring area, or a narrow frequency band. As such, it might not

be well suited to high-speed communications, but can still be used in the switch for

communicating the control information between the different modules. Examples of

random assignment networks include Ethernet LANs and common computer buses.

14.5 Space Division Switching

Space division switching is the method of choice to implement high-performance

switches since they provide high capacity and low access time delay. Space division

switching can be broadly classified as crossbar networks and multistage intercon-

nection networks (MIN). We discuss each in the following sections.