01-10-2012, 12:55 PM
Routing in the Internet
Routing.ppt (Size: 501 KB / Downloads: 61)
Last Time
Link-State routing protocol
Broadcast all link state to all routers
Run Dijkstra’s algorithm to find best paths
Distance Vector routing protocol
Distribute vector of current distances to all neighbors
Update current distances based on neighbors’ inputs
MP3
Implement LS and DV routing algorithms
Write a node that:
Connects to some neighbors
Monitors link quality
Exchanges routing state information
Computes (outputs) best routes
Troll
Network “troll” simulates an unreliable link
Drops packets
Delays packets
Reorders packets
Garbles packets
One troll per direction of a (logical) link
Things to Keep in Mind
Find a partner
Teams of 1-2, suggest 2
Ask in class, on newsgroup
Start early!
Deal with loss, errors, dead links
How do you detect dead links?
Watch out for runaway broadcast
Solve the count-to-infinity problem
Choosing among multiple ASes
Now suppose AS1 learns from the inter-AS protocol that subnet x is reachable from AS3 and from AS2.
To configure forwarding table, router 1d must determine towards which gateway it should forward packets for dest x.
This is also the job on inter-AS routing protocol!
RIP: Link Failure and Recovery
If no advertisement heard after 180 sec --> neighbor/link declared dead
routes via neighbor invalidated
new advertisements sent to neighbors
neighbors in turn send out new advertisements (if tables changed)
link failure info quickly (?) propagates to entire net
poison reverse used to prevent ping-pong loops (infinite distance = 16 hops)
Hierarchical OSPF
Two-level hierarchy: local area, backbone.
Link-state advertisements only in area
each nodes has detailed area topology; only know direction (shortest path) to nets in other areas.
Area border routers: “summarize” distances to nets in own area, advertise to other Area Border routers.
Backbone routers: run OSPF routing limited to backbone.
Boundary routers: connect to other AS’s.
Internet inter-AS routing: BGP
BGP (Border Gateway Protocol): the de facto standard
BGP provides each AS a means to:
Obtain subnet reachability information from neighboring ASs.
Propagate reachability information to all AS-internal routers.
Determine “good” routes to subnets based on reachability information and policy.
allows subnet to advertise its existence to rest of Internet: “I am here”