Upload
buibao
View
213
Download
0
Embed Size (px)
Citation preview
Velocidade, banda ou taxa de transmissão da Internet no Brasil
Marcio Augusto de Deus Engenharia IP da GlobeNet
Professor e Pesquisador do InsAtuto Federal de Brasilia Programa de Pós-‐graduação em Engenharia Elétrica da UnB
Capacidade do Canal
• Capacidade = taxa máxima teórica de transmissão para um canal.
• Teorema de Nyquist: – Largura de Banda = W Hz – Taxa de dados <= 2W – 2 níveis de codificação – M é o número de níveis.
1 0
C = 2Wlog2 M
bps ≈ Baud/s
Capacidade do Canal
• Teorema de Nyquist-‐Shannon – 1928 – define taxa de transmissão máxima para um canal de banda passante limitada
– sendo “W” a largura de banda, Nyquist prova que a amostragem máxima sobre o canal é 2W
– assim, com canal de W Hz transmite-‐se 2W Bauds C = 2 W Bauds C = 2 W log2 M bps
Capacidade do Canal
• Bit x Baud – Baud: número de intervalos de sinalização por segundo – Bit: 0 ou 1
• Tipo do sinal: dibit, tribit, etc – sinal dibit: dois bits codificados em um intervalo de sinalização
– 1 Baud = log2 M bps onde M é o número de níveis sinalizáveis
00 01
11
10 00
10
11
01
Capacidade do Canal (Teoria da Informação)
• Shannon – levou em consideração a relação sinal-‐ruído (S/N) em dB
C = W log2 (1 + S/N) bps
• Exemplo: canal de 3.000 Hz com relação S/N de 30 dB não transmiArá em
hipótese alguma a mais de 30.000 bps • Limite máximo teórico
Relação entre capacidade de canal e banda efeAva
C = W log2 (1 + S/N) bps
Banda EfeAva (Relacionada a fonte de Informação)
(Fonte/Receptor)
Relação entre capacidade de canal e banda efeAva
Forma simplificada
C = W log2 (1 + S/N) bps
Banda EfeAva (Relacionada a fonte de Informação,
neste caso na camada de rede)
(Fonte/Receptor)
to-‐ti = Intervalo de amostragem
Problema Operações muito simples para banda efeAva
5 10 15 20
300Mb
Qb
25 tmin
Se to-‐ti=5min Beff=300Mb/(300) = 1Mbps
Se to-‐ti=10min Beff=300Mb/(600) = 0,5Mbps
SNMP ßà MIB (Coletas padronizadas em 5 min)
Qual é a banda, taxa ou velocidade neste caso? 1Mbps ou 0,5Mbps ?
Medidores de velocidade na Internet
Internet (Acesso+Backbone)
Usuário
Usuário
Ferramenta Lado do usuário
Ferramenta
Medidor
upload
download
Metodologia mais usada:
A base de tempo é definida no intervalo entre 1 e 30 segundos
Medidores de velocidade na internet
• São válidos? Medem taxa instantânea, normalmente não usam modelos matemáAcos para previsão de banda efeAva.
• A metodologia do teste nem sempre é apresentada.
• De uma forma geral usam uma medida de taxa instantânea e sem consideração do buffer.
• Certamente usam bases de tempo diferentes daquelas usadas pelos provedores. – Provedor: SNPM ßà MIB (1 ou 5 minutos)
Problemas Uso do cálculo baseado apenas na média (1ª ordem) é válido?
Escala de tempo
crescen
te
Self-‐similar, MulAfractal Poisson
EsAmador de Capacidade (bps)
K X[0,t] Servidor
[ ]∞<<= tK
KteEtKBP
tKX
,0log),(],0[
BP (bps)
Onde: n K é o buffer n X[0,t] processo que define a quantidade de bits que estão chegando para serem
encaminhados n t é o tempo.
[Kelly, 1996]
t
bits
Interface de um roteador
Base teórica
Dependência de longa e curta duração
Modelos baseados em Poisson
Modelos baseados em 2aordem Sem memória Com memória
Definição da Banda EfeAva (Kelly)
Para uma fonte Gaussiana com H=0,75
Z(t) é uma dist gaussiana com média zero
para um processo fBm
Definição da Banda EfeAva (Kelly)
onde, são incrementos independentes, então: Se
Para qualquer valor de com s sendo incrementado, temos:
Onde é o maximo valor possível
Norros
Processos com dependência de longa-‐duração:
954
-0.6;
IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS, VOL. 13, NO. 6, AUGUST 1995
We always assume that the process At has stationary increments, i.e., that for any t E % and s1 < . . . < s, the distribution of
(A(t + SI. t + SZ), . . . , A( t + ~ ~ - 1 , t + s n ) )
is independent of t . We also assume square integrability, i.e., EA: < CO. It follows from the stationarity of the increments that EAt = mt for some constant m, the mean rate, and that, denoting v(t) = VarA+
1 2
CovA,,At = - ( v ( t ) + t f ( ~ ) - v ( t - s ) )
for s < t . Thus, the correlation structure (all so called second- order properties) of At is determined by the variance function v(t) alone.
The process At is called short-range dependent if for any s < t 5 U < v the correlation coefficient between A(as,at) and A ( a u , a v ) converges to zero when the time scale a approaches infinity. Otherwise it is called long- range dependent. If At is short-range dependent, v ( t ) is asymptotically linear. In particular, if At is a process with independent increments, say a Poisson process or a compound Poisson process, then w ( t ) is a linear function.
All traffic models traditionally used in teletraffic theory are short-range dependent. From this point of view it was rather shocking that the accurate and extensive LAN traffic measurements conducted in Bellcore [ 151 gave variance curves where v ( t ) grew rather accurately as a fractional power t p , with p taking values strictly between 1 and 2, through half a dozen of orders of magnitude. It became obvious that at least some traffic phenomena had to be studied with long-range dependent models.
The power form v ( t ) = tP is closely related to the fascinat- ing fractal nature of the traffic traces recorded at Bellcore. Indeed, the time-scaled process A,t then has the variance function
V,arAmt = (at)P = aPVarAt
which implies that Aat and apI2At have the same correlation structure, i.e., the centered process At - mt is second-order self-similar. Note that a second-order self-similar process is long-range dependent unless it has uncorrelated increments, and that the (centered) Poisson process is second-order self- similar (with p = 1).
A process Yt is called (strictly) selfsimilar with Hurst parameter (or self-similarity parameter) H if, for any a > 0, the processes Yet and aH& have the same finite-dimensional distributions. Obviously, self-similarity and second-order self- similarity are equivalent for Gaussian processes since their finite dimensional distributions are by definition Gaussian and thus fully characterized by their first and second-order moments. By an important theorem of Lamperti [14], self- similarity is a generic property of wide classes of limit processes. As a general reference to self-similar processes, see, e.g., articles in the collection [5] .
When a model is built on second-order properties alone, a Gaussian process is often the simplest choice. In this paper we shall model the variation of connectionless traffic with a
0 . 2 0 . 4 0 . 6 0 .8 1.0 -0.1
v Fig. 1. A realization of Zt , t E [0,1] with H = 0.8
Gaussian self-similar process, a fractional Brownian motion (FBM). A normalized FBM with Hurst parameter H E [i, 1) is a stochastic process Zt, t E (-m, CO) , characterized by the following properties:
1) 2, has stationary increments; 2) 2, = 0, and EZt = 0 for all t ; 3) EZ? = Jt12H for all t ; 4) Zt has continuous paths; and 5 ) 2, is Gaussian, i.e., all its finite-dimensional marginal
distributions are Gaussian. This process was found by Kolmogorov [12], but relatively little attention was paid to it before the pioneering paper by Mandelbrot and Van Ness [16] (where the FBM also got its present name). In the special case H = l / 2 , Zt is the standard Brownian motion. We have ruled out the other limiting case H = 1 since the respective 2, is a deterministic process with linear paths.
The covariance of the increments in two nonoverlapping intervals is always positive and has the expression
covzt, - zt, , zt, - zt, 1 2
= - ((t4 - t p - (t3 - t p
+(t3 - t 2 y - (t4 - t p )
for tl < t2 5 t 3 < t4. Many features of FBM’s with H > 1/2 are different
from those of most stochastic processes usually appearing in traffic models. They are not Markov processes and not even semimartingales, having nondifferentiable paths with zero quadratic variation. Fig. 1 presents a simulated realization of Zt with H = 0.8, produced with a simple but somewhat inaccurate bisection method given in [17]. Note that the path looks considerably smoother than that of an ordinary Brownian motion.
For the use of the FBM as a traffic model element it is pleasant to note that in spite of the strong correlations, it is ergodic in the sense that the stationary sequence of increments Zn+l - 2, is ergodic (e.g., [2], Theorem 14.2.1).
B. Fractional Brownian TrafJic
model defined as follows. The rest of this paper is devoted to the -study of a traffic
954
-0.6;
IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS, VOL. 13, NO. 6, AUGUST 1995
We always assume that the process At has stationary increments, i.e., that for any t E % and s1 < . . . < s, the distribution of
(A(t + SI. t + SZ), . . . , A( t + ~ ~ - 1 , t + s n ) )
is independent of t . We also assume square integrability, i.e., EA: < CO. It follows from the stationarity of the increments that EAt = mt for some constant m, the mean rate, and that, denoting v(t) = VarA+
1 2
CovA,,At = - ( v ( t ) + t f ( ~ ) - v ( t - s ) )
for s < t . Thus, the correlation structure (all so called second- order properties) of At is determined by the variance function v(t) alone.
The process At is called short-range dependent if for any s < t 5 U < v the correlation coefficient between A(as,at) and A ( a u , a v ) converges to zero when the time scale a approaches infinity. Otherwise it is called long- range dependent. If At is short-range dependent, v ( t ) is asymptotically linear. In particular, if At is a process with independent increments, say a Poisson process or a compound Poisson process, then w ( t ) is a linear function.
All traffic models traditionally used in teletraffic theory are short-range dependent. From this point of view it was rather shocking that the accurate and extensive LAN traffic measurements conducted in Bellcore [ 151 gave variance curves where v ( t ) grew rather accurately as a fractional power t p , with p taking values strictly between 1 and 2, through half a dozen of orders of magnitude. It became obvious that at least some traffic phenomena had to be studied with long-range dependent models.
The power form v ( t ) = tP is closely related to the fascinat- ing fractal nature of the traffic traces recorded at Bellcore. Indeed, the time-scaled process A,t then has the variance function
V,arAmt = (at)P = aPVarAt
which implies that Aat and apI2At have the same correlation structure, i.e., the centered process At - mt is second-order self-similar. Note that a second-order self-similar process is long-range dependent unless it has uncorrelated increments, and that the (centered) Poisson process is second-order self- similar (with p = 1).
A process Yt is called (strictly) selfsimilar with Hurst parameter (or self-similarity parameter) H if, for any a > 0, the processes Yet and aH& have the same finite-dimensional distributions. Obviously, self-similarity and second-order self- similarity are equivalent for Gaussian processes since their finite dimensional distributions are by definition Gaussian and thus fully characterized by their first and second-order moments. By an important theorem of Lamperti [14], self- similarity is a generic property of wide classes of limit processes. As a general reference to self-similar processes, see, e.g., articles in the collection [5] .
When a model is built on second-order properties alone, a Gaussian process is often the simplest choice. In this paper we shall model the variation of connectionless traffic with a
0 . 2 0 . 4 0 . 6 0 .8 1.0 -0.1
v Fig. 1. A realization of Zt , t E [0,1] with H = 0.8
Gaussian self-similar process, a fractional Brownian motion (FBM). A normalized FBM with Hurst parameter H E [i, 1) is a stochastic process Zt, t E (-m, CO) , characterized by the following properties:
1) 2, has stationary increments; 2) 2, = 0, and EZt = 0 for all t ; 3) EZ? = Jt12H for all t ; 4) Zt has continuous paths; and 5 ) 2, is Gaussian, i.e., all its finite-dimensional marginal
distributions are Gaussian. This process was found by Kolmogorov [12], but relatively little attention was paid to it before the pioneering paper by Mandelbrot and Van Ness [16] (where the FBM also got its present name). In the special case H = l / 2 , Zt is the standard Brownian motion. We have ruled out the other limiting case H = 1 since the respective 2, is a deterministic process with linear paths.
The covariance of the increments in two nonoverlapping intervals is always positive and has the expression
covzt, - zt, , zt, - zt, 1 2
= - ((t4 - t p - (t3 - t p
+(t3 - t 2 y - (t4 - t p )
for tl < t2 5 t 3 < t4. Many features of FBM’s with H > 1/2 are different
from those of most stochastic processes usually appearing in traffic models. They are not Markov processes and not even semimartingales, having nondifferentiable paths with zero quadratic variation. Fig. 1 presents a simulated realization of Zt with H = 0.8, produced with a simple but somewhat inaccurate bisection method given in [17]. Note that the path looks considerably smoother than that of an ordinary Brownian motion.
For the use of the FBM as a traffic model element it is pleasant to note that in spite of the strong correlations, it is ergodic in the sense that the stationary sequence of increments Zn+l - 2, is ergodic (e.g., [2], Theorem 14.2.1).
B. Fractional Brownian TrafJic
model defined as follows. The rest of this paper is devoted to the -study of a traffic
Variância é uma potência de t
Processo de tempo-‐escala
954
-0.6;
IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS, VOL. 13, NO. 6, AUGUST 1995
We always assume that the process At has stationary increments, i.e., that for any t E % and s1 < . . . < s, the distribution of
(A(t + SI. t + SZ), . . . , A( t + ~ ~ - 1 , t + s n ) )
is independent of t . We also assume square integrability, i.e., EA: < CO. It follows from the stationarity of the increments that EAt = mt for some constant m, the mean rate, and that, denoting v(t) = VarA+
1 2
CovA,,At = - ( v ( t ) + t f ( ~ ) - v ( t - s ) )
for s < t . Thus, the correlation structure (all so called second- order properties) of At is determined by the variance function v(t) alone.
The process At is called short-range dependent if for any s < t 5 U < v the correlation coefficient between A(as,at) and A ( a u , a v ) converges to zero when the time scale a approaches infinity. Otherwise it is called long- range dependent. If At is short-range dependent, v ( t ) is asymptotically linear. In particular, if At is a process with independent increments, say a Poisson process or a compound Poisson process, then w ( t ) is a linear function.
All traffic models traditionally used in teletraffic theory are short-range dependent. From this point of view it was rather shocking that the accurate and extensive LAN traffic measurements conducted in Bellcore [ 151 gave variance curves where v ( t ) grew rather accurately as a fractional power t p , with p taking values strictly between 1 and 2, through half a dozen of orders of magnitude. It became obvious that at least some traffic phenomena had to be studied with long-range dependent models.
The power form v ( t ) = tP is closely related to the fascinat- ing fractal nature of the traffic traces recorded at Bellcore. Indeed, the time-scaled process A,t then has the variance function
V,arAmt = (at)P = aPVarAt
which implies that Aat and apI2At have the same correlation structure, i.e., the centered process At - mt is second-order self-similar. Note that a second-order self-similar process is long-range dependent unless it has uncorrelated increments, and that the (centered) Poisson process is second-order self- similar (with p = 1).
A process Yt is called (strictly) selfsimilar with Hurst parameter (or self-similarity parameter) H if, for any a > 0, the processes Yet and aH& have the same finite-dimensional distributions. Obviously, self-similarity and second-order self- similarity are equivalent for Gaussian processes since their finite dimensional distributions are by definition Gaussian and thus fully characterized by their first and second-order moments. By an important theorem of Lamperti [14], self- similarity is a generic property of wide classes of limit processes. As a general reference to self-similar processes, see, e.g., articles in the collection [5] .
When a model is built on second-order properties alone, a Gaussian process is often the simplest choice. In this paper we shall model the variation of connectionless traffic with a
0 . 2 0 . 4 0 . 6 0 .8 1.0 -0.1
v Fig. 1. A realization of Zt , t E [0,1] with H = 0.8
Gaussian self-similar process, a fractional Brownian motion (FBM). A normalized FBM with Hurst parameter H E [i, 1) is a stochastic process Zt, t E (-m, CO) , characterized by the following properties:
1) 2, has stationary increments; 2) 2, = 0, and EZt = 0 for all t ; 3) EZ? = Jt12H for all t ; 4) Zt has continuous paths; and 5 ) 2, is Gaussian, i.e., all its finite-dimensional marginal
distributions are Gaussian. This process was found by Kolmogorov [12], but relatively little attention was paid to it before the pioneering paper by Mandelbrot and Van Ness [16] (where the FBM also got its present name). In the special case H = l / 2 , Zt is the standard Brownian motion. We have ruled out the other limiting case H = 1 since the respective 2, is a deterministic process with linear paths.
The covariance of the increments in two nonoverlapping intervals is always positive and has the expression
covzt, - zt, , zt, - zt, 1 2
= - ((t4 - t p - (t3 - t p
+(t3 - t 2 y - (t4 - t p )
for tl < t2 5 t 3 < t4. Many features of FBM’s with H > 1/2 are different
from those of most stochastic processes usually appearing in traffic models. They are not Markov processes and not even semimartingales, having nondifferentiable paths with zero quadratic variation. Fig. 1 presents a simulated realization of Zt with H = 0.8, produced with a simple but somewhat inaccurate bisection method given in [17]. Note that the path looks considerably smoother than that of an ordinary Brownian motion.
For the use of the FBM as a traffic model element it is pleasant to note that in spite of the strong correlations, it is ergodic in the sense that the stationary sequence of increments Zn+l - 2, is ergodic (e.g., [2], Theorem 14.2.1).
B. Fractional Brownian TrafJic
model defined as follows. The rest of this paper is devoted to the -study of a traffic
Variância
Aαt bαp/2 . At isto é, ambos os processos possuem a mesma correlação.
Yαt bαH . Yt Y é auto-‐similar para ½ < H < 1 ou de outra forma, se as distribuições finitesimais de Yαt e αH . Yt forem iguais.
Norros
Generalizando:
NORROS: ON THE USE OF FRACTIONAL BROWNIAN MOTION 957
In the Brownian case H = 1/2, (8) reduces to
l-p . x = const (9)
with p = 7n/C. Here we may roughly say that reducing the relative free capacity 1 - p by half costs doubling the storage size. Note that the link capacity C does not appear in the equation except within p.
With H > l / Z the situation is different. Let us first write
Pa
(8) in the form of a buffer dimensioning formula - VPC p m - H ) )
(1 - o)H/(l--H) = f - 1 ( t )a1 / (2 (1-H) )C(2H--1) l (2 (1~H))
Fig. 4. connections.
Reduction of VPC's by the use of a CLS instead of pairwise ATM
for the virtual waiting time in a queueing system ([20], cited according to [l]).
Dejinition 3. I : The (stationary) fractional Brownian stor- age with input parameters m, a and H and output capacity C > m is the stochastic process X t defined as
X t SUP (At - A , - C( t - s ) ) , t E (-CO, CO) (6) s s t
where At is the fractional Brownian traffic process with parameters m, n and H . In the special case H = l / Z we call X t the Brownian storage.
The stationarity of X t follows from the stationarity of the increments of A t . That X t is almost surely finite is a consequence of Birkhoff's ergodic theorem. Indeed, the ergodicity of Zt implies that limt,, Zt / t = E21 = 0 a.s., which together with the assumption rn < C yields
lim ( A t - A , - C( t - s ) ) = --x as. Y ' - m
Note that the storage process X t is always nonnegative, although the arrival process has also negative increments.
B. A Scaling Law
The fractional Brownian storage X t obeys an interesting scaling law which is easily deduced from the self-similarity of the FBM. Consider the typical requirement that the probability that the amount of work in system exceeds a certain level x must be small. (The value x is the substitute for the buffer size in our infinite storage model.) If the largest allowed buffer saturation probability (or time congestion probability) is t, then the equation
t = P(X > x) (7)
holds at the maximal allowed load. Now, the self-similarity of Zt allows for deriving from (7) a more explicit relation between the design parameters x (buffer space, or requirement) and C (link capacity) and the traffic parameters m, a and H at the critical boundary.
Theorem 3.2: [ 181 Assuming (7), the following equation holds
where the function
\ V I
(10) It is seen that when H is high, a substantial increase in utiliza- tion, say again halving the free capacity, requires a tremendous amount more storage space. Thus we have a new argument for the widely accepted view that for connectionless packet traffic the utilization factor cannot be practically improved by enlarging the buffers.
The scaling relation (8) can also be written as the bandwidth allocation rule
C = + ~ ~ l ( ~ ) a l / ( 2 H ) x - ( l - H ) / H ~ ~ ~ l / ( z H ) (11)
showing that, for H > l / Z , the link requirement C increases slower than linearly in m so that a multiplexing gain is obtained by using links with higher capacity.
As a practical example where the multiplexing gain plays a central role, compare the use of painvise ATM virtual path connections (VPC's) between n + 1 LAN/ATM intenvorking units (IWU's) with the use of a centralized routing function (connectionless server (CLS)). The essential difference be- tween an ATM switch and a CLS is that the former performs switching purely at the ATM layer whereas the latter looks at the network layer address, found in the payload of the first cell of each datagram. The two alternatives, called in [lo] indirect and direct connectionless service provision over an ATM network, respectively, are depicted in Fig. 4 in the case ri = 3.
Denote the bandwidth needed per IWU with centralized routing by Cdir and the total bandwidth needed per IWU with painvise VPC's by Cindir,n. Assume that a fixed amount x of output buffer space is allocated for any VPC and that all traffic streams between the IWU's are equal. It is then seen from (1 1) that
Cin&r,lL = m + (Cdir - m)711-1 ' (2H) . (12)
Note that this expression for the relative multiplexing gain does not contain the unknown factor f - ' ( t ) .
C. The Approximate Queue Length Distribution
No explicit formula for the distribution of the fractional Brownian storage seems to be known. Instead, we shall approach the distribution of X t through a lower bound.
Theorem 3.3: [ 181 Let X t be the fractional Brownian stor- age with parameters m, a , H and C. Then
depends on H but not on m, a , C or x.
Média Parâmetros relacionados ao 2º momento
O EsAmador de Banda EfeAva FEP
• O buffer é aqui representado pela letra K • a letra a representa a média • H é o parâmetro de Hurst • σ representa o desvio padrão das amostras • Ploss representa a probabilidade da perda de dados por transbordo do buffer.
para H pertencente ao intervalo: 0,5 < H < 1.
( ) ( ) HH
Hloss
HH
HHPKaEN−−
−−+=111
1**)ln(*2* σ
Base teórica
[Fonseca] [Norros]
Estimador FEPBanda média = 108Mbpsσ = 52,34 e Ploss=2%
100120140160180200220240260280300
0,5 0,540,580,620,66 0,7 0,7
40,780,820,86 0,9 0,9
40,98
H
Ban
da E
stim
ada
(Mbp
s)
b=5minb=1minb=5sb=1sb=0,5s
Base teórica (Curvas de FEP) Capacidade -‐ FEP
C=Ba
nda Efe3
va (M
bps)
ForecasAng MulAfractal mBm
AðtÞ ¼Z t
0
!aþ jrHðxÞxHðxÞ%1 dx;
a = Average k = buffer size
σ = Standard DevitaAon H(x) = Holder FuncAon
Forecast MulAfractal
0
1e+07
2e+07
3e+07
4e+07
5e+07
6e+07
7e+07
0 10000 20000 30000 40000 50000 60000
Acc
umul
ated
traf
fic (
in B
ytes
)
Time (in milliseconds)
TraceEP Multifractal
TraceEP Multifractal
TraceEP Multifractal
0
1e+08
2e+08
3e+08
4e+08
5e+08
6e+08
7e+08
8e+08
9e+08
1e+09
0 20000 40000 60000 80000 100000 120000 140000
Acc
umul
ated
traf
fic (
in B
ytes
)
Time (in milliseconds)
0
1e+08
2e+08
3e+08
4e+08
5e+08
6e+08
7e+08
8e+08
0 50000 100000 150000 200000 250000 300000
Acc
umul
ated
traf
fic (
in B
ytes
)
Time (in milliseconds)
(a) (b)
(c)
Conclusões
A banda efeAva a ser usada nas seguintes condições:
-‐ Bases de tempo iguais -‐ O cálculo simplificado, sem considerar o buffer. -‐ Lembrar que o roteador não possui velocímetro.
-‐ Bases de tempos disAntas: -‐ Deve ser caracterizada. -‐ Deve ser definido um modelo que possa ser usado em diferentes bases de tempo.