一种受约束排队系统的控制方案

本发明属于一种对流经网络通讯系统的信息进行控制的方案，包括实现方法及器件。

为适应当前的网络在规模上和需求容量上的迅速增长，近期有一个趋势是将快速包交换 机作为新一代路由器的底层硬件。因此极需设计一种可满足不同网络环境的数据包交换机体 系结构。采用该体系结构生产的数据包交换机可以部署在从接入网到骨干网的不同位置。为 达到此目的，采用的交换机体系结构必须要有很好的扩展性。交换机的扩展性主要决定于所 用的排队策略，即供排队之用的缓冲区所处的位置及其组织机制。一般地，排队方案可分为 输入端排队、中央排队、输出端排队或前者间之组合。在各种方案中，输入端排队具有最好 的扩展性。然而，一个输入端排队的交换机达到高性能的关键是设计一个高效控制方案来控 制数据包经过该交换机的延迟。

本文给出一种结合流量控制及动态调度的高性能数据交换机控制方案。该方案可用来控 制各数据包经过输入端排队交换机的延迟以取得可预期的交换机性能。然而，该方案的应用 并不仅仅局限于输入端排队交换机，其应用包括有线网和无线网、电子网和光纤网，等等。 根据这些具体应用，我们抽象出一个受约束排队系统模型，并以该模型为参照展开对本发明 的论述。

一个NxM的受约束排队系统有N个发送源和M个目的站。该受约束排队系统地时间 以离散的时间段为单位。经过流量控制后到达该系统发送源的数据包(或称顾客)在他们被 调度传送到目的站以前将在发送源的缓冲区排队。不失一般性地，我们假设数据包仅在时间 段的开始到达该系统的发送源。到达发送源后的数据包将在各个时间段内被我们的DSDP方 法调度其传往各相应目的站的次序。依据此次序，各个数据包将在各时间段的结束被传送到 相应目的站。各个数据包的传送时间以时间段为单位来度量。如不加说明，每个数据包的传 送时间假设为一个时间段。每个数据包的传送延迟定义为其到达相应发送源及目的站的时间 间隔。而有限的互连网络资源仅在同时建立的路径相互间没有共同的发送源和目的站的情况 下可同时建立连接多个发送源及目的站间的路径。以上所述的受约束排队系统是一系列网络 的抽象模型，例如，输入端排队的交换机、波分光纤网、无线网等等。

经过流量控制后在同一时间到达该受约束排队系统的不同发送源的数据包有可能要被送 到相同的目的站，其结果是造成发送源对目的站的竞争。这些竞争必须用某种方法来加以解 决。在竞争中获胜的数据包将沿着建立的路径被传送到它们的目的站。而在竞争中失败的数 据包则继续在相应的缓冲区内排队，以候下次调度。用来组织排队的机制及解决发送源对目 的站的竞争方法是影响该受约束排队系统性能的关键因素。解决多个数据包在发送源对目的 站的竞争是该受约束排队系统所用调度方法的主要任务。下面，我们先讨论该受约束排队系 统中数据包在发送源缓冲区内的排队机制，然后在第五节中再给出构成本发明的控制该受约 束排队系统达到预期性能的控制方案。

每个发送源缓冲区中的数据包按它们的目的站来进行组队，亦即是要送到同一个目的站 的数据包组成一条独立的队列。因此对一个NxM的系统而言，每个发送源缓冲区最多可有 M个队列，而整个系统最多可有NxM个队列。此组队方式可有效地解决困扰先进先出队列 的所谓队头堵塞问题。(在先进先出排队方式中，每个发送源在其缓冲区中仅维持一条队列 来对所有到达该发送源的数据包提供缓冲。)每个队列中的数据包以它们的目的站优先级来 进行排队。因此在每个队列中排头的数据包具有该队列中所有数据包的最高目的站优先级。 关于各数据包的目的站优先级的详细定义及用途，我们稍后再述。

图1给出了如上所述的一个3x3的受约束排队系统。

现阶段已有多个对一种称之为虚拟输出端排队交换机的输入端排队交换机的调度方法[文 献1，3，4，6，7，8，9，10，11，12，13，14，15，16，17，18，19]。这些现存的方法可根据它们可否控制 各个数据包通过交换机的延迟大体上划分为两大类。

一个NxM的虚拟输出端排队交换机实际上也是一个受约束排队系统。在一个虚拟输出 端排队交换机中，每个输入端(亦即是发送源)有一个缓冲储存区。该(物理)缓冲区由M 个(逻辑)队列组成。每个队列对应一个输出端(亦即是目的站)，即该队列被单独用来容 纳所有从该发送源到所对应的输出端的数据包。该交换机的输入端和输出端间以一个交换网 络相连。调度方法的任务是在每个时间段里根据所排队数据包的状态来控制交换网络以建立 传送相应被选中数据包的路径。大部分现存的方法都以提高交换机的吞吐量为目标，仅极少 数几个可以控制各个数据包通过交换机的延迟。然而，这几个方法都存在着复杂度高和实现 难度大的问题。

在文献中，每个时间段里对排队数据包的调度通常被描述成根据系统当前的负载矩阵来 出一个配对矩阵。负载矩阵及配对矩阵中的行和列分别对应被调度虚拟输出端排队交换机 的输入端和输出端。负载矩阵的每个元素是一个二元式(Wi，Wo)，该二元式中的Wi和Wo 分别代表对应队头数据包的发送源和目的站优先级。不失一般性，一个为“0”的元素代表 其所对应的队列为空。如果Wi和Wo总是相等的，二元式(Wi，Wo)可用一个标量W来表 示。根据一个负载矩阵所出的配对矩阵由值为“0”或“1”的元素组成。在每个配对矩阵 中，每行或每列最多可有一个“1”。由配对矩阵中值为“1”的元素所构成的行和列间的一 一映射可用来控制交换网络以建立相应之路径。

根据负载矩阵来配对矩阵是图论中的一个典型匹配问题[文献2]。以所出的配对矩 阵依其性质可分为最大的、最优的或稳定的。其中又以出最大配对矩阵的算法的复杂度最 低。图论中对各种匹配问题已研究得相当透澈。对将之应用到虚拟输出端排队交换机而言， 主要任务是如何设计具有特定性质的匹配方案以达到所期望的交换机性能。在已有的基于数 据包的发送源和目的站优先级的匹配方法中，计算各数据包的发送源优先级需要额外的存储 空间和运行时间，因而限制了其在极高速环境下的应用。

本发明的目的是提供对一种受约束排队系统的高效控制方案以控制该系统达到预期的性 能，亦即达到性能可控的目标。

控制各个数据包的延迟是使一个受约束排队系统达到此目标的根本途径。为达到控制各 个数据包的延迟的目的，现存的研究已在输入端排队交换机的环境里作了一些努力及设计了 一些方案。不同方案间的区别主要在于如何从排队中的数据包状态来获得解决多个数据包对 发送源和目的站的竞争所需的调度信息。与其它方案不同的是，我们将调度方法与流量控制 相结合的控制方案是唯一的且是创造性的。主要表现在其所达到的高效、高性能、极低复杂 度以及易于在极高速下的物理实现。

该方案中的DSDP调度方法创造性地根据在各发送源缓冲区中排队的顾客的目的站优先 级进行动态的、高速的最大配对调度。将该调度方法与对到达各发送源的数据包进行流量控 制的方法相结合，形成了我们可控制各数据包通过交换机的延迟的高效方案。将其应用到实 际的受约束排队系统中，可实现高速、性能可控和大规模的数据交换机或路由器。而实际的 受约束排队系统还包括其它一系列的通讯系统，如无线网络和波分光纤网络，等等。

具体地，我们发明的控制方案由对到达该系统发送源的数据包的流量控制和对等候于发 送源缓冲区内的数据包的动态调度两大部分组成。流量控制的任务是在给定的系统参数下， 控制到达该系统发送源的数据包的到达过程，以使等候于各发送源缓冲区内的数据包数目维 持在预定的范围内。而动态调度的任务则是在各时间段里，对各个队列中排头的数据包进行 满足以下限制的、往其目的站的传送调度：在每个时间段里，每个发送源最多可以传出一个 数据包和每个目的站最多可以接收一个数据包。详细地，在每个时间段的开始，调度方法对 各个队列的队头数据包进行满足该限制的调度。然后在每个时间段的结束，被调度方法所选 中的数据包将被传送到它们的目的站。图2给出了在一个受约束排队系统中的调度及传送操 作的时序关系。

对到达各发送源的数据包进行流量控制的目的，是令到在各发送源的缓冲区中排队等候 的顾客数目限制在希望的范围内。执行该流量控制的任务可根据系统参数，采用包括仿真、 数学分析或两者相结合、现在已有和将来出现的任何方法来实现。本发明对如何实现流量控 制的方法和形式不加任何限制，而动态调度的任务则由我们发明的以下方法来实现。

在发生对目的站的竞争时，各数据包的目的站的优先级代表了其在解决竞争时的优先程 度，即最高优先级的数据包获胜。对具有相同优先级的数据包间的竞争则可用任意方式来解 决。本发明对如何计算及赋以各数据包其目的站优先级不加任何限制。在各数据包已被赋以 其目的站优先级的前提下，在每次对各队列的队头数据包进行的调度中，我们的调度方法 出满足以下条件的一个调度集：假设Cij是一个在发送源i的缓冲区中等候送往目的站j的 队头数据包，如果数据包Cij不在该调度集中，则该调度集至少包含一个这样的数据包： 该数据包或在发送源i，或要送到目的站j且具有比Cij高的对目的站j的优先级。

以上已对本发明所涉及的受约束排队系统中的对数据包的流量控制、排队机制、调度策 略和传送过程作了简要描述。其中的流量控制和调度策略是本发明的两个组成部分。而调度 策略作为系统参数之一，又是进行流量控制的基础。因此在以下的内容里，我们将进一步对 本发明的核心，即调度策略，作出实现方法上的探讨和给出具体的例子。

设计可用于虚拟输出端排队交换机的调度方法是一个近期内急待解决的问题。不幸的 是，现存的方法不但复杂而且难于实现，因而导致较差的交换机性能。本节给出可用于高速 虚拟输出端排队交换机的DSDP调度方法。该方法具有一般通用性，其应用并不仅仅局限于 输入端排队交换机，还可用于包括有线网和无线网、电子网和光纤网等等的网络。

首先，我们列出一些用以简明后随论述的符号：

●Cij：一个在发送源i的缓冲区中等候送往目的站j的队头数据包。

●DPL[j]：由在所有发送源中排队且要送到目的站j的队头数据包所组成的有序表。该 表中的每个元素是一个变量：DP。每个表中的元素对应一个队头数据包。该表因而 最多可有N个元素。当一个要送到目的站j的数据包成为一个新的队头数据包时， 其对应的元素将被加入到该有序表中。当一个数据包被传送到目的站j后，其对应 的元素将从该有序表中删除。

我们的DSDP方法简述如下：

第一步：初始化，以建立优先级数据结构并使系统处于调度状态；

第二步：将对应每个目的站的队头数据包按其目的站优先级来进行从高到低的排序；

第三步：根据各队头数据包的状态，出一个发送源和目的站间的最大配对。(一个配 对是最大的当且仅当任何未配对的发送源和目的站间没有可供调度的数据包。) 该最大配对满足以下条件：如果数据包Cij未被配对，则至少有一个这样的数据 包被配对：该被配对的数据包或在发送源i，或要送到目的站j且具有比Cij高 的目的站优先级。

以上所示的DSDP方法的第三步需要执行以下的调度任务：根据排队中的队头数据包的 目的站优先级，通过循环配对的过程来进行发送源和目的站间的配对。如果一个发送源和一 个目的站在调度任务中被配对，一条连接该发送源和目的站的路径将由发送源和目的站间的 互联网络建立用以传送相应的队头数据包。

为叙述简单起见，当我们说一个数据包Cij被配对时，其意是指第i个发送源与第j个目 的站被配对。而当我们说一个数据包的发送源和目的站时，其意是指该数据包所在的发送源 和该数据包所要传往的目的站。另外，我们定义一个数据包是自由的当且仅当该数据包的发 送源和目的站都是未配对的。 用于DSDP方法中第三步的最大配对过程可通过以下循环方式来实现： 配对法：在每次循环中，如果自由数据包Cij在所有要传送到第j个目的站的、自由的

队头数据包中具有最高的目的站优先级，则自由数据包Cij将被配对。

给出的DSDP方法可用任何现在已有或将来出现的程序语言实现及应用到任何所述的受 约束排队系统中。

现存的基于最大配对方法的调度方法有以下的缺陷：

1．所有的数据包的长度被假设是固定的。现存的基于各数据包的目的站优先级的 最大配对方法没有提供对变长数据包的处理。

2．现存的基于最大配对方法的方案为了控制各数据包通过交换机的延迟，除了需 要利用各数据包的目的站优先级，亦需要利用各数据包的发送源优先级。

3．现存的方法大多根据各数据包的目的站优先级来计算其发送源优先级，此举加 重了高速环境下的计算负担，因而增加了实现难度。

以上所列现存方法的三大缺陷是设计一个应用于极高速环境下的高性能方法时所必须克 服的。我们的调度方法仅需要各数据包的目的站优先级来进行调度。此外，以统一的方式对 定长和变长数据包进行不加区别的调度。

我们的调度方法对每个数据包分配一个变量DP来代表其目的站优先级。不失一般性， 我们假设越小的DP变量值代表的目的站优先级越大。各数据包的目的站优先级代表对应的 数据包在解决目的站竞争时的优先次序。本发明对如何定义和计算每个数据包的目的站优先 级不作任何限制。

我们所要解决的是如何利用各数据包的目的站优先级来控制其通过交换机的延迟。在对 这一关键问题的解决上，我们的方法是与众不同的。具体表现在其所达到的性能上，主要有： 1．极高速：一个调度方法的复杂度由两大部分组成，即是，配对方法和计算每个数据    包的发送源及目的站优先级。与现存的方法相比，因为不需要计算各数据包的发送    源优先级，所以我们的调度方法有极低的复杂度。此外，由于在配对过程中不存在    要考虑各数据包的发送源优先级的问题，配对方法的复杂度可降到最低。 2．对服务质量的有力支持：对服务质量提供支持的能力强弱是评价未来的交换机系统    性能的一个主要指标。我们将流量控制与调度方法相结合的方案可控制每个数据包    通过交换机的延迟，因而为设计不同的服务质量保证方法提供最大的自由度和支    持。 3．易于实现：与现存的其它方案相比，我们的方案可进一步减低其所调度系统的实现    难度。 4．优良的扩展性：我们的方案可用于从小到大、不同规模的约束排队系统，而其复杂    度仅随系统规模的增大而缓慢增长。 5．可分布性：我们的方法可以分布的形式来实现。其分布实现可进一步降低被调度系    统的实现、扩展和热维护难度。

下面结合附图对本发明作进一步详细的描述。

图1所示的是一个有3个发送源S1[4]、S2[5]、S3[6]和3个目的站D1[8]、D2[9]、D3[10] 的受约束排队系统模型。发送源和目的站间以一个互连网络[7]相连。每个编号的方框代表 一个正在排队的数据包。方框内的编号代表该数据包的目的站。队列[1]、[2]、[3]分别用以 缓冲储存从发送源[4]到目的站[8]、[9]、[10]的数据包。每个队头数据包是其所在队列的最 高优先级数据包。

图2所示的是在一个受约束排队系统中的调度及传送操作的时序关系。如图所示，在每 个时间段的开始，调度方法对各个队头数据包进行调度；然后在每个时间段的结束，被调度 方法所选中的队头数据包将被传送到它们的目的站。

本发明所给出的控制方案可用串行、并行、流水线、软件、固件、硬件或其组合等等的 任何方式来实现。因本发明对该方案中如何实现流量控制的方法和形式不加任何限制，故此 处仅论述对方案中的调度方法的实现。

在8．1至8．2节中，我们给出一个对第5节中所述DSDP方法的软件实现及对变长数据 包的处理。在8．3节中，我们给出运行DSDP方法的体系结构设计及硬件实现。

在(5．2)节中，我们给出了一个配对方法。在每个时间段的开始，该配对方法出发送 源和目的站间的配对。然后在每个时间段的结束，相应该配对的队头数据包将被传送到它们 的目的站。该配对方法可有不同的实现。具有相同效能的配对方法可用各种形式来实现，只 要被该配对方法所配对的发送源和目的站也被此新形式的方法所配对。以下给出一个基于队 头数据包的目的站优先级的并行循环最大配对方法。 并行循环最大配对方法

在此我们给出对上述配对方法的一个并行实现。在方法运行的开始，所有的发送源和目 的站都是未配对的。以下的两个步骤将被重复直到已经执行了min(N，M)次循环或没有新的 配对可建立：

步骤1：每个未配对的目的站向其自由数据包中具有最高目的站优先级的数据包所在的 发送源发出请求；

步骤2：每个被请求的发送源在向其发出请求的目的站中任选其一来进行答复。

在步骤2中，我们并没有对被请求的发送源如何答复请求中的目的站作任何限制。换言 之，被请求的发送源可用任何特定的方式来答复请求中的目的站。例如，随机，按被请求的 数据包先进先出或后进先出的次序，等等。

在以上的讨论里，我们一直假设所有数据包的长度是固定的。因此将每个被调度出去的 队头数据包传送到其目的站所需的时间也是不变的。然而在有些情况下，各数据包的长度是 可变的，因而导致其从发送源到目的站间传送所需的时间也是可变的。

为了降低被调度系统的实现难度，对变长数据包的调度通常要求每个数据包的传送过程 是连续的。亦即是对任何数据包Cij，一旦被调度开始往其目的站的传送，则其传送过程不 可被其它从发送源i到目的站j的数据包所中断。然而，数据包Cij的传送过程可以被除此 而外的数据包所中断。

为达到上述对变长数据包的调度要求，我们的DSDP方法只需作如后所示的、极小的改 动：当某个数据包于某时间段被调度要送往其目的站，如果与该数据包同队列另有一个数据 包于更早时间已开始其传送而尚未结束，则后者继续其传送过程，而前者将等待下次再被调 度。

实现DSDP调度方法可有多种软硬件体系结构，不能一一列举。以下所举的仅是一个典 型实现。任何对DSDP调度方法的实现并不要求受该典型实现所限。

在调度方法运行的开始，所有的发送源和目的站都是未配对的。DPP处理器根据各个队 头数据包的目的站优先级为所有的M个目的站构造M个DPL表。一个名为排序器的器件 将对每个DPL表中的队头数据包按其目的站优先级来进行从高到低的排序，即，按照每个 三元式中的DP变量值从低到高来排序(我们假设越小的DP变量值代表的目的站优先级越 大)。该排序器可以任何软件、固件、串行或并行硬件的形式来实现。一旦M个PL表被建 立后，在其后的时间里，我们可用二叉插入法来对要加入到一个DPL表中的新队头数据包 以每个时间段加入一个或多个的形式来完成。

接着，配对器将根据各个队头数据包的DP变量值来进行发送源和目的站间的配对。按

照配对结果，互连网络将建立发送源和目的站间的路径来传送被配对的队头数据包。

本发明给出了一种受约束排队系统的控制方案。该种受约束排队系统是一系列网络的抽 象模型，例如，输入端排队的交换机、波分光纤网、无线网及有线网等等。与现存的其它方 案相比，我们的方案在保证被控制系统具有良好性能的前提下不但更加灵活，更重要的是易 于在极高速环境下实现。