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

2、擎。這種方法能增多路由器的性能。從而能夠解決網絡服務質量的問題，讓路由器不再成為是制約網絡發展的關口和約束。關鍵字：路由器 網絡服務質量 高速轉發引擎 流水技術 并行流水技術 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前言路由器是整個互聯網設備中的樞紐，它是相互之間有差別的網絡進行彼此聯接的核心，路由器是Internet的全部框架的組成者，它的處理速度在網絡快速發展中是一大制約因素。因此，在未來整個因特網研究領域，路由器技術處于并且將長時間的出去要害地位，它的發展過程也將成為整個因特網研究的一個重要寫照。現今網絡發展速度，不可小觀。隨著網絡快速成長，它在路由器的性能方面，提出了愈來愈高的要求。為了適合于下一代網絡的高速度的需求，路由器正在被挑釁。為了對路由器的性能加以提升，許多先行者會有很多在路由器上研究。對于路由器高速轉發技術，他們是研究的方向之一。高速轉發技術中引入流水線技術。這是現今提升路

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

32、水線的工作安排合理程度。則流水線的加速比為：公式中 是在順序執行期間所要花費的時間， 是采用用流水線方式后執行花費的時間，其就是加速比的公式。指標三：效率在時間上，流水線中的設備實際使用的花費和整體運行的花費比稱為流水線效率。簡單來說流水線效率就是流水線中設備的使用率。如圖5所示，流水線的效率是在時空區進行定義的，具體來說：n個操作任務在現實中使用的時空區和多個（公式中用k表示）功能階段的總的數量的的比值。一個段線效率用公式表示為：它就是是計算流水線的效率的基本公式。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 流水線的各區間構成和時空圖2.3流水線技術的相關問題流水線中會出現流水相關現象。造成這種現象的原因是指令流（流水線上的工作），受到某種緣故的影響，在指令的一個時鐘內，流水部件無法完成應該完成的的操作，這種現象我們就稱為流水線相關。流水線相關現象促使了流水線性能滑落，使得加速比大大的小于理想情況。下面就流水線相關的三個方面開始分個討論。2.2.1資源相關多指令進入流水線，在同一個機器周期，在對相同的組件資源的競爭引起沖突。有一些不能夠完全流水化生產功能部件

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

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

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

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

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

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

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

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

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

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

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

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

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

47、才能實現，即需要通過TCAM才能完成記錄TCAM表項和SRAM表項。因此，記錄一條完整的表項所用的時間是二者之和：方法（1）記錄表項的時間等于是寫TCAM表項的時間和經由TCAM記錄SRAM表項的時間之和。反過來說，若是TCAM的結果總線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）更有利于發揮轉發性能，這篇論文選用的就是方法（2）的流水線的路由查表方案。4.3基于TCAM的具體并行處理研究通過上文中我們對轉發引擎系統流水線的分析，提出了對路由查表也引入流水線機制，并且給出了路由查表流水線設計方案，那么我們在這里根據TCAM的特點，提出一種路由查找的并行工作方式，下文中將詳細闡述。根據已有的資料，我們可以知道TCAM在查表方面具有很快的速度，在存儲方面也很靈活。當然

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

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

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