Round-Robin轮询调度机制在多队列处理中的应用

前言

本文主要介绍了虚拟化路由器的结构以及其中的关键调度机制的算法和实现，通过多级的调度处理，实现了支持多个可灵活配置，线速转发的路由实例的虚拟化路由器。本文所提到虚拟化路由器实际设计名称为“IsoRouter”，它基于NetFPGA板卡，本文所介绍的调度机制不针对具体某一型号的FPGA，它可以在任何一款FPGA上实现。

调度算法设计

轮询调度(Round-Robin Scheduling)算法就是以轮询的方式依次调度不同的请求或者队列。即每次调度执行i = (i + 1) mod n，并选出第i个队列进行处理。算法的优点是其简洁性，它无需记录当前所有连接的状态，所以它是一种无状态调度。虽然该算法十分简单，但是却不断被证明是十分有效的，且在各种设计中被广泛采用。

传统的路由器结构

在传统的基于流水线的路由器结构中，流水线设计如图1所示。

流水线包括这几个部分：输入队列1-8，输入调度模块，数据包处理，输出调度模块，输出队列1-8。