Subject: Re: [alto] ALTO with CPID extension

From: Haibin Song <[email-masked]>
Date: Sat, 12 Jun 2010 17:29:57 +0800

Hi Richard,
 
> -----Original Message-----
> From: [email-masked] 
> [mailto:[email-masked]] On Behalf Of Richard Alimi
> Sent: Thursday, June 10, 2010 11:46 PM
> To: Song Haibin
> Cc: [email-masked]
> Subject: Re: [alto] ALTO with CPID extension
> 
> Hi Haibin,
> 
> On Fri, Jun 4, 2010 at 3:42 AM, Song Haibin 
> <[email-masked]> wrote:
> > Hi all,
> >
> > I would like to make a clarification on how CPID works and in which 
> > way it will benefit.
> >
> > First the ALTO server collects network topology and policy 
> information 
> > from network equipments. And then constructs a cost/priority matrix 
> > among the network aggregation points. And after a mathematical 
> > decomposition, the original cost/priority matrix turns into the 
> > multiply products of two matrixes. And each cost/priority 
> value in the 
> > original matrix is the multiply product of two vectors in 
> the latter 
> > two matrixes. And these vectors become the CPIDs for peers 
> under those 
> > aggregation points. There are two kinds of CPIDs, CPIDsource and 
> > CPIDdestination in the case the priority/cost from one area 
> to another 
> > area is not equal to the cost vice versa. A small map indicates the 
> > priority from the current ISP/AS to other ISP/AS (one to 
> many) will also be needed.
> 
> Is the mechanism for interdomain specified in any more detail 
> somewhere?  In particular, how does an ALTO Client determine 
> that a peer's CPID is not "compatible" with its own (i.e., it 
> is not generated by the same ALTO Service Provider)?  What is 
> the structure of this map and why is it small?
> 

There could be an identity for each ISP, I would assume this could be
assigned by IANA. Clients can use this identity for the differentiation. The
size of the map is linear to the number of ISPs. The CPID draft will be
updated and you will see more details. 

> >
> > Second, the CPID for each area and the the very small map could be 
> > delivered to the local DHCP server in that area, and the 
> end user will 
> > get their CPID through the DHCP server. The ALTO server 
> does not have 
> > to process any user requests. The end user does not need to 
> know more 
> > information than that got from the DHCP server.
> 
> This is of course presuming that the ALTO Client can access 
> any DHCP options? Looking briefly on my linux machine, this 
> appears to require installing hooks (as root).  The situation 
> appears to be somewhat easier on Windows, which has a 
> DhcpRequestParams() function.
> 

The client is required to support a new DHCP option if it wants to use this
way to retrieve its CPID, this is bad, but the benefit is that it is not
required to change anything to do ALTO server discovery. 

> > Third, as each end user or resource provider all have their 
> own CPIDs. 
> > The end user will choose peers according to the source and 
> destination 
> > CPIDs and priority from its ISP/AS to others.
> 
> It may also be good to enumerate assumptions that CPID has on 
> the Resource Consumer and Resource Providers so that one can 
> more explicitly judge in which deployment scenarios it might 
> apply. There are a couple that I can think of off the top of my head:
> - Both Resource Consumer and Resource Provider must have ALTO Clients

That's because we hope CPID could be the basic atrribute for each client,
somewhat like IP address. The cost between two clients could be calculated
by the "cost attribute" of these two clients.  

> - Both Resource Consumer and Resource Provider must have the 
> same ALTO Service Provider 

No. We also have interdomain traffic optimization. But if you want to
totally cut off the "small map" I mentioned above, that would be possible if
there is an third party to get all the cost among ISPs and turns them into a
portion of each CPID vector. 

>(my initial interpretation is that 
> the "small map"
> you mentioned above looks a lot like the Network Map and Cost 
> Map currently in the protocol -- is that right?)

No Network Map. Somewhat similar to the Cost Map with only cost information
from the current ISP to other ISPs.

> - The application protocol between the Resource Consumer and 
> Resource Provider can be changed
> 
I think either way that you can let the resource consumer to get the CPID of
the resource provider is okay.

> > I would agree that the network map and cost/priority map could be 
> > re-calculated by efforts if an application has millions of 
> users and 
> > wants to collect this kind of information (CPID and IP addresses).
> 
> If users can recompute such information, that is fine.  
> However, I strongly object to making any claims as to any 
> increase in ISP privacy beyond the level currently offered by 
> the Network Map and Cost Map approach.  In addition, such 
> considerations should be stated clearly so that ISPs don't 
> fall into a false sense of privacy.
> 
> > But ALTO server
> > does not have to process user requests (offload to local 
> DHCP server, 
> > no burst load on the ALTO server, you even do not need ALTO server 
> > discovery in this case).
> 
> Okay.
> 
> > And the end user does not have to search the big map to 
> find all the 
> > PIDs for destination peers and then search the costs in the 
> cost map.
> 
> As I mentioned before, I think the computational overhead for 
> a single network map lookup (i.e., a longest-prefix match) 
> and a single matrix lookup (indexing into a 2-dimensional 
> array) is extremely minor especially for an ALTO Client 
> deployed at an end-user's machine.

CPID is mainly based on the calculation with the source CPID and destination
CPID, not lookup. 

> 
> Our benchmarks for a single peer join and peer selection at a 
> tracker with 1,000,000 registered peers (which included a few 
> longest-prefix matches, 50 lookups into a peering weight 
> matrix the size of a cost map, as well as various other 
> bookkeeping and lookup operations) took under 40 
> microseconds.  The burden on an ALTO Client would presumably 
> be much less in the use case you mentioned above.
> 

Okay. That is for a single selection. How many user requests per second are
there in the tracker you mentioned above? What is the average number of
peers in each swarm? 

BR,
Haibin

> Thanks,
> Rich
> 
> >
> >
> >
> > My two cents,
> > Haibin
> >
> >
> >
> > _______________________________________________
> > alto mailing list
> > [email-masked]
> > https://www.ietf.org/mailman/listinfo/alto
> >
>

---

From: Richard Alimi <[email-masked]>
Date: Sat, 12 Jun 2010 10:36:14 -0400

Hi Haibin,

> updated and you will see more details.

I'm not sure it is quite that simple. For example, there are many ISPs
that span large geographical areas (e.g., AT&T, Verizon, Comcast in
the U.S.) and they may have peering points between them in multiple
locations.  Then, the question "what is the cost from a customer in
AT&T to a customer in Comcast?" is *not* as simple as saying "What is
the cost from AT&T to Comcast?".  The real question is "what is the
cost from this location in the AT&T network to another location in the
Comcast network?".

This is one reason why we have both a Network Map (on the basis of IP
Prefixes) and a Cost Map in the ALTO Protocol today.

> required to change anything to do ALTO server discovery.

That's fine, I'm simply pointing out one of the properties of the solution.

> by the "cost attribute" of these two clients.

That's fine, but note that it doesn't apply to particular deployment
scenarios such as mirror selection (mentioned in the charter).

> from the current ISP to other ISPs.

See my comment above about the "small map" approach.

> the resource provider is okay.

In certain deployment scenarios, it also adds queries to an ALTO
Server (similar to queries to the existing Endpoint Cost Service).
You can probably argue that it still alleviates some load on the ALTO
Server since many P2P applications may have the luxury of augmenting
the protocol.

However, if the protocol cannot be changed, and a Resource Consumer
needs to query for the CPID of the Resource Provider, note that:
(1) There is still load on the ALTO Server roughly the same as would
be used by the Endpoint Cost Service.
(2) The benefits to P2P Privacy discussed in the current version of
the draft are gone (since you're sending IP addresses of peers to the
ALTO Server).

Again, I don't necessarily have a problem if a particular scheme
requires changing the application protocol.  I simply wanted to be
explicit about the deployment considerations.

>> > wants to collect this kind of information (CPID and IP addresses).

Just a side note: if you allow queries for a Resource Provider's CPID,
you no longer have the requirement that to learn a CPID there must be
an active client within that CPID.

> CPID is mainly based on the calculation with the source CPID and destination

I understand that.  I'm comparing to the Network Map / Cost Map
approach which requires a longest prefix match and indexing into the
row and column of a matrix.  For CPID, you need to index into the row
of a matrix twice and compute an a inner product.

My claim is that at the rate that a P2P client (presumably where this
would be deployed) is performing either of these operations, it isn't
going to matter.  I think it is useless to try and optimize at this
point to calculate a cost a few microseconds faster.

My only point for discussing the benchmarks below was to show that the
Network Map and Cost Map computations were indeed of that order.

> Okay. That is for a single selection.

Let me add a few more details of the methodology. The benchmark began
with the tracker empty. We then allowed 1,000,000 peers to join as
fast as they could by calling our addPeer() and selectPeers()
procedures in the code for each new peer.  We were simply benchmarking
the code and did not have any network messages in the experiment.

Note that addPeer() does the lookup into the Network Map for each ISP
(since this is a tracker) and we store the PID.  selectPeers() does
the indexing into the peering weight matrices.

> How many user requests per second are
> there in the tracker you mentioned above?

The effective load on the tracker at the end of the experiment was
25,000 peer joins per second (1 second / 40 microseconds).  I hesitate
to say "requests per second" since the benchmark did not include any
networking (but that isn't what is being debated here).

> What is the average number of
> peers in each swarm?

There are 1,000,000 in the swarm at the end.   The time measurement of
40 microseconds for a single peer is drawn from benchmark towards the
end of the experiment when when there are close to 1,000,000 already
in the swarm.

Again, a "peer join" in this benchmark included much more than a
single longest-prefix match and a single indexing into the matrix.  As
I recall, a non-negligible amount of time was actually drawn from
generating random numbers used in the peer selection (50 times in the
benchmark above).

If I get a chance in the next few days I'll be happy to setup an
experiment which only benchmarks a single longest-prefix match and
matrix lookup if you think it would be helpful to convince you that
looking up into a Network Map and Cost Map is actually a pretty cheap
operation.

Rich