4 · Message segmentation ★
HW1 P7 · Sample midterm P2 · slide 1-24 (store-and-forward)
The idea
- Store-and-forward (from topic 2): a router must receive the whole packet before it can send any of it on.
- No segmentation: the message is one giant packet. Each router waits for the entire message, so the links take turns and only one link is busy at a time.
- Segmentation: chop the message into small packets. While packet 2 is on link 1, packet 1 is already on link 2. All the links work at the same time (pipelining), so the total time drops a lot.
The formulas
\(N\) = number of links (hops), \(R\) = rate of each link, \(M\) = message size, \(P\) = number of packets, \(L\) = size of one packet including its header.
No segmentation (the whole message crosses each link one after another):
$$T = N \cdot \frac{M}{R}$$With segmentation into \(P\) packets:
$$T = (N + P - 1)\,\frac{L}{R}$$• Links = routers + 1. "4 intermediate routers" means 5 links.
• Add the header to every packet before computing \(L/R\): \(L = \text{payload} + \text{header}\).
• "10 users use the network" does not divide the rate. In packet switching each packet goes at the full link rate R.
• If propagation is not ignored, add \(N \cdot d_{prop}\) on top (the last packet still has to travel every wire once).
See it on a timeline
\(P = 3\) packets, \(N = 3\) links. One column = one \(L/R\) time slot.
| slot 1 | slot 2 | slot 3 | slot 4 | slot 5 | |
|---|---|---|---|---|---|
| link 1 | p1 | p2 | p3 | ||
| link 2 | p1 | p2 | p3 | ||
| link 3 | p1 | p2 | p3 |
p1 arrives at the end of slot 3 (\(= N\)). p2 and p3 follow one slot apart. The last one finishes at slot 5 \(= N + P - 1 = 3 + 3 - 1\) ✓
Worked example 1: HW1 P7
Q: 8×10⁶-bit message. Source → switch → switch → destination, so 3 links, each 2 Mbps. Ignore propagation, queuing and processing.
(a) No segmentation
One hop:
$$\frac{M}{R} = \frac{8 \times 10^6}{2 \times 10^6} = 4 \text{ s}$$Store-and-forward over 3 links:
$$T = 3 \times 4 = \mathbf{12 \text{ s}}$$(b) 800 packets of 10,000 bits each
First packet to the first switch:
$$\frac{L}{R} = \frac{10^4}{2 \times 10^6} = 0.005 \text{ s} = \mathbf{5 \text{ ms}}$$The 2nd packet is fully at switch 1 at \(2 \times 5 = \mathbf{10 \text{ ms}}\). That's the same moment the 1st packet is fully at switch 2.
(c) Total time with segmentation
$$T = (N + P - 1)\,\frac{L}{R} = (3 + 800 - 1) \times 5 \text{ ms} = 802 \times 5 \text{ ms} = 4010 \text{ ms} = \mathbf{4.01 \text{ s}}$$That's about 1/3 of the 12 s without segmentation, because all 3 links work at once.
(d) Other reasons to segment
- Bit errors: one bad bit means resending one small packet, not the whole message.
- Fairness: without segmentation, huge packets hog the routers and small packets get stuck queuing behind them.
(e) Drawbacks
- Packets must be put back in order at the destination.
- More header overhead: every packet carries its own header, so more total bits are sent.
Worked example 2: Sample midterm P2
Q: 8×10⁶-bit message, 4 intermediate routers, every link 1.6 Mbps, 10 users. Ignore propagation, queuing, setup and processing.
4 routers → \(N = 5\) links.
(a) No segmentation
$$\frac{M}{R} = \frac{8 \times 10^6}{1.6 \times 10^6} = 5 \text{ s per hop} \qquad T = 5 \times 5 = \mathbf{25 \text{ s}}$$(b) 5000 packets of 1600 bits + 160-bit header each
Packet size with header:
$$L = 1600 + 160 = 1760 \text{ bits}$$ $$\frac{L}{R} = \frac{1760}{1.6 \times 10^6} = 1.1 \times 10^{-3} \text{ s} = 1.1 \text{ ms}$$ $$T = (5 + 5000 - 1) \times 1.1 \text{ ms} = 5004 \times 1.1 \text{ ms} = 5504.4 \text{ ms} = \mathbf{5.5044 \text{ s}}$$Quick check
1. A path has 2 routers between source and destination. How many links?
3 links (routers + 1).2. 10⁶-bit message, 2 routers, every link 1 Mbps, no segmentation. Total time?
3 links. One hop = 10⁶ / 10⁶ = 1 s. Total = 3 × 1 = 3 s.3. Same message, now split into 100 packets of 10,000 bits (no header). Total time?
$$\frac{L}{R} = \frac{10^4}{10^6} = 10 \text{ ms} \qquad T = (3 + 100 - 1) \times 10 \text{ ms} = 102 \times 10 = \mathbf{1.02 \text{ s}}$$4. Same as #3, but each packet also has a 1000-bit header. Total time?
$$L = 11{,}000 \text{ bits} \quad \frac{L}{R} = 11 \text{ ms} \qquad T = 102 \times 11 \text{ ms} = \mathbf{1.122 \text{ s}}$$5. When does segmentation NOT reduce delay?
When there's only 1 link (no routers). Then \((1 + P - 1)\frac{L}{R} = P \cdot \frac{L}{R}\), which is just the whole message's transmission time, and headers make it slightly worse. The speedup comes only from the links working in parallel.6. Name one benefit (other than delay) and one drawback of segmentation.
Benefit: a bit error only costs resending one small packet (or: small packets don't get stuck behind huge ones).Drawback: packets must be reordered at the destination (or: more total header bits).