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

Scheduling Algorithm for Packet Switching Based on Network Coding

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

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.