Longest prefix matching longest prefix match when looking for forwarding table entry for given destination address,use longest address prefix that matches destination address. Destination Address Range Link interface 11001000 00010111 00010*+ 女★★女大业女 0 11001000 00010111 00011000 ★★女★★★ 1 11001000 00011★** ★★★女★★大 2 otherwise 3 match! 11001000 00 00010110 10100001 which interface? examples: 1001000 00010111 00011000 10101010 which interface? Network Layer:4-21
Longest prefix matching when looking for forwarding table entry for given destination address, use longest address prefix that matches destination address. longest prefix match Destination Address Range 11001000 00010111 00010 11001000 00010111 00011000 11001000 00010111 00011 otherwise Link interface 0 1 2 3 11001000 00010111 00011000 10101010 examples: which interface? which interface? *** ******** *** ******** ******** 11001000 00010111 00010110 10100001 match! Network Layer: 4-21
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:~1M routing table entries in TCAM Network Layer:4-22
▪ 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: ~1M routing table entries in TCAM Longest prefix matching Network Layer: 4-22
Switching fabrics transfer packet from input link to appropriate output link 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 R (rate:NR, R ideally) N input ports· high-speed switching ·N output ports fabric R- Network Layer:4-23
▪ transfer packet from input link to appropriate output link Switching fabrics high-speed switching fabric N input ports N output ports . . . . . . ▪ 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 R R R R (rate: NR, ideally) Network Layer: 4-23
Switching fabrics transfer packet from input link to appropriate output link 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 major types of switching fabrics: memo 日 巨日 memory bus interconnection network Network Layer:4-24
Switching fabrics memory bus memory interconnection network ▪ three major types of switching fabrics: ▪ transfer packet from input link to appropriate output link ▪ 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 Network Layer: 4-24
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 u11 (e.g, (e.g-, Ethernet) Ethernet) system bus Network Layer:4-25
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) Switching via memory input port (e.g., Ethernet) memory output port (e.g., Ethernet) system bus Network Layer: 4-25