Computer Networking: A Top-Down Approach Chapter 4 PDF

Chapter 4 Network Layer: Data Plane A note on the use of these PowerPoint slides: We’re making these slides freely available to all (faculty, students, readers). They’re in PowerPoint form so you see the animations; and can add, modify, and delete slides (including this one) and slide content to sui...

Chapter 4 Network Layer: Data Plane A note on the use of these PowerPoint slides: We’re making these slides freely available to all (faculty, students, readers). They’re in PowerPoint form so you see the animations; and can add, modify, and delete slides (including this one) and slide content to suit your needs. They obviously represent a lot of work on our part. In return for use, we only ask the following:  If you use these slides (e.g., in a class) that you mention their source (after all, we’d like people to use our book!) Computer  If you post any slides on a www site, that you note that they are adapted from (or perhaps identical to) our slides, and note our copyright of this material. Networking: A Top- For a revision history, see the slide note for this page. Down Approach Thanks and enjoy! JFK/KWR 8th edition Jim Kurose, Keith Ross All material copyright 1996-2020 Pearson, 2020 J.F Kurose and K.W. Ross, All Rights Reserved Network layer: our goals  understand principles  instantiation, behind network layer implementation in the services, focusing on Internet data plane: IP protocol network layer service models NAT, middleboxes forwarding versus routing how a router works addressing generalized forwarding Internet architecture Network Layer: 4-2 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  Generalized Forwarding, SDN  IP: the Internet Protocol Match+action datagram format OpenFlow: match+action in addressing action network address translation  Middleboxes IPv6 Network Layer: 4-3 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-4 Two key network-layer functions network-layer functions: analogy: taking a trip  forwarding: move packets  forwarding: process of from a router’s input link getting through single to appropriate router  interchange routing: process of planning trip from source to  output routing:link determine route destination taken by packets from source to destination routing algorithms forwarding routing Network Layer: 4-5 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 hostcontrol-plane approaches:  two 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-6 Per-router control plane Individual routing algorithm components in each and every router interact in the control plane Routing Algorithm control plane data plane values in arriving packet header 0111 1 2 3 Network Layer: 4-7 Software-Defined Networking (SDN) control plane Remote controller computes, installs forwarding tables in routers Remote Controller control plane data plane CA CA CA CA CA values in arriving packet header 0111 1 2 3 Network Layer: 4-8 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  restrictions on changes in msec delay inter-packet spacing Network Layer: 4-9  Network-layer service model 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 Internet i. successful datagram Intserv Guaranteed yes delivery yes to destination yes yes (RFC 1633) ii. timing or order of delivery Diffserv (RFC 2475available Internet iii.bandwidth ) possibleto end-end possiblyflow possibly no Network Layer: 4-10  Network-layer service model 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 ATM Available Bit Rate Guaranteed min no yes no Internet Intserv Guaranteed yes yes yes yes (RFC 1633) Internet Diffserv (RFC 2475) possible possibly possibly no Network Layer: 4-11 Reflections on best-effort service:  simplicity of mechanism has allowed Internet to be widely deployed adopted  sufficient provisioning of bandwidth allows performance of real-time applications (e.g., interactive voice, video) to be “good enough” for “most of the time”  replicated, application-layer distributed services (datacenters, content distribution networks) connecting close to clients’ networks, allow services to be provided from multiple locations  congestion control of “elastic” services helps It’s hard to argue with success of best-effort service model Network Layer: 4-12 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  Generalized Forwarding, SDN Match+action datagram format OpenFlow: match+action in addressing action network address translation  Middleboxes IPv6 Network Layer: 4-13 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-14 Router architecture overview analogy view of generic router architecture: routing, management Station control plane (software) manager operates in millisecond time frame forwarding data plane (hardware) operates in nanosecond timeframe roundabout entry stations exit roads Network Layer: 4-15  Input port functions lookup, link layer forwarding line switch protocol fabric termination (receive) queueing Datagram 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”) Frame  goal: complete input port processing at ‘line speed’  input port queuing: if datagrams arrive faster Network Layer: 4-16  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-17  Destination-based forwarding 3 Q: but what happens if ranges don’t divide up so nicely? Network Layer: 4-18  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-19  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-20  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-21  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-22 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-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 R (rate: NR, R ideally) high-speed.... N input ports N output ports.. switching fabric R R Network Layer: 4-24 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: memory memory bus interconnection network Network Layer: 4-25 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: 4-26 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 routers Network Layer: 4-27 Switching via interconnection network  Crossbar, Clos networks, other interconnection nets initially developed to connect processors in  multiprocessor multistage switch: nxn switch 3x3 crossbar from multiple stages of smaller switches  exploiting parallelism: fragment datagram into fixed length cells on entry switch cells through the fabric, reassemble datagram at exit 8x8 multistage switch built from smaller-sized switches Network Layer: 4-28 Switching via interconnection network  scaling, using multiple switching “planes” in parallel:  speedup, scaleup via parallelism  Cisco CRS router: fabric plane 0  basic unit: 8 fabric plane 1............ switching planes fabric plane 2 fabric plane 3  each plane: 3-............ fabric plane 4 fabric plane 5 stage............ fabric plane 6 fabric plane 7 interconnection............ network  up to 100’s Tbps switching capacity Network Layer: 4-29 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!  Head-of-the-Line (HOL) blocking: queued datagram at front of queue prevents others in queue from moving forward switch switch fabric fabric output port contention: only one one packet time later: red datagram can be transferred. green packet experiences lower red packet is blocked HOL blocking Network Layer: 4-30 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 datagrams for who gets best transmission performance, network neutrality Network Layer: 4-31 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-32 How much buffering?  RFC 3439 rule of thumb: average buffering equal to “typical” RTT (say 250 msec) times link capacity C e.g., C = 10 Gbps link: 2.5 Gbit buffer  more recent recommendation: with N flows, buffering equal to. RTT C N  but too much buffering can increase delays (particularly in home routers) long RTTs: poor performance for real-time apps, sluggish TCP response recall delay-based congestion control: “keep bottleneck link just full enough (busy) but no fuller” Network Layer: 4-33  Buffer Management buffer management: switch datagram buffer link  drop: which packet to fabric layer line R add, drop when buffers protocol termination queueing (send) are full scheduling tail drop: drop arriving packet priority: drop/remove on priority basis Abstraction: queue  marking: which packets to mark to signal packet R packet departures congestion (ECN, RED) arrivals queue link (waiting area) (server) Network Layer: 4-34  Packet Scheduling: FCFS packet scheduling: FCFS: packets deciding which packet to transmitted in order send next on link of arrival to output first come, first served priority port round robin  also known as: First-in- weighted fair queueing first-out (FIFO)  real world examples? Abstraction: queue packet packet R departures arrivals queue link (waiting area) (server) Network Layer: 4-35 Scheduling policies: priority Priority scheduling: high priority queue  arriving traffic arrivals classified, queued by classify link departures class low priority queue any header fields can be 2 used for classification  send packet from arrivals 1 3 4 5 highest priority queue that has buffered packet in 1 3 2 4 5 packets service FCFS within priority class departures 1 3 2 4 5 Network Layer: 4-36 Scheduling policies: round robin Round Robin (RR) scheduling:  arriving traffic classified, queued by class any header fields can be used for classification  server cyclically, R repeatedly scans class classify link departures queues, sending one arrivals complete packet from each class (if available) in turn Network Layer: 4-37 Scheduling policies: weighted fair queueing Weighted Fair Queuing (WFQ):  generalized Round Robin  each class, i, has weight, w1 wi, and gets weighted amount of service in each cycle: w2 R wi classify link departures Sjwj arrivals w3  minimum bandwidth guarantee (per-traffic- class) Network Layer: 4-38  Sidebar: Network Neutrality What is network neutrality?  technical: how an ISP should share/allocation its resources packet scheduling, buffer management are the mechanisms  social, economic principles protecting free speech encouraging innovation, competition  enforced Different legal countries haverules and“takes” different policies on network neutrality Network Layer: 4-39 Sidebar: Network Neutrality 2015 US FCC Order on Protecting and Promoting an Open Internet: three “clear, bright line” rules:  no blocking … “shall not block lawful content, applications, services, or non-harmful devices, subject to reasonable network management.”  no throttling … “shall not impair or degrade lawful Internet traffic on the basis of Internet content, application, or service, or use of a non-harmful device, subject to reasonable network management.”  no paid prioritization. … “shall not engage in paid prioritization” Network Layer: 4-40 ISP: telecommunications or information service? Is an ISP a “telecommunications service” or an “information service” provider?  the answer really matters from a regulatory standpoint! US Telecommunication Act of 1934 and 1996: Title II: imposes “common carrier duties” on telecommunications services: reasonable rates, non- discrimination and requires regulation Title I: applies to information services: no common carrier duties (not regulated) but grants FCC authority “… as may be necessary in the execution of its functions” 4 Network Layer: 4-41 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 Generalized Forwarding, SDN  IP: the Internet Protocol match+action OpenFlow: match+action in datagram format action addressing  Middleboxes network address translation IPv6 Network Layer: 4-42 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-43  IP Datagram format 32 bits IP protocol version number total datagram ver head. type of length length (bytes) header length(bytes) len service fragment fragmentation/ “type” of service: 16-bit identifier flgs  diffserv (0:5) offset reassembly  ECN (6:7) time to upper header 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-44 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-45 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-46 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-47 Subnets 223.1.1.1  What’s a subnet ? 223.1.2.1 device interfaces that can 223.1.1.2 physically reach each 223.1.1.4 223.1.2.9 other without passing through an intervening 223.1.1.3 223.1.3.27 223.1.2.2 router  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-48 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-49 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-50 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-51 IP addresses: how to get one? That’s actually two questions: 1.Q: How does a host get IP address within its network (host part of address)? 2.Q: How does a network get IP address for itself (network part of address) How does host get IP address?  hard-coded by sysadmin in config file (e.g., /etc/rc.config in UNIX)  DHCP: Dynamic Host Configuration Protocol: dynamically get address from as server “plug-and-play” Network Layer: 4-52 DHCP: Dynamic Host Configuration Protocol goal: host dynamically obtains IP address from network server when it “joins” network  can renew its lease on address in use  allows reuse of addresses (only hold address while connected/on)  support for mobile users who join/leave network DHCP overview:  host broadcasts DHCP discover msg [optional]  DHCP server responds with DHCP offer msg [optional]  host requests IP address: DHCP request msg  DHCP server sends address: DHCP ack msg Network Layer: 4-53 DHCP client-server scenario Typically, DHCP server will be DHCP co-located in router, serving 223.1.1.1 server all subnets to which router is 223.1.2.1 attached 223.1.2.5 223.1.1.2 223.1.1.4 223.1.2.9 223.1.1.3 223.1.3.27 arriving DHCP client 223.1.2.2 needs address in this network 223.1.3.1 223.1.3.2 Network Layer: 4-54 DHCP client-server scenario DHCP server: 223.1.2.5 DHCP discover Arriving client src : 0.0.0.0, 68 Broadcast: is there a dest.: 255.255.255.255,67 DHCP server yiaddr: 0.0.0.0out transaction there? ID: 654 DHCP offer src: 223.1.2.5, 67 Broadcast: I’m a DHCP dest: 255.255.255.255, 68 yiaddr: 223.1.2.4 server! Here’s an IP transaction ID: 654 address you can use lifetime: 3600 secs The two steps above DHCP request can be skipped “if a src: 0.0.0.0, 68 client remembers and dest:: 255.255.255.255, Broadcast: OK. I would67 wishes to reuse a yiaddr: 223.1.2.4 previously allocated like to useID: transaction this 655 IP address! lifetime: 3600 secs network address” [RFC 2131] DHCP ACK src: 223.1.2.5, 67 dest: 255.255.255.255, 68 Broadcast: OK. You’ve yiaddr: 223.1.2.4 gottransaction that IPID: address! 655 lifetime: 3600 secs Network Layer: 4-55 DHCP: more than IP addresses DHCP can return more than just allocated IP address on subnet:  address of first-hop router for client  name and IP address of DNS sever  network mask (indicating network versus host portion of address) Network Layer: 4-56 DHCP: example DHCP DHCP  Connecting laptop will use DHCP UDP DHCP IP DHCP to get IP address, DHCP Eth address of first-hop router, Phy address of DNS server. DHCP  DHCP REQUEST message encapsulated in UDP, DHCP DHCP 168.1.1.1 encapsulated in IP, DHCP UDP IP encapsulated in Ethernet DHCP  Ethernet frame broadcast (dest: DHCP Eth router with DHCP Phy server built into FFFFFFFFFFFF) on LAN, received at router router running DHCP server  Ethernet de-mux’ed to IP de- mux’ed, UDP de-mux’ed to DHCP Network Layer: 4-57 DHCP: example DHCP DHCP  DCP server formulates DHCP DHCP UDP ACK containing client’s IP DHCP IP address, IP address of first-hop DHCP Eth Phy router for client, name & IP address of DNS server  encapsulated DHCP server DHCP DHCP reply forwarded to client, de- UDP DHCP DHCP IP muxing up to DHCP at client DHCP Eth router with DHCP DHCP Phy server built into  client now knows its IP router address, name and IP address of DNS server, IP address of its first-hop router Network Layer: 4-58 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-59 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-60 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-61 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-62 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-63 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 Generalized Forwarding, SDN  IP: the Internet Protocol match+action OpenFlow: match+action in datagram format action addressing  Middleboxes network address translation IPv6 Network Layer: 4-64  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-65 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-66 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-67  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-68 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-69 IPv6: motivation  initial motivation: 32-bit IPv4 address space would be completely allocated  additional motivation: speed processing/forwarding: 40-byte fixed length header enable different network-layer treatment of “flows” Network Layer: 4-70  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-71 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-72 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-73 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-74 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-75 IPv6: adoption  Google1: ~ 40% of clients access services via IPv6 (2023)  NIST: 1/3 of all US government domains are IPv6 capable Network Layer: 4-76  IPv6: adoption  Google1: ~ 40% of clients access services via IPv6 (2023)  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-77 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  Generalized Forwarding, SDN  IP: the Internet Protocol Match+action datagram format OpenFlow: match+action in addressing action network address translation IPv6  Middleboxes Network Layer: 4-78 Generalized forwarding: match plus action Review: each router contains a forwarding (aka:table flow  “match plus action” abstraction: match table) bits in arriving destination-based packet, values intake arriving action forwarding: forward based on dest. IP packet header generalized address 0111 1 forwarding:2 many header fields can 3 determine action many action possible: drop/copy/modify/log packet forwarding table (aka: flow table) Network Layer: 4-79 Flow table abstraction  flow: defined by header field values (in link-, network-, transport- layer fields)  generalized forwarding: simple packet-handling rules match: pattern values in packet header fields actions: for matched packet: drop, forward, modify, matched packet or send matched packet to controller priority: disambiguate overlapping patterns counters: #bytes and #packets Flow table Router’s flow table match action define router’s match+action rules Network Layer: 4-80 Flow table abstraction  flow: defined by header fields  generalized forwarding: simple packet-handling rules match: pattern values in packet header fields actions: for matched packet: drop, forward, modify, matched packet or send matched packet to controller priority: disambiguate overlapping patterns counters: #bytes and #packets Flow table src = *.*.*.*, dest=3.4.*.* match action src=1.2.*.*, forward(2) dest=*.*.*.* drop src=10.1.2.3, dest=*.*.*.* send to controller * : wildcard 1 4 3 2 Network Layer: 4-81 OpenFlow: flow table entries Match Action Stats Packet + byte counters 1. Forward packet to port(s) 2. Drop packet 3. Modify fields in header(s) 4. Encapsulate and forward to controller Header fields to match: VLA VLA IP TCP/ TCP/ Ingres Src Dst Eth IP IP IP N N Prot UDP Src UDP Dst s Port MAC MAC Type Src Dst ToS Port Port ID Pri o Link layer Network layer Transport layer Network Layer: 4-82  OpenFlow: examples Destination-based forwarding: Switc MAC MAC Eth VLAN IP IP IP IP VLAN TCP TCP h src dst type ID Src Dst Prot ToS s-portd-port Action Port Pri 51.6.0. * * * * * * * * * * * port6 IP datagrams destined to IP address8 51.6.0.8 should be forwarded to router output port 6 Firewall: Switc MAC MAC Eth VLAN h VLAN IP IP IP IP TCP TCP src dst type ID Pri Src Dst Prot ToS s-portd-port Action Port * * not* forward) * * datagrams * * * * to TCP * * 22 drop Block (do all destined port 22 (ssh port #) Switc MAC MAC Eth VLAN h VLAN IP IP IP IP TCP TCP src dst type ID Pri Src Dst Prot ToS s-portd-port Action Port 128.119.1 * * * * * * * * drop sent by* host* * Block (do not forward) all datagrams.1 128.119.1.1 Network Layer: 4-83  OpenFlow: examples Layer 2 destination-based forwarding: Switc MAC MAC Eth VLAN IP IP IP IP VLAN TCP TCP h src dst type ID Src Dst Prot ToS s-portd-port Action Port Pri 22:A7:23 * * : * * * * * * * * * port3 11:E1:02 layer 2 frames with destination MAC address 22:A7:23:11:E1:02 should be forwarded to output port 3 Network Layer: 4-84 OpenFlow abstraction  match+action: abstraction unifies different kinds of devices Router Firewall match: longest match: IP addresses destination IP prefix and TCP/UDP port action: forward out a numbers link action: permit or deny Switch match: destination NAT MAC address match: IP address and action: forward or port flood action: rewrite address and port Network Layer: 4-85 OpenFlow example Host h6 Orchestrated tables can 10.3.0.6 1 s3 controller create network-wide 2 4 behavior, e.g.,: 3 Host h5  datagrams from hosts 10.3.0.5 h5 and h6 should be sent to h3 or h4, via s1 Host h1 1 s1 1 s2 and from there to s2 2 Host h4 10.1.0.1 4 2 4 10.2.0.4 3 3 Host h3 Host h2 10.2.0.3 10.1.0.2 Network Layer: 4-86 OpenFlow example match action IP Src = 10.3.*.* forward(3) Host h6 Orchestrated tables can 10.3.0.6 IP Dst = 10.2.*.* 1 s3 controller create network-wide 2 4 behavior, e.g.,: 3 Host h5  datagrams from hosts 10.3.0.5 h5 and h6 should be sent to h3 or h4, via s1 Host h1 1 s1 1 s2 and from there to s2 2 Host h4 10.1.0.1 4 2 4 10.2.0.4 3 3 match match action action Host h3 Host h2 ingress port = 2 ingress port = 1 10.1.0.2 10.2.0.3 forward(3) IP Src = 10.3.*.* forward(4) IP Dst = 10.2.0.3 IP Dst = 10.2.*.* ingress port = 2 forward(4) IP Dst = 10.2.0.4 Network Layer: 4-87 Generalized forwarding: summary  “match plus action” abstraction: match bits in arriving packet header(s) in any layers, take action matching over many fields (link-, network-, transport- layer) local actions: drop, forward, modify, or send matched packet to controller “program” network-wide behaviors  simple form of “network programmability” programmable, per-packet “processing” historical roots: active networking today: more generalized programming: P4 (see p4.org). Network Layer: 4-88 Network layer: “data plane” roadmap  Network layer: overview  What’s inside a router  IP: the Internet Protocol  Generalized Forwarding  Middleboxes middlebox functions evolution, architectural principles of the Internet Network Layer: 4-89 Middleboxes Middlebox (RFC 3234) “any intermediary box performing functions apart from normal, standard functions of an IP router on the data path between a source host and destination host” Middleboxes everywhere! Firewalls, IDS: corporate, institutional, national or global ISP service providers, ISPs NAT: home, cellular, institutional Load balancers: corporate, service provider, data center, mobile nets Application- specific: datacenter network service providers, Caches: service institutional, enterprise provider, mobile, CDN network CDNs Middleboxes  initially: proprietary (closed) hardware solutions  move towards “whitebox” hardware implementing open API  move away from proprietary hardware solutions  programmable local actions via match+action  move towards innovation/differentiation in software  SDN: (logically) centralized control and configuration management often in private/public cloud  network functions virtualization (NFV): programmable services over white box networking, computation, storage The IP hourglass HTTP SMTP RTP … QUIC DASH Internet’s “thin many waist”: TCP UDP protocols in  one network layer protocol: IP IP physical, link,  must be transport, EthernetPPP… implemented by PDC WiFi Bluetoot and every (billions) of P h application Internet- copper radio fiber layers connected devices The IP hourglass, at middle age HTTP SMTP RTP … QUIC DASH Internet’s middle TCP UDP age “love handles”? caching N FV  middleboxes, NAT IP Firewalls operating inside EthernetPPP… the network PDC WiFi Bluetoot P h copper radio fiber Architectural Principles of the Internet RFC 1958 “Many members of the Internet community would argue that there is no architecture, but only a tradition, which was not written down for the first 25 years (or at least not by the the goal is connectivity, the tool is IAB). However, in very general terms, the community believes that the Internet Protocol, and the intelligence is end to end rather than hidden in the network.” Three cornerstone beliefs:  simple connectivity  IP protocol: that narrow waist  intelligence, complexity at network edge The end-end argument  some network functionality (e.g., reliable data transfer, congestion) can be implemented in network, or at network edge applicatio end-end implementation of reliable data transfer applicatio n n transport transport network network data link data link physical physical applicatio applicatio n n transport hop-by-hop (in-network) implementation of reliable data transfer transport network network data link networ data link physical networ networ networ networ networ k physical k k k k k link link link link link link physica physica physica physica physica physica l l l l l l The end-end argument  some network functionality (e.g., reliable data transfer, congestion) can be implemented in network, or at network edge “The function in question can completely and correctly be implemented only with the knowledge and help of the application standing at the end points of the communication system. Therefore, providing that questioned function as a feature of the communication system itself is not possible. (Sometimes an incomplete version of the function provided by the communication system may be useful as a performance enhancement.) We call this line of reasoning against low-level Saltzer, function Reed, Clark 1981 implementation the “end-to-end argument.”  Where’s the intelligence? 20th century phone Internet (pre-2005) Internet (post-2005) net: intelligence, computing programmable network intelligence/computing at at edge devices network switches intelligence, computing, massive application-level infrastructure at edge Chapter 4: done!  Network layer: overview  What’s inside a router  IP: the Internet Protocol  Generalized Forwarding, SDN  Middleboxes Question: how are forwarding tables (destination-based forwarding) or flow tables (generalized forwarding) computed? Answer: by the control plane (next chapter) Additional Chapter 4 slides Network Layer: 4-100 IP fragmentation/reassembly  network links have MTU (max. transfer size) - largest fragmentation: possible link-level frame … in: one large datagram different link types, different out: 3 smaller datagrams MTUs  large IP datagram divided (“fragmented”) within net reassembly one datagram becomes several datagrams … “reassembled” only at destination IP header bits used to identify, order related fragments Network Layer: 4-101 IP fragmentation/reassembly example: length ID fragflag offset =4000 =x =0 =0  4000 byte datagram  MTU = 1500 bytes one large datagram becomes several smaller datagrams 1480 bytes in length ID fragflag offset data field =1500 =x =1 =0 offset = length ID fragflag offset 1480/8 =1500 =x =1 =185 length ID fragflag offset =1040 =x =0 =370 Network Layer: 4-102 DHCP: Wireshark output (home LAN) Message type: Boot Request (1) Hardware type: Ethernet Message type: Boot Reply (2) Hardware type: Ethernet Hardware address length: 6 Hops: 0 request Hardware address length: 6 Hops: 0 reply Transaction ID: 0x6b3a11b7 Seconds elapsed: 0 Transaction ID: 0x6b3a11b7 Bootp flags: 0x0000 (Unicast) Seconds elapsed: 0 Client IP address: 0.0.0.0 (0.0.0.0) Bootp flags: 0x0000 (Unicast) Your (client) IP address: 0.0.0.0 (0.0.0.0) Client IP address: 192.168.1.101 (192.168.1.101) Next server IP address: 0.0.0.0 (0.0.0.0) Your (client) IP address: 0.0.0.0 (0.0.0.0) Relay agent IP address: 0.0.0.0 (0.0.0.0) Next server IP address: 192.168.1.1 (192.168.1.1) Client MAC address: Wistron_23:68:8a (00:16:d3:23:68:8a) Relay agent IP address: 0.0.0.0 (0.0.0.0) Server host name not given Client MAC address: Wistron_23:68:8a (00:16:d3:23:68:8a) Boot file name not given Server host name not given Magic cookie: (OK) Boot file name not given Option: (t=53,l=1) DHCP Message Type = DHCP Request Magic cookie: (OK) Option: (61) Client identifier Option: (t=53,l=1) DHCP Message Type = DHCP ACK Length: 7; Value: 010016D323688A; Option: (t=54,l=4) Server Identifier = 192.168.1.1 Hardware type: Ethernet Option: (t=1,l=4) Subnet Mask = 255.255.255.0 Client MAC address: Wistron_23:68:8a (00:16:d3:23:68:8a) Option: (t=3,l=4) Router = 192.168.1.1 Option: (t=50,l=4) Requested IP Address = 192.168.1.101 Option: (6) Domain Name Server Option: (t=12,l=5) Host Name = "nomad" Length: 12; Value: 445747E2445749F244574092; Option: (55) Parameter Request List IP Address: 68.87.71.226; Length: 11; Value: 010F03062C2E2F1F21F92B IP Address: 68.87.73.242; 1 = Subnet Mask; 15 = Domain Name IP Address: 68.87.64.146 3 = Router; 6 = Domain Name Server Option: (t=15,l=20) Domain Name = "hsd1.ma.comcast.net." 44 = NetBIOS over TCP/IP Name Server …… Network Layer: 4-103