Investigação Operacional em Problemas de Telecomunicaçõesapolo.dps.uminho.pt/eventos/semana_IO_2016/semana_IO_amaro_sousa.pdf · •A Investigação Operacional é fundamental

Investigação Operacional em Problemas de Telecomunicações Amaro Fernandes de Sousa

Universidade de Aveiro ([email protected])

Instituto de Telecomunicações ([email protected])

Semana da Investigação Operacional Universidade do Minho, 17 de março de 2016

1

mailto:[email protected]

mailto:[email protected]

Factos

• Liberalização do mercado das telecomunicações • Os operadores de telecomunicações estão sujeitos a concorrência

• Constante aumento, diversificação e agregação dos serviços oferecidos • O tráfego a suportar pelas redes dos operadores é cada vez mais

imprevisível

• Importância dos serviços de telecomunicações no dia a dia das pessoas e das empresas • As redes de telecomunicações têm de ser robustas a falhas

• As questões ambientais e de consumo energético • As redes de telecomunicações deverão ser energeticamente

eficientes 2

Desafios para os operadores

• Minimizar os custos de aquisição (CAPEX) e de operação e manutenção (OPEX) de infraestruturas e equipamentos de rede

• Maximizar a utilização da rede

• Maximizar a capacidade da rede em suportar aumentos imprevistos de tráfego

• Maximizar a sobrevivência da rede a falhas por forma a garantir serviços mínimos em contínuo

• Minimizar os custos associados ao consumo energético dos equipamentos

3

Tipos de problemas

• Desenho/dimensionamento da rede

• O operador precisa de decidir que recursos instalar na rede (tanto nos nós como nas ligações): • para suportar uma determinada matriz de tráfego estimada

• com determinados requisitos (de qualidade de serviço, de sobrevivência, tecnológicos, etc…)

• Objetivo principal: minimizar os custos (CAPEX e/ou OPEX) da rede

• O desenho/dimensionamento é feito quando o operador considera que os recursos instalados na sua rede atual não serão suficientes num futuro próximo

4

Tipos de problemas

• Engenharia de tráfego

• Os recursos da rede estão instalados

• O operador precisa de decidir como atribuir os recursos a cada fluxo de tráfego

• Objetivos possíveis: • maximizar a utilização da rede

• maximizar a robustez da rede a variações imprevistas de tráfego

• otimizar a qualidade de serviço proporcionada

• minimizar o consumo de energia

• uma combinação das anteriores

• A engenharia de tráfego pode ser online, periódica ou planeada

5

Exemplos descritos de seguida

• Desenho/dimensionamento de Redes

• Desenho de Redes MPLS/WDM com Sobrevivência e Restrições de Salto

• Desenho de Redes MPLS com Encaminhamento OSPF

• Engenharia de Tráfego

• Balanceamento de Tráfego para 2 Serviços Diferenciados

• Encaminhamento Energeticamente Eficiente

6

Desenho de Redes MPLS/WDM com Sobrevivência e Restrições de Salto • Considere-se uma rede MPLS sobre uma rede ótica WDM

7

E

C

WDM OXC

E MPLS Edge LSR

C MPLS Core LSR

WDM Lightpath

E

E

Fiber

L. Gouveia, et al., “MPLS over WDM Network Design with Packet Level QoS Constraints based on ILP Models”, IEEE INFOCOM , 2003

Desenho de Redes MPLS/WDM com Sobrevivência e Restrições de Salto • Para a rede MPLS, os Lightpaths da rede ótica funcionam

como ligações ponto-a-ponto

8

E

C

E MPLS Edge LSR

C MPLS Core LSR

MPLS LSP

E

E

Lightpath Connection

L. Gouveia, et al., “MPLS over WDM Network Design with Packet Level QoS Constraints based on ILP Models”, IEEE INFOCOM , 2003

Desenho de Redes MPLS/WDM com Sobrevivência e Restrições de Salto

9

• Parâmetros de entrada: • Dada a rede ótica WDM e a localização dos Edge LSRs

• Dada uma matriz de tráfego entre os Edge LSRs

• A solução inclui D percursos de encaminhamento, disjuntos nos nós, entre cada par de Edge LSRs

• Cada percurso de encaminhamento é limitado a H saltos

• O comprimento de cada Lightpath é limitado a L

• Determinar: • Os Core LSRs e sua localização

• Os Lightpaths necessários e sua capacidade

• Objetivo: • minimizar o custo total da configuração da rede (Core LSRs +

Lightpaths)


10

• Mecanismos de Sobrevivência

• Path diversity: • Cada fluxo de tráfego é dividido igualmente por D percursos

disjuntos nos nós

• Se um Lightpath ou um LSR falhar, [ (D – 1) / D ] 100% do fluxo está protegido

• Path protection: • Para cada fluxo de tráfego, estabelecem-se D percursos de

encaminhamento disjuntos nos nós

• O fluxo é dividido igualmente por D – 1 percursos

• O último percurso é usado quando um dos outros falha

• Existe 100% de proteção para falhas individuais

• Quanto maior o D, menores os recursos adicionais necessários


11

• Grafo expandido: as arestas representam percursos de comprimento mínimo na rede WDM menor que L

• Redes de Teste (L = 2000 km):

L. Gouveia, et al., "Hop-Constrained Node Survivable Network Design: An Application to MPLS over WDM", Networks and Spatial Economics, March 2008


12

• O custo adicional é menor com Path Diversity (mas a proteção é também menor)

• Com Path Protection, o custo adicional é menor com D = 3

L. Gouveia, et al., "Hop-Constrained Node Survivable Network Design: An Application to MPLS over WDM", Networks and Spatial Economics, March 2008

Desenho de Redes MPLS com Encaminhamento OSPF • Considere-se uma rede MPLS

13

1

2

5

4

6

Edge LSRs

Core LSR

3

Fluxo de tráfego

Par de nós em que é possível estabelecer uma ligação

Desenho de Redes MPLS com Encaminhamento OSPF • Considere-se uma rede MPLS com encaminhamento OSPF:

• São atribuídos pesos às ligações

• Os percursos de encaminhamento são determinados pelos percursos de peso mínimo

14

1

2

2 1

1 1

1

2

Desenho de Redes MPLS com Encaminhamento OSPF

15

• Parâmetros de entrada: • Dada a localização dos Edge LSRs e dos Core LSRs

• Dada uma matriz de tráfego entre os Edge LSRs

• Dados os custos e capacidades de todas as possíveis ligações

• Determinar: • As ligações a estabelecer na rede

• Os pesos OSPF a adotar em cada ligação

• Objetivo: • minimizar o custo total da configuração da rede


16

• Redes de Teste:

C. Lopes, et al., “Combined Link Dimensioning and Weight Assignment of Minimum Weight Routing Networks”, NGI 2005

Rede A Rede B


17 • O encaminhamento OSPF impõe uma penalização média

de apenas 1.78% no custo da rede quando comparado com o encaminhamento estabelecido por gestão

Balanceamento de Tráfego para 2 Serviços Diferenciados

18

1

2

4 5

3

Serviço Gold (par de nós: fluxo): 1 – 2 : 2 2 – 5 : 1 3 – 4 : 1 Serviço Standard (par de nós: fluxo): 2 – 3 : 4 2 – 4 : 3 3 – 5 : 4

O objetivo é: • escolher um percurso de encaminhamento para cada

fluxo • minimizar a ligação com mais carga

Capacidade das ligações: 10


19

1

4 5

3

Serviço Gold 1 – 2 : 2 2 – 5 : 1 3 – 4 : 1 Serviço Standard 2 – 3 : 4 2 – 4 : 3 3 – 5 : 4

2 2

1

1

1 3

3

4

4

• Em ambos os serviços a pior carga é de 50% • A rede fica congestionada para ambos os serviços se

todos os fluxos crescerem (1 – 0.5)/0.5 = 100%

• Sem diferenciação de serviço


Pior carga 50% 10% 50%



20

Serviço Gold 1 – 2 : 2 2 – 5 : 1 3 – 4 : 1 Serviço Standard 2 – 3 : 4 2 – 4 : 3 3 – 5 : 4

• A rede fica congestionada para o serviço Standard se todos os fluxos crescerem (1 – 0.8)/0.8 = 25%

• A rede fica congestionada para o serviço Gold se todos os fluxos crescerem (1 – 0.4)/0.4 = 150%

• Com diferenciação de serviço




1

4 5

3 2 4

7

1

2

1

8

3


21

• Parâmetros de entrada: • Dados os nós da rede e as capacidades das ligações entre nós da

rede

• Dada uma matriz de tráfego para cada um dos 2 serviços

• Dado uma diferença máxima de entre a pior carga de cada serviço

• Determinar: • O percurso de encaminhamento de cada fluxo de tráfego

• Objetivo: • minimizar a carga máxima de cada serviço


22

• Rede de Teste:

A. de Sousa, et al., “Load balancing optimization of telecommunication networks with two differentiated services”, Electronic Notes in Discrete Mathematics, June 2013

14

1

2

3

4

5

7

6

12

9

8

10

11

13

16

20

1918

15

22

21

23

26

25

24

17


23 • Percentagem de tráfego Gold cresce de 100 para 101 para 102

• Redes NSF’ com ligações de capacidade diferente

A. de Sousa, et al., “Load balancing optimization of telecommunication networks with two differentiated services”, Electronic Notes in Discrete Mathematics, June 2013

= 1 = 0.3


24

• Instância NSF100 ( = 0.0)


25



26


Encaminhamento Energeticamente Eficiente

27 R. Bolla, et al., “Enabling Backbone Networks to Sleep”, IEEE Network, March/April 2011

• O tráfego suportado não é constante

• Por exemplo, o tráfego apresenta padrões de variação periódicos ao longo do dia.


28

• Assumindo que os equipamentos podem ser configurados em modo adormecido

• Parâmetros de entrada: • Dada uma rede de telecomunicações e os consumos energéticos

(em modo operacional e em modo adormecido) de cada elemento

• Dado um conjunto de períodos horários

• Dada uma matriz de tráfego por período horário

• Determinar: • O percurso de encaminhamento de cada fluxo de tráfego

• Objetivo: • minimizar a energia total consumida pela rede


29

R. Bolla, et al., “Enabling Backbone Networks to Sleep”, IEEE Network, March/April 2011

• Mesmo para volumes de tráfego altos (de 75%), o número de ligações adormecidas é significativo obtendo-se ganhos superiores a 40%

Em conclusão • A Investigação Operacional é fundamental para os

operadores de telecomunicações

• A minimização dos custos permite tarifas mais apelativas • Aumento do número de clientes

• A gestão ótima dos recursos permite o aumento do tráfego suportado e/ou robustez a variações de tráfego • Maior receita

• Maior satisfação dos clientes

• A robustez da rede permite assegurar níveis de serviço quando há falhas • Requisito de clientes empresariais

• Maior satisfação dos clientes

• A gestão energeticamente eficiente permite minimizar os custos e uma maior responsabilidade ambiental

30

Parabéns pelos 40 anos do

Departamento de Produção e Sistemas Universidade do Minho

Obrigado!

31

Documents

Investigação Operacional em Problemas de Telecomunicaçõesapolo.dps.uminho.pt/eventos/semana_IO_2016/semana_IO_amaro_sousa.pdf · •A Investigação Operacional é fundamental