Subject: Re: [Bier] BIER and deterministic ECMP

From: Albert Tian <[email-masked]>
Date: Tue, 18 Nov 2014 05:52:55 +0000

Hi Ross,

Very good point. Yes IMHO this needs to be addressed, otherwise the links
leading to lower numbered BFERs will more likely be chosen in ECMP and
cause unbalanced traffic. This maybe just as bad as the instability you
have identified.

Agreed multiple BIFT solution should work.

Thanks,
Albert

On 11/17/14, 3:10 PM, "Ross Callon" <[email-masked]> wrote:

>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
>
>
>
>_______________________________________________
>BIER mailing list
>[email-masked]
>https://www.ietf.org/mailman/listinfo/bier

---

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

What if rather than process in the order of the bits the processing is inverted and instead the links are processed in some lexicographic ordering as the outer loop. That would lead to a determinism of the paths used irrespective of entry or departure of lower order bits. Slower I guess for a sparsely populated bit set.

Peter 

-----Original Message-----
From: BIER [mailto:[email-masked]] On Behalf Of Albert Tian
Sent: Tuesday, November 18, 2014 12:53 AM
To: Ross Callon; [email-masked]
Subject: Re: [Bier] BIER and deterministic ECMP

Hi Ross,

Very good point. Yes IMHO this needs to be addressed, otherwise the links leading to lower numbered BFERs will more likely be chosen in ECMP and cause unbalanced traffic. This maybe just as bad as the instability you have identified.

Thanks,
Albert

On 11/17/14, 3:10 PM, "Ross Callon" <[email-masked]> wrote:

>noticed the last sentence of section 6.7:
>
>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)
>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.
> 
>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: Ross Callon <[email-masked]>
Date: Tue, 18 Nov 2014 19:14:22 +0000

I think that the problem with this is that the number of links out of the router can be quite large. You may be forwarding any one packet on only a small number of links, and want to be able to keep all of your outgoing links full. Therefore you want to have a reasonable limit on the number of lookups required for each packet. A good feature of the algorithm currently described in the BIER architecture is that the number of lookups that you need to do is bounded by the number of copies of the packet that you will actually be sending out. 

Also, in the example that Tony and I were discussing, regardless of what lookup algorithm is used, you still have the issue of whether you want the packets to Y to all go out the same way (deterministic forwarding), or do you want the path to fluctuate based on what other destinations are receiving the packet (minimize the number of packets transmitted). 

Ross

-----Original Message-----
From: BIER [mailto:[email-masked]] On Behalf Of AshwoodsmithPeter
Sent: Tuesday, November 18, 2014 2:00 PM
To: [email-masked]
Subject: Re: [Bier] BIER and deterministic ECMP

Peter 

-----Original Message-----
From: BIER [mailto:[email-masked]] On Behalf Of Albert Tian
Sent: Tuesday, November 18, 2014 12:53 AM
To: Ross Callon; [email-masked]
Subject: Re: [Bier] BIER and deterministic ECMP

Hi Ross,

Thanks,
Albert

---

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

Yes, there are all kind of 'dialects' of the algorithm that can be imagined, e.g. 
matching the 'entry with most bits' that AND's with the packet mask first instead
of 'right side' walking  yields quite interesting properties when deployed network-wide.

If one can hire a hardware guy smart and cheap 
enough, one could build a TCAM variation just for that ;-) 

--- tony  

> From: BIER [mailto:[email-masked]] On Behalf Of Ross Callon
> Sent: Tuesday, November 18, 2014 11:14 AM
> To: AshwoodsmithPeter
> Cc: Ross Callon; [email-masked]
> I think that the problem with this is that the number of links out of the
> router can be quite large. You may be forwarding any one packet on only a
> small number of links, and want to be able to keep all of your outgoing links
> full. Therefore you want to have a reasonable limit on the number of
> lookups required for each packet. A good feature of the algorithm currently
> described in the BIER architecture is that the number of lookups that you
> need to do is bounded by the number of copies of the packet that you will
> actually be sending out.
> 
> Also, in the example that Tony and I were discussing, regardless of what
> lookup algorithm is used, you still have the issue of whether you want the
> packets to Y to all go out the same way (deterministic forwarding), or do you
> want the path to fluctuate based on what other destinations are receiving
> the packet (minimize the number of packets transmitted).
>

---

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

Hi Peter,

If I understood it correctly, your proposal is still non-deterministic.
Consider fluctuation of group members behind the lower ordered links, they
could still impact the paths of the members behind the higher ordered
links, assuming you are going to have F-BM on for each link.

Statistically speaking, lower ordered links would also draw more traffic
due to the F-BM operations.

Thanks,
Albert

On 11/18/14, 11:00 AM, "AshwoodsmithPeter" <[email-masked]>
wrote:

>What if rather than process in the order of the bits the processing is
>inverted and instead the links are processed in some lexicographic
>ordering as the outer loop. That would lead to a determinism of the paths
>used irrespective of entry or departure of lower order bits. Slower I
>guess for a sparsely populated bit set.
>
>Peter 
>

---

From: Xuxiaohu <[email-masked]>
Date: Wed, 26 Nov 2014 10:05:50 +0000

For deterministic path selection for each egress, how about disabling the ECMP for BIER forwarding?

Best regards,
Xiaohu

> Sent: Wednesday, November 19, 2014 4:15 AM
> To: AshwoodsmithPeter; [email-masked]
> could still impact the paths of the members behind the higher ordered links,
> assuming you are going to have F-BM on for each link.
> 
> Statistically speaking, lower ordered links would also draw more traffic due to
> the F-BM operations.
> 
> Thanks,
> Albert
> 
> 
> 
> 
> 
> >ordering as the outer loop. That would lead to a determinism of the
> >paths used irrespective of entry or departure of lower order bits.
> >Slower I guess for a sparsely populated bit set.
> >
> >Peter
> >
> >Very good point. Yes IMHO this needs to be addressed, otherwise the
> >links leading to lower numbered BFERs will more likely be chosen in
> >ECMP and cause unbalanced traffic. This maybe just as bad as the
> >instability you have identified.
> >
> >>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.
> >>
> >>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)