工程碩士班《通信網(wǎng)理論基礎(chǔ)》

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

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

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

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

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

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

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

在簡(jiǎn)單圖中,簡(jiǎn)單路徑可以由頂點(diǎn)序列來定義每個(gè)頂點(diǎn)與序列中在其前面和后面的頂點(diǎn)相鄰序列中沒有重復(fù)的頂點(diǎn)6.簡(jiǎn)單路徑(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條(其余的請(qǐng)自行列出)7.簡(jiǎn)單圖(2)兩頂點(diǎn)間的所有路徑中有一條最短路徑,如:V1,V3,V6頂點(diǎn)間的距離是所有路徑中邊數(shù)最少的路徑的邊的數(shù)目回路是起于和止于同一頂點(diǎn)的路徑例如:.V1,V3,V4,V18.有向圖邊有方向性的圖有向圖G(V,E)的邊由一對(duì)頂點(diǎn)的有序組合來定義代表邊的線段用箭頭表示其方向允許存在平行邊,只要它們的方向相反便于用圖表示通信網(wǎng)絡(luò)每條有向邊表達(dá)一個(gè)方向上的數(shù)據(jù)流仍然可用鄰接矩陣表示除非每對(duì)相鄰的頂點(diǎn)用平行邊連接,否則鄰接矩陣是不對(duì)稱的9.加權(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)值路徑長(zhǎng)度是權(quán)值之和最短距離路徑不一定是長(zhǎng)度最短路徑(見下面兩張PPT)10.加權(quán)圖與鄰接矩陣11.V1

至V6

的路徑距離和路徑長(zhǎng)度路徑 距離長(zhǎng)度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.樹樹是圖的子集以下幾項(xiàng)定義是等效的:*樹是一種簡(jiǎn)單圖,頂點(diǎn)i

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

樹的例15.子圖從圖G中選擇一些邊和頂點(diǎn)構(gòu)成G的子圖每條被選上的邊的兩個(gè)關(guān)聯(lián)頂點(diǎn)必須同時(shí)選上圖G’(E’,V’)是圖G(E,V)的子圖,如果:V’V,

E’E

并且對(duì)每一條E’中的邊e’.如果e’

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

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

是樹

包含G的所有頂點(diǎn)從圖G中刪去一些邊,使所有的回路不復(fù)存在,但保持圖的連通性:圖G的生成樹通常并不唯一17.生成樹的例子18.生成樹的“先廣搜索”算法將頂點(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)被處理完畢19.例選擇頂點(diǎn)順序如:V1,V2,V3,V4,V5,V6選擇“根”例如V1現(xiàn)在樹T只包含一個(gè)頂點(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ù)處理過程,得到第三層….…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算法可以得到從根頂點(diǎn)s到所有其他頂點(diǎn)的最短距離路徑和距離δ(s,v)

任何從s

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

N=網(wǎng)絡(luò)頂點(diǎn)的集合s=源頂點(diǎn)(起始點(diǎn))T=到目前為止算法已經(jīng)用到的頂點(diǎn)的臨時(shí)集合Tree=T中頂點(diǎn)組成的生成樹,它包括從s到T中每個(gè)頂點(diǎn)的最小代價(jià)路徑上的邊w(i,j)=從頂點(diǎn)i到頂點(diǎn)j的鏈路代價(jià),w(i,i)=0w(i,j)=ifi,j不直接連接w(i,j)0ifi,j直接連接L(n)=當(dāng)前知道的從s到n的最小代價(jià)路徑的代價(jià)cost運(yùn)算結(jié)束是它就是從s到n的最小代價(jià)路徑的代價(jià)32.Dijkstra算法(2)–步驟初始化T=Tree={s}–臨時(shí)頂點(diǎn)集合中暫時(shí)只含源頂點(diǎn)L(n)=w(s,n)forns;到鄰點(diǎn)的初始路徑代價(jià)就是鏈路代價(jià)取下一個(gè)頂點(diǎn)找xT使L(x)=minL(j),jT將x加入到T和Tree中將關(guān)聯(lián)x,且使L(x)成為最小代價(jià)的邊加入到Tree中它是路徑的最后一跳更新最小代價(jià)路徑L(n)=min[L(n),L(x)+w(x,n)]nT如果后一項(xiàng)最小,從s到n的路徑就是從s到x的路徑與從x到n的邊的連接33.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)間直接相連鏈路的代價(jià)因而需要與所有其他各點(diǎn)交換路由信息某點(diǎn)（s)已知網(wǎng)絡(luò)中其他各點(diǎn)到其鄰點(diǎn)的鏈路的代價(jià)值w(x,n),計(jì)算S到其他各點(diǎn)的最短路徑34.Dijkstra’s算法(3)–說明當(dāng)所有頂點(diǎn)都加入到T以后,算法結(jié)束需要|V|次迭代結(jié)束時(shí)L(x)是s到x的最小代價(jià)路徑的代價(jià)值Tree是原圖的一顆最小生成樹定義了從s到其他頂點(diǎn)的最小代價(jià)路徑每次迭代有一個(gè)新的頂點(diǎn)加入到T中,運(yùn)行時(shí)間是|V|2量級(jí)35.Dijkstra算法用于例圖36.Bellman-Ford算法(1)–定義

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

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

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

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

算法的運(yùn)算結(jié)果42.比較所需要的信息

–Bellman-Ford算法頂點(diǎn)n處的計(jì)算需要知道到所有鄰接點(diǎn)的鏈路的代價(jià),以及從源點(diǎn)到這些點(diǎn)的路徑的總代價(jià)e每個(gè)頂點(diǎn)需要維持一個(gè)到網(wǎng)絡(luò)中所有其他頂點(diǎn)的路徑及其代價(jià)的表與其直接鄰接頂點(diǎn)交換上述信息每個(gè)頂點(diǎn)都用Bellman-Ford算法步驟2中的表達(dá)式更新其路徑與代價(jià)表43.比較兩種算法所需要的信息-------------Dijkstra算法步驟3要求每個(gè)頂點(diǎn)知道網(wǎng)絡(luò)拓?fù)涞耐暾畔?因而:必須知道網(wǎng)絡(luò)中所有鏈路的代價(jià)值每個(gè)頂點(diǎn)必須與所有其他頂點(diǎn)交換信息究竟哪個(gè)算法好,需要考慮算法的運(yùn)行時(shí)間等其他因素44.其他事項(xiàng)當(dāng)網(wǎng)絡(luò)拓?fù)浜玩溌反鷥r(jià)處于準(zhǔn)靜態(tài)時(shí),兩種算法都收斂給出相同的結(jié)果如果鏈路代價(jià)變化,算法會(huì)企圖跟上這種變化如果鏈路代價(jià)與通信流量有關(guān),而后者又與路由選擇有關(guān),則:存在反饋可能產(chǎn)生不穩(wěn)定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