Subject: Re: [Bier] Follow up on my comments from Honolulu concerning T.E/ Steiner Tree optimization with Bier

From: Albert Tian <[email-masked]>
Date: Mon, 17 Nov 2014 22:44:42 +0000

Hi Peter,

One main factor of the BIER encoding efficiency comes from the fact that distributed BIFTs are already calculated on all the BFRs, and the BIFTs can be shared in the tree building exercise regardless of the group membership.

So in the Steiner tree case, if the BIFT tables for each tree can not be shared, then BIER may not be the right technology for the use case.

However, using SPF, BIER can deliver the shortest path from each ingress to each egress, which is a different optimization goal than Steiner’s. Also playing with the MT and BIFTs, BIER can support many tree types that can approximate the Steiner.

Thanks,
Albert

From: AshwoodsmithPeter <[email-masked]<mailto:[email-masked]>>
Date: Monday, November 17, 2014 at 2:11 PM
To: "[email-masked]<mailto:[email-masked]>" <[email-masked]<mailto:[email-masked]>>
Subject: [Bier] Follow up on my comments from Honolulu concerning T.E/ Steiner Tree optimization with Bier

I made a couple of points in Honolulu about the inability of Bier to  produce optimum bandwidth trees (i.e Steiner) which I did not properly explain. In particular the counter claim that Multi Topology (MT) could solve the problem is not correct.

A Steiner tree is essentially a minimum cost tree that spans a subset of nodes in a graph. It will use the minimum bandwidth to deliver copies to all members. If you add or remove a member the tree usually will be totally different (i.e. more expensive, often considerably so).

The computation of the Steiner tree is very hard, i.e. non-polynomial, in part because:
- The Steiner tree for some set of nodes is NOT a subset of any tree computed based on a superset of those nodes (i.e. not a subset of another Steiner tree, or SPF tree, or spanning tree etc.).

To compute the Steiner tree you therefore need the exact set of nodes to be connected as input. Since Bier routing has no knowledge of the set of nodes being connected when it computes the path to a given node for a given MT it is impossible for those computations to produce a proper Steiner tree for each subset of nodes.

The best that can be done with MT is to produce a small number of Steiner trees that span the entire set of edge nodes but since the subsets of those trees are not Steiner we don’t get Steiner trees between the actual members of the bitset (which is usually a subset of what was used to compute the full tree).

Now does this matter? Well  if you are trying to squeeze the last drop of bandwidth out of the network you need a real Steiner tree for the set of nodes being connected.  Mind you if you are so concerned about bandwidth the 10% or more overhead of the Bier header is likely also a concern.

Now I’m not suggesting Bier is a bad idea, simply trying make sure people understand it cannot do what a statically configured P2MP tree could do in terms of bandwidth optimization.  For other applications, such as PIM replacement it seems like a very interesting solution.

Anyway a very interesting proposal and as far as creating a WG, I think that if SPRING got a WG Bier deserves one.

Cheers,

Peter