Electrical computers and digital processing systems: multicomput – Network computer configuring
Reexamination Certificate
2000-09-22
2002-07-30
Vu, Viet D. (Department: 2154)
Electrical computers and digital processing systems: multicomput
Network computer configuring
C709S224000, C709S235000, C709S238000, C370S254000
Reexamination Certificate
active
06427166
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to network communications. More specifically, the invention is a method and apparatus for performing sender-initiated pruning of slow receivers in a multicast data distribution set-up.
BACKGROUND OF THE INVENTION
In a multicast data distribution set-up a sender (“a source”), sends multicast data messages to a plurality of receivers called a multicast group. The sender's data rate is preconfigured or dynamically determined. Receivers in the multicast group provide the sender with data reception feedback in the form of repair requests. The sender responds to the data reception feedback by retransmitting the data to the multicast group.
The sender can operate in a mode that is either sensitive or insensitive to the data reception feedback, depending upon what the design goal is. A sender that is sensitive to data reception feedback responds to all or nearly all of the repair requests sent by receivers. A sensitive sender provides very reliable data transmission but it can be slow where there are a large number of receivers. When numerous receivers send repair requests, the sender uses a higher percentage of its available resources for servicing repair requests and has less resources available for performing other tasks such as sending more data. The result is a drop in the sender's performance.
Operating in an insensitive mode enables the sender to operate more quickly, but has some drawbacks. An insensitive sender ignores some repair requests, resulting in the sender being able to perform faster but also reducing the reliability of the data transmission if there are a large number of receivers. However, there are drawbacks such as not being responsive to network congestion, not being network friendly and being unable to deliver data to as many receivers as possible.
One way to overcome these problems is to implement pruning techniques. Pruning techniques involve identifying receivers which reduce the overall performance of the sender and removing them from the network so that the sender will perform faster. Currently available pruning techniques rely on either the sender or the receiver to perform the pruning. Both techniques prune unresponsive receivers from the data distribution set-up. As receivers are pruned from the data distribution set-up, the sender is left with fewer receivers from which it can expect to receive repair requests. Sender-initiated pruning techniques are entirely under the sender's control and remove receivers that are too slow, for example, receivers that operate at a much lower data rate than the sender. Receiver-initiated pruning techniques operate by having the receivers voluntarily prune themselves if they can not keep up with the sender's data rate. One problem with sender-initiated pruning techniques is that they tend to become less reliable as the number of receivers in the multicast group grows, because the sender becomes overloaded from servicing the large number of group members.
Receiver-initiated pruning techniques operate from the receiver as opposed to from the sender. Each receiver tracks whether or not it is able to respond to the data rate of the sender. The lightweight reliable multicast protocol (LRMP) uses this technique. In the receiver initiated pruning model, when a receiver detects that it is unable to keep up with the sender's data rate, it voluntarily prunes itself from the multicast data distribution tree. One problem with the receiver initiated pruning is that receivers may prune themselves prematurely in a situation where the sender may have been able to accommodate them by reducing its data rate.
SUMMARY OF THE INVENTION
To overcome the disadvantages of existing pruning techniques, and consistent with the present invention, the multicast delivery system support a centralized mechanism for initiating the pruning process in which receivers which do not meet minimum reception criteria can be isolated and removed from the multicast data distribution set-up without allowing the receivers to prune themselves independently and prematurely.
The sender provides a signaling mechanism to a tree-based hierarchically organized multicast data distribution set-up having multiple repair groups. The tree-based multicast data distribution set-up includes a sender at the root and a plurality of receivers extending from the sender like branches on the tree. The branches are organized into groups called repair groups. Some of the receivers function as the heads of these repair groups. The heads are responsible for servicing repair requests from members of their groups so that the sender is not obligated to service repair requests from all of the receivers in the data distribution set-up.
To determine which receivers should be pruned the sender uses a centralized signaling mechanism that responds to network congestion feedback information from one or more of the receivers. Based on the congestion feedback, the sender recommends that the group heads select candidates for pruning from their groups. Receivers become candidates for pruning if they are slow, not responsive, or request an excessive number of repairs from the group head. A receiver is considered to be slow if it runs at a data rate much lower than the sender's data rate. The sender can reduce its data rate to accommodate slow receivers so that the group head does not immediately mark it for pruning but when the sender's data rate drops so low that data transmission is beyond the operating characteristics of the sender or is too slow to be practical, then the sender stops reducing its data rate and lets the group head mark the receiver for pruning.
In accordance with an embodiment consistent with the present invention, a method and apparatus for distributing multicast data, performed by a data processor, includes the steps of forming a multicast repair tree including a sender, a plurality of heads, and a plurality of receivers. At least one head is associated with the sender and at least one receiver is associated with the head. A sender sends a plurality of multicast messages at a data rate to the plurality of heads and the plurality of receivers. The sender receives a status associated with a receiver of the head from one of the plurality of heads. The status may be a congestion status. The sender slows the data rate in accordance with the status. An embodiment consistent with the present invention may be implemented as a computer program product or as a computer data signal embodied in a carrier wave.
Advantages of the invention will be set forth, in part, in the description that follows and in part, will be understood by those skilled in the art from the description or may be learned by practice of the invention. The advantages of the invention will be realized and attained by means of the elements and combinations particularly pointed out in the appended claims and equivalents.
REFERENCES:
patent: 5289460 (1994-02-01), Drake, Jr. et al.
patent: 5313454 (1994-05-01), Bustini et al.
patent: 5331637 (1994-07-01), Francis et al.
patent: 5361256 (1994-11-01), Doeringer et al.
patent: 5675576 (1997-10-01), Kalampoukas et al.
patent: 5831975 (1998-11-01), Chen et al.
patent: 5903559 (1999-05-01), Acharya et al.
patent: 5905871 (1999-05-01), Buskens et al.
patent: 6078590 (2000-06-01), Farinacci et al.
patent: 6185210 (2001-02-01), Troxel
D. Katz, RFC 2113 entitled “IP Router Alert Option”, published Feb. 1997.
Douglas E. Comer, Chapter 17, entitled “Multicast Addressing (IGMP)” in Book entitled “Internetworking with TCP/IP vol. 1 Principles, Protocols, and Architecture”, 2sup.nd Edition, published by Prentice Hall, 1991, pp. 281-290.
D. DeLucia and K. Obraczka, “Multicast Feedback Suppression Using Representatives”, Infocom 1997, 16.sup.th Annual Joint Conference of the IEEE Apr. 7-12, 1997, pp. 463-470.
Hanna Stephen R.
Hurst Stephen A.
Kadansky Miriam C.
Rosenzweig Philip M.
Wesley Joseph
Sun Microsystems Incorporated
Vu Viet D.
LandOfFree
Method and apparatus for routing and congestion control in... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for routing and congestion control in..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for routing and congestion control in... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2853748