matematicas discretas

Tema 19

Enrutamiento de amplia difusión (broadcast)
Eytan Modiano


Eytan Modiano
Diapositiva 1

Enrutamiento de amplia difusión


•

Se dirige un paquete desde un origen hacia todos los nodos de la red

•

Posibles soluciones:
– Inundación (flooding): cada nodo envía el paquete a todos los links de salida:
Se descartan los paquetes recibidos por segunda vez

–Enrutamiento de árbol de expansión: se envía el paquete a lo largo de un
árbol que incluye todos los nodos de la red

Eytan Modiano
Diapositiva 2

Grafos

•

Un grafo G = (N,A) consta de un conjunto finito no vacío de nodos N
y un conjunto de pares de nodos A llamados arcos (enlaces o aristas)

2
2
1

3
1
4

N = {1,2,3,4}

A = {(1,2),(2,3),(1,4),(2,4)}

Eytan Modiano
Diapositiva3

3

N = {1,2,3}
A = {(1,2)}


Caminos y rutas
• Un camino (walk) es una secuencia de nodos (n1, n... nk) en la que cada par de
nodos adyacentes es un arco.

•

Una ruta (path) es un camino sin nodos repetidos

2
1

2
4

3

Camino (1,2,3,4,2)

Eytan Modiano
Diapositiva 4

1

4

3

Ruta (1,2,3,4)

Ciclos

•

Un ciclo es un camino (n1, n2... nk) con n1= nk, k>3, y sin nodos
repetidos excepto n1 = nk

2
1

4

3

Eytan Modiano
Diapositiva 5

Ciclo (1,2,4,3,1)

Grafo conexo

•

Un grafo es conexo si existe una ruta entre cada par de nodos
2

2

1

1
4

3

3

Conexo

Inconexo

• Un grafo inconexo se puede separar en dos o más componentes
conexos

Eytan Modiano
Diapositiva 6

Árboles y grafos acíclicos•

Un grafo acíclico es un grafo sin ciclos

•

Un árbol es un grafo acíclico conexo
2

1

2

4

1

3

3

Acíclico,
conexo

•

1

3

Cíclico,
no árbol

El número de arcos en un árbol es siempre uno menos que el número de nodos:
–

Eytan Modiano
Diapositiva 7

Inconexo,
no árbol

2

Demostración: empezar con un nodo arbitrario y añadir un nodo cada vezque
se añade un arco => N nodos y N-1 enlaces. Si se añade un arco sin añadir un nodo,
el arco deberá ir a un nodo que ya esté en el árbol formando, así, un ciclo

Subgrafos

•

G' = (N',A') es un subgrafo de G = (N,A) si:
–
–
–

•

1) G' es un grafo
2) N' es un subconjunto de N
3) A' es un subconjunto de A

Un subgrafo se obtiene eliminando nodos y arcos de un grafo:
–Nota: los arcos adyacentes a un nodo eliminado también deben ser eliminados
2

1

2

4

1

3

3

–

Eytan Modiano
Diapositiva 8

Grafo G

Subgrafo G' de G

Árboles de expansión (Spanning trees)

•

T = (N',A') es un árbol de exansión de G = (N,A) si:
T es un subgrafo de G con N' = N y T es un árbol

–

2

2
5

1

4
3

Grafo G

Eytan Modiano
Diapositiva9

5
1

4
3

Árbol de expansión de G

Árboles de expansión

•

Los árboles de expansión son útiles para difundir y recoger información
de control en las redes; a veces son útiles también para el enrutamiento

•

Para difundir datos desde el nodo n:
–
–

•

El nodo n realiza una amplia difusión de los datos en todos los arcos
del árbol adyacente
Otros nodos retardan losdatos en los arcos de otros árboles adyacentes

Para recoger datos en el nodo n:
– Todas las ramas del árbol (todas salvo la n) envían datos
– Los otros nodos (todos salvo el n) esperan la recepción de datos en todos
sus arcos salvo en uno adyacente y, a continuación, envían los datos
recibidos más los propios por el arco restante

Eytan Modiano
Diapositiva 10

Construcción generalde un árbol de expansión
•

Algoritmo para construir un árbol de expansión para un grafo conexo G = (N,A):
1) Seleccionar cualquier nodo n en N; N' = {n}; A' = { }
2) Si N' = N, entonces parar (T=(N',A') es un árbol de expansión)
3) Elegir (i,j) ∈ A, i ∈ N', j ∉N'
N' := N'∪{j}; A' := A'∪{(i,j)}; ir al paso 2

•

La conectividad de G garantiza que se puede elegir un arco en el paso 3...