Subject: [RRG] Is 12 bytes really so scary?

From: Robin Whittle <[email-masked]>
Date: Sat, 08 Dec 2007 19:31:59 +1100

I listened to the Friday morning meeting via a 64kbps MP3 stream -
and didn't notice any glitches whatsoever.  This is a modest,
commonplace, consumerish, data rate - completely uneventful, across
the planet in 17 hops from Oregon to Melbourne, Australia.

An ITR-ETR scheme with real-time (a few seconds ideally) push
distribution of mapping data only needs 12 bytes for each mapping
change, for IPv4:

  4 bytes  Micronet start address
  4 bytes  Length
  4 bytes  ETR address

Length would compress well, since in virtually all updates the upper
16 bits would be zero.  There's no need for lists of alternative
ETRs or for ITRs to decide between them.  This is assuming that the
ITRs are not required to follow instructions regarding load
splitting - ie. that the desired TE can be done by having some IP
addresses mapped to ETR-A and others to ETR-B etc.

12 bytes is all we need for IPv4.

IPv6 requires 32 bytes:

   8 bytes  Micronet start (bits 127 to 64)
   8 bytes  Length (bits 127 to 64)
  16 bytes  ETR address

but it will be a long time, if ever, before IPv6 is highly utilized
- and by then bandwidth, RAM etc. will be even cheaper.

Lets ignore protocol overhead for a moment.  There needs to be
authentication, error detection etc.  Also some management guff and
flags to say the following updates are all for IPv4 traffic with
IPv4 ETRs.  Also, I will ignore the likelihood that each full
database ITRD and QSD probably needs to get two separate streams of
data for robustness.

64kbps = 8k bytes = 666 updates a second = 20 billion a year.

Lets say we get to 100,000,000 multihomed end-user networks and each
has, on average, two micronets.  This is 200,000,000 micronets with
an average change rate of 2 a week.

The BGP system today, with ~240,000 prefixes, gives a router about 3
updates a second:

  http://bgpupdates.potaroo.net/instability/bgpupd.html

but quite a bit of this is convergence towards a final state.  I
think it is fair to say that the actual change of advertisements,
including those caused directly by outages, is half, a third or less
of this rate.

I don't see why the ITR-ETR proposals other than Ivip are based
entirely on the belief that it is impractical or undesirable to fan
out mapping changes to a few hundred thousand or a million ITRDs and
 Query Servers (QSDs).  Even if they all had to stream across the
globe like my MP3 packets travelled, I don't see it as so scary as
to be unthinkable.

Bandwidth, RAM and CPU power are cheap.

Distributing mapping in real time might involve several tree-like
structures, similar to multicast (maybe actual multicast, over a
tunneled overlay network), with each ITRD or QSD receiving (ideally)
two streams from different trees so the chance of packet loss is
minimised.  If a packet is not delivered, it can be requested from
one of several servers run by whoever created that packet (whoever
runs one or more Mapped Address Blocks).

By the time we get to this 100 million micronet stage, bandwidth,
RAM and CPU power will be cheaper still.

Planning and building an ITR-ETR scheme like this is non-trivial,
but it can be fast, efficient and robust - because it doesn't
involve routers chattering to their peers, spreading information
across the Net like rumours propagating through a crowd.

I don't see what is so scary about real-time control of the global
ITR system.

The advantages are obvious - simplicity for ITRs, simpler mapping
data, modular user control of mapping (multihoming service
restoration detection and logic as they choose, not all built into a
monolithic system) - and a whole new gutsy, efficient, approach to
mobility which doesn't require host changes and which works fine
with IPv4 and IPv6 alike.

I see a huge amount of activity with LISP based on the fervent
belief that we can't and never will be able to do real time push for
this growing stream of 12 byte update messages.

First there was LISP-CONS - a mess of new stuff to create a global
scale query server system.  It was clearly going to be slow, complex
and costly.  Now it is superseded.

LISP-NERD is a "push" system, but with each ITR asking for updates
from one of multiple relatively centralised servers.  At least there
is no packet delays or dropping.  But there isn't a concept of a
multicast-like replication system to fan the data out efficiently.
Nor is there the concept (as far as I recall) of caching ITRs and
local query servers.  LISP-NERD is to be left on the back-burner, in
favour of ALT.

eFIT-APT has even slower aspirations for distributing the data
globally, but has some smart (I think) arrangements for local
full-database Query Servers (Default Mappers) which are also ITRDs -
so most of the traffic is handled by caching ITRCs.  Now (according
to what I heard in the meeting), APT is to be merged with, or
adapted to, LISP.

TRRP relies on a global DNS-like query network.  I think this would
be simpler faster and more robust than CONS or ALT.  However it is
still too slow for realtime control and the simplifications and
modularity this enables.  I figure Bill Herrin will be busy for a
while with democrats.org .

LISP-ALT sounds nifty, but there are all sorts of delays in the
paths taken across the world in this global query server system too.
 One level of aggregation may be a router in the the USA, the next
in Japan, the next in the Netherlands.  The query packets traverse
the long tunnels between these routers, and have to make it all the
way back along the same tunnels.  There's no clear way of
authenticating the ETRs which are the authoritative query servers
for particular micronets, so the whole ALT overlay network needs to
be tied together carefully, manually, according to business
relationships.  That makes it expensive to administer and costly to
change.  Yet when the customer decides on a new ISP, they need to
change the IP address and the administrator of their ETRs.  So this
seems to defeat the purpose of ending provider lock-in.  (Ivip uses
username and password access, with a simple, lasting business
relationship to the organisation which runs whichever Mapped Address
Block the micronet is part of.  See RRG message 536.)

LISP is a complex mess of stuff and the IDs are now longer than Ivip's.

Ivip isn't finished, but it has a clear vision and is a lot better
explained than LISP.  There are no contradictory, incompatible,
variants - one cast aside after the other - as with LISP.

Since its inception in mid-June, Ivip has had a plan for
reachability from non-upgraded networks.  LISP finally adopted the
same system ("Anycast ITRs in the core" AKA "Proxy Tunnel Routers")
in late November.  APT doesn't have such a scheme and TRRP's
deployment plans uses the word "stick" and "carrot" frequently.

Ivip is the only ITR-ETR proposal to recognise that PMTUD problems
need to be solved.  I understand from the meeting today that the
LISP folks are of the view that there is no problem.  I would like
to see their reasons for this.  It would be nice if these problems
could be ignored, while still allowing for deep and flexible
placement of ITRs and ETRs.

My IPTM proposal looks pretty good to me for the current situation
of typically ~1500 byte MTU hosts and data links.  However, it has
problems when most hosts and most links are jumboframe compatible,
but we still need to assume ~1500 PMTUs between ITRs and ETRs.
Then, Fred Templin's critiques start to bite and his sprite-mtu
proposal starts to look better.  But sprite-mtu tends to assume that
most hosts will implement RFC 4821 - and I think this is unlikely to
occur any time soon, if ever.

I think Ivip or some other scheme with real-time, simple, mapping
data distribution is clearly the way forward - and the whole LISP
effort will be of little lasting value.  Alternatively, if LISP is
built, many people would soon start ripping it apart in order to
speed it up and achieve the simplicity, modularity and mobility
support that Ivip aspired to from the start.

  - 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: [email-masked]
Date: Sat, 8 Dec 2007 05:58:45 EST

In einer eMail vom 08.12.2007 09:35:06 Westeuropäische Normalzeit schreibt  
[email-masked]:

360 + 180 = 540 = 512 +28, i.e. a number that fits into 10 bits.
 
Hence 10 additional bits in the IPv4 header would enable scalable  
IPv4-forwarding even if the internet were thousand times bigger and  denser.
 
Further side effects: 
- 20 times faster next hop determination
 
- IPv4 address depletion becomes a non issue provided that the IRTF   
seriously cared about
identifier/location split rather than kept going to sell the "EID/RLOC"-2  
loose hops forwarding as a separation of identifier and location. Within the  
same city there may live several Mr.Smith ! Each of whom
may also roam BTW ! But each would have a different social security card  
number or passport number which is not affected in case of roaming ! The  
currently discussed solutions just prove that the longly theoretical  loc/id  
discussion a year ago was just done to pave the ground  for LISP and just stopped all 
of a sudden.
IPv4 addresses could be just geopatch locally unique (therefore no problem  
with IPv4 address depletion).
But agreed, roaming to some other geopatch must be enabled, too, i.e. must  
not wind up in a situation where there are several IP-phones with the same  
IPv4-address. Will say: identifier/location split is needed,
but is not provided and dealt with by the current LISP (agreed, I  haven't 
yet provided a solution to this problem (in case of roaming) either.But  why 
should I, if no one cared anyway).

Heiner

---

From: [email-masked]
Date: Sat, 8 Dec 2007 14:42:59 EST

In einer eMail vom 08.12.2007 12:00:49 Westeuropäische Normalzeit schreibt  
[email-masked]:

slight correction: 360 takes 9 bits, 180 takes 8 bits. I.e. 17 bits  
altogether.

Hence 17 additional bits in the IPv4 header would enable  scalable 
IPv4-forwarding even if the internet were thousand times bigger and  denser.
 
Further side effects: 

Heiner

---

From: Robin Whittle <[email-masked]>
Date: Sun, 09 Dec 2007 14:53:19 +1100

Heiner, I am not responding to your suggestions because I am only
interested in proposals which are incrementally deployable.  You
discuss modifying TCP/IP, introducing a completely new routing
architecture etc.

I will be away from email for a few days - back on Wednesday.

Maybe the wariness about the practicality of making a real-time
controlled ITR-ETR scheme as been due assuming that the problem is
inherently "hard" - or at least that the solution is likely to be
complex and involve hundreds of thousands of routers talking to each
other, organising themselves autonomously, like the BGP system we
are trying to save.

One way of conceptualising the BGP problem is "insufficient
aggregation".  Some ITR-ETR schemes which involve new structures
which optimise "aggregation" include LISP x.x, CONS, ALT and EMACS.

These all involve the "lots of routers all talking to each other in
a complex system, with messages or at least packets being passed
back and forth, peer to peer, with each one either deciding the next
hop for the packet, or doing something intelligent with the message
before deciding how to pass it on" - not unlike the BPG system.

LISP NERD and Ivip are ITR-ETR schemes where aggregation is not a
concern - they just get the mapping data out to the ITRs.  NERD and
Ivip are conceptually simple, deterministic systems with a
centralised control system, by which actual control of mapping is in
the hands of end-users.

If you took NERD, replaced the HTTP retrieval system with a fast
tree-structured multicast-like fan-out system, added Query Servers
(as in APT's Default Mappers) and then added caching Query Servers
and ITR functions in hosts, you would wind up with a fast push
system resembling Ivip.  Then there wouldn't be a need for complex
mapping data with multiple options for ETRs or for ITRs to test
connectivity to ETRs - the end-users can change their mapping
manually or with their chosen monitoring system.

No-one really knows how big the Net will grow.  So if you fear a
fast push system can't be done, it is easy to justify this by
picking a very large number out of the air, citing this as the
number of micronets multiplied by the rate of change that the system
must ultimately scale to - and multiplying this by the presumed size
of an update message to arrive at a scary number.

I think we want to make something which happily handles micronets at
least a thousand times more numerous than the current 240k BGP
prefixes.  But that factor of a thousand growth will take time to
occur.  Even doubling the growth rate (currently about a doubling of
BPG prefixes ever 4 years), it would take 20 years for a factor of
1000 growth to occur.

I don't think we should adopt something unambitious like LISP (slow,
with complex ITR functions and no support for mobility) just because
 of the assumption that a fast push system won't be workable 20
years in the future.

I think a good solution would be one we are confident will work for
15 years or so - till 2027 - as long as we feel confident it could
be extended then, or that its costs then would be less of a concern
with the technology of the day.

I could imagine perhaps a few tens of millions of businesses
(including folks like us at our home offices) wanting to multihome -
but that is an outside figure and maybe over 20 to 30 years the true
figure would be one or two million.

I think the only foreseeable cause of massive growth in micronets
would be if it became common for every cell-phone (as these things
are currently called - audio-video player, PC etc. in the future) to
have its own micronet.  That definitely requires a pay for mapping
change arrangement, and the mapping would only change when switching
between networks - such as to a WiFi connection - not between 3G
base-stations.

I don't think we should reject a technical solution because we can't
imagine how it would work at some distant time in the future when we
assume it will need to handle billions of micronets.  The growth may
never be that great, and by then, we will be able to adapt the
system and handle it with cheaper silicon and bandwidth.

We are not trying to make a new routing system which delivers
packets to ISPs and adapts to changes and outages in how ISPs
connect to each other.  The BGP system already does that fine.

We are creating a special class of address space and piping it
around the place with a global system of ITRs around the edge of the
BGP system - and also in the middle of it to catch packets sent from
networks without ITRs.

The BGP system is very "labour intensive" (RAM, CPU and memory):

  123,000 DFZ routers (probably more - RRG messages 255, 257 & 262).

  240,000 BGP advertised prefixes, doubling every 4 years (faster
              as fresh IPv4 space runs out).

  3 peers average? (My wild guess.)

= 88 billion, divide by 2

= 44 billion two-way conversations between DFZ routers, each
comparing notes with its peer about which has the shortest path for
each prefix.

No wonder no-one can simulate the BGP control plane - even if they
could simulate the traffic, outages etc.  I guess there is no other
IT system with this number of interdependent real-time
communications going on at once.  One crude way of thinking about
the global BGP control plane is 123k+ nodes simultaneously playing
240k games of Life (with the single-homed routers generating changes
as well) - with time delays due to long distance fibre delays and
CPU limits at times of high activity.

A fast (few seconds) ITR-ETR scheme will be big global project, but
not messy like BGP, with high-powered devices fighting their way
through hundreds of thousands of decisions and communications which
necessarily provide a very blinkered view of the situation.

Ivip and any other fast push ITR-ETR scheme will not involve a
pulsating, potentially chaotic, interconnected network like BGP's
control plane.  It can start nice and small, and still provide
immediate benefits to users in the form of address space which they
can multihome and take to any ETR-equipped ISP (or run their own ETR
in their PA space).  It can also provide highly valuable, efficient,
mobility.

A fast push ITR-ETR system such as Ivip will be highly deterministic
and won't require complex modelling in order to predict its behavior.

The mapping data needs to come from various sources and be combined
into multiple identical streams of packets, with each packet signed.
 I have some ideas about doing this and hope to complete them in a
few months.  I can see a relatively straightforward way (no PKI
etc.) that each "replicator" can check the validity of the packet it
gets from its upstream replicator.  Each replicator should get feeds
of packets from two upstream replicators, so it will only rarely not
get a copy of any particular packet in the mapping stream.  It fans
each packet in the stream out to some larger number of replicators
at the next level - say 10 or 20 of them, maybe more.

This looks challenging, but practical.  The average data rates will
not be high by current standards, until perhaps some time in the
future - say 15 years - when they will be higher, but still not
excessive by the standards of the day.

There will be peaks of activity, for instance due to some outages,
but it is not like the whole pattern of "best path" shifting in the
DFZ due to outages, with changes rippling across the global BGP
control plane.  There would just be a bunch of micronets being
switched to another ETR.  This would only occur due to a hard
outages in one or more ISP networks.  Currently, BGP rearranges its
best paths when there is a change in transit connectivity.

There is no reason to believe that a fast push ITR-ETR system would
generate its own noise, amplify perturbations, create "hunting"
patterns etc. as BGP's control plane sometimes does.  (IDR list
early June.)

There is some demanding FIB stuff to do in ITRs, and some fancy work
to enable QSD query servers to securely and robustly send updates to
their queriers about micronets the querier recently asked about and
for which new mapping has just been received.

A robust, secure, mapping data replication system is challenging,
but will probably require just some imagination and good
engineering, rather then heroics.  Replicators will most likely be
Linux/BSD boxes.  Likewise it will be possible to use cheap PC
hardware to build good query servers and many ITRDs and ITRCs -
sitting on a single Ethernet cable next to existing routers.  In the
longer term, I think Big Iron routers will do a lot of the ITR work,
but servers can do quite a lot of it in smaller ISPs who don't want
to upgrade their routers immediately.

ETRs in a fast push scheme can be pretty simple (assuming they don't
need to filter decapsulated packets according to source address),
except for whatever PMTUD work they need to do with the ITR.  Apart
from that, they don't need to communicate with the ITR.  It might be
best to have a standardised method of testing an ETR is reachable,
so any multihoming monitoring system can use that.  Reachability of
end-user networks can tested through the ETRs, but without requiring
any new ETR functionality or without standardising how ETRs send
packets to end-user devices.

The PMTUD stuff will be tricky - but this has nothing to do with the
fast mapping replication.  Every ITR-ETR scheme needs to cope with
this in order that ITRs and ETRs can be placed in all the locations
we need them to ensure short paths and good load spreading.

Maybe people have been spooked by the tangled web of BGP.  While it
is beyond our power to seamlessly untangle that, our ITR-ETR system
throws a ring around the DFZ and handles vastly more end-user
networks in a clean fashion, without further burdening the DFZ
control plane.

Just because this is a router-based fix for a messy router problem
doesn't mean that the solution needs to be as tricky and have such a
resemblance to cellular automata as the BGP system we are trying to
keep ticking.

  - Robin

---

From: Lixia Zhang <[email-masked]>
Date: Mon, 10 Dec 2007 10:22:13 -0800

On Dec 8, 2007, at 12:31 AM, Robin Whittle wrote:
> ......

Hi Robin,

I almost caught up with RRG mail by IETF week, but how falling behind  
again. But someone sent the above quote to me, so a quick  
clarification seems necessary:
- Please call APT just as APT
   (eFIT is a project name, not a design as LISP is).
- What you heard at the end of RRG meeting was a plan to write
   a LISP-APT internet-draft to show the APT mapping scheme
   interworking with LISP.

I appreciate your effort of comparing different approaches. I'm also  
doing the same and will write up my version soon.

Lixia

---

From: [email-masked]
Date: Wed, 12 Dec 2007 17:36:57 EST

In einer eMail vom 09.12.2007 04:56:28 Westeuropäische Normalzeit schreibt  
[email-masked]:

Robin, as I wrote before: My concept is incrementally deployable because  
whoever can afford to collect 400 000 entries can easily collect 1K-2K entries  
in addition whereby the "routing churn" for collecting this additional info  
tends to zero.

I  don't think we should adopt something unambitious like  LISP 
The IETF may develop LISP, but the IRTF should do research,  imho.   

Well, the algorithm I used in my pdf-file is almost 20 years old (it has  
been published by Kurt Mehlhorn in 1988) and I used it to compute the best next  
hop for any destination outside the current node's 1x1 square degreee 
geopatch.  It  will still be working in 15 years from now just like my own algorithms  
which go beyond Dijkstra and which are rather 50 years ahead of the current  
IETF's state-of-art. 
But I am afraid that the IETF community will never accept that  Dijkstra did 
not finish the job, and therefore it will stick to the stone-age  like 
TTL-mechanism forever. It will not accept that Dijkstra only provides the  absolute 
minimum of routing information and will ignore any progress on this  matter 
(e.g. by calling it hand waving ...)
 
As a matter of fact there could be much more ambitious goals:
Not only to abolish the scalability problem but also to provide "multiple  
topologies inter-domain", or:
Multicast to ten millions of receivers (without using any multicast address  
btw), 
 or real-time traffic balancing (of course  without MPLS) etc.  etc., all 
goals I experienced to be rated even VERY POOR.
 
Robin, while following the discussion, I got the impression that  your  
contributions haven't got the appropriate attention either. We both are  loosers, 
aren't we?
 
Bonjour tristesse,
 
Heiner