Management of Multi-Queue Switches in QoS Networks

The concept of Quality of Service (QoS) networks has gained growing attention recently, as the traffic volume in the Internet constantly increases, and QoS guarantees are essential to ensure proper operation of most communication-based applications. A QoS switch serves m incoming queues by transmitting packets arriving to these queues through one output port, one packet per time step. Each packet is marked with a value indicating its priority in the network. Since the queues have bounded capacities and the rate of arriving packets can be much higher than the transmission rate, packets can be lost due to insufficient queue space. The goal is to maximize the total value of transmitted packets. This problem encapsulates two dependent questions: buffer management, namely which packets to admit into the queues, and scheduling, i.e. which queue to use for transmission in each time step. We use competitive analysis to study online switch performance in QoS-based networks. Specifically, we provide a novel generic technique that decouples the buffer management and scheduling problems. Our technique transforms any single-queue buffer management policy (preemptive or non-preemptive) to a scheduling and buffer management algorithm for our general m queues model, whose competitive ratio is at most twice the competitive ratio of the given buffer management policy. We use our technique to derive concrete algorithms for the general preemptive and non-preemptive cases, as well as for the interesting special cases of the 2-value model and the unit-value model. We also provide a 1.58-competitive randomized algorithm for the unit-value case. This case is interesting by itself since most current networks (e.g. IP networks) do not yet incorporate full QoS capabilities, and treat all packets equally.     

Balanced Scheduling toward Loss-Free Packet Queuing and Delay Fairness

In current networks, packet losses can occur if routers do not provide sufficiently large buffers. This paper studies how many buffers should be provided in a router to eliminate packet losses. We assume a network router has m incoming queues, each corresponding to a single traffic stream, and must schedule at any time on-line from which queue to take the next packet to send out. To exclude packet losses with a small amount of buffers, the maximum queue length must be kept low over the entire scheduling period. We call this new on-line problem the balanced scheduling problem (BSP). By competitive analysis, we measure the power of on-line scheduling algorithms to prevent packet losses. We show that a simple greedy algorithm is Θ(log m)-competitive which is asymptotically optimal, while Round-Robin scheduling is not better than m-competitive, as actually is any deterministic on-line algorithm for BSP. We also give a polynomial time algorithm for solving off-line BSP optimally. We also study another on-line balancing problem that tries to balance the delay among the m traffic streams.     

Packet mode and QoS algorithms for buffered crossbar switches with FIFO queuing

The buffered crossbar switch architecture has recently gained considerable research attention. In such a switch, besides normal input and output queues, a small buffer is associated with each crosspoint. Due to the introduction of crossbar buffers, output and input dependency is eliminated, and the scheduling process is greatly simplified. We analyze the performance of switch policies by means of competitive analysis, where a uniform guarantee is provided for all traffic patterns. We assume that each packet has an intrinsic value designating its priority and the goal of the switch policy is to maximize the weighted throughput of the switch. We consider FIFO queueing buffering policies, which are deployed by the majority of today’s Internet routers. In packet-mode scheduling, a packet is divided into a number of unit length cells and the scheduling policy is constrained to schedule all the cells contiguously, which removes reassembly overhead and improves Quality-of-Service. For the case of variable length packets with uniform value density (Best Effort model), where the packet value is proportional to its size, we present a packet-mode greedy switch policy that is 7-competitive. For the case of unit size packets with variable values (Differentiated Services model), we propose a β-preemptive (β is a preemption factor) greedy switch policy that achieves a competitive ratio of 6 + 4β + β ² + 3/(β − 1). In particular, its competitive ratio is at most 19.95 for the preemption factor of β = 1.67. As far as we know, this is the first constant-competitive FIFO policy for this architecture in the case of variable value packets. In addition, we evaluate performance of β-preemptive greedy switch policy by simulations and show that it outperforms other natural switch policies. The presented policies are simple and thus can be efficiently implemented at high speeds. Moreover, our results hold for any value of the internal switch fabric speedup.     

Trends in highly scalable crossbar-based packet switch architecture

A combined input and crosspoint queued (CICQ) switch is receiving significant attention to be the next generation high speed packet switch for its scalability; however, a multi-cabinet implementation of a combined input and crosspoint queued (CICQ) switch unavoidably introduces a large round-trip time (RTT) latency between the line cards and switch fabric, resulting a large crosspoint (CP) buffer requirement. In this paper, virtual crosspoint queues (VCQs) that significantly reduces the CP buffer requirement of the CICQ switch is investigated. The VCQs unit resides inside the switch fabric, is dynamically shared among virtual output queues (VOQ) from the same source port, and is operated at the line rate, making the implementation practical. A threshold-based exhaustive round-robin (T-ERR) arbitration is employed to reduce buffer hogging at VCQ. The T-ERR at VCQ and CP arbiters serves packets residing in a longer queue more frequently than packet residing in a shorter queue. Consequently, the T-ERR, drastically increases the throughput of the CICQ switch with small CP buffers. A multi-cabinet implementation of CICQ switch do not support multicasting traffic well since a combination of small CP buffer in the switch fabric and a large RTT latency between the line cards and switch fabric results in non-work conservation of the intra-switch link. Deployment of multicast FIFO buffer between the input buffer and CP buffer shows a promise. With its ability to achieve high throughput independent of RTT and switch port size, the integration of the VCQ architecture and T-ERR scheduler to the CICQ switch is ideal for supporting ever-increasing Internet traffic that requires higher data rate, larger switch size, and efficient multicasting.     

Competitive On-Line Switching Policies

Consider the following problem. A switch connecting n input channels to a single output channel must deliver all incoming messages through this channel. Messages are composed of packets , and in each time slot the switch can deliver a single packet from one of the input queues to the output channel. In order to prevent packet loss, a buffer is maintained for each input channel. The goal of a switching policy is to minimize the maximum buffer size. The setting is on-line; decisions must be made based on the current state without knowledge of future events. This general scenario models multiplexing tasks in various systems such as communication networks, cable modem systems, and traffic control. Traditionally, researchers analyzed the performance of a given policy assuming some distribution on the arrival rates of messages at the input queues, or assuming that the service rate is at least the aggregate of all the input rates. We use competitive analysis, avoiding any prior assumptions on the input. We show O(log n )-competitive switching policies for the problem and demonstrate matching lower bounds.     

Competitive On-Line Switching Policies

Abstract. Consider the following problem. A switch connecting n input channels to a single output channel must deliver all incoming messages through this channel. Messages are composed of packets , and in each time slot the switch can deliver a single packet from one of the input queues to the output channel. In order to prevent packet loss, a buffer is maintained for each input channel. The goal of a switching policy is to minimize the maximum buffer size. The setting is on-line; decisions must be made based on the current state without knowledge of future events. This general scenario models multiplexing tasks in various systems such as communication networks, cable modem systems, and traffic control. Traditionally, researchers analyzed the performance of a given policy assuming some distribution on the arrival rates of messages at the input queues, or assuming that the service rate is at least the aggregate of all the input rates. We use competitive analysis, avoiding any prior assumptions on the input. We show O(log n )-competitive switching policies for the problem and demonstrate matching lower bounds.     

Balanced Scheduling toward Loss-Free Packet Queuing and Delay Fairness

In current networks, packet losses can occur if routers do not provide sufficiently large buffers. This paper studies how many buffers should be provided in a router to eliminate packet losses. We assume a network router has m incoming queues, each corresponding to a single traffic stream, and must schedule at any time on-line from which queue to take the next packet to send out. To exclude packet losses with a small amount of buffers, the maximum queue length must be kept low over the entire scheduling period. We call this new on-line problem the balanced scheduling problem (BSP). By competitive analysis, we measure the power of on-line scheduling algorithms to prevent packet losses. We show that a simple greedy algorithm is (log m)-competitive which is asymptotically optimal, while Round-Robin scheduling is not better than m-competitive, as actually is any deterministic on-line algorithm for BSP. We also give a polynomial time algorithm for solving off-line BSP optimally. We also study another on-line balancing problem that tries to balance the delay among the m traffic streams.     

Synchronous versus asynchronous operation of a packet switch with combined input and output queueing

A single-stage non-blocking N × N packet switch with combined input and output queueing is considere. The limited queueing at the output ports partially resolves output port contention. Overflow at the output queues is prevented by employment of a backpressure mechanism and additional queueing at the input ports. This paper investigates the performance of the switch under two different modes of operation: asynchronous and synchronous or slotted. For the purpose of comparison a switch model is developed. Assuming Poisson packet arrivals, several performance measures are obtained analytically. These include the distribution of the delay through the switch, the input queue length distribution, packet losses at the inputs in the case of finite input queues, and the maximum switch throughput. The results obtained demonstrate a slight performance advantage of asynchronous over synchronous operation. However, the maximum switch throughput is the same for both modes of operation.     

Non-preemptive buffer management for latency sensitive packets

The delivery of latency sensitive packets is a crucial issue in real-time applications of communication networks. Such packets often have a firm deadline and a packet becomes useless if it arrives after its deadline. The deadline, however, applies only to the packet’s journey through the entire network; individual routers along the packet’s route face a more flexible deadline. We study policies for admitting latency sensitive packets at a router. Each packet is tagged with a value. A packet waiting at a router loses value over time as its probability of arriving at its destination on time decreases. The router is modeled as a non-preemptive queue, and its objective is to maximize the total value of the forwarded packets. When a router receives a packet, it must either accept it (and delay future packets), or reject it immediately. The best policy depends on the set of values that a packet can take. We consider three natural sets: an unrestricted model, a real-valued model, where any value over 1 is allowed, and an integral-valued model. For the unrestricted model, we prove that there is no constant competitive ratio algorithm. For the real-valued model, we give a randomized 4-competitive algorithm and a matching lower bound (up to low order terms). We also provide a deterministic lower bound of \(\phi ^3 - {\varepsilon }\approx 4.236\), almost matching the previously known 4.24-competitive algorithm. For the integral-valued model, we describe a deterministic 4-competitive algorithm, and prove that this is tight even for randomized algorithms (up to low order terms).     

An Experimental Study of New and Known Online Packet Buffering Algorithms

We present the first experimental study of online packet buffering algorithms for network switches. We consider a basic scenario in which m queues of size B have to be maintained so as to maximize the packet throughput. For this model various online algorithms with competitive factors ranging between 2 and 1.5 were developed in the literature. We first develop a new 2-competitive online algorithm, called HSFOD, which is especially designed to perform well under real-world conditions. In our experimental study we have implemented all the proposed algorithms, including HSFOD, and tested them on packet traces from benchmark libraries. We have evaluated the experimentally observed competitiveness, the running times, memory requirements and actual packet throughput of the strategies. The tests were executed for varying values of m and B as well as varying switch speeds. It shows that greedy-like strategies and HSFOD perform best in practice.     

Optimal and online preemptive scheduling on uniformly related machines

We consider the problem of preemptive scheduling on uniformly related machines. We present a semi-online algorithm which, if the optimal makespan is given in advance, produces an optimal schedule. Using the standard doubling technique, this yields a 4-competitive deterministic and an e≈2.71-competitive randomized online algorithm. In addition, it matches the performance of the previously known algorithms for the offline case, with a considerably simpler proof. Finally, we study the performance of greedy heuristics for the same problem.     

Tiny Tera: a packet switch core

Describes Tiny Tera: a small, high-bandwidth, single-stage switch. Tiny Tera has 32 ports switching fixed-size packets, each operating at over 10 Gbps (approximately the Sonet OC-192e rate, a telecom standard for system interconnects). The switch distinguishes four classes of traffic and includes efficient support for multicasting. We aim to demonstrate that it is possible to use currently available CMOS technology to build this compact switch with an aggregate bandwidth of approximately 1 terabit per second and a central hub no larger than a can of soda. Such a switch could serve as a core for an ATM switch or an Internet router. Tiny Tera is an input-buffered switch, which makes it the highest bandwidth switch possible given a particular CMOS and memory technology. The switch consists of three logical elements: ports, a central crossbar switch, and a central scheduler. It queues packets at a port on entry and optionally prior to exit. The scheduler, which has a map of each port's queue occupancy, determines the crossbar configuration every packet time slot. Input queueing, parallelism, and tight integration are the keys to such a high-bandwidth switch. Input queueing reduces the memory bandwidth requirements: When a switch queues packets at the input, the buffer memories need run no faster than the line rate. Thus, there is no need for the speedup required in output-queued switches     

Port partitioning and dynamic queueing for IP forwarding

With the increase of internet protocol (IP) packets the performance of routers became an important issue in internet/working. In this paper we examine the matching algorithm in gigabit router which has input queue with virtual output queueing. Dynamic queue scheduling is also proposed to reduce the packet delay and packet loss probability. Port partitioning is employed to reduce the computational burden of the scheduler in a switch which matches the input and output ports for fast packet switching. Each port is divided into two groups such that the matching algorithm is implemented within each pair of groups in parallel. The matching is performed by exchanging the pair of groups at every time slot. Two algorithms, maximal weight matching by port partitioning (MPP) and modified maximal weight matching by port partitioning (MMPP) are presented. In dynamic queue scheduling, a popup decision rule for each delay critical packet is made to reduce both the delay of the delay critical packet and the loss probability of loss critical packet. Computational results show that MMPP has the lowest delay and requires the least buffer size. The throughput is illustrated to be linear to the packet arrival rate, which can be achieved under highly efficient matching algorithm. The dynamic queue scheduling is illustrated to be highly effective when the occupancy of the input buffer is relatively high.Scope and purposeTo cope with the increasing internet traffic, it is necessary to improve the performance of routers. To accelerate the switching from input ports to output in the router partitioning of ports and dynamic queueing are proposed. Input and output ports are partitioned into two groups A/B and a/b, respectively. The matching for the packet switching is performed between group pairs (A, a) and (B, b) in parallel at one time slot and (A, b) and (B, a) at the next time slot. Dynamic queueing is proposed at each input port to reduce the packet delay and packet loss probability by employing the popup decision rule and applying it to each delay critical packet.The partitioning of ports is illustrated to be highly effective in view of delay, required buffer size and throughput. The dynamic queueing also demonstrates good performance when the traffic volume is high.     

Performance analysis of small non-uniform packet switches

Packet switches have been studied extensively as part of ATM and LAN networks under the assumption that the number of input ports N tends to infinity. Our study of packet switches is motivated by networks on chips, where N is usually 4 or 5 and asymptotic models lead to inaccurate results. We consider small non-uniform switches and accurately approximate stability conditions and throughput. In addition to this, we approximate the mean waiting time in the switch by that in a ./Geo/1 queue.     

An Optimal Lower Bound for Buffer Management in Multi-Queue Switches

In the online packet buffering problem (also known as the unweighted FIFO variant of buffer management), we focus on a single network packet switching device with several input ports and one output port. This device forwards unit-size, unit-value packets from input ports to the output port. Buffers attached to input ports may accumulate incoming packets for later transmission; if they cannot accommodate all incoming packets, their excess is lost. A packet buffering algorithm has to choose from which buffers to transmit packets in order to minimize the number of lost packets and thus maximize the throughput. We present a tight lower bound of e/(e?1)≈1.582 on the competitive ratio of the throughput maximization, which holds even for fractional or randomized algorithms. This improves the previously best known lower bound of 1.4659 and matches the performance of the algorithm Random Schedule. Our result contradicts the claimed performance of the algorithm Random Permutation; we point out a flaw in its original analysis.     

Scheduling Protocols for Switches with Large Envelopes

Traditionally, switches make scheduling decisions on the granularity of a packet. However, this is becoming increasingly difficult since network bandwidth is growing rapidly whereas packet sizes remain largely unchanged. Therefore the service time of an individual packet is decreasing rapidly. In this paper we study switches that make scheduling decisions on the granularity of an envelope which can be much larger than a packet in size. For an output-queued switch with envelope size E, each output chooses one input every E time steps and transmits packets from this chosen input during the next E steps. For an input-queued switch with envelope size E, one matching from the inputs to the outputs is computed every E steps and only the input–output pairs that are defined by this matching are allowed to transmit packets during the next E steps. Traditional switches correspond to envelope size E = 1 and almost all previous scheduling work deals with this case exclusively. We first show how some stable protocols for scheduling networks of output-queued switches with E = 1 fail for arbitrary E when these protocols are generalized in the most straightforward manner. We then present an extremely simple protocol that does guarantee network stability for output-queued switches for any E ≥ 1. For input-queued switches we first present a max-weight matching protocol that is stable for a single switch with arbitrary E. We then present a more complex protocol that achieves stability for a network of input-queued switches for any E ≥ 1.     

Buffer Management for Colored Packets with Deadlines

We consider buffer management of unit packets with deadlines for a multi-port device with reconfiguration overhead. The goal is to maximize the throughput of the device, i.e., the number of packets delivered by their deadline. For a single port or with free reconfiguration, the problem reduces to the well-known packets scheduling problem, where the celebrated earliest-deadline-first (EDF) strategy is optimal 1-competitive. However, EDF is not 1-competitive when there is a reconfiguration overhead. We design an online algorithm that achieves a competitive ratio of 1−o(1) when the ratio between the minimum laxity of the packets and the number of ports tends to infinity. This is one of the rare cases where one can design an almost 1-competitive algorithm. One ingredient of our analysis, which may be interesting on its own right, is a perturbation theorem on EDF for the classical packets scheduling problem. Specifically, we show that a small perturbation in the release and deadline times cannot significantly degrade the optimal throughput. This implies that EDF is robust in the sense that its throughput is close to the optimum even when the deadlines are not precisely known.     

A new congestion control algorithm for improving the performance of a broadcast-based multiprocessor architecture

Congestion occurring in the input queues of broadcast-based multiprocessor architectures can severely limit their overall performance. The existing congestion control algorithms estimate congestion based on a node’s output channel parameters such as the number of free virtual channels or the number of packets waiting at the channel queue. In this paper, we have proposed a new congestion control algorithm to prevent congestion on broadcast-based multiprocessor architectures with multiple input queues. Our algorithm performs congestion control at the packet level and takes into account the next input queue number which will be accessed by the processor, which form the fundamental differences between our algorithm and the algorithms based on the idea of virtual channel congestion control. The performance of the algorithm is evaluated by OPNET Modeler with various synthetic traffic patterns on a 64-node Simultaneous Optical Multiprocessor Exchange Bus (SOME-Bus) architecture employing the message passing protocol. Performance measures such as average input waiting time, average network response time and average processor utilization have been collected before and after applying the algorithm. The results show that the proposed algorithm is able to decrease the average input waiting time by 13.99% to 20.39%, average network response time by 8.76% to 20.36% and increase average processor utilization by 1.92% to 6.63%. The performance of the algorithm is compared with that of the other congestion control algorithms and it is observed that our algorithm performs better under all traffic patterns. Also, theoretical analysis of the proposed method is carried out by using queuing networks.     

An efficient implementation of bypass queue under bursty traffic

In this paper we present a new bypass queue scheme for an input buffered nonblocking packet switch operating under bursty traffic. The proposed scheme uses first-in-first-out (FIFO) queues and is thus more efficient for implementation as compared to other schemes which use first-in-random-out (FIRO) queues. Maximum throughput comparison of the proposed scheme with the conventional scheme shows significant improvement.     

The Network as a Storage Device: Dynamic Routing with Bounded Buffers

We study dynamic routing in store-and-forward packet networks where each network link has bounded buffer capacity for receiving incoming packets and is capable of transmitting a fixed number of packets per unit of time. At any moment in time, packets are injected at various network nodes with each packet specifying its destination node. The goal is to maximize the throughput, defined as the number of packets delivered to their destinations. In this paper, we make some progress on throughput maximization in various network topologies. Let n and m denote the number of nodes and links in the network, respectively. For line networks, we show that Nearest-to-Go (NTG), a natural distributed greedy algorithm, is -competitive, essentially matching a known lower bound on the performance of any greedy algorithm. We also show that if we allow the online routing algorithm to make centralized decisions, there is a randomized polylog(n)-competitive algorithm for line networks as well as for rooted tree networks, where each packet is destined for the root of the tree. For grid graphs, we show that NTG has a competitive ratio of while no greedy algorithm can achieve a ratio better than . Finally, for arbitrary network topologies, we show that NTG is -competitive, improving upon an earlier bound of O(mn). An extended abstract appeared in the Proceedings of the 8th Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2005, Berkeley, CA, USA, pp. 1–13, Lecture Notes in Computer Science, vol. 1741, Springer, Berlin. S. Angelov is supported in part by NSF Career Award CCR-0093117, NSF Award ITR 0205456 and NIGMS Award 1-P20-GM-6912-1. S. Khanna is supported in part by an NSF Career Award CCR-0093117, NSF Award CCF-0429836, and a US-Israel Binational Science Foundation Grant. K. Kunal is supported in part by an NSF Career Award CCR-0093117 and NSF Award CCF-0429836.