Network tomography from measured end-to-end delay covariance

End-to-end measurement is a common tool for network performance diagnosis, primarily because it can reflect user experience and typically requires minimal support from intervening network elements. However, pinpointing the site of performance degradation from end-to-end measurements is a challenging problem. We show how end-to-end delay measurements of multicast traffic can be used to infer the under-lying logical multicast tree and the packet delay variance on each of its links. The method does not depend on cooperation from intervening network elements; multicast probing is bandwidth efficient. We establish desirable statistical properties of the estimator, namely consistency and asymptotic normality. We evaluate the approach through simulations, and analyze its failure modes and their probabilities.     

Multicast-based inference of network-internal loss characteristics

Robust measurements of network dynamics are increasingly important to the design and operation of large internetworks like the Internet. However, administrative diversity makes it impractical to monitor every link on an end-to-end path. At the same time, it is difficult to determine the performance characteristics of individual links from end-to-end measurements of unicast traffic. In this paper, we introduce the use of end-to-end measurements of multicast traffic to infer network-internal characteristics. The bandwidth efficiency of multicast traffic makes it suitable for large-scale measurements of both end-to-end and internal network dynamics. We develop a maximum-likelihood estimator for loss rates on internal links based on losses observed by multicast receivers. It exploits the inherent correlation between such observations to infer the performance of paths between branch points in the tree spanning a multicast source and its receivers. We derive its rate of convergence as the number of measurements increases, and we establish robustness with respect to certain generalizations of the underlying model. We validate these techniques through simulation and discuss possible extensions and applications of this work     

Algorithms for precomputing constrained widest paths and multicast trees

We consider the problem of precomputing constrained widest paths and multicast trees in a communication network. Precomputing and storing of the relevant information minimizes the computational overhead required to determine an optimal path when a new connection request arrives. We evaluate algorithms that precompute paths with maximal bandwidth (widest paths), which in addition satisfy given end-to-end delay constraints. We analyze and compare both the worst case and average case performance of the algorithms. We also show how the precomputed paths can be used to provide computationally efficient solutions to the constrained widest multicast tree problem. In this problem, a multicast tree with maximal bandwidth (widest multicast tree) is sought, which in addition satisfies given end-to-end delay constraints for each path on the tree from the source to a multicast destination.     

Multicast topology inference from measured end-to-end loss

The use of multicast inference on end-to-end measurement has been proposed as a means to infer network internal characteristics such as packet link loss rate and delay. We propose three types of algorithm that use loss measurements to infer the underlying multicast topology: (i) a grouping estimator that exploits the monotonicity of loss rates with increasing path length; (ii) a maximum-likelihood estimator (MLE); and (iii) a Bayesian estimator. We establish their consistency, compare their complexity and accuracy, and analyze the modes of failure and their asymptotic probabilities     

Optimal partition of QoS requirements on unicast paths andmulticast trees

We investigate the problem of optimal resource allocation for end-to-end QoS requirements on unicast paths and multicast trees. Specifically, we consider a framework in which resource allocation is based on local QoS requirements at each network link, and associated with each link is a cost function that increases with the severity of the QoS requirement. Accordingly, the problem that we address is how to partition an end-to-end QoS requirement into local requirements, such that the overall cost is minimized. We establish efficient (polynomial) solutions for both unicast and multicast connections. These results provide the required foundations for the corresponding QoS routing schemes, which identify either paths or trees that lead to minimal overall cost. In addition, we show that our framework provides better tools for coping with other fundamental multicast problems, such as dynamic tree maintenance     

Sequential Monte Carlo inference of internal delays innonstationary data networks

On-line, spatially localized information about internal network performance can greatly assist dynamic routing algorithms and traffic transmission protocols. However, it is impractical to measure network traffic at all points in the network. A promising alternative is to measure only at the edge of the network and infer internal behavior from these measurements. We concentrate on the estimation and localization of internal delays based on end-to-end delay measurements from a source to receivers. We propose a sequential Monte Carlo (SMC) procedure capable of tracking nonstationary network behavior and estimating time-varying, internal delay characteristics. Simulation experiments demonstrate the performance of the SMC approach     

Multicast Routing in Wireless Mesh Networks: Minimum Cost Trees or Shortest Path Trees?

There exist two fundamental approaches to multicast routing: shortest path trees (SPTs) and minimum cost trees (MCTs). The SPT algorithms minimize the distance (or cost) from the sender to each receiver, whereas the MCT algorithms minimize the overall cost of the multicast tree. Due to the very large scale and unknown topology of the Internet, computing MCTs for multicast routing in the Internet is a very complex problem. As a result, the SPT approach is the more commonly used method for multicast routing in the Internet, because it is easy to implement and gives minimum delay from the sender to each receiver, a property favored by many real-life applications. Unlike the Internet, a wireless mesh network (WMN) has a much smaller size, and its topology can be made known to all nodes in the network. This makes the MCT approach an equally viable candidate for multicast routing in WMNs. However, it is not clear how the two types of trees compare when used in WMNs. In this article we present a simulation-based performance comparison of SPTs and MCTs in WMNs, using performance metrics, such as packet delivery ratio, end-to-end delay, and traffic impacts on unicast flows in the same network.     

Network loss tomography using striped unicast probes

In this paper, we explore the use of end-to-end unicast traffic as measurement probes to infer link-level loss rates. We leverage off of earlier work that produced efficient estimates for link-level loss rates based on end-to-end multicast traffic measurements. We design experiments based on the notion of transmitting stripes of packets (with no delay between transmission of successive packets within a stripe) to two or more receivers. The purpose of these stripes is to ensure that the correlation in receiver observations matches as closely as possible what would have been observed if a multicast probe followed the same path to the receivers. Measurements provide good evidence that a packet pair to distinct receivers introduces considerable correlation which can be further increased by simply considering longer stripes. Using an M/M/1/K model for a link, we theoretically confirm this benefit for stripes. We also use simulation to explore how well these stripes translate into accurate link-level loss estimates. We observe good accuracy with packet pairs, with a typical error of about 1%, which significantly decreases as stripe length is increased.     

Maximum pseudo likelihood estimation in network tomography

Network monitoring and diagnosis are key to improving network performance. The difficulties of performance monitoring lie in today's fast growing Internet, accompanied by increasingly heterogeneous and unregulated structures. Moreover, these tasks become even harder since one cannot rely on the collaboration of individual routers and servers to measure network traffic directly. Even though the aggregative nature of possible network measurements gives rise to inverse problems, existing methods for solving inverse problems are usually computationally intractable or statistically inefficient. A pseudo likelihood approach is proposed to solve a group of network tomography problems. The basic idea of pseudo likelihood is to form simple subproblems and ignore the dependences among the subproblems to form a product likelihood of the subproblems. As a result, this approach keeps a good balance between the computational complexity and the statistical efficiency of the parameter estimation. Some statistical properties of the pseudo likelihood estimator, such as consistency and asymptotic normality, are established. A pseudo expectation-maximization (EM) algorithm is developed to maximize the pseudo log-likelihood function. Two examples, with simulated or real data, are used to illustrate the pseudo likelihood proposal: 1) inference of the internal link delay distributions through multicast end-to-end measurements; 2) origin-destination matrix estimation through link traffic counts.     

Multicast routing for multimedia communication

The authors present heuristics for multicast tree construction for communication that depends on: bounded end-to-end delay along the paths from source to each destination and minimum cost of the multicast tree, where edge cost and edge delay can be independent metrics. The problem of computing such a constrained multicast tree is NP-complete. It is shown that the heuristics demonstrate good average case behavior in terms of cost, as determined by simulations on a large number of graphs     

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.     

Multicast routing with end-to-end delay and delay variationconstraints

We study the problem or constructing multicast trees to meet the quality of service requirements of real-time interactive applications operating in high-speed packet-switched environments. In particular, we assume that multicast communication depends on: (1) bounded delay along the paths from the source to each destination and (2) bounded variation among the delays along these paths. We first establish that the problem of determining such a constrained tree is NP-complete. We then present a heuristic that demonstrates good average case behavior in terms of the maximum interdestination delay variation. The heuristic achieves its best performance under conditions typical of multicast scenarios in high speed networks. We also show that it is possible to dynamically reorganize the initial tree in response to changes in the destination set, in a way that is minimally disruptive to the multicast session     

Bayesian inference of network loss and delay characteristics with applications to TCP performance prediction

In large-scale dynamic communication networks, end systems cannot rely on the network itself to cooperate in characterizing its own behavior. This has prompted research activities on methods for inferring internal network behavior based on the external end-to-end network measurements. In particular, knowledge of the link losses and link delays inside the network is important for network management. However, it is impractical to directly measure packet losses or delays at every router. On the other hand, measuring end-to-end (from sources to destinations) losses or delays is relatively easy. We formulate the problems of link and delay estimation in a network based on end-to-end measurements as Bayesian inference problems and develop several Markov chain Monte Carlo (MCMC) algorithms to solve them. We show how these link loss and delay estimates can be used to predict point-to-point transfer control protocol (TCP) throughput in the network. We apply the proposed link loss and delay estimation algorithms, as well as the TCP throughput estimation algorithms, to data generated by the network simulator (ns-2) software and obtain good agreements between the theoretical results and the actual measurements.     

Efficient QoS Partition and Routing of Unicast and Multicast

In this paper, we study problems related to supporting unicast and multicast connections with quality of service (QoS) requirements. We investigate the problem of optimal routing and resource allocation in the context of performance dependent costs. In this context, each network element can offer several QoS guarantees, each associated with a different cost. This is a natural extension to the commonly used bi-criteria model, where each link is associated with a single delay and a single cost. This framework is simple yet strong enough to model many practical interesting networking problems. An important problems in this framework is finding a good path for a connection that minimizes the cost while retaining the end-to-end delay requirement. Once such a path (or a tree, in the multicast case) is found, one needs to partition the end-to-end QoS requirements among the links of the path (tree). We consider the case of general integer cost functions (where delays and cost are integers). As the related problem is NP complete, we concentrate on finding efficient epsiv-approximation solutions. We improve on recent previous results by Erguumln Lorenz and Orda, and Raz and Shavitt, both in terms of generality as well as in terms of complexity of the solution. In particular, we present novel approximation techniques that yield the best known complexity for the unicast QoS routing problem, and the first approximation algorithm for the QoS partition problem on trees, both for the centralized and distributed cases     

A ring-based multicast routing topology with QoS support in wireless mesh networks

Wireless mesh networking (WMN) is an emerging technology for future broadband wireless access. The proliferation of the mobile computing devices that are equipped with cameras and ad hoc communication mode creates the possibility of exchanging real-time data between mobile users in wireless mesh networks. In this paper, we argue for a ring-based multicast routing topology with support from infrastructure nodes for group communications in WMNs. We study the performance of multicast communication over a ring routing topology when 802.11 with RTS/CTS scheme is used at the MAC layer to enable reliable multicast services in WMNs. We propose an algorithm to enhance the IP multicast routing on the ring topology. We show that when mesh routers on a ring topology support group communications by employing our proposed algorithms, a significant performance enhancement is realized. We analytically compute the end-to-end delay on a ring multicast routing topology. Our results show that the end-to-end delay is reduced about 33 %, and the capacity of multicast network (i.e., maximum group size that the ring can serve with QoS guarantees) is increased about 50 % as compared to conventional schemes. We also use our analytical results to develop heuristic algorithms for constructing an efficient ring-based multicast routing topology with QoS guarantees. The proposed algorithms take into account all possible traffic interference when constructing the multicast ring topology. Thus, the constructed ring topology provides QoS guarantees for the multicast traffic and minimizes the cost of group communications in WMNs.     

A heuristic multicast algorithm to support QoS group communications in heterogeneous network

This paper examines the problem of quality-of-service group communications in a heterogeneous network, which consists of multiple mobile ad hoc networks attached to the backbone Internet. A heuristic multicast algorithm named delay and delay variation multicast algorithm (DDVMA) is proposed. DDVMA is designed for solving the delay- and delay-variation-bounded multicast tree problem, which has been proved to be NP-complete. It can find a multicast tree satisfying the multicast end-to-end delay constraint and minimizing the multicast delay variation. Two concepts, which can help the DDVMA achieve better performance in terms of multicast delay variation than the delay and delay variation constraint algorithm that is known to be the most efficient so far, are proposed, namely, 1) the proprietary second shortest path and 2) the partially proprietary second shortest path. An analysis is given to show the correctness of DDVMA, and simulations are conducted to demonstrate the performance improvement of DDVMA in terms of multicast delay variation. It is also shown that the strategy employed by DDVMA is also applicable to handling the mobility of mobile hosts in a heterogeneous network.     

On minimizing end-to-end delay with optimal traffic partitioning

Multipath transport provides higher usable bandwidth for a session. It has also been shown to provide load balancing and error resilience for end-to-end multimedia sessions. Two key issues in the use of multiple paths are 1) how to minimize the end-to-end delay, which now includes the delay along the paths and the resequencing delay at the receiver, and 2) how to select paths. This paper presents an analytical framework for the optimal partitioning of real-time multimedia traffic that minimizes the total end-to-end delay. Specifically, it formulates optimal traffic partitioning as a constrained optimization problem using deterministic network calculus and derives its closed-form solution. Compared with previous work, the proposed scheme is simpler to implement and enforce. This analysis also greatly simplifies the solution to the path selection problem as compared to previous efforts. Analytical results show that for a given flow and a set of paths, a minimal subset can be chosen to achieve the minimum end-to-end delay with O(N) time, where N is the number of available paths. The selected path set is optimal in the sense that adding any rejected path to the set will only increase the end-to-end delay.     

基于传输路径质量的无线mesh网络可靠多播

提出了一种可靠多播网(RM)模型,探讨了无线链路和节点可靠性对多播路径选择的影响。首先,建立了无线链路的相关性和多播路径的可靠性模型,并提出了多播传输的可靠性判据;同时,结合首树算法和多路径树算法提出了构造可靠多播网的算法。可靠多播网具有并行的多播路径,通过在多播源节点和目的节点之间选择多播链路和节点构成了可靠的多播路径,提供了多播路径的"负荷分担"和"热备份"功能,从而支持了多播业务可靠性。     

Efficient network QoS provisioning based on per node trafficshaping

This paper addresses the problem of providing per-connection end-to-end delay guarantees in a high-speed network. We consider a network comprised of store-and-forward packet switches, in which a packet scheduler is available at each output link. We assume that the network is connection oriented and enforces some admission control which ensures that the source traffic conforms to specified traffic characteristics. We concentrate on the class of rate-controlled service (RCS) disciplines, in which traffic from each connection is reshaped at every hop, and develop end-to-end delay bounds for the general case where different reshapers are used at each hop. In addition, we establish that these bounds can also be achieved when the shapers at each hop have the same “minimal” envelope. The main disadvantage of this class of service discipline is that the end-to-end delay guarantees are obtained as the sum of the worst-case delays at each node, but we show that this problem can be alleviated through “proper” reshaping of the traffic. We illustrate the impact of this reshaping by demonstrating its use in designing RCS disciplines that outperform service disciplines that are based on generalized processor sharing (GPS). Furthermore, we show that we can restrict the space of “good” shapers to a family which is characterized by only one parameter. We also describe extensions to the service discipline that make it work conserving and as a result reduce the average end-to-end delays     

Performance and resource cost comparisons for the CBT and PIMmulticast routing protocols

Researchers have proposed the core-based trees (CBTs) and protocol independent multicasting (PIM) protocols to route multicast data an internetworks. We compare the simulated performance of CBT and PIM using the OPNET network simulation tool. Performance metrics include end-to-end delay, network resource usage, join time, the size of the tables containing multicast routing information, and the impact of the timers introduced by the protocols. We also offer suggestions to improve PIM sparse mode while retaining the ability to offer both shared tree and source-based tree routing