Fault-tolerant routing algorithms using estimator discretizedlearning automata for high-speed packet-switched networks

We present an adaptive routing algorithm (VP-LA) for high speed packet-switched networks. We use the source routing strategy. VP-LA uses anew S-Model Ergodic Discretized Estimator Learning Automaton (SEDEL), specially designed for the routing problem, to select accurately and rapidly the minimum delay routes in high-speed packet-switched networks. The estimator provides VP-LA with excellent fault-tolerant properties. Moreover, the VP-LA is E-optimal. VP-LA was extensively simulated; the results showed the superiority of VP-LA over other source and link-by-link routing algorithms. VP-LA performs quite well even where the network feedback is misleading, and can be easily and efficiently applied because of its reduced complexity and overhead     

多媒体通信的成组多点广播路由算法

多点广播是一源点传送信息到多个目的节点,成组多点广播是一组节点内部互相进行多点广播。成组多点广播的路由算法是为组内的每一个节点建立一棵路由树,用于点到多点的广播通信。本文提出一种新的成组广播路由算法,它比传统的成组广播路由算法在性能上有了一定的提高,同时更为简洁。     

QoS-based multicast routing optimization algorithms for Internet

Most of the multimedia applications require strict Quality-of-Service （QoS） guarantee during the communication between a single source and multiple destinations. The paper mainly presents a QoS Multicast Routing algorithms based on Genetic Algorithm （QMRGA）. Simulation results demonstrate that the algorithm is capable of discovering a set of QoS-based near optimized, non-dominated multicast routes within a few iterations, even for the networks environment with uncertain parameters.     

New algorithms for multicast routing and wavelength assignment in multi-hop optical WDM networks

We study the problem of multicast routing and wavelength assignment (MC-RWA) in multi-hop optical WDM networks with respect to several target functions. Specially, we first study the MC-RWA problem under the target of minimize maximum hops, an efficient MC-RWA algorithm was proposed for that case. But for the objective of minimizing the total number of wavelength conversions, problem turns out to be NP-hard, we proposed a new approximation MC-RWA algorithm based on group Steiner tree. At last, combining the two objectives, a bi-factor approximation algorithm was introduced to minimize the both targets in the system simultaneously.     

在overlay网络上的负载平衡多播路由算法

针对基于代理服务器的overlay网络的负载平衡多播路由算法被提出.它能均衡利用overlay网络的有限资源,并能满足多播应用的延迟限制需求.首先用具有延迟约束的Steiner树问题对路由问题进行建模;然后采用预计算方法将计算复杂度集中在预备的单点路径计算上,使由这些单点路径所构成的网络更易于构建负载平衡路由树:预计算只计算一次,结果使用多次,因此降低了总体的计算复杂度.仿真实验的结果表明,相对于其他的快速启发式算法,该算法能提供更为优越的性能.整体而言,基于预计算的负载平衡多播路由算法在性能和计算复杂度方面取得了很好的平衡.     

Tabu search based algorithms for bandwidth-delay-constrained least-cost multicast routing

The advent of various real-time multimedia applications in high-speed networks creates a need for quality of service (QoS) based multicast routing. The Steiner tree problem, is a well-known NP-complete problem, provides the mathematical structure behind multicast communications. Two important QoS constraints are the bandwidth constraint and the end-to-end delay constraint. In this paper, we propose various algorithms to solve the bandwidth-delay-constrained least-cost multicast routing problem based on Tabu Search (TS), addressing issues of the selected initial solution and move type as two major building blocks in short-term memory version of Tabu Search and longer-term memory with associated intensification and diversification strategies as advanced Tabu Search techniques. We evaluate the performance and efficiency of the proposed TS-based algorithms in comparison with other existing TS-based algorithms and heuristics on a variety of random generated networks with regard to total tree cost. Finally we identify the most efficient algorithm uncovered by our testing.     

Avoidance of multicast incapable branching nodes for multicast routing in WDM networks

In this article we study the multicast routing problem in all-optical WDM networks under the spare light splitting constraint. To implement a multicast session, several light-trees may have to be used due to the limited fanouts of network nodes. Although many multicast routing algorithms have been proposed in order to reduce the total number of wavelength channels used (total cost) for a multicast session, the maximum number of wavelengths required in one fiber link (link stress) and the end-to-end delay are two parameters which are not always taken into consideration. It is known that the shortest path tree (SPT) results in the optimal end-to-end delay, but it can not be employed directly for multicast routing in sparse light splitting WDM networks. Hence, we propose a novel wavelength routing algorithm which tries to avoid the multicast incapable branching nodes (MIBs, branching nodes without splitting capability) in the shortest-path-based multicast tree to diminish the link stress. Good parts of the shortest-path-tree are retained by the algorithm to reduce the end-to-end delay. The algorithm consists of tree steps: (1) a DijkstraPro algorithm with priority assignment and node adoption is introduced to produce a SPT with up to 38% fewer MIB nodes in the NSF topology and 46% fewer MIB nodes in the USA Longhaul topology, (2) critical articulation and deepest branch heuristics are used to process the MIB nodes, (3) a distance-based light-tree reconnection algorithm is proposed to create the multicast light-trees. Extensive simulations demonstrate the algorithm’s efficiency in terms of link stress and end-to-end delay.     

Hierarchical geographic multicast routing for wireless sensor networks

Wireless sensor networks comprise typically dense deployments of large networks of small wireless capable sensor devices. In such networks, multicast is a fundamental routing service for efficient data dissemination required for activities such as code updates, task assignment and targeted queries. In particular, efficient multicast for sensor networks is critical due to the limited energy availability in such networks. Multicast protocols that exploit location information available from GPS or localization algorithms are more efficient and robust than other stateful protocols as they avoid the difficulty of maintaining distributed state (multicast tree). Since localization is typically already required for sensing applications, this location information can simply be reused for optimizing multicast performance at no extra cost. Recently, two protocols were proposed to optimize two orthogonal aspects of location-based multicast protocols: GMR (Sanchez et al. GMR: Geographic multicast routing for wireless sensor networks. In Proceedings of the IEEE SECON, 2006) improves the forwarding efficiency by exploiting the wireless multicast advantage but it suffers from scalability issues when dealing with large sensor networks. On the other hand, HRPM (Das et al. Distributed hashing for scalable multicast in wireless ad hoc networks. IEEE TPDS 47(4):445–487, 2007) reduces the encoding overhead by constructing a hierarchy at virtually no maintenance cost via the use of geographic hashing but it is energy-inefficient due to inefficacies in forwarding data packets. In this paper, we present HGMR (hierarchical geographic multicast routing), a new location-based multicast protocol that seamlessly incorporates the key design concepts of GMR and HRPM and optimizes them for wireless sensor networks by providing both forwarding efficiency (energy efficiency) as well as scalability to large networks. Our simulation studies show that: (i) In an ideal environment, HGMR incurs a number of transmissions either very close to or lower than GMR, and, at the same time, an encoding overhead very close to HRPM, as the group size or the network size increases. (ii) In a realistic environment, HGMR, like HRPM, achieves a Packet Delivery Ratio (PDR) that is close to perfect and much higher than GMR. Further, HGMR has the lowest packet delivery latency among the three protocols, while incurring much fewer packet transmissions than HRPM. (iii) HGMR is equally efficient with both uniform and non-uniform group member distributions.     

Two algorithms for multi‐constrained optimal multicast routing

Multimedia applications, such as video‐conferencing and video‐on‐demand, often require quality of service (QoS) guarantees from the network, typically in the form of minimum bandwidth, maximum delay, jitter and packet loss constraints, among others. The problem of multicast routing subject to various forms of QoS constraints has been studied extensively. However, most previous efforts have focused on special situations where a single or a pair of constraints is considered. In general, routing under multiple constraints, even in the unicast case is an NP‐complete problem. We present in this paper two practical and efficient algorithms, called multi‐constrained QoS dependent multicast routing (M_QDMR) and (multicasting routing with multi‐constrained optimal path selection (M_MCOP)), for QoS‐based multicast routing under multiple constraints with cost optimization. We provide proof in the paper that our algorithms are correct. Furthermore, through extensive simulations, we illustrate the effectiveness and efficiency of our proposals and demonstrate their significant performance improvement in creating multicast trees with lower cost and higher success probability. Copyright © 2003 John Wiley & Sons, Ltd.     

Adaptive multicast routing in multirate loss networks

In this paper, we study two versions of the multicast routing problem in multirate loss networks: complete and partial. In the complete version of the multicast routing problem, the identities of all destination nodes are available to the multicast routing algorithm at once. Conversely, in the partial version of the multicast problem, the identities of the destination nodes are revealed to the routing algorithm one by one. Although the complete version of the multicast routing problem, also known as the Steiner tree problem, has been well studied in the literature, less attention has been paid for the definition of link costs and evaluating the performance of multicast routing algorithm from the network revenue point of view. Therefore, in this paper, we first propose two approaches, namely, the Markov Decision Processbased (MDPbased) and Least Loaded Routingbased (LLRbased) approaches, for defining link costs. Several heuristic multicast routing algorithms are then proposed for both fully connected networks and sparsely connected networks. We have also proposed a new performance metric, referred to as fractional reward loss, for evaluating the performance of multicast routing algorithms. Our simulation results indicate that algorithms based on partial destination information yield worse performance than those based on complete information. We also found that, for fully connected networks, algorithms that use LLRbased link costs yield very competitive performance as compared to those that use MDP approach. However, for sparsely connected networks, LLRbased algorithms yield significantly worse performance as compared to the MDPbased algorithms.     

Improved heuristics for multicast routing in wireless mesh networks

Multicast is a communication technique that allows a source to transmit data to a set of recipients in an efficient manner. Therefore, the primary objective of a multicast routing protocol would be to minimize number of transmissions to conserve bandwidth. The problem of computing multicast trees with minimal bandwidth consumption is similar to Steiner tree problem and has shown to be NP-complete. So, heuristic based algorithms are suitable to approximate such bandwidth optimal trees. This paper proposes a multicast routing protocol based on minimum number of transmission trees using an heuristic approach. The simulation results show that the proposed algorithm offers better performance over existing protocols, even in the worst-case scenario when the set of multicast receivers are sparsely distributed across the network.     

A multicast routing algorithm for LEO satellite IP networks

Satellite networks provide global coverage and support a wide range of services. Since low Earth orbit (LEO) satellites provide short round-trip delays, they are becoming increasingly important for real-time applications such as voice and video traffic. Many applications require a mechanism to deliver information to multiple recipients. A multicast routing algorithm for datagram traffic is introduced for LEO satellite IP networks. The new scheme creates multicast trees by using the datagram routing algorithm. The bandwidth utilization and delay characteristics are assessed through simulations     

QoS-driven multicast routing in sparse-splitting optical networks

This paper investigates the quality-of-service (QoS)-driven multicast routing problem in a sparse-splitting optical network. The main objective is to minimize the total cost of wavelength channels utilized by the light-tree while satisfying required QoS parameters. In this paper, both the optical-layer constraints (e.g., optical signal power) and application-layer requirements (e.g., end-to-end delay and inter-destination delay variation) are considered as the QoS parameters. First, integer linear programming (ILP) formulations to solve the optimal multicast routing problem with the given QoS parameters are presented. Solving the ILP formulations for large-scale networks can easily overwhelm the capabilities of state-of-the-art computing facilities, and hence, a heuristic algorithm is proposed to construct a feasible light-tree that satisfies the required QoS parameters in large-scale networks. Simulation results demonstrate the performance of the proposed heuristic algorithm in terms of the cost of utilized wavelength channels.     

A survey of multicast routing protocols for mobile Ad-Hoc networks

A Mobile Ad-hoc NETwork (MANET) is composed of Mobile Nodes (MNs) without any infrastructure. MNs selforganize to form a network over radio links. In this environment, multicast routing protocols are faced with the challenge of producing multi-hop routing under host mobility and bandwidth constraint. Multicast routing plays a significant role in MANETs. In recent years, various multicast routing protocols with distinguishing feature have been newly proposed. In order to provide a comprehensive understanding of these multicast routing protocols designed for MANETs and pave the way for the further research, a survey of the multicast routing protocols is discussed in detail in this paper. Qualitatively, based on their primary multicast routing selection principle, we show that all these protocols could be placed under one of two broad routing selection categories: multicast routing based on application independence and multicast routing based on application dependence.     

Distributed algorithms for multicast path setup in data networks

Establishing a multicast tree in a point-to-point network of switch nodes, such as a wide-area asynchronous transfer mode (ATM) network, can be modeled as the NP-complete Steiner problem in networks. In this paper, we introduce and evaluate two distributed algorithms for finding multicast trees in point-to-point data networks. These algorithms are based on the centralized Steiner heuristics, the shortest path heuristic (SPH) and the Kruskal-based shortest path heuristic (K-SPH), and have the advantage that only the multicast members and nodes in the neighborhood of the multicast tree need to participate in the execution of the algorithm. We compare our algorithms by simulation against a baseline algorithm, the pruned minimum spanning-tree heuristic that is the basis of many previously published algorithms for finding multicast trees. Our results show that the competitiveness (the ratio of the sum of the heuristic tree's edge weights to that of the best solution found) of both of our algorithms was, on the average, 25% better in comparison to that of the pruned spanning-tree approach. In addition, the competitiveness of our algorithms was, in almost all cases, within 10% of the best solution found by any of the Steiner heuristics considered, including both centralized and distributed algorithms. Limiting the execution of the algorithm to a subset of the nodes in the network results in an increase in convergence time over the pruned spanning-tree approach, but this overhead can be reduced by careful implementation     

Random algorithms for scheduling multicast traffic in WDMbroadcast-and-select networks

We develop and analyze simple algorithms for scheduling multicast traffic in wavelength division multiplexing (WDM) broadcast-and-select networks with N nodes, W wavelengths, and a single receiver per node that can be tuned to any of the W wavelengths. Each message is addressed to κ randomly chosen nodes. Since optimal message scheduling in a WDM network is known to be very difficult, we study two simple scheduling schemes: in the first, a message is continuously retransmitted until it is received by all of its intended recipients; and in the second, a random delay is introduced between retransmissions of the same message. We develop a throughput analysis for both schemes using methods from discrete-time queueing systems and show that the algorithm with random delays between retransmissions results in higher throughput. We also consider a number of receiver algorithms for selecting among multiple simultaneous transmissions and show, through simulation, that an algorithm where the receiver selects the message with the least number of intended recipients performs better than a random selection algorithm. Finally, we show that channel utilization can be significantly increased with multiple receivers/node     

有/无线ATM网的组播选路算法

本文提出一种组播选路算法,在组播连接路由树的代价函数中计入了移动成员的越区切换发生概率,使为移动成员服务的接入节点（ＡＰ）尽可能成为组播路由树的树叶节点。当移动成员发生越区切换以后,可减去原来为之服务的ＡＰ和相应的树枝通道链路,从而保证了网络资源得以有效地利用。数值模拟分析的结果表明,我们提出的算法达到了这一目的。     

Efficient solutions to multicast routing in communication networks

An important problem in both wireless and wired communication networks is to be able to efficiently multicst information to a group of network sites. Multicasting reduces the transmission overhead of both wireless and wired networks and the time it takes for all the nodes in the subset to receive the information. Since transmission bandwidth is a scarce commodity especially in wireless networks, efficient and near minimum-cost multicast algorithms are particularly useful in the wireless context. In this paper, we discuss methods of establishing efficient and near minimum-cost multicast routing in communication networks. In particular, we discuss an efficient implementation of a widely used multicast routing method which can construct a multicast tree with a cost no greater than twice the cost of an optimal tree. We also present two efficient multicast tree constructions for a general version of the multicast routing problem in which a network consists of different classes of nodes, where each class can have one or more nodes of the same characteristic which is different from the characteristics of nodes from other classes. Because of their efficient running times, these multicast routing methods are particularly useful in the mobile communication environments where topology changes will imply recomputation of the multicast trees. Furthermore, the proposed efficient and near minimum-cost multicast routing methods are particularly suited to the wireless communication environments, where transmission bandwidth is more scarce than wired communication environments.Partially supported by NSF/LaSER under grant number EHR-9108765, by LEQSF grant number 94-RD-A-39, by NASA under grant number NAG 5-2842.     

Hypo-Steiner heuristic for multicast routing in all-optical WDM mesh networks

In sparse light splitting all-optical WDM networks, the more destinations a light-tree can accommodate, the fewer light-trees and wavelengths a multicast session will require. In this article, a Hypo-Steiner light-tree algorithm (HSLT) is proposed to construct a HSLT light-tree to include as many destinations as possible. The upper bound cost of the light-trees built by HSLT is given as N(N − 1)/2, where N is the number of nodes in the network. The analytical model proves that, under the same condition, more destinations could be held in a HSLT than a Member-Only (Zhang et al., J. Lightware Technol, 18(12), 1917–1927 2000.) light-tree. Extensive simulations not only validate the proof but also show that the proposed heuristic outperforms the existing multicast routing algorithms by a large margin in terms of link stress, throughput, and efficiency of wavelength usage.     

高速网络服务质量的路由选择问题

适时地转发数字化音频／视频信息的需求,对下一代综合业务宽带网络（ＩＳＢＮ）提出了新的挑战,其关键问题之一是服务质量的路由选择;它依据提供的服务质量参数,来选择有充足资源的网络路由。本文是关于路由选择问题的分类,指出了不同路由选择策略的优势和弱点。