IEEE/ACM Transactions on Networking

The capacity of ad hoc wireless networks is constrained by the mutual interference of concurrent transmissions between nodes. We study a model of an ad hoc network where n nodes communicate in random source-destination pairs. These nodes are assumed to be mobile. We examine the per-session throughput for applications with loose delay constraints, such that the topology changes over the time-scale of packet delivery. Under this assumption, the per-user throughput can increase dramatically when nodes are mobile rather than fixed. This improvement can be achieved by exploiting a form of multiuser diversity via packet relaying.

In order to stem the increasing packet loss rates caused by an exponential increase in network traffic, the IETF has been considering the deployment of active queue management techniques such as RED (random early detection) (see Floyd, S. and Jacobson, V., IEEE/ACM Trans. Networking, vol.1, p.397-413, 1993). While active queue management can potentially reduce packet loss rates in the Internet, we show that current techniques are ineffective in preventing high loss rates. The inherent problem with these algorithms is that they use queue lengths as the indicator of the severity of congestion. In light of this observation, a fundamentally different active queue management algorithm, called BLUE, is proposed, implemented and evaluated. BLUE uses packet loss and link idle events to manage congestion. Using both simulation and controlled experiments, BLUE is shown to perform significantly better than RED, both in terms of packet loss rates and buffer size requirements in the network. As an extension to BLUE, a novel technique based on Bloom filters (see Bloom, B., Commun. ACM, vol.13, no.7, p.422-6, 1970) is described for enforcing fairness among a large number of flows. In particular, we propose and evaluate stochastic fair BLUE (SFB), a queue management algorithm which can identify and rate-limit nonresponsive flows using a very small amount of state information.

We consider the definition of the expedited forwarding per-hop behavior (EF PHB) as given in RFC 2598 and its impact on worst case end-to-end delay jitter. On the one hand, the definition in RFC 2598 can be used to predict extremely low end-to-end delay jitter, independent of the network scale. On the other hand, the worst case delay jitter can be made arbitrarily large, while each flow traverses at most a specified number of hops, if we allow networks to become arbitrarily large; this is in contradiction with the previous statement. We analyze where the contradiction originates and find the explanation. It resides in the fact that the definition in RFC 2598 is not easily implementable in known schedulers, mainly because it is not formal enough and also because it does not contain an error term. We propose a new definition for the EF PHB, called "packet scale rate guarantee" (PSRG) that preserves the spirit of RFC 2598 while allowing a number of reasonable implementations and has very useful properties for per-node and end-to-end network engineering. We show that this definition implies a rate-latency service curve property. We also show that it is equivalent, in some sense, to the stronger concept of "adaptive service guarantee". Then we propose some proven bounds on delay jitter for networks implementing this new definition in cases without loss and with loss.

Online social networks have been one of the most effective platforms for marketing and advertising. Through the “world-of-mouth” exchanges, so-called viral marketing, the influence and product adoption can spread from few key influencers to billions of users in the network. To identify those key influencers, a great amount of work has been devoted for the influence maximization (IM) problem that seeks a set of k seed users that maximize the expected influence. Unfortunately, IM encloses two impractical assumptions: 1) any seed user can be acquired with the same cost and 2) all users are equally interested in the advertisement. In this paper, we propose a new problem, called cost-aware targeted viral marketing (CTVM), to find the most costeffective seed users, who can influence the most relevant users to the advertisement. Since CTVM is NP-hard, we design an efficient (1 - 1/√e - ∈)-approximation algorithm, named Billion-scale Cost-award Targeted algorithm (BCT), to solve the problem in billion-scale networks. Comparing with IM algorithms, we show that BCT is both theoretically and experimentally faster than the state-of-the-arts while providing better solution quality. Moreover, we prove that under the linear threshold model, BCT is the first sub-linear time algorithm for CTVM (and IM) in dense networks. We carry a comprehensive set of experiments on various real-networks with sizes up to several billion edges in diverse disciplines to show the absolute superiority of BCT on both CTVM and IM domains. Experiments on Twitter data set, containing 1.46 billions of social relations and 106 millions tweets, show that BCT can identify key influencers in trending topics in only few minutes.

The paper considers the problem of minimizing the energy used to transmit packets over a wireless link via lazy schedules that judiciously vary packet transmission times. The problem is motivated by the following observation. With many channel coding schemes, the energy required to transmit a packet can be significantly reduced by lowering transmission power and code rate and therefore transmitting the packet over a longer period of time. However, information is often time-critical or delay-sensitive and transmission times cannot be made arbitrarily long. We therefore consider packet transmission schedules that minimize energy subject to a deadline or a delay constraint. Specifically, we obtain an optimal offline schedule for a node operating under a deadline constraint. An inspection of the form of this schedule naturally leads us to an online schedule which is shown, through simulations, to perform closely to the optimal offline schedule. Taking the deadline to infinity, we provide an exact probabilistic analysis of our offline scheduling algorithm. The results of this analysis enable us to devise a lazy online algorithm that varies transmission times according to backlog. We show that this lazy schedule is significantly more energy-efficient compared to a deterministic (fixed transmission time) schedule that guarantees queue stability for the same range of arrival rates.

Prompted by the advent of quality-of-service routing in the Internet, we investigate the properties that path weight functions must have so that hop-by-hop routing is possible and optimal paths can be computed with a generalization of E.W. Dijkstra's algorithm (see Numer. Math., vol.1, p.269-71, 1959). We define an algebra of weights which contains a binary operation, for the composition of link weights into path weights, and an order relation. Isotonicity is the key property of the algebra. It states that the order relation between the weights of any two paths is preserved if both of them are either prefixed or appended by a common, third, path. We show that isotonicity is both necessary and sufficient for a generalized Dijkstra's algorithm to yield optimal paths. Likewise, isotonicity is also both necessary and sufficient for hop-by-hop routing. However, without strict isotonicity, hop-by-hop routing based on optimal paths may produce routing loops. They are prevented if every node computes what we call lexicographic-optimal paths. These paths can be computed with an enhanced Dijkstra's algorithm that has the same complexity as the standard one. Our findings are extended to multipath routing as well. As special cases of the general approach, we conclude that shortest-widest paths can neither be computed with a generalized Dijkstra's algorithm nor can packets be routed hop-by-hop over those paths. In addition, loop-free hop-by-hop routing over widest and widest-shortest paths requires each node to compute lexicographic-optimal paths, in general.