通信網理論基礎

第三部分圖論基礎與應用1.基本概念圖G(V,E)

由兩個集合加以定義:頂點(或節點)集合

V={v1,v2,v3….vn};邊集合

E={e1,e2,e3……em};G={V,E}邊由一對直接關連的頂點的組合定義如果:(i,j)E,則頂點i和j稱為相鄰的頂點的數目稱為圖的“階”;邊的數目稱為圖的“尺寸”;許多圖的算法的運行時間與圖的“階”和“尺寸”相關2.圖的一個例子3.圖的鄰接矩陣鄰接矩陣是用數學方式來表示圖頂點編號:1,2,3,…,|V||V|x|V|鄰接矩陣

A=(ai,j)定義為:ai,j=1if(i,j)E(ij是圖的一條邊)0otherwise對于邊沒有方向性的圖(即邊的兩頂點的順序不影響邊的性質),鄰接矩陣A是對稱矩陣.4.鄰接矩陣一例5.Terminology關聯同一對頂點的邊稱為:平行邊關聯同一頂點的邊稱為:環既無平行邊,又無環的圖稱為:簡單圖頂點i到頂點j的路徑是:

頂點和邊的交替序列起于i,止于j;每條邊只與序列中直接在它前面和直接在它后面的頂點相連簡單路徑:頂點和邊在序列中只出現一次的路徑

在簡單圖中,簡單路徑可以由頂點序列來定義每個頂點與序列中在其前面和后面的頂點相鄰序列中沒有重復的頂點6.簡單路徑(1)由V1到

V6(不完全)V1,V2,V3,V4,V5,V6V1,V2,V3,V5,V6V1,V2,V3,V6V1,V2,V4,V3,V5,V6V1,V2,V4,V5,V6V1,V3,V2,V4,V5,V6V1,V3,V6V1,V4,V3,V6總共14條(其余的請自行列出)7.簡單圖(2)兩頂點間的所有路徑中有一條最短路徑,如:V1,V3,V6頂點間的距離是所有路徑中邊數最少的路徑的邊的數目回路是起于和止于同一頂點的路徑例如:.V1,V3,V4,V18.有向圖邊有方向性的圖有向圖G(V,E)的邊由一對頂點的有序組合來定義代表邊的線段用箭頭表示其方向允許存在平行邊,只要它們的方向相反便于用圖表示通信網絡每條有向邊表達一個方向上的數據流仍然可用鄰接矩陣表示除非每對相鄰的頂點用平行邊連接,否則鄰接矩陣是不對稱的9.加權圖或加權有向圖每條邊有一與之關聯的數(權值w)-------便于說明路由算法鄰接矩陣定義為:

ai,j=

wi,jif(i,j)E0otherwisewi,j是與邊(i,j)關聯的權值路徑長度是權值之和最短距離路徑不一定是長度最短路徑(見下面兩張PPT)10.加權圖與鄰接矩陣11.V1

至V6

的路徑距離和路徑長度路徑 距離長度V1,V2,V3,V4,V5,V6 5 11V1,V2,V3,V5,V6 4 8V1,V2,V3,V6 3 10V1,V2,V4,V3,V5,V6 5 10V1,V2,V4,V5,V6 4 7V1,V3,V2,V4,V5,V6 5 16V1,V3,V6 2 10V1,V4,V5,V6 3 412.樹樹是圖的子集以下幾項定義是等效的:*樹是一種簡單圖,頂點i

和j之間只有一條簡單路徑*N個頂點的簡單圖如果只有N-1條邊,沒有回路*N個頂點的簡單圖如果只有N-1條邊,而且是連通的可以指定一個頂點為“根”根通常畫在上部與根鄰接的頂點畫在下一層這些頂點可以到達樹根,路徑距離為113.樹中頂點的等級關系每個頂點(除根外)有一個父頂點靠根一邊的鄰接頂點每個頂點有0個或幾個子頂點離根遠的鄰接頂點沒有子頂點的頂點稱為葉層次等級直接在根下面的頂點是第一層第一層頂點的子頂點是第二層14.

樹的例15.子圖從圖G中選擇一些邊和頂點構成G的子圖每條被選上的邊的兩個關聯頂點必須同時選上圖G’(E’,V’)是圖G(E,V)的子圖,如果:V’V,

E’E

并且對每一條E’中的邊e’.如果e’

關聯v’andw’,

則v’,w’V’16.生成樹圖G的子圖T是一顆生成樹,如果:T

是樹

包含G的所有頂點從圖G中刪去一些邊,使所有的回路不復存在,但保持圖的連通性:圖G的生成樹通常并不唯一17.生成樹的例子18.生成樹的“先廣搜索”算法將頂點劃分成不同的層次在處理下一層之前,先處理完本層的所有頂點從任一頂點x開始指定它為0層所有它的鄰接頂點屬于1層設Vi1,Vi2,

Vi3,…

Vij,是i層的頂點所有Vi1的鄰接頂點中不屬于1,2,…,i層的頂點指定為(i+1)層所有Vi2的鄰接頂點中不屬于1,2,3,…,i,(i+1)層的頂點也指定為(i+1)層直到所有頂點被處理完畢19.例選擇頂點順序如:V1,V2,V3,V4,V5,V6選擇“根”例如V1現在樹T只包含一個頂點V1,不含邊在樹上增加邊(V1,x)和頂點x,但不要形成回路:將邊(V1,V2),(V1,V3),(V1,V4)和頂點V1,V2,V3加入到樹中,這是第一層在第一層的頂點上按序重復上述過程,得到第二層是否所有頂點都處理完?如果沒有,在第二層的頂點上重復處理過程,得到第三層….…20.上例的圖示21.AvoidingLoopsLAN1LAN2LAN3B1B2B3B4B5LAN4(1)(2)(1)22.AvoidingLoopsLAN1LAN2LAN3B1B2B3B4B5LAN4(1)(2)(1)23.SpanningTreeAlgorithmSelectarootbridgeamongallthebridges.rootbridge=thelowestbridgeID.Determinetherootportforeachbridgeexcepttherootbridgerootport=portwiththeleast-costpathtotherootbridgeSelectadesignatedbridgeforeachLANdesignatedbridge=bridgehasleast-costpathfromtheLANtotherootbridge.designatedportconnectstheLANandthedesignatedbridgeAllrootportsandalldesignatedportsareplacedintoa“forwarding”state.Thesearetheonlyportsthatareallowedtoforwardframes.Theotherportsareplacedintoa“blocking”state.24.LAN1LAN2LAN3B1B2B3B4B5LAN4(1)(2)(1)(1)(1)(1)(2)(2)(2)(2)(3)25.LAN1LAN2LAN3B1B2B3B4B5LAN4(1)(2)(1)(1)(1)(1)(2)(2)(2)(2)(3)Bridge1selectedasrootbridge26.LAN1LAN2LAN3B1B2B3B4B5LAN4(1)(2)(1)(1)(1)(1)(2)(2)(2)(2)(3)RootportselectedforeverybridgeexceptrootportRRRR27.最短距離路徑的距離BFS算法可以得到從根頂點s到所有其他頂點的最短距離路徑和距離δ(s,v)

任何從s

到v的路徑中BFS給出的路徑是距離最短的,即該路徑邊數之和最小。28.最短長度路徑分組交換,幀中繼,ATM等網絡可以看作一張圖每個節點是圖中一頂點每一鏈路是一對平行邊對于互聯網(Internet或intranet)每個路由器是一個頂點如路由器直接相連,雙向連接相當于一對平行邊如多于兩個路由器,則由多對平行邊構成表示網絡的圖一對邊連接一對路由器為將分組由源送到目的,需要路由決策等效于在圖上找出路徑29.路由決策基于最小代價最少跳數(hop)每條邊(一跳)的權重為1相當于最短距離路徑或者,每跳有一相關聯的代價(見下一PPT)路徑的代價是路徑中各鏈路的代價之和需要找出最小代價路徑相當于加權圖中的最小長度路徑30.一跳的代價反比于路徑的容量正比于當前的負荷鏈路的貨幣價值幾種因素的組合在不同方向上的代價可能不同31.Dijkstra算法(1)–定義

N=網絡頂點的集合s=源頂點(起始點)T=到目前為止算法已經用到的頂點的臨時集合Tree=T中頂點組成的生成樹,它包括從s到T中每個頂點的最小代價路徑上的邊w(i,j)=從頂點i到頂點j的鏈路代價,w(i,i)=0w(i,j)=ifi,j不直接連接w(i,j)0ifi,j直接連接L(n)=當前知道的從s到n的最小代價路徑的代價cost運算結束是它就是從s到n的最小代價路徑的代價32.Dijkstra算法(2)–步驟初始化T=Tree={s}–臨時頂點集合中暫時只含源頂點L(n)=w(s,n)forns;到鄰點的初始路徑代價就是鏈路代價取下一個頂點找xT使L(x)=minL(j),jT將x加入到T和Tree中將關聯x,且使L(x)成為最小代價的邊加入到Tree中它是路徑的最后一跳更新最小代價路徑L(n)=min[L(n),L(x)+w(x,n)]nT如果后一項最小,從s到n的路徑就是從s到x的路徑與從x到n的邊的連接33.Dijkstra算法原理圖示TSNXnw(x,n)L(n)L(x)已算出最短路徑的點的集合找xT使

L(x)=minL(j),jT

x→TL(n)=min[L(n),L(x)+w(x,n)]nT所以，S需要知道w(x,n)-----各點與其鄰點間直接相連鏈路的代價因而需要與所有其他各點交換路由信息某點（s)已知網絡中其他各點到其鄰點的鏈路的代價值w(x,n),計算S到其他各點的最短路徑34.Dijkstra’s算法(3)–說明當所有頂點都加入到T以后,算法結束需要|V|次迭代結束時L(x)是s到x的最小代價路徑的代價值Tree是原圖的一顆最小生成樹定義了從s到其他頂點的最小代價路徑每次迭代有一個新的頂點加入到T中,運行時間是|V|2量級35.Dijkstra算法用于例圖36.Bellman-Ford算法(1)–定義

s=源頂點(起始點)w(i,j)=從頂點i到頂點j的鏈路的代價值w(i,i)=0w(i,j)=如i,j不直接相連w(i,j)0如i,j直接連接h=在算法的當前步驟中路徑的最大鏈路數Lh(n)=從頂點s到n的最小代價路徑的代價,限制條件是路徑的鏈路數不超過h37.Bellman-Ford算法(2)–步驟初始化L0(n)=nsLh(s)=0h更新對每個相繼的h0對每個ns,計算:Lh+1(n)

=min[Lh(j)+w(j,n)],j找到實現最小值的頂點j,將n與該前趨頂點j相連,刪除n與此前計算得到與j不同的前趨頂點的連接,從s到n的路徑以j到n的鏈路結束38.Bellman-FordAlgorithm(3)–

說明結果與Dijkstra算法的結果相同運行時間是|V|x|E|的量級39.Bellmin-Ford算法原理圖示Sn已知n與其鄰點間鏈路的代價值w(j,n);j到s的最短路徑的代價值L(j);找n到s的最短路徑；j對每個ns,計算:Lh+1(n)

=min[Lh(j)+w(j,n)],jw(j,n)（已知，因為與n直連）L(n)L(j)n點在計算時需知其鄰接點的L(j)—當前估計的到S的最短路徑的長度，和它到自己的鄰點的鏈路的代價值，所以為了求出到所有點的最短路徑，每點需與其鄰接點交換各自到所有其他點的最短路徑長度的當前估計值40.Bellman-Ford算法用于例圖41.Dijkstra和Bellman-Ford

算法的運算結果42.比較所需要的信息

–Bellman-Ford算法頂點n處的計算需要知道到所有鄰接點的鏈路的代價,以及從源點到這些點的路徑的總代價e每個頂點需要維持一個到網絡中所有其他頂點的路徑及其代價的表與其直接鄰接頂點交換上述信息每個頂點都用Bellman-Ford算法步驟2中的表達式更新其路徑與代價表43.比較兩種算法所需要的信息-------------Dijkstra算法步驟3要求每個頂點知道網絡拓撲的完整信息,因而:必須知道網絡中所有鏈路的代價值每個頂點必須與所有其他頂點交換信息究竟哪個算法好,需要考慮算法的運行時間等其他因素44.其他事項當網絡拓撲和鏈路代價處于準靜態時,兩種算法都收斂給出相同的結果如果鏈路代價變化,算法會企圖跟上這種變化如果鏈路代價與通信流量有關,而后者又與路由選擇有關,則:存在反饋可能產生不穩定45.46.AutonomousSystemsGlobalInternetviewedascollectionofautonomoussystems.Autonomoussystem(AS)isasetofroutersornetworksadministeredbyasingleorganizationSameroutingprotocolneednotberunwithintheASBut,totheoutsideworld,anASshouldpresentaconsistentpictureofwhatASsarereachablethroughitStubAS:hasonlyasingleconnectiontotheoutsideworld.MultihomedAS:hasmultipleconnectionstotheoutsideworld,butrefusestocarrytransittrafficTransitAS:hasmultipleconnectionstotheoutsideworld,andcancarrytransitandlocaltraffic.47.ASNumberForexteriorrouting,anASneedsagloballyuniqueAS16-bitintegernumberCurrently,thereareabout11,000registeredASsinInternet(andgrowing)StubAS,whichisthemostcommontype,doesnotneedanASnumbersincetheprefixesareplacedattheprovider’sroutingtableTransitASneedsanASnumberRequestanASnumberfromtheARIN,RIPEandAPNIC48.InterandIntraDomainRoutingRRRRRRRRASAASBASCIGPEGPIGPIGPInteriorGatewayProtocol(IGP):routingwithinASRIP,OSPFExteriorGatewayProtocol(EGP):routingbetweenAS’sBGPv4BorderGatewaysperformIGP&EGProuting49.OutlineBasicRoutingRoutingInformationProtocol(RIP)OpenShortestPathFirst(OSPF)BorderGatewayProtocol(BGP)50.RFC1058RIPbasedonrouted,“routed”,distributedinBSDUNIXUsesthedistance-vectoralgorithmRunsontopofUDP,portnumber520Metric:numberofhopsMaxlimitedto15suitableforsmallnetworks(localareaenvironments)valueof16isreservedtorepresentinfinitysmallnumberlimitsthecount-to-infinityproblemRoutingInformationProtocol(RIP)51.RIPOperationRoutersendsupdatemessagetoneighborsevery30secArouterexpectstoreceiveanupdatemessagefromeachofitsneighborswithin180secondsintheworstcaseIfrouterdoesnotreceiveupdatemessagefromneighborXwithinthislimit,itassumesthelinktoXhasfailedandsetsthecorrespondingminimumcostto16(infinity)Usessplithorizonwithpoisonedreverse

Convergencespeededupbytriggeredupdatesneighborsnotifiedimmediatelyofchangesindistancevectortable52.RIPProtocolRoutersrunRIPinactivemode(advertisedistancevectortables)HostscanrunRIPinpassivemode(updatedistancevectortables,butdonotadvertise)RIPdatagramsbroadcastoverLANs&specificallyaddressedonpt-ptormulti-accessnon-broadcastnetsTwoRIPpackettypes:requesttoaskneighborfordistancevectortableresponsetoadvertisedistancevectortableperiodically;inresponsetorequest;triggered53.CommandVersion

ZeroAddressfamilyidentifierZeroIPaddressZeroZeroMetric081631...RIPMessageFormatRequest/Response1/22forIPRIPentryUpto25RIPentriespermessage54.Command:requestorresponseVersion:v1orv2Oneormoreof:AddressFamily:2forIPIPAddress:networkorhostdestinationMetric:numberofhopstodestinationDoesnothaveaccesstosubnetmaskinformationCannotworkwithvariable-lengthsubnetmasksRIPv2(RFC2453):Subnetmask,nexthop,routingdomaincanworkwithCIDRstillusesmaxcostof16RIPMessageFormat55.OutlineBasicRoutingRoutingInformationProtocol(RIP)OpenShortestPathFirst(OSPF)BorderGatewayProtocol(BGP)56.UsedinOSPFtodistributelinkstate(LS)informationForwardincomingpackettoallportsexceptwherepacketcameinPacketeventuallyreachesdestinationaslongasthereisapathbetweenthesourceanddestinationGeneratesexponentialnumberofpackettransmissionsApproachestolimit#oftransmissions:UseaTTLateachpacket;won’tfloodifTTLisreachedEachrouteraddsitsidentifiertoheaderofpacketbeforeitfloodsthepacket;won’tfloodifitsidentifierisdetectedEachpacketfromagivensourceisidentifiedwithauniquesequencenumber;won’tfloodifsequencenumberissameFlooding57.ExampleOSPFTopology10.5.1.110.5.1.310.5.1.510.5.1.210.5.1.410.5.1.6Atsteadystate:AllroutershavesameLSdatabaseKnowhowmanyroutersinnetworkInterfaces&linksbetweenroutersCostofeachlinkOccasionalHellomessages(10sec)&LSupdatessent(30min)58.Toimprovescalability,ASmaybepartitionedintoareasAreaisidentifiedby32-bitAreaIDRouterinareaonlyknowscompletetopologyinsidearea&limitsthefloodingoflink-stateinformationtoareaAreaborderrouterssummarizeinfofromotherareasEachareamustbeconnectedtobackbonearea(0.0.0.0)DistributesroutinginfobetweenareasInternalrouterhasalllinkstonetswithinthesameareaAreaborderrouterhaslinkstomorethanoneareabackbonerouterhaslinksconnectedtothebackboneAutonomoussystemboundary(ASB)routerhaslinkstoanotherautonomoussystem.OSPFNetwork59.ASB:4ABR:3,6,and8IR:1,2,7BBR:3,4,5,6,8Area0.0.0.1Area0.0.0.2Area0.0.0.3R1R2R4R5R7N1N2N3N4N5N6N7ToanotherASArea0.0.0.0R=routerN=networkR8R3R6OSPFAreas60.Neighborrouters:tworoutersthathaveinterfacestoacommonnetworkNeighborsarediscovereddynamicallybyHelloprotocolEachneighborofarouterdescribedbyastatedown,attempt,init,2-way,Ex-Start,Exchange,Loading,FullAdjacentrouter:neighborroutersbecomeadjacentwhentheysynchronizetopologydatabasesbyexchangeoflinkstateinformationNeighborsonpoint-to-pointlinksbecomeadjacentRoutersonmultiaccessnetsbecomeadjacentonlytodesignated&backupdesignatedroutersReducessizeoftopologicaldatabase&routingtrafficNeighbor,Adjacent&DesignatedRouters61.ReducesnumberofadjacenciesElectedbyeachmultiaccessnetworkafterneighbordiscoverybyhelloprotocolElectionbasedonpriority&idfieldsGenerateslinkadvertisementsthatlistroutersattachedtoamulti-accessnetworkFormsadjacencieswithroutersonmulti-accessnetworkBackuppreparedtotakeoverifdesignatedrouterfailsDesignatedRouters62.Linkstateinfoexchangedbyadjacentrouterstoallowareatopologydatabasestobemaintainedinter-area&inter-ASroutestobeadvertisedRouterlinkad:generatedbyallOSPFroutersstateofrouterlinkswithinarea;floodedwithinareaonlyNetlinkad:generatedbythedesignatedrouter

listsroutersconnectedtonet:floodedwithinareaonlySummarylinkad:generatedbyareaborderrouters1.routestodestinotherareas;2.routestoASBroutersASexternallinkad:generatedbyASBroutersdescribesroutestodestinationsoutsidetheOSPFnetfloodedinallareasintheOSPFnetLinkStateAdvertisements63.OSPFpacketstransmitteddirectlyonIPdatagrams;ProtocolID89TOS0,IPprecedencefieldsettointernetworkcontroltogetprecedenceovernormaltrafficOSPFpacketssenttomulticastaddress224.0.0.5(allSPFRoutersonpt-2-ptandbroadcastnets)OSPFpacketssentonspecificIPaddressesonnon-broadcastnetsFiveOSPFpackettypes:HelloDatabasedescriptionLinkstaterequest;Linkstateupdate;LinkstateackOSPFProtocol64.OSPFHeaderType:Hello,Databasedescription,Linkstaterequest,Linkstateupdate,LinkstateacknowledgementsVersionTypePacketlengthRouterIDAreaIDChecksumAuthenticationtypeAuthenticationAuthentication081631OSPFcommonheaderOSPFpacketbodyData65.OSPFStagesDiscoverneighborsbysendingHellopackets(every10sec)anddesignatedrouterelectedinmultiaccessnetworksAdjacenciesareestablished&linkstatedatabasesaresynchronizedLinkstateinformationispropagated&routingtablesarecalculatedWeelaborateonOSPFstagesinfollowing66.Stage1:OSPFHelloPacketHellointerval:numberofsecondsbetweenHellopacketsPriority:usedtoelectdesignatedrouter&backupDeadinterval:#secbeforedeclaringanon-respondingneighbordown.Neighbor:theRouterIDofeachneighborfromwhomHellopacketshaverecentlybeenreceivedSendHellopacketstoestablish&maintainneighborrelationshipNetworkmaskHellointervalOptionsPriority0162431DeadintervalDesignatedrouterBackupdesignatedrouterNeighbor1Neighborn...67.Stage2:OSPFDatabaseDescriptionInitbit1ifpktisfirstinsequenceofdatabasedescriptionpacketsMorebit1iftherearemoredatabasedescriptionpacketstofollowMaster/Slavebitindicatesthattherouteristhemaster.Linkstatead(LSA)headerdescribesstateofrouterornetwork;containsinfotouniquelyidentifyentryinLSA(type,ID,andadvertisingrouter).CanhavemultipleLSAheadersOnceneighborroutersbecomeadjacent,theyexchangedatabasedescriptionpacketstosynchronizetheirlink-statedatabases.68.LSAHeaderLStype:RouterLSAsgeneratedbyallOSPFrouters;NetworkLSAsgeneratedbydesignatedrouters;SummaryLSAsbyareaborderrouters;AS-externalLSAsbyASBRsLSid:identifiespieceofroutingdomainbeingdescribedbyLSALSSeq.Number:numbersLSAstodetectold/duplicateLSAsLSchecksum:coverscontentsofLSAexceptlinkstateageLink-stateageOptions