Data Communication · Lecture 10
Switching
Circuit, datagram and virtual-circuit networks: how data finds its way through switches
Md Mahbub E Noor · Assistant Professor, Department of CSE, University of Barishal
Course: Data Communication · 2nd Year, 2nd Semester
Moving data through a network: today's goals
- Explain why networks use switches instead of direct links
- Describe circuit switching: its three phases, efficiency and delay
- Describe datagram and virtual-circuit packet switching, with their tables
- Calculate and compare end-to-end delay for each method
- Size crossbar and multistage (Clos) switches; know TSI and packet-switch parts
Lecture 9 ended with
statistical TDM: share capacity on demand, label each slot with an address.
Today
the same idea across a whole network of switches, compared with reserving a path in advance.
Reading: Forouzan, Chapter 8
Md Mahbub E Noor
Lecture 10: Switching
University of Barishal
2 / 31
Why switching?
- Connecting every pair directly (a mesh) needs n(n − 1)/2 links: impractical beyond a few devices
- A switched network is a set of interconnected nodes called switches
- Switches create temporary connections between devices attached to them
- End systems (computers, phones) attach to switches; switches attach to each other
Mesh: 8 × 7 / 2 = 28 links
Switched: 8 links to a switch
Mesh for 100 devices
100 × 99 / 2
4,950 links
Md Mahbub E Noor
Lecture 10: Switching
University of Barishal
3 / 31
Three ways to switch
Circuit switching
Reserve a dedicated path first, then send
· physical layer
· traditional telephone network
Datagram switching
Packet switching: each packet routed on its own
· network layer
· the Internet (IP)
Virtual-circuit switching
Packet switching along a path set up in advance
· data link layer
· Frame Relay, ATM, MPLS
Packet switching = datagram + virtual circuit: data is cut into packets and no resources are reserved permanently. A fourth historical method, message switching, stored whole messages at each node.
Md Mahbub E Noor
Lecture 10: Switching
University of Barishal
4 / 31
Circuit switching
- Switches are joined by links, each divided into channels by FDM or TDM
- A connection is a dedicated path: one channel on each link
- Resources are reserved at setup and held until teardown
- Data is a continuous flow, not packets; switches forward by channel, so no addresses are needed
A
S1
S2
S3
S4
B
Orange: one channel reserved on every link of the path for the whole call
Each link is divided into n channels by FDM or TDM (Lecture 9); a call takes one channel per link.
Md Mahbub E Noor
Lecture 10: Switching
University of Barishal
5 / 31
The three phases of a circuit
- Setup: the end systems' addresses are used once, to build the path
- Data transfer: data flows with no addressing, no waiting at switches
- Teardown: either side signals the end; switches free the channels
- Total delay = setup + data transfer + teardown
A
B
| Phase | What happens |
|---|---|
| Setup | request travels to B, each switch reserves a channel; B accepts; acknowledgement returns |
| Data transfer | continuous flow on the reserved path |
| Teardown | a signal releases the channels |
Md Mahbub E Noor
Lecture 10: Switching
University of Barishal
6 / 31
Example 8.1: a small circuit-switched network
- Eight telephones in a small area, joined by one switch
- Voice channels of 4 kHz; each link carries two channels by FDM
- So each link needs 2 × 4 = 8 kHz of bandwidth
- Current calls: 1↔7, 2↔5, 3↔8, 4↔6; the switch changes them as new calls are made
1
5
2
6
3
7
4
8
Colour shows each connection: 1↔7, 2↔5, 3↔8, 4↔6
Each link: FDM, 2 voice channels × 4 kHz
2 × 4 kHz
8 kHz per link
Md Mahbub E Noor
Lecture 10: Switching
University of Barishal
7 / 31
Circuit switching: efficiency and delay
- Efficiency: low; resources stay reserved for the whole connection, busy or idle
- Fine for steady voice calls; wasteful for bursty computer traffic
- Delay: after setup, minimal and constant; no waiting at switches
- Worked example: a 30 kbit message over 3 links at 1 Mbps
| Step | Working | Time |
|---|---|---|
| Setup (request + acknowledgement) | given | 20 ms |
| Transmit the message | 30 kbit / 1 Mbps | 30 ms |
| Propagation, 3 links | 3 × 2 ms | 6 ms |
| Total (teardown ignored) | 20 + 30 + 6 | 56 ms |
Illustrative numbers (not from the textbook). Notice the 20 ms setup paid before a single bit is sent.
Efficiency when the line is busy only 10% of a call
90% of reserved capacity is idle
10% use
Md Mahbub E Noor
Lecture 10: Switching
University of Barishal
8 / 31
Checkpoint 1 · 3 minutes
Check your understanding
Q1
How many links would a full mesh of 50 devices need? How many with one central switch?
Q2
In Example 8.1, why is each link 8 kHz wide?
Q3
Setup takes 15 ms, a 60 kbit message is sent at 2 Mbps over 4 links with 1 ms propagation each. Total delay?
Md Mahbub E Noor
Lecture 10: Switching
University of Barishal
9 / 31
Packet switching: datagram networks
- The message is divided into packets; each carries the destination address
- Each packet (a datagram) is routed independently
- Packets may take different paths, so they can arrive out of order, or be lost
- No setup or teardown: also called connectionless; used by IP in the Internet
A
S1
S2
S3
S4
B
1
2
3
4
Packets 1–4 of one message, on different routes at the same moment
No reservation: resources are used on demand, first come, first served. A busy switch makes packets wait in a queue.
Md Mahbub E Noor
Lecture 10: Switching
University of Barishal
10 / 31
Routing tables in a datagram network
- Each switch has a routing table: destination address → output port
- Tables are built and updated by routing protocols (network-layer topic)
- On arrival, the switch reads the destination address and looks up the port
- The forwarding decision is made packet by packet
Routing table of a switch
| Destination address | Output port |
|---|---|
| 1232 | 1 |
| 4150 | 2 |
| 9130 | 3 |
| … | … |
A packet arrives with destination 4150
look up 4150 → port 2
forward on port 2
The destination address stays the same for the whole journey; each switch makes its own decision.
Md Mahbub E Noor
Lecture 10: Switching
University of Barishal
11 / 31
Delay in a datagram network
- No setup delay, but each switch must receive the whole packet before forwarding it (store-and-forward)
- Each packet may also wait in a switch's queue
- For one packet over 3 links: 3 transmissions + 3 propagations + 2 waits
- Delay varies from packet to packet: not uniform
A
S1
S2
B
Total = 3T + 3τ + w₁ + w₂
T = transmission time, τ = propagation time, w = waiting at each switch (grey)
Md Mahbub E Noor
Lecture 10: Switching
University of Barishal
12 / 31
Worked example: packet versus circuit
- Same message as slide 8: 30 kbit, 3 links, 1 Mbps, 2 ms propagation
- Cut it into 5 packets of 6 kbit; no setup needed
- Switches work on different packets at the same time: pipelining
- Here packet switching wins, 48 ms against 56 ms, but queuing delay can reverse it
| Quantity | Working | Value |
|---|---|---|
| Packets N | 30 kbit cut into 5 × 6 kbit | 5 |
| Packet time T | 6,000 / 1,000,000 s | 6 ms |
| Pipelined transmission | (N + links − 1) × T = 7 × 6 | 42 ms |
| Propagation | 3 × 2 ms | 6 ms |
| Packet total | 42 + 6 | 48 ms |
Circuit (slide 8)
20 + 30 + 6
56 ms
Packet (no queuing)
42 + 6
48 ms
Md Mahbub E Noor
Lecture 10: Switching
University of Barishal
13 / 31
Try it: circuit or packet, which is faster?
Interactive
Md Mahbub E Noor
Lecture 10: Switching
University of Barishal
14 / 31
Checkpoint 2 · 3 minutes
Check your understanding
Q1
Give two reasons why packets of one message can arrive out of order in a datagram network.
Q2
One 8,000-bit packet crosses 3 links at 1 Mbps, 1 ms propagation each, waiting 2 ms at each switch. Total delay?
Q3
A 40 kbit message is sent as 4 packets over 2 links at 1 Mbps (ignore propagation). Total time?
Md Mahbub E Noor
Lecture 10: Switching
University of Barishal
15 / 31
Virtual-circuit networks
- A cross between circuit-switched and datagram networks
- A path is set up first; then all packets of the connection follow it, in order
- Packets carry a short local label, the VCI, not the full destination address
- Normally at the data link layer: Frame Relay and ATM (today, MPLS works similarly)
| Feature | Like circuit switching | Like datagram switching |
|---|---|---|
| Setup and teardown | yes | |
| Same path for all packets | yes | |
| Data in packets with headers | yes | |
| Resources | can be reserved at setup | or allocated on demand |
Two kinds of address
Global address (source, destination): used only during setup
Virtual-circuit identifier (VCI): a small number with meaning on one link only; carried in every frame
Md Mahbub E Noor
Lecture 10: Switching
University of Barishal
16 / 31
Data transfer: following the VCI through the tables
- Each switch keeps one table row per virtual circuit: in port, in VCI → out port, out VCI
- A frame arrives on port 1 with VCI 14: switch 1 sends it out on port 3 with VCI 66
- Switch 2: (1, 66) → (2, 22); switch 3: (2, 22) → (3, 77)
- The lookup is a simple table index, so switching is fast
A
S1
S2
S3
B
VCI 14
VCI 66
VCI 22
VCI 77
| Switch | In port | In VCI | Out port | Out VCI |
|---|---|---|---|---|
| Switch 1 | 1 | 14 | 3 | 66 |
| Switch 2 | 1 | 66 | 2 | 22 |
| Switch 3 | 2 | 22 | 3 | 77 |
Md Mahbub E Noor
Lecture 10: Switching
University of Barishal
17 / 31
Try it: follow the VCI through the switches
Interactive
Md Mahbub E Noor
Lecture 10: Switching
University of Barishal
18 / 31
Setting up and tearing down a virtual circuit
- Setup has two steps: a setup request and an acknowledgement
- The request uses global addresses and fills three of the four table columns
- The acknowledgement carries back each next-hop VCI to fill the fourth
- Teardown removes the rows; the VCIs can be reused
1 · Setup request (A → B)
Travels by the global address. Each switch picks the out port, fills in port, in VCI, out port, and chooses an unused incoming VCI for the next link.
2 · Acknowledgement (B → A)
Travels back; each switch learns the out VCI chosen by the next switch, completing its row. A learns VCI 14.
3 · Teardown
A sends a teardown request; B confirms; every switch deletes the row.
Md Mahbub E Noor
Lecture 10: Switching
University of Barishal
19 / 31
Virtual circuits: efficiency and delay
- Pays a setup delay, like circuit switching, and teardown at the end
- Data transfer is store-and-forward, like datagram switching
- If resources are reserved at setup, delay is the same for every packet
- Switching is fast: one table lookup per frame, no route calculation
Total = setup + data transfer + teardown
| Resources | Effect on delay |
|---|---|
| Reserved at setup | every packet sees the same delay |
| On demand | packets can wait in queues: different delays |
One setup round trip, then 3 packets of T each over 3 links
setup + (3 + 3 − 1)T + 3τ
same path, in order
Md Mahbub E Noor
Lecture 10: Switching
University of Barishal
20 / 31
Circuit, datagram and virtual circuit compared
| Circuit | Datagram | Virtual circuit | |
|---|---|---|---|
| Setup / teardown | yes | no | yes |
| Resources | reserved for the whole call | on demand | reserved or on demand |
| Data unit | continuous stream | packets (datagrams) | packets (frames) |
| Address in data | none | full destination address | local VCI |
| Path | fixed | per packet, may differ | fixed |
| Order | kept | may change | kept |
| Delay | setup, then constant | variable, no setup | setup, then steady or variable |
| Efficiency | low for bursty traffic | high | high |
| Layer / example | physical / telephone | network / IP | data link / Frame Relay, ATM |
Md Mahbub E Noor
Lecture 10: Switching
University of Barishal
21 / 31
Try it yourself: Switching Lab
- 1 · Circuit vs packet: change message size, packets, links and setup; who wins?
- 2 · Datagrams: send four packets; do they arrive in order?
- 3 · Virtual circuit: step a frame through three switch tables
- 4 · Switch fabric: crosspoints for crossbar and three-stage switches
Md Mahbub E Noor
Lecture 10: Switching
University of Barishal
22 / 31
Inside a circuit switch: the crossbar
- A space-division switch keeps paths physically separate
- A crossbar connects n inputs to m outputs with n × m crosspoints
- Closing crosspoint (i, j) connects input i to output j; each input uses one at a time
- Problem: crosspoints grow as n², and most are idle at any moment
Rows = inputs, columns = outputs; orange = closed crosspoints
Crosspoints, n × n crossbar
n² = 6²
36
1,000 × 1,000 crossbar
1,000²
1,000,000
At most 1,000 can be in use at once: 99.9% idle.
Md Mahbub E Noor
Lecture 10: Switching
University of Barishal
23 / 31
Multistage switches and Example 8.3
- Combine small crossbars in stages; inputs can reach outputs through several middle crossbars
- Stage 1: N/n crossbars of size n × k; stage 2: k crossbars of N/n × N/n; stage 3: N/n of k × n
- Ex. 8.3: a 200 × 200 switch with n = 20, k = 4 needs only 2,000 crosspoints
- Drawback: blocking: with only 4 middle paths per group, a 5th call from a group cannot connect
N/n of n × k
k of N/n × N/n
N/n of k × n
Total = 2kN + k(N/n)²
Ex. 8.3: N = 200, n = 20, k = 4
2·4·200 + 4·(200/20)² = 1,600 + 400
2,000 (5% of 40,000)
Md Mahbub E Noor
Lecture 10: Switching
University of Barishal
24 / 31
Example 8.4: a non-blocking Clos switch
- Clos criterion: no blocking if the middle stage has k ≥ 2n − 1 crossbars
- Minimum crosspoints when n = √(N/2)
- Ex. 8.4: N = 200 → n = 10, k = 19
- Total 15,200 crosspoints: more than Example 8.3 (2,000), but still only 38% of 40,000, and never blocks
n = √(N/2), k = 2n − 1
Total ≥ 4N[√(2N) − 1]
Clos criterion: with k ≥ 2n − 1 middle crossbars, a three-stage switch never blocks
| Stage | Crossbars | Size | Crosspoints |
|---|---|---|---|
| 1 | 20 | 10 × 19 | 20 × 190 = 3,800 |
| 2 | 19 | 20 × 20 | 19 × 400 = 7,600 |
| 3 | 20 | 19 × 10 | 20 × 190 = 3,800 |
| Total | 15,200 |
Md Mahbub E Noor
Lecture 10: Switching
University of Barishal
25 / 31
Try it: crossbar or three-stage switch?
Interactive
Md Mahbub E Noor
Lecture 10: Switching
University of Barishal
26 / 31
Time-division switches, and inside a packet switch
- A time-division switch reorders TDM slots instead of building separate paths
- The TSI uses memory: write in arrival order, read out in the order of the destinations
- Large exchanges combine stages: TST (time–space–time)
- A packet switch (router) has input ports, a switching fabric, output ports and a routing processor
Time-slot interchange (TSI)
Writes incoming TDM slots into RAM in arrival order, then reads them out in the order the outputs need: here A moves to slot 2, C to slot 1 …
A
B
C
D
→ RAM →
C
A
D
B
Space and time together: TST
Time stage, space stage (crossbar), time stage: used in large digital telephone exchanges
Packet switch (router) parts
Input ports (physical, data link, queue) · switching fabric (crossbar, banyan) · output ports · routing processor (table lookup)
Md Mahbub E Noor
Lecture 10: Switching
University of Barishal
27 / 31
See it in action: finding a path
- Watch a circuit being set up, used and torn down
- See four datagrams take different routes and arrive out of order
- Follow a frame along a virtual circuit as its VCI changes
- When a “Pause & predict” card appears, answer before the video moves on
Click the video to play or pause · Press → for full screen
Md Mahbub E Noor
Lecture 10: Switching
University of Barishal
28 / 31
Checkpoint 3 · 3 minutes
Check your understanding
Q1
Switch 2's table has the row (in port 3, in VCI 41) → (out port 1, out VCI 9). A frame arrives on port 3 with VCI 41. What leaves, and where?
Q2
How many crosspoints does a 400 × 400 single crossbar need, and a Clos switch for N = 400?
Q3
Give one advantage and one disadvantage of datagram switching compared with virtual circuits.
Md Mahbub E Noor
Lecture 10: Switching
University of Barishal
30 / 31
Key takeaways
- Switches create temporary connections, avoiding n(n − 1)/2 direct links
- Circuit: setup, data, teardown; reserved channels; constant delay but wasteful
- Datagram: independent packets with full addresses; efficient; variable delay and order
- Virtual circuit: setup, then label-swapped packets (VCI) on one path
- Crossbar n² crosspoints; multistage 2kN + k(N/n)²; Clos k = 2n − 1 never blocks
Next lecture
Lecture 11 · Data Link Layer I
Framing, byte and bit stuffing, and error detection and correction: parity, Hamming codes, checksums and CRC.
Reading: Forouzan, Chapters 9 and 10 · Practise in Switching Lab
Md Mahbub E Noor
Lecture 10: Switching
University of Barishal
31 / 31