Monthly Newsletter from CNI

Issue - November 2023


Upcoming talks


Join us in the upcoming talk by Dr. Neeraj Kayal, Principal Researcher at the Microsoft Research lab, Bengaluru to learn about Applications of Algebraic Complexity to unsupervised learning in which he will highlight proof techniques for proving hardness of computing certain polynomials and illustrate how these proof techniques lead to efficient algorithms for learning arithmetic circuits and for unsupervised learning.  


Dr. Neeraj Kayal is a renowned researcher in complexity theory and theoretical computer science. He, along with his colleagues Manindra Agrawal and Nitin Saxena, developed the first deterministic polynomial time primality testing algorithm, earning recognition through awards like the Godel Prize (2006) and Fulkerson Prize (2006). With expertise in complexity theory and algorithms, he continues to contribute significantly to algebraic complexity theory, earning best paper awards and honors, including the Infosys Prize and Bhatnagar Award.  


What’s cooking at the CNI ?


Load balancing policies without feedback using timed replicas

This is a recent work by Rooji Jinan, Ajay Badita, Tejas Bodas, and Parimal Parag to appear in the November issue of Performance Evaluation. (Performance Evaluation is a leading journal in modelling, measurement, and evaluation of performance aspects of computing and communication systems. Check out their work here to learn more).  

A load balancing system consists of a dispatcher that routes the incoming jobs to the queues of a subset of homogeneous servers. When the instantaneous queue length or queue workload is known, the optimal dispatch policy is to join the shortest queue (JSQ) or join the queue with the smallest workload (JSW). However, in most real-life systems, this information is not available. One way to tackle this problem is to query this information from a random subset of these servers and implement this policy on that subset. However, this policy becomes intractable in large systems.  


In redundancy-based load balancing policies, the dispatcher creates replicas of the incoming job and sends it to a subset of the servers, thus avoiding the need to query instantaneous state information. However, these policies require dispatcher-side cancellation of the redundant jobs once the job has been served by one of the servers. Synchronized cancelling of the redundant replica is an implementation challenge. This work proposes a policy in which the dispatcher duplicates each job and appends a timer to each replicated job referred to as a server-side cancellation criterion. A replica is discarded if its timer expires before it starts receiving service. The authors analyze several variants of this policy which are novel and simple to implement. Numerical computations on variants of the proposed policy indicate that the proposed policy outperforms popular feedback-based policies for low arrival rates, despite no feedback from servers to the dispatcher.


Achievements Corner


Sheela C S, CNI PhD fellow from Department of Electronic Systems Engineering, IISc Bangalore received distinguished Alumni award in the category of Academic excellence from her Alma mater R N S Institute of Technology, Bangalore. Congratulations Sheela! 


Past Events

Providing high reliability in the Google global network .


During an engaging presentation, Dr. Ranjita Bhagwan, Principal Engineer at Google, delved into the topic of ensuring robust reliability within Google's expansive global network. Google owns and manages one of the world's largest networks, serving billions of users. Today, this network not only caters to Google's diverse range of applications, including Search, YouTube, Gmail, and Maps, but also plays a crucial role in supporting enterprise customers of the Google Cloud Platform. Given the vast scale and demanding requirements of these diverse applications, the network employs many aligned yet complementary techniques to guarantee network reliability. In her presentation, Dr. Bhagwan elucidated some of these techniques and how they collaboratively function to deliver a dependable network experience for all Google users.

Multi-AP Coordination in Wi-Fi Networks using Centrally Controlled Overlay Time-Sliced Scheduling.


Prof Anurag Kumar presented a discussion on their ongoing project titled "ADWISER: Centralized Overlay Time-Sliced Scheduling for Multi-AP Coordination in Wi-Fi Networks". This research work introduced a centrally controlled overlay solution with the goal of enhancing the performance management of Wi-Fi networks. ADWISER's primary objective is to optimize user-level performance by implementing a centralized queuing and scheduling mechanism. A typical commercial Wi-Fi access point operates on longer time scales and lacks user level visibility and performance management capabilities. ADWISER works at the user and connection level while aiming to maximize overall network utility. In the absence of a multi-AP coordination control plane, ADWISER utilizes various measurement and learning techniques, with no explicit support from the devices it controls. The work highlights the substantial advantages that explicit multi-AP coordination can reap, and the need for a substantially enhanced control plane.

Multi-AP Coordination in Wi-Fi Networks using Centrally Controlled Overlay | Prof. Anurag Kumar
Facebook icon Instagram icon Twitter icon YouTube icon