We introduce a queueing model for passengers waiting to get transport by drivers participating in a ridesharing system. The effect of available drivers' mobility pattern, their willingness to accept rides in a given location, and the incentives offered by the platform, on system throughput is considered. We characterize the largest set of passenger arrival rates which can be served by a fixed number of drivers under any policy dictating the mobility pattern of available drivers. It turns out that any rate in this set can be achieved by offering appropriate constant but region-dependent rewards to drivers for passenger pick up. Moreover, it is shown that dynamic rewards which scale in proportion to the number of passengers waiting for pick up in each region, not only maximize throughput but also significantly decrease pick up delays.

Congestion control protocols for background data are commonly conceived and designed to emulate low priority traffic, which yields to transmission control protocol (TCP) flows. In the presence of even a few very long TCP flows, this behavior can cause bandwidth starvation, and hence, the accumulation of large numbers of background data flows for prolonged periods of time, which may ultimately have an adverse effect on the download delays of delay-sensitive TCP flows. In this paper, we look at the fundamental problem of designing congestion control protocols for background traffic with the minimum impact on short TCP flows while achieving a certain desired average throughput over time. The corresponding optimal policy under various assumptions on the available information is obtained analytically. We give tight bounds of the distance between TCP-based background transfer protocols and the optimal policy, and identify the range of system parameters for which more sophisticated congestion control makes a noticeable difference. Based on these results, we propose an access control algorithm for systems where control on aggregates of background flows can be exercised, as in file servers. Simulations of simple network topologies suggest that this type of access control performs better than protocols emulating low priority over a wide range of parameters.

For CDMA cell-based systems we propose an uplink power control scheme for low data packet queueing delay. The scheme can be seen as a simple extension to the Foschini-Miljanic algorithm which takes the transmit queue sizes at the mobile stations into account. The proposed scheme minimizes the draining time compared to all other policies with the same power consumption. This is because of resource pooling effects which arise when all queues empty at the same time. Although in CDMA systems there is no idle capacity as in wired systems, greater cummulative service is obtained by simultaneous transmissions than through time-sharing. Simulations exhibit significant reductions in queueing delay compared to other power control schemes proposed in the literature.

We consider the joint minimization of queueing cost and power consumption in a wireless network, over all power control policies at the transmitters. Approximately optimal policies are derived through the use of a comparison to a single link system offering lower bounds for both performance metrics. The derived policies are of a simple form: the total power consumed at any instant is a monotonic function of a linear combination of the queue backlogs at that instant, while the portions of power allocated to each transmitter are such that the resulting link speeds are proportional to the queue backlogs. Simulations show that the lower bounds become tight -and so the policies become optimal- as the average power approaches the lowest value for which stability is maintained. Moreover, these policies are shown to perform better than gradient projection -based power adaptive algorithms such those arising in formulations using static optimization problems.

In this paper we present a methodology for the design of congestion control protocols for background data transfers that have a minimal delay impact on short TCP transfers and compete for a target share of the leftover average capacity with other background TCP transfers. We analytically compute the optimal policy and show that it's delay performance can be well approximated by a weighted TCP policy, which maintains a target proportion of TCPs bandwidth at all times in order to achieve the same share of excess capacity. The relative approximation error is always less than 17.2% while it quickly decreases to zero as the number of coexisting background TCP flows increases. Next, we consider a general utility-based fairness criterion for sharing the leftover average capacity, including a penalty term capturing the delay impact to short flows. The criterion is jointly optimized over all allocations of excess capacity to background flows (including TCP ones) on long timescales, and all bandwidth sharing policies on fast time scales. Even though the delay optimal sharing policy that solves the above optimization problem does not lead to distributed congestion control algorithms and more significantly, requires knowledge of the number of competing background TCP flows, both problems disappear under the weighted TCP policy. A distributed weight adjustment policy is considered where, at equilibrium, the overall performance is nearly optimal, with a vanishing relative optimality error as the number of background TCP flows increases. We illustrate the methodology by giving two examples of congestion control algorithms for background transfers. Both achieve low delay for short flows relative to TCP, but at the same time they present strong incentives for adoption against incumbent low priority solutions in public environments.

For a multiplexer fed by a large number of sources, we derive conditions under which a given subset of the sources can be substituted for a single source while preserving the buffer overflow probability and the dominant timescales of buffer overflows. This notion of traffic equivalence is stronger than simple effective bandwidth equality and depends on the multiplexing context. We propose several applications of the above traffic substitution conditions. First, we show that fractional Brownian motion as a single source substitute can effectively model a large number of multiplexed sources using information obtained purely from traffic traces; this has direct application to simple but accurate traffic generation. Second, we focus on dynamic (i.e., on-line) estimation of available capacity and buffer overflow probability. This requires the solution of a double optimization problem expressed in terms of functions whose values are obtained from time averages of the traffic traces over a large range of timescales. We show how to solve this problem on-line by reducing it to the calculation of a fixed-point equation that can be solved iteratively by combining traffic substitution using fractional Brownian motion with dynamic measurements of the actual traffic. We have validated this approach by extensive experimentation with large numbers of real traffic sources that are fed to a high bandwidth link, and comparing our on-line estimation of available capacity and the resulting dynamic call admission control with other existing approaches. The superior accuracy of our approach also suggests that taking the buffer size into account, as does our on-line algorithm, may be vital for achieving approximations of practical interest.

This paper introduces a framework for answering questions regarding the conditions on the network load that allow a best-effort network like the Internet to support connections of given duration that require a certain quality of service. Such quality of service is expressed in terms of the percentage of time the bandwidth allocated to a connection may drop below a certain level or the maximum allowable delay in placing the call through the network waiting for more favorable loading conditions. The call-acceptance conditions, which depend on the behavior of the system over the lifetime of accepted calls, are thus based on transient models for the congestion (instead of looking at the average behavior) and attempt to exploit the time-scales of the fluctuations of the number of connections competing for bandwidth. Extensions of the model consider the case of dynamic pricing which allows connections that pay more to get larger shares of the bandwidth, and investigate the trade-off between quality of service, the size of the acceptance region, and the charge to be paid by the connection. Under this framework we introduce an option contract that reduces the risk of quality disruption, if a user has a fixed budget at his disposal, and calculate its price. One potential use of this methodology is towards developing a simple admission control mechanism for placing voice calls through an IP network, where the decisions can be taken by edge devices.

For a multiplexer fed with a large number of sources, we derive conditions under which a single source can be substituted for a given subset of the sources while preserving the buffer overflow probability and the dominant time scales of buffer overflows. This equivalence is stronger than simple effective bandwidth equality and takes into account the context in which multiplexing takes place. This allows a substitution to be made for arbitrarily large proportions of the traffic without changing the operating point of the multiplexer as experienced by the rest of the traffic. It corresponds to defining a single source which is equivalent in a sense "local" to a given context, rather than equivalent in a sense which is "universal" to all contexts. The proposed methodology does not rely on traffic models and obtains the necessary information from the actual traffic traces. We study the case of fractional Brownian motion as a single source substitute and provide theoretical and experimental results that validate our approach.