Tree-based ordered multicasting method

Details Tree-based ordered multicasting method Tree-based ordered multicasting method

2006-04-18

2006-04-18

Chin, Wellington (Department: 2664)

Multiplex communications

Pathfinding or routing

Switching a message which includes an address header

C370S401000, C370S407000, C370S408000, C370S465000, C370S486000, C370S487000, C709S220000, C709S221000, C709S226000, C709S227000, C709S243000, C709S244000

Reexamination Certificate

active

07031308

ABSTRACT:
A method for performing end-to-end “tree-based ordered multicasting” (TOM) which ensures collective integrity and consistency of distributed operations, and which is applicable to distributed multiparty collaboration and other multipoint applications. The TOM protocol performs cascaded total ordering of messages among on-tree hosts en route from senders to receivers, and does not require the building of a separate propagation graph to compute ordering information. TOM elects sequencer nodes dynamically based on address extensions of the multicast tree. Message ordering is performed by multicasting a message from each source node to receivers, unicasting a control message from a source node across a primary node to an ordering node for the designated multicast group or transmission in the tree, determining a binding sequence number for the message and a multicast to the receiver group, and delivering messages at end hosts according to the agreed-upon sequence numbers.

REFERENCES:
patent: 5195086 (1993-03-01), Baumgartner et al.
patent: 5541927 (1996-07-01), Kristol et al.
patent: 6353596 (2002-03-01), Grossglauser et al.
patent: 6487690 (2002-11-01), Schuster et al.
Levine, Brain Neil et al.; “The Case for Reliable Concurrent Multicasting Using Shared Ack Trees,” Proceedings ACM Multimedia, pp. 365-376, Boston MA, Nov., 1996.
Paul, Sanjoy etl al; “Reliable Multicast Transport Protocol (RMTP),” IEEE Journal on Selected Areas in Communications, vol. 15, No. 3, pp. 407-421, Apr., 1997.
Yavatkar, Rajendra; “A Reliable Dissemination Protocol for Interactive Collaborative Applications,” Proceedings ACM Mutlimedia, pp. 333-344, San Francisco, CA., Nov., 1995.
Shieh, S.-P. et al.; “A Comment on ‘A Total Order Multicast Protocol Using Propagation Trees,’” IEEE Transactions on Parallel and Distribution Systems, vol. 8, No. 10, pp. 1084, Oct., 1997.
Chandra, T. et al.; “Unreliable Failure Detectors for Reliable Distributed Systems,” Journal of the ACM, vol. 43, No. 2, pp. 225-267, Mar., 1996.
Cheriton, D.R. and Skeen, D., “Understanding the Limitations of Causally and Totally Ordered Communication,” Operating Systems Review, vol. 27, No. 5, pp. 44-57, Dec., 1993.
Dolev, D. et al.; “Early Delivery Totally Ordered Multicast in Asynchronous Enviroments,” International Symposium on Fault-Tolerant Computing, pp. 544-553, Toulouse, France, Jun., 1993.
Garcia-Molina, H. et al; “Ordered and Reliable Multicast Communication,” ACM Transactions on Computing System, vol. 9, No. 3, pp. 242-271, Aug., 1991.
Guerraoui, R. et al.; “Total Order Mutlicast to Multiple Groups,” Proceedings 17th International Conference on Distributed Computing Systems, pp. 578-585, Baltimore, Maryland, May, 1997.
Jia, X.; “A Total Ordering Multicast Protocol Using Propagation Trees,” IEEE Tranactiosn on Parallel and Distributing Systems, vol. 6, No. 6, pp. 617-627, Jun., 1995.
Lamport, L.; “Time, Clocks and the Ordering of Events in a Distributed System,” Communications ACM, vol. 21, No. 7, pp. 558-565, Jul., 1978.
Navaratnam, S. et al.; “Reliable Group Communication in Distributed Systems,” Proceedings 8th International Conference on Distributed Computing Systems, pp. 439-446, San Jose, CA., Jun., 1988.
Ng, T.P.; “Ordered Broadcast for Large Applications,” Proceedings IEEE 10th Symposium Reliable Distributing Systems, pp. 188-197, PIsa, Italy, Sep., 1991.
Obraczka, K.; “Multicast Transport Protocols: A Survey and Taxonomy,” IEEE Communications Magazine, vol. 36, No. 1, pp. 94-102, Jan., 1998.
Rajagopalan, B. et al.; “A Token-Based Protocol for Reliable, Ordered Multicast Communication,” Proceedings of the 8th Symposium on Reliable Distributed Systems, pp. 84-93, Seattle, WA., Oct., 1989.
Rodrigues, L. et al.; “Totally Ordered Multicast in Large-Scale Systems,” Proceedings of the 16th Internatinoal Conference on Distributed Computing Systems, pp. 503-510, Hong Kong, May, 1996.
Rodrigues, L. et al.; “Scalable Atomic Multicast,” Proceedings of the 7th International Conference on Computer Communications and Networks, pp. 840-847, Lafayette, LA, Oct., 1998.
ZeinEldine, O. et al.; “Multicast in Interconnected Networks,” Proceedings of Symposium on Computers and Communications, pp. 313-319, Alexandria, Egypt, Jun., 1995.

Affiliated with

Also associated with

Rating

Tree-based ordered multicasting method does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Tree-based ordered multicasting method, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Tree-based ordered multicasting method will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3605607