Complete the tasks below, submit your task files on-line before the deadline, and complete your check-off interview within a week of the file submission deadline.
As always, help is available in 32-083 (see the Lab Hours web page).
For this lab, you will need wxPython (2.8.x), which has already been installed on the athena machines. To install it on your computer, visit http://www.wxpython.org/
This lab uses NetSim, a simple packet-level network simulator. You will write the code for the main components of distance-vector and link-state routing protocols.
NetSim executes a set of steps every time slot; time increments by 1 each slot. During each time slot a link can deliver one packet from source of the link to the destination of the link.
You can run the python programs for this lab using ipython or python (ipython602 and python602 on the athena machines). The lab will not work in IDLE.
To understand the different parameters one can set in NetSim, go to a shell and enter:
# python lab9_dv.py -h
(Or, in ipython, run lab9_dv.py -h)
This command prints out the various options:
-n NUMNODES, --numnodes=NUMNODES
-t SIMTIME, --simtime=SIMTIME
The "-r" option generates a random topology with the specified number of nodes (the default number of nodes is 12 and the default simulation time is 2000 time slots).
This lab has two main tasks, each with a few sub-tasks. The first task is to implement a distance-vector (DV) routing protocol. The second task is to implement a link-state (LS) routing protocol. You will test these implementations on a few different topologies that will be generated when you run the corresponding task files.
Both routing protocols should construct the minimum cost path from the Router to all the other destination addresses that are currently reachable in the network. The "destination" itself is derived from the Router class and has an "address" field that will be used as an index into the routing table and the cost table. Unless explicitly mentioned otherwise, we will use the term "minimum-cost path" and "shortest path" interchangeably,
Useful classes and data structures
The Link class: This class is defined in lab9_net.py; you don't need to modify this class, and the main fact you should know for this lab is that you can obtain the cost of a link, l, using l.cost (a variable in class Link). The other place you'll use the Link class is to populate the routing table, which (by definition) stores the Link to be used to reach any destination. We have provided a useful function in the Router class, getlink(n), which takes a neighboring Router, n, and returns the Link connecting self to n. This function is useful in constructing the routing table.
The HELLO protocol and maintaining live neighbors
The HELLO protocol has already been implemented for you in lab9_router.py (you should not need to modify this file); each Router sends a HELLO packet every HELLO_INTERVAL time slots (10 by default in NetSim). Whenever a node hears a HELLO along a link, it adds the current time, the address of the Router at the other end of the link, and the cost of that link, to self.neighbors, which is a dictionary mapping a Link to a (timestamp, address, linkcost) tuple.
If a node does not hear a HELLO for more than 2*HELLO_INTERVAL time slots on a link, it removes that node from self.neighbors and calls the Router's link_failed(link) function, giving the "failed" link as argument. In response, the routing protocol may take suitable actions.
For simple topologies, eye-balling these routes and the printed state at several nodes in the network should convince you of the health of your routing protocol implementation.
Please note that clicking on any link toggles the state of the link between "working" and "failed" states, thereby letting you test your protocol under link failures. We will want to ensure that your protocol works properly in the face of failures and recoveries.
The "Step 1", "Step 10", and "Step 100" buttons are the way in which you should step through the operation of your protocol and see what is happening by clicking on various nodes. (The GUI also provides a "play" and "step all" buttons, which aren't particularly useful for debugging.)
In any given time-slot, colored squares may appear on a link. These are packets. The packets are color-coded: green ones are HELLO packets, red are advertisements (type ADVERT), and blue are data packets. (The data packets aren't relevant to this lab.)
For both the routing protocols you will implement in this lab, you should demonstrate the correctness of the routing tables at the various nodes in the following scenarios (on any random topology) during the checkoff interview.
The file you will have to extend is lab9_dv.py. This file contains the DVRouter class, which is derived from the Router class (which in turn derives from the Node class defined in lab9_net.py. Your first task for this lab is to write the following three functions, which are the core of any DV protocol:
As explained in lecture and the lecture notes, each router in a DV protocol periodically exchanges routing advertisements with its neighbors in the network topology, containing the information about destinations and their shortest-path costs ([(dest1,cost1), (dest2,cost2), ...]). This function will be called every ADVERT_INTERVAL time slots (50 by default in NetSim) by send_advertisement(), which will take care of constructing packets with this list as its contents, and sending one such packet to each neighbor in the topology.
We are intentionally not specifying the precise behavior, leaving it to you to design it. As long as what you do in this step is consistent with what you do in make_dv_advertisement(), your protocol will work correctly. Conversely, an inconsistency will likely cause the protocol to be incorrect.
The result of integrate() is the current self.routes and self.spcost tables, which as mentioned before, are the routing table and table of shortest path costs. The underlying rule you should use is the Bellman-Ford update rule, as described in lecture: remember to add the link cost to the cost reported by the advertisement that comes from the neighbor at the other end of the link.
The integrate() step should take care to update the current route for a destination under the following conditions:
You are not required to implement mechanisms to alleviate or eliminate "counting-to-infinity", but are welcome to do so if you like.
self.LSA.get(u) returns the last LSA update originating from Router u that this Router (self) knows about. It has the format [seqnum, (n1,c1), (n2,c2), ...] where seqnum is the sequence number at u when it originated the LSA and each n_i is a neighbor of u (that u's HELLO protocol considered to be "live" when it generated the LSA numbered seqnum), and c_i is the cost of the link from u to n_i.
The details of how an LS protocol works were described in the lecture and are in the lecture notes. Each Router periodically sends its currenly live links (which we maintain in the self.neighbors dictionary, as explained earlier when we discussed the HELLO protocol). Each Router also re-broadcasts, along all its links, an LSA packet that it receives via a neighboring Router, containing an LSA originating at some other Router. This re-broadcast is done only once per LSA; to ensure this property, the Router checks the sequence number of the incoming LSA to make sure that it is larger than the last LSA heard from that originating Router. These periodic LSA broadcasts are done every ADVERT_INTERVAL time slots (50 by default in NetSim); the re-broadcasts are done when a Router receives a new LSA (using the sequence number check).
For this task, the file you will have to extend is lab9_ls.py -- your task is to write the following two functions, which are the core of any LS protocol:
Note that the self.neighbors dictionary mapping a Link to a (timestamp, address, linkcost) tuple will be useful in constructing the LSA; as mentioned above in the discussion of the HELLO protocol, neighbors keeps track of currently "live" neighboring Routers.
There is one important issue that you need to watch out for in the steps of run_dijkstra() that will set the routing table entries, self.routes, for various destinations. At the Router, as you go through the different destinations in non-decreasing order of shortest-path costs and set the route to a node to be that of its parent in the shortest path tree. If the parent is self.address (i.e., the Router running the algorithm), then you should remember to set the route to the link connecting the Router (self) to the destination. You can use the self.getlink() method for this purpose.