In many applications, the traffic traversing the network has interpacket dependencies due to application-level encoding schemes. For some applications, e.g., multimedia streaming, dropping a single packet may render useless the delivery of a whole sequence. In such environments, the algorithm used to decide which packet to drop in case of buffer overflows must be carefully designed, to avoid goodput degradation. We present a model that captures such interpacket dependencies, and design algorithms for performing packet discard. Traffic consists of an aggregation of multiple streams, each of which consists of a sequence of interdependent packets. We provide two guidelines for designing buffer management algorithms, and demonstrate their effectiveness. We devise an algorithm according to these guidelines and evaluate its performance analytically, using competitive analysis. We also perform a simulation study that shows that the performance of our algorithm is within a small fraction of the performance of the best known offline algorithm.

In this paper we consider the classical network formation problem where nodes want to connect to other nodes that have similar “interests”. This problem is of fundamental importance in the network formation of peer-to-peer networks and online social networks. For this problem, we study whether there exists an algorithm that is robust with respect to the underlying interest graph that models the similarity of nodes in the networks. With robust, we mean that the algorithm is simple and achieves high-performance for a variety of interest graph models. The concrete interest graph models that we consider are the widely used planted partition and latent space model. We propose a network formation mechanism based on a cosine-neighbourhood refinement step and formally show that it performs well for the planted partition model. In addition, it can be shown that this mechanism based on cosine-neighbourhood refinement step also performs well under a latent space model for a one-dimensional sphere. To the best of our knowledge, this is the first time that a network formation mechanism has been shown to be robust and perform well for both the planted partition and latent space model. The proposed algorithm is simple and can be implemented in a distributed or centralized manner.

In this paper, we consider CSMA policies for scheduling packet transmissions in multihop wireless networks with one-hop traffic. The main contribution of the paper is to propose a novel CSMA policy, called Unlocking CSMA (U-CSMA), that enables to obtain both high throughput and low packet delays in large wireless networks. More precisely, we show that for torus interference graph topologies with one-hop traffic, U-CSMA is throughput optimal and achieves order-optimal delay. For one-hop traffic, the delay performance is defined to be order-optimal if the delay stays bounded as the network-size increases. Simulations that we conducted suggest that (a) U-CSMA is throughput-optimal and achieves order-optimal delay for general geometric interference graphs and (b) that U-CSMA can be combined with congestion control algorithms to maximize the network-wide utility and obtain order-optimal delay. To the best of our knowledge, this is the first time that a simple distributed scheduling policy has been proposed that is both throughput/utility optimal and achieves order-optimal delay.

A fundamental challenge in peer-to-peer and online social networks is the design of a simple, distributed algorithm that allows users to discover, and connect to, peers who closely match their interests or preferences. In this paper, we consider an algorithm that is based on simple, local comparisons, and analyze it to provide insights into why similar peer discovery algorithms work well in practice. To do so, we use a mathematical framework to characterize the closeness of individual interests, and formally introduce the notion of a “perfect network formation” under the framework. Our analysis shows that the proposed algorithm indeeds achieves perfect network formation. Our analysis uses bounding techniques based on Chernoff bounds.

We analyze asynchronous carrier sense multiple access (CSMA) policies for scheduling packet transmissions in multihop wireless networks subject to collisions under primary interference constraints. While the (asymptotic) achievable rate region of CSMA policies for single-hop networks has been well-known, their analysis for general multihop networks has been an open problem due to the complexity of complex interactions among coupled interference constraints. Our work resolves this problem for networks with primary interference constraints by introducing a novel fixed-point formulation that approximates the link service rates of CSMA policies. This formulation allows us to derive an explicit characterization of the achievable rate region of CSMA policies for a limiting regime of large networks with a small sensing period. Our analysis also reveals the rate at which CSMA achievable rate region approaches the asymptotic capacity region of such networks. Moreover, our approach enables the computation of approximate CSMA link transmission attempt probabilities to support any given arrival vector within the achievable rate region. As part of our analysis, we show that both of these approximations become (asymptotically) accurate for large networks with a small sensing period. Our numerical case studies further suggest that these approximations are accurate even for moderately sized networks.

In many applications the traffic traversing the network has inter-packet dependencies due to application-level encoding schemes. For some applications, e.g., multimedia streaming, dropping a single packet may render useless the delivery of a whole sequence. In such environments, the algorithm used to decide which packet to drop in case of buffer overflows must be carefully designed, to avoid goodput degradation. We present a model that captures such inter-packet dependencies, and design algorithms for performing packet discards. Traffic consists of an aggregation of multiple streams, each of which consists of a sequence of inter-dependent packets. We provide two guidelines for designing buffer management algorithms for this problem, and demonstrate the effectiveness of these criteria. We devise an algorithm according to these guidelines and evaluate its performance analytically, using competitive analysis. We also present a simulation study that shows that the performance of our algorithm is within a small fraction of the performance of the best offline algorithm.

Activity in social media such as blogs, micro-blogs, social networks, etc is manifested via interaction that involves text, images, links and other information items. Naturally, some items attract more attention than others, expressed with large volumes of linking, commenting or tagging activity, to name a few examples. Moreover, high attention can be indicative of emerging events, breaking news or generally indicate information items of interest to a vast set of people. The numbers associated with digital social activity are astonishing: in excess of millions of blog posts, tweets and forums updates per day, millions of tags in photos, news articles or blogs. Being able to identify information items that gather much attention in such a real time information collective is a challenging task.

We propose a novel search mechanism for unstructured p2p networks, and show that it is both scalable, i.e., it leads to a bounded query traffic load per peer as the peer population grows, and reliable, i.e., it successfully locates all files that are (sufficiently often) brought into the system. To the best of our knowledge, this is the first time that a search mechanism for unstructured p2p networks has been shown to be both scalable and reliable. We provide both a formal analysis and a numerical case study to illustrate this result. Our analysis is based on a random graph model for the overlay graph topology and uses a mean-field approximation to characterize the evolution of how files are replicated in the network.

We consider the problem of ranking the popularity of items and suggesting popular items based on user feedback. User feedback is obtained by iteratively presenting a set of suggested items, and users selecting items based on their own preferences either from this suggestion set or from the set of all possible items. The goal is to quickly learn the true popularity ranking of items (unbiased by the made suggestions), and suggest true popular items. The difficulty is that making suggestions to users can reinforce popularity of some items and distort the resulting item ranking. The described problem of ranking and suggesting items arises in diverse applications including search query suggestions and tag suggestions for social tagging systems. We propose and study several algorithms for ranking and suggesting popular items, provide analytical results on their performance, and present numerical results obtained using the inferred popularity of tags from a month-long crawl of a popular social book marking service. Our results suggest that lightweight, randomized update rules that require no special configuration parameters provide good performance.

Wireless social community networks are emerging as a new alternative to providing wireless data access in urban areas. By relying on users in the network deployment, a wireless community can rapidly deploy a high-quality data access infrastructure in an inexpensive way. But, the coverage of such a network is limited by the set of access points deployed by the users. Currently, it is not clear if this paradigm can serve as a replacement of existing centralized networks operating in licensed bands (such as cellular networks) or if it should be considered as a complimentary service only, with limited coverage. This question currently concerns many wireless network operators. In this paper, we study the dynamics of wireless social community networks by using a simple analytical model. In this model, users choose their service provider based on the subscription fee and the offered coverage. We show how the evolution of social community networks depends on their initial coverage, the subscription fee, and the user preferences for coverage. We conclude that by using an efficient static or dynamic pricing strategy, the wireless social community can obtain a high coverage. Using a game-theoretic approach, we then study a case where the mobile users can choose between the services provided by a licensed band operator and those of a social community. We show that for specific distribution of user preferences, there exists a Nash equilibrium for this non-cooperative game.

In this paper, we consider hybrid peer-to-peer systems where users form an unstructured peer-to-peer network with the purpose of assisting a server in the distribution of data. We present a mathematical model that we use to analyze the scalability of hybrid peer-to-peer systems under two query propagation mechanisms: the random walk and the expanding ring. In particular, we characterize how the query load at the server, the load at peers as well as the query response time scale as the number of users in the peer-to-peer network increases. We show that, under a properly designed random walk propagation mechanism, hybrid peer-to-peer systems can support an unbounded number of users while requiring only bounded resources both at the server and at individual peers. This important result shows that hybrid peer-to-peer systems have excellent scalability properties. To the best of our knowledge, this is the first time that a theoretical study characterizing the scalability of such hybrid peer-to-peer systems has been presented. We illustrate our results through numerical studies.

We propose a distributed scheduling and active queue management mechanism for wireless ad hoc networks. The approach is based on a random access scheduler where the transmission attempt probabilities depend on the local backlog. The resulting mechanism is simple and can be implemented in a distributed fashion. The performance of the resulting protocol can be modelled as a utility maximization problem to establish that it indeed leads to a high throughput and fair bandwidth allocation.

We use a mathematical model based on Brownian motion to analyze the performance of Last Encounter Routing (LER), a routing protocol for ad hoc networks. Our results show that, under our model, LER outperforms the simple flooding mechanism employed by reactive protocols.

We study the interaction between rate control and medium access control in wireless networks.We start out by developing a discrete time model for the interaction of TCP Renorate ontrol and IEEE 802.11 medium acess control. Considering the operating point of the system, we obtain the well-known characteristics that the throughput decreases as the number of nodes in the network increases and that IEEE 802.11 does not provide per-flow fairness. We then propose and study alternative rate and medium acess control schemes which allow to offer per-flow fairness, as well as provide a stable and predictable throughput as the number of nodes increases.

We propose a model under which several inherent properties of the exponential age search routing protocol can be derived. By making simplifications on this model, we are able to address the issue of the optimality of a parameter of the protocol and to improve the existing upper bound on its performance.

We study how selfish nodes react to transmission costs in wireless networks. Intuitively, it seems that transmission costs should have a stabilizing effect as (rational) nodes defer the packet transmissions when congestion develops and the cost for (successfully) transmitting a packet becomes high. In this paper we investigate whether this intuition is true. We use slotted Aloha to model the communication channel.

We consider a market-based approach to stimulate cooperation in ad hoc networks where nodes charge a price for relaying data packets. Assuming that nodes set prices to maximize their own net benefit, we characterize the equilibria of the resulting market. In addition, we propose an iterative algorithm for the nodes to adapt their price and rate allocation, and study its convergence behavior. We use a numerical case study to illustrate our results.

We study a price-based rate control mechanism for random access networks. The mechanism uses channel feedback information to control the aggregate packet arrival rate. For our analysis, we use the standard slotted Aloha model with an infinite set of nodes. We show that the resulting Markov chain is positive recurrent. In addition, we characterize the throughput and delay at the operating point of the system and show how the operating point can be set a priori by appropriately choosing the control parameters. We illustrate our results using numerical experiments.

We analyze a static pricing scheme for priority services. Users are free to choose the priority of their traffic but are charged accordingly. Using a game theoretic framework, we study the case where users choose priorities to maximize their net benefit. For the single link case, we show that there always exists an equilibrium for the corresponding game; however, the equilibrium is not necessarily unique. Furthermore, we show that packet loss in equilibrium can be expressed as a function of the prices associated with the different priority classes. We provide a numerical case study to illustrate our results.

Pricing is considered as a means to stimulate cooperation in ad hoc networks: users can charge other users a price for relaying their data packets. Assuming that users set prices to maximize their own net benefit, we propose an iterative price and rate adaption algorithm. We show that this algorithm converges to a socially optimal bandwidth allocation. We use a numerical case study to illustrate our results.

We study a priority service where users are free to choose the priority of their traffic, but are charged accordingly by the network. We assume that each user chooses priorities to maximize its own net benefit, and model the resulting interaction among users as a noncooperative game. We show that there exists an unique equilibrium for this game and that in equilibrium the bandwidth allocation is weighted max-min fair.

We study a pricing scheme for networks which use priorities to provide differentiated quality of service. We consider the situation where users are free to choose the priority of their traffic, but are charged accordingly. We model this situation as a non-cooperative game, where users behave in a selfish manner and choose an allocation of priorities to packets to optimize their own net benefit. We show that there exists an unique equilibrium for this game and the bandwidth allocation in equilibrium is weighted max-min fair.

This paper considers resource allocation and pricing for the downlink of a wireless network. We describe a model that applies to either a time-slotted system (e.g. Qualcomm's HDR proposal) or a CDMA system; the main feature of this model is that the channel quality varies across the users. We study using a pricing scheme for the allocation of radio resources. We show that to maximize revenue in such a system, the base station should allocate resources in a discriminatory manner, where different users are charged different prices based in part on their channel quality. However, optimally allocating resources in this way is shown to require knowledge about each user's utility function. We consider a suboptimal scheme which does not require knowledge of the users' utility functions, and show that this scheme is asymptotically optimal, in the limit of large demand. Moreover, such a scheme is shown to maximize social welfare. We also consider a heuristic scheme for the case of small demand, which does not require perfect knowledge about the users' utility functions. We provide numerical results that illustrate the performance of this heuristic.

We study the role of pricing in differentiated services (Diff-Serv) networks. We model DiffServ as a priority service, where users are given the freedom to choose the priorities of their traffic, but are charged accordingly. Using a game theoretic framework, we study the case where users choose an allocation of priorities to packets in order to optimize their net benefit. For the case where users with bursty traffic access a single link, we show that there always exists an equilibrium for the corresponding noncooperative game. Furthermore we show that pricing can be used to provide relative QoS guarantees.

We consider the problem of call admission control (CAC) and routing in an integrated services network that handles several classes of calls of different value and with different resource requirements. The problem of maximizing the average value of admitted calls per unit time (or of revenue maximization) is naturally formulated as a dynamic programming problem, but is too complex to allow for an exact solution. We use methods of neuro-dynamic programming (NDP) [reinforcement learning (RL)], together with a decomposition approach, to construct dynamic (state-dependent) call admission control and routing policies. These policies are based on state-dependent link costs, and a simulation-based learning method is employed to tune the parameters that define these link costs. A broad set of experiments shows the robustness of our policy and compares its performance with a commonly used heuristic.

We are interested in solving large-scale Markov decision problems. The classical method of dynamic programming provides a mathematical framework for finding optimal solutions for a given Markov decision problem. However, dynamic programming algorithms become computationally infeasible when the underlying Markov decision problem evolves over a large state space. In recent years, a new methodology, called neuro-dynamic programming, has emerged which tries to overcome this "curse of dimensionality". We show how neuro-dynamic programming can be applied to the admission control problem for a single link in an ATM environment. Based on results obtained through neuro-dynamic programming, we derive a heuristic "threshold" policy. Performances of the policies obtained through neuro-dynamic programming are compared with a policy which always accepts a customer when the required resources are available.