PowerPoint PresentationHierarchical routingSlide 3Interconnected ASesInter-AS tasksExample: setting forwarding table in router 1dExample: choosing among multiple ASesSlide 8Slide 9Intra-AS RoutingRIP ( Routing Information Protocol)RIP: exampleSlide 13RIP: link failure, recoveryRIP table processingOSPF (Open Shortest Path First)OSPF “advanced” features (not in RIP)Hierarchical OSPFSlide 19Internet inter-AS routing: BGPBGP basicsBGP basics: distributing path informationPath attributes and BGP routesBGP route selectionBGP messagesBGP routing policyBGP routing policy (2)Why different Intra-, Inter-AS routing ?Slide 29Broadcast routingIn-network duplicationSpanning treeSpanning tree: creationMulticast routing: problem statementApproaches for building mcast treesShortest path treeReverse path forwardingReverse path forwarding: exampleReverse path forwarding: pruningShared-tree: steiner treeCenter-based treesCenter-based trees: exampleInternet Multicasting Routing: DVMRPDVMRP: continued…TunnelingPIM: Protocol Independent MulticastConsequences of sparse-dense dichotomy:PIM- dense modePIM - sparse modeSlide 50Slide 51Network Layer4-14.1 introduction4.2 virtual circuit and datagram networks4.3 what’s inside a router4.4 IP: Internet Protocoldatagram formatIPv4 addressingICMPIPv64.5 routing algorithmslink statedistance vectorhierarchical routing4.6 routing in the InternetRIPOSPFBGP4.7 broadcast and multicast routingChapter 4: outline (4C)Network Layer4-2Hierarchical routingscale: with 600 million destinations:can’t store all dest’s in routing tables!routing table exchange would swamp links! administrative autonomyinternet = network of networkseach network admin may want to control routing in its own networkour routing study thus far - idealization all routers identicalnetwork “flat”… not true in practiceNetwork Layer4-3aggregate routers into regions, “autonomous systems” (AS)routers in same AS run same routing protocol“intra-AS” routing protocolrouters in different AS can run different intra-AS routing protocolgateway router:at “edge” of its own AShas link to router in another ASHierarchical routingNetwork Layer4-43b1d3a1c2aAS3AS1AS21a2c2b1bIntra-ASRouting algorithmInter-ASRouting algorithmForwardingtable3cInterconnected ASesforwarding table configured by both intra- and inter-AS routing algorithmintra-AS sets entries for internal destsinter-AS & intra-AS sets entries for external destsNetwork Layer4-5Inter-AS taskssuppose router in AS1 receives datagram destined outside of AS1:router should forward packet to gateway router, but which one?AS1 must:1. learn which dests are reachable through AS2, which through AS32. propagate this reachability info to all routers in AS1job of inter-AS routing!AS3AS23b3c3aAS11c1a1d1b2a2c2bothernetworksothernetworksNetwork Layer4-6Example: setting forwarding table in router 1dsuppose AS1 learns (via inter-AS protocol) that subnet x reachable via AS3 (gateway 1c), but not via AS2inter-AS protocol propagates reachability info to all internal routersrouter 1d determines from intra-AS routing info that its interface I is on the least cost path to 1cinstalls forwarding table entry (x,I)AS3AS23b3c3aAS11c1a1d1b2a2c2bothernetworksothernetworksx…Network Layer4-7Example: choosing among multiple ASesnow suppose AS1 learns from inter-AS protocol that subnet x is reachable from AS3 and from AS2.to configure forwarding table, router 1d must determine which gateway it should forward packets towards for dest x this is also job of inter-AS routing protocol!AS3AS23b3c3aAS11c1a1d1b2a2c2bothernetworksothernetworksx………?Network Layer4-8learn from inter-AS protocol that subnet x is reachable via multiple gatewaysuse routing infofrom intra-AS protocol to determinecosts of least-cost paths to eachof the gatewayshot potato routing:choose the gatewaythat has the smallest least costdetermine fromforwarding table the interface I that leads to least-cost gateway. Enter (x,I) in forwarding tableExample: choosing among multiple ASesnow suppose AS1 learns from inter-AS protocol that subnet x is reachable from AS3 and from AS2.to configure forwarding table, router 1d must determine towards which gateway it should forward packets for dest xthis is also job of inter-AS routing protocol!hot potato routing: send packet towards closest of two routers.Network Layer4-94.1 introduction4.2 virtual circuit and datagram networks4.3 what’s inside a router4.4 IP: Internet Protocoldatagram formatIPv4 addressingICMPIPv64.5 routing algorithmslink statedistance vectorhierarchical routing4.6 routing in the InternetRIPOSPFBGP4.7 broadcast and multicast routingChapter 4: outlineNetwork Layer4-10Intra-AS Routingalso known as interior gateway protocols (IGP)most common intra-AS routing protocols:RIP: Routing Information ProtocolOSPF: Open Shortest Path FirstIGRP: Interior Gateway Routing Protocol (Cisco proprietary)Network Layer4-11RIP ( Routing Information Protocol)included in BSD-UNIX distribution in 1982distance vector algorithmdistance metric: # hops (max = 15 hops), each link has cost 1DVs exchanged with neighbors every 30 sec in response message (aka advertisement)each advertisement: list of up to 25 destination subnets (in IP addressing sense)DCBAuvwxyzsubnet hops u 1 v 2 w 2 x 3 y 3 z 2 from router A to destination subnets:Network Layer4-12RIP: example destination subnet next router # hops to dest w A 2y B 2 z B 7x -- 1…. …. ....routing table in router DwxyzACDBNetwork Layer4-13wxyzACDBdestination subnet next router # hops to dest w A 2y B 2 z B 7x -- 1…. …. ....routing table in router DA5 dest next hops w - 1 x - 1 z C 4 …. … ...A-to-D advertisementRIP: exampleNetwork Layer4-14RIP: link failure, recovery if no advertisement heard after 180 sec --> neighbor/link declared deadroutes via neighbor invalidatednew advertisements sent to neighborsneighbors in turn send out new advertisements (if tables changed)link failure info quickly (?) propagates to entire netpoison reverse used to prevent ping-pong loops (infinite distance = 16 hops)Network Layer4-15RIP table processingRIP routing tables managed by application-level process called route-d (daemon)advertisements
View Full Document
Unlocking...