Towards a Generalized Stochastic Model of End-to-End Packet-Pair Sampling

End-to-end packet-pair probing has been used as one of the primary mechanisms to measure bottleneck capacity, cross-traffic intensity, and available bandwidth of end-to-end Internet paths. However, there has been lacking an understanding of what types of information about the path are sampled by packet-pairs and how they are encoded in the corresponding output dispersions. In this paper, we answer these questions by deriving the expression of individual output spacings (i.e., dispersions) in the context of multihop paths and general bursty cross-traffic arrivals. Based on these results, we examine stochastic properties of the sampled signals and derive the statistical mean of the output interpacket spacings as a recursive function of the input spacing. We show that the result is different from what has been obtained in prior work using fluid cross-traffic models and that this discrepancy has a significant adverse impact on the accuracy of packet-pair bandwidth measurement techniques     

Packet-dispersion techniques and a capacity-estimation methodology

The packet-pair technique aims to estimate the capacity of a path (bottleneck bandwidth) from the dispersion of two equal-sized probing packets sent back to back. It has been also argued that the dispersion of longer packet bursts (packet trains) can estimate the available bandwidth of a path. This paper examines such packet-pair and packet-train dispersion techniques in depth. We first demonstrate that, in general, packet-pair bandwidth measurements follow a multimodal distribution and explain the causes of multiple local modes. The path capacity is a local mode, often different than the global mode of this distribution. We illustrate the effects of network load, cross-traffic packet-size variability, and probing packet size on the bandwidth distribution of packet pairs. We then switch to the dispersion of long packet trains. The mean of the packet-train dispersion distribution corresponds to a bandwidth metric that we refer to as average dispersion rate (ADR). We show that the ADR is a lower bound of the capacity and an upper bound of the available bandwidth of a path. Putting all of the pieces together, we present a capacity-estimation methodology that has been implemented in a tool called pathrate. We report on our experiences with pathrate after having measured hundreds of Internet paths over the last three years.     

IP网可用带宽快速检测方法SSP的研究与应用

在IP网中,可用带宽是最重要的网络资源,是网络传输性能的决定因素,可用带宽的实时检测具有重要的研究和现实意义.本文对当前典型的端到端的可用带宽测量工具Pathload进行了研究,分析了Pathload工具检测算法的优点以及不足,提出了一种快速而精确的带宽测量方法--SSP,通过它可以快速检测到端到端路径的可用带宽值,为有效利用网络资源、支持QoS服务和多媒体实时业务提供了保证.     

Measuring Capacity Bandwidth of Targeted Path Segments

Accurate measurement of network bandwidth is important for network management applications as well as flexible Internet applications and protocols which actively manage and dynamically adapt to changing utilization of network resources. Extensive work has focused on two approaches to measuring bandwidth: measuring it hop-by-hop, and measuring it end-to-end along a path. Unfortunately, best-practice techniques for the former are inefficient and techniques for the latter are only able to observe bottlenecks visible at end-to-end scope. In this paper, we develop end-to-end probing methods which can measure bottleneck capacity bandwidth along arbitrary, targeted subpaths of a path in the network, including subpaths shared by a set of flows. We evaluate our technique through ns simulations, then provide a comparative Internet performance evaluation against hop-by-hop and end-to-end techniques. We also describe a number of applications which we foresee as standing to benefit from solutions to this problem, ranging from network troubleshooting and capacity provisioning to optimizing the layout of application-level overlay networks, to optimized replica placement.      

FEBA: A Bandwidth Allocation Algorithm for Service Differentiation in IEEE 802.16 Mesh Networks

In wireless mesh networks, the end-to-end throughput of traffic flows depends on the path length, i.e., the higher the number of hops, the lower becomes the throughput. In this paper, a fair end-to-end bandwidth allocation (FEBA) algorithm is introduced to solve this problem. FEBA is implemented at the medium access control (MAC) layer of single-radio, multiple channels IEEE 802.16 mesh nodes, operated in a distributed coordinated scheduling mode. FEBA negotiates bandwidth among neighbors to assign a fair share proportional to a specified weight to each end-to-end traffic flow. This way traffic flows are served in a differentiated manner, with higher priority traffic flows being allocated more bandwidth on the average than the lower priority traffic flows. In fact, a node requests/grants bandwidth from/to its neighbors in a round-robin fashion where the amount of service depends on both the load on its different links and the priority of currently active traffic flows. If multiple channels are available, they are all shared evenly in order to increase the network capacity due to frequency reuse. The performance of FEBA is evaluated by extensive simulations. It is shown that wireless resources are shared fairly among best-effort traffic flows, while multimedia streams are provided with a differentiated service that enables quality of service.     

一种基于端到端测量的路径性能参数估计算法

现有的网络性能估计技术不能实现对路径容量和可用带宽的同时测量。该文通过对存在拥塞链路的路径作随机分析,得到了一种对路径可用带宽的近似估计式,并通过对Kapoor(2004)中的方法进行改进, 提出了一种基于端到端的可以同时对单拥塞路径的容量及可用带宽进行估算的算法。在较准确估算路径容量的同时,达到了用同一组样本实例同时估计路径容量和可用带宽的目的。仿真验证了算法的有效性和准确性。     

FAST CAPACITY ESTIMATION ALGORITHMS FOR MANETS USING DIRECTIONAL ANTENNAS

In this letter,capacity estimation for Mobile Ad hoc NETworks (MANETs) using direc- tional antennas are studied.Two Matrix-based Fast Calculation Algorithms (MFCAs) are proposed to estimate the network capacity in a network scenario in which there is no channel sharing among multiple sessions and traffic is sensitive to delay with an end-to-end delay constraint.The first algo- rithm MFCA-1 is used to estimate network capacity in a situation where all links have the same delay. It estimates the maximum number of k-hop sessions in a network based on the k-hop adjacency matrix of the network.The second algorithm MFCA-2 is used to estimate network capacity in a situation where different links may have different delays.It calculates the maximum number of sessions in a network with an end-to-end delay constraint based on the adjacency matrix and the link-delay matrix of the network.Numerical and simulation results show that both MFCA-1 and MFCA-2 can calculate network capacity much faster than the well-known Brute-Force Search Algorithm (BFSA) but with the same accuracy.     

Estimating the channel capacity of multi-hop IEEE 802.11 wireless networks

In IEEE 802.11 wireless networks, the residual capacity of the wireless links should be accurately estimated to realize advanced network services such as flow admission control or load balancing. In this paper, we propose an algorithm that estimates the packet delivery failure probability by collecting transmission statistics from nearby nodes, and by using a basic collision detection mechanism. This probability is then used in an analytical model to calculate the maximum allowable traffic needed to reach the saturation condition. We show by simulations that estimation error is within 0.5–5.0%, which is significantly lower than the best performance of prior estimation methods. We also demonstrate that the flow admission control is successfully achieved in a realistic wireless network scenario by the help of accurate link residual bandwidth estimation, where the unsatisfied traffic demand remain bounded at a negligibly low level. A routing algorithm that finds max–min residual bandwidth path between source and destination nodes is also implemented, and simulation results show that the network throughput achieved by this algorithm significantly exceeds that of other popular mesh routing protocols. Finally, we provide test results from the real implementation of our algorithm on 802.11 wireless equipment, which are consistent with the simulations.     

Evaluation and characterization of available bandwidth probing techniques

The packet pair mechanism has been shown to be a reliable method to measure the bottleneck link capacity on a network path, but its use for measuring available bandwidth is more challenging. In this paper, we use modeling, measurements, and simulations to better characterize the interaction between probing packets and the competing network traffic. We first construct a simple model to understand how competing traffic changes the probing packet gap for a single-hop network. The gap model shows that the initial probing gap is a critical parameter when using packet pairs to estimate available bandwidth. Based on this insight, we present two available bandwidth measurement techniques, the initial gap increasing (IGI) method and the packet transmission rate (PTR) method. We use extensive Internet measurements to show that these techniques estimate available bandwidth faster than existing techniques such as Pathload, with comparable accuracy. Finally, using both Internet measurements and ns simulations, we explore how the measurement accuracy of active probing is affected by factors such as the probing packet size, the length of probing packet train, and the competing traffic on links other than the tight link.     

Bandwidth estimation: metrics, measurement techniques, and tools

In a packet network, the terms bandwidth and throughput often characterize the amount of data that the network can transfer per unit of time. Bandwidth estimation is of interest to users wishing to optimize end-to-end transport performance, overlay network routing, and peer-to-peer file distribution. Techniques for accurate bandwidth estimation are also important for traffic engineering and capacity planning support. Existing bandwidth estimation tools measure one or more of three related metrics: capacity, available bandwidth, and bulk transfer capacity. Currently available bandwidth estimation tools employ a variety of strategies to measure these metrics. In this survey we review the recent bandwidth estimation literature focusing on underlying techniques and methodologies as well as open source bandwidth measurement tools.     

一种基于带宽接入控制的AODV改进路由协议

无线自组网中的路由协议AODV没有提供流控和拥塞避免机制,当网络负载较重时,多媒体业务或产生较大的延时,或分组被大量丢弃,使网络性能下降.在AODV协议的基础上,提出一种基于带宽接入控制的改进协议BAC-AODV,对节点和路径的可用带宽进行估算,修改路由建立机制,使路径满足业务流对带宽的需求,保证网络的QoS质量.分析和仿真结果表明,改进后的协议相比原有AODV,能更有效地控制业务流量,提高吞吐量,降低延时.     

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     

Packet triplet: a novel approach to estimate path capacity

Packet Pair is an end-to-end approach to estimate the capacity of an Internet path. Many studies have shown that such estimation exhibits a lot of bias due to the dynamic cross traffic. In this paper, we propose a novel approach, called Packet Triplet, which uses three back-to-back probing packets - different from two back-to-back probing packets in Packet Pair - to estimate the capacity of a network path. A new filtering technique is also introduced into Packet Triplet to further refine the path capacity estimation approach. The experiments demonstrate that such probing approach is effective under different cross traffic.     

A QoS-aware routing mechanism for multi-channel multi-interface ad-hoc networks

To accommodate real-time multimedia application while satisfying application QoS requirements in a wireless ad-hoc network, we need QoS control mechanisms. In this paper, we propose a new routing mechanism to support real-time multimedia communication by efficiently utilize the limited wireless network capacity. Our mechanism considers a wireless ad-hoc network composed of nodes equipped with multiple network interfaces to each of which a different wireless channel can be assigned. By embedding information about channel usage in control messages of OLSRv2, each node obtains a view of topology and bandwidth information of the whole network. Based on the obtained information, a source node determines a logical path with the maximum available bandwidth to satisfy application QoS requirements. Through simulation experiments, we confirmed that our proposal effectively routed multimedia packets over a logical path avoiding congested links. As a result, the load on a network is well distributed and the network can accommodate more sessions than QOLSR. We also conducted practical experiments using wireless ad-hoc relay nodes with four network interfaces and verified the practicality of our proposal.     

Evaluating the impact of network density,hidden nodes and capture effect for throughput guarantee in multi-hop wireless networks

To optimize the performance of wireless networks, one needs to consider the impact of key factors such as interference from hidden nodes, the capture effect, the network density and network conditions (saturated versus non-saturated). In this research, our goal is to quantify the impact of these factors and to propose effective mechanisms and algorithms for throughput guarantees in multi-hop wireless networks. For this purpose, we have developed a model that takes into account all these key factors, based on which an admission control algorithm and an end-to-end available bandwidth estimation algorithm are proposed. Given the necessary network information and traffic demands as inputs, these algorithms are able to provide predictive control via an iterative approach. Evaluations using analytical comparison with simulations as well as existing research show that the proposed model and algorithms are accurate and effective.     

Design and Performance Analysis of a Proxy-Based Indirect Routing Scheme in Ad Hoc Wireless Networks

The majority of existing ad hoc network routing protocols has a tendency to use the shortest single path from a source to a destination. However, in constantly changing topologies such as those in mobile ad hoc wireless networks, the shortest single path is not only unreliable for reachability but also unsuitable for traffic load equilibrium. In order to improve routing performance and make optimum use of the limited resources, the congestion must first be relieved as much as possible and the routing path be made available at all times. In this paper, we propose a novel scheme, called the Applicative Indirect Routing (AIR), to control network traffic congestion and refine route availability by coping with unreliable links quickly. The proposed scheme, acting as a proactive routing protocol, utilizes additional information about the neighbors shared by the sender and the receiver to find an alternative for the original path with unreliable links. The additional bandwidth usage in AIR to obtain the information about shared neighbors (defined as proxy candidates) is so minimal that the bandwidth availability for user data traffic is not significantly affected. Extensive simulation experiments show that compared with a conventional proactive protocol, namely Destination-Sequenced Distance Vector (DSDV), the AIR scheme leads to a much improved system performance in terms of packet delivery ratio, average end-to-end packet delay, and network reliability. We further show that, in terms of packet delivery ratio, AIR is also a competitive protocol compared with such reactive protocols as Ad hoc On Demand Distance Vector (AODV) and Dynamic Source Routing (DSR).     

虚级联信号的链路容量调整机制LCAS及其在新一代SDH智能带宽响应中的应用

通用成帧规程GFP、VC虚级联和链路容量调整机制LCAS是有效实现Data over SDH(DoS)的新型协议。基于此运营商可以实现网络带宽的动态分配响应。通过分析LCAS的特点、结构和功能实现方式,指出其作为一种源-宿之间无损伤的改变虚级联组容量大小的握手信令协议,其服务可以建立在集中或分布式控制基础上。特别分析了结合基于GMPLS/ASTN的智能化控制平面,LCAS将进一步拓展BoD应用。     

Bandwidth Estimation for IEEE 802.11-Based Ad Hoc Networks

Since 2005, IEEE 802.11-based networks are able to provide a certain level of Quality of Service by the means of service differentiation, thanks to the IEEE 802.11e amendment. However, no mechanism or method has been standardized to accurately evaluate the amount of resources remaining on a given channel. Such evaluation would however be a good asset for bandwidth-constrained applications. In multi-hop ad hoc networks, such evaluation becomes even more difficult. Consequently, despite the various contributions around this research topic, the estimation of the available bandwidth still represents one of the main issues in this field. In this article, we propose an improved mechanism to estimate the available bandwidth in IEEE 802.11-based ad hoc networks. Through simulations, we compare the accuracy of the estimation we propose to the estimation performed by others state of the art QoS protocols, BRuIT, AAC and QoS-AODV.     

A multi-path cognitive resource management mechanism for QoS provisioning in wireless mesh networks

In a Wireless Mesh Network (WMN), achieving acceptable Quality of Service (QoS) levels requires distributed control over network resources and subsequent awareness of the dynamically changing conditions of the WMN. In this paper, for facilitating such control, a cognitive mechanism is introduced, which facilitates cooperation and cognition among multiple Mesh Access Points and edge routers called Mesh Portals for routing client traffic via multiple paths. The aim of the cognition is to reasonably maximize the fulfillment of the clients from the achieved QoS (e.g., end-to-end delay and bandwidth). The cognitive process consists of three cycles. In the first cycle, the Perception Cycle, the current performance status of the WMN is continuously perceived through feedback loops. The perceived information is further processed and fed into the second cycle, the Learning Cycle, in order to understand the network conditions. This results in the prediction of the performance of the paths and estimation of the path delay for various load conditions. The third cycle, the Decision Cycle, is a game theoretic coalition formation algorithm, that results in path selection and data rate assignment. This algorithm is modeled as a cooperative game theory, which incorporates the Bilateral Shapley Value to find the best coalition from available paths, whereupon a bargaining game theory formulates the data rate assignment. Extensive simulations are performed for evaluating the proposed cognitive mechanism under various load conditions and results demonstrate the evident enhancement of the achieved end-to-end QoS of the clients and the network performance compared with non-cognitive scenarios, specifically in congested conditions.     

基于可用带宽测量的分层组播拥塞控制机制

针对现有的组播拥塞控制机制对接收端可用带宽估计精度较低的问题,提出了一种基于可用带宽测量的分层组播拥塞控制机制ABM-LMCC.在分析了现有可用带宽估计方法不足的基础上,提出一种适用于组播的可用带宽测量算法,并设计了分层组播拥塞控制机制的具体操作规程.通过调节组播数据包的发送间隔,使其呈现降速率的指数分布,从而实现各接收端对可用带宽的准确测量,并根据其测量值迅速调节期望速率,从而达到组播拥塞控制的目的.仿真表明,ABM-LMCC能够有效避免拥塞,提高链路利用率,显著降低丢包率,具有良好的响应性、稳定性.