End‐to‐end response time with fixed priority scheduling: trajectory approach versus holistic approach

In this paper, we are interested in providing deterministic end‐to‐end guarantees to real‐time flows in a distributed system. We focus on the end‐to‐end response time, quality of service (QoS) parameter of the utmost importance for such flows. We assume that each node uses a Fixed Priority scheduling. We determine a bound on the end‐to‐end response time of any real‐time flow with a worst case analysis using the trajectory approach. We establish new results that we compare with those provided by the classical holistic approach for flows visiting the same sequence of nodes. These results show that the trajectory approach is less pessimistic than the holistic one. Moreover, the bound provided by our worst‐case analysis is reached in various configurations, as shown in the examples presented. Copyright © 2004 John Wiley & Sons, Ltd.     

Distributed Priority Scheduling and Medium Access in Ad Hoc Networks

Providing Quality-of-Service in random access multi-hop wireless networks requires support from both medium access and packet scheduling algorithms. However, due to the distributed nature of ad hoc networks, nodes may not be able to determine the next packet that would be transmitted in a (hypothetical) centralized and ideal dynamic priority scheduler. In this paper, we develop two mechanisms for QoS communication in multi-hop wireless networks. First, we devise distributed priority scheduling, a technique that piggybacks the priority tag of a node's head-of-line packet onto handshake and data packets; e.g., RTS/DATA packets in IEEE 802.11. By monitoring transmitted packets, each node maintains a scheduling table which is used to assess the node's priority level relative to other nodes. We then incorporate this scheduling table into existing IEEE 802.11 priority backoff schemes to approximate the idealized schedule. Second, we observe that congestion, link errors, and the random nature of medium access prohibit an exact realization of the ideal schedule. Consequently, we devise a scheduling scheme termed multi-hop coordination so that downstream nodes can increase a packet's relative priority to make up for excessive delays incurred upstream. We next develop a simple analytical model to quantitatively explore these two mechanisms. In the former case, we study the impact of the probability of overhearing another packet's priority index on the scheme's ability to achieve the ideal schedule. In the latter case, we explore the role of multi-hop coordination in increasing the probability that a packet satisfies its end-to-end QoS target. Finally, we perform a set of ns-2 simulations to study the scheme's performance under more realistic conditions.     

Expedited forwarding end‐to‐end delay and jitter in DiffServ

The scheduling disciplines and active buffer management represent the main components employed in the differentiated services (DiffServ) data plane, which provide qualitative per‐hop behaviors corresponding to the QoS required by supported traffic classes. In the first part of this paper, we compute the per‐hop delay bound that should be guaranteed by the different multiservice scheduling disciplines, so that the end‐to‐end (e2e) delay required by expedited forwarding (EF) traffic can be guaranteed. Consequently, we derive the e2e delay bound of EF traffic served by priority queuing–weighted fair queuing (PQ–WFQ) at every hop along its routing path. Although real‐time flows are principally offered EF service class, some simulations on DiffServ‐enabled network show that these flows suffer from delay jitter and they are negatively impacted by lower priority traffic. In the second part of this paper, we clarify the passive impact of delay jitter on EF traffic, where EF flows are represented by renewal periodic ON–OFF flows, and the background (BG) flows are characterized by the Poisson process. We analyze through different scenarios the jitter effects of these BG flows on EF flow patterns when they are served by a single class scheduling discipline, such as first‐input first‐output, and a multiclass or multiservice scheduling discipline, such as static priority service discipline. As a result, we have found out that the EF per‐hop behaviors (PHBs) configuration according to RFCs 2598 and 3246 (IETF RFC 2598, June 1999; RFC 3246, IETF, March 2002) cannot stand alone in guaranteeing the delay jitter required by EF flows. Therefore, playout buffers must be added to DiffServ‐enabled networks for handling delay jitter problem that suffers from EF flows. Copyright © 2008 John Wiley & Sons, Ltd.     

A distributed laxity-based priority scheduling scheme for time-sensitive traffic in mobile ad hoc networks

Characteristics of Mobile Ad hoc Networks such as shared broadcast channel, bandwidth and battery power limitations, highly dynamic topology, and location dependent errors, make provisioning of quality of service (QoS) in such networks very difficult. The Medium Access Control (MAC) layer plays a very important role as far as QoS is concerned. The MAC layer is responsible for selecting the next packet to be transmitted and the timing of its transmission. We have proposed a new MAC layer protocol that includes a laxity-based priority scheduling scheme and an associated back-off scheme, for supporting time-sensitive traffic. In the proposed scheduling scheme, we select the next packet to be transmitted, based on its priority value which takes into consideration the uniform laxity budget of the packet, the current packet delivery ratio of the flow to which the packet belongs, and the packet delivery ratio desired by the user. The back-off mechanism devised by us grants a node access to the channel, based on the rank of its highest priority packet in comparison to other such packets queued at nodes in the neighborhood of the current node. We have studied the performance of our protocol that combines a packet scheduling scheme and a channel access scheme through simulation experiments, and the simulation results show that our protocol exhibits a significant improvement in packet delivery ratio under bounded end-to-end delay requirements, compared to the existing 802.11 DCF and the Distributed Priority Scheduling scheme proposed recently in [ACM Wireless Networks Journal 8 (5) (2002) 455–466; Proceedings of ACM MOBICOM '01, July 2001, pp. 200–209].     

Performance Evaluation of Resource Reservation Policies for Rate-Controlled Earliest-Deadline-First Scheduling in Multi-Service Packet Networks

The paper addresses the issue of reserving resources at packet switches along the path of flows requiring a deterministic bound on end-to-end delay. The switches are assumed to schedule outgoing packets using the Rate-Controlled Earliest-Deadline-First (RC-EDF) scheduling discipline. EDF is known to be an optimal scheduling discipline for deterministic delay services in the single scheduler case. We propose a number of static and dynamic reservation policies for mapping the end-to-end delay requirement of a flow into local delay deadlines to be reserved at each scheduler. These policies are based on non-even resource reservation where the resources reserved depend on the capacities and loading at each node in the network. We define and prove the optimality of a certain non-even policy for the case of a single path network with homogenous static traffic. We present extensive simulation results for different scenarios which show that dynamic non-even resource reservation provides superior performance when compared to simple policies such as even dividing of end-to-end delay among the schedulers.     

A Packet Scheduling Approach to QoS Support in Multihop Wireless Networks

Providing packet-level quality of service (QoS) is critical to support both rate-sensitive and delay-sensitive applications in bandwidth-constrained, shared-channel, multihop wireless networks. Packet scheduling has been a very popular paradigm to ensure minimum throughput and bounded delay access for packet flows. This work describes a packet scheduling approach to QoS provisioning in multihop wireless networks. Besides minimum throughput and delay bounds for each flow, our scheduling disciplines seek to achieve fair and maximum allocation of the shared wireless channel bandwidth. However, these two criteria can potentially be in conflict in a generic-topology multihop wireless network where a single logical channel is shared among multiple contending flows and spatial reuse of the channel bandwidth is possible. In this paper, we propose a new scheduling model that addresses this conflict. The main results of this paper are the following: (a) a two-tier service model that provides a minimum fair allocation of the channel bandwidth for each packet flow and additionally maximizes spatial reuse of bandwidth, (b) an ideal centralized packet scheduling algorithm that realizes the above service model, and (c) a practical distributed backoff-based channel contention mechanism that approximates the ideal service within the framework of the CSMA/CA protocol.     

Group priority scheduling

We present an end-to-end delay guarantee theorem for a class of guaranteed deadline (GD) servers. The theorem can be instantiated to obtain end-to-end delay bounds for a variety of source control mechanisms and GD servers. We then propose the idea of group priority, and specialize the theorem to a subclass of GD servers that use group priority in packet scheduling. With the use of group priority, the work of packet schedulers can be substantially reduced. We work out a detailed example, for the class of burst scheduling networks, to illustrate how group sizes can be designed such that the worst case end-to-end delay of application data units in a real-time flow is unaffected by the use of group priority. Group priority also can be used in packet schedulers that provide integrated services (best effort as well as real-time services) to achieve statistical performance gains, which we illustrate with empirical results from simulation experiments     

A policy based framework for quality of service management in software defined networks

Growth in multimedia traffic over the Internet increases congestion in the network architecture. Software-Defined Networking (SDN) is a novel paradigm that solves the congestion problem and allows the network to be dynamic, intelligent, and it centrally controls the network devices. SDN has many advantages in comparison to traditional networks, such as separation of forwarding and control plane from devices, global centralized control, management of network traffic. We design a policy-based framework to enhance the Quality of Service (QoS) of multimedia traffic flows in a potential SDN environment. We phrase a max-flow-min-cost routing problem to determine the routing paths and presented a heuristic method to route the traffic flows in the network in polynomial time. The framework monitors the QoS parameters of traffic flows and identifies policy violations due to link congestion in the network. The introduced approach dynamically implements policy rules to SDN switches upon detection of policy violations and reroutes the traffic flows. The results illustrate that the framework achieves a reduction in end-to-end delay, average jitter, and QoS violated flows by 24%, 37%, and 25%, respectively, as compared to the Delay Minimization method. Furthermore, the proposed approach has achieved better results when compared to SDN without policy-based framework and reduced end-to-end delay, average jitter, and QoS violated flows by 51%, 62%, and 28%, respectively.

     

UMTS核心网中基于区分服务的QoS控制模型

3G新业务的发展，要求UMTS提供端到端QoS控制。文章构建了在UMTS核心网中为不同业务类提供QoS保证的区分服务模型，提出了从UMTS业务类到DiffServ域服务等级的映射方案，设计了一种新的队列调度算法，采用优先级和分离机制，在流量调整器配合下可满足不同业务类的QoS要求。最后，通过模拟实验证明了模型的有效性。     

基于剩余路径跳数的动态优先调度实现区分服务EF PHB

Internet区分服务（DiiffServ）中EF PHB(Expedited Forwarding Per Hop Behavior)提供严格的端到端延迟保证，其实现机制和性能是当前研究的热点。随着可扩展性成为核心网络考虑的关键因素，一般用简单的FIFO高度实现EF PHB。FIFO实现问题在于最坏的端到端延迟与流经历的最大跳数成正比，结果降低了网络最坏延迟性能，并影响了整个网络的总体利用率。文章在分析并比较FIFO实现以及考虑流跳数因素的绝对跳数优先（HBAP）实现、相对跳数优先（HBRP）实现的延迟性能基础上，提出了用基于剩余路径跳数的动态优先（DHBP）调度实现EF PHB。理论分析和实验结果表明，基于剩余路径跳数的动态优先调度算法可以平衡不同跳数流的端到端延迟性能，从而减小网络最坏的端到端延迟，并有效地提高了网络 选用率，最坏延迟性能明显优于FIFO和绝对跳数优先调度，与性能最优的相对跳数优先调度相似，并将计算复杂度降为0(1)。