logo SBA

ETD

Archivio digitale delle tesi discusse presso l’Università di Pisa

Tesi etd-05042011-130450


Tipo di tesi
Tesi di dottorato di ricerca
Autore
LORI, ALESSANDRO
URN
etd-05042011-130450
Titolo
Delay-aware Link Scheduling and Routing in Wireless Mesh Networks
Settore scientifico disciplinare
ING-INF/05
Corso di studi
INGEGNERIA DELL'INFORMAZIONE
Relatori
tutor Prof. Vaglini, Gigliola
Parole chiave
  • computer networks
  • real-time traffic
  • resource allocation
Data inizio appello
11/05/2011
Consultabilità
Completa
Riassunto
Resource allocation is a critical task in computer networks because of their capital-intensive nature. In this thesis we apply operations research tools and technologies to model, solve and analyze resource allocation problems in computer networks with real-time traffic.

We first study Wireless Mesh Networks, addressing the problem of link scheduling with end-to-end delay constraints. Exploiting results obtained with the Network Calculus framework, we formulate the problem as an integer non-linear optimization problem. We show that the feasibility of a link schedule does depend on the aggregation framework. We also address the problem of jointly solving the routing and link scheduling problem optimally, taking into account end-to-end delay guarantees. We provide guidelines and heuristics.

As a second contribution, we propose a time division approach in CSMA MAC protocols in the context of 802.11 WLANs. By grouping wireless clients and scheduling time slots to these groups, not only the delay of packet transmission can be decreased, but also the goodput of multiple WLANs can be largely increased.

Finally, we address a resource allocation problem in wired networks for guaranteed-delay traffic engineering. We formulate and solve the problem under different latency models. Global optimization let feasible schedules to be computed with instances where local resource allocation schemes would fail. We show that this is the case even with a case-study network, and at surprisingly low average loads.
File