Disk Configuration:
Figure 2.6 shows the comparison of the
minimum spanning overlay multicast tree with network multicast trees
on the disk configuration. Unless otherwise mentioned, the default
parameters used in these simulations are: each session includes 100
randomly selected nodes, the number of MSNs placed is 50, the edge
probability for the disk topology 
, and the disk radius is
one unit. In Figure 2.6(a) , the cost of the
trees is measured as the total distance of sending one packet to the
multicast session. Figure 2.6(a) shows the
cost trend of the three multicast trees with varied network
connectivity from a sparse graph to a complete graph; the 
-axis
shows the varied edge probability of the underlying random graph. All
plots are an average over 10 simulation runs.
| [Overlay Tree Cost] | |
 |
 |
| [Link Stress] | |
 |
 |
Both the cost of the approximate Steiner tree and the overlay tree decreases with the increase of network connectivity, indicating a better utilization of the network resources. The shortest path tree, on the other hand, sees an increase of its cost with a better connected network. This is because the shortest path tree always concentrates on minimizing the delay, and with the increase of available edges, each source is more likely to use a different path to reach each destination. In particular, if the underlying network assumes a complete graph, a shortest path tree is equivalent to the source using unicast to reach each destination. As most IP multicast protocols continue to use the shortest path tree approach and as the backbone network becomes more richly connected, the inefficiency of the shortest path tree becomes worse. Figure 2.6(a) shows that with the increase of session size, the cost of the shortest path trees also remains higher than the overlay tree.
Figure 2.6(b) shows the stress measurement on the network links with the tree. The network multicast trees always have a stress of one. We only measure the stress at the interface links of the MSNs, since these are the places where most duplicate packets occur. The average stress would be lower if we average the number of duplicate packets over all network links. The duplicate packets occur when an MSN sends the packet over the same interface where the packet is received from. On average, this occurs once per interface as the average stress is measured at around two. There are some links, however, that may sustain a higher stress, shown by the maximum stress. This is further exacerbated if the number of MSNs in the network is small.
The relative delay penalty in Figure 2.6(c) shows the tree performs slightly worse than the approximate Steiner tree. With a network of multiple paths, there is no single tree that can minimize the delay between all pairs of members. The shortest path trees achieve an RDP of one since it utilizes one tree for each source. The RDP for the tree has an average of 2 to 2.5 and a 90 percentile of 3.5 to 4.5. We observe that the large RDP values are more likely to occur between clients having small network delay; this makes the denominator smaller, yet the absolute maximum end-to-end delay along the tree is bounded at 6 unit of distance.
Figure 2.6(d) shows the session delay penalty with varied network connectivities and session sizes. The curves for the overlay spanning tree and for the approximate Steiner tree are quite close to each other, with the overlay tree outperforming slightly the approximate Steiner tree. The case when there are 20 MSNs in the overlay network outperforms the case of having 50 MSNs, since the latter has more MSNs involved in a session, leading to longer tree paths. However, having more available MSNs in the network generally gives better performance as indicated by the cost and the stress metrics.
Metro Configuration: Figure 2.7 shows a similar set of tree comparisons performed on the metro configuration. Here, we show the transmission cost as the relative cost ratio over the approximate Steiner tree cost.
The metro configuration differs from the disk configuration in that it attempts to model the network with a two-level hierarchy: the top level is the backbone network connecting 50 largest cities in US and the bottom level consists of regional routers directly connecting to the backbone. This implies that the tree is likely to align with the backbone network, with each tree branch corresponding to one or more backbone links. This topology alignment should help the tree to reduce the stress and the RDP. Figure 2.7(c) and 2.7(d) shows that, as compared with the disk configuration, both measurements reduce significantly.
| [Relative tree cost with varied session size.] |
 |
| [Relative tree cost with varied number of MSNs.] |
 |
| [Link Stress] |
 |
| [Relative Delay Penalty] |
 |
| [Session Delay Penalty] |
 |
Figure 2.7(a) shows the relative tree cost with varied session size for 20 and 50 MSNs, as well as the relative cost of the shortest path tree. While the tree with 50 MSNs again outperforms the shortest path tree, it shows that both trees have an increased cost with the growth of the session size, while the shortest path tree cost holds constant. Dissecting the tree composition, we find that the increase of cost can be mainly attributed to the point-to-point connection cost from clients to the MSNs. Recall that in the metro configuration, the paths from regional routers to the backbone consist of links that form a star and links that form an MST. While the shortest path tree and the Steiner tree are able to aggregate the paths from regional routers to the backbone by using the MST links, the tree always selects the star links. With larger session size, this part of the connection cost dominates the total tree cost. Figure 2.7(b) shows this effect further. With larger numbers of MSNs, MSNs are placed closer to clients, reducing the overall tree cost. On the other hand, with smaller numbers of MSNs, although the tree cost among the MSNs reduces, the overall cost becomes higher.
We observe in Figure 2.7(c), that the maximum stress holds constant at 2 with 50 MSN. This is clearly a benefit of aligning the overlay topology with the network topology so that the backbone links are better utilized with fewer duplicated packets. Figure 2.7(d) shows that this alignment also helps the tree to achieve better RDP performance than the approximate Steiner tree.
Figure 2.7(e) shows the session delay penalty for the minimum spanning overlay tree with 20 and 50 MSNs, compared with the approximate Steiner tree. All curves are quite close to each other. The crossover of the two curves for the 20 and 50 MSNs is because a session node always selects the closest MSN as its proxy, so more MSNs are involved in a session if there are more of them available in the network. For smaller sessions, the larger number of MSNs results in longer tree paths; while for larger sessions, this is compensated by the smaller distances from the clients to the MSNs.
We conclude from these simulation results that it is possible to build trees to utilize network resources efficiently without straining the end-to-end delay performance. Especially when the placement of the MSNs aligns well with the underlying network topology, the tree not only incurs very little overhead on network links, it also produces better delay performance than the optimal network level multicast tree.
