Subject: [RRG] Mobility, update rates & charging per update

From: Robin Whittle <[email-masked]>
Date: Tue, 18 Mar 2008 01:20:43 +1100

Short version:  Map-encap direct support for mobility doesn't mean
                frequent updates, because the mapping change only
                occurs when a new TTR is used - which only happens
                when the mobile device moves to an access network
                ~1000 km distant from the current TTR.

                Why we don't need to worry so much about the
                maximum update rate in a push or hybrid push-pull
                system if that system charges per update - since the
                system will be self-funded and grow to whatever
                capacity the demand requires, at whatever price-per
                update the system can support.

                This removes the biggest problems of "too frequent"
                updates - as bedevils the BGP system - that they
                place a burden on people who are not deriving any
                benefit, including being paid, for each update.

Hi Tony,

In "RE: [RRG] Reactivating the RAM list?" you wrote:

>> indicating that we should drop the mobility discussion for now.

> ... And the operative words here are "for now".

OK - but I would be keen to hear from people on the list of
privately that they either understand and accept my point about
mobility not requiring frequent updates, whilst benefiting from low
latencies for updates.  Likewise I would be keen to hear any
critiques.

I think it is a really important point and no-one has yet agreed
with me on the list - or disagreed.

A guide to my recent attempts to explain this is:

   http://www.firstpr.com.au/ip/ivip/#mobile

I request that if we pause the mobility discussion for the moment,
that people go forward with the tentative notion that maybe mobility
won't involve changes every minute or hour - but only usually when
people travel large distances like 1000km.   Then, the 5 billion
mobile end-users scenario doesn't necessarily mean astronomical
update rates.

> I have every intention of returning to the topic at the
> appropriate time, but for the sake of making forward progress, it
> seems like there are some more basic issues that we can
> deal with (granularity & churn) and then revisit mobility in a
> bit.

> If, for example, we conclude that we want host level granularity
> and can support a churn of 1 nano-second, then the entire mobility
> discussion is moot.

I support host-level granularity and have some WAGs:

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

which gives about half the update rate to mobiles, with total update
rates in the few hundreds per second, which seems feasible to me -
even when whatever number (X billions - one for every person and
their dog) of mobile devices have 5 million people and dogs a day
moving 1000km or so.

> So let's decide where we are on the basic issues and then come
> back to the more complex issues.

OK.

>> I am also wary of the notion of trying to set an upper bound on
>> the rate of mapping changes, because this may involve an
>> assumption that each mapping change doesn't pay its way and so
>> causes unreasonable burdens on other parties.  That is true of
>> BGP or APT, but is substantially not the case for Ivip or
>> potentially other proposals.

> Interesting point.  I'm not quite following.  Is this is an
> intrinsic difference between push and pull, or is there something
> more?

In most practical examples I could think of, it is a difference
between push and pull.  But impractical counter-examples indicate
the difference is not actually intrinsic.

With push in the form of Ivip's hybrid push-pull, there is a unified
but decentralised, fault tolerant, set of servers called the
Launch system which sends, every second, a bunch of updates to the
cross-linked tree structured Replicator system, which fans them out
to ~x00,000 full database ITRs and query servers all over the Net.

This is bold stuff, but we are designing a new routing and
addressing architecture, so I figure it is worth going to this sort
of trouble to get the mapping out across the planet in a fast,
streamlined, robust manner.

The Launch system and quite a lot of the Replicator system is owned
and run collectively by the Root Update Authorisation Systems, each
of which is a separate commercial entity, probably for-profit.

This is described in pages 33 to 48 of:

http://www.firstpr.com.au/ip/ivip/draft-whittle-ivip-db-fast-push-00.pdf

All updates are initiated by end-users (or some system with the
end-user authorises to make the updates, such as a multihoming
monitoring company) and go through one of the RUASes.  Each RUAS
handles one or more Mapped Address Blocks (MABs), so each produces,
ever second, a bunch of updates for its own MABs.

End-users can choose between various RUASes (and in so doing decide
what fees to pay, which MAB their micronet address space comes from
etc.) and every update goes through one RUAS.  I am guessing their
might be one or two dozen RUASes, not hundreds or thousands.

RUASes will charge the end-users directly - if the end-users are
direct customers - or indirectly if the end-users are customers of
some intermediate Update Authorisation Service company.  The charges
will be, in part, for updates - but will also cover how much mapped
address space each end user has.  (There may also be traffic charges
for high-volume end-users where the traffic to those end-user's
micronets burdens the "anycast ITRs in the core/DFZ" which the RUAS
runs to make the MAB reachable from hosts in networks without ITRs.)

This fee per update will allow the RUASes to pay for the Launch and
Replicator systems - and help them turn a profit.

My WAGs lead to 228 updates a second - 2 million a day.  At 5 cents
an update, this is a million dollars a day, more than enough to
build and run a handsome Launch and Replicator system.

(For initial deployment, the Replicator system would use existing
stable servers, such as nameservers which were not too heavily
loaded - since the update volume would be quite light for a few years.)

People here frequently pay a cent a second to talk on a cellphone,
so I figure paying 5 cents to change mapping when mobile (after
moving 1000km or so, and so using another TTR in the new area) will
be fine.

Mapping changes for TE would be well worth 5 cents to many busy
network operators, since they give ~5 second latency control over
whether a micronet is mapped to one ETR or another.  So there is an
unknown demand there, which would depend very much on the price,
which is also unknown.

For a million dollars a day I reckon you could run most of a
fast-push system, whether it was doing 1000 changes a second at one
cent each, or 200 a second at 5 cents.

If there was demand for 100,000 changes a second, at a cent each, I
am sure there would be a way of doing it ($3.65 billion a year) -
but rates such as this are going to be difficult or impossible for
full database ITRs and query servers to process with foreseeable CPU
and RAM technologies.

By the time it happens - say 2020 - I could imagine 1000 updates a
second, on average, being a feasible.  However, I don't think we
will need this rate.  Maybe a hundred a second or so will be fine,
depending on the demand for TE changes.  The fast hybrid push-pull
system is is a streamlined system designed for this purpose, not the
inefficient BGP approach of a bunch of routers chattering to each
other with the information flowing across the network like rumours
through a crowd.

The key point is that the physical and commercial structure of this
fast hybrid push-pull system is ideally suited to charging for each
update, and so raising the revenue to run the system and to set
pricing so the actual update rate does not exceed the technical
capabilities of the system.

This means we don't have to worry so much about absolute update
rates, since we are not trying to prevent a meltdown similar to the
problem with DFZ routes and updates in BGP today.  The meltdown is
caused by more and more people adding routes, which cost a lot for
everyone who runs a DFZ router - but without any payment from the
people who advertise the routes:

  http://bill.herrin.us/network/bgpcost.html

It would be a mistake to build a push or hybrid push-pull system
with free updates, or to assume that this is how any practical
system would in fact work.

With pull, you could have a reasonably centralised source of
mapping, not unlike the RUAS idea of Ivip.  Then you could have a
small number of query servers, and each ITR could verify the
signature of the mapping replies it gets - since the ITRs could
feasibly authenticate the signatures of the small number of RUASes.

That would greatly simplify the problem of authenticating the map
change commands, because the small number of RUASes would be the
gateway to a billion or more end-users.  (ITRs can't be expected to
authenticate billions of different signatures.)

This "centralised pull" system would also be amenable to charging
for updates, and or for charging in part of the basis of the number
of requests for each mapping.

There is less need - perhaps no need - to charge for updates in a
pure pull system, since generally changing the mapping doesn't
burden any ITRs.  However, if a pull system such as LISP-ALT had
some EIDs with really short caching times, for fast response to
changed mapping, then this would be widely perceived as an
unreasonable burden on the ALT network, and on the ITRs handling
traffic addressed to those EIDs.

However, the existing pull systems (ALT and TRRP) do not use this
centralised approach.  They have fully decentralised authoritative
query servers (ETRs or nameservers respectively), each controlled
directly or indirectly by one of the billion or so end-users.

I think this will be a nightmare to run securely.  It is also an
architecture which resembles BGP in some important and undesirable ways:

1 - The changes are injected into a global system, from any point -
    raising difficulties for any one part of the network being sure
    that any mapping information injected from near or far is
    properly authorised.

2 - In the absence of some central register of what is allowed,
    there is no way of erecting a gate to improve and centralise
    authentication of mapping information.

3 - Likewise, there is no way of stopping the mapping information
    which is injected by end-users who don't pay some fee for each
    announcement, change etc.

4 - Consequently, the ALT network suffers from the potential that
    it could be swamped by a subset of end-users producing mapping
    information with very short cache times, whether or not the
    mapping actually changes much.  (In BGP, it is the changed
    advertisements which burden the whole network.)

However, it is not as bad with ALT as with BGP, since with ALT, the
more frequent requests and responses only come from and go to that
subset of ITRs which is actually handling traffic, while with BGP, a
changed advertisement could affect every DFZ router.

With pure pull, we don't need to fuss so much about update rates
(except as noted with very short cache times), so in general you
don't need to worry about charging for them, or the total rate of
change.

With a pure push, or hybrid push-pull, we do need to worry about
each change being a burden on the push network, and computationally
on the full database ITRs and query servers which receive every
change.  However, if there is a reasonably centralised gateway -
such as the RUASes in Ivip - then they can charge a small fee, and
thereby  pay for whatever push network is required to meet the
demand of the day, at that price.  So then we don't need to worry so
much about changes burdening people who don't benefit from them in
some way - which is the nature of one of the primary routing
scalability problems with BGP which we are trying to solve.

If you had a push or hybrid push-pull network without such charging,
you would have difficulties showing why anyone would build it, and
you would have to figure out either what maximum rate end-users
might  collectively drive changes into it, or some way to deter
"excessive" sending of changes, however defined.

  - Robin

--
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: "Joel M. Halpern" <[email-masked]>
Date: Mon, 17 Mar 2008 10:55:34 -0400

One small aspect that I think I am seeing here is the same words 
("incrementally deployable") being used to describe two different 
concepts.  I may be confused, but it looks to me like:

Deployable incrementally without disruption:  This means that a portion 
of the net (host, site ISP, whatever) can deploy the system without 
losing capability or connectivity.  A flag day is not necessary in order 
to get the system operational.

Deployment incremental incentives:  This sounds like what Robin is 
asking for, and is related to a bunch of work I have seen from folks 
like Dr. Odlyzko on the economic incentives that are needed to drive 
deployment.    It includes analysis of issues like when do folks need 
positive return on new technologies to cause them to deploy.

They are both valid concerns.  But I think they are two different 
dimensions.

Yours,
Joel

---

From: Jari Arkko <[email-masked]>
Date: Mon, 17 Mar 2008 17:37:56 +0200

Joel,

> They are both valid concerns.  But I think they are two different

Right. Thanks for explaining this so clearly.

And I agree with Robin that mobility does not have to imply change of
the tunnel router endpoint. This does reduce mapping changes. However,
I'll note that administrative boundary crossings are quite typical even
in situations where you don't move a lot physically. E.g., from my
office to the city and then to my home; not far away physically, but
they reside in very different places in the Internet topology.

(In any case, what I am looking forward from the RRG or anyone who is
working in this space is a solution to the routing scalability problem.
I don't have a solution for that. I do have plenty of solutions for the
mobility problem, however, some deployed some not. I have a hard time
believing mobility is going to be the deciding factor with regards to a
new routing architecture. Lets see a working routing architecture first.
Just a personal opinion...)

Jari

---

From: Robin Whittle <[email-masked]>
Date: Tue, 18 Mar 2008 12:26:09 +1100 (EST)

Hi Jari,

Thanks for this:

> the tunnel router endpoint. This does reduce mapping changes. 

I am maintaining links to messages and other resources concerning
map-encap support for mobility at:

> However, I'll note that administrative boundary crossings are quite 
> typical even in situations where you don't move a lot physically. 
> E.g., from my office to the city and then to my home; not far away 
> physically, but they reside in very different places in the Internet 
> topology.

The mobile node can still use the original TTR (Translating Tunnel
Router, which behaves like an ETR to the map-encap system).  The only
reason for using another TTR would be that it is closer to the currently
used access network and that the first one was far enough away (assuming
this distance would worsen traffic path lenghts, which would often be
the case) that the extra path lengths was a concern to the user.  Then,
it would be worth doing a mapping change to the new TTR.  

Assuming TTRs were located at or near major Internet peering points, I
imagine that most networks in most major cities or geographical areas
would have a link of some kind leading to that peering point.

With traffic to the mobile node from globally dispersed hosts, it
probably doesn't matter much if the TTR is 1000km away, unless for some
reason there are so many hops in that distance, or packet loss, that it
would be better to have a closer TTR.

Also, if you were in a city getting a lot of traffic from that city, or
from the same access network, then it would be best to have a TTR as
close as possible to or within the access network.

But the mobility system will still work even if the TTR is on the other
side of the planet.  Choosing a closer TTR and changing the mapping to
that is simply to reduce path length, delays and packet loss.

If you working for a large corporation, your mobile node's care-of
address at work (say WiFi in the office, or via an Ethernet cable) would
be in the corporate network - which may not have many links to the rest
of the Net.  Perhaps it works primarily over private links, to support
inter-office communication as the first priority.  Then, the nearest
link to the rest of the Net may be some distance away - perhaps in
another country.  That would be a case where it might be best to use a
nearby TTR.  If you were exchanging a lot of traffic with other hosts in
the same network, including mobile hosts, it would be best if your
mobile node and and the others used a TTR in your network, reasonably
close to your point of connection.

> working in this space is a solution to the routing scalability 
> problem. I don't have a solution for that. 

   http://www.firstpr.com.au/ip/ivip/Ivip-summary.pdf

> I do have plenty of solutions for the mobility problem, however, 
> some deployed some not. 

The map-encap mobility approach with TTRs I suggest is the only one I am
aware of which provides generally optimal path lengths without requiring
any new software in the IPv4 or IPv6 correspondent host.

> I have a hard time believing mobility is going to be the deciding 
> factor with regards to a new routing architecture. Lets see a working 
> routing architecture first. Just a personal opinion...)

I think there are big differences between the map-encap proposals, such
as Ivip being modular - leaving reachability and multihoming failure
restoration decisions to the user to perform in real-time.

Nonetheless, if two map-encap systems were judged reasonably equivalent
in terms of overall support for scalable multihoming, portability and
TE, and one could support a powerful new form of mobility, while the
other could not (such as LISP, which aspires only to work with current
mobile-IP techniques) then I would think that mobility would be the
deciding factor.

  - Robin

---

From: Scott Brim <[email-masked]>
Date: Tue, 18 Mar 2008 15:26:08 -0400

On 3/17/08 11:37 AM, Jari Arkko allegedly wrote:
> I don't have a solution for that. I do have plenty of solutions for
> the mobility problem, however, some deployed some not. I have a hard
> time believing mobility is going to be the deciding factor with
> regards to a new routing architecture. Lets see a working routing
> architecture first. Just a personal opinion...)

Exactly.

Thanks ... Scott

---

From: Dino Farinacci <[email-masked]>
Date: Tue, 18 Mar 2008 16:02:31 -0700

>> architecture first. Just a personal opinion...)

Good answer Jari. ;-)

Since it seems the benefits of a host-based scheme is only for  
mobility, are you conjecturing a host-based scheme is not necessary?

Dino

---

From: Xu Xiaohu <[email-masked]>
Date: Wed, 19 Mar 2008 09:56:50 +0100

> -----邮件原件-----
> 发件人: [email-masked] [mailto:[email-masked]] 代表 Dino Farinacci
> 发送时间: 2008年3月19日 0:03
> 收件人: Scott Brim
> 抄送: Jari Arkko; Joel M. Halpern; Routing Research Group
> 主题: Re: [RRG] Mobility, update rates & charging per update
> 

Hi Dino,

As I known, the benefit of a host-based scheme is not limited to mobility.:)

BTW, there are some statements in RFC 1752 "Recommendation for IPng" as
follows:

1) Develop an understanding of the level of urgency and the time constraints
imposed by the rate of address assignment and rate of growth in the routing
tables.

2) Define the scope of the IPng effort based on the understanding of the
time constraints.

3) We needed a reasonable estimate of the time remaining before we exhausted
the IPv4 address space in order to determine the scope of the IPng effort.
If the time remaining was about the same needed to deploy a replacement,
then we would have select the IPng which would only fix the address
limitations since we would not have enough time to develop any other
features.  If more time seemed available, we could consider additional
improvements.

Does the above statement still have some value of reference for us?

Best wishes,
Xiaohu XU

---

From: Randall Atkinson <[email-masked]>
Date: Wed, 19 Mar 2008 04:02:06 -0700

% Since it seems the benefits of a host-based scheme is only for
% mobility, ...

The above assertion isn't obvious and isn't what I thought Jari said...

Ran

---

From: Jari Arkko <[email-masked]>
Date: Wed, 19 Mar 2008 16:40:56 +0200

Ran, Dino,

> The above assertion isn't obvious and isn't what I thought Jari said...
Right. Clearly one of the benefits of a host-based scheme is that it
might be capable of handling host based mobility as well. Likewise, a
router based approach might be capable of handling network & mobile
network type mobility. Be that as it may, again I'm not sure that
matters so much at this stage.

There may be other advantages (and issues) in host based schemes.

> mobility, are you conjecturing a host-based scheme is not necessary?

I would not make this conclusion. Lets see the proposals and see how
they compare in terms of some of the other properties... the ones that I
consider important, like deployability or effects to the rest of the
Internet.

(However, my personal default assumption is a router-based scheme,
because I think it will be more deployable. I am willing to be convinced
otherwise, however. I'm reading Ran's proposal at the moment, for
instance...)

Jari

---

From: David R Oran <[email-masked]>
Date: Fri, 21 Mar 2008 07:32:54 -0400

> they reside in very different places in the Internet topology.
There is also the pesky "capture effect" in wireless systems in the  
seams between two competing service providers. In the early days of  
GSM, the provider in one country would try to "reach across the  
border" simply in order to cause calls to roam internationally. It  
reportedly took some hard political work on the MOU to stamp that  
process out and have fair rules for node capture at the seams.

I don't think this necessarily has to affect the mobility update rate,  
but it does given a policy dimension to the hysteresis.

Speaking as an individual, I frankly would prefer we did not address  
mobility in this RRG effort.

> problem.
> the