Routers, switches y enlaces forman grafos físicos y lógicos. Los algoritmos de encaminamiento utilizan costos para elegir rutas y reaccionar ante congestión, cambios o fallos.
Una red transporta datos entre dispositivos mediante enlaces. La teoría de grafos permite describir topología, calcular rutas, detectar puntos críticos y distribuir capacidad.
La representación depende del nivel: un vértice puede ser un host, switch, router, red autónoma o centro de datos.
El grafo físico describe cables, radios y dispositivos reales. El lógico describe conexiones visibles para un protocolo, túneles o sesiones.
Una ruta redundante en la vista lógica puede compartir infraestructura física y fallar por una misma causa.
Un enlace puede modelarse como no dirigido si ofrece características similares en ambos sentidos. Si capacidad, latencia o políticas difieren, se usan aristas dirigidas.
Que exista conectividad A → B no garantiza la ruta inversa ni que ambos sentidos sigan el mismo camino.
El peso puede representar latencia, costo administrativo, pérdida, utilización o una combinación.
Los pesos deben ser comparables y reflejar el objetivo operativo.
Una tabla asocia destinos o prefijos con el siguiente salto y una interfaz. No necesita almacenar el camino completo.
Los protocolos calculan y actualizan estas decisiones a partir de información distribuida.
Ejecuta Dijkstra paso a paso desde A hasta G. Después provoca el fallo de C–E o congestiona B–C para observar la ruta alternativa.
Distancias desde A
Ruta a G
Acción actual
Cada router anuncia sus enlaces y costos. Con esa información construye una vista de la topología y ejecuta Dijkstra.
Las actualizaciones requieren números de secuencia y mecanismos para descartar información antigua.
Cada router comunica a sus vecinos su mejor distancia conocida hacia los destinos. La actualización sigue la idea de Bellman–Ford.
No necesita conocer toda la topología, pero puede converger más lentamente tras ciertos fallos.
Información desactualizada puede hacer que dos routers se envíen tráfico mutuamente. El campo de límite de saltos evita una circulación infinita de paquetes.
Horizonte dividido, envenenamiento de rutas y temporizadores ayudan a reducir bucles en protocolos de vector distancia.
Después de un cambio, existe un intervalo durante el que los routers poseen vistas diferentes. Convergencia es el proceso de alcanzar decisiones coherentes.
Una reacción muy lenta pierde conectividad; una demasiado sensible puede oscilar ante variaciones pequeñas.
Los enlaces redundantes entre switches pueden crear bucles de tramas. Un protocolo de árbol de expansión deshabilita lógicamente algunas conexiones para conservar una topología sin ciclos.
Si falla un enlace activo, puede habilitarse una alternativa previamente bloqueada.
Un puente del grafo es un enlace cuya pérdida desconecta la red; un vértice de corte representa un dispositivo crítico.
La redundancia útil debe considerar también energía, ubicación física y proveedores compartidos.
La ruta más corta no considera por sí sola cuánto tráfico comparte cada enlace. Las capacidades convierten la red en un problema de flujo.
El flujo máximo proporciona una cota de transporte entre regiones, mientras los cortes mínimos revelan cuellos de botella.
Al acercarse a la capacidad, crecen colas, latencia y pérdida. Si el costo depende del tráfico, recalcular rutas puede desplazar la congestión o provocar oscilaciones.
El balanceo debe considerar capacidad disponible, estabilidad y distribución desigual de los flujos.
Cuando existen varios caminos mínimos, el tráfico puede repartirse entre siguientes saltos equivalentes.
El reparto por flujo mantiene orden de paquetes, mientras el reparto por paquete utiliza mejor los enlaces pero puede introducir reordenamiento.
Enviar el mismo contenido a múltiples receptores mediante rutas independientes duplica tráfico. Un árbol multicast comparte tramos y ramifica solo cuando es necesario.
Optimizar exactamente el árbol con restricciones generales puede ser difícil, por lo que se utilizan árboles basados en rutas cortas o puntos centrales.
SDN separa decisiones de control del reenvío. Un controlador con vista amplia puede calcular rutas, aplicar políticas y programar dispositivos.
La centralización lógica facilita optimización global, pero requiere tolerancia a fallos y sincronización del estado.
Telemetría y trazas permiten comparar la topología esperada con el comportamiento observado. Cambios inusuales pueden indicar fallos, errores o ataques.
El análisis de grafos ayuda a detectar rutas inesperadas, concentración de dependencia y propagación potencial de incidentes.
Las redes de computadoras convierten la teoría de grafos en decisiones operativas: elegir rutas, responder a fallos y administrar capacidad. Una buena métrica debe reflejar el servicio que se desea optimizar.
En el próximo tema estudiaremos grafos en compiladores y análisis de dependencias.