Chapter 4 Network Layer: The Data Plane

1 Computer Networking: A Top Down Approach 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 lotof work on our part. In return for use, we only ask the following: If you use these slides ( , in a class) that you mention their source (after all, we d like people to use our book!) 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 and enjoy! JFK/KWRAll material copyright Kurose and Ross, All Rights Reserved7thedition Jim Kurose, Keith RossPearson/Addison WesleyApril 2016 Chapter 4 Network Layer: The Data Plane4-1 Network Layer: Data Overview of Network layer data Plane control What s inside a IP: Internet Protocol datagram format fragmentation IPv4 addressing Network address translation Generalized Forward and SDN match action OpenFlow examples of match-plus-action in actionChapter 4: outline4-2 Network Layer: Data PlaneChapter 4: Network layerchapter 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 Internet4-3 Network Layer.

2 Data PlaneNetwork 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 everyhost, router router examines header fields in all IP datagrams passing through itapplicationtransportnetworkdata linkphysicalapplicationtransportnetworkd ata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysical4-4 Network Layer: Data PlaneTwo key Network -layer functionsnetwork-layer functions: forwarding:move packets from router s input to appropriate router output routing:determine route taken by packets from source to destination routing algorithmsanalogy: taking a trip forwarding:process of getting through single interchange routing:process of planning trip from source to destination4-5 Network Layer: Data PlaneNetwork layer: data Plane , control planeData Plane local, per-router function determines how datagram arriving on router input port is forwarded to router output port forwarding functionControl 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 (SDN): implemented in (remote) servers1230111values in arriving packet header4-6 Network Layer: Data PlanePer-router control planeRoutingAlgorithmIndividual routing algorithm components in each and every router interact in the control planedataplanecontrolplane5-7 Network Layer.

3 Control Plane120111values in arriving packet header3dataplanecontrolplaneLogically centralized control planeA distinct (typically remote) controller interacts with local control agents (CAs)Remote ControllerCACACACACA5-8 Network Layer: Control Plane1201113values in arriving packet headerNetwork service modelQ:What service modelfor channel transporting datagrams from sender to receiver?example services for individual datagrams: guaranteed delivery guaranteed delivery with less than 40 msec delayexample services for a flow of datagrams: in-order datagram delivery guaranteed minimum bandwidth to flow restrictions on changes in inter-packet spacing4-9 Network Layer: Data PlaneNetwork layer service models:NetworkArchitectureInternetATMATM ATMATMS erviceModelbest effortCBRVBRABRUBRB andwidthnoneconstantrateguaranteedrategu aranteed minimumnoneLossnoyesyesnonoOrdernoyesyes yesyesTimingnoyesyesnonoCongestionfeedba ckno (inferredvia loss)nocongestionnocongestionyesnoGuaran tees ?

4 4-10 Network Layer: Data Overview of Network layer data Plane control What s inside a IP: Internet Protocol datagram format fragmentation IPv4 addressing Network address translation Generalized Forward and SDN match action OpenFlow examples of match-plus-action in actionChapter 4: outline4-11 Network Layer: Data PlaneRouter architecture overviewhigh-seed switchingfabricrouting processorrouter input portsrouter output portsforwarding data Plane (hardware) operttes in nanosecond timeframerouting, managementcontrol Plane (software)operates in millisecond time frame high-level view of generic router architecture:4-12 Network Layer: Data Planelineterminationlink layer protocol(receive)lookup,forwardingqueuei ngInput port functionsdecentralized switching: using header field values, lookup output port using forwarding table in input port memory ( match plus action ) goal: complete input port processing at line speed queuing: if datagrams arrive faster than forwarding rate into switch fabricphysical Layer: bit-level receptiondata link , Ethernetsee Chapter 5switchfabric4-13 Network Layer: Data Planelineterminationlink layer protocol(receive)lookup,forwardingqueuei ngInput port functionsdecentralized switching: using header field values, lookup output port using forwarding table in input port memory ( match plus action ) destination-based forwarding: forward based only on destination IP address (traditional) generalized forwarding: forward based on any set of header field valuesphysical Layer: bit-level receptiondata link , Ethernetsee Chapter 5switchfabric4-14 Network Layer.

5 Data PlaneDestination Address Range11001000 00010111 00010000 00000000through11001000 00010111 00010111 1111111111001000 00010111 00011000 00000000through11001000 00010111 00011000 1111111111001000 00010111 00011001 00000000through11001000 00010111 00011111 11111111otherwiseLink Interface0123Q:but what happens if ranges don t divide up so nicely? Destination-based forwardingforwarding table4-15 Network Layer: Data PlaneLongest prefix matchingDestination Address Range11001000 00010111 00010** **11001000 00010111 00011000 **11001000 00010111 00011** **otherwiseDA: 11001000 00010111 00011000 10101010examples:DA: 11001000 00010111 00010110 10100001 which interface?which interface?when looking for forwarding table entry for given destination address, use longestaddress prefix that matches destination prefix matchingLink interface01234-16 Network Layer: Data PlaneLongest prefix matching we ll seewhy 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: can up ~1M routing table entries in TCAM4-17 Network Layer: Data PlaneSwitching 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 fabricsmemorymemorybuscrossbar4-18 Network Layer.

6 Data PlaneSwitching via memoryfirst 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)inputport( ,Ethernet)memoryoutputport( ,Ethernet)system bus4-19 Network Layer: Data PlaneSwitching via a bus datagram from input port memoryto output port memory via a shared bus bus contention:switching speed limited by bus bandwidth 32 Gbps bus, Cisco 5600: sufficient speed for access and enterprise routersbus4-20 Network Layer: Data PlaneSwitching 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 networkcrossbar4-21 Network Layer: Data PlaneInput port queuing fabric slower than input ports combined -> queueing may occur at input queues queueing delay and loss due to input buffer overflow!

7 Head-of-the-Line (HOL) blocking:queued datagram at front of queue prevents others in queue from moving forwardoutput port contention:only one red datagram can be red packet is blockedswitchfabricone packet time later: green packet experiences HOL blockingswitchfabric4-22 Network Layer: Data PlaneOutput ports bufferingrequired when datagrams arrive from fabric faster than the transmission rate scheduling disciplinechooses among queued datagrams for transmissionlineterminationlink layer protocol(send)switchfabricdatagrambuffer queueingThis slide in HUGELY important!Datagram (packets) can be lost due to congestion, lack of buffersPriority scheduling who gets best performance, Network neutrality4-23 Network Layer: Data PlaneOutput port queueing buffering when arrival rate via switch exceeds output line speed queueing (delay) and loss due to output port buffer overflow!at t,packets morefrom input to outputone packet time laterswitchfabricswitchfabric4-24 Network Layer: Data PlaneHow much buffering?

8 RFC 3439 rule of thumb: average buffering equal to typical RTT (say 250 msec) times link capacity C , C = 10 Gpbs link: Gbit buffer recent recommendation: with Nflows, buffering equal to RTT Layer: Data PlaneScheduling mechanisms scheduling: choose next packet to send on link FIFO (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 randomlyqueue(waiting area)packetarrivalspacketdepartureslink( server)4-26 Network Layer: Data PlaneScheduling policies: prioritypriority scheduling: send highest priority queued packet multiple classes, with different priorities class may depend on marking or other header info, IP source/dest, port numbers, etc. real world example? high priority queue(waiting area)low priority queue(waiting area)arrivalsclassifydepartureslink(serv er)132455522113344arrivalsdeparturespack et in service4-27 Network Layer: Data PlaneScheduling policies: still moreRound Robin (RR) scheduling: multiple classes cyclically scan class queues, sending one complete packet from each class (if available) real world example?

9 123455523113344arrivalsdeparturespacket in service4-28 Network Layer: Data PlaneWeighted Fair Queuing (WFQ): generalized Round Robin each class gets weighted amount of service in each cycle real-world example?Scheduling policies: still more4-29 Network Layer: Data Overview of Network layer data Plane control What s inside a IP: Internet Protocol datagram format fragmentation IPv4 addressing Network address translation Generalized Forward and SDN match action OpenFlow examples of match-plus-action in actionChapter 4: outline4-30 Network Layer: Data PlaneThe Internet Network layerforwardingtablehost, router Network layer functions:routing protocols path selection RIP, OSPF, BGPIP protocol addressing conventions datagram format packet handling conventionsICMP protocol error reporting router signaling transport layer: TCP, UDPlink layerphysical layernetworklayer4-31 Network Layer: Data Planeverlength32 bitsdata (variable length,typically a TCP or UDP segment)16-bit identifierheaderchecksumtime tolive32 bit source IP ofserviceflgsfragmentoffsetupperlayer32 bit destination IP addressoptions (if any)IP datagram formatIP protocol versionnumberheader length(bytes)upper layer protocolto deliver payload tototal datagramlength (bytes) type of data forfragmentation/reassemblymax numberremaining hops(decremented at each router) timestamp,record routetaken, specifylist of routers to much overhead?

10 20 bytes of TCP 20 bytes of IP = 40 bytes + app layer overhead4-32 Network Layer: Data PlaneIP fragmentation, reassembly Network links have MTU ( size) -largest possible link-level frame different link types, different MTUs large IP datagram divided ( fragmented ) within net one datagram becomes several datagrams reassembled only at final destination IP header bits used to identify, order ltdftfragmentation:in:one large datagramout:3 smaller Layer: Data PlaneID=xoffset=0fragflag=0length=4000ID =xoffset=0fragflag=1length=1500ID=xoffse t=185fragflag=1length=1500ID=xoffset=370 fragflag=0length=1040one large datagram becomesseveral smaller datagramsexample: 4000 byte datagram MTU = 1500 bytes1480 bytes in data fieldoffset =1480/8 IP fragmentation, reassembly4-34 Network Layer: Data Overview of Network layer data Plane control What s inside a IP: Internet Protocol datagram format fragmentation IPv4 addressing Network address translation Generalized Forward and SDN match action OpenFlow examples of match-plus-action in actionChapter 4: outline4-35 Network Layer: Data PlaneIP addressing: introduction IP 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 ( , wired Ethernet, wireless ) IP addresses associated with each = 11011111 00000001 00000001 000000012231114-36 Network Layer: Data PlaneIP addressing: introductionQ: how are interfaces actually connected?