WiFi networks suffer from severe network utility degradation due to the usage of diverse modulation and coding schemes. The proportional-fair allocation, that has been shown to be a good remedy, can be enforced through the proper selection of contention window values. This has been achieved so far for centralized systems by an explicit solution of an optimization problem or, as proposed recently, by following a learning-based approach. In this paper, we present the first fully distributed solution in which each of the WiFi nodes independently tunes its contention window to achieve proportional fairness. Our solution is therefore applicable also for a set of collocated, unconnected WiFi networks. We compare the throughput and air-time allocation that this algorithm achieves to the values achieved by standard WiFi binary exponential back-off and values achieved by known centralized algorithms.

Recent developments of smart devices and mobile applications have significantly increased the level at which human users interact with mobile systems. As a result, human activities, usage behavior, and perceived experience of users weigh increasingly on the performance of mobile networks, which has created new challenges for system operation in various aspects, such as increasing uncertainty, selfishness in operations, and complicated performance evaluation. On the other hand, the strong engagement of a large population of human users makes it possible to take advantage of the unique features of human behavior and to leverage the computing powers owned by users. Due to these emerging features of mobile networks, their design and evaluation require a hybrid view of human factor and information technology, and a paradigm shift is required for designing a new human-in-the-loop architecture by actively learning, adapting, and steering user behavior, so as to exploit the human factor in future ubiquitous mobile systems, and to greatly enhance system efficiency and provide superior quality-of-experience to users. The goal of this survey is to summarize recent results that focus on understanding and exploiting the human factor in mobile networks. In the tutorial, we summarize and discuss novelties of these formulations, adopted methodologies, and interesting results. We also point out some future research directions.

No abstract available.

Sensor nodes equipped with renewable energy sources are capable of recharging their batteries and supporting data collection and transmission indefinitely. Energy and data management of these types of systems is challenging primarily due to the variability of renewable energy sources and transmission channels. This paper explores a methodology for designing the control of such systems. The goal is to jointly control the energy usage and data sampling rate to maximize the long-term performance of the system subject to the constraints imposed by the available energy and data. The design of this control is based on estimates of the large deviations of the energy stored in the battery and of the queued data. A low-complexity control policy is proposed that does not depend on the instantaneous charge of the battery and data backlog and almost maximizes the long-term data transmission rate. Moreover, the results show that one can decouple the analysis of the energy and of the data queue without much loss in performance.

As the successor to the 3G standard, the 4G cellular standard provides much higher data rates to address cellular users' ever-increasing demands for high-speed multimedia communications. This paper analyzes the cellular operators' timing of network upgrades, by considering user subscription dynamics induced by switching from 3G to 4G technologies. Being the first to upgrade 3G to 4G service, an operator increases its market share but takes more risk or upgrade cost as 4G technology matures overtime. This paper first studies a 4G monopoly market with one dominant operator and some small operators, where the monopolist decides its upgrade time by trading off increased market share and upgrade cost. The paper also considers a 4G competitive market and develops a game theoretic model for studying operators' interactions. The analysis shows that operators select different upgrade times to avoid severe competition. One operator takes the lead to upgrade, using the benefit of a larger market share to compensate for the larger cost of an early upgrade. This result matches well with many industry observations of asymmetric4G upgrades. The paper further shows that the availability of 4G upgrade may decrease both operators' profits due to increased competition. Perhaps surprisingly, the profits can increase with the upgrade cost.

This paper analyzes and compares different incentive mechanisms for a master to motivate the collaboration of smartphone users on both data acquisition and distributed computing applications. To collect massive sensitive data from users, we propose a reward-based collaboration mechanism, where the master announces a total reward to be shared among collaborators, and the collaboration is successful if there are enough users wanting to collaborate. We show that if the master knows the users' collaboration costs, then he can choose to involve only users with the lowest costs. However, without knowing users' private information, then he needs to offer a larger total reward to attract enough collaborators. Users will benefit from knowing their costs before the data acquisition. Perhaps surprisingly, the master may benefit as the variance of users' cost distribution increases. To utilize smartphones' computation resources to solve complex computing problems, we study how the master can design an optimal contract by specifying different task-reward combinations for different user types. Under complete information, we show that the master involves a user type as long as the master's preference characteristic outweighs that type's unit cost. All collaborators achieve a zero payoff in this case. If the master does not know users' private cost information, however, he will conservatively target at a smaller group of users with small costs, and has to give most benefits to the collaborators.

Today’s communication networks and networked systems are highly complex and heterogeneous \nand are often owned by profit-making entities. For new technologies or \ninfrastructure designs to be adopted, they must not only be based on sound engineering \nperformance considerations but also present the right economic incentives. Recent \nchanges in regulations of the telecommunication industry make such economic considerations \neven more urgent. For instance, new concerns such as network neutrality \nhave a significant impact on the evolution of communication networks. \nAt the same time, communication networks and networked systems support increasing \neconomic activity based on applications and services such as cloud computing, \nsocial networks, and peer-to-peer networks. These applications pose new challenges \nincluding the development of good pricing and incentive mechanisms to promote effective \nsystem-wide behavior. Similarly, the security and privacy of these applications are \nthemselves heavily dependent on economic considerations, which therefore need to be \nfully understood. \nTo address these questions, this special issue brings together a relevant set of state-of-the-art research contributions on complementary topics including communication \nnetworks, wireless networks, web content and security, and the use of multidisciplinary \napproaches ranging from game theory and economic modeling to algorithms \nand mechanism design, and including empirical studies.

As the successor to the 3G standard, 4G provides much higher data rates to address cellular users' ever-increasing demands for high-speed multimedia communications. This paper analyzes the cellular operators' timing of network upgrades and models that users can switch operators and services. Being the first to upgrade 3G to 4G service, an operator increases his market share but takes more risk or upgrade cost because 4G technology matures over time. This paper first studies a 4G monopoly market with one dominant operator and some small operators, where the monopolist decides his upgrade time by trading off increased market share and upgrade cost. The paper also considers a 4G competition market and develops a game theoretic model for studying operators' interactions. The analysis shows that operators select different upgrade times to avoid severe competition. One operator takes the lead to upgrade, using the benefit of a larger market share to compensate for the larger cost of an early upgrade. This result matches well with many industry observations of asymmetric 4G upgrades. The paper further shows that the availability of 4G upgrade may decrease both operators' profits due to increased competition. Perhaps surprisingly, the profits can increase with the upgrade cost.

Benes networks are constructed with simple switch modules and have many advantages, including small latency and requiring only an almost linear number of switch modules. As circuit-switches, Benes networks are rearrangeably non-blocking, which implies that they are full-throughput as packet switches, with suitable routing. Routing in Benes networks can be done by time-sharing permutations. However, this approach requires centralized control of the switch modules and statistical knowledge of the traffic arrivals. We propose a backpressure-based routing scheme for Benes networks, combined with end-to-end congestion control. This approach achieves the maximal utility of the network and requires only four queues per module, independently of the size of the network.

This paper proposes a new type of range-free localization method based on affine transformation. Nodes extract subgraphs with a grid topology from a sensor network and assign x-y coordinates to themselves in a decentralized manner. The nodes estimate their positions using an affine transformation based on the mapping of the physical positions and the x-y coordinates of three anchors in an extracted graph. In contrast with multilateration-based localization methods, the proposed method works well even in a non-convex hull deployment, such as a terrain with big regions without sensors. We provide a theoretical analysis and simulation results. We also present a strategy for minimizing the position estimation error and maximizing the coverage of the proposed method. In the simulation results, the position estimation error is 0.18 (normalized by the radio communication range) and the coverage is almost 100% in a non-convex hull deployment.

This paper analyzes and compares different incentive mechanisms for a client to motivate the collaboration of smartphone users on both data acquisition and distributed computing applications. Data acquisition from a large number of users is essential to build a rich database and support emerging location-based services. We propose a reward-based collaboration mechanism, where the client announces a total reward to be shared among collaborators, and the collaboration is successful if there are enough users willing to collaborate. We show that if the client knows the users' collaboration costs, then he can choose to involve only users with the lowest costs by offering a small total reward. However, if the client does not know users' private cost information, then he needs to offer a larger total reward to attract enough collaborators. Users will benefit from knowing their costs before the data acquisition. Distributed computing aims to solve computational intensive problems in a distributed and inexpensive fashion. We study how the client can design an optimal contract by specifying different task-reward combinations for different user types. Under complete information, we show that the client will involve a user type as long as the client's preference for that type outweighs the corresponding cost. All collaborators achieve a zero payoff in this case. But if the client does not know users' private cost information, he will conservatively target at a smaller group of efficient users with small costs. He has to give most benefits to the collaborators, and a collaborator's payoff increases in his computing efficiency.

Glauber dynamics is a powerful tool to generate randomized, approximate solutions to combinatorially difficult problems. It has been recently used to design distributed carrier-sense multiple-access (CSMA) scheduling algorithms for multihop wireless networks. In this paper, we derive bounds on the mixing time of a generalization of Glauber dynamics where multiple links update their states in parallel and the fugacity of each link can be different. The results are used to prove that the average queue length (and hence, the delay) under the parallel-Glauber-dynamics-based CSMA grows polynomially in the number of links for wireless networks with bounded-degree interference graphs when the arrival rate lies in a fraction of the capacity region. Other versions of adaptive CSMA can be analyzed similarly. We also show that in specific network topologies, the low-delay capacity region can be further improved.

Networking researchers complain that the current Internet is ossified, i.e. that it can hardly be changed. We believe that one of the fundamental reasons for that is the lack of appropriate incentives for providers to invest in new technology, especially in the absence of a compelling new architecture and a killer application that would benefit from an alternative architecture. There is a chicken-and-egg problem: In order to come up with exciting new applications, there needs to be an infrastructure supporting them. Researchers have proposed to build network testbeds (e.g. GENI/FIRE) to test new network architectures and protocols at larger scale. However, these testbeds appear to have little attraction for users, in particular for commercially oriented application developers. OpenFlow is an alternative approach enabling experimental protocols in production networks. However, one of its limitations is lack of addressing provider incentives. In this position paper, we therefore sketch the characteristics that we think a new Internet platform should have in order to be compelling. We argue for a platform that offers rich programmability at low performance cost and that separates traffic to enhance security and limit interference among applications. Moreover, the platform should be open and accessible to a wide community of users and have a high usability in terms of being easily programmable by application developers. Finally, we believe the new platform should provide support for running sophisticated applications across multiple provider domains.

Glauber dynamics is a powerful tool to generate randomized, approximate solutions to combinatorially difficult problems. It has been recently used to design distributed CSMA scheduling algorithms for multi-hop wireless networks. In this paper, we derive bounds on the mixing time of a generalization of Glauber dynamics where multiple links update their states in parallel and the fugacity of each link can be different. The results are used to prove that the average queue length (and hence, the delay) under the parallel-Glauber-dynamics-based CSMA grows polynomially in the number of links for wireless networks with bounded-degree interference graphs when the arrival rate lies in a fraction of the capacity region. Other versions of adaptive CSMA can be analyzed similarly.

We study a network security game where strategic players choose their investments in security. Since a player's investment can reduce the propagation of computer viruses, a key feature of the game is the positive externality exerted by the investment. With selfish players, unfortunately, the overall network security can be far from optimum. The contributions of this paper are as follows. 1) We first characterize the price of anarchy (POA) in the strategic-form game under an “Effective-investment” model and a “Bad-traffic” model, and give insight on how the POA depends on individual players' cost functions and their mutual influence. We also introduce the concept of “weighted POA” to bound the region of payoff vectors. 2) In a repeated game, players have more incentive to cooperate for their long term interests. We consider the socially best outcome that can be supported by the repeated game, as compared to the social optimum. 3) Next, we compare the benefits of improving security technology and improving incentives, and show that improving technology alone may not offset the price of anarchy. 4) Finally, we characterize the performance of correlated equilibrium (CE). Although the paper focuses on network security, many results are generally applicable to games with positive externalities .

It was shown recently that carrier sense multiple access (CSMA)-like distributed algorithms can achieve the maximal throughput in wireless networks (and task processing networks) under certain assumptions. One important but idealized assumption is that the sensing time is negligible, so that there is no collision. In this paper, we study more practical CSMA-based scheduling algorithms with collisions. First, we provide a Markov chain model and give an explicit throughput formula that takes into account the cost of collisions and overhead. The formula has a simple form since the Markov chain is “almost” time-reversible. Second, we propose transmission-length control algorithms to approach throughput-optimality in this case. Sufficient conditions are given to ensure the convergence and stability of the proposed algorithms. Finally, we characterize the relationship between the CSMA parameters (such as the maximum packet lengths) and the achievable capacity region.

This paper provides proofs of the rate stability, Harris recurrence, and ε-optimality of carrier sense multiple access (CSMA) algorithms where the random access (or backoff) parameter of each node is adjusted dynamically. These algorithms require only local information and they are easy to implement. The setup is a network of wireless nodes with a fixed conflict graph that identifies pairs of nodes whose simultaneous transmissions conflict. The paper studies two algorithms. The first algorithm schedules transmissions to keep up with given arrival rates of packets. The second algorithm controls the arrivals in addition to the scheduling and attempts to maximize the sum of the utilities, in terms of the rates, of the packet flows at different nodes. For the first algorithm, the paper proves rate stability for strictly feasible arrival rates and also Harris recurrence of the queues. For the second algorithm, the paper proves the ε-optimality in terms of the utilities of the allocated rates. Both algorithms are iterative and we study two versions of each of them. In the first version, both operate with strictly local information but have relatively weaker performance guarantees; under the second version, both provide stronger performance guarantees by utilizing the additional information of the number of nodes in the network.

In multihop wireless networks, designing distributed scheduling algorithms to achieve the maximal throughput is a challenging problem because of the complex interference constraints among different links. Traditional maximal-weight scheduling (MWS), although throughput-optimal, is difficult to implement in distributed networks. On the other hand, a distributed greedy protocol similar to IEEE 802.11 does not guarantee the maximal throughput. In this paper, we introduce an adaptive carrier sense multiple access (CSMA) scheduling algorithm that can achieve the maximal throughput distributively. Some of the major advantages of the algorithm are that it applies to a very general interference model and that it is simple, distributed, and asynchronous. Furthermore, the algorithm is combined with congestion control to achieve the optimal utility and fairness of competing flows. Simulations verify the effectiveness of the algorithm. Also, the adaptive CSMA scheduling is a modular MAC-layer algorithm that can be combined with various protocols in the transport layer and network layer. Finally, the paper explores some implementation issues in the setting of 802.11 networks.

This paper investigates Internet service provider (ISP) incentives with a single-service class and with two-service classes in the Internet. We consider multiple competing ISPs who offer network access to a fixed user base, consisting of end-users who differ in their quality requirements and willingness to pay for the access. We model user-ISP interactions as a game in which each ISP makes capacity and pricing decisions to maximize its profits and the end-users only decide which service to buy (if any) and from which ISP. Our model provides pricing for networks with single- and two-service classes for any number of competing ISPs. Our results indicate that multiple service classes are socially desirable, but could be blocked due to the unfavorable distributional consequences that it inflicts on the existing Internet users. We propose a simple regulatory tool to alleviate the political economic constraints and thus make multiple service classes in the Internet feasible.

Femtocells or home base stations are a proposed solution to the problem of degraded indoor service from the macrocell base station in future 4G data networks. In this paper, we study user incentives for the adoption of femtocells and their resulting impact on network operator revenues. We model a monopolist network operator who offers the option of macrocell access or macro+femtocell access to a population of users who possess linear valuations for the data throughput. We compare the revenues from two possible spectrum schemes for femtocell deployment; the split spectrum scheme, where femtocells and macrocells operate on different frequencies and do not interfere, and, the common spectrum scheme, where they operate on the same frequencies (partially or fully) and interfere. Our results suggest that the optimal pricing scheme always charges a higher price for the femtocell service, i.e., the operator does not offer any subsidies for adoption. Yet, at the optimal prices, almost full adoption of femtocells is achieved even for many common spectrum schemes that degrade macrocell capacity. Femtocell deployments provide huge revenue gains when macrocell capacities are low. However, in this range, even common spectrum schemes that heavily degrade the macrocell capacity perform comparably to the split spectrum scheme. Some common spectrum schemes with moderate macrocell degradation yield revenues comparable or higher than the split spectrum scheme at all levels of macrocell congestion.

In this paper, we devise a novel method for bottleneck analysis of UDP networks based on the concept of network utility maximization. To determine the losses on the links in a UDP network, we propose an optimization problem (geometric program) for which we find and prove conditions under which it accurately determines the true losses. We further extend this analysis to stochastic rates using stochastic optimization techniques and provide a new metric to flag bottleneck links. This method does not rely on time-consuming packet-level simulations, but is instead based on robust mathematical models. Alternatively, one could determine the losses by solving a fixed point problem and extend it to random rates using a Monte Carlo simulation. However, lack of knowledge of convergence makes it difficult to predict the end of such simulations. Our method is more advantageous as it involves solving an optimization problem, the solution to which can be numerically determined to the desired accuracy. Also, compared to a black and white approach between worst-case analysis and average-case analysis, our method offers network managers the flexibility of choosing the shades of gray in between.

We consider a multi-cell wireless network with a large number of users. Each user selfishly chooses the Base Station (BS) that gives it the best throughput (utility), and each BS allocates its resource by some simple scheduling policy. First we consider two cases: (1) BS allocates the same time to its users; (2) BS allocates the same throughput to its users. It turns out that, combined with users' selfish behavior, case (1) results in a single Nash Equilibrium (NE), which achieves system-wide Proportional Fairness. On the other hand, case (2) results in many possible Nash Equilibria, some of which are very inefficient. Next, we extend (1) to the case where the users have general concave utility functions. It is shown that the if each BS performs intra- cell optimization, the total utility of all users is maximized at NE. This suggests that under our model, the task of joining the ";correct"; BS can be left to individual users, leading to a distributed solution.

In ISM bands, many wireless protocols proliferate such as 802.11, Bluetooth, and ZigBee. However, these incompatible protocols create complex coexistence and connectivity problems. If the same trend continues, similar interference and performance problems will continue to exist in future unlicensed bands. As new unlicensed bands open up, one can take a different approach to spectrum sharing. Instead of proposing a new MAC protocol for each type of application, we propose a family of parameterized MAC protocols called WiFlex that can tailor to different application needs ranging from wireless sensors to media center. Yet, these protocols within this family are compatible with each other to allow communication and spectrum-sharing coordination among different types of devices. We envision this family to be based on an OFDM-like multichannel physical layer. The contribution of this paper includes the discovery of an asynchronous split phase (ASP) protocol with dynamic priority support. This protocol enables powerful devices to achieve a high throughput and protects low power devices with urgent but only occasional transmissions. It is distributed and data collision-free. Moreover, it can support low delays for real time applications. The performance of the protocols are evaluated using an extension of NS-2. The results demonstrate the coexistence of devices with disparate radio characteristics and the support of applications with different requirements with good performance.

The 26 papers in this special issue focus on game theory in communication systems. The papers are grouped in four clusters according to their topics: (1) Physical layer models in wireless communications, (2) higher layer and cross-layer issues in wireless communications, (3) wire-line communication networks, and (4) specific topics including peer-to-peer networking, network coding, and network security.

This paper compares, analytically and through simulations, a number of multichannel MAC protocols. We first classify these protocols into four categories based on their principles of operation: Dedicated Control Channel, Common Hopping, split phase, and parallel rendezvous protocols. We then examine the effects of the number of channels and devices, channel switching times, and traffic patterns on the throughput and delay of the protocols. Here are some of the conclusions of our study: 1) Parallel Rendezvous protocols perform generally better than Single Rendezvous protocols; 2) Dedicated Control Channel protocols can be a good approach with its simplicity when the number of channels is high and the packets are long; 3) Split Phase protocol is very sensitive to the durations of the control and data phases. Our study focuses on a single collision domain.

Many distributed multiple access (MAC) protocols use an exponential backoff mechanism. In that mechanism, a node picks a random backoff time uniformly in an interval that doubles in size after a collision. When used in an ad-hoc network spanning multiple interference domains, this backoff mechanism is unfair towards nodes in the middle of the network. Indeed, such nodes tend to experience more collisions than nodes with fewer neighbors; consequently they choose larger backoff delays than those other nodes; and as a result, get lesser throughput. We propose a different backoff mechanism that achieves a fairer allocation of the available bandwidth, by decreasing the backoff delay upon collision or failure to send a packet. That is, a node becomes more aggressive after each failure. Accordingly, we call this mechanism the impatient backoff algorithm (IBA). The nodes maintain stability of the algorithm by resetting, in a distributed way, the average backoff delays if they become too small. We perform a Markov analysis of the system to prove stability and fairness in simple topologies. We also use simulations to study the performance of IBA in random ad-hoc networks, and compare with an exponential backoff scheme. Results show that IBA achieves comparable mean throughput, while delivering significantly better fairness.

An unequal importance communication approach, for cheap, reliable and real-time image communication over heterogeneous networks and its applications in mobile multimedia communication systems is presented. Here, an image is partitioned into different layers of importance: base layer and enhancement layers. The low-rate base layer description, which can be strongly protected, is transmitted through a low-bandwidth, but robust and more expensive channel, supporting delay-sensitive applications (e.g. GSM network), while the high-rate enhancement layer description(s) are transmitted through a high-bandwidth, but high/variable-delay and cheap channel which does not support delay-sensitive applications (e.g. WLAN). In the receiver, when the base layer description is quickly received, an acceptable quality image is reconstructed, and when the enhancement layer description(s) are received a high quality image can be reconstructed. Our practical results indicated that this effective, flexible, and highly compatible method not only facilitates high quality image distribution among heterogeneous networks and increases the coverage, quality of service, and bandwidth and power efficiency but also decreases the delay and cost of image distribution in mobile communication systems.

Many multiple channel MAC protocols for wireless networks have been proposed to make efficient use of multiple channels where each node has a single radio which allows it to send or receive on one channel at a time. However, most of the proposed protocols are single rendezvous protocols that are subject to the congestion of the control channel. The paper proposed a new parallel rendezvous protocol, McMAC, to avoid control channel congestion so that it can scale to use a large number of channels efficiently. The authors validate the protocol design using simulation and implementation.

Researchers have proposed many wireless MAC protocols such as [20], [8], [25], [24], [6], and [17] which exploit frequency-agile radios and multiple available channels to increase network through-put. These protocols usually only require each node to have one radio. By carefully coordinating the frequency hopping of different nodes, different node pairs can use multiple channels simultaneously. In [17], Mo et al classified these protocols into four generalized categories and compared their performances through both analysis and simulation. They found that the Parallel Rendezvous family of protocols has the best overall performance by removing the bottleneck of a single control channel. These protocols show good promise for use with multi-hop networks because these networks suffer from self-interference and traditional MAC protocols using only one channel often fail to provide satisfactory throughput. However, we are not aware of any implemented Parallel Rendezvous multi-channel MAC protocols. We argue one major reason is that existing proposals such as McMAC[17] and SSCH[6] have not thoroughly considered a practical aspect of the design essential for a working implementation, namely: synchronization. Through an exploration including an implementation exercise on hardware, we show that synchronization for multi-channel MAC protocols is a non-trivial problem. We designed and implemented a synchronization mechanism specifically for this purpose and show that it has tackled the problem of synchronizing one-hop neighbor pairs effectively, thereby paving the way for efficient multi-channel MAC protocols.

In this paper, we revisit the optimization based control problem of wireless ad-hoc networks. Even though much work has been done so far, they are limited either in their practicality or in their efficiency. We develop another framework based on independent set and propose an implementable heuristic algorithm. Our heuristic is based on the longest queue first (LQF) policy and the neighborhood price.

One of the challenges facing the networking industry today is to increase the profitability of Internet services. This calls for economic mechanisms that can enable providers to charge more for better services and collect a fair share of the increased revenues. In this paper, we present a generic pricing model for Internet services jointly offered by a group of providers. We show that noncooperative pricing strategies may lead to unfair distribution of profit and may even discourage future upgrades to the network. As an alternative, we propose a fair revenue-sharing policy based on the weighted proportional fairness criterion. We show that this fair allocation policy encourages collaboration among providers, and hence can produce higher profits for all providers. Based on the analysis, we suggest a scalable algorithm for providers to implement this policy in a distributed way and study its convergence property.

Traditional distributed algorithms for QoS routing in wired networks may not work in the ad-hoc domain, due to interference between links. We propose a heuristic interference-aware QoS routing algorithm (IQRouting) that chooses candidate paths based on localized information at the source nodes. The candidate paths are compared in a distributed manner using probe packets, with the best path confirmed by the destination node. Simulations demonstrate significant (up to 30 %) improvements in admission ratio over traditional shortest path algorithms, and better performance than other QoS routing algorithms in literature as well.

One of the critical challenges facing the networking industry today is to increase the profitability of Internet services. One well-known method in economics for increasing the revenues of a service is to segment its market through differentiation. However, special characteristics of Internet services, such as congestion externality, may complicate the design and provisioning of such offerings. In this paper, we study how a provider should price its services differentially based on their characteristics. By using a game-theoretic approach, we show that even with a simple two-class differentiated service model, if prices are not properly matched with service qualities, then the system may settle into an undesirable equilibrium similar to that in the classical "prisoner's dilemma" game. In addition, there may not even be a stable equilibrium under certain conditions. We then show that dynamic pricing approaches, in which prices are chosen according to users' relative preferences over different service classes, may be used to avoid such types of problems.

One of the challenges facing the networking industry today is to increase the profitability of Internet services. This calls for economic mechanisms that can enable providers to charge more for better services and collect a fair share of the increased revenues. In this papery we present a generic model for pricing Internet services that are jointly offered by a group of providers. We show that non-cooperative pricing strategies between providers may lead to unfair distribution of profit and may even discourage future upgrades to the network. As an alternative, we propose a fair revenue-sharing policy based on the weighted proportional fairness criterion. We show that this fair allocation policy encourages collaboration among providers and hence can produce higher profits for all providers. Based on the analysis, we suggest a scalable algorithm for providers to implement this policy in a distributed way and study its convergence property.

The problem of computing bandwidth guaranteed paths for given flow requests in an ad-hoc network is complicated because neighboring links share the medium. We define the path width on top of the conflict-graph based interference model, and present the ad-hoc shortest widest path (ASWP) routing problem in an ad-hoc network context. We propose a distributed algorithm to address the ASWP problem. Adopting the Bellman-Ford architecture and the k-shortest-path approach, the proposed algorithm achieves a performance close to the optimum. Numerical simulations demonstrate the performance of the algorithm, and also analyze gains achieved over prevalent shortest-path algorithms.

This paper compares, through analysis and simulation, a number of multichannel MAC protocols for wireless networks. We first classify these protocols into 4 categories based on their principles of operation. We then examine the effects of the number of channels and devices, channel switching times, and traffic patterns on throughput and delay. Our study focuses on a single collision domain.

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

We study QoS routing in wireless networks. We impose a structure on the network to combat the far-reaching effects of interference. We observe that there is little difference between routes through shared interference domains; instead the choices exist between routes through different domains. Based on this observation, we suggest partitioning the network into non-overlapping clusters where each cluster represents an interference domain. Routing algorithms operate over the cluster-level topology and use shortest paths within the clusters. Clustering decouples the constraints allowing for estimates of the available capacity within a cluster via local measurements. We present a routing algorithm that chooses amongst cluster-level paths to accommodate a flow with certain QoS requirements. An admission control policy checks the feasibility of the suggested route and refines our estimates of available capacity.

The capacity of an ad-hoc network is severely affected by interference between links, and several efforts to model this effect make use of 'clique' structures in the ad-hoc graphs. We propose a fully distributed heuristic algorithm to approximate cliques in such networks. We further propose methods to shrink the generated set of cliques to a set of maximal cliques. Simulation results verify the efficacy of the heuristic algorithms and also analyze their computation time.

The increasing presence of UDP traffic in the Internet and the emergence of sensing applications which do not require full reliability motivates the search for a robust acknowledgement scheme for unreliable flows. TCP-styled cumulative ack relies on the eventual retransmission of all lost packets and hence cannot be used for unreliable flows. Our contribution is the design and analysis of a simple, yet robust acknowledgement scheme for unreliable flows. We show that our scheme achieves good performance even when the actual network conditions deviate from the designer's estimate. It works in networks having orders of magnitude difference in bandwidth and loss probability, with little variation of overhead and no change to the algorithms.

Provides an overview of the technical articles and features presented in this issue.

In this paper we propose a modification of the explicit congestion notification (ECN) to correct the bias against connections with long round trip times (RTT) of TCP. The new-ECN algorithm achieves a fair sharing of the available bandwidth of a bottleneck gateway. The idea is to prevent a fast connection from opening its congestion window too quickly and to enable a slow connection to open its window more aggressively. This is done by modifying not only the congestion window size but also by modifying its rate of increase. Both are reduced while receiving marked packets and are increased during times of no congestion. We demonstrate the effect and performance of the new-ECN algorithm with the network simulator "ns" for different network topologies. Additionally, we study the TCP and ECN-TCP friendliness of the new-ECN algorithm. In this paper we only focus on the single bottleneck case. The behavior of new-ECN with multiple congested gateways needs further research.

Traditional traffic engineering for communication networks assumes that the sources generate traffic with known statistics. Using simulation and/or analysis, one then studies the quality of service that the network offers to these traffic streams. However, most of the traffic in the Internet is TCP-based. TCP, the Transmission Control Protocol, regulates the delivery of packets to correct errors and avoid saturating the destination of the packets or routers inside the network. Accordingly, the traffic that a TCP source generates is not specified a priori. Instead, this traffic depends in an essential way on the QoS that the network provides. We propose a simple model and we use it to predict the QoS that a network provides to TCP connections. The tool can compute the probability that each connection gets at least some given throughput. Conversely, the tool can be used to design the network to ensure that every connection gets a given throughput with a specified probability. The tool incorporates uncertainties about the load on the network and about the model.

Provides an abstract of the keynote presentation and a brief professional biography of the presenter. The complete presentation was not made available for publication as part of the conference proceedings.

In this paper, we demonstrate the existence of fair end-to-end window-based congestion control protocols for packet-switched networks with first come-first served routers. Our definition of fairness generalizes proportional fairness and includes arbitrarily close approximations of max-min fairness. The protocols use only information that is available to end hosts and are designed to converge reasonably fast. Our study is based on a multiclass fluid model of the network. The convergence of the protocols is proved using a Lyapunov function. The technical challenge is in the practical implementation of the protocols.

We propose a novel explicit rate flow control algorithm intended for available-bit-rate (ABR) service on an ATM network subject to loss and fairness constraints. The goal is to guarantee low cell loss in order to avoid throughput collapse due to retransmission by higher level protocols. The mechanism draws on measuring the current queue length and bandwidth availability, as well as tracking the current number of active sessions contending for capacity, to adjust an explicit bound on the source transmission rates. We identify the factors that affect queue overflows and propose simple design rules aimed at achieving transmission with controlled loss in a dynamic environment. We also discuss how conservative design rules might be relaxed by accounting for statistical multiplexing in bandwidth sharing among bursty ABR sources and variable-bit-rate (VBR) sources.

We propose some improvements of TCP Vegas and compare its performance characteristics with TCP Reno. We argue through analysis that TCP Vegas, with its better bandwidth estimation scheme, uses the network resources more efficiently and fairly than TCP Reno. Simulation results are given that support the results of the analysis.

It is well known that head-of-line blocking limits the throughput of an input-queued switch with first-in-first-out (FIFO) queues. Under certain conditions, the throughput can be shown to be limited to approximately 58.6%. It is also known that if non-FIFO queueing policies are used, the throughput can be increased. However, it has not been previously shown that if a suitable queueing policy and scheduling algorithm are used, then it is possible to achieve 100% throughput for all independent arrival processes. In this paper we prove this to be the case using a simple linear programming argument and quadratic Lyapunov function. In particular, we assume that each input maintains a separate FIFO queue for each output and that the switch is scheduled using a maximum weight bipartite matching algorithm. We introduce two maximum weight matching algorithms: longest queue first (LQF) and oldest cell first (OCF). Both algorithms achieve 100% throughput for all independent arrival processes. LQF favors queues with larger occupancy, ensuring that larger queues will eventually be served. However, we find that LQF can lead to the permanent starvation of short queues. OCF overcomes this limitation by favoring cells with large waiting times.

It is well known that head-of-line (HOL) blocking limits the throughput of an input-queued switch with FIFO queues. Under certain conditions, the throughput can be shown to be limited to approximately 58%. It is also known that if non-FIFO queueing policies are used, the throughput can be increased. However it has not been previously shown that if a suitable queueing policy and scheduling algorithm are used then it is possible to achieve 100% throughput for all independent arrival processes. In this paper we prove this to be the case using a simple linear programming argument and quadratic Lyapunov function. In particular we assume that each input maintains a separate FIFO queue for each output and that the switch is scheduled using a maximum weight bipartite matching algorithm.

This paper is principally concerned with resource allocation for connections tolerating statistical quality of service (QoS) guarantees in a public wide-area ATM network. Our aim is to sketch a framework, based on effective bandwidths, for call admission schemes that are sensitive to individual QoS requirements and account for statistical multiplexing. Results approximating the effective bandwidth required by heterogeneous streams sharing buffered links, including results for the packetized generalized processor sharing service discipline, are described. Extensions to networks follow via the concept of decoupling bandwidths, motivated by a study of the input-output properties of queues. Based on these results we claim that networks with sufficient routing diversity will inherently satisfy nodal decoupling. We then discuss on-line methods for estimating the effective bandwidth of connection. Using this type of traffic monitoring we propose an approach to usage parameter control (i.e., policing) for effective bandwidth descriptors. Finally, we suggest how on-line monitoring might be combined with admission control to exploit unknown statistical multiplexing gains and thus increase utilization.>

Addresses the issue of call acceptance and routing in ATM networks. The goal is to design an algorithm that guarantees bounds on the fraction of cells lost by a call. The method proposed for call acceptance and routing does not require models describing the traffic. Each switch estimates the additional fraction of cells that would be lost if new calls were routed through the switch. The routing algorithm uses these estimates. The estimates are obtained by monitoring the switch operations and extrapolating to the situation where more calls are routed through the switch. The extrapolation is justified by a scaling property. To reduce the variance of the estimates, the switches calculate the cell loss that would occur with virtual buffers. A way to choose the sizes of the virtual buffers in order to minimize the variance is discussed. Thus, the switches constantly estimate their spare capacity. Simulations were performed using Markov fluid sources to test the validity of the approach.>

The authors consider buffer asymptotics for feed-forward networks shared by heterogeneous traffic streams. This is done by identifying the effective bandwidth of the departure processes from shared queues. They introduce the idea of decoupling bandwidths and constraints which guarantee "decoupled" asymptotics within the network. They discuss these results in the context of resource management for ATM networks.>

We consider parameter estimation for a FIFO queue with deterministic service times and two independent arrival streams of "observed" and "unobserved" packets. The arrivals of unobserved packets are Poisson with an unknown rate /spl lambda/ while the arrivals of observed packets are arbitrary. Maximum likelihood estimation of /spl lambda/ is formulated based on the arrival times and waiting times of k observed packets. The likelihood function is derived in terms of the transition probabilities of the unfinished work process which are calculated recursively. Sufficient conditions for consistency, asymptotic normality, and asymptotic efficiency are given. The mean and variance of the MLE are measured in simulation experiments. Numerical results indicate that the MLE is consistent and asymptotically normal.>

The relative entropy between two Markov transition rate matrices is derived from sample path considerations. This relative entropy is interpreted as a level-2.5 large-deviations action functional. That is, the level-two large-deviations action functional for empirical distributions of continuous-time Markov chains can be derived from the relative entropy using the contraction mapping principle.>

The authors show the existence of effective bandwidths for multiclass Markov fluids and other types of sources that are used to model ATM traffic. More precisely, it is shown that when such sources share a buffer with deterministic service rate, a constraint on the tail of the buffer occupancy distribution is a linear constraint on the number of sources. That is, for a small loss probability one can assume that each source transmits at a fixed rate called its effective bandwidth. When traffic parameters are known, effective bandwidths can be calculated and may be used to obtain a circuit-switched style call acceptance and routing algorithm for ATM networks. The important feature of the effective bandwidth of a source is that it is a characteristic of that source and the acceptable loss probability only. Thus, the effective bandwidth of a source does not depend on the number of sources sharing the buffer or the model parameters of other types of sources sharing the buffer.>

The general problem of parallel (concurrent) processing is investigated from a queuing theoretic point of view. As a basic simple model, consider infinitely many processors that can work simultaneously, and a stream of arriving jobs, each carrying a processing time requirement. Upon arrival, a job is allocated to a processor and starts being executed, unless it is blocked by another one already in the system. Indeed, any job can be randomly blocked by any preceding one, in the sense that it cannot start being processed before the one that blocks it leaves. After execution, the job leaves the system. The arrival times, the processing times and the blocking structures of the jobs form a stationary and ergodic sequence. The random precedence constraints capture the essential operational characteristic of parallel processing and allow a unified treatment of concurrent processing systems from such diverse areas as parallel computation, database concurrency control, queuing networks, flexible manufacturing systems. The above basic model includes the G/G/1 and G/G/∞ queuing systems as special extreme cases. Although there is an infinite number of processors, the precedence constraints induce a queuing phenomenon, which, depending on the loading conditions, can lead to stability or instability of the system. In this paper, the condition for stability of the system is first precisely specified. The asymptotic behavior, at large times, of the quantities associated with the performance of the system is then studied, and the degree of parallelism, expressed as the asymptotic average number of processors that work concurrently, is computed. Finally, various design and simulation aspects concerning parallel processing systems are considered, and the case of finite number of processors is discussed. The results proved for the basic model are then extended to cover more complex and realistic parallel processing systems, where each job has a random internal structure of subtasks to be executed according to some internal precedence constriants.

The Programmable Network Prototyping System (PNPS), which is a rapid-prototyping tool used for emulating a wide variety of communication networks, is discussed. There are two parts to the PNPS hardware: the reusable hardware modules and the control and observation system. The reusable hardware modules consist of a channel emulator and a collection of node emulators. The channel emulator can be programmed to behave like a variety of network topologies, and each node emulator is configured to behave like a node on a network under study. The control and observation system links these modules together for configuration, experimentation, and monitoring purposes. There are three phases to using PNPS. first, the various components of a proposed network are designed. Next, the components are combined and run on the hardware while its behavior is monitored. Finally, the monitoring data is analyzed in order to evaluate the network design. A menu-driven user interface guides the user through the various tools of the system.>

Since the reconstruction of continuous speech from voice packets is complicated by the variable delays of the packets through the network, a dynamic priority protocol is proposed to minimize the variability of packet delays. The protocol allows the priority of a packet to vary with time. After a discussion of the concept of dynamic priorities, two examples of dynamic priorities are studied through queueing analysis and simulations. Optimal properties of the oldest customer first (OCF) and earliest deadline first (EDF) disciplines are proven, suggesting that they may be theoretically effective in reducing the variability of packet delays. Simulation results of the OCF discipline indicate that the OCF discipline is most effective under conditions of long routes and heavy traffic, i.e., the conditions when delay variability is most likely to be significant. Under OCF, the delays of packets along long routes are improved at the expense of packets along short routes. It is noted that more complex and realistic simulations, including simulations of the EDF discipline, are needed.>

An overview of distributed simulation of discrete event systems and the issues associated with it. Alternative approaches for decomposing the simulation into tasks that can be run on separate processors are described, and the potential parallelism associated with certain kinds of decomposition is studied. Existing synchronization algorithms are discussed. An attempt is made throughout to show what decomposition approaches and synchronization algorithms may be appropriate depending on properties of the application and the multiprocessor architecture. Empirical and analytical performance studies are described, where available.>

Probabilistic arguments are given to explain some recent results on networks of queues. Those results are the product form, the output theorems, the distributions at the jumps, and the Poisson character of the flows. The proposed approach replaces the usual calculations by arguments showing these properties to be consequences of the behavior of the nodes in isolation.

The symbols produced by a finite Markov source are causally encoded so as to be transmitted through a noisy memoryless channel. The encoder is assumed to have channel feedback information and the decoder to be causal. The feedback information is shown to be useful in general. Separation results are derived and used to prove that encoding is useless for a class of symmetric channels.