Sun Microsystems, Inc.

Stephen A Hurst

Stephen R Hanna

Miriam C Kadansky

Joseph S Wesley

Radia Joy Perlman

Philip M Rosenzweig

Dah Ming Chiu

Joseph E Provino

Radia J Pearlman

An embodiment consistent with the present invention includes a method and apparatus for forming a multicast repair tree. The methods perform by a data processor and comprises the steps of determining, for each of a plurality of potential heads in a multicast group, a ranking value associated with the potential head; advertising, by the potential heads to a plurality of potential receivers; prioritizing, by a potential receiver, the ranking values from the potential heads; and binding, by a potential receiver to the head having the highest ranking value, thereby forming a group of which the potential receiver,is a member and the potential head is the head. The ranking values may include &ldquo;able&rdquo;, &ldquo;unable&rdquo;, &ldquo;willing&rdquo;, and &ldquo;reluctant.&rdquo; The ranking value of a potential head determines in accordance with a static or a dynamic configuration. Ranking values determine dynamically based on ranges of system resource levels such as memory and available processor resources.

Method and apparatus for using ranking to select repair nodes in formation of a dynamic tree for multicast repair

A method and apparatus for identifying a data message that is eligible for discard. A beacon node periodically transmits a beacon message to a plurality of client nodes communicatively coupled via a network. Each beacon message includes a beacon sequence number and preferably, the beacon sequence numbers are authenticated by the beacon, node. The client nodes, upon receipt of the beacon messages, verify the authenticity of the respective received beacon sequence numbers and generate a local sequence number derived from the received beacon sequence number. When one client in the session has data to transmit to another client in the session, the sending client assembles a data message and inserts its local sequence number in the data message prior to transmission of the data message to the other client nodes in the session. The client nodes receiving the data message discard the data message if their respective local sequence number at the time of receipt of the data message exceeds the local sequence number inserted in the data message by a predetermined value. In one embodiment, the beacon node generates sequence numbers at a periodic interval P but only transmits 1 out of every m beacon sequence numbers to the client nodes in the session. The client nodes each set a local sequence counter equal to the beacon sequence number upon receipt of the beacon message and thereafter, increment the local sequence counter periodically at interval P. The local sequence counter value is employed as the local sequence number in each client node.

Use of beacon message in a network for classifying and discarding messages

A method of detecting congestion in a computer network uses a receiving station which determines a first number of messages missing in a first acknowledgment window. The station then determines a second number of messages missing in a subsequent acknowledgement window. The station then measures congestion on the network in response to an increase in the number of missing messages as indicated by the first number of missing messages in the first acknowledgement window and the second number of missing messages in the second acknowledgement window.

Detecting congestion by comparing successive loss of packets in windows to provide congestion control in reliable multicast protocol

Receiver stations located close together in a computer network dynamically form a multicast repair tree by a plurality of receiver stations choosing a repair head station from among the closely located receiver stations. A receiver station calculates its distance from a repair head station by subtracting the decremented TTL value read from the IP header from the initial value of the TTL parameter carried in field TTL SCOPE of HELLO messages, transmitted by repair head stations. Using a criteria that a closer repair head station is a more optimum repair head station, receiver stations listen to each received HELLO message, calculate the distance to the repair head station, and reaffiliate with the closest repair head station.

DYNAMIC OPTIMIZATION FOR RECEIVERS USING DISTANCE BETWEEN A REPAIR HEAD AND A MEMBER STATION IN A REPAIR GROUP FOR RECEIVERS HAVING A CLOSELY KNIT TOPOLOGICAL ARRANGEMENT TO LOCATE REPAIR HEADS NEAR THE MEMBER STATIONS WHICH THEY SERVE IN TREE BASED REPAIR IN RELIABLE MULTICAST PROTOCOL

A multicast repair tree is established, the repair tree having one sender station and a plurality of repair head stations. A repair head station has an affiliated group of member stations. A repair head station retransmits a lost message to its affiliated group of member stations upon receipt from a member station of a NACK message indicating that the selected message was not received. Acknowledgment windows (ACK windows) are established in a member station for transmission of ACK or NACK message by the member station. A number of messages transmitted by the sender station during a transmission window is established. Also a same size of ACK window is established in the receiving stations, with a slot in the ACK window corresponding to each message transmitted by the repair head station. Each receiving station is assigned a slot in the ACK window during which time that receiving station transmits its ACK or NACK messages. Thus the ACK window slots assigned to receiver stations for transmission of ACK/NACK windows are staggered so that different receiver stations transmit their ACKNACK messages at different times. The slot for a particular receiver station to use may be assigned by a random process.

Multiple ACK windows providing congestion control in reliable multicast protocol

An embodiment consistent with the present invention includes a method and apparatus for distributing multicast data. The method may be performed by a data processor and comprises the steps of forming a multicast repair tree including a sender, a plurality of heads, and a plurality of receivers, wherein at least one head is associated with the sender and at least one receiver is associated with the head; sending, by a sender to the plurality of heads and the plurality of receivers, a plurality of multicast messages at a data rate; receiving, by the sender from one of the plurality of heads, a congestion status associated with a receiver of the head; and slowing the data rate, by the sender, in accordance with the congestion status.

Method and apparatus for routing and congestion control in multicast networks

To authenticate and authorize prospective members in a reliable multicast data distribution setup, the prospective members contact a central authority to obtain a &ldquo;participation certificate&rdquo; for the multicast session. The central authority authenticates each node and issues a digitally signed certificate to the node. Each certificate contains information specifying the manner in which the respective node is authorized to participate in the multicast session in addition to the respective node's public key. The nodes exchange their participation certificates with each other during session-establishment dialog to prove their identities and their authorization to participate. Each node verifies the rights of other nodes based on authorization information contained in the participation certificate received from the other node. Thus, a node is allowed to participate as a repair node only if it presents a participation certificate authorizing it to do so. Disruption in network operation is avoided by reducing the ability of malicious nodes to consume resources to the detriment of legitimate session members.

Tree-based reliable multicast system where sessions are established by repair nodes that authenticate receiver nodes presenting participation certificates granted by a central authority

A base node of a computer network sends concurrent TTL query messages using multicast to other receiving nodes of the computer network. Each of the TTL query messages has a different time-to-live (TTL) parameter value and records the TTL parameter of the TTL query message into a message body. The receiving nodes receive one or more of the TTL query messages, namely, those TTL query messages whose TTL parameter values are sufficient to allow the TTL query message to reach the receiving node. Each receiving node can determine the TTL distance to the receiving node from the base node by determining the lowest TTL parameter value of all TTL query messages which reached the receiving node. Each receiving node communicates the TTL distance by sending to the base node a TTL query response message which indicates, in the message body, the least TTL parameter value of all TTL query messages received by the receiving node. Accordingly, the base node can determine TTL distances to other nodes of the computer network very quickly.

Determination of distance between nodes in a computer network

An embodiment consistent with the present invention includes a method and apparatus for forming a multicast repair tree. The method may be performed by a data processor and comprises the steps of determining, for each of a plurality of potential heads in a multicast group, a ranking value associated with the potential head; advertising, by the potential heads to a plurality of potential receivers; prioritizing, by a potential receiver, the ranking values from the potential heads; and binding, by a potential receiver to the head having the highest ranking value, thereby forming a group of which the potential receiver is a member and the potential head is the head. The head may also be the sender. There may be a plurality of heads. The ranking values may include &ldquo;able&rdquo;, &ldquo;unable&rdquo;, &ldquo;willing&rdquo;, and &ldquo;reluctant.&rdquo; The ranking value of a potential head may be determined in accordance with a static or a dynamic configuration. Ranking values may be determined dynamically based on ranges of system resource levels such as memory and available processor resources.

Method and apparatus using ranking to select repair nodes in formation of a dynamic tree for multicast repair

Method and apparatus for routing and congestion control in multicast

A computer sends a message to each of a number of recipient computers of a computer network by sending the message as a multicast message to near ones of the recipient computers and sending the message as unicast messages to far ones of the recipient computers. The sending computer determines the circumstances under which a combination of multicast and unicast messages are efficient by determining that many recipient computers are near the sending computer and that few recipient computers are far. The sending computer makes such a determination by determining no more than a predetermined number of recipient computers are at least a predetermined distance further from the sending computer than are the others of the recipient messages. The sending computer can also determine that the burden imposed upon the computer network by a multicast message is justified by the need to deliver the message to its intended recipients. For intended recipients which are too far and too few to justify use of a multicast message, unicast messages are sent.

Efficient message distribution to subsets of large computer networks

Determination of a Time To Live ('TTL') hop count for repair data units transmitted from a repair head to a standard destination device in a communications network is facilitated for multicast transmission. The repair head destination device monitors the path between the repair head destination device and the standard destination devices by exchanging messages with the respective standard destination devices. The repair head transmits control messages to each destination device including a dispatched TTL value and an Internet Protocol ('IP') TTL value. If the control message fails to reach one of the standard destination devices, that standard destination device transmits a transmission failure indication to the repair head destination device. In response to the transmission failure indication the TTL value employed for the control message is increased. Following receipt of the control message, the standard destination device calculates the TTL value required to transmit a data unit from the repair head to the standard destination device by subtracting the IP TTL value from the dispatched TTL value. If the calculated TTL difference value is non-zero then an excess-TTL indication is transmitted from the standard destination device to the repair head destination device.

Growing community of inventors

Nashua, NH, United States of America

Stephen A Hurst