| Re: [ptp-dev] Need help on the construction of SDM routing tree |
| Jie, This code is used to construct a binomial tree. The tree is "lopsided" in that there are more elements on the left side than the right side of each branch. This ensures that at a particular node in the tree messages sent to each branch in sequence will reach the leaves simultaneously. See http://en.wikipedia.org/wiki/Binomial_heap for a diagram. The tree is constructed in sdm_route_init, which in turn calls find_descendants. A couple of things to note. First is that the root of the computed tree is always node 0. SInce the actual node id of the root can vary, we first normalize the tree so that the root id is 0. Second, each node actually computes a number of trees: - "descendants" contains all the nodes in the tree from the current location to the leaves - "children" contains only the immediate children of the current location - "child_descendants" is a hash that contains the descendants of every child of the current location At any given position in the tree, it is easy to compute the children by starting with the current node and setting successively higher bits until the highest numbered node in the tree has been reached. For example, suppose there are 9 nodes in the tree. Node 0 (0000) will have children 1 (0001), 2 (0010), 4 (0100), and 8 (1000). Node 1 (0001) will have children 3 (0011) and 5 (0101). Node 2 (0010) will have child 6 (0110) and node 3 (0011) will have child 7 (0111). Nodes 4, 5, 6, 7, and 8 don't have any children because if you set the next highest bit the result will be greater than the number of nodes. For example setting the next highest bit on node 4 (0100) gives 10 (1100). The full tree is computed recursively. Hope this helps, Greg On Nov 4, 2008, at 3:56 PM, JiangJie wrote: |