Tight performance bounds in the worst-case analysis of feed-forward networks

Network Calculus theory aims at evaluating worst-case performances in communication networks. It provides methods to analyze models where the traffic and the services are constrained by some minimum and/or maximum envelopes (arrival/service curves). While new applications come forward, a challenging and inescapable issue remains open: achieving tight analyzes of networks with aggregate multiplexing. The theory offers efficient methods to bound maximum end-to-end delays or local backlogs. However as shown in a recent breakthrough paper (Schmitt et al. 2008), those bounds can be arbitrarily far from the exact worst-case values, even in seemingly simple feed-forward networks (two flows and two servers), under blind multiplexing (i.e. no information about the scheduling policies, except FIFO per flow). For now, only a network with three flows and three servers, as well as a tandem network called sink tree, have been analyzed tightly.We describe the first algorithm which computes the maximum end-to-end delay for a given flow, as well as the maximum backlog at a server, for any feed-forward network under blind multiplexing, with piecewise affine concave arrival curves and piecewise affine convex service curves. Its computational complexity may look expensive (possibly super-exponential), but we show that the problem is intrinsically difficult (NP-hard). Fortunately we show that in some cases, like tandem networks with cross-traffic interfering along intervals of servers, the complexity becomes polynomial. We also compare ourselves to the previous approaches and discuss the problems left open.     

Closed-form analysis of end-to-end network delay with Markov-modulated Poisson and fluid traffic

This paper develops a method for using traffic sources modelled as a Markov-modulated Poisson process (MMPP) and Markov-modulated fluid process (MMFP) in the framework of the bounded-variance network calculus, a novel stochastic network calculus framework for the approximated analysis of end-to-end network delay. The bounded-variance network calculus is an extension to multi-hop end-to-end paths of the Choe’s and Shroff’s Central-Limit-Theorem-based analysis of isolated network nodes. The input of the analysis is the statistical traffic envelope of sources, which is not available for generic MMPP and MMFP sources. The paper provides two statistical traffic envelopes, named two-moment and linear envelope, for general MMPP and MMFP sources, which can be used as an input of Central-Limit-Theorem-based frameworks for the analysis of network delay and, in turn, make it possible to use the rich collection of MMPP and MMFP models of voice, audio, data and video sources available in the literature. In this way, it is possible to avoid the computational complexity of traditional Markov analysis of end-to-end delay with MMPP and MMFP sources. With the linear envelope we can use simple analytical closed-form solutions for many important schedulers.     

基于网络演算计算保证服务端到端延迟上界

归纳总结了网络演算,阐明了网络演算的两个基本工具——进入曲线和服务曲线,得出了服务曲线存在瓶颈效应、端到端延迟的理想与近似确定性上界、提供保证服务网络节点的服务曲线需求等结论,计算了服务曲线以速率等待时间及PGPS(packetizedgeneralizedprocessorsharing)形式表示的保证服务端到端延迟确定性上界.     

Analytical queue length distributions of GPS systems with long range dependent service capacity

Generalized Processor Sharing (GPS) is an idealized scheduling mechanism with given weights assigned to individual traffic flows for service differentiation. Based on the principle of GPS, a number of variants have been proposed and deployed in real-world communication systems where the service capacity of network channels is usually variable. This paper proposes an analytical performance model for GPS systems with the variable service capacity characterized by Long Range Dependent (LRD) processes. The model is able to accommodate heterogeneous fractional Brownian motion (fBm) and Poisson traffic in multi-service networks. We derive the expressions of the queue length distributions of the GPS system and individual traffic flows. The accuracy of the analytical model is validated through comparison between analytical and simulation results.     

基于矩母函数的端到端网络统计时延上界研究

为分析网络中自相似业务的时延性能,运用矩母函数和有效带宽等理论,重新表征网络演算中到达包络和有效服务曲线,提出基于矩母函数形式的时延上界,利用相关理论建立并推导适应于自相似业务的端到端统计时延上界模型。数值分析结果表明,该模型能提高统计复用,对分型布朗运动业务性能评价具有较好的适应性。     

Resource allocation and admission control for the provisioning of quality of service in networks of static priority schedulers

This paper, proposes an analytical method for the resource allocation and admission control of traffic flows with statistical Quality-of-Service (QoS) guarantees in a Static Priority service discipline, in the case of both isolated nodes and end-to-end paths comprising multiple schedulers. The statistical QoS targets for each service class are expressed in terms of a delay bound and delay violation probability. Moreover, we assume that traffic admits a linear variance envelope; therefore, the method accounts for Leaky-Bucket-regulated traffic, for general Markov-Modulated Poisson Process sources and Markov-Modulated Fluid Process sources and, in general, to the wide class of sources for which the variance of the cumulative generated traffic can be upper bounded by a linear function of time. Under these assumptions, the resource allocation problem is solved analytically by deriving the closed-form expression of the minimum capacity to be allocated in the network in order to guarantee concurrently the QoS of all traffic flows across all service priorities. Moreover, the closed-form analytical solution of the admission control problem is obtained by deriving the expression of the maximum number of flows that is possible to accept, in all priority levels, knowing the link capacity, with differentiated statistical QoS constraints on delay for each priority level. Furthermore, by exploiting the bounded-variance network calculus, a novel framework for the calculation of statistical end-to-end delay bounds, we iterate our formulas, derived for the isolated node, to multi-node paths and, in turn, we provide analytical closed forms for the performance evaluation of end-to-end delay.     

A novel path protection scheme for MPLS networks using multi-path routing

Multi-protocol label switching (MPLS) is an evolving network technology that is used to provide traffic engineering (TE) and high speed networking. Internet service providers, which support MPLS technology, are increasingly demanded to provide high quality of service (QoS) guarantees. One of the aspects of QoS is fault tolerance. It is defined as the property of a system to continue operating in the event of failure of some of its parts. Fault tolerance techniques are very useful to maintain the survivability of the network by recovering from failure within acceptable delay and minimum packet loss while efficiently utilizing network resources.In this paper, we propose a novel approach for fault tolerance in MPLS networks. Our approach uses a modified (k, n) threshold sharing scheme with multi-path routing. An IP packet entering MPLS network is partitioned into n MPLS packets, which are assigned to node/link disjoint LSPs across the MPLS network. Receiving MPLS packets from k out of n LSPs are sufficient to reconstruct the original IP packet. The approach introduces no packet loss and no recovery delay while requiring reasonable redundant bandwidth. In addition, it can easily handle single and multiple path failures.     

自相似环境中端到端延迟上界

论文对网络队列系统性能定量分析新型数学工具——网络微积分学进行了归纳和总结,利用网络微积分学证明了利用分形漏桶整形器对自相似业务进行整形不会增加网络端到端延迟上界,计算了通用处理器共享下以分形漏桶包络轨迹为到达曲线和以速度等待时间函数为服务曲线的端到端延迟确定性上界。     

Providing traffic smoothness and service guarantees within ATM networks through a rate-controlled service discipline

With the introduction of diverse rate requirements under a variety of statistical multiplexing schemes, traffic burstiness behavior of a source stream and its quality-of-service (QoS) performances within the ATM networks become difficult to model and analyze. In this paper, we address this issue and propose a rate-controlled service discipline that provides control of the traffic burstiness while maintaining QoS guarantees for traffic flows with various rate requirements. According to our analysis, traffic streams from different connections can be well regulated at the output of each network node based on their rate requirements. Traffic envelope and the associated burstiness behavior inside the network can thus be effectively characterized. In addition, by assuming a leaky-bucket constrained input source, we prove that the proposed scheme can provide end-to-end delay and jitter bounds for each connection passing through a multi-hop network. Further, due to the low traffic burstiness, only a small buffer space is required at the internal switches for guaranteeing QoS requirements.     

Numerical analysis of worst-case end-to-end delay bounds in FIFO tandem networks

This paper addresses the problem of computing end-to-end delay bounds for a traffic flow traversing a tandem of FIFO multiplexing network nodes using Network Calculus. Numerical solution methods are required, as closed-form delay bound expressions are unknown except for few specific cases. For the methodology called the Least Upper Delay Bound, the most accurate among those based on Network Calculus, exact and approximate solution algorithms are presented, and their accuracy and computation cost are discussed. The algorithms are inherently exponential, yet affordable for tandems of up to few tens of nodes, and amenable to online execution in cases of practical significance. This complexity is, however, required to compute accurate bounds. As the LUDB may actually be larger than the worst-case delay, we assess how close the former is to the latter by computing lower bounds on the worst-case delay and measuring the gap between the lower and upper bound.     

Tighter Lower Bounds for Nearest Neighbor Search and Related Problems in the Cell Probe Model

We prove new lower bounds for nearest neighbor search in the Hamming cube. Our lower bounds are for randomized, two-sided error, algorithms in Yao's cell probe model. Our bounds are in the form of a tradeoff among the number of cells, the size of a cell, and the search time. For example, suppose we are searching among n points in the d dimensional cube, we use poly(n,d) cells, each containing poly(d, log n) bits. We get a lower bound of Ω(d/log n) on the search time, a significant improvement over the recent bound of Ω(log d) of Borodin et al. This should be contrasted with the upper bound of O(log log d) for approximate search (and O(1) for a decision version of the problem; our lower bounds hold in that case). By previous results, the bounds for the cube imply similar bounds for nearest neighbor search in high dimensional Euclidean space, and for other geometric problems.     

自相似业务网络性能分析

最近10多年的大量研究结果表明,网络业务具有普遍的自相似特性.自相似特性对网络的性能分析和设计具有广泛的影响.自相似业务的性能分析问题是一个没有很好解决的问题.提出了自相似业务环境下的分形界到达过程,研究了基于分形界到达过程的自相似业务漏桶参数的优化方法,给出了时延约束条件下漏桶速率和桶深的计算公式.最后研究了网络演算在确保服务性能分析中的建模方法,推导出了基于网络演算的端到端时延界、队列长度界和有效带宽的计算公式.通过具体的应用实例,验证了分析结果的正确性和有效性.     

A Distributed Critical Section Protocol for General Topology

We present a new critical section protocol designed for distributed systems with general topologies, where the physical layer is implemented as point-to-point physical links in contrast to shared access physical media. The protocol operates correctly for any topology; however, its time performance is topology dependent. The distributed system can be modeled by a graph G(V, E), where V denotes the set of processors and E is the set of bidirectional communication links. We use n to denote |V|; D(G) is the diameter of G, T(G) is the spanning tree of G, and D(T) is the diameter of T(G). An important measure of the performance of the protocol is the amount of traffic caused by its operation. Let message-hop be the amount of traffic generated by a single message between two adjacent nodes. The proposed protocol generates network traffic of only 3*(n − 1) ∈ Θ(n) [message-hops] per critical section access for any topology which is less than other existing fully distributed protocols. A lower bound on traffic for a single critical section access for a fully distributed protocol is shown to be 2*(n − 1) [message-hops]. Some previously published algorithms generate Θ(n²) [message-hops] of network traffic for some topologies. Another important measure of the performance of the protocol is the cs-access time. It is the time required to access the critical section in the absence of other requests; and it depends on the topology. The high cs-access time performance is achieved by taking a novel approach of distributing the communication and parts of computation functions of the protocol and exploiting the physical topology. For a constant size message, the time to traverse an edge, including the message communication software processing in the source and destination nodes, is called message-hop-time and it is denoted by t_h. For a general graph G (with spanning tree T) the new protocol has the cs-access time performance Θ(max(D(T), max(deg (v_i)))) [t_h], where deg(v_i) is computed in T. For the graphs where G has D(G) ∈ Θ(log₂n) and max(deg(v_i)) in G is O(log₂n), the cs-access time performance is Θ(log₂n) [t_h]. For the class of graphs where G has D(G) ∈ Θ(n), the cs-access time performance is Θ(n) [t_h]. For the Star graphs the cs-access time performance is Θ(n) [t_h]. The worst case time performance occurs for linear and Star graphs. The proposed protocol has a better network traffic performance and (depending on the topology) a better or equal cs-access time performance than previously published fully distributed protocols. The protocol keeps the clock bounded in well-designed systems using a distributed predictive "clock squashing" mechanism.     

On the Expansion and Diameter of Bluetooth-Like Topologies

The routing capabilities of an interconnection network are strictly related to its bandwidth and latency characteristics, which are in turn quantifiable through the graph-theoretic concepts of expansion and diameter. This paper studies expansion and diameter of a family of subgraphs of the random geometric graph, which closely model the topology induced by the device discovery phase of Bluetooth-based ad hoc networks. The main feature modeled by any such graph, denoted as BT(r(n),c(n)), is the small number c(n) of links that each of the n devices (vertices) may establish with those located within its communication range r(n). First, tight bounds are proved on the expansion of BT(r(n),c(n)) for the whole set of functions r(n) and c(n) for which connectivity has been established in previous works. Then, by leveraging on the expansion result, nearly-tight upper and lower bounds on the diameter of BT(r(n),c(n)) are derived. In particular, we show asymptotically tight bounds on the diameter when the communication range is near the minimum needed for connectivity, the typical scenario considered in practical applications.     

无线多跳网QoS性能统计性边界的研究

为保证无线多跳网的服务质量（QoS）,需要求解其性能边界。基于统计型流量包络建立了无线多跳网的数据流传输模型,在此模型的基础上利用统计网络演算理论推导了无线多跳网单节点的时延统计性边界、端到端的时延统计性边界以及端到端数据积压统计性边界。仿真实验结果表明,不同数据流的测量值都在数值计算的边界范围之内,表明基于统计网络演算理论的无线多跳网QoS边界模型具有较好的性能。     

Filtering effects of queueing systems on end-to-end network performance

A network is a mesh connection of network elements (NEs), each of which can be characterized as a single server queueing system. Upon arrival to the single server queueing system, a customer may see another customer already in service, and yet others may be in the queue. The new arrival either joins the queue, or is lost if there is no room available. By studying the traffic parameters at the ingress and egress of a generic NE, it is possible to deduce the filtering effect of a single server queueing system. On the assumption of exponential on–off traffic flows, we have derived equations to recursively compute the output traffic parameters as a function of the input traffic parameters. Since the output from the ith NE is also the input to the (i+1)st NE, the recursive equations allow us to assess the end-to-end network performance. Simulation results are used to gauge the accuracy of the analytical approach.     

Absorbant of generalized de Bruijn digraphs

The generalized de Bruijn digraph GB(n,d) has good properties as an interconnection network topology. The resource location problem in an interconnection network is one of the facility location problems. Finding absorbants of a digraph corresponds to solving a kind of resource location problem. In this paper, we establish bounds on the absorbant number for GB(n,d), and we give some sufficient conditions for the absorbant number of GB(n,d) to achieve the bounds. When d divides n, the extremal digraphs achieving the upper bound are characterized by determining their absorbants.     

Delay efficient scheduling via redundant constraints in multihop networks

We consider the problem of delay-efficient scheduling in general multihop networks. While the class of max-weight type algorithms are known to be throughput optimal for this problem, they typically incur undesired delay performance. In this paper, we propose the Delay-Efficient SCheduling algorithm (DESC). DESC is built upon the idea of accelerating queues (AQ), which are virtual queues that quickly propagate the traffic arrival information along the routing paths. DESC is motivated by the use of redundant constraints to accelerate convergence in the classic optimization context. We show that DESC is throughput-optimal. The delay bound of DESC can be better than previous bounds of the max-weight type algorithms which did not use such traffic information. We also show that under DESC, the service rates allocated to the flows converge quickly to their target values and the average total “network service lag” is small. In particular, when there are O(1) flows and the rate vector is of Θ(1) distance away from the boundary of the capacity region, the average total “service lag” only grows linearly in the network size.     

基于延时测量的端到端路径性能检测

网络路径的端到端性能直接决定了为用户提供服务的质量,网络路径性能的测量是网络运营和SLA(ServiceLevelAgreement)验证的重要组成部分。文章在描述端到端路径性能检测的一般性问题的基础上,提出了延时差平稳系数和绝对平稳系数作为测量检测网络路径性能的几个评价指标,作为已有的测量标准化工作的补充和利用网络测量进行端到端性能管理的参考方法。