HW 2 CS 6390, Spring 09

Due Fri April 10 8am

Question 1 - PIM

Consider the shortest-path tree (SPT) for a source S and the rendezvous-point tree (RPT). Show an example in which the intersection of the SPT of S and the RPT form a loop, and how how PIM would behave under this situation.

Note that if we use min-hop routing, and the links consist of only those indicated by the edges, then min-hop routing would create the above trees.

To prevent the multicast message from going around from one tree to the next, in PIM B would prune itself (selectively for S) from the RP tree (since it has a parent in S), similarly, A would selectively prune itself from the RP tree (i.e. from B).

Question 2 - Interdomain Multicast

We discussed two techniques for inter-domain multicast: single-source multicast and PIM with MSDP. Compare the two against each other, i.e., the advantages and disadvantages of each.

ANSWER

SSM:

Advantages – impossible to run out of multicast addresses (each IP address is now a multicast address), better control (security etc) as to who can transmit data over the channel.

Disadvantages – if there are sources which generate little data and a tree is not needed, then they must send their data via a “host relay”, which involves the application layer.

PIM with MSDP:

Advantages – no need for a session relay, source-trees are possible if desired.

Disadvantages – less control of who can send (any source multicast), flooding of MSDP source active messages, and easy to run out of multicast addresses.

Question 3 - AODV

Show by an example that if an intermediate node X receives a rreply for source S and destination D, such that the metric for D (seq#, hopcount) in the rreply is better than the metric for D at X, then X MUST update its metric to that of the message. Briefly discuss why this must be done.

ANSWER

Assume we have the following (arrows indicate the path of a RREQ)

S ---> . . . ---> Q ---> X ---> Y ---> . . . . ---> D

S sends a rreq looking for D, D sends a rreply, which goes back to S via Y and X. Assume that X’s next hop to D at the moment is some other neighbor Z (not Y) with a metric to D worse than that of the rreply. Since X points to Z and not Y, it chooses not to update its routing table (and keeps pointing to Z and keeps the lower metric)

However, X has to forward the packet to Q. If Q has never heard of D, it will set a routing table entry to D with X as the next hop, and using the seq number of the rreply

Thus, Q ---> X, and metric at Q is better than the metric at X. This violates our requirement on the metric (must improve at each hop) and it could lead to loops.

Question 4 - AODV

Assume that a node X, after not using the routing table entry for a destination D, times out and removes D from its routing table (and hence forgets everything about D). In this case, is it possible for a routing loop to be formed? Argue why yes or why no.

ANSWER

Consider the following network path:

A ---> B ---> C ---> D

The arrow indicates the next hop to the destination, which is node D. Assume D’s seq no at A is less than that at B which is less than that at C which is less than that at D.

Assume C timeouts first, and forgets about D (removing it from its routing table). We thus have

A ---> B ---> C (C has no next hop to reach D, not even information that D exists, since D’s entry in C’s routing table is removed)

Assume that some node X sends a RREQ looking for D. This RREQ passes via C (which lets it go by), and assume C and A are neighbors (C moved closer to A or whatever) and the RREQ arrives at A. A, since it has information about D, sends an early RREPLY back to X (and hence along C). C then learns that D is in the direction of A, and points to A

A ---> B ---> C ---> A

a loop is thus formed.

Don’t ask me how the standard avoids this. They must have a way, but this is possible given what we have covered about the protocol in class.

Question 5 - MPLS

Assume that we are doing MPLS over ATM switches (which are now "label-switching routers", i.e. routers that handle IP but use ATM hardware). Assume that we do destination-based forwarding MPLS over these routers.

a) Should label-merging or non-label-merging be used? Why?

b) Assume that ATM cells have a bit in the header, and that reassembly of packets is done as follows: all cells of a packet have 0 in this bit, except the last one, which has a 1 in this bit (i.e. a 1 in the bit marks the last cell in the packet) Under this reassembly method, is there something that switches can do so that label-merging can be used?

ANSWER

a) Non-label merging must be used. If we use label merging, given that IP packets are broken into multiple ATM cells, it is possible that cells from different packets (arriving over different links) could be merged together before being forwarded, the destination then would not be able to separate the cells into those that belong to different IP packets.

b) Under that reassembly method, what a switch can do is, on each input VC, as cells arrive, buffer all cells until a 1 is received, and then transfer all the cells at once into the output queue of the output VC (without merging them with cells of another input VC). In this way, cells from different IP packets are not merged together.

Question 6 - Designing a Header

You are hired to design a reliable byte-stream protocol that uses a sliding window (like TCP). This protocol will run over a 1 Gbps network. The RTT of the network is 140 ms, and the maximum segment life is 60 seconds. How many bits would you include in the Advertised Window and Sequence Number fields of your protocol header?

ANSWER

The window size (in bytes) must be RTTxBandwidth = (10^9/8) × 0.14 = 17500000 bytes. We need therefore, 25 bits for the advertized window (allows a maximum window size of 33554431 bytes).

In 60 seconds, (19^9/8) × 60 = 7500000000 bytes can be transmitted. They must all have unique sequence numbers. Therefore, we need 33 bits for the sequence numbers

Question 7 - TCP Connection Management

If server A accepts a TCP connection from client B, then during the three-way handshake A sent its initial sequence number to B and received an acknowledgment from it. Therefore, another client C can pretend to be B in the following way:

· C sends a SYN packet to open TCP connection to A pretending to be B

· A sends its SYN+ACK packet with its initial sequence number as part of the three-way handshake to B, and waits for the acknowledgement

· B ignores, i.e. does not respond to A's SYN+ACK packet

· C sends an acknowledgement to A pretending to be B

One would argue, however, that C cannot properly acknowledge A because it does not receive A's initial sequence number.

The algorithm for choosing the initial sequence number gives unrelated hosts a fair chance of guessing it. Specifically, A selects the initial sequence number based on a clock value at the time of connection. RFC 793 specifies that this clock value be incremented every 4 microsecs; common Berkeley implementations once simplified this to incrementing by 250000 once per second.

(a) Given this simplified increment-once-per-second implementation, explain how C could masquerade as B in at least the opening of a TCP connection.

(b) Assuming real RTT can be estimated to within 40 ms, about how many tries would you expect it to take to implement the strategy of part (a) with the unsimplified "increment every 4 microsecs" TCP implementation?

ANSWER

a)

1. C connects to A, and gets A’s current clock-based sequence number SN₁.

2. C sends a SYN packet to A, pretending to be B.

3. A sends SYN+ACK, with SN2 to B, which we are assuming is ignored.

4. C makes a guess at SN₂, e.g. SN1 plus some suitable increment (RTT + t seconds passed, see diagram below), and sends the appropriate ACK to A (pretending to be B), along with some data that has some possibly malign effect on A.

5. C does nothing further, and the connection either remains half-open indefinitely, or else is reset, but the damage is done

b) In one 40ms period there are 40ms/4µsec = 10000 possible sequence numbers; we would expect to need about 10000 tries.