Next generation 3G/4G wireless data networks allow multiple codes (or channels) to be allocated to a single user, where each code can support multiple data rates. Providing fine-grained QoS to users in such networks poses the two dimensional challenge of assigning both power (rate) and codes for every user. This gives rise to a new class of parallel scheduling problems. We abstract general downlink scheduling problems suitable for proposed next generation wireless data systems. This includes a communication-theoretic model for multirate wireless channels. In addition, while conventional focus has been on throughput maximization, we attempt to optimize the maximum response time of jobs, which is more suitable for stream of user requests. We present provable results on the algorithmic complexity of these scheduling problems. In particular, we are able to provide very simple, online algorithms for approximating the optimal maximum response time. This relies on resource augmented competitive analysis. We also perform on experimental study with realistic data of channel conditions and user requests to show that our algorithms are more accurate than our worst case analysis shows, and they provide fine-grained QoS to users effectively.

Parallel scheduling problems in next generation wireless networks / Becchetti, Luca; Diggavi, S.; Leonardi, Stefano; MARCHETTI SPACCAMELA, Alberto; Muthukrishnan, S.; Nandagopal, T.; Vitaletti, Andrea. - STAMPA. - (2002), pp. 238-247. (Intervento presentato al convegno Fourteenth Annual ACM Symposium on Parallel Algorithms and Architectures tenutosi a Winnipeg, MAN.; Canada nel 10-13 August 2002).

Parallel scheduling problems in next generation wireless networks

BECCHETTI, Luca;LEONARDI, Stefano;MARCHETTI SPACCAMELA, Alberto;VITALETTI, Andrea
2002

Abstract

Next generation 3G/4G wireless data networks allow multiple codes (or channels) to be allocated to a single user, where each code can support multiple data rates. Providing fine-grained QoS to users in such networks poses the two dimensional challenge of assigning both power (rate) and codes for every user. This gives rise to a new class of parallel scheduling problems. We abstract general downlink scheduling problems suitable for proposed next generation wireless data systems. This includes a communication-theoretic model for multirate wireless channels. In addition, while conventional focus has been on throughput maximization, we attempt to optimize the maximum response time of jobs, which is more suitable for stream of user requests. We present provable results on the algorithmic complexity of these scheduling problems. In particular, we are able to provide very simple, online algorithms for approximating the optimal maximum response time. This relies on resource augmented competitive analysis. We also perform on experimental study with realistic data of channel conditions and user requests to show that our algorithms are more accurate than our worst case analysis shows, and they provide fine-grained QoS to users effectively.
2002
Fourteenth Annual ACM Symposium on Parallel Algorithms and Architectures
Software; Safety, Risk, Reliability and Quality
04 Pubblicazione in atti di convegno::04b Atto di convegno in volume
Parallel scheduling problems in next generation wireless networks / Becchetti, Luca; Diggavi, S.; Leonardi, Stefano; MARCHETTI SPACCAMELA, Alberto; Muthukrishnan, S.; Nandagopal, T.; Vitaletti, Andrea. - STAMPA. - (2002), pp. 238-247. (Intervento presentato al convegno Fourteenth Annual ACM Symposium on Parallel Algorithms and Architectures tenutosi a Winnipeg, MAN.; Canada nel 10-13 August 2002).
File allegati a questo prodotto
File Dimensione Formato  
VE_2002_11573-950429.pdf

solo gestori archivio

Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 322.48 kB
Formato Adobe PDF
322.48 kB Adobe PDF   Contatta l'autore

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/950429
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 8
  • ???jsp.display-item.citation.isi??? ND
social impact