Re: Draft on constraint-based routing

[Bala Rajagopalan <[e-mail]>]

 

"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: [phone]
Email: [e-mail]