畢業(yè)論文——快速路由迭代方法的實現(xiàn)

1、快速路由迭代方法的實現(xiàn)快速路由迭代方法的實現(xiàn)摘要：要：在計算機網(wǎng)絡(luò)中每個路由項均必須有其對應(yīng)的下一跳地址，對于普通的路由來說，其下一跳地址在路由器直連的網(wǎng)段內(nèi)；對于需要迭代的路由，其下一跳不在路由器的直連網(wǎng)段內(nèi)。在轉(zhuǎn)發(fā)時，必須將此非直連下一跳地址做一次或多次迭代處理，以找出一個直連的下一跳地址，從而進行二層尋址。迭代部分大多使用定時器迭代方式，此方法定時時間只能根據(jù)經(jīng)驗值來選擇，而迭代路由需要等待定時時間后才可能生效，效率低。本課題提出

2、一種快速路由迭代的實現(xiàn)方案，基于實時迭代，抽象出鄰居信息并加以復(fù)用，迭代效率得以大幅提升。關(guān)鍵詞：關(guān)鍵詞：路由迭代；靜態(tài)路由協(xié)議；邊界網(wǎng)關(guān)協(xié)議；鄰居Abstract:Incomputerwkseachrouteentrymusthavethecrespondingnexthopaddress.Fdinaryrouteitsnexthopaddressisintherouterdirectlyconnectedwksegment.Faro

3、uterequiringrecursionitsnexthopaddressisnotdirectlyconnected.DuringroutefwardingthisnondirectlyconnectednexthopaddressmustberecursionprocessedonceseveraltimestofindoutadirectlyconnectednexthopaddresstoenableLayer2pathsea

4、rching.Mostofrecursiveroutingusingthetimertimecanonlybeedaccdingtoexperiencetherecursiveroutingmayneedtowaituntiltimertimetotakeeffectwhichhaslowefficiency.Thispaperproposesafastrealtimebasedrecursiveroutingimplementatio

5、n.Itabstractreuseneighbinfmationrecursiveefficiencycanbegreatlyimproved.Keywds:RecursiveRoutingStaticRoutingProtocolBGPNeighbour路由器在Inter中起著舉足輕重的作用，它是構(gòu)成IP網(wǎng)絡(luò)的核心，最基本的作用就是連接不同類型的網(wǎng)絡(luò)，可以智能選擇最佳的信息傳送線路。路由迭代是路由系統(tǒng)中一個重要的功能。對于BGP路由和

6、靜態(tài)路由而言，其所攜帶的下一跳信息可能并不是直接可達(dá)，需要找到到達(dá)下一跳的直連出口。路由迭代的過程就是通過路由的下一跳信息來找到直連出口的過程。傳統(tǒng)路由迭代方法是定時器路由迭代。定時器路由迭代總體來說就是按一定的時間間隔，循環(huán)遍歷需要迭代的路由進行重新迭代。定時器時間間隔根據(jù)經(jīng)驗設(shè)置，也可根據(jù)需要修改定時器時間。定時器路由迭代對所有迭代節(jié)點進行重新操作。過大和過小的時間片對于CPU的影響都很大，效率低。隨著網(wǎng)絡(luò)的大規(guī)模發(fā)展，路由器的數(shù)量

7、成倍的增長，網(wǎng)絡(luò)中每增加一臺路由器，隨之而來就會帶來IP地址、路由協(xié)議鄰居數(shù)量、路由表條目的增加等問題。而定時器每次處理的迭代路由個數(shù)是有限的，以免阻塞太久。迭代路由表項過大會導(dǎo)致每次完成一次完整遍歷的周期較長，迭代延時更為明顯。為了解決上述問題，本文實現(xiàn)一種快速路由迭代的方法。圖2路由管理模塊2系統(tǒng)關(guān)鍵技術(shù)系統(tǒng)關(guān)鍵技術(shù)2.1兩段式存儲兩段式存儲NBR（Neighbour），即鄰居?？梢宰鳛榱髁肯乱徽镜奶摂M節(jié)點，也可以是一個接口，也可以

8、是一個可表達(dá)的下一跳節(jié)點，或者某個接口出發(fā)可達(dá)的下一跳節(jié)點。NBR包含了下一條信息，如果是迭代節(jié)點，則還會記錄保存路由迭代的結(jié)果，包括依賴路由的概要信息、迭代路徑、迭代深度等。每個NBR都有唯一的ID，占用4個字節(jié)，其構(gòu)成如圖3。0123AddID4567ProID012345670123456701234567Index圖3鄰居IDAddID表示地址簇，區(qū)分IPV4和IPV6；ProID表示協(xié)議；Index表示NBR的索引，24bit

9、s，即最大支持16M個NBR；數(shù)據(jù)結(jié)構(gòu)在路由快速迭代的實現(xiàn)中至關(guān)重要，對路由表采用查找（Radix樹）和存儲（DB）分離的方式設(shè)計。Radix樹提高了的路由表項的查找速度，DB提高內(nèi)存分配的速度以及安全性。為了提高效率，節(jié)約內(nèi)存，實現(xiàn)IPV4IPV6地址簇復(fù)用，路由表采用完全二段式的組織方式（下一跳和前綴分離存儲）。下一跳信息采用復(fù)用原則單獨維護，路有前綴根據(jù)地址簇存儲到對應(yīng)的radix樹上。復(fù)用的邏輯關(guān)系如圖4所示，其中，每個鄰居的信

10、息包含了引用了該鄰居的前綴的各數(shù)。...Prefix1目的地址1Prefix2目的地址2Prefix1W目的地址1WNBR下一跳地址Count=1W依賴路由圖4鄰居復(fù)用關(guān)系從真實的組網(wǎng)應(yīng)用來看，路由鄰居個數(shù)是非常有限的，而充分利用復(fù)用鄰居是提高路由表的維護和路由迭代效率的關(guān)鍵。靜態(tài)路由協(xié)議配置并且優(yōu)選后的路由以及動態(tài)路由協(xié)議學(xué)習(xí)到的路由都統(tǒng)一發(fā)給路由管理進行優(yōu)選。優(yōu)選后每個路由器中都至少保存著一張路由表和一張路由轉(zhuǎn)發(fā)表，路由器決策路由的

11、關(guān)鍵是路由表，而路由表正是由路由管理維護的。每臺路由器中都保存著一張由本地管理的路由表，同時各個路由協(xié)議也維護著自己的一張自己協(xié)議的路由表。鄰居的組織方式為Radix樹，如圖5，其外節(jié)點存儲路由地址、掩碼以及其他信息。此處的其他信息有整條路由的詳細(xì)信息的指針以及所有此相同前綴的鏈表的指針。只存儲路由詳細(xì)信息的鏈表是為了達(dá)到存儲與查找分離的目的，因為很多應(yīng)用場合是需要查詢或者之需要用到前綴而不用下一跳。存儲相同前綴的鏈表的指針也是為了同樣