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

Crónicas de Cambio de Cola en Sistemas de Colas

Información Básica

  • ID del Artículo: 2402.11061
  • Título: Chronicles of Jockeying in Queuing Systems
  • Autores: Anthony Kiggundu, Bin Han, Dennis Krummacker, Hans D. Schotten
  • Clasificación: cs.NI (Arquitectura de Redes e Internet)
  • Fecha de Publicación/Conferencia: ACM Computing Surveys (Previsto enero de 2023)
  • Enlace del Artículo: https://arxiv.org/abs/2402.11061

Resumen

Las tendencias emergentes en sistemas de comunicación, como la softwarización de redes, la descomposición funcional y la computación de borde de múltiple acceso (MEC), están remodelando el panorama de infraestructura y el ecosistema de aplicaciones. Estos cambios presentan nuevos desafíos para la transmisión de paquetes, descarga de tareas y asignación de recursos bajo requisitos estrictos de nivel de servicio. La impaciencia en colas es un factor crítico, donde las entidades en espera modifican su comportamiento en función de la latencia. Aunque el abandono (balking) y la renuncia (reneging) han sido ampliamente estudiados, esta revisión se enfoca en explorar el fenómeno menos estudiado pero operacionalmente importante del cambio de cola (jockeying), es decir, el cambio de trabajos o usuarios entre colas. A pesar de la abundante literatura que modela el comportamiento de cambio de cola, la diversidad de enfoques plantea interrogantes sobre su aplicabilidad práctica en entornos dinámicos y distribuidos de 5G y futuras redes. Este artículo revisa y clasifica las metodologías, supuestos de modelado y casos de uso de estas investigaciones, enfatizando particularmente los sistemas de comunicación y escenarios MEC. Argumentamos que los cambios arquitectónicos de las redes de próxima generación harán que muchos modelos de cambio de cola existentes sean inaplicables, e identificamos desafíos abiertos como propagación de estado, costos de migración y estabilidad, destacando paradigmas emergentes como MEC, segmentación de red y virtualización de funciones de red.

Contexto de Investigación y Motivación

Definición del Problema

El problema central que aborda esta investigación es: ¿cómo se adaptan los modelos tradicionales de cambio de cola (jockeying) a los cambios arquitectónicos en redes de comunicación de próxima generación (5G/6G), y cómo rediseñar los métodos de modelado del comportamiento de impaciencia en colas?

Importancia del Problema

  1. Proliferación de aplicaciones sensibles a la latencia: Control remoto, automatización industrial, conducción autónoma y servicios XR inmersivos requieren requisitos extremadamente altos de latencia y confiabilidad
  2. Cambios arquitectónicos: Complejidad introducida por softwarización de redes, descomposición funcional y MEC
  3. Necesidad de optimización de recursos: Asignación de recursos en tiempo real y descarga de tareas bajo restricciones estrictas de SLA

Limitaciones de Enfoques Existentes

  1. Supuestos de homogeneidad: La mayoría de los modelos asumen que los sistemas de colas son homogéneos, ignorando la heterogeneidad en la realidad
  2. Observabilidad completa: Asumen que toda la información de estado de las colas está disponible de manera oportuna y precisa
  3. Costo de migración cero: Ignoran los gastos reales de transferencia de estado y reconfiguración
  4. Entorno estático: No consideran movilidad, escalado dinámico, tráfico de ráfagas y otros factores dinámicos

Motivación de la Investigación

Con el despliegue generalizado de tecnologías como segmentación de red, SDN/NFV y MEC en redes 5G/6G, los supuestos fundamentales de la teoría clásica de colas se han roto, requiriendo urgentemente una revisión y rediseño de modelos de cambio de cola que se adapten a la nueva arquitectura.

Contribuciones Principales

  1. Revisión sistemática y exhaustiva: Primera revisión sistemática y clasificación de técnicas de modelado de cambio de cola, proporcionando la revisión de literatura más completa hasta la fecha en este campo
  2. Análisis de brechas: Evaluación cuantitativa de las limitaciones de aplicabilidad de modelos clásicos bajo restricciones arquitectónicas modernas de 5G/6G
  3. Análisis de integración arquitectónica: Análisis profundo de cómo MEC, SDN/NFV y segmentación de red redefinen el modelado de cambio de cola, revelando los impactos de heterogeneidad, latencia de señalización y restricciones de confianza entre dominios
  4. Principios de diseño y direcciones futuras: Basándose en la clasificación y análisis de brechas, se proponen principios de diseño de modelos de cambio de cola robustos y conscientes de la comunicación aplicables a entornos distribuidos de próxima generación

Explicación Detallada de Métodos

Definición de Tareas

Este artículo es un trabajo de revisión cuyas tareas principales son:

  • Entrada: Literatura existente sobre cambio de cola, características arquitectónicas de 5G/6G, restricciones de despliegue de MEC
  • Salida: Clasificación sistemática, evaluación de aplicabilidad, principios de diseño, direcciones de investigación futura
  • Restricciones: Deben considerarse restricciones técnicas y económicas del despliegue real de redes

Marco de Clasificación

1. Métodos de Modelado Estocástico

  • Procesos de Decisión de Markov (MDP): Aplicables a toma de decisiones secuencial, pero sufren del problema de explosión del espacio de estados
  • Enfoques de teoría de juegos: Basados en equilibrio de Nash, pero requieren supuestos de información completa y participantes racionales
  • Modelos de teoría de fluidos: Promedian eventos discretos en flujo continuo, aplicables al análisis de sistemas a gran escala

2. Métodos de Modelado Analítico

  • Método de matriz geométrica: Proporciona soluciones exactas para procesos cuasi-nacimiento-muerte, pero requiere sistemas de Markov estructurados y estacionarios

3. Métodos de Modelado de Comportamiento

  • Modelos de valor de información: Consideran el cambio de cola como un problema de decisión local
  • Redes neuronales artificiales: Capturan relaciones no lineales de alta dimensión, pero presentan problemas de "caja negra"

Mecanismos de Activación de Cambio

Cambio Basado en Umbral

Umbral de longitud de cola o tiempo de espera: el cambio se activa cuando la diferencia de longitud de cola excede un umbral predefinido

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

Cambio Basado en Costo y Latencia Esperada

En sistemas heterogéneos, combinando umbral de longitud de cola y tiempo de espera esperado:

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

Puntos de Innovación Técnica

  1. Diseño de arquitectura híbrida: Separación de propagación de estado y control de decisiones
    • Propagación centralizada: Asegura visibilidad del estado de cola en todo el sistema
    • Decisión distribuida: Toma de decisiones autónomas locales bajo restricciones de latencia
  2. Enfoque de valor de información: Activar actualizaciones de alta fidelidad solo cuando la ganancia de utilidad esperada exceda el costo de comunicación
  3. Garantía de estabilidad: Prevenir oscilaciones mediante umbrales de histéresis, temporizadores de enfriamiento y consideración explícita de costos de migración

Configuración Experimental

Metodología de Análisis de Literatura

  • Búsqueda sistemática: Cubre campos relacionados como teoría de colas, redes de comunicación y computación de borde
  • Criterios de clasificación: Clasificación por método de modelado, tipo de cola, umbral de cambio e indicadores de rendimiento
  • Evaluación de aplicabilidad: Evaluación de limitaciones de modelos existentes basada en características arquitectónicas de 5G/6G

Dimensiones de Evaluación

  1. Realismo de supuestos de modelado: Homogeneidad, disponibilidad de información, costos de migración, etc.
  2. Escalabilidad: Complejidad del espacio de estados, viabilidad computacional
  3. Robustez: Capacidad de adaptación a información incompleta y entornos dinámicos

Resultados Experimentales

Hallazgos Principales

1. Fallo de Supuestos Clásicos

  • Supuesto de homogeneidad: La segmentación de red introduce múltiples proveedores y configuraciones de rendimiento, haciendo insuficiente la simple comparación de longitud de cola
  • Costo de migración cero: La migración con estado genera tiempo de transmisión proporcional al tamaño de estado y características de ruta de red
  • Información completa: La propagación oportuna de descriptores de segmento autenticados consume recursos del plano de control

2. Riesgos de Estabilidad y Seguridad

  • Efecto ping-pong: Umbrales bajos de longitud de cola pueden provocar comportamiento oscilante
  • Amenazas de seguridad: Los reportes de estado no autenticados pueden ser explotados maliciosamente

3. Potencial de Mejora de Rendimiento

Los estudios numéricos muestran que la redistribución adaptativa de carga de trabajo puede reducir el tiempo de permanencia promedio en 20-30%, acelerando la finalización de tareas para aplicaciones MEC sensibles a la latencia.

Análisis de Limitaciones del Modelo

Limitaciones de Modelos Estocásticos

  • Telemetría parcial, retrasada o censurada produce estimaciones sesgadas de alta varianza
  • Sistemas dinámicos (movilidad, escalado automático) causan cambio conceptual rápido
  • La heterogeneidad de segmentación invalida modelos de agrupación

Limitaciones de Modelos de Equilibrio de Nash

  • Asumen funciones de utilidad explícitas y conocimiento suficiente de participantes
  • En la práctica, los participantes tienen racionalidad limitada y ejecutan heurísticas de aprendizaje
  • Problemas de ejecutabilidad entre dominios administrativos

Limitaciones de Modelos de Fluidos

  • El promediado de eventos discretos puede enmascarar eventos de cola y disparadores discretos
  • Asumen entrada suave y de cambio lento, pero el escalado de funciones de red produce discontinuidades

Trabajo Relacionado

Fundamentos de Teoría de Colas

Comenzando con el trabajo pionero de Haight (1958), la investigación de cambio de cola ha evolucionado desde sistemas M/M/2 simples a entornos heterogéneos complejos.

Aplicaciones en Redes Modernas

  • Computación de borde: Investigación de colas impacientes en entornos MEC por Han et al.
  • Segmentación de red: Asignación de recursos basada en segmentación y gestión de SLA en redes 5G
  • SDN/NFV: Equilibrio de carga dinámico en redes definidas por software

Relación con Este Artículo

Este artículo integra la teoría clásica de colas y la arquitectura de redes modernas, proporcionando una perspectiva integral interdisciplinaria.

Conclusiones y Discusión

Conclusiones Principales

  1. Insuficiencia de modelos clásicos: Los modelos tradicionales de cambio de cola enfrentan desafíos fundamentales en entornos 5G/6G
  2. Necesidad de arquitectura híbrida: Se requiere diseño híbrido que separe propagación de estado y control de decisiones
  3. Orientación por valor de información: Las estrategias de actualización de información basadas en utilidad son más eficientes que la difusión periódica
  4. Estabilidad crítica: Debe considerarse explícitamente los costos de migración y mecanismos anti-oscilación

Limitaciones

  1. Brecha entre teoría y práctica: La mayoría del análisis se basa en modelos teóricos, careciendo de validación en despliegues reales a gran escala
  2. Consideraciones de seguridad insuficientes: Los mecanismos de protección contra comportamiento malicioso y ataques requieren investigación más profunda
  3. Coordinación entre dominios: La coordinación de políticas y mecanismos de confianza en entornos multiproveedor aún necesita perfeccionamiento

Direcciones Futuras

  1. Validación empírica: Experimentos controlados en plataformas de prueba MEC
  2. Simulación a gran escala: Cuantificación de rendimiento basada en trazas de tráfico real
  3. Límites teóricos: Análisis de límites teóricos de frecuencia mínima de actualización
  4. Mecanismos de seguridad: Autenticación de telemetría robusta resistente a reportes maliciosos

Evaluación Profunda

Fortalezas

  1. Exhaustividad: Primera revisión sistemática del campo de cambio de cola, cubriendo desde teoría clásica hasta aplicaciones modernas
  2. Visión prospectiva: Identifica con precisión los desafíos que los cambios arquitectónicos de 5G/6G presentan a los modelos tradicionales
  3. Practicidad: Los principios de arquitectura híbrida y diseño propuestos tienen valor para despliegue real
  4. Interdisciplinariedad: Conecta exitosamente los campos de teoría de colas, redes de comunicación y computación de borde

Debilidades

  1. Falta de validación experimental: Como artículo de revisión, carece de validación experimental original
  2. Análisis cuantitativo limitado: El análisis cuantitativo de mejoras de rendimiento se basa principalmente en investigaciones citadas
  3. Detalles de implementación insuficientes: Los principios de diseño propuestos requieren orientación de implementación más específica

Impacto

  1. Valor académico: Proporciona base teórica importante y dirección de desarrollo para investigación en cambio de cola
  2. Valor práctico: Tiene significado orientador para diseño de redes 5G/6G y despliegue de MEC
  3. Inspiración: Proporciona buen ejemplo para investigación interdisciplinaria

Escenarios Aplicables

  1. Entornos de segmentación de red: Escenarios con requisitos de múltiples inquilinos y servicios heterogéneos
  2. Computación de borde: Descarga de tareas y asignación de recursos para aplicaciones sensibles a la latencia
  3. Sistemas en tiempo real: Aplicaciones críticas como automatización industrial y conducción autónoma

Referencias

El artículo cita 172 referencias, cubriendo literatura clásica de teoría de colas, investigación de arquitectura de redes modernas y aplicaciones de computación de borde, proporcionando una base bibliográfica exhaustiva para los lectores.

Evaluación General: Este es un artículo de revisión de alta calidad que analiza sistemáticamente los desafíos que enfrenta el cambio de cola en entornos de redes modernas y propone direcciones de solución valiosas. La principal contribución del artículo radica en identificar las limitaciones de los modelos tradicionales y proponer principios de diseño que se adapten a la nueva arquitectura, teniendo importancia significativa tanto para el desarrollo teórico como para la aplicación práctica en este campo.