CPSC 441 Computer Networks Lecture Notes PDF

CPSC 441 Computer Networks Majid Ghaderi Department of Computer Science University of Calgary Network Layer Data Plane chapter goals: § understand principles behind network layer services, focusing on data plane: forwarding versus routing how a router works generalized...

CPSC 441 Computer Networks Majid Ghaderi Department of Computer Science University of Calgary Network Layer Data Plane chapter goals: § understand principles behind network layer services, focusing on data plane: forwarding versus routing how a router works generalized forwarding § instantiation, implementation in the Internet CPSC 441 - Network Layer: Data Plane 2 Chapter 4: outline 4.1 Overview of Network 4.4 Generalized Forwarding layer and SDN data plane match plus action control plane OpenFlow 4.2 What’s inside a router 4.3 IP: Internet Protocol datagram format fragmentation IPv4 addressing NAT IPv6 CPSC 441 - Network Layer: Data Plane 3 Network layer application § transport segment from transport network sending to receiving host data link physical network network § on sending side network data link data link physical data link physical encapsulates segments physical network data link network data link into datagrams physical physical § on receiving side, delivers network data link network data link segments to transport physical physical network data link layer network physical application transport § network layer protocols network data link physical network data link network data link in every host, router data link physical physical physical § router examines header fields in all IP datagrams passing through it CPSC 441 - Network Layer: Data Plane 4 Two key network-layer functions network-layer functions: analogy: taking a trip §forwarding: move packets § forwarding: process of from router’s input to getting through single appropriate router output interchange §routing: determine route taken by packets from § routing: process of source to destination planning trip from source routing algorithms to destination CPSC 441 - Network Layer: Data Plane 5  Network layer: data plane, control plane Data plane Control plane § local, per-router function § network-wide logic § determines how datagram § determines how datagram is arriving on router input routed among routers along port is forwarded to end-end path from source host router output port to destination host § forwarding function § two control-plane approaches: traditional routing algorithms: values in arriving packet header implemented in routers 1 software-defined networking 0111 2 (SDN): implemented in 3 (remote) servers CPSC 441 - Network Layer: Data Plane 6  Per-router control plane Individual routing algorithm components in each and every router interact in the control plane 4.1 OVERVIEW OF NETWORK LAYER 309 Routing Algorithm Routing algorithm control Control plane plane Data plane Local forwarding table data header output plane 0100 3 0110 2 0111 2 1001 1 Values in arriving values in arriving packet’s header 1 packet header 1101 2 3 0111 1 2 3 Figure 4.2 ♦ Routing algorithms determine values in forward tables CPSC 441 - Network Layer: Data Plane 7 tables. In this example, a routing algorithm runs in each and every router and both forwarding and routing functions are contained within a router. As we’ll see in Sec- tions 5.3 and 5.4, the routing algorithm function in one router communicates with  Logically centralized control plane A distinct (typically remote) controller interacts with local control agents (CAs) Remote Controller control plane data plane CA CA CA CA CA values in arriving packet header 0111 1 2 3 CPSC 441 - Network Layer: Data Plane 8 Chapter 4: outline 4.1 Overview of Network 4.4 Generalized Forwarding layer and SDN data plane match plus action control plane OpenFlow 4.2 What’s inside a router 4.3 IP: Internet Protocol datagram format fragmentation IPv4 addressing NAT IPv6 CPSC 441 - Network Layer: Data Plane 9  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-seed switching fabric router input ports router output ports CPSC 441 - Network Layer: Data Plane 10  Input port functions lookup, link forwarding line layer switch termination protocol fabric (receive) queueing physical layer: bit-level reception data link layer: decentralized switching: e.g., Ethernet § using header field values, lookup output port using forwarding table in input port memory § queuing: if datagrams arrive faster than forwarding rate into switch fabric CPSC 441 - Network Layer: Data Plane 11  Input port functions lookup, link forwarding line layer switch termination protocol fabric (receive) queueing physical layer: bit-level reception decentralized switching: data link layer: § using header field values, lookup output e.g., Ethernet port using forwarding table in input port memory § destination-based forwarding: forward based only on destination IP address (traditional) § generalized forwarding: forward based on any set of header field values CPSC 441 - Network Layer: Data Plane 12 Destination-based forwarding forwarding table Destination Address Range Link Interface 11001000 00010111 00010000 00000000 through 0 11001000 00010111 00010111 11111111 11001000 00010111 00011000 00000000 through 1 11001000 00010111 00011000 11111111 11001000 00010111 00011000 00000000 through 2 11001000 00010111 00011111 11111111 otherwise 3 CPSC 441 - Network Layer: Data Plane 13 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 11001000 00010111 00010*** ******** 0 11001000 00010111 00011000 ******** 1 11001000 00010111 00011*** ******** 2 otherwise 3 examples: DA: 11001000 00010111 00010110 10100001 which interface? DA: 11001000 00010111 00011000 10101010 which interface? CPSC 441 - Network Layer: Data Plane 14 Switching fabrics § transfer packet from input buffer to appropriate output buffer § switching rate: rate at which packets can be transferred from inputs to outputs § three types of switching fabrics memory memory bus crossbar CPSC 441 - Network Layer: Data Plane 15 Output ports datagram switch buffer link fabric layer line protocol termination queueing (send) § buffering required when datagrams arrive from fabric faster than the transmission rate § scheduling discipline chooses among queued datagrams for transmission CPSC 441 - Network Layer: Data Plane 16 Output ports datagram switch buffer link fabric layer line protocol termination queueing (send) § buffering required when datagrams Datagram arrive (packets) can be lost from fabric faster than the due to transmission congestion, lack of buffers rate § scheduling discipline chooses Priority among scheduling – who queued gets best datagrams for transmission performance, network neutrality CPSC 441 - Network Layer: Data Plane 17 How much buffering? § RFC 3439 rule of thumb: average buffering equal to “typical” RTT (say 250 msec) times link capacity C aka: Delay-Bandwidth Product e.g., C = 10 Gpbs link: 2.5 Gbit buffer CPSC 441 - Network Layer: Data Plane 18 Chapter 4: outline 4.1 Overview of Network 4.4 Generalized Forwarding layer and SDN data plane match plus action control plane OpenFlow 4.2 What’s inside a router 4.3 IP: Internet Protocol datagram format fragmentation IPv4 addressing NAT IPv6 CPSC 441 - Network Layer: Data Plane 19 The Internet network layer host, router network layer functions: transport layer: TCP, UDP routing protocols IP protocol path selection addressing conventions OSPF, BGP datagram format network packet handling conventions layer forwarding table ICMP protocol error reporting router “signaling” link layer physical layer CPSC 441 - Network Layer: Data Plane 20  IP datagram format IP protocol version 32 bits number total datagram header length type of length (bytes) ver head. length (bytes) len service for fragment fragmentation/ 16-bit identifier flgs offset reassembly max number time to upper header remaining hops live layer checksum (decremented at 32 bit source IP address each router) 32 bit destination IP address options (if any) how much overhead? data (variable length, v 20 bytes of TCP typically a TCP v 20 bytes of IP or UDP segment) v = 40 bytes + app layer overhead CPSC 441 - Network Layer: Data Plane 21  IP fragmentation, reassembly § network links have MTU (max. transfer unit) - largest possible link-level fragmentation: … frame in: one large datagram different link types, out: 3 smaller datagrams different MTUs § large IP datagram divided (“fragmented”) within net reassembly one datagram becomes several datagrams “reassembled” only at … final destination IP header bits used to identify, order related fragments CPSC 441 - Network Layer: Data Plane 22 Chapter 4: outline 4.1 Overview of Network 4.4 Generalized Forwarding layer and SDN data plane match plus action control plane OpenFlow 4.2 What’s inside a router 4.3 IP: Internet Protocol datagram format fragmentation IPv4 addressing NAT IPv6 CPSC 441 - Network Layer: Data Plane 23 IP addressing 223.1.1.1 § IP address: 32-bit 223.1.2.1 identifier for host, router interface 223.1.1.2 223.1.1.4 223.1.2.9 § interface: connection between host/router and 223.1.3.27 physical link 223.1.1.3 223.1.2.2 routers typically have multiple interfaces hosts typically have one or 223.1.3.1 223.1.3.2 two interfaces (e.g., wired Ethernet, wireless 802.11) § IP addresses associated with each interface 223.1.1.1 = 11011111 00000001 00000001 00000001 223 1 1 1 CPSC 441 - Network Layer: Data Plane 24 Subnets § IP address: 223.1.1.1 subnet part - high order bits 223.1.1.2 223.1.2.1 223.1.1.4 223.1.2.9 host part - low order bits 223.1.2.2 223.1.1.3 223.1.3.27 § what’s a subnet ? device interfaces with subnet same subnet part of IP 223.1.3.2 address 223.1.3.1 can physically reach each other without intervening router network consisting of 3 subnets CPSC 441 - Network Layer: Data Plane 25 Subnets 223.1.1.1 Q: how are interfaces in a 223.1.2.1 subnet connected? 223.1.1.2 223.1.1.4 223.1.2.9 223.1.3.27 223.1.1.3 223.1.2.2 A: wired Ethernet interfaces connected by Ethernet switches 223.1.3.1 223.1.3.2 A: wireless WiFi interfaces connected by WiFi base station CPSC 441 - Network Layer: Data Plane 26 Subnets 223.1.1.0/24 223.1.2.0/24 recipe 223.1.1.1 § to determine the 223.1.1.2 223.1.2.1 subnets, detach each 223.1.1.4 223.1.2.9 interface from its host 223.1.2.2 or router, creating 223.1.1.3 223.1.3.27 islands of isolated subnet networks 223.1.3.2 § each isolated network 223.1.3.1 is called a subnet 223.1.3.0/24 subnet mask: /24 CPSC 441 - Network Layer: Data Plane 27 Subnets 223.1.1.2 how many? 223.1.1.1 223.1.1.4 223.1.1.3 223.1.9.2 223.1.7.2 223.1.9.1 223.1.7.1 223.1.8.1 223.1.8.2 223.1.2.6 223.1.3.27 223.1.2.1 223.1.2.2 223.1.3.1 223.1.3.2 CPSC 441 - Network Layer: Data Plane 28 IP addressing: CIDR CIDR: Classless InterDomain Routing 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 CPSC 441 - Network Layer: Data Plane 29 IP addresses: how to get one? Q: How does a host get IP address? § hard-coded by system admin in a file Windows: control-panel->network->configuration- >tcp/ip->properties Linux: /etc/network/interfaces § DHCP: Dynamic Host Configuration Protocol: dynamically get address from a server “plug-and-play” CPSC 441 - Network Layer: Data Plane 30 DHCP: Dynamic Host Configuration Protocol goal: allow host to dynamically obtain its 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 want to join network CPSC 441 - Network Layer: Data Plane 31 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) CPSC 441 - Network Layer: Data Plane 32 DHCP: example DHCP DHCP § connecting laptop needs DHCP UDP its IP address, addr of DHCP IP DHCP Eth first-hop router, addr of Phy DNS server: use DHCP DHCP § DHCP request encapsulated in UDP, encapsulated in IP, DHCP DHCP 168.1.1.1 encapsulated in Ethernet DHCP UDP DHCP IP DHCP Eth router with DHCP § Ethernet frame broadcast on Phy server built into LAN, received at router router running DHCP server § Ethernet de-encapsulated to IP, UDP and eventually DHCP CPSC 441 - Network Layer: Data Plane 33 DHCP: example DHCP DHCP § DHCP server formulates DHCP UDP DHCP ACK containing DHCP IP client’s IP address, IP DHCP Eth address of first-hop Phy router for client, name & IP address of DNS server § encapsulation of DHCP DHCP DHCP server, forwarded to client DHCP UDP § client now knows its IP DHCP IP Eth address, name and IP DHCP router with DHCP Phy address of DSN server, IP server built into DHCP router address of its first-hop router CPSC 441 - Network Layer: Data Plane 34 IP addresses: how to get one? Q: how does network get subnet part of IP addr? A: gets allocated portion of its provider ISP’s address space ISP's block 11001000 00010111 00010000 00000000 200.23.16.0/20 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 CPSC 441 - Network Layer: Data Plane 35 IP addressing: the last word... Q: how does an ISP get block of addresses? A: ICANN: Internet Corporation for Assigned Names and Numbers http://www.icann.org/ allocates addresses manages DNS assigns domain names, resolves disputes CPSC 441 - Network Layer: Data Plane 36 Chapter 4: outline 4.1 Overview of Network 4.4 Generalized Forwarding layer and SDN data plane match plus action control plane OpenFlow 4.2 What’s inside a router 4.3 IP: Internet Protocol datagram format fragmentation IPv4 addressing NAT IPv6 CPSC 441 - Network Layer: Data Plane 37  NAT: network address translation rest of local network Internet (e.g., home network) 10.0.0.0/24 10.0.0.1 10.0.0.4 10.0.0.2 138.76.29.7 10.0.0.3 all datagrams leaving local datagrams with source or network have same single destination in this network source NAT IP address: have 10.0.0.0/24 address for 138.76.29.7,different source source, destination (as usual) port numbers CPSC 441 - Network Layer: Data Plane 38  NAT: network address translation motivation: local network uses just one IP address as far as outside world is concerned: § range of addresses not needed from ISP: just one IP address for all devices § can change addresses of devices in local network without notifying outside world § can change ISP without changing addresses of devices in local network § devices inside local net not explicitly addressable, visible by outside world (a security plus) CPSC 441 - Network Layer: Data Plane 39  NAT: network address translation NAT translation table 1: host 10.0.0.1 2: NAT router WAN side addr LAN side addr changes datagram sends datagram to source addr from 138.76.29.7, 5001 10.0.0.1, 3345 128.119.40.186, 80 10.0.0.1, 3345 to …… …… 138.76.29.7, 5001, updates table S: 10.0.0.1, 3345 D: 128.119.40.186, 80 10.0.0.1 1 S: 138.76.29.7, 5001 2 D: 128.119.40.186, 80 10.0.0.4 10.0.0.2 138.76.29.7 S: 128.119.40.186, 80 D: 10.0.0.1, 3345 4 S: 128.119.40.186, 80 D: 138.76.29.7, 5001 3 10.0.0.3 4: NAT router 3: reply arrives changes datagram dest. address: dest addr from 138.76.29.7, 5001 138.76.29.7, 5001 to 10.0.0.1, 3345 CPSC 441 - Network Layer: Data Plane 40 Chapter 4: outline 4.1 Overview of Network 4.4 Generalized Forwarding layer and SDN data plane match plus action control plane OpenFlow 4.2 What’s inside a router 4.3 IP: Internet Protocol datagram format fragmentation IPv4 addressing NAT IPv6 CPSC 441 - Network Layer: Data Plane 41 IPv6: motivation § initial motivation: 32-bit address space soon to be completely allocated 128 bit addresses (16 bytes) in IPv6 § additional motivation: header format helps speed up processing/forwarding fixed-length 40 byte header no fragmentation allowed checksum removed entirely to reduce processing time at each hop CPSC 441 - Network Layer: Data Plane 42 IPv6 datagram format ver pri flow label payload len next hdr hop limit source address (128 bits) destination address (128 bits) data 32 bits CPSC 441 - Network Layer: Data Plane 43 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 IPv4 header fields IPv6 header fields IPv4 payload IPv4 source, dest addr IPv6 source dest addr UDP/TCP payload IPv6 datagram IPv4 datagram CPSC 441 - Network Layer: Data Plane 44 Tunneling A B IPv4 tunnel E F connecting IPv6 routers logical view: IPv6 IPv6 IPv6 IPv6 A B C D E F physical view: IPv6 IPv6 IPv4 IPv4 IPv6 IPv6 CPSC 441 - Network Layer: Data Plane 45 Tunneling A B IPv4 tunnel E F connecting IPv6 routers logical view: IPv6 IPv6 IPv6 IPv6 A B C D E F physical view: IPv6 IPv6 IPv4 IPv4 IPv6 IPv6 flow: X src:B src:B flow: X src: A dest: E src: A dest: F dest: E dest: F Flow: X Flow: X Src: A Src: A data Dest: F Dest: F data data data A-to-B: E-to-F: IPv6 B-to-C: B-to-C: IPv6 IPv6 inside IPv6 inside IPv4 IPv4 CPSC 441 - Network Layer: Data Plane 46 Chapter 4: outline 4.1 Overview of Network 4.4 Generalized Forwarding layer and SDN data plane match plus action control plane OpenFlow 4.2 What’s inside a router 4.3 IP: Internet Protocol datagram format fragmentation IPv4 addressing NAT IPv6 CPSC 441 - Network Layer: Data Plane 47 Generalized Forwarding and SDN Each router contains a flow table that is computed and distributed by a logically centralized routing controller logically-centralized routing controller control plane data plane local flow table headers counters actions 1 0100 1101 3 2 values in arriving packet’s header CPSC 441 - Network Layer: Data Plane 48 OpenFlow data plane abstraction § flow: defined by header fields § generalized forwarding: simple packet-handling rules Pattern: match values in packet header fields Actions: for matched packet: drop, forward, modify, matched packet or send matched packet to controller Flow table in a router (computed and distributed by controller) defines router’s match+action rules CPSC 441 - Network Layer: Data Plane 49 OpenFlow data plane abstraction § flow: defined by header fields § generalized forwarding: simple packet-handling rules Pattern: match values in packet header fields Actions: for matched packet: drop, forward, modify, matched packet or send matched packet to controller * : wildcard 1. src=1.2.*.*, dest=3.4.5.* à drop 2. src = *.*.*.*, dest=3.4.*.* à forward(2) 3. src=10.1.2.3, dest=*.*.*.* à send to controller CPSC 441 - Network Layer: Data Plane 50