logo SBA

ETD

Digital archive of theses discussed at the University of Pisa

 

Thesis etd-05042011-130450


Thesis type
Tesi di dottorato di ricerca
Author
LORI, ALESSANDRO
URN
etd-05042011-130450
Thesis title
Delay-aware Link Scheduling and Routing in Wireless Mesh Networks
Academic discipline
ING-INF/05
Course of study
INGEGNERIA DELL'INFORMAZIONE
Supervisors
tutor Prof. Vaglini, Gigliola
Keywords
  • computer networks
  • real-time traffic
  • resource allocation
Graduation session start date
11/05/2011
Availability
Full
Summary
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