Datagram forwarding table 4 billion ip addresses. so ing algorithm rather than list ndividual destination address ocal forwarding table dest address putput link list range of addresses ddress-range 1 3 (aggregate table address-range entries ddress-range 41 iP destination address in arriving packet s header 3\2 Network Layer 4-17
Network Layer 4-17 1 3 2 Datagram forwarding table IP destination address in arriving packet’s header routing algorithm local forwarding table dest address output link address-range 1 address-range 2 address-range 3 address-range 4 3 2 2 1 4 billion IP addresses, so rather than list individual destination address list range of addresses (aggregate table entries)
Datagram forwarding table Destination Address range Link Interface 11001000000101110001000000000000 through 11001000000101110001011111111111 11001000000101110001100000000000 through 11001000000101110001100011111111 11001000000101110001100100000000 through 2 11001000000101110001111111111111 otherwise 3 Q: but what happens if ranges dont divide up so nicely? Network Layer 4-18
Network Layer 4-18 Destination Address Range 11001000 00010111 00010000 00000000 through 11001000 00010111 00010111 11111111 11001000 00010111 00011000 00000000 through 11001000 00010111 00011000 11111111 11001000 00010111 00011001 00000000 through 11001000 00010111 00011111 11111111 otherwise Link Interface 0 1 2 3 Q: but what happens if ranges don’t divide up so nicely? Datagram forwarding table
Longest prefix matching longest prefix matching when looking for forwarding table entry for gu iven destination address, use longest address prefix that matches destination address Destination Address range Link interface 110010000001011100010*大大大大大大大大大大大 0 110010000001011100011000大大大★大大大大大 110010000001011100011大大大大大大大大大大大大 2 otherwise examples DA:11001000000101110001011010100001 which interface? DA:110010000010111000110010101010 which interface? Network Layer 4-19
Network Layer 4-19 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
Datagram or vc network: Why? Internet(datagram) ATM(VC) ,s data exchange among evolved from computers telepho elastic service. no 冷 human conversation∷ strict timing req strict timing reliability requirements o many link types need for quaranteed different characteristics service uniform service difficu÷“dumb" end systems smart" end systems telephones (computers) complexity inside network can adapt, perform control, error recovery simple inside network complexity at edge Network Layer 4-20
Network Layer 4-20 Datagram or VC network: why? Internet (datagram) ❖ data exchange among computers ▪ “elastic” service, no strict timing req. ❖ many link types ▪ different characteristics ▪ uniform service difficult ❖ “smart” end systems (computers) ▪ can adapt, perform control, error recovery ▪ simple inside network, complexity at “edge” ATM (VC) ❖ evolved from telephony ❖ human conversation: ▪ strict timing, reliability requirements ▪ need for guaranteed service ❖ “dumb” end systems ▪ telephones ▪ complexity inside network
Chapter 4: outline 4.1 introduction 4.5 routing algorithms 4.2 virtual circuit and link state datagram networks distance vector 4.3 what's inside a router hierarchical routing 4.4 IP: Internet protocol 4.6 routing in the datagram format Internet IPv4 addressing RIP ICMP OSPF IPv6 BGP 4.7 broadcast and multicast routing Network Layer 4-21
Network Layer 4-21 4.1 introduction 4.2 virtual circuit and datagram networks 4.3 what’s inside a router 4.4 IP: Internet Protocol ▪ datagram format ▪ IPv4 addressing ▪ ICMP ▪ IPv6 4.5 routing algorithms ▪ link state ▪ distance vector ▪ hierarchical routing 4.6 routing in the Internet ▪ RIP ▪ OSPF ▪ BGP 4.7 broadcast and multicast routing Chapter 4: outline