Subject: [Bier] comments on draft-zhang-bier-designed-routing-00.txt

From: Antoni Przygienda <[email-masked]>
Date: Sat, 31 Oct 2015 11:49:24 +0000

Flew over the draft and I think (I did not have time to follow the extensive exapmles given by the authors) that the draft as written will always duplicate given that a representation of hierarchical bitmasks given by authors is not a datastructure that can represent a DAG without running @ least a specialized O (N log(N)) computation over the bitmasks. Simple Banyan example works easily (source is @ level 1 in my enumeration)

Trying to describe something that delivers to the set of [ Source, Transit1, Transit2, Sink2 ] cannot be done with 3 levels of bitmasks without replicating to Sink2 _UNLESS_ Source does not only compute level 2 bitmasks but also level 3, i.e. computes that Transit2 and Transit1 receive _different_ level3 bitmasks. The according computation is e.g. a Dijkstra that tie-breaks ECMPs (ONlogN is very dirty complexity measure for Dijkstra but sufficient for purpose of this discussion).

I don't consider running Dijkstra's for the bitmasks (observe that set of receivers will modify the necessary computation) and modifying the whole hierarchy per node the packet is replicated to something that is justifiable in complexity for what it achieves, especially given the size of the headers we're talking. I would consider the BIER-TE suggestion significantly better here.

thanks

--- tony

"Your work is to discover your work and then with all your heart to give yourself to it." --- Buddha