网络中时延受限的代理服务器放置问题

该文考虑网络数据更新,需要控制代理服务器与客户的距离时,网络中的代理服务器的放置问题。找到代理服务器的最优数量和放置位置,使网络中数据访问的总花费（包括数据读取和更新）最小。利用二叉树结构和动态规划方法,得到了一个时间复杂度O（n²）的多项式时间算法,其中n为网络结点数。     

Efficient group communications in location aware mobile ad-hoc networks

The highly dynamic and uncertain character of mobile ad-hoc networks poses significant challenges for group management. Node mobility often changes the multicast tree, and therefore, frequent updates from group members are required to refresh the multicast tree at the source node. This paper presents Courier, a group communications algorithm that uses the location and velocity of roaming nodes to provide bandwidth efficient multicast between a source and its destinations (i.e., group members) in location aware mobile environments. Toward that end, Courier offers (1) a bandwidth efficient method for location updates from group members, (2) a mobility prediction model for predicting the movement of mobile group members, and (3) an overlay multicast data distribution tree (OMDDT) construction algorithm that is guided by the mobility prediction model. Comparisons of Courier to related multicast algorithms indicate an increase in data transmission success and a decrease in overall bandwidth consumption.     

树上时延约束的代理服务器放置问题

该文考虑网络数据更新,需要控制代理服务器与目标服务器的距离时,树状网络上代理服务器的放置问题。利用二叉树结构和动态规划方法,得到了一个时间复杂度O(nhk)为多项式时间算法,其中n为网络结点数,k为代理服务器要放置的个数,h为树高。     

基于P2P系统应用层组播在流媒体中的应用

由于live流是一种高带宽的应用，甚至当为数不多的客户同时采用单播从一个源请求流时，也可以使服务器的带宽饱和。作为有效解决方法的IP组播因为缺乏广泛的支持而逐渐被应用层组播代替。本文在peer-to-peer系统上采用以树为基础的应用层组播结构，实现用客户自己的带宽传输流媒体以缓解服务器附近的拥塞问题。在该结构中，每个客户peer端在应用层与传输层之间加入peering层，实现结点之间的协调和建立、维护组播树。     

Optimal branching factor for tree-based reliable multicast protocols

In recent years, many reliable multicast protocols on transport layer have been proposed. Previous analysis and simulation studies gave evidence for the superiority of tree-based approaches in terms of throughput and bandwidth requirements.In many tree-based protocols, the nodes of the tree are formed of multicast group members. In this case, the branching factor, i.e. the maximum number of child nodes is adjustable. In this paper, we analyze the influence of the branching factor on a protocol's throughput and bandwidth consumption. This knowledge is important to configure protocols for best performance and to optimize the tree creation process.Our results show that the optimal branching factor depends mainly on the probability for receiving messages from other local groups. If local groups are assigned to a separate multicast address, the optimal branching factor is small. On the other hand, if TTL scoping is used and therefore the probability for receiving messages from other local groups is greater than zero, larger local groups provide better performance.     

Multicast Routing Optimization Algorithm with Bandwidth and Delay Constraints Based on GA

Most of the multimedia applications require strict QoS guarantee during the communication between a single source and multiple destinations. This gives rise to the need for an efficient QoS multicast routing strategy. Determination of such QoS-based optimal multicast routes basically leads to a multi-objective optimization problem, which is computationally intractable in polynomial time due to the uncertainty of resources in networks. This paper proposes a new multicast routing optimization algorithm based on Genetic Algorithms, which find the low-cost multicasting tree with bandwidth and delay constraints. The simulation results show that the proposed algorithm is able to find a better solution, fast convergence speed and high reliability. It can meet the real-time requirement in multimedia communication networks. The scalability and the performance of the algorithm with increasing number of network nodes are also quite encouraged.     

一种具有能力约束性能的任意源覆盖多播方法

近年来提出的许多面向单个数据源设计的多播树并不能简单扩展到任意源多播系统中,因为针对每个源建立一个树代价高昂.而已存在的一些允许多数据源的P2P(peer-to-peer)系统的维护量大,在体现结点能力差异等方面缺少灵活性.提出一个任意源覆盖多播服务方案,并具有结点能力约束性能.它建立在非DHT(distributed hash table)覆盖网络上,无须建立显式的多播树.设计了两种分布式多播算法,它们将任意源的多播信息传送到所有结点的期望跳数是O(log_cn),其中,c是平均结点能力,n是多播组中的结点个数.     

A new high performance approach: merging optimal multicast sessions for supporting multisource routing

Each single source multicast session (SSMS) transmits packets from a source node s _i to a group of destination nodes t _i , i=1,2,…,n. An SSMS’s path can be established with a routing algorithm, which constructs multicast path between source and destinations. Also, for each SSMS, the routing algorithm must be performed once. When the number of SSMS increases to N≥2, the routing algorithm must be separately performed N≥2 times because the number of source nodes increase to N≥2 (for each SSMS the routing algorithm must be performed once). This causes that time of computation and bandwidth consumption to grow. To remove this problem, in this paper, we will present a new approach for merging different SSMSs to make a new multicast session, which is performed only with one execution of a routing algorithm. The new approach, merging different sessions together, is based on the optimal resource allocation and Constraint Based Routing (CBR). We will show that as compared to other available routing algorithms, it improves time of computation and bandwidth consumption and increases data rate and network efficiency. The new approach uses CBR and merges more than one single source multicast session (SSMS) problem to one multisource multicast session (MSMS) problem. By solving one MSMS problem instead of solving more than one SSMS, we can obtain an optimal solution that is more efficient than optimal solutions of SSMS problems.     

Uncertain multicast under dynamic behaviors

Multicast transfer can efficiently save the bandwidth consumption and reduce the load on the source node than a series of independent unicast transfers.Nowadays,many applications employ the content replica strategy to improve the robustness and efficiency;hence each file and its replicas are usually distributed among multiple sources.In such scenarios,the traditional deterministic multicast develops into the Uncertain multicast,which has more flexibility in the source selection.In this paper,we focus on building and maintaining a minimal cost forest(MCF)for any uncertain multicast,whose group members(source nodes and destination nodes)may join or leave after constructing a MCF.We formulate this dynamic minimal cost forest(DMCF)problem as a mixed integer programming model.We then design three dedicated methods to approximate the optimal solution.Among them,our a-MCF aims to efficiently construct an MCF for any given uncertain multicast,without dynamic behaviors of multicast group members.The d-MCF method motivates to slightly update the existing MCF via local modifications once appearing a dynamic behavior.It can achieve the balance between the minimal cost and the minimal modifications to the existing forest.The last r-MCF is a supplement method to the d-MCF method,since many rounds of local modifications maymake the resultant forest far away from the optimal forest.Accordingly,our r-MCF method monitors the accumulated degradation and triggers the rearrangement process to reconstruct an new MCF when necessary.The comprehensive evaluation results demonstrate that our methods can well tackle the proposed DMCF problem.     

ACOM: Any-source Capacity-constrained Overlay Multicast in Non-DHT P2P Networks

rdquoApplication-level multicast is a promising alternative to IP multicast due to its independence from the IP routing infrastructure and its flexibility in constructing the delivery trees. The existing overlay multicast systems either support a single data source or have high maintenance overhead when multiple sources are allowed. They are inefficient for applications that require any-source multicast with varied host capacities and dynamic membership. This paper proposes ACOM, an any-source capacity-constrained overlay multicast system, consisting of three distributed multicast algorithms on top of a non-DHT overlay network with simple structures (random overlay with a non-DHT ring) that are easy to manage as nodes join and depart. The nodes have different capacities, and they can support different numbers of direct children during a multicast session. No explicit multicast trees are maintained on top of the overlay. The distributed execution of the algorithms naturally defines an implicit, roughly balanced, capacity-constrained multicast tree for each source node. We prove that the system can deliver a multicast message from any source to all nodes in expected O(log_c n) hops, which is asymptotically optimal, where c is the average node capacity and n is the number of members in a multicast group.     

Ad hoc网络中基于标号的组播路由算法

针对Ad hoc网络中最小带宽消耗组播路由问题,给出一个基于标号优化的启发式算法(LOHA),介绍标号规则及修改节点间邻接关系规则,通过修改组播树中节点的标号来减少树中的转发节点数,从而最小化带宽消耗。该算法的时间复杂度为O(n3),从转发节点个数和平均跳数2个方面比较LOHA及广度优先搜索算法所生成的组播树。实验结果表明,LOHA得到的组播树带宽消耗较少。     

Optimal configuration of an optical network providing predefined multicast transmissions

Operators of networks covering large areas are confronted with demands from some of their customers who are virtual service providers. These providers may call for the connectivity service which fulfills the specificity of their services, for instance a multicast transmission with allocated bandwidth. On the other hand, network operators want to make profit by trading the connectivity service of requested quality to their customers and to limit their infrastructure investments (or do not invest anything at all).We focus on circuit switching optical networks and work on repetitive multicast demands whose source and destinations are à priori known by an operator. He may therefore have corresponding trees “ready to be allocated” and adapt his network infrastructure according to these recurrent transmissions. This adjustment consists in setting available branching routers in the selected nodes of a predefined tree. The branching nodes are opto-electronic nodes which are able to duplicate data and retransmit it in several directions. These nodes are, however, more expensive and more energy consuming than transparent ones.In this paper we are interested in the choice of nodes of a multicast tree where the limited number of branching routers should be located in order to minimize the amount of required bandwidth. After formally stating the problem we solve it by proposing a polynomial algorithm whose optimality we prove. We perform exhaustive computations to show an operator gain obtained by using our algorithm. These computations are made for different methods of the multicast tree construction. We conclude by giving dimensioning guidelines and outline our further work.     

多媒体通信中带度约束的多播路由算法

随着多媒体业务的发展,多播技术应用日益广泛,多播路由是要寻找连接源节点和一组目的节点的一棵多播树,这个问题在数学上归结为Steiner树问题,它是一个NPC问题。在实际网络中,网络节点具备不同的多播能力,有些节点不支持多播,有些节点支持多播,但为了保证网络速度和节点负载平衡,支持多播的节点要限制其复制信息的数量,即节点的多播能力受限。在这种情况下,寻找多播树变得更加困难,该文用节点的约束来表示敏个节点具备的多播能力,节点多播能力受限情况下的多播路由问题被称为带度约束的多播路由问题,其仍是一个NPC问题。该文提出了一种求解带度的约束多播路由问题的双层遗传算法。算法的基本思想是最优多播树应是一棵满足度约束的最小生成树,因此问题的关键在于如何找到包括在最优生成树中的Steiner节点。遗传算法 采用二进制编码方式,内层算法用于求解满足度约束的最小生成树;外层算法进行全局搜索。该文将算法在稀疏图上进行实验,为了更好地模拟真实网络,稀疏图中每个节点具有不同的多播能力,并且多播目的节点数目相比于网络节点数要小。实验对算法进行了三方面比较：（1）解的质量;（2）计算时间;（3）算法的收敛性。实验结果表明,文中提出的遗传算法能够找到费用较小的多播树,但是当网络规模增大时,算法的求解时间也较长。     

一种在Ad Hoc网络中基于地理位置的节约能量的组播路由算法

在移动adhoc网络中,设计节约能量的组播路由算法是非常重要的,这是由于网络中的节点运行时所需要的能量来自于电池的有限供给。由于节点是可以移动的,这就要求节约能量的路由协议在本质上是分布式的,对于当前的节点状态是自适应的。论文提出一种基于地理位置的节约能量的组播路由算法,使得在满足带宽的同时,组播的能量消耗尽可能的少。其基本思想是:先由基本的组播算法生成一棵组播树,然后由组播树的每个非叶子节点根据其邻居节点的地理位置,动态地选择一些转发点,通过这些点以较小功率转发时可节约能量,以此优化组播树。     

Routing in sparse splitting optical networks with multicast traffic

In this paper, we investigate the problem of Multicast Routing in Sparse Splitting Networks (MR-SSN). Given a network topology with the multicast capable nodes distributed uniformly throughout the network, and a multicast session, the MR-SSN problem is to find a route from the source node of the multicast session to all destinations of the multicast session such that the total number of fibers used in establishing the session is minimized. In this paper, we develop a rerouting algorithm for a given Steiner tree, which makes it feasible to route a multicast session using a tree-based solution in sparse light splitting optical networks. In addition, we present a heuristic based on Tabu Search (TS) that requires only one transmitter for the source node and one wavelength for each multicast session. To evaluate the performance of heuristics, we formulate the MR-SSP problem as an integer linear program (ILP), and optimally solve small instances using the commercially available linear solver, CPLEX. We test our heuristic on a wide range of network topologies. Our experimental results show that: (1) The difference between our solution and ILP optimal solution, in terms of the number of fibers used for establishing a multicast session, is within 10% in almost all the instances and within 5% in about half of the instances. (2) The average delay, taken over all destination nodes, falls within three times the optimal value. (3) A sparse light splitting all-optical network with 30% of multicast capable cross-connects has an acceptable low cost and relatively good performance. (4) The improvement achieved by TS heuristic increases considerably when the session size is large, the number of Splitter-and-Delivery cross-connects is small, and the network connectivity is dense.     

Traffic distribution for end-to-end QoS routing with multicast multichannel services

With the development of multimedia group applications and multicasting demands, the construction of multicast routing tree satisfying Quality of Service (QoS) is more important. A multicast tree, which is constructed by existing multicast algorithms, suffers three major weaknesses: (1) it cannot be constructed by multichannel routing, transmitting a message using all available links, thus the data traffic cannot be preferably distributed; (2) it does not formulate duplication capacity; consequently, duplication capacity in each node cannot be optimally distributed; (3) it cannot change the number of links and nodes used optimally. In fact, it cannot employ and cover unused backup multichannel paths optimally. To overcome these weaknesses, this paper presents a polynomial time algorithm for distributed optimal multicast routing and Quality of Service (QoS) guarantees in networks with multichannel paths which is called Distributed Optimal Multicast Multichannel Routing Algorithm (DOMMR). The aim of this algorithm is: (1) to minimize End-to-End delay across the multichannel paths, (2) to minimize consumption of bandwidth by using all available links, and (3) to maximize data rate by formulating network resources. DOMMR is based on the Linear Programming Formulation (LPF) and presents an iterative optimal solution to obtain the best distributed routes for traffic demands between all edge nodes. Computational experiments and numerical simulation results will show that the proposed algorithm is more efficient than the existing methods. The simulation results are obtained by applying network simulation tools such as QSB, OpNet and MATLB to some samples of network. We then introduce a generalized problem, called the delay-constrained multicast multichannel routing problem, and show that this generalized problem can be solved in polynomial time.     

Ant based Pareto optimal solution for QoS aware energy efficient multicast in wireless networks

Most of the group communication technologies support real-time multimedia applications such as video conferencing and distributed gaming. These applications require quality-of-service (QoS) aware multicast routing protocol to deliver the same data stream to a predefined group of receivers. Since nodes in wireless networks are severely energy constrained due to finite battery source, hence it is of paramount importance that QoS aware multicast routing protocol be energy efficient. Transmission power control is one of the methods used to save energy. In this method, the nodes dynamically adjust the transmission power so that energy consumption in the tree is minimized. However, reduction in the transmission power increases the number of forwarding nodes in the multicast tree. This negatively impacts the QoS in terms of propagation delay, delay jitter, and packet loss etc. In wireless networks, there is a trade-off between the energy consumption and the QoS guarantees provided by the network. We unify these requirements into a multiobjective framework referred to as Energy Efficient QoS Multicast Routing (E²QoSMR). The goal is to simultaneously optimize the total power consumption and the QoS parameters in the multicast tree. We extend two algorithms based on metaphor of swarm intelligence for finding an energy efficient multicast tree satisfying the QoS guarantees. Extensive simulations have been conducted to validate the correctness and efficiency of the algorithms. The simulation result of the algorithms is compared with the nondominated sorting genetic algorithm, NSGA-III. The experimental results are consolidated by statistical analyses that demonstrate the ability of the algorithms to generate the Pareto optimal solution set.     

基于NS2的组播路由协议实现及仿真

组播是一个源节点将同一信息传送到多个目的节点的通信方式,IP组播技术减少了网络不必要的带宽开销、网络资源的消耗以及大大减轻了源主机的负担。网络仿真是网络研究者验证网络协议在各种情况下是否具有健壮性和可靠性的有效手段。NS2是面向对象的大型离散事件仿真器,它不仅能实现复杂的网络数据传输和拓扑结构的仿真,还能近乎真实地模拟各种IP网络环境。用NS2实现了一个20个节点网络拓扑的组播路由协议PIM—SM仿真,并获取数据对PIM—SM组播网络性能进行了分析。仿真结果表明了组播网络性能的优越性。     

一种公平分配代价的组播路由算法

本文提出了一种公平分配代价的组播路由算法 DFC_ DCMT- -分布式公平分配代价的延迟受限组播路由算法 ,该算法在优化 tree- cost的条件下 ,能够计算出满足延迟限制的、各目的节点公平负担网络代价的点到多点的组播路由树 .本文还给出一种近似算法 ,可减少节点间交换的信息量 ,同时在一般情况下仍保持各目的节点公平负担网络代价 .     

主动结点启动的可靠多播通信

一、概述在Internet网上实现多播通信还存在没有完全解决的技术问题,如反馈信息爆炸、丢失数据局部恢复功能等,针对这些问题目前有两个主要研究方向:定时器方法(如SRM)和等级结构化方法(如RMTP),但它们都只能部分地解决这些问题。