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

From: AshwoodsmithPeter <[email-masked]>
Date: Mon, 17 Nov 2014 22:11:45 +0000

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

---

From: Antoni Przygienda <[email-masked]>
Date: Tue, 18 Nov 2014 01:38:00 +0000

inline

From: BIER [mailto:[email-masked]] On Behalf Of AshwoodsmithPeter
Sent: Monday, November 17, 2014 2:12 PM
To: [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.
[Tony said]   Well, no, MT per se cannot do that but you can restrict the topology using MT to be a Steiner itself so it's a 'poor man's' solution to the problem ;-)

[Tony said] yes.

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.
[Tony said] It was never claimed that we compute for each subset of nodes, a practical solution would be to compute a single steiner (MST) spanning _all_ the BFRs with assigned ids (=BFERs & BFIRs) which should be still significantly better than SPFs in terms of replication (but that's all very hand-wavy, pathological cases are easily constructed).

[Tony said] yes

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.
[Tony said] yes, but you don't provide any solution, just raise a problem. Computing all the Steiners for all sets (which is combinatorial) is not feasible obviously.

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.
[Tony said]  A fully statically optimized solution based on known set of inputs is always very hard to beat by a dynamic scheme.  We can come up with all kind of smarts such as measuring volumes between sets of BFIRs/BFERs and optimizing trees for those & pretty soon we'll have 32 'modes' of running BIER.

I think a single Steiner heuristics spanning all BFI/ERs would be interesting enough. Optionally, we could stick a bit of BFRs saying "I'm preferred replicator = core" of a tree and so on. Tons of work has been done in this respect.

n  tony

---

From: Eric C Rosen <[email-masked]>
Date: Tue, 18 Nov 2014 10:43:52 -0500

> 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.

This is an interesting point, though I don't think it's stated quite 
right.  A phrase like "BIER routing has no knowledge of the set of nodes 
being connected when it computes the path" is a bit imprecise, given the 
three-layer BIER architecture.

In at least some applications, the multicast flow layer will know the 
exact set of nodes that needs to be connected for a given multicast 
flow.  It is then possible for the multicast flow layer to cause a 
Steiner tree for that flow to be created.  That tree can then be 
identified (e.g., assigned an MT-id), and used as an underlay by the 
BIER forwarding procedures.   So I don't think there is anything in the 
BIER architecture that prevents the use of Steiner trees.

However ...

If you're going to build a tree that contains all and only the nodes 
through which a given flow needs to travel, you can use conventional 
multicast forwarding to send packets of that flow on that tree.  BIER 
doesn't provide any added value in that case.

Alternatively, as Tony suggests, one could build a Steiner tree 
connecting all the BFIRs/BFERs in the domain.  Then one could send all 
flows along that tree, using BIER to prevent a given flow from going 
through nodes that it does not need to visit.  I suspect Peter would say 
though that there is no point in doing this, as the path taken by any 
given flow would not be optimized (i.e., the path traveled by a given 
flow is not the path along the Steiner tree for that flow, and hence 
does not have the properties one might hope for).

So I think the architecture does support the use case that Tony 
describes; whether that use case is actually useful or not is something 
we don't have to decide.

---

From: Antoni Przygienda <[email-masked]>
Date: Tue, 18 Nov 2014 16:32:48 +0000

> If you're going to build a tree that contains all and only the nodes through
> which a given flow needs to travel, you can use conventional multicast
> forwarding to send packets of that flow on that tree.  BIER doesn't provide
> any added value in that case.
> 
> Alternatively, as Tony suggests, one could build a Steiner tree connecting all
> the BFIRs/BFERs in the domain.  Then one could send all flows along that
> tree, using BIER to prevent a given flow from going through nodes that it
> does not need to visit.  I suspect Peter would say though that there is no
> point in doing this, as the path taken by any given flow would not be
> optimized (i.e., the path traveled by a given flow is not the path along the
> Steiner tree for that flow, and hence does not have the properties one might
> hope for).
> 
> So I think the architecture does support the use case that Tony describes;
> whether that use case is actually useful or not is something we don't have to
> decide.
> 

[Tony said]  I would roughly agree with Eric here, if you have flows stable and fat enough that you need to optimize distribution tree for specific receiver/sender set and compute dedicated Steiner for it, amount of state in the network becomes a secondary problem. Computer #1000s of Steiners for large number of such combinations is not something I saw done since even the heuristics on Steiner are quite beefy.

I would still say that BIER provides an advantage due to minimizing the state/protocols needed in the network if number of such trees is small [one tree per sub-domain]. If number of such trees is large, it does not (since one would need a BIER sub-domain per receiver/sender set optimized by a Steiner).  Maybe BIER architecture can be easily extended to maintain set of computed trees in a sub-domain and choose the 'right' Steiner tree to deliver traffic by setting it in the packet header but then one could argue, bitmask is not needed, the tree encodes the receivers/senders and compression of such a thing quickly leads to (S,G) state in the core again is my intuition [or alternately each tree represents a sub-domain but BIER is not made to scale to huge numbers of sub-domains] 

--- tony

---

From: AshwoodsmithPeter <[email-masked]>
Date: Tue, 18 Nov 2014 18:51:54 +0000

[PETER] Clarifying a problem actually. I raised it in the meeting but was told it was not a problem because MT solved it so I am simply clarifying that it is still a problem and MT does not solve it. It may not be a critical problem but it is none the less true that you could end up with some pretty horrible trees interconnecting small numbers of nodes.

The only solution that I know of along the lines of BIER would be to encode the links to traverse as a bit set in a header as that would allow an arbitrary tree per set of destinations. However for that you'd need to have a bigger header. The alternatives to that are of course the hash based headers that use Bloom filters but they produce false positives and unwanted traffic .. also possible loops.

Unfortunately its trade-offs all the way down. I think BIER is actually a pretty good set of trade-offs but let's be clear on what it can and cannot accomplish.

Peter

---

From: Antoni Przygienda <[email-masked]>
Date: Tue, 18 Nov 2014 18:56:31 +0000

Peter, yes, agreed, very fair summary.   I didn't say in the meeting that MT solves it, must have been someone else ;-)
I only clarified with you that  I considered the 'Steiner problem' a single Steiner for _all_ I/E on the tree so we talked about different assumptions.

I actually _can_ imagine a variation of BIER encaps that would list the links but I think that would be truly  'multicast segment routing' rather than BIER
as was proposed in Hawaii ;-)

tony

From: AshwoodsmithPeter [mailto:[email-masked]]
Sent: Tuesday, November 18, 2014 10:52 AM
To: Antoni Przygienda; [email-masked]
Subject: RE: Follow up on my comments from Honolulu concerning T.E/ Steiner Tree optimization with Bier

Peter

---

From: AshwoodsmithPeter <[email-masked]>
Date: Tue, 18 Nov 2014 19:27:22 +0000

Inline [PETER]

> -----Original Message-----
> From: Eric C Rosen [mailto:[email-masked]]
> Sent: Tuesday, November 18, 2014 10:44 AM
> To: AshwoodsmithPeter; [email-masked]
> Cc: [email-masked]
> Subject: Re: [Bier] Follow up on my comments from Honolulu concerning
> T.E/ Steiner Tree optimization with Bier
> 
> node
> > for a given MT it is impossible for those computations to produce a
> > proper  Steiner tree for each subset of nodes.
> 
> right.  A phrase like "BIER routing has no knowledge of the set of
> nodes being connected when it computes the path" is a bit imprecise,
> given the three-layer BIER architecture.

[PETER] Ok, more precisely the computation of the next hops has no knowledge of all the intended member subsets.

> BIER architecture that prevents the use of Steiner trees.

[PETER] True but that's a bit of a stretch. In that case the MT computed tree creates state for the use of only that set of destinations and is essentially removing the stateless (per set of destinations) nature of Bier.

> doesn't provide any added value in that case.

[PETER] Correct, my point above. Works but is not really saving you any state and on the contrary the 10% of so B/W tax is still present so it not only does not buy you anything it costs you something that other trees don't.

> through nodes that it does not need to visit.  I suspect Peter would
> say though that there is no point in doing this, as the path taken by
> any given flow would not be optimized (i.e., the path traveled by a
> given flow is not the path along the Steiner tree for that flow, and
> hence does not have the properties one might hope for).

[PETER] Would say there is likely a very good point in doing that much of the time but there will be some horrific degenerate cases with small numbers of members out in the edges of that tree that will surprise people. 

Very likely what you want is to have a number of MT's where each MT has a different 'center of gravity' for want of a better word. When dealing with small sets of members that are localized, the centers of gravity of that set of members is used to pick an appropriate MT, thus minimizing the horrific kinds of routing that would otherwise result. So a bit of offline analysis will be required to pick a good MT and MT's will need to be distributed properly to avoid bad degenerate routing.

> describes; whether that use case is actually useful or not is something

[PETER] With sufficient MT's even Bier will fly ;) 

Sorry could not resist :)

Again I'm not knocking the idea, think it's pretty cool and hope it goes ahead, just trying to be clear on what it can and cannot do and how it would have to be used to get results similar to say P2MP central control.

Peter

---

From: Antoni Przygienda <[email-masked]>
Date: Tue, 18 Nov 2014 19:31:20 +0000

> 
> Very likely what you want is to have a number of MT's where each MT has a
> different 'center of gravity' for want of a better word. When dealing with
> small sets of members that are localized, the centers of gravity of that set of
> members is used to pick an appropriate MT, thus minimizing the horrific
> kinds of routing that would otherwise result. So a bit of offline analysis will
> be required to pick a good MT and MT's will need to be distributed properly
> to avoid bad degenerate routing.
> 

[Tony said]  RFC2201 ;-)

---

From: AshwoodsmithPeter <[email-masked]>
Date: Tue, 18 Nov 2014 19:47:06 +0000

Exactly, if you assign a bit per adjacency and the header encodes the set of adjacencies to cross then you get segment routing for multicast. I.e. source routed multicast and can create any tree you want ingress. Pretty cool if you can afford the overhead. I suppose you could compress with the header encoding logical adjacencies into some set of abstract topologies .. probably give you similar behavior to the MT solution.

Peter

From: Antoni Przygienda [mailto:[email-masked]]
Sent: Tuesday, November 18, 2014 1:57 PM
To: AshwoodsmithPeter; [email-masked]
Subject: RE: Follow up on my comments from Honolulu concerning T.E/ Steiner Tree optimization with Bier

tony

From: AshwoodsmithPeter [mailto:[email-masked]]
Sent: Tuesday, November 18, 2014 10:52 AM
To: Antoni Przygienda; [email-masked]<mailto:[email-masked]>
Subject: RE: Follow up on my comments from Honolulu concerning T.E/ Steiner Tree optimization with Bier

Peter

---

From: AshwoodsmithPeter <[email-masked]>
Date: Tue, 18 Nov 2014 19:54:26 +0000

Ok, but not one per sender as in 2201, that would be too many MT's, you'd likely want one per 'corner' of the network so that if a cluster of members are near that corner they use the tree rooted at that 'corner'.

Cheers,

Peter

> Sent: Tuesday, November 18, 2014 2:31 PM
> To: AshwoodsmithPeter; Eric C Rosen; [email-masked]
> Subject: RE: [Bier] Follow up on my comments from Honolulu concerning
> > Very likely what you want is to have a number of MT's where each MT
> > has a different 'center of gravity' for want of a better word. When
> > dealing with small sets of members that are localized, the centers of
> > gravity of that set of members is used to pick an appropriate MT,
> thus
> > minimizing the horrific kinds of routing that would otherwise result.
> > So a bit of offline analysis will be required to pick a good MT and
> > MT's will need to be distributed properly to avoid bad degenerate
> routing.
> >
> 
> [Tony said]  RFC2201 ;-)

---

From: Eric C Rosen <[email-masked]>
Date: Tue, 18 Nov 2014 15:04:42 -0500

Peter,

I don't think we have a substantive disagreement, but I do like to
distinguish between "X is prohibited by the BIER architecture" and
"combining X with BIER is a bad idea".  Perhaps I'm being overly 
pedantic ...

> the computation of the next hops has no knowledge of all the intended
> member subsets.

The BIER architecture does not say what facts may or may not be known
when the next hops are computed.  (That's the pedantic point ;-))

> the MT computed tree creates state for the use of only that set of
> destinations and is essentially removing the stateless (per set of
> destinations) nature of Bier.

This is the substantive point.  The more pre-computed trees you have,
and the more specific each one is to a particular set of egress nodes,
the less benefit you get from BIER.  I think that's absolutely correct.
If you wanted a Steiner tree for each flow, you would not use BIER.

> just trying to be clear on what it can and cannot do and how it would
> have to be used to get results similar to say P2MP central control.

Certainly global optimization of the multicast flow patterns is unlikely 
to be achieved with a solution that is both (a) distributed and (b) low 
in multicast-specific state.

Eric