资源描述
Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,Network Layer,4-,*,Chapter 4Network Layer,Computer Networking:A Top Down Approach Featuring the Internet,3,rd,edition.Jim Kurose,Keith RossAddison-Wesley,July 2004.,Based on the slides by,Jim Kurose and Keith Ross,1,Network Layer,Chapter 4:Network Layer,Chapter goals:,understand principles behind network layer services:,network layer service models,forwarding versus routing,how a router works,routing(path selection),dealing with scale,advanced topics:IPv6,mobility,instantiation,implementation in the Internet,2,Network Layer,Chapter 4:Network Layer,4.1 Introduction,4.2 Virtual circuit and datagram networks,4.3 Whats inside a router,4.4 IP:Internet Protocol,Datagram format,IPv4 addressing,ICMP,IPv6,4.5 Routing algorithms,Link state,Distance Vector,Hierarchical routing,4.6 Routing in the Internet,RIP,OSPF,BGP,4.7 Broadcast and multicast routing,3,Network Layer,1,2,3,0111,value in arriving,packets header,routing algorithm,local forwarding table,header value,output link,0100,0101,0111,1001,3,2,2,1,Interplay between routing and forwarding,4,Network Layer,Connection setup,3,rd,important function in,some,network architectures:,ATM,frame relay,X.25,before datagrams flow,two end hosts,and,intervening routers establish virtual connection,routers get involved,network,vs,transport layer connection service:,network:,between two hosts(may also involve,inervening,routers in case of VCs),transport:,between two processes,5,Network Layer,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,6,Network Layer,Chapter 4:Network Layer,4.1 Introduction,4.2 Virtual circuit and datagram networks,4.3 Whats inside a router,4.4 IP:Internet Protocol,Datagram format,IPv4 addressing,ICMP,IPv6,4.5 Routing algorithms,Link state,Distance Vector,Hierarchical routing,4.6 Routing in the Internet,RIP,OSPF,BGP,4.7 Broadcast and multicast routing,7,Network Layer,Network layer connection and connection-less service,datagram network provides network-layer connectionless service,VC network provides network-layer connection service,analogous to the transport-layer services,but:,service:,host-to-host,no choice:,network provides one or the other,implementation:,in network core,8,Network Layer,Virtual circuits,call setup,teardown for each call,before,data can flow,each packet carries VC identifier(not destination host address),every,router on source-dest path maintains“state”for each passing connection,link,router resources(bandwidth,buffers)may be,allocated,to VC(dedicated resources=predictable service),“,source-to-dest path behaves much like telephone circuit”,performance-wise,network actions along source-to-dest path,9,Network Layer,VC implementation,a VC consists of:,path from source to destination,VC numbers,one number for each link along path,entries in forwarding tables in routers along path,packet belonging to VC carries VC number(rather than,dest,address),VC number can be changed on each link.,New VC number comes from forwarding table,10,Network Layer,Forwarding table,12,22,32,1,2,3,VC number,interface,number,Incoming interface Incoming VC#Outgoing interface Outgoing VC#,1 12 3 22,2 63 1 18,3 7 2 17,1 97 3 87,Forwarding table in,northwest router:,Routers maintain connection state information!,11,Network Layer,Virtual circuits:signaling protocols,used to setup,maintain teardown VC,used in ATM,frame-relay,X.25,not used in todays Internet,application,transport,network,data link,physical,application,transport,network,data link,physical,1.Initiate call,2.incoming call,3.Accept call,4.Call connected,5.Data flow begins,6.Receive data,12,Network Layer,Datagram networks,no call setup at network layer,routers:no state about end-to-end connections,no network-level concept of“connection”,packets forwarded using destination host address,packets between same source-dest pair may take different paths,application,transport,network,data link,physical,application,transport,network,data link,physical,1.Send data,2.Receive data,13,Network Layer,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 00011001 00000000,through 2,11001000 00010111 00011111 11111111,otherwise 3,4 billion,possible entries,14,Network Layer,Longest prefix matching,Prefix Match,Link Interface,11001000 00010111 00010 0,11001000 00010111 00011000 1,11001000 00010111 00011 2,otherwise 3,DA:11001000 00010111 00011000 10101010,Examples,DA:11001000 00010111 00010110 10100001,Which interface?,Which interface?,15,Network Layer,Datagram or VC network:why?,Internet(datagram),data exchange among computers,“elastic”service,no strict timing req.,“smart”end systems(computers),can adapt,perform control,error recovery,simple inside network,complexity at“edge”,many link types,different characteristics,uniform service difficult,ATM(VC),evolved from telephony,human conversation:,strict timing,reliability requirements,need for guaranteed service,“dumb”end systems,telephones,complexity inside network,16,Network Layer,Chapter 4:Network Layer,4.1 Introduction,4.2 Virtual circuit and datagram networks,4.3 Whats inside a router,4.4 IP:Internet Protocol,Datagram format,IPv4 addressing,ICMP,IPv6,4.5 Routing algorithms,Link state,Distance Vector,Hierarchical routing,4.6 Routing in the Internet,RIP,OSPF,BGP,4.7 Broadcast and multicast routing,17,Network Layer,Chapter 4:Network Layer,4.1 Introduction,4.2 Virtual circuit and datagram networks,4.3 Whats inside a router,4.4 IP:Internet Protocol,Datagram format,IPv4 addressing,ICMP,IPv6,4.5 Routing algorithms,Link state,Distance Vector,Hierarchical routing,4.6 Routing in the Internet,RIP,OSPF,BGP,4.7 Broadcast and multicast routing,18,Network Layer,IP datagram format,ver,length,32 bits,data,(variable length,typically a TCP,or UDP segment),16-bit identifier,header,checksum,time to,live,32 bit source IP address,IP protocol version,number,header length,(bytes),max number,remaining hops,(decremented at,each router),for,fragmentation/,reassembly,total datagram,length(bytes),upper layer protocol,to deliver payload to,head.,len,type of,service,“,type”of data,flgs,fragment,offset,upper,layer,32 bit destination IP address,Options(if any),E.g.timestamp,record route,taken,specify,list of routers,to visit.,how much overhead with TCP?,20 bytes of TCP,20 bytes of IP,=40 bytes+app layer overhead,19,Network Layer,Chapter 4:Network Layer,4.1 Introduction,4.2 Virtual circuit and datagram networks,4.3 Whats inside a router,4.4 IP:Internet Protocol,Datagram format,IPv4 addressing,ICMP,IPv6,4.5 Routing algorithms,Link state,Distance Vector,Hierarchical routing,4.6 Routing in the Internet,RIP,OSPF,BGP,4.7 Broadcast and multicast routing,20,Network Layer,IP Addressing:introduction,IP address:,32-bit identifier for host,router,interface,interface:,connection between host/router and physical link,routers typically have multiple interfaces,host typically has one interface,IP addresses associated with each interface,223.1.1.1,223.1.1.2,223.1.1.3,223.1.1.4,223.1.2.9,223.1.2.2,223.1.2.1,223.1.3.2,223.1.3.1,223.1.3.27,223.1.1.1=11011111 00000001 00000001 00000001,223,1,1,1,21,Network Layer,Subnets,IP address:,subnet part(high order bits),host part(low order bits),Whats a subnet?,device interfaces with same subnet part of IP address,can physically reach each other without intervening router,223.1.1.1,223.1.1.2,223.1.1.3,223.1.1.4,223.1.2.9,223.1.2.2,223.1.2.1,223.1.3.2,223.1.3.1,223.1.3.27,network consisting of 3 subnets,subnet,22,Network Layer,Subnets,223.1.1.0/24,223.1.2.0/24,223.1.3.0/24,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,.,Subnet mask:/24,23,Network Layer,Subnets,How many?,223.1.1.1,223.1.1.3,223.1.1.4,223.1.2.2,223.1.2.1,223.1.2.6,223.1.3.2,223.1.3.1,223.1.3.27,223.1.1.2,223.1.7.0,223.1.7.1,223.1.8.0,223.1.8.1,223.1.9.1,223.1.9.2,24,Network Layer,IP addressing:CIDR,CIDR:,C,lassless,I,nter,D,omain,R,outing,subnet portion of address of arbitrary length,address format:,a.b.c.d/x,where x is#bits in subnet portion of address,11001000 00010111,0001000,0 00000000,subnet,part,host,part,200.23.16.0/23,25,Network Layer,IP addresses:how to get one?,Q:,How does,host,get IP address?,hard-coded by system admin in a file,Wintel:control-panel-network-configuration-tcp/ip-properties,UNIX:/etc/rc.config,DHCP:,D,ynamic,H,ost,C,onfiguration,P,rotocol:dynamically get address from as server,“plug-and-play”,(more in next chapter),26,Network Layer,IP addresses:how to get one?,Q:,How does,network,get subnet part of IP addr?,A:,gets allocated portion of its provider ISPs address space,ISPs block,11001000 00010111 0001,0000 00000000 200.23.16.0/20,Organization 0,11001000 00010111 0001000,0 00000000 200.23.16.0/23,Organization 1,11001000 00010111 0001001,0 00000000 200.23.18.0/23,Organization 2,11001000 00010111 0001010,0 00000000 200.23.20.0/23,.,Organization 7,11001000 00010111 0001111,0 00000000 200.23.30.0/23,27,Network Layer,Hierarchical addressing:route aggregation,“,Send me anything,with addresses,beginning,200.23.16.0/20”,200.23.16.0/23,200.23.18.0/23,200.23.30.0/23,Fly-By-Night-ISP,Organization 0,Organization 7,Internet,Organization 1,ISPs-R-Us,“,Send me anything,with addresses,beginning,199.31.0.0/16”,200.23.20.0/23,Organization 2,.,.,.,.,.,.,Hierarchical addressing allows efficient advertisement of routing,information:,28,Network Layer,Hierarchical addressing:more specific routes,ISPs-R-Us has a more specific route to Organization 1,“,Send me anything,with addresses,beginning,200.23.16.0/20”,200.23.16.0/23,200.23.18.0/23,200.23.30.0/23,Fly-By-Night-ISP,Organization 0,Organization 7,Internet,Organization 1,ISPs-R-Us,“,Send me anything,with addresses,beginning 199.31.0.0/16,or 200.23.18.0/23”,200.23.20.0/23,Organization 2,.,.,.,.,.,.,29,Network Layer,IP addressing:the last word.,Q:,How does an ISP get block of addresses?,A:,ICANN,:,I,nternet,C,orporation for,A,ssigned,N,ames and,N,umbers,allocates addresses,manages DNS,assigns domain names,resolves disputes,30,Network Layer,NAT:Network Address Translation,10.0.0.1,10.0.0.2,10.0.0.3,10.0.0.4,138.76.29.7,local network,(e.g.,home network),10.0.0/24,rest of,Internet,Datagrams with source or,destination in this network,have 10.0.0/24 address for,source,destination(as usual),All,datagrams,leaving,local,network have,same,single source NAT IP address:138.76.29.7,different source port numbers,31,Network Layer,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).,32,Network Layer,NAT:Network Address Translation,Implementation:,NAT router must:,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 addr.,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 dest fields of every incoming datagram with corresponding(source IP address,port#)stored in NAT table,33,Network Layer,NAT:Network Address Translation,10.0.0.1,10.0.0.2,10.0.0.3,S:10.0.0.1,3345,D:128.119.40.186,80,1,10.0.0.4,138.76.29.7,1:,host 10.0.0.1,sends datagram to,128.119.40.186,80,NAT translation table,WAN side addr LAN side addr,138.76.29.7,5001 10.0.0.1,3345,S:128.119.40.186,80,D:10.0.0.1,3345,4,S:138.76.29.7,5001,D:128.119.40.186,80,2,2:,NAT router,changes datagram,source addr from,10.0.0.1,3345 to,138.76.29.7,5001,updates table,S:128.119.40.186,80,D:138.76.29.7,5001,3,3:,Reply arrives,dest.address:,138.76.29.7,5001,4:,NAT router,changes datagram,dest addr from,138.76.29.7,5001 to 10.0.0.1,3345,34,Network Layer,NAT:Network Address Translation,16-bit port-number field:,60,000 simultaneous connections with a single LAN-side address!,NAT is controversial:,routers should only process up to layer 3,violates end-to-end argument,NAT possibility must be taken into account by app designers,eg,P2P applications,address shortage should instead be solved by IPv6,35,Network Layer,Chapter 4:Network Layer,4.1 Introduction,4.2 Virtual circuit and datagram networks,4.3 Whats inside a router,4.4 IP:Internet Protocol,Datagram format,IPv4 addressing,ICMP,IPv6,4.5,Routing algorithms,Link state,Distance Vector,Hierarchical routing,4.6 Routing in the Internet,RIP,OSPF,BGP,4.7 Broadcast and multicast routing,36,Network Layer,1,2,3,0111,value in arriving,packets header,routing algorithm,local forwarding table,header value,output link,0100,0101,0111,1001,3,2,2,1,Interplay between routing,forwarding,37,Network Layer,u,y,x,w,v,z,2,2,1,3,1,1,2,5,3,5,Graph:G=(N,E),N=set of routers=u,v,w,x,y,z,E=set of links=(,u,v,),(,u,x,),(,v,x,),(,v,w,),(,x,w,),(,x,y,),(,w,y,),(,w,z,),(,y,z,),Graph abstraction,Remark:Graph abstraction is useful in other network contexts,Example:P2P,where N is set of peers and E is set of TCP connections,38,Network Layer,Graph abstraction:costs,u,y,x,w,v,z,2,2,1,3,1,1,2,5,3,5,c(x,x,)=cost of link(,x,x,),-e.g.,c(w,z,)=5,cost could always be 1,or,inversely related to bandwidth,or inversely related to,congestion,Cost of path(x,1,x,2,x,3,x,p,)=c(x,1,x,2,)+c(x,2,x,3,)+c(x,p-1,x,p,),Question:Whats the least-cost path between u and z?,Routing algorithm:algorithm that finds least-cost path,39,Network Layer,Routing Algorithm classification,Global or decentralized information?,Global:,all routers have complete topology,link cost info,“link state”algorithms,Decentralized:,router knows physically-connected neighbors,link costs to neighbors,iterative process of computation,exchange of info with neighbors,“distance vector”algorithms,Static or dynamic?,Static:,routes change slowly over time,Dynamic:,routes change more quickly,periodic update,in response to link cost changes,40,Network Layer,Chapter 4:Network Layer,4.1 Introduction,4.2 Virtual circuit and datagram networks,4.3 Whats inside a router,4.4 IP:Internet Protocol,Datagram format,IPv4 addressing,ICMP,IPv6,4.5 Routing algorithms,Link state,Distance Vector,Hierarchical routing,4.6 Routing in the Internet,RIP,OSPF,BGP,4.7 Broadcast and mult
展开阅读全文