基于NP體系結構的路由器內部流量控制技術研究＊

李海濤 丁宜棟

（海軍計算技術研究所 北京 100841）

1 引言

目前的高性能IP路由器普遍采用了基于網絡處理器NP（Network Processor）的體系結構［1］，如圖1所示。

圖1 核心路由器體系結構圖

為了適應互聯網流量的突發特性，減小數據分組的丟失率，路由器內部一般在網絡處理器和交換網絡（Switch Fabric）上設置了緩沖區，如圖1所示，在網絡處理器上設置了輸入排隊緩沖區和輸出排隊緩沖區，在交換網絡內部設置了虛擬輸出隊列VOQ或共享存儲器緩沖區［2～5］。由于路由器內部在數據轉發路徑上設置了多個緩沖區，不能不考慮各個緩沖區的阻塞問題［6］，因此需要在各緩沖區之間采用恰當的流量控制機制以提高系統整體適應數據突發的能力。

2 流量控制基本原理及方式

2.1 流量控制基本原理

網絡除了可為信息提供高速率、高帶寬的傳輸功能外，更為重要的是能靈活地支持現有的和將來可能出現的各種業務，并對各種業務提供服務質量（Qos）保證，使網絡達到很高的資源利用率。要達到這些目的需要對不同業務的數據運用不同的流量控制和擁塞控制機制。概括地說流量控制就是為了避免網絡出現擁塞而采取的一系列操作［7～8］。

圖2 流量控制棊本原理

圖2是流量控制基本原理的示意圖，當發送方的數據發送速率超過接收方的數據處理速率時，數據將被緩存在緩沖區內，如果不調節發送方數據發送的速率或數量，緩沖區就會充滿，產生擁塞而引起數據丟失。因此流量控制的基本工作原理就是通過接收方的反饋信息來調節發送方的發送能力。流量控制技術按調節發送方數據發送的速率或數量可分為基于速率和基于信用兩種方式。

2.2 基于速率的流量控制

基于速率（Rate－based）［9］的流量控制方式是一種端到端的流量控制機制，通過反饋數據分組所經過節點的網絡狀況來控制源端的數據發送速率。圖3中所示為一種簡單的控制模型，為只有一個隊列的情況。其中x（t）為輸入速率，y為輸出速率，q（t）為緩沖區內隊列長度。m為正向傳輸累積延遲，n是反向傳輸累積延遲。k為線性增加系數，β為指數減少系數。為了問題的簡單性，我們假設當隊列小于某一閾值f1時，反饋回來的流控信號將線性增加輸入速率x（t）。相反，當隊列大于某一閾值f2時，輸入速率將按指數減小。

以上討論了一種簡單的基于速率的流量控制模型，其速率控制參數比較簡單。實際應用中針對不同的需求會有不同的速率控制參數，流量控制粒度以及機制實現的復雜度等。

2.3 基于信用的流量控制

基于信用（Credit－based）［10］的流量控制機制就是源端在向鏈路上發送任何數據分組之前，都需要接收從接收端傳來的信用（Credit）信息。源端依據信用值大小決定發送數據的數量。一般來說信用值大于等于鏈路傳輸速率乘以鏈路往返傳輸時延。圖4給出了基于信用流控機制的基本模型。數據接收方首先發送信用到數據發送方，通知可用緩沖區容量，發送方收到信用后，根據信用值決定發送的數據分組數量。

圖3 單隊列基于速率流量控制模型

圖4 基于信用的流控模型

下面給出一種基于信用量分配方案的滑動窗口流量控制例子。如圖5所示。

圖5 信用量分配方案的滑動窗U流量控制

開始時發送端賦予七個幀的信用量被允許發送七個幀，每發送一個幀，窗口減小1。發送端發出了0、1、2號三個幀后，發送窗口減小到包含3～6號。此時，接收端對0～2號幀確認，在發回的確認幀中設置 ACK（2），Credit［5］，信用量大小為5，信用量大小代表了流控的粒度。即允許發送端在收到ACK后可以繼續發送五個幀（即從3～7號）。但由于確認幀返回時延，發送端在收到ACK（2），Credit［5］之前，已經發送了第3～4幀，使窗口相應地減少。在收到信用后，發送窗口就只能增加1，即包含5～7號。然后發送端將5～7三幀連續發送出去，就消耗了它的信用量，發送窗口減小到0，等待收到下一個信用。當收到ACK（7），Credit［7］后，恢復到原來的窗口。

圖5只給出了發送方情況，并假設數據幀和確認幀都不發生差錯和失序。接收方并不需要立即確認進入的數據幀，而等到許多數據到來后發出一個累計確認。

2.4 兩種流量控制比較

基于速率和基于信用兩種流控方式各有優缺點。

理想的情況下，基于信用的方法可保證無信元丟失，即使遇到突發業務流時信元的排隊長度也不會超出信用值所規定的范圍。基于速率的方式有可能發生信元的丟失，當遇到突發業務流時，排隊長度急劇增加，從而引起緩存溢出，造成信元丟失。這是因為基于信用的流控機制一旦接收到有可靠的信用就以全線速度立即傳輸業務流。基于速率的流控機制在接收到網絡狀態消息后才調整信源速率。

但基于信用的流控機制需要為每一條虛擬電路VC保持一個排隊隊列，這就需要較大的緩存空間，使得交換機的緩沖區設計變得復雜。因此不適應于有大量VC的情況。

基于速率的流控方案在適配卡的設計上比信用策略復雜，相應的硬件成本也高。基于信用的流量控制在LAN環境中可以實現低成本的網絡適配器和較高的性能。

3 路由器內部流量控制分析

3.1 路由器內部流控方式選擇

對于高性能IP路由器的內部設計來說，路由器內部各處理節點間已經具有了相對獨立的緩沖區隊列設置，根據前面的分析，我們認為基于信用的流量控制機制較適宜IP路由器內部采用；而采用基于速率的流控機制在實現上較基于信用的流控機制更為復雜，且硬件實現代價也較高，因此在路由器內部很少考慮這種復雜的流控機制。

3.2 路由器內部流控機制分析

從圖l中可以看出有兩個地方需要進行流控，即各個NP上的FIFO隊列之間需要互相通告擁塞信息以及各個VOO隊列與交換網之間需要流控信息。相應地引入兩種流控機制：NP－Fabric流控和NP－NP流控。

網絡處理器NP和交換芯片之間的流控，記為NPFabric流 控，NP－Fabric 流控允許交換芯片向NP通告它的全局隊列存儲器（VOQ）中的空閑空間信息。這允許NP決定怎樣最好利用剩余的存儲空間，以避免擁塞發生。除此之外，還在各線卡之間引入了NP－NP流控。該流控機制允許各線卡交互隊列長度信息，根據隊列長度分配各自輸入到各個輸出的帶寬，以此來調節各線卡發往目的端口的數據傳送能力，避免該數據通路上相應排隊緩沖區數據接收能力大于處理能力而發生數據溢出。例如當N號線卡上的排隊緩沖區將滿時，通過NP之間互相反饋流控信息（通告信用量），1號線卡得知N號線卡狀態后（無信用或收到信用量為0的流控信息）就停止往該線卡上發送數據，以減小擁塞的可能性。下圖描述了基于NP的路由器內部流控模型。

圖6 基于NP的路由器內部流控模型

為了實現上述路由器內部流控模型，如圖1所示，在交換網與NP之間添加了NPSI流控接口。NPSI流接口規范由標準化組織NPF（網絡處理論壇）給出。該接口支持在一對包括物理層（PHY）器件（如SONET成幀器／映射器或以太網MAC器件）、網絡處理器、網絡協處理器和交換網的網絡處理器件間進行網絡業務傳輸。它定義了三種數據和流控傳輸模式即 NPE－Framer，NPE－Fabric和 NPE－NPE三種接口模式。其中NPE－NPE和NPE－Fabric接口模式也明確提出了一種基于信用的流控方案。

NPE－NPE之間（上述模型的 NP－NP），通過互相通告FIFO隊列信息，各個線卡決定是否發送數據到FIFO負載比較重的線卡上去，以減小擁塞的可能性。

NPE－Fabric之間（上述模型的 NP－Fabric），可以采用一種被稱為全局流控（Global Flow Control）機制來實現。交換網接收NPE來的數據進入隊列，交換網利用收到的數據中的控制字（ADF）信息決定數據存入哪個隊列。全局流控是在NPE－Fabric接口上的可選機制，它允許Fabric在它的全局隊列（VOQ）存儲器中通告空閑空間。在共享存儲交換網中資源被動態分配，這允許NPE決定怎樣最好利用剩余的存儲空間。全局流控消息通過流控幀格式中的全局狀態位global status［7：0］來傳輸Fabric能接受的數量。全1表示所有空間可用，全0表示無剩余空間，在此，global status［7：0］就相當于信用通告位，其值就表示通告的信用量大小。

4 結語

通過對路由器內部進行流量控制，能有效緩解路由器內部緩沖區的擁塞水平，減少數據丟包機會。對整個系統而言具有適應突發數據能力強，不易丟包，網絡延遲短，網絡資源綜合利用率高等特點。為了實現下一代具有QOS功能路由器，還有待更進一步對這方面進行研究。

［1］Jonathan Chao.Next Generation Routers［J］.Proceedings of The IEEE，2002，90（9）：33－36.

［2］Chuang S T.Matching Output Queuing with a Combined Input／Output Queued Switch［J］.IEEE Journal on Selected Areas in Communications，1999，17（6）：1030－1039.

［3］Minkenberg C，Engbersen T.A Combined Input and Output Queued Packet－Switched System Based on PRIZMA Switch－ona－Chip Technology［J］.IEEE Communications Magazine，2000，38（12）：70－77.

［4］Stunkel C.The SP2High－Perfomance Switch［J］.IBM Systems Journal，1995，34（2）.

［5］McKeown N，The iSLIP Scheduling Algorithm for Input＿Queued Switches［J］.IEEE／ACM Trans Networking，1999，7（2）.

［6］徐恪，熊勇強，吳建平.寬帶IP路由器的體系結構分析［J］.軟件學報，2000，11（2）：179－186.

［7］Roberts JW.Traffic control in the BISDN［J］.Computer Networks and ISDN Systems，1993，25：1055－1064.

［8］R Epsilon，J Ke C.Williamson.Analysis of ISP IP／ATM Network Traffic Measurements［J］.ACM Performance Evaluation Review，1999，27（2）：15－24.

［9］Bolotj c，Shankar A U.Dynamical behavior of rate－based flow control mechanisms［J］.ACM SIGCOMM Computer Communication Review，1990，20（2）：35－49.

［10］Kong H T，Morris R.Credit－based flow control for ATM Networks［J］.IEEE Network Magazine，1995，9（2）：40－48.