Computer Networking: A Top-Down Approach PDF

Chapter 4 Network Layer: Data Plane Computer Networking: A Top- Down Approach 8th edition Jim Kurose, Keith Ross Pearson, 2020 Network layer: “data plane” roadmap  Network layer: overview data plane control plane ...

Chapter 4 Network Layer: Data Plane Computer Networking: A Top- Down Approach 8th edition Jim Kurose, Keith Ross Pearson, 2020 Network layer: “data plane” roadmap  Network layer: overview data plane control plane  What’s inside a router input ports, switching, output ports  IP: the Internet Protocol datagram format addressing network address translation IPv6 Network Layer: 4-2 Network-layer services and protocols  transport segment from sending mobile network to receiving host national or global ISP sender: encapsulates segments into datagrams, passes to link applicati layer on transpor receiver: delivers segments to t network transport layer protocol link physical networ k networ k link link  network layer protocols in every physica l physica l Internet device: hosts, routers networ k networ k link  routers: physica link networ l physica k datacenter l link network examines header fields in all IP physica l datagrams passing through it applicati on moves datagrams from input ports enterprise transpor t network network to output ports to transfer link physical datagrams along end-end path. Network Layer: 4-3 Two key network-layer functions network-layer functions: analogy: taking a trip  forwarding: router-local action of moving packets  forwarding: process of from a router’s input link to getting through single appropriate router output  interchange routing: process of planning link. trip from source to destination  routing: network-wide process that determine route taken by packets from source to destination. routing algorithms forwarding routing Network Layer: 4-4 Network layer: data plane, control plane Data plane: Control plane:  local, per-router  network-wide logic function.  determines how datagram  determines how is routed among routers datagram arriving on along end-end path from router input port is source host to destination forwarded values in arriving to router host.  two control-plane approaches: output packet header port. traditional routing algorithms: 0111 1 implemented in routers. 3 2 software-defined networking (SDN): implemented in (remote) servers. Network Layer: 4-5 Per-router control plane Individual routing algorithm components in each and every router interact in the control plane. ** the routing Routing algorithm Algorithm function in one control plane router communicates data plane with the routing algorithm function in other routers to values in arriving compute the packet header values for its 0111 1 forwarding 2 table. 3 Network Layer: 4-6 Software-Defined Networking (SDN) control plane Remote controller computes, installs forwarding tables in routers. The remote controller might Remote Controller be implemented in control a remote data plane center with high data reliability and plane redundancy, and might CA be managed by the ISP or values somein arriving CA CA CA CA third party.packet header 0111 1 2 3 Network Layer: 4-7 Network service model Q: What service model for “channel” transporting datagrams from sender to receiver? example services for example services for a individual flow of datagrams: datagrams:  in-order datagram delivery.  guaranteed delivery.  guaranteed minimum  guaranteed delivery bandwidth to flow. with less than 40 msec delay. Network Layer: 4-8  Network-layer service model ** The Internet’s network layer provides a single service, known as best-effort service. Quality of Service (QoS) Guarantees ? Network Service Architecture Model Bandwidth Loss Order Timing Internet best effort none no no no ATM Constant Bit Rate Constant rate yes yes yes Internet “best effort” service model ATM Available Bit Rate No guarantees on: Guaranteed min no yes no Interneti. successful datagram Intserv Guaranteed yes delivery yesto destination. yes yes (RFC 1633) ii. timing or order of delivery. Diffserv (RFC 2475 Internetiii.bandwidth ) possible available possibly to end-end possibly no flow. Network Layer: 4-9 Network layer: “data plane” roadmap  Network layer: overview data plane control plane  What’s inside a router input ports, switching, output ports  IP: the Internet Protocol datagram format addressing network address translation IPv6 Network Layer: 4-10 Router architecture overview high-level view of generic router architecture: routing, management routing control plane (software) processor operates in millisecond time frame forwarding data plane (hardware) operates in nanosecond timeframe high-speed switching fabric router input ports router output ports Network Layer: 4-11  Input port functions ** With such a shadow copy at each line card, forwarding decisions lookup, can be made locally, at link layer forwarding each input port, without line switch invoking the centralized protocol fabric termination routing processor on a (receive) queueing per-packet basis and thus avoiding physical layer: a centralized processing bit-level reception bottleneck. decentralized switching: link layer:  using header field values, lookup output port e.g., Ethernet using forwarding table in input port memory (chapter 6) (“match plus action”)  goal: complete input port processing at ‘line speed’  input port queuing: if datagrams arrive faster Network Layer: 4-12  Input port functions lookup, link layer forwarding line switch protocol fabric termination (receive) queueing physical layer: bit-level reception decentralized switching: link layer:  using header field values, lookup output port e.g., Ethernet using forwarding table in input port memory (chapter 6) (“match plus action”)  destination-based forwarding: forward based only on destination IP address (traditional)  generalized forwarding: forward based on any set Network Layer: 4-13  Destination-based forwarding 3 Q: but what happens if ranges don’t divide up so nicely? Network Layer: 4-14  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 00010111 00011*** ******** 2 otherwise 3 11001000 00010111 00010110 10100001 which interface? examples: 11001000 00010111 00011000 10101010 which interface? Network Layer: 4-15  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 match! 00010111 00011*** ******** 2 otherwise 3 11001000 00010111 00010110 10100001 which interface? examples: 11001000 00010111 00011000 10101010 which interface? Network Layer: 4-16  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 00010111 00011*** ******** 2 otherwise 3 match! 11001000 00010111 00010110 10100001 which interface? examples: 11001000 00010111 00011000 10101010 which interface? Network Layer: 4-17  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 00010111 00011*** ******** 2 otherwise 3 match! 11001000 00010111 00010110 10100001 which interface? examples: 11001000 00010111 00011000 10101010 which interface? Network Layer: 4-18 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) high-speed.... N input ports N output ports.. switching fabric R R Network Layer: 4-19 Input port queuing  If switch fabric slower than input ports combined -> queueing may occur at input queues queueing delay and loss due to input buffer overflow! Network Layer: 4-20 Output port queuing datagram This is a really important slide switch buffer link layer line fabric termination protocol (rate: NR) queueing (send) R  Buffering required when datagrams arrive from fabric faster than link transmission rate. Drop Datagrams can be policy: which datagrams to drop if lost due to no free buffers? congestion, lack of  Scheduling discipline buffers Priority scheduling – chooses among queued who gets best datagrams for transmission. performance, Network Layer: 4-21 Output port queuing switch switch fabric fabric at t, packets more one packet time later from input to output  buffering when arrival rate via switch exceeds output line speed  queueing (delay) and loss due to output port buffer overflow! Network Layer: 4-22 Network layer: “data plane” roadmap  Network layer: overview data plane control plane  What’s inside a router input ports, switching, output ports buffer management, scheduling  IP: the Internet Protocol datagram format addressing network address translation IPv6 Network Layer: 4-23 Network Layer: Internet host, router network layer functions: transport layer: TCP, UDP Path-selection IP protocol datagram format algorithms: addressing network implemented packet handling conventions forwarding layer in routing table ICMP protocol protocols error reporting (OSPF, BGP) router “signaling” SDN controller link layer physical layer Network Layer: 4-24  IP Datagram format 32 bits IP protocol version number (4 bits) total datagram ver head. type of length length (bytes) header length(bytes) len service fragment fragmentation/ “type” of service: 16-bit identifier flgs  to allow different types of IP datagrams to be offset reassembly distinguished from each other. E.g. real time or time to upper header non real time live layer checksum header checksum TTL: remaining max hops source IP address 32-bit source IP address (decremented at each router) Maximum length: 64K bytes destination IP address 32-bit destination IP address upper layer protocol (e.g., TCP or UDP) Typically: 1500 bytes or less options (if any) e.g., timestamp, record overhead route taken  20 bytes of TCP payload data  20 bytes of IP (variable length,  = 40 bytes + app typically a TCP layer overhead for or UDP segment) TCP+IP Network Layer: 4-25 IP addressing: introduction 223.1.1.1  IP address: 32-bit 223.1.2.1 identifier associated with 223.1.1.2 each host or router 223.1.1.4 223.1.2.9 interface  interface: connection 223.1.1.3 223.1.3.27 223.1.2.2 between host/router and physical link router’s typically have 223.1.3.1 223.1.3.2 multiple interfaces host typically has one or two interfaces (e.g., wired dotted-decimal IP address notation: Ethernet, wireless 802.11) 223.1.1.1 = 11011111 00000001 00000001 00000001 223 1 1 1 Network Layer: 4-26 IP addressing: introduction 223.1.1.1  IP address: 32-bit 223.1.2.1 identifier associated with 223.1.1.2 each host or router 223.1.1.4 223.1.2.9 interface  interface: connection 223.1.1.3 223.1.3.27 223.1.2.2 between host/router and physical link router’s typically have 223.1.3.1 223.1.3.2 multiple interfaces host typically has one or two interfaces (e.g., wired dotted-decimal IP address notation: Ethernet, wireless 802.11) 223.1.1.1 = 11011111 00000001 00000001 00000001 223 1 1 1 Network Layer: 4-27 IP addressing: introduction 223.1.1.1 Q: how are 223.1.2.1 interfaces 223.1.1.2 A: actually we’ll learn about A: wired 223.1.1.4 223.1.2.9 connected? that in chapters 6, Ethernet interfaces 7 connected by 223.1.1.3 223.1.3.27 223.1.2.2 Ethernet switches 223.1.3.1 223.1.3.2 For now: don’t need to worry about how one interface is connected to another (with no A: wireless WiFi interfaces connected by WiFi base station intervening router) Network Layer: 4-28 Subnets 223.1.1.1  What’s a subnet ? 223.1.2.1 device interfaces that can 223.1.1.2 223.1.1.4 223.1.2.9 physically reach each other without passing through an 223.1.3.27 223.1.1.3 intervening router 223.1.2.2  IP addresses have structure: subnet part: devices in same 223.1.3.1 223.1.3.2 subnet have common high order bits. network consisting of 3 subnets host part: remaining low order bits Network Layer: 4-29 Subnets subnet 223.1.1.0/24 223.1.1.1 subnet 223.1.2.0/24 Recipe for defining 223.1.2.1 subnets: 223.1.1.2 223.1.1.4 223.1.2.9  detach each interface from its host or router, 223.1.1.3 223.1.3.27 223.1.2.2 creating “islands” of isolated networks subnet 223.1.3.0/24 223.1.3.1 223.1.3.2  each isolated network is called a subnet subnet mask: /24 (high-order 24 bits: subnet part of IP addre Network Layer: 4-30 Subnets 223.1.1.2 subnet 223.1.1/24  where are 223.1.1.1 223.1.1.4 the 223.1.1.3 subnets?  what are 223.1.9.2 223.1.7.0 subnet 223.1.7/24 the /24 subnet 223.1.9/24 subnet addresses? 223.1.9.1 223.1.7.1 223.1.8.1 223.1.8.0 subnet 223.1.2/24 223.1.2.6subnet 223.1.8/24 223.1.3.27 subnet 223.1.3/24 223.1.2.1 223.1.2.2 223.1.3.1 223.1.3.2 Network Layer: 4-31 IP addressing: CIDR CIDR: Classless InterDomain Routing (pronounced “cider”) subnet portion of address of arbitrary length address format: a.b.c.d/x, where x is # bits in subnet portion of address subnet host part part 11001000 00010111 00010000 00000000 200.23.16.0/23 Network Layer: 4-32 IP addresses: how to get one? Q: how does network get subnet part of IP address? A: gets allocated portion of its provider ISP’s address space ISP's block 11001000 00010111 00010000 00000000 200.23.16.0/20 ISP can then allocate out its address space in 8 blocks: Organization 0 11001000 00010111 00010000 00000000 200.23.16.0/23 Organization 1 11001000 00010111 00010010 00000000 200.23.18.0/23 Organization 2 11001000 00010111 00010100 00000000 200.23.20.0/23... ….. …. …. Organization 7 11001000 00010111 00011110 00000000 200.23.30.0/23 Network Layer: 4-33 Hierarchical addressing: route aggregation hierarchical addressing allows efficient advertisement of routing information: Organization 0 200.23.16.0/23 Organization 1 “Send me anything 200.23.18.0/23 with addresses Organization 2 beginning 200.23.20.0/23. Fly-By-Night-ISP 200.23.16.0/20”... Internet. Organization 7. 200.23.30.0/23 “Send me anything ISPs-R-Us with addresses beginning 199.31.0.0/16” Network Layer: 4-34 Hierarchical addressing: more specific routes  Organization 1 moves from Fly-By-Night-ISP to ISPs- R-Us  ISPs-R-Us Organization 0 now advertises a more specific route to Organization 200.23.16.0/231 Organization 1 “Send me anything 200.23.18.0/23 with addresses Organization 2 beginning 200.23.20.0/23. Fly-By-Night-ISP 200.23.16.0/20”... Internet. Organization 7. 200.23.30.0/23 “Send me anything ISPs-R-Us with addresses Organization 1 beginning 199.31.0.0/16” 200.23.18.0/23 “or 200.23.18.0/23” Network Layer: 4-35 Hierarchical addressing: more specific routes  Organization 1 moves from Fly-By-Night-ISP to ISPs- R-Us  ISPs-R-Us Organization 0 now advertises a more specific route to Organization 200.23.16.0/231 “Send me anything with addresses Organization 2 beginning 200.23.20.0/23. Fly-By-Night-ISP 200.23.16.0/20”... Internet. Organization 7. 200.23.30.0/23 “Send me anything ISPs-R-Us with addresses Organization 1 beginning 199.31.0.0/16” 200.23.18.0/23 “or 200.23.18.0/23” Network Layer: 4-36 IP addressing: last words... Q: how does an ISP get block of Q: are there enough 32-bit IP addresses? addresses? A: ICANN: Internet Corporation  ICANN allocated last chunk for Assigned Names and of IPv4 addresses to RRs in Numbers 2011 http://www.icann.org/ allocates IP addresses,  NAT (next) helps IPv4 through 5 regional registries address space exhaustion (RRs) (who may then allocate to  IPv6 has 128-bit address local registries) space manages DNS root zone, "Who the hell knew how much including delegation of address space we needed?" Vint individual TLD (.com,.edu , Cerf (reflecting on decision to …) management make IPv4 address 32 bits long) Network Layer: 4-37 Network layer: “data plane” roadmap  Network layer: overview data plane control plane  What’s inside a router  IP: the Internet Protocol datagram format addressing network address translation IPv6 Network Layer: 4-38  NAT: network address translation NAT: all devices in local network share just one IPv4 address as far as outside world is concerned rest of local network (e.g., Internet home network) 10.0.0/24 10.0.0.1 138.76.29.7 10.0.0.4 10.0.0.2 10.0.0.3 all datagrams leaving local datagrams with source or network have same source NAT IP destination in this network have address: 138.76.29.7, but 10.0.0/24 address for source, different source port numbers destination (as usual) Network Layer: 4-39 NAT: network address translation  all devices in local network have 32-bit addresses in a “private” IP address space (10/8, 172.16/12, 192.168/16 prefixes) that can only be used in local network  advantages:  just one IP address needed from provider ISP for all devices  can change addresses of host in local network without notifying outside world  can change ISP without changing addresses of devices in local network  security: devices inside local net not directly addressable, visible by outside world Network Layer: 4-40 NAT: network address translation implementation: NAT router must (transparently):  outgoing datagrams: replace (source IP address, port #) of every outgoing datagram to (NAT IP address, new port #) remote clients/servers will respond using (NAT IP address, new port #) as destination address  remember (in NAT translation table) every (source IP address, port #) to (NAT IP address, new port #) translation pair  incoming datagrams: replace (NAT IP address, new port #) in destination fields of every incoming datagram with corresponding (source IP address, port #) stored in NAT table Network Layer: 4-41  NAT: network address translation NAT translation table 2: NAT router changes 1: host 10.0.0.1 sends WAN side addr LAN side addr datagram to datagram source address from 10.0.0.1, 138.76.29.7, 5001 10.0.0.1, 3345 128.119.40.186, 80 3345 to 138.76.29.7, …… …… 5001, S: 10.0.0.1, 3345 updates table D: 128.119.40.186, 80 10.0.0.1 1 S: 138.76.29.7, 2 5001 10.0.0.4 D: 128.119.40.186, 10.0.0.2 80 138.76.29.7 S: 128.119.40.186, 80 4 S: 128.119.40.186, 10.0.0.3 80 3 D: 10.0.0.1, 3345 D: 138.76.29.7, 3: reply arrives, 5001 destination address: 138.76.29.7, 5001 Network Layer: 4-42 NAT: network address translation  NAT has been controversial: routers “should” only process up to layer 3 address “shortage” should be solved by IPv6 violates end-to-end argument (port # manipulation by network-layer device) NAT traversal: what if client wants to connect to server behind NAT?  but NAT is here to stay: extensively used in home and institutional nets, 4G/5G cellular nets Network Layer: 4-43 IPv6: motivation  initial motivation: 32-bit IPv4 address space would be completely allocated  additional motivation: Expanded addressing capabilities. IPv6 increases the size of the IP address from 32 to 128 bits speed processing/forwarding: 40-byte fixed length header enable different network-layer treatment of “flows”. This allows “labeling of packets belonging to particular flows for which the sender requests special handling, such as a non-default quality of service or real-time service.” Network Layer: 4-44  For example, audio and video transmission might likely be treated as a flow. On the other hand, the more traditional applications, such as file transfer and e-mail, might not be treated as flows. It is possible that the traffic carried by a high-priority user (for example, someone paying for better service for their traffic) might also be treated as a flow. Network Layer: 4-45  IPv6 datagram format flow label: identify 32 bits datagrams in same priority: identify priority among ver pri flow label "flow.” (concept of datagrams in flow payload len next hdr hop limit “flow” not well source address defined). 128-bit (128 bits) IPv6 addresses destination address (128 bits) payload (data) What’s missing (compared with IPv4):  no checksum (to speed processing at routers)  no fragmentation/reassembly  no options (available as upper-layer, next-header Network Layer: 4-46 protocol at router) Transition from IPv4 to IPv6  not all routers can be upgraded simultaneously no “flag days” how will network operate with mixed IPv4 and IPv6 routers?  tunneling: IPv6 datagram carried as payload in IPv4 datagram among IPv4 routers (“packet within a packet”) tunneling used extensively in other contexts (4G/5G) IPv4 header fields IPv6 header fields IPv4 payload IPv4 source, dest addr IPv6 source dest addr UDP/TCP payload IPv6 datagram IPv4 datagram Network Layer: 4-47 Tunneling and encapsulation A B Ethernet connects two E F Ethernet IPv6 routers connecting two IPv6 IPv6 IPv6 IPv6 IPv6 routers: IPv6 datagram Link-layer frame The usual: datagram as payload in link-layer frame IPv4 network A B E F connecting two IPv6 routers IPv6 IPv6/v4 IPv6/v4 IPv6 IPv4 network Network Layer: 4-48 Tunneling and encapsulation A B Ethernet connects two E F Ethernet IPv6 routers connecting two IPv6 IPv6 IPv6 IPv6 IPv6 routers: IPv6 datagram Link-layer frame The usual: datagram as payload in link-layer frame IPv4 tunnel A B IPv4 tunnel E F connecting IPv6 routers connecting two IPv6 routers IPv6 IPv6/v4 IPv6/v4 IPv6 IPv6 datagram IPv4 datagram tunneling: IPv6 datagram as payload in a IPv4 datagram Network Layer: 4-49 Tunneling A B IPv4 tunnel E F connecting IPv6 routers logical view: IPv6 IPv6/v4 IPv6/v4 IPv6 A B C D E F physical view: IPv6 IPv6/v4 IPv4 IPv4 IPv6/v4 IPv6 flow: X src:B src:B src:B flow: X src: A dest: E dest: E src: A dest: F dest: E dest: F Flow: X Flow: X Flow: X Src: A Src: A Src: A Note source data Dest: F Dest: F Dest: F data and destination data data data addresses! A-to-B: E-to-F: B-to-C: B-to-C: B-to-C: IPv6 IPv6 IPv6 inside IPv6 inside IPv6 inside IPv4 IPv4 IPv4 Network Layer: 4-50  IPv6: adoption  Google1: ~ 41.94% of clients access services via IPv6  NIST: 1/3 of all US government domains are IPv6 capable  Long (long!) time for deployment, use 25 years and counting! think of application-level changes in last 25 years: WWW, social media, streaming media, gaming, telepresence, … Why? 1 https://www.google.com/intl/en/ipv6/statistics.html Network Layer: 4-51