Comp 343/443 Sample Midterm answers Summer 2001 Dordal chapter 2: ====================================================================== #30 Sliding windows Note that this is the canonical SWS = bandwidth x delay case, with RTT = 4 sec. (SWS = Sender window size) (a)In the following we list the progress of one particular packet. At any given instant, there are four packets outstanding in various states. T=N Data[N] leaves A T=N+1 Data[N] arrives at R T=N+2 Data[N] arrives at B; ACK[N] leaves T=N+3 ACK[N] arrives at R T=N+4 ACK[N] arrives at A; DATA[N+4] leaves. Here is a specific timeline showing all packets in progress: T=0 Data[0]...Data[3] ready; Data[0] sent T=1 Data[0] arrives at R; Data[1] sent T=2 Data[0] arrives at B; ACK[0] starts back; Data[2] sent T=3 ACK[0] arrives at R; Data[3] sent T=4 ACK[0] arrives at A; Data[4] sent T=5 ACK[1] arrives at A; Data[5] sent ... (b) (delay changed to 1 sec *latency*) T=0 Data[0]...Data[3] sent T=1 Data[0]...Data[3] arrive at R T=2 Data arrive at B; ACK[0]...ACK[3] start back T=3 ACKs arrive at R T=4 ACKs arrive at A; Data[4]...Data[7] sent T=5 Data arrive at R ====================================================================== #31 Sliding windows T=0 A sends frames 1-4. Frame[1] starts across the R--B link. Frames 2,3,4 are in R's queue. T=1 Frame[1] arrives at B; ACK[1] starts back; Frame[2] leaves R. Frames 3,4 are in R's queue. T=2 ACK[1] arrives at R and then A; A sends Frame[5] to R; Frame[2] arrives at B; B sends ACK[2] to R. R begins sending Frame[3]; frames 4,5 are in R's queue. T=3 ACK[2] arrives at R and then A; A sends Frame[6] to R; Frame[3] arrives at B; B sends ACK[3] to R; R begins sending Frame[4]; frames 5,6 are in R's queue. T=4 ACK[3] arrives at R and then A; A sends Frame[7] to R; Frame[4] arrives at B; B sends ACK[4] to R. R begins sending Frame[5]; frames 6,7 are in R's queue. The steady-state queue size at R is two frames. ====================================================================== #32 Sliding windows T=0 A sends frames 1-4. Frame[1] starts across the R--B link. Frame[2] is in R's queue; frames 3 & 4 are lost. T=1 Frame[1] arrives at B; ACK[1] starts back; Frame[2] leaves R. T=2 ACK[1] arrives at R and then A; A sends Frame[5] to R. R immediately begins forwarding it to B. Frame[2] arrives at B; B sends ACK[2] to R. T=3 ACK[2] arrives at R and then A; A sends Frame[6] to R. R immediately begins forwarding it to B. Frame[5] (not 3) arrives at B; B sends no ACK. T=4 Frame[6] arrives at B; again, B sends no ACK. T=5 A TIMES OUT, and retransmits frames 3 and 4. R begins forwarding Frame[3] immediately, and enqueues 4. T=6 Frame[3] arrives at B and ACK[3] begins its way back. R begins forwarding Frame[4]. T=7 Frame[4] arrives at B and ACK[6] begins its way back. ACK[3] reaches A and A then sends Frame[7]. R begins forwarding Frame[7]. ====================================================================== #33 Ethernet minimum packet size Ethernet has a minimum frame size (64 bytes for 10Mbps; considerably larger for faster Ethernets); smaller packets are padded out to the minimum size. Protocols above Ethernet must be able to distinguish such padding from actual data. ====================================================================== #39 Ethernet collision timeline Here is one possible solution; many, of course, are possible. The probability of four collisions appears to be quite low. Events are listed in order of occurrence. A attempts to transmit; discovers line is busy and waits. B attempts to transmit; discovers line is busy and waits. C attempts to transmit; discovers line is busy and waits. D finishes; A, B, and C all detect this, and attempt to transmit, and collide. A chooses k_A=1, B chooses k_B=1, and C chooses k_C=1. One slot time later A, B, and C all attempt to retransmit, and again collide. A chooses k_A=2, B chooses k_B=3, and C chooses k_C=1. One slot time later C attempts to transmit, and succeeds. While it transmits, A and B both attempt to retransmit but discover the line is busy and wait. C finishes; A and B attempt to retransmit and a third collision occurs. A and B back off and (since we require a fourth collision) once again happen to choose the same k<8. A and B collide for the fourth time; this time A chooses k_A=15 and B chooses k_B=14. 14 slot times later, B transmits. While B is transmitting, A attempts to transmit but sees the line is busy, and waits for B to finish. ====================================================================== ====================================================================== Chapter 3: ====================================================================== #1 connections => VCI tables The following table is cumulative; at each part the VCI tables consist of the entries at that part and also all previous entries. part switch Port VCI | Port VCI (a) 1 2 0 | 1 0 2 3 0 | 0 0 3 0 0 | 3 0 (b) 1 3 0 | 1 1 2 3 1 | 1 0 4 3 0 | 1 0 (c) 2 2 0 | 0 1 3 0 1 | 2 0 (d) 1 0 0 | 1 2 2 3 2 | 0 2 3 0 2 | 3 1 (e) 2 1 1 | 0 3 3 0 3 | 1 0 4 2 0 | 3 1 (f) 1 1 3 | 2 1 2 1 2 | 3 3 4 0 0 | 3 2 ====================================================================== #2 datagram forwarding Node A: Node B: Dest Next hop Dest Next hop B C A E C C C E D C D E E C E E F C F E Node C: Node D: Dest Next hop Dest Next hop A A A E B E B E D E C E E E E E F F F E Node E: Node F: Dest Next hop Dest Next hop A C A C B B B C C C C C D D D C F C E C ====================================================================== #3 datagram forwarding with DEFAULT entry S1: destination port A 1 B 2 default 3 S2: destination port A 1 B 1 C 3 D 3 default 2 S3: destination port C 2 D 3 default 1 S4: destination port D 2 default 1 ====================================================================== #13 Ethernet learning bridges When A sends to C, all bridges see the packet and learn where A is. However, when C then sends to A, the packet is routed directly to A and B4 does not learn where C is. Similarly, when D sends to C, the packet is routed by B2 towards B1 only, and B1 does not learn where D is. B1: A-interface: A B2-interface: C (not D) B2: B1-interface: A B3-interface: C B4-interface: D B3: B2-interface: A,D C-interface: C B4: B2-interface: A (not C) D-interface: D ====================================================================== ====================================================================== Chapter 4: ====================================================================== #1 IP addresses are per host, not per machine IP addresses include the network/subnet, so that interfaces on different networks must have different network portions of the address. Alternatively, addresses include location information and different interfaces are at different locations, topologically. Point-to-point interfaces can be assigned a duplicate address (or no address) because the other endpoint of the link doesn't use the address to reach the interface; it just sends. Such interfaces, however, cannot be addressed by any other host in the network. See also RFC1812, section 2.2.7, page 25, on ``unnumbered point-to-point links''. ====================================================================== #2 Fragmentation, header layout issues The IPv4 header allocates only 13 bits to the Offset field, but a packet's length can be up to 2^16 - 1. In order to support fragmentation of a maximum-sized packet, we must count offsets in multiples of 2^{16-13} = 2^3 bytes. The only concerns with counting fragmentation offsets in 8-byte units are that we would waste space on a network with MTU = 8n+7 bytes, or that alignment on 8-byte boundaries would prove inconvenient. 8-byte chunks are small enough that neither of these is a significant concern. ====================================================================== #12 IP routing tables (a) info | distance to reach node stored | at node| A B C D E F ------------------------------------------- A | 0 inf 3 8 inf inf B | inf 0 inf inf 2 inf C | 3 inf 0 inf 1 6 D | 8 inf inf 0 2 inf E | inf 2 1 2 0 inf F | inf inf 6 inf inf 0 (b) info | distance to reach node stored | at node| A B C D E F ------------------------------------------- A | 0 inf 3 8 4 9 B | inf 0 3 4 2 inf C | 3 3 0 3 1 6 D | 8 4 3 0 2 inf E | 4 2 1 2 0 7 F | 9 inf 6 inf 7 0 (c) info | distance to reach node stored | at node| A B C D E F ------------------------------------------- A | 0 6 3 6 4 9 B | 6 0 3 4 2 9 C | 3 3 0 3 1 6 D | 6 4 3 0 2 9 E | 4 2 1 2 0 7 F | 9 9 6 9 7 0 ====================================================================== #14 IP forwarding The cost=1 links show A connects directly to B and D, and F connects to C and E. F reaches B through C at cost 2, so B and C must connect. F reaches D through E at cost 2, so D and E must connect. A reaches E at cost 2 through B, so B and E must connect. These give: A---B---C | | | D---E---F ====================================================================== #15 IP routing tables (b) A's table: dest cost nexthop B 12 D C 3 C D 8 D E 10 D F 9 C D's table: dest cost nexthop A 8 A B 4 E C 11 A E 2 E F 17 A (c) C's table: dest cost nexthop A 3 A B 15 A D 11 A E 13 A F 6 F ====================================================================== #16 Standard IP forwarding Apply each subnet mask and if the corresponding subnet number matches the SubnetNumber column, then use the entry in Next-Hop. (In these tables there is always a unique match.) (a) Applying the subnet mask 255.255.255.128, we get 128.96.39.0. Use interface0 as the next hop. (b) Applying subnet mask 255.255.255.128, we get 128.96.40.0. Use R2 as the next hop. (c) All subnet masks give 128.96.40.128 as the subnet number. Since there is no match, use the default entry. Next hop is R4. (d) Next hop is R3. (e) None of the subnet number entries match, hence use default router R4. ====================================================================== #32 Based on a real incident at Loyola. Aaargh! A can reach B and D but not C. To reach B, A sends ARP requests directly to B; these are passed by RB as are the actual ethernet packets. To reach D, A uses ARP to send to R2. However, if A tries to ARP to C, the request will not pass R1. Even if A knows C's Ethernet address already, the packets will not pass R1. ====================================================================== #34 subnets To solve this with routing, C has to be given its own subnet. Even if this is small, this reduces the available size of the original Ethernet to at most seven bits of subnet address. Here is a possible routing table for B; subnet numbers and masks are in binary. Note that we didn't get to this part yet in class, and this kind of table will *not* be on the exam. net subnet mask interface 200.0.0 0/000 0000 1000 0000 Ethernet 200.0.0 1000 00/00 1111 1100 direct link Here C's subnet has been made as small as possible; only two host bits are available (a single host bit can't be used because all-zero-bits and all-ones-bits are reserved in the host portion of an address). C's address might now be 200.0.0.10000001, with the last octet again in binary. ====================================================================== ====================================================================== Here are solutions for the two more that were not from the text. 1. (a). A's table: 200.0.{5,6} direct default B B's table: 200.0.{6,7,9} direct 200.0.5 A 200.0.10 C default D C's table 200.0.{9,10} direct default B D's table 200.0.{7,8} direct 200.0.{5,6,9,10} B default DEFAULT (b): Note there is more than one possible solution; A can use either B or C as a default path. Still other solutions are *possible*. B *could* use A as default, if A defaulted to C and C defaulted to D, but that would be somewhat inefficient. ====================================================================== 2. A sends an ARP request "where is B", but lists C's phys addr. Then B will reply, but to *C*. B will install the entry in its table. C will receive the reply packet and discard it. Any *other* machine that had had A in its cache will now also update its entry to that above, Such machines that had been sending to A will now also send to C, and C will (unless it is a router) discard the packets. Even C will have this entry. It may or may not actually *receive* the packet sent to its own ethernet address, but either way A surely will not receive it. ======================================================================