Explore
For Enterprise
Join for Free
Log In

Artes e Humanas
Negócios
Ciência da Computação
Ciência de Dados
Tecnologia da informação
da saúdesaúde
Matemática e Lógica
Desenvolvimento Pessoal
Ciência e Engenharia Física
Ciências Sociais
Línguas
Notas
Certificados

Explore todo o Coursera

Navegar
Pesquisar
For Enterprise
Entrar
Inscreva-se gratuitamente

4. FastTrack and BitTorrent

Loading...

Cloud Computing Concepts, Part 1

Universidade de Illinois em Urbana-ChampaignUniversidade de Illinois em Urbana-Champaign

4.5 (716 classificações) | 63K alunos inscritos

Curso 1 de 6 no Computação em nuvemComputação em Nuvem Programa de cursos integrados

Cloud computing systems today, whether open-source or used inside companies, are built using a common set of core techniques, algorithms, and design philosophies – all centered around distributed systems. Learn about such fundamental distributed computing "concepts" for cloud computing. Some of these concepts include: clouds, MapReduce, key-value/NoSQL stores, classical distributed algorithms, widely-used distributed algorithms, scalability, trending areas, and much, much more! Know how these systems work from the inside out. Get your hands dirty using these concepts with provided homework exercises. In the programming assignments, implement some of these concepts in template code (programs) provided in the C++ programming language. Prior experience with C++ is required. The course also features interviews with leading researchers and managers, from both industry and academia.

Visualizar o programa do curso

Habilidades que você aprenderá

Distributed Algorithm, Distributed Computing, C++, Cloud Computing

Avaliações

4.5 (716 classificações)

5 stars
485 ratings
4 stars
155 ratings
3 stars
38 ratings
2 stars
16 ratings
1 star
22 ratings

WK

Feb 27, 2018

This is a great course with a good balance of just theory and concepts, with practical ideas and exercises. The programming exercise can be a bit annoying, but was enjoyable nonetheless.

VR

Dec 31, 2017

very happy with the course. got to know new concepts. assignments are awesome. enjoyed working on them. enjoyed the course. it would be good if we get a color and original certificate.

Na lição

Week 3: P2P Systems

P2P systems: This module teaches the detailed design of two classes of peer to peer systems: (a) popular ones including Napster, Gnutella, FastTrack, and BitTorrent; and (b) efficient ones including distributed hash tables (Chord, Pastry, and Kelips). Besides focusing on design, the module also analyzes these systems in detail.

1. P2P Systems Introduction5:44

3. Gnutella20:15

4. FastTrack and BitTorrent7:11

6. Failures in Chord14:53

Ministrado por

Indranil Gupta
Professor

Transcrição

In this lecture we will quickly review,

uh, FastTrack and BitTorrent,

uh, two systems that are also very popular

and have been very popular, uh, for many years now.

So FastTrack is, um, uh, in a sense derived from Gnutella

and is a hybrid between Gnutella and Napster.

Uh, it's a better version Gnutella by, um,

the fact that it uses some of the "healthier" participants,

some of the more powerful peers in the system,

uh, to make the system faster.

FastTrack is a proprietary system.

It's the underlying technology

in Kazaa, KazaaLite and Grokster.

Uh, though it's proprietary, some of the details are known,

and that's what we're gonna discuss, uh, here.

So FastTrack, for the most part, is just like Gnutella.

It maintains an overlay graph,

but some of the peers, uh, have some special, uh, duties,

and these peers are known as supernodes.

So this is what a FastTrack system might look like.

Uh, it looks just like a-a Gnutella overlay,

except that two of the peers,

marked as "S" over here, are supernodes.

Uh, these peers might, uh,

undertake some of the responsibilities

very similar to, uh, Napster, uh, peers

in the sense that they might be storing directory information

that are used by its neighboring peers

in the overlay to search for files.

So a supernode stores a directory listing of

a subset of a nearby, um, uh,

filename, uh, peer pointer lists,

uh, similar to what Napster servers were doing.

Uh, the supernode membership might change over time.

Essentially, a peer, uh, cannot select itself to be a supernode.

Instead, peers are selected to be supernodes

based on their contributions in the past.

Uh, essentially, uh, this contribution is decided

from a reputation level.

For instance, in KazaaLite, the participation level,

the reputation, of a user is between 0 and 1,000.

When a user joins the system, their reputation is 10.

If the user has, uh, prolonged periods of connectivity

and more uploads from that, uh, client,

their reputation goes up, or the participation level goes up.

When the participation level crosses a threshold, uh,

the peer might become a supernode.

Uh, there are also a lot of, uh,

uh, sophisticated reputation schemes

that have been invented in, um, the academic literature.

Uh, there is an entire, uh, workshop called P2PEcon,

which, um, you might want to look at if you're interested,

that covers some of, uh, these ideas.

With this, uh, the, uh, peers, um, can now search much faster.

They can just search in nearby supernode,

going back to the previous figure.

This peer on the bottom left corner can now

simply send a query,

its query to, ah, its neighboring supernode

instead of flooding the query

throughout the entire overlay graph.

Uh, why is there an advantage to being a supernode?

What is the incentive to be a supernode?

Well, a lot of your queries and searches now become

just local searches in your local uh, data structure

or your local directory information,

and so they do not incur any network traffic.

They are really, really fast.

BitTorrent is one of these systems

that has been very popular and continues to be popular.

Uh, it has a lot of similarities

with the systems that we have discussed so far,

but it works in slightly different ways, uh,

by incentivizing peers to participate in the system.

Remember that we discussed that peers oftentimes

do not contribute anything to the system.

They do not contribute files,

they do not contribute even bandwidth in many cases,

and BitTorrent addresses this by having incentives,

um, uh, for the peers to participate

so that the peers can benefit from,

uh, being unselfish and helping other peers.

So how does, uh, BitTorrent work?

Well, BitTorrent has a notion of trackers.

Uh, typically there is one tracker per file.

Uh, there might also be trackers for multiple files.

When a peer wants to join the system,

you f-somehow find, uh, the torrent or the tracker,

uh, and this, uh, enables you to talk to the tracker.

The tracker, uh, maintains a list of some of the peers

that are currently transferring that file.

Uh, it does so by receiving heartbeats

from, uh, the current, uh, peers

heartbeat messages, uh, from these peers.

The peers are of two kinds, a seed, which has a full file

and is still continuing to be, um, uh, part of the system

and help the other peers download the file,

and the leechers, which has some blocks from the file,

a file is split up into blocks,

[silence]

typically equal sized blocks,

and, uh, this peer has some of the files

and is still looking to download

the other, uh, blocks of that particular file.

The new peer, when it joins this particular, uh, group of peers,

uh, is also a leecher because it has, obviously,

none of the blocks of that particular file.

A file is typically split into blocks.

Uh, the block size is fixed,

maybe somewhere between 32 kilobytes to 256 kilobytes.

Uh, now when a peer starts to download a file

from some of its neighbors,

remember, going back to the previous slide,

the peer, when it joins, uh, when it joins the group,

it has some neighboring peers,

and it has multiple blocks that it can download

and multiple peers from which it can download,

uh, each of these blocks.

How does it select which block to download

and which peer to download from?

Well, it uses the Local Rarest First policy.

Essentially, um, it prefers that block

which is the least replicated among its current neighbors.

Uh, this is useful because-

because with churn in the system,

some of these blocks might disappear

quicker than other blocks, uh, and earlier than other blocks

that are replicated more among its neighbors.

And so, uh, this Local Rarest First policy helps

to download those blocks that are the rarest.

There are of course exceptions to this.

Uh, a new node, newly joining peer, is allowed to pick one,

uh, neighbor at random, and this helps in bootstrapping

so that you don't always get stuck, uh,

with just one deterministic group.

Now incentives are provided

by a tit-for-tat bandwidth usage scheme.

Um, uh, this incentivizes a peer to provide blocks to neighbors,

uh, so that, um, you-you're providing blocks

to neighbors that provided you

the best download rates in the past, okay?

So this, uh, enables or incentivizes your neighbors

to provide download, uh, speed to you

so that you are then able to provide,

uh, blocks to it in the future.

And the seeds do the same too, not just the leechers.

Now, the number of, uh, concurrent transfers

that might go on for-from a peer to its neighboring peers

might become very large,

um, so you don't want this to overload the, uh, peer itself,

and so choking is used here.

Choking limits the number of neighbors

to which concurrent uploads are going on.

Um, uh, typically this is a n-small number like 5.

Uh, these are the best neighbors.

Everyone else is considered to be choked.

These selected neighbors are considered to be unchoked.

Uh, you periodically reevaluate this set, say every 10 seconds,

and you do an optimistic unchoke,

so periodically you unchoke a random neighbor.

This helps keep the, uh, set of neighbors that are unchoked,

uh, to be very, very fresh.

Okay, and again, this is used, uh, because the set of blocks

that are-that are peers is changing,

and also the set of peers in your group is changing

because of, uh, churn.

Okay, so choking, in summary, helps peers to,

um, uh, limit how many other peers they're, uh, uploading to,

uh, so that the upload bandwidth is, uh, not overwhelmed.

Explore nosso catálogo

Registre-se gratuitamente e obtenha recomendações, atualizações e ofertas personalizadas.

O Coursera proporciona acesso universal à melhor educação do mundo fazendo parcerias com as melhores universidades e organizações para oferecer cursos on-line.

© 2019 Coursera Inc. Todos os direitos reservados.

Baixar na App Store

Baixar no Google Play

Coursera
Sobre
Liderança
Carreiras
Lista de cursos
Certificados
Certificados MasterTrack™
Notas
For Enterprise
For Government

Comunidade
Learners
Partners
Developers
Beta Testers
Translators

Conectar
Blog
Facebook
LinkedIn
Twitter
Instagram
YouTube
Tech Blog

Mais
Termos
Privacidade
Ajuda
Acessibilidade
Imprensa
Contato
Diretório
Afiliados