Subject: [alto] How many PIDs in an ALTO server?

From: Bill Roome <[email-masked]>
Date: Tue, 13 Sep 2011 10:35:13 -0400

How many PIDs do we expect an ALTO server to handle?

I ask because I've discovered that code that works fine with a few hundred
pids dies when I go to 5,000 pids.

The biggest problem is the full cost map response message. With 5,000
pids, that has 25 million cost entries. When I went to 5,000 pids, my
off-the-shelf JSON parser ran out of memory. Granted I'm using java, so
there's a big memory hit there. But I gave the JVM a 4 gigabyte heap, and
it STILL ran out of memory.

Eventually I was able to parse a 5k-pid CostMap, but I had to completely
re-write the JSON parser.

So my first concern is that if we really expect servers to have 5,000
pids, and if we expect clients to ask for full cost maps, then we need to
warn client authors. Otherwise someone will write a simple client, test it
with a simple ALTO server ... and then have it die when it encounters a
production ALTO server.

My other concern is that the current JSON encoding of a full cost map is
very large and inefficient. For 5,000 pids, a full cost map takes 417
megs. And that's with relatively short pid names (pid_1 thru pid_5000).
Granted that can be compressed, but it's still a lot of data.

If we're concerned about maps with large pid counts, there is much more
efficient way to present the cost data. Instead of the nested dictionaries
with multiple repetitions of the pid names, we could use three arrays:

	srcs
	dests
	costs

"srcs" & "dests" would be arrays of pid names. The cost array would have
nSrc x nDest costs. costs[0] would be the cost from srcs[0] to dests[0],
costs[1] would be the cost from srcs[0] to dests[1], etc. That is, "costs"
is the cost matrix in row-major order.

For example, where the current encoding uses

	"map":{
		"pid1": {"pid3":1, "pid4":2}
		"pid2": {"pid3":3, "pid4":4}
	}

the alternate encoding would be:

	"srcs":  ["pid1","pid2"],
	"dests": ["pid3","pid4"],
	"costs": [1,2,3,4]

That's not impressive for small pid counts, but it makes a big difference
for large counts. For example, for 5,000 pids:

	current encoding:   417 megs
	alternate encoding: 148 megs

What are your thoughts?

	- Bill Roome

---

From: Sebastian Kiesel <[email-masked]>
Date: Tue, 13 Sep 2011 22:49:18 +0200

On Tue, Sep 13, 2011 at 10:35:13AM -0400, Bill Roome wrote:
> pids, that has 25 million cost entries. 

I'm wondering whether retrieving the full N x N cost map is an
important (or even a realistic?) use case.

Consider an ALTO client embedded into a (P2P) application running on a
PC connected to ISP A, say in PID 1.  It makes sense to ask ISP A's ALTO
server how expensive it is to get from PID 1 to candidate peers located
in PIDs 2 (other access network of ISP A), 3 (ISP B) and 4 (ISP C),
respectively. That is, it would need to know an 1 x N vector.
But why should the application be interested in knowing the cost from
PID 3 to 4? And even if it was interested, how would ISP A know the cost
between ISP B and C's networks?

If, on the other hand, we consider a big resource directory (e.g. P2P
tracker) it would make sense to know the N x N matrix. But I doubt
that there would be a single ALTO server that can deliver this matrix
with a high level of detail. Who would be the operator of this
ALTO server? I assume that the resource directory will have to ask
several ALTO servers (of different ISPs) for their 1 x N matrix
from their point of view and it will have to assemble the N x N matrix
from that.

Just my 2 cents.

   - Sebastian

---

From: Songhaibin <[email-masked]>
Date: Sat, 24 Sep 2011 08:43:48 +0000

I agree with you, Sebastian. 

We still need to consider the ALTO client in PID1 may need to retrieve the whole network map. Then the size of the network map matters. And the App resource directory may want to get the full network map and cost map from ALTO Server in ISP A, which contains the M (number of PIDs within ISP A) * N (Number of total PIDs from ISP A's perspective) matrix.

BTW, IMO, PID is a local meaningful number within an ISP. Two ISPs can use the same PID to define different things.

-Haibin

> -----Original Message-----
> From: [email-masked] [mailto:[email-masked]] On Behalf Of
> Sebastian Kiesel
> Sent: Wednesday, September 14, 2011 4:49 AM
> To: Bill Roome
> Cc: [email-masked]
> Subject: Re: [alto] How many PIDs in an ALTO server?
> 
> _______________________________________________
> alto mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/alto

---

From: Richard Alimi <[email-masked]>
Date: Sat, 24 Sep 2011 10:52:37 -0700

Hi Bill,

Thank you for such a detailed analysis :)

With regards to how many PIDs might be seen in actual deployments,
this document has some measurement results from one specific
deployment:
  http://tools.ietf.org/html/rfc5632
Of course, that is one specific case.

Have you attempted to see how big the maps are after being compressed?
 I'd be curious to see what the raw size differences are in that case.
 When we were doing the trials with P4P, enabling compression on the
HTTP client and server was one of the first things that our
integration testing guided us to do :)

I'm fine with changing the structure of the map if really desired, but
I can give a bit of rationale for the current one :)  One of the
reasons we went with JSON (and a text encoding in particular) was to
make messages more humanly-readable to ease debugging.  Having the map
structured as "source -> { destination -> cost }" made it easier to
look at a map immediately to determine the cost for a (source,
destination) from only visible inspection.  Similarly to your other
comments, I'd like to hear from others in the WG before making a
change to the base protocol (after all, it is a WG document :) ).

A couple of additional comments inline:

> pids dies when I go to 5,000 pids.

I would expect most servers to have *some* upper bound given that
memory is not an infinite resource :)

> it STILL ran out of memory.

The way that I approached this problem was to use a SAX-style JSON
parser. Then the in-memory cost-map can be populated as the response
is read.

A similar thing can be done at the server-side -- one could have the
response generated on-the-fly (using HTTP chunked encoding) from the
cost map stored in RAM.  Then there's only a small, fixed amount of
RAM used per connection instead of buffering the full response before
sending it.

I would imagine that such things would need to be done if an
implementation or deployment really does wish to handle cost maps /
network maps of *any* size.

> with a simple ALTO server ... and then have it die when it encounters a

Some of this probably boils down to testing practices :) I would hope
that integration tests would make use of realistic data, and still
fail gracefully if it encounters an ALTO Server that returns data much
larger than was ever expected in testing.

It seems like we're getting quite a bit of feedback about
implementation-level aspects of the ALTO protocol. Do you think some
of these things would better go into the Deployment Considerations
document rather than the protocol specification?

>        alternate encoding: 148 megs

What I said above, and also another thanks for your detailed feedback
on the protocol and implementation :)

Rich

---

From: Richard Alimi <[email-masked]>
Date: Sat, 24 Sep 2011 11:03:00 -0700

> important (or even a realistic?) use case.

Yes I do believe it is important and realistic.  If someone is going
to be doing post-processing on the map to optimize for a a network as
a whole, then this would be the desired interface to use.

> between ISP B and C's networks?

Yes - some of the feedback from IETF81 was to give an ALTO Server a
way to say "I don't know" (one of the ways to do this might be to just
omit such entries from the cost map, but that's another thread so I
won't comment on it more here).

> tracker) it would make sense to know the N x N matrix.

Agreed.

> But I doubt
> with a high level of detail.

Why not? I think I would disagree with this, depending on what you
mean by "a high level of detail".  An ALTO Server does not need to
reply based on information from within other ISPs.  The semantics of
ALTO maps and information in general is that it is from the ALTO
service provider's perspective.

> Who would be the operator of this

Remember that the semantics of ALTO maps and information from its own
perspective. See:
  http://tools.ietf.org/html/draft-ietf-alto-protocol-09#section-2.2

Thanks,
Rich

---

From: Bill Roome <[email-masked]>
Date: Mon, 26 Sep 2011 10:39:33 -0400

I have to agree with Sabastian. I think ALTO servers will be run by ISPs,
and will have high detail and accuracy for the endpoints the ISP runs. But
the detail and accuracy will drop as you get farther away from the ISP's
territory.

Example: An ALTO server run by a US-based ISP might divide North America
into 100's of PIDs, and provide very accurate cost data between them. But
that ALTO might have only 2 PIDs for all of Japan. The server might give
good cost data for North America to those two Japanese PIDs, but it's cost
data between those two Japanese PIDs would be very flakey.

An ALTO server run by a Japan-based ISP would be just the opposite: lots
of PIDs for Japan, but only a few for North America.

	- Bill Roome

---

From: Sebastian Kiesel <[email-masked]>
Date: Mon, 26 Sep 2011 16:46:40 +0200

> a whole, then this would be the desired interface to use.

I have no doubts that there would be interesting things that could
be done with the full map (in particular if we think about a tracker).

The question for me is more: will a single organization be able to
gather the data? That depends on the metric / rating criterion:
latencies or AS paths from the point of view of the ALTO server can
easily be found.  For other criteria, such as (normalized) monetary
costs for transmitting traffic from one PID to another, ISPs would have
to cooperate and disclose the data, I'm not sure this will ever happen.

> won't comment on it more here).

So we need an efficient encoding for a sparse matrix ...

> service provider's perspective.

Agreed. But not sure how useful is information from the point of view
of the ALTO server.

-- S.

---

From: Richard Alimi <[email-masked]>
Date: Mon, 26 Sep 2011 09:25:33 -0700

> to cooperate and disclose the data, I'm not sure this will ever happen.

Okay - without detracting from the original comment, it sounds like we
both agree that the NxN matrix can be a reasonable request for an ALTO
Client to make. I agree that the quality of information (and whether
the ALTO Server provides certain cost types for addresses outside of
its administrative domain) is going to vary depending on many factors.

> So we need an efficient encoding for a sparse matrix ...

Yep - saving that for the other thread :)

> Agreed. But not sure how useful is information from the point of view

FWIW, I fully expect there to be ALTO Clients out there who will crawl
all publicly-available ALTO Servers and do data mining on that
aggregated set.  iPlane is an example of gathering data on a global
scale without ALTO, and I would imagine that ALTO would only serve as
another helpful input.   But that is a separate question from the size
of a map of a single ALTO Server.

Rich

---

From: Richard Alimi <[email-masked]>
Date: Mon, 26 Sep 2011 09:32:53 -0700

> of PIDs for Japan, but only a few for North America.

Sure - and that's what I meant when I said "depending on what you mean
by 'a high level of detail'".  The RFC5632 shows one example of a
"high level of detail" within
a single ISP, and for that trial, much less granular costs were given
to/from peering ISPs.  The ISP maps were not consulted when
determining costs between a pair of endpoints that were completely
outside of the ISP.  My only point was that the full map can still be
useful.  I'm not opposed to giving the ALTO Server a way of saying "I
don't know", which as Sebastian pointed out, basically makes that a
sparse matrix.  However, that's a separate thread...

Rich

---

From: Sebastian Kiesel <[email-masked]>
Date: Mon, 26 Sep 2011 18:54:23 +0200

On Mon, Sep 26, 2011 at 09:25:33AM -0700, Richard Alimi wrote:
> Client to make. 

ACK.

> I agree that the quality of information (and whether

Let me rephrase my original point:

If an ALTO client in an application running at the resource consumer
asks its ISP's ALTO server for guidance related to its own topological
location, the answer will be a (Mx1)-matrix (Vector).

A tracker, in contrast, would be interested in the (NxN)-matrix.

I'd say that usually M can be much higher than N, with high-quality data.

Of course, the gut feeling "M >> N" does not allow any direct
conclusion whether tranmission of a (NxN) could become a problem.

> of a map of a single ALTO Server.

ACK.

  -- Sebastian