In order to obtain and maintain the bus id numbering, and use this information
for routing messages between different buses, yet another abstraction is
necessary: viewing the net as a graph with bridges for edges, and buses for
nodes and having spanning trees in this graph structure.
The graph abstraction is illustrated in Figure 3.
Here, the numbers in the nodes of the graph are the bus ids.
Figure 3:
The bus-based graph abstraction
The first notion of spanning tree is the bus tree. For each bus id in
use, the corresponding bus tree enables the routing of messages destined for
that bus id. An example bus tree is shown in
Figure 4(a). Here, the dashed edge indicates a
bridge that is not part of the spanning tree.
Clearly, there must be as many bus trees as the number of bus ids in use.
The second notion of spanning tree is the net tree. There is one net
tree that gives each bus a route to the root bus where the prime portal
resides. The prime portal is in charge of assigning bus ids and its
unique 64-bit id is the identity of the net.
An example net tree is shown in Figure 4(b).
Here, the white arrow head indicates the prime portal.
Figure 4:
Examples of spanning trees for the net in
Figure 3
[A net tree]
