6.2.1: Problem Sets 1-10

Last updated
Save as PDF

Page ID: 76069

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

Problem Set 1: Quarria

1997–1–2a…m

Quarria is a new country formed on a 1-kilometer-wide rock island in the middle of the Pacific Ocean. The founders have organized the Quarria Stock Market in order to get the economy rolling. The stock market is very simple, since there is only one stock to trade (that of the Quarria Rock Company). Moreover, due to local religious convictions, the price of the stock is always precisely the wind velocity at the highest point on the island. Rocky, Quarria's president, proposes that the stock market be entirely network-based. He suggests running the stock market from a server machine, and requiring each investor to have a separate client machine which makes occasional requests to the server using a simple RPC protocol. The two remote procedures Rocky proposes supporting are

BALANCE(): requests that the server return the cash balance of a client's account. This service is very fast, requiring a simple read of a memory location.
TRADE(nshares): requests that nshares be bought (assuming nshares is positive) or nshares be sold (if nshares is negative) at the current market price. This service is potentially slow, since it potentially involves network traffic in order to locate a willing trade partner.

Quarria implements a simple RPC protocol in which a client sends the server a request message with the following format:

structure Request integer Client // Unique code for the client integer Opcode // Code for operation requested integer Argument // integer argument, if any integer Result // integer return value, if any

The server replies by sending back the same message, with the Result field changed. We assume that all messages fit in one packet, that link- and network-layer error checking detect and discard garbled packets, and that Quarria investors are scrupulously honest; thus any received message was actually sent by some client (although sent messages might get lost).

Q1.1 Is this RPC design appropriate for a connectionless network model, or is a connection-based model assumed?

The client RPC stub blocks the client thread until a reply is received, but includes a timer expiration allowing any client RPC operation to return with the error code TIME_EXPIRED if no response is heard from the server after \(Q\) seconds.

Q1.2 Give a reason for preferring returning a TIME_EXPIRED error code over simply having the RPC operation block forever.

Q1.3 Give a reason for preferring returning a TIME_EXPIRED error code over having the RPC stub transparently retransmit the message.

Q1.4 Suppose you can bound the time taken for a request, including network and server time, at 3 seconds. What advantage is there to setting the expiration time, \(Q\), to 4 seconds instead of 2 seconds?

Unfortunately, no such bound exists for Quarria's network.

Q1.5 What complication does client message retransmission introduce into the RPC semantics, in the absence of a time bound?

Rocky’s initial implementation of the server is as follows:

integer Cash[1000] // Cash balance of each client integer Shares[1000] // Stock owned by each client

procedure SERVER () Request instance req, rep // Pointer to request message do forever // loop forever...
req ← GETNEXTREQUEST () // take next incoming request, if req.Opcode = 1 then // …and dispatch on opcode. rep ← BALANCE (req) // Request 1: return balance SEND (rep) if req.Opcode = 2 then // Request 2: buy/sell stock rep ← TRADE (req); SEND (rep)

// Process a BALANCE request... procedure BALANCE (Request instance req) client ← req.Client // Get client number from request req.Result ← Cash[client] // Return his cash balance return req // and return reply.

// Perform a trade: buy/sell Argument/-Argument shares of stock and // return the total number of shares owned after trade. procedure TRADE (Request instance req) client ← req.Client // The client who is requesting p ← STOCKPRICE () // Price, using network requests nshares ← req.Argument // Number of shares to buy/sell actual ← CONFIRMTRADE (req, p, nshares) // See how many shares we can trade Cash[client]← Cash[client] + p x actual // Update our records Shares[client] ← Shares[client] + actual req.Result ← actual return req

Note that CONFIRMTRADE uses network communication to check on available shares, executes the trade, and returns the number of shares that have actually been bought or sold.

Rocky tests this implementation on a single server machine by having clients scattered around the island sending BALANCE requests as fast as they can. He discovers that after some point adding more clients doesn't increase the throughput—the server throughput tops out at 1000 requests per second.

Q1.6 Rocky is concerned about performance, and hires you to recommend steps for improvement. Which, if any, of the following steps might significantly improve Rocky's measured 1000 BALANCE requests per second?

A. Use faster client machines.
B. Use multiple client threads (each making BALANCE requests) on each client.
C. Use a faster server machine.
D. Use faster network technology.

Stone Galore, a local systems guru, has another suggestion to improve the performance generally. He proposes multithreading the server, replacing calls to service procedures like

BALANCE (req) // Run BALANCE, to service request

with

CREATE_THREAD (BALANCE, req) // create thread to run BALANCE (req)

The CREATE_THREAD primitive creates a new thread, runs the supplied procedure (in this case BALANCE) in that thread, and deactivates the thread on completion. Stone's thread implementation is preemptive.

Stone changes the appropriate three lines of the original code according to the above model, and retries the experiment with BALANCE requests. He now measures a maximum server throughput of 500 requests per second.

Q1.7 Explain the performance degradation.

Q1.8 Is there an advantage to the use of threads in other requests? Explain.

Q1.9 Select the best advice for Rocky regarding server threads:

A. Don't use threads; stick with your original design.
B. Don't use threads for Balance requests, but use them for other requests.
C. Continue using them for all requests; the benefits outweigh the costs.

Independently of your advice, Stone is determined to stick with the multithreaded implementation.

Q1.10 Should the code for TRADE be changed to reflect the fact that it now operates in a multithreaded server environment? Explain, suggesting explicit changes as necessary.

Q1.11 What if the client is multithreaded and can have multiple request outstanding? Should the code for TRADE be changed? Explain, suggesting explicit changes as necessary.

Rocky decides that multithreaded clients are complicated and abandons that idea. He hasn't read about RPC, and isn't sure whether his server requires at-most-once RPC semantics.

Q1.12 Which of the requests require at-most-once RPC semantics? Explain

Q1.13 Suggest how one might modify Rocky's implementation to guarantee at-most-once semantics. Ignore the possibility of crashes, but consider lost messages and retransmissions.

Problem Set 2: PigeonExpress!.com I

1999–2–7…15

(Chapter 1)

Ben Bitdiddle cannot believe the high valuations of some Internet companies, so he is creating a startup, PigeonExpress!.com, which provides high-performance networking using pigeons. Ben's reasoning is that it is cheaper to build a network using pigeons than it is to dig up streets to lay new cables. Although there is a standard for transmitting Internet datagrams with avian carriers (see network RFC 1149) it is out of date, and Ben has modernized it.

When sending a pigeon, Ben's software prints out a little header on a sticky label and also writes a compact disk (CD) containing the data. Someone sticks the label on the disk and gives it to the pigeon. The header on the label contains the Global Positioning System (GPS) coordinates of the destination and the source (the point where the pigeon is taking off), a type field indicating the kind of message (REQUEST or ACKNOWLEDGMENT), and a sequence number:

structure header GPS source GPS destination integer type integer sequence_no

The CD holds a maximum of 640 megabytes of data, so some messages will require multiple CDs. 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 simple end-to-end protocol (Ben's End-to-End Protocol, BEEP) to ensure reliable delivery. Suppose that there is a single sender and a single receiver. The sender's computer executes the following code:

shared next_sequence initially 0 // a global sequence number, starting at 0.

procedure BEEP (destination, n, CD[]) // send n CDs to destination header h // h is an instance of header. nextCD ← 0 h.source ← MY_GPS // set source to my GPS coordinates h.destination ← destination // set destination h.type ← REQUEST // this is a request message while nextCD < n do // send the CDs h.sequence_no ← next_sequence // set seq number for this CD send pigeon with h, CD[nextCD] // transmit wait 2,000 seconds

Pending and incoming acknowledgments are processed only when the sender is waiting:

procedure PROCESS_ACK (h) // process acknowledgment if h.sequence_no = sequence then // ack for current outstanding CD? next_sequence ← next_sequence + 1 nextCD ← nextCD + 1 // allow next CD to be sent

The receiver's computer executes the following code. The arrival of a request triggers invocation of PROCESS_REQUEST:

procedure PROCESS_REQUEST (h, CD) // process request PROCESS (CD) // process the data on the CD h.destination ← h.source // send to where the pigeon came from h.source ← MY_GPS h.sequence_no ← h.sequence_no // unchanged h.type ← ACKNOWLEDGMENT send pigeon with h // send an acknowledgment back

Q2.1 If a pigeon travels at 100 meters per 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 pigeon link that is 50,000 meters (50 kilometers) long? Assume that the processing delay at the sender and receiver are negligible.

Q2.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 next_sequence are incremented only on the arrival of a matching acknowledgment.
B. No, since there is no explicit loss-recovery procedure (such as a timer expiration procedure).
C. No, since both request and acknowledgments can get lost.
D. Yes, since the next acknowledgment will trigger a retransmission

Q2.3 To guarantee 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 acknowledgment pigeons do not get lost and must arrive within 2,000 seconds after the corresponding request pigeon is dispatched.
C. We must assume request pigeons must never get lost.
D. Nothing. The protocol guarantees at-most-once delivery.

Q2.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 acknowledgment pigeons never get lost.

To attract more users to PigeonExpress!, Ben improves the 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 now is:

procedure BEEP (destination, n, CD[]) // send n CDs to destination nextCD ← 0 window ← 10 // initial window size is 10 CDs h.source ← MY_GPS // set source to my GPS coordinates h.destination ← destination // set destination to the destination h.type ← REQUEST // this is a request message while nextCD < n do // send the CDs CDsleft ← n - nextCD temp ← FOO (CDsleft, window) // FOO computes how many pigeons to send for k from 0 to (temp - 1) do h.sequence_no ← next_sequence; // set seq number for this CD send pigeon with h, CD[nextCD + k] // transmit wait 2,000 seconds

The procedures PROCESS_ACK and PROCESS_REQUEST are unchanged.

Q2.5 What should the procedure FOO compute in this code fragment?

A. minimum.
B. maximum.
C. sum.
D. absolute difference.

Q2.6 Alyssa looks at the code and tells Ben it may lose a CD. Ben is shocked and disappointed. What should Ben change to fix the problem?

A. Nothing. The protocol is fine; Alyssa is wrong.
B. Ben should modify PROCESS_REQUEST to accept and process CDs in the order of their sequence numbers.
C. Ben should set the value of window to the delay \(\times\) bandwidth product.
D. Ben should ensure that the sender sends at least one CD after waiting for 2,000 seconds.

Q2.7 Assume pigeons do not get lost. Under what assumptions is the observed data rate for the window-based BEEP larger than the observed data rate for the previous BEEP implementation?

A. The time to process and launch a request pigeon is less than 2,000 seconds
B. The sender and receiver can process more than one request every 2,000 seconds
C. The receiver can process less than one pigeon every 2,000 seconds

After the initial success of PigeonExpress!, the pigeons have to travel farther and farther, and Ben notices that more and more pigeons don't make it to their destinations because they are running out of food. To solve this problem, Ben calls up a number of his friends in strategic locations and asks each of them to be a hub, where pigeons can reload on food.

To keep the hub design simple, each hub can feed one pigeon per second and each hub has space for 100 pigeons. Pigeons feed in first-in, first-out order at a hub. If a pigeon arrives at a full hub, the pigeon gets lucky and retires from PigeonExpress!. The hubs run a patented protocol to determine the best path that pigeons should travel from the source to the destination.

Q2.8 Which layer in the reference model of Chapter 1 provides functions most similar to the system of hubs?

A. the end-to-end layer
B. the network layer
C. the link layer
D. the network layer and the end-to-end layer
E. the feeding layer

Q2.9 Assume Ben is using the window-based BEEP implementation. What change can Ben make to this BEEP implementation in order to make it respond gracefully to congested hubs?

A. Start with a window size of 1 and increase it by 1 upon the arrival of each acknowledgment.
B. Have PROCESS_REQUEST delay acknowledgments and have a single pigeon deliver multiple acknowledgments.
C. Use a window size smaller than 100 CDs, since the hub can hold 100 pigeons.
D. Use multiplicative decrease and additive increase for the window size.

Problem Set 3: Monitoring Ants

2003–2–5…12

(Chapter 1 with a bit of Chapter 5)

Alice has learned that ants are a serious problem in the dorms. To monitor the ant population she acquires a large shipment of motes. Motes are tiny self-powered computers the size of a grain of sand, and they have wireless communication capability. She spreads hundreds of motes in her dorm, planning to create an ad hoc wireless network. Each mote can transmit a packet to another mote that is within its radio range. Motes forward packets containing messages on behalf of other motes to form a network that covers the whole dorm. The exact details of how this network of motes works are our topic.

Each mote runs a small program that every 1 millisecond senses if there are ants nearby. Each time the program senses ants, it increments a counter, called SensorCount . Every 16 milliseconds the program sends a message containing the value of SensorCount and the mote's identifier to the mote connected to Alice's desktop computer, which has identifier A . After sending the message, the mote resets SensorCount . All messages are small enough to fit into a single packet.

Only the radio consumes energy. The radio operates at a speed of 19.2 kilobits per second (using a 916.5 megahertz transceiver). When transmitting the radio draws 12 milliamperes at 3 volts DC. Although receiving draws 4.5 millamperes, for the moment assume that receiving is uses no power. The motes have a battery rated at 575 milliamperehours (mAh).

Q3.1 If a mote transmits continuously, about how long will it be until its battery runs down?

Q3.2 How much energy (voltage \(\times\) current \(\times\) time) does it take to transmit a single bit (1 watt-second = 1 joule)?

Because the radio range of the motes is only ten meters, the motes must cooperate to form a network that covers Alice's dorm. Motes forward packets on behalf of other motes to provide connectivity to Alice's computer, A . To allow the motes to find paths and to adapt to changes in the network (e.g., motes failing because their batteries run down), the motes run a routing protocol. Alice has adopted the path-vector routing protocol from Chapter 1. Each mote runs the following routing algorithm, which finds paths to mote A :

n ← MYID if n = A then path ← [] else path ← NULL

procedure ADVERTISE () if path ≠ NULL then TRANSMIT ({n, path}) // send marshaled message

procedure RECEIVE (p) if n in p then return else if (path = NULL) or (FIRST (p) = FIRST(path)) or (LENGTH (p) < LENGTH(path)) then path ← p

procedure TIMER () if HAVENOTHEARDFROMRECENTLY (FIRST (path)) then path ← NULL

When a mote starts it initializes its variables n and path . Each mode has a unique ID, which the mote stores in the local variable n . Each mote stores its path to A into the path variable. A path contains a list of mote IDs; the last element of this list is A . The first element of the list (FIRST (path)) is the first mote on the path to A . When a mote starts it sets path to NULL , except for Alice's mote, which sets path to the empty path ([]).

Every \(t\) seconds a mote creates a path that contains its own ID concatenated with the value of path, and transmits that path (see ADVERTISE ) using its radio. Motes in radio range may receive this packet. Motes outside radio range will not receive this packet. When a mote receives a routing packet, it invokes the procedure RECEIVE with the argument set to the path p stored in the routing packet. If p contains n , then this routing packet circled back to n and the procedure RECEIVE just returns, rejecting the path. Otherwise, RECEIVE updates path in three cases:

if path is NULL , because n doesn't have any path to A yet.
if the first mote on path is the mote from which we are receiving p , because that mote might have a new path to A .
if p is a shorter path to A than path . (Assume that shorter paths are better.)

A mote also has a timer. If the timer goes off, it invokes the procedure TIMER . If since the last invocation of TIMER a mote hasn't heard from the mote at the head of the path to A , it resets path to NULL because apparently the first node on path is no longer reachable.

The forwarding protocol uses the paths found by the routing protocol to forward reports from a mote to A . Since A may not be in radio range, a report packet may have to be forwarded through several motes to reach A . This forwarding process works as follows:

structure report id data

procedure SEND (counter) report.id ← n report.data ← counter if path ≠ NULL then TRANSMIT (FIRST (path), report);

procedure FORWARD (nexthop, report) if n ≠ nexthop then return if n = A then DELIVER (report) else TRANSMIT (FIRST (path), report)

The procedure SEND creates a report (the mote's ID and its current counter value) and transmits a report packet. The report packet contains the first hop on path, that is FIRST (path), and the report:

Diagram representing the report packet, which contains three sections: nexthop on the left, source in the middle, and sensorcount on the right. The sections source and sensorcount constitute the report.

Figure \(PS.3.1\): Structure of the report packet transmited by SEND .

The nexthop field contains the ID of the mote to which this packet is directed. The source field contains the ID of the mote that originated the packet. The sensorcount field contains the sensor count. (If path is NULL , SEND has no mote to forward the report to so the mote drops the packet.)

When a mote receives a report packet, it calls FORWARD . If a mote receives a report packet for which it is not the next hop, it ignores the packet. If a report packet has reached its final destination A , FORWARD delivers it to Alice's computer. Otherwise, the mote forwards the report by setting nexthop to the first mote on its path variable. This process repeats until the report reaches A , and the packet is delivered.

Suppose we have the following arrangement of motes:

Motes A, B, E, and D are connected so as to form the vertices of a quadrilateral. Motes B and D are at opposite vertices from each other, and are connected to each other by a path that passes through Mote C.

Figure \(PS.3.2\): The arrangement of five motes, identified as A through E.

The circles represent motes with their node IDs. The edges connect motes that are in radio range of one another. For example, when mote A transmits a packet, it may be received by B and D, but not by C and E.

Packets may be lost and motes may also fail (e.g., if their batteries run down). If a mote fails, it just stops sensing, transmitting, and receiving packets.

Q3.3 If motes may fail and if packets may be lost, which of the following values could the variable path at node E have?

A. NULL
B. [B, C]
C. [D, A]
D. [B, A]
E. [B, C, D, A]
F. [C, D, A]
G. [D, A, B, C, D, A]

Q3.4 If no motes fail and packets are not lost, what properties hold for Alice's routing and forwarding protocols with the given arrangement of motes?

A. Every mote's path variable will contain a path to A .
B. After the routing algorithm reaches a stable state, every mote's path variable will contain a shortest path (in hops) to A .
C. After the routing algorithm reaches a stable state, the routing algorithm may have constructed a forwarding cycle.
D. After the routing algorithm reaches a stable state, the longest path is two hops.

Q3.5 If packets may be lost but motes don't fail, what properties hold for Alice's routing and forwarding protocols with the given arrangement of motes?

A. Every mote's path variable will contain a path to A .
B. The routing algorithm may construct forwarding cycles.
C. The routing algorithm may never reach a stable state.
D. When a mote sends a report packet using send, the report may or may not reach A .

A report is 13 bits: an 8-bit node ID and a 5-bit counter. A report packet is 21 bits: an 8-bit next hop and a report. Assume that your answer to Q3.2 (the energy for transmitting one bit) is \(j\) joules. Further assume that to start the radio for transmission takes \(s\) joules. Thus, transmitting a packet with \(r\) bits takes \(s + r \times j\) joules.

Q3.6 Assuming the routing algorithm reaches a stable state, with no node or packet failures, how much total energy does it take for every node to send one report to A (ignoring routing packets)?

Q3.7 Which of the following changes to Alice's system will reduce the amount of energy needed for each node to send one report to A ?

A. Add a nonce to a report so that Alice's computer can detect duplicates.
B. Delay forwarding packets and piggyback them on a report packet from this mote.
C. Use 4-bit node IDs.
D. Use a stop-and-wait protocol to transmit each report reliably from one mote to the next.

To be able to verify the integrity of the reports, Alice creates for each mote a public key pair. She manually loads the private key for mote i into mote i , and keeps the corresponding public keys on her computer. A mote signs the contents of the report (the counter and the source) with its private key and then transmits it.

Thus, a signed report consists of a 5-bit counter, a node ID, and a signature. When Alice's computer receives a signed report, it verifies the signed report and rejects the ones that don't check out.

Q3.8 Assuming that the private keys on the motes are not compromised, and the SIGN and VERIFY procedures are correctly implemented, which of the following properties hold for Alice's plan?

A. A mote that forwards a report is not able to read the report's content.
B. A mote that forwards a report may be able to duplicate a report without Alice's computer rejecting the duplicated report.
C. A mote that forwards a report can use its private key to verify the report.
D. When Alice receives a report for which VERIFY returns ACCEPT , she knows that the report was signed by the mote that is listed in the report and that the report is fresh.

Problem Set 4: Gnutella

2002–2–5…12

Chapters 1 and 5

Ben Bitdiddle is disappointed that the music industry is not publishing his CD, a rap production based on this textbook. Ben is convinced there is a large audience for his material. Having no alternative, he turns his CD into a set of MP3 files, the digital music standard understood by music playing programs, and publishes the songs through Gnutella.

Gnutella is a distributed file sharing application for the Internet. A user of Gnutella starts a Gnutella node, which presents a user interface to query for songs, talks to other nodes, and makes files from its local disk available to other remote users. The Gnutella nodes form what is called an overlay network on top of the existing Internet. The nodes in the overlay network are Gnutella nodes and the links between them are TCP connections. When a node starts it makes a TCP connection to various other nodes, which are connected through TCP connections to other nodes. When a node sends a message to another node, the message travels over the connections established between the nodes. Thus, a message from one node to another node travels through a number of intermediate Gnutella nodes.

To find a file, the user interface on the node sends a query (e.g., "System Design Rap") through the overlay network to other nodes. While the search propagates through the Gnutella network, nodes that have the desired file send a reply, and the user sees a list filling with file names that match the query. Both the queries and their replies travel through the overlay network. The user then selects one of the files to download and play. The user's node downloads the file directly from the node that has the file, instead of through the Gnutella network.

The format of the header of a Gnutella message is:

A Gnutella message header, represented as a long horizontal rectangle, is divided into five sections. From left to right, these sections are the fields MessageID (16 bytes), Type (1 byte), TTL (1 byte), Hops (1 byte), and Length (4 bytes).

Figure \(PS.4.1\): Format of the header of a Gnutella message.

This header is followed by the payload, which is Length bytes long. The main message Types in the Gnutella protocol are:

PING: A node finds additional Gnutella nodes in the network using PING messages. A node wants to be connected to more than one other Gnutella node to provide a high degree of connectivity in the case of node failures. Gnutella nodes are not very reliable because a user might turn off his machine running a Gnutella node at any time. PING messages have no payload.
PONG: A node responds by sending a PONG message via the Gnutella network whenever it receives a PING message. The PONG message has the same MessageID as the corresponding PING message. The payload of the PONG message is the Internet address of the node that is responding to the PING Message.
QUERY: Used to search the Gnutella network for files; its payload contains the query string that the user typed.
QUERYHIT: A node responds by sending a QUERYHIT message via the Gnutella network if it has a file that matches the query in a QUERY message it receives. The payload contains the Internet address of the node that has the file, so that the user's node can connect directly to the node that has the song and download it. The QUERYHIT message has the same MessageID as the corresponding QUERY message.

(The Gnutella protocol also has a PUSH message to deal with firewalls and network address translators, but we will ignore it.)

In order to join the Gnutella network, the user must discover and configure the local node with the addresses of one or more existing nodes. The local node connects to those nodes using TCP. Once connected, the node uses PING messages to find more nodes (more detail below), and then directly connects to some subset of the nodes that the PING message found.

For QUERY and PING messages, Gnutella uses a kind of broadcast protocol known as flooding. Any node that receives a PING or a QUERY message forwards that message to all the nodes it is connected to, except the one from which it received the message. A node decrements the TTL field and increments the Hops field before forwarding the message. If after decrementing the TTL field, the TTL field is zero, the node does not forward the message at all. The Hops field is set to zero by the originating user's node.

To limit flooding and to route PONG and QUERYHIT messages, a node maintains a message table, indexed by MessageID and Type , with an entry for each message seen recently. The entry also contains the Internet address of the Gnutella node that forwarded the message to it. The message table is used as follows:

If a PING or QUERY message arrives and there is an entry in the message table with the same messageID and Type, then the node discards that message.
For a QUERYHIT or PONG message for which there is a corresponding QUERY or PONG entry with the same MessageID in the message table, then the node forwards the QUERYHIT or PONG to the node from which the QUERY or PING was received.
If the corresponding QUERY or PING message doesn't appear in the table, then the node discards the QUERYHIT or PONG message.
Otherwise, the node makes a new entry in the table, and forwards the message to all the nodes it is connected to, except the one from which it received the message.

Q4.1 Assume one doesn't know the topology of the Gnutella network or the propagation delays of messages. According to the protocol, a node should forward all QUERYHIT messages for which it saw the corresponding QUERY message back to the node from which it received the QUERY message. If a node wants to guarantee that rule, when can the node remove the QUERY entry from the message table?

A. Never, in principle, because a node doesn't know if another QUERYHIT for the same Query will arrive.
B. Whenever it feels like, since the table is not necessary for correctness. It is only a performance optimization. C. As soon as it has forwarded the corresponding QUERYHIT message.
D. As soon as the entry becomes the least recently used entry.

Both the Internet and the Gnutella network form graphs. For the Internet, the nodes are routers and the edges are links between the routers. For the Gnutella network, the nodes are Gnutella nodes and the edges are TCP connections between the nodes. The shortest path in a graph between two nodes A and B is the path that connects A with B through the smallest number of nodes.

Q4.2 Assuming a stable Internet and Gnutella network, is the shortest path between two nodes in the Gnutella overlay network always the shortest path between those two nodes in the Internet?

A. Yes, because the Gnutella network uses the Internet to set up TCP connections between its nodes.
B. No, because TCP is slower than UDP.
C. Yes, because the topology of the Gnutella network is identical to the topology of the Internet.
D. No, because for node A to reach node B in the Gnutella network, it might have to go through node C, even though there is a direct, Internet link between A and B.

Q4.3 Which of the following relationships always hold? (TTL(i) and HOP(i) are the values of the TTL and Hop fields respectively after the message has traversed \(i\) hops)

A. TTL(0) = HOPS(i) - TTL(i)
B. TTL(i) = TTL(i-1) - 1, for i > 0
C. TTL(0) = TTL(i) + HOPS(i)
D. TTL(0) = TTL(i) × HOPS(i)

Q4.4 Ben observes that both PING and QUERY messages have the same forwarding rules, so he proposes to delete PING and PONG messages from the protocol and to use a QUERY message with a null query (which requires a node to respond with a QUERYHIT message) to replace PING messages. Is Ben's modified protocol a good replacement for the Gnutella protocol?

A. Yes, good question. Beats me why the Gnutella designers included both PING and QUERY messages.
B. No, a PING message will typically have a lower value in the TTL field than a QUERY message when it enters the network.
C. No, because PONG and QUERYHIT messages have different forwarding rules.
D. No, because there is no way to find nodes using QUERY messages.

Q4.5 Assume that only one node S stores the song "System Design Rap," and that the query enters the network at a node C. Further assume TTL is set to a value large enough to explore the whole network. Gnutella can still find the song "System Design Rap" despite the failures of some sets of nodes (either Gnutella nodes or Internet routers). On the other hand, there are sets of nodes whose failure would prevent Gnutella from finding the song. Which of the following are among the latter sets?

A. any set containing S
B. any set containing a single node on the shortest path from C to S
C. any set of nodes that collectively disconnects C from S in the Gnutella network
D. any set of nodes that collectively disconnects C from S in the Internet

Q4.6 To which of the following attacks is Gnutella vulnerable (i.e., an attacker can implement the described attack)?

A. A single malicious node can always prevent a client from finding a file by dropping QUERYHITs.
B. A malicious node can respond with a file that doesn't match the query.
C. A malicious node can always change the contact information in a QUERYHIT message that goes through the node, for example, misleading the client to connect to it.
D. A single malicious node can always split the network into two disconnected networks by never forwarding PING and QUERY messages.
E. A single malicious node can always cause a QUERY message to circle forever in the network by incrementing the TTL field (instead of decrementing it).

Q4.7 Ben wants to protect the content of a song against eavesdroppers during downloads. Ben thinks a node should send ENCRYPT (k, song), using a shared-secret algorithm, as the download, but Alyssa thinks the node should send CSHA (song), where CSHA is a cryptographically secure hash algorithm. Who is right?

A. Ben is right because no one can compute song from the output of CSHA (song), unless they already have song .
B. Alyssa is right because even if one doesn't know the shared-secret key k, anyone can compute the inverse of the output of ENCRYPT (k, song) .
C. Alyssa is right because CSHA doesn't require a key and therefore Ben doesn't have to design a protocol for key distribution.
D. Both are wrong because a public-key algorithm is the right choice, since encrypting with a public key algorithm is computationally more expensive than either CSHA or a shared-secret algorithm.

Ben is worried that an attacker might modify the "System Design Rap" song. He proposes that every node that originates a message signs the payload of a message with its private key. To discover the public keys of nodes, he modifies the PONG message to contain the public key of the responding node along with its Internet address. When a node is asked to serve a file it signs the response (including the file) with its private key.

Q4.8 Which attacks does this scheme prevent?

A. It prevents malicious nodes from claiming they have a copy of the "System Design Rap" song and then serving music written by Bach.
B. It prevents malicious nodes from modifying QUERY messages that they forward.
C. It prevents malicious nodes from discarding QUERY messages.
D. It prevents nodes from impersonating other nodes and thus prevents them from forging songs.
E. None. It doesn't help.

Problem Set 5: The Ottonet\(^*\)

\(^*\) Credit for developing this problem set goes to Hari Balakrishnan.

2004–2–5…13

(Chapter 1 with a bit of Chapter 5)

Inspired by the recent political success of his Austrian compatriot, "Arnie," in Caleeforneea, Otto Pilot decides to emigrate to Boston. After several months, he finds the local accent impenetrable, and the local politics extremely murky, but what really irks him are the traffic nightmares and long driving delays in the area.

After some research, he concludes that the traffic problems can be alleviated if cars were able to discover up-to-date information about traffic conditions at any specified location, and use this information as input to software that can dynamically suggest good paths to use to go from one place to another. He jettisons his fledgling political career to start a company whose modest goal is to solve Boston's traffic problems.

After talking to car manufacturers, Otto determines the following:

All cars have an on-board computer on which he can install his software. All cars have a variety of sensors that can be processed in the car to provide traffic status, including current traffic speed, traffic density, evidence of accidents, construction delays, etc.
It is easy to equip a car with a Global Positioning System (GPS) receiver (in fact, an increasing number of cars already have one built-in). With GPS, software in the car can determine the car's location in a well-known coordinate system. (Assume that the location information is sufficiently precise for our purposes.)
Each car's computer can be networked using an inexpensive 10 megabits per second radio. Each radio has a spherical range, \(R\), of 250 meters; i.e., a radio transmission from a car has a non-zero probability of directly reaching any other car within 250 meters, and no chance of directly reaching any car outside that range.

Otto sets out to design the OttoNet, a network system to provide traffic status information to applications. OttoNet is an ad hoc wireless network formed by cars communicating with each other using cheap radios, cooperatively forwarding packets for one another.

Each car in OttoNet has a client application and a server application running on its computer. OttoNet provides two procedures that run on every car, which the client and server applications can use:

QUERY (location): When the client application running on a car calls QUERY (location) , OttoNet delivers a packet containing a query message to at least one car within distance \(R\) (the radio range) of the specified location, according to a best-effort contract. A packet containing a query is 1,000 bits in size.
RESPOND (status_info, query_packet): When the server application running on a car receives a query message, it processes the query and calls RESPOND (status_info, query_packet). RESPOND causes a packet containing a response message to be delivered to the client that performed the query, again according to a best-effort contract. A response message summarizes local traffic information ( status_info ) collected from the car's sensors and is 10,000 bits in size.

For packets containing either query or response messages, the cars will forward the packet cooperatively in best-effort fashion toward the desired destination location or car. Cars may move arbitrarily, alternating between motion and rest. The maximum speed of a car is 30 meters per second (108 kilometers per hour or 67.5 miles per hour).

Q5.1 Which of the following properties is true of the OttoNet, as described thus far?

A. Because the OttoNet is "best-effort," it will attempt to deliver query and response messages between client and server cars, but messages may be lost and may arrive out of order.
B. Because the OttoNet is "best-effort," it will ensure that as long as there is some uncongested path between the client and server cars, query and response messages will be successfully delivered between them.
C. Because the OttoNet is "best-effort," it makes no guarantees on the delay encountered by a query or response message before it reaches the intended destination.
D. An OttoNet client may receive multiple responses to a query, even if no packet retransmissions occur in the system.

Otto develops the following packet format for OttoNet (all fields except payload are part of the packet header):

structure packet GPS dst_loc // intended destination location integer_128 dst_id // car’s 128-bit unique ID picked at random GPS src_loc // location of car where packet originated integer_128 src_id // unique ID of car where packet originated integer hop_limit // number of hops remaining (initialized to 100) integer type // query or response integer size // size of packet string payload // query request string or response status info packet instance pkt; // pkt is an instance of the structure packet

Each car has a 128-bit unique ID, picked entirely at random. Each car's current location is given by its GPS coordinates. If the sender application does not know the intended receiver's unique ID, it sets the dst_id field to 0 (no valid car has an ID of 0).

The procedure FORWARD (pkt) runs in each car, and is called whenever a packet arrives from the network or when a packet needs to be sent by the application. FORWARD maintains a table of the cars within radio range and their locations, using broadcasts every second to determine the locations of neighboring cars, and implements the following steps:

F1. If the car's ID is pkt.dst_id then deliver to application (using pkt.type to identify whether the packet should be delivered to the client or server application), and stop forwarding the packet.

F2. If the car is within \(R\) of pkt.dst_id and pkt.type is QUERY, then deliver to server application, and forward to any one neighbor that is even closer to dst_loc .

F3. Geographic forwarding step: If neither F1 nor F2 is applicable, then among the cars that are closer to pkt.dst_loc , forward the packet to some car that is closer in distance to pkt.dst_loc . If no such car exists, drop the packet.

The OttoNet's QUERY (location) and RESPOND (status_info, query_packet) procedures have the following pseudocode:

1 procedure QUERY (location) 2 pkt.dst_lock ← location 3 pkt.dst_id ← X // see question 5.2. 4 pkt.src_loc ← my_gps 5 pkt.src_id ← my_id 6 pkt.payload ← “What’s the traffic status near you?” 7 SEND (pkt)

8 procedure RESPOND (status_info, query_packet) 9 pkt.dst_loc ← query_packet.src_loc 10 pkt.dst_id ← Y // see question 5.2. 11 pkt.src_loc ← my_gps 12 pkt.src_id ← my_id 13 pkt.payload ← “My traffic status is:” + status_info // “+” concatenates strings 14 SEND (pkt)

Q5.2 What are suitable values for X and Y in lines 3 and 10, such that the pseudocode conforms to the specification of QUERY and RESPOND?

Q5.3 What kinds of names are the ID and the GPS location used in the OttoNet packets? Are they addresses? Are they pure names? Are they unique identifiers?

Q5.4 Otto outsources the implementation of the OttoNet according to these ideas and finds that there are times when a QUERY gets no response, and times when a receiver receives packets that are corrupted. Which of the following mechanisms is an example of an application of an end-to-end technique to cope with these problems?

A. Upon not receiving a response for a QUERY, when a timer expires retry the QUERY from the client.
B. If FORWARD fails to deliver a packet because no neighboring car is closer to the destination, store the packet at that car and deliver it to a closer neighboring car a little while later.
C. Implement a checksum in the client and server applications to verify if a message has been corrupted.
D. Run distinct TCP connections between each pair of cars along the path between a client and server to ensure reliable end-to-end packet delivery.

Otto decides to retry queries that don't receive a response. The speed of the radio in each car is 10 megabits per second, and the response and request sizes are 10,000 bits and 1,000 bits respectively. The car's computer is involved in both processing the packet, which takes 0.1 microsecond per bit, and in transmitting it out on the radio (i.e., there's no pipelining of packet processing and transmission). Each car's radio can transmit and receive packets at the same time.

The maximum queue size is 4 packets in each car, the maximum radio range for a single hop is 250 meters, and that the maximum possible number of hops in OttoNet is 100. Ignore media access protocol delays. The server application takes negligible time to process a request and generate a response to be sent.

Q5.5 What is the smallest "safe" timer expiration setting that ensures that the retry of a query will happen only when the original query or response packet is guaranteed not to still be in transit in the network?

Otto now proceeds to investigate why FORWARD sometimes has to drop a packet between a client and server, even though it appears that there is a sequence of nodes forming a path between them. The problem is that geographic forwarding does not always work, in that a car may have to drop a packet (rule F3) even though there is some path to the destination present in the network.

Q5.6 In the figure below, suppose the car at F is successfully able to forward a packet destined to location D using rule F3 via some neighbor, N. Assuming that neither F or N has moved, clearly mark the region in the figure where N must be located.

Two dots are horizontally in line with each other, separated by some distance. The dot located in the left side of the figure is labeled F, and the dot in the right side is labeled D.

Figure \(PS.5.1\): Problem diagram for Q5.6.

Q5.7 Otto decides to modify the client software to make pipelined QUERY calls in quick succession, sending a query before it gets a response to an earlier one. The client now needs to match each response it receives with the corresponding query. Which of these statements is correct?

A. As long as no two pipelined queries are addressed to the same destination location (the dst_loc field in the OttoNet header), the client can correctly identify the specific query that caused any given response it receives.
B. Suppose the OttoNet packet header includes a nonce set by the client, and the server includes a copy of the nonce in its response, and the client maintains state to match nonces to queries. This approach can always correctly match a response to a query, including when two pipelined queries are sent to the same destination location.
C. Both the client and the server need to set nonces that the other side acknowledges (i.e., both sides need to implement the mechanism in choice B above), to ensure that a response can always be correctly matched to the corresponding query.
D. None of the above.

Q5.8 After running the OttoNet for a few days, Otto notices that network congestion occasionally causes a congestion collapse because too many packets are sent into the network, only to be dropped before reaching the eventual destination. These packets consume valuable resources. Which of the following techniques is likely to reduce the likelihood of a congestion collapse?

A. Increase the size of the queue in each car from 4 packets to 8 packets.
B. Use exponential backoff for the timer expiration when retrying queries.
C. If a query is not answered within the timer expiration interval, multiplicatively reduce the maximum rate at which the client application sends OttoNet queries.
D. Use a flow control window at each receiver to prevent buffer overruns.

Q5.9 The OttoNet is not a secure system. Otto has an idea—he observes that the unique 128-bit ID of a car can be set to be the public key of the car! He proposes the following protocol. On a packet containing a query message, sign the packet with the client car's private key. On a packet containing a response, encrypt the packet with the client car's public key (that public key is in the packet that contained the query). To allow packets containing responses to be forwarded through the network, the server does not encrypt the destination location and ID fields of those packets. Assume that each car's private key is not compromised. Which of the following statements are true?

A. A car that just forwards a packet containing queries can read that packet's payload and verify it.
B. The only car in the network that can decrypt a response from a server is the car specified in the destination field.
C. The client cannot always verify the message integrity of a response, even though it is encrypted.
D. If every server at some queried location is honest and not compromised, the client can be sure that an encrypted response it receives for a query actually contains the correct traffic status information.

Problem Set 6: The Wireless EnergyNet

\(^*\) Credit for developing this problem set goes to Hari Balakrishnan.

2005–2–7

(Chapter 1 and a little bit of 2)

Sara Brum, an undergraduate research assistant, is concerned about energy consumption in the Computer Science building and decides to design the EnergyNet, a wireless network of nodes with sensors to monitor the building. Each node has three sensors: a power consumption sensor to monitor the power drawn at the power outlet to which it is attached, a light sensor, and a temperature sensor. Sara plans to have these nodes communicate with each other via radio, forwarding data via each other, to report information to a central monitoring station. That station has a radio-equipped node attached to it, called the sink.

There are two kinds of communication in EnergyNet:

Node-to-sink reports: A node sends a report to the sink via zero or more other nodes.
EnergyNet routing protocol: The nodes run a distributed routing protocol to determine the next hop for each node to use to forward data to the sink. Each node's next hop en route to the sink is called its parent.

EnergyNet is a best-effort network. Sara remembers that layering is a good design principle for network protocols, and decides to adopt a three-layer design similar to the Chapter 1 reference model. Our job is to help Sara design the EnergyNet and its network protocols. We will first design the protocols needed for the node-to-sink reports without worrying about how the routing protocol determines the parent for each node.

To start, let's assume that each node has an unchanging parent, every node has a path to the sink, and nodes do not crash. Nodes may have hardware or software faults, and packets could get corrupted or lost, though. Sara develops the following simple design for the three-layer EnergyNet stack:

Layer Header fields Trailer fields

Layer	Header fields	Trailer fields
E2E report protocol	`location` `time`	`e2e_cksum` (32-bit checksum)
Network	`dstaddr` (16-bit network address of destination)
Layer	`recvid` (32-bit unique ID of link-layer destination) `sendid` (32-bit unique ID of link-layer source)	`ll_cksum` (32-bit checksum)

E2E report protocol

location

time

e2e_cksum (32-bit checksum)

Network

dstaddr (16-bit network address of destination)

Layer

recvid (32-bit unique ID of link-layer destination)

sendid (32-bit unique ID of link-layer source)

ll_cksum (32-bit checksum)

In addition to these fields, each report packet has a payload that contains a report of data observed by a node's sensors. When sending a report packet, the end-to-end layer at the reporting node sets the destination network-layer address to be a well-known 16- bit value, SINK_ADDR . The end-to-end layer at the sink node processes each report. Any node in the network can send a report to the sink.

If a layer has a checksum, it covers that layer's header and the data presented to that layer by the higher layer. Each EnergyNet node has a first-in, first-out (FIFO) queue at the network layer for packets waiting to be transmitted.

Q6.1 What does an EnergyNet report frame look like when sent over the radio from one node to another? Fill in the rectangle below to show the different header and trailer fields in the correct order, starting with the first field on the left. Be sure to show the payload as well. You do not need to show field sizes.

A long, thin horizontal rectangle has its left end labeled as "start of frame."

Figure \(PS.6.1\): Answer framework for Q6.1.

Q6.2 Sara's goal is to ensure that the end-to-end layer at the sink passes on (to the application) only messages whose end-to-end header and payload are correct. Assume that the implementation of the functions to set and verify the checksum are correct, and that there are no faults when the end-to-end layer runs.

A. Will using just ll_cksum and not e2e_cksum achieve Sara's goal?
B. Will using just e2e_cksum and not ll_cksum achieve Sara's goal?
C. Must each node on the path from the reporting node to the sink recalculate e2e_cksum in order to achieve Sara's goal?

To recover lost frames, Sara decides to implement a link-layer retransmission scheme. When a node receives a frame whose ll_cksum is correct, it sends an acknowledgment (ACK) frame to the sendid of the frame. If a sender does not receive an ACK before a timer expires, it retransmits the frame. A sender attempts at most three retransmissions for a frame.

Q6.3 Which of these statements is true of Sara's link-layer retransmission scheme if no node changes its parent?

A. Duplicate error-free frames may be received by a receiver.
B. Duplicate error-free frames may be received by a receiver even if the sending node's timeout is longer than the maximum possible round trip time between sender and receiver.
C. If each new frame is sent on a link only after all link-layer retransmissions of previous frames, then the sink may receive packets from a given node in a different order from the way in which they were sent.
D. If Sara were to implement an end-to-end retransmission scheme in addition to this link-layer scheme, the resulting design would violate an end-to-end argument.

Q6.4 EnergyNet's radios use phase encoding with the Manchester code. Sara finds that if the frequency of level transitions of voltage is set to 500 kilohertz, the link has an acceptably low bit error rate when there is no radio channel interference, noise, or any other concurrent radio transmissions. What is the data rate corresponding to this level transition frequency? (Specify the correct units.)

Q6.5 Consider the transmission of an error-free frame (that is, one that never needed to be retransmitted) over one radio hop from node A to node B. Which of the delays in the right column of the table below contribute to the time duration specified in the left column? (There may be multiple contributors.)

1. Time lag between first bit leaving A and that bit reaching B	A. Processing delay
2. Time lag between first bit reaching B and last bit reaching B	B. Propagation delay
3. Time lag between when the last bit of the packet was received at A and the first bit of the same packet begins to be sent by A's link layer to B	C. Queuing delay
	D. Transmission delay

Q6.6 Sara finds that EnergyNet often suffers from congestion. Which of the following methods is likely to help reduce EnergyNet's congestion?

A. If no link-layer ACK is received, the sender should use exponential backoff before sending the next frame over the radio.
B. Provision the network-layer queue at each node to ensure that no packets ever get dropped for lack of queue space.
C. On each link-layer ACK, piggyback information about how much queue space is available at a parent, and slow down a node's rate of transmission when its parent's queue occupancy is above some threshold.

Now, let's assume that nodes may crash and each node's parent may change with time.

Let us now turn to designing the routing protocol that EnergyNet nodes use to form a routing tree rooted at the sink. Once each second, each node picks a parent by optimizing a "quality" metric and broadcasts a routing advertisement over its radio, as shown in the BROADCAST_ADVERTISEMENT procedure. Each node that receives an advertisement processes it and incorporates some information in its routing table, as shown in the HANDLE_ADVERTISEMENT procedure. These routing advertisements are not acknowledged by their recipients.

An advertisement contains one field in its payload: quality , calculated as shown in the pseudocode below. The quality of a path is a function of the success probability of frame delivery across each link on the path. The success probability of a link is the probability that a frame is received at the receiver and its ACK received by the sender.

In the pseudocode below, quality_table is a table indexed by sendid and stores an object with two fields: quality , the current estimate of the path quality to the parent via the corresponding sendid , and lasttime , the last time at which an advertisement was heard from the corresponding sendid .

procedure BROADCAST_ADVERTISEMENT () // runs once per second at each node if quality_table = EMPTY and node != sink then return REMOVE_OLD_ENTRIES (quality_table) // remove entries older than 5 seconds if node = sink then adv.quality ← 1.0 else parent ← PICK_BEST(quality_table) // returns node with highest quality value adv.quality ← quality_table[parent].quality NETWORK_SEND (RTG_BCAST_ADDR, adv) // broadcasts adv over radio

procedure HANDLE_ADVERTISEMENT (sendid, adv) quality_table[sendid].lasttime ← CURRENT_TIME () quality_table[sendid].quality ← adv.quality × SUCCESS_PROB (sendid)

When BROADCAST_ADVERTISEMENT runs (once per second), it first removes all entries older than 5 seconds in quality_table . Then, it finds the best parent by picking the sendid with maximum quality, and broadcasts an advertisement message out to the network-layer address (RTG_BCAST_ADDR) that corresponds to all nodes within one network hop.

Whenever a node receives an advertisement from another node, sendid , it runs HANDLE_ADVERTISEMENT () . This procedure updates quality_table[sendid] . It calculates the path quality to reach the sink via sendid by multiplying the advertised quality with the success probability to this sendid , SUCCESS_PROB (sendid). The implementation details of SUCCESS_PROB () are not important here; just assume that all the link success probabilities are estimated correctly.

Assume that no "link" is perfect; i.e., for all i and j , p_ij is strictly less than 1, and that every received advertisement is processed within 100 ms after it was broadcast.

Q6.7 Ben Bitdiddle steps on and destroys the parent of node N at time t = 10 seconds. Assuming that node N has a current entry for its parent in its quality_table , to the nearest second, what are the earliest and latest times at which node N would remove the entry for its parent from its quality_table ?

See Figure \(PS.6.2\). The picture shows the success probability for each pair of transmissions (only non-zero probabilities are shown). The number next to each radio link is the link's success probability, the probability of a frame being received by a receiver and its ACK being received successfully by the sender.

Figure \(PS.6.2\): Network topology for some EnergyNet questions.

Q6.8 In Figure \(PS.6.2\), suppose B is A's parent and B fails. Louis Reasoner asserts that as long as no routing advertisements are lost and there are no software or hardware bugs or failures, a routing loop can never form in the network. As usual, Louis is wrong. Explain why, giving a scenario or sequence of events that can create a routing loop.

Q6.9 Describe a modification to EnergyNet's routing advertisement that can prevent routing loops from forming in any EnergyNet deployment.

Q6.10 Suppose node B has been restored to service and the success probabilities are as shown. Which path between R and S would be chosen by Sara's routing protocol and why? Name the path as a sequence of nodes starting with R and ending with S.

Q6.11 Returning once again to Figure \(PS.6.2\), recall that the nodes use link-layer retransmissions for report packets. If you want to minimize the total expected number of non-ACK radio transmissions needed to successfully deliver the packet from R to S, which path should you choose? You may assume that frames are lost independently over each link and that the link success probabilities are independent of each other. (Hint: If a coin has a probability \(p\) of landing "heads", then the expected number of tosses before you see "heads" is \(1/p\).)

Sara finds that each sensor's reported data is noisy, and that to obtain the correct data from a room, she needs to deploy \(k > 1\) sensors in the room and take the average of the \(k\) reported values. However, she also finds that sensor nodes may fail in fail-fast fashion. Whenever there are fewer than \(k\) working sensors in a room, the room is considered to have "failed", and its data is "unavailable". When that occurs, an administrator has to go and replace the faulty sensors for the room to be "available" again, which takes time \(Tr\). \(Tr\) is smaller than the MTTF of each sensor, but non-zero.

Assume that the sensor nodes fail independently and that Sara is able to detect the failure of a sensor node within a time much smaller than the node's MTTF. Sara deploys \(m > k\) sensors in each room. Sara comes up with three strategies to deploy and replace sensors in a room:

A. Fix each faulty sensor as soon as it fails.
B. Fix the faulty sensors as soon as all but one fail.
C. Fix each faulty sensor as soon as data from the room becomes unavailable.

Q6.12 Rank these strategies in the order of highest to lowest availability for the room's sensor data.

Q6.13 Suppose that each sensor node's failure process is memoryless and that sensors fail independently. Sara picks strategy C from the choices in the previous question. What is the resulting MTTF of the room?

Problem Set 7: SureThing \(^*\)

\(^*\) Credit for developing this problem set goes to Barbara Liskov.

2006–2–7

(Chapter 1)

Alyssa P. Hacker decides to offer her own content delivery system, named SURETHING. A SURETHING system contains 1000 computers that communicate via the Internet. Each computer has a unique numerical identifier ID#, and the computers are thought of as (logically) being organized in a ring as in Figure \(PS.7.1\). Each computer has successors as shown in the figure. The ring wraps around: the immediate successor of the computer with the highest ID# (computer N251 in the figure) is the computer with the lowest ID# (computer N8).

Figure \(PS.7.1\): Arrangement of computers in a ring. Computer N232's pointers to its 4 successors lead to computers N251, N8, N21, and N36. The content item C192 is stored at computer N205 because #205 is the next largest computer ID# after C192's ID#. Similarly, content item C48 is stored at its immediate successor, computer N48, and item number C165 is stored at its immediate successor, computer N174.

Each content item also has a unique ID, c , and the content is stored at c 's immediate successor: the first computer in the ring whose ID# exceeds the ID# of c . This scheme is called consistent hashing.

Alyssa designs the system using two layers: a forwarding and routing layer (to find the IP address of the computer that stores the content) and a content layer (to store or retrieve the content).

Building a Forwarding and Routing Layer. Inspired by reading a paper on a system named Chord\(^{**}\) that uses consistent hashing, Alyssa decides that the routing step will work as follows: Each computer has a local table, successors[i], that contains the ID and IP address of its 4 successors (the 4 computers whose IDs follow this computer's ID in the ring); the entries are ordered as they appear in the ring. These tables are set up when the system is initialized.

The forwarding and routing layer of each node provides a procedure GET_LOCATION that can be called by the content layer to find the IP address of the immediate successor of some content item c . This procedure checks its local successors table to see if it contains the immediate successor of the requested content; if not, it makes a remote procedure call to the GET_LOCATION procedure on the most distant successor in its own successors table. That computer returns the immediate successor of c if it is known locally in its successors table; otherwise that node returns its most distant successor, and the originating computer continues the search there, iterating in this way until it locates c 's immediate successor.

For example, if computer N232 is looking for the immediate successor of c = C165 in the system shown in Figure \(PS.7.1\), it will first look in its local table; since this table doesn't contain the immediate successor of c , it will request information from computer N36. Computer N36 also doesn't have the immediate successor of C165 in its local successors table, and therefore it returns the IP address of computer N96. Computer N96 does have the immediate successor (computer N174) in its local successors table and it returns this information. This sequence of RPC requests and responses is shown in Figure \(PS.7.2\).

Figure \(PS.7.2\): Sequence of RPCs and replies required for computer N232 to find the immediate successor of the content item with ID C165.

\(^{**}\) Ion Stoica, Robert Morris, David Karger, M. Frans Kaashoek, and Hari Balakrishnan. Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications, Proceedings of the ACM SIGCOMM '01 Conference, August 2001.

Q7.1 While testing SURETHING, Alyssa notices that when the Internet attempts to deliver the RPC packets, they don't always arrive at their destination. Which of the following reasons might prevent a packet from arriving at its destination?

A. A router discards the packet.
B. The packet is corrupted in transit.
C. The payload of an RPC reply contains the wrong IP address.
D. The packet gets into a forwarding loop in the network.

For the next two questions, remember that computers don't fail and that all tables are initialized correctly.

Q7.2 Assume that c is an id whose immediate successor is not present in successors , and \(n\) is the number of computers in the system. In the best case, how many remote lookups are needed before GET_LOCATION (c) returns?

A. \(0\)
B. \(1\)
C. \(2\)
D. \(O(\log n)\)
E. \(O(n)\)
F. \(O(n^2)\)

Q7.3 Assume that c is an id whose immediate successor is not present in successors , and \(n\) is the number of computers in the system. In the worst case, how many remote lookups are needed before GET_LOCATION (c) returns?

A. \(0\)
B. \(1\)
C. \(2\)
D. \(O(\log n)\)
E. \(O(n)\)
F. \(O(n^2)\)

Building the Content Layer. Having built the forwarding and routing layer, Alyssa turns to building a content layer. At a high level, the system supports storing data that has an ID associated with it. Specifically, it supports two operations:

PUT (c, content) stores content in the system with ID c .
GET (c) returns the content that was stored with ID c .

Content IDs are integers that can be used as arguments to GET_LOCATION . (In practice, one can ensure that IDs are integers by using a hash function that maps human-readable names to integers.)

Alyssa implements the content layer by using the forwarding and routing layer to choose which computers to use to store the content. For reliability, she decides to store every piece of content on two computers: the two immediate successors of the content's ID. She modifies GET_LOCATION to return both successors, calling the new version GET_2LOCATIONS . For example, in Figure \(PS.7.1\), if GET_2LOCATIONS is asked to find the content item with ID C165, it returns the IP addresses of computers N174 and N205.

Once the correct computers are located using the forwarding and routing layer, Alyssa's implementation sends a PUT RPC to each of these computers to store the content in a file in both places. (If one of the computers is the local computer, it performs that store with a local call to PUT rather than an RPC.)

To retrieve the content associated with a given ID, if either ID returned by GET_2LOCATIONS is local it reads the file with a local GET . If not, it sends a GET RPC to the computer with the first ID, requesting that the computer load the appropriate file from disk, if it exists, and return its contents. If that RPC fails for some reason, it tries the second ID.

Q7.4 Which of the following are the end-to-end properties of the content layer? Assume that there are no failures of computers or disks while the system is running, that all tables are initialized correctly, and that the network delivers every message correctly.

A. GET (c) always returns the same content that was stored with ID c .
B. PUT (c, content) stores the content at the two immediate successors of c .
C. GET returns the content from the immediate successor of c .
D. If the content has been stored on some computer, GET will find it.

Q7.5 Now, suppose that individual computers may crash but the network continues to deliver every message correctly. Which of the following properties of the content layer are true?

A. One of the computers returned by GET_2LOCATIONS might not answer the GET or PUT call.
B. PUT will sometimes be unable to store the content at the content's two immediate successors.
C. GET will successfully return the requested content, assuming it was stored previously.
D. If one of the two computers on which PUT stored the content has not crashed when GET runs, GET will succeed in retrieving the content.

Improving Forwarding Performance. We now return to the forwarding and routing layer and ignore the content layer.

Alyssa isn't happy with the performance of the system, in particular GET_LOCATION . Her friend Lem E. Tweakit suggests the following change: each computer maintains a node_cache , which contains information about the IDs and IP addresses of computers in the system. The node_cache table initially contains information about the computers in successors .

For example, initially the node_cache at computer N232 contains entries for computers N251, N8, N21, N36. But after computer N232 communicates with computer N36 and learns the ID and IP address of computer N96, N232's node_cache would contain entries for computers N251, N8, N21, N36, and N96.

Q7.6 Assume that c is a content ID whose immediate successor is not one of the computers listed in successors , and \(n\) is the number of computers in the system. In the best case, how many remote lookups are needed before GET_LOCATION (c) returns?

A. \(0\)
B. \(1\)
C. \(2\)
D. \(O(\log n)\)
E. \(O(n)\)
F. \(O(n^2)\)

Problem Set 8: Sliding Window\(^*\)

\(^*\) Credit for developing this problem set goes to Dina Katabi.

2008–2–7

(Chapter 1)

Consider the sliding window algorithm described in Chapter 1. Assume the topology in the figure below, where all links are duplex and have the same capacity and delay in both directions. The capacities of the two links on the left are very large and can be assumed infinite, while their propagation delays are negligible and can be assumed zero. Both sources send to the same destination node.

On the left side of the diagram, two sources (Source 1 and Source 2) are connected to router R. Both of those links have infinite capacity and a 1-way delay of 0 seconds. R is connected to a destination node on the right of the diagram; this link has a capacity of 10 segments/second and a 1-way delay of 1 second.

Figure \(PS.8.1\): Topology of the sliding window algorithm used for Problem Set 8.

Q8.1 Assume the window size is fixed and only Source 1 is active. (Source 2 does not send any traffic.) What is the smallest sliding window that allows Source 1 to achieve the maximum throughput?

Source 1 does not know the bottleneck capacity and hence cannot compute the smallest window size that allows it to achieve the maximum throughput. Ben has an idea to allow Source 1 to compute the bottleneck capacity. Source 1 transmits two data segments back-to-back, i.e., as fast as possible. The destination sends an acknowledgment for each data segment immediately.

Q8.2 Assume that acknowledgements (acks) are significantly smaller than data segments, all data segments are the same size, all acks are the same size, and only Source 1 has any traffic to transmit. In this case, which option is the best way for Source 1 to compute the bottleneck capacity?

A. Divide the size of a data segment by the interarrival time of two consecutive acks.
B. Divide the size of an ack by the interarrival time of two acks.
C. Sum the size of a data segment with an ack segment and divide the sum by the ack interarrival time.

Now assume both Source 1 and Source 2 are active. Router R uses a large queue with space for about 10 times the size of the sliding window of question 8.1. If a data segment arrives at the router when the buffer is full, R discards that segment.

Source 2 uses standard TCP congestion control to control its window size. Source 1 also uses standard TCP, but hacks its congestion control algorithm to always use a fixed-size window, set to the size calculated in question 8.1.

Q8.3 Which of the following is true?

A. Source 1 will have a higher average throughput than Source 2.
B. Source 2 will have a higher average throughput than Source 1.
C. Both sources get the same average throughput.

Problem Set 9.1: Geographic Routing \(^*\)

\(^*\) Credit for developing this problem set goes to Dina Katabi.

2008–2–3

(Chapter 1)

Ben Bitdiddle is excited about a novel routing protocol that he came up with. Ben argues that since Global Positioning System (GPS) receivers are getting very cheap, one can equip every router with a GPS receiver so that the router can know its location and route packets based on location information.

Assume that all nodes in a network are in the same plane and nodes never move. Each node is identified by a tuple \((x, y)\), where \(x\) and \(y\) are its GPS-derived coordinates, and no two nodes have the same coordinates. Each node is joined by links to its neighbors, forming a connected network graph. A node informs its neighbors of its coordinates when it joins the network and whenever it recovers after a failure.

When a source sends a packet, in place of a destination IP address, it puts the destination coordinates in the packet header. (A sender can learn the coordinates of its destination by asking Ben's modified DNS, which he calls the Domain Name Location Service.) When a router wants to forward a packet, it checks whether any of its neighbors are closer to the destination in Euclidean distance than itself. If none of its neighbors is closer, the router drops the packet. Otherwise the router forwards the packet to the neighbor closest to the destination. Forwarding of a packet stops when that packet either reaches a node that has the destination coordinates or is dropped.

Q9.1 Which of these statements are true about Ben's geographic routing algorithm?

A. If there are no failures, and no nodes join the network while packets are en route, no packet will experience a routing loop.
B. If nodes fail while packets are en route, a packet may experience a routing loop.
C. If nodes join the network while packets are en route, a packet may experience a routing loop.

Suppose that that there are no failures of either links or nodes, and also that no node joins the network.

Q9.2 Can Ben's algorithm deliver packets between any source-destination pair in a network? If yes, explain. If no, draw a counterexample in the grid below, placing nodes on grid intersections and making sure that links connect all nodes.

A grid with 4 rows and 6 columns occupies the first quadrant of a standard coordinate plane, with the horizontal axis labeled x and the vertical axis labeled y. The lower left corner of the grid is located at the origin.

Figure \(PS.9.1\): Answer grid for Q9.2.

Q9.3 For all packets that Ben's algorithm delivers to their corresponding destinations, does Ben's algorithm use the same route as the path vector algorithm described in Section 1.5.2? If your answer is yes, then explain it. If your answer is no, then draw a counter example.

Figure \(PS.9.2\): Answer grid for Q9.3.

Problem Set 10: Carl's Satellite\(^*\)

\(^*\) Credit for developing this problem set goes to Robert T. Morris.

2001–3–6…13

(Chapter 2)

Carl Coder decides to quit his job at an e-commerce start-up and go to graduate school. He's curious about the possibility of broadcasting data files through satellites, and decides to build a prototype that does so.

Carl decides to start simple. He launches a satellite into a geosynchronous orbit, so that the satellite is visible from all points in the United States. The satellite listens for incoming bits on a radio up-channel, and instantly retransmits each bit on a separate down-channel. Carl builds two ground stations, a sender and a receiver. The sending station sends on a radio to the satellite's up-channel; the receiving station listens to the satellite's down-channel.

Carl's test application is to send Associated Press (AP) news stories from a sending station, through the satellite, to a receiving station; the receiving station prints each story on a printer. AP stories always happen to consist of 1024 characters. Carl writes the code below to run on computers at the sending and receiving stations (Scheme 1).

procedure SEND_BUFFER (byte buffer[1024]) for i from 0 to 1024 do SEND_8_BITS (buffer[i])

procedure RECEIVER () byte buffer[1024] do forever ok ← RECV_BUFFER (buffer) if ok = TRUE then print buffer on a printer

procedure RECV_BUFFER (byte buffer[1024]) for i from 0 to 1024 do buffer[i] ← RECV_8_BITS () return (TRUE)

The receiving radio hardware receives a bit if and only if the sending radio sends a bit. This means the receiver receives the same number of bits that the sender sent. However, the receiving radio may receive a bit incorrectly, due to interference from sources near the receiver. The radio doesn't detect such errors; it just hands the incorrect bit to the computer at the receiving ground station with no warning. These incorrect bits are the only potential faults in the system, other than (perhaps) flaws in Carl's design. If the computer tells the printer to print an unprintable character, the printer prints a question mark instead.

After running the system for a while, Carl observes that it doesn't always work correctly. He compares the stories that are sent by the sender with the stories printed at the receiver.

Q10.1 What kind of errors might Carl see at the receiver's printer?

A. Sometimes one or more characters in a printed story are incorrect.
B. Sometimes a story is repeated.
C. Sometimes stories are printed out of order.
D. Sometimes a story is entirely missing.

Q10.2 The receiver radio manufacturer claims that the probability of receiving a bit incorrectly is one in 10⁵, and that such errors are independent. If these claims are true, what fraction of stories is likely to be printed correctly?

Carl wants to make his system more reliable. He modifies his sender code to calculate the sum of the bytes in each story and append the low 8 bits of that sum to the story. He modifies the receiver to check whether the low 8 bits of the sum of the received bytes match the received sum. His new code (Scheme 2) is below.

procedure SEND_BUFFER (byte buffer[1024]) byte sum ← 0 // byte is an eight-bit unsigned integer for i from 0 to 1024 do SEND_8_BITS (buffer[i]) sum ← sum + buffer[i] SEND_8_BITS (sum)

procedure RECV_BUFFER (byte buffer[1024]) byte sum1, sum2 sum1 ← 0 for i from 0 to 1024 do buffer[i] ← RECV_8_BITS() sum1 ← sum1 + buffer[i] sum2 ← RECV_8_BITS() if sum1 = sum2 then return TRUE else return FALSE

Q10.3 What kind of errors might Carl see at the receiver's printer with this new system?

A. Sometimes one or more characters in a printed story are incorrect.
B. Sometimes a story is repeated.
C. Sometimes stories are printed out of order.
D. Sometimes a story is entirely missing.

Q10.4 Suppose the sender sends 10,000 stories. Which scheme is likely to print a larger number of these 10,000 stories correctly?

Carl decides his new system is good enough to test on a larger scale, and sets up 3 new receiving stations scattered around the country, for a total of 4. All of the stations can hear the AP stories from his satellite. Users at each of the receivers call him up periodically with a list of articles that don't appear in their printer output so Carl can have the system re-send them. Users can recognize which stories don't appear because the Associated Press includes a number in each story, and assigns numbers sequentially to successive stories.

Q10.5 Carl visits the sites after the system has been in operation for a week, and looks at the accumulated printouts (in the order they were printed) at each site. Carl notes that the first and last stories were received by all sites and all sites have received all retransmissions they have requested. What kind of errors might he see in these printouts?

A. Sometimes one or more characters in a printed story are incorrect.
B. Sometimes a story is repeated.
C. Sometimes stories are printed out of order.
D. Sometimes a story is entirely missing.

Q10.6 Suppose Carl sends out four AP stories. Site 1 detects an error in just the first story; site 2 detects an error in just the second story; site 3 detects an error in just the third story; and site 4 receives all 4 stories correctly. How many stories will Carl have to re-send? Assume any re-sent stories are received and printed correctly.

After hearing about RAID, Carl realizes he could improve his system even more. He modifies his sender to send an extra "parity story" after every four AP stories; the parity story consists of the exclusive or of the previous four real stories. If one of the four stories is damaged, Carl's new receiver reconstructs it as the exclusive or of the parity and the other three stories.

His new pseudocode uses the checksumming versions of SEND_BUFFER () and RECV_BUFFER () to detect damaged stories.

procedure SENDER () byte buffer[1024] byte parity[1024] do forever clear parity[] to all zeroes for i from 0 to 4 do read next AP story into buffer SEND_BUFFER (buffer) parity ← parity ⊕ buffer // XOR’s the whole buffer SEND_BUFFER (parity)

procedure RECEIVER () byte buffers[5][1024] // holds the 4 stories and the parity boolean ok[5] // records which ones have been received correctly integer n // count buffers received correctly do forever n ← 0 for i from 0 to 5 do ok[i] ← RECV_BUFFER (buffers[i]) if ok[i] then n ← n + 1 for i from 0 to 4 do if ok[i] then print buffers[i] // buffers[i] is correct else if n = 4 then clear buffers[i] to all zeroes for j from 0 to 5 do if i ≠ j then buffers[i] ← buffers[i] ⊕ buffers[j] // XOR two buffers print buffers[i] // don’t print if you cannot reconstruct

Q10.7 Suppose Carl sends out four AP stories with his new system, followed by a parity story. Site 1 is just missing the first story; site 2 is just missing the second story; site 3 is just missing the third story; and site 4 receives all stories correctly. How many stories will Carl have to re-send? Assume any re-sent stories are received and printed correctly.

Q10.8 Carrie, Carl's younger sister, points out that Carl is using two forms of redundancy: the parity story and the checksum for each story. Carrie claims that Carl could do just as well with the parity alone, and that the checksum serves no useful function. Is Carrie right? Why or why not?