Re: Draft on constraint-based routing

Bala Rajagopalan <braja@ccrl.nj.nec.com> Fri, 05 February 1999 16:03 UTC

Received: from ns.newbridge.com (ns.newbridge.com [192.75.23.67]) by ietf.org (8.8.5/8.8.7a) with ESMTP id LAA02693 for <qosr-archive@odin.ietf.org>; Fri, 5 Feb 1999 11:03:06 -0500 (EST)
Received: (from smtpd@localhost) by ns.newbridge.com (8.8.8/8.6.12) id LAA27730 for qosr-archive@odin.ietf.org; Fri, 5 Feb 1999 11:03:09 -0500 (EST)
Received: from kanata-gw1.newbridge.com(192.75.23.72), claiming to be "kanata-gw1.ca.newbridge.com" via SMTP by ns.newbridge.com, id smtpdWIAa21873; Fri Feb 5 11:01:08 1999
Received: from qmaster.ca.newbridge.com by kanata-mh1.ca.newbridge.com with ESMTP; Fri, 5 Feb 1999 10:59:37 -0500
Received: (from majordom@localhost) by qmaster.ca.newbridge.com. (8.8.8/8.8.8) id KAA13357 for qosr-outgoing; Fri, 5 Feb 1999 10:53:56 -0500 (EST)
Received: from kanata-mh1.ca.newbridge.com (kanata-mh1.ca.newbridge.com [138.120.118.18]) by qmaster.ca.newbridge.com. (8.8.8/8.8.8) with ESMTP id KAA13349 for <qosr@qmaster.ca.newbridge.com>; Fri, 5 Feb 1999 10:53:51 -0500 (EST)
Received: from kanata-gw.ca.newbridge.com by kanata-mh1.ca.newbridge.com; Fri, 5 Feb 1999 10:53:48 -0500
Received: from ns.newbridge.com ([192.75.23.67]) by kanata-gw.ca.newbridge.com via smtpd (for kanata-mh1.ca.newbridge.com [138.120.118.18]) with SMTP; 5 Feb 1999 15:53:48 UT
Received: (from smtpd@localhost) by ns.newbridge.com (8.8.8/8.6.12) id KAA23857 for qosr@newbridge.com; Fri, 5 Feb 1999 10:53:47 -0500 (EST)
Received: from hermes.ccrl.nj.nec.com(138.15.101.93) via SMTP by ns.newbridge.com, id smtpdAAAa23848; Fri Feb 5 10:53:41 1999
Received: from ccrl.nj.nec.com (braja-ppp.ccrl.nj.nec.com [138.15.98.41]) by hermes.ccrl.nj.nec.com (1.00/LJF980616) with ESMTP id KAA13650; Fri, 5 Feb 1999 10:44:15 -0500 (EST)
Message-Id: <36BB13ED.2B88E2DA@ccrl.nj.nec.com>
Date: Fri, 05 Feb 1999 10:53:17 -0500
From: Bala Rajagopalan <braja@ccrl.nj.nec.com>
X-Mailer: Mozilla 4.5 [en] (Win98; U)
X-Accept-Language: en
To: "Guo, Liang" <guol@ccs.neu.edu>
CC: Yao-Min Chen <ychen@fla.fujitsu.com>, qosr@newbridge.com
Subject: Re: Draft on constraint-based routing
References: <Pine.GSU.4.05.9902042033490.13428-100000@taboor.ccs.neu.edu>
X-MIME-Autoconverted: from 8bit to quoted-printable by hermes.ccrl.nj.nec.com id KAA13650
MIME-Version: 1.0
Content-Type: text/plain; charset=x-user-defined
Content-Transfer-Encoding: 8bit
X-MIME-Autoconverted: from Quoted-Printable to 8bit by qmaster.ca.newbridge.com. id KAA13350
Sender: qosr-owner@newbridge.com
Precedence: bulk

 

"Guo, Liang" wrote:

> On Thu, 4 Feb 1999, Yao-Min Chen wrote:
>
> > It seems reasonable to run in parallel best-effot and
> > QoS routing protocols.  The mechanism described
> > in the proposal is described as "overlay" because
> > QoS routing relies on link state info collected by the
> > best effort routing protocol.  The info is used to
> > compute the MST.  It seems that the proposal chose
> > MST instead of other types of spanning trees because
> > nodes can individually compute but the computations
> > will lead to exactly the same tree, which is important
> > to the correct operation of the proposal. Other than this,
> > is there any strong empirical or analytical reason
> > why MST should be used?  Another type of spanning tree
> > may be a min-hop one where the max number
> > of hops between any pair of nodes along the tree is
> > minimized.  Since the draft requires reliable
> > transmission between neighboring nodes at the QoS
> > routing layer, per-hop delay may be significant.
> > By reducing number of hops one can
> > reduce the latency when some routing update
> > needs to be propagated along the tree to all nodes.
> >
> > Rgds,
> > Yao-Min
> >
>
> A good reason could be the simplicity of the MST algorithm,
> it's impractical to use a steiner tree or "min-diameter" tree
> to transmit control messages since both these trees are hard
> to compute, heuristics to these trees are usually time-consuming.
>
> Guo, Liang
>  
>  

This is exactly the case. You could compute per-source trees,
but this requires larger forwarding tables. Please see the
reference on efficient link state QoS-based routing,
http://homepages.infoseek.com/~balarajagopalan/qoslinkstate.ps

Regards,

Bala
 

--

Bala Rajagopalan
NEC C&C Research Labs
4 Independence Way
Princeton, NJ 08540, USA
Ph: +1-609-951-2969
Email: braja@ccrl.nj.nec.com