Gebali F. Analysis Of Computer And Communication Networks

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

13.4 Circuit and Packet Switching 481

Fig. 13.3 Frequency division

multiple access assigns a

frequency band to each user.

The gaps between packets

indicate that the channel is

idle and the frequency band is

not in use

Frequency

Band

...

Time

Similar to TDMA, there are two ways that SDMA could be used. Fixed as-

signment is called circuit switching and is discussed in Section 13.4.1. Random

assignment is called packet switching which is discussed in Section 13.4.2.

13.3.3 Frequency Division Multiple Access (FDMA)

In this technique, each user is assigned a unique frequency band in the frequency

spectrum. Radio and analog TV broadcasting use this technique where each station

is allocated a frequency band. Figure 13.3 shows the assignment of the frequency

bands among users versus time.

This technique is also used in optical fibers by assigning a particular optical

wavelength (light color) to each channel. This is known as wavelength division

multiple access (WDMA).

13.3.4 Code Division Multiple Access (CDMA)

In code division multiple access technique, data from each user are used to modulate

a unique binary pattern that belongs to the user. The binary patterns (called polyno-

mials) are designed such that no interference takes place when the signals are sent.

At the receiver end, information carried on each pattern can be extracted with no

interference from the other signals. Figure 13.4 shows an example of CDMA where

N codes are used to transmit data from N users.

13.4 Circuit and Packet Switching

In digital communications, there are two main techniques for establishing a path

through the network: circuit switching and packet switching.

482 13 Switches and Routers

Fig. 13.4 Code division

multiple access assigns a

binary pattern (or

polynomial) to each user. The

gaps between packets

indicate that the channel is

idle and the channel is not in

use

Binary Code

(Polynomial)

...

Time

13.4.1 Circuit Switching

In circuit switching, a unique path is used to move data between the two end users.

Thus, the path or the resource is reserved for the duration of a particular session. This

is a waste of resources when there is no activity on the channel while other users

are waiting to access the channel. Constant bit rate traffic does well with circuit

switching since the path is dedicated and there are always data sent on the channel.

Computer communication, however, is bursty and does not do well under circuit-

switched techniques. The telephone network is circuit switched and the path is held

up by the user until it is released.

The important characteristics of circuit switching are as follows:

1. Overhead of establishing the path is only spent at the start of the session.

2. Data format is simple since the path is already established beforehand.

3. In-sequence delivery of data is possible since all packets will arrive using the

same route.

4. The channel bandwidth is guaranteed and this suites constant bit rate traffic.

5. The channel is better utilized carrying constant bit rate traffic and not bursty

traffic.

6. Traffic information is easily observable since switching nodes maintain informa-

tion about each call.

To establish a path in circuit switching, three consecutive phases are required:

1. Connection establishment: For data to be transferred between two end users,

a connection (path) must be established. The intermediate switches exchange

information related to the availability of a path and inform the end users when

the path is available. This is similar to using the phone by waiting for the dial

tone, then dialing the desired number.

2. Data transfer: Data can now be moved between the users over the connection

that was established. The type of connection will determine the data rate, average

delay, and data loss rate. This is similar to talking on the phone once the other

party picks up the phone.

13.4 Circuit and Packet Switching 483

3. Connection tear down: After data transfer is complete, the end users inform the

intermediate switches to free the connection. This is similar to placing the phone

on the hook to inform the phone company that the circuit can be released.

13.4.2 Packet Switching

In packet switching, data are broken into packets of fixed or variable size, depending

on the protocol used. There are two approaches for packet switching: datagram and

virtual circuit.

In datagram switching, each packet carries with it all the routing information it

needs to reach its destination and each packet is treated independently of the ones

before it or after it. In fact, it is possible that different packets might travel down

different paths. This is actually an advantage since the resulting network is immune

to faults, and packets can be dynamically routed on any available links. This was the

main reason for using packet communication in the first place in the 1970s to build a

highly fault-tolerant communication network that is immune to enemy attack. Since

each packet carries all the information it needs to determine its destination, there

is no need to establish a connection before transmitting the data. The connection

establishment phase of circuit switching is removed. However, packet switching

carries the following penalties:

1. In-sequence delivery of data is not possible since different packets might travel

down different paths.

2. Packet routing will be complex since the router has to choose the optimum route

to send each packet.

3. Packet delay will vary depending on the route chosen for each packet.

4. Packet loss cannot be detected by the network. The end-nodes are able to detect

lost packets.

5. Traffic information is not easily observable since switching nodes do not have

information about the state of each stream.

In virtual circuit switching, a unique path is used to move data between the two

end users. This is similar to the circuit switching approach. However, the channel or

path could be used by other data when there are no packets to send. Virtual circuit

switching has several advantages over circuit switching and datagram switching:

1. Since packets belonging to a certain session are distinct, it is easy to associate

quality of service guarantees to the session and deliver those guarantees.

2. The ability to identify individual sessions enables the service provider to guar-

antee the service, monitor the user traffics, and charge for the services provided.

3. Different classes of service are easily established for the different sessions. The

cost of these services is definitely cheaper compared to leasing a private tele-

phone line.

4. The packets have a simple format since the routing information has been deter-

mined during path, or connection, establishment phase.

484 13 Switches and Routers

5. Packet routing is simple since there is only one route associated with all the

packets belonging to a call.

6. In-sequence delivery of data is possible since the packets from a certain call

traverse the same route.

7. The channel is well utilized since different calls share the same channel. This

results in an overall gain in the network capacity, which is usually referred to as

statistical gain.

8. Packet loss can be detected by the network since the packets follow each other

in sequence and each carries a unique sequence number.

9. Virtual circuit switching is suited to both bursty and constant bit rate traffic.

To establish a path in virtual circuit switching, the same steps are followed as

in circuit switching: connection establishment, data transfer, then connection tear

down.

13.5 Packet Switching Hardware

We review some of the hardware components that are commonly used in communi-

cation networks. We should point out that the following definitions are not very strict

since the capabilities of the components become more sophisticated with advances

in technology. The component capabilities are implemented in software or hardware

and there are grey areas where a device bridges the gap between two classifications

or partially implements the functionality of a given class of devices. We discuss

below several important networking components in the order of their level of com-

plexity. Figure 13.5 shows the ISO and TCP/IP reference model layers implemented

by the different components: hubs, bridges, switches, routers, and gateways.

13.5.1 End-Node

An end-node is a device that is attached to the network. The user accesses the net-

work through the end-node, which could be a workstation, a PC, a printer, a file

server, etc.

Fig. 13.5 Hubs, bridges,

switches, routers, and

gateways and the layers

implemented by each

component

ISO Model

Hub

Bridge

Switch

Router

Gateway

TCP/IP Model

Application

Transport

Internet

Host-to-network

13.5 Packet Switching Hardware 485

13.5.2 Hub

A hub connects several segments of a LAN. A hub has several ports such that when

a packet arrives at a port, it is copied to all the other ports so that all segments of the

LAN see the packet. In that sense, a hub acts as a repeater to repeat one message on

one LAN to all the other LANs [3].

A passive hub serves simply as a conduit for the data, enabling it to go from

one device (or network segment) to another. An intelligent hub includes additional

features that enable an administrator to monitor the traffic passing through the hub

and to configure each port in the hub. A switching hub actually reads the destination

address of each packet and then forwards the packet to the correct port based on

the header information. A hub does not improve network capacity or performance.

It only acts as the “wiring” between the network segments. Thus we can think of

the hub as operating mainly in Layer 1 of the ISO reference model since it only

enables the operation of the physical layer of the ISO reference model. Figure 13.5

shows the location of the hub and the other main network connectivity components

in relation to the ISO reference model layers.

13.5.3 Bridge

A bridge is a device that connects two local-area networks (LANs) or two segments

of the same LAN. The two LANs being connected can be alike or dissimilar. For ex-

ample, a bridge can connect an Ethernet with a token-ring network. Unlike routers,

bridges are protocol independent. They simply forward packets without analyzing

and re-routing messages. Consequently, they are faster than routers, but less versa-

tile. A bridge uses the packet header to determine whether to pass the packet to the

other LAN or not. A bridge operates at Layer 2 of the ISO reference model since it

supports the operation of the data link (network access ) layer . A bridge is simpler

than a router but still requires a switch for delivering the packets to the correct output

port.

13.5.4 Switch

A switch connects several LANs. A switch has several ports such that when a

packet arrives at a port, it is forwarded only to the appropriate output port based

on the header information. In that sense, a switch provides a temporary dedicated

connection between an input port and an output port. A switch improves network

performance by dividing the network into several independent segments, thereby

increasing the overall capacity. In that sense, the switch is smarter than a hub. Typ-

ically, switches work in Layer 2 of the ISO reference model, which is equivalent

to a bridge. The new trend is to move to Layer 3 switching, which is capable of

switching millions of packets per second. It should be mentioned that a switch is

486 13 Switches and Routers

protocol specific. However, newer switches are able to handle several protocols such

as multi-protocol label switching (MPLS).

13.5.5 Router

A router connects networks that may or may not be similar. A router uses the packet

header and a forwarding table to determine the best way a packet should go between

the networks. Routers use ICMP

to communicate with each other and determine the

best route between any two hosts. Very little filtering of data is done through routers.

Routers know how the whole network is connected and how to move information

from one part of the network to another. They free the end-nodes from having to do

these tasks. Routers enhance the network by connecting networks that use different

protocols. Note that a router requires the use of a switch to perform its packet rout-

ing (switching) functions. Routers are smarter than hubs and switches. The router

operates at Layer 3 of the ISO reference model since its supports the operation of

the network layer (such as data transmission and switching) [2] .

13.5.6 Gateway

A gateway is a computer that uses a combination of hardware and software to link

two different types of networks using different protocols. Gateways between e-mail

systems, for example, allow users on different e-mail systems to exchange messages.

Thus a gateway translates between two different protocols and sometimes topolo-

gies. For example, a gateway is needed to translate between TCP/IP over Ethernet

and ATM over SONET. We can think of the gateway as operating mainly above

Layer 3 of the ISO model since its enables the operation of the application layer and

above.

From the above definitions, we see that a switch is the basic component of net-

working, and the design of an efficient high-speed switch is absolutely necessary to

obtain networks capable of meeting customer demands for ever-increasing capacity

and reduced delay.

13.6 Basic Switch Components

As was explained above, network routers rely on switches to perform their functions.

Thus it is worthwhile to study the construction of switches in more detail. A switch

is a hardware device that accepts packets at its inputs and routes them to its outputs

according to the routing information provided in the packet header and the switch

Internet Control Message Protocol. ICMP supports packets containing error, control, and infor-

mational messages.

13.6 Basic Switch Components 487

Fig. 13.6 Basic components

of a switch

Input

Switch Fabric

(SF)

Output

Control

Input

Ports

Outpu

Ports

Interface to

Control Processor

...

Network Processor

Unit (NPU)

routing table. Figure 13.6 is a block diagram showing the main components of a

switch.

The switch has three main architectural components: a network processor unit

(NPU), a controller, a datapath comprising input/output ports, and switch fabric.

The functionalities of each are explained in the following sections. In general, the

functions of intensive data processing and control should be distributed, whenever

possible, among the different switch components to reduce the delay and be able

to handle many inputs/outputs simultaneously. The components of the switch that

have the most impact on its performance are the storage buffers/queues and the

switch fabric. For example, packet loss in the switch results due to buffer overflow

or inability to establish a path from an input to an output port through the switching

fabric. Also, the maximum line rate depends on the memory access speed.

13.6.1 Network Processing Unit (NPU)

The network processing unit is required to do compute-intensive tasks to enable

the switch to process data at high speeds. An NPU is a programmable processor

with special instructions or hardware components that are specifically designed to

efficiently perform networking tasks. A general-purpose processor proves too slow

to do the required networking tasks. However, specialized hardware meets the de-

mands but has the disadvantages that once the tasks or protocols are upgraded, a

major redesign is required and this takes time. By the time a specialized hardware is

available, the protocols might have changed already. Thus the major motives for an

NPU are flexibility/programmability and efficiency in executing networking tasks.

Figure 13.7 shows a switch with NPU-specialized hardware components that do

specific tasks. Examples of the tasks that the NPU might be required to perform

include the following:

1. Implementation of security protocols for firewalls, network security, data encryp-

tion/decryption, etc

488 13 Switches and Routers

Classify &

Forward

Classify &

Forward

N input

buffers

N input

buffers

Line Card # 1

...

Deep packet

parsing

processor

Security

processor

Network

processor

controller

...

PHY

* POS

* ATM

* ETHERNET

PHY

* POS

* ATM

* ETHERNET

PHY

* POS

* ATM

* ETHERNET

PHY

* POS

* ATM

* ETHERNET

Line Card # N

Schdeuler

Virtual

Queues

Schdeuler

Virtual

Queues

Switch fabric/

Bus Matrix

Fig. 13.7 A switch incorporating NPU components

2. Deep packet search which is essentially string search for pattern matching using

the packet payload as input

3. Implementation of quality of service protocols

4. Traffic shaping

5. Packet routing using routing tables

6. Interface

13.6.2 Control Section

The control section deals with packet streams and establishing and tearing down

circuits and is composed of the bottom two components of the switch block diagram

in Fig. 13.6. The control section performs the following functions:

1. Maintains the contents of the routing table, which determines the proper destina-

tion output port of an incoming packet

2. For the case of circuit switching, decides whether to accept new connections or

not based on current utilization of switch resources

3. Provides congestion control for the switch by continually monitoring the switch

resources (e.g., buffer occupancy) and issuing proper actions

4. Assigns switch resources to the established connections based on the class of

service

13.6 Basic Switch Components 489

It should be mentioned that these functionalities could be centralized or they

could be distributed between the input and output ports. The latter option is desirable

to ensure high-speed operation.

13.6.3 Datapath Section

The datapath deals with individual packets or cells and is composed of the top three

components of the switch block diagram in Fig. 13.6. The datapath performs the

following functions:

1. Accepts incoming packets on any of its N input ports and stores them in tempo-

rary buffers for processing their header information

2. Establishes a path to the desired output port through the switch fabric (SF)

3. Stores the routed packets in the output queues and schedules the stored packets

for transmission based on some scheduling protocol

13.6.4 Switch Fabric

The switch fabric (SF) establishes the required paths between pairs of input and out-

put ports. The switch fabric must also support any type of connection such as single

cast (one input to one output), multicast (one input to many outputs), broadcast (one

input to all outputs), or hot point (many inputs to one output). A detailed discussion

of switch fabrics and their performance is found in Chapter 14.

13.6.5 Lookup Table Design

The routing or lookup table stores information about which output ports should

receive a packet that arrives at an input port. This information is maintained and

updated by the control processor. The data in the lookup table could be organized

using any of the following approaches:

1. Heap storage: Store the data in a heap with no particular order using a random-

access memory (DRAM or SRAM). This approach is simple but searching for

a particular data item requires searching the entire memory. RAMs suffer from

I/O port limitations (typically one!) and large cycle time. Thus accessing the

database is done one item at a time using a slow search strategy which is not

practical in high-speed switches.

2. Content-addressable memory (CAM): This is sometimes called associative mem-

ory or associative storage. CAM could be a small memory but complex in design

and slow in performance. Searching for a data item is done in a distributed fash-

ion within the memory which speeds up the search operation. The design of an

490 13 Switches and Routers

efficient and fast CAM is certainly a challenging and exciting hardware design

problem.

3. Hash tables: Here the input header information is compressed to a smaller num-

ber of bits (e.g., from 48 bits to 16 bits) using a hashing function to reduce the

RAM size [4–6]. The hashing function should be simple to implement without

requiring much processing time. Typically, hashing functions are implemented

using a linear feedback shift register (LFSR) that performs polynomial division.

The input to the LFSR is treated as a polynomial and the LFSR contents are the

“signature” that corresponds to the input. See Appendix F for a discussion of

hashing.

4. Balanced tree (B-tree): The B-tree is a data structure that is used to efficiently

build large dictionaries and implement the algorithms used to search, insert, and

delete keys from it. The advantage of using B-trees for constructing lookup tables

is the small time required to search for the routing information. However, com-

plex hardware design is required to implement the other lookup table functions

such as data insertion and deletion. Again, the design of B-trees is a very chal-

lenging and exciting hardware design project. See Appendix F for a discussion

of B-trees.

In an ATM switch, the routing table uses direct lookup to determine the desti-

nation output port and to update the VPI/VCI bytes. For an Ethernet switch, the

lookup table uses associative lookup (content-addressable memory or CAM). For

an IP router, the routing table could be based on the new CIDR or cache memory.

13.7 Switch Functions

A switch or a router has to perform several functions beside simply routing packets

from its inputs to its outputs.

13.7.1 Routing

The switch or router must be able to read the header of each incoming packet to

determine which output link must be used to move the packet to its destination. It is

obvious that an arriving packet cannot be routed until packet classification based on

its header information has been performed. These routing decisions are done using

routing tables. Techniques for building routing tables are discussed in more detail

in Section 13.6.5 and in Appendix F.

13.7.2 Traffic Management

When too many packets are present in the network, congestion is said to have taken

place. When congestion occurs in a router, the buffers become filled and packets