Difference between forwarding and Routing

difference between network switch and router and difference between forwarding table and routing table
Dr.ShivJindal Profile Pic
Dr.ShivJindal,India,Teacher
Published Date:19-07-2017
Your Website URL(Optional)
Comment
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  Source-based 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: Garcia-Luna-Aceves: "Loop-free Routing Using Diffusing Computations" :  Reading: Alaettinoglu, Jacobson, Yu: "Towards Milli-Second 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  Source-based 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  Data-plane 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)  Control-plane 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 127.0.0.1 127.0.0.1 UH 0 26492 lo0 192.168.2. 192.168.2.5 U 2 13 fa0 193.55.114. 193.55.114.6 U 3 58503 le0 192.168.3. 192.168.3.5 U 2 25 qaa0 224.0.0.0 193.55.114.6 U 3 0 le0 default 193.55.114.129 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 = dest-addr 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  Source-based 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 next-hop 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 time-to-time. 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, Bellman-Ford 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 (control-plane 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 policy-control over routing.  Routers then condense paths into next hops, either:  depending upon other routers in a path to compute next-hops 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 multi-path routing, source- based or distributed traffic splitting, fast re-route, 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  Source-based 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 long-lived  Source-based (explicit) vs. hop-by-hop (fully distributed)  Will the source-based route be signaled to fix the path and to minimize packet header information?  Eg: ATM, Frame-relay 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 20