Subject: Re: Draft on constraint-based routing

From: Yao-Min Chen <[email-masked]>
Date: Thu, 04 Feb 1999 17:09:15 -0800

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  

Bala Rajagopalan wrote:
> 
> The following ID was recently posted to internet-drafts.
> Your comments are welcome.
> 
> Regards,
> 
> Bala
> 
> -------------
> Title           : An Overlay Model for Constraint-Based Routing
>         Author(s)       : B. Rajagopalan, Q. Ma
>         Filename        : draft-rajagopalan-CR-overlay-00.txt
>         Pages           : 18
>         Date            : 25-Jan-99
> 
>        This draft considers an overlay model for constraint-based intra-
> 
>        domain routing and describes a mechanism for efficient update
>        propagation that can be used as the basis for this model. As a
>        specific example, the incorporation of a constraint-based routing
> 
>        overlay on the OSPF protocol is discussed.
> 
> A URL for this Internet-Draft is:
> http://www.ietf.org/internet-drafts/draft-rajagopalan-CR-overlay-00.txt
> 
> --
> 
> Bala Rajagopalan
> NEC USA, C&C Research Labs
> 4 Independence Way
> Princeton, NJ 08540
> U.S.A
> 
> Ph: +1-609-951-2969
> Fax: +1-609-951-2499
> Email: [email-masked]

-- 
Yao-Min Chen, Fujitsu Labs of America, [email-masked]  
595 Lawrence Expressway, Sunnyvale, CA 94086-3922, USA
Ph: +1 408 530 4513  Fax: +1 408 530 4518

---

From: "Guo, Liang" <[email-masked]>
Date: Thu, 4 Feb 1999 20:41:18 -0500 (EST)

> needs to be propagated along the tree to all nodes.  

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

[email-masked]                   College of Computer Science,
(617)373-7920 (O)                  161 Cullinane Hall,
(617)859-8879 (H)                  Northeastern University.
http://www.ccs.neu.edu/home/guol   MA 02115.

---

From: Bala Rajagopalan <[email-masked]>
Date: Fri, 05 Feb 1999 10:53:17 -0500

> to compute, heuristics to these trees are usually time-consuming.

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