Unformatted text preview:

14 –Inter/Intra-AS Routing14 Inter/IntraAS RoutingNetwork Layer4-1Hierarchical RoutinggOur routing study thus far - idealization ll d l all routers identical network “flat” nottrue in practicescale: with 200 million administrative autonomy… nottrue in practicedestinations: can’t store all dest’s in routing tables! internet = network of networks each network admin may g routing table exchange would swamp links!ywant to control routing in its own networkNetwork Layer4-2Hierarchical Routingg aggregate routers into “ Gateway routerregions,“autonomous systems” (AS)routers in same AS run y Direct link to router in another ASrouters in same AS run same routing protocol “intra-AS” routingpt lprotocol routers in different AS can run different intra-AS r utin pr t c lAS routing protocolNetwork Layer4-3Interconnected ASes3Interconnected ASes3b3a1c2aAS3AS22c2b3c1dAS1AS21a1b Forwarding table is configured by both Intra-ASRouting algorithmInter-ASRouting algorithmgyintra- and inter-AS routing algorithmsIntra-AS sets entries ForwardingtableIntra-AS sets entries for internal dests Inter-AS & Intra-AS set entries for external Network Layer4-4set entries for external destsInter-AS tasksAS1 needs: Suppose router in AS1 receives datagram for which dest is outside 1. to learn which dests are reachable through AS2 and which which dest is outside of AS1 Router should forward kt t d f AS2 and which through AS32. to propagate this packet towards one of the gateway routers, but which one?ppgreachability info to all routers in AS1Job of interAS routing!3cJob of inter-AS routing!3b3a1c2aAS3AS21a2c2b3cNetwork Layer4-51dAS11a1bExample: Setting forwarding table in router 1din router 1d3b1d3a1c2aAS31AS21a2c2b1b3c Suppose AS1 learns from the inter-AS protocol that subnet xis reachable from 1dAS1protocol that subnet xis reachable from AS3 (gateway 1c) but not from AS2.Inter-AS protocol propagates reachability InterAS protocol propagates reachability info to all internal routers. Router 1d determines from intra-AS routing info that its interface Iis on the least cost path to 1c.Network Layer4-6 Puts in forwarding table entry (x,I).Example: Choosing among multiple ASespggp Now suppose AS1 learns from the inter-AS protocol that subnet xis reachable from AS3 andfrom AS2that subnet xis reachable from AS3 andfrom AS2. To configure forwarding table, router 1d must determine towards which gateway it should forward packets for dest x. packets for dest x.  This is also the job of inter-AS routing protocol! Hot potato routing: send packet towards closest of two routersLearn from inter-AS Use routing infofitASHot potato routing:Determine fromforwarding table thetwo routers.protocol that subnet x is reachable via multiple gatewaysfrom intra-AS protocol to determinecosts of least-cost paths to eachof the gatewayspgChoose the gatewaythat has the smallest least costforwarding table the interface I that leads to least-cost gateway. Enter (x,I) in forwarding tableNetwork Layer4-7gyIntra-AS Routingg Also known as Interior Gateway Protocols (IGP)y() Most common Intra-AS routing protocols:RIP: Routing Information ProtocolRIP: Routing Information Protocol OSPF: Open Shortest Path First IGRP: Interior Gateway Routing Protocol (Cisco proprietary)Network Layer4-8RIP ( Routing Information Protocol)(gfm ) Distance vector algorithmg Distance metric: # of hops (max = 15 hops)destinationhopsAt A:BAuvwdestinationhopsu 1v 2w 2DCxyzx 3y 3z 2Network Layer4-9yRIP advertisementsRIP advert sementsDistance vectors: exchanged among Distance vectors: exchanged among neighbors every 30 sec via Response Message (also called advertisement) Each advertisement: list of up to 25 destination nets within ASNetwork Layer4-10RIP: ExampleRIP: ExamplezwxyADBDestination Network Next Router Num. of hops to dest.Cpw A2y B2zB7zB7x -- 1…. …. ....Network Layer4-11Routing table in DRIP: ExampleDest Next hopsw --x --zC 4Advertisementfrom A to DwxyzzC 4…. … ...wxyACDBDestination Network Next Router Num. of hops to dest.w A2B2CyB2z B A 7 5x -- 1Network Layer4-12…. …. ....Routing table in DRIP: Link Failure and RecoveryRIP L nk Fa lure and RecoveryIf no advertisement heard after 180 sec --> neighbor/link declared deadneighbor/link declared dead routes via neighbor invalidatednew advertisements sent to neighborsnew advertisements sent to neighbors neighbors in turn send out new advertisements (if tables changed) link failure info quickly propagates to entire netNetwork Layer4-13RIP Table processingpg RIP routing tables managed by application-levelggyppprocess called routed (daemon) advertisements sent in UDP packets (port 520), idi ll tdperiodically repeatedroutedroutednt k f dinTransprt(UDP)tkTransprt(UDP)fdihillinknetwork forwarding(IP) tablehllinknetwork(IP)forwardingtableNetwork Layer4-14physicalphysicalOSPF (Open Shortest Path First)F( p F ) “open”: publicly available Uses Link State algorithm  LS packet disseminationTopology map at each nodeTopology map at each node Route computation using Dijkstra’s algorithmAd ti t di i t d t tiAS ( i Advertisements disseminated to entireAS (via flooding) Carried in OSPF messages directly over IP (rather than TCP gy(or UDPNetwork Layer4-15OSPF “advanced” features (not in RIP)()Security:all OSPF messages authenticated (to Security:all OSPF messages authenticated (to prevent malicious intrusion)  Multiple same-cost paths allowed (only one path in RIP) Hierarchical OSPF in large domains.Network Layer4-16Hierarchical OSPFHierarchical OSPFNetwork Layer4-17Hierarchical OSPFF Two-level hierarchy: local area, backbone.y, Link-state advertisements only in area  each node has detailed area topology; only know d (h h) h direction (shortest path) to nets in other areas. Area border routers: connect to the backbone and thus other areasthus other areas. Backbone routers: route traffic between areas. Boundary routers: connect to other AS’s.Network Layer4-18yInternet inter-AS routing: BGPg BGP (Border Gateway Protocol):thede (y)facto standard BGP provides each AS a means to:1. Obtain subnet reachability information from neighboring ASs.2Propagate the reachability


View Full Document

Rose-Hulman CSSE 432 - Hierarchical Routing

Download Hierarchical Routing
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Hierarchical Routing and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Hierarchical Routing 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?