AW: Unequal cost multi-path routing?

Schrodi Karl <karl.schrodi@SIEMENS.COM> Tue, 05 August 2003 17:13 UTC

Received: from cherry.ease.lsoft.com (cherry.ease.lsoft.com [209.119.0.109]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id NAA19467 for <ospf-archive@LISTS.IETF.ORG>; Tue, 5 Aug 2003 13:13:31 -0400 (EDT)
Received: from PEAR.EASE.LSOFT.COM (209.119.0.19) by cherry.ease.lsoft.com (LSMTP for Digital Unix v1.1b) with SMTP id <17.00ABFAEB@cherry.ease.lsoft.com>; Tue, 5 Aug 2003 13:13:34 -0400
Received: from PEACH.EASE.LSOFT.COM by PEACH.EASE.LSOFT.COM (LISTSERV-TCP/IP release 1.8e) with spool id 50415728 for OSPF@PEACH.EASE.LSOFT.COM; Tue, 5 Aug 2003 13:13:32 -0400
Received: from 192.35.17.28 by WALNUT.EASE.LSOFT.COM (SMTPL release 1.0i) with TCP; Tue, 5 Aug 2003 13:13:32 -0400
Received: from mail2.siemens.de (mail2.siemens.de [139.25.208.11]) by goliath.siemens.de (8.11.7/8.11.7) with ESMTP id h75HDVb29062 for <OSPF@PEACH.EASE.LSOFT.COM>; Tue, 5 Aug 2003 19:13:31 +0200 (MEST)
Received: from moody.mchh.siemens.de (moody.mchh.siemens.de [139.21.205.85]) by mail2.siemens.de (8.11.7/8.11.7) with ESMTP id h75HDUm06786 for <OSPF@PEACH.EASE.LSOFT.COM>; Tue, 5 Aug 2003 19:13:30 +0200 (MEST)
Received: from mchh248e.mchh.siemens.de (mchh248e.mchh.siemens.de [139.21.200.58]) by moody.mchh.siemens.de (8.9.3/8.9.1) with ESMTP id TAA02351 for <OSPF@PEACH.EASE.LSOFT.COM>; Tue, 5 Aug 2003 19:13:30 +0200 (MET DST)
Received: by mchh248e.mchh.siemens.de with Internet Mail Service (5.5.2653.19) id <PLMJG0TQ>; Tue, 5 Aug 2003 19:12:52 +0200
MIME-Version: 1.0
X-Mailer: Internet Mail Service (5.5.2653.19)
Content-Type: text/plain; charset="utf-8"
Content-Transfer-Encoding: quoted-printable
Message-ID: <47D260E84215734F81779E8A50BE9B37656125@mchh2a4e.mchh.siemens.de>
Date: Tue, 05 Aug 2003 19:12:51 +0200
Reply-To: Mailing List <OSPF@PEACH.EASE.LSOFT.COM>
Sender: Mailing List <OSPF@PEACH.EASE.LSOFT.COM>
From: Schrodi Karl <karl.schrodi@SIEMENS.COM>
Subject: AW: Unequal cost multi-path routing?
To: OSPF@PEACH.EASE.LSOFT.COM
Precedence: list
Content-Transfer-Encoding: quoted-printable

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:rob_path@YAHOO.COM]
Gesendet: Sonntag, 3. August 2003 23:09
An: OSPF@PEACH.EASE.LSOFT.COM
Betreff: Re: Unequal cost multi-path routing?


--- Acee Lindem <acee@REDBACK.COM> 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 : rob_path@yahoo.com

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