BR112013003488A2 - engenharia automatizada de tráfego para comutação de rótulo de múltiplos protocolos (mpls) com utilização de link como feedback em um mecanismo de decisão - Google Patents

Abstract

ENGENHARIA AUTOMATIZADA DE TRÁFEGO PARA COMUTAÇÃO DE RÓTULO DE MÚLTIPLOS PROTOCOLOS (MPLS) COM UTILIZAÇÃO DE LINK COMO FEEDBACK EM UM MECANISMO DE DECISÃO. Um método que proporciona em um nó de uma rede de comutação de rótulo de múltiplos protocolos (MPLS) para uma distribuição de carga melhorada, incluindo determinar um primeiro conjunto de um ou mais caminhos mais curtos entre cada par de nó MPLS, selecionar pelo menos um primeiro caminho mais curto aplicando processo de decisão de algoritmo comum, calculando um valor de utilização de link para cada link da rede MPLS, determinando um segundo conjunto de um ou mais caminhos mais curtos entre cada um dos pares de nós MPLS, gerando um valor de utilização de caminho para cada caminho mais curto no segundo conjunto de caminhos mais curtos com base nos valores de utilização de link correspondentes a cada um dos caminhos mais curtos e selecionando um segundo caminho mais curto do segundo conjunto de caminhos mais curtos com base no valor de utilização de caminho, por meio do que a seleção dos segundo subconjunto na luz de utilização de caminho minimiza o desvio padrão de distribuição de carga através da rede MPLS inteira.

Description

ÍWS ENGENHARIA AUTOMATÍZADA DE TRÁFEGO PARA COMUTAÇÃO DE RÓTULO DE MÚLTIPLOS PROTOCOLOS (MPLS) COM UTILIZAÇÃO DE LINK COMO FEEDBACK EM UM MECANISMO DE DECISÃO

REFERÊNCIA CRUZADA AO PEDIDO CORRELATO 5 É feita referência cruzada a um pedido de patente copendente em nome de David lan Allen e Scott Andrew Mansfield para "ENGENHARIA AUTOMATIZADA DE TRÁFEGO PARA 802 IAQ COM BASE NO EMPREGO DE UTILIZAÇÃO DE LINK COMO FEEDBACK NO MECANISMO DE DECISÃO' depositado na mesma data da presente invenção e de propriedade comum. O pedido de referência cruzada é incorporado presentemente como 10 referência.

CAMPO DA INVENÇÃO As modalidades da presente invenção referem-se a um método e a um aparelho para melhorar a distribuição de carga em uma rede. Especificamente, as modalidades da invenção referem-se a um método para espalhamento de carga em redes de comutacão de P 15 rótulos de múitiplos protocolos (MPLS) com múltipios caminhos de custo igualitário entres os nós na rede.

TÉCNICA ANTERIOR ' A distribuição de carga ou espalhamento de carga é um método pelo qual a banda larga é mais efetivamente utilizada e o desempenho global é melhorado em uma rede. As 20 técnicas de distribuição de carga automatizada e espalhamento de carga lançadas atualmente operam com apenas uma vista muito local, estas técnicas de distribuição de carga e espalhamento de carga apenas consideram o número de caminhos ou as seguintes porções de deslocamento de sinal (hops) para uma dada destinação e não consideram a distribuição global de tráfego na rede. 25 Múltiplos caminhos de custo igualitário (ECMP) é uma estratégia comum para espalhamento de carga de tráfego de transmissão Única (unicast) em redes roteadas e que é utilizada onde a decisão de como encaminhar um pacote para uma dada destinação pode resolver por qualquer um dos múltiplos caminhos de "custo igualitário", que formam um impasse pelo caminho mais CúftO quando são realizados cálculos de uma base de dados. O 30 ECMP pode ser utilizado em conjunção com a maioria dos protocolos de roteamento de transmissão única e os nós são equipados com o equipamento de suporte de plano de dados, tendo em vista se basear em uma decisão por hop que é local para um roteador únlco que assume uma recepção promíscua e uma mesa encaminhamento completo em cada nó intermediário. Utilizando ECMP em qualquer dado nó em uma rede, a carga é 35 divida pseudo-un'fomemente através de um conjunto de próximos hops de custo igualitário. Este processo é implementado independentemente em cada hop da rede onde existir mais de um caminho para uma dada destinação.

Em muitas implementações, quando a presença de múítiplos próximos hops de custo igualitário é encontrada, cada pacote é inspecionado para uma fonte de entropia tal como um cabeçalho de Protocojo de lntemet (lP) e um fragmento (hash) de módulo de informação " de cabeçalho do número de caminhos é utilizado para selecionar o próximo hop para o 5 pacote particular. Para tráfego altamente agregado, este método irá distribuir em média a » carga igualmente em topoIogias regulares (i.e., topologias simétricas) e oferece algum inelhoramento nas topologias menos regulares. A comutação de rótulo de múltiplo protocolo (MPLS) é uma combinação de um plano de dados e tecnologia de plano de controle utilizada para encaminhar tráfego através da 10 rede utilizando um arranjo (lookup) de rótulos e tradução (referido como "swapping'). Cada nó da rede suporta MPLS revisando o tráfego recebido pela rede e encaminhando este tráfego com base em seu rótulo, o rótulo é normalmente traduzido ou "swapped" em cada deslocamento de sinal (hop). As redes MPLS pode me]horar a distribuição do tráfego roteado na rede utilizando 15 por hop o ECMP para distribuir ou espalhar uma carga através de caminhos de custo · igualitário. Em redes MPLS, um caminho de comutação de rótulo (LSP) é preparado em cada hop próximo por todo nó na rede. O caminho de encaminhamento para uma dada " destinação na rede é calculado utilizando o primeiro algoritmo de caminho maís curto (SPF) em cada nó na rede, mapeado para as junções de rótulo Iocais no nó, e a conectividade 20 resultante aparece como uma maíha de múltiplo ponto para múltiplo ponto. NÓs individuais quando apresentados com o tráfego destinado para múltiplos caminhos de custo igualitário utilizam informação de carga conio parte do mecanismo de seleção de caminho para maximizar a regularidade da distribuição de fluxo através de um conjunto de caminhos. O estabelecimento do LSP de múltiplo-ponto a múltiplo-ponto ê automático. 25 O protocolo de distribuição de rótulo (LDP) ou protocolo similar é utilizado para sobre-provisionar um conjunto completo de junções de rótulos para todos as possÍveis dasses de equivalência de encaminhamentos na rede, e então, cada roteador de comutação de rótulo (LSR) independentemente computa o conjunto de hops próximos para cada encaminhamento de classe de equivalência e seleciona quais junções de rótulos será 30 realmente utilizada em qualquer dado momento.

SUMÁRIO É proporcionado um método em um nó de uma rede de múltiplo prctocob de comutação de rótulo (MPLS) para melhorar a distribuição de carga, em que o nó é um de uma pluralidade de nós na rede MPLS cada um dos quais proporciona um processo de 35 decisão de algoritmo comum para produzir árvores de caminhos de mais curto custo minimo, o nó inclui uma base de dados de topologia da rede MPLS, em que a topologia da rede MPLS inclui uma pluralidade de nós e links entre qs nós, o método compreende as etapas de: determinar um primeiro conjunto de um ou mais caminhos mais curtos entre cada par de nó MPLS na rede MPLS executando um algoritmo de busca de menor caminho na topologia da rede MPLS armazenada na base de dados de topologia; selecionar pelo menos " um primeiro caminho mais curto do primeiro conjunto de caminhos mais curtos para cada 5 par de nós MPLS, aplicando o processo de decisão de algoritmo comum; calcular um valor « de utilização de link para cada link da rede MPLS com base na contagem de caminhos mais curtos selecionado que trânsito em cada link; determinar um segundo conjunto de um ou mais caminhos mais curtos entre cada par de nó MPLS na rede MPLS executando o algoritmo de busca de menor caminho na topologia da rede MPLS armazenada na base de 10 dados de topologia; gerar um valor de utilização de caminho para cada caminho mais curto no segundo conjuntc de um ou mais caminhos mais curtos com base nos valores de utilização de link correspondente a cada caminho mais curto; selecionar um caminho mais curto do segundo conjLlnto de um ou mais caminhos mais curtos na base do valor de utiiização de caminho, em que a seleção utiliza o processo de decisão de algoritmo comum 15 quando os múltiplos caminhos mais curtos tendo valores de utilização de caminhos

- igualitários èstàj presentes no conjunto de um ou mais caminhos mais curtos; e armazenar pelo menos o primeiro caminho mais curto e os segundos caminhos mais curtos para cada " par de nó MPLS em uma base de dados de informação de rótulo, em que a base de dados de informação de rótulo indica onde encaminhar o tráfego de entrada no nó MPLS, por onde 20 a seleção dos segundos subconjuntos à luz da utilizaçãô de caminho minimiza o desvio padrão da distribuição e carga através da rede MPLS inteira.

Um elemento de rede para distribuição de carga melhorada em uma rede de múltiplo protocolo de comutação de rótulo (MPLS) que inclui o elemento de rede, em que o elemento de rede é um de uma pIuralidade de nós na rede MPLS, em que uma topologia da rede 25 MPLS inclui uma pluralidade de nós e links entre os nós, o elemento de rede compreende: uma base de dados de topologia para amazenar informação de link para cada Iink na rede MPLS; uma base de dados para amazenar informação de rótulo para cada porta do elemento de rede; em que a base dados de informação de rótulo indica onde encaminhar a classe de equivalência (FEC) que entra no elemento de rede; um processadQr de controle 30 acoplado na base de dados de topologia e a base de dados de infomação, o processador de rede está acoplado na base de dados de topologia e a base de dados de informação de rótulo, o processador de rede é configurado para processar o tráfego de dados, em que o processador de rede compreende: um módulo de gerenciamento de MPLS configurado para encaminhar tráfego de dados sobre caminhos de comLltação de rótubs (LSP's) ria rede

35 MPLS; um módulo de busca de caminho mais curto configurado para deteminar pelo menos um caminho mais curto entre cada par de nós de MPLS na rede MPLS executando um algoritmo de busca de caminho mais curto na base de dados de topologia, em que o módulo de busca de caminho mais curto é configurado para enviar, para cada um dos pares de nós MPLS com uma pluralídade de caminhos mais curtos e de custo Ígualitário em um módulo de distribuição de carga; um módulo de classificação configurado para ordenar cada uma " das pIuralidades de caminhos mais curtos de custo igualitário com base no valor de 5 utiiização de caminho dos valores de utilização de Íink associados com cada caminho na b pluralidade de caminhos mais curtos de custo igualitário; e o módulo de distribuição de carga configurado para selecionar, da pIuralidade de caminhos mais curtos de custo igualitário recebida, um primeiro subconjunto da plumlidade de caminhos mais curtos de eusto igualitário para que o par de nós MPLS a ser utilizado para compartilhar carga de 10 tráfego de dados entre o par de nós MPLS e para selecionar, com base no valor de utilização de caminho, um segundo conjunto da pluralidade de caminhos mais curtos de custo igualitário para que o par de nós MPLS a ser utilizado possa compartilhar a carga de tráfego de dados com o primeiro subconjunto para que o par Ethemet Biidge, por meio da seleção do segundo subconjunto na luz do valor de utilização de caminho, minimiza o desvio 15 padrão da distribuição de carga através da rede MPLS inteira. > BREVE DESCRIÇÃO DAS FIGURAS A presente invenção é ilustrada por meio de exemplos e, não de maneira limitativa, " pelas figuras apensas em que referências comuns indicam elementos similares. Deve ser notado que referências diferentes a "uma" modalidade na presente descrição não 20 necessariamente na mesma modalidade, e tais referências significam pelo menos uma. Além disso, quando uma apresentação, estrutura ou característica em particular em conexão com outras modalidades se ou não explicitamente descritos. A Figura 1 ilustra um diagrama de um exemplo de uma topologia de rede. A Figura 2 ilustra um diagrama de uma modalidade de elemento de rede que 25 implementa engenharia de tráfego automático para uma rede de múltiplo protocolo de comutação de rótulo (MPLS). A Figura 3 ilustra um fluxograma de um modalidade de um processo de distribuição de carga que inclui engenharia tráfego automatizada que incorpora o uso de uma utilização de link como feedback dentro de um mecanismo de decisão.

30 A Figura 4 ilustra um fluxograma de uma modaiidade de um processo para gerar uma mensagem de mapeamento de rótulo como parte do protocolo de distribuição de rótulo. A Figura 5 ilustra um diagrama de um exemplo de uma topologia de rede de múltiplo- ponto a múltiplo-ponta A Figura 6 ilustra um diagrama de um outro exemplo de uma topologia de rede de 35 múltipío-ponto a múlÜplo-ponto. A Figura 7 ilustra um diagrama de uma modalidade de um mapeamento de um conjunto de pseudo-linhas na rede de comutação de pacote subjacente para suportar operações, administração e manutenção (OAM) na rede MPLS.

DESCRIÇÃO DETALHADA DA INVENÇÃO Na descrição a seguir, serão proporcionados numerosos detalhes específicos. " Entretanto, é entendldo que as modalidades da invenção podem ser praticadas sem tais 5 detalhes especificos. Nos outros casos, circuitos, estruturas e técnicas bem conhecidas não b foram mostrados em detalhe para não prejudicar o entendimento desta descrição. Será apreciado, entretanto, por aqueles versados na técnica, que a invenção pode ser praticada sem tais detaihes específicos. Aqueles versados na técnica com as descrições indusas, serão capazes de proporcionar a funcionalidade apropriada sem experimentação indevida. 10 As modalidades incluem um processo de decisão básico com propriedades específicas incluindo as propriedades em que o processo irá sempre resolver por um único caminho é independente da ordem ou direção da computação, e possui uma propriedade de localidade tal que um impasse para qualquer porção do caminho considerado pode ser resolvido sem ter que considerar o caminho inteiro. 15 As operações dos diagramas de fluxo serão descritas com referência à modalidade - exemplificativa da Figura 2. Entretanto, deve ser entendido que as operações dos diagramas de fluxo podem ser realizadas pelas modalidades da invenção que 'não aquelas discutidas com referência á Figura 2, e a modalidade discutida com referência a Figura 2 pode realizar operações diferentes daquelas discutidas com referência aos diagmmas de fluxo das 20 Figuras 3 e 4. As Figuras 1 e 5-7 proporcionam exemplos de topologias e cenários que ilustram a implementação dos princípios e estruturas das Figuras 2,3 e 4. As técnicas mostradas nas figuras podem ser proporcionadas utilizando código e dados armazenados e executados em um ou mais dispositivos eletrônicos (por exemplo, estação terminal, um elemento de rede, etc.). Tais dispositivos eletrônicos amazenam e 25 comunicam (internamente e/ou com oLltros dispositivos eletrônicos sobre uma rede) código dados utilizando mídia não transitória lida por máquina ou lida por computador, tal como midia de armazenamento não transitório iido por máquina ou lido por computador (por exemplo, discos magnéticos; discos óticos; memória de acesso aleatório; memória de leitura única; di$positjvQs de memória flash; e memória de mudança de fase). Além disso, tais ,30 dispositivos eletrônicos norma|mente incluem um conjunto de um ou mais processos acoplados em um ou mais outros componentes, tais como um ou mais dispositivos de armazenamento, dispositivos de input/output de usuários (por exemplo, teclado, tela de toque e/ou display), e conexões de rede. O acoplamento do conjunto de processadores e outros componentes é normalmente através de um ou mais subsistemas bus e biidges 35 (também denominados como controladores de bus). O dispositivo de armazenamento representa um ou mais mídias de comunicação não transitórias, lida por máquina ou lida por computador. Então, o dispositivo de armazenamento cle um dado dispositivo eletrônico l d 6/19 normalmente armazena código e/ou dados para execução do canjunto de um ou mais processadores de um dispositivo ele'trônico.

Evidentemente, uma ou mais partes de uma modalidade da presente invenção pode ser proporcionada utilizando diferentes combinações " de software, firmware e/ou hardware. 5 Conforme utilizado presentemente, um elemento de rede (por exemplo, roteador, e ·comutador, bridge, etc.) é uma peça de equipamento de rede, incluindo hardware e software que interconecta comunicativamente outro equipamento na rede (por exemplo, elementos de rede, estações terminais, etc.). Alguns elementos de rede são "elementos de rede de serviços múltiplos" que proporcionam suporte para múltiplas funções de rede (por exemplo, 10 roteamento, bndging, comutação, agregação Layer 2, controle de Iimite de sessão, multi- transmissão, e/ou gerenciamento de assinante) e/ou proporcionar suporte para serviços de múltipla aplicação (por exemplo, dados, voz e vÍdeo). Assinantes e estações terminais (por exemplo, servidores, Workstations, Iaptops, palm tops, telefone móveis, smart phones, telefones multimídia, Voz sobre Protocolo de lntemet (VOlP), telefones, aparelhos de mídia 15 portáti!, unidades GPS, sistemas de jogos, Caixas set-top (STB)'S, etc.) acesso a " conteúdos/serviços proporcionados sobre lnternet e/ou serviços proporcionados em redes privadas virtuais (VPN'S) sobrepostos na lnternet.

O conteúdo e/ou serviços são " normalmente proporcionados pcr uma ou mais estações terminais (por exemplo, estações teminais de servidor ) pertencentes a um serviço ou provedor de conteúdo ou estações 20 terminais que participam em um serviço usuário para usuário (peer to peer), e pode incluir página da rede pública (conteúdo livre, frentes de amazenamento, serviços de busca, etc.) , página da rede privada (por exemplo, página de rede nome de usuáriolsenha acessadas proporcionando serviços de mensagem, etc.) redes corporativas sobre VPN's, IPTV, etc.

Normalmente, estações terminais de assinante são acoplada (por exemplo através de 25 equipamento de premissa de usuário acoplado em uma rede de acesso (com ou sem fio) nos elementos de rede extrema, que são acoplados (por exemplo, através de um ou mais elementos de núcleo de rede para outros elementos de rede extrema) em outras estações terminais (por exemplo, estações terminais de servldor). As modalidades ou da presente invenção proporciona um sistema, rede e um 30 método para evitar as desvantagens da técnica anterior incluindo: baixo desempenho em topologias assimétricas. falta de suporte para operações, protocolos de administração e gerenciamento (OAM), altos requisitos de recurso por inspeção de pacote, altos níveis de dilatação para conseguir uma utilização razoável de rede, geração de múltiplos conjuntos métricos e manutenção, e significativos Têcúrsos requeridos para causar pequenas 35 mudanças no estado.

As modalidades da invenção contornam estas desvantagens permitindo uma engenharia de tráfego dinâmica enquanto minimiza um número de transversais da base de n

7/19 dados de topologia para uma rede.

O método de distribuição de carga incorpora a engenharia de tráfego dinâmica e utiliza a instanciação de mú|tip|o$ conjuntos de caminhos de custo igualitárío no plano de encaminhamento, que pode ser agregado em conjuntos de + áNores de custo iguaíitário, por onde o número acumulativo de caminhos mais curtos que 5 transitam em cada Iink em um caminho resultam de todas as interações prévias do fator de a processo de geração de caminho dentro de uma decisão para a geração do próximo conjunto de caminhos.

Uma vez que um nó realizou uma seleção de caminho inicial usando o processo de decisão (tie-breaking), e processou todos os pares de nós na base de dados de topologia, o número de caminhos mais curtos transmitindo cada link é determinado e é 10 referido como um vaior de utilização de link.

Para cada passo subsequente da base de dados para gerar ou'tros conjuntos de caminho, o conjunto de caminho entre quaisquer dois pares de nós é cortado ordenando a lista lexicograficamente classificada de valores de utilização de link para cada link em cada caminho sendo considerado- Se a lista ordenada possui um único caminho utilizado mais baixo, então este caminho é selecionado.

Se a lista 15 ordenada não tiver um caminho utilizado mais baixo, então o processo de decisão é " aplicado no subconjunto de caminhos mais curtos que geraram impasse para L(ti|ização de link mais baixo. " No método e no sistema de distribuição de carga, o modelo da carga da rede é computado em cada interação de geração de caminho Ievando em consideração a decisão 20 das interações prévias de maneira a regularizar a carga de links na rede.

O algoritmo melhorado inerentemente favorece a seleção de Iinks menos carregados em cada interação após a primeira interação.

O processo de distribuição de carga utiliza o processo de decisão cQm propriedades distintas tal que para um caminho entre quaisquer dois pontos será resoivido para um único 25' caminho simétrico a despeito da direção de computação, ordem de computação ou exame de qualquer subconjunto do caminho, uma propriedade descrita como "qualquer por'ção do 'caminho mais curto é também o caminho mais curto". Ou dito de outra forma, onde o impasse ocorrer ao longo de qualquer porção do caminho mais curto, aqueles nós irão resolver o impasse para o subconjunto do caminho com a mesma escolha, o resuitado 30 'sendo uma árvore de caminho de custo mínimo. lsto é referido presentemente como: processo de "decisão de algoritmo comum". Nq processo de distribuição de carga, um passe inicial da base de dados de topologia utilizando o processo de decisão de algoritmo comum resulta na geração do primeiro conjunto de árwres. lsto é porque ner1huma carga em qualquer link foi registrada,

35 então todos os caminhos de custo igualitários serão amarrados para utilização onde a definição de custo igualitário metricamente a menor e com q menor número de hops.

A etapa inicial requer a determinação do caminho maís curto entre cada um dos pares de nós

MPLS na rede onde para mais de um camMho mais curto entre dois nõs MPLS quaisquer em que é encontrado o processo de decisão para algoritmo comum é utilizado para decisão de modo a gerar uma seleção única de caminho entre cada um dos pares de nós MPLS na 0 rede e para gerar um ou mais conjuntos de árvores de encaminhamento de custo igualitário, 5 denominado "conjurito ECT". O processo de distribuição de carga pode ordenar os caminhos de custo igualitário e deteminar os caminhos de maior e menor ordem, ou "bookend paths", onde ambos os caminhos exibem um conjunto de propriedades requisitos.

Este processo de distribuição de carga pode, desta maneira selecionar mais de um camjnhos de um único passe "todos os 10 pares" da base de dados.

O processo de distribuição de carga também computa o número de caminhos mais curtos que atraves-"am cada link com base dos caminhos reaimente selecionados por procedimentos de decisão prévios.

Este valor é referido como valor de "utilização de link", que pode ser utilizado na computação subsequente.

Os valores de utilização de Íink podem ser a contagem de pares de nós MPLS cujo caminho mais curto 15 transita pelo link.

Em outras modalidades, possibilidades mais sofísticadas existem para

- serem utilizadas no lugar da utilização de link considerando a informação adicional na base de dados de topolog ia. " Em passos subsequerites através da base de dados pam gerar outros conjuntos de caminhos ou árvores, o conjunto de caminhos mais curtos entre qL|aisquer dois nós MPLS é 20 primeiramente ordenado gerarido valores de utiiização de caminho que podem incluir os valores de utilização de link dassificados lexicograficamente para cada um dos caminhos ou simplesmente a soma da utilização de cada link no caminho e então ordenando os caminhos resultantes com base nos valores de utilização.

Dois ou mais esquemas de ordenamento podem também ser utilizados, porque quando é selecionado mais de um caminho quando 25 da geração de um conjunto de caminhos de custo igualitário ou árvores é vantajoso minimizar o número de vezes que o mesmo caminho é selecionado.

Utilizando ordenações de múltiplos links que demonstram diversidade, pode-se minimizar o número de iterações necessárias para selecionar múltiplos caminhos.

Quando o processo de ordenamento gera um único caminho mais baixo utilizado, este pode ser selecionado sem outro 30 processamento.

Quando mais de um ordenamentos (por exemplo, um ordenamento mais baixo e um ordenamento mais alto) é considerado, então o caminho mais baixo utilizado é selecionado tanto como de ordenamento mais alto como de ordenamento mais baixo.

Quando houver mais de um caminho mais baixo utilizado e de custo igualitário, o processo de decisão de algoritmo comum é aplicado para o conjunto de caminhos utilizados mais 35 baixos pam fazer a seleção.

Em uma modalidade, mais de um ordenamento poderá ser selecionado a partir desta etapa.

Quando mais de um mecanismo de ordenamento de carga for utilizado (por exemplo, ordenamentos de soma e classificação lexicográfica) é também m possivel extrair múltiplos ordenamentos de cada quando ocorrerem amarrações.

Passes adicionais ou iterações através da base de dados de topologia podem ser realizados em cada iteração, o valor de utilização de link consignado a cada Íink em um caminho é a medida cumulativa ou iridicação de caminhos mais curtos que transitam o link selecionado durante todos os passes prévios através da base de dados de topologia.

A Figura 1 ilustra um diagrama de uma modalidade de um exemplo de topologia de rede.

O exemplo de topologia de rede inclui seis nós com os correspondentes identificadores de nós 1-6. Nenhum par de caminhos foi determinado para a topologia de rede.

Um processo de decisão de algoritmo comum é utilizado e ordena os caminhos lexicograficamente utilizando os identificadores de nós.

Examinando o conjunto de caminhos de custo igualitário entre o nó 1 e o nó 4 será gerado o seguinte conjunto ordenado de identificadores de caminho (note que os identificadores de caminho foram lexicograficamente cIassificados tal que os identificadores de nós não apareçam como uma Iista de trânsito): 1-2-3-4 1-2-4-6 1-3-4-5 1-4-5-6

Esta aplicação inicial do processo de decisão irá selecionar 1-2-3-4 e 14-5-6 como os caminhos de mais baixa e mais alta ordenações entre estes nós.

Por simplicidade neste exemplo, apenas um par de nõs 1 e 4 $ão consideradQs na determinação da contagem do caminho para a rede em vez das árvores de caminho mais curto de todos os seis nós.

Neste exemplo, os links nos caminfm de Iinks selecionados têm consignados então cada uma contagem de par de caminho 1. Para o passe seguinte, através da base de dados de topologia o processo de distribuição de carga renderia a seguinte dassificação lexicográfica de carregamento de link associado a cada um dos ID's do caminho.

Carga 0,1,1 para caminho 1-2-4-6 Carga 0,1,1 para caminho 1-3-4-5 Carga 1,1,1 para caminho 1-2-3-4 Carga 1,1,1 para caminho 1-4-5-6 A dassificação lexicográfica de cargas de links irã resultar em um impasse para os caminhos 1-2-4-6 e 1-3-4-5, como cada um é 0,1,1, Similarmente, a soma de cargas de link irá render: Carga 2 para caminho 1-2-4-6 Carga 2 para caminho 1-3-4-5 Carga 3 para caminlio 1-2-3-4 Carga 3 para caminho 1-4-5-6

Como resultado para ambos os estilos de ordenamento, é empregado o decisório secundário dos ID's de caminho classificado lexicograficamente.

Em ambos os casos deste decisório secundária o caminho baixo de (1-2-4-6) é selecionado.

Similarmente 1-3-4-5 " podem ser selecionados como o ID de caminho de alto ordenamento do conjunto de 5 caminhos carregados mais baixos.

Em uma modalidade, quando é utilizada uma seleção * alto-baixo, são selecionados dois caminhos.

Estes caminhos podem ser os mesmos ou terem sobreposição significativa.

Por exemplo, se o caminho 1-3-4-5 não existe na lista ordenada acima, então o caminho 1-2-4-6 qualificaria tanto q caminho ordenado baixo quanto o caminho ordenado alto de menor custo.

Em outras modalidades, uma entrada 10 üiicial na seleção de caTninho baixo pode ser da or'denação com base na classificação lexicográfica das cargas e a entrada primária na seleção de caminho alto pode ser da ordenação com base na soma das cargas.

Enquanto que o exemplo apenas considerou a utilização de link do exame de um par de caminhos, uma pessoa versada na técnica poderia entender que após um passe único 15 da base de dados, uma vista compreensiva da distribuição de tráfego potencial existe e que

- os passos de decisão irão inerentemente evitar os máximos e portanto, a carga é distribuida através da rede com maicir regularidade.

O graLl de modificação da distribuição de carga " proporciona|mente diminui com cada novo conjunto de caminhos consideradQs confome o efeito é acumulativo. 20 O número de caminhos selecionados por iteração do processo e o número cumulativo de caminhos que uma rede é configurada para utilizar pode ser utna função de a priori um estado de encaminhamento versus uma análise de potência computaciorta) requerida.

Selecionar tanto o caminho de mais baixo custo mais baixo como o caminho de mais baixo mais aíto irá minimizar a quantidade de potência de computação requerida para 25 um dado melhoramento no desvio padrão de utilização de Iink, mas irá requerer mais estado de encaminhamento como uma consequência, porque dois conjuntos de áNores de custo igualitário serão gerados por iteração.

Selecionar uma única permutação de caminho único de cada iteração irá requerer mais potência de computação, mas irá reduzir a quantidade de estados de base de dados de encaminhamento requerida para uma dada redL|ção no desvio 30 padrão de utilização, porque o número de vezes que dois caminhos devem ser selecionados de um candidato único e de utilização mais baixa é miMmizado.

O número global de caminhos gerados é determinado com base na combinação do estado de elemento de rede e considerações de potência computacional equilibradas contra a eficiência de rede.

A utiiização de múltiplos esquemas para ordenar cargas de caminho permite que mais

35 caminhos a serem selecionados de um dado passo da base de dados conforme reduz a probabijidade do mesmo caminho ser selecionado mais de uma vez para um dado número de seleções de caminho.

Nos exemplos acima, dois métodos de ordenação de carga de caminho foram descritos os quais produziriam resultados consistentes aplicados através da rede. Em outras modalidades, métodos adicionais ou substitutos de ordenamento poderiam ser utilizados. Por exemplo, outros mecanismos de ordenamento de cargas qUe também < possuem uma propriedade de locaiidade (qualquer porção de caminho carregado mais baixo 5 é também o caminho carregado mais baixo quando combinado com um processo de

W decisão de algoritmo comum) e podem ser utilizadas combinações de tais ordenamentos. Ajém disso, no exempb acima, a utiiização de fink é representada pela contagem de caminhos mais curtos que transitaram um Iink. É possivel utilizar numerosas variações para representar a utilização de Iink com maior detalhe e com precisão aumentada. Dentro da 10 informação de rótulo e da base de dados de topologia há infomação suficiente tal que cada nó da rede possa determinar o número de instâncias de serviço que utilizam um caminho mais curto em particular. O valor de utilização de iink pode ser determinado com base nesta utilização para pesar o link cowespondente apropriadamente. Por meio do aumerito dos dados armazenados pela informação de rótulo ou base de dados de topologia, uma 15 informação de perfil de banda larga adicional por serviço está disponível para uso em " cálculos de distribuição de carga. Em uma outra modalidade, apenas a métrica mínima de link do conjunto de links em um caminho é utilizada como representativa da carga máxima " que poderia ser oferecida entre o par de nodos. Em outras modalidades, uma métrica similar ou métricas mais detalhadas podem ser utilizadas. 20 Em uma modalidade, tudo menos o passe final da base de dados de topologia envolve uma computação de "todos os pares" dos menores caminhos entre todos os pares de nós na rede, lsto pode ser computacionalmente custoso devido a sua complexidade- O processo de distribuição de carga, entretanta não requer um número significativo de fases através da base de dados de topologia para render benefícios mensutáveis e conforme um 25 resultado o processo de distribuição de carga proporciona melhorias globais valiosas em alocação de recursos de rede que justificam estas computações de "todos os pares". Em exemplos experimentais utilizando geração aleatória de gráfico, passes únicos através da base de dados após estabelecer o conjunto ECT inicial resultado de uma redução média aproximada de 45°6 no coeficiente de variação em carregamento de link 30 medído como contagem de caminhos mais curtos que transitam em cada Iink na rede. Posteriores três passes através da base de dados de topologia continuou a reduzir o coeficiente de variação no ponto onde ocorreu uma média de 75% de redução, mas a maioria dos benefícios na distribuição de carga veio no primeiro passe após o estabelecimento da linha base. Então, a maioria dos benefícios na distribuição de carga é 35 acumulado nos primeiros dois passes da base de dados. O número de caminhos através da rede foi dobrado quando o segundo conjunto e explicitamente oolocado para evitar a carga do primeiro conjunto. Entretanto, a taxa de melhora do coeficiente de variabilidade cai do passe a passe muito mais rapidamente do que taxas de 1/2; 1/3; 1/4 que a contagem do caminho acumulativo poderia superficialmente sugerir.

Então, resultados significativos podem ser conseguidos enquanto mantém o processo de distribuição de carga tratável em termos tanto de computação quanto estado de encaminhamento. 5 Devido ao método ser efetivamente conexão orientado, e procurar os links menos carregados, qualquer perturbação da matriz de tráfego causada por uma falha tende a ser isoiada e Íocal em natureza.

O pmcesso de distribuição de carga tenderá a dirigir o tráfego de dados de volta para dentro da distribuição original uma vez que a constrição na rede foi contornada (by-passed)b O método também trabalha com base de tecnologia MPLS-TP 10 emergente, tal que protocolos de operação, administração e gerenciamento (OAM) possam ser utilizados não modificados e preseNam a arquitetura e garantias de serviço da rede MPLS, O processo de equilÍbrio de carga e sistema também permite que um administrador previamente "desequilibre" um link com um fator de carga que irá ter o efeito de mudança de 15 alguma carga fora de um link em particular. lsto permlte graduações mais úteis para

" muitiplicar o comportamento cle roteamento do que uma simples modificação métrica, de mais simples administração do que o roteamento de topologia e obvia a necessidade de " virtualização de Iink (taí como "adjacências de encaminhamento" MPLS como para RFC 4206) para acionar artificialmente a densidade de malha, que é feita antes dos sistemas de 20 equilibrio de cargas.

Para a classificação de dois estágios, o tempo de quando o desequilfbrio de link é aplicado é impcirtante.

Isto normalmente é considerado para as segunda e terceira interações subsequentes.

Em uma implementação onde na primeira interação todos qs caminhos de custo igualitário foram amarrados para utilização (zero), aplicando o fator de desequilíbrio imediatamente tenderia a mudar toda a carga para fora

25 deste Iink com um direcionamento para outros caminhos resultantes da primeira interação.

A Figura 2 é um diagrama de uma modalidade de um elemento de rede que implementa o método de distribuição de carga incorporando utilização de Iink como feedback dentro do mecanismo de decisão.

O elemento de rede (200) pode incluir uma base de dados de informação de rótulo (215), uma base de dados de topologia (217), um módulo

30 de ingresso (203), um módulo cle egresso (205) e um processador de controle (207). O módulo de ingresso (203) pode lidar com o processamento de pacotes de dados sendo recebidos pelo elemento de rede (200) no link fisico e nível de Iink de dados.

O módulo egresso (205) lida com o processamento de pacotes de dados sendo transmitidos pelo elemento de rede (200) no link fisico e no nível de link de dados.

O processador de controle

35 (207) Iida com o roteamento, encaminhamento e processamento em nivel mais alto do tráfico de dados.

O processador de controle (207) pode executar ou incluir um módulo de pesquisa de caminho mais curto (209), módulo de distribuição de carga (215), módulo de protocolo de distribuição de rótub (LDP) (213), módulo de gerenciamento de MPLS (217) e módub de classificação (211). A base de dados de informação de rótulo (215) inclui uma tábua com entradas de

W encaminhamento de rótulos que definem a maneira em que os pacotes de dados estão para 5 ser encaminhados. As entradas de encaminhamento de rótulos relatam rótulos e FEC

P subjacentes e topologias virtuais para interfaces do elemento de rede (200). Esta informação pode ser utilizada pelo pmcessador de controle (207) para determinar como um pacote de dados está para ser manuseado, i.e., parâ que interface de rede o pacote de dados deveria ser encaminhado. O método e o sístema de distribuição de carga criam entradas de 10 encaminhamento através do protocolo de distribuição de rótulo (LDP) que implementam a distribuição de carga con'forme descrito presentemente abaixo. A base de dados de topologia (217) armazena um modelo de rede ou representação similar da topologia da rede com a qual o elemento de rede (200) é conedado. Em uma modalidade, os nodos na rede são cada um roteadores de comutação de rótulo (LRS) e os 15 Iinks entre os LSR podem utilizar um número de protocolos e tecnologias subjacentes. Os " nós podem ser identificados com identificadores de nós únicos tais como endereços de canaís de comunicação "loopback nodaT e os Iinks com pares nó-identificadores. Aqueles " versados na técnicã entenderiam que esta representação de modelo de rede é proporcionado como forma de exemplo e que outras representações de topologia de rede 20 podem ser utillzadas com q método e sistema de distribuição de carga. O módulo de busca de menor caminho (209) é um componente do processador de protocolo (207) ou um módulo executado pelo processador de controle (207). O módulo de pesquisa de caminho mais curto (209) atravessa a base de dados de topologia para deteminar o caminho mais curto entre quaisquer dois nós na topologia de rede. Se 25 existirem múitiplos caminhos que possuem igual distância ou gusto na rede entre dois nodos e estes múltiplos caminhos de iguai custo padem ser proporcionados no módub de classificação (211) e módulo de distribuição de carga (21 5) para deteminar o que utiiizar. O módulo de busca de caminho mais curto (209) pode deteminar os caminhos mais curtos entre todos os nodos na topologia de rede, referido presentemente como camputação de 30 "todos os pares". O módulo de busca de caminho mais curto (209) proporciona um conjunto de caminhos mais curtos para cada par de nós e o módulo de distribuição de carga (215) seleciona um subconjunto de caminhos mais curtos e atualiza a base de dados de informação de rótulo para incluir uma entrada que implementa o subconjunto de cada um 35 dos caminhos mais curtos que atravessam o elemento de rede (200)- Após o primeiro passo, o módulo de busca de caminho mais curto (209) calcula o valor de utilização de link para cada link na topologia de rede resultante do primeiro passe através da base de dados de topologia.

O valor de utilização de link é uma contagem do número de caminhos mais curtos que atravessam um dado link.

Um valor de utilização de link separado é calculado e gravado para cada Iink.

Estes valores de utilização de Iink são « utilizados para gerar um valor de utilização de caminho que por sua vez é utilizado para 5 desequilibrar as ordenações dos caminhos para passos subsequentes através da base de » dados de topologia onde o decisório inicial é tanto a lista ordenada de valores de utilização de link lexicograficamente cIassificados ou a soma de valores de utilização de link (i.e., na foma do valor de utilização de caminho), e onde isto resulta em um impasse, o processo de decisão de algoritmo comum é utilizado como um decisório subsequente. 10 O módulo de classificação (211) é um componente do processador de controle (207) ou um módulo executado pelo processador de controíe (207)- O módulo classificador (211) assiste ao módulo de distribuição de carga (215) realizando uma ordenação inicial do conjunto carregado de árvores de custo igualitário com base nôs vaiores de utilização de caminho no segundo passe e nos passes subsequentes. 15 Para cada par de nós com múltiplos caminhos de custo igualitário, o móduio de · cIassificação (211) gera uma ordenação de cada um dos caminhos de custo iguaiitário com base nos valores de utilização de caminho e o módulo de distribuição de carga (215) " seleciona pelo menos um caminho desta ordenação.

Em outras modalidades, os caminhos de maior ordenação e o de menor ordenação podem ser $e|ecjonados para dividir a carga 20 entre os pares de nós correspondentes.

O módulo de distribuição de carga (215) é um componente do processador de controle (207) ou um módulo executado pelo processador de controle (207). Este processo pode ser repetido através de qualquer número de passes ou iterações onde os valores de utilização de link são atualizados para serem uma ind icação cumulativa 25 do conjunto de caminhos mais curtos que transitam no referido link.

Os valores de utilização de caminho são também atualizados eni linha com as mudanças nos valores de utilização de tink.

O desvio padrão na variância nos caminhos normaknente diminuem com cada iteração. mas conforme o número de conjuntos de caminhos se eleva, o impacto global de cadà conjunto adicional é proporcionalmente diminuído, indicando que o usq de mais de um 30 ou três passes ou iterações não vantajoso mesmo se o esforço computacional para produzir ou o estado de encaminhamento for instanciado.

O número de passes ou iterações é projetado por um administrador e é configurado por toda a rede.

O módulo de gerenciamento MPLS (217) é um componente do processador de protocolo (207) ou um módulo executado pelo processador de rede (207). O módulo 35 gerenciador MPLS (217) inspeciona pacotes de entrantes e determina os rótulos associados e realiza arranjos look-ups para os pacotes na base de dados de informação de rótulo (219) para determinar uma interface de rede para encaminhar o pacote através desta.

O módulo

15l19/ de gerenciamento MPLS (217) também realiza qualquer operação necessária de arrumação de rótulo (label swapping), adição de rótulo, ou remoção de rótulo para afetar a própría transversal do LSP para cada pacote de dados. O módulo LDP (213) é um componente do processador de controle (207) ou um

P 5 mõdulo executado pelo processador de controle (207). O móduio LDP (213) gera as mensagens necessárias para estabelecer a classe de equivalência de encaminhamento (FEC) e a topobgia virtual para junções de rótulos na rede utilizada para criar aqueles LSP'S utilizados para distribulr a carga da rede. O módulo LSP (213) gera mensagens de mapeamento de rótulo que incluem campos tipo-comprimento-valor (TLV) de FEC, campos 10 de rótulos nv, bem como campos de topologia virtual. A topologia virtual TLV inclui um indice de topologia que indica que iteração do processo de disüibuição de carga a que o rótulo e a FEC são associados. O módulo LDP (213) também realiza outras funções tradicionais para implementar a distribuição de rótulo, A Figura 3 ilustra um fluxograma de uma modalidade de um processo para 15 engenharia de tráfego automatizada de suporte de distribuição de carga para comutação de · rótulo de múltiplos protocolos com base no emprego de utilização de link como feedback dentro de um mecanismo de decisão para caminhos de custo igualitário. Em outra " modalidade, o processo pode ser executado na iniciação de um elemento de rede tal como um roteador de comutação de Iink, mediante notificação de uma mUdança na topobgia para 2çl a rede conectada em um roteador, em intervalos definidos ou em eventos ou tempos similares. Uma base de daclos de topologia é mantida em cada elemento de rede em uma rede como processo separado do processo de distribuição de carga e é assumido ser uma representação corrente da topologia verdadeira da rede. Em uma modalidade, o processo de distribuição de carga começa pela determinação 25 de um conjunto de caminhos mais curtos entre um elemento de rede ou nó MPLS (por exemplo, um LSR) na rede ou em um outro elemento de rede ou nó MPLS na rede (Bloco 301). O conjunto de caminhos mais curtos pode ser concebido como caminhos individuais ou como um conjunto de ámores com cada elemento de rede como uma raiz de sua respectiva árvore. Uma checagem é feita para deteminar se existem múltiplos caminhos 30 mais curtos, isto é, há um impasse peio caminho mais curto entre os nós MPLS (Bloco 303). Se o par de nós MPLS tiver um único caminho mais curto entre "eles, a base de dados de informação de rótulo é atualizada para refletir o caminho mais curto (BIOco 306). Em uma modalidade, a base de dados de informação de rótulo é atualizada para refletir cada um dos caminhos que atravessam o elemento de rede que a mantêm. Cada elemento de rede na 35 rede reatiza este mesmo cálculo. O processo de distribuição de carga é determinístico e então cada elemento de rede irá produzir o mesmo resultado. Outro processamento daqueles pares de nós MPLS com um único caminho mais curto é desnecessãrio a menos que haja uma mudança na topoiogia. Se o par de nós MPLS não tiver um único caminho mais curto nomalmente medido como o menor número de hops e o menor custo então o processo de decisão de algoritmo " comum é utilizado para permitir um único caminho mals curto ou conjunto de caminhos mais 5 curtos a serem selecionados (BIOcO 305). Em uma modalidade, é possÍvel selecionar os r primeiro e último camirihos ordenados. Após os caminhos ser'em selecionados, eles são armazenados na base de dados de informação de rótulo ou utiiizados para atualizar a base de dados de informação de rótulo, tal que todos os pares de nós MPLS tenham pelo menos um caminho entre eles selecionado. 10 Após ser selecionado o caminho mais curto, uma checagem é feita para determinar se todos os pares de nós MPLS tiveram um caminho selecionado (Bloco 307). Se outros pares de nós MPLS não tiverem tido um caminho ou conjurjto de camMhos selecionado, então o processo continua por meio de seleção do próximo par de nós para processar (Bloco 309). Se todos os pares de nós MPLS tiverem tido um caminho mais curto 15 selecionado, então o processo continua no segundo passe ou interação.

· O valor de utilização de link para cada link é calculado mesmo como uma consequência de ou após a atualização da base de dados de encaminhamento para todos " os pares de nós MPLS tiver sido completada (Bloco 310). O valor de utilização de link é uma contagem do número de caminhos que atravessam cada link correspondente em uma 20 topdogia da rede. O valor de utilização de link é calculado para cada link na rede. O valor de utilização de link proporciona uma indicação do nível de uso e potenciais gargalos na rede que deveriam ser evitados se caminhos adicionais fossem fomados. Para a formação subsequente de caminhos mais curtos, é injcialmente realizada uma decisão (tie-breaking) gerando valores de utilização de caminho mesmo conforma a 25 Iista Iexicograficamente sorteada onde 0$ valores de caminho de utilização incluem valores de uti1izaçãQ de link ou a soma dos valores de utilização de Iink. O processo todos os nós inicia-se novamente selecionando um par de nós MPLS e determinando um conjunto de caminhos mais curtos entre o par de nós MPLS (Bloco 311). Este processo inclui valores de utilização de caminho com base nos valores de utilização de link que correspondem a cada 30 caminho (Bloco 313). Os valores de utilização de caminho podem representar a carga global de cada caminho, tal como uma soma de valores de utilização de link ou podem ser um arranjo lexicograficamente classificado dos valores de utilização de link destacando os links mais ou menos carregados em cada caminho ou arranjos e representações similares. Os caminhos mais curtos são ordenados por seus valores de utilização de caminho (Bloco 315)- 35 Uma checagem é feita para determinar se há mais de um caminho mais curto para um dado par de nós MPLS tendo valores de utilização de caminho igualitários (Bloco 317). Onde um caminho unicamente baixo existir este será selecionado sem outro

= processamento para todas as ordenações de caminho (por exemplo, o mais baixo e çj mais alto). Quando houver mais de um caminho mais curto de carga idêntica (i.e., valores de utilização de caminhos idênticos), o processo de decisão de algoritmo comum é então 4 utilizado para realizar a seleção de caminho neste subconjunto de mais baixos carregados 5 conjuntos de caminhos mais curtos (Bloco 321). A ordenação leva em consideração o valor

W de utilização de link tal que aqueles caminhos com os links mais baixos ou menos utilizados são os mais prováveis de serem selecionados, que leva em conta a carga global da rede e não apenas um próximo hop na rede como resultado, o roteamento através da rede é mais equilibrado. A base de dados de informação de rótulo é então atualizada para refletir os 10 caminhos selecionados (Bbco 318). É feita então uma checagem para determinar se todos os pares de nós MPLS possuem Llm caminho mais curto selecionado ou conjuntô de caminhos mais curtos selecionados (Bloco 319). Se não, então o processo continua por melo de seleção do próximo par de nós MPLS para processar (Bloco 323). Se todos qs pares de nós MPLS 15 tiverem sido calculados, então uma checagem é feita para deteminar se são necessários " caminhos adicionais (Bloco 325). Se nenhum caminho adicional for necessário (isto pode ser um parâmetro que é ajustado pelo administrador da rede ou similarmente deteminado), então, o processo de distribuição de cargas termina. Se caminhos adicionais forem necessários, então o processo continua com um terceiro passo ou iteração que é similar ao 20 segundo, mas montado sobre a utilização de link determinado em iterações prévias. Este processo pode ter qualquer riúmero de iterações- A Figura 4 é Ljm fluxograma de uma modalidade de um processo para gerar uma mensagem de mapeamento de rótulo como parte do protocolo de distribuição de rótulo. Em uma modalidade, o processo é iniciado em resposta a uma mudança na topologia ou a uma 25 mudança em uma base de dados de informação de rótulo para a rede. Em uma outra modalidade, o processo é iniciado por cada nó que gera uma mensagem de mapeamentQ de rótulo a ser enviada a um de seus pares (Bloco 401). A mensagem de mapeamento de rótulo inclui um número de campos tipo- comprimento-valor (TLV). Uma mensagem de mapeamento de rótulo em separado é gerada 30 para cada classe de equivalência de encaminhamento (FEC) e cada caminho de topologia ou árvore na topologia da rede gonforme representada na base de informação de rótulo do nó hospedeiro. Para cada mensagem de mapeamento de rótulo a classe de equivalência de correspondência de campo é definida em um campo FEC TLV da mensagem de mapeamento de rótulo (Bloco 403). 35 O campo TLV de rótulo de cada uma das mensagens de mapeamento de rótulo é tambéni definido de acordo com o rótulo consignado a um LSP para cada uma das interfaces no caminho (Bloco 405). Um indice de topologia é também definido na mensagem de mapeamento de rótulo (Bloco 407). O índice de topologia indica a iteração do processo de seleção do LSP definido pela mensagem de mapeamento de rótulo.

Por exemplo, se a mensagem de mapeamento de rótulo corresponder à primeira árvore selecionada ou 't caminho, então o Índice de topologia de zero ou um poderá ser selecionado e Ínserido 5 dentro da mensagem de mapeamento de rótulo.

Similarmente, se um segundo caminho ou m árvore corresponder à mensagem então um ou dois poderá ser especificado como o vabr.

Uma vez que cada uma das mensagens de mapeamento de rótujo é definida e cada um de seus valores é especificado, então a mensagem de mapeamento de rótulo pode ser enviada a cada um dos pares de protoco|o de distribuição de rótulo (Bloco 409). Em uma 10 modalidade, uma topologia TLV é definida para a mensagem de mapeamento de rótulo.

A Figura 5 é um diagrama de uma modalidade de uma rede múltiplo-ponto a múltiplo-ponto incluindo um conjunto de roteadores de comutação de rótuh (LSR) 1-18. O diagrama mostra um conjunto de caminhos ou árvores definidas pela primeira iteração do processo acima deiinido para o dado exemplo.

O diagrama assume que o ingresso nesta 15 rede pode ser distribuído pelos nós 1-4 e da mesma forma 13-18, em outras palavras, estes " LSR estão na borda da rede, mas possuem as mesmas interfaces extemas.

Neste exemplo, no primeiro passe do processo seria gerado um canjunto de caniinhos únicos " lexicograficamente classificados para todos os pares de nÓe\ de 1-13 a 4-18 (por exemplo, 1- 5, 5-9, 9-13 e 4-8, &12, 12-18) deste conjunto de caminhos únicos o exemplo assume que 20 um caminho baixo ou um caminho alto da ordenação destes identificadores de caminho único é selecionado, que corresponde às árvores 501 e 503. A Figura 6 ilustra caminhos ou árvores setecionados na segunda iteração do método de distribuição de carga descrito presentemente.

Neste exemplo, o método de distribuição de carga encontra dois caminhos onde a ordenação lexicográfica da c'arga de link associada 25 com cada caminho produz um impasse entre dois caminhos e a ordenação lexicográfica exemp|ifjçativa de id de nó conforme um identificador de caminho é invocada para autoritariamente resolver o impasse.

A árvore mais baixamente ordenada (605) e a árvore de maior ordenação (607) da segunda iteração também distribuem o tráfego entre os nós 104 e os nós 13-18 e suplementa a árvore mais baixamente ordenada (601) e árvore mais 30 altamente ordenacla (603) da primeira iteração ilustrada na Figura 5. lncorporando o valor de utílização de Íink na classificação Iexicográfica, a segunda iteração seleciona caminhos de custo igualitário que possuem os links menos utilizados pelos quais há o aumento da utilização da banda larga e a diversidade da topologia dos caminhos "todos qs pares" selecionados. 35 A Figura 7 ilustra um diagrama de uma modalidade de mapeamento de um conjunto de pseudo linhas na rede de comutação de pacote subjacente para suportar administração de operações e manutenção (OAM) na rede MPLS.

O monitoramento de desempenho pode lt

19/19 ser mantido e a compatibiiidade mantida com o sistema de engenharia de tráfego por subjazer uma malha inteira de LSP par a par entre os pontos terminais equivalentes em um conjunto de pseudo linhas.

A ordem de escalas de rede de comutação de pacote (N) e o gerenciamen'to de faltas pode medir conformemente, mas a sobreposição possui 5 propriedades par a par requeridas para monitoramento de desempenho.

As FEC de pseL|do Iinhas são modificadas para juntar FEC de pseudo linhas em um Índice de topologia virtual PSN.

Conforme a topobgia PSN é Iogicamente par a par entre os pseudo pontos finais, o rótulo da pseudo linha proporciona um meio de desambiguidade de fonte para contadores OAM. 10 Então, um método, um sistema e um aparelho para distribuição de carga em uma rede MPLS que leva em conta q uso de link foi presentemente descrito, Deve ser entendido que a descrição acima é pretendida como sendo ilustrativa e não restritiva- Muitas outras modalidades se tornarão aparentes para aqueles versados na técnica por meio da Ieitura e entendimento da descrição acima.

O escopo da presente invenção deveria, portanto ser 15 determinado com referência às reivindicações apensas, com as quais a totalidade do

· escopo de equivalentes são abrangidas.

Claims (18)

REIVINDICAÇÕES

1. Método implementado em um nó de uma rede de comutação de rótulo de múltiplos protocolos (MPLS) para distribuição melhorada de carga, caracterizado pelo fato de o nó ser um dentre uma pluralidade de nós na rede MPLS em que cada um dos nós implementa um processo de decisão de algoritmo comum para produzir árvores de caminho mais curto e custo mínimo, o nó incluindo uma base de dados de topologia para armazenar uma topologia da rede MPLS, em que a topologia da rede MPLS inclui uma pluralidade de nós e links entre os nós, o método compreendendo as etapas de: - determinar um primeiro conjunto de um ou mais caminhos mais curtos entre cada par de nó MPLS na rede MPLS executando um algoritmo de busca de caminho mais curto na topologia da rede MPLS armazenada na base de dados de topologia; - selecionar pelo menos um primeiro caminho mais curto do primeiro conjunto de caminhos mais curtos para cada par de nós MPLS, aplicando o processo de decisão de algoritmo comum; - calcular um valor de utilização de link para cada link da rede MPLS com base na contagem de caminhos mais curtos selecionados que transitam em cada link; - determinar um segundo conjunto de um ou mais caminhos mais curtos entre cada par de nós MPLS na rede MPLS executando o algoritmo de busca de caminho mais curto na topologia da rede MPLS armazenada na base de dados de topologia; - gerar um valor de utilização de caminho para cada caminho mais curto no segundo conjunto de um ou mais caminhos mais curtos com base nos valores de utilização de link correspondentes a cada caminho mais curto; - selecionar um segundo caminho mais curto do segundo conjunto de um ou mais caminhos mais curtos com base no valor de utilização de caminho, em que a seleção utiliza o processo de decisão de algoritmo comum quando múltiplos caminhos mais curtos tendo valores de utilização de caminho igualitários estão presentes no conjunto de um ou mais caminhos mais curtos; e - armazenar pelo menos o primeiro caminho mais curto e o segundo caminho mais curto para cada par de nós MPLS em uma base de dados de informação de rótulo, em que a base de dados de informação de rótulo indica onde encaminhar o tráfego entrante no nó MPLS, por meio do que a seleção dos segundos subconjuntos na luz da utilização de caminho minimiza o desvio padrão da distribuição de carga através da rede MPLS inteira.

2. Método, de acordo com a reivindicação 1, caracterizado pelo fato de a etapa de geração do valor de utilização de caminho compreender: - somar valores de utilização de link correspondentes a cada caminho, ou - classificar lexicograficamente os valores de utilização de link correspondentes a cada caminho.

3. Método, de acordo com a reivindicação 2, caracterizado pelo fato de compreender as etapas de: - receber um fator de modificação de link de um administrador; e - combinar o fator de modificação de link com o valor de utilização de link para ponderar um correspondente dos links e caminhos para diminuir a utilização do link diminuindo uma probabilidade de seleção afetando a ordenação do conjunto de caminho carregado mais baixo.

4. Método, de acordo com a reivindicação 2, caracterizado pelo fato de compreender adicionalmente as etapas de: - ordenar cada caminho mais curto no segundo conjunto de caminhos mais curtos com base nos valores de utilização de caminho correspondentes, em que a etapa de seleção de pelo menos o segundo caminho mais curto compreende adicionalmente: - selecionar da ordenação um caminho mais curto ordenado mais alto e mais baixo.

5. Método, de acordo com a reivindicação 2, caracterizado pelo fato de compreender as etapas de: - iterativamente selecionar caminhos mais curtos adicionais para compartilhar distribuição de carga com o primeiro caminho mais curto e com o segundo caminho mais curto até que seja alcançado um número administrado de caminhos que refletem um desejo dos operadores de rede para melhora global para a rede Ethernet.

6. Método, de acordo com a reivindicação 1, caracterizado pelo fato de os conjuntos de caminhos mais curtos entre pares de nós MPLS serem implementados como caminhos comutados de rótulo dentro da rede MPLS.

7. Método, de acordo com a reivindicação 1, caracterizado pelo fato de compreender adicionalmente as etapas de: - gerar uma mensagem de mapeamento de rótulo; - definir um campo FEC tipo-comprimento-valor (TLV) na mensagem de mapeamento de rótulo; - definir um campo TLV de rótulo na mensagem de mapeamento de rótulo; - definir um índice de topologia para a mensagem de mapeamento de rótulo, em que o índice de topologia indica uma iteração nas etapas de seleção do primeiro subconjunto e do segundo subconjunto; e - enviar a mensagem de mapeamento de rótulo para cada par de protocolo de distribuição de rótulo na rede MPLS.

8. Método, de acordo com a reivindicação 7, caracterizado pelo fato de as mensagens de mapeamento de rótulo serem enviadas para cada par LDP para cada combinação de valores de índice de topologia e FEC.

9. Elemento de rede para distribuição melhorada de carga em uma rede de comutação de rótulo de múltiplos protocolos (MPLS) que inclui o elemento de rede, caracterizado pelo fato de ser um de uma pluralidade de nós na rede MPLS, em que uma topologia da rede MPLS inclui uma pluralidade de nós e links entre os nós, o elemento de rede compreendendo: - uma base de dados de topologia para armazenar informação de link para cada link na rede MPLS; - uma base de dados de informação de rótulo para armazenar informação de rótulo para cada porta do elemento de rede, em que a base de dados de informação de rótulo indica onde encaminhar cada classe de equivalência de encaminhamento (FEC) que entra no elemento de rede; - um processador de controle acoplado à base de dados de topologia e à base de dados de informação de rótulo, o processador de rede configurado para processar tráfego de dados, em que o processador de rede compreende: - um módulo de gerenciamento MPLS configurado para encaminhar tráfego de dados através de caminhos de comutação de rótulo (LSP); - um módulo de protocolo de distribuição de rótulo (LDP) configurado para estabelecer LSPs na rede MPLS; - um módulo de busca de caminho mais curto configurado para determinar pelo menos um caminho mais curto entre cada par de nós MPLS na rede MPLS executando um algoritmo de busca de caminho mais curto na base de dados de topologia, em que o módulo de busca de caminho mais curto é configurado para enviar, para cada um dos pares de nós MPLS com uma pluralidade de caminhos mais curtos de custo igualitário, os caminhos mais curtos de custo igualitário para um módulo de distribuição de carga; - um módulo de classificação configurado para ordenar cada um da pluralidade de caminhos mais curtos de custo igualitário com base em um valor de utilização de caminho derivado dos valores de utilização de link associados com cada caminho na pluralidade de caminhos mais curtos de custo igualitário; e - um módulo de distribuição de carga configurado para selecionar, da pluralidade de caminhos mais curtos de custo igualitário recebida, um primeiro subconjunto da pluralidade de caminhos mais curtos de custo igualitário para aquele par de nós MPLS a ser utilizado para compartilhar carga de tráfego de dados entre o par de nós MPLS e para selecionar, com base no valor de utilização de caminho, um segundo subconjunto da pluralidade de caminhos mais curtos de custo igualitário para aquele par de nós MPLS a ser utilizado para compartilhar carga de tráfego de dados com o primeiro subconjunto para aquele par de Ethernet Bridge,

por meio do que, a seleção do segundo subconjunto na luz do valor de utilização de caminho minimiza o desvio padrão de distribuição de carga através da rede MPLS inteira.

10. Elemento de rede, de acordo com a reivindicação 9, caracterizado pelo fato de o módulo de classificação ser adicionalmente configurado para classificar os valores de utilização de link lexicograficamente para criar uma ordenação da pluralidade de caminhos mais curtos de custo igualitário.

11. Elemento de rede, de acordo com a reivindicação 9, caracterizado pelo fato de o módulo de busca de caminho mais curto ser adicionalmente configurado para calcular o valor de utilização de link para cada link na topologia.

12. Elemento de rede, de acordo com a reivindicação 9, caracterizado pelo fato de o processador de controle ser adicionalmente configurado para gerar caminhos de comutação de rótulo (LSP) para implementar cada um dos caminhos mais curtos selecionados entre pares de nós dentro da rede MPLS.

13. Elemento de rede, de acordo com a reivindicação 9, caracterizado pelo fato de o módulo de distribuição de carga ser adicionalmente configurado para receber um fator de modificação de link de um administrador e combinar o fator de modificação de link com o valor de utilização de link para ponderar um link correspondente em um caminho para diminuir a utilização do link diminuindo a probabilidade de seleção afetando a classificação lexicográfica daquele caminho.

14. Elemento de rede, de acordo com a reivindicação 9, caracterizado pelo fato de o módulo de distribuição de carga ser adicionalmente configurado para selecionar o primeiro subconjunto de cada da pluralidade de caminhos mais curtos de custo igualitário selecionando um item mais alto e mais baixo na primeira ordenação de caminhos mais curtos de custo igualitário.

15. Elemento de rede, de acordo com a reivindicação 9, caracterizado pelo fato de o módulo de distribuição de carga ser adicionalmente configurado para selecionar o segundo subconjunto de cada um da pluralidade de caminhos mais curtos de custo igualitário selecionando um item mais alto e mais baixo aplicando um processo de decisão de algoritmo comum nos caminhos mais curtos de custo igualitário tendo uma carga mais baixa.

16. Elemento de rede, de acordo com a reivindicação 9, caracterizado pelo fato de o módulo de classificação e o módulo de distribuição de carga serem adicionalmente configurados para iterativamente selecionar subconjuntos adicionais para compartilhar distribuição de carga com o primeiro subconjunto e com o segundo subconjunto.

17. Elemento de rede, de acordo com a reivindicação 9, caracterizado pelo fato de o módulo LDP ser adicionalmente configurado para gerar uma mensagem de mapeamento de rótulo que inclui um campo FEC tipo-comprimento-valor (TLV) na mensagem de mapeamento de rótulo, um campo TLV de rótulo na mensagem de mapeamento de rótulo, um índice de topologia para a mensagem de mapeamento de rótulo, em que o índice de topologia indica uma iteração nas etapas de seleção do primeiro subconjunto e do segundo subconjunto e é adicionalmente configurado para enviar a mensagem de mapeamento de rótulo para cada par de protocolo de distribuição de rótulo na rede MPLS.

18. Elemento de rede, de acordo com a reivindicação 17, caracterizado pelo fato de o módulo LDP ser adicionalmente configurado para enviar mensagens de mapeamento de módulo para cada par LDP para cada combinação índice de topologia e FEC.