Question? Leave a message!

Routing vs Forwarding

Routing vs Forwarding 34
Routing I: Basic Ideas Shivkumar Kalyanaraman 1Overview  Routing vs Forwarding  Forwarding table vs Forwarding in simple topologies  Routers vs Bridges: review  Routing Problem  Telephony vs Internet Routing  Sourcebased vs Fully distributed Routing  Distance vector vs Link state routing  Addressing and Routing: Scalability  Refs: Chap 8, 11, 14, 16 in Comer textbook  Books: “Routing in Internet” by Huitema, “Interconnections” by Perlman  Reading: Notes for Protocol Design, E2e Principle, IP and Routing: In PDF  Reading: Routing 101: Notes on Routing: In PDF In MS Word  Reading: Khanna and Zinky, The revised ARPANET routing metric  Reference: GarciaLunaAceves: "Loopfree Routing Using Diffusing Computations" :  Reading: Alaettinoglu, Jacobson, Yu: "Towards MilliSecond IGP Convergence" Shivkumar Kalyanaraman 2Where are we  Routing vs Forwarding  Forwarding table vs Forwarding in simple topologies  Routers vs Bridges: review  Routing Problem  Telephony vs Internet Routing  Sourcebased vs Fully distributed Routing  Distance vector vs Link state routing  Addressing and Routing: Scalability Shivkumar Kalyanaraman 3Routing vs. Forwarding  Forwarding: select an output port based on destination address and routing table  Dataplane function  Often implemented in hardware  Routing: process by which routing table is built..  … so that the series of local forwarding decisions takes the packet to the destination with high probability, and …(reachability condition)  … the path chosen/resources consumed by the packet is efficient in some sense… (optimality and filtering condition)  Controlplane function  Implemented in software Shivkumar Kalyanaraman 4Forwarding Table  Can display forwarding table using “netstat rn” Sometimes called “routing table” Destination Gateway Flags Ref Use Interface UH 0 26492 lo0 192.168.2. U 2 13 fa0 193.55.114. U 3 58503 le0 192.168.3. U 2 25 qaa0 U 3 0 le0 default UG 0 143454 Shivkumar Kalyanaraman 5Forwarding Table Structure  Fields: destination, gateway, flags, ...  Destination: can be a host address or a network address. If the „H‟ flag is set, it is the host address.  Gateway: router/next hop IP address. The „G‟ flag says whether the destination is directly or indirectly connected.  U flag: Is route up  G flag: router (indirect vs direct)  H flag: host (dest field: host or n/w address) Key question:  Why did we need this forwarding table in the first place Shivkumar Kalyanaraman 6Routing in Simple Topologies . . . Bus: Drop pkt on the wire… Full mesh: port = destaddr Ring: send packet consistently Star: stubs point to hub; in (anti)clockwise direction hub behaves like full mesh Shivkumar Kalyanaraman 7 SWhere are we  Routing vs Forwarding  Forwarding table vs Forwarding in simple topologies  Routers vs Bridges: review  Routing Problem  Telephony vs Internet Routing  Sourcebased vs Fully distributed Routing  Distance vector vs Link state routing  Addressing and Routing: Scalability Shivkumar Kalyanaraman 8Recall… Layer 1 2  Layer 1:  Hubs do not have “forwarding tables” – they simply broadcast signals at Layer 1. No filtering.  Layer 2:  Forwarding tables not required for simple topologies (previous slide): simple forwarding rules suffice The nexthop could be functionally related to destination address (i.e. it can be computed without a table explicitly listing the mapping). This places too many restrictions on topology and the assignment of addresses visàvis ports at intermediate nodes. Forwarding tables could be statically (manually) configured once or from timetotime. Does not accommodate dynamism in topology Shivkumar Kalyanaraman 9Recall… Layer 2  Even reasonable sized LANs cannot tolerate above restrictions  Bridges therefore have “L2 forwarding tables,” and use dynamic learning algorithms to build it locally. Even this allows LANs to scale, by limiting broadcasts and collisions to collision domains, and using bridges to interconnect collision domains. The learning algorithm is purely local, opportunistic and expects no addressing structure. Hence, bridges often may not have a forwarding entry for a destination address (I.e. incomplete) In this case they resort to flooding – which may lead to duplicates of packets seen on the wire. Bridges coordinate “globally” to build a spanning tree so that flooding doesn‟t go out of control. Shivkumar Kalyanaraman 10Recall …: Layer 3  Routers have “L3 forwarding tables,” and use a distributed protocol to coordinate with other routers to learn and condense a global view of the network in a consistent and complete manner.  Routers NEVER broadcast or flood if they don‟t have a route – they “pass the buck” to another router.  The good filtering in routers (I.e. restricting broadcast and flooding activity to be within broadcast domains) allows them to interconnect broadcast domains,  Routers communicate with other routers, typically neighbors to collect an abstracted view of the network.  In the form of distance vector or link state.  Routers use algorithms like Dijkstra, BellmanFord to compute paths with such abstracted views. Shivkumar Kalyanaraman 11Recall: Interconnection Devices Extended LAN =Broadcast LAN= domain B H H H H Collision Router Domain Application Application Gateway Transport Transport Network Network Router Datalink Datalink Bridge/Switch Physical Physical Repeater/Hub Shivkumar Kalyanaraman 12Summary so far  If topology is simple and static, routing is simple and may not even require a forwarding table  If topology is dynamic, but filtering requirements are weak (I.e. network need not scale), then a local heuristic setup of forwarding table (bridging approach) suffices.  Further, if a) filtering requirements are strict, b) optimal/efficient routing is desired, and c) we want small forwarding tables and bounded control traffic, then … some kind of global communication, and smart distributed algorithms are needed to condense global state in a consistent, but yet complete way … Shivkumar Kalyanaraman 13What’s up in advanced routing  Routers are efficient in the collection of the abstracted view (controlplane filtering)  Routers accommodate a variety of topologies, and sub networks in an efficient manner  Routers are organized in hierarchies to achieve scalability; and into autonomous systems to achieve complex policycontrol over routing.  Routers then condense paths into next hops, either:  depending upon other routers in a path to compute nexthops in a consistent manner (fully distributed), or  using a signaling protocol to enforce consistency.  Advanced routing algorithms support “QoS routing” and “traffic engineering” goals like multipath routing, source based or distributed traffic splitting, fast reroute, path protection etc. Shivkumar Kalyanaraman 14Where are we  Routing vs Forwarding  Forwarding table vs Forwarding in simple topologies  Routers vs Bridges: review  Routing Problem  Telephony vs Internet Routing  Sourcebased vs Fully distributed Routing  Distance vector vs Link state routing  Addressing and Routing: Scalability Shivkumar Kalyanaraman 15Routing problem  Collect, process, and condense global state into local forwarding information  Global state inherently large dynamic hard to collect  Hard issues: consistency, completeness, scalability Impact of resource needs of sessions Shivkumar Kalyanaraman 16Consistency  Defn: A series of independent local forwarding decisions must lead to connectivity between any desired (source, destination) pair in the network.  If the states are inconsistent, the network is said not to have “converged” to steady state (I.e. is in a transient state)  Inconsistency leads to loops, wandering packets etc  In general a part of the routing information may be consistent while the rest may be inconsistent.  Large networks = inconsistency is a scalability issue.  Consistency can be achieved in two ways:  Fully distributed approach: a consistency criterion or invariant across the states of adjacent nodes  Signaled approach: the signaling protocol sets up local Shivkumar Kalyanaraman forwarding information along the path. 17Completeness  Defn: The network as a whole and every node has sufficient information to be able to compute all paths.  In general, with more complete information available locally, routing algorithms tend to converge faster, because the chances of inconsistency reduce.  But this means that more distributed state must be collected at each node and processed.  The demand for more completeness also limits the scalability of the algorithm.  Since both consistency and completeness pose scalability problems, large networks have to be structured hierarchically and abstract entire networks as a single node. Shivkumar Kalyanaraman 18Design Choices …  Centralized vs. distributed routing  Centralized is simpler, but prone to failure and congestion  Centralized preferred in traffic engineering scenarios where complex optimization problems need to be solved and where routes chosen are longlived  Sourcebased (explicit) vs. hopbyhop (fully distributed)  Will the sourcebased route be signaled to fix the path and to minimize packet header information  Eg: ATM, Framerelay etc  Or will the route be condensed and placed in each header Eg: IP routing option  Intermediate: loose source route Shivkumar Kalyanaraman 19Design choices…  Static vs Dynamic Routing: a) „route‟ command Static b) ICMP redirect message.Static c) routing daemon.Eg: „routed‟ Dynamic, connectionless d) A signaling protocol Dynamic, virtual circuit Shivkumar Kalyanaraman 20Static vs Dynamic Statically Dynamically Administrator Routers exchange network reachability manually configures information using ROUTING PROTOCOLS. forwarding table entries Routers use this to compute best routes + More control + Can rapidly adapt to changes + Not restricted to in network topology destinationbased + Can be made to scale well forwarding Complex distributed algorithms Doesn’t scale Consume CPU, Bandwidth, Memory Slow to adapt to Debugging can be difficult network failures Current protocols are destinationbased Practice : a mix of these. Static routing mostly at the “edge” Shivkumar Kalyanaraman 21Example Dynamic Routing Model Shivkumar Kalyanaraman 22Where are we  Routing vs Forwarding  Forwarding table vs Forwarding in simple topologies  Routers vs Bridges: review  Routing Problem  Telephony vs Internet Routing  Sourcebased vs Fully distributed Routing  Distance vector vs Link state routing  Addressing and Routing: Scalability Shivkumar Kalyanaraman 23Detour: Telephony routing  Circuitsetup is what is routed. Voice then follows route, and claims reserved resources.  3level hierarchy, with a fullyconnected core  ATT: 135 core switches with nearly 5 million circuits  LECs may connect to multiple cores Shivkumar Kalyanaraman 24Telephony Routing algorithm  If endpoints are within same CO, directly connect  If call is between COs in same LEC, use onehop path between COs  Otherwise send call to one of the cores  Only major decision is at toll switch  onehop or twohop path to the destination toll switch.  Essence of telephony routing problem: which twohop path to use if onehop path is full (almost a static routing problem… ) Shivkumar Kalyanaraman 25Features of telephone routing  Resource reservation aspects:  Resource reservation is coupled with path reservation Connections need resources (same 64kbps) Signaling to reserve resources and the path  Stable load Network built for voice only. Can predict pairwise load throughout the day Can choose optimal routes in advance  Technology and economic aspects:  Extremely reliable switches Why Endsystems (phones) dumb because computation was nonexistent in early 1900s. Downtime is less than a few minutes per year = topology does not change dynamically Shivkumar Kalyanaraman 26Features of telephone routing Source can learn topology and compute route Can assume that a chosen route is available as the signaling proceeds through the network Component reliability drove system reliability and hence acceptance of service by customers  Simplified topology: Very highly connected network Hierarchy + full mesh at each level: simple routing High cost to achieve this degree of connectivity  Organizational aspects:  Single organization controls entire core  Afford the scale economics to build expensive network  Collect global statistics and implement global changes = Sourcebased, signaled, simple alternatepath routing Shivkumar Kalyanaraman 27Internet Routing Drivers  Technology and economic aspects:  Internet built out of cheap, unreliable components as an overlay on top of leased telephone infrastructure for WAN transport. Cheaper components = fail more often = topology changes often = needs dynamic routing  Components (including endsystems) had computation capabilities. Distributed algorithms can be implemented  Cheap overlaid internetworks = several entities could afford to leverage their existing (heterogeneous) LANs and leased lines to build internetworks. Led to multiple administrative “clouds” which needed to interconnect for global communication. Shivkumar Kalyanaraman 28Internet Routing Model  2 key features:  Dynamic routing  Intra and InterAS routing, AS = locus of admin control  Internet organized as “autonomous systems” (AS).  AS is internally connected  Interior Gateway Protocols (IGPs) within AS.  Eg: RIP, OSPF, HELLO  Exterior Gateway Protocols (EGPs) for AS to AS routing.  Eg: EGP, BGP4 Shivkumar Kalyanaraman 29Requirements for IntraAS Routing  Should scale for the size of an AS.  Low end: 10s of routers (small enterprise)  High end: 1000s of routers (large ISP)  Different requirements on routing convergence after topology changes  Low end: can tolerate some connectivity disruptions  High end: fast convergence essential to business (making money on transport)  Operational/Admin/Management (OAM) Complexity  Low end: simple, selfconfiguring  High end: Selfconfiguring, but operator hooks for control  Traffic engineering capabilities: high end only Shivkumar Kalyanaraman 30Requirements for InterAS Routing  Should scale for the size of the global Internet.  Focus on reachability, not optimality  Use address aggregation techniques to minimize core routing table sizes and associated control traffic  At the same time, it should allow flexibility in topological structure (eg: don‟t restrict to trees etc)  Allow policybased routing between autonomous systems  Policy refers to arbitrary preference among a menu of available options (based upon options‟ attributes)  In the case of routing, options include advertised AS level routes to address prefixes  Fully distributed routing (as opposed to a signaled approach) is the only possibility.  Extensible to meet the demands for newer policies. Shivkumar Kalyanaraman 31IntraAS and InterAS routing C.b Gateways: B.a •perform interAS A.a routing amongst A.c b c themselves a a C •perform intraAS b a B routers with other d routers in their AS c b A network layer interAS, link layer intraAS physical layer routing in gateway A.c Shivkumar Kalyanaraman 32IntraAS and InterAS routing: Example InterAS routing C.b between B.a A and B A.a Host b h2 c A.c a a C b a B Host d IntraAS routing c h1 b A within AS B IntraAS routing within AS A Shivkumar Kalyanaraman 33Basic Dynamic Routing Methods  Sourcebased: source gets a map of the network,  source finds route, and either  signals the routesetup (eg: ATM approach)  encodes the route into packets (inefficient)  Link state routing: perlink information  Get map of network (in terms of link states) at all nodes and find nexthops locally.  Maps consistent = nexthops consistent  Distance vector: pernode information  At every node, set up distance signposts to destination nodes (a vector)  Setup this by peeking at neighbors‟ signposts. Shivkumar Kalyanaraman 34Where are we  Routing vs Forwarding  Forwarding table vs Forwarding in simple topologies  Routers vs Bridges: review  Routing Problem  Telephony vs Internet Routing  Sourcebased vs Fully distributed Routing  Distance vector vs Link state routing  Bellman Ford and Dijkstra Algorithms  Addressing and Routing: Scalability Shivkumar Kalyanaraman 35DV LS: consistency criterion  The subset of a shortest path is also the shortest path between the two intermediate nodes.  Corollary:  If the shortest path from node i to node j, with distance D(i,j) passes through neighbor k, with link cost c(i,k), then: D(i,j) = c(i,k) + D(k,j) j i k Shivkumar Kalyanaraman 36Distance Vector DV = Set (vector) of Signposts, one for each destination Shivkumar Kalyanaraman 37Distance Vector (DV) Approach Consistency Condition: D(i,j) = c(i,k) + D(k,j)  The DV (BellmanFord) algorithm evaluates this recursion iteratively. th  In the m iteration, the consistency criterion holds, assuming that each node sees all nodes and links m hops (or smaller) away from it (i.e. an mhop view) 1 1 B C B B C 7 7 7 A A 2 8 A 8 1 1 1 E E D E D 2 2 Example network A’s 1hop view A’s 2hop view st nd (After 1 iteration) (After 2 Iteration) Shivkumar Kalyanaraman 38Distance Vector (DV)…  Initial distance values (iteration 1):  D(i,i) = 0 ;  D(i,k) = c(i,k) if k is a neighbor (i.e. k is onehop away); and  D(i,j) = INFINITY for all other nonneighbors j.  Note that the set of values D(i,) is a distance vector at node i.  The algorithm also maintains a nexthop value (forwarding table) for every destination j, initialized as:  nexthop(i) = i;  nexthop(k) = k if k is a neighbor, and  nexthop(j) = UNKNOWN if j is a nonneighbor. Shivkumar Kalyanaraman 39Distance Vector (DV).. (Cont’d)  After every iteration each node i exchanges its distance vectors D(i,) with its immediate neighbors.  For any neighbor k, if c(i,k) + D(k,j) D(i,j), then:  D(i,j) = c(i,k) + D(k,j)  nexthop(j) = k  After each iteration, the consistency criterion is met  After m iterations, each node knows the shortest path possible to any other node which is m hops or less.  I.e. each node has an mhop view of the network.  The algorithm converges (selfterminating) in O(d) iterations: d is the maximum diameter of the network. Shivkumar Kalyanaraman 40Distance Vector (DV) Example  A‟s distance vector D(A,):  After Iteration 1 is: 0, 7, INFINITY, INFINITY, 1  After Iteration 2 is: 0, 7, 8, 3, 1  After Iteration 3 is: 0, 7, 5, 3, 1  After Iteration 4 is: 0, 6, 5, 3, 1 1 1 B C B B C 7 7 7 A A 2 8 A 8 1 1 1 E E D E D 2 2 Example network A’s 1hop view A’s 2hop view st nd (After 1 iteration) (After 2 Iteration) Shivkumar Kalyanaraman 41Distance Vector: link cost changes Link cost changes: 1  node detects local link cost change Y 4 1  updates distance table X Z 50  if cost change in least cost path, notify neighbors “good Time 0 Iter. 1 Iter. 2 news algorithm travels DV(Y) 4 0 1 1 0 1 1 0 1 terminates fast” DV(Z) 5 1 0 5 1 0 2 1 0 Shivkumar Kalyanaraman 42Distance Vector: link cost changes Link cost changes: 60  good news travels fast Y 4 1  bad news travels slow X Z “count to infinity” problem 50 Time 0 Iter 1 Iter 2 Iter 3 Iter 4 algo goes on DV(Y) 4 0 1 6 0 1 6 0 1 8 0 1 8 0 1 DV(Z) 5 1 0 5 1 0 7 1 0 7 1 0 9 1 0 Shivkumar Kalyanaraman 43Distance Vector: poisoned reverse  If Z routes through Y to get to X : 60 Y  Z tells Y its (Z‟s) distance to X is 4 1 infinite (so Y won‟t route to X via Z) X Z 50  At Time 0, DV(Z) as seen by Y is INF INF 0, not 5 1 0 algorithm terminates Time 0 Iter 1 Iter 2 Iter 3 DV(Y) 4 0 1 60 0 1 60 0 1 51 0 1 DV(Z) 5 1 0 5 1 0 50 1 0 7 1 0 Shivkumar Kalyanaraman 44Link State (LS) Approach  The link state (Dijkstra) approach is iterative, but it pivots around destinations j, and their predecessors k = p(j)  Observe that an alternative version of the consistency condition holds for this case: D(i,j) = D(i,k) + c(k,j) j i k  Each node i collects all link states c(,) first and runs the complete Dijkstra algorithm locally. Shivkumar Kalyanaraman 45Link State (LS) Approach…  After each iteration, the algorithm finds a new destination node j and a shortest path to it.  After m iterations the algorithm has explored paths, which are m hops or smaller from node i.  It has an mhop view of the network just like the distancevector approach  The Dijkstra algorithm at node i maintains two sets:  set N that contains nodes to which the shortest paths have been found so far, and  set M that contains all other nodes.  For all nodes k, two values are maintained: D(i,k): current value of distance from i to k. p(k): the predecessor node to k on the shortest known path from i Shivkumar Kalyanaraman 46Dijkstra: Initialization  Initialization:  D(i,i) = 0 and p(i) = i;  D(i,k) = c(i,k) and p(k) = i if k is a neighbor of I  D(i,k) = INFINITY and p(k) = UNKNOWN if k is not a neighbor of I  Set N = i , and nexthop (i) = I  Set M = j j is not i  Initially set N has only the node i and set M has the rest of the nodes.  At the end of the algorithm, the set N contains all the nodes, and set M is empty Shivkumar Kalyanaraman 47Dijkstra: Iteration  In each iteration, a new node j is moved from set M into the set N.  Node j has the minimum distance among all current nodes in M, i.e. D(i,j) = min D(i,l). l  M  If multiple nodes have the same minimum distance, any one of them is chosen as j.  Nexthop(j) = the neighbor of i on the shortest path Nexthop(j) = nexthop(p(j)) if p(j) is not i Nexthop(j) = j if p(j) = i  Now, in addition, the distance values of any neighbor k of j in set M is reset as: If D(i,k) D(i,j) + c(j,k), then D(i,k) = D(i,j) + c(j,k), and p(k) = j.  This operation is called “relaxing” the edges of node j. Shivkumar Kalyanaraman 48Dijkstra’s algorithm: example D(B),p(B) D(D),p(D) Step D(C),p(C) D(E),p(E) set N D(F),p(F) 2,A 1,A 0 5,A infinity A infinity 2,A 1 4,D 2,D AD infinity 2 2,A 3,E ADE 4,E 3 3,E ADEB 4,E 4 ADEBC 4,E 5 ADEBCF 5 3 B C 5 2 A 2 1 F 3 1 2 D E 1 The shortestpaths spanning tree rooted at A is called an SPFtree Shivkumar Kalyanaraman 49Miscl Issues: Transient Loops  With consistent LSDBs, all nodes compute consistent loopfree paths B  Limited by Dijkstra 1 1 computation overhead, 3 space requirements A C  Can still have transient loops 5 2 D Packet from CA may loop around BDC if B knows about failure and C D do not Shivkumar Kalyanaraman 50Dijkstra’s algorithm, discussion Algorithm complexity: n nodes  each iteration: need to check all nodes, w, not in N  n(n+1)/2 comparisons: O(n2)  more efficient implementations possible: O(nlogn) Oscillations possible:  e.g., link cost = amount of carried traffic A A A A 1 1+e 2+e 0 0 2+e 2+e 0 D B D B D B 0 D 0 B 1 1+e 0 0 1+e 1 e 0 0 0 e 1 1+e 0 C C C C 1 1 e … recompute … recompute … recompute initially routing Shivkumar Kalyanaraman 51Misc: How to assign the Cost Metric  Choice of link cost defines traffic load  Low cost = high probability link belongs to SPT and will attract traffic  Tradeoff: convergence vs load distribution  Avoid oscillations  Achieve good network utilization  Static metrics (weighted hop count)  Does not take traffic load (demand) into account.  Dynamic metrics (cost based upon queue or delay etc)  Highly oscillatory, very hard to dampen (DARPAnet experience)  Quasistatic metric:  Reassign static metrics based upon overall network load (demand matrix), assumed to be quasistationary Shivkumar Kalyanaraman 52Misc: Incremental SPF Algorithms  Dijkstra algorithm is invoked whenever a new LS update is received.  Most of the time, the change to the SPT is minimal, or even nothing  If the node has visibility to a large number of prefixes, then it may see large number of updates.  Flooding bugs further exacerbate the problem  Solution: incremental SPF algorithms which use knowledge of current map and SPT, and process the delta change with lower computational complexity compared to Dijkstra  Avg case: O(logn) compared to O(nlogn) for Dijkstra  Ref: Alaettinoglu, Jacobson, Yu, “Towards MilliSecond Shivkumar Kalyanaraman IGP Convergence,” Internet Draft. 53Summary: Distributed Routing Techniques Link State Vectoring  Topology information is  Each router knows little flooded within the routing about network topology domain  Only best nexthops are  Best endtoend paths are chosen by each router for computed locally at each each destination network. router.  Best endtoend paths result  Best endtoend paths from composition of all next determine nexthops. hop choices  Based on minimizing some  Does not require any notion notion of distance of distance  Works only if policy is shared Does not require uniform and uniform policies at all routers  Examples: OSPF, ISIS Examples: RIP, BGP Shivkumar Kalyanaraman 54Where are we  Routing vs Forwarding  Forwarding table vs Forwarding in simple topologies  Routers vs Bridges: review  Routing Problem  Telephony vs Internet Routing  Sourcebased vs Fully distributed Routing  Distance vector vs Link state routing  Bellman Ford and Dijkstra Algorithms  Addressing and Routing: Scalability Shivkumar Kalyanaraman 55Addressing: Objects  Address is a numerical “name” which refers to an object  There are several types of objects we‟d like to refer to at the network layer…  Interface:  A place to which a producer or consumer of packets connects to the network; a network attachment point  Network:  A collection of interfaces which have some useful relationship:  Any interface can send directly to any other without going through a router  A topology aggregate Shivkumar Kalyanaraman 56Addressing: Objects  Route or Path:  A path from one place in the network to another  Host:  An actual machine which is the source or destination of traffic, through some interface  Router:  A device which is interconnecting various elements of the network, and forwarding traffic  Node:  A host or router Shivkumar Kalyanaraman 57Address Concept  Address: A structured name for a network interface or topology aggregate:  The structure is used by the routing to help it scale  Topologically related items have to be given related addresses  Topologically related addresses also:  Allow the number of destinations tracked by the routing to be minimized  Allow quick location of the named interface on a map  Provide a representation for topology distribution  Provide a framework for the abstraction process  DNS names:  A structured human usable name for a host, etc  The structure facilitates the distribution and lookup Shivkumar Kalyanaraman 58Flat vs Structured Addresses  Flat addresses: no structure in them to facilitate scalable routing  Eg: IEEE 802 LAN addresses  Hierarchical addresses:  Network part (prefix) and host part  Helps identify direct or indirectly connected nodes Shivkumar Kalyanaraman 59Tradeoffs in Large Scale Routing  Tradeoff: discard detailed routing information vs incur the overhead of large, potentially unneeded detail.  This process is called abstraction.  There are two types of abstraction for routing:  Compression, in which the same routing decision is made in all cases after the abstraction as before  Thinning, in which the routing is affected  If the prior routing was optimal, discarding routing information via thinning means nonoptimal routes  Largescale routing incurs two kinds of overhead cost:  The cost of running the routing  The cost of nonoptimal routes  Challenge of routing is managing this choice of costs. Shivkumar Kalyanaraman 60Hierarchical Routing Example: PNNI Shivkumar Kalyanaraman 61Summary  Routing Concepts  DV and LS algorithms  Addressing and Hierarchy Shivkumar Kalyanaraman 62