《网路层通讯协定》PPT课件

第四章網路層通訊協定,NetworkLayerProtocols,ProtocolStack,PhysicalLayer,NetworkLayer,DataLinkLayer,TransportLayer,ApplicationLayer,網路層的特色,底層可以連結數種不同介質的網路。底層不同的網路介質可以透過網路層傳輸協定互相連結。Internet的主要定址層網路層的位址(Address)為階層式(Hierarchical)定義，鄰近的節點往往具有相似的網路層位址prefix。可以依照網路層位址找到節點的所在位置。鏈結層(DataLinkLayer)的位址為平面式(flat)，位址與實際的地域位置(Location)大多無相關。無法依照鏈結層位址找到節點所在的位置。,網路層的主要功能,Routing:決定封包(packet)適當的傳輸路徑。RoutingAlgorithms:計算傳輸路徑的演算法。Switching:將封包轉送至適當的出口埠。CallSetup:在傳送資料前建立整條傳輸路徑。協助通訊的兩端在資料(DataFlow)真正開始傳送之前建立連線(example:TCP3-wayhandshaking,ATM)。,ServiceModel,ServiceModel:描述傳送端與接收端之間資料傳輸的特性，如:封包是否照著傳輸順序到達接收端(intheorder)?傳送的間距與接收的間距是否相同(jitter)?壅塞時的處理方法(congestion)?封包是否會在傳輸過程中遺失(loss-free)?,VirtualCircuit,VC的生命週期主要有三個部分:VCSetup:傳送端告知網路接收端的位址，由網路層依照傳送端以及接收端的位址開始建立VC。DataTransfer:開始傳送資料。Virtual-Circuitteardown:結束資料傳送並且釋放之前建立的VC。傳輸層的連線與網路層VC的重要差異:傳輸層連線為End-To-End的連線，中間的router不必紀錄連線狀態。VC:中間的router必須紀錄現有的VC狀態(state)。,VirtualCircuit,每個封包都包含VCidentifier而不是目的地位址(Destination)。SignalingMessage:用來建立或是結束VC。SignalingProtocol:交換signalingmessage的協定。,1.Initiatecall,2.incomingcall,3.Acceptcall,4.Callconnected,5.Dataflowbegins,6.Receivedata,Physical,DataLink,Network,Transport,Application,Physical,DataLink,Network,Transport,Application,DatagramNetwork,每個封包傳送時都含有接收端的位址(address)，不需要先行建立path，router查詢routingtable決定出口埠。Routingtable可以動態改變同一個資料流(flow)的封包不一定會依照相同路徑傳送。同一個資料流的封包不一定依照傳送順序到達。,1.Senddata,2.Receivedata,Physical,DataLink,Network,Transport,Application,Physical,DataLink,Network,Transport,Application,NetworkServiceModel,NetworkArchitectureInternetATMATMATMATM,ServiceModelbesteffortCBRVBRABRUBR,Bandwidthnoneconstantrateguaranteedrateguaranteedminimumnone,Lossnoyesyesnono,Ordernoyesyesyesyes,Timingnoyesyesnono,Congestionfeedbackno(inferredvialoss)nocongestionnocongestionyesno,Guarantees?,NetworkServiceModel,Best-Effort:不保證封包傳送的時間，接收時不保證順序正確，不保證不會遺失。CBR(Constantbitrate):ATMservicemodel中適合即時性以及穩定輸出量的資料流。可以保證延遲、封包遺失率小於某特定值。UBR(Unspecifiedbitrate):僅比Best-Effort的傳送方式多了保證順序正確的特性。ABR(availablebitrate):保證最少的傳輸量(MCR,MinimumCellTransmission)具有告知傳送端網路有壅塞的情形發生，必須調整MCR以及PCR(PeakCellRate)VBR(Variablebitrate).,Routing,Routing:尋找一條適當的路徑，將封包從傳送端傳遞到接收端。如圖:A,B,C,D,E,F為router，由實體連線互相連結。每條實體連線都會因為傳輸延遲、壅塞的情況賦予一個cost值。GoodPath:一般是指cost累加最小的路徑，但是也有可能因為實際需求的不同而有不同的定義。,RoutingAlgorithm的分類,RoutingAlgorithm可依照兩方面來分類:Router所蒐集的資訊範圍(Globalordecentralized)Route是靜態(static)還是動態(dynamic)變化Globalordecentralizedinformation:Global:每個router都知道整個網路的狀態及拓樸(Topology)，如”LinkState”algorithms.Decentralized:router只知道與鄰近節點的位址以及連線的cost。利用router間交換這些資訊，可以計算出完整的routingtable。如”distancevector”algorithms.,Link-StateAlgorithm(Global),Link-StateAlgorithm的特色：每個router都擁有相同且完整網路拓樸及cost的資訊。Example:DijkstrasAlgorithm初始條件：以本身為起始點，設定相鄰的節點的cost值，無直接連結的節點cost設定為無限大。替換條件：選擇最小cost的節點作為下一個起始點，不斷更新(比原來cost小)鄰近的節點所具有的cost值。終結條件：執行替換條件到鄰近的節點所具有的cost值都不需要在更新時，計算完成。,DijkstrasAlgorithm,符號定義：C(i,j):節點i到節點j的cost，若i,j不相鄰，此值為無限大。D(v):目前從起始點到v的最少cost(可能會被更新)。p(v):從起始點到v的前一個點(predecessornode)。N:已經確定與起始點最短路徑的所有點所成的集合(set)。,DijkstrasAlgorithm(Example),Step012345,startNAADADEADEBADEBCADEBCF,D(B),p(B)2,A2,A2,A,D(C),p(C)5,A4,D3,E3,E,D(D),p(D)1,A,D(E),p(E)infinity2,D,D(F),p(F)infinityinfinity4,E4,E4,E,DijkstrasAlgorithm,1Initialization:2N=A3forallnodesv4ifvadjacenttoA5thenD(v)=c(A,v)6elseD(v)=infty78Loop9findwnotinNsuchthatD(w)isaminimum10addwtoN11updateD(v)forallvadjacenttowandnotinN:12D(v)=min(D(v),D(w)+c(w,v)13/*newcosttoviseitheroldcosttovorknown14shortestpathcosttowpluscostfromwtov*/15untilallnodesinN,DijkstrasAlgorithm:時間複雜度,DijkstrasAlgorithm的計算時間複雜度(TimeComplexity)：假設共有n個節點。需要n*(n+1)/2次比較:O(n2),DistanceVectorAlgorithm(decentralized),DistanceVectorAlgorithm的特色：反覆交換訊息(iterative)。非對稱性(asynchronous)。分散式(distributed)。Router只需要知道最佳路徑的nexthop即可傳送。distancetable是用來計算route的主要資料結構。Table中的每個element的定義如下：,DistanceVectorAlgorithm:DistanceTable,loop!,DistanceVectorAlgorithm:DistanceTable-RoutingTable,Router可以依照distancetable找出具有到某個目的節點最少cost的next-hop。依照next-hop就可以知道routingtable。,ABCD,A,1D,5D,4D,4,Outgoinglinktouse,cost,destination,Routingtable,DistanceVectorAlgorithm,重新交換訊息的原因：週遭的Link-cost改變。鄰近的router告知到某節點的的最少cost改變。運作的流程圖如右：,DistanceVectorAlgorithm,1Initialization:2foralladjacentnodesv:3D(*,v)=infty/*the*operatormeansforallrows*/4D(v,v)=c(X,v)5foralldestinations,y6sendminD(y,w)toeachneighbor/*woverallXsneighbors*/,8loop9wait(untilIseealinkcostchangetoneighborV10oruntilIreceiveupdatefromneighborV)1112if(c(X,V)changesbyd)13/*changecosttoalldestsvianeighborvbyd*/14/*note:dcouldbepositiveornegative*/15foralldestinationsy:D(y,V)=D(y,V)+d1617elseif(updatereceivedfromVwrtdestinationY)18/*shortestpathfromVtosomeYhaschanged*/19/*VhassentanewvalueforitsminDV(Y,w)*/20/*callthisreceivednewvalueisnewval*/21forthesingledestinationy:D(Y,V)=c(X,V)+newval2223ifwehaveanewminD(Y,w)foranydestinationY24sendnewvalueofminD(Y,w)toallneighbors2526forever,DistanceVectorAlgorithm,DistanceVectorAlgorithm,DistanceVector:linkcostchanges,algorithmterminates,Y偵測到與X的連線cost減少(Goodnewstravelfast)。Y修改自己的distancetable。如果這條路徑在leastcost上，必須通知鄰近的router。,DistanceVector:linkcostchanges,Y偵測到與X的連線cost增加badnewstravelsslow:防止“counttoinfinity”。,algorithmcontinueson!,DistanceVector:Poisonreverse,Z經過Y到達X，通知Y經過Z到達X的cost為無限大(本身的distancetable仍要紀錄真實的值)。當X,Y之間連線的cost值變大，Z就不會再透過Y連到X，而是直接連結。此時Z告知Y到達X的cost為50。可以避免”counttoinfinity”。,algorithmterminates,HierarchicalRouting,在龐大的網際網路中，往往不只有一種routingprotocol，原因為Scale:當連結的網路變大，每個router的routingtable就會擴張的很迅速，因此必須要想辦法減少routingtable所佔的記憶體空間。Administrativeautonomy:某些單位可能希望自己所管理的網域採用某種routingprotocol，與外界無關。在同一個AS(AutonomousSystem)中的router採用相同的routingprotocol。Gatewayrouter:AS對外連結的router，對內跑intra-ASroutingprotocol，對外則跑inter-systemroutingprotocol。,Intra-ASandInter-ASrouting,A、B、C為三個不同的AS。必須由Gatewayrouter連結。,inter-AS,intra-ASroutingingatewayA.c,networklayer,linklayer,a,b,a,C,A,B,d,Intra-ASandInter-ASrouting,Hosth2,Hosth1,Intra-ASroutingwithinASA,Intra-ASroutingwithinASB,網路層通訊協定,Transportlayer:TCP,UDP,Linklayer,physicallayer,Networklayer,IPaddressing,IPaddress:由32bits所組成，用來辨識在網際網路上主機(Host)或介面(Interface)的數值。Router上通常有多個介面，一個主機上也允許有多個介面，每個介面具有各自的IPaddress。,,,,,=11011111000000010000000100000001,223,1,1,1,LAN,IPaddressing,IPaddress由兩個部分組成：Networkpart:較高位(Highorderpart)的位元用來辨識網域。HostPart(Interfacepart):較低位(Loworderpart)的位元用來辨識主機。何謂一個網域(Network)?IPaddress具有相同高位位元(NetworkPart)的介面所成的統稱。這些介面彼此互相連接而不透過router(Layer-3Device)。,IPaddressing,網路遮罩(NetworkMask):用來判斷IP位址中的NetworkPart以及HostPart。Example:/24，代表左邊24個位元是Networkpart，剩下的8位元是hostpart。IP網路位址可以依照前面若干個位元來區分是屬於哪個class(A,B,C,D)。,0,network,host,A,B,C,D,class,to55,to55,to55,to55,32bits,IPaddressing,如果完全依照class來分配IP位址，可能無法有效的利用IP位址(空著很多IP並未使用)。CIDR:ClasslessInterDomainRoutingIP位址的Networkpart長度並未固定，可以依照NetworkMask來決定Networkpart的長度。,IPaddressing,如何取得一個IP?經過人工設定，將IP位址寫入設定檔中。DynamicHostConfigurationProtocol(DHCP):啟動後與鄰近的DHCP伺服器取得IP。利用DHCP取得IP的步驟：客戶端廣播(broadcast)DHCPDiscovery的訊息。DHCP伺服器用DHCPOffer訊息告知客戶端有伺服器存在。客戶端送出DHCPRequest的訊息要求取得IP。DHCP伺服器送回DHCPAck的訊息夾帶派發的IP位址。,IPaddressing,利用網路遮罩(NetworkMask)可以將取得的一段IP再度分割成更小段的子網路(sub-network)。,“Sendmeanythingwithaddressesbeginning/20”,Fly-By-Night-ISP,Organization0,Organization7,Internet,Organization1,ISPs-R-Us,“Sendmeanythingwithaddressesbeginning/16”,Organization2,IPaddressing,ICANN:InternetCorporationforAssignedNamesandNumbers.分配IP位址。管理rootDNS。分派DomainName。要申請IP位址網段必須要向ICANN申請。,傳送IP封包的過程,封包(Layer-3packet)內容並未改變。傳送時依靠封包標頭(Header)內的目的地IP位置以及Routingtable決定出口埠。,傳送IP封包的過程,A要送封包到B，封包內容如上。A與B直接連線(Layer-2)。A利用子網路遮罩判斷B跟本身屬於同一個子網路。鏈結層會直接將此封包給B。,miscfields,,,data,傳送IP封包的過程,A要傳送封包給E，內容如上。利用子網路遮罩判斷，A與E並沒有在同一個子網路上，並未直接連線。A將此訊息(用鏈結層frame包裝)傳送給router()，封包(Layer-3)內容不變。Router查詢routingtable後發現目的地E所屬的子網路在的埠。Router將封包轉送(用鏈結層的frame包裝)至E所屬的子網路。E收到這個封包。,miscfields,,,data,傳送IP封包的過程,Routingtable如右：,IP封包格式,ver,length,32bits,data(variablelength,typicallyaTCPorUDPsegment),16-bitidentifier,Internetchecksum,timetolive,32bitsourceIPaddress,IPprotocolversionnumber,headerlength(bytes),maxnumberremaininghops(decrementedateachrouter),forfragmentation/reassembly,totaldatagramlength(bytes),upperlayerprotocoltodeliverpayloadto,head.len,typeofservice,“type”ofdata,flgs,fragmentoffset,upperlayer,32bitdestinationIPaddress,Options(ifany),E.g.timestamp,recordroutetaken,pecifylistofrouterstovisit.,IP封包切割與重組,MTU(MaximumTransferUnit):表示Link-Layer所能夠傳送封包的最大長度(會因不同的Link-Layer而有不同的MTU)。IP封包的切割：在傳送過程中將一個封包切割(fragmentation)為若干個小封包。在接收端接收到以後利用Header中的identifier重新組合(reassembly)。,fragmentation:in:onelargedatagramout:3smallerdatagrams,reassembly,IP封包切割與重組,Onelargedatagrambecomesseveralsmallerdatagrams,4040=4000+2*Header長度,ICMP:InternetControlMessageProtocol,ICMP是用來讓Host、Router以及Gateway交換網路層訊息的通訊協定。Errorreporting:unreachablehost,network,protocol.Echorequest/reply:ping.ICMP訊息是利用IP封包傳送。,TypeCodedescription00echoreply(ping)workunreachable31desthostunreachable32destprotocolunreachable33destportunreachable36destnetworkunknown37desthostunknown40sourcequench(congestioncontrol-notused)80echorequest(ping)90routeadvertisement100routerdiscovery110TTLexpired120badIPheader,RoutingintheInternet,網際網路由數個AS(AutonomousSystem)互相連結所組成。考慮AS的routing：IntraAS:管理者可以自由選擇在所屬AS內的RoutingProtocol。InterAS:必須與外界跑相同的RoutingProtocol。,InternetASHierarchy,Intra-ASborder(exteriorgateway)routers,Inter-ASinterior(gateway)routers,Intra-ASRouting,IGP:InteriorGatewayProtocols。一般常見的IGP:RIP:RoutingInformationProtocol.OSPF:OpenShortestPathFirst.IGRP:InteriorGatewayRoutingProtocol(Ciscoproprietary),RIP(RoutingInformationProtocol),採用”DistanceVectorAlgorithm”RFC1058(version1),RFC1723(version2)所紀錄的路徑長度最多通過15個hop。透過每三十秒傳送的RIPresponsemessage與相鄰的router交換routingtable，也稱作RIPadvertisement。每次利用RIPadvertisement交換routingtable最多可包含25個destinationnetwork.,RIP(RoutingInformationProtocol),DestinationNetworkNextRouterNum.ofhopstodest.wA2yB2zB7x-1.,w,x,y,z,A,C,D,B,RoutingtableinD,RIP處理連結(Link)變化的方式,如果超過180秒沒有聽到定期的廣播，則RIP就會認為此條路徑已經不復存在(與Neighbor斷線)。經過這個neighbor的路徑已經不在。傳送新的advertisement給其他neighbor。如果neighbor的routingtable有所更動，就會再度傳送出去。可以透過這種方式將連結變化傳送到整個網路。設定MaxHop=15的目的是避免Count-To-Infinity。,管理RIP的RoutingTable,利用在應用層執行的processrouted來管理RIProutingtable。(daemon)定期傳送UDP封包(advertisement)，routed再依照封包的內容修改本身的routingtable。,RIPTable的範例,第一行為Loop-Back。具有三個介面、、。第五行為IPmulticast。最後一行表示在表中查詢不到的IP就送往29。,DestinationGatewayFlagsRefUseInterface-UH026492lo0U213fa0U358503le0U225qaa0U30le0default29UG0143454,Router:giroflee.eurocom.fr,OSPF(OpenShortestPathFirst),OSPF:RFC2178(Version2)OSPF是一種Link-StateAlgorithm，每個router都知道整個AS的拓樸(Topology)狀況。Flooding:每個router必須要將本身與哪些neighbor相鄰的訊息傳送到整個AS。Security:所有router間交換的訊息需要被認可(authenticated)，防止錯誤的訊息影響到正常的routingtable。Multiplesame-costpaths:到達某目的地可能有多重路徑(相同cost)可以選擇。,OSPF(OpenShortestPathFirst),可以依照IPHeader中不同的TOS計算出不同的路徑。MulticastOSPF(MOSPF,RFC1584):利用原有的OSPF資料再加上新的link-stateadvertisement。HierarchicalOSPF：分成兩層：Localarea,backbone。Areaborderrouters:收集本身所在area內的資訊，並告知其他Areaborderrouters。Backbonerouters:採用OSPF，僅收集backbone的資訊。Boundaryrouters:連結其他AS的router。,HierarchicalOSPF,IGRP(InteriorGatewayRoutingProtocol),EIGRP(EnhancedInteriorGatewayRoutingProtocol):一種改進RIP的DistanceVectorAlgorithm。計算pathcost時不僅以hop數為cost，也考量：延遲(Delay)頻寬(Bandwidth)可靠度(Reliability)負載(load),Inter-ASrouting,Internetinter-ASrouting:BGP,BGP:BorderGatewayProtocol.PathVectorProtocol:與DistanceVector相似。Mechanism:router告知neighbor通往某個目的地的path(sequenceofASs)。Policy:管理者決定是否將這個path加入routingtable。Ex：GatewayX告知neighbor從X到達Z的路徑如下：Path(X,Z)=X,Y1,Y2,Y3,Z,Internetinter-ASrouting:BGP,考慮X將到Z的path告知W的各種情況:W可能因為下列原因不採用X所提供的路徑：Cost較高。不欲通過競爭性的AS。避免產生Loop。如果W採用了X所提供的路徑：Path(W,Z)=W,Path(X,Z)X本身也可以透過控制advertisement的方式做出一些管理的決策：X不希望別的封包透過X到達Z不廣播有關於Z的Path。,Internetinter-ASrouting:BGP,BGP的透過TCP作訊息交換。BGPmessage的種類：OPEN:與對方建立TCP連線並且確認Sender。UPDATE:廣播新的path，或是取消舊的path。KEEPALIVE:目的是維持TCP連線(可能一段時間沒有UPDATE訊息)，也用來產生OPEN的ACKs。NOTIFICATION:回報上述的訊息所產生的錯誤或是關閉連線。,Intra-與Inter-ASrouting的不同,Policy:Inter-AS:AS的管理者需要Policy來控制是否讓其他AS的封包通過。Intra-AS:單一管理者。Scale:利用Hierarchy的方式可以減少routingtable的大小，也減少update的流量。Performance:Intra-AS:在乎performance。Inter-AS:policy的重要性勝於performance的重要性。,RouterArchitecture,Router的主要兩個功能：與其他router溝通(routingprotocol)交換封包到適當的出口(outgoinglink),InputPort,DecentralizedSwitching依照封包的dest欄位決定要往哪個outputport傳送。當封包流入的速度比處理的速度快，就儲存在queue中等待處理。,Physicallayer:bit-levelreception,Datalinklayer:e.g.,Ethernetseechapter5,InputPortQueuing,當封包流入的總和比交換switch的速