Example Problem: PigeonExpress!4/13/049 6.033 quiz 2 reviewBen Bitdiddle cannot believe the high valuations of today s Internetcompanies, so he is doing a startup, PigeonExpress!.com, whichprovides high performance networking using pigeons. Ben's reasoningis that it is cheaper to build a network using pigeons than it is todig up streets to lay new cables. Although there is a standard fortransmitting Internet datagrams with avian carriers (see network RFC1149) it is out of date, and Ben has modernized it.When transmitting a pigeon, Ben's software prints out a little headeron a sticky label and also writes a compact disk (CD) containing thedata. Someone sticks the label on the disk and gives it to thepigeon. The header on the label contains the Global Positioning System(GPS) coordinates of the destination and the source (the point wherethe pigeon is taking off), a type field indicating the kind of message(request or acknowledgement), and a sequence number:Example Problem: PigeonExpress!4/13/0410 6.033 quiz 2 reviewstruct header { GPS src; GPS dst; int type; int seq;} The CD holds a maximum of 640 Megabytes of data. The pigeon reads the header and delivers the labeled CD to the destination. The header and data are never corrupted and never separated. Even better, for purposes of this problem, computers don't fail. However, pigeons occasionally get lost, in which case they never reach their destination. To make life tolerable on the pigeon network, Ben designs a simpleend-to-end protocol (Ben's End-to-End Protocol, BEEP) to ensurereliable delivery. Suppose that there is a single sender and a singlereceiver. On the sender's computer, the following code is executed:Example Problem: PigeonExpress!4/13/0411 6.033 quiz 2 reviewint sequence; // a global sequence number int nextCD; // the next CD to be sent from CD[] init_sender() { sequence = 0; } BEEP(GPS dest, int n, CD[]) { // send n CDs to dest struct header h; nextCD = 0; h.src = my_GPS; // set src to my GPS coordinates h.dst = dest; // set dst to the destination h.type = REQUEST; // this is a request message while (nextCD < n) { // send the CDs h.seq = sequence; // set seq number for this CD send pigeon with h, CD[nextCD]; //transmit pigeon wait 2,000 seconds; } }Example Problem: PigeonExpress!4/13/0412 6.033 quiz 2 review Pending and incoming acknowledgements are processed only when the sender is waiting:process_ack(struct header h){if(h.seq == sequence){sequence = sequence + 1;nextCD = nextCD + 1; // allow next CD to be sent}}The receiver executes the following code: process_request(struct header h, CD) { // process requestprocess(CD); // process the data on the CDh.dst = h.src; //send to where the pigeon came fromh.src = my_GPS;h.seq = h.seq; //unchangedh.type = ACK; // this is an acknowledgementsend pigeon with h; // send an acknowledgement back}Question 14/13/0413 6.033 quiz 2 reviewIf a pigeon travels at 100 meters/second (these are express pigeons!) and pigeons do not get lost, then what is the maximum data rate observed by the caller of BEEP on a 50,000 meter (50 kilometer) long pigeon link? Assume that the processing delay at the sender and receiver are negligible.Question 1640 MB / 2000 seconds, or 320 Kilobytes/second4/13/0414 6.033 quiz 2 reviewIf a pigeon travels at 100 meters/second (these are express pigeons!) and pigeons do not get lost, then what is the maximum data rate observed by the caller of BEEP on a 50,000 meter (50 kilometer) long pigeon link? Assume that the processing delay at the sender and receiver are negligible.Question 2●Does at least one copy of each CD make it to the destination, even though some pigeons are lost?A. Yes, because nextCD and sequence are incremented only on the arrival of a matching acknowledgement.B. No, since there is no explicit loss-recovery procedure (such as a time-out procedure).C. No, since other requests and acknowledgements can get lost.D. Yes, since the next acknowledgement will trigger a retransmission.4/13/0415 6.033 quiz 2 reviewQuestion 2●Does at least one copy of each CD make it to the destination, even though some pigeons are lost?A. Yes, because nextCD and sequence are incremented only on the arrival of a matching acknowledgement.B. No, since there is no explicit loss-recovery procedure (such as a time-out procedure).C. No, since other requests and acknowledgements can get lost.D. Yes, since the next acknowledgement will trigger a retransmission.4/13/0416 6.033 quiz 2 reviewQuestion 3● To guaranteee that each CD arrives at most once, what is required?A. We must assume that a pigeon for each CD has to arrive eventually.B. We must assume that acknowledgement pigeons do not get lost and must arrive within 2,000 seconds after the corresponding request pigeon is transmitted.C. We must assume request pigeons must never get lost.D. Nothing. The protocol guaranteees at-most-once delivery.4/13/0417 6.033 quiz 2 reviewQuestion 3● To guaranteee that each CD arrives at most once, what is required?A. We must assume that a pigeon for each CD has to arrive eventually.B. We must assume that acknowledgement pigeons do not get lost and must arrive within 2,000 seconds after the corresponding request pigeon is transmitted.C. We must assume request pigeons must never get lost.D. Nothing. The protocol guaranteees at-most-once delivery.4/13/0418 6.033 quiz 2 reviewQuestion 4● Ignoring possible duplicates, what is needed to guarantee that CDs arrive in order?A. We must assume that pigeons arrive in the order in which they were sent. B. Nothing. The protocol guarantees that CDs arrive in order. C. We must assume that request pigeons never get lost. D. We must assume that acknowledgement pigeons never get lost.4/13/0419 6.033 quiz 2 reviewQuestion 4● Ignoring possible duplicates, what is needed to guarantee that CDs arrive in order?A. We must assume that pigeons arrive in the order in which they were sent. B. Nothing. The protocol guarantees that CDs arrive in order. C. We must assume that request pigeons never get lost. D. We must assume that acknowledgement pigeons never get lost.4/13/0420 6.033 quiz 2 reviewExample Problem: PigeonExpress!4/13/0421 6.033 quiz 2 review To attract more users to PigeonExpress!, Ben improves throughput of the 50-Kilometer long link by using a window-based flow-control scheme. He picks window (number of CDs) as the window size and rewrites the code. The code to be executed on the sender's computer isnow as follows:Example Problem:
View Full Document
Unlocking...