Algoritmos de Scheduling de
Pacotes
João Reis e Valdemar Monteiro
MOTION
mobile system communications group
João Reis, Valdemar Monteiro
Covilhã, 30 de Junho de 2005
Apresentação
• Motivação
• RRM desenvolvido no âmbito do projecto
MATRICE
– Descrição do sistema
– Algoritmos de sheduling
– Resultados demosntrativos
• Geração de tráfego
– Baseados em modelos de 3GPP
– Interface IP – Desenvolvido para a interface de
simuladores de sistemas com rede IP real.
MOTION
mobile system communications group
João Reis, Valdemar Monteiro
Covilhã, 30 de Junho de 2005
2
Motivação
• As futuras redes de comunicações sem fios perspectivam oferecer aos
utilizadores uma grande variedade de serviços multimédia,
caracterizados por requisitos variáveis de largura de banda (taxa de
dados).
• As características das ligações rádio são dinâmicas e dependentes da
localização, e portanto podem-se ter ligações rádio para cada utilizador
com diferentes propriedades (SINR, …)
• Esquemas adaptativos de scheduling de pacotes são cruciais para gerir
o acesso dos utilizadores aos recursos disponíveis, de acordo com
determinadas politicas, que consideram, por exemplo, características de
tráfego, condições de canal de cada utilizador, …
• Contudo, no sentido de tirar partido das vantagens da adaptabilidade,
é necessária uma concepção cross-layer da arquitectura de rede de um
sistema de comunicações.
MOTION
mobile system communications group
João Reis, Valdemar Monteiro
Covilhã, 30 de Junho de 2005
3
RRM
• Âmbito do projecto do IST MATRICE
• RRM para sistemas Pós-3G baseados em MCCDMA
• Inclui
– Link adaptation
– H-ARQ com Chase combining
– Scheduling
• Os trabalhos desenvolvidos no IT incidiram no scheduler
– RRM com modelo aproximado ao HSDPA do UMTS
MOTION
mobile system communications group
João Reis, Valdemar Monteiro
Covilhã, 30 de Junho de 2005
4
Modelo de sistema
Scheduler
•
•
•
L tipo de fontes de informação
Tráfego de fontes do tipo i agregado
na fila Qai correspondendo à
agragação do tráfego gerado pelas
Ni fontes de tráfego idênticos e
independentes
Conversão de pacotes em blocos
rádio  Filas (Qi) com
características ditadas pela operação
de agragação e conversão de
formato
– Algumas simplificações levadas em
conta na implementação do sistema
MOTION
mobile system communications group
Fonte 1
tipo1
Qa1
Agr
eg.
Pacote
 bloco
rádio
Q1
Buffer
Fonte
N1 tipo1
Algoritmo
de sched.
Fonte 1
tipo L
QaL
Agr
eg.
Fonte
NL tipo
L
QL
Pacote
 bloco
rádio
Buffer
João Reis, Valdemar Monteiro
Covilhã, 30 de Junho de 2005
5
Modelo de sistema
• Simplificações
– Buffers de tamanho infinito
– Segmentação dos pacotes não altera a
estatística das filas Qi  Pacotes com
tamanho original fixo
MOTION
mobile system communications group
João Reis, Valdemar Monteiro
Covilhã, 30 de Junho de 2005
6
Modelo de sistema
• Caracterização do pacote
Atributos do pacte
Tipo (classe de serviço)
destino
Instante de chegada
Deadline (toa+max allowable delay)
# de tentativas de transmição
Requisitos de robustez na transmissão (BER / FER)
• O pacote é caracterizado de acordo com o estado pelo sheduler, usando
– Atributos do pacote
– Informação do canal
Estado do pacote
Tipo (classe de serviço)
Robustez esperada na Tx
Time out
# de transmições efectuadas
MOTION
mobile system communications group
João Reis, Valdemar Monteiro
Covilhã, 30 de Junho de 2005
7
Algoritmo de scheduling
• Prioridade de cada calculada de acordo com o estado.
Pacotes com prioridade mais elevada serão servidos
primeiro
• Prioridade=F(tipo, time-out, requisitos de robustez, #
tentaivas de transmissão)
– Inclusão do # tentativas de transmissãoão é incluido pq o Chase
combining é aplicada
– Functão implementada
Priority  w1(type, time out)  w2 (# attemptedtransmissions, type)w3 (rel. exp., type)
•
•
•
•
w1: funcão que decresce com o time-out
w2: função decresce com o número de tentativas de transmissão
w3: função ternária para a robustez de transmissão
Em caso de igualdade são ordenados pelo time-out, e depois pelo
SIR
MOTION
mobile system communications group
João Reis, Valdemar Monteiro
Covilhã, 30 de Junho de 2005
8
Resultados demosntrativos
Algoritmo comp. com max(C/I)
Cenário
• Modelo de canal urbano, células de 300m,
• Tramas de 10 ms
• Tráfego: Voz e Web baseados em modelos da
3GPP
– Voz: On-Off distribuído exponencialmente, com médias
de 1 e 1.35 sec.; ritmo de 11.04 kbps no período on
– Web: Tempo entre chamadas distribuído
geométricamente com média 5sec.; tamanho de
chamadas de acordo com a distribuição de Pareto com
média 12 kBytes, e pico de ritmo de dados de 512 kbps
• Simulações de downlink
MOTION
mobile system communications group
João Reis, Valdemar Monteiro
Covilhã, 30 de Junho de 2005
9
Resultados demonstrativos
Voz
Scheduling de
prioridade
MOTION
mobile system communications group
Scheduling
Max(C/I)
João Reis, Valdemar Monteiro
Covilhã, 30 de Junho de 2005
10
Resultados demonstrativos
Web
Scheduling de
prioridade
MOTION
mobile system communications group
Scheduling
Max(C/I)
João Reis, Valdemar Monteiro
Covilhã, 30 de Junho de 2005
11
Modelo do Sistema
• Uma entidade central de scheduling na estação base
controla as transmissões em downlink de um sistema de
comunicações acedido por múltiplos utilizadores.
• A entidade de scheduling decide que pacotes devem ser
transmitidos no inicio de cada trama rádio.
Traffic Queues
BTS
User 1
mobile system communications group
h1(t)
User 2
User 2
User n
MOTION
User 1
Packet
Scheduler
h2(t)
Transmit
Unit
SINR
QoS Constraints
User n
hn(t)
Feedback Link
João Reis, Valdemar Monteiro
Covilhã, 30 de Junho de 2005
12
Algoritmos de Scheduling I
• Algoritmo conjunto de scheduling e adaptação de modulação
– A politica para determinar os pacotes a transmitir leva em consideração a
formatação dos dados (modulação), permitida por cada utilizador.
– A selecção da modulação permitida é realizada de acordo com a qualidade
de canal e o tamanho da fila de tráfego de cada utilizador.
Algoritmo de
Scheduling
Estado do Canal
Pacotes
Selecionados
Modulação
selecionada
Selecção de
Modulação
MOTION
mobile system communications group
João Reis, Valdemar Monteiro
Covilhã, 30 de Junho de 2005
13
Resultados Experimentais
Ilustrativos
• Função de distribuição cumulativa (CDF) para o
atraso na entrega dos pacotes
O algoritmo “Adaptação de
modulação” ultrapassa,
significativamente, o
desempenho do algoritmo
designado por “máximo
throughput”, em termos do atraso
máximo de pacote.
1
0.9
0.8
0.7
cdf
0.6
0.5
0.4
0.3
Maxino Throughput
Adatação de Modulação
0.2
0.1
50
100
150
200
250
Atraso (time-slots)
MOTION
mobile system communications group
João Reis, Valdemar Monteiro
Covilhã, 30 de Junho de 2005
14
Algoritmos de Scheduling II
• Algoritmo conjunto de scheduling e beamforming
– Fazer o scheduling dos pacotes de acordo com uma politica conjunta de
prioridade e beamforming.
– Passo 1: Função de Prioridade
• Nesta fase os pacotes existentes nas filas de tráfego são ordenados com base
numa função de prioridade envolvendo parâmetros da camada física e
parâmetros de qualidade de serviço ( QoS).
– Passo 2: Mapeamento Espacial
• Nesta fase, o objectivo passa por mapear os pacotes num array , em que as
linhas representam os “códigos” e as colunas representam a dimensão espacial.
• Na tabela cada linha corresponde a um código, e portanto todos os utilizadores
na mesma linha usam o mesmo código. Isto implica, que dois utilizadores que
estejam na mesma linha da tabela, necessitem de estar espacialmente
separados, isto é, a diferença entre os seus ângulos deva ser no mínimo θmin
MOTION
mobile system communications group
João Reis, Valdemar Monteiro
Covilhã, 30 de Junho de 2005
15
Algoritmos de Scheduling III
•
Demonstração do Algoritmo
MS6
MS1
Beam1
Beam2
Code1
MS1
MS3
Code2
MS5
MS4
Coden
MS6
MS2
W1,2(MS1)
MS4
W1,2(MS2)
1,3
Array
Processing
W1,2(MS3)
W1,2(MS4)
W1,2(MS5)
MS2
W1,2(MS6)
BS
1,3   min
 2,6   min
MS3
 4,5   min
MOTION
mobile system communications group
João Reis, Valdemar Monteiro
Covilhã, 30 de Junho de 2005
16
Interface IP - Conceito
•
•
•
•
Interface de simuladores de sistema com a rede IP
Interface através de ficheiros de captura
Tráfego baseado no IP v6
Parâmetros extraídos dos pacotes capturados:
– Endereço da fonte
• Inteiro de 0 a núm. max de addresses capturados
– Endereço de destino
• Associated ao Id do endereço
– Instante de chegada (em µs)
– comprimento (bytes)
– Classe de serviço – DSCP (de 0 a 255)
MOTION
mobile system communications group
João Reis, Valdemar Monteiro
Covilhã, 30 de Junho de 2005
17
Interface IP - Interfaces
• Entrada: Ficheiro de captura
• Saídas:
– Ficheiros de texto
• Um ficheiro por parâmetro
• Cada linha do ficheiro corresponde a uma stream
individual
– Objecto de tráfego do simulador
• stream de pacotes do simulador são criados para
serem associados a cada fonte de tráfego
MOTION
mobile system communications group
João Reis, Valdemar Monteiro
Covilhã, 30 de Junho de 2005
18
Interface IP
Interfaces do múdulo
Configuration
Capture
File
I
N
Packet
Read
Unit
Packet
Parameter
extractors
OUT2
File
MOTION
mobile system communications group
Load stream
to Traffic
Manager
Parameters
extraction to file
João Reis, Valdemar Monteiro
Covilhã, 30 de Junho de 2005
19
Interface Ip
Ficheiros de saída
• Ficheiro de texto com um parâmetro individual
– Organizado em streams
• Stream corresponde à combinação de: endereço da fonte, endereço de
destino e Flow Id
– Alterações não muito significativas se outros parâmetros forem
necessários (indexação manter-se-á)
Packet
Stream
Packet
s
MOTION
mobile system communications group
Packet
s
Packet
s
João Reis, Valdemar Monteiro
Covilhã, 30 de Junho de 2005
20