Delay Efficient Scheduling via Redundant Constraints in Multihop Networks

Abstract : We consider the problem of delay-efficient scheduling in general multihop networks. While the class of max-weight type algorithms are known to be throughput optimal for this problem, they typically incur undesired delay performance. In this paper, we propose the Delay-Efficient SCheduling algorithm (DESC). DESC is built upon the idea of accelerating queues (AQ), which are virtual queues that quickly propagate the traffic arrival information along the routing paths. DESC is motivated by the use of redundant constraints to accelerate convergence in the classic optimization context. We show that DESC is throughputoptimal. The delay bound of DESC can be better than previous bounds of the max-weight type algorithms which did not use such traffic information. We also show that under DESC, the service rates allocated to the flows converge quickly to their target values and the average total “network service lag” is small. In particular, when there are O(1) flows and the rate vector is of (-) (1) distance away from the boundary of the capacity region, the average total “service lag” only grows linearly in the network size.
Type de document :
Communication dans un congrès
WiOpt'10: Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks, May 2010, Avignon, France. pp.120-129, 2010
Liste complète des métadonnées

Littérature citée [20 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00501496
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : lundi 12 juillet 2010 - 11:17:59
Dernière modification le : dimanche 17 décembre 2017 - 07:04:03
Document(s) archivé(s) le : jeudi 14 octobre 2010 - 15:31:48

Fichier

p120-huang.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00501496, version 1

Collections

Citation

Longbo Huang, Michael J. Neely. Delay Efficient Scheduling via Redundant Constraints in Multihop Networks. WiOpt'10: Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks, May 2010, Avignon, France. pp.120-129, 2010. 〈inria-00501496〉

Partager

Métriques

Consultations de la notice

56

Téléchargements de fichiers

79