Longest prefix matching longest prefix matching when looking for forwarding table entry for given destination address,use longest address prefix that matches destination address. Destination Address Range Link interface 110010000001011100010************ 0 110010000001011100011000****** 1 110010000001011100011************ 2 otherwise 3 examples: DA:11001000000101110001011010100001 which interface? DA:11001000000101110001100010101010 which interface? Network Layer:Data Plane 4-16
Longest prefix matching Destination Address Range 11001000 00010111 00010*** ********* 11001000 00010111 00011000 ********* 11001000 00010111 00011*** ********* otherwise DA: 11001000 00010111 00011000 10101010 examples: DA: 11001000 00010111 00010110 10100001 which interface? which interface? when looking for forwarding table entry for given destination address, use longest address prefix that matches destination address. longest prefix matching Link interface 0 1 2 3 Network Layer: Data Plane 4-16
Longest prefix matching we'll see why longest prefix matching is used shortly,when we study addressing longest prefix matching:often performed using ternary content addressable memories(TCAMs) content addressable:present address to TCAM:retrieve address in one clock cycle,regardless of table size Cisco Catalyst:can up ~IM routing table entries in TCAM Network Layer:Data Plane 4-17
Longest prefix matching ▪ we’ll see why longest prefix matching is used shortly, when we study addressing ▪ longest prefix matching: often performed using ternary content addressable memories (TCAMs) • content addressable: present address to TCAM: retrieve address in one clock cycle, regardless of table size • Cisco Catalyst: can up ~1M routing table entries in TCAM Network Layer: Data Plane 4-17
Switching fabrics transfer packet from input buffer to appropriate output buffer switching rate:rate at which packets can be transfer from inputs to outputs often measured as multiple of input/output line rate N inputs:switching rate N times line rate desirable three types of switching fabrics memo 巨马 巨日 日 memory bus crossbar Network Layer:Data Plane 4-18
Switching fabrics ▪ transfer packet from input buffer to appropriate output buffer ▪ switching rate: rate at which packets can be transfer from inputs to outputs • often measured as multiple of input/output line rate • N inputs: switching rate N times line rate desirable ▪ three types of switching fabrics memory memory bus crossbar Network Layer: Data Plane 4-18
Switching via memory first generation routers: traditional computers with switching under direct control of CPU packet copied to system's memory speed limited by memory bandwidth(2 bus crossings per datagram) input output port memory port (e.g, (e.g, Ethernet) Ethernet) system bus Network Layer:Data Plane 4-19
Switching via memory first generation routers: ▪ traditional computers with switching under direct control of CPU ▪ packet copied to system’ s memory ▪ speed limited by memory bandwidth (2 bus crossings per datagram) input port (e.g., Ethernet) memory output port (e.g., Ethernet) system bus Network Layer: Data Plane 4-19
Switching via a bus datagram from input port memory to output port memory via a shared bus bus contention:switching speed limited by bus bandwidth 32 Gbps bus,Cisco 5600:sufficient bus speed for access and enterprise routers Network Layer:Data Plane 4-20
Switching via a bus ▪ datagram from input port memory to output port memory via a shared bus ▪ bus contention: switching speed limited by bus bandwidth ▪ 32 Gbps bus, Cisco 5600: sufficient speed for access and enterprise routers bus Network Layer: Data Plane 4-20