From: Janet Davis (jlnd_at_cs.washington.edu)
Date: Wed Feb 18 2004 - 11:21:31 PST
Stats:
Maximum: 25
Median : 23
Mean: 22.9
StdDev: 1.8
Evan reports that the most common issue was not checking the sequence
number on LSPs. Note that topology changes (and other issues) can cause
packets to be delivered in a different order than they were sent; it's
important not to replace a newer LSP with an older one.
Evan also had this to say:
> It seemed like pretty much everyone's routing worked. The
> distinguishing factor is now how *well* it worked. Suppose you set
> your node up so that it sends LSPs every 10 seconds, and updates its
> routing table 10 seconds after it recieves an LSP. This means that it
> takes 20 seconds for it to react to problems in the network. If your
> laptop took 20 seconds after plugging it in for it to be able to use
> the network, you'd send it back to the manufacturer saying it's
> broken.
>
> If you feel you had the right answer to these questions and I missed
> it, please come to my office hours and we'll discuss it.
Here are our grading criteria:
Code (20 points)
----------------
Correctness requirements (-2 points):
* LSPs are sent out both in response to topology changes and periodically
* Check sequence number before replacing LSP
* LSPs are timed out
* Dijkstra's algorithm implemented correctly (use your judgment on small bugs)
* Ping should use the routing table rather than broadcasting
* Maintain name to address mappings
Design choices and efficiency (-1 point):
* When several neighbors are added at about the same time, send a single
LSP rather than one for each new neighbor
* Send periodic LSPs less frequently than neighbor discovery
* Dijkstra's algorithm should be invoked only when the topology has
changed, not periodically or on every new LSP
* Frequency of broadcasting name to address mapping should be low
Other issues (-1/2 point):
* No hard coding of constants
* Use reasonable data structures
* Modularity of code
Praiseworthy points:
* Trigger Dijkstra's algorithm on topology change, but set a short timer
to wait for more updates before doing computation
* Favor lower-address nodes to get symmetric routes
* Use binary heap for Dijkstra's algorithm
Discussion questions (1 point each)
-----------------------------------
1) If two neighbors disagree about whether a link exists, you can't be
certain whether it exists or not in either direction. Chances are good
the link has either just come up or just failed, and the nodes are using
different timeout strategies.
2) Not necessarily due to equal cost routes.
"Yes" is fine if the algorithm favors lower-cost nodes to produce
symmetric routes.
"Not necessarily, if the network changes in flight" is a half-credit
answer, if they didn't also mention the concern over equal-cost routes.
3) Give full credit for a plausible answer for what to do in this case.
Half credit for just "packets get lost".
4) Half credit for "We get an inconsistent view of the network and routes
could be inconsistent." Full credit if routing loops are specifically
mentioned. Full credit for "And periodic reflooding of LSPs should
help this."
5) Don't want to constantly recalculate routes. Could delay
recalculations, increase cost of flaky node, etc. in response to this
problem.
-- Janet Davis jlnd_at_cs.washington.edu http://www.cs.washington.edu/homes/jlnd/ _______________________________________________ Cse461 mailing list Cse461_at_cs.washington.edu http://mailman.cs.washington.edu/mailman/listinfo/cse461
This archive was generated by hypermail 2.1.6 : Wed Feb 18 2004 - 11:21:36 PST