Subject: [RRG] ALT + NERD is inelegant & inefficient, compared to APT or Ivip

From: Robin Whittle <[email-masked]>
Date: Tue, 22 Jan 2008 15:05:05 +1100

Is Tony Li the only person other than me who is critical of the
prospect of LISP-ALT and LISP-NERD running in parallel?

Everyone seems to agree that neither is sufficient on its own.  Yet
most folks seem to be assuming that the future map-encap scheme will
be based on, or resemble LISP CONS or ALT - with its global query
network and some system to handle traffic packets while the ITR is
waiting for the response from the slow, unreliable, global query
network.

In responding to concerns about all ITRs caching (ALT) or about all
ITRs having the full feed of mapping information (NERD), Dino
proposed that LISP should be implemented with both systems at once.
Here are some quotes from Dino and Tony around 10 January:

http://psg.com/lists/rrg/2008/msg00113.html

DF >>  As you know, all the LISP mapping database
DF >>  mechanisms touches on all tradeoffs. We know how
DF >>  to do it each way, what's left is experimentation
DF >>  and a decision to pick one, or blend two.

TL >   ?  You missed my point: you pick all, simultaneously.
TL >   You let your particular working set characteristics in
TL >   your particular location select which particular approach
TL >   you use at that particular location.  All of the choices
TL >   need to be integrated so that they result in one clean
TL >   mechanism.

http://psg.com/lists/rrg/2008/msg00115.html

DF >>  We have already made that conclusion. You should have
DF >>  seen that at RRG.

TL >   No, what I saw was a total mess of mechanisms, with no
TL >   coherency.

http://psg.com/lists/rrg/2008/msg00118.html

DF >>  Is coherency in the eye of the beholder? Systems with
DF >>  radically different operating points are going to look
DF >>  radically different.
DF >>
DF >>  As long as each operates well, they don't interfere with
DF >>  one another, and there is a good algorithm/whatever for
DF >>  deciding which one to use in a given situation, is it a
DF >>  problem if they are very dissimilar?

TL >   Something that looks like three different systems still
TL >   looks like three different systems. What we're talking
TL >   here is a smooth continuum of solutions with a common
TL >   infrastructure. There was no dial that you could set for
TL >   "light", "normal", and "heavy duty".

Here is my understanding of deploying both ALT and NERD, with and
without the "Default Mapper" approach to handling packets for which
a caching ITR currently has no mapping information.

Some ITRs are full database NERD ITRs.  They receive ("push", though
in NERD the ITR initiates the downloads) the full mapping database
and updates to this database.  These full database ITRs (ITRDs in
Ivip parlance) correctly and immediately encapsulate every traffic
packet (one addressed to an EID) they receive.  The cost is an
expensive ITR with a substantial flow of mapping data to it at all
times, irrespective of the traffic it handles.

The remaining ITRs are caching ITRs (ITRCs in Ivip).  They can only
get mapping data some time (fractions of a second to several
seconds) after they request it from the global ALT network.  These
ITRs can in principle be smaller and cheaper and their communication
needs for mapping data are smaller than for a NERD ITR.  The
communication needs are in direct proportion to the range of EIDs of
the traffic they handle.

With the original LISP approach of not using a "Default Mapper", the
initial one or more traffic packets cannot be tunnelled directly to
the ETR - because the mapping reply has not yet been received.  With
ALT as originally defined, they are sent into the global ALT system
which functions both as a global (often or typically slow) query
server network and as a global (slower and more costly than direct
tunnelling) network for delivering these initial packets to the correct
ETR.

The trouble with this is that by the time these initial traffic
packets emerge from their circuitous travels in the ALT network,
they are likely to be delayed so much that they have zero or
negative value for the end-users who are trying to communicate.

If the "Default Mapper" approach is used, then the ALT network is
only for handling mapping queries, and the packets which the caching
ITR has no mapping information for will be sent to a "Default
Mapper" - and ITR which does know how to tunnel them.  This may or
may not involve longer paths (stretch) compared to direct tunnelling.

By the way, the "Default Mapper" approach fits nicely with LISP's
"Proxy Tunnel Router" approach (which is identical to Ivip's
"anycast ITRs in the core").  The "Default Mapper" ITR can be one
and the same as the "Proxy Tunnel Router".

A "Default Mapper" / "Proxy Tunnel Router" ITR only makes sense if
it has the full database - so I assume these are NERD ITRs.  The ITR
functions as a "Proxy Tunnel Router" for packets originating in ISP
networks with no ITRs, and as a "Default Mapper" for packets sent
from an ISP with caching only ITRs.  An ITR could also be a "Default
Mapper" just for the ALT (caching) ITRs in a particular ISP network.

Without "Default Mapper" / "Proxy Tunnel Router" approach, ALT and
NERD are entirely independent systems which do not interfere, depend
upon or assist each other.

With the "Default Mapper" approach, ALT is used only for queries,
and NERD is used for some or many ordinary ITRs and for the "Default
Mappers" which caching (ALT) ITRs send their initial traffic packets
to.  So the ALT system depends on and derives benefits from the NERD
system.

However this ALT + NERD combination is inelegant and inefficient -
since with a little thought, a number of improvements can easily be
made.

The first obvious inefficiency is that ALT ITRs are going to rely on
the global (slow) ALT query system - sending their request around
the world (sometimes on a path longer than around the world) when
there is a NERD ITR at a distance which is far less than the path
which would be taken in the ALT network.

The NERD ITR has the full database.  So the first improvement is to
make that ITR, or a server at the same site, a query server.

Now the system resembles APT.  APT's Default Mappers are both query
servers and full database ITRs - but they only tunnel packets which
the other (caching) ITRs don't yet have mapping information for.
The traffic packet also functions as the mapping request (elegant
and efficient!), and assuming the Default Mapper (there can be
several of them) is close, the caching ITR will have the mapping
data within tens of milliseconds.  So only one or a few initial
traffic packets are handled by the Default Mapper.  This means the
Default Mapper can be a server, rather than a Big Iron router with
hardware FIB etc.

APT is an improvement on LISP ALT+NERD in several respects:

1 - There is no need for a global (big, expensive, unreliable and
    often very slow) query network - all queries are handled by
    the local full database query server: the Default Mapper.

2 - No traffic packets are delayed excessively - in contrast to
    ALT + NERD without "Default Mappers" which relies on the ALT
    network to deliver the first packets.

However, the APT design can be improved upon to deal with these
problems:

1 - There is no support for traffic packets from non-upgraded
    networks as there is for Ivip or LISP ("Proxy Tunnel
    Routers").  So APT as it stands is not incrementally
    deployable.

2 - The caching ITRs can only use Default Mappers in their own
    ISP network.  Therefore, every upgraded network needs
    one or more Default Mappers and so a full feed of mapping
    information.

Firstly, we can split the Default Mapper functions of full database
query server (QSD) and full database ITR (ITRD) - to allow them to
be implemented on separate devices if this is desired.

Secondly we can remove the requirement that caching ITRs can only
access these things within their own ISP's network.

QSDs and ITRDs might be in the same device, or be in separate
devices at the same location - but it is easy to imagine an
architecture which does not tie the two things together.  Both need
a full feed of mapping data, so they may well be in the same
location or the same device.

Thirdly we can allow for the possibility that there be a second kind
of query server - one which caches the answers it receives from a
full database query server.  This is a caching query server (QSC).

Fourthly, we allow for the possibility of the sending host
performing ITR functions (ITFH).  The host cannot be behind NAT, but
this saves on specific ITR hardware and makes use of CPU power and
RAM where it is often freely available, without any extra hops.  It
is unlikely that an ITFH would be a full database ITR (but the
architecture should not rule this out), so we assume the ITFH needs
to send queries to a local full database query server (QSD), perhaps
via one or more QSCs.

With no restrictions on the locations of these devices, we allow
their deployment to proceed according to the locally made decisions
about capital cost, mapping traffic (full feed or query and
response).  Combined with "anycast ITRs (ITRDs) in the core)", we
have a highly flexible, fully integrated, elegant architecture which:

1 - Does not drop or delay packets.

2 - Does not require a global query server network, since there
    will be one or more full database query servers in reasonably
    close proximity.

3 - Does not need any "gleaning" or "piggybacking" system for
    conveying mapping information which presumably will soon be
    required, since every ITR either has the full database or is
    close to a query server which has the full database.

3 - Requires a global mapping database feed for a large number
    of ITRDs and QSDs - but which will be used only as far
    as operators choose, not to every ITR.

This is the overall architecture of Ivip, as defined in July last year.

To this, Ivip adds:

1 - Make the mapping distribution *fast* - a few seconds at most
    from users to all ITRDs and QSDs.

2 - Add a mechanism by which QSDs can push mapping changes to ITRCs,
    ITFHs and QSCs which may be handling packets affected by the
    changes.

These two changes mean that the ITRs no longer need to test for
connectivity to ETRs, because the end-user can use their own
connectivity test system (multihoming monitoring system) to change
the mapping accordingly in real time.

So ITRs and ETRs are simpler and the whole system is modular, rather
than integrating reachability testing and multihoming service
restoration decisions into the map-encap scheme, as does LISP and APT.

This also enables the mapping data to be very compact - just a
description of the range of addresses and the address of the ETR.
See "Is 12 bytes really so scary?"

   http://psg.com/lists/rrg/2007/msg00806.html

The simpler mapping information is easier to push *fast*.

These two changes also enable the system to be used for mobile
networks and hosts, for both IPv4 and IPv6, with no need for special
software in the correspondent hosts, and minimal extra software in
the mobile host.

To this, Ivip also adds:

3 - The source address of the encapsulated packets (outer source
    address) is the address of the sending host (inner source
    address) - rather than the ITR's address.

This enables the ETR to easily enforce any source address filtering
imposed at the border routers of the network it operates in - by
dropping any inner packet whose source address is not the same as
the outer source address.

This should also enable Traceroute to operate over the tunnelled
portion of the path, if the sending host runs a modified Traceroute
program which can detect the replies which arrive with different
destination addresses (the ETR's rather than the destination host's).

Ivip doesn't directly support the ITR load splitting traffic to
multiple ETRs.  Load splitting needs to be done by having one or
more IP addresses mapped to one ETR, one or more IP addresses to the
next ETR etc. - with fine (real time) control by the user.

Ivip will also require some charging system to cover the cost of
sending out mapping changes for end-users who change their mapping
frequently, such as for mobility or fancy, dynamic, load-splitting TE.

I intend to revise the Ivip material into multiple, less monolithic,
IDs in the next month or so.  This will include a more detailed
description of the fast push system for mapping data, and of how I
propose to handle PMTUD and fragmentation problems.  The latter will
draw heavily on the on-list discussions with Fred Templin and
Iljitsch van Beijnum.

The result is more complex than ALT + NERD, or APT.  However, it is
a fully integrated system which I think is elegant and highly
flexible.

Ivip is intended to work fine with individual IP addresses (IPv4) or
/64s (IPv6) being mapped to different ETRs.

Ivip also fulfils Tony's desire for flexibility in deploying
caching and non-caching ITRs:

http://psg.com/lists/rrg/2008/msg00115.html

DF >>  You guys that are not favoring caches can other favor
DF >>  full tables and that can't scale to 10^10.
DF >>
DF >>  So do you have a proposal?

TL >   I don't fall into "you guys" because a) I'm in favor
TL >   of caches in some places and b) I'm against them in
TL >   others. I haven't noticed that opinion expressed by
TL >   anyone else yet. Yes, that's something of a proposal.

The Ivip description is longer than for ALT, NERD or APT because it
is more detailed and because Ivip tackles some problems the LISP and
APT developers have not yet attempted to handled, including
Traceroute, ETRs enforcing source address filtering, and especially
the PMTUD/fragmentation problem.

 - Robin   http://www.firstpr.com.au/ip/ivip/

--
to unsubscribe send a message to [email-masked] with the
word 'unsubscribe' in a single line as the message text body.
archive: <http://psg.com/lists/rrg/> & ftp://psg.com/pub/lists/rrg

---

From: Dino Farinacci <[email-masked]>
Date: Tue, 22 Jan 2008 07:58:41 -0800

> DF >>  and a decision to pick one, or blend two.

I said what is left to do is 1) make a decision (see text right above  
this line) or 2) blend two mapping database scheme. We don't know yet.  
We need to experiment.

Dino

---

From: Robin Whittle <[email-masked]>
Date: Wed, 23 Jan 2008 12:29:08 +1100

Hi Dino,

> this line) or 2) blend two mapping database scheme. We don't know yet.

How would experimentation with your current prototype LISP system
lead to any fresh insights about the fundamental limitations of ALT
or NERD?

NERD on its own won't work because every ITR in the world would need
the full feed of mapping updates.

ALT on its own won't work because the ITR drops or greatly delays
(sending them to the ETR via the ALT network) the initial packets
while it waits for the mapping information.  This would make EID
address space suck - so no-one would want to use it.

The logic of this seems inexorable: Any global query system would
often be so slow that it wouldn't be acceptable unless every ITR is
able to deliver the initial packets via some other mechanism within
a fraction of a second.  If all caching ITRs can do that, then why
bother with a global query server network at all?

I don't think anyone believes ALT or NERD alone could possibly form
an acceptable solution, far less the optimal one.

So that leaves your other suggestion: blending the two systems
together.  This is what I explored - making changes to them starting
from the position of the two systems running alongside each other.

When you have NERD ITRs around the place, there is no need to build
the ALT global query and packet delivery system, because it makes
much more sense to use the nearest NERD ITR as a default mapper and
to have a full database Query Server at the same location - perhaps
in the same device as the NERD ITR.  Then there is no need for ALT,
CONS or any other global (expensive, hard to administer, slow and
unreliable) query server system.

If you or anyone else disagrees with my sequence of improvements to
LISP, you will be able to argue why a particular stage of my
improvements makes the system worse and/or suggest some better set
of improvements.

---

From: Eliot Lear <[email-masked]>
Date: Wed, 23 Jan 2008 15:02:03 +0100

Robin,
> the full feed of mapping updates.

Table 1 in Section 5.1 of draft-lear-lisp-nerd-02.txt addresses this 
somewhat.  At 10^8 EIDs, assuming IPv6 addresses, the database size is 
likely to be less than 6 GB.  Let us be pessimistic and say that the 
update rate is 1.0% per day, leading to a change rate of 60MB per day, 
or an hourly rate of 2.5MB.  My netnews server could do this in 1987.  
We're talking about 2050.  What's the problem?

Eliot

---

From: David Meyer <[email-masked]>
Date: Wed, 23 Jan 2008 08:06:09 -0800

Robin,

> lead to any fresh insights about the fundamental limitations of ALT

	I don't think any is saying that. My sense is that its
	more the case that while we work on the theoretical
	aspects of these system (as this thread is, and that is
	all goodness), there are things that one can learn by
	observing a system's behavior. To do that you need
	implementations (or at least simulations). Suffice it to
	say that a lot has been learned in the process of trying
	to make things work (especially in the cases of large
	dynamic systems that are difficult to characterize in a
	bottom up fashion).   

	So there's a theory v. practice point here (and I'll
	leave alone for the moment the whole issue of emergent
	properties that really can't be studied in a bottom up
	fastion).  

> the full feed of mapping updates.

	Notwithstanding Eliot's calculations, this is a concern
	many of us has voiced. 

01:	That's why hybrid systems seem so attractive; but then
	you trade off rate v. state. v. lookup latency. All of
	these systems seem to occupy a different point on in this
	space (except for perhaps CONS and ALT, which are
	architecturally similar in this respect).  I'm sure there
	are other dimensions one can through into this, but for
	now my sense is that these three dominate.

> address space suck - so no-one would want to use it.

	goto 01;

	(I [again, and others] have been concerned not only about
	latency [your point] but also about the aggregate traffic
	load in the ALT core [consider near the "top" of the
	hierarchy, i.e., data traffic "rate" in the control
	plane]).  

> bother with a global query server network at all?

	I don't know if the logic is "inexorable", but your point
	is well taken. We need to examine the tradeoffs in the
	3-space I described above.

> an acceptable solution, far less the optimal one.

	Again, "anyone" is a lot of folks.

> from the position of the two systems running alongside each other.

	So this is an architectural tradeoff in the space I was
	describing. As Noel is found of saying, TANSTAAFL.

> unreliable) query server system.

	But then you need to construct the complete map; again,
	this is just a point in the tradeoff space I described
	above. It would appear that there are only a finite
	number of ways to skin a cat...

> improvements makes the system worse and/or suggest some better set

	I have a somewhat different suggestion. I don't see any
	"solutions convergence" occurring, at least on RRG
	list. What might be helpful is objective criteria that
	could be used to pick "more optimal" points in the
	archtiectural space (here I mean the rate*space*latency
	space). Give such critera, we could do the
	evaluation. Without such critera, well, we're
	speculating.

	Now, I'm not saying we need a "requirements document"
	(been there, done that). But we do need something
	objective that we can use to compare against. 

	Dave

---

From: Brian E Carpenter <[email-masked]>
Date: Thu, 24 Jan 2008 07:19:03 +1300

> We're talking about 2050.  What's the problem?

I seem to hear Tony saying that 10^8 is nothing like enough, unless
I'm missing something in his argument that we should go to host level.
Personally I think that 10^8 is more than plenty, but we do need to get
a fix on this.

    Brian

---

From: Tony Li <[email-masked]>
Date: Wed, 23 Jan 2008 10:36:49 -0800

> Personally I think that 10^8 is more than plenty, but we do need to  

Again, the real question here is about whether we need host  
granularity or not.

If not, then Eliot's figures make perfect sense and the lack of  
granularity also suggests that the rate of change would be relatively  
low, further endorsing his approach.

However, if we do need host granularity, then I think you need about  
3 orders of magnitude more scale, and pure push approaches simply  
won't get you there.

Tony

---

From: Robin Whittle <[email-masked]>
Date: Thu, 24 Jan 2008 13:03:00 +1100

I am responding to the messages from Eliot Lear, David Meyer, Brian
Carpenter and Tony Li.

Eliot wrote:

RW > NERD on its own won't work because every ITR in the world would
RW > need the full feed of mapping updates.

> Table 1 in Section 5.1 of draft-lear-lisp-nerd-02.txt addresses
> this somewhat.  At 10^8 EIDs, assuming IPv6 addresses, the
> database size is likely to be less than 6 GB.  Let us be
> pessimistic and say that the update rate is 1.0% per day, leading
> to a change rate of 60MB per day, or an hourly rate of 2.5MB.  My
> netnews server could do this in 1987.  We're talking about 2050.
> What's the problem?

I agree with you in some respects.  For LISP, the mapping data won't
change at a huge rate, and even though the mapping data is more
complex than for Ivip, the communications volume required is
probably not a problem for ISPs and for larger routers.

Other folks in the LISP team apparently saw things differently,
because they developed CONS and then ALT as a complete solution, not
involving NERD.

Sticking with these assumptions, I will consider a pure NERD scheme.

I think this would be much better than ALT or CONS, because it would
work - fast - without dropping or unreasonably delaying packets.

The major costs are the need for all ITRs to have a lot of RAM and
to have a substantial communications load for incoming mapping data.
 Arguably neither of these will be much of a concern for ISPs and
other organisations with substantial networks by the time the
mapping database gets to this 100,000,000 EID size.

However, it still constrains where you implement ITRs.  Ideally,
ITRs would be cheap or have zero hardware cost.  Then they can be
closer to the sending hosts, reducing the load in each ITR and
ensuring that the total path taken by packets is no longer than it
would be without the map-encap scheme.

Maybe some of the pure NERD, full database, ITRs will have a
"hardware" (specialised processors and cards) FIB which implements
the full set of EIDs directly, but I am assuming that most will have
a FIB which at any one time is only set up to encapsulate packets to
the small subset of EID which the current traffic is addressed to.

In that case, the ITR would store its copy of the database in RAM
(or in FLASH or even a hard drive) and the FIB would be capable of
detecting traffic packets addressed to parts of the address space
which are known to be covered by LISP, but which the FIB has not yet
been set up to handle.

Then the ITR's CPU would function as a query server for the FIB(s)
in the same device.

What do you think of the idea of making that query server function
available to nearby devices?

I think this would be an enhancement to the NERD architecture - to
allow for this, enabling operators to do it when it made sense to them.

Then there could be caching ITRs nearby which send map requests and
get responses really quickly and reliably.  These caching ITRs will
not need all the RAM or continual inflow of mapping information
which the full database ITR needs.

"Nearby" could have various meanings.  "Nearby" doesn't have to be
tightly constrained in the architecture.  (In APT, it is constrained
to being in the same network.)  If operators would rather run one or
more caching ITRs with the main full database ITR operating as a
query server, then I think the architecture should allow for this.
Likewise if the end user wants to run ITRs using the ISP's query
server, or anyone else's query server (maybe their ISP doesn't have
one), then the architecture should allow for this.

The next enhancement is to allow for the separation of the query
server function from the ITR function.  There's no obvious reason
why the architecture should insist they be in the one device.
Operators may choose to do this, and will probably put full database
ITRs and query servers in the same location, to maximise the utility
of the feed of mapping data to that location.

I am keen for you and others to critique the series of enhancements
I proposed in my initial message.  Do you agree or do you think that
one or more of these enhancements makes things worse?  Or do you
have a better enhancement?

One enhancement to the architecture is to allow for caching ITR
functions in the sending host (or DSL modem etc. whatever it is, not
behind NAT).  With local query servers, this would enable a lot of
the ITR work to be done without additional hardware expense.

David Meyer wrote:

DF >>> I said what is left to do is 1) make a decision (see text
DF >>> right above >>> this line) or 2) blend two mapping database
DF >>> scheme. We don't know yet. We need to experiment.

RW >> How would experimentation with your current prototype LISP
RW >> system lead to any fresh insights about the fundamental
RW >> limitations of ALT or NERD?

>       I don't think any(one) is saying that.

I raised what I consider to be fundamental limitations of pure ALT
and pure NERD.  Rather than respond directly to these, Dino said he
needed to do more experimentation.  So I figure he meant that
experimentation would or might lead him to some insights which would
prove my critique was wrong, or perhaps enable him to come up with a
workaround or some other enhancement to avoid the problems I cited.

>       My sense is that its
>       fashion).

OK, but the limitations of ALT and NERD seem to be fundamental.

I see no prospect that running a tiny LISP system (as you do at
present) or running a simulation of a larger one is going to find a
workaround for those limitations.  The only way of overcoming them
is to change these architectures into something different, or use
something different to start with.

My proposed enhancements start with NERD and do away with the need
for ALT or CONS at the very first step.

>> NERD on its own won't work because every ITR in the world
>> would need the full feed of mapping updates.
>

OK.

>       hierarchy, i.e., data traffic "rate" in the control

Yes, this is another objection to any global query server network
such as CONS or ALT, unless there is caching in the network, or some
fancy distributed system for answering the queries.

>> often be so slow that it wouldn't be acceptable unless every ITR
>> is able to deliver the initial packets via some other mechanism
>> within a fraction of a second.  If all caching ITRs can do that,
>> then why bother with a global query server network at all?
>

The only way I can imagine this logic failing is if the fast
delivery of early packets was expensive, and couldn't be sustained
for the main body of traffic.

Maybe you could argue that using a "Default Mapper" to deliver the
initial packets quickly is too expensive for the main body of
traffic, since these would quickly become overloaded.  But if you
have a local default mapper, there seems to be no need for a global
query server network such as CONS or ALT, since the mapping query
can be answered quickly by that default mapper or by a query server
at the same location, running from the same feed of mapping data.

>> I don't think anyone believes ALT or NERD alone could possibly
>> form an acceptable solution, far less the optimal one.
>

OK.  Eliot and perhaps others think a pure NERD system would be
fine.  I would favour this over a pure CONS or ALT system any day.
But a pure NERD system can easily be improved as I suggest to allow
for caching ITRs and ITR functions in sending hosts.

Anyone who believes in a pure ALT system must be expecting end-users
to put up with initial packets being dropped or delayed so much as
to be useless or worse than useless if and when they arrive.  I
think this idea is completely unworkable, but if there are such
folks, then I stand corrected.

>> together.  This is what I explored - making changes to them
>> starting from the position of the two systems running alongside
>> each other.
>

There are probably no free lunches, but there are combinations of
techniques which work elegantly and efficiently by complementing
and/or supporting each other.  So some lunches are cheaper, more
nutritious and more enjoyable than others.  For instance:

>> When you have NERD ITRs around the place, there is no need to
>> build the ALT global query and packet delivery system, because it
>> makes much more sense to use the nearest NERD ITR as a default
>> mapper and to have a full database Query Server at the same
>> location - perhaps in the same device as the NERD ITR.  Then
>> there is no need for ALT, CONS or any other global (expensive,
>> hard to administer, slow and unreliable) query server system.
>

I think this enhancement is much more than choosing a particular
trade-off between multiple costs and benefits.  For one thing, it
eliminates the need for a global query server network.  For another,
it enables all packets to be delivered quickly.  These are
tremendous benefits in terms of cost, complexity, reliability and
performance.

>> If you or anyone else disagrees with my sequence of improvements
>> to LISP, you will be able to argue why a particular stage of my
>> improvements makes the system worse and/or suggest some better
>> set of improvements.
>
> 	list.

I think it is productive to try to combine the best elements of
current proposals and/or to ask questions like "If we had Y, and did
Z to it, then why would we still need X, which previously we thought
was essential?"

>       What might be helpful is objective criteria that

I don't think we need any formal documents - or algorithms for
evaluating and trading off costs and benefits - to agree that it is
better, cheaper and simpler to have NERD with the possibility of
local query servers and caching ITRs than to have NERD alone, ALT
alone or NERD and ALT running in parallel.

Brian Carpenter wrote:

RW >>> NERD on its own won't work because every ITR in the world
RW >>> would need the full feed of mapping updates.

EL >> Table 1 in Section 5.1 of draft-lear-lisp-nerd-02.txt
EL >> addresses this somewhat.  At 10^8 EIDs, assuming IPv6
EL >> addresses, the database size is likely to be less than 6 GB.
EL >> Let us be pessimistic and say that the update rate is 1.0% per
EL >> day, leading to a change rate of 60MB per day, or an hourly
EL >> rate of 2.5MB.  My netnews server could do this in 1987.
EL >> We're talking about 2050.  What's the problem?

> I seem to hear Tony saying that 10^8 is nothing like enough,
> unless I'm missing something in his argument that we should go to
> host level.  Personally I think that 10^8 is more than plenty, but
> we do need to get a fix on this.

I agree we need some realistic figures, otherwise any time someone
proposes a push system, another person will think of a number,
double it, and say push can't work with that number.

I am absolutely in favour of separate mapping being allowed and
efficiently supported "per host" - meaning per IP address in IPv4 or
per /64 in IPv6.

An entire network could run from one of these.

Even if there was only one host behind it, I think multihoming and
portability of the number between ISPs (apologies to those who
bristle at this phrase) should be efficiently supported by the new
architecture.

All the schemes - LISP, APT and Ivip - can technically support
single "hosts".  Ivip can support micronets (a range of contiguous
addresses mapped to the same ETR address) of arbitrary size, while
the others restrict micronet lengths to powers of 2.

I don't think the new architecture should be made as if we are
scared of this usage, as if it should be suppressed or as if it is
never likely to be needed.

Probably the way to cope with the costs of handling large numbers of
end-user-generated EID divisions (micronets) and mapping changes is
is to have some kind of charging scheme for each mapping change.
Then, those folks who want to pay the charge for frequent changes
for their single host, or their entire network hanging off a single
IP address or /64, can do so if the benefits are worth the fee they
pay.  The cost doesn't have to be very high, I believe.

Ivip is intended to support mobility between ISPs for individual
hosts or networks.

There probably is some upper limit on the number of devices which
might do this.  If we imagine 10 billion people, 3/4 of them with a
cell phone, and they all want session survivability on the one IP
address or /64 as the "phone" (PC, audio visual player, P2P network
data sucker, Second Life client etc.) roams from one radio network
to the next, then we have a figure of 10^10.

With pure NERD, the long-term figure for the number of EIDs, and for
the rate of change of their mapping is crucial - because all ITRs
need to get the full feed of mapping changes and to store the full
database.  This increases the cost of building and running an ITR
and so of constrains how many ITRs you can have.  So this causes
difficulties with packets having to reach that smaller number of
ITRs - with each ITR handling a larger load.

Pure CONS or ALT isn't fussed about the total number of EIDs or
their rate of change.  But pure CONS or ALT drops and delays packets
- so it is never going to be successfully deployed.

If you add query servers and caching ITRs to NERD, you don't need
CONS or ALT, but the total number of EIDs and their rate of change
remains important.

My proposed enhancement of NERD enables flexible deployment of
caching and non-caching ITRs, so the system copes nicely in the
future if the number of EIDs and rate of change becomes a serious
burden for full database (non-caching) ITRs: simply have less of
them, and use more caching ITRs and local query servers.

So no matter how big the number and rate of change gets, this
enhancement to NERD provides the flexibility for operators to run
their system at their chosen spot along a continuum of costs and
benefits for caching and non-caching ITRs.

Tony Li wrote:

EL >>> (As quoted above.)
EL >>> We're talking about 2050.  What's the problem?

BC >>  I seem to hear Tony saying that 10^8 is nothing like enough,
BC >>  unless I'm missing something in his argument that we should
BC >>  go to host level.

BC >>  Personally I think that 10^8 is more than plenty, but we do
BC >>  need to get a fix on this.

> granularity also suggests that the rate of change would be
> relatively low, further endorsing his approach.
>
> However, if we do need host granularity, then I think you need
> about 3 orders of magnitude more scale, and pure push approaches
> simply won't get you there.

Yes, but I would say two orders of magnitude - 10^10 as an outside
limit.

APT, Ivip and my enhancement to NERD are not pure push approaches.

I think that Ivip is the most flexible of the current approaches.
No matter what the number of micronets (EIDs), and no matter how
often some or many of them change, I argue that the flexibility of
Ivip is better than the other approaches at enabling operators to
deploy their equipment in ways which best handle the challenges of
the day.

  - Robin

---

From: Tony Li <[email-masked]>
Date: Wed, 23 Jan 2008 18:16:20 -0800

Hi Robin,

> Yes, but I would say two orders of magnitude - 10^10 as an outside

Not to quibble, but...  10^10 is only 10 billion.  We're about to add  
6 billion cell phones to the net, and the thought of every human  
having on average 2 devices within 50 years doesn't seem like it's  
impossible.

~"If an architectural parameter isn't obviously too large, then it's  
probably too small."~
										- Ross Callon

Tony

---

From: Brian E Carpenter <[email-masked]>
Date: Thu, 24 Jan 2008 15:31:03 +1300

On 2008-01-24 15:16, Tony Li wrote:
> Not to quibble, but...  10^10 is only 10 billion.  We're about to add 6
> billion cell phones to the net, and the thought of every human having on
> average 2 devices within 50 years doesn't seem like it's impossible.
> 

Sure, and nobody has even mentioned sensor networks recently.

But is that the point? I'm not arguing that we shouldn't be able to map
EIDs as long as /128. I'm suggesting that these will be a small minority,
and that the size of the map is likely to be in the 10^8 range at most, since
most of the entries will be sites (for some definition of "site", but
on average, significantly larger than a single household).

   Brian

---

From: Tony Li <[email-masked]>
Date: Wed, 23 Jan 2008 18:38:36 -0800

> on average, significantly larger than a single household).

A fair point, but I would certainly be more comfortable knowing that  
the mapping subsystem was designed to deal with the worst case load  
rather than simply the expected load.

Something about half-inch gusset plates on bridges comes to mind...  ;-(

Tony

---

From: Brian E Carpenter <[email-masked]>
Date: Thu, 24 Jan 2008 15:46:19 +1300

On 2008-01-24 15:38, Tony Li wrote:
> A fair point, but I would certainly be more comfortable knowing that the
> mapping subsystem was designed to deal with the worst case load rather
> than simply the expected load.
> 

That's also a fair point, but of course a factor two on a lump of steel
is easier to arrange than a factor 100 on a distributed database.

    Brian

---

From: Tony Li <[email-masked]>
Date: Wed, 23 Jan 2008 19:02:43 -0800

> is easier to arrange than a factor 100 on a distributed database.

Agreed.  However, the steel is also easier to retrofit if you find  
you've underestimated.

Tony

---

From: David Conrad <[email-masked]>
Date: Wed, 23 Jan 2008 19:59:25 -0800

Robin,

> probably not a problem for ISPs and for larger routers.

Wouldn't it be more correct to say that if you make the assumption  
that the mapping data won't change at a huge rate and/or the map  
itself isn't overly large, then it is probably safe to say that  
communications volume won't be a problem.

The problem I personally have is that I don't feel comfortable in  
making either of those assumptions.  In fact, one might argue that  
making both of these assumptions is what has gotten us into trouble in  
the first place.

> available to nearby devices?

It is something I think should be explored.

> to be useless or worse than useless if and when they arrive.

I will note that back when Proteon was the router maker of choice, it  
was fairly common for the first packet in a new incoming conversation  
to get dropped due to the need to do an ARP lookup, yet people got by  
(most didn't notice).  As the technology improved, the need to drop  
packets waiting for ARP lookups was removed. It isn't clear to me why  
history wouldn't repeat itself.

> and/or supporting each other.

As others have noted, the downside is that you're adding a fourth  
vector the the triplet of (rate, state, latency), namely complexity.   
It may be that this is necessary and a mixed model is the best way  
forward, but it is yet another factor in a "no free lunch" tradeoff.

> is to have some kind of charging scheme for each mapping change.

I suspect along this path lay madness.  Assuming the imposition of a  
particular operational business model in order to alleviate a downside  
of an architecture hasn't worked very well in the past.

Regards,
-drc

---

From: Eliot Lear <[email-masked]>
Date: Thu, 24 Jan 2008 09:14:31 +0100

Robin,
> available to nearby devices?

I ponder this in the NERD draft if one presumes that one loads "near" 
databases and uses ALT or CONS for "far" networks.  A simpler approach, 
however, given the lower volume of data, would be to receive ALL 
databases, and keep them in a secondary cache or storage, and then keep 
the query on the box.

> allow for this, enabling operators to do it when it made sense to them.

I remain averse to delay.  Even the above scheme would require 
architectural changes, and would impose delay for cache misses, but 
those cache misses would be extremely small.  I also remain averse to 
mechanisms where an inability to complete a query due to a device 
failure would cause either yet more delay or a mapping failure.  With 
NERD, the worst that happens is that you use the old mapping for a time.

And indeed I am engineering a solution that does not require host 
granularity.  I believe mechanisms such as HIP and MIPv6 need to be 
improved to scale to address that problem.

But that's me.

Eliot

---

From: Eliot Lear <[email-masked]>
Date: Thu, 24 Jan 2008 10:15:34 +0100

David,
> making both of these assumptions is what has gotten us into trouble in 

I think one must argue that either this is the case or is not the case, 
but not leave this sort of thought just dangling.  For my part, I'll 
argue that no such assumptions were made, but that we simply did what we 
knew how to do, and knew of no better approach.

A *fundamental* change between today and the world we perceive with LISP 
is how we manage different types of state.  Today everything is lumped 
together in operational state.  LISP separates that state into two 
buckets and treats them quite differently.

Eliot

---

From: [email-masked] (Noel Chiappa)
Date: Thu, 24 Jan 2008 07:40:00 -0500 (EST)

> From: David Conrad <[email-masked]>

    > Assuming the imposition of a particular operational business model in
    > order to alleviate a downside of an architecture hasn't worked very
    > well in the past.

Heck, we haven't had much luck adopting a particular operational business
model in order to alleviate a downside of mathematics (i.e. charging for
global routing table slots)...

	Noel

---

From: [email-masked] (Noel Chiappa)
Date: Thu, 24 Jan 2008 07:41:55 -0500 (EST)

> From: Tony Li <[email-masked]>

    > However, the steel is also easier to retrofit if you find you've
    > underestimated.

Q.v. IPv4 (although that's a worst-case, since that involves all the hosts too).

	Noel

---

From: Peter Sherbin <[email-masked]>
Date: Thu, 24 Jan 2008 08:01:43 -0800 (PST)

> model...

E=mc^2 makes economics a natural part of any project including the Internet.
Officially IETF does not comment on business models and yet economical topics
regularly surface at multiple discussion lists.

In data communications the model is straightforward where the sender of data bears
the cost of moving it to the final destination. What if IETF just postulates that
fact and let markets to figure out how to apply it to specific cases.

Thanks,

Peter

> global routing table slots)...

      ____________________________________________________________________________________
Never miss a thing.  Make Yahoo your home page. 
http://www.yahoo.com/r/hs

---

From: Tony Li <[email-masked]>
Date: Thu, 24 Jan 2008 08:42:17 -0800

> regularly surface at multiple discussion lists.

<co-chair>
Once again, we're now operating as part of the IRTF.  AFAIK, that  
restriction does not apply.

Please, comment away.  However, please keep it on topic...
<co-chair/>

Tony

---

From: Xu Xiaohu <[email-masked]>
Date: Thu, 24 Jan 2008 18:28:05 +0100

Hi Eliot,
> improved to scale to address that problem.
HIP uses host granularity because the HIT/HI is a flat label without any
structure, but the HoA in MIPv6 has structure so it's easy to scale to
address that problem, e.g. NEMO or CRIO like mechanisms.
Best wishes,
Xiaohu XU

---

From: David Conrad <[email-masked]>
Date: Thu, 24 Jan 2008 09:48:05 -0800

Eliot,

On Jan 24, 2008, at 1:15 AM, Eliot Lear wrote:
>> making both of these assumptions is what has gotten us into trouble  
>> in the first place.
>
> I think one must argue that either this is the case or is not the  
> case, but not leave this sort of thought just dangling.  For my  
> part, I'll argue that no such assumptions were made, but that we  
> simply did what we knew how to do, and knew of no better approach.

Whether or not the assumptions were explicitly made in the past isn't  
really relevant and I do not mean to imply any criticism -- I would  
agree we did what we knew how to do.  However, we know more now so we  
should take that information into account.

> A *fundamental* change between today and the world we perceive with  
> LISP is how we manage different types of state.  Today everything is  
> lumped together in operational state.  LISP separates that state  
> into two buckets and treats them quite differently.

Yes. The issue (at least for me) is how to propagate the mapping info  
since we're moving the scaling thrash problem from the FIB to the  
map.  Pushing around the whole mapping table seems to me to have the  
potential of simply recreating the problem 'later'.

---

From: Iljitsch van Beijnum <[email-masked]>
Date: Sun, 27 Jan 2008 18:26:14 +0100

> 3 orders of magnitude more scale, and pure push approaches simply  

What's wrong with the approach where a host that is away from home  
gets its packets tunneled from home to its current location and then  
negotiates a direct tunnel with its correspondents for more optimal  
packet flow?

---

From: Tony Li <[email-masked]>
Date: Mon, 28 Jan 2008 00:37:56 -0800

On Jan 27, 2008, at 9:26 AM, Iljitsch van Beijnum wrote:

> gets its packets tunneled from home to its current location and  
> then negotiates a direct tunnel with its correspondents for more  
> optimal packet flow?

Nothing 'wrong' per-se.  However, it would have the drawbacks of  
requiring host modifications and tunneling, with the associated  
issues.  There are also going to be latency issues vs. going direct.

Tony