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:
DEBUG:user:h3:rx:
WARNING:user:h2:NOT ??????????FOR ??????????ME:
DEBUG:user:h1:rx:
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.
版权所有:编程辅导网 2021 All Rights Reserved 联系方式:QQ:99515681 微信:codinghelp 电子信箱:99515681@qq.com
免责声明:本站部分内容从网络整理而来,只供参考!如有版权问题可联系本站删除。