Subject: AW: Unequal cost multi-path routing?

From: Schrodi Karl <[email-masked]>
Date: Tue, 5 Aug 2003 19:12:51 +0200

Hi Folks,

this is a subject, which may deserve a few more thoughts:

1. Obviously, whenever we leave the shortest (or least cost) path, the overall cost function (sum of(cost * used bandwidth)) will increase. This is what Rob shows (with the implicit assumption of equal distribution of packets to the unequal cost paths).

2. Thus, such kind of inefficiency still holds, if we weight the packet distribution inversely proportional to the respective cost of each path, as (according to my knowledge) EIGRP is capable of doing, or - a little bit more aggressive - if we would control the traffic distribution to the different paths by individual weights, calculated according to whatever rules. Such rules, for example, could take into account the knowledge about certain traffic patterns in the network (e.g. a traffic matrix) and aim at a better distribution of the traffic in the network and thus a more efficient (dito!) usage of network resources in case of some unbalance between available network path capacities and traffic demand.

3. Of course, loop prevention is an issue, but not a show stopper. OSPF-OMP as well as recent proposals (e.g. Schollmeier et al. at HPSR´2003 in Torino) can deal with that. Todays processing power calculates multiple routes in very short time.

4. A more severe problem may arise from packet sequence errors caused by per packet traffic distribution on different delay paths. Hash based per flow distribution may overcome this at least in network areas where the flow statistics, i.e. number of simultaneous flows, are large enough.

5. So, Acee is right, it complicates the basic SPF - but what (besides traffic distribution) could it be good for?
Multi-path routing has the inherent capability of having at least one alternative path available, if one path fails. Thus, connectivity can be preserved in a single node by an immediate and independent, local only reaction without any involvement of other nodes and without any delays due to network wide routing convergence. As soon as a failure is detected, the faulty path can be blocked locally and all traffic is sent to the remaining part of the multi-path group. Together with fast failure detection mechanisms as recently presented by the plp (Kompella) and bfd (Katz/Ward) drafts in the grow WG this could result in excellent failure reaction times.
I see several applications, where I would like that kind of behaviour:
web radio, video streaming, interactive video (net meeting), gaming, any kind of joint and interactive activities, - and, btw, I see no reason why I wouldn´t like it for simple web surfing.

6. So, - do we need it? Well, we may find out, that intra-AS rerouting is (or at least can be made) fast enough for such applications (where are we today?)- and if we arrive there and can proof it - why do anything else? Still, at that time our network may be faced with a new generation of more demanding applications ...
Finally, everything boils down to a cost/benefit estimate - is it worth while doing it? Who can judge?

Regards

Karl

-----Ursprungliche Nachricht-----
Von: ROB PATH [mailto:[email-masked]]
Gesendet: Sonntag, 3. August 2003 23:09
An: [email-masked]
Betreff: Re: Unequal cost multi-path routing?

--- Acee Lindem <[email-masked]> wrote:
> Ashish Zalani wrote:
> > This may sound like a dumb question, but:
> >
> > Why does OSPF not support unequal cost multi-path
> routing, like EIGRP?
> > Is it because unequal cost multi-path may lead to
> routing loops or other similar routing problems?
>
> Yes - it complicates the basic SPF and there has
> never been
> a strong requirement.

The default SPF based route calculation in the case of
OSPF does not take into account the traffic load
on any of the routes.

The SPF algorithm computes the optimal routes based
only on the cost metric and traffic load on the paths
are not considered.

So if load balancing is done over multiple unequal
cost paths then it leads to non-optimal routing.

E.g assume there are n paths P1, P2, ... Pn of unequal
costs say, C1, C2, C3, C4, .... ... Cn and total
lengths of packets transmitted over those paths are,
L1, L2, ... ... Ln.

Also let Cj is the cost to transmit a packet of unit
length over the path Pj.

Without loss of generality the unequal costs can be
ordered as :- Cn > Cn-1 > ... ... C3 > C2 > C1 > 0.

Then total cost of transmission using

a) Unequal cost multi-path load balancing is :-
        C1L1+C2L2+C3L3+ ... ... CnLn

b) No unequal cost multi-path load balancing (Optimal
Routing) is :- C1 * (L1+L2+L3+ ... ... +Ln).

Now :-
C1L1+C2L2+C3L3+ ... ... CnLn > C1L1+C1L2+C1L3+...+C1Ln
                             > C1 * (L1+L2+L3+ ...+Ln)

This shows that Unequal cost multi-path routing
leads to non-optimal routing.

Thanks,
     Rob.

> > -Ashish.
> --
> Acee

=====
Rob Path
E-Mail : [email-masked]

__________________________________
Do you Yahoo!?
Yahoo! SiteBuilder - Free, easy-to-use web site design software
http://sitebuilder.yahoo.com