Subject: [rbridge] RBridge Spanning Tree Comments

From: Venkata.Naidu at Marconi.com (Naidu, Venkata)
Date: Fri May 7 15:44:31 2004

-> 2.2  Spanning Tree
->
->   There will be cases when RBridges will need to send packets to all
->   links.  These cases include:

  The above sentence needs correction.
   
  If spanning tree is used to flood packets, every router will get 
  the packet. Not every link. If we want every link to see a packet
  then the only way is to flood, as in link-state IGPs.

->   o  layer 2 multicast or broadcast packets
->
->   o  distributed RBridge layer 3 address location query
->
->   In this case the packets must be sent through a spanning tree.
->   However, there is no need to implement a separate spanning tree
->   protocol in addition to the link state protocol. Instead, the link
->   state information can be used to create a single spanning tree
->   throughout the campus. This is done by choosing the RBridge with
->   lowest ID, and calculating the Dijkstra tree with that RBridge as
->   Root.

  There is a problem with this. 

  1. Dijkstra tree? Dijkstra single source shortest path tree?!
     Yes. SPT is an spanning tree (not necessarily an MST). 
     Why SPF ? Why not Spanning Tree algorithms (like prim etc).

  2. Here, we choose not to build a dynamic distributed spanning 
     tree. Rather an offline spanning tree using distributed
     link-state information. 

     Distributed algorithms perspective, having a *unique* spanning 
     tree reduces lot of communication complexity. Building a 
     off-line spanning tree doesn't solve f-failure termination. 
     When a process or link fails, then every node has to 
     re-compute the spanning tree. This will lead to loops when 
     some routers get link-state information ahead of other routers.

  3. The above paragraph says "This is done by choosing the RBridge 
     with lowest ID....". How do we choose the lowest ID. When the 
     routers come up, routers run some leader-election algorithm or
     use link-state information ? If routers use link-state
     information, when should routers start build the spanning tree ?
  
  I am wondering, why can't IGPs use the spanning tree to reduce
  communication complexity ?

Venkata.