Electrical computers and digital processing systems: support – Multiple computer communication using cryptography – Particular communication authentication technique
Reexamination Certificate
1997-03-18
2001-04-24
Swann, Tod R. (Department: 2132)
Electrical computers and digital processing systems: support
Multiple computer communication using cryptography
Particular communication authentication technique
C713S168000, C713S169000, C380S287000, C380S280000, C455S018000, C455S412100, C455S502000
Reexamination Certificate
active
06223286
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a multicast message transmission device and a message receiving protocol device, which realize a fair message delivery time for a multicast message transmitted from a multicast message transmission device to a plurality of message receiving protocol devices through a communication network.
2. Description of the Background Art
A multicast communication is a communication scheme useful for applications such as a broadcasting and a distributed information processing using a communication network.
In the computer application and the information providing service, a highly reliable multicast communication scheme is required. Also, in order to take a full advantage of the characteristics of the multicast communication, there are cases in which the multicast communication is required to have a property that the identical result can be obtained at all receiver devices. This property is also applicable to a scheme for maintaining the integrity of data in a case of distributedly storing data, and a scheme for realizing a fair information providing service among subscribers.
In response to these demands, a protocol for guaranteeing the following properties has been proposed and practiced. Here, the group of receiver devices which receive the same multicast message are collectively referred to as a multicast group.
(1) Atomicity:
In a case of delivering a certain message, this message is not delivered at all unless this message is received by all the receiver devices. In other words, when a multicast message is received at one receiver device, it is guaranteed that the same multicast message is also delivered to all the other receiver device of the same multicast group.
(2) Order equivalency:
An order of receiving messages is identical among all the receiver devices of the same multicast group. The major causes for lowering the reliability in the multicast communication are a bit error in the message transmission and a discarding of the message during the message transmission. The bit error is caused by an error in a transmission path, while the discarding is caused by the congestion (the congestion in the packet network or the ATM network). As for the bit error, the message delivery failure probability can be lowered by employing the error correction technique at communicating terminals. As for the discarding, the message delivery failure probability can be lowered by carrying out the message re-transmission. Of course, the re-transmission is also effective for the message delivery failure due to the bit error, but the error correction technique is not effective for the congestion over such an extended period of time as the message is completely lost. In order to secure the reliability with respect to the congestion, the re-transmission technique is indispensable.
On the other hand, for a realization of the property that the identical receiving result can be obtained at all the receiver devices, the message delivery failure and the irregularity of the transmission delay can be obstacles. The message delivery failure can be recovered by the re-transmission as described above, but the message delivery time will be delayed when the re-transmission is carried out. Also, the transmission delay difference affects the message delivery time.
In the following, the prior art for realizing the multicast communication which satisfies the above described two properties will be described.
A device for managing the message transmission and reception in the multicast group is called a master, and a device for receiving a message is called a client, while a device for transmitting a message is called a sender. Each of the master, the client, and the sender can be conceptually divided into a functional portion for processing the multicast communication protocol and a functional portion for carrying out the multicast communication application by utilizing the protocol processing function.
Here, an exemplary case for providing the stock price information by the multicast will be considered. The application in this case corresponds to a portion for carrying out the broadcast of the stock price at the sender side, and a portion for processing the stock price information at the receiver side, such as a portion for handling the electronic stock transaction according to the stock price information for example.
The protocol processing function and the application function can be divided conceptually, but in general, they are not clearly separated in the actual implementation. In many personal computers, even when the protocol processing function and the application function are divided as the software function portions, both of these functions are executed on the same memory space by the same processor.
Now, with reference to
FIG. 1
, a conventional multicast receiving procedure will be described.
A master
701
transmits a message to a client-A
702
and a client-B
703
through a multicast connection. The messages are assigned with identifiers which have continuously ordered relationship. In
FIG. 1
, Mp denotes a message with an identifier p.
When the message Mp is received, the client-A
702
and the client-B
703
transmit acknowledge response ACKp(A) and ACKp(B) respectively to the master
701
. The acknowledge response contains the message identifier p and the client identifier. There is no need to multicast this response. When the acknowledge responses ACKp(X) from all the clients (the client-A
702
and the client-B
703
in this case) are confirmed, the master
701
multicasts a message release permission RELp(i). Here, i is an identifier of a message to which the release permission is issued. This identifier is given in an order of issuing the release permission, in a manner of i, i+1, . . . .
Next, with reference to
FIG. 2
, a conventional multicast receiving procedure in a case of a message loss will be described. Here, the same notations as in
FIG. 1
are used in FIG.
2
.
The master
701
transmits the message Mp to the client-A
702
and the client-B
703
through the multicast connection. The master
701
also sets a timer T
1
at a time of the transmission. The client-A
702
receives the message Mp at a time t
0
. On the other hand, the message to the client-B
703
is lost. In this case, the master
701
detects that the acknowledge response for the message Mp from the client-B
703
has not arrived at the time-out timing of the timer T
1
, and carries out the re-transmission of the message Mp. When the message Mp is received, the client-B
703
transmits the acknowledge response ACKp(B). When this acknowledge response ACKp(B) is received, the master
701
has the acknowledge responses from all the clients, so that the master
701
multicasts the message release permission RELp(i).
In the message re-transmission, the message is multicast to all the clients, and the client who received this message transmits the acknowledge response, even when the acknowledge response for the same message was already transmitted before. In this manner, even when the acknowledge response ACKp(X) is lost, the master
701
can confirm that the message is received by all the clients according to the acknowledge responses for the re-transmission after the time-out.
Next, with reference to
FIG. 3
, a conventional multicast receiving procedure in a case of a release permission message loss will be described. Here, the same notations as in
FIG. 1
are used in FIG.
3
.
FIG. 3
shows a case in which the release permission message RELp(i) for the message Mp transmitted to the client-B
703
is lost. The client-A
702
normally received the release permission message RELp(i), and the message Mp is released at a time t
2
.
At the client-B
703
, the receiving procedure for the next message Mp+1 is normally carried out while the message Mp remains unreleased, and the client-B
703
receives the release permission message RELp+1 for that next message Mp+1. Then, the client-B
703
compares the identifier p+1
Callahan Paul E.
Foley & Lardner
Kabushiki Kaisha Toshiba
Swann Tod R.
LandOfFree
Multicast message transmission device and message receiving... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Multicast message transmission device and message receiving..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multicast message transmission device and message receiving... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2493276