Publications

2025

[C35]
The Power of Two in Large Service-Marketplaces
Dheeraj Narasimha, Srinivas Nomula, Srinivas Shakkottai, and Parimal Parag
IEEE International Conference on Computer Communications (INFOCOM), (May 2025)

2024

[J32]
A SUFFICIENT CONDITION FOR THE QUASIPOTENTIAL TO BE THE RATE FUNCTION OF THE INVARIANT MEASURE OF COUNTABLE-STATE MEAN-FIELD INTERACTING PARTICLE SYSTEMS
Sarath Yasodharan and Rajesh Sundaresan
Advances in Applied Probability vol 56(3), pp 960 – 1003 (2024)
DOI PDF
This paper considers the family of invariant measures of Markovian mean-field interacting particle systems on a countably infinite state space and studies its large deviation asymptotics. The Freidlin-Wentzell quasipotential is the usual candidate rate function for the sequence of invariant measures indexed by the number of particles. The paper provides two counterexamples where the quasipotential is not the rate function. The quasipotential arises from finite-horizon considerations. However, there are certain barriers that cannot be surmounted easily in any finite time horizon, but these barriers can be crossed in the stationary regime. Consequently, the quasipotential is infinite at some points where the rate function is finite. After highlighting this phenomenon, the paper studies some sufficient conditions on a class of interacting particle systems under which one can continue to assert that the Freidlin-Wentzell quasipotential is indeed the rate function. © The Author(s), 2024.
[J31]
Holistic Energy Awareness and Robustness for Intelligent Drones
Ravi Raj Saxena, Joydeep Pal, Srinivasan Iyengar, Bhawana Chhaglani, Anurag Ghosh, Venkata N. Padmanabhan, and Prabhakar T. Venkata
ACM Transactions on Sensor Networks vol 20(3), (2024)
DOI PDF
Drones represent a significant technological shift at the convergence of on-demand cyber-physical systems and edge intelligence. However, realizing their full potential necessitates managing the limited energy resources carefully. Prior work looks at factors such as battery characteristics, intelligent edge sensing considerations, planning, and robustness in isolation. But a global view of energy awareness that considers these factors and looks at various tradeoffs is essential. To this end, we present results from our detailed empirical study of battery charge-discharge characteristics and the impact of altitude and lighting on edge inference accuracy. Our energy models, derived from these observations, predict energy usage while performing various manoeuvres with an error of 5.6%, a 2.5X improvement over the state-of-the-art. Furthermore, we propose a holistic energy-aware multi-drone scheduling system that decreases the energy consumed by 21.14% and the mission times by 46.91% over state-of-the-art baselines. To achieve system robustness in the event of link or drone failure, we observe trends in Packet Delivery Ratio to propose a methodology to establish reliable communication between nodes. We release an open-source implementation of our system. Finally, we tie all of these pieces together using a people-counting case study. © 2024 Copyright held by the owner/author(s). Publication rights licensed to ACM.
[J30]
Caching Contents with Varying Popularity Using Restless Bandits
K.J. Pavamana and Chandramani Singh
Lecture Notes of the Institute for Computer Sciences, Social-Informatics and Telecommunications Engineering, LNICST vol 539, pp 133 – 150 (2024)
DOI PDF
We study content caching in a wireless network in which the users are connected through a base station that is equipped with a finite capacity cache. We assume a fixed set of contents whose popularity vary with time. Users’ requests for the contents depend on their instantaneous popularity levels. Proactively caching contents at the base station incurs a cost but not having requested contents at the base station also incurs a cost. We propose to proactively cache contents at the base station so as to minimize content missing and caching costs. We formulate the problem as a discounted cost Markov decision problem that is a restless multi-armed bandit problem. We provide conditions under which the problem is indexable and also propose a novel approach to manoeuvre a few parameters to render the problem indexable. We demonstrate efficacy of the Whittle index policy via numerical evaluation. © 2024, ICST Institute for Computer Sciences, Social Informatics and Telecommunications Engineering.
[J29]
Holistic Energy Awareness and Robustness for Intelligent Drones
Ravi Raj Saxena, Joydeep Pal, Srinivasan Iyengar, Bhawana Chhaglani, Anurag Ghosh, Venkata N. Padmanabhan, and Prabhakar T. Venkata
ACM Transactions on Sensor Networks vol 20(3), (2024)
DOI PDF
Drones represent a significant technological shift at the convergence of on-demand cyber-physical systems and edge intelligence. However, realizing their full potential necessitates managing the limited energy resources carefully. Prior work looks at factors such as battery characteristics, intelligent edge sensing considerations, planning, and robustness in isolation. But a global view of energy awareness that considers these factors and looks at various tradeoffs is essential. To this end, we present results from our detailed empirical study of battery charge-discharge characteristics and the impact of altitude and lighting on edge inference accuracy. Our energy models, derived from these observations, predict energy usage while performing various manoeuvres with an error of 5.6%, a 2.5X improvement over the state-of-the-art. Furthermore, we propose a holistic energy-aware multi-drone scheduling system that decreases the energy consumed by 21.14% and the mission times by 46.91% over state-of-the-art baselines. To achieve system robustness in the event of link or drone failure, we observe trends in Packet Delivery Ratio to propose a methodology to establish reliable communication between nodes. We release an open-source implementation of our system. Finally, we tie all of these pieces together using a people-counting case study. © 2024 Copyright held by the owner/author(s). Publication rights licensed to ACM.
[J28]
Dy-MAC: Implementation of dynamic MAC stack for IEEE 802.15.4e-TSCH
Deeksha P. Rao, Shrutkirthi S. Godkhindi, Abhigna V. Kumar, and T.V. Prabhakar
Ad Hoc Networks vol 152, (2024)
DOI PDF
This paper presents the lessons learnt in the implementation of IEEE 802.15.4e-Time Slotted Channel Hopping (TSCH) Medium Access Control (MAC) protocol on commercially available hardware. Our MAC Application programming Interface (API) called the Dy-MAC is agnostic to the PHY layer and is coded on a ARM cortex M4. MAC functions such as TDMA, FDMA, frame counter, channel access, synchronization and PAN formation are abstracted as part of this API. Dy-MAC is demonstrated for 2.4GHz with O-QPSK modulation and 868MHz with SUN FSK modulation. Furthermore, the API supports star, mesh and tree network to provide flexible topologies in factory environment. Our experiments show that for a 76 byte payload, the TSCH Dy-MAC provides ∼ 99% packet delivery ratio (PDR) for 26ms timeslot with SUN FSK PHY and ∼ 97% PDR for 10ms timeslot with O-QPSK PHY. To maintain synchronization over the entire network, we implemented algorithms to successfully communicate between fast and slow nodes. Resilience to interference and range with packet delivery ratio is evaluated. We consolidate our implementation in terms of 10 lessons that were learnt in building the Dy-MAC protocol. © 2023 Elsevier B.V.
[C34]
Energy-minimizing workload splitting and frequency selection for guaranteed performance over heterogeneous cores
Aditya Priya, Rajiv Choudhury, Sujay Patni, Himkant Sharma, Moonmoon Mohanty, Krishnasuri Narayanam, Umamaheswari Devi, Pratibha Moogi, Preetam Patil, and Parimal Parag
Proceedings of the 15th ACM International Conference on Future and Sustainable Energy Systems, pp 308–322 (2024)
DOI PDF
Heterogeneous computing involves CPU architectures that support more than one core type, and it aims to achieve energy efficiency while meeting the performance guarantees. This aim can be achieved by the operating system or the on-chip driver by exploiting the differential power-performance trade-off that heterogeneous cores offer. We characterize the power-performance trade-off for an Intel CPU with heterogeneous cores and provide a mathematical framework to study heterogeneous computing. In particular, we provide probabilistic workload split and operating frequency for all active cores that allow workload execution with minimal carbon emissions. We support the analytical findings with experimental evaluations for a few representative workloads. As compared to the default Linux frequency governors, our scheme can reduce the energy-delay product by up to 80%.
[C33]
Enabling Smartness in a Legacy Lathe Machine
Laxmikant D. Pai Angle, Deeksha P. Rao, Shrutkirthi S. Godkhindi, and T.V. Prabhakar
2024 16th International Conference on COMmunication Systems and NETworkS, COMSNETS 2024, pp 309 – 311 (2024)
DOI PDF
We provide the first-ever low-cost, low-power, easily adaptable solution for tool monitoring and analysis of Lathe machines. An alternate looping system is employed to provide automatic coolant dispensing and to classify tools based on their sharpness using the CNN model. The first objective is achieved using thermal profiling of the tool, whereas a vision-based edge detection approach is used for the latter. A correlation between raise in temperature and tool degradation is inferred. © 2024 IEEE.
[C32]
Fresh Caching of Dynamic Contents using Restless Multi-armed Bandits
Ankita Koley and Chandramani Singh
Proceedings - 2024 IEEE 21st International Conference on Mobile Ad-Hoc and Smart Systems, MASS 2024, pp 238 – 246 (2024)
DOI PDF
We consider a dynamic content caching problem wherein the contents get updated at a central server, and local copies of a subset of contents are cached at a local cache associated with a Base station (BS). When a content request arrives, based on whether the content is in the local cache, the BS can decide whether to fetch the content from the central server or serve the cached version from the local cache. Fetching a content incurs a fixed fetching cost, and serving the cached version incurs an ageing cost proportional to the age-of-version (AoV) of the content. The BS has only partial information regarding AoVs of the contents. We formulate an optimal content fetching and caching problem to minimize the average cost subject to cache capacity constraints. The problem suffers from the curse of dimensionality and is provably hard to solve. We formulate this problem as a continuous time restless multi-armed bandit process (RMAB), where a single content problem of the corresponding RMAB is a partially observable Markov decision process. We reformulate the single content problem as a semi-Markov decision process, prove indexability, and provide a Whittle index based solution to this problem. Finally, we compare the performance with recent work and show that our proposed policy is optimal via simulations. © 2024 IEEE.
[J27]
Cyber-Physical Modeling and Vulnerability Assessment of Substations for Transmission System Operator
S. Shashank, Gurunath Gurrala, P.S. Sastry, and Vaibhav Katewa
Electric Power Systems Research vol 235, (2024)
DOI PDF
In bulk power systems, the majority of interaction between cyber and physical components takes place in substations. However, in most of the cyber–physical power system models the physical layer is typically done using the bus-branch (BB) model, where each substation is considered as a single node. This approach will not capture the details of the cyber layer. This paper proposes a framework to model the substations using node-breaker (NB) models for physical system representation so that the detailed station configurations, the current and the voltage transformer positions, arrangements of protective relays, bay control units and associated communication infrastructure within the substations and its dependencies on the physical elements can be captured effectively using a single cyber–physical graph. Keeping a transmission system operator in view, who does not use power flow and security assessment tools for station operations and maintenance, a vulnerability assessment approach is proposed to assess the risk using some representative attack scenarios. The proposed approach is demonstrated using WECC 3-machine system for breaker and half station configuration. The attack scenarios are developed based on the real substation configuration and the adversary's ability to understand the substation protection and BI/BO operations. © 2024 Elsevier B.V.
[C31]
EdgeP4: In-Network Edge Intelligence for a Tactile Cyber-Physical System Testbed Across Cities
Nithish Krishnabharathi Gnani, Joydeep Pal, Deepak Choudhary, Himanshu Verma, Soumya Kanta Rana, Kaushal S Mhapsekar, T V Prabhakar, and Chandramani Singh
IEEE INFOCOM 2024 - IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS), pp 1-6 (May 2024)
DOI PDF
Tactile Internet based operations, e.g., telesurgery, rely on the human operator for end-to-end closed loop control to achieve accuracy. While feedback and control are subject to network latency and packet loss, critical operations such as pose correction, fiducial marking, tremor reduction, etc. are tasks that should be carried out automatically and thus dispensing with these feedback signals from traversing the network to the other end. We design two edge intelligence algorithms hosted at P4 programmable end switches placed 400 km apart. These algorithms locally compute and command corrective signals. We implement these algorithms entirely on data plane on Netronome Agilio SmartNICs. “pose correction” is placed at the edge switch connected to an industrial robot gripping a tool. The round trip between transmitting force sensor array readings to the edge switch and receiving correct tip coordinates at the robot is shown to be less than 100µs. “tremor suppression” is placed at the edge switch connected to the operator. It suppresses physiological tremors, which improves the application's performance and also reduces the network load up to 99.9%. Our EdgeP4 framework allows edge intelligence modules to seamlessly switch between the algorithms based on the tasks being executed by devices connected to their ports.
[C30]
Saturation Throughput Analysis of Hybrid Access MAC Protocol in IEEE 802.11ax WLANs
S. Arthi and Neelesh B. Mehta
IEEE Global Communications Conf. (Globecom), (December 2024)
[J26]
Optimal resource management for multi-access edge computing without using cross-layer communication
Ankita Koley and Chandramani Singh
Performance Evaluation vol 166, (2024)
DOI PDF
We consider a Multi-access Edge Computing (MEC) system with a set of users, a base station (BS) with an attached MEC server, and a cloud server. The users can serve the service requests locally or can offload them to the BS which in turn can serve a subset of the offloaded requests at the MEC and can forward the requests to the cloud server. The user devices and the MEC server can be dynamically configured to serve different classes of services. The service requests offloaded to the BS incur offloading costs and those forwarded to the cloud incur additional costs; the costs could represent service charges or delays. Aggregate cost minimization subject to stability warrants optimal service scheduling and offloading at the users and the MEC server, at their application layers, and optimal uplink packet scheduling at the users’ MAC layers. Classical back-pressure (BP) based solutions entail cross-layer message exchange, and hence are not viable. We propose virtual queue-based drift-plus-penalty algorithms that are throughput optimal, and achieve the optimal delay arbitrarily closely but do not require cross-layer communication. We first consider an MEC system without local computation, and subsequently, extend our framework to incorporate local computation also. We demonstrate that the proposed algorithms offer almost the same performance as BP based algorithms. These algorithms contain tuneable parameters that offer a trade off between queue lengths at the users and the BS and the offloading costs. © 2024 Elsevier B.V.
[J25]
Analysis of Fork-Join Scheduling on Heterogeneous Parallel Servers
Moonmoon Mohanty, Gaurav Gautam, Vaneet Aggarwal, and Parimal Parag
IEEE/ACM Transactions on Networking vol 32(6), pp 4798 – 4809 (2024)
DOI PDF
This paper investigates the (k,k) fork-join scheduling scheme on a system of n parallel servers comprising both slow and fast servers. Tasks arriving in the system are divided into k sub-tasks and assigned to a random set of k servers, where each task can be assigned independently to a distinct slow or fast server with selection probability ps or 1-ps, respectively. Our analysis demonstrates that the joint distribution of the stationary workload across any set of k queues becomes asymptotically independent as the number of servers n grows, with k scaling as o(n1/4). Under asymptotic independence, the limiting mean task completion time can be expressed as an integral. However, it is analytically challenging to compute the optimal selection probability ps∗ that minimizes this integral. To address this, we provide an upper bound on the limiting mean task completion time and identify the selection probability ps that minimizes this bound. We validate that this selection probability ps yields a near-optimal performance through numerical experiments. © 1993-2012 IEEE.
[C29]
Towards a TSN-DetNet Intercity Testbed for Tactile Cyber-Physical Systems
Joydeep Pal, Deepak Choudhary, Nithish Krishnabharathi Gnani, T.V. Prabhakar, Chandramani Singh, Hari Krishna Atluri, and A. Paventhan
IEEE INFOCOM 2024 - IEEE Conference on Computer Communications Workshops, INFOCOM WKSHPS 2024, (2024)
DOI PDF
We present a TSN-DetNet testbed design for Tactile Cyber-Physical Systems (TCPS) that facilitates Time-Sensitive Networking (TSN) and Deterministic Networking (DetNet) standards to provide low-latency and high-reliability communication across two cities separated by 400 kilometres. The core design revolves around two key domains: the CPS domain, encompassing haptic devices, robotic arms, and sensing equipment, and the Tactile Internet domain, comprising TSN-enabled LAN switches and Multiprotocol Label Switching (MPLS)-based WAN routers. This configuration ensures the handling of diverse traffic classes, including Scheduled Traffic (ST) for critical tactile data and Best Effort (BE) for non-critical flows. We leverage Precision Time Protocol (PTP) for time synchronization. The paper comprehensively evaluates the testbed's performance metrics, encompassing latency, jitter, packet loss, and time synchronization accuracy. Subsequently, it showcases the practical capabilities of the testbed through a real-world demonstration of a robotic teleoperation application, incorporating haptic and video feedback functionalities. The paper also discusses the challenges of building an intercity TSN-DetNet testbed and future work for using it to demonstrate and evaluate TCPS applications. © 2024 IEEE.

2023

[J24]
Analysis of Interevent Times in Linear Systems Under Region-Based Self-Triggered Control
Anusree Rajan and Pavankumar Tallapragada
IEEE Transactions on Automatic Control vol 69(4), pp 2545 – 2551 (2023)
DOI PDF
—This article analyzes the evolution of interevent times (IETs) in linear systems under region-based self-triggered control (RBSTC). In this control method, the state space is partitioned into a finite number of conic regions and each region is associated with a fixed IET. In this framework, studying the steady-state behavior of the IETs is equivalent to studying the existence of a conic subregion that is positively invariant under the map that gives the evolution of the state from one event to the next. We provide necessary conditions and sufficient conditions for the existence of a positively invariant subregion (PIS). We also provide the necessary and sufficient conditions for a PIS to be asymptotically stable. Indirectly, they provide necessary and sufficient conditions for the local convergence of IETs to a constant or to a given periodic sequence. We illustrate the proposed method of analysis and results through numerical simulations. © 2023 IEEE.
[J23]
MPClan: Protocol Suite for Privacy-Conscious Computations
Nishat Koti, Shravani Patil, Arpita Patra, and Ajith Suresh
Journal of Cryptology vol 36(3), (2023)
DOI PDF
The growing volumes of data being collected and its analysis to provide better services are creating worries about digital privacy. To address privacy concerns and give practical solutions, the literature has relied on secure multiparty computation techniques. However, recent research over rings has mostly focused on the small-party honest-majority setting of up to four parties tolerating single corruption, noting efficiency concerns. In this work, we extend the strategies to support higher resiliency in an honest-majority setting with efficiency of the online phase at the centre stage. Our semi-honest protocol improves the online communication of the protocol of Damgård and Nielsen (CRYPTO’07) without inflating the overall communication. It also allows shutting down almost half of the parties in the online phase, thereby saving up to 50% in the system’s operational costs. Our maliciously secure protocol also enjoys similar benefits and requires only half of the parties, except for one-time verification towards the end, and provides security with fairness. To showcase the practicality of the designed protocols, we benchmark popular applications such as deep neural networks, graph neural networks, genome sequence matching, and biometric matching using prototype implementations. Our protocols, in addition to improved communication, aid in bringing up to 60–80% savings in monetary cost over prior work. © 2023, The Author(s).
[C28]
Lessons Learnt From the Implementation of the IEEE 802.15.4e-TSCH MAC
Ipsita Sanyal, Deeksha P. Rao, Rakshana Gunasekaran, S.M. Sachin, and T.V. Prabhakar
2023 15th International Conference on COMmunication Systems and NETworkS, COMSNETS 2023, pp 658 – 666 (2023)
DOI PDF
In this work, we implement the IEEE 802.15.4e-Time Slotted Channel Hopping (TSCH) Medium Access Control (MAC) protocol software stack on standard hardware. An Application Programming Interfaces (API) support and ready to deploy star network is built and tested. The interfacing between micro-controller and radio uses the Serial Peripheral Interface (SPI) bus. Our implementation reveals that over 50% of the time overhead is SPI communication. To maintain synchronisation over the entire network, we implemented algorithms to successfully communicate between fast and slow nodes. Resilience to interference and packet error ratio is evaluated. We consolidate our implementation in terms of 6 lessons that were learnt in building the MAC protocol. © 2023 IEEE.
[J22]
Revenue Optimal Bandwidth Allocation in a Class of Multihop Networks: Algorithms and Asymptotic Optimality
Sarath Yasodharan and Anurag Kumar
IEEE/ACM Transactions on Networking vol 31(5), pp 2251 – 2266 (2023)
DOI PDF
We study Bandwidth Reservation (BR) policies for the Bandwidth on Demand (BoD) problem in a class of multihop networks. We motivate an Erlang fixed-point BR heuristic for the general BoD problem by first establishing the optimality of BR on a class of multihop networks. The motivating problem is a wireline network comprising k links in tandem, each link of which is shared by two types of bandwidth demands, one type requiring one unit of bandwidth from every link, and the other type (being dedicated to the link) requiring one unit of bandwidth as well. First, for this k -hop tandem network, when each link has unit bandwidth, we demonstrate that a policy of BR form is optimal. We then study the BoD problem for a more general k -hop tandem network, in the 'Kelly' limiting regime, where the arrival rates as well as the link bandwidths become large. For certain parameter regimes of the k -hop tandem network, we show that an admission control policy of BR form is asymptotically optimal. Motivated by these results, we propose an Erlang fixed-point based, link-by-link, heuristic algorithm for computing a BR policy for the BoD problem in a general network. We, finally, evaluate this proposal numerically. © 1993-2012 IEEE.
[C27]
Integrated Taxiing and TLOF pad Scheduling Using Different Surface Directions with Fairness Analysis
Ravi Raj Saxena, Tejas Joshi, Yashashav Dk, T.V. Prabhakar, and Joy Kuri
IEEE Conference on Intelligent Transportation Systems, Proceedings, ITSC, pp 1747 – 1752 (2023)
DOI PDF
Vertical Take-Off and Landing (VTOL) vehicles have gained immense popularity in the delivery drone market and are now being developed for passenger transportation in urban areas to efficiently enable Urban Air Mobility (UAM). UAM aims to utilize the urban airspace to address the problem of heavy road congestion in dense urban cities. VTOL vehicles require vertiport terminals for landing, take-off, refuelling (or charging), and maintenance. An efficient scheduling algorithm is essential to maximize the throughput of the vertiport terminal while maintaining safety protocols to handle the UAM traffic. While traditional departure and taxiing operations can be applied in the context of vertiport terminals, specific algorithms are required for take-off and landing schedules. Unlike fixed-wing aircraft that require a runway to take-off and climb in a single direction, VTOL vehicles can approach and climb in several directions. We propose a Mixed Integer Linear Program (MILP) formulation to schedule flights for taxiing and climbing in multiple directions after take-off. Our results show that increasing the number of climbing directions can reduce delays by over 50%. We also introduce a fairness metric to ensure a uniform delay distribution. © 2023 IEEE.
[C26]
Enhancing Reliability of Scheduled Traffic in Time-Sensitive Networks using Frame Replication and Elimination
Soumya Kanta Rana, Himanshu Verma, Joydeep Pal, Deepak Choudhary, T.V. Prabhakar, and Chandramani Singh
IEEE Workshop on Local and Metropolitan Area Networks, (2023)
DOI PDF
The IEEE 802.1CB standard for Frame Replication and Elimination for Reliability (FRER) emphasises improving reliability by introducing link redundancy. In this paper, two approaches towards the elimination of duplicates are implemented on a programmable pipelined switch. The first approach meets the intermittent stream traffic goal of the standard. A sliding window-based algorithm is used for storing and comparing identification numbers of packets. The second approach handles bulk stream traffic by using a hash table along with the sliding window for a faster lookup, making it more scalable. Hash-collision mitigation with the help of stream identification is also incorporated in the hash table approach. The algorithms are implemented in P4 and Micro-C. Latency versus window size obtained for both the approaches and the end-To-end packet loss reduction yielded by FRER in presence of lossy intermediate links are demonstrated. © 2023 IEEE.
[M4]
$\mu$TAS: Design and implementation of Time Aware Shaper on SmartNICs to achieve bounded latency
Joydeep Pal, Deepak Choudhary, Nithish Krishnabharathi Gnani, Chandramani Singh, and T. V. Prabhakar
arXiv, (2023)
DOI PDF
Time-Aware Shaper (TAS) is a time-triggered scheduling mechanism that ensures bounded latency for time-critical Scheduled Traffic (ST) flows. The Linux kernel implementation (a.k.a TAPRIO) has limited capabilities due to varying CPU workloads and thus does not offer tight latency bound for the ST flows. Also, currently only higher cycle times are possible. Other software implementations are limited to simulation studies without physical implementation. In this paper, we present μTAS, a MicroC-based hardware implementation of TAS onto a programmable SmartNIC. μTAS takes advantage of the parallel-processing architecture of the SmartNIC to configure the scheduling behaviour of its queues at runtime. To demonstrate the effectiveness of μTAS, we built a Time-Sensitive Networking (TSN) testbed from scratch. This consists of multiple end-hosts capable of generating ST and Best Effort (BE) flows and TSN switches equipped with SmartNICs running μTAS. Time synchronization is maintained between the switches and hosts. Our experiments demonstrate that the ST flows experience a bounded latency of the order of tens of microseconds.
[J21]
Learning in Constrained Markov Decision Processes
Rahul Singh, Abhishek Gupta, and Ness B. Shroff
IEEE Transactions on Control of Network Systems vol 10(1), pp 441-453 (March 2023)
DOI PDF
We consider reinforcement learning (RL) in Markov decision processes in which an agent repeatedly interacts with an environment that is modeled by a controlled Markov process. At each time step $t$, it earns a reward and also incurs a cost vector consisting of $M$ costs. We design model-based RL algorithms that maximize the cumulative reward earned over a time horizon of $T$ time steps while simultaneously ensuring that the average values of the $M$ cost expenditures are bounded by agent-specified thresholds $c^\textub_i,i=1,2,\ldots,M$. The consideration of the cumulative cost expenditures departs from the existing literature, in that the agent now additionally needs to balance the cost expenses in an online manner while simultaneously performing the exploration–exploitation tradeoff that is typically encountered in RL tasks. This is challenging since the dual objectives of exploration and exploitation necessarily require the agent to expend resources. In order to measure the performance of an RL algorithm that satisfies the average cost constraints, we define an $M+1$ dimensional regret vector that is composed of its reward regret, and $M$ cost regrets. The reward regret measures the suboptimality in the cumulative reward while the $i$th component of the cost regret vector is the difference between its $i$th cumulative cost expense and the expected cost expenditures $Tc^\textub_i$. We prove that the expected value of the regret vector is upper-bounded as $\tildeO(T^2\slash 3)$, where $T$ is the time horizon, and $\tildeO(\cdot)$ hides factors that are logarithmic in $T$. We further show how to reduce the regret of a desired subset of the $M$ costs, at the expense of increasing the regrets of rewards and the remaining costs. To the best of our knowledge, ours is the only work that considers nonepisodic RL under average cost constraints and derives algorithms that can tune the regret vector according to the agent's requirements on its cost regrets.
[J20]
Optimal Pricing in a Single Server System
Ashok Krishnan K. S, Chandramani Singh, Siva Theja Maguluri, and Parimal Parag
ACM Transactions on Modeling and Performance Evaluation of Computing Systems vol 8(4), (2023)
DOI PDF
We study optimal pricing in a single server queue when the customers valuation of service depends on their waiting time. In particular, we consider a very general model, where the customer valuations are random and are sampled from a distribution that depends on the queue length. The goal of the service provider is to set dynamic state dependent prices in order to maximize its revenue, while also managing congestion. We model the problem as a Markov decision process and present structural results on the optimal policy. We also present an algorithm to find an approximate optimal policy. We further present a myopic policy that is easy to evaluate and present bounds on its performance. We finally illustrate the quality of our approximate solution and the myopic solution using numerical simulations. © 2023 Copyright held by the owner/author(s). Publication rights licensed to ACM.
[J19]
Asymptotic Analysis of Probabilistic Scheduling for Erasure-Coded Heterogeneous Systems
Rooji Jinan, Gaurav Gautam, Parimal Parag, and Vaneet Aggarwal
Performance Evaluation Review vol 50(4), pp 8 – 10 (2023)
DOI PDF
We consider (k, k) fork-join scheduling on a large number (say, N) of parallel servers with two sets of heterogeneous rates. An incoming task is split into k sub-tasks and dispatched to k servers according to a probabilistic selection policy, with parameter ps being the selection probability of slower servers. Mean task completion time admits an integral form, and thus it is analytically intractable to compute ps that minimizes it. In this work, we provide an upper bound on the mean task completion time, and determine ps that minimizes this upper bound. Numerically, this choice has been shown to be near-optimal. © 2023 Copyright is held by the owner/author(s).
[J18]
Load balancing policies without feedback using timed replicas
Rooji Jinan, Ajay Badita, Tejas Bodas, and Parimal Parag
Performance Evaluation vol 162, (2023)
DOI PDF
Dispatching policies such as join the shortest queue (JSQ), join the queue with smallest workload (JSW), and their power of two variants are used in load balancing systems where the instantaneous queue length or workload information at all queues or a subset of them can be queried. In situations where the dispatcher has an associated memory, one can minimize this query overhead by maintaining a list of idle servers to which jobs can be dispatched. Recent alternative approaches that do not require querying such information include the cancel-on-start and cancel-on-complete replication policies. The downside of such policies however is that the servers must communicate either the start or the completion time instant of each service to the dispatcher and must allow the coordinated and instantaneous cancellation of all redundant replicas. In practice, the requirements of query messaging, memory, and replica cancellation pose challenges in their implementation and their advantages are not clear. In this work, we consider load-balancing policies that do not need to query load information, do not need memory, and do not need to cancel replicas. Our policies allow the dispatcher to append a timer to each job or its replica. A job or a replica is discarded if its timer expires before it starts receiving service. We analyze several variants of this policy which are novel and simple to implement. We numerically observe that the variants of the proposed policy outperform popular feedback-based policies for low arrival rates, despite no feedback from servers to the dispatcher. © 2023 Elsevier B.V.

2022

[J17]
Multiple Support Recovery Using Very Few Measurements Per Sample
Lekshmi Ramesh, Chandra R. Murthy, and Himanshu Tyagi
IEEE Transactions on Signal Processing vol 70, pp 2193 – 2206 (2022)
DOI PDF
In the problem of multiple support recovery, we are given access to linear measurements of multiple sparse samples in Rd. These samples can be partitioned intoℓ groups, with samples having the same support belonging to the same group. For a given budget of m measurements per sample, the goal is to recover the ℓ underlying supports, in the absence of the knowledge of group labels. We study this problem with a focus on the measurement-constrained regime where m is smaller than the support size k of each sample. We design a two-step procedure that estimates the union of the underlying supports first, and then uses a spectral algorithm to estimate the individual supports. Our proposed estimator can recover the supports with m< k measurements per sample, from Ok4ℓ 4/m4 samples. Our guarantees hold for a general, generative model assumption on the samples and measurement matrices. We also provide results from experiments conducted on synthetic data and on the MNIST dataset. © 1991-2012 IEEE.
[J16]
Dynamics of a Stratified Population of Optimum Seeking Agents on a Network—Part I: Modeling and Convergence Analysis
Nirabhra Mandal and Pavankumar Tallapragada
IEEE Transactions on Control of Network Systems vol 9(3), pp 1104 – 1115 (2022)
DOI PDF
In this article, we consider a population composed of a continuum of agents that seek to maximize a payoff function by moving on a network. The nodes in the network may represent physical locations or abstract choices. The population is stratified, i.e., agents opting for the same choice may not get the same payoff. In particular, we assume payoff functions with diminishing returns, i.e., agents in “newer” strata of a node receive a smaller payoff compared to “older” strata. In this first part of this two-part work, we model the population dynamics under three choice revision policies, having varying levels of coordination: 1) no coordination and the agents are selfish; 2) coordination among agents in each node; and 3) coordination across the entire population. For the case with selfish agents, we generalize the Smith dynamics to our setting, where we have a stratified population and network constraints. To model nodal coordination, we allow the fraction of population in a node, as a whole, to take the “best response” to the state of the population in the node’s neighborhood. For the case of population-wide coordination, we explore a dynamics where the population evolves according to centralized gradient ascent of the social utility, though constrained by the network. In each case, we show that the dynamics has existence and uniqueness of solutions and also show that the solutions from any initial condition asymptotically converge to the set of Nash equilibria. 2325-5870 © 2021 IEEE.
[J15]
Dynamics of a Stratified Population of Optimum Seeking Agents on a Network—Part II: Steady-State Analysis
Nirabhra Mandal and Pavankumar Tallapragada
IEEE Transactions on Control of Network Systems vol 9(3), pp 1116 – 1127 (2022)
DOI PDF
In this second part of our work, we study the steady state of the population and the social utility for a general class of dynamics that converge to the set of Nash equilibria and follow a certain positive correlation property. This class of dynamics includes the three dynamics introduced in the first part. We provide sufficient conditions on the network based on a maximum payoff density parameter of each node under which there exists a unique Nash equilibrium. We then utilize the positive correlation properties of the dynamics to reduce the flow graph in order to provide an upper bound on the steady-state social utility. Finally, we extend the idea behind the sufficient condition for the existence of a unique Nash equilibrium to partition the graph appropriately in order to provide a lower bound on the steady-state social utility. We also illustrate interesting cases as well as our results using simulations. 2325-5870 © 2021 IEEE.
[C25]
Tetrad: Actively Secure 4PC for Secure Training and Inference
Nishat Koti, Arpita Patra, Rahul Rachuri, and Ajith Suresh
29th Annual Network and Distributed System Security Symposium, NDSS 2022, (2022)
DOI PDF
Mixing arithmetic and boolean circuits to perform privacy-preserving machine learning has become increasingly popular. Towards this, we propose a framework for the case of four parties with at most one active corruption called Tetrad. Tetrad works over rings and supports two levels of security, fairness and robustness. The fair multiplication protocol costs 5 ring elements, improving over the state-of-the-art Trident (Chaudhari et al. NDSS'20). A key feature of Tetrad is that robustness comes for free over fair protocols. Other highlights across the two variants include (a) probabilistic truncation without overhead, (b) multi-input multiplication protocols, and (c) conversion protocols to switch between the computational domains, along with a tailor-made garbled circuit approach. Benchmarking of Tetrad for both training and inference is conducted over deep neural networks such as LeNet and VGG16. We found that Tetrad is up to 4 times faster in ML training and up to 5 times faster in ML inference. Tetrad is also lightweight in terms of deployment cost, costing up to 6 times less than Trident. © 2022 29th Annual Network and Distributed System Security Symposium, NDSS 2022. All Rights Reserved.
[J14]
Relay Placement Algorithms for IoT Connectivity and Coverage in an Outdoor Heterogeneous Propagation Environment
Nihesh Rathod and Rajesh Sundaresan
IEEE Access vol 10, pp 13270 – 13289 (2022)
DOI PDF
A vast majority of the Internet of Things (IoT) devices will be connected in a topology where the edge-devices push data to a local gateway, which forwards the data to a cloud for further processing. In sizeable outdoor deployment regions, the edge-devices may experience poor connectivity due to their distant locations and limited transmission power. Repeaters or relays must be placed at a few locations to ensure reliable connectivity to either a gateway or another node in the network. A big challenge in achieving reliable connectivity and coverage is the outdoor propagation environment being heterogeneous. Engineers often deploy networks based on resource-intensive field visits, detailed surveys, measurements, initial test deployments, followed by fine-tuning. For scalability to large scale IoT deployments, automated network planning tools are essential. Such tools should predict connectivity based on the edge-device locations using available Geographical Information System (GIS) data, identify the need for relays/repeaters, and, if needed, suggest the number of relays needed with their locations. Furthermore, such tools should also be extended to suggest the minimum number and locations of base stations that maximise coverage. In this paper, we propose an automated network deployment framework using a black box received signal strength estimation oracle that provides signal strength estimates between candidate pairs of transceiver locations in a heterogeneous deployment region. Our proposed methodology uses either Ant Colony Optimisation (ACO) or Differential Evolution (DE) to identify the number and locations of relays for meeting specified quality of service constraints. We discuss adaptations of our techniques to handle scenarios with multiple gateways. Further, we show the effectiveness of these algorithms to find suitable candidate base station locations to provide coverage in a heterogeneous propagation environment that meets the specified quality of service constraints. We then demonstrate the effectiveness of our algorithms in two deployment regions. © 2013 IEEE.
[M3]
IMPACT OF WEEKNIGHT AND WEEKEND CURFEWS USING MOBILITY DATA: A CASE STUDY OF BENGALURU URBAN
Aniruddha Adiga, Siva Athreya, Madhav Marathe, Jagadish Midthala, Nihesh Rathod, Rajesh Sundaresan, Srinivasan Venkataramanan, and Sarath Yasodharan
arXiv, (2022)
DOI PDF
Karnataka imposed weeknight and weekend curfews to mitigate the spread of the Omicron variant of SARS-CoV-2. We attempt to assess the impact of curfew using community mobility reports published by Google. Then, we quantify the impact of such restrictions via a simulation study. The pattern of weeknight and weekend curfew, followed by relaxations during the weekdays, seems, at best, to slow and delay the Omicron spread. The simulation outcomes suggest that Omicron eventually spreads and affects nearly as much of the population as it would have without the restrictions. Further, if Karnataka cases trajectory follows the South African Omicron wave trend and the hospitalisation is similar to that observed in well-vaccinated countries (2% of the confirmed cases), then the healthcare requirement is likely within the capacity of Bengaluru Urban when the caseload peaks, with or without the mobility restrictions. On the other hand, if Karnataka cases trajectory follows both the South African Omicron wave trend and the hospitalisation requirement observed there (6.9%), then the healthcare capacity may be exceeded at peak, with or without the mobility restrictions.Competing Interest StatementThe authors have declared no competing interest.Funding StatementThis work was partially supported by the Centre for Networked Intelligence, the Indian Statistical Institute\textquoterights CPDA, the NSF Expedition in Computing Grant CCF-1918656, the NSF RAPID CCF-2142997 and the IISc Institution of Eminence grants.Author DeclarationsI confirm all relevant ethical guidelines have been followed, and any necessary IRB and/or ethics committee approvals have been obtained.YesI confirm that all necessary patient/participant consent has been obtained and the appropriate institutional forms have been archived, and that any patient/participant/sample identifiers included were not known to anyone (e.g., hospital staff, patients or participants themselves) outside the research group so cannot be used to identify individuals.YesI understand that all clinical trials and any other prospective interventional studies must be registered with an ICMJE-approved registry, such as ClinicalTrials.gov. I confirm that any such study reported in the manuscript has been registered and the trial registration ID is provided (note: if posting a prospective study registered retrospectively, please provide a statement in the trial ID field explaining why the study was not registered in advance).YesI have followed all appropriate research reporting guidelines and uploaded the relevant EQUATOR Network research reporting checklist(s) and other pertinent material as supplementary files, if applicable.YesAll data produced in the present work are contained in the manuscript https://www.incovid19.org/ https://apps.bbmpgov.in/Covid19/en/media_pdf/Covid_Bengaluru_19_January_2022%20Bulletin-667.pdf https://www.nicd.ac.za/wp-content/uploads/2022/01/NICD-COVID-19-Daily-Sentinel-Hospital-Surveillance-report-National-20220102.pdf https://www.google.com/covid19/mobility/ https://www.gstatic.com/covid19/mobility/2022-01-15_IN_Karnataka_Mobility_Report_en-GB.pdf
[C24]
Latency-Redundancy Tradeoff in Distributed Read-Write Systems
Saraswathy Ramanathan, Gaurav Gautam, Vikram Srinivasan, and Parimal Parag
2022 14th International Conference on COMmunication Systems and NETworkS, COMSNETS 2022, pp 172 – 180 (2022)
DOI PDF
Data is replicated and stored redundantly over multiple servers for availability in distributed databases. We focus on databases with frequent reads and writes, where both read and write latencies are important. This is in contrast to databases designed primarily for either read or write applications. Redundancy has contrasting effects on read and write latency. Read latency can be reduced by potential parallel access from multiple servers, whereas write latency increases as a larger number of replicas have to be updated. We quantify this tradeoff between read and write latency as a function of redundancy, and provide a closed-form approximation when the request arrival is Poisson and the service is memoryless under prioritized reads. We empirically show that this approximation is tight across all ranges of system parameters. Thus, we provide guidelines for redundancy selection in distributed databases. © 2022 IEEE.
[C23]
A Scalable Container-based Virtualized Data Center Emulation Framework
Gaurav Gautam, Sandhya Rathee, Preetam Patil, and Parimal Parag
2022 14th International Conference on COMmunication Systems and NETworkS, COMSNETS 2022, pp 452 – 454 (2022)
DOI PDF
Data Center Networks (DCNs) powering cloud services as well as social networks pose unique network de-sign/optimization challenges. In response, numerous solutions have been proposed utilizing SDN, programmable data plane, and telemetry. However, testbeds supporting the experimental features while imitating DCN traffic-for implementing and analyzing such solutions-are not trivial to build. We present a data center emulation framework for development and validation of data center algorithms and protocols using lightweight virtualized components such as containers and virtual switches. The framework facilitates automated creation of DCN topologies, telemetry, SDN controller, and data center workload generation at scale. The framework also enables combining diverse virtualized elements and hardware elements. This demo exhibits our in-progress framework implementation that is capable of instantiating a leaf-spine topology with P4-capable switches, gNMI telemetry, BGP routing and end-hosts. © 2022 IEEE.
[J13]
Optimal pricing in multi server systems
Ashok Krishnan K.S., Chandramani Singh, Siva Theja Maguluri, and Parimal Parag
Performance Evaluation vol 154, pp 102282 (2022)
DOI PDF
We study optimal service pricing in server farms where customers arrive according to a renewal process and have independent and identical (i.i.d.) exponential service times and i.i.d. valuations of the service. The service provider charges a time varying service fee aiming at maximizing its revenue rate. The customers that find free servers and service fees lesser than their valuation join for the service else they leave without waiting. We consider both finite server and infinite server farms. We solve the optimal pricing problems using the framework of Markov decision problems. We show that the optimal prices depend on the number of free servers. We propose algorithms to compute the optimal prices. We also establish several properties of the optimal prices and the corresponding revenue rates in the case of Poisson customer arrivals. We illustrate all our findings via numerical evaluation.
[J12]
Latency Optimal Storage and Scheduling of Replicated Fragments for Memory Constrained Servers
Rooji Jinan, Ajay Badita, Pradeep Kiran Sarvepalli, and Parimal Parag
IEEE Transactions on Information Theory vol 68(6), pp 4135 – 4155 (2022)
DOI PDF
We consider the setting of a distributed storage system where a single file is subdivided into smaller fragments of same size which are then replicated with a common replication factor across servers of identical cache size. An incoming file download request is sent to all the servers, and the download is completed whenever the request gathers all the fragments. At each server, we are interested in determining the set of fragments to be stored, and the sequence in which fragments should be accessed, such that the mean file download time for a request is minimized. We model the fragment download time as an exponential random variable independent and identically distributed for all fragments across all servers, and show that the mean file download time can be lower bounded in terms of the expected number of useful servers summed over all distinct fragment downloads. We present deterministic storage schemes that attempt to maximize the number of useful servers. We show that finding the optimal sequence of accessing the fragments is a Markov decision problem, whose complexity grows exponentially with the number of fragments. We propose heuristic algorithms that determine the sequence of access to the fragments which are empirically shown to perform well. © 1963-2012 IEEE.
[C22]
Performance Analysis of Channel-Dependent Rate Adaptation for OFDMA transmission in IEEE 802.11ax WLANs
C. Sheela, Joy Kuri, and Nadeem Akhtar
2022 14th International Conference on COMmunication Systems and NETworkS, COMSNETS 2022, pp 877 – 882 (2022)
DOI PDF
This paper investigates the application of the Received Bit Information Rate (RBIR) mapping technique to abstract the physical (PHY) layer in performing rate adaptation for IEEE WLAN 802.11ax systems. We observe that the modulation and coding scheme (MCS) obtained by PHY Layer Abstraction (PLA) is too conservative when used in practice. Motivated by this observation, we propose Hybrid Channel-Dependent Rate Adaptation (HCDRA) to map the measured SNR to an MCS value that maximizes the throughput while keeping the average Packet Error Rate (PER) below a threshold value. We evaluate HCDRA for a user on a Resource Unit (RU) in the OFDMA mode of transmission. The proposal of channel-dependent rate adaptation in OFDMA mode of transmission for IEEE WLAN 802.11ax is novel to the best of our knowledge. We implement and evaluate HCDRA in the standard-compliant MATLAB WLAN Toolbox and compare its performance with other well-known rate adaptation algorithms such as Automatic Rate Fallback (ARF), Adaptive ARF (AARF), Minstrel, and MutFed. More realistic situations with PHY impairments such as carrier frequency offset (CFO) and symbol timing offset are considered in all our simulations. Results show that HCDRA has better throughput performance compared to the four other algorithms we have evaluated. HCDRA is eminently implementable without any modification in the standard frames, and hence it is suitable for practical deployment. © 2022 IEEE.
[C21]
IEEE 802.15.4e-TSCH MAC Stack Extensions to GNU Radio
Ipsita Sanyal and T.V. Prabhakar
2022 14th International Conference on COMmunication Systems and NETworkS, COMSNETS 2022, pp 199 – 203 (2022)
DOI PDF
In this work we have designed and implemented the IEEE 802.15.4e- TSCH protocol using GNU radio systems. The goal was to create a user configurable tool to test several future applications that might use deterministic MAC protocol. The main blocks that were implemented include: (a) Clear Channel Assessment using energy thresholding (b) Frequency and Channel hopping (c) Frame structure for Enhanced Beacon, Data frame and Enhanced acknowledgment. Results indicate that IEs and their transmission order are satisfied, Channel hopping and TDMA are validated, and interoperability with COTS radio systems performs well. The timeslot for Tx and Rx were implemented to remain within the standard's specification. © 2022 IEEE.
[J11]
Assessing Quality of Control in Tactile Cyber-Physical Systems
Kurian Polachan, Joydeep Pal, Chandramani Singh, and T.V. Prabhakar
IEEE Transactions on Network and Service Management vol 19(4), pp 5348 – 5365 (2022)
DOI PDF
We evolve a methodology and define a metric to evaluate Tactile Cyber-Physical Systems (TCPS). Towards this goal, we use the step response analysis, a well-known control-theoretic method. The adoption includes replacing the human operator (or master) with a controller with known characteristics and analyzing its response to slave side step disturbances. The resulting step response curves demonstrate that the Quality of Control (QoC) metric is sensitive to control loop instabilities and serves as a good indicator of potential factors that contribute to operator-side cybersickness. Through experiments, we demonstrate how QoC accounts for network overheads such as the link latency and jitter and non-networking overheads such as the testbed settings and robot performances in a TCPS. We show that there is a one-to-one correlation between QoC and end-to-end latency, jitter, and packet drops of a TCPS implementation. We show through experiments how QoC can be used to estimate positional errors in tactile-visual control applications. Since higher positional errors can result in poor task performance, estimating them is useful in developing a better-performing TCPS. We also evaluate a TCPS using Fitts' test and compare its results with QoC. We show that QoC is useful in distinguishing TCPS with differences in their specifications that are not detectable using Fitts' test. © 2004-2012 IEEE.
[J10]
TCPSbed: A Modular Testbed for Tactile Internet-Based Cyber-Physical Systems
Kurian Polachan, Joydeep Pal, Chandramani Singh, T.V. Prabhakar, and Fernando A. Kuipers
IEEE/ACM Transactions on Networking vol 30(2), pp 796 – 811 (2022)
DOI PDF
Tactile Internet based Cyber-Physical Systems (TCPS) are highly sensitive to component and communication latencies and packet drops. Building a high performing TCPS, thus, necessitates experimenting with different hardware, algorithms, access technologies, and communication protocols. To facilitate such experiments, we have developed TCPSbed, a modular testbed for TCPS. TCPSbed facilitates the integration of different components, both real and simulated, to realize different TCPS applications and evaluate their latency and control performances. TCPSbed's latency analyzer tool employs a novel method to isolate latencies of individual TCPS components such as the latencies contributed by actuation, sensing, algorithms, and by the network, all in an online fashion. TCPSbed's method of analyzing stability is also novel. It involves the use of the step response analysis method, a classic control-theoretic method used for analyzing the stability of generic control systems. TCPSbed's support for edge intelligence modules enables prediction of command and feedback signals at the network's edge allowing TCPS applications to perform well in adverse network conditions. TCPSbed's source-code, made available through our GitHub page TactileInternet, allows developers to extend its features and functionalities further. In this paper, we describe the architecture and implementation details of TCPSbed and demonstrate its features through several proof-of-concept experiments. © 2022 IEEE.
[C20]
Time-slicing high throughput wifi networks using centralized queueing and scheduling
Vishal Sevani, Purushothaman Saravanan, S.V.R. Anand, Joy Kuri, and Anurag Kumar
WiNTECH 2022 - Proceedings of the 2022 16th ACM Workshop on Wireless Network Testbeds, Experimental evaluation and CHaracterization, Part of MobiCom 2022, pp 53 – 60 (2022)
DOI PDF
We study fine grained (10s of ms) overlay time-slicing, and centralized queuing and scheduling, for the performance management of "high throughput"(HT) IEEE 802.11 standards, where cochannel interference reduces PHY rates and aggregation, causing poor performance. In overlay time-slicing, interference between AP-STA (Access Point and associated Station) links is eliminated by queuing downlink packets in a scheduler, between the wireline network and the APs, and releasing packets to a set of AP-STA links only in their time-slice. This can manage downlink and uplink FTP and HTTP transfers, and downlink packet voice traffic. We utilize a stochastic approximation based closed-loop mechanism that releases only as much data in a time-slice as can be "served,"so that the AP-STA links mapped to that time-slice are inactive at the end of their time-slice, thus, eliminating cochannel interference. Fine-grained overlay time-slicing is demonstrated on an experimental network with two cochannel AP-STA pairs, a setting that we see in our campus WiFi network. In our approach, even for small time-slices (20ms to 50ms), for downlink and uplink TCP bulk transfers, in spite of the scheduler working with partial information, the time-slice boundaries are respected, and performance is close to network utility optimal. Fine-grained time-slicing reduces HTTP access delay, prevents TCP connections over the wide area network from reacting to the path interruptions, and also permits slicing of applications such as interactive packet voice. © 2022 ACM.
[C19]
Opacity and its Trade-offs with Security in Linear Systems
Varkey M. John and Vaibhav Katewa
Proceedings of the IEEE Conference on Decision and Control, pp 5443 – 5449 (2022)
DOI PDF
Opacity and attack detectability are important properties for any system as they allow the states to remain private and malicious attacks to be detected, respectively. In this paper, we show that a fundamental trade-off exists between these properties for a linear dynamical system, in the sense that one cannot have an opaque system without making it vulnerable to undetectable attacks. We first characterize the opacity conditions for the system in terms of its weakly unobservable subspace (WUS) and show that the number of opaque states is proportional to the size of the WUS. Further, we establish conditions under which increasing the opaque sets also increases the set of undetectable attacks. This highlights a fundamental trade-off between security and privacy. We demonstrate our results on a team of delivery UAVs. © 2022 IEEE.
[C18]
Augmented RBMLE-UCB Approach for Adaptive Control of Linear Quadratic Systems
Akshay Mete, Rahul Singh, and P.R. Kumar
Advances in Neural Information Processing Systems, (2022)
DOI PDF
We consider the problem of controlling an unknown stochastic linear system with quadratic costs - called the adaptive LQ control problem. We re-examine an approach called “Reward-Biased Maximum Likelihood Estimate” (RBMLE) [1] that was proposed more than forty years ago, and which predates the “Upper Confidence Bound” (UCB) method as well as the definition of “regret” for bandit problems [2]. It simply added a term favoring parameters with larger rewards to the criterion for parameter estimation. We show how the RBMLE and UCB methods can be reconciled, and thereby propose an Augmented RBMLE-UCB algorithm that combines the penalty of the RBMLE method with the constraints of the UCB method [3], uniting the two approaches to optimism in the face of uncertainty. We establish that theoretically, this method retains Õ(√T) regret, the best known so far. We further compare the empirical performance of the proposed Augmented RBMLE-UCB and the standard RBMLE (without the augmentation) with UCB, Thompson Sampling, Input Perturbation, Randomized Certainty Equivalence and StabL on many real-world examples including flight control of Boeing 747 and Unmanned Aerial Vehicle. We perform extensive simulation studies showing that the Augmented RBMLE consistently outperforms UCB, Thompson Sampling and StabL by a huge margin, while it is marginally better than Input Perturbation and moderately better than Randomized Certainty Equivalence. © 2022 Neural information processing systems foundation. All rights reserved.
[C17]
The RBMLE method for Reinforcement Learning
Akshay Mete, Rahul Singh, and P.R. Kumar
2022 56th Annual Conference on Information Sciences and Systems, CISS 2022, pp 107 – 112 (2022)
DOI PDF
The Reward Biased Maximum Likelihood Estimate (RBMLE) method was proposed about four decades ago for the adaptive control of unknown Markov Decision Processes, and later studied for more general Controlled Markovian Systems and Linear Quadratic Gaussian systems. It showed that if one could bias the Maximum Likelihood Estimate in favor of parameters with larger rewards then one could obtain long-term average optimality. It provided a reason for preferring parameters with larger rewards based on the fact that generally one can only identify the behavior of a system under closed-loop, and therefore any limiting parameter estimate has to necessarily have lower reward than the true parameter. It thereby provided a reason for what his now called 'optimism in the face of uncertainty'. It similarly preceded the definition of 'regret', and it is only in the last three years that it has been analyzed for its regret performance, both analytically, and in comparative simulation testing. This paper provides an account of the RBMLE method for reinforcement learning. © 2022 IEEE.
[C16]
Index-aware reinforcement learning for adaptive video streaming at the wireless edge
Guojun Xiong, Xudong Qin, Bin Li, Rahul Singh, and Jian Li
Proceedings of the International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc), pp 81 – 90 (2022)
DOI PDF
We study adaptive video streaming for multiple users in wireless access edge networks with unreliable channels. The key challenge is to jointly optimize the video bitrate adaptation and resource allocation such that the users' cumulative quality of experience is maximized. This problem is a finite-horizon restless multi-armed multi-action bandit problem and is provably hard to solve. To overcome this challenge, we propose a computationally appealing index policy entitled Quality Index Policy, which is well-defined without the Whittle indexability condition and is provably asymptotically optimal without the global attractor condition. These two conditions are widely needed in the design of most existing index policies, which are difficult to establish in general. Since the wireless access edge network environment is highly dynamic with system parameters unknown and time-varying, we further develop an index-aware reinforcement learning (RL) algorithm dubbed QA-UCB. We show that QA-UCB achieves a sub-linear regret with a low-complexity since it fully exploits the structure of the Quality Index Policy for making decisions. Extensive simulations using real-world traces demonstrate significant gains of proposed policies over conventional approaches. We note that the proposed framework for designing index policy and index-aware RL algorithm is of independent interest and could be useful for other large-scale multi-user problems. © 2022 ACM.
[C15]
Reinforcement Learning Augmented Asymptotically Optimal Index Policy for Finite-Horizon Restless Bandits
Guojun Xiong, Jian Li, and Rahul Singh
Proceedings of the 36th AAAI Conference on Artificial Intelligence, AAAI 2022, pp 8726 – 8734 (2022)
DOI PDF
We study a finite-horizon restless multi-armed bandit problem with multiple actions, dubbed as R(MA)2B. The state of each arm evolves according to a controlled Markov decision process (MDP), and the reward of pulling an arm depends on both the current state and action of the corresponding MDP. Since finding the optimal policy is typically intractable, we propose a computationally appealing index policy entitled Occupancy-Measured-Reward Index Policy for the finite-horizon R(MA)2B. Our index policy is well-defined without the requirement of indexability condition and is provably asymptotically optimal. We then adopt a learning perspective where the system parameters are unknown, and propose R(MA)2B-UCB, a generative model based reinforcement learning augmented algorithm that can fully exploit the structure of Occupancy-Measured-Reward Index Policy. Compared to existing algorithms, R(MA)2B-UCB performs close to offline optimum, as well as achieves a sub-linear regret and a low computational complexity all at once. Experimental results show that R(MA)2B-UCB outperforms existing algorithms in both regret and running time. Copyright © 2022, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.
[J9]
Bayesian Learning-based Link adaptation in IEEE 802.11ax WLANs
Sheela C S and Joy Kuri
Wireless World Research and Trends Magazine, pp 79 - 86 (2022)
DOI PDF
The optimal modulation and coding scheme (MCS) selection in wireless transmission depends on the dynamically evolving channel state. Hence, Rate adaptation in a wireless channel relies on periodically reported channel quality indicator (CQI) values to select the optimal MCS. The latest 802.11ax, with a HE-sounding protocol, supports an explicit feedback mechanism where the client sends back a transformed estimate of the channel state information (CSI) in the HE CQI Report field. When generated more frequently, these reports can be expensive as they introduce unnecessary computational and protocol overhead. Also, the CSI feedback information is quantized, delayed, and noisy. To reduce the frequent CSI feedback (receiver to the transmitter) overhead, in our work, we obtain CSI statistically at the transmitter through Bayesian Learning (BL). Further, we propose a Bayesian Learning based Rate Adaptation (BLbRA) scheme at the transmitter. BLbRA throughput performance is consistent even with reduced feedback overhead. BLbRA can be implemented without any change in the standard frame format, and therefore, it is suitable for practical deployment.

2021

[C14]
Phase Transitions for Support Recovery from Gaussian Linear Measurements
Lekshmi Ramesh, Chandra R. Murthy, and Himanshu Tyagi
IEEE International Symposium on Information Theory - Proceedings, pp 1606 – 1611 (2021)
DOI PDF
We study the problem of recovering the common k-sized support of a set of n samples of dimension d, using m noisy linear measurements per sample. Most prior work has focused on the case when m exceeds k, in which case n of the order (k/m)\log(d/k) is both necessary and sufficient. Thus, in this regime, only the total number of measurements across the samples matter, and there is not much benefit in getting more than k measurements per sample. In the measurement-constrained regime where we have access to fewer than k measurements per sample, we show an upper bound of O((k^2/m^2)\log d) on the sample complexity for successful support recovery when m\geq 2\log d. Along with the lower bound from our previous work, this shows a phase transition for the sample complexity of this problem around k/m=1. In fact, our proposed algorithm is sample-optimal in both the regimes. It follows that, in the m\ll k regime, multiple measurements from the same sample are more valuable than measurements from different samples. © 2021 IEEE.
[J8]
Single-Forking of Coded Subtasks for Straggler Mitigation
Ajay Badita, Parimal Parag, and Vaneet Aggarwal
IEEE/ACM Transactions on Networking vol 29(6), pp 2413 – 2424 (2021)
DOI PDF
Given the unpredictable nature of the nodes in distributed computing systems, some of the tasks can be significantly delayed. Such delayed tasks are called stragglers. Straggler mitigation can be achieved by redundant computation. In maximum distance separable (MDS) redundancy method, a task is divided into k subtasks which are encoded to n coded subtasks, such that a task is completed if any k out of n coded subtasks are completed. Two important metrics of interest are task completion time, and server utilization which is the aggregate completed work by all servers in this duration. We consider a proactive straggler mitigation strategy where n0 out of n coded subtasks are started at time 0 while the remaining n-n0 coded subtasks are launched when ℓ0≤ min of the initial ones finish. The coded subtasks are halted when k of them finish. For this flexible forking strategy with multiple parameters, we analyze the mean of two performance metrics when the random service completion time at each server is independent and distributed identically (i.i.d.) to a shifted exponential. From this study, we find a tradeoff between the metrics which provides insights into the parameter choices. Experiments on Intel DevCloud illustrate that the shifted exponential distribution adequately captures the random coded subtask completion times, and our derived insights continue to hold. © 2021 IEEE.
[C13]
Low latency replication coded storage over memory -constrained servers
Rooji Jinan, Ajay Badita, Pradeep Sarvepalli, and Parimal Parag
IEEE International Symposium on Information Theory - Proceedings, pp 2340 – 2345 (2021)
DOI PDF
We consider a distributed storage system storing a single file, where the file is divided into equal sized fragments. The fragments are replicated with a common replication factor, and stored across servers with identical storage capacity. An incoming download request for this file is sent to all the servers, and it is considered serviced when all the unique fragments are downloaded. The download time for all fragments across all servers, is modeled as an independent and identically distributed (i.i.d.) random variable. The mean download time can be bounded in terms of the expected number of useful servers available after gathering each fragment. We find the mean number of useful servers after collecting each fragment, for a random storage scheme for replication codes. We show that the performance of the random storage for replication code achieves the upper bound for expected number of useful servers at every download asymptotically in number of servers for any storage capacity. Further, we show that the performance of this storage scheme is comparable to that of Maximum Distance Separable (MDS) coded storage. © 2021 IEEE.
[C12]
The four levels of fixed-points in mean-field models
Sarath Yasodharan and Rajesh Sundaresan
2021 National Conference on Communications, NCC 2021, (2021)
DOI PDF
The fixed-point analysis refers to the study of fixed-points that arise in the context of complex systems with many interacting entities. In this expository paper, we describe four levels of fixed-points in mean-field interacting particle systems. These four levels are (i) the macroscopic observables of the system, (ii) the probability distribution over states of a particle at equilibrium, (iii) the time evolution of the probability distribution over states of a particle, and (iv) the probability distribution over trajectories. We then discuss relationships among the fixed-points at these four levels. Finally, we describe some issues that arise in the fixed-point analysis when the system possesses multiple fixed-points at the level of distribution over states, and how one goes beyond the fixed-point analysis to tackle such issues. © 2021 IEEE.
[C11]
GenSys: A scalable fixed-point engine for maximal controller synthesis over infinite state spaces
Stanly Samuel, Deepak D'Souza, and Raghavan Komondoor
ESEC/FSE 2021 - Proceedings of the 29th ACM Joint Meeting European Software Engineering Conference and Symposium on the Foundations of Software Engineering, pp 1585 – 1589 (2021)
DOI PDF
The synthesis of maximally-permissive controllers in infinite-state systems has many practical applications. Such controllers directly correspond to maximal winning strategies in logically specified infinite-state two-player games. In this paper, we introduce a tool called GenSys which is a fixed-point engine for computing maximal winning strategies for players in infinite-state safety games. A key feature of GenSys is that it leverages the capabilities of existing off-the-shelf solvers to implement its fixed point engine. GenSys outperforms state-of-the-art tools in this space by a significant margin. Our tool has solved some of the challenging problems in this space, is scalable, and also synthesizes compact controllers. These controllers are comparatively small in size and easier to comprehend. GenSys is freely available for use and is available under an open-source license. © 2021 ACM.
[C10]
Order statistics based collision analysis for PUFs
Girish Vaidya, Chandramani Singh, and T.V. Prabhakar
2021 National Conference on Communications, NCC 2021, (2021)
DOI PDF
Physically unclonable functions (PUFs) exploit the inherent manufacturing variations for generating a device identifier. However, different devices may map to the same identifier causing a 'collision'. It is imperative to determine the probability of such collisions before a PUF is deployed for an application. We present a framework that computes the collision probabilities based on its inter-device and intra-device variations. This framework could be used for determining the collision probabilities, tuning the PUF attributes as well as to compare different PUF implementations. We demonstrate the use of our framework for real-world applications by comparing the results from our analyses with data from experiments and numerical simulation. © 2021 IEEE.
[C9]
Hardware Implementation of Cell-Free MIMO and Dynamic TDD using the OAI 5G NR Codebase
Himani Kamboj, Bhawesh Anand, Sanjhi Gupta, Ashish Meshram, Sudhakar Balijepalli, and Chandra R. Murthy
WSA 2021 - 25th International ITG Workshop on Smart Antennas, pp 362 – 366 (2021)
DOI PDF
The cell-edge user in a traditional cellular network experiences degraded quality of service compared to a user at the centre of the cell due to path loss and interference from neighboring base stations (BSs). Cell-free multiple input and multiple output (MIMO) is a promising technology that can improve the cell-edge performance as it offers macro-diversity and consequently improved coverage and throughput. Moreover, the network capacity in a cellular network is often underutilized due to a static time division duplex (TDD) configuration coupled with asymmetric traffic demands in neighboring cells. To handle heterogeneous traffic demands, dynamic TDD is considered to be a beneficial technology, wherein different cells can independently schedule slots in the uplink (UL)/downlink (DL) directions depending on their local traffic demands. However, dynamic TDD brings new challenges because of the introduction of cross-link interferences (CLI) between users and between BSs. Combining cell-free MIMO with dynamic TDD can effectively overcome the CLI, as there exists inbuilt co-operation between the access points (APs) in the cell-free MIMO architecture. This paper presents a hardware implementation of cell-free MIMO and dynamic TDD using the OPENAIRINTERFACE (OAI) 5G new radio (NR) software stack, with the aim to experimentally understand the role of cell-free MIMO and dynamic TDD in providing better connectivity at the cell-edge and improving network throughput. © VDE VERLAG GMBH ∙ Berlin ∙ Offenbach.
[C8]
OTFS Modulation in Dual-LED Indoor Visible Light Communication Systems
Sujata Sinha and A. Chockalingam
IEEE Vehicular Technology Conference, (2021)
DOI PDF
In this paper, we investigate the use of a new modulation scheme recently introduced in the RF domain, called orthogonal time frequency space (OTFS) modulation, in an indoor visible light communication (VLC) setting. In particular, we consider VLC systems that employ dual-LED schemes for transmission. The following dual-LED schemes are considered: 1) non-DC biased (NDC) scheme, and 2) dual-LED complex modulation (DCM) scheme. The proposed NDC-OTFS scheme uses 2-dimension (2D) Hermitian symmetry operation to convert complex signals to positive, real-valued signals suitable for transmission in the optical domain, and the proposed DCM-OTFS scheme achieves this by exploiting the polar representation of complex signals. We obtain analytical upper bounds on the bit error performance of the proposed NDC-OTFS and DCM-OTFS schemes, which are found to be tight at high signal-to-noise ratios (SNR). Our analytical and simulation results show that the proposed NDC-OTFS and DCM-OTFS schemes achieve better performance, respectively, compared to NDC-OFDM and DCM-OFDM schemes known in the VLC literature. Further, using the ratio of the minimum distance of different normalized received signal sets as a metric, we quantify the spatial distribution of the SNR gain of the proposed NDC-OTFS/DCM-OTFS schemes compared to NDC-OFDM/DCM-OFDM schemes. © 2021 IEEE.
[C7]
Quad-LED OTFS Modulation in Indoor Visible Light Communication Systems
Sujata Sinha and A. Chockalingam
Proceedings - IEEE Global Communications Conference, GLOBECOM, (2021)
DOI PDF
In this paper, we investigate orthogonal time frequency space (OTFS) modulation in multi-LED indoor visible light wireless communications. Specifically, we propose two quad-LED OTFS schemes, namely, 1) quad-LED complex modulation OTFS (QCM-OTFS), and 2) spatial modulation dual-LED complex modulation OTFS (SM-DCM-OTFS). The proposed QCM-OTFS scheme sends the magnitudes of real and imaginary parts of complex signals through intensity modulation (IM) and their sign information through spatial indexing of LEDs. The proposed SM-DCM-OTFS scheme sends the magnitude and phase of complex signals (polar representation) through a pair of LEDs and frame indexing across two pairs of LEDs. The proposed schemes do not require Hermitian symmetry and DC bias operations to obtain real positive valued signals suited for IM of LEDs. We obtain upper bounds on the bit error rate (BER) performance of the proposed schemes, which are tight at high signal-to-noise ratios (SNR). Compared to the QCM-OFDM and SM-DCM-OFDM schemes known in the literature, the proposed schemes achieve significantly better BER performance. We also analyze the spatial distribution of the SNR gain in the proposed QCM-OTFS/SM-DCM-OTFS schemes compared to QCM-OFDM/SM-DCM-OFDM schemes using the ratio of minimum distance of normalized received signal sets as a metric. © 2021 IEEE.
[C6]
Attention Actor-Critic Algorithm for Multi-Agent Constrained Co-operative Reinforcement Learning
P. Parnika, Raghuram Bharadwaj Diddigi, Sai Koti Reddy Danda, and Shalabh Bhatnagar
Proceedings of the 20th International Conference on Autonomous Agents and MultiAgent Systems, pp 1616–1618 (2021)
DOI PDF
In this work, we consider the problem of computing optimal actions for Reinforcement Learning (RL) agents in a co-operative setting, where the objective is to optimize a common goal. However, in many real-life applications, the agents are also required to satisfy certain constraints specified on their actions. Under this setting, the objective of the agents is to not only learn the actions that optimize the common objective but also meet the specified constraints. In recent times, the Actor-Critic algorithm with an attention mechanism has been successfully applied to obtain optimal actions for RL agents in multi-agent environments. In this work, we extend this algorithm to the constrained multi-agent RL setting.
[M2]
Strategies to Mitigate COVID-19 Resurgence Assuming Immunity Waning: A Study for Karnataka, India
Aniruddha Adiga, Siva Athreya, Bryan Lewis, Madhav V. Marathe, Nihesh Rathod, Rajesh Sundaresan, Samarth Swarup, Srinivasan Venkatramanan, and Sarath Yasodharan
arXiv, (2021)
DOI PDF
COVID-19 vaccination is being rolled out among the general population in India. Spatial heterogeneities exist in seroprevalence and active infections across India. Using a spatially explicit age-stratified model of Karnataka at the district level, we study three spatial vaccination allocation strategies under different vaccination capacities and a variety of non-pharmaceutical intervention (NPI) scenarios. The models are initialised using on-the-ground datasets that capture reported cases, seroprevalence estimates, seroreversion and vaccine rollout plans. The three vaccination strategies we consider are allocation in proportion to the district populations, allocation in inverse proportion to the seroprevalence estimates, and allocation in proportion to the case-incidence rates during a reference period.The results suggest that the effectiveness of these strategies (in terms of cumulative cases at the end of a four-month horizon) are within 2% of each other, with allocation in proportion to population doing marginally better at the state level. The results suggest that the allocation schemes are robust and thus the focus should be on the easy to implement scheme based on population. Our immunity waning model predicts the possibility of a subsequent resurgence even under relatively strong NPIs. Finally, given a per-day vaccination capacity, our results suggest the level of NPIs needed for the healthcare infrastructure to handle a surge.Competing Interest StatementThe authors have declared no competing interest.Funding StatementThis work was partially supported by Google Grants, the Centre for Networked Intelligence, the SERB-MATRICS grant, National Institutes of Health (NIH) Grant R01GM109718, NSF BIG DATA Grant IIS-1633028, NSF Grant No.: OAC-1916805, NSF Expeditions in Computing Grant CCF-1918656, NSF RAPID CNS-2028004, NSF RAPID OAC-2027541.Author DeclarationsI confirm all relevant ethical guidelines have been followed, and any necessary IRB and/or ethics committee approvals have been obtained.YesThe details of the IRB/oversight body that provided approval or exemption for the research described are given below:Not requiredAll necessary patient/participant consent has been obtained and the appropriate institutional forms have been archived.YesI understand that all clinical trials and any other prospective interventional studies must be registered with an ICMJE-approved registry, such as ClinicalTrials.gov. I confirm that any such study reported in the manuscript has been registered and the trial registration ID is provided (note: if posting a prospective study registered retrospectively, please provide a statement in the trial ID field explaining why the study was not registered in advance).YesI have followed all appropriate research reporting guidelines and uploaded the relevant EQUATOR Network research reporting checklist(s) and other pertinent material as supplementary files, if applicable.YesData used is from publicly available data sources. https://des.kar.nic.in/docs/ProjectedPopulation2012-2021.pdf
[J7]
Second round statewide sentinel-based population survey for estimation of the burden of active infection and anti-SARS-CoV-2 IgG antibodies in the general population of Karnataka, India, during January-February 2021
M Rajagopal Padma, Prameela Dinesh, Rajesh Sundaresan, Siva Athreya, Shilpa Shiju, Parimala S Maroor, R Lalitha Hande, Jawaid Akhtar, Trilok Chandra, Deepa Ravi, Eunice Lobo, Yamuna Ana, Prafulla Shriyan, Anita Desai, Ambica Rangaiah, Ashok Munivenkatappa, S. Krishna, Shantala Gowdara Basawarajappa, H.G. Sreedhara, K.C. Siddesh, B. Amrutha Kumari, Nawaz Umar, B.A. Mythri, K.M. Mythri, Mysore Kalappa Sudarshan, Ravi Vasanthapuram, and Giridhara R Babu
IJID Regions vol 1, pp 107 – 116 (2021)
DOI PDF
Objective: Demonstrate the feasibility of using the existing sentinel surveillance infrastructure to conduct the second round of the serial cross-sectional sentinel-based population survey. Assess active infection, seroprevalence, and their evolution in the general population across Karnataka. Identify local variations for locally appropriate actions. Additionally, assess the clinical sensitivity of the testing kit used on account of variability of antibody levels in the population. Methods: The cross-sectional study of 41,228 participants across 290 healthcare facilities in all 30 districts of Karnataka was done among three groups of participants (low, moderate, and high-risk). The geographical spread was sufficient to capture local variations. Consenting participants were subjected to real-time reverse transcription-polymerase chain reaction (RT-PCR) testing, and antibody (IgG) testing. Clinical sensitivity was assessed by conducting a longitudinal study among participants identified as COVID-19 positive in the first survey round. Results: Overall weighted adjusted seroprevalence of IgG was 15.6% (95% CI: 14.9–16.3), crude IgG prevalence was 15.0% and crude active infection was 0.5%. Statewide infection fatality rate (IFR) was estimated as 0.11%, and COVID-19 burden estimated between 26.1 to 37.7% (at 90% confidence). Further, Cases-to-infections ratio (CIR) varied 3-35 across units and IFR varied 0.04–0.50% across units. Clinical sensitivity of the IgG ELISA test kit was estimated as ≥38.9%. Conclusion: We demonstrated the feasibility and simplicity of sentinel-based population survey in measuring variations in subnational and local data, useful for locally appropriate actions in different locations. The sentinel-based population survey thus helped identify districts that needed better testing, reporting, and clinical management. The state was far from attaining natural immunity during the survey and hence must step up vaccination coverage and enforce public health measures to prevent the spread of COVD-19. © 2021 The Authors
[M1]
Modeling Performance and Energy trade-offs in Online Data-Intensive Applications
Ajay Badita, Rooji Jinan, Balajee Vamanan, and Parimal Parag
arXiv, (2021)
DOI PDF
We consider energy minimization for data-intensive applications run on large number of servers, for given performance guarantees. We consider a system, where each incoming application is sent to a set of servers, and is considered to be completed if a subset of them finish serving it. We consider a simple case when each server core has two speed levels, where the higher speed can be achieved by higher power for each core independently. The core selects one of the two speeds probabilistically for each incoming application request. We model arrival of application requests by a Poisson process, and random service time at the server with independent exponential random variables. Our model and analysis generalizes to today's state-of-the-art in CPU energy management where each core can independently select a speed level from a set of supported speeds and corresponding voltages. The performance metrics under consideration are the mean number of applications in the system and the average energy expenditure. We first provide a tight approximation to study this previously intractable problem and derive closed form approximate expressions for the performance metrics when service times are exponentially distributed. Next, we study the trade-off between the approximate mean number of applications and energy expenditure in terms of the switching probability.
[J6]
Observability of Discrete-Time LTI Systems under Unknown Piece-Wise Constant Inputs
Vipul Kumar Sharma and Pavankumar Tallapragada
IEEE Control Systems Letters vol 5(6), pp 1886 – 1891 (2021)
DOI PDF
This letter is on observability of discrete-time LTI systems under unknown piece-wise constant inputs with sufficiently slow, but arbitrary update times. Assuming knowledge of the update times, we characterize the unobservable subspace and show that with sufficiently many measurements in each inter-update interval of the input, the unobservable subspace remains fixed. We explore the implications of the result for privacy in event-triggered control through an illustrative example. © 2017 IEEE.
[J5]
Event-triggered second-moment stabilisation under action-dependent Markov packet drops
Shourya Bose and Pavankumar Tallapragada
IET Control Theory and Applications vol 15(7), pp 949 – 964 (2021)
DOI PDF
This paper considers the problem of the second-moment stabilisation of a scalar linear plant with process noise. It is assumed that the sensor communicates with the controller over an unreliable channel, whose state evolves according to a Markov chain, with the transition matrix on a timestep depending on whether there is a transmission on that timestep. Under such a setting, an event-triggered transmission policy is proposed which meets the objective of exponential convergence of the second moment of the plant state to an ultimate bound. Further, upper bounds on the transmission fraction of the proposed policy are provided. The results are illustrated through an example scenario of control in the presence of a battery-equipped energy-harvesting sensor. The proposed control design as well as the analytical guarantees are verified through simulations for the example scenario. © 2021 The Authors. IET Control Theory & Applications published by John Wiley & Sons Ltd on behalf of The Institution of Engineering and Technology
[C5]
MPCLEAGUE: ROBUST 4-PARTY COMPUTATION FOR PRIVACY-PRESERVING MACHINE LEARNING
Nishat Koti, Arpita Patra, and Ajith Suresh
International Conference on Learning Representations (ICLR) 2021, (2021)
DOI PDF
Secure computation has demonstrated its potential in several practical use-cases, particularly in privacy-preserving machine learning (PPML). Robustness, the property that guarantees output delivery irrespective of adversarial behaviour, and efficiency, are the two first-order asks of a successfully deployable PPML framework. Towards this, we propose the first robust, highly-efficient mixed-protocol framework, MPCLeague that works with four parties, offers malicious security, and supports ring. MPCLeague has a multifold improvement over ABY3 (Mohassel et al. CCS'18), a 3-party framework achieving security with abort, and improves upon Trident (Chaudhari et al. NDSS’20), a 4-party framework achieving security with fairness. MPCLeague's competence is tested with extensive benchmarking for deep neural networks such as LeNet and VGG16, and support vector machines.

2020

[J4]
Coverage Estimation in Outdoor Heterogeneous Propagation Environments
Nihesh Rathod, Renu Subramanian, and Rajesh Sundaresan
IEEE Access vol 8, pp 31660 – 31673 (2020)
DOI PDF
This paper is on a coverage estimation procedure for the deployment of outdoor Internet of Things (IoT). In the first part of the paper, a data-driven coverage estimation technique is proposed. The estimation technique combines multiple machine-learning-based regression ideas. The proposed technique achieves two purposes. The first purpose is to reduce the bias in the estimated received signal strength arising from estimations performed only on the successfully received packets. The second purpose is to exploit commonality of physical parameters, e.g. antenna-gain, in measurements that are made across multiple propagation environments. It also provides the correct link function for performing a nonlinear regression in our communication systems context. In the second part of the paper, a method to use readily available geographic information system (GIS) data (for classifying geographic areas into various propagation environments) followed by an algorithm for estimating received signal strength (which is motivated by the first part of the paper) is proposed. Together they enable quick and automated estimation of coverage in outdoor environments. It is anticipated that these will lead to faster and more efficient deployment of outdoor Internet of Things. © 2013 IEEE.
[J3]
Minimizing Latency for Secure Coded Computing Using Secret Sharing via Staircase Codes
Rawad Bitar, Parimal Parag, and Salim El Rouayheb
IEEE Transactions on Communications vol 68(8), pp 4609 – 4619 (2020)
DOI PDF
We consider the setting of a Master server, M, who possesses confidential data and wants to run intensive computations on it, as part of a machine learning algorithm for example. The Master wants to distribute these computations to untrusted workers who volunteered to help with this task. However, the data must be kept private in an information theoretic sense. Some of the workers may be stragglers, e.g., slow or busy. We are interested in reducing the delays experienced by the Master. We focus on linear computations as an essential operation in many iterative algorithms. We propose a solution based on new codes, called Staircase codes, introduced previously by two of the authors. Staircase codes allow flexibility in the number of stragglers up to a given maximum, and universally achieve the information theoretic limit on the download cost by the Master, leading to latency reduction. We find upper and lower bounds on the Master's mean waiting time. We derive the distribution of the Master's waiting time, and its mean, for systems with up to two stragglers. We show that Staircase codes always outperform existing solutions based on classical secret sharing codes. We validate our results with extensive implementation on Amazon EC2. © 2020 IEEE.
[J2]
Optimal Server Selection for Straggler Mitigation
Ajay Badita, Parimal Parag, and Vaneet Aggarwal
IEEE/ACM Transactions on Networking vol 28(2), pp 709 – 721 (2020)
DOI PDF
The performance of large-scale distributed compute systems is adversely impacted by stragglers when the execution time of a job is uncertain. To manage stragglers, we consider a multi-fork approach for job scheduling, where additional parallel servers are added at forking instants. In terms of the forking instants and the number of additional servers, we compute the job completion time and the cost of server utilization when the task processing times are assumed to have a shifted exponential distribution. We use this study to provide insights into the scheduling design of the forking instants and the associated number of additional servers to be started. Numerical results demonstrate orders of magnitude improvement in cost in the regime of low completion times as compared to the prior works. © 1993-2012 IEEE.
[J1]
Real-Time Status Updates with Perfect Feedback over Erasure Channels
Sarat Chandra Bobbili, Parimal Parag, and Jean-Francois Chamberland
IEEE Transactions on Communications vol 68(9), pp 5363 – 5374 (2020)
DOI PDF
Real-time decision making relies on the availability of accurate data and, therefore, delivering status updates in a timely fashion is of paramount importance. The topic of real-time status updates has received much attention in recent years. This article contributes new results to this research area by studying the interplay between average timeliness and design decisions made at the physical layer, for unreliable communication channels. Specifically, this study explores the tension between the fact that more reliable transmissions with lower probabilities of decoding failure tend to improve timely delivery, unless these improvements come at the expense of significantly longer codewords. The average timeliness is adopted as an evaluation criterion, and a framework to efficiently compute the performance of various transmission schemes for the binary erasure channel is developed. We show that the average timeliness decreases as we increase the feedback rate in a hybrid ARQ scheme for a range of codeword lengths. This article also provides design guidelines for the codeword length selection for an hybrid ARQ scheme to improve the average information timeliness. Numerical examples are included to further illustrate the applicability of our findings. © 1972-2012 IEEE.
[C4]
Evolution of a population of selfish agents on a network
Nirabhra Mandal and Pavankumar Tallapragada
IFAC-PapersOnLine, pp 3385 – 3390 (2020)
DOI PDF
In this work, we consider a population composed of a continuum of agents that seek to selfishly minimize a cost function by moving on a network. The nodes in the network may represent physical locations or abstract choices. Taking inspiration from how water distributes itself in a system of connected tanks of varying heights, we formulate a best response dynamics for the population. In this dynamics, the population in each node simultaneously seeks to redistribute itself according to the 'best response' to the state of the population in the node's neighborhood. We provide an algorithm to determine the best response as a function of the state of the population. We then show that given the state of the population, the best response is unique. For the continuous time version of the best response dynamics, we show asymptotic convergence to an equilibrium point for an arbitrary initial condition. We then explore a second dynamics, in which the population evolves according to centralized gradient descent of the social cost. Again, we show asymptotic convergence for an arbitrary initial condition. We illustrate our results through simulations. Copyright © 2020 The Authors. This is an open access article under the CC BY-NC-ND license
[C3]
Analysis of Inter-Event Times for Planar Linear Systems under a General Class of Event Triggering Rules
Anusree Rajan and Pavankumar Tallapragada
Proceedings of the IEEE Conference on Decision and Control, pp 5206 – 5211 (2020)
DOI PDF
This paper analyzes the evolution of inter-event times for a planar linear system under a general class of scale-invariant event triggering rules. For scale-invariant event triggering rules, the inter-event time is a function of only the angle of the state at an event. We analyze the properties of this inter-event time function such as periodicity and continuity. In particular, the inter-event time function is continuous except for finitely many angles and we provide sufficient conditions under which the inter-event time function is continuous. Then, we analyze the evolution of the angle of the state from one event to the next and reduce the problem of studying the evolution of the inter-event times to that of studying the angle map and its fixed points. For a specific triggering rule, we provide necessary conditions for the convergence of inter-event time to a steady state value. We illustrate the proposed results through numerical simulations. © 2020 IEEE.
[C2]
Event-triggered Stabilization for Nonlinear Systems with Center Manifolds
Akshit Saradagi, Arun D. Mahindrakar, and Pavankumar Tallapragada
Proceedings of the IEEE Conference on Decision and Control, pp 751 – 756 (2020)
DOI PDF
In this work, we consider event-based implementation of control laws designed for local stabilization of nonlinear systems with center-manifolds. The systems being considered possess linearised models with uncontrollable modes on the imaginary axis. The controller chosen decides both the structure of the center-manifold and its stability. Although the control of systems with center-manifolds is well studied, event-based control of such systems is yet to be probed. This involves the exploration of input-to-state stability (ISS) properties of such systems, with respect to measurement errors. Considering the most general structure for the controller, we prove that a controller that locally asymptotically stabilizes the dynamics on the center-manifold, also renders the overall system locally input-to-state stable (LISS) and find the comparison functions involved in the Lyapunov characterization of ISS. This general characterization required a nonlinear change of variables, involving the center-manifold, which can only be approximately determined in most cases. Because of this, it is found to be unsuitable for designing event-triggered controllers. We then explore an approach that does not resort to this change of variables and present our findings. We discuss the possibility of a simpler relative thresholding mechanism and present simulation results for an illustrative example. © 2020 IEEE.

2019

[C1]
Probabilistic Forwarding of Coded Packets on Networks
B.R. Vinay Kumar and Navin Kashyap
IEEE International Symposium on Information Theory - Proceedings, pp 1952 – 1956 (2019)
DOI PDF
We consider a scenario of broadcasting information over a network of nodes connected by noiseless communication links. A source node in the network has k data packets to broadcast, and it suffices that a large fraction of the network nodes receives the broadcast. The source encodes the k data packets into n≥k coded packets using a maximum distance separable (MDS) code, and transmits them to its one-hop neighbours. Every other node in the network follows a probabilistic forwarding protocol, in which it forwards a previously unreceived packet to all its neighbours with a certain probability p. A "near-broadcast" is when the expected fraction of nodes that receive at least k of the n coded packets is close to 1. The forwarding probability p is chosen so as to minimize the expected total number of transmissions needed for a near-broadcast. In this paper, we analyze the probabilistic forwarding of coded packets on two specific network topologies: binary trees and square grids. For trees, our analysis shows that for fixed k, the expected total number of transmissions increases with n. On the other hand, on grids, we use ideas from percolation theory to show that a judicious choice of n will significantly reduce the expected total number of transmissions needed for a near-broadcast. © 2019 IEEE.

Publications

C: Conference proceedings

J: Journal articles

M: Miscellaneous

2025

2024

2023

2022

2021

2020

2019