基于NP體系結(jié)構(gòu)的路由器內(nèi)部流量控制技術(shù)研究＊

李海濤 丁宜棟

（海軍計(jì)算技術(shù)研究所 北京 100841）

1 引言

目前的高性能IP路由器普遍采用了基于網(wǎng)絡(luò)處理器NP（Network Processor）的體系結(jié)構(gòu)［1］，如圖1所示。

圖1 核心路由器體系結(jié)構(gòu)圖

為了適應(yīng)互聯(lián)網(wǎng)流量的突發(fā)特性，減小數(shù)據(jù)分組的丟失率，路由器內(nèi)部一般在網(wǎng)絡(luò)處理器和交換網(wǎng)絡(luò)（Switch Fabric）上設(shè)置了緩沖區(qū)，如圖1所示，在網(wǎng)絡(luò)處理器上設(shè)置了輸入排隊(duì)緩沖區(qū)和輸出排隊(duì)緩沖區(qū)，在交換網(wǎng)絡(luò)內(nèi)部設(shè)置了虛擬輸出隊(duì)列VOQ或共享存儲(chǔ)器緩沖區(qū)［2～5］。由于路由器內(nèi)部在數(shù)據(jù)轉(zhuǎn)發(fā)路徑上設(shè)置了多個(gè)緩沖區(qū)，不能不考慮各個(gè)緩沖區(qū)的阻塞問題［6］，因此需要在各緩沖區(qū)之間采用恰當(dāng)?shù)牧髁靠刂茩C(jī)制以提高系統(tǒng)整體適應(yīng)數(shù)據(jù)突發(fā)的能力。

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

2.1 流量控制基本原理

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

圖2 流量控制棊本原理

圖2是流量控制基本原理的示意圖，當(dāng)發(fā)送方的數(shù)據(jù)發(fā)送速率超過接收方的數(shù)據(jù)處理速率時(shí)，數(shù)據(jù)將被緩存在緩沖區(qū)內(nèi)，如果不調(diào)節(jié)發(fā)送方數(shù)據(jù)發(fā)送的速率或數(shù)量，緩沖區(qū)就會(huì)充滿，產(chǎn)生擁塞而引起數(shù)據(jù)丟失。因此流量控制的基本工作原理就是通過接收方的反饋信息來調(diào)節(jié)發(fā)送方的發(fā)送能力。流量控制技術(shù)按調(diào)節(jié)發(fā)送方數(shù)據(jù)發(fā)送的速率或數(shù)量可分為基于速率和基于信用兩種方式。

2.2 基于速率的流量控制

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

以上討論了一種簡單的基于速率的流量控制模型，其速率控制參數(shù)比較簡單。實(shí)際應(yīng)用中針對(duì)不同的需求會(huì)有不同的速率控制參數(shù)，流量控制粒度以及機(jī)制實(shí)現(xiàn)的復(fù)雜度等。

2.3 基于信用的流量控制

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

圖3 單隊(duì)列基于速率流量控制模型

圖4 基于信用的流控模型

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

圖5 信用量分配方案的滑動(dòng)窗U流量控制

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

圖5只給出了發(fā)送方情況，并假設(shè)數(shù)據(jù)幀和確認(rèn)幀都不發(fā)生差錯(cuò)和失序。接收方并不需要立即確認(rèn)進(jìn)入的數(shù)據(jù)幀，而等到許多數(shù)據(jù)到來后發(fā)出一個(gè)累計(jì)確認(rèn)。

2.4 兩種流量控制比較

基于速率和基于信用兩種流控方式各有優(yōu)缺點(diǎn)。

理想的情況下，基于信用的方法可保證無信元丟失，即使遇到突發(fā)業(yè)務(wù)流時(shí)信元的排隊(duì)長度也不會(huì)超出信用值所規(guī)定的范圍?；谒俾实姆绞接锌赡馨l(fā)生信元的丟失，當(dāng)遇到突發(fā)業(yè)務(wù)流時(shí)，排隊(duì)長度急劇增加，從而引起緩存溢出，造成信元丟失。這是因?yàn)榛谛庞玫牧骺貦C(jī)制一旦接收到有可靠的信用就以全線速度立即傳輸業(yè)務(wù)流?；谒俾实牧骺貦C(jī)制在接收到網(wǎng)絡(luò)狀態(tài)消息后才調(diào)整信源速率。

但基于信用的流控機(jī)制需要為每一條虛擬電路VC保持一個(gè)排隊(duì)隊(duì)列，這就需要較大的緩存空間，使得交換機(jī)的緩沖區(qū)設(shè)計(jì)變得復(fù)雜。因此不適應(yīng)于有大量VC的情況。

基于速率的流控方案在適配卡的設(shè)計(jì)上比信用策略復(fù)雜，相應(yīng)的硬件成本也高?；谛庞玫牧髁靠刂圃贚AN環(huán)境中可以實(shí)現(xiàn)低成本的網(wǎng)絡(luò)適配器和較高的性能。

3 路由器內(nèi)部流量控制分析

3.1 路由器內(nèi)部流控方式選擇

對(duì)于高性能IP路由器的內(nèi)部設(shè)計(jì)來說，路由器內(nèi)部各處理節(jié)點(diǎn)間已經(jīng)具有了相對(duì)獨(dú)立的緩沖區(qū)隊(duì)列設(shè)置，根據(jù)前面的分析，我們認(rèn)為基于信用的流量控制機(jī)制較適宜IP路由器內(nèi)部采用；而采用基于速率的流控機(jī)制在實(shí)現(xiàn)上較基于信用的流控機(jī)制更為復(fù)雜，且硬件實(shí)現(xiàn)代價(jià)也較高，因此在路由器內(nèi)部很少考慮這種復(fù)雜的流控機(jī)制。

3.2 路由器內(nèi)部流控機(jī)制分析

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

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

圖6 基于NP的路由器內(nèi)部流控模型

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

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

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

4 結(jié)語

通過對(duì)路由器內(nèi)部進(jìn)行流量控制，能有效緩解路由器內(nèi)部緩沖區(qū)的擁塞水平，減少數(shù)據(jù)丟包機(jī)會(huì)。對(duì)整個(gè)系統(tǒng)而言具有適應(yīng)突發(fā)數(shù)據(jù)能力強(qiáng)，不易丟包，網(wǎng)絡(luò)延遲短，網(wǎng)絡(luò)資源綜合利用率高等特點(diǎn)。為了實(shí)現(xiàn)下一代具有QOS功能路由器，還有待更進(jìn)一步對(duì)這方面進(jìn)行研究。

［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］徐恪，熊勇強(qiáng)，吳建平.寬帶IP路由器的體系結(jié)構(gòu)分析［J］.軟件學(xué)報(bào)，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.