Handbook of Computer Networks: LANs, MANs, WANs, The

Internet, and Global, Cellular, and Wireless Networks

by Hossein Bidgoli
Copyright 2008 John Wiley & Sons, Inc.

Packet Switching
Qinqing Zhang and Qi Bi, Bell Laboratory, Alcatel-Lucent Technologies

Introduction to Packet Switching

Fundamentals of Packet Switching
Packets
Nodes
Packet Switching
Evolution of Packet Switching
History of Packet Switching
Interconnection in Packet-Switched Networks
Interconnection: Switches, Bridges, Routers,
and Gateways

136
136
136
137
137
138
138
139

141
141
141
142
143
144
144
145
145

139

INTRODUCTION TO PACKET
SWITCHING
Packet switching is the dominant communication technology in modern data networking and telecommunications.
In previous chapters, the concepts of computer networks
were introduced and different type of networks were described based on scale, connection method, functionality,
topology, or services. The communication between computers or devices involves the term switching, which describes how information is exchanged between the input
ports and output ports at each network element.
There have always been two fundamental and competing switching technologies in communications: static
allocation and dynamic allocation of the transmission
bandwidth. The public switched telephone network
(PSTN) is a typical circuit-switched network, where a xed
bandwidth is pre-allocated for the duration of a call. The
early radio system, that is the advanced mobile phone
systems (AMPS), is also circuit-switched where the radio
spectrum is pre-allocated during a mobile call. On the other
hand, message, telegraph, and mail systems have been
operated by dynamically allocating bandwidth or spaces
after a message is received at the time. They never attempt
to schedule bandwidth or space over the end-to-end
source to destination path.
There are three major switching techniques, that is,
packet switching, circuit switching, and message switching.
In packet switching, packets (units of information block)
are individually routed among nodes over data links that are
shared by many other nodes in the data networks. In contrast with circuit switching that pre-allocates the transmission bandwidth for a user, packet switching allocates the
transmission bandwidth dynamically, permitting many
users to share the same transmission link previously required by one user. This improves the transmission efciency especially when users transmit at variable bit rates.
Packet switching optimizes the usage of the bandwidth
available in a network and saves the transmission cost.
It also improves the reliability and functional exibility
of packet delivery in communication networks. Packet
switching has been so successful and become the exclusive
136

Main Techniques in Packet Switching

X.25
Frame Relay
ATM
TCP/IP
Other Advanced Packet-Switching Networks
Glossary
Cross References
References

communication paradigm in all the data networks built

throughout the world. In this chapter, we describe the fundamentals, history and evolution, and key techniques of
packet switching.

FUNDAMENTALS OF PACKET
SWITCHING
Packets
A packet is a block of data that carries user information
exchanged over a communication link. It usually consists
of three elements: header, payload, and trailer, as shown in
Figure 1. The rst element, header, contains address and
administrative information that allows the packet be delivered by the network nodes from the source to the destination. The second element, payload, contains the user
information that needs to be exchanged in the network.
The third element, trailer, usually contains information for
error detection, allowing receivers to verify that packets
do not have errors during transmission. (If errors occur
during transmission and cannot be corrected, the packet
is usually discarded.) Sometimes, a packet may not have a
trailer. The payload together with the header contains all
the information needed for packet delivery.
A packet is analogous to a letter (payload) sent through
the mail (network) with the address (header) written
on the envelope.
Unlike a message (in message switching), the length of
a packet is limited and can vary between successive packets. Packets are usually transmitted via frames, which are
either xed-length or variable length data blocks transmitted over the actual physical links. Sometimes packets and
frames are interchangeable in some places but they actually have different meaning. Packets are usually referred

Header

Payload

Figure 1: The format of a packet

Trailer

FUNDAMENTALS OF PACKET SWITCHING

as the transmission unit at layer 3 or the network layer, in

a layered network protocol stack, whereas frames are usually referred as the transmission unit at layer 1 or layer 2,
the physical layer or the link layer (Tanenbaum 1981).

Nodes
A node is a physical device that is connected as part of a
data network. Nodes can be personal computers, workstations or servers, specialized data processors, cell phones,
personal digital assistants (PDAs), or various other network appliances. Depending on their functionalities,
nodes can be characterized in different types. For example, in the SNA (systems network architecture) network
architecture invented in early stages of computer networks
(Cypser 1978), there are four type of nodes dened. Type
I nodes are terminals. Type 2 nodes are controllers,
machines that supervise the behaviors of terminals. Type 4
nodes are front-end processors, devices that relieve the
main CPU of the processing and interrupt handling in
data communications. Type 5 nodes are the main hosts
themselves. There are no type 3 nodes. Nodes that route
data for the other network devices as well as themselves
are sometimes called super-nodes.

Packet Switching
Circuit Switching and Packet Switching
Computer-to-computer communication has some fundamentally differences from human-to-human communication. When you or your telephone places a telephone call,
the switching equipment at the central ofce attempts to
allocate a physical path all the way from the callers telephone to the called telephone. This switching technique is
called circuit switching. Figure 2 shows a simplied schematic model of circuit switching. In this example, there
are multiple switching elements between the two telephones. Each switch has the same number of incoming
lines and outgoing lines. When a call is placed through a
switch, a physical connection is established between the
incoming ports and outgoing ports. The dotted line shows
the allocated physical path between the two end points.
This dedicated link exists during the entire phone conversation. An important property of circuit switching is that
it needs certain time to setup an end-to-end connection

Figure 2: Circuit switching

137

before any information can be sent. This is usually called

the call setup time. Once the connection is established,
the data transmission delay is only the propagation time,
which is quite small.
In contrast to circuit switching, packet switching does
not require any dedicated link or path be established in
advance between sender and receiver. Instead, the users overall message is broken up into a number of small
packets, each of which is sent separately. Figure 3 shows
a simplied schematic model of packet switching. Each
packet of user information is labeled to identify its source
and destination before it is sent. Each packet is stored at
the receiving switching ofce and then forwarded later,
one hop at a time. The receiving end re-assembles the
packets in their proper order, with the assistance of
the sequence number and other administrative information stored in the header and trailer elds. A network
uses this store-and-forward technique and allocates the
most efcient route available at the time for each packet.

Packet Switching and Message Switching

Yet another alternative switching technique is message switching. Message switching is very similar to packet
switching, where there is no need to establish a physical
path or link in advance between both ends. Compared to
packet switching, message switching puts no restriction
on the block size. In other words, the entire message is
the transmission and switching unit at each switch. As a
result, the switch needs to have large buffer or memory
size to store and forward a large message, resulting in
a longer queueing and transmission delay and reduced
throughput. The advantage of message switching is that
it maintains the complete message delivery from sender
to receiver. Data networks are usually packet switched
instead of message switched. More descriptions on message switching are provided in a subsequent chapter.
Circuit switching and packet switching differ in many
respects. The key difference is that circuit switching
statically reserves the required end-to-end bandwidth before any data can be sent. Any unused bandwidth on an
allocated end-to-end circuit is just wasted. Packet switching acquires and releases the required bandwidth on
a packet-by-packet basis. The unused bandwidth for a
users trafc may be utilized by packets from other unrelated users going to different destinations. Therefore,

138

PACKET SWITCHING

A3 A2 A1

A3 A2 B2 A1
Message to user A
A3 A2 A1

User A

B3 B2 B1

B2

Message to user B
B3 B1

B3 B2 B1

User B

packet switching utilizes the network bandwidth more

efciently than circuit switching.
Because there is no dedicated circuit or path for a users
trafc, packets may be routed by each network node on
different routes at the time. Packets may be delivered out
of order to the destination with packet switching. Reordering of packets can never happen with circuit switching.
Transmission capacity between pairs of nodes in a
packet-switched network is generally not split up into
separately physical channels, each of which has a xed
bandwidth. Instead, the entire available bandwidth between pairs of nodes is treated as a single high bit-rate
pipe and shared by all the packets sent on the link. In
this way, individual packets are transported more quickly,
that is, at full speed of the line rate, and bursts of transmission can be accommodated.
A problem occurs when more than one data sources
try to send packets at the same time exceeding the bandwidth of the data link. This situation is accommodated by
buffers at both sending and receiving ends of the connection between pairs of nodes. The use of buffers smoothes
out the burstness of the trafc and improves the link utilization. This is achieved by statistically multiplexing the
packets from different sources sharing the same link. The
statistical average total bit-rate must be slightly lower
than the link bit-rate so that there is no packet dropping
as a result of buffer overow.
The charging algorithms between the two switching
technologies are different. In a circuit-switched network,
carriers charge the clients based on the connection time
and transmission distance. In a packet-switched network,
carriers charge the clients based on both the time and
number of bytes or packets carried. Transmission distance usually does not matter except when it involves the
network layout internationally.

EVOLUTION OF PACKET SWITCHING

Before the modern advances in computer technology and
digital signal processing, systems with dynamic allocation were necessarily limited to non-real time communications, because many manual sorting and routing
decisions were required along the source to destination
path of each message. In late 1960s, virtually all interactive data communication networks were circuit switched,
the same as the telephone network. Interactive data trafc
occurs in short bursts and thus 90% or more of the static

Figure 3: Packet switching

allocated bandwidth is wasted. The rapid advances in

technology evolution have made digital electronics with
fast processing power inexpensive enough for a complete
redesign of communication networks. The packetswitching concept was introduced to make the dynamic
allocation systems superior to static allocation systems in
terms of cost, connection time, transport efciency, reliability, and exibility. As a result, packet switching has
become the dominant paradigm in modern communication networks and offered substantial economic and performance advantages over the conventional systems.

History of Packet Switching

Packet switching was evolved from the basic dynamic allocation technique used for conventional mail, telegraph,
and paper tape switching systems. Bandwidth is allocated
only when a block of data is ready to be sent, and only
enough for that particular data block to be transferred over
the data link at the time. Depending on the trafc characteristics of the data being transferred, packet switching
is generally more efcient (3-100 times more) than static
allocation approaches, because it can reduce the wasted
available bandwidth resources. This is achieved by adding both processing power and buffer storage resources at
each network switch along the path. The economic tradeoff between circuit switching and packet switching is obvious: if the bandwidth is cheap, use circuit switching; if
computing is cheap, use packet switching.
The rst published description of the so-called packet
switching was an 11-volumn analysis, On Distributed
Communications, written by Paul Baran of the Rand Corporation in August 1964 (Baran 1964). It proposed a fully
distributed packet-switching system to provide for all
military communications of data and voice. The RANDs
proposed packet-switching system not only achieved the
original goal but also projected superior economics for
both voice and data communications.
Independently Donald Davies from the National Physical Laboratory (NPL) in the United Kingdom conducted
detail design of a store-and-forward packet switching system. The rst ofcial publication of the NPL proposal was
in October 1967. Davies original proposal, developed in
late 1965, was very similar to the actual networks being
built today in almost all respects. His cost analysis demonstrated strong economic advantages for the packetswitching technique.

INTERCONNECTION IN PACKET-SWITCHED NETWORKS

Barans study had its inuence to Robert Taylor and

J. C. R. Licklider from the Advanced Research Projects
Agency (ARPA). The interesting discussions motivated
Lawrence Roberts to initiate the rst two actual network
projects. Merrill and Roberts (Roberts and Merrill 1966)
did an experiment of connecting the TX-2 computer in
Massachusetts to the Q-32 computer in California with a
low-speed dial-up telephone line creating the rst widearea computer network. This experiment realized that
time-shared computers could work together, running
programs and retrieving data on the remote machine.
ARPANET is the creation of ARPA (now DARPA), the
(Defense) Advanced Research Projects Agency of the U.S.
Department of Defense. The design proposal, which was
published in June 1967, consisted of a packet-switching
network, with minicomputers at each computer site as the
packet switches and interfacing devices, interconnected
by 50 Kbps leased lines. The original ARPANET was an
experimental four-node network that became operation in
December 1969. Each minicomputer took blocks of data
from the computers and terminals connected to it, subdivided the data into 128-byte packets and added a header
specifying the source and destination addresses. The
minicomputer used a dynamically updated routing table
to send the packets over the most free line with the fastest
route toward the destination. Upon receiving a packet,
the next minicomputer would acknowledge it and conducted the same routing process independently from
the previous node. Therefore, ARPANET (Roberts 1974;
Roberts 1978) was a completely distributed network with
a dynamic routing algorithm on a packet-by-packet basis.
Much of our present knowledge of networking is a direct
result of this pioneering work.

INTERCONNECTION IN PACKETSWITCHED NETWORKS

Packet-switched network is a fully distributed system
that dynamically routes the packets based on a continuous evaluation of the delay on the path, line availability,
and queue length at the network node. The interconnection of numerous networks of different types or the connections within a network requires the physical devices
that have different functionalities and purposes to serve
the network.

Interconnection: Switches, Bridges, Routers,

and Gateways

139

sense of making connections and relaying the speech information. In a packet-switched network, for example, in
the Ethernet local area network (LAN), a switch examines the physical devices media access control or MAC
address in each incoming packet and determines which
output port to forward the packet. Figure 4 illustrates a
simplied structure of a switch matrix in a central ofce.
All the outgoing trunk circuits (numbered 1 to 4) may be
accessed by any of the customer lines (marked A to D).
Figure 5 illustrates a simplied internal structure of a
packet switch device. It consists of a bus, or multiple
buses, connecting together each of the incoming and outgoing ports. Packets received from any of the incoming
ports are rst stored in the buffers. The switching logic
analyzes the address in the packet header and decides
which outgoing port the packet is sent to.
A switch usually uses store-and-forward, or cut-through
forwarding method. In store-and-forward method, the
switch receives and buffers each frame entirely, typically
performs a checksum on the frame, and then forwards
it on the output port. In cut-through method, the switch
only checks the frames physical layer address and then
forwards it to the output port. It does not do any error
checking on the frame.
A switch only connects data from an incoming port
to an output port. It does not monitor the trafc because
each port is isolated, and only the sending and receiving ports are connected when they transmit the data.
Two common methods, that is, port mirroring and switch
monitoring (SMON), were specically designed to allow

A
B
C
D

Figure 4: Switch matrix in an exchange ofce

Port A

Port B

Switches
A switch is a computer networking device that channels
incoming data from any of the multiple incoming physical ports to a specic output port toward its destination.
Switches are used in both circuit-switched networks
and packet-switched networks. In the traditional circuitswitched telephone network, one or more switches are
used to set up a dedicated connection or circuit for an exchange between two or more parties. A telephone exchange
or central ofce houses equipment that is commonly known
as simply a switch, which is a piece of equipment that
connects phone calls. It makes phone calls work in the

Port 1

Port 2

Figure 5: Packet switch internal structure

140

PACKET SWITCHING

a network manager to monitor the trafc in a network

with switches. In the port mirroring method, a switch
sends a copy of network packets to a monitoring network
connection so that the network manager can collect the
information and monitor the trafc. The SMON (RFC
2613) is a protocol dened by the IETF RFC 2613 for controlling the interfaces and facilities between the switches
and network managers for port mirroring.

Bridges
A bridge is a computer networking device that connects
multiple network segments along the data link layer to
operate as a single network. It works by using bridging as
what its name entails, by connecting two sides of the adjacent networks. It forwards the trafc from one network
to another network.
A bridge has intelligence built in the hardware to determine which packets should be transferred into another network. It examines the addresses (indicating a
destination service access point and a source service access point) in the logical link control (LLC) header of each
packet and transfers the relevant packets to the second
network directly or via a second bridge. If the physical
structure of the two networks is different, for example,
one network is an Ethernet, the other is a token ring as
shown in Figure 6, the bridge will transform the packet
into the right format.
Primitive bridges are relatively cheap. They provide a
very economic means for self-congurable interconnection. However, bridges have some limitations of their usage and functionalities. They do not limit the scope of
broadcasts and do not scale to large networks. Bridges
result in very complicated topologies that are extremely
difcult to manage. Thus bridges are not recommended
for large and complex networks. Instead, the router appears and is used to provide a more complex and intelligent functionality of interconnection in packet-switched
networks.

There are different options when designing a network.

One option is to put multiple segments into one bridged
network. Another option is to divide the network into different sub-networks interconnected by routers. If a host
moves between segments in a routed network, it has to get
a new IP address and therefore break the transport layer
connections, that is, TCP/IP connection. If the host moves
in a bridged network, it does not have to recongure the
packet format and thus is simpler and more economic.
The drawback of a bridged network is that it lacks the intelligence and scalability in large and complex networks.

Gateways
A gateway is a computer networking device for interfacing with another network that uses different protocols. It
is also called a protocol converter and can operate at any
layer of the network model. The function of a gateway
is much more complex than that of a router or switch.
Typically, a gateway must convert one protocol stack into
another.
A gateway may contain devices such as protocol translators, impedence matching devices, rate converters, fault
isolators, or signal translators as necessary to provide system interoperability. It also requires the establishment of
mutually acceptable administrative procedures between
the two networks. A protocol translation/mapping gateway interconnects networks with different network protocol technologies by performing the required protocol
conversions.
For example, a gateway may connect a local area network (LAN) or wireless LAN (WLAN) to the Internet or
other wide area network (WAN). In this case the gateway
connects an IPX/SPX (the LAN) to a TCP/IP network (the
Internet), as shown in Figure 8.
Gateways that connect two IP-based networks, like
TCP/IP, have two IP addresses, one on each network. An
address like 192.168.1.xxx is an address in LAN, to which
trafc is sent from the LAN. The other IP address is an

Routers
A router is a computer networking device that forwards
data packets across the network toward their destinations
based on the routing algorithms. A router acts as a junction between two networks and transfers data packets
between them (see Figure 7). Routers are more intelligent
than switches and bridges. They are designed to learn
the topology of complicated networks that are constantly
changing and expanding and determine the best route
for packets or packet ows to their destinations. The key
design of routers is the routing algorithm. Routers can
learn the network topology through experience, that is,
the previous successful routes, and update the routing
table accordingly.

Router
Router
Router

Figure 7: Network router

IP Network

LAN

Ethernet LAN

Token Ring LAN

Gateway

Bridge

Figure 6: LAN bridge

Figure 8: Gateway connecting two different networks

MAIN TECHNIQUES IN PACKET SWITCHING

address in WAN, to which trafc is sent from the WAN.

When talking about the gateway IP address, it commonly
means the address of the gateway in LAN.
The addresses of computers connected to the LAN are
hidden behind the gateway. This means that the WAN
can only see the gateways IP address. To regulate trafc
between the WAN and the LAN, the gateway commonly
performs network address translation (NAT), presenting
all of the LAN trafc to the WAN as coming from the gateways WAN IP address and doing packet sorting and distribution of return WAN trafc to the local area network.

MAIN TECHNIQUES IN PACKET

SWITCHING
X.25
X.25 is the rst international standard recommended
by International Telecommunications Union (ITU) for
packet-switched networks. It was developed in the early
stages of packet networks evolution for the nations to
agree on a standard user interface to the networks to facilitate network interconnection and permit easier user
attachment. X.25 has been widely adopted and used in
most packet switched networks.
The X.25 recommendation denes the protocols between a data terminal equipment (DTE), for example,
personal computer or computer terminal controller, and
a data circuit terminating equipment (DCE), for example,
the connection point to a packet-switched network, as
shown in Figure 9. It denes protocols corresponding to
layer 1 (physical layer), layer 2 (link layer), and layer 3
(packet layer) in the International Standard Organization
(ISO)s Open System Interconnect (OSI) model.
The physical layer connection may either be X.21 for
digital leased line or X.21 bis for V.24/V.28 modem in conjunction with an analogue leased line. The X.25 protocol
provides for the data blocks for up to 4095 virtual circuits (VCs) on a single full-duplex leased line interface to
the network. It includes all procedures for call setup and
tear-down. One important feature of this interface is the
notion of independent ow control on each VC. The ow
control enables the network and the user to regulate the
trafc on the ow to protect itself from congestion and
overow. In early networks like ARPANET that did not
have the ow control capability, the network had to depend on the host to insure that no user transmitted more
data to the network than the network could handle. The
network had to shut off the entire host interface if congestion happened, which could be disastrous to other users communicating with the host or network.

141

Another signicant aspect of X.25 is that it denes both

layer 1, layer 2, and layer 3 protocol interfaces. These protocols are called the link access procedures (LAP) and the
packet level interface. The link access procedure assures
the correct delivery of data across the link connecting a
DTE to an DCE for multiplexing of logical channels. The
packet level interface guarantees the end-to-end delivery
of data across the entire network.
The link access procedures balanced (LAPB) protocol
provides for the balanced class of procedure and also allows making a single logical link using multiple physical
circuits. The link access procedure uses the principles and
terminology of high-level data link control (HDLC) as dened by ISO. HDLC provides error checksum and ensures
the error-free transmission of data information across the
link from a DTE to a DCE. However, it does not determine
where the information should be forwarded by the DCE
within the network, nor ensure its correct delivery at the
destination in the packet network. This function is handled by the OSI layer 3 protocol, that is, the X.25 packet
level interface.
After X.25 was adopted in March 1976, many additional standards have been agreed on and developed as
well, all patterned around X.25. For example, X.31 has
been adopted as the standard interface for physical layer
connection between a DTE and DCE via an integrated
services digital network (ISDN). X.32 species the use of
dial-up connection for a packet mode connection via the
telephone or ISDN network to an X.25 exchange. Finally,
X.75 denes the standard protocol for connecting international networks.

Frame Relay
Frame relay is a standard protocol for fast packet switching in LAN. It has much less overhead than the earlier
X.25 networks and operates more efciently. Packets vary
in length and are call frames for this protocol. Erroneous or bad frames are discarded instead of retransmitted
and thus packets are switched more quickly. Frame relay
began its commercial service in 1992 and is now widely
deployed.
Standards for the frame relay protocol have been developed by American National Standards Institute (ANSI)
and International telephone and telegraph consultative
committee (CCITT), now known as ITU-T simultaneously.
Frame relay is essentially an enhancement of X.25,
taking advantage of the widespread implementation of
ber optic communication links by long-distance carriers. Fiber is much less prone to introducing errors in
a data stream. Therefore frame relay does not use the

Packet-Switched
Network

Figure 9: X.25
structure

data

network

DTE

DCE

DCE

DTE

142

PACKET SWITCHING

extensive error checking in X.25 at the switching nodes.

The error-handling processes are instead completed by
the sending and receiving devices.
The frame relay frame is transmitted to its destination
using the concepts of virtual circuits as in X.25, that is, logical paths from an originating point in the network to a destination point. Virtual circuits may be permanent (PVCs)
or switched (SVCs). PVCs are set up administratively by
the network manager for a dedicated point-to-point connection. SVCs are set up dynamically on a call-by-call
basis. Because virtual circuits consume bandwidth only
when they are used to transport data, many virtual circuits
can exist simultaneously across a given transmission line.
In addition, each device can use more of the bandwidth as
necessary, and thus operate at higher speeds. Frame relay
is designed to operate at speeds up to 1.5 Mbps, and may
be enhanced to operate at higher speeds.
Frame relay is particularly well-suited to the interconnection of LANs that generate bursty trafc consisting of
variable-length frames of data. Frame relay accepts this
trafc as is, adding only a wide area network address at
the front and its own check sequence at the end of each
frame. Frame relay interfaces for customer premise equipment such as routers, bridges, and hubs are available
from a number of vendors.
Frame relay switches are also available, and numerous
carriers offer public frame relay services. As the technology and standards are rened and carrier tariffs are claried, frame relay networks are expected to replace many
X.25 networks during the next several years. However,
frame relay is not well-suited to the transmission of realtime voice or video, because of the variable delay allowed
between frames.

ATM
ATM stands for asynchronous transfer mode. ATM is
a high-speed advanced packet-switching scheme. ATM
makes all its packets one length, i.e., the so called
ATM cells. Each cell has 53 bytes, 48 bytes of data, and
5 bytes of header information. These uniformly small
packets or cells let data ow smoothly. ATM also boasts
improved error control compared to conventional packet
switching, as well as numerous other features that make
it a core technology of data networks.
ATM was initially designed to provide a single unied
networking standard that could support both synchronous channel networking and packet-based networking
(IP, frame relay, and so on), whilst supporting multiple
levels of quality of service (QoS) for packet data. It was
intended to resolve the conict between circuit-switched
networks and packet-switched networks by mapping both
bit streams and packet streams onto a stream of small
xed-size cells tagged with virtual circuit identiers. The
cells are typically sent on demand within a synchronous
time-slot pattern in a synchronous bit-stream. The asynchronous part here is the sending of the cells, which does
not need to follow any synchronous pattern.
In its original conception, ATM was considered as the
enabling technology of the broadband integrated services
digital network (B-ISDN) that would replace the existing
PSTN. The full suite of ATM standards provides denitions

for layer 1 (physical connections), layer 2 (data link layer),

and layer 3 (network) of the classical OSI seven-layer
networking model. Standards that dene ATM networks
are established by two different organizations, the ITU
and ATM Forum. ATM Forum is an industry consortium
that is focused on ATM. The activities of this organization included setting of the technical standards for ATM
networks and facilitating the market adoption of the
ATM technology. Although the two organizations frequently use different terminology to describe the ATM
systems, they present the same concepts of ATM.

ATM Transport and Switching

There are two layers relate to ATM functions and transport, that is, an ATM layer that handles packet transfer
and switching capabilities, and an ATM adaptation layer
(AAL) that handles specic services and mapping to ATM
transport. The ATM layer denes the transmission of data
in the format of cells and also the use of logical connections. The ATM layer is further divided into two switching
levels supported in the network.

Virtual channel (VC): A VC is a generic term representing the unidirectional transport of ATM cells. The cells
carried over a specic VC are identied by a Virtual
channel identier (VCI).
Virtual path (VP): A VP is used to describe a bundle of
VCs. The VCs associated with a VP are transported over
a transmission path within the network as a group. A
VP is identied by a virtual path identier (VPI).

The VPI and VCI values are carried in the header of an

ATM cell, and are used for routing and switching the cell
across the ATM network.
The ATM transport creates the need to dene an adaptation layer to support specic services and map other
transport protocols to ATM. The AAL maps higher-layer
data to ATM cells and retrieve data from ATM cells for delivery to higher layers. The general services provided by
AAL are: transmission error handling, segmentation and
reassembly, ow control and timing control, handling of
lost and misinserted cells. The AAL layer is further divided into two logical sub-layers.

Convergence sublayer (CS): The CS provides the functions needed to support specic services and applications using the ATM transport. The CS is service and
application dependant. Each user attaches to AAL at a
service access point (SAP). The SAP is simply the address of the user application.
Segmentation and reassembly sublayer (SAR): The SAR
sublayer provides the functions of generating cells with
the data received from CS and retrieving the data from
the cells for delivery to CS.

There are ve different protocol types dened for the class

of services supported by ATM, that is, AAL Type 1, AAL
Type 2, AAL Type 3//4, and AAL Type 5. Each protocol
type supports specic class of service. For example, type 1
is used to support constant bit rate (CBR) service. Type 2

MAIN TECHNIQUES IN PACKET SWITCHING

143

is used to support variable bit rate (VBR) service. For

detailed descriptions of each protocol type and packet
format, the readers can refer to the chapter on ATM.

less central management. However, because of the automatic recovery, network problems can go undiagnosed
and uncorrected for long periods of time.

ATM Switching Concept

TCP

As described earlier, the ATM layer consists of VC and

VP sub-layers that form the basis of switching in ATM
networks. There are correspondingly two levels of
ATM connection:

Virtual channel connection (VCC): A VCC extends between points where adaptation layer functionality is
performed. The basic function of the adaptation layer
is to format data for transport over an ATM connection
on the sending end and extract data at the receiving
end. These points are VC connection end points.
Virtual path connection (VPC): A VPC extends from the
point at which VCs are assigned with VCI values and
associated with a VP, to the point where VCs are removed from the VP or have their VCI values modied.
These end points are referred to as the VP connection
end points.

VC and VP connections are established by the permanent VC (PVC) by a network operator manually, or the
switched VC (SVC), established on demand by signaling
procedures between the connection end points.
ATM provides a highly complex technology, with features intended for applications ranging from global telecommunication networks to private local area computer
networks. ATM has been a partial success as a technology,
with widespread deployment, but generally only used as
a transport for IP trafc. Its goal of providing a single integrated technology for LANs, public networks, and user
services has not been achieved.

TCP/IP
The Internet protocol suite is the set of communications
protocols that implement the protocol stack on which the
Internet and most commercial networks run. The TCP/IP
protocol suite has the two most important protocols: the
transmission control protocol (TCP) and the Internet
protocol (IP).
TCP and IP were initially developed by a research
project for the Department of Defense (DOD). The goal
was to connect a number of different networks from different vendors into a network of networks (the so-called
Internet). The Internet protocol suite includes not only
lower-level specications (such as TCP and IP), but also
specications for common applications such as electronic
mail, terminal emulation, and le transfer. Several computers in a small department can use TCP/IP (along with
other protocols) on a single LAN. The IP component provides routing from the department to the enterprise network, then to regional networks, and nally to the global
Internet. A communication network needs to sustain damage on a battleeld. Therefore, the DOD designed TCP/IP
a robust protocol suite that has the capability of automatically recovery from any node or phone line failure. This
design allows the construction of very large networks with

TCP is a connection-oriented transport protocol that

sends data as an unstructured stream of bytes. IETF
RFC793 denes the transmission control protocol (TCP).
TCP provides a reliable stream delivery and virtual
connection service to applications via the use of sequence
numbers and acknowledgment messages. TCP can provide
a sending node with delivery information about packets
transmitted to a destination node. A three way handshake between the source and destination node in TCP
sets up the protocol states properly. The retransmission
protocol ensure that the data be delivered successfully to
the destination. If data has been lost in transit from source
to destination, TCP will retransmit the data until either
a timeout condition is reached or successful delivery is
achieved. TCP has the capability of detecting duplicate
messages and discards them appropriately. TCP has a
window-based ow control mechanism built in to regulate the data ow from source to destination. If the sending node is transmitting too fast for the receiving node,
the ow control mechanism will take effect to slow down
the data transfer. In addition to ow control, TCP also has
a window-based congestion control mechanism built in
to achieve congestion avoidance. When TCP detects any
packet loss, the transmission window will be reduced to
relieve the congestion along the path. Both ow control
and congestion control make TCP very robust in different
network environments.

IP
IP is the primary layer 3 protocol in the Internet suite.
The main function of IP layer is to route packets in different network segments. In addition, IP provides fragmentation and reassembly of datagrams (that is, information
units) for transmission over networks with different maximum transmission unit (MTU) sizes. IP represents the
heart of the Internet protocol suite.

IP Addressing
IP address is a globally unique, 32-bit number assigned
by the network information center and network administrator. Globally unique addresses permit IP networks
anywhere in the world to communicate with each other.
By convention, each byte in a 4-byte IP address is expressed as a decimal number (0 to 255) and separated
with a period. For example, the IP address of my machine
is 192.168.1.36.
An IP address is divided into two parts. The rst part
designates the network address; and the second part designates the host address. IP addressing supports three
different network classes. Class A networks allocate 8 bits
for the network address eld and are intended mainly for
use with a few very large networks. Class B networks allocate 16 bits and are intended for use with large networks.
Class C networks allocate 24 bits for the network address
eld and are intended for use with small networks. Class
C networks only provide 8 bits for the host eld. Therefore

144

PACKET SWITCHING

universities, and many other organizations around the

world. Routing in IP networks is organized as a hierarchy
structure. Some routers are used to move information
through one particular group of networks under the same
administrative authority and control. Such an entity is
called an autonomous system. Routers used for information exchange within autonomous systems are called interior routers. They use a variety of interior gateway protocols
(IGPs) to accomplish the task. Routers that move information between autonomous systems are called exterior
routers. They use the exterior gateway protocol (EGP) or
border gateway protocol (BGP). More details on hierarchical routings are described in other chapters.

Class A 0
Network

Host

Class B 10
Network

Host

Class C 110

Network

Host

Figure 10: IP addresses for class A, B, C networks

the number of hosts per class C network may be a limiting factor. In all three cases, the left most bit(s) indicate
the network class. Figure 10 shows the address formats
for class A, B, and C IP networks.
It is convenient for most class A and class B networks
to be internally managed as a much smaller and simpler
version of the large network organizations. The two or
three bytes available for host address are often divided
into a subnet number and a workstation ID. Subnets provide extra exibility for the network administrator. The
administrator can subdivide the network into small units.
This is done by borrowing bits from the host portion of
the address and using them as a subnet eld, as depicted
in Figure 11.
The number of bits that can be borrowed for the subnet address varies. To specify how many bits are used
and where they are located in the host eld, IP provides
subnet masks. Subnet masks use the same format and
representation technique as IP addresses. Subnet masks
have ones in all bits except those that specify the host
eld. For example, the subnet mask that species 8 bits
of sub-netting for class A address 192.0.0.0 is 255.255.0.0.
The subnet mask that species 16 bits of sub-netting for
class A address 192.0.0.0 is 255.255.255.0. Subnet masks
can be passed through a network on demand so that new
nodes can learn how many bits of sub-netting are being
used on the network.

IP Routing
An internet is a group of interconnected networks.
The Internet is the collection of networks that permits
communication between most research institutions,

Class B without Subnet

Packet-switching networks have experienced tremendous

growth and development in recent years. IP network has
become the dominating networking technology. Much
research and development has been conducted in packetswitching networks. Particularly, advances in IP network
routing, QoS managements, active queue management
and congestion control, network trafc management, etc.
have been made to design an efcient network supporting various applications and services.
In addition to layer 3 (such as IP) network development, the evolution in LAN has also gone through rapid
changes. The most important LAN technologies are the
fast Ethernet and Gigabit Ethernet, which are the extensions of the classical Ethernet with carrier sense multiple access with collision detection (CSMA/CD) to higher
speeds.
Another important packet-switching technology is
MPLS, that is, multiprotocol label switching. MPLS is dened by IETF as a base technology for using label switching and for implementation of label-switched paths
over various link level technologies, such as frame relay,
SONET, ATM, and Ethernet protocols, and so on. MPLS
speeds up the trafc ow transmission by setting up a specic path for a given sequence of packets and saving the
time needed for a router to route the packet. MPLS allows packets to be forwarded at the layer 2 (switching)
level rather than at the layer 3 (routing) level. In addition
to speeding up the network trafc, MPLS makes it easy to
manage a network for quality of service (QoS). As a result of these reasons, MPLS technique has been rapidly
adopted in todays networks carrying mixed trafc.
More detailed descriptions on Ethernet LAN, MPLS,
and other advanced technologies are provided in other
chapters.

GLOSSARY

10
Network

Class B with Subnet

Other Advanced Packet-Switching Networks

Host

10
Network

Subnet Host

Figure 11: IP subnet addresses

ATM: asynchronous transmission mode. It is an advanced fast packet-switching technique. It provides

quality of service for different applications.
Circuit switching: A switching technology used in conventional telephone networks. A dedicated circuit or
connect is pre-allocated for an entire call.
Frame relay: An enhancement of X.25 for packet
switching. It switches packets fast via eliminating the
error checking procedures at the network nodes.

REFERENCES

IP: Internet protocol.

ITU-T: International Telecommunication Union Telecommunication Sector. It is an international standards organization that provides recommendations in
telecommunication technologies.
Packet switching: A switching technology used in modern data communication networks. Packets are individually allocated bandwidth dynamically and shared
the transmission bandwidth with other users.
TCP: Transport control protocol.
X.25: The rst international standards on packet
switching. It denes the protocol interfaces between
user terminals and the networks to facilitate network
interconnection.

CROSS REFERENCES
See ATM (Asynchronous Transfer Mode); Circuit Switching; Frame Relay; Message Switching; TCP/IP Suite.

REFERENCES
ANSI T1-618. 1991. Core aspects of frame protocol for
use with frame relay bearer service. Integrated Services Digital Network (ISDN).
Baran, P. 1964. On distributed communications: Introduction to distributed communications network.
Memorandum RM-3420-PR. RAND Corporation.
http://www.rand.org/publications/RM/baran.list.html.
Baran, P. 1964. On distributed communications networks,
IEEE Transactions on Communications, 12(1), 19.

145

Clark, M. P. 1996. ATM networks and principles. New York:

Wiley.
Clark, M. P. 1998. Networks and telecommunications,
design and operations, 2nd edition. New York: Wiley.
http://www.atmforum.com.
Cypser, R. J. 1978. Communication architecture for distributed systems. Reading, MA: Addison-Wesley.
IETF. 1981. Internet protocol (IP). RFC791. http://www.
ietf.org.
IETF. 1981. Transmission control protocol (TCP). RFC
793. http://www.ietf.org.
Kleinrock, L. 1961. Information ow in large communication nets. RLE Quarterly Progress Report. July.
Kleinrock, L. 1964. Communication nets: Stochastic message ow and delay. New York: Mcgraw-Hill.
Kleinrock, L. and Opderbeck 1975. Throughput in the
ARPANETProtocols and measurement. Proceedings
of 4th Data Communications Symposium. Quebec City.
Canada. pp. 61 to 611, October.
Nakamura, R., F. Ishino, and M. Sasakoka. 1976. Some
design aspects of a public packet switched network.
Proceedings of International Conference on Computers
and Communications. Toronto, Canada. pp. 31722.
Roberts, L., and M. Merrill. 1966. Toward a cooperative network of time-shared computers. Fall AFIPS
Conference, October.
Roberts, L. G. 1974. Data by the packet. IEEE Spectrum.
11(2), February.
Roberts, L. 1978. The evolution of packet switching. Proceedings of the IEEE. 66(1), November.
Tanenbaum, A. S. 1981. Computer networks. Englewood
Cliffs, NJ: Prentice-Hall.