Circuit, packet and virtual-circuit switching

A link can carry only so many bits a second, and many conversations want to use it at once. Networks share links in one of three ways. Circuit switching reserves a fixed slice of every link on the path for the whole call, whether or not anything is being sent. Packet switching cuts data into packets that take turns on each link and wait in a queue while it is busy; in its datagram form every packet carries its full destination address and is forwarded on its own. Virtual circuits sit in between: a setup step writes the path into every switch, then packets that carry only a short label follow it. This lesson compares the three, times a file across store-and-forward switches, and uses a binomial model to show why sharing on demand lets one link serve several times as many users.

Three ways to share a link

The three designs differ in what happens before the first byte is sent, in what each switch has to remember, and in what a link does when nobody is talking.

Circuit switching: a reserved slice of every link

A circuit-switched network divides each link into fixed channels. With frequency-division multiplexing (FDM) each call gets its own band of frequencies, as radio stations do. With time-division multiplexing (TDM) time is cut into frames that repeat at a fixed rate, and each call owns one slot in every frame.

The E1 trunk of ITU-T G.704 is a clean example of TDM. It sends 8,000 frames a second, each 256 bits long: 32 time slots of 8 bits. That makes 32 × 8 × 8,000 = 2,048,000 bits a second, and each slot is a 64 kb/s channel, exactly the rate of one telephone call coded with G.711 (8,000 samples a second of 8 bits each). Slot 0 carries the frame alignment pattern, slot 16 may carry signalling, and the other 30 slots carry one call each. The 1,544 kb/s frame of the same Recommendation, used on T1 lines, has 24 slots and one framing bit: 193 bits, 8,000 times a second.

Two consequences follow from reserving slots:

• A call is set up before it can talk. Signalling must find a free slot on every link of the path. If one link has none, the call is refused (the busy tone), not slowed down.
• Delay is fixed and the capacity is guaranteed, but idle time is wasted. The 64 kb/s belongs to the call from set-up to hang-up, also while nobody speaks. No other call can borrow the slot.

Packet switching and store and forward

A packet-switched network sends data in packets that carry their own addresses. IP is the datagram kind: RFC 791 describes it as carrying blocks of data called datagrams, treats each one as an independent entity, and gives it no mechanisms of its own for end-to-end reliability or sequencing. A router looks at each packet’s destination, picks the outgoing link and puts the packet in that link’s queue. Nothing is set up first, and nothing is reserved.

A store-and-forward switch receives a whole packet, checks it, and only then starts sending it on; the numericals in this lesson, and in exams, assume every switch works this way. Every hop therefore adds one transmission time, the packet’s length L in bits divided by the link rate R. For one packet over N equal links that is N × L/R, plus the propagation delay of each link and any queueing and processing. Sending the file as one unit, message switching, is the same rule with L as the whole file.

The example times a 10 MB file across three links of 100 Mb/s, first as one message and then as 1,500-byte packets with 40 bytes of headers each:

# Message switching against packet switching: a 10 MB file crosses three links of
# 100 Mb/s through two store-and-forward switches. Propagation delay is left out: it adds
# the same distance delay to both, so only the time to put bits on each link counts.

FILE_BYTES = 10_000_000  # 10 MB, decimal megabytes
RATE = 100_000_000  # 100 Mb/s on every link
LINKS = 3
PACKET = 1_500  # bytes on the wire per full packet
HEADER = 40  # bytes of headers in every packet (and in the message)
PAYLOAD = PACKET - HEADER  # 1,460 bytes of the file per packet


def transmit(nbytes):
    """Seconds to put nbytes onto one link."""
    return nbytes * 8 / RATE


# Message switching: each switch receives the whole message before it sends it on.
one_hop = transmit(FILE_BYTES + HEADER)
print(f"message switching: {LINKS} hops x {one_hop:.6f} s = {LINKS * one_hop:.6f} s")

# Packet switching: the file is cut into packets that follow each other through the switches.
full, rest = divmod(FILE_BYTES, PAYLOAD)
sizes = [PACKET] * full + ([rest + HEADER] if rest else [])
print(f"packets: {len(sizes)} ({full} full, the last one carries {rest} bytes of the file)")

# Store and forward, packet by packet: a link starts a packet once the whole packet has
# arrived and the link has finished the packet before it.
link_free = [0.0] * LINKS  # when each link finishes its latest packet
timeline = []
for number, size in enumerate(sizes, start=1):
    t = 0.0  # every packet is ready at the sender at time 0
    for link in range(LINKS):
        start = max(t, link_free[link])
        t = link_free[link] = start + transmit(size)
        if number <= 3:
            timeline.append((number, link + 1, start, t))
print(f"packet switching: the last packet arrives after {link_free[-1]:.6f} s")

print("first three packets (microseconds):")
for number, link, start, end in timeline:
    print(f"  packet {number} on link {link}: {start * 1e6:6.0f} to {end * 1e6:4.0f}")

# The usual shortcut treats every packet as full: (links + packets - 1) packet times.
shortcut = (LINKS + len(sizes) - 1) * transmit(PACKET)
print(f"shortcut (N + P - 1) x L/R: {shortcut:.6f} s")

message switching: 3 hops x 0.800003 s = 2.400010 s
packets: 6850 (6849 full, the last one carries 460 bytes of the file)
packet switching: the last packet arrives after 0.822160 s
first three packets (microseconds):
  packet 1 on link 1:      0 to  120
  packet 1 on link 2:    120 to  240
  packet 1 on link 3:    240 to  360
  packet 2 on link 1:    120 to  240
  packet 2 on link 2:    240 to  360
  packet 2 on link 3:    360 to  480
  packet 3 on link 1:    240 to  360
  packet 3 on link 2:    360 to  480
  packet 3 on link 3:    480 to  600
shortcut (N + P - 1) x L/R: 0.822240 s

As one message, each link must carry all 80 million bits before the next can start: 0.8 s a hop, 2.4 s in all. As 6,850 packets the links overlap. Look at the timeline for the first three packets: while packet 1 is on link 3, packet 2 is on link 2 and packet 3 on link 1.

That pipeline gives the usual formula for P equal packets over N links: the first packet needs N packet times to arrive, and each later packet arrives one packet time after the one before.

The formula treats every packet as full, so it gives 0.822240 s. The exact run is 80 µs shorter, because the last packet carries only 460 bytes of the file and needs 40 µs instead of 120 µs on the final link. Either way the file arrives almost three times sooner than as one message, although packet switching sends 6,849 more headers.

How big should a packet be?

Smaller packets make the pipeline finer, so less time is spent waiting for the first packet to fill each hop. But every packet carries the same 40 bytes of headers, so more packets also mean more bits to send. The example times the same file with payloads from 100 bytes to the whole file:

# How big should a packet be? Small packets flow through store-and-forward switches
# like a pipeline, but each one carries 40 bytes of headers. Same 10 MB file, links of
# 100 Mb/s, no propagation or queueing delay.
from math import ceil, sqrt

FILE_BYTES = 10_000_000
HEADER = 40
RATE = 100_000_000


def arrival(payload, links):
    """Seconds until the last packet arrives: (P + N - 2) full packet times plus the last packet."""
    packets = ceil(FILE_BYTES / payload)
    last = FILE_BYTES - (packets - 1) * payload
    full_time = (payload + HEADER) * 8 / RATE
    last_time = (last + HEADER) * 8 / RATE
    return (packets + links - 2) * full_time + last_time


sizes = [100, 500, 1_460, 4_000, 9_000, 100_000, FILE_BYTES]
print("payload bytes   3 links     10 links")
for size in sizes:
    label = f"{size:,}" if size < FILE_BYTES else "whole file"
    print(f"{label:>13}  {arrival(size, 3):8.4f} s  {arrival(size, 10):8.4f} s")

# Fewer packets mean fewer headers; more packets mean a shorter pipeline wait. The two
# balance at a payload of sqrt(file x header / (links - 1)).
for links in (3, 10):
    best = sqrt(FILE_BYTES * HEADER / (links - 1))
    print(f"{links} links: best payload about {best:,.0f} bytes, {arrival(round(best), links):.4f} s")
    for factor in (0.5, 2):
        size = round(best * factor)
        print(f"  {factor:g} x that ({size:,} bytes): {arrival(size, links):.4f} s")

payload bytes   3 links     10 links
          100    1.1200 s    1.1201 s
          500    0.8641 s    0.8644 s
        1,460    0.8222 s    0.8230 s
        4,000    0.8086 s    0.8109 s
        9,000    0.8050 s    0.8101 s
      100,000    0.8163 s    0.8723 s
   whole file    2.4000 s    8.0000 s
3 links: best payload about 14,142 bytes, 0.8045 s
  0.5 x that (7,071 bytes): 0.8057 s
  2 x that (28,284 bytes): 0.8057 s
10 links: best payload about 6,667 bytes, 0.8096 s
  0.5 x that (3,333 bytes): 0.8120 s
  2 x that (13,333 bytes): 0.8120 s

With 100-byte payloads the headers add 40 % to the bits sent, and the file needs 1.12 s whatever the number of links. With one big message there is no pipeline at all: 2.4 s over 3 links and 8 s over 10. In between, the total time is close to (F/p + N − 1) × (p + h) × 8/R for a file of F bytes, payloads of p bytes and headers of h bytes, and it is smallest where its two costs balance:

For this file that is about 14,100 bytes over 3 links and 6,700 over 10, and the curve is flat near its best point: half or twice that size costs only 1.2 ms more over 3 links and 2.4 ms over 10. Real networks stay well below it for other reasons. Ethernet carries at most 1,500 bytes of data in a frame (RFC 894), a big packet holds a link longer while other users’ packets wait behind it, and a bit error costs a whole packet to send again.

Virtual circuits: set up a path, then send labelled packets

A virtual circuit keeps the packets of packet switching but adds the setup of circuit switching. It has three phases:

1. Setup. A request travels along the chosen path, and every switch on it stores a row: packets that arrive on this port with this label leave on that port with that label.
2. Data transfer. Each packet carries only the label. A switch finds the row, swaps the label and sends the packet on, so every packet of the circuit follows the same path and arrives in order.
3. Teardown. The rows are removed and the labels can be used again.

A label only has to be unique on one link, which keeps it short. ATM, specified in ITU-T I.361, carries everything in cells of 53 octets: a 5-octet header with the circuit’s identifiers and a 48-octet information field. MPLS applies the same idea to IP packets, which it sends along label-switched paths. RFC 3031 defines its label as a short, fixed-length identifier that has meaning only locally, and lets the downstream router choose the label that its upstream neighbour must use.

The example sets up a circuit through three switches in that downstream-first order, sends two packets and then restarts the middle switch:

# A virtual circuit across three switches. Setting it up writes one row into every
# switch on the path; data packets then carry only a short label, which each switch
# looks up and swaps for the label the next switch expects.


class Switch:
    def __init__(self, name, first_label):
        self.name = name
        self.table = {}  # (in port, in label) -> (out port, out label)
        self.free_label = first_label

    def add(self, in_port, out_port, out_label):
        """Pick a label for the incoming side and remember where it leads."""
        label = self.free_label
        self.free_label += 1
        self.table[(in_port, label)] = (out_port, out_label)
        return label

    def forward(self, port, label):
        out_port, out_label = self.table[(port, label)]
        print(f"  {self.name}: in port {port}, label {label} -> out port {out_port}, label {out_label}")
        return out_port, out_label


# The path: host A -> S1 (port 1 in, port 2 out) -> S2 (1 in, 3 out) -> S3 (2 in, 4 out) -> host B.
s1, s2, s3 = Switch("S1", 20), Switch("S2", 40), Switch("S3", 70)
path = [(s1, 1, 2), (s2, 1, 3), (s3, 2, 4)]

# Setup runs from the far end back, so each switch learns the label its neighbour chose.
label = 0  # the label host B receives (0: no label, the circuit ends here)
for switch, in_port, out_port in reversed(path):
    label = switch.add(in_port, out_port, label)
print(f"set up: host A sends on label {label}")
for switch, _, _ in path:
    print(f"  {switch.name} table: {switch.table}")


def send(first_label):
    label = first_label
    for switch, in_port, _ in path:
        _, label = switch.forward(in_port, label)


print("packet 1:")
send(20)
print("packet 2 (same path, same labels, so packets stay in order):")
send(20)

# A switch that restarts loses its table, and with it every circuit through it.
s2.table.clear()
print("after S2 restarts:")
try:
    send(20)
except KeyError as missing:
    print(f"  S2 has no row for {missing}: the circuit must be set up again")

set up: host A sends on label 20
  S1 table: {(1, 20): (2, 40)}
  S2 table: {(1, 40): (3, 70)}
  S3 table: {(2, 70): (4, 0)}
packet 1:
  S1: in port 1, label 20 -> out port 2, label 40
  S2: in port 1, label 40 -> out port 3, label 70
  S3: in port 2, label 70 -> out port 4, label 0
packet 2 (same path, same labels, so packets stay in order):
  S1: in port 1, label 20 -> out port 2, label 40
  S2: in port 1, label 40 -> out port 3, label 70
  S3: in port 2, label 70 -> out port 4, label 0
after S2 restarts:
  S1: in port 1, label 20 -> out port 2, label 40
  S2 has no row for (1, 40): the circuit must be set up again

Each switch rewrites the label, so the packet that entered with label 20 leaves S1 with 40 and S2 with 70. When S2 restarts, its table is empty and the circuit is gone: the packet has nowhere to go until the circuit is set up again. A datagram router that restarts loses the packets in its queues, but it keeps no rows per conversation, so as soon as it has its routes back it forwards any packet that arrives.

Statistical multiplexing: why sharing wins for bursty users

Much data traffic comes in bursts: a page loads, then the reader reads. Suppose a link can carry 10 users at full speed at the same moment, and each user is sending only 12 % of the time, independently of the others. Circuit switching must reserve a tenth of the link for each user, so it admits 10 users and the link is busy only 12 % of the time on average.

Packet switching can admit more users, because it only fails them when more than 10 happen to send at the same moment. With n users each active with probability p, the number active at once follows the binomial distribution:

# Statistical multiplexing: users share a link that can carry 10 of them at the same
# moment. Each user is active (sending) 12 % of the time, independently of the others.
import random
from math import comb

ACTIVE = 0.12  # share of the time one user is sending
CAPACITY = 10  # users the link can carry at once


def p_overload(users, p=ACTIVE, capacity=CAPACITY):
    """P(more than `capacity` of `users` are active at once): the binomial distribution."""
    return sum(comb(users, k) * p**k * (1 - p) ** (users - k) for k in range(capacity + 1, users + 1))


print("users  average load  P(overload)")
for users in (10, 20, 30, 40, 50, 60, 70):
    load = users * ACTIVE / CAPACITY  # average share of the link in use
    print(f"{users:5}  {load:11.0%}  {p_overload(users):11.6f}")

# Circuit switching would admit only 10 users, each with a reserved tenth of the link.
print(f"circuit switching: 10 users, link busy {10 * ACTIVE / CAPACITY:.0%} of the time on average")

# Check the formula for 50 users by sampling 100,000 random moments.
random.seed(42)
samples = 100_000
over = sum(random.binomialvariate(50, ACTIVE) > CAPACITY for _ in range(samples))
print(f"sampled: {over} of {samples:,} moments overloaded = {over / samples:.4f}")
print(f"formula: {p_overload(50):.4f}")

users  average load  P(overload)
   10          12%     0.000000
   20          24%     0.000004
   30          36%     0.000452
   40          48%     0.006153
   50          60%     0.032498
   60          72%     0.099402
   70          84%     0.214170
circuit switching: 10 users, link busy 12% of the time on average
sampled: 3265 of 100,000 moments overloaded = 0.0326
formula: 0.0325

With 50 users the link is busy 60 % of the time on average, five times the circuit-switched figure, and more than 10 users are active only about 3.25 % of the time; sampling 100,000 random moments gives almost the same answer, 0.0326. During those moments packets queue and may be dropped, so the price of sharing is variable delay and occasional loss. Push to 70 users and the link is overloaded about 21 % of the time. That is the trade-off of the whole lesson: reserving capacity buys predictable service for steady streams, and sharing it buys efficiency for bursty ones.

Exercise: time a file across the switches

def total_delay(file_bytes, payload, header, links, rate, prop):
    """Seconds until the last bit of the file arrives, sent as packets through store-and-forward switches.

    file_bytes: size of the file; payload: bytes of the file per packet (the last packet may carry fewer);
    header: header bytes in every packet; links: number of links; rate: bits per second of every link;
    prop: propagation delay of every link, in seconds.
    """
    # This is message switching: the whole file and one header cross each link in turn.
    # Change it so that it times packet switching.
    one_hop = (file_bytes + header) * 8 / rate
    return links * (one_hop + prop)

import math

from delay import total_delay


def close(a, b):
    return math.isclose(a, b, rel_tol=1e-9, abs_tol=1e-12)


def test_lesson_example():
    """10 MB in 1,460-byte payloads with 40-byte headers over three 100 Mb/s links"""
    assert close(total_delay(10_000_000, 1_460, 40, 3, 100_000_000, 0), 0.82216)


def test_one_packet_is_message_switching():
    """a file that fits in one packet crosses each link in turn"""
    assert close(total_delay(1_000, 1_460, 40, 3, 1_000_000, 0), 0.02496)
    assert close(total_delay(500, 1_000, 20, 2, 1_000_000, 0.002), 0.01232)


def test_two_full_packets():
    """two 1,500-byte packets over two 1 Mb/s links take three packet times"""
    assert close(total_delay(2_920, 1_460, 40, 2, 1_000_000, 0), 0.036)


def test_propagation_is_added_once_per_link():
    """1 ms of propagation on each of three links adds 3 ms"""
    assert close(total_delay(10_000_000, 1_460, 40, 3, 100_000_000, 0.001), 0.82516)


def test_one_link_has_no_pipeline_wait():
    """on a single link the packets simply follow each other"""
    assert close(total_delay(10_000, 1_000, 0, 1, 8_000_000, 0.005), 0.015)


def test_short_last_packet():
    """three packets of which the last carries 100 bytes, over four links"""
    assert close(total_delay(2_100, 1_000, 50, 4, 1_000_000, 0.0001), 0.0436)

Interview questions

What is the difference between a virtual circuit and a datagram network? (warm-up)

In a datagram network such as IP, every packet carries its full destination address and each router picks the next hop for it independently. There is no setup, routers keep no per-conversation state, and packets of one flow can take different paths and arrive out of order. A virtual-circuit network sets up a path first: every switch on it stores a row for the circuit, and packets carry only a short label that each switch looks up and swaps. Packets then follow one path in order and the network can reserve capacity per circuit, but setup costs a round of signalling and a failed switch breaks every circuit through it. Both share links packet by packet, unlike circuit switching, which reserves a fixed slice of each link.

Key takeaways

• Circuit switching reserves a fixed slot or band on every link for the whole call: guaranteed rate and fixed delay, but idle capacity cannot be borrowed. An E1 frame has 32 slots of 64 kb/s.
• Datagram packet switching sets nothing up and reserves nothing; packets carry addresses, share links on demand and wait in queues when links are busy.
• A store-and-forward hop adds one transmission time L/R. P equal packets over N links take (N + P − 1) × L/R, plus propagation, queueing and processing.
• Packets beat one big message because the hops work in parallel; payload size balances header overhead against the pipeline wait.
• Virtual circuits set up per-circuit rows in every switch, then forward short, swapped labels: ATM cells and MPLS label-switched paths work this way.
• Statistical multiplexing admits more bursty users than reserved circuits; the binomial distribution gives how often they overload the link.