Subject: Re: [pcp] Option ordering, ticket #41

From: Paul Selkirk <[email-masked]>
Date: Fri, 25 Feb 2011 19:23:39 +0000

This whole discussion is about marginal optimization.  In the best case,
it reduces the cost of a search from O(n) to O(n/2); in the worst case
(inserting an option into a request), it increases the cost from O(1) to
O(n).  This puts an extra burden on the client, when some have said the
client should be kept as simple as possible at any price.  It also puts
a burden on the server, which now needs to validate option ordering as
well as the semantics of the individual options.

And it still doesn't support hardware acceleration (the original
proposed reason), because options are optional, so you can't predict
which ones will be present, even if you can now predict their order.

(However, if we're going to order the options, it makes sense to put the
mandatory-to-process options first.)

				paul

---

From: Reinaldo Penno <[email-masked]>
Date: Fri, 25 Feb 2011 15:05:16 -0500

Hello,

Comments inline.

On 2/25/11 11:23 AM, "Paul Selkirk" <[email-masked]> wrote:

> O(n).  

Right, but a PCP Server processes requests for potentially millions of
clients and a PCP client has to deal only with its own requests. So, your
reduction in the cost of a search certainly makes a difference.

> This puts an extra burden on the client, when some have said the

Does it? Must order does not necessarily means validation. I thought the
validation is implicit, see below.

> which ones will be present, even if you can now predict their order.

There are multiple ways of looking at this. One example:

* If I need to see option '2' and I get to option '3', drop packet. As
opposed to scan all options.

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