US 6,959,323 B1Granted

Scalable atomic multicast

AssigneeLucent Technologies Inc.

InventorsHong-Yi Tzeng, Yin Zhang

Life of this patent

Estimating the term…

Loading patent…

Abstract

This document describes a protocol for reliably synchronizing states of nodes in a distributed environment through use of a Scalable Atomic Multicast (SAM) Service that ensures both atomicity and total order among messages sent to a multicast group. In addition to possessing good scalability property, this fault-tolerant protocol does not require explicit knowledge of multicast group membership, allows for non-disturbing state synchronization, and supports asynchronous non-blocking communications. According to one aspect of this invention, a dedicated sequencer is responsible solely for assigning sequence numbers to the multicast messages. The sequencer does not multicast the messages. Another aspect of the invention is the use of receiver-driven negative acknowledgments. According to third aspect, the invention supports message consolidation and garbage collection.

Claims28

Dependent claims

A method for multicasting data messages to members of a multicast group, the multicast group comprising a sequencer, one or more clients, one or more data servers, and one or more commit servers, the method comprising the steps of:

transmitting a first data message to the members of the multicast group;
each data server that receives the first data message requesting the sequencer to assign a first sequence number to the first data message, the first sequence number being from a sequence of numbers allocated to the data messages, said first sequence number following all sequence numbers assigned prior to assignment of the first sequence number;
assigning the first sequence number to the first data message, in response to the sequencer receiving a first quantity of the requests to assign a first sequence number to the first data message said first quantity of requests being other than a majority of requests from the data servers;
notifying the commit servers of the assignment of the first sequence number to the first data message;
each of the commit servers sending to the sequencer an acknowledgment of the notification of the assignment of the first sequence number to the first data message, in response to being notified of the assignment of the first sequence number to the first data message;
committing the first sequence number to the first data message, in response to the sequencer receiving a second quantity of the acknowledgments of the notification of the assignment of the first sequence number to the first data message;
and
informing the members of the multicast group of the commitment of the first sequence number to the first data message.

5 more elements

A method for processing data messages multicast to members of a multicast group, the multicast group comprising a sequencer, one or more clients, one or more data servers, and one or more commit servers, the method comprising the steps of:

each data server that receives said each data message requesting the sequencer to assign a sequence number, from a sequence of numbers allocated to the data messages, to said each data message, in response to receiving each data message;
assigning a sequence number following all sequence numbers assigned prior to assignment of the sequence number to said each data message, in response to the sequencer receiving a first quantity of requests to assign a sequence number to said each data message said first quantity of requests being other than a majority of requests from the data servers;
notifying the commit servers of each assignment, each notification identifying said each assignment by said each data message and the sequence number assigned to said each data message;
each of the commit servers sending to the sequencer an acknowledgment of said each notification, in response to being notified of said each assignment, said acknowledgment identifying said each data message;
committing said each assignment, in response to the sequencer receiving a second quantity of the acknowledgments identifying said each data message;
and
informing the members of the multicast group of each commitment.

4 more elements

A method for multicasting data messages to members of a multicast group comprising the steps of:

transmitting a data message to the members of the multicast group;
requesting assignment of a sequence number to the data message;
assigning the sequence number to the data message in response to a non-majority number of requests from the data servers;
sending notification of the assignment of the sequence number to the data message;
sending an acknowledgment of the notification of the assignment of the sequence number to the data message;
committing the sequence number to the data message;
and
informing the members of the multicast group of the commitment of the sequence number to the data message.

5 more elements

Dependencies are inferred from the claim text.

Facts

Application: 09/384,699Filed 27 Aug 1999 · us provisional application
Priority: 27 Aug 1998
Granted: 25 Oct 2005
Term ends: Not estimatedThe source records don’t support an estimate.

Classification6 codes

H04L 12/1881
For broadcast or conference , e.g. multicast: with schedule organisation, e.g. priority, sequence management
H04L 47/10
Traffic control in data switching networks: flow control; Congestion control
H04L 47/15
Flow control; Congestion control: in relation to multipoint traffic
H04L 47/34
Flow control; Congestion control: ensuring sequence integrity, e.g. using sequence numbers