8.
3 PACKET SWITCHING
In data communications, we need to send messages from one end system to another. If
the message is going to pass through a packet-switched network, it needs to be
divided into packets of fixed or variable size. The size of the packet is determined by
the network and the governing protocol.
In packet switching, there is no resource allocation for a packet. This means that
there is no reserved bandwidth on the links, and there is no scheduled processing time
for each packet. Resources are allocated on demand. The allocation is done on a first-
come, first-served basis. When a switch receives a packet, no matter what the source or
destination is, the packet must wait if there are other packets being processed. As with
other systems in our daily life, this lack of reservation may create delay. For example, if
we do not have a reservation at a restaurant, we might have to wait.
In a packet-switched network, there is no resource reservation;
resources are allocated on demand.
We can have two types of packet-switched networks: datagram networks and virtual-
circuit networks.
8.3.1 Datagram Networks
In a datagram network, each packet is treated independently of all others. Even if a
packet is part of a multipacket transmission, the network treats it as though it existed
alone. Packets in this approach are referred to as datagrams.
Datagram switching is normally done at the network layer. We briefly discuss
datagram networks here as a comparison with circuit-switched and virtual-circuit-
switched networks. In Chapter 18 of this text, we go into greater detail.
Figure 8.7 shows how the datagram approach is used to deliver four packets from
station A to station X. The switches in a datagram network are traditionally referred to
as routers. That is why we use a different symbol for the switches in the figure.
Figure 8.7 A datagram network with four switches (routers)
Datagram network
A 3 1
4 3 2 1
4 1
2 3
1
4 X
2 3 4 1
2
In this example, all four packets (or datagrams) belong to the same message, but
may travel different paths to reach their destination. This is so because the links may be
involved in carrying packets from other sources and do not have the necessary bandwidth
available to carry all the packets from A to X. This approach can cause the datagrams of
a transmission to arrive at their destination out of order with different delays between the
packets. Packets may also be lost or dropped because of a lack of resources. In most
protocols, it is the responsibility of an upper-layer protocol to reorder the datagrams or
ask for lost datagrams before passing them on to the application.
The datagram networks are sometimes referred to as connectionless networks. The
term connectionless here means that the switch (packet switch) does not keep information
about the connection state. There are no setup or teardown phases. Each packet is treated
the same by a switch regardless of its source or destination.
CHAPTER 8 SWITCHING 215
Routing Table
If there are no setup or teardown phases, how are the packets routed to their destinations
in a datagram network? In this type of network, each switch (or packet switch) has a rout-
ing table which is based on the destination address. The routing tables are dynamic and
are updated periodically. The destination addresses and the corresponding forwarding
output ports are recorded in the tables. This is different from the table of a circuit-
switched network (discussed later) in which each entry is created when the setup phase
is completed and deleted when the teardown phase is over. Figure 8.8 shows the routing
table for a switch.
Figure 8.8 Routing table in a datagram network
Destination Output
address port
1232 1
4150 2
…
…
9130 3
1 4
2 3
A switch in a datagram network uses a routing table that is based on the destination
address.
Destination Address
Every packet in a datagram network carries a header that contains, among other infor-
mation, the destination address of the packet. When the switch receives the packet,
this destination address is examined; the routing table is consulted to find the corre-
sponding port through which the packet should be forwarded. This address, unlike the
address in a virtual-circuit network, remains the same during the entire journey of the
packet.
The destination address in the header of a packet in a datagram network
remains the same during the entire journey of the packet.
Efficiency
The efficiency of a datagram network is better than that of a circuit-switched net-
work; resources are allocated only when there are packets to be transferred. If a
source sends a packet and there is a delay of a few minutes before another packet can
be sent, the resources can be reallocated during these minutes for other packets from
other sources.
Delay
There may be greater delay in a datagram network than in a virtual-circuit network.
Although there are no setup and teardown phases, each packet may experience a wait at a
switch before it is forwarded. In addition, since not all packets in a message necessarily
travel through the same switches, the delay is not uniform for the packets of a message.
Figure 8.9 gives an example of delay in a datagram network for one packet.
Figure 8.9 Delay in a datagram network
A B
Transmission
time
Waiting
Total delay
time
Waiting
time
Time Time Time Time
The packet travels through two switches. There are three transmission times (3T ),
three propagation delays (slopes 3τ of the lines), and two waiting times (w1 + w2). We
ignore the processing time in each switch. The total delay is
Total delay 5 3T 1 3τ 1 w1 1 w2