If this PowerPoint presentation contains mathematical equations, you may need to check that your computer has the following installed: 1) MathType Plugin 2) Math Player (free versions available) 3) NVDA Reader (free versions available) Slides in this presentation contain hyperlinks. JAWS users should be able to get a list of links by using INSERT+F7 Copyright © 2017, 2013, 2010 Pearson Education, Inc. All Rights Reserved

2 Learning Objectives (1 of 7) 4.1 Overview of Network layer data plane control plane 4.2 What’s inside a router 4.3 I P: Internet Protocol datagram format fragmentation I Pv4 addressing network address translation I Pv6 4.4 Generalized Forward and S D N match action OpenFlow examples of match- plus-action in action

3 Chapter 4: Network Layer chapter goals: understand principles behind network layer services, focusing on data plane: network layer service models forwarding versus routing how a router works generalized forwarding instantiation, implementation in the Internet

4 Network Layer transport segment from sending to receiving host on sending side encapsulates segments into datagrams on receiving side, delivers segments to transport layer network layer protocols in every host, router router examines header fields in all I P datagrams passing through it

5 Two Key Network-Layer Functions forwarding: move packets from router’s input to appropriate router output routing: determine route taken by packets from source to destination routing algorithms analogy: taking a trip forwarding: process of getting through single interchange routing: process of planning trip from source to destination

6 Network Layer: Data Plane, Control Plane local, per-router function determines how datagram arriving on router input port is forwarded to router output port forwarding function Control plane network-wide logic determines how datagram is routed among routers along end- end path from source host to destination host two control-plane approaches: traditional routing algorithms: implemented in routers software-defined networking (S D N): implemented in (remote) servers

7 Per-Router Control Plane Individual routing algorithm components in each and every router interact in the control plane

8 Logically Centralized Control Plane A distinct (typically remote) controller interacts with local control agents (C A s)

9 Network Service Model Q: What service model for “channel” transporting datagrams from sender to receiver? example services for individual datagrams: guaranteed delivery guaranteed delivery with less than 40 msec delay example services for a flow of datagrams: in-order datagram delivery guaranteed minimum bandwidth to flow restrictions on changes in inter-packet spacing

10 Network Layer Service Models: Architecture Service Model Guarantees ? Bandwidth Loss Order Timing Congestion feedback Internet best effort none no no (inferred via loss) A T M C B R constant rate yes congestion V B R guaranteed A B R minimum U B R

11 Learning Objectives (2 of 7) 4.1 Overview of Network layer data plane control plane 4.2 What’s inside a router 4.3 I P: Internet Protocol datagram format fragmentation I Pv4 addressing network address translation I Pv6 4.4 Generalized Forward and S D N match action OpenFlow examples of match- plus-action in action

12 Router Architecture Overview high-level view of generic router architecture:

13 Input Port Functions (1 of 2)

14 Input Port Functions (2 of 2)

15 Destination-Based Forwarding Q: but what happens if ranges don’t divide up so nicely?

16 Longest Prefix Matching (1 of 2) when looking for forwarding table entry for given destination address, use longest address prefix that matches destination address. examples:

17 Longest Prefix Matching (2 of 2) we’ll see why longest prefix matching is used shortly, when we study addressing longest prefix matching: often performed using ternary content addressable memories (T C A M s) content addressable: present address to T C A M : retrieve address in one clock cycle, regardless of table size Cisco Catalyst: can up ~1M routing table entries in T C A M

18 Switching Fabrics transfer packet from input buffer to appropriate output buffer 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 types of switching fabrics

19 Switching via Memory first generation routers: traditional computers with switching under direct control of C P U packet copied to system’s memory speed limited by memory bandwidth (2 bus crossings per datagram)

20 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 G b p s bus, Cisco 5600: sufficient speed for access and enterprise routers

21 Switching via Interconnection Network overcome bus bandwidth limitations banyan networks, crossbar, other interconnection nets initially developed to connect processors in multiprocessor advanced design: fragmenting datagram into fixed length cells, switch cells through the fabric. Cisco 12000: switches 60 Gbps through the interconnection network

22 Input Port Queuing 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 (H O L) blocking: queued datagram at front of queue prevents others in queue from moving forward

23 Output Ports buffering required when datagrams arrive from fabric faster than the transmission rate Datagram (packets) can be lost due to congestion, lack of buffers scheduling discipline chooses among queued datagrams for transmission Priority scheduling – who gets best performance, network neutrality

24 Output Port Queueing buffering when arrival rate via switch exceeds output line speed queueing (delay) and loss due to output port buffer overflow!

25 How Much Buffering? R F C 3439 rule of thumb: average buffering equal to “typical” R T T (say 250 msec) times link capacity C e.g., C = 10 G p b s link: 2.5 Gbit buffer recent recommendation: with N flows, buffering equal to

26 Scheduling Mechanisms scheduling: choose next packet to send on link F I F O (first in first out) scheduling: send in order of arrival to queue real-world example? discard policy: if packet arrives to full queue: who to discard? tail drop: drop arriving packet priority: drop/remove on priority basis random: drop/remove randomly

27 Scheduling Policies: Priority priority scheduling: send highest priority queued packet multiple classes, with different priorities class may depend on marking or other header info, e.g. I P source/dest, port numbers, etc. real world example?

28 Scheduling Policies: Round Robin Round Robin (R R) scheduling: multiple classes cyclically scan class queues, sending one complete packet from each class (if available) real world example?

29 Scheduling Policies: Weighted Fair Queuing Weighted Fair Queuing (W F Q): generalized Round Robin each class gets weighted amount of service in each cycle real-world example?

30 Learning Objectives (3 of 7) 4.1 Overview of Network layer data plane control plane 4.2 What’s inside a router 4.3 I P: Internet Protocol datagram format fragmentation I Pv4 addressing network address translation I Pv6 4.4 Generalized Forward and S D N match action OpenFlow examples of match- plus-action in action

31 The Internet Network Layer host, router network layer functions:

32 I P Datagram Format how much overhead? 20 bytes of T C P 20 bytes of I P \= 40 bytes + app layer overhead

33 I P Fragmentation, Reassembly (1 of 2) network links have M T U (max.transfer size) - largest possible link-level frame different link types, different M T U s large I P datagram divided (“fragmented”) within net one datagram becomes several datagrams “reassembled” only at final destination I P header bits used to identify, order related fragments

34 I P Fragmentation, Reassembly (2 of 2) example: 4000 byte datagram M T U = bytes

35 Learning Objectives (4 of 7) 4.1 Overview of Network layer data plane control plane 4.2 What’s inside a router 4.3 I P: Internet Protocol datagram format fragmentation I Pv4 addressing network address translation I Pv6 4.4 Generalized Forward and S D N match action OpenFlow examples of match- plus-action in action

36 I P Addressing: Introduction (1 of 2) I P address: 32-bit identifier for host, router interface interface: connection between host/router and physical link Router’s typically have multiple interfaces host typically has one or two interfaces (e.g., wired Ethernet, wireless ) I P addresses associated with each interface

37 I P Addressing: Introduction (2 of 2) Q: how are interfaces actually connected? A: we’ll learn about that in chapter 5, 6. For now: don’t need to worry about how one interface is connected to another (with no intervening router)

38 Subnets (1 of 3) I P address: subnet part - high order bits host part - low order bits What’s subnet ? device interfaces with same subnet part of I P address can physically reach each other without intervening router

39 Subnets (2 of 3) recipe to determine the subnets, detach each interface from its host or router, creating islands of isolated networks each isolated network is called a subnet

40 Subnets (3 of 3) how many?

41 I P Addressing: C I D R C I D R: Classless Inter Domain Routing subnet portion of address of arbitrary length address format: where x is # bits in subnet portion of address

42 I P Addresses: How to Get One? (1 of 2) Q: How does a host get I P address? hard-coded by system admin in a file Windows: control-panel->network->configuration- >t c p/i p->properties U N I X: /etc/rc.config D H C P: Dynamic Host Configuration Protocol: dynamically get address from as server “plug-and-play”

43 D H C P: Dynamic Host Configuration Protocol goal: allow host to dynamically obtain its I P 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 (more shortly) D H C P overview: host broadcasts “D H C P discover” msg [optional] D H C P server responds with “D H C P offer” msg [optional] host requests I P address: “D H C P request” msg D H C P server sends address: “D H C P ack” msg

44 D H C P Client-Server Scenario (1 of 2)

45 D H C P Client-Server Scenario (2 of 2)

46 D H C P: More Than I P Addresses D H C P can return more than just allocated I P address on subnet: address of first-hop router for client name and I P address of D N S sever network mask (indicating network versus host portion of address)

47 D H C P: Example (1 of 2) connecting laptop needs its I P address, addr of first-hop router, addr of D N S server: use D H C P D H C P request encapsulated in U D P, encapsulated in I P, encapsulated in Ethernet Ethernet frame broadcast (dest: FFFFFFFFFFFF) on LAN, received at router running D H C P server Ethernet demuxed to I P demuxed, U D P demuxed to D H C P

48 D H C P: Example (2 of 2) D C P server formulates D H C P A C K containing client’s I P address, I P address of first-hop router for client, name & I P address of D S N server encapsulation of D H C P server, frame forwarded to client, demuxing up to D H C P at client client now knows its I P address, name and I P address of D S N server, I P address of its first-hop router

49 D H C P: Wireshark Output (Home LAN)

50 I P Addresses: How to Get One? (2 of 2) Q: how does network get subnet part of I P addr? A: gets allocated portion of its provider I S P’s address space

51 Hierarchical Addressing: Route Aggregation hierarchical addressing allows efficient advertisement of routing information:

52 Hierarchical Addressing: More Specific Routes I S P s-R-U s has a more specific route to Organization 1

53 I P Addressing: The Last Word Q: how does an I S P get block of addresses? A: I C A N N: Internet Corporation for Assigned Names and Numbers allocates addresses manages D N S assigns domain names, resolves disputes

54 N A T: Network Address Translation (1 of 5)

55 N A T: Network Address Translation (2 of 5) motivation: local network uses just one I P address as far as outside world is concerned: range of addresses not needed from I S P: just one I P address for all devices can change addresses of devices in local network without notifying outside world can change I S P without changing addresses of devices in local network devices inside local net not explicitly addressable, visible by outside world (a security plus)

56 N A T: Network Address Translation (3 of 5) implementation: N A T router must: outgoing datagrams: replace (source I P address, port #) of every outgoing datagram to (N A T I P address, new port #) remote clients/servers will respond using (N A T I P address, new port #) as destination addr remember (in N A T translation table) every (source I P address, port #) to (N A T I P address, new port #) translation pair incoming datagrams: replace (N A T I P address, new port #) in dest fields of every incoming datagram with corresponding (source I P address, port #) stored in N A T table

57 N A T: Network Address Translation (4 of 5)

58 N A T: Network Address Translation (5 of 5) 16-bit port-number field: 60,000 simultaneous connections with a single L A N-side address! N A T is controversial: routers should only process up to layer 3 address shortage should be solved by I P v 6 violates end-to-end argument N A T possibility must be taken into account by app designers, e.g., P 2 P applications N A T traversal: what if client wants to connect to server behind N A T?

59 Learning Objectives (5 of 7) 4.1 Overview of Network layer data plane control plane 4.2 What’s inside a router 4.3 I P: Internet Protocol datagram format fragmentation I Pv4 addressing network address translation I Pv6 4.4 Generalized Forward and S D N match action OpenFlow examples of match- plus-action in action

60 I P v 6: Motivation initial motivation: 32-bit address space soon to be completely allocated. additional motivation: header format helps speed processing/forwarding header changes to facilitate Q o S I P v 6 datagram format: fixed-length 40 byte header no fragmentation allowed

61 I P v 6 Datagram Format priority: identify priority among datagrams in flow flow Label: identify datagrams in same “flow.” (concept of ”flow” not well defined). next header: identify upper layer protocol for data

62 Other Changes from I P v 4 checksum: removed entirely to reduce processing time at each hop options: allowed, but outside of header, indicated by “Next Header” field I C M P v 6: new version of I C M P additional message types, e.g. “Packet Too Big” multicast group management functions

63 Transition from I P v 4 to I P v 6 not all routers can be upgraded simultaneously no “flag days” how will network operate with mixed I P v 4 and I P v 6 routers? tunneling: I P v 6 datagram carried as payload in I P v 4 datagram among I P v 4 routers

64 Tunneling (1 of 2)

65 Tunneling (2 of 2)

66 I P v 6: Adoption Google: 8% of clients access services via I P v 6 N I S T: 1/3 of all U S government domains are I P v 6 capable Long (long!) time for deployment, use 20 years and counting! think of application-level changes in last 20 years: WWW, Facebook, streaming media, Skype, … Why?

67 Learning Objectives (6 of 7) 4.1 Overview of Network layer data plane control plane 4.2 What’s inside a router 4.3 I P: Internet Protocol datagram format fragmentation I Pv4 addressing network address translation I Pv6 4.4 Generalized Forward and S D N match action OpenFlow examples of match-plus-action in action

68 Generalized Forwarding and S D N Each router contains a flow table that is computed and distributed by a logically centralized routing controller

69 OpenFlow Data Plane Abstraction (1 of 2) 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 Priority: disambiguate overlapping patterns Counters:

bytes and

packets Flow table in a router (computed and distributed by controller) define router’s match+action rules

70 OpenFlow Data Plane Abstraction (2 of 2) * : wildcard

71 OpenFlow: Flow Table Entries

72 Example (1 of 2) Destination-based forwarding: Firewall:

73 Example (2 of 2) Destination-based layer 2 (switch) forwarding:

74 OpenFlow Abstraction (1 of 2) match+action: unifies different kinds of devices Router match: longest destination I P prefix action: forward out a link Switch match: destination MAC address action: forward or flood

75 OpenFlow Abstraction (2 of 2) Firewall match: I P addresses and T C P/U D P port numbers action: permit or deny N A T match: I P address and port action: rewrite address and port

76 OpenFlow Example Example: datagrams from hosts h5 and h6 should be sent to h3 or h4, via s1 and from there to s2

77 Learning Objectives (7 of 7) 4.1 Overview of Network layer data plane control plane 4.2 What’s inside a router 4.3 I P: Internet Protocol datagram format fragmentation I Pv4 addressing network address translation I Pv6 4.4 Generalized Forward and S D N Match plus action OpenFlow examples of match-plus-action in action Question: how do forwarding tables (destination-based forwarding) or flow tables (generalized forwarding) computed? Answer: by the control plane (next chapter)