PACKET SWITCHING

PACKET SWITCHING

Around 1970, research began on a new form of architecture for long-distance

digital data communications: packet switching. Although the technology of

packet switching has evolved substantially since that time, it is remarkable

that the basic technology of packet switching is fundamentally the same today

as it was in the early-1970s networks, and (2) packet switching remains one of the

few effective technologies for long-distance data communications.

This lesson provides an overview of packet-switching technology. We will

see that many of the advantages of packet switching (flexibility, resource sharing,

robustness, responsiveness) come with a cost. The packet-switching network is a

distributed collection of packet-switching nodes. Ideally, all packet-switching nodes

would always know the state of the entire network. Unfortunately, because the

nodes are distributed, there is always a time delay between a change in status in one

portion of the network and the knowledge of that change elsewhere. Furthermore,

there is overhead involved in communicating status information. As a result, a

packet-switching network can never perform "perfectly," and so elaborate algorithms

are used to cope with the time delay and overhead penalties of network

operation.

The lesson begins with an introduction to packet-switching network principles.

Next, we look at the internal operation of these networks, introducing the concepts

of virtual circuits and datagrams. Following this, the key technologies of

routing and congestion control are examined. The lesson concludes with an introduction

to X.25, which is the standard interface between an end system and a

packet-switching network.

Packet Switching Principles

The long-haul circuit-switching telecommunications network was orginally designed

to handle voice traffic, and the majority of traffic on these networks continues

to be voice. A key characteristic of circuit-switching networks is that

resources within the network are dedicated to a particular call. For voice connections,

the resulting circuit will enjoy a high percentage of utilization because, most

of the time, one party or the other is talking. However, as the circuit-switching network

began to be used increasingly for data connections, two shortcomings became

apparent:

In a typical userlhost data connection (e.g., personal computer user logged on

to a database server), much of the time the line is idle. Thus, with data connections,

a circuit-switching approach is inefficient.

In a circuit-switching network, the connection provides for transmission

at constant data rate. Thus, each of the two devices that are connected

must transmit and receive at the same data rate as the other; this limits the

utility of the network in interconnecting a variety of host computers and

terminals.

To understand how packet switching addresses these problems, let us briefly

summarize packet-switching operation. Data are transmitted in short packets. A

typical upper bound on packet length is 1000 octets (bytes). If a source has a longer

message to send, the message is broken up into a series of packets (Figure 9.1). Each

packet contains a portion (or all for a short message) of the user's data plus some

control information. The control information, at a minimum, includes the information

that the network requires in order to be able to route the packet through the

network and deliver it to the intended destination. At each node en route, the

packet is received, stored briefly, and passed on to the next node.

Let us return to Figure 8.1, but now assume that it depicts a simple packetswitching

network. Consider a packet to be sent from station A to station E. The

packet will include control information that indicates that the intended destination

is E. The packet is sent from A to node 4. Node 4 stores the packet, determines the

next leg of the route (say 5), and queues the packet to go out on that link (the 4-5

link). When the link is available, the packet is transmitted to node 5, which will forward

the packet to node 6, and finally to E. This approach has a number of advantages

over circuit switching:

* Line efficiency is greater, as a single node-to-node link can be dynamically

shared by many packets over time. The packets are queued up and transmitted

as rapidly as possible over the link. By contrast, with circuit switching,

time on a node-to-node link is preallocated using synchronous time-division

multiplexing. Much of the time, such a link may be idle because a portion of

its time is dedicated to a connection which is idle.

A packet-switching network can perform data-rate conversion. Two stations

of different data rates can exchange packets because each connects to its node

at its proper data rate.

When traffic becomes heavy on a circuit-switching network, some calls are

blocked; that is, the network refuses to accept additional connection requests

until the load on the network decreases. On a packet-switching network,

packets are still accepted, but delivery delay increases.

* Priorities can be used. Thus, if a node has a number of packets queued for

transmission, it can transmit the higher-priority packets first. These packets

will therefore experience less delay than lower-priority packets.

Switching Technique

A station has a message to send through a packet-switching network that is of

length greater than the maximum packet size. It therefore breaks the message up

into packets and sends these packets, one at a time, to the network. A question

arises as to how the network will handle this stream of packets as it attempts to

route them through the network and deliver them to the intended destination; there

are two approaches that are used in contemporary networks: datagram and virtual

circuit.

In the datagram approach, each packet is treated independently, with no reference

to packets that have gone before. Let us consider the implication of this

approach. Suppose that station A in Figure 8.1 has a three-packet message to send

to E. It transmits the packets, 1-2-3, to node 4. On each packet, node 4 must make

a routing decision. Packet 1 arrives for delivery to E. Node 4 could plausibly forward

this packet to either node 5 or node 7 as the next step in the route. In this case,

node 4 determines that its queue of packets for node 5 is shorter than for node 7, so

it queues the packet for node 5. Ditto for packet 2. But for packet 3, node 4 finds

that its queue for node 7 is now shorter and so queues packet 3 for that node. So the

packets, each with the same destination address, do not all follow the same route.

As a result, it is possible that packet 3 will beat packet 2 to node 6. Thus, it is also

possible that the packets will be delivered to E in a different sequence from the one

in which they were sent. It is up to E to figure out how to reorder them. Also, it is

possible for a packet to be destroyed in the network. For example, if a packetswitching

node crashes momentarily, all of its queued packets may be lost. If this

were to happen to one of the packets in our example, node 6 has no way of knowing

that one of the packets in the sequence of packets has been lost. Again, it is up

to E to detect the loss of a packet and figure out how to recover it. In this technique,

each packet, treated independently, is referred to as a datagram.

In the virtual-circuit approach, a preplanned route is established before any

packets are sent. For example, suppose that A has one or more messages to send to

E. It first sends a special control packet, referred to as a Call-Request packet, to 4,

requesting a logical connection to E. Node 4 decides to route the request and all

subsequent packets to 5, which decides to route the request and all subsequent

packets to 6, which finally delivers the Call-Request packet to E. If E is prepared to

accept the connection, it sends a Call-Accept packet to 6. This packet is passed back

through nodes 5 and 4 to A. Stations A and E may now exchange data over the

route that has been established. Because the route is fixed for the duration of the

logical connection, it is somewhat similar to a circuit in a circuit-switching network,

and is referred to as a virtual circuit. Each packet now contains a virtual-circuit

identifier as well as data. Each node on the preestablished route knows where to

direct such packets; no routing decisions are required. Thus, every data packet from

A intended for E traverses nodes 4,5, and 6; every data packet from E intended for

A traverses nodes 6, 5, and 4. Eventually, one of the stations terminates the connection

with a Clear-Request packet. At any time, each station can have more than

one virtual circuit to any other station and can have virtual circuits to more than one

station.

So, the main characteristic of the virtual-circuit technique is that a route

between stations is set up prior to data transfer. Note that this does not mean that

this is a dedicated path, as in circuit switching. A packet is still buffered at each

node, and queued for output over a line. The difference from the datagram

approach is that, with virtual circuits, the node need not make a routing decision for

each packet; it is made only once for all packets using that virtual circuit.

If two stations wish to exchange data over an extended period of time, there

are certain advantages to virtual circuits. First, the network may provide services

related to the virtual circuit, including sequencing and error control. Sequencing

refers to the fact that, because all packets follow the same route, they arrive in the

original order. Error control is a service that assures not only that packets arrive in

proper sequence, but that all packets arrive correctly. For example, if a packet in a

sequence from node 4 to node 6 fails to arrive at node 6, or arrives with an error,

node 6 can request a retransmission of that packet from node 4. Another advantage

is that packets should transit the network more rapidly with a virtual circuit; it is not

necessary to make a routing decision for each packet at each node.

One advantage of the datagram approach is that the call setup phase is

avoided. Thus, if a station wishes to send only one or a few packets, datagram delivery

will be quicker. Another advantage of the datagram service is that, because it is

more primitive, it is more flexible. For example, if congestion develops in one part

of the network, incoming datagrams can be routed away from the congestion. With

the use of virtual circuits, packets follow a predefined route, and it is thus more difficult

for the network to adapt to congestion. A third advantage is that datagram

delivery is inherently more reliable. With the use of virtual circuits, if a node fails,

all virtual circuits that pass through that node are lost. With datagram delivery, if a

node fails, subsequent packets may find an alternate route that bypasses that node.

Most currently available packet-switching networks make use of virtual circuits

for their internal operation. To some degree, this reflects a historical motivation

to provide a network that presents a service as reliable (in terms of sequencing)

as a circuit-switching network. There are, however, several providers of private

packet-switching networks that make use of datagram operation. From the user's

point of view, there should be very little difference in the external behavior based

on the use of datagrams or virtual circuits. If a manager is faced with a choice, other

factors such as cost and performance should probably take precedence over

whether the internal network operation is datagram or virtual-circuit. Finally, it

should be noted that a datagram-style of operation is common in internetworks

(discussed in Part IV).

Packet Size

One important design issue is the packet size to be used in the network. There is a

significant relationship between packet size and transmission time, as illustrated in

beginning of each packet and is referred to as a header. If the entire message is sent

as a single packet of 33 octets (3 octets of header plus 30 octets of data), then the

packet is first transmitted from station X to node a (Figure 9.2a). When the entire

packet is received, it can then be transmitted from a to b. When the entire packet is

received at node b, it is then transferred to station Y. The total transmission time at

the nodes is 99 octet-times (33 octets X 3 packet transmissions).

Suppose now that we break up the message into two packets, each containing

15 octets of the message and, of course, 3 octets each of header or control information.

In this case, node a can begin transmitting the first packet as soon as it has

arrived from X, without waiting for the second packet. Because of this overlap in

transmission, the total transmission time drops to 72 octet-times. By breaking the

message up into 5 packets, each intermediate node can begin transmission even

sooner and the savings in time is greater, with a total of 63 octet-times. However,

this process of using more and smaller packets eventually results in increased,

rather than reduced, delay as illustrated in Figure 9.2d; this is because each packet

contains a fixed amount of header, and more packets means more of these headers.

Furthermore, the example does not show the processing and queuing delays at each

node. These delays are also greater when more packets are handled for a single

message. However, we will see in Lesson 11 that an extremely small packet size

(53 octets) can result in an efficient network design.

Comparison of Circuit Switching and Packet Switching

Having looked at the internal operation of packet switching, we can now return to

a comparison of this technique with circuit switching. We first look at the important

issue of performance, and then examine other characteristics.

Performance

A simple comparison of circuit switching and the two forms of packet switching are

provided in Figure 9.3. The figure depicts the transmission of a message across four

nodes. from a source station attached to node 1 to a destination station attached to

node 4. In this figure, we are concerned with three types of delay:

Propagation delay. The time it takes a signal to propagate from one node to

the next. This time is generally negligible. The speed of electromagnetic signals

through a wire medium, for example, is typically 2 X l0^8 mls.

@ Transmission time. The time it takes for a transmitter to send out a block of

data. For example, it takes 1 s to transmit a 10,000-bit block of data onto a

10-kbps line.

Node delay. The time it takes for a node to perform the necessary processing

as it switches data.

For circuit switching, there is a certain amount of delay before the message

can be sent. First, a call request signal is sent through the network in order to set up

a connection to the destination. If the destination station is not busy, a call-accepted

signal returns. Note that a processing delay is incurred at each node during the call

request; this time is spent at each node setting up the route of the connection. On

the return, this processing is not needed because the connection is already set up;

once it is set up, the message is sent as a single block, with no noticeable delay at

the switching nodes.

Virtual-circuit packet switching appears quite similar to circuit switching. A

virtual circuit is requested using a call-request packet, which incurs a delay at each

node. The virtual circuit is accepted with a call-accept packet. In contrast to the

circuit-switching case, the call acceptance also experiences node delays, even

though the virtual circuit route is now established the reason is that this packet is

queued at each node and must wait its turn for retransmission. Once the virtual circuit

is established, the message is transmitted in packets. It should be clear that this

phase of the operation can be no faster than circuit switching, for comparable networks;

this is because circuit switching is an essentially transparent process, providing

a constant data rate across the network. Packet switching involves some delay

at each node in the path; worse, this delay is variable and will increase with

increased load.

Datagram packet switching does not require a call setup. Thus, for short messages,

it will be faster than virtual-circuit packet switching and perhaps circuit

switching. However, because each individual datagram is routed independently, the

processing for each datagram at each node may be longer than for virtual-circuit

packets. Thus, for long messages, the virtual-circuit technique may be superior.

Figure 9.3 is intended only to suggest what the relative performance of the

techniques might be; however, actual performance depends on a host of factors,

including the size of the network, its topology, the pattern of load, and the characteristics

of typical exchanges.

Other Characteristics

Besides performance, there are a number of other characteristics that may be considered

in comparing the techniques we have been discussing. Table 9.1 summarizes

the most important of these. Most of these characteristics have already been discussed.

A few additional comments follow.

As was mentioned, circuit switching is essentially a transparent service. Once

a connection is established, a constant data rate is provided to the connected stations;

this is not the case with packet switching, which typically introduces variable

delay, so that data arrive in a choppy manner. Indeed, with datagram packet switching,

data may arrive in a different order than they were transmitted.

An additional consequence of transparency is that there is no overhead

required to accommodate circuit switching. Once a connection is established, the

analog or digital data are passed through, as is, from source to destination. For

packet switching, analog data must be converted to digital before transmission; in

addition, each packet includes overhead bits, such as the destination address.

With connectionless service, the network only agrees to handle packets independently,

and may not deliver them in order or reliably. This type of service is

sometimes known as an external datagram service; again, this concept is distinct

from that of internal datagram operation. Internally, the network may actually construct

a fixed route between endpoints (virtual circuit), or it may not (datagram).

These internal and external design decisions need not coincide:

External virtual circuit, internal virtual circuit. When the user requests a virtual

circuit, a dedicated route through the network is constructed. All packets

follow that same route.

External virtual circuit, internal datagram. The network handles each packet

separately. Thus, different packets for the same external virtual circuit may

take different routes. However, the network buffers packets at the destination

node, if necessary, so that they are delivered to the destination station in the

proper order.

External datagram, internal datagram. Each packet is treated independently

from both the user's and the network's point of view.

External datagram, internal virtual circuit. The external user does not see any

connections, as it simply sends packets one at a time. The network, however,

sets up a logical connection between stations for packet delivery and may

leave such connections in place for an extended period, so as to satisfy anticipated

future needs.

The question arises as to the choice of virtual circuits or datagrams, both internally

and externally. This will depend on the specific design objectives for the communication

network and the cost factors that prevail.

We have already made some comments concerning the relative merits of

internal datagram versus virtual-circuit operation. With respect to external service,

we can make the following observations.

The datagram service, coupled with internal datagram operation, allows for

efficient use of the network; no call setup and no need to hold up packets

while a packet in error is retransmitted. This latter feature is desirable in some

real-time applications.

The virtual-circuit service can provide end-to-end sequencing and error control;

this service is attractive for supporting connection-oriented applications,

such as file transfer and remote-terminal access.

In practice, the virtual-circuit service is much more common than the datagram

service. The reliability and convenience of a connection-oriented service is

seen as more attractive than the benefits of the datagram service.