BRPI0713458A2

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

Info

Publication number: BRPI0713458A2
Application number: BRPI0713458-4A
Authority: BR
Inventors: Remi Andreoletti; Frederic Minot
Original assignee: Airbus France
Priority date: 2006-06-23
Filing date: 2007-05-25
Publication date: 2012-02-22
Also published as: US20100195531A1; FR2902956B1; RU2009102070A; CN101473613B; JP4959792B2; US7983195B2; CA2655948C; WO2007147990A1; CN101473613A; JP2009542068A; RU2432697C2; CA2655948A1; EP2033380B1; EP2033380A1; FR2902956A1

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 respeitando para isso uma restrição de segregação em relação a tripletos de comutadores consecutivos que pertencem aos ditos laços orientados, de maneira a permitir uma verificação do determinismo da rede.

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 através 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 ports conectados aos ports de outros comutadores ou acopladores de terminais. Uma ligação virtual entre um terminal fonte e um terminal destinatário é definida como um caminho orientado 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 ordenada dos 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. Nós nos interessamos na seqüência a uma rede de comutação de quadros da qual as tabelas de comutação são predefinidas e será designada na seqüência "ligação virtual" uma conexão de ponta a ponta de nível 2 em uma tal rede, por exemplo uma ligação virtual em uma rede Ethernet comutada.

É possível obter uma garantia de serviço para uma ligação virtual. No entanto, visto que 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. A rede AFDX (.Avionics Full Duplex Switehed Ethernet), desenvolvida para as necessidades da aeronáutica, é um exemplo de rede Ethernet comutada na qual é possível atribuir uma 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 borne de latência, é garantido para cada ligação virtual.

Será encontrada uma descrição detalhada da rede AFDX 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 já 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 borne 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, a rede Ethernet subjacente sendo duplicada por razões de disponibilidade. Os dados são transmitidos sob a forma de pacotes IP 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 incluído no cabeçalho de quadro. Quando um comutador recebe em um de seus ports 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 sem entretanto demandar 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 (ou unicast), que só servem um único destinatário, ligações virtuais em modo multiponto (ou multicast) que servem vários destinatários.

A Fig. 1 representa esquematicamente uma rede AFDX que compreende terminais T1 a T6 e comutadores de quadros SW1, SW2. É visto que a ligação virtual VL3 que liga o terminal T3 a T2 é de tipo ponto a ponto enquanto que as ligações virtuais VL2 que servem T2 e T3, e VL1 que serve T3 a T5 são de tipo multiponto.

A Fig. 2 representa esquematicamente um comutador em uma rede AFDX. Ele compreende uma pluralidade de buffers de entrada 210 de tipo FIFO, meios de filtragem de quadros 220, meios de multiplexação 230 e buffers de saída 240 de tipo FIFO. Os quadros incidentes são estocados nos diferentes buffers de entrada, cada buffer sendo ligado a um port de entrada e,.

Os meios de filtragem 220 eliminam os quadros que correspondem a uma ligação virtual não reconhecida, os quadros errados e os quadros que levam a uma violação das características de uma ligação. Os meios de multiplexação 230 orientam os quadros na direção dos diferentes buffers de saída 240 em função dos identificadores de ligações virtuais que eles contêm e da tabela de comutação. Os buffers de saída transmitem os quadros para as ligações físicas, cada buffer sendo ligado a um port de saída pr

O roteamento das ligações virtuais em uma rede AFDX consiste em definir as tabelas de comutação dos diferentes comutadores da rede. O roteamento é escolhido de maneira a respeitar as restrições em banda passante das diferentes ligações. Para uma solução de roteamento dada, é verificado que a rede é mesmo determinista, quer dizer que os tempos de encaminhamento nas diferentes ligações são bem inferiores aos bornes de latência garantidos. Para fazer isso, é utilizado geralmente um algoritmo de cálculo denominado "network calculus" do qual será possível encontrar uma descrição nos artigos de René L. Cruz intitulados "A calculus for network delay, part I: network elements in isolation" e "Calculus for network delay, Part II: network analysis", publicados em IEEE Transactions on Information Theory, Vol. 37, N0 1, Janeiro 1991, páginas 114-141. Esse algoritmo avalia de maneira não probabilista, para cada elemento da rede, a vazão máxima instantânea de dados na saída do elemento em questão. O tráfego emitido por um terminal fonte em uma ligação virtual Li é modelado por uma função de taxa máxima de tráfego, dita ainda função de invólucro de fluxo R,(t) que depende do comprimento máximo dos quadros e do intervalo de tempo mínimo que separa dois quadros da ligação, ou seja:

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

Em que ,S1max é o tamanho máximo dos quadros e BAG é uma quantidade chamada intervalo de alocação de banda passante da ligação, dito de outro modo BAG é o intervalo de tempo mínimo que separa dois quadros da dita ligação. A quantidade de dados gerada na ligação durante o intervalo de tempo [t0,t1] é expressa então simplesmente como

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

Para cada elemento da rede, é determinado o invólucro de fluxo na saída desse elemento a partir do invólucro de fluxo na entrada e de uma função de transferência do dito elemento, também chamada curva de serviço. Em função dos invólucros de fluxo na entrada e na saída, é sabido limitar por valores superiores, o tamanho da fila de espera do elemento (o atraso de trabalho do elemento) e o retarde sofrido por um pacote que atravessa esse elemento. Calcula-se assim gradualmente, partindo-se dos terminais fontes e progredindo-se na direção dos terminais destinatários, os invólucros de fluxo em cada ponto da rede. O tempo de latência relativo a uma ligação virtual é estimado a partir dos retardes sofridos nos elementos atravessados por essa ligação e, se for o caso, os tempos de propagação entre esses elementos. Verifica-se em seguida se os tempos de latência estimados estão mesmo de acordo com os valores que se deseja garantir para as diferentes ligações da rede.

Será encontrada uma descrição da aplicação do algoritmo "network calculus" no cálculo dos tempos de latência na tese de J. Grieu intitulada «Analyse et évaluation de techniques de commutation Ethernet pour Pinterconnection des systèmes avioniques» de 24 de setembro de 2004.

O modo de verificação descrito acima funciona bem enquanto a rede não compreender laço físico. Ao contrário, se um tal laço está presente na rede, os tempos de latência das ligações que seguem o caminho do laço não podem ser determinados.

A Fig. 3 ilustra a situação de uma rede AFDX que compreende um laço de três comutadores: SW1, SW2, SW3. Cada comutador possui três ports físicos, cada port sendo constituído por um port de entrada e por um port de saída. O port de saída p1 do comutador SWi é conectado ao port de entrada e3 do comutador SJV3. O port de saída p3 do comutador SW3 é conectado ao port de entrada e2 do comutador SW2- O port de saída p2 do comutador SW2 é conectado ao port de entrada e1 do comutador SWi. O caminho C que passa pelos ports, p1, e3, p3, e2, p2, e1 forma um laço orientado no seio da rede. O invólucro de fluxo no port de saída p1 depende do invólucro de fluxo em ex, quer dizer de p2, e daquele da ligação VLi (na entrada de SW1). De maneira similar, o invólucro de fluxo em p2 depende por sua vez do invólucro de fluxo em p3 e daquele da ligação VL3. Finalmente o invólucro de fluxo em p3 depende por sua vez do invólucro de fluxo em p1 e daquele da ligação VL2. É constatado que se tem uma relação de dependência circular que torna impossível a estimativa dos invólucros de fluxo e portanto dos tempos de latência.

A Fig. 4 ilustra a situação de uma rede AFDX que compreende um laço de quatro comutadores: SW1, SW2, SW3, SW4. Cada comutador possui quatro ports físicos, cada port sendo constituído por um port de entrada e por um port de saída. E notado que quatro ligações virtuais VL1 a VL4 foram roteadas na rede.

O invólucro de fluxo do port de saída 23 de SW1 depende do invólucro de fluxo do port de saída 5 de SW3 e daquele da ligação VL1. O invólucro de fluxo do port de saída 5 de SW3 depende do invólucro de fluxo do port de saída 23 de SW4 e daquele da ligação VL3. O invólucro de fluxo do port de saída 23 de SW4 depende do invólucro de fluxo do port de saída 24 de SW2 e daquele da ligação VL4. Finalmente, o invólucro de fluxo do port de saída 24 de SW2 depende do invólucro de fluxo do port de saída 23 de SWi e daquele de VL2.

Aí ainda, a relação de dependência circular não permite estimar os invólucros de fluxo e portanto os tempos de latência.

A fim de evitar as dependências circulares, é conhecido modificar a topologia da rede, por exemplo acrescentar uma ligação física entre comutadores não ligados do laço e mesmo acrescentar um comutador central ligado a vários ou todos os comutadores do laço. Nos dois casos, a modificação de topologia aumenta localmente o número de caminhos possíveis de roteamento das ligações virtuais, de modo que é possível modificar o roteamento inicial e quebrar a dependência circular. No entanto, não é certo que não sejam criados assim novos laços ou que o roteamento de uma nova ligação não acarretará uma nova dependência circular. Teria-se então voltado para o caso precedente e a incapacidade de verificar o determinismo da rede levaria a tornar complexa de novo a topologia da rede.

O objeto da presente invenção é propor um processo de roteamento de ligações virtuais em uma rede de comutação de quadros que permita uma verificação certa do determinismo da rede, sem modificação de sua topologia.

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 processo compreende as etapas seguintes:

(a) procura dos laços orientados na rede, com exceção de uma permutação circular dos comutadores que eles contêm;

(b) seleção de um tripleto de comutadores consecutivos no seio de cada laço orientado, cada tripleto definindo um caminho de roteamento proibido; (c) determinação de uma solução de roteamento das ligações virtuais que não tomam os ditos caminhos proibidos;

(d) verificação do determinismo da rede com base nas ligações virtuais assim roteadas.

Se o determinismo da rede é verificado, é possível então estocar nos comutadores as tabelas de comutação que correspondem à dita solução de roteamento.

A verificação do determinismo da rede compreende vantajosamente o cálculo dos invólucros de fluxo na saída dos comutadores atravessados pelas ligações virtuais e dos tempos de latência relativos a essas ligações, os tempos de latência assim obtidos sendo em seguida comparados com bornes de latência de referência.

De acordo com um modo de realização vantajoso, seleciona-se na etapa (b) tripletos comuns ao maior número possível de laços orientados.

Também será possível selecionar em prioridade na etapa (b) tripletos que pertencem a caminhos de roteamento proibidos por uma restrição topológica. Essa restrição topológica pode consistir para uma rede dividida em zonas distintas alimentadas por alimentações independentes, em proibir:

- qualquer caminho de roteamento que transpõe uma fronteira entre duas zonas, quando os comutadores respectivamente ligados ao terminal fonte e ao terminal destinatário da ligação virtual pertencem à mesma zona;

- qualquer caminho de roteamento que transpõe mais de uma vez uma fronteira entre duas zonas, quando os comutadores respectivamente ligados ao terminal fonte e ao terminal destinatário da ligação virtual pertencem a zonas diferentes.

Em uma aplicação preferida, a rede de comutação de quadros é uma rede AFDX.

Finalmente, a invenção se refere por outro lado a um programa de computador que compreende meios de software adaptados para executar as etapas do processo 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 a estrutura de um comutador em uma rede AFDX;

a Fig. 3 ilustra a situação de uma rede AFDX que compreende um laço de três comutadores;

a Fig. 4 ilustra a situação de uma rede AFDX que compreende um laço de quatro comutadores;

as Figs. 5A e 5B ilustram o princípio de funcionamento da invenção;

a Fig. 6 representa um organograma do método de roteamento de acordo com a invenção;

a Fig. 7 ilustra um exemplo simplificado de rede AFDX para a aplicação do método de roteamento de acordo com a invenção.

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 de segregação específica com partes de laços orientados da rede.

Será chamado na seqüência de laço orientado qualquer seqüência ordenada 1 de nós ou de comutadores da rede 1 = SW1, SW2,..., SWN com N > 3 tal que SWm e G(SW1) para i = 1,..., N-1 e SW1G G(SWn) em que G é uma aplicação que faz corresponder a cada comutador SW o conjunto de seus sucessores, quer dizer o conjunto dos comutadores diretamente ligados a um port de saída de SW. Em uma rede íull-duplex em que cada port físico compreende um port de entrada e um port de saída, será compreendido que se existe um laço orientado SW1,... SW2,..., SWn na rede então SWN, SWn.1,...,SW1 é também um laço orientado mas de sentido contrário.

Antes de efetuar o roteamento das ligações virtuais, o processo de acordo com a invenção recenseia os laços orientados da rede. Para fazer isso, é possível representar a rede sob uma forma de um gráfico orientado do qual os picos são os comutadores e os terminais e as ligações port de saída a port de entrada são os arcos. A procura dos laços orientados na rede é o mesmo que uma procura de circuitos no gráfico. Com essa finalidade, marca- se cada pico do gráfico com o auxílio de uma etiqueta, Cada pico transmite a seus sucessores sua etiqueta, e depois cada um desses sucessores concatena a etiqueta que ele recebeu com sua etiqueta própria e transmite as etiquetas assim concatenadas a seus próprios sucessores. Prossegue-se a propagação das etiquetas gradualmente. Quando um pico recebe uma lista de etiquetas que compreende a sua, um circuito é identificado e a propagação dessa lista é interrompida. Agrupa-se em seguida os circuitos por classes de equivalência: os circuitos/laços orientados de uma mesma classe são idênticos com exceção de uma permutação circular. Escolhe-se arbitrariamente um laço orientado por classe de equivalência para representá-la.

Os laços orientados estando identificados, faz-se a triagem dos mesmos por número de comutadores atravessados. Será considerado um tal laço orientado, representado na Fig. 5A. Ele corresponde aqui a um laço físico de seis comutadores SWi a SW6. Uma ligação virtual VL que penetra no laço em um comutador SWi e sai no comutador seguinte SWi+1 não é suscetível de induzir uma relação de dependência circular no laço, qualquer que seja o número de ligações virtuais já roteadas no laço e o número de comutadores que essas últimas partilham com ele. De fato, a ligação VL em questão não atravessando dois ports de saída de comutadores consecutivos, ela não induz uma relação entre os invólucros de fluxo na saída desses comutadores.

Compreende-se assim que só se pode induzir dependência circular quando uma ligação virtual partilha pelo menos três comutadores sucessivos, ou seja pelo menos dois ports de saída comuns, com o laço orientado. Se se considera as ligações virtuais partilhando exatamente três comutadores com o laço orientado da Fig. 5A, nota-se que é preciso no máximo seis dessas ligações VLi,..., VL6 para obter um recobrimento do laço e em conseqüência disso uma dependência circular. De maneira geral para um laço orientado de N comutadores, será possível obter uma dependência com no mínimo N ligações que têm exatamente três comutadores comuns com o laço, a fortiori para N ligações que apresentam mais de três comutadores comuns com o laço. Para ligações que partilham exatamente M> 2

comutadores com o laço orientado, será preciso no mínimo E(———) de tais

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

ligações para obter uma relação de dependência circular, em que E(.) exprime o valor inteiro.

Agora se suporá que para um laço orientado dado, suprime-se um caminho de roteamento que corresponde a três picos sucessivos do laço. A situação foi ilustrada na Fig, 5B em que o caminho SW1, SW2, SW3 representado em traço descontínuo, é proibido ao roteamento. Graças a essa restrição, não é mais possível obter um recobrimento do laço com ligações virtuais que acarretam uma dependência circular. De fato, a ligação virtual VL1 não é mais permitida e qualquer ligação virtual que obedece à restrição prescrita contém no máximo o caminho SW1, SW2 ou o caminho SW2, SW3. Nenhuma das ligações virtuais e em especial nem VL6 e VL2, permite induzir uma relação entre os invólucros de fluxo dos comutadores SWi e SW3.

É visto que se proibindo qualquer caminho de roteamento que passa por três comutadores sucessivos dados do laço orientado, elimina-se qualquer risco de dependência circular. Por outro lado, o número de possibilidades de roteamento de ligações virtuais é relativamente pouco afetado por essa proibição (redução de no máximo um terço, para um laço de três comutadores). Procede-se da maneira descrita acima para cada laço orientado.

Vantajosamente, proíbe-se caminhos de roteamento comuns a vários laços de maneira a reduzir o número dos mesmos.

A Fig. 6 ilustra o organograma do método de roteamento de acordo com a invenção. A partir da descrição da topologia da rede 610, recenseia-se em 620 todos os laços orientados da rede, com exceção de uma permutação circular. Em 630, eles são separados por número de comutadores atravessados. Para cada laço orientado assim obtido, identifica-se em seguida em 640, todos os tripletos de comutadores consecutivos do laço. Em 650, procura-se os tripletos comuns a vários laços. Na etapa 660, seleciona-se um tripleto por laço. Vantajosamente, ele será selecionado tomando-se por ordem de preferência, os tripletos que são partilhados pelo maior número possível de laços. Os tripletos selecionados definem caminhos de roteamento proibidos, a proibição de roteamento por um caminho permitindo romper a relação de dependência circular para o laço ou os laços ao qual ele pertence.

Em 670, determina-se uma solução de roteamento das ligações virtuais respeitando-se para isso as restrições estabelecidas em 660.

Na etapa 680 verifica-se, para a solução de roteamento encontrada em 670, se a rede é mesmo determinista estimando-se para isso os invólucros de fluxo na sai dos comutadores atravessados pelas ligações, e depois os tempos de latência para as diferentes ligações. Compara-se em seguida os tempos de latência obtidos nos bornes de latência de referência para as ditas ligações.

Se o determinismo é mesmo verificado, as tabelas de comutação que correspondem à solução de roteamento são estabelecidas e estocadas nos comutadores. Se o determinismo não é verificado, tenta-se uma nova solução de roteamento em 670 ou, na falta disso, uma nova seleção de caminhos de roteamento proibidos em 660, como indicado em traço descontínuo. A Fig. 7 representa um exemplo simplificado de rede AFDX que permite ilustrar o método de roteamento de acordo com a invenção.

A rede compreende cinco terminais T1 a T5 que podem ser cada um deles fonte ou destinatário, e quatro comutadores SWi a SFF4. Os laços orientados da rede são identificados com exceção de uma permutação circular;

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

- para os laços de 4 comutadores:

if = SWi9SW2,SW4lSW3 ; ti™ = SW39SW49SW2iSWi ;

Para cada um dos laços, são listados os tripletos candidatos para os caminhos de roteamento proibidos:

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

Para suprimir qualquer risco de dependência circular, basta escolher um tripleto por laço e proibir o roteamento através dos caminhos correspondentes. Vantajosamente, como já mencionado, são escolhidos tripletos comuns ao maior número de laços possíveis, a fim de reduzir o número de caminhos proibidos. No caso presente, serão selecionados por exemplo:

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

Assim, serão proibidos somente 4 caminhos no lugar dos 6 teoricamente necessários.

Na prática, a restrição de roteamento imposta, a verificação do determinismo da rede não é a única restrição a levar em consideração para o roteamento das ligações virtuais. Por exemplo, em uma aplicação aviônica, é conhecido dividir a rede em zonas distintas, alimentadas por fontes de alimentação independentes. Por razões de segurança, fixa-se então uma restrição topológica, abaixo denominada restrição de divisão, que consiste em proibir:

- qualquer caminho de roteamento que transpõe uma fronteira entre zonas, se os comutadores ligados respectivamente ao terminal fonte e ao terminal destinatário pertencem à mesma zona;

- qualquer caminho de roteamento que transpõe mais de uma vez uma fronteira entre zonas, se os comutadores ligados respectivamente ao terminal fonte e ao terminal destinatário pertencem a zonas distintas adjacentes.

Recenseia-se em um primeiro tempo o conjunto S dos caminhos de roteamento proibidos no sentido da restrição de divisão. Para uma ligação virtual dada a rotear, o respeito dessa restrição eqüivale a uma segregação da ligação em relação dos caminhos S.

De maneira geral, de acordo com um modo de realização da invenção,se disporá de um conjunto S de caminhos proibidos, previamente à aplicação da restrição de roteamento associada à verificação do determinismo da rede. Por ocasião da escolha do tripleto de comutador por laço orientado, será vantajosamente selecionado um tripleto que pertence a um caminho já proibido do conjunto S. Naturalmente, se vários tripletos do laço pertencem a S, será escolhido por prioridade aquele que é comum ao maior número possível de laços orientados. Assim, se aumentará relativamente pouco o número de caminhos a excluir para a verificação do determinismo.

Claims

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 ele compreende as etapas seguintes: (a) procura dos laços orientados na rede, com exceção de uma permutação circular dos comutadores que eles contêm; (b) seleção de um tripleto de comutadores consecutivos no seio de cada laço orientado, cada tripleto definindo um caminho de roteamento proibido; (c) determinação de uma solução de roteamento das ligações virtuais que não tomam os ditos caminhos proibidos; (d) verificação do determinismo da rede com base nas ligações virtuais assim roteadas.

2. Processo de roteamento de acordo com a reivindicação 1, caracterizado pelo fato de que, se o determinismo é verificado, estoca-se nos comutadores as tabelas de comutação que correspondem à dita solução de roteamento.

3. Processo de roteamento de acordo com a reivindicação 1 ou 2, caracterizado pelo fato de que a verificação do determinismo da rede compreende o cálculo dos invólucros de fluxo na saída dos comutadores atravessados pelas ligações virtuais e dos tempos de latência relativos a essas ligações, os tempos de latência assim obtidos sendo em seguida comparados com bornes de latência de referência.

4. Processo de roteamento de acordo com uma das reivindicações precedentes, caracterizado pelo fato de que seleciona-se na etapa (b) tripletos comuns ao maior número possível de laços orientados.

5. Processo de roteamento de acordo com uma das reivindicações precedentes, caracterizado pelo fato de que seleciona-se em prioridade na etapa (b) tripletos que pertencem a caminhos de roteamento proibidos por uma restrição topológica.

6. Processo de roteamento de acordo com a reivindicação 5, caracterizado pelo fato de que a dita restrição topológica consiste para uma rede dividida em zonas distintas alimentadas por alimentações independentes, em proibir: - qualquer caminho de roteamento que transpõe uma fronteira entre duas zonas, quando os comutadores respectivamente ligados ao terminal fonte e ao terminal destinatário da ligação virtual pertencem à mesma zona; - qualquer caminho de roteamento que transpõe mais de uma vez uma fronteira entre duas zonas, quando os comutadores respectivamente ligados ao terminal fonte e ao terminal destinatário da ligação virtual pertencem a zonas diferentes.

7. Processo de roteamento de acordo com uma das reivindicações precedentes, caracterizado pelo fato de que a rede de comutação de quadros é uma rede AFDX.

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