Comp 443 Midterm Exam Information

The midterm will cover the sections below. Sections in bold are the most important.

During the exam you will have a copy of the following midterm notes to use as reference. You may not use your own notes.

Chapter 1: Overview

1.1 Layers
1.3 Packets
1.4 Datagram Forwarding
1.5 Topology
1.6 Routing loops
1.7 Congestion
1.8 Packets again
1.9 LANs and Ethernet
1.10 IP
1.12 Transport

Chapter 2:

2.1 10-Mbps classic Ethernet
2.2 100-Mbps Ethernet
2.4 Ethernet Switches

Chapter 3: Other LANs

3.6, 3.7: Wi-Fi
(virtual circuits are officially dropped)

Chapter 4: Links

4.1 Encoding and Framing

Chapter 5: Packets

5.1: delay
5.2: delay variability
5.3: packet size

Chapter 6: Sliding Windows

6.1: stop-and-wait
6.2: sliding windows
6.3: bottlenecks

Chapter 7:

7.1  The IPv4 header (you do not need to memorize the specific layout)
7.5  Classless IP delivery
7.6  Subnets
7.8  ARP

Chapter 8: IPv6
        Not on midterm

Chapter 9:

9.1: distance-vector
9.2: slow-convergence problem and fixes
9.3: slow-convergence fixes

Chapter 11: UDP

11.1: UDP
11.2: fundamental transport issues

Chapter 12: TCP

12.3: connection establishment
12.6: state diagram
12.7: old duplicates
12.8: TIMEWAIT
12.9: 3WHS
12.10: anomalous scenarios


The following exercises from the book should give you a fair idea of what to expect on the exam; you shouldn't necessarily complete every detail of these, but you should study the text until you're reasonably confident you know how to approach them. There are also likely to be some short-answer "non-exercise"-format problems.

Answers will be available soon. Look for them on Sakai.


Chapter 1

1. Give forwarding tables for each of the switches S1-S4 in the following network with destinations A, B, C, D. For the next_hop column, give the neighbor on the appropriate link rather than the interface number.

A         B         C
│         │         │
S1────────S2────────S3
          │
          │
          S4───D

3. Consider the following arrangement of switches and destinations. Give forwarding tables (in neighbor form) for S1-S4 that include default forwarding entries; the default entries should point toward S5. Eliminate all table entries that are implied by the default entry (that is, if the default entry is to S3, eliminate all other entries for which the next hop is S3).

A───S1
    │         D
    │         │
C───S3────────S4─────────S5
    │         │
    │         E
B───S2


7. Consider the following arrangement of switches:

S1─────S4─────S10──A──E
│      │
│      │
S2─────S5─────S11──B
│      │
│      │
S3─────S6─────S12──C──D──F

Suppose S1-S6 have the forwarding tables below. For each destination A,B,C,D,E,F, suppose a packet is sent to the destination from S1. Give the switches it passes through, including the initial switch S1, up until the final switch S10-S12.

S1: (A,S4), (B,S2), (C,S4), (D,S2), (E,S2), (F,S4)

S2: (A,S5), (B,S5), (D,S5), (E,S3), (F,S3)

S3: (B,S6), (C,S2), (E,S6), (F,S6)

S4: (A,S10), (C,S5), (E,S10), (F,S5)

S5: (A,S6), (B,S11), (C,S6), (D,S6), (E,S4), (F,S2)

S6: (A,S3), (B,S12), (C,S12), (D,S12), (E,S5), (F,S12)


Chapter 2: Ethernet

2. Suppose we have Ethernet switches S1 through S3 arranged as below. All forwarding tables are initially empty.

S1────────S2────────S3───D
│         │         │
A         B         C

    If A sends to B, which switches see this packet?
    If B then replies to A, which switches see this packet?
    If C then sends to B, which switches see this packet?
    If C then sends to D, which switches see this packet?

3. Suppose we have the Ethernet switches S1 through S4 arranged as below. All forwarding tables are empty; each switch uses the Ethernet switch learning algorithm.

              B
              │
              S4
              │
A───S1────────S2────────S3───C
              │
              D
Now suppose the following packet transmissions take place:

For each switch, list what source addresses (eg A,B,C,D) it has seen (and thus what nodes it has learned the location of).


Chapter 3: Other LANs

8 (omitted).

Chapter 5: packets and delay

2. Suppose the path from A to B has a single switch S in between: A───S───B. Each link has a propagation delay of 60 µsec and a bandwidth of 2 bytes/µsec.

    (a). How long would it take to send a single 600-byte packet from A to B?
    (b). How long would it take to send two back-to-back 300-byte packets from A to B?
    (c). How long would it take to send three back-to-back 200-byte packets from A to B?

6. Suppose we have five links, A───R1───R2───R3───R4───B. Each link has a bandwidth of 100 bytes/ms. Assume we model the per-link propagation delay as 0.

    (a). How long would it take a single 1500-byte packet to go from A to B?
    (b). How long would it take five consecutive 300-byte packets to go from A to B?


Chapter 6: Sliding windows

3. Create a table as in the text's Section 6.3.1: Simple fixed-window-size analysis for the original A───R1───R2───R3───R4───B network, with 1 packet/sec bandwidth delay for the R1⟶R2, R2⟶R3, R3⟶R4 and R4⟶B links. The A–R link and all reverse links (from B to A) are infinitely fast. Assume winsize = 8. Carry out the table for 10 seconds.

5. Suppose RTTnoLoad = 4 seconds and the bottleneck bandwidth is 1 packet / 2 seconds.

    (a). What window size is needed to remain just at the knee of congestion?
    (b). Suppose winsize=6. How many packets are in the queue, at the steady state, and what is RTTactual?

8. Suppose RTTnoLoad is 50 ms and the available bandwidth is 2,000 packets/sec. sliding windows is used for transmission.

    (a). What window size is needed to remain just at the knee of congestion?
    (b). If RTTactual rises to 60 ms (due to use of a larger winsize), how many packets are in a queue at any one time?
    (c). What value of winsize would lead to RTTactual = 60 ms?
    (d). What value of winsize would make RTTactual rise to 100 ms?


Chapter 7: IPv4

4. The following diagram has routers A, B, C, D and E; E is the “border router” connecting the site to the Internet. All links are via /24 subnets of the form 200.0.x. Give forwarding tables for each of A, B, C and D. Each table should include each of the listed subnets and also a default entry that routes traffic toward router E.

200.0.5────A────200.0.6────B────200.0.7────D────200.0.8────E────Internet
                           │
                       200.0.9
                           │
                           C
                           │
                       200.0.10


6. For each IP network prefix given (with length), identify which of the subsequent IP addresses are part of the same subnet.

(a). 10.0.130.0/23: 10.0.130.23, 10.0.129.1, 10.0.131.12, 10.0.132.7
(b). 10.0.132.0/22: 10.0.130.23, 10.0.135.1, 10.0.134.12, 10.0.136.7
(c). 10.0.64.0/18: 10.0.65.13, 10.0.32.4, 10.0.127.3, 10.0.128.4


10. (new) Suppose A broadcasts an ARP request “who-has B”, but inadvertently lists the physical address of another machine C instead of its own (that is, A’s ARP query has IPsrc = A, but LANsrc = C). What will happen? Will A receive a reply? Will any other hosts on the LAN be able to send to A? What entries will be made in the ARP caches on A, B and C?


Chapter 9: Routing-update Algorithms

3. Suppose a router R has the following distance-vector table:

destination cost next hop
A 5 R1
B 6 R1
C 7 R2
D 8 R2
E 9 R3

R now receives the following report from R1; the cost of the R–R1 link is 1.

destination cost
A 4
B 7
C 7
D 6
E 8
F 8

Give R's new table after processing R1's report. For each entry that changes, give a brief reason.


8. Suppose the routers are A, B, C, D, E and F, and all link costs are 1. The distance-vector forwarding tables for A and F are below. Give the network with the fewest links that is consistent with these tables. Hint: any destination reached at cost 1 is directly connected; if X reaches Y via Z at cost 2, then Z and Y must be directly connected.

A’s table

destination cost next hop
B 1 B
C 1 C
D 2 C
E 2 C
F 3 B

F’s table

destination cost next hop
A 3 E
B 2 D
C 2 D
D 1 D
E 1 E



Chapter 12

4. Simultaneous connection initiations are rare, but simultaneous connection termination is relatively common. How do two TCP nodes negotiate the simultaneous sending of FIN packets to one another? Which node goes into TIMEWAIT state?


5. (a). Suppose you see multiple connections on your workstation in state FIN_WAIT_1. What is likely going on? Whose fault is it?

(b). What might be going on if you see connections languishing in state FIN_WAIT_2?

6. Suppose that, after downloading a file, a user workstation is unplugged from the network. The workstation may or may not have first sent a FIN to start closing the connection.

(a). If the receiver has not sent the first FIN, what TCP states could this leave the server stuck in? Use the TCP state diagram.
(b). Now suppose the receiver has sent its FIN before being unplugged. What states could this leave the server stuck in?


7. Suppose A and B create a TCP connection with ISNA=20000 and ISNB=5000. A sends three 1000-byte packets, and B ACKs each. Then B sends a 1000-byte packet to A and terminates the connection with a FIN. List all packets, together with SEQ and ACK fields, up through this first FIN packet from B.

A sends B sends
SYN, ISNA=20000  

SYN, ISNB=5000, ACK=______
ACK, SEQ=______, ACK=______  
Data1, SEQ=______, ACK=______  

ACK, SEQ=______, ACK=______
Data2, SEQ=______, ACK=______  

ACK, SEQ=______, ACK=______
Data3, SEQ=______, ACK=______  

ACK, SEQ=______, ACK=______

DataB, SEQ=______, ACK=______
ACK, SEQ=_____, ACK=______  

FIN, SEQ=______, ACK=______


8. Suppose you are watching a video on a site like YouTube, where there is a progress bar showing how much of the video has been downloaded (and which hopefully stays comfortably head of the second progress bar showing your position in viewing the video). Occasionally, the download-progress bar jumps ahead, instantaneously fast. At the TCP layer, what is going on to cause this jump? Hint: what does a TCP receiver perceive when a packet is lost and retransmitted?