Search

Modern content delivery networks (CDNs) allow their customers (i.e., operators of web services) to customize the processing of requests by uploading and executing code at the edges of the CDN's network. To achieve scale, CDNs have forgone heavyweight virtualization techniques. Instead, all requests often execute within the same OS or even process. However, performance interference may arise when these requests have differing demands on multiple system resources. In this paper, we study the sources of performance interference based on workloads from real customers, identify the lack of multi-resource fairness as the culprit, and show that existing schedulers available in commodity OSs are insufficient to enforce fairness between customers. We then design Sandpaper, a new and practical multi-resource request scheduler for mitigating performance interference in CDN edge environments. Sandpaper enforces fairness despite constraints, such as sitting within the application runtime and running atop the OS's underlying resource schedulers. By leveraging key insights about the differences between theoretical system models and real systems, Sandpaper bridges the trade-off between resource utilization and multi-resource fairness that plagues existing schedulers. We implement Sandpaper atop Varnish, an open-source CDN edge proxy, and show that it mitigates performance interference while maintaining high resource utilization and with little performance overhead.

Multi-tenant datacenters and cloud networks must provide both isolation and interactive service to tenant applications, many of which are sensitive to tail flow completion times. Network operators must also ensure high utilization of network capacity to reduce cost. Existing approaches that statically partition network capacity, in either time or space, provide good isolation but suffer from under-utilization. Existing schemes that dynamically allocate capacity to tenants incur either decreased fairness or high tail flow completion times. To overcome these limitations, we propose Ether. Ether is able to overcome these limitations because it can prioritize bursty flows during short congestion episodes while still ensuring fairness at long timescales. In this paper, we present a preliminary design of Ether and discuss its feasibility in today's programmable switches. Our evaluations show that, at high loads, Ether achieves 23% improvement in tail flow completion times (FCT) when compared with idealized fair queueing (FQ) while still providing similar fairness as FQ. In contrast, pFabric, which optimizes FCT, worsens fairness by a factor of 1.8 when compared with Ether.

Fair queuing (FQ) algorithms have been widely adopted in computer systems to share resources among multiple users. Modern operating systems and hypervisors use variants of FQ algorithms to implement the critical OS resource management -- the thread scheduler. While the existing FQ algorithms enforce fair CPU allocation on a per-core basis, there lacks an algorithm to fairly allocate CPU on multiple cores. This common deficiency in state-of-the-art multicore schedulers causes unfair CPU allocations to parallel programs using blocking synchronization, leading to severe performance degradation. Parallel threads that frequently block due to synchronization exhibit deceptive idleness and are penalized by the thread scheduler. To this end, we propose a preemptive multi-queue fair queuing (P-MQFQ) algorithm that uses a centralized queue to fairly dispatch threads from different programs based on their received CPU bandwidth from multiple cores. We demonstrate that P-MQFQ can be approximated by augmenting the existing load balancing in the OS without requiring to implement the centralized queue or undermining scalability. We implement P-MQFQ in Linux and Xen, respectively, and show significantly improved utilization and performance for parallel programs.

With the emergence of increasingly heterogeneous devices and networks, computing systems are required to support a variety of services with different quality of service requirements. The degree of heterogeneity makes it more difficult to fairly allocate resources based on the client's weight. Moreover, as the systems become larger, their performance can worsen significantly. In this paper, we present a fair scheduling algorithm for multiprocessor systems using a task satisfaction index. The proposed algorithm, called LZF, aims to achieve a high level of proportional fairness for the heterogeneous tasks. The evaluation results show that its service time error is bounded between -1 and 1, and the LZF achieves the best proportional fairness among existing scheduling algorithms with respect to the average service time error.

Virtual machines frequently have various demands of storage I/O and priority. They are desired to operated several services simultaneously in the same system. However, we cannot assure that some virtual machine which required higher I/O bandwidth will gain proper resources. Moreover, existing fair queueing I/O schedulers cannot provide efficient disk resource allocation, which often leads to bottlenecks at a storage level. To solve the upper described problems, we propose AIO, an Adaptive I/O Bandwidth Allocation for Virtualization Environment on Xen platform. We designed AIO by adopted the concept of the traffic policing and shaping to support the bandwidth sharing between virtual machines and ensuring the Quality of Service of disk I/O resource. This framework allows us to allocate disk I/O bandwidth among the groups of virtual domains dynamically according to configuration rate and priority of particular resource classes. Experiments results show that AIO is useful in maintaining the disk I/O bandwidth of the virtual domain and slightly improves the I/O performance of the system.

In this paper, we address the performance analysis of the cooperative communication networks with data packet and energy packet independent arrival but interactive departure which can be profiled as a Coupled Processor Queuing Model. The joint data packet and energy packet assigning problem can achieve its steady state transition probability by Quasi-Birth and Death method and the expressions of throughput, delay and packet drop rate for both data queue and energy queue are also derived. Simulations are demonstrated to verify the accuracy of theoretical derivation results.

We wish to allocate outgoing bandwidth at a server among customer VMs. The allocation for each VM is proportional to the bandwidth purchased for that VM by the customer, while allowing idle bandwidth to redistributed. Classical fair queuing in routers assumes tight feedback between transmitter and scheduler, and that cheap scheduler invocation on every transmission. Since these assumptions are false in Virtual Switches, we propose MBFQ (Measurement Based Fair Queuing) with two levels of scheduling: a microscheduler that operates cheaply and paces VM transmissions, and a macroscheduler that periodically redistributes tokens to microschedulers based on the measured bandwidth of VMs. We show that MBFQ allows a VM to obtain its allocated bandwidth in X scheduling intervals, and that idle bandwidth is reclaimed within Y periods. An implementation of MBFQ is available in Windows Server 2016 Technical Preview.

In many important cloud services, different tenants execute their requests in the thread pool of the same process, requiring fair sharing of resources. However, using fair queue schedulers to provide fairness in this context is difficult because of high execution concurrency, and because request costs are unknown and have high variance. Using fair schedulers like WFQ and WF²Q in such settings leads to bursty schedules, where large requests block small ones for long periods of time. In this paper, we propose Two-Dimensional Fair Queueing (2DFQ), which spreads requests of different costs across di erent threads and minimizes the impact of tenants with unpredictable requests. In evaluation on production workloads from Azure Storage, a large-scale cloud system at Microsoft, we show that 2DFQ reduces the burstiness of service by 1-2 orders of magnitude. On workloads where many large requests compete with small ones, 2DFQ improves 99th percentile latencies by up to 2 orders of magnitude.

Although traditional CPU scheduling efficiently utilizes multiple cores with equal computing capacity, the advent of multicores with diverse capabilities pose challenges to CPU scheduling. For the multi-cores with uneven computing capability, scheduling is essential to exploit the efficiency of core asymmetry, by matching each application with the best core type. However, in addition to the efficiency, an important aspect of CPU scheduling is fairness in CPU provisioning. Such uneven core capability is inherently unfair to threads and causes performance variance, as applications running on fast cores receive higher capability than applications on slow cores. Depending on co-running applications and scheduling decisions, the performance of an application may vary significantly. This study investigates the fairness problem in multi-cores with uneven capability, and explores the design space of OS schedulers supporting multiple fairness constraints. In this paper, we consider two fairness-oriented constraints, minimum fairness for the minimum guaranteed performance and uniformity for performance variation reduction. This study proposes three scheduling policies which guarantee a minimum performance bound while improving the overall throughput and reducing performance variation too. The three proposed fairness-oriented schedulers are implemented for the Linux kernel with an online application monitoring technique. Using an emulated asymmetric multi-core with frequency scaling and a real asymmetric multi-core with the big.LITTLE architecture, the paper shows that the proposed schedulers can effectively support the specified fairness while improving overall system throughput.

Using the protocol IEEE 802.11, multi-hop wireless ad hoc networks yield only a poor performance, especially in throughput and fairness. When the offered load becomes large, i.e. the system is in saturation state, long-distance flows suffer a high degree of throughput deterioration. These problems not only come from medium contention at the MAC layer but are due to the link layer. In this paper, we propose a method to solve the throughput degradation and unfairness problem by providing fair treatment between flows at the link-layer. In our proposed method, a fair scheduling algorithm using round robin queue and the estimation for the average interval of packet enqueueing is applied to alleviate the unfairness problem at both MAC layer and link layer. The simulation results reveal that our proposed method is able to achieve better throughput and fairness compared to the standard IEEE 802.11.

We introduce split-level I/O scheduling, a new framework that splits I/O scheduling logic across handlers at three layers of the storage stack: block, system call, and page cache. We demonstrate that traditional block-level I/O schedulers are unable to meet throughput, latency, and isolation goals. By utilizing the split-level framework, we build a variety of novel schedulers to readily achieve these goals: our Actually Fair Queuing scheduler reduces priority-misallocation by 28x; our Split-Deadline scheduler reduces tail latencies by 4x; our Split-Token scheduler reduces sensitivity to interference by 6x. We show that the framework is general and operates correctly with disparate file systems (ext4 and XFS). Finally, we demonstrate that split-level scheduling serves as a useful foundation for databases (SQLite and PostgreSQL), hypervisors (QEMU), and distributed file systems (HDFS), delivering improved isolation and performance in these important application scenarios.

Multimedia services are carried by data packet in LTE (Long Term Evolution, LTE) system, such as voice, video, and so on. Quality of Service in multimedia services is essential to user experience. In this paper, we present a packet scheduling algorithm to improve the performance of video traffic. By considering the number of packet loss and packet delay in the buffer, the priority of each user can be adjusted dynamically to reduce the packet loss rate and maximize system throughput. The results show that compared with the current typical packet scheduling algorithm, the proposed algorithm can significantly improve the packet loss rate, fairness, throughput and other performance.

Middleboxes are widely deployed in today's networks. They apply a variety of complex network functions to transform, filter, and optimize incoming traffic based on the payload of packets. These functions require the support of multiple types of resources, such as CPU and link bandwidth, for processing incoming packets. Hence, a multi-resource packet scheduling algorithm is needed to allow flows to share these resources fairly and efficiently. However, unlike traditional fair queueing where bandwidth is the only concern, we show in this paper that fairness and efficiency are conflicting objectives that cannot be achieved simultaneously in the presence of multiple resources. Ideally, a scheduling algorithm should allow network operators to flexibly specify their fairness and efficiency requirements, so as to meet the Quality of Service demands while keeping the system at a high utilization level. Yet, existing multi-resource scheduling algorithms focus on fairness only, and may lead to poor resource utilization. In this paper, we propose a new scheduling algorithm to achieve a flexible tradeoff between fairness and efficiency for packet processing, consuming both CPU and link bandwidth. Experimental results based on both real-world implementation and trace-driven simulation suggest that trading off a modest level of fairness can potentially improve the efficiency to the point where the system capacity is almost saturated.

The Bufferbloat project was founded three and half years ago to explore solutions to why modern data networks became so slow when loaded. We set out to explore the literature, and code, from the earliest days of the Internet to today, to try and find out what had gone wrong, and to find ways to fix it. A result of that effort (so far!) has been a renaissance in interest in congestion control, and huge - orders of magnitude - improvements in network latency along the edge of the Internet, with deployable new algorithms and code. Surprisingly, we also made large improvements in simultaneous bidirectional goodput on asymmetric networks. This talk goes into the history and future of Active Queue Management (AQM) and fair queuing algorithms, touches upon current work across the field and tries to identify useful techniques for exploring and designing future work that can scale.

Now that our smartphones have multiple interfaces (WiFi, 3G, 4G, etc.), we have preferences for which interfaces an application may use. We may prefer to stream video over WiFi because it is fast, but VoIP over 3G because it gives continued connectivity. We also have relative preferences, such as giving Netflix twice as much capacity as Dropbox. This means our mobile devices need to schedule packets in keeping with our preferences while making use of all the capacity available. This is the natural domain of fair queuing, and this paper is about the design of a packet scheduler to meet these requirements. We show that traditional fair queueing schedulers cannot take into account a user's preferences for some interfaces over others. We present a novel packet scheduler called miDRR that meets our needs by generalizing DRR for multiple interfaces. We demonstrate a prototype running in Linux and show that it works correctly and can easily run at the speeds we need.

This paper describes a new approach to end-to-end congestion control on a multi-user network. Rather than manually formulate each endpoint's reaction to congestion signals, as in traditional protocols, we developed a program called Remy that generates congestion-control algorithms to run at the endpoints. In this approach, the protocol designer specifies their prior knowledge or assumptions about the network and an objective that the algorithm will try to achieve, e.g., high throughput and low queueing delay. Remy then produces a distributed algorithm---the control rules for the independent endpoints---that tries to achieve this objective. In simulations with ns-2, Remy-generated algorithms outperformed human-designed end-to-end techniques, including TCP Cubic, Compound, and Vegas. In many cases, Remy's algorithms also outperformed methods that require intrusive in-network changes, including XCP and Cubic-over-sfqCoDel (stochastic fair queueing with CoDel for active queue management). Remy can generate algorithms both for networks where some parameters are known tightly a priori , e.g. datacenters, and for networks where prior knowledge is less precise, such as cellular networks. We characterize the sensitivity of the resulting performance to the specificity of the prior knowledge, and the consequences when real-world conditions contradict the assumptions supplied at design-time.

Scarcity of bandwidth for fixed allocation of frequency and also current growth trends in wireless communications shows that Cognitive Radio Networks (CRNs) are followed strictly. Fluctuating nature of the radio spectrum with a variety of quality services which needs causes some challenges in CRNs, such as spectrum sharing. In many previous works, the problem of performance loss is seen due to the sudden presence of primary user. In such a situation, secondary user has to vacate bandwidth at the moment. This often leads to long wait for secondary user on access the channel. However, Spectrum Pooling concept is used with the ability of secondary utility for licensed frequency band, without reducing quality of service and without requiring new hardware. In this paper, a fair queuing algorithm with weighting and prioritization between different users is recommended. This type of queuing model with weighted fair queuing policy is efficient to share the bandwidth among systems with different priority levels. The proposed algorithm offers shared use of spectrum to invest a fair sharing of bandwidth between cognitive users. The proposed model involves a different service rates for unlicensed users and can be used as an acceptable model in heterogeneous networks. By the use of analytical and simulation results, we can achieve a desirable level of performance and an improvement in fairness.

Middleboxes are ubiquitous in today's networks and perform a variety of important functions, including IDS, VPN, firewalling, and WAN optimization. These functions differ vastly in their requirements for hardware resources (e.g., CPU cycles and memory bandwidth). Thus, depending on the functions they go through, different flows can consume different amounts of a middlebox's resources. While there is much literature on weighted fair sharing of link bandwidth to isolate flows, it is unclear how to schedule multiple resources in a middlebox to achieve similar guarantees. In this paper, we analyze several natural packet scheduling algorithms for multiple resources and show that they have undesirable properties. We propose a new algorithm, Dominant Resource Fair Queuing (DRFQ), that retains the attractive properties that fair sharing provides for one resource. In doing so, we generalize the concept of virtual time in classical fair queuing to multi-resource settings. The resulting algorithm is also applicable in other contexts where several resources need to be multiplexed in the time domain.

We consider protocols that serve communication requests arising over time in a wireless network that is subject to interference. Unlike previous approaches, we take the geometry of the network and power control into account, both allowing to increase the network's performance significantly. We introduce a stochastic and an adversarial model to bound the packet injection. Although taken as the primary motivation, this approach is not only suitable for models based on the signal-to-interference-plus-noise ratio (SINR). It also covers virtually all other common interference models, for example the multiple-access channel, the radio-network model, the protocol model, and distance-2 matching. Packet-routing networks allowing each edge or each node to transmit or receive one packet at a time can be modeled as well. Starting from algorithms for the respective scheduling problem with static transmission requests, we build distributed stable protocols. This is more involved than in previous, similar approaches because the algorithms we consider do not necessarily scale linearly when scaling the input instance. We can guarantee a throughput that is as large as the one of the original static algorithm. In particular, for SINR models the competitive ratios of the protocol in comparison to optimal ones in the respective model are between constant and O(log^2 m) for a network of size m., Comment: 23 pages

Denial of service protection mechanisms usually require classifying malicious traffic, which can be difficult. Another approach is to price scarce resources. However, while congestion pricing has been suggested as a way to combat DoS attacks, it has not been shown quantitatively how much damage a malicious player could cause to the utility of benign participants. In this paper, we quantify the protection that congestion pricing affords against DoS attacks, even for powerful attackers that can control their packets' routes. Specifically, we model the limits on the resources available to the attackers in three different ways and, in each case, quantify the maximum amount of damage they can cause as a function of their resource bounds. In addition, we show that congestion pricing is provably superior to fair queueing in attack resilience.

Fair queueing algorithms based on Generalized Processor Sharing (GPS) provide sessions with instantaneous fair sharing of server capacity, as well as guaranteed service rate and delay. The instantaneous fair sharing distributes server capacity to currently back-logged sessions in proportion to their weights regardless of the amount of service that the sessions received in the past. From a long-term perspective, however, this type of sharing leads to a different quality of service to sessions even if they have the same weight, since it provides only the instantaneous capacity sharing without considering the accumulated service delay and bandwidth. To minimize such long-term unfairness, we propose a delay and bandwidth normalized scheduling model in which the concept of Value of Service (VoS) is defined from the aspects of both delay and bandwidth. Performance comparisons between the proposed algorithm and traditional fair queueing algorithms show that the proposed algorithm provides better long-term fairness among sessions and is more adaptive to sessions with dynamic traffic patterns without compromising the guarantees of service rate and delay.

Since the utilization of multiuser diversity in wireless networks can increase the information theoretic capacity, much attention has been paid to schedulers exploiting multiuser diversity. It is known that there exists a tradeoff between the capacity and fairness achieved by schedulers exploiting multiuser diversity. Due to its good balance between the capacity and fairness, the one-bit feedback fair scheduler is considered as an attractive choice. The fairness is classified into short term fairness and long term fairness. It is known that the one-bit feedback fair scheduler has an ideal long term fairness property. However, the short term fairness properties of the scheduler have not been sufficiently explored yet. Since packet level performances of individual MSs (Mobile Stations) are strongly affected by short term fairness, it is also important to examine the short term fairness of the schedulers. In this paper, we focus on the short term fairness of the one-bit feedback fair scheduler. As a short term fairness index, we consider the statistical time-access fairness index (STAFI). We then develop two numerical methods to understand the transient properties of the STAFI of the one-bit feedback fair scheduler. The first method calculates the exact value of the STAFI by using the inverse discrete FFT method. The second method estimates the asymptotic decay rate of the STAFI by using the theory of large deviations.

Multi-core architectures are commonly used for network applications because the workload is highly parallelizable. Packet scheduling is a critical performance component of these applications and significantly impacts how well they scale. Deep packet inspection (DPI) applications are more complex than most network applications. This makes packet scheduling more difficult, but it can have a larger impact on performance. Also, packet latency and ordering requirements differ depending on whether the DPI application is deployed inline. Therefore, different packet scheduling tradeoffs can be made based on the deployment. In this paper, we evaluate three packet scheduling algorithms with the Protocol Analysis Module (PAM) as our DPI application using network traces acquired from production networks where intrusion prevention systems (IPS) are deployed. One of the packet scheduling algorithms we evaluate is commonly used in production applications; thus, it is useful for comparison. The other two are of our own design. Our results show that packet scheduling based on cache affinity is more important than trying to balance packets. More specifically, for the three network traces we tested, our cache affinity packet scheduler outperformed the other two schedulers increasing throughput by as much as 38%.

The time-constraint data traffic is very common in vehicle-to-infrastructure (V2I) and vehicle-to-vehicle (V2V) communications. Time-constraint flows are those who have fixed start and stop times and try to maximize the transferred data volume during the limited connection time. From the view of users, the total data transmitted by each flow should be proportional to each one's holding time if the network resources are allocated fairly. However, we find that the traditional fairness concept solely based on flow rates is not suitable for this scenario. Therefore, we redefine the fairness concept regarding the application utility for time-constraint flows. According to this utility-based fairness definition, we propose a new practical bandwidth sharing scheme using TCP parameter tuning for transferring data with fast-moving wireless nodes such as vehicles. Simulations through ns-2 show that the proposed algorithm can achieve better utility fairness than the standard TCP and it is also friendly to TCP in the long term.

Fourth Generation broadband wireless technologies such as WiMAX and LTE depend heavily in the performance of their schedulers to deliver high data throughput and meet quality-of-service commitments. This paper compares four different proposed schedulers for mobile WiMAX (Proportional Fairness (PF), Multiclass Modified Largest Weighted Delay First (MLWDF), Highest Urgency First (HUF), and Weighted Fair Queuing (WFQ) )in a range of environments. The evaluation is based on five industry-defined key performance indicators: average sector throughput, application throughput, average completion time, fairness index and delay). The schedulers are evaluated under three simulated environments: controlled (with a detailed analysis of each algorithm's behavior in terms of throughput over time), stationary and mobile. The controlled environment provides interesting insights about the behavior of flows with identical QoS parameters and different RF conditions, and helps to validate subsequent results obtained in the other two environments. Our results for the stationary and mobile environments show that all algorithms meet quality-of-service requirements within system capacity. Algorithms that maximize spectral efficiency (PF and MLWDF) also achieved considerable throughput improvements. MLWDF's throughput results, while outperforming all other schedulers under stationary conditions, fall behind PF in the mobile scenario. The variability introduced by the mobile environment yields no statistically significant difference among the schedulers.

As organizations start to use data-intensive cluster computing systems like Hadoop and Dryad for more applications, there is a growing need to share clusters between users. However, there is a conflict between fairness in scheduling and data locality (placing tasks on nodes that contain their input data). We illustrate this problem through our experience designing a fair scheduler for a 600-node Hadoop cluster at Facebook. To address the conflict between locality and fairness, we propose a simple algorithm called delay scheduling: when the job that should be scheduled next according to fairness cannot launch a local task, it waits for a small amount of time, letting other jobs launch tasks instead. We find that delay scheduling achieves nearly optimal data locality in a variety of workloads and can increase throughput by up to 2x while preserving fairness. In addition, the simplicity of delay scheduling makes it applicable under a wide variety of scheduling policies beyond fair sharing.

The self-similar network traffic influence on the telecommunication queuing systems with infinite and finite buffer sizes in terms of the average queuing size and buffer overflow probability is investigated in this paper. The obtained results show that the average queue length and overflow probability of queuing systems with self-similar input traffic are much higher than the classical queuing systems. The investigated parameters are much higher, when the degrees of self-similarity (Hurst parameter) increase. The results confirm that self-similar traffic has serious implication on telecommunication network queuing.

In this paper, we investigate the use of a size-based scheduling policy, LASTOTAL, inWLANs. A size-based scheduling policy is a priority policy where the priority of a flow is based on its size. LASTOTAL replaces the legacy IP level FIFO scheduler at the access point. The lower protocol layers, and especially the MAC 802.11 layer are left unchanged. We demonstrate using realistic synthetic workloads, that LAS-TOTAL solves the unfairness issue due to DCF in 802.11 WLANs and ensures small response times to the majority of the flows under any load conditions. The latter property is desirable as short flows correspond to interactive applications and maintaining low response times for those flows despite load variations, significantly improves user experience. We also introduce and validate Markovian queuing models to assess the response time of the access point for both FIFO and LASTOTAL.

In this paper the fairness of the subchannel allocation problem for relay based OFDMA systems is studied. The proportional fairness algorithm is extended to a two-hop scenario to ensure that both direct-link users and relay-link users are fairly allocated capacity; this approach is called the "two-hop proportional fairness scheduling algorithm". The fairness allocation problem is considered both in the first time subslot between direct-link users and relay stations, and the second time subslot among relay-link users. Simulation results show that this algorithm achieves an overwhelming performance on the long-term fairness of the user data rate, although suffering some throughput reduction.

In a shared server infrastructure, a scheduler controls how quantities of resources are shared over time in a fair manner across multiple, competing consumers. It should support wide (parallel) requests for variable-sized pool of resources, provide assurance of minimum resource allotment on demand, and give predictable assignments. Our approach integrates a fair queuing algorithm with a calendar scheduler. We present WINKS, a proportional share allocation policy that addresses the needs of shared server environments. It extends start-time fair queuing to support wide requests with backfill, advance reservations, dynamic cluster sizing, dynamic request sizing, and intra-flow request prioritization. It also preserves fairness properties across queue transformations and calendar operations needed to implement these extensions.

All-optical packet switching is a promising candidate for future high-speed switching. However, due to the absence of optical Ran-dom Access Memory, the traditional Virtual Output Queue (VOQ) based input-queued switches are difficult to implement in optical domain. In this paper we consider output-buffered optical packet switches. We focus on packet scheduling in an output-buffered optical packet switch with limited-range wavelength conversion, aiming at maximizing throughput and minimizing average queuing delay simultaneously. We show that it can be converted to a minimum cost maximum network flow problem. To cope with the high complexity of general network flow algorithms, we further present a new algorithm that can determine an optimal scheduling in O (min {W2,BW}) time, where W is the number of wave-length channels in each fiber and B is the length of the output buffer. We also conduct simulations to test the performance of the proposed scheduling algorithm under different traffic models.

It is well known that competition between 802.11 wireless flows can lead to severe unfairness problems. In this paper we show that certain flows can be denied from their fair share of network access for long periods of time due toinequitable channel conditions. We argue that this unfairness problem is likely to get worse as the use of wireless in terms of number of devices and bandwidth continues to grow. To address unfairness, we rely on a common network management technique called traffic shaping. Instead of designing new MAC protocols or introducing complex wireless fair queuing or adaptation algorithms, we argue that 802.11, TCP and a well-understood wired fair queuing scheme can provide fairness even in unfavourable network topologies as long as we can prevent MAC-layer congestion from happening. This shaping approach has the advantage of being easily deployed in existing network management systems, requiring no change to the end-user devices or access points. We have proven the effectiveness of this cross-layer approach using a wireless testbed, and are currently in the process of incorporating this scheme into a large-scale campus wireless network.

In this paper, we study the joint spectrum allocation and scheduling problems with the objectives of maximizing through-put and achieving certain fairness in Dynamic Spectrum Access (DSA) wireless networks. A novel Multi-Channel Contention Graph (MCCG) is proposed to characterize the impact of interference under the protocol interference model. Based on MCCG, we present an optimal scheme to compute maximum throughput solutions. As simply maximizing throughput may result in a severe bias on resource allocation, we take fairness into consideration by presenting optimal schemes to compute fair solutions based on a simplified max-min fairness model and the well-known proportional fairness model. Fast and effective heuristics are also proposed to provide high throughput and fair solutions. Numerical results show that compared with the optimal schemes, our heuristic schemes produce very close performance and our proportional fair schemes achieve a good tradeoff between throughput and fairness. In addition, we extend our research to the physical interference model.

The IEEE 802.16 standard has been promoted by the WiMAX (Worldwide Interoperability for Microwave Access) forum as a leading wireless broadband access technology. The packet scheduling mechanism represents the core of WiMAX QoS architecture; however, each vendor needs to design its own algorithm to offer effective quality provisioning to the end user. This paper reports on the design and analysis of a channel-aware WF2Q+ based scheduling algorithm for downlink traffic delivery in a point-to-multipoint WiMAX network. A technique for compensation of channel errors is proposed to preserve QoS and fairness of the scheduling algorithm when working under non-ideal channel conditions. Simulation analysis confirms the effectiveness of the compensation mechanism under different channel conditions, network load, and traffic characteristics.

Grid systems are highly variable environments, made of a series of independent organizations that share their resources, creating what is known as virtual organization, VO. This variability makes quality of service (QoS) highly desirable, though it is very complex to achieve due to the large scale of interconnected networks. Entities entrusted with the care of the users' interests in a Grid, are known as meta-schedulers or Grid Schedulers [2] [1]. These entities usually take into account the power of computing resources in order to decide which resource will run an user's job, but do not pay attention to the interconnecting network. The provision of network QoS in a Grid environment is the topic of interest of this work, and what we want to do is to develop a meta-scheduler that pays attention to the network when making decisions. This new entity, known as grid network broker, GNB, will be developed at first using a simulation tool. The simulation tool that we have chosen is GridSim [5], because it provides us with a good infrastructure, including an implementation of Differentiated Services [3]. The implementation of differentiated services in GridSim is the Self Clocked Fair Queueing (SCFQ) scheduler [4]. A SCFQ scheduler can provide differentiated service to traffic by changing the weights associated with a certain class of traffic. The higher the weight of a class of traffic is, the better treatment it receives.Our aim is firstly develop our GNB on a simulator and, when our model is tested, we will proceed with its implementation on a real grid environment.

Low throughput due to unfairness is a key problem in multi-rate wireless local area networks. To promote fairness and hence throughput, T2-Fair groups flows according to their average data rate, provides each group fair time allocations and ensures throughput fairness for flows in each group. Since each group is allocated transmission times fairly, T2-Fair isolates high and low rate groups and prevents system capacity from being degraded by low rate flows. We have derived T2-Fair's performance bounds analytically and investigated its performance using the ns-2 simulator in various scenarios with a mix of high and low rate flows. Our results show that T2-Fair is effective in isolating and providing proportional throughput fairness to these flows.

Most common network protocols transmit variable size packets, whereas contemporary switches still operate with fixed- size cells, which are easier to transmit and buffer. This necessitates packet segmentation and reassembly modules, resulting in significant computation and communication overhead that might be too costly as switches become faster and bigger. It is, therefore, imperative to investigate an alternative mode of scheduling in which packets are scheduled contiguously over the switch fabric. This paper investigates the cost of packet-mode scheduling for the combined input-output-queued (CIOQ) switch architecture. We devise frame-based schedulers that allow a packet-mode CIOQ switch with small speedup to mimic an ideal output-queued switch, with bounded relative queuing delay. The schedulers are pipelined and based on matrix decomposition. Our schedulers demonstrate a trade-off between the switch speedup and the relative queuing delay incurred while mimicking an output-queued switch. When the switch is allowed to incur high relative queuing delay, a speedup arbitrarily close to two suffices to mimic an ideal output-queued switch. This implies that packet-mode scheduling does not require higher speedup than a cell-based scheduler. The relative queuing delay can be significantly reduced with just a doubling of the speedup. We further show that it is impossible to achieve zero relative queuing delay (that is, a perfect emulation), regardless of the switch speedup. In addition, simpler algorithms can mimic an output-queued switch with a bounded buffer size, using speedup arbitrarily close to one. Simulations confirm that packet-mode emulation with reasonable relative queuing delay can be achieved with moderate speedup. Furthermore, a simple and practical heuristic is shown by simulations to also provide effective packet-mode emulation.

Packet processing systems maintain high throughput despite relatively high memory latencies by exploiting the coarse-grained parallelism available between packets. In particular, multiple processors are used to overlap the processing of multiple packets. Packet queuing-the fundamental mechanism enabling packet scheduling, differentiated services, and traffic isolation-requires a read-modify-write operation on a linked list data structure to enqueue and dequeue packets; this operation represents a potential serializing bottleneck. If all packets awaiting service are destined for different queues, these read-modify-write cycles can proceed in parallel. However, if all or many of the incoming packets are destined for the same queue, or for a small number of queues, then system throughput will be serialized by these sequential external memory operations. For this reason, low latency SRAMs are used to implement the queue data structures. This reduces the absolute cost of serialization but does not eliminate it; SRAM latencies determine system throughput.In this paper we observe that the worst-case scenario for packet queuing coincides with the best-case scenario for caches: i.e., when locality exists and the majority of packets are destined for a small number of queues. The main contribution of this work is the queuing cache, which consists of a hardware cache and a closely coupled queuing engine that implements queue operations. The queuing cache improves performance dramatically by moving the bottleneck from external memory onto the packet processor, where clock rates are higher and latencies are lower. We compare the queuing cache to a number of alternatives, specifically, SRAM controllers with: no queuing support, a software-controlled cache plus a queuing engine (like that used on Intel's IXP network processor), and a hardware cache. Relative to these models, we show that a queuing cache improves worst-case throughput by factors of 3.1, 1.5, and 2.1 and the throughput of real-world traffic traces by factors of 2.6, 1.3, and 1.75, respectively. We also show that the queuing cache decreases external memory bandwidth usage, on-chip communication, and the number of queuing instructions executed under best-case, worst-case and real-world traffic workloads. Based on our VHDL models, we conclude that a queuing cache could be implemented at a low cost relative to the resulting performance and efficiency benefits.

An enhanced flow-aware Internet is arguably a more effective means of ensuring adequate performance than implementing the complex standardized QoS architectures. This flow-aware network would provide flow-level performance guarantees for real time and data applications by implementing per-flow fair queueing and by limiting the impact of overload through flow level admission control. The paper discusses the feasibility of the implied router mechanisms and proposes original solutions that minimize the necessary overhead with respect to the current best effort network. Preferred solutions significantly reduce requirements for flow state by employing directly addressed bitmaps to record flow status, as necessary for scheduling and admission control, respectively.

This work aims at studying the fairness of multi-queue and multi-server queueing systems. We deal with the issues of queue-multiplicity, queue joining policy and queue jockeying and use a quantitative measure (RAQFM) to evaluate them. Our results yield the relative fairness of the mechanisms as a function of the system configuration and parameters. Practitioners can use these results to quantitatively account for system fairness and to weigh efficiency aspects versus fairness aspects in designing and controlling their queueing systems. In particular, we quantitatively demonstrate that: 1) Joining the shortest queue increases fairness, 2) A single "combined" queue system is more fair than "separate" (multi) queue system and 3) Jockeying from the head of a queue is more fair than jockeying from its tail.

We study a simple ingress policing scheme for a stochastic queuing network that uses a round-robin service discipline, and derive conditions under which the flow rates approach a max-min fair share allocation. The scheme works as follows: Whenever any of a flow's queues exceeds a policing threshold, the network discards that flow's arriving packets at the network ingress, and does so until all of that flow's queues fall below their thresholds. To prove our results, we use previously known results relating the stability of a queuing system to the stability of its fluid limit and extend these results to relate the flow rates of the stochastic system to those of a corresponding fluid model. In particular, we consider the fluid limit of a sequence of queuing networks with increasing thresholds. Using a Lyapunov function derived from the fluid limits, we find that as the policing thresholds are increased the state of the stochastic system is attracted to a relatively smaller and smaller neighborhood surrounding the equilibrium of the fluid model. We then show how this property implies that the achieved flow rates approach the max-min rates predicted by the fluid model.

Despite many years of research, fair queuing still faces a number of implementation challenges in high speed routers. In particular, in spite of proposals such as DiffServ, the state needs for even simple schedulers are still large for heavily channelized core routers and for edge routers. An earlier proposal, Stochastic Fair Queuing, reduces state but at the expense of added unfairness between certain flows. Another earlier scheme, Core Stateless Fair Queuing, requires header changes and does not address the state needs of edge routers. By contrast, our paper proposes a randomization technique that removes the need to store deficit counters per flow in Deficit Round Robin and its variants. Even without the counters, we show, using both analysis and simulation, that randomized technique preserves throughput fairness properties of DRR. This randomization technique introduced in this paper can be used to considerably reduce the state requirements of high speed schedulers in edge and core routers, making hardware designs feasible. The randomization idea in this paper can also be applied to other round robin schedulers as well as potentially in entirely different scenarios wherever deficits need to be tracked over time explicitly.

The Least Attained Service (LAS) scheduling policy, when used for scheduling packets over the bottleneck link of an Internet path, can greatly reduce the average flow time for short flows while not significantly increasing the average flow time for the long flows that share the same bottleneck. No modification of the packet headers is required to implement the simple LAS policy. However, previous work has also shown that a drawback of the LAS scheduler is that, when link utilization is greater than 70%, long flows experience large jitter in their packet transfer times as compared to the conventional First-Come-First-Serve (FCFS) link scheduling. This paper proposes and evaluates new differentiated LAS scheduling policies that reduce the jitter for long flows that are identified as "priority" flows.To evaluate the new policies, we develop analytic models to estimate average flow transfer time as a function of flow size, and average packet transmission time as a function of position in the flow, for the single-bottleneck "dumbbell topology" used in many ns simulation studies. Models are developed for FCFS scheduling, LAS scheduling, and each of the new differentiated LAS scheduling policies at the bottleneck link. Over a wide range of configu-rations, the analytic estimates agree very closely with the ns estimates. Thus, the analytic models can be used instead of simulation for comparing the policies with respect to mean flow transfer time (as a function of flow size) and mean packet transfer time. Furthermore, an initial discrepancy between the analytic and simulation estimates revealed errors in the parameter values that are often specified in the widely used ns Web workload generator. We develop an improved Web workload specification, which is used to estimate the packet jitter for long flows (more accurately than with previous simulation workloads).Results for the scheduling policies show that a particular policy, LAS-log, greatly improves the mean flow transfer time for priority long flows while providing performance similar to LAS for the ordinary flows. Simulations show that the LAS-log policy also greatly reduces the jitter in packet delivery times for the priority flows.

We investigate the fair bandwidth sharing among responsive and unresponsive traffic flows. When these flows compete for the same output link in a router, unresponsive flows tend to occupy more than their fair share of the link capacity. We propose a new active queue management algorithm named Random Early Detection with Dynamic Thresholds (RED-DT) that dynamically adapts queue parameters to achieve a more fair distribution of the link capacity.

Fair queuing is a well-studied problem in modern computer networks. However, there remains a gap between scheduling algorithms that have provably good performance, and those that are feasible and practical to implement in high speed routers. In this paper, we propose a novel packet scheduler called Stratified Round Robin, which has low complexity, and is amenable to a simple hardware implementation. Stratified Robin Robin exhibits good fairness and delay properties that are demonstrated through both analytical results and simulations. In particular, it provides a single packet delay bound that is independent of the number of flows. This property is unique to Stratified Round Robin among all other schedulers of comparable complexity.

For years, the conventional wisdom [7, 22] has been that the continued stability of the Internet depends on the widespread deployment of "socially responsible" congestion control. In this paper, we seek to answer the following fundamental question: If network end-points behaved in a selfish manner, would the stability of the Internet be endangered?.We evaluate the impact of greedy end-point behavior through a game-theoretic analysis of TCP. In this "TCP Game" each flowattempts to maximize the throughput it achieves by modifying its congestion control behavior. We use a combination of analysis and simulation to determine the Nash Equilibrium of this game. Our question then reduces to whether the network operates efficiently at these Nash equilibria.Our findings are twofold. First, in more traditional environments -- where end-points use TCP Reno-style loss recovery and routers use drop-tail queues -- the Nash Equilibria are reasonably efficient. However, when endpoints use more recent variations of TCP (e.g., SACK) and routers employ either RED or drop-tail queues, the Nash equilibria are very inefficient. This suggests that the Internet of the past could remain stable in the face of greedy end-user behavior, but the Internet of today is vulnerable to such behavior. Second, we find that restoring the efficiency of the Nash equilibria in these settings does not require heavy-weight packet scheduling techniques (e.g., Fair Queuing) but instead can be done with a very simple stateless mechanism based on CHOKe [21].

We discuss the relevance of fairness as a design objective for congestion control mechanisms in the Internet. Specifically, we consider a backbone network shared by a dynamic number of short-lived flows, and study the impact of bandwidth sharing on network performance. In particular, we prove that for a broad class of fair bandwidth allocations, the total number of flows in progress remains finite if the load of every link is less than one. We also show that provided the bandwidth allocation is "sufficiently" fair, performance is optimal in the sense that the throughput of the flows is mainly determined by their access rate. Neither property is guaranteed with unfair bandwidth allocations, when priority is given to one class of flow with respect to another. This suggests current proposals for a differentiated services Internet may lead to suboptimal utilization of network resources.

This paper discusses resource allocation and management in Differentia ted Services (DiffServ) networks, particularly in the context of IP telephony. We assume that each node uses Weighted Fair Queuing (WFQ) schedulers in order to provide Quality of Service (QoS) to aggregates of traffic. All voice traffic destined for a certain output interface is aggregated into a single queue. When a voice flow traverses a node, its packets are placed in this queue; which is drained at a certain rate, determined by a weight associated with that queue. This paper shows how to set this weight such that the edge-router-to-edge-router queuing delay in the DiffServ network is statistically bounded. The nodes are modeled as M/G/1 queuing systems and a heuristic formula is used to compute a quantile of the queuing delay. This formula is compared with results derived from simulations. It is also shown how to use this result to allocate the appropriate resources in a DiffServ network and how to update and process RSVP messages at the edge of a DiffServ network in an IntServ over DiffServ scenario.

The explosive increase in the volume and variety of Internet traffic has placed a growing emphasis on congestion control and fairness in Internet routers. Approaches to the problem of congestion, such as active queue management schemes like Random Early Detection (RED) use congestion avoidance techniques and are successful with TCP flows. Approaches to the problem of fairness, such as Fair Random Early Drop (FRED), keep per-flow state and punish misbehaved, non-TCP flows. Unfortunately, these punishment mechanisms also result in a significant performance drop for multimedia flows that use flow control. We extend Class-Based Threshold (CRT) [12], and propose a new active queue management mechanism as an extension to RED called Dynamic Class-Based Threshold (D- CBT) to improve multimedia performance on the Internet. Also, as an effort to reduce multimedia jitter, we propose a lightweight packet scheduling called Cut-In Packet Scheduling (ChIPS) as an alternative to FIFO packet scheduling. The performance of our proposed mechanisms is measured, analyzed and compared with other mechanisms (RED and CBT) in terms of throughput, fairness and multimedia jitter through simulation using NS. The study shows that D-CBT improves fairness among different classes of flows and ChIPS improves multimedia jitter without degrading fairness.