Subject: [Bier] BIER and deterministic ECMP

From: Ross Callon <[email-masked]>
Date: Mon, 17 Nov 2014 23:10:30 +0000

Reading the BIER architecture (draft-wijnands-bier-architecture-01) I noticed
the last sentence of section 6.7:

   Note however that by the rules of Section 6.5, any packet destined
   for both BFER-D and BFER-F will be sent via BFR-C.

Thinking about this more: It is clear that where ECMP paths exist, which path
is taken to reach any particular destination will depend upon which other
destinations the same packet goes to. In particular, which lower numbered
bits are set in the BitString can change the choice among ECMP paths. This
could have the effect that as a lower numbered destination intermittently
joins and leaves a multicast group, the path to a higher numbered
destination could switch back and forth between different ECMP paths.
 
This could be fixed if we used multiple BIFT tables, such that each BIFT table
has only one path to each destination, but the multiple possible ECMP paths
to any particular destination are spread across the multiple tables. When a
BIER-encapsulated packet arrives to be forwarded, the BFR would use the BIER 
Entropy field (or a hash thereon, if fewer than 256 next hops are supported) 
to determine which BIFT to use, and then the normal BIER forwarding algorithm 
(the same as described in draft-wijnands-bier-architecture-01) would be used 
with whichever BIFT table was selected. This would of course increase the 
amount of memory that would be needed to store BIFT tables, but my quick "back 
of the envelope" calculation suggests that the amount of memory to store BIFT 
tables still should not be a problem if there aren't too many BIFT tables (I 
did my "back of the envelope" with max 16 tables). The forwarding algorithm and 
packet headers stay unchanged. This also has the feature that if this approach 
is consistently implemented across a service provider, then where a problem has 
been reported on a particular flow of packets to a particular receiver, we can 
traceroute with the same entropy value to that particular receiver and know 
that we will be using the same path as the normal data packets to that receiver.
 
I would be happy to write up appropriate text to add to draft-wijnands-bier-
architecture-01 (presumably for a -02 version) if the authors would like, or
alternately could write up a separate Internet Draft to further describe the
issue and the solution.

Thanks, Ross

---

From: Antoni Przygienda <[email-masked]>
Date: Tue, 18 Nov 2014 17:41:50 +0000

> destination could switch back and forth between different ECMP paths.

 [Tony said]  Ross, I thought more about it & it's not a simple ECMP problem in my eyes. What you suggest [entry per destination] can lead to quite detrimental effects under normal operation since we're operating here in the domain of fan-out counts as well (I'll explain) [unless I misunderstood your email]. 

Observe the attached figure  (I hope it survives the mailing list send for others).   When you're sending to a XYZ you clearly prefer the upper-most path due 1 replication count (latest possible fan-out).  Tables split per destination can lead to twice the bandwidth network consumption on the network if A ends up replicating along ACX, ADY, AEZ (immediate fan-out).  When X falls off the receiver list, AD is the prefered 'axis' and if only Z is receiver, you have 3 ECMP paths all consuming same amount of bandwidth. 

My point:  what is the property we try to preserve ?  Given the example, I would argue first that changing receiver list you may want as preference to change the paths through the network since the optimal replication points may shift to save bandwidth. Using ECMP too early can lead to unnecessary duplications.   As long the receiver list is the same however, something like entropy label should control the ECMP.  

I am not saying the problem does not exist, I am just introducing another important axis that can deteriorate when looking @ optimizations in another axis. 

--- tony

---

From: Ross Callon <[email-masked]>
Date: Tue, 18 Nov 2014 18:45:42 +0000

Yes, there is a tradeoff.

Suppose in your figure that you remove the link from C to Z. In that case, a packet destined for Y and Z would be more efficiently sent to D (since only one copy needs to be sent by A to D, and D can replicate to Y and Z. However, a packet destined for X and Y would more efficiently be sent to C, since A would send only one copy (to C) and C can replicate to X and Y.

Suppose that X and Z kept joining and leaving the group, so that some packets go only to X and Y, and some packets go only to Y and Z. In this case there is a legitimate question: What behavior do we want? If we minimize traffic on the links out of A then the packets to X and Y would go via C, and the packets to Y and Z would go via D. This would mean that the packets to Y keep fluctuating between paths (or at least fluctuate as quickly as X and Z join and leave the group). If we wanted steady performance and predictability for the traffic to Y, we might prefer to have the traffic to Y always take the same path at the cost of sometimes having to send two packets out of node A. 

Ross

PS: Your figure showed up and printed fine, at least in my email system.
 
-----Original Message-----
From: Antoni Przygienda [mailto:[email-masked]] 
Sent: Tuesday, November 18, 2014 12:42 PM
To: Ross Callon; [email-masked]
Cc: IJsbrand Wijnands ([email-masked]); Albert Tian; Eric Rosen; Greg Shepherd (shep) ([email-masked])
Subject: RE: BIER and deterministic ECMP

--- tony

---

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

Yepp, we're in sync.  I think it's pretty much a vendor optimization we're talking here but merits a draft explaining the trade-off space.  The only property I see as uniformly desirable is that while the receiver set and label stack is stable, OAM must be deterministic as to which of the ECMP paths it's following (i.e. predictable ECMP, probably based on entropy label if I'm not mistaken but I stand corrected otherwise).

--- tony 

> From: Ross Callon [mailto:[email-masked]]
> Sent: Tuesday, November 18, 2014 10:46 AM
> To: Antoni Przygienda; [email-masked]
> Cc: IJsbrand Wijnands ([email-masked]); Albert Tian; Eric Rosen; Greg
> Shepherd (shep) ([email-masked]); Ross Callon
> Suppose in your figure that you remove the link from C to Z. In that case, a
> packet destined for Y and Z would be more efficiently sent to D (since only
> one copy needs to be sent by A to D, and D can replicate to Y and Z.
> However, a packet destined for X and Y would more efficiently be sent to C,
> since A would send only one copy (to C) and C can replicate to X and Y.
> 
> Suppose that X and Z kept joining and leaving the group, so that some
> packets go only to X and Y, and some packets go only to Y and Z. In this case
> there is a legitimate question: What behavior do we want? If we minimize
> traffic on the links out of A then the packets to X and Y would go via C, and
> the packets to Y and Z would go via D. This would mean that the packets to Y
> keep fluctuating between paths (or at least fluctuate as quickly as X and Z
> join and leave the group). If we wanted steady performance and
> predictability for the traffic to Y, we might prefer to have the traffic to Y
> always take the same path at the cost of sometimes having to send two
> packets out of node A.
> 
> Ross
>

---

From: Eric C Rosen <[email-masked]>
Date: Tue, 18 Nov 2014 14:38:17 -0500

On 11/18/2014 1:50 PM, Antoni Przygienda wrote:
> The only property I see as uniformly desirable is that while the
> receiver set and label stack is stable, OAM must be deterministic as
> to which of the ECMP paths it's following

I don't agree.  I think the path for a flow to travel from A to B needs
to be independent of whether or not there are other receivers.

Suppose in your diagram that traffic from A to Y along takes the path
A-->D-->Y.  But traffic from A to (X+Y) goes from A to C and then from C
to X and from C to Y.

Now suppose that the link from C to Y is flaky.

This means that whenever someone at site X joins the flow, the folks at
site Y will see a degradation in service.  When the folks at site X
stop receiving the flow, the folks at site Y will see an improvement in
service.

This seems like something that would be very hard to troubleshoot, and
could really annoy the folks at site Y.

> I think it's pretty much a vendor optimization we're talking here

I think it's more a question of what sort of behavior the operators want.

---

From: Albert Tian <[email-masked]>
Date: Tue, 18 Nov 2014 20:02:25 +0000

Nice picture Tony :-)

Given the limitation of BIER, some heuristics such as defer the split (as
you alluded to) can reduce the total cost of the tree. For example, any
BFR can try to locally minimize the number of copies (or the sum of the
oif costs to be precise).

However in some examples, like the one in the attached topology, the
global tree optimization is hard to achieve in the current BIER.

In this example, A is trying to send to X Y Z. The best tree is to group Y
with X (compared to grouping Y with Z). A needs to make that decision,
however from its BIFT, A would only know Y has ECMP next hops B and C, and
they are equally good from A¹s point of view.

On the topic of what behavior do we want: please note that receiver may
see out of order packets due to path shifts, which are undesirable.
Trouble shooting non-deterministic paths could also be a headache.

Thanks,
Albert

On 11/18/14, 9:41 AM, "Antoni Przygienda" <[email-masked]>
wrote:

> [Tony said]  Ross, I thought more about it & it's not a simple ECMP
>problem in my eyes. What you suggest [entry per destination] can lead to
>quite detrimental effects under normal operation since we're operating
>here in the domain of fan-out counts as well (I'll explain) [unless I
>misunderstood your email].
>
>Observe the attached figure  (I hope it survives the mailing list send
>for others).   When you're sending to a XYZ you clearly prefer the
>upper-most path due 1 replication count (latest possible fan-out).
>Tables split per destination can lead to twice the bandwidth network
>consumption on the network if A ends up replicating along ACX, ADY, AEZ
>(immediate fan-out).  When X falls off the receiver list, AD is the
>prefered 'axis' and if only Z is receiver, you have 3 ECMP paths all
>consuming same amount of bandwidth.
>
>My point:  what is the property we try to preserve ?  Given the example,
>I would argue first that changing receiver list you may want as
>preference to change the paths through the network since the optimal
>replication points may shift to save bandwidth. Using ECMP too early can
>lead to unnecessary duplications.   As long the receiver list is the same
>however, something like entropy label should control the ECMP.
>
>I am not saying the problem does not exist, I am just introducing another
>important axis that can deteriorate when looking @ optimizations in
>another axis. 
>
>--- tony 
>
>