Packet Switching
Protocols and Computer Networks Course
at
This page was created by:
Shiri Chechik
Adi Gati
Circuit Switching vs. Packet Switching
Introduction
What is packet switching?
Packet switching refers to protocols in which messages are broken up
into small packets before they are sent. Each packet is transmitted
individually across the net. The packets may even follow different routes to the
destination, depends on the type of packet switching. Thus, each packet has
header information in which enable to route the packet to its destination. At
the destination the packets are reassembled into the original message.
To prevent unpredictably long delays and ensure that the network has a
reliably fast transit time, a maximum length is allowed for each packet. It is
for this reason that a message submitted to the transport
layer may first have to be divided by the transport
protocol entity into a number of smaller packet units before transmission. In
turn, they will be reassembled into a single message at the destination.
Circuit Switching vs. Packet Switching
In Circuit Switching networks, when establishing a call a set of
resources is allocated for this call. These resources are dedicated for this
call, and can’t be used by any of the other calls. Circuit Switching is ideal
when data must be transmitted quickly, must arrive in sequencing order and at a
constant arrival rate. There for when transmitting real time data, such as
audio and video, Circuit Switching networks will be used.
Packet switching main difference from Circuit Switching is that that the
communication lines are not dedicated to passing messages from the source to
the destination. In Packet Switching, different messages can use the same
network resources within the same time period. Since network resources are not
dedicated to a certain session the protocol avoid from waste of resources when
no data is transmitted in the session. Packet Switching is more efficient and
robust for data that is burst in its nature, and can withstand delays in
transmission, such as e-mail messages, and Web pages.
Two kinds of Packet Switching
There are two basic types of Packet Switching.
1.
Virtual Circuit Packet Switching Networks
An initial setup phase is used to set up a route between the
intermediate nodes for all the packets passed during the session between the
two end nodes. In each intermediate node, an entry is registered in a table to
indicate the route for the connection that has been set up. The packets passed
through this route, have short headers, containing only a virtual circuit
identifier (VCI). Each intermediate node passes the packets according to the
information that was stored in its table, in the setup phase and according to
the packets header content.
In this way, packets arrive at the destination in the correct sequence.
This approach is slower than Circuit Switching, since different virtual
circuits may compete over the same resources. As in Circuit Switching, if an
intermediate node fails, all virtual circuits that pass through it are lost.
The most common forms of Virtual Circuit networks are ATM and Frame
Relay, which are commonly used for public data networks (PDN).
2.
Datagram Packet Switching Networks
This approach uses a different, more dynamic scheme, to determine the
route through the network links. Each packet is treated as an independent
entity, and its header contains full information about the destination of the
packet. The intermediate nodes examine the header of the packet, and decide the
next hop of this packet. In the decision two factors are taken into account:
The shortest way to pass the packet to its destination - protocols such
as RIP/OSPF is used to determine the shortest path to the destination.
Finding a free node to pass the packet to - in this way, bottle necks
are eliminated, since packets can reach the destination in alternate routes.
Thus, in this method, the packets don't follow a pre-established route, and the
intermediate nodes (the routers) don't have pre-defined knowledge of the routes
that the packets should be passed through.
Packets can follow different routes to the destination. Due to the
nature of this method, the packets can reach the destination in a different
order than they were sent, thus they must be sorted at the destination to form
the original message. This approach is time consuming since every router has to
decide where to send each packet.
The main implementation of Datagram Switching network is the Internet
which uses the IP network protocol.
Switch functionality
The world of
broadband data communications is based on interconnecting small networks to
larger ones. At the lowest level we always find fast hardware-based switches,
capable of delivering information from the various interconnected networks to
their correct destinations. Because of the high data rates involved, routing
decision-making logic must be implemented entirely in hardware; software
processing would be grossly incapable of keeping pace with the high rate of
packet arrivals. The implementation normally requires custom-design VLSI
circuitry to maintain physical compactness. In this discussion, we will assume
that the arriving packets are of fixed length. Such fixed-length packets are
also referred to as cells.
Two primary functions are supported by the N-input,
N-output switch (subsequently referred to as an N×N switch):
1. Routing of each cell to its correct
destination port.
2. Resolving the contention which arises when several simultaneously
arriving cells are headed to a common output port. This is solved by means of
store-and-forward buffering: arriving packets which cannot be immediately
delivered are stored in a buffer (or buffers) within the switch, their delivery
being deferred according to a buffer servicing discipline.
Basic switching element
The routing
function implemented for a 2X2 switch, often referred to as a β-element.
In a larger switch the routing function is typically synthesized by a network
of β-elements and buffers.
The structure of a
β-element is:
It consists of decision logic which operates on the cell headers, a
latch to hold the result of that decision for the duration of the cell, delay
lines to synchronize the cell contents with the decision, and the 2x2
cross-connect. The cross-connect is a dual multiplexer which can be set in
either a "bar" or a "cross" state (each input
can be routed to either output, with the other input correspondingly routed to the
other output). The complexity of a β-element depends entirely on the
requirements from its decision-making circuitry.
Switch Architectures
The switch
architectures presented below attempt to trade between link utilization, packet
loss rate, and design complexity.
1. The Banyan Switch
The Banyan switch is a multistage self-routing
architecture which is not rearrangeable and not non-blocking .An NxN Banyan switch
uses (N/2) log N elements. The buffers must lie inside the switch to achieve a
reasonably low packet loss rate.
The structure of an
8x8 Banyan switch is
We see that the
β-elements are arranged in three columns of four elements each. The inputs
to the switch are the inputs to the elements in the first column, and the
outputs of the last column are the outputs from the switch. In each
β-element, one output is connected to the input of the element just
horizontally on its right, and the other goes to an element whose line number,
represented in binary, differs in precisely the j's bit, where j is the column
number of the element (counting from 0). For example, the outputs of element
(2,1) (red in the diagram) are connected to the inputs of elements (2,2)
(horizontal connection) and (0,2) (diagonal connection), as the numbers 2 and 0
differ in bit #1 of their binary representation. This simple rule also tells
how to construct a path from any input to any output: in each column j, an appropriate
β-element should be set in the "bar" state if the j's bits of
the input and the output numbers equal, and in the "cross" state if
those bits differ. The path shown in red in the diagram illustrates how to
connect input 7 to output 0. Since all the bits in the binary representations
of the input and the output differ, all elements along the path are set to
"cross". Note that every such path is unique. Obviously, several
paths cannot be routed concurrently unless they happen to require the same
states of the β-elements. Thus, in our case, once input 7 is connected to
output 0, input 6 cannot be connected to outputs 2, 4, and 6, because any of
these connections would require the element in the first column to be set to
"bar".
Several remedies can be employed to attempt resolving
this type of routing conflict:
Provide
buffers within the β-elements, so that cells that cannot be immediately
delivered are stored and their routing deferred according to some contention
resolution policy.
Run
the internal links at a rate that is a multiple of the cell arrival rate,
sequentially establishing several paths within the duration of one cell. To
provide an insight to how good these techniques can be in reducing packet loss
rate, it suffices to quote the results of a computer simulation for a large
(1024x1024) Banyan
switch run at full input load. With the internal links running at twice the
cell rate (hence capable of establishing two subsequent paths within one time
slot) and a buffer size of 5 cells in each β-element, as many as 92% of
the input cells were delivered, compared to about 25% for a simple switch
without buffers, and about 75% for a double-rate switch without buffers. Still,
to achieve reasonable packet loss rates (such as one packet per million), the
input load would have to be reduced considerably.
2. The Knockout Switch
The knockout switch is a fully connected architecture which attempts to
combine the implementation simplicity of input queuing
(buffer complexity is linear in the number of ports) with
the throughput performance of output queuing (permitted
input load and saturation throughput both approaching 100%). The knockout
switch architecture achieves this goal by intentionally introducing a new
source of packet loss, known as buffer blocking; in addition to packet loss
mechanisms present in any switch architecture, mainly buffer overflow and
noise-induced random channel errors. The rate of loss from buffer blocking can
be readily controlled and kept low, to reduce significantly the complexity of a
switch based in principle on the output queuing idea.
The knockout
switch architecture is
Each cell arriving
at one of the input ports is placed on a broadcast bus from which each of the
output modules taps the cells intended for itself. It is obvious that multicast
and broadcast cells are readily supported. The output module acts as
statistical multiplexer, deferring cells that cannot be immediately placed onto
the output link because of contention.
The output module
diagram:
Each input to an
output module receives the cells broadcasted on the corresponding input bus.
The job of each packet filter is simply to pass the cell to the concentrator if
the cell is destined for that output, and to mark the cell as inactive
otherwise. Such a filter can be easily implemented by a β-element,
only one input and one output of which is used. The role of the concentrator is
to identify among its inputs those cells that are active and route them to its
leftmost outputs, one cell per output line. Note that the concentrator has only
L<N outputs. Should L+1 or more cells arrive simultaneously, only L of them
will be processed via the concentrator; all others will be lost. This is the
extra packet loss source in the knockout switch. By properly choosing L, the
loss rate induced by the concentrator can be controlled and maintained at a
reasonably low level. Furthermore, the value of L required to maintain a given
loss rate is relatively small, independent of the number of inputs when the
latter is large, and grows only logarithmically in the loss rate. For example,
L = 8 is sufficient to maintain the packet loss rate in the concentrator at one
packet per million, for large N and full input load, and it only grows by one
per every order of magnitude reduced in the loss rate (i.e. L = 11 is enough
for a loss rate of one packet per billion). This effect is the key to
maintaining linear complexity of the knockout switch, as the number of buffers
is proportional to LxN rather than N².
The concentrator
inputs receive cells which have already been passed by the packet filters and
are known to be intended for the switch output port served by the concentrator.
There are four (generally, L) stages in the concentrator shown in the diagram.
Each stage is designed to operate like an elimination tournament. Specifically,
each β-element is programmed to set itself to the "bar" state if
there is an active cell on its left input, and to "cross" otherwise.
Whenever there is only one active cell at the inputs of a β-element, it is
allowed to pass downward. If both cells are active, the right-hand one is
"knocked out" to the next stage and contends there. Each stage
produces one "winner" among the active cells that enter it, and each
subsequent stage receives one less active cell than the previous one.
Therefore, when there are k active cells, they are guaranteed to come out on
the outputs of the first k stages.
If the packet
buffers in the output module diagram were to be loaded directly from the
concentrator outputs, then the leftmost buffers would tend to fill up faster,
and might even overflow despite the presence of empty buffer entries on the
right. The shifter prevents that from happening by spreading each bulk of cells
arriving at its input continuously to the right; in other words, if the last
buffer to receive a packet happened to be m, then the next k cells arriving at
the shifter's input will be directed to buffers m+1, ..., m+k (modulo L).
Physically, the shifter can be implemented with an L׳L Banyan network.
Because of the round-robin nature of the shifter and the fact that the
buffers are filled cyclically, they can also be emptied cyclically. At each
time slot, the output line fetches a cell from a buffer just right (cyclically)
of the buffer last fetched from, beginning with buffer 1. Moreover, if the
output circuitry encounters an empty buffer, the round-robin policy of buffer
filling guarantees that all buffers are empty at that point, and the one just
reached is precisely the next one to be filled again. The output pointer can
then just stops there and wait for that buffer to receive a cell, after which
the circular emptying of buffers can restart from that point.
3. The Tandem Banyan Switch
A block diagram of the Tandem Banyan
The only difference
between the Tandem Banyan switch and the knockout
switch is the replacement of the N input broadcast lines by a
cascade of L Banyans. Consequently, there are only L packet filters per each
output. The jobs of the concentrator, the shifter, and the shared buffers
remain the same as for a knockout switch. In particular, if more than L cells
simultaneously arrive for the same output, all except L of them are lost.
The Tandem Banyan
switch does not use a knockout concentrator to find those inputs intended for a
given output. Instead, it uses a cascade of memory less Banyan routing
networks. The first Banyan does the best it can to route its inputs to its
correct outputs. However, since the path from every input to any output inside
the Banyan is unique, contention may arise if two inputs either request the
same output or need to use the same internal link. In both cases, one of the
cells is routed correctly, while the other one is misrouted and appears on a
wrong line at the output. In order to minimize the damage caused by misrouted
cells, any cell that has been misrouted once (and therefore cannot reach its
correct output within the Banyan) is marked so as not to contend for internal
links in later stages of the Banyan, which can be needed for correctly routed
cells. Every cell that has reached its correct output by the end of the first
Banyan is intercepted by the first packet filter of that output module. Only
the cells misrouted by the first Banyan enter the second one, and so on; each
subsequent Banyan receives only cells misrouted by previous Banyans in the
cascade. Cells still misrouted after L stages are irrecoverably lost.
The Tandem Banyan
architecture cannot support multicasting as easily as the knockout switch does.
The Banyans have to know a single destination for each input cell, and no
packet filter can just intercept a cell appearing on the correct line, because
that cell may have to be read by other outputs' packet filters as well.
Contrary to the
knockout switch, in the Tandem Banyan, even if not more than L cells appear
concurrently for a given output, there is no guarantee that they will all enter
that output's concentrator. As a consequence, the value of L required to
maintain a given packet loss rate resulting from buffer blocking is generally
larger than for the knockout. Moreover, it does not become independent for
large N, as was the case there. Specifically, given an input load of 100% and N
= 1024, L = 15 stages are required as opposed to only L = 8 in the knockout
switch, and it grows further (approximately logarithmically) for larger
switches.
The major advantage of the Tandem Banyan architecture
over the knockout is in the number of β-elements required in its
implementation. In the knockout switch, there are N output modules, each
containing N packet filters and a concentrator whose implementation requires an
order of LN β-elements, for a total of O(LN²) switching elements. In the
Tandem Banyan, an output module contains only L packet filters, and its
concentrator, being of lower dimensions, needs only about L² β-elements,
for a total of O(L²N). As for the Banyan packet routing networks - there are L
of them, each having (N/2) log N switching elements, for a total of O(LN log
N). Since, as previously mentioned, L itself grows approximately as a logarithm
of N, we get the Tandem Banyan switch complexity to be O(LN log N) < O(LN²).
For very large N, the Tandem Banyan switch therefore requires a substantially
smaller amount of β-elements.
4. The Shared Memory Switch
The shared memory switch architecture is
The distinctive
feature of an NxN shared memory switch is its use of a high-speed
internal bus, with a bit rate N times as large as the rate on each individual
input/output line. For a time slot of length F, the internal bus is capable of
transferring a cell in a mini slot of length F/N. All cells received during a
time slot are therefore transferred to the shared memory, albeit with a very
short delay (probably during the very next time slot, if double-buffering
technique is used within the serial-to-parallel converter). Conversion from
serial to parallel is required to maintain acceptable clock rates; the bus
clock rate only needs to be N/W times higher than the incoming bit rate, with W
the bus (and memory) width.
In the shared
memory, the cells intended for each output are kept in separate partitions.
During an output cycle, the cells are discharged to their outputs, again with
only a mini slot of length F/N being required on the output bus to discharge a
single cell. Thus in a full time slot one cell is read from the shared memory
for each output. If the memory partition for an output is empty, the corresponding
mini slot remains unfilled.
It is a matter of
implementation whether the partitions in the shared memory are of rigid or
flexible sizes. Obviously, flexible-size partitions require more sophisticated
hardware to manage, but the cell loss rate performance is improved, because a
memory partition does not suffer from overflow until no free memory remains at
all; outputs idle at a given time can "lend" some memory to other
outputs that happen to be heavily used at the moment.
The design simplicity appeal of the shared memory architecture makes it
popular for small-sized fast switches, particularly for interconnecting a small
number of LANs. However, for even moderately sized switches, the clock rate
required of the internal bus becomes intolerable. As an example, at a cell
arrival rate of 155 Mbit/sec, N = 32 and W = 16, the internal bus has to
operate under a clock rate of 310 MHz.
Some useful definitions
Rearrangeable - a rearrangeable switch can route
any permutation from inputs to outputs.
Non-blocking
- Given any current connections through the switch. Any unused input can be
routed to any unused output.
Port – An outlet on the switch into which a cable
connects.
Input Queuing - Cells arriving on each input line are
placed into buffers, prior to placement on the correct output lines. In any
given time slot, leading cells in all the buffers are sent to their output
lines.
Output Queuing - There are N² buffers, one for each
input-output combination. For every time slot, all cells active during that
time slot enter the queue in the intersection of their input line and output
line. The leading cells in all the buffers with a common output contend for
that output.
Simulation
In this simulation you will see how Packet Switching is executed over a network, and the differences between Virtual Circuit Switching and Datagram Switching. In order to simplify the demonstration and to emphasize the differences between Virtual Circuit and Datagram Switching, some assumptions have been made on the nature of the net:
- Packets can be transmitted over a communication link (edge) in one direction only. The directions are from left to right and from the upper node to the lower one.
- The routes that the packets pass are not chosen according to an algorithm which finds the shortest path between the source and the destination, but each node chooses randomly to which one of its connected nodes to pass the packet. Due to the nature of the net, the packets are ensured to reach the destination.
- Each node can only send one packet during a time interval, and can receive only one as well (It can receive and send simultaneously).
Network Description
The two nodes at the left of the net are the two message sources. From each of these sources, a message is sent to the destination node at the right of the net. These messages are broken into packets which are numbered serially and colored in the same color as their source node. The packets can be sent to the destination via Datagram Switching or Virtual Circuit Switching. The network's edges are colored according to the virtual circuit they are assigned to. Note that the edges which are shared by the two virtual circuits are colored in red.
Operating Instructions
Fill the desired number of packets for each message sent from the two sources. The total number of packets must not exceed 16.
Choose the type of Packet Switching method - Virtual Circuit Switching or Datagram Switching.
Press the Step button for a step by step simulation, or the Start button for a continuous one.
Notice the number of time cycles required by each of the switching methods.
Quiz
Credits
This project is an integration of two older projects:
Packet Switching Simulation written by Gilbert Ohana and Ohad Parush.
Introduction to Packet Switches written by Lavy Libman.
References
Books
A. S. Acampora, "An Introduction to Broadband Networks",
Plenum Press, 1994.
R. Perlman, "Interconnections: Bridges and Routers",
Addison-Wesley, 1992.
P. E. Green, "Network Interconnection and Protocol
Conversion", IEEE Press, 1988.
Data Communications, Computer Networks and OSI / F. Halsall.
Computer Networks and Internets / D.E. Comer.
Resources on the Web
http://www.pbs.org/opb/nerds2.0.1/geek_glossary/packet_switching_flash.html.
http://www.privateline.com/Switching/packet.html.
Publications of Sangoma Technologies Inc.