Fairness and opportunistic behavior [Elektronische Ressource] : packet scheduling for mobile systems / von Stefan Gruhl

Informations

• Publié par: technische_universitat_ilmenau
• Publié le: 01 janvier 2007
• Nombre de lectures: 41
• Langue: Deutsch
• Poids de l'ouvrage: 4 Mo

Extrait

zur Erlangung des akademischen Grades Doktoringenieur (Dr.-Ing.)
vorgelegt der Fakultät für Informatik und Automatisierung
der Technischen Universität Ilmenau
von Dipl.-Inf. Stefan Gruhl
1. Gutachter: Prof. Dr.Ing. habil. Andreas Mitschele-Thiel
2. Gutachter: Prof. Dr. rer. nar. habil. Jochen Seitz
3. Gutachter: Prof. Dr. Ed Knightly
Tag der Einreichung: 21.12.2006
Tag der wissenschaftlichen Aussprache: 12.07.2007
urn:nbn:de:gbv:ilm1-2007000218Fairness and Opportunistic Behavior -
Packet Scheduling for Mobile Systems
Zusammenfassung in Deutscher Sprache
"Fairness" ist eine h˜auflge Zielsetzung fur˜ Systeme mit mehreren Akteuren, die konkur-
rierendeInteressenhaben. "OpportunistischesVerhalten"beschreibtdagegeneinenAnsatz,
bei dem das Ausnutzen bestimmter Bedingungen gewisse Vorteile verspricht.
IndieserArbeitinteressierenwirunsfur˜ denKon iktdieserbeidenAns˜atzebeiAnwen-
dung auf die Paketdatenub˜ ertragung in zellul˜aren Funknetzen. Fur˜ die zuverl˜assige Paket-
datenub˜ ertragung im Mobilfunk existieren inzwischen zahlreiche Methoden der adaptiven
Vorw˜artskorrektur abh˜angig von systembedingten Kanalschwankungen, allerdings bei vari-
abler E–zienz. Wir schlagen anstelle des klassischen Kanalmodells mit zwei Zust˜anden ein
neues,kontinuierlichesKanalmodellvor. DervorgeschlageneWCFQ-Algorithmus"Wireless
Credit-based Fair Queuing" erweitert ein bekanntes Verfahren aus dem Festnetz um eine
Kostenfunktion der Kanalmessung. WCFQ bevorzugt Benutzer mit geringer Kostenfunk-
tion und steigert dadurch die Systeme–zienz, wie z.B. den Gesamtdurchsatz. Die konkur-
rierenden, individuellen Fairnessanforderungen einzelner Benutzer werden dabei durch eine
interne Berechnung von "credits" beruc˜ ksichtigt.
DieFairnessdeflnitionbasiertaufdembew˜ahrtenAnsatzvonrelativerFairnesszwischen
jeweils zwei Nutzern. Die analytisch gewonnenen Grenzen bzgl. der Wahrscheinlichkeiten
einerFairnessverletzungmitWCFQstelleneinehilfreicheOrientierungbeimEntwurfbereit.
Der Einsatz der Kostenfunktion abstrahiert die zugrunde liegenden Kanalmessungen von
konkreter Mobilfunktechnik. Zudem dient die Kostenfunktion als Steuerungsmechanismus
fur˜ den Netzwerkbetreiber, um das Systemverhalten zwischen den beiden Extremen "Fair-
ness" und "Opportunistisches Verhalten" kontrollierend zu beein ussen. WCFQ fugt˜ sich
in die allgemein akzeptierte QoS Architektur aus der Literatur ein und kann in praktischen
Systemen in Bezug auf die Anforderungen an Eingabedaten und der Rechenkomplexit˜at
zum Einsatz kommen.
In szenariobasierten Simulationen untersuchen wir detailliert die Ein usse˜ von Kanal-
schwankungenundMobilit˜atjeweilsbereinweitesSpektrumanKostenfunktionen. Fur˜ die
Szenarien bei strengen Anforderungen an Fairness sind E–zienzsteigerungen von 10-20%
m˜oglich. Bei weniger strengen Fairnessanforderungen sind Steigerungen bis zu 30% und
mehr zu beobachten. Das Potential wird dabei erheblich vom Ausma… der kurzfristigen
Schwankungen in der Kanalqualit˜at bestimmt, die wiederum von einer konkreten Mobil-
funktechnologie und dem Mobilit˜atsverhalten der Nutzer vorgegeben wird. Ein Vorteil von
WCFQ liegt darin, dass je nach Kanal bei fester Kostenfunktion der E–zienzgewinn unter-
schiedlich ausf˜allt, die Fairnesseigenschaften allerdings vorhersehbar bleiben. Diese Ergeb-
nissewurdenzus˜atzlichfur˜ speziflscheUMTS-DSCHKanaleigenschaftenineinemNetzwerk
mit 36 simulierten Funkzellen und 250 aktiven Nutzern auf Applikationsebene veriflziert.
Alle untersuchten Szenarien zeigen, dass ein Mittelweg aus Fairness und opportunisti-
schemSchedulingzueinemerstrebenswertenGesamtverhaltenmitgro…enE–zienzverbesser-
ungen fuhren˜ kann. Davon profltieren l˜angerfristig alle Beteiligten, insbesondere da die
Systemeigenschaften auch Nutzern mit schlechten Kanalbedingungen ein steuerbares Ma…
an Fairness zusichern.Fairness and Opportunistic Behavior -
Packet Scheduling for Mobile Systems
Summary in English Language
"Fairness" is a popular requirement in systems with multiple participants and con ict-
ing interests. "Opportunistic behavior" on the other hand refers to a difierent resource
allocation scheme to utilize beneflcial system properties.
In this work we address this con ict for the fleld of packet data scheduling for mobile
systems. Adaptive forward error correction provides mechanisms for reliable data trans-
mission regardless of system related channel variations, yet with variable e–ciency. This
motivates new, opportunistic scheduling strategies to delay a feasible transmission of a user
in favor of a competing user with a better channel and hence higher e–ciency.
We propose a new continuous channel model instead of the legacy two state channel
model to describe the channel conditions. The proposed WCFQ-algorithm of "Wireless
Credit-based Fair Queuing" extends an existing algorithm by a cost function of the channel
measurement. Thus, WCFQprovidesamechanismtoexploitinherentvariationsinc
conditionsandselectlowcostusersinordertoincreasethesystemsoverallperformance(e.g.,
total throughput). However, opportunistic selection of the best user must be balanced with
fairness considerations. In WCFQ, we use a credit abstraction and a general cost function
to address these con icting objectives. This provides system operators with the exibility
to achieve a range of performance behaviors between perfect fairness of temporal access
independent of channel conditions, and purely opportunistic scheduling of the best user
without consideration of fairness. To quantify the systems fairness characteristics within
this range, we develop an analytical model for short- and long-term fairness that provides
a statistical fairness bound based on the cost function and the statistical properties of the
channel. WCFQ flts into the commonly accepted Quality-of-Service architecture and is
feasible for implementation with regard to computational complexity and signaling.
The expected fairness properties for our extensive models of channel-variations and
mobility-in uences were shown in scenario based simulations. For the range of analyzed
cost functions we experienced signiflcant e–ciency improvement compared to traditional
QoS-scheduling. For tightfairness constraintsweflnd improvementsof 10-20 %, for relaxed
fairness constraints up to 30% and more. The potential for improvement depends on the
short-term channel variations, that are dictated by actual wireless technology and user
mobility. A major advantage of WCFQ for a flxed cost function is the variable amount
of e–ciency improvement, while the fairness performance remains predictable regardless of
the wireless technology. The results are also verifled on application level for the speciflc
wireless technology of UMTS-DSCH with a simulation of 36 cells and 250 users.
Weshowthat a controlled tradeofibetweenultimate fairnessand extreme opportunistic
behavior leads to desirable system properties for all participants involved.Acknowledgements
It is my pleasure to express my deepest gratitude and appreciation to my advisor, Prof.
Andreas Mitschele-Thiel, for his excellent guidance, advice, and encouragement during the
course of this investigation. His balanced interest in the fleld of computer science and in
the fleld of mobile communications helped signiflcantly in the deflnition and presentation
of this report.
I am indebted to Prof. Edward Knightly of the Department of Electrical Engineering,
Rice University, Houston, Texas. I most happily followed his invitation to join his excellent
research team for the spring semester in 2001. His widely acknowledged expertise in QoS
and his previous research on wireless applications made him my flrst choice. He proved to
be the perfect host for my studies with his legendary open-door policy. It am thankful for
the collaborate work with Dr. Yonghe Liu. I owe them deep insights from our publication
in the IEEE transactions on wireless communications.
This dissertation has been considerably improved because of comments from and dis-
cussionwithProf. JochenSeitz. Hisdetailedstudyoftheworkwasverymuchappreciated.
I thank Prof. Ulrich Herzog. Not only he has established my contact to industry, Bell
Labs Lucent Technologies, he has always been a role model for a clear and strong research
focus of this work.
As a member of the Lucent Technologies Bell-Labs research facilities I enjoyed the
company of most dedicated researchers. I appreciated the open working environment and
the inspiring atmosphere from my colleagues from various flelds in telecommunications.
Workingininterdisciplinaryfleldswasamostrewardingexperienceinmyacademiclife. My
particular thanks go to Dr. Michael Soellner, who supported me from the very beginning,
when I did my master thesis in his department. He envisioned the importance of wireless
QoS and greatly supported me in technical, as well as in personal issues and created a
space for sincere research. I particularly appreciated the flnancial support from Lucent
Technologies to fund a sabbatical during a semester at a US university of my choice. I
thank all my colleagues at Lucent Technologies. I particular thank Dr. Jens Mueckenheim
for his enlightening insights into physical layer details of CDMA. I thank Michael Link
and Jurgen˜ Kettschau, who became the main contributors of our joint UMTS-prototype
project. For mathematical