Chronicles of Jockeying in Queuing Systems

Basic Information

• Paper ID: 2402.11061
• Title: Chronicles of Jockeying in Queuing Systems
• Authors: Anthony Kiggundu, Bin Han, Dennis Krummacker, Hans D. Schotten
• Classification: cs.NI (Networking and Internet Architecture)
• Publication Venue/Date: ACM Computing Surveys (Expected January 2023)
• Paper Link: https://arxiv.org/abs/2402.11061

Abstract

Emerging trends in communication systems, such as network softwarization, functional decomposition, and multi-access edge computing (MEC), are reshaping the infrastructure landscape and application ecosystem. These transformations introduce new challenges for packet transmission, task offloading, and resource allocation under stringent service level requirements. Queue impatience is a critical factor, as waiting entities modify their behavior based on delays. While balking and reneging have been extensively studied, this survey focuses on exploring a less-studied but operationally important phenomenon—queue jockeying, wherein jobs or users switch between queues. Despite substantial literature modeling queue switching behavior, the diversity of approaches raises questions about their practical applicability in 5G and future dynamic distributed environments. This paper reviews and classifies the methodologies, modeling assumptions, and use cases of these studies, with particular emphasis on communication systems and MEC scenarios. We argue that architectural transformations in next-generation networks will render many existing queue jockeying models obsolete, and by highlighting emerging paradigms such as MEC, network slicing, and network function virtualization, we identify open challenges including state propagation, migration costs, and stability.

Research Background and Motivation

Problem Definition

The core problem this research addresses is: How can traditional queue jockeying models adapt to architectural transformations in next-generation communication networks (5G/6G), and how should modeling approaches for queue impatience behavior be redesigned?

Problem Significance

1. Proliferation of Latency-Sensitive Applications: Remote control, industrial automation, autonomous driving, and immersive XR services impose extreme requirements on latency and reliability
2. Architectural Transformation: Complexity introduced by network softwarization, functional decomposition, and MEC
3. Resource Optimization Requirements: Real-time resource allocation and task offloading under strict SLA constraints

Limitations of Existing Approaches

1. Homogeneity Assumptions: Most models assume homogeneous queue systems, overlooking real-world heterogeneity
2. Complete Observability: Assumes all queue state information is available promptly and accurately
3. Zero Migration Costs: Ignores actual overhead from state transfers and reconfiguration
4. Static Environments: Fails to account for mobility, dynamic scaling, and traffic bursts

Research Motivation

With widespread deployment of network slicing, SDN/NFV, and MEC technologies in 5G/6G networks, fundamental assumptions of classical queuing theory are violated, necessitating urgent reconsideration and redesign of queue jockeying models adapted to new architectures.

Core Contributions

1. Comprehensive Taxonomic Survey: First systematic review and classification of queue jockeying modeling techniques, providing the most comprehensive literature survey to date in this field
2. Gap Analysis: Quantitatively evaluates practical limitations of classical models under modern 5G/6G architectural constraints
3. Architecture Integration Analysis: Deeply analyzes how MEC, SDN/NFV, and network slicing redefine queue jockeying modeling, revealing impacts of heterogeneity, signaling delays, and cross-domain trust constraints
4. Design Principles and Future Directions: Based on classification and gap analysis, proposes design principles for robust, communication-aware queue jockeying models applicable to next-generation distributed environments

Methodology Details

Task Definition

This paper is a survey-type contribution with primary tasks:

• Input: Existing queue jockeying literature, 5G/6G architectural characteristics, MEC deployment constraints
• Output: Systematic classification, applicability assessment, design principles, future research directions
• Constraints: Must consider technical and economic constraints of actual network deployment

Classification Framework

1. Stochastic Modeling Approaches

• Markov Decision Processes (MDP): Suitable for sequential decision-making, but suffers from state space explosion
• Game-Theoretic Methods: Based on Nash equilibrium, but requires complete information and rational participant assumptions
• Fluid-Theoretic Models: Averages discrete events into continuous flows, suitable for large-scale system analysis

2. Analytical Modeling Approaches

• Matrix-Geometric Methods: Provides exact solutions for quasi-birth-death processes, but requires structured, stationary Markovian systems

3. Behavioral Modeling Approaches

• Information Value Models: Treats queue switching as local decision problems
• Artificial Neural Networks: Captures high-dimensional nonlinear relationships, but suffers from "black box" issues

Switching Trigger Mechanisms

Threshold-Based Switching

Queue length or waiting time thresholds: Triggers switching when queue length differences exceed preset thresholds

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

Cost and Expected Delay-Based Switching

In heterogeneous systems, combines queue length thresholds with expected waiting time:

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

Technical Innovations

1. Hybrid Architecture Design: Separates state propagation from decision control
   • Centralized Propagation: Ensures system-wide queue state visibility
   • Distributed Decision-Making: Enables local autonomous decisions under latency constraints
2. Information Value Approach: Triggers high-fidelity updates only when expected utility gains exceed communication costs
3. Stability Assurance: Prevents oscillation through hysteresis thresholds, cooldown timers, and explicit migration cost considerations

Experimental Setup

Literature Analysis Methodology

• Systematic Retrieval: Covers related domains including queuing theory, communication networks, and edge computing
• Classification Criteria: Classifies by modeling approach, queue type, switching thresholds, and performance metrics
• Applicability Assessment: Evaluates limitations of existing models based on 5G/6G architectural characteristics

Evaluation Dimensions

1. Realism of Modeling Assumptions: Homogeneity, information availability, migration costs
2. Scalability: State space complexity, computational feasibility
3. Robustness: Adaptability to incomplete information and dynamic environments

Experimental Results

Key Findings

1. Failure of Classical Assumptions

• Homogeneity Assumption: Network slicing introduces multi-vendor, multi-performance configurations, making simple queue length comparisons insufficient
• Zero Migration Costs: Stateful migrations incur transmission times proportional to state size and network path characteristics
• Complete Information: Timely authenticated slice descriptor propagation consumes control plane resources

2. Stability and Security Risks

• Ping-Pong Effect: Low queue length thresholds may trigger oscillatory behavior
• Security Threats: Unauthenticated state reports can be exploited maliciously

3. Performance Improvement Potential

Numerical studies demonstrate that adaptive workload redistribution can reduce average sojourn time by 20-30%, accelerating task completion for latency-sensitive MEC applications.

Model Limitation Analysis

Stochastic Model Limitations

• Partial, delayed, or censored telemetry produces biased, high-variance estimates
• Dynamic systems (mobility, auto-scaling) cause rapid concept drift
• Slice heterogeneity invalidates pooled models

Nash Equilibrium Model Limitations

• Assumes explicit utility functions and sufficient participant knowledge
• In practice, participants exhibit bounded rationality and employ learning heuristics
• Enforceability issues across administrative domains

Fluid Model Limitations

• Averaging discrete events may mask tail events and discrete triggers
• Assumes smooth, slowly-changing inputs, but network function scaling produces discontinuities

Related Work

Queuing Theory Foundations

Beginning with Haight's pioneering work (1958), queue switching research has evolved from simple M/M/2 systems to complex heterogeneous environments.

Modern Network Applications

• Edge Computing: Han et al.'s research on impatient queues in MEC environments
• Network Slicing: Slice-based resource allocation and SLA management in 5G networks
• SDN/NFV: Dynamic load balancing in software-defined networks

Relationship to This Work

This paper integrates classical queuing theory with modern network architectures, providing an interdisciplinary perspective.

Conclusions and Discussion

Main Conclusions

1. Insufficiency of Classical Models: Traditional queue jockeying models face fundamental challenges in 5G/6G environments
2. Necessity of Hybrid Architecture: Requires hybrid designs separating state propagation from decision control
3. Information Value Orientation: Utility-based information update strategies are more efficient than periodic broadcasting
4. Stability as Critical: Must explicitly consider migration costs and anti-oscillation mechanisms

Limitations

1. Theory-Practice Gap: Most analyses are based on theoretical models, lacking validation through large-scale actual deployments
2. Insufficient Security Considerations: Protection mechanisms against malicious behavior and attacks require deeper investigation
3. Cross-Domain Coordination: Policy coordination and trust mechanisms in multi-vendor environments need refinement

Future Directions

1. Empirical Validation: Controlled experiments on MEC testbeds
2. Large-Scale Simulation: Performance quantification based on real traffic traces
3. Theoretical Bounds: Analysis of theoretical limits on minimum update frequencies
4. Security Mechanisms: Robust telemetry authentication resistant to malicious reports

In-Depth Evaluation

Strengths

1. Comprehensiveness: First systematic survey of queue jockeying field, spanning from classical theory to modern applications
2. Foresight: Accurately identifies challenges posed by 5G/6G architectural transformations to traditional models
3. Practicality: Proposed hybrid architecture and design principles have practical deployment value
4. Interdisciplinarity: Successfully bridges queuing theory, communication networks, and edge computing

Weaknesses

1. Lack of Experimental Validation: As a survey paper, lacks original experimental verification
2. Limited Quantitative Analysis: Quantitative analysis of performance improvements primarily cites other research
3. Insufficient Implementation Details: Proposed design principles require more concrete implementation guidance

Impact

1. Academic Value: Provides important theoretical foundation and development direction for queue jockeying research
2. Practical Value: Offers guidance for 5G/6G network design and MEC deployment
3. Inspirational Value: Provides excellent example for interdisciplinary research

Applicable Scenarios

1. Network Slicing Environments: Multi-tenant, heterogeneous service requirement scenarios
2. Edge Computing: Task offloading and resource allocation for latency-sensitive applications
3. Real-Time Systems: Critical applications such as industrial automation and autonomous driving

References

The paper cites 172 references, covering classical queuing theory literature, modern network architecture research, and edge computing applications, providing readers with comprehensive literature foundation.

Overall Assessment: This is a high-quality survey paper that systematically analyzes challenges faced by queue jockeying in modern network environments and proposes valuable solution directions. The paper's main contribution lies in identifying limitations of traditional models and proposing design principles adapted to new architectures, holding significant importance for both theoretical development and practical applications in this field.