Network delay tomography

The substantial overhead of performing internal network monitoring motivates techniques for inferring spatially localized information about performance using only end-to-end measurements. In this paper, we present a novel methodology for inferring the queuing delay distributions across internal links in the network based solely on unicast, end-to-end measurements. The major contributions are: 1) we formulate a measurement procedure for estimation and localization of delay distribution based on end-to-end packet pairs; 2) we develop a simple way to compute maximum likelihood estimates (MLEs) using the expectation-maximization (EM) algorithm; 3) we develop a new estimation methodology based on recently proposed nonparametric, wavelet-based density estimation method; and 4) we optimize the computational complexity of the EM algorithm by developing a new fast Fourier transform implementation. Realistic network simulations are carried out using network-level simulator ns-2 to demonstrate the accuracy of the estimation procedure.     

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     

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     

Algorithm for minimum end-to-end delay paths

We consider the transmission of a message of size r from a source to a destination with the minimum end-to-end delay over a computer network where bandwidth can be reserved and guaranteed on the links. Different paths will be required for different intervals of values for r. We propose a polynomial-time algorithm that computes a table that maps all intervals for r to the corresponding paths that minimize the end-to-end delay     

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.     

有时延及时延差别约束的最小代价组播路由问题

本文把有时延、时延差别约束的组播路由问题提到优化的层次上,提出了有时延、时延差别约束的最小代价组播路由优化问题,并证明此问题是NP－complete问题。继而提出了一种基于动态罚函数法的启发式遗传算法以及解该问题,并分析了算法的复杂度。仿真表明,本文算法是有效的、稳定的。在满足两种约束的情况下,能够使网络代价优化。     

Node delay assignment strategies to support end-to-end delay requirements in heterogeneous networks

In a complex, heterogeneous network environment, such as the Internet, packets traversing different networks may be subjected to different treatments and may face different traffic loads across the routing path. This paper addresses the key issue of how to assign delay budgets to each network node along the routing path so that the end-to-end delay requirements of the supported applications are met. First, we describe a methodology to compute for a given flow a set of feasible per-node delays for the class of delay-based servers. We then formalize an optimal per-node delay assignment problem which takes into consideration the workload across the routing path. The solution, for homogeneous and heterogeneous networks, is provided. The resulting solution is optimal, but its implementation overhead is relatively high. To overcome this shortcoming, we propose two heuristics, EPH() and LBH(), to approximate the optimal strategy. EPH() uses the equi-partition concept to compute initial delay values and adjust these delay values to meet the end-to-end delay requirements. LBH() uses a relaxation factor to distribute the load proportionally across all nodes on the routing path. A simulation-based comparative analysis shows that the heuristics perform closely to the optimal schemes.     

Towards an end-to-end delay analysis of wireless multihop networks

In wireless multihop networks, end-to-end (e2e) delay is a critical parameter for quality of service (QoS) guarantees. We employ discrete-time queueing theory to analyze the end-to-end (e2e) delay of wireless multihop networks for two MAC schemes, m-phase TDMA and slotted ALOHA. In one-dimensional (1-D) networks, due to the lack of sufficient multiplexing and splitting, a space–time correlation structure exists, the nodes are spatially correlated with each other, and the e2e performance cannot be analyzed as in general two-dimensional networks by assuming all nodes independent of each other. This paper studies an 1-D network fed with a single flow, an extreme scenario in which there is no multiplexing and splitting. A decomposition approach is used to decouple the whole network into isolated nodes. Each node is modeled as a GI/Geo/1 queueing system. First, we derive the complete per-node delay distribution and departure characterization, accounting for both the queueing delay and access delay. Second, based on the departure process approximation, we define a parameter to measure the spatial correlation and its influence on the e2e delay variance. Our study shows that traffic burstiness of the source flow and MAC together determines the sign of the correlation.     

基于统计网络演算的端到端时延上界研究

为分析融合网络端到端统计时延性能,根据最小加代数理论中的统计网络演算相关知识,提出了一种改进的统计服务曲线并应用GPS调度系统模型,然后利用网络演算理论求解串型网络节点统计时延上界。数值分析结果表明,改进的调度模型有效改善了自相关特性对时延上界所造成的影响,比未改进的模型相比统计时延上界更具有良好的紧致性,为在融合网络环境中对端到端节点延迟上界研究提供有效控制、调度和管理具有一定的参考价值。     

一种基于聚合流的端到端统计时延界的新算法

为分析融合网络中聚合业务的端到端时延性能,提出一种基于聚合流的融合网络端到端统计时延界的新算法.该算法利用MGF(矩母函数)重新表征了网络端到端时延界的MGF形式的概率模型.数值分析结果表明了该算法的有效性和优越性,该算法很大程度上提高了独立统计复用,对融合网络性能评价具有参考意义.     

基于链路重构—解构的端到端网络链路时延推测研究简

基于网络时延推测的2个假设、时延推测模型和路径时延数据采集方法,提出了一种基于链路重构—解构的端到端网络链路时延推测方法,应用伪似然估计将原整体问题分解为若干独立子问题分别求解,利用链路重构—解构确定可求解的推测单元,控制平均采样精度和减少推测单元链路数,从而显著降低计算复杂度。通过基于模型的计算和基于NS2的仿真实验研究,验证了推测方法的准确性和有效性。     

多信道广播组总延误端到端延迟变化路由问题

在高速分组交换环境中,提出了构造多信道广播树,且满足实时交互性应用端到端变化要求的总延误问题.多信道广播路由将寻找从源到包括所有多信道广播终端的一棵有根树.在多媒体应用中,关于路由问题有两种要求:最小总延误和延迟变化.在实践中链路延迟和终端延迟的概念是有区别的.重新定义延迟的概念,也就是端到端的路径延迟定义为截止延迟或界定延迟,延误成员数的延迟定义为松驰延迟.终端的松驰延迟具有的特征是沿着一棵树从源到任何一个终端的累积延迟可以超过松驰延迟的值.确定这样一棵约束树的问题是NP-完全的.由时间的复杂性和动态成员的灵活性,提出了一个有效的启发式算法.     

Adaptive per hop differentiation for end-to-end delay assurance in multihop wireless networks

As the rapid growth of smart hand-held devices, multihop wireless access networks have a lot of potential applications in a variety of fields in civilian and military environments. Many of these applications, such as realtime audio/video streaming, will require some form of end-to-end QoS assurance. In this paper, we present an adaptive per hop differentiation (APHD) scheme towards achieving end-to-end delay assurance in multihop wireless networks. Our scheme is based on EDCA technique which is proposed in 802.11e draft. In EDCA, data packets of different priorities will use different MAC contention parameter set, which translate into different delays. Our APHD scheme extends the capability of EDCA into multihop environment by taking end-to-end delay requirement into consideration at each intermediate hop. Following a cross-layer design approach, APHD is aimed to be a distributed and localized technique. Individual nodes keep track of the channel state independently without any intercommunication overhead. Data packets carry end-to-end delay requirement along with other important information in the packet header. At an intermediate node, based on data packet’s end-to-end requirement, its accumulative delay so far, and the current node’s channel status, APHD smartly adjusts data packet’s priority level in order to satisfy its end-to-end delay requirement. Simulation results show that APHD scheme can provide excellent end-to-end delay assurance while achieving much higher network utilization, compared to a pure EDCA scheme.     

An average velocity-based routing protocol with low end-to-end delay for wireless sensor networks

To reduce energy consumption, in most MAC protocols for wireless sensor networks, listen-sleep cycles are adopted. However, even though it is a good solution for energy efficiency, it may introduce a large end-to-end delay due to sleep delay, since a node with a packet to transmit should wait until the next-hop node of the packet awakes. To resolve this issue, in this paper, we propose the Average Velocity-Based Routing (AVR) protocol for wireless sensor networks that aims at reducing the end-toend delay. The AVR protocol is a kind of a geographic routing protocol that considers both location of a node and waiting time of a packet at the MAC layer. When a node can use information of n-hop away neighbor nodes, it calculates the n-hop average velocity for each of its one-hop neighbor nodes and forwards a packet to the neighbor node that has the highest n-hop average velocity. Simulation results show that as the knowledge range, n, increases, the average end-to-end delay decreases.     

Bounded end-to-end delay with Transmission Power Control techniques for rechargeable wireless sensor networks

Due to sporadic availability of energy, a fundamental problem in rechargeable wireless sensor networks is nodes have to adjust their duty cycles continuously. On the other hand, the energy harvested from surrounding environment usually is not enough to power sensor nodes continually. Therefore, the nodes have to operate in a very low duty cycle. These unique characteristics cause packet delivery latency is critical in Rechargeable WSNs. At the same time, energy storage device of a node is always limited. Hence, the node cannot be always beneficial to conserve energy when a network can harvest excessive energy from the environment. In this work, we introduce a scheme by improving transmission power of nodes to bound E2E delay. We provide an algorithm for finding the minimal sleep latency from a node to a sink by increasing minimal h number of nodes whose transmission power improved. For bounding E2E delay from source node to the sink, we propose an E2E delay maintenance solution. Through extensive simulation and experiments, we demonstrate our delay bound maintenance scheme is efficient to provide E2E delay guarantees in rechargeable wireless sensor networks.     

Queue management based duty cycle control for end-to-end delay guarantees in wireless sensor networks

In this paper, we propose an analytical method for duty cycle adaptation in wireless sensor networks so that delay requirement is guaranteed while power consumption is minimized. The proposed method, named Dual-QCon, provides a formal method for stabilizing controller design based on queue management in order to control both duty cycle and queue threshold according to changing network conditions. Dual-QCon also provides a delay notification mechanism in order to determine an appropriate queue threshold of each node according to the application-dependent and time-varying delay requirements. Based on control theory, we analyze the adaptive behavior of the proposed method and derive conditions for system stability. Asymptotic analysis shows that Dual-QCon guarantees end-to-end delay requirement by controlling parameters of local nodes. Simulation results indicate that Dual-QCon outperforms existing scheduling protocols in terms of delay and power consumption.     

Superresolution of multipath delay profiles measured by PNcorrelation method

Time resolution of multipath delay profiles measured by using the autocorrelation of a pseudonoise (PN) code sequence is generally limited by the chip interval of the PN code sequence. A superresolution PN correlation method (SPM) is proposed which improves the time resolution of delay profiles measured by the conventional PN correlation method. The SPM is based on a decomposition of the eigenvector space of the correlation matrix of the delay profile data vector and gives the number of paths and their delay times with higher resolution. It is verified by computer simulations and experiments using coaxial delay lines that the SPM can resolve two paths with a delay difference of a few tenths of the chip interval. The applicability of the SPM to the analysis of an indoor multipath environment in which many delayed waves arrive with short delay differences is demonstrated by an indoor radio propagation experiment at 2.3 GHz     

构建时间、空间、网络层次端到端安全网络

针对目前IP网对安全的新要求,华为提出了“i^3安全”解决方案．即时间、空间、网络层次三个纬度端到端集成安全体系架构。此方案所具有的特色包括：在时间上,同时关注网络的事前防范和事后跟踪能力;在空间上,针时外网与内网的不同特点制定有效的安全策略;在网络层次上,分别根据网络层、用户接入层和业务层的特点进行有针对性的防范。     

基于分形漏桶的长程相关业务端到端延迟上界模型

为了求解以长程相关业务作为输入的网络端到端延迟上界,提出了基于分形漏桶和GPS系统的端到端网络模型,利用网络演算理论证明了分形漏桶的引入不增加网络端到端延迟上界,建立了端到端延迟理想及其近似确定上界模型.数值结果表明,分形漏桶有效改善了长程相关特性对端到端延迟上界所造成的影响,与简单漏桶相比,基于分形漏桶的长程相关业务端到端延迟上界具有更好的紧致性.     

采用频域光延迟线的光学相干层析成像

频域光延迟线是一种光学扫描结构,其基本组成是一个衍射光栅、一个透镜和一个扫描镜.把频域光延迟线应用到光学相干层析成像系统中,可以使参考臂扫描速率至少达到数m/s以上,从而实现视频速率的图像获取.从几何光学的角度分析了频域光延迟线的工作原理,分析结果表明在扫描角很小的情况下,入射光的光程或相位变化频率与扫描角频率有较好的线性关系.基于这一结构的光学相干层析成像的结果证明可以避免活体生物组织位移引入的图像模糊.另外,还提出了一种基于微执行器的新扫描装置.