RT-WIFI: Uma Arquitetura para Comunicação de Tempo-Real em Redes IEEE 802.11 Infraestruturadas

FACULDADE DE ENGENHARIA DA UNIVERSIDADE DO PORTO RT-WiFi: Uma Arquitetura para Comunicação de Tempo-Real em Redes IEEE 802.11 Infraestruturadas Robson Costa Programa Doutoral em Engenharia Informática Orientador: Paulo Portugal (Prof. Dr.) Co-orientador: Ricardo Moraes (Prof. Dr.) 2013 RT-WiFi: Uma Arquitetura para Comunicação de Tempo-Real em Redes IEEE 802.11 Infraestruturadas Robson Costa Programa Doutoral em Engenharia Informática Aprovado em provas públicas pelo Júri: Presidente: Eugénio da Costa Oliveira (Prof. Dr.) Vogal: Paulo Bacelar Reis Pedreiras (Prof. Dr.) Vogal: Ana Cristina Costa Aguiar (Profa. Dra.) Vogal: Joaquim José de Castro Ferreira (Prof. Dr.) Vogal: Pedro Alexandre Guimarães Lobo Ferreira Souto (Prof. Dr.) Vogal: Ricardo Alexandre Reinaldo de Moraes (Prof. Dr.) Vogal: Paulo José Lopes Machado Portugal (Prof. Dr.) Prof. Dr. Paulo José Lopes Machado Portugal (Orientador) "Para Ana Paula e Yasmin, por estarem sempre ao meu lado. Sem vocês este trabalho não teria sido terminado." ii Agradecimentos Inicialmente eu gostaria de agradecer a Deus, por sempre iluminar meu caminho e colocar pessoas maravilhosas nele. Por diferentes razões eu gostaria de agradecer algumas pessoas que foram fundamentais para a conclusão deste trabalho: ao professor da Universidade do Porto, Paulo Portugal, pelo exercício exemplar da sua função de orientador, pela disponibilidade em ouvir todas as questões e dúvidas que surgiram no decorrer deste trabalho e também pela confiança em mim depositada ao longo destes anos. Muito mais que a orientação de um trabalho de doutoramento tu me deste valiosos conselhos para a vida, não os esquecerei. Tenho a certeza que a realização deste projeto não teria sido possível sem o seu auxílio. ao professor na Universidade Federal de Santa Catarina, Ricardo Moraes, por todo o estímulo que recebi, pelas inúmeras ideias proporcionadas, paciência em discuti-las, questionamentos e principalmente pela sua amizade e confiança em mim depositada. ao professor da Universidade do Porto, Francisco Vasques, pela confiança em mim depositada, pelas discussões científicas que tivemos a oportunidade de realizar e também por todo o auxílio que me deste desde que cheguei ao Porto. à minha esposa Ana Paula, por toda a compreensão e apoio. Mesmo nos momentos mais difíceis tu sempre esteve ao meu lado dando-me forças e ânimo para continuar. Tenha a certeza de que este trabalho não teria sido finalizado sem a sua ajuda. à minha filha Yasmin, por compreender tantas horas de ausência do pai. Pelas vezes que cheguei desmotivado em casa e que o teu abraço fez meu mundo mudar instantaneamente. Sem ti eu não teria chego até o fim. ao meus pais (Gentil e Iara) e irmãos (Átila e Ádson) que sempre estiveram ao meu lado em todas as minhas caminhadas; e nesta, uma vez mais. Foi muito difícil ficar este período de tempo fisicamente longe de vocês. Agradeço por tudo o que representam na minha vida. à Tata e Aldori, pelo apoio e confiança depositada em mim. Cuidarei muito bem da neta do senhor Aristides e da dona Edith. ao Silvio Sampaio, Carlos Viegas, Marcos Madruga, Luís Oliveira e Zahid Iqbal, pela partilha de diferentes momentos e pela oportunidade de convívio e aprendizado com cada um de vocês. iv ao Eng. Vasques de Carvalho, pela amizade, atenção e disponibilidade. O senhor me deu a oportunidade de vivenciar com tranquilidade a minha estadia e de minha família no Porto. aos portugueses, que acolheram à mim e a minha família. Um povo forte e batalhador, o qual passei a respeitar e admirar ainda mais. Por fim, agradeço à Fundação para a Ciência e a Tecnologia (FCT), ao Departamento de Engenharia Mecânica e Gestão Industrial (DEMEGI) e à Unidade de Integração de Sistemas e Processos Automatizados (UISPA) do Instituto de Engenharia Mecânica (IDMEC – pólo FEUP) pelo apoio financeiro e logístico neste estudo. Resumo Com os recentes avanços no desenvolvimento de tecnologias de comunicação sem fios, estas tornaram-se uma alternativa credível para o suporte de aplicações distribuídas em ambientes industriais. O aumento da mobilidade e a redução dos custos de instalação e de manutenção são fatores preponderantes que tornam atrativa a sua adoção. Além disso, a possibilidade de construir sistemas de produção de rápida e fácil reconfiguração (on-the-fly) torna a sua utilização ainda mais interessante no domínio industrial. Neste contexto, e com base na crescente disponibilidade de soluções de redes sem fios para ambientes industriais, é provável que num futuro próximo uma parte importante destas tecnologias seja baseada na família de protocolos IEEE 802.11. Os requisitos de comunicação em ambientes industriais são muito específicos. O tráfego transmitido neste tipo de ambiente está tipicamente associado a aplicações de controlo, para as quais os dados de controlo devem ser periodicamente transferidos entre sensores, controladores e atuadores de acordo com metas temporais bem definidas. Um dos grandes desafios encontrados para suportar este tipo de tráfego em redes sem fios está associado ao meio físico utilizado para a transmissão das mensagens. Este meio é considerado essencialmente um ambiente de comunicação aberto, uma vez que a qualquer momento outras estações que estejam fora da esfera de controlo da arquitetura de tempo-real podem tentar acedêlo para realizar as suas transmissões. Caso estas estações estejam a operar na mesma área de cobertura geográfica e no mesmo canal de comunicação, a transmissão destas mensagens pode resultar em atrasos não controláveis na transmissão do tráfego de tempo-real. Logo, uma das questões fundamentais que devem ser abordadas é: "Como garantir que os requisitos temporais do tráfego de tempo-real sejam respeitados, quando este é transmitido num ambiente de comunicação aberto?". O principal objetivo desta tese é responder a esta questão, propondo novas soluções para a transmissão de tráfego de tempo-real em redes IEEE 802.11 a operar em ambientes de comunicação abertos. Nesta tese é proposta uma nova arquitetura de comunicação de tempo-real denominada RTWiFi, baseada na operação conjunta de novos mecanismos de controlo de acesso ao meio e controlo de admissão. Estes mecanismos são capazes de priorizar o tráfego de tempo-real sobre os restantes tipos de tráfego, sem ter a necessidade de controlar estes últimos diretamente. A avaliação do desempenho do RT-WiFi em cenários industriais mostrou que este é capaz de suportar a transmissão de tráfego soft real-time, mesmo ao operar em cenários muito exigentes. Além disso, a arquitetura proposta oferece também um atraso médio quase constante, característica esta considerada importante na transmissão de tráfego de tempo-real. Quando os seus resultados foram comparados aos obtidos por soluções tradicionais como o HCCA, o RT-WiFi mostrou que o seu comportamento é significativamente melhor no que diz respeito ao número máximo de fluxos de dados admitidos. xii ÍNDICE 4 A Arquitetura RT-WiFi 63 4.1 Introdução...................................... 63 4.2 Mecanismo de Controlo de Acesso ao Meio . . . . . . . . . . . . . . . . . . . . 66 4.3 Mecanismo de Controlo de Admissão . . . . . . . . . . . . . . . . . . . . . . . 73 4.3.1 Teste de Escalonabilidade . . . . . . . . . . . . . . . . . . . . . . . . . 77 4.3.2 Gestão do Tamanho dos Slots ....................... 83 4.3.3 Verificação de Falhas das TS . . . . . . . . . . . . . . . . . . . . . . . . 87 4.4 Suporte de Tráfego Broadcast ........................... 88 4.5 Conclusões ..................................... 90 5 Resultados 93 5.1 Descriçãodoscenários ............................... 93 5.1.1 Tráfego de Tempo-Real . . . . . . . . . . . . . . . . . . . . . . . . . . . 96 5.1.2 Tráfego Não Tempo-Real . . . . . . . . . . . . . . . . . . . . . . . . . . 98 5.2 Resultados...................................... 101 5.2.1 AtrasoMédio................................ 102 5.2.2 Percentagem Média de Deadlines Perdidas . . . . . . . . . . . . . . . . 105 5.2.3 Fairness................................... 108 5.2.4 Tamanho Médio do Slot .......................... 110 5.2.5 Percentagem Média de Deadlines Perdidas em função da Carga da Rede . 112 5.3 Conclusões ..................................... 114 6 Conclusões e Trabalhos Futuros 117 6.1 Conclusões ..................................... 117 6.2 TrabalhosFuturos.................................. 120 Referências 123 A Lista de Publicações 133 B Modelo HCCA implementado no simulador OPNET 135 B.1 Introdução...................................... 135 B.2 ImplementaçãodoHCCA.............................. 138 B.2.1 Limitações do modelo implementado . . . . . . . . . . . . . . . . . . . 138 B.2.2 O arquivo wlan_dispatch.pr.m .................... 139 B.2.3 O arquivo wlan_mac_hcf.pr.m ..................... 140 Lista de Figuras 2.1 Arquiteturas da rede IEEE 802.11. . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.2 Arquitetura MAC da norma IEEE 802.11 original (adaptada de [1]). . . . . . . . 7 2.3 Arquitetura MAC da emenda IEEE 802.11e (adaptada de [2]). . . . . . . . . . . 8 2.4 Diferentes IFS das funções DCF e PCF (adaptada de [1]). . . . . . . . . . . . . . 8 2.5 Relações entre os IFS e o aSlotTime (adaptada de [2]). . . . . . . . . . . . . . . 9 2.6 Transmissão DCF (adaptada de [2]). . . . . . . . . . . . . . . . . . . . . . . . . 10 2.7 Transmissão PCF (adaptada de [2]). . . . . . . . . . . . . . . . . . . . . . . . . 12 2.8 CFP encurtado (adaptada de [2]). . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.9 Relação entre IFS e AIFS no mecanismo EDCA (adaptada de [2]). . . . . . . . . 14 2.10 Transmissão HCCA (adaptada de [2]). . . . . . . . . . . . . . . . . . . . . . . . 16 2.11 Fluxo das mensagens TSPEC (adaptada de [3]). . . . . . . . . . . . . . . . . . . 17 2.12 Formato do TSPEC (adaptada de [4]). . . . . . . . . . . . . . . . . . . . . . . . 18 2.13 Cálculo do SI no mecanismo HCCA (adaptada de [4]). . . . . . . . . . . . . . . 22 3.1 Comparação entre as propostas de controlo de acesso ao meio apresentadas. . . . 36 3.2 Comparação entre as propostas de controlo de admissão apresentadas. . . . . . . 60 4.1 Fluxo das mensagens na arquitetura RT-WiFi. . . . . . . . . . . . . . . . . . . . 64 4.2 ArquiteturaRT-WiFi................................. 65 4.3 Modelos de interação entre os dispositivos de tempo-real. . . . . . . . . . . . . . 66 4.4 Ciclo TDMA na arquitetura RT-WiFi. . . . . . . . . . . . . . . . . . . . . . . . 69 4.5 Sobreposição parcial dos slots............................ 70 4.6 Exemplo de uma lista de escalonamento enviada na mensagem de beacon. . . . . 71 4.7 Tempo de atraso uplink (buplink i). .......................... 84 4.8 Tempo de atraso downlink (bdownlink i). ....................... 84 4.9 Tempo de atraso downlink (bdownlink i) para transmissão em broadcast........ 89 5.1 Ambiente de comunicação aberto. . . . . . . . . . . . . . . . . . . . . . . . . . 94 5.2 Atraso médio para o cenário P=30ms. ...................... 103 5.3 Atraso médio para o cenário P=60ms. ...................... 103 5.4 Atraso médio para o cenário P=90ms. ...................... 104 5.5 Média de deadlines perdidas para o cenário P=30ms. .............. 105 5.6 Média de deadlines perdidas para o cenário P=60ms. .............. 106 5.7 Média de deadlines perdidas para o cenário P=90ms. .............. 107 5.8 Fairness para o cenário P=30ms. ......................... 108 5.9 Fairness para o cenário P=60ms. ......................... 109 5.10 Fairness para o cenário P=90ms. ......................... 109 5.11 Tamanho médio do slot para o cenário P=30ms. ................. 110 5.12 Tamanho médio do slot para o cenário P=60ms. ................. 111 xiv LISTA DE FIGURAS 5.13 Tamanho médio do slot para o cenário P=90ms. ................. 112 5.14 Percentagem média de deadlines perdidas para o cenário P=30ms. ....... 113 5.15 Percentagem média de deadlines perdidas para o cenário P=60ms. ....... 113 5.16 Percentagem média de deadlines perdidas para o cenário P=90ms. ....... 114 B.1 Objetos disponíveis para modelagem de WLAN. . . . . . . . . . . . . . . . . . 136 B.2 Parâmetros de comunicação sem fio configuráveis numa estação. . . . . . . . . . 136 B.3 Pilha TCP/IP implementada no objeto wlan_wkstn................ 137 B.4 Processo wlan_dispatch. ............................ 137 B.5 Processo wlan_mac_hcf.............................. 138 Lista de Tabelas 2.1 Valores de aCWmin eaCWmax para cada camada física. . . . . . . . . . . . . . . . 11 2.2 Comparação entre IEEE 802.1D e IEEE 802.11e. . . . . . . . . . . . . . . . . . 13 2.3 Parâmetros das Categorias de Acesso. . . . . . . . . . . . . . . . . . . . . . . . 15 5.1 Ocupação do meio de transmissão (por mensagem). . . . . . . . . . . . . . . . . 96 5.2 ParâmetrosdoRT-WiFi. .............................. 97 5.3 ParâmetrosdoHCCA. ............................... 97 5.4 Parâmetros utilizados para o tráfego HTTP. . . . . . . . . . . . . . . . . . . . . 99 5.5 Parâmetros utilizados para o tráfego SMTP/POP3. . . . . . . . . . . . . . . . . . 99 5.6 Parâmetros utilizados para o tráfego FTP. . . . . . . . . . . . . . . . . . . . . . 100 5.7 Parâmetros utilizados para o tráfego de vídeo. . . . . . . . . . . . . . . . . . . . 100 5.8 Parâmetros utilizados para o tráfego de voz. . . . . . . . . . . . . . . . . . . . . 101 xvi LISTA DE TABELAS Lista de Algoritmos 1 Envio da mensagem de beacon pelo APTR ..................... 72 2 Receção da mensagem de beacon pela estação de tempo-real . . . . . . . . . . . 72 3 Função SEARCHTSID() .............................. 73 4 Interrupção SPi................................... 73 5 Envio da requisição ADDTS ao APTR........................ 75 6 Processamento da requisição ADDTS pela ACU. . . . . . . . . . . . . . . . . . 77 7 Função DELTS() .................................. 77 8 Função SchedTest() ................................. 79 9 Função COMPUTEVALUES() ........................... 81 10 Função COMPUTECOMPRESSIONFACTOR() .................. 81 11 Função GETSCHEDLIST() ............................ 82 12 Interrupção de avaliação dos atrasos de uplink/downlink .............. 85 13 Função ComputeDelay() .............................. 86 14 Função RedefineSlotLength() ........................... 87 15 Função CheckIdleFlows() ............................. 88 xviii LISTA DE ALGORITMOS Lista de Acrónimos AC Access Category ACK Acknowledgement ACM Admission Control Mandatory ACU Admission Control Unit ADDTS Add Traffic Stream AIFS Arbitration Interframe Space AIFSN Arbitration Interframe Space Number AP Access Point BB Black-Burst BE Best-Effort BER Bit Error Ratio BI Beacon Interval BK Background BP Backoff Period BSS Basic Service Set BSSID Basic Service Set Identification BTPS Busy Tone Priority Scheduling CAP Controlled Access Phase CBR Constant Bit Rate CBS Constant Bandwidth Server CCA Clear Channel Assessment CFP Contention Free Period CL Controlled Load COTS Commercial Off-The-Shelf xx LISTA DE ACRÓNIMOS CP Contention Period CS Carrier Sense CSMA/CA Carrier Sense Multiple Access with Collision Avoidance CT Communication Type CTS Clear-to-Send CW Contention Window DCF Distributed Coordination Function DELTS Delete Traffic Stream DFS Distributed Fair Scheduling DIFS Distributed Interframe Space EB Energy-Burst EDCA Enhanced Distributed Channel Access EDF Earliest Deadline First EE Excellent Effort EIFS Extended Interframe Space EMI Electromagnetic Interference EP End Point EPL Ethernet Powerlink FCR Force Collision Resolution FHCF Fair HCF FTDMA Flexible TDMA FTT Flexible Time-Triggered GHz GigaHertz HC Hybrid Coordinator HCCA HCF Controlled Channel Access HCF Hybrid Coordination Function HEMM HCCA/EDCA Mixed Mode IBSS Independent BSS IEEE Institute of Electrical and Electronics Engineers IFS Interframe Space LISTA DE ACRÓNIMOS xxi MAC Medium Access Control Mbps Mega bits por segundo MHz Mega Hertz MMPDU MAC Management Protocol Data Unit MOS Mean Opinion Score MPDU MAC Protocol Data Unit MSDU MAC Service Data Unit NAV Network Allocator Vector NC Network Control NT Number of Transmissions NTR Não Tempo-Real OFDM Orthogonal Frequency Division Multiplexing PAAC Priority Access-based Admission Control PC Point Coordinator PCF Point Coordination Function PER Packet Error Ratio PHCCA Priority HCCA PHY Physical PIFS PCF Interframe Space PLCP Physical Layer Convergence Procedure PRCW Physical Rate and Contention Window PSQA Pseudo-Subject Quality Assessment QAP QoS Access Point QoS Quality of Service / Qualidade de Serviço QP-CAT Queue size Prediction using Computation of Additional Transmission QSTA QoS Station RIFS Real-Time IFS RM Rate Monotonic RTH Real-Time HCCA RTR Ready-To-Receive 4 Capítulo 1 - Introdução 3. A especificação de um mecanismo de controlo de admissão híbrido, capaz de tomar decisões acerca da admissão (ou não) de novos fluxos de dados com base num conjunto de informações fornecidas tanto pelas estações de tempo-real, quanto por medições realizadas no meio de comunicação. Adicionalmente, este mecanismo suporta a implementação de diversos tipos de algoritmos de escalonamento de tempo-real e também é responsável pelo redimensionamento do tamanho dos slots alocados às estações de tempo-real; 4. A implementação de um modelo de simulação da função HCCA (HCF Controlled Channel Access), desenvolvido com a ferramenta de simulação OPNET Wireless Modeler. Esta contribuição torna-se igualmente importante uma vez que não existia um modelo implementado para a ferramenta de simulação utilizada. Os artigos publicados no desenvolvimento desta tese, até o momento da finalização deste documento, são listados no Anexo A. 1.4 Estrutura da Tese A tese está organizada em 6 capítulos, dos quais este é o primeiro. No capítulo 2 é apresentada uma descrição resumida das principais características da norma IEEE 802.11, com o objetivo de compreender as suas principais funcionalidades e limitações. O capítulo 3 apresenta a revisão do estado-da-arte, que está subdividido entre propostas focadas no mecanismo de controlo de acesso ao meio e propostas focadas no mecanismo de controlo de admissão. No capítulo 4, é apresentada e discutida a arquitetura RT-WiFi. A avaliação do desempenho desta arquitetura, obtida através de simulação, é apresentada no capítulo 5. Por fim, no capítulo 6, são apresentadas as conclusões finais e as perspectivas de trabalhos futuros. Capítulo 2 IEEE 802.11 Este capítulo tem como objetivo apresentar uma breve introdução à norma IEEE 802.11, nomeadamente aos mecanismos de Controlo de Acesso ao Meio e de Controlo de Admissão, que têm um papel fundamental num sistema de comunicação de tempo-real. 2.1 Introdução Em 1990, o IEEE (Institute of Electrical and Electronics Engineers) estabeleceu um comité para definir uma norma para as redes locais sem fios. A primeira versão desta norma foi aprovada em 1997 sob o nome de IEEE 802.11 [1] e suportava taxas de transmissão de 1 e 2 Mbps. Em 1999, foram aprovadas as normas IEEE 802.11b [14] e IEEE 802.11a [15], que operam nas gamas de frequência de 2.4 e 5 GHz e alcançam taxas de transmissão de 11 e 54 Mbps, respectivamente. Na prática, os dispositivos que implementavam a norma IEEE 802.11b, acabaram por conquistar uma importante quota do mercado devido ao seu baixo custo e por terem sidos disponibilizados para venda antes dos dispositivos que implementam a norma IEEE 802.11a. Em 2003, o IEEE aprovou a norma 802.11g [16] que opera na gama de frequência de 2.4 GHz e consegue atingir taxas de transmissão até 54 Mbps. Para que os dispositivos IEEE 802.11 pudessem suportar diferentes níveis de qualidade de serviço (QoS – Quality-of-Service), foi aprovado em 2005 a emenda IEEE 802.11e [17], a qual inclui, além de outras inovações, o suporte para a transmissão de voz e de vídeo. Mais recentemente, em 2009, foi aprovada a norma IEEE 802.11n [18], a qual tem por objetivo fornecer maiores taxas de transmissão. Os dispositivos que implementam esta norma podem operar em ambas as gamas de frequência (2.4 GHz e 5 GHz) e são capazes de obterem taxas de transmissão até 600 Mbps. Em 2012 foi publicada uma versão revista da norma IEEE 802.11 [4], a qual incorporou as várias emendas aprovadas ao longo dos últimos anos, bem como algumas correções às mesmas. 6 Capítulo 2 - IEEE 802.11 2.2 Descrição geral da arquitetura A arquitetura básica de uma rede IEEE 802.11 é denominada BSS (Basic Service Set), que caracteriza-se por um grupo de estações que pretendem comunicar entre si. Estas comunicações ocorrem dentro de uma área comum, denominada área de serviço básico (Basic Service Area), definida pelas características do meio físico de comunicação. Uma estação que esteja nesta área pode comunicar com qualquer outra estação membro da mesma BSS. As BSS são divididas em dois diferentes tipos: i) independentes; ii) infraestruturadas. Nas BSS independentes (IBSS – Independent BSS), as estações comunicam diretamente entre si, desde que estejam na área de cobertura uma da outra (Figura 2.1(a)). Tipicamente, as IBSS são compostas por um pequeno número de estações configuradas para um objetivo específico e por um curto período de tempo. Um exemplo é a criação de uma rede IBSS para fornecer conectividade numa reunião, permitindo aos participantes a partilha de dados. Quando a reunião termina, a IBSS é dissolvida. Devido à sua curta duração, tamanho reduzido e propósito específico, as IBSS são também conhecidas como redes Ad Hoc. (a) Rede Ad Hoc. Access Point (b) Rede Infraestruturada. Figura 2.1: Arquiteturas da rede IEEE 802.11. As BSS infraestruturadas (Infrastructured BSS), distinguem-se das IBSS pelo uso de um AP (Access Point) para interligar as estações (Figura 2.1(b)). Isto faz com que as estações necessitem estar dentro da área de cobertura do AP, não sendo imposta nenhuma restrição na distância existente entre cada estação. Desta forma, se uma estação pretende comunicar com outra, a comunicação será efetuada em dois passos: a) primeiro, a estação origem envia as suas mensagens para o AP (fluxo de dados denominado uplink); b) segundo, o AP reencaminha estas mensagens para as estações destino (fluxo de dados denominado downlink). Numa rede infraestruturada, as estações devem inicialmente associar-se ao AP para obterem acesso aos serviços de rede. A associação é um processo pela qual a estação entra na rede IEEE 802.11, sendo logicamente equivalente a ligação de um cabo numa rede Ethernet. Quem inicia o processo de associação é a estação, tendo o AP a função de autorizar, ou não, o acesso. Esta decisão baseia-se no conteúdo do pedido de associação. Capítulo 2 - IEEE 802.11 7 2.3 Mecanismo de Controlo de Acesso ao Meio O IEEE 802.11 utiliza o protocolo CSMA/CA (Carrier Sense Multiple Access with Collision Avoidance) como base para o mecanismo de controlo de acesso ao meio. Neste caso, é utilizado um esquema de avaliação do meio para definir se o mesmo se encontra livre ou ocupado. Neste contexto, quando uma estação deseja transmitir uma mensagem, irá inicialmente “escutar” o meio por um período de tempo pré-determinado, a fim de verificar se outras estações estão a transmitir no mesmo canal de comunicação. Se o resultado desta avaliação definir que o canal está livre, a estação irá atrasar a transmissão, por um período de tempo aleatório, denominado de backoff. Se, após este tempo, o meio permanecer livre, a estação inicia imediatamente a sua transmissão. Caso contrário, a estação irá atrasar a sua transmissão, executando novamente o procedimento de backoff. Isto permite reduzir a probabilidade de colisões com outras estações que estejam a executar procedimentos semelhantes. Além disso, um outro backoff, denominado de pos-backoff, também é executado ao final de cada transmissão. A subcamada MAC (Medium Access Control) propõe duas funções de coordenação diferentes: uma obrigatória, denominada DCF (Distributed Coordination Function) e outra opcional, denominada PCF (Point Coordination Function). A função DCF fornece um serviço de acesso ao meio com contenção, ou seja, todas as estações competem entre si pelo acesso ao meio. Já a função PCF fornece um serviço de acesso ao meio livre de contenção, ou seja, durante um período de tempo uma estação pode aceder ao meio sem competir com outras estações. Este acesso é efetuado de forma ordenada e apenas com a autorização de um controlador. A Figura 2.2 apresenta a arquitetura MAC da norma IEEE 802.11 original com as funções DCF e PCF. Distributed Coordination Function (DCF) Point Coordination Function (PCF) Extensão MAC Utilizado para Serviços com Contenção e base para o PCF Necessário para Serviços Livre de Contenção Figura 2.2: Arquitetura MAC da norma IEEE 802.11 original (adaptada de [1]). Com o objetivo de suportar QoS em redes IEEE 802.11, foi publicado em 2005 a emenda IEEE 802.11e, que incorpora uma função de coordenação adicional denominada HCF (Hybrid Coordination Function), (Figura 2.3). A função HCF fornece um serviço de acesso ao meio que aloca diferentes oportunidades de transmissão (TXOP – Transmission Opportunities) para cada estação. Uma TXOP é definida por um instante de tempo inicial e por uma duração máxima (ou seja, um intervalo de tempo durante o qual a estação é capaz de manter o controlo do acesso ao meio), de forma a possibilitar que 8 Capítulo 2 - IEEE 802.11 Distributed Coordination Function (DCF) Point Coordination Function (PCF) Extensão MAC Utilizado para Serviços com Contenção, base para o PCF e o HCF Necessário para Serviços Livre de Contenção para estações não-QoS, caso contário é opcional HCF Contention Access (EDCA) HCF Controlled Access (HCCA) Necessário para Serviços QoS com Priorização Necessário para Serviços QoS Parametrizados Hybrid Coordination Function (HCF) Figura 2.3: Arquitetura MAC da emenda IEEE 802.11e (adaptada de [2]). múltiplas mensagens sejam transmitidas sem a interferência de outras estações da rede. As TXOP podem ser alocadas através de um dos dois mecanismos especificados pela função HCF: o EDCA (Enhanced Distributed Channel Access) e o HCCA (HCF Controlled Channel Access). 2.3.1 DCF - Distributed Coordination Function A função DCF é definida pela norma IEEE 802.11 como a função básica de acesso ao meio. Nesta, as estações executam o procedimento de backoff antes de iniciarem as suas transmissões1. A função DCF utiliza diferentes intervalos de tempo entre mensagens consecutivas, que são denominados IFS (Interframe Spaces) (Figura 2.4). DIFS Meio Ocupado SIFS PIFS DIFS Backoff Slots Atraso no Acesso Slot Time Acesso imediato quando o meio estiver livre por um período >= DIFS Contention Window Próxima Trama Decrementa o contador de Backoff enquanto o meio estiver livre Figura 2.4: Diferentes IFS das funções DCF e PCF (adaptada de [1]). Os diferentes valores de IFS resultam em diferentes prioridades no acesso ao meio para diversos tipos de mensagens. O SIFS (Short Interframe Space), o menor IFS, é utilizado para receber mensagens de confirmação (ACK – Acknowledgment) e na transmissão de múltiplos fragmentos de uma mensagem. O PIFS (PCF Interframe Space) é utilizado em operações sob a função PCF. O DIFS (DCF Interframe Space) é utilizado por estações que utilizam a função DCF na transmissão de mensagens de dados e de gestão. O EIFS (Extended Interframe Space) é utilizado em condições onde ocorram erros de comunicação. 1É definido pela norma IEEE 802.11 um mecanismo de proteção adicional, RTS/CTS, para resolver o problema dos terminais ocultos e para gerir de forma adequada a transmissão de mensagens longas [1]. Capítulo 2 - IEEE 802.11 9 O valor do SIFS (doravante denominado aSIFSTime) é definido pela camada física (PHY – Physical Layer) e pode variar das camadas físicas utilizadas pelos dispositivos (802.11a, 802.11b, 802.11g ou 802.11n). Além disso, o seu valor é também utilizado como base para calcular os restantes IFS. O valor de aSIFSTime é dado pela seguinte equação: aSIFSTime =aRxRFDelay +aRxPLCPDelay +aMACProcessingDelay +aRxT xTurnaroundTime (2.1) onde aRxRFDelay é o atraso na antena de receção, aRxPLCPDelay é o atraso da camada PHY para transmitir a mensagem para a subcamada MAC, aMACProcessingDelay é o atraso de processamento da subcamada MAC e aRxTxTurnaroundTime é o tempo necessário para a mudança do fluxo de processamento da antena de receção para a antena de transmissão. Outro parâmetro definido pela camada física é o aSlotTime. Além de ser utilizado para a definição dos intervalos de backoff 2, este parâmetro também serve como base para a definição dos diferentes IFS (com exceção do aSIFSTime). Seu valor é dado pela seguinte equação: aSlotTime =aCCATime +aRxT xTurnaroundTime +aAirPropagationTime +aMACProcessingDelay (2.2) onde aCCATime é o tempo necessário para se detetar (utilizando o mecanismo CCA – Clear Channel Assessment) que o meio de comunicação está livre, aRxTxTurnaroundTime é o tempo necessário para se mudar o fluxo de processamento da antena de receção para a antena de transmissão, aAirPropagationTime é o atraso de propagação no ar, e aMACProcessingDelay é o atraso de processamento da subcamada MAC. A Figura 2.5 apresenta a relação entre o aSlotTime e os diferentes IFS. Meio Ocupado D1 M1 Rx/Tx D2 CCAdel M2 Rx/Tx SIFS Slot Time PIFS D2 CCAdel M2 Rx/Tx D2 CCAdel M2 Rx/Tx DIFS Primeiro Slot de Backoff Slot Time Slot Time Slot Time PHYRXEND.indicate Limite TxSIFS Limite TxPIFS Limite TxDIFS Limite do primeiro Backoff D1 = Atraso aRxRF + Atraso aRXPLCP (referenciado a partir do último símbolo de uma trama no meio) D2 = D1 + Tempo de Propagação no Ar Rx/Tx = Tempo de mudança Rx/Tx (inicia com um PHYTXSTART.request) M1 = M2 = Atraso de Processamento MAC CCAdel = Tempo CCA – D1 Figura 2.5: Relações entre os IFS e o aSlotTime (adaptada de [2]). 2Os valores definidos pelos intervalos de backoff são múltiplos de aSlotTime. 10 Capítulo 2 - IEEE 802.11 Após descrever o aSIFSTime e o aSlotTime, é possível apresentar os valores de DIFS, PIFS e EIFS, os quais são doravante denominados aPIFSTime,aDIFSTime eaEIFSTime, respectivamente, sendo definidos pelas seguintes equações: aPIFSTime =aSIFSTime +aSlotTime (2.3) aDIFSTime =aSIFSTime +(2×aSlotTime)(2.4) aEIFSTime =CACK +aSIFSTime +aDIFSTime (2.5) onde CACK é o tempo necessário para a transmissão de uma mensagem de confirmação (ACK) utilizando a taxa de transmissão base definida pela camada física. Quando uma estação, que opera sob a função DCF, pretende realizar uma transmissão, necessita previamente de "escutar" o meio utilizando para isso o mecanismo CS (Carrier Sense), implementado pela primitiva CCA. Caso o meio esteja livre3por um período de tempo maior ou igual à aDIFSTime, a estação pode iniciar a sua transmissão imediatamente. Caso contrário, a estação aguarda até que o meio fique livre por um período de tempo igual aDIFSTime e seguidamente atribui a um contador de backoff um valor definido por um inteiro (múltiplo de aSlotTime) que toma valores no intervalo [0, CW], onde CW (Contention Window), é inicialmente definido como aCWmin4. Conforme o meio mantém-se livre, este contador é decrementado. Quanto o seu valor atingir zero, então a estação inicia a sua transmissão (Figura ??). DIFS Outra Destino Origem Atraso no Acesso ao Meio Backoff após Atraso no Acesso ao Meio Dados SIFS Ack DIFS Contention Window Figura 2.6: Transmissão DCF (adaptada de [2]). Caso o meio torne-se ocupado antes do contador atingir zero, então a sua contagem é suspensa, sendo retomada apenas quando o meio torne-se livre por um período de tempo igual à aDIFSTime. Se após uma transmissão, a mensagem de confirmação não for recebida, então a estação irá incrementar o seu número de retransmissões efetuadas e verificar se este valor atingiu o valor máximo definido pela norma IEEE 802.11. Se o número de retransmissões for inferior ao valor máximo permitido, então é obtido um novo valor aleatório de backoff para uma nova tentativa de transmissão. Neste caso, o valor do CW é incrementado por (oldCW ×2+1), com um limite superior dado por aCWmax5. Caso o número máximo de retransmissões tenha sido atingido, então a estação cancela a transmissão da mensagem. 3Tempo contado a partir da receção da última mensagem pela camada física. 4O valor do aCWmin é definido pela camada física. 5O valor de aCWmax é definido pela camada física. Capítulo 2 - IEEE 802.11 11 A Tabela 2.1 apresenta os diferentes valores de aCWmin eaCWmax para cada camada física. No caso do IEEE 802.11g, o valor de aCWmin será 15 caso todas as estações da BSS estejam a operar em 5 GHz, caso contrário será 31. Tabela 2.1: Valores de aCWmin eaCWmax para cada camada física. CW IEEE 802.11a IEEE 802.11b IEEE 802.11g IEEE 802.11n aCWmin 15 31 15/31 15 aCWmin 1023 1023 1023 1023 2.3.2 PCF - Point Coordination Function A função PCF foi proposta na versão original da norma como uma função opcional capaz de fornecer um serviço de acesso ao meio livre de contenção. O PCF implementa um esquema de polling centralizado para suportar a transmissão síncrona de mensagens, onde o PC (Point Coordinator) opera como um coordenador central, definindo as regras de polling. Este coordenador é utilizado para assegurar o acesso ao meio livre de contenção através da sua restrição. Esta restrição faz com que as estações associadas ao PC possam transmitir somente após receberem uma autorização. O coordenador central encontra-se geralmente instalado no AP, o que limita a função PCF a redes infraestruturadas. O serviço livre de contenção fornecido pela função PCF é utilizado apenas durante uma parte do tempo. Assim, quando esta função é utilizada, o tempo é dividido entre o período livre de contenção (CFP – Contention-Free Period) e o período com contenção (CP – Contention Period) os quais são alternados entre si. O acesso ao meio no CFP é controlado pela função PCF, enquanto que no CP é controlado pela função DCF. O início do CFP é definido através do envio de uma mensagem de beacon pelo PC. Esta mensagem (enviada em broadcast) contém um campo que define a duração máxima do CFP (CFPmax). Todas as estações que recebem a mensagem de beacon atualizam seu NAV (Network Allocator Vector) com o valor definido no campo CFPmax. O objetivo é bloquear o acesso ao meio para dispositivos que estão a utilizar a função DCF. O NAV é um mecanismo CCA virtual utilizado pelos dispositivos IEEE 802.11. Este mecanismo usa o valor do campo duration time existente no cabeçalho das mensagens IEEE 802.11 para inferir por quanto tempo o meio vai ser utilizado por uma estação que esteja a transmitir. Assim, como o valor do NAV é decrementado ao longo do tempo, uma estação só pode efetuar uma transmissão após o seu NAV chegar a zero. Como segurança adicional para prevenir interferências, todas as transmissões efetuadas no CFP são separadas por aSIFSTime ou aPIFSTime (Figura 2.4). Como ambos os IFS são menores que o aDIFSTime (utilizado pela função DCF), as estações PCF conseguem manter o controlo do acesso ao meio sem interferências de estações DCF (Figura 2.7). 12 Capítulo 2 - IEEE 802.11 PIFS SIFS D1 + poll Beacon SIFS U1 + ack SIFS D2 + ack + poll SIFS SIFS PIFS SIFS SIFS Período Livre de Contenção Período com Contenção NAV Reinicia o NAV CFPMaxDuration Intervalo de Repetição do Perído Livre de Contenção Sem resposta ao CF-Poll U2 + ack D3 + ack + poll D4 + poll U4 + ack CF-End NAV = “CSMA Virtual” Dx = Tramas enviadas pelo Point Coordinator Ux = Tramas enviadas pelas estações Figura 2.7: Transmissão PCF (adaptada de [2]). Após o PC ter obtido o controlo do meio, este envia mensagens de autorização (denominadas CF-Poll – Contention-Free Polling) para as estações que estão na lista de polling (a lista de estações que solicitaram autorização para operarem durante o CFP) para que estas realizem as suas transmissões. Durante o CFP, as estações podem transmitir apenas se receberem uma mensagem CF-Poll do PC. Cada mensagem de autorização possibilita que a estação transmita apenas uma mensagem de dados, independentemente do seu tamanho. Para transmitir múltiplas mensagens de dados, a estação deve receber múltiplas mensagens CF-Poll do PC. Para assegurar que o PC não perca o controlo do acesso ao meio, caso alguma estação autorizada não inicie sua transmissão no período de tempo alocado a si, após aPIFSTime, é enviada pelo PC uma nova mensagem CP-Poll para a próxima estação da lista de polling. O CP é iniciado logo a seguir ao CFP. Este deve ter uma duração mínima igual ao tempo necessário para a transmissão (com confirmação) de uma mensagem de dados com um MPDU (MAC Protocol Data Unit) de tamanho máximo6. A primeira transmissão dentro do CFP não ocorre necessariamente logo após o seu início. Por vezes, é possível que uma transmissão baseada num serviço com contenção, ultrapasse o final do CP. Quando isto ocorre, dizemos que o CFP foi encurtado (Figura 2.8). Caso exista uma transmissão a decorrer no momento em que a mensagem de Beacon deveria ser enviada, esta transmissão tem permissão para ser finalizada. Como consequência, uma vez que a mensagem de Beacon anuncia o início do próximo CFP, este é encurtado de acordo com o atraso sofrido. Para evitar um “efeito cascata”, este novo CFP deve ser finalizado antes do próximo instante esperado para a transmissão da mensagem de Beacon, referido como TBTT (Target Beacon Transmission Time). O PC pode terminar um CFP, antes da sua duração máxima, transmitindo uma mensagem denominada CF-End (Contention-Free End). Esta decisão pode ser baseada no tamanho da lista de polling, carga da rede, ou qualquer outro fator que o PC julgue importante. 6O tamanho máximo de um MPDU de acordo com a norma IEEE 802.11 é de 4095 bytes. Capítulo 2 - IEEE 802.11 13 PIFS Beacon Período Livre de Contenção Período com Contenção NAV Intervalo de Repetição do Perído Livre de Contenção NAV = “CSMA Virtual” PCF DCF Tamanho Variável Meio Ocupado PIFS Beacon Período Livre de Contenção Período com Contenção PCF DCF Período Livre de Contenção reduzido devido ao atraso gerado pela ocupação do meio de comunicação Atraso (devido ao meio estar ocupado) Figura 2.8: CFP encurtado (adaptada de [2]). Diferentemente da função DCF, a função PCF opera sem o mecanismo de backoff nas estações durante o CFP. Neste contexto, há o risco de ocorrerem repetidas colisões, se múltiplos PC estiverem a operar no mesmo canal de comunicação. Para minimizar este risco, o PC pode opcionalmente utilizar um aDIFSTime mais um valor aleatório de backoff (onde o CW varia num intervalo de [1, aCWmin]) antes de iniciar um novo CFP, caso a mensagem de Beacon seja atrasada devido ao meio estar ocupado. O PC pode também escolher utilizar este valor de backoff durante o CFP antes de efetuar uma retransmissão. 2.3.3 EDCA - Enhanced Distributed Channel Access O mecanismo EDCA foi desenvolvido com o objetivo de melhorar o serviço fornecido pela função DCF. A sua característica principal é a diferenciação na transmissão das mensagens através do uso de quatro categorias de acesso (Access Categories – AC). Cada mensagem que chega à subcamada MAC com uma prioridade pré-definida é alocada numa das quatro AC (voz, vídeo, best-effort ebackground). Todas as AC definidas pelo mecanismo EDCA são baseadas nos oito níveis de prioridade (UP – User Priority) definidos pela norma IEEE 802.1D (Tabela 2.2). As categorias de voz e background são, respectivamente, as categorias com maior e menor prioridade. Tabela 2.2: Comparação entre IEEE 802.1D e IEEE 802.11e. 802.1D 802.11e UP Designação Categoria de Acesso Designação 1 BK - Background 0 BK - Background 2 Reservado 0 BE - Best Effort 1 BE - Best Effort 3 EE - Excellent Effort 4 CL - Carga Controlada 2 VI - Vídeo 5 VI - Vídeo 6 VO - Voz 3 VO - Voz 7 NC - Controlo de Rede 20 Capítulo 2 - IEEE 802.11 e também a política de acesso do EDCA. O QAP deve associar a UP recebida pela requisição ADDTS com a AC apropriada (de acordo com a Tabela 2.2). Quando o QAP recebe a requisição ADDTS, ele pode aceitá-la, ou rejeitá-la, utilizando para isso um algoritmo local. Se decidir aceitar a requisição, deve também calcular o Tempo no Meio das informações contidas no TSPEC. Este valor será enviado juntamente com a resposta ADDTS. Para que seja possível efetuar o cálculo anterior, devem ser levados em consideração dois fatores: os requisitos do tráfego e os requisitos do meio. Ambos são caracterizados por parâmetros TSPEC enviados pela estação. No caso dos requisitos do tráfego, os parâmetros são: Taxa Média de Dados (ρ) e Tamanho Nominal da MSDU (L). No caso dos requisitos do meio, os parâmetros são: Largura de Banda Excedentária (β) e Taxa Mínima PHY (φ). Com estas informações é possível obter o valor do Tempo no Meio utilizando a seguinte equação: Tempo no Meio =β×(ρ/8) L×MPDUExchangeTime (2.7) onde MPDUExchangeTime é o tempo necessário (em µs) para se transmitir a sequência MPDU. Para o caso de uma MPDU transmitida com uma política normal de confirmação e sem a proteção RTS/CTS, este valor é igual ao tempo necessário para se transmitir a MPDU mais o tempo necessário para se receber a mensagem de confirmação (ACK). Este tempo pode ser definido pela seguinte equação: MPDUExchangeTime =Cφ L+aSIFSTime +CACK (2.8) ondeCé a primitiva PLME-TXTIME, a qual retorna a duração (em µs) de uma mensagem baseada no tamanho do seu campo de dados (L) e na taxa mínima PHY (φ) utilizada pela estação. Quando a resposta ADDTS é recebida pela estação indicando a sua aceitação, esta irá organizar o controlo de admissão utilizando duas variáveis: Tempo Admitido, que é o tempo (em µs) autorizado pelo QAP para que a estação tenha acesso ao meio; e Tempo Utilizado, que é o tempo (em µs) decorrido de utilização do meio pela estação. Ambos são inicializados com o valor 0 no momento da (re)associação. No caso do Tempo Admitido, seu valor é calculado utilizando como base o valor do campo Tempo no Meio enviado pelo QAP. Este processo é executado utilizando a seguinte equação: Tempo Admitido =Tempo Admitido +dot11EDCAAveragingPeriod ×Tempo no Meio (2.9) onde o dot11EDCAAveragingPeriod indica o intervalo de tempo (em segundos) em que os parametros Tempo Admitido eTempo Utilizado devem ser recalculados. A valor padrão para este parâmetro é 5 (definido pela emenda IEEE 802.11e). Uma estação pode escolher cancelar um pedido específico a qualquer momento. Para isso, deve transmitir uma mensagem DELTS ao QAP, contendo o TSID e a direção da TS. Se a estação Capítulo 2 - IEEE 802.11 21 enviar ou receber uma mensagem DELTS, deve recalcular o Tempo Admitido de acordo com a seguinte equação: Tempo Admitido =Tempo Admitido −dot11EDCAAveragingPeriod ×Tempo no Meio (2.10) O valor da variável Tempo Utilizado pode ser atualizado em duas diferentes situações: • Em intervalos de cada dot11EDCAAveragingPeriod: Tempo Utilizado =max[(Tempo Utilizado −Tempo Admitido),0](2.11) • Após cada tentativa de transmissão ou retransmissão de uma MPDU, independentemente de esta ser finalizada com sucesso ou não: Tempo Utilizado =Tempo Utilizado +MPDUExchangeTime (2.12) Se o valor do Tempo Utilizado atingir ou exceder o valor do Tempo Admitido, a estação deve imediatamente deixar de transmitir utilizando a AC solicitada. No entanto, esta estação pode continuar suas transmissões utilizando outra AC que não necessite de aprovação prévia pelo controlo de admissão. 2.4.3 Mecanismo de Controlo de Admissão do HCCA O mecanismo HCCA foi desenvolvido para suportar parametrização QoS do tráfego transmitido. Desta forma, uma estação pode enviar ao HC as características e os requisitos QoS de uma TSkque deseja transmitir. Se esta TS for admitida, o HC define um escalonamento de forma a cumprir todos estes requisitos. O escalonamento do HCCA baseia-se num esquema Round-Robin, que obriga as estações a transmissão dos seguintes parâmetros TSPEC: Taxa Média de Dados (ρ), Tamanho Nominal da MSDU (L), e o Intervalo Máximo de Serviço (SImax) ou Atraso Limite (D). Se ambos parâmetros SImax eDforem enviados, o escalonador utiliza SImax para efetuar os cálculos. Quando um novo pedido é recebido pelo HC, a unidade de controlo de admissão (ACU – Admission Control Unit) realiza o processo de verificação das condições solicitadas pela TSkexecutando os passos seguintes: 1. Inicialmente a ACU verifica qual o menor de todos os SImax pertencente às TS já admitidas pelo HC e à TSk; 2. Seguidamente, a ACU seleciona um novo SI, que será comum à todas as TS admitidas pelo sistema. Este valor deve ser inferior ao menor SImax encontrado no passo anterior e, deve ser submúltiplo do intervalo de envio das mensagens de beacon. Na Figura 2.13, é 22 Capítulo 2 - IEEE 802.11 apresentado um exemplo de uma TSiadmitida. Neste caso específico, o intervalo entre o envio das mensagens de beacon é de 100 milissegundos e o SImax para a TSié de 60 milissegundos. Utilizando as regras previamente apresentadas, a ACU escolhe um SI igual a 50 milissegundos. SI = 50 ms SI = 50 ms Intervalo da mensagem de Beacon = 100 ms TXOP i TXOP i TXOP i Figura 2.13: Cálculo do SI no mecanismo HCCA (adaptada de [4]). 3. Em seguida a ACU calcula o número de MSDU que serão enviadas ao HC (Nk). Para isto são utilizados os valores do novo SI e da taxa média de dados (ρ) enviada pela estação. Este valor é dado pela seguinte equação: Nk=SI ×ρk Lk(2.13) 4. Seguidamente, a ACU calcula a duração da TXOP que precisa ser alocada à TSk, dado pela seguinte equação: TXOPk=maxNk×Lk Rk +O,M Rk +O(2.14) onde Rké a taxa mínima PHY, Mé o tamanho máximo de um MSDU7, e Oé o overhead em unidades de tempo. O overhead inclui os tempos IFS, AIFS e ACK. 5. Por fim, a ACU determina se a TSkpode ser admitida pelo sistema de comunicação caso a seguinte inequação seja satisfeita: TXOPk SI + n ∑ i=1 TXOPi SI ≤T−TCP T(2.15) onde né o número de TS previamente admitidas, Té o intervalo entre as mensagens de Beacon eTCP é o tempo alocado para o tráfego EDCA no CP. Uma observação importante neste processo é que, de acordo com a norma IEEE 802.11e, a taxa de transmissão física (Rk), utilizada pelo HCCA para o cálculo do tamanho da TXOP, deverá ser 7O tamanho máximo de um MSDU definido pela norma IEEE 802.11 é de 2304 bytes. Capítulo 2 - IEEE 802.11 23 igual a menor taxa de transmissão disponibilizada pela camada física. Esta abordagem é utilizada para evitar a necessidade de se realizar novos cálculos das TXOP, caso a taxa de transmissão seja alterada pelo mecanismo de auto-rate em detrimento as interferências no canal de comunicação. 2.5 Conclusões A utilização de tecnologias de comunicação sem fios cresceram progressivamente ao longo dos últimos anos. O aumento da necessidade de conectividade e de mobilidade tem impulsionado o desenvolvimento de novas tecnologias e o aperfeiçoamento de outras já existentes. Entre estas, a que ganhou maior destaque foi a definida pela norma IEEE 802.11. O seu baixo custo e facilidade de implementação conquistaram a indústria de computadores que, na sua grande maioria, acabaram por adotá-la como padrão nos seus dispositivos de comunicação. Basicamente, a norma IEEE 802.11 define quatro mecanismos de controlo de acesso ao meio, que são implementados pela subcamada MAC. Estes mecanismos podem ser classificados entre os que disponibilizam um serviço de acesso ao meio baseado em contenção (DCF e EDCA) e os que disponibilizam um serviço de acesso ao meio livre de contenção (PCF e HCCA). No que concerne à implementação de um mecanismo de controlo de admissão e à definição de diferentes níveis de QoS, apenas o EDCA e o HCCA são capazes de fornecer este tipo de serviço. Ao analisarmos os mecanismos disponibilizados pelo IEEE 802.11 sob a ótica da transmissão do tráfego de tempo-real, podemos observar algumas limitações (discutidas com maior detalhe no capítulo 3). Neste contexto, a que se destaca nos mecanismos DCF e PCF é a transmissão de todos os tipos de tráfego através de apenas uma categoria de acesso, ou seja, definindo assim um único nível de prioridade. Embora o mecanismo EDCA apresente uma solução para esta limitação, estudos realizados [20] apontam que, ao operar num ambiente de comunicação aberto, o EDCA não é capaz de cumprir os requisitos temporais do tráfego de tempo-real, mesmo quando este é transmitido através da categoria de acesso de mais alta prioridade (voz) . O mecanismo que reúne um conjunto de características mais favoráveis à transmissão do tráfego de tempo-real é o HCCA. Isto porque, com a utilização do elemento TSPEC para obter informações acerca das TS, é possível ao HC alocar de forma mais eficiente os recursos do meio de comunicação, além também de evitar sobrecargas no sistema. No entanto, estudos preliminares [21, 22] demonstraram que em algumas situações o HCCA não é capaz de garantir os requisitos temporais das mensagens de tempo-real. Portanto, é possível concluir que, embora alguns dos mecanismos definidos pela norma IEEE 802.11 suportem a transmissão de tráfego com requisitos QoS, isto por si só não é o suficiente para a transmissão do tráfego de tempo-real. Isto evidencia a necessidade de propor novas soluções capazes de suportar um serviço de comunicação de tempo-real em redes IEEE 802.11 a operar em ambientes de comunicação abertos. 24 Capítulo 2 - IEEE 802.11 Capítulo 3 Trabalhos Relacionados No capítulo anterior foram apresentados os mecanismos de controlo de acesso ao meio e controlo de admissão implementados pela norma IEEE 802.11, bem como, algumas das suas respectivas limitações no que concerne à transmissão de tráfego de tempo-real. Assim, evidenciou-se a necessidade de investigações nesta área, de forma a tornar possível a criação de novas propostas capazes de suportar a transmissão deste tipo de tráfego em redes IEEE 802.11. Neste contexto, o objetivo deste capítulo é, expandir de forma detalhada a discussão acerca das limitações apresentadas pela norma IEEE 802.11 e, analisar e classificar as propostas apresentadas pela comunidade científica. Como a maioria das propostas, ou focam em aspectos relacionados ao mecanismo de controlo de acesso ao meio, ou em aspectos relacionados ao mecanismo de controlo de admissão, optou-se por dividir este capítulo entre estes dois tipos de mecanismos para uma melhor organização e compreensão das características e limitações encontradas. 3.1 Mecanismos de Controlo de Acesso ao Meio A norma IEEE 802.11 [4] define uma arquitetura para WLAN (Wireless Local Area Networks), que abrange as camadas física e de ligação de dados. No contexto da camada de ligação de dados, nomeadamente a subcamada MAC (Media Access Control), são definidos quatro mecanismos de controlo de acesso ao meio que podem ser implementados de forma centralizada ou distribuída. O acesso ao meio ocorre basicamente através da utilização de diferentes valores de IFS (Interframe Space) e do mecanismo de backoff, o qual é baseado num algoritmo probabilístico. Os mecanismos que fornecem um serviço de acesso ao meio livre de contenção também utilizam este algoritmo para tentar solucionar situações onde duas ou mais redes que fornecem este tipo de serviço se encontram sobrepostas. Neste contexto, e com base nas limitações da norma IEEE 802.11 apresentadas no capítulo anterior, a comunidade científica tem apresentado novas propostas para o mecanismo de controlo de acesso ao meio com o objetivo de suportar a transmissão do tráfego de tempo-real neste tipo de tecnologia. 26 Capítulo 3 - Trabalhos Relacionados Esta secção apresenta algumas destas propostas dividindo-as numa classificação baseada em três níveis. O primeiro nível está relacionado com a arquitetura da proposta, que pode adotar uma abordagem Centralizada ou Distribuída. Na abordagem centralizada é utilizado um dispositivo central para coordenar o acesso ao meio que, entre outras funções, irá definir qual a estação que terá acesso ao meio, em que instante e por quanto tempo. Na abordagem distribuída, esta decisão é tomada localmente pelas próprias estações. Osegundo nível de classificação baseia-se na forma como as colisões são tratadas, uma vez que o mecanismo de backoff implementado por cada estação não é capaz de fornecer garantias temporais às aplicações de tempo-real. Neste nível, classificou-se as colisões de acordo com as seguintes estratégias [23]: •Evitar Colisões: o acesso ao meio é realizado através de um serviço livre de contenção que, tem por objetivo tentar evitar a ocorrência de colisões; •Resolver Colisões: substitui-se o algoritmo tradicional de backoff (baseado num esquema probabilístico) por um algoritmo que garanta um limite temporal; •Reduzir Colisões: utilizam-se algoritmos distribuídos fracamente acoplados com o objetivo de se reduzir o número de colisões. Oterceiro nível de classificação baseia-se na grande disseminação no mercado de dispositivos que utilizam uma tecnologia de comunicação sem fio baseada na norma IEEE 802.11. Desta forma, faz-se necessário avaliar o grau de compatibilidade das estações de tempo-real sob dois aspectos considerados importantes: •IEEE 802.11: a prioridade no acesso ao meio do tráfego de tempo-real é mantida mesmo na presença de estações IEEE 802.11 padrão a operar no mesmo ambiente de comunicação; •COTS: a implementação das estações de tempo-real é compatível com hardware COTS (Commercial-Off-The-Shelf ), não necessitando a utilização de hardware específico. É importante observar que os aspectos apontados no terceiro nível de classificação podem apresentar-se de forma independente em cada proposta, não sendo estes mutuamente exclusivos. 3.1.1 Abordagens Centralizadas Nesta subsecção são apresentadas as propostas que utilizam uma abordagem centralizada do mecanismo de controlo de acesso ao meio, sendo estas também subdivididas de acordo com a forma como são tratadas as colisões (segundo nível de classificação anteriormente definido). Capítulo 3 - Trabalhos Relacionados 27 3.1.1.1 Evitar Colisões O PCF (Point Coordination Function) foi desenvolvido como um mecanismo opcional de controlo de acesso ao meio. Implementa um esquema de polling centralizado para suportar transmissões síncronas de dados, onde o PC (Point Coordinator) desempenha o papel de mestre, fornecendo assim um serviço de acesso ao meio livre de contenção. Esta abordagem faz com que as estações associadas ao PC possam transmitir as suas mensagens apenas após a receção de uma autorização. Como o PC é executado no AP (Access Point), este mecanismo é restrito às redes infraestruturadas. A sua principal limitação reside no facto do PC não ser capaz de prever o tamanho das mensagens transmitidas por cada TS (Traffic Stream), o que pode introduzir assim um tempo de transmissão variável. Além disso, a taxa de transmissão das estações pode mudar devido a diferentes características do ambiente, impedindo assim que este serviço possa garantir tempos de resposta confiáveis. O mecanismo HCCA (HCF Controlled Channel Access), proposto como uma melhoria do PCF, baseia-se também num esquema de polling. Tem como principal objetivo fornecer um serviço de comunicação com tempo de resposta limitado superiormente. De forma semelhante ao PCF, o HCCA implementa um coordenador central denominado HC (Hybrid Coordinator), que distribui autorizações de transmissão a todas as estações associadas a ele, mesmo quando estas não tenham nenhuma mensagem para transmitir. Quando isto ocorre, a estação irá transmitir uma mensagem com o campo de dados vazio (denominada Null Frame). Este processo de alocação de tempo para estações que não tenham mensagens para transmitir é considerado um overhead no mecanismo HCCA [24]. Além disso, estudos preliminares [21, 22] demonstraram que o HCCA pode não ser capaz de garantir os requisitos de tempo-real esperados. Uma limitação comum a ambos os mecanismos PCF e HCCA é a sua utilização em termos práticos, uma vez que a maioria dos dispositivos WLAN comerciais nunca os implementaram em função das suas complexidades [25]. Para tentar solucionar o problema de overhead do HCCA diversos autores propuseram melhorias. Em [24], Son et al. apresentam um esquema de polling onde o HC pune as estações que recebem uma autorização mas que não tenham mensagens para transmitir. Assim, sempre que uma estação transmite uma mensagem vazia, esta permanecerá durante um período de tempo pré-determinado sem receber uma nova autorização. A principal limitação desta proposta é que se um fluxo de dados tiver um intervalo de serviço maior que o intervalo de serviço definido pelo HC (comum à todos os fluxos de dados admitidos), esta estação poderá ser erradamente punida. Este problema pode também ocorrer se o tráfego de tempo-real for aperiódico ou esporádico. De forma diferente, Lo, Lee e Chen [26] definem um mecanismo denominado CP-Multipoll (Contention Period Multipoll) capaz de distribuir múltiplas autorizações. Para isto, foi incorporado o esquema de acesso do DCF (Distributed Coordination Function) ao mecanismo de polling, de forma a utilizar diferentes valores de backoff para múltiplos fluxos de dados gerados por estações associadas ao HC. Desta forma, cada estação necessita executar um procedimento de backoff após receber a mensagem CP-Multipoll. Além disso, com o objetivo de evitar repetidas colisões entre 28 Capítulo 3 - Trabalhos Relacionados estações de diferentes BSS (Basic Service Set) a operar no mesmo canal de comunicação, os valores atribuídos às mensagens CP-Multipoll da BSS vizinhas devem ser diferentes entre si. Lee et al. [27] propuseram um mecanismo de polling baseado numa arquitetura MestreEscravo. Neste caso, o tempo no meio de comunicação é dividido em ciclos de transmissão definidos pelo VPP (Virtual Polling Period). Cada VPP é subdividido em múltiplos slots que podem ser alocados às estações escravo. Para definir a sequência de alocação, a estação mestre envia uma mensagem em broadcast contendo esta informação. Quando uma estação escravo recebe uma autorização, esta pode transmitir uma mensagem de resposta (com dados) para a estação mestre ou então diretamente para outra estação escravo. Em [25, 28], Miorandi et al. apresentam também uma solução baseada numa arquitetura Mestre-Escravo para suportar comunicação de tempo-real em redes IEEE 802.11. Nesta abordagem, são entregues mensagens cíclicas às estações escravo através de requisições periódicas enviadas pela estação mestre. São apresentadas três diferentes técnicas para controlar o tráfego acíclico: a primeira consulta (no final do ciclo corrente) os escravos que sinalizam a presença de mensagens acíclicas a serem transmitidas. A segunda, permite que um escravo, após receber uma autorização, possa enviar diretamente mensagens acíclicas ao mestre. A terceira explora a natureza descentralizada do protocolo MAC da norma IEEE 802.11 onde, assim que uma mensagem acíclica é gerada, a estação escravo pode tentar efetuar a sua transmissão. Em [29], Willig propôs um protocolo MAC denominado FTDMA (Flexible Time Division Multiple Access) que é baseado em um esquema de polling, onde em cada ciclo uma estação base envia autorizações a todas as estações registadas. Os ciclos são logicamente subdivididos em fases: SYNC (utilizado pela estação base para enviar as demais estações mensagens de sincronização do relógio), Polling (utilizado pela estação base para enviar as autorizações de transmissão), Reservation (utilizado pelas estações para indicarem à estação base qual o tempo necessário para sua transmissão), Register (utilizado pelas estações para se associarem a estação base), Current Scheduler (utilizado pela estação base para enviar via broadcast a lista de escalonamento) e Data Transfer (utilizado pelas estações para transmitir suas mensagens de dados). A principal vantagem do FTDMA sobre o TDMA tradicional é a possibilidade do reaproveitamento dos slots livres. A principal limitação encontrada nas quatro propostas apresentadas anteriormente reside no facto destas não considerarem as suas respectivas operações num ambiente de comunicação aberto. Desta forma, a existência de transmissões provenientes de redes que estejam fora da esfera de controlo da arquitetura de tempo-real pode resultar em perdas de deadlines. Hantrakoon e Phonphoem [30] propuseram um gestor para a fila de transmissão e um mecanismo de controlo de admissão denominado PHCCA (Priority-based HCCA). O gestor da fila de transmissão modifica o HCCA dividindo-o em três classes diferentes, organizadas pelo tipo de tráfego ou pela relevância do utilizador. O objetivo é fornecer um serviço de QoS (Quality of Service) com garantia mínima de recursos (starvation protection) para a classe de menor prioridade. Por outro lado, o mecanismo de controlo de admissão implementa um algoritmo de empréstimo de largura de banda onde as classes de maior prioridade podem solicitar a largura de banda das classes de menor prioridade (detalhado na seção 3.2). Apesar das melhorias realizadas nesta abordagem, Capítulo 3 - Trabalhos Relacionados 29 o problema de overhead do HCCA não foi solucionado. Uma avaliação experimental do framework RTnet [31] a operar numa rede IEEE 802.11 é apresentada por Boggia et al. em [32]. O RTnet foi originalmente proposto para comunicações de tempo-real hard em redes Ethernet. Neste contexto, a sua adaptação para redes IEEE 802.11 foi dada através da utilização de um esquema TDMA e da utilização do escalonador de tempo-real Xenomai [33]. De acordo com os autores, foram utilizados dispositivos sem fio contendo o chipset RT2500 [34] devido ao facto de ser o único suportado pelo RTnet. Esta abordagem é baseada numa arquitetura Mestre-Escravo onde a estação mestre gere a sincronização enviando mensagens periódicas às estações escravo. Com base nesta mensagem e no número de identificação atribuído à cada estação escravo, cada uma sabe em que momento se inicia e termina o seu slot. A principal limitação desta proposta está no facto de não ter sido levada em consideração a existência de tráfego externo a operar no mesmo canal de comunicação da rede de tempo-real, sendo este capaz de gerar interferências no sistema de sincronização. Seno et al. propuseram em [35] uma extensão do protocolo EPL (Ethernet Powerlink) [36] para redes IEEE 802.11. Foram utilizados os mesmos princípios do EPL original que opera de acordo com um esquema TDMA implementado na subcamada MAC e divide cada ciclo em períodos isócronos e assíncronos. No período isócrono, a estação mestre define o início do ciclo enviando uma mensagem (em broadcast) denominada Start of Cycle (SoC). Seguidamente, esta envia mensagens de autorização para cada estação escravo solicitando as suas transmissões. No final do ciclo, a estação mestre envia (em broadcast) uma mensagem denominada Start of Asynchronous (SoA) para notificar o início do período assíncrono. A principal limitação desta proposta é a possibilidade de existir uma rede sobreposta a gerar tráfego de forma não controlada. Isto faz com que o período isócrono do sistema não seja unicamente utilizado pelas estações autorizadas, mas também por estações que estejam fora da esfera de controlo do sistema de comunicação de tempo-real. Uma avaliação experimental desta proposta é apresentada por Gamba et al. em [13]. 3.1.1.2 Resolver Colisões Em [37], Bartolomeu et al. propuseram o WFTT (Wireless Flexible Time Triggered) inspirado no paradigma FTT [38], o qual foi aplicado com sucesso em outras tecnologias de comunicação como Controller Area Network (FTT-CAN) [39] e Ethernet (FTT-Ethernet) [40]. O WFTT é uma abordagem baseada numa arquitetura Mestre-Escravo que visa explorar a capacidade do mecanismo de bandjacking1em aumentar a prioridade no acesso ao meio e também a flexibilidade, pontualidade e eficiência do FTT em suportar comunicações de tempo-real para aplicações abrangendo requisitos estáticos e/ou dinâmicos. Assim, o WFTT divide o tempo de acesso ao meio em ciclos que são inicializados através da transmissão de uma mensagem de trigger (TM) efetuada pela estação mestre. Cada ciclo é dividido em três períodos: Protected (onde as mensagens são transmitidas sem contenção através do 1O funcionamento do mecanismo de bandjacking consiste no envio de impulsos de energia para que estações ao redor da estação transmissora atrasem as suas transmissões por considerarem o meio ocupado. 36 Capítulo 3 - Trabalhos Relacionados P-HCCA Centralizada Distribuída Arquitetura Esquema de Colisões Compatibilidade Evitar Resolver Reduzir IEEE 802.11 COTS CP-Multipoll Lee et al. FTDMA Miorandi et al. Boggia et al. Seno et al. PCF HCCA Son et al. WFTT Ripple WTRP WRTMAC Black-Burst Energy-Burst BTPS Shew et al. VTP-CSMA GDCF Lopez et al. H-EDCA CWFG DCC RT-FCR DFS Hamidian et al. DCF EDCA B-EDCA Figura 3.1: Comparação entre as propostas de controlo de acesso ao meio apresentadas. Duas outras soluções baseiam-se no HCCA. A primeira (Son et al. [24]) visa diminuir o problema do overhead do mecanismo de pollling punindo estações que recebam uma autorização mas não tenham mensagens para transmitir. No entanto, o método utilizado pode punir erradamente estações que tenham um fluxo de dados com um intervalo de serviço superior ao intervalo de serviço definido pelo HC, ou então estações que gerem tráfego aperiódico e/ou esporádico. A segunda solução (Hantrakoon e Phonphoem [30]) modifica o mecanismo de controlo de acesso ao meio Capítulo 3 - Trabalhos Relacionados 37 do HCCA para suportar três classes de prioridade diferentes, não efetuando qualquer melhoria relativa ao problema de overhead. Por fim, a última solução encontrada é apresentada por Moraes et al. [49]. Consiste num mecanismo baseado num esquema Token-Passing onde a passagem do token é implementada de forma virtual, ou seja, localmente em cada estação. Embora isto solucione o problema de perda do token, a maneira como este processo é implementado pode sofrer interferências quando as estações estão a operar num ambiente de comunicação aberto. Isto porque como a passagem do token baseia-se numa medição dos tempos de transmissão efetuados na rede, caso alguma estação não escute (por algum motivo) estas transmissões, esta pode interpretar erradamente a passagem do token, resultando assim em situações onde duas ou mais estações estejam de posse do token ao mesmo tempo. Torna-se assim evidente a necessidade de avançar com uma nova proposta para o mecanismo de controlo de acesso ao meio. Esta, por sua vez, deve ser capaz de favorecer o tráfego de temporeal tanto no acesso ao meio quanto na resolução de possíveis colisões. Deve também ser capaz de garantir os requisitos temporais das mensagens mesmo na presença de outras estações IEEE 802.11 standard a operar no mesmo canal de comunicação. Por fim, a nova proposta deve permitir suportar a implementação de um mecanismo de controlo de admissão e também ser capaz de ser implementada em hardware COTS. 3.2 Mecanismos de Controlo de Admissão Além de um mecanismo de controlo de acesso ao meio capaz de fornecer uma maior prioridade ao tráfego de tempo-real, tanto no acesso ao meio quanto na resolução de colisões, um sistema de comunicação de tempo-real deve também implementar um mecanismo de controlo de admissão. O principal objetivo deste mecanismo é limitar a quantidade de tráfego admitida por uma classe de serviço específica de forma que a QoS dos fluxos de dados já existentes não sejam degradadas, além de maximizar a utilização do meio de comunicação [19]. Neste contexto, são apresentadas nesta secção as principais propostas relacionadas ao mecanismo de controlo de admissão encontradas na literatura. Uma classificação geralmente utilizada para estes mecanismos consiste em dividí-los em três diferentes abordagens: Baseada em Modelos,Baseada em Medidas eHíbrida [61]. As propostas que utilizam uma abordagem baseada em modelos utilizam tipicamente modelos analíticos como critério de decisão para a admissão (ou não) de um fluxo de dados específico. A principal vantagem é a possibilidade de otimizar o sistema como um todo, mesmo antes da sua inicialização. Entretanto, a principal desvantagem é a dificuldade de se redefinir (sempre que necessário) os parâmetros do sistema de forma a acompanhar o comportamento dinâmico da rede. As propostas que utilizam uma abordagem baseada em medidas utilizam como critério as métricas obtidas do meio de comunicação e das estações comunicantes. Esta característica possibilita que os parâmetros do sistema sejam reajustados de acordo com o comportamento dinâmico da rede. No entanto, a sua principal desvantagem está na dificuldade em definir-se um limite 38 Capítulo 3 - Trabalhos Relacionados (threshold) apropriado para realizar a comparação com as métricas observadas. Além disto, dificilmente se obtém uma configuração "ótima" no momento da inicialização do sistema, uma vez que é necessário um tempo mínimo de operação para se obterem as métricas utilizadas. Com o objetivo de evitar as limitações previamente apresentadas, algumas propostas utilizam uma abordagem híbrida, que realiza uma fusão das características das abordagens baseada em modelos ebaseada em medidas. Neste caso, o sistema pode ser inicializado com um grupo de parâmetros "ótimo", o qual pode ser modificado dinamicamente de acordo com o comportamento da rede e/ou das estações. 3.2.1 Abordagens Baseadas em Modelos O mecanismo HCCA possui uma coordenação centralizada que permite o acesso ao meio livre de contenção. Baseia-se num esquema de polling que aloca TXOP aos fluxos de dados previamente admitidos. O seu mecanismo de controlo de admissão (apresentado no capítulo 2) implementa uma ACU (Admission Control Unit) responsável por decidir entre aceitar (ou não) um fluxos de dados. Esta ACU posteriormente define os parâmetros que permitem ao escalonador (baseado num esquema Round-Robin) a gestão do mecanismo de polling. Tanto a ACU quanto o escalonador encontram-se numa entidade lógica denominada HC, e residente normalmente no AP. Com o objetivo de disponibilizar um mecanismo de controlo de admissão baseado em prioridades ao HCCA, Hantrakoon e Phonphoem [30] propuseram o PHCCA (Priority based HCCA). Este mecanismo controla as filas de transmissão dividindo-as em 3 classes diferentes (derivadas da norma IEEE 802.3D) que podem ser organizadas pelo tipo ou pela relevância do utilizador. Para possibilitar novas admissões em classes de alta prioridade quando estas se encontrem esgotadas, o controlo de admissão implementa um algoritmo de partilha de banda (bandwidth borrowing algorithm). Este algoritmo possibilita que classes de maior prioridade possam solicitar banda “emprestada” de classes de menor prioridade para assim transmitir as suas mensagens. Para evitar problemas de starvation nas classes de menor prioridade, cada classe divide sua largura de banda em duas partes: uma passível de ser emprestada a uma classe de maior prioridade, e outra exclusiva da classe em questão. O controlo de admissão opera evitando que a soma da banda usada pelas 3 diferentes classes exceda a largura de banda máxima disponível. Em [62], Cicconetti et al. apresentam o RTH (Real-Time HCCA) que tem como objetivo assegurar uma capacidade fixa para as TS durante um intervalo de tempo fixo. Este mecanismo baseia-se no algoritmo EDF (Earliest Deadline First) com SRP (Stack Resource Policy) e considera a transmissão de uma mensagem como uma seção crítica, uma vez que não pode interromper a sua transmissão para transmitir outra mensagem (non-preemptive). O escalonador subdivide-se entre atividades online eoffline. A atividade online consiste em ler a próxima entrada [i,ti, TXOPi] escalonada. Esta é composta pelo índice da próxima TS, o tempo de polling e a duração da transmissão, respectivamente. A atividade offline é utilizada para efetuar o controlo de admissão e gerir os recursos disponíveis no sistema. Para solicitar a admissão de uma TS, a estação envia ao HC os seguintes parâmetros: taxa média de dados (Ri), tamanho da MSDU (MAC Service Data Unit)(Ni), atraso máximo (Di) e taxa de transmissão mínima da PHY (Γi). Capítulo 3 - Trabalhos Relacionados 39 Desta forma, cada TSié caracterizada por dois parâmetros: período (Ti) e capacidade (Ci). O período é dado por: Ti=(Dise Di<Ni/Ri jRi Ni×Dik×Ni Ricaso contrário (3.1) Neste caso, o período Tié definido como o atraso máximo da mensagem (Di), caso este seja inferior ao tempo médio entre as chegadas das mensagens na camada MAC da estação (Ni/Ri). Caso contrário, o período Tié definido como o maior múltiplo do intervalo entre chegadas que não seja superior a Di, respeitando assim a condição Ti≤Di. A capacidade é definida como o tempo mínimo necessário para que a TSicomplete a sua transmissão cumprindo seus requisitos, sendo dado pela seguinte equação: Ci=Ri×Ti Ni×tNi(3.2) onde tNié o tempo necessário para a transmissão de uma MSDU, incluindo o tempo necessário para a recepção da mensagem de ACK. Assim, para admitir uma nova TSk, inicialmente é realizado um teste de escalonabilidade levando em consideração o tempo de bloqueio que cada TSipode gerar. Primeiro a ACU calcula o tamanho da seção crítica (bi) de cada TSi. Este valor é dado pela seguinte equação: bi=tNi+tPi(3.3) onde tPié o tempo necessário para efetuar o polling da TSi(incluindo o IFS). Após isto é possível definir o bloqueio máximo (Bk) que uma TSkpode sofrer. Este valor é dado pela maior seção crítica encontrada entre todas as TSijá admitidas pelo sistema e que tenham um período maior que TSk: Bk=maxj>i{bj}(3.4) A análise de escalonabilidade produz a seguinte condição suficiente para determinar o grupo de nTS escalonáveis: Bi Ti +∑ j≤i Cj+πj×tPj Tj ≤1∀i: 1 ≤i≤n(3.5) onde πjé o número máximo de vezes que o AP pode efetuar polling em TSjdurante o período Tj. Em [63], Cecchetti et al propuseram uma alteração e adaptação para ambientes de comunicação sem fio do escalonador CBS (Constant Bandwidth Server) proposto por Albeni e Butazzo em [64], tendo como resultado o W-CBS (Wireless-CBS). Este algoritmo define de forma independente capacidades (budgets) para cada TSi(Qi). Assim, além de respeitar um escalonamento realizado por um algoritmo EDF, antes de permitir a transmissão por uma TS, a ACU verifica se esta contém um budget suficiente para realizá-la. 40 Capítulo 3 - Trabalhos Relacionados O parâmetro Qidefine a utilização máxima que a TSipode ter dentro do seu período Pide geração de mensagens. Ambos, Qie Pi, são enviados à ACU via TSPEC. Assim, o teste de escalonabilidade do W-CBS utiliza como base o período e o budget definido para cada TS, e para que seja aceite deve respeitar a seguinte inequação: N ∑ i=0 Qi Pi ≤T−TCP T(3.6) onde Pié o intervalo máximo de serviço (Maximum Service Interval – MSI). O valor do budget de uma TSi(Qi) é dado por: Qi=Qmin +CW F(Qmax −Qmin)(3.7) onde Fé uma função de peso de Qmin e Qmax. O parâmetro Qmin representa o menor budget necessário para que a TSipossa transmitir (durante o período Ti) uma MSDU utilizando a taxa média de dados. O parâmetro Qmax representa o maior budget necessário para que a TSipossa transmitir (durante o período Ti) a maior MSDU gerada utilizando a taxa máxima de dados. Portanto, no que concerne as limitações do mecanismo de controlo de admissão do HCCA, a sua abordagem pessimista (causada pela utilização da taxa mínima de transmissão e alocação das TXOP com base numa MSDU de tamanho máximo) resulta na subutilização do meio de comunicação. Outro problema é a sua incapacidade de gerir tráfegos VBR (Variable Bit Rate), uma vez que ao longo do tempo o tamanho e o número de mensagens podem diferir dos valores negociados no momento da admissão2. Além disso, a falta de um mecanismo de diferenciação das categorias de serviço e o facto da ACU não levar em consideração o nível de ocupação do meio de comunicação por outros dispositivos que estejam fora da esfera de controlo do mecanismo HCCA podem também serem consideradas limitações importantes. Com relação as limitações das restantes propostas apresentadas anteriormente, embora o RTH melhore a questão do escalonamento através da utilização de um algoritmo EDF/SRP, o PHCCA proporcione níveis de prioridade diferentes ao do HCCA e o W-CBS reduzida a ineficiência do cálculo da TXOP, todas estas propostas continuam a ter a maioria das limitações impostas ao HCCA original, uma vez que baseiam-se neste para a sua implementação. 3.2.2 Abordagens Baseadas em Medidas Em [65], Toscano e Lo Bello propuseram um mecanismo de controlo de admissão baseado no EDF e num factor de redundância (ρ) atribuído à cada TS. Este factor (alterado dinamicamente) define o número máximo de retransmissões que uma TS pode efetuar. O controlo de admissão opera sobre um mecanismo de controlo de acesso ao meio baseado num esquema Master/Slave. É reservada uma janela inicial para que o AP envie a mensagem de beacon e para que as estações 2Embora os algoritmos de codificação VBR clássicos tendam a gerar variações somente no tamanho das mensagens, alguns algoritmos permitem que este tamanho seja fixo, ou seja, podem ser geradas múltiplas mensagens com um tamanho limite pré-determinado. Capítulo 3 - Trabalhos Relacionados 41 realizem os seus pedidos de admissão. Em seguida, o AP envia para as estações mensagens de polling na forma de autorizações de transmissão. No processo de submissão de uma TSi, a estação precisa enviar à ACU o seu período de geração de tráfego (Ti) e o tamanho da maior mensagem que pode ser gerada (WCSizeDatai). Baseado neste último parâmetro, a ACU calcula o WCET (Worst Case Execution Time) para esta mensagem de dados da seguinte forma: WCETDatai=WCSizeDatai Bandwidth +latency (3.8) onde Bandwidth é a taxa de transmissão de dados e latency é uma estimativa do atraso no acesso ao meio. Após isto, é somado ao WCETDataio tempo necessário para o envio da mensagem de polling (WCETpoll) para definir-se o tempo total WCETi. Desta forma, o tempo alocado pela ACU à TSi(Ci) é dado pelo valor de WCETie por um factor de redundância (ρi): Ci=ρi×WCETi(3.9) O valor ρié alterado dinamicamente com base na estimativa do PER (Packet Error Ratio) sofrido por cada cada TSi. Esta estimativa leva em consideração a média de mensagens perdidas dentro de uma janela de observação. Além do PER, a ACU utiliza também como base para a definição do valor de ρia taxa máxima de perda tolerável pela TSi(MaxPERi), a qual é informada à ACU pela estação no processo de admissão. Esta taxa define a fração mínima de mensagens que devem ser entregues corretamente antes das respectivas deadlines. Assim, a ACU altera o valor de ρicom base na seguinte regra: ρi=           1 se k = 0 ρi+1 se PERi>MaxPERi ρi−1 se EarlyCompletioni(m) for TRUE ρicaso contrário (3.10) onde k=0 é o número de mensagens transmitidas na janela de observação e EarlyCompletioni(m) representa mmensagens consecutivas transmitidas com sucesso e a utilizar um número de retransmissões inferior a ρi. Portanto, para que seja possível a admissão de uma nova TSkou a alteração do factor ρide alguma TSijá admitida, os novos parâmetros devem respeitar a seguinte inequação: k ∑ i=1 Ci Ti +Bk Tk ≤1∀k=1,2,...,N(3.11) onde Bké o bloqueio máximo que a TSipode sofrer. Como o mecanismo utiliza o EDF não preemptivo, Bké igual ao maior Ciadmitido pela ACU. 42 Capítulo 3 - Trabalhos Relacionados Desta forma, uma limitação desta proposta é a abordagem pessimista no cálculo de tamanho da TXOP. Embora o seu superdimensionamento acabe por resultar no suporte ao tráfego VBR3 isto resulta na subutilização do meio de comunicação. Outro ponto importante é a definição do valor de bloqueio Bk, o qual é definido como o maior valor Cidentre as TS previamente admitidas, ignorando assim o bloqueio que pode ser gerado pelo tráfego proveniente de estações que estejam fora da esfera de controlo do sistema de comunicação proposto. Em [66], Bazzi et al. apresentam dois diferentes mecanismos de controlo de admissão para redes IEEE 802.11 infraestruturadas. O primeiro baseia-se no nível de ocupação do meio de comunicação (Co) observado pelo AP. Este valor é dado em função do tempo de ocupação do meio (TB) num intervalo de observação 4T: Co=TB 4T(3.12) Para garantir que o valor de TBseja computado corretamente, é somado ao seu valor o tempo de transmissão gasto pelo AP (TAP), ou seja, TB= TAP + TSB. O principal objetivo é garantir um alto throughput. Assim, o modelo tenta manter um nível de ocupação do meio elevado sem exceder o ponto de saturação (CT), o qual é previamente definido pelo sistema. Quando este valor é ultrapassado, não são permitidas novas admissões até que a ocupação do meio diminua e se encontre inferior à um nível pré-determinado chamado de "descongestionamento" (DT). O segundo mecanismo proposto utiliza a informação sobre o tamanho da fila de transmissão do AP, ou seja, considera somente o tráfego downlink. Nesta abordagem o aumento da fila representa um congestionamento da rede, sendo a sua diminuição um sinal de descongestionamento. Neste caso, o threshold é definido pelo nível de utilização do buffer de transmissão. Para evitar oscilações repentinas, o mecanismo faz uso de um factor de persistência (TP) que indica quanto tempo os níveis devem se manter acima ou abaixo dos thresholds pré-estabelecidos antes de modificar o estado da fila. Neste caso, são permitidas novas admissões apenas quando o mecanismo se encontra no estado de descongestionamento. Em [67] Yong et al. propuseram um mecanismo de controlo de admissão para redes IEEE 802.11 infraestruturadas baseado no nível de ocupação da rede e no atraso máximo tolerável pela TS. Este atraso é definido pela estação no momento da admissão através do envio de mensagens TSPEC. No AP, um mecanismo monitoriza constantemente as diferentes ifilas de receção descrevendo assim diferentes níveis de prioridade. Baseado nisto, o mecanismo define uma taxa de recepção (λi) para cada fila. Da mesma forma, outro mecanismo monitoriza as filas de transmissão obtendo assim uma taxa de envio (µi) para cada uma. Como podem existir múltiplas prioridades, o problema é modelado como uma fila de prioridade preemptiva com uma única taxa de serviço. 3Uma vez que o mecanismo utiliza como base de cálculo para o controlo de admissão a maior mensagem que pode ser gerada pela aplicação, qualquer variação no tamanho das mensagens não afetará os valores calculados pela ACU. Capítulo 3 - Trabalhos Relacionados 43 O mecanismo de controlo de admissão admite apenas uma nova TS se esta cumprir dois requisitos. O primeiro é o atraso máximo tolerável pela TS na fila a qual as mensagens serão transmitidas (Delayi). Assim, o valor estipulado de Delayideve respeitar a seguinte inequação: Delayi<∑n i=1ρi/µi (1−σi−1)×(1−σi)(3.13) onde µidenota uma taxa de serviço markoviana e ρia sua respectiva taxa de utilização para a fila i. Baseado nesta inequação o modelo proposto consegue estimar o tempo de espera das mensagens nas diferentes filas de transmissão. Os valores de ρieσnsão dados pelas seguintes equações, respectivamente: ρi=λi µi (3.14) σn= n ∑ i=0 ρn(3.15) O segundo requisito para a admissão de uma nova TS é a sua taxa de utilização (Ratei), a qual deve respeitar a seguinte inequação: Ratei+CURRENTBW <AdmitTi(3.16) onde CURRENTBW é a estimativa da banda total utilizada e AdmitTé um threshold definido pelo sistema para a fila i. Em [68], Kim et al. propuseram um mecanismo de controlo de admissão implementado sobre um MAC capaz de criar prioridades de acesso por meio do uso de impulsos de energia (busy-tone). No mecanismo MAC proposto, filas com menor prioridade podem transmitir apenas quando não existirem mensagens para serem transmitidas nas filas de maior prioridade. Para que isto seja possível, as estações que desejam efetuar suas transmissões precisam aguardar que o meio fique livre por aSIFSTime + (AIFSN ×aSlotTime) - aSlotTime. Em seguida a estação envia um pulso de energia do tamanho de um aSlotTime e logo após efetua a transmissão da mensagem utilizando o mecanismo EDCA. Caso alguma estação que tenha mensagens na fila de transmissão receba um pulso de energia antes de finalizado o período de deteção do estado (livre/ocupado) do meio, esta suspende o envio do seu próprio pulso de energia. Assim, as filas com menor prioridade transmitem apenas quando não existirem mensagens para serem transmitidas nas filas de maior prioridade de qualquer outra estação. Os valores de AIFSN são diferentes para cada fila (variando de 0 a 3). Para diferenciar entre a transmissão de uma mensagem em um impulso de energia o mecanismo utiliza os seus respectivos tempos de duração, uma vez que a duração de um impulso de energia é inferior a 1 aSlotTime e a duração de uma mensagem normalmente é superior a 3 aSlotsTime, dado o tamanho do cabeçalho da camada física. 44 Capítulo 3 - Trabalhos Relacionados O controlo de admissão deste mecanismo, denominado PAAC (Priority Access-based Admission Control), encontra-se no AP e utiliza informações TSPEC enviadas pelas estações que desejam submeter novas TS. Para realizar uma nova admissão, inicialmente o PAAC calcula o tempo de ocupação que a nova TS irá necessitar. Assim, calcula no final de cada intervalo de beacon (BI) os seguintes valores para cada ACi: intervalo de transmissão (TIi), tempo total de backoff (BPi), número de transmissões (NTi) e número de colisões (NCi). Baseado nestes valores, o AP obtém a taxa de utilização do canal (Umeasure i), a probabilidade de colisão (Pmeasure i) e o tempo médio de backoff (Bmeasure i), que são dados, respectivamente, por: Umeasure i=TIi BI (3.17) Pmeasure i=NCi NTi (3.18) Bmeasure i=BPi NTi (3.19) Posteriormente um mecanismo baseado em uma janela deslizante obtém os valores aproximados do tempo médio de utilização do meio (Ui), da probabilidade média de colisão (Pi) e do tempo médio de backoff (Bi) por tentativa de transmissão: Ui=αUi+(1−α)×Umeasure i(3.20) Pi=αPi+(1−α)×Pmeasure i(3.21) Bi=αBi+(1−α)×Bmeasure i(3.22) onde αé um factor de suavização que varia de 0 a 1. Valores próximos de 1 fazem com que as mudanças sejam mais lentas enquanto que valores próximos de 0 fazem com que as mudanças sejam mais rápidas. Para solicitar a admissão numa AC i, uma TSkenvia uma mensagem ADDTS ao AP contendo os seguintes parâmetros: tamanho médio da mensagem (Li,k), taxa média de dados (ρi,k) e a taxa de transmissão física (Ri,k). Ao receber a solicitação, o AP calcula o número de mensagens enviadas pela TS durante um intervalo de beacon (Ni,k) e o número total de mensagens transmitidas em caso de colisões (Ni,k,total =Ni,k/1−Pi). Em seguida, o AP calcula o tempo necessário para se transmitir as Ni,k,total mensagens (ChTimei,k). Este valor é dado pela seguinte equação: ChTimei,k=Ni,k×TS+(Ni,k,total −Ni,k)×TC+Ni,k,total ×(Bi+AIFS[i]) (3.23) Capítulo 3 - Trabalhos Relacionados 45 onde TSé o tempo para se efetuar uma transmissão com sucesso e TCé o tempo médio de ocupação do meio resultante de colisões. Assim, a taxa de utilização de uma nova TS é dada por: Ui,k,require =ChTimei,k BI (3.24) Como a ACU do mecanismo PAAC divide o tempo total do meio (C) em 4 diferentes porções (voz, voz e vídeo, vídeo e outros tipos), cada ACipossui uma porção exclusiva alocada para si. Portanto, é utilizada a seguinte inequação para decidir entre a admissão (ou não) de uma nova TS k: Ui+Ui,k≤CTi(3.25) onde CTié a taxa de utilização livre da ACie que ainda pode ser alocada para novas TS. Em [69], Shin e Schulzrinne especificam um controlo de admissão chamado QP-CAT (Queue size Prediction using Computation of Additional Transmission). Este mecanismo tem por objetivo prever o tamanho da fila de transmissão do fluxo downlink de uma TS, para que então possa ser possível prever o seu respectivo atraso e impedir (caso necessário) a admissão de novas TS evitando assim a saturação do meio de comunicação. Inicialmente é feita a admissão da nova TS de forma virtual, levando em conta o período de geração das suas mensagens. Então, através da monitorização do meio e levando em conta a transmissão de mensagens reais, é calculado o número adicional de mensagens virtuais que poderiam ser enviadas. Por último, o número de mensagens adicionais que poderiam ser enviadas é subtraído do tamanho da fila virtual. Sendo assim, o tamanho previsto da fila é o número total de mensagens na fila atual e na fila virtual. Para emular uma nova TS, são utilizados dois contadores especiais (UpCounter eDnCounter). Estes contadores armazenam o número de mensagens uplink edownlink, e ambos são incrementados em 1 a cada ciclo de geração da mensagem. Os respectivos valores são decrementados durante a execução baseado no número de mensagens nptransmitidas. Desta forma pode-se afirmar que a soma da fila atual no AP com o valor de DnCounter será o tamanho previsto da fila de downlink no AP caso uma nova TS seja admitida. Para admitir uma nova TS, o QP-CAT mede o tempo livre no meio (Tc). Caso seja utilizado o EDCA, então o valor de Tcé dado pelo tempo não utilizado de uma TXOP, ou seja, o tempo que poderia ser alocado para o envio de mensagens de outra TS. A partir disto é calculado o número de mensagens adicionais que são passíveis de serem enviadas (np) utilizando a seguinte equação: np=Tc Tt(3.26) onde Tté o tempo necessário para a transmissão de uma mensagem (com sucesso) incluindo o tempo de backoff e os tempos IFS. 52 Capítulo 3 - Trabalhos Relacionados valor de TXQAP diminui proporcionalmente com o aumento de α. O controlo de admissão, por sua vez, monitoriza continuamente os recursos da BSS e reserva uma largura de banda específica para cada AC. Assim, uma nova TS só pode ser admitida se existir largura de banda disponível para a AC a que se destina. Quando uma nova TS solicita sua a admissão, o algoritmo começa por calcular o nível de utilização do meio de comunicação caso a nova TS seja admitida. Esta estimativa baseia-se no modelo apresentado em [78] o qual prevê othroughput máximo que uma WLAN pode alcançar baseado no tamanho médio das mensagens transmitidas. Desta forma, primeiramente o algoritmo calcula o tamanho médio das mensagens (FrSzavg) dentro de uma janela de observação: FrSzavg =∑f lows(Frf low ×FrSzf low) ∑f low Frf low (3.42) onde, Frf low é o número de mensagens transmitidas e FrSzf low é o tamanho das mensagens transmitidas. Como esta equação considera tanto as mensagens transmitidas pelas TS já admitidas quanto as mensagens que deverão ser transmitidas pela nova TS submetida, o valor FrSzavg corresponde ao tamanho médio das mensagens caso a nova TS seja admitida. Othroughput equivalente (Thpeq) é dado pela seguinte equação: Thpeq =T hpre f PkSzre f ×PkSzavg ×s1+log2PkSzre f PkSzavg (3.43) onde Thpre f é o throughput de referência da BSS e PkSzre f é o tamanho médio de referência das mensagens. Como a ACU aloca diferentes percentagens de banda para cada AC, caso o valor de Thpeq ultrapasse o valor alocado, a TS é rejeitada, caso contrário é admitida. A principal limitação deste mecanismo encontra-se na sua premissa que tem como base a garantia de um alto throughput nas comunicações. No entanto, isto não representa necessariamente o cumprimento dos prazos de entrega das mensagens. Em [79] Cicconetti et al. propuseram o WTTP (Wireless Timed Token Protocol) baseado no TTP (Timed Token Protocol) e opera sobre o mecanismo de acesso ao meio do HCCA. Nesta abordagem, um token é utilizado para gerir uma lista Round-Robin. Nesta lista, cada entrada representa um fluxo (downlink ou uplink) de uma TS. Uma entrada especial é alocada para representar o tráfego gerado por estações que utilizam um esquema de acesso ao meio baseado em contenção (EDCA e DCF). A ACU verifica cada entrada da lista e calcula um tempo denominado sojourn time (equivalente ao TXOP) para a TS em questão. A ACU insere e remove TS da lista de acordo com a existência (ou não) de mensagens nas suas respectivas filas de transmissão. No caso do tráfego downlink, a verificação do estado da fila de transmissão torna-se transparente, uma vez que este tráfego é proveniente do AP. No entanto, como o estado das filas do tráfego uplink são conhecidos somente pelas estações, um mecanismo de piggyback é utilizado para informar o AP (através das mensagens de dados) acerca do estado da fila de cada TS. Neste caso, as TS são inseridas na lista Capítulo 3 - Trabalhos Relacionados 53 ou quando o AP recebe a informação de que há novas mensagens na fila de transmissão da estação ou quando o SI mínimo da TS em questão é atingido. A rotação do token é regida pelo TTRT (Target Token Revolution Time), que é um parâmetro equivalente ao SI do sistema. Este valor é calculado pela ACU de acordo com os parâmetros TSPEC enviados pelas estações durante a fase de admissão (taxa média de geração de dados Ri, tamanho da MSDU Ni, tamanho máximo da MSDU Mie atraso máximo Di), sendo definido como a metade do menor Diencontrado dentre as TS admitidas pela ACU: TTRT =mini{Di} 2(3.44) O mecanismo divide o tempo definido por TTRT em duas partes denominadas de banda simétrica e banda assimétrica. As transmissões com garantias HCCA são efetuadas apenas na banda simétrica. O sojourn time atribuído a cada TS é calculado de forma diferente para cada banda. Na banda simétrica, este tempo (denominado Hi) é fixo e calculado como uma percentagem do TTRT. Na banda assimétrica, este valor é uma porção variável e não reservada de TTRT. Em outras palavras, cada entrada item um Hi≥0 e um TRTi(Token Rotation Timer) inicialmente definido com o valor de TTRT. O valor de TRTié decrementado a partir do último serviço provido pelo HC. Quando uma entrada ié servida, a banda assimétrica (ai) é calculada com base na seguinte regra: ai=(0TRTi<0 min{TTRT −Hi,TRTi}caso contrário (3.45) Desta forma, uma TS assimétrica pode transmitir mensagens apenas se o token for recebido antes do previsto, ou seja, antes de 1 ×TTRT após a última receção do token. Isto ocorre quando outra TS assimétrica consome menos recursos do que o reservado. A alocação do sojourn time é definida como uma fração fixa de TTRT, ou seja, este valor nunca é recalculado. No caso de recursos não utilizados, a estação realoca-os para o tráfego baseado em contenção. O tempo Hina banda simétrica para ambos os tráfegos CBR e VBR é dado por: Hi=tx(P)×I(i)+Ri×TTRT Ni×tx(Ni,Γi)(3.46) onde tx(P)é o tempo necessário para transmitir a mensagem de polling,I(i)é uma função que indica qual a direção do fluxo de dados (1 se for uplink e 0 se for downlink) e tx(Ni,Γi)o tempo necessário para se transmitir uma MSDU de tamanho Nia uma taxa de transmissão física Γi. Neste contexto, uma nova TS só pode ser admitida se respeitar a seguinte inequação: ∑ i Hi+τ≤TTRT (3.47) onde τé o tempo necessário para se retomar o controlo do meio de comunicação e iniciar uma nova CAP após uma fase EDCA. 54 Capítulo 3 - Trabalhos Relacionados A principal limitação desta proposta encontra-se na abordagem conservadora do escalonador em termos do atraso máximo tolerável pelas estações, implicando que uma estação possa receber otoken mais vezes que o necessário (tal como o HCCA), o que resulta num overhead adicional. Em [80], Ruscelli et al. propuseram um mecanismo auxiliar em cada estação denominado Overboost. Este possibilita a gestão de tráfegos VBR através da cooperação entre os mecanismos HCCA e EDCA. Esta cooperação baseia-se no modo HEMM (HCCA/EDCA Mixed Mode) definido na norma IEEE 802.11e. Neste caso, as admissões de novas TS são geridas pelo mecanismo HCCA original. No entanto, caso no fim de uma TXOP alguma TS possua ainda mensagens para serem transmitidas, o Overboost move as mensagens excedentes para a fila de mais alta prioridade do mecanismo EDCA (fila de voz). Após o término do CFP, o EDCA (através da intervenção do Overboost) envia as mensagens excedentes do mecanismo HCCA e posteriormente envia as mensagens alocadas pelo mecanismo EDCA original. Isto faz com que, principalmente em casos onde o tráfego é VBR, as TS possam utilizar o meio de comunicação mais tempo do que o alocado pela ACU através da TXOP. A principal limitação deste mecanismo encontra-se no indeterminismo que o EDCA impõe às TS. Isto resulta principalmente de dois motivos: i) embora o Overboost transmita inicialmente as mensagens excedentes do mecanismo HCCA, estas são transmitidas pelo EDCA e assim podem sofrer colisões com mensagens oriundas de redes que estejam fora da esfera de controlo do sistema de tempo-real; e ii) a transmissão das mensagens excedentes, cujo número pode variar a cada ciclo, é diretamente dependente do tamanho do CP alocado ao mecanismo EDCA. Assim, caso este seja demasiado pequeno e/ou existam demasiadas mensagens para serem transmitidas, podem ocorrer perdas de deadlines. Em [81], Ansel et al. apresentam o FHCF (Fair HCF) que é composto por dois escalonadores: um no AP e outro nas estações. O escalonador do AP é responsável por estimar a variação no tamanho da fila de cada estação (qest i) antes do início do próximo SI e compará-lo com o valor ideal (qideal i). O escalonador do AP utiliza uma janela de estimativa de erro para cada TS admitida com o intuito de adaptar o cálculo da TXOP. Por outro lado, o escalonador nas estações é responsável por redistribuir entre suas TS o tempo não utilizado de uma TXOP alocada. Inicialmente o AP calcula o tamanho ideal da fila de cada TS ino início de cada SI. Neste caso, o tamanho da fila é calculado levando em consideração que no final da sua TXOP todas as mensagens foram transmitidas, ou seja, o tamanho da fila é 0, ou seja: qideal i=ρi×(SI −∑ij=1Nj×(Mj Re f f +2×tSIFS +tACK)) Mi (3.48) onde ρié a taxa média de geração de dados, Njé quantidade de mensagens que devem ser transmitidas, Mjé o tamanho das mensagens, Re f f é a taxa de transmissão efetiva e Mié o tamanho da mensagem da TS i. Ao enviar uma mensagem de dados a estação insere no seu cabeçalho (no final da TXOP) o tamanho atual da sua fila de transmissão (qe i). Uma vez que o AP conhece este instante de tempo Capítulo 3 - Trabalhos Relacionados 55 (te i), é possível então estimar o tamanho da fila (qest i) da TSino início do próximo SI: qest i=ρi(SI −te i) Mi +qe i(3.49) Como a taxa de envio e o tamanho das mensagens podem variar ao longo do tempo, esta estimativa realizada pelo AP não é exata. Para resolver este problema o FHCF utiliza uma janela de observação w(a qual têm valores reais observados pelo AP) para melhorar as estimativas. Isto significa que ao n-ésimo SI, o AP terá a sua disposição as wúltimas estimativas de erro. Estes valores são dados por: 4n−1 i=qb,real i(n−1)−qb,est i(n−1)(3.50) 4n−2 i=qb,real i(n−2)−qb,est i(n−2)(3.51) ... (3.52) 4n−w i=qb,real i(n−w)−qb,est i(n−w)(3.53) Assim, o AP pode calcular a diferença entre os valores estimado e real para o próximo SI n: E[|4i(n)|]≃∑n−1 j=n−w|4i(n)| w(3.54) Este valor é utilizado para melhorar a estimativa do tamanho da fila da TS ino próximo SI n: qb,est i,new(n) = qb,est i(n)+E[|4i(n)|](3.55) No início do próximo SI, o AP compara o tamanho estimado da fila com o seu tamanho ideal e calcula o número de mensagens adicionais (DNest i) que possam existir. O AP calcula o tempo de ajuste (test i), que pode ser positivo ou negativo, que é necessário para cada TS recalcular a TXOP: test i=DNest i×Mi Re f f +2×tSIFS +tACK(3.56) Para verificar se o escalonador é capaz de realizar estas alterações o AP compara a soma de todos os valores positivos (TP) e a soma de todos os valores negativos (TN) com o tempo restante do mecanismo HCCA após alocar todas as TXOP (T’). Caso TPTN>T’, significa que o escalonador não é capaz de alocar todo o tempo extra solicitado e que o mesmo deve ser reduzido. Neste caso, para garantir igualdade entre as TS, o escalonador reduz cada test ipositivo com uma porcentagem β. Por outro lado, cada test inegativo é incrementado na mesma porcentagem. O valor de βé dado por: β=(TP−TN)−T0 TP+TN (3.57) 56 Capítulo 3 - Trabalhos Relacionados Baseado nestas alterações, o tempo adicional efetivo (tadd i) aplicado a cada TS é dado por: tadd i=((1+β)ttest itest i≥0 (1−β)ttest itest i<0(3.58) onde o valor tadd ié calculado juntamente com os valores das TXOP alocadas pelo HCCA. O escalonador executado em cada estação tem como função redistribuir o tempo adicional de uma TXOP entre as suas TS. Este executa o mesmo cálculo que o escalonador do AP mas com mais exatidão, uma vez que sabe exatamente o tamanho das filas de cada TS no momento da receção da mensagem de polling. Assim, é capaz de estimar o tamanho da fila no final da TXOP e também o tempo adicional necessário para a TS. De acordo com o tempo Talocado por uma TXOP, a estação pode estimar o tempo restante T0que pode ser realocado entre as TS considerando o número de mensagens (Ni) para transmitir em cada T Sie seus respectivos tempos de transmissão. O valor de T0é dado pela seguinte equação: T0=T− p ∑ i=1 Ni×Mi Re f f +2×tSIFS +tACK(3.59) A principal limitação deste mecanismo encontra-se na generalização das prioridades do tráfego, ignorando a deadline de cada TS. Além disto, embora a verificação das filas de transmissão seja capaz de garantir uma gestão do tráfego aperiódico e esporádico, não é capaz de fazer o mesmo com o tráfego VBR (na variação no tamanho das mensagens), uma vez que esta informação é enviada ao AP somente no momento da admissão, e este somente estima o tamanho da fila baseado no número de mensagens e não no tempo necessário para a sua transmissão. Toscano e Lo Bello [82] apresentam um mecanismo de controlo de admissão baseado no escalonador EDF não preemptivo. Cada TS admitida pelo sistema define uma taxa de sucesso mínima a qual esta deve operar, ou seja, a fração mínima de mensagens que devem ser entregues corretamente e antes da deadline. O mecanismo utiliza a taxa de perda de cada TSipara calcular a sua probabilidade de erro (Ei). Cada TSié descrita pelos seguintes parâmetros: deadline relativo (Di), tempo máximo de transmissão (Ci), taxa de erro (Ei) e taxa de sucesso (si). Caso ocorra um erro de transmissão a mensagem é reescalonada com a mesma deadline da mensagem original. O principal objetivo deste mecanismo é considerar no teste de escalonabilidade o número de retransmissões que permite que a taxa de sucesso seja atingida. Uma vez que as probabilidades de sucesso para cada tentativas de transmissão são estatisticamente independentes, pode-se assumir que dada a probabilidade de erro Ei, a probabilidade de uma mensagem ser perdida após Mtentativas de transmissão é EM i. Como resultado, o número mínimo de tentativas de transmissão Mi que satisfaz os requisitos em termos de probabilidade de sucesso na transmissão sié dado por: Mi=dlogEi(1−si)e=log(1−si) log(Ei)(3.60) onde Mié decrementado em 1 (Mi1) para se obter exclusivamente o número de retransmissões. Capítulo 3 - Trabalhos Relacionados 57 No entanto, considerar que cada TSideva ter um número de retransmissões Mié demasiado pessimista, uma vez que somente torna-se necessária uma retransmissão quando a transmissão anterior falhou. A análise do mecanismo é realizada pela modelagem das retransmissões das mensagens como uma TS periódica. Do grupo original de TS (Φ= TS1, TS2, ..., TSN) é derivado um novo grupo Φ* o qual inclui as retransmissões de mensagens. Para cada TSido grupo original, um grupo TSi,1, TSi,2, ..., TSi,Mié gerado, onde TSi,1é a primeira transmissão. Como resultado temos Φ* = SN i=1{TSi,1,TSi,2,...,TSi,Mi}. A mesma notação é utilizada para os períodos das mensagens onde Ti,1representa o período da primeira transmissão. Os seus valores são definidos de acordo com a frequência média de cada retransmissão. Para a primeira transmissão de cada TSio período é conhecido, ou seja, Ti,1= Ti. Por outro lado, para a primeira retransmissão, como a probabilidade de erro é Eientão Ti,2=Ei/Ti. Sendo assim, a segunda retransmissão é dada com a probabilidade de erro E2 i, o que resulta em Ti,3=E2 i/Ti. Com base nesta consideração, os períodos Ti,jdas TS podem ser definidos por: Ti,j=(Tij=1 Ti (Ei)j−1j=2,3,...,Mi (3.61) Levando em conta que o deadline relativo de uma retransmissão é igual ao da mensagem original (1a tentativa), e que o escalonador EDF é não preemptivo, uma alteração no teste de escalonabilidade foi proposta. Desta forma, uma condição suficiente para alcançar a taxa de sucesso desejada em um grupo de NTS escalonadas de acordo com o algoritmo EDF é possível respeitando a seguinte inequação: N ∑ i=1 Mi ∑ j=1 Ci,j Ti +Bk Tk ≤1∀k=1,2,...,N(3.62) onde Cié o tempo de transmissão e Bké o bloqueio do sistema, dado por Bk= max(Ci,j). No entanto, esta inequação acaba por ser pessimista, uma vez que transforma o tempo entre chegadas das retransmissões em deadlines relativos. Com o objetivo de propor um modelo menos pessimista, os autores utilizaram a análise de Spuri [83] que se baseia no conceito de período de ocupação (busy period). Desta forma é possível prover a seguinte condição suficiente: d≥∑ Di≤d Mi ∑ j=11+d−Di Ti,jCi,j+Bk(d)(3.63) onde dé o deadline absoluto, Diodeadline relativo e Bk(d)é o maior bloqueio sofrido pela TS k. Embora esta proposta otimize o cálculo da TXOP com base num mecanismo que avalia independentemente cada retransmissão realizada por uma TS, isto por si só não garante o cumprimento das deadlines. Esta limitação resulta do facto de que nem sempre a alocação de uma grande TXOP a uma TS significa o cumprimento da respectiva deadline, uma vez que esta pode ser perdida em consequência de um atraso no acesso ao meio. Além disso, o cálculo de ocupação do meio de comunicação efetuado por este mecanismo, pelo mecanismo apresentados por Cruz et al. [74] e pelos mecanismos PRCW [73] e DTXOP 58 Capítulo 3 - Trabalhos Relacionados [77] apresentando anteriormente não levam em consideração o tráfego gerado por estações que estão fora da esfera de controlo da arquitetura de tempo-real. Isto pode levar a decisões erradas na admissão de novas TS ou na definição dos tempos de bloqueio, podendo em algumas situações resultar na saturação do meio de comunicação e consequentemente degradação da QoS de todas as TS previamente admitidas. 3.2.4 Síntese dos Mecanismos de Controlo de Admissão A implementação dos mecanismos de controlo de admissão tem um papel fundamental na construção de uma arquitetura de comunicação de tempo-real. Através deste é possível garantir os recursos necessários e impedir a saturação do meio de comunicação, consequentemente impedindo também a perda das deadlines das mensagens. Neste contexto, alguns mecanismos encontrados na literatura focam os seus esforços na resolução do problema da imprecisão gerada pelo tráfego VBR, enquanto outros focam-se na limitação do tamanho imposto às TXOP, facto que impede um melhor desempenho na transmissão de fluxos contendo grandes quantidades de dados (por exemplo, vídeos de alta definição). No entanto, é importante ter em conta que estes problemas não ocorrem na grande maioria dos sistemas de comunicação de tempo-real utilizados em ambientes industriais. Isto deve-se ao facto de, em termos gerais, as mensagens trocadas entre os dispositivos de tempo-real serem periódicas, de tamanho fixo (ou seja, caracterizadas por um tráfego CBR) e contendo uma pequena quantidade de dados (eliminando assim o problema de limitação do tamanho da TXOP). Outros mecanismos focam os seus esforços na precisão do cálculo da TXOP atribuída a cada fluxo de dados admitido. O principal desafio encontrado por estas propostas é a variação ocorrida na taxa de transmissão de cada estação, que pode surgir devido à mobilidade ou então por possíveis interferências sofridas pelas estações. Neste contexto, algumas propostas possibilitam ao controlo de admissão recalcular tanto os recursos disponíveis no sistema quanto os recursos necessário para cada TS. Estes cálculos geralmente são efetuados com base na verificação da nova taxa de transmissão utilizada por cada estação. No contexto do algoritmo de escalonamento, são utilizados diferentes algoritmos de temporeal para tornar possível a definição da ordem de transmissão das TS admitidas. Esta ordenação pode tomar como base parâmetros enviados pelas estações via TSPEC (por exemplo, atraso limite), medidas efetuadas na rede (por exemplo, carga total) ou até medidas efetuadas nas estações (por exemplo, tamanho da fila de transmissão). Portanto, ao considerarmos a transmissão de tráfego de tempo-real num ambiente de comunicação aberto, podemos concluir que além das informações TSPEC enviadas pelas estações de tempo-real, a ACU deve levar em conta também o comportamento dinâmico do meio de comunicação. Este comportamento pode ser alterado em resultado de transmissões efetuadas por estações de não tempo-real ou por ruídos no meio de comunicação. Assim, e com base na classificação previamente definida, podemos concluir que a utilização de uma abordagem híbrida pelo mecanismo de controlo de admissão apresenta-se como uma opção promissora, uma vez que esta é capaz de iniciar o sistema a partir de um modelo analítico e Capítulo 3 - Trabalhos Relacionados 59 posteriormente alimentá-lo com informações constantemente atualizadas, sejam estas do meio de comunicação, sejam das estações. Assim é possível eliminar as limitações apresentadas pelas restantes abordagens5. Outro ponto fundamental na construção de um mecanismo de controlo de admissão é a utilização do elemento TSPEC para que as estações possam informar a ACU dos requisitos e características de cada TS que desejam transmitir. Além disso, este procedimento possibilita também a definição das deadlines das mensagens, informação considerada fundamental para um sistema de comunicação de tempo-real. Como consequência, torna-se possível utilizar um algoritmo de escalonamento de tempo-real para organizar a sequência de transmissão das mensagens com base nas suas respectivas deadlines. Por fim, outra característica importante que deve ser levada em consideração para a construção de um mecanismo de controlo de admissão é a respectiva operação num ambiente de comunicação aberto, onde o tráfego gerado pelas estações que estão fora da esfera de controlo da arquitetura de tempo-real pode resultar em atrasos e bloqueios diferentes dos calculados num ambiente fechado. Em jeito de conclusão, são listados seguidamente os requisitos julgados necessários para a implementação de um mecanismo de controlo de admissão de um sistema de comunicação de tempo-real: • obrigatoriamente utilizar uma abordagem híbrida, obtendo tanto informações das TS (via TSPEC), quanto do meio de comunicação para efetuar a admissão (ou não) de uma nova TS; • deve ser capaz de gerir variações repentinas que possam ocorrer nos valores medidos no meio de comunicação e/ou nas estações; • preferencialmente ser implementado sobre uma arquitetura centralizada; • caracterizar as TS através do uso de informações TSPEC; • implementar um algoritmo de escalonamento de tempo-real para organizar a sequência de transmissão das mensagens com base nas respectivas deadlines; • identificar e remover TS que possam se encontrar num estado de "falha", ou seja, que estejam com recursos alocados mas que não estejam em operação. A Figura 3.2 resume e classifica os diferentes mecanismos de controlo de admissão apresentados previamente. Além de apresentar uma classificação quanto à abordagem utilizada (definida no início desta secção), apresenta também algumas das principais características de cada mecanismo avaliado. A primeira divide os mecanismos quanto à sua arquitetura (centralizada ou distribuída). De forma complementar são apresentados os tipos de tráfegos (CBR, VBR e aperiódico6) suportados por cada mecanismo, suporte às informações TSPEC, utilização de informações provenientes 5As limitações das abordagens utilizadas para implementar o mecanismo de controlo de admissão são discutidas no início desta secção. 6O suporte ao tráfego esporádico não é caracterizado uma vez que este pode ser modelado como um tráfego periódico com período igual ao seu intervalo mínimo de geração (MIT – Minimum Interarrival Time). 60 Capítulo 3 - Trabalhos Relacionados do ambiente de comunicação aberto (ACA), utilização da deadline como referência para a transmissão, tipo de algoritmo de escalonamento utilizado (quando existir) e tipo do mecanismo de controlo de acesso ao meio sobre o qual a proposta foi construída. Desta forma, podemos observar que das 19 soluções apresentadas, apenas 7 implementam uma abordagem híbrida. Destas 7 soluções, apenas 4 implementam um algoritmo de escalonamento de tempo-real e utilizam a deadline das mensagens como referência para organizar a transmissão das TS. Por fim, ao analisarmos as soluções que consideram a sua operação num ambiente de comunicação aberto, este número acaba por ser reduzido para apenas uma solução, apresentada por Toscano e Lo Bello [82]. HCCA Baseada em Modelos Baseada em Métricas Abordagem Arquitetura Híbrida Centralizada Distribuída PHCCA RTH W-CBS Toscano e Lo Bello Bazzi et al. Yong et al. PAAC QP-CAT d-EDCA Hiraguri et al. PSQA PRCW Cruz et al. DTXOP WTTP Overboost FHCF Toscano e Lo Bello Outras Características CBR VBR Aperiódica TSPEC Valores do ACA Considera a deadline Round-Robin Round-Robin EDF/SRP EDF EDF Round-Robin Round-Robin Round-Robin Round-Robin EDF Polling Polling Polling DCF/EDCA Polling DCF/EDCA Busy-Tone/EDCA DCF/EDCA EDCA EDCA DCF/EDCA Polling DCF/EDCA EDCA Polling HEMM Polling Polling Escalonador MAC Polling Figura 3.2: Comparação entre as propostas de controlo de admissão apresentadas. Capítulo 3 - Trabalhos Relacionados 61 No entanto, esta solução não satisfaz completamente o critério relacionado com os valores observados num ambiente de comunicação aberto. Isto porque, embora o mecanismo considere que as colisões possam ocorrer com qualquer outra estação, o cálculo utilizado para a definição do bloqueio não considera que as ocupações no meio de comunicação podem ser geradas pelo tráfego proveniente de estações que estão fora da esfera de controlo da arquitetura de tempo-real. Como resultado, o bloqueio real pode ser superior ao bloqueio calculado pelo mecanismo. Torna-se assim evidente a necessidade de avançar com uma nova proposta para o mecanismo de controlo de admissão. Esta, por sua vez, deve ser capaz de considerar interferências provenientes de tráfego transmitido por estações que estão fora da esfera de controlo da arquitetura de tempo-real. Para isto, esta deve ser construída sobre uma abordagem híbrida, que permita atualizar dinamicamente o comportamento do algoritmo de escalonamento de tempo-real com base tanto nas informações enviadas pelas estações via TSPEC, quanto em informações obtidas da rede ou das próprias estações de tempo-real. 3.3 Conclusões Da análise dos mecanismos de controlo de acesso ao meio e controlo de admissão apresentados neste capítulo torna-se evidente a necessidade de uma integração entre ambos para que seja possível propor uma arquitetura de comunicação de tempo-real para redes IEEE 802.11. Um factor fundamental que deve ser considerado no momento da concepção deste tipo de arquitetura é a premissa de que o ambiente de comunicação é aberto, ou seja, pode existir tráfego a ser transmitido a partir de redes que estão fora de esfera de controlo desta arquitetura e que irá interferir com a transmissão do tráfego de tempo-real. Assim, uma nova solução deve ser capaz de operar neste tipo de ambiente, sem que para isto seja necessário controlar as estações que não fazem parte da arquitetura de tempo-real. Neste contexto e, no que diz respeito aos mecanismos de controlo de acesso ao meio, constatouse que a maioria é incapaz de fornecer tal característica. E das soluções que suportam este tipo de operação, apenas algumas têm a sua implementação compatível com hardware COTS. Por outro lado, ao analisarmos esta mesma característica sob a ótica dos mecanismos de controlo de admissão, podemos concluir que a maioria das soluções não leva em conta os efeitos que as estações localizadas fora da esfera de controlo da arquitetura de tempo-real podem gerar para a transmissão do tráfego de tempo-real. Isto resulta no dimensionamento errado dos recursos disponíveis para alocação de recursos e, consequentemente, em decisões (por parte da ACU) que podem comprometer todos os fluxos previamente admitidos. Desta forma, podemos concluir que se torna evidente a necessidade de avançar com uma nova proposta, e que esta se deve focar na integração dos mecanismos de controlo de acesso ao meio com o controlo de admissão, bem como na proposta de novos mecanismos deste tipo, dado que os existentes não são totalmente adequados para o suporte de tráfego de tempo-real. 68 Capítulo 4 - A Arquitetura RT-WiFi TS. Assim, além de evitar que variações no tamanho dos slots resultem em exclusões de TS previamente admitidas, esta abordagem permite também que o teste de escalonabilidade da TS seja executado somente no momento da sua admissão, reduzindo assim o custo computacional desta operação na ACU. Neste contexto, durante a operação da rede a dimensão atual dos slots pode ser inferior ao definido pelo seu respectivo parâmetro Cmax. Esta diferença relativa entre o tamanho máximo e o tamanho atual dos slots é considerado o factor de compressão do sistema. Com o objetivo de otimizar a utilização dos recursos disponíveis na rede de tempo-real, a arquitetura RT-WiFi utiliza este factor de compressão para possibilitar que as estações TR transmitam dois tipos diferentes de tráfego TR (alta ebaixa prioridade) além do tráfego NTR. Num ambiente industrial, isto permite que além das mensagens de tempo-real de alta prioridade, as estações possam também transmitir mensagens de tempo-real de menor prioridade, como por exemplo as mensagens de gestão do software SCADA (Supervisory Control and Data Acquisition). Além disso, a compatibilidade com a transmissão de tráfego NTR permite que as estações RT-WiFi transmitam mensagens de gestão, como por exemplo o beacon (no caso do APTR), requisições e respostas ADDTS e também pedidos de associação e autenticação. A diferença entre os tráfegos TR de alta ebaixa prioridade reside no facto do primeiro receber uma garantia da ACU de que terá uma alocação de slots de acordo com o seu período de geração de mensagens. Por outro lado, esta mesma garantia não é dada ao tráfego TR de baixa prioridade. Este receberá apenas uma alocação de slots se existirem recursos disponíveis no sistema. A definição da disponibilidade de recursos é dada a partir da soma dos recursos disponíveis (ou seja, não alocados por nenhuma TS) e dos recursos disponíveis do factor de compressão (ou seja, a quantidade de recursos que embora sejam reservados ao tráfego TR de alta prioridade, no momento atual, não estão sendo utilizados). Importa referir que, embora o tráfego TR de baixa prioridade não receba uma garantia de alocação de slots por parte da ACU, mantêm-se as configurações do mecanismo FCR e do esquema TDMA. No caso de uma estação RT-WiFi desejar transmitir mensagens pertencentes a uma TS NTR, esta utiliza o mecanismo DCF ou EDCA definido pela norma IEEE 802.11, não havendo assim a necessidade de aprovação prévia pelo mecanismo de controlo de admissão. Caso contrário, a estação utiliza as definições da arquitetura RT-WiFi, sendo obrigatória a aprovação prévia pelo mecanismo de controlo de admissão. Neste contexto, a estação pode alternar entre modos RT-WiFi e DCF/EDCA conforme a necessidade de transmissão de suas TS, sendo que o modo DCF/EDCA será ativado apenas durante os intervalos de tempo em que não existam slots alocados para as TS TR, independentemente da sua prioridade. Como todas as mensagens TR são transmitidas através da fila de voz, é possível que mensagens TR de diferentes prioridades e mensagens NTR estejam misturadas na mesma fila. Neste contexto, cada estação TR implementa um escalonador local que permite distinguir as mensagens TR e NTR alocadas na fila de voz evitando assim inversões de prioridade nas suas transmissões. Esta diferenciação ocorre através do uso de uma lista local contendo todas as TS admitidas pela ACU e também os seus respectivos tipos de tráfego. Ao cruzar as informações desta lista com o parâmetro Capítulo 4 - A Arquitetura RT-WiFi 69 TID (Traffic Identifier) contido no campo QoS Control pertencente ao cabeçalho MAC (Medium Access Control) de cada mensagem, o escalonador da estação consegue identificar qual o tipo de tráfego e, se necessário, modificar o seu posicionamento. Tal como descrito anteriormente, as comunicações da arquitetura RT-WiFi são organizadas em ciclos TDMA (Figura 4.4). O tamanho de cada ciclo é dado pelo parâmetro SI (Service Inteval) que é definido pela ACU com base no período de geração de mensagens das TS admitidas. O início de cada ciclo TDMA é definido pelo envio de uma mensagem de beacon pelo AP. Esta mensagem é utilizada para sincronizar o relógio das estações com o relógio do AP e também difundir uma lista de escalonamento. Esta lista informa as estações acerca do instante inicial (SP - Start Point) e final (EP – End Point) dos slots alocados a cada TS que tem permissão para transmitir no ciclo atual. Cnp CBeacon CBeacon C1C2 SI t SP1EP1/SP2EP2/SP3 EPnp-1/SPnp EP3/SP4 EPnp C2 max C3 Figura 4.4: Ciclo TDMA na arquitetura RT-WiFi. Uma TSisó pode tentar aceder ao meio de comunicação durante o intervalo de tempo compreendido entre SPie EPi(Ci), e para a transmissão de uma única mensagem de dados, independentemente do número de mensagens que possam existir na fila de transmissão. Esta característica simplifica o algoritmo de escalonamento e mantém-se compatível com o modelo de tráfego assumido pela arquitetura RT-WiFi. Para garantir que as estações TR transmitam uma única mensagem por vez, o respectivo parâmetro TXOP (Transmission Oportunity) é definido como 0. Além disso, para evitar transmissões desnecessárias, o escalonador local é também responsável por eliminar mensagens que eventualmente possam ter perdido suas respectivas deadlines e não tenham iniciado uma transmissão. Uma observação importante é que, mesmo com a utilização do mecanismo FCR para aumentar a prioridade no acesso ao meio de uma estação TR (ou APTR), há a possibilidade de existirem colisões subsequentes com outros dispositivos NTR (por exemplo: uma segunda colisão com outra estação NTR). Estas novas colisões são tratadas da mesma maneira que as primeiras. Assim, para que uma estação TR mantenha uma alta prioridade no acesso ao meio mesmo diante de tais colisões, as estações de TR podem efetuar quantas retransmissões forem necessárias até que oslot atribuído à TSitermine ou então que a mensagem de dados seja enviada com sucesso. 70 Capítulo 4 - A Arquitetura RT-WiFi Numa situação normal, a transmissão de qualquer mensagem de TR irá terminar antes do EPi. No entanto, em certas condições (por exemplo, altas cargas da rede) este instante de tempo pode ser excedido. Neste caso específico, a transmissão corrente não é cancelada, mas não serão permitidas novas retransmissões. Esta situação não leva a qualquer conflito com a transmissão que deverá ser efetuada no slot seguinte, uma vez que para este efeito o meio é considerado ocupado, impedindo assim o início de qualquer transmissão. Cada estação TR pode transmitir múltiplas TS com diferentes características. Para cada TS admitida pela ACU é atribuído um índice i(TSi), sendo i∈N*. Desta forma, considera-se um grupo Gcontendo np membros representados por G={TS1,TS2,...,TSnp}, onde TSnp representa ai-ésima TS admitida. Cada estação somente pode iniciar suas transmissões dentro do período de tempo compreendido entre SP e EP. Caso alguma estação não receba a mensagem de beacon, esta não iniciará nenhuma transmissão por considerar que não existem slots alocados para si. Como cada estação TR pode ter uma ou mais TS a transmitir mensagens, a ACU aloca os slots de forma independente para cada TS admitida pelo sistema. Além disso, como a arquitetura RT-WiFi considera a sua operação num ambiente de comunicação aberto, o tamanho de cada slot é definido pela soma dos tempos necessários para que sejam efetuadas as transmissões uplink e downlink e também de um tempo extra para que sejam realizadas retransmissões em casos de falha e para que sejam suportados atrasos no início das transmissões em consequência da ocupação do meio de comunicação por estações NTR. Mesmo com este "superdimensionamento" dos slots, em algumas situações, as transmissões podem iniciar-se dentro dos seus respectivos slots mas serem finalizadas sobre o slot subsequente (Figura 4.5). Esta sobreposição parcial dos slots não interfere no correto funcionamento do mecanismo de controlo de acesso ao meio. Isto porque, como não são permitidas retransmissões após EP e, como o AIFS (Arbitrary Interframe Space) do AP é menor que o das estações de tempo-real (Figura 4.1), uma estação que tenha o seu slot sobreposto irá detetar o meio de comunicação como ocupado e, atrasará o início da sua transmissão evitando assim colisões. t SPiEPi / SPi+1 EPi+1 Slot iSlot i+1 Meio Ocupado Transmissão Slot i Transmissão Slot i+1 Figura 4.5: Sobreposição parcial dos slots. Se por um lado o "superdimensionamento" dos slots auxilia a evitar perdas de deadlines em situações onde a ocupação do meio de comunicação é considerada alta, por outro ele pode ser considerado um overhead caso a ocupação do meio de comunicação seja considerada baixa. Para amortizar esta situação, a ACU ajusta dinamicamente o tamanho de cada slot com base numa Capítulo 4 - A Arquitetura RT-WiFi 71 média ponderada do atraso sofrido pela TS para entregar a sua mensagem com sucesso. Este atraso, contado a partir do SP, é a soma do tempo em que o meio de comunicação manteve-se ocupado mais o tempo gasto por transmissões que resultaram em falha. O mecanismo de gestão do tamanho dos slots é detalhado na secção 4.3.2. O "superdimensionamento" dos slots permite também que estações que estejam fora de esfera de controlo da arquitetura de tempo-real possam efetuar suas transmissões nos "intervalos" não utilizados dos slots. Este "compartilhamento" do meio de comunicação acaba por gerar uma maior equidade (fairness) dos dispositivos da rede TR com dispositivos de outras redes NTR. A lista de escalonamento (SchedList) inserida na mensagem de beacon é criada pelo algoritmo de escalonamento com base nas informações obtidas pela ACU e contém, para cada TSia permissão para transmitir no ciclo corrente, o endereço MAC, o ID da própria estação1e os respectivos limites SP e EP (Figura 4.6). O seu conteúdo pode ser alterado a cada ciclo TDMA, garantindo assim uma elevada flexibilidade à arquitetura RT-WiFi. Lista de Escalonamento SP EP 2 3 2 1 3 0.000150 0.000250 0.000400 0.000600 0.000700 0.000250 0.000400 0.000600 0.000700 0.000850 Addr_STA TSID 00 : 1b : b1 : 4c : ec : 23 00 : 24 : 54 : ce : c6 : b9 58 : 98 : 35 : 7c : 75 : 3b 00 : 1b : b1 : 4c : ec : 23 08 : 76 : ff : 99 : d0 : 56 Figura 4.6: Exemplo de uma lista de escalonamento enviada na mensagem de beacon. Assim, ao receber uma mensagem de beacon, cada estação inicialmente sincroniza seu relógio local com o relógio do APTR e então realiza uma busca na SchedList (utilizando o seu endereço MAC como índice) para obter os valores de SPieEPireferentes às suas TS. Seguidamente, a estação agenda interrupções com os valores recebidos para sinalizar início e fim de cada slot. Uma vez que antes de agendar novas interrupções os relógios foram sincronizados, os valores definidos nas variáveis SPieEPisão descritos em termos absolutos, ou seja, os mesmos do APTR. Caso alguma estação não receba a mensagem de beacon, esta não aloca nenhum slot, passando assim um ciclo TDMA sem transmitir. Caso a estação receba a mensagem de beacon mas não tenha nenhum slot alocado para o ciclo corrente, realiza mesmo assim a sincronização do relógio. 1O ID local (na estação) de uma TS admitida pode ser diferente do ID atribuído pela ACU. Neste contexto, a nível das estações, as identificações são realizadas sempre pelo tuplo [endereço MAC / ID local]. 72 Capítulo 4 - A Arquitetura RT-WiFi O algoritmo 1 formaliza a função SENDBEACON, invocada pela ACU quando a interrupção periódica que agenda o envio das mensagens de beacon é executada. Inicialmente a ACU verifica se entre as TS previamente admitidas, alguma se encontra num estado de "falha". Em caso afirmativos, remove-as da lista de admissão (linha 2). Seguidamente, a ACU calcula os atrasos sofridos pelos fluxos uplink edownlink de cada TS (linha 3). Estes atrasos são utilizados como base para a redefinição do tamanho do slot que será alocado à cada TS (linha 4). Após atualizar o tamanho dos slots, a ACU atribui à variável SchedList a nova lista de escalonamento para o ciclo corrente (linha 5) e insere-a na mensagem de beacon (linha 6). As funções descritas entre as linhas 2 e 5 são específicas do controlo de admissão e serão detalhadas na secção 4.3. Por fim, a ACU agenda (no APT R) as interrupções de início e fim do slot para cada TS da SchedList (linhas 8 e 9) e envia a mensagem de beacon (linha 11). O objetivo das interrupções é sinalizar à ACU os limites dos slots atribuídos à cada TS no ciclo corrente, de forma a permitir que esta possa estimar os atrasos nos fluxos de dados. Algoritmo 1 Envio da mensagem de beacon pelo APTR 1: function SENDBEACON() 2: CHECKIDLEFLOWS() 3: COMPUTEDELAY() 4: REDEFINESLOTLENGTH() 5: SchedList ←GETSCHEDLIST() 6: BEACON.SCHEDLIST ←SchedList 7: for (i=0→SchedList.SIZE - 1) do 8: SETINTRPTSP[SchedList[i].TSID]=SchedList[i].SP 9: SETINTRPTEP[SchedList[i].TSID]=SchedList[i].EP 10: end for 11: SEND.BEACON 12: end function Por outro lado, o algoritmo 2 formaliza os procedimentos realizados quando a mensagem de beacon é recebida por uma estação TR. Inicialmente, a estação verifica se a mensagem de beacon é proveniente do APT R (linha 2). Em caso afirmativo, então esta bloqueia a transmissão de novas mensagens (linha 3) e cancela qualquer interrupção agendada que possa ainda não ter sido executada (linha 4). Algoritmo 2 Receção da mensagem de beacon pela estação de tempo-real 1: if (RXMSG == BEACON)then 2: if (BEACON.BSSID == StationBSSID)then 3: RightToSend ←FALSE 4: CANCELALLINTRPT() 5: SYNC(BEACON.TSF) 6: SEARCHTSID(BEACON.SCHEDLIST) 7: end if 8: end if Por fim, a estação realiza a sincronização dos relógios (linha 5) e invoca a função SEARCHTSID passando como parâmetro a lista de escalonamento recebida na mensagem de beacon (linha Capítulo 4 - A Arquitetura RT-WiFi 73 6). Esta função têm como objetivo pesquisar na SchedList entradas para as TS previamente submetidas pela estação e aprovadas pela ACU e, caso encontradas, agendar suas respectivas interrupções SP e EP. A função SEARCHTSID é formalizada pelo algoritmo 3, e recebe como parâmetro de entrada a lista de escalonamento enviada pela mensagem de beacon. Esta função realiza uma pesquisa na lista de escalonamento até encontrar uma entrada correspondente ao endereço MAC da estação (linha 3). Seguidamente agenda as interrupções SP e EP para a TS em questão (linhas 4 e 5). Algoritmo 3 Função SEARCHTSID() 1: function SEARCHTSID(SchedList) 2: for (i=0→SchedList.SIZE - 1) do 3: if (SchedList[i].Addr_STA == LocalAddr)then 4: SETINTRPTSP[SchedList[i].TSID]←SchedList[i].SP 5: SETINTRPTEP[SchedList[i].TSID]←SchedList[i].EP 6: end if 7: end for 8: end function Por fim, o algoritmo 4 formaliza os procedimentos executados pela estação quando a interrupção SPié executada. Neste caso, o parâmetro TSID é utilizado para identificar qual TS deve iniciar a transmissão (linha 1). Assim, inicialmente a estação atualiza a variável RightToSend (linha 3) para permitir que sejam efetuadas repetidas tentativas de transmissão de uma única mensagem da TSi(linha 4) até que uma das três seguintes situações ocorra (linha 4): i) a estação receba a mensagem de ACK, ii) a interrupção do final do slot (EPi) seja executada, iii) a variável RightToSend seja atualizada para False. Algoritmo 4 Interrupção SPi 1: if (EXEC.INTRPTSP[TSID]) then 2: repeat 3: RightToSend ←TRUE 4: SEND.DATAMESSAGE(TSID, 1) 5: until (RECEIPT.ACK[TSID] or EXEC.INTRPTEP[TSID] or !RightToSend) 6: end if 4.3 Mecanismo de Controlo de Admissão Para evitar que haja uma sobrecarga de tráfego TR, e consequentemente a sua degradação, a arquitetura RT-WiFi implementa um Mecanismo de Controlo de Admissão que obriga as estações que queiram transmitir mensagens de TR a solicitarem previamente à ACU a admissão de uma TS. Esta TS identifica um fluxo de dados específico entre uma estação origem e uma estação destino, ou seja, na arquitetura RT-WiFi uma TS é composta pelos fluxos de dados uplink edownlink das estações comunicantes. Para realizar o pedido de admissão de uma nova TSk, a estação deve enviar os respectivos requisitos temporais e características específicas. Com base nestas informações, a ACU efetua 74 Capítulo 4 - A Arquitetura RT-WiFi o teste de escalonabilidade do grupo Gpreviamente admitido juntamente com a TSk. Este teste (detalhado na secção 4.3.1) é dado pelo algoritmo de escalonamento em utilização, e seu resultado irá definir entre a admissão (ou não) da TSk. O pedido de admissão da TSké realizado através do envio de uma requisição ADDTS (Add Traffic Stream) ao APTR contendo as seguintes informações TSPEC: • período de geração das mensagens (Pk); • tamanho (Lk) da MPDU (MAC Protocol Data Unit); • intervalo de inatividade (IIk); • tipo de requisição (CTk); • tempo extra de alocação (SurplusTimek). A arquitetura RT-WiFi implementa três tipos de requisições que podem ser efetuadas pelas estações para a transmissão de tráfegos de TR de alta ou baixa prioridades: •Alta: solicita a alocação de recursos para a transmissão de tráfegos de alta prioridade; •Alta/Baixa: solicita a alocação de recursos para a transmissão de tráfegos de alta prioridade. No entanto, caso não seja possível alocar tais recursos nesta categoria, solicita então a alocação de recursos como sendo para a transmissão de tráfegos de baixa prioridade; •Baixa: solicita a alocação de recursos para a transmissão de tráfegos de baixa prioridade; O tempo extra de alocação (definido pelo parâmetro SurplusTimek) solicitado pela estação refere-se ao tempo adicional (além do necessário para a transmissão com sucesso de uma única mensagem de dados) que é solicitado à ACU alocar para a TSk. Para simplificar os cálculos, este valor é baseado no número de retransmissão que cada fluxo de dados (uplink edownlink) pode efetuar caso não ocorram atrasos no acesso ao meio. Desta forma, o valor de SurplusTimeké dado pela seguinte equação: SurplusTimek= (Cuplink attempt ×RNuplink k)+(Cdownlink attempt ×RNdownlink k)(4.3) onde RNuplink ke RNdownlink krepresentam o número de retransmissões utilizada pela TSkcomo base de cálculo para cada fluxo de dados, respectivamente2. Os parâmetros Cuplink attempt e Cdownlink attempt são os tempos necessários para efetuar as transmissões com sucesso de uma única mensagem de dados nos fluxos uplink edownlink, respectivamente. Os respectivos valores são dados pelas seguintes equações: Cuplink attempt =AIFSQSTA VO +CDATA[Lk]+SIFS +CACK (4.4) 2Os parâmetros RNuplink e RNdownlink podem ser configurados pelo utilizador. Capítulo 4 - A Arquitetura RT-WiFi 75 Cdownlink attempt =AIFSQAP VO +CDATA[Lk]+SIFS +CACK (4.5) onde AIFSQSTA VO é o AIFS da categoria de voz na estação TR, AIFSQAP VO é o AIFS da categoria de voz no APTR, CDATA é o tempo necessário para se realizar a transmissão de uma única mensagem de dados com MPDU de tamanho Lke CACK é o tempo necessário para se realizar a transmissão da mensagem de ACK. Todos estes tempos são baseados nos valores definidos pela camada física. Neste contexto, o envio da requisição ADDTS é formalizado pelo algoritmo 5. Esta função recebe como parâmetros o endereço MAC da estação TR (Addr_STA), o id da TSk(TSID), o período de geração das mensagens (Pk), o tamanho do MPDU (Lk), o intervalo de inatividade (IIk) e o tipo de requisição (CTk), sendo os cinco primeiros enviados pelo TSPEC e o último pelo elemento TCLAS (Traffic Classification), ambos definidos na norma IEEE 802.11. Algoritmo 5 Envio da requisição ADDTS ao APTR. 1: function SEND_ADDTSREQUEST(Addr_STA, TSID, Pk, Lk, IIk, CTk) 2: Cuplink attempt = AIFSQSTA VO + CDATA[Lk] + SIFS + CACK 3: Cdonwlink attempt = AIFSQAP VO + CDATA[Lk] + SIFS + CACK 4: SurplusTimek= (Cuplink attempt ×RNuplink k)+(Cdownlink attempt ×RNdownlink k) 5: SENDMSG.ADDTSRequest[Addr_STA, TSID, Pk, Lk, IIk, CTk, SurplusTimek] 6: while (!TIMEOUT.ADDTSRequest) do 7: if (RECEIPT.ADDTSResponse) then 8: if (ADDTSResponse.STATUS = Accepted) then 9: INSERT.AdmittedList(TSID, ADDTSResponse.CT) 10: else 11: DELTS(TSID) 12: end if 13: EXIT() 14: end if 15: end while 16: end function Inicialmente a estação calcula o tempo necessário para a transmissão de uma mensagem de dados com sucesso para ambos os fluxos de dados (uplink edownlink) (linhas 2 e 3, respectivamente) e calcula também o valor da variável SurplusTime (linha 4). Seguidamente, a estação insere a variável SurplusTime juntamente com os restantes parâmetros recebidos pela função na requisição ADDTS, a qual é então enviada ao APTR (linha 5). Quando recebe a mensagem de resposta ADDTS, a estação verifica se a sua solicitação foi aceite ou não (linha 8). Em caso afirmativo, a estação insere a TS na sua lista de admissão utilizando o tipo de classificação definida pela ACU na mensagem de resposta ADDTS (linha 9), caso contrário a TS é eliminada (linha 11). Ao receber a requisição ADDTS da TSk, a ACU calcula o tempo necessário para a transmissão de uma única mensagem de dados de tamanho Lknos fluxos uplink (equação 4.4) e downlink (equação 4.5). Seguidamente, a ACU define um tempo de atraso (Inter fk) que a estação pode sofrer antes de efetivamente iniciar suas tentativas de acesso ao meio de comunicação. Este atraso pode ser resultande ou da ocupação do meio de comunicação por estações que se encontram fora 76 Capítulo 4 - A Arquitetura RT-WiFi da esfera de controlo da arquitetura RT-WiFi, ou pela sobreposição parcial de slots3. O valor do parâmetro Inter f é dado pela seguinte equação: Inter fk=CDATA[MPDUmax]+SIFS +CACK (4.6) onde CDATA[MPDUmax]é o tempo necessário para a transmissão de uma mensagem contendo um MPDU de tamanho máximo4. Uma vez que a ACU pode modificar dinamicamente o tamanho dos slots alocados para a TSk (procedimento detalhado na secção 4.3.2), para evitar o seu crescimento excessivo, esta define um tamanho máximo que os slots podem atingir (Cmax k), que é dado pela seguinte equação: Cmax k= (2×Inter fk)+Cuplink attempt +Cdownlink attempt +SurplusTimek(4.7) onde o valor de Inter f é multiplicado por 2 para considerar as interferências que ambos os fluxos de dados uplink edownlink possam sofrer. O algoritmo 6 formaliza o processamento de uma requisição ADDTS recebida pela ACU. Esta função recebe como parâmetros de entrada os valores TSPEC enviados pela estação para a admissão de uma TSk. Inicialmente a ACU calcula o tempo necessário para a transmissão de uma mensagem de dados (com sucesso) para ambos os fluxos de dados uplink edownlink (linhas 2 e 3, respectivamente) e também o valor da variável Interfk(linha 4). Seguidamente, a ACU calcula o tamanho máximo do slot (linha 5) e invoca a função SCHEDTEST para realizar o teste de escalonabilidade (linha 6). Caso os parâmetros inseridos no teste sejam escalonáveis (linha 7), então a ACU define como tamanho atual do slot (Ccurrent k) o tamanho utilizado no teste de escalonabilidade (linha 8) e atualiza a variável CTkpara qual a prioridade a TSkfoi admitida (linha 9). Se esta foi admitida como sendo de alta prioridade (linha 10), então a ACU agenda interrupções subsequentes com um intervalo de tempo defindo pela variável Pkpara a sua inserção na "lista de pronto" de TS de alta prioridade (linha 11). Caso contrário, agenda interrupções subsequentes com um intervalo de tempo defindo pela variável Pkpara a sua inserção na "lista de pronto" de TS de baixa prioridade (linha 13). Uma vez definida a respectiva prioridade, a ACU insere a TSke seus respectivos parâmetros numa lista de TS admitidas (linha 15) e envia uma mensagem de resposta ADDTS à estação contendo a informação acerca da admissão e para qual prioridade esta foi admitida (linha 16). Caso o resultado do teste de escalonabilidade seja negativo, então a ACU envia uma mensagem de resposta ADDTS informando a estação acerca da impossibilidade de admissão da TSk(linha 18). Uma vez admitida, a remoção de uma TS (seja na ACU ou na estação) pode ocorrer em duas situações: i) por solicitação da própria estação, ii) por imposição da ACU. Em ambos os casos a função DELTS é invocada. 3A sobreposição parcial de slots ocorre quando a TSide uma estação inicia a sua transmissão instantes antes do final do seu slot (EPi) e esta é prolongada até uma parte inicial do slot da TSi+1. 4O tamanho máximo de um MPDU definido pela norma IEEE 802.11 é de 2304 bytes. Capítulo 4 - A Arquitetura RT-WiFi 77 Algoritmo 6 Processamento da requisição ADDTS pela ACU. 1: function PROCESS_ADDTSREQUEST(Addr_STA, TSID, Pk, Lk, IIk, CTk, SurplusTimek) 2: Cuplink attempt ←AIFSQSTA VO + CDATA[Lk] + SIFS + CACK 3: Cdownlink attempt ←AIFSQAP VO + CDATA[Lk] + SIFS + CACK 4: Interfk←CDATA[MSDUmax] + SIFS + CACK 5: Cmax k←(2 ×Interfk)+Cuplink attempt + Cdownlink attempt +SurplusTimek 6: SCHEDTEST(Cmax k,Pk,CTk) 7: if (SCHEDTEST.STATUS == SCHEDULABLE)then 8: Ccurrent k←Cmax k 9: CTk←SCHEDTEST.CT 10: if (CTk== HIGH)then 11: SETINTRPTLOOPINSERTREADYLIST(ReadyListHigh,Pk) 12: else 13: SETINTRPTLOOPINSERTREADYLIST(ReadyListLow,Pk) 14: end if 15: AdmittedList.INSERT(Addr_STA, TSID, Pk, IIk, CTk,Ccurrent k,Cmax k, Cuplink attempt , Cdownlink attempt ) 16: SENDMSG.ADDTSResponse[Accepted, CTk] 17: else 18: SENDMSG.ADDTSResponse[Denied, NULL] 19: end if 20: end function No primeiro caso, a estação invoca a função DELTS localmente (removendo a TS da sua lista local) e envia uma requisição DELTS ao APTR que, ao receber esta mensagem, invoca também a função DELTS (removendo a TS da lista de admissão da ACU). No segundo caso, inverte-se a situação, a ACU invoca a função DELTS localmente (removendo a TS da lista de admissão da ACU) e envia uma requisição DELTS à estação da TS impondo a sua remoção. Esta, por sua vez, invoca a função DELTS para remover a TS da sua lista local. A função DELTS (formalizada pelo algoritmo 7) recebe como parâmetro de entrada o identificador local da TS (TSID). Com base neste valor é feita uma pesquisa na lista de TS admitidas (linha 2) até que seja encontrada a entrada correspondente (linha 3) e então é removida a entrada para a TS (linha 4). Algoritmo 7 Função DELTS() 1: function DELTS(TSID) 2: for (i=0→AdmittedList.SIZE - 1) do 3: if (AdmittedList[i].TSID == TSID) then 4: AdmittedList[i].REMOVE 5: end if 6: end for 7: end function 4.3.1 Teste de Escalonabilidade A arquitetura RT-WiFi foi implementada de forma a possibilitar a utilização de diferentes algoritmos de escalonamento sem a necessidade de uma reestruturação completa. Assim, é apenas 84 Capítulo 4 - A Arquitetura RT-WiFi Meio Ocupado . . . SPi 1a tentativa (sem sucesso) n-ésima tentativa (com sucesso) Ci Tempo de Atraso Uplink Cattempt uplink . . . ACKSIFSDadosIFS ACKSIFSDadosIFS TACK Sent Figura 4.7: Tempo de atraso uplink (buplink i). Neste contexto, o valor de buplink ié dado pela seguinte equação: buplink i=TSent ACK −SPi−Cuplink attempt (4.11) onde TSent ACK é o instante de tempo onde a mensagem de ACK é enviada pelo APT R à estação origem, SPié o instante de tempo descrito como o início do slot atribuído à TSie Cuplink attempt o tempo necessário para se realizar a transmissão de uma mensagem de dados (com sucesso) da estação origem ao APTR. A topologia infraestruturada permite também que o tempo bdownlink ide uma TSipossa ser calculado pela ACU com base no tempo necessário para que o APTR reencaminhe (com sucesso) a mensagem recebida à estação destino. Este tempo inicia-se logo após o envio da mensagem de ACK para a estação origem e termina no início de uma transmissão com sucesso para a estação destino (Figura 4.8). É importante referir que, embora a transmissão do fluxo de dados downlink seja procedida logo após a recepção da mensagem pelo APTR, a sua transmissão para a estação destino pode sofrer atrasos devido a estações ocultas (hidden-nodes), ou seja, estações que estão fora da área de cobertura da estação origem. . . . 1a. tentativa (sem sucesso) Tempo de Atraso Downlink Meio Ocupado . . . n-ésiama tentativa (com sucesso) Cattempt downlink . . . IFS Dados SIFS ACK IFS Dados SIFS ACK TACK Received TForward Begin Figura 4.8: Tempo de atraso downlink (bdownlink i). Capítulo 4 - A Arquitetura RT-WiFi 85 Neste caso, o valor de bdownlink ié dado pela seguinte equação: bdownlink i=TReceived ACK −TBegin Forward −Cdownlink attempt (4.12) onde TReceived ACK é o instante de tempo onde a mensagem de ACK da estação destino é recebida pelo APTR, TBegin Forward é o instante de tempo onde o APTR inicia o reencaminhamento da mensagem para a estação destino (ou seja, logo após o envio da mensagem de ACK à estação origem) e Cdownlink attempt o tempo necessário para se realizar a transmissão de uma única mensagem de dados do APTR à estação destino. O algoritmo 12 formaliza a função MEASUREDELAY, que é invocada pela ACU quando a interrupção agendada no instante SPide cada slot é activada. Esta função recebe como parâmetro de entrada o identificador da TS que deve monitorizar (TSID) e tem como objetivo estimar os atrasos sofridos em ambos os fluxos de dados. Algoritmo 12 Interrupção de avaliação dos atrasos de uplink/downlink 1: function MEASUREDELAY(TSID) 2: repeat 3: if (SENT.ACK[TSID]) then 4: buplink ←TSent ACK - TSP -AdmittedList[TSID].Cuplink attempt 5: AdmittedList[TSID].MsgUpRcvd ←TRUE 6: AdmittedList[TSID].IdleTime ←0 7: EXIT() 8: end if 9: until (INTRPTEP[TSID]) 10: if (!AdmittedList[TSID].MsgUpRcvd) then 11: buplink ←AdmittedList[TSID].Ccurrent 12: INC(AdmittedList[TSID].IdleTime) 13: else 14: repeat 15: if (RECEIPT.ACK.MSGDEST[TSID]) then 16: bdownlink ←TReceipt ACK - TBegin Forward -AdmittedList[TSID].Cdownlink attempt 17: AdmittedList[TSID].MsgDownSent ←TRUE 18: EXIT() 19: end if 20: until (INTRPTEP[TSID]) 21: if (!AdmittedList[TSID].MsgDownSent) then 22: bdownlink ←AdmittedList[TSID].Ccurrent - (buplink +AdmittedList[TSID].Cuplink attempt ) 23: end if 24: end if 25: COMPUTEDELAY(TSID,buplink,bdownlink) 26: end function Após o início da interrupção SPi, a ACU monitoriza a sua fila de transmissão até ao envio da mensagem de ACK para a estação da TSID em questão, ou até a execução da interrupção EPi. Caso a mensagem de ACK seja enviada (linha 3), então a ACU calcula o atraso sofrido pela estação para o envio do tráfego uplink (linha 4) e atualiza duas variáveis contidas na lista de TS admitidas pelo sistema (linhas 5 e 6). A primeira variável (MsgUpRcvd), indica ao sistema que o fluxo uplink foi recebido com sucesso (linha 5) enquanto que a segunda (IdleTime) reinicializa o contador que 86 Capítulo 4 - A Arquitetura RT-WiFi controla o tempo máximo ao qual uma TS pode ficar sem transmitir (linha 6). Este contador será utilizado posteriormente para controlar a exclusão das TS que se encontrem num estado de "falha" (detalhado na seção 4.3.3). Caso a mensagem do fluxo uplink não tenha sido recebida com sucesso, significa que a interrupção EPifoi executada e que as variáveis previamente referidas não foram atualizadas (linha 10). Neste caso a ACU define como atraso do fluxo uplink o tamanho atual do seu slot (linha 11) e incrementa o valor da variável IdleTime (linha 12). Caso a mensagem do fluxo uplink tenha sido recebida corretamente, então a ACU inicia a monitorização da sua fila de receção até receber a mensagem de ACK da estação destino ou, até à execução da interrupção EPi. Caso a mensagem de ACK seja recebida (linha 15), é calculado o atraso sofrido pelo fluxo de dados downlink (linha 16) e atualizada a variável MsgDownSent (linha 17). A variável MsgDownSent tem por objetivo sinalizar o encaminhamento com sucesso da mensagem para a estação destino. Caso constate-se que esta não tenha sido atualizada (linha 21), significa então que a mensagem não foi reencaminhada com sucesso. Neste caso, a ACU calcula o atraso sofrido pelo fluxo downlink (linha 22) como sendo o tamanho atual do slot menos o tempo utilizado pelo fluxo de dados uplink (inclusive pelo seu atraso). Por fim, a ACU invoca a função COMPUTEDELAY() passando como parâmetros de entrada o identificador da TS e os atrasos uplink edownlink previamente medidos. Esta função tem como objetivo suavizar o impacto que variações repentinas possam gerar sobre a redefinição do tamanho do slot. Neste contexto, é utilizada uma janela deslizante baseada numa média exponencial ponderada. Sendo assim, os valores de atraso previamente medidos (buplink ie bdownlink i) são utilizados como base para gerar valores aproximados dos tempos de atraso uplink (Buplink i) e downlink (Bdownlink i) que, posteriormente serão utilizados como base na redefinição do tamanho do slot. Os valores de Buplink ie Bdownlink isão dados pelas seguintes equações, respectivamente: Buplink i= (1−α)×Buplink i+α×buplink i(4.13) Bdownlink i= (1−α)×Bdownlink i+α×bdownlink i(4.14) onde αé o fator de suavização e varia de [0...1]. O valor de αutilizado pela arquitetura RT-WiFi é o mesmo sugerido por Jacobson em [85] e utilizado pela RFC 6298 [86], ou seja, α=0.125. Neste contexto, a função COMPUTEDELAY() é formalizada no algoritmo 13 a qual atualiza os valores de Buplink ie Bdownlink ipara uma dada TSID. Algoritmo 13 Função ComputeDelay() 1: function COMPUTEDELAY(TSID, buplink, bdownlink) 2: AdmittedList[TSID].Buplink ←((1 - α)×AdmittedList[TSID].Buplink)+(α×buplink) 3: AdmittedList[TSID].Bdownlink ←((1 - α)×AdmittedList[TSID].Bdownlink)+(α×bdownlink) 4: end function Uma vez que os atrasos dos fluxos de dados uplink edownlink são calculados durante a execução do ciclo TDMA, a redefinição do tamanho dos slots ocorre posteriormente, isto é, momentos antes da criação de uma nova mensagem de beacon (a qual conterá os novos valores) através da Capítulo 4 - A Arquitetura RT-WiFi 87 função REDEFINESLOTLENGTH. O tamanho atual do slot de uma TSi(Ccurrent i) é redefinido utilizando a seguinte equação: Ccurrent i=min[(Buplink i+Cuplink attempt +Bdownlink i+Cdownlink attempt ),Cmax i](4.15) onde Cmax ié o tamanho máximo que o slot pode alcançar. A função REDEFINESLOTLENGTH é formalizada no algoritmo 14, a qual atualiza o tamanho dos slots de todas as TS contidas na lista de admissão da ACU. Para cada entrada na lista (linha 2) a ACU inicializa algumas variáveis auxiliares (linhas 3 – 7) e, com base nestas variáveis, é calculado o novo tamanho do slot (linha 8), que tem um limite superior defindo por Cmax. Algoritmo 14 Função RedefineSlotLength() 1: function REDEFINESLOTLENGTH() 2: for (i=0→AdmittedList.SIZE - 1) do 3: Cuplink attempt ←AdmittedList[i].Cuplink attempt 4: Cdownlink attempt ←AdmittedList[i].Cdownlink attempt 5: Buplink ←AdmittedList[i].Buplink 6: Bdownlink ←AdmittedList[i].Bdownlink 7: Cmax ←AdmittedList[i].Cmax 8: Ccurrent ←min[(Buplink +Cuplink attempt +Bdownlink +Cdownlink attempt ), Cmax] 9: end for 10: end function É importante referir que os valores de Buplink ieBdownlink isão calculados no ciclo TDMA anterior, diferentemente dos valores de buplink iebdownlink i, que são calculados no ciclo TDMA corrente. Assim, quando o sistema é inicializado ou quando uma nova TS é admitida, ambos os valores de Buplink ieBdownlink iainda não estão definidos. No entanto, isto não reflete um problema uma vez que ao enviar a requisição ao APTR as estações definem previamente um valor extra que deve ser alocado para retransmissões (parâmetro SurplusTime). 4.3.3 Verificação de Falhas das TS Numa situação normal, ao excluir uma TS a ACU liberta os recursos a ela alocados, independentemente deste processo ter sido iniciado pela estação ou pela própria ACU. No entanto, quando ocorre uma "falha" numa TS ou então na estação que a detém (por exemplo, desligamento inesperado da estação), estes recursos podem ficar bloqueados caso não exista um mecanismo capaz de identificá-las. Desta forma, a ACU considera que uma TSientrou num estado de "falha" quando esta para de efetuar transmissões por um período de tempo maior que o estipulado pelo parâmetro de intervalo de inatividade (IIi) enviado por ela (via TSPEC) no momento da sua admissão. Assim, após identificá-la a ACU pode excluí-la para libertar os recursos a ela alocados. Para realizar esta verificação, a ACU insere na lista de admissão uma variável (IdleTime) que define o tempo máximo que uma TSipode permanecer sem efetuar qualquer transmissão. Cada vez que a ACU identificar a receção de uma mensagem de dados (independentemente de 88 Capítulo 4 - A Arquitetura RT-WiFi esta ser recebida com sucesso ou não) proveniente da TSie com destino ao APT R dentro do seu respectivo slot, então a variável IdleTime é reinicializa (IdleTime =0). Caso contrário, o seu valor é incrementado com base no período de geração de mensagens (Pi) estipulado pela TSino momento da admissão. Assim, antes de criar uma nova mensagem de beacon, a ACU invoca a função CHECKIDLEFLOWS (formalizada no algoritmo 15) que tem como objetivo verificar se alguma TS previamente admitida pela ACU encontra-se num estado de "falha". Neste contexto, é executada uma verificação para cada TS contida na sua lista de admissão (linha 2). Se alguma destas TS tiverem o valor da sua variável IdleTime maior ou igual ao definido pelo parâmetro II (linha 3) então é invocada a função DELTS (linha 4), a qual irá remover a TS da sua lista de admissão, liberar os recursos por ela alocados e enviar uma mensagem DELTS à estação origem. Algoritmo 15 Função CheckIdleFlows() 1: function CHECKIDLEFLOWS() 2: for (i=0→AdmittedList.SIZE - 1) do 3: if (AdmittedList[i].IdleTime ≥AdmittedList[i].II) then 4: DELTS[AdmittedList[i].TSID] 5: end if 6: end for 7: end function 4.4 Suporte de Tráfego Broadcast Tal como discutido na secção 4.1, inicialmente foi utilizado como base para a construção da arquitetura RT-WiFi o suporte a aplicações baseadas num modelo de comunicação peer-to-peer. Assim, assumindo os conceitos apresentados anteriormente, o objetivo desta secção é apresentar as alterações necessárias para que a arquitetura RT-WiFi possa suportar aplicações que utilizem um modelo de comunicação baseado em broadcast. Neste contexto, é importante lembrar que numa rede IEEE 802.11 infraestruturada, o envio de uma mensagem em broadcast ocorre somente no fluxo de dados downlink, sendo a comunicação no fluxo de dados uplink efetuada através de uma transmissão unicast (ou seja, com confirmação). Assim, se por um lado a utilização do modelo de comunicação baseado em broadcast torna as comunicações menos confiáveis, uma vez que não é utilizada a mensagem de confirmação (ACK), por outro lado esta abordagem reduz o tempo necessário para que sejam efetuadas as transmissões e, no âmbito da arquitetura RT-WiFi, consequentemente o tamanho dos slots. Neste contexto, são necessárias três modificações para que a arquitetura RT-WiFi possa suportar aplicações que utilizem este modelo de comunicação. A primeira é a maneira como o parâmetro SurplusTimek(Equação 4.3) é definido pelas estações de tempo-real. Este parâmetro, enviado para a ACU com o objetivo de definir o tempo extra de alocação de uma TSk, passa a ser Capítulo 4 - A Arquitetura RT-WiFi 89 calculado levando em consideração somente o número de retransmissões que podem ser efetuadas no fluxo de dados uplink, uma vez que não são efetuadas retransmissões no fluxo de dados downlink. Portanto, o parâmetro SurplusTimekpassa a ser definido pela seguinte equação: SurplusTimek= (Cuplink attempt ×RNuplink k)+Cdownlink attempt (4.16) onde Cuplink attempt e Cdownlink attempt são, respectivamente, os tempos necessários para efetuar as transmissões com sucesso de uma única mensagem de dados nos fluxos de dados uplink edownlink e RNuplink ké o número de retransmissões utilizada pela TSkcomo base de cálculo para o fluxo de dados uplink. A segunda modificação ocorre no cálculo do tempo de transmissão do fluxo de dados downlink (Equação 4.5). Neste caso, como esta transmissão é efetuada em broadcast, são removidos da equação os tempos referentes a receção da mensagem de confirmação. Assim, o novo valor é dado pela seguinte equação: Cdownlink attempt =AIFSQAP VO +CDATA[Lk](4.17) A última modificação é a maneira como o atraso no fluxo de dados downlink (bdownlink i) é calculado para cada TSi(Equação 4.12). Como neste caso em específico não é transmitida uma mensagem de confirmação, o novo atraso deve ser medido entre o início do reencaminhamento da mensagem pelo APTR (dado pelo instante de tempo TBegin Forward) e o final da sua respectiva transmissão (dado pelo instante de tempo TSent DATA). A Figura 4.9 apresenta como é medido o tempo de atraso downlink para transmissões em broadcast. . . . fluxo uplink (com sucesso) Tempo de Atraso Downlink Cattempt uplink IFS Dados SIFS ACK . . . transmissão broadcast Meio Ocupado IFS Dados TForward Begin Cattempt downlink TDATA Sent Figura 4.9: Tempo de atraso downlink (bdownlink i) para transmissão em broadcast. Neste contexto, o valor de bdownlink ipassa a ser dado pela seguinte equação: bdownlink i=TSent DATA −TBegin Forward −Cdownlink attempt (4.18) Uma vez que o método original de análise dos tempos de atraso downlink no APTR muda em função da transmissão de tráfego broadcast, faz-se necessária a indicação deste tipo de tráfego no momento da submissão de uma nova TS a ACU. Esta diferenciação é realizada através do campo 90 Capítulo 4 - A Arquitetura RT-WiFi de destino contido no elemento TCLAS enviado juntamente com a requisição ADDTS. Desta forma, como este elemento é naturalmente enviado neste tipo de requisição para identificar a TS, nenhuma alteração adicional precisa ser realizada. É importante observar que embora a transmissão de tráfego broadcast seja realizada de forma diferente ao originalmente proposto, a operação destes dois modos não é mutuamente exclusiva, ou seja, é perfeitamente possível que numa mesma rede RT-WiFi podem existir algumas TS a transmitir tráfego broadcast e outras a transmitir tráfego unicast (peer-to-peer). 4.5 Conclusões Neste capítulo foi apresentada a arquitetura de comunicação RT-WiFi, a qual tem como objetivo suportar a transmissão de tráfego soft real-time em ambientes de comunicação abertos, ou seja, partilhando o meio de comunicação com estações que estão fora da sua esfera de controlo. Uma das suas principais características é a capacidade de fornecer um serviço de comunicação de tempo-real controlando apenas as estações TR, sem a necessidade de uma atualização de todos os dispositivos de comunicação que estejam a operar na mesma área de cobertura e canal de comunicação. Esta característica por si só já demonstra uma vantagem quando comparada com as propostas apresentadas no capítulo anterior. Outra vantagem é a utilização de um mecanismo de controlo de acesso ao meio baseado num esquema TDMA. Esta abordagem possibilita uma redução no overhead das comunicações (quando comparado com os mecanismos de polling tradicionais) e impede colisões entre transmissões de tempo-real. Como cada ciclo TDMA se inicia com a transmissão de uma mensagem de beacon, que contém uma lista de escalonamento, além de garantir uma sincronização frequente dos relógios das estações, possibilita também uma elevada flexibilidade ao algoritmo de escalonamento, uma vez que a cada ciclo TDMA a ordem de alocação dos slots pode ser alterada em função das necessidades existentes. Esta flexibilidade é estendida à capacidade que a arquitetura tem de ajustar dinamicamente o tamanho de cada slot alocado pela ACU. Este ajuste é realizado tendo como base os atrasos que os fluxos de dados uplink edownlink sofrem para transmitirem as respectivas mensagens. Tais atrasos levam em consideração tanto o atraso no acesso ao meio (devido à ocupação do canal de comunicação por outra estação) quanto o tempo gasto em retransmissões (sejam estas resultantes de colisões ou de erros de transmissão causados por ruídos no canal de comunicação). Neste contexto, para evitar que seja necessário executar um novo teste de escalonabilidade cada vez que é realizada uma alteração no tamanho dos slots, no momento da admissão de uma TSka ACU define o tamanho máximo que os slots alocados para esta TS podem atingir. Assim, independentemente do tamanho que estes slots possam assumir durante a operação da rede, o teste de escalonabilidade será sempre realizado com o tamanho máximo definido pela ACU. Como consequência, esta abordagem reduz o custo computacional imposto à ACU, uma vez que o teste é apenas executado no momento da admissão de uma nova TS. Capítulo 4 - A Arquitetura RT-WiFi 91 A gestão dinâmica no tamanho dos slots permite uma melhor utilização dos recursos disponíveis na rede. Com o objetivo de otimizar a utilização deste recursos e, ao levar em consideração que em algumas situações o tamanho atual do slot é menor que o seu tamanho máximo, a arquitetura possibilita a transmissão de dois tipos de tráfego de tempo-real: alta e baixa prioridade; além de tráfego não tempo-real. Desta forma, o tráfego tempo-real de baixa prioridade é transmitido nos espaços alocados pelo tráfego tempo-real de alta prioridade, mas que no momento, devido a redução no tamanho atual destes slots, não estão a ser utilizados. No que diz respeito ao mecanismo de controlo de admissão, este foi construindo tendo como principal objetivo as deadlines das mensagens de cada TS admitida pela ACU. O objetivo é evitar que as características de algumas TS possam ser generalizadas, tal como algumas propostas apresentadas no capítulo anterior. Para isto, previamente à admissão de uma TSk, a respectiva estação deve enviar ao APTR uma requisição ADDTS contendo algumas informações de TSPEC. Após analisar este pedido a ACU decide entre a admissão ou não desta TS. Caso seja admitida, o algoritmo de escalonamento realizará a ordenação das transmissões com base na deadline de todas as TS admitidas pela ACU. Ressalva-se que, a arquitetura RT-WiFi foi desenvolvida de forma a facilitar a migração de um algoritmo de escalonamento para outro, sem que seja necessária uma reestruturação completa dos mecanismos da arquitetura. Para auxiliar na gestão dos recursos disponíveis, a arquitetura RT-WiFi implementa um mecanismo capaz de identificar e remover TS admitidas pela ACU e que por algum motivo não estejam em operação. Isto permite que os recursos alocados por estas TS possam ser libertados para outros fins. Outra vantagem da arquitetura RT-WiFi é a sua fácil implementação, sendo necessárias apenas pequenas modificações no driver/firmware dos dispositivos IEEE 802.11 padrão, o que torna esta proposta compatível com hardware COTS. Esta é uma característica muito importante do ponto de vista econômico, uma vez que não implica no desenvlvimento de novos dispositivos de comunicação para a implantação de uma rede RT-WiFi. Por fim, como todas as estruturas e formatos de mensagens utilizadas pela arquitetura RT-WiFi estão previstas na norma IEEE 802.11, esta mantém a sua compatibilidade com os dispositivos IEEE 802.11 standard. A única alteração significativa foi a introdução de uma lista de escalonamento na mensagem de beacon. No entanto, a norma IEEE 802.11 define que esta mensagem tem um tamanho variável e também existem campos reservados para uso futuro. Assim as alterações propostas não implicam nenhuma modificação no formato original desta mensagem. 92 Capítulo 4 - A Arquitetura RT-WiFi Capítulo 5 Resultados O principal objetivo deste capítulo é avaliar o comportamento da arquitetura RT-WiFi num ambiente de comunicação aberto. Para isso, definiu-se um conjunto de cenários representativos deste tipo de ambiente e avaliou-se a arquitetura proposta através de um conjunto de métricas relevantes. Além disso, compara-se o desempenho do RT-WiFi com soluções já existentes, nomeadamente com a função HCCA (HCF Controled Channel Access), uma vez que esta é a única solução definida pela norma IEEE 802.11 que suporta um mecanismo de controlo de admissão e um escalonador. Os resultados foram obtidos a partir de modelos de simulação do RT-WiFi e do HCCA1implementados utilizando a ferramenta OPNET Wireless Modeler [87]. 5.1 Descrição dos cenários Em consequência da crescente comercialização de dispositivos de comunicação baseados na norma IEEE 802.11 e na limitação do número de canais disponibilizados pela respectiva camada física, torna-se cada vez mais difícil a criação de um ambiente de comunicação fechado, ou seja, livre de interferências provenientes da sobreposição da outras redes que possam estar a operar na mesma zona geográfica. Esta situação torna-se ainda mais crítica em regiões metropolitanas, isto porque, com a redução de custos desta tecnologia, além das WLAN (Wireless Local Network) normalmente encontradas em escritórios, lojas, instituições de ensino e ambientes públicos, tem-se tornando cada vez mais frequente a utilização deste tipo de redes em ambientes domésticos. Neste contexto, optou-se por criar cenários de simulação que modelem a operação da rede de tempo-real (seja esta RT-WiFi ou HCCA) num ambiente de comunicação aberto. Assim, considerou-se que a rede de tempo-real (TR) tem a sua área de cobertura sobreposta por uma rede não tempo-real (NTR) a operar no mesmo canal de comunicação (Figura 5.1). A rede NTR gera diferentes tipos de tráfegos que estão fora da esfera de controlo do sistema de comunicação de tempo-real. Neste sentido, embora a maioria das redes IEEE 802.11 atuais utilizem como mecanismo de controlo de acesso ao meio a função DCF (Distributed Coordination 1A descrição do modelo HCCA é detalhada no anexo B. 100 Capítulo 5 - Resultados 3) Tráfego FTP (File Transfer Protocol) Este tráfego foi modelado como o envio e a receção de arquivos através de um serviço FTP alocado no SRVNTR. Utiliza o protocolo de transporte TCP para gerir suas conexões, e é transmitido através da fila best-effort da função EDCA, representando 5% da carga total imposta na rede [96, 97]. De todo o tráfego FTP processado pelas estações NTR, 80% é caracterizado pela receção de arquivos do SRVNT R e apenas 20% é caracterizado pelo envio de arquivos ao SRVNTR. O tamanho dos arquivos transferidos é modelado por uma distribuição Gaussiana tendo como valor médio 500 Kbytes [94]. Os intervalos de envio e requisições de arquivos são modelados por uma distribuição de Poisson [97]. A Tabela 5.6 resume os parâmetros utilizados para o tráfego FTP. Tabela 5.6: Parâmetros utilizados para o tráfego FTP. Parâmetro Carga Baixo Médio Alto Command Mix (Get/Total) 80% 80% 80% Inter-request Time (segundos) poisson(1) poisson(1) poisson(1) File Size (Kbytes) normal(µ=84,σ2=0.1) normal(µ=250,σ2=0.1) normal(µ=500,σ2=0.1) Type of Service (ToS) Best-Effort(0) Best-Effort(0) Best-Effort(0) 4) Tráfego de Vídeo Este tráfego foi modelado como chamadas de vídeo-conferência entre as estações NTR e o SRVNTR. Utiliza o protocolo UDP e representa 25% da carga total imposta na rede [96, 97]. As suas mensagens são transmitidas através da fila de vídeo da função EDCA. As chamadas de vídeo-conferência utilizam o codec8de vídeo H.264 [107] com o perfil CBP Constrained Baseline Profile [105]. Para possibilitar o aumento da carga de rede imposta pelas estações NTR, a resolução das chamadas de vídeo-conferência é aumentada. A Tabela 5.7 resume os parâmetros utilizados para o tráfego de vídeo. Tabela 5.7: Parâmetros utilizados para o tráfego de vídeo. Parâmetro Carga Baixo Médio Alto Frame Interarrival Time Information (segundos) constant(0.05) constant(0.05) constant(0.05) Frame Size Information (bytes) constant(730) constant(2175) constant(3625) Type of Service (ToS) Interactive Multimedia (5) Interactive Multimedia (5) Interactive Multimedia (5) 8Um codec é um dispositivo ou programa de computador capaz de codificar e decodificar um fluxo de dados ou um sinal digital. Capítulo 5 - Resultados 101 5) Tráfego de Voz Este tráfego foi modelado como chamadas de VoIP (Voice over IP) efetuadas entre as estações NTR e o SRVNTR. Utiliza o protocolo UDP e representa 15% da carga total imposta na rede [96, 97]. As suas mensagens são transmitidas através da fila de voz da função EDCA. As chamadas de VoIP utilizam o codec de voz G.711 [108] com um Codec Bit Rate que varia de acordo com a carga de rede imposta pelas estações NTR. Desta forma, como são transmitidas mensagens com um tamanho fixo de 20 milisegundos, o tamanho final da mensagem irá variar de acordo com o Codec Bit Rate utilizado [100]. Para possibilitar o aumento da carga de rede imposta pelas estações NTR, o Codec Bit Rate das chamadas de VoIP é aumentado. A Tabela 5.8 resume os parâmetros utilizados para o tráfego de voz. Tabela 5.8: Parâmetros utilizados para o tráfego de voz. Parâmetro Carga Alto Médio Alto Silence Length (segundos) exponential(0.01) exponential(0.01) exponential(0.01) Talk Spurt Length (segundos) exponential(0.992) exponential(0.992) exponential(0.992) Encoder Scheme G.711 G.711 G.711 Coding Rate (bits/segundo) 40 Kbps 135 Kbps 240 Kbps Frame Size (segundos) 0.02 0.02 0.02 Frame Size (bytes) 100 337.5 600 Voice Frames per Packet 1 1 1 Type of Service (ToS) Interactive Voice (6) Interactive Voice (6) Interactive Voice (6) Copression delay (segundos) 0.02 0.02 0.02 Decompression delay (segundos) 0.02 0.02 0.02 5.2 Resultados As métricas de desempenho analisadas são: atraso médio, percentagem média de deadlines perdidas, fairness e tamanho médio dos slots. O atraso médio das transmissões representa o atraso fim-a-fim das mensagens que foram transmitidas com sucesso das estações de tempo-real para o SRVTR. É importante observar que este valor não deve ultrapassar a deadline relativa estipulada para cada TS, caso contrário as mensagens serão entregues fora do prazo limite. Esta métrica permite também a avaliação do comportamento (variável ou constante) das transmissões. Neste contexto, para algumas aplicações de tempo-real, é desejável que o atraso nas transmissões tenha um comportamento constante, uma vez que isto torna as comunicações mais previsíveis e também possibilita a redução do jitter. Outra métrica analisada é a percentagem média de deadlines perdidas que, representa a percentagem de mensagens geradas pelas estações de tempo-real e que perderam as suas respectivas deadlines. É importante observar que nesta métrica são contabilizadas tanto as mensagens que foram entregues corretamente, mas fora do prazo limite, quanto as mensagens que não puderam ser entregues por erros e/ou colisões durante as suas respectivas transmissões. Esta métrica pode 102 Capítulo 5 - Resultados ser considerada uma das mais importantes na análise dos sistemas de comunicação de tempo-real, uma vez que quantifica de forma direta o limite crítico que o sistema poderá atingir. No contexto dos resultados do RT-WiFi, outra métrica considerada relevante é o tamanho médio dos slots. Este valor representa o tamanho médio dos slots alocados às TS admitidas pela ACU (Admission Control Unit). A sua análise possibilita observar o comportamento dinâmico do mecanismo responsável por gerir o tamanho dos slots sob diferentes cargas de rede e número de TS admitidas. Por fim, com o objetivo de avaliar o impacto que as comunicações de tempo-real têm sobre a rede não tempo-real, foi analisado também o impacto sobre o fairness das transmissões NTR. Faz-se observar que esta não é uma métrica clara e bem definida, tendo sido proposta na literatura diversas abordagens para a sua quantificação [109, 110, 111, 112, 113]. No entanto, com o objetivo de simplificar a sua avaliação, optou-se por analisá-la com base no throughput agregado da rede NTR, quando esta opera sozinha no meio de comunicação e, quando este é compartilhado com a rede TR. Para que fosse possível obter diferentes tendências e comportamentos, cada simulação foi repetida 5 vezes utilizando-se uma semente (seed) diferente para cada simulação. Logo, os resultados apresentados neste capítulo representam a média dos valores obtidos nestas simulações. Todos os resultados são apresentados com um intervalo de confiança de 95%, com uma largura relativa de 5%. O tempo de simulação utilizado representa o tempo necessário para que os resultados obtidos respeitassem o intervalo de confiança selecionado. 5.2.1 Atraso Médio A primeira avaliação considera um cenário onde cada estação TR admitida pela ACU gera mensagens num intervalo periódico de 30 milisegundos (P=30ms). Estas estações operam na mesma área de cobertura e canal de comunicação que outras 10 estações NTR que impõem diferentes cargas de rede (Baixa,Média eAlta). A Figura 5.2 ilustra o atraso médio das transmissões para um número de estações TR, que varia de 1 até o máximo suportado pelo mecanismo de controlo de admissão em questão (eixo X). A primeira característica que é possível observar é a grande diferença entre o número máximo de estações admitidas pelo RT-WiFi (19 estações) e pelo HCCA (apenas 2 estações). O número reduzido de estações admitidas pelo HCCA é o reflexo das regras pessimistas implementadas pelo seu respectivo mecanismo de controlo de admissão. Com relação ao atraso médio sofrido pelas transmissões do RT-WiFi, é possível observar que este é ligeiramente menor (≈15ms, ou seja, metade do SI) ao apresentado pelo HCCA (≈17 ms). Uma tendência semelhante à anterior pode ser observada na segunda avaliação, onde o cenário passa a considerar um período de geração de mensagens TR definido por P=60ms (Figura 5.3). Neste caso, devido à diminuição do número de mensagens geradas por cada TS a cada segundo, houve um acréscimo no número máximo de estação que ambos os sistemas de comunicação, RTWiFi e HCCA, são capazes de admitir. Capítulo 5 - Resultados 103 0 5 10 15 20 25 30 35 40 45 50 1 2 4 6 10 14 18 19 Atraso Médio (ms) Número de estações tempo-real HCCA (Baixa) HCCA (Média) HCCA (Alta) RT-WiFi (Baixa) RT-WiFi (Média) RT-WiFi (Alta) Figura 5.2: Atraso médio para o cenário P=30ms. 0 5 10 15 20 25 30 35 40 45 50 1 2 4 6 10 14 18 22 26 30 34 38 Atraso Médio (ms) Número de estações tempo-real HCCA (Baixa) HCCA (Média) HCCA (Alta) RT-WiFi (Baixa) RT-WiFi (Média) RT-WiFi (Alta) Figura 5.3: Atraso médio para o cenário P=60ms. No caso do RT-WiFi, o número de estações admitidas pela ACU duplicou, seguindo assim um comportamento já esperado, uma vez que o número de mensagens geradas por segundo em cada TS foi reduzido pela metade, quando comparado ao cenário anterior. O mesmo ocorreu como o HCCA, que passou a admitir 4 estações. Tal como no caso anterior, o atraso médio sofrido pelas transmissões do RT-WiFi (≈30ms) é ligeiramente inferior ao apresentado pelo HCCA que, se inicia em ≈31ms (para 1 estação admitida) indo até ≈33ms (para 4 estações admitidas). 104 Capítulo 5 - Resultados Por fim, a última avaliação realizada considera um cenário onde as estações TR têm um período de geração de mensagens de P=90ms (Figura 5.4). Assim como esperado, com a diminuição do número de mensagens geradas por cada TS a cada segundo, ocorreu um acréscimo no número de estações admiditas tanto pelo HCCA (que passou a admitir até 6 estações), quanto pelo RT-WiFi (que passou a admitir até 58 estações). 0 5 10 15 20 25 30 35 40 45 50 1 2 4 6 10 14 18 22 26 30 34 38 42 46 50 54 58 Atraso Médio (ms) Número de estações tempo-real HCCA (Baixa) HCCA (Média) HCCA (Alta) RT-WiFi (Baixa) RT-WiFi (Média) RT-WiFi (Alta) Figura 5.4: Atraso médio para o cenário P=90ms. Seguindo a tendência dos resultados anteriores, é possível observar que o atraso médio sofrido pelas transmissões do RT-WiFi (≈45ms) é ligeiramente inferior ao apresentado pelo HCCA, que se inicia em ≈46ms (para 1 estação admitida) indo até ≈48ms (para 6 estações admitidas). Para todos os resultados apresentados anteriormente, foram também avaliados os valores do respectivo desvio padrão. No entanto, devido a sua reduzida expressão (tipicamente <5%), não foram representados graficamente. Pode-se assim, concluir que, o jitter das transmissões de ambos os sistemas de comunicação, RT-WiFi e HCCA, é considerado pequeno. Com base na análise comparativa dos resultados, apresentados anteriormente, é possível concluir que o atraso médio da arquitetura RT-WiFi é quase constante e previsível (tendendo para SI/2 tal como esperado). Além disso, seu valor não sofre variações, nem com o aumento da carga de rede imposta pelas estações NTR, nem como o aumento do número de estações TR admitidas pela arquitetura. Este comportameto deve-se basicamente a dois factores. O primeiro é o uso do mecanismo FCR (Force Collision Resolution). Como as transmissões TR são efetuadas utilizando a fila de voz e para além disto não executam o procedimento de backoff, a sua probabilidade de aceder ao meio antes das estações NTR é maior. Desta forma é possível suportar diferentes cargas provenientes da rede NTR sem sofrer alterações significativas no atraso médio. O segundo factor é o uso do esquema TDMA (Time Division Multiple Access). Isto evita que as estações TR concorram entre si para aceder ao meio de comunicação, permitindo assim um Capítulo 5 - Resultados 105 aumento no número de estações TR admitidas sem sofrer variações no atraso médio das transmissões. Além disso, como este esquema distribui o acesso ao meio das estações TR dentro de um SI (Service Interval) e, como as estações TR foram inicializadas de forma aleatória e em momentos diferentes, isto faz com que os resultados do atraso médio tendam para SI/2. Na análise do atraso médio apresentado pelo HCCA, é possível observar que, tal como no RT-WiFi, este não sofre grandes variações devido ao aumento da carga de rede imposta pela rede NTR. Isto deve-se ao CFP (Contention Free Period) criado pelo seu mecanismo de polling, que bloqueia o meio de comunicação para a transmissão das mensages de tempo-real. No entanto, este mecanismo impõe o envio de uma mensagem de autorização para que uma estação TR possa iniciar a transmissão das suas mensagens. O envio destas mensagens de autorização pode ser considerado um overhead que pode ser observado no comportamento ascendente do atraso médio do HCCA sempre que uma nova estação TR é admitida. Por fim, com base na análise comparativa dos resultados apresentados, verifica-se que a arquitetura RT-WiFi é capaz de admitir quase 10 vezes mais estações TR que o HCCA. Esta é uma observação importante e que demonstra a escalabilidade da proposta. 5.2.2 Percentagem Média de Deadlines Perdidas A percentagem média de deadlines perdidas para o cenário P=30ms é apresentada na Figura 5.5. No que diz respeito ao RT-WiFi é possível verificar que, quando a carga imposta pelas estações NTR é considerada Baixa, esta métrica situa-se por volta de ≈0,5%. Quando a carga de rede aumenta até o nível considerado Médio, a percentagem média de deadlines perdidas também cresce para ≈2%. Por fim, quando a rede NTR impõe uma carga considerada Alta, a percentagem média de deadlines perdidas sobe para ≈4,25%. 0 1 2 3 4 5 6 7 8 1 2 4 6 10 14 18 19 Média de Deadlines Perdidas (%) Número de estações tempo-real HCCA (Baixa) HCCA (Média) HCCA (Alta) RT-WiFi (Baixa) RT-WiFi (Média) RT-WiFi (Alta) Figura 5.5: Média de deadlines perdidas para o cenário P=30ms. 106 Capítulo 5 - Resultados No que diz respeito ao HCCA, é possível verificar que as estações TR não perderam praticamente nenhuma deadline. Isto demonstra um comportamento esperado, uma vez que o HCCA bloqueia o acesso ao meio para poder efetuar as suas transmissões sem nenhuma contenção e/ou colisão. Embora possam ocorrer erros devido a ruídos nas transmissões, estes são resolvidos através de retransmissões. Para estes resultados foram também avaliados os valores do respectivo desvio padrão, os quais são representados em cada ponto do gráfico. Assim, para cada um, é possível observar os níveis de variação superior e inferior em relação à média. Neste contexto, verifica-se que, mesmo ao considerarmos o índice mais alto atingido por uma variação superior (1 estação RT-WiFi sob uma carga de rede Alta), o resultado apresentado mantém-se abaixo de 5%. A mesma métrica é apresentada na Figura 5.6 para o cenário onde P=60ms. No caso do RTWiFi é possível verificar que, para os níveis de carga impostos pela rede NTR considerados Baixo eMédio, os resultados para este cenário foram muito semelhantes aos apresentados anteriormente (≈0,5% e ≈2%, respectivamente). Quando comparados com os resultados anteriores, observa-se uma pequena diminuição na percentagem média de deadlines perdidas quando a carga de rede imposta pela rede NTR é considerada Alta, situando-se à volta de ≈4%. Isto deve-se ao aumento no intervalo de geração das mensagens, fazendo com que os requisitos temporais sejam reduzidos. No que diz respeito ao HCCA, e tal como esperado, é possível verificar o mesmo comportamento apresentado no resultado anterior. 0 1 2 3 4 5 6 7 8 1 2 4 6 10 14 18 22 26 30 34 38 Média de Deadlines Perdidas (%) Número de estações tempo-real HCCA (Baixa) HCCA (Média) HCCA (Alta) RT-WiFi (Baixa) RT-WiFi (Média) RT-WiFi (Alta) Figura 5.6: Média de deadlines perdidas para o cenário P=60ms. Por fim, são apresentados os resultados para o cenário de P=90ms (Figura 5.7). Com relação ao RT-WiFi verifica-se que, para o nível de carga de rede considerado Baixo, a percentagem média de deadlines perdidas não ultrapassa 0,5%. Quando a carga aumenta para o nível considerado Médio, a percentagem média de deadlines perdidas passa a ser ≈1,5%. Por fim, quando a carga é considerada Alta, a percentagem média de deadlines perdidas sobe para ≈3,5%. Capítulo 5 - Resultados 107 De forma análoga, os resultados obtidos pelo HCCA mantém a mesma tendência apresentada nos resultados anteriores. 0 1 2 3 4 5 6 7 8 1 2 4 6 10 14 18 22 26 30 34 38 42 46 50 54 58 Média de Deadlines Perdidas (%) Número de estações tempo-real HCCA (Baixa) HCCA (Média) HCCA (Alta) RT-WiFi (Baixa) RT-WiFi (Média) RT-WiFi (Alta) Figura 5.7: Média de deadlines perdidas para o cenário P=90ms. Ao compararmos os resultados obtidos pelo RT-WiFi no cenário de P=90ms com os obtidos nos cenários anteriores, é possível verificar uma queda na percentagem média de deadlines perdidas para todos os 3 tipos de cargas consideradas. Isto deve-se ao aumento do intervalo de geração das mensagens que, por consequência, aumenta também o tempo máximo disponível para a entrega das mesmas. Com base na análise comparativa dos resultados previamente apresentados, pôde-se concluir que o RT-WiFi apresenta um comportamento semelhante nos três cenários avaliados, não sendo afetado pelo aumento do número de estações TR. Além disso, a percentagem média de deadlines perdidas (mesmo ao considerarmos os valores do desvio padrão) encontra-se abaixo do limite de 5% normalmente imposto por sistemas de controlo [114]. Uma análise mais aprofundada destes resultados mostrou que, a principal causa da perda das deadlines no RT-WiFi está relacionada com a perda da mensagem de beacon. Como esta mensagem é utilizada para sincronizar o ciclo TDMA e difundir a lista de escalonamento, com a sua perda, as estações não iniciam as suas respectivas transmissões. Um comportamento com leves variações pode ser observado nos resultados apresentados pelo RT-WiFi. Estas variações devem-se ao posicionamento aleatório das estações TR no ambiente de comunicação, uma vez que, para um número diferente de estações em posições geográficas diferentes, poderá incedir à cada uma diferentes níveis de interferência. No entanto, mesmo assim é possível observar que estas variações encontram-se dentro do desvio padrão apresentado. No que diz respeito aos resultados obtidos pelo HCCA, embora este não tenha perdido praticamente nenhuma deadline, o seu mecanismo de controlo de admissão impõe uma grave limitação no que diz respeito ao número máximo de estações TR que podem ser admitidas. 108 Capítulo 5 - Resultados 5.2.3 Fairness Como previamente discutido, embora na comunidade científica exista um consenso acerca do significado do fairness nas comunicações (ou seja, um equilíbrio dos direitos de transmissão entre as estações em operação numa determinada rede ou local), o mesmo não ocorre acerca da sua metodologia de quantificação, existindo diversas abordagens propostas [109, 110, 111, 112, 113]. No entanto, com o objetivo de simplificar a sua avaliação, neste trabalho optou-se por analisar o fairness com base no throughput agregado da rede NTR, quando esta opera sozinha no meio de comunicação, comparando estes resultados com os valores obtidos quando o meio de comunicação é compartilhado com a rede TR. Desta forma, o fairness do RT-WiFi para o cenário de P=30ms é apresentado na Figura 5.8. A primeira coluna apresenta o throughput agregado da rede NTR quando a carga de rede é considerada Baixa e sem a presença da rede RT-WiFi. As 3 colunas apresentam o throughput agregado da rede NTR, quando uma rede RT-WiFi com 2, 10 e 19 estações está a operar sobreposta, respectivamente. É possível verificar que não ocorre nenhuma variação significativa. 0 2 4 6 8 10 12 14 16 18 20 Baixa Média Alta Throughput das estações NTR (Mbits/s) Carga da Rede Sem estações TR 2 estações TR 10 estações TR 19 estações TR Figura 5.8: Fairness para o cenário P=30ms. A mesma comparação é realizada para as cargas consideradas Média eAlta. É possível verificar uma pequena variação apenas quando a carga de rede imposta é considerada Alta e quando a arquitetura RT-WiFi opera com 19 estações, ou seja, o limite para este cenário. Mesmo assim, a variação apresentada (< 0,5 Mbits/s) pode ser considerada pequena. Ofairness para o cenário de P=60ms é apresentado na Figura 5.9. Ao observarmos os resultados obtidos é possível verificar que estes seguem a mesma tendência dos anteriores. Neste caso em específico, o throughput agregado da rede NTR sofre apenas uma pequena diminuição no seu nível, quando o nível de carga de rede é considerado Alto. Neste contexto, é possível verificar uma variação mínima, quando o RT-WiFi opera com 22 estações e uma variação maior quando o RT-WiFi opera com 38 estações. No entanto, esta última variação (< 0,5 Mbits/s) continua a ser considerada pequena. Capítulo 5 - Resultados 109 0 2 4 6 8 10 12 14 16 18 20 Baixa Média Alta Throughput das estações NTR (Mbits/s) Carga da Rede Sem estações TR 6 estações TR 22 estações TR 38 estações TR Figura 5.9: Fairness para o cenário P=60ms. No cenário de P=90ms (Figura 5.10) é possível observar a mesma tendência apresentada nos resultados anteriores, onde as variações no throughput agregado da rede NTR ocorrem apenas quando se impõe uma carga considerada Alta. A principal diferença é que neste caso a variação sofrida pela rede NTR se inicia quando o RT-WiFi está a operar com 18 estações. Esta variação aumenta conforme ocorre o aumento do número de estações TR. No entanto, embora a variação máxima apresentada seja de 0,9 Mbits/s, esta ainda pode ser considerada pequena, tendo em conta o número de estações TR que foram admitidas pelo RT-WiFi (58 estações). 0 2 4 6 8 10 12 14 16 18 20 Baixa Média Alta Throughput das estações NTR (Mbits/s) Carga da Rede Sem estações TR 18 estações TR 38 estações TR 58 estações TR Figura 5.10: Fairness para o cenário P=90ms. 116 Capítulo 5 - Resultados Por fim, é possível observar que o conjunto de mecanismos implementados pela arquitetura RT-WiFi consegue, garantir uma alta taxa de cumprimento das deadlines (superior a 95%), além de ser capaz de admitir quase 10 vezes mais estações de TR que a função HCCA sem que para isto seja necessário o bloqueio do acesso ao meio pela rede TR. Capítulo 6 Conclusões e Trabalhos Futuros Este capítulo resume os principais resultados obtidos nesta tese, destacando as contribuições resultantes da investigação, assim como também apresentada algumas perspectivas para trabalhos de investigação futuros que possam surgir a partir deste trabalho. 6.1 Conclusões O objetivo principal desta tese foi propor uma solução que permitisse a transmissão de tráfego de tempo-real em redes sem fios a operar em ambientes de comunicação abertos, nomeadamente industriais. Neste contexto, optou-se por dar ênfase à soluções compatíveis com a norma IEEE 802.11, uma vez que esta se tornou um standard de facto para a implementação de WLAN (Wireless Local Network). Baseada na análise da norma IEEE 802.11 foi possível identificar várias limitações no que diz respeito à sua utilização para a transmissão de tráfego de tempo-real. A compreensão detalhada dos seus modos de funcionamento, bem como das respectivas limitações, serviram como base para a definição dos pré-requisitos que a solução proposta deveria contemplar. Complementarmente, foram também analisadas, classificadas e comparadas diversas soluções propostas para a transmissão de tráfego de tempo-real sobre redes IEEE 802.11. No que diz respeito às soluções focadas no Mecanismo de Controlo de Acesso ao Meio, foi possível definir uma classificação em três eixos. O primeiro define a arquitetura (centralizada ou distribuída) utilizada. Neste contexto, concluiu-se que a utilização de uma arquitetura centralizada seria capaz de fornecer melhores resultados no que diz respeito à gestão das transmissões de tempo-real, uma vez que a solução teria uma visão global do ambiente de comunicação. O segundo eixo de classificação define a forma como as soluções tratam as colisões. Neste contexto, foram definidas 3 categorias: soluções que evitam colisões, que resolvem as colisões e que reduzem a ocorrência de colisões. Concluiu-se que as soluções mais adequadas são aquelas 118 Capítulo 6 - Conclusões e Trabalhos Futuros que tentam resolver ou evitar as colisões, uma vez que é possível gerar um comportamento mais previsível na transmissão das mensagens de tempo-real. Por fim, o terceiro eixo de classificação define a forma como as soluções se comportam na presença de estações IEEE 802.11 standard a operar em redes sobrepostas à rede de tempo-real, além de analisar também, a possibilidade de implementação das soluções em hardware COTS (Commercial Off-The-Shelf ). Através desta avaliação, ficou claro que existem poucas soluções que possibilitam a coexistência de dispositivos de tempo-real e dispositivos IEEE 802.11 standard no mesmo ambiente de comunicação. A maioria das soluções analisadas necessita de um controlo completo do ambiente de comunicação, ou seja, todas as estações que estejam a operar no mesmo canal de comunicação e área de cobertura devem obrigatoriamente estar dentro da esfera de controlo da arquitetura de tempo-real. Porém, com a crescente utilização de dispositivos de comunicação sem fio, não é realista assumir-se atualmente a possibilidade de criar um ambiente de comunicação fechado, uma vez que o meio de comunicação utilizado por este tipo de tecnologia é compartilhado. Desta forma, as soluções que garantem as características de tempo-real através do controlo de todos os dispositivos de comunicação existentes no ambiente não são consideradas aplicáveis. No que diz respeito ao Mecanismo de Controlo de Admissão, foi definida uma classificação em 2 eixos para a análise das soluções existentes. O primeiro eixo define a abordagem utilizada pelo modelo. Esta, por sua vez, é classificada em 3 diferentes categorias: a) baseadas em modelos, b) baseadas em métricas e, c) híbridas. Neste contexto, concluiu-se que a utilização de uma abordagem híbrida seria a melhor opção, uma vez que, permite um comportamento dinâmico por parte do mecanismo de controlo de admissão que, além de utilizar informações TSPEC para decidir entre a admissão (ou não) de uma TS (Traffic Stream), pode também utilizar dados provenientes do meio de comunicação e também das estações. O segundo eixo define a arquitetura (centralizada ou distribuída) utilizada pelas soluções. Concluiu-se que a utilização de uma arquitetura centralizada seria capaz de fornecer melhores resultados no que diz respeito à gestão das transmissões de tempo-real, uma vez que a ACU (Admission Control Unit) possui uma visão global do ambiente de comunicação. Esta conclusão, por sua vez, vem de encontro a obtida na análise das soluções relativas aos mecanismos de controlo de acesso ao meio. Além destes dois eixos de classificação, da análise das soluções focadas no Mecanismo de Controlo de Admissão resultou numa lista de características apresentadas por cada um: suporte aos tráfegos CBR (Constant Bit Rate), VBR (Variable Bit Rate) e aperiódico, utilização (pela ACU) de informações TSPEC (Traffic Specification) e de medidas do meio de comunicação para o auxílio à tomada de decisão, utilização de um escalonador baseado nas deadlines das mensagens e tipo de mecanismo de controlo de acesso ao meio sobre o qual a soluções foram construídas. Partindo da análise de todas estas propostas, foi possível definir uma lista de pré-requisitos necessários numa nova solução capaz de suportar a transmissão de tráfego de tempo-real em redes IEEE 802.11: Capítulo 6 - Conclusões e Trabalhos Futuros 119 • ser capaz de garantir requisitos soft real-time, mesmo quando estiver a operar num ambiente de comunicação aberto, onde o meio de comunicação é compartilhado com estações que estão fora da esfera de controlo da arquitetura de tempo-real; • implementação compatível com hardware COTS; • mecanismo de controlo de acesso ao meio capaz de: –resolver ou evitar as colisões, uma vez que ambas as abordagens visam garantir limites temporais para a sua resolução; –reduzir o overhead gerado pelos mecanismos de polling tradicionais; • mecanismo de controlo de admissão capaz de: –utilizar uma abordagem híbrida, obtendo tanto informações das TS (via TSPEC), quanto do meio de comunicação para analisar o pedido de admissão de uma nova TS; –gerir as variações que possam ocorrer nos valores medidos no meio de comunicação e/ou nas estações; –caracterizar as TS através do uso de informações TSPEC; –implementar um algoritmo de escalonamento de tempo-real para organizar a sequência de transmissão das mensagens com base nas respectivas deadlines; –identificar e remover as TS que possam se encontrar num estado de "falha", ou seja, que estejam com recursos alocados mas que não estejam em operação. Neste contexto, foi proposta uma nova arquitetura para comunicação de tempo-real em redes IEEE 802.11, denominada RT-WiFi. Esta arquitetura, organizada em duas camadas, propõe dois novos mecanismos de Controlo de Acesso ao Meio e de Controlo de Admissão com o objetivo de garantir o cumprimento das deadlines específicas de cada TS admitida pela ACU, mesmo quando o meio de comunicação é partilhado com estações que estejam fora da sua esfera de controlo. OMecanismo de Controlo de Acesso ao Meio implementa um esquema de separação de tráfego que permite a priorização do tráfego de tempo-real sobre os restantes tipos de tráfego sem que para isto seja necessário controlar todas as estações que estejam a operar no ambiente de comunicação. Além disso, implementa também um esquema TDMA para evitar colisões entre mensagens de tempo-real. A utilização deste esquema possibilita também a redução do overhead da transmissão, resultante do envio das mensagens de autorização para as estações, quando comparado ao mecanismo tradicional de polling utilizado pela grande maioria das soluções existentes. Sobre este mecanismo é implementado o Mecanismo de Controlo de Admissão. A sua implementação assume uma abordagem híbrida, onde, além de utilizar os requisitos temporais especificados por cada TS (através do envio de mensagens TSPEC), permite também alterar dinamicamente o seu comportamento, através da constante análise dos atrasos sofridos por cada transmissão de tempo-real. Isto permite à ACU redimensionar os slots alocados a cada TS de forma a otimizar 120 Capítulo 6 - Conclusões e Trabalhos Futuros a alocação dos recursos do sistema. Outra função implementada pela ACU é a de identificar a possibilidade de uma TS se encontrar num estado de "falha"e, então removê-la da lista de alocação de forma a libertar os recursos por ela reservados. O mecanismo implementa também um algoritmo de escalonamento que reordena, a cada ciclo TDMA, a sequência de alocação dos slots de forma a cumprir as deadlines das mensagens de tempo-real. Os resultados obtidos pela arquitetura RT-WiFi mostram claramente que esta é capaz de garantir uma elevada probabilidade de sucesso nas transmissões do tráfego de tempo-real. Uma característica importante é que, para os cenários avaliados, independentemente da carga de rede imposta pelas estações que estão fora da esfera de controlo da arquitetura de tempo-real, ou do número de estações existentes na rede de tempo-real, o atraso médio das transmissões no RT-WiFi é aproximadamente constante e tem um comportamento previsível (tendendo para SI/2). Outra característica importante é a sua capacidade de suportar um número elevado de estações de tempo-real. Os resultados obtidos mostram claramente que mesmo para o cenário mais exigente (onde a carga de rede imposta pelas estações não tempo-real se encontra perto do ponto de saturação e onde é atingido o limite máximo de estações de tempo-real admitidas pelo controlo de admissão), a arquitetura RT-WiFi é capaz de suportar a transmissão do tráfego de tempo-real e manter uma percentagem média de perdas de deadlines inferior aos 5% geralmente admissíveis nos sistemas de controlo. A arquitetura RT-WiFi apresenta também um nível adequado de fairness, pois a sua operação não resulta em interferências significativas sobre as restantes estações que estão fora da esfera de controlo da arquitetura de tempo-real. Embora a arquitetura RT-WiFi tenha sido concebida com o foco em ambientes industriais, esta última característica em particular possibilita expandir a sua operação para ambientes domésticos e empresariais. Adicionalmente, a implementação da arquitetura RT-WiFi pode ser realizada através de pequenas modificações no driver/firmware dos dispositivos IEEE 802.11 já existentes, tornando-a assim compatível com hardware COTS. Por fim, importa também referir, como contribuição desta tese, a implementação de um modelo de simulação da função HCCA (HCF Controlled Channel Access) para a ferramenta OPNET. Este modelo teve como objetivo a geração de resultados comparativos com a arquitetura RT-WiFi. Além disso, também foi possível entender as limitações do HCCA, quando este é utilizado para suportar tráfego de tempo-real. A principal conclusão obtida foi que, embora o HCCA possa ser compatível com a transmissão de alguns tipos de tráfego de tempo-real (nomeadamente CBR), este sofre uma grave limitação no que diz respeito ao número máximo de estações que podem ser admitidas pelo seu mecanismo de controlo de admissão. 6.2 Trabalhos Futuros Os trabalhos futuros que surgem a partir desta tese estão intimamente relacionados com a arquitetura RT-WiFi. Em primeiro lugar, a utilização da mensagem de beacon para o envio da lista de escalonamento deve ser cuidadosamente avaliada. Como a sua transmissão é realizada em broadcast (ou seja, sem confirmação), estações que estejam fora da área de cobertura geográfica Capítulo 6 - Conclusões e Trabalhos Futuros 121 do AP (Access Point) ou que recebam a mensagem de beacon corrompida não poderão iniciar as suas transmissões. Como consequência, as TS alocadas nestas estações perderão as respectivas deadlines. Neste contexto, devem ser propostas técnicas que efetuem a transmissão da mensagem de beacon de forma mais eficiente, como por exemplo reliable broadcast ou reliable multicast. Outra possibilidade seria desenvolver um mecanismo de recuperação (por parte das estações) da lista de escalonamento quando a mensagem de beacon é perdida. Como o APTR pode ser considerado um ponto único de falha, é interessante analisar a arquitetura RT-WiFi do ponto de vista de tolerância a falhas. Neste contexto, poderiam ser propostos mecanismos de recuperação do APTR (por exemplo, shadowing) e analisar o seu comportamento em diferentes situações de falha de modo a avaliar o seu impacto na perda das deadlines das mensagens. A proposta realizada nesta tese apresenta a arquitetura RT-WiFi a operar numa única BSS (Basic Service Set). No entanto, poderiam ser propostas soluções onde múltiplas redes RT-WiFi poderiam trocar mensagens entre si através do DS (Distribution System). Neste contexto, para garantir o correto escalonamento das mensagens com origem numa das redes e transmitida para a outra, seria necessário propor um mecanismo capaz de realizar um escalonamento centralizado destas transmissões. De forma análoga, poderiam ser propostas soluções para situações onde duas (ou mais) redes RT-WiFi sem qualquer ligação lógica entre si estejam a operar na mesma área de cobertura geográfica e canal de comunicação. Outra avaliação que poderia ser realizada seria a análise de uma forma mais robusta da arquitetura RT-WiFi. Neste contexto, e de forma semelhante ao mecanismo de polling, a mensagem de beacon criaria um período livre de contenção (CFP – Contention Free Period) para o envio da lista de escalonamento e também onde os slots das estações de tempo-real seriam alocados. De forma a garantir o controlo do meio de transmissão, todas as mensagem de tempo-real transmitidas neste período transportam no respectivo campo duration do seu cabeçalho um valor condizente com o fim do CFP. A vantagem desta abordagem está na redução do número de deadlines perdidas, e também numa redução dos recursos alocados a cada TS, possibilitando uma expansão do número máximo de TS admitidas. No contexto da análise do atraso sofrido pelas estações de tempo-real para iniciarem suas respectivas transmissões, torna-se interessante realizar testes com diferentes valores de αpara otimizar a janela deslizante utilizada para suavizar as variações na rede. Além disso, outros mecanismos de caracterização de tendência comportamental poderiam ser propostos e avaliados. Por fim, podemos concluir que a transmissão de tráfego de tempo-real (nomeadamente soft real-time) em redes sem fios apresenta-se como uma tendência natural a ser adotada pelas indústrias. O nível de exigência das aplicações que utilizarão estes sistemas de comunicação crescerá acompanhando os níveis de desempenho que estes possam proporcionar. O aumento da confiabilidade e disponibilidade destas soluções pode ser atingido através da coordenação de esforços empregues tanto na camada física (reduzindo o número de erros de transmissão) quanto na subcamada MAC (coordenando o acesso ao meio e a alocação de recursos). Porém, outro aspecto que se aponta como fundamental para a adoção destas soluções em larga escala diz respeito à sua 122 Capítulo 6 - Conclusões e Trabalhos Futuros segurança. Uma vez que estas soluções operam num ambiente de comunicação aberto estão mais suscetíveis às tntativas de ataque. Desta forma, garantir requisitos de confidencialidade, integridade, autenticidade e disponibilidade dos fluxos de dados será tão importante quanto a garantia dos seus requisitos temporais. Referências [1] IEEE Standard for Information Technology - Telecommunications and Information Exchange Between Systems - Local and Metropolitan Area Networks - Specific Requirements - Part 11: Wireless Medium Access Control (MAC) and Physical Layer (PHY) Specifications, Junho 1997. [2] IEEE Standard for Information Technology - Telecommunications and Information Exchange Between Systems - Local and Metropolitan Area Networks - Specific Requirements - Part 11: Wireless Medium Access Control (MAC) and Physical Layer (PHY) Specifications, 1999. [3] Tomoko Miyano, Shinya Otsuki, Makoto Umeuchi, e Mamoru Ogasawara. Admission and Traffic Control Techniques for WLANs. Special Feature: QoS Control Techniques for Quality Improvement in Wireless Local Area Networks 11, NTT Access Network Service Systems Laboratories, Novembro 2007. [4] IEEE Standard for Information Technology - Telecommunications and Information Exchange Between Systems - Local and Metropolitan Area Networks - Specific Requirements - Part 11: Wireless Medium Access Control (MAC) and Physical Layer (PHY) Specifications, 2012. [5] G. Cena, I. C. Bertolotti, A. Valenzano, e C. Zunino. Evaluation of response times in industrial WLANs. IEEE Transactions on Industrial Informatics, 3(3):191–201, 2007. [6] T. Sauter. The continuing evolution of integration in manufacturing automation. IEEE Industrial Electronics Magazine, 1(1):10–19, 2007. [7] P. Ramanathan. Overload management in real-time control applications using (m, k)-firm guarantee. IEEE Transactions on Parallel and Distributed Systems, 10(6):549–559, 1999. [8] L. Lo Bello, G. A. Kaczynski, e O. Mirabella. Improving the real-time behavior of ethernet networks using traffic smoothing. IEEE Transactions on Industrial Informatics, 1(3):151– 161, 2005. [9] K. Kopetz. The time-triggered model of computation. Em Proceedings of the 19th IEEE Real-Time Systems Symposium (RTSS), pp. 168–177, 1998. [10] R. Moraes, P. Portugal, F. Vasques, e R. F. Custódio. Assessment of the IEEE 802.11e EDCA Protocol Limitations when Dealing with Real-Time Communication. EURASIP Journal on Wireless Communications and Networking, 2010. [11] G. Cena, L. Seno, A. Valenzano, e C. Zunino. On the Performance of IEEE 802.11e Wireless Infrastructures for Soft-Real-Time Industrial Applications. IEEE Transactions on Industrial Informatics, 6(3):425–437, 2010. 124 REFERÊNCIAS [12] G. Cena, A. Valenzano, C. Zunino, e L. Seno. Evaluation of real-time communication performance in QoS-enabled infrastructure WLANs. Em Proceedings of the 14th IEEE International Conference on Emerging Technologies and Factory Automation (ETFA), pp. 1149–1155, 2009. [13] G. Gamba, L. Seno, e S. Vitturi. Theoretical and experimental evaluation of polling times for wireless industrial networks using commercially available components. Em Proceedings of the 15th IEEE Conference on Emerging Technologies and Factory Automation (ETFA), pp. 1–8, 2010. [14] Supplement to IEEE Standard for Information Technology - Telecommunications and Information Exchange Between Systems - Local and Metropolitan Area Networks - Specific Requirements - Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) specifications: Higher-Speed Physical Layer Extension in the 2.4 GHz Band, Setembro 1999. [15] Supplement to IEEE Standard for Information Technology - Telecommunications and Information Exchange Between Systems - Local and Metropolitan Area Networks - Specific Requirements - Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) specifications: High-speed Physical Layer in the 5 GHZ Band, Setembro 1999. [16] IEEE Standard for Information Technology - Telecommunications and Information Exchange Between Systems - Local and Metropolitan Area Networks - Specific Requirements - Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) specifications: Amendment 4: Further Higher Data Rate Extension in the 2.4 GHz Band, Junho 2003. [17] IEEE Standard for Information Technology - Telecommunications and Information Exchange Between Systems - Local and Metropolitan Area Networks - Specific Requirements - Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) specifications: Amendment 8: Medium Access Control (MAC) Quality of Service Enhancements, Novembro 2005. [18] IEEE Standard for Information Technology - Telecommunications and Information Exchange Between Systems - Local and Metropolitan Area Networks - Specific Requirements - Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) specifications: Amendment 5: Enhancements for Higher Throughput, Outubro 2009. [19] D. Gao, J. Cai, e K. N. Ngan. Admission control in IEEE 802.11e wireless LANs. IEEE Network, 19(4):6–13, 2005. [20] R. Moraes, P. Portugal, e F. Vasques. Simulation analysis of the IEEE 802.11e EDCA protocol for an industrially-relevant real-time communication scenario. Em IEEE International Conference on Emerging Technologies and Factory Automation (ETFA), pp. 202–209, 2006. [21] C. Casetti, C. F. Chiasserini, M. Fiore, e M. Garetto. Notes on the Inefficiency of 802.11e HCCA. Em Proceedings of the 62nd IEEE Vehicular Technology Conference, volume 4, pp. 2513–2517, Setembro 2005. [22] P. Garg, R. Doshi, R. Greene, M. Baker, M. Malek, e X. Cheng. Using IEEE 802.11e MAC for QoS over Wireless. Em IEEE International Performance, Computing, and Communications Conference, pp. 537–542, 2003. REFERÊNCIAS 125 [23] J. D. Decotignie. Ethernet-Based Real-Time and Industrial Communications. Proceedings of the IEEE, 93(6):1102–1117, 2005. [24] J. Son, I. G. Lee, H. J. Yoo, e S. C. Park. An effective polling scheme for IEEE 802.11e. IEICE Transactions on Communications, E88.B(12):4690–4693, 2005. [25] D. Miorandi e S. Vitturi. Analysis of master-slave protocols for real-time-industrial communications over IEEE 802.11 WLANs. Em Proceedings of the 2nd IEEE International Conference on Industrial Informatics (INDIN), pp. 143–148, Junho 2004. [26] S.C. Lo, G. Lee, e W.T. Chen. An efficient multipolling mechanism for IEEE 802.11 wireless LANs. IEEE Transactions on Computers, pp. 764–778, 2003. [27] S. Lee, K.N. Ha, J.H. Park, K.C. Lee, G.S. Byun, e H.K. Lee. NDIS-based virtual polling algorithm for IEEE 802.11b for guaranteeing the real-time requirements. Computer Standards & Interfaces, 29(3):316–324, 2007. [28] F. De Pellegrini, D. Miorandi, S. Vitturi, e A. Zanella. On the use of wireless networks at low level of factory automation systems. IEEE Transactions on Industrial Informatics, 2(2):129–143, 2006. [29] A. Willig. A MAC protocol and a scheduling approach as elements of a lower layers architecture in wireless industrial LANs. Em Proceedings of the IEEE International Workshop on Factory Communication Systems (WFCS), pp. 139–148, 1997. [30] S. Hantrakoon e A. Phonphoem. Priority Based HCCA for IEEE 802.11e. Em Proceedings of the International Conference on Communications and Mobile Computing (CMC), volume 3, pp. 485–489, Abril 2010. [31] J. Kiszka, B. Wagner, Y. Zhang, e J. Broenink. RTNet - A flexible hard real-time networking framework. Em Proceedings of the 10th IEEE International Conference on Emerging Technologies and Factory Automation (ETFA), pp. 19–22, 2005. [32] G. Boggia, P. Camarda, L.A. Grieco, e G. Zacheo. An experimental evaluation on using TDMA over 802.11 MAC for Wireless Networked Control Systems. Em Proceedings of the IEEE International Conference on Emerging Technologies and Factory Automation (ETFA), pp. 1157–1160, 2008. [33] Xenomai: Real-Time Framework for GNU/Linux, 2010. URL: http://www.xenomai. org. [34] RaLink Technologies , 2010. URL: http://www.ralinktech.com/. [35] L. Seno, S. Vitturi, e C. Zunino. Analysis of Ethernet Powerlink Wireless Extensions Based on the IEEE 802.11 WLAN. IEEE Transactions on Industrial Informatics, 5(2):86–98, Maio 2009. [36] Ethernet Powerlink Standarization Group: Ethernet Powerlink Communication Profile Specification, 2004. [37] P. Bartolomeu, J. Ferreira, e J. Fonseca. Enforcing Flexibility in Real-Time Wireless Communications: A Bandjacking Enabled Protocol. Em Proceeding of the 14th IEEE Conference on Emerging Technologies Factory Automation (ETFA), pp. 1–4, Setembro 2009.