Project 1 – Distance Vector Routing
Due: Oct 7, XXXXXXXXXX:59 PM
1 Problem Statement
The goal of this project is for you to learn to implement distributed algorithms for intradomain routing,
where all routers run an algorithm that allows them to transport packets to their destination, but no central
authority determines the forwarding paths. You will implement code to run at a router, and we will provide
a routing simulator that builds a graph connecting your routers to each other and to simulated hosts on
the network. By the end of this project, you will have implemented a version of a distance vector protocol
that computes efficient paths across the network.
2 Getting a bit more Concrete
In much of the class material, we discussed routing abstractly, i.e., the algorithms discussed were used on
graphs and computed distances between every pair of nodes. In the real world, we have both switches
outers
and hosts, and you’re primarily concerned with whether hosts can reach other hosts. Which is to say, fo
the purposes of this assignment, you need not compute routes to other routers—only to other hosts.
Similarly, we often speak about abstract links. Links in the real world are often a combination of a port (o
interface) on one device, a cable, and a port on another device. A device is often not aware so much of
a link as a whole as it is aware of its own side of the link, i.e., its own port. Ports are typically numbered.
When a device sends data out of one of its own ports, the data travels through the cable and is received by
the port on the other side. The API functions in the simulator reflect this: they deal in ports, not in links.1
3 Simulation Environment
You will be developing your router in Python 3.8 under a simulation environment provided by us. The
simulation environment, as well as your router implementation, lives under the simulator directory; you
should cd into this directory before entering any terminal commands provided in this document.
In the simulation environment, every type of network device (e.g., a host or your router) is modeled by a
subclass of the Router class. Each Router has a number of ports, each of which may be connected to a
neighboring entity (e.g., a host or another router). Each link connecting two entities has a latency—think
of it as the link’s propagation delay. Your Router sends and receives Packet’s to and from its neighbors.
The Router, Packet and Ports classes are defined in the cs168.dv module. Relevant methods of these
classes are displayed in Figures 1 and 2 3; now might be a good time to skim through them. You can learn
more about the simulation environment from the Simulator Guide.
Before we begin, let’s make sure that your Python version is supported. Type in your terminal:
$ python --version
You should be good to go if the printed version has the form Python 3.8.*.
1Don’t get these confused with the logical “ports” that are part of transport layer protocols like TCP and UDP. The ports
we’re talking about here are actual holes that you plug cables into!
CS 168, Fall 2022 – Project 1 2/ 16
class Router (api.Entity)
add_static_route (self, host, port)
Adds a static route to a host directly connected to this router.
Called by the framework when a host is connected.
host - the host that got connected
port - the port that the host got connected to
You should ove
ide this method.
handle_data_packet (self, packet, in_port)
Called by the framework when a data packet a
ives at this router.
packet - a Packet (or subclass)
in_port - port number it a
ived on
You should ove
ide this method.
send_routes (self, force=False, single_port=None)
Send route advertisements for all routes in the table.
force - if True, advertises ALL routes in the table; otherwise, advertises
only those routes that have changed since the last advertisement.
single_port - if not None, sends updates only to that port; to be used in
conjunction with handle_link_up.
You should ove
ide this method.
handle_route_advertisement (self, route_dst, port, route_latency)
Called when the router receives a route advertisement from a neighbor.
oute_dst - the destination of the advertised route.
oute_latency - latency from the neighbor to the destination
port - the port that the advertisement a
ived on.
You should ove
ide this method.
expire_routes (self)
Clears out expired routes from table.
You should ove
ide this method.
handle_link_up (self, port, latency)
Called by the framework when a link is attached to this router.
port - local port number associated with the link
latency - the latency of the attached link
You should ove
ide this method.
handle_link_down (self, port)
Called by the framework when a link is unattached from this router.
port - local port number associated with the link
You should ove
ide this method.
send (self, packet, port)
Sends the given packet out on the specified port.
packet - the packet to forward.
port - the port for the packet to be sent on.
Do not ove
ide this method.
send_route (self, port, dst, latency)
Creates a routing packet with the specified destination and latency
and sends the packet out on the port.
Note that the destination is not the destination of the packet
ut the advertised route destination.
port - the port for the route to be sent on.
dst - the destination being advertised by the route.
latency - the latency for the advertised route.
Do not ove
ide this method.
CS 168, Fall 2022 – Project 1 3/ 16
log (self, format, *args)
Produces a log message in Python terminal
format - The log message as a Python format string
args - Arguments for the format string
Do not ove
ide this method.
s_log (self, format, *args)
Logs the only these messages, if this router is selected in the simulator.
format - The log message as a Python format string
args - Arguments for the format string
Do not ove
ide this method.
Figure 1: Relevant methods of the Router superclass.
class Packet (object)
self.src
Packets have a source address.
You generally don't need to set it yourself. The "address" is actually a
eference to the sending Entity, though you shouldn't access its attributes!
self.dst
Packets have a destination address.
In some cases, packets aren't routeable -- they aren't supposed to be
forwarded by one router to another. These don't need destination addresses
and have the address set to None. Otherwise, this is a reference to a
destination Entity.
self.trace
A list of every Entity that has handled the packet previously. This is
here to help you debug. Don't use this information in your router logic.
Figure 2: Relevant methods of the Packet class.
class Ports (object)
get_latency (self, port)
Returns the latency of the link associated with that port.
port - the port whose latency will be returned.
get_all_ports (self)
Returns a list of all of the active ports connected to this router.
Figure 3: Relevant methods of the Ports class.
CS 168, Fall 2022 – Project 1 4/ 16
h1 h2 h3
s1 s2 s3
Figure 4: Linear topology with three hosts. Circles
denote hosts, squares denote routers, and lines de-
note links. A link has a latency of 1 unless otherwise
specified.
Figure 5: Sending a “ping” from the visualize
in the hub example. (Packets shown are “pong”
packets sent by h3 back to h1 being flooded by
hub s2.)
4 Warm-up Example: Hu
To get you started, we have provided an implementation of a hub—a network device that floods any
packet it receives to all of its ports (other than the port that the packet came from). The hub is already
implemented and you don’t need to submit anything for this section.
Take a look at the hub implementation in examples/hub.py. Having no need to record any routes, the hu
only implements the handle_data_packet method to flood data packets.
Let’s try out the hub on a linear topology with three hosts (Figure 4):
$ python3 simulator.py --start --default-switch-type=examples.hub topos.linear --n=3
You can now access the visualizer at http:
XXXXXXXXXX:4444 using your
owser; you should see the
hosts and routers displayed against a purple background. Let’s now make host h1 send a ping packet to
host h3. You can either type into the Python terminal:
h1.ping(h3)
or you can send the ping from the visualizer by: (1) selecting h1 and pressing A on the keyboard; (2)
selecting h3 and pressing B ; and (3) pressing P to send a ping from host A to host B (Figure 5).
You should see the “ping” and “pong” packets being delivered between h1 and h3. You should also see
oth packets delivered to h2 despite it not being the recipient. This behavior is expected since the hu
simply floods packets everywhere. You may also observe what’s going on from the log messages printed to
the Python terminal:2
WARNING:user:h2:NOT FOR ME:
h3 ttl:17> s1,s2,h2
DEBUG:user:h3:rx: h3 ttl:16> s1,s2,s3,h3
WARNING:user:h2:NOT FOR ME: h3 ttl:16
s3,s2,h2
DEBUG:user:h1:rx: h3 ttl:16
s3,s2,s1,h1
2You can see a ttl field printed for each packet. The simulator automatically assigns each packet a “time to live” (TTL)—
any packet will only be forwarded up to some maximum number of times. The TTL is managed entirely by the simulator; you
should not read or write the ttl field.
http:
XXXXXXXXXX:4444
CS 168, Fall 2022 – Project 1 5/ 16
Recall from class that flooding is problematic when the network has loops. Let’s see this in action by
launching the simulator with the topos.candy topology, which has a loop (Figure 6):
$ python3 simulator.py --start --default-switch-type=examples.hub topos.candy
Now, send a ping from host h1a to host h2b. You should be seeing a lot more log messages in the terminal,
and the visualizer should be showing routers forwarding superfluous packets for quite a while. Oops! This
is why our next step will be to implement a more capable distance vector router.
s1 s2
s3
s4 s5h1a
h1
h2a
h2
3 2
2
Figure 6: The topos.candy topology, which has a loop. A link has latency 1 unless otherwise specified.
We’ll be using this topology for demonstrative purposes throughout the project.
5 Distance Vector Router: Working Section
We’ve provided a skeleton dv_router.py file with the beginnings of a DVRouter class for you to flesh out.
The DVRouter class inherits from the DVRouterBase class.
To guide your implementation of DVRouter, we have split the implementation process into three sections,
each of which contains a subset of the ten total stages and focuses on one aspect of the router. You
should follow along stage by stage, and by the end, you will have implemented a functional distance vecto
outer!
Testing
To help you check