Dissertação (Mestrado em Informática) — Universidade de Brasília, Instituto de Ciências Exatas, Departamento de Ciência da Computação, Brasília, 2021. Projetistas de sistemas tem sido confrontados com aplicações e sistemas do mundo real que são inerentemente distribuídas e abertas. Um sistema inerentemente aberto é um no qual é impossível estabelecer controle global ou, também dizendo, aquele no qual uma única entidade não é capaz de possuir uma descrição completa do estado do sistema. Sistemas que atendem a essa descrição são complexos, e projetá-los é desafiante. Uma forma de lidar com esses desafios é abordar o problema como o projeto de um sistema multiagente. Um agente é um sistema computadorizado dotado de autonomia para agir em nome de seu proprietário. Um sistema multiagente é uma sociedade de agentes que interagem sob determinadas regras para alcançar metas comuns ou individuais. Um exemplo de problema complexo que poderia se beneficiar de uma abordagem multiagente é a distribuição de vídeo através da Internet. Uma das razões para o crescimento rápido do consumo de dados na Internet é a crescente demanda por conteúdo em vídeo. Entre os provedores de streaming de vídeo ao vivo, a técnica Streaming de Vídeo Adaptativo (Adaptive Bitrate Streaming - ABR) se tornou o padrão de fato da indústria. ABR é uma forma conveniente de distribuir vídeo pela Internet para muitos usuários simultaneamente. Para descrever a técnica ABR brevemente, um streaming de vídeo é divido em segmentos que são transcodificados em diferentes taxas de bits, assim os usuários podem se adaptar, consumindo a representação que melhor se conforma com a sua largura de banda. Os recursos computacionais que a transcodificação demanda não são negligenciáveis. De fato, a transcodificação de vídeo representa custos relevantes para os provedores de vídeo ao vivo. A bufferização empregada pelos players de vídeo compatíveis com a ABR é uma característica chave para determinar a previsibilidade das requisições de segmento de vídeo. Experimentos indicam que a audiência de vídeos pela Internet prefere representações com altas taxas de bits, sendo que constantes interrupções prejudicam a qualidade da experiência. Uma função de utilidade básica de uma sessão de vídeo pode ser definida como a razão entre a taxa de bits média, contrabalançada pela suavidade da reprodução. Suavidade da reprodução é a razão entre o tempo gasto esperando o buffer de vídeo ser preenchido e o tempo total de exibição. Em uma arquitetura baseada em nuvem, a periferia onde ficam os dispositivos dos usuários finais é chamada de Borda (Edge) ou Neblina (Fog). Desta forma, tirar vantagem desses recursos que estão geograficamente distribuídos é referenciado como Computação na Neblina (Fog-Edge Computing - FEC). O ambiente da FEC é definido como um complemento da núvem que emprega dispositivos na borda da rede para melhorar a qualidade de serviço através de um contínuo. Como um complemento da infraestrutura da Internet, o FEC herda algumas de suas características. O FEC tem muitos recursos computacionais ociosos, que estariam, teoricamente, disponíveis para serem utilizados entregando uma baixa latência. Usar esses dispositivos do FEC pode ser útil para a transcodificação distribuída de vídeo ao vivo. No entanto, a colaboração com dispositivos desconhecidos pode ser arriscada, pois não estão sob controle dos provedores ou dos usuários. Já que alguns dos nós do FEC tem autonomia deliberativa visando melhorar seu desempenho, nós podemos descrevê-los como agentes. Uma sociedade composta de entidades autônomas, como um sistema multiagente, leva a possibilidade de uma parte destas entidades serem egoístas. Em outras palavras, é necessário saber em quem confiar. A aplicação de modelos de confiança e reputação é uma característica chave quando queremos lidar com o risco de delegar tarefas em ambientes abertos e semi-competitivos, tal como o FEC. Para enfrentar a incerteza de colaborar com dispositivos no FEC, um agente racional A, antes de delegar uma tarefa da qual seu bem-estar depende para um agente B, precisa de alguma forma calcular a probabilidade de B completar a tarefa satisfatoriamente. Esta probabilidade representa o quanto o agente A avalia que B é digno de confiança quanto a tarefa em questão. De qualquer forma, um agente talvez não seja capaz de avaliar a confiabilidade de uma contraparte se eles nunca se encontraram antes. Uma solução recorrente para a falta de informação advinda de interação direta é perguntar a outros sobre a opinião que eles têm de um possível parceiro. A ponderação da confiança que uma comunidade deposita em um agente é chamada de reputação. Na literatura, há vários modelos de interação entre agentes baseados em confiança e reputação (Trust and Reputation Models - T&RM). Um dos aspectos que diferencia esses modelos são as fontes de informação que eles podem utilizar como insumo. No entanto, todos eles consideram a interação direta e/ou a opinião de testemunhas em seus cálculos. Os algoritmos chamados de Multi-Armed Bandits (MAB) são aplicados quando um agente precisa escolher entre alternativas incertas. Agentes não sabem a priori qual é a distribuição de recompensas das escolhas postas à sua frente, mas têm certa confiança que existem escolhas melhores que outras. Os algoritmos MAB possuem duas fases, a fase de exploração e a fase de aproveitamento. Na fase de exploração são feitas escolhas para tentar estimar a distribuição de recompensas de cada uma das opções testadas. Depois disso, o agente pode utilizar o conhecimento que adquiriu para escolher a melhor opção dentre as que passou a conhecer na fase de aproveitamento. Ao passar para a fase de aproveitamento, não queremos dizer que o agente sabe de forma incontestável qual é a melhor opção, já que a distribuição de recompensas verdadeira é ainda desconhecida e pode haver uma opção melhor dentre as que não foram escolhidas. Muitos algoritmos implementam diferentes estratégias para balancear exploração e aproveitamento. Para exemplificar, citamos e-Greedy, e-First, e-Decreasing e a família de algoritmos chamada Limites de Confiança Elevados (Upper Confidence Bounds - UCB). Foram selecionados alguns trabalhos prévios que abordaram o problema de habilitar a transcodificação de vídeo ao vivo para dispositivos heterogêneos em ambientes distribuídos. Cada trabalho empregou um método específico, onde os autores validaram as abordagens em cenários distintos dificultando a comparação de desempenho dos mesmos. Assim, as soluções propostas foram analisadas procurando brechas onde modelos de confiança e reputação pudessem ser aplicados para trazer vantagens, tanto para os provedores quanto para os usuários finais. Destaca-se que os trabalhos pesquisados na literatura falham ao abordar ambientes abertos. No entanto, o problema da colaboração com agentes potencialmente maliciosos é proeminente quando se pretende empregar os dispositivos do usuário final. Seria interessante que as tarefas de transcodificação fossem designadas aos nós de forma dinâmica de acordo com o desempenho observado a cada turno de execução. Neste caso, o uso de uma métrica de confiança e reputação que represente uma avaliação geral da contribuição para a utilidade dos visualizadores, não apenas incluindo a estabilidade do nó, mas a competência em desempenhar a tarefa designada seria útil. Assim, uma proposta mais adequada ao problema poderia abordar três frentes: definir uma arquitetura baseada em agentes autônomos, capacitar a arquitetura a selecionar os nós apropriados para fazer a transcodificação em ambiente aberto e, ainda, avaliar a credibilidade de testemunhas evitando a influência de agentes não-confiáveis. Como solução para o problema descrito, foram analisados os requisitos do sistema multiagente com a metodologia Tropos. Tropos é uma metodologia de desenvolvimento de software para programação orientada a agentes. Essa metodologia permite a representação de estados mentais como metas e qualidades. O aspecto que mais diferencia a metodologia Tropos de outras metodologias de desenvolvimento de software é a natureza centrada em agentes. A metodologia Tropos guia o desenvolvimento de soluções orientadas a agentes através de um conjunto de fases, pelas quais o desenvolvedor gradativamente vai refinando a representação do sistema. Da análise com a metodologia Tropos surgiu a proposta de uma arquitetura para transcodificação distribuída composto de agentes que desempenham três papéis: o Corretor (Broker), o Proxy do visualizador (Viewer’s proxy) e o Transcodificador (Transcoder). O Proxy do visualizador é o papel para os agentes que representam a audiência do stream de vídeo ao vivo. Esse papel é destinado aos agentes que requerem ao Corretor a adaptação do stream em ABR e interage com ele para avaliar o desempenho dos transcodificadores. O Transcodificador é o papel a ser desempenhado pelos agentes interessados em receber tarefas de transcodificação e serem recompensados por elas. A responsabilidade dos corretores é gerenciar a associação entre os proxies dos visualizadores e os transcodificadores para o benefício de ambos. Pensando sobre o trabalho que os corretores desempenham no modelo proposto, em certo ponto eles irão formar um conjunto de transcodificadores dentre os quais alguns são bem conhecidos, enquanto outros não terão sido testados. Então, corretores devem balancear suas estratégias entre aproveitar os mais bem conhecidos ou explorar os desconhecidos para aprender sobre o desempenho deles. Aprender sobre os transcodificadores disponíveis, nós queremos dizer que os corretores devem formar uma crença sobre o quão bom transcodificador é um nó específico, com a ajuda da avaliação de um determinado grupo de visualizadores. Esta crença externa (relação não reflexiva) é uma medida da reputação do transcodificador na comunicade de visualizadores. Para o corretor, a reputação de uma transcodificador é representado por um par de valores: a confiabilidade do transcodificador e uma medida da confiança que se tem no primeiro valor, a credibilidade da confiança. Para que o corretor tenha a capacidade de selecionar os nós de acordo com as regras estabelecidas foi introduzido o algoritmo ReNoS - Reputation Node Selection. O algoritmo foi projetado para balancear exploração e aproveitamento de forma que o nó mais confiável não seja sobrecarregado. Quando um novo transcodificador é registrado, recebe uma avaliação de confiança acima do limiar de cooperação e um pouco abaixo da maior avaliação possível, assim aumentando as chances de ser selecionado na próxima iteração. Um problema detectado com o uso do ReNoS é que ele requer que o valor de confiança inicial seja alto. Isto significa que, para usar o algoritmo, o agente que usa a confiança deve acreditar que um nó novo e desconhecido é tão bom quanto um muito conhecido e bem avaliado. De outra forma, a exploração não irá funcionar adequadamente. Esta política é semelhante a utilizada no algoritmo UCB1, onde as opções menos selecionadas até o momento são aquelas com as maiores chances de serem selecionadas no próximo turno. Para contornar esse problema, foi elaborada uma nova versão do algoritmo denominado ReNoS-II. O ReNoS-II é baseado na ideia do algoritmo conhecido como Thompson Sampling. Quando um novo transcodificador se registra recebe um valor de reputação com baixa confiança e credibilidade. Desta forma, a expectativa para a curva de desempenho é achatada e larga, semelhante a uma distribuição uniforme. Mas a medida que o transcodificador é testado e mais conhecimento se acumula sobre ele a credibilidade cresce e a curva se estreita em torno do valor da confiança. Para validação da arquitetura proposta foi realizado um experimento com o objetivo de verificar se a abordagem trata adequadamente o problema da transcodificação distribuída com nós do FEC. Foi utilizado um protótipo implementado seguindo estritamente as diretrizes da arquitetura, capaz de desempenhar as tarefas necessárias para distribuir a transcodificação em tempo real. Validar o modelo proposto que combina MAB e T&RM para selecionar nós no FEC envolve identificar as condições nas quais as características do ambiente FEC poderiam prejudicar as garantias dos algoritmos MAB. Uma dessas condições é quando os agentes não são verdadeiros em seus relatórios. Já que transcodificadores estão interessados em receber o maior número de tarefas de transcodificação possível, os nós não-confiáveis podem formar uma coalisão com visualizadores para tentar manipular as escolhas do corretor. Desta forma, o experimento inclui dois cenários distintos. No Cenário 01, o objetivo é obter uma linha base de comparação onde os agentes envolvidos não recusam interações sendo sempre verdadeiros nas trocas de informação. No cenário 02, o objetivo é observar o que acontece quando um transcodificador tenta manipular a transcodificação distribuída com ataques de relatórios falsos. Nesse experimento, a métrica utilizada para comparação foi o valor da recompensa acumulada pelo corretor ao longo de uma sessão de transcodificação. O experimento revelou que quando o algoritmo UCB1 foi empregado houve um decréscimo significativo do Cenário 01 para o Cenário 02. No entanto, não foi observado o mesmo decréscimo quando os algoritmos empregados foram ReNoS e ReNoS-II associados ao modelo FIRE. UCB1 e ReNoS produziram resultados semelhantes em termos de recompensa acumulada. Por outro lado, os resultados obtidos com o algoritmo ReNoS-II foram significativamente maiores do que os obtidos com UCB1 e ReNoS nos dois cenários, apesar da variância ter sido maior. Pelos resultados dos experimentos realizados, conclui-se que o modelo proposto combinando MAB e T&RM para selecionar nós no FEC é promissor para aplicação no mundo real. Os resultados experimentais do algoritmo ReNoS se apresenta tão performativo quanto UCB1. O algoritmo ReNoS-II apresenta um desempenho melhor que o ReNos e UCB1 nos dois cenários testados. Enfim, os experimentos mostraram que ponderando e filtrando informação dos relatórios baseando-se na credibilidade das testemunhas é possível proteger o sistema de transcodificação distribuída no FEC de agentes não-confiáveis, evitando danos causados pela formação de coalisões. Adaptive Bitrate Streaming (ABR) is a popular technique for providing video media over the Internet. In ABR, the streaming provider splits the video stream into small segments then transcodes them in many different bitrates. So, players can adapt to unstable network parameters minimizing interruptions on playback. However, the computational cost of transcoding a video in many formats can limit its application on live video streaming. Besides, the network overhead of transmitting simultaneously many versionsof the same content is a problem. Offloading the transcoding burden to the edge of the network, near the end-users, should alleviate the data traffic burden on the backbone while diluting the computational cost. Users and providers of live video could benefit from a joint scheme that allowed end-user devices to do the transcoding with tolerable latency and delay. We applied Tropos, the agent-oriented software development methodology, to analyze the described scenario and design a multi-agent architecture to deal with the problem of distributed transcoding on Fog-Edge Computing (FEC). The presented architecture consists of three well-defined roles. The transcoder role is intended for those agents on FEC interested in receiving transcoding tasks. The viewer proxy role should be performed by those software agents who will act for the sake of the viewers. The broker role is performed by the agents who will coordinate the tasks for the benefit of the other two. Since FEC is an open environment, distributing transcoding tasks over unknown partners is risky. One of the threats is the risk of untrustworthy partners trying to manipulate the broker by sending it fake information. Literature refers to this kind of manipulation as fake feedback attacks. In this master thesis, we propose combing reward evaluation functions that account for Quality of Service (QoS) with Trust and Reputation Models (TRM) and Multi-armed bandits algorithms (MAB). We present two algorithms, Reputation-based Node Selection (ReNoS) and ReNoS-II, designed to online select the best edge nodes to perform the transcoding tasks. We experimented with ReNoS, ReNoS-II, and the other three selecting algorithms in two scenarios to compare them regarding accumulated reward, exploration of available partners, and vulnerability to fake feedback attacks. The outcomes indicate that our proposal can afford rewards gain keeping good QoS as perceived by viewers, besides offering protection against fake feedback attacks delivered by untrustworthy transcoders and viewers. Our main contribution is a multi-agent architecture that combines the robustness of TRM and stochastic MAB algorithms to mitigate the risk of fake feedback attacks, which enabled the employment of unknown partners in open environments. This achievement is in the interest of distributed transcoding applications since it mitigates the risk of employing end-user devices.