1

Puentes Transparentes (IEEE 802.1d)Puentes “No Frills”.Puentes “Learning”.Problema de los ciclos. Algoritmo de Spanning Tree.Extensiones a los puentes transparentes.

BibliografíaR. Perlman, “Interconnections Second Edition

Bridges, Routers, Switches and Internetworking protocols”,Addison Wesley, 1999.

2

Puente = Switch

Diferencias:

1) Número de puertos

2) Velocidad de conmutación (SW vs HW)

Igualdades:

1) Escuchar promiscuo

2) Aprendizaje

3) Spanning Tree Protocol

No relevante, evolución lógica

Engañoso

HUB

3) Multipunto vs. Punto-a-punto

3

PuentesTransp.

No Frills (“tontos”)

“Listos”

Administrador

Dir. en rangos

Dir. Estructuradas

Puentes “learning”

Puentes Transparentes

4

A BC D

E F

A A

B A ------B A ------

B A ------A B ------

B

1. Escuchar “promiscuo” (como todos los puentes transparentes).2. Con la DIR. ORIGEN... Actualizar la CACHE del puerto por donde la ha recibido.3. Con la DIR. DESTINO ...

Comprobar las CACHES de todos los puertos ...SI la encuentra

SI es el mismo puerto ---> eliminar la tramaSI NO ---> transmitir por el puerto correspondiente

SI NO ---> Transmitir por todos los puertos menos por el que recibió la trama.4. Eliminar de las CACHES la información con tiempo mayor a “aging time”.

CDEF

BCD

EF

Puentes “Learning”

5

A

B

¿Solución al problema? Evitarlo

1. Prohibir los bucles Si existen ... culpar al administrador (como con los repetidores).

2. Que un puente (u otra máquina) pueda detectar la existencia de un bucle. (¿cómo?)

3. Diseñar un algoritmo que seleccione un ÁRBOL de la topología original.Existirían los ciclos, pero no “activos” algoritmo de SPANNING TREE

Es interesante que existan los ciclos. Ciclo camino alternativo tolerancia a fallos.

Problema de los ciclos

6

618

22 56

ÁRBOL: N nodos unidos por N-1 líneas.ÁRBOL de EXPANSIÓN: ...que se expande a partir de un nodo raíz.RAÍZ: El puente con el BRIDGE-ID más bajo.MÉTRICA: Criterio para la expansión. Usaremos la más sencilla, el HOP (otras posibilidades).

Cada puente se une al árbol buscando la métrica mejor a la raíz.

ÁRBOL: N nodos unidos por N-1 líneas.ÁRBOL de EXPANSIÓN: ...que se expande a partir de un nodo raíz.RAÍZ: El puente con el BRIDGE-ID más bajo.MÉTRICA: Criterio para la expansión. Usaremos la más sencilla, el HOP (otras posibilidades).

Cada puente se une al árbol buscando la métrica mejor a la raíz.

Expansión vistadesde fuera

14 25

Root

1 HOP

2 HOP

3 HOP

SPANNING TREE

7

Spanning Tree Protocol (STP) es un algoritmo DISTRIBUIDOa) Muy sencillo de ejecución en cada puenteb) Complejo de controlar globalmente

Idea básica1) Los puentes transmiten

periódicamente a los vecinos mensajes de configuración (BPDU).

2) Los puentes seleccionan al puente raíz (el de número de identificación más bajo).

3) Cada puente calcula la mejor métrica a la raíz.

4) Para cada LAN, se selecciona un designate bridge entre los puentes que conectan a la LAN (el puente con mejor métrica a la raíz).

5) En cada puente, se selecciona como root port el puerto que da al puente acceso a la raíz con la mejor métrica.

6) Puertos en el árbol = root port + designate portsresto = blocking

Idea básica1) Los puentes transmiten

periódicamente a los vecinos mensajes de configuración (BPDU).

2) Los puentes seleccionan al puente raíz (el de número de identificación más bajo).

3) Cada puente calcula la mejor métrica a la raíz.

4) Para cada LAN, se selecciona un designate bridge entre los puentes que conectan a la LAN (el puente con mejor métrica a la raíz).

5) En cada puente, se selecciona como root port el puerto que da al puente acceso a la raíz con la mejor métrica.

6) Puertos en el árbol = root port + designate portsresto = blocking

1 2

4 5

3

1

X

X

X

STP: Operación

8

ROOT-ID = Prioridad (16 bits) + Dirección MAC de una de las placas de red (48 bits)ROOT-ID = Prioridad (16 bits) + Dirección MAC de una de las placas de red (48 bits)

Valor de fábrica = 32.535Valor de fábrica = 32.535

Configurable por el administradorConfigurable por el administrador

100Mbps

¿Que puente seleccionarías como ROOT?

Selección del puente ROOT

9

1.......... 42 42 Mensaje de configuración (BPDU)

Dest. Orig. Tipo Datos

Root-IDCostBridge-IDPort-ID.....Otros

Hello time (1 a 10 seg)

Mensajes de configuración

10

Los puente reciben los mensajes de configuración de sus vecinos y ...eligen el “MEJOR MENSAJE”. Configuran sus puertos en base al mejor mensaje entre

- los recibidos- y el que puede generar el propio puente.

Los puente reciben los mensajes de configuración de sus vecinos y ...eligen el “MEJOR MENSAJE”. Configuran sus puertos en base al mejor mensaje entre

- los recibidos- y el que puede generar el propio puente.

Sean M(A)=(a1, a2, a3, a4) y M(B)=(b1,b2,b3,b4) dos BPDUs.Decidimos que el mensaje M(A) es mejor que M(B) con base en:si (a1<b1) entonces M(A) es mejor que M(B);si (a1=b1) entonces si (a2<b2) entonces M(A) es mejor que M(B);si (a1=b1) entonces si (a2=b2) entonces si (a3<b3)

entonces M(A) es mejor que M(B);si (a1=b1) entonces si (a2=b2) entonces si (a3=b3) entonces si (a4<b4)

entonces M(A) es mejor que M(B);

Sean M(A)=(a1, a2, a3, a4) y M(B)=(b1,b2,b3,b4) dos BPDUs.Decidimos que el mensaje M(A) es mejor que M(B) con base en:si (a1<b1) entonces M(A) es mejor que M(B);si (a1=b1) entonces si (a2<b2) entonces M(A) es mejor que M(B);si (a1=b1) entonces si (a2=b2) entonces si (a3<b3)

entonces M(A) es mejor que M(B);si (a1=b1) entonces si (a2=b2) entonces si (a3=b3) entonces si (a4<b4)

entonces M(A) es mejor que M(B);

“Mejor mensaje”

11

Estados Puertoforwarding ---------- root-port, designated-portlistening ------------ estado intermedio (forward delay)learning ----------- “ “ “blocking ------------ resto de puertos

Estados Puertoforwarding ---------- root-port, designated-portlistening ------------ estado intermedio (forward delay)learning ----------- “ “ “blocking ------------ resto de puertos

forwardingblocking

dp dp

dp dp dp

rp rp

rp = root-portdp = designated-port

listening/learning

Blocking Forwarding

Listening Learning

Blocking Forwarding

Listening Learning

Forward delay=30 seg. tip. Forward delay=30 seg. tip.

Estado de los puertos

7

27 3714

RSTP802.1w

12

Ejemplo

4.0.4.c4.0.4.b3.0.3.c3.0.3.b2.0.2.c2.0.2.a1.0.1.b1.0.1.aTx-1

cbcbcaba

Puente-4Puente-3Puente-2Puente-1Tiempo

( root-id . cost . bridge-id . port-id )

1.0.1.x 2.0.2.x 3.0.3.x 4.0.4.x

13

Ejemplo

2.0.2.c3.0.3.c

1.0.1.b3.0.3.b

2.0.2.c4.0.4.c

1.0.1.b4.0.4.b

3.0.3.c4.0.4.c

1.0.1.a3.0.3.b4.0.4.b

2.0.2.aRx-1

4.0.4.c4.0.4.b3.0.3.c3.0.3.b2.0.2.c2.0.2.a1.0.1.b1.0.1.aTx-1

cbcbcaba

Puente-4Puente-3Puente-2Puente-1Tiempo

( root-id . cost . bridge-id . port-id )

1.0.1.x 2.0.2.x 3.0.3.x 4.0.4.x

14

Ejemplo

1.0.1.b1.0.1.aTx-2

2.0.2.c3.0.3.c

1.0.1.b3.0.3.b

2.0.2.c4.0.4.c

1.0.1.b4.0.4.b

3.0.3.c4.0.4.c

1.0.1.a3.0.3.b4.0.4.b

2.0.2.aRx-1

4.0.4.c4.0.4.b3.0.3.c3.0.3.b2.0.2.c2.0.2.a1.0.1.b1.0.1.aTx-1

cbcbcaba

Puente-4Puente-3Puente-2Puente-1Tiempo

( root-id . cost . bridge-id . port-id )

1.0.1.x 2.0.2.x 3.0.3.x 4.0.4.x

15

Ejemplo

1.1.4.c1.1.4.b1.1.3.c1.1.3.b1.1.2.c1.1.2.a1.0.1.b1.0.1.aTx-2

2.0.2.c3.0.3.c

1.0.1.b3.0.3.b

2.0.2.c4.0.4.c

1.0.1.b4.0.4.b

3.0.3.c4.0.4.c

1.0.1.a3.0.3.b4.0.4.b

2.0.2.aRx-1

4.0.4.c4.0.4.b3.0.3.c3.0.3.b2.0.2.c2.0.2.a1.0.1.b1.0.1.aTx-1

cbcbcaba

Puente-4Puente-3Puente-2Puente-1Tiempo

( root-id . cost . bridge-id . port-id )

1.0.1.x 2.0.2.x 3.0.3.x 4.0.4.x

16

Ejemplo

1.1.2.c1.1.3.c

1.0.1.b1.1.3.b

1.1.2.c1.1.4.c

1.0.1.b1.1.4.b

1.1.3.c1.1.4.c

1.0.1.a1.1.3.b1.1.4.b

1.1.2.aRx-2

1.1.4.c1.1.4.b1.1.3.c1.1.3.b1.1.2.c1.1.2.a1.0.1.b1.0.1.aTx-2

2.0.2.c3.0.3.c

1.0.1.b3.0.3.b

2.0.2.c4.0.4.c

1.0.1.b4.0.4.b

3.0.3.c4.0.4.c

1.0.1.a3.0.3.b4.0.4.b

2.0.2.aRx-1

4.0.4.c4.0.4.b3.0.3.c3.0.3.b2.0.2.c2.0.2.a1.0.1.b1.0.1.aTx-1

cbcbcaba

Puente-4Puente-3Puente-2Puente-1Tiempo

( root-id . cost . bridge-id . port-id )

1.0.1.x 2.0.2.x 3.0.3.x 4.0.4.x

17

Ejemplo

1.0.1.b1.0.1.aTx-3

1.1.2.c1.1.3.c

1.0.1.b1.1.3.b

1.1.2.c1.1.4.c

1.0.1.b1.1.4.b

1.1.3.c1.1.4.c

1.0.1.a1.1.3.b1.1.4.b

1.1.2.aRx-2

1.1.4.c1.1.4.b1.1.3.c1.1.3.b1.1.2.c1.1.2.a1.0.1.b1.0.1.aTx-2

2.0.2.c3.0.3.c

1.0.1.b3.0.3.b

2.0.2.c4.0.4.c

1.0.1.b4.0.4.b

3.0.3.c4.0.4.c

1.0.1.a3.0.3.b4.0.4.b

2.0.2.aRx-1

4.0.4.c4.0.4.b3.0.3.c3.0.3.b2.0.2.c2.0.2.a1.0.1.b1.0.1.aTx-1

cbcbcaba

Puente-4Puente-3Puente-2Puente-1Tiempo

( root-id . cost . bridge-id . port-id )

1.0.1.x 2.0.2.x 3.0.3.x 4.0.4.x

18

Ejemplo

1.1.4.c1.1.4.b1.1.3.c1.1.3.b1.1.2.c1.1.2.a1.0.1.b1.0.1.aTx-3

1.1.2.c1.1.3.c

1.0.1.b1.1.3.b

1.1.2.c1.1.4.c

1.0.1.b1.1.4.b

1.1.3.c1.1.4.c

1.0.1.a1.1.3.b1.1.4.b

1.1.2.aRx-2

1.1.4.c1.1.4.b1.1.3.c1.1.3.b1.1.2.c1.1.2.a1.0.1.b1.0.1.aTx-2

2.0.2.c3.0.3.c

1.0.1.b3.0.3.b

2.0.2.c4.0.4.c

1.0.1.b4.0.4.b

3.0.3.c4.0.4.c

1.0.1.a3.0.3.b4.0.4.b

2.0.2.aRx-1

4.0.4.c4.0.4.b3.0.3.c3.0.3.b2.0.2.c2.0.2.a1.0.1.b1.0.1.aTx-1

cbcbcaba

Puente-4Puente-3Puente-2Puente-1Tiempo

( root-id . cost . bridge-id . port-id )

1.0.1.x 2.0.2.x 3.0.3.x 4.0.4.x

19

Ejemplo

dpForwarding

dpForwarding

Puerto estado

1.1.4.c1.1.4.b1.1.3.c1.1.3.b1.1.2.c1.1.2.a1.0.1.b1.0.1.aTx-3

1.1.2.c1.1.3.c

1.0.1.b1.1.3.b

1.1.2.c1.1.4.c

1.0.1.b1.1.4.b

1.1.3.c1.1.4.c

1.0.1.a1.1.3.b1.1.4.b

1.1.2.aRx-2

1.1.4.c1.1.4.b1.1.3.c1.1.3.b1.1.2.c1.1.2.a1.0.1.b1.0.1.aTx-2

2.0.2.c3.0.3.c

1.0.1.b3.0.3.b

2.0.2.c4.0.4.c

1.0.1.b4.0.4.b

3.0.3.c4.0.4.c

1.0.1.a3.0.3.b4.0.4.b

2.0.2.aRx-1

4.0.4.c4.0.4.b3.0.3.c3.0.3.b2.0.2.c2.0.2.a1.0.1.b1.0.1.aTx-1

cbcbcaba

Puente-4Puente-3Puente-2Puente-1Tiempo

( root-id . cost . bridge-id . port-id )

1.0.1.x 2.0.2.x 3.0.3.x 4.0.4.x

20

Ejemplo

dpForwarding

rpForwarding

dpForwarding

dpForwarding

Puerto estado

1.1.4.c1.1.4.b1.1.3.c1.1.3.b1.1.2.c1.1.2.a1.0.1.b1.0.1.aTx-3

1.1.2.c1.1.3.c

1.0.1.b1.1.3.b

1.1.2.c1.1.4.c

1.0.1.b1.1.4.b

1.1.3.c1.1.4.c

1.0.1.a1.1.3.b1.1.4.b

1.1.2.aRx-2

1.1.4.c1.1.4.b1.1.3.c1.1.3.b1.1.2.c1.1.2.a1.0.1.b1.0.1.aTx-2

2.0.2.c3.0.3.c

1.0.1.b3.0.3.b

2.0.2.c4.0.4.c

1.0.1.b4.0.4.b

3.0.3.c4.0.4.c

1.0.1.a3.0.3.b4.0.4.b

2.0.2.aRx-1

4.0.4.c4.0.4.b3.0.3.c3.0.3.b2.0.2.c2.0.2.a1.0.1.b1.0.1.aTx-1

cbcbcaba

Puente-4Puente-3Puente-2Puente-1Tiempo

( root-id . cost . bridge-id . port-id )

1.0.1.x 2.0.2.x 3.0.3.x 4.0.4.x

21

Ejemplo

blockedrp

Forwardingdp

Forwardingrp

Forwardingdp

Forwardingdp

ForwardingPuerto estado

1.1.4.c1.1.4.b1.1.3.c1.1.3.b1.1.2.c1.1.2.a1.0.1.b1.0.1.aTx-3

1.1.2.c1.1.3.c

1.0.1.b1.1.3.b

1.1.2.c1.1.4.c

1.0.1.b1.1.4.b

1.1.3.c1.1.4.c

1.0.1.a1.1.3.b1.1.4.b

1.1.2.aRx-2

1.1.4.c1.1.4.b1.1.3.c1.1.3.b1.1.2.c1.1.2.a1.0.1.b1.0.1.aTx-2

2.0.2.c3.0.3.c

1.0.1.b3.0.3.b

2.0.2.c4.0.4.c

1.0.1.b4.0.4.b

3.0.3.c4.0.4.c

1.0.1.a3.0.3.b4.0.4.b

2.0.2.aRx-1

4.0.4.c4.0.4.b3.0.3.c3.0.3.b2.0.2.c2.0.2.a1.0.1.b1.0.1.aTx-1

cbcbcaba

Puente-4Puente-3Puente-2Puente-1Tiempo

( root-id . cost . bridge-id . port-id )

1.0.1.x 2.0.2.x 3.0.3.x 4.0.4.x

22

Ejemplo

blockedrp

Forwardingblocked

rpForwarding

dpForwarding

rpForwarding

dpForwarding

dpForwarding

Puerto estado

1.1.4.c1.1.4.b1.1.3.c1.1.3.b1.1.2.c1.1.2.a1.0.1.b1.0.1.aTx-3

1.1.2.c1.1.3.c

1.0.1.b1.1.3.b

1.1.2.c1.1.4.c

1.0.1.b1.1.4.b

1.1.3.c1.1.4.c

1.0.1.a1.1.3.b1.1.4.b

1.1.2.aRx-2

1.1.4.c1.1.4.b1.1.3.c1.1.3.b1.1.2.c1.1.2.a1.0.1.b1.0.1.aTx-2

2.0.2.c3.0.3.c

1.0.1.b3.0.3.b

2.0.2.c4.0.4.c

1.0.1.b4.0.4.b

3.0.3.c4.0.4.c

1.0.1.a3.0.3.b4.0.4.b

2.0.2.aRx-1

4.0.4.c4.0.4.b3.0.3.c3.0.3.b2.0.2.c2.0.2.a1.0.1.b1.0.1.aTx-1

cbcbcaba

Puente-4Puente-3Puente-2Puente-1Tiempo

( root-id . cost . bridge-id . port-id )

1.0.1.x 2.0.2.x 3.0.3.x 4.0.4.x

23

Ejemplo (2)

D E

C

F

A B 1. Dar direcciones a los puentes.

2. Calcular el árbol (God mode :-))

3. Calculo distribuido (tablas de configuración)

4. Simular un error en (p.e.) línea C-3

1

2

3

4

5 6

TAREAS:

24

Cache TimeOuts

1. Dilema del TimeOut largo (minutos) frente al corto (segundos)

2. Dos TimeOuts configurables por el administrador.

TimeOut largo ---> funcionamiento normalTimeOut corto ---> activado por el mensaje TC (topology change)

25

Formato de los mensajes

Protocol identifierversion

menssage typeTCA, reserved, TC

root-IDcost

bridge-IDport-ID

message agemax. Agehello time

forward delay

Protocol identifierversion

message type

Topology changenotification

Configurationmsg

000

20 [6-40]2 [1-10]15 [4-30]

00128

Message-age=0

Message-age=1

Message-age=2

26

Detalles de implementación

Considerando:1. Que en ausencia de mensajes de configuración en un puerto, el puente asume ser

el ‘designated port’ para ese puerto.2. Que los ciclos son potencialmente desastrosos.

Debe procurarse:Diseñar el árbol de tal manera que si la red se congestiona, el ST funcione correctamente.

¿Como?1. Suficiente potencia en la CPU de los puentes para evitar que el puente descarte tramas.

(Si descarta .... Posible pérdida de mensajes de configuración.)

2. El puente debe poder transmitir mensajes de configuración no importa lo congestionada que este la red.

27

Problemas con el Spanning Tree

1. One way connectivity.

2. Estaciones multi-homed

s

s ss ss ss ss ss s

Tx pero no Rx

28

No tan transparente

1. Mayor probabilidad de pérdida de tramas

Diferencias entre una LAN y una LAN Extendida

2. Mayor retardo ---> mayor tiempo de vida de una trama ---> TimeOuts de aplicaciones3. Mayor probabilidad de errores en trama. (fallos en memoria de puentes)

(mantener CRC si es posible)4. Posibilidad de recepción de tramas desordenadas (reconfiguraciones del árbol)

5. Posibilidad de duplicados (bucles temporales)

Además, si coexisten diferentes tecnologías de LAN ...

6. Las estaciones tienen que controlar cual es el tamaño máximo de trama (MTU)

7. Información específica de una tecnología puede perderse (p.e. Las prioridades en FDDI, TR)

Y además, se asume ...

A. Una estación sólo debe aparecer en un único punto de la red.

B. Una estación destino, especialmente si recibe mucho tráfico, responderá identificandose (y siendolocalizada por los puentes).

C. No habrá alumnos de la FI maliciosos mandando desde una estación “mensajes de desconfiguración”

Diámetro máximo recomendado por IEEE 7 puentes

29

El árbol como topología de interconexión

Internet

G

- Problemas de sobrecarga de tráfico cuanto más cerca de la Raíz.- Solución: Fat Tree- Nuevo problema: Varias tecnologías, no pudiendo utilizar la mejor en las hojas.

UPVnet basada en dorsal 1GE

30