1、流水技術用于提升路由器性能的分析與研究學生： （指導老師： ）（淮南師范學院計算機學院）摘要：隨著互聯(lián)網(wǎng)技術的發(fā)展和各種類型的網(wǎng)絡應用的出現(xiàn)，使得網(wǎng)絡的服務質(zhì)量受到了巨大的挑戰(zhàn)和關注，許多研究人員發(fā)現(xiàn)單純的加大帶寬并不能解決這個問題。由此觀之，路由設備是網(wǎng)絡首要連接器件。它的性能將即刻反應網(wǎng)絡服務質(zhì)量。本文是在流水技術方面做了探究的。其最重要的目標是來增加路由器的性能。在路由器的高速轉(zhuǎn)發(fā)過程中，著重研究流水技術的應用。關于轉(zhuǎn)發(fā)引擎在速度進展方面，它對其進行了透徹的研究。提升轉(zhuǎn)發(fā)引擎必須面對困境。通過應用多種方法（多種辦法里包括TCAM等方法），為高速轉(zhuǎn)發(fā)引擎指出了新的思想流水線機制的高速轉(zhuǎn)發(fā)引

2、擎。這種方法能增多路由器的性能。從而能夠解決網(wǎng)絡服務質(zhì)量的問題，讓路由器不再成為是制約網(wǎng)絡發(fā)展的關口和約束。關鍵字：路由器 網(wǎng)絡服務質(zhì)量 高速轉(zhuǎn)發(fā)引擎 流水技術 并行流水技術 Water technology is used to improve the performance of router analysis and researchStudent: (Faculty Adviser： )(Huainan normal university computer college)Abstract: With the advent of Internet technology and vari

3、ous types of network applications, so network quality of service has been a huge challenge and concern, many researchers have found a simple increase bandwidth does not solve this problem. From this perspective, the routing device is the primary network connection devices. Its performance will be im

4、mediate reaction network quality of service. This article is made inquiry in water technology. Its most important goal is to increase the performance of the router. In the high-speed router forwarding process, focusing on application of water technologies. About forwarding engine speed progress, it

5、was carried out thorough research. Enhance the forwarding engine must face difficulties. By using a variety of methods (a variety of approaches in other methods including TCAM), high-speed forwarding engine pointed out new ideas - pipelining of high-speed forwarding engine. This method can increase

6、the performance of the router. It is possible to solve the problem of network quality of service, so that the router is no longer a barrier restricting network development and constraints.Keywords: The router Network quality of service High-speed forwarding engine Water technology Parallel flow tech

7、nology前言路由器是整個互聯(lián)網(wǎng)設備中的樞紐，它是相互之間有差別的網(wǎng)絡進行彼此聯(lián)接的核心，路由器是Internet的全部框架的組成者，它的處理速度在網(wǎng)絡快速發(fā)展中是一大制約因素。因此，在未來整個因特網(wǎng)研究領域，路由器技術處于并且將長時間的出去要害地位，它的發(fā)展過程也將成為整個因特網(wǎng)研究的一個重要寫照?，F(xiàn)今網(wǎng)絡發(fā)展速度，不可小觀。隨著網(wǎng)絡快速成長，它在路由器的性能方面，提出了愈來愈高的要求。為了適合于下一代網(wǎng)絡的高速度的需求，路由器正在被挑釁。為了對路由器的性能加以提升，許多先行者會有很多在路由器上研究。對于路由器高速轉(zhuǎn)發(fā)技術，他們是研究的方向之一。高速轉(zhuǎn)發(fā)技術中引入流水線技術。這是現(xiàn)今提升路

8、由器的一個重要探究方向。流水線技術可謂是很好一種方法。它將串行處理轉(zhuǎn)變?yōu)椴⑿刑幚?。簡單在運行操作期間，多條指令一起執(zhí)行。流水技術能夠提升指令的運行功效。其利用的方法是對各個部件的使用來兌現(xiàn)的。路由器是整個網(wǎng)絡重要組成部分，流水技術在路由器中應用也將在提升路由器性能發(fā)揮巨大作用。本文對路由器的工作原理、轉(zhuǎn)發(fā)過程、體系結(jié)構等理論進行了簡要的概述，對于流水線進行了基本概念的敘述和有關問題的說明，并且流水技術在路由器中的應用。1 路由器的概述1.1路由器產(chǎn)生網(wǎng)上的最重要的設備是路由器。它用于連接不同的網(wǎng)絡的。傳輸控制協(xié)議/互聯(lián)網(wǎng)絡協(xié)議(Transmission Control Protocol/Int

9、ernet Protocol，簡稱TCP/IP)是在美國國防部ARAPNET基礎上發(fā)展過來，時間為上世紀70年代。美國軍方期望能夠在它幫助下，使得不同廣域網(wǎng)和局域網(wǎng)能夠互相通信。讓路由器稱為一種不能夠被交換機所替換的設備，這樣可以確保網(wǎng)絡即使在遭受戰(zhàn)爭打擊后也能夠相互連接通信。在這種歷史背景下，路由器的產(chǎn)生就稱為了必然結(jié)果。1.11路由器基本結(jié)構和發(fā)展歷程網(wǎng)絡接口路由引擎路由表轉(zhuǎn)發(fā)引擎內(nèi)部交換網(wǎng)絡接口控制路徑路由更新控制路徑路由查找數(shù)據(jù)路徑圖1路由器基本結(jié)構圖據(jù)圖1，路由器的基礎構造能夠從圖1中看出，網(wǎng)絡接口、引擎模塊（包括轉(zhuǎn)發(fā)和路由的引擎）和內(nèi)部互換模塊這四個功能模塊構造了路由設備。從圖1中

10、可以看到物理鏈路和網(wǎng)絡接口。它們是直接連接的。處理互相對應的物理傳輸數(shù)據(jù)報文模塊、將網(wǎng)絡報文接收和發(fā)送任務完成，都是有網(wǎng)絡接口實現(xiàn)的。高速路由查找需要一種特種設備。路由器轉(zhuǎn)發(fā)引擎是其所需的。轉(zhuǎn)發(fā)引擎是具有數(shù)據(jù)包發(fā)送途徑?jīng)Q策的任務。路由設備由內(nèi)部處理模塊實現(xiàn)，其對高層協(xié)議操作。路由引擎有很多工作。它對高層協(xié)議進行操作，特別是路由協(xié)議。整個路由設備穩(wěn)定工作也是由路由器來負責。整個路由器穩(wěn)工作包括維護各個網(wǎng)絡之間狀態(tài)的一致性，監(jiān)控系統(tǒng)狀態(tài)等工作。這些工作任務都是經(jīng)由路由設備引擎來實現(xiàn)的。路由引擎模塊和網(wǎng)絡接口連接。它們之間進行的數(shù)據(jù)傳輸。其傳輸過程中提供高速數(shù)據(jù)路徑。這是內(nèi)部交換模塊的任務。另外，從

11、圖1中能夠看出路由設備提供哪一種路徑是依據(jù)網(wǎng)絡報文來確定。數(shù)據(jù)路徑處理的目標地址是需要轉(zhuǎn)發(fā)網(wǎng)絡報文，路由器的整體性能都受到它的影響。固然處理的目標地址（在控制路徑上的）不處于路由器的要害途徑，然而它在路由器報文轉(zhuǎn)發(fā)時提供了準確訊息。身為互聯(lián)網(wǎng)關卡的路由器現(xiàn)在正向著運行速度不斷增加、服務在質(zhì)量的更好以及更便于管理的方向發(fā)展。隨著網(wǎng)絡速度的不段發(fā)展，路由器也在幾個方面快速發(fā)展著，這個幾個方面主要是：引擎模塊劃分為路由引擎和轉(zhuǎn)發(fā)引擎，它們之間相互獨立、在路由表上，對全局路由表和局部轉(zhuǎn)發(fā)表的劃分、硬件設備上，我在對于網(wǎng)絡之間互連的協(xié)議（Internet Protocol，簡稱IP）的報文，要實現(xiàn)報頭的

12、快速處理、對于路徑，要進行搜索和發(fā)送、轉(zhuǎn)變中央處理器為中央處理控制器。將接口卡模式轉(zhuǎn)變?yōu)樵S多個單元。這個單元是分布式的接口，這樣，新的方式將上述的方式替換、提高數(shù)據(jù)通信速度使用的交換結(jié)構。路由器在成長的歷程中，走過了兩個過渡階段。一個是歷經(jīng)了單個處理器階段向并行處理器的過渡階段。另外一個由總線的同享向結(jié)構的交換的過渡階段。目前路由器又提出在大規(guī)模并行工作處理技術的結(jié)構體系基礎上，路由器性能在路由器結(jié)構體系的發(fā)展下不斷提高。1.12路由器研究現(xiàn)狀現(xiàn)有的高性能路由器技術基快速發(fā)展。高端路由器的成長方向和探究方向基本上都關注在四個方面：首先是硬件將在并行工作處理技能中廣泛采用的；第二方面是協(xié)議處理將

13、專注于分布式處理技術；第三方面是在網(wǎng)絡骨干節(jié)點多粒度路由提供流量控制和管理技術。最后的是路由協(xié)議在算法的改進。而且智能路由技術（這種技術有約束條件）將基于距離準則替代。思科，Juniper，華為，上海貝爾艾爾卡特、中興等企業(yè)是目前的高水準路由器的來源。主流的高端設備都有很強的能力。例如，高于360G的交換能力、G比特每秒單端口速率等。許多制造商走的是中低端路由器路線。在上文中提到的制造商之外，比威，神州數(shù)碼，邁普等制造商也從事制作中低端路由器。具有強大的適用范圍中低端設備，在定位和功能形態(tài)上都各有不同，差距很大，這里也不再對它們詳細闡述了。1.2 路由器體系結(jié)構（1） 從上文所述的路由器的發(fā)展

14、歷程，我們可以看出路由器體系機構的變化。一般路由器的結(jié)構體系可以分為三種類型：在同享總線方面，單個處理設備的體系結(jié)構和多個處理設備結(jié)構以及互換機制的多個處理設備體系結(jié)構。下面對于上文中提到體系結(jié)構進行詳細闡述（2） 單個處理總線體系結(jié)構CPUmemorybusLineCardLineCardLineCard圖2 單個處理器結(jié)構體系圖2呈現(xiàn)的是經(jīng)典的路由器結(jié)構系統(tǒng)。它是基于總線的路由器結(jié)構體制。整個數(shù)據(jù)報文轉(zhuǎn)發(fā)過程是：數(shù)據(jù)報文首先抵達接口卡，然后將報文發(fā)送給中央處理器（Central Processing Unit，簡稱CPU），CPU對路由表進行搜索，然后根據(jù)搜索結(jié)果做出下一步的地址的選擇，最

15、后通過其他的接口卡將報文轉(zhuǎn)發(fā)出去。從上述報文轉(zhuǎn)發(fā)過程中，可以看要通過兩次才能將數(shù)據(jù)轉(zhuǎn)發(fā)出去。這成為了制約整個系統(tǒng)因素。在路由器的傳統(tǒng)總線結(jié)構中央處理器是要完成很多工作的。例如包的轉(zhuǎn)發(fā)、路由協(xié)議等。整個系統(tǒng)都依賴于路由器的CPU，從而可以得出這種系統(tǒng)的缺點有：1）路由設備的報文都由中央處理設備來進行執(zhí)行操作，中央處理設備成為制約因素。2）報文轉(zhuǎn)發(fā)涉及存儲器訪問，CPU處理不能成線性處理，訪問存儲器時間成為主要的制約者；3）總線結(jié)構的交換方式對高速轉(zhuǎn)發(fā)無法支持。（3） 多個處理共享總線體系結(jié)構CPUmemoryLine cardProcessMemoryLine cardProcessMemory

16、Line cardProcessmemoryProcessmemoryProcessmemoryProcessmemoryCPU MemoryLine cardLine cardLine card圖3 多個處理共享總線結(jié)構這種體系結(jié)構是在傳統(tǒng)的路由器結(jié)構中的改進，其主要的理論是用多個處理部件來分解處理報文轉(zhuǎn)發(fā)。如圖3所展示的一樣，圖中有在多處理共享總線體系結(jié)構有存在兩種。其分別為分布體系結(jié)構和并行式體系結(jié)構。其中，分布式體系結(jié)構的工作原理是一個線卡上報文要由對應其線卡的處理器來進行操作。另一種的原理是將相互獨立的線卡和轉(zhuǎn)發(fā)處理器在共享總線的上連接。并行體系結(jié)構已經(jīng)初步有了流水線操作的模式，它在

17、處理過程同時對數(shù)據(jù)報文進行路由查找和數(shù)據(jù)緩存的操作，完成報文的更新和發(fā)送報文數(shù)據(jù)部分。從總線帶寬上看，這種方法節(jié)約了花費。（4） 多個處理互換機構結(jié)構體系LineCardLineCardLineCardForwordEngineForwordEngineForwordEngineCPU memoryLineCardLineCardLineCardCPU memoryForwordEngineForwordEngineForwordEngine圖4 多處理互換機構結(jié)構體系這種體系結(jié)構在第二代路由器的基礎上，使用了交換機構方式作為背板傳輸?shù)姆绞?，而且使用集成電路（Application Speci

18、fic Integrated Circuit,簡稱ASIC）替換了通用CPU，使得路由器的性能大大提高。通過對路由體系研究與分析，我們可以看出傳統(tǒng)路由工作模式依然是串行模式，路由器的轉(zhuǎn)發(fā)性能的不到提高，因此，本文中將引入流水線機制，在路由轉(zhuǎn)發(fā)的過程中改變傳統(tǒng)路由器的工作模式，使得路由器作業(yè)流水化、并行化，從而提高路由器性能。本次論文將論文的第二部分和第三部分對流水技術和如何使用流水技術提升路由器性能做詳細闡述。1.3 路由器的工作原理在開放式系統(tǒng)互聯(lián)（Open System Interconnection，簡稱OSI）七層協(xié)議中，它位于網(wǎng)絡層，并且在其中工作。每當一個網(wǎng)絡層發(fā)送的數(shù)據(jù)報，路由器

19、對其接收和做直線前進，給自己連接到網(wǎng)絡或轉(zhuǎn)發(fā)到另一個路由器或丟棄該數(shù)據(jù)報的決定。路由器使用的源地址和目的地址的網(wǎng)絡層的信息進行轉(zhuǎn)發(fā)的信息。據(jù)此確定將信息轉(zhuǎn)發(fā)到哪個網(wǎng)絡。假如同一個網(wǎng)絡中包含了源網(wǎng)絡和目的網(wǎng)絡號，則傳遞到該網(wǎng)絡所指定主機。一個信息包在抵達路由器以后立即進入隊列，然后路由器遵從以下順序進行處理：獲取數(shù)據(jù)信息包的目標地址，對路由表進行檢查，若是抵達目標地有超過一條以上途徑，那么路由設備在對選擇道路途徑的中，他會選擇最佳路徑，路由器的選擇時除了上面說的，在互聯(lián)網(wǎng)上的路由器的延長時間，分組長度和指定的服務類型等因素來綜合分析的數(shù)據(jù)集，然后根據(jù)這些做出決定，在道路途徑上選擇最優(yōu)的一個的決定

20、。下面對路由設備對于路由的選擇算法說明（以IP路由器為例）：保存目的地網(wǎng)絡號碼于路由表中，當路由器接收到IP數(shù)據(jù)信息報文之時，首先找到IP數(shù)據(jù)信息報文的目標站點的地址（即IP地址），由IP路由設備將其獲取，計算出目的站點的網(wǎng)絡號（網(wǎng)絡號是屬于目標站點所在的網(wǎng)），然后依據(jù)計算出的網(wǎng)絡號查找路由，最后決定該IP數(shù)據(jù)報要通過哪個接口發(fā)送出去。在TCP/IP協(xié)議控制下，數(shù)據(jù)包到達路由器后，對于數(shù)據(jù)包，路由器將進行拆除報頭（報頭屬于數(shù)據(jù)鏈路層）操作，查找到目標地址（其屬于網(wǎng)絡層）。當目的地址被獲取。路由器就會對路由表進行查看。通過路由表搜索到目標地址。最后獲取目標地址的路由。整個數(shù)據(jù)包的轉(zhuǎn)發(fā)過程為：第一

21、：數(shù)據(jù)包的報頭先進入路由器的入站口，通過多路訪問控制(Multiple Access Control, 簡稱MAC)過程找到可用的硬件的目的地址，如若MAC過程中找到目的地址，就會使用循環(huán)冗余校驗（Cyclical Redundancy Check，簡稱CRC）來對數(shù)據(jù)信息包的幀來確認這個幀沒有被破壞。通過CRC校驗，拆包，丟棄該幀。在由路由設備的內(nèi)存中將數(shù)據(jù)信息包保存后結(jié)束。第二：路由器運行搜索的操作。這個操作在路由表中運行。其后獲取匹配地址（該地址為最長的數(shù)據(jù)信息包報頭的目標地址）。如若符合，該路由將由路由器為其搜索到下一跳的地址或者是直連的接口上（其中，若是存在一個直接連接的接口，它被指

22、向路由，我們可以就可以跳過下一步而沒有執(zhí)行遞歸查找）。反之，匹配不符，路由也未發(fā)現(xiàn)默認網(wǎng)關，數(shù)據(jù)包會被丟棄，并且會發(fā)送網(wǎng)絡控制信息協(xié)議（Internet Control Message Protocol，簡稱ICMP）不可達到的消息給原設備。第三：當下一跳地址被獲取，遞歸查找操作被路由器執(zhí)行。這么做的目的便于直連的接口（在路由器上），找到表項（位于流出接口的），然后把數(shù)據(jù)包轉(zhuǎn)發(fā)出去。如若遞歸操作被運行后未獲取到IP地址(在表項的上的），也沒有默許的網(wǎng)關，那么路由器會出現(xiàn)兩種操作：一是將該數(shù)據(jù)包扔掉，二是利用ICMP發(fā)消息給數(shù)據(jù)包源。第四：出站口緩沖器有自己的作用。它接收被交換的數(shù)據(jù)包。其交換過

23、程主要通過ARP技術實現(xiàn)。第五：路由器根據(jù)直連接口和下一跳的連接類型。將合適的數(shù)據(jù)鏈路幀封包裝入數(shù)據(jù)包。在傳輸線上有出站接口。其放置攜帶下一跳地址的幀（該幀屬于數(shù)據(jù)鏈路層）。在數(shù)據(jù)信息包到達目標地之前，這個包的轉(zhuǎn)而發(fā)送過程都要被路由設備控制運行。1.4路由器的基本功能和特點路由器有一個最重要的功能。它就是“路由”的作用。簡單的來說就是“方向?qū)Ш健惫τ?，基本上是用來對?shù)據(jù)信息包的轉(zhuǎn)而發(fā)送時為其指清楚方向的功能。若是詳細的劃分，路由器的“路由”作用可以區(qū)別為以下兩個方面：（1）路由選擇根據(jù)地址（由網(wǎng)絡層提供的），使用路由表為IP數(shù)據(jù)包選擇到達目標地的最好途徑，換句話說就是通過路由器的選擇算法選擇一

24、條最佳的途徑到目的地。為了目標的完成，每個路由設備都會建成并保護路由表，在路由表中，其包涵蓋了能夠被本地連接的所有的網(wǎng)絡。在路由表的基礎上路由設備查找數(shù)據(jù)信息包所要選取的最好的途徑。路由表中包括路由的有關信息。路由器利用這些信息轉(zhuǎn)發(fā)數(shù)據(jù)包使達到非直連遠程網(wǎng)絡。一條路由蘊含了目標網(wǎng)絡地址、掩碼、網(wǎng)關或者接口地址、路由開銷或度量等訊息。（2）存儲轉(zhuǎn)發(fā)路由設備首先讓自己的以連接端口獲取一個IP包，然后，在經(jīng)由路由設備另一個連接端口發(fā)送出去。如果我們想?yún)^(qū)分關于路由的算法是動態(tài)算法和靜態(tài)算法，我們可以通過網(wǎng)的拓撲結(jié)構和通信的應變能力來判斷。靜態(tài)路由算法又稱為非自適應路由選擇算法。其特征是更加簡潔，花費少

25、，結(jié)構簡單，但無法立即適應網(wǎng)絡的狀態(tài)的改變。動態(tài)路由算法又稱為自適應路由選擇算法，其優(yōu)點是迅速在網(wǎng)絡狀態(tài)的變化并做出相應的反應，缺點是更復雜的完成，成本也比較大。路由器的主要特點是：（1）路由器，不一樣的MAC協(xié)議，不一樣的傳輸介質(zhì)，不相同的拓撲結(jié)構和不一樣的網(wǎng)絡不同的傳輸速率是相互連接的，具有很強的異構網(wǎng)絡互聯(lián)能力。（2）路由器是一種設備。它的功能體現(xiàn)在存儲轉(zhuǎn)發(fā)上。它在相互連通的遠程網(wǎng)上，有著很強大的使用性。在遠程網(wǎng)上，它具有強大相互連接能力。它被較大范圍的使用在遠網(wǎng)和局域網(wǎng)之間互聯(lián)互接情況里。（3）在邏輯上相互不相同的的子網(wǎng)絡可以憑借路由器連接在一起，其中每個子網(wǎng)絡全部看一個單一的子網(wǎng)廣播

26、域，因此在子網(wǎng)網(wǎng)絡與子網(wǎng)路之間，廣播信息在路由器中不會流通。因此，路由器有這個能力。它可以去阻隔廣播信息。（4）路由器具備很多能力，例如流量控制、擁塞控制的能力，可以對異種速率網(wǎng)絡之間進行速度匹配，用來確保數(shù)據(jù)包可以準確地進行傳輸。（5）路由器忙碌于OSI的第三層。OSI第三層也就是網(wǎng)絡層。它是與網(wǎng)絡層的各種協(xié)議都有著緊密聯(lián)系。多種協(xié)議路由設備可以支撐許多不同種網(wǎng)絡層的協(xié)議（例如：IPX，DECnet，TCP / IP協(xié)議），數(shù)據(jù)包轉(zhuǎn)發(fā)在異種網(wǎng)絡的協(xié)議之間。（6）路由設備對于網(wǎng)絡層面的地址進行檢查，從而發(fā)送數(shù)據(jù)的分組（Packet）。當然，該該數(shù)據(jù)分組來自網(wǎng)絡層。出于這個原因，路由設備能夠根據(jù)

27、網(wǎng)絡協(xié)議地址來進行數(shù)據(jù)包的過濾,路由設備使用訪問控制列表(Access Control List,簡稱ACL)根據(jù)各種協(xié)議封包裝入的數(shù)據(jù)信息包并且對封包裝入過程加以掌控。同樣，TCP、UDP端口號也會被實施數(shù)據(jù)過濾。（7）首先對較大規(guī)模的網(wǎng)絡劃分為微小段化，然后將劃分為微小段后的網(wǎng)段運用路由設備互連在一起。這方法不僅達到在網(wǎng)絡上提高性能，提升網(wǎng)絡的帶寬的目標。另外，這種方法有利于管理網(wǎng)絡和維護網(wǎng)絡。其亦是一個網(wǎng)絡同享的方法通常是帶寬問題解決方案。（8）路由設備即可以在中、小規(guī)模分級集中網(wǎng)中進行運用。同樣適合在大規(guī)模、情況多變的互聯(lián)網(wǎng)絡環(huán)境。（9）路由器有很好的分離效果。它具體體現(xiàn)沖突域和廣播域

28、中。2 流水技術的研究2.1流水技術的基本概念2.1.1什么是流水線技術流水線（pipelining）是一種將串行工作的方式轉(zhuǎn)變?yōu)椴⑿泄ぷ鞯募夹g，在程序運行期間，若干條指令在時間上重疊進行并行操作的。關于計算機的系統(tǒng)結(jié)構性能上，流水線技術是一種十分好方法。它可以提高計算機系統(tǒng)性能。重復的過程，它將流程進行了重新規(guī)劃，把原本該是順序執(zhí)行的流程，重新劃分成相對獨立的流程，但在耗時上卻相當步驟，提高資源途徑等方法來，在時間方面或者資源方面，讓這些步驟之間相關性解除，這樣他們就可以實現(xiàn)并行到一定程度，從而達到優(yōu)化性能的目的。在最初的時，CPU的內(nèi)部結(jié)構中最先運用到流水線技術，它被分為兩種：一是部件級別

29、的流水，二是處理設備級別的流水。2.1.2流水線的特點在處理器方面，讓兩種方式進行對比，這二者是：一是傳統(tǒng)的串行方式，二是流水線方式。它們特征如下：（1）持續(xù)不斷地操作是流水線處理的前提。在這種前提下，才能將流水線的效率發(fā)揮出來。若斷流，則會效率會變差。（2）在流水線過程中，運行一個操作過程可以分解成多個子操作（它們之間有互聯(lián)關系），并分別讓專門的功能組件運行。（3）緩沖寄存器位于在每個功能組件之后，作用是緩沖本步驟的執(zhí)行之后所得到結(jié)果的，這是因為在每一段間延遲不平等，因此必須使用緩沖寄存器解決。（4）同時有多個操作在執(zhí)行。每一個子操作的功能組件工作在并行狀態(tài)，但各個功能組件上正在運行的是不一

30、樣的操作。（5）各個子任務執(zhí)行的時間應盡量相等，如果延時過長將造成“斷流”問題。2.2流水技術的主要性能指標與許多其他的計算機技術一樣，流水技術作為計算機的技術也有著自己的性能指標。流水技術的性能指標不僅僅關系著流水技術的好壞，而且對于使用流水技術的路由器也有著十分重要的影響，所以下面我們來對流水技術的性能指標加以分析。指標一：吞吐率流水線的吞吐量是單位時間內(nèi)其流水線處理指令數(shù)，或者說是從流水線中，我們能夠獲取輸出的結(jié)果數(shù)量。流水線的最大吞吐率是一個關于吞吐的數(shù)量。這個吞吐量僅僅當流水線來到一個穩(wěn)定狀態(tài)后，才會發(fā)生。若各個功能階段的時間相等，那么ti=t0 TPmax=1/t0，若各功能段時間

31、不相等，TPmax=1/max（ti）由花費時間最多的功能段所決定。計算吞吐率的公式為：在這個公式中，操作數(shù)是n，是完成全部操作的時間。為了對流水線的最大吞吐率進行提升，首先要找出阻礙吞吐率的制約因素，然后想辦法解除制約因素。解除這種因素有兩種方案：一是將制約因素子過程再次逐一劃分，二是多次設立多個制約因素區(qū)讓它們并聯(lián)在一起，允許它們交叉進行。第二種方法，首先要把在各并行子過程之間的任務分配合同步控制解決好，其與把制約因素子過程再細分控制過程相比，它更加要復雜、需要的設備量更多。指標二：加速比 有一條流水線采用串行模式。然后將它更改為流水模式，流水速度兩者比值被稱為加速比。加速比通常用來衡量流

32、水線的工作安排合理程度。則流水線的加速比為：公式中 是在順序執(zhí)行期間所要花費的時間， 是采用用流水線方式后執(zhí)行花費的時間，其就是加速比的公式。指標三：效率在時間上，流水線中的設備實際使用的花費和整體運行的花費比稱為流水線效率。簡單來說流水線效率就是流水線中設備的使用率。如圖5所示，流水線的效率是在時空區(qū)進行定義的，具體來說：n個操作任務在現(xiàn)實中使用的時空區(qū)和多個（公式中用k表示）功能階段的總的數(shù)量的的比值。一個段線效率用公式表示為：它就是是計算流水線的效率的基本公式。1 2 3 4 5S5S4S3S20mt(n-1)tS1(段號)sttn-1 tn tn+4t1 t2 t3 t4 t5n-1

33、nn-1 nn-1 nn-1 nn-1 n1 2 3 4 51 2 3 4 51 2 3 4 51 2 3 4 5填入填滿（正常）排空 圖5 流水線的各區(qū)間構成和時空圖2.3流水線技術的相關問題流水線中會出現(xiàn)流水相關現(xiàn)象。造成這種現(xiàn)象的原因是指令流（流水線上的工作），受到某種緣故的影響，在指令的一個時鐘內(nèi)，流水部件無法完成應該完成的的操作，這種現(xiàn)象我們就稱為流水線相關。流水線相關現(xiàn)象促使了流水線性能滑落，使得加速比大大的小于理想情況。下面就流水線相關的三個方面開始分個討論。2.2.1資源相關多指令進入流水線，在同一個機器周期，在對相同的組件資源的競爭引起沖突。有一些不能夠完全流水化生產(chǎn)功能部件

34、的根本原因就是造成了資源相關。流水沖突產(chǎn)生的另一個關鍵原因就在于系統(tǒng)中，對流水線中的組合所有指令的情況分析，使硬件資源數(shù)量充足。解決的方法有1）完全流水化功能部件；2）根據(jù)流水線中指令組合，設置足夠多的資源。2.2.2數(shù)據(jù)相關數(shù)據(jù)相關就是指在一個程序中，在前面的一條條指令執(zhí)行完成情況下，后面的一條的指令才能被執(zhí)行，因此，我們可以知道這兩條指令就是數(shù)據(jù)相關。數(shù)據(jù)相關可以劃分三種，它們是指令相關、主存空間數(shù)相關和通用寄存器組相關。解決數(shù)據(jù)相關的方案有：一就是退后分析法，在碰到數(shù)據(jù)沖突時候，暫不對本條指令進行分析，等到本條指令所需數(shù)據(jù)寫入，才開始分析本條指令的操作。二是建立一個專門的路徑，原理是操作

35、必要數(shù)據(jù)直接從專用路徑中獲取，不需要再等待操作需要的數(shù)據(jù)寫入該指令存儲單元中。2.2.3控制相關由于程序在運行過程中，也許其運行方向發(fā)生變化造成的沖突，這種相關叫做控制相關。它亦被稱為局部性相關。解決的方法有：（1）延遲轉(zhuǎn)移法延遲轉(zhuǎn)移法的理論是讓前面少數(shù)不相關的指令和轉(zhuǎn)系指令互換位置，使得成功轉(zhuǎn)移指令在少數(shù)指令執(zhí)行后才開始執(zhí)行，這種方法可以減少轉(zhuǎn)移造成的性能損失。這種方法用軟件實現(xiàn)。（2）轉(zhuǎn)移預測法在指令過去行為的基礎上，我們可以來預先猜想指令未來可能出現(xiàn)的行為。我們要達到預定猜想，在指令預取隊列器和目標指令緩存的幫助下，可以在取指階段提前進行轉(zhuǎn)移預測。其中這種方法用硬件來實現(xiàn)。3路由器的轉(zhuǎn)發(fā)

36、引擎分析3.1路由器的轉(zhuǎn)發(fā)引擎的概述3.1.1轉(zhuǎn)發(fā)引擎概述伴隨路由器結(jié)構體系的改進，它的內(nèi)部的轉(zhuǎn)發(fā)引擎也在持續(xù)的高速發(fā)展著。現(xiàn)今路由器中最典型的路由器結(jié)構就是如圖6呈現(xiàn)的。它是一種分布式的并行多處理結(jié)構。從圖6中我們可以直觀的看見轉(zhuǎn)發(fā)引擎在路由器中處于什么位置。外部接口線路接口模塊線路接口模塊線路接口模塊轉(zhuǎn)發(fā)引擎模塊轉(zhuǎn)發(fā)引擎模塊轉(zhuǎn)發(fā)引擎模塊轉(zhuǎn)發(fā)引擎模塊轉(zhuǎn)發(fā)引擎模塊轉(zhuǎn)發(fā)引擎模塊高速交換網(wǎng)絡主 控 處 理 模 塊 圖6 路由器結(jié)構圖轉(zhuǎn)發(fā)引擎的任務是對輸入報文的IP層進行處理完成。它的任務內(nèi)容有許多，例如報文完整性檢查、地址路由查找等。另外，轉(zhuǎn)發(fā)引擎的實現(xiàn)基本上憑借它的功能模塊。這些功能模塊是它的重

37、要組成部分，其包括有報頭處理、安全檢測等。轉(zhuǎn)發(fā)引擎工作過程如下：首先，外部IP包進入轉(zhuǎn)發(fā)引擎，轉(zhuǎn)發(fā)引擎就對其緩存，第二，在緩存中IP包，處理邏輯將其取出，再由處理邏輯對IIP包的報頭進行分析，將錯誤的報文挑出來并且丟掉。依據(jù)查轉(zhuǎn)發(fā)表的結(jié)果得出其輸出的接口，在確保QoS的基礎上查流的分類。當?shù)诙酵瓿珊螅罁?jù)第二步操作的結(jié)果來修改報頭，完成報頭修改后IP包被輸出到交換網(wǎng)絡。最后完成轉(zhuǎn)引擎的交換功能。3.1.2轉(zhuǎn)發(fā)引擎的的功能上文中對轉(zhuǎn)發(fā)引擎的工作過程有一個清晰的分析，下面對轉(zhuǎn)發(fā)引擎需要實現(xiàn)的功能做一個分析：（1）輸入處理：信號轉(zhuǎn)換和實現(xiàn)和線路接口模塊之間的數(shù)據(jù)格式轉(zhuǎn)換，得到IP包，使得IP數(shù)據(jù)包

38、報頭和報文緩存孤立（2）報頭的有效性檢測處理：分析報頭，對版本域、負載長度等檢測其合法性和有效性以及檢測IP包是否有擴展項。（3）安全策略檢查處理：在五元組信息基礎上對IP包進行安全過濾（五元組信息是源地址、目標地址源端口、源接口和協(xié)議域）。在安全過濾的基礎上記錄和轉(zhuǎn)發(fā)IP包。（4）單播地址查表處理：發(fā)現(xiàn)完整輸出接口，控制邏輯的IPV6單播目的地址查找表部。（5）直連檢查處理：組播報文被檢查，看其是否與對應的路由器相連。（6）RPF檢查處理：組播報文的反向地址檢測。（7）組播地址查表處理：找到輸出接口列表，對組播地址查表完成部分控制邏輯。(8)性能統(tǒng)計處理：完成對每個線口發(fā)到本模塊IP包的統(tǒng)計

39、。（9）QoS（英文全稱Quality of Service，中文全稱服務質(zhì)量，下文中都以QoS簡稱）查表處理：在DiffServ協(xié)議幫助下完成PHB相互對應，提供QoS給高性能路由器。3.2轉(zhuǎn)發(fā)引擎系統(tǒng)級流水線上文已經(jīng)提出了要運用流水技術于路由轉(zhuǎn)發(fā)過程，為了更清晰的了解流水技術如何在路由器的轉(zhuǎn)發(fā)過程中應用，我們需要對路由器的轉(zhuǎn)發(fā)引擎的轉(zhuǎn)發(fā)過程轉(zhuǎn)發(fā)過程進行全面的分析。如圖7所示，轉(zhuǎn)發(fā)引擎的處理過程包括了接口的轉(zhuǎn)發(fā)、提取報頭、路由查表、報文的修改和處理以及輸出控制等的五個方面。這是轉(zhuǎn)發(fā)引擎系統(tǒng)級的流水。以下文中將對它們進行一一剖析其作用。接口的轉(zhuǎn)換提取報頭路由查表報頭的修改和處理輸出控制 圖7（

40、1） 輸入緩存：接收和緩存線路接口輸出的報文。（2） 提取報頭：先對所接收到的報文進行分析，提取報頭，在把所提取的報頭發(fā)送到路由表模塊。（3） 路由查表：表關鍵字根據(jù)數(shù)據(jù)報頭生成，再依據(jù)生成的表關鍵來路由查表。（4） 報頭處理：檢查報頭的有效性，報文的TTL、地址范圍的有效性也要檢查。若是報文為組播報文，除了上述的操作外，還要對直連和RPF檢查。（5） 輸出控制：操縱報文的輸出。這個報文由報頭處理。有一些的轉(zhuǎn)發(fā)引擎的系統(tǒng)級功能模塊的知識，我們來分析在系統(tǒng)級別上流水線的工作過程：外部接口的輸入數(shù)據(jù)包轉(zhuǎn)發(fā)引擎，轉(zhuǎn)發(fā)引擎接收寫存儲在輸入緩沖器，然后報頭提取模塊從輸入緩存中的數(shù)據(jù)包提取報頭，提取出來的

41、報頭被送給查表模塊后開始查表操作。然后在查表后的結(jié)果和關于報頭有效性結(jié)果的基礎上，報頭處理模塊對報文如何處理做抉擇，如丟棄等。最后輸出控制模塊把報文(按照報文處理方式重新封裝好的)輸出去。上述的論文重點分析轉(zhuǎn)發(fā)引擎，并對其系統(tǒng)流水線做了詳細的分析，從而我們得到在系統(tǒng)流水線中，路由查表的過程時間最長。路由查表也就成了制約整個系統(tǒng)流水線的一大因素，因此，本文將在下一章節(jié)中提出一個基于TCAM流水線查找方案，從而提高路由器性能。4流水線在路由查表中的應用分析4.1基于TCAM的路由查找由一次三態(tài)內(nèi)容尋址存儲器（ternary content addressable memory，簡稱TCAM）操作和

42、一次靜態(tài)隨機存儲器（英文全稱為Static Random Access Memory，簡稱SRAM）操作構成了典型的TCAM路由查找方案。TCAM的結(jié)構又是構建在存儲陣列和優(yōu)先編碼器的基礎上。那么，TCAM的存儲陣列作用就是存儲前綴，前綴對應的轉(zhuǎn)發(fā)信息卻在SRAM上進行存儲。TCAM查找結(jié)構圖如圖8所展示的。TCAM的查找過程是：目標地址被拿來與存儲陣列的各個掩碼做與運算，其與運算的結(jié)果用來和同樣存儲在TCAM中前綴做比對，比對結(jié)果相等，匹配向量為1，反之，匹配向量為。另外，匹配符合的項可能有多個，因此讓優(yōu)先編碼器作為結(jié)果進行輸出的是保存于地址匹配項最低的地址。然后在此基礎上，在SRAM中取得

43、與之相對的轉(zhuǎn)發(fā)信息（轉(zhuǎn)發(fā)信息值得是輸出端口號和下一跳的地址）。據(jù)上所述，我們可以看出TCAM查表過程中由TCAM查表搜索過程和TCAM讀出表項兩個操作組成，這兩個操作是串行執(zhí)行的并且無法進行流水操作，因此，整個路由器的路由表查表過程需要的時間是TCAM查表搜索過程和TCAM讀出表項兩個操作的和，這個過程通常需要十幾個時鐘周期甚至更多存儲陣列321010N目的地址P9P8前綴長度匹配向量優(yōu)先編碼器轉(zhuǎn)發(fā)信息存儲器匹配表項轉(zhuǎn)發(fā)信息地址轉(zhuǎn)發(fā)消息TCAMSRAM圖8 TCAM查找結(jié)構為了解決這個現(xiàn)象，本論文設計了一個將流水技術引入路由查表的方案來解決路由查表周期時間長的問題，其方案由TCAM和SRAM一

44、起完成路由查表流水線，使得路由查表區(qū)分為兩個層次來完成:首先查表的搜索過程是通過TCAM完成，然后查表結(jié)果從SRAM里取出。將流水技術引入路由查表可使得減少到2個時鐘周期或者是4個時鐘周期。4.2路由查表的流水線方案設計路由查表是路由轉(zhuǎn)發(fā)過程中的重要組成部分。它的處理過程耗費的時間也是最長的。表項搜索和結(jié)果讀取兩個過程構成了實際上的路由查表過程，如同上文所說的一樣，要將兩個操作通過TCAM和SRAM分別來實現(xiàn)，我們就需要引入流水技術，盡可能的減少路由查表的時間，憑借這種來提高轉(zhuǎn)發(fā)引擎在轉(zhuǎn)發(fā)處理過程中的效率，提升路由器的整體性能。流水查表方案具體為：TCAM表用來將關鍵字（在路由查表時需要的）保

45、存起來，SRAM則是用與之相對某個的地址將查表后得到結(jié)果存貯起來，從單播查表看，TCAM地址保存為一個查表的關鍵字目標IP地址，在SRAM中的相應的一地址空間將保存，然后用作查表結(jié)果的目的接口號，從而形成了一條完整的單播表項。當報文來到時，第一是由FPGA將查表關鍵字從報頭中提出，隨后發(fā)送給TCAM查表來搜索，當TCAM搜索到與關鍵字相匹配的表項時，RBUS就會發(fā)送該表項的地址，SRAM獲取該表項的地址即獲得這次路由查表操作后得到結(jié)果轉(zhuǎn)發(fā)該報文的目標接口，通過SRAM發(fā)送到FPGA。如圖8所示。FPGATCAMDBUS RBUSAddrDQ SRAM第1步：送查表關鍵字第2步：輸出匹配地址第3

46、步：讀出查表結(jié)果FPGATCAMDBUS RBUSAddrSRAMDQ 第1步：送查表關鍵字第2步：輸出匹配結(jié)果第3步：讀SRAM操作第4步：讀出查表結(jié)果（1）（2）圖9圖9中有兩種關于流水線的設計方案，其兩者不同就在于TCAM中的RBUS是直連到SRAM的地址總線上還是不直連到SRAM的地址總線上若將TCAM的RBUS讓SRAM直接讀取地址，如圖9（1），好處是電路板的制作較為簡單，降低了現(xiàn)場可編程邏輯門陣列(FieldProgrammable Gate Array，簡稱FPGA)中的User IO的資源緊張問題。不足的是記錄表項的用時較長，原因在于記錄SRAM表項必須經(jīng)過相應的TCAM操作

47、才能實現(xiàn)，即需要通過TCAM才能完成記錄TCAM表項和SRAM表項。因此，記錄一條完整的表項所用的時間是二者之和：方法（1）記錄表項的時間等于是寫TCAM表項的時間和經(jīng)由TCAM記錄SRAM表項的時間之和。反過來說，若是TCAM的結(jié)果總線RBUS和SRAM的地址相連方式是要FPGA做中間人，如圖9（2）所示，電路板的制作難度是加大了，但是寫一條完整表項的時間卻降低了（其時間為寫TCAM表項和SRAM表項二者之間最大值）。原因是可以同時進行寫TCAM表項和SRAM表項，而且一般來說TCAM的讀寫時間大于SRAM的讀寫時間。即：方法（2）記錄表項時間就是等于記錄TCAM表項的時間。然而，若是SRA

48、M表項是由TCAM寫的，那么它的時間常常和獨自寫TCAM表項時間是差不多，因此圖9中的方法（2）寫表項的時間與圖9方法（1）寫表項的時間大大的不同，圖9中方法（2）寫表項的時間有了大幅度的降低了。所以方法（2）更有利于發(fā)揮轉(zhuǎn)發(fā)性能，這篇論文選用的就是方法（2）的流水線的路由查表方案。4.3基于TCAM的具體并行處理研究通過上文中我們對轉(zhuǎn)發(fā)引擎系統(tǒng)流水線的分析，提出了對路由查表也引入流水線機制，并且給出了路由查表流水線設計方案，那么我們在這里根據(jù)TCAM的特點，提出一種路由查找的并行工作方式，下文中將詳細闡述。根據(jù)已有的資料，我們可以知道TCAM在查表方面具有很快的速度，在存儲方面也很靈活。當然

49、，它也有不足之處，其不足之處在價格昂貴，功能消耗大而且表項更新方面速度很慢。據(jù)此，本文提出一種將TCAM空間進行多個分區(qū)處理，且這些分區(qū)是相互獨立的，我們稱這些分區(qū)為block。根據(jù)TCAM的特性，這些分區(qū)中，每一個都可以在獨立的情況下對查表任務完成，而且為分區(qū)供電只在其工作時。這種方法的具體實現(xiàn)過程是：第一要將TCAM空間進行分區(qū)，劃分為m個獨立的分區(qū)。將特征想同的表項存放在同一個分區(qū)中，那么路由查表時，現(xiàn)根據(jù)目標地址的特點，判斷它是哪個分區(qū)的。然后再使用該分區(qū)，對路由表進行再次查表操作。SRAM用來存放下一條的地址，讀取TCAM分區(qū)查表的結(jié)果。那么它的并行流水處理過程如圖10所呈現(xiàn)的。一次

50、查表邏輯Block1Block2.Blockm-1BlockmSRAM下一跳地址Hash值TCAM1TCAM2圖10基于TCAM并行處理流水工程4.4轉(zhuǎn)發(fā)查表外部結(jié)構和FPGA內(nèi)部結(jié)構4.41轉(zhuǎn)發(fā)查表的外部結(jié)構為了實現(xiàn)上述的路由查表，我們需要如下器件:FPGA、CAM和SRAM，它們組成的外部結(jié)構圖如圖11所示。SRAMFPGATCAM1TCAM2圖11 轉(zhuǎn)發(fā)查表的外部結(jié)構圖4.41轉(zhuǎn)發(fā)查表的FPGA內(nèi)部結(jié)構由邏輯仲裁、搜索查表、表項更新、數(shù)據(jù)選擇和TCAM的初初始化等功能構成了轉(zhuǎn)發(fā)查表FPGA模塊內(nèi)部結(jié)構，其圖如圖12所示。這些功能每一個都有自己的功用，在這里就不一一詳述了。TCAM初始化報

51、頭處理單播入FIFO（處理機接口邏輯仲裁FWP2FWP51搜素查表表項更新單元單播入FIFO（處理機接口FWP51查表結(jié)果輸出FWP2數(shù)據(jù)選擇TCAMSRAM圖12 FPGA內(nèi)部結(jié)構圖路由查表過程采用流水技術設計后，轉(zhuǎn)發(fā)引擎的等效流水線就如圖13所示。SRAM查表結(jié)果讀取CAM查表結(jié)果輸出CAM查關鍵字生成輸入接口轉(zhuǎn)換報頭提取輸出控制報頭處理和合成路由查表圖13 轉(zhuǎn)發(fā)引擎等效流程圖5路由器轉(zhuǎn)發(fā)性能提升小結(jié)高端的路由器其轉(zhuǎn)發(fā)引擎都要支持G比特的線速轉(zhuǎn)發(fā)能力。本文將流水技術引入到路由器轉(zhuǎn)發(fā)引擎。路由器的轉(zhuǎn)而發(fā)送能力有了很大的增長。路由器報文發(fā)送處理過程中速度最慢就是路由查表。那么，解決路由查表問題就是掃除了路由器的性能問題。本次論文首先詳細介紹了流水技術、路由器和轉(zhuǎn)發(fā)引擎。在路由設備的角度中，主要敘述的是路由設備的概念。工作過程、路由器的特點、基本構成以及研究現(xiàn)在的狀態(tài)也進行了描述。通過對路由器的分析，讓我明白了如何工作原理和如何提升路由器性能以及為什么要提升路由器性能。流水技術主要闡述了基本思想