Routing I: Basic Ideas,Shivkumar Kalyanaraman Rensselaer Polytechnic Institute shivkumaecse.rpi.edu Based in part upon slides of Prof. Raj Jain (OSU), S. Keshav (Cornell), J. Kurose (U Mass), Noel Chiappa (MIT),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“,Overview,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,Where are we?,Routing 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,Forwarding 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,Forwarding 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 ?,Routing in Simple Topologies,. . .,Full mesh: port# = dest-addr,Bus: Drop pkt on the wire,Star: stubs point to hub; hub behaves like full mesh,S,Ring: send packet consistently in (anti-)clockwise direction,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,Where are we?,Recall 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,Recall 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 doesnt go out of control.,Recall : 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 dont 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 broadcas