Sun Microsystems, Inc.

Dah Ming Chiu

Miriam C Kadansky

Radia Joy Perlman

Joseph S Wesley

Stephen R Hanna

Stephen A Hurst

Philip M Rosenzweig

Joseph E Provino

Murat Yuksel

Guy Lewis Steele, Jr

John Reynders

Radia J Pearlman

A system for selecting routing information from a routing table describing alternative routes between end nodes. The routing table represents a set of minimum cost, deadlock-free routes between end nodes. The selected routing information is included in forwarding tables, and sent to networking devices in the network. The selected routing information is optimized for at least one network performance metric, such as overall network capacity or fault tolerance. Capacity optimization is obtained by selecting from alternative routes stored within the routing table such that the standard deviation of the number of routes flowing over each link in the network is minimized. Fault tolerance optimization is achieved by selecting from the alternative routes stored in the routing table such that the selected route for a given end node pair has a 'failover' route with a maximum number of dissimilar links from the selected route.

Method of optimizing network capacity and fault tolerance in deadlock-free routing

A system and method for adding routing information for a node to a routing table, which efficiently makes necessary changes to the routing table to support routing to and from the node, while maintaining the deadlock-free quality of the paths described by the routing table. The routing table is generated by storing routing information in the routing table that reflects and describes a deadlock-free set of paths through a network of nodes. A row of entries is added to the routing table describing how to forward data units from the node. A column of entries is added to the routing table describing how to forward data units addressed to the node. The forwarding information within each entry added to the routing table maintains the deadlock-free quality of the set of paths represented by the forwarding table.

Efficient system and method of node and link insertion for deadlock-free routing on arbitrary topologies

A distributed system and method generate 'layered routes' that reflect a layered representation of a network, which representation provides deadlock-free routes. The layered representation consists of an ordered set of layers, where each layer is a deadlock-free sub-topology of the network. In determining routes, the links used in each route are constrained to be taken from layers of non-decreasing order as the route extends from source to destination. A device that determines a better or equal cost path to a destination node with respect to its current path to that node sends a route information message to its neighbor devices. The receiver of a route information message may then accept the message and begin using the new path described by the message, or reject the message without using the new path.

Calculation of layered routes in a distributed manner

One embodiment of the present invention provides a system that facilitates efficient flow control for data transmissions between a sender and a plurality of receivers. The system operates by sending a stream of packets from the sender to the plurality of receivers, wherein the packets include information specifying a sampling window for the stream of packets. The sender subsequently receives feedback information from the plurality of receivers, wherein a receiver sends feedback information to the sender if a congestion condition occurs at the receiver while receiving packets within the sampling window. In response to the feedback information, the sender adjusts a rate of transmission for the stream of packets. In one embodiment of the present invention, the feedback information from the receivers is aggregated at intermediate nodes prior to reaching the sender in order to eliminate redundant feedback information. In one embodiment of the present invention, the sender communicates with the plurality of receivers through a tree of nodes, wherein the sender is a root node of the tree.

Method and apparatus for facilitating efficient flow control for multicast transmissions

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 system for accurately measuring the reception characteristics of receivers in a multicast data distribution group having a sending node and a plurality of receivers. The multicast group is organized as a repair tree in which selected nodes of the multicast group comprise repair nodes for downstream receivers. Multicast data packets transmitted by the repair nodes include a retransmission count field in addition to the multicast packet header information, a session identifier, a packet sequence number and payload data. The retransmission count provides an indication of the number of times the respective packet has been retransmitted in response to a repair request. The receivers include an original packet counter and a retransmission count counter for each multicast session. Each receiver increments the original packet counter upon receipt of a packet that has not been previously received. Each receiver adds the value contained in the retransmission count field of a received packet to the retransmission count counter upon receipt of a retransmitted multicast packet that corresponds to a packet identified as a missing packet by the respective receiver. The data in the actual packet count counter and the retransmission count counter is employed to generate a loss metric at each receiver that provides a measure of the reception characteristic of the respective receiver for the particular multicast session.

Method and system for measuring reception characteristics in a multicast data distribution group

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

A method and apparatus that constructs a &ldquo;router database&rdquo; and then uses the database to determine a longest match between a piece of target data, such as an address in a packet to be routed, and the database. The database contains a comparison table having a plurality of entries. In a first embodiment, each entry has up to k values, where 2<&equals;k<&equals;N, where N is a number of comparison values in the database. In a second embodiment, each entry has up to k&minus;1 values. During operation, various ones of the comparison table entries are loaded and compared to the address to determine a longest matching prefix in the router database. The comparison can be done in parallel.

Method and apparatus for longest prefix address lookup

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

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 method and system for pruning slow multicast group members in a multicast group that includes a sending node and member nodes. The sending node and selected ones of the other nodes comprise repair heads of a repair tree. Each repair head has at least one child. Each of the member nodes generates a slowness metric. Each member node repair head aggregates its own slowness metric with the slowness metrics of their respective children in the tree along with a subtree flag that indicates whether the respective slowness metric is due to the reporting node or a node downstream of the reporting node. The member node repair heads propagates the largest of the aggregated slowness metrics upstream along with a subtree flag associated with the propagated slowness metric. Via this process the sending node receives the largest slowness metrics generated in respective branches of the repair tree along with corresponding subtree flags associated with the respective metrics. In response to the receipt of an indication of congestion at one or more of the member nodes when the sending node is transmitting at a minimum acceptable data rate, the sending node initiates pruning of slow group members in a predetermined manner. The globally largest slowness metric is employed in conjunction with the aggregated slowness metrics and associated subtree flags retained at the sending node and intermediate nodes to identify slow member nodes within the multicast group that should be pruned.

Method and apparatus for hierarchical discovery and pruning of slow members of a multicast group

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.

Growing community of inventors

Acton, MA, United States of America

Dah Ming Chiu