Next: Results Up: IEEE FireWire and Net Previous: Graph view vs. implementation

#### Net update algorithm

Net update (re)starts executing on a bus whenever the local bus topology has changed (removal or insertion of bridge portals), or when one of the bridge portal's information was adjusted because of net update executing on an adjacent bus. It consists of the following consecutive operations, presented in the graph terminology for sake of clarity and compactness. We assume extra variables per bridge for the net identity, for the distance to the root bus in the net tree, and a destroy flag for each possible bus id.
1. loop elimination: if the information of the bridge portals indicates a loop in the topology, then one edge must be taken out of the net tree and bus trees. One of the following applies:
• loop criterion 1 For one net tree identity, there are two outgoing edges on the bus. The one with the largest distance to the root is selected.
• loop criterion 2 For one net tree identity, there is one outgoing edge and one edge with the prime portal on the bus. The outgoing edge is selected.
• action The bridge with the selected edge is undirected in both the net tree and all bus trees.
2. spanning & destroying trees: each bridge attached to the bus is adjusted so that a selected net tree is spanned, and each bus tree is either destroyed (if in conflict), spanned (if no conflict but not yet complete) or left unchanged (otherwise).
• net tree criterion The maximal net tree identity for which an outgoing edge or the prime portal is present on the bus is selected. If there is no outgoing edge or prime portal, the unique id of one of the bridge portals is selected at random.
• distance criterion If the selected tree identity is of an outgoing edge, the distance of that bridge is selected and incremented with 1. Otherwise, the selected distance is 0.
• local bus tree criterion One of the bus trees for which there are only incoming edges and undirected edges is selected at random.
• bus tree criterion Each bus tree for which one of the following holds must be destroyed: (1) there are two outgoing edges, (2) there is no outgoing edge and it is not the selected local bus tree, or (3) the destroy flag is true for that bus id at a bridge portal. Each bus tree that is not destroyed for which there is an outgoing edge must be extended.
• net tree action For each bridge portal, the selected net tree identity is copied. If this means a change, then the bridge is directed in the net tree towards the bus. If the bridge is incoming or undirected, it copies the selected distance.
• bus tree action For each bridge portal, and each bus tree, if it must be destroyed, the bridge is undirected in the bus tree and the corresponding destroy flag is set to true. If it must be extended and the bridge is undirected in the bus tree, then the bridge is directed in the bus tree towards the bus. If it is the selected local bus tree, then the bridge is directed in the bus tree towards the bus.
• spreading net update For each bridge portal that has been adjusted and that is directed in the net tree, net update is started on the neighbour bus.
3. completion For each bridge not adjacent to a bus where net update is busy, all destroy flags are set to false.

Next: Results Up: IEEE FireWire and Net Previous: Graph view vs. implementation