通用多速率组播加权公平速率分配理论

研究了通用多速率组播加权公平速率分配问题.首先,给出了一个形式化的多速率组播网络模型,在该模型中考虑了接收者的异构性.在此基础上,定义了通用多速率组播加权Max-Min公平概念,建立了通用多速率组播加权Max-Min公平速率分配基本理论.最后给出了一个解决通用多速率组播加权Max-Min公平速率分配问题的集中式算法,并证明了该算法的正确性.     

Bandwidth guaranteed multicast scheduling for virtual output queued packet switches

Multicast enables efficient data transmission from one source to multiple destinations, and has been playing an important role in Internet multimedia applications. Although several multicast scheduling schemes for packet switches have been proposed in the literature, they usually aim to achieve only short multicast latency and high throughput without considering bandwidth guarantees. However, fair bandwidth allocation is critical for the quality of service (QoS) of the network, and is necessary to support multicast applications requiring guaranteed performance services, such as online audio and video streaming. This paper addresses the issue of bandwidth guaranteed multicast scheduling on virtual output queued (VOQ) switches. We propose the Credit based Multicast Fair scheduling (CMF) algorithm, which aims at achieving not only short multicast latency but also fair bandwidth allocation. CMF uses a credit based strategy to guarantee the reserved bandwidth of an input port on each output port of the switch. It keeps track of the difference between the reserved bandwidth and actually received bandwidth, and minimizes the difference to ensure fairness. Moreover, in order to fully utilize the multicast capability provided by the switch, CMF lets a multicast packet simultaneously send transmission requests to multiple output ports. In this way, a multicast packet has more chances to be delivered to multiple destination output ports in the same time slot and thus to achieve short multicast latency. Extensive simulations are conducted to evaluate the performance of CMF, and the results demonstrate that CMF achieves the two design goals: fair bandwidth allocation and short multicast latency.     

Fair allocation of utilities in multirate multicast networks: aframework for unifying diverse fairness objectives

We study fairness in a multicast network. We assume that different receivers of the same session can receive information at different rates. We study a fair allocation of utilities, where the utility of a bandwidth is an arbitrary function of the bandwidth. The utility function is not strictly increasing, nor continuous in general. We discuss fairness issues in this general context. Fair allocation of utilities can be modeled as a nonlinear optimization problem. However, nonlinear optimization techniques do not terminate in a finite number of iterations in general. We present an algorithm for computing a fair utility allocation. Using specific fairness properties, we show that this algorithm attains global convergence and yields a fair allocation in polynomial number of iterations     

Discrete bandwidth allocation considering fairness and transmission load in multicast networks

As a promising solution to tackle the network heterogeneity in multicasting, layered multicast protocols such as receiver-driven layered multicast (RLM) and layered video multicast with retransmission (LVMR) have been proposed. This paper considers fairness as well as transmission load in the layered multicasting. Lexicographically fair bandwidth allocation among multicast receivers is considered under the constraint of minimum bandwidth requirement and the link capacity of the network. The problem of transmission load in the layer multicasting due to various user requirements is also examined by minimizing the number of layers.     

Group multicast routing problem: A genetic algorithms based approach

To save network resources, multicast transmissions are more and more adopted by the operators when the same content has to reach several destinations in parallel, such as in IPTV services, radio broadcast and video-clip streaming. Though, with respect to unicast transmissions, multicast sessions make the routing problem more complex with huge sets of trees to be evaluated. Additionally, since in the real world several multicast sessions occur simultaneously, the suitable trees for more sessions have to be found concurrently. This problem is addressed in this paper, which proposes the use of the genetic algorithms (GA) to reduce the number of solutions to be evaluated. Firstly, a heuristic procedure is employed to generate a set of possible trees for each session in isolation; secondly, the GA are applied to find the appropriate combination of the trees to comply with the bandwidth needs of the group of multicast sessions simultaneously. The goodness of each solution is assessed by means of an expression that weights both network bandwidth allocation and one-way delay. Some key parameters are also introduced that allow the operator to find the desired balance between quality of service and network resource utilization. Experimental results are provided to show the performance of the proposed algorithm compared with alternative solutions in terms of bandwidth utilization and transmission delay and to illustrate the influence of the selection and crossover procedures configuration.     

基于公平服务多维加权轮询调度的IPTV组播流量控制策略

根据大规模接入汇聚路由器（ACR)的总体技术规范,IPTV组播复制在ACR的以太网分合路器（EMD)中进行,而IPTV组播业务的增长会对其他业务造成冲击,因此需要对IPTV组播流量进行控制,以保证其他业务的带宽分配,针对IPTV流量控制中的关键环节──队列调度,提出了一种公平服务多维轮询调度策略(FSMWRR),性能仿真的结果表明该调度策略能够满足IPTV业务的低时延、时延抖动的需求,同时保证各个业务带宽分配的公平性。     

Back pressure based multicast scheduling for fair bandwidth allocation

We study the fair allocation of bandwidth in multicast networks with multirate capabilities. In multirate transmission, each source encodes its signal in layers. The lowest layer contains the most important information and all receivers of a session should receive it. If a receiver's data path has additional bandwidth, it receives higher layers which leads to a better quality of reception. The bandwidth allocation objective is to distribute the layers fairly. We present a computationally simple, decentralized scheduling policy that attains the maxmin fair rates without using any knowledge of traffic statistics and layer bandwidths. This policy learns the congestion level from the queue lengths at the nodes, and adapts the packet transmissions accordingly. When the network is congested, packets are dropped from the higher layers; therefore, the more important lower layers suffer negligible packet loss. We present analytical and simulation results that guarantee the maxmin fairness of the resulting rate allocation, and upper bound the packet loss rates for different layers.     

分层组播中MAX-MIN公平速率分配算法的运用

以分层多速率组播解决方案为研究目标,针对多速率组播与TCP单播共存网络的公平性问题,通过在分层组播中应用max min公平速率分配算法来得到各虚会话的公平速率,并采用二分法对速率集合进行不同粒度上的整合,给出了具体的分层解决策略,从而为异构网络环境中分层多速率组播在公平性前提下的有效实施提供了保障。     

分层组播中INTER-SESSION FAIRNESS问题的分析与对策

通过一组实验结果分析现有分层多速率组播协议的速率控制机制中存在的会话间公平性问题,提出在组播分层解决方案中,以一种基于Max-Min公平性的速率分配计算算法,在网络状态改变时得到共存于网络环境中的各虚会话的公平速率分配集,并辅以二分法,对取值于连续数据集合上的速率分配集进行不同粒度上的离散化整合.实验结果表明该方案使得分层组播在保证会话间公平性的前提下,提高了流量控制的高效性和灵敏性.     

Analysis of bandwidth allocation on end-to-end QoS networks under budget control

This paper considers the problem of bandwidth allocation on communication networks with multiple classes of traffic, where bandwidth is determined under the budget constraint. Due to the limited budget, there is a risk that the network service providers can not assert a 100% guaranteed availability for the stochastic traffic demand at all times. We derive the blocking probabilities of connections as a function of bandwidth, traffic demand and the available number of virtual paths based on the Erlang loss formula for all service classes. A revenue/profit function is studied through the monotonicity and convexity of the blocking probability and expected path occupancy. We present the optimality conditions and develop a solution algorithm for optimal bandwidth of revenue management schemes. The sensitivity analysis and three economic elasticity notions are also proposed to investigate the marginal revenue for a given traffic class by changing bandwidth, traffic demand and the number of virtual paths, respectively. By analysis of those monotone and convex properties, it significantly facilitates the operational process in the efficient design and provision of a core network under the budget constraint.     

多源多播服务功能链优化部署算法

在软件定义网络和网络功能虚拟化环境下,针对多播中的服务功能链（SFC）部署,探究了多源多播中的联合虚拟网络功能（VNF）部署和流量路由问题,目的是最小化节点资源消耗和链路资源消耗总成本。同时考虑到节点、链路及带宽延迟限制,建立了整数线性规划模型,并提出一种名为多源多播树优化的启发式算法。该算法旨在为所有用户找到最近的源节点,获得多个源、目节点组,为每个组构造一棵多播服务功能树,然后优化多播服务功能树。实验仿真结果表明,与其他启发式算法相比,该算法有效地降低了总成本、链路利用率及时延。     

宽带卫星网络中基于Stackelberg模型的下载带宽分配策略*

宽带卫星网络中,下载带宽是非常宝贵的资源。而使用宽带卫星网络下载带宽的用户有着自身的特点,即下载带宽需求量不同。为此,本文将研究高效的的下载带宽分配策略。Stackelberg模型可以解决层次化资源合理分配问题。应用该模型,带卫星网络用户被分成两个组。一组是下载需求量大的用户组;另一组是,下载需求量小的用户组。分别对其建立优化函数,利用Stackelberg求解算法得到各用户最佳的下载带宽。数值仿真实验验证了分配策略的有效性。     

一种REM算法辅助的分层组播流量控制方案

基于分层组播中公平速率分配算法实施过程中存在的问题以及分层组播协议策略中同步点的优化问题,提出了将主动队列管理算法REM作为对端系统的辅助加入到分层组播流量控制中,将分层组播同步点策略、满足Max-Min公平性要求的速率分配算法以及基于REM的显式拥塞指示技术有机地结合起来,设计了一种基于速率的、由接收者和发送者混合驱动的分层组播流量控制方案。仿真实验结果表明该方案使得分层多速率组播在保证会话内、会话间公平性的前提下,提高了流量控制机制的高效性和对网络状态适应的灵敏性。     

基于ECN的单播流与多播流间带宽共享算法

An ECN-based implementing bandwidth-sharing algorithm for unicast and multicast flows is presented.The algorithm uses a bandwidth allocation strategy to give an incentive to multicast flows in bandwidth allocation according to algorithm of the number of receivers, and to assure the unicast flows get their bandwidth shares fairly.Provided best-effort networks, an ECN-based congestion control algorithm is used to implement differentiated service in bandwidth allocation between unicast flows and multicast flows. In implementation, we solve the problems such asreceiver‘s number estimation, the RTT estimation and compromise between convergence and stability.The simulation results show that the algorithm can implement bandwidth sharing for TCP flows and multicast flows. Atthe same time, the algorithm not only allocates more bandwidth to multicast flows, but promises TCP flows to get their fair bandwidth share.     

Performance improvement of dynamic buffered ATM switch

Performance of ATM networks depends on switch performance and architecture. This paper presents a simulation study of a new dynamic allocation of input buffer space in ATM switching elements. The switching elements are composed of input and output buffers which are used to store received and forwarded cells, respectively. Efficient and fair use of buffer space in an ATM switch is essential to gain high throughput and low cell loss performance from the network. In this paper, input buffer space of each switching element is allocated dynamically as a function of traffic load. A shared buffer pool is provided with threshold-based virtual partition among input ports, which supplies the necessary input buffer space as required by each input port. The system behaviour under varying traffic loads has investigated using a simulation program. Also, a comparison with a static allocation scheme shows that the threshold based dynamic buffer allocation scheme ensures an increased network throughput and a fair share of the buffer space even under bursty loading conditions.     

A novel high speed transport protocol based on explicit virtual load feedback

Since traditional TCP congestion control is ill-suited for high speed networks, designing a high speed replacement for TCP has become a challenge. From the simulations of some existing high speed protocols, we observe that these high speed protocols make the round-trip time bias problem and the multiple-bottleneck bias problem more serious than for standard TCP. To address these problems, we apply the population ecology theory to design a novel congestion control algorithm. By analogy, we treat the network flows as the species in nature, the sending rates of the flows as the population number, and the bottleneck bandwidth as the food resources. Then we extend the construction method of population ecology models to design a control model, and implement the corresponding end-to-end protocol with virtual load factor feedback, which is called Explicit Virtual Load Feedback TCP (EVLF-TCP). The virtual load factor is computed based on the information of the bandwidth, the aggregate incoming traffic and the queue length in routers, and then senders adjust the sending rate based on the virtual load factor. Theoretical analysis and simulation results validate that EVLF-TCP achieves high utilization, fair bandwidth allocation independent of round-trip time, and near-zero packet drops. These characteristics are desirable for high speed networks.     

基于混合遗传算法的QoS多播路由算法

具有多QoS约束的多播路由问题具有NP完全的复杂度。基于延时、延时抖动、带宽、丢包率等QoS约束,描述了一种适应于研究QoS多播路由的网络模型,提出了基于遗传算法和禁忌搜索混合策略的具有多QoS约束的多播路由算法。该算法充分利用了遗传算法和禁忌搜索的优点。克服了遗传算法在求解多QoS约束多播路由问题中的爬山能力差以及不成熟收敛等问题。仿真实验结果表明,该算法为多QoS约束多播路由问题的求解提供了一种有效的新途径。     

光纤Mesh网络动态组播业务疏导算法

针对当前低速组播业务请求与光网络高速波长传输容量的问题,基于光网络组播业务疏导模型,提出动态组播业务疏导算法,将新的组播业务请求疏导到已建立的光组播树上,达到提高网络资源的利用率、降低组播业务连接阻塞概率的目的。仿真结果表明,该算法可有效地改善网络性能。     

A sleep-mode interleaving algorithm for layered-video multicast services in IEEE 802.16e networks

In this paper we investigate efficient mechanisms to support layered-video multicast services in IEEE 802.16e (Mobile WiMAX) networks.¹ Given the bandwidth eager and energy hungry nature of layered-video multicast services, network systems should employ efficient bandwidth allocation and energy saving mechanisms. We first investigate how the WiMAX energy saving mechanisms significantly degrade the performance of multicast bandwidth allocation mechanisms for layered-video multicast services. Then, we present a theoretical model for illustrating this interaction problem. To the best of our knowledge, this paper offers the first investigation into and the first theoretical model of the interaction problem between multicast bandwidth allocation and WiMAX energy saving mechanisms. To solve the interaction problem, we propose a novel sleep-mode interleaving algorithm beyond the existing mechanisms. The proposed algorithm has full compatibility with the existing multicast bandwidth allocation mechanisms and with IEEE 802.16e standards. By appropriately adjusting one sleep mode parameter defined in the standard, the proposed sleep-mode interleaving algorithm effectively guarantees the bandwidth efficiency of the video multicast mechanisms while mobile users can execute the standard sleep mode operations. Simulation results demonstrate the effectiveness of the proposed algorithm in terms of packet delivery ratio, user satisfaction, energy efficiency and computational complexity.     

Topology Design of Network-Coding-Based Multicast Networks

It is anticipated that a large amount of multicast traffic needs to be supported in future communication networks. The network coding technique proposed recently is promising for establishing multicast connections with a significantly lower bandwidth requirement than that of traditional Steiner-tree-based multicast connections. How to design multicast network topologies with the consideration of efficiently supporting multicast by the network coding technique becomes an important issue now. It is notable, however, that the conventional algorithms for network topology design are mainly unicast-oriented, and they cannot be adopted directly for the efficient topology design of network-coding-based multicast networks by simply treating each multicast as multiple unicasts. In this paper, we consider for the first time the novel topology design problem of network-coding-based multicast networks. Based on the characteristics of multicast and network coding, we first formulate this problem as a mixed-integer nonlinear programming problem, which is NP-hard, and then propose two heuristic algorithms for it. The effectiveness of our heuristics is verified through simulation and comparison with the exhaustive search method. We demonstrate in this paper that, in the topology design of multicast networks, adopting the network coding technique to support multicast transmissions can significantly reduce the overall topology cost as compared to conventional unicast-oriented design and the Steiner-tree-based design.