《Internet网络层协议设计.ppt》由会员分享，可在线阅读，更多相关《Internet网络层协议设计.ppt（233页珍藏版）》请在三一办公上搜索。
1、Internet网络层协议设计,清华大学计算机系,2,提纲,网络层服务网络路由基本原理层次化路由体系结构IP协议简介Internet路由协议intra-domain:RIP,OSPFinter-domain:BGP新一代互联网路由寻址体系结构,3,提纲,网络层服务网络路由基本原理层次化路由体系结构IP协议简介Internet路由协议intra-domain:RIP,OSPFinter-domain:BGP新一代互联网路由寻址体系结构,4,Best Effort Connectivity,This is the fundamental service provided by Internet S
2、ervice Providers(ISPs),All other IP services depend on connectivity:DNS,email,VPNs,Web Hosting,IP traffic,135.207.49.8,192.0.2.153,5,Network layer functions,transport packet from sending to receiving hosts network layer protocols in every host,routerthree important functions:path determination:route
3、 taken by packets from source to dest.Routing algorithmsforwarding:move packets from routers input to appropriate router outputcall setup:some network architectures require router call setup along path before data flows,6,R,R,R,A,B,C,D,R1,R2,R3,R4,R5,E,Net,Nxt Hop,R4R3R3R4DirectR4,Net,Nxt Hop,A B C
4、D Edefault,R2R2DirectR5R5R2,Net,Nxt Hop,A B C D Edefault,R1DirectR3R1R3R1,Default toupstreamrouter,A B C D Edefault,Forwarding:determine next hopRouting:find end-to-end paths,Routing and Forwarding,7,Network service model,Q:What service model for“channel”transporting packets from sender to receiver?
5、guaranteed bandwidth?preservation of inter-packet timing(no jitter)?loss-free delivery?in-order delivery?congestion feedback to sender?,?,?,?,virtual circuitor datagram?,The most important abstraction provided by network layer:,service abstraction,8,Virtual circuits,call setup for each call before d
6、ata can floweach packet carries VC identifier(not destination host ID)every router on source-dest path maintains“state”for each passing connectionlink,router resources(bandwidth,buffers)may be allocated to VC,“source-to-dest path behaves much like telephone circuit”performance-wisenetwork actions al
7、ong source-to-dest path,9,Virtual circuits:signaling protocols,used to setup,maintain,teardown VCused in ATM,frame-relay,X.25not used in todays Internet,1.Initiate call,2.incoming call,3.Accept call,4.Call connected,5.Data flow begins,6.Receive data,10,Datagram networks:the Internet model,no call se
8、tup at network layerrouters:no state about end-to-end connectionspackets forwarded using destination host address,1.Send data,2.Receive data,11,Network layer service models,NetworkArchitectureInternetATMATMATMATM,ServiceModelbest effortCBRVBRABRUBR,Bandwidthnoneconstantrateguaranteedrateguaranteed m
9、inimumnone,Lossnoyesyesnono,Ordernoyesyesyesyes,Timingnoyesyesnono,Congestionfeedbackno(inferredvia loss)nocongestionnocongestionyesno,Guarantees?,Internet model being extended:Intserv,Diffserv,12,Datagram or VC network:why?,Internetdata exchange among computers“elastic”service,no strict timing req.
10、“smart”end systems(computers)can adapt,perform control,error recoverysimple inside network,complexity at“edge”many link types different characteristicsuniform service difficult,ATMevolved from telephonyhuman conversation:strict timing,reliability requirementsneed for guaranteed service“dumb”end syst
11、emstelephonescomplexity inside network,13,提纲,网络层服务网络路由基本原理层次化路由体系结构IP协议简介Internet路由协议intra-domain:RIP,OSPFinter-domain:BGP新一代互联网路由寻址体系结构,14,Before We Go Any Further,Usually,IP ROUTING PROTOCOLS DO NOT DYNAMICALLY ROUTE AROUND NETWORK CONGESTION,IP traffic can be very bursty Dynamic adjustments in ro
12、uting typically operate more slowly than fluctuations in traffic loadDynamically adapting routing to account for traffic load can lead to wild,unstable oscillations of routing system,15,Before We Go Any Further,Anindya Basu,Alvin Lin,Sharad Ramanathan.Routing Using Potentials:A Dynamic Traffic-Aware
13、 Routing Algorithm.Proceedings of Sigcomm2003The routing algorithm routes around congested areas while preserving the key desirable properties of IP routing mechanisms including hop-by-hop routing,local route computations and statistical multiplexing,16,Routing,Graph abstraction for routing algorith
14、ms:graph nodes are routersgraph edges are physical linkslink cost:delay,$cost,or congestion level,Goal:determine“good”path(sequence of routers)thru network from source to dest.,“good”path:typically means minimum cost pathother defs possible,17,Routing Algorithm Classification,Global or decentralized
15、 information?Global:all routers have complete topology,link cost info“link state”algorithmsDecentralized:router knows physically-connected neighbors,link costs to neighborsiterative process of computation,exchange of info with neighbors“distance vector”algorithms,18,Routing Algorithm Classification,
16、Static or dynamic?Static:routes change slowly over timeDynamic:routes change more quicklyperiodic updatein response to link cost changes,19,A Link-State Routing Algorithm,Dijkstras algorithmnet topology,link costs known to all nodesaccomplished via“link state broadcast”all nodes have same infocomput
17、es least cost paths from one node(“source”)to all other nodesgives routing table for that nodeiterative:after k iterations,know least cost path to k destinations,Idea:at each iteration increase spanning tree by the node that has least cost path to it,20,A Link-State Routing Algorithm,Notation:c(i,j)
18、:link cost from node i to j.cost infinite if not direct neighborsD(v):current value of cost of path from source to dest.V p(v):predecessor node along path from source to v,that is next vN:set of nodes already in spanning tree(least cost path known),Examples:c(B,C)=3D(E)=2p(B)=AN=A,B,D,E,21,Dijsktras
19、 Algorithm,1 Initialization:2 N=A 3 for all nodes v 4 if v adjacent to A 5 then D(v)=c(A,v)6 else D(v)=infinity 7 8 Loop 9 find w not in N such that D(w)is a minimum 10 add w to N 11 update D(v)for all v adjacent to w and not in N:12 D(v)=min(D(v),D(w)+c(w,v)13/*new cost to v is either old cost to v
20、 or known 14 shortest path cost to w plus cost from w to v*/15 until all nodes in N,22,Dijkstras algorithm:example,Step012345,N,D(B),p(B),D(C),p(C),D(D),p(D),D(E),p(E),D(F),p(F),2,2,1,3,1,1,2,5,3,5,23,Spanning tree gives routing table,BCDEF,B,2D,3D,1D,2D,4,Outgoing link to use,cost,destination,Resul
21、t from Dijkstras algorithm,Routing table:,Step,N,D(B),p(B),D(C),p(C),D(D),p(D),D(E),p(E),D(F),p(F),2,2,1,3,1,1,2,5,3,5,24,Dijkstras algorithm performance,Algorithm complexity(n nodes and l links)Computationn iterationseach iteration:need to check all nodes,w,not in Nn*(n+1)/2 comparisons:O(n2)more e
22、fficient implementations possible:O(n log n)Messagesnetwork topology and link cost known to all nodeseach node broadcasts its direct link costO(l)messages per broadcast announcementO(n l),25,Dijkstras algorithm discussion,Oscillations are possibledynamic link coste.g.,link cost=amount of carried tra
23、ffic by linkc(i,j)!=c(j,i)Example:,1,1+e,e,0,e,1,1,0,0,2+e,0,0,0,1+e,1,0,2+e,1+e,1,0,0,2+e,0,e,0,1+e,1,initially,recomputerouting,recompute,recompute,e,1,1,e,1,1,e,1,1,26,Distance Vector Routing Algorithm,iterative:continues until no nodes exchange infoself-terminating:no“signal”to stopasynchronous:
24、nodes need not exchange info/iterate in lock step!distributed:each node communicates only with directly-attached neighbors,Distance Table data structure each node has its ownrow for each possible destinationcolumn for each directly-attached neighbor to nodeexample:in node X,for dest.Y via neighbor Z
25、:,27,Distance Table:example,7,8,1,2,1,2,loop!,loop!,28,Distance table gives routing table,E ABCD,A,1D,5D,4D,2,Outgoing link to use,cost,destination,Distance table,Routing table,29,Distance Vector Routing:overview,Iterative,asynchronous:each local iteration triggered by:local link cost change message
26、 from neighbor:its least cost path change from neighborDistributed:each node notifies neighbors only when its least cost path to any destination changesneighbors then notify their neighbors if necessary,Each node:,30,Distance Vector Algorithm:,1 Initialization:2 for all adjacent nodes v:3 D(*,v)=inf
27、inity/*the*operator means for all rows*/4 D(v,v)=c(X,v)5 for all destinations,y 6 send min D(y,w)to each neighbor/*w over all Xs neighbors*/,X,X,X,w,At all nodes,X:,31,Distance Vector Algorithm(cont.):,8 loop 9 wait(until I see a link cost change to neighbor V 10 or until I receive update from neigh
28、bor V)11 if(c(X,V)changes by d)13/*change cost to all dests via neighbor v by d*/14/*note:d could be positive or negative*/15 for all destinations y:D(y,V)=D(y,V)+d 16 17 else if(update received from V wrt destination Y)18/*shortest path from V to some Y has changed*/19/*V has sent a new value for i
29、ts min DV(Y,w)*/20/*call this received new value is newval*/21 for the single destination y:D(Y,V)=c(X,V)+newval 22 23 if we have a new min D(Y,w)for any destination Y 24 send new value of min D(Y,w)to all neighbors 25 forever,w,X,X,X,X,X,w,w,32,Distance Vector Algorithm:example,33,Distance Vector A
30、lgorithm:example,34,Distance Vector:link cost changes,Link cost changes:node detects local link cost change updates distance table(line 15)if cost change in least cost path,notify neighbors(lines 23,24),1,4,50,1,algorithmterminates,“goodnews travelsfast”,35,Distance Vector:link cost changes,Link cos
31、t changes:good news travels fast bad news travels slow-“count to infinity”problem!,1,4,50,60,algorithmcontinueson!,36,Distance Vector:poisoned reverse,If Z routes through Y to get to X:Z tells Y its(Zs)distance to X is infinite(so Y wont route to X via Z)will this completely solve count to infinity
32、problem?,algorithmterminates,1,4,50,60,37,Comparison of LS and DV algorithms,Message complexityLS:with n nodes,E links,O(nE)msgs sent each DV:exchange between neighbors onlyconvergence time variesSpeed of ConvergenceLS:O(n2)algorithm requires O(nE)msgsmay have oscillationsDV:convergence time variesm
33、ay be routing loopscount-to-infinity problem,38,Comparison of LS and DV algorithms,Robustness:what happens if router malfunctions?LS:node can advertise incorrect link costeach node computes only its own tableDV:DV node can advertise incorrect path costeach nodes table used by others error propagate
34、thru network,39,提纲,网络层服务网络路由基本原理层次化路由体系结构IP协议简介Internet路由协议intra-domain:RIP,OSPFinter-domain:BGP新一代互联网路由寻址体系结构,40,Hierarchical Routing,Our routing study thus far-idealization all routers identicalnetwork“flat”not true in practice,41,Hierarchical Routing,scale:with 500 million destinationscant store
35、all dests in routing tables!routing table exchange would swamp links!,administrative autonomyinternet=network of networkseach network admin may want to control routing in its own network,42,Hierarchical Routing,aggregate routers into regions,“autonomous systems”(AS)routers in same AS run same routin
36、g protocol“intra-AS”routing protocolrouters in different AS can run different intra-AS routing protocol,special routers in ASrun intra-AS routing protocol with all other routers in ASalso responsible for routing to destinations outside ASrun inter-AS routing protocol with other gateway routers,43,In
37、tra-AS and Inter-AS routing,Gateways:perform inter-AS routing amongst themselvesperform intra-AS routers with other routers in their AS,inter-AS,intra-AS routing in gateway A.c,network layer,link layer,physical layer,a,b,a,C,A,B,d,44,Intra-AS and Inter-AS routing,Host h2,Hosth1,Intra-AS routingwithi
38、n AS A,Intra-AS routingwithin AS B,Well examine specific inter-AS and intra-AS Internet routing protocols shortly,45,提纲,网络层服务网络路由基本原理层次化路由体系结构IP协议简介Internet路由协议intra-domain:RIP,OSPFinter-domain:BGP新一代互联网路由寻址体系结构,46,The Internet Network layer,Host,router network layer functions:,Transport layer:TCP,U
39、DP,Link layer,physical layer,Networklayer,47,IP datagram format,ver,length,32 bits,data(variable length,typically a TCP or UDP segment),16-bit identifier,Internet checksum,time tolive,32 bit source IP address,IP protocol versionnumber,header length(bytes),max numberremaining hops(decremented at each
40、 router),forfragmentation/reassembly,total datagramlength(bytes),upper layer protocolto deliver payload to,head.len,type ofservice,“type”of data,flgs,fragment offset,upper layer,32 bit destination IP address,Options(if any),E.g.timestamp,record routetaken,specifylist of routers to visit.,how much ov
41、erhead with TCP?20 bytes of TCP20 bytes of IP=40 bytes+app layer overhead,48,IP Fragmentation&Reassembly,network links have MTU(max.transfer size)largest possible link-level framedifferent link types,different MTUs large IP datagram divided(“fragmented”)within netone datagram becomes several datagra
42、ms“reassembled”only at final destinationIP header bits used to identify,order related fragments,fragmentation:in:one large datagramout:3 smaller datagrams,reassembly,49,IP Fragmentation and Reassembly,Example4000 byte datagramMTU=1500 bytes,50,ICMP:Internet Control Message Protocol,used by hosts,rou
43、ters,gateways to communication network-level informationerror reporting:unreachable host,network,port,protocolecho request/reply(used by ping)network-layer“above”IP:ICMP msgs carried in IP datagramsICMP message:type,code plus first 8 bytes of IP datagram causing error,Type Code description0 0 echo r
44、eply(ping)3 0 dest network unreachable3 1 dest host unreachable3 2 dest protocol unreachable3 3 dest port unreachable3 6 dest network unknown3 7 dest host unknown4 0 source quench(congestion control-not used)8 0 echo request(ping)9 0 route advertisement10 0 router discovery11 0 TTL expired12 0 bad I
45、P header,51,DHCP:Dynamic Host Configuration Protocol,Goal:(1)allow host to dynamically obtain its IP address from network server when it joins network(2)Can renew its lease on address in use(3)allows reuse of addresses(only hold address while connected an“on”)(4)support for mobile users who want to
46、join networkDHCP overview:host broadcasts“DHCP discover”msgDHCP server responds with“DHCP offer”msghost requests IP address:“DHCP request”msgDHCP server sends address:“DHCP ack”msg,52,DHCP client-server scenario,53,DHCP client-server scenario,DHCP server:223.1.2.5,Arriving client,time,DHCP offer,src
47、:223.1.2.5,67 dest:255.255.255.255,68yiaddrr:223.1.2.4transaction ID:654Lifetime:3600 secs,DHCP request,src:0.0.0.0,68 dest:255.255.255.255,67yiaddrr:223.1.2.4transaction ID:655Lifetime:3600 secs,DHCP ACK,src:223.1.2.5,67 dest:255.255.255.255,68yiaddrr:223.1.2.4transaction ID:655Lifetime:3600 secs,5
48、4,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 ofInternet,Datagrams with source or destination in this networkhave 10.0.0/24 address for source,destination(as usual),All datagrams leaving localnetwork have same single
49、source NAT IP address:138.76.29.7,different source port numbers,55,NAT:Network Address Translation,Motivation:local network uses just one IP address as far as outside world is concerned:no need to be allocated range of addresses from ISP:-just one IP address is used for all devicescan change address
50、es of devices in local network without notifying outside worldcan change ISP without changing addresses of devices in local networkdevices inside local net not explicitly addressable,visible by outside world(a security plus),56,NAT:Network Address Translation,Implementation:NAT box must:outgoing dat
