Filas finitas e redes de Jackson

Uma interface com espaço total para dois pacotes rejeita uma chegada quando já há um pacote em transmissão e outro à espera. A taxa oferecida conta também essa chegada, enquanto a taxa admitida só conta os pacotes que entram; esta diferença muda a aplicação da lei de Little.

Poisson e serviço

A contagem Poisson e os tempos entre chegadas já permitem calcular silêncio: $P(A(t)=0)=e^{-\lambda t}$. A taxa média não impõe intervalos fixos entre pacotes.

Duas fontes Poisson independentes, de 20 e 30 pacotes/s, formam um processo Poisson de 50 pacotes/s quando se juntam. Se cada chegada desse agregado escolher uma saída com probabilidade 0,4, independentemente das outras, essa saída recebe um processo Poisson de 20 pacotes/s e a outra de 30; somar fluxos dependentes ou escolher uma saída conforme o estado das filas não garante estas propriedades.

A letra M em M/M/1 refere-se a processos sem memória: o tempo decorrido não altera a distribuição do tempo restante. O primeiro M descreve as chegadas; o segundo descreve o serviço. Alterar só os comprimentos de pacotes para constantes muda M/M/1 para M/D/1, mantendo a hipótese Poisson à entrada. As distribuições seguintes precisam de ser escolhidas pelas duas condições, não apenas pela taxa média.

M/M/1/B e bloqueio

Nesta página, B é a capacidade total do sistema, incluindo serviço. Se um enunciado usar B só para espera, substitui por B+1. Confirma a convenção antes de usares fórmulas.

Por exemplo, com $\rho=0,75$, «um buffer» como um lugar total dá $B=1$ e bloqueio $0,75/(1+0,75)\approx42,86\%$. Se significar um lugar de espera além do servidor, $B=2$ e o bloqueio é $0,75^2/(1+0,75+0,75^2)\approx24,32\%$. Não resolves a ambiguidade do enunciado escolhendo uma das fórmulas sem declarar a interpretação.

Em equilíbrio, cada fronteira entre estados n−1 e n equilibra subidas e descidas ($\lambda p_{n-1}=\mu p_n$), daqui resulta $p_n=\rho^n p_0$ e $p_0$ sai da normalização da soma até B. Com $\rho=\lambda/\mu$, existem estados 0 até B. Para $\rho\ne1$:

Para $\rho=1$, todos os estados têm probabilidade $1/(B+1)$. A probabilidade de bloqueio é $p_B$, porque uma chegada Poisson observa as probabilidades estacionárias do sistema.

A taxa admitida é $\lambda_e=\lambda(1-p_B)$. Calcula o número médio como $N=\sum_{n=0}^B n p_n$ e aplica Little aos pacotes admitidos: $T=N/\lambda_e$. Se pedirem só fila, subtrai do número médio a probabilidade de o servidor estar ocupado, $1-p_0$, e do tempo médio o serviço $1/\mu$.

Exemplo. $\lambda=\mu=10$ pacotes/s e B=2. O estado conta todos os pacotes no sistema, incluindo o que está em serviço.

Os três estados têm probabilidade 1/3; bloqueio 1/3, taxa admitida $20/3$, N=1, então $T=1/(20/3)=0{,}15$ s. O serviço médio é 0,1 s e a espera média é 0,05 s. Usar $N/\lambda$ daria 0,1 s e ignoraria que um terço das entradas foi rejeitado.

Ao contrário de M/M/1 com capacidade infinita, a fila finita admite uma distribuição estacionária mesmo com $\lambda\ge\mu$. O excesso de procura aparece como bloqueio. Isso não torna a taxa oferecida integralmente atendida.

Dimensionamento de buffers

Adaptação do problema 5 e da resolução docente. Uma saída de 256 kbit/s recebe pacotes com comprimento exponencial médio de 4000 bits e chegadas Poisson. Com tráfego oferecido de 192 kbit/s, $\mu=256000/4000=64$ pacotes/s, $\lambda=192000/4000=48$ e $\rho=0,75$. Na fila ilimitada, $T=1/(64-48)=62,5$ ms, dos quais 15,625 ms são serviço.

Mantendo capacidade e tráfego em bits/s, duplicar o comprimento médio divide ambas as taxas de pacotes por dois. A carga mantém-se, mas T duplica para 125 ms. Reduzir o comprimento para metade dá T=31,25 ms. Fixar a taxa de pacotes, em vez do tráfego em bits/s, seria outro problema.

Com capacidade total B=24 pacotes, passamos a M/M/1/B:

A carga aqui é a razão oferecida, não a fração efetiva de ocupação do servidor da fila finita. Mesmo com mais buffers, no último caso o bloqueio tende a $1-1/1,25=20\%$: o canal não consegue servir todo o tráfego sustentado.

O bloqueio depende de $\rho$ e B. Se mantivermos tráfego em bits/s e B em pacotes, mudar o comprimento não muda $\rho$ nem o bloqueio deste modelo, mas altera a memória em bytes necessária para o mesmo número de pacotes. Com memória física fixa em bytes, B também pode mudar, por isso não podemos então concluir que a perda fica igual.

Inferir a ligação a partir do tempo ocioso

Numa M/M/1 estável, $P(N=0)=1-\rho$. Se o servidor está ocioso 20% do tempo e chegam 360 pacotes/s, $\rho=0{,}8$ e $\mu=\lambda/\rho=450$ pacotes/s. Com comprimento médio de 800 bytes, a capacidade é $C=450\times800\times8=2{,}88$ Mbit/s. Ocupação, taxa de chegada e comprimento médio bastam para inferir a capacidade, sem medir diretamente o débito da ligação.

Doze portas de entrada geram cada uma 200 kbit/s para a mesma saída, com pacotes médios de 1000 bytes. O tráfego oferecido é $12\times200=2400$ kbit/s, ou 300 pacotes/s. Para uma ocupação média de 80%, a saída precisa de $C=2400/0{,}8=3000$ kbit/s, servindo $\mu=375$ pacotes/s; o tempo médio no sistema é então $T=1/(375-300)\approx13{,}33$ ms. Dimensionar pela ocupação inverte a conta habitual: fixa primeiro a fração de tempo ocupada e deduz a capacidade.

O número de pacotes no sistema, incluindo o que está em serviço, tem cauda geométrica:

Nos mesmos dados, $P(N\ge3)=0{,}8^3=0{,}512$. Se a pergunta disser «três em espera», há também o pacote em serviço: $P(N_q\ge3)=P(N\ge4)=0{,}4096$. Escrever a fronteira evita deslocar o expoente uma posição.

M/M/1 dá $T=1/(450-360)=11{,}111$ ms e $T_q=8{,}889$ ms. Se apenas o serviço passar a constante, mantendo chegadas Poisson, FIFO e capacidade ilimitada, M/D/1 dá $T_q=4{,}444$ ms e $T=6{,}667$ ms. A capacidade e a carga mantêm-se; a variabilidade muda.

Espera limitada com serviço constante

Imagina serviço constante $s=1/450$ s e capacidade total de quatro pacotes, incluindo serviço, FIFO sem preempção. Um admitido encontra no máximo três à frente, por isso a fila fica limitada por $3s=6{,}667$ ms. É um limite superior, não a espera média.

Se os quatro lugares forem apenas de espera, a capacidade total é cinco e o limite muda. A distribuição estacionária de M/M/1/B não se aplica automaticamente à fila M/D/1/B: mudar o serviço muda o modelo.

M/G/1 e variância do serviço

Seja $S$ o tempo de serviço. $E[S]$ é a média, $Var(S)$ a variância e $E[S^2]$ a média do quadrado. O tempo residual médio que uma chegada encontra é $R=\lambda E[S^2]/2$, pois cada serviço contribui com metade do seu quadrado, porque serviços longos são mais prováveis de estar em curso. Com Poisson, serviços iid independentes das chegadas, um servidor, FIFO ilimitada sem preempção e $\rho=\lambda E[S]<1$:

Como $E[S^2]=Var(S)+E[S]^2$, maior variância pode aumentar a espera mesmo mantendo serviço médio e carga. Para serviço constante, $Var(S)=0$; para exponencial, $E[S^2]=2E[S]^2$. Estas substituições recuperam M/D/1 e M/M/1.

Exemplo. $E[S]=0{,}01$ s, variância $0{,}0001$ s² e $\lambda=50$. Então $\rho=0{,}5$, $E[S^2]=0{,}0002$ s² e $T_q=0{,}01$ s. O tempo total é 0,02 s. Quadrados de tempos usam s²; somar uma variância a uma média sem elevar esta ao quadrado não faz sentido.

Filas em série e independência

Duas ligações em série não tornam automaticamente a segunda fila M/M/1. Se a primeira transmitir pacotes de comprimento constante em $s_1$ segundos, as suas saídas ficam separadas por pelo menos $s_1$. Não são Poisson, que permite chegadas arbitrariamente próximas.

Com segunda ligação mais rápida, serviço $s_2\le s_1$, propagação constante e sem outro tráfego, cada pacote termina antes de o próximo chegar. A segunda fila não acumula espera, apesar de a primeira poder ter espera M/D/1. Somar duas fórmulas M/D/1 inventaria uma chegada Poisson que a segunda não tem.

Com comprimentos variáveis conservados entre saltos, um pacote longo exige serviço longo em ambos. As chegadas e os serviços na segunda fila podem estar relacionados. A aproximação de independência de Kleinrock permite modelar cada ligação por M/M/1 quando a mistura de vários fluxos torna essa dependência menos importante. É uma aproximação, usada nos slides para redes com mistura de tráfego, não uma consequência apenas de $\lambda<\mu$.

As taxas de cada ligação somam os fluxos dos percursos que a atravessam. Calcula $N$ por ligação e soma-os; para obter o tempo médio na rede, divide essa soma pela taxa de pacotes que entram do exterior. Contar cada salto como uma nova entrada externa reduziria artificialmente o atraso.

Redes abertas de Jackson

Uma rede aberta tem chegadas externas, várias filas e saídas. Nos modelos de Jackson usados aqui, as chegadas externas são Poisson, cada nó tem um servidor com serviço exponencial, independente dos restantes processos, o encaminhamento tem probabilidades fixas e as filas têm capacidade infinita. Todos os nós precisam de carga inferior a um.

Desenha primeiro entradas externas, visitas e saídas de cada nó. Só depois escreve as equações. Se $\gamma_i$ for a taxa externa do nó i e $p_{ji}$ a probabilidade de um pacote que sai de j seguir para i, as taxas totais satisfazem:

Resolve estas equações antes de usares fórmulas de filas, porque a taxa interna pode exceder a externa quando há visitas repetidas.

Exemplo. Entram 40 pacotes/s em A. Metade vai depois para B; um quarto das saídas de B regressa a A e o resto sai. Assim $\lambda_A=40+0{,}25\lambda_B$ e $\lambda_B=0{,}5\lambda_A$, logo $\lambda_A=40/0{,}875\approx45{,}714$ e $\lambda_B\approx22{,}857$.

Se $\mu_A=100$ e $\mu_B=80$, os tempos por visita são $T_A=1/(100-\lambda_A)\approx0{,}01842$ s e $T_B\approx0{,}0175$ s. O número médio de pacotes em toda a rede é $N=\lambda_AT_A+\lambda_BT_B\approx1{,}2421$. Por Little na fronteira externa, o tempo médio por pacote externo é $N/40\approx0{,}03105$ s. Somar simplesmente $T_A+T_B$ seria errado, porque nem todos visitam B e alguns regressam.

Num percurso fixo sem retornos, o atraso soma os tempos das filas visitadas e as propagações. A forma produto de Jackson permite calcular médias por nó, mas não autoriza tratar qualquer tráfego real como Poisson. Filas finitas, prioridades ou serviços correlacionados pedem outro modelo.