Math 343/443 Midterm study guide answers Dordal Exercise numbers here are from the SECOND edition of the text! Sorry! The original study guide lists exercise numbers from both 2nd and 3rd editions. chapter 1: ====================================================================== #18 Either way, we have 35 microsec switch delay and a net 40 microsec propagation delay. Sent as one packet, we have two 1000-microsec bandwidth delays as well; sent as two packets, we have three 500-microsec delays. Thus, the totals are 2075 and 1575, respectively. ====================================================================== ====================================================================== chapter 2: ====================================================================== #30 Sliding windows Note that this is the canonical SWS = bandwidth x delay case, with RTT = 4 sec. (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. ====================================================================== #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 Here is the table for (c): stored | distance to reach: 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 A-----B-----C | | | | | | D-----E-----F ====================================================================== #15 Standard DV update exercise (a) "inf" = infinite cost A: dest cost nexthop B: dest cost nexthop B inf - A inf - C 3 C C inf - D inf - D 4 E E inf - E 2 E F 9 C F inf - D: dest cost nexthop F: dest cost nexthop A inf - A 9 C B 4 E B inf - C inf - C 6 C E 2 E D inf - F inf - E inf - (b) A: dest cost nexthop B 12 D C 3 C D 8 D E 10 D F 9 C D: dest cost nexthop A 8 A B 4 E C 11 A E 2 E F 17 A (c) C: dest cost nexthop A 3 A B 15 A D 11 A E 13 A F 6 F ====================================================================== ====================================================================== Chapter 5 ====================================================================== #20 (a). There are 4096 ports; we run out if we use these in less than 60 sec, that is, at a rate of more than 4096/60 = 70 ports/sec. (b). The fact that actual sequence numbers in use do not overlap prevents old packets from being accepted as new. We do, however, have to consider the possible arrival of very late FINs from the previous connection; we need to be sure we do not respond with RST. ====================================================================== Here are solutions for the two that didn't appear in 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.