路由器并行交換體系結(jié)構(gòu)的研究
一、引言
由于Internet采用TCP流控機制，數(shù)據(jù)傳輸?shù)氖驅(qū)W(wǎng)絡(luò)性能產(chǎn)生較大影響。盡管采用散列函數(shù)等方法可以保證TCP報文流按順序傳送，但只能從統(tǒng)計意義上保證并行交換系統(tǒng)的性能，并且對網(wǎng)絡(luò)流量的分布依賴較大。因此，較好的方法是采用固定長度信元的并行處理機制，不僅系統(tǒng)控制易于實現(xiàn)，而且系統(tǒng)性能有絕對保證，不依賴于網(wǎng)絡(luò)流量分布。然而，高速路由器處理的是不定長的IP分組，要在基于定長信元并行交換系統(tǒng)上實現(xiàn)IP報文的高速交換，首先要以線路速率將IP分組分成定長的信元流；同時，每個信元都必須帶有相應(yīng)的控制信息，以保證信元流的正確交換與目的端口 IP報文的重組。本文按照高速路由器的IP分組處理流程，較詳細地分析了各處理模塊的功能與性能要求，提出了一種IP分組并行處理與信元并行處理相結(jié)合的高速路由器體系結(jié)構(gòu)。
二、路由器的報文處理
路由器要完成IP分組的交換，其處理過程通常應(yīng)包括分組報頭處理、路由查表、流量控制、緩存、隊列調(diào)度、交換、輸出緩存等過程。
1．輸入報文處理
路由器輸入報文處理過程主要包括分組報頭處理、路由查表、流量控制、緩存、隊列調(diào)度等。報頭處理單元主要完成IP報文報頭字段的處理，包括報頭校驗、TTL字段處理、錯誤檢查、報頭選項識別、報文分類等。不能直接轉(zhuǎn)發(fā)的IP包被放入一個單獨的隊列，由系統(tǒng)處理機做相應(yīng)的處理；對于需要轉(zhuǎn)發(fā)的IP報文，根據(jù)系統(tǒng)配置，提取TOS域，映射成報文化先級。同時，生成路由查找模塊需要的數(shù)據(jù)結(jié)構(gòu)，交路由查找模塊進行路由查找。路由查找單元根據(jù)系統(tǒng)維護的轉(zhuǎn)發(fā)表，按報文中目的IP地址查找相應(yīng)的輸出端口。由于IP報文的隊列管理與流量控制依賴于報文的流向與QOS要求的相關(guān)信息，因此要求路由器必須以線速率完成查表處理，保證報文在查表前不排隊。按目前技術(shù)水平，采用大規(guī)模ASIC實現(xiàn)的查表引擎可達到40MPPS的平均處理能力（目前采用的查表技術(shù)可達到20MPPS的處理能力）。從平均意義上講，采用這些硬件查表技術(shù)可以保證40GbPs和20Gbps的線速接口的處理要求。需要說明的是，上述轉(zhuǎn)發(fā)引擎性能的測試都是在不考慮轉(zhuǎn)發(fā)表更新的條件下進行的，而轉(zhuǎn)發(fā)表的更新將占用較大的內(nèi)存訪問帶寬，從而影響實際報文轉(zhuǎn)發(fā)速率。這些查表技術(shù)不僅轉(zhuǎn)發(fā)表占用內(nèi)存較大，而且由于其數(shù)據(jù)結(jié)構(gòu)組織復(fù)雜，轉(zhuǎn)發(fā)表更新效率不高。據(jù)有關(guān)文獻報道，由于因特網(wǎng)路由的不穩(wěn)定性，干線路由器路由表更新的峰值速率可達每秒數(shù)百次。因此，如何在保證查表速率的前提下，提高轉(zhuǎn)發(fā)表的更新速率是有待進一步研究的問題。
隊列管理與擁塞控制單元根據(jù)緩沖區(qū)狀態(tài)及有關(guān)隊列狀態(tài)信息，根據(jù)IP報文分類和路由查找結(jié)果將報文送往隊列緩沖區(qū)。在出現(xiàn)擁塞的情況下，流量控制單元將根據(jù)擁塞控制策略實施擁塞控制。為了實現(xiàn)基于區(qū)分服務(wù)體系結(jié)構(gòu)IP QOS保證，報文丟棄將根據(jù)不同的業(yè)務(wù)類型和流向分別實施控制。通常，緩沖區(qū)的管理都采用定長數(shù)據(jù)塊為單位申請和釋放緩沖區(qū)，這樣不僅管理方便、易于硬件實現(xiàn)，可以避免出現(xiàn)大量緩沖區(qū)“碎塊”，而且便于實現(xiàn)以定長數(shù)據(jù)塊為傳送單位的交換網(wǎng)絡(luò)的接口，實現(xiàn)IP報文的公平傳送。由于IP報文為不定長的報文，因此在報文進入緩沖區(qū)之前必須分成固定長度的信元。為了保證各個信元可以獨立地被調(diào)度和交換，并且在輸出緩沖區(qū)重新組裝成完整的IP報文，各個信元都必須帶有相應(yīng)的目的端口和控制信息。
隊列調(diào)度單元根據(jù)交換網(wǎng)絡(luò)控制器的仲裁結(jié)構(gòu)和調(diào)度策略，將相應(yīng)隊列中的信元通過交換網(wǎng)絡(luò)送往目的端口。交換網(wǎng)絡(luò)用于完成報文從源端口向目的端口的交換傳送。用于高速路由器的交換網(wǎng)絡(luò)通常采用模共享緩存交換或交換矩陣（Crossbar）兩種方式。交換矩陣方式又以其良好的可擴展性而在目前高速路由器產(chǎn)品中得到越來越多的應(yīng)用。
2．輸出報文處理
輸出端主要完成報文的重組、緩沖及輸出鏈路接口控制。
首先通過交換網(wǎng)絡(luò)接口從交換網(wǎng)絡(luò)得到定長的信元，將其重新組裝成完整的IP報文。由于交換網(wǎng)絡(luò)控制器以信元為傳輸單位控制各個源端口的數(shù)據(jù)傳輸，輸出端將同時接收各個源端口的信元流。因此在邏輯上必須為每個源端口設(shè)置獨立緩沖區(qū)，分別緩存各個IP報文的信元，完成整個IP報文的接收并將完整的IP分組送交輸出緩沖區(qū)等待發(fā)送。
對于采用輸入緩沖（虛擬輸出隊列VOQ）的交換體系結(jié)構(gòu)，交換網(wǎng)路的傳送速率等于鏈路速率。這樣，輸出緩沖區(qū)可采用簡單的FIFO管理機制，緩沖區(qū)大小為最大報文長度的N倍即可（N為路由器端口個數(shù)）。但是，輸入緩沖交換無法保證輸出鏈路的盡職工作，采用VOQ機制只能保證在輸入流量為均勻分布的條件下達到100％的吞吐量。研究表明，因特網(wǎng)流量分布具有很強的不均勻性。因此，輸入緩沖交換的加速問題成為交換技術(shù)研究的一個熱點，其目的是使輸入緩沖交換嚴格模仿輸出緩沖交換。為此，交換網(wǎng)絡(luò)的速率必須是鏈路速率的兩倍。然而，交換網(wǎng)絡(luò)的加速將導(dǎo)致交換網(wǎng)絡(luò)輸出速率大于輸出鏈路速率，輸出報文在輸出緩沖區(qū)必須重新排隊，甚至導(dǎo)致輸出緩沖區(qū)的溢出。這樣，必須在輸出端另外再設(shè)置緩沖區(qū)管理、隊列調(diào)度與擁塞控制機制。并且，系統(tǒng)擁塞控制策略的實現(xiàn)不僅與輸入端的擁塞控制機制有關(guān)，而且與輸出端的擁塞控制機制有關(guān)。無論是輸入緩沖交換，還是輸出緩沖交換，隊列管理與擁塞控制都只需在交換網(wǎng)絡(luò)的一側(cè)實現(xiàn)，而加速后的輸入緩沖交換，報文需要在輸入和輸出端分別緩存。有些文獻稱之為組合輸入輸出交換（CIOQ）。對于這種組合輸入輸出交換體系結(jié)構(gòu)的隊列調(diào)度與擁塞控制，目前尚未有理想的解決方案。
一種簡單的解決方案是借鑒ATM交換機中常用的反壓機制。在輸出端設(shè)置較小的緩沖區(qū)；采用簡單的FIFO調(diào)度策略；當輸出端緩沖區(qū)出現(xiàn)溢出時通過反壓機制控制交換網(wǎng)絡(luò)暫緩數(shù)據(jù)傳輸。對于這種方案的性能還有待于做進一步分析。
由于輸出端報文處理較簡單，在目前技術(shù)水平下，對于2.5G的接口速率，完全可以采用單個處理模塊實現(xiàn)。但是，對于10G以上的接口，由于內(nèi)存訪問速度及總線帶寬的限制，必須采用多模塊并行處理體系結(jié)構(gòu)。#p#
三、報文并行處理與交換
1．分組并行處理與信元并行處理
基于信元的并行處理體系結(jié)構(gòu)，不僅可以保證信元的按序傳輸，而且可以保證輸出鏈路的盡職工作（100％吞吐量）。為此，必須將輸入的IP報文拆成定長的信元，通過調(diào)度機制將信元送往各個不同的轉(zhuǎn)發(fā)處理模塊。
為了將輸入的IP分組拆成信元流，并保證在目的端口正確地組裝成完整的IP分組，各個信元必須帶有其所屬IP分組的有關(guān)信息。為此，在拆分IP分組之前必須完成IP分組的報頭處理及IP地址查表。這部分處理必須實時完成，以保證不會出現(xiàn)報文積壓。如果單個處理模塊無法以線路速率完成報文的處理，應(yīng)以分組為調(diào)度單位實現(xiàn)多模塊并行處理。首先這部分處理功能是為分組轉(zhuǎn)發(fā)提供控制信息，在處理前系統(tǒng)缺少分組的相關(guān)信息，如業(yè)務(wù)類型、目的端口、校驗是否正確等，無法得到各信元所需的控制信息；其次，這部分處理雖然是不定長的IP分組，但只是處理IP分組的報頭，處理時間基本固定，與分組的長度無關(guān)，丟棄校驗出錯的分組也只需簡單的硬件操作即可實現(xiàn)；再者，由于無需報文緩沖，硬件實現(xiàn)較簡單，易于實現(xiàn)多處理模塊的并行處理；最后，由于流量控制必須以分組為單位實施分組丟棄，在流量控制之前將分組拆成定長的信元將加大流量控制的實現(xiàn)難度。
流量控制模塊在出現(xiàn)擁塞時根據(jù)設(shè)定的分組丟棄策略丟棄部分分組，從而保證緩沖區(qū)不會出現(xiàn)溢出。如果在流量控制之前將分組拆成定長的信元，分組的丟棄必須保證將同一個IP分組的所有信元同時丟棄。因此，如果需要做并行處理，必須保證同一個IP分組的所有信元分配到同一個處理模塊。同時，流量控制也只需要IP報文的報頭信息和報文緩沖區(qū)狀態(tài)，其處理時間基本為一定值，與IP報文的長度無關(guān)。所以，在流量控制之后實施IP分組的拆包更合適。
綜上所述，在流量控制以前的操作不需要大容量存儲器，處理時間基本為定值，與IP報文長度無關(guān)，只需專用器件（ASIC或FGA）完成相應(yīng)的處理即可。因此，對于需要并行處理的高速路由器，IP報文的報頭處理、查表轉(zhuǎn)發(fā)、流量控制應(yīng)該采用以IP報文為基本處理單位的多模塊并行處理結(jié)構(gòu)。根據(jù)目前技術(shù)、工藝水平及國外高速路由器產(chǎn)品開發(fā)實踐，單個處理模塊難以勝任2.5G以上接口的 IP報文處理要求。盡管基于IP報文為基本處理單位的多模塊并行處理結(jié)構(gòu)的效率低于基于定長信元的多模塊并行處理結(jié)構(gòu)，對于未來高速路由器，它仍將是IP報文處理流程中必不可少的組成部分。
報文緩沖區(qū)是用于緩存IP報文的海量存儲器。對于一個10Gbps的接口，若數(shù)據(jù)線采用256比特寬度，則至少每12.8ns就要完成一次讀或?qū)懖僮?。實現(xiàn)如此高速的海量存儲器目前尚有一定困難，對于10G以上的接口，無法采用單模塊實現(xiàn)。按目前的技術(shù)水平，只能采用多處理模塊并行處理體系結(jié)構(gòu)。從存儲器管理機制的實現(xiàn)和存儲器利用率方面考慮，目前緩沖區(qū)管理通常采用分區(qū)管理機制，將內(nèi)存劃分成定長的分區(qū)，根據(jù)請求的緩沖區(qū)長度分配一定數(shù)量的分區(qū)。這樣，若要緩存一個IP報文，需要將不定長的報文按存儲器分區(qū)大小分成多個定長的數(shù)據(jù)段。因此，可以首先將IP分組分成定長的信元，而將分區(qū)大小設(shè)置成信元長度，以信元為單位實施緩沖區(qū)管理。
在輸出端，同樣由于存儲器芯片訪問速度的限制，對于10G以上的端口，必須采用并行處理結(jié)構(gòu)。同時，鏈路輸出必須以IP報文為基本傳輸單位，在多模塊并行處理體系結(jié)構(gòu)中必須以IP分組作為基本傳輸單元分配處理模塊。然而同一個IP分組的各個信元是通過不同的交換單元傳輸?shù)?，交換網(wǎng)絡(luò)與緩沖區(qū)的接口必須識別同一個IP分組的信元流送往相同的處理模塊。
綜上所述，若要在高速路由器輸入端實現(xiàn)IP報文的并行處理，在緩沖區(qū)管理之前應(yīng)采用基于IP分組的并行處理結(jié)構(gòu)；而緩沖區(qū)管理和交換網(wǎng)絡(luò)應(yīng)采用基于信元的并行處理結(jié)構(gòu)；輸出端則應(yīng)采用基于IP分組的多模塊并行處理結(jié)構(gòu)。
2．輸入端報文并行處理
根據(jù)上節(jié)的分析，輸入端報文在報文緩沖之前采用基于IP分組的并行處理結(jié)構(gòu)。我們將IP報頭處理、查表、擁塞控制三項處理稱為轉(zhuǎn)發(fā)控制。這樣，輸入端處理包括線路接口、轉(zhuǎn)發(fā)控制及報文緩沖。對于需要并行處理的高速路由器，轉(zhuǎn)發(fā)控制部分采用基于IP分組的并行處理結(jié)構(gòu)，而報文緩沖采用基于信元的并行處理結(jié)構(gòu)。
分組解復(fù)用器的作用是將從線路接口接收到的IP分組分配到各個處理模塊。為了保證協(xié)議類型為TCP的IP分組的按序傳送，對于屬于TCP業(yè)務(wù)的IP分組按散列法分配轉(zhuǎn)發(fā)控制單元，而其它類型的IP分組則按最短隊列分配轉(zhuǎn)發(fā)控制單元。
其中，hp表示IP分組的報頭信息；S表示緩沖區(qū)隊列大??；HASH（hp）表示根據(jù)IP分組的報頭信息做散列；而F（s）表示根據(jù)當前緩沖區(qū)隊列大小S做調(diào)度（如選擇具有最短隊列的處理單元）。由于轉(zhuǎn)發(fā)控制部件的輸出是無阻塞、定速率的，根據(jù)輸入流量的大小即可確定緩沖區(qū)中隊列的大小?？刂妻D(zhuǎn)發(fā)單元的輸出經(jīng)過分段處理，將報文分成定長的信元流。分配器用于實施信元調(diào)度，將信元送往不同的緩沖處理單元，經(jīng)緩存送往交換網(wǎng)絡(luò)。
3．輸出端報文并行處理
在輸出端，首先要將從交換網(wǎng)絡(luò)接收的信元重組成完整的IP報文，以IP報文為基本單位送往發(fā)送緩沖區(qū)。通過輸出隊列調(diào)度，將發(fā)送緩沖區(qū)的IP報文送高速緩存（CACHE），高速緩存以線路速率向輸出鏈路輸出完整的IP報文。
高速緩存的作用是為高速輸出鏈路與低速報文緩沖區(qū)提供接口。由于緩沖區(qū)無法提供與高速鏈路相適應(yīng)的訪問速度，所以采用高速緩存：它接收發(fā)送緩沖區(qū)的報文，然后將完整的IP報文以線速率通過輸出復(fù)用器向輸出鏈路發(fā)送。輸出復(fù)用器以完整的IP報文為基本傳輸單位，每次以一定的調(diào)度策略選擇一個高速緩存輸出報文。
四、結(jié)論
本文通過分析高速路由器IP報文的處理流程和各處理單元的處理要求，對基于分組的并行處理結(jié)構(gòu)和基于信元的體系結(jié)構(gòu)做了詳細分析和討論。我們認為信元轉(zhuǎn)發(fā)控制和輸出緩沖應(yīng)采用以基于IP分組的并行處理，而輸入端報文緩沖和交換網(wǎng)路應(yīng)采用基于定長信元的并行處理結(jié)構(gòu)。本文給出的高速路由器報文輸入、輸出的并行處理方案具有一定的實用價值和理論意義。
【編輯推薦】
