Fairness and Opportunistic Behavior - Packet Scheduling for Mobile Systems

Gruhl, Stefan

"Fairness" ist eine populäre Zielsetzung, wenn Systeme aus mehreren Akteuren bestehen, die jeweils konkurrierende Interessen verfolgen. "Opportunistisches Verhalten" beschreibt dagegen einen Ansatz, bei dem das Ausnutzen bestimmter Bedingungen gewisse Vorteile verspricht. In dieser Arbeit interessieren wir uns für den Konflikt dieser beiden Ansätze bei Anwendung auf die Paketdatenübertragung in zellulären Funknetzen. Für die zuverlässige Übertragung im Mobilfunk existieren inzwischen zahlreiche Methoden der adaptiven Vorwärtskorrektur abhängig von systembedingten Kanalschwankungen, allerdings bei variabler Effizienz. Wir schlagen anstelle des klassischen Kanalmodells mit zwei Zuständen ein neues, kontinuierliches Kanalmodell vor. Der vorgeschlagene WCFQ-Algorithmus "Wireless Credit-based Fair Queuing" erweitert ein bekanntes Verfahren aus dem Festnetz um eine Kostenfunktion der Kanalmessung. WCFQ bevorzugt Benutzer mit geringer Kostenfunktion und steigert dadurch die Systemeffizienz, wie z.B. den Gesamtdurchsatz. Die konkurrierenden, individuellen Fairnessanforderungen einzelner Benutzer werden dabei durch eine interne Berechnung von "credits" berücksichtigt. Die Fairnessdefinition basiert auf dem bewährten Ansatz von relativer Fairness zwischen jeweils zwei Nutzern. Die analytisch gewonnenen Grenzen bzgl. der Wahrscheinlichkeiten einer Fairnessverletzung mit WCFQ stellen eine hilfreiche Orientierung beim Entwurf bereit. Der Einsatz der Kostenfunktion abstrahiert die zugrunde liegenden Kanalmessungen von konkreter Mobilfunktechnik. Zudem dient die Kostenfunktion als Steuerungsmechanismus für den Netzwerkbetreiber, um das Systemverhalten zwischen den beiden Extremen "Fairness" und "Opportunistisches Verhalten" kontrollierend zu beeinflussen. In szenariobasierten Simulationen untersuchen wir detailliert die Einflüsse von Kanalschwankungen und Mobilität jeweils über ein weites Spektrum an Kostenfunktionen. Die Effizienzsteigerungen sind stark von den Fairnessansprüchen und dem Charakter des Funkkanals abhängig und liegen zwischen 10% und 30%. Ein Vorteil von WCFQ liegt darin, dass je nach Kanal bei fester Kostenfunktion der Effizienzgewinn unterschiedlich ausfällt, die Fairnesseigenschaften allerdings vorhersehbar bleiben. Alle untersuchten Szenarien zeigen, dass ein Mittelweg aus Fairness und opportunistischem Scheduling zu einem erstrebenswerten Gesamtverhalten mit großen Effizienzverbesserungen führen kann. Davon profitieren längerfristig alle Beteiligten, insbesondere da die Systemeigenschaften auch Nutzern mit schlechten Kanalbedingungen ein steuerbares Maß an Fairness zusichern.

"Fairness" is a popular requirement in systems with multiple participants and conflicting interests. "Opportunistic behavior" refers to a different resource allocation scheme to utilize beneficial system properties. In this work we address this conflict for the field of packet data scheduling for mobile systems. The proposed WCFQ-algorithm of "Wireless Credit-based Fair Queuing" extends an xisting algorithm by a cost function of the channel measurement. Thus, WCFQ provides a mechanism to exploit inherent variations in channel conditions and select low cost users in order to increase the system’s overall performance (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 conflicting objectives. This provides system operators with the flexibility 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 system’s 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 fits 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-influences were shown in scenario based simulations. For the range of analyzed cost functions we experienced significant efficiency improvement compared to traditional QoS-scheduling. For tight fairness constraints we find improvements of 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 fixed cost function is the variable amount of efficiency improvement, while the fairness performance remains predictable regardless of the wireless technology. The results are also verified on application level for the specific wireless technology of UMTS-DSCH with a simulation of 36 cells and 250 users. We show that a controlled tradeoff between ultimate fairness and extreme opportunistic behavior leads to desirable system properties for all participants involved.

Zitieren

Zitierform:

Gruhl, Stefan: Fairness and Opportunistic Behavior - Packet Scheduling for Mobile Systems. 2007.

Zugriffsstatistik

Gesamt:
Volltextzugriffe:
Metadatenansicht:
12 Monate:
Volltextzugriffe:
Metadatenansicht:

Grafik öffnen

Export