Constructing Height-Balanced Multicast Acknowledgment Trees with the Token Repository Service Part 2

Seite

Textversion

the case of low background load. Since it takes longer for a node to join the ACK tree if the timeout interval is increased, it takes also longer before the joining node itself is able to accept successor nodes. Therefore, other joining nodes must possibly search in a larger scope to connect to the ACK tree. As it can be seen in the chart, ERA results in a high message overhead. With increased background load, the message overhead seems to decrease but this is only caused by our simulation scenario. The use of ERA leads to a high network congestion and so not all invitation messages were delivered within simulation time.
Figure 8 shows the message overhead of 50 join operations for various network sizes. TRS causes the lowest message overhead and moreover, in difference to ERS, this overhead is also independent of the network size. Note that multicast messages sent by ERS and ERA are even counted as a single message, so the real network load with these multicast based approaches is even higher as the chart indicates. As it can be further seen in the figure, TRS-MH causes more messages than TRS-RC. If we enforce strict height-balanced ACK trees, the minimalheight strategy needs about twice as much messages as the random-choice strategy. However, if we allow a maximum height deviation in the created ACK tree of two levels, the minimal-height strategy results in a only slightly increased message overhead compared to the random-choice strategy. The results show that the TRS scheme scales significantly better than ERS and ERA. Figure 9 shows the round trip delay depending on the number of join operations. The network consists of 251 nodes. Each dot in the chart is the average round trip delay of 12 measurements with different randomly distributed join operations and different background load levels. The round trip delay is assumed to be the time between sending a multicast message and receiving the last aggregated ACK at the root node.
The results show that TRS-MH decreases the round trip delays. The poor results of ERS and ERA with PIM- SM is conspicuous. If PIM-SM routing is used, the dissemination of multicast messages starts always at the same core node for all senders. Therefore, ERS and ERA typically finds always nodes close to this core rather than close to the searching node, which results in high round trip times.
In our last simulation, we have investigated the reliability of the created ACK tree, which is determined by its shape. As mentioned in Section II, the availability of a node depends on the availability of its ancestors in the ACK tree. If an non-leaf node becomes unavailable, this may cause message loss and extra overhead for rejoining the successors. In this respect, a well-shaped tree has a

minimal number of inner nodes which is satisfied by height-balanced trees. Figure 10 shows the average num-

Figure 8: Scalability in terms of network size

100

200

300

400

500

600

100 251 584 755 1110 1884
network size [number of nodes]

numberofsentmessages

ERA ERS TRS-RC
TRS-MH (dev. 2) TRS-MH (dev. 0) DVMRP

0
200
400
600
800
1000
1200
1400
1600
1800

100 251 584 755 1110 1884
network size [number of nodes]

numberofsentmessages

ERA ERS TRS-RC
TRS-MH (dev. 2) TRS-MH (dev. 0) PIM-SM

Figure 9: Round trip delay

0
200
400
600
800
1000
1200
1400
1600
1800

20 50 70 100 120 150 170 200 220
number of join operations

roundtripdelay[ms]

ERAERSTRS-RC

TRS-MH (dev. 2)
TRS-MH (dev. 0)

DVMRP

0
200
400
600
800
1000
1200
1400
1600
1800
2000

20 50 70 100 120 150 170 200 220
number of join operations

roundtripdelay[ms]

ERAERSTRS-RC

TRS-MH (dev. 2)
TRS-MH (dev. 0)

PIM-SM

Seite 11 Seite Textversion Grafikversion Übersicht

Seite 12 Seite Textversion Grafikversion Übersicht

ber of nodes that must rejoin the tree if a single ACK tree node fails. Note that this number is equivalent to the average path length in the ACK tree. Of course, the minimal-height strategy leads to the best results which corresponds with the theoretically achievable minimum. The use of ERS leads to a high number of dependent nodes, especially in combination with PIM-SM routing. The presented simulations with a wide variety of networks sizes, number of receivers and background traffic illustrates that TRS-MH performs better than ERS or ERA approaches and, in terms of round trip delay and average path length, better than TRS-RC.

V. SUMMARY

The token repository service with minimal-height strategy is a novel approach that allows to create height-balanced ACK trees. The basic concept is a distributed token repository storing tokens which represents the right to connect to a certain predecessor node in the corresponding ACK tree. We have described how it can be implemented in fault tolerant, yet efficient manner. Simulation studies in this paper illustrates that the token repository service with minimal height strategy performs better than ERS and ERA. It results in a lower message overhead and ACK trees with higher quality in terms of round trip delay and average path length.

REFERENCES

[1] S. Pingali, D. Towsley, F. Kurose: A comparison of sender-initiated and receiver-initiated reliable multicast protocols, Proceedings of ACM SIGMETRICS, 1994, pages 221-230.
[2] B.N. Levine, J.J. Garcia-Luna-Aceves: A comparison of known classes of reliable multicast protocols, Proceedings of the IEEE International Conference on Network Protocols, 1996, pages 112-121.
[3] R. Yavatkar, J. Griffioen, M. Sudan: A reliable dissemination protocol for interactive collaborative applications, Proceedings of the third ACM International Conference on Multimedia, 1995, pages 333-344. [4] J.C. Lin, S. Paul: RMTP: A reliable multicast transport protocol, Proceedings of the Conference on Computer Communications (IEEE Infocom), 1996, pages 1414-1424.
[5] D. M. Chiu, S. Hurst, J. Kadansky, J. Wesley: TRAM: A tree-based reliable multicast protocol, Sun Microsystems Laboratories Technical Report Series, TR-98-66, 1998.
[6] M. Hofmann: Adding scalability to transport level multicast, Lecture Notes in Computer Science, No. 1185, 1996, pages 41-55.
[7] S. Deering, D. Cheriton: Host Groups: A multicast extension to the internet protocol, RFC 966, 1985. [8] S. Deering: Host extensions for IP multicasting, RFC 1112, 1989.
[9] D. Boggs: Internet broadcasting, XEROX Palo Alto

Research Center, Technical Report CSL-83-3, 1983. [10] K. Rothermel, C. Maihöfer: A robust and efficient mechanism for constructing multicast acknowledgment trees, Proceedings of the Eight International Conference on Computer Communications and Networks (IEEE ICCCN), 1999, pages 139 - 145. [11] A. S. Tanenbaum: Computer networks, 3rd edition, Prentice-Hall, 1996.
[12] D. Waitzman, C. Partridge, S. Deering: Distance vector multicast routing protocol, RFC 1075, 1988. [13] Estrin, D.; Farinacci, D.; Helmy, A.; Thaler, D.; Deering, S.; Handley, M.; Jacobson, V.; Liu, C.; Sharma, P.; Wei, L.: Protocol Independent Multicast-Sparse Mode (PIM-SM): Protocol Specification, RFC 2362, 1998. [14] D. Clark: The design philosophy of the DARPA internet protocols, Proceedings of ACM SIGCOMM, 1988, pages 106-114.
[15] UCB/LBNL/VINT Network Simulator - ns (version 2), http://www-mash.cs.berkeley.edu/ns/ns.html. [16] Tiers Topology Generator, http://www.geocities.com/ResearchTriangle/3867/sourcecode.html.

Figure 10: Average path length

0
1
2
3
4
5
6
7
8
9
10

20 50 70 100 120 150 170 200 220
number of join operations

averagepathlength

ERAERSTRS-RC

TRS-MH (dev. 2)
TRS-MH (dev. 0)

PIM-SM

20 50 70 100 120 150 170 200 220
number of join operations

averagepathlength

ERAERSTRS-RC

TRS-MH (dev. 2)
TRS-MH (dev. 0)

DVMRP

Seite 12 Seite Textversion Grafikversion Übersicht