计算机网络-自顶向下方法与INTERNET特色.ppt

Chapter 4 The Network Layer Computer Networking A Top-Down Approach Featuring the Internet计算机网络计算机网络-自顶向下方法与自顶向下方法与Internet特色特色School of Computer Science&Technology2 2IntroductionrChapter goalsqunderstand principles behind network layer services:prouting(path selection)pdealing with scalephow a router workspadvanced topics:IPv6,mobilityqinstantiation and implementation in the InternetSchool of Computer Science&Technology3 3roadmaprr4.1 Introduction4.1 Introductionrr4.2 Virtual circuit and datagram networks4.2 Virtual circuit and datagram networksrr4.3 Whats inside a router4.3 Whats inside a routerrr4.4 IP:Internet Protocol4.4 IP:Internet Protocolr4.5 Routing algorithmsqLink state、Distance Vector、Hierarchical routingr4.6 Routing in the InternetqRIP、OSPF、BGPrr4.7 4.7 Broadcast and multicast routingBroadcast and multicast routingrSummarySchool of Computer Science&Technology4 44.1 Network layer introductionrServices descriptionrKey Network-Layer FunctionsqRoutingqForwardingqConnection setuprNetwork service modelSchool of Computer Science&Technology5 51、Key Network-Layer FunctionsForwarding move packets from routers input to appropriate router outputRouting determine the route(path)taken by packets from source to dest.rrouting algorithms4.1 introductionSchool of Computer Science&Technology6 61、Key Network-Layer FunctionsConnection setupq3rd important function in some network architectures:pATM,frame relay,X.25qBefore datagrams flow,two hosts and intervening routers establish virtual connectionpRouters get involved4.1 introductionSchool of Computer Science&Technology7 7rNetwork and transport layer service:qNetwork Layer:pbetween two hostsppoint to point.qTransport Layer:pbetween two processespend to end.4.1 introduction2、Network service modelSchool of Computer Science&Technology8 82、Network service model4.1 introductionQ:Whats the service model of the channel connecting the transporting layer in the sending and receiving hosts?qExample services for individual datagrams:Example services for individual datagrams:pguaranteed deliverypGuaranteed delivery with less than 40 msec delayqExample services for a flow of datagrams:Example services for a flow of datagrams:pIn-order datagram deliverypGuaranteed minimum bandwidth to flowpRestrictions on changes in inter-packet spacing(delay jitter)School of Computer Science&Technology9 92、Network service model4.1 introductionNetworkArchitectureInternetATMATMATMATMServiceModelbest effortCBRVBRABRUBRBandwidthnoneconstantrateguaranteedrateguaranteed minimumnoneLossnoyesyesnonoOrdernoyesyesyesyesTimingnoyesyesnonoCongestionfeedbackno(inferredvia loss)nocongestionnocongestionyesnoGuarantees?School of Computer Science&Technology1010roadmaprr4.1 Introduction4.1 Introductionrr4.2 Virtual circuit and datagram networks4.2 Virtual circuit and datagram networksrr4.3 Whats inside a router4.3 Whats inside a routerrr4.4 IP:Internet Protocol4.4 IP:Internet Protocolr4.5 Routing algorithmsqLink state、Distance Vector、Hierarchical routingr4.6 Routing in the InternetqRIP、OSPF、BGPrr4.7 4.7 Broadcast and multicast routingBroadcast and multicast routingrSummarySchool of Computer Science&Technology1212IntroductionrDatagram network provides network-layer connectionless servicerVC network provides network-layer connection servicerAnalogous to the transport-layer services,but:qService:host-to-host(aka.End to End)qNo choice:network provides one or the otherqImplementation:in the network core4 4.2 2 V Vi ir rt tu ua al l c ci ir rc cu ui it t a an nd d d da at ta ag gr ra amm n ne et twwo or rk ks sSchool of Computer Science&Technology13131、Virtual-Circuit Networks4 4.2 2 V Vi ir rt tu ua al l c ci ir rc cu ui it t a an nd d d da at ta ag gr ra amm n ne et twwo or rk ks s“source-to-dest path behaves much likelike telephone circuittelephone circuit”,but there are crucial differences，so called virtual circuit rather than circuit.shared or dedicated resource actions along source-to-dest path Router determines the packets path according to the information in the packet itselfSchool of Computer Science&Technology1414rcall setup for each call before data can flowqteardown the connectionreach packet carries VC identifierVC identifier(not destination host address)reveryevery router on source-dest path maintains“state”for each passing connectionrlink,router resources(bandwidth,buffers)may be allocated allocated to a VC1、Virtual-Circuit Networks4 4.2 2 V Vi ir rt tu ua al l c ci ir rc cu ui it t a an nd d d da at ta ag gr ra amm n ne et twwo or rk ks sSchool of Computer Science&Technology1515VC implementationA VC consists of:1.A pathpath from source to destination2.VC numbers,oneone numbernumber forfor eacheach linklink along path3.3.EntriesEntries in forwarding tables in routers along pathrPackets belonging to a VC carries the VC number.rVC number must be changed on each link.qVC switchingqNew VC number comes from forwarding table4 4.2 2 V Vi ir rt tu ua al l c ci ir rc cu ui it t a an nd d d da at ta ag gr ra amm n ne et twwo or rk ks sSchool of Computer Science&Technology1616Virtual circuits:signaling protocols4 4.2 2 V Vi ir rt tu ua al l c ci ir rc cu ui it t a an nd d d da at ta ag gr ra amm n ne et twwo or rk ks srused to setup,maintain teardown VCrused in ATM,frame-relay,X.25rnot used in todays Internet(packet switching networks)School of Computer Science&Technology17172、Datagram Networks4 4.2 2 V Vi ir rt tu ua al l c ci ir rc cu ui it t a an nd d d da at ta ag gr ra amm n ne et twwo or rk ks srno call setup at network layerrrouters:no state about end-to-end connectionsqno network-level concept of“connection”rpackets forwarded using destination host addressqpackets between same source-dest pair may take different pathsSchool of Computer Science&Technology1818Forwarding table of Datagram Net Destination Address Range output Link Interface 11001000 00010111 00010000 00000000 through 0 11001000 00010111 00010111 11111111 11001000 00010111 00011000 00000000 through 1 11001000 00010111 00011000 11111111 11001000 00010111 00011001 00000000 through 2 11001000 00010111 00011111 11111111 otherwise 3At most,232 possible entries4 4.2 2 V Vi ir rt tu ua al l c ci ir rc cu ui it t a an nd d d da at ta ag gr ra amm n ne et twwo or rk ks sSchool of Computer Science&Technology1919Longest prefix matching4 4.2 2 V Vi ir rt tu ua al l c ci ir rc cu ui it t a an nd d d da at ta ag gr ra amm n ne et twwo or rk ks s Prefix Match Link Interface11001000 00010111 00010 0 11001000 00010111 00011000 111001000 00010111 00011 2 otherwise 3DA:11001000 00010111 00011000 10101010 ExamplesDA:11001000 00010111 00010110 10100001 Which interface?Which interface?School of Computer Science&Technology20203、Datagram or VC network:why?Internetrdata exchange among computersq“elastic”service,no strict timing req.r“smart”“smart”end systems(computers)qcan adapt,perform control,error recoveryqsimple inside network,complexity at“edge”ppEnd2EndEnd2End argumentrmany link types qdifferent characteristicsquniform service difficult4 4.2 2 V Vi ir rt tu ua al l c ci ir rc cu ui it t a an nd d d da at ta ag gr ra amm n ne et twwo or rk ks sSchool of Computer Science&Technology21213、Datagram or VC network:why?ATMrevolved from telephony for human conversationhuman conversationqstrict timing,reliability requirementsqneed for guaranteed servicer“dumb”end systemsqtelephonesqcomplexity inside network4 4.2 2 V Vi ir rt tu ua al l c ci ir rc cu ui it t a an nd d d da at ta ag gr ra amm n ne et twwo or rk ks sSchool of Computer Science&Technology2222roadmaprr4.1 Introduction4.1 Introductionrr4.2 Virtual circuit and datagram networks4.2 Virtual circuit and datagram networksrr4.3 Whats inside a router4.3 Whats inside a routerrr4.4 IP:Internet Protocol4.4 IP:Internet Protocolr4.5 Routing algorithmsqLink state、Distance Vector、Hierarchical routingr4.6 Routing in the InternetqRIP、OSPF、BGPrr4.7 4.7 Broadcast and multicast routingBroadcast and multicast routingrSummarySchool of Computer Science&Technology23234.3 Whats inside a routerrRouter Architecture OverviewqRouter Functions:qRouter ArchitecturerInput Port Functionsrswitching fabricrOutput Ports FunctionsSchool of Computer Science&Technology2424Introductionrouters two key functions:rrun routing algorithms/protocol(RIP,OSPF,BGP)rforwarding datagrams from incoming to outgoing link4.3 Whats inside a routerSchool of Computer Science&Technology2525Introduction-Architecture4.3 Whats inside a routerSchool of Computer Science&Technology26261、Input Port FunctionsPhysical layer:bit-level receptionData link layer:e.g.,EthernetDecentralized switching:rgiven datagram dest.,lookup output port using forwarding tableforwarding table in input port memoryrgoal:complete input port processing at line line speedspeedrrqueuing:queuing:if datagrams arrive faster than forwarding rate into switch fabric4.3 Whats inside a routerSchool of Computer Science&Technology27272、Switching FabricsThree typesThree types of switching fabrics4.3 Whats inside a routerSchool of Computer Science&Technology2828（1）Switching Via Memory4.3 Whats inside a routerInputPortOutputPortMemorySystem BusrFirst generation routers:qqtraditional computerstraditional computers with switching under direct control of CPUqpacket copied to systems memoryqspeed limited by memory bandwidthmemory bandwidth(2 bus crossings per datagram)School of Computer Science&Technology2929（2）Switching Via a Bus4.3 Whats inside a routerSchool of Computer Science&Technology3030Switching Via a Bus4.3 Whats inside a routerrdatagram from input port memory to output port memory via a shared busrbus contention:switching speed limited by bus bandwidthr1 Gbps bus,Cisco 1900:sufficient speed for access and enterprise routers(not regional or backbone)School of Computer Science&Technology3131（3）Switching Via An Interconnection NetworkrGoal:qovercome bus bandwidth limitationsrinterconnection nets initially developed to connect processors in multiprocessorrAdvanced design:fragmenting datagram into fixed length cells,switch cells through the fabric.rCisco 12000:switches Gbps through the interconnection network4.3 Whats inside a routerSchool of Computer Science&Technology3232Switching Via An Interconnection Network4.3 Whats inside a routerSchool of Computer Science&Technology33334、Output Ports4.3 Whats inside a routerrBuffering required when datagrams arrive from fabric faster than the transmission rate of the output linkrScheduling disciplineScheduling discipline chooses among queued datagrams for transmissionSchool of Computer Science&Technology3434Output port queueing4.3 Whats inside a routerrbuffering when arrival rate via switch exceeds output line speedrqueueing(delay)and loss due to output port buffer overflow!School of Computer Science&Technology3535Input Port Queuing4.3 Whats inside a routerSchool of Computer Science&Technology3636Input Port Queuing4.3 Whats inside a routerrfabric slower than input ports combined qqueueing may occur at input queues rHead-of-the-Line(HOL)blocking:queued datagram at front of queue prevents others in queue from moving forwardrqueueing delay and loss due to input buffer overflow!School of Computer Science&Technology3737roadmaprr4.1 Introduction4.1 Introductionrr4.2 Virtual circuit and datagram networks4.2 Virtual circuit and datagram networksrr4.3 Whats inside a router4.3 Whats inside a routerrr4.4 IP:Internet Protocol4.4 IP:Internet Protocolr4.5 Routing algorithmsqLink state、Distance Vector、Hierarchical routingr4.6 Routing in the InternetqRIP、OSPF、BGPrr4.7 4.7 Broadcast and multicast routingBroadcast and multicast routingrSummarySchool of Computer Science&Technology3838The Internet Network layerforwardingtableHost,router network layer functions:Routing protocolspath selectionRIP,OSPF,BGPIP protocoladdressing conventionsdatagram formatpacket handling conventionsICMP protocolerror reportingrouter“signaling”Transport layer:TCP,UDPLink layerphysical layerNetworklayerSchool of Computer Science&Technology39394.4 IP:Internet ProtocolqDatagram formatpIPv4 datagram formatpIP Fragmentation&ReassemblyqIPv4 addressingpIntroductionpSubnetspCIDRpNATqICMPqIPv6School of Computer Science&Technology40401、IPv4 datagram formatverlength32 bitsdata(variable length,typically a TCP or UDP segment)16-bit identifierHeaderchecksumtime tolive32 bit source IP addressIP protocol versionNumber(4-bits)header length(4-byte)(4-bits)upper layer protocolto deliver payload tototal datagramlength(bytes)head.lentype ofservice“type”of data(8bits)flgsfragment offsetforfragmentation/reassemblyProtocolTTL32 bit destination IP addressOptions(if any)E.g.timestamp,record routetaken,specifylist of routers to visit.4.4 IP:Internet ProtocolProtocol=1：ICMP =6：TCP =17：UDPSchool of Computer Science&Technology41414.4 IP:Internet Protocol1、IPv4 datagram formatHow much overhead with TCP?q20 bytes headers of TCP Segmentq20 bytes headers of IP Datagramq=40 bytes+app layer overheadSchool of Computer Science&Technology4242IP Fragmentation&Reassemblyrnetwork links have MTU(max.transfer unit)-largest possible link-level frame.qdifferent link types,different MTUMTUs rlarge IP datagram divided into fragments(“fragmented”)within netqone datagram becomes several datagramsq“reassembled”only at the final destinationqIP header bits used to identify,order related fragments4.4 IP:Internet ProtocolSchool of Computer Science&Technology4343Fragmentation Flagsflags0DFMFReservedDF=0:May Fragment;DF=1:Dont FragmentMF=0:Last Fragment;MF=1:More Fragment4.4 IP:Internet Protocolverlength32 bitsdata(variable length,typically a TCP or UDP segment)16-bit identifierHeaderchecksumtime tolive32 bit source IP addresshead.lentype ofserviceflgsflgsfragment offsetProtocol32 bit destination IP addressOptions(if any)School of Computer Science&Technology4444IP Fragmentation and ReassemblyID=xoffset=0DF=0length=4000offset=0offset=185ID=xID=xID=xoffset=370length=1500length=1500length=1040MF=1MF=1MF=0One large datagram becomesseveral smaller datagramsExampler4000 byte datagramq20+3980rMTU=1500 bytes1480 bytes in data fieldoffset=1480/8 4.4 IP:Internet ProtocolSchool of Computer Science&Technology45452、IPv4 Addressing:IntroductionrIP address:32-bit identifier for interfaces of hosts and routersrdotted decimal notationq4 bytes4.4 IP:Internet ProtocolSchool of Computer Science&Technology4646（1）Introductionrinterface:connection between host/router and physical linkqA router typicallytypically have multiple interfacesqhost maymay have multiple interfacesqIP address associated with eacheach interface223.1.1.1223.1.1.2223.1.1.3223.1.1.4223.1.2.9223.1.2.2223.1.2.1223.1.3.2223.1.3.1223.1.3.274.4 IP:Internet ProtocolSchool of Computer Science&Technology4747Subnets rIP address:IP address:qqsubnetsubnet partpart(high order bits of IP Address)qqhost parthost part(low order bits of IP Address)rWhats a subnet?Whats a subnet?qdevice interfaces with same subnet partsame subnet part of IP address can physically reach each other without intervening router4.4 IP:Internet ProtocolSubnet IDHost IDS