2nd International ICST Workshop on Resource Allocation in Wireless Networks

Research Article

On Asymptotic Optimality of Dual Scheduling Algorithm In A Generalized Switch

  • @INPROCEEDINGS{10.1109/WIOPT.2006.1666500,
        author={Lijun Chen and Steven H Low and John C. Doyle},
        title={On Asymptotic Optimality of Dual Scheduling Algorithm In A Generalized Switch},
        proceedings={2nd International ICST Workshop on Resource Allocation in Wireless Networks},
        publisher={IEEE},
        proceedings_a={RAWNET},
        year={2006},
        month={8},
        keywords={},
        doi={10.1109/WIOPT.2006.1666500}
    }
    
  • Lijun Chen
    Steven H Low
    John C. Doyle
    Year: 2006
    On Asymptotic Optimality of Dual Scheduling Algorithm In A Generalized Switch
    RAWNET
    IEEE
    DOI: 10.1109/WIOPT.2006.1666500
Lijun Chen1,2, Steven H Low1,2, John C. Doyle1,2
  • 1: Engineering & Applied Science Division, California Institute of Technology
  • 2: Pasadena, CA 91125, USA

Abstract

Generalized switch is a model of a queueing system where parallel servers are interdependent and have time-varying service capabilities. This paper considers the dual scheduling algorithm that uses rate control and queue-length based scheduling to allocate resources for a generalized switch. We consider a saturated system in which each user has in£nite amount of data to be served. We prove the asymptotic optimality of the dual scheduling algorithm for such a system, which says that the vector of average service rates of the scheduling algorithm maximizes some aggregate concave utility functions. As the fairness objectives can be achieved by appropriately choosing utility functions, the asymptotic optimality establishes the fairness properties of the dual scheduling algorithm. The dual scheduling algorithm motivates a new architecture for scheduling, in which an additional queue is introduced to interface the user data queue and the time-varying server and to modulate the scheduling process, so as to achieve different performance objectives. Further research would include scheduling with Quality of Service guarantees with the dual scheduler, and its application and implementation in various versions of the generalized switch model.