BRPI0721380A2 - mÉtodo de alocar recursos de comunicaÇço entre uma pluralidade de conexÕes e programador - Google Patents

Abstract

MÉTODO DE ALOCAR RECURSOS DE COMUNICAÇçO ENTRE UMA PLURALIDADE DE CONEXÕES E PROGRAMADOR. A presente invenção se refere a um método para alocar recursos de comunicações emtre uma pliralidade de conexões e um programador para o mesmo. Método inclui uma etapa de avalisr necessidades de cada conexão, e somar as necessidades de conexão, e somar as necessidades de cada conexão para obter necessidades totais para todas as conexões . Então o método prossegue ponderando as nessidades de cada conexão com correspondentes dentre as necessidades totais. Depois, o método aloca os recursos de comunicação entre a pluralidade de conexões coonforme as necessidade ponderadas. Por sua vez, o programador inclui um módulo de informação, um módulo de cálculo e um módulo de informação identifica necessidades de cada uma de uma pluralidade de conexões. O módulo de cálculo executa a soma das necessidades e a ponderação das necessidades de cada conexão, enquanto o módulo de concessão aloca recursos de comunicação entre a pluralidade de conexões conforme as necessidades ponderadas.

Description

"MÉTODO DE ALOCAR RECURSOS DE COMUNICAÇÃO ENTRE UMA PLURALIDADE DE CONEXÕES E PROGRAMADOR" CAMPO DA INVENÇÃO

A presente invenção trata da alocação de recursos de comunicações entre uma pluralidade de conexões, e mais particularmente a um método e programador para alocar recursos de comunicações entre uma pluralidade de conexões que levam em consideração alguma qualidade de exigências de serviço (QoS). ANTECEDENTES DA INVENÇÃO

Hoje em dia, redes de telecomunicações são amplamente usadas para transportar grande quantidade de pacotes e operar simultaneamente múltiplas conexões com diferentes exigências Qo S, e às vezes para um assinante. Para atender tais demandas, as normas 802.16 do Institute of Electrical and Electronics Engineers (IEEE) definem concessão de largura de faixa em uma base por assinante, em oposição a uma base por conexão. As concessões de largura de faixa são determinadas e radiodifundidas por estações de base para estações de assinante através de mensagens de UL-MAP.

É porém um problema bem conhecido distribuir eficazmente e razoavelmente a largura de faixa concedida entre múltiplas conexões. Múltiplas publicações da arte anterior propuseram algumas soluções parciais para esta última questão. Uma dessas publicações é uma publicação do IEEE intitulada "Quality of Service support in IEEE 802.16 networks", escrita por Cláudio Cicconetti et al., apresentada na ΓΕΕΕ Netword, Março/Abril 2006. Esta publicação apresenta mecanismos disponíveis nas redes 802.16 do IEEE para suportar QoS. Mais particularmente, a publicação relaciona simulações executadas em dois cenários distintos. As simulações demonstram a eficácia do controle de acesso a meio (MAC) 802.16 proporcionando serviços diferenciados para aplicações com diferentes exigências de QoS, tais como protocolo de voz sobre Internet (VoIP) e Web. A publicação também informa as diferenças no retardo entre canais de enlace descendente e de enlace ascendente, e reporta retardos mais altos e aumento mais acentuado em retardo nos canais de enlace ascendente.

Outra publicação de interesse, intitulada "Efficient Fair

ι

Queuing Using Déficit Round-Robin", escrita por Shreedar et al., apresentada nas IEEE/ACM Transactions on networking, volume 4, no. 3, de junho de 1996, descreve um mecanismo para melhorar a eficiência e viabilidade no enfileiramento de fluxos múltiplos sobre recursos de rede alocados. Para assim fazer, os autores propõem uso de enfileiramento estocástico viável para atribuir fluxos a filas. Então, para a conservar os fluxos, um mecanismo round-robin é usado, e rastreamento de déficits é executado. Embora esta solução melhore a viabilidade entre múltiplas filas, ele não toma sob consideração exigências adicionais impostas por QoS. Na publicação intitulada "Packet Scheduling for QoS support

in IEEE 802.16 broadband wireless access systems" escrita por Wongthavarawat et al., publicada no International Journal of Communication Systems, 2003, volume 16, páginas 81-96, descreve um algoritmo de programação para padrão IEEE 802.16, provendo suporte QoS para diferentes classes de tráfego. Para assim fazer, cada tipo de classe de tráfego é manipulado diferentemente. O algoritmo começa aplicando alocação de largura de faixa global que segue prioridade estrita, e policiando a largura de faixa máxima por classe de tráfego. Então, um segundo nível de granularidade de alocação de largura de faixa é executado em um nível de tipo de conexão. Embora esta publicação proporcione uma solução para a questão de alocação de largura de faixa, esta última não resolve a alocação de largura de faixa simples e viável global. Antes, esta publicação provê uma solução na qual classes de tráfego de prioridade mais alta são tratadas primeiro, e a largura de faixa deixada é usada para as classes de tráfego restantes. Há assim uma necessidade de programador e um método para alocar recursos de comunicação de enlace ascendente simplesmente e razoavelmente, com qualidade de serviço. SUMÁRIO DA INVENÇÃO A presente invenção se refere a um programador e um método

para alocar recursos de rede entre uma pluralidade de conexões de uma maneira simples e viável. Ao contrário de soluções da arte anterior, a presente solução é simples, e assim requer menos capacidades computacionais que outras soluções da arte anterior, enquanto alcançando viabilidade entre múltiplas conexões aa etapa que respeita a qualidade de serviço.

De acordo com um primeiro aspecto, a presente invenção se refere a um método de alocar recursos de comunicação entre uma pluralidade de conexões. O método avalia necessidades de cada conexão, e soma as necessidades de cada conexão para obter necessidades totais para todas as conexões. O método então pondera as necessidades de cada conexão com correspondentes dentre as necessidades totais e aloca os recursos de comunicação entre a pluralidade de conexões conforme as necessidades ponderadas.

Conforme outro aspecto, a presente invenção se refere a um programador. O programador inclui um módulo de informação, um módulo de cálculo e um módulo de atribuição. O módulo de informação identifica necessidades de cada uma dentre uma pluralidade de conexões. O módulo de cálculo soma as necessidades de cada conexão para obter necessidades totais para todas as conexões. O módulo de cálculo ainda pondera as necessidades de cada conexão com correspondentes dentre as necessidades totais. O módulo de atribuição aloca recursos de comunicação entre a pluralidade de conexões conforme as necessidades ponderadas; DESCRIÇÃO BREVE DOS DESENHOS

Os seguintes desenhos serão usados em conjunto com a seguinte descrição detalhada da invenção, para descrever vários aspectos da presente invenção em que:

A figura 1 descreve um fluxograma exemplificativo para uma estação de assinante Unicast Grant conforme o padrão IEEE 802.16;

A figura 2 é um fluxograma de um método conforme uma

modalidade da presente invenção;

As figuras 3a e b são fluxogramas de um método conforme outra modalidade da presente invenção.

A figura 4 é um programador esquemático conforme uma modalidade da presente invenção.

DESCRIÇÃO DETALHADA DA INVENÇÃO

A presente invenção se refere a comunicações de dados, e mais particularmente a comunicações de dados de um tipo similar a IEEE 802.16 no qual a largura de faixa de enlace ascendente é alocada em uma base por assinante, em vez de em uma base por conexão. Para permitir a gestão otimizada da largura de faixa, estações de assinante (incluindo equipamento estacionário e móvel, por exemplo computadores sem fios, assistentes digitais pessoais sem fios, e o similares) são equipadas com um programador. Um programador é um componente da estação de assinante que aloca recursos de comunicação, tais como largura de faixa de enlace ascendente, sobre conexões em operação. No contexto presente, uma conexão se refere a um trajeto entre dois terminais, tais como a estação de assinante em um extremo, e uma estação de base no outro extremo.

Como levantado em muitos documentos da arte anterior, a alocação de recursos de comunicação é uma tarefa delicada, com muitas conseqüências. Uma alocação de recursos inapropriada pode resultar em algumas conexões terem boa qualidade de serviço, e outras conexões terem têm escassamente qualquer serviço. Além disso, muitos algoritmos de alocação conhecidos requerem capacidades de processamento extensas que podem resultar em maior consumo de energia e assim não são apropriados para aplicações limitadas em e processamento e sensíveis a energia, tais como aplicações sem fios.

Um das particularidades adicionais das comunicações de dados como o IEEE 802.16 é o fato que a estação base, em uma base necessitada, executa a alocação de largura de faixa dinamicamente. A necessidade é baseada em uma percepção na estação base das exigências do assinante, da qualidade definida de serviço para cada conexão estabelecida quando disponível, e da largura de faixa de enlace ascendente disponível. Assim a largura de faixa de enlace ascendente alocada a cada assinante não é conhecida com antecedência, e dinamicamente modificada pela estação base. A largura de faixa de enlace ascendente alocada pela estação base é comunicada à estação de assinante por mensagens UL-MAP (acrônimo usado para representar um conjunto de informações que define todo o acesso para um intervalo de programação). As UL-MAP são radiodifundidas a partir da estação base para todas as estações de assinante e definem um intervalo de uso da largura de faixa de enlace ascendente. O intervalo de uso da largura de faixa de enlace ascendente pode ser atribuído a um endereço de unidifusão, de multidifusão ou de radiodifusão. Quando a estação de assinante recebe o tamanho da concessão, ela então deve executar algumas escolhas quanto a como a concessão deve ser alocada através das várias conexões, tarefa que é executada tipicamente pelo programador, (daqui em diante chamado um tamanho de concessão).

Referência é feita agora à figura 1 que descreve um fluxograma exemplificativo para manipulação por uma estação de assinante de uma concessão Unicast conforme Padrão IEEE 802.16. Após a recepção do UL-MAP, este último é processado primeiro (etapa 110). Então, verificação é feita na etapa 120 de se o UL-MAP recebido, se o UL-MAP recebido contém uma concessão atribuída ao Identificador de Conexão Básico do assinante (CID). Se a concessão for para CID básico, a largura de faixa é atribuída na etapa 130 e dados são enviados através das conexões de enlace ascendente. Adicionalmente, a etapa 140 também podem ser usada para enviar mensagens de solicitação de largura de faixa à estação base, para requisitar largura de faixa adicional.

No contexto da presente invenção, uma primeira modalidade do método para alocar os recursos de comunicações (incluindo mais particularmente largura de faixa de enlace ascendente) da presente invenção é mostrada na figura 2. O método geralmente inclui 4 etapas principais: uma etapa de avaliar necessidades (etapa 210), uma etapa de somar as necessidades (etapa 220), uma etapa de ponderar as necessidades (etapa 230) e uma etapa de alocar os recursos (etapa 240). Mais particularmente, o método da presente invenção visa otimizar a alocação do tamanho de concessão, enquanto respeitando qualidade comprometida de serviço de todas as conexões.

Exemplos de parâmetros de qualidade de serviço podem incluir taxa de tráfego reservada mínima (MRTR), latência máxima (ML), e todos os outros parâmetros de qualidade de serviço geralmente conhecidos para conexões. A MRTR se refere a uma quantidade mínima de dados a ser transportada a cargo da conexão, rateada no tempo. A MRTR assim representa a largura de faixa a ser garantida à conexão mesmo no advento de uma rede pesadamente carregada. A medida dos pacotes de dados para a MRTR considera o tamanho de carga útil em uma entrada de uma camada de acesso de meio (MAC), sem sobrecarga MAC e campo CRC (Checagem de Redundância Cíclica) opcional. A ML especifica uma quantidade máxima de tempo que se permite que um pacote de dados espere em uma fila de uma conexão, antes de ser transmitido. A qualidade de serviço ML será preferivelmente atendida somente quando a conexão estiver transmitindo debaixo de seu valor de MRTR. Outros parâmetros de qualidade de serviço também podem ser considerados no contexto da presente invenção, mas para facilidade de compreensão, a descrição seguinte vai se referir somente a MRTR e ML.

Assim, após a recepção da mensagem UL-MAP, o método começa com a avaliação das necessidades na etapa 210. A avaliação das necessidades pode tomar várias formas. Por exemplo, as necessidades podem incluir apenas número de pacotes de dados que precisam ser transmitidos para atender os parâmetros de qualidade de serviço (tais como MRTR e/ou ML), ou uma combinação de parâmetros de qualidade de serviço e uma número pacotes em uma fila para cada um das conexões. Mais particularmente, conforme uma modalidade da presente invenção, a avaliação das necessidades é executada calculando um déficit (etapa 250) e calculando um superávit (etapa 260) para cada uma das conexões. Podem ser usadas várias equações para calcular o déficit de cada conexão. Tais equações podem incluir: (a) um valor máximo da MRTR e o número de pacotes na fila

excedendo o critério de ML pré-definido para a conexão;

(b) comparar o valor de déficit calculado com o número de pacotes na fila para a conexão e selecionar um valor menor como o valor de déficit calculado; e

(c) assegurar que o valor de déficit calculado seja maior que

um cabeçalho de concessão de requisição de largura de faixa.

O método prossegue com a etapa 260 para calcular o valor de superávit para cada das conexões. O valor de superávit pode consistir por exemplo de uma diferença entre o número de pacotes em fila para aquela conexão e o valor de déficit calculado.

A etapa 220 de somar as necessidades inclui, conforme uma modalidade da presente invenção, duas sub-etapas de somar os déficits de todas as conexões (etapa 270), e somar o superávit de todas as conexões (etapa 280), para obter uma visão global das necessidades totais para todas as conexões.

O método prossegue então com a etapa de ponderar as necessidades na etapa 230. Essa etapa pode ser executada dividindo cada uma das necessidades de cada uma das conexões por uma correspondente das necessidades totais. É assim depois possível proceder com a alocação da largura de faixa de enlace ascendente para múltiplas conexões de acordo com as necessidades ponderadas (também chamado abaixo de compartilhamento calculado). Medindo as necessidades de cada conexão, e somando essas necessidades, é assim possível alocar a largura de faixa de enlace ascendente às várias conexões de uma maneira tal que seja viável, isso é justo, simples, e respeite a qualidade de exigências de serviço.

Referência é feita agora simultaneamente às figuras 3a e 3b, que descrevem fluxogramas de um método de acordo com uma outra modalidade da presente invenção. O método começa na etapa 305 com uma etapa de inicializar valores para um déficit total, um superávit total e uma requisição de largura de faixa total (total_bw_req) para 0. Então o método procede para cada conexão (identificada como" i") da maneira seguinte:

(a) determinar vários pacotes de dados em uma fila para essa conexão (etapa 310);

(b) se o número de pacotes de dados na fila para essa conexão

é acima de 0, proceder para a etapa 320, ou então, proceder para a etapa 325;

(c) obter o valor de MRTR para a conexão na etapa 320;

(d) se o valor de MRTR para a conexão é acima de 0, proceder para a etapa 330, ou senão, proceder para a etapa 335;

(e) na etapa 330, determinar vários pacotes de dados que

excedem a ML pré-definida para a conexão;

(f) na etapa 335, ajustar o número de pacotes de dados que excedem a ML pré-definida para a conexão em 0;

(g) em seguida, na etapa 340, o valor de déficit é calculado da maneira seguinte: déficit = max (MRTR, último); déficit = min (número de pacotes de dados na fila, déficit); déficit = max (tamanho de (cabeçalho de bw-req) déficit);

(h) adicionalmente na etapa 340, o valor de superávit é calculado da maneira seguinte: superávit = # de pacotes em fila - valor de déficit;

(i) na etapa 345, o valor de déficit e valor de superávit calculados para a conexão são adicionados ao valor de déficit total, valor de superávit total, e valor de requisição de largura de faixa total;

(j) e na eventualidade que não haja nenhum pacote na fila, o método procede para a etapa 325, onde o valor de MRTR, o último valor, o valor de déficit e valor de superávit para a conexão são todos ajustados a 0.

Em seguida, o método continua na figura 3 b, onde uma primeira verificação é executada na etapa 350 para determinar se o déficit total é maior que a largura de faixa alocada (concessão). Se o déficit total for maior que a concessão, o método procede com a etapa 355, enquanto que se o déficit total for menor que a concessão, o método procede com a etapa 360. O restante do método é executado em uma base por conexão.

Na etapa 355, o valor de déficit para a conexão é comparado com 0. Se o valor de déficit para a conexão é maior que 0, o método procede com a etapa 365, caso contrário ele é terminado. Na etapa 365, a largura de faixa alocada (também chamada compartilhamento) da largura de faixa concedida é determinada da maneira seguinte:

compartilhamento = tamanho de (cabeçalho bw-req) + (concessão - _bw_req total)* (déficit/déficittotal);

compartilhamento = min (déficit, compartilhamento); compartilhamento = max (tamanho de (cabeçalho sizeof(bw_req) compartilhamento).

O método continua então na etapa 370 deduzindo do valor de requisição de largura de faixa total o tamanho do cabeçalho bandreq.

Alternativamente, na eventualidade que o valor do déficit total não é maior que a concessão, o método procede com a etapa 360, onde uma determinação é feita sobre o número de pacotes na fila. Na eventualidade que o número de pacotes na fila para a conexão é maior que 0, o método continua com a etapa 375, caso contrário, ele é terminado.

Na etapa 375, a largura de faixa alocada para a conexão é calculada da maneira seguinte:

compartilhamento = déficit + (concessão - déficit total)*(superávit/ superávit total);

compartilhamento = min (total, compartilhamento); ] compartilhamento = max (tamanho de (cabeçalho bw req), compartilhamento).

O método continua então na etapa 380 com re-cálculo do déficit total e do superávit total. Finalmente, na etapa 385, o valor da concessão é também recalculado para deduzir o compartilhamento alocado à conexão.

Com referência agora à figura 4, é ilustrado um programador esquemático 400 de acordo com uma modalidade da presente invenção. O programador 400 da presente invenção está principalmente composto de um módulo de informação 410, um módulo de cálculo 420 e um módulo de atribuição 430. O módulo de informação 410 identifica as necessidades de cada uma das pluralidades de conexões. As necessidades podem ser determinadas comparando critérios de qualidade de serviço acordados armazenados por conexão e informação de estado coletada para cada uma das conexões. Exemplos de critérios de qualidade de serviço podem incluir MRTR, ML, etc..) A informação de estado inclui o número de pacotes em fila para a conexão. Informações de estado adicionais poderiam ser obtidas por exemplo comunicando 440 com um policiador de tráfego para obter taxa de transmissão de cada uma das conexões de enlace ascendente. O módulo de informação 410 também pode obter informação sobre o retardo sofrido por cada pacote nas filas comparando um tempo atual com um selo de tempo aplicado sobre cada pacote ao entrar em uma camada de MAC.

Os resultados do módulo de informação são então

comunicados ao módulo de cálculo 420. O módulo de cálculo 420 soma as necessidades de cada conexão para obter necessidades totais para todas as conexões. O módulo de cálculo 420 calcula ainda o valor de déficit e valor de superávit para cada conexão. O módulo de cálculo 420 ainda soma os valores de déficit e valores de superávit de todas as conexões para obter o valor de déficit total e o valor de superávit total. O módulo de cálculo 420 pondera ainda as necessidades de cada conexão com necessidades totais correspondentes para obter um valor de uma compartilhamento de largura de faixa para cada conexão. Então, os resultados do módulo de cálculo 420 são comunicados ao módulo de atribuição 430, cuja tarefa é alocar a largura de faixa concedida para cada conexão de acordo com o compartilhamento calculado.

O módulo de informação 410, o módulo de cálculo 420 e o módulo de atribuição 430 poderiam consistir respectivamente em material de hardware, montado em uma placa ou incorporado dentro de conjunto de chip, ou alternativamente, ser implementados na forma de um software.

A presente invenção foi descrita a título de modalidade preferida. Deve ficar claro para aquele qualificado na arte que as modalidades preferidas descritas são apenas para fins exemplificativos, e não devem ser interpretado para limitar o escopo da presente invenção. O método e programador como descritos na descrição de modalidades preferidas podem ser modificados sem sair do escopo da presente invenção. O escopo da presente invenção deve ser definido por referência às reivindicações anexas que claramente delimitam a proteção buscada

Claims (19)

1. Método de alocar recursos de comunicação entre uma pluralidade de conexões, o método caracterizado pelo fato de que compreende as etapas de: avaliar necessidades de cada conexão; somar as necessidades de cada conexão para obter necessidades totais para todas conexões; ponderar as necessidades de cada conexão com correspondentes dentre as necessidades totais; e alocar os recursos de comunicação entre a pluralidade de conexões conforme as necessidades ponderadas.

2. Método de acordo com a reivindicação 1, caracterizado pelo fato de que as necessidades incluem um número de pacotes em fila para a conexão sendo avaliada, e uma taxa de tráfego de reserva mínima (MRTR) para a conexão.

3. Método de acordo com a reivindicação 2, caracterizado pelo fato de que as necessidades incluem um número de pacotes em fila excedendo um critério predefinido de latência máxima (ML).

4. Método de acordo com a reivindicação 3, caracterizado pelo fato de que a etapa de ponderar as necessidades é executada dividindo as necessidades de cada da conexão pelas necessidades totais.

5. Método de acordo com a reivindicação 3, caracterizado pelo fato de que a etapa de avaliar necessidades inclui: calcular um valor de déficit para a conexão, o valor de déficit sendo igual a um valor máximo da MRTR e o número de pacotes em fila excedendo o critério predefinido de ML para a conexão.

6. Método de acordo com a reivindicação 5, caracterizado pelo fato de que a etapa de calcular o valor de déficit ainda inclui comparar o valor de déficit calculado com o número de pacotes em fila para a conexão e selecionar um valor menor como o valor de déficit calculado.

7. Método de acordo com a reivindicação 6, caracterizado pelo fato de que a etapa de calcular o valor de déficit ainda assegura que o valor de déficit calculado é maior que um cabeçalho de concessão de requisição de largura de faixa.

8. Método de acordo com a reivindicação 7, caracterizado pelo fato de que inclui ainda uma etapa de calcular um valor de superávit para cada uma das conexões, o valor de superávit sendo igual a uma diferença entre o número de pacotes em fila para aquela conexão e o valor de déficit calculado.

9. Método de acordo com a reivindicação 8, caracterizado pelo fato de que a etapa de somar as necessidades de cada conexão para obter necessidades totais para todas as conexões inclui somar o déficit calculado e superávit de todas as conexões para obter déficit total e superávit total.

10. Programador caracterizado pelo fato de que compreende: um módulo de informação para identificar necessidades de cada uma de uma pluralidade de conexões; um módulo de cálculo para somar as necessidades de cada conexão para obter necessidades totais para todas as conexões e para ponderar as necessidades de cada conexão com correspondentes dentre as necessidades totais; e um módulo de concessão para alocar recursos de comunicação dentre a pluralidade de conexões de acordo com as necessidades ponderadas.

11. Programador de acordo com a reivindicação 10, caracterizado pelo fato de que a identificação das necessidades é baseada na qualidade armazenada acordada de critérios de serviço por conexão e informação de estado coletada para cada uma das conexões.

12. Programador de acordo com a reivindicação 11, caracterizado pelo fato de que as necessidades incluem um número de pacotes em fila para a conexão que é avaliada, e uma taxa de tráfego mínima reservada (MRTR) para a conexão.

13. Programador de acordo com a reivindicação 12, caracterizado pelo fato de que as necessidades incluem ainda um número de pacotes em fila excedendo um critério predefinido de latência máxima (ML).

14. Programador de acordo com a reivindicação 13, caracterizado pelo fato de que a ponderação das necessidades é executada dividindo as necessidades de cada uma das conexões pelas necessidades totais.

15. Programador de acordo com a reivindicação 14, caracterizado pelo fato de que o módulo de cálculo calcula ainda um valor de déficit para cada uma das conexões, o valor de déficit sendo igual a um valor máximo da MRTR e o número de pacotes em fila excedendo o critério predefinido de ML para a conexão.

16. Programador de acordo com a reivindicação 15, caracterizado pelo fato de que o cálculo do valor de déficit inclui ainda comparar o valor de déficit calculado com o número de pacotes em fila para a conexão e selecionar um valor menor como o valor de déficit calculado.

17. Programador de acordo com a reivindicação 16, caracterizado pelo fato de que o cálculo do valor de déficit inclui ainda assegurar que o valor de déficit calculado é maior que um cabeçalho de concessão de requisição de largura de faixa.

18. Programador de acordo com a reivindicação 17, caracterizado pelo fato de que o módulo de cálculo calcula ainda um valor de superávit para cada uma das conexões, o valor de superávit sendo igual a uma diferença entre o número de pacotes em fila para aquela conexão e o valor de déficit calculado para aquela conexão.

19. Programador de acordo com a reivindicação 18, caracterizado pelo fato de que o módulo de cálculo soma ainda o déficit e superávit calculados de todas as conexões para obter um déficit total e um superávit total.