In data center networks (DCNs), incast traffic, primarily composed of small flows (S-Flows), faces congestion due to buffer bloating caused by large flows (L-Flows). Consequently, S-Flows experience inflated flow completion times (FCTs). This paper introduces R-CASH, a receiver-assisted class-aware active queue management (AQM) scheme that exploits in-switch hysteresis to address this issue. R-CASH relies on flow classification at the source host to differentiate S-Flows and L-Flows based on their size. While switches monitor queue lengths to determine congestion based on three hysteresis thresholds that divide the buffer into four zones, the state is encoded in two ToS bits on the packet header. Receivers decode this state and selectively clamp the receiver window (Rwnd) in the corresponding outgoing TCP ACKs to throttle L-Flows as necessary, thereby safeguarding S-Flows. R-CASH has been implemented in a small testbed and has demonstrated improved FCTs for S-Flows while maintaining sustained throughput for L-Flows compared to centralized AQMs.

In chunk-based interest-driven content-centric networks, each interest packet forwarded upstream by a node on a face implies the return of at most one data chunk to the node from that face shortly after. As a consequence, the congestion of the downstream transmission buffer in the data path of the node is highly correlated with the occupancy of the pending interest table (PIT). Therefore a systematic study and analysis of the PIT occupancy are of paramount importance to understanding congestion in CCN. In particular, in this paper, we propose an analytical model to estimate the PIT occupancy distribution via a continuous-time Markov chain (CTMC) model that considers the effects of interest blocking, interest timeout and retries. To validate our model and assumptions, we invoke simulation with realistic traffic streams and show how the filtering effects of caching and interest aggregation make the Markov assumption reasonable in the nodes that are the most susceptible to experiencing congestion. To solve the model numerically, we use two alternative approximations, state space truncation and state aggregation, and then give some numerical results to demonstrate the accuracy of our approximations.

In data-centers, the composite origin and bursty nature of traffic, the small bandwidth-delay product and the tiny switch buffers lead to unusual congestion patterns that are not handled well by traditional end-to-end congestion control mechanisms such as TCP. Existing works address the problem by modifying TCP to adapt it to the idiosyncrasies of data-centers. While this is feasible in private environments, it remains almost impossible to achieve practically in public multi-tenant clouds where a multitude of operating systems and thus congestion control protocols coexist. In this work, we design a simple switch-based active queue management scheme to deal with such congestion issues adequately. Our approach requires no modification to TCP which enables easy and seamless deployment in public data-centers via switch software/firmware updates. We present a simple analysis to show its stability and effectiveness, then discuss three different real implementations in software and hardware switches on the NetFPGA platform. Numerical results from NS-2 simulation and experimental results from a small testbed cluster demonstrate the effectiveness of our approach in achieving high overall throughput, good fairness, smaller flow completion times (FCT) for short-lived flows, and reduction in the tail of the FCT distribution by as much as two orders of magnitude.

In this paper we study the relationship between the TCP packet loss cycle and the performance of time-sensitive traffic in data centers. Using real traffic measurements and analysis, we find that such loss cycles are not long enough to enable most partition-aggregate time-sensitive TCP applications to recover their packet losses via the TCP 3-dup ACKs mechanism. As a result, the Timeout (RTO) mechanism is frequently triggered, leading to the expansion of the flow completion times (FCT) of such applications by orders of magnitude. Hence, we seek an alternative method that does not change the virtual machines and that can effectively expand the loss cycle duration to enable short flows to finish their transfer without incurring the cost of the RTO. To this end, we propose a novel TCP-AQM mechanism that alternates between a slow constant bitrate (CBR) mode and a fast TCP rate via hysteresis switching to expand the loss cycle. We prove the stability of the proposed TCP-AQM via a control theoretic model, then evaluate its performance gains via small and large scale NS2 simulation and by real FPGA implementation of a prototype on the NetFPGA platform. The results show considerable improvements in FCT distribution and reduction of missed deadlines in simulation and real experiments.

In vehicular networks, the benefits of jointly-optimizing data prefetching and caching with broadcast transmission scheduling and rate adaptation strategies at road-side units (RSUs) have already been demonstrated in the literature. Nevertheless, the effectiveness of the solution depends greatly on the accurate knowledge of vehicular trajectories. In practice, as specified in the standards, this is at odds with the important issue of privacy. One of the main contributions of this work is to address this issue by providing a scheme that jointly optimizes the throughput of broadcast-transmission scheduling from RSUs to vehicles, and the privacy of vehicles’ locations, by enabling them to disseminate obfuscated locations to the server from time to time. We formulate this problem as a reinforcement learning (RL) problem, where the vehicles learn when to report obfuscated locations, in order to maximize a utility that encompasses both the network capacity (related to vehicles’ throughput) and the level of privacy achieved. The proposed scheme is shown to consistently outperform alternative randomized schemes considered in past work, and in particular it proves to be robust against prediction errors of the future locations of the vehicles.

In information centric networking (ICN), by default, forwarder nodes along the paths from content producers to consumers, cache and reuse content chunks ubiquitously, invoking the Least Recently Used (LRU) replacement policy when needed. Due to the cache filtering effect, this ubiquitous-LRU strategy is inefficient: popular contents that are cached a few hops away from the edge are of little utility. Most alternative proposals adopt unified on-path schemes that rely on popularity statistics or other global state information to improve the performance. In the Internet, it is difficult to imagine different administrative-entities exposing such information to each other, and so we argue that such schemes are not realistic; and secondly, a unified caching scheme across the network ignores the administrative autonomy, which is one of the tenets of the Internet. In this paper we argue for a two-tiered caching scheme that maintains an on-path caching scheme (e.g., Ubiquitous-LRU), yet embraces AS-autonomy by adding within the AS an off-path cooperative-caching and redundancy elimination, to make better use of caches in the edge where they are most valuable. We describe the implementation of our scheme and highlight the design choices to make the system practical. Our evaluation results show that our scheme can reduce cache misses and upstream traffic by up to 15% compared to the state-of-the-art.

Cloud interactive data-driven applications generate swarms of small TCP flows that compete for the small switch buffer space in data-center. Such applications require a small flow completion time (FCT) to be effective. Unfortunately, TCP is myopic with respect to the composite nature of application data. In addition it tends to artificially inflate the FCT of individual flows by several orders of magnitude, because of its Internet-centric design, that fixes the retransmission timeout (RTO) to be at least hundreds of milliseconds. To better understand this problem, in this paper, we use empirical measurements in a small data center testbed to study, at a microscopic level, the effects of various types of packet losses on TCP's performance. In particular, we single out packet losses that impact the tail end of small flows, as well as bursty losses that span a significant fraction of small TCP congestion windows, and show a non-negligible effect of such losses on the FCT. Based on this, we propose the so-called, timely-retransmitted ACKs (or T-RACKs), a simple loss recovery mechanism that conceals the drawbacks of the long RTO even in the presence of heavy packet losses. Interestingly enough, T-RACKS achieves this transparently to TCP itself as it does not require any change to TCP in the tenant's virtual machine (VM) or container. T-RACKs can be implemented as a software shim layer in the hypervisor between the VMs and the server's NIC or in hardware as a networking function in a SmartNIC. Simulation and real testbed results show remarkable performance improvements.

Traditional cache algorithms for information centric networks cache every seen item and rely on simple statistics, such as usage recency, to determine the target for replacement. While they result in a simple and efficient O(1) algorithms, such simple statistics perform poorly when dealing with realistic request patterns, that are non-uniform and that often exhibit daily, weekly and monthly seasonality. As the computational power of processors increased dramatically over the years, it is worth trying to use more complex cache algorithms in order to yield better performance. In this paper, we investigate the use of convolutional neural networks as a means to capture the seasonal patterns in the requests stream, and propose a cache algorithm that is able to consider seasonality and make decisions accordingly. We implement our cache algorithm by building an interface to the real-world ICN forwarder from the CICN open source project, the so-called Metis forwarder; and conduct our experiments on a real-world dataset representing the access statistics of Wikipedia to demonstrate the effectiveness of our algorithm.

Prefetching and caching content at road-side units (RSUs) and broadcast-transmission scheduling can be shown to improve the throughput in vehicular networks considerably, provided vehicular trajectories prediction are accurate enough. As such many studies assume implicitly that such trajectories are accurately available via GPS or location tracking. In practice, as discussed in the standards, this raises a big issue of privacy. In this paper, we focus on jointly optimizing the broadcastscheduling throughput from RSUs to vehicles, while preserving the privacy of vehicles by enabling them to disseminate obfuscated location information to the server. As it is difficult to predict the vehicular throughput according to its disseminated obfuscated locations, we propose to use the capacity based on reported information as an approximation. We formulate the problem as a reinforcement learning (RL) problem, where the decision variables concern the action to obfuscate disseminated location according to current location and the last disseminated location, with the objective of maximizing a utility function that consists of a weighted sum of the capacity and the level of privacy. Simulation results show that, the proposed scheme consistently outperforms the randomized benchmark, and is insensitive to the prediction accuracy of vehicles' future locations.

Modern data centers host a plethora of interactive data-intensive applications. These are known to often generate large numbers of short-lived parallel flows that must complete their transfer quickly to meet the stringent performance requirements of interactive applications. Network resources (e.g., switch buffer space) in the data center are scarce and are easily congested, which unfortunately results in long latency. As a first solution, following a traditional design rationale, Data Center TCP (DCTCP) was proposed to speed up the completion time of short-lived flow by maintaining a low buffer occupancy in the switch. In general, DCTCP performs well in homogeneous environments, however, its performance degrades quickly in heterogeneous environments or when it uses a large initial congestion window. To resolve this problem, we propose a Hypervisor-based congestion watching mechanism (HWatch), which measures the network load in the data center via ECN and uses the resulting statistics to determine the appropriate initial congestion window size to avoid congestion. HWatch neither needs modification to the TCP stack in the VMs nor requires any specialized network hardware features to meet its targets. In our evaluation, we demonstrate the benefits of HWatch in improving the performance of TCP flows through large-scale ns2 simulation and via testbed experiments in a small data center.

Prefetching data at the road side units (RSUs) and transmitting them to interested vehicles can help reduce the traffic load in vehicular networks, and improve the data retrieval time. Most prior work in this area opted for supporting data delivery by using a single data rate, in stark contrast to common networking knowledge that good tradeoffs can be achieved in terms of performance by adopting different, more appropriate data rates for different users. In particular, in general wireless networks it is well known that when the data rate is small, the transmission is robust but takes too long; while when the data rate is high, the data delivery time is smaller but the coverage area of the RSU becomes smaller and so does the robustness. In this paper, we study the joint problem of caching and scheduling to decide, what data to prefetch, when to deliver it, and which data rate to use, with the objective of maximizing the volume of data delivered to the mobile vehicles in the network. This problem is subject to many constraints imposed by the real system limits, such as the mobility pattern of the vehicles, the distribution of data requests by the vehicles, and the limited buffer space available at the RSUs. We formulate the problem as an integer linear programming problem, and propose a heuristic caching algorithm, and a heuristic scheduling algorithm to find an approximate solution that is shown via simulation to improve the throughput, compared to standard alternative approaches.

Datacenter networked applications, often require multiple data transfer flows that semantically constitute a coflow group. A coflow is thus considered completed when all the transfers in the coflow are completed. Hence, application performance is optimized whenever the completion time of a coflow is minimized, rather than that of the flows composing it. Currently, popular coflow scheduling algorithms are mostly centralized, and they incur high overheads. The decentralized approach in the “many-to-many” scenario also incurs high communication overheads due to the communication among the local controllers. In this paper, we present a coflow scheduling mechanism that aims to minimize the coflow completion time for coflows that show a many-to-many communication pattern, and as a byproduct communication overhead cost is also minimized. Our algorithm preserves compatibility with existing commodity switches and network protocols and improves the coflow completion times on average by 1.8 times compared to the baseline as demonstrated via testbed implementation and large-scale simulation.

In cloud environments, interactive applications deployed in data centers often generate swarms of short-lived data transfers (or flows) that face dramatic competition for the scarce switch buffer space from other short-lived as well as the long-lived flows. In the presence of bloated queues, such short-lived flows often experience multiple packet losses per round-trip time which often triggers the timeout-based loss recovery mechanism. A direct consequence of this is an inflated application response time that turns out to be orders of magnitude larger than what it should be. A data center aware TCP protocol (DCTCP) was designed as a new TCP specifically to address this issue, however, it does not consider its co-existence with other transport protocol (e.g., CuBIC and NewReno of Linux). In such situations, which are abundant in multi-tenant data centers, the legacy large initial congestion window sizes (e.g., 10 segments), induce multiple packet losses at the onset of a TCP flow, which forces timeout and even binary exponential backoff. In this paper, we propose a novel Hypervisor-based, application-transparent approach for active congestion probing to enable the hypervisor to infer on-path congestion before the TCP connection is fully established for new traffic to avoid such massive packet losses and timeout. The so-called ProBoSCIS mechanism does not require any changes to TCP, works with all versions of TCP and does not need any special network hardware features other than those that exist in today's data center commodity switches. We show its effectiveness via ns2 simulation and demonstrate its practical feasibility by implementing and deploying it in a small-scale data center test-bed. We show the significant reduction in application latency by adopting ProBoSCIS in a series of real experiments.

Much of the incremental improvement to TCP over the past three decades had the ultimate goal of making it more effective in using the long-fat pipes of the global Internet. This resulted in a rigid set of mechanisms in the protocol that put TCP at a disadvantage in small-delay environments such as data centers. In particular, in the presence of the shallow buffers of commodity switches and the short round trip times in data centers, the continued use of a large TCP initial congestion window and a huge minimum retransmission timeout (both inherited from the Internet-centric design) results in a very short TCP loss cycle that affects particularly the flow completion times of short-lived incast flows. In this paper, we first investigate empirically the TCP loss cycle and discuss its impact on packet losses, recovery and delay; then we propose a switch-based congestion controller with hysteresis (HSCC) that aims to stretch the TCP loss cycle without modifying TCP itself. To protect incast flows from severe congestion, HSCC is designed to transparently induce the TCP source to alternate between its native TCP congestion control algorithm and a slower more conservative constant bit rate flow control mode that is activated when congestion is imminent. We show the stability of HSCC via analytical modelling, and demonstrate its effectiveness via simulation and implementation in a small testbed.

Satisfying the huge demand for high bandwidth in 5G networks is in part achieved by vertical densification of the network infrastructure with so-called small-cell base stations. As a direct consequence, the performance of 5G networks intrinsically suffers from: 1) a huge inter-cell interference due to the network density and 2) a large energy waste that results from the high redundancy of lightly loaded, always-on, and small-cell base stations. In this paper, we use a game theoretic approach to design a distributed energy efficient bandwidth sharing mechanism for small-cell networks. To circumvent the combinatorial nature of searching in the huge strategy space, we invoke a reinforcement learning approach to intelligently guide the search toward good solutions. More precisely, our solution relies on dynamically learning good strategies for the user-equipment association and orthogonal frequency division multiple access (OFDMA) scheduling to strike a balance between energy efficiency and high bandwidth utilization. Our model takes into account inter-cell interference and the diversity of user quality of service requirements.

In this paper, we describe a software defined networking (SDN) approach to traffic engineering in inter-data center communication; then present$\mathrm{MCTEQ}$, a constrained utility-optimization formulation of the joint-bandwidth allocation problem for multiple classes of traffic in inter-data center communication.$\mathrm{MCTEQ}$handles priorities between traffic classes in a soft manner and explicitly considers the delay requirement of$\mathrm{Interactive}$flows.$\mathrm{MCTEQ}$being NP-hard, we construct a new approximation to be able to lean on the mature and efficient linear programming solvers to obtain fast and accurate approximations. We demonstrate via numerical experiments with two realistic inter-data center network topologies that$\mathrm{MCTEQ}$achieves considerably more network utilization than the best known solutions from the literature, while running at least twice faster. We also show via ns-2 packet level simulation that with$\mathrm{MCTEQ}$traffic engineering, end-to-end packet delay requirements of$\mathrm{Interactive}$flows are indeed guaranteed for in-profile traffic, which is not the case for alternative approaches.

TCP's internet-centric design is oblivious to the composite nature of the data center traffic, and in the presence of small switch buffers and other long-lived flows (elephants), short-lived (mice) flows often experience “Incast” congestion events that significantly affect their flow completion time (FCT). In this paper, we implement a switch- assisted Incast congestion mitigation system that takes into consideration the existence of other elastic traffic in data center networks (DCNs). The so-called IncastGuard system does not require any changes to the TCP protocol at the sender nor at the receiver and is shown to be effective in mitigating the effects of incast congestion via a prototype implementation in NetFPGA and experiments in a small-scale cluster testbed.

We first study, at a microscopic level, the effects of various types of packet losses on TCP performance in a small data center. Then based on the findings we propose a simple recovery mechanism to combat the drawbacks of the long retransmission timeout. We emphasize through our empirical study that packet losses that occur at the tail of short-lived flows$a$nd/or bursty losses that span a large fraction of the congestion window are frequent in data center networks; and, in most cases, especially for short-lived flows, they result in a loss recovery that incurs waiting for a long retransmission timeout (RTO). The negative effect of frequent RTOs on the FCT is dramatic, yet recovery via RTO is merely a symptom of the pathological design of TCP's minimum RTO mechanism (set by default to the Internet scale). We propose the so-called Timely Retransmitted ACKs (T-RACKs), a very simple recovery mechanism for data centers, implemented as a shim layer between the virtual machines layer and the end-host NIC, to bridge the gap between TCP's huge RTO and the actual round trip times experienced in the data center. Compared to alternative solutions such as DCTCP, our T-RACKS has the virtue of not requiring any modification to TCP, which makes it readily deployable in virtualized multi-tenant public data centers. Experimental results show considerable improvements in the FCT distribution.

Due to the partition/aggregate nature of many distributed cloud-based applications, incast traffic carried by TCP abounds in data center networks. TCP, being agnostic to such applications' traffic patterns and their delay-sensitivity, cannot cope with the resulting congestion events, leading to severe performance degradation. The co-existence of such incast traffic with other throughput-demanding elastic traffic flows in the network worsens the performance degradation further. In this paper, relying on the programmability of Software Defined Networks (SDN), we address this problem in an efficient and easily deployable manner. The proposed SDN-based incast congestion control framework relies on the SDN controller and the hypervisor programmability to solve such congestion problems without altering the guest virtual machines nor the network switches. We assess the performance of the proposed scheme via real deployment in a small-scale testbed and ns2 simulation in larger environments.

To meet the deadlines of interactive applications, congestion-agnostic transport protocols like UDP are increasingly used side-by-side with congestion-responsive TCP. As bandwidth is not totally virtualized in data centers, service outage may occur (for some applications) when such diverse traffics contend for the small buffers in the switches. In this paper we present SDN-GCC, a simple and practical software-based congestion control mechanism that puts monitoring and control decisions in a centralized controller and traffic control enforcement in the hypervisors on the servers. SDN-GCC builds a congestion control loop between the SDN controller and hypervisors without assuming any cooperation from tenants applications (or transport protocol), ultimately making it deployable in existing data centers without any service disruption or hardware upgrade. SDN-GCC is implemented and evaluated via simulation in ns2 as well as real-life small-scale test-bed deployment and experiments.

In today's modern cloud supported applications, the traffic relies on both congestion-responsive transport protocols like TCP and congestion-oblivious transport like UDP including all their variations. As bandwidth is not totally virtualized in today's data centers, the diverse responses of these protocols to congestion lead to inefficiencies and service disruption to some applications. In this paper we present HyGenICC, a simple, distributed and practical congestion control mechanism that puts congestion control back where it belongs, in the network layer, albeit, without modifying the network layer behaviour. To this end IP ECN marking in the switches to indicate congestion, combined with additional packet processing in the hypervisor enable HyGenICC to partition bandwidth among competing virtual machines (VMs) in datacenters effectively. To enable easy deployment in existing data center, HyGenICC design is subjected to several constraints such as: i) freedom of changes to the guest VMs' congestion control mechanism, and ii) reliance only on switch capabilities that are already available in today's commodity switches. We evaluate HyGenICC via extensive simulation in the ns2 network simulator.

The occupancy of the pending interest table (PIT) in content-centric networks (CCN) and other information-centric networking (ICN) architectures has an undeniable effect on the congestion level and the performance of the network. Each interest packet forwarded upstream by a node results in at most one data packet arriving back at the node and being possibly forwarded to many interfaces downstream. Clearly, to regulate the rate of arrival of new data chunks at a node, one can regulate the arrival rate of interest packets. To be able to design effective mechanisms to control the traffic in CCN, a systematic study and analysis of the PIT occupancy is thus imperative. In this paper, we derive an analytical model to estimate the PIT occupancy distribution via an approximate continuous time Markov (CTMC) model and validate the model via simulation experiments with different system parameters. Our proposed model is not only useful in the design of traffic controllers for managing the PIT occupancy but also offers an effective method for dimensioning the PIT.

In this paper, we propose a novel task scheduling algorithm for Hadoop MapReduce called dynamic priority multiqueue scheduler (DPMQS). DPMQS i) increases the data locality of jobs, and, ii) dynamically increases the priority of jobs that are near to completing their Map phase, to bridge the time gap between the start of the reduce tasks and the execution of the reduce function for these jobs. We discuss the details of DPMQS and its practical implementation, then assess its performance in a small physical cluster and large-scale simulated clusters and compare it to the other schedulers available in Hadoop. Both real experiments and simulation results show that DPMQS decreases significantly the response time, and demonstrate that DPMQS is insensitive to changes in the cluster geometry.

Despite the improvements brought about by content-centric networking's (CCN) in-network caching and interest aggregation, congestion can still take place in such networks due to the dominance of non-reusable content, high cache churn, high delay variations, premature timeouts and interest retransmission. This becomes even more dramatic when multi-path routing is adopted. Identifying that at a given node in CCN, the Pending Interest Table (PIT) occupancy can give a good estimate of the data workload to arrive to the node in the near future, we propose in this paper a novel mechanism to control congestion in CCN based on this idea. Our mechanism uses the average occupancy of the PIT to estimate the anticipated data packet transmission queue length and sends explicit congestion notification signals to the content requesters to reduce their interest sending rates when such anticipated queue size exceeds a threshold. We demonstrate the effectiveness of our proposed mechanism via ns-3 simulation.

The increasing demand for high bandwidth in cellular wireless networks led to a dramatic increase in the number of deployed LTE femtocell base stations (FBS) in recent years. While the energy consumed by a single FBS is relatively negligible, the collective energy footprint of all FBSs deployed by an operator turns out to be huge. Energy-efficient protocols are needed thus to balance the trade-off between energy saving and bandwidth utilization. The key component of the desired protocol to prevent both energy and bandwidth waste is interference mitigation, which, most previous work has failed to properly consider. To this end, in this paper, we manipulate user equipment (UE) association and OFDMA scheduling with a combination of interference mitigation to enable an energy efficient QoS-constrained medium access for femtocell networks. Recognizing the NP-hardness of the problem, we propose two algorithms with guaranteed convergence. Extensive simulations show that our algorithms outperform alternatives in multiple metrics such as utility, power consumption, and convergence speed.

Despite the dramatic improvements achieved in building energy-efficient electronic devices, the amount of electricity consumed worldwide to power the global information technology infrastructure has grown tremendously in the past decade. In this paper, we propose algorithms to reduce energy consumption by data centers by considering the placement of virtual machines onto the servers in the data center intelligently. We formulate this problem as an integer programming problem, prove it is NP-hard, then explore two greedy approximation algorithms, minimum energy virtual machine (VM) scheduling algorithm (MinES) and minimum communication virtual machine scheduling algorithm (MinCS), to reduce the energy while satisfying the tenants' service level agreements. We examine the performance of these two algorithms in both small and large clusters using real data traces and synthetic workloads, and compare them to other alternatives. Our results demonstrate that MinES and MinCS yield scheduling that are within 4.3 to 6.1 percent energy consumption of the optimal solution while being computationally efficient.

Due to the partition/aggregate nature of many cloud applications, incast traffic is preponderant in data center networks (DCNs). Because TCP is agnostic to this composite nature of the applications traffic and their quality of service requirements, a few congestion events often degrade significantly the user perceived quality of service. This is exacerbated by the co-existence of such incast traffic with other elastic traffic flows in the network. In this paper we address the congestion problems of incast traffic and its interaction with other elastic traffic in DCNs. We propose a switch- assisted TCP congestion control via some small modifications to the switch software that do not require any modification to the TCP protocol nor to the TCP sender or receiver logic. We assess the performance of the proposed scheme via ns2 simulation as well as a real deployment in a small-scale testbed1.

To improve their profits, it is crucial for cloud service providers to fulfil their tenants target QoS requirements in an energy efficient way. The services provided in many modern public clouds have graduated to include more sophisticated and flexible virtual clusters, encompassing not only the resource requirement of the virtual machines (VMs) but also the virtual topology between VMs. In this paper, we study the energy efficiency of virtual cluster embedding in data centers. We carefully develop a mathematical model, aiming to minimize the energy consumption of a data center, and given the NP- hardness of the problem, we propose an approximate algorithm MinE-VCE to solve the problem efficiently. We show via numerical experiments how MinE-VCE consistently outperforms other alternative algorithms.

Recent studies have shown that the Pending Interest Table (PIT) in most Information-Centric Networking proposals can represent a bottleneck for the network performance. Newly arrived interest packets at the PIT are dropped if the PIT becomes full. In-network caching may fail to reduce the traffic load on the PIT if the cache dynamics is high as memory in routers is limited. How to manage the occupancy of the PIT in the presence of high traffic load remains an interesting but challenging problem. To this end, this paper presents an analytical model to estimate the PIT occupancy distribution via a continuous-time Markov chain model. In the model, we take into account caching, interest aggregation, interest timeouts and retransmission.We validate the model via simulation experiments to show the accuracy of our model. Our proposed model is useful in the design of traffic controllers for managing the PIT occupancy.

Powering an individual LTE femtocell base station, or Home eNodeB (HeNB) in the LTE jargon, requires relatively very little energy. It is only when HeNBs are deployed massively, as has happened in the past few years, that energy efficiency becomes an important issue. With large numbers of co-located HeNBs and the increased inter-cell interference resource utilization becomes highly inefficient resulting in a high unnecessary energy consumption. To tackle this problem, coordination techniques could be invoked by the network operator to consolidate the offered workload to the network on as few HeNBs as possible and power down idle ones. Recognizing, however, that such techniques usually impair user-perceived quality of service (QoS), especially with bursty traffic, more sophisticated methods need to be investigated to also consider QoS. Despite the volume of prior work, the key issue -- viz. simultaneously reducing energy waste, increasing bandwidth utilization while guaranteeing user-perceived QoS -- has not been properly considered so far. In this paper, we model the trade-off between energy efficiency and QoS preservation by manipulating user equipment (UE) association and OFDMA scheduling in controlled networks of HeNBs. The problem being NP-hard, we propose two distributed learning algorithms, within a potential game-based framework, to obtain good and fast solutions to the problem. We demonstrate via numerical results the effectiveness of the proposed algorithms in achieving better performance in terms of utility, power, energy efficiency, convergence speed, and complexity compared to other alternatives.

The CDN serves as an essential element in providing content delivery services on the Internet; however, limited by its footprint and influenced by variations of network conditions and user demands, no individual CDN can qualitatively fulfill delivery tasks anytime and anywhere. As such, large content providers often use multiple CDNs. Nevertheless, this approach is not only cumbersome to negotiate multiple business contracts, but also economically inefficient, especially for small content providers. A simpler alternative approach would be to let each content provider only sign one contract with an authoritative CDN, say CDN-0, and let CDN-0 handle the potential performance trap of individual CDN. To fulfill its business commitment, CDN-0 could either use its own infrastructure or rent services from other CDNs, which is sometimes indispensable. To make an optimal operating plan for CDN-0 operator, we propose a new problem, called MCDN-CM, whose objective is to minimize CDN-0's operating cost. MCDN-CM is a concave minimization problem and we take advantage of the special form of the practical CDN-pricing function - piece-wise linear concave - to arrive at an optimal solution through an iterative procedure. We conduct numerical experiments under realistic settings and show via the experimental results that CDN-0 can achieve a tremendous cost-saving by using our proposed algorithm.

This paper presents a new jamming attack in wireless LANs that deliberately targets uplink TCP acknowledgements (TCP-ACKs) of downlink TCP flows. To ensure immunity to detection with existing schemes, in this attack, the attacker does not jam the target constantly; instead, it relies on our probabilistic estimation model to forecast the time when its transmission has the highest likelihood of colliding with the target's generated TCP-ACKs. Repeating this process results in a decrease of the average congestion window of the targeted due to an increased round-trip time (RTT). The rogue node and/or its colluding attackers can grab this freed bandwidth and increase their throughput. We demonstrate via ns-2 simulation the effectiveness of such attack and show how easy it is to deploy without hardware modification. We also discuss its immunity to detection by existing detection schemes and investigate some parameters that may be used in building future detection mechanisms.

The settlement-free peering relationships play a vital role in today's Internet, notably in helping ISPs cope with the dramatic increase in traffic load caused by the recent surge in the demand for videos and user generated content. Because of the added caching capability of CCN, peering in CCN can be expanded to encompass not only content that is permanently stored in the ISP's network, but also content that is temporarily cached at CCN routers in the ISP's network. Intuitively, this content-level peering is likely to benefit the networks involved in the peering relationship; however, this comes at a non-trivial cost. In this paper, we try to answer the question of whether the additional overhead and complexity to extend content-level peering is justifiable in view of the benefits it brings. To this end, we formulate the content-level peering problem as an optimization problem to study its maximum potential benefit. We conduct extensive numerical experiments to evaluate the potential peering benefit under realistic AS-level peering graphs, using realistic video traffic. The experimental results show that the interconnectivity of the peering graph significantly affects the maximum benefit of content-level peering. Compared to local greedy caching, cooperative caching can bring higher peering benefits; yet it is sensitive to parameters like the peering link bandwidth and the AS-level cache size.

With the increased density of LTE femtocell base station (FBSs) deployments, mutual interference between FBSs becomes a bottleneck to network performance. Inter-femtocell coordination has been invoked in the past to address this problem, however it is not practically possible as LTE FBSs do not possess the X2 interface to enable them to communicate with each other. In this paper, we opt for a fully distributed approach and introduce a self-learning MAC protocol for FBSs to allocate resources based on historical user feedback. In our approach, each FBS independently learns about the asymmetric contention level on its links, and transfers resources from highly-contended links to low-contention ones to avoid wasting resources. The learning process is modelled as a cluster-structural regret-based game and simulation results show that our algorithm outperforms alternative algorithms from the literature on a wide range of metrics.

In dense indoor multi-cell wireless networks, such as WLANs and OFDMA-based femtocell networks (e.g., LTE, WiMAX), the wireless bandwidth waste has become more dramatic due to the large interference and contention occasioned by uncoordinated channel access methods such as CSMA. Coordinating resource allocation in the network can be a good compromise solution to this problem. However, in general, resource allocation in wireless networks is a complex multi-dimensional problem that involves four tasks: client association to select a base station to associate with, antenna beam selection when directional antennas are used, link scheduling to ensure conflict freedom, and power adaptation to reduce mutual interference. In this paper we study the joint optimization of the above four components, and propose a unified conflict-free scheduling algorithm that solves the joint problem with two alternative objectives: (1) power-utility-maximization and (2) fair-throughput-maximization. Our scheduling algorithm can be directly implemented in OFDMA-based femtocell networks. In addition, to enable realistic deployment in WLANs, we design the so-called TD-CSMA, a coordinated access protocol that is compatible with the legacy IEEE 802.11 MAC protocol. With extensive simulations in ns-2 we notably show that our model outperforms some benchmark algorithms on a wide range of metrics.

In cloud computing systems, such as Hadoop, system performance is a significant target for improvement. In classic master node-central schedulers, decision is made in the heartbeat time scale, and idle slots during a heartbeat, remain idle until allocated a task by the master node. In this paper, we propose a novel scheduler named multiple queues scheduler (MQS) that improves the throughput of the system by increasing data locality rate of map tasks, reducing thereby the average completion time of jobs. To achieve this, we associate slave nodes with individual queues, and distribute the tasks of a job at arrival to those nodes that contain the associated input data, based on data locality. To reduce the load on overloaded slave nodes, task migration is performed asynchronously between nodes within a rack, without the intervention of the master node. Our results demonstrate the effectiveness of the proposed algorithm. The benefits of MQS are three-fold: first, it decreases the probability of allocating map tasks to non data-local nodes; second, it decreases the time wasted between heartbeats; these two aspects immediately improve the system performance; and third, it mitigates the stress on the master node by assigning part of the scheduler's functions to slave nodes.

Multi-cell wireless LANs (WLANs) are often densely deployed in order to achieve full coverage of a given area, in particular in indoor environments. In such scenarios, it is widely believed that the co-existence of hidden and exposed APs simultaneously results in a dramatic download throughput degradation for the clients. Indeed, in such environment, intutively, each AP while competing for channel access with neighbouring exposed APs may suffer collisions from hidden APs each time it wins such competition. In this paper we study the problem of fairly allocating download bandwidth to clients in such dense multi-cell WLANs. To this end, we design algorithms that adapt client association, airtime sharing among clients and rate control to achieve optimal fairness in bandwidth access. We model this problem as a non-linear programming problem, and propose a distributed algorithm to solve such an NP-hard problem via transformation into a convex problem as well as approximations. Our numerical and simulation results show that, the proposed algorithm significantly improves the performance compared to existing solutions, and leads to the counter intuitive conclusion that intelligently adding exposed APs will lead to better system performance.1

In this paper we study the problem of client association, airtime sharing and contention resolution in a multi-cell WLAN to achieve fair download bandwidth sharing. We first model the problem as a utility maximization problem, then, because of the integral nature of association, the problem being NP-hard, we decompose it into two sub-problems: the client association problem on one hand, and the joint airtime sharing and contention resolution problem on the other. We show that, for each fixed association pattern, the corresponding joint airtime sharing and contention resolution problem can be solved in polynomial time. To solve the client association problem, we propose the so-called Swap localized algorithm. The Swap procedure iteratively swaps clients between pairs of neighbour access points (APs) if the swap leads to an improvement in the global utility. Simulation results show that, the proposed algorithm is significantly better than RSSI-based heuristic, and quickly leads to a near-optimal solution.

In this paper we study the problem of throughput maximization, with fairness guarantee, in multi-cell WLANs with hidden terminals. In such a scenario, the throughput gained by each flow is generally determined by the four major control mechanisms that make the basis of WLAN control protocols - viz., radio frequency channel assignment, association control, intra-AP airtime sharing between the associated clients, and the access rate control which is determined by the MAC layer contention window tuning. Instead of focusing on each of the four mechanisms apart, in this paper we optimize the network performance via a joint channel assignment, association control, airtime sharing, and contention window tuning; we formulate this joint problem as a non-linear programming problem. Because such a problem is in general NP hard due to the integral nature of both channel assignment and association control, we solve it by iteratively approximating it via a convex programming problem. Numerical and simulation results show that, the resulting solution significantly improves the network throughput and fairness, compared with methods that optimize separately the different mechanisms. Our solution also gives further insights into the importance of each one of these mechanisms when considered jointly.

In this paper we study the problem of joint client association, airtime sharing and contention resolution in IEEE802.11 multi-cell WLANs with directional antennas with the goal of achieving optimal fair throughput. We formulate the problem as a non-linear programming problem and solve it under the network utility maximization framework. Using simulation, we demonstrate that i) the association pattern should try to balance the number of clients associated with each AP to use the capacity of more APs; ii) clients in the same transmission range of an antenna should always be associated with the same AP to avoid hidden node collisions.

The current Internet is based on the old concept of data networking whose role was to mainly build a fault-tolerant network infrastructure that enables efficient sharing of scarce and expensive resources such as storage and CPU time. Its main feature is the end-to-end principle of communication between any pair of hosts under the client-server model, which was well suited for early Internet applications, e.g., remote login (CPU sharing) and ftp (storage). In recent years, the main usage of the Internet has evolved to become a vehicle of content generation, sharing and retrieval, demonstrated by such extremely hot applications as P2P live and on-demand streaming, User-Generated Content (UGC) services (e.g., Youtube, Flickr ) and Social Networks (e.g., Facebook, Google+). To match such transformation, a clean-slate redesign of the future Internet architecture has been proposed under the generic name of Content-Centric Networking (CCN). In this paper, we propose a new caching scheme for such CCN networks and evaluate the in-network caching performance of this policy by comparing it with that of the default proposed policy via simulation.

In this paper, we study the trade-off between the aggregate MAC flow throughput and the fairness in IEEE 802.11 based wireless mesh networks (WMNs) that utilize scheduling on top of the CSMA/CA access scheme. We use a toy WMN topology to allow us to understand easily this trade-off and propose an analytical model to study the interaction between contending links in this topology. Based on this model, we formulate the bandwidth scheduling problem as an aggregate MAC flow throughput maximization problem subject to the fairness requirements dictated by the scheduler. This study is dictated by the need to understand the limits of such scheduling algorithms which have proliferated in recent years to balance the throughput and fairness of WMNs without modifying the CSMA/CA protocol or the binary exponential backoff due to the non programmability of the MAC and backoff procedure in modern commercial Wi-Fi chipset. As an example, we evaluate our previously proposed bandwidth scheduling mechanism - the so-called distributed fair MAC scheduler (DFMS) to validate our model on one hand and demonstrate the efficiency of our scheduler on the other.

In this paper, we study jointly the problems of rate control and contention resolution in multi-cell WLANs based on the IEEE 802.11 MAC protocol in the presence of hidden terminals. We adopt the network utility maximization (NUM) framework to formulate the problem as a nonlinear optimization problem. Unlike previous approaches that require maximal weight scheduling or target simple MAC protocols without hidden terminals, our problem formulation considers a realistic IEEE 802.11-based MAC layer model. The resulting formulation being non-convex, we propose a simple scheme to transform this non-convex problem into a convex one. We derive a simple distributed algorithm to solve the problem via Lagrangian dual decomposition. Our algorithm does not require exchanges of topology or spatial information about the mobile clients between APs. Practical issues like random backoff, carrier sensing, frame retransmission and optimal contention window (CW) setting are considered in our design. The effectiveness, accuracy and convergence speed of our analytically derived algorithm are verified via numerical experiments and simulations.

In this paper, we study the problem of determining the optimal association in multi-cell WLANs in the presence of hidden terminals and inter-AP collisions. Unlike most work in this area which deal with networks without inter-AP interference, we reveal that association control alone is not sufficient to achieve fair throughput allocation and load balancing across APs. Instead, we advocate the joint association control, rate control and contention control to improve network performance. Based on this, we formulate a cross-layer optimization problem whose objective is to allocate downlink throughput according to the proportional fairness principle. As the problem turns out to be a non-convex mixed integer programming problem, which is known to be NP-hard, we relax it into a continuous convex problem and propose a distributed algorithm to solve it. We then design a simple yet effective distributed approximation algorithm to construct an solution that fulfills the discrete integral association constraint. The output of the algorithm provides the optimal association, the maximum achievable rate for each downlink flow and each AP's optimal average backoff time. Numerical experiments and simulation results show that our algorithm converges rapidly and works effectively.

There have been a number of TCP variants proposed in the literature to combat random packet losses in wireless networks. In this paper we first perform a simulation study on the performance of these TCP variants in the context of IEEE 802.11 WLAN with various channel conditions, generated using different wireless error models and show that none of the existing TCP variants has superior performance over the conventional TCP in such WLANs. We also observe that in IEEE 802.11 WLAN efficiency problem with TCP protocols only exists when the number of active wieless nodes is small and the channel condition is extremely bad. We further demonstrate that employing the delayed ACK mechanism and SACK option at the TCP receiver can generally improve the performance. With the option to modify the TCP implementation at the receivers we further propose TCP-WOW algorithm, which estimates the flow queue size on the forward path and further uses such estimates as quantitative indication of the congestion level to dynamically guide the congestion response. TCP-WOW is robust to reverse traffic interactions. TCP-WOW also shows a better RTT fairness and consistently good performance in our IEEE 802.11 WLAN simulations.

In this paper, we study the bandwidth allocation problem on a bi-directional end-to-end path in a last-mile wireless mesh network. We first propose an analytical model to study the interaction between contending links. Based on this model, we formulate the bandwidth allocation problem as a constrained maximization problem that captures real world complexities such as hidden node collisions, multi-hop flows and maximum packet transmission retry limit. The objective of the optimization problem is to maximize the downlink end-to-end throughput under a predefined uplink end-to-end throughput requirement. The optimal setting of each mesh router's contention windows can be obtained from the solution of the optimization problem. Our approach does not require any hardware modification and application layer rate control. Simulation results show that the proposed methodology works very well, the target uplink bandwidth can be reached and the downlink throughput is increased significantly when compared to the IEEE 802.11 standard.

As the Internet evolves, traffic management has become a high-priority problem. Without a network centric traffic management scheme, severe fairness problems can arise. For instance, unfairness occurs with TCP traffic in the presence of careless or subversive misbehaving flows, or even in the presence of other TCP flavors if we consider inter-protocol unfairness. In this paper we propose a new AQM scheme, Stochastic Fair Traffic Management (SiFTM), to help achieve fair bandwidth allocation among flows even in the presence of misbehaving ones. SiFTM relies on multi-level hashing to perform packet classification and on a random sampling mechanism to identify and punish misbehaving flows harshly. SiFTM improves the fairness index among TCP flows even with different TCP flavors. Through simulations we show that SiFTM outperforms other related schemes, especially in the presence of misbehaving flows. Furthermore, we argue that with the fair bandwidth allocation it provides, SiFTM deprives end systems of the incentive to behave unresponsively as a means to enjoying better services. It thus promotes rational behavior and self imposed network-friendly congestion control in the transport protocol.

Due to the limited number of orthogonal channels and the dense deployment of IEEE 802.11 access points (APs), interference between neighboring basic service sets (BSSs) are very common in indoor environment. One consequence of such neighboring interference is the inter-BSSs hidden terminal problem in which some mobile stations may suffer from throughput starvation. In this paper, we advocate and develop a methodology to allocate bandwidth as a mean of combating such starvation problem. We first propose an analytical model to study the interaction between contending links in the network, then based on this model, we demonstrate how the contention window (CW) can be adjusted in order to allocate the upload and download bandwidth to sustain some predefined bandwidth requirement with only the basic access scheme is used. Our approach does not require any hardware modification, and is compatible with most WLAN chipsets. The optimal window setting can be obtained by simply solving a nonlinear system once without any iterative algorithm. Simulation are invoked to support the effectiveness of the proposed methodology in achieving the target bandwidth even under saturation condition.

In this paper, we consider the throughput allocation problem in an extended (or multi-cells) IEEE 802.11 wireless network. We first demonstrate the severe throughput imbalance that can take place between downlink TCP flows even in simple multi-cell WLANs. Then to solve this unfairness problem, we derive an analytical model that describes the interaction between different TCP flows at the MAC layer, and formulate the throughput allocation problem as a nonlinear optimization problem subject to certain fairness requirements. Real world complexity such as hidden terminals, packet transmission retry limit, and the unique characteristics of TCP traffic are considered. Unlike alternative approaches that rely on modifying the TCP sender or implementing active queue management at the network layer, solving our optimization problem yields the optimal MAC layer contention windows settings that can lead each TCP flow to its target end-to-end throughput. Among the practically appealing characteristics of this approach are: i) its locality and the possibility of implementing it at the AP and within the ESS, whereas alternative approaches rely on changing the TCP traffic source; and ii) its simplicity, i.e., it is achieved by controlling a single parameter per-node, whereas alternative approaches based on AQM require the tuning of many parameters and achieve mitigated results. Simulation results show that our approach can achieve a fair throughput allocation and attest to the accuracy of our proposed method.

We present a distributed fair MAC flow allocation and scheduling framework for IEEE 802.11 based wireless mesh networks. The framework consists of (1) a modified wireless ad hoc routing protocol to take into account bandwidth requirement, (2) a link information dissemination protocol to propagate local topology information, (3) a cooperative gradient-based iterative algorithm to allocate fairly MAC flow bandwidth and (4) a distributed fair MAC scheduler to coordinate access to the channel according to the allocated bandwidth. We stress the importance of our framework's practicality, such that it is easily deployable in real IEEE 802.11 based devices, and, most importantly, it is extensible to include other services such as QoS routing and admission control. Before carrying out an expensive on-site performance evaluation, we conduct numerous simulations to evaluate our framework, and the fairness index indicates, under extremely high traffic rates, that our framework is fair to more than 90% of the MAC flows in the network.

Several studies have shown that in high-speed networks it is likely that a large number of packets are dropped in a single loss event on a bottleneck link and a large portion of the ongoing flows are about to experience packet losses. Such synchronized losses among flows have negative effects on the performance of most loss-based congestion control protocols proposed for high-speed networks, especially with respect to fairness considerations. We propose in this paper F2-TCP, a new loss-based congestion control protocol for high-speed networks, to achieve better fairness and TCP-friendliness. Simulation studies show that F2-TCP indeed fulfills these design goals. The superior performance and the low deployment cost, especially on legacy machines, make F2-TCP a good alternative for todaypsilas high-speed networks.

In this paper, we develop a Markov model to evaluate the performance of WLAN in the presence of hidden terminals. We focus on characterizing and studying the scenario of an access point with a population of clients partitioned into two mutually hidden groups, and derive a model to estimate the network throughput and the individual nodes' throughput. We propose a general methodology to solve the Markov chain by forming a nonlinear system of equations which describes the relationship between the conditional state transition probabilities, the transmission attempts probability and the steady state probability. Unlike alternative approaches, it is not necessary to invoke iterative methods to solve this system. We also demonstrate how our methodology and model can be used to estimate the optimal stable rate for each source in the WLAN as a means for rate control to achieve a given fairness principle between hidden groups of nodes and avoid starvation or congestion collapse for one group. Simulation results attest to the accuracy of our proposed model.

Many sensor network applications only require probabilistic data delivery, as they can tolerate some missing data samples. For example, in environmental monitoring, missing temperature, pressure and humidity level samples can often be inferred by spatial and/or temporal interpolations. In this paper we propose and study an adaptive p-persistent CSMA-based media access control protocol that supports end-to-end probabilistic reliability for sensor networks on a hop-by-hop basis. In an effort to reduce the probability of packet collisions, first we tune the carrier sensing range of the nodes; then given an end-to-end reliability requirement, we determine the optimal allocation of per-hop reliability requirements on each route to minimize the expected total number of transmissions needed; finally, our adaptive p-persistent CSMA protocol tunes its link persistence probability to further reduce the expected total number of transmissions, and thereby minimizes the energy consumption in the network. We formulate this latter problem as a constrained optimization problem, and then derive an algorithm to adapt the link persistence probabilities using the Lagrangian dual decomposition method.

A particularly severe attack on routing protocols in ad hoc networks is the so-called wormhole attack in which two or more colluding attacking nodes record packets at one location, and tunnel them to another location for a replay at that remote location. When this attack targets specifically routing control packets, the nodes that are close to the attackers are in effect shielded from finding any alternative routes to the remote location with more than one or two hops, and thus all the routes will be directed to the wormhole established by the attackers. In optimized link state routing protocol (OLSR), if a wormhole attack is launched during the propagation of link state packets, the wrong link information will propagate throughout the network, leading to routing disruption. In this paper, we devise an efficient method to detect wormhole attacks in the OLSR protocol. This method tries to ascertain the effective presence of neighbors by employing an efficient neighborhood detection algorithm. Our method has several advantages since it does not require any time synchronization or location information and shows high detection rate under various scenarios.

We present a novel fair queue management algorithm called stochastic RED (StoRED), inspired by the well known stochastic fair queuing and based on the random early detection (RED) scheme. By extensive simulations, we show the versatility of StoRED in disciplining misbehaving flows and achieving adjustable fairness in a variety of applications where there is a need to prevent unresponsive flows from overwhelming others. In another application, StoRED can also be invoked to improve the performance of Web traffic by reducing the probability of experiencing packet losses for such traffic. StoRED turns out to be an effective and practical algorithm that is ready for deployment.

The efficient use of energy in wireless sensor networks is critical issue as the battery of a sensor node, in most cases, cannot be recharged or replaced after deployment. In order to detect an event, a sensor node spends most of the time in monitoring its environment, during which a significant amount of energy can be saved by placing the radio in the low power sleep mode when no reception and/or transmission of data is involved. In this paper, we discuss the design of a new MAC protocol for wireless sensor networks whose goal is to extend the lifetime of the network by avoiding major energy waste causes, such as collisions, overhearing and idle listening, without compromising other network performance measures such as network throughput. The performance of the protocol is studied by simulation and is compared to that of the well known S-MAC protocol which is designed to save energy and to the IEEE 802.11 protocol which is designed to maximize throughput.

This paper studies the tradeoff between energy consumption and application performance in wireless sensor networks by investigating the interaction between network lifetime maximization and rate allocation problems. To guarantee the individual performance of sensor nodes, we adopt the network utility maximization (NUM) framework to ensure certain fairness on source rates of sensor nodes. We formulate the network lifetime maximization problem and fair rate allocation problem as constrained maximization problems, and combine them by introducing a system parameter, which characterizes the tradeoff between the two problems. Using Lagrange dual decomposition, the original problem is vertically decomposed into three subproblems: a rate control problem at the transport layer, a contention resolution problem at the MAC Layer, and a cross-layer energy conservation problem. The first and second subproblems jointly solve the congestion problem in sensor networks via congestion prices, and fully distributed algorithms are derived. Furthermore, they are coupled with the cross layer energy conservation problem to solve the network lifetime maximization problem via energy prices. For the third subproblem, we first propose a partially distributed algorithm where network lifetime is a global information, and then by exploring the similarity between max-min rate allocation and network lifetime maximization in sensor networks, we approximate the latter by the NUM framework, and hence formulate the tradeoff problem in the unified NUM framework. As a result, a fully distributed algorithm is derived for the energy conservation problem.

Energy consumption is a critical issue in wireless sensor networks as the battery of a sensor node, in most cases, cannot be recharged or replaced after deployment. In order to detect an event, a sensor node spends most of the time in monitoring its environment, during which a significant amount of energy can be saved by placing the radio in the low power sleep mode when no reception and/or transmission of data is involved. In this paper, we discuss the design of a new MAC protocol for wireless sensor networks, which mainly avoids overhearing, collisions, and frequent commutation between sleep and active modes. These issues are generally considered to be the most important reasons behind energy waste in heavy loaded conditions of wireless sensor networks. The proposed protocol, called Reservation-MAC (R-MAC), uses two separate periods during the communication process. In the first period, nodes compete for time slots reservation for their future transmissions, and in the second period, each node transmits its data or receive data from a corresponding sender. Once a node is aware of its transmission and/or reception time slot, it stays active only for these time slots and goes back to the sleep mode during the remaining time of the transmission period. In our experiments, the performance of the R-MAC protocol is studied in saturated conditions and compared with the well known S-MAC and T- MAC protocols. Depending on the traffic load, the proposed MAC protocol significantly improves the energy consumption compared to S-MAC and T-MAC.

In this paper, we propose and study two adaptive media access control protocols to support probabilistic data delivery reliability in sensor networks using MAC layer retransmissions. Since retransmissions consume energy, our adaptive p-persistent CSMA protocols tune their persistence probabilities in an effort to minimize the expected number of retransmissions that meet a given probabilistic reliability requirement, and thereby minimize energy consumption in the network. We formulate this problem of reliability with minimal energy consumption at the MAC layer as a constrained optimization problem and then derive the algorithms to adapt the persistence probabilities using the Lagrangian dual decomposition method.

A particularly severe attack on routing protocols in ad hoc networks is the so-called wormhole attack in which two or more colluding attacking nodes record packets at one location, and tunnel them to another location for a replay at that remote location. When this attack targets specifically routing control packets, the nodes that are close to the attackers are in effect shielded from finding any alternative routes to the remote location with more than one or two hops, and thus all the routes are directed to the wormhole established by the attackers. In optimized link state routing protocol (OLSR), if a wormhole attack is launched during the propagation of link state packets, the wrong link information propagates throughout the network, leading to routing disruption. In this paper, we devise an efficient method to detect and avoid wormhole attacks in the OLSR protocol. This method tries first to infer links that may potentially lead to wormhole tunnels. The proper wormhole detection was then be applied to suspicious links by means of an exchange of encrypted probing packets between the two supposed neighbors (endpoints of the wormhole). Our solution has several advantages since it does not require any time synchronization or location information and shows high detection rate under various scenarios.

Many communication and networking systems can be modeled as resource-sharing systems with multiple classes of calls. Call admission control (CAC) is an essential component of such systems. Markov decision process (MDP) tools can be applied to analyze and compute the optimal CAC policy that optimizes certain performance metrics of the system. But for most practical systems, it is prohibitively difficult to compute the optimal CAC policy using any MDP algorithm because of the "curse of dimensionality". We are, therefore, motivated to consider two families of structured CAC policies: reservation and threshold policies. These policies are easy to implement and have good performance in practice. However, since the number of structured policies grows exponentially with the number of call classes and the capacity of the system, finding the optimal structured policy is a complex unsolved problem. In this paper, we develop fast and efficient search algorithms to determine the parameters of the structured policies. We prove the convergence of the algorithms. Through extensive numerical experiments, we show that the search algorithms converge quickly and work for systems with large capacity and many call classes. In addition, the returned structured policies have optimal or near-optimal performance, and outperform those structured policies with parameters chosen based on simple heuristics

We model the problem of bandwidth sharing in wireless multi-hop networks as a general utility maximization problem with link bandwidth constraints. Lagrangean relaxation and duality are invoked to derive a gradient-based iterative algorithm to solve the problem. We then investigate the practical aspects of the problem and discuss how such theoretical framework can be used to design practical fair media access control frameworks that can be implemented in real systems based on the IEEE 802.11 distributed coordination function.

In this paper we study the correlations that exist between the required transmission power of RTS, CTS, DATA and ACK frames to guarantee a successful 4-way handshake in wireless ad hoc networks based on the IEEE 802.11 distributed coordination function (DCF). From these correlations, and starting from a set of different initial conditions, we can derive a class of power controlled media access control (MAC) algorithms for single channel ad hoc networks based on the existing IEEE 802.11 DCF. From substantial simulations of the different algorithms and comparison to some prominent alternatives, we come to a conclusion that contradicts the intuitively sound, commonly held belief which states that sending control frames at maximum power - to reduce interference on the long data frames - then, the ensuing long data frames at a lower, yet sufficient power level decreases power consumption per carried bit.

This paper considers the problem of routing in sensor networks from the point of view od data collection. That is, given the initial amount of battery energy in each node, the aim is to determine how much data can each source transmit until the network is partitioned (i. e., until the nodes cannot find end-to-end routes to their respective sinks). In addition, to respond to some specific applications' requirements, when determining such nodal data volume distribution, fairness among nodes is taken into account. The problem is formulated as a concave utility maximization and a sub-gradient algorithm is proposed to solve it distributively. Some numerical results are given and the convergence of the algorithm is discussed.

Sensor networks are deployed to gather some useful data from a field and forward it toward a set of base stations or sinks for data analysis and decision making. Each sensor node is endowed with a finite amount of energy, and each byte transmission or reception costs a certain fixed fraction of energy as well as a variable fraction that depends on the distance between sender and receiver. Maximizing the volume of data collected at the sinks until some particular set of nodes exhaust their battery and partition the network is a very desirable trait in sensor networks, as it equates with a high level of energy efficiency. In this paper we formulate the problem of maximum data collection routing for sensor networks as a utility maximization problem subject to energy constraints, and invoke lagrange relaxation, duality and sub-gradient technique to solve the problem. We then focus on the problem of path oscillation, which is well known to happen in routing algorithms where link costs are function of the traffic load and propose heuristic solutions to address this oscillation problem

The network lifetime and application performance are two fundamental but conflicting desig objectives in wireless sensor networks. Hence there is an intrinsic tradeoff between network lifetime maximization and application performance maximization. Often application performance correlates to the application data rate obtained in sensor networks. We can thus study this tradeoff by investigating the interactions between the network lifetime maximization problem and the rate allocation problem. Severe bias on the allocated rates of some sensor nodes may exist if only the total throughput of the sensor network is maximized, hence we enforce fairness on source rates of sensor nodes by invoking the network utility maximization (NUM) framework. First we consider the network lifetime as global information shared by sensor nodes. We formulate the network lifetime maximization and fair rate allocation both as constrained maximization problems. By introducing a system parameter, we combine these two objectives into a single weighted objective, and characterize the tradeoff between them. Then we give the optimality condition, and derive a partially distributed algorithm. Also, we identify the similarity between network lifetime maximization and max-min rate allocation in networks. Since the latter one can be approximated using NUM framework, we adopt the same idea for the former one, and approximate the optimal solution in the unified NUM framework. Based on this, an efficient fully distributed algorithm is derived.

End-to-end available bandwidth estimation is important in understanding network congestion and enhancing service quality. In this paper, we investigate a light-weight probing method for available bandwidth measurement in a queueing analysis approach. Unlike the self-congestion based measurement approach, a light-weight probing technique infers the available bandwidth along a path without congesting the routers along the path. Of particular interest in our investigations, is the squared coefficient of variation (SCV) of the inter-departure process of a periodic probing stream. We analyze approximately the departure process of this probing stream. Simulation results indicate that the proposed hybrid approximation can provide good estimates of the SCV of the probing stream regardless of the stochastic behavior of the arrival process of the cross traffic. Given a measured SCV, inverting this approximation infers the load of the cross traffic on the congested link.

Power control for mobile ad hoc networks has received increasing interest from the research community. Power control can be invoked to achieve different objectives, including the most popular goals of either increasing the network throughput by mitigating the effects of interference on a node or ensuring minimal power consumption. We propose a power control algorithm for ad hoc networks to improve network throughput. As such, we study and exploit the correlation that exists between the appropriate transmit power of successive RTS, CTS, DATA and ACK frames and propose an adaptive power control algorithm in the framework of the IEEE 802.11 MAC protocol. In contrast to some alternative approaches, our algorithm operates in a single channel and does not require additional hardware support, which makes it very appropriate for existing IEEE 802.11 based networks.

Many communications and networking systems can be modelled as resource-sharing systems with multiple classes of calls. Call admission control (CAC) is an essential component of such systems. For most practical systems it is prohibitively difficult to compute the optimal CAC policy that optimizes certain performance metrics because of the 'curse of dimensionality'. In this paper we study two families of structured CAC policies: threshold and reservation policies. These policies are easy to implement and have good performance in practice. However, since the number of structured policies grows exponentially with the number of call classes and the capacity of the system, finding the optimal structured policies is a complex unsolved problem. In this paper efficient search algorithms are proposed to find the coordinate optimal structured policies among all structured policies. Through extensive numerical experiments we show that the search algorithms converge quickly and work for systems with large capacity and many call classes. In addition, the returned structured policies have optimal or near-optimal performance, and outperform those structured policies with parameters chosen based on simple heuristics.

In this paper an adaptive opportunistic scheduling scheme is proposed for wireless LANs in the presence of a link adaptation scheme such as auto-rate fall-back (ARF). Extensive simulation experiments and scenarios have shown that this scheme outperforms other alternatives in terms of throughput as well as adaptation to different channel characteristics such as location dependent and bursty errors. Current work consists in implementing this algorithm in a real test-bed using IEEE802.11a/g wireless LAN access point.

Power control is often invoked in mobile ad hoc networks to achieve one of two popular goals: i) increasing network throughput by mitigating the effects of mutual interference of nodes or; ii) ensuring minimal power consumption. This paper proposes a new adaptive power control algorithm for ad hoc networks to save energy while maintaining a similar throughput as that achieved by the IEEE 802.11 MAC protocol. The contributions of this proposed scheme are two fold. First, we define and invoke the concept of MAC packet delivery curve to guide the power control algorithm in the adaptation decision under different possible scenarios. In particular when choosing among different service profiles the packet curve can tell which is better in the long term. Then, the power control algorithm takes into consideration the short term correlations between transmit powers of RTS/CTS frames and those of DATA/ACKs frames, to ensure robustness.

The high speed wireless local area network (WLAN) is emerging today as a strong contender for the last hop communication in the Internet. However, due to interference and time varying channel characteristics, the advertised data rates are seldom achieved. Link adaptation is the technique that allows a station to change the characteristics of its links (e.g., modulation scheme, frame size, coding rate, and so on) in order to improve the throughput. In this paper, we propose a link adaptation system that performs per frame fragment rate adaptation to quickly adapt to different channel states. The system comprises an online fragmentation module and a credit based scheduler and relies on a a pre-computed lookup table to determine the appropriate fragment size and rate that maximizes the throughput given the channel condition. Simulations performed under real world signal-to-noise (SNR) values show that the goodput of our system can reach twice that achieved by the well known autorate fallback (ARF) scheme when multiple stations with different channel characteristics co-exist in the network.

Multicode-code division multiple access (CDMA) supports a variety of transmission rates within a wireless network. However, providing packet-delay guarantees in a multicode-CDMA network is difficult because its transmission capacity is time varying even in an error-free wireless channel. In this paper, we develop a packet-scheduling algorithm called multicode-deficit round robin (DRR) as a solution to the problem. The basic idea of multicode-DRR is to separate the time-varying capacity into a deterministic component and a variable component, and to use these components to serve time-sensitive and non-time-sensitive traffic, respectively. With the proposed scheduling algorithm, simulation results have confirmed that the maximum packet delays for time-sensitive traffic never exceed their target upper bounds.

Providing quality of service (QoS) in wireless ad hoc networks introduces a major challenge due to their dynamic topologies. In general, a QoS scheme requires close collaboration between all layers in the protocol stack. At the base of the scheme is a QoS capable MAC protocol. In ad hoc networks nowadays, the widely deployed distributed coordination function (DCF) proposed by the IEEE 802.11 standard is a random access scheme and suffers from a fairness problem. In order to provide a guarantee of minimal throughput and improve the fairness of bandwidth sharing, a class of collision-free MAC scheduling algorithms is proposed. When implementing these algorithms, the set of node identifiers (IDs) that can connect to the network should be known in advance. In addition, neighborhood information sharing is required. Compared with their counterparts proposed in the literature, these algorithms can guarantee a minimal throughput and do not rely on per-packet information exchange. Simulation results show that these algorithms can provide better long term fairness when compared with IEEE 802.11 DCF, even when they are implemented in coarse time granularity.

Due to their dynamic topologies, providing quality of service (QoS) in wireless/mobile ad-hoc networks introduces major new challenges to the research community. Today, the only commercially available ad-hoc network products are those based on the widely deployed IEEE 802.11 distributed coordination function (DCF). However DCF is a random access scheme, which not only cannot provide any guarantees, is also well known to suffer from a problem of fairness. In this paper, the bandwidth allocation problem in the medium access control (MAC) layer of ad-hoc networks is modelled as a constrained maximization problem. Based on duality, the problem is further modelled as a cooperative game and an algorithm to solve this problem is provided, and the discussion is centered on the design and implementation issues of the algorithm.

In IEEE 802.11 WLANs, there are two types of access modes which perform very differently under different channel or traffic conditions: the basic access mode CSMA/CA and and an RTS/CTS based mechanisms. In seeking to balance between the use of the different modes, the contribution of this paper is threefold. Firstly, we present our development of a new method capable of calculating the access delay via an analytical model. Secondly, we report a comparison of the throughput and delay performance of basic and RTS/CTS mechanisms and the analysis of which mode should be chosen to obtain better throughput and delay performance under different conditions. Finally, we propose an adaptive RTS/CST mechanism that adjusts the RTS threshold adaptively in order to achieve optimal performance in a centralized or distributed way. Numerical results, and simulation results obtained using NS2 are provided.

The IEEE 802.11 working group is currently working on the standard IEEE 802.11e and introduces the hybrid coordination function (HCF) to provide better QoS support to real-time traffic. A reference design of simple scheduling and admission control algorithm is proposed in a TGe consensus proposal. However, this scheduling and admission control unit only consider the mean data rate and mean packet size. The rate and packet size variation are not taken into account. Thus, it is only efficient to CBR traffic and the packet loss rate of VBR traffic may be very high. In W. F. Fan et al. (Aug. 2004), we analyzed the packet loss rate of the reference scheme and proposed a new method to determine the effective TXOP duration for admission control so that the packet loss rate of VBR flows can be guaranteed. In both reference and our proposed scheme, all stations use fixed schedule service interval (SI) which is the minimum of all maximum service interval of all admitted flows. Thus, maximum packet delay of all stations is limited by the most stringent SI and some traffic with larger delay bound may be over-guaranteed. Also, the efficiency of the admission control scheme in W. F. Fan et al. (Aug. 2004), becomes lower than that of the reference one. We extend our admission control scheme by using variable service interval to improve the efficiency about 20% - 30% and avoid over guarantee on packet delay. Also, the packet loss rate of VBR traffic can be guaranteed.

This paper examines the theoretical aspects of bandwidth sharing in wireless, possibly mobile, ad-hoc networks (MANETs) through a game theoretic framework. It presents some applications to show how such a framework can be invoked to design efficient media access control protocols in a noncooperative, self-organized, topology-blind environment as well as in environments where the competing nodes share some basic information to guide their choice of channel access policies. For this purpose, contentions between concurrent links in a MANET are represented by a conflict graph, and each maximal clique in the graph defines a contention context which in turn imposes a constraint on the share of bandwidth that the links in the clique can obtain. Using this approach the fair bandwidth allocation problem is modeled as a general utility based constrained maximization problem, called the system problem, which is shown to admit a unique solution that can only be obtained when global coordination between all links is possible. By using Lagrange relaxation and duality theory, both a non-cooperative and a cooperative game formulation of the problem are derived. The corresponding mathematical algorithms to solve the two games are also provided where there is no need for global information. Implementation issues of the algorithms are also considered. Finally, simulation results are presented to illustrate the effectiveness of the algorithms.

This paper addresses the problem of modelling and analysing an interior node in IETF's DiffServ services model. Specifically it is concerned with the performance of the DiffServ assured forwarding service category in presence of a premium service class. In this model, the network node shares its outgoing link capacity between a premium service representing the expedited forwarding (EF) per-hop behavior, and two classes of assured service, that represent two classes of the assured forwarding (AF) per-hop behavior. It this paper, the traffic is modelled as Markov modulated fluid sources, and we focus on a system where out of profile traffic is dropped at the edge of the network thus both AF queues support only one drop precedence. Using a decomposition approach, approximations, and spectral analysis, we are able to derive upper and lower bounds on the tail of the distribution of the buffer content for both AF classes given a generalized processor sharing scheduling is used to differentiate the two classes. Such approximate analysis of the interaction between traffic classes can help to achieve a better understanding of this type of networks; enables the provision of throughput differentiation as defined by the AF PHB through the GPS scheduler while quantifying delay; and finally helps simplify greatly the design of bandwidth brokers that do not rely on long term bandwidth (over) provisioning.

In this paper, we investigated a non-intrusive probing methodology for available bandwidth measurement based on the analysis of the departure process of an active Poisson probing stream. Unlike the self-congestion based available bandwidth measurement, non intrusive techniques are meant to infer the available bandwidth along a path without congesting the path. We propose to probe the end-to-end path using small size packets with exponentially distributed time between consecutive probing packets. Of particular interest to our investigations, is the squared coefficient of variation (SCV) of the inter-departure process of the probing stream. The Internet is modelled as single server queue with two concurrent streams, the probing traffic stream and the cross traffic, we rely on the results on M/sub 1/ + M/sub 2//GI/sub i//1 queueing system and a heavy traffic approximation model to analyze the departure process of the probing stream. Thus, in a real measurement system, given the measured SCV of the probing stream, inverting the approximation helps inferring the load of the cross traffic on an end-to-end-path.

IEEE 802.11 wireless LAN is considered one of the most popular wireless technology all over the world because of its low cost and easy deployment. The support of quality of service (QoS) in medium access control (MAC) protocol is important in meeting the QoS requirements of real-time traffic such as guaranteed packet delay and packet loss probability. In this paper, the performance of the proposed admission control algorithm and different VBR video traffic are analyzed. In the analysis, three mean data rates of video flows ( 300 kbps, 600 kbps and 1 Mbps) were also considered.

We first present our recent work on the non-saturation modelling and performance analysis for IEEE 802.11 distributed coordination function. We extended the previous work and developed a model capable of reflecting the non-saturation condition. Employing the model, by introducing a concept of equivalent competing entity, we designed a measurement-aided model-based call admission control scheme for IEEE 802.11e WLANs contention-based channel access - enhanced distributed coordination function (EDCF) to provide guaranteed throughput quality of service (QoS) in a statistical sense. Extensive numerical and simulation results are provided.

The new standard IEEE 802.11e is specified to support quality-of-service in wireless local area networks. A comprehensive study of the performance of enhanced distributed channel access (EDCA), the fundamental medium access control mechanism in IEEE 802.11e, is reported in this paper. We present our development of an analytical model, in which most new features of the EDCA such as virtual collision, different arbitration interframe space (AIFS), and different contention window are taken into account. Based on the model, we analyze the throughput performance of differentiated service traffic and propose a recursive method capable of calculating the mean access delay. Service differentiation functionality and effectiveness of the EDCA are investigated through extensive numerical and simulation results. The model and the analysis provide an in-depth understanding and insights into the protocol and the effects of different parameters on the performance.

This paper introduces a new backoff mechanism for IEEE802.11, which aims to achieve fair channel access without knowledge of the network topology. By adjusting a time interval and the contention window dramatically, the algorithm aims to approach the optimal equilibrium where the time interval is the minimum possible such that every node that faces the same contention successfully sends only one packet per such interval. We show how this algorithm can be modeled as a game and use game theoretic arguments to prove the existence and uniqueness of the equilibrium as well as convergence of the algorithm to this equilibrium.

A MultiCode-CDMA network that is capable of providing quality-of-service guarantees will find widespread application in future wireless multimedia networks. However, providing delay guarantees to time-sensitive traffic in such a network is challenging because its transmission capacity is variable even in the absence of any channel impairment. We propose and evaluate the performance of a novel transmission scheduling scheme that is capable of providing such a delay guarantee in a MultiCode-CDMA network. The proposed scheme drops packets to ensure that delays for all transmitted packets are within the guaranteed target bounds, but packets are dropped in a controlled manner such that the average dropping ratios of a set of time-sensitive flows can be proportionally differentiated according to the assigned weighting factors or shares. We provide extensive simulation results to show the effectiveness of the proposed scheme as well as to study the effects of various parameters on its performance. In particular, we show that it can simultaneously guarantee a delay upper bound and a proportionally differentiated dropping ratio in a fading wireless channel for different traffic loads, peak transmission rates, and weighting factors of individual flows.

Due to hidden terminals and a dynamic topology, contention among stations in an ad-hoc network is not homogeneous. Some stations are at a disadvantage in opportunity of access to the shared channel and can suffer severe throughput degradation when the traffic load is high. This is the so-called "fairness problem" encountered mainly in existing MAC protocols such as IEEE 802.11 Distributed Foundation Wireless Medium Access Control (DFWMAC) that is used as a basis for most performance evaluation of routing protocols in mobile ad-hoc networks (MANET). The binary exponential backoff (BEB) used in DFWMAC protocol to resolve contention is known to always favor the last station that succeeds its transmission, which exacerbates the fairness problem in heavy traffic. This paper reviews a measurement-based backoff algorithm for the DFWMAC protocol that achieves statistical fair access to the shared medium, and then models analytically the resultant system as a feedback control system. The analytical model confirms the fairness property of the algorithm, as well as its convergence and show the impact of different parameters of the algorithm on the performance of the system.

Existing multicode-CDMA MAC protocols do only single dimensional access control either in the code or time domain, and thus result in a complex optimisation problem. In this paper, we propose a MAC protocol which can do simultaneous code-time access control to avoid the optimisation problem, and to achieve better system utilisation. In order to do that, the proposed protocol decouples the function of transmission ordering from the function of packing all the scheduled transmissions in the resource space. As such, different transmission scheduling algorithms can be adopted without altering the protocol. A water filling approach is used for efficient transmission packing where each of the scheduled transmissions is treated as a rectangular capsule with an arbitrary size and the resource space is viewed as a water container. Simulation results indicate that the proposed protocol can achieve higher throughput compared to single dimensional access control protocols. Therefore, the proposed MAC protocol is a more efficient one.

Multicode-CDMA is a good choice for wireless networking because it can support devices with different peak transmission rates within one network and hence, enables cost scalability. However, delivering delay guarantee in a multicode-CDMA network is difficult because its capacity is variable even in a perfect wireless channel. We develop a scheme called multicode-DRR as a solution to the problem. The basic idea of multicode-DRR is to separate the variable capacity into a deterministic component and a variable component, and to use these components to serve time-sensitive traffic and non-time-sensitive traffic, respectively. Simulation results confirm that the maximum time-sensitive packet delay never exceeds the theoretical upper bound when the devices are served using the proposed scheme. In short, multicode-DRR is significant because it enables a multicode-CDMA network to deliver deterministic upper delay guarantee.

Future wireless networks need to support different service requirements. Ho-sever, the exiting methods of specifying QoS commitments, namely qualitative commitment and quantitativ e commitment are not perfect for a wireless communication environment. In this paper, we propose a new concept called compound QoS commitment which combines qualitative and quantitative commitments within a single service commitment. As such, the proposed concept can provide a practical approach to deal with the highly variable wireless netw ork capacijr. Since each compound QoS commitment has tw o degrees of freedom, it m\ also increase the fiexibilit y in committing an ahievable QoS. In order to show the feasibility of the proposed concept, we present a scheduling algorithm whic hcan sim ultaneouslypro vide a proportional dropping ratio guarantee and a deterministic upper delay guarantee to a flow. Numerical results confirm that the algorithm is capable of delivering the tw o guarantees simultaneously.

This paper addresses the problem of fairness in wireless ad-hoc networks. Usually, the problem of fairness in wireless ad-hoc networks is addressed in a classic approach inherited from wired networks. The common assumption is that nodes/flows have pre-assigned fair shares. The task becomes then to modify wired networks' fair queueing algorithms to address wireless network nature. Wired networks have efficient means of allocating fiar shares through admission control and additionally, the fair shares remain constant throughout the session duration due to the static nature of the nodes. In ad-hoc networks, it is meaningless to assume statically pre-assigned fair shares, since on one hand, not only the nodes move, but also the routers are mobile, and on the other hand, contention is location dependent, such that in terms of absolute guarantees, fairness would at most mean "avoiding starvation": thus applying rate proportional fiar queueing algorithms is beyond the original goal of such algorithm, viz. flow isolation/protection and bandwidth guarantee. In this work we argue in favor of multi-level scheduling for wireless ad-hoc networks with max-min fair allocation of the fair shares at the lower-most layer (MAC layer). This paper, mainly lays down the theoretical framework by which one can calculate the fair shares that would achieve max-min fairness in an ad-hoc network. We design distributed algorithms that allow each node to determine its max-min per-link fair share in a global ad-hoc network without knowledge of the global topology of the network. The results are then used in conjunction with a novel practical scheduling algorithm for IEEE 802.11 to show how fairness is achieved

This paper proposes a simple rate-based scheduling algorithm for packet-switched networks. Using a set of counters to keep track of the credits accumulated by each traffic flow, the bandwidth share allocated to each flow, and the size of the head-of-line (HOL) packets of the different flows, the algorithm decides which flow to serve next. Our proposed algorithm requires on average a smaller complexity than the most interesting alternative ones while guaranteeing comparable fairness, delay, and delay jitter bounds. To further reduce the complexity, a simplified version (CBFQ-F) of the general algorithm is also proposed for networks with fixed packet lengths, such as ATM, by relaxing the fairness bound by a negligibly small amount.

Wireless environment properties, such as fading, multipath and interference, mean that the capacity is time-varying and the errors are location dependent. This makes it difficult to directly extend algorithms developed for wire-line networks to wireless networks. In order to support relatively differentiated QoS requirements over a time-varying shared wireless medium with location-dependent errors, we propose in this paper a wireless fair scheduling algorithm which tries both to provide short-term fairness in the rate proportional guarantee sense and to maintain a reasonable system throughput. We present both the numerical and simulation results in this paper to verify that CS-WFQ (channel-state independent wireless fair queueing) has improved the short-term fairness property in error-prone wireless environments.

The medium access control (MAC) protocol through which mobile stations can share a common broadcast channel is essential in an ad-hoc network. Due to the existence of the hidden terminal problem, partially-connected network topology and lack of central administration, existing popular MAC protocols like IEEE 802.11 Distributed Foundation Wireless Medium Access Control (DFWMAC) may lead to "capture" effects which means that some stations grab the shared channel and other stations suffer from starvation. This is also known as the "fairness problem". This paper reviews some related work in the literature and proposes a general approach to address the problem. This paper borrows the idea of fair queueing from wireline networks and defines the "fairness index" for ad-hoc network to quantify the fairness, so that the goal of achieving fairness becomes equivalent to minimizing the fairness index. Then this paper proposes a different backoff scheme for IEEE 802.11 DFWMAC, instead of the original binary exponential backoff scheme. Simulation results show that the new backoff scheme can achieve far better fairness without loss of simplicity.

Future wireless mobile multimedia networks are likely to adopt micro/pico cellular architectures. A consequence of using small cell sizes is the increased rate of call handoffs as mobile terminals move between cells during the holding times of the calls. In a network supporting multimedia services, the increased rate of call handoffs makes it very difficult for the network to guarantee the quality of service (QoS) promised to a call at setup. This paper describes a handoff priority scheme which reduces the probability of call handoff failures in such a mobile multimedia network. The impact of this admission control policy on packet level performance is studied analytically for a homogeneous network supporting a mix of wideband and narrowband calls.

We propose a fuzzy logic-based control scheme for real-time motion picture expert group (MPEG) video to avoid long delay or excessive loss at the user-network interface (UNI) in an asynchronous transfer mode (ATM) network. The system consists of a shaper whose role is to smooth the MPEG output traffic to reduce the burstiness of the video stream. The input and output rates of the shaper buffer are controlled by two fuzzy logic-based controllers. To avoid a long delay at the shaper, the first controller aims to tune the output rate of the shaper in the video frame time scale based on the number of available transmission credits at the UNI and the occupancy of the shaper's buffer. Based on the average occupancy of the shaper's buffer and its variance, the second controller tunes the input rate to the shaper over a much larger time scale by applying a closed-loop MPEG encoding scheme. With this approach, the traffic enters the network at an almost constant bit rate (with a very small variation) allowing simple network management functions such as admission control and bandwidth allocation, while guaranteeing a relatively constant video quality since the encoding rate is changed only in critical periods when the shaper buffer "threatens" to overflow. The performance of the proposed scheme is evaluated through numerical tests on real video sequences.

Estimating the cell loss probability in an ATM multiplexer is a key issue in network management and traffic control such as call admission control and bandwidth allocation. In this paper, we derive a new approximation to estimate the total and individual cell loss probabilities in an ATM multiplexer fed by a superposition of heterogeneous on-off sources with exponentially distributed on and off periods. Based on this approximation, a simple and accurate method is proposed to estimate the aggregate required bandwidth by a given mix of traffic to guarantee a given cell loss probability.

An important parameter in asynchronous transfer model (ATM)-based network design and management is the cell loss ratio (CLR) in ATM multiplexers. It is a key parameter to many vital functions in the network such as call admission control (CAC), bandwidth allocation, etc. However, the CLR depends usually on many unknown and unpredictable traffic parameters such as input traffic correlations. In this paper, we propose a simple and robust fuzzy-based algorithm to predict the CLR in large-sized systems based on both a small amount of information from small-sized systems, and the asymptotic behavior for very large systems. Unlike the model-based approaches, our approximation avoids the problem of assuming any traffic parameters or arrival process. This algorithm is used with real-time traffic measurement to propose an effective measurement-based call admission control framework for ATM networks.