How?

The implementation of spanning trees is obtained as follows. Each bridge portal has information that corresponds with that of its co-portal, and that initially spans a net tree consisting of just the edge represented by that bridge, and no bus trees. Upon each topology change on a bus, first an algorithm called net update is executed that adjusts the information of all bridge portals attached to the bus. It ensures the maintenance and (if necessary) construction of the net tree as well as the maintenance and (if necessary) desctruction of the bus trees. Whenever the information of one portal in the bridge is changed, this is done in synchronisation with the co-portal, so the information of two portals in one bridge is always consistent. Each adjusted bridge portal ensures that net update is executed on the co-portal's bus as well, which by repetition ensures that all bridges in the net are updated. Upon completion of net update on a bus, if the bus has no bus id and hence no bus tree exists for it in the net, an algorithm called bus enumeration is executed to obtain a new bus id and span the corresponding bus tree. The information employed by each bridge portal for the net tree and the bus trees is the following:

• prime: the unique identity of the prime portal (64 bits)
• alpha: a direction flag for the net tree (1 bit)
• mute: a flag indicating if the bridge can be used (1 bit)
• hops to prime: the distance to the root bus of the net tree (10 bits)
• bus id: the identity of the local bus (10 bits)
• route map: for each possible bus id, a four-valued direction variable (clean/valid/forward/dirty, 2046 bits in total)

The net update information is depicted in Figure 5 for the bridge that connects buses 2 and 4 in Figures 3 and 4.

Figure 5: Net update information per bridge portal

The net update task of collecting information of all bridge portals on the bus, determining which trees are to be destroyed, adjusted, spanned and left alone, and informing each bridge portal of the result, is performed by one designated portal, the coordinator.