Subject: [RAM] Consequences of needing route micro-management (long)

From: Elwyn Davies <[email-masked]>
Date: Mon, 15 Jan 2007 20:24:53 +0000

After my previous post on Traffic engineering and the network model 
(http://www1.ietf.org/mail-archive/web/ram/current/msg00102.html) I was 
thinking some more about the near-perfect in-order delivery constraint 
imposed by the transport layer.

I don't know whether TCP was designed that way to take advantage of the 
fact that the routing protocols delivered a single fully specified 
end-to-end route or whether this constraint was deliberately laid on 
routing at the beginning of IP time, but it is currently a constraint on 
routing and associated mechanisms: we had to take it into account when 
architecting DiffServ and in the design of ECMP. [Maybe someone who was 
in at the beginning remembers which was chicken and which was egg, but 
it no longer really matters.]

The result is that routers need to micro-manage the flow of every packet 
even in the core of the network.  They need to be supplied with a fully 
specified route from source to destination applicable to every packet 
that goes past.  Further packets belonging to the same 'micro-flow' 
(DiffServ terminology) must take the same complete path at least for a 
longish time period - between rerouting events.  In a meshy network, 
with multiple paths that are equivalently effective at delivering the 
packet, this may be very inefficient and require more complex hardware 
than is desirable.  It effectively introduces (more) state into the 
control plane of the network core contrary to Internet principles.

So far this is just a restatement of the analysis in the previous 
message, except for bringing out that routers appear to require a 
complete AS path for each prefix to do their business.

Aside on Information Explosion
==============================

Before going on I should mention that Joel Halpern pointed out to me 
that path vector protocols are not good at carrying alternative routes.  
Doing this leads very quickly to an information explosion.  One way of 
viewing what is happening in core routers today is a sort of partly 
controlled explosion where providers and multihomed sites are seeking to 
advertise a smallish number of alternative routes in order to try and 
make efficient use of the meshy network.

Consequences
============

I believe that the need for a fully specified end-to-end path has some 
important consequences that are limiting our options for solutions and 
are tied in to Brian Carpenter's observations on the possible need for 
contextual evaluation of id/loc mapping 
(http://www1.ietf.org/mail-archive/web/ram/current/msg00445.html).

One of the identified shortcomings of the existing inter-domain routing 
system is that information is propagated further than is desirable.  Put 
another way, a requirement identified for a next gen routing system is 
locality of information dissemination.  At the time when I was involved 
in writing this down (rrg routing requirements draft), this was an 
abstract requirement but I think it is now clear to me that the need for 
a very precisely specified path over the whole end-to-end route and 
known at every point on the path is not just a symptom, but actually the 
cause of the problem.

In essence, we have information leakage about the internal structure of 
the various parts of the network to all the other parts.  This leakage 
is driven by the pressure of needing to have a fully specified, unique 
path available everywhere.

In turn, the fact that globally comprehensible information is 
essentially obliged to be propagated over the whole network drives the 
need for essentially a single addressing realm.  This then results in 
the need for the hierarchical "addressing follows routing or vice versa" 
structure with a single hierarchy.

Of course the real network does not use a single addressing realm, and 
research work is looking at additional realms:
- NATs provide linkage to site realms
- DTN (Delay Tolerant Networking) uses (or at least can use) alternative 
addressing in DTN realms linked by DTN gateways
- Potentially the contextual id/loc mapping links to additional realms.
The need for a fully specified end-to-end path puts some very heavy 
constraints on the gateways between these realms and the routes that 
pass between them.  We know that switching a route from one NAT gateway 
to another is difficult, and I have had personal experience of trying to 
work out how to link between a DTN realm and the conventional Internet 
where there is more than one gateway.

Maps and the Single Hierarchy
=============================

NIMROD introduced maps as a conceptual model for Internet routing.  My 
understanding from when I looked at the original architecture was that 
maps would only export sufficient detail to allow a packet to reach the 
edge of a mapped area where the routing would get more precise 
directions taking it to a nested boundary, and so on.  This would 
inherently reduce the leakage of information.  The detailed working out 
of this strategy, if I read the runes correctly back when I first met 
NIMROD and now with a good deal of added hindsight, foundered exactly 
because the need for a fully specified end-to-end route was anathema to 
the mapping concept. (This is my own opinion and was certainly not 
written down in the annals).

PNNI attempted to implement the mapping concept, but my understanding - 
again I have never had anybody confirm this to me - is that it only 
really worked in a single hierarchical domain with a god-like entity 
sitting at the top to allow a single path to be created.

Does multi-path routing help? A hypothesis.
===========================================

It has been my belief (and this was not backed up by proof, and still 
isn't fully) that a number of the problems that the Internet is 
suffering are caused by the need to use single tree-like hierarchies for 
fundamental structures, such as addressing.  It appears to me now that 
it would be worth investigating whether relaxing the transport-imposed 
in-order delivery constraint would allow the Internet to use multi-path 
routing.  By this I mean that a packet may be routed along any 
reasonably effective path towards its destination without needing to 
consider what other members of its micro-flow did.  In principle this 
should match much more closely with the needs of multihoming and traffic 
engineering.  It might well allow the decoupling of DiffServ traffic 
classes from the constituent micro-flows and make QoS easier to deliver 
(pious hope??) which would be architecturally much sounder than the 
current way of working.

I believe that multi-path routing would also make it possible to 
properly realize the NIMROD map concept which seems to be an excellent 
way of keeping routing information as localised as possible.

Finally this would, I believe, make it possible to link addressing 
realms in a much freer way rather than the restrictive topologies we are 
forced to adopt today.

A research task...
==================
As Joel pointed out, the current inter-domain routing mechanisms are 
unlikely to help with multi-path routing because we would trade one form 
of information explosion for another one.  The current research 
strategies are AFAIK treading the same ground of finding better ways to 
deliver a fully specified unique path.  We know ways of finding 
multi-paths in the intra-domain environment where the routing protocols 
are all-informed (they are used for fast reroute mechanisms).  I think 
inter-domain multi-path and its relationship to maps oght to be a 
fruitful area for future research, and if my beliefs are correct, we can 
make some tweaks to existing transports to reduce their dependence on 
in-order delivery (TCP made some limited changes already if remember 
correctly) so that we are ready to implement.

Philosophically, it is also intriguing, because it would take the 
Internet closer to the true connectionless model whereas the need for 
fully specified paths is only a half-way house on the march away from 
connections.

Finally, an analogy
===================
In the previous message, I opined that attempting to disguise the meshy 
nature of the Internet infrastructure rather than embracing it was a 
dangerous strategy.  Those of you familiar with the wireless realm will 
probably be aware that for more or less the whole of radio technology's 
short lifetime multi-path reception was a bugbear to be suffered and 
concealed by putting aerials on high points and pumping out more power.  
Recent developments initially in military communications and cellular 
phones have stopped fighting the problem and started using multi-path as 
a way to get more bandwidth from less power and less spectrum.  Multiple 
directional receiving antennas and cunning adaptations of the spread 
spectrum correlation techniques have allowed receivers to work with low 
radiated powers in what would previously been considered impossibly 
hostile environments.  This has recently percolated into Wi-Fi (802.11n) 
and claims to be further increasing the effective range and/or bandwidth 
of the technology.

Clearly the analogy is not exact, but it reinforces the need to embrace 
the "multi-path opportunity" and hopefully get a boost in the process!

Apologies for the long and somewhat discursive posting.
Thoughts?

/Elwyn Davies

_______________________________________________
RAM mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/ram

---

From: JFCM <[email-masked]>
Date: Tue, 16 Jan 2007 13:54:27 +0100

At 21:24 15/01/2007, Elwyn Davies wrote:
>The result is that routers need to micro-manage the flow of every 
>packet even in the core of the network.  They need to be supplied 
>with a fully specified route from source to destination applicable 
>to every packet that goes past.  Further packets belonging to the 
>same 'micro-flow' (DiffServ terminology) must take the same complete 
>path at least for a longish time period - between rerouting 
>events.  In a meshy network, with multiple paths that are 
>equivalently effective at delivering the packet, this may be very 
>inefficient and require more complex hardware than is desirable.  It 
>effectively introduces (more) state into the control plane of the 
>network core contrary to Internet principles.
>

Dear Elwyn,
I subscribe to most of your concerns, often for the same reasons. 
However, I feel that the real problem is that you consider them still 
as engineering issues in the "mono-Internet", rather than using them 
to explore the possibilities of a "multi-Internet" architectural culture.

>Aside on Information Explosion

This depends on what you call a path and an alternative route. If the 
path vector implies a set of alternative route possibilities you do 
not have the problem anymore.

>  Doing this leads very quickly to an information explosion.  One 
> way of viewing what is happening in core routers today is a sort of 
> partly controlled explosion where providers and multihomed sites 
> are seeking to advertise a smallish number of alternative routes in 
> order to try and make efficient use of the meshy network.

subsidiarity is the key (see below). You still think meshed 
decentralised network here. Let try to think distributed one.

>Consequences
>============
>I believe that the need for a fully specified end-to-end path has 
>some important consequences that are limiting our options for 
>solutions and are tied in to Brian Carpenter's observations on the 
>possible need for contextual evaluation of id/loc mapping 

The key issue here IMHO is to avoid redundant constraining 
information. Meaning that id and loc information must be totally 
orthogonal and each of them global. If one is relative in any way, 
they are not orthogonal and will not scale (this does not preclude 
orthogonal contextualities)

>One of the identified shortcomings of the existing inter-domain 
>routing system is that information is propagated further than is 
>desirable.  Put another way, a requirement identified for a next gen 
>routing system is locality of information dissemination.  At the 
>time when I was involved in writing this down (rrg routing 
>requirements draft), this was an abstract requirement but I think it 
>is now clear to me that the need for a very precisely specified path 
>over the whole end-to-end route and known at every point on the path 
>is not just a symptom, but actually the cause of the problem.

Sure it is. But it is to be analysed why. Size, computation, usage, 
maintenance, fialbility, security, uncompleteness?

>In essence, we have information leakage about the internal structure 
>of the various parts of the network to all the other parts.  This 
>leakage is driven by the pressure of needing to have a fully 
>specified, unique path available everywhere.

Not only. It also comes from focusing on nodes rather than on links (see below)

>essentially obliged to be propagated over the whole network drives 
>the need for essentially a single addressing realm.  This then 
>results in the need for the hierarchical "addressing follows routing 
>or vice versa" structure with a single hierarchy.

Which by essence is a centralised approach, hence unable to support a 
distributed system for very long.

>Of course the real network does not use a single addressing realm, 
>and research work is looking at additional realms:
>- DTN (Delay Tolerant Networking) uses (or at least can use) 
>alternative addressing in DTN realms linked by DTN gateways
>pass between them.  We know that switching a route from one NAT 
>gateway to another is difficult, and I have had personal experience 
>of trying to work out how to link between a DTN realm and the 
>conventional Internet where there is more than one gateway.

Did you list somewhere the analysis of that difficulties?

>NIMROD introduced maps as a conceptual model for Internet routing.

Probably the reason why we do not use it today. IMHO the important 
introduction of NIMROD are the clusters. The error was to consider 
static nodes rather than focussing on "adjencies". In terms of 
adjencies there is no difference between adjencies to a node or to a 
cluster. RFC 1992.3.3  says: "Maps": "a map is a graph composed of 
nodes and adjencies. Propeties of the nodes are contained in 
attributes associated wih them. Adjencies have no attributes". 
Intervert "nodes" and "adjencies" in this section and you have your solution.

>My understanding from when I looked at the original architecture was 
>that maps would only export sufficient detail to allow a packet to 
>reach the edge of a mapped area where the routing would get more 
>precise directions taking it to a nested boundary, and so on.  This 
>would inherently reduce the leakage of information.  The detailed 
>working out of this strategy, if I read the runes correctly back 
>when I first met NIMROD and now with a good deal of added hindsight, 
>foundered exactly because the need for a fully specified end-to-end 
>route was anathema to the mapping concept. (This is my own opinion 
>and was certainly not written down in the annals).

The node-node end-to-end route can only be fully specified. To not 
fully specify it you must either consider clusters as nodes (what 
creates a really heady infromation flow you do not use), or document 
the end-to-end route in terms of adjencies. Clusters are then free to 
support these adjencies the way they want, using their internal 
adjencies the most efficiently.

Other problem with node maps are that different visions are quite 
complex, traffic load cannot be easily considered, there is no 
datachecking and alternative routes are complex to compute. Adjency 
maps have not that problems;

- I can document different visions of the same area, depending on 
different types of service or characteristics and report different 
adjencies (or lack of adjencies) depending on the user criteria.
- traffic load can easily be supported in giving a cost to each 
adjency and increasing that cost depending on the traffic load.
- each node reporting on its adjencies, each adjency is independently 
reported twice - helping checks.
- alternative route resolution can be simplified through the formula 
AC=AB+BC and taking considering the least effective attributes of AB 
and BC to deduce the possibilities of AC.

>PNNI attempted to implement the mapping concept, but my 
>understanding - again I have never had anybody confirm this to me - 
>is that it only really worked in a single hierarchical domain with a 
>god-like entity sitting at the top to allow a single path to be created.
>
>It has been my belief (and this was not backed up by proof, and 
>still isn't fully) that a number of the problems that the Internet 
>is suffering are caused by the need to use single tree-like 
>hierarchies for fundamental structures, such as addressing.  It 
>appears to me now that it would be worth investigating whether 
>relaxing the transport-imposed in-order delivery constraint would 
>allow the Internet to use multi-path routing.

No need to support it when it is not available. The cluster concept 
permits to address this simply and elegantly. Transparently to the 
external world.

>By this I mean that a packet may be routed along any reasonably 
>effective path towards its destination without needing to consider 
>what other members of its micro-flow did.

You can route packets as datagrams within a cluster if you find it 
more effective.

>In principle this should match much more closely with the needs of 
>multihoming and traffic engineering.  It might well allow the 
>decoupling of DiffServ traffic classes from the constituent 
>micro-flows and make QoS easier to deliver (pious hope??) which 
>would be architecturally much sounder than the current way of working.
>
>properly realize the NIMROD map concept which seems to be an 
>excellent way of keeping routing information as localised as possible.
>
>realms in a much freer way rather than the restrictive topologies we 
>are forced to adopt today.

Yes.
You also have to consider the set-up and error mechanisms and ISP 
rotation (route balancing) [missing in the NIMROD list of requirements]

>unlikely to help with multi-path routing because we would trade one 
>form of information explosion for another one.  The current research 
>strategies are AFAIK treading the same ground of finding better ways 
>to deliver a fully specified unique path.  We know ways of finding 
>multi-paths in the intra-domain environment where the routing 
>protocols are all-informed (they are used for fast reroute 
>mechanisms).  I think inter-domain multi-path and its relationship 
>to maps oght to be a fruitful area for future research, and if my 
>beliefs are correct, we can make some tweaks to existing transports 
>to reduce their dependence on in-order delivery (TCP made some 
>limited changes already if remember correctly) so that we are ready 
>to implement.

This can only be helped by orthogonal and global loc/id/extension 
addressing schemes.

Another issue is to be consistent with semantic internet. I will take 
an image: http.1.1 - it permits to locally extend the adressing with 
global (using an URN) or relative information and access virtual 
hosts on Apache. The same, a new addressing/routing scheme should 
extend routing to applications and meaning (whatever the way meaning 
is made addressable).

jfc

---

From: "Spencer Dawkins" <[email-masked]>
Date: Tue, 16 Jan 2007 15:45:28 -0600

Hi, Elwyn,

Just to follow up on the transport aspects of your thoughtful note 
(http://www1.ietf.org/mail-archive/web/ram/current/msg00453.html).

TCP did not start out caring about out-of-order delivery. As long as you got 
an ACK in less than Retransmission TimeOut (RTO) time, any order of delivery 
for either payload packets or ACKs was fine.

TCP became sensitive to out-of-order delivery with Fast Retransmit/Fast 
Recovery - instead of waiting for RTO, we added a hack that said "when we 
receive N-many ACKs that don't fill in a 'hole' in the sequence number 
space, it's likely that we lost a packet, so we should retransmit". The 
problem is that if you reorder packets by more than N-many, the sender will 
see enough duplicate ACKs to decide that a packet was lost, in less than RTO 
time - and TCPs Fast-Retransmit the apparently-missing packet, and then 
Fast-Recover by cutting the congestion window in half ("Fast" is not a 
misnomer here, it's less drastic than Slow-Starting from CWND=1).

N-many is 3 duplicate ACKs (4 ACKs total) in current-standard TCP. Mark 
Allman and friends have been working on dynamically adjusting N-many 
(Non-Congestion Robustness, NCR, recently published in 
http://www.icir.org/mallman/papers/rfc4653.txt), so there's nothing written 
in granite that we couldn't CHANGE the way TCP works (or SCTP either, for 
that matter). The idea, roughly, is to come up with a value of N-many that 
works over a specific path, instead of always using the same value as we do 
today. If you see new ACKs coming back after 6 duplicate ACKs, you assume 
that N-many should be increased from 3, for example.

So some of the work on "relaxing nearly in-order delivery constraints" has 
already happened. It may be that routers could stop worrying about 
reordering microflows for at least TCP/SCTP traffic, at some point in the 
future.

Thanks,

Spencer

---

From: Elwyn Davies <[email-masked]>
Date: Wed, 17 Jan 2007 01:04:07 +0000

Thanks for pointing this out.   I hadn't come across this work.  This 
would help the transition for TCP/SCTP assuming it is effective.
However, the multipath  problem as stated has other issues (cf RFC 2991) 
- potentially variable MTU, non-deterministic RTT and these would still 
be a problem for TCP I fear.  Actually I suspect the MTU issue is 
probably not that serious, but the non-deterministic RTT would certainly 
upset current TCP algorithms.

In the meantime, I have been checking up to see what, if anything, is 
going on in the research community on *inter-domain* multi-path routing.
The vast majority of work is either for intra-domain siuataions or 
ad-hoc radio networks.  There are 3 or 4 sightly interesting papers that 
I can find.

Section 5 of 
http://www.ecse.rpi.edu/Homepages/shivkuma/research/papers/bananas-jcn04.pdf 
has some thoughts on how you might be able to adapt BGP.

This paper is referred to in this TUCS report 
(http://www.tucs.fi/publications/insight.php?id=tLofman05a) which is a 
very interesting paper.  It discusses the RTT issue noted above and 
suggests some ways to approach a solution.

Jen Rexford and Wen Xu have an overlay story (MIRO - 
http://www.cs.princeton.edu/~jrex/papers/multipath06.pdf) but this is 
not really what we are looking for.

A multipath distance vector algorithm is described in 
http://www.soe.ucsc.edu/research/ccrg/publications/vutukury.info01.pdf

Regards,
Elwyn

Spencer Dawkins wrote:
> TCP did not start out caring about out-of-order delivery. As long as 
> you got an ACK in less than Retransmission TimeOut (RTO) time, any 
> order of delivery for either payload packets or ACKs was fine.
>
> TCP became sensitive to out-of-order delivery with Fast 
> Retransmit/Fast Recovery - instead of waiting for RTO, we added a hack 
> that said "when we receive N-many ACKs that don't fill in a 'hole' in 
> the sequence number space, it's likely that we lost a packet, so we 
> should retransmit". The problem is that if you reorder packets by more 
> than N-many, the sender will see enough duplicate ACKs to decide that 
> a packet was lost, in less than RTO time - and TCPs Fast-Retransmit 
> the apparently-missing packet, and then Fast-Recover by cutting the 
> congestion window in half ("Fast" is not a misnomer here, it's less 
> drastic than Slow-Starting from CWND=1).
>
> N-many is 3 duplicate ACKs (4 ACKs total) in current-standard TCP. 
> Mark Allman and friends have been working on dynamically adjusting 
> N-many (Non-Congestion Robustness, NCR, recently published in 
> http://www.icir.org/mallman/papers/rfc4653.txt), so there's nothing 
> written in granite that we couldn't CHANGE the way TCP works (or SCTP 
> either, for that matter). The idea, roughly, is to come up with a 
> value of N-many that works over a specific path, instead of always 
> using the same value as we do today. If you see new ACKs coming back 
> after 6 duplicate ACKs, you assume that N-many should be increased 
> from 3, for example.
>
> So some of the work on "relaxing nearly in-order delivery constraints" 
> has already happened. It may be that routers could stop worrying about 
> reordering microflows for at least TCP/SCTP traffic, at some point in 
> the future.
>
> Thanks,
>
> Spencer
>
>

---

From: Tony Li <[email-masked]>
Date: Tue, 16 Jan 2007 17:39:06 -0800

Hi Elwyn,

> packet even in the core of the network.

More precisely, the routers attempt to ensure that packets belonging  
to a single TCP connection always follow a single path.  The typical  
approach to doing this in the face of multiple paths is to hash the  
source and destination addresses into an index for the path table.

> They need to be supplied with a fully specified route from source  
> to destination applicable to every packet that goes past.

Full path information is a result of BGP's loop-prevention algorithm,  
and is not related to the need for near-perfect ordering.  I'll point  
out that the Internet has been run successfully (for some values of  
success ;-), on an entirely different distance-vector algorithm  
without full path information.

> In a meshy network, with multiple paths that are equivalently  
> effective at delivering the packet, this may be very inefficient  
> and require more complex hardware than is desirable.  It  

Nit: the hashing process exists in the forwarding/data plane.

> desirable.  Put another way, a requirement identified for a next  
> gen routing system is locality of information dissemination.

I don't think that this is a supportable, practical requirement.  As  
we can see from current practice, we know that if there is economic  
benefit to violating the locality of information dissemination, it  
will, in fact happen.  Now, the obvious alternative is to legislate  
additional dissemination out of existence, but that then creates a  
large deployment disincentive.

> Does multi-path routing help? A hypothesis.

Again, you're assuming facts not in evidence.  In-order delivery does  
not constrain us to single path routing.  While there are issues  
getting to true multi-path routing, TCP is *not* the problem.

Tony