Transcript Addressing, Routing, and Forwarding

Lab 4
Dynamic Routing
CS144 Review Session 5
October 30, 2009
Samir Selman
Announcements
• Lab 4 : Due in 2 weeks (Thurs ,Nov 12)
• Lab 3 : Due Yesterday
• For those of you submitting late, contact us
before your deadline if you need an additional
extension. Tell us:
– Where you are
– How much more time you need
Routing
• Static Routing (Implemented Lab 3)
• Dynamic Routing:
– Unicast Routing:
• Interior Gateway Protocols (RIP, OSPF, IS-IS)
• Exterior Gateway Protocols (BGP)
– Multicast Routing
• Examples: Multicast OSPF (MOSPF) , Multicast
BGP(MBGP)
• This Lab will cover RIP
Routing
Routing Information Protocol(RIP)
• RIP:
– Routing Protocol based on Bellman-Ford, Distance Vector
algorithm.
– Intra-domain routing algorithm or interior gateway
protocol (IGP)
– Cost is usually hop count
– Limitations:
• The protocol is limited to networks whose longest path is 15 hops
• The protocol depends upon "counting to infinity" to resolve
certain unusual situations
• The protocol uses fixed "metrics" to compare alternative routes
RIP-Lab4: Implementation
• Lab 4 is just a subset of RIP
• Want you to focus on the RIP part of the
router => Supplied you with ‘dr’ binary
• Binary relies on API implemented in a shared
library to handle dynamic routing. You should
implement this library.
• Write code in dr_api.h and dr_api.c
RIP-Lab4
• Each Router has a forwarding table containing
an entry for every destination network.
• Forwarding table Entry: (Dest Network, Cost,
Next-hop, Time Stamp).
– Dest Network: Represented by a network address
and a network mask (X.X.X.X / Y)
– Cost: Sum of link costs to reach destination.
– Next-hop: IPv4 address of next router along the
path to destination
– Time Stamp: Used to timeout routing entries
RIP-Lab4: RIP Packet Format
• RIP packet:
• Command: Indicates whether packet is request or response
– Request: Asks that a router sends all or part of its routing table.
(For this Lab you don’t need to worry about RIP Requests)
– Response: Either unsolicited routing update or a response to
request.
• Version: RIP version used. Lab 4 uses RIP V2
• AFI: Address family used. (AF_INET)
• Route Tag: Not used in this lab (replaced by pad)
RIP-Lab4: RIP Packet Format
• RIP packet:
• Network address: IP address for the entry
• Subnet Mask: Contains subnet mask for the entry
• Next Hop: Indicates IP address of the next hop to which
packets for the entry is forwarded.
• Metric: Indicates how many hops(routers) have been
traversed in the trip to the destination. (16=unreachable)
RIP-Lab4: Periodic Updates
• Send routing updates:
– At regular intervals (periodic)
– When a router changes the metric to a route (Triggered
Updates)
• Every 10 sec send RIP reply message to all neighbors
containing complete routing table
• Triggered update when an interface goes down or
cost of a local interface changes.
RIP-Lab4: Route Timeouts
• Dynamic Route:
– Route learned from a neighboring router
– Have a Timestamp field per entry
– When receive an update, a router sets the entry Timestamp
value to the current time.
– Periodically check if entries expired (current time –
updatetime > 20 sec.
– If an entry expires => set the Cost = INFINITY
• Local Route:
– Directly Connected Networks
– Invalid TTL= -1
– Next_hop_ip = 0
RIP-Lab4: Routing Loops
• Split Horizon with Poisoned Reverse
– Prevent a loop from occurring between two nodes
– Advertise information back to source with cost INFINITY.
– What about loops with more than 2 nodes. eq: A -> B, B ->
C, C -> A ?
• Cannot stop such a loop using split horizon.
• This loop will only be resolved when the metric reaches infinity
and the network involved is then declared unreachable
• Speed up process using triggered update.
RIP-Lab4: Routing Loops
RIP-Lab4: Code
• You should only touch the safe_ methods (threading handled
already for you)
• Routing table entry
/** a single entry in the routing table */
typedef struct route_t {
uint32_t subnet;
/* destination subnet which this route is for */
uint32_t mask;
/* mask associated with this route */
uint32_t next_hop_ip; /* next hop on on this route */
uint32_t outgoing_intf; /* interface to use to send packets on this route */
uint32_t cost;
struct timeval last_updated;
int is_garbage; /* boolean which notes whether this entry is garbage */
route_t* next; /* pointer to the next route in a linked-list */
} route_t;
RIP-Lab4: Code
• safe_dr_get_next_hop(ip): Called when router needs to know
how to route a packet. Returns which interface packet should
be sent out and IP address of next hop.
• safe_dr_handle_packet: Method called when router receives
a dynamic routing packet.
• safe_dr_handle_periodic(): Method called periodically by the
router.
• safe_dr_interface_changed: When interface goes up or down
or upon a change in direct link cost
• dr_init: Used to initialize any internal data structures.
RIP-Lab4: Running the Lab
• First start the lvns server
– ./lvns -t simple.topo
• If the server is running on the same machine as the dr
instance, then you can start a router which takes control of a
node named "dr1" like this:
– ./dr -v dr1
• If you are running dr from a separate location you'll want to
specify the server‘s address and port explicitly:
– ./dr -v dr1 -s myth5.stanford.edu -p 9999