Portada » Informática » Optimización y Arquitecturas Avanzadas en Redes de Datos
Ambos teoremas se usan para estudiar redes que pueden configurar sus conexiones internas para evitar bloqueos. Slepian-Duguid establece las condiciones que debe cumplir una red para ser reconfigurable, y Offman demuestra que una red Banyan puede ser reconfigurable si se le añaden etapas adecuadas (m = n – 1).
r2 >= max(n,m)
M: Número de matrices de la 3ª etapa
N: Número de matrices (switches) en la 1ª etapa
r2 = n
. Es decir, basta que haya tantos conmutadores intermedios como en las etapas de entrada/salida.
Es RNB porque cumple el teorema de Slepian-Duguid: r2 >= max(n,m)
.
Donde:
Teorema de Clos: garantiza SNB si se cumplen ciertas condiciones (por ejemplo, tener suficientes conmutadores intermedios).
Teorema de Slepian-Duguid: garantiza que una red es RNB si el número de etapas y matrices intermedias es suficiente (por ejemplo, r2 ≥ max(n,m)
).
No se puede evitar el bloqueo en una red multietapa de dos etapas de conmutación total porque no hay suficiente flexibilidad interna para garantizar que todas las conexiones posibles se puedan establecer sin conflicto.
Una red multietapa de solo dos niveles (entrada → salida, sin etapa intermedia) no puede evitar el bloqueo. Si varios dispositivos quieren hablar con destinos diferentes al mismo tiempo, puede que se bloqueen mutuamente, aunque haya enlaces disponibles. Esto es una limitación estructural.
En una red con 3 etapas se puede evitar el bloqueo, pero solo si se cumple el Teorema de Clos o el de Slepian-Duguid, que te indican cuántos conmutadores intermedios necesitas.
La propiedad más destacada es que el camino desde origen a destino se calcula automáticamente usando los bits del destino. Esto simplifica enormemente el control y el encaminamiento.
Son redes bloqueantes, es decir, puede que no haya camino disponible entre dos nodos aunque teóricamente exista, debido a la ocupación interna de los switches intermedios.
Porque mantiene la propiedad de autoenrutamiento de Banyan y resuelve el problema del bloqueo sin perder simplicidad en el control.
¿Tiene accesibilidad total?
Sí.
Cada entrada puede llegar a cualquier salida siempre que no haya otras conexiones activas.
Esto significa que existen caminos entre cualquier par de entrada y salida, lo que se conoce como accesibilidad total (pero solo bajo la condición de que el sistema esté libre en ese momento).
¿Es no bloqueante por reconfiguración?
No.
No es no bloqueante por reconfiguración porque solo existe un camino entre cada par entrada-salida.
Si ya hay conexiones establecidas, podrían bloquear otras nuevas si comparten algún enlace. Por eso, no se pueden reconfigurar las conexiones sin cortar alguna de las actuales.
¿Tiene accesibilidad total?
No.
Una red tiene accesibilidad total si cada entrada puede alcanzar cualquier salida, al menos cuando no hay otras conexiones activas.
Pero en esta red:
Por ejemplo, si el nodo ‘a’ quiere ir a ‘g’, no hay un camino directo posible debido a la forma fija de las conexiones entre switches.
¿Es no bloqueante?
Tampoco.
Una red es no bloqueante si puede establecer una nueva conexión sin bloquear otras existentes, mediante reconfiguración si es necesario.
En esta red, hay conexiones fijas que no permiten reorganizar rutas para acomodar nuevos flujos. Por ejemplo:
¿Tiene accesibilidad total? ¿Por qué?
Sí tiene accesibilidad total.
Porque es una red Clos con 3 etapas y cumple con la condición de accesibilidad total:
Cada entrada puede alcanzar cualquier salida si no hay otras conexiones establecidas.
Se trata de clasificar dos redes multietapa (Red A y Red B) según su capacidad de evitar bloqueos bajo distintas condiciones:
4.1 Identificar tipo:
4.2 Equivalencia:
4.3 Coste en puntos de cruce:
Se extiende con log2 N – 1
Offman K >= 2 N – 1
De memoria: Omega y Baseland.
En una red DiffServ, se usa un policer SR-TCM (Single Rate Three Color Marker) para garantizar el cumplimiento del contrato de tráfico. El EBS (Excess Burst Size) se ha fijado a 0. Para un Per-Hop Behavior (PHB) del tipo Expedited Forwarding, ¿qué acción (descartar, transmitir y marcar como fuera de contrato, transmitir) se asocia al tráfico que ha sido señalado con los siguientes colores?
– Verde: transmitir
– Rojo: descartar
¿Y para un Per-Hop Behavior del tipo Assured Forwarding (0,5p)?
Policer SR-TCM (Single Rate Three Color Marker): es un mecanismo de control de tráfico. Un marcador de tres colores que clasifica los paquetes según su cumplimiento con un contrato de tráfico.
Funcionamiento:
Si EBS = 0, significa que no existe el color amarillo; todo lo que no sea verde se marca directamente como rojo y se descarta si el PHB (Per-Hop Behavior) como EF no lo permite.
Per-Hop Behavior del tipo Expedited Forwarding (EF) es un tipo especial de tratamiento en redes DiffServ. Este tipo no admite degradación del tráfico, es decir, que solo los paquetes verdes son válidos dentro del contrato y cualquier paquete fuera del contrato es descartado inmediatamente.
Per-Hop Behavior del tipo Assured Forwarding (AF): el tráfico fuera de contrato (rojo) puede transmitirse, pero sin garantía; es decir, tiene alta probabilidad de descarte en congestión. Se considera «fuera de contrato», pero no se descarta automáticamente.
En una red IntServ, ¿qué tipo de servicio (end-to-end reservation service type) elige para una aplicación que necesita bajo retardo, bajo jitter, bajas pérdidas y ancho de banda garantizado (0,5p)?
Guaranteed Services
En una IntServ, los dos tipos principales de servicios definidos son:
En una red DiffServ, ¿qué PHB (per hop behavior) elige para una aplicación que necesita ancho de banda garantizado (0,5p)?
Assured Forwarding
AF está diseñado para aplicar diferentes niveles de garantía de entrega, incluyendo ancho de banda asegurado. Permite definir varias clases de tráfico, cada una con su nivel de prioridad y probabilidad de descarte. El tráfico marcado como verde (dentro del contrato) tiene baja probabilidad de pérdida, lo que asegura un uso mínimo garantizado del enlace.
Propósito: Controlar el rendimiento efectivo del tráfico.
Propósito: Marcar/priorizar paquetes para aplicar reglas específicas.
QoS se refiere a las garantías reales que la red ofrece al tráfico (como poco retardo). CoS es una clasificación de paquetes en categorías para tratarlos diferente. CoS es parte de la implementación de QoS.
Clase A: envía 1 paquete de 800 bytes
Clase B: envía 1 paquete de 200 bytes
Se transmite en 2 turnos: Total = 800 + 200 = 1000 Bytes
A: 1*800 = 800
B: 5*200 = 1000 Bytes
Para A: 800/1800 = 44.4%
Para B: 1000/1800 = 55,6%
Si ambas clases usan su quantum completo, queda 1000 /(1000 + 1000) = 0.5 cada una.
Funcionamiento:
Ambos sistemas garantizan mínimos, pero:
Protocolo usado para implementarlo:
Mensajes principales de RSVP:
Principal problema de IntServ:
Multifield (MF) Classification
Behavior Aggregate (BA) Classification
El camino mostrado en el ejemplo es local, ya que utiliza Adjacency Segments para forzar el uso de enlaces concretos, en lugar de dejar que el routing IP determine el camino global (que sería con Prefix Segments).
Los segmentos indican qué camino debe seguir un paquete.
LSP 1: A → B → C → D → E
LSP 2: N → M → C → D → E
Técnicas utilizadas para optimizar:
1. De A a C:
2. De N a C:
Hasta aquí, los caminos A→C y N→C son diferentes, así que necesitan etiquetas separadas.
3. De C a E (común a ambos):
¿En qué consiste?
En lugar de seguir siempre las rutas más cortas (como haría OSPF o IS-IS), con MPLS TE se pueden establecer caminos explícitos (LSPs) que evitan congestión, equilibran la carga y respetan restricciones de ancho de banda, latencia, etc.
Esto se logra con:
Principales objetivos:
El mecanismo de LSP preemption en ingeniería de tráfico (MPLS-TE) consiste en permitir que un LSP de alta prioridad pueda «interrumpir» o reemplazar a otro LSP de menor prioridad que esté ocupando los recursos (ancho de banda, enlaces, etc.) necesarios para establecerse.
¿Cómo funciona?
¿Para qué sirve?
Merging de etiquetas (fusión de etiquetas) es una técnica usada en MPLS (Multiprotocol Label Switching) para optimizar el número de etiquetas necesarias cuando múltiples LSPs (Label Switched Paths) comparten el mismo tramo final.
¿Cómo funciona?
Cuando dos o más LSPs diferentes llegan a un mismo nodo y comparten la misma salida, este nodo puede fusionar los LSPs y continuar con una sola etiqueta hacia el siguiente salto.
Ejemplo:
Supongamos dos LSPs:
Ambos pasan por C → D → E.
Ventajas del merging:
Penultimate Hop Popping (PHP) es una técnica utilizada en redes MPLS donde el router anterior al último salto (penultimate hop) elimina la etiqueta MPLS del paquete antes de enviarlo al router final (egress LSR).
¿Cómo funciona?
Ventajas que aporta PHP:
Una tabla de hash es una estructura que almacena y busca datos rápidamente. Utiliza una función hash para convertir una clave en una posición de memoria. Idealmente, cada clave tiene una única posición, pero a veces varias claves generan la misma posición (colisión).
Las tablas hash convencionales pueden necesitar muchos accesos a memoria si hay colisiones. En cuckoo hashing, cada elemento tiene dos posibles sitios donde puede ir; si ambos están ocupados, se desplaza otro elemento para hacer sitio, lo cual garantiza que buscar algo nunca tarda más de 2 accesos, incluso si la tabla está llena. Como tiene un tiempo fijo, funciona muy bien con routers con pipelines o procesamiento paralelo.
El speed-up es cuántas veces más rápido debe funcionar el conmutador interno (switching fabric) que las líneas de entrada y salida normales del router.
En un router output-queued, los paquetes van directamente a las colas de salida; no se quedan esperando en las entradas.
Entonces, si tienes N entradas y todas quieren enviar al mismo puerto de salida a la vez, el conmutador tiene que mover N paquetes al mismo tiempo, uno desde cada entrada.
El speed-up en un router con colas en la salida (output-queued) debe ser al menos igual al número de puertos (N), porque el conmutador tiene que mover todos los paquetes que llegan a la vez hacia las salidas sin perder ninguno.
Ambos mensajes se envían directamente sobre IP y el identificador de protocolo es el 46.
Ejemplos de uso:
Ejemplos de uso:
Ejemplo: entrada TCAM 110x, tanto 1100 como 1101 son válidas.
Esto resuelve el problema de Head-of-Line-blocking, que es cuando el primer paquete de la cola quiere ir a una salida ocupada, bloquea a otros que sí podrían salir por otras salidas libres. Con VoQ, esto no sucede porque cada destino tiene su propia cola.
La figura muestra una arquitectura de bus compartido (shared bus). Todas las Line Cards comparten un único bus central para transferir datos entre entradas y salidas.
El bus central es el principal punto de congestión, ya que todos los flujos deben pasar por él. Si múltiples line cards intentan usar el bus al mismo tiempo, se genera contención y posibles retrasos.
Si hay N line cards y cada una transmite a velocidad de línea R, entonces el bus debe tener un throughput de al menos:
Throughput del bus = N * R
Esto garantiza que todas las entradas puedan enviar al mismo tiempo sin causar colisiones o cuellos de botella.
La figura representa un Patricia Trie (también conocido como Compressed Binary Trie), una estructura de datos usada en búsqueda de rutas IP basada en prefijos binarios. Es eficiente en memoria y permite búsquedas rápidas con el método Longest Prefix Match (LPM).
VoQ significa que cada puerto de entrada del conmutador mantiene una cola virtual separada por cada puerto de salida. Así, si hay congestión en un puerto de salida, no bloquea el envío de otros paquetes destinados a otros puertos, evitando el problema de Head-of-Line (HoL) blocking.
En este escenario, cada entrada solo tiene paquetes para un puerto de salida específico (por ejemplo, entrada 1 solo envía a salida 3), así que no hay conflicto entre destinos. Por tanto, no habría ventajas reales al usar VoQ, porque no se produciría HoL blocking.
El slow path no necesita aceleración por hardware como los TCAMs. Se puede gestionar con CPU/software, mientras que el fast path sí aprovecha los TCAMs para búsquedas rápidas (ACLs, rutas, etc.).
El multibit Trie permite hacer más búsquedas por segundo (mayor velocidad) y reduce los accesos a memoria, lo cual mejora la escalabilidad y eficiencia del switch.
1 hash function, 2 tables
La opción «2 hash functions, 1 table» es la mejor para minimizar el peor caso de accesos.
¿Por qué?
Para minimizar el número de accesos en el peor caso, usarías 2 funciones hash con 1 tabla, ya que asegura encontrar una clave con a lo sumo 2 accesos de memoria.
Una VPN (Virtual Private Network) consiste en extender una red privada sobre una red pública (como Internet), de forma segura. Permite a los usuarios conectarse a una red como si estuvieran físicamente en ella, aunque estén geográficamente separados.
Características esenciales de una VPN:
Problema principal de RRM:
Mejora que introduce iSLIP:
Head-of-Line (HoL) blocking en Input-Queued:
En Distributed Output Queued:
En una red de conmutación de circuitos, como en telefonía tradicional:
En cambio, en una red de conmutación de paquetes (como IP):
Por eso, en redes de circuitos el retardo de cada unidad (ej. celda o bit) es predecible, mientras que en redes de paquetes fluctúa, y hay que usar buffers para compensarlo.
El «soft state» o estado blando es un mecanismo en protocolos como RSVP (Resource Reservation Protocol) y RSVP-TE (Traffic Engineering) en el que:
¿Qué beneficios aporta?