Lista 5 de Exercı́cios de Avaliação de Desempenho
CMTC e Sistemas P2P
Professores: Paulo Aguiar e Daniel S. Menasché
1
Disponibilidade do Conteúdo
Considere um arquivo C. Publishers deste arquivo chegam ao sistema de acordo com um
processo Poisson com taxa Λ. Cada publisher fica no sistema por tempo exponencial, com
média 1/δ, e depois vai embora.
1. descreva a cadeia de Markov que caracteriza o número de publishers no sistema
2. ache as probabilidades em estado estacionário do número de publishers no sistema
3. a partir da probabilidade de haver zero peers no sistema, π0 , derive a média do perı́odo
ocupado deste sistema
4. assuma que o conteúdo está disponı́vel enquanto há pelo menos um publisher no sistema.
A disponibilidade do conteúdo é definida como a fração de tempo em que o conteúdo
está disponı́vel. Determine a disponibilidade em função de Λ e δ
5. assuma agora que os publishers de K conteúdos decidem distribuir os conteúdos uns dos
outros, na forma de bundles. Ou seja, toda vez que um publisher chega ao sistema, ele
pode oferecer qualquer um dos K conteúdos do bundle. A taxa agregada de chegada
dos publishers com o bundle é KΛ. Seja A a disponibilidade dos arquivos quando
distribuı́dos de forma isolada, e AB a disponibilidade dos arquivos quando distribuı́dos
de forma agregada (bundled ). Qual o ganho em termos de disponibilidade do bundle?
Mostre que A/AB = e−Θ(K) .
1
2
Seleção de Portfolio
Considere agora um único publisher, estável (sempre online). O publisher pode selecionar
quais arquivos transmitir dentro de um catálogo de arquivos. A cada arquivo está associada
uma taxa de chegada de requisições de λ requisições/s. Após concluir o download de um
arquivo, o peer sai imediatamente do sistema.
Assuma que o sistema é perfeitamente escalável, i.e., a capacidade do sistema aumenta
em função do tamanho da população. Assim sendo, independente do número de usuários no
sistema, o tempo de download de um arquivo é exponencialmente distribuı́do com média 1/µ
(a variação do tempo de download deve-se às variações de atraso na rede).
2.1
Maximizando Dependência do Publisher na Presença de Pirataria
O publisher decide servir, dentro do catálogo de arquivos, aqueles cuja taxa λ de requisições
maximize seus lucros por unidade de tempo. Assuma que, sempre que houver dois ou mais
peers no sistema, os peers irão baixar conteúdo entre si, sem pagar ao publisher. No entanto,
quando só há um peer no sistema, este peer tem que fazer download do publisher. Neste
último caso, o publisher lucra (cada peer paga c reais imediatamente após efetuar download
do publisher ).
• monte e resolva a cadeia de Markov que descreve o número de peers no sistema (excluindo o publisher )
• caracterize o lucro do publisher em função de λ e µ
• qual o valor de λ que maximiza o lucro do publisher ?
• seja c = 1 e µ = 1. Plote o lucro do publisher em função de λ, variando λ entre 0.01 e
10, em incrementos de 0.01.
2
2.2
Maximizando Lucro do Publisher na Ausência de Pirataria
Assuma, agora que autoridades de combate a pirataria impedem que peers façam download
de conteúdo sem autorização. O publisher agora lucra por cada download efetuado pelos
usuários, independente do número de usuários no sistema. Os usuários ainda fazem downloads
de arquivos entre si, mas para acessar os arquivos precisam pagar ao publisher, que então
autoriza o uso dos arquivos.
• seja L o lucro do publisher. Seja C o custo e R o ganho, L = R − C. O publisher ganha
c reais por download efetuado, e incorre custo de b reais por peer servido. Assuma,
como na questão anterior, que o publisher só serve um peer quando este está sozinho
no sistema (caso contrário, os peers servem uns aos outros, e contactam o publisher
apenas para pagá-lo). Derive L em função de c, b, λ, µ.
• seja c = 1 e µ = 1, como na questão anterior, e b = 100. Plote o lucro do publisher em
função de λ. O que ocorre se o publisher selecionar o arquivo com λ ótimo derivado
de acordo com a questão anterior? Qual o menor valor de λ para o qual vale a pena o
publisher disseminar o arquivo?
3
3
CMTC e transformadas
Pessoas chegam à fila do trem fantasma a uma taxa Poisson λ. Os carrinhos carregam até
duas pessoas e chegam para embarque segundo um intervalo exponencial com taxa µ. As
pessoas são acomodadas duas por carrinho, exceto quando temos apenas uma pessoa para
embarcar ou a fila está vazia. Assuma que o tempo de embarque em si é muito rápido e
desprezı́vel frente ao tempo médio de espera pelo carrinho.
a) Assumindo o estado como o número de pessoas na fila de espera para entrar no trem
fantasma, desenhe a CMTC correspondente.
b) Obtenha as equações de equilı́brio. Verifique se é possı́vel obter um número de equações
suficientes para a resolução das probabilidades em equilı́brio sem indeterminações. Não tente
resolver o sistema de equações.
c) Assumindo que haja o estado em equilı́brio, e definindo P (z) =
P∞
k=0
z k πk , mostre, a
partir das equações de equilı́brio (multiplique os dois lados por z k e some) , que
P (z) =
−µ(π1 + π0 )z − µπ0
λz 2 − µz − µ
d) A partir da conservação de probabilidade, obtenha uma equação envolvendo π0 e π1 .
Sabendo que as probabilidades são sempre positivas, que restrição nas taxas pode ser obtida
a partir desta equação?
e) Mostre que das duas raı́zes do denominador de P (z), uma delas tem módulo menor
que 1, isto é, ela está dentro do cı́rculo unitário, assumindo as restrições para existência de
equilı́brio (ou seja π0 > 0), e a outra está fora do cı́rculo unitário.
f) Usando a analiticidade da T.L. (não pode ter polos dentro do cı́rculo unitário), obtenha
mais uma equação envolvendo π0 e π1 e resolva para π0 . Mostre que π0 > 1.
4