Admission Control Algorithm for Guaranteeing Real-Time Anycast Flow

［1］S. Deering,R. Hinden. Internet Protocol version 6(Ipv6)specification, RFC2460, Dec. 1998 ［2］R. Hinde, S. Derring. IP Version 6 Addressing Architecture,RFC 1884, Dec. 1995 ［3］S. Bhattacharjee, M. H. Ammar, E. W. Zegura, V. Shah,Z.Fei. Application-Laye     

一种有效的实时选播流连接建立算法

选播服务被定义为一组复制服务器所提供的相同或类似的服务。使用选播服务能大大简化某些应用,例如查找合适的服务器来获得QoS服务、实现网络负载平衡和客错性服务等。为选播流建立连接提出了一种有效的分布式算法。对于有时延约束和最小带宽要求的一个选播流,我们的算法能有效地并行查找多个目标以建立连接、并确保满足选播请求的最好路径得到选择。     

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 core stateless bandwidth broker architecture for scalable support of guaranteed services

We present a novel bandwidth broker architecture for scalable support of guaranteed services that decouples the QoS control plane from the packet forwarding plane. More specifically, under this architecture, core routers do not maintain any QoS reservation states, whether per-flow or aggregate. Instead, the QoS reservation states are stored at and managed by a bandwidth broker. There are several advantages of such a bandwidth broker architecture. Among others, it avoids the problem of inconsistent QoS states faced by the conventional hop-by-hop, distributed admission control approach. Furthermore, it allows us to design efficient admission control algorithms without incurring any overhead at core routers. The proposed bandwidth broker architecture is designed based on a core stateless virtual time reference system developed recently. This virtual time reference system provides a unifying framework to characterize, in terms of their abilities to support delay guarantees, both the per-hop behaviors of core routers and the end-to-end properties of their concatenation. We focus on the design of efficient admission control algorithms under the proposed bandwidth broker architecture. We consider both per-flow end-to-end guaranteed delay services and class-based guaranteed delay services with flow aggregation. Using our bandwidth broker architecture, we demonstrate how admission control can be done on a per domain basis instead of on a "hop-by-hop" basis. Such an approach may significantly reduce the complexity of the admission control algorithms. In designing class-based admission control algorithms, we investigate the problem of dynamic flow aggregation in providing guaranteed delay services and devise a new apparatus to effectively circumvent this problem. We conduct detailed analyses to provide theoretical underpinning for our schemes as well as to establish their correctness. Simulations are also performed to demonstrate the efficacy of our schemes.     

Distributed admission control for anycast flows

Anycasting has recently become an important research topic, especially for replicated servers. With anycasting, applications can request the "nearest" server for provision of desired (multimedia) service. In this paper, we study efficient distributed admission control (DAC) for anycast flows. We focus on algorithms that perform destination selection and efficient path establishment. Taking advantage of anycasting, our distributed algorithms differ from each other in their dependence on system status information. Performance data obtained through mathematical analysis and simulations show that, in terms of admission probabilities, DAC systems that are based on local status information have performance levels close to those that utilize global and dynamic status information. This renders our DAC algorithms useful not only for the network layer, but also for the application layer admission control for anycast flows.     

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

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

基于遗传算法的QoS选播流路由优化算法

选播是一种网络通信服务,在视频流点播等领域发挥重要作用。该文提出QoS选播流路由优化的问题模型,给出选播流路由端到端时延、服务器负载、网络流量等优化目标和QoS约束的遗传算法表达式,说明了算法求解的关键步骤和实现过程。实验结果表明,该算法在满足QoS约束的前提下可以实现选播路由的多目标组合优化。     

Dynamic load distribution with hop-by-hop forwarding based on max-min one-way delay

Load balancing can effectively improve network performance and scalability,but it may cause packet disorder,so worsening the performance.Additionally,without MPLS to establish the desired end-to-end paths,hop-by-hop routing load balancing is more difficult to achieve than the source routing;however,it can significantly improve network performance.In this paper,we propose a load balancing scheme with hop-by-hop routing,by using the burstiness features of flows to make sure that the packets of the same flow arrive at the receiving end in order.Simulation results show that our algorithm can adapt to the dynamic changes of the end-to-end delay and the routing vector,and also can achieve fine-gained load balancing.     

Probe-based admission control for a differentiated-services internet

End-point admission control solutions have been proposed to meet quality requirements of audio-visual applications with little support from routers. These proposals decentralize the admission decision by requiring each host or access gateway to probe the network before sending data. In this paper we describe a probe-based admission control scheme that offers a reliable upper bound on packet loss, as well as small end-to-end delay and delay jitter. The admission control supports host mobility and multicast communications without adding any complexity to the network nodes. We present a mathematical analysis which relates system performance to design parameters and which can be used as a dimensioning aid for the system. Finally, we describe performance results from an experimental prototype as well as simulations that prove that the scheme provides a reliable and efficient solution for QoS provisioning for delay and loss sensitive applications.     

Rate control of multi class priority flows with end-to-end delay and rate constraints for QoS networks

To address end-to-end quality of service (QoS) requirements, we derive a novel distributed combined rate and end-to-end delay control in a network serving multi-class flows with priority packet scheduling. We show that the control is globally asymptotically stable without information time lags. The stable flows attain the end-to-end delay requirements and have no packet loss. We also show that by enhancing the network with bandwidth reservation and admission control, minimum rate is also guaranteed. The stability with very long time lags of a discrete time version control with non-greedy flows and random packet arrivals is studied numerically by an NS2 packet-based simulation of the Australian Academic and Research Network.     

一种带时延约束的选播路由算法

选播是一种新型的网络服务，它使用户通过一个选播地址就能访问到该地址所表示的一组服务器中对用户来说“最近”的一个。在实时性要求较高的业务传输过程中，保证信息传榆时延尽可能小是非常重要的。本文研究时延受限的选播路由问题，提出一种时延受限的选播路由（DCAR）算法，生成一棵以时延为度量且代价最小的选播生成树。仿真实验结果表明了该算法的正确性和高效性。 [     

无线自组网络QoS流的准入控制和流量控制

作者曾提出一个QoS路由和准入控制机制－QDSR,并且在小规模实时视频传输实验床上实现了这些方案。虽然QDSR的准入控制只保证每个节点有足够的可用带宽给准入的所有流使用,但并不保证每个流在较小的时间尺度上得到请求的带宽。为此,作者对QDSR的准入控制机制进行了改进并增加了流量控制机制,以满足实时应用的QoS需求。在NS2仿真环境中实现了QDSR以及对QDSR的改进。仿真结果表明,改进机制改善了QDSR的视频流的传输质量,较好地提高了视频流的吞吐率和投递率,减小了数据包的端到端延迟,并且能很好地满足包括视频传输在内的多种业务的传输需要。     

Tight end-to-end per-flow delay bounds in FIFO multiplexing sink-tree networks

Aggregate scheduling has been proposed as a solution for achieving scalability in large-size networks. However, in order to enable the provisioning of real-time services, such as video delivery or voice conversations, in aggregate scheduling networks, end-to-end delay bounds for single flows are required. In this paper, we derive per-flow end-to-end delay bounds in aggregate scheduling networks in which per-egress (or sink-tree) aggregation is in place, and flows traffic is aggregated according to a FIFO policy. The derivation process is based on Network Calculus, which is suitably extended to this purpose. We show that the bound is tight by deriving the scenario in which it is attained. A tight delay bound can be employed for a variety of purposes: for example, devising optimal aggregation criteria and rate provisioning policies based on pre-specified flow delay bounds.     

吸收协议-一个选播路由协议

选播是一种很有用的通信模式．由于在复制服务器、移动IP等多个应用领域的需求．使越来越多的人关注怎样更好的实现选播．提出了一个选播路由协议一吸收协议．协议在提供最小端到端延迟路由前提下支持多路路由．以平衡网络流量．改善网络链路利用率．协议通过从选播成员开始的吸收过程．使网络中每个节点都有一条或者多条到选播地址的路由指向到该节点端到端延迟最小的选播成员．吸收协议原理简单，开销小．易于实现．不依赖其他路由协议．修改、升级不会影响其他路由协议．     

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.     

WSN中单数据流端到端延迟上界研究

在WSN中采用独立分析（SFA）法求得的单数据流端到端延迟上界有时比整体分析（TFA）法求得的总数据流端到端延迟上界要大, 这不符合物理意义。针对这一问题, 分析了现有TFA法与SFA法在数据流服务分配机制上的差别, 并指出这两种方法求得的延迟上界不具有可比性。随后在修正流经节点数据流输出上界的基础上, 推导出与TFA法数据流服务分配机制相匹配的单数据流端到端延迟上界表达式。公式推导与数值分析结果均表明, 本方法求得的单数据流端到端延迟上界能够被TFA法总数据流端到端延迟上界所包络, 符合物理意义且更精确。     

延时受限的选播QoS路由算法的设计与仿真

选播是一种新型的网络服务,它使用户通过一个选播地址就能访问到该地址所表示的一组服务器中对用户来说“最近”的一个。在实时性要求较高的业务传输过程中,保证信息传输延时尽可能小是非常重要的。该文研究延时受限的选播路由问题,提出了一种改进的遗传算法以求解该问题。仿真实验结果表明,该算法是有效和切实可行的。     

Reduction-based schedulability analysis of distributed systems with cycles in the task graph

A significant problem with no simple solutions in current real-time literature is analyzing the end-to-end schedulability of tasks in distributed systems with cycles in the task graph. Prior approaches including network calculus and holistic schedulability analysis work best for acyclic task flows. They involve iterative solutions or offer no solutions at all when flows are non-acyclic. This paper demonstrates the construction of the first generalized closed-form expression for schedulability analysis in distributed task systems with non-acyclic flows. The approach is a significant extension to our previous work on schedulability in Directed Acyclic Graphs. Our main result is a bound on end-to-end delay for a task in a distributed system with non-acyclic task flows. The delay bound allows one of several schedulability tests to be performed. Using the end-to-end delay bound, we extend the delay composition algebra developed for acyclic distributed systems in prior work, to handle loops in the task graph as well. Evaluation shows that the schedulability tests thus constructed are less pessimistic than prior approaches for large distributed systems.     

一种新的连通区域标记算法*

为了进一步提高标记效率,提出了一种连通区域标记的新算法RCL（run and contour based labeling algorithm）。该算法采用轮廓跟踪技术、行程技术和位操作等一系列加速技术,彻底消除了传统算法标记过程中对邻居像素信息的依赖。实验表明RCL算法的执行效率与传统的轮廓跟踪法相比提高了约80%,而且表现出稳定的性能和非常好的鲁棒性。