1.Give one-two advantages of using RED over (a) drop-head (b) drop-tail (c) Fair Queueing. A1: vs. drop-head/drop-tail: 1. RED does "early" drop and can proactively avoid congestion. 2. RED avoids large queue buildup thus improving end-to-end performance by avoiding large queueing delays. 3. drop-tail/drop-head lead to global synchronization problems because packets from multiple flows get dropped causing all of them to enter congestion avoidance at the same time -- RED avoids this 4. drop-tail has the lockout problem, i.e., a previous burst can cause subsequent connections to not get service, whereas RED avoids this (drop-head doesnt have this problem) vs. fair queueing RED is more lightweight, doesnt need per-flow state on routers (since it is specifically designed for TCP-like flows can make more assumptions on the response behavior of the end hosts) 2. Harry Bovik proposes a new ``secure network'' mechanism for next generation networks, where every pair of neighboring routers share a secret key and use this key to encrypt/decrypt packet on each link. Would you recommend that the NSF fund this proposal? Why A2: no. encryption is fundamentally an end-to-end requirement; the end-to-end argument suggests that there is no benefit from having intermediary routers do encryption. if users want private communication they would do end-to-end encryption anyway, and any link-by-link encryption would be obsolete. 3. NASA sends out a Moon probe that sends out high quality video streams back to earth. To save energy, the system communicates with earth for 10 seconds every 30 minutes. The system uses a 1 Gbps high performance communication channel and Van Jacobson's TCP protocol. A separate TCP connection is set up for each communication. Assuming there is no loss, estimate the average throughput during each 10 second interval. Make appropriate assumptions and check on Google on constants that you need. A3: one-way distance ~ 380,000 km speed of light ~ 3 * 10^8 m/s RTT ~ 2.5 seconds MSS ~ 1500 bytes ssthresh = 65535 bytes (predefined constant) Number of "data" RTTs in 10 seconds ~ 3 (after 1.5 RTT for the setup) max cwnd after 3 RTTs < ssthresh => TCP is in slow start (i.e., cwnd doubles every RTT) Number of bytes sent in 10 seconds = (1 + 2 + 4 ) * MSS = 10500 bytes Throughput = number of bytes / 10 s = 1050 bytes/sec 4. What is max-min fairness? Imagine 5 flows with demands of 10,8,7,2,1 arriving at a router with capacity 20. What are the max-min allocations to the 5 flows? A4: there are three (equivalent) definitions 1.resource allocation is said to be max-min fair when: first, the minimum data rate that a dataflow achieves is maximized; second, the second lowest data rate that a dataflow achieves is maximized and so on. 2. each flow that is bottlenecked (that is allocated less than its requested share) is allocated an equal amount of the resource, which is the fair-share allocation rate, and every flow is allocated the minimum of the fair-share rate, and its requested resource 3. max-min fairness allocation scheme has three properties a. No user receives more than its request b. no other allocation scheme satisfying condition (a) has a higher minimum allocation, c. Condition (c) remains recursively true as we remove the minimal user and reduce the total resource accordingly, In the above example, the allocations are the following {10 ,8, 7} -> 5.67 2-> 2 1 -> 1 (heres how to calculate the max-min rates. step1: 20/5 =4 --> give each flow max(request, 4) {10,8,7} -> 4 2 -> 2, 1 -> 1 step2: remaining resources = 5. divide among the remaining unsaturated flows {10,8,7} -> 5/3 step 3: total allocation {10,8,7} -> 4 + 5/3 2 -> 2 1 -> 1 5. In the ``End-to-End Routing Behavior in the Internet'' study, Vern Paxson introduced two metrics to characterize two aspects of paths' stability. a. What are the two metrics? (i.e., what aspects of the routes do they characterize?) b. Which one was most difficult for him to assess and why? A5: The two metrics are prevalence (probability that we observe the same route at a later time) and persistence (how long before the route changes). persistence is harder -- needs high-frequency measurements or needs measurements to determine if routing changes on short time scales 6. In the Multicast scheme suggested by Deering a. Does the sender need to know the membership of the group? b. Does the sender need to be a member of the group? c. What do table entries maintained by routers consist of? d. How does a participant join a group? A6: a. no, b. no all members of a host group are identified by a destination multicast address, the sender needs not know the membership of the group and need not itself be a member of the group. It only needs to know the multicast address of the host group. c. A single multicast address may have multiple outgoing branches, table entries consist of variable-length records of the form: (address, (outgoing-branch, age), (outgoing-branch, age), . . . ). The age field allows to handle the dynamic memberships of participants joining and leaving the group. for specific solutions: Reverse Path Flooding (RPF): no additional table entries are needed (except maybe a list of multicast addresses) Reverse Path Broadcasting (RPB): an additional field called "children" for each routing table entry. children is a bitmap (#bits = #incident links). bit for link j in the entry for "destination" is set if j is a child link of this router for broadcasts originating at "destination". Truncated Reverse Path Broadcasting (TRPB): Keep a list, for each incident link, of which groups are present on that link. Reverse Path Multicast (RPM): each router needs to store non-membership reports. in the worst case, the number of NMRs that a router must store is on the order of the number of multicast sources active within a T_maxage period, times the average number of groups they each send to in that period, times the number of adjacent routers. With link-state: for each link, the set of groups that have members on that link. or a cache of records of the type (source, group, min-hops), where min-hops is a vector of distances specifying min number of hops required to reach the nearest descendant group member via each link. d. broadcast/announce a "join/membership" message with the multicast group address as part of the join message.