Homework 5 - Router Protocols
Note: In this homework, only problems 1 and 2 are required. Problem 3 is extra credit - worth an additional 50%!
Problem 1 - Link-State Algorithms (Dijkstra's Algorithm)
Use Dijkstra's shortest-path algorithm for the following network to compute the shortest path from router x to all other routers. (Note: In a real application, "router x" would be really be "subnet x")
Use the following table format to present your answer:
Step | N' | D(t),p(t) | D(u),p(u) | D(v),p(v) | etc... |
---|---|---|---|---|---|
0 | x | ... | |||
1 | ... | ||||
etc... | ... |
Recall from the example in class that:
- Dijkstra's algorithm is iterative and only 1 winning destination (with the shortest path) is picked for each round.
- N' represents the subset of all nodes that are currently in the shortest-path tree (of "winners"). At the beginning, node x only knows the shortest path to itself.
- D(v) represents the least-cost path from the source node to destination v as of this iteration
- p(v) represents the previous node (which must be a neighbor of v) along the current least-cost path from the source to v.
For tie-breaking purposes (and so we all end up with similar answers), assume that if there are multiple destinations with equal "lowest cost" routes, pick the destination that comes earlier in the alphabet. (Thus, t would win over z if both had equal costs).
After filling in the table, draw the resulting shortest-path tree from node x to all other nodes in the network.
Problem 2 - Traceroute Decoding
Wireshark was used to capture the operation of the Traceroute program on the ecs-network server and output a packet trace file. This trace was filtered to only include "necessary" packets, and omit things like the SSH session used to manage Wireshark. Included in this trace file are:
- The packets Traceroute sent to the destination server to probe the network path
- The packets that routers on the Internet replied with
- The conversation between the Traceroute host and the campus DNS server. (DNS is used both to translate the original target of the traceroute (i.e. www.sometarget.com) into an IP address, and to translate various router IP addresses into their human-friend host names, if possible. The latter operation is known as a "reverse DNS" request.)
For this problem, download the binary trace file and open it using Wireshark on your local computer. Using the saved packet data, determine the traceroute destination (hostname and IP address) and fill in the missing data in the following table:
Traceroute destination hostname: ???
Traceroute destination IP address: ???
Hop | Router DNS Name (if available) | Router IP Address |
---|---|---|
1 | ??? | ??? |
2 | ??? | ??? |
3 | ??? | ??? |
... | ... | ... |
DNS names are not available for every router.
Tip 1: The Linux command I used to generate this trace file was traceroute <destinationHostName> -N 16 -q 1 (where -N 16 means "send out 16 probes at a time" and -q 1 means "only send 1 probe for each TTL value"). You could use Traceroute and Wireshark together to generate your own trace to a known destination, compare the result in Traceroute to the packets Wireshark captured, and deduce how Traceroute makes sense of the packet stream. Or, if you think you know the answer, you could verify it by running this command on ecs-network and comparing its results to your own.
Tip 2: The UDP port numbers in the trace are important in untangling all the router responses!
Problem 3 - Distance Vector Algorithms (Bellman-Ford Algorithm)
This problem is extra credit, and worth up to an additional 50% on this homework assignment.
Use the Bellman-Ford shortest-path algorithm for the following network to compute the cost of the shortest path from router z to all other routers. Assume that each router initially knows the costs only to each of its neighbors.
In this problem, you only have to report what router z knows. But, in order to answer that, you will need to track what all the routers know. Rather than writing down all the other router tables, you might find it easier to only pay attention to cases where a router suddenly discovers a better path to a particular destination, since only those lower cost distance vectors will be communicated to the neighbors.
Use the following table format to summarize the current knowledge ("state") of router z at each stage of the calculation. You should have multiple tables to show how the algorithm repeats until stable costs are obtained.This table will have, at every stage of the calculation, the current cost of the shortest path from z (on the left) to every possible destination (represented as columns). In addition, the table also stores information obtained from other routers, specifically the costs that router z's neighbors (x and v) have communicated to z.
u | v | x | y | z | |
---|---|---|---|---|---|
v | |||||
x | |||||
z |
For example, here is the initial table from the perspective of router z. Only the costs to its direct neighbors are known initially. Unknown costs are infinity.
Cycle 0:
u | v | x | y | z | |
---|---|---|---|---|---|
v | Inf. | Inf. | Inf. | Inf. | Inf. |
x | Inf. | Inf. | Inf. | Inf. | Inf. |
z | Inf. | 6 | 2 | Inf. | 0 |
After exchanging distance vectors with its neighbors, router z learns of some new costs to previously unreachable destinations. Router z will now re-run the Bellman-Ford equation for all possible destinations. Hopefully it will determine some new costs to previously unreachable routers, and perhaps it will discover new lower-cost paths to routers it could already reach...
Cycle 1:
u | v | x | y | z | |
---|---|---|---|---|---|
v | 1 | 0 | 3 | Inf. | 6 |
x | Inf. | 3 | 0 | 3 | 2 |
z | ?? | ?? | ?? | ?? | ?? |
You should include the tables from cycle 0 and 1 in your solution, fill in the missing fields from cycle 2, and draw all subsequent iterations until router z is stable. Your final answer is just the final table, showing costs from router z to all other routers in the network.