We consider the problem of managing a bounded size First-In-First-Out (FIFO) queue buffer, where each incoming unit-sized packet requires several rounds of processing before it can be transmitted out. Our objective is to maximize the total number of successfully transmitted packets. We consider both push-out (when the policy is permitted to drop already admitted packets) and non-push-out cases. In particular, we provide analytical guarantees for the throughput performance of our algorithms. We further conduct a comprehensive simulation study which experimentally validates the predicted theoretical behaviour.
Various models have been proposed and studied, including, among others, QoS-oriented models where packets have weights @cite_25 @cite_11 @cite_21 @cite_27 and models where packets have dependencies @cite_4 @cite_3 . A related field that has received much attention in recent years focuses on various switch architectures and aims at designing competitive algorithms for such multi-queue scenarios; see, e.g., @cite_30 @cite_18 @cite_26 @cite_5 @cite_6 . Some other works also provide experimental studies of these algorithms and further validate their performance @cite_28 .
@cite_30 @cite_18 @cite_26 @cite_4 @cite_28 @cite_21 @cite_3 @cite_6 @cite_27 @cite_5 @cite_25 @cite_11
1911070062 2155749359 2953352566 2136340918 1537647641 1544216698 2169023571 2078182186 2076648698 1504391490 2033020629 2067963342 2070497154 2169444479 1666061104 1986442642 2593786213 2109679596 2101438247 2035671992
Combined input and output queued (CIOQ) architectures with a moderate fabric speedupS> 1 have come to play a major role in the design of high performance switches. In this paper we study CIOQ switches with First-In-First-Out (FIFO) buffers providing Quality of Service (QoS) guarantees. The goal of the switch policy is to maximize the total value of packets sent out of the switch. We analyze the performance of a switch policy by means of competitive analysis, where a uniform performance guarantee is provided for all traffic patterns. Azar and Richter [8] proposed an algorithm β-PG(Preemptive Greedy with a preemption factor of β) that is 8-competitive for an arbitrary speedup value when β= 3. We improve upon their result by showing that this algorithm achieves a competitive ratio of 7.5 and 7.47 for β= 3 and β= 2.8, respectively. Basically, we demonstrate that β-PGis at most @math and at least @math -competitive. Motivated by the quality-of-service (QoS) buffer management problem, we consider online scheduling of packets with hard deadlines in a finite capacity queue. At any time, a queue can store at most b isin Z + packets. Packets arrive over time. Each packet is associated with a non-negative value and an integer deadline. In each time step, only one packet is allowed to be sent. Our objective is to maximize the total value gained by the packets sent by their deadlines in an online manner. Due to the Internet traffic's chaotic characteristics, no stochastic assumptions are made on the packet input sequences. This model is called a finite-queue model. We use competitive analysis to measure an online algorithm's performance versus an unrealizable optimal offline algorithm who constructs the worst possible input based on the knowledge of the online algorithm. For the finite-queue model, we first present a deterministic 3-competitive memoryless online algorithm. Then, we give a randomized (Phi 2 = (1+radic(5) 2) 2 ap 2.618)-competitive memoryless online algorithm. The algorithmic framework and its theoretical analysis include several interesting features. First, our algorithms use (possibly) modified characteristics of packets; these characteristics may not be same as those specified in the input sequence. Second, our analysis method is different from the classical potential function approach. We use a simple charging scheme, which depends on a clever modification (during the course of the algorithm) on the packets in the queue of the optimal offline algorithm. We then prove that a set of invariants holds at the end of each time step. Finally, we analyze the two proposed algorithm in a relaxed model, in which packets have no hard deadlines but an order. We conclude that both algorithms have the same competitive ratios in the relaxed model. We study the problem of buffer management in QoS-enabled network switches in the bounded delay model where each packet is associated with a weight and a deadline. We consider the more realistic situation where the network switch has a finite buffer size. A 9.82-competitive algorithm is known for the case of multiple buffers (Azar and Levy, SWAT'06). Recently, for the case of a single buffer, a 3-competitive deterministic algorithm and a 2.618-competitive randomized algorithm was known (Li, INFOCOM'09). In this paper we give a simple deterministic 2-competitive algorithm for the case of a single buffer. We consider the problem of resource allocation in downlink OFDMA systems for multi service and unknown environment. Due to users' mobility and intercell interference, the base station cannot predict neither the Signal to Noise Ratio (SNR) of each user in future time slots nor their probability distribution functions. In addition, the traffic is bursty in general with unknown arrival. The probability distribution functions of the SNR, channel state and traffic arrival density are then unknown. Achieving a multi service Quality of Service (QoS) while optimizing the performance of the system (e.g. total throughput) is a hard and interesting task since it depends on the unknown future traffic and SNR values. In this paper we solve this problem by modeling the multiuser queuing system as a discrete time linear dynamic system. We develop a robust H∞ controller to regulate the queues of different users. The queues and Packet Drop Rates (PDR) are controlled by proposing a minimum data rate according to the demanded service type of each user. The data rate vector proposed by the controller is then fed as a constraint to an instantaneous resource allocation framework. This instantaneous problem is formulated as a convex optimization problem for instantaneous subcarrier and power allocation decisions. Simulation results show small delays and better fairness among users. We study the online problem of multiplexing packets with arbitrary deadlines in bounded multi-buffer switch. In this model, a switch consists of m input buffers each with bounded capacity B and one output port. Each arriving packet is associated with a value and a deadline that specifies the time limit till the packet can be transmitted. At each time step the switch can select any non-empty buffer and transmit one packet from that buffer. In the preemptive model, stored packets may be preempted from their buffers due to lack of buffer space or discarded due to the violation of the deadline constraints. If preemption is not allowed, every packet accepted and stored in the buffer must be transmitted before its deadline has expired. The goal is to maximize the benefit of the packets transmitted by their deadlines. To date, most models for packets with deadlines assumed a single buffer. To the best of our knowledge this is the first time a bounded multi-buffer switch is used with arbitrary deadline constraints Our main result is a 9.82-competitive deterministic algorithm for packets with arbitrary values and deadlines. Note that the greedy algorithm is not competitive. For the non-preemptive model we present a 2-competitive deterministic algorithm for the unit value packets. For arbitrary values we present a randomized algorithm whose competitiveness is logarithmic in the ratio between the largest and the smallest value of the packets in the sequence Motivated by providing differentiated services in the Internet, we consider online buffer management algorithms for quality-of-service network switches. We study a multi-buffer model . Packets have values and deadlines; they arrive at a switch over time. The switch consists of multiple buffers whose sizes are bounded. In each time step, only one pending packet can be sent. Our objective is to maximize the total value of the packets sent by their deadlines. We employ competitive analysis to measure an online algorithm's performance. In this paper, we first show that the lower bound of competitive ratio of a broad family of online algorithms is 2. Then we propose a ( @math )-competitive deterministic algorithm, which is improved from the previously best-known result 9.82 (Azar and Levy. SWAT 2006). We study a basic problem in Multi-Queue switches. A switch connects m input ports to a single output port. Each input port is equipped with an incoming FIFO queue with bounded capacity B. A switch serves its input queues by transmitting packets arriving at these queues, one packet per time unit. Since the arrival rate can be higher than the transmission rate and each queue has limited capacity, packet loss may occur as a result of insufficient queue space. The goal is to maximize the number of transmitted packets. This general scenario models most current networks (e.g., IP networks) which only support a “best effort” service in which all packet streams are treated equally. A 2-competitive algorithm for this problem was designed in [4] for arbitrary B. Recently, a ( 17 9 1.89 )-competitive algorithm was presented for B>1 in [2]. Our main result in this paper shows that for B which is not too small our algorithm can do better than 1.89, and approach a competitive ratio of ( e e-1 1.58 ). The problem of maximizing the weighted throughput in various switching settings has been intensively studied recently through competitive analysis. To date, the most general model that has been investigated is the standard CIOQ (Combined Input and Output Queued) switch architecture with internal fabric speedup S ≥ 1. CIOQ switches, that comprise the backbone of packet routing networks, are N × N switches controlled by a switching policy that incorporates two components: Admission control and scheduling. An admission control strategy is essential to determine the packets stored in the FIFO queues in input and output ports, while the scheduling policy conducts the transfer of packets through the internal fabric, from input ports to output ports. The online problem of maximizing the total weighted throughput of CIOQ switches was recently investigated by Kesselman and Rosen [2003]. They presented two different online algorithms for the general problem that achieve non-constant competitive ratios (linear in either the speedup or the number of distinct values, or logarithmic in the value range). We introduce the first constant-competitive algorithm for the general case of the problem, with arbitrary speedup and packet values. Specifically, our algorithm is 8-competitive, and is also simple and easy to implement. We consider packet scheduling in a network providing differentiated services, where each packet is assigned a value. We study various queueing models for supporting QoS (Quality of Service). In the nonpreemptive model, packets accepted to the queue will be transmitted eventually and cannot be dropped. The FIFO preemptive model allows packets accepted to the queue to be preempted (dropped) prior to their departure, while ensuring that transmitted packets are sent in the order of arrival. In the bounded delay model, packets must be transmitted before a certain deadline, otherwise it is lost (while transmission ordering is allowed to be arbitrary). In all models the goal of the buffer policy is to maximize the total value of the accepted packets.Let α be the ratio between the maximal and minimal value. For the non-preemptive model we derive a Θ(log &alpha) competitive ratio, both exhibiting a buffer policy and a general lower bound. For the interesting case of two distinct values, we give an 2α--1 α competitive buffer policy, which exactly matches the lower bound. We also analyze a RED-like policy and derive its competitive ratio, which is approximately 2α--0.5 α for two values and Θ(log α) for multiple values. In addition we improve the previous known lower and upper bounds of the Fixed Partition and Flexible Partition policies.For the FIFO preemptive model, we improve the general lower bound and show a tight bound for the special case of queue size 2. We prove that the bounded delay model with uniform delay 2 is equivalent to a modified FIFO preemptive model with queue size 2. We then give improved upper and lower bounds on the 2-uniform bounded delay model. We also give lower bound for the 2-variable bounded delay model, which matches the previously known upper bound. 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. Analytical models of IEEE 802.11-based WLANs are invariably based on approximations, such as the well-known mean-field approximations proposed by Bianchi for saturated nodes. In this paper, we provide a new approach for modeling the situation when the nodes are not saturated. We study a State Dependent Attempt Rate (SDAR) approximation to model M queues (one queue per node) served by the CSMA CA protocol as standardized in the IEEE 802.11 DCF. The approximation is that, when n of the M queues are non-empty, the attempt probability of the n non-empty nodes is given by the long-term attempt probability of n saturated nodes as provided by Bianchi's model. This yields a coupled queue system. When packets arrive to the M queues according to independent Poisson processes, we provide an exact model for the coupled queue system with SDAR service. The main contribution of this paper is to provide an analysis of the coupled queue process by studying a lower dimensional process and by introducing a certain conditional independence approximation. We show that the numerical results obtained from our finite buffer analysis are in excellent agreement with the corresponding results obtained from ns-2 simulations. We replace the CSMA CA protocol as implemented in the ns-2 simulator with the SDAR service model to show that the SDAR approximation provides an accurate model for the CSMA CA protocol. We also report the simulation speed-ups thus obtained by our model-based simulation. We study a basic buffer management problem that arises in network switches. Consider @math input ports, each of which is equipped with a buffer (queue) of limited capacity. Data packets arrive online and can be stored in the buffers if space permits; otherwise packet loss occurs. In each time step the switch can transmit one packet from one of the buffers to the output port. The goal is to maximize the number of transmitted packets. Simple arguments show that any work-conserving algorithm, which serves any nonempty buffer, is 2-competitive. Azar and Richter recently presented a randomized online algorithm and gave lower bounds for deterministic and randomized strategies. In practice, greedy algorithms are very important because they are fast, use little extra memory, and reduce packet loss by always serving a longest queue. In this paper we first settle the competitive performance of the entire family of greedy strategies. We prove that greedy algorithms are not better than 2-competitive no matter how ties are broken. Our lower bound proof uses a new recursive construction for building adversarial buffer configurations that may be of independent interest. We also give improved lower bounds for deterministic and randomized online algorithms. In this paper we present the first deterministic online algorithm that is better than 2-competitive. We develop a modified greedy algorithm, called semigreedy, and prove that it achieves a competitive ratio of @math . The new algorithm is simple, fast, and uses little extra memory. Only when the risk of packet loss is low does it not serve the longest queue. Additionally we study scenarios when an online algorithm is granted additional resources. We consider resource augmentation with respect to memory and speed; i.e., an online algorithm may be given larger buffers or higher transmission rates. We analyze greedy and other online strategies. An important issue in IP-based QoS networks is the effective management of packets at the router level. Specifically, if the arriving packets cannot all be stored in a buffer, or if the packets have deadlines by which they must be delivered, the router needs to identify the packets that should be dropped. In recent work, [6] propose a model, called buffer management with bounded delay, which can be thought of as an online scheduling problem on a single machine: packets arrive at a network switch and are stored in a buffer of size B. Each packet has a positive weight and a deadline, with the weight representing the value of transmitting the packet by its deadline. At each integer time step, exactly one packet can be transmitted, and the objective is to maximize the total weight of the transmitted packets. If B = ∞, this is the online version of the scheduling problem 1| p j = 1, r j , d j |Σ w j U j . (We assume that r j and d j are integers.) We study the behavior of algorithms for buffering packets weighted by different levels of Quality of Service (QoS) guarantees in a single queue. Buffer space is limited, and packet loss occurs when the buffer overflows. We describe a modification of the previously proposed “preemptive greedy” algorithm of for buffer management and give an analysis to show that this algorithm achieves a competitive ratio of at most 1.75. This improves upon recent work showing a 1.98 competitive ratio, and a previous result that shows a simple greedy algorithm has a competitive ratio of 2. The model is motivated by the problem of load distribution in large-scale cloud-based data processing systems. We consider a heterogeneous service system, consisting of multiple large server pools. The pools are different in that their servers may have different processing speeds and or different buffer sizes (which may be finite or infinite). We study an asymptotic regime in which the customer arrival rate and pool sizes scale to infinity simultaneously, in proportion to some scaling parameter n. Arriving customers are assigned to the servers by a "router," according to a pull-based algorithm, called PULL. Under the algorithm, each server sends a "pull-message" to the router, when it becomes idle; the router assigns an arriving customer to a server according to a randomly chosen available pull-message, if there are any, or to a random server, otherwise. Assuming subcritical system load, we prove asymptotic optimality of PULL. Namely, as system scale @math n??, the steady-state probability of an arriving customer experiencing blocking or waiting, vanishes. We also describe some generalizations of the model and PULL algorithm, for which the asymptotic optimality still holds. Several high-speed TCP variants are adopted by end users and therefore, heterogeneous congestion control has become the characteristic of newly emerging high-speed optical networks. In contrast to homogeneous TCP flows, fairness among heterogeneous TCP flows now depends on router parameters such as queue management scheme and buffer size. To the best of our knowledge, this is the first study of fairness performance among heterogeneous TCP variants over a 10 Gbps high-speed optical network environment. Our evaluation scenarios for heterogeneous TCP flows consist of TCP variants with substantial presence in current Internet; therefore, TCP-SACK, CUBIC TCP (CUBIC) and HighSpeed TCP (HSTCP) compete for bottleneck bandwidth. Experimental results for fairness are presented for different queue management schemes, such as Drop-tail, Random Early Detection (RED), CHOose and Keep for responsive flows CHOose and Kill for unresponsive flows (CHOKe), and Approximate Fair Dropping (AFD), with varying degree of buffer sizes. We observe heterogeneous TCP flows induce more unfairness than homogeneous ones. Active queue management (AQM) schemes, RED, CHOKe, and AFD, improve fairness for large buffer sizes as compared to Drop-tail, whereas AQM schemes lose the fairness advantage for small buffer sizes. This study provides preliminary results for fairness challenges to deploy all-optical routers with limited buffer size. We consider FIFO buffer management for switches providing differentiated services. In each time step, an arbitrary number of packets arrive, and only one packet can be sent. The buffer can store a limited number of packets, and, due to the FIFO property, the sequence of sent packets has to be a subsequence of the arriving packets. The differentiated service model is abstracted by attributing each packet with a value according to its service level. A buffer management strategy can drop packets. The goal is to maximize the sum of values of sent packets. For only two different packet values, we introduce the account strategy and prove that this strategy achieves an optimal competitive ratio of ≈ 1.282, if the buffer size tends to infinity, and an optimal competitive ratio of (√13-1) 2 ≈ 1.303, for arbitrary buffer sizes. For general packet values, the simple preemptive greedy strategy (PG) is studied. We show that PG achieves a competitive ratio of √3 ≈ 1.732 which is the best known upper bound on the competitive ratio of this problem. In addition, we give a lower bound of of 1+1 √2 ≈ 1.707 on the competitive ratio of PG which improves the previously known lower bound. As a consequence, the competitive ratio of PG cannot be further improved significantly. There has been extensive work on network architectures that support multi-path routing to improve performance in wireless mesh networks. However, previous work uses ad-hoc design principles that cannot guarantee any network-wide performance objectives such as conjointly maximizing resource utilization and improving fairness. In parallel, numerous theoretical results have addressed the issue of optimizing a combined metric of network utilization and fairness using techniques based on back-pressure scheduling, routing and flow control. However, the proposed theoretical algorithms are extremely difficult to implement in practice, especially in the presence of the 802.11 MAC and TCP. We propose Horizon, a novel system design for multi-path forwarding in wireless meshes, based on the theoretical results on back-pressure. Our design works with an unmodified TCP stack and on top of the existing 802.11 MAC. We modified the back-pressure approach to obtain a simple 802.11-compatible packet-forwarding heuristic and a novel, light-weight path estimator, while maintaining global optimality properties. We propose a delayed reordering algorithm that eliminates TCP timeouts while keeping TCP packet reordering to a minimum. We have evaluated our implementation on a 22-node testbed. We have shown that Horizon effectively utilizes available resources (disjoint paths). In contrast to previous work, our design not only avoids bottlenecks but also optimally load-balances traffic across them when needed, improving fairness among competing flows. To our knowledge, Horizon is the first practical wireless system based on back-pressure. Since many Internet applications employ a multitier architecture, in this article, we focus on the problem of analytically modeling the behavior of such applications. We present a model based on a network of queues where the queues represent different tiers of the application. Our model is sufficiently general to capture (i) the behavior of tiers with significantly different performance characteristics and (ii) application idiosyncrasies such as session-based workloads, tier replication, load imbalances across replicas, and caching at intermediate tiers. We validate our model using real multitier applications running on a Linux server cluster. Our experiments indicate that our model faithfully captures the performance of these applications for a number of workloads and configurations. Furthermore, our model successfully handles a comprehensive range of resource utilization---from 0 to near saturation for the CPU---for two separate tiers. For a variety of scenarios, including those with caching at one of the application tiers, the average response times predicted by our model were within the 95p confidence intervals of the observed average response times. Our experiments also demonstrate the utility of the model for dynamic capacity provisioning, performance prediction, bottleneck identification, and session policing. In one scenario, where the request arrival rate increased from less than 1500 to nearly 4200 requests minute, a dynamic provisioning technique employing our model was able to maintain response time targets by increasing the capacity of two of the tiers by factors of 2 and 3.5, respectively. We provide analytical models for capacity evaluation of an infrastructure IEEE 802.11 based network carrying TCP controlled file downloads or full-duplex packet telephone calls. In each case the analytical models utilize the attempt probabilities from a well known fixed-point based saturation analysis. For TCP controlled file downloads, following (In Networking '04, LNCS 2042, pp.?626---637), we model the number of wireless stations (STAs) with ACKs as a Markov renewal process embedded at packet success instants. In our work, analysis of the evolution between the embedded instants is done by using saturation analysis to provide state dependent attempt probabilities. We show that in spite of its simplicity, our model works well, by comparing various simulated quantities, such as collision probability, with values predicted from our model. Next we consider N constant bit rate VoIP calls terminating at N STAs. We model the number of STAs that have an up-link voice packet as a Markov renewal process embedded at so called channel slot boundaries. Analysis of the evolution over a channel slot is done using saturation analysis as before. We find that again the AP is the bottleneck, and the system can support (in the sense of a bound on the probability of delay exceeding a given value) a number of calls less than that at which the arrival rate into the AP exceeds the average service rate applied to the AP. Finally, we extend the analytical model for VoIP calls to determine the call capacity of an 802.11b WLAN in a situation where VoIP calls originate from two different types of coders. We consider N 1 calls originating from Type 1 codecs and N 2 calls originating from Type 2 codecs. For G711 and G729 voice coders, we show that the analytical model again provides accurate results in comparison with simulations.