Question? Leave a message!




High Speed Router Design

High Speed Router Design 33
Dr.ShivJindal Profile Pic
Dr.ShivJindal,India,Teacher
Published Date:19-07-2017
Website URL
Comment
High Speed Router Design Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 1Overview  Introduction  Evolution of High-Speed Routers  High Speed Router Components: Lookup Algorithm Classification Switching Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 2What do switches/routers look like? Access routers e.g. ISDN, ADSL Core router Core ATM switch e.g. OC48c POS Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 3Basic Architectural Components Congestion Control Admission Control Reservation Control Routing Datapath: Output per-packet Policing Switching Scheduling processing Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 4Basic Architectural Components: Forwarding Decision 3. 1. Output 2. Scheduling Forwarding Table Interconnect Forwarding Decision Forwarding Table Forwarding Decision Forwarding Table Forwarding Decision Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 5Per-packet processing in an IP Router 1. Accept packet arriving on an incoming link. 2. Lookup packet destination address in the forwarding table, to identify outgoing port(s). 3. Manipulate packet header: e.g., decrement TTL, update header checksum. 4. Send (switch) packet to the outgoing port(s). 5. Classify and buffer packet in the queue. 6. Transmit packet onto outgoing link. Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 6Lookup and Forwarding Engine Packet header payload Router Routing Lookup Destination Outgoing Data Structure Address Port Forwarding Table Dest-network Port 65.0.0.0/8 3 128.9.0.0/16 1 149.12.0.0/19 7 Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 7Example Forwarding Table Destination IP Prefix Outgoing Port 65.0.0.0/ 8 3 Prefix length 128.9.0.0/16 1 142.12.0.0/19 7 IP prefix: 0-32 bits 142.12.0.0/19 128.9.0.0/16 65.0.0.0/8 32 0 128.9.16.14 24 2 -1 2 65.0.0.0 65.255.255.255 Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 8Prefixes can Overlap Longest matching prefix 128.9.176.0/24 128.9.16.0/21128.9.172.0/21 142.12.0.0/19 65.0.0.0/8 128.9.0.0/16 32 0 128.9.16.14 2 -1 Routing lookup: Find the longest matching prefix (aka the most specific route) among all prefixes that match the destination address. Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 9Difficulty of Longest Prefix Match 2-dimensional search: - Prefix Length 32 - Prefix Value 24 128.9.176.0/24 128.9.16.0/21 128.9.172.0/21 142.12.0.0/19 128.9.0.0/16 65.0.0.0/8 8 128.9.16.14 Prefix Values Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 10 Prefix LengthLookup Rates Required Year Line Line-rate 40B (Gbps) packets (Mpps) 1998-99 OC12c 0.622 1.94 1999-00 OC48c 2.5 7.81 2000-01 OC192c 10.0 31.25 2002-03 OC768c 40.0 125 31.25 Mpps  33 ns DRAM: 50-80 ns, SRAM: 5-10 ns Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 11Update Rates Required  Recent BGP studies show that updates can be: Bursty: several 100s of routes updated/withdrawn = insert/delete operations Frequent: Average 100+ updates per second  Need data structure to be efficient in terms of lookup as well as update (insert/delete) operations. Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 12Size of the Forwarding Table 100000 90000 Renewed Exponential 80000 Growth 70000 60000 10,000/year 50000 40000 30000 20000 10000 0 95 96 97 98 99 00 Year Renewed growth due to multi-homing of enterprise networks Shivkumar Kalyanaraman Rensselaer Polytechnic Institute Source: http://www.telstra.net/op13 s/bgptable.html Number of PrefixesPotential Hyper-Exponential Growth Global routing table vs Moore's law since 1999 160000 Global prefixes Moore's law 150000 Double growth 140000 130000 120000 110000 100000 90000 80000 70000 60000 50000 01/99 04/99 07/99 10/99 01/00 04/00 07/00 10/00 01/01 04/01 Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 14 Prefixeslog N 2 Trees and Tries Binary Search Tree Binary Search Trie 0 1 0 1 0 1 010 111 N entries Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 15Trees and Tries Multiway tries 16-ary Search Trie 0000, ptr 1111, ptr 1111, ptr 0000, 0 1111, ptr 0000, 0 000011110000 111111111111 Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 16Lookup: Multiway Tries Tradeoffs Degree of Mem Nodes Total Memory Fraction 6 Tree References (Mbytes) Wasted (%) (x10 ) 2 48 1.09 4.3 49 4 24 0.53 4.3 73 8 16 0.35 5.6 86 16 12 0.25 8.3 93 64 8 0.17 21 98 256 6 0.12 64 99.5 15 Table produced from 2 randomly generated 48-bit addresses Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 17Routing Lookups in Hardware Prefix length Most prefixes are 24-bits or shorter Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 18 NumberRouting Lookups in Hardware Prefixes up to 24-bits 24 2 = 16M entries 142.19.6 Next Hop Next Hop 1 24 Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 19 142.19.6.14 14 142.19.6Routing Lookups in Hardware Prefixes up to 24-bits 128.3.72 Next Hop 1 Next Hop 24 Pointer 0 Prefixes above 24-bits Next Hop Next Hop 8 Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 20 128.3.72.44 44 128.3.72 base offset