一个快速的时延有界低代价多播路由算法

基于ＱｏＳ的多播路由算法需要在满足每个个体ＱｏＳ需求的同时,又能高效管理网络资源,提出了一种满足端端时延限制的低代价多播路由算法。算法使用一个修改的Ｓｔｅｉｎｅｒ树近似算法先构建时延有界的低代价多播树,再通过最小时延路径与其它尚不在多播树的且结点相连。     

QoS based multicast routing algorithms for real time applications

In recent years, there has been a lot of interest in providing real-time multimedia services like digital audio and video over packet-switched networks such as Internet and ATM. These services require certain quality of service (QoS) from the network. The routing algorithm should take QoS factor for an application into account while selecting the most suitable route for the application. In this paper, we introduce a new routing metric and use it with two different heuristics to compute the multicast tree for guaranteed QoS applications that need firm end-to-end delay bound. We then compare the performance of our algorithms with the other proposed QoS-based routing algorithms. Simulations were run over a number of random networks to measure the performance of different algorithms. We studied routing algorithms along with resource reservation and admission control to measure the call throughput over a number of random networks. Simulation results show that our algorithms give a much better performance in terms of call throughput over other proposed schemes.     

A Delay-Constrained Least-Cost Multicast Routing Heuristic for Dynamic Multicast Groups

Many new multimedia applications involve dynamic multiple participants, have stringent end-to-end delay requirement and consume large amount of network resources. In this paper, we propose a new dynamic delay-constrained least-cost multicast routing algorithm (DDCLCMR) to support these applications. When group membership changes, the existing multicast tree is perturbed as little as possible. Simulation results show that DDCLCMR performs very well in terms of cost for both, static and dynamic multicast groups, when compared to the best multicast algorithms known. Our evaluation of the cost performance of the algorithms showed that DDCLCMR is always within 10% from BSMA which has the best cost performance among all the proposed delay-constrained static multicast heuristics, while NAIVE, the well-known dynamic multicast routing algorithm, is up to 70% worse than BSMA in some cases.     

Ad Hoc网络QoS路由协议研究

Ad Hoc网络自身固有的特点使得Ad Hoc网络QoS路由协议面临许多新的挑战和机遇。通过对基于标签探测（ticket-based probing,TBP）协议和在TBP协议基础上提出的延时约束最小费用的Ad Hoc网络中的完全分布式QoS路由协议——基于熵的长寿的分布式QoS路由（entropy-based long-life distributed QoS routing,EBLLD）协议进行的详细地分析和比较,可以得出以下结论：EBLLD协议有较高的路由成功率,具有可扩展性,可应用于较大规模的Ad Hoc网络。     

A novel heuristic algorithm for QoS-aware end-to-end service composition

Many works have been carried out to find the efficient algorithms for QoS-aware service composition in recent years. Nevertheless, on one hand, some of these works only consider the local QoS attributes in Web services composition; on the other hand, some ideas derived from QoS selection algorithms for network routing are directly applied in service composition without any adaption. A service composition model with end-to-end QoS constraints has been presented in this paper. An improved heuristics HCE based on the observation of characteristic of end-to-end service composition is proposed as a novel solution. Simulation results reveal the better performance of proposed heuristic compared to the other two heuristics, HMCOP and generic CE algorithm.     

网络QoS的分组调度算法仿真研究

随着Internet的不断发展,实时数据的应用对网络提出了更高的服务质量控制要求,分组调度是实现网络服务质量控制的核心技术之一.分组调度按照一定的规则决定队列中分组的发送次序并分配共享链路带宽.文中介绍了一种先进的分组调度和资源管理模型:链路共享模型, 以及两种不同的实现算法:CBQ和HPFQ,分析了它们用于传输实时流的可行性.HPFQ算法为实时数据提供了严格的时延保证和完全意义上的等级链路共享服务.文中使用网络仿真工具NS2,对链路共享模型下实时流传输的服务质量性能进行了仿真分析.     

QoS and data relaying for wireless sensor networks

In this paper we study the effects of data relaying in wireless sensor networks (WSNets) under QoS constraints with two different strategies. In the first, data packets originating from the same source are sent to the base station possibly along several different paths, while in the second, exactly one path is used for this purpose. The two strategies correspond to splitting and not splitting relaying traffic, respectively. We model a sensor network architecture based on a three-tier hierarchy of nodes which generalizes to a two-tier WSNet with multiple sinks. Our results apply therefore to both types of networks. Based on the assumptions in our model, we describe several methods for computing relaying paths that are optimal with respect to energy consumption and satisfy QoS requirements expressed by the delay with which data are delivered to the base station(s). We then use our algorithms to perform an empirical analysis that quantifies the performance gains and losses of the splittable and unsplittable traffic allocation strategies for WSNets with delay-constrained traffic. Our experiments show that splitting traffic does not provide a significant advantage in energy consumption, but can afford strategies for relaying data with a lower delay penalty when using a model based on soft-delay constraints.     

一种基于模拟退火方法的多约束QoS组播路由算法

研究了带宽、时延及时延抖动约束最小代价的QoS组播路由问题,提出一种利用模拟退火方法解决该问题的QoS组播路由算法SABDMA。该算法通过选择合适的模拟退火参数迭代求解,以获得满足QoS约束的最小代价组播树。同时,为避免搜索区域的扩大和计算时间的增加,根据时延和时延抖动的关系,提出采用“路径交换”策略在可行解范围内构造邻域集。仿真结果表明该算法具有可行、稳定、收敛快的特点;能根据组播应用对QoS的限制要求,有效地构造代价较低的组播树,具有较强的实时性。     

AntNet的多路径QoS路由算法研究

以AntNet算法为基础,介绍了蚁群网络路由的问题模型和数据结构,通过引入QoS约束机制,提出了一种基于AntNet的多路径QoS路由算法. 该算法采用具有带宽和时延QoS约束的新规则进行节点选择,并利用改进的节点信息更新规则以及根据路由表中概率值随机地选择相邻节点转发数据包. 性能分析和模拟结果显示,基于AntNet的多路径QoS路由算法具有较快的收敛速度和较好的鲁棒性,能够自适应网络状态的动态变化,同时考虑了QoS约束和负载平衡问题     

A Polynomial Time Approximation Scheme for Minimum Cost Delay-Constrained Multicast Tree under a Steiner Topology

This paper is concerned with a restricted version of minimum cost delay-constrained multicast in a network where each link has a delay and a cost. Given a source vertex $s$ and $p$ destination vertices $t_1, t_2, \ldots, t_p$ together with $p$ corresponding nonnegative delay constraints $d_1, d_2, \ldots, d_p$, many QoS multicast problems seek a minimum cost multicast tree in which the delay along the unique $s$--$t_i$ path is no more than $d_i$ for $1 \le i \le p$. This problem is NP-hard even when the topology of the multicast tree is fixed. In this paper we show that every multicast tree has an underlying Steiner topology and that every minimum cost delay-constrained multicast tree corresponds to a minimum cost delay-constrained realization of a corresponding Steiner topology. We present a fully polynomial time approximation scheme for computing a minimum cost delay-constrained multicast tree under a Steiner topology. We also present computational results of a preliminary implementation to illustrate the effectiveness of our algorithm and discuss its applications.     

A Polynomial Time Approximation Scheme for Minimum Cost Delay-Constrained Multicast Tree under a Steiner Topology

This paper is concerned with a restricted version of minimum cost delay-constrained multicast in a network where each link has a delay and a cost. Given a source vertex $s$ and $p$ destination vertices $t_1, t_2, \ldots, t_p$ together with $p$ corresponding nonnegative delay constraints $d_1, d_2, \ldots, d_p$, many QoS multicast problems seek a minimum cost multicast tree in which the delay along the unique $s$--$t_i$ path is no more than $d_i$ for $1 \le i \le p$. This problem is NP-hard even when the topology of the multicast tree is fixed. In this paper we show that every multicast tree has an underlying Steiner topology and that every minimum cost delay-constrained multicast tree corresponds to a minimum cost delay-constrained realization of a corresponding Steiner topology. We present a fully polynomial time approximation scheme for computing a minimum cost delay-constrained multicast tree under a Steiner topology. We also present computational results of a preliminary implementation to illustrate the effectiveness of our algorithm and discuss its applications.     

Delay-Constrained,Low-Cost Multicast Routing in Multimedia Networks

Support for multimedia applications is a major objective of future high speed networks. Multimedia applications are usually resource intensive, have stringent quality of service (QoS) requirements, and in many cases involve large multicast groups. Multicasting enables these applications to scale to a large number of users without overloading the network and server resources. This paper focuses on developing low-cost, delay-bounded multicast trees to support the QoS requirements of multimedia applications. The approach taken in the development of the multicast trees is to decouple the cost optimization from bounding the delay by first building a low-cost tree and then handling any delay violations that may occur in the tree. Three new heuristics are proposed. The first two heuristics, delay-constrained low-cost inexpensive multicasting (SLIM) and SLIM+, use the least-cost path between the multicast nodes to incrementally build a multicast tree that satisfies the delay requirements of the multicast nodes. Their complexity is O(n³), where n is the number of nodes in the network. The third heuristic, K-SLIM, builds a set of k shortest paths and uses these paths in an attempt to further reduce the cost of the multicast tree without violating the delay requirements of the multicast nodes. Its time complexity is O(kn³ log(n)), where k, a user-defined parameter, denotes the number of shortest paths to be considered. Our simulation results show that K-SLIM on average outperforms other well-known heuristics. The results also show that SLIM+ produces low-cost, delay-bounded trees with an average cost close to the average cost of the trees produced by K-SLIM but with much lower processing overhead.     

多约束QoS多播路由的模型和算法研究

随着高性能网络、移动网络及Internet的不断发展,具有QoS约束的多播路由技术已成为网络及分布式系统领域的一个重要研究课题。基于约束多播路由的目的在于鉴别一条路径满足QoS约束,然而,多加、乘约束的路由是一个NP-完全性问题。因此,快速的和精确的约束路由算法是少有的,甚至不存在。如此基于路由算法的需求导致众多的启发算法和一些少有的QoS算法的出现。文章描述了一种适用于研究QoS多播路由的网络模型,给出一个完全,简洁和公平地评价7个典型的基于多约束QoS多播路由算法,并且提供多约束路径算法的最坏情况下复杂性的比较。     

一种带约束的多目标服务质量路由算法

多约束服务质量(QoS)路由是要求在多个约束条件下计算满足所有独立限制条件的可行路径．将这种NPC问题转化为一种带约束条件的多目标优化问题，根据多目标遗传算法的智能优化原理，提出一种多目标QoS路由算法来产生一组最优非劣路由．理论分析和实验结果表明，使用带约束的多目标遗传算法是解决多约束QoS路由的有效途径，能对提高网络性能起到重要作用．     

Ant colony-based algorithm for constructing broadcasting tree with degree and delay constraints

Heterogeneous ISP router policies prevent multimedia QoS applications, such as real-time media streaming, video conferencing, and distance learning, that require IP layer multicasting from wide deployment on the Internet. Thus, recent efforts have applied application layer multicast to implement such applications by organizing the multicast group in an overlay (virtual), peer-to-peer network. Such a communication scheme can be regarded as a broadcasting problem with degree and delay constraints in the overlay network. The degree and delay-constrained broadcasting problem with minimum-cost appears to be NP-complete. This study proposes an ant colony-based algorithm to solve the difficult broadcasting problem and compares it with some related methods. The results of a series of simulations show the efficiency and effectiveness of the proposed algorithm.     

Linux下多媒体业务差分IPv6测试平台的设计与实现

为了在无线网络中保证实时多媒体业务的服务质量(QoS),基于IPv6在无线局域网中设计并实现了差分QoS测试平台,实验测试各种支持QoS调度策略。测试平台核心部件为实现差分QoS调度的IPv6路由器。路由器由Linux操作系统来实现,采用可加载内核模块编程,使用Netfilter中钩子函数截获网络数据包,根据业务的不同优先级进行调度,合理分配网络资源,保证实时业务的服务质量。在此平台上,进行了多媒体业务差分QoS的演示和测试。实验表明,测试平台运行稳定,可以为QoS研究提供一个开放式开发测试环境。     

智能配电网通信多信道调度策略

为了有效提高基于无线传感网的配电网服务质量,进一步增强配电网中数据实时性,减少延迟,提出了一种基于优先级的多信道调度策略。首先,根据实时的信道链路状态信息,提出了基于最小跳数生成树的链路路由算法（LB-MHST）,克服了无线射频干扰,保证智能电网的服务质量;然后,针对配电网中不同数据包对于延迟要求的不同,考虑了数据优先级传输,有效地提高了感知节点的数据传输效率,进一步满足了配电网中的QoS性能要求。实验结果表明,与最小跳数生成树（MHST）算法相比,尤其是在多信道延迟感知传输中,提出算法在单信道、8信道和16信道时分别将高负载流量延迟性能提高了12%,15.2%和18%。     

Fault-tolerant real-time communication in distributed computingsystems

The delivery delay in a point-to-point packet switching network is difficult to control due to the contention among randomly-arriving packets at each node and multihops a packet must travel between its source and destination. Despite this difficulty, there are an increasing number of applications that require packets to be delivered reliably within prespecified delay bounds. This paper shows how this can be achieved by using real-time channels which make “soft” reservation of network resources to ensure the timely delivery of real-time packets. We first present theoretical results and detailed procedures for the establishment of real-time channels and then show how the basic real-time channels can be enhanced to be fault-tolerant using the multiple disjoint paths between a pair of communicating nodes. The contribution of the former is a tighter schedulability condition which makes more efficient use of network resources than any other existing approaches, and that of the latter is a significant improvement in fault tolerance over the basic real-time channel, which is inherently susceptible to component failures     

QoS路由近似算法的研究

QoS需求可分为基于路径的与基于链路的两种。称一个具有足够资源来满足应用QoS需求的路径为可行路径。另外,优化准则可以进一步缩小在可行路径间的选择范围。QoS路由的目标是寻找最优的可行路径。基于QoS的路由是当前的一个研究热点,其目标是在确定满足多个约束条件(QoS需求)的路径的同时实现网络资源的高利用率。基于QoS的路由对资源预置的服务(如IntServ,ATM)与非资源预置的服务(如DiffServ)都是需要的。如,ATM PNNI(Private Network Node Interface)协议基     

一种多径QoS的MANET路由协议

近年来,QoS(Quality of Service)路由问题已成为Ad hoc网络的一个研究热点.本文提出一种按需的多径QoS路由协议-MTBP(Multipath Ticket Based Probing Routing Protocol).该协议能够在源节点和目的节点间找到多条满足QoS要求的路由.与传统路由协议相比,本协议通过"票"限制洪泛,在链路断裂时采用备份路由及时恢复数据分组的传递,具有多路径传输、负载平衡、控制开销小等特点,能很好的适应无线移动自组织网中网络拓扑结构变化迅速,节点间移动速率快的特性.