保证100%吞吐率的两级组播交换结构

在路由器或交换机的交换结构中实现组播是提高组播应用速度的重要途径之一。传统的交叉开关结构(crossbar)组播调度方案有两种缺陷,一种是性能较低,另一种是实现的复杂度太高,无法满足高速交换的需要。该文提出了一个新的基于交叉开关的两级组播交换结构(TSMS),第1级是组播到单播的交换结构,第2级是联合输入和输出排队(CIOQ)交换,并为该结构设计了合适的最大扇出排队(FCN)优先-均匀分配中间缓存调度算法(LFCNF-UMBA)。理论分析和仿真实验都显示在该结构中,加速比低于22/(N+1)倍时吞吐率不可能实现100%;而采用LFCNF-UMBA调度算法,2倍加速比就可保证在任意允许(admissible)组播的吞吐率达到100%。     

面向可重构服务承载网的分域混合承载组调度研究

传统网络技术体系,网络是封闭的、刚性的,无法满足未来网络大量差异化业务的规模化应用,由此提出了面向服务提供的柔性网络技术体系,该体系将传统网络中的用户业务、网络服务和网络基础设施中的紧耦合关系转变为松耦合关系,通过资源分割构建可重构服务承载网实现对业务的服务质量保证。该文分析了服务承载网映射到交换结构的需求,提出分域调度的思想。通过选择关闭部分交叉节点的方法建立了crossbar交换结构分域模型,实现了分域调度的端口分离。提出了支持可重构服务承载网构建的混合承载组调度(HCGS)算法,推导了承载组内SDRR(Smoothed Deficit Round Robin)调度、单个域内基于时间戳的输入端口调度和交叉节点输出端口调度算法,证明了HCGS具有良好的时延性能和最坏公平指数(WFI)公平性。仿真结果表明:在均匀分布的泊松业务源条件下,分域HCGS算法具有更优的时延性能,可保证业务带宽的公平性。在diagonal非均匀允许流量条件下,该算法的吞吐量可达100%。     

一种用于光组播冲突解决的节点结构及其调度策略

光分组在核心节点处的冲突解决问题是实现全光 组播分组交换的关键。本文提出了一种新型的解决光组播冲突的节 点结构,用于冲突解决的部分包括输出共享的网络编码模块和光纤延迟线(FDL)环 形反馈共享缓存(FDL-LSFB)模块。网络编码 模块将异或网络编码作为冲突解决方式,利用全光异或门将冲突组播进行网络编码并且改变 编码后分组波长,从而避免波长 冲突。而FDL-LSFB模块由子交换矩阵和FDL缓存组连接成环状,且冲突组 播可从任意子交换矩阵进出缓存模块, 使用少数的FDL可以提供大容量的光缓存、提高FDL利用率。针对FDL-LSFB模块冲突组播调 度问题,为减小缓存时延,设计了最小缓存长度级联控制算法(MLCBST),进而提出冲突光 组播的总调度策略。仿真结果表明,本文提出的组播节点结构和调度策略在降低丢包率(PLP)和减小缓存时延方面具有明显的效果。     

输入排队结构交换机分组调度研究

以决定分组调度算法的交换结构为基础,从协调,减少和隔离输入排队交换结构中输入输出竞争裁决冲突的角度,分别讨论了VOQ,CIOQ,CICQ结构中的分组调度问题,并以当前最新的调度算法为例加以说明,进行了定性分析和定量对比,指出了具体有待研究的问题。随后讨论了最近才开始研究的光电混合结构中的分组调度问题。最后从交换结构和算法两个方面探讨了今后的研究方向和发展趋势。     

一种支持扇出分割能力的光组播调度算法研究

组播调度是影响光组播分组交换节点吞吐量的重要因素.针对“一次发送”模型下的光组播调度算法对阻塞的源组播实行全部丢弃的缺点,文章基于节点共享有限波长转换器的光分组交换结构,提出了一种支持扇出分割能力的光组播调度算法,该算法采用随机丢弃阻塞的源组播复制的方法,有效地提高了端口资源的利用率.仿真结果表明,该算法与已有算法相比...     

适合全光组播网络的网络编码技术研究

传统的网络编解码算法需要进行线性运算,只适合在电域中实现。而当前全光器件的发展已经能够实现逻辑运算和移位操作。为了将网络编码引入到全光组播网络当中,文章研究了生成网络编码组播树的算法,以及适合于光网络编码的编码向量选取方法,并对所提出的算法进行了仿真分析。结果表明,将网络编码应用于全光组播中能够显著提高组播性能。     

适合全光组播网络的网络编码技术研究北大核心

传统的网络编解码算法需要进行线性运算,只适合在电域中实现。而当前全光器件的发展已经能够实现逻辑运算和移位操作。为了将网络编码引入到全光组播网络当中,文章研究了生成网络编码组播树的算法,以及适合于光网络编码的编码向量选取方法,并对所提出的算法进行了仿真分析。结果表明,将网络编码应用于全光组播中能够显著提高组播性能。     

图压缩优化光组播最小网络编码路由

将网络编码和光网络相结合可以有效解决光网络的 带宽资源利用率等问题。然而,在光网络中进行编码操作,又将增加光网的光域运算开销、 复杂度和缓存需求。为了减少光网络中网络编码的操作次数,本文提出一种基于图压缩的方 法优化光网络拓扑结构, 结合智能优化遗传算法(GA)实现组播最大速率的光组播最小编码节点,通过对光网络拓扑结 构中的一类特殊潜在编码节点 进行压缩处理,达到缩小算法搜索空间、排除大量非最优解的目的。仿真结果表明,通过本 文图压缩优化后的光网络拓扑结 构,可以使得现有的智能优化GA在求解光组播最小网络编码路由问题时效率更高,寻找到的 解更优。     

MPLS网络中DiffServ组播算法

文章提出一种在多协议标签交换(MPLS)网络中边界路由器实现组播和区分服务的算法,该算法利用处于分支点的边界路由器之间的标签交换路径来传输组播数据包,同时引入了信息管理点,用于计算、管理和调整组播树,实现全域的服务质量.描述了算法的具体细节和实现原理,也评价了该算法的可行性和优越性.     

基于随机线性网络编码的双源交替调度算法

为减少单源组播中链路质量最差的组播成员对组播速率的影响,该文提出了适用于双源可靠组播的静态和动态交替调度算法。算法通过交替传输编码数据包,可充分挖掘组播成员到不同源节点链路质量的差异性。与单源组播相比,理论分析和仿真表明:两种调度算法可以有效提高组播速率,从而减少期望传输时间。动态交替调度算法通过动态更新参数,可以获得更低的期望传输时间。     

Cross-Layer Rate Control, Routing and Scheduling Design for Multicast with Network Coding in Ad Hoc Networks

Network coding is a powerful coding technique that has been proved to be very effective in achieving the maximum multicast capacity. It is especially suited for new emerging networks such as ad-hoc and sensor networks. In this paper, we develop a distributed rate control algorithm for multicast session in ad hoc networks. With random network coding, the algorithm can be implemented in a distributed manner, and work at transport layer to adjust source rates and at network layer to carry out network coding. The scheduling element of our algorithm is a dynamic scheduling policy. The stability of the resulted system is established, and simulation results are provided to support our conclusions.     

Call scheduling algorithms in a multicast switch

Multicast switching is emerging as a new switching technology that can provide efficient transport in a broadband network for video and other multipoint communication services. The authors develop and analyze call scheduling algorithms for a multicast switch. In particular, they examine two general classes of scheduling algorithms: call packing algorithms and call splitting algorithms. The performance improvement by the call packing algorithms examined is shown to be negligible. In contrast, the call splitting algorithms can provide significantly lower blocking by reducing the level of output port contention. However, excessive call splitting could degrade performance because of the additional load introduced to the input ports. The authors present a simple call splitting algorithm called greedy splitting which achieves near-optimal performance     

Matching output queueing with a combined input/output-queued switch

The Internet is facing two problems simultaneously: there is a need for a faster switching/routing infrastructure and a need to introduce guaranteed qualities-of-service (QoS). Each problem can be solved independently: switches and routers can be made faster by using input-queued crossbars instead of shared memory systems; QoS can be provided using weighted-fair queueing (WFQ)-based packet scheduling. Until now, however, the two solutions have been mutually exclusive-all of the work on WFQ-based scheduling algorithms has required that switches/routers use output-queueing or centralized shared memory. This paper demonstrates that a combined input/output-queueing (CIOQ) switch running twice as fast as an input-queued switch can provide precise emulation of a broad class of packet-scheduling algorithms, including WFQ and strict priorities. More precisely, we show that for an N×N switch, a “speedup” of 2-1/N is necessary, and a speedup of two is sufficient for this exact emulation. Perhaps most interestingly, this result holds for all traffic arrival patterns. On its own, the result is primarily a theoretical observation; it shows that it is possible to emulate purely OQ switches with CIOQ switches running at approximately twice the line rate. To make the result more practical, we introduce several scheduling algorithms that with a speedup of two can emulate an OQ switch. We focus our attention on the simplest of these algorithms, critical cells first (CCF), and consider its running time and implementation complexity. We conclude that additional techniques are required to make the scheduling algorithms implementable at a high speed and propose two specific strategies     

面向可重构基础网络的部分扇出组播交换阻塞率模型

传统网络采用调度前复制和扇出拷贝方式的多播交换模型不具备大规模可扩展能力。面向可重构基础网络,提出了一种部分扇出多播交换模型,该模型采用2×2布尔单元和布尔群组集线器建立基本交换结构,采用部分扇出拷贝方式和四状态分割编码实现自路由路径选择,进而推导了该模型在单多播混合业务源输入下的单播阻塞率、多播阻塞率和多播扇出率迭代过程。仿真实验表明:该模型在Bernoulli均匀业务源条件下,单播归一化负载强度为0.2时,多播阻塞率在10 10～10 2之间,多播时延总小于百纳秒量级上限,能够为到达业务提供时延上限保障。     

Multicast with network coding in application-layer overlay networks

All of the advantages of application-layer overlay networks arise from two fundamental properties: 1) the network nodes in an overlay network, as opposed to lower-layer network elements such as routers and switches, are end systems and have capabilities far beyond basic operations of storing and forwarding; 2) the overlay topology, residing above a densely connected Internet protocol-layer wide-area network, can be constructed and manipulated to suit one's purposes. We seek to improve end-to-end throughput significantly in application-layer multicast by taking full advantage of these unique characteristics. This objective is achieved with two novel insights. First, we depart from the conventional view that overlay nodes can only replicate and forward data. Rather, as end systems, these overlay nodes also have the full capability of encoding and decoding data at the message level using efficient linear codes. Second, we depart from traditional wisdom that the multicast topology from source to receivers needs to be a tree, and propose a novel and distributed algorithm to construct a two-redundant multicast graph (a directed acyclic graph) as the multicast topology, on which network coding is applied. We design our algorithm such that the costs of link stress and stretch are explicitly considered as constraints and minimized. We extensively evaluate our algorithm by provable analytical and experimental results, which show that the introduction of two-redundant multicast graph and network coding may indeed bring significant benefits, essentially doubling the end-to-end throughput in most cases.     

一种基于Credit的变长分组并行交换网络调度算法

该文提出了一种新的并行分组交换(PPS)网络调度算法。该算法通过在解复用器处采用以变长分组为业务分配单元的方式消除了信元的乱序问题;通过采用Credit机制进行业务分配,实现了业务到各个交换平面完全公平的分配;各个并行交换单元采用组合输入输出排队,降低了对缓存和交换平面的加速要求,同时可以充分利用现有单Crossbar网络调度算法的研究成果。文中证明了该算法对业务分配的公平性,对高速缓存的需求量以及整个网络的稳定性,仿真进一步证明了该算法具有良好性能。     

Minimum coding nodes multicast tree for two-channel all-optical network coding scheme

A heuristic algorithm of establishing a minimum coding nodes multicast tree on which a two-channel all-optical network coding scheme can be performed is presented.To minimize the coding nodes,the heuri...     

On the stability of local scheduling policies in networks of packet switches with input queues

A significant research effort has been devoted to the design of simple and efficient scheduling policies for input queued (IQ) and combined input-output queued (CIOQ) packet switches. As a result, a number of switch control algorithms have been proposed. Among these, scheduling policies based on maximum weight matching (MWM) were identified as optimal, in the sense that they were proved to achieve 100% throughput under any admissible arrival process satisfying the strong law of large number. On the contrary, it has been shown that the usual MWM policies fail to guarantee 100% throughput in networks of interconnected IQ/CIOQ switches. Hence, new policies suited for networks of interconnected switches were proposed and proved to achieve 100% throughput. All of these new policies require coordination and cooperation among different switches. We identify scheduling policies that require no coordination among switches (and are, thus, said to be local), and that guarantee 100% throughput in a network of IQ/CIOQ switches. The only assumptions on the input traffic pattern are that it is stationary, satisfies the strong law of large numbers and does not oversubscribe any link in the network.     

Flexible multicasting in high-capacity switches

Since packet switches with input queueing require low-speed buffers and simple cross-bar fabrics, they potentially provide high switching capacities. In these switches, the port that is a source of a multicast session might easily get congested with the increasing popularity of this session. We propose the protocol for scheduling packets in switches with input buffers for varying popularity of different content on the Internet. Copies of a multicast packet are forwarded through the switch, so that multicasting is evenly distributed over switch ports. The performance trade-off between capacity that can be reserved and guaranteed packet delay is discussed.