Round-Robin輪詢(xún)調度機制在多隊列處理中的應用

　　前言

　　本文主要介紹了虛擬化路由器的結構以及其中的關(guān)鍵調度機制的算法和實(shí)現，通過(guò)多級的調度處理，實(shí)現了支持多個(gè)可靈活配置，線(xiàn)速轉發(fā)的路由實(shí)例的虛擬化路由器。本文所提到虛擬化路由器實(shí)際設計名稱(chēng)為“IsoRouter”，它基于NetFPGA板卡，本文所介紹的調度機制不針對具體某一型號的FPGA，它可以在任何一款FPGA上實(shí)現。

　　調度算法設計

　　輪詢(xún)調度(Round-Robin Scheduling)算法就是以輪詢(xún)的方式依次調度不同的請求或者隊列。即每次調度執行i = (i + 1) mod n，并選出第i個(gè)隊列進(jìn)行處理。算法的優(yōu)點(diǎn)是其簡(jiǎn)潔性，它無(wú)需記錄當前所有連接的狀態(tài)，所以它是一種無(wú)狀態(tài)調度。雖然該算法十分簡(jiǎn)單，但是卻不斷被證明是十分有效的，且在各種設計中被廣泛采用。

　　傳統的路由器結構

　　在傳統的基于流水線(xiàn)的路由器結構中，流水線(xiàn)設計如圖1所示。

　　流水線(xiàn)包括這幾個(gè)部分：輸入隊列1-8，輸入調度模塊，數據包處理，輸出調度模塊，輸出隊列1-8。