Subject: Re: [p2pi] Refining the ALTO problem statement [Was: Re: discussing P2PI-related standardization in Dublin]

From: Laird Popkin <[email-masked]>
Date: Fri, 13 Jun 2008 08:14:53 -0400 (EDT)

This is a great discussion.

One point I'll make related to the signaling protocol for querying the "oracle" is that while the "send in a list of peer IP addresses and receive a sorted list back" approach is appealing in its simplicity, it has some serious limitations that would need to be taken into account. 

It's important to keep in mind that optimizing peer selection for p2p transfers has the most impact for large swarms. That is, if there are only 20 people on the planet that can serve you data, (1) it doesn't take too long to connect to all of them so optimized peer selection doesn't save much peer connection time, and (2) the odds of any of them being in the same ISP is fairly low, so optimized peer selection doesn't affect data flow much. Optimizing peer selection is focused on swarms with very large numbers of peers. For example, we often see swarms with thousands or tens of thousands of peers. These are a small percentage of swarms, of course, but they are responsible for a disproportionately large volume of data. For example, when Yale surveyed "major tracker sites" they saw that a very small percentage of swarms had 100+ peers, but that those swarms were responsible for well over 50% of downloads. For perspective, at Pando, we see swarms with thousands to tens of thousands of peers fairly often.

It is for these large sarms where the "list of IPs" approach runs into some pragmatic issues:
- The "oracle" must be sent the current complete set of IPs in each swarm. This means that the queries would be very large (e.g. a list of 1,000 IP addresses). This is not very cacheable, because swarm composition is highly dynamic. And it has to be a complete list, or the value of the guidance degrades dramatically. (Conceivable this could be implemented as 'delta' updates, but that raises oracle state issues, makes the software and protocol much more complex, etc.).
- The "oracle" would have to maintain state (or recompute on every query) for every swarm in every p2p network.
- The volume of queries would be very large (perhaps on the order of 100K queries per second, across all p2p networks operating within an ISP).
- The queries cannot be cached (because the first announce is the most important to optimize, and following queries need to include all new peers, and each query generates a response unique to the peer being provided the guidance).
- The ISP would need to scale the "oracle" capacity to satisfy this volume.
- It exposes the entire membership and data flow of the p2p network to the ISPs, which raises obvious legal and privacy issues. Imagine asking your lawyers whether they want to run Pirate's Bay's Trackers.
- It makes every Tracker announce slow, expensive and unreliable instead of fast, cheap and reliable.

This is why we shifted (in the P4P approach) away from the more obvious IP list approach to moving the guidance into the Tracker's memory. Admittedly that does require ISPs to expose some abstract guidance information (IP prefixes and percentages), but in return:
- The communication from the "oracle" to the p2p network is a single asynchronous update (e.g. as little as one message every hour) instead of one message per peer announce per swarm.
- The p2p network's Tracker can process peer requests in-memory, without having to make a blocking network call to an external "oracle". This is several orders of magnitude faster, more reliable, and far less resource intensive.
- There's minimal information exposed between the ISP and the P2P network (which is, from a legal and privacy angle, better for both P2P and ISP).

- Laird Popkin, CTO, Pando Networks
  mobile: 646/465-0570

----- Original Message -----
From: "stefano previdi" <[email-masked]>
To: "Enrico Marocco" <[email-masked]>, [email-masked]
Sent: Friday, June 13, 2008 4:52:29 AM (GMT-0500) America/New_York
Subject: Re: [p2pi] Refining the ALTO problem statement [Was: Re: discussing P2PI-related standardization in Dublin]

Enrico,

I mostly agree mostly with everything below. My suggestion (as a routing guy
more than an apps guy) is also to scope what could be extended/enhanced in
routing protocols in order to improve localization mechanisms (whatever they
are). 

As an example, we have extended ISIS routing protocol in order to carry some
application related information (at this stage is an empty container) and
probably these kind of enhancements may have a use in localization/oracle
services.

s.

> From: Enrico Marocco <[email-masked]>
> 
> Peterson, Jon wrote:
>> The proposal for the ALTO BoF (which roughly covers (3)) is now in the
>> BoF tracker. You can read about it at its home page:
>> 
>> http://alto.tilab.com/
> [...]
>> we hope that discussions surrounding the BoF could elucidate the proper
>> division of labor and approach to this problem.
> 
> To follow up on Jon's thoughts and to reflect discussions that happened
> during the MIT workshop and on the mailing list, Vijay and I are going
> to update the problem statement draft the ALTO BoF proposal is based on
> (draft-marocco-alto-problem-statement-00).
> 
> As a prelude to focus the ALTO BoF, it would be great to start
> coalescing community agreement on ensuring that the scope of the problem
> is well defined and understood.
> 
> Essentially, the problem that ALTO will attempt to solve is this:
> applications (P2P and otherwise) that make intensive use of the network
> bandwidth or want to make decisions to optimize some function (see use
> cases) may be interested in choosing all or some of their peers based on
> recommendations provided by some network entity -- colloquially called
> an oracle -- that has more of a global view on the peers in the network,
> their topological distances, and their capabilities than the application
> itself does.
> 
> In thinking about the problem, it may help to consider the following:
> 
> + Use cases: current version of the draft identifies four use cases for
>   ALTO solutions (file-sharing, VoIP, p2p streaming and DHTs) but others
>   come to mind (e.g. cache/http-mirror selection, CDN).  At the MIT
>   workshop, Ted Hardie coined the term "unattended consequences" of
>   peer-to-peer nodes where traffic runs constantly for as long as the
>   resources to that node are popular.  Video feeds to remote stations
>   were identified as a category.
> 
> + Third-party services: even if topology information is directly
>   available to network operators, nothing should prevent third-parties
>   to provide peer selection services alternatively to or in competition
>   with ISPs.  An incomplete list of proposed solutions for providing
>   such services is online at http://alto.tilab.com/resources.html;
> 
> + Type(s) of information that are likely provided by the oracle (note
>   that a third-party oracle may not have access to some of this
>   information):
>   * Given a list of peer candidate IP addresses, sort them according to
>     preferences (topological proximity, bandwidth constraints, etc.) and
>     return to querying application;
>   * Ability for an application to determine its network location and
>     proximity to other nodes;
>   * Support for cost and charging information for application so that
>     applications can make appropriate trade-offs;
>   * Capabilities and characteristics of peers (i.e., last hop bandwidth,
>     etc.);
>   * Network policies;
>   * ...
> 
> + Type(s) of information that is provided to the oracle for rendering an
>   equitable decision:
>   * List of peer candidate IP addresses;
>   * Parameter to optimize (cost, delay, ...);
>   * ...
> 
> This is mainly what we have captured so far; however, feedback,
> suggestions and contributions are not only welcome, but at this time
> even required for the successful setting of a BOF.
> 
> Besides, the draft currently identifies two elements for which
> standardization work would be required, namely a discovery mechanisms
> for locating oracles and a signaling protocol for querying them.  Do
> people think the core solution for ALTO should include anything else?
> 
> -- 
> Ciao,
> Enrico
> _______________________________________________
> p2pi mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/p2pi

_______________________________________________
p2pi mailing list
[email-masked]
https://www.ietf.org/mailman/listinfo/p2pi
_______________________________________________
p2pi mailing list
[email-masked]
https://www.ietf.org/mailman/listinfo/p2pi

---

From: stefano previdi <[email-masked]>
Date: Fri, 13 Jun 2008 15:01:32 +0200

Hi Laird,

I understand your concern and let me try to answer from a routing
implementation perspective. My thoughts are as follows:

- the options of having a list of IP addresses to rank may be faced to some
limitations but I probably have different view. I believe one alternative is
to have a ranking of _pair_ of IP addresses (I believe there's a proposal
made already on this direction). It doesn't address scalability per se but
it allows other form of oracle/proximity capability.

- From a routing algorithm perspective (and its implementation). The
localization of 10 Vs. 1000 addresses may not incur an exponential
complexity. I fact, routing algorithms/implementations are faced to this
problem for years now... ;-) In the last years a lot of work has been done
in the routing layer in order to improve performance and to minimize the
impact of routing computations. We are now leveraging all this work in order
to address other type of routing paradigms (using the same input).

- State can be kept even if it results from different computations. This
allows an "oracle/proximity" provider to minimize the amount of computation
and to be able do deliver results on-the-fly.

- There are apps models that have some form of hierarchy (e.g: trackers) and
some others not. Should we have different models in the oracle too, or
should we try to be as much as possible transparent/agnostic ? I'd vote for
the latter.

- I can't speak much about the legal/psychological issue (disclosing p2p
addresses to SP) as I come from bottom layers, but what I can say is that,
technically, the SP doesn't need any form of oracle in order to understand
who among his customers is a p2p addicted... ;-)

- In one point we're in violent agreement: This is a great discussion.

Thanks.

s.

> From: Laird Popkin <[email-masked]>
> 
> One point I'll make related to the signaling protocol for querying the
> "oracle" is that while the "send in a list of peer IP addresses and receive a
> sorted list back" approach is appealing in its simplicity, it has some serious
> limitations that would need to be taken into account.
>
> It's important to keep in mind that optimizing peer selection for p2p
> transfers has the most impact for large swarms. That is, if there are only 20
> people on the planet that can serve you data, (1) it doesn't take too long to
> connect to all of them so optimized peer selection doesn't save much peer
> connection time, and (2) the odds of any of them being in the same ISP is
> fairly low, so optimized peer selection doesn't affect data flow much.
> Optimizing peer selection is focused on swarms with very large numbers of
> peers. For example, we often see swarms with thousands or tens of thousands of
> peers. These are a small percentage of swarms, of course, but they are
> responsible for a disproportionately large volume of data. For example, when
> Yale surveyed "major tracker sites" they saw that a very small percentage of
> swarms had 100+ peers, but that those swarms were responsible for well over
> 50% of downloads. For perspective, at Pando, we see swarms with thousands to
> tens of thousands of peers fairly often.
> 
> - The "oracle" must be sent the current complete set of IPs in each swarm.
> This means that the queries would be very large (e.g. a list of 1,000 IP
> addresses). This is not very cacheable, because swarm composition is highly
> dynamic. And it has to be a complete list, or the value of the guidance
> degrades dramatically. (Conceivable this could be implemented as 'delta'
> updates, but that raises oracle state issues, makes the software and protocol
> much more complex, etc.).
>
> - The volume of queries would be very large (perhaps on the order of 100K
> queries per second, across all p2p networks operating within an ISP).
> - The queries cannot be cached (because the first announce is the most
> important to optimize, and following queries need to include all new peers,
> and each query generates a response unique to the peer being provided the
> guidance).
> - It exposes the entire membership and data flow of the p2p network to the
> ISPs, which raises obvious legal and privacy issues. Imagine asking your
> lawyers whether they want to run Pirate's Bay's Trackers.
> This is why we shifted (in the P4P approach) away from the more obvious IP
> list approach to moving the guidance into the Tracker's memory. Admittedly
> that does require ISPs to expose some abstract guidance information (IP
> prefixes and percentages), but in return:
> - The communication from the "oracle" to the p2p network is a single
> asynchronous update (e.g. as little as one message every hour) instead of one
> message per peer announce per swarm.
> - The p2p network's Tracker can process peer requests in-memory, without
> having to make a blocking network call to an external "oracle". This is
> several orders of magnitude faster, more reliable, and far less resource
> intensive.
> - There's minimal information exposed between the ISP and the P2P network
> (which is, from a legal and privacy angle, better for both P2P and ISP).
>

---

From: Enrico Marocco <[email-masked]>
Date: Fri, 13 Jun 2008 16:37:33 +0200

Laird Popkin wrote:
> "oracle" is that while the "send in a list of peer IP addresses and
> receive a sorted list back" approach is appealing in its simplicity, it
> has some serious limitations that would need to be taken into account.

Actually I used the term "oracle" in a general way, to refer to servers
providing information useful for peer selection.  The "sorting" oracle
is only one proposed approach for addressing the problem of p2p traffic
optimization.  Other competing or complementary approaches, e.g. based
on network coordinates or topology/policy information, have both
advantages and disadvantages in respect to it.

The main goal of ALTO is to compare the different approaches on a
technical basis with a view towards standardization

---

From: Stephane Bortzmeyer <[email-masked]>
Date: Fri, 13 Jun 2008 17:12:46 +0200

On Fri, Jun 13, 2008 at 04:37:33PM +0200,
 Enrico Marocco <[email-masked]> wrote 
 a message of 112 lines which said:

> The "sorting" oracle is only one proposed approach for addressing
> the problem of p2p traffic optimization.  Other competing or
> complementary approaches, e.g. based on network coordinates or
> topology/policy information, have both advantages and disadvantages
> in respect to it.
> 

As a beginner in this list, I request more explanations. Reading
draft-marocco-alto-problem-statement-00, I had the impression that
ALTO only follows one approach, "optimizing traffic generated by P2P
applications Using Information Provided By Isps And Network
Operators" (section 1).

I'm a big fan of ICS myself but are they really on-topic? Or is it too
early to say?
_______________________________________________
p2pi mailing list
[email-masked]
https://www.ietf.org/mailman/listinfo/p2pi

---

From: "Vijay K. Gurbani" <[email-masked]>
Date: Fri, 13 Jun 2008 10:23:01 -0500

Stephane Bortzmeyer wrote:
> As a beginner in this list, I request more explanations.

Stephane: I am not sure how recently you joined the list, but
there were a fair amount of papers and viewpoints presented at
the MIT workshop in May 2008.  In case you do not have access
to those, here here is a link to the final set of papers and
summary slides that were discussed at the workshop:

http://idisk.mac.com/cullenfluffyjennings-Public?view=web

> Reading draft-marocco-alto-problem-statement-00, I had the impression
> that ALTO only follows one approach, "optimizing traffic generated by
> P2P applications Using Information Provided By Isps And Network 
> Operators" (section 1).

A good summary of the approaches, including ALTO, that came
out of the workshop is also discussed in Lars' follow-up email,
which can be accessed at:
http://www.ietf.org/mail-archive/web/p2pi/current/msg00068.html

> I'm a big fan of ICS myself but are they really on-topic? Or is it
> too early to say?

I am sorry but could you please expand on "ICS"?

Thanks,

- vijay
-- 
Vijay K. Gurbani, Bell Laboratories, Alcatel-Lucent
2701 Lucent Lane, Rm. 9F-546, Lisle, Illinois 60532 (USA)
Email: vkg@{alcatel-lucent.com,bell-labs.com,acm.org}
WWW:   http://www.alcatel-lucent.com/bell-labs
_______________________________________________
p2pi mailing list
[email-masked]
https://www.ietf.org/mailman/listinfo/p2pi

---

From: Laird Popkin <[email-masked]>
Date: Fri, 13 Jun 2008 11:25:39 -0400

Yes, I certainly didn't mean to imply that there was any problem with  
the "oracle" approach or the ALTO proposal - I am a strong supporter  
of this model. My only concern is that we don't limit our discussion  
to the one signaling protocol that was used as an example. My  
apologies if my (perhaps overly detailed) email came across as more  
negative than I intended. :-)

- LP

---

From: Stephane Bortzmeyer <[email-masked]>
Date: Fri, 13 Jun 2008 17:27:35 +0200

On Fri, Jun 13, 2008 at 10:23:01AM -0500,
 Vijay K. Gurbani <[email-masked]> wrote 

> I am sorry but could you please expand on "ICS"?

Sorry, Internet Coordinates Systems as in
<http://www.imconf.net/imc-2003/papers/p310-lim11.pdf> or similar
works.
_______________________________________________
p2pi mailing list
[email-masked]
https://www.ietf.org/mailman/listinfo/p2pi

---

From: Stephane Bortzmeyer <[email-masked]>
Date: Fri, 13 Jun 2008 17:28:50 +0200

> http://idisk.mac.com/cullenfluffyjennings-Public?view=web

Required Browsers  	
			
You may be using an unsupported browser.
We recommend:

    * Mac OS X Safari 1.3 or later
    * Firefox 1.0.4 or later

    * Windows Firefox 1.0.4 or later
    * Internet Explorer 6 or later

[I use Firefox 2.0.0.14]

---

From: "Vijay K. Gurbani" <[email-masked]>
Date: Fri, 13 Jun 2008 10:33:52 -0500

> <http://www.imconf.net/imc-2003/papers/p310-lim11.pdf> or similar

Ah, OK.  I figured as much, but before suggesting anything, I
wanted to be sure.

A discussion of ICS as epitomized by Vivaldi, PIC, et al. is
discussed in our paper (in the URL I sent you for the iDisk
volume, see the paper "29 alto.pdf").

Thanks,

- vijay

---

From: "Vijay K. Gurbani" <[email-masked]>
Date: Fri, 13 Jun 2008 10:35:33 -0500

>     * Internet Explorer 6 or later

Hmmm ... funny -- I use Firefox v2.0.0.14 as well, and it works
for me.  In any case, I will send you a tar file in private
email that includes the workshop proceedings and presentations.

Ciao.

- vijay

---

From: Laird Popkin <[email-masked]>
Date: Fri, 13 Jun 2008 11:37:17 -0400

Very interesting reading, thanks!

- Laird Popkin, CTO, Pando Networks
   http://www.pandonetworks.com
   520 Broadway, 10th Floor, NY, NY, 10012
   [email-masked], 646/465-0570.

Sent from my iPhone. Apologies in advance for typo's.

---

From: "Vijay K. Gurbani" <[email-masked]>
Date: Fri, 13 Jun 2008 11:24:11 -0500

> negative than I intended. :-)

Laird: No worries, it did not.  In fact, you bring a lot of
relevant discussion points.  One thing that caught my eye was:

> transfers has the most impact for large swarms. That is, if there
> are only 20 people on the planet that can serve you data, (1) it
> doesn't take too long to connect to all of them so optimized peer
> selection doesn't save much peer connection time, and (2) the odds of
> any of them being in the same ISP is fairly low, so optimized peer
> selection doesn't affect data flow much.

This is very true for large swarms.  However, aside from a BitTorrent-
like P2P configuration, consider the whole notion of service
discovery in VoIP P2P networks in the context of finding the
nearest -- say -- video mail peer to deposit my video mail, and
if that resource is replicated in the DHT, to find the
nearest peer that can serve it.  Here, the number of people
interested in this video mail resource is low, probably the
sender and the receiver only, and maybe a finite number of
others who the first two may want to share the resource with.
But the network could benefit from keeping the traffic localized.

> This is why we shifted (in the P4P approach) away from the more
> obvious IP list approach to moving the guidance into the Tracker's
> memory [...]

Thanks; I did read your paper in preparation for the workshop,
but either I did not read it closely enough, or some epiphany
occurred on reading your email to make things more clear on
the tracker approach.

Ciao.

- vijay

---

From: Enrico Marocco <[email-masked]>
Date: Sat, 14 Jun 2008 20:42:36 +0200

>> http://idisk.mac.com/cullenfluffyjennings-Public?view=web

It is actually quite an unfriendly website for non-mac users, but 
fortunately it has also a webdav interface.  Just point a dav client 
(e.g. cadaver) to the URL above and it should work.

> [I use Firefox 2.0.0.14]

Maybe your browser is just presenting itself with another name (Iceweasel?).

---

From: Enrico Marocco <[email-masked]>
Date: Sat, 14 Jun 2008 20:53:24 +0200

> applications Using Information Provided By Isps And Network

Actually the draft was written a couple of months ago with much emphasis 
on ISP-based solutions.  After several discussions, it has become clear 
that the same service could be effectively provided by third-parties.
We'll try make it clearer in the next version of the draft.

> I'm a big fan of ICS myself but are they really on-topic? Or is it too

The main goal here is to provide an interface to help p2p applications 
in the peer selection process.  Whether such interface is implemented by 
an oracle deployed by some ISPs, or by a distributed coordinate system 
should be transparent to the standardization effort we are proposing.

---

From: Laird Popkin <[email-masked]>
Date: Fri, 13 Jun 2008 16:19:14 -0400

Comments below.

> and to be able do deliver results on-the-fly.

I'm not concerned about the computational cost of figuring out which  
peers to connect to which - we do that now in our Trackers, and with  
enough pre-computation it's remarkably fast, though of course not  
quite as fast as picking random numbers from a list. But we don't mind  
a little CPU overhead if it generates performance and efficiency. :-)

The main concern that I have is that I can't take an extremely high  
volume, fast, in-memory operation and turn it into a blocking external  
message, because that makes my system orders of magnitude slower and  
more fragile.

The issue isn't the algorithm, it's where we draw the "line" through  
the system where data crosses the wire. If the high-volume  
interactions (mapping IP's to network locations, finding nearby  
locations, and returning a sorted list of nearby IP's) can be done in  
memory, and only periodic map updates are done over the wire, that's  
more efficient then if the high-volume interactions all have to cross  
the wire.

Now perhaps we can find a way to have "sorting lists of IP's" work  
really well. As far as the ALTO BOF goes, I just don't want us to  
assume that approach, because I tried it last year and hit a wall, and  
I don't want us to collectively hit that wall without at least knowing  
that there's a wall in the vicinity.

> should we try to be as much as possible transparent/agnostic ? I'd  

This is a very good question. In principle I agree that a single, more  
'generic' solution would be better. But the communication patterns for  
tracker-based and trackerless p2p networks are quite different, and  
the scaling requirements are so extreme, that it's not clear to me  
what a single approach can work well for both. But that's what the  
ALTO discussions will help explore.

For a tracker-based system, my instinct is that a "map-based" approach  
is more efficient, because there are a small number of Trackers and  
they have plenty of resources to keep a map in memory. For a  
trackerless system, my instinct is that a "sort IP list" approach  
might be more appropriate, since each peer only knows about a small  
piece of the swarm (so the lists aren't too big) and it seems  
inefficient to send a complex "map" to millions of peers.

> who among his customers is a p2p addicted... ;-)

I am sure that's true - uplink utilization probably correlates pretty  
well with p2p application usage. But if the p2p network sent IP lists  
for every swarm to the oracle, that means that the ISP would know  
exactly who was in each swarm for each unique piece of content in the  
swarm, and which p2p network that piece of content was in, and (to  
some degree) what the content is. This is broadcasting a level of  
detail around user behavior that is, to be frank, a little unsettling.

> - In one point we're in violent agreement: This is a great discussion.

Yep. I am enjoying this quite a bit.

>> receive a
>> are only 20
>> It is for these large sarms where the "list of IPs" approach runs  
>> into some
>> pragmatic issues:
>> - The "oracle" would have to maintain state (or recompute on every  
>> query) for
>> every swarm in every p2p network.
>> - It makes every Tracker announce slow, expensive and unreliable  
>> instead of
>> fast, cheap and reliable.
>>
>> obvious IP
>> Subject: Re: [p2pi] Refining the ALTO problem statement [Was: Re:  
>> discussing
>> P2PI-related standardization in Dublin]
>>
>> Enrico,
>>

---

From: Stephane Bortzmeyer <[email-masked]>
Date: Mon, 16 Jun 2008 09:21:21 +0200

> > http://idisk.mac.com/cullenfluffyjennings-Public?view=web

And I'm not the only one having problems with this broken Web site:

http://blogs.voxeo.com/speakingofstandards/2008/05/20/ietf-p2p-workshop-agenda-and-papers-now-available/
_______________________________________________
p2pi mailing list
[email-masked]
https://www.ietf.org/mailman/listinfo/p2pi

---

From: stefano previdi <[email-masked]>
Date: Mon, 16 Jun 2008 11:22:21 +0200

> a little CPU overhead if it generates performance and efficiency. :-)

indeed... I believe (from an implementation standpoint) it shouldn't cost
more than a simple RIB lookup... but we're probably diverging from our
purpose here... ;-)

> that there's a wall in the vicinity.

I tend to agree. But what's missing (at least to me) is a set of
requirements. Having a time issue is possible only if you quantifies your
time budged...

My kids will tolerate an extra second or two prior to start their download,
but in other contexts it may be less evident.

> ALTO discussions will help explore.

I agree.

> detail around user behavior that is, to be frank, a little unsettling.

Bu this implies the client to communicate (in addition to peers list) also
the piece of content related to the swarm. Isn't just the case of an
embedded localization component inside an application-specific tracker ?

thanks.

s.