路由器公平排隊仿真模型研究與實現

2019-11-05 00:31:58

字體：大中小

來源：轉載

供稿：網友

　　1　引　言
　　寬帶網絡的發展要求一個通信網絡要能同時支持多種不同的業務特性的流量，也即能提供不同的服務質量保證，具體表現在滿足帶寬、時延、時延抖動等方面的不同需求。因此網絡本身必須具有提供不同服務質量的能力，其中，分組公平隊列調度算法是提供服務質量保證的重要機制之一。近年來，基于GPS（Generalized PRocessor Share）［1］的分組公平排隊調度算法得到了廣泛的研究，其中最重要的是WFQ［2］。WFQ考慮的不定長度分組的排隊和調度，因此，對WFQ的仿真通常使用事件驅動的方式，模型需要維護的信息量大，開銷較大。另外，對硬件的實現也是一種挑戰。
　　
　　但在當今許多高速路由器／交換機中，為了提高傳輸效率，通常采用定長交換技術，處理數據單元為固定長度的“信元”。對于不同長度的ip分組，可以在交換前劃分成信元，在輸出端重組后再發送到鏈路上去。那么，基于固定長度的信元排隊和調度的WFQ的實現也隨之而來，這也是WFQ的一種特例。在這種情況下，固然可以采用事件驅動的方式來仿真WFQ，但本文提出了一種更有效的仿真模型，他利用了信元輸出時間固定的特性，采用固定時間驅動的方式，從而簡化了仿真流程和減小了系統開銷。此外，對硬件的設計和實現也有指導意義。
　　
　　本文提出WFQ的仿真模型簡單、高效，在研究單個交換節點的性能時，為研究者提供了一種仿真工具。本文主要對基于信元排隊的WFQ進行了建模和仿真，并從帶寬分配的公平性方面與FIFO（許多路由器／交換機采用仍采用的排隊方式）進行了性能比較，仿真結果表明基于信元排隊的WFQ適用于高速路由器／交換機中。
　　
　　2　基于信元排隊的WFQ
　　在提出仿真模型之前，首先介紹WFQ和基于信元排隊的WFQ，這是模型建立的理論基礎和模型實現中的要害部分。因此，單獨提出并做簡單介紹。
　　
　　文獻［2］定義的WFQ基于：
　　
　　（1）系統維持一個全局函數V（t），稱為系統虛時間函數，用以記錄WFQ已經提供的服務量。V（t）也就是GPS系統中系統虛時間。WFQ利用系統虛時間函數為每個分組計算其相應的開始時間標簽和完成時間標簽如式（1）所示：
　　　

　　φi表示賦予會話i的任一正實數，這里可以理解為會話i預約的歸一化帶寬ri。其中系統虛時間的維護是WFQ實現的要害，按文獻［2］中的實現方法，V（t）更新的時刻不固定，隨時都有可能必須使用事件驅動的方式實現。
　　
　　（2）執行分組選擇策略，WFQ遵循最小完成時間標簽優選（SFF，Smallest Finishing time First）。
　　
　　基于信元排隊的WFQ與分組WFQ的不同可歸結于：
　　
　　①信元長度固定，調度事件發生間隔固定。
　　
　　②系統虛時間可以在每次調度時更新。
　　
　　其中②依據①和文獻［4］中的結論，這充分利用了信元輸出時間固定的特點。文獻［4］介紹了一種只在分組離開時更新V（t）的方法，而信元輸出的時刻是固定的并且間隔相等，那么對于基于信元的WFQ，我們只需要在間隔相等的固定時刻采用文獻［3］的技術就可以實現。
　　
　　3　模型建立
　　根據以上的分析，仿真模型采用簡單的固定時間驅動的方法實現。模型建立的幾點假設［3］：
　　
　　（1）一個信元傳輸的時間稱為一個時隙。
　　
　　（2）各輸入端信元的到達過程相互獨立。
　　
　　（3）信元只在每個時隙開始時到達，輸出隊列容量足夠大。
　　
　　（4）模型建立和仿真研究都基于單播數據流。一個具有N個輸入／輸出端口的WFQ模型的框圖如圖1所示。
　　
　　該模型是由信元產生器、交換結構、輸出隊列組成，其中輸出隊列包含用于存儲各個會話的信元的緩存和WFQ調度器。根據假設（1），在仿真模型中，信元的產生、交換和調度輸出都將在一個時隙內同時進行。本文使用模塊化的設計思路實現該模型，基于兩點考慮：一是模型各主要組成部分交互關系簡單、直接；二是方便模型的改進和擴展。圖2表示了模型的工作流程。
　　　

　　我們使用標準C語言在linux下實現了該模型。進行仿真時，各模塊的參數全部放在一個配置文件內，在初始化步驟中對WFQ模型設置參數，仿真結果可以輸出到屏幕上，也可以輸出到文件中，不支持圖形輸出。
　　
　　3．1　信元產生器
　　
　　信元產生器負責生成信元，是模型的數據源，在每個時隙到來時最先運行。根據假設（2），每個端口的信元產生器相互獨立的工作，依據各個會話負載參數p（0≤p≤1），主要產生服從獨立同分布的貝努利到達過程信元：每個時隙內產生信元的數目服從p的0～1二項式分布。產生的信元假如均勻地分配給各個會話，稱為均勻獨立同分布的貝努利過程；否則稱為非均勻獨立同分布的貝努利過程。
　　
　　在模型中，信元的產生只是生成一個復雜的數據結構，并沒有類似現實的信元的具體內容，釋放這個數據結構的過程模擬了信元的輸出過程。
　　
　　3．2　交換結構
　　
　　交換結構主要負責信元的傳送，完成輸入與輸出端之間的連接。本模型提供一種邏輯的支持輸出排隊的交換結構，當輸入端產生信元后，負責將信元傳送到正確的目的地，即把產生的信元元素轉移到輸出緩存中。
　　
　　此外，交換結構還負責為每個到達的信元計算時間標簽，與式（1）不同的是，這里只為會話i維護2個時間標簽：會話i當前等待調度的信元的服務結束時間標簽F（i）和會話i的服務結束時間標簽SF（i）（會話最后一個信元的服務結束時間標簽），并不需要為每個信元記錄時間標簽。和“WFQ調度器”協助工作，共同完成信元的調度輸出。
　　
　　3．3　輸出隊列
　　
　　由于信元在輸出端發生輸出競爭，為了緩解擁塞，需要設置輸出隊列用于緩存信元，并負責隊列的治理。模型中輸出隊列包含2部分：輸出緩存和WFQ調度器。
　　
　　輸出緩存用于存儲等待發送的信元，每個邏輯獨立的輸出緩存只為一個會話服務。每個輸出隊列中只包含N個輸出緩存，每個輸出緩存對應一個輸入端。輸出緩存使用雙向鏈表實現，鏈表的數據項為信元。如上所述，每個輸出端維護N個這樣的鏈表。
　　
　　WFQ調度器負責按SFF策略調度并輸出信元，同時更新系統虛時間函數。WFQ調度器每個時隙執行一次。具體形式化描述見文獻［4］。
　　
　　4　仿真結果
　　本節主要對基于信元的WFQ模型進行仿真研究，分析了帶寬分配公平性性能，并與FIFO做了比較。為繪圖清楚，假設每個輸出端有4個會話，對于輸出端1，4個會話分別標示為flow（1，1），flow（2，1），flow（3，1）和flow（4，1），預約歸一化帶寬為0．4，0．3，0．2，0．1，并且每個會話負載是相同的。
　　
　　在上述數據流到達情況下，圖3和圖4分別表示在FIFO和WFQ調度下帶寬的分配。
　　
　　（1）當各會話負載p≤0．25時，輸出隊列能滿足他們的帶寬需求，因此在FIFO和WFQ分配給各會話所需的帶寬。
　　
　　（2）當p＞0．25時，FIFO不考慮各會話的預約，將帶寬平均分配給4個會話，這違反了文獻［1］中的公平性原則。也就是說，FIFO不具備公平排隊的能力。而對于WFQ，我們從圖4中可以看出，當p＞0．4時，各個會話帶寬需求都超出他們的預約，WFQ則按預約帶寬分配給相應的會話。當0．25≤p≤0．4時，WFQ仍然是公平的。
　　　

　　5　結　語
　　本文主要對基于固定長度的信元排隊的WFQ進行了建模和仿真研究。首先分析了基于信元排隊的WFQ和實現的方法，該方法充分利用信元輸出時間固定的特點，在間隔相等的固定時刻更新系統虛時間函數。這種方法非凡適合使用固定時間驅動的方法實現，具有高效、簡單的特點。這些為模型的建立奠定了基礎。接著提出了基于信元排隊的WFQ模型，并分析了各個組成部分。最后對基于信元的WFQ模型進行了仿真研究，從帶寬分配公平性指標與FIFO做了比較。仿真結果表明：基于信元排隊的WFQ適用于高速路由器／交換機中。

上一篇：Cisco系列路由器密碼恢復研究與實踐

下一篇：電信級核心路由器的擴展性