Certified Closed-Loop Control for Packet Networks: A Compositional Certification Framework

Resumen Técnico: Control de Lazo Cerrado Certificado para Redes de Paquetes

1. Declaración del Problema

Las redes de paquetes funcionan como sistemas dinámicos controlados caracterizados por discontinuidades, observaciones con retardo y la información parcial del estado. Si bien los controladores adaptativos o basados en aprendizaje (propositores) pueden mejorar el rendimiento, carecen de garantías inherentes; una propuesta insegura puede provocar inanición de colas, picos de retardo en la cola (tail-delay) o inestabilidad. Los mecanismos de seguridad existentes suelen analizar la acción prevista de un controlador o dependen de supuestos fuera de línea (offline) que no se mantienen bajo estrés en tiempo de ejecución, telemetría con retardo o cambios adversos en el tráfico.

El problema central abordado es cómo combinar la propuesta adaptativa con garantías estrictas y verificables en línea para las colas de paquetes de una manera que se componga a través de una red. Específicamente, el artículo busca asegurar que la acción realmente ejecutada en el plano de datos satisfaga las restricciones de seguridad y estabilidad, independientemente de la calidad o la naturaleza del propositor (que puede ser heurístico, aprendido o agéntico).

2. Metodología

El artículo propone una arquitectura de Operador Certificado que se sitúa entre cualquier propositor y el plano de datos. Este operador actúa como un filtro de seguridad en tiempo de ejecución, imponiendo un certificado compilado de la configuración en cada ciclo de control (control tick).

Mecanismo Central:

• Entrada: En cada ciclo $t$, un propositor emite una acción candidata $\tilde{u}(t)$ basada en telemetría con retardo.
• Certificación: El operador proyecta $\tilde{u}(t)$ sobre un conjunto factible certificado $U_{cert}(t)$ derivado de un certificado unificado.
• Salida: El operador devuelve una acción ejecutada $u(t)$, un sobre (envelope) exportado $\bar{z}(t)$ para la composición descendente, y un indicador de estado ($\sigma(t)$).
  • CERTIFIED (CERTIFICADO): La acción satisface todas las restricciones.
  • INFEASIBLE (INFRACTABLE): Las restricciones no pueden cumplirse; el operador ejecuta una "caída de respaldo de minimización de holgura" (política de emergencia) e informa la magnitud de la violación.
  • MISSING (AUSENTE): Faltan las entradas requeridas (envelopes o límites de estado).

Componentes del Certificado:
El marco unifica tres tipos de restricciones en un problema de optimización por ciclo:

1. Tipo B (Barrera/Seguridad): Impone topes de acumulación (backlog caps) ($q_i(t) \le Q_{max}$) para prevenir desbordamientos. Esto incluye restricciones lineales para pisos de servicio (para clases protegidas) y topes de mitigación.
2. Tipo A (Deriva/Estabilidad): Impone condiciones de deriva de Foster–Lyapunov. Si una cola excede un umbral alto ($q_i(t) \ge Q_{hi}$), la tasa de servicio debe exceder el sobre de llegada más un margen ($\epsilon$), asegurando la estabilidad.
3. Tipo C (Composición): Exporta un sobre $\bar{z}(t)$ que representa el límite superior de salida. Los módulos descendentes utilizan estos límites exportados como sus supuestos de llegada, permitiendo un razonamiento modular.

Gestión de Restricciones del Mundo Real:

• Telemetría y Actuación con Retardo: El operador construye límites de acumulación conservadores utilizando contadores con retardo y sobres de llegada declarados. Tiene en cuenta el "retardo de actuación" ($\tau_u$) al proyectar las restricciones hacia el futuro tiempo en el que la acción realmente surtirá efecto.
• Seguimiento de Servicio: Reconociendo que los planificadores reales (por ejemplo, WFQ, DRR) pueden no realizar perfectamente las tasas objetivo debido a la packetización o el agrupamiento (batching), el modelo introduce un factor de seguimiento de servicio $\kappa \in [\kappa_{min}, 1]$. Las garantías se adjuntan a la remoción realizada, acotada por este factor.
• Semántica de Inviabilidad: En lugar de fallar silenciosamente, el operador resuelve una proyección relajada que minimiza la holgura cuando las restricciones son estructuralmente imposibles (por ejemplo, bajo una sobrecarga severa). Esto proporciona una señal auditable de la violación.

3. Contribuciones Clave

1. Modelo Formal: Un modelo de lazo cerrado con retardo para colas de paquetes y una interfaz de operador certificado que compila la configuración en restricciones por ciclo.
2. Restricciones Unificadas: Un marco que soporta topes de acumulación, pisos/topes de servicio, estabilidad explícita basada en deriva y contratos composicionales mediante sobres exportados.
3. Garantías Teóricas:
   • Seguridad a Nivel de Operador: Se demuestra que si el operador reporta CERTIFIED y las entradas son válidas, la acumulación se mantiene dentro de los límites seguros.
   • Seguridad y Estabilidad Composicional: Demostrado para redes DAG de alimentación directa (feed-forward) utilizando únicamente sobres exportados.
   • Cierre Cíclico: Un resultado que muestra que las redes cíclicas logran una solución de sobre única de punto fijo bajo una condición de "pequeña ganancia" (radio espectral de la matriz de ganancia de enrutamiento/exportación $< 1$).
4. Semántica del Fallo: Definiciones explícitas para brecha (violación de sobre), inviabilidad (violación de restricción) y falta de información, asegurando que el sistema permanezca definido y auditable incluso bajo estrés.

4. Resultados y Evaluación

La evaluación se realizó en un backend de Python de nivel de bytes en lazo cerrado, centrándose en el límite de certificación en lugar de los detalles de implementación del planificador de Linux de bajo nivel.

• Rendimiento: El paso de certificación (resolver la proyección) es computacionalmente eficiente, tomando aproximadamente 37–52 µs para 128 colas, lo que permite intervalos de control a escala de milisegundos.
• Robustez ante Propositores:
  • Para propositores benignos (proporcionales al backlog o aleatorios), el operador actúa de forma neutral, pasando las acciones con corrección mínima.
  • Para propositores adversarios (diseñados para causar inanición), el operador reduce significamente las colas de retardo p99/p99.9 y restaura el rendimiento mediante la imposición de restricciones de barrera y deriva.
• Gestión de Retardos: Bajo telemetría y actuación con retardo, el operador evita las "excursiones de umbral" observadas en la ejecución directa o el recorte ingenuo al compilar las restricciones sobre la ventana de retardo de peor caso.
• Desajuste de Sobre (Envelope Mismatch): El sistema identifica y reporta correctamente las brechas cuando los sobres declarados son optimistas (violados por el tráfico real), evitando que los módulos descendentes dependan de contratos inválidos.
• Sobrecarga: Bajo sobrecarga, el sistema transiciona a un "modo de emergencia", reportando INFEASIBLE y cuantificando la holgura, en lugar de violar silenciosamente las restricciones de seguridad.
• Inversión de Prioridad: El marco previene con éxito la inversión de prioridad (donde el tráfico masivo/bulk causa la inanición del tráfico sensible a la latencia) mediante la imposición de pisos de servicio explícitos como restricciones de primera clase, independientes de la lógica del propositor.

5. Significado y Alcance

El artículo sostiene que el control de la red de paquetes debe certificarse en el punto de ejecución, no solo en la etapa de propuesta. La importancia radica en la separación de la intención de un controlador adaptativo de la seguridad de la acción ejecutada.

• Declaraciones Modestas: Los autores declaran explícitamente que este trabajo no pretende la verificación mecanizada del compilador de certificados, del solver o del backend subyacente del plano de datos (por ejemplo, el kernel de Linux o el hardware de la NIC). Las garantías son condicionales a la validez de los sobres declarados, los límites de estado y el factor de seguimiento de servicio ($\kappa_{min}$).
• Posicionamiento: El marco está diseñado para trabajar con el cálculo de redes clásico (usando contratos de tipo token-bucket como entradas) pero desplaza la ejecución al tiempo de ejecución (runtime). Trata el "sobre" no solo como un supuesto offline para límites estáticos, sino como una entrada dinámica para una interfaz de certificación por ciclo.
• Trabajo Futuro: El artículo identifica la necesidad de instanciar el factor de seguimiento de servicio en hardware real (HTB de Linux, DRR, switches programables) y de fortalecer la base de computación confiable mediante la validación de traducción o pruebas verificadas por máquina.

En resumen, el artículo proporciona un marco riguroso y composicional para la garantía en tiempo de ejecución en redes de paquetes, asegurando que, incluso si un propositor es defectuoso o la red está bajo estrés, las acciones ejecutadas permanezcan dentro de límites auditables de seguridad y estabilidad.