应用网络编码的分组交换调度算法

基金项目：国家高技术研究发展计划(“863”计划)资助项目(2007AA01Z218)；国家自然科学基金资助项目(60872010、60872005)

    现代网络技术的发展要求交换设备不仅能提供大的交换容量，同时还需要能够对多种网络业务提供良好的服务质量(QoS)。输出排队(OQ)交换结构在提供QoS保障方面极具优势，它能够为业务流提供吞吐量、速率以及时延等多方面的QoS保障[1]。然而要实现N×N 的OQ交换结构，其交换单元和存储单元都必须工作于线路速率的N 倍，这使得OQ交换结构在构建大容量交换结构时实现代价过高，有时甚至无法实现。比较而言，由于输入排队(IQ)交换结构的交换单元和存储单元均只需工作于线路速率[2]，因而对于构建大容量交换结构是一种十分经济的解决方案。但是IQ交换结构需要采用集中控制的调度算法[3]，这使得采用IQ交换结构实现服务质量保障十分复杂。

    虽然交换结构领域的研究取得了一定的进展，但如何构建可提供QoS保障的大容量交换结构依然是一个难题。一种新的研究思路是构建能够完全模拟OQ交换结构的新型交换结构，从而使交换结构不仅可以提供大的交换容量，同时还可以提供QoS保障。基于这一思想，研究人员提出了联合输入输出排队(CIOQ)交换结构，并证明了该交换结构在2倍加速时能够完全模拟OQ交换结构[4-7]。然而CIOQ交换结构模拟OQ交换结构同样需要集中式的匹配算法。更重要的是，在实现组播服务时，即便允许扇出分离，以上结构依然无法达到100%的吞吐率[8]。事实上，要达到100%吞吐率所需要的最小提速随着交换规模的增长是没有上限的。

    然而，随着网络编码理论的提出和发展，为在CIOQ交换结构中实现组播带来新的启发。结合网络编码，交换结构可以承载不采用编码时所不能承载的流量模式，特别地，在实现组播服务时，具有更大的速度区域，在某些流量模式下，可以达到100%的吞吐率。并且，所需最小提速的上限相对也得到降低。本文所讨论的这种在CIOQ交换结构中结合网络编码应用的交换调度算法称为最大权重稳定集(MWSS)算法，是采用图论方法来进行表征的。

1 基本的交换调度算法及结构
    由于对信息流进行了缓存以及实际流量的特性，信元在通过交换结构时，很可能会引起输出端口及内部链路的争用问题，因此必须对交换进行调度匹配来解决这个问题，以获得更大的吞吐率。

1.1 基于虚拟输出队列交换的调度
    基本的输入缓存交换模型如图1所示。这种交换结构的每个输入前面由先入先出(FIFO)队列实现，它用来存储到达的分组。然后调度它们并传输到交换结构。由于排在队头信元(HOL)的目标地址与其他输入已经调度分配好的分组争用而导致该队列后面的信元不能送到空虚的其他端口以前的阻塞，在均衡负载流量模式中，输入缓存结构的总吞吐率限制在58.6%内，在非均衡负载流量模式中更差[9]。

    由于FIFO队列结构吞吐率的局限，图2所示的虚拟输出队列(VOQ)结构已经被广泛用来消除HOL阻塞，因而改善了系统的吞吐率。每一个输入缓存有N 个FIFO队列(N 是交换结构的规模大小)，每一个对应于一个输出端口，因此总共有N 2个FIFO队列。换句话说，到达输入端口i 并要到输出端口j 的分组/信元存储在VOQi,j中。VOQ里的每一个HOL信元在任意时隙内均可以被调度传输。然而，在N个VOQ中，至多可以选择一个信元传输。

    信元到达输入端口i 是一个随机的过程Ai(t )。在每一个时隙内，每个输入端口至多有一个信元到达。到达输入端口i 并要到输出端口j 的信元放入队列Qi,j中。时隙t 时刻，Qi,j的队列长度记为Li,j(t )。
Ai,j(t )表示从输入i 到输出j 速率为λij的到达过程，A(t )={Ai,j(t ),1≤i≤N 和1≤j≤N }。如果到达每个输入输出端口的信元是可容纳的，也就是：

    信元的到达是一个独立的过程，满足下列两个条件：

    (1)到达每个输入端口的所有信元是独立的，并且服从同样的分布。

    (2)到达一个端口的所有信元独立于到达其他端口。如果到达的速率是一样的，且信元的目的地对所有输出端口均匀分布，那么到达的信元流量就称是均衡分布的。

    吞吐量和时延用来评价一个交换的性能。吞吐量的定义是一个时隙内传输的平均信元数，时延的定义是一个信元从接收到由离开输出端口所经历的时间。如果预期的队列长度是有限的，即，那么这个交换结构就被定义为稳定的。如果一个交换在任何独立和可允许的输入流量情况下是稳定的，那么这个交换可以达到100%吞吐率。

1.2 最大权重匹配算法
    在一个双向图中，我们定义wi,j为从输入i 到输出j 的边ei,j 的权重。VOQ的权重通常是指VOQ的长度，即积压在队列中数据分组的数目。在最大权重匹配(MWM)中，对于一个双向图来说，M 是使∑e(i,j )∈M wi,j 最大的值。如图3所示。图3是一个最大权重匹配的例子。

    定理：对于任意允许的流量模式，最大值匹配算法可以达到100%的吞吐率[10]。

    MWM可以在O(N 3)[11]时间内求解，这对于高速数据分组交换而言太长了。通过仔细地选择每条边的权重，或者使用MWM的近似方法，可以减少计算最大值权重匹配的复杂度。

    最长队列优先(LQF)和最旧信元于优先(OCF)是两种不久前被提出来的MWM算法。LQF算法采用队列的长度Lij(t )作为权重wij(t )，而OCF用HOL信元的等待时间作为权重wij(t )。在允许的流量下，这两种方法可以达到100%的吞吐量。在非许可流量模式下，LQF将发生队列长期得不到服务的情况，而OCQ则不会。为了降低LQF的复杂度，提出了最长端口优先(LPF)算法，其权重wij(t )定义为端口的占用情况：其中，。由于LPF的权重不等于队列长度，它同时具有最大尺寸匹配(MSM)和MWM的优点。

1.3 最大尺寸匹配
    最大尺寸匹配(MSM)得到含有最大数目的边匹配。显然，最大尺寸匹配是最大权重匹配当每个边的权重都为1时的特殊情况。MSM的时间复杂度是o (N 2.5)[12]。图4所示的是最大尺寸匹配的例子。通过仿真发现，在允许的均匀的流量下，MSM可达到100%的吞吐量。不过，在允许的非均匀流量下，它会导致不稳定和不公平，且对于一些端口来说，它会导致长期得不到服务。

2 结合网络编码的交换调度算法
    在一个CIOQ交换结构中，允许其输入端口扇出分离(组播交换部分服务的能力，即是组播信元只被送到其所有目的输出的一个子集，并在随后的时隙中完成整个服务)和进行流内线性网络编码，为解决传统争用问题，提供了一个新的思路和方向，并在某些流量模式中，提高了交换结构的吞吐率。

2.1 一个网络编码提高组播吞吐率的例子
    考虑如图5所示的流量模式。这是一个2×3交换机，有4个流：1个从入口1到3个出口的组播流A，和3个分别从入口2到出口1、2和3的单播流B、C 和D。4个流的归一化流量载荷分别被设定在2/3、1/3、1/3、1/3的到达速率。

    即便交换允许扇出分离也无法达到这个流量模式。为了证明这一点，可以发现在调度的整个过程中，入口2的单播中的一个必须得到服务，因为它是一个饱和输入(即总的输入流量为1)。因此，在任何一个时隙里面，一个输出端口被阻塞而一个组播包最多可以发送到其他两个端口。这就意味着至少需要两个时隙来服务每个包，因此一个大于1/2的流量速率是无法达到的。由于要求的速率是2/3，于是组播允许扇出分离仍然无法满足这个流量模式。

    然而，如果扇出分离和流内编码都允许的话，这是可以达到的。事实上，一个二元域上的编码就足够了。只对入口1组播流的分组进行网络编码。对入口1上两个分组块进行编码，然后在3个时隙里发送。考虑组播流的两个分组的一个块{P1,P2}。表1给出了编码，并且指出了编码分组发送到那个输出端口。符号?茌是指两个数据分组按比特异或然后发送。它证实了在第3个时隙的末尾，这个编码可以使每个目的地都可以解码块中的每个分组。

    至于单播流，也可以在这些时隙中并行地得到服务。入口1在每个给定的时间只占用2个出口。因此，入口2可以向第3个空闲的出口发送一个单播包，对每个单播来说1/3的速率是可以达到的。换句话说，给定的编码满足了该例子的所有速率要求。

2.2 基于图论方法的网络编码相关定义
    从上面的例子，可以看出，应用网络编码，交换结构可以完成之前不能实现的流量模式，并满足相应的速率要求，从而获得吞吐率上面的提高。

    下面本文对交换中允许扇出分离和网络编码的条件下，采用基于图论方法进行更深入的讨论。首先从一些定义和一个交换结构排队的假设开始。

    定义1——流：流就是具有共同的源和接收集合的一个数据分组流。用一个包含输入i 和对应于组播流目的端口集合J 的二元组(i，J )表示,J是所有输出端口的一个子集。

    定义2——子流：子流是包含输入i，输出的子集J 以及属于该子集的一个输出j (即j∈J )的一个三元组。
一个子流(i，J，j )是流(i，J )的一部分。

    它是从输入i 流到J的一个特定输出j。一个组播流可以被认为由几个流向一个不同输出的子流组成。

    排队假设：假设对每个流的输入有一个独立的缓存。缓存不一定是FIFO的。事实上，假设在任一时隙，一个输入可以传输一个缓存中所有分组的一个线性组合，然而不可以对不同缓存的内容进行编码。假定普通交换机的约束依然成立——一个输入端口一次可以把同一个分组发送到不同的输出端口，而不可以同时把不同的分组发送到不同的输出端口。一个输出每次只可以从一个输入接收一个分组。在不允许编码的情况之下，假定组播虚拟出口排队结构有重新排队的功能，就如同文献[7]描述的那样。

    由于允许扇出分离，同一个流的子流不互相冲突，即它们的任意子集合可以同时得到服务。然而，一个输入不可以在同一时间把不同的信息发送到不同的输出端口。也不允许对不同流的分组进行编码，于是属于不同流的子流不能同时得到服务。因此，任一子流和同一输入的其他流的子流相冲突。它同时也与有不同输入，但是有相同输出的子流相冲突。这些冲突由下述增强冲突图理论得到描述及规范。

    定义3——增强冲突：给定一个流量模式，增强冲突图G=(V,E )是一个顶点有权的无向图，定义顶点(每个子流都成了图的一个顶点)；边(每个子流都和其他拥有共同入口的流的所有子流相连。另外，每个子流也和所有拥有共同出口的子流相连)，权重(每个顶点被赋予一个等于该子流所属流的速率值)。

    图5中右边的图便是该流量模式的增强冲突图。

    上述定义暗含了在任何有效的交换配置中可以同时得到服务的子流必须是增强冲突图的一个稳定集。
所谓稳定集，就是任意两个不相连顶点的集合[13]。例如，图5中的增强冲突图的稳定集是：{A1,D},{A2,B},{A3,C}。显然，稳定集是可以具有多种不同划分的。

    定义4——增强速率向量：r∈R |F |是一个包含流集合F 流量模式的速率向量。s是这种类型中子流的总数(即所有扇出大小之和)。对应于r 的增强的速率向量e∈R s 的定义如下：
    e (i，J，j )=r (i,J ),?坌j∈J,?坌(i,J )∈F

    于是，增强的速率向量和增强的冲突图的顶点权向量相同。图5显示了例子中流量模式的增强冲突图。需要指出的是，一个特定流的子流的权等于这个流的速率。

    定义5——含新信息分组：一个分组从一个入口被传输到一个出口，如果它包含出口事先不知道的信息，那么它被称为含新信息分组。对于网络编码，这意味着使用线性组合计算分组时的系数和出口已经接收到的所有分组的系数向量线性无关，因此传递了一个新的自由度。

    定义6——虚拟队列：是指和每个子流相关的虚拟队列的概念。当一个数据分组到达其相应的流队列中，被定义为子流虚拟队列的一个到达。一个离开(或者服务)被定义为当为一个子流送传一个含新信息分组。于是虚拟队列的大小代表了为了服务所有已经到达的数据分组而仍需要传输到输出端口的自由度的数目。一个实际流队列的到达速率向量r 转化成为虚拟队列的速率向量e (对应于r 的增强速率向量)。

    定理1：如果允许扇出分离和流内编码，则存在一个基于合适选择的帧大小F 的调度，在一个帧的持续期内，每个虚拟队列最多可以得到e(i,J,j)F 次服务，当且仅当增强速率向量e在增强冲突图的稳定集多面体中。

    证明：(1)充分性。如果e在增强冲突图的稳定集多面体中，那么可以把e表达成图稳定集关联向量的凸组合，这里χS表示稳定集合Si 的关联向量。

    假定Фi是有理数，可以选择一个足够大的整数F 使ФiF 对所有i 都是整数(这个F 也将能够满足e(i,J,j )F 对所有子流都是整数)。把这个F 当作帧大小，可以在不同的由稳定集合表示的交换结构连接配置间恰当地分配时间从而构造一个基于帧的调度。于是，在一个帧的F 个时隙内，对每个i，交换机把稳定集合Si 配置ФiF个时隙。对于每个时隙，稳定集都指出了那些子流得到服务。这个调度具有对每个具有速率r (i,j )的流(i，J )，在它的扇出中的每一个出口j 在一个帧的持续期内接收到e(i,J,j )F =r (i,j )F 次传输的性质。

    (2)必要性。让r表示速率向量，e表示相对应的增强的速率向量。假设存在一个交换结构连接配置的调度以及和每个时隙相联系的编码，使得每个子流都有足够时间接收含有新信息分组，来满足它的速度要求。基于这个可实现的调度，在每个时隙内对每个子流形成一个0-1向量，如果该时隙内的编码传输了一个函数含有新信息分组到该子流，则为1。于是e便是一个帧的所有F 个时隙的指示向量的平均值。但是由于交换机的约束，每个指示向量都是增强冲突图某些稳定集合的关联向量。于是，任何这样的增强速率向量都可以被写成稳定集合的凸组合，这就证明了必要性。

    定义7——速率区域：如果存在一个确保所有虚拟队列强稳定性的调度，则说一个速率向量r是可以达到的。速率区域是所有可达到速率向量的集合。

    强稳定性：如果队列在有限时间内，其分组长度的积压期望值是有限的，则一个队列是强稳定的[14]。

    允许区域：对于一般的图，线性不等式形式的稳定集多面体的完整特征是未知的。但是一些必要条件族是已知的。
一个例子就是团不等式，指的是一个最大团的所有节点的总权重不可以超过1(一个团就是所有的节点两两相连的节点的集合)。对于交换机，可以证明增强冲突图的最大团对应于拥有共同入口或者出口的流。于是，团不等式暗示了所有的入口或者出口都不可以超载。这些也被称为允许条件。这些条件和非负约束描述的多面体为允许区域。

    当且仅当图是完美的[15]，非负约束和团不等式才足以描述稳定集多面体。这引出下面的推论。

    推论1：对于一个给定的流量模式，在扇出分离和流内编码存在的情况下，如果增强冲突图是完美的，则整个允许区域是可达到的。

    定义8——分数权重着色问题：给定一个图G和每个节点的权重WV∈R +，让最小，以至于存在一个G的稳定集合{Si}使，这里w是一个给定的权重向量，χS为稳定集合S 的关联向量。最小化问题的最优值称为分数权重着色数[16]。

    这里把权重理解成相应的流速率，系数λi 理解成调度中时间片。实际上，如果分数权重着色数小于1，那么最优解把权重集合表达成了稳定集合的一个凸组合，它对应于一个交换调度。这就引出了下面的推论。

    推论2：在允许扇出分离和流内编码的情况下，为一个组播流量模式计算离线交换结构调度的问题，等价于把增强速率当成节点的权的增强冲突图的分数权重着色问题。

    实际上，通过对分数权重着色问题的求解，便可得到基于稳定集的流的调度和组合。

    定义9——提速：如果交换结构内部传送分组的速率是交换机入口和出口线路速率的s 倍，则称是一个提速系数为s 交换机。

    如果定义了一个为线路速率倒数的时隙，那么这就意味着交换结构可以在一个时隙中传送s 个连接配置。需要指出的是，如果s >1，则需要出口缓存。到目前为止已经考虑了s ＝1的情况。很容易看出有着提速s 的速率向量r是可以达到的当且仅当它是被允许的，并且位于提速为1时对应的速率区域中。

    如果对于一个给定的速率向量，分数权重着色数c 超过1，那么这样的一个速率向量是不能达到的，原因是它不在稳定集多面体里面。然而如果允许一个等于c 的提速，那么这个速率向量就是可以达到的，这是因为提速实质上把速率向量减小到了原来的c 分之一，这同样使最小化的最优值减小了相同的比例。于是新的速率向量位于速率区域之中。这就为对应于一个给定的速率向量的分数权重着色数给出了一个有趣的物理解释，总结在下面的定理中。

    定理2：扇出和编码存在时，为了达到一个给定的速率向量所需要的最小提速，就要把增强速率向量当作顶点权重的增强冲突图的分数权重着色数。

2.3 在线调度的最大权重稳定集算法
    假定各种流的速度是未知的，并且只用队列的占用情况的信息在线计算调度。类似单播的最大权重匹配算法，可以证明增强的冲突图上的MWSS算法在扇出分离和网络编码允许的情况下，可以达到组播的整个速度区域。

2.3.1 最大权重稳定集算法
    (1)将xi,J,j(t )作为顶点的权重，对应于子流(i,J,j )，计算增强冲突图中的最大权重稳定集。这详细描述了当前时隙将要服务的子流集。如果对于任意选定的子流，xi,J,j(t )是0的话，它将从稳定集中被丢弃。

    (2)对于选定集的每个流，计算一个直至时间t，该流所接收的所有数据分组的线性组合，以使得该线性组合对于该流所有选定的输出端口来说，是一个含新信息数据分组。

    (3)传输已计算好的线性组合到步骤1中的稳定集所选定的子流的输出端口，同时，相应地更新xi,J,j(t )。返回步骤1。
让xi,J,j(t )表示子流(i,J,j )在时隙t的虚拟队列的占用。于是xi,J,j(t )是子流(i,J,j )在自由度中积压的度量。MWSS把这些“虚拟积压”当作权重来计算最大稳定权集合。

    解码数据分组：假定在一个集中式控制系统中一个输出端口知道入口线性组合所用的系数。一个出口可以通过判断一个数据分组系数向量是否在它前面已经接收的分组的系数向量空间中来确定它是否含有新信息。

    每个含有新信息的数据分组算为一个新的自由度，当自由度足够时，出口只需要转换系数矩阵来获得原始的数据分组。于是，如果积压变成0，出口便可以完全解码到该时刻为止的所有数据分组。网络编码确保了每次传输都带来了新的自由度。
引理1：假定V是域大小为q的一个n 维向量空间，V1,V2……Vk是V 的子空间，维数分别是n1,n2……nk。假设对于所有的i＝1，2……k，n >ni。那么如果q大于k，则有一个向量存在于V中，但是不存在任意的Vi中。

    证明：V中向量总的数目是qn。Vi中向量总的数目是q ni。因此中向量中的数目最多是。现在
 ，其中n max是ni的最大值，最大为n -1。于是V 含有的向量数大于。

    定理3：如果流间互相独立，其到达数据是i.i.d.，并且速度向量在Г(推论中1的速度域)中，那么上面给出的MWSS算法把x 稳定在期望值。

    证明：首先需要证明在MWSS算法的第二步，至少存在一个线性组合来确保它对于所有的出口都是含有新信息的。现在xi,J,j是入口知道的维数值和出口j 知道的维数值的差。所以，如果xi,J,j 对于一个出口集是正数，那么情况和引理1中的情况相同。引理中的k个子空间对应于出口已经知道的子空间，而n是入口知道的全部向量空间的维数。于是，引理保证了存在流(i,J )的数据分组的一个线性组合对于所有出口都是含有新信息的，因为域的大小大于所包含的出口的数目。这样的一个组合在第二步被选中。

    证明的其余部分实质上是并行队列情况下文献[18]和文献[19]结论的应用。考虑的队列就是先前定义的虚拟队列。合理激活向量因此对应于子流的无冲突集合，也就是增强冲突图的稳定集合。

    在这些定义下，这种情况和文献[18]中定义的情况唯一不同就是文献[18]假设不同队列的到达是相互独立的。而在这里，同一个流的子流的到达总是同时发生的。然而，这种到达过程独立性的缺失没有影响到文献[18]的结果，本质上是因为相关随机变量的期望值的线性关系。只要其他假设，如到达过程的遍历性和其二次矩的有限性成立，总体的稳定性就依然成立。
只要它们的到达速率在合理激活向量的凸面体，即稳定集多面体中，MWSS算法就稳定了虚拟队列x 的占用。换言之，只要到达速度在Г中，对任意的子流(i,J,j )来说，limt→∞E |xi,J,j (t )|<∞。

2.3.2 有限范围的MWSS算法
    上面的定理表明了MWSS算法可稳定自由度数的积压。但是当一个出口可能以正确的速度接收自由度的时候，不能保证足够频繁地解码，因为要解码数据分组，出口需要接收到和现在用来编码的编码窗口的大小相同的自由度。由于直到t 时到达的所有的分组可能在t 时都用来编码，而编码窗口则继续增加。这也就意味着入口不能够足够频繁地清理它的缓存。

    为了证明缓存也可以被稳定，把算法修改到批模式，称之为有限范围MWSS算法。分组根据它们的到达时间被组成批。基本的观点就是在一个批上运行MWSS算法，然后中断一下来清理该批的积压，于是使得出口可以完全正确地解码。

    在这之后，该批从入口缓存中被冲刷掉，然后重新开始下一个批。这些中断可能导致吞吐率的损失，因为MWSS算法只运行了一部分时间。然而当批的长度足够大时，这个吞吐率损失可以任意的小。

    一个类似的批策略在文献[19]中研究。然而，这里的目的是为了减少重新配置的频率，重新配置即是要估算负载向量。本文不估算负载向量，取而代之的是利用每个时隙的队列占用。具体的算法在下面有更详细的描述。

    批长度记为Δ0，对于所有的k＝0，1，2……，从时间kΔ0+1到时间(k+1)Δ0的所有到达属于批k。一个批的处理只有当其完全到达时才开始。每个批的处理如下：

    对于一个Δ(小于Δ0)个时隙的帧，允许在当前批的分组上运行MWSS算法。为了准确地模仿MWSS算法，提出了这样的约束，在MWSS帧的第k个时隙，即使整个批都是可用的，但是只使用批中第个时隙之前到达的分组来计算权重和编码数据包。这是因为原始的MWSS算法是以在线方式运行的，没有使用未来的到达数据。这个约束允许使用定理3中对有限范围情况的稳定性结果。期望在每一步使用，进而使整个批可以提高性能。

    在帧的末尾部分，交换机通过向每个子流一个接一个的发送足够数量含有新信息的数据分组，来清除当前批的自由度中存在的积压。对于第k批，把清除积压的持续时间记为Tk，这依赖于MWSS留下的积压的数量。于是在Δ0时间内到达的所有分组在Δ0+Tk 时间内清除掉。

    一旦第k批的积压被清除掉，该批的所有分组被冲刷掉，并且一个新的帧开始，而下一个批就在该帧中处理。在新帧开始之前，算法等待第k+1个批完全到达交换机。如果没有等待在交换机中的完全到达的批，并且所有以前的批都被服务了，则系统处于空闲状态。所有其他的时间称之为忙状态。一个典型的批处理实例如图6所示。

    定理4：如果到达的数据包是i.i.d，和流相互独立，并且平均到达速率向量严格地在Г内，这时，便存在可选择的Δ和Δ0，使有限范围MWSS算法保证交换中缓存的稳定性。在这个意义上，系统可以1的概率有限地经常性地到达一个空闲的状态。
证明：用MWSS算法在自由度方面的稳定性来说明，对于每个批数据，与帧Δ的大小相比，其期望的积压消除时间可以是所需要的任意小的值。

    对于严格地在速率区域内的任意速率点r，?埚ε>0，s.t.(1+ε)r同样也在速率区域内。选择Δ0=(1+ε)Δ。考虑一个单独的MWSS帧。至于涉及到的算法，其到达过程表现得像原来到达过程一样，除了时间轴被一个因子压缩外。结果是，MWSS算法得到一个有效到达速率，由于该有效速率在速率区域内，根据定理3，积压xi,J,j (t )的期望值是稳定的。

    所有子流的积压消除周期Tk本质上是在MWSS帧最后的积压自由度之和，即是，Tk(Δ)=∑(i,J,j )xi,J,j (Δ)。因此，Tk的期望值同样是稳定的，即是limt →∞E [Tk(t )]<∞。服从。选择足够大的Δ，使得 。

    系统处于一个繁忙的状态时间，称为一个繁忙周期。可以证明一个单独的邻接的繁忙周期，有限持续时间的概率是1。这意味着，系统将以1的概率经常性地在有限时间内变成空闲。考虑一个单独的繁忙周期，在该繁忙周期里的第n批数据的等待时间记为Wn。这是在交换中批数据完全到达的时间和服务之后批数据被完全清空的时间之差。

    在一个繁忙周期内，Wn通常要大于Δ0。当Wn降到Δ0之下的时候，繁忙周期便结束，因为任意批数据只在前一周期后的最后Δ0个时隙到达。因此，需要证明Wn最终会降到Δ0之下。现在，。

    所以，Wn<Δ0当且仅当 。由于所有的数据包Ti 都是i.i.d，它对于大的n，以1的概率服从大数定律，
 。o(n)为一函数f (n)，有。现在，由于E[Ti]<εΔ，对于足够大的n，可使。

3 结束语
    在本文中，讨论介绍了在一个CIOQ交换结构中实现组播服务的调度问题。说明了允许在输入端口进行流内线性网络编码的情况下，可以得到更大的速率区域。并举例说明了，使用编码消除提速的要求，以一种稳定的方式，为流量服务。
用图论的方法得到了使用网络编码的交换的速率区域，并提出了在线的算法以达到该速率区域。同时也使用该方法来理解在吞吐率上，流量模式配置的影响，和计算调度的复杂性。在运用图论这个方法上，未来的工作是使用该方法，提出近似的匹配方法和试探，以简化在线调度算法，使之实用。

    使用流内线性网络编码，得到的不仅是吞吐率的提高，同时是一个更具意义的速率区域的描述，使之有运用图论结果的可能性。

    总的来说，网络编码由于编解码以及等待数据的过程，会引起交换有一时延，在对于要求快速交换的结构中，这显然是不利的，然而，当网络负载比较大时，应用网络编码则可以得到比常规情况较小的时延。

4 参考文献
[1] KESIDIS G, MCKEOWN N. Output - buffer ATM packet switching for integrated-services communication networks[C]//Proceedings of International Conference on Communications (ICC'97): Vol 3, Jun 8-12, 997, ontreal, Canada. Piscataway, NJ, USA: IEEE, 1997: 1684-1688.
[2] MCKEOWN N. Scheduling algorithms for input-queued cell switches[D]. Berkeley, CA, USA: University of California, 1995.
[3] MEKKITTIKUL A, MCKEOWN N. A practical scheduling algorithm to achieve 100% throughput in input-queued switches[C]// Proceedings of the 17th Annual Joint Conference of the IEEE Computer and Communications Societies (Infocom’98). Mar 29-Apr 2, 1998, San Francisco, CA, USA. Piscataway, NJ,USA: IEEE, 1998: 792-799.
[4] CHUANG S T, GOEL A, MCKEOWN N, et al. Matching output queueing with a combined input output queued switch[J]. IEEE Journal on Selected Areas in Communications, 1999, 17 (6): 1030-1039.
[5] STOICA I, ZHANG H. Exact emulation of an output queueing switch by a combined input output queueing switch[C]//Proceedings of 6th IEEE/IFIP International Workshop on Quality of Service (IWQoS’98), May 18-20, 1998, Napa, CA, USA. Piscataway, NJ, USA: IEEE, 1998: 218-224.
[6] 伊鹏, 汪斌强, 李挥. 一种可提供QoS保障的新型交换结构[J]. 电子学报, 2007, 35(7): 1257-1263.
[7] HU Hongchao, YI Peng, GUO Yunfei, et al. A fair service and dynamic round robin scheduling scheme for CICQ switches[C]//Proceedings of IEEE International Conference on Telecommunications (ICT’08), Jun 16-19, 2008, St Petersburg, Russia. Los Alamitos, CA, SA: IEEE Computer Society, 2008: 6.
[8] MARSAN M A, BIANCO A, GIACCONE P, et al. Multicast traffic in input-queued switches: optimal scheduling and maximum throughput[J]. IEEE/ACM Transactions on Network, 2003, 11(3): 465-477.
[9] KAROL M J, HLUCHYJ M, MORGEN S. Input vs output queuing on a space-division packet switch[J]. IEEE Transactions on Communications, 1987, 35(12): 1347-1356.
[10] MCKEOWN N, MEKKITTIKUL A, ANANTHARAM V, et al. Achieving 100% throughput in an input-queued switch[J]. IEEE Transactions on Communications, 1999, 47(8): 1260-1267.
[11] TARJAN R E. Data structures and network algorithms[M]. Philadelphia, PA, USA: Society for Industrial and Applied Mathematics, 1983.
[12] HOPCROFT J E, KARP R M. An n2.5 algorithm for maximum matchings in bipartite graphs[J]. SIAM Journal on Computing, 1973, 2(4): 225-231.
[13] SUNDARAJAN J K, MEDARD M, KOETTER R, et al. A systematic approach to network coding problems using conflict graphs[C]//Proceedings of the UCSD Workshop on Information Theory and Its Applications, Feb 60-10,2006, San Diego,CA,SA.2006.
[14] GEORGJADIS L, NEELY M J, TASSIULAS L. Resource allocation and cross-layer control in wireless networks[M]. Hanover, MA, USA: Now Publishers Inc, 2006.
[15] SCHRIJVER A. Combinatorial optimization: Polyhedra and efficiency[M]. Berlin, Germany: Springer Verlag, 2003.
[16] KILAKOS K, MARCOTTE O. Fractional and integral colourings[J]. Mathematical Programming, 1997, 76 (2):333-347.
[17] TASSIULAS L, EPHREMIDES A. Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks[J]. IEEE Transactions on Automatic Control, 1992,37(12): 1936-1948.
[18] TASSIULAS L. Linear complexity algorithms for maximum throughput in radio networks and input queued switches[C]//Proceedings of the 17th Annual Joint Conference of the IEEE Computer and Communications Societies (Infocom’98). Mar 29-Apr 2, 1998,San Francisco, CA,USA. Piscataway, NJ,USA:IEEE,1998: 533-539.
[19] ARMONY M, BAMBOS N. Queueing dynamics and maximal throughput scheduling in switched processing systems[J]. Queueing Systems, 2003,44(3 ):209-252.

收稿日期：2008-11-02

[摘要] 网络编码理论与交换调度算法相结合重点是实现在联合输入输出排队(CIOQ)交换结构中提供组播服务。文章证明了对一个流中的分组进行线性网络编码可以承载不允许网络编码时不能够承载的交换流量模式，也就是说，网络编码允许CIOQ交换结构在实现组播服务时有更大的速率区域，并给出了基于图论方法的描述。运用增强冲突图的稳定集多面体等概念，文章证明了计算离线调度的问题可以简化成某种图染色问题，同时，也针对组播调度提出了一个称之为最大权重稳定集的在线调度算法。

[关键词] 分组交换；网络编码；调度算法

[Abstract] This paper introduces the development of network coding theory in the field of scheduling algorithm for switching system, which focuses on the issue of serving multicast flows in a Combined Input/Output Queuing (CIOQ) switch. By operating linear network coding within packets of a flow, the switching fabric can sustain traffic patterns that cannot be served if network coding were not allowed. That is, network coding has a larger rate region in a multicast CIOQ switch. Moreover, the graph-theoretic characterization was given out. With the concepts of stable set polytope from the enhanced conflict graph, it is pointed out that computing the offline schedule can be reduced to certain graph coloring problems. An online algorithm called maximum weighted stable set is proposed for multicast scheduling based on the graph-theoretic formulation.

[Keywords] packet switching; network coding; scheduling algorithm