3.-第三章课后习题及答案

第三章1. (Q1) Suppose the network layer provides the following service. The network layer in the source host accepts a segment of maximum size 1,200 bytes and a destination host address from the transport layer. The network layer then guarantees to deliver the segment to the transport layer at the destination host. Suppose many network application processes can be running at the destination host.a. Design the simplest possible transport-layer protocol that will getapplication data to the desired process at the destination host. Assume the operating system in the destination host has assigned a 4-byte port number to each running application process.b. Modify this protocol so that it provides a “return address”to the destination process.c. In your protocols, does the transport layer “have to do anything” in thecore of the computer network.Answer:a. Call this protocol Simple Transport Protocol (STP). At the sender side, STPaccepts from the sending process a chunk of data not exceeding 1196 bytes,a destination host address, and a destination port number. STP adds a four-byte header to each chunk and puts the port number of the destination process in this header. STP then gives the destination host address and the resulting segment to the network layer. The network layer delivers the segment to STP at the destination host. STP then examines the port number in the segment, extracts the data from the segment, and passes the data to the process identified by the port number.b. The segment now has two header fields: a source port field and destinationport field. At the sender side, STP accepts a chunk of data not exceeding 1192 bytes, a destination host address, a source port number, and a destination port number. STP creates a segment which contains the application data, source port number, and destination port number. It then gives the segment and the destination host address to the network layer. After receiving the segment, STP at the receiving host gives the application process the application data and the source port number.c. No, the transport layer does not have to do anything in the core; thetransport layer “lives” in the e nd systems.2. (Q2) Consider a planet where everyone belongs to a family of six, every family lives in its own house, each house has a unique address, and each person in a given house has a unique name. Suppose this planet has a mail service that delivers letters form source house to destination house. The mail service requires that (i) the letter be in an envelope and that (ii) the address of the destination house (and nothing more ) be clearly written on the envelope. Suppose each family has a delegate family member who collects and distributes letters for the other family members. The letters do not necessarily provide any indication of the recipients of the letters.a. Using the solution to Problem Q1 above as inspiration, describe a protocolthat the delegates can use to deliver letters from a sending family member to a receiving family member.b. In your protocol, does the mail service ever have to open the envelope andexamine the letter in order to provide its service.Answer:a.For sending a letter, the family member is required to give the delegate theletter itself, the address of the destination house, and the name of therecipient. The delegate clearly writes the recipient’s name on the top of the letter. The delegate then puts the letter in an envelope and writes the address of the destination house on the envelope. The delegate then gives the letter to the planet’s mail service. At the receiving side, the delegate receives the letter from the mail service, takes the letter out of the envelope, and takes note of the recipient name written at the top of the letter. The delegate than gives the letter to the family member with this name.b.No, the mail service does not have to open the envelope; it only examines theaddress on the envelope.3. (Q3) Describe why an application developer might choose to run an application over UDP rather than TCP.Answer:An application developer may not want its application to use TCP’s congestion control, which can throttle the application’s sending rate at times of congestion. Often, designers of IP telephony and IP videoconference applications choose to run their applications over UDP because they want to avoid TCP’s congestion control. Also, some applications do not need the reliable data transfer provided by TCP.4. (P1) Suppose Client A initiates a Telnet session with Server S. At about the same time, Client B also initiates a Telnet session with Server S. Provide possible source and destination port numbers fora. The segment sent from A to B.b. The segment sent from B to S.c. The segment sent from S to A.d. The segment sent from S to B.e. If A and B are different hosts, is it possible that the source port numberin the segment from A to S is the same as that from B to Sf. How about if they are the same hostAnswer:e Yes.f No.5. (P2) Consider Figure What are the source and destination port values in thesegments flowing form the server back to the clients’ processes What are the IP addresses in the network-layer datagrams carrying the transport-layer segmentsAnswer:Suppose the IP addresses of the hosts A, B, and C are a, b, c, respectively.(Note that a,b,c are distinct.)To host A: Source port =80, source IP address = b, dest port = 26145, dest IP address = aTo host C, left process: Source port =80, source IP address = b, dest port = 7532, dest IP address = cTo host C, right process: Source port =80, source IP address = b, dest port = 26145, dest IP address = c6. (P3) UDP and TCP use 1s complement for their checksums. Suppose you have thefollowing three 8-bit bytes: 01101010, 01001111, 01110011. What is the 1s complement of the sum of these 8-bit bytes (Note that although UDP and TCP use 16-bit words in computing the checksum, for this problem you are being asked to consider 8-bit sums.) Show all work. Why is it that UDP takes the 1s complement of the sum; that is , why not just sue the sum With the 1s complement scheme, how does the receiver detect errors Is it possible that a 1-bit error will go undetected How about a 2-bit errorAnswer:One's complement = 1 1 1 0 1 1 1 0.To detect errors, the receiver adds the four words (the three original words and the checksum). If the sum contains a zero, the receiver knows there has been an error. All one-bit errors will be detected, but two-bit errors can be undetected ., if the last digit of the first word is converted to a 0 and the last digit of the second word is converted to a 1).7. (P4) Suppose that the UDP receiver computes the Internet checksum for thereceived UDP segment and finds that it matches the value carried in the checksum field. Can the receiver be absolutely certain that no bit errors have occurred Explain.Answer:No, the receiver cannot be absolutely certain that no bit errors have occurred. This is because of the manner in which the checksum for the packet is calculated. 0 1 0 1 0 1 0 1 + 0 1 1 1 0 0 0 0 1 1 0 0 0 1 0 1 1 1 0 0 0 1 0 1 + 0 1 0 0 1 1 0 0 0 0 0 1 0 0 0 1If the corresponding bits (that would be added together) of two 16-bit words in the packet were 0 and 1 then even if these get flipped to 1 and 0 respectively, the sum still remains the same. Hence, the 1s complement the receiver calculates will also be the same. This means the checksum will verify even if there was transmission error.8. (P5) a. Suppose you have the following 2 bytes: 01001010 and 01111001. Whatis the 1s complement of sum of these 2 bytesb. Suppose you have the following 2 bytes: and 01101110. What is the 1scomplement of sum of these 2 bytesc. For the bytes in part (a), give an example where one bit is flipped ineach of the 2 bytes and yet the 1s complement doesn’t change.Answer:a. Adding the two bytes gives . Taking the one’s complement gives 01100010b. Adding the two bytes gives 00011110; the one’s complement gives .c. first byte = 00110101 ; second byte = 01101000.9. (P6) Consider our motivation for correcting protocol . Show that the receiver,shown inthe figure on the following page, when operating with the sender show in Figure , can lead the sender and receiver to enter into a deadlock state, where each is waiting for an event that will never occur.Answer:Suppose the sender is in state “Wait for call 1 from above” and the receiver (the receiver shown in the homework problem) is in state “Wait for 1 from below.” The sender sends a packet with sequence number 1, and transitions to “Wait for ACK or NAK 1,” waiting for an ACK or NAK. Suppose now the receiverreceives the packet with sequence number 1 correctly, sends an ACK, and transitions to state “Wait for 0 from below,” waiting for a data packet with sequence number 0. However, the ACK is corrupted. When the sender gets the corrupted ACK, it resends the packet with sequence number 1. However, the receiver is waiting for a packet with sequence number 0 and (as shown in the home work problem) always sends a NAK when it doesn't get a packet with sequence number 0. Hence the sender will always be sending a packet with sequence number 1, and the receiver will always be NAKing that packet. Neither will progress forward from that state.10. (P7) Draw the FSM for the receiver side of protocolAnswer:The sender side of protocol differs from the sender side of protocol in thattimeouts have been added. We have seen that the introduction of timeouts adds the possibility of duplicate packets into the sender-to-receiver data stream. However, the receiver in protocol can already handle duplicate packets. (Receiver-side duplicates in rdt would arise if the receiver sent an ACK that was lost, and the sender then retransmitted the old data). Hence the receiver in protocol will also work as the receiver in protocol rdt .11. (P8) In protocol , the ACK packets flowing from the receiver to the senderdo not have sequence numbers (although they do have an ACK field that contains the sequence number of the packet they are acknowledging). Why is it that our ACK packets do not require sequence numbersAnswer:To best Answer this question, consider why we needed sequence numbers in the firstplace. We saw that the sender needs sequence numbers so that the receiver can tell if a data packet is a duplicate of an already received data packet. In the case of ACKs, the sender does not need this info ., a sequence number on an ACK) to tell detect a duplicate ACK. A duplicate ACK is obvious to the receiver, since when it has received the original ACK it transitioned to the next state. The duplicate ACK is not the ACK that the sender needs and hence is ignored by the sender.12. (P9) Give a trace of the operation of protocol when data packets andacknowledgment packets are garbled. Your trace should be similar to thatused in FigureAnswer: Suppose the protocol has been in operation for some time. The sender is in state “Waitfor call from above” (top left hand corner) and the receiver is in state “Wait for 0 from below”. The scenarios for corrupted data and corrupted ACK are shown in Figure 1.13. (P10) Consider a channel that can lose packets but has a maximum delay thatis known. Modify protocol to include sender timeout and retransmit.Informally argue why your protocol can communicate correctly over thischannel.Answer:Here, we add a timer, whose value is greater than the known round-trip propagation delay. We add a timeout event to the “Wait for ACK or NAK0” and “Wait for ACK or NAK1” states. If the timeout event occurs, the most recently transmitted packet is retransmitted. Let us see why this protocol will still work with the receiver.• Suppose the timeout is caused by a lost data packet, ., a packet on the senderto- receiver channel. In this case, the receiver never received the previous transmission and, from the receiver's viewpoint, if the timeoutretransmission is received, it look exactly the same as if the original transmission is being received.• Suppose now that an ACK is lost. The receiver will eventually retransmit the packet on a timeout. But a retransmission is exactly the same action that is take if an ACK is garbled. Thus the sender's reaction is the same with a loss, as with a garbled ACK. The rdt receiver can already handle the case of a garbled ACK.14. (P11) Consider the protocol. Draw a diagram showing that if the networkconnection between the sender and receiver can reorder messages (thatis, that two messages propagating in the medium between the sender andreceiver can be reordered), then the alternating-bit protocol will notwork correctly (make sure you clearly identify the sense in which itwill not work correctly). Your diagram should have the sender on theleft and the receiver on the right, with the time axis running down thepage, showing data (D) and acknowledgement (A) message exchange. Makesure you indicate the sequence number associated with any data oracknowledgement segment.Answer:15. (P12) The sender side of simply ignores (that is, takes no action on) allreceived packets that are either in error or have the wrong value inthe ack-num field of an acknowledgement packet. Suppose that in suchcircumstances, were simply to retransmit the current data packet .Would the protocol still work (hint: Consider what would happen if therewere only bit errors; there are no packet losses but premature timeoutcan occur. Consider how many times the nth packet is sent, in the limitas n approaches infinity.)Answer:The protocol would still work, since a retransmission would be what would happen if the packet received with errors has actually been lost (and from the receiver standpoint, it never knows which of these events, if either, will occur). To get at the more subtle issue behind this question, one has to allow for premature timeouts to occur. In this case, if each extra copy of the packet is ACKed and each received extra ACK causes another extra copy of the current packet to be sent, the number of times packet n is sent will increase without bound as n approaches infinity.16. (P13) Consider a reliable data transfer protocol that uses only negativeacknowledgements. Suppose the sender sends data only infrequently. Woulda NAK-only protocol be preferable to a protocol that uses ACKs Why Nowsuppose the sender has a lot of data to send and the end to end connectionexperiences few losses. In this second case , would a NAK-only protocolbe preferable to a protocol that uses ACKs WhyAnswer:In a NAK only protocol, the loss of packet x is only detected by the receiver when packetx+1 is received. That is, the receivers receives x-1 and then x+1, only when x+1 is received does the receiver realize that x was missed. If there is a long delay between the transmission of x and the transmission of x+1, then it will be a long time until x can be recovered, under a NAK only protocol.On the other hand, if data is being sent often, then recovery under a NAK-only scheme could happen quickly. Moreover, if errors are infrequent, then NAKs are only occasionally sent (when needed), and ACK are never sent – a significant reduction in feedback in the NAK-only case over the ACK-only case.17. (P14) Consider the cross-country example shown in Figure . How big wouldthe window size have to be for the channel utilization to be greaterthan 80 percentAnswer:It takes 8 microseconds (or milliseconds) to send a packet. in order for the senderto be busy 90 percent of the time, we must have util = = / or n approximately 3377 packets.18. (P15) Consider a scenario in which Host A wants to simultaneously sendpackets to Host B and C. A is connected to B and C via a broadcastchannel—a packet sent by A is carried by the channel to both B and C.Suppose that the broadcast channel connecting A, B, and C canindependently lose and corrupt packets (and so, for example, a packetsent from A might be correctly received by B, but not by C). Design astop-and-wait-like error-control protocol for reliable transferringpackets from A to B and C, such that A will not get new data from theupper layer until it knows that B and C have correctly received thecurrent packet. Give FSM descriptions of A and C. (Hint: The FSM for Bshould be essentially be same as for C.) Also, give a description ofthe packet format(s) used.Answer:In our solution, the sender will wait until it receives an ACK for a pair of messages (seqnum and seqnum+1) before moving on to the next pair of messages. Data packets have a data field and carry a two-bit sequence number. That is, the valid sequence numbers are 0, 1, 2, and 3. (Note: you should think about why a 1-bit sequence number space of 0, 1 only would not work in the solution below.) ACK messages carry the sequence number of the data packet they are acknowledging.The FSM for the sender and receiver are shown in Figure 2. Note that the sender state records whether (i) no ACKs have been received for the current pair, (ii) an ACK for seqnum (only) has been received, or an ACK for seqnum+1 (only) has been received. In this figure, we assume that the seqnum is initially 0, and that the sender has sent the first two data messages (to get things going). A timeline trace for the sender and receiver recovering from a lost packet is shown below:Sender Receivermake pair (0,1)send packet 0Packet 0 dropssend packet 1receive packet 1buffer packet 1send ACK 1receive ACK 1(timeout)resend packet 0receive packet 0deliver pair (0,1)send ACK 0receive ACK 019. (P16) Consider a scenario in which Host A and Host B want to send messagesto Host C. Hosts A and C are connected by a channel that can lose andcorrupt (but not reorder)message. Hosts B and C are connected by anotherchannel (independent of the channel connecting A and C) with the sameproperties. The transport layer at Host C should alternate in deliveringmessages from A and B to the layer above (that is, it should firstdeliver the data from a packet from A, then the data from a packet fromB, and so on). Design a stop-and-wait-like error-control protocol forreliable transferring packets from A to B and C, with alternatingdelivery at C as described above. Give FSM descriptions of A and C.(Hint: The FSM for B should be essentially be same as for A.) Also, givea description of the packet format(s) used.Answer:This problem is a variation on the simple stop and wait protocol . Because the channel may lose messages and because the sender may resend a message that one of the receivers has already received (either because of a premature timeout or because the other receiver has yet to receive the data correctly), sequence numbers are needed. As in , a 0-bit sequence number will suffice here.The sender and receiver FSM are shown in Figure 3. In this problem, the sender state indicates whether the sender has received an ACK from B (only), from C (only) or from neither C nor B. The receiver state indicates which sequence number the receiver is waiting for.20. (P17) In the generic SR protocol that we studied in Section the sendertransmits a message as soon as it is available (if it is in the window)without waiting for an acknowledgment. Suppose now that we want an SRprotocol that sends messages two at a time. That is , the sender willsend a pair of messages and will send the next pair of messages onlywhen it knows that both messages in the first pair have been receivercorrectly.Suppose that the channel may lose messages but will not corrupt or reorder messages. Design an error-control protocol for theunidirectional reliable transfer of messages. Give an FSM descriptionof the sender and receiver. Describe the format of the packets sentbetween sender and receiver, and vice versa. If you use any procedurecalls other than those in Section (for example, udt_send(),start_timer(), rdt_rcv(), and so on) ,clearly state their actions. Givean example (a timeline trace of sender and receiver) showing how yourprotocol recovers from a lost packet.Answer:21. (P18) Consider the GBN protocol with a sender window size of 3 and a sequencenumber range of 1024. Suppose that at time t, the next in-order packetthat the receiver is expecting has a sequence number of k. Assume thatthe medium does not reorder messages. Answer the following questions:a. What are the possible sets of sequence number inside the sender’swindow at time t Justify your Answer.b .What are all possible values of the ACK field in all possible messagescurrently propagating back to the sender at time t Justify your Answer. Answer:a.Here we have a window size of N=3. Suppose the receiver has received packetk-1, and has ACKed that and all other preceeding packets. If all of these ACK's have been received by sender, then sender's window is [k, k+N-1].Suppose next that none of the ACKs have been received at the sender. In this second case, the sender's window contains k-1 and the N packets up to and including k-1. The sender's window is thus [k- N,k-1]. By these arguments, the senders window is of size 3 and begins somewhere in the range [k-N,k]. b.If the receiver is waiting for packet k, then it has received (and ACKed)packet k-1 and the N-1 packets before that. If none of those N ACKs have been yet received by the sender, then ACK messages with values of [k-N,k-1] may still be propagating back. Because the sender has sent packets [k-N, k-1], it must be the case that the sender has already received an ACK for k-N-1.Once the receiver has sent an ACK for k-N-1 it will never send an ACK that is less that k-N-1. Thus the range of in-flight ACK values can range from k-N-1 to k-1.22. (P19) Answer true or false to the following questions and briefly justifyyour Answer.a. With the SR protocol, it is possible for the sender to receive anACK for a packet that falls outside of its current window.b. With CBN, it is possible for the sender to receiver an ACK for apacket that falls outside of its current window.c. The alternating-bit protocol is the same as the SR protocol with asender and receiver window size of 1.d. The alternating-bit protocol is the same as the GBN protocol with asender and receiver window size of 1.Answer:a.True. Suppose the sender has a window size of 3 and sends packets 1, 2, 3 att0 . At t1 (t1 > t0) the receiver ACKS 1, 2, 3. At t2 (t2 > t1) the sender times out and resends 1, 2, 3. At t3 the receiver receives the duplicates and re-acknowledges 1, 2, 3. At t4 the sender receives the ACKs that the receiver sent at t1 and advances its window to 4, 5, 6. At t5 the sender receives the ACKs 1, 2, 3 the receiver sent at t2 . These ACKs are outside its window.b.True. By essentially the same scenario as in (a).c.True.d.True. Note that with a window size of 1, SR, GBN, and the alternating bitprotocol are functionally equivalent. The window size of 1 precludes the possibility of out-of-order packets (within the window). A cumulative ACK is just an ordinary ACK in this situation, since it can only refer to the single packet within the window.23. (Q4) Why is it that voice and video traffic is often sent over TCP ratherthan UDP in today’s Internet. (Hint: The Answer we are looking for hasnothing to do with TCP’s congestion-control mechanism. )Answer:Since most firewalls are configured to block UDP traffic, using TCP for video and voice traffic lets the traffic though the firewalls24. (Q5) Is it possible for an application to enjoy reliable data transfer evenwhen the application runs over UDP If so, howAnswer:Yes. The application developer can put reliable data transfer into the application layer protocol. This would require a significant amount of work and debugging, however.25. (Q6) Consider a TCP connection between Host A and Host B. Suppose that theTCP segments traveling form Host A to Host B have source port number xand destination port number y. What are the source and destination portnumber for the segments traveling form Host B to Host AAnswer:Source port number y and destination port number x.26. (P20) Suppose we have two network entities, A and B. B has a supply of datamessages that will be sent to A according to the following conventions.When A gets a request from the layer above to get the next data (D)message from B, A must send a request (R) message to B on the A-to-Bchannel. Only when B receives an R message can it send a data (D) messageback to A on the B-to-A channel. A should deliver exactly one copy ofeach D message to the layer above. R message can be lost (but notcorrupted) in the A-to-B channel; D messages, once sent, are alwaysdelivered correctly. The delay along both channels is unknown andvariable.Design(give an FSM description of) a protocol that incorporates the appropriate mechanisms to compensate for the loss-prone A-to-B channeland implements message passing to the layer above at entity A, asdiscussed above. Use only those mechanisms that are absolutely necessary.Answer:Because the A-to-B channel can lose request messages, A will need to timeout and retransmit its request messages (to be able to recover from loss). Because the channel delays are variable and unknown, it is possible that A will send duplicate requests ., resend a request message that has already been received by B). To be able to detect duplicate request messages, the protocol will use sequence numbers. A 1-bit sequence number will suffice for a stop-and-wait typeof request/response protocol.A (the requestor) has 4 states:•“Wait for Request 0 from above.” Here the requestor is waiting for a call from above to request a unit of data. When it receives a request from above, it sends a request message, R0, to B, starts a timer and makes a transition to the “Wait for D0” state. When in the “Wait for Request 0 from above” state, A ignores anything it receives from B.•“Wait for D0”. Here the requestor is waiting for a D0 data message from B.A timer is always running in this state. If the timer expires, A sends another R0 message, restarts the timer and remains in this state. If a D0 message is received from B, A stops the time and transits to the “Wait for Request 1 from above” state. If A receives a D1 data message while in this state, it is ignored.•“Wait for Request 1 from above.” Here the requestor is again waiting for a call from above to request a unit of data. When it receives a request from above, it sends a request message, R1, to B, starts a timer and makes a transition to the “Wait for D1” state. When in the “Wait for Request 1 from above” state, A ignores anything it receives from B.•“Wait for D1”. Here the requestor is waiting for a D1 data message from B.A timer is always running in this state. If the timer expires, A sends another R1 message, restarts the timer and remains in this state. If a D1 message is received from B, A stops the timer and transits to the “Wait for Request 0 f rom above” state. If A receives a D0 data message while in this state, it is ignored.The data supplier (B) has only two states:•“Send D0.” In this state, B continues to respond to received R0 messages by sending D0, and then remaining in this state. If B receives a R1 message, then。