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¶
|E||D (or C)|
|D||E (or A)|
|C||E (or A)|
|A||C (or D)|
Exercise 7.0(d) (destination D):
The path from S1 to D is thus S1–S2–S5–S6–S12.
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¶
The path from S2 to S5 is S2–S3–S1–S5.
- 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.
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¶
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 S0, the station with the next-smallest address becomes S1, etc.
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.
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).
The connections are as follows, where the VCI number is shown between the endpoints of each link:
23.5 Solutions for Packets¶
|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.
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: 10100010 0: parity over these bits: 10100010 0: parity over these bits: 10100010
So the incorrect received code bits are 0111.
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 10100010.
The third bit of the received code tells us that the error is in the bold bits of 10100010, 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 10100010, which means the fourth bit is it, and the corrected data is 10110010 (making the data the same as that in the example in 126.96.36.199 Hamming Codes).
23.6 Solutions for Sliding Windows¶
The network is
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|
If Data is in the receiver’s window, then Data must have been received. For the sender to have sent Data it must have previously received ACK. Therefore, all transmissions of Data must precede the first transmission of Data, and so must precede the first successful transmission of Data. Because of non-reordering, no Data can arrive after Data.
23.7 Solutions for IPv4¶
Forwarding table for A:
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
23.8 Solutions for Routing-Update Algorithms¶
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
|A||2||R1||no change; same next_hop|
|B||3||R2||no change; tie|
|D||4||R1||lower-cost route found|
23.9 Solutions for Large-Scale IP Routing¶
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¶
Let t be the transit capacity; then the total
cwndmax 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)/2t. 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 − f2)/4(1+f)
23.11 Solutions for Dynamics of TCP Reno¶
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.
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 RTTnoLoad 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:
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:
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 wA = α(Q + 2(dA+d)) = (1/3)×(60 + 240) = 100, also in agreement with our earlier answer.
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.