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.     

Determining end-to-end delay bounds in heterogeneous networks

We define a class of Guaranteed Rate (GR) scheduling algorithms. The GR class includes Virtual Clock, Packet-by-Packet Generalized Processor Sharing and Self-Clocked Fair Queuing. For networks that employ scheduling algorithms belonging to GR, we present a method for determining an upper bound on end-to-end delay. The method facilitates determination of end-to-end delay bounds for a variety of sources. We illustrate the method by determining end-to-end delay bounds for sources conforming to Leaky Bucket and exponentially bounded burstiness.     

Non-asymptotic end-to-end performance bounds for networks with long range dependent fBm cross traffic

Fractional Brownian motion (fBm) emerged as a useful model for self-similar and long-range dependent aggregate Internet traffic. Asymptotic, respectively, approximate performance measures are known for single queueing systems with fBm through traffic. In this paper end-to-end performance bounds for a through flow in a network of tandem queues under open-loop fBm cross traffic are derived. To this end, a rigorous sample path envelope for fBm is proven that complements previous approximate results. The sample path envelope and the concept of leftover service curves are employed to model the remaining service after scheduling fBm cross traffic at a queuing system. Using composition results for tandem systems from the stochastic network calculus end-to-end statistical performance bounds for individual flows in networks under fBm cross traffic are derived. The discovery is that these bounds grow in O(n(logn)^1/(2-2H)) for n systems in series where H is the Hurst parameter of the cross traffic. Explicit results on the impact of the variability and the burstiness of through and cross traffic on network performance are shown. Our analysis has direct implications on fundamental questions in network planning and service management.     

LTE-A飞蜂窝网络自相似业务流的端到端时延边界分析

LTE-A是一种4G移动通信标准,可满足移动数据业务对传输带宽的要求。为解决移动通信网络中室内信号质量较差的问题,LTE-A标准采用飞蜂窝技术作为室内无线接入解决方案。针对LTE-A飞蜂窝网络的时延边界问题,运用随机网络演算方法分析业务流的自相似性质和MIMO信道的时变特性,构建了LTE-A飞蜂窝网络中自相似业务流的随机到达与随机服务模型。围绕所构建的到达与服务模型,运用有效带宽理论和chernoff界方法,给出了自相似业务流的端到端时延边界。NS3仿真验证表明,在信道带宽和业务流优先级等指标不同的情形下,所给出的理论端到端时延边界与仿真时延的偏差在2ms以内,较为准确有效,可为确保LTE-A飞蜂窝网络的服务质量提供依据。     

An analytical QoS service model for delay-based differentiation

The increased need for Quality of Service (QoS) in today’s IP networks has concentrated a lot of research and implementation efforts. Carefully designed and managed priority services are essential for quality-demanding traffic, especially in large-scale IP-based environments where aggregation of flows is extensive and a variety of traffic types co-exist. Although individual mechanisms have been widely investigated, not much related work exists on integrated approaches to QoS provisioning that are also feasible to implement. This work presents a thorough approach to the design, dimensioning and provisioning of a high-priority service for high-quality-demanding traffic over an IP network. Our approach employs efficient scheduling and a dynamic admission control scheme while demonstrating an outstanding performance in terms of the quality offered to QoS-demanding traffic. A novel feature is also introduced: while other existing schemes only focus on provisioning of service rate guarantees, ours achieves in addition differentiation of the end-to-end delay perceived by IP flows.     

End-to-end QoS guarantees for a network based on Latency-Rate Max–Min service curve

Recently, a number of studies have been made based on the concept of Route Interference to provide deterministic end-to-end quality of service (QoS) guarantees. Nonetheless, these studies tend to confine to a simple scheduling scheme and study the traffic in a single-class environment or the highest priority traffic in a multi-class environment. This is rather restrictive. In this paper, we propose a new general service scheme to service flows. This scheme is represented by a Latency-Rate Max–Min service curve (LRMMSC). Subsequently, for a network of LRMMSC, we prove the existence of tight bounds on end-to-end queuing delay and buffer size needed for loss-free packet delivery, provided that all flows obey a given source rate condition in the form of their route interference. Our approach has two salient features: (1) the general nature of the concept of service curve enables the service scheme to be implemented by many well-known scheduling disciplines, (2) the general network model adopted with no constraints on the manner of packet queuing makes the results applicable to many complex networks. In addition, we have also derived a concise expression of end-to-end delay bound that depends only on the service offered to the buffers containing the considered flow. This is very useful in practice as the expression is simple and requires minimum amount of information input. Simulation experiments are conducted to verify the LRMMSC model. The analytical and simulation results exhibit close resemblance. In addition, the advantage of LRMMSC scheme in providing maximum end-to-end delay is also demonstrated.     

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

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

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.     

Delay Control and Parallel Admission Algorithms for Real-Time Anycast Flow

An anycast flow is a flow that can be connected to any one of the members in a group of designated (replicated) servers (called anycast group). In this paper, we derive a set of formulas for calculating the end-to-end delay bound for the anycast flows and present novel admission control algorithms for anycast flows with real-time constraints. Given such an anycast group, our algorithms can effectively select the paths for anycast flows' admission and connection based on the least end-to-end delay bounds evaluated. We also present a parallel admission control algorithm that can effectively calculate the available paths with a short delay bound for different destinations in the anycast group so that a best path with the shortest delay bound can be chosen.     

Throughput bounds for closed queueing networks

Analytical lower and upper bounds for the throughput of closed queueing networks with single and delay (infinite) servers are studied in this paper. The numerical evaluation of these bounds requires a small number of significant operations which is independent of the population N. This is in contrast to the exact computation of the throughput which requires at least O(N) operations as N tends to infinity. The bounds are given by simple closed-form analytical expressions and may be more suitable for various performance studies than the algorithmical form of the exact solution.In this paper, the previously known balanced-job bounds are generalized to networks containing delay servers (terminals) and a hierarchy of bounds is obtained for single and multiple class networks. For the single class network, further new bounds are derived: lower and upper bounds that require the evaluation of one square root and an upper bound that requires a constant number of exponentiations. This upper bound does not employ the balancing of server loadings and is especially useful for asymptotic analysis in the case of a large number of customers N.     

Analyzing Weighted Round Robin policies with a stochastic comparison approach

We study queuing delays for Weighted Round Robin (WRR) scheduling policies. The delay characteristics of these policies can be estimated through worst-case bounds as other fair queuing scheduling policies. However, these deterministic bounds are in general not accurate and they require that the input process has been shaped. Under Markovian arrival hypothesis, the delay of WRR   policies can be evaluated through Markovian numerical analysis. Nevertheless, this analysis is limited to small parameter sizes because of the state space explosion problem. We propose to apply the stochastic comparison approach. We build a bounding model based on the aggregation of sessions, and we show that under the same arrivals, the packet delays in the bounding model are larger in the _?st${?}_{\mathrm{st}}$ stochastic order sense than the packet delays in the original model. Due to this aggregation, the state space size is drastically reduced and we are able to provide stochastic delay bounds for WRR policies. We discuss the accuracy of the proposed bounds through numerical examples.     

A calculus for stochastic QoS analysis

The issue of Quality of Service (QoS) performance analysis in packet-switched networks has drawn a lot of attention in the networking community. There is a lot of work including an elegant theory under the name of network calculus, which focuses on analysis of deterministic worst case QoS performance bounds. In the meantime, researchers have studied stochastic QoS performance for specific schedulers. However, most previous works on deterministic QoS analysis or stochastic QoS analysis have only considered a server that provides deterministic service, i.e. deterministically bounded rate service. Few have considered the behavior of a stochastic server that provides input flows with variable rate service, for example wireless links. In this paper, we propose a stochastic network calculus to analyze the end-to-end stochastic QoS performance of a system with stochastically bounded input traffic over a series of deterministic and stochastic servers. We also prove that a server serving an aggregate of flows can be regarded as a stochastic server for individual flows within the aggregate. Based on this, the proposed framework is further applied to analyze per-flow stochastic QoS performance under aggregate scheduling.     

基于流量隔离的公平聚集器

为实现对微流的最差延迟最早聚集,并对聚集完成的宏流进行过滤与排序,实现宏流公平调度,提出基于流量隔离的公平聚集器(FAFI)。FAFI解决了在基于流量聚集调度模式中,同一宏流内部各竞争微流之间的突发流量对数据包传输延迟产生影响的问题。通过严格的数学推理与演算,证明FAFI的有效性。仿真实验验证了对FAFI模型的定量分析结果和FAFI模型的性能。     

Fundamental trade-offs in aggregate packet scheduling

In this paper, we investigate the fundamental trade-offs in aggregate packet scheduling for support of guaranteed delay service. In our study, we consider two classes of aggregate packet scheduling algorithms: the static earliest time first (SETF) and dynamic earliest time first (DETF). Through these two classes of aggregate packet scheduling (and together with the simple FIFO packet scheduling algorithm), we show that, with additional timestamp information encoded in the packet header for scheduling purposes, we can significantly increase the maximum allowable network utilization level, while, at the same time, reducing the worst-case edge-to-edge delay bound. Furthermore, we demonstrate how the number of the bits used to encode the timestamp information affects the trade-off between the maximum allowable network utilization level and the worst-case edge-to-edge delay bound. In addition, the more complex DETF algorithms have far superior performance than the simpler SETF algorithms. These results illustrate the fundamental trade-offs in aggregate packet scheduling algorithms and shed light on their provisioning power in support of guaranteed delay service.     

“Pay bursts only once” does not hold for non-FIFO guaranteed rate nodes

We consider end-to-end delay bounds in a network of guaranteed rate (GR) nodes. We demonstrate that, contrary to what is generally believed, the existing end-to-end delay bounds apply only to GR nodes that are FIFO per flow. We show this by exhibiting a counter example. Then, we show that the proof of the existing bounds has a subtle, but important, dependency on the FIFO assumption, which was never noticed before. Finally, we give a tight delay bound that is valid in the non-FIFO case; it is noticeably higher that the existing one. In particular, the phenomenon known as “pay bursts only once” does not apply to non-FIFO nodes. These findings are important in the context of differentiated services. Indeed the existing bounds have been applied to cases where a flow (in the sense of the GR definition) is an aggregate of end-user microflows, and it is not generally true that a router is FIFO per aggregate; thus, the GR node model of a differentiated services router cannot always be assumed to be FIFO per flow.     

Routing Internet traffic in heterogeneous mesh networks: Analysis and algorithms

In practical wireless mesh networks (WMNs), gateways are subject to hard capacity limits on the aggregate number of flows (in terms of bit rate) that they can support. Thus, if traffic is routed in the mesh network without considering those constraints, as well as the traffic distribution, some gateways or intermediate mesh routers may rapidly get overloaded, and the network resources can be unevenly utilized. To address this problem, in this paper we firstly develop a multi-class queuing network model to analyze feasible throughput allocations, as well as average end-to-end delay, in heterogeneous WMNs. Guided by our analysis, we design a Capacity-Aware Route Selection algorithm (CARS), which allocates network paths to downstream and upstream Internet flows so as to ensure a more balanced utilization of wireless network resources and gateways’ fixed connections. Through simulations in a number of different network scenarios we show that the CARS scheme significantly outperforms conventional shortest path routing, as well as an alternative routing method that distributes the traffic load on the gateway nodes to minimize its variance.     

Dynamic end-to-end capacity in IEEE 802.16 wireless mesh networks

The IEEE 802.16 standard defines mesh mode as one of its two operational modes in medium access control (MAC). In the mesh mode, peer-to-peer communication between subscriber stations (SSs) is allowed, and transmissions can be routed via other SSs across multiple hops. In such an IEEE 802.16 mesh network, accurate and reliable determination of dynamic link capacity and end-to-end capacity of a given multi-hop route is crucial for robust network control and management. The dynamic capacities are difficult to determine in a distributed system due to decentralized packet scheduling and interference between communicating nodes caused by the broadcast nature of radio propagation. In this paper, we first propose a method for computing the dynamic link capacity between two mesh nodes, and extend that to determine the dynamic end-to-end capacity bounds of a multi-hop route based on the concept of Bottleneck Zone. The physical deployments of networks are also considered in the capacity estimation. We demonstrate the effectiveness and accuracy of our methods for computing dynamic link capacity and end-to-end capacity bounds through extensive simulations.     

Conformance analysis in networks with service level agreements

To achieve some level of Quality of Service (QoS) assurance, a network usually has Service Level Agreements (SLAs) with its users and neighboring domains, which describe the QoS level that the service provider is committed to provide, and the specification of traffic that users or neighboring domains are allowed to send. An interesting and important question arises as to whether a flow is still conformant to its original traffic specification after crossing the network since it may interact with other flows within the network. In this paper, we study analytically the extent to which a flow and an aggregate of flows become non-conformant through an analysis of the stochastic burstiness increase of flows after crossing a per-flow scheduling network and an aggregate scheduling network . The stochastic behavior of a server in aggregate scheduling networks is also studied to determine the conformance deterioration of individual flows, which provides the theoretical conformance deterioration bound and provides useful results for conformance analysis in an aggregate scheduling network with general topology. Our theoretical results are verified by extensive simulations.