共查询到20条相似文献,搜索用时 15 毫秒
1.
Although weighted fair queueing (WFQ) has been regarded as an ideal scheduling algorithm in terms of its combined delay bound and proportional fairness properties, its asymptotic time complexity increases linearly with the number of sessions serviced by the scheduler, thus limiting its use in high-speed networks. An algorithm that combines the delay and fairness bounds of WFQ with O(1) timestamp computations had remained elusive so far. In this paper we present two novel scheduling algorithms that have O(1) complexity for timestamp computations and provide the same bounds on end-to-end delay and buffer requirements as those of WFQ. The first algorithm, frame-based fair queueing (FFQ), uses a framing mechanism to periodically recalibrate a global variable tracking the progress of work in the system, limiting any short-term unfairness to within a frame period. The second algorithm, starting potential based fair queueing (SPFQ), performs the recalibration at packet boundaries, resulting in improved fairness while still maintaining the O(1) timestamp computations. Both algorithms are based on the general framework of rate-proportional servers (RPSs) introduced by Stiliadis and Varma (see ibid., vol.6, no.2, p.164-74, 1998). The algorithms may be used in both general packet networks with variable packet sizes and in asynchronous transfer mode (ATM) networks 相似文献
2.
Generalized processor sharing (GPS) has been considered as an ideal scheduling discipline based on its end-to-end delay bounds and fairness properties. Until recently, emulation of GPS in a packet server has been regarded as the ideal means of designing a packet-level scheduling algorithm to obtain low delay bounds and bounded unfairness. Strict emulation of GPS, as required in the weighted fair queueing (WFQ) scheduler, however, incurs a time-complexity of O(N) where N is the number of sessions sharing the link. Efforts in the past to simplify the implementation of WFQ, such as self-clocked fair queueing (SCFQ), have resulted in degrading its isolation properties, thus affecting the delay bound. We present a methodology for the design of scheduling algorithms that provide the same end-to-end delay bound as that of WFQ and bounded unfairness without the complexity of GPS emulation. The resulting class of algorithms, called rate-proportional servers (RPSs), are based on isolating scheduler properties that give rise to ideal delay and fairness behavior. Network designers can use this methodology to construct efficient fair-queueing algorithms, balancing their fairness with implementation complexity 相似文献
3.
The problem of allocating network resources to application sessions backlogged at an individual switch has a great impact on the end-to-end delay and throughput guarantees offered by the network. There exists a class of algorithms based on weighted fair queueing (WFQ) for scheduling packets which are work-conserving and they guarantee fairness to the backlogged sessions. These algorithms also apply to ATM networks with a packet equal to a single cell or an ATM block (of fixed size). Bursts are groups of varying numbers of cells. We generalize WFQ to schedule bursts. Our motivation is to derive an adaptive algorithm which generalizes the (fixed size) packet level to a varying size packet level. The new algorithm enhances the performance of the switch service for many important applications. The proposed scheme maintains the work-conserving property, and also provides throughput and fairness guarantees. The worst-case delay bound is also given. We use simulation to study the performance characteristics of our algorithm. Our results demonstrate the efficiency of the new algorithm. 相似文献
4.
提出了一类具有最大速率控制的速率保障(Maximum Rate Control-Guaranteed Rate,MRC-GR)算法,可对流同时提供速率保障和最大速率控制.当网络各节点执行MRC-GR算法时,提供了确定网络端到端时延上限和下限的方法,针对服从令牌桶模型和同步单元模型的业务源给出了网络时延上限和下限.针对MRC-GR算法实例——具有最大速率控制的最差情形公平加权公平排队(worst-case fair weighted fair queueing with maximum rate control)调度算法进行仿真实验,仿真结果验证了理论分析. 相似文献
5.
We develop a general model, called latency-rate servers (ℒℛ servers), for the analysis of traffic scheduling algorithms in broadband packet networks. The behavior of an ℒℛ server is determined by two parameters-the latency and the allocated rate. Several well-known scheduling algorithms, such as weighted fair queueing, virtualclock, self-clocked fair queueing, weighted round robin, and deficit round robin, belong to the class of ℒℛ servers. We derive tight upper bounds on the end-to-end delay, internal burstiness, and buffer requirements of individual sessions in an arbitrary network of ℒℛ servers in terms of the latencies of the individual schedulers in the network, when the session traffic is shaped by a token bucket. The theory of ℒℛ servers enables computation of tight upper bounds on end-to-end delay and buffer requirements in a heterogeneous network, where individual servers may support different scheduling architectures and under different traffic models 相似文献
6.
McLaughlin K. Sezer S. Blume H. Yang X. Kupzog F. Noll T. 《Very Large Scale Integration (VLSI) Systems, IEEE Transactions on》2008,16(7):781-791
A novel implementation of a tag sorting circuit for a weighted fair queueing (WFQ) enabled Internet protocol (IP) packet scheduler is presented. The design consists of a search tree, matching circuitry, and a custom memory layout. It is implemented using 130-nm silicon technology and supports quality of service (QoS) on networks at line speeds of 40 Gb/s, enabling next generation IP services to be deployed. 相似文献
7.
Self‐Clocked Fair Queueing (SCFQ) algorithm has been considered as an attractive packet scheduling algorithm because of its implementation simplicity, but it has unbounded delay property in some input traffic conditions. In this paper, we propose a Rate Proportional SCFQ (RP‐SCFQ) algorithm which is a rate proportional version of SCFQ. If any fair queueing algorithm can be categorized into the rate proportional class and input is constrained by a leaky bucket, its delay is bounded and the same as that of Weighted Fair Queueing (WFQ) which is known as an optimal fair queueing algorithm. RP‐SCFQ calculates the timestamps of packets arriving during the transmission of a packet using the current value of system potential updated at every packet departing instant and uses a starting potential when it updates the system potential. By doing so, RP‐SCFQ can have the rate proportional property. RP‐SCFQ is appropriate for high‐speed packet‐switched networks since its implementation complexity is low while it guarantees the bounded delay even in the worst‐case input traffic conditions. 相似文献
8.
量子通信能够有效提高电力业务传输的可靠性与安全性,但由于量子密钥成码率低,难以满足重要电力业务的加密需求,因此,需要一种队列调度算法对量子通信中的待加密电力业务进行合理调度。提出了一种改进的加权公平队列(weighted fair queuing,WFQ)算法LD-WFQ,算法通过估计待加密数据分组的预计耗时,优先处理即将超时的待加密数据分组,在保持高优先级业务量子加密时延达标率的基础上,有效降低了低优先级业务的量子加密超时率。与WFQ算法进行仿真对比,结果证明了LD-WFQ算法的优越性。 相似文献
9.
Hyoung-Il Lee Seung-Woo Seo 《Networking, IEEE/ACM Transactions on》2006,14(1):121-132
We have previously proposed an efficient switch architecture called multiple input/output-queued (MIOQ) switch and showed that the MIOQ switch can match the performance of an output-queued switch statistically. In this paper, we prove theoretically that the MIOQ switch can match the output queueing exactly , not statistically, with no speedup of any component. More specifically, we show that the MIOQ switch with two parallel switches (which we call a parallel MIOQ (PMIOQ) switch in this paper) can provide exact emulation of an output-queued switch with a broad class of service scheduling algorithms including FIFO, weighted fair queueing (WFQ) and strict priority queueing regardless of incoming traffic pattern and switch size. To do that, we first propose the stable strategic alliance (SSA) algorithm that can produce a stable many-to-many assignment, and prove its finite, stable and deterministic properties. Next, we apply the SSA algorithm to the scheduling of a PMIOQ switch with two parallel switches, and show that the stability condition of the SSA algorithm guarantees for the PMIOQ switch to emulate an output-queued switch exactly. To avoid possible conflicts in a parallel switch, each input-output pair matched by the SSA algorithm must be mapped to one of two crossbar switches. For this mapping, we also propose a simple algorithm that requires at most 2N steps for all matched input-output pairs. In addition, to relieve the implementation burden of N input buffers being accessed simultaneously, we propose a buffering scheme called redundant buffering which requires two memory devices instead of N physically-separate memories. In conclusion, we demonstrate that the MIOQ switch requires two crossbar switches in parallel and two physical memories at each input and output to emulate an output-queued switch with no speedup of any component. 相似文献
10.
Fair scheduling with tunable latency: a round-robin approach 总被引:1,自引:0,他引:1
Weighted fair queueing (WFQ)-based packet scheduling schemes require processing at line speeds for tag computation and tag sorting. This requirement presents a bottleneck for their implementation at high transmission speeds. We propose an alternative and lower complexity approach to packet scheduling, based on modifications of the classical round-robin scheduler. Contrary to conventional belief, we show that appropriate modifications of the weighted round-robin (WRR) service discipline can, in fact, provide tight fairness properties and efficient delay guarantees to multiple sessions. Two such modifications are described: 1) list-based round robin, in which the server visits different sessions according to a precomputed list which is designed to obtain the desirable scheduling properties; 2) multiclass round robin, a version of hierarchical round robin with controls designed for good scheduling properties. The schemes considered are compared with well-known WFQ schemes and with deficit round robin (a credit-based WRR), on the basis of desirable properties such as bandwidth guarantees, fairness in excess bandwidth sharing, worst-case fairness, and efficiency of latency (delay guarantee) tuning. The scheduling schemes proposed and analyzed here operate with fixed packet sizes, and hence can be used in applications such as cell scheduling in ATM networks, time-slot scheduling on wireless links as in GPRS air interface, etc. A credit-based extension of the proposed schemes to handle variable packet sizes is also possible. 相似文献
11.
Byeong Kil Lee John L.K. John E. 《Very Large Scale Integration (VLSI) Systems, IEEE Transactions on》2006,14(6):609-615
Complex network protocols and various network services require significant processing capability for modern network applications. One of the important features in modern networks is differentiated service. Along with differentiated service, rapidly changing network environments result in congestion problems. In this paper, we analyze the characteristics of representative congestion control applications-scheduling and queue management algorithms, and we propose application-specific acceleration techniques that use instruction-level parallelism (ILP) and packet-level parallelism (PLP) in these applications. From the PLP perspective, we propose a hardware acceleration model based on detailed analysis of congestion control applications. In order to get large throughputs, a large number of processing elements (PEs) and a parallel comparator are designed. Such hardware accelerators provide large parallelism proportional to the number of processing elements added. A 32-PE enhancement yields 24/spl times/ speedup for weighted fair queueing (WFQ) and 27/spl times/ speedup for random early detection (RED). For ILP, new instruction set extensions for fast conditional operations are applied for congestion control applications. Based on our experiments, proposed architectural extensions show 10%-12% improvement in performance for instruction set enhancements. As the performance of general-purpose processors rapidly increases, defining architectural extensions (e.g., multi-media extensions (MMX) as in multimedia applications) for general-purpose processors could be an alternative solution for a wide range of network applications. 相似文献
12.
13.
A Unified Architecture for the Design and Evaluation of Wireless Fair Queueing Algorithms 总被引:2,自引:0,他引:2
Fair queueing in the wireless domain poses significant challenges due to unique issues in the wireless channel such as location-dependent and bursty channel errors. In this paper, we present a wireless fair service model that captures the scheduling requirements of wireless scheduling algorithms, and present a unified wireless fair queueing architecture in which scheduling algorithms can be designed to achieve wireless fair service. We map seven recently proposed wireless fair scheduling algorithms to the unified architecture, and compare their properties through simulation and analysis. We conclude that some of these algorithms achieve the properties of wireless fair service including short-term and long-term fairness, short-term and long-term throughput bounds, and tight delay bounds for channel access. 相似文献
14.
A new scheduling algorithm based on self-clocked fair queueing is proposed. The algorithm employs an array of sorting bins for managing the virtual finishing time of connections and uses token buckets as a behaviour-indicator. It remedies the drawbacks of existing fair queueing algorithms and is able to reserve bandwidth to connections while guaranteeing a class-dependent and rate-independent delay for behaving connections 相似文献
15.
Fair queueing of rate and delay-sensitive packet flows in a shared-medium, multihop wireless network is challenging due to the unique design issues. These issues include: 1) spatial contention among transmitting flows in a spatial locality, as well as spatial reuse of bandwidth through concurrent flow transmissions in different network locations; 2) conflicts between ensuring fairness and maximizing spatial channel reuse; and 3) the distributed nature of ad hoc fair queueing. In this paper, we propose a new topology-independent fair queueing model for a shared-medium ad hoc network. Our fairness model ensures coordinated fair channel access among spatially contending flows, while seeking to maximize spatial reuse of bandwidth. We describe packetized algorithms that realize the fluid fairness model with analytical performance bounds. We further design a distributed implementation which approximates the ideal centralized algorithm. We present simulations and analysis on the performance of our proposed algorithms. 相似文献
16.
Bursty ATM user traffic allowed by a jitter tolerant leaky bucket and its impact on link utilization
Herbert Heiss 《International Journal of Communication Systems》1994,7(3):161-175
In a network based on the asynchronous transfer mode (ATM), quality of service requirements have to be met even in the presence of users who send traffic as bursty as the policing device allows. For peak cell rate policing with a jitter tolerant leaky bucket, a periodic maximally bursty traffic pattern allowed by the leaky bucket is derived. The impact of this kind of bursty user traffic on the cell loss performance of the remaining sources is investigated by introducing, solving and applying the queueing model Geo(n) + P/D/1/K, where P stands for ‘periodic’. Taking bursty user traffic into account, it is shown that the maximal jitter or cell delay variation allocated to the user and tolerated by the leaky bucket is an important parameter for link utilization. The results help to answer the question under which conditions a shaping function is needed in conjunction with the usage parameter control function. 相似文献
17.
Network delay analysis of a class of fair queueing algorithms 总被引:1,自引:0,他引:1
A self-clocked fair queueing (SCFQ) scheme has been proposed by Golestani (see Proc. IEEE INFOCOM, p. 636-636, 1994) as an easily implementable version of fair queueing. In this paper, the worst case network delay performance of a class of fair queueing algorithms, including the SCFQ scheme, is studied. We build upon and generalize the methodology developed by Parekh and Gallager (see ACM/IEEE Trans. Networking, vol.1, no.3, p.344-357, 1993, and vol.2, no.2, p.137-150, 1994) to study this class of algorithms based on the leaky-bucket characterization of traffic. Under modest resource allocation conditions, the end-to-end session delays and backlogs corresponding to this class of algorithms are shown to be bounded. For the SCFQ scheme, these bounds are larger, but practically as good as the corresponding bounds for the PGPS scheme. It is shown that the SCFQ scheme can provide adequate performance guarantees for the delay-sensitive traffic in ATM 相似文献
18.
19.
20.
用户系统基于流的QoS调度 总被引:3,自引:0,他引:3
Diff-Serv网与用户系统之间有服务等级协议,有必要对用户系统的分组流进行合理调度,以确保定购的服务等级上速率、突发比特量等符合协议要求。进行合理调度还有有效分配带宽好处。基于流的排队(FBQ)在加权公平分享带宽的同时起到流量整形(traffic shaping)的作用,比较适合这种调度要求。但FBQ对带宽利用率不够高,本文在FBQ分类结构基础上通过新颖的分配令牌参数和虚拟时钟的方法构建新的分级调度算法,保留FBQ优点但提高带宽利用率。 相似文献