UNIVERSIDAD DE SANTIAGO DE CHILEFACULTAD DE INGENIERIA

DEPARTAMENTO DE INGENIERIA ELECTRICA

MAGÍSTER EN TELECOMUNICACIONES

.TEMA:

Algoritmos de enrutamiento para redes ópticas basadas en Multiplexión por División de Longitud de Onda Densa: DWDM

PROFESOR GUÍA:DR. FIDEROMO SAAVEDRA G.

CÉSAR LAGOMARSINO BARRIENTOS

2008

Objetivo General

• Evaluar algoritmos de enrutamiento y asignación de longitud de onda, sobre una red óptica DWDM, donde peticiones de tasas entre los pares de nodos fuente-destino, son arregladas asignando rutas y longitudes de onda sobre lightpaths, mediante la técnica de tráfico Grooming

Objetivos Específicos

• Determinar rutas y longitudes de onda mediante algoritmos RWA

• Formular el problema de tráfico Grooming• Evaluar algoritmos bajo una demanda de

tráfico dinámico por medio de métricas de rendimiento para establecer lightpaths en la topología virtual de la red

ORIGEN DEL ENRUTAMIENTO Y ASIGNACIÓN DE LONGITUD DE ONDA

Capa de conmutación de Paquetes

IP-Router Gig Eth Swtich

SDH/SONET

Dominio TDM

Anillo DWDMAdd-Drop

Dominio DWDM

NNI

OXCs

Tributarios:OC-3/STM-1OC-12/STM-4OC-48/STM-16

Tributarios:N x OC-48/STM-16N x OC-196/STM-64

Dominio DWDM

Dominio IP capa 3 Dominio IP capa 2

UNI

Vertical:Capas, Granularidad

Horizontal:Dominios

Red Malla de Enrutamientoy asignación de longitud de onda

Capa de conmutación de Óptica

Conmutación Óptica

OXCs

λ2

OBJETIVO1- Minimizar la Probabilidad de bloqueo2.-Maximizar las peticiones de conexión

usando un mínimo de longitudes de onda

λ1

Restricción de continuidad de longitud de onda

Nodo de Conmutación Lightpath sobre λ1

Lightpath sobre λ2Nodo de Acceso

Control y Gestión de la red OXC

OXCs

λ2

λ1

Plano de Control y Gestión

Controlados de Conexiones: OCC

Técnica de Tráfico Grooming

Red de Acceso

Sub red IP/MPLS

OXC

LSR

LSR: Label SwitchingRouter

Sub red IP/MPLS

LSR

OC-48

OC-1

OC-3

OC-12

OC-12

OXC

OXC

OXC

OXC

OC-1

OC-3

ConexiónSub red IP/MPLSLightpath

DEMANDA DE TRÁFICO:

Peticiones de baja granularidad

TRÁFICOGROOMING

TOPOLOGÍA VIRTUAL

ASIGNACIÓN DELONGITUD DE ONDA

ENRUTAMIENTO

TOPOLOGÍA FÍSICA

Modelo de trafico de dos capas

Topología Virtual

Topología Física

Fibra Lightpaths

OC-X

Grado de multiplexión “C”o factor Grooming

Cdssaltounenconexionesds

W ≤∑,

)),((yxC =

sd

∑tdsy

tysdSyMaximizar

,,,

,:

{ }48,12,3,1∈y

{ }sdyt ,,1 Α∈

049397249033839301977319023287230

, =Α sdy

=01yt

sdS

OC-Y

Petición deconexión

Conexión

ALGORITMOS RWA

• FAR: Enrutamiento alternado fijo (FixedAlternate Routing)

• First Fit: Primera Encontrada (First Fit)

• LU: Menos Usada (Least Used)

• MU: Más Usada (Most Used)

• R : Orden Aleatorio (Random)

FAR: Fixed Alternate Routing(Enrutamiento fijo alternado)

OXC3

OXC2

OXC10

OXC6

OXC4

OXC8

21-2-101-10

21-7-91-9

31-7-9-81-8

11-71-7

21-5-61-6

31-7-9-61-6

31-2-10-61-6

11-151-5

31-2-3-41-4

21-2-3 1-3

11-21-2

CostoRutaTrayecto

OXC1

OXC5

OXC7 OXC9

Rutas candidatas: Rp1, Rp2, Rp3,…, RpK

La cuenta de saltos y el retardo usados como métrica de costo.

FAR en tráfico Grooming

OXC2

OXC10

OXC6

OXC4

OXC8

OXC1

Transporte de una conexión desde el nodo 1 a nodo 6

OXC3

Ruta candidata:

OXC1

Tráfico de Salto SimpleOXC2 OXC10 OXC6

OXC7 OXC9

OXC5

lightpath 1- 6

Tráfico Multi - SaltoOXC1 OXC2 OXC10 OXC6Nodo Grooming

Nodo no Grooming lightpath 1-10 y lightpath 10-6

OXC1

OXC2

OXC3

OXC4

OXC6

OXC5

OXC7

OXC9

OXC11

Algoritmos de Asignación de longitud de onda

w0

w0

w1

w1

w1

w1

w2

w3

w3

w3

w3

4W3

1W2

5W1

2W0

Numero de enlaces usadas

Longitud de onda Wn

LU: busca en el orden W2, W0, W3 y W1 Selecciona menos usada: W2

R: busca en el orden, por ejemplo, W1, W2, W3 y W0 Selecciona: primera libre encontrada W2

Petición de conexión para la

ruta R desde OXC1 a OXC9Sobre R, W0, W1, W2, y W3

están libres w1

Trayecto: R

MU: busca en el orden W1, W3, W0 y W2

Selecciona mas usada: W1

FF: busca en el orden W0, W1, W2 y W3 Selecciona primera libre encontrada: W0

Modelado del tráfico

• Demanda de tráfico dinámico, las peticiones de conexión de llegada y salida de un nodo OXC de una red, son de forma aleatoria.

• Los lightpath una vez establecidos permanecen por un tiempo finito

• Las peticiones llegan dinámicamente a los nodos de acuerdo a un proceso Poisson: M/M/1

• Las llamadas aplicadas en el tiempo están exponencialmente distribuidas

Tasas de llegada λ(llamadas/unidad de tiempo)

[ ]!

)()(ntentNPnt λλ−

==

OXC1

OXC2 OXC4

OXC5

Disciplina de llamadas :FIFO

λ(llamadas/unidad de tiempo)Nodo 2 a Nodo 5: 11 (llamadas/ut)

Probabilidad de bloqueo versus

Carga de la red

OXC3

Red propuesta: NSFNET (National ScienceFoundation Net)

OXC7

OXC1OXC3

OXC5

OXC6

OXC8

OXC9

OXC10

OXC11

OXC12

OXC14

Nodo sin conversión de longitud de onda

Nodo con conversión de longitud de onda

OXC13

OXC2

Nodo Grooming Salto Simple OXC4

Nodo Grooming Multi-Salto Total

Tráfico de la Red

Matriz de Capacidades sobre los enlaces: W longitudes de onda

Matriz de Tasa de llegadas λ (llamadas/Unidad de tiempo)

Caso 1: Nodos sin conversión de longitud de onda

OXC7

OXC1

OXC3

OXC5

OXC6

OXC8

OXC9

OXC10

OXC11

OXC12

OXC14

Nodo sin conversión de longitud de onda

OXC13

OXC2

OXC4

Nodos sin conversión de longitud de onda

Restricción de continuidad

0,2240,1980,2190,190

Caso 1: Nodos con conversión de longitud de onda

OXC1

OXC2

OXC3

OXC4

OXC5

OXC6

OXC7

OXC8

OXC9

OXC10

OXC11

OXC12

OXC13

OXC14

Nodo con conversión de longitud de onda

Caso 1: Nodos con conversión de longitud de onda

0,135

Caso 1: Nodos con capacidad de tráfico Grooming

OXC1

OXC3

OXC5

OXC6

OXC8

OXC9

OXC10

OXC11

OXC12

OXC13

OXC14

Nodo Grooming Salto Simple

OXC7

OXC2

OXC4Nodo Grooming Multi-Salto Total

Caso 1: Nodos con capacidad de tráfico Grooming

0,0820,0640,0790,061

Caso 2: Capacidad uniforme, nodos con capacidad de tráfico Grooming

OXC7

OXC1

OXC3

OXC5

OXC6

OXC8

OXC9

OXC10

OXC11

OXC12

OXC13

OXC14

Nodo Grooming Salto Simple

OXC2

OXC4Nodo Grooming Multi-Salto Total

Caso 2: Capacidad uniforme, nodos con capacidad de tráfico Grooming

0,0830,0650,0780,065

Equidad (Fairness) Caso 1. Nodos sin conversión de longitud de onda

0,0870,0650,0830,058

Equidad (Fairness) Caso 1. Nodos con capacidad de tráfico Grooming

0,0360,0210,0340,018

CONCLUSIONES

• La evaluación de los algoritmos RWA

• Convergencia de las medidas de probabilidad de bloqueo para carga alta de la red

• Equidad en los enlaces, promedio probabilidad de bloqueo versus fairness

• Optimización del rendimiento de los algoritmos RWA

CONCLUSIONES

• La demanda en el núcleo de la red.

• Transporte de tráfico IP sobre WDM.

• La técnica de Tráfico Grooming

CONCLUSIONES

• Un óptimo rendimiento de los algoritmos no es fácil, ya que depende de varias variables asociadas a la red, tipo de carga, disponibilidad de recursos y otros factores que permanecen en investigación actualmente

• El rendimiento de los algoritmos, permite un adecuado transporte de la red DWDM mediante la técnica de tráfico Grooming