Chapter 5 Problems, Programming Assignments, Lab and Interview

Twenty-three review questions and twenty-two problems from the book, every one checkable in the browser. Then the ICMP (Internet Control Message Protocol) socket assignment, the distance-vector programming assignment, the Wireshark lab, and an interview with Jennifer Rexford.

How to use this page

Attempt before you look. A numeric part unlocks its solution when you answer it, or when you ask for it outright. That is deliberate.
The graph problems have their own widgets, below the exercises. Do the arithmetic first, then use them to mark it.
Every number here was computed, not copied. The P1 and P2 path counts come from the same exhaustive enumerator that verified Figure 5.3. The P5, P8 and P11 answers come from the same distance-vector simulator the section-5.2.2 widgets run.

Why this matters

Reading a routing algorithm and running one are different skills. The chapter’s widgets will step through Dijkstra or a distance-vector exchange for you, and watching is not the same as being able to do it.

These problems are where that gets tested. Several also go somewhere the chapter’s prose does not. P11 builds a three-node loop that poisoned reverse cannot see. P16 asks how one autonomous system can bend another’s routing from the outside. P18 shows an application defeating a routing policy entirely.

Review questions

Chapter 5 Review Questions

R1–R23, the book's own review questions. Answer before you look: a solution read too early is a solution not learned.

R1What is meant by a control plane that is based on per-router control? In such cases, when we say the network control and data planes are implemented "monolithically", what do we mean?
a.Per-router control means:
b.What does "monolithically" mean here?
R2What is meant by a control plane that is based on logically centralized control? In such cases, are the data plane and the control plane implemented within the same device or in separate devices?
a.In a logically centralized control plane:
b.Are the two planes in the same device?
R3Compare and contrast the properties of a centralized and a distributed routing algorithm. Give an example of a routing protocol that takes a centralized and a decentralized approach.
a.A centralized routing algorithm is one that:
b.Examples of each:
R4Compare and contrast link-state and distance-vector routing algorithms.
Give the contrast in terms of what each node knows, what it sends, and to whom.
R5What is the "count to infinity" problem in distance vector routing?
Describe it.
R6Is it necessary that every autonomous system use the same intra-AS routing algorithm?
Must every AS use the same intra-AS routing algorithm?
R7Why are different inter-AS and intra-AS protocols used in the Internet?
Give the book's three reasons.
R8True or false: when an OSPF router sends its link-state information, it is sent only to those nodes directly attached neighbours.
True or false?
R9What is meant by an area in an OSPF autonomous system? Why was the concept of an area introduced?
Define it, and say why it exists.
R10Define and contrast the following terms: subnet, prefix, and BGP route.
Define all three and say how they differ.
R11How does BGP use the NEXT-HOP attribute? How does it use the AS-PATH attribute?
a.NEXT-HOP is:
b.AS-PATH is used for two things. Which?
R12Describe how a network administrator of an upper-tier ISP can implement policy when configuring BGP.
How is policy actually enforced?
R13True or false: when a BGP router receives an advertised path from its neighbour, it must add its own identity to the received path and then send that new path on to all of its neighbours.
True or false?
R14Describe the main role of the communication layer, the network-wide state-management layer, and the network-control application layer in an SDN controller.
Give one sentence for each, bottom-up.
R15Suppose you wanted to implement a new routing protocol in the SDN control plane. At which layer would you implement it?
Which layer?
R16What types of messages flow across an SDN controller's northbound and southbound APIs? Who receives messages sent from the controller across the southbound interface, and who sends messages to the controller across the northbound interface?
Answer all four parts.
R17Describe the purpose of two OpenFlow messages sent from a controlled device to the controller, and two sent from the controller to a controlled device.
a.Which pair travels UP, from switch to controller?
b.Describe two messages the controller sends down.
R18What is the purpose of the service abstraction layer in the OpenDaylight SDN controller?
What does the SAL do?
R19Name four different types of ICMP message.
a.Which set is drawn entirely from Figure 5.19?
b.Name four, with type and code.
R20What two types of ICMP message are received at the sending host executing the Traceroute program?
Which two?
R21Define the following terms in the context of SNMP: managing server, managed device, network management agent and MIB.
Define all four.
R22What are the purposes of the SNMP GetRequest and SetRequest messages?
a.GetRequest:
b.SetRequest:
R23What is the purpose of the SNMP trap message?
What is a trap, and how does it differ from everything else in SNMP?

Problems

Chapter 5 Problems

P1–P22. Numeric answers are checked in the browser; every solution is worked in full. The graph problems reuse the same simulators the chapter's own widgets run, so the answers here and the answers there cannot disagree.

P1Looking at Figure 5.3, enumerate the paths from y to u that do not contain any loops.
Figure 5.3's graph: c(u,v)=2, c(u,x)=1, c(u,w)=5, c(v,x)=2, c(v,w)=3, c(x,w)=3, c(x,y)=1, c(w,y)=1, c(w,z)=5, c(y,z)=2.
How many loop-free paths are there from y to u?
paths
P2Repeat Problem P1 for paths from x to z, from z to u, and from z to w.
Figure 5.3's graph: c(u,v)=2, c(u,x)=1, c(u,w)=5, c(v,x)=2, c(v,w)=3, c(x,w)=3, c(x,y)=1, c(w,y)=1, c(w,z)=5, c(y,z)=2.
a.Loop-free paths from x to z:
paths
b.Loop-free paths from z to u:
paths
c.Loop-free paths from z to w:
paths
P3Use Dijkstra's algorithm to compute the shortest path from x to all network nodes, showing a table like Table 5.1.
The P3 network: c(z,x)=8, c(z,y)=12, c(y,t)=7, c(y,x)=6, c(y,v)=8, c(x,v)=3, c(x,w)=6, c(v,t)=4, c(v,u)=3, c(v,w)=4, c(t,u)=2, c(w,u)=3. Seven nodes: t, u, v, w, x, y, z.
a.Least cost from x to v:
b.Least cost from x to u:
c.Least cost from x to w:
d.Least cost from x to y:
e.Least cost from x to t:
f.Least cost from x to z:
g.Give x's forwarding table, and note where the iteration table depends on a tie-break.
P4Using Dijkstra's algorithm on the P3 network, compute the shortest path from t, u, v, w, y and z to all network nodes.
The P3 network: c(z,x)=8, c(z,y)=12, c(y,t)=7, c(y,x)=6, c(y,v)=8, c(x,v)=3, c(x,w)=6, c(v,t)=4, c(v,u)=3, c(v,w)=4, c(t,u)=2, c(w,u)=3. Seven nodes: t, u, v, w, x, y, z.
a.From t: least cost to x:
b.From u: least cost to y:
c.From v: least cost to z:
d.From w: least cost to y:
e.From y: least cost to u:
f.From z: least cost to u:
g.Give the full table of least costs from every source.
P5Consider the distance-vector algorithm on the network below, and show the distance table entries at node z.
The P5 network: c(u,v)=1, c(u,y)=2, c(v,x)=3, c(v,z)=6, c(y,x)=3, c(x,z)=2. Each node initially knows only the costs to its own neighbours.
a.z's final least cost to x:
b.z's final least cost to v:
c.z's final least cost to y:
d.z's final least cost to u:
e.Show z's distance table as it evolves.
P6Consider a general topology and a synchronous version of the distance-vector algorithm, where each node exchanges vectors with its neighbours at each iteration. Beginning with each node knowing only its immediate neighbours' costs, what is the maximum number of iterations required before the algorithm converges?
Give the bound and justify it.
P7x has only two attached neighbours, w and y. w has a minimum-cost path to destination u of 5, and y has one of 6.
x has exactly two neighbours, w and y, with c(x,w)=2 and c(x,y)=5, and c(w,y)=2. w's minimum cost to destination u is 5; y's is 6. All link costs are strictly positive integers.
a.x's distance to w:
b.x's distance to y:
c.x's distance to u:
d.Give a link-cost change that WILL make x tell its neighbours about a new minimum-cost path to u.
e.Give a link-cost change that will NOT.
P8Consider the three-node topology of Figure 5.6, but with link costs c(x,y) = 3, c(y,z) = 6, c(z,x) = 4. Compute the distance tables after initialization and after each iteration of the synchronous distance-vector algorithm.
a.How many columns does the figure need — the initial one plus how many more?
columns
b.Write out the tables.
P9Will the count-to-infinity problem occur if we decrease the cost of a link? How about if we connect two nodes which do not have a link?
a.Decreasing a link cost:
b.Connecting two nodes that had no link:
P10Argue that for the distance-vector algorithm in Figure 5.6, each value in the distance vector D(x) is non-increasing and will eventually stabilize in a finite number of steps.
Give the argument.
P11Consider Figure 5.7 with another router w connected to routers y and z, with poisoned reverse in use.
Figure 5.7 with an extra router w connected to y and z. Costs: c(x,y)=4, c(x,z)=50, c(y,w)=1, c(z,w)=1, c(y,z)=3. Poisoned reverse is in use.
a.When the routing has stabilized, what distance to x does y report to its neighbours?
b.What distance to x does w report to z?
c.What distance to x does z report to y?
d.c(x,y) now increases to 60. Is there a count-to-infinity problem even with poisoned reverse?
e.How many message exchanges before it stabilizes again, and what are the final values?
f.How large must c(y,z) be so that no count-to-infinity happens at all when c(y,x) goes from 4 to 60?
P12Describe how loops in paths can be detected in BGP.
How?
P13Will a BGP router always choose the loop-free route with the shortest AS-PATH length?
Always?
P14Router 3c, 3a, 1c and 1d each learn about prefix x. From which routing protocol does each learn it: OSPF, RIP, eBGP or iBGP?
Four autonomous systems. AS4 holds prefix x, attached to router 4a. Links between systems: 3c–4c joins AS3 and AS4; 3a–1c joins AS3 and AS1; 1b–2a joins AS1 and AS2. AS3 and AS2 run OSPF internally; AS1 and AS4 run RIP. Initially there is no link between AS2 and AS4.
a.Router 3c learns about x from:
b.Router 3a learns about x from:
c.Router 1c learns about x from:
d.Router 1d learns about x from:
e.What pattern do the four answers show?
P15Once router 1d learns about x it puts an entry (x, I) in its forwarding table. Will I be I₁ or I₂?
Router 1d has two interfaces: I₁ leading toward 1a and I₂ leading toward 1b.
a.With no link between AS2 and AS4:
b.Now suppose there is a physical link between AS2 and AS4, and 1d learns that x is reachable via AS2 as well as via AS3.
c.And now suppose another AS, AS5, lies between AS2 and AS4.
P16ISP B provides national backbone service to regional ISP A; ISP C provides it to regional ISP D. B and C peer in two places. B would prefer to hand A-to-D traffic to C on the West Coast, so that C carries it across the country; C would prefer to receive it at the East Coast peering point. What BGP mechanism might C use so that B hands the traffic over on the East Coast?
What can C do?
P17In Figure 5.13, consider the path information that reaches stub networks W, X and Y. Based on the information available at W and X, what are their respective views of the network topology?
What does W see, and what does X see?
P18In Figure 5.13, B would never forward traffic destined to Y via X, based on BGP routing. But there are popular applications for which data packets go to X first and then flow to Y. Identify one such application.
a.Which kind of application does this?
b.Explain how the packets take a path BGP never chose.
P19In Figure 5.13, suppose there is another stub network V that is a customer of ISP A. B and C have a peering relationship, and A is a customer of both B and C. A would like traffic destined to W to come from B only, and traffic destined to V from either B or C. How should A advertise its routes?
What should A advertise, and to whom? And what does C receive?
P20Suppose ASs X and Z are not directly connected but are connected by AS Y. X has a peering agreement with Y, and Y has a peering agreement with Z. Z wants to transit all of Y's traffic but does not want to transit X's traffic. Does BGP allow Z to implement this policy?
a.Does BGP allow it?
b.Say precisely what Z does.
P21Consider the two ways communication occurs between a managing entity and a managed device: request-response mode and trapping. What are the pros and cons in terms of (1) overhead, (2) notification time when exceptional events occur, and (3) robustness with respect to lost messages?
Compare them on all three.
P22We saw that it was preferable to transport SNMP messages in unreliable UDP datagrams. Why do you think the designers of SNMP chose UDP rather than TCP?
Give the reasons.

The graph problems, marked

P3 and P4 · Dijkstra on a seven-node network

P3 and P4 — the network, with Dijkstra running on it

sourcestep 0 of 6

Initialization. N′, the solved set, holds only the source x. Every neighbour of x gets D = the cost of the direct link. Every other node gets ∞.

The iteration table. Each row is the state at the end of that step; a blank cell means the value can no longer change, because the node is already in N′.
step	N′	D(z), p(z)	D(y), p(y)	D(t), p(t)	D(v), p(v)	D(u), p(u)	D(w), p(w)
0	x	8, x	6, x	∞	3, x	∞	6, x

This run contains a tie. Tick break ties the other way and step through again: the order the nodes enter N′ changes, and every final least cost stays the same.

P3 asks for the run from x. P4 asks for the run from each of the other six nodes — change the source and step through. Do the arithmetic yourself first; this is here to mark your work, not to do it.

The tie P3 hides

After v joins N′, three nodes sit at cost 6 together: u, w and y. Any of them may be added next. This is the count-to-infinity problem’s opposite: a tie that costs nothing.

The book’s own instruction, from section 5.2.1, is to break such a tie arbitrarily. The widget’s tie-break control lets you see what “arbitrarily” costs. The order the three enter N′ changes; not one final least cost does.

If your table has the rows in a different order from someone else’s, you are both right.

P5 · a distance-vector run

P5 — the distance-vector run, node by node

step 0 of 3

Initialization. Each node knows only the cost of its own links. Its own row holds those costs, and ∞ for every node it is not attached to. The rows for its neighbours are all ∞, because nothing has arrived yet. Then everyone sends.

Node u table

initial · cost to
	u	v	z	y	x
u	0	1	∞	2	∞
v	∞	∞	∞	∞	∞
y	∞	∞	∞	∞	∞

Node v table

initial · cost to
	u	v	z	y	x
u	∞	∞	∞	∞	∞
v	1	0	6	∞	3
z	∞	∞	∞	∞	∞
x	∞	∞	∞	∞	∞

Node z table

initial · cost to
	u	v	z	y	x
v	∞	∞	∞	∞	∞
z	∞	6	0	∞	2
x	∞	∞	∞	∞	∞

Node y table

initial · cost to
	u	v	z	y	x
u	∞	∞	∞	∞	∞
y	2	∞	∞	0	3
x	∞	∞	∞	∞	∞

Node x table

initial · cost to
	u	v	z	y	x
v	∞	∞	∞	∞	∞
z	∞	∞	∞	∞	∞
y	∞	∞	∞	∞	∞
x	∞	3	2	3	0

Each table holds three rows: the node's own distance vector, in blue and bold, and the last vector it received from each neighbour. A value in amber changed in this round.

The problem asks only for node z’s table. All five are shown, because seeing which of the others changed in the same round explains why z’s entry moved when it did.

The problem asks for node z’s table. Watch the entry for v: it starts at 6, the direct link, and drops to 5 once x reports that it can reach v for 3. z’s own 6-cost link to v is then never used again.

P11 · a loop poisoned reverse cannot see

P11 — count-to-infinity in a three-node loop, with poisoned reverse on

messages sent: 0step 0 of 61

t0. Before the change. Every estimate has settled and no messages are moving.

t	node	Dy(x)	Dw(x)	Dz(x)	sends
0	—	4 via x	5 via y	6 via w	—

Press Play. The estimates climb by 5 every three messages, and the arrows stay red the whole way — poisoned reverse cannot see a loop that runs y → z → w → y. Sixty messages before it settles.

Sixty messages. The estimates climb 9, 10, 11, then 14, 15, 16, then 19, 20, 21, rising by 5 every three messages. It ends when z’s trip round the loop finally costs more than its own direct 50-cost link to x.

Poisoned reverse is switched on the whole time. It fails because each node lies only to the neighbour it routes through, and no node in a three-way cycle knows it is on one.

P11(c) — the same failure with c(y,z) raised to 54

messages sent: 0step 0 of 11

t0. Before the change. Every estimate has settled and no messages are moving.

t	node	Dy(x)	Dw(x)	Dz(x)	sends
0	—	4 via x	5 via y	6 via w	—

One link cost changed, and the loop never forms: y prefers its own 60-cost link to 54 + 6. Ten messages instead of sixty, and no red arrows at all. Try 53 by hand and the count comes back.

Part (c) asks how to prevent it. The answer is a cost, not a protocol: at the instant c(y,x) becomes 60, y computes

D_y(x) = min{ 60 + 0, c(y,z) + 6, 1 + ∞ }

— the last term being ∞ because poisoned reverse makes w report ∞ to y. For y to keep its own direct link and stay out of the loop, c(y,z) + 6 ≥ 60, so c(y,z) ≥ 54.

Why that fix should make you uncomfortable

It works, and it is fragile. It depends on one link cost being large enough relative to another, in a network nobody will remember tuning in five years.

The real answer to count-to-infinity is not a cost setting. It is BGP (Border Gateway Protocol) ‘s AS-PATH: carry the path itself, and a loop becomes something a router can see rather than something the numbers happen to make unattractive.

Socket programming assignment 5 · ICMP ping

The book’s fifth socket assignment asks you to write ping in Python, using ICMP (Internet Control Message Protocol) directly. Only the client is needed: the server side is built into almost all operating systems, as section 5.6 explained — there is no process listening.

Three things make this assignment different from the four in chapter 2.

There is no socket in the ordinary sense. ICMP has no ports, so you cannot bind one. You open a raw socket, which on most systems needs administrator privileges. That is the same point the book makes when it says the client must be able to instruct the operating system to generate a type 8 code 0 message.

You build the header yourself. No library fills in the type, the code or the checksum.

You measure time, not correctness. The program’s output is a round-trip time, a loss count, and a statistical summary — minimum, mean, maximum and standard deviation over several exchanges.

import os, socket, struct, sys, time

ICMP_ECHO_REQUEST = 8            # section 5.6, Figure 5.19
ICMP_ECHO_REPLY   = 0


def checksum(data: bytes) -> int:
    """The Internet checksum, as in section 3.3 — but over the ICMP message
    alone. ICMP has no pseudo-header, because it has no ports to protect."""
    total = 0
    for i in range(0, len(data) - 1, 2):
        total += (data[i] << 8) + data[i + 1]
        total = (total & 0xFFFF) + (total >> 16)
    if len(data) % 2:                     # a final odd byte, left-aligned
        total += data[-1] << 8
        total = (total & 0xFFFF) + (total >> 16)
    return ~total & 0xFFFF


def build_request(ident: int, seq: int) -> bytes:
    payload = struct.pack('!d', time.time())      # send the clock with it
    # type, code, checksum=0, identifier, sequence
    header = struct.pack('!BBHHH', ICMP_ECHO_REQUEST, 0, 0, ident, seq)
    ck = checksum(header + payload)
    return struct.pack('!BBHHH', ICMP_ECHO_REQUEST, 0, ck, ident, seq) + payload


def ping_once(sock, dest: str, ident: int, seq: int, timeout=1.0):
    sock.sendto(build_request(ident, seq), (dest, 0))
    sock.settimeout(timeout)
    try:
        packet, _ = sock.recvfrom(1024)
    except socket.timeout:
        return None                                # counted as a loss

    ip_header_len = (packet[0] & 0x0F) * 4         # IHL, in 4-byte words
    icmp = packet[ip_header_len:]
    r_type, _, _, r_ident, r_seq = struct.unpack('!BBHHH', icmp[:8])
    if r_type != ICMP_ECHO_REPLY or r_ident != ident:
        return None                                # somebody else's reply
    sent_at, = struct.unpack('!d', icmp[8:16])
    return (time.time() - sent_at) * 1000.0        # milliseconds


def main(dest: str, count: int = 4):
    ident = os.getpid() & 0xFFFF
    sock = socket.socket(socket.AF_INET, socket.SOCK_RAW,
                         socket.getprotobyname('icmp'))
    rtts = []
    for seq in range(1, count + 1):
        rtt = ping_once(sock, dest, ident, seq)
        if rtt is None:
            print(f'seq={seq}  request timed out')
        else:
            rtts.append(rtt)
            print(f'seq={seq}  time={rtt:.1f} ms')
        time.sleep(1)

    lost = count - len(rtts)
    print(f'\n{count} sent, {len(rtts)} received, {100 * lost / count:.0f}% loss')
    if rtts:
        mean = sum(rtts) / len(rtts)
        sd = (sum((r - mean) ** 2 for r in rtts) / len(rtts)) ** 0.5
        print(f'min {min(rtts):.1f} / avg {mean:.1f} / max {max(rtts):.1f} '
              f'/ stddev {sd:.1f} ms')


if __name__ == '__main__':
    main(sys.argv[1] if len(sys.argv) > 1 else '127.0.0.1')

Expected output

Run against the running example’s server, whose round trip is 180 ms:

$ sudo python3 ping.py 198.51.100.7
seq=1  time=181.4 ms
seq=2  time=179.8 ms
seq=3  request timed out
seq=4  time=180.2 ms

4 sent, 3 received, 25% loss
min 179.8 / avg 180.5 / max 181.4 / stddev 0.7 ms

Four details in that output are worth connecting to section 5.6.

sudo. A raw socket is privileged, because an unprivileged program that could forge ICMP could forge anything.

The identifier. os.getpid() gives each running copy its own value, and the reply copies it back unchanged, so two pings on one machine do not steal each other’s replies.

Stripping the IP (Internet Protocol) header. A raw socket hands you the whole datagram, so the code reads the IHL field to find where the ICMP message starts. The capture on the §5.6 page shows exactly the bytes this line is skipping.

The timestamp travels in the payload. The reply echoes every data byte back unchanged, so the sender can read its own send time out of the reply rather than keeping a table.

Programming assignment · distributed distance-vector routing

The chapter’s larger assignment asks for a distributed, asynchronous distance-vector computation over four nodes, written as eight procedures: rtinit0() … rtinit3() and rtupdate0() … rtupdate3().

The network is four nodes with these costs:

Link	Cost
0 – 1	1
0 – 2	3
0 – 3	7
1 – 2	1
2 – 3	2

rtinit0() runs once. It fills node 0’s distance table with the direct costs 1, 3 and 7 to nodes 1, 2 and 3. It then sends its minimum costs to its directly connected neighbours by calling tolayer2().

rtupdate0(struct rtpkt *rcvdpkt) runs whenever a routing packet arrives from a neighbour. It is the heart of the algorithm. Apply the received vector to line 14 of section 5.2.2’s pseudocode. Then, if and only if one of node 0’s own minimum costs changed, send the new vector to its neighbours.

Work out the answer before you write the code

The true least costs, which your program must converge to:

from ↓ to →	0	1	2	3
0	0	1	2	4
1	1	0	1	3
2	2	1	0	2
3	4	3	2	0

Two entries are worth checking by hand, because they are the ones that move.

D₀(2) = 2, not 3. The direct link costs 3, but 0 → 1 → 2 costs 1 + 1 = 2.

D₀(3) = 4, not 7. The direct link costs 7, but 0 → 1 → 2 → 3 costs 1 + 1 + 2 = 4. Node 0’s 7-cost link is never used, and neither is its 3-cost one.

So if your implementation ever settles with node 0 believing 3 or 7, it is applying line 14 to its own link costs only and ignoring what its neighbours reported.

One trap the assignment sets. Nodes 1 and 3 are not connected, so rtupdate1() will never receive a packet from node 3. Only directly connected nodes exchange routing packets — that is the definition of the algorithm, and the simulator enforces it.

Wireshark lab · ICMP

The book’s lab examines ICMP as used by ping and traceroute. The site cannot run Wireshark, so here is the same run as a capture, taken on Lin’s laptop.

Wireshark lab — ICMP in ping and traceroute

No.	Time	Source	Destination	Protocol	Length	Info
1	0.000000	192.168.1.24	198.51.100.7	UDP	54	45678 → 33434 Len=12 [TTL=1]
2	0.001000	192.168.1.1	192.168.1.24	ICMP	70	Time-to-live exceeded (type 11, code 0) ← hop 1: home router / access point
3	0.005000	192.168.1.24	198.51.100.7	UDP	54	45678 → 33435 Len=12 [TTL=2]
4	0.014000	41.72.10.1	192.168.1.24	ICMP	70	Time-to-live exceeded (type 11, code 0) ← hop 2: ISP-A, Bangkok
5	0.018000	192.168.1.24	198.51.100.7	UDP	54	45678 → 33436 Len=12 [TTL=3]
6	0.114000	203.0.113.1	192.168.1.24	ICMP	70	Time-to-live exceeded (type 11, code 0) ← hop 3: Tier-1-T, transit backbone
7	0.118000	192.168.1.24	198.51.100.7	UDP	54	45678 → 33437 Len=12 [TTL=4]
8	0.296000	192.0.2.1	192.168.1.24	ICMP	70	Time-to-live exceeded (type 11, code 0) ← hop 4: university border router
9	0.300000	192.168.1.24	198.51.100.7	UDP	54	45678 → 33438 Len=12 [TTL=5]
10	0.480000	198.51.100.7	192.168.1.24	ICMP	70	Destination port unreachable (type 3, code 3) ← the destination host
11	0.500000	192.168.1.24	198.51.100.7	ICMP	74	Echo (ping) request (type 8, code 0) id=0x1a2b seq=1
12	0.680000	198.51.100.7	192.168.1.24	ICMP	74	Echo (ping) reply (type 0, code 0) id=0x1a2b seq=1

Packet 1 — Traceroute probe 1. An ordinary UDP datagram to an unlikely port, with the time-to-live set by hand to 1.

Protocol tree — click a field

The actual bytes

0000  aa bb cc 00 00 01 aa bb  cc 00 00 11 08 00 45 00  ..............E.
0010  00 28 2b 10 00 00 01 11  a2 ba c0 a8 01 18 c6 33  .(+............3
0020  64 07 b2 6e 82 9a 00 14  3f 1c 40 41 42 43 44 45  d..n....?.@ABCDE
0030  46 47 48 49 4a 4b                                FGHIJK

Captured on Lin’s laptop. Five probes with rising time-to-live, four routers reporting themselves, the destination host refusing the port, and then a single ping. One probe per hop; the real program sends three.

Lab tasks — answer them from the capture above

What is the IP protocol number of every ICMP packet here, and what does a host do with it? Select any ICMP packet and open its IPv4 (Internet Protocol version 4) layer.
Are the traceroute probes ICMP messages? Look at packet 1. What protocol is it, and what makes it a traceroute probe rather than an ordinary datagram?
How does the time-to-live change across packets 1, 3, 5, 7 and 9? Click the TTL (Time To Live) field in each.
The four time-exceeded replies come from four different source addresses. Why does that matter? It is the entire output of the program.
Select packet 2 and click “quoted IP header of the datagram that caused this”. Twenty bytes highlight in the hex pane. Compare them with packet 1’s IPv4 header. Then click the next field, the quoted first 8 bytes, and find the port numbers packet 1 used.
Why does the last reply have a different type and code from the first four? What would traceroute do if it never arrived?
The ping pair, packets 11 and 12. What is copied unchanged from the request into the reply, and what is it for?

Every one of these is answerable from the bytes on screen. If an answer is not visible in the hex pane, you have not found the right field.

An interview with Jennifer Rexford

Voices from the field

Jennifer Rexford is a Professor of Computer Science at Princeton University. Her research aims to make computer networks easier to design and manage, with particular emphasis on programmable networks. From 1996 to 2004 she was in the Network Management and Performance department at AT&T Labs–Research, where she designed measurement, traffic-engineering and router-configuration tools that were deployed in AT&T’s backbone. She chaired ACM SIGCOMM from 2003 to 2007. Her awards include ACM’s Grace Murray Hopper Award, the ACM Athena Lecturer Award, the ACM SIGCOMM lifetime contributions award and the IEEE (Institute of Electrical and Electronics Engineers) Internet Award.

On the project she found most exciting. At AT&T her group designed a new way to manage routing in ISP (Internet Service Provider) backbones. Traditionally operators configure each router individually and the routers run distributed protocols to compute paths. Her group believed management would be simpler and more flexible if operators could control forwarding directly, from a network-wide view of topology and traffic. The Routing Control Platform they built could compute the routes for all of AT&T’s backbone on a single commodity computer, and could control unmodified legacy routers. What made it exciting, she says, was having a provocative idea, a working system, and ultimately a real deployment. A few years later SDN (Software-Defined Networking) became mainstream.

On where SDN should go next. The software controlling network devices can now be written by many different programmers, not only by the companies selling the equipment. But unlike applications on a server, SDN applications must work together on the same traffic. An operator does not want load balancing on some traffic and routing on other traffic, but both, together, on all of it. Future platforms should offer good abstractions for composing independently written applications. They should also offer abstractions for updating a distributed set of devices, so administrators can reason about packets in flight during the update.

On the future of networking. The field keeps reinventing itself: smartphones, cloud computing, networked sensors and actuators. And yet, she says, the network is notoriously “in the way” — limiting performance, compromising reliability, constraining applications. We should strive to make the network of the future as invisible as the air we breathe, so it never stands in the way of new ideas. Doing that means raising the level of abstraction above individual devices and protocols.

On who inspired her. Sally Floyd, of the International Computer Science Institute. Her research was always purposeful, and she dug deeply into hard questions until she understood both the problem and the space of solutions. She pushed her ideas into protocol standards and network equipment. She also gave back by building tools, including the widely used ns-2 and ns-3 simulators, that let other researchers succeed. She retired in 2009 and died in 2019.

What these problems are really testing

P5–P11 — that a distance vector is an estimate, that estimates only fall while costs are fixed, and that the whole difficulty starts the moment one rises. Poisoned reverse fixes two-node loops and nothing longer.
P12–P16 — that BGP’s four rules run in order, and that policy is enforced by choosing what not to advertise.
P21–P22 — that polling and trapping trade overhead against notification time against robustness, and that SNMP (Simple Network Management Protocol) chose UDP (User Datagram Protocol) because management traffic must work when the network does not.