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: ====================================================================== #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 ====================================================================== #40/33 (a). This was more-or-less the same example I did in class Thursday. Giving each department a single subnet, the nominal subnet sizes are 2^7 = 128, 2^6 = 64, 2^5 = 32, 2^5 = 32 respectively; we obtain these by rounding up to the nearest power of 2. A possible arrangement of subnet numbers is as follows. Subnet numbers are in binary and represent an initial segment of the bits of the last byte of the IP address; anything to the right of the / represents host bits. The / thus represents the subnet mask. Any individual bit can, by symmetry, be flipped throughout; there are thus several possible bit assignments. A 0/ one subnet bit, with value 0; seven host bits B 10/ C 110/ D 111/ The essential rule for "nonoverlapping" assignments is that any two subnet prefixes are distinct when the longer one is truncated to the length of the shorter. For part (b), the sizes of each subnet still total less than 256, but the total EXCEEDS 256 when each is rounded up to the next power of 2. Thus, the only way to do this using subnets is to divide one of the existing subnets. Subnet A for example, could be divided into A1 of size 64 and A2 of size 16; the total of 80 is much less than the old rounded-up size of 128. Note that in the "real world" bridging would likely be used instead of subnets. ====================================================================== ====================================================================== Chapter 5 ====================================================================== #2/2 (a) In the following, the client receives file "foo" when it thinks it has requested "bar". 1. The client sends a request for file "foo", and immediately aborts locally. The request, however, arrives at the server. 2. The client sends a new request, for file "bar". It is lost. 3. The server responds with first data packet of "foo", answering the only request it has actually seen. Note that this is NOT the same as the old-late-duplicates problem. (b) Requiring the client to use a new port number for each separate request would solve the problem. To do this, however, the client would have to trust the underlying operating system to assign a new port number each time a new socket was opened. Having the client attach a timestamp or random number to the file request, to be echoed back in each data packet from the server, would be another approach fully under the application’s control. ====================================================================== #5/5 The two-segment-lifetime timeout results from the need to purge old late duplicates, and uncertainty of the sender of the last ACK as to whether it was received. For the first issue we only need one connection endpoint to be in TIMEWAIT (though either endpoint would suffice). For the second issue, however, a host in the LAST_ACK state expects to receive the last ACK, rather than send it, and thus the host that initiated the close (and thus eventually progresses to LAST_ACK) is the one that must enter TIMEWAIT. ====================================================================== #8/8 The sequence number doesn’t always begin at 0 for a transfer, but is randomly or clock generated. So, if the ISN (Initial Sequence Number) is, say, 4293967296, then after 1,000,000 bytes are transfered the sequence number will be 4294967296 = 2^32 and will at that point wrap around to 0. ====================================================================== #14/12 (a) If a SYN packet is simply a duplicate, its ISN value will be the same as the initial ISN. If the SYN is not a duplicate, and ISN values are clock-generated, then the second SYN’s ISN will be different. (b) We will assume the receiver is single-homed; that is, has a unique IP address. Let be the remote sender, and lport be the local port. We suppose the existence of a table CONN_TABLE indexed by and containing (among other things) data fields lISN and rISN for the local and remote ISNs. Here's a pseudocode version. if (connections to lport are not being accepted) send RST; break if (there is no entry in CONN_TABLE for ) // new SYN Put into a table, Set rISN to be the received packet’s ISN, Set lISN to be our own ISN, Send the reply ACK Record the connection as being in state SYN RECD else if (CONN_TABLE[] already exists) if (ISN in incoming packet matches rISN from the table) // SYN is a duplicate; ignore it else send RST to ====================================================================== ====================================================================== 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. ====================================================================== 3. This is the old-late-duplicates problem. Some packet, say Data[4], is delayed AND RETRANSMITTED: 1. First REQ is sent from client port 2000; DATA is sent from server child port 3000. 2. When server sends DATA[4], it gets lost somewhere. There's a timeout, and the SECOND copy of DATA[4] makes it through successfully. The first copy is still out there, though, in limbo. (It is also possible that the first copy is the one eventually delivered successfully and the second is the one in limbo, BUT one way or another several packets sent AFTER DATA[4] must make it through successfully to the client BEFORE DATA[4] arrives.) 3. First transfer ends. 4. Client starts a second transfer, again ports 2000 and 3000 are used. 5. Just as client gets to the point of expecting DATA[4], but BEFORE the server actually sends DATA[4].new, the old DATA[4].old from step 2 FINALLY shows up at the client. The client accepts it as DATA[4]. 6. The server does send DATA[4].new; the client receives it but ignores it as a duplicate. The essential requirements are: 1. Same port numbers used on both sides for both logical connections. 2. Some packet gets held up "indefinitely"; following packets however make it through ok. (One proposed model for this is that the unlucky packet gets caught in a routing loop caused by some link failure; the routers discover a new route quickly so subsequent packets make it through ok, but it takes somewhat longer for the loop to be resolved. 3. The unlucky packet must arrive at just the right time.