Math 343/443 Midterm study guide answers Dordal Exercise numbers are in the form (3rd_edition)/(2nd_edition). chapter 1: ====================================================================== #22/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: ====================================================================== #36/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 ====================================================================== #37/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. ====================================================================== #39/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. ====================================================================== #47/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/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 ====================================================================== #3/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 ====================================================================== #4/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 ====================================================================== #15/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/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/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. ====================================================================== #15/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 ====================================================================== #18/14 A-----B-----C | | | | | | D-----E-----F ====================================================================== #20/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 ====================================================================== ====================================================================== 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.