Chapter-4-Network-Layer-addtition-高级计算机网络-教学课件(英文版.ppt

1、addtitionr1,route tabledestination,mask,interface,gatewayinterface and gateway are in the same subnet.192.168.123.0 255.255.255.0 192.168.123.88 192.168.123.88 rroute print;netstat-rQuestion:how to configure pc1 and pc2 so that they can communicate?rRouterAint e0/0rRouterA-Ethernet0/0ip addr 10.1.1.

2、1 24rRouterA-Ethernet0/0int s0rRouterA-Serial0/0ip addr 20.1.1.2 30rRouterBint e0rRouterB-Ethernet0ip addr 30.1.1.1 24rRouterB-Ethernet0int s0rRouterB-Serial0ip addr 20.1.1.1 30rConfigure static routemRouterAip route-static 30.1.1.0 255.255.255.0 20.1.1.1mRouterBip route-static 10.1.1.0 255.255.255.

3、0 20.1.1.2rRouter bdis ip routing-tableDestination/Mask Protocol Pre Cost Nexthop Interfacer10.1.1.0/24 STATIC 60 0 20.1.1.2 Serial0/0r20.1.1.0/30 DIRECT 0 0 20.1.1.1 Serial0/0r20.1.1.1/32 DIRECT 0 0 127.0.0.1 InLoopBack0r20.1.1.2/32 DIRECT 0 0 20.1.1.2 Serial0/0r30.1.1.0/24 DIRECT 0 0 30.1.1.1 Ethe

4、rnet0/0r30.1.1.1/32 DIRECT 0 0 127.0.0.1 InLoopBack0r127.0.0.0/8 DIRECT 0 0 127.0.0.1 InLoopBack0r127.0.0.1/32 DIRECT 0 0 127.0.0.1 InLoopBack0128.30.33.10destinationsubmaskNext hop128.30.33.0128.30.33.128128.30.36.0255.255.255.128255.255.255.128255.255.255.0inter 0Inter 1R2128.30.33.13H1subnet1：net

5、 address 128.30.33.0 mask 255.255.255.128128.30.33.130R1 route tableR11R2Subnet 2：net 128.30.33.128 mask 255.255.255.128H2128.30.33.13801128.30.33.129H3128.30.36.2Subnet 3：net 128.30.36.0 mask 255.255.255.0128.30.36.122,How to route a datagram?128.30.33.10destinationsubmaskNext hop128.30.33.0128.30.

6、33.128128.30.36.0255.255.255.128255.255.255.128255.255.255.0inter 0Inter 1R2128.30.33.13H1 subnet1：net 128.30.33.0 mask 255.255.255.128128.30.33.130R11R2Subnet 2：net 128.30.33.128 mask 255.255.255.128H2128.30.33.13801128.30.33.129H3128.30.36.2子网3：网络地址 128.30.36.0 子网掩码 255.255.255.0128.30.36.12Dest i

7、p:128.30.33.138请注意：H1 并不知道 H2 连接在哪一个网络上。H1 仅仅知道 H2 的 IP 地址是128.30.33.138First:direct delivery?Else:deliver to R1.128.30.33.10目的网络地址子网掩码下一跳128.30.33.0128.30.33.128128.30.36.0255.255.255.128255.255.255.128255.255.255.0接口 0接口 1R2R1 的路由表（未给出默认路由器）H1子网1：网络地址 128.30.33.0 子网掩码 255.255.255.128128.30.33.130R

8、11R2子网2：网络地址 128.30.33.128 子网掩码 255.255.255.128H2128.30.33.13128.30.33.13801128.30.33.129H3128.30.36.2子网3：网络地址 128.30.36.0 子网掩码 255.255.255.0128.30.36.12255.255.255.128 and 128.30.33.138128 10000000138 10001010 :10000000 128255.255.255.128128.30.33.138128.30.33.128 H1 network address128.30.33.10dest

9、masknext128.30.33.0128.30.33.128128.30.36.0255.255.255.128255.255.255.128255.255.255.0inter 0inter 1R2128.30.33.13H1128.30.33.130R11R2H2128.30.33.13801128.30.33.129H3128.30.36.2Subnet 3：net 128.30.36.0 mask 255.255.255.0128.30.36.12 subnet1：net 128.30.33.0 mask 255.255.255.128Subnet 2：net 128.30.33.

10、128 mask 255.255.255.128128.30.33.10destmasknext128.30.33.0128.30.33.128128.30.36.0255.255.255.128255.255.255.128255.255.255.0接口 0接口 1R2128.30.33.13H11：128.30.33.0255.255.255.128128.30.33.130R11R22：128.30.33.128 255.255.255.128H2128.30.33.13801128.30.33.129H3128.30.36.2子网3：网络地址 128.30.36.0 子网掩码 255.

11、255.255.0128.30.36.12255.255.255.128 and 128.30.33.138=128.30.33.128Not match!：128.30.33.138not128.30.33.10destmasknext128.30.33.0128.30.33.128128.30.36.0255.255.255.128255.255.255.128255.255.255.0接口 0接口 1R2128.30.33.13H1128.30.33.130R11R22：128.30.33.128 255.255.255.128H2128.30.33.13801128.30.33.129

12、H3128.30.36.2子网3：网络地址 128.30.36.0 子网掩码 255.255.255.0128.30.36.12255.255.255.128 and 128.30.33.138=128.30.33.128yes!dest IP：128.30.33.138yes!subnet1：net 128.30.33.0 mask 255.255.255.128Static configurationQuidway undo ip route-static ip-address mask|masklen interface-type interface-name|nexthop-addre

13、ss preference value Quidway ip route-static 129.1.0.0 16 10.0.0.2 Quidway ip route-static 129.1.0.0 255.255.0.0 10.0.0.2 Quidway ip route-static 129.1.0.0 16 Serial 2129.1.0.0/16E0Quidway BS010.0.0.2Quidway A10.0.0.1S0在路由器 Quidway A上配置：ip route-static 129.1.0.0 255.255.0.0 10.0.0.2 ip route-static 1

14、29.1.0.0 16 10.0.0.2 ip route-static 129.1.0.0 16 s 0 Default routeQuidway A10.0.0.1S010.0.0.2S0Quidway BPrivate NetworkPublic NetworkQuidway A：ip route-static 0.0.0.0 0 10.0.0.2question3，route algorithmsrThe ideal algorithmsmOptimum simpleness,low cost mRobust/Convergent mapplicability rclassificat

15、ion mStatic vs dynamicsingle path vs multi-pathSingle-layer structure vs Hierarchical structure intra domain vs inter domain domain:AS link state vs distance vector Network Layer4-18Hierarchical Routingscale:with 200 million destinations:rcant store all dests in routing tables!rrouting table exchang

16、e would swamp links!administrative autonomyrinternet=network of networksreach network admin may want to control routing in its own networkOur routing study thus far-idealization rall routers identicalrnetwork“flat”not true in practiceNetwork Layer4-19Hierarchical Routingraggregate routers into regio

17、ns,“autonomous systems”(AS)rrouters in same AS run same routing protocolm“intra-AS”routing protocolmrouters in different AS can run different intra-AS routing protocolGateway routerrDirect link to router in another ASNetwork Layer4-213b1d3a1c2aAS3AS1AS21a2c2b1bIntra-ASRouting algorithmInter-ASRoutin

18、g algorithmForwardingtable3cInterconnected ASesrforwarding table configured by both intra-and inter-AS routing algorithmmintra-AS sets entries for internal destsminter-AS&intra-As sets entries for external dests Network Layer 4-223b1d3a1c2aAS3AS1AS21a2c2b1b3cInter-AS tasksrsuppose router in AS1 rece

19、ives datagram destined outside of AS1:mrouter should forward packet to gateway router,but which one?AS1 must:1.learn which dests are reachable through AS2,which through AS32.propagate this reachability info to all routers in AS1Job of inter-AS routing!Network Layer 4-23Example:Setting forwarding tab

20、le in router 1drsuppose AS1 learns(via inter-AS protocol)that subnet x reachable via AS3(gateway 1c)but not via AS2.rinter-AS protocol propagates reachability info to all internal routers.rrouter 1d determines from intra-AS routing info that its interface I is on the least cost path to 1c.minstalls

21、forwarding table entry(x,I)3b1d3a1c2aAS3AS1AS21a2c2b1b3cxNetwork Layer 4-24Example:Choosing among multiple ASesrnow suppose AS1 learns from inter-AS protocol that subnet x is reachable from AS3 and from AS2.rto configure forwarding table,router 1d must determine towards which gateway it should forwa

22、rd packets for dest x.mthis is also job of inter-AS routing protocol!3b1d3a1c2aAS3AS1AS21a2c2b1b3cxNetwork Layer 4-25Learn from inter-AS protocol that subnet x is reachable via multiple gatewaysUse routing infofrom intra-AS protocol to determinecosts of least-cost paths to eachof the gatewaysHot pot

23、ato routing:Choose the gatewaythat has the smallest least costDetermine fromforwarding table the interface I that leads to least-cost gateway.Enter(x,I)in forwarding tableExample:Choosing among multiple ASesrnow suppose AS1 learns from inter-AS protocol that subnet x is reachable from AS3 and from A

24、S2.rto configure forwarding table,router 1d must determine towards which gateway it should forward packets for dest x.mthis is also job of inter-AS routing protocol!rhot potato routing:send packet towards closest of two routers.rThe standard of route costmThe path length:hop mDelay:the source end to

25、 the destination endmbandwidth:throughout capacity Network Layer 4-27uyxwvz2213112535Graph: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 abstractionRemark:Graph abstraction is useful in other network contextsExample:P2P,where N is set o

26、f peers and E is set of TCP connectionsNetwork Layer 4-28Graph abstraction:costsuyxwvz2213112535 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 congestionCost of path(x1,x2,x3,xp)=c(x1,x2)+c(x2,x3)+c(xp-1,xp)Question:Whats the

27、least-cost path between u and z?Routing algorithm:algorithm that finds least-cost pathNetwork Layer 4-29Routing Algorithm classificationGlobal or decentralized information?Global:rall routers have complete topology,link cost infor“link state”algorithmsDecentralized:rrouter knows physically-connected

28、 neighbors,link costs to neighborsriterative process of computation,exchange of info with neighborsr“distance vector”algorithmsStatic or dynamic?Static:rroutes change slowly over timeDynamic:rroutes change more quicklymperiodic updatemin response to link cost changesNetwork Layer 4-30Chapter 4:Netwo

29、rk Layerr4.1 Introductionr4.2 Virtual circuit and datagram networksr4.3 Whats inside a routerr4.4 IP:Internet ProtocolmDatagram formatmIPv4 addressingmICMPmIPv6r4.5 Routing algorithmsmLink statemDistance Vectorr4.6 Routing in the InternetmRIPmOSPFmBGPr4.7 Broadcast and multicast routingNetwork Layer

30、4-31Chapter 4:Network Layerr4.1 Introductionr4.2 Virtual circuit and datagram networksr4.3 Whats inside a routerr4.4 IP:Internet ProtocolmDatagram formatmIPv4 addressingmICMPmIPv6r4.5 Routing algorithmsmLink statemDistance Vectorr4.6 Routing in the InternetmRIPmOSPFmBGPr4.7 Broadcast and multicast r

31、outingNetwork Layer 4-32Distance Vector Algorithm Bellman-Ford Equation(dynamic programming)Definedx(y):=cost of least-cost path from x to yThendx(y)=min c(x,v)+dv(y)where min is taken over all neighbors v of xvNetwork Layer 4-33Bellman-Ford example uyxwvz2213112535Clearly,dv(z)=5,dx(z)=3,dw(z)=3du(

32、z)=min c(u,v)+dv(z),c(u,x)+dx(z),c(u,w)+dw(z)=min 2+5,1+3,5+3 =4Node that achieves minimum is nexthop in shortest path forwarding tableB-F equation says:Network Layer 4-34Distance Vector Algorithm rDx(y)=estimate of least cost from x to yrNode x knows cost to each neighbor v:c(x,v)rNode x maintains

33、distance vector Dx=Dx(y):y N rNode x also maintains its neighbors distance vectorsmFor each neighbor v,x maintains Dv=Dv(y):y N Network Layer 4-35Distance vector algorithm(4)Basic idea:rFrom time-to-time,each node sends its own distance vector estimate to neighborsrAsynchronousrWhen a node x receive

34、s new DV estimate from neighbor,it updates its own DV using B-F equation:Dx(y)minvc(x,v)+Dv(y)for each node y NrUnder minor,natural conditions,the estimate Dx(y)converge to the actual least cost dx(y)Network Layer 4-36Distance Vector Algorithm(5)Iterative,asynchronous:each local iteration caused by:

35、rlocal link cost change rDV update message from neighborDistributed:reach node notifies neighbors only when its DV changesmneighbors then notify their neighbors if necessarywait for(change in local link cost or msg from neighbor)recompute estimatesif DV to any dest has changed,notify neighbors Each

36、node:距离向量算法部分说明距离向量算法部分说明Network Layer 4-38x y zxyz0 2 7fromcost tofromfromx y zxyz0fromcost tox y zxyz cost tox y zxyz7 10cost to2 0 1 2 0 17 1 0timexz127ynode x tablenode y tablenode z tableDx(y)=minc(x,y)+Dy(y),c(x,z)+Dz(y)=min2+0,7+1=2Dx(z)=minc(x,y)+Dy(z),c(x,z)+Dz(z)=min2+1,7+0=332 Network Lay

37、er 4-39x y zxyz0 2 7fromcost tofromfromx y zxyz0 2 3fromcost tox y zxyz0 2 3fromcost tox y zxyz cost tox y zxyz0 2 7fromcost tox y zxyz0 2 3fromcost tox y zxyz0 2 3fromcost tox y zxyz0 2 7fromcost tox y zxyz7 10cost to2 0 1 2 0 17 1 02 0 17 1 02 0 13 1 02 0 13 1 02 0 13 1 02 0 13 1 0timexz127ynode x

38、 tablenode y tablenode z tableDx(y)=minc(x,y)+Dy(y),c(x,z)+Dz(y)=min2+0,7+1=2Dx(z)=minc(x,y)+Dy(z),c(x,z)+Dz(z)=min2+1,7+0=3Network Layer 4-40Distance Vector:link cost changesLink cost changes:rnode detects local link cost change rupdates routing info,recalculates distance vectorrif DV changes,notif

39、y neighbors“goodnews travelsfast”xz1450y1At time t0,y detects the link-cost change,updates its DV,and informs its neighbors.At time t1,z receives the update from y and updates its table.It computes a new least cost to x and sends its neighbors its DV.At time t2,y receives zs update and updates its d

40、istance table.ys least costs do not change and hence y does not send any message to z.Network Layer4-41Distance Vector:link cost changesLink cost changes:rgood news travels fast rbad news travels slow-“count to infinity”problem!r44 iterations before algorithm stabilizes:see textPoisoned reverse:rIf

41、Z routes through Y to get to X:mZ tells Y its(Zs)distance to X is infinite(so Y wont route to X via Z)rwill this completely solve count to infinity problem?xz1450y60Network Layer 4-42Comparison of LS and DV algorithmsMessage complexityrLS:with n nodes,E links,O(nE)msgs sent rDV:exchange between neig

42、hbors onlymconvergence time variesSpeed of ConvergencerLS:O(n2)algorithm requires O(nE)msgsmmay have oscillationsrDV:convergence time variesmmay be routing loopsmcount-to-infinity problemRobustness:what happens if router malfunctions?LS:mnode can advertise incorrect link costmeach node computes only

43、 its own tableDV:mDV node can advertise incorrect path costmeach nodes table used by others error propagate thru networkNetwork Layer 4-43Chapter 4:Network Layerr4.1 Introductionr4.2 Virtual circuit and datagram networksr4.3 Whats inside a routerr4.4 IP:Internet ProtocolmDatagram formatmIPv4 address

44、ingmICMPmIPv6r4.5 Routing algorithmsmLink statemDistance Vectorr4.6 Routing in the InternetmRIPmOSPFmBGPr4.7 Broadcast and multicast routingNetwork Layer 4-44Chapter 4:Network Layerr4.1 Introductionr4.2 Virtual circuit and datagram networksr4.3 Whats inside a routerr4.4 IP:Internet ProtocolmDatagram

45、 formatmIPv4 addressingmICMPmIPv6r4.5 Routing algorithmsmLink statemDistance Vectorr4.6 Routing in the InternetmRIPmOSPFmBGPr4.7 Broadcast and multicast routingNetwork Layer 4-45Intra-AS Routingralso known as Interior Gateway Protocols(IGP)rmost common Intra-AS routing protocols:mRIP:Routing Informa

46、tion ProtocolmOSPF:Open Shortest Path FirstmIGRP:Interior Gateway Routing Protocol(Cisco proprietary)R1H1H2IGP（RIP）AS:AAS:BAS:CIGPIGPIGPIGPIGPIGPIGPIGPIGPIGPIGPIGPEGPEGPEGPIGP（OSPF）EGP（BGP-4）IGPR3R2Network Layer 4-47Chapter 4:Network Layerr4.1 Introductionr4.2 Virtual circuit and datagram networksr4

47、.3 Whats inside a routerr4.4 IP:Internet ProtocolmDatagram formatmIPv4 addressingmICMPmIPv6r4.5 Routing algorithmsmLink statemDistance VectormHierarchical routingr4.6 Routing in the InternetmRIPmOSPFmBGPr4.7 Broadcast and multicast routingNetwork Layer 4-48RIP(Routing Information Protocol)rdistance

48、vector algorithmrincluded in BSD-UNIX Distribution in 1982rdistance metric:#of hops(max=15 hops)DCBAuvwxyzdestination hops u 1 v 2 w 2 x 3 y 3 z 2 From router A to subnets:Network Layer 4-49RIP advertisementsrdistance vectors:exchanged among neighbors every 30 sec via Response Message(also called ad

49、vertisement)reach advertisement:list of up to 25 destination subnets within ASNetwork Layer 4-50RIP:Example Destination Network Next Router Num.of hops to dest.wA2yB2 zB7x-1.wxyzACDBRouting/Forwarding table in DNetwork Layer4-51RIP:Example Destination Network Next Router Num.of hops to dest.wA2yB2 z

50、B A7 5x-1.Routing/Forwarding table in DwxyzACDB Dest Next hops w -1 x -1 z C 4 .Advertisementfrom A to DUpdate polices:r1，if the destination does not exit,this entry will be added.r2，if the dest is the same and the cost c is less than the old cost 1,the entry will be change.The cost will be c+1.r3，i