Algoritmo de Escalonamento DRR com
Quantum Adaptativo para Redes IEEE
802.16j
Einar César Santos
ORIENTADOR: Paulo Roberto Guardieiro, Dr.
Introdução e Motivação
- Crescente demanda por redes banda larga sem fio;
- Redes WiMAX (4G) possuem custo relativamente baixo;
- Área de cobertura extensa;
Introdução e Motivação
- Padrão IEEE 802.16 não especifica algoritmos de
escalonamento;
- Poucas propostas de escalonamento relevantes
existentes para IEEE 802.16j.
Descrição do Problema
- Recursos alocados não são quantificados
adequadamente;
- Necessidade de melhor aproveitamento de informações
da camada física;
- Utilização eficaz dos recursos disponíveis;
Solução Proposta
- Mecanismo dinâmico de alocação e quantificação de
recursos;
- Mecanismo mais ágil e menos rígido de controle de
congestionamento;
- Mecanismo de informação sobre estado da conexão.
Roteiro da Apresentação
- Histórico e fundamentos do IEEE 802.16j;
- Algoritmos de escalonamento e obtenção de QoS;
- Detalhamento da solução proposta;
- Avaliação da solução proposta;
- Conclusões gerais.
Histórico do IEEE 802.16
- WiMAX foi criado em 2001 e publicado em 2002;
- Versão IEEE 802.16a (2003) operava em frequências de 2
a 11 GHz NLOS;
- IEEE 802.16d (2004) tinha alcance de até 50 Km com
taxas de até 70 Mbps
- IEEE 802.16e (2006) introduziu mobilidade;
- IEEE 802.16j (2009) introduziu o conceito Multihop Relay
em substituição ao modo mesh;
- IEEE 802.16m última versão recente publicada.
Topologia e Modos de Operação
- Modo Transparent Relay (T-RS);
- Modo Non-Transparent Relay (NT-RS).
Implantação da(s) RS(s)
- Fixed Relay Station (F-RS);
- Nomadic Relay Station (N-RS);
- Mobile Relay Station (M-RS).
Arquitetura – Camada PHY
- Padrão define camadas PHY e MAC correspondentes às
camadas 1 e 2 do modelo de referência OSI/ISO;
- PHY utiliza modulação OFDMA nos modos TDD ou FDD;
- Quadro é dividido em Downlink (DL) e Uplink (UL);
- Subdivisão DL e UL em zonas access e relay.
Estrutura do Quadro – Modo NT-RS
Cabeçalho de Controle de Quadro
FCH – Frame Control Header
Arquitetura – Camada MAC
- Dividida em três subcamadas:
* Convergence Sublayer (CS);
* Common Part Sublayer (CPS);
* Security Sublayer (SS).
- CS classifica os quadros e mapeia-os em Service Data
Units (SDU);
- CPS realiza alocação de recursos e rotinas de entrada
de dispositivos à rede;
- SS implementa criptografia e autenticação de acesso.
Arquitetura – Camada MAC
Encaminhamento de Quadros
- Tunelamento;
- Connection Identifier (CID);
- Tunelamento utiliza campo T-CID no cabeçalho;
- Campo MT-CID utilizado para gerenciamento, possui
informações para aplicação de AMC e obtenção de QoS;
- CID utilizado em esquema onde BS e RS gerenciam
seus próprios links.
Esquemas de Retransmissão
- Amplificação e Encaminhamento:
* Simples;
* Baixo atraso.
- Decodificação e Encaminhamento Seletivo:
* Evita propagação de erro;
* Requer maiores taxas de transmissão.
- Demodulação e Encaminhamento:
* Adequado para situações com dois ou mais tipos de
modulação.
Esquemas de Pareamento
- Centralizado:
* Responsabilidade total da BS.
- Distribuído:
* Decisões de pareamento realizadas isoladamente.
- Aleatório:
* Nenhum critério considerado.
- Oportunista:
* “Melhor” estação superordenada escolhida.
Controle de Tráfego e QoS
* Conexões são classificadas em 5 classes de serviço:
- UGS: voz sem supressão de silêncio (VoIP);
- rtPS: taxa de dados variável (MPEG);
- ertPS: voz com supressão de silêncio;
- nrtPS: tráfego com largura de banda mínima
reservada (FTP);
- BE: tráfego com baixa prioridade.
* CS classifica conexão e associa a um Service Flow (SF);
* SFs são escalonados de acordo com regras internas.
Modos de Escalonamento e CAC
- Escalonamento e roteamento centralizados
(T-RS e NT-RS);
- Escalonamento centralizado e roteamento distribuído
(NT-RS);
- Escalonamento e roteamento distribuídos (NT-RS);
- Escalonamento e roteamento híbridos (NT-RS);
- Connection Admission Control (CAC): Mecanismo
auxilia o escalonamento, aceitando ou rejeitando
conexões.
Alocação de Largura de Banda e
Mecanismos de Correção
- Requisição de largura de banda (BW-REQ) incremental
ou agregada;
- Automatic Repeat Request (ARQ);
- Hybrid Automatic Repeat Request (HARQ);
* End-to-End;
Alocação de Largura de Banda
Modo de operação ARQ
* Two-links;
* Hop-by-Hop;
Forma de Alocação
End-to-end Two Links Hop-by-hop Incremental ou Agregada
T-RS Centralizado
NT-RS Centralizado
NT-RS Distribuído
X
-
-
Incremental/Agregada
X
X
X
Incremental
-
X
X
Incremental
Handover ou Handoff
- Hard Handover (HHO):
* MS conecta com apenas uma estação superordenada por
vez.
- Macro Diversity Handover (MDHO):
* MS mantém lista de estações superordenadas;
* Active Set.
- Fast Base Station Switching (FBSS):
* MS mantém Active Set e CID válido para estações
superordenadas;
* MS conecta apenas com estação âncora;
* Dispensa sinalização de handover.
Critérios para Seleção de
Escalonadores
- Simplicidade;
- Utilização eficiente do link;
- Degradação de serviço;
- Escalabilidade;
- Justiça;
- Economia de Energia;
- Proteção contra fluxos indesejados;
- Desacoplamento entre atraso e largura de banda;
- Design Cross-Layer;
- Reuso do espectro de frequência;
- Roteamento;
- Estratégia de requisição de largura de banda.
Parâmetros para Obtenção de QoS
- Taxa máxima de tráfego sustentada;
- Taxa mínima de tráfego reservada;
- Latência Máxima;
- Jitter Tolerado;
- Prioridade de Tráfego;
- Política de Requisição e Transmissão.
Critérios para Seleção de
Escalonadores
- Simplicidade;
- Utilização eficiente do link;
- Degradação de serviço;
- Escalabilidade;
- Justiça;
- Economia de Energia;
- Proteção contra fluxos indesejados;
- Desacoplamento entre atraso e largura de banda;
- Design Cross-Layer;
- Reuso do espectro de frequência;
- Roteamento;
- Estratégia de requisição de largura de banda.
Tipos de Escalonadores
- Wireline:
* Generalized Processor Sharing – GPS;
* Virtual Clock – VC;
* Weighted Round Robin – WRR;
* Fair Queuing – FQ;
* Stochastic Fair Queuing – SFQ;
* Deficit Round Robin – DRR;
* Weighted Fair Queuing – WFQ;
* Worst-Case Fair Weighted Fair Queuing – WF²Q;
* Self-Clocked Fair Queuing – SCFQ;
* Earliest Deadline First – EDF.
- Wireless:
* Idealized Wireless Fair Queuing – IWFQ;
* Channel-Independent Fair Queuing – CIFQ.
Estratégias de Escalonamento
- Estratégias Homogêneas;
- Estratégias Heterogêneas ou Híbridas;
- Estratégias Diversas:
* Abordagem Cross-Layer;
* Abordagem por Informações de Comprimento de Filas;
* Abordagem por Diversidade de Múltiplos Usuários;
* Abordagens Oportunistas e Adaptativas.
Framework de Escalonamento
Descrição do Problema
- Algoritmo DRR adotado em [1] possui quantum fixo,
sendo inflexível a variações;
- Propostas DRR com quantum adaptativo não
consideram MTU como parâmetro [2];
- Ausência de mecanismos que combinem:
* Escalonamento;
* Equilíbrio do comprimento médio das filas dos buffers de
saída;
* Máxima utilização de recursos disponíveis;
* Variação na quantidade de dados alocados.
Solução Proposta – Estado da Conexão
- RS informa estado de congestionamento. Adaptado de
[1];
- Informação auxilia escalonamento downlink na BS;
- Estado obtido em função do comprimento médio da fila
do buffer de saída:
Solução Proposta – Estado da Conexão
- Estados:
* NORMAL (00);
* PRÉ-CONGESTIONAMENTO (01);
* CONGESTIONAMENTO (10);
* DESCARTE (11).
Algoritmo de Gerenciamento de Filas
- Implementação de algoritmo de gerenciamento de filas
na camada MAC (CPS);
- Algoritmo baseado no ARED;
- Algoritmo realiza descartes aleatórios, de acordo com
probabilidade calculada em função do nível de ocupação
das filas;
- Probabilidade descarte define agressividade do
algoritmo.
Escalonamento DRR c/ Quantum
Adaptativo
Cálculo do Quantum
MTU
q orig =
3
2 q orig
Qi=
γ Ci
∀ C i ϵ ℤ : C i> 0
0,04≤ γ≤ 0,2
[1] Congestion Aware - Chang
[2] DRR adaptativo – Sayenko