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

前言

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

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

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

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

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

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

關(guān)鍵詞： FPGA