Routing - DePaul University DePaul University, Chicago

Network ProtocolsRoutingTDC375 Autumn 03/04John Kristoff - DePaul University1

IPv4 unicast routingAll Internet hosts perform basic routingfor local net destinations, forward to local hostfor non-local nets, forward to default routerDedicated routers often used between networksRouting tables maintain next hop informationForwarding decision based on destination addressrouters can use other info to influence decisionRouters forward to next-hop if not locally attachedTDC375 Autumn 03/04John Kristoff - DePaul University2

Basic IPv4 forwarding processFor an IP datagram received on an interface.remove layer 2 information,extract destination IP address (D),find best match for (D) in routing table,extract forwarding address (F) for next hop,create layer 2 info on outgoing interface,send datagram to (F).TDC375 Autumn 03/04John Kristoff - DePaul University3

IP routing tablesSince each row in a routing table represents anentry associated with one IP network, the size ofthe routing table is directly proportional to thenumber of IP networks known throughout theentire internetwork.TDC375 Autumn 03/04John Kristoff - DePaul University4

IP routing table illustratedTDC375 Autumn 03/04John Kristoff - DePaul University5

Populating the routing tableStatically (through manual configuration)Simple for small sites with few links/routersLacks scalability and flexibilityUseful for permanent route entriesAutomatically (with distributed routing protocols)Allows quick re-route around failures/changesUseful for large networks with redundant pathsFailures in protocol can be catastrophicTDC375 Autumn 03/04John Kristoff - DePaul University6

IP routing illustratedTDC375 Autumn 03/04John Kristoff - DePaul University7

IP routing illustrated (continued)TDC375 Autumn 03/04John Kristoff - DePaul University8

Routing metricsShortest/longest hop pathLowest/highest cost pathLowest/highest reliable pathBest/worst latency/delaySite specific path policy decisionTDC375 Autumn 03/04John Kristoff - DePaul University9

Some routing terminologyAutonomous system (AS)Network(s) set administered by a single entityInterior gateway protocol (IGP)distributed routing protocol used within an ASExterior gateway protocol (EGP)distributed routing protocol used between ASesTDC375 Autumn 03/04John Kristoff - DePaul University10

Distance vector routingEach node maintains a distance to destinatione.g. 4 hops to network XYZ, 2 hops to ABCPeriodically advertise attached nets out each linkLearn other nets from other router advertisementsAdvertise learned routes (add 1 to hop count)Also known as Bellman-Ford after the inventorsTDC375 Autumn 03/04John Kristoff - DePaul University11

Distance vector illustratedTDC375 Autumn 03/04John Kristoff - DePaul University12

Distance vector illustrated [cont]TDC375 Autumn 03/04John Kristoff - DePaul University13

Distance vector illustrated [cont]covergedTDC375 Autumn 03/04John Kristoff - DePaul University14

Problems with distance vectorConvergence time can be slowAlso known as the count to infinity problemWhat happens when link to A fails?TDC375 Autumn 03/04John Kristoff - DePaul University15

Solving count to infinityHold downadvertise infinity for a route and wait beforeswitching paths. hope that news of the changepropagates before timer expires. Kludge.Report the entire pathguarantees no loops, but resource expensiveSplit horizonDo not advertise route to neighbor if it wasreceived from that neighbor. Not foolpoof.TDC375 Autumn 03/04John Kristoff - DePaul University16

Other distance vector tricksTriggered updatesadvertise changes immediately, may causeroute flapping, but generally a good thing to doPoison reversethis is used with split horizon, advertise infinityrather than nothing at allDUALlike hold down, but can switch paths if a newdistance is lower, sufficiently complexTDC375 Autumn 03/04John Kristoff - DePaul University17

Routing information protocol(RIP)RFC 1058 (RIPv1) and RFC 2453 (RIPv2)Very simple distance vector protocolSlow convergence timeUDP broadcast every 30 seconds (by default)Route times out after 180 seconds (by default)Widely used as an IGP (RIPv2 in particular)15 hop limit (anything greater equals infinity)TDC375 Autumn 03/04John Kristoff - DePaul University18

RIPv2Mainly updated to support subnet masksSupports simple authenticationUses IP multicast group for destination addressRoute tag option for interaction with EGPsNext-hop option to associated with advertisementTDC375 Autumn 03/04John Kristoff - DePaul University19

RIPv1 packet formatPacket 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) --------------- --------------- --------------- --------------- 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 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - address family identifier (2) must be zero (2) ------------------------------- ------------------------------- IPv4 address (4) ------------- must be zero (4) ------------- must be zero (4) ------------- metric (4) ------------- TDC375 Autumn 03/04John Kristoff - DePaul University20

RIPv2 packet formatPacket format is the same, RIPv2 entry format is: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) ------------- 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 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - Command (1) Version (1) unused --------------- --------------- ------------------------------- 0xFFFF Authentication Type (2) ------------------------------- ------------------------------- Authentication (16) ------------- TDC375 Autumn 03/04John Kristoff - DePaul University21

Link state routingAll routes have complete network topologyinformation (database within their area)link state packets are flooded to all area routersEach router computes its own optimal pathConvergence time is very shortProtocol complexity is higher than distance vectorEnsures a loop free environmentTDC375 Autumn 03/04John Kristoff - DePaul University22

Link state routing illustratedTDC375 Autumn 03/04John Kristoff - DePaul University23

Link state routing databasesLink state databasecontains latest link state packet from each routerPATH (permanent) database(router id / path cost / forwarding direction) tupleTENT (tenative) databasesame format as PATH, candidate PATH entriesForwarding database (aka FIB)contains ID and forwarding directionTDC375 Autumn 03/04John Kristoff - DePaul University24

Dijkstra's algorithmStart with self as root of the tree(my ID / cost 0 / forwarding direction 0) in PATHFor each node in PATH, examine its LSP and placethose neighbors in TENT if not already in PATH orTENT (with lower cost)If TENT is empty, exit, otherwise find ID with lowestcost in TENT and move it to PATHTDC375 Autumn 03/04John Kristoff - DePaul University25

Dijkstra's algorithm illustrated1. Start with A, put A in PATH, examine A's LSP, add B and D to TENT2. B is lowest path cost in TENT, place B in PATH, examine B's LSP, put C,E in TENT3. D is lowest path cost in TENT, place D in PATH, examine D's LSP, found better E path4. C is lowest path cost in TENT, place C in PATH, exame C's LSP, found better E path again5. E is lowest path cost in TENT, place E in PATH, examine E's LSP (no better paths)6. TENT is empty, terminateTDC375 Autumn 03/04John Kristoff - DePaul University26

Open shortest path first (OSPF)Standardized as RFC 2328 (OSPFv2)Relatively complexSupports multiple route metrics (no one does this)Allows 2-tier area hierarchy for scalingRelatively efficientGood convergence propertiesRuns directly over IPRecommended IGP by the IETFTDC375 Autumn 03/04John Kristoff - DePaul University27

OSPF packetsHellolink maintenanceExchangeinitial exchange of routing tablesFloodingincremental routing updatesTDC375 Autumn 03/04John Kristoff - DePaul University28

OSPF database recordsRouter linkssummarizes links from advertising routerNetwork linkstransit networks (broadcast and non-broadcast)Summary linkssummary info advertised by area border routersExternal linksimported routes, typically from EGPTDC375 Autumn 03/04John Kristoff - DePaul University29

Common OSPF header01230 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 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - TDC375 Autumn 03/04John Kristoff - DePaul University30

Interdomain routingRouting domains are independently fundedRouting domains do not trust each otherDifferent routing domains have different policiesStatic routingEGP – first interdomain routing protocolBGP – current path vector routing protocolTDC375 Autumn 03/04John Kristoff - DePaul University31

Border gateway protocol (BGP)Current version 4 standardized in RFC 1771Runs over TCPList of AS numbers comprise a full path to networkAnnouncements can be edited (paths padded)Can selectively filter or preference received routesRoute can be selected on path or a preferenceexternal BGP versus internal BGPTDC375 Autumn 03/04John Kristoff - DePaul University32

BGP attributesDescribes routes in BGP updatesConfusing descriptions of attributese.g. well known must be supportede.g. mandatory must be present in updatesExamplesAS pathcommunityunreachableTDC375 Autumn 03/04John Kristoff - DePaul University33

ConfederationsGroup of ASes that appear as a single ASA form of aggregationMay simplify routing policies“Don't route through confed X” as opposed to“don't go through AS A, AS B, AS C, etc.”Sub-optimal routing may resultmultiple ASes in path vector appear as a loopTDC375 Autumn 03/04John Kristoff - DePaul University34

BGP message typesOpenfirst message when neighbors come upUpdatecontains routing informationNotificationfinal message before session is disconnectedKeepalivereassures reachability in absence of updatesTDC375 Autumn 03/04John Kristoff - DePaul University35

Route dampeningRoutes that oscillate ripple through the Internetconsumes CPU and causes instability (churn)Unstable (flapping) routes are penalizedfor some period of time, the flap is suppressedsuppression time can increase to a maximumsuppression of routes results in lost connectivityDampen big/important netblocks more cautiouslyDampening may introduce stabilities of its ownTDC375 Autumn 03/04John Kristoff - DePaul University36

Sample Cisco configRouter 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 outip 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.ip prefix-list announce seq 10 permit 128.160.0.0/16ip prefix-list announce seq 20 deny 0.0.0.0/0 le 32TDC375 Autumn 03/04John Kristoff - DePaul University37