CS 6390 Advanced Computer NetworksRoutingRouting in the InternetInternet AS HierarchyIntra-AS and Inter-AS routingIntra-AS RoutingRIP ( Routing Information Protocol)Distance Vector AlgorithmCount to infinity problemSlide 10OSPF (Open Shortest Path First)OSPF “advanced” features (not in RIP)Reliable floodingSlide 14Dijsktra’s AlgorithmDijkstra’s algorithm, discussionHierarchical OSPFSlide 18Routing ProtocolsIntra-Domain Routing TodayWhat do Operators Worry About?Topology Design: Intra-AS TopologyISP Topology Design: Points-of-Presence (PoPs)Convergence: Detecting Topology ChangesConvergence: Transient DisruptionsConvergence: Delay for ConvergingConvergence: Reducing Convergence DelayScalability: Overhead of Link-State ProtocolsScalability: Improving the Scaling PropertiesScalability: Introducing Hierarchy Through AreasCS 6390Advanced Computer NetworksIntra-Domain RoutingRoutingFinding a (good) path between two remote ends in the networkNeed one or more algorithms that are most likely distributed amongst a set of hosts and routersRouting involvesProtocols: defines how to exchange information using which to do routing decisionsAlgorithms: use the data exchanged by the nodes to select good routes (a distributed process)Routing tables: where the exchanged information or the resulting routing information is kept in routersRouting domainA set of routers under same administration running the same routing protocolRouting vs forwarding: what is the difference?Routing in the InternetThe Global Internet consists of Autonomous Systems (AS) interconnected with each other:Stub AS: small corporation: one connection to other AS’sMultihomed AS: large corporation (no transit): multiple connections to other AS’sTransit AS: provider, hooking many AS’s togetherTwo-level routing: Intra-AS: administrator responsible for choice of routing algorithm within networkInter-AS: unique standard for inter-AS routing: BGPInternet AS HierarchyInter-AS border (exterior gateway) routersIntra-AS interior (gateway) routersIntra-AS and Inter-AS routingGateways:•perform inter-AS routing amongst themselves•perform intra-AS routing with other routers in their ASinter-AS, intra-AS routing in gateway A.cnetwork layerlink layerphysical layerabbaaCABdA.aA.cC.bB.acbcIntra-AS RoutingAlso known as Interior Gateway Protocols (IGP)Most common Intra-AS routing protocols:RIP: Routing Information ProtocolOSPF: Open Shortest Path FirstRIP ( Routing Information Protocol)Distance vector algorithmIncluded in BSD-UNIX Distribution in 1982Distance metric: # of hops (max = 15 hops)Distance Vector AlgorithmDistributed next hop computationEach node knows about its neighbors and the cost to reach them(destination, cost, nexthop)Each node exchanges information with its neighbors onlyInfo exchangedVector of distances to destinations: (destination, cost)Via periodic updates, orAfter a topology change that affects the forwarding to a destinationHow to detect topology change? Slow convergenceSuffers from count-to-infinity problemWhat is this?Count to infinity problemABC1110Xdest | cost,nh B | 1, B C | 1, Cdest | cost, nh A | 1, A B | 2, AABC1 10dest | cost, nh B | inf, ? C | 1, Cdest | cost, nh A | 1, A B | 2, AABC1 10dest | cost, nh B | 3, C C | 1, Cdest | cost, nh A | 1, A B | 2, AABC1 10dest | cost, nh B | 3, C C | 1, Cdest | cost, nh A | 1, A B | 4, A((B,3), (C,1))Count to infinity problemPartial solutionsUse a small value to represent infinitySplit horizonC does not advertise route to A Why: C uses A to reach BPoison reverseC advertises route to A with infinite distanceWork for two node loopsDoes not work for loops with more nodesConvince yourself using an exampleHow to avoid loops (ie, perfect solution) ?Each advertisement carries the entire pathBGP uses this approachOSPF (Open Shortest Path First)Uses Link State algorithm LS packet disseminationTopology map at each nodeRoute computation using Dijkstra’s algorithmEach node assumed to know state of links to its neighborsEach node broadcasts its state to all other nodes using reliable flooding mechanismEach node locally computes shortest paths to all other nodes from the locally available global stateUsing Dijkstra’s shortest path algorithmOSPF “advanced” features (not in RIP)Security: all OSPF messages authenticated (to prevent malicious intrusion) Multiple same-cost paths allowed (only one path in RIP)For each link, multiple cost metrics for different TOS (e.g., satellite link cost set “low” for best effort; high for real time)Integrated uni- and multicast support: Multicast OSPF (MOSPF) uses same topology data base as OSPFHierarchical OSPF in large domains.Reliable floodingEach node creates and sends updates to its neighbors and these updates are forwarded to everyone in the network:1. Create a link-state packet (LSP) includingIP of the node creating LSPList of neighbors and cost of the links to eachA sequence number and TTL value (different from IP TTL)and reliably send it to all neighborshop-by-hop reliability – via acknowledgements & retransmissions2. A node X on receiving an LSP originated at a node YCheck if already has a copy of LSP from Y; if not store this oneIf it has, compare the seq.nos, if this is bigger, replace the old one and decrement TTL and forward to all neighbors except the senderIf not bigger, then ignore itHow to guarantee termination of the algorithm?Use of sequence numbers help in thisReliable floodingLSPs are exchanged whenPeriodic timer expires, orA change in the topology occursTTL values ensure that old link-state info get removed from the networkTopology changes can be detected byLink layer protocols, orExchange of “Hello” messagesDijsktra’s Algorithm1 Initialization: 2 N = {A} 3 for all nodes v 4 if v adjacent to A 5 then D(v) = c(A,v) 6 else D(v) = infinity 7 8 Loop 9 find w not in N such that D(w) is a minimum 10 add w to N 11 update D(v) for all v adjacent to w and not in N: 12 D(v) = min( D(v), D(w) + c(w,v) ) 13 /* new cost to v is either old cost to v or known 14 shortest path cost to w plus cost from w to v */ 15 until all nodes in
View Full Document
Unlocking...