Events Calendar

Communications, Networks & Systems (CommNetS) Seminar

Speaker: Dr. Rajgopal Kannan, Louisiana State University

Talk Title: Balancing Delay and Congestion Costs in Scheduling and Computing Bottleneck Congestion Equilibria

Series: CommNetS

Abstract: We consider the problem of minimum cost scheduling of an arbitrary sequence of packet arrivals over a given time frame where the cost of transmission during a slot is the sum of an arbitrary function of the congestion (number of packets transmitted) during that slot and the delay incurred by these packets. This problem could arise in various contexts such as wireless link transmissions where both congestion costs and scheduling delays must be balanced as well as in transactional memory systems where one can complete a transaction during a slot by paying a cost proportional to the number of interfering transactions during that slot (the congestion) or defer by some slots and try again. We find the offline optimal solution to this problem given the exact sequence of packet arrivals and then develop algorithms with constant factor competitive ratio for the online version of the problem in which the sequence of packet arrivals is unknown. For the second part of the talk, we consider the problem of computing bottleneck congestion equilibria in networks. This problem has been shown to be PLS complete and we describe an algorithm for finding logN approximate equilibra.

Biography: Rajgopal Kannan is a Professor in the Computer Science Department at Louisiana State University. He obtained his PhD from the University of Denver and a B.Tech from IIT-Bombay. His areas of interest are in wireless network algorithms, game-theory and cybersecurity. He is currently on sabbatical at the ANRG group at USC with Prof. Bhaskar Krishnamachari.

Host: Prof. Ashutosh Nayyar and the Ming Hsieh Institute

Location: Hughes Aircraft Electrical Engineering Center (EEB) - 248

Audiences: Everyone Is Invited

Contact: Annie Yu