Slides de Apresentação

Reduzindo os Efeitos do Bufferbloat
sobre Multi-Caminhos em Redes Sem
Fio Heterogêneas
XXXIV Simpósio Brasileiro de Redes de
Computadores e Sistemas Distribuídos
(SBRC2016)
Benevid Felix, Aldri Santos, Michele Nogueira
Universidade Federal do Paraná
Salvador, BA
01/06/2016
Roteiro
• Introdução
• Problema
• Objetivos
• TCP multi-caminhos (MPTCP)
• Controle de fila
• Avaliação da transmissão multi-caminhos
• LIFO-CoDel
• Resultados
• Conclusões
01/06/2016
www.nr2.ufpr.br
2
Introdução
•
Crescente demanda de acesso sem fio a Internet
– Baixa latência e Maior largura de banda
•
Redes heterogêneas sem fio (HetNets)
– Rede celulares, WiFI, e outras
• Dispositivos com múltiplas interfaces (multihomed)
Macro células
Células pequenas e.g.
micro, (ultra-) pico, femto
WiFi AP
Acesso sem fio (Macro Célula)
Acesso sem fio (Pequenas Células)
Acesso sem fio (WiFi)
01/06/2016
www.nr2.ufpr.br
3
Problema
• Como melhorar o desempenho da
transmissão no cenário de HetNets?
– Reduzir latência e aumentar vazão (atender à
demanda!)
• Uso da transmissão de dados multi-caminhos
– Desafios em aberto para HetNets sem fio
• Impacto de caminhos com diferentes características
(atraso, largura de banda, perdas, etc)
• Variação do estado do caminho
– Congestionamentos
01/06/2016
www.nr2.ufpr.br
4
Problema
• Consequências
– Bloqueio da fila de recebimento (HOL Blocking)
– Recebimentos de pacotes fora de ordem
– Degradação do desempenho
Emissor
Receptor
P1,P2,P3
x
P3,P2 (HoL)
2x ACKd
Retransmite
P1
P1,P2,P3
Fonte Imagem: http://chimera.labs.oreilly.com/books/1230000000545/ch02.html#TCP_HOL
01/06/2016
www.nr2.ufpr.br
5
Objetivos
• Avaliar o impacto de caminhos heterogêneos
– Variação do atraso
• Comparação do CC do TCP multi-caminhos no
cenário de HetNets
– Algoritmos Linked Increases (padrão), RTT_Compensator
e Uncoupled
– Impacto do congestionamento (bufferbloat)
– Impacto das perdas de pacotes (Descartes na fila)
• Reduzir a latência e Aumentar a vazão
– Mudança na disciplina de fila
Fonte Imagem: http://chimera.labs.oreilly.com/books/1230000000545/ch02.html#TCP_HOL
01/06/2016
www.nr2.ufpr.br
6
TCP multi-caminhos (MPTCP)
• Extensão ao TCP definido pela RFC 6824
– Funciona com maioria do middleboxes (NAT, Firewall, etc)
• Transmissão de dados concorrente (i.e sub-fluxos)
• Disponível para Linux e iOS7
Aplicação
Aplicação
Socket
Transporte
TCP Multi-caminhos
Rede
Enlace
TCP1
TCP2
TCPn
Física
Fonte Imagem: http://queue.acm.org/detail.cfm?id=2591369
01/06/2016
www.nr2.ufpr.br
7
TCP multi-caminhos (MPTCP)
• Como é estabelecido uma conexão MPTCP?
– Sub-fluxos adicionais (RFC 6182)
eNB
Servidor
EU
1 sub-fluxo por IPsrc,dst
2 IPsrc e 2 IPdst => 2x2 = 4
01/06/2016
WiFi AP
www.nr2.ufpr.br
8
TCP multi-caminhos (MPTCP)
• Controle de congestionamento acoplado
– Janela de recepção compartilhada (RCW)
– Sub-fluxos são interdependentes
• CWND são acopladas
– Objetivos do CC:
• Justo com TCP ao compartilhar gargalos (independente do nº de
sub-fluxos)
• Utilizar eficientemente os caminhos
MPTCP
Regular TCP
Fonte Imagem: http://www.wischik.com/damon/Work/Talks/mptcp-nsdi.pptx
01/06/2016
www.nr2.ufpr.br
9
Controle de fila
• Grandes buffers nos equipamentos de rede (ex.
roteadores)
– Disciplina padrão FIFO
• DropTail: descarta pacotes quando a fila enche
– Atraso adicional
• Tempo de espera na fila
• Fenômeno Bufferbloat (grande atraso e poucas perdas)
• Estratégia: Gerenciamento ativo de filas (AQM)
– CoDel e FQ-CoDel (Nichols e Jacobson [NJ12] )
– Sinalização do congestionamento (descarte)
Fonte: http://queue.acm.org/detail.cfm?id=2209336
01/06/2016
www.nr2.ufpr.br
10
Controle de fila
• CoDel
– Marcação dos tempo de entrada e saída da fila
• Tempo de permanência (𝛿" ) do pacote
𝑑𝑒𝑞"
𝑒𝑛𝑞"
𝜇
𝛿" = 𝑑𝑒𝑞" − 𝑒𝑛𝑞"
– Valor padrão: 𝜏 = 5𝑚𝑠 e 𝜇 ⇒ 𝜆 = 100𝑚𝑠
Fonte Imagem: http://queue.acm.org/detail.cfm?id=2209336
01/06/2016
www.nr2.ufpr.br
11
Controle de fila
• Estado de descarte
– Intervalo 𝜇 é reduzido sucessivamente se 𝛿" persiste
acima de 𝜏
𝛿" < 𝜏
𝛿" < 𝜏
𝛿" > 𝜏
𝛿" > 𝜏
𝛿" < 𝜏
𝛿"
𝜇
𝜇
𝜇
𝜇
𝜇
Tempo
– Flow Queue Codel (FQ-CoDel)
• Separa cada sub-fluxo em uma fila
• Algoritmo de escalonamento DDR (Deficit Round Robin)
Fonte Imagem: http://queue.acm.org/detail.cfm?id=2209336
01/06/2016
www.nr2.ufpr.br
12
Avaliação: transmissão multicaminhos
• Cenário utilizado nas simulações
•
•
•
•
Simulador NS-3
Carga de trabalho – 4Mb
Nó UDP – objetivo de saturar a fila
Variação do atraso no caminho A (1,10,100ms)
1
E
U
enB (LTE)
2
1
1
2
2
3
4
1
AP (WiFi)
C
1 Servidor
Fila
Router
2
1
UDP
MPTCP NS-3: github.com/mkheirkhah/mptcp
01/06/2016
www.nr2.ufpr.br
13
Avaliação: transmissão multicaminhos
• CoDel
– Redução do RTT comparado com DropTail
900
800
700
600
500
400
300
200
700
600
500
400
300
200
100
100
0
0
1
10
100
Atraso no caminho A (ms)
1
10
100
Atraso no caminho A (ms)
RTT DropTail
01/06/2016
WiFi
LTE
800
RTT médio (ms)
RTT médio (ms)
900
WiFi
LTE
RTT CoDel
www.nr2.ufpr.br
14
Avaliação: transmissão multicaminhos
– Descarta mais pacotes na fila
– Degradação do desempenho do MPTCP
• Melhor utilização do Link (~75%) com DropTail
• Tradeoff entre CoDel e DropTail
0.9
CoDel−FIFO
DropTail
0.8
Goodput médio (Mbps)
Descarte médio (pacotes)
125
1
CoDel−FIFO
DropTail
100
75
50
Descartes na fila
25
0.7
0.6
0.5
0.4
Goodput
0.3
0.2
0.1
0
1
01/06/2016
10
Atraso no caminho A (ms)
100
0
www.nr2.ufpr.br
1
10
Atraso no caminho A (ms)
100
15
Avaliação: transmissão multicaminhos
• CC Uncoupled tem desempenho inferior aos
demais
– CC acoplado é mais eficiente
0.09
RTTCompensator
LinkedIncreases
UncoupledTCPs
14
0.08
0.07
0.06
0.05
0.04
0.03
0.02
Tempo de permanência
0.01
0
1
01/06/2016
10
Atraso no caminho A (ms)
100
Tamanho médio (pacotes)
Tempo médio de permanência (ms)
0.1
RTTCompensator
LinkedIncreases
UncoupledTCPs
12
10
8
6
4
Tamanho da fila
2
0
www.nr2.ufpr.br
1
10
Atraso no caminho A (ms)
100
16
LiFO-CoDel
• Mudança de Fila para Pilha
– Priorizar pacotes com menor tempo de
Tempo
permanência
Tamanho da fila
𝜃
Tamanho da fila
entrada
𝜌"
𝜌"
𝜌"
𝜌"
𝜌"
𝜌"
𝜌"
𝛿"
𝜌"
𝜌"
𝜌"
Tempo
www.nr2.ufpr.br
entrada
𝜌"
X
01/06/2016
𝛿"
𝜌"
𝜌"
𝜇
X
17
LiFO-CoDel
• Encaminhar pacotes
descartados pelo FIFOCoDel
𝐷𝑒𝑞 " 𝑝"
𝛿" > 𝜏
n
nreiniciar𝑘, 𝑛=>?@
y
• O parâmetro 𝜽:
𝒕 >= 𝜇
- Pacotes acima do tempo
de permanência
- k contabiliza𝜹𝒊 crescente
- O valor de 𝜽 tende a 2
01/06/2016
www.nr2.ufpr.br
n
encaminhar 𝑝"
y
𝐶𝑎𝑙𝑐𝑢𝑙𝑎𝑟𝑘, 𝜃
𝐷𝑒𝑠𝑐𝑎𝑟𝑡𝑎𝑟 𝑝",
𝑛=>?@GG
y
𝑘 > 𝜃
n
𝜇 = 𝜇 𝑛=>?@
18
Resultados
• Redução do tempo médio de permanência
– Pacotes com menor tempo de permanência
(pilha)
• Redução do tamanho médio da fila
CoDel−FIFO
CoDel−LIFO
0.09
14
0.08
0.07
Tamanho médio (pacotes)
Tempo médio de permanência (ms)
0.1
Tempo de permanência
0.06
0.05
0.04
0.03
0.02
01/06/2016
12
Tamnho da fila
10
8
6
4
2
0.01
0
CoDel−FIFO
CoDel−LIFO
1
10
Atraso no caminho A (ms)
100
0
www.nr2.ufpr.br
1
10
Atraso no caminho A (ms)
100
19
Resultados
• LIFO-CoDel
– Redução do número de descartes
– RTT: muito próximo do FIFO-CoDel (pontos verdes)
900
WiFi
LTE
700
600
125
500
Descarte médio (pacotes)
RTT médio (ms)
800
RTT LIFO-CoDel
400
300
200
100
Descartes na fila
100
75
50
25
0
0
1
1
10
100
Atraso no caminho A (ms)
01/06/2016
CoDel−FIFO
CoDel−LIFO
www.nr2.ufpr.br
10
Atraso no caminho A (ms)
100
20
Resultados
• Melhor Goodput em relação ao CoDel
1
0.9
CoDel−FIFO
CoDel−LIFO
DropTail
Goodput
Goodput médio (Mbps)
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0
01/06/2016
1
10
Atraso no caminho A (ms)
www.nr2.ufpr.br
100
21
Conclusões
• Tradeoff entre RTT e Goodput mais
expressivo
– Cenário com caminhos heterogêneos
– CoDel reduz o atraso, mas degrada o Goodput
• LIFO-CoDel reduz o impacto do CoDel
– Reduz descartes, mantém o RTT e melhora o
Goodput
• Trabalhos Futuros
– Avaliar novos algoritmos de CC
– Cenários mais dinâmicos
01/06/2016
www.nr2.ufpr.br
22
Agradecimentos
www.nr2.ufpr.br
Perguntas?
Fonte Imagem: Google Imagens
Backup – CC do MPTCP
• Janela de congestionamento do MPTCP
– Algoritmo padrão - LIA (Linked Increases)
Tamanho da Janela
Dados
com ACK
Aguardando
ACK
𝛼 1
min
,
𝑊 𝑤"
𝑤" =
𝑤"
2
01/06/2016
Pronto p/
Enviar
Dados não
Enviados
incremento
𝛼=
decremento
\]
XYZ(
)
^__] `
𝑊×(∑ \ /^__ )`
]
] ]
24