Project requirement is attached
Project 1 – Distance Vector Routing Due: Oct 7, 2022 11: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/routers and hosts, and you’re primarily concerned with whether hosts can reach other hosts. Which is to say, for 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 (or 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 override this method. handle_data_packet (self, packet, in_port) Called by the framework when a data packet arrives at this router. packet - a Packet (or subclass) in_port - port number it arrived on You should override 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 override this method. handle_route_advertisement (self, route_dst, port, route_latency) Called when the router receives a route advertisement from a neighbor. route_dst - the destination of the advertised route. route_latency - latency from the neighbor to the destination port - the port that the advertisement arrived on. You should override this method. expire_routes (self) Clears out expired routes from table. You should override 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 override 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 override 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 override 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 but 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 override 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 override 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 override 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 reference 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 visualizer in the hub example. (Packets shown are “pong” packets sent by h3 back to h1 being flooded by hub s2.) 4 Warm-up Example: Hub 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 hub 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://127.0.0.1:4444 using your browser; 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 both packets delivered to h2 despite it not being the recipient. This behavior is expected since the hub 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://127.0.0.1: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 h1b h2a h2b 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 vector router! Testing To help you check