代写CS 168 Fall 2024代做Python编程

日期：2024-09-27 12:31

CS 168 Fall 2024

Project 2:Distance-Vector Routing

In this project,you will write a distance-vector routing protocol.We have provided simulator code that you can use to visualize your protocol in action.

Lectures needed for this project:Lecture 6(Routing States),Lecture 7 (Distance-Vector Protocols).

You can work on this project alone,or with one partner.You can keep the same partner from Project 1,or choose a different partner.Reminder: Our course policies page has a collaboration policy that  youmust follow.

Setup

Python Installation

This project has been tested to work on Python 3.8.(It probably works on newer versions of Python as well,but use at your own risk.)

If you run python3 --version or python --version in your terminal and you see output of the form. python 3.8.*, you're all set.

Starter Code

Download a copy of the starter code here.

We recommend making frequent backups of your code.Some parts of the project will require you to modify code that you wrote earlier,and you might want to revert your  changes to start over from an earlier save point.

You should only edit dv router.py.There are comments clearly indicating the places where you should fill in code.

Guidelines:

·Don't  modify  any other files. ·Don't add any new files.

·Don't  add any  imports.

·Don't edit any code outside the sections indicated by the comments.

·Don't add any hard-coded global variables.

·Adding helper methods is fine (and encouraged in the last part).

·In general,if we haven't told you to use something,you probably don't need it.Our goal is not to trick you!

In   your   terminal,use    cd   to   navigate    to   the cs168-fa24-proj2-routing/simulator directory.All     of

the Python commands should be run from this directory.

New Spec

Note:This spec has been rewritten for Fall 2024 to be clearer and provide a few extra hints.It may contain bugs.

If you would like to work off the previous version of the spec,you can find ithere.

Project Overview

This project is split into 3 sections,with a total of 10 stages across all sections.

Each stage has its own unit tests,provided to you locally.Your grade will be determined only by these unit tests (no hidden tests).

To run a unit test,run this command,replacing 5 with the number of the stage you want to test:

python3  dv_unit_tests.py  5

Warning:Stage 10 is a good deal longer than the other stages,so plan accordingly

Warm-Up Example:Hub

Some assumptions before we get started:

·In this project,your code will find routes between hosts.You don't need to find routes to other routers.

·In this project.our forwarding tables will map destinations to numbered physical ports,instead of next-hops.For example,a row of the table might say:“Packets   destined for h1 should be sent out of port 1.”

To get you started,we've provided an implementation of a hub in examples/hub.py.The hub  is a network device that takes any incoming packet,and forwards that packet out of all its ports (except the port the packet came from).

Let's run the simulator on a linear topology with three hosts:

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 in your browser.You should see the hosts and routers displayed against a purple background.

Now,let's make host h1 send a ping packet to host h3.You can either type in the Python terminal:

h1.ping(h3)

Or,you can send the ping from the visualizer by:(1)clicking h1 and pressing A,(2) clicking h3 and pressing B,and (3)pressing p to send the ping from A to B.

You should see the"ping"packet sent from  h1 to  h3.Then,you should see the  reply

“pong”packet sent from h3 to h1.You should also see both packets delivered to h2,even though h2 isn't the recipient.This behavior. is expected,because the hub floods packets   everywhere.

You can also observe what's going on by reading the log messages printed to the Python terminal (you can ignore the TTL field,you won't touch it in this project).

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

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:

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!Your job in this project will be to implement a more capable distance-vector router.

You don't need to modify or submit anything for this section.

Code Overview

You will be implementing the DVRouter class in dv router.py,which represents a single router.

Some useful helper classes are implemented in dv.py (you can read this file,but don't modify it).We've also described them below.

Table

The instance variable self.table is aTable object representing the forwarding table inside the router.

The Table object is a dictionary,where the keys are destinations,and values are TableEntry objects.

Each TableEntry object    contains:

·dst:The destination  for  this  route.

· port :The port that packets to the destination should be sent out of.

· latency:The latency("cost")of the route from this router to the destination. ·expire_time:The timestamp (in seconds)at which this route expires.Use

api.current time() to get the current time,and add seconds to indicate a time in the future.

TableEntry   objects    are   immutable,so    if    you   want    to   update    an    entry,you   should    create    a

new TableEntry with      updated      attributes.

Example usage:

t    =Table()

t[h1]=TableEntry(dst=h1,port=p1,latency=10,expire_time=api.current_time()+20) t[h2]=TableEntry(dst=h2,port=p2,latency=20,expire_time=api.current_time()+20) for host,entry in t.items(): #<--This is how you iterate through a dict.

print( "Route  to  {}has  latency  {}". format(host,entry.latency)) This corresponds to a table that looks like this:

Key	Value(TableEntry)
Destination	Destination	Port	Latency	Expire Time
h1	h1	p1	10	20 seconds later
h2	h2	p2	20	20 seconds later

Ports

The instance variable self.ports is a Ports object representing the links connected to the router.

The Ports object contains a dictionary,where each key is a link(port),and the corresponding value is the latency (cost)along that link.

To get the latency along the link connected to port p,you can use:

self.ports.get_latency(p)

To iterate through all the ports,you can use:

for  p in   self .ports.get_all_ports():

Flags

The following flags identify what mode the router is in.We'l tell you when to include them in the code.Your code should not be reassigning these flags to True or False.

● self.SPLIT HORIZON

● self.POISON REVERSE

self.POISON ON LINK DOWN

· self.POISON          EXPIRED

self.SEND     ON     LINK     UP

Stage 1:Installing Static Routes

Foreach host directly connected to your router,you should record a static route to that host.

Your Task

Implement add static route.

Assign an expire time of FOREVER for the new route.

The framework will magically call the code you write here any time a new static route needs to be installed.

Testing and Debugging

To check your work,run the unit tests:

python3  dv_unit_tests.py  1

To debug,you can start up the simulator,and use the terminal to print out the tables inside each router.For example,to print the table inside s1:

print(s1.table)

If you're debugging in the code that you wrote,you can print out your own table like this:

print(self.table)

Check Your Understanding

Now that we've implemented static routes,what do you expect to happen if we try to send a packet along a path?

To find out,start up the simulator and open http://127.0.0.1:4444 in your browser:

python3 simulator.py --start    --default-switch-type=dv_router topos.simple

Try to send a ping from host h1 to host h2,e.g.by typing h1.ping(h2) in the terminal. What happened?Did it align with your expectation?

Stage 2:Forwarding

We've added entries to the routing table,but we need to actually use them to forward packets.

Your Task

Implement handle_data_packet.

This method will be called each time a data packet arrives at your router. Hint:To   send   a   given packet out   of   a   given   port,you   can   use:

self.send(packet,port=port)

If no route exists for the packet's destination,you should drop the packet (do nothing).

If the latency along the outgoing link is greater than or equal to INFINITY,you  should  also drop the packet.

Testing  and  Debugging

To check your work,run the unit tests: python3    dv_unit_tests.py    2

Check Your Understanding

Start the simulator from the previous stage again:

python3 simulator.py --start --default-switch-type=dv_router topos.simple

Again,try to send a ping from host h1 to host h2,e.g.by typing h1.ping(h2) in  the terminal.Hopefully the packet arrived this time!

You've finished the first section!Next,let's add more routes to our table.

Stage 3:Sending Advertisements

Check Your Understanding

Given our current implementation,what should happen when pings are sent from one host to the other in these topologies?

Topology 1: h1  ---s1 ---h2

Topology 2:h1  ---s1 ---s2 ---h3

Do the pings work in both topologies?Only one of them?Neither of them? To find out,start the simulator again to run through these two scenarios:

python3 simulator.py --start --default-switch-type=dv_router topos.simple

We have a problem in Topology 2.The routers collectively know about both destinations, but each router by itself doesn't know about both destinations.

To fix this,let's have routers exchange advertisements so they can learn about other destinations in the network.

Your Task

Implement send routes.

For now,you can assume force=True and single port=None,and  ignore  those arguments.

The framework will periodically call this function for you,so that your router periodically advertises routes to all of its neighbors.

Hint:To send a message out of a specific port,saying that you can reach a specific dst with a specific latency,you can  use:

self.send_route(port,dst,latency)

Testing  and  Debugging

To check your work,run the unit tests: python3   dv_unit_tests.py   3

Check Your Understanding

What happens now if we try to send a ping in Topology 1 and Topology 2?

To find out,start the simulator again and try it out.You'll notice that routing advertisements (purple dots)are periodically being sent out of each router.

However,the ping in Topology 2 stilldoesn't work.

Stage 4:Handling Advertisements

Your router now sends advertisements,but it also needs to handle any advertisements it receives!In particular,we'll need to implement Rule 1(Bellman-Ford update)and Rule 2  (Updates From Next-Hop)of distance-vector.

Your Task

Implement handle route   advertisement.

The framework will call this for you every time your router receives an advertisement.

If the advertised route is equally good as the current route,tiebreak by preferring the   current route.In other words,only accept an advertised route if it is strictly better than the current route.

Reminder:If you get an advertisement for a destination that's not in the table,you should always accept it.

Reminder:If you get an advertisement from the current next-hop,you should always accept it.This is Rule 2 (Updates From Next-Hop)of distance-vector.

If you update the table,set the expire time of the new entry to

api.current time()+self.ROUTE TTL.(By default,this is 15 seconds in the future.)

Testing and Debugging

To check your work,run the unit tests: python3    dv_unit_tests.py    4

Check Your Understanding

Why did we choose to tiebreak by preferring the current route?What if we preferred the new route instead?

There's a trade-off between correctness and stability here.

To see what we mean by stability,temporarily change your implementation to tiebreak by preferring the new route (accept advertised route if it's equally good as the current

route).

Then,start the simulator with the square topology:

python3 simulator.py --start --default-switch-type=dv_router topos.square

Send a bunch of pings between the two corners of the square.Notice that packets

between the same two hosts can take different paths.We consider this to be unstable, and suboptimal.

(Preview:Packets taking different paths might end up arriving out-of-order,and this causes TCP,the Layer 4 reliability protocol,to slowdown.)

Now,undo your temporary change,so that you again tiebreak by preferring the current route (only accept advertised route if it's strictly better).

Then,start the simulator again and send a bunch of pings again.Our packets always take the same path now!

So,what's the trade-off?Preferring the current path is more stable.On the other hand,a new route represents state that is more recent and therefore more indicative of the

current state of the network.

Stage 5:Handling Timeouts

Next,let's implement Rule 3 (Expiring)of distance-vector.

Check Your Understanding

What happens if a link goes down?To find out,start the simulator with the candy topology:

python3 simulator.py --start --default-switch-type=dv_router topos.candy

Wait for all routes to propagate.Then,remove the link between routers s4 and s5.You

can either select the two routers and press E in the browser,or you can type s4.unlinkTo(s5)in the terminal.

Now,try sending a ping from h1a to h2b.Even though there's still a path through s3, you'll see the packet get forwarded to s4 and then dropped!

Router s4 is trying to forward to s5,to which it is no longer connected!

Your Task

Implement expire_routes.

The framework will call this function periodically for you.Your job is to go through the forwarding table entries and delete any entries that are expired.

Optional,ungraded:When you delete an expired route,use self.s_log or self.log to  print out a message in the terminal.

Hint:To remove a table entry with key h,you can use: self.table.pop(h)

Testing  and  Debugging

To check your work,run the unit tests: python3    dv_unit_tests.py    5

Check Your Understanding

Start up the simulator with the candy topology again:

python3 simulator.py --start --default-switch-type=dv_router topos.candy

Again,bring  down  the   link,e.g.s4.unlinkTo(s5).Start sending a bunch of pings from h1a     to  h2b.Roughly  15  seconds  after the  link  goes  down,the old  route will  expire,and future pings should be forwarded correctly along the alternate route!

You've finished the second section!Next,let's  make  our  router  more efficient.

Stage 6:Split Horizon

Next,let's  implement  Rule  5A  (Split  Horizon)of  distance-vector.

Check Your Understanding

Start up the simulator with the linear topology with 3 hosts:

python3 simulator.py --start --default-switch-type=dv_router topos.linear--n=3

Wait for all routes to propagate.

Send a ping from h3 to h1.This should work.

Next,bring  down  the  link  between  s1  and  s2,e.g. s1.unlinkTo(s2).

Now,try sending pings from h3 to h1.You should see packets get dropped at s2.

Eventually,the route at s2 will timeout.and s2 will get a new advertisement from s3. Now,when you send a  ping from  h3 to  h1,what  happens,and why?

How  long will this  routing  loop  continue?What  is  the  larger  problem,and  how  can  we tackle this issue?

Your Task

Modify send routes to support split horizon if the self.SPLIT HORIZON flag is True.

Testing and Debugging

To check your work,run the unit tests: python3    dv_unit_tests.py    6

Check Your Understanding

Set self.SPLIT HORIZON to True  in  your code,and  run  the same demo again.The  routing loop  problem  should  be  solved  now!

Stage 7:Poison Reverse

Next,let's implement Rule 5B(Poison Reverse)of distance-vector.

Check Your Understanding

Set self.SPLIT HORIZON to False,and start up the simulator with the double triangle topology:

python3  simulator.py  --start    --default-switch-type=dv_router   topos.double_triangle Disconnect s2 by removing all links that connect it to other routers:

s2.unlinkTo(s1) s2.unlinkTo(s3) s2.unlinkTo(s4)

Let's see if split horizon will save us!Turn on split horizon and re-run the demo. Can we do better than this,and if so,by how much?

Your Task

Modify send routes to implement poison reverse advertisements if the self.POISON REVERSE flag is True.

Note: self.POISON REVERSE and self.SPLIT            HORIZON will       never        be       True        at       the       same        time.They

could both be False,or one of them could be True.

Testing and Debugging

To check your work,run the unit tests: python3  dv_unit_tests.py  7

Check Your Understanding

Set self.POISON REVERSE to True,and re-run the double triangle demo from earlier.How long will it take to reach the correct state now?

Stage 8:Counting to Infinity

Next,let's implement Rule 6(Count to Infinity)of distance-vector.

Check Your Understanding

Recall that split horizon and poison reverse can prevent length-2 routing loops,but not longer ones.

To see why,start the simulator with the loopy topology:

python3 simulator.py --start  --default-switch-type=dv_router topos.loopy

Wait for all routes to propagate.

Disconnect s1 from s2,e.g.s2.unlinkTo(s1).

You can print the forwarding tables in the terminal,e.g.print(s1).How  long will the routers count?It seems to be forever...despite all of our hard work!

Will we ever stabilize?Can split horizon or poison reverse save the day?

Your Task

Modify send  routes so  that  any   latency  greater  than INFINITY is  rounded  down  to INFINITY when advertised.

Testing and Debugging

To check your work,run the unit tests: python3    dv_unit_tests.py    8

Check Your Understanding

Re-run the loopy demo from earlier.How long will the routers count now?

Stage 9:Poisoning Expired Routes

Next,let's implement Rule 4(Poisoning Expired Routes)of distance-vector.

Check Your Understanding

Start up the simulator with the linear topology with 7 hosts:

python3 simulator.py --start --default-switch-type=dv_router topos.linear --n =7

Wait for all routes to converge (e.g.s7's table should have a route to h1).This can take a while!

Then,disconnect s1 from s2,e.g.s1.unlinkTo(s2).

How long will it take for the route to s1 to be updated in the other routers?

Your Task

Modify expire routes.

Any expired routes should get replaced with poison if self.POISON EXPIRED is True.

Set the poisoned entry to have an expire time of api.current time()+self.ROUTE TTL.This ensures the poisoned route gets advertised periodically.

Optional,ungraded:Ideally,the periodic advertisements should halt after awhile (i.e. poisoned routes should be removed eventually),because it's not useful to keep

advertising the nonexistence of a route.We won't test you on this though.

Testing and Debugging

To check your work,run the unit tests: python3   dv_unit_tests.py   9

Check Your Understanding

What do route removals now propagate relative to?

You're almost done!Now might be a goodtime to back up your work.The last stage  requires changing your code so far,and you might want to revert to your code before starting Stage 10.