CPS 214 Written Homework 3 Solutions Fall, 1996 1a) "Application" routines get invoked at runtime via threads. For example, asp_init gets called once at startup. This routine then schedules an event (via Event) to invoke the client and server routines. 1b) clientDemux sends the remaining packets. Since the client sends the next message when it gets a response for the previous message, the same thread that delivers the packet received from the server to the client can turn around and send the next packet on behalf of the client. 2) WANs have a high latency, which increases the "contention interval", the window during which two stations may both transmit leading to a collision. In short, the cost of collisions becomes unacceptably high. In addition, the minimum packet size (to insure that every packet is at least twice the latency in length) becomes to large to be reasonable. 3a) Hamming distance is 2; 2 changes converts 110011->111111 b) the code can detect 1 single-bit error. c) Can't guarantee to correct any errors. 4) Error correcting codes would be more appropriate because of the large propagation delays. The space craft couldn't hold on to the data long enough to wait for an ACK. It simply wouldn't be practical to have it do so. It would need too much memory. 5) The performance of go back N and selective repeat are identical, assuming that no packets are lost and they are not reordered during transmission (which is always true at the data link layer). Go back N does worse when packet losses take place, because it rejects all packets that follow the lost one, and they will all need to be retransmitted. 6) Round trip delay is 2*60ms = 120ms. The time to transmit a single frame is 1000bits/56kb/sec = 17.8ms. The receiving peer cannot ACK a frame until it has completely received it, so the total delay before receiving an ACK is 120+17.8 = 137.8ms. That corresponds to 137.8ms/17.8ms/frame = 7.74 frames. Thus, efficiency reaches 100% with a window size of 8; making it larger won't help. 7) No benefit whatsoever. The sender won't send data outside its send window, so making the receive window bigger won't allow it to receive more data. Tanenbaum 3.3) In bit stuffing, a 0-bit is appended to each occurrence of 5 consecutive 1-bits. Thus, the replacement string is ``011110111110011111010''. Tanenbaum 3.11) Efficiency = time spent sending useful data divided by total time spent sending and waiting. The time to transmit one message = (n bits)* (msec/4bits) = n/4 msec After sending a packet, we must wait one round trip time for the ACK. Thus, efficiency is: (n/4 msec)/(n/4 msec + 2*20 msec) = n/(n+160) We want the efficiency to be > 50%, so: n/(n+160) > .5 n > .5n + 80 n > 160 Tanenbaum 4.21) The minimum frame size needs to be twice the propagation delay. If P is our packet size, P / 1Gbps >= 2km / [200,000 km/s] P >= 10000 bits Tanenbaum 4.29) Each station would need to see enough of the frame to decide whether it was addressed to them (and hence needed to be removed) before they could forward it on. This would increase the transmission delay. Also, if the intended destination isn't on the ring, one would still need a way to remove the packet. So the sender would still need to remove some frames. Not clear how you would implement broadcasting or multicasting (i.e., such frames would need to be propagated all the way around the ring). It would also be difficult to support the "A" and "C" bits that indicate whether the intended receiver was able to copy the frame into its internal memory. The algorithm for bumping up the priority on data frames wouldn't work anymore. Tanenbaum 4.30) 4Mb/s * 10ms * 1s/1000ms = 40000 bits Tanenbaum 4.32) Time to transmit frame is 10**3B *(8b/B) * (1/100Mb/sec) = 8*10**-5 seconds The time for the frame to travel around the ring is (approximately) : 200km * (1/2*10**5km/s) = 10**-3 sec Thus, the efficiency is roughly 8*10**-5/10**-3 = .08 = 8% Tanenbaum 4.35) The token ring delay is bounded only if all of the stations are functioning properly and stations aren't failing. When a station fails, the ring monitor may need to do work to regenerate tokens, or the stations may need to elect a new ring monitor. The amount of time needed to this is potentially unbounded, depending on the actual sequence of failures. Tanenbaum 4.37) To forward a packet, their are two costs: the per-packet cost (looking at header fields, consulting tables, etc.) that is constant independent of the packet size. The second cost is dependent on the packet length (e.g., copying overheads). The bridge that needs to forward 1000 (vs. 200) pps probably needs the faster cpu. Tanenbaum 5.3) Virtual circuit networks still need to be able to route/forward packets individually. How else will the network find the path actually used once a VC has been set up? 11) The minimum Ethernet frame size is 64 bytes. If the packet to be sent is less that 64 bytes, the frame must be padded with filler. Without a length field, the receiver wouldn't be able to distinguish filler from valid data. Peterson 4.2) a) After A connects to B: Assuming ID are numbered starting at 0: Switch # In Port In ID Out Port Out ID 1 2 0 1 0 2 3 0 0 0 3 0 0 3 0 b) After C connects to G: Switch # In Port In ID Out Port Out ID 1 2 0 1 0 3 0 1 1 2 3 0 0 0 3 1 1 0 3 0 0 3 0 4 3 0 1 0 c) After E connects to I: Switch # In Port In ID Out Port Out ID 1 2 0 1 0 3 0 1 1 2 3 0 0 0 3 1 1 0 2 0 0 1 3 0 0 3 0 0 1 2 0 4 3 0 1 0 d) After H connects to B: Switch # In Port In ID Out Port Out ID 1 2 0 1 0 3 0 1 1 0 0 1 2 2 3 0 0 0 3 1 1 0 2 0 0 1 3 2 0 2 3 0 0 3 0 0 1 2 0 0 2 3 1 4 3 0 1 0 e) After F connects to J: Switch # In Port In ID Out Port Out ID 1 2 0 1 0 3 0 1 1 0 0 1 2 2 3 0 0 0 3 1 1 0 2 0 0 1 3 2 0 2 1 0 0 3 3 0 0 3 0 0 1 2 0 0 2 3 1 0 3 1 0 4 3 0 1 0 2 0 3 0 f) After H connects to A: Switch # In Port In ID Out Port Out ID 1 2 0 1 0 3 0 1 1 0 0 1 2 1 0 2 0 2 3 0 0 0 3 1 1 0 2 0 0 1 3 2 0 2 1 0 0 3 1 1 3 0 3 0 0 3 0 0 1 2 0 0 2 3 1 0 3 1 0 4 3 0 1 0 2 0 3 0 0 0 3