Switching

A switched network consists of a series of interlinked nodes, called switches. Switches are devices
capable of creating temporary connections between two or more devices linked to the switch. In a switched
network, some of these nodes are connected to the end systems (eg: computers or telephones). Others are
used only for routing.

The above figure shows a switched network, where the end systems (communicating devices) are
labeled A, B, C, D, and so on, and the switches are labeled I, II, III, IV, and V. Each switch is connected to
multiple links.
Today's networks can be divided into three broad categories:
 Circuit-switched networks,
 Packet-switched networks, and
 Message-switched networks.
Packet-switched networks can further be divided into two subcategories called virtual-circuit
networks and datagram networks as shown below.

CIRCUIT-SWITCHED NETWORKS
A circuit-switched network consists of a set of switches connected by physical links. A connection
between two stations is a dedicated path made of one or more links. However, each connection uses only
one dedicated channel on each link. Each link is normally divided into n channels by using FDM or TDM.
The following figure shows a trivial (small) circuit-switched network with four switches and four
links. Each link is divided into n (n is 3 in the figure) channels by using FDM or TDM.
The multiplexing symbols have been shown in the figure for the division of the link into channels
even though multiplexing can be included in the switch fabric.
The end systems, such as computers or telephones, are directly connected to a switch. The figure
shows only two end systems for simplicity. When end system A needs to communicate with end system M,
system A needs to request a connection to M that must be accepted by all switches as well as by M itself.

Page 1 of 15
This is called the setup phase (circuit establishment) in which a circuit (channel) is reserved on each link,
and the combination of circuits or channels defines the dedicated path. After the dedicated path made of
connected circuits (channels) is established, data transfer can take place. After all data have been
transferred, the circuits are disconnected.

The following are the highlighted points in circuit-switching:

 Circuit switching takes place at the physical layer.
 Before starting communication, the stations must make a reservation for the resources to be used
during the communication. These resources, such as channels (bandwidth in FDM and time slots in
TDM), switch buffers, switch processing time, and switch input/output ports, must remain dedicated
during the entire duration of data transfer until the disconnect phase.
 Data transferred between the two stations are not packetized. The data are a continuous flow sent by
the source station and received by the destination station, although there may be periods of silence.
 There is no addressing involved during data transfer. The switches route the data based on their
occupied band (FDM) or time slot (TDM). But, there is end-to-end addressing used during the setup.
Three Phases
The actual communication in a circuit-switched network requires three phases: Circuit
establishment, Data transfer, and Circuit disconnect.
Circuit establishment / Setup phase:
Before the two stations can communicate, a dedicated circuit (combination of channels in links)
needs to be established. The end systems are normally connected through dedicated lines to the switches, so
connection setup means creating dedicated channels between the switches. For example, in the above figure,
when system A needs to connect to system M, it sends a setup request that includes the address of system M,
to switch I. Switch I finds a channel between itself and switch IV that can be dedicated for this purpose.
Switch I then sends the request to switch IV, which finds a dedicated channel between itself and switch III.
Switch III informs system M of system A's intention at this time.
In the next step to making a connection, an acknowledgment from system M needs to be sent in the
opposite direction to system A. Only after system A receives this acknowledgment, the connection is
established.
Note that end-to-end addressing is required for creating a connection between the two end systems.
For example, these can be the addresses of the computers assigned by the administrator in a TDM network,
or telephone numbers in an FDM network.
Data transfer phase
Now data can be transmitted from A through the network to M. The data may be analog or digital,
depending on the nature of the network. Generally, the connection is full-duplex.
Circuit disconnect phase
Page 2 of 15
 After some period of data transfer, the connection is terminated, usually by the action of one of
the two stations. Signals must be propagated to nodes I, IV, and III to deallocate the dedicated resources.
Efficiency
Circuit-switched networks are not as efficient as the other two types of networks because resources
are allocated during the entire duration of the connection. These resources are unavailable to other
connections. In a telephone network, people normally terminate the communication when they have finished
their conversation. However, in computer networks, a computer can be connected to another computer even
if there is no activity for a long time. In this case, allowing resources to be dedicated means that other
connections are depressed.
Delay
Although a circuit-switched network normally has low efficiency, the delay in this type of network is
minimal. During data transfer the data are not delayed at each switch and the resources are allocated for the
duration of the connection.
Applications of Circuit-switched Networks
Circuit switching was originally designed and implemented to service analog telephone
subscribers in public telephone network. Now, the network handles substantial data traffic via modem and
is gradually being converted to a digital network. Another well-known application of circuit switching
is the private branch exchange (PBX), used to interconnect telephones within a building or office. A final
common example of the application of circuit switching is the data switch. The data switch is similar to
the PBX but is designed to interconnect digital data-processing devices, such as terminals and computers.
Public telecommunications network
A public telecommunications network can be described using four components:
Subscribers: The telephones or data devices that attach to the network.
Local loop: The link between the subscriber and the network, also referred to as the subscriber loop,
mostly using twisted-pair wire in a distance of few kilometers.
Exchanges: The switching centers in the network. A switching center that directly supports many
thousands of subscribers in a small area is known as an end office. There are many hundreds of end offices
in a particular city or zone. So it is impractical for each end office to have a direct link to each of the other
end offices. Hence intermediate switching nodes are used between end offices.
Trunks: The branches between exchanges. Trunks carry multiple voice frequency circuits using
either FDM or synchronous TDM. Earlier, these were referred to as carrier systems.

Subscribers connect directly to an end office. The end office switches traffic between subscribers
(between a and b in the following figure) and between a subscriber and other exchanges. The other
exchanges are responsible for routing and switching traffic between end offices. In c's end office, a
connection is established between line c and one channel on a TDM trunk to the intermediate switch. In
the intermediate switch, that channel is connected to a channel on a TDM trunk to d's end office. In that
end office, the channel is connected to line d.
Page 3 of 15
  Circuit-switching technology has been widely used for voice traffic as there is no transmission
delay the quality of the received signal is sufficiently high.
 Circuit switching is also used for both LAN and WAN. It is transparent. Once a circuit is
established, it appears as a direct connection to the two attached stations.

SWITCHING CONCEPTS
Digital Switch
The function of the digital switch is to provide a transparent signal path between any pair (dotted
lines) of attached devices. There is a direct connection between them and the connection must allow
full-duplex transmission.
Network Interface
The network-interface element represents the functions and hardware needed to connect digital
devices. Analog telephones can also be attached if the network interface contains the logic for converting
to digital signals.
Control Unit
1. Establish connections
 Generally on demand
 Handle and acknowledge requests
 Determine if destination is free
 Construct path
2. Maintain connection
3. Disconnect

Page 4 of 15
Blocking or Non-blocking circuit-switching device
Blocking
 A network is unable to connect stations because all paths are in use
 A blocking network allows this
 Used on voice systems with short duration calls
Non-blocking
 Permits all stations to connect (in pairs) immediately
 Used for some data connections

Space-division Switching
In space-division switching, the paths in the circuit are separated from one another spatially. This
technology was originally designed for use in analog networks but is used currently in both analog and
digital networks.

A crossbar switch connects n inputs to m outputs in a grid, using electronic micro switches
(transistors) at each cross point. The major limitation of this design is, to connect n inputs to m outputs using
a crossbar switch requires n x m cross points. A crossbar with this number of cross points is impractical and
is also inefficient. But it is non-blocking.
The solution to the limitations of the crossbar switch is the multistage switch, which combines
crossbar switches in several (normally three) stages, as shown in the following figure. The number of
crosspoints is reduced, increasing crossbar utilization. In this example, the total number of crosspoints for
10 stations is reduced from 100 to 48. There is more than one path through the network to connect two
endpoints, increasing reliability. But, a multistage network is more complex and it may be blocking.

Page 5 of 15
Time-division Switching
All modern circuit switches use digital time-division techniques for establishing and maintaining
"circuits" . Time-division switching involves the partitioning of a lower-speed bit stream into slots that
share a higher-speed stream with other bit streams. The individual pieces, or slots, are manipulated by
control logic to route data from input to output.
One of the simplest but most popular techniques, referred to as TDM bus switching. TDM bus
switching is based on the use of synchronous TDM which permits multiple low-speed bit streams to
share a high-speed line. A set of inputs is sampled in turn. The samples are organized serially into slots
(channels) to form a recurring frame of slots, with the number of slots per frame equal to the number of
inputs. A slot may be a bit, a byte, or some longer block. As the source and destination of the data in each
time slot are known, there is no need for address bits in each slot.

The above figure shows a system connecting four input lines to four output lines. Imagine that each
input line wants to send data to an output line according to the following pattern:

The following figure combines a TDM multiplexer, a TDM demultiplexer, and a TDM bus switching
consisting of random access memory (RAM) with several memory locations. The size of each location is the
same as the size of a single time slot. The number of locations is the same as the number of inputs. The
RAM fills up with incoming data from time slots in the order received. Slots are then sent out in an order
based on the decisions of a control unit.

Control of a TDM bus switch

ROUTING IN CIRCUIT-SWITCHED NETWORKS

In a large circuit-switched telephone network , when a call is placed, the network must devise a route
through the network from calling subscriber to called subscriber that passes through some number of
switches and trunks. There are two main requirements for the routing strategy: efficiency and resilience.
First, efficiency is to minimize the amount of equipments (switches and trunks) in the network. Another

Page 6 of 15
requirement is resilience. During the busiest hours, switches and trunks will be temporarily unavailable.
To provide a reasonable level of service under such conditions is resilience.
There is a trade-off between efficiency and resilience that determines the routing strategy.
Traditionally, the switches of a network were organized into a tree structure, or hierarchy. A path was
constructed by starting at the calling subscriber, tracing up the tree to the first common node, and then
tracing down the tree to the called subscriber. This is a static approach. But, this design leads to
oversizing and inefficiency. In terms of resilience, the fixed hierarchical structure with supplemental
trunks may result congestion.
A dynamic routing approach is one in which routing decisions are influenced by current traffic
conditions. Typically, the circuit-switching nodes have a peer relationship with each other rather than a
hierarchical one. All nodes are capable of performing the same functions. In such architecture, routing is
both more complex and more flexible. Two broad classes of dynamic routing algorithms have been
implemented: Alternate routing and Adaptive routing.

Alternate Routing
In alternate-routing scheme, the possible routes to be used between two end offices are
predefined. The originating switch selects the appropriate route for each call. Each switch is given a set of
preplanned routes for each destination, in order of preference. The preferred choice is a direct trunk
connection between two switches. If this trunk is unavailable, then the second choice is to be tried, and so
on. If there is only one routing sequence defined for each source-destination pair, the scheme is known as
a fixed alternate-routing scheme. More commonly, a dynamic alternate-routing scheme is used, in which
a different set of preplanned routes is used for different time periods, to take advantage of the differing
traffic patterns in different times of day. Thus, the routing decision is based both on current and past
traffic patterns.
A simple example is shown below. The originating switch, X, has four possible routes to the
destination switch, Y. The direct route (a) will always be tried first. If this trunk is unavailable, the other
routes will be tried in a particular order, depending on the time period. For example, during weekday
mornings, route b is tried next.

Adaptive Routing
In the adaptive-routing scheme , the switches exchange information to learn the network
conditions and traffic patterns, accordingly select the route. Such schemes require greater management
overhead. However, compared to an alternate-routing scheme, an adaptive scheme has the potential for
more effectively optimizing the use of network resources.
Dynamic traffic management (DTM) is an important example of adaptive-routing scheme.

PACKET SWITCHING
Page 7 of 15
Packet Switching Principles
The circuit-switching network was originally 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 and used efficiently in
voice connections. However, as the circuit-switching network began to be used increasingly for data
connections, two shortcomings became apparent:
1. In a typical user or host data connection, much of the time the line is idle. Thus, with data
connections, a circuit-switching is inefficient.
2. In a circuit-switching network, the connection provides for transmission at constant data rate.
This limits the utility of the network in interconnecting a variety of host computers and
terminals.
In packet-switching, data are transmitted in short packets with typical packet length of 1000 bytes. If a
source has a longer message to send, the message is broken up into a series of packets and each packet
contains a portion of the user's data plus some control information. The control information 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.

Advantages of packet-switching over circuit-switching

• Line efficiency
— Single node to node link can be shared by many packets over time
— Packets queued and transmitted as fast as possible
• Data rate conversion
— Each station connects to the local node at its own speed
— Nodes buffer data if required to equalize rates
• Packets are accepted even when network is busy
— But, delivery may slow down
• Priorities can be used with packets

Switching Technique
A longer message is split in to packets and sends to the network. To route the packets through the
network and deliver them to the intended destination, two approaches that are used: datagram and virtual
circuit.

Page 8 of 15
 In the datagram approach, each packet is treated independently, with no reference to packets that
have gone before. Suppose that station A in the above figure has a three-packet message to send to E. It
transmits the packets, 1-2-3, to node 4. It forwards packet 1 to either node 5 or 7. If it sends to node 7, then
packet 2 will be sent to node 5, as its queue is shorter than node 7. Packet 3 is sent to node 7 as its queue is
now shorter. So the packets, each with the same destination address, do not all follow the same route. So, it
is possible that packet 3 may reach node 6 earlier to packet 2. Thus packets will be delivered to E in
different order. Reordering the packets and recovering the destroyed packets are up to E.
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 Call-Request packet, to 4,
requesting a logical connection to E. Node 4 decides to send the request to 5, which decides to send the
request 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-switching network, and is referred to
as a virtual circuit. Thus, every data packet from A intended for E traverses nodes 4,5, and 6 and every
data packet from E intended for A traverses nodes 6, 5, and 4. Finally, 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.

Virtual Circuits Vs Datagram

• Virtual circuits
— Network can provide sequencing and error control
— Packets are forwarded more quickly
• No routing decisions to make
— Less reliable
• Loss of a node looses all circuits through that node
• Datagram
— No call setup phase
• Better if few packets
— More flexible
• Routing can be used to avoid congested parts of the network
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. In this example, it is assumed that there is a virtual
circuit from station X through nodes a and b to station Y. The message to be sent comprises 30 bytes, and

Page 9 of 15
each packet contains 3 bytes of control information, which is placed at the beginning of each packet
and is referred to as a header.

In the above figure (a), 33 bytes (30+3) are transmitted in 33 x 3 = 99 byte-times. In fig.(b), data is
split in to two 15 bytes packets, hence transmitted time is reduced to 72 and in fig(c) further reduced to 63.
But in fig(d), as there are more headers, transmission time is increased.
Comparison of Circuit Switching and Packet Switching

Page 10 of 15
Routing in Packet Switched Network
• Routing is complex and crucial aspect in packet switched networks
• Characteristics required
1. Correctness
2. Simplicity
3. Robustness
4. Stability
5. Fairness
6. Optimality
7. Efficiency
Elements of routing techniques for packet-switching networks
Performance criteria - Used for selection of route with following performances:

 Minimum number of hops

 Least Cost
 Minimum delay
 High throughput

In the Diagram, least cost path from 1 to 6 is 1-4-5-6 with minimum delay.

Decision time - Is it on a packet (datagram) or virtual circuit basis?

If datagram, routing is individualized for each packet.

Page 11 of 15
Decision place - refers to which node or nodes in the network are responsible for the routing decision.
Network information source
- Knowledge of the topology of the network, traffic load, and link cost. Some strategies use no
such information and yet manage to get through the packets. Eg. flooding and some random
strategies are in this category.

Network information update timing

- Update timing depends on the strategy. The more frequent the update, the better the routing
decision, but could impair the network.
Routing Strategies
A large number of routing strategies have evolved for dealing with the routing requirements of
packet-switching networks. Many having these strategies are also applied to internetwork routing. We
survey four key strategies: fixed, flooding, random, and adaptive.
Fixed Routing
- Single permanent route is configured for each source to destination pair
- Routes usually determined using a least cost algorithm
- Route fixed, at least until a change in network topology
- No difference in routing of datagrams and virtual circuits, because route is fixed
The following matrix shows, for each source-destination pair of nodes, the identity of the next
node on the route for the network. From this overall matrix, routing tables can be developed and stored at
each node. The complete route, then, from node 1 to node 6 is 1-4-5-6.

Flooding
• No network information is required
• Packet sent by node to all its adjacent nodes
• Incoming packets retransmitted on every link except incoming link
• Eventually a number of copies will arrive at destination
• Each packet is uniquely numbered so duplicates can be discarded
• Nodes can remember packets already forwarded to keep network load in bounds
• Can include a hop count in packets
• Very heavy load on traffic, but good in getting out emergency messages

For example, if node 1 in the above figure has a packet to send to node 6, it sends a copy of that
packet (with a destination address of 6), to nodes 2,3, and 4. Node 2 will send a copy to nodes 3 and 4.
Node 4 will send a copy to nodes 2,3, and 5. And so it goes. Eventually, a number of copies of the packet
will arrive at node 6. The packet must have some unique identifier (e.g., source node and sequence
number, or virtual-circuit number and sequence number) so that node 6 knows to discard all but the first
copy.

Page 12 of 15
Advantages:
a) the flooding technique is highly robust and could be used to send emergency messages
b) flooding might be used to initially set up the route for a virtual circuit
c) flooding can be useful for the dissemination of important information to all nodes
Disadvantages: It is the high traffic load that it generates, which is directly proportional to the connectivity
of the network.
Random Routing
• Simple and robust, like flooding, but with less load on network
• Intermediate node selects one outgoing path (anything but node from which packet delivered) for
retransmission of incoming packet
• Selection can be random or round robin
• Can select outgoing path based on probability calculation
• No network information is needed
• Route is typically not least cost nor minimum hop
• Not as much network traffic, but may take a short time to reach final destination.
Adaptive Routing
• Used by almost all packet switching networks
• Routing decisions change as conditions on the network change
— Failure: When a node or trunk fails, it can no longer be used as part of a route.
— Congestion: When a particular portion of the network is heavily congested, it is desirable
to route packets around the area of congestion.
• Requires information about network
• Decisions more complex
• Tradeoff between quality of network information and overhead (traffic burden)
• Reacting too quickly can cause oscillation
• Too slowly to be relevant
Adaptive Routing – Advantages
• Improved performance
• Aid congestion control
Page 13 of 15
CONGESTION CONTROL
What Is Congestion?
•Congestion occurs when the number of packets being transmitted through the network approaches
the packet handling capacity of the network
•Congestion control aims to keep number of packets below level at which performance falls off
dramatically
A packet-switching network is a network of queues. At each node, there is a queue of packets for
each outgoing channel. If the rate at which packets arrive and queue up exceeds the rate at which packets
can be transmitted, the queue size grows without bound and the delay experienced by a packet goes to
infinity. Even if the packet arrival rate is less than the packet transmission rate, queue length will grow
dramatically as the arrival rate approaches the transmission rate.

Consider the queuing situation at a single packet-switching node, such as is illustrated in the
above figure. Any given node has a number of transmission links attached to it; one or more to other
packet-switching nodes, and zero or more to host systems. On each link, packets arrive and depart. We can
consider that there are two buffers at each link, one to accept arriving packets (input), and one to hold
packets that are waiting to depart (output).
• Packets arriving are stored at input buffers
• Routing decision made
• Packet moves to output buffer
— Packets queued for output transmitted as fast as possible by Statistical time division
multiplexing
• If packets arrive too fast to be routed, or to be output, buffers will fill
• Can discard packets
• Can use flow control
• Can propagate congestion through network
Congestion Control
A number of control mechanisms for congestion control in packet-switching networks have been
suggested:
1. Send a control packet from a congested node to some or all source nodes. This choke packet will have the
effect of stopping or slowing the rate of transmission from sources and, hence, limit the total number of
packets in the network. This approach requires additional traffic on the network during a period of
congestion.
2. Rely on routing information. Routing algorithms provide link delay information to other nodes, which
influences routing decisions. This information could also be used to influence the rate at which new packets

Page 14 of 15
are produced. Because these delays are being influenced by the routing decision, they may vary too
rapidly to be used effectively for congestion control.
3. Make use of an end-to-end probe packet. Such a packet could be time-stamped to measure the
delay between two particular endpoints. This procedure has the disadvantage of adding overhead to the
network.
4. Allow packet-switching nodes to add congestion information to packets as they go by. There are two
possible approaches here. A node could add such information to packets going in the direction opposite of
the congestion. This information quickly reaches the source node, which can reduce the flow of packets
into the network. Alternatively, a node could add such information to packets going in the same direction as
the congestion. The destination either asks the source to adjust the load or returns the signal back to the
source in the packets (or acknowledgments) going in the reverse direction.



Page 15 of 15