
Motivated by recent concerns that queuing delays in the Internet are on the
rise, we conduct a performance evaluation of Compound TCP (CTCP) in two
topologies: a single bottleneck and a multibottleneck topology, under
different traffic scenarios. The first topology consists of a single bottleneck
router, and the second consists of two distinct sets of TCP flows, regulated by
two edge routers, feeding into a common core router. We focus on some dynamical
and statistical properties of the underlying system. From a dynamical
perspective, we develop fluid models in a regime wherein the number of flows is
large, bandwidthdelay product is high, buffers are dimensioned small
(independent of the bandwidthdelay product) and routers deploy a DropTail
queue policy. A detailed local stability analysis for these models yields the
following key insight: smaller buffers favour stability. Additionally, we
highlight that larger buffers, in addition to increasing latency, are prone to
inducing limit cycles in the system dynamics, via a Hopf bifurcation. These
limit cycles in turn cause synchronisation among the TCP flows, and also result
in a loss of link utilisation. For the topologies considered, we also
empirically analyse some statistical properties of the bottleneck queues. These
statistical analyses serve to validate an important modelling assumption: that
in the regime considered, each bottleneck queue may be approximated as either
an $M/M/1/B$ or an $M/D/1/B$ queue. This immediately makes the modelling
perspective attractive and the analysis tractable. Finally, we show that
smaller buffers, in addition to ensuring stability and low latency, would also
yield fairly good system performance, in terms of throughput and flow
completion times.

We consider a setting where qubits are processed sequentially, and derive
fundamental limits on the rate at which classical information can be
transmitted using quantum states that decohere in time. Specifically, we model
the sequential processing of qubits using a single server queue, and derive
explicit expressions for the capacity of such a `queuechannel.' We also
demonstrate a sweetspot phenomenon with respect to the arrival rate to the
queue, i.e., we show that there exists a value of the arrival rate of the
qubits at which the rate of information transmission (in bits/sec) through the
queuechannel is maximized. Next, we consider a setting where the average rate
of processing qubits is fixed, and show that the the capacity of the
queuechannel is maximized when the processing time is deterministic. We also
discuss design implications of these results on quantum information processing
systems.

Reaction delays play an important role in determining the qualitative
dynamical properties of a platoon of vehicles traversing a straight road. In
this paper, we investigate the impact of delayed feedback on the dynamics of
the Classical CarFollowing Model (CCFM). Specifically, we analyze the CCFM in
no delay, small delay and arbitrary delay regimes. First, we derive a
sufficient condition for local stability of the CCFM in nodelay and
smalldelay regimes using. Next, we derive the necessary and sufficient
condition for local stability of the CCFM for an arbitrary delay. We then
demonstrate that the transition of traffic flow from the locally stable to the
unstable regime occurs via a Hopf bifurcation, thus resulting in limit cycles
in system dynamics. Physically, these limit cycles manifest as backpropagating
congestion waves on highways. In the context of humandriven vehicles, our work
provides phenomenological insight into the impact of reaction delays on the
emergence and evolution of traffic congestion. In the context of selfdriven
vehicles, our work has the potential to provide design guidelines for control
algorithms running in selfdriven cars to avoid undesirable phenomena.
Specifically, designing control algorithms that avoid jerky vehicular movements
is essential. Hence, we derive the necessary and sufficient condition for
nonoscillatory convergence of the CCFM. Next, we characterize the rate of
convergence of the CCFM, and bring forth the interplay between local stability,
nonoscillatory convergence and the rate of convergence of the CCFM. Further,
to better understand the oscillations in the system dynamics, we characterize
the type of the Hopf bifurcation and the asymptotic orbital stability of the
limit cycles using Poincare normal forms and the center manifold theory. The
analysis is complemented with stability charts, bifurcation diagrams and MATLAB
simulations.

Several realtime delaysensitive applications pose varying degrees of
freshness demands on the requested content. The performance of cache
replacement policies that are agnostic to these demands is likely to be
suboptimal. Motivated by this concern, in this paper, we study caching
policies under a request arrival process which incorporates user freshness
demands. We consider the performance metric to be the steadystate cache hit
probability. We first provide a universal upper bound on the performance of any
caching policy. We then analytically obtain the contentwise hitrates for the
Least Popular (LP) policy and provide sufficient conditions for the asymptotic
optimality of cache performance under this policy. Next, we obtain an accurate
approximation for the LRU hitrates in the regime of large content population.
To this end, we map the characteristic time of a content in the LRU policy to
the classical Coupon Collector's Problem and show that it sharply concentrates
around its mean. Further, we develop modified versions of these policies which
eject cache redundancies present in the form of stale contents. Finally, we
propose a new policy which outperforms the above policies by explicitly using
freshness specifications of user requests to prioritize among the cached
contents. We corroborate our analytical insights with extensive simulations.

We conduct a preliminary investigation into the levels of congestion in New
Delhi, motivated by concerns due to rapidly growing vehicular congestion in
Indian cities. First, we provide statistical evidence for the rising congestion
levels on the roads of New Delhi from taxi GPS traces. Then, we estimate the
economic costs of congestion in New Delhi. In particular, we estimate the
marginal and the total costs of congestion. In calculating the marginal costs,
we consider the following factors: (i) productivity loss, (ii) air pollution
costs, and (iii) costs due to accidents. In calculating the total costs, in
addition to the above factors, we also estimate the costs due to the wastage of
fuel. We also project the associated costs due to productivity loss and air
pollution till 2030. The projected traffic congestion costs for New Delhi comes
around 14658 million US$/yr for the year 2030. The key takeaway from our
current study is that costs due to productivity loss, particularly from buses,
dominates the overall economic costs. Additionally, the expected increase in
fuel wastage makes a strong case for intelligent traffic management systems.

Reaction delays are important in determining the qualitative dynamical
properties of a platoon of vehicles traveling on a straight road. In this
paper, we investigate the impact of delayed feedback on the dynamics of the
Modified Optimal Velocity Model (MOVM). Specifically, we analyze the MOVM in
three regimes  no delay, small delay and arbitrary delay. In the absence of
reaction delays, we show that the MOVM is locally stable. For small delays, we
then derive a sufficient condition for the MOVM to be locally stable. Next, for
an arbitrary delay, we derive the necessary and sufficient condition for the
local stability of the MOVM. We show that the traffic flow transits from the
locally stable to the locally unstable regime via a Hopf bifurcation. We also
derive the necessary and sufficient condition for nonoscillatory convergence
and characterize the rate of convergence of the MOVM. These conditions help
ensure smooth traffic flow, good ride quality and quick equilibration to the
uniform flow. Further, since a Hopf bifurcation results in the emergence of
limit cycles, we provide an analytical framework to characterize the type of
the Hopf bifurcation and the asymptotic orbital stability of the resulting
nonlinear oscillations. Finally, we corroborate our analyses using stability
charts, bifurcation diagrams, numerical computations and simulations conducted
using MATLAB.

We consider a Carrier Sense Multiple Access (CSMA) based scheduling algorithm
for a singlehop wireless network under a realistic
Signaltointerferenceplusnoise ratio (SINR) model for the interference. We
propose two local optimization based approximation algorithms to efficiently
estimate certain attempt rate parameters of CSMA called fugacities. It is known
that adaptive CSMA can achieve throughput optimality by sampling feasible
schedules from a Gibbs distribution, with appropriate fugacities.
Unfortunately, obtaining these optimal fugacities is an NPhard problem.
Further, the existing adaptive CSMA algorithms use a stochastic gradient
descent based method, which usually entails an impractically slow (exponential
in the size of the network) convergence to the optimal fugacities. To address
this issue, we first propose an algorithm to estimate the fugacities, that can
support a given set of desired service rates. The convergence rate and the
complexity of this algorithm are independent of the network size, and depend
only on the neighborhood size of a link. Further, we show that the proposed
algorithm corresponds exactly to performing the wellknown Bethe approximation
to the underlying Gibbs distribution. Then, we propose another local algorithm
to estimate the optimal fugacities under a utility maximization framework, and
characterize its accuracy. Numerical results indicate that the proposed methods
have a good degree of accuracy, and achieve extremely fast convergence to
nearoptimal fugacities, and often outperform the convergence rate of the
stochastic gradient descent by a few orders of magnitude.

CSMA (Carrier Sense Multiple Access) algorithms based on Gibbs sampling can
achieve throughput optimality if certain parameters called the fugacities are
appropriately chosen. However, the problem of computing these fugacities is
NPhard. In this work, we derive estimates of the fugacities by using a
framework called the regional free energy approximations. In particular, we
derive explicit expressions for approximate fugacities corresponding to any
feasible service rate vector. We further prove that our approximate fugacities
are exact for the class of chordal graphs. A distinguishing feature of our work
is that the regional approximations that we propose are tailored to conflict
graphs with small cycles, which is a typical characteristic of wireless
networks. Numerical results indicate that the fugacities obtained by the
proposed method are quite accurate and significantly outperform the existing
Bethe approximation based techniques.

We consider a collaborative online learning paradigm, wherein a group of
agents connected through a social network are engaged in playing a stochastic
multiarmed bandit game. Each time an agent takes an action, the corresponding
reward is instantaneously observed by the agent, as well as its neighbours in
the social network. We perform a regret analysis of various policies in this
collaborative learning setting. A key finding of this paper is that natural
extensions of widelystudied single agent learning policies to the network
setting need not perform well in terms of regret. In particular, we identify a
class of nonaltruistic and individually consistent policies, and argue by
deriving regret lower bounds that they are liable to suffer a large regret in
the networked setting. We also show that the learning performance can be
substantially improved if the agents exploit the structure of the network, and
develop a simple learning algorithm based on dominating sets of the network.
Specifically, we first consider a star network, which is a common motif in
hierarchical social networks, and show analytically that the hub agent can be
used as an information sink to expedite learning and improve the overall
regret. We also derive networkwide regret bounds for the algorithm applied to
general networks. We conduct numerical experiments on a variety of networks to
corroborate our analytical results.

Bus transportation is considered as one of the most convenient and cheapest
modes of public transportation in Indian cities. Due to their
costeffectiveness and wide reachability, they help a significant portion of
the human population in cities to reach their destinations every day. Although
from a transportation point of view they have numerous advantages over other
modes of public transportation, they also pose a serious threat of contagious
diseases spreading throughout the city. The presence of numerous local spatial
constraints makes the process and extent of epidemic spreading extremely
difficult to predict. Also, majority of the studies have focused on the
contagion processes on scalefree network topologies whereas,
spatiallyconstrained realworld networks such as, bus networks exhibit a
widespectrum of network topology. Therefore, we aim in this study to
understand this complex dynamical process of epidemic outbreak and information
diffusion on the bus networks for six different Indian cities using SI and SIR
models. This will allow us to identify epidemic thresholds for these networks
which will help us in controlling outbreaks by developing nodebased
immunization techniques.

In the information overload regime, human communication tasks such as
responding to email are wellmodeled as priority queues, where priority is
determined by a mix of intrinsic motivation and extrinsic motivation
corresponding to the task's importance to the sender. We view priority queuing
from a principalagent perspective, and characterize the effect of
prioritymisalignment and information asymmetry between task senders and task
receivers in both singleagent and multiagent settings. In the singleagent
setting, we find that discipline can override misalignment. Although variation
in human interests leads to performance loss in the singleagent setting, the
same variability is useful to the principal with optimal routing of tasks, if
the principal has suitable information about agents' priorities. Our approach
starts to quantitatively address the effect of human dynamics in routine
communication tasks.

We conduct a local stability and Hopf bifurcation analysis for Compound TCP,
with small Droptail buffers, in three topologies. The first topology consists
of two sets of TCP flows having different round trip times, and feeding into a
core router. The second topology corresponds to two queues in tandem, and
consists of two distinct sets of TCP flows, regulated by a single edge router
and feeding into a core router. The third topology comprises of two distinct
sets of TCP flows, regulated by two separate edge routers, and feeding into a
common core router. For each of these cases, we conduct a detailed local
stability analysis and obtain conditions on the network and protocol parameters
to ensure stability. If these conditions get marginally violated, our analysis
shows that the underlying systems would lose local stability via a Hopf
bifurcation. After exhibiting a Hopf, a key concern is to determine the
asymptotic orbital stability of the bifurcating limit cycles. We present a
detailed analytical framework to address the stability of the limit cycles, and
the type of the Hopf bifurcation by invoking Poincare normal forms and the
center manifold theory. We conduct packetlevel simulations to highlight the
existence and stability of the limit cycles in the queue size dynamics.

Recent work has shown that adaptive CSMA algorithms can achieve throughput
optimality. However, these adaptive CSMA algorithms assume a rather simplistic
model for the wireless medium. Specifically, the interference is typically
modelled by a conflict graph, and the channels are assumed to be static. In
this work, we propose a distributed and adaptive CSMA algorithm under a more
realistic signaltointerference ratio (SIR) based interference model, with
timevarying channels. We prove that our algorithm is throughput optimal under
this generalized model. Further, we augment our proposed algorithm by using a
parallel update technique. Numerical results show that our algorithm
outperforms the conflict graph based algorithms, in terms of supportable
throughput and the rate of convergence to steadystate.

In this paper, we derive optimal transmission policies for energy harvesting
sensors to maximize the utility obtained over a finite horizon. First, we
consider a single energy harvesting sensor, with discrete energy arrival
process, and a discrete energy consumption policy. Under this model, we show
that the optimal finite horizon policy is a threshold policy, and explicitly
characterize the thresholds, and the thresholds can be precomputed using a
recursion. Next, we address the case of multiple sensors, with only one of them
allowed to transmit at any given time to avoid interference, and derive an
explicit optimal policy for this scenario as well.

We investigate the asymptotic behavior of the steadystate queue length
distribution under generalized maxweight scheduling in the presence of
heavytailed traffic. We consider a system consisting of two parallel queues,
served by a single server. One of the queues receives heavytailed traffic, and
the other receives lighttailed traffic. We study the class of throughput
optimal maxweightalpha scheduling policies, and derive an exact asymptotic
characterization of the steadystate queue length distributions. In particular,
we show that the tail of the light queue distribution is heavier than a
powerlaw curve, whose tail coefficient we obtain explicitly. Our asymptotic
characterization also contains an intuitively surprising result  the
celebrated maxweight scheduling policy leads to the worst possible tail of the
light queue distribution, among all nonidling policies. Motivated by the above
negative result regarding the maxweightalpha policy, we analyze a
logmaxweight (LMW) scheduling policy. We show that the LMW policy guarantees
an exponentially decaying light queue tail, while still being throughput
optimal.