BRPI0712116A2 - processo de roteamento de ligações virtuais em uma rede de comutação de quadros, e, programa de computador - Google Patents

Abstract

PROCESSO DE ROTEAMENTO DE LIGAçõES VIRTUAIS EM UMA REDE DE COMUTAçãO DE QUADROS, E, PROGRAMA DE COMPUTADOR. A invenção se refere a um processo de roteamento de ligações virtuais em uma rede de comutação de quadros que compreende uma pluralidade de terminais fontes e/ou destinatários dos ditos quadros, comutadores de quadros sendo ligados entre si por ligações fisicas, cada ligação virtual sendo definida, para um tipo ponto a ponto, por um caminho através da dita rede entre um terminal fonte e um terminal destinatário e, para um tipo multiponto, por uma pluralidade de caminhos através da dita rede entre um terminal fonte por um lado e uma pluralidade de terminais destinatários, por outro lado. O processo efetua o roteamento das ligações minimizando para isso pelo menos uma função de custo em um conjunto de soluções que satisfazem a pelo menos uma restrição topológica predeterminada.

Description

"PROCESSO DE ROTEAMENTO DE LIGAÇÕES VIRTUAIS EM UMA REDE DE COMUTAÇÃO DE QUADROS, E, PROGRAMA DE COMPUTADOR"

DESCRIÇÃO

DOMÍNIO TÉCNICO

A presente invenção se refere ao domínio do roteamento em uma rede de comutação de quadros e mais especialmente em uma rede AFDX.

ESTADO DA TÉCNICA ANTERIOR

As redes Ethernet são as mais conhecidas das redes locais. Elas podem funcionar sob dois modos distintos mas compatíveis entre si; um modo dito partilhado, no qual um mesmo suporte físico é partilhado entre os terminais, com acesso aleatório e detecção de colisões entre quadros, e um modo dito comutado, no qual os terminais trocam entre si quadros com o auxílio de ligações virtuais, garantindo assim a ausência de colisões.

Em uma rede Ethernet comutada, cada terminal, fonte ou destinatário, é ligado individualmente a um comutador de quadros e os comutadores são ligados entre si por ligações físicas. Mais precisamente, cada comutador possui uma pluralidade de porás conectados aos porás de outros comutadores ou acopladores de terminais. Uma ligação virtual entre um terminal fonte e um terminal destinatário é definida como um caminho através da rede percorrido pelos quadros do terminal fonte com destino ao terminal destinatário. De maneira equivalente, uma ligação virtual é definida pela lista de comutadores que esses quadros atravessam. Para cada comutador atravessado, a comutação de quadros é realizada a partir do endereço do destinatário, com o auxílio de uma tabela de comutação preestabelecida. Essa tabela de comutação é muito simples visto que ela indica em função do port de entrada do comutador e do endereço de destinação do quadro, o port de saída correspondente. Um outro exemplo bem conhecido de rede de comutação de quadros é a rede ATM na qual uma conexão de circuito virtual (VCC) pode ser estabelecida para encaminhar quadros elementares ou células entre um terminal fonte e destinatário.

Será designada na seqüência por "ligação virtual" uma conexão de ponta a ponta de nível 2 em uma rede de comutação de quadros, tal como uma ligação virtual em uma rede Ethernet comutada ou uma conexão de circuito virtual em uma rede ATM. Em uma rede de comutação de quadros, as ligações virtuais são roteadas através da rede, ou de maneira administrativa, ou por via de sinalização que passa pelo plano de controle. O roteamento das ligações consiste em definir e em programas as tabelas de comutação dos diferentes comutadores da rede. De maneira geral, essas tabelas de comutação podem ser estáticas (roteamento administrativo) ou dinâmico (roteamento por sinalização).

Em certos casos, é possível obter uma certa garantia de serviço por ligação virtual. Por exemplo, em uma rede ATM, a classe de serviço CBR (Constant Bit Rate) permite reservar uma banda passante fixa e uma vazão mínima na ligação. No entanto, como os comutadores só podem suportar uma vazão máxima dada, essa garantia de serviço impõe restrições no roteamento das ligações.

De maneira similar, a rede AFDX (Avionics Full Duplex Switched Ethernet) desenvolvida para as necessidades da aeronáutica, é uma rede Ethernet comutada na qual é possível efetuar uma reserva de banda passante por ligação virtual. Mais precisamente, a cada ligação virtual é associado um intervalo mínimo entre quadros assim como um tamanho máximo de quadro. Além disso, um tempo máximo de encaminhamento dos quadros ou tempo de latência é garantido para cada ligação virtual. Visto que os comutadores só podem assegurar uma vazão dada por port de saída, a garantia das características das ligações virtuais passa aí ainda por restrições de roteamento.

A presente invenção se aplica preferencialmente mas não exclusivamente à rede AFDX. Será encontrada uma descrição detalhada dessa rede no documento intitulado "AFDX protocol tutorial" disponível no site www.condoreng.com assim como no pedido de patente FR-A-2832011 depositado em nome da requerente. Suas principais características serão simplesmente lembradas abaixo.

Como previamente mencionado, a rede AFDX é baseada em uma rede Ethernet comutada. Ela é por outro lado de tipo full-duplex, cada terminal podendo simultaneamente emitir e receber quadros em ligações virtuais distintas. A rede AFDX é também determinista, no sentido em que suas ligações virtuais têm características garantidas em termos de latência, de segregação física de fluxo, de banda passante e de vazão. Cada ligação virtual dispõe para fazer isso de um caminho reservado de ponta a ponta, de uma fragmentação temporal em intervalos de transmissão (denominados BAG para Bandwidth Allocation Gap) e de um tamanho de quadro máximo. Os quadros são enviados no início de cada intervalo de transmissão com uma tolerância de flutuação de fase predeterminada. Finalmente a rede AFDX é redundante, no sentido em que ela é duplicada por razões de disponibilidade.

Os dados são transmitidos sob a forma de pacotes EP encapsulados em quadros Ethernet. Diferentemente da comutação Ethernet clássica (que utiliza o endereço Ethernet do destinatário), a comutação de quadros em uma rede AFDX utiliza um identificador de ligação virtual concatenado ao cabeçalho de quadro. Quando um comutador recebe em um de seus porás de entrada um quadro, ele lê o identificador de ligação virtual e determina a partir de sua tabela de comutação o ou os port(s) de saída no(s) qual (quais) ele deve ser transmitido. Os comutadores verificam sem interrupção a integridade dos quadros transmitidos mas não demandam uma retransmissão se um quadro está errado: os quadros detectados como errados são eliminados. Os quadros que transitam em uma ligação virtual são numerados em seqüência. Na recepção, o terminal destinatário verifica a integridade da seqüência dos quadros.

Cada ligação virtual é mono-direcional. Ela só pode ser proveniente de um terminal fonte de cada vez mas pode chegar a vários destinatários. São distinguidas as ligações virtuais em modo ponto a ponto, que só servem um único destinatário, ligações virtuais em modo multiponto que servem vários destinatários.

A Fig. 1 representa esquematicamente uma rede AFDX que compreende terminais LRUl a LRU5 e comutadores de quadros SWl, SW2. E visto que a ligação virtual VL3 que liga o terminal LRU3 a LRU2 é de tipo ponto a ponto enquanto que as ligações virtuais VL2 que servem LRU2 e LRU3, e VLi que serve LRU3 a LRU5 são de tipo multiponto.

Certas ligações virtuais são bastante dependentes entre si pois elas participam para a realização de uma mesma função. Por exemplo, as ligações virtuais provenientes de diferentes sensores de navegação de uma aeronave participam para a mesma função de posicionamento. E chamado na seqüência de feixe funcional ou simplesmente feixe qualquer conjunto de ligações virtuais, de tipo ponto a ponto ou multiponto, que participa para a realização de uma mesma função.

As redes de comutação de quadros que oferecem uma garantia de serviço, como as redes ATM e AFDX, necessitam impor restrições de roteamento das ligações virtuais. Além disso, as aplicações embarcadas, em especial as aplicações aeronáuticas exigem precauções suplementares que se traduzem por sua vez com muita freqüência em restrições de roteamento.

Até agora, o roteamento de ligações em uma rede AFDX era efetuado de maneira empírica. Esse tipo de roteamento pode ser aceitável para um número de ligações virtuais relativamente pequeno. Com o aumento da complexidade dos sistemas aeronáuticos, o número de ligações virtuais pode doravante atingir vários milhares. A presente invenção visa oferecer um processo de roteamento sistemático e automático que leve em consideração o conjunto das restrições de roteamento e permita otimizar a segurança de utilização da rede.

EXPOSIÇÃO DA INVENÇÃO

A presente invenção é definida por um processo de roteamento de ligações virtuais em uma rede de comutação de quadros que compreende uma pluralidade de terminais fontes e/ou destinatários dos ditos quadros, comutadores de quadros sendo ligados entre si por ligações físicas, cada ligação virtual sendo definida, para um tipo ponto a ponto, por um caminho através da dita rede entre um terminal fonte e um terminal destinatário e, para um tipo multiponto, por uma pluralidade de caminhos através da dita rede entre um terminal fonte por um lado e uma pluralidade de terminais destinatários, por outro lado. O dito processo compreende as etapas seguintes para pelo menos uma ligação virtual:

(a) seleção entre um conjunto de caminhos possíveis entre o terminal fonte e o ou os terminal(ais) destinatário(s), de um subconjunto de caminhos que satisfazem a pelo menos uma restrição topológica predeterminada;

(b) determinação entre o dito subconjunto, de um caminho, para uma ligação virtual de tipo ponto a ponto ou de uma pluralidade de caminhos, para uma ligação virtual de tipo multiponto, que minimiza pelo menos uma função de custo dada;

(c) roteamento da dita ligação virtual de acordo com o ou os caminho(s) assim determinado(s).

De acordo com uma primeira variante, quando a dita ligação virtual é uma ligação ponto a ponto e a rede sendo dividida em zonas distintas, a dita restrição topológica se exprime vantajosamente como uma restrição de não transposição de fronteira entre zonas se os comutadores ligados respectivamente ao terminal fonte e ao terminal destinatário pertencem à mesma zona, e, no caso contrário, como uma restrição de transposição única da fronteira entre as zonas de pertença respectivas dos ditos terminais fonte e destinatário. A etapa de seleção pode levar em consideração restrições topológicas adicionais de segregação e/ou de colocação dos caminhos possíveis em relação às ligações virtuais já roteadas ou a rotear simultaneamente com a dita ligação ou a comutadores da dita rede.

Alternativamente ou cumulativamente, a etapa de seleção poderá levar em consideração restrições topológicas adicionais que têm como objeto um grupo de caminhos constitutivos de um conjunto de ligações virtuais a rotear simultaneamente, o dito grupo sendo constituído por uma pluralidade Nsg de subgrupos dos ditos caminhos, a dita restrição adicional exprimindo que no máximo um número nsg de subgrupos tal que O < nsg < Nsg podem ser invalidados, um subgrupo sendo invalidado se todos os caminhos que lhe pertencem são afetados pela falha de um mesmo comutador da dita rede.

A dita função de custo precitada pode ser escolhida igual ao número de comutadores atravessados por um caminho.

De acordo com uma segunda variante, quando a dita ligação virtual é de tipo multiponto e a rede é dividida em zonas distintas, aplica-se vantajosamente a cada caminho possível entre o dito terminal fonte e um terminal destinatário da dita ligação, uma restrição de não transposição de fronteira entre zonas se os comutadores ligados respectivamente ao terminal fonte e ao dito terminal destinatário pertencem à mesma zona e, no caso contrário, uma restrição de transposição única da fronteira entre as zonas de pertença respectivas dos ditos terminais fonte e destinatário. Como precedentemente, é possível aplicar para cada um dos caminhos possíveis entre o dito terminal fonte e um terminal destinatário da dita ligação, restrições topológicas adicionais de segregação e/ou de colocação desses caminhos em relação a ligações virtuais já roteadas ou a rotear simultaneamente com a dita ligação ou a comutadores. Alternativamente ou cumulativamente, a etapa de seleção poderá levar em consideração restrições topológicas adicionais, cada restrição topológica adicional tendo como objeto um grupo de caminhos constitutivos de um conjunto de ligações virtuais a rotear simultaneamente, o dito grupo sendo constituído por uma pluralidade Nsg de subgrupos dos ditos caminhos, a dita restrição adicional exprimindo que no máximo um número nsg de subgrupos tal que 0 < nsg < Nsg podem ser invalidados, um subgrupo sendo invalidado se todos os caminhos que lhe pertencem são afetados pela falha de um mesmo comutador da dita rede.

A função de custo poderá ser tomada igual ao número de comutadores atravessados por um caminho e será minimizada em cada conjunto de caminhos possíveis entre o dito terminal fonte e um terminal destinatário da dita ligação, para fornecer pelo menos um caminho candidato por terminal destinatário. Vantajosamente, são efetuadas combinações de K caminhos candidatos em que K é o número de terminais destinatários da ligação, cada combinação correspondendo a uma solução possível de roteamento da dita ligação multiponto, uma segunda função de custo é minimizada no conjunto das ditas soluções possíveis assim obtidas. Essa segunda função de custo avalia, para cada solução possível, o número de comutadores partilhados entre seus diferentes caminhos constitutivos.

De acordo com uma terceira variante, para pelo menos um grupo de ligações que participam para a realização de uma mesma função, dito feixe de ligações, cada ligação sendo ponto a ponto e a rede sendo dividida em zonas distintas, aplica-se para cada uma das ligações do dito feixe, a cada caminho possível entre o terminal fonte e o terminal destinatário da dita ligação, uma restrição de não transposição de fronteira entre zonas se os comutadores ligados respectivamente ao terminal fonte e ao terminal destinatário pertencem à mesma zona, e, no caso contrário, uma restrição de transposição única da fronteira entre as zonas de pertença respectivas dos ditos terminais fonte e destinatário. Como precedentemente, é possível aplicar para cada ligação virtual e para cada um dos caminhos possíveis entre o terminal fonte e o terminal destinatário da dita ligação, restrições topológicas adicionais de segregação e/ou de colocação desses caminhos em relação a ligações virtuais já roteadas ou a rotear simultaneamente com a dita ligação ou a comutadores. Alternativamente ou cumulativamente, a etapa de seleção poderá levar em consideração restrições topológicas adicionais, cada restrição topológica adicional tendo como objeto um grupo de caminhos constitutivos de um conjunto de ligações virtuais a rotear simultaneamente, o dito grupo sendo constituído por uma pluralidade Nsg de subgrupos dos ditos caminhos, a dita restrição adicional exprimindo que no máximo um número nsg de subgrupos tal que O ≤ nsg ≤ Nsg podem ser invalidados, um subgrupo sendo invalidado se todos os caminhos que lhe pertencem são afetados pela falha de um mesmo comutador da dita rede.

A dita função de custo poderá ser tomada igual ao número de comutadores atravessados por um caminho e será minimizada, para cada uma das ligações do dito feixe, em cada conjunto de caminhos possíveis entre o terminal fonte e o terminal destinatário da dita ligação, para fornecer pelo menos um caminho candidato por ligação. Vantajosamente, são efetuadas combinações de N caminhos candidatos em que N é o número de ligações do dito feixe, cada combinação correspondendo a uma solução possível de roteamento do dito feixe, uma terceira função de custo é minimizada no conjunto das ditas soluções possíveis assim obtidas. A terceira função de custo avalia, para cada solução possível de roteamento do feixe, o número de comutadores partilhados entre os caminhos dos quais a dita solução é a combinação.

De acordo com uma quarta variante, para pelo menos um grupo de ligações que participam para a realização de uma mesma função, dito feixe de ligações, cada ligação sendo de tipo multiponto e a rede sendo dividida em zonas distintas, aplica-se para cada uma das ligações do dito feixe, a cada caminho possível entre o terminal fonte e um terminal destinatário da dita ligação, uma restrição de não transposição de fronteira entre zonas se os comutadores ligados respectivamente ao terminal fonte e ao terminal destinatário pertencem à mesma zona, e, no caso contrário, uma restrição de transposição única da fronteira entre as zonas de pertença respectivas dos ditos terminais fonte e destinatário. Como precedentemente, será possível aplicar para cada ligação virtual e para cada um dos caminhos possíveis entre o terminai fonte e um terminal destinatário da dita ligação, restrições topológicas adicionais de segregação e/ou de colocação desses caminhos em relação a ligações virtuais já roteadas ou a rotear simultaneamente com a dita ligação ou a comutadores da dita rede.

Alternativamente ou cumulativamente, a etapa de seleção poderá levar em consideração restrições topológicas adicionais, cada restrição topológica adicional tendo como objeto um grupo de caminhos constitutivos de um conjunto de ligações virtuais a rotear simultaneamente, o dito grupo sendo constituído por uma pluralidade Nsg de subgrupos dos ditos caminhos, a dita restrição adicional exprimindo que no máximo um número nsg de subgrupos tal que 0 < nsg < Nsg podem ser invalidados, um subgrupo sendo invalidado se todos os caminhos que lhe pertencem são afetados pela falha de um mesmo comutador da dita rede.

A dita função de custo poderá ser tomada igual ao número de comutadores atravessados por um caminho e será minimizada, para cada uma das ligações do dito feixe, em cada conjunto de caminhos possíveis entre o terminal fonte e cada terminal destinatário da dita ligação, para fornecer pelo menos um caminho candidato por ligação e por terminal destinatário.

Vantajosamente, são efetuadas combinações de K1H-K2+...+Kn caminhos candidatos em que os Ki, 1 < i < N são os números de caminhos respectivos das N ligações do dito feixe, cada combinação correspondendo a uma solução possível de roteamento do dito feixe, e uma quarta função de custo é minimizada no conjunto das ditas soluções possíveis assim obtidas. A quarta função de custo avalia, para cada solução possível de roteamento do feixe, o número de comutadores atravessados pelas ligações do feixe que corresponde a essa solução.

Em todas as variantes acima, as ditas zonas da rede são por exemplo alimentadas por fontes de alimentação independentes.

Finalmente, qualquer que seja a variante, será minimizada vantajosamente uma quinta função de custo que avalia a carga de tráfego do comutador mais carregado da rede, no conjunto das soluções de roteamento obtidas por minimização de uma das segunda, terceira ou quarta funções de custo.

A invenção também se refere a um programa de computador que compreende meios se software adaptados para executar as etapas do processo definido mais acima, quando ele é executado por um computador.

BREVE DESCRIÇÃO DOS DESENHOS

A Fig. 1 representa esquematicamente um exemplo de rede AFDX;

a Fig. 2 representa esquematicamente um organograma do método de roteamento de ligações virtuais de acordo com um modo de realização da invenção;

as Figs. 3A a 3E ilustram um mecanismo de minimização de funções de custo no caso de uma ligação virtual de tipo multiponto;

a Fig. 4 ilustra um exemplo de roteamento para uma ligação virtual de tipo ponto a ponto;

a Fig. 5 ilustra um exemplo de roteamento para uma ligação virtual de tipo multiponto;

a Fig. 6 ilustra um exemplo de roteamento para um feixe de ligações virtuais de tipo ponto a ponto; a Fig. 7 ilustra um exemplo de roteamento para um feixe de ligações virtuais de tipo multiponto;

a Fig. 8 ilustra um exemplo de grupo de caminhos constitutivos de ligações virtuais, sujeitado a uma restrição de segregação relaxada;

a Fig. 9 ilustra um exemplo de roteamento de ligações virtuais sob restrição de segregação relaxada;

as Figs. 10A e IOB ilustram respectivamente uma configuração de roteamento aceitável e uma configuração de roteamento inaceitável.

EXPOSIÇÃO DETALHADA DE MODOS DE REALIZAÇÃO ESPECIAIS

A idéia na base a invenção é efetuar o roteamento de uma ligação virtual selecionando para isso entre os caminhos possíveis, aqueles que obedecem a uma restrição ou a uma pluralidade de restrições topológicas predeterminadas, e depois selecionar em seguida entre esses últimos, aquele ou aqueles que minimiza(m) uma função de custo predeterminada.

A Fig. 2 ilustra o princípio do processo de roteamento de acordo com a invenção.

O dito processo utiliza na entrada:

- um arquivo 210 que descreve a topologia da rede, a saber os nós extremais (terminais), os nós de comutação, as ligações físicas entre os nos;

- um arquivo 220 que dá o estado da rede, a saber as capacidades dos porás dos comutadores, os laços virtuais já roteados com suas características;

- um arquivo 230 que dá as características da ou das ligações virtuais a rotear. Cada ligação virtual é descrita aí pelos identificadores dos comutadores ligados respectivamente ao terminal fonte e ao terminal destinatário (modo ponto a ponto) ou aos terminais destinatários (modo multiponto), a duração do intervalo de transmissão (BAG) e o comprimento máximo dos quadros na ligação, a pertença eventual a um feixe funcional e, se for o caso, o identificador do feixe;

- um arquivo 240 de declaração de restrições topológicas que será descrito em detalhe mais adiante.

O algoritmo procede em uma primeira etapa 250 à seleção dos caminhos entre o terminal fonte e o terminal destinatário que satisfazem a uma restrição ou a uma pluralidade de restrições topológicas indicada(s) em 240.

O algoritmo procede em um segundo tempo, em 260, à minimização de uma função de custo ou à minimização de uma pluralidade de funções de custo, sucessivamente ou conjuntamente. Com finalidade de minimização conjunta, como detalhado mais adiante, uma função de custo compósita é construída como combinação linear das funções de custo precitadas, os coeficientes de ponderação sendo escolhidos de maneira a refletir as importâncias relativas dos custos na escolha do roteamento. Alternativamente, as funções de custo são minimizadas uma após a outra de acordo com uma ordem de prioridade decrescente, cada minimização sendo efetuada no subconjunto de soluções fornecidas pela etapa de minimização precedente.

Se a minimização da função de custo/das funções de custo dá varias soluções equivalentes, uma solução é escolhida de maneira arbitrária entre essas últimas. A solução na saída de 260 fornece o caminho (modo ponto a ponto) ou os caminhos (modo multiponto) que permitem rotear a ligação virtual. Na etapa 270, o arquivo de estado da rede 220 é atualizado. O algoritmo procede de maneira iterativa, até o esgotamento das ligações virtuais a rotear.

Em 280, é verificado se todas as ligações virtuais estão roteadas e, na afirmativa, procede-se, de acordo com um modo de realização, a uma etapa de verificação do determinismo da rede em 290. Essa etapa é assumida por um algoritmo denominado "network calculus" conhecido pelo estado da técnica, por exemplo pelo artigo de Jean-Yves Le Boudec intitulado "Application of network calculus to garanteed service networks" publicado em IEEE Trans. On Information Theory, Vol. 44, n° 3, Maio 1998. Esse algoritmo calcula a parir de um invólucro de trafego em todos os pontos da rede, os bornes de latência e os tamanhos de filas de espera para cada elemento da rede. O determinismo é garantido para uma latência limitada e um dimensionamento correto das filas de espera para cada elemento da rede.

Em último lugar, as tabelas de comutação dos comutadores de quadro são atualizadas em 295. Essas tabelas de comutação fixam de maneira unívoca o roteamento das ligações na rede.

O processo de roteamento pode ser executado uma primeira vez por ocasião da colocação em funcionamento da rede e/ou a cada vez que uma ligação virtual deve ser modificada ou acrescentada.

As restrições topológicas mencionadas mais acima são de dois tipos distintos: as restrições absolutas e as restrições relativas.

As restrições absolutas pesam no roteamento de uma ligação virtual independentemente da presença de outras ligações na rede. Por exemplo, no caso de uma rede AFDX embarcada em uma aeronave, os "lados" esquerdo e "direito" da rede, que correspondem aos lados "esquerdo" e "direito" do avião, são alimentados por barras de alimentação diferentes. A fim de que a falha de uma alimentação não coloque em perigo a totalidade da rede, as restrições topológicas seguintes são impostas:

- uma ligação virtual proveniente de um terminal fonte situado de um lado da rede e que chega a um terminal destinatário situado do lado oposto só pode atravessar uma vez a fronteira que separa os dois lados da rede. Se a ligação virtual é do tipo multiponto, a restrição se aplica a cada caminho constitutivo da ligação; - uma ligação virtual proveniente de um terminal fonte situado de um lado da rede e que serve um terminal destinatário situado do mesmo lado não pode atravessar a fronteira que separa os dois lados da rede.

Essa regra se generaliza sem dificuldade no caos em que a rede pode ser dividida em uma pluralidade qualquer de zonas distintas, sob reserva de que um terminal qualquer de uma zona possa servir um terminal qualquer de uma outra zona sem passar por uma terceira zona. As diferentes zonas da rede são por exemplo alimentadas por fontes de alimentação independentes. As ligações virtuais intra-zona são roteadas no seio da zona em questão enquanto que as ligações virtuais inter-zona só transpõem uma única vez a fronteira que separa as ditas zonas, isso sem passar por uma terceira zona.

Outras restrições topológicas absolutas podem ser fixadas como a colocação ou a segregação com um elemento da rede. Entende-se por aí que poderá ser especificado que a ligação virtual passa necessariamente por um elemento dado da rede (por exemplo um comutador ou uma ligação física) ou então ao contrário evita necessariamente esse elemento. Concebe-se que a colocação com vários elementos da rede possa levar a um roteamento unívoco da ligação virtual. A ligação virtual é então dita "fixada".

As restrições topológicas relativas se referem às ligações virtuais entre si. Assim, será possível fixar restrições de colocação ou de segregação entre ligações virtuais. Entende-se por aí que poderá ser especificado que duas ligações virtuais devem passar pelos mesmos comutadores da rede ou então ao contrário que essas últimas não devem partilhar nenhum comutador comum. As restrições topológicas relativas podem se referir a diferentes ligações virtuais de um mesmo feixe funcional, caso no qual a restrição posta é uma restrição de segregação. Elas podem também se referir a ligações virtuais que pertencem a feixes funcionais distintos. Nos dois casos, as restrições topológicas de colocação/segregação de uma ligação virtual podem ser expressas em relação a ligações já roteadas ou a ligações a rotear simultaneamente com a dita ligação.

Acontece que as restrições topológicas relativas formuladas em termos de colocação e/ou de segregação sejam estritas demais para permitir obter uma solução de roteamento. Nesse caso, algumas dessas restrições e mesmo todas são relaxadas como indicado abaixo.

Considera-se um conjunto de ligações virtuais cujo roteamento é realizado simultaneamente, seu roteamento individual não podendo ser considerado de maneira independente. Cada uma dessas ligações virtuais compreende em geral um (ligação ponto a ponto) ou vários (ligação multiponto) caminho(s). O conjunto dos caminhos constitutivos dessas ligações virtuais, abaixo denominado grupo de ligações virtuais, pode ser dividido em subgrupos, um caminho podendo pertencer a vários subgrupos. Geralmente um subgrupo corresponde a uma instancia da função assegurada pelo dito conjunto de ligações virtuais. Em outros termos, os diferentes subgrupos representam um certo grau de redundância para a realização de uma mesma função.

Se Nsg é o número de subgrupos do grupo de caminhos, impõe- se ao dito conjunto de ligações virtuais uma restrição de segregação relaxada de acordo com a qual no máximo nsg subgrupos entre Nsg, com O < nsg < Nsg, podem ser invalidados pela falha de um comutador. O caso nsg = O corresponde à situação especial na qual não se tolera nenhum subgrupo invalidado. Por falha de um comutador, entende-se aqui ou uma comutação errada ou ausente, ou uma corrupção dos quadros comutados. Por subgrupo invalidade, entende-se um subgrupo do qual todos os caminhos são afetados pela falha do mesmo comutador.

Se compreenderá que uma restrição de segregação relaxada oferece mais flexibilidade do que uma restrição de segregação na medida em que ela leva em consideração a redundância da rede e não se aplica de maneira indiferenciada a todos os caminhos constitutivos de uma ligação virtual.

Exemplos de restrições de segregação relaxadas são dados em anexo.

Como foi visto mais acima, depois de ter selecionado um subconjunto de candidatos possíveis que satisfazem às restrições topológicas precitadas, o algoritmo de roteamento procura entre os candidatos possíveis aquele ou aqueles que minimiza(m) uma ou várias funções de custo.

Uma primeira função de custo considerada é o número de comutadores atravessados pela ligação virtual. Mais precisamente, se a ligação é de tipo ponto a ponto, procura-se minimizar o número de comutadores atravessados por essa ligação. Se a ligação é de tipo multiponto, a minimização tem como objeto o número de comutadores atravessados para cada um dos caminhos constitutivos da ligação. Um pequeno número de comutadores atravessados permite reduzir a probabilidade de falha da ligação virtual ou de cada caminho constitutivo dessa ligação.

Uma segunda função de custos se refere às ligações virtuais de tipo multiponto. Ela é definida como o número de comutadores comuns aos caminhos constitutivos de uma ligação de tipo multiponto.

Uma terceira função de custo se refere aos feixes de ligações. Ela é definida como o número de comutadores comuns às ligações virtuais que pertencem a um mesmo feixe.

A minimização da segunda ou da terceira função de custo permite, de acordo com o caso, reduzir a probabilidade de falha conjunta dos caminhos de uma mesma ligação virtual ou das ligações virtuais de um mesmo feixe.

Uma quarta função de custo se refere também aos feixes de ligações. Ela é definida como o número total de comutadores atravessados por todas as ligações virtuais de um mesmo feixe.

Uma quinta função de custo é definida como a vazão do port de saída do comutador mais carregado da rede. A minimização dessa função de custo visa repartir do melhor modo possível a carga de trafego no seio da rede.

Esses exemplos de funções de custo não são em nenhum caso limitativos. Outras funções de custo podem ser consideradas, na medida em que elas visam notadamente quantificar o impacto da falha de um elemento ou de uma pluralidade de elementos da rede.

A minimização sucessiva das funções de custo pode levar a um conjunto de soluções sub-ótimas. De acordo com uma variante de realização, é construída uma combinação linear das funções de custo com o auxílio de coeficientes de ponderação que refletem a importância relativa dessas funções no roteamento e minimiza-se a nova função de custo assim construída no conjunto das soluções possíveis. De maneira similar, a nova função de custo pode ser construída como produto das funções de custo, cada uma delas tendo atribuído um expoente que reflete sua importância relativa no roteamento.

As Figs. 3A a 3E ilustram o mecanismo de minimização das funções de custo no caso de uma ligação virtual do tipo multiponto.

A ligação virtual a rotear é proveniente do terminal fonte Ei e serve os terminais destinatários Ri e R2. Supõe-se que os caminhos satisfatórios para as restrições topológicas foram previamente selecionados. A minimização da primeira função de custo é efetuada procurando-se para cada um dos caminhos possíveis que ligam Ei a Ri por um lado e Ej a R2, por outro lado, aqueles que atravessam o número mínimo de comutadores. No caso presente, o número mínimo é de 3 para o caminho ErR, como para o caminho ErR2. As soluções ótimas estão ilustradas nas Figs. 3A a 3D. Ao contrário, será notado que a solução ilustrada na Fig. 3E não é ótima: de fato, ela minimiza o número de comutadores no conjunto da ligação virtual mas não em cada um de seus caminhos constitutivos (o caminho que liga Ei-R2 é de custo 4).

A minimização da segunda função de custo leva a reter entre as quatro soluções precedentes, aquelas ilustradas nas Figs. 3A, 3B e 3D. De fato para essas últimas, o número de comutadores comuns entre os dois caminhos é igual a 1 enquanto que ele é igual a 2 para aquela da Fig. 3C.

A minimização da quinta função de custo permite desempatar as três soluções retidas na etapa precedente. Na falta disso, a solução escolhida é escolhida de maneira arbitrária entre as soluções restantes.

O problema do roteamento se torna aquele de uma minimização de uma função de custo/de funções de custo sob restrições. Vantajosamente, as funções de custo sob restrições são expressas sob a forma de desigualdades lineares e as funções de custo são expressões lineares de variáveis de decisão. A minimização pode então ser efetuada graças ao algoritmo simplex. E lembrado que o algoritmo do simplex permite resolver um problema do tipo:

Arg min(b x) com Ax > c e χ > 0 (1)

em que b é o vetor representativo de uma forma linear (função de custo), χ é o vetor das variáveis de decisão (positivas), A representa a matriz das restrições e c é um vetor constante.

Na prática, o algoritmo de roteamento dispõe na entrada da lista dos comutadores, anotada SS e, para cada par de terminais fonte e destinação, da lista dos caminhos que permitem passar do primeiro ao segundo, cada caminho sendo descrito por uma lista ordenada dos comutadores que ele atravessa. Será anotada na seqüência como PP a lista de caminhos repertoriados. Vantajosamente PP será previamente reduzido a uma lista de caminhos que já satisfazem certas restrições topológicas absolutas, por exemplo aquelas relativas à participação em zonas independentes.

São então construídas as matrizes Cps, Cfs, Cis, Cpss as três primeiras tendo uma dimensão PxSea última uma dimensão PxSxS em que P é o número total de caminhos repertoriados no arquivo e S é o número total de comutadores da rede, os elementos dessas matrizes sendo definidos por:

cps(p, sw) = 1 se sw pertence ao caminho ρ e cps(p, sw) = 0 senão;

cfs(p, sw) = 1 se sw é o primeiro comutador de ρ e CfS(p, sw) = 0 senão;

cis(p, sw) = 1 se sw é o último comutador de ρ e cis(p, sw) = 0 senão;

cpss(p, SW1, sw2) = 1 se Sw1 e sw2 são comutadores sucessivos do caminho ρ e cpss(p, Sw1, sw2) = 0 senão;

onde ρ é o identificador de um caminho entre os dois terminais e onde sw, Sw1, sw2 são identificadores de comutadores da rede.

Para simplificar o algoritmo de roteamento é considerado que qualquer ligação virtual faz parte de um feixe funcional, o feixe podendo se reduzir se for o caso a uma só ligação. E anotada FF a lista dos feixes funcionais.

Um feixe f de FF é determinado por seus atributos:

- f.profile que indica se o feixe f contém uma só ligação virtual (f.profile = 1) ou não ( f.profile = 0);

- f.ocs que dá a lista dos identificadores das ligações virtuais que fazem parte do feixe.

Uma ligação virtual vl de um feixe f é definida por seus atributos:

- vl. f que dá o identificador do feixe ao qual a ligação pertence;

- vl.cost que indica o custo em termo de trafego na ligação virtual; esse custo pode ser expresso por exemplo em função do par intervalo de transmissão e comprimento máximo de quadro; - vl.rted que indica se a ligação já está roteada (vl.rted = 1) ou não (vl.rted = 0);

- vl.txsw que dá o identificador do comutador ligado ao terminal fonte;

- v1.rxsw que dá o identificador do comutador ligado ao terminal destinatário (ligação de tipo ponto a ponto) ou os identificadores dos comutadores respectivamente ligados aos terminais destinatários (ligação multiponto).

Um caminho b constitutivo de uma ligação virtual vl é definido por seus atributos:

- b.v1 identificador da ligação virtual à qual ele pertence;

- b.swDest identificador do comutador ligado ao terminal destinatário servido pelo dito caminho.

Por outro lado, é anotada GG a lista dos grupos de caminhos constitutivos de ligações virtuais submetidas a uma restrição de segregação relaxada. Cada grupo g de GG é definido por:

- um atributo g.sgErrmax que indica o número máximo aceitável de subgrupos invalidados no grupo;

- a lista de seus subgrupos g.sglist.

Finalmente, é anotada SG a lista dos subgrupos relativos aos diferentes grupos de GG. Cada subgrupo sg de SG é definido por:

- um atributo sg.group que indica o grupo ao qual ele pertence;

- a lista sg.pathlist dos caminhos constitutivos desse subgrupo.

São introduzidas por outro lado as variáveis de decisão seguintes, todas com valores positivos:

- vlPath[vl,p] é igual a 1 se o caminho ρ é constitutivo da ligação virtual vl e igual a 0 senão. É lembrado que um caminho ρ é constitutivo de vl se esse caminho parte do comutador ligado ao terminal vl.txsw e chega a um dos comutadores de vl.rxsw; - vlBrSw[vl,swDest,sw] é igual a 1 se o caminho constitutivo da ligação virtual vl que se termina por swDest passa pelo comutador sw e igual a 0 senão;

- vlBrPerSw[vl,sw] é igual ao número de caminhos constitutivos da ligação virtual vl que passa pelo comutador sw;

- comBrSw[vl,sw] é igual a 1 se vários caminhos constitutivos da ligação virtual vl passam pelo comutador sw;

- vlSw[vl,sw] é igual a 1 se a ligação virtual vl passa pelo comutador sw e a 0 senão;

- fVlPersw[ f ,sw] é igual ao número de ligações virtuais do feixe funcional f que passa pelo comutador sw;

- comfSw[ f,sw] é igual a 1 se várias ligações virtuais do feixe funcional f passa pelo comutador sw e a 0 senão;

-fSw[f,sw] é igual a 1 se uma das ligações virtuais do feixe funcional ( passa pelo comutador sw e a 0 senão;

- vlSwNb[vl,sw!,sw2] é igual ao número de caminhos constitutivos da ligação virtual vl que passa sucessivamente pelos comutadores swi, sw2;

- vlSw[vl,swi,sw2] é igual a 1 se existe um caminho constitutivo da ligação virtual vl que passa sucessivamente pelos comutadores Sw1, sw2;

- trfCst[swi,sw2] é a soma de trfCstPast[sw!,sw2] e do custo de trafego entre os comutadores Swh sw2 cumulado no subconjunto corrente de ligações virtuais a rotear;

- fixvl[sw!,sw2] é igual a 1 se existe uma ligação virtual já roteada do dito subconjunto corrente, que passa sucessivamente pelos comutadores swi e sw2 e igual a 0 senão;

- sgSw[sg,sw] é igual a 1 se o comutador sw é comum a todos os caminhos constitutivos do subgrupo sg e igual a 0 senão. <formula>formula see original document page 23</formula>

A restrição de base que é imposta a uma solução (ou ligação virtual candidata) é que o(s) caminho(s) constitutivo(s) da solução seja(m) proveniente(s) do terminal fonte e chegue(m) ao(s) terminal(ais) destinatário(s), quer dizer:

e que, para cada terminal destinatário da ligação virtual, haja um só caminho constitutivo proveniente do terminal fonte, ou seja:

<formula>formula see original document page 23</formula>

A maior parte das restrições topológicas absolutas são suscetíveis do mesmo formalismo. As restrições restantes são levadas em consideração, como indicado mais acima, restringindo-se desde o início o conjunto PP.

As restrições topológicas relativas podem também ser expressas a partir das variáveis de decisão precitadas sob a forma de desigualdades ou de igualdades lineares. Assim, para cada conjunto Π de caminhos constitutivos que devem ser segregados, quer dizer que não podem partilhar nenhum comutador comum, a restrição de segregação é expressa por:

<formula>formula see original document page 23</formula>

De maneira similar, para um conjunto Π de caminhos constitutivos que devem ser submetidos a uma restrição de colocação, quer dizer que devem passar pelos mesmos comutadores;

<formula>formula see original document page 23</formula> Naturalmente, as restrições devem ser verificadas para todas as instâncias de segregação e de colocação a levar em consideração, a cada instância sendo associado um conjunto Π determinado.

Alternativamente, se são utilizadas restrições de segregação relaxadas, se colocará para qualquer grupo geGG de caminhos constitutivos de ligações virtuais, sujeito a uma tal restrição:

<formula>formula see original document page 24</formula>

na qual a variável de decisão sgSw[sg,sw] é definida pelas restrições seguintes:

<formula>formula see original document page 24</formula>

As expressões (5") implicam de fato:

<formula>formula see original document page 24</formula>

As funções de custo são expressas também a partir das variáveis de decisão precitadas.

Por exemplo, a primeira função de custo CF1 que visa minimizar independentemente o número de comutadores atravessados pelos caminhos constitutivos de uma ligação virtual pode ser expressa por: <formula>formula see original document page 25</formula>

onde card(p) é a cardinalidade da lista ordenada p, dito de outro modo o número de comutadores atravessados pelo caminho p.

E possível mostrar matematicamente que a segunda função de custo, que visa minimizar o número de comutadores comuns aos diferentes caminhos de cada ligação virtual de tipo multiponto pode ser expressa por:

<formula>formula see original document page 25</formula>

De maneira similar, a terceira função de custo, que visa minimizar o número de comutadores comuns às ligações virtuais de um mesmo feixe funcional pode ser escrita:

<formula>formula see original document page 25</formula>

E possível também mostrar que a quarta função de custo, que visa minimizar o número de comutadores atravessados pelas ligações de um feixe funcional pode ser expressa simplesmente por:

<formula>formula see original document page 25</formula>

A quinta função de custo visa rotear as ligações virtuais de maneira a passar pelos comutadores menos carregados. É possível determinar a partir do arquivo de estado da rede e das ligações a rotear o custo de tráfego entre dois comutadores adjacentes. São chamados aqui comutadores adjacentes comutadores swh sw2 ligados por uma ligação física direta. Mais precisamente, determina-se primeiramente para cada par qualquer de comutadores adjacentes Sw1, sw2, se existe pelo menos uma ligação virtual que passa sucessivamente por esses últimos:

<formula>formula see original document page 26</formula>

A variável de decisão vlSw[vl,swi,sw2] é expressa em função de vlSwNb[vl,swl,sw2] com o auxílio das restrições lineares seguintes:

<formula>formula see original document page 26</formula>

Essejogo de restrições lineares implica de fato:

vlSw[vl,sw1,sw2] = 0 se vlSwNb[vl,sw1,sw2] = 0 vlSw[vl,sw1,sw2] = 1 se vlSwNb[vl,sw1,sw2] > 1 (12)

Do mesmo modo exprime-se a variável de decisão fixvl[sw1,sw2] em função da soma

<formula>formula see original document page 26</formula>

com o auxílio das restrições lineares seguintes:

<formula>formula see original document page 26</formula>

COM M = F.max(Card(f.ocs)) Onde F = Card(WF) Essejogo de restrições lineares implica de fato:

<formula>formula see original document page 27</formula>

Avalia-se em seguida o custo de trafego do port de saída de Sw1 conectado a sw2, para um par qualquer de comutadores adjacentes: e SS;

<formula>formula see original document page 27</formula>

onde trfCstPast[swi,sw2] é o custo de trafego entre os comutadores swi, sw2 quer dizer no port de saída de swi ligado a sw2, cumulado em todas as ligações virtuais já roteadas.

Dito de outro modo, o cálculo de trafego é efetuado nas ligações já roteadas (vl.rted = 1) e nas ligações a rotear (vl.rted = 0). O valor trfCstPast[swl5sw2] é inicializado pelo valor do custo de trafego induzido pelas ligações virtuais fixadas, quer dizer cujo roteamento é unívoco. Ele pode ser estocado no arquivo de estado da rede.

A quinta função de custo é expressa então sob a forma seguinte:

<formula>formula see original document page 27</formula>

impondo-se para isso as restrições lineares: <formula>formula see original document page 28</formula>

Esse jogo de restrições lineares implica de fato para qualquer par de comutadores Sw1, sw2:

<formula>formula see original document page 28</formula>

Isso permite só considerar na variável de decisão trfCstw[swl5sw2] a contribuição das ligações virtuais a rotear e, entre essas últimas, somente aquelas que passam por Sw1, sw2.

Se é desejado efetuar uma minimização conjunta das funções de custo, constrói-se uma nova função

<formula>formula see original document page 28</formula>

combinação linear das funções CF, com os coeficientes de ponderação O ≤ αi ≤ 1. É em definitivo a procura do mínimo da função de custo CF que dá a solução ótima de roteamento sob a forma de valores das variáveis de decisão. Se várias soluções ótimas existem no sentido precedente, uma entre elas é escolhida de maneira arbitrária.

Alternativamente, as funções de custo podem ser minimizadas uma após a outra, por ordem de prioridade decrescente, cada uma delas estando no subconjunto de soluções fornecidas pela etapa de minimização precedente. Nesse modo de realização, restrições podem ser levadas em consideração entre as etapas de minimização. Que seja por minimização conjunta ou sucessiva das funções de custo, a otimização global no conjunto FF pode acarretar tempos de cálculo muito longos se o número de ligações virtuais é elevado.

Divide-se então vantajosamente esse conjunto em subconjuntos independentes de menos cardinalidade possível, as restrições topológicas relativas e a minimização das funções de custo se aplicando somente no seio de cada subconjunto. Visto que as ligações virtuais de um mesmo feixe funcional não podem ser roteadas independentemente, cada subconjunto é necessariamente constituído por um ou vários feixes. O algoritmo de roteamento é aplicado em seqüência aos ditos subconjuntos.

E conveniente notar entretanto que a independência dos subconjuntos pode não ser total. Assim, a minimização de função de custo CF5 faz em princípio intervir todas as ligações virtuais a rotear. Nesse caso, privilegia-se os subconjuntos de ligações virtuais para os quais a liberdade de roteamento é a menor,por exemplo aqueles dos quais as ligações serão a priori as mais curtas, esses subconjuntos sendo tratados em prioridade pelo processo de roteamento.

Exemplos de roteamento de acordo com a invenção serão dados abaixo para uma rede embarcada. Nesses exemplos, as funções de custo são minimizadas sucessivamente. A unidade de roteamento considerada é aqui o feixe funcional, uma ligação virtual sendo considerada como um feixe de uma só ligação.

A Fig. 4 ilustra esquematicamente um exemplo de roteamento de ligação virtual (ou feixe monoligação) de tipo ponto a ponto, entre um terminal fonte E1 e um terminal destinatário Rj.

Na etapa 410, aplica-se a restrição de base para determinar os caminhos possíveis entre o terminal fonte e o terminal destinatário.

Na etapa 420, aplica-se as restrições topológicas relativas, levando-se em consideração as ligações já roteadas, se elas existirem, e depois determina-se em 430 se os terminais estão do mesmo lado da rede. Se esse for o caso, aplica-se em 435 uma restrição de não transposição (roteamento intra- zona) e minimiza-se a função de custo CF1 no conjunto das soluções possíveis selecionadas pelas restrições precedentes. Em contrapartida, se os terminais não estão do mesmo lado da rede, aplica-se em 437 uma restrição de transposição (uma só transposição inter-zona) e minimiza-se, como para o primeiro caso, a função de custo CF1 no conjunto das soluções possíveis.

Se as etapas 435 ou 437 não fornecem uma solução de roteamento único, prossegue-se minimizando-se em 440 a função de custo CF5 nas soluções restantes. Atualiza-se o arquivo de estado da rede em 450.

A Fig. 5 ilustra esquematicamente um exemplo de roteamento de ligação virtual (ou feixe monoligação) de tipo multiponto, entre um terminal fonte E1 e uma pluralidade k de terminais destinatários Ri, R2, ..., Rk-

Para cada par de terminais (Ei, Rk) aplica-se em 5IO1, 5IO2, ..., 510K a restrição de base de maneira a só reter os caminhos possíveis entre E1 por um lado e R1, R2,..., Rk por outro lado.

Em 5201? 5202, ..., 520K aplica-se individualmente aos diferentes caminhos, as restrições topológicas relativas levando-se para isso em consideração as ligações já roteadas.

Em cada uma dos K conjuntos de caminhos possíveis minimiza-se individualmente a função de custo CF1, em 5301; 5302, ..., 530K, respectivamente.

Efetua-se em seguida em 540 todas as combinações dos caminhos dados por 5301? 5302, ..., 530K, respectivamente. Obtém-se assim um conjunto de soluções de roteamento possíveis para a ligação virtual em questão.

Minimiza-se então em 550 a função de custo CF2 no conjunto dessas soluções possíveis.

Se a etapa 550 não fornece uma solução única, minimiza-se em 560 a função de custo CF4 no conjunto das soluções restantes.

Se a etapa ainda não fornece uma solução única, a função de custo CF5 é minimizada em 570 no conjunto das soluções restantes e atualiza- se o arquivo de estada da rede em 580.

A Fig. 6 ilustra esquematicamente um exemplo de roteamento de feixe de N ligações virtuais de tipo ponto a ponto. Cada ligação é proveniente de um terminal fonte Ei e serve um terminal destinatário Ri, 1 < i <N.

Para cada par de terminais (Ei, Ri) aplica-se em 610i a restrição de base de maneira a só reter os caminhos possíveis entre Ei e Ri.

As etapas i, 630;, 640 são análogas às etapas 520k, 530k, 540 com exceção de que obtém-se em 640 todas as soluções possíveis de roteamento para o feixe de ligações..

Minimiza-se em seguida em 650 a função de custo CF3 no conjunto das soluções possíveis.

Se a etapa 650 não fornece uma solução única, minimiza-se em 660 a função de custo CF4 no conjunto das soluções restantes.

Se a etapa 660 ainda não fornece uma solução única, a função de custo CF5 é minimizada em 670 no conjunto das soluções restantes e atualiza-se o arquivo de estado da rede em 680.

A Fig. 7 ilustra esquematicamente um exemplo de roteamento de feixe de N ligações virtuais de tipo multiponto. Supõe-se que cada ligação virtual VLi é proveniente de um terminal fonte Ei e serve Ki terminais destinatários R;k com l<i<Nel<k<K;.

Aplica-se em 701i a restrição de base para todos os pares de terminais (Ei, Rnc), 1 < k < Ki e depois em 720i as restrições topológicas relativas como na Fig. 5.

Obtém-se na saída de 720; K; conjuntos Pik de caminhos possíveis para constituir a ligação virtual VLi, um conjunto Pik sendo relativo a um par (Ei, Rik) dado.

Na etapa 73 Oi minimiza-se a função de custo CFi em cada um desses conjuntos, como nas etapas 530j a 530k da Fig. 5.

Na etapa 740, efetua-se todas as combinações possíveis de todos os caminhos retidos na etapa 73Oi ficando entendido que, para cada combinação, só se seleciona um caminho por par (Ei, Rik). Cada combinação corresponde assim a K1 + K2 + ... + Kn caminhos retidos. Obtém-se assim um conjunto de soluções de roteamento possíveis para as diferentes ligações virtuais VLi, quer dizer um conjunto de soluções de roteamento possíveis do feixe.

O resto do organograma é idêntico àquele da Fig. 6, as etapas 750, 760, 770 e 780 sendo respectivamente idênticas àquelas representadas em 650, 660, 670 e 680. Anexo

As restrições de segregação relaxadas têm geralmente como objeto um grupo de caminhos constitutivos de ligações virtuais a rotear simultaneamente.

Foi representado simbolicamente na Fig. 8 um tal grupo de caminhos.

Será suposto que três ligações virtuais VLi, VL2, VL3 devem ser roteadas simultaneamente e que seus caminhos constitutivos são:

<formula>formula see original document page 33</formula>

No exemplo ilustrado, o grupo GG de caminhos submetidos à restrição de segregação relaxada é dividido em Nsg = 4 subgrupos

<formula>formula see original document page 33</formula>

A restrição de segregação relaxada é expressa por um número máximo nsg < Nsg de subgrupos que podem ser invalidados pela falha de um mesmo comutador (por exemplo, a falha de um comutador afetará os caminhos COPIAR AS EXPRESSÕES NA PÁGINA 41 LINHA 25 de sgi). Dito de outro modo, pelo menos Nsg - nsg subgrupos devem cada um deles conter pelo menos um caminho não corrompido pela falha de um comutador.

Um exemplo de aplicação de restrição de segregação relaxada é dado abaixo. Considera-se o roteamento de ligações virtuais entre os sistemas de gestão de vôo denominados FMS (Flight Management System) e os computadores de comando de vôo denominados FCGU (Flight Control and Guidance Unit). Os primeiros são classicamente encarregados de assistir o piloto nas operações de navegação e de gestão do vôo. Os segundos calculam as ordens de guia e de servocomando dos comandos de vôo.

Será suposto que a aeronave compreende dois sistemas FMS e quatro computadores FCGU, cada sistema FMS estando na origem de uma ligação virtual (multiponto) com destinação dos quatro computadores FCGU, como ilustrado na Fig. 9. A arquitetura representada é de tipo "cross-check": cada computador FCGU recebe parâmetros de vôo dos dois sistemas FMS e efetua uma comparação dos mesmos. Se os parâmetros recebidos por um mesmo computador diferem, o computador assinala um erro e não efetua nenhum tratamento sobre o parâmetro. As exigências de segurança impõem que um erro em um parâmetro não permaneça não detectado por mais de um computador. E anotado a o parâmetro transmitido pelos sistemas FMS e mesmo um quadro de tais parâmetros, suposto(s) correto(s) e a* um parâmetro errado recebido por um computador FCGU e mesmo um quadro errado de parâmetros, o erro sendo devido à falha de um comutador.

Como ilustrado nas Figs. 10 A e 10B, um computador pode não detectar erro em caso de corrupção bilateral (caso de FCGUia na Fig. 10A e de FCGUia e FCGU2A na Fig. 10B), quando os dois parâmetros errados/quadros errados são idênticos. Essa situação não deve se produzir para mais de um computador. Assim, a situação ilustrada na Fig. 1OA (um só erro não detectado) é aceitável enquanto que aquela na Fig. IOB (dois erros não detectados) não o é.

Considera-se o grupo GG constituído pelos caminhos constitutivos pelas duas ligações virtuais a rotear:

<formula>formula see original document page 34</formula>

e divide-se o grupo GG em quantos subgrupos quantos forem os computadores FCGU ou seja sgi, sg2, sg3, Sg4, cada subgrupo contendo os dois caminhos provenientes dos sistemas FMS com destinação ao computador considerado. Impõe-se então que a falha de um comutador invalida no máximo um subgrupo (nsg =1) entre os 4 (Nsg = 4). Essa restrição de segregação relaxada permite se assegurar que no máximo um computador FCGU não diagnostica um erro em conseqüência da falha de um comutador da rede.

Claims (26)

1. Processo de roteamento de ligações virtuais em uma rede de comutação de quadros que compreende uma pluralidade de terminais fontes e/ou destinatários dos ditos quadros, comutadores de quadros sendo ligados entre si por ligações físicas, cada ligação virtual sendo definida, para um tipo ponto a ponto, por um caminho através da dita rede entre um terminal fonte e um terminal destinatário e, para um tipo multiponto, por uma pluralidade de caminhos através da dita rede entre um terminal fonte por um lado e uma pluralidade de terminais destinatários, por outro lado, o dito processo sendo caracterizado pelo fato de que, para pelo menos uma ligação virtual, ele compreende as etapas seguintes: (a) seleção (250) entre um conjunto de caminhos possíveis entre o terminal fonte e o ou os terminal(ais) destinatário(s), de um subconjunto de caminhos que satisfazem a pelo menos uma restrição topológica predeterminada; (b) determinação (260) entre o dito subconjunto, de um caminho, para uma ligação virtual de tipo ponto a ponto ou de uma pluralidade de caminhos, para uma ligação virtual de tipo multiponto, que minimiza pelo menos uma função de custo dada; (c) roteamento (295) da dita ligação virtual de acordo com o ou os caminho(s) assim determinado(s).

2. Processo de roteamento de acordo com a reivindicação 1, caracterizado pelo fato de que, a dita ligação virtual sendo uma ligação ponto a ponto e a rede sendo dividida em zonas distintas, a dita restrição topológica é uma restrição (435) de não transposição de fronteira entre zonas se os comutadores ligados respectivamente ao terminal fonte e ao terminal destinatário pertencem à mesma zona, a dita restrição topológica aplicada sendo, no caso contrário, uma restrição (437) de transposição única da fronteira entre as zonas de pertença respectivas dos ditos terminais fonte e destinatário.

3. Processo de roteamento de acordo com a reivindicação 1 ou 2, caracterizado pelo fato de que a etapa de seleção leva em consideração restrições topológicas adicionais (420) de segregação e/ou de colocação dos caminhos possíveis em relação às ligações virtuais já roteadas ou a rotear simultaneamente com a dita ligação ou a comutadores da dita rede.

4. Processo de roteamento de acordo com a reivindicação 1 ou 2, caracterizado pelo fato de que a etapa de seleção leva em consideração restrições topológicas adicionais, cada restrição topológica adicional tendo como objeto um grupo de caminhos constitutivos de um conjunto de ligações virtuais a rotear simultaneamente, o dito grupo sendo constituído por uma pluralidade Nsg de subgrupos dos ditos caminhos, a dita restrição adicional exprimindo que no máximo um número nsg de subgrupos tal que 0 < nsg < Nsg podem ser invalidados, um subgrupo sendo invalidado se todos os caminhos que lhe pertencem são afetados pela falha de um mesmo comutador da dita rede.

5. Processo de roteamento de acordo com a reivindicação 2, 3 ou 4, caracterizado pelo fato de que a dita função de custo (440) é número de comutadores atravessados por um caminho.

6. Processo de roteamento de acordo com a reivindicação 1, caracterizado pelo fato de que a dita ligação virtual sendo de tipo multiponto e a rede sendo dividida em zonas distintas, aplica-se a cada caminho possível entre o dito terminal fonte e um terminal destinatário da dita ligação, uma restrição (520i, ..., 520K) de não transposição de fronteira entre zonas se os comutadores ligados respectivamente ao terminal fonte e ao dito terminal destinatário pertencem à mesma zona, a dita restrição topológica aplicada sendo, no caso contrário, uma restrição de transposição única da fronteira entre as zonas de pertença respectivas dos ditos terminais fonte e destinatário.

7. Processo de roteamento de acordo com a reivindicação 6, caracterizado pelo fato de que aplica-se (520l,..., 520K) para cada um dos caminhos possíveis entre o dito terminal fonte e um terminal destinatário da dita ligação, restrições topológicas adicionais de segregação e/ou de colocação desses caminhos em relação a ligações virtuais já roteadas ou a rotear simultaneamente com a dita ligação ou a comutadores.

8. Processo de roteamento de acordo com a reivindicação 6, caracterizado pelo fato de que a etapa de seleção leva em consideração restrições topológicas adicionais, cada restrição topológica adicional tendo como objeto um grupo de caminhos constitutivos de um conjunto de ligações virtuais a rotear simultaneamente, o dito grupo sendo constituído por uma pluralidade Nsg de subgrupos dos ditos caminhos, a dita restrição adicional exprimindo que no máximo um número nsg de subgrupos tal que 0 ≤ nsg < Nsg podem ser invalidados, um subgrupo sendo invalidado se todos os caminhos que lhe pertencem são afetados pela falha de um mesmo comutador da dita rede.

9. Processo de roteamento de acordo com a reivindicação 6, 7 ou 8 caracterizado pelo fato de que a dita função de custo é o número de comutadores atravessados por um caminho e que ela é minimizada (530i, ..., -530K) em cada conjunto de caminhos possíveis entre o dito terminal fonte e um terminal destinatário da dita ligação, para fornecer pelo menos um caminho candidato por terminal destinatário.

10. Processo de roteamento de acordo com a reivindicação 9, caracterizado pelo fato de que são efetuadas (540) combinações de K caminhos candidatos em que K é o número de terminais destinatários da ligação, cada combinação correspondendo a uma solução possível de roteamento da dita ligação multiponto, e que uma segunda função de custo é minimizada (550) no conjunto das ditas soluções possíveis assim obtidas.

11. Processo de roteamento de acordo com a reivindicação 10, caracterizado pelo fato de que a segunda função de custo avalia, para cada solução possível, o número de comutadores partilhados entre seus diferentes caminhos constitutivos.

12. Processo de roteamento de acordo com a reivindicação 1, caracterizado pelo fato de que para pelo menos um grupo de ligações que participam para a realização de uma mesma função, dito feixe de ligações, cada ligação sendo ponto a ponto e a rede sendo dividida em zonas distintas, aplica-se para cada uma das ligações do dito feixe (6201, ..., 620N), a cada caminho possível entre o terminal fonte e o terminal destinatário da dita ligação, uma restrição de não transposição de fronteira entre zonas se os comutadores ligados respectivamente ao terminal fonte e ao terminal destinatário pertencem à mesma zona, e, no caso contrário, uma restrição de transposição única da fronteira entre as zonas de pertença respectivas dos ditos terminais fonte e destinatário.

13. Processo de roteamento de acordo com a reivindicação 12, caracterizado pelo fato de que aplica-se (620i, ..., 620K) para cada ligação virtual e para cada um dos caminhos possíveis entre o terminal fonte e o terminal destinatário da dita ligação, restrições topológicas adicionais de segregação e/ou de colocação desses caminhos em relação a ligações virtuais já roteadas ou a rotear simultaneamente com a dita ligação ou a comutadores.

14. Processo de roteamento de acordo com a reivindicação 12, caracterizado pelo fato de que a etapa de seleção leva em consideração restrições topológicas adicionais, cada restrição topológica adicional tendo como objeto um grupo de caminhos constitutivos de um conjunto de ligações virtuais a rotear simultaneamente, o dito grupo sendo constituído por uma pluralidade Nsg de subgrupos dos ditos caminhos, a dita restrição adicional exprimindo que no máximo um número nsg de subgrupos tal que 0 < nsg < Nsg podem ser invalidados, um subgrupo sendo invalidado se todos os caminhos que lhe pertencem são afetados pela falha de um mesmo comutador da dita rede.

15. Processo de roteamento de acordo com a reivindicação 12, 13 ou 14 caracterizado pelo fato de que a dita função de custo é o número de comutadores atravessados por um caminho e que ela é minimizada (6301, ..., 630N), para cada uma das ligações do dito feixe, em cada conjunto de caminhos possíveis entre o terminal fonte e o terminal destinatário da dita ligação, para fornecer pelo menos um caminho candidato por ligação.

16. Processo de roteamento de acordo com a reivindicação 15, caracterizado pelo fato de que são efetuadas (640) combinações de N caminhos candidatos em que N é o número de ligações do dito feixe, cada combinação correspondendo a uma solução possível de roteamento do dito feixe, e que uma terceira função de custo é minimizada (650) no conjunto das ditas soluções possíveis assim obtidas.

17. Processo de roteamento de acordo com a reivindicação 16, caracterizado pelo fato de que a terceira função de custo avalia, para cada solução possível de roteamento do feixe, o número de comutadores partilhados entre os caminhos dos quais a dita solução é a combinação.

18. Processo de roteamento de acordo com a reivindicação 1, caracterizado pelo fato de que, para pelo menos um grupo de ligações que participam para a realização de uma mesma função, dito feixe de ligações, cada ligação sendo de tipo multiponto e a rede sendo dividida em zonas distintas, aplica-se para cada uma das ligações do dito feixe (720i, ..., 720N), a cada caminho possível entre o terminal fonte e um terminal destinatário da dita ligação, uma restrição de não transposição de fronteira entre zonas se os comutadores ligados respectivamente ao terminal fonte e ao terminal destinatário pertencem à mesma zona, e, no caso contrário, uma restrição de transposição única da fronteira entre as zonas de pertença respectivas dos ditos terminais fonte e destinatário.

19. Processo de roteamento de acordo com a reivindicação 18, caracterizado pelo fato de que aplica-se (720χ, ..., 770N) para cada ligação virtual e para cada um dos caminhos possíveis entre o terminal fonte e um terminal destinatário da dita ligação, restrições topológicas adicionais de segregação e/ou de colocação desses caminhos em relação a ligações virtuais já roteadas ou a rotear simultaneamente com a dita ligação ou a comutadores da dita rede.

20. Processo de roteamento de acordo com a reivindicação 18, caracterizado pelo fato de que a etapa de seleção leva em consideração restrições topológicas adicionais, cada restrição topológica adicional tendo como objeto um grupo de caminhos constitutivos de um conjunto de ligações virtuais a rotear simultaneamente, o dito grupo sendo constituído por uma pluralidade Nsg de subgrupos dos ditos caminhos, a dita restrição adicional exprimindo que no máximo um número nsg de subgrupos tal que 0 ≤ nsg < Nsg podem ser invalidados, um subgrupo sendo invalidado se todos os caminhos que lhe pertencem são afetados pela falha de um mesmo comutador da dita rede.

21. Processo de roteamento de acordo com a reivindicação 18, -19 ou 20, caracterizado pelo fato de que a dita função de custo é o número de comutadores atravessados por um caminho e que ela é minimizada (730i, ..., -730N), para cada uma das ligações do dito feixe, em cada conjunto de caminhos possíveis entre o terminal fonte e cada terminal destinatário da dita ligação, para fornecer pelo menos um caminho candidato por ligação e por terminal destinatário.

22. Processo de roteamento de acordo com a reivindicação 21, caracterizado pelo fato de que são efetuadas (740) combinações de Ki+K2+...+KN caminhos candidatos em que os Ki, 1 < i ≤ N são os números de caminhos respectivos das N ligações do dito feixe, cada combinação correspondendo a uma solução possível de roteamento do dito feixe, e que uma quarta função de custo é minimizada (750) no conjunto das ditas soluções possíveis assim obtidas.

23. Processo de roteamento de acordo com a reivindicação 22, caracterizado pelo fato de que a quarta função de custo avalia, para cada solução possível de roteamento do feixe, o número de comutadores atravessados pelas ligações do feixe que corresponde a essa solução.

24. Processo de roteamento de acordo com uma das reivindicações 2, 6, 12 ou 18, caracterizado pelo fato de que as ditas zonas da rede são alimentadas por fontes de alimentação independentes.

25. Processo de roteamento de acordo com uma das reivindicações precedentes, caracterizado pelo fato de que minimiza-se uma quinta função de custo que avalia a carga de tráfego do comutador mais carregado da rede, no conjunto das soluções de roteamento obtidas por minimização de uma das segunda, terceira ou quarta funções de custo.

26. Programa de computador caracterizado pelo fato de que ele compreende meios de software adaptados para executar as etapas do processo de acordo com uma das reivindicações precedentes, quando ele é executado por um computador.