可编程路由器中基于缓冲队列长度阈值的处理器调度

可编程路由器除了转发IP分组之外,还需要执行计算任务.如何调度可编程路由器中CPU的处理能力是一个需要解决的重要问题.本文首先建立了一种通用的可编程路由器软件体系结构,在此基础上,提出了一种基于缓冲队列长度阈值的CPU调度算法,采用随机Petri网对算法进行了模型分析和计算.结果表明,该调度算法可以同时保证可编程路由器中的尽力发送流和QoS流的计算需求.     

输入排队中抢占式的短包优先调度算法

调度算法决定了输入排队交换结构的性能.本文根据Internet业务特征提出调度算法应保证短包的高优先级和低延迟.已有包方式调度中,长包信元的连续传输将造成短包长时间等待.为解决该问题,本文设计了一种低复杂度抢占式交换结构,并提出了相应的抢占式短包优先调度算法(P-SPF).短包优先可减小TCP流的RTT,并由此提高TCP之性能.通过排队论分析和实际业务源模型下仿真可知:P-SPF取得短包近似为零的平均包等待时间,同时达到94%的系统吞吐量.     

Optimal Time Slot Assignment Algorithm for Combined Unicast and Multicast Packets

This paper considers a packet‐scheduling algorithm for a given combined traffic of unicast and multicast data packets and proposes a hybrid router with several dedicated buses for multicast traffic. Our objective is to develop a scheduling algorithm that minimizes schedule length for the given traffic in the hybrid router. We derive a lower bound and develop an optimal solution algorithm for the hybrid router.     

A novel routing algorithm in distributed IEEE 802.16 mesh networks

In this paper, we propose a novel distributed routing algorithm for IEEE 802.16/WiMax based mesh networks. Our algorithm aims at providing routes for traffic flows with minimum end-to-end delays. Based on the underlying IEEE802.16 standard distributed scheduling mechanism, our routing algorithm is incorporated into the medium access control (MAC) layer. Each node determines the next-hop nodes for the passing flows according to the scheduling information and attempts to forward packets in the very earliest slots. In addition, a loop cancelation mechanism is proposed to avoid being trapped in path loops and thus guarantees the accessibility of our algorithm. The simulation results show that our proposal can considerably reduce the delay of traffic flows and also achieve load balance to a certain degree.     

Approximate fair bandwidth sharing in high-speed multimedia networks

Existing fair-queuing algorithms use complicated flow management mechanisms, thus making them expensive to deploy in current high-bandwidth networks. In this paper we propose a scalable SCORE (stateless core) approach to provide fair bandwidth sharing for a traffic environment composed of TCP and UDP flows. At an edge router, the arrival rates of each flow are estimated, each packet then being labelled with this estimate. The outgoing link’s fair share at a router is estimated based on UDP traffic. Probabilistic dropping is used to regulate those flows that send more than the fair share. At a core router, all the functions performed by an edge router are repeated, excluding the flow rate estimation. The simulation results show that the degree of fairness achieved by the proposed solution is comparable to that of other algorithms, but with a lower implementation cost.     

Core‐stateless fair rate estimation fair queuing

Core‐stateless mechanisms, such as core‐stateless fair queuing (CSFQ), reduce the complexity of fair queuing, which usually need to maintain states, manage buffers, and perform flow scheduling on a per‐flow basis. However, they require executing label rewriting and dropping decision on a per‐packet basis, thus preventing them from being widely deployed. In this paper, we propose a novel architecture based on CSFQ without per‐packet labelling. Similarly, we distinguish between edge routers and core routers. Edge routers maintain the per‐flow state by employing a fair queuing mechanism to allocate each flow a fair bandwidth share locally and a token bucket mechanism to regulate those flows with feedback packets sent from egress edge routers. Core routers do not maintain per‐flow state; they use FIFO packet scheduling extended by a fare rate alarm mechanism by estimating the arrival rate and the number of flows using a matching–mismatching algorithm. The novel scheme is called core‐stateless fair rate estimation fair queuing (CSFREFQ). CSFREFQ is proven to be capable of achieving max–min fairness. Furthermore, we present and discuss simulations and experiments on the performance under different traffic scenarios. Copyright © 2005 John Wiley & Sons, Ltd.     

ORCA-MRT: an optimization-based approach for fair scheduling in multirate TDMA wireless networks

This paper presents an optimization-based approach to solve the wireless fair scheduling problem under a multirate time division multiple access (TDMA)-based medium access control (MAC) framework. By formulating the fair scheduling problem as an assignment problem, the authors propose the optimal radio channel allocation for multirate transmission (ORCA-MRT) algorithm for fair bandwidth allocation in wireless data networks that support MRT at the radio link level. The key feature of ORCA-MRT is that while allocating transmission rate to each flow fairly, it keeps the interaccess delay bounded under a certain limit. The authors investigate the performance of the proposed ORCA-MRT scheduler in comparison to another recently proposed multirate fair scheduling algorithm. They also propose two channel prediction models and perform extensive simulations to investigate the performance of ORCA-MRT for different system parameters such as channel state correlation, number of flows, etc.     

A New Starting Potential Fair Queuing Algorithm with O(1) Virtual Time Computation Complexity

In this paper, we propose an efficient and simple fair queuing algorithm, called new starting potential fair queuing (NSPFQ), which has O(1) complexity for virtual time computation and also has good delay and fairness properties. NSPFQ introduces a simpler virtual time recalibration method as it follows a rate‐proportional property. The NSPFQ algorithm recalibrates the system virtual time to the minimum virtual start time among all possible virtual start times for head‐of‐line packets in backlogged sessions. Through analysis and simulation, we show that the proposed algorithm has good delay and fairness properties. We also propose a hardware implementation framework for the scheduling algorithm.     

Cell Switching Versus Packet Switching in Input-Queued Switches

Input Queued (IQ) switches have been well studied in the past two decades by researchers. The main problem concerning IQ switches is scheduling the switching fabric in order to transfer packets from input ports to output ports. Scheduling is relatively easier when all packets are of the same size. However, in practice, packets are of variable length. In the current implementation of switches, variable length packets are segmented into fixed length packets—also knowns as cells—for the purpose of scheduling. However, such cell-based switching comes with some significant disadvantages: (a) loss of bandwidth due to the existence of incomplete cells; and (b) additional overhead of segmentation of packets and re-assembly of cells. This is a strong motivation to study packet-based scheduling, i.e., scheduling the transfer of packets without segmenting them. The problem of packet scheduling was first considered by Marsan They showed that under any admissible Bernoulli IID (independent and identically distributed) arrival traffic, a simple modification of the Maximum Weight Matching (MWM) algorithm achieves 100% throughput. In this paper, we first show that no work-conserving (i.e., maximal) packet-based algorithm is stable for arbitrary admissible arrival processes. Thus, the results of Marsan are strongly dependent on the arrival distribution. Next, we propose a new class of “waiting” algorithms. We show that the “waiting”-MWM algorithm is stable for any admissible traffic using the fluid limit technique. We would like to note that the algorithms presented in this paper are distribution independent or universal. The algorithms and proof methods of this paper may be useful in the context of other scheduling problems.     

高速crossbar控制算法iDRR及其性能分析

DRR(Dual Round-Robin)算法^[6]是一种公平、高效、可扩展性强、硬件实现简单的crossbar控制算法.为了进一步改善算法的时延性能和公平性,文中提出了多重迭代DRR算法,即iDRR算法,它继承了DRR算法所有优点.仿真结果表明iDRR算法可达到100%吞吐量,在时延性能和公平性方面都优于DRR 算法.使用可编程逻辑器件实现了基于iDRR算法的仲裁器,工作频率达80MHz,可支持10Gbps速率的输入端口,可用于超高速、大容量的路由器中.     

Implementing scheduling algorithms in high-speed networks

The fluid generalized processor sharing (GPS) algorithm has desirable properties for integrated services networks and many packet fair queueing (PFQ) algorithms have been proposed to approximate GPS. However, there have been few high-speed implementations of PFQ algorithms that can support a large number of sessions with diverse rate requirements and at the same time maintain all the important properties of GPS. The implementation cost of a PFQ algorithm is determined by: (1) computation of the system virtual time function; (2) maintenance of the relative ordering of the packets via their timestamps (scheduling); and (3) regulation of packets based on eligibility time, in some algorithms. While most of the recently proposed PFQ algorithms reduce the complexity of computing the system virtual time function, the complexity of scheduling and traffic regulation is still a function of the number of active sessions. In addition, while reducing the algorithmic or asymptotic complexity has been the focus of most analysis, it is also important to reduce the complexity of basic operations in order for the algorithm to run at high speed. We develop techniques to reduce both types of complexities for networks of both fixed and variable size packets. Regulation and scheduling are implemented in an integrated architecture that can be viewed as logically performing sorting in two dimensions simultaneously. By using a novel grouping architecture, we are able to perform this with an algorithmic complexity independent of the number of sessions in the system at the cost of a small controllable amount of relative error. To reduce the cost of basic operations, we propose a hardware-implementation framework and several novel techniques that reduce the on-chip memory size, off-chip memory bandwidth, and off-chip access latency. The proposed implementation techniques have been incorporated into commercial ATM switch and IP router products     

LHFS-支持公平服务的CICQ混合调度策略

 针对现有联合输入交叉点排队交换结构(CICQ,Combined Input and Cross-point Queuing)调度策略无法提供基于"流"的服务质量保障,探讨了在CICQ交换结构实施基于流调度的可能性,提出一种能够为到达流提供公平服务的分层混合公平服务调度策略—LHFS(Layered and Hybrid Fair Scheduling).LHFS对每个输入、输出端口可独立地进行变长分组交换,其算法复杂度为O(1),具有良好可扩展特性.理论分析结果表明,LHFS能够为业务流提供时延上限和公平性保障.最后,基于SPES(Switching Performance Evaluation System)仿真系统对LHFS的性能进行了评估.     

Hardware implementation of fair queuing algorithms for asynchronoustransfer mode networks

Providing quality-of-service guarantees in both cell- and packet-based networks requires the use of a scheduling algorithm in the switches and network interfaces. These algorithms need to be implemented in hardware in a high-speed switch. The authors present a number of approaches to implement scheduling algorithms in hardware. They begin by presenting a general methodology for the design of timestamp-based fair queuing algorithms that provide the same bounds on end-to-end delay and fairness as those of weighted fair queuing, yet have efficient hardware implementations. Based on this general methodology, the authors describe two specific algorithms, frame-based fair queuing and starting potential-based fair queuing, and discuss illustrative implementations in hardware. These algorithms may be used in both cell switches and packet switches with variable-size packets. A methodology for combining a traffic shaper with this class of fair queuing schedulers is also presented for use in network interface devices, such as an ATM segmentation and reassembly device     

Centralized and Distributed Algorithms for Routing and Weighted Max-Min Fair Bandwidth Allocation

Given a set of demands between pairs of nodes, we examine the traffic engineering problem of flow routing and fair bandwidth allocation where flows can be split to multiple paths (e.g., MPLS tunnels). This paper presents an algorithm for finding an optimal and global per-commodity max-min fair rate vector in a polynomial number of steps. In addition, we present a fast and novel distributed algorithm where each source router can find the routing and the fair rate allocation for its commodities while keeping the locally optimal max-min fair allocation criteria. The distributed algorithm is a fully polynomial epsilon-approximation (FPTAS) algorithm and is based on a primal-dual alternation technique. We implemented these algorithms to demonstrate its correctness, efficiency, and accuracy.      

Defending against distributed denial-of-service attacks with max-min fair server-centric router throttles

Our work targets a network architecture and accompanying algorithms for countering distributed denial-of-service (DDoS) attacks directed at an Internet server. The basic mechanism is for a server under stress to install a router throttle at selected upstream routers. The throttle can be the leaky-bucket rate at which a router can forward packets destined for the server. Hence, before aggressive packets can converge to overwhelm the server, participating routers proactively regulate the contributing packet rates to more moderate levels, thus forestalling an impending attack. In allocating the server capacity among the routers, we propose a notion of level-k max-min fairness. We first present a control-theoretic model to evaluate algorithm convergence under a variety of system parameters. In addition, we present packet network simulation results using a realistic global network topology, and various models of good user and attacker distributions and behavior. Using a generator model of web requests parameterized by empirical data, we also evaluate the impact of throttling in protecting user access to a web server. First, for aggressive attackers, the throttle mechanism is highly effective in preferentially dropping attacker traffic over good user traffic. In particular, level-k max-min fairness gives better good-user protection than recursive pushback of max-min fair rate limits proposed in the literature. Second, throttling can regulate the experienced server load to below its design limit - in the presence of user dynamics - so that the server can remain operational during a DDoS attack. Lastly, we present implementation results of our prototype on a Pentium III/866 MHz machine. The results show that router throttling has low deployment overhead in time and memory.     

Algorithms for packet classification

The process of categorizing packets into “flows” in an Internet router is called packet classification. All packets belonging to the same flow obey a predefined rule and are processed in a similar manner by the router. For example, all packets with the same source and destination IP addresses may be defined to form a flow. Packet classification is needed for non-best-effort services, such as firewalls and quality of service; services that require the capability to distinguish and isolate traffic in different flows for suitable processing. In general, packet classification on multiple fields is a difficult problem. Hence, researchers have proposed a variety of algorithms which, broadly speaking, can be categorized as basic search algorithms, geometric algorithms, heuristic algorithms, or hardware-specific search algorithms. In this tutorial we describe algorithms that are representative of each category, and discuss which type of algorithm might be suitable for different applications     

A game-based algorithm for fair bandwidth allocation in Fibre-Wireless access networks

Fibre-Wireless (FiWi) access networks have been proposed as flexible and cost-effective solutions for future access networks. At the wireless mesh section, wireless routers have to forward both local traffic from directly connected users and foreign traffic from neighbour wireless routers. How to allocate resources to local and foreign traffic at each router in a balanced way, while avoiding starvation of routers requiring less resources, is a fundamental issue that must be solved so that new services emerge. Here, we develop a repeated game framework for bandwidth allocation and propose an algorithm that allocates bandwidth in a fair manner. The algorithm is able to detect over claiming routers and avoid possible denial of service that these may cause to others. Moreover, unfruitful use of resource is prevented, avoiding the forwarding of packets that would be dropped at some point later in the path, and queueing delay conditions are kept similar among local and foreign traffic. These fair network conditions open way for QoS support since it is easier to ensure the operationality of services.     

The iSLIP scheduling algorithm for input-queued switches

An increasing number of high performance internetworking protocol routers, LAN and asynchronous transfer mode (ATM) switches use a switched backplane based on a crossbar switch. Most often, these systems use input queues to hold packets waiting to traverse the switching fabric. It is well known that if simple first in first out (FIFO) input queues are used to hold packets then, even under benign conditions, head-of-line (HOL) blocking limits the achievable bandwidth to approximately 58.6% of the maximum. HOL blocking can be overcome by the use of virtual output queueing, which is described in this paper. A scheduling algorithm is used to configure the crossbar switch, deciding the order in which packets will be served. Previous results have shown that with a suitable scheduling algorithm, 100% throughput can be achieved. In this paper, we present a scheduling algorithm called iSLIP. An iterative, round-robin algorithm, iSLIP can achieve 100% throughput for uniform traffic, yet is simple to implement in hardware. Iterative and noniterative versions of the algorithms are presented, along with modified versions for prioritized traffic. Simulation results are presented to indicate the performance of iSLIP under benign and bursty traffic conditions. Prototype and commercial implementations of iSLIP exist in systems with aggregate bandwidths ranging from 50 to 500 Gb/s. When the traffic is nonuniform, iSLIP quickly adapts to a fair scheduling policy that is guaranteed never to starve an input queue. Finally, we describe the implementation complexity of iSLIP. Based on a two-dimensional (2-D) array of priority encoders, single-chip schedulers have been built supporting up to 32 ports, and making approximately 100 million scheduling decisions per second     

ABE: providing a low-delay service within best effort

We propose alternative best effort (ABE), a novel service for IP networks, which idea of providing low-delay at the expense of maybe less throughput. The objective is to retain the simplicity of the original Internet single-class best-effort service while providing low-delay to interactive adaptive applications. With ABE, every best effort packet is marked as either green or blue. Green packets are guaranteed a low bounded delay in every router. In exchange, green packets are more likely to be dropped (or marked using congestion notification) during periods of congestion than blue packets. For every packet, the choice of color is made by the application based on the nature of its traffic and on global traffic conditions. Typically, an interactive application with real-time deadlines, such as audio, will mark most at its packets as green, as long as the network conditions offer large enough throughput. In contrast, an application that transfers binary data such as bulk data transfer will seek to minimize overall transfer time and send blue traffic. We propose router requirements that aim at enforcing benefits for all types of traffic, namely that green traffic achieves low-delay and blue traffic receives at least as much throughput as it would in a flat (legacy) best effort network. ABE is different from differentiated or integrated services in that neither packet color can be said to receive better treatment; thus, flat rate pricing may be maintained, and there is no need for reservations or profiles. We define the ABE service, its requirements, properties, and usage. We discuss the implications of replacing the existing IP best effort service by the ABE service. We propose and analyze an implementation based on a new scheduling method called duplicate scheduling with deadlines. It supports any mixture of TCP, TCP-friendly, and non-TCP-friendly traffic     

Quality‐of‐Service Mechanisms for Flow‐Based Routers

In this paper, we propose quality of service mechanisms for flow‐based routers which have to handle several million flows at wire speed in high‐speed networks. Traffic management mechanisms are proposed for guaranteed traffic and non‐guaranteed traffic separately, and then the effective harmonization of the two mechanisms is introduced for real networks in which both traffic types are mixed together. A simple non‐work‐conserving fair queuing algorithm is proposed for guaranteed traffic, and an adaptive flow‐based random early drop algorithm is proposed for non‐guaranteed traffic. Based on that basic architecture, we propose a dynamic traffic identification method to dynamically prioritize traffic according to the traffic characteristics of applications. In a high‐speed router system, the dynamic traffic identification method could be a good alternative to deep packet inspection, which requires handling of the IP packet header and payload. Through numerical analysis, simulation, and a real system experiment, we demonstrate the performance of the proposed mechanisms.