BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/745
DTSTAMP:20230914T125936Z
SUMMARY:Throughput-Optimal Algorithms for Generalized Flow Problems
DESCRIPTION:Speaker: Abhishek Sinha (Massachusetts Institute of Technology\
 nLaboratory for Information and Decision Systems\nCambridge\, MA 02139\nUn
 ited States of America)\n\nAbstract: \nOne of the fundamental problems in 
 Computer Networking is to efficiently transport packets belonging to diffe
 rent sessions\, such as unicast\, broadcast\, multicast and anycast\, coll
 ectively known as the generalized flows. The problem is to design an effic
 ient routing\, and wireless link scheduling policy\, which achieves the en
 tire capacity region. Currently\, a throughput-optimal algorithm (Backpres
 sure) is known only for the unicast problem and little progress has been m
 ade towards a universal algorithm addressing the generalized flow problem.
  In this thesis\, we propose provably optimal algorithms for the broadcast
  and the generalized flow problems.\n\nWe begin our study with the problem
  of optimal broadcasting in a wireless Directed Acyclic Graph (DAG). Exist
 ing policies achieve the broadcast capacity by balancing traffic over a se
 t of spanning trees\, which are difficult to maintain in a large and time-
 varying network. We propose a fundamentally new broadcast policy\, which i
 s decentralized\, utilizes local queue-length information only\, does not 
 require the use of global topological structures\, such as spanning trees 
 and offers the useful feature of in-order delivery of packets. It also yie
 lds a new characterization of broadcast capacity in wireless DAGs\, which 
 further leads to an efficient algorithm for computing the capacity under t
 he primary interference constraints. The algorithm extends gracefully to t
 ime-varying wireless networks. We next study the problem of broadcasting i
 n networks with arbitrary topology and derive a new dynamic broadcast poli
 cy which can be viewed as “Backpressure on sets”. This yields an effic
 ient solution to the problem when combined with a multi-class in-order pac
 ket scheduling rule.\n\nFinally\, we study the generalized flow problem an
 d derive an online dynamic policy\, called Universal Max-Weight (UMW)\, wh
 ich yields an efficient solution. To the best of our knowledge\, UMW is th
 e first throughput-optimal algorithm of such versatility in this context. 
 Conceptually\, the UMW policy is derived by relaxing the precedence constr
 aints associated with multi-hop routing\, and then solving a min-cost rout
 ing and max-weight scheduling problem on a virtual network of queues. When
  specialized to the unicast setting\, the UMW policy yields a throughput-o
 ptimal cycle-free routing and link scheduling policy. This is in contrast 
 with the Backpressure policy which allows for packet cycling\, resulting i
 n excessive delay. The proposed algorithmic paradigm is surprisingly gener
 al and yields solutions to other related problems\, such as optimal broadc
 asting with point-to-multipoint links. The proof of throughput-optimality 
 of the UMW policy combines techniques from stochastic Lyapunov theory with
  a sample path argument from adversarial queueing theory and may be of ind
 ependent theoretical interest.\n \n
URL:https://www.tcs.tifr.res.in/web/events/745
DTSTART;TZID=Asia/Kolkata:20170120T113000
DTEND;TZID=Asia/Kolkata:20170120T130000
LOCATION:D-405 (D-Block Seminar Room)
END:VEVENT
END:VCALENDAR