Algoritmos de broadcasting

Los routers envían los paquetes recibidos a todos sus vecinos, excepto al que se los entrega.
Para evitar que los lazos generen una sucesión infinita de replicaciones (broadcast strorm) se utilizan dos técnias:
1. Sequence-number-controlled flooding. En cada paquete se incluye un número de secuencia que lo identifica. Este número junto con la dir IP origen del paquete sirve para que cuando un router lo recibe, este lo replica si y sólo si antes no ha sido replicado.
2. Reverse path forwarding (RPF). En este caso se utiliza sólo la dir IP del paquete. Un router lo replica si y sólo si recibe el paquete a través del enlace que forma parte de la ruta de distancia mínima entre ambos routers (el de origen del paquete y el que recibe el paquete).^* Un ejemplo lo encontramos en la siguiente figura (A es el router origen):

Es más óptimo que el fooding (cada router recibe sólo una copia de los datos).
Se basa en que los routers sólo envían los datos a través del minimum spanning tree. El árbol de expansión mínimo es un árbol (y por tanto un grafo sin ciclos) que utiliza a todos los nodos del grafo y que posee un coste mínimo.

Para determinar el minimum spanning tree se puede utilizar el algoritmo de Steiner [13], pero éste es muy costoso en términos de tiempo (es un problema de complejidad exponencial (x^N), donde N es el número de nodos del grafo y x es una costante) y por este motivo se utilizan otros algoritmos menos costosos basados en heurísticas.
Uno de los algoritmos usados es el “algoritmo del punto de encuentro (rendezvous point) para el cálculo del spanning tree”^† :
1. Definir un rendezvous router y hacérselo saber a todos los demás routers.
2. Todos los demás routers envían un mensaje tree-join hacia el rendezvous router usando el camino mínimo (que sí es determinado por los algoritmos de routing unicast).
3. Cada router que recibe un mensaje tree-join añade al spanning tree el enlace por el que ha llegado el mensaje.
4. El mensaje se retransmite hacia el rendezvous router si el router todavía no pertenece al spanning tree. Ejemplo (E es el punto de encuentro):