Round-Robin輪詢調度機制在多隊列處理中的應用

前言

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

調度算法設計

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

傳統的路由器結構

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

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

關鍵詞： FPGA