Making Gnutella-like P2P Systems Scalable

Abstract
Napster pioneered the idea of peer-to-peer file sharing, and supported it with a centralized file search facility. Subsequent P2P systems like Gnutella adopted decentralized search algorithms. However, Gnutella’s notoriously poor scaling led some to propose distributed hash table solutions to the wide-area file search problem. Contrary to that trend, we advocate retaining Gnutella’s simplicity while proposing new mechanisms that greatly improve its scalability. Building upon prior research [1, 12, 22], we propose several modifications to Gnutella’s design that dynamically adapt the overlay topology and the search algorithms in order to accommodate the natural heterogeneity present in most peer-to-peer systems. We test our design through simulations and the results show three to five orders of magnitude improvement in total system capacity. We also report on a prototype implementation and its deployment on a testbed.

Mostra alguns problemas de escalabilidade do Gnutella e propões as seguintes soluções:

• Adaptação da topologia: Ensures that high-capacity nodes are the high degree nodes
• Controle de fluxo: Forward queries if can't answer them
• Cria ponteiros para o conteúdo nos vizinhos
• Biased walk: Não realiza flooding, encaminha para alguns poucos nós. Em geral encaminha para os nós mais conectados. Como o conteúdo é replicado nos vizinhos, nós muito conectados conhecem muito da rede.

Ele ainda argumenta porquê utilizar Gnutella ao invés de DHTs, uma vez que DHTs não sofrem tanto com escalabilidade:

• P2P clients are extremely transient
• Keyword searches are more prevalent, and more important, than exact-match queries.
• Most queries are for hay, not needles.

A Cross-layer Decentralized BitTorrent for Mobile Ad hoc Networks

Abstract
In recent years, a number of P2P systems, for instance, Gnutella, KaZaA, Napster, and BitTorrent, have been proposed for the wired Internet. However, these protocols are not immediately applicable to the mobile ad hoc networks (MANETs) owing to the extreme conditions MANETs operate under. Of the above protocols, although BitTorrent has several features which make it an ideal candidate for adapting to MANETs, the current specification of BitTorrent has several drawbacks which make a straightforward implementation of BitTorrent for MANETs an undesirable solution. In this paper, we investigate a straightforward implementation of BitTorrent [6, 3] in MANETs, termed BTI, and compare its performance with a cross-layer adaptation of BitTorrent for MANETs, termed BTM. We resolve the issues of centralized control and single point of failure in BTI by proposing mechanisms to decentralize the BitTorrent model for MANETs and provide resource/data redundancy to improve the protocol performance. In addition, the cross-layer model of BTM is more suited for use in a MANET. Our performance comparison studies show that BTM is able to outperform BTI in terms of goodput, and the number of pieces delivered, in the context of amortizing the client download expenses over more connections (that is, BTM has a higher average peer degree).

Mudanças no BitTorrent

• Pesquisa por peers(elimina necessidade do tracker) e torrents através de inundação. Utiliza o protocolo de roteamento, ANSI
• Resource replication para aumentar o número de seeds

Observações
- A.1 é desnecessária e foge do problema que o BitTorrent resolve (transferências de arquivos e não buscas). Além disso, ele força o sistema a utilizar um protocolo de roteamento pró-ativo.
- Este protocolo utiliza inundação para encontrar peers e torrents. Além de sobrecarregar a rede, ele não dá garantias de encontrar o que está procurando. Esta técnica não pode ser empregada desse jeito em redes críticas onde um arquivo deve possuir garantias de entrega, porém é uma boa idéia utilizar inundação na vizinhança de um nó (alguns poucos hops) para encontrar outros peers próximos e aumentar a localidade da rede overlay. As duas técnicas devem ser utilizadas em conjunto.
- A replicação de conteúdo da seção 4.1.3 é idéia furada. Primeiro ele diz que o BTI começa com apenas uma única semente, o que não é uma exigência do BitTorrent, mas do BTI. Se for o caso de resiliência ser muito importante, o administrador pode colocar mais seeds. Nos outros casos, replicação de conteúdo levaria a disperdício. Além disso é pedir demais que os participantes da rede baixem arquivos que não lhes interessam.
- Uma consulta é broadcasted com um TTL de 2. Se der pau, ele incrementa de 1 em 1 e vai assim até 10. Isso é muito tosco, gera muita mensagem repetida. Rolava dele aumentar o TTL exponenciamente. APM.
* Ele não falou no artigo, mas usou tamanhos menores de blocos no experimento que o BitTorrent normal. Essa é uma boa idéia para nós móveis uma vez que a conectividade pode mudar muito já que os nós são móveis.
- Meio picareta o BTM mostrar um node degree mais alto que o BTI simplesmente pelo fato de haver proxy seeds. Na conclusão ele diz que assim ele consegue armotizar mais o custo de download, mas isso é uma bobagem pq ele só aumentou o custo de download do seed original que teve que repassar os arquivos inteiros para os proxy seeds. Além disso, isso não serve para casos em que o arquivo não é popular pq ele vai ser replicado e dificilmente vai ser reutilizado em outro nó.

Trechos relevantes
BTM is a cross-layer P2P system which takes advantage of the routing layer activities in the MANET for collecting key/peer information for the smooth functioning of BTM at the application layer.
Of all of the above proposed P2P systems for the wired Internet, BitTorrent has certain distinctive features which are advantageous in the context of MANETs.
*The overlay construction in BitTorrent is on-demand—the peer overlay is not constructed until a client enters the P2P system, at which time a tracker node (whose ID is known) is contacted by the client for a list of peers which are currently downloading the file or hold a full copy of the file (and are willing to share with other peers). Thus, peer discovery essentially involves a constant overhead in BitTorrent, and does not depend on how far from the client the peers are located.
*Moreover, the peer overlay changes during the duration of file download, because clients are in contact with the tracker node through the duration of the download (and request a peer list periodically), and this directly affects the file download at the BitTorrent client because the BitTorrent client simultaneously downloads pieces of the file from all members of the overlay. In contrast, clients in Gnutella and Napster download their file from one peer over an overlay that may change, but has no effect on the file download at a client.
*In addition, BitTorrent is concerned with amortizing the cost of download of the file across the network. That is, in BitTorrent, the cost of the download of a particular file at a client is not fully borne by one peer, but instead borne by multiple peers in the system. In BitTorrent, because the file is downloaded piece-by-piece, and because these pieces are of a pre-determined order, size and number, a BitTorrent client can resume download easily after long periods of disconnection from the network. One obvious advantage of this mechanism is that a BitTorrent client can start serving the file it is downloading to other peers as soon as the BitTorrent client downloads the first piece of the file.
*All of the above properties allow BitTorrent to circumvent a number of issues which typical P2P system designs for MANETs face, thus making BitTorrent an attractive P2P system to adapt for MANETs.

Despite the above advantages, BitTorrent is not immediately usable in the MANET context owing to some obvious disadvantages.
*The BitTorrent model is inherently centralized with respect to the tracker node operations—the presence of a single tracker node, which provides each client with the list of peers currently downloading a file, makes peer overlay construction simple, but also raises the issue of single point of failure of the tracker. -Likewise, when all nodes with a full copy of a file (seed nodes) leave the network, BitTorrent clients are no longer able to download the full file, if the undownloaded pieces are not available at other clients in the P2P system.
*Lastly, network partitions make accessing the tracker/seed difficult, and potentially stall the client download process indefinitely.

Unlike the wired Internet in which not all the nodes are routers, any node in a MANET may perform routing activities and is thus aware of topological information. Using a cross-layer interface in the protocol stack, the network layer topology information can be used to make effective decisions for key and peer lookup at the BitTorrent (application) layer.

In the MANET context, the effect of changing peer overlay on piece download at the client is greater, given node mobility and other issues such as partitions.