Routing John Kristoff - DePaul University

TDC375 Winter 2002John Kristoff - DePaul UniversityRoutingNetwork Protocols1

TDC375 Winter 2002John Kristoff - DePaul University2Route determined by destination IP addressForwarding decision on a hop-by-hop basisTable (information base) drivenPerformed by routersIP routing

TDC375 Winter 2002John Kristoff - DePaul UniversitySend datagram to (F)Create layer 2 information3Extract fowarding address (F) for next hopFind best match for (D) in the routing tableExtract destination IP address (D)Remove layer 2 informationFor an IP datagram received on an interfaceBasic IP forwarding process

TDC375 Winter 2002John Kristoff - DePaul University4Since each entry in a routing table representsan IP network, the size of the routing table isproportional to the number of IP networksknown throughout the entire internetwork.IP routing tables

TDC375 Winter 2002John Kristoff - DePaul UniversityIP routing table illustrated5

Generating routing tables TDC375 Winter 2002John Kristoff - DePaul University6Catastrophic, distributed failures are possibleUseful for large multi-path networksAllows quick re-routing around failed nodes/linksDynamicallyUseful for permanent route entriesDoes not scale wellSimple for small, single path networksManually

TDC375 Winter 2002John Kristoff - DePaul UniversityIP routing illustrated7

TDC375 Winter 2002John Kristoff - DePaul University8IP routing illustrated (continued)

TDC375 Winter 2002John Kristoff - DePaul UniversityPolicy decisionsBest/worst latencyLowest/highest reliabilityLowest/highest cost pathShortest/longest hop pathRouting metrics9

Some terminology TDC375 Winter 2002John Kristoff - DePaul UniversityRouting protocol used between ASesExterior gateway protocols (EGP)Routing protocol used within an ASInterior gateway protocols (IGP)A network or set of networks that isadministrated by a single entityAutonomous system (AS) 10

Distance vector routingTDC375 Winter 2002John Kristoff - DePaul University11Also known as Bellman-Ford after inventorsof the algorithmAdvertise learned routesLearn from other router advertisementsPeriodically advertise attached networks outeach linke.g. 4 hops to network XYZ, 2 hops to ABCEach node maintains distance to destination

TDC375 Winter 2002John Kristoff - DePaul UniversityDistance vector illustrated12

TDC375 Winter 2002John Kristoff - DePaul UniversityDistance vector illustrated(continued)13

TDC375 Winter 2002John Kristoff - DePaul UniversityDistance vector illustrated(converged)14

TDC375 Winter 2002John Kristoff - DePaul UniversityWhat happens when link to A fails?15Also known as the count to infinity problemConvergence time can be slowProblems with distance vector

Solving count to infinity TDC375 Winter 2002John Kristoff - DePaul University16Do not advertise route to a neighbor if youreceived route from that neighbor. Not foolproof.Split horizonGuarantees no loops, but expensive.Report the entire pathAdvertise infinity for route and wait a period oftime before switching routes. Hope that news ofthe downed link will spread fast enough. Kludge.Hold down

Other distance vectorimprovements TDC375 Winter 2002John Kristoff - DePaul University17Somewhat like hold down. Can switch paths ifnew distance is lower. Sufficiently complex.DUALUsed with split horizon, advertise infinity ratherthan nothing at all.Poison reverseAdvertise changes immediately. May causeroute flapping, but generally a good thing to do.Triggered updates

TDC375 Winter 2002John Kristoff - DePaul University15 hop limit (any greater equals infinity)18Widely used as an IGP (RIPv2 particulary)Route times out after 180 seconds (default)UDP broadcast every 30 seconds (default)Slow convergence timeVery simpleThe later defines RIPv2 for improvementsStandardized in RFC 1058 and 2453Routing information protocol (RIP)

RIP version 2 (RIPv2) TDC375 Winter 2002Next-hop routerassociated with advertisementJohn Kristoff - DePaul University19Next-hop optionFor interaction with external gateway protocolsRoute tag optionUses IP multicast destination addressSupport for authenticationNeeded to support classless addressingMost important new feature was to includethe subnet mask with the advertised route

TDC375 Winter 2002John Kristoff - DePaul University01230 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - address family identifier (2) must be zero (2) ------------------------------- ------------------------------- IPv4 address (4) ------------- must be zero (4) ------------- A RIPv1 entry has the following format:01230 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - command (1) version (1) must be zero (2) --------------- --------------- ------------------------------- RIP Entry (20) --------------- --------------- --------------- --------------- Packet format:RIPv1 packet format20

TDC375 Winter 2002John Kristoff - DePaul University01230 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - Command (1) Version (1) unused --------------- --------------- ------------------------------- Authentication uses one entry of the format:01230 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - Address Family Identifier (2) Route Tag (2) ------------------------------- ------------------------------- IP Address (4) ------------- Subnet Mask (4) ------------- Next Hop (4) ------------- Metric (4) ------------- Packet format is the same, RIPv2 entry format is:RIPv2 packet format21

Link state routing TDC375 Winter 2002John Kristoff - DePaul UniversityEnsures a loop free environmentProtocol complexity is highConvergence time is very short22Each router computes its own optimal path toa destination networkLink state packets are flooded to all area routersAll routers have complete network topologyinformation (database) within their area

TDC375 Winter 2002John Kristoff - DePaul UniversityLink state routing illustrated23

Link state routing databases TDC375 Winter 2002John Kristoff - DePaul UniversityContains ID and forwarding directionForwarding databaseSame structure as PATH, its entries may becandidates to move into PATHTENT (tentative) database24Contains (router ID/path cost/forwarding direction)triplesPATH (permanent) databaseContains latest link state packet from each routerLink state database

Dijkstra's algorithm TDC375 Winter 2002John Kristoff - DePaul University25If TENT is empty, exit, otherwise find ID withlowest path cost and in TENT and move it toPATHFor each node in PATH, examine its LSPand place those neighbors in TENT if notalready in PATH or TENT(my ID, path cost 0, forwarding direction 0) inPATHStart with self as root of the tree

TDC375 Winter 20026. TENT is empty, terminateJohn Kristoff - DePaul University5. E is lowest path cost in TENT, place E in PATH, examine E's LSP (no better paths)4. C is lowest path cost in TENT, place C in PATH, exame C's LSP, found better E path again3. D is lowest path cost in TENT, place D in PATH, examine D's LSP, found better E path2. B is lowest path cost in TENT, place B in PATH, examine B's LSP, put C,E in TENT1. Start with A, put A in PATH, examine A's LSP, add B and D to TENT26Dijkstra's algorithm illustrated

TDC375 Winter 2002John Kristoff - DePaul UniversityRecommended IGP by the IETFRuns directly over IPGood convergence propertiesEfficientAllows 2 tier hierarchy for scalability27Supports multiple routing metrics (though rarely used)ComplexStandardized as RFC 2328 (OSPFv2)Open shortest path first (OSPF)

OSPF packets TDC375 Winter 2002John Kristoff - DePaul UniversityIncremental routing updatesFloodingInitial exchange of routing tablesExchangeLink maintenanceHello 28

OSPF database records TDC375 Winter 2002John Kristoff - DePaul UniversityImported routers, typically from a EGPExternal linksSummary info advertised by area border routersSummary links29Transit networks (broadcast and non-broadcast)Network linksSummarizes links from advertising routerRouter links

TDC375 Winter 2002John Kristoff - DePaul University01230 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - Version # Type Packet length - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - Router ID - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - Area ID - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - Checksum AuType - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - Authentication - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - Authentication - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - Common OSPF header30

TDC375 Winter 2002John Kristoff - DePaul University31BGP - current path vector routing protocolEGP - first interdomain routing protocolStatic routingRouting domains may have different policiesRouting domains do not trust each otherRouting domains are independently fundedInterdomain routing

TDC375 Winter 2002John Kristoff - DePaul UniversityE-BGP versus I-BGPCan selectively advertise paths/routesCan edit path in route advertisements32Select route based on preferences of path(s)Sequence of AS numbers comprises pathRuns over TCPCurrent version 4 standardized in RFC 1771Border gateway protocol (BGP)

BGP attributes TDC375 Winter 2002UnreachableCommunityAS pathExamplesJohn Kristoff - DePaul University33e.g. Mandatory must be present in the updatee.g. Well known attributes must be supportedConfusing descriptionsDescribe routes in BGP updates

Confederations TDC375 Winter 2002John Kristoff - DePaul University34Multiple ASs in a path vector appear as a loopSub-optimal routing may resulte.g. Don't go through confederation X rather thanspecifying each AS in the confederationMay simplify routing policiesA form of aggregationGroup of ASs that appear as a single AS

Message types TDC375 Winter 2002John Kristoff - DePaul University35Reassures reachability in absence of updatesKeepaliveFinal message just before link is disconnectedNotificationContains routing informationUpdateFirst message when neighbors come upOpen

Route dampening TDC375 Winter 2002John Kristoff - DePaul University36Bigger/important netblocks dampen slowlySupression of routes results in lost connectivitySupression time can increase to a maximumFor some period of time route is surpressedUnstable (flapping) routes are penalizedConsumes CPU and causes instabilityRoutes that oscillate ripple through Internet

TDC375 Winter 2002John Kristoff - DePaul Universityip prefix-list announce seq 10 permit 128.160.0.0/16ip prefix-list announce seq 20 deny 0.0.0.0/0 le 32ip prefix-list invalid seq 10 deny 0.0.0.0/8 le 32ip prefix-list invalid seq 20 deny 10.0.0.0/8 le 32ip prefix-list invalid seq 30 deny 127.0.0.0/8 le 32.Router bgp 12345bgp log-neighbor-changesnetwork 128.160.0.0 mask 255.255.0.0neighbor 36.5.1.1 remote-as 54321neighbor 36.5.1.1 description E-BGP peer with XYZ corp.neighbor 36.5.1.1 password as54321passwordneighbor 36.5.1.1 version 4neighbor 36.5.1.1 prefix-list invalid inneighbor 36.5.1.1 prefix-list announce out37Sample Cisco BGP configuration

TDC375 Winter 2002John Kristoff - DePaul UniversityInternet peering is a fun issue to explore38Generally the only necessary intelligence thatis required in the network is IP routingTroubleshooting complex routing problemscan make your brain hurtRouting protocols work fine 99.99% of thetime, but when they don't, failures aregenerally catastrophicFinal thoughts

Each node maintains distance to destination e.g. 4 hops to network XYZ, . found better E path 4. C is lowest path cost in TENT, place C in PATH, exame C's LSP, found better E path again 5. E is lowest path cost in TENT, place E in PATH, examine E's LSP (no better paths) 6. TENT is empty, terminate . TDC375 Winter 2002 John Kristoff - DePaul University Open shortest path first (OSPF) 27 .