Video distribution on multicast networks

The Internet is being used to distribute video programming to small, widely distributed audiences over a multicast backbone (Mbone). This type of service can be used to deliver specialized programming to the general population. As the service becomes more widely used, conserving the required transmission facilities becomes more important. We define the problem of designing multicast networks for video distribution. The problem is related to the Steiner tree problem, with an interesting twist. The line costs are not constant. An heuristic is developed to solve the problem and the new heuristic is related to and compared with heuristics, developed for the Steiner tree problem and algorithms to design minimum depth and minimum spanning trees     

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     

Destination-driven routing for low-cost multicast

We present a destination-driven algorithm that optimizes for applications, such as group video or teleconferencing, that require multicast trees with low total cost. The destination-driven algorithm uses a greedy strategy based on shortest-path trees and minimal spanning trees but biases routes through destinations. The performance of the algorithm is analyzed through extensive simulation and compared with several Steiner tree heuristics and the popular shortest-path tree (SPT) method. The algorithm is found to produce trees with significantly lower overall cost than the SPT while maintaining reasonable per-destination performance. Its performance also compares well with other known Steiner heuristics. Moreover, the algorithm does not suffer from high complexity common to most Steiner tree heuristics and builds a route by querying only incident links for cost information     

Routing to Multiple Destinations in Computer Networks

Algorithms for effectively routing messages from a source to multiple destination nodes in a store-and-forward computer network are studied. The focus is on minimizing the network cost (NC), which is the sum of weights of the links in the routing path. Several heuristic algorithms are studied for finding the NC minimum path (which is an NP-complete problem). Among them are variations of a minimum spanning tree (MST) heuristic and heuristics for the traveling salesman problem, both of which use global network information. Another set of heuristics examined are based on using only the shortest paths to the destinations. While the MST algorithm has the best worst case performance among all algorithms, a detailed, empirical study of the "average" performance of the algorithms on typical, randomly chosen networks reveals that simpler heuristics are almost as effective. The NC cost measure is also compared to the destination cost (DC), which is the sum of weights of the shortest path distances to all destinations. A scheme of algorithms is given which trades off between NC and DC.     

Evaluation of multicast routing algorithms for real-timecommunication on high-speed networks

Multicast (MC) routing algorithms capable of satisfying the quality of service (QoS) requirements of real-time applications will be essential for future high-speed networks. We compare the performance of all of the important MC routing algorithms when applied to networks with asymmetric link loads. Each algorithm is judged based on the quality of the MC trees it generates and its efficiency in managing the network resources. Simulation results over random networks show that unconstrained algorithms are not capable of fulfilling the QoS requirements of real-time applications in wide-area networks. Simulations also reveal that one of the unconstrained algorithms, reverse path multicasting (RPM), is quite inefficient when applied to asymmetric networks. We study how combining routing with resource reservation and admission control improves the RPM's efficiency in managing the network resources. The performance of one semiconstrained heuristic, MSC, three constrained Steiner tree (CST) heuristics, Kompella, Pasquale, and Polyzos (1992), constrained adaptive ordering (CAO), and bounded shortest multicast algorithm (BSMA), and one constrained shortest path tree (CSPT) heuristic, the constrained Dijkstra heuristic (CDKS) are also studied. Simulations show that the semiconstrained and constrained heuristics are capable of successfully constructing MC trees which satisfy the QoS requirements of real-time traffic. However, the cost performance of the heuristics varies. The BSMA's MC trees are lower in cost than all other constrained heuristics. Finally, we compare the execution times of all algorithms, unconstrained, semiconstrained, and constrained     

Energy efficient broadcast routing in static ad hoc wireless networks

In this paper, we discuss energy efficient broadcast in ad hoc wireless networks. The problem of our concern is: given an ad hoc wireless network, find a broadcast tree such that the energy cost of the broadcast tree is minimized. Each node in the network is assumed to have a fixed level of transmission power. We first prove that the problem is NP-hard and propose three heuristic algorithms, namely, shortest path tree heuristic, greedy heuristic, and node weighted Steiner tree-based heuristic, which are centralized algorithms. The approximation ratio of the node weighted Steiner tree-based heuristic is proven to be (1 + 2 ln(n - 1)). Extensive simulations have been conducted and the results have demonstrated the efficiency of the proposed algorithms.     

A new delay‐constrained algorithm for multicast routing tree construction

New multimedia applications provide guaranteed end‐to‐end quality of service (QoS) and have stringent constraints on delay, delay‐jitter, bandwidth, cost, etc. The main task of QoS routing is to find a route in the network, with sufficient resources to satisfy the constraints. Most multicast routing algorithms are not fast enough for large‐scale networks and where the source node uses global cost information to construct a multicast tree. We propose a fast and simple heuristic algorithm (EPDT) for delay‐constrained routing problem for multicast tree construction. This algorithm uses a greedy strategy based on shortest‐path and minimal spanning trees. It combines the minimum cost and the minimum radius objectives by combining respectively optimal Prim's and Dijkstra's algorithms. It biases routes through destinations. Besides, it uses cost information only from neighbouring nodes as it proceeds, which makes it more practical, from an implementation point of view. Copyright © 2004 John Wiley & Sons, Ltd.     

Utilizing Redundancy for Timing Critical Interconnect

Conventionally, the topology of signal net routing is almost always restricted to Steiner trees, either unbuffered or buffered. However, introducing redundant paths into the topology (which leads to non-tree) may significantly improve timing performance as well as tolerance to open faults and variations. These advantages are particularly appealing for timing critical net routings in nanoscale VLSI designs where interconnect delay is a performance bottleneck and variation effects are increasingly remarkable. We propose Steiner network construction heuristics which can generate either tree or non-tree with different slack-wirelength tradeoff, and handle both long path and short path constraints. We also propose heuristics for simultaneous Steiner network construction and buffering, which may provide further improvement in slack and resistance to variations. Furthermore, incremental non-tree delay update techniques are developed to facilitate fast Steiner network evaluations. Extensive experiments in different scenarios show that our heuristics usually improve timing slack by hundreds of pico seconds compared to traditional approaches. When process variations are considered, our heuristics can significantly improve timing yield because of nominal slack improvement and delay variability reduction.     

一种改进的Steiner树启发式算法

最小Steiner树问题是NP完全问题，关于Steiner问题的启发式算法的研究具有重要理论和实际意义。本文在MPH算法基础上，对于经过某些关键节点的短路径优先考虑，提出了KBMPH算法，从而实现更多链路的共享。在随机网络上的仿真结果表明，极大多数情况下，在准Steiner树的网络费用KBMPH算法优于MPH算法，KBMPH算法的复杂度为O（n^3）。     

Optimal and heuristic algorithms for all‐optical group multicast in resource‐constrained WDM networks

Given a sparse‐splitting wavelength‐division multiplexing network with no wavelength converter, we study a group multicast problem that is how to transmit a number of multicast streams from the video server to multiple destinations simultaneously. To avoid the situation that the wavelengths are used up by the first few requests, one wavelength is available for each multicast request. Hence, some of destinations may not be included in the multicast trees because of the lack of wavelengths. Our goal is to construct a number of light trees with conflict‐free wavelengths for multiple requests so that the number of served clients is maximized. This problem is named as the revenue‐maximized and delay‐constrained group multicast routing problem. We first determine a set of multicast trees with the maximum number of served clients, then followed by the wavelength assignment to allocate the minimum number of wavelengths to the resulting trees. In this study, we propose two Integer Linear Programming ILP‐based algorithms for determining the optimal solutions for the light‐tree construction problem and the wavelength assignment problem, respectively. For large‐scale networks, two heuristics are introduced to solve the light‐tree construction problem approximately. A set of simulations are also provided for comparing performances of our algorithms against the other published methods. Copyright © 2016 John Wiley & Sons, Ltd.     

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.     

Strong minimum energy topology in wireless sensor networks: NP-completeness and heuristics

Wireless sensor networks have recently attracted lots of research effort due to the wide range of applications. These networks must operate for months or years. However, the sensors are powered by battery, which may not be able to be recharged after they are deployed. Thus, energy-aware network management is extremely important. In this paper, we study the following problem: Given a set of sensors in the plane, assign transmit power to each sensor such that the induced topology containing only bidirectional links is strongly connected. This problem is significant in both theory and application. We prove its NP-completeness and propose two heuristics: power assignment based on minimum spanning tree (denoted by MST) and incremental power. We also show that the MST heuristic has a performance ratio of 2. Simulation study indicates that the performance of these two heuristics does not differ very much, but; on average, the incremental power heuristic is always better than MST.     

Minimum-power multicast routing in static ad hoc wireless networks

Wieselthier et al. (2000) proposed three greedy heuristics for Min-Power Asymmetric Broadcast Routing: SPT (shortest-path tree), MST (minimum spanning tree), and BIP (broadcasting incremental power). Wan et al. (2001) proved that SPT has an approximation ratio of at least (n/2) where n is the total number of nodes, and both MST and BIP have constant approximation ratios. Based on the approach of pruning, Wieselthier et al. also proposed three greedy heuristics for Min-Power Asymmetric Multicast Routing: P-SPT (pruned shortest-path tree), P-MST (pruned minimum spanning tree), and P-BIP (pruned broadcasting incremental power). In this paper, we first prove that the approximation ratios of these three heuristics are at least (n-1/2),n-1, and n-2-o(1), respectively. We then present constant-approxiation algorithms for Min-Power Asymmetric Multicast Routing. We show that any /spl rho/-approximation Steiner tree algorithm gives rise to a c/spl rho/-approximation heuristic for Min-Power Asymmetric Multicast Routing, where c is a constant between 6 and 12. In particular, the Takahashi-Matsuyama Steiner tree heuristic leads to a heuristic called SPF (shortest-path first), which has an approximation ratio of at most 2c. We also present another heuristic, called MIPF (minimum incremental path first), for Min-Power Asymmetric Multicast Routing and show that its approximation ratio is between (13/3) and 2c. Both SPF and MIPF can be regarded as an adaptation of MST and BIP, respectively, in a different manner than pruning. Finally, we prove that any /spl rho/-approximation Steiner tree algorithm also gives rise to a 2/spl rho/-approximation algorithm for Min-Power Symmetric Multicast Routing.     

Multicriteria Steiner tree with the cost of Steiner vertices

The multicriteria problem of constructing the Steiner tree with consideration for the cost of additional Steiner vertices is studied. Formulations of the problems of constructing the covering Steiner trees and algorithmic approaches are described. The engineering formulation of the problem is aimed at constructing a telecommunications network with allowance for the spatial distribution of radio interferences. An approach to solving the formulated milticriterion problem on the basis of combination of two solving schemes is proposed: (1) the basic scheme for constructing a covering Steiner tree on the basis of clustering the vertices of the initial graph and (2) the general scheme for constructing the covering Steiner trees with allowance for the number of additional vertices and calculation of the Pareto-efficient solutions. A module based on the modified Prim’s algorithm for constructing a multicriteria covering tree is additionally used. The vertices of the initial graph are clustered on the basis of a hierarchical algorithm. Examples of a computational experiment on constructing the multicriteria Steiner trees are given.     

On finding minimum cost tree for multi-resource manycast in mesh networks

We investigate the problem of multi-resource manycast in mesh networks. The problem of multi-resource manycast extends the traditional manycast problem or k-Steiner tree problem, which finds a minimum cost tree spanning any k vertices. For the traditional manycast, all the vertices in the set of candidate destinations will be regarded as identical. However, the computing capability of the resource at each vertex may be not equivalent in the realistic networks. In this paper, we consider the problem of multi-resource manycast, in which the computing capability of the resource at a vertex is decomposed into discrete units. That is, each vertex may have multiple units of computing resources. The objective is to find a minimum cost tree spanning any k units of computing resources distributed in the networks. We show that multi-resource manycast is NP-Complete. The ILP formulation and approximation analysis are given for this problem. Simple polynomial-time heuristic algorithms are also proposed for the problem of multi-resource manycast. We investigate various approaches to implement multi-resources manycast in mesh networks, and verify the effectiveness of the approaches through simulation.     

A heuristic for constructing a rectilinear Steiner tree by reusing routing resources over obstacles

The obstacle-avoiding rectilinear Steiner minimal tree (OARSMT) problem is a hot topic in very-large-scale integration physical design. In practice, most of the obstacles occupy the device layer and certain lower metal layers. Therefore, we can place wires on top of the obstacles. To maximize routing resources over obstacles, we propose a heuristic for constructing a rectilinear Steiner tree with slew constraints. Our algorithm adopts an extended rectilinear full Steiner tree grid as the routing graph. We mark two types of Steiner point candidates, which are used for constructing Steiner trees and refining solutions. A shortest path heuristic variant is designed for constructing Steiner trees and it takes into account slew constraint by inhibiting growth. Furthermore, we use a pre-computed strategy to avoid calculating slew rate repeatedly. Experimental results show that our algorithm maximizes routing resources over obstacles and saves routing resources outside obstacles. Compared with the conventional OARSMT algorithm, our algorithm reduces the wire length outside obstacles by as much as 18.74% and total wire length by as much as 6.03%. Our algorithm improves the latest related algorithm by approximately 2% in terms of wire length within a reasonable running time. Additionally, calculating the slew rate only accounts for approximately 15% of the total runing time.     

组播路由调度的神经网络方法

本文探讨了在高速包交换计算机网络中，具有端到端时延及时延抖动限制的组播路由问题。首先给出了此类问题的网络模型及其数学描述，然后提出了基于Ｈｏｐｆｉｅｌｄ神经网络的组播路由优化算法。实验表明，本算法能根据组播应用对时延的要求，快速、有效地构造最优组播树，有较强的实时性。     

On average throughput and alphabet size in network coding

We examine the throughput benefits that network coding offers with respect to the average throughput achievable by routing, where the average throughput refers to the average of the rates that the individual receivers experience. We relate these benefits to the integrality gap of a standard linear programming formulation for the directed Steiner tree problem. We describe families of configurations over which network coding at most doubles the average throughput, and analyze a class of directed graph configurations with N receivers where network coding offers benefits proportional to /spl radic/N. We also discuss other throughput measures in networks, and show how in certain classes of networks, average throughput bounds can be translated into minimum throughput bounds, by employing vector routing and channel coding. Finally, we show configurations where use of randomized coding may require an alphabet size exponentially larger than the minimum alphabet size required.     

Distributed center-location algorithms

Recent multicast routing protocol proposals such as protocol independent multicast (PIM) and core-based trees (CBT) have been based on the notion of group-shared trees. Since construction of a minimal-cost tree spanning for all members of a group is difficult, they rely on center-based trees and distribute packets from all sources over a single shortest-path tree rooted at some center. PIM and CBT provisionally use administrative selection or simple heuristics for locating the center of a group but do not preclude the use of other methods that provide an ordered list of centers. Other previously proposed heuristics typically require knowledge of the complete network topology, a requirement which is not always practical for a distributed problem such as Internet routing. We investigate the problem of finding a good center in a distributed fashion, study various heuristics for automating center selection, and examine their applicability to real-world networks. We also propose several new algorithms which we feel to be more practical than existing methods. We present simulation results on hierarchical and nonhierarchical networks showing that of the methods potentially feasible in the Internet multicast backbone, ours offer the best results in terms of cost and delay, and they incur low overhead     

Wavelength assignment for multicast in all-optical WDM networks with splitting constraints

Multicast is an important application in all-optical WDM networks. The wavelength assignment problem for WDM multicast is to assign a set of wavelengths to the links of a given multicast tree. In an all-optical WDM network without wavelength conversions, wavelength assignment is the key to guarantee the quality of service and to reduce communication costs. In this paper, we study wavelength assignment for WDM multicast with two criteria, to cover the maximum number of destinations, and to minimize the wavelength costs. The computational complexity of the problem is studied. Three heuristic algorithms are proposed and the worst-case approximation ratios for some heuristic algorithms are given. We also derive a lower bound of the minimum total wavelength cost and an upper bound of the maximum number of reached destinations. The efficiency of the proposed heuristic algorithms and the effectiveness of the derived bounds are verified by the simulation results.