Um Modelo de Encaminhamento Hierárquico Multi-Objectivo em Redes MPLS, com Duas Classes de Serviço - PDF
Download "Um Modelo de Encaminhamento Hierárquico Multi-Objectivo em Redes MPLS, com Duas Classes de Serviço"
Raquel Cabral Stachinski
1 Um Modelo de Encaminhamento Hierárquico Multi-Objectivo em Rede MPLS, com Dua Clae de Serviço Rita Girão Silva a,c (Tee de Doutoramento realizada ob upervião de Profeor Doutor Joé Craveirinha a,c e Profeor Doutor João Clímaco b,c ) a b c DEEC-FCTUC FEUC INESC-Coimbra Jornada do INESC-Coimbra Coimbra, Portugal, 25/Jun/09
2 1. Motivação Reumo 2. Modelo de encaminhamento 3. Generalidade obre a abordagem heurítica de reolução 4. Variante heurítica e meta-heurítica 5. Aplicação do modelo e reultado experimentai 6. Concluõe e trabalho futuro 2
3 1. Motivação Encaminhamento em rede MPLS Na rede multi-erviço actuai, há diferente exigência de Qualidade de Serviço (QoS), com caracterítica muito heterogénea, a coniderar no modelo de encaminhamento. Há vantagen potenciai na formulação do problema de encaminhamento em rede MPLS como problema multiobjectivo. Em [Craveirinha et al,08], dicute-e alguma quetõe de encaminhamento em rede MPLS a um nível conceptual e ao nível de modelo de encaminhamento. Um meta-modelo de encaminhamento multi-objectivo hierárquico formulado ao nível da rede é propoto em [Craveirinha et al,08]. Ete meta-modelo foi aplicado a rede MPLS com dua clae de erviço, QoS (tráfego de mai alta prioridade) e Bet Effort (BE), que contitui o tráfego de mai baixa prioridade. 3
4 2. Modelo de Encaminhamento Conidera-e um modelo de encaminhamento multiobjectivo hierárquico formulado ao nível da rede: Modelo de encaminhamento multi-objectivo hierárquico Primeiro nível: funçõe objectivo aociada ao tráfego QoS, formulada ao nível global da rede Segundo nível: métrica de média de deempenho aociada ao diferente erviço de tráfego QoS e objectivo ao nível global da rede para o tráfego BE (receita eperada) Objectivo de equidade explicitamente coniderado em ambo o nívei de optimização Formulação multi-objectivo: Em cada nível, o objectivo ão potencialmente conflituoo entre i. Formulação hierárquica: Ao avaliar cada um do erviço, tenta-e optimizar a f.o. de 2º nível para ee erviço, etando empre ubjacente a optimização da f.o. de 1º nível, formulada ao nível global da rede para o fluxo de mai alta prioridade. 4
5 Modelo de encaminhamento Conidera-e uma repreentação etocática do fluxo de tráfego aociado a rota explícita, o que permite o cálculo de probabilidade de bloqueio para cada fluxo. A interacçõe entre todo o fluxo de tráfego ão coniderada, apear de e eparar o objectivo QoS do objectivo BE (etão até em nívei diferente). Na rede, conidera-e todo o tráfego exitente, ao invé do que acontece habitualmente, em que e define rede virtuai para o fluxo QoS e para o fluxo BE. Formulação ao nível da rede: a f.o. para um determinado tipo de erviço dependem explicitamente de todo o fluxo na rede. Conidera-e a poibilidade de encaminhamento alternativo, o que tende a er vantajoo para a f.o. de 1º nível. 5
6 Modelo de encaminhamento Problema P-M2-S2 Primeiro nível (QoS Objectivo de rede) max {W Q = receita média total para o tráfego QoS} R min {B Mm Q = máxima probabilidade média de bloqueio para todo R o erviço QoS} objectivo de equidade na rede Segundo nível (QoS Objectivo de erviço) min {B m Q = probabilidade média de bloqueio para o fluxo QoS R de tipo }, S Q min {B M Q = probabilidade máxima de bloqueio para o fluxo QoS R de tipo }, S Q objectivo de equidade para o erviço QoS (BE Objectivo de rede) max {W B = receita média total para o tráfego BE} R 6
7 com W Q = S Q A c w A c : tráfego total tranportado para o erviço w : receita média por cada µ-fluxo ( chamada ) do tipo Toda a f.o. podem er exprea em termo do tráfego oferecido por todo o fluxo f, A(f ) ( S Q U S B ) e a probabilidade de bloqueio ponto-a-ponto correpondente, B(f ). O valore de B(f ) ão calculado com bae num itema multidimenional de Erlang, utilizando o conceito de largura de banda efectiva. B 1 B M Q = max f F {B(f )} B Mm Q = max SQ {B m } W m Q = A(f)B(f) o A f F B = S B A c w 7
8 Modelo de encaminhamento O problema de encaminhamento hierárquico multi-objectivo alternativo aqui coniderado é de difícil tratamento, poi: é batante complexo devido à interdependência entre toda a f.o. (exprea no cálculo de B(f )); é NP-completo. A f.o. em P-M2-S2 ão potencialmente conflituoa. Em particular, no 1º nível, a maximização de W Q pode levar a uma deterioração de B(f ), S Q, para o fluxo de tráfego de pequena intenidade A(f ), o que leva a uma tendência de aumento de B M Q e, conequentemente, B Mm Q. 8
9 3. Generalidade Sobre a Abordagem Heurítica de Reolução A heurítica deenvolvida para o problema P-M2-S2 baeiam-e no cálculo de oluçõe para um problema auxiliar de c.m.c. bi-objectivo. A métrica a minimizar ão o cuto implícito marginai e a probabilidade de bloqueio. Ao minimizar a probabilidade de bloqueio, tende-e a minimizar a probabilidade máxima de bloqueio ponto-aponto B(f ). Ao minimizar o cuto implícito, tende-e a maximizar a receita média total W T. Aim, eta dua métrica ão potencialmente conflituoa. O cuto implícito marginai aociado ao tráfego QoS (BE), c Q(B) ku, reultante da aceitação duma chamada do fluxo f u no arco l k podem er definido como o valor médio de perda de receita em todo o fluxo de tráfego na rede que podem uar o arco l k, devido à diminuição da capacidade diponível nee arco. Aim, eta métrica permite medir o efeito de aceitação duma chamada na rede obre todo o fluxo de tráfego. 9
10 Generalidade obre a abordagem heurítica de reolução O problema auxiliar de c.m.c. bi-objectivo tem dua configuraçõe poívei, conoante e pretende melhorar a receita do tráfego QoS ou do tráfego BE. r( f min ) D ( f ) m Problema P (2) n ( r( f )) = m l r ( f n= 1;2 m k1 =c Q(B) k ; m k2 = -log(1-b k ); D(f ) é o conjunto de caminho admiívei para cada fluxo f, reultante de retriçõe de engenharia de tráfego. O procedimento para pequia e elecção do caminho a er uado pela chamada de cada fluxo de tráfego combina uma oma ponderada da dua f.o. m k1 e m k2 e a definição de regiõe de prioridade obtida a partir de limiare de preferência relacionado com valore aceitávei e requerido para cada f.o. Note-e que a métrica ponderada é uada apena para a geração de oluçõe! A elecção de oluçõe é feita com bae na regiõe de preferência em que a oluçõe e encontram. Define-e um conjunto de procedimento para auxílio à elecção de oluçõe. k ) n k 10
11 Generalidade obre a abordagem heurítica de reolução r(f min ) D (f ) l r(f k Q( B) c k l r( ) k f ( Q(B) Q(B) Q(B) ε ()( log(1 B )) + ε ()c ) ) 1 k 2 k c acc () B 1 C c req () A B 2 c * ( f ) log(1 B * ( f )) log( 1 B req ( )) l r ( k f log(1 ) B k ) log( 1 B acc ( )) 11
12 4. Variante Heurítica e Meta-Heurítica Diferente variante heurítica foram implementada para reolver o problema de encaminhamento hierárquico multiobjectivo: MOR-S2 (Multi-Objective Routing conidering 2 clae of Service), decrita em [Craveirinha et al,07], é uma adaptação dum algoritmo heurítico propoto para reolver um problema mai imple do que P-M2-S2 poi não incluía tráfego de diferente clae de erviço. HMOR-S2 (Hierarchical Multi-Objective Routing conidering 2 clae of Service), decrita em [Girão-Silva et al,09], ua a mema abordagem metodológica de MOR-S2, ma contém alguma adaptaçõe epecífica ao problema em caua, permitindo obter melhore reultado. Em [Girão-Silva et al,08], decreve-e a análie de enibilidade que foi feita à heurítica de bae HMOR-S2. Verificou-e a HMOR-S2 tratava a f.o. de 1º e 2º nível de forma equilibrada. No entanto, verificou-e também que era poível encontrar oluçõe com melhore valore para a f.o. de 1º nível, do que o obtido com a HMOR-S2. 12
13 Variante heurítica e meta-heurítica Diferente técnica foram introduzida na heurítica de bae para tentar encontrar ea oluçõe: HMOR-S2 R (HMOR-S2 with a floating Relaxation) e HMOR-S2 L (HMOR- S2 with a floating barrier or Limit), decrita em [Girão-Silva et al,08], em que e impõe uma relaxação ou uma barreira flutuante ao valor de uma da f.o. de 1º nível. Com a relaxação(barreira), permite-e(exigee) que o valor da f.o. de 1º nível em caua piore(melhore) um certo valor percentual (em função do eu valor corrente). Em [Girão-Silva et al,09a], propõe-e dua variante, HMOR-S2 SA e HMOR-S2 TS, em que e introduziu caracterítica típica da metaheurítica Simulated Annealing e Tabu Search na heurítica de bae. Em [Girão-Silva et al,09b], propõe-e a variante HMOR-S2 PAS (HMOR- S2 with a Pareto Archived Strategy) em que e introduziu um arquivo de oluçõe não-dominada encontrada ao longo da execução da heurítica, ma que devido à extrema exigência da heurítica para a aceitação de nova oluçõe, não foram coniderada como nova oluçõe do problema. Em [Girão-Silva,08], propõe-e a variante HMOR-S2-LS (HMOR-S2 with Load Sharing), que não permitiu obter reultado relevante. 13
14 5. Aplicação do Modelo A heurítica bae e a ua variante foram aplicada a uma rede uada num cao de etudo (ver [Mitra et al,01]), em que e conidera encaminhamento em rede MPLS para dua clae de erviço. Nete cao de etudo, conidera-e um modelo de encaminhamento em rede MPLS, formulado como uma optimização lexicográfica, baeada em MCF (Multicommodity Flow). A repreentação do fluxo de tráfego é determinítica. Faz-e divião de tráfego (traffic plitting) e controlo de aceo para o tráfego BE. A f.o. a optimizar ão a receita W Q e W B. Tenta-e maximizar a receita para o fluxo BE, mantendo o valor óptimo obtido para a receita do fluxo QoS. Inicialmente, numa primeira fae, define-e um modelo determinítico de optimização. Coniderando ó o tráfego QoS na rede, verifica-e qual erá a capacidade reidual da rede. Poteriormente, conidera-e o tráfego BE, que é oferecido a eta rede reidual. Só parte dete tráfego é admitida à rede. Numa egunda fae, adapta-e o modelo determinítico a um ambiente etocático, mantendo invariante a relaçõe de intenidade de tráfego. Eta adaptação é feita para 3 matrize de tráfego ditinta. Com ete modelo de referência, obtém-e valore óptimo para a receita do fluxo QoS, que podem er coniderado limite máximo para o valore de W Q obtido com a heurítica. 14
15 Aplicação do modelo Rede de tete, com informação obre a capacidade do arco [Mbp] Caracterítica do erviço na rede de tete 15
16 Reultado experimentai Etudo analítico: Coniderou-e doi tipo de tete: tete (i), em que a olução inicial é a olução tipicamente utilizada no algoritmo convencionai de Internet: apena caminho de primeira ecolha, c.m.c.; tete (f), em que a olução inicial é a olução obtida apó a execução da heurítica bae. Ete tete ó foram realizado para alguma da variante e têm por objectivo verificar até que ponto ea variante coneguem melhorar a olução final obtida com a HMOR-S2. Etudo imulacional: Coniderou-e uma plataforma de imulação etocática por acontecimento dicreto. É poível avaliar o reultado num ambiente etocático mai próximo da condiçõe reai de funcionamento numa rede. Método de encaminhamento etático: o plano de encaminhamento em cada imulação não muda ao longo da imulação. É o plano de encaminhamento obtido apó o tete (i) ou (f) para cada variante. Método de encaminhamento dinâmico periódico e dependente do etado. A informação recolhida por avaliação periódica do etado da rede é uada para uma ecolha periódica do caminho na rede. Reultado de imulação: valor médio ± emi-intervalo de confiança a 95% 16
17 Algun reultado experimentai Etudo analítico Valore da f.o. de 1º nível para a oluçõe iniciai e finai da heurítica HMOR-S2 e alguma variante A oluçõe finai obtida têm valore de f.o. de 1º nível melhore do que o obtido com o plano de encaminhamento típico da rede Internet (olução inicial), para todo o valore de α. Coniderando a heurítica HMOR-S2 como bae, verifica-e que muita da variante permitem melhorar o valore da f.o. de 1º nível. Comparando o reultado da heurítica bae com o obtido em [Mitra et al,01], verifica-e que a receita W Q repreentam cerca de 99.5% do valore óptimo. A utilização da variante numa egunda fae da execução, ito é, apó a execução da heurítica bae numa primeira fae (verão (f)), permite a melhoria de reultado para a f.o. de 1º nível, para todo o valore de α. Refira-e no entanto que a melhoria é muito ligeira para α=
18 Algun reultado experimentai Etudo imulacional Valore médio e intervalo de confiança a 95% para a f.o. de 1º nível para a HMOR-S2 e alguma variante Na maioria da ituaçõe, o reultado analítico etão fora do intervalo de confiança a 95%, quer para o modelo etático quer para o modelo dinâmico. No entanto, o reultado ão muito próximo. O reultado analítico tendem a er melhore que o reultado imulacionai correpondente. 18
19 Algun reultado experimentai Etudo imulacional Para a heurítica bae, o intervalo de confiança a 95% obtido com o modelo dinâmico incluem ou ão melhore que o valor analítico correpondente para α=0.0; 0.5. Neta ituaçõe de carga mai elevada, o modelo dinâmico é capaz de obter reultado que ultrapaam o reultado antecipado pelo modelo analítico. A diferença entre o reultado analítico e o reultado imulacionai devem-e eencialmente a impreciõe intríneca à reolução analítico-numérica, em particular no que e refere a implificaçõe do modelo de tráfego (que tendem a ub-etimar a probabilidade de bloqueio na rede) e da propagação do erro aociado. O modelo de imulação por acontecimento dicreto confirma a validade do reultado analítico, já que a dicrepância obtida no reultado numérico não afectam o valore relativo da f.o. Refira-e que ao longo do procedimento de optimização do encaminhamento o que é importante é comparar diferente oluçõe de encaminhamento com o memo modelo de tráfego, e não obter valore muito precio para a f.o. O reultado médio obtido com o modelo dinâmico ão melhore ou iguai ao reultado médio obtido com o modelo etático. 19
20 6. Concluõe e Trabalho Futuro Apreentou-e um modelo de encaminhamento hierárquico bi-nível multiobjectivo em rede MPLS, com dua clae de erviço (com diferente prioridade) e diferente tipo de erviço em cada clae. Propô-e diferente heurítica e meta-heurítica para reolução do problema de encaminhamento aociado. Coneguiu obter-e boa oluçõe de compromio para ete problema, quando comparada com a oluçõe do modelo uado como benchmarking. Obteve-e reultado analítico e também reultado imulacionai, coniderando uma plataforma de imulação etocática por acontecimento dicreto, que permite um ambiente etocático mai próximo da condiçõe reai de funcionamento numa rede. O reultado imulacionai foram em linha com o eperado. A principal limitação deta abordagen de reolução é o cuto computacional, que é elevado. Aim, ete método de encaminhamento etá retrito a rede com número limitado de nó do tipo metro-core. Trabalho futuro: Aplicação de divião de tráfego; Exploração doutra técnica meta-heurítica, em particular, algoritmo genético; Aplicação da heurítica e variante a outra rede. 20
21 Referência [Craveirinha et al,07] J. Craveirinha, R. Girão-Silva, J. Clímaco, L. Martin. A hierarchical multiobjective routing model for MPLS network with two ervice clae Analyi and reolution approach. Reearch Report 5/2007, INESC-Coimbra, Oct (A horter verion will be publihed at the Pot-Conference Proceeding of the 23rd IFIP TC7 Conference on Sytem Modelling and Optimization (Cracow, Poland, Jul , 2007), Springer, 2009.) [Craveirinha et al,08] J. Craveirinha, R. Girão-Silva, J. Clímaco. A meta-model for multiobjective routing in MPLS network. Central European Journal of Operation Reearch, 16(1):79-105, Mar [Girão-Silva et al,08] R. Girão-Silva, J. Craveirinha, J. Clímaco. Hierarchical multiobjective routing in MPLS network with two ervice clae Heuritic reolution and enitivity analyi. Reearch Report 8/2008, INESC-Coimbra, Jul [Girão-Silva,08] R. Girão-Silva. Um modelo de encaminhamento hierárquico multi-objectivo em rede MPLS, com dua clae de erviço. Tee PhD, FCTUC, Coimbra, Dec [Girão-Silva et al,09] R. Girão-Silva, J. Craveirinha, J. Clímaco. Hierarchical multiobjective routing in MPLS network with two ervice clae A heuritic olution. International Tranaction in Operational Reearch, 16(3): , May [Girão-Silva et al,09a] R. Girão-Silva, J. Craveirinha, J. Clímaco. Hierarchical multiobjective routing in MPLS network with two ervice clae A meta-heuritic olution. Journal of Telecommunication and Information Technology, 3, [Girão-Silva et al,09b] R. Girão-Silva, J. Craveirinha, J. Clímaco. Hierarchical multiobjective routing in MPLS network with two ervice clae Report on a Pareto Archived Strategy. Reearch Report (Draft verion), INESC-Coimbra, (A horter verion will be preented at the 8th International Conference on Deciion Support for Telecommunication and Information Society (DSTIS 2009), Coimbra, Portugal, Sep. 4-7, 2009.) [Mitra et al,01] D. Mitra, K. G. Ramakrihnan. Technique for traffic engineering of multiervice, multipriority network. Bell Lab Technical Journal, 6(1): , Jan
Encaminhamento Multiobjetivo em Redes MPLS Abordagem exata de resolução de problema com otimização global da rede
Encaminhamento Multiobjetivo em Redes MPLS Abordagem exata de resolução de problema com otimização global da rede Rita Girão-Silva a,b, José Craveirinha b, Teresa Gomes a,b, Lúcia Martins a,b, João Clímaco