Subject: [RAM] Goal: Minimising Routing Entropy

From: RJ Atkinson <[email-masked]>
Date: Fri, 29 Dec 2006 09:42:20 -0500

I'd like to suggest that an architectural goal
for any new effort should be to reduce/minimise Routing
Entropy.  We know that doing this will address the near-term
engineering issues identified by tli and others.  It also
will fundamentally improve the scalability of the Internet
(including but not limited to the IPv6 Internet) over the
longer term.

	I'd really like to ensure that the global Internet
will be capable of scaling for at least my own lifetime
(even as I remain open to some new approach to networking
that would obviate the current packet network approaches :-).

	My belief is that if we move to a different ("better")
naming/routing/addressing architecture, that we really
can minimise the Routing Entropy (at least within the DFZ),
while retaining existing capabilities (e.g. site multi-homing)
and maybe also adding some new practical-to-use capabilities
(e.g. native mobility support, host multi-homing).

	I have some concrete ideas on ways that this might
be approached, in an incrementally-deployable way, but I'd like
to see whether there is agreement on terminology and goals first.

Ran
[email-masked]

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

---

From: John Schnizlein <[email-masked]>
Date: Fri, 29 Dec 2006 10:18:10 -0500

> (including but not limited to the IPv6 Internet) over the

One step toward agreement on terminology might be to replace 
"minimizing" here with "limiting growth of".  Strictly minimizing is 
likely to produce impractical results.  Are there analytic results that 
suggest practical bounds on routing entropy or its growth?

> can miniFrom [email-masked] Fri Dec 29 10:41:31 2006
From: John Schnizlein <[email-masked]>
Subject: Re: [RAM] Goal: Minimising Routing Entropy
Date: Fri, 29 Dec 2006 10:18:10 -0500
To: RJ Atkinson <[email-masked]>
Cc: [email-masked]

> (including but not limited to the IPv6 Internet) over the

One step toward agreement on terminology might be to replace 
"minimizing" here with "limiting growth of".  Strictly minimizing is 
likely to produce impractical results.  Are there analytic results that 
suggest practical bounds on routing entropy or its growth?

> while retaining existing capabilities (e.g. site multi-homing)

I fear even "site multi-homing" is actually ambiguous, despite that we 
all feel we know that that means.  Of course it means that there is 
more than one last hop from the DFZ to the site.  But what does it 
imply about how far the multiple paths to the site extend.  Shall we 
make hot-potato routing, which is often implicit, explicit, or can this 
assumption be relaxed to limit how far routing entropy extends to other 
realms?  One way to clarify this is to ask against what failures site 
multi-homing is to protect.

> to see whether there is agreement on terminology and goals first.

Please share your ideas while consensus forms on terminology and goals. 
  Sometimes the terminology "discussion" lasts longer than the problem.  
;-)

John

---

From: RJ Atkinson <[email-masked]>
Date: Fri, 29 Dec 2006 11:08:41 -0500

On  29 Dec 2006, at 10:18, John Schnizlein wrote:
> "minimizing" here with "limiting growth of".

I prefer my original formulation which was "reduce/minimise".
The "/" was deliberate as was my NOT saying "strictly minimise".

Thanks for the feedback.

> I fear even "site multi-homing" is actually ambiguous, despite that  
> we all feel we know that that means.  Of course it means that there  
> is more than one last hop from the DFZ to the site.  But what does  
> it imply about how far the multiple paths to the site extend.

"site multi-homing" doesn't imply anything.  I meant what I said,
nothing more and nothing less.

(A good general principle, at least with words I write, is that
trying to read between my words is a waste of the reader's energy.
I'm plain spoken.)

Ran

---

From: David Meyer <[email-masked]>
Date: Fri, 29 Dec 2006 08:32:03 -0800

> suggest practical bounds on routing entropy or its growth?

	To that point, are there more precise definitions (and
	measurements) of "Routing Entropy" around?

	--dmm

---

From: Marshall Eubanks <[email-masked]>
Date: Fri, 29 Dec 2006 12:17:30 -0500

Hello;

> 	measurements) of "Routing Entropy" around?

There is a routing entropy defined in US Patent 5596722

Packet routing system and method for achieving uniform link usage and  
minimizing link load;
US Patent Issued on January 21, 1997

This defines it as follows :

for any pair of nodes in network, find all paths between then, and  
the link usage probability (LUP) for
each link in such path, the LUP being F / TC,
where F is the load on the link, C is the link capacity, and T is the  
total network load. The
NRE (normalized routing entropy) is

- (1/T) * Sum (LUP log LUP), the sum being over all links.

This patent picks the routing that maximizes the NRE for the network.

Suppose that there are 2 links, of equal capacity, and 2 cases. In  
one, all traffic goes over link 1; in the other, both links share the  
traffic. (Let T = 1 for simplicity.)

Case 1 : LUP 1 = 1, LUP 2 = 0, NRE = 0
Care 2 : LUP 1 = 1/2, LUP 2 = 1/2, NRE = 0.693

so case 2 would be chosen. In other words, this technique equalizes  
the load over all links.

Note that this routing entropy is a "global" concept. In other words,  
if I have a choice to send
packets through link 1 or link 2, how do I determine which choice has  
a lower entropy ? I need to know the complete routing table for the  
entire network.

Wouldn't a useful design principle be to favor local concepts over  
global ones ?

Regards
Marshall

---

From: Tony Li <[email-masked]>
Date: Fri, 29 Dec 2006 10:28:12 -0800

> Wouldn't a useful design principle be to favor local concepts over  

Not if you're trying to address global issues.

Tony

---

From: JFCM <[email-masked]>
Date: Sat, 30 Dec 2006 04:38:01 +0100

>Not if you're trying to address global issues.

We are trying to address global issues from local diversity. This is 
the difference between (de)centralised and distributed (user centric) 
architectures. Question is to understand if a better decentralisation 
is possible or if we must switch to decentralisation, with all the 
resulting consequences for the architecture, the IETF and the 
Internet culture and governance. Not a small thing, but IMO the 
network development is such that decentralised (network centric) 
solutions have become too complex.
jfc

---

From: "Chris L. Morrow" <[email-masked]>
Date: Sat, 30 Dec 2006 03:36:32 +0000 (GMT)

> multi-homing is to protect.

it's probably also important to keep in mind that site-multihoming is
sometimes done for reasons not related to failure too... perhaps just
performance improvements (or percieved improvements).