Packet switching: store-and-forward, datagrams, statistical multiplexing

1. Rate of one circuit when a 1.536 Mbps link carries 24 circuits?
   Stuck? Peek at 1.2.1 Circuit switching: setup, reserved resources, teardown

   • Circuit switching: setup → data transfer → teardown.
   • Dedicated path; each link's share (time slot or frequency band) is reserved: circuit rate = R/n.
   • Total time = setup + bits/circuit rate (+ travel time if given).
   • + guaranteed rate, in order, no queues; − setup delay, idle capacity wasted, fragile.

   Read lesson 1.2.1

2. What is the network-layer PDU called?
   Stuck? Peek at 1.1.3 Encapsulation, headers, PDU names, addresses and devices per layer

   • Encapsulation: payload + header (+ trailer at data link); decapsulation in reverse.
   • PDUs: message (app) → segment (transport) → packet/datagram (network) → frame (data link) → bits.
   • Addresses: link (per hop, changes) · network (end to end, fixed) · which-program id · names.
   • Devices: hub/repeater 1 · bridge/switch 2 · router 3 · gateway/host up to 7.
   • Efficiency = data / (data + all headers + trailer).

   Read lesson 1.1.3

3. P(none of n sends) for probability p each?
   Stuck? Peek at 0.2.4 Exponents, logarithms and basic probability

   • 2ᵃ·2ᵇ = 2ᵃ⁺ᵇ; 2¹⁰ ≈ 10³ (estimates only).
   • log₂ x = power of 2 giving x; bits for N values = ⌈log₂ N⌉.
   • P(none) = (1−p)ⁿ · P(≥ 1) = 1 − (1−p)ⁿ · P(exactly 1) = n·p·(1−p)ⁿ⁻¹.
   • (1 − 1/n)ⁿ → 1/e ≈ 0.368; 1/(2e) ≈ 0.184.
   • 1 + 2 + … + 2ᵏ⁻¹ = 2ᵏ − 1; expected tries = 1/p.

   Read lesson 0.2.4

Posting letters instead of phoning: nobody books the roads in advance. Each letter carries its full destination address, sorting offices pass it along to the next office, and two letters to the same place may even take different routes. If many letters arrive at once, they wait in a pile. This is packet switching — the way the Internet works.

A router receives a packet on one link and must send it on another. Can it start sending the first bit out before the last bit has arrived?

Not in store-and-forward switching: the router must receive the whole packet, store it, check it, then forward it. So every hop costs the full time to push the packet out again. (This is why splitting a message into smaller packets speeds things up — the pieces pipeline across hops.)

Packets and no reservation

Store-and-forward

A switch (router) receives an entire packet, stores it in a buffer, then forwards it on the next link. If the outgoing link is busy, the packet waits in a queue. If the buffer is full, arriving packets are dropped (packet loss).

The datagram approach

In the datagram approach every packet is handled independently: each router looks at the destination address in the header, consults its own lookup table of directions, and sends the packet on. Consequences:

• No setup phase — send immediately.
• Packets of one message may take different routes and arrive out of order; the receiver must reorder them.
• A failed router only affects packets passing through it; others route around it.

Statistical multiplexing

Because nothing is reserved, link capacity is shared on demand: whoever has packets uses the link. If users are active only part of the time, many more users can share a link than circuit switching could admit — at the risk of occasional queueing and loss when too many are active together.

To quantify the risk we need the chance that exactly k of n independent users are active: C(n, k) · pᵏ · (1 − p)ⁿ⁻ᵏ, where C(n, k) = n! / (k!(n − k)!) counts the ways to choose which k users are active. (For k = 1 this is the n·p·(1 − p)ⁿ⁻¹ of Lesson 0.2.4.)

Putting it together

• Packet switching reserves nothing; packets use links on demand at full rate.
• Store-and-forward makes every hop wait for the whole packet; queues build and can overflow.
• Statistical multiplexing lets many bursty users share a link with small risk.

• Store-and-forward means the router waits for the entire packet before forwarding — the sending time is paid again on every link.
• Datagram packets can arrive out of order; circuit-switched data cannot.
• Packet switching can lose packets when buffers overflow; circuit switching does not queue on the path.

"Circuit = book the road. Packet = post the letters."

Datagrams are flexible but every packet carries a full address and may wander. Next (1.2.3): can we get packet switching's sharing with circuit switching's fixed path — set up a path once, then let small-labelled packets follow it?

1. NAT

   A packet takes 2 ms to be pushed onto each link. Store-and-forward over 5 links, other delays ignored. Arrival time in ms?

   Write your answer before opening the key.

2. MSQ

   Which are true of datagram packet switching?

   1. Each packet carries the full destination address.
   2. A path is reserved before sending.
   3. Packets may arrive out of order.
   4. Packets may be dropped when buffers are full.
3. MCQ

   Packet switching lets more users share a link than circuit switching mainly because:

   1. packets are smaller than circuits
   2. users are not all active at the same time
   3. routers are faster than circuit switches
   4. packets never wait
4. NAT

   4 users, each active with probability 0.5 independently. P(exactly 2 active)? (3 decimals)

   Write your answer before opening the key.

• Packet switching: packets with headers; no reservation; full link rate while sending.
• Store-and-forward: receive whole packet → buffer/queue → forward; full buffer → loss.
• Datagram: each packet routed independently; may reorder; robust to failures.
• Statistical multiplexing: share capacity on demand; P(exactly k of n) = C(n,k)pᵏ(1−p)ⁿ⁻ᵏ.

• packet switching
• store-and-forward
• buffer, queue
• packet loss on overflow
• datagram approach
• out-of-order arrival
• statistical multiplexing
• C(n, k) and P(exactly k of n)

1. Store-and-forward?
   Reveal answer

   A router receives the whole packet before forwarding it.
2. Datagram approach?
   Reveal answer

   Each packet is routed independently using its own destination address.
3. P(exactly k of n active)?
   Reveal answer

   C(n, k)·pᵏ·(1 − p)ⁿ⁻ᵏ.
4. Why can packets arrive out of order?
   Reveal answer

   Different packets of one message may take different routes.

• One packet, h links, store-and-forward: h × (packet bits / rate) for sending (travel times added in 1.3.2). — equal-rate links, one packet, no queueing.
• Circuit users = R / per-user rate; packet risk = P(more than that many active) by the binomial sum. — independent users with the same activity probability.