• Motivated by recent concerns that queuing delays in the Internet are on the rise, we conduct a performance evaluation of Compound TCP (C-TCP) in two topologies: a single bottleneck and a multi-bottleneck 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, bandwidth-delay product is high, buffers are dimensioned small (independent of the bandwidth-delay product) and routers deploy a Drop-Tail 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 `queue-channel.' We also demonstrate a sweet-spot 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 queue-channel is maximized. Next, we consider a setting where the average rate of processing qubits is fixed, and show that the the capacity of the queue-channel 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 Car-Following 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 no-delay and small-delay 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 back-propagating congestion waves on highways. In the context of human-driven vehicles, our work provides phenomenological insight into the impact of reaction delays on the emergence and evolution of traffic congestion. In the context of self-driven vehicles, our work has the potential to provide design guidelines for control algorithms running in self-driven 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 non-oscillatory convergence of the CCFM. Next, we characterize the rate of convergence of the CCFM, and bring forth the interplay between local stability, non-oscillatory 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 real-time delay-sensitive 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 sub-optimal. 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 steady-state cache hit probability. We first provide a universal upper bound on the performance of any caching policy. We then analytically obtain the content-wise hit-rates 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 hit-rates 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 non-oscillatory 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 non-linear 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 single-hop wireless network under a realistic Signal-to-interference-plus-noise 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 NP-hard 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 well-known 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 near-optimal 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 NP-hard. 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 multi-armed 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 widely-studied single agent learning policies to the network setting need not perform well in terms of regret. In particular, we identify a class of non-altruistic 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 cost-effectiveness 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 scale-free network topologies whereas, spatially-constrained real-world networks such as, bus networks exhibit a wide-spectrum 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 node-based immunization techniques.
  • In the information overload regime, human communication tasks such as responding to email are well-modeled 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 principal-agent perspective, and characterize the effect of priority-misalignment and information asymmetry between task senders and task receivers in both single-agent and multi-agent settings. In the single-agent setting, we find that discipline can override misalignment. Although variation in human interests leads to performance loss in the single-agent 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 Drop-tail 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 packet-level 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 signal-to-interference ratio (SIR) based interference model, with time-varying 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 steady-state.
  • 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 steady-state queue length distribution under generalized max-weight scheduling in the presence of heavy-tailed traffic. We consider a system consisting of two parallel queues, served by a single server. One of the queues receives heavy-tailed traffic, and the other receives light-tailed traffic. We study the class of throughput optimal max-weight-alpha scheduling policies, and derive an exact asymptotic characterization of the steady-state queue length distributions. In particular, we show that the tail of the light queue distribution is heavier than a power-law curve, whose tail coefficient we obtain explicitly. Our asymptotic characterization also contains an intuitively surprising result - the celebrated max-weight scheduling policy leads to the worst possible tail of the light queue distribution, among all non-idling policies. Motivated by the above negative result regarding the max-weight-alpha policy, we analyze a log-max-weight (LMW) scheduling policy. We show that the LMW policy guarantees an exponentially decaying light queue tail, while still being throughput optimal.