# 23 Selected Solutions¶

In this chapter we present solutions (in some cases partial solutions) to exercises marked with a ♢.

## 23.1 Solutions for *An Overview of Networks*¶

**Exercise 2.7**

A | |
---|---|

B,C,D | direct |

E | D (or C) |

B | |
---|---|

A,C | direct |

D | A |

E | C |

C | |
---|---|

A,B,E | direct |

D | E (or A) |

D | |
---|---|

A,E | direct |

B | A |

C | E (or A) |

E | |
---|---|

C,D | direct |

A | C (or D) |

B | C |

**Exercise 7.0(d)** (destination D):

The path from S1 to D is thus S1–S2–S5–S6–S12.

**Exercise 7.5(a)**

The shortest path from A to F is A–S1–1–S2–2–S5–1–S6–F, for a total cost of 1+2+1 = 4.

## 23.2 Solutions for *Ethernet*¶

**Exercise 2.7**

switch | known destinations |
---|---|

S1 | AD |

S2 | ABD |

S3 | A |

S4 | AB |

**Exercise 8.5**

The path from S2 to S5 is S2–S3–S1–S5.

**Exercise 12.0**

*not*reported to C, as destination h1

*is*known by S. The packet is not flooded.

- h2→h3: this packet is reported to C, as destination h3 is not known by S. C installs on S the rule that h2 can be reached via port 2. The packet is then flooded.

**Exercise 13.0**

Table for S1 only:

S1’s table ends up with forwarding entries for h1 and h2, but not h3.

## 23.3 Solutions for *Other LANs*¶

**Exercise 3(b)**

One simple strategy is for stations to compare themselves to one another according to the numeric value of their MAC addresses. The station with the smallest MAC address becomes S_{0}, the station with the next-smallest address becomes S_{1}, etc.

**Exercise 4.5**

The three sending nodes can be laid out at the vertices of an equilateral triangle, with the receiving node in the center. Alternatively, with impermeable walls the following arrangement works:

```
sender1
───────────
receiver sender2
───────────
sender1
```

The latter arrangement generalizes to almost any number of senders. For the former, senders can be laid out at the vertices of a square, or tetrahedron, or possibly a pentagon, but geometry enforces an eventual limit.

**Exercise 5(b)**

If T is the length of the contention interval, in µsec, then transmission and contention alternate with lengths 151–T–151–T–.... The fraction of bandwidth lost to contention is T/(T+151).

**Exercise 10.5**

The connections are as follows, where the VCI number is shown between the endpoints of each link:

A–1–S1–2–S2–3–S4–2–DB–1–S2–2–S4–1–S3–3–S1–2–A

## 23.4 Solutions for *Links*¶

**Exercise 3.5**

The binary ASCII for the three letters is

N | 0100 1110 |

e | 0110 0101 |

t | 0111 0100 |

If we look up the 4-bit “nybbles” in the right column above in the 4B/5B table at 4.1.4 4B/5B, we get

data | symbol |
---|---|

0100 | 01010 |

1110 | 11100 |

0110 | 01110 |

0101 | 01011 |

0111 | 01111 |

0100 | 01010 |

Putting all these symbols together, the encoding is (with spaces added for readability)

## 23.5 Solutions for *Packets*¶

**Exercise 3**

T=0 | A begins sending the packet |

T=300 | A finishes sending the packet |

T=600 | S begins receiving the packet |

T=900 | S finishes receiving the packet and begins sending to B |

T=1200 | S finishes sending the packet |

T=1500 | B begins receiving the packet |

T=1800 | B finishes receiving the packet |

T=0 | A begins sending packet 1 |

T=150 | A finishes sending packet 1, starts on packet 2 |

T=300 | A finishes sending packet 2 |

T=600 | S begins receiving packet 1 |

T=750 | S finishes receiving packet 1 and begins sending it to B |

S begins receiving packet 2 | |

T=900 | S finishes receiving packet 2 and begins sending it to B |

T=1350 | B begins receiving packet 1 |

T=1500 | B has received all of packet 1 and starts receiving packet 2 |

T=1650 | B finishes receiving packet 2 |

Here’s the data for (b) in ladder-diagram format (not quite to scale):

The long propagation delay means that A finishes all transmissions before S begins receiving anything, and S finishes all transmissions before B begins receiving anything. With a smaller propagation delay, these A/S/B events are likely to overlap.

**Exercise 15(a)**

The received data is 10100010 and the received code bits are 0111. We first calculate the four code bits for the received data:

1: parity over all bits
1: parity over second half: 1010**0010**
0: parity over these bits: 10**10**00**10**
0: parity over these bits: 1**0**1**0**0**0**1**0**

So the incorrect received code bits are **0**1**11**.

The first bit of the received code tells us that the error is in the data (rather than the code bits). The second – correct – bit of the received code tells us that the error is in the first half, that is, in the non-bold bits of 1010**0010**.

The third bit of the received code tells us that the error is in the bold bits of 10**10**00**10**, so we’re down to the third or fourth bit. Finally, the fourth bit of the received code tells us the error is in the bold bits of 1**0**1**0**0**0**1**0**, which means the fourth bit is it, and the corrected data is 101**1**0010 (making the data the same as that in the example in 5.4.2.1 Hamming Codes).

## 23.6 Solutions for *Sliding Windows*¶

**Exercise 2.5**

The network is

_{noLoad}. We know winsize = 6, bandwidth = 1 packet/sec and RTT

_{noLoad}= 4, so this works out to 2 packets in the queue.

**The window slides forward by one**, from [1-6] to [2-7], and C sends new packet 7, which instantly arrives at S1 and is placed in the queue there.

Here is the table. The column “S1→S2” is the data packet S1 is currently sending to S2; the column “S2→S1” is the ACK that S2 is currently sending to S1; similarly for “S2→D” and “D→S2”.

T | C sends | S1 queues | S1→S2 | S2→D | ACK D→S2 | S2→S1 |
---|---|---|---|---|---|---|

0 | 1,2,3,4,5,6 | 2,3,4,5,6 | 1 | |||

1 | 3,4,5,6 | 2 | 1 | |||

2 | 4,5,6 | 3 | 2 | 1 | ||

3 | 5,6 | 4 | 3 | 2 | 1 | |

4 | 7 | 6,7 | 5 | 4 | 3 | 2 |

5 | 8 | 7,8 | 6 | 5 | 4 | 3 |

6 | 9 | 8,9 | 7 | 6 | 5 | 4 |

7 | 10 | 9,10 | 8 | 7 | 6 | 5 |

8 | 11 | 10,11 | 9 | 8 | 7 | 6 |

**Exercise 7.5**

_{noLoad}= 1000 pkts/sec × 0.1 sec = 100 packets.

_{actual}− RTT

_{noLoad}) = 1 pkt/ms × (130ms − 100ms) = 30 packets.

_{actual}= winsize / bandwidth = (100+50)/(1 pkt/ms) = 150 ms.

**Exercise 9.0**

If Data[8] is in the receiver’s window, then Data[4] must have been received. For the sender to have sent Data[4] it must have previously received ACK[0]. Therefore, all transmissions of Data[0] must precede the first transmission of Data[4], and so must precede the first successful transmission of Data[4]. Because of non-reordering, no Data[0] can arrive after Data[4].

## 23.7 Solutions for *IPv4*¶

**Exercise 4.0**

Forwarding table for A:

destination | next_hop |
---|---|

200.0.5.0/24 | direct |

200.0.6.0/24 | direct |

default | B |

**Exercise 6.0(d)**

The subnet prefix is 10.0.168.0/21. The /21 means that the prefix consists of the first two bytes (16 bits) and the first 5 (=21-16) bits of the third byte.

Expressing the third byte, 168, in binary, we get 10101|000.

We now convert the third byte of each of the four addresses to binary, and see which match this to the first five bits. Bits after the “|” mark are ignored.

10.0.166.1: 166 = 10100|110; not a match10.0.170.3: 170 = 10101|010; this is a match10.0.174.5: 174 = 10101|110; this is a match10.0.177.7: 177 = 10110|001; not a match

**Exercise 6.5**

## 23.8 Solutions for *Routing-Update Algorithms*¶

**Exercise 2.5**

For destination A, R1’s report is likely the same as it sent earlier, when R’s route to A was first established. There is no change.

For destination B, R’s total distance using R1 would be 2+1 = 3. This is tied with R’s route to B using next_hop R2, and so there is no change.

For destination C, R1 is reporting an increase in cost. R’s next_hop to C is R1, and so R must increase its cost to C to 4+1 = 5.

For destination D, R’s total cost using R1 is 3+1 = 4, cheaper than R’s previous cost of 5 using next_hop R3. R changes to the R1 route.

The updated table is

destination | cost | next hop | |
---|---|---|---|

A | 2 | R1 | no change; same next_hop |

B | 3 | R2 | no change; tie |

C | 5 | R1 | source increase |

D | 4 | R1 | lower-cost route found |

## 23.9 Solutions for *Large-Scale IP Routing*¶

**Exercise 0.5**

**Exercise 5(a)**

P’s table

destination | next hop |
---|---|

52.0.0.0/8 | Q |

53.0.0.0/8 | R |

51.10.0.0/16 | A |

51.23.0.0/16 | B |

Q’s table

destination | next hop |
---|---|

51.0.0.0/8 | P |

53.0.0.0/8 | R |

52.14.0.0/16 | C |

52.15.0.0/16 | D |

R’s table

destination | next hop |
---|---|

51.0.0.0/8 | P |

52.0.0.0/8 | Q |

**Exercise 7(a)**

P will receive a route from Q with AS-path (Q,S), and a route from R with AS-path (R,S).

## 23.10 Solutions for *TCP Reno*¶

**Exercise 12.5(b)**

Let *t* be the transit capacity; then the total `cwnd`

_{max} is *t*(1+*f*). At this point it is convenient to normalize the units of capacity measurement so *t*(1+*f*) = 2. Then the link-unsaturated and queue-filling phases have lengths in the proportion *t*−1 to *ft*. The average height of the tooth during the link-unsaturated phase is (*t*+1)/2, and the average utilization percentage is thus (*t*+1)/2*t*. This gives a utilization of

(t+1)/2t× (t−1) +ft

We next eliminate t. After normalization, we have *t*(1+*f*) = 2, and so *t* = 2/(1+*f*). Plugging this in above and simplifying gives

utilization = (3 + 6f−f^{2})/4(1+f)

## 23.11 Solutions for *Dynamics of TCP Reno*¶

**Exercise 2(a)**

Because the window size of 50 is larger than the bandwidth×delay product is 40 packets, packets are sent at the bottleneck rate of 5 packets/ms. As packets spend 1 ms on the C–R1 link, on average this link must be carrying 5 packets. The same applies to the R2–D link; for the R1–R2 link with a 2.0 ms propagation delay, the number of packets carried will be 2.0×5 = 10.

Alternatively, from the bandwidth×delay product of 40 packets we conclude 40 packets are in transit. Of these, half are acknowledgments. The other half are distributed in proportion to the link propagation delays, yielding 5, 10, and 5 packets.

**Exercise 2.5**

At the point when A’s bandwidth is 2 packets/ms, B’s bandwidth is 4 packets/ms, and so B has 4×20 = 80 packets in transit. As B’s winsize is 120, this leaves 120−80 = 40 packets in R’s queue.

For A to have half as much bandwidth, it must have half the queue capacity, or 20 packets. With a bandwidth of 2 packets/ms and an RTT_{noLoad} of 40 ms, A will have 2×40 = 80 packets in transit. A’s winsize is then 20+80 = 100.

We can confirm this using the following formulas from 14.2.3 Example 3: competition and queue utilization:

_{A}− 2α(d

_{A}+d)

_{B}− 2β(d

_{B}+d)

However, these formulas were derived under the assumption that the bottleneck bandwidth was normalized to 1. To apply them here, we need to measure time in units of 1/6 ms; that is, all times need to be multiplied by 6. We have:

_{A}= 90

_{B}= 30

_{B}= 120

Substituting these into the second formula, we get the total queue utilization Q = 180 − 120 = 60, in agreement with our earlier answer. From the first formula we now solve for w_{A} = α(Q + 2(d_{A}+d)) = (1/3)×(60 + 240) = 100, also in agreement with our earlier answer.

**Exercise 3(a)**

The bottleneck bandwidth is 5 packets/ms, and as the bottleneck link is saturated, this will be the transmission rate on all links. For 5 packets to be in transmission, we need a propagation delay of 5 packets / (5 packets/ms) = 1.0 ms.