Networks ’07: Networks ’07 Advanced Routing


Dynamic Routing: Dynamic Routing Dynamic routing provides a way to automatically work out the path between two nodes on a network Dynamic routing protocols can be divided into two different forms: Interior Gateway Protocols (IGP) Exterior Gateway Protocols (EGP)


Autonomous Systems: Autonomous Systems An autonomous system “is a collection of IP networks and routers under the control of one entity (or sometimes more) that presents a common routing policy to the Internet.” (RFC 1930) Autonomous systems can be assigned an autonomous system number (ASN) by their RIR.


Interior Gateway Protocols: Interior Gateway Protocols Control routing within a single autonomous system Examples include RIP, OSPF, iBGP, IGRP, EIGRP, IS-IS


Exterior Gateway Protocols: Exterior Gateway Protocols Control routing between different autonomous systems Sometimes known as inter-domain routing (as in CIDR) The most common example is (e)BGP. Others are EGP and CSPF


Routing Algorithms: Routing Algorithms There are three predominant forms of routing algorithms Distance vector algorithms Link State algorithms Path vector algorithms The first two are largely used for IGPs, the last is used by EGPs


Distance Vector Algorithms: Distance Vector Algorithms Use the Bellman-Ford algorithm Learn routing information from their immediate neighbours Choose the lowest (total) cost path between two nodes Must have some metric to measure “cost”


Link-State Algorithms: Link-State Algorithms Attempt to create a map of the whole network Update the map every time there’s a link transition Use Dijkstra's algorithm to find the best path through the map


Path Vector Algorithms: Path Vector Algorithms Are a variation of distance vector algorithms The view each autonomous system as a node, with no regard to routing within the AS Reduces the amount of flap caused by internal topology changes


Criteria Common to all Protocols: Criteria Common to all Protocols Choose routes based on the smallest matching prefix (this is true in static routing too) Must have some metric to determine the “best” route given two (or more) routes to the same destination Must be able to handle topology changes Can usually redistribute routes from other sources


Routing Information Protocol: Routing Information Protocol Is a widely implemented UDP broadcast-based distance-vector IGP Uses hop count as a routing metric Prevents loops by limiting the number of hops (usually to 15) Each router broadcasts its routing table every ~ 30 seconds Originally contained no authentication or support for VLSMs (RIPv1)


Open Shortest Path First: Open Shortest Path First OSPF is a link-state algorithm A layer four protocol in its own right. Typically uses multicast and/or unicast Defines one or more areas, and creates a map of each area Each area must have a designated router (DR) and a backup designated router (BDR) to maintain the map Areas are linked by area border routers Autonomous systems are linked by ASBRs


OSPF Areas: OSPF Areas The backbone area is the core of an OSPF network. It is also known as area zero (0.0.0.0). A stubby area is one that doesn’t receive external routes (but does receive intra-area routes) There are also totally-stubby areas and not-so-stubby areas


OSPF Path Preference: OSPF Path Preference OSPF uses path cost as its routing metric. The standard doesn’t link path cost to any particular value, leaving that to the network designer It is typically represented by the speed of a link. This needs scaling on modern networks


Border Gateway Protocol: Border Gateway Protocol TCP-based path vector algorithm Makes use of autonomous system numbers Can be an IGP (one ASN) or an EGP (intra-ASN) Routes are exchanged in a peering session


BGP Peering Session: BGP Peering Session When a new (TCP) session is established, neighbours exchange routing information bases (RIB) When the TCP connection to a neighbour is closed, routes learned from that neighbour are removed When topology changes, neighbours exchange updates Updates may be damped to reduce route flap


BGP Routing Decision: BGP Routing Decision Weight check Local preference check. Local route check. AS path length check. Origin check. Multi Exit Discriminator (MED) check.


BGP Communities: BGP Communities Communities can be used to tag routes with extra information There are some standard communities: internet local-as no-export no-advertise Other communities are used defined, and have a user-defined interpretation


Route Maps: Route Maps Used by both BGP and OSPF Route maps can be used to alter incoming or outgoing routes Can set or remove community in BGP Can change weight or local preference Can change the next-hop Can drop route entirely


Blackhole Routes: Blackhole Routes Traffic routed to a black hole disappears Can be a route to 255.255.255.255 to a null interface (hence null routing) Name and convention are implementation specific Best practices dictate that you black hole traffic to your complete IP block on every internal router (why?, how does this not break things?)