《通信網(wǎng)理論基礎(chǔ)》

通信網(wǎng)理論基礎(chǔ)

第三部分圖論基礎(chǔ)與應(yīng)用《通信網(wǎng)理論基礎(chǔ)》(2)基本概念圖G(V,E)

由兩個集合加以定義:頂點(diǎn)(或節(jié)點(diǎn))集合

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

E={e1,e2,e3……em};G={V,E}邊由一對直接關(guān)連的頂點(diǎn)的組合定義如果:(i,j)

E,則頂點(diǎn)i和j稱為相鄰的頂點(diǎn)的數(shù)目稱為圖的“階”;邊的數(shù)目稱為圖的“尺寸”;許多圖的算法的運(yùn)行時間與圖的“階”和“尺寸”相關(guān)《通信網(wǎng)理論基礎(chǔ)》(2)圖的一個例子《通信網(wǎng)理論基礎(chǔ)》(2)圖的鄰接矩陣鄰接矩陣是用數(shù)學(xué)方式來表示圖頂點(diǎn)編號:1,2,3,…,|V||V|x|V|鄰接矩陣

A=(ai,j)定義為:ai,j=1if(i,j)

E(ij是圖的一條邊)0otherwise對于邊沒有方向性的圖(即邊的兩頂點(diǎn)的順序不影響邊的性質(zhì)),鄰接矩陣A是對稱矩陣.《通信網(wǎng)理論基礎(chǔ)》(2)鄰接矩陣一例《通信網(wǎng)理論基礎(chǔ)》(2)Terminology關(guān)聯(lián)同一對頂點(diǎn)的邊稱為:平行邊關(guān)聯(lián)同一頂點(diǎn)的邊稱為:環(huán)既無平行邊,又無環(huán)的圖稱為:簡單圖頂點(diǎn)i到頂點(diǎn)j的路徑是:

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

在簡單圖中,簡單路徑可以由頂點(diǎn)序列來定義每個頂點(diǎn)與序列中在其前面和后面的頂點(diǎn)相鄰序列中沒有重復(fù)的頂點(diǎn)《通信網(wǎng)理論基礎(chǔ)》(2)簡單路徑(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條(其余的請自行列出)《通信網(wǎng)理論基礎(chǔ)》(2)簡單圖(2)兩頂點(diǎn)間的所有路徑中有一條最短路徑,如:V1,V3,V6頂點(diǎn)間的距離是所有路徑中邊數(shù)最少的路徑的邊的數(shù)目回路是起于和止于同一頂點(diǎn)的路徑例如:.V1,V3,V4,V1《通信網(wǎng)理論基礎(chǔ)》(2)有向圖邊有方向性的圖有向圖G(V,E)的邊由一對頂點(diǎn)的有序組合來定義代表邊的線段用箭頭表示其方向允許存在平行邊,只要它們的方向相反便于用圖表示通信網(wǎng)絡(luò)每條有向邊表達(dá)一個方向上的數(shù)據(jù)流仍然可用鄰接矩陣表示除非每對相鄰的頂點(diǎn)用平行邊連接,否則鄰接矩陣是不對稱的《通信網(wǎng)理論基礎(chǔ)》(2)加權(quán)圖或加權(quán)有向圖每條邊有一與之關(guān)聯(lián)的數(shù)(權(quán)值w)-------便于說明路由算法鄰接矩陣定義為:

ai,j=

wi,jif(i,j)

E0otherwisewi,j是與邊(i,j)關(guān)聯(lián)的權(quán)值路徑長度是權(quán)值之和最短距離路徑不一定是長度最短路徑(見下面兩張PPT)《通信網(wǎng)理論基礎(chǔ)》(2)加權(quán)圖與鄰接矩陣《通信網(wǎng)理論基礎(chǔ)》(2)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 4《通信網(wǎng)理論基礎(chǔ)》(2)樹樹是圖的子集以下幾項(xiàng)定義是等效的:*樹是一種簡單圖,頂點(diǎn)i

和j之間只有一條簡單路徑*N個頂點(diǎn)的簡單圖如果只有N-1條邊,沒有回路*N個頂點(diǎn)的簡單圖如果只有N-1條邊,而且是連通的可以指定一個頂點(diǎn)為“根”根通常畫在上部與根鄰接的頂點(diǎn)畫在下一層這些頂點(diǎn)可以到達(dá)樹根,路徑距離為1《通信網(wǎng)理論基礎(chǔ)》(2)樹中頂點(diǎn)的等級關(guān)系每個頂點(diǎn)(除根外)有一個父頂點(diǎn)靠根一邊的鄰接頂點(diǎn)每個頂點(diǎn)有0個或幾個子頂點(diǎn)離根遠(yuǎn)的鄰接頂點(diǎn)沒有子頂點(diǎn)的頂點(diǎn)稱為葉層次等級直接在根下面的頂點(diǎn)是第一層第一層頂點(diǎn)的子頂點(diǎn)是第二層《通信網(wǎng)理論基礎(chǔ)》(2)

樹的例《通信網(wǎng)理論基礎(chǔ)》(2)子圖從圖G中選擇一些邊和頂點(diǎn)構(gòu)成G的子圖每條被選上的邊的兩個關(guān)聯(lián)頂點(diǎn)必須同時選上圖G’(E’,V’)是圖G(E,V)的子圖,如果:V’

V,

E’

E

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

關(guān)聯(lián)v’andw’,

則v’,w’

V’《通信網(wǎng)理論基礎(chǔ)》(2)生成樹圖G的子圖T是一顆生成樹,如果:T

是樹

包含G的所有頂點(diǎn)從圖G中刪去一些邊,使所有的回路不復(fù)存在,但保持圖的連通性:圖G的生成樹通常并不唯一《通信網(wǎng)理論基礎(chǔ)》(2)生成樹的例子《通信網(wǎng)理論基礎(chǔ)》(2)生成樹的“先廣搜索”算法將頂點(diǎn)劃分成不同的層次在處理下一層之前,先處理完本層的所有頂點(diǎn)從任一頂點(diǎn)x開始指定它為0層所有它的鄰接頂點(diǎn)屬于1層設(shè)Vi1,Vi2,

Vi3,…

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

任何從s

到v的路徑中BFS給出的路徑是距離最短的,即該路徑邊數(shù)之和最小。《通信網(wǎng)理論基礎(chǔ)》(2)最短長度路徑分組交換,幀中繼,ATM等網(wǎng)絡(luò)可以看作一張圖每個節(jié)點(diǎn)是圖中一頂點(diǎn)每一鏈路是一對平行邊對于互聯(lián)網(wǎng)(Internet或intranet)每個路由器是一個頂點(diǎn)如路由器直接相連,雙向連接相當(dāng)于一對平行邊如多于兩個路由器,則由多對平行邊構(gòu)成表示網(wǎng)絡(luò)的圖一對邊連接一對路由器為將分組由源送到目的,需要路由決策等效于在圖上找出路徑《通信網(wǎng)理論基礎(chǔ)》(2)路由決策基于最小代價最少跳數(shù)(hop)每條邊(一跳)的權(quán)重為1相當(dāng)于最短距離路徑或者,每跳有一相關(guān)聯(lián)的代價(見下一PPT)路徑的代價是路徑中各鏈路的代價之和需要找出最小代價路徑相當(dāng)于加權(quán)圖中的最小長度路徑《通信網(wǎng)理論基礎(chǔ)》(2)一跳的代價反比于路徑的容量正比于當(dāng)前的負(fù)荷鏈路的貨幣價值幾種因素的組合在不同方向上的代價可能不同《通信網(wǎng)理論基礎(chǔ)》(2)Dijkstra算法(1)–定義

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

L(x)=minL(j),jT

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

s=源頂點(diǎn)(起始點(diǎn))w(i,j)=從頂點(diǎn)i到頂點(diǎn)j的鏈路的代價值w(i,i)=0w(i,j)=

如i,j不直接相連w(i,j)0如i,j直接連接h=在算法的當(dāng)前步驟中路徑的最大鏈路數(shù)Lh(n)=從頂點(diǎn)s到n的最小代價路徑的代價,限制條件是路徑的鏈路數(shù)不超過h《通信網(wǎng)理論基礎(chǔ)》(2)Bellman-Ford算法(2)–步驟初始化L0(n)=nsLh(s)=0h更新對每個相繼的h0對每個ns,計算:Lh+1(n)

=min[Lh(j)+w(j,n)],j找到實(shí)現(xiàn)最小值的頂點(diǎn)j,將n與該前趨頂點(diǎn)j相連,刪除n與此前計算得到與j不同的前趨頂點(diǎn)的連接,從s到n的路徑以j到n的鏈路結(jié)束《通信網(wǎng)理論基礎(chǔ)》(2)Bellman-FordAlgorithm(3)–

說明結(jié)果與Dijkstra算法的結(jié)果相同運(yùn)行時間是|V|x|E|的量級《通信網(wǎng)理論基礎(chǔ)》(2)Bellmin-Ford算法原理圖示Sn已知n與其鄰點(diǎn)間鏈路的代價值w(j,n);j到s的最短路徑的代價值L(j);找n到s的最短路徑；j對每個ns,計算:Lh+1(n)

=min[Lh(j)+w(j,n)],jw(j,n)（已知，因?yàn)榕cn直連）L(n)L(j)n點(diǎn)在計算時需知其鄰接點(diǎn)的L(j)—當(dāng)前估計的到S的最短路徑的長度，和它到自己的鄰點(diǎn)的鏈路的代價值，所以為了求出到所有點(diǎn)的最短路徑，每點(diǎn)需與其鄰接點(diǎn)交換各自到所有其他點(diǎn)的最短路徑長度的當(dāng)前估計值40《通信網(wǎng)理論基礎(chǔ)》(2)Bellman-Ford算法用于例圖《通信網(wǎng)理論基礎(chǔ)》(2)Dijkstra和Bellman-Ford

算法的運(yùn)算結(jié)果《通信網(wǎng)理論基礎(chǔ)》(2)比較所需要的信息

–Bellman-Ford算法頂點(diǎn)n處的計算需要知道到所有鄰接點(diǎn)的鏈路的代價,以及從源點(diǎn)到這些點(diǎn)的路徑的總代價e每個頂點(diǎn)需要維持一個到網(wǎng)絡(luò)中所有其他頂點(diǎn)的路徑及其代價的表與其直接鄰接頂點(diǎn)交換上述信息每個頂點(diǎn)都用Bellman-Ford算法步驟2中的表達(dá)式更新其路徑與代價表《通信網(wǎng)理論基礎(chǔ)》(2)比較兩種算法所需要的信息-------------Dijkstra算法步驟3要求每個頂點(diǎn)知道網(wǎng)絡(luò)拓?fù)涞耐暾畔?因而:必須知道網(wǎng)絡(luò)中所有鏈路的代價值每個頂點(diǎn)必須與所有其他頂點(diǎn)交換信息究竟哪個算法好,需要考慮算法的運(yùn)行時間等其他因素《通信網(wǎng)理論基礎(chǔ)》(2)其他事項(xiàng)當(dāng)網(wǎng)絡(luò)拓?fù)浜玩溌反鷥r處于準(zhǔn)靜態(tài)時,兩種算法都收斂給出相同的結(jié)果如果鏈路代價變化,算法會企圖跟上這種變化如果鏈路代價與通信流量有關(guān),而后者又與路由選擇有關(guān),則:存在反饋可能產(chǎn)生不穩(wěn)定《通信網(wǎng)理論基礎(chǔ)》(2)《通信網(wǎng)理論基礎(chǔ)》(2)AutonomousSystemsGlobalInternetviewedascollectionofautonomoussystems.Autonomoussystem(AS)isasetofroutersornetworksadministeredbyasingleorganizationSameroutingprotocolneednotberunwithintheASBut,totheoutsideworld,anASshouldpresentaconsistentpictureofwhatASsarereachablethroughitStubAS:hasonlyasingleconnectiontotheoutsideworld.MultihomedAS:hasmultipleconnectionstotheoutsideworld,butrefusestocarrytransittrafficTransitAS:hasmultipleconnectionstotheoutsideworld,andcancarrytransitandlocaltraffic.《通信網(wǎng)理論基礎(chǔ)》(2)ASNumberForexteriorrouting,anASneedsagloballyuniqueAS16-bitintegernumberCurrently,thereareabout11,000registeredASsinInternet(andgrowing)StubAS,whichisthemostcommontype,doesnotneedanASnumbersincetheprefixesareplacedattheprovider’sroutingtableTransitASneedsanASnumberRequestanASnumberfromtheARIN,RIPEandAPNIC《通信網(wǎng)理論基礎(chǔ)》(2)InterandIntraDomainRoutingRRRRRRRRASAASBASCIGPEGPIGPIGPInteriorGatewayProtocol(IGP):routingwithinASRIP,OSPFExteriorGatewayProtocol(EGP):routingbetweenAS’sBGPv4BorderGatewaysperformIGP&EGProuting《通信網(wǎng)理論基礎(chǔ)》(2)OutlineBasicRoutingRoutingInformationProtocol(RIP)OpenShortestPathFirst(OSPF)BorderGatewayProtocol(BGP)《通信網(wǎng)理論基礎(chǔ)》(2)RFC1058RIPbasedonrouted,“routed”,distributedinBSDUNIXUsesthedistance-vectoralgorithmRunsontopofUDP,portnumber520Metric:numberofhopsMaxlimitedto15suitableforsmallnetworks(localareaenvironments)valueof16isreservedtorepresentinfinitysmallnumberlimitsthecount-to-infinityproblemRoutingInformationProtocol(RIP)《通信網(wǎng)理論基礎(chǔ)》(2)RIPOperationRoutersendsupdatemessagetoneighborsevery30secArouterexpectstoreceiveanupdatemessagefromeachofitsneighborswithin180secondsintheworstcaseIfrouterdoesnotreceiveupdatemessagefromneighborXwithinthislimit,itassumesthelinktoXhasfailedandsetsthecorrespondingminimumcostto16(infinity)Usessplithorizonwithpoisonedreverse

Convergencespeededupbytriggeredupdatesneighborsnotifiedimmediatelyofchangesindistancevectortable《通信網(wǎng)理論基礎(chǔ)》(2)RIPProtocolRoutersrunRIPinactivemode(advertisedistancevectortables)HostscanrunRIPinpassivemode(updatedistancevectortables,butdonotadvertise)RIPdatagramsbroadcastoverLANs&specificallyaddressedonpt-ptormulti-accessnon-broadcastnetsTwoRIPpackettypes:requesttoaskneighborfordistancevectortableresponsetoadvertisedistancevectortableperiodically;inresponsetorequest;triggered《通信網(wǎng)理論基礎(chǔ)》(2)CommandVersion

ZeroAddressfamilyidentifierZeroIPaddressZeroZeroMetric081631...RIPMessageFormatRequest/Response1/22forIPRIPentryUpto25RIPentriespermessage《通信網(wǎng)理論基礎(chǔ)》(2)Command:requestorresponseVersion:v1orv2Oneormoreof:AddressFamily:2forIPIPAddress:networkorhostdestinationMetric:numberofhopstodestinationDoesnothaveaccesstosubnetmaskinformationCannotworkwithvariable-lengthsubnetmasksRIPv2(RFC2453):Subnetmask,nexthop,routingdomaincanworkwithCIDRstillusesmaxcostof16RIPMessageFormat《通信網(wǎng)理論基礎(chǔ)》(2)OutlineBasicRoutingRoutingInformationProtocol(RIP)OpenShortestPathFirst(OSPF)BorderGatewayProtocol(BGP)《通信網(wǎng)理論基礎(chǔ)》(2)UsedinOSPFtodistributelinkstate(LS)informationForwardincomingpackettoallportsexceptwherepacketcameinPacketeventuallyreachesdestinationaslongasthereisapathbetweenthesourceanddestinationGeneratesexponentialnumberofpackettransmissionsApproachestolimit#oftransmissions:UseaTTLateachpacket;won’tfloodifTTLisreachedEachrouteraddsitsidentifiertoheaderofpacketbeforeitfloodsthepacket;won’tfloodifitsidentifierisdetectedEachpacketfromagivensourceisidentifiedwithauniquesequencenumber;won’tfloodifsequencenumberissameFlooding《通信網(wǎng)理論基礎(chǔ)》(2)ExampleOSPFTopology10.5.1.110.5.1.310.5.1.510.5.1.210.5.1.410.5.1.6Atsteadystate:AllroutershavesameLSdatabaseKnowhowmanyroutersinnetworkInterfaces&linksbetweenroutersCostofeachlinkOccasionalHellomessages(10sec)&LSupdatessent(30min)《通信網(wǎng)理論基礎(chǔ)》(2)Toimprovescalability,ASmaybepartitionedintoareasAreaisidentifiedby32-bitAreaIDRouterinareaonlyknowscompletetopologyinsidearea&limitsthefloodingoflink-stateinformationtoareaAreaborderrouterssummarizeinfofromotherareasEachareamustbeconnectedtobackbonearea(0.0.0.0)DistributesroutinginfobetweenareasInternalrouterhasalllinkstonetswithinthesameareaAreaborderrouterhaslinkstomorethanoneareabackbonerouterhaslinksconnectedtothebackboneAutonomoussystemboundary(ASB)routerhaslinkstoanotherautonomoussystem.OSPFNetwork《通信網(wǎng)理論基礎(chǔ)》(2)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=networkR8R3R6OSPFAreas《通信網(wǎng)理論基礎(chǔ)》(2)Neighborrouters:tworoutersthathaveinterfacestoacommonnetworkNeighborsarediscovereddynamicallybyHelloprotocolEachneighborofarouterdescribedbyastatedown,attempt,init,2-way,Ex-Start,Exchange,Loading,FullAdjacentrouter:neighborroutersbecomeadjacentwhentheysynchronizetopologydatabasesbyexchangeoflinkstateinformationNeighborsonpoint-to-pointlinksbecomeadjacentRoutersonmultiaccessnetsbecomeadjacentonlytodesignated&backupdesignatedroutersReducessizeoftopologicaldatabase&routingtrafficNeighbor,Adjacent&DesignatedRouters《通信網(wǎng)理論基礎(chǔ)》(2)ReducesnumberofadjacenciesElectedbyeachmultiaccessnetworkafterneighbordiscoverybyhelloprotocolElectionbasedonpriority&idfieldsGenerateslinkadvertisementsthatlistroutersattachedtoamulti-accessnetworkFormsadjacencieswithroutersonmulti-accessnetworkBackuppreparedtotakeoverifdesignatedrouterfailsDesignatedRouters《通信網(wǎng)理論基礎(chǔ)》(2)Linkstateinfoexchangedbyadjacentrouterstoallowareatopologydatabasestobemaintainedinter-area&inter-ASroutestobeadvertisedRouterlinkad:generatedbyallOSPFroutersstateofrouterlinkswithinarea;floodedwithinareaonlyNetlinkad:generatedbythedesignatedrouter

listsroutersconnectedtonet:floodedwithinareaonlySummarylinkad:generatedbyareaborderrouters1.routestodestinotherareas;2.routestoASBroutersASexternallinkad:generatedbyASBroutersdescribesroutestodestinationsoutsidetheOSPFnetfloodedinallareasintheOSPFnetLinkStateAdvertisements《通信網(wǎng)理論基礎(chǔ)》(2)OSPFpacketstransmitteddirectlyonIPdatagrams;ProtocolID89TOS0,IPprecedencefieldsettointernetworkcontroltogetprecedenceovernormaltrafficOSPFpacketssenttomulticastaddress224.0.0.5(allSPFRoutersonpt-2-ptandbroadcastnets)OSPFpacketssentonspecificIPaddressesonnon-broadcastnetsFiveOSPFpackettypes:HelloDatabasedescriptionLinkstaterequest;Linkstateupdate;LinkstateackOSPFProtocol《通信網(wǎng)理論基礎(chǔ)》(2)OSPFHeaderType:Hello,Databasedescription,Linkstaterequest,Linkstateupdate,LinkstateacknowledgementsVersionTypePacketlengthRouterIDAreaIDChecksumAuthenticationtypeAuthenticationAuthentication081631OSPFcommonheaderOSPFpacketbodyData《通信網(wǎng)理論基礎(chǔ)》(2)OSPFStagesDiscoverneighborsbysendingHellopackets(every10sec)anddesignatedrouterelectedinmultiaccessnetworksAdjacenciesareestablished&linkstatedatabasesaresynchronizedLinkstateinformationispropagated&routingtablesarecalculatedWeelaborateonOSPFstagesinfollowing《通信網(wǎng)理論基礎(chǔ)》(2)Stage1:OSPFHelloPacketHellointerval:numberofsecondsbetweenHellopacketsPriority:usedtoelectdesignatedrouter&backupDeadinterval:#secbeforedeclaringanon-respondingneighbordown.Neighbor:theRouterIDofeachneighborfromwhomHellopacketshaverecentlybeenreceivedSendHellopacketstoestablish&maintainneighborrelationshipNetworkmaskHellointervalOptionsPriority0162431DeadintervalDesignatedrouterBackupdesignatedrouterNeighbor1Neighborn...《通信網(wǎng)理論基礎(chǔ)》(2)Stage2:OSPFDatabaseDescriptionInitbit1ifpktisfirstinsequenceofdatabasedescriptionpacketsMorebit1iftherearemoredatabasedescriptionpacketstofollowMaster/Slavebitindicatesthattherouteristhemaster.Linkstatead(LSA)headerdescribesstateofrouterornetwork;containsinfotouniquelyidentifyentryinLSA(type,ID,andadvertisingrouter).CanhavemultipleLSAheadersOnceneighborroutersbecomeadjacent,theyexchangedatabasedescriptionpacketstosynchronizetheirlink-statedatabases.《通信網(wǎng)理論基礎(chǔ)》(2)LSAHeaderLStype:RouterLSAsgeneratedbyallOSPFrouters;NetworkLSAsgeneratedbydesignatedrouters;SummaryLSAsbyareaborderrouters;AS-externalLSAsbyASBRsLSid:identifiespieceofroutingdomainbeingdescribedbyLSALSSeq.Number:numbersLSAstodetectold/duplicateLSAsLSchecksum:coverscontentsofLSAexceptlinkstateageLink-stateageOptionsLin