ETD system

Electronic theses and dissertations repository


Tesi etd-05042011-130450

Thesis type
Tesi di dottorato di ricerca
Delay-aware Link Scheduling and Routing in Wireless Mesh Networks
Settore scientifico disciplinare
Corso di studi
tutor Prof. Vaglini, Gigliola
Parole chiave
  • resource allocation
  • real-time traffic
  • computer networks
Data inizio appello
Riassunto analitico
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.