Round-Robin輪詢調(diào)度機(jī)制在多隊(duì)列處理中的應(yīng)用

前言

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

調(diào)度算法設(shè)計

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

傳統(tǒng)的路由器結(jié)構(gòu)

在傳統(tǒng)的基于流水線的路由器結(jié)構(gòu)中，流水線設(shè)計如圖1所示。

流水線包括這幾個部分：輸入隊(duì)列1-8，輸入調(diào)度模塊，數(shù)據(jù)包處理，輸出調(diào)度模塊，輸出隊(duì)列1-8。

關(guān)鍵詞： FPGA