<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML><HEAD>
<META http-equiv=Content-Type content="text/html; charset=iso-8859-1">
<META content="MSHTML 6.00.3790.2666" name=GENERATOR></HEAD>
<BODY>
<DIV dir=ltr align=left><SPAN class=531460003-04052006><FONT face=宋体 size=2>My
thoughts on the two issues Bryan brings:</FONT></SPAN></DIV>
<DIV dir=ltr align=left><SPAN class=531460003-04052006><FONT face=宋体
size=2></FONT></SPAN> </DIV>
<DIV dir=ltr align=left><SPAN class=531460003-04052006><FONT face=宋体 size=2>On
fairness</FONT></SPAN></DIV>
<DIV dir=ltr align=left><SPAN class=531460003-04052006><FONT face=宋体
size=2></FONT></SPAN> </DIV>
<DIV dir=ltr align=left><SPAN class=531460003-04052006><FONT face=宋体 size=2>Both
are saying something true. The point is whether the experiments carried out
capture any situation that seeders are scarce. </FONT></SPAN></DIV>
<DIV dir=ltr align=left><SPAN class=531460003-04052006><FONT face=宋体
size=2></FONT></SPAN> </DIV>
<DIV dir=ltr align=left><SPAN class=531460003-04052006><FONT face=宋体 size=2>But
generally I don't think free-riders can be eliminated even with a byte-for-byte
fairness heuristic. For example, free-riders contributes nothing,
but if their downloading bandwidths are also small (compare
with other leechers), the fair share offered by seeders can well
saturate this capacity. Also joining peers without any information of
the free riders and optimistic unchoking inevitably feed the free
riders. [1] tries to replace optimistic unchoking by estimate the bandwidth
between peers, how well does this work? I don't know if any better approaches
can solve this problem.</FONT></SPAN></DIV>
<DIV dir=ltr align=left><SPAN class=531460003-04052006><FONT face=宋体
size=2></FONT></SPAN> </DIV>
<DIV dir=ltr align=left><SPAN class=531460003-04052006><FONT face=宋体 size=2>The
good thing is, bitTorrent introduce seeders to provide extra resources. And if
we want to prove/disprove the current algorithm is not efficient esp. when
uploading capacity is rare, two things should be demonstrated:
</FONT></SPAN></DIV>
<DIV dir=ltr align=left><SPAN class=531460003-04052006><FONT face=宋体 size=2>1.
whether peers can pick up optimal remote downloaders in the
neighborhood quickly. </FONT></SPAN></DIV>
<DIV dir=ltr align=left><SPAN class=531460003-04052006><FONT face=宋体
size=2>2. If they can do 1, how much performance loss they undertake by the
current optimistic unchoking algorithm; if they cannot, how far from
optimal do we expect the downloader selection.</FONT></SPAN></DIV>
<DIV dir=ltr align=left><SPAN class=531460003-04052006><FONT face=宋体
size=2></FONT></SPAN> </DIV>
<DIV dir=ltr align=left><SPAN class=531460003-04052006><FONT face=宋体
size=2></FONT></SPAN> </DIV>
<DIV dir=ltr align=left><SPAN class=531460003-04052006><FONT face=宋体 size=2>On
Network Coding</FONT></SPAN></DIV>
<DIV dir=ltr align=left><SPAN class=531460003-04052006><FONT face=宋体
size=2></FONT></SPAN> </DIV>
<DIV dir=ltr align=left><SPAN class=531460003-04052006><FONT face=宋体 size=2>I am
not really familiar with network coding, the only example in P2P I read is
"Network Coding for Large Scale Content Distribution" [2]. But network coding
often requires a global view or good heuristics on what to generate. In
[2], to generate highly needed (innovative in this article) needs
communication among the neighbors. Anybody knows some real-world,
large-scale P2P system that provides realistic data?</FONT></SPAN></DIV>
<DIV><FONT face=宋体 size=2></FONT> </DIV>
<DIV><FONT face=宋体 size=2></FONT> </DIV>
<DIV><FONT face=宋体 size=2></FONT> </DIV>
<DIV><FONT face=宋体><FONT size=2>Nice<SPAN class=531460003-04052006> article,
Arnaud, I think I've read your previous article on BitTorrent months ago. Very
solid data, and I'm curious on your methodology in choosing the sessions
(as they should be representative).</SPAN></FONT></FONT></DIV>
<DIV><FONT face=宋体 color=#0000ff size=2></FONT> </DIV>
<DIV><FONT size=2><SPAN class=531460003-04052006>[1</SPAN>] AR Bharambe, C.
Herley, and VN Padmanabhan, "Analyzing and. improving bittorrent performance,"
Technical Report, MSR-TR-2005-03</FONT></DIV>
<DIV><SPAN class=531460003-04052006><FONT size=2>[2] </FONT></SPAN><FONT
color=#0000ff><A
href="http://research.microsoft.com/~pablo/papers/nc_contentdist.pdf"><FONT
face=宋体><FONT
size=2>http://research.microsoft.com/~pablo/papers/nc_contentdist.pdf</FONT></FONT></A></FONT></DIV><!-- Converted from text/plain format -->
<P><FONT size=2>--<BR>Ranus Yue<BR>Tsinghua University<BR></FONT></P>
<DIV><FONT face=宋体 color=#0000ff size=2></FONT> </DIV><FONT face=宋体
color=#0000ff size=2></FONT><BR>
<BLOCKQUOTE
style="PADDING-LEFT: 5px; MARGIN-LEFT: 5px; BORDER-LEFT: #0000ff 2px solid; MARGIN-RIGHT: 0px">
<DIV class=OutlookMessageHeader lang=zh-cn dir=ltr align=left>
<HR tabIndex=-1>
<FONT face=Tahoma size=2><B>From:</B> p2p-hackers-bounces@zgp.org
[mailto:p2p-hackers-bounces@zgp.org] <B>On Behalf Of </B>Bryan
Turner<BR><B>Sent:</B> Thursday, May 04, 2006 1:57 AM<BR><B>To:</B>
Peer-to-peer development.<BR><B>Subject:</B> Re: [p2p-hackers] paper "rarest
first and choke algorithms are enough"<BR></FONT><BR></DIV>
<DIV></DIV>Arnaud,<BR><BR> Thanks for the new paper, there
is a lot of nice data here. The presented graphs and analysis indeed
suggest that the BitTorrent protocol's choices achieve near-optimal data
distribution in its paradigm (single file, block-based content
distribution). I agree with your suggestions for fairness criteria, and
my own suggestions are similar (my suggestion is for a reputation-based system
to model leechers and free-riders). <BR><BR> However, I
disagree with several conclusions you make along the way. A brief
overview:<BR>- Byte-for-byte fairness is not appropriate<BR>- Network Coding
is not justified<BR><BR>Fairness:<BR><BR> I am unconvinced by the
arguments against byte-for-byte fairness. Your evidence to support this
is that tit-for-tat does not take into account the excess capacity of some
torrents (ie: more seeders than leechers). Yet this situation is
equivalent under byte-for-byte and choking rules. Leechers are upholding the
byte-for-byte policy (seeders cannot, as you mention) and thus only leechers
are restricting their upload capacities to free-riders, and rightly so.
Seeds (who hold the excess capacity) are distributing this capacity fairly to
all peers. Thus, choking and byte-for-byte are equivalent in this regard
- free riders receive a share of the bandwidth equal to the fair distribution
given by seeders in both cases. <BR><BR> The more important
case, when excess capacity is not available, free riders should be eliminated
or diminished. Because leecher participation cannot be proven, the only
other method of measurement is via equal exchange of services.
Byte-for-byte is one such measurement (reputation systems are another).
In this scenario, free riders will only receive a small credit from the
leechers in the swarm before having to resort to hand-outs from the
seeds. With the seeds giving fair capacity to the swarm, the free riders
will receive very little of the swarm capacity, while the participating
leechers will receive fair resources. <BR><BR> Free riders
always receive more resources under choking than under exchange measurement
models.<BR><BR>Network Coding:<BR><BR> On the topic of
Network Coding [1], I did not see any evidence in your paper refuting the
network coding literature. Please correct me if I missed it, but it
appears your only rebuttal is in the poor modeling of BitTorrent, not in the
application of network coding techniques. From this I don't see how you
conclude that network coding is not justified? I agree that most of the
simulation literature does not model BitTorrent correctly, but this doesn't
negate the positive results of the network coding trials, only their
comparisons to BitTorrent. <BR><BR> In section 4-A, pp 6-7, you
suggest that source or network coding may not propose interesting pieces to
peers during the startup phase. I counter that this is exactly what
network coding solves - every packet has an innovation rate based on the
network flows from the local node to the source(s). Assuming a densely
connected graph with fair sharing from the seeder, it is unlikely that any
packet is not innovative during the startup phase. Unless the local
node's bandwidth is many multiples of the seeder, a problem which is not
specific to network coding. <BR><BR> Network Coding is superior to
Rarest First and other BitTorrent-like protocols for several reasons:<BR>1)
The innovation rate is the min-cut of all flows from the local node to the
source(s), which is likely to be much larger than BitTorrent's default of 4
active connections. <BR>2) BitTorrent transfers pieces in blocks-at-a-time,
but only advertises in piece-at-a-time. This injects a significant delay
between downloading of an innovative byte and sharing of that byte (on
average, one half the download time of an entire piece). Network coding
imposes no such delay. <BR>3) There is no first-blocks or last-blocks problem
with network coding, they are entirely non-issues. Large portions of
your paper are devoted to these issues which simply don't occur under network
coding.<BR>4) The meta-network utilization is higher for network coding.
That is, since BitTorrent cannot align to the underlying physical connections
of the network elements, it is impossible to maximally utilize them.
Network coding (using an innovation rate tracking algorithm) can rapidly align
to the structure of the physical network, eliminating cross-core
retransmissions. This saves a significant amount of ISP bandwidth and
reduces the overall burden of supporting filesharing services on the internet.
<BR><BR>Of course, network coding does have cons also:<BR>- Typically larger
memory footprint<BR>- Typically larger CPU requirements (falling rapidly with
new research)<BR>- Typically more complex supporting protocols (innovation
tracking, security checks, etc) <BR><BR> Is the full
implementation of Network Coding superior enough to BitTorrent that it offers
compelling reasons for migration to it as a solution? Your paper argues
that BitTorrent is "good enough", and I tend to agree. <BR><BR>Please
discuss! :-)<BR>--Bryan<BR><A
href="mailto:bryan.turner@pobox.com">bryan.turner@pobox.com</A><BR><BR>[1]
Network Coding: An Instant Primer - <A
href="http://infoscience.epfl.ch/search.py?recid=64508">http://infoscience.epfl.ch/search.py?recid=64508
</A><BR><BR><BR>
<DIV><SPAN class=gmail_quote>On 5/3/06, <B class=gmail_sendername>Arnaud
Legout</B> <<A
href="mailto:Arnaud.Legout@sophia.inria.fr">Arnaud.Legout@sophia.inria.fr</A>>
wrote:</SPAN>
<BLOCKQUOTE class=gmail_quote
style="PADDING-LEFT: 1ex; MARGIN: 0pt 0pt 0pt 0.8ex; BORDER-LEFT: rgb(204,204,204) 1px solid">Hello,<BR><BR>we
have a new paper called "rarest first and choke algorithms are
enough"<BR>that is about an experimental evaluation of the two core
BitTorrent<BR>algorithms<BR>on real torrents.<BR><BR>A. Legout, G.
Urvoy-Keller, and P. Michiardi. Rarest First and Choke <BR>Algorithms Are
Enough. Technical Report<BR>(inria-00001111, version 1 - 13 February 2006),
INRIA, Sophia Antipolis,<BR>February 2006.<BR><A
href="http://hal.inria.fr/inria-00001111/en">http://hal.inria.fr/inria-00001111/en
</A><BR><BR>Comments are welcomed.<BR><BR>Regards,<BR>Arnaud
Legout.<BR><BR>--<BR>Arnaud Legout, Ph.D.<BR><BR>INRIA Sophia Antipolis -
Plančte Phone : 00.33.4.92.38.78.15<BR>2004 route des lucioles -
BP 93 Fax : 00.33.4.92.38.79.78 <BR>06902 Sophia
Antipolis CEDEX E-mail: <A
href="mailto:arnaud.legout@sophia.inria.fr">arnaud.legout@sophia.inria.fr</A><BR>FRANCE Web
: <A
href="http://www-sop.inria.fr/planete/Arnaud.Legout/index.html">http://www-sop.inria.fr/planete/Arnaud.Legout/index.html</A><BR></BLOCKQUOTE></DIV><BR></BLOCKQUOTE></BODY></HTML>