代写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.