A Caltech Library Service

Dual scheduling algorithm in a generalized switch: asymptotic optimality and throughput optimality

Chen, Lijun and Low, Steven H. and Doyle, John C. (2007) Dual scheduling algorithm in a generalized switch: asymptotic optimality and throughput optimality. In: High-performance Packet Switching Architectures. Springer , London, pp. 147-168. ISBN 978-1-84628-273-7.

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


In this article, we consider the dual scheduling algorithm for a generalized switch. For a saturated system, we prove the asymptotic optimality of the dual scheduling algorithm and thus establish its fairness properties. For a system with exogenous arrivals, we propose a modified dual scheduling algorithm, which is throughput-optimal while providing some weighted fairness among the users at the level of flows. 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 stemming out of this article includes scheduling with Quality of Service guarantees with the dual scheduler, and its application and implementation in various versions of the generalized switch model.

Item Type:Book Section
Related URLs:
URLURL TypeDescription
Low, Steven H.0000-0001-6476-3048
Doyle, John C.0000-0002-1828-2486
Additional Information:© 2007 Springer-Verlag London Limited. This work is part of the Caltech FAST Project supported by NSF, Caltech Lee Center for Advanced Networking, ARO, AFOSR, DARPA, and Cisco.
Funding AgencyGrant Number
Caltech Lee Center for Advanced NetworkingUNSPECIFIED
Army Research Office (ARO)UNSPECIFIED
Air Force Office of Scientific Research (AFOSR)UNSPECIFIED
Defense Advanced Research Projects Agency (DARPA)UNSPECIFIED
Record Number:CaltechAUTHORS:20170810-103710158
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:80086
Deposited By: Zhaojian Wang
Deposited On:14 Aug 2017 19:41
Last Modified:15 Nov 2021 17:52

Repository Staff Only: item control page