Multiplex communications – Network configuration determination – Using a particular learning algorithm or technique
Reexamination Certificate
2000-02-03
2001-07-31
Nguyen, Chau (Department: 2663)
Multiplex communications
Network configuration determination
Using a particular learning algorithm or technique
C370S351000, C370S408000, C370S229000
Reexamination Certificate
active
06269085
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to a method and system for detecting and pruning slow members of a multicast group.
The use of multicast data transmission within communication networks is well known. In a multicast transmission group one node, referred to herein as the sending node, transmits data in packets via a reliable multicast protocol to a plurality of other nodes in the multicast group. The multicast group is organized as a hierarchical repair tree as known in the art. The repair tree includes nodes identified as repair heads that receive Acknowledgements (ACKs) and Negative Acknowledgements (NACKs) from child nodes within the repair tree. In response to the receipt of a NACK at a repair head, the repair head retransmits data packets that were not received by its children.
The data packets may be multicast by the sending node to the group members and forwarded via the repair tree nodes or alternatively via other nodes that are not nodes within the repair tree. The nodes within the repair tree include the sending node and intermediate nodes which serve as repair heads and receivers which provide ACK/NACK responses to repair heads but do not serve as repair heads. For purposes of discussion herein, it is assumed that the multicast group members and the repair tree are the same, although it is recognized that data packets may be delivered to multicast group members via nodes that are not members of the repair tree.
For purposes of reference, packets transmitted toward the sending node from the receivers or intermediate nodes are considered as being transmitted upstream or up the tree and packets transmitted from the sending node or intermediate nodes toward a receiver node are considered as being transmitted downstream or down the tree.
Typically, in multicast data transmissions, reliability support mechanisms are employed which attempt to assure that all member nodes of a multicast group receive the transmitted data. Moreover, flow control mechanisms are employed that result in the adjustment of the data transmission rate to a rate that can be accommodated by intermediate nodes and receivers. The technique of reducing the transmission rate of the sending node to a rate that can be accommodated by all intermediate and receiver nodes fails, however, when the sending node must maintain a minimum data transmission rate which exceeds the rate at which one or more nodes in the multicast group can receive data.
For the above reasons, it would be desirable to have a mechanism which provides for the detection of multicast group members which cannot receive data from a sending node at a minimum specified data rate. Additionally, it would be desirable to provide a mechanism for pruning such nodes from the multicast group so that the sending node can resume transmission at an acceptable data rate.
BRIEF SUMMARY OF THE INVENTION
Consistent with the present invention a method and system is disclosed for identifying and pruning members of a multicast group that cannot keep up with a minimum specified data transmission rate. A multicast group includes a sending node that originates a multicast packet. The sending node transmits the multicast packet via a multicast protocol to multicast group members which, in the illustrated embodiment include intermediate nodes and receiver nodes. The multicast group is organized as a repair tree with the sending node and intermediate nodes serving as repair heads for reporting lower level nodes within the repair tree. The receiver and intermediate nodes at each level of the repair tree, from time to time, forward to their respective repair heads flow control messages in the form of ACK/NACK messages to indicate whether data packets were correctly received or need to be retransmitted by the respective repair heads.
Each intermediate node and receiver within the multicast group generates a slowness metric which is representative of the ability of the respective node to receive data packets at the then current data transmission rate employed by the sending node. The flow control packets forwarded upstream by the receiver nodes and intermediate nodes include, in a preferred embodiment, a selected one of the slowness metrics generated either by the reporting node or a downstream node within the repair tree and a subtree flag that indicates whether the respective slowness metric was generated by the reporting node or a node downstream of the reporting node. Each intermediate node aggregates and maintains a list of its slowness metric along with slowness metrics and subtree flags received from its respective reporting downstream children. Each intermediate node forwards upstream to its repair head the largest slowness metric of its aggregated list along with a subtree flag that indicates whether the slowness metric contained within the flow control message is due to the reporting node or a downstream node. In this manner, the sending node receives the largest slowness metric within the multicast group. Additionally, the receiver and intermediate nodes each forward upstream congestion packets which indicate when a congestion condition has been detected at the respective node. Congestion packets received at a repair head are forwarded upstream so that the sending node receives notification of the congestion condition.
If the sending node has reduced the transmission rate to the minimum acceptable transmission rate and congestion packets are still being received by the sending node, such is indicative of a pruning condition. Upon detection of a pruning condition, the sending node prunes its children within the repair tree that have a slowness metric greater than or equal to the largest slowness metric observed by the sending node minus a predetermined tolerance. Additionally, the sending node inserts into a multicast data packet a pruning flag along with the largest slowness metric observed by the sending node and optionally, an indication of the tolerance to be applied in pruning nodes within the multicast group. This packet is referred to as a pruning indication packet. The pruning indication packet is prefereably reliably multicast to the multicast group members. In response to receipt of the pruning indication packet, for each active child associated with the respective repair head, the respective intermediate node determines whether the respective child was responsible for generation of the slowness metric received from that child by inspection of the subtree flag received from that child. If the child was responsible for the generation of the respective slowness metric, the respective intermediate node determines whether the slowness metric received from the respective child is greater than the largest observed slowness metric minus the predetermined tolerance. If the slowness metric generated by the respective child is larger than the largest observed slowness metric minus the predetermined tolerance, the respective child is pruned from the multicast group. This process is repeated for each child of an intermediate node so that all “slow” child nodes are pruned from the multicast group. Once the slow intermediate and receiver nodes are pruned from the multicast group, operation of the multicast group may continue at an acceptable transmission rate at or above the minimum acceptable transmission rate.
REFERENCES:
patent: 5289460 (1994-02-01), Drake, Jr. et al.
patent: 5634001 (1997-05-01), Auerbach et al.
patent: 5696896 (1997-12-01), Badovinatz et al.
patent: 5831975 (1998-11-01), Chen et al.
patent: 6104695 (2000-08-01), Wesley et al.
patent: 6151633 (2000-11-01), Hurst et al.
Chiu Dah Ming
Kadansky Miriam C.
Provino Joseph E.
Wesley Joseph S.
Boakye Alexander O.
Nguyen Chau
Sun Microsystems Inc.
Weingarten, Schurgin Gagnebin & Hayes LLP
LandOfFree
Method and apparatus for hierarchical discovery and pruning... 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 hierarchical discovery and pruning..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for hierarchical discovery and pruning... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2556916