2025-11-16T04:34:12.484648

Chronicles of Jockeying in Queuing Systems

Kiggundu, Han, Krummacker et al.
Emerging trends in communication systems, such as network softwarization, functional disaggregation, and multi-access edge computing (MEC), are reshaping both the infrastructural landscape and the application ecosystem. These transformations introduce new challenges for packet transmission, task offloading, and resource allocation under stringent service-level requirements. A key factor in this context is queue impatience, where waiting entities alter their behavior in response to delay. While balking and reneging have been widely studied, this survey focuses on the less explored but operationally significant phenomenon of jockeying, i.e. the switching of jobs or users between queues. Although a substantial body of literature models jockeying behavior, the diversity of approaches raises questions about their practical applicability in dynamic, distributed environments such as 5G and Beyond. This chronicle reviews and classifies these studies with respect to their methodologies, modeling assumptions, and use cases, with particular emphasis on communication systems and MEC scenarios. We argue that forthcoming architectural transformations in next-generation networks will render many existing jockeying models inapplicable. By highlighting emerging paradigms such as MEC, network slicing, and network function virtualization, we identify open challenges, including state dissemination, migration cost, and stability, that undermine classical assumptions. We further outline design principles and research directions, emphasizing hybrid architectures and decentralized decision making as foundations for re-conceptualizing impatience in next-generation communication systems.
academic

Chroniken des Warteschlangenwechsels in Warteschlangensystemen

Grundinformationen

  • Paper-ID: 2402.11061
  • Titel: Chronicles of Jockeying in Queuing Systems
  • Autoren: Anthony Kiggundu, Bin Han, Dennis Krummacker, Hans D. Schotten
  • Klassifizierung: cs.NI (Netzwerk- und Internetarchitektur)
  • Veröffentlichungszeit/Konferenz: ACM Computing Surveys (erwartet Januar 2023)
  • Paper-Link: https://arxiv.org/abs/2402.11061

Zusammenfassung

Aufstrebende Trends in Kommunikationssystemen wie Netzwerksoftwarisierung, Funktionsdekomposition und Multi-Access Edge Computing (MEC) gestalten die Infrastrukturlandschaft und das Anwendungsökosystem neu. Diese Transformationen stellen neue Herausforderungen für die Paketübertragung, Task-Offloading und Ressourcenallokation unter strikten Service-Level-Anforderungen dar. Warteschlangen-Ungeduld ist ein Schlüsselfaktor, da wartende Entitäten ihr Verhalten basierend auf Verzögerungen ändern. Obwohl Balking und Reneging bereits umfassend untersucht wurden, konzentriert sich diese Übersicht auf die Erforschung des weniger untersuchten, aber operativ wichtigen Phänomens – Warteschlangenwechsel (Jockeying), d. h. der Wechsel von Jobs oder Benutzern zwischen Warteschlangen. Trotz umfangreicher Literatur zur Modellierung von Warteschlangenwechselverhalten werfen die methodischen Unterschiede Fragen zur praktischen Anwendbarkeit in 5G und zukünftigen dynamischen verteilten Umgebungen auf. Dieser Artikel überprüft und klassifiziert die Methoden, Modellierungsannahmen und Anwendungsfälle dieser Forschungen und betont besonders Kommunikationssysteme und MEC-Szenarien. Wir argumentieren, dass die Architekturveränderungen von Netzen der nächsten Generation viele bestehende Warteschlangenwechselmodelle obsolet machen werden, und identifizieren offene Herausforderungen wie Zustandsausbreitung, Migrationkosten und Stabilität durch Hervorhebung aufstrebender Paradigmen wie MEC, Netzwerk-Slicing und Netzwerkfunktionsvirtualisierung.

Forschungshintergrund und Motivation

Problemdefinition

Die Kernfrage dieser Forschung ist: Wie können sich traditionelle Warteschlangenwechsel-Modelle (Jockeying) an die Architekturveränderungen in Kommunikationsnetzen der nächsten Generation (5G/6G) anpassen, und wie sollten Modellierungsmethoden für Warteschlangen-Ungeduld neu gestaltet werden?

Bedeutung des Problems

  1. Zunahme verzögerungsempfindlicher Anwendungen: Fernsteuerung, Industrieautomation, autonomes Fahren und immersive XR-Dienste stellen extreme Anforderungen an Latenz und Zuverlässigkeit
  2. Architekturveränderungen: Komplexität durch Netzwerksoftwarisierung, Funktionsdekomposition und MEC
  3. Ressourcenoptimierungsbedarf: Echtzeitressourcenallokation und Task-Offloading unter strikten SLA-Einschränkungen

Einschränkungen bestehender Methoden

  1. Homogenitätsannahmen: Die meisten Modelle gehen von homogenen Warteschlangensystemen aus und ignorieren reale Heterogenität
  2. Vollständige Beobachtbarkeit: Annahme, dass alle Warteschlangenzustandsinformationen zeitnah und genau verfügbar sind
  3. Null-Migrationskosten: Ignorieren von Zustandsübergangs- und Rekonfigurationsaufwand
  4. Statische Umgebung: Keine Berücksichtigung von Mobilität, dynamischer Skalierung und Verkehrsspitzen

Forschungsmotivation

Mit der weit verbreiteten Bereitstellung von Netzwerk-Slicing, SDN/NFV und MEC in 5G/6G-Netzen werden die grundlegenden Annahmen der klassischen Warteschlangen-Theorie durchbrochen, was eine dringende Überprüfung und Neuentwicklung von Warteschlangenwechsel-Modellen erfordert, die sich an neue Architekturen anpassen.

Kernbeiträge

  1. Umfassende Klassifizierungsübersicht: Erste systematische Überprüfung und Klassifizierung von Warteschlangenwechsel-Modellierungstechniken mit der bislang umfassendsten Literaturübersicht in diesem Bereich
  2. Lückenanalyse: Quantitative Bewertung der praktischen Anwendbarkeitsgrenzen klassischer Modelle unter modernen 5G/6G-Architektur-Einschränkungen
  3. Architektur-Integrationsanalyse: Tiefgehende Analyse, wie MEC, SDN/NFV und Netzwerk-Slicing die Warteschlangenwechsel-Modellierung neu definieren und die Auswirkungen von Heterogenität, Signalisierungsverzögerung und domänenübergreifenden Vertrauenseinschränkungen offenbaren
  4. Designprinzipien und zukünftige Richtungen: Basierend auf Klassifizierung und Lückenanalyse werden Designprinzipien für robuste, kommunikationsbewusste Warteschlangenwechsel-Modelle in verteilten Umgebungen der nächsten Generation vorgeschlagen

Methodische Details

Aufgabendefinition

Dieser Artikel ist eine Übersichtsarbeit mit folgenden Hauptaufgaben:

  • Eingabe: Bestehende Warteschlangenwechsel-Literatur, 5G/6G-Architekturmerkmale, MEC-Bereitstellungseinschränkungen
  • Ausgabe: Systematische Klassifizierung, Anwendbarkeitsbewertung, Designprinzipien, zukünftige Forschungsrichtungen
  • Einschränkungen: Berücksichtigung technischer und wirtschaftlicher Einschränkungen bei der praktischen Netzwerkbereitstellung

Klassifizierungsrahmen

1. Stochastische Modellierungsmethoden

  • Markov-Entscheidungsprozesse (MDP): Geeignet für sequenzielle Entscheidungen, aber anfällig für Zustandsraum-Explosion
  • Spieltheoretische Ansätze: Basierend auf Nash-Gleichgewicht, erfordern aber vollständige Informationen und rationale Teilnehmerannahmen
  • Fluidtheorie-Modelle: Durchschnittswertbildung diskreter Ereignisse als kontinuierliche Flüsse, geeignet für großflächige Systemanalyse

2. Analytische Modellierungsmethoden

  • Matrixgeometrische Methode: Bietet exakte Lösungen für quasi-Geburts-Todes-Prozesse, erfordert aber strukturierte, stationäre Markov-Systeme

3. Verhaltensmodellierungsmethoden

  • Informationswert-Modelle: Betrachten Warteschlangenwechsel als lokales Entscheidungsproblem
  • Künstliche neuronale Netze: Erfassen hochdimensionale nichtlineare Beziehungen, aber mit „Black-Box"-Problemen

Wechsel-Triggermechanismen

Schwellenwertbasierter Wechsel

Warteschlangenlänge oder Wartezeit-Schwellenwerte: Wechsel wird ausgelöst, wenn die Warteschlangenlängendifferenz einen vordefinierten Schwellenwert überschreitet

if |Q₁ - Q₂| > threshold:
    switch_to_shorter_queue()

Basierend auf Kosten und erwarteter Verzögerung

In heterogenen Systemen, kombiniert mit Warteschlangenlängen-Schwellenwert und erwarteter Wartezeit:

switch_condition = (expected_waiting_time < current_position_time) 
                  AND (migration_cost < benefit)

Technische Innovationspunkte

  1. Hybrid-Architektur-Design: Trennung von Zustandsausbreitung und Entscheidungskontrolle
    • Zentralisierte Ausbreitung: Gewährleistung der Sichtbarkeit des Warteschlangenzustands im gesamten System
    • Verteilte Entscheidungsfindung: Autonome lokale Entscheidungen unter Verzögerungseinschränkungen
  2. Informationswert-Methode: Hochwertige Updates werden nur ausgelöst, wenn der erwartete Nutzengewinn die Kommunikationskosten übersteigt
  3. Stabilitätssicherung: Vermeidung von Oszillationen durch Hysterese-Schwellenwerte, Kühl-Timer und explizite Berücksichtigung von Migrationskosten

Experimentelle Einrichtung

Literaturanalysemethode

  • Systematische Recherche: Umfasst verwandte Bereiche wie Warteschlangen-Theorie, Kommunikationsnetze und Edge Computing
  • Klassifizierungskriterien: Klassifizierung nach Modellierungsmethode, Warteschlangen-Typ, Wechsel-Schwellenwert und Leistungskennzahlen
  • Anwendbarkeitsbewertung: Bewertung der Einschränkungen bestehender Modelle basierend auf 5G/6G-Architekturmerkmalen

Bewertungsdimensionen

  1. Realitätsnähe der Modellierungsannahmen: Homogenität, Informationsverfügbarkeit, Migrationskosten usw.
  2. Skalierbarkeit: Zustandsraum-Komplexität, Rechenfeasibilität
  3. Robustheit: Anpassungsfähigkeit an unvollständige Informationen und dynamische Umgebungen

Experimentelle Ergebnisse

Hauptergebnisse

1. Versagen klassischer Annahmen

  • Homogenitätsannahme: Netzwerk-Slicing führt zu Multi-Vendor- und Multi-Performance-Konfigurationen, wodurch einfache Warteschlangenlängen-Vergleiche unzureichend werden
  • Null-Migrationskosten: Zustandsmigration erzeugt Übertragungszeiten proportional zur Zustandsgröße und Netzwerkpfad-Charakteristiken
  • Vollständige Informationen: Zeitnahe authentifizierte Slice-Deskriptor-Ausbreitung verbraucht Kontrollplan-Ressourcen

2. Stabilitäts- und Sicherheitsrisiken

  • Ping-Pong-Effekt: Niedrige Warteschlangenlängen-Schwellenwerte können Oszillationsverhalten auslösen
  • Sicherheitsbedrohungen: Nicht authentifizierte Zustandsberichte können böswillig ausgenutzt werden

3. Verbesserungspotenzial der Leistung

Numerische Studien zeigen, dass adaptive Arbeitslast-Umverteilung die durchschnittliche Verweilzeit um 20-30% reduzieren kann und die Task-Fertigstellung für verzögerungsempfindliche MEC-Anwendungen beschleunigt.

Modellierungslimitierungen-Analyse

Stochastische Modell-Limitierungen

  • Teilweise, verzögerte oder zensierte Telemetrie erzeugt verzerrte Schätzungen mit hoher Varianz
  • Dynamische Systeme (Mobilität, automatische Skalierung) führen zu schnellem Konzeptdrift
  • Slice-Heterogenität macht gepoolte Modelle ungültig

Nash-Gleichgewicht-Modell-Limitierungen

  • Annahme expliziter Nutzenfunktionen und ausreichenden Wissens der Teilnehmer
  • In der Praxis sind Teilnehmer begrenzt rational und verwenden Lern-Heuristiken
  • Durchsetzungsprobleme über Verwaltungsdomänen hinweg

Fluidmodell-Limitierungen

  • Durchschnittswertbildung diskreter Ereignisse kann Tail-Events und diskrete Trigger maskieren
  • Annahme glatter, langsam veränderlicher Eingaben, aber Netzwerkfunktions-Skalierung erzeugt Diskontinuitäten

Verwandte Arbeiten

Grundlagen der Warteschlangen-Theorie

Beginnend mit Haights Pionierarbeit (1958) hat sich die Warteschlangenwechsel-Forschung von einfachen M/M/2-Systemen zu komplexen heterogenen Umgebungen entwickelt.

Moderne Netzwerkanwendungen

  • Edge Computing: Forschung zu Ungeduld-Warteschlangen in MEC-Umgebungen durch Han et al.
  • Netzwerk-Slicing: Slice-basierte Ressourcenallokation und SLA-Management in 5G-Netzen
  • SDN/NFV: Dynamische Lastverteilung in softwaredefinierten Netzen

Beziehung zu diesem Artikel

Dieser Artikel integriert klassische Warteschlangen-Theorie und moderne Netzwerk-Architektur und bietet eine interdisziplinäre Perspektive.

Schlussfolgerungen und Diskussion

Hauptschlussfolgerungen

  1. Unzulänglichkeit klassischer Modelle: Traditionelle Warteschlangenwechsel-Modelle sehen sich in 5G/6G-Umgebungen mit grundlegenden Herausforderungen konfrontiert
  2. Notwendigkeit von Hybrid-Architekturen: Hybrid-Design mit Trennung von Zustandsausbreitung und Entscheidungskontrolle erforderlich
  3. Informationswert-orientiert: Nutzenbasierte Informationsaktualisierungsstrategien sind effizienter als periodisches Broadcasting
  4. Stabilität ist entscheidend: Explizite Berücksichtigung von Migrationskosten und Anti-Oszillations-Mechanismen erforderlich

Limitierungen

  1. Theorie-Praxis-Lücke: Die meisten Analysen basieren auf theoretischen Modellen, es fehlt die Validierung durch großflächige praktische Bereitstellung
  2. Unzureichende Sicherheitsüberlegungen: Schutzmechanismen gegen böswilliges Verhalten und Angriffe erfordern tiefere Forschung
  3. Domänenübergreifende Koordination: Strategiekoordination und Vertrauensmechanismen in Multi-Vendor-Umgebungen müssen noch verbessert werden

Zukünftige Richtungen

  1. Empirische Validierung: Kontrollierte Experimente auf MEC-Testplattformen
  2. Großflächige Simulation: Leistungsquantifizierung basierend auf echten Verkehrsspuren
  3. Theoretische Grenzen: Analyse theoretischer Grenzen minimaler Aktualisierungsfrequenzen
  4. Sicherheitsmechanismen: Robuste Telemetrie-Authentifizierung gegen böswillige Berichte

Tiefgehende Bewertung

Stärken

  1. Umfassendheit: Erste systematische Übersicht des Warteschlangenwechsel-Bereichs, von klassischer Theorie bis zu modernen Anwendungen
  2. Zukunftsorientierung: Genaue Identifizierung der Herausforderungen, die 5G/6G-Architekturveränderungen für traditionelle Modelle darstellen
  3. Praktischer Nutzen: Vorgeschlagene Hybrid-Architektur und Designprinzipien haben praktischen Bereitstellungswert
  4. Interdisziplinarität: Erfolgreiche Verbindung von Warteschlangen-Theorie, Kommunikationsnetzen und Edge Computing

Schwächen

  1. Mangel an experimenteller Validierung: Als Übersichtsarbeit fehlen originale experimentelle Validierungen
  2. Begrenzte quantitative Analyse: Quantitative Analysen von Leistungsverbesserungen beruhen hauptsächlich auf Zitaten anderer Forschungen
  3. Unzureichende Implementierungsdetails: Vorgeschlagene Designprinzipien benötigen konkretere Implementierungsanleitungen

Einflussfähigkeit

  1. Akademischer Wert: Bietet wichtige theoretische Grundlagen und Entwicklungsrichtungen für Warteschlangenwechsel-Forschung
  2. Praktischer Wert: Bietet Orientierung für 5G/6G-Netzwerk-Design und MEC-Bereitstellung
  3. Inspirationswert: Bietet gutes Beispiel für interdisziplinäre Forschung

Anwendungsszenarien

  1. Netzwerk-Slicing-Umgebungen: Szenarien mit Multi-Tenant- und heterogenen Serviceanforderungen
  2. Edge Computing: Task-Offloading und Ressourcenallokation für verzögerungsempfindliche Anwendungen
  3. Echtzeitsysteme: Kritische Anwendungen wie Industrieautomation und autonomes Fahren

Literaturverzeichnis

Der Artikel zitiert 172 Referenzen, die klassische Warteschlangen-Theorie-Literatur, Forschung zu modernen Netzwerk-Architekturen und Edge-Computing-Anwendungen umfassen und Lesern eine umfassende Literaturgrundlage bieten.

Gesamtbewertung: Dies ist eine hochwertige Übersichtsarbeit, die systematisch die Herausforderungen analysiert, denen sich Warteschlangenwechsel in modernen Netzwerkumgebungen gegenübersieht, und wertvolle Lösungsrichtungen vorschlägt. Der Hauptbeitrag des Artikels liegt in der Identifizierung der Limitierungen traditioneller Modelle und der Vorschlag von Designprinzipien, die sich an neue Architekturen anpassen, was sowohl für die theoretische Entwicklung als auch für praktische Anwendungen in diesem Bereich von großer Bedeutung ist.