Blog

SBRC 2007 – Redes IEEE 802. 16 e em Malha 723 Escalonamento com Qualidade de Servico em redes IEEE 802. 16 Juliana Freitag e Nelson L. S. da Fonseca Instituto de Computacao – Universidade Estadual de Campinas (UNICAMP) s – Caixa Postal 6176 – 13084-971 – Campinas – sp – Brasil OF34 Abstract. In order to applications the IEEE p h-bandwidth cted to provide Quality of Service (QOS). Although the stahdard defines a QOS signaling framework and four service levels, scheduling disciplines for these service levels are unspecified. In this paper, we introduce a scheduling scheme for the uplink traffic.

Simulation esults show that our scheme is able to provide QOS and share in a fair way the resources between connections in the same service level. Resumo. Para que o padr- o IEEE 802. 16 seja adotado no acesso a aplicacoes a de tempo real e aplicacoes que demandam alta largura de banda e necess’ rio , – a ‘ que forneca Qualidade de Servico (QoS). O padr- o define um mecanismo de a sinalizacao entre a estacao base e as estacoes cliente e quatro n ‘ veis de servico, – – – entretanto, disciplinas de escalonamento n- o foram definidas.

Este artigo a prop- e um mecanismo de escalonamento para o tr’ fego uplink. Resultados partir de experimentos de simulacao mostram que o mecanismo proposto e capaz de prover QoS e de compartilhar os recursos de forma justa entre • conex- es de um mesmo n ‘vel de servico. o l. 1. Introducao O padr- o IEEE 802. 16 [IEEE Std. 2004], freq” enternente referenciado como WiMAX a u (Worldwide Interoperability for Microwave Access Forum), vem sendo desenvolvido com a finalidade de padronizar a tecnologia de acesso sem fio em banda larga.

O padr- o a define a interface a” rea e o protocolo de acesso ao meio para redes metropolitanas sem fio e fornecendo altas taxas de transmiss- o para o acesso comercial e residencial Internet. a para dar suporte a grande diversidade de aplicacoes dispon veis na Internet, tais como servicos de voz, v’ deo, multim’ dia e transfer- ncia de arquivos, o padr- o define e a mecanismos de sinalizacao entre a estacao base e as estacoes cliente e quatro n’ veis de – I servico. Embora esses servicos fornecam a base para a provis- o de Qualidade de Servico a . QoS), para que essa tarefa seja realizada de maneira eficiente os fabricantes de equipamentos WiMAX devem projetar e implementar um conjunto de mecanismos n- o esa pecificados no padr- o. Tais mecanismos incluem oliciamento e moldagem do tr’ fego, a a controle de admiss- o e escalonamento. a O presente trabalho foi realizado com o apoio do UOL (www. uol. com. br), atrav’ s do Programa UOL e Bolsa Pesquisa, 34 trabalho foi realizado com o apoio do UOL (vvww. uol. com. br), atrav’ s do Programa UOL e Bolsa Pesquisa, processo n • mero 20060511022200a e do CNPq, processo n’ mero 305076/2003-5. 24 25a Simpósio Brasileiro de Redes de Computadores e Sistemas Distribuídos Devido a natureza vari’ vel do tr’ fego multim• dia, mecanismos de policiamento e aa I moldagem do tr’ fego s- o necess• rios as estacoes cliente para assegurar a utilizacao justa a a a s – eficiente dos recursos da rede [Pellegrini 2006]. O policiamento protege a rede contra tr’ fegos “mal comportados”, ou seja, tr fegos que violam os par” metros negociados dua a a rante o estabelecimento da conex- o. O mecanismo de moldagem do tr’ fego tem como a a tarefa regular o tr’ fego para que os par- metros negociados sejam respeitados.

O mecaa a a u a nismo de controle de admiss- o restringe o n • mero de usu rios simultaneamente presentes na rede de forma a evitar a saturacao do enlace sem fio e, conseq ” entemente, a violacao dos requisitos de QoS. Embora os mecanismos mencionados sejam necess nos para provis- o de QoS, o a a n • cleo de tal tarefa reside no algoritmo de escalonamento. Um algoritmo de escalonau mento eficiente e essencial para garantir que os requisitos de QoS sejam atendidos e tem ” grande influ- ncia no desempenho da rede. O escalonamento do tr• fego downlink no padr- o IEEE 802. 16 requer um unico aa ‘ escalonador escalonamento do tr’ fego downllnk no padr- o IEEE 802. 16 requer um unico a a ‘ escalonador na estacao base, enquanto o escalonamento uplink precisa de dois compo,- nentes, um na stacao base e um na estacao cliente. O escalonador na estacao base aloca largura de banda para as estacoes cliente e o escalonador na estacao cliente determina , – – quais pacotes ser- o enviados nas oportunidades de transmiss- o recebidas. a Este artigo prop- e um algoritmo de escalonamento para a estacao base, cuja finao lidade e fazer a alocacao de banda para as estacoes cliente levando em consideracao as requisicoes de banda e os requisitos de QoS de cada n’ vel de servico. O escalonamento I nas estacoes cliente e uma tarefa mais simples, dado que o escalonador tem acesso direto filas. O escalonador na estacao base depende das mensagens de requisicao de banda para ter conhecimento da situacao das filas nas estacoes cliente e, portanto, suas decis- es o podem estar baseadas em informacoes desatualizadas que podem prejudicar a provis- o de a QoS.

Diferente de outras propostas [Hawa 2002, Chu 2002, Sun 2006], o algoritmo proposto leva em consideracao, al’ m do requisito de banda m” nima, o requisito de retardo e I m • ximo do tr- fego de tempo real. Em [Wongthavarawat 2003] e [Chen 2005] esse rea a quisito e considerado, por’ m requer um m’ dulo adicional para oc’ Iculo do deadline 4 34 quisito e considerado, por’ m requer um m • dulo adicional para o c’ Iculo do deadline dos e o a pacotes.

Al’ m disso, esses trabalhos prop- em mecanismos de escalonamento complexos e o de serem implementados, compostos por uma hierarquia de escalonadores tais como Earliest Deadline First (EDF), Deficit Round Robin (DRR), Weighted Fair Queueing (WFQ) e Worst-case Weighted Fair Queueing (W 2 F Q). Entretanto, solucoes simples s- o mais in: a teressantes, pois o escalonador disp- e de pouco tempo para tomar suas decis- es dado que o o o escalonamento e realizado a cada frame; por exemplo, em determinadas onfiguracoes podem haver at’ 400 frames por segundo [‘EEE Std. 2004]. or outro lado, existem trabae lhos [Lee 2005, Yang 2006] que prop- em um mecanismo de escalonamento apenas para o tr• fego de tempo real. O mecanismo proposto neste artigo suporta os quatro n’ veis de a I servico definidos pelo padr- o IEEE 802. 16 e utiliza uma abordagem simples baseada em a tr- s filas de prioridade. e Resultados obtidos a partir de experimentos de simulacao mostram que o mecas- nismo de escalonamento proposto e capaz de atender os requisitos dos diferentes n’ veis ‘ I de servico e alocar recursos de forma justa ara conex- es da mesma classe. 725 O restante do artigo est’ organizado da seguinte forma: a Secao 2 descreve o a padr- o IEEE 802. 16. A Secao 3 apresenta o organizado da seguinte forma: a Secao 2 descreve oa padr- o IEEE 802. 16. A Secao 3 apresenta o mecanismo de escalonamento proposto. As a , – Secoes 4 e 5 apresentam, respectivamente, os experimentos de simulacao realizados e os resultados obtidos. A Secao 6 resume os trabalhos relacionados e a Secao 7 traz as – consideracoes finais. s – 2. O padr- o IEEE 802. 16 a A arquitetura de uma rede que utiliza o padr- o IEEE 802. 6 ossui dois elementos prina cipais: Base Station (BS) e Subscriber Station (SS). A BS faz a comunicacao entre a rede sem fio e a rede n’ cleo, enquanto a SS fornece ao usu’ rio acesso a rede n’ cleo atrav’ sua ue do estabelecimento de conex- es com a BS em uma topologia Ponto-Multiponto (PMP). o O padr- o tamb m permite topologias Mesh (opcional). A principal diferenca entre as toa e . pologias PMP e Mesh est’ no fato de que em uma rede PMP o tr’ fego flui apenas entre aa a BS e as SSs, enquanto que no modo Mesh, o tr- fego pode ser roteado atrav’ s das SSs e a e pode ocorrer diretamente entre duas SSs.

Este trabalho enfoca redes com topologia PMP. A camada f’ sica opera em um formato de frames, os quais s- o subdivididos em a intervalos de tempo chamados slots f’ sicos. Em cada frame h’ um subframe downlink I a e um subframe uplink. O subframe downlink e utilizado pela BS para a transmiss- o de a dados e de informacoes de controle para as SSs. O subframe uplink e compart 6 OF34 transmiss- o de a dados e de informacoes de controle para as SSs. O subframe uplink e compartilhado entre , – todas as SSs para transmiss- es que t” m como destino a BS. o e O padr- o IEEE 802. permite dois modos de acesso ao meio f’ sico: duplexacao a por divis- o de freq ” encia (Frequency Division Duplexing – FDD) e duplexacao por divis- o a um – a de tempo (Time Division Duplexing – TDD). No modo FDD os canais downlink e uplink operam simultaneamente em freq- encias diferentes. No modo TDD os subframes uplink u – e downlink compartilham a mesma freq encia, logo, n- o e poss ‘vel realizar transmiss- a ‘ I o simult- neas nos dois sentidos. Cada frame TDD es u tem um subframe downlink seguido por a um subframe uplink. Neste trabalho, utiliza-se o modo de acesso TDD.

A camada de cesso ao meio (Medium Access Control layer – MAC) e orientada a conex- o. Cada conex- oe identificada por um identificador (Connection Identifier aa ‘ CID) de 16 bits e cada SS tem um endereco MAC unico que a identifica e e utilizado para registra-la e autentica-la na rede. Todo o tr’ fego, incluindo o tr fego n- o orientado a a a a conex- o, e mapeado para uma conex- o. Al’ m do gerenciamento das conex- es, a camada a a e o MAC e respons• vel pelo controle de acesso ao meio e pela alocacao de banda. ‘ a A alocacao de recursos para as SSs e realizada sob demanda.

Quando uma SS – precisa de largura de anda para uma para as SSs e realizada sob demanda. Quando uma SS precisa de largura de banda para uma conex- o, ela envia uma mensagem de requisicao a , – para a BS. Uma requisicao de banda pode ser enviada como um pacote individual em um grant reservado para esse fim, ou pode ser enviada juntamente com um pacote de dados (Piggyback)_ A requisicao de largura de banda pode ser incremental ou agregada. Uma requisicao incremental indica a largura de banda adicional que a SS precisa, enquanto uma requisicao agregada indica a largura de banda total requisitada pela SS. ara a SS as requisicoes de banda empre s- o referentes a uma determinada conex- o, enquanto os a a grants alocados pela BS s- o destinados a uma SS e n- o a uma conex- o em particular. a a a Dessa forma, a SS pode utilizar o grant recebido para uma conex- o diferente daquela a para a qual a requisicao foi feita. A alocacao de grants para o envio de requisicoes de banda, chamada polling, pode se dar de duas formas: 726 • unicast: a SS recebe um grant cujo tamanho e suficiente para o envio de uma requisicao de banda; – • baseado em contencao: utilizado quando n- o h’ banda dispon ‘vel para fazer o s – a a polling unicast de todas as SSs.

Nesse caso, a BS aloca um grant para um grupo de SSs, as quais devem competir pela oportunidade de enviar a mensagem de aloca um grant para um grupo de SSs, as quais devem competir pela oportunidade de enviar a mensagem de requisicao. para reduzir a probabilidade de colis- o, apenas as SSs que necessitam a de banda participam da contencao. Para resolucao da contencao, as estacoes de, – – vem utilizar o algoritmo de backoff exponencial. O tamanho da janela m ‘ nima e da janela m’ xima de contencao e controlado pela BS. , – ‘ A MAC tamb m prov- mecanismos para fornecer QoS aos tr’ fegos uplink downe e a link. O principal mecanismo para a provis- o de QoS consiste em associar os pacotes que a passam pela camada MAC a um fluxo de servico. O fluxo de servico e um servico da . camada MAC que fornece transporte uni-direcional aos pacotes. Durante a fase de estabelecimento da conex- o, esses fluxos de servico s- o criados e ativados pela BS e pela SS. a , a V’ rias secoes das camadas superiores podem operar sobre o mesmo fluxo de servico na a camada MAC caso seus requisitos de QoS sejam os mesmos.

Cada fluxo de servico deve definir seu conjunto de par- metros de QoS, dentre eles etardo m’ Ximo, largura de banda a a m ‘nima e o tipo de servico de escalonamento. I O padr- o especifica quatro servicos de escalonamento. Cada fluxo e associado a a um desses servicos e o escalonador da BS aloca largura de banda para as SSs seguindo o , conjunto de regras definido por eles: • Unsolicited Grant Service (UGS): suporta fluxos seguindo o conjunto de regras definido por eles: • Unsolicited Grant Service (UGS): suporta fluxos de tempo real que geram pacotes de dados com tamanho fixo periodicamente, tal como voz sobre IP. O servico ofe. ece grants com tamanho fixo periodicamente. Fluxos UGS n- o podem utilizar a slots reservados para requisicao de banda. Um fluxo IJGS deve especificar os se,- guintes par* metros de QoS: Maximum Sustained Traffic Rate, Maximum Latency, a Tolerated Jitter e Request/Transmission Policy. • Real-Time Polling Semice (rtPS): suporta fluxos de tempo real que geram pacoa I tes com tamanho vari’ vel periodicamente, como por exemplo v deo MPEG. O sewico oferece slots unicast peri’ dicos para requisicao de largura de banda, os o quais satisfazem as necessidades do fluxo e permitem a SS especificar o tamanho desejado para o grant.

Conex- es rtPS n- o podem utilizar slots de contencao reo a servados para requisicao de banda. Os fluxos rtPS devem fornecer os seguintes par- metros de QoS: Minimum Reserved Traffic Rate, Maximum Sustained Traffic a Rate, Maximum Latency e Request/Transmission Policy. • Non-real-time Polling Service (nrtPS): suporta tr’ fego n- o sens ‘vel ao retardo que a a I requer grants de tamanho vari- vel regularmente, tal como tr’ fego FTP. O servico a a, e similar aquele oferecido pelo rtPS, por’ m o e freq encia e o fluxo pode polling unicast ocorre com menor utilizar slots de contencao 0 DF 34