DOC PREVIEW
MIT 6 033 - Quiz II - Solutions

This preview shows page 1-2-3-4 out of 11 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 11 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 11 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 11 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 11 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 11 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Department of Electrical Engineering and Computer ScienceMASSACHUSETTS INSTITUTE OF TECHNOLOGY6.033 Computer Systems Engineering: Spring 2008Quiz II - Solutions 0 10 20 30 40 5091-10081-9071-8061-7051-6041-5031-4021-3011-20CountScore2008 Quiz 2 GradesMean: 67Median: 71StDev: 186.033 Spring 2008, Quiz 2 Page 2 of 11I Reading Questions1. [6 points]: Which of the following statements are true of Ethernet (as described in the Ethernetpaper, reading #9)?(Circle True or False for each choice.)A. True / False Ethernet enforces a minimum packet size with the intention of minimizing the numberof collisions.FALSE. The purpose of the minimum packet size is to provide reliable collision detection.B. True / False Using repeaters to overcome signal attenuation, you can make an Ethernet network aslong as you want.FALSE. The maximum size is limited because the RTT must be less than the length of a minimum-sizepacket. Otherwise the transmitter could complete sending the packet before detecting a collision.C. True / False Consider one node on an Ethernet network using TCP to send a large amount of datato another node on the same network. If there are no other nodes transmitting on this network, therecan’t be any collisions.FALSE. The TCP ACKs can collide with the data packets.2. [8 points]: Which of the following statements are true of LFS (as described in the LFS paper,reading #15)?(Circle True or False for each choice.)A. True / False If a program writes an entire 64KB file in a single write system call, all the blocksof the file are likely to be stored in one or two groups of nearby cylinders.TRUE. LFS will append the data to its log, which it lays out contiguously on the disk.B. True / False A computer with an LFS file system crashes and then reboots. Data that were writtento files after LFS wrote its last checkpoint, but before the crash, are lost; that is, during recovery LFSreturns to its state at the time it wrote the checkpoint.FALSE. During recovery, LFS looks at the end of the log to learn about modifications after the lastcheckpoint.For questions C and D, consider a program that uses a single large file that does not change in size.The program performs bursts of reads or bursts writes to random blocks in the file. Assume that duringreads, the requested blocks are not found in a RAM cache, and that by the time a burst of writes ends,all the blocks are actually written to disk.C. True / False If the file is stored on LFS, the disk will perform roughly the same number of seekoperations during a burst of random reads as during a burst of random writes.FALSE. LFS appends each write to the log, which often requires no seeks.D. True / False If the file is stored on the original UNIX file system, the disk will perform roughly thesame number of seek operations during a burst of random reads as during a burst of random writes.TRUE.6.033 Spring 2008, Quiz 2 Page 3 of 11II Geographic RoutingBen Bitdiddle is very excited about a novel routing protocol that he came up with. Ben argues that sinceGPS devices are getting very cheap, one can equip each router with GPS capabilities to find its location androute packets based on location information.Specifically, assume that all nodes in a network are in the same plane and nodes never move. Each node isidentified by a tuple (x,y), which refers to its GPS-derived coordinates and no two nodes have the samecoordinates. Each node is joined by links to its neighbors, forming a connected network graph. A nodeinforms its neighbors of its coordinates when it joins the network and whenever it recovers after a failure.When a source sends a packet, it puts the destination coordinates in the packet header. These coordinatesplay the role of a destination IP address, and you can assume that each sender knows the coordinates ofits destination. When a router wants to forward a packet, it checks if any of its neighbors are closer to thedestination in Euclidean distance than itself. If none of its neighbors is closer, the router drops the packet.Otherwise the router forwards the packet to its neighbor closest to the destination. Forwarding stops whenthe packet reaches its destination or is dropped.3. [8 points]: Circle all that are true about the Ben’s geographic routing algorithm.(Circle ALL that apply)A. If there are no failures, and no nodes join the network while packets are en route, no packet willexperience a routing loop.TRUE. Each hop brings the packet strictly closer to the destination, or results in the packet beingdropped.B. If nodes fail while packets are en route, a packet may experience a routing loop.FALSE. A failed node might cause a lost packet, but again each hop either takes the packet closer tothe destination or causes it to be dropped.C. If nodes join the network while packets are en route, a packet may experience a routing loop.FALSE. Again, a new node will either drop the packet or forward it closer to the destination.Since Ben’s algorithm forces the distance to the destination to strictly decrease, the packet cannotloop.6.033 Spring 2008, Quiz 2 Page 4 of 11In the following two questions assume that no link or node fails or joins the network. If drawing anexample, do so in the grid provided. Ensure that all nodes are located on the intersection of grid lines, thatyour graph is connected, and links are clearly marked with solid lines. Links need not follow grid lines.4. [10 points]: Can Ben’s algorithm deliver packets between any source-destination pair in a net-work? If yes, explain, if no, provide a counter example.NO. One possible counter example is shown below.Ben’s algorithm will never send packets along the first hop in the path, since this hop travels furtheraway from the destination.6.033 Spring 2008, Quiz 2 Page 5 of 115. [10 points]: For all packets that Ben’s algorithm delivers to their corresponding destinations, doesBen’s algorithm use the same route as the path vector algorithm discussed in class? If your answer isyes, then explain it. If your answer is no, then draw a counter example.NO. One possible counter example is shown below.The path vector protocol will select the shorter (in terms of hops) upper path while Ben’s algorithmwill always choose the lower path.Acceptable answers included scenarios where both paths were the same length, but where the pathvector protocol may choose either path, i.e., where the paths may be different if the two protocolsbroke ties differently. It was also acceptable to interpret the


View Full Document

MIT 6 033 - Quiz II - Solutions

Documents in this Course
TRIPLET

TRIPLET

12 pages

End Layer

End Layer

11 pages

Quiz 1

Quiz 1

4 pages

Threads

Threads

18 pages

Quiz I

Quiz I

15 pages

Atomicity

Atomicity

10 pages

QUIZ I

QUIZ I

7 pages

Load more
Download Quiz II - Solutions
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Quiz II - Solutions and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Quiz II - Solutions 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?