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