Embed Size (px)
Citation preview
Minimização da Latência no Posicionamento de Funções
em Cloud RANs
Jean Lucas de Lima e Rodrigo de Souza Couto
Pesquisa financiada pela FAPERJ, CNPq, CAPES e FAPESP
Radio Access Network (RAN)
• Infraestrutura para prover conectividade a dispositivos móveis em uma rede celular
• Tradicionalmente, todas as tarefas de transmissão e recepção são centralizadas
2
Separação entre recepção e processamento
3
• Unidade de rádio
– RRH (Remote Radio Head)
– Processamento digital de sinais
– Interfaces com o meio de transmissão
• Unidade de banda base
– BBU (Baseband unit)
– Processa o sinal de banda base
– Tarefas de mais alto nível
• Correção de Erros, MAC, etc.
Custo da RAN
• RAN possui custo elevado
– Estações (Base Stations – BSs) muitas vezes são dimensionadas para o pico
• Equipamentos permanecem ociosos por longo períodos
• Exemplo: Regiões próximas a estádios de futebol
– Alta utilização em dias de evento
– Baixa utilização em dias normais
4
Cloud RAN (C-RAN)
• Centralização das BBUs
– Utilização sob demanda
5Fonte: Adaptado de (CHECKO et al., 2015)
Vantagens da C-RAN
• Melhor gerenciamento e manutenção
– Implantação de novas células de modo mais simples
• Redução de custos
– Consumo de energia
– Diminuição da quantidade de hardware
• Escalabilidade
– É possível aumentar a capacidade da rede apenas adicionando hardware na infraestrutura centralizada
• Herança de diversas vantagens da computação em nuvem6
Desvantagem da C-RAN
• Latência entre RRH e BBU
– Tradicionalmente eram instaladas em um mesmo local
– Em C-RANs, alguns quilômetros podem distanciar as duas entidades
• Exigência de enlaces bem provisionados entre RRH e BBU
7
C-RAN Hierárquica
• Utilização de nuvens intermediárias para hospedar BBUs
– Similar ao conceito de computação em névoa
– Também chamada de Fog RAN
8
n0 n1
n4
n2 n3
n5
n7n6
BS0 BS1 BS2 BS3 BS4 BS5 BS6 BS7
Central
Regional
Borda
C-RAN Hierárquica
• Utiliza nuvens borda quando possível
– Se capacidade não for suficiente, utiliza nuvens centrais
• Melhora da latência entre RRH e BBU
9
n0 n1
n4
n2 n3
n5
n7n6
BS0 BS1 BS2 BS3 BS4 BS5 BS6 BS7
Central
Regional
Borda
C-RAN Hierárquica e NFV
• Funções das BBUs podem ser divididas em diversas funções virtuais
– VNFs (Virtualized Network Functions)
• Orquestradores de NFV (Network Functions Virtualization) podem alocar VNFs pela infraestrutura
10
n0 n1
n2
n7n3
BS0 BS1 BS2 BS3
BS3
BS3
BS3
BS3
BS3
BS2
BS2
BS2
BS1
BS1
BS1
BS0
BS0
BS0
BS0
BS0
BS1
BS1
BS2
BS2
Função 4
Função 3
Função 2
Função 1
Função 0
Problema abordado neste trabalho
• Escolher, para cada BS, a localização (nó da nuvem) de cada uma de suas funções
– Algoritmo de posicionamento de VNFs
– Otimização de uma função objetivo
• Considera a latência da rede
• Relacionado ao tema de Gerenciamento e Orquestração (Management and Orchestration - MANO) de NFV
11
Trabalhos Relacionados
• Na área de NFV, diversos trabalhos propõem algoritmos para posicionar funções virtuais (VNFs)
– Topologia da rede geralmente é complexa
• Em comparação, C-RANs utilizam muitas vezes topologia em árvore
– Simplicidade das topologias de C-RAN pode possibilitar algoritmos mais simples de posicionamento
• Literatura sobre posicionamento em C-RAN ainda é escassa
• Este trabalho se baseia na proposta do Maestro12
Maestro
• Posicionamento de VNFs em nuvens hierárquicas
• Principal objetivo é minimizar a taxa de dados transmitida entre as nuvens da hierarquia
– Também prioriza nuvens de borda para redução de latência
• Mas, em termos de latência, não diferencia nuvens regionais de nuvens centrais
• Formulação MILP (Mixed-Integer Linear Programming)
13
Dalla-Costa, A. G., Schimuneck, M. A., Wickboldt, J. A., Both, C. B., Gaspary, L. P.
e Granville, L. Z. (2017). NFV em redes 5G: Avaliando o desempenho de
composição de funçõeses virtualizadas via Maestro. SBRC 2017
Diferenças deste trabalhopara o Maestro
• Objetivo é minimizar latência na rede
– Muito importante em C-RAN
– Considera que enlaces da nuvem são bem provisionados
• Não minimiza banda do enlace
• Proposta de heurísticas para solução do problema
– Solução do MILP pode não escalar
14
Problema de otimização
• Formulação MILP
• Função Objetivo
– Minimizar a latência média da rede
• Parâmetros
– Latência entre as estações (BSs) e os nós da nuvem
– Capacidade dos nós da nuvem
– Capacidade dos enlaces
15
16
n0 n1
n2
n7n3
BS0 BS1 BS2 BS3
Central
Regional
Borda
10ms
10ms 10ms 10ms 10ms
10ms10ms
BS3
BS3
BS3
BS3
BS3
BS2
BS2
BS2
BS1
BS1
BS1
BS0
BS0
BS0
BS0
BS0
BS1
BS1
BS2
BS2
Função 4
Função 3
Função 2
Função 1
Função 0
Função ObjetivoLatência média
Para cada BS, considera-se a latência de sua função mais distante
20 ms
30 ms
30 ms
30 ms
27,5 ms
Restrições
• Cada função de uma estação só pode ser posicionada em um nó da nuvem
• Consumo das funções em um nó da nuvem não podem exceder sua capacidade
– Capacidade de hospedagem
• Número de funções suportadas
– Capacidade de banda
• Enlace com a nuvem imediatamente superior
17
Restrições
• Cálculo da latência percebida por cada BS
– Latência da função mais distante possível
• Limite máximo de latência permitido pelas BSs
18
Solução ótima do Problema
• Realizada pelo otimizador GLPK
– Atualmente, após publicação do trabalho, utiliza-se o IBM CPLEX
• Não escala para redes grandes
– GLPK já apresenta problemas para redes com mais de 8 BSs
– CPLEX executa para 16 BSs, mas possui problemas a partir desse número
19
Solução ótima do Problema
• Realizada pelo otimizador GLPK
– Atualmente, após publicação do trabalho, utiliza-se o IBM CPLEX
• Não escala para redes grandes
– GLPK já apresenta problemas para redes com mais de 8 BSs
– CPLEX executa para 16 BSs, mas possui problemas a partir desse número
20
Necessidade de heurísticas para solucionar o problema
Heurísticas gulosaspara solução aproximativa
• Algoritmo 1
– Tentar posicionar todas as funções de uma BS na borda
• Se não for possível, tentar no nó regional e, posteriormente, no central
– Realizar procedimento para todas as BSs
• Algoritmo 2
– Ordenar pares de BS e nós da nuvem
– Priorizar, na ordem de alocação, pares com latências mais baixas
21
22
n0 n1
n2
n7n3
BS0 BS1 BS2 BS3
Central
Regional
Borda
10ms
10ms 10ms 10ms 10ms
10ms10ms
Função 4
Função 3
Função 2
Função 1
Função 0
Algoritmo 1
23
n0 n1
n2
n7n3
BS0 BS1 BS2 BS3
Central
Regional
Borda
10ms
10ms 10ms 10ms 10ms
10ms10ms
BS0
Função 4
Função 3
Função 2
Função 1
Função 0
Algoritmo 1
24
n0 n1
n2
n7n3
BS0 BS1 BS2 BS3
Central
Regional
Borda
10ms
10ms 10ms 10ms 10ms
10ms10ms
BS0
BS0
Função 4
Função 3
Função 2
Função 1
Função 0
Algoritmo 1
25
n0 n1
n2
n7n3
BS0 BS1 BS2 BS3
Central
Regional
Borda
10ms
10ms 10ms 10ms 10ms
10ms10msBS0
BS0
BS0
Função 4
Função 3
Função 2
Função 1
Função 0
Algoritmo 1
26
n0 n1
n2
n7n3
BS0 BS1 BS2 BS3
Central
Regional
Borda
10ms
10ms 10ms 10ms 10ms
10ms10ms
BS0
BS0
BS0
BS0
Função 4
Função 3
Função 2
Função 1
Função 0
Algoritmo 1
27
n0 n1
n2
n7n3
BS0 BS1 BS2 BS3
Central
Regional
Borda
10ms
10ms 10ms 10ms 10ms
10ms10ms
BS0
BS0
BS0
BS0
BS0
Função 4
Função 3
Função 2
Função 1
Função 0
Algoritmo 1
28
n0 n1
n2
n7n3
BS0 BS1 BS2 BS3
Central
Regional
Borda
10ms
10ms 10ms 10ms 10ms
10ms10ms
BS0
BS0
BS0
BS0
BS0
BS1
Função 4
Função 3
Função 2
Função 1
Função 0
Algoritmo 1
29
n0 n1
n2
n7n3
BS0 BS1 BS2 BS3
Central
Regional
Borda
10ms
10ms 10ms 10ms 10ms
10ms10ms
BS0
BS0
BS0
BS0
BS0
BS1
BS1
Função 4
Função 3
Função 2
Função 1
Função 0
Algoritmo 1
30
n0 n1
n2
n7n3
BS0 BS1 BS2 BS3
Central
Regional
Borda
10ms
10ms 10ms 10ms 10ms
10ms10ms
BS1
BS0
BS0
BS0
BS0
BS0
BS1
BS1
Função 4
Função 3
Função 2
Função 1
Função 0
Algoritmo 1
31
n0 n1
n2
n7n3
BS0 BS1 BS2 BS3
Central
Regional
Borda
10ms
10ms 10ms 10ms 10ms
10ms10ms
BS1
BS1
BS0
BS0
BS0
BS0
BS0
BS1
BS1
Função 4
Função 3
Função 2
Função 1
Função 0
Algoritmo 1
32
n0 n1
n2
n7n3
BS0 BS1 BS2 BS3
Central
Regional
Borda
10ms
10ms 10ms 10ms 10ms
10ms10ms
BS1
BS1
BS1
BS0
BS0
BS0
BS0
BS0
BS1
BS1
Função 4
Função 3
Função 2
Função 1
Função 0
Algoritmo 1
33
n0 n1
n2
n7n3
BS0 BS1 BS2 BS3
Central
Regional
Borda
10ms
10ms 10ms 10ms 10ms
10ms10ms
BS3
BS3
BS3
BS3
BS3
BS2
BS2
BS2
BS1
BS1
BS1
BS0
BS0
BS0
BS0
BS0
BS1
BS1
BS2
BS2
Função 4
Função 3
Função 2
Função 1
Função 0
Algoritmo 1
Possíveis problemas do Algoritmo 1
• Posicionamento funções de BSs com alta latência
– Exaustão de recursos que poderiam ser utilizados por uma nuvem de melhor latência
34
n0 n1
n4
n2 n3
n5
n7n6
BS0 BS1 BS2 BS3 BS4 BS5 BS6 BS7
10ms50ms
50ms
50ms
50ms
50ms 50ms 50ms
10ms
10ms 10ms
10ms10ms
10ms
Algoritmo 2
• Posiciona as funções em ordem crescente da latência entre uma BS e sua respectiva nuvem
– Ordenam-se, pela latência, todos os possíveis pares de BSs-com nós da Nuvem
– Posicionam-se as funções na ordem desses pares
– Privilegiam-se BSs que possuem menores latências
35
36
n0 n1
n4
n2 n3
n5
n7n6
BS0 BS1 BS2 BS3 BS4 BS5 BS6 BS7
10ms50ms
50ms
50ms
50ms
50ms 50ms 50ms
10ms
10ms 10ms
10ms10ms
10ms
Função 4
Função 3
Função 2
Função 1
Função 0
Algoritmo 2
37
n0 n1
n4
n2 n3
n5
n7n6
BS0 BS1 BS2 BS3 BS4 BS5 BS6 BS7
10ms50ms
50ms
50ms
50ms
50ms 50ms 50ms
10ms
10ms 10ms
10ms10ms
10ms
Função 4
Função 3
Função 2
Função 1
Função 0
BS1
Algoritmo 2
38
n0 n1
n4
n2 n3
n5
n7n6
BS0 BS1 BS2 BS3 BS4 BS5 BS6 BS7
10ms50ms
50ms
50ms
50ms
50ms 50ms 50ms
10ms
10ms 10ms
10ms10ms
10ms
Função 4
Função 3
Função 2
Função 1
Função 0
BS1
BS1
Algoritmo 2
39
n0 n1
n4
n2 n3
n5
n7n6
BS0 BS1 BS2 BS3 BS4 BS5 BS6 BS7
10ms50ms
50ms
50ms
50ms
50ms 50ms 50ms
10ms
10ms 10ms
10ms10ms
10ms
Função 4
Função 3
Função 2
Função 1
Função 0
BS1
BS1
BS1
Algoritmo 2
40
n0 n1
n4
n2 n3
n5
n7n6
BS0 BS1 BS2 BS3 BS4 BS5 BS6 BS7
10ms50ms
50ms
50ms
50ms
50ms 50ms 50ms
10ms
10ms 10ms
10ms10ms
10ms
Função 4
Função 3
Função 2
Função 1
Função 0
BS1
BS1
BS1
BS1
Algoritmo 2
41
n0 n1
n4
n2 n3
n5
n7n6
BS0 BS1 BS2 BS3 BS4 BS5 BS6 BS7
10ms50ms
50ms
50ms
50ms
50ms 50ms 50ms
10ms
10ms 10ms
10ms10ms
10ms
Função 4
Função 3
Função 2
Função 1
Função 0
BS1
BS1
BS1
BS1
BS1
Algoritmo 2
42
n0 n1
n4
n2 n3
n5
n7n6
BS0 BS1 BS2 BS3 BS4 BS5 BS6 BS7
10ms50ms
50ms
50ms
50ms
50ms 50ms 50ms
10ms
10ms 10ms
10ms10ms
10ms
Função 4
Função 3
Função 2
Função 1
Função 0
BS1
BS1
BS1
BS1
BS1 BS3
Algoritmo 2
43
n0 n1
n4
n2 n3
n5
n7n6
BS0 BS1 BS2 BS3 BS4 BS5 BS6 BS7
10ms50ms
50ms
50ms
50ms
50ms 50ms 50ms
10ms
10ms 10ms
10ms10ms
10ms
Função 4
Função 3
Função 2
Função 1
Função 0
BS1
BS1
BS1
BS1
BS1BS3
BS3
Algoritmo 2
44
n0 n1
n4
n2 n3
n5
n7n6
BS0 BS1 BS2 BS3 BS4 BS5 BS6 BS7
10ms50ms
50ms
50ms
50ms
50ms 50ms 50ms
10ms
10ms 10ms
10ms10ms
10ms
Função 4
Função 3
Função 2
Função 1
Função 0
BS1
BS1
BS1
BS1
BS1
BS3
BS3
BS3
Algoritmo 2
45
n0 n1
n4
n2 n3
n5
n7n6
BS0 BS1 BS2 BS3 BS4 BS5 BS6 BS7
10ms50ms
50ms
50ms
50ms
50ms 50ms 50ms
10ms
10ms 10ms
10ms10ms
10ms
Função 4
Função 3
Função 2
Função 1
Função 0
BS1
BS1
BS1
BS1
BS1
BS3
BS3
BS3
BS3
Algoritmo 2
46
n0 n1
n4
n2 n3
n5
n7n6
BS0 BS1 BS2 BS3 BS4 BS5 BS6 BS7
10ms50ms
50ms
50ms
50ms
50ms 50ms 50ms
10ms
10ms 10ms
10ms10ms
10ms
Função 4
Função 3
Função 2
Função 1
Função 0
BS1
BS1
BS1
BS1
BS1
BS3
BS3
BS3
BS3
BS3
Algoritmo 2
47
n0 n1
n4
n2 n3
n5
n7n6
BS0 BS1 BS2 BS3 BS4 BS5 BS6 BS7
10ms
50ms
50ms
50ms
50ms
50ms 50ms 50ms
10ms
10ms 10ms
10ms10ms
10ms
Função 4
Função 3
Função 2
Função 1
Função 0
BS1
BS1
BS1
BS1
BS1
BS3
BS3
BS3
BS3
BS3
BS5
BS5
BS5
BS5
BS5
BS7
BS7
BS7
BS7
BS7
Algoritmo 2
48
n0 n1
n4
n2 n3
n5
n7n6
BS0 BS1 BS2 BS3 BS4 BS5 BS6 BS7
10ms
50ms
50ms
50ms
50ms
50ms 50ms 50ms
10ms
10ms 10ms
10ms10ms
10ms
Função 4
Função 3
Função 2
Função 1
Função 0
BS1
BS1
BS1
BS1
BS1
BS3
BS3
BS3
BS3
BS3
BS5
BS5
BS5
BS5
BS5
BS7
BS7
BS7
BS7
BS7
BS2
BS2
BS2
BS2
BS2
BS6
BS6
BS6
BS6
BS6
Algoritmo 2
49
n0 n1
n4
n2 n3
n5
n7n6
BS0 BS1 BS2 BS3 BS4 BS5 BS6 BS7
10ms
50ms
50ms
50ms
50ms
50ms 50ms 50ms
10ms
10ms 10ms
10ms10ms
10ms
Função 4
Função 3
Função 2
Função 1
Função 0
BS1
BS1
BS1
BS1
BS1
BS3
BS3
BS3
BS3
BS3
BS5
BS5
BS5
BS5
BS5
BS7
BS7
BS7
BS7
BS7
BS2
BS2
BS2
BS2
BS2
BS6
BS6
BS6
BS6
BS6
BS0
BS0
BS0
BS0
BS0
BS4
BS4
BS4
BS4
BS4
Algoritmo 2
Complexidade
• Algoritmo 1
– O (n)
• n é o número de BSs
• Algoritmo 2
– O (n log n)
– Ordenação é responsável pelo aumento da complexidade
50
AvaliaçãoIdeia Geral
51
• Avaliar, para cada algoritmo, sua distância em relação à solução ótima
– Desvio relativo (optimal gap)
Valor da função objetivo
da solução ótima
Valor da função objetivo
da solução heurística
(Alg.1 ou Alg. 2)
AvaliaçãoTopologia Utilizada
52
n0 n1
n4
n2 n3
n5
n7n6
BS0 BS1 BS2 BS3 BS4 BS5 BS6 BS7
Central
Regional
Borda
• Cada BS possui 5 funções
AvaliaçãoParâmetros
• Variação aleatória de latência dos enlaces e capacidade de hospedagem das nuvens
– Diversas amostras do experimento
• Para cada amostra, calcula-se o desvio relativo
• Resultados apresentados com média e intervalo de confiança de 95%
• Latência
– Constante de 300 μs multiplicada por um valor obtido de uma distribuição lognormal
• μ=0
• σ=1 (alta heterogeneidade) e σ=0,125 (baixa heterogeneidade)
53
AvaliaçãoParâmetros
• Capacidade
– Banda é infinita
– Hospedagem
• Em número de funções suportadas por nó da nuvem
• Para o nó central
– 40 funções (ou seja, todas as funções da C-RAN)
• Para cada nó de borda
– Distribuição uniforme entre 0 e 40 Mbor
• Para cada nó regional
– Distribuição uniforme entre 0 e 40 Mreg
54
Resultados Baixa heterogeneidade da latência
• Pequeno desvio relativo para os dois algoritmos
– Pior caso é menor que 3%
55
ResultadosBaixa heterogeneidade da latência
• Algoritmo 2 não é necessariamente melhor que o Algoritmo 1
56
ResultadosAlta heterogeneidade da latência
• Aumento da heterogeneidade não muda o comportamento observado anteriormente
57
Conclusão
• Heurísticas muito simples de posicionamento de funções podem minimizar latência em C-RANs hierárquicas
– Gap menor que 3%
• Baixa complexidade das heurísticas
– O (n) e O (n log n)
• Ordenação de latência (Algoritmo 2) não necessariamente melhora o posicionamento
58
Trabalhos Futuros
• Avaliar o gap de forma analítica
• Combinar a heurística com outros modelos da literatura de C-RAN
– Será que, com mais restrições, as heurísticas continuam com baixo gap?
• Reduzir para um problema conhecido e usar heurísticas próprias desse problema
– Problema atual se parece com variações do bin-packing
59
Minimização da Latência no Posicionamento de Funções
em Cloud RANs
Jean Lucas de Lima e Rodrigo de Souza Couto
Pesquisa financiada pela FAPERJ, CNPq, CAPES e FAPESP
Tempo de Execução
61
Algoritmo 1
Algoritmo 2
Tem
po d
e E
xecução (
ms)
Número de Estações
ANEXO:Formulação do Problema
62
Formulação do Problema
63
ANEXO:Algoritmo 1
64
ANEXO:Algoritmo 2
66
