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

[0002] This application claims the benefit of Provisional application Ser. No. 60/091,330, filed Jun. 30, 1998.

[0003] This Application is related to patent applications as follows:

[0004] Title, “Dynamic Optimization Using the Number of Member Receiver Stations in a Repair Group for Receiver Stations Having Dense of Sparse Topological Arrangements in Tree Based Repair in Reliable Multicast Protocol” by, Miriam C. Kadansky, Dah Ming Chiu, Stephen R. Hanna, Stephen A. Hurst, Joseph S. Wesley, Philip M. Rosenzweig, and Radia J. Perlman, filed on Jun. 18, 1999 (date) with Ser. No. 09/336,669,

[0005] Title, “Multiple ACK Windows Providing Congestion Control in Reliable Multicast Protocol” by, Dah Ming Chiu, Miriam C. Kadansky, Stephen R. Hanna, Stephen A. Hurst, Joseph S. Wesley, Philip M. Rosenzweig, and Radia J. Perlman, filed on Jun. 18, 1999 (date) with Ser. No. 09/336,659;

[0006] Title, “Historically Highest Transmission Rate for Determining Incremental Transmission Rate to Provide Congestion Control in Reliable Multicast Protocol” by, Dah Ming Chiu, Miriam C. Kadansky, Stephen R. Hanna, Stephen A. Hurst, Joseph S. Wesley, Philip M. Rosenzweig, and Radia J. Perlman, filed on Jun. 18, 1999 (date) with Ser. No. 09/336,671;

[0007] Title, “Detecting Congestion by Comparing Successive Loss of Packets in Windows to Provide Congestion Control in Reliable Multicast Protocol” by, Dah Ming Chiu, Miriam C. Kadansky, Stephen R. Hanna, Stephen A. Hurst, Joseph S. Wesley, Philip M. Rosenzweig, and Radia J. Perlman, filed on Jun. 18, 1999 (date) with Ser. No. 09/336,670;

[0008] all disclosures of which are incorporated herein by reference.

[0009] This invention relates to multicast communication in computer networks, and more particularly to optimization of a repair tree in reliable multicast protocol.

[0010] Communication between computers in a computer network can be established by one of several methods. These include unicast messaging (where a source station and a destination station exchange messages over a point to point path), broadcast communication (where a sender station transmits messages which may be received by all stations attached to the network), multicast communication (where a sender station transmits messages which may be received by a predetermined group of stations), and so forth.

[0011] Reliable point to point communication is established by use of sequence numbers in packets transmitted by a sending station, and by the receiving station transmitting an acknowledgement message (ACK message) or a negative acknowledgement message (NACK message) to the sending station. The sending station maintains a buffer containing messages which it has transmitted, and upon receipt of an ACK message indicating that a packet having a particular sequence number has been received, the sending station flushes that packet from its buffer. In the event that the sending station either receives a NACK message, or does not receive an ACK message during a certain timing period, then the sending station uses its buffer to retransmit the packet. Reliable unicast communication is established by requiring the sending station to retransmit packets until it has received an ACK message for each packet which it transmitted. An example of a reliable unicast protocol is the well known TCP/IP protocol.

[0012] A problem in reliable multicast transmission is that the sending station must respond to ACK or NACK messages transmitted by all of the receiving stations. If there are only a few receiving stations, such as for example ten (10) or so receiving stations, then receiving buffers in the transmitting station can handle the ACK or NACK traffic. However where there are hundreds of receiving stations, or thousands, or millions of receiving stations, the large number of ACK or NACK messages overwhelm the transmitting station.

[0013] It is standard engineering practice in the design of computer networks for a network manager (a person) to use a network management computer program to establish a repair tree for multicast communication. The manager assigns particular stations to be repair head stations for a particular group of receiving stations. The group of receiving stations along with the repair head station are referred to as a “repair group”, with a repair head station and member stations. The repair head stations provide a solution to the problem of too many ACK or NACK messages flooding the sending station by the repair head stations receiving, and reacting to, the ACK or NACK messages transmitted by member stations of their repair group.

[0014] A problem with establishing a repair tree having a plurality of repair head stations in a reliable multicast protocol is that the locations of the member stations may not be optimum for the repair head stations established by the network manager. For example, if the repair head stations are established in the United States, and the member stations are in Europe, Japan, and South America, then retransmitting repair packets is very expensive. And the network manager may not have complete information when he establishes the repair groups, and so he does not realize that he is imposing a very expensive solution on the repair tree.

[0015] Further, a second problem with a network manager establishing a repair tree is that the topology of the repair tree cannot respond to changes in network configuration. That is, in the network links go down, new links are established, routers go down, new routers come on line, etc., and if any of these changes affects to established repair tree, then the repair tree may become inoperative.

[0016] There is needed a method and apparatus to help establish an optimum topological arrangement of a repair tree in reliable multicast transmission, especially when the receiving stations are widely separated, and to establish a simple method for the repair tree to respond to changes in the topology of the network.

[0017] 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.

[0018] 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.

[0019] 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.

[0020] Referring now to the drawings, in which like numerals represent like parts in the several views:

[0021] FIG. 1 is a block diagram of a multicast repair tree in accordance with the invention.

[0022] FIG. 2 is a schematic block diagram of a computer internetwork comprising a collection of interconnected communication media attached to a plurality of stations, including end stations;

[0023] FIG. 3 is a schematic block diagram of a station, such as an end station, configured to operate in accordance with a reliable multicast transport protocol of the present invention;

[0024] FIG. 5 is a schematic diagram of a repair group formed dynamically.

[0025] FIG. 6 is a schematic diagram of a repair group formed dynamically in accordance with the invention.

[0026] FIG. 7 is a schematic diagram of a repair group formed dynamically.

[0027] FIG. 8 is a schematic diagram of a repair group formed dynamically in accordance with the invention.

[0028] FIGS. 9A-9B are schematic diagrams of a network with many stations formed into repair groups, and the diagrams represent a model used for simulation.

[0029] FIG. 10 is a graph of the response of a simulated network.

[0030] FIG. 11 is a graph of the response of a simulated network.

[0031] FIG. 12 is a block diagram of protocol stacks for communication between computers.

[0032] FIG. 14 is a block diagram showing a multicast repair tree.

[0033] FIG. 15 is a block diagram of a multicast tree showing receiver group relationships.

[0034] FIG. 16 is a block diagram of a HState transition diagram.

[0035] FIG. 17 is a block diagram of a multicast repair tree showing improper loop formation during re-affiliation.

[0036] FIG. 18 is a chart showing various messages and sub-messages used in TRAM.

[0037] FIG. 19 is a table showing the timers used by TRAM.

[0038] FIG. 20 is a table showing counters used by TRAM.

[0039] FIG. 21 is a block diagram showing a multicast packet format for a sender Beacon Message.

[0040] FIG. 22 is a block diagram showing a packet format for a Data Message.

[0041] FIG. 23 is a block diagram showing a packet format for a HA Message.

[0042] FIG. 24 is a block diagram showing a packet format for a MS Message.

[0043] FIG. 25 is a block diagram showing a packet format for a Hello Message.

[0044] FIG. 26 is a block diagram of a packet format for a ACK Message.

[0045] FIG. 27 is a block diagram of a unicast packet format for a Hello Uni Message.

[0046] FIG. 28 is a block diagram of a packet format for a Head Bind Message.

[0047] FIG. 29 is a block diagram of a packet format for a Accept Membership Message.

[0048] FIG. 30 is a block diagram of a packet format for a Reject Membership Message.

[0049] FIG. 31 is a block diagram of flag fields for a Sender Beacon Message.

[0050] FIG. 32 is a block diagram of flag fields for a Hello Message.

[0051] FIG. 33 is a block diagram of flag fields for a ACK Message.

[0052] FIG. 34 is a block diagram of flag fields for a Hello-Uni Message.

[0053] FIG. 35 is a block diagram of flag fields for a HA Message.

[0054] FIG. 36 is a block diagram of flag fields for a Data Message.

[0055] Reliable Communication

[0056] The reliability of communication, for example a file transfer comprising a plurality of messages is an important element in computer networking. Reliable unicast communication is established by implementations based upon the concept of a protocol stack. A protocol stack has several levels. At the lowest, or “physical”, layer, a physical connection is established between two computers.

[0057] The physical connection permits hardware in the “physical” layer to exchange signals between two computers. At the next higher layer, the “data link” layer, frames are constructed in accordance with the requirements of the communication protocol used on the physical layer.

[0058] The data link layer provides a best effort, but unreliable, transfer of packets between a sending computer and a receiving computer. Each packet is numbered by a “sequence number” for use by that layer of the protocol for establishing reliable communication.

[0059] The next higher layer, for example in some protocols the “LLC2” layer, in other protocols the “network layer”, and in still other protocols the “transport” layer, permits establishment of reliable communication. In the transmitter a cache of already transmitted packets is maintained, including the sequence number of each. The receiver checks the sequence number of the received packets and determines if any packets are missing. Packets may be missing because of congestion on the network, unreliability of the medium, static on the line, or any one of many possible reasons. In one design, the receiver transmits an acknowledgment (ACK) message to the transmitter indicating that a packet has been received, and also transmits a negative-acknowledge (NACK) message when it determines that a packet with a particular sequence number is missing. Upon receipt of an ACK, the transmitter flushes the packet from a cache (retransmit cache) used for re-transmission of lost packets. Upon receipt of a NACK, the transmitter then queues the packet from its retransmit cache and retransmits the packet. The transmitter continues to wait for receipt of an ACK before flushing the packet from its retransmit cache. Some protocols use a time-out period with a timer rather than using ACK and NACK messages to signal that a packet should be retransmitted. Some protocols establish reliable communication on every hop of a communication pathway, and some do not.

[0060] Protocols used for reliable unicast message transfer are more fully described by Douglas E. Comer in the book Internetworking with TCP/IP, Volume I, and also Volume II, published by Prentice Hall, Englewood Cliffs, N.J., in 1991, all disclosures of which are incorporated herein by reference. The IP portion (Internet Protocol) of the TCP/IP protocol is a layer 3 protocol, and is used to establish unreliable transfer of messages between end stations, for example across the Internet. Layer 3 handles addressing, routing, etc. The TCP portion of TCP/IP (The Connection Protocol) is a layer 4 protocol and establishes reliable communication between the end stations by causing retransmission of packets using the IP protocol.

[0061] In a commonly used terminology, the words “datagram” and “message” are often used interchangeably. In an alternative usage, a “message” may be broken into one or more “datagrams”. However, in this document the words “datagram” and “message” and “packet” are used interchangeably. A “frame” is used as the messaging unit transferred by the physical layer on a hop between two computers.

[0062] Unreliable multicast communication is relatively simple to implement, as the source station simply transmits the datagrams with an address that the designated computers can recognize as a multicast address, and which routers forward. The destination stations then receive any datagrams which they detect. No attempt is made to either identify or retransmit lost datagrams.

[0063] Reliable multicast is more difficult to implement. For example, in the case of a few destination computers, the source station must maintain a record of the ACK messages received from each intended destination station so that a datagram missing from any one of the destination stations can be retransmitted. However in the case where there are tens of thousands, even millions, of intended destination stations, the large number of ACK messages will flood the source station and will flood the network. The detrimental effect of too many ACK and too many NACK messages is referred to as ACK implosion or NACK implosion. Administration problems also arise, where for example, a source station has a particular destination station on its list of intended destination stations, and for some reason that destination station is no longer operational. The source station may then continue indefinetly retransmitting messages while waiting for an ACK from the missing station.

[0064] One solution to the reliable multicast problem, where the multicast message is to is be received by a group of destination computers, has been to have an administrator (a person or a computer program operated by the person) set up a repair tree. In a repair tree, certain computers are designated as a “repair head”. The rest of the computers of the group of destination computers are assigned to a designated repair head. Typically, a source station transmits a multicast datagram onto the network. The datagram should be received by all members of the destination group. Since the datagrams carry a sequence number, each destination station determine if it has missed a datagram. Each station sends an ACK to its repair head upon successful reception of a window of datagrams, and sends a NACK to its repair head upon determining that it has missed a datagram. Upon receipt of an ACK from every member of its repair group, the repair head flushes the datagram from its cache. The repair head retransmits any datagram for which it receives a NACK, until all members of its repair group respond with an ACK for each datagram.

[0065] In the event that a repair head is missing a datagram, it NACKs to the source station, and the source station retransmits the datagram. The source station maintains a cache of transmitted datagrams and flushes them after receipt of an ACK from each of the repair heads affiliated with the original source station.

[0066] Congestion on the network can result from large numbers of ACK and NACK messages. Particularly, a destination station which is slower than the transmitting source station will miss many multicast datagrams. The resulting NACK messages can cause a NACK implosion and contribute to network congestion. Upon receipt of a NACK message, a source station or repair head will begin retransmission of datagrams, thereby contributing to even more congestion. Congestion can particularly increase when a low bandwidth link is responsible for a number of destination stations being slower than the source station. Each destination station will miss numerous datagrams, and will flood the network with NACK messages, followed by more retransmission in a feedback cycle which increases congestion.

[0067] First Exemplary Embodiment

[0068] Turning now to FIG. 1, there is shown a multicast repair tree 100. Sender station 102 is transmitting a multicast message to the other stations shown in FIG. 1. Communication path 104 represents the fact that sender station 102 transmits a message having a multicast address, and this message is received by all of the addressed stations, 110-1, 110-2, . . . 110-N directly from sender station 102. Communication path 104 may include, physically, many hops through many physical networks. Communication path 104 simply represents that the destination stations receive the multicast message directly from sender station 102.

[0069] During operation, sender station 102 first transmits a beacon message with the multicast address of the intended destination stations for the multicast message. The beacon message alerts the destination stations that they should arrange themselves into a hierarchical multicast repair tree (repair tree hereinafter) in preparation to receiving the multicast message so that the message can be reliably received by all destination stations. FIG. 1 represents the situation after the repair tree has been formed. The method of formation of the repair tree will be fully disclosed hereinbelow.

[0070] During operation of the dynamically configured multicast tree protocol, sender station 102 transmits beacon messages in order to assist in establishing the repair tree 100. Beacon messages transmitted by sender station 102 are also used in management of congestion control in the repair tree.

[0071] Destination station 110-4 is selected to be a repair head by the tree forming process, either static or dynamic. Destination stations 110-1, 110-2, 110-3, and 110-4 form a repair group 115. Repair head 110-4 caches messages received from sender station 102, and repair head 110-4 transmits ACK messages to sender station 102 along path 120 as numbered messages are successfully received by repair head 110-4. Sender station 102 maintains a cache of messages which it has transmitted, and maintains a log of ACK messages received from various repair head stations so that it can clear a message from its cache after ACK messages have been received from all repair head stations, as will be more fully described hereinbelow.

[0072] Path 104 represents the multicast path where data, retransmission and beacon messages, flow. Paths 120, 122, 124 and 126, etc. represent unicast flows of ACK and congestion messages.

[0073] Repair head 110-4 receives ACK messages from the destination stations in its repair group 115, including destination station 110-1 along path 122, destination station 110-2 along path 124, and destination station 110-3 along path 126. Repair head 110-4 maintains a cache of messages transmitted by sender station 102, and upon receipt of ACK messages from all of the member stations of its repair group, deletes the message from its cache.

[0074] Repair group 115 is illustrated in FIG. 1 as having four (4) members, receiver members 110-1, and 110-2, and 110-3, designated by an “M”, and also repair head 1104. A repair head may have many members in its repair group.

[0075] In this way, repair head 110-4 acts to receive the ACK messages from members of its repair group 115, and “repairs” missing messages transmitted by sender station 102 to destination stations 110-1, and 110-2, and 110-3 of its repair group 115. By “repairing”, that is by retransmitting missing messages, repair head 110-4 provides reliable multicast communication from sender station 102 to members of repair group 115.

[0076] Repair group 117 has as members stations 110-5, and 110-6, and 110-7, and 110-18, with member station 110-7 being the repair head. Repair head 110-7 caches messages received from sender station 102 and transmits its ACK messages to sender station 102 along path 130. Sender station 102 then re-transmits a message for which it receives a NACK from repair head 110-7. Ordinary members of repair group 117 transmit their ACK messages to repair head 110-7: station 110-5 along path 132, station 110-6 along path 133, and station 110-18 along path 135. Repair head 110-7 maintains a cache of all messages transmitted by sender 102, and deletes the messages as soon as an ACK is received from each of the member stations of repair group 117.

[0077] Repair group 119 illustrates a second level in the repair tree hierarchy. Station 110-18 is a member of repair group 117. Station 110-18 is also a repair head for repair group 119. Repair group 119 has members 110-18, its repair head, and also station 110-8, station 110-9, and station 110-10. Repair head station 110-18 maintains a cache of messages transmitted by sender station 102. Any messages missed by repair head station 10-18 are repaired by use of path 135 for sending ACKs (NACKs) to its repair head 110-7. Repair head station 110-18 receives ACK messages from member stations: station 110-8, station 110-9, and station 110-10, and when an ACK has been received from all member stations of its repair group, repair head station 10-18 deletes the message from its cache.

[0078] Similarly, repair group 140 has repair head 110-13 with additional member stations 110-11, station 110-12, and station 110-14. Repair head station 110-13 transmits its ACK messages to sender station 102, and so is in the first level of the hierarchical multi-cast repair tree.

[0079] Station 110-14 is also a repair head station for repair group 150, and so is a second-level repair head station.

[0080] Member station 110-17 of repair group 150 is also a repair head station for repair group 160, and so is a third-level repair head station in the repair tree hierarchy.

[0081] With a repair head hierarchy, the ACK messages are distributed among a plurality of repair head stations. The number of members of each repair group are limited so that each repair head station can handle the ACK messages, and can also handle the retransmission of messages for which NACK information is received. No “ACK implosion” and no “NACK implosion” occur, both because the repair work is distributed over many computer stations, and congestion and flow control prevent excessive packet loss, and so reliable multicast communication is established.

[0082] Congestion and Flow Control

[0083] The invention avoids an ACK implosion by spreading out the ACK (and NACK) messages so that a flood of them do not reach the repair head simultaneously. The use by members of the ACK window for timing of transmission of the ACK messages helps to prevent too many ACK messages from reaching the transmitting station at the same time. The ACK messages contain both acknowledgment information for packets received by the member station, and contain NACK information for packets not received by the member station, as based on the sequence numbers of the packets. The term “ACK message” will be used throughout this patent to indicate a message returned by a receiving station to a transmitting station, where the message carries both ACK and NACK information.

[0084] The ACK window is defined for a multicast session by establishing the number packets which make a full sequence of ACK windows. Receipt of a full window of packets is an event which triggers transmission of an ACK message by a member station. In a preferred embodiment of the invention, the ACK window size is configurable, and the default number of packets which make a full sequence of ACK windows is thirty two (32) packets.

[0085] To prevent many member stations from sending ACK messages at the same time, ACK messages are distributed over the next ACK window. Each member is assigned a window (for example between 1 and 32) for sending its ACK messages. For example, one member may send ACKs after receiving messages 32, 64, 96; etc., while another sends ACKs at messages 10, 42, 74, etc. The ACK messages may be sent as the next window of packets are being received, because at the levels of the protocol stack at which the invention operates, communication is full duplex.

[0086] In an exemplary embodiment of the invention, acknowledgments are also sent if an ACK timer counts up to, for example, greater than 1.5 times an estimated ACK interval. The estimated ACK interval is computed at each receiver when an ACK is sent. The estimated ACK interval estimates the amount of time it takes to receive an ACK window's worth of messages. The formula is:

[0087] ACKinterval=ACKwindow*(Time since last ACK/Packets since last ACK)

[0088] If this timer expires, it indicates that the sender has paused and allows members to report and recover any lost packets without having to wait for the sender to start sending new data.

[0089] The ACK message format which both reports NACK information (that is, packet loss information) and acknowledgment information (ACK information) uses a bit map length field. Each ACK message contains the bit map length field and a start sequence number. If no packets were missing, the bit map length is “0” and the sequence number indicates that all packets prior to and including this packet were successfully received. The repair head saves this information and uses it to flush packets from its cache.

[0090] If there are one or more missing packets, the start sequence number indicates the first missing packet. A bit map must follow. Each bit in the map represents a packet sequence number starting with the start sequence number. If the bit is set, for example, that packet is missing and must be retransmitted.

[0091] When the repair head receives an ACK message with a missing packets bit map, the sequence number specified minus 1 is saved for this member. This indicates that all packets prior to and including this sequence number have been received successfully. The repair head then scans the bit map looking for missing packets. It immediately places these packets onto the transmit queue unless they have recently been retransmitted or are already on the queue from another request. Missing packet retransmission receives first priority in the transmission queue, so that packets may be flushed from the transmitter cache.

[0092] Also, in accordance with the invention, the cache buffers in the source station, and in the repair head stations, hold packets which have been transmitted but for which an ACK has not yet been received. It is necessary to prevent overflow of this buffer, and accordingly, the “fill level” of this buffer is monitored. A threshold is assigned for the fill level. When the threshold for the fill level is exceeded, the sender station stops sending packets and waits for ACK messages so that it can flush acknowledged packets from its buffer. This wait is a pause in the transmission of packets, and causes the ACK timer in members to expire, and the members then to transmit an ACK message.

[0093] Also, in accordance with the invention, the transmission rate of packets by the source station, and by the repair head stations, is dynamically adjusted. Adjustment of the transmission rate of packets is accomplished by causing the sender station to pause between transmission of packets, so that the average transmission rate of packets will have a desired value. The transmission rate should be high so as to fully use the band-width of the network, and should be sufficiently low that packets are not lost due to congestion, or to the inability of a receiver station to keep up with the transmitter. Since the bandwidth of the network is unknown, the sender station starts transmitting at an assigned minimum rate, and then starts increasing the rate by adding an increment to its transmission rate at the occurrence of selected events (additive increase). In a preferred embodiment of the invention, the selected event is the transmission of a full set of windows of packets.

[0094] Upon receipt of an ACK message indicating that packets have been lost, the transmitting station reduces its transmission rate by multiplying its current rate by a fraction, for example 0.25 (multiplicative decrease). By using an additive increase along with a multiplicative decrease, the transmission rates of each of the transmitting stations adjusts itself to an optimum rate for its network, and its receiving stations.

[0095] Accordingly, a transmitting station has a “slow start”. That is, the transmitting station begins transmission at a “slow” or minimum rate of packet transmission and slowly increases its rate by “additive increase” until it receives notice that packets are being lost, at which time the transmitting station reduces its transmission rate. After the reduction, the station again begins increasing its transmission rate. The transmission rate therefore oscillates, and attempts to fully utilize the bandwidth of the network.

[0096] A key point about the slow start phase of the multicast transmission session is that the historical high rate is established as the maximum rate for which packets were not lost.

[0097] A further feature of the invention in retransmission operation is to avoid duplicate retransmission. Whenever an ACK message indicates that a packet must be retransmitted, first a check is done in order to determine if that packet is already in the transmit queue. If the packet is already in the transmit queue, the new ACK request is ignored.

[0098] Stable system operation is achieved by the invention. In accordance with the invention, synchronization between feedback, from reading ACK messages, and control in increasing or decreasing the transmission rate, is maintained in order to achieve stable system operation. Synchronization is maintained by requiring the transmitting station to immediately decrease the rate after receiving feedback which indicates congestion. The station is then required to wait for a number of windows before implementing either another decrease or an increase in rate. This wait permits the effect of the change to be felt throughout the network, and for the most recent feedback to be in response to that change.

[0099] Pruning of receiving stations from the multicast network is done when a station gives evidence that it cannot keep up with the transmitting station when it is operating at its minimum transmit rate. Evidence that a station cannot keep up appears at the transmitting station as an excessive number of retransmission requests. When the number of retransmission requests becomes excessive, the offending station is dropped (that is, pruned) from the multicast tree.

[0100] A still further feature in accordance with the invention is that an “end of packet” beacon frame is transmitted by the source station after all packets of the multicast transmission sequence have been transmitted. This “end of packet” beacon frame informs the various stations of the sequence number of the last packet, so that retransmission requests can be appropriately formulated.

[0101] Second Exemplary Embodiment

[0102] Communications

[0103] FIG. 2 is a schematic block diagram of a computer internetwork 200 comprising a collection of interconnected communication media attached to a plurality of stations. The communication media may be configured as local area networks (LANs) 210 and 220, although other media configurations such as point-to-point network links may be advantageously employed. The stations are typically computers comprising source and destination end stations 302, 312, such as personal computers or workstations, and intermediate stations 320a-esuch as routers, bridges, switches and/or firewalls. Communication among the stations is typically effected by exchanging discrete data frames or packets between the communicating nodes according to a predefined protocol, such as the Internet protocol (IP), Internet Packet Exchange protocol, AppleTalk protocol or DECNet protocol.

[0104] FIG. 3 is a schematic block diagram of a station, generally designated 300, configured to operate in accordance with the invention. The station may comprise any type of station, such as an end station, that is capable of advantageously sending and/or receiving data frame/packet messages in accordance with the protocol of the present invention. The station generally comprises a plurality of interconnected elements, such as a processor 302, a memory 304 and a network adapter 306. An operating system 310, portions of which are typically resident in memory and executed by the CPU, functionally organizes the station by, inter alia, invoking network operations in support of software processes 320 executing on the station.

[0105] The memory may comprise storage locations addressable by the processor and by the adapter for storing software programs and data structures associated with the inventive multicast transport protocol. The processor is typically a central processing unit (CPU), although it may generally comprise processing elements or logic configured to execute the software programs and manipulate the data structures. It will be apparent to those skilled in the art that other processor and memory means, including various computer readable media, may be used for storing and executing program instructions pertaining to the techniques described herein.

[0106] An exemplary embodiment of the invention is referred to as the Tree based Reliable Multicast protocol, or TRAM model as a shorthand.

[0107] Broadly stated, the inventive multicast transport protocol (TRAM) utilizes a hierarchical tree-based multicasting system for transferring identical data from a single sender to multiple receivers (clients). The sender and receiving clients in a multicast session interact with each other to dynamically form repair groups. The repair groups are linked together in the hierarchical tree with the sender at the root of the tree. Each repair group has a receiver that functions as a group head for other receiving clients in the tree. Except for the sender, each repair group head in the system is a member of another repair group.

[0108] Group members report lost and successfully received messages to their associated group head using a selective acknowledgment mechanism. The repair heads store (“cache”) every message received from the sender, and provide repair services (i.e., re-transmission) of messages that are reported lost by the members. Features are also provided to permit the tree structure to adapt depending upon the changes that may occur in the network during the multicast session, so as to permit optimal multicasting during the session.

[0109] To dynamically construct the tree, the system utilizes a “top-down” approach wherein the tree begins formation from the sender. That is, the sender starts accepting client members for its own repair group, and each receiving client, upon becoming a member of a repair group, may start to form its own respective repair group. Every receiving client has to be a part of the tree in order to form a repair group of its own. Advantageously, this top-down approach guarantees caching of data somewhere in the tree hierarchy, because repair heads accept members in their respective repair groups only after attaching to the tree.

[0110] In order to attach to the tree, a receiving client discovers a repair head that can accept the receiving client as a member of the repair head's repair group. This may be accomplished most efficiently from the standpoint of network resource usage by periodically multicasting from receiving clients an advertisement message that the receiving client issuing the multicast message is seeking a repair head with which to become associated. Alternatively, current repair heads in the system may periodically multicast an advertisement message to solicit new members.

[0111] The tree system may be constructed in networks supporting only unidirectional multicast, bi-directional multicast, combinations of uni-directional and bi-directional multicasting, and local area network (LAN) environments. Tree construction is initiated by the sender multicasting either a periodic beacon message or data to the multicast group using the multicast session time-to-live (TTL) scope. Advertisement messages from the repair group heads seeking client members, and/or receiving clients seeking repair head advertisement are multicast using an expanding ring search (ERS) mechanism. Receiving clients affiliate themselves with the closest repair head.

[0112] Each repair head monitors the operation of the members of its respective repair group to ensure that the members are functioning properly. Likewise, each of the members of a given repair group monitor the operation of the repair head associated with that group to ensure proper functioning of the head. If a repair head determines that a member of its group is no longer functioning (e.g., as a result of failure of the member to acknowledge receipt of special monitoring messages after a predetermined number of messages have been transmitted and/or a predetermined time period for response has elapsed), the repair head may prune that member from its group.

[0113] Similarly, if a member of a repair group determines that the current repair head that it is associated with is no longer functioning properly (e.g., if the member does not receive special monitoring messages from the head), the member may seek to re-affiliate itself with a different repair head that it has learned of as a result of receipt of monitoring messages from that different head. The members of the group may also re-affiliate themselves with a different repair head if the current repair head with which they are associated resigns from being the repair head for that group. Such resignation may occur if the repair head determines that it is redundant in the region of the system in which it resides.

[0114] Optimization of Reliable Multicast Repair Trees

[0115] As noted, it is often useful to use IP multicast to disseminate data to a large group of receivers on a data network. However, any number of data messages may be lost in transit due to errors or overloading of networking equipment. Ensuring that each member of such a group has received all of the data is difficult for a single sender to determine once the group is of any size, since messages from each member to the sender can over-load the sender. Organizing the members of such a group into a tree structure for aggregation of this information is a scaleable way to avoid this problem.

[0116] In accordance with an aspect of the invention, optimization features are provided for organizing the members into a tree. Broadly stated, selected members of the receiver group are designated to be heads. Each head is responsible for ensuring that the set of members assigned to it receives all of the data. Heads also propagate information about the tree back to the sender, such as congestion information, reception information, and number of members.

[0117] Repair trees for reliable multicast are generally constructed once, at the beginning of or in advance of a multicast transmission. While these trees may be optimal at the time of construction, they may become suboptimal as time goes on and conditions change. No matter which criteria are used to construct a tree, changes in the composition of the group as well as the underlying network infrastructure may make a change in the tree structure desirable to keep it optimal.

[0118] For example, if all receiving clients are densely located in one network region (e.g., an intranet with relatively few hops in-between the sender and receivers), it may become difficult to form repair groups that have a low degree of membership overlap. In this situation, an optimal construction of the tree has as few repair heads as possible. In order to carry this out, an existing head may assume the duties of another head to thereby reduce the number of active heads. This can be initiated either by members of the retiring head or by the retiring head itself.

[0119] In some cases, it may be desirable to form a sparse tree wherein the number of members in each repair group is minimized. In order to carry this optimization out, members of a given group whose membership exceeds a predetermined maximum threshold may be directed to affiliate themselves with another repair head. Once again, this optimization may be initiated either by the members themselves or by the current head with which they are affiliated. Alternatively, if it is determined that another head with which a member is currently not affiliated is closer to that member than the current head with which the member is affiliated, the member may become affiliated with the closer head.

[0120] This aspect of the invention describes the following ways of optimizing existing repair trees:

[0121] A dense tree may be desired in which the number of internal nodes (heads) is to be kept to a minimum.

[0122] A closely-knit tree may be desired in which a node chooses a head that is as close to it as possible.

[0123] A sparse tree may be desired in which the number of members for each head is kept to a minimum.

[0124] In the case of the dense tree, an existing head may be able to take over the duties of another, optimizing the tree by reducing the number of active heads by one. This optimization can be instigated by either members of the extraneous head, or by the extraneous head itself. In a first case, a member of Head1 may notice another head, Head2, which has more members than Head1. The member learns of Head2 by overhearing its multicast messages. The member subsequently changes its affiliation to Head2. In a second case, a head, Head1, may notice a more optimal head, Head2, and direct Head1's members to use Head2 instead. Once Head1 no longer has any members, it can discontinue its head duties. Both of these methods guarantee a convergence of the tree to the to fewest number of heads possible. For instance, if members of a group are concentrated on local area networks, it is efficient to have a minimal number of heads per LAN, assuming that all of the receivers on each LAN will share the same loss experience.

[0125] In the case of a sparse tree, members may be directed to new heads in order to off-load existing ones. This optimization can be instigated by either members of the overloaded head, or by the overloaded head itself. In the first case, a member of Head1 may notice another head, Head2, which has fewer members than Head1. The member learns of Head2 by overhearing its multicast messages. The member subsequently changes its affiliation to Head2. In the second case, a head, Head1, may notice a less loaded head, Head2 and direct some of Head1's members to use Head2 instead. Both of these methods guarantee a convergence of the tree to one in which the number of members for each head is kept to a minimum. This type of tree is useful if most of the members have little capacity to act as heads.

[0126] In both the dense tree and the sparse tree cases, reaffiliation of a receiver station is based on the number of receiver stations served by the repair head station. In the dense tree situation a receiver station reaffiliates with a repair head station having a greater number of member stations in its repair group in order to reduce the number of repair head stations. In contrast, in the sparse tree situation a receiver station reaffiliates with a repair head station having a smaller number of member stations in its repair group in order to balance the repair work among the repair head stations. In both the dense tree and the sparse tree cases the number of member stations served by a repair head station is determined by the TOTAL MEMBER COUNT field of the Hello Message of FIG. 25, or the DIRECT MEMBER COUNT field of the HA Message of FIG. 23. Either a receiver station can read the Hello Messages and HA messages which it receives from all repair head stations, or a repair head station can read these fields in the messages it receives from other repair head stations.

[0127] In the case of the closely-knit tree, changing network conditions or a new group member may result in a new head that is closer to a particular member. This optimization can only be instigated by members of the now suboptimal head as follows: a member of Head1 may notice another head, Head2, which is closer than Head1. The member learns of Head2 by overhearing its multicast messages. The member subsequently changes its affiliation to Head2. This method guarantees a tree in which members are as close to their heads as possible. This type of tree best suits a group in which most members are not generally co-located.

[0128] The distance between a receiver station and a repair head station is calculated in terms of the number of routers which have forwarded the message as the message travels from the repair head station to the receiver station. The distance is calculated by a receiver station in response to an initial TTL value carried in field TTL SCOPE of Hello Messages or in field TTL DISTANCE of HA Messages of FIG. 23, and a decremented value of TTL read from the IP header of the message. Subtracting the decremented value read from the IP header from the initial value carried in the field of the Hello Message or the HA Message gives the number of routers which have forwarded the message, and therefore the distance between the repair head station and the receiver station.

[0129] Congestion Detection and Feedback

[0130] The flow and congestion control mechanism is generally rate-based and adjustable, based upon network congestion. That is, the transmission rate of multicast data packets is dynamically adjusted based upon the rate at which the receiving clients can accept and process the data packets. A pruning mechanism is also provided whereby receiving clients that are unable to receive and process the data packets at a minimum threshold rate are removed from the tree system.

[0131] For example, each multicast data packet transmitted from the sender includes a unique sequence number. Receiving clients utilize these numbers to detect out-of-order and missing packets, and to request transmission of same from the repair head with which it is associated. Each of the repair heads maintains a cache of multicast packets received from the sender and flushes the packets out of the cache after receipt of the cached packets by all of the members of its repair group has been acknowledged. In order to avoid multiple members sending such acknowledgment messages at the same time, and to expedite repair, each member of a repair group selects a random packet between one and a predetermined acknowledgment window size to begin transmission of acknowledgment messages. Using a single acknowledgment message for each respective acknowledgment window, the members acknowledge those packets of that window that have been received and not received. Each repair head computes the average data rate of all packets it receives, and sends retransmissions to the members of its group at this rate.

[0132] Congestion is detected at the receiving clients and repair heads, and is used to dynamically adjust transmission rate of packets in the system. More specifically, the receiving clients transmit congestion messages to their repair heads based upon changes in the number of data packets that the receiving clients failed to receive between the preceding two acknowledgment windows. When the repair head receives these congestion messages, it generates a congestion message for each acknowledgment window and forwards that message to its own repair head. Each repair head also generates congestion messages when its data cache (i.e., for retransmission purposes) equals or exceeds a predetermined maximum fill level. The repair head may also adjust upwardly its maximum cache fill level, if possible. The sender adjusts its data transmission rate based upon the congestion it receives as well as its own cache fill level for its immediate group members, while staying within predetermined minimum and maximum data transmission rates.

[0133] More specifically, in an exemplary embodiment of the invention, the sender increases transmission rate every second acknowledgment window in the absence of congestion reports. When a congestion report is received, the sender immediately reduces transmission rate and records the window for which the congestion report was generated, and thereafter, the sender does not further adjust transmission rate until a predetermined number N of acknowledgment windows have transpired, wherein N is proportional to the current data transmission rate divided by the historically highest achieved transmission rate.

[0134] After each rate decrease, the next increase in transmission rate is equal to the historically highest achieved rate minus the current data transmission rate, divided by a number, for example 4. After receipt of a congestion report, the sender reduces its data transmission rate by a predetermined percentage (e.g., 50% or 25%) of current data transmission rate. The sender's data transmission rate never exceeds, and never falls below, respective predetermined maximum and minimum thresholds.

[0135] The sender notifies all members of the session when it has completed data transmission by transmitting a beacon packet that includes the sequence number of the last data packet transmitted. The sender retransmits this packet periodically until all of the members of its immediate repair group have acknowledged receipt of all packets sent.

[0136] When a member receives the beacon packet, it immediately sends an acknowledgment to its repair head indicating whether it has received all of the packets transmitted, or requires packet retransmission. If the beacon from the sender is received, but a member has not acknowledged receipt of all data packets, a monitoring message is transmitted from the repair head associated with that member. If the member does not acknowledge receipt of such message to the repair head sending the monitoring message, the repair head may retransmit the monitoring message. If, after a predetermined number of retransmissions of the monitoring message, the member has still failed to acknowledge receipt, the repair head prunes the member from the tree. When all members have either acknowledged receipt of all data packets to the repair head or have been pruned from the tree, the repair head terminates its session.

[0137] Third Exemplary Embodiment

[0138] General Discussion of the Hierarchical Repair Tree

[0139] The TRAM model is tree-based. The tree formation process is dynamic. The TRAM tree formation algorithm works in both bidirectional multicast environments and unidirectional multicast environments (such as satellite links) with unicast-only back-channels. Repair nodes are elected based on a wide spectrum of criteria, and the tree is continuously optimized based on the receiver population and network topology. The ACK reporting mechanism is window-based, including optimizations to reduce burstiness and processing overhead. The flow control mechanism is rate-based and adapts to network congestion. The sender senses and adjusts to the rate at which the receivers can accept the data. Receivers that cannot keep up with a minimum data rate can be dropped from the repair tree.

[0140] Some of the major features of TRAM are:

[0141] Reliability

[0142] TRAM guarantees delivery of data to any receiver that joins the tree and is able to keep up with the minimum transmission speed specified by the sender. While this level of guarantee cannot ensure applications against delivery failure, features can be used to closely keep track of individual members' status.

[0143] Avoiding Acknowledgment Implosion

[0144] Point-to-point transports achieve reliability by acknowledging receipt of data directly to the sender. Unfortunately this does not scale over multicast. A sender trying to field acknowledgments from many receivers will quickly become overloaded. TRAM avoids this implosion by dynamically designating a receiver to be a repair head for a group of members. The repair head fields acknowledgments from each of its group members and supplies them with repair packets. To avoid overload, each repair head is responsible for only a limited number of members.

[0145] Local Repair

[0146] TRAM builds the tree so that repair heads are close to their members. A frame or message usually carries a “time-to-live” indication in its header which was written by the source station which transmitted the message onto the network. Upon expiration of the time-to-live value the message will no longer be forwarded by routers or other hardware of the network. The “time-to-live” is measured, in this document, by hop count. For example, if the time-to-live has the value of “2”, the message will be forwarded for only two (2) hops. Alternatively, if the time-to-live has a value of “4”, the message will be forwarded over four (4) hops in the network. Use of a time-to-live designation in message headers enables repair heads to perform repairs using small time-to-live (TTL) values, which not only minimizes network bandwidth consumption but also avoids unnecessary processing at receivers not requiring repair.

[0147] Automatic Configuration

[0148] Different applications, networks, or user groups may perform better using different types of trees. TRAM provides for building different types of trees optimized for these different circumstances without adding complexity to the network infrastructure itself. As a receiver group changes, TRAM also provides for ongoing optimization of an existing tree. For instance, a member is enabled to find a better repair head. A particular tree's formation method may also be changed at any time during the transmission at the discretion of the sender. TRAM's tree management works in networks providing only unidirectional multicast, as well as those supporting bidirectional multicast.

[0149] Rate-based Flow Control and Congestion Avoidance

[0150] TRAM schedules packet transmission according to a data rate. This data rate is dynamically adjusted based on congestion feedback from the receivers. Congestion feedback is aggregated by repair heads through the tree. The algorithm used to adjust the rate works in different network topologies. The rate is bounded by maximum and minimum rates configured at the sender station.

[0151] Feedback to the Sender

[0152] Each member of the tree periodically reports statistics to its repair head. This includes statistics that assist in building the tree in dynamic tree embodiments of the invention (for instance, the number of available repair heads on the tree) as well as reports on congestion conditions. Reports on congestion conditions from repair heads allow the sender to adapt its data rate to network conditions. This information is aggregated at each level of the tree in order to reduce control traffic to the sender.

[0153] Controlling Memory Use

[0154] Each repair head is responsible for ensuring that the data is received by all of its members. This means that a repair head must cache data until it is sure that all of its members have received it. TRAM requires positive acknowledgments from members when data is received. This enables repair heads to reclaim cache buffers containing data that has been received by all members.

[0155] Repair Group Management

[0156] Both members and repair heads monitor each other to detect unreachability. Non-responsive members can be dropped from the repair group and corresponding cache buffers can be reclaimed. Non-responsive repair heads can be abandoned by their members in favor of an active repair head. Repair heads are also responsible for detecting receivers which cannot keep up with the minimum transmission rate specified by the sender. While such members cannot be dropped from the multicast group, they can be denied repair head support and receive no repairs.

[0157] Scalability

[0158] TRAM has been designed to be scalable in many situations, such as large numbers of receivers and sparsely or densely populated receiver groups. TRAM also accommodates wide ranges of receiver capabilities. Control message traffic is designed to be limited in all of these cases.

[0159] Tree Formation and Management

[0160] FIG. 4 shows a typical hierarchical repair tree of TRAM with repair heads caching the multicast data sent by the sender and performing localized repairs to their group members.

[0161] A hierarchical repair tree can be constructed using either a top-down or a bottom-up approach. In the top-down approach, the tree begins to form from the sender. That is, the sender will first start accepting members for its repair group and each receiver upon becoming a member of some group can start to form its own repair group. A receiver has to be part of the tree to form a repair group of its own.

[0162] In the bottom up approach, the receivers can independently start forming their own repair groups even before attaching to the tree.

[0163] The top-down approach guarantees caching of data somewhere in the tree hierarchy because the repair heads accept members only after attaching to the tree. The same level of guarantee cannot be achieved with the bottom-up approach, as a repair head that is still unattached may receive repair requests for data for which the repair head itself needs to seek repair. The data guarantee as stated here assumes the use of an acknowledgment-based mechanism to manage the data cache. Repair groups may be formed more quickly using the bottom-up approach due to parallelism. TRAM primarily uses the top-down approach, but incorporates the advantages of the bottom-up approach in its optimization for LANs.

[0164] Tree Construction Techniques Supported In TRAM

[0165] To dynamically construct the repair tree, a protocol has to have mechanisms to enable receivers to attach and detach from the tree. Since TRAM uses the top-down approach, a receiver has to first attach to the tree before it can form its own repair group. In order to attach to the tree, a receiver has to discover a repair head that can accept it as its member. The discovery process can be done in one of two ways:

[0166] (1) the current repair heads in the system periodically multicast an advertisement message to solicit new members, or

[0167] (2) the receivers that are seeking a repair head multicast a periodic advertisement message.

[0168] From an efficiency and network resource usage standpoint, the second option is more attractive because the advertisements occur only when there are receivers that are seeking a repair head and will stop when all the receivers in the system are attached to the tree. The major disadvantage of the first option is that head advertisements have to persist for the entire multicast session as repair heads have no way of discovering that all receivers have attached to the tree. The only disadvantage of the second option is that it requires the underlying network to support bidirectional multicast service.

[0169] It is possible to have a configuration in which there is no guarantee of multicast support from every receiver back to the sender. But there is enough support for any member to find a head using the second option.

[0170] To be flexible and independent of network-related constraints, TRAM supports the following tree construction techniques:

[0171] Repair tree construction when the network supports only unidirectional multicast.

[0172] Repair tree construction when the network supports bi-directional multicast.

[0173] Combination of unidirectional and bi-directional multicast tree construction techniques.

[0174] Repair tree construction when, multiple receivers are on a LAN (LAN-based Tree Formation). This method can be used locally on a LAN, with any of the above methods used to connect the LAN tree to the rest of the group.

[0175] Some of the generic policies governing the tree construction process in TRAM are:

[0176] 1. The repair tree construction process is initiated by the sender by multicasting either a periodic control message (called the beacon message) or data to the multicast group using the session TTL scope.

[0177] 2. The advertisement messages (the head seeking member advertisement and the receiver seeking head advertisement) are multicast using the Expanding Ring Search (ERS) mechanism. The ERS mechanism is used to control the scope of these messages. TRAM allows the maximum value of this scope to be limited in order to control advertisement traffic.

[0178] 3. Receivers affiliate with the closest repair head. Closeness is determined by the shortest TTL distance from the repair head to the receiver. This policy promotes localized repairs.

[0179] Other prioritizations of parameters, such as round-trip time, or tree level, result in the formation of different kinds of trees. For instance. a repair head may be chosen based on its proximity to the sender.

[0180] 4. Each repair head maintains a repair TTL that is large enough to reach all its members.

[0181] 5. The repair heads in TRAM have to cache the received multicast data messages, perform repairs, and also process acknowledgments from the group members. Not every receiver in the system may be suitable to perform this role. A receiver may be unsuitable for reasons relating to hardware, software, resource limitations, or administrative restrictions. TRAM allows receivers to be configured with the following preferences:

[0182] EagerHead.

[0183] ReluctantHead.

[0184] MemberOnly.

[0185] An EagerHead will attempt to form its own repair group upon attaching itself to the tree. A ReluctantHead will also attempt to form its own repair group; however, the rules of repair head selection will prevent it from attracting members unless no eager repair heads are available. Note that the default value for receiver preference is ReluctantHead; this allows a tree to be formed without specifically configuring a receiver preference for each member. A MemberOnly receiver will never attempt to perform the role of a repair head.

[0186] 6. The sender of the multicast session is an EagerHead and is always considered to be part of the tree.

[0187] 7. To reduce the processing load on repair heads, TRAM supports mechanisms to restrict the number of members that an individual repair head can accept.

[0188] Repair Tree Construction Under Unidirectional Multicast

[0189] There are many existing networks that support multicast with some restrictions. These restrictions can be either technological (hardware or software limitations) or administrative in nature. A typical administrative restriction can be a network that is configured to forward incoming multicast messages and discard all outgoing multicast mess ages originating within the network. Constructing a dynamic repair tree with multicast restrictions can be tricky and complex. The following tree construction technique is adopted by TRAM when the underlying network has only unidirectional multicast.

[0190] All receivers tuned to the multicast group are inactive until the sender initiates the tree formation process. The sender triggers the process by multicasting either the beacon or data. Data as-well as beacon messages contain the HeadAdvertisementInterval information. The HeadadvertisementInterval specifies the rate at which Headadvertisement messages are to be sent out by the affiliated repair heads in the system. The sender alters the HeadAdvertisementInterval as the number of advertising repair heads in the system changes. This restricts the HeadAdvertisement traffic to a constant bandwidth. The number of advertising repair heads in the system is propagated up in the tree hierarchy and is made available to the sender. The sender computes the HeadAdvertisementInterval using the following formula

[0191] HeadAdvertisementInterval=max(½ second, AdvertisingHeadCount*HASize/MaxHABW,AdvertisingHeadCount/MaxPacketRate)

[0192] Where

[0193] HASize the size of the HeadAdvertisement message in bits. This is typically 416 bits (including the UDP & IP headers).

[0194] MaxHABW=The maximum allowed HeadAdvertisement bandwidth in bits per second. The application controls this value which can be different before the data starts and after the data starts. Typically, only a small portion of the data bandwidth is reserved for HeadAdvertisement messages after data starts.

[0195] MaxPacketRate=Typically 30 packets/second.

[0196] Affiliated receivers whose receiver preference is either EagerHead or ReluctantHead send out periodic HeadAdvertisement messages. The sender, like any receiver that is a potential repair head and is already part of the tree, sends out periodic HeadAdvertisement messages. HeadAdvertisements are sent with increasing TTL scope at the interval specified by the sender (HeadAdvertisementInterval). For example, a TTL of “2” is first used, and if no potential head is found, the TTL will be increased to a value of “4”, etc.

[0197] Repair heads, including the sender, stop sending HeadAdvertisement messages when they can no longer accommodate new members.

[0198] Reception of a beacon or data will cause any unaffiliated receivers to wait for one HAListenInterval to receive a HeadAdvertisement message. The HAListenInterval is given by the following minimization factor:

[0199] HAListenInterval=Min((3*HeadAdvertisementlnterval), 60 secs)

[0200] At the end of one HAListenInterval, if no HeadAdvertisement message is received, the receiver continues to listen for another HAListenInterval. The listening process continues until one or more HeadAdvertisement messages are received. When multiple HeadAdvertisement messages are received, the receiver will have to perform a selection process to choose the best-suited repair head. The repair head selection criteria is based on the following parameters and are listed in the order of preference:

[0201] Smallest TTL distance from the repair head to the member.

[0202] EagerHead over ReluctantHead.

[0203] Highest reported group member count.

[0204] Upon selecting a repair head, the receiver sends a unicast HeadBind message to the repair head. The HeadBind message is sent to the repair head's unicast port number that is specified in the HeadAdverlisement message.

[0205] A repair head, upon receiving a HeadBind message, verifies that the receiver can be accommodated as a member and responds with a unicast AcceptMember or with a unicast RejectMember. Typically a RejectMember message is sent when the repair head can no longer accept members or when the repair head is attempting to relinquish its head duties. If a RejectMember message is sent, an appropriate reason code is included in the message. The unicast port to which the repair head sends the response is obtained from the member's HeadBind message. The member then tries the next best repair head, or goes back to listening for HeadAdvertisements if none are available.

[0206] After sending a HeadBind, the receiver waits for a predetermined interval of time to receive a response. Failing to receive a response causes the receiver to retransmit the HeadBind message. After a number of successive failed attempts, the member tries the next best repair head, or goes back to listening for HeadAdvertisements if none are available.

[0207] If an AcceptMember message is received, the receiver considers itself affiliated with the repair head and starts to send periodic HeadAdvertisement messages if its receiver preference requires.

[0208] In a typical scenario, with values for AdvertisingHeadCount of 500 and Max-HABW of 200 kbps in the first equation, the HeadAdvertisementInterval yields a value of 16 seconds. Using this value in the second equation yields a value of 48 seconds for HAListeninterval. This is the minimum time that it will take a member to join the tree. The minimization factor of equation 2 limits the maximum time that a member waits to choose a repair head to 60 seconds.

[0209] The main advantage of this technique is that it does not require the network to support bi-directional multicast, since the tree construction mechanism only relies on multicast service from the repair head to the receiver.

[0210] Some of the disadvantages of this technique are:

[0211] The bandwidth consumed by HeadAdvertisement messages can be significant, especially when there are many receivers with receiver preference set to either EagerHead or ReluctantHead and the incremental increases of TTL scope ultimately cause the HeadAdvertisement messages to go beyond where they are needed.

[0212] The HeadAdvertisement messages may have to continue for the entire multicast session if the repair heads have no way of knowing when all the receivers have joined the tree in order to stop sending the HeadAdvertisement messages.

[0213] The excess HeadAdvertisement traffic can contribute to network congestion and reduce the scalability of the protocol. In some exemplary embodiments of the invention of TRAM, HeadAdvertisement traffic is not subject to congestion control.

[0214] Repair Tree Construction Under Bidirectional Multicast

[0215] Constructing a repair tree when the underlying network has no directional restrictions can be efficient and straightforward. Except for the difference in the HeadAdvertisement triggering mechanism, this tree construction technique is very similar to the preceding one. The receivers seeking repair heads use a MemberSolicilation message to trigger the repair heads to generate HeadAdvertisement messages. The following describes the tree construction process.

[0216] Receivers listen for beacon or data messages from the sender before trying to join the tree. Once a receiver hears from the sender, it multicasts a MemberSolicitation message to the multicast group using the Expanding Ring Search, ERS, mechanism. After sending the MemberSolicitation message, the receiver waits to receive one or more HeadAdvertisements from the potential repair heads in the neighborhood. This wait period is referred as ResponseInterval.

[0217] Any repair head that is already part of the tree and can accommodate new members will respond to the MemberSolicitation message by multicasting a HeadAdvertisement message. Any repair head that cannot accommodate the member or a member with receiver preference configured to MemberOnly will ignore the MemberSolicitation message.

[0218] If the receiver's ResponseLnterval expires and it has not received any HeadAdvertisement messages, the MemberSolicitation message is resent to a larger TTL. This process continues until one or more HeadAdvertisement messages are received from the repair heads that received the MemberSolicitation message. If multiple HeadAdvertisement messages are received, the receiver will have to perform a selection process to choose the best-suited repair head. The repair head selection criteria are the same as in the previous technique. Upon selecting a repair head, the receiver sends a HeadBind message to the repair head.

[0219] The processing of a HeadBind message at the repair head and dispatching of an AcceptMember or RejectMember message is the same as in the previous technique.

[0220] After sending the HeadBind message, the receiver expects to receive a response within a fixed interval of time. Failing to receive a response causes the receiver to retransmit the HeadBind message. After a number of successive failed attempts, the member tries the next best repair head, or sends another MemberSolicitation if no other repair heads are available.

[0221] If an Accept member message is received, the receiver considers itself affiliated with the repair head.

[0222] The main advantages of this approach are:

[0223] MemberSolicitation avoids continuous advertisement by repair heads because it is used only when there are receivers attempting to join the tree. This tends to reduce over-all bandwidth consumption by tree formation activities.

[0224] The ERS mechanism used by the MemberSolicitation message provides isolation when receivers are seeking repair heads in different parts of the network.

[0225] The main disadvantage is that this technique does not work with unidirectional multicast. Also, the bandwidth consumed by the MemberSolicitation messages can be significant when many receivers from a region attempt to attain membership at the same time, especially in a LAN environment. The LAN optimizations described below helps to alleviate this problem.

[0226] Combined Tree Formation Technique

[0227] This technique is a hybrid of the earlier two techniques. Before the multicast data starts to flow, TRAM builds its repair tree using the unidirectional multicast tree construction technique. Once the multicast data starts to flow, TRAM switches to using the bi-directional multicast tree construction technique.

[0228] The reasoning behind this strategy is that in the absence of the data, the HeadAdvertisement messages can utilize the bandwidth expected to be used by data. Typically, the bandwidth expected to be used by the data is specified by the maximum data rate at the sender. The sender takes into account the number of advertising repair heads in the system when computing the HeadAdvertisementInterval. This allows the sender to control the advertising overhead, limiting it to no more than the MaxHABW.

[0229] However, once the data starts to flow, the sender may not want to have HeadAdvertisement traffic in addition to data and local repairs. At this point, it changes the tree construction technique to bi-directional multicast by setting, the HeadAdvertisementInterval to zero “0”.

[0230] This technique has its limitations and can fail to construct a repair tree if data starts before all members are affiliated. Some members may not be able to affiliate with the tree if their multicast MemberSolicitation messages cannot reach any available repair heads.

[0231] LAN-Based Tree Formation

[0232] When a large number of receivers are located on one LAN, the tree construction techniques described above are not optimal for the following reasons:

[0233] Most of the LAN members will affiliate with repair heads that are not on the LAN, resulting in increased link traffic.

[0234] All LAN members that are potential repair heads will start advertising for members, causing increased traffic on the LAN.

[0235] TRAM eliminates these problems by adopting the following optimization technique.

[0236] The LAN-based tree formation optimization adopts the bottom-up approach for building a subtree on the LAN before affiliating it with the rest of the tree. The result is a subtree in which only one repair head on the LAN affiliates off of the LAN. Also, only certain repair heads on the LAN will multicast HeadAdvertisement messages.

[0237] The LAN-based tree construction technique requires the receivers on a LAN to elect a LAN head. The elected LAN head, known as the root LAN head, is then responsible for attaching to the repair tree using whatever tree-formation method is in use and performing repairs of lost packets on the LAN. While the root LAN head attaches itself to the rest of the repair tree, the rest of the receivers on the LAN become members of the root LAN head. If the number of receivers on the LAN exceeds the root LAN head's membership limit, its members collaborate to elect additional LAN heads.

[0238] LAN-based tree formation uses the bidirectional method described above. One additional field is added to the HeadAdvertisement message: a LAN state field indicating the advertising node's LAN state. Nodes willing to be a LAN head use this field to volunteer. After one HeadAdvertisementInterval, the best repair head, based on receiver preference and member limit, is elected the root LAN head.

[0239] Once the root LAN head is elected it solicits members as if it were already affiliated with the tree. Other LAN members will naturally choose the root LAN head since it is the closest one. Meanwhile, the root LAN head affiliates itself to an off-LAN repair head.

[0240] If the root LAN head reaches its member limit, additional LAN heads are elected from those already affiliated under the root LAN head.

[0241] FIG. 5 and FIG. 6 are diagrams showing the advantage of using LAN-based tree formation. Both FIG. 5 and FIG. 6 show a sender 502 which is not connected directly with the LAN, and the rest of the nodes 512 are repair heads or reluctant repair heads on the LAN.

[0242] FIG. 5 shows tree formation without LAN optimization. Most of the LAN members 512 affiliate directly with the sender 502 which is not on the LAN.

[0243] FIG. 6 shows tree formation with LAN-based tree formation. Members 512 on the LAN affiliate with the root LAN head 522, which affiliates with the sender 502.

[0244] Tree Management

[0245] The constructed repair tree has to be maintained to ensure reliable data delivery and proper protocol operation. TRAM supports a robust and rich tree management framework. Some of the functions supported by tree management are:

[0246] (1) group member and repair head monitoring.

[0247] (2) repair group TTL computation and management.

[0248] (3) member re-affiliations and repair head resignations.

[0249] (4) pruning of unsuitable members.

[0250] (5) aggregation and propagation of protocol related information up the tree hierarchy to the sender.

[0251] The different tree management messages used in TRAM are:

[0252] Hello: a multicast message sent to the group address with a TTL scope limited to the repair group scope. Repair heads that have one or more group members multicast this message.

[0253] Hello-Unicast: a unicast hello message from a repair head to a specific group member.

[0254] ACK: a unicast control message sent by a member to its repair head. This message includes a bitmap indicating received and lost packets, indications of inadequate or excess Hello TTL values, and congestion indications.

[0255] Beacon: a multicast message sent by the sender to the session scope to trigger tree-building and as a keep-alive in the absence of data.

[0256] The details of how these messages are used in the tree management operation are described in the following sections.

[0257] Group Member And Repair Head Monitoring

[0258] In TRAM, the sender distributes the burden of reliable delivery among a subset of receivers that perform the role of repair heads. To ensure reliable delivery it is required that every repair head cache the received multicast data until every member in the group acknowledges it. Since a repair head caches data until all the members acknowledge, it is very important that the repair head monitor its group members. The monitoring mechanism enables the repair heads to detect and react to conditions such as a member exiting the multicast session or becoming unresponsive. Absence of such a monitoring mechanism may lead to indefinite caching of messages at the repair heads.

[0259] From the member's perspective, it is important to ensure that lost messages are safely cached at the repair head, or further up in the tree. Repair can only be ensured when the members find the affiliated repair head to be reachable and responsive. If a repair head becomes unresponsive, the availability of lost messages cannot be guaranteed unless the member detects this condition and quickly re-affiliates with a different repair head. The monitoring mechanism enables members to detect the repair head loss condition.

[0260] The details of how the monitoring operation is carried out in TRAM are discussed below.

[0261] Monitoring of Repair Head by the Group Members

[0262] Each repair head periodically multicasts a Hello message (when necessary) to the group address with a session scope large enough to reach all of its members. The Hello period is determined by the following:

[0263] Hello Period=Max(1 Second, 1 AckInterval)

[0264] The AckInterval is computed at run time and represents the time that a member has to wait to receive a window of packets at the rate of data transfer that is currently in use. The details of computing the AckInterval are discussed later.

[0265] The reception of the repair head's Hello message ensures that the repair head is operational. If the member does not receive a Hello message for more than one Hello period, the member sets a flag indicating that Hellos are not being received in its next ACK message to the repair head. If two such ACK messages go unanswered, the member gives up on the repair head and attempts to re-affiliates with a different repair head.

[0266] In response to a member's ACK message indicating that Hellos are not being received, the repair head sends out a Hello-Unicast message. The Hello- Unicast message serves to fill in for the lost Hello message.

[0267] Repairs performed by a repair head can also indicate to its members that it is operational. But, this cannot replace the Hello mechanism as the repairs are not guaranteed to be regular, and some repair heads may not perform any repairs for many Hello periods. However, TRAM can exploit repairs to optimize the repair head monitoring mechanism. The following are some of the optimizations adopted:

[0268] Since the sender is always sending data or beacons, it does not need to send out periodic Hello messages. The sender sends out Hello messages only when it is essential, such as for TTL computation, or to demand acknowledgments.

[0269] Repair heads do not send Hello messages when they have performed repairs within the latter half of the preceding Hello period.

[0270] Members reset their Hello monitoring timers whenever a repair packet from the repair head is received.

[0271] Monitoring of Group Members by the Repair Head

[0272] Repair heads use the following mechanism to monitor members.

[0273] Each member of a repair group is expected to send at least one ACK message to its repair head for every acknowledgment interval. The details of computing the acknowledgment interval are discussed below. If a repair head does not receive an ACK message from a member for a period longer than one acknowledgment interval, the repair head adds the member to a list. The next time the repair head builds the Hello message, the entries in the list are included in the message. A special flag in the Hello message is set to demand ACK messages from the listed members. If more than three such Hello messages go unanswered by a member, the repair head disowns the member and reclaims all the cache buffers containing data unacknowledged by the member.

[0274] A member finding itself listed in a Hello message responds immediately by sending an ACK message to the repair head.

[0275] Repair Group TTL Computation

[0276] To conserve network bandwidth, it is important for repair heads to perform localized repairs, that is, with a TTL scope that is just large enough to reach ail of their members. As mentioned above TTL is the time-to-live of a message, and TTL is stated in terms of hop count. For the localized repair strategy to function properly, it is critical that the repair heads performing the repair compute the appropriate TTL to use to perform repairs. If the computed computer repair TTL is too small, the repair may not reach all of the repair requestors. On the other hand, if the TTL is larger than required, the repair will unnecessarily burden other receivers affiliated with other repair heads.

[0277] Initially, in the HeadBind message, each member recommends a TTL, based on the received HeadAdvertisement message. The repair head uses the largest recommended TTL as its repair TTL. Should the path from the repair head to the member change, the computed repair TTL might become inappropriate. The following mechanisms help the repair heads track and adjust the repair TTL:

[0278] When the repair TTL becomes insufficient, some group members fail to receive the Hello messages. These members report the condition to the repair head via ACK messages.

[0279] The repair head responds to such ACK messages by first sending a Hello-Unicast message. The Hello-Unicast message assures the member that the repair head is functioning. The repair head then increases the repair TTL by a default step value. The next Hello message sent by the repair head goes to the new repair TTL scope. Note that the repair TTL is never expected to be greater than the session TTL.

[0280] The above two steps continue until the member stops reporting that Hellos are not being received.

[0281] Each member reports in the ACK message the excess TTL from the repair head's Hello messages. If the repair head determines that it is using a larger TTL than required to reach all of its members, it reduces the repair TTL.

[0282] Member Re-affiliations and Repair Head Resignations

[0283] Re-affiliation in TRAM is triggered when a member decides that it wants to affiliate with a different repair head. This may occur because its old repair head is resigning, or is not responding, or because the member has decided that another repair head would be better (see the section below on tree optimization).

[0284] The following describes the steps involved in the re-affiliation process.

[0285] The member attempting to re-affiliates can either directly send a HeadBind message to the preferred repair head (learned from Hello and possibly HeadAdvertisement messages), or perform repair head selection based on received HeadAdvertisement messages, or seek a repair head by multicasting MemberSolicitation messages using the scheme described earlier, When the re-affiliating member is a repair head, the member has to avoid selecting a repair head that is at or below its level/depth in the tree hierarchy in order to avoid loops and disconnection from the rest of the tree.

[0286] The member uses the normal TRAM affiliation mechanisms to affiliate with the new repair head (sending a HeadBind and receiving an AcceptMember or RejectMember message). If this affiliation fails, it may start over with another repair head.

[0287] Once the member has affiliated to the new repair head, it maintains its affiliation with its old repair head until it has successfully received repairs for any packets for which repairs are not guaranteed by the new repair head. During this interval (the TransitionInterval), the member sends ACKs to both the old and the new repair heads, unless the old repair head is not responding. If the new repair head becomes unresponsive during this interval, the member may start over with another repair head.

[0288] Once the TransitionInterval has been completed, the member sends an ACK with the Terminate Membership flag set to its old repair head. At this point, re-affiliation is complete and the member and the old repair head forget about each other. If the member is itself a repair head, it continues to function as a repair head during re-affiliation.

[0289] A repair head that is re-affiliating may not accept new members until its re-affiliation process is complete. Repair heads support all other normal repair head operations during re-affiliation.

[0290] A repair head typically resigns when the application exits or when it has determined itself to be redundant in the region. The reception of Hello messages from neighboring repair heads enables a member or repair head to determine that there are multiple repair heads in the region. Reducing the number of repair heads in a region leads to a reduction in management traffic.

[0291] Aggregation and Propagation of Session Information

[0292] The monitoring mechanism supported in TRAM establishes a management session between every repair head and its members. This session can be used as a means to aggregate and propagate various protocol related events land information up the tree hierarchy. This is an efficient mechanism as it avoids problems related to implosion. The following are some of the events and information aggregated and propagated in the tree:

[0293] Congestion Events from the Receivers in the System

[0294] (1) Informatory details such as the number of receivers that are currently being served by the tree. The total number of receivers being serviced is computed as follows: every repair head in the system reports its direct member count and also the number of members that its members are serving.- This information gets aggregated at each level and is reported to the next level in the tree hierarchy and eventually to the sender. Other information aggregated in this way includes the number of advertising repair heads in the tree (used to calculate the HeadAdvertisementlnterval).

[0295] (2) Information related to the tree depth at which a member is operating. The repair heads utilize this information to avoid tree loop at the time of re-affiliation.

[0296] Tree Optimization Techniques

[0297] The optimality of the repair tree can drastically affect the scaling benefits of using a repair tree in the first place. A randomly built tree with many overlapping repair groups can cause repair heads to perform repairs with large TTL scope, which causes spillover of repair traffic to regions that do not require the repairs. The spillover is undesirable as it affects scalability, exhibits poor use of network resources and may also contribute to network congestion. The characteristics of an optimal multicast repair tree and the details of achieving the same are discussed below.

[0298] The characteristics of an optimal repair tree in TRAM may vary depending on the distribution of the receiver base. We consider two types of receiver populations. In sparse distributions, receivers are widely scattered with few concentrations (in terms of TTL) of members. In dense distributions, receivers are closely located to each other in terms of TTL.

[0299] Tree Optimization for Sparse Distributions

[0300] When the receivers are sparsely distributed, the typical characteristics of an optimal tree are:

[0301] multiple repair groups that have few overlapping repair regions, and every member in a group is affiliated to the closest repair head (in terms of the TTL distance from the repair head to the member).

[0302] The following examples illustrate poorly built and well built trees using the above criteria of optimality. In the first example, all members have affiliated with the sender, forming one large repair group. Any repair will reach all of the members. In the second example, localized groups are formed, limiting the scope of repairs.

[0303] FIG. 7 illustrates a poorly-built tree 700 for sparse distribution, showing all members 701 affiliating with sender 702.

[0304] FIG. 8 illustrates a well-built tree 800 for sparse distribution with sender 802 affiliating with repair heads 812, 814, 816, 818. Repair head 812 then affiliates with members 832. Repair head 814 affiliates with members 834, and so forth. Repair function in well-built tree 800 is shared by the repair heads 812, 814, 816, 818.

[0305] Due to the unpredictable times at which receivers join the group, it is likely that the initial tree constructed in TRAM is sub-optimal. To achieve tree optimality, every member and every repair head in the system should continuously pursue tree optimization. Tree optimization consists of determining where optimization is possible and acting upon this opportunity.

[0306] The following are some of the tree optimization techniques:

[0307] When a member hears a Hello from a different repair head in the region that is closer than its current repair head, the member attempts to re-affiliate to the closer repair head. Note that a repair head has to perform loop avoidance checks before choosing to re-affiliate with the closer repair head. Without loop avoidance checks, improper tree formation (or tree disintegration) may result when a repair head chooses to affiliate with a repair head that is at or below its level/depth in the tree hierarchy.

[0308] When two repair heads are found to be close to each other, one of the repair heads can volunteer to resign in favor of the other repair head. Typically the repair head that is better suited can continue to be a repair head while the other repair head can resign. In situations where both the repair heads are found to be suitable, tie breaker techniques such as the repair head that has fewer members, or the repair head that has the lowest unicast address and port number combination, can be used to resolve the condition.

[0309] To ensure quick and smooth re-affiliations of its members, a resigning repair head can include the details of any backup repair head (network address, unicast port number, worst case TTL distance from the backup repair head to the members) in the Hello message. The backup repair head details are informatory in nature and members with better alternatives can choose to ignore this information and re-affiliate with a different repair head. The details of the backup repair head help the members that do not hear Hellos from any other repair head other than the currently affiliated repair head.

[0310] The repair head can adopt a strategy wherein the members that are considered to be farthest are repaired using unicast and those that are considered closer are repaired using multicast. When this strategy is in use, the repair heads can be limited to accept only a few unicast members.

[0311] Tree Optimization for Dense Distributions

[0312] When all receivers are densely located in one region (say an intranet with few TTL hops between the sender and all the receivers), it may be difficult to form repair groups that have a low degree of overlap. In this situation, if the number of repair heads in the system is not controlled, much of the bandwidth can be consumed by the management traffic. Hence in the dense case, the characteristic of an optimal tree is to have as few repair heads in the system as possible.

[0313] The tree optimization technique in the dense case focuses on reducing the number of repair heads rather than finding a closer repair head. A member tries to affiliate to a repair head that is already performing the role of repair head. A new repair head is accepted only when all the current repair heads are no longer accepting members. Monitoring Hellos and HeadAdvertisements is not necessary.

[0314] The dense mode optimization algorithm is simple, straightforward and quick. The sparse mode optimization algorithm is complex and has to be pursued throughout the multicast session to form localized repair groups that have fewer overlapping regions. It is to be noted that the sparse mode optimization is unsuitable for multicast sessions that span a short duration, since some time is required to optimize the tree.

[0315] Flow Control

[0316] TRAM is designed to transfer bulk data from one sender to many receivers. The data is transmitted at a rate that adjusts automatically between a specified minimum and maximum. Sequence numbers in the data packets allow receivers to identify missing packets. Each member is bound to a repair head that retransmits lost packets when requested. Acknowledgments sent by receivers contain a bitmap indicating received and missing packets. Missing packets are repaired by the repair head. Packets acknowledged by all members are removed from the repair head's cache. The following sections describe in detail the mechanisms for transmitting data, requesting retransmission of lost packets, detecting congestion, adjusting the transmit rate, late join requests, and handling end of transmission.

[0317] Data Transmission

[0318] The sender in a TRAM application transmits data packets to every receiver in the multicast group. TRAM sends the packets at a specified rate. Each packet is given a unique sequence number starting with one (1). Receivers use these numbers to detect out of order and missing packets.

[0319] Acknowledgments

[0320] Members acknowledge one window of packets at a time to their repair head. This window is known as the ACK window. The ACK window size is configurable; the default is 32. For example, in the default case, members send ACKs every 32 packets.

[0321] To avoid multiple members sending ACK messages at the same time, and to possibly expedite repairs, ACK messages are distributed over the window. Each member selects a random packet between 1 and the ACK window size to start sending ACK messages. For example, one member may send ACKs at packets 32, 64, 96; etc., while another sends ACKs at packets 10, 42, 74, etc.

[0322] Acknowledgments are also sent if a timer equal to 1.5 times the estimated ACK interval expires. The estimated ACK interval is computed at each receiver when an ACK is sent. It estimates the amount of time it takes to receive an ACK window's worth of packets. The formula is:

[0323] ACKinterval=ACKwindow*(Time since last ACK/Packets since last ACK)

[0324] This timer is canceled if an ACK is sent using the triggering mechanism described above. If this timer expires, it indicates that the sender has paused and allows members to report and recover any lost packets without having to wait for the sender to start sending new data.

[0325] Each ACK message contains a start sequence number and a bit map length. If no packets were missing, the bit map length is “0” and the sequence number indicates that all packets prior to and including this packet were successfully received. The repair head saves this information and uses it to remove packets from its cache.

[0326] If there are one or more missing packets, the start sequence number indicates the first missing packet. A bit map must follow. Each bit in the map represents a packet sequence number starting with the start sequence number. If the bit is set, that packet is missing and must be retransmitted. A bit map length indicates how many valid bits are present.

[0327] When the repair head receives an ACK message with a “missing packets” bit map, the sequence number specified minus 1 is saved for this member. This indicates that all packets prior to and including this sequence number have been received successfully. The repair head then scans the bit map looking for missing packets. It immediately places these packets onto the transmit queue unless they have recently been retransmitted or are already on the queue from another request.

[0328] Data Retransmissions

[0329] When a repair head receives a request to retransmit a packet, it retransmits it as soon as possible. Retransmissions take priority over new data packets. Retransmitted packets are sent at the current rate used for new data packets from the sender. Each repair head computes the average data rate of all packets it receives and sends retransmissions at this rate.

[0330] Duplicate Retransmission Avoidance

[0331] When several members request retransmission of the same packet, TRAM sends the packet immediately for the first request. Subsequent requests are ignored if they are received within 1 second of the first request.

[0332] Occasionally packets are waiting for retransmission due to rate limitations. If a new request for a packet is received and that packet is awaiting retransmission, the request is ignored.

[0333] Every repair head in TRAM keeps track of the lowest packet sequence number that all members have received. Before a repair head retransmits a packet that has been waiting to be retransmitted, it again checks the sequence number of the packet to be retransmitted against this lowest packet number. If the retransmission packet sequence number is lower, the repair head skips this retransmission because all of its members have already acknowledged the receipt of the packet. This can happen when multiple repair heads retransmit the same packets and their transmission range overlaps.

[0334] Rate-based Flow Control

[0335] Even with unicast transports, flow and congestion control is a delicate problem. The flow control in TRAM is rate-based and is similar to a rate-based unicast protocol.

[0336] TRAM's packet scheduler computes the amount of time to delay each packet in order to achieve the desired data rate. The delay is computed with the formula:

[0337] packet size/desired rate

[0338] The overhead in processing the packet is subtracted from this delay. TRAM then sleeps for the calculated period, sends the packet, and the cycle continues. This is similar to the widely known token bucket algorithm.

[0339] TRAM's flow control uses various algorithms such as slow start and congestion control to dynamically adapt to network conditions. A maximum and a minimum rate can be specified to limit the operation of these algorithms. The minimum rate effectively defines the receiver population. Any receiver that cannot keep up with the minimum rate will be pruned (no longer guaranteed repairs).

[0340] If packets are lost or ACKs are not reaching a repair head, its cache will start to fill up. If the sender's cache fills up above a threshold value, it stops sending new data until it can free some buffers from its cache. This bounds how much the sender and receivers are allowed to get out of synch.

[0341] TRAM sessions go through two phases of flow control: slow start; and congestion control. The slow start phase is the initial phase during which TRAM carefully tests the network to find an appropriate operating point. This is analogous to TCP's slow start. After the slow start phase, TRAM will have established some boundaries for its operation and enters the congestion control phase.

[0342] Slow Start

[0343] During the slow start phase, the initial data rate starts at 10% of the maximum, or the minimum rate if that is greater. Every two ACK windows this rate is increased another 10% of the maximum data rate. This process continues until the maximum rate is reached or congestion causes the rate to decrease.

[0344] Congestion Reporting

[0345] Congestion is detected at the receivers and repair heads. Receivers detect and report congestion based on missing packets. Repair heads detect and report congestion based on their cache usage.

[0346] At Receivers

[0347] Receivers detect and report congestion based on an increase in the number of missing packets between two ACK windows. For example, if a receiver detects 5 missing packets during an ACK window, and has 10 packets missing in the next window, a congestion message is sent to its repair head. The congestion message contains the highest sequence number received. When the repair head receives the congestion message, it determines whether this is a new congestion report and if so, forwards it immediately up to its repair head. Each repair head will forward one congestion packet from its members for each ACK window. The repair head computes the ACK window from the sequence number specified in the congestion message with the formula: sequence number/ACK window size.

[0348] Once a congestion message for an ACK window has been forwarded up the tree, congestion reports for its ACK window and previous ACK windows will be ignored. The sender does not react to multiple congestion reports for the same window.

[0349] At Repair Heads

[0350] Repair heads also generate congestion messages when their data caches begin to fill up. Each repair head maintains a low and high water mark on its cache. When the number of packets in the cache reaches the high water mark, an attempt is made to purge the cache. If it can't purge the cache below the high water mark because a member has not acknowledged these packets, a congestion message is forwarded up the repair tree. In this situation the repair head temporarily increases its high water mark to the current value plus the number of packets in an ACK window. The repair head performs the same test when this new temporary high water mark is reached. If the cache is exhausted, new packets are dropped without acknowledging them.

[0351] The sequence number in a repair-cache-generated congestion message is the highest sequence number the repair head has received.

[0352] At The Sender

[0353] The sender also maintains a cache for its immediate group members. If its cache fills up to the high water mark and can't be reduced, it reacts as if it received a congestion message for that window. It also temporarily increases its high water mark to the current value plus the size of an ACK window. If the cache fills to this new level and can't be reduced, it reacts again.

[0354] This process continues until the cache is full. At this point the sender blocks any new data from the application and attempts to solicit an ACK from the members that are causing the cache to fill up. If these members do not respond quickly, they may be pruned.

[0355] When some cache buffers are freed, the application can start sending data again.

[0356] In experiments, we observe that the repair head's cache-generated congestion messages almost always follow the receivers' loss-generated congestion messages. This is logical as the build-up in the repair head's cache is invariably caused by the lost packets at the receivers.

[0357] Congestion Control

[0358] The sender reacts to congestion feedback as follows: react to selected congestion reports; decrease the rate in the face of congestion; and, increase the rate in the absence of congestion.

[0359] The only significant experience with real network congestion control is based on TCP traffic and the algorithms implemented in the TCP protocol. One of the key ingredients of TCP's algorithm is to follow the additive increase/multiplicative decrease rule.

[0360] The Increase Amount

[0361] Since TRAM transmission is rate based, an immediate problem is determining the right rate increase in the absence of congestion. TCP is a window based protocol in which increases are done by incrementing the congestion window by one, a dimensionless parameter. In the spirit of TCP, the correct amount to increase TRAM's rate would be a small fraction of the bottleneck bandwidth. Plus, this amount would need to be adopted by all the flows sharing the same bottleneck. This increase is not easily determined.

[0362] A constant increase amount will always be wrong for some topologies. Although we used 10% of the maximum rate for slow start, it does not seem suitable since the maximum rate may be far from the current bottleneck rate. Instead, TRAM derives the increase amount dynamically as follows. TRAM keeps track of the historically highest achieved rate (HHR). After each rate decrease, a new increase amount is calculated as:

[0363] Increase=(HHR−current_rate)/S

[0364] The rationale is to use HHR as a local estimate of the bottleneck bandwidth. Within a small number of steps “S” (for example, in a preferred embodiment S is set to equal 4), TRAM tries to return to that level if there is no congestion. The constant S may be changed from its initial value of 4 in response to further experimentation; a larger number might be adopted for potentially more equitable bandwidth sharing by many flows in exchange for slower convergence to the optimal rate.

[0365] An immediate reaction to this formula would be to replace HHR with something that adapts to the current network condition, for instance, using the most recently achieved high (MRH), or a moving average of MRH, or the session average data rate. Each of these cases resulted in diminishing increases for some common topologies, eventually leading to a rate close to zero.

[0366] Decrease

[0367] The receipt of a congestion report causes the data rate to drop by a percentage (for example 50%, and we are also experimenting with 25%). This is the same as TCP. Adjusting the rate by a percentage is very appealing since the adjusted amount is dimensionless, hence there are no calibration problems.

[0368] Synchronizing Feedback And Control

[0369] The next important aspect of a congestion control scheme is how to keep the feedback and control in synchrony with each other. Ideally, each control action is based on the feedback from the network that reflects the consequence of the previous control. From systems theory, we know that there is a chance of building a control that leads to optimal and stable behavior.

[0370] If our feedback does not capture the consequence of the previous control, then we are likely to end up with a control that reacts to the same conditions repeatedly and leaves the system in wide oscillation. This oscillation is indeed what we observed in our simulation experiments if we increase the rate for each window when there is no congestion, and decrease for each window when there is congestion.

[0371] In order to make sure that each congestion feedback includes the previous control actions, the congestion control algorithm must wait for several windows before acting on the feedback. This tends to make the system less responsive to topologies with a small number of receivers.

[0372] As a compromise, TRAM increases the rate every other ACK window in the absence of congestion reports. When a congestion report is received, TRAM decreases the rate right away and records the window in which the congestion happened. Another increase or decrease in rate is not allowed until after N windows, where N is:

[0373] N=4*(rate/HHR)

[0374] Where 4 is simply 2 times the normal schedule of reacting to every 2 windows.

[0375] The reasons for using a variable schedule are: at lower rates, the risk of congestion is less hence it is fairly safe to increase the rate sooner; at lower rates, the time penalty for waiting an additional window is longer.

[0376] Accounting for Retransmission

[0377] To further improve the congestion control algorithm, TRAM includes mechanisms to take into account the effect of retransmission when determining the rate during periods of congestion.

[0378] In the congestion message, the receivers report an estimate of how long it will take to do local repairs. This information is aggregated back to the sender. In reaction to a congestion message, the sender not only reduces its rate, but also pauses briefly to let the local repairs complete.

[0379] This mechanism has further smoothed out the oscillations in our simulation experiments.

[0380] Congestion Control Simulation and Results

[0381] To support the design of TRAM, we built a simulation model using the NS simulation tool. The NS simulation tool used was version 2 of the Network Simulator, http://www.mash.cs.berkeley.edu/ns. The TRAM protocol is modeled using the simulation tool NS. The object-oriented simulation environment, the scripting language support, plus the companion animation tool, NAM, enable effective experiments.

[0382] Many different network topologies were simulated.

[0383] Turning now to FIG. 9, a network topology 900 used in simulation is shown. The results from two variants of the topology shown in FIG. 9 are disclosed. The basic network consists of two hundred one (201) nodes. The sender agent 902 runs on one node, repairer agents run on 24 of the nodes, and pure receiver agents run on 168 of the nodes. The other 8 nodes are router-only nodes. The whole network is symmetric. Each repairer is 2 hops away from the sender, and each receiver is 1 hop away from its parent (repair head). The links from the sender to the first tier routers are 1.5 Mb/s links with 50 msec delay. The rest of the links are 1.5 Mb/s links with 10 msec delay, except 3 of these links are 0.5 Mb/s links with 10 msec delay. These 3 slow links are the bottleneck of the multicast session.

[0384] In the variation of this topology, the 3 slow links are further programmed to deterministically go up and down. Every 3 seconds, they go down for 0.05 seconds. On average the down time is less than 2%.

[0385] The experiment is to send 1000 packets, 1400 bytes each. The sending starts at 1.5 seconds from the beginning of the simulation. Since the limiting bandwidth is 0.5 Mb/s, assuming ideal scheduling the whole transmission should take 22.4 and 23 seconds respectively.

[0386] FIG. 10 and FIG. 11 show how TRAM did for each of the two cases. The X axis is time in units of seconds. The Y axis scale is used for a number of things:

[0387] Rate: in 10 Kb/s (i.e. 50=0.5 Mb/s)

[0388] Loss: number of packets lost at ACK time

[0389] Cache occupancy: number of packets

[0390] FIG. 10 is a graph 10,002 showing results for a network without up/down dynamics.

[0391] FIG. 11 is a graph 11,002 showing results for a network with up/down dynamics.

[0392] FIG. 10 for a static 201 node network is next discussed. The top curves represent the monitored rate and the send rate. The next curve is the cache occupancy observed at a repair head that is responsible for a receiver that is behind the slow link. Losses are shown along the bottom. As can be seen, the buffer occupancy shoots up soon after the losses start to occur.

[0393] For the static network in FIG. 10, the maximum possible transmission rate, as limited by the bottleneck bandwidth, is 50 (Kb/s). TRAM manages to keep the rate oscillating between 30 and 60. The initial spike is bigger, the result of slow start when there is no hint what the possible maximum rate is. The subsequent improved performance is what we expected.

[0394] The fact that the cache occupancy oscillates at around 7 in the steady state is normal. In these tests, the ACK window is set to 8. With ACK staggering, the cache usage is expected to stay around 8, instead of going from zero (0) to eight (8) and back to zero (0) in a saw-tooth form.

[0395] FIG. 11 shows results for the simulation network of FIG. 9 and including adding up/down dynamics to some links. In FIG. 11, the link up/down dynamics clearly induce very periodic losses at the times the links turn off (every 3 seconds). TRAM adapts quite well, except right after the first link down, when the losses induced a high cache occupancy. This is because a retransmission failed to get to the receiver behind the faulty link for quite a long time. After it overcame the initial difficulty, the rate oscillated between 30 and 60 as in the static network case. The time of completing the test is only marginally longer than the static network case.

[0396] Late Joins

[0397] Receivers joining the multicast group after data transmission has startedhave two options for recovering data previously sent:

[0398] Recover as much data previously sent as possible. This option allows the receiver to request retransmission of all the previously sent data that its repair head has cached. A repair head typically has at least the last 50 packets sent, in its cache.

[0399] Don't recover anything sent before the receiver joined. This option doesn't attempt to recover any previously sent packets. The first data packet received after the new member joins the repair tree is handed up to the application. All previously sent packets are ignored.

[0400] End of Transmission

[0401] Receivers must be able to determine when the session has completed to ensure they have received all of the data before exiting.

[0402] When the sender application completes, end of transmission is signaled throughout the multicast group. The sender notifies all members of session completion with a beacon packet that has the TXDONE flag set. This packet also includes the sequence number of the last data packet sent. The sender transmits this packet periodically until all of its immediate members acknowledge the receipt of all packets sent. The sender can then exit.

[0403] When a member receives the beacon packet with the TXDONE flag set, it immediately sends an ACK message to its repair head indicating whether it has received all the packets transmitted or requires more retransmissions. TRAM notifies the application when it receives all of the packets.

[0404] When a repair head receives the beacon packet with the TXDONE flag set, it communicates with its repair head just as a receiver does. The repair head must wait for all of its members' to acknowledge all packets before it can close the session. If a member requires retransmission, the repair head must retransmit all the packets required of its members prior to closing itself. If the beacon from the sender with the TXDONE flag set is received but one or more members have not acknowledged all packets, a Hello message is sent to these members with the same information contained in the beacon packet. Members receiving this Hello message must respond in the same way that they would if they received the beacon. If the repair head still doesn't hear from its members after sending the Hello, it retries several times. After a period of time it gives up on the member and removes it from the member list.

[0405] When all members have either acknowledged all packets to the repair head or have been removed from the member list because they were not responsive, the repair head can close its session.

[0406] Pruning

[0407] In a multicast data distribution setup, the source of a multicast stream can operate in a mode that is sensitive or insensitive to the data reception feedback from the receivers. The drawbacks of being insensitive are a lack of response to network congestion and an inability to deliver the data to as many receivers as possible. Being sensitive makes the multicast distribution mechanism overcome the above drawbacks but also introduces a new drawback that may make the sender operate at a rate that is slower than what is desired by the application. To overcome this drawback, it is necessary that the multicast delivery system support some sort of a pruning mechanism which enables receivers that do not meet the reception criteria to be isolated and removed from the repair mechanism.

[0408] In TRAM, the reception characteristics of all the receivers is distributed knowledge. The sender knows of the reception characteristics of its immediate members while some other repair heads in the system know the reception characteristics of some other set of receivers. Due to the distributed nature of reception characteristics, TRAM adopts a collaborative pruning technique that involves the sender and all the repair heads in the system.

[0409] The technique requires the sender to orchestrate the pruning operation by providing a MinimumDataRate signal. The signal is included in the header of multicast data and beacons sent by the sender. The signal is set to OFF when no congestion is being reported from the sender.

[0410] As a result of receiving congestion feedback information from one or more receivers, the sender attempts to reduce the rate of transmission to accommodate the slow receivers.

[0411] The sender sets the MinimumDataRate signal ON when the sender is operating at the minimum rate specified by the application. The MinimumDataRate signal informs repair heads in the distribution tree to prune any poorly performing receivers. The repair heads may respond to receiving the MinimumDataRate signal by pruning members.

[0412] Pruned members can be members that are slow, members that are requesting excessive repairs or members that have become unresponsive as a result of a network partition or for some other reason. The members that are pruned are notified of membership termination via the Hello-Unicast message. The repair head may stop honoring repair requests from members that are pruned.

[0413] Repair heads can independently perform the pruning operation (i.e., without a sender signal). This may result in premature pruning of the members, as the repair heads may not know whether or not the sender is operating at the configured minimum rate.

[0414] Fourth Exemplary Embodiment

[0415] General Description of Computer Communication Protocols

[0416] Communication in a computer internetwork involves the exchange of data between two or more entities interconnected by communication media. The entities are typically software programs executing on hardware computer platforms, such as end stations and intermediate stations. In particular, communication software executing on the end stations correlate and manage data communication with other end stations. The stations typically communicate by exchanging discrete packets or frames of data according to predefined protocols. A protocol, in this context, consists of a set of rules defining how the stations interact with each other.

[0417] The hardware and software components of these stations generally comprise a communications network and their interconnections are defined by an underlying architecture. Modem communications network architectures are typically organized as a series of hardware and software levels or “layers” within each station. These layers interact to format data for transfer between, e.g., a source station and a destination station communicating over the internetwork. Predetermined services are performed on the data as it passes through each layer and the layers communicate with each other by means of the predefined protocols. Examples of communications architectures include the Internet Packet Exchange (IPX) communications architecture and, as described below, the Internet communications architecture.

[0418] The Internet architecture is represented by four layers which are termed, in ascending interfacing order, the network interface, internetwork, transport and application layers. These layers are arranged to form a protocol stack in each communicating station of the network.

[0419] Turning now to FIG. 12, there is illustrated a schematic block diagram of prior art Internet protocol stacks 12,125 and 12,175 used to transmit data between a source station 12,110 and a destination station 12,150, respectively, of an internetwork 12,100. As can be seen, the stacks 12,125 and 12,175 are physically connected through a communications medium 12,180 at the network interface layers 12,120 and 12,160. For ease of description, the protocol stack 12,125 will be described.

[0420] In general, the lower layers of the communications stack provide Internetworking services and the upper layers, which are the users of these services, collectively provide common network application services. The application layer 12,112 provides services suitable for the different types of applications using the internetwork, while the lower network interface layer 12,120 accepts industry standards defining a flexible network architecture oriented to the implementation of local area networks (LANs).

[0421] Specifically, the network interface layer 12,120 comprises physical and data link sublayers. The physical layer 12,126 is concerned with the actual transmission of signals across the communication medium and defines the types of cabling, plugs and connectors Is used in connection with the medium. The data link layer is responsible for transmission of data from one station to another and may be further divided into two sublayers: Logical Link Control (LLC 12,122) and Media Access Control (MAC 12,124).

[0422] The MAC sublayer 12,124 is primarily concerned with controlling access to the transmission medium in an orderly manner and, to that end, defines procedures by which the stations must abide in order to share the medium. In order for multiple stations to share the same medium and still uniquely identify each other, the MAC sublayer defines a hardware or data link address called a MAC address. This MAC address is unique for each station interfacing to a LAN. The LLC sublayer 12,122 manages communications between devices over a single link of the internetwork.

[0423] The primary network layer protocol of the Internet architecture is the Internet protocol (IP) contained within the internetwork layer 12,116. IP is a network protocol that provides internetwork routing and relies on transport protocols for end-to-end reliability. An example of such a transport protocol is the Transmission Control Protocol (TCP) contained within the transport layer 12,114. The term TCP/IP is commonly used to refer to the Internet architecture. Protocol stacks and the TCP/IP reference model are well-known and are, for example, described in Computer Networksby Andrew S. Tanenbaum, printed by Prentice Hall PTR, Upper Saddle River, N.J., 1996.

[0424] Data transmission over the internetwork 12,100 therefore consists of generating data in, e.g., sending process 12,104 executing on the source station 12,110, passing that data to the application layer 12,112 and down through the layers of the protocol stack 12,125, where the data are sequentially formatted as a frame for delivery onto the medium 12,180 as bits. Those frame bits are then transmitted over an established connection of medium 12,180 to the protocol stack 12,175 of the destination station 12,150 where they are passed up that stack to a receiving process 12,174. Data flow is schematically illustrated by solid arrows.

[0425] Although actual data transmission occurs vertically through the stacks, each layer is programmed as though such transmission were horizontal. That is, each layer in the source station 12,110 is programmed to transmit data to its corresponding layer in the destination station 12,150, as schematically shown by dotted arrows. To achieve this effect, each layer of the protocol stack 12,125 in the source station 12,110 typically adds information (in the form of a header) to the data generated by the sending process as the data descends the stack.

[0426] For example, the internetwork layer encapsulates data presented to it by the transport layer within a packet having a network layer header. The network layer header contains, among other information, source and destination network addresses needed to complete the data transfer. The data link layer, in turn, encapsulates the packet in a frame, such as a conventional Ethernet frame, that includes a data link layer header containing information, such as MAC addresses, required to complete the data link functions. At the destination station 12,150, these encapsulated headers are stripped off one-by-one as the frame propagates up the layers of the stack 12,175 until it arrives at the receiving process.

[0427] In many cases, the destination of a data frame (“message”) issued by a source (“sender”) May be more than one, but less than all of the entities (“receivers”) on a network; this type of multicast data transfer is typically employed to segregate communication between groups of receivers on the network. IP multicasting, in particular, may be used to disseminate data to a large group of receivers on the network. However, any number of data messages may be lost in transit due to errors or overloading of networking equipment. Ensuring that each receiver/member of a multicast group has received all of the data messages is difficult for a single sender to determine once the group is of any size, since messages from each member to the sender can overload the sender.

[0428] One approach to providing scalable reliable multicasting is to organize the receivers into a tree structure so that each internal “node” of the tree is responsible for helping its subordinates recover any lost packets and communicating status back to the sender. Many conventional algorithms exist for constructing such a tree. For example, reliable multicast protocols such as TMTP and RMTP build trees that are used for an entire data transfer session without optimization. Lorax describes methods for generally enforcing member limits. After such a tree is constructed, it may be further optimized as network conditions change. The present invention is directed, in one aspect, to defining characteristics of optimal trees and mechanisms for obtaining such trees.

[0429] To effect IP multicasting, a sending process generally specifies a destination IP address that is a multicast address for the message. Receiving processes typically notify their internetwork layers that they want to receive messages destined for the multicast address; this is called “joining a multicast group”. These receiving members then “listen” on the multicast address and, when a multicast message is received at a receiver, it delivers a copy of the message to each process that belongs to the group. The result is that the message traverses each link between the sender and receivers only once. When the sender issues a sequence of messages, a multicast flow occurs.

[0430] Flow and congestion control for multicast transport is a relatively new research topic. For minutes of an Internet Research Task Force meeting on this topic in September 1997, see http://www.east.isi.edu/RMRG/notes-revO. html. In general, flow and congestion control algorithms adaptively find an optimal (transmission) rate for a multicast flow, based on available bandwidth of all links involved in the transmission and the speed 1 of all the receivers involved.

[0431] When a multicast flow competes with other flows (multicast or unicast) for network resources, the flow and congestion control algorithm should exhibit some level of fairness in using the congested resources.

[0432] Adaptive control of transmission rate is based on feedback from the network, as is done in unicast flows. A multicast flow tends to traverse more links and depend on the speed of more receivers than a unicast flow. This dependence on more resources makes to the multicast flow control problem substantially more complicated than the case for a unicast flow. The present invention is further directed, in another aspect, to an efficient flow and congestion control technique.

[0433] The present invention generally relates to a scalable, reliable multicast transport protocol (TRAM) that supports bulk data transfer with a single sender and multiple receivers of a computer internetwork, such as an intranet or Internet. In one aspect of the invention, TRAM uses reliable multicast repair trees that are optimized to implement local error recovery and to scale to a large number of receivers without substantially impacting the sender.

[0434] Fifth Exemplary Embodiment of the Invention

[0435] Further features of TRAM are disclosed in this fifth exemplary embodiment of the invention.

[0436] TRAM is a tree based reliable multicast protocol. TRAM enables applications requiring reliable multicast to be essentially free of transport related issues like:

[0437] Transmission of data between the sender and the receivers reliably.

[0438] Direct interaction between the sender and receiver applications.

[0439] Congestion control, ACK: implosion and other scalability issues.

[0440] Further, TRAM requires no prior knowledge of the receiver community. Also, scalability is non-trivial in former reliable multicast technology, and TRAM achieves this by dynamically grouping the tuned receiver community into hierarchical groups. Grouping enables TRAM to avoid the ACK/NACK implosion problem and to perform local repair operations.

[0441] The invention provides many features, for example the features of the invention include: reliable multicast; single source to many receivers; scalable—ability to support a large receiver community; support local repair; support adaptive congestion control mechanisms to prevent network flooding; ordered data delivery; support unidirectional and multidirectional multicast environments during the initial building of the tree and for late joins, and reaffiliation during data transfer; control bandwidth used by multicast control messages during tree formation anti data transfer; scalable up to a million receivers; late joins without data recovery; support for real-time data and resilient category of applications; and, unordered data delivery.

[0442] Introduction To Reliable Multicast

[0443] Multicasting provides an efficient way of disseminating data from a sender to a group of receivers. There are wide range of applications that can gain by adopting this technology for their data delivery. While some of the applications can function well in an unreliable setup, some of the applications do require reliability for their proper functioning. The degree of reliability required for applications requiring reliable multicast support varies from application to application. The RM group forming within the IRTF has broadly classified the applications requiring multicast into the following categories:

[0444] Bulk Data.

[0445] Live Data

[0446] Resilient Streams.

[0447] Shared Data.

[0448] Hybrid.

[0449] Major challenges posed by reliable multicast in supporting a large scale multicast application are:

[0450] ACK/NACK Implosion

[0451] For multicast messages to be delivered reliably to every receiver, the sender can either wait for the receivers to acknowledge (ACK) the receipt of the messages; or alternatively adopt a model wherein the receivers report only those messages that were not (NACK) received. For a large receiver base, an ACK implosion is said to occur when a message (or a window of messages) are successfully received by the receivers. A NACK implosion occurs whenever a message loss is detected by a large number of receivers.

[0452] Retransmission Based Error Control

[0453] This involves the process of delivering the lost data to the individual receivers and the mechanisms (sender based or local repair etc.,) used in performing the repair operations.

[0454] Congestion Control

[0455] Process of sensing congestion and recovering from it rather than aggravating it. The congestion control mechanism is rate based and is adaptive which enables the sender to sense and adjust to the rate at which the receivers can accept the data.

[0456] TRAM Reliable Multicast Protocol

[0457] The TRAM model includes the following features:

[0458] Scope: one source to multiple receivers.

[0459] Tree based with dynamic grouping of receiver community. Regrouping of receivers supported to achieve better distribution of receivers.

[0460] Robust tree management and quicker re-grouping under node failure conditions.

[0461] Distributed ACK and NACK reporting.

[0462] Receiver initiated localized repair operations.

[0463] Adaptive congestion control with the ability to adjust the rate of data transmission either to the rare suitable to the slowest receiver nodes or to the specifications provided by the application (involves pruning of slow receivers).

[0464] Scales to very large number of receivers.

[0465] Count of the number of receivers tuned to a multicast session.

[0466] Turning now to FIG. 14, a brief description of the TRAM model follows. The receivers in TRAM are dynamically grouped into hierarchical groups to form a tree 14,000. The sender 14,002 is at the head of the tree. The parent 14,012; 14,014; 14,016; 14,018; 14,020 of each respective group 14,012-1; 14014-1; 14,016-1; 14,018-1; 14-020-1 is said to be a head. Data is multicast by the sender and all the receivers receive it. The heads in the tree cache the received data messages. The members of a group need not cache the data. Caches 14,030-X are shown for each respective head. The members send acknowledgments of receiving the data to the associated/affiliated head. The heads can free the cached data messages upon receiving acknowledgments from all the members. When members detect loss of a message, they send retransmission requests to the affiliated heads. The group heads retransmit the requested message with a local TTL scope that is large enough to reach all its members.

[0467] In addition, the model supports mechanisms: to detect loss of a member/head; detect and control congestion; and to regroup members in a group to achieve tree optimizations.

[0468] The model is discussed by first presenting the model fundamentals. The model fundamentals are then threaded together to describe the detailed operation in the Transport Operation subsection.

[0469] Scalability

[0470] TRAM has the potential of scaling to large number of receivers. This is primarily achieved as a result of adopting:

[0471] (1) Hierarchical tree based grouping of the receiver community.

[0472] (2) Distributed ACK reporting mechanism.

[0473] (3) Local repair operations; and

[0474] (4) Adaptive congestion control mechanisms.

[0475] Ideally speaking, a four (4) level balanced tree with the sender at the head and every node in the tree supporting 32 different nodes can easily scale to a million receivers. In reality, the factors that limit the scalability of TRAM are:

[0476] The required maximum and minimum rate of data transmission of the sender.

[0477] The ability of the receiver nodes to cache the multicast data and perform local repair operations.

[0478] The computing power of the receiver nodes performing the local repair operations.

[0479] Efficient tree/group formation.

[0480] Rate of local repair operations and the degree/extent of overlap of the TTL based local repair boundary between groups.

[0481] Multicast bandwidth consumed by the TRAM control and tree/group management messages.

[0482] In an exemplary embodiment of the invention, TRAM scales to a four level tree with 32 members per node, for a scaling to 32*32*32*32=1,048,576 members. Further levels of scaling to even more members is expected to perform smoothly.

[0483] TRAM Repair Tree

[0484] Modes

[0485] The TRAM modes of operation are:

[0486] SEND-ONLY

[0487] RECEIVE-ONLY

[0488] SEND-RECEIVE.

[0489] SEND-ONLY mode is typically used by an application intending to be the source of a multicast data stream. The application is addressed as the sender in the document.

[0490] RECEIVE ONLY mode is typically used by application(s) intending to receive a multicast data stream. The application is addressed as the receiver in the document.

[0491] SEND-RECEIVE mode is suitable for applications intending to source as well to receive from a multicast stream.

[0492] The TRAM requires the applications to specify the mode of operation at the time of starting a TRAM session. The mode causes the TRAM to initiate appropriate management operations required to support the application.

[0493] RxGroup, RxGroup-head, RxGroup-member and RxNode

[0494] Turning now to FIG. 15, a block diagram 15,000 showing RxGroup relationships is shown. For each multicast data stream, TRAM dynamically organizes the tuned receiver community into multi-level hierarchical groups 15,002; 15,004; 15,006; 15,008; 15,010; 15,012; 15,014 named RxGroups. Every RxGroup comprises of a group head known as RxGroup-head and a configurable number of group members known as RxGroup-members. For example, for RxGroup 15,014, the group head 15,014-H, and members 15,014-1; 15,104-2; 15,014-3 are shown. The transport supporting the sender 15,020 application is by default a RxGroup-head. A RxGroup in which the transport supporting the sender operates as the group head is known as a Primary-RxGroup, and all the rest as Secondary-RxGroups. A RxGroup-Member of one RxGroup can in turn play the role of a group head to its lower level RxGroup, as member 15,008-1 of group 15,008 is a group head for group 15,010.

[0495] A RxGroup-head is primarily responsible for caching the sent/received multicast data to participate in local repair/retransmission operations. Multicast messages received by the RxGroup-members are acknowledged with the aid of unicast ACK messages. The ACK messages are sent to the respective RxGroup-heads to distribute and overcome the ACK implosion problem. The ACK reporting is done using a window mechanism.

[0496] A receiver node not part of any RxGroup or is in the process of affiliating to a RxGroup is known as a RxNode, as illustrated by RxNode 15,030.

[0497] The details of RxGroup formation and the selection of the RxGroup-head and RxGroup-members are discussed in the RxGroup Management section hereinbelow.

[0498] Sender-beacon

[0499] A sender-beacon is a lightweight multicast message generated by the TRAM supporting the sender at various stages in a multicast session. The sender-beacon uses the same multicast address destined to be used by the sender. The sender TRAM utilizes the sender-beacon as a means to communicate with the receiver community.

[0500] The Sender-beacon Serves Different Purpose Under Different Conditions

[0501] At the beginning of a multicast session (i.e., before the multicast data transmission), the sender-beacon signals the receiver community to start the RxGroup formation process. The sender-beacon is periodic (T_BEACON) and has session-scope TTL. In the middle of a multicast session (i.e., when the multicast data transmission is in progress), the sender-beacons are generated only under the following conditions and have a session-scope TTL

[0502] 1. When the application at the sender is not producing the data packets at the specified (configured) rate of data transmission. The sender-beacon rate in this case does not match the specified rate of data transmission but is frequent enough to indicate to the receiver community that the multicast session is active.

[0503] 2. Under congestion when the multicast data transmission is temporarily suspended. The sender-beacon is periodic (T_BEACON_FILLER) for the suspended interval of time and serves to enable the receiver community to consider the muiticast session to be active.

[0504] The TRAMs on the receiver side discard the sender-beacon message after processing and updating the sender status information.

[0505] At the end of the multicast session, the sender-beacon is used to signal the end of the multicast session and gather some statistics. The sender-beacon in this case is periodic (T_BEACON_FILLER) for a configured period of time. This is currently considered to be optional.

[0506] RxGroup Management

[0507] The RxGroup management mechanism enables the dynamic formation of receiver community into RxGroup(s). The RxOroup, formation uses a mechanism similar to expanding ring search (ERS).

[0508] RxGroup formation occurs at the start of a multicast session. The TRAM at the sender triggers the RxGroup formation process by generating the sender-beacon messages. The sender-beacons are stopped when the sender starts transmitting the multicast data. In order to accommodate late joins, the group formation continues even after the sender-beacon stops. Regrouping of RxGroup can occur at anytime during the multicast session and are primarily done to achieve optimizations such as load balance etc.; or due to the loss of a RxGroup-head.

[0509] Before the reception of a sender-beacon or multicast data message, all tuned receiver TRAMs remain idle and do not participate in any RxGroup formation process.

[0510] RxGroup management requires TRAMs to maintain the following state for every supported multicast session:

[0511] 1. Member role (MRole).

[0512] 2. Head state (HState).

[0513] 3. Group level (RxLevel).

[0514] 4. Direct member count (Dmem_Count).

[0515] 5. Indirect member count (IndMem_Count).

[0516] 6. Direct head count (Dhead_Count).

[0517] 7. Indirect head count (IndHead_Count).

[0518] 8. Direct advertising head count (DAdverthead_Count).

[0519] 9. Indirect advertising head count (IndAdvertHead_Count).

[0520] 10. Reserved head slots available (Reserved_Head_Slots).

[0521] 11. Member slots available (Avail_Member_Slots).

[0522] Items 2, 4, 5, 6, 7, 8, 9, 10 and 11 are applicable only if the TRAM is performing the role of a RxGroup-head.

[0523] The MRole information is advertised by the TRAMs, as part of the RxGroup Management process, to indicate its current or preferred role in the RxGroup Management. The different MRoles in RxGroup Management are:

[0524] Member_Only.

[0525] Member_EagerHead,

[0526] Member_ReluctantHead.

[0527] Member_Only role indicates the inability of TRAM to perform the role of a RxGroup-head. This is typically reported by RxNodes with resource limitations or explicitly administered to perform the role.

[0528] Member_EagerHead role indicates that the TRAM is either (1) performing the role of a RxGroup-head or (2) is attempting to become a RxGroup-member and is willing to perform the role of a RxGroup-head when required.

[0529] Member_ReluctantHead role indicates that the TRAM is either (1) performing the role of a RxGroup-head or (2) is attempting to become a RxGroup-member and can perform the role of RxGroup-head when commanded or when it is absolutely necessary.

[0530] The HState information is maintained and advertised by TRAMs that are currently performing the role of a RxGroup-head. This information is included in the RxGroup Management messages that are multicast with a local scope. The RxGroup-members use the HState information to decipher the current state of a RxGroup-head in the neighborhood. The different HState states are:

[0531] Accepting_Members.

[0532] Not Accepting_Members.

[0533] Resigning.

[0534] Turning now to FIG. 16, there is shown an HState transition diagram 16,000. The Accepting_Members state 16,002 indicates that the RxGroup-head has the potential of accepting new RxGroup-members, and Not_Accepting_Members 16,004 state means the opposite. Resigning state 16,006 means that the RxGroup-head is in the process of giving up the RxGroup-head role and is indicating to its dependent RxGroup-members to re-affiliate to a different RxGroup-head.

[0535] The RxLevel indicates the operating level of a RxGroup-member from the sender. In other words, the RxLevel provides the RxGroup hop distance from the sender.

[0536] The Dmem_Count refers to a count of RxGroup-members that a RxGroup-head is directly responsible for. The IndMem_Count of a RxGroup-head refers to the sum total of all RxGroup-members (direct as well as indirect) that the direct RxGroup-members are responsible for.

[0537] The Dhead_Count refers to a count of RxGroup-members that are heads that a RxGroup-head is directly responsible for. The IndHead_Count of a RxGroup-head refers to the sum total of all RxGroup-members (direct as well as indirect) that are heads that the direct RxGroup-members are responsible for.

[0538] The DAdverthead_Count refers to a count of RxGroup-members that are advertising heads that a RxGroup-head is directly responsible for. The IndAdvertHead_Count of a RxGroup-head refers to the sum total of all RxGroup-members (direct as well as indirect) that are advertising heads that the direct RxGroup-members are responsible for.

[0539] Reserved_Head Slots refers to the number of slots the head is reserving for affiliation of other heads. Avail_Member_Slots refers to the number of slots available at the head for members regardless of MRole.

[0540] RxGroup Membership Process

[0541] The sender TRAM initiates the RxGroup membership process by generating session-scope sender-beacons. In HA, the sender-beacon and data messages include the Head Advertisement Interval (HAI) to be used by all heads. Only RxNodes that receive the sender-beacon or data messages are eligible to join the tree. Once the sender is ready to start forming the tree, it starts head advertisement.

[0542] Head Advertisement

[0543] Any head that is affiliated with the tree (including the sender) that still has room for more members sends multicast Head-Advertisement (HA) messages. HAs are sent with increasing TTL, at the interval specified by the HAI sent by the sender in the sender beacon (plus randomization). Affiliated nodes with MRole of Member_ReluctantHead send HAs at half of this rate (plus randomization).

[0544] Each time an HA is sent, the TTL is increased by the HA TTL increment parameter if no additional members made a successful bind to the head during the last two head advertisement intervals.

[0545] The HAI is determined by the sender and may be changed as the tree grows and an increasing number of heads advertise. HAI starts off at ½ second, then adjusts according to the following formula:

[0546] HAI=max(½ second, ((AdvertisingHeadCount*HASize)/MaxHABW), (AdvertisingHeadCount/MaxPackctRate))

[0547] where:

[0548] AdvertisingHeadCount is the number of heads in the tree currently sending HAs.

[0549] HASize is the size of an HA message in bits (approximately bits).

[0550] MaxHABW is the maximum bandwidth allocated For HAs:

[0551] MaxHABWTreeFormation before data transfer

[0552] MaxHABWDataTransfer during data transfer.

[0553] MaxPacketRate is assumed to be 30 packets per second in an exemplary embodiment of the invention.

[0554] Applications control the amount of bandwidth used by HAs with the MaxHABWTreeForm and MaxHABWDataTransfer parameters. The default value for MaxHABWTreeForm is Max_Data_Rate. The default value for MaxHABWDataTansfer is 0, indicating that Head Advertisement is not used for late joins and reaffiliation.

[0555] HAs include:

[0556] The MRole information.

[0557] Original TTL value.

[0558] TTL to sender (if known).

[0559] RTT to sender (if known).

[0560] The address of the multicast data source.

[0561] Unicast port to use to respond.

[0562] Flags.

[0563] RxLevel.

[0564] Dmem_Count and IndMem_Count.

[0565] Reserved Head Slots

[0566] Avail_Member_Slots

[0567] RxNodes wishing to join the repair tree listen for HA messages for a period determined by the following minimization factor after the receipt of either a sender-beacon or a data packet from the data source. The minimization factor is given by:

[0568] HAlisten Time=MIN( (3*HAInterval specified by Data source), 60 seconds)

[0569] At the expiration of this period, the receiver chooses the head that it prefers and binds to it. If the RxNode fails to receive any HA advertisements at the end of the period, the listen period is reloaded. HAI is recalculated every time the sender sends a sender-beacon. Head advertisements stop once a head sees data from the sender. Members wishing to join the tree after data transmission begins must use the “late join” procedure, described below.

[0570] Choosing a Head

[0571] A member chooses a head after listening to HA messages for three head advertisement intervals. The member selects a head based on the following criteria:

[0572] 1. Available slot type (members with MRole Member_Only cannot bind with a head with only head slots available).

[0573] 2. MRole (pick empty reluctant heads only if no other heads are available).

[0574] 3. TTL to the head.

[0575] 4. Tree level (eliminate all but those with the lowest level).

[0576] 5. Member count (choose heads that are close to being fully populated).

[0577] Member Bind

[0578] Once the optimal head is selected, the RxNode attempts to bind with the head by sending it a unicast Head-Bind (HB) message. While waiting for a response, the RxNode continues to monitor HA messages, just in case this bind fails. If the head responds with a unicast Accept-Member (AM) message, the RxNode is bound. If the head responds with a unicast Reject-Member (RM) message (for instance if the head is already full, or only has reserved head slots available and the RxNode's MRole is Member_Only), the RxNode tries to affiliate with the next-best head. If no answer is heard after N_HB_RETXM retransmissions at T_HB intervals, the RxNode gives up on the chosen head and tries the next best one.

[0579] Once an RxNode with an MRole of Member_EagerHead or Member_ReluctantHead is bound to the tree, it starts to send HAs in the same manner as the other heads.

[0580] If the RxNode starts to receive multicast data messages before becoming a RxGroup-member, then the RxNode uses the MTHA late join procedure. HB messages include:

[0581] MRole.

[0582] TTL to sender (if known).

[0583] RTT to sender (if known).

[0584] Original TTL.

[0585] Former RxLevel (used during reaffiliation).

[0586] Unicast port to use to respond.

[0587] Flags.

[0588] Dmem_Count and IndMem_Count (used during reaffiliation). RxGroup-head and RxGroup-member Interaction (RRI)

[0589] RRI plays a crucial role in TRAM and aids in the following operations:

[0590] Detecting unresponsiveness of a dependent RxGroup-member or a dependent

[0591] RxGroup-head.

[0592] Propagation of congestion information to the sender.

[0593] Round trip time (RTT) computations.

[0594] Propagation of RxGroup level, direct and indirect membership counts.

[0595] Informing the RxGroup-members of other RxGroup-heads in the neighborhood.

[0596] The different RRI messages are:

[0597] 1. Hello message.

[0598] 2. Hello-Uni message.

[0599] 3. ACK message.

[0600] The Hello message is a multicast message which is generated by a RxGroup-head on a periodic (T_Hello) basis. Since the RxGroup-heads (non sender) do perform regular data transmissions other than retransmissions, the Hello message acts like a heart beat message to the dependent members. In the case of the sender, the data message itself acts as a heart beat message and as a result the sender generates a Hello message only if the situation requires. The Hello message includes the following details:

[0601] HState.

[0602] CState.

[0603] Current TTL Scope for handling retransmissions.

[0604] RxLevel.

[0605] Multicast data source address.

[0606] Unicast port in use.

[0607] Flags.

[0608] Checksum.

[0609] In addition to the above details, the Hello message supports option fields. In an exemplary embodiment of the invention, two options are defined but only one of them can be used at a time. When options are used, the relevant bits in the flags space are set. Except for the ease when using option two (described below), the Hello message does not require a response.

[0610] The first option is an informatory message to the dependent members. Currently, one such informatory message is to inform the members of the unavailability of one or mere data messages in its cache. This message is rare and is generated in response to retransmission request of an unavailable message from one of the dependent members. This option adds the following details to the Hello message:

[0611] Valid bitmask length.

[0612] Start sequence number of the window of messages being reported missing.

[0613] Bitmask to report the message status.

[0614] The second option is used by the RxGroup heads to cause some of the members to respond to the Hello message. This is typically done to perform RTT computations. (Note the RTT computed is that of multicast path from the head to the member, and a unicast path from the member to the head). In this case the list of members required to respond to the Hello message is included in the option field. The timestamp included in the Hello message is bounced back to the head with the aid of an unicast ACK message by the members listed in the Hello message. This option adds the following details to the Hello message.

[0615] Number of members whose addresses are listed.

[0616] A timestamp that needs to be bounced back.

[0617] List of Addresses of members that need to respond to the Hello message.

[0618] Further, since the Hello message is a multicast message, the Hello message can serve as a means to inform other RxGroup-heads and RxGroup-members in the neighborhood of its existence. This can be used to detect and optimize the number of heads in the neighborhood and can also serve to provide backup head information to other members in the neighborhood. The TTL scope in use field in the Hello message can be maintained by the non dependent members as a backup TTL, and can quickly re-affiliate upon losing its dependent RxGroup-head.

[0619] Hello-Uni is a unicast Hello message that is generated occasionally by a RxGroup-head to one of its RxGroup-members. The Hello-Uni message is generally used for unicast communication with a RxGroup-member. The Hello-Uni message can be used to inform a member of its data latency from the sender or can be used to specifically determine if a member is unresponsive. The Hello-Uni message includes the following details:

[0620] HState

[0621] CState.

[0622] Flags.

[0623] Multicast Address.

[0624] Multicast data source address.

[0625] RxLevel.

[0626] Receiving member's latency (in ms) from the data source as computed by the RxGroup-head.

[0627] The Hello-Uni message requires a member to respond with an ACK message. Every RxGroup member maintains a watchdog timer to keep track of its RxGroup-head. Receiving a Hello/Hello-Uni message or even a retransmission message can cause the timer to be reloaded. If a RxGroup-member misses N_HELLO_MISSES successive Hello/Hello-Uni messages, a re-affiliation/regrouping process begins.

[0628] Every RxGroup-head computes the round trip time between itself and a RxGroup-member, adds its latency from the data source (learnt via its RxGroup-head) and relays the information to the RxGroup-member via the Hello-Uni message. Note that member latency reported in the Hello-Uni message refers to the previously computed latency. Until the RTT is computed, the Hello-Uni message, if generated, will have the receiver's member latency set to zero (0).

[0629] The ACK message is a unicast message that is generated by RxGroup-members. Typically ACK message is used to acknowledge the receipt of multicast data messages that are sent by the sender TRAM, but NACK and various other management information such as RTT, member count etc., are piggy backed in the same message. The details included in the ACK message are:

[0630] MRole.

[0631] CState.

[0632] Multicast address and the multicast data source address.

[0633] Start Sequence number (SSQ) of the window of messages being acknowledged.

[0634] Valid bitmask length (N) or the window length of messages being reported.

[0635] Bitmask to indicate the receive Status of individual messages in the window length.

[0636] Flags.

[0637] Checksum.

[0638] Timestamp received in the Hello message (when applicable).

[0639] Dmem_Count (if any).

[0640] IndMem_Count (if any).

[0641] DAdverhead_Count (if any).

[0642] IndAdvertHead_Count (if any).

[0643] The maximum number of receive message status that can be included in one ACK message is configurable. The details of the ACK mechanism is discussed in a later section.

[0644] The ACK message serves as a heartbeat message for the RxGroup-heads to keep track of its member community.

[0645] The Hello messages are generated only after a member assumes the role of a head. That is, after receiving an AM message from a RxNode. The Hello messages are initially generated based on the TTL computed from the HB message. If the multicast path from the member to a head is not the same as from head to a member, then TTL may not be appropriate, and as a result the member may not be able to receive the Hello messages. Since the head multicasts the retransmissions with a limited scope, it is important that the head use a TTL value that is large enough to reach all the dependent members. The member can detect this condition when the Hellos are not being heard. The member under this condition will inform the head of this condition via the flag field in the ACK message. To ascertain that the head has not gone offline, the member can optionally request the head to send a Hello-Uni message. The head upon receiving the ACK message will increase its TTL and if required, a Hello-Uni message is sent to the member. This process continues until the member indicates the receipt Hellos.

[0646] Late Join Procedure

[0647] Many applications allow users to join the session after some data has been transmitted. These are known as late joins. New members can detect whether or not data transfer has begun by listening for a given time on the multicast address. If no packets are received, the receiver is either outside of the scope of the session, or the session has not yet begun. If a sender-beacon with sequence number zero is received, the member knows the tree is still forming and should soon receive an HA. If a data packet or a sender-beacon with non-zero sequence number is received, the member uses the late join procedure.

[0648] Late joins use either Head Advertisement as described above, or Member-Triggered Head Advertisement (MTHA). Continuing Head Advertisement during data transfer may result in enough extra multicast traffic to disrupt the application. MTHA is available as an alternative for these applications. Late joiners can determine which method is being used by observing the HAI in the sender-beacons and data messages: if the HAI is 0, MTHA is in use.

[0649] MTHA can be a better choice for late joins because it eliminates the need for continuous multicast HAs with session TTL. Receivers that want to join the repair tree send multicast (Member-Solicitation (MS) messages every T_MS seconds to find a head. Any heads (eager or reluctant) that receive this message and are willing to be a head for this node (and are already affiliated with the TRAM tree) send multicast Head-Advertisement (HA) messages using the original TTL from the MS message. A member increases the TTL of its MS message by the MS_TTL increment parameter if no HAs are received during the T_MS period. After an interval of 3*T_MS (plus randomization) seconds from receipt of the first HA, the receiver chooses a head as in HA (described above).

[0650] In order to avoid storms of MS messages, late joins first Listen for MSs for 2*T_MS (plus randomization) seconds before sending. If a local (TTL=original TTL) MS with an identical MRole is heard, it suppresses its own MS and listens for HAs for another 2*T_MS for MS (plus randomization) seconds. If no MSs or HAs are heard during this interval, it send its own MS.

[0651] In order to avoid storms of HA messages in response to MSs, heads that are willing to accept members should listen for MS messages. If they receive one, they can set a timer for one T_MS (plus randomization). When the timer expires, they should look at all MS messages received during that inter interval, then send their HA with the greatest original TTL of any of these incoming MSs. MS messages include:

[0652] MRole.

[0653] TTL to sender (if known).

[0654] RTT to sender (if known)

[0655] original TTL.

[0656] Former RxLevel (used during reaffiliation).

[0657] Flags.

[0658] Dmem_Count and IndMem_Count (used during reaffiliation).

[0659] Re-affiliation of RxGroups

[0660] Re-affiliation is triggered when a group member decides that it wants to affiliate with a different head. This may occur because its old head is resigning or not responding, or because the member has discovered a better head (in terms of closeness). A functioning head can typically resign when the user is attempting to exit out of the multicast group, or when the functioning head has determined itself to be redundant in the region. Detection of a better head and redundant heads in a region are made possible by reception and processing of various multicast control messages generated by the heads and members in a region. The various steps involved in the re-affiliation process are listed below:

[0661] 1. A member decides to re-affiliate. It finds a head that it wants to re-affiliate to (by checking Hellos, HAs, or using MTHA).

[0662] 2. The member uses the normal TRAM affiliation mechanisms to affiliate with the new head (sending a Head Bind and receiving an Accept Member or Reject Member). If this affiliation fails, it goes back to step 1 (finding a head).

[0663] 3. Once the member has affiliated to the new head, it maintains its affiliation to its old head until it successfully receives all missing packets that are earlier than the starting sequence number of the packets that is guaranteed to be cached by the new head. The new head reports the starting sequence number of the packets that will be cached via the AM message. During this interval, the member sends ACKs to both the old and the new heads (unless the old head is dead). If the new head becomes unresponsive during this interval, the member goes back to step 1 (finding a head). This interval is known as the Transition Interval.

[0664] 4. Once the Transition Interval has been completed, the member sends an ACK with the Terminate Membership bit set to its old head. At this point, reaffiliation is complete and the member and the old head forget about each other.

[0665] During re-affiliation, if the member is itself a head, it continues to function as a head and is not allowed to accept new members.

[0666] The whole re-affiliation process is straightforward and simple when the re-affiliating member is not performing the role of a head. When the re-affiliating member is performing the role of a head, certain additional checks have to be performed while selecting the new head so as to avoid forming malformed repair tree or loops.

[0667] Turning now to FIG. 17, a re-affiliation by a head attempting to form an undesirable loop is shown. Typically a loop can be formed when a head higher up in the tree hierarchy re-affiliates with a head that is a descendent of itself. For example as shown in FIG. 17, head B117,002 may re-affiliate with head B11117,004 to form a malformed repair tree.

[0668] TRAM avoids the loop formation shown in FIG. 17 by propagating a tree level information called RxLevel as part of the tree management information. The sender is said to be at RxLevel 1, the heads that are members of the sender's RxGroup are said to be at RxLevel 2 and so on. Loops are avoided by adopting the policy that a member performing the role of a head will not re-affiliate with any head whose RxLevel is equal or greater that its own RxLevel. Further, a head upon losing its heads is unable to find a suitable head for more than 5 minutes is forced to resign. This is important, since members of an unaffiliated head are disconnected from the sender. They may not receive repairs and cannot provide congestion feedback.

[0669] Maximizing Reaffiliated Members

[0670] By adding the former DMEM_COUNT and IndMem_Count to the MS and HB packets, existing heads with limited slots for reaffiliations can choose heads with the most members.

[0671] Standby Heads

[0672] During data transfer, members can have a hot-standby head to use for a quick re-affiliation instead of having to start at the beginning of the HA or MTHA process.

[0673] Standby Heads for HA

[0674] Members of trees that use HA for late joins simply continue to listen to HAs during data transfer, keeping track of the next best head available.

[0675] If the watchdog timer tracking the RxGroup-head expires N_HELLO_MISSES times, the RxGroup-member starts the re-affiliation process by sending a HB message to the selected head. If the member cannot bind with the selected head, reaffiliation falls back on the default HA method.

[0676] Standby Heads for MTHA

[0677] Members of trees that use MTHA for late joins still have a possible way to determine standby heads. Every RxGroup-member, while successfully affiliated to a RxGroup-head, processes the nearby RxGroup-head's multicast Hello messages and maintains a maximum backup TTL value that it may have to use reach one of these neighboring RxGroup-heads. The TTL values from Hello messages that indicate that the HSTATE as Not_Accepting_Members are ignored.

[0678] If the watchdog timer tracking the RxGroup-head expires N_HELLO_MISSES times, the RxGroup-member starts the re-affiliation process by sending a MS message with TTL scope of the message set to the backup head TTL scope maintained (if any, otherwise with expanding scope as in a late join). If the MS sent to the computed TTL scope does not yield HA messages, ERS mechanism will be pursued.

[0679] Specifying the Tree Formation Method

[0680] TRAM's default mode of operation is to use the HA method for tree formation before the sender starts data transmission, and MTHA after. This is intentionally done to form the tree quickly using a higher-bandwidth method (HA), then use a slower, less bandwidth-intensive method once data starts.

[0681] However, some groups or applications may prefer to use only HA or only MTHA throughout the entire session. For that reason, the tree formation method may be specified in the transport profile. The default value, TREE_FORMATION_HAMTHA specifies the default behavior. TREE_FORMATION_HA specifies that HA be used throughout the session. TREE_FORMATION_MTHA specifies that MTHA be used throughout the session.

[0682] Optimizing Tree Formation in Local Area Networks

[0683] If several members of a group are located on a local area network (LAN), neither HA nor MTHA will form an optimal tree. In this case, all members of the LAN are likely to affiliate to heads that are off of the LAN. This can result in extra traffic between the members on the LAN and the off-LAN heads in the event of packet loss.

[0684] A more optimal tree is formed in this case by electing a single head on the LAN, and having only that head affiliate off of the LAN. If necessary, extra heads on the LAN can form a subtree under the LAN head.

[0685] LAN trees are formed using a slight variation on the existing tree formation methods. The changes allow LAN tree formation to finish before the timeouts controlling off-LAN tree formation expire. Whether using HA or MTHA, LAN members send HA packets to the LAN only (using a TTL of 1), and elect a LAN head just as in the usual HA method. Once this head has been elected, the tree formation method continues as usual. Since it is the closest head to any member on the LAN, the elected LAN head will always be selected for affiliation by members on the LAN. If the elected LAN head cannot handle any more members, additional heads are elected from those already affiliated with the LAN head.

[0686] LAN tree formation is not enabled by default because it does result in more multicast traffic, and only helps groups with multiple members on a LAN. It can be enabled using the setLanTreeFormation method in the transport profile.

[0687] Data Transmission

[0688] The sender in a TRAM application transmits data packets to every receiver in the multicast group. TRAM sends the packets at a specified rate. Each packet is given a unique sequence number starting with one (1). Receivers use these numbers to detect out of order and missing packets.

[0689] Data Retransmissions

[0690] When the sender receives a request for retransmitting a packet, it queues the requested packet up immediately. Retransmissions take priority over new data packets. Retransmitted packets are sent at the same rate as regular data packets from the sender. Repair heads compute the average data rate of all packets it receives and sends retransmissions at this rate.

[0691] The sender in a TRAM application multicasts data packets to all of the receivers in the multicast group. The application calls the putPacket method (or write method for the stream interface) to queue up packets for transmission. The output dispatcher sends the packets at the specified rate. Each packet is given a unique sequence number. Receivers use these numbers to detect out of order and missing packets.

[0692] Duplicate Retransmission Avoidance

[0693] When several members request retransmission of the same packet, TRAM sends the packet immediately for the first request. Subsequent requests are ignored if they are received within a set time, for example one second, of the first request.

[0694] Occasionally many packets are queued up waiting for retransmission. If a new request for a packet is received and that packet is already on the transmit queue, the request is ignored.

[0695] Acknowledgments

[0696] Reliable transmission in TRAM is achieved with acknowledgments. Members use an ACK window to trigger sending an acknowledgment message to their repair head. The ACK window expires when a packet with a sequence number greater than or equal to the end of the next window arrives.

[0697] Members acknowledge one ACK window of packets at a time to their repair head. The ACK window size is configurable; the default is 32. For example, in the default case, members send ACKs every 32 packets.

[0698] To avoid multiple members sending ACK messages at the same time, and to possibly expedite repairs, ACK messages are distributed over the window. Each member selects a random packet between 1 and the ACK window size to start sending ACK messages. For example, one member may send ACKs at packets 32, 64, 96; etc., while another sends ACKs at packets 10, 42, 74, etc.

[0699] Acknowledgments are also sent if a timer equal to 1.5 times the estimated ACK interval expires. The estimated ACK interval is computed at each receiver when an ACK is sent. It estimates the amount of time it takes to receive an ACK window's worth of packets. The formula is:

[0700] ACKinterval=ACKwindow*(Time since last ACK/Packets since last ACK)

[0701] This timer is canceled if an ACK is sent using the triggering mechanism described above. If this timer expires, it indicates that the sender has paused and allows members to report and recover any lost packets without having to wait for the sender to start sending new data.

[0702] Each ACK message contains a start sequence number and a bit map length. If no packets were missing, the bit map length is “0” and the sequence number indicates that all packets prior to and including this packet were successfully received. The repair head saves this information and uses it to remove packets from its cache.

[0703] If there are one or more missing packets, the start sequence number indicates the first missing packet. A bit map must follow. Each bit in the map represents a packet sequence number starting with the start sequence number. If the bit is set, that packet is missing and must be retransmitted. A bit map length indicates how many valid bits are present.

[0704] When the repair head receives an ACK message with a “missing packets” bit map, the sequence number specified minus 1 is saved for this member. This indicates that all packets prior to and including this sequence number have been received successfully. The repair head then scans the bit map looking for missing packets. It immediately places these packets onto the transmit queue unless they have recently been retransmitted is or are already on the queue from another request.

[0705] Flow Control

[0706] In TRAM the sender maintains a data rate between a minimum and maximum specified rate. The rate is increased every two (2) ACK windows and decreased for each new congestion report. If the senders data cache fills up, the sender stops sending new data until it can reduce its cache below the high water mark.

[0707] The actual rate scheduler is implemented as follows. When the application places a packet on the transmit queue, the output dispatcher sends the packet on the multicast socket. It then computes the amount of time to delay in order to achieve the desired data rate. The delay is computed with the formula:

[0708] packet size/desired rate

[0709] The overhead in processing the packet is subtracted from this delay. The output dispatcher then sleeps for the calculated period and the cycle continues.

[0710] Slow Start

[0711] The initial data rate starts at 10% of the maximum or the minimum rate if that is greater. Every two (2) ACK windows this rate is increased another 10% of the maximum data rate. This process continues until the maximum rate is reached or congestion causes the rate to decrease.

[0712] Congestion Reports

[0713] Congestion reports from the receivers, in an exemplary embodiment of the invention, cause the data rate to drop 25%. After congestion the rate increments are more conservative in an attempt to alleviate the congestion. The new rate increment is computed from the previous rate increment value as follows:

[0714] new rate=current rate+((last increment rate−current rate)/4)

[0715] This algorithm allows the data rate to increment quickly back to the point where congestion was reported.

[0716] Congestion Control

[0717] Congestion is detected at the receivers and repair nodes. Receivers detect and report congestion based on missing packets. Repair heads detect and report congestion based on their cache content.

[0718] Rate Based Congestion Detection

[0719] Receivers detect and report congestion when the number of outstanding missing packets between two ACK windows increases. For example:

[0720] If a receiver detects five (5) missing packets during the last interval and has ten (10) packets missing in the next interval, a congestion message is sent to its repair head. The congestion message contains the highest sequence number received. When the repair head receives the congestion message, it determines whether this is a new congestion report and if so, forwards it immediately up to its repair head. Each head will forward one congestion packet from its members for each ACK window. The head computes the ACK window from the sequence number specified in the congestion message with the formula:

[0721] sequence number/ACK window

[0722] The repair head will send one congestion message up the tree for each ACK window. Once a congestion message has been forwarded up the tree, congestion reports for previous ACK windows will be ignored. The sender will also ignore any congestion messages for the same or earlier windows.

[0723] Cache Based Congestion Detection

[0724] Repair heads also generate congestion messages when their data cache begins to fill up. Each head maintains a low and high water mark on their cache. When the number of packets in the cache reaches the high water mark, an attempt is made to purge the cache back to the low water mark. If it can't purge the cache below the high water mark because a member has not acknowledged these packets, a congestion message is forward up the repair tree. In this situation the repair head increases its high water mark to the current value plus the number of packets in an ACK window. The repair head performs the same test when this new threshold is reached.

[0725] The sequence number in repair cache generated congestion message is the highest sequence number the head has received.

[0726] Late Joins

[0727] If a receiver joins the multicast group after data transmission has started, it has two options in TRAM.

[0728] Recover as much previously sent data as possible. This option allows the receiver to ask for retransmissions of all the previously sent data that its repair head has cached. A repair head typically has at least the last 50 packets sent in its cache.

[0729] Do not recover anything sent before the receiver joined. This option doesn't attempt to recover any previously sent packets. The first data packet received after the new member joins the repair tree is handed up to the application. All previously sent packets are ignored.

[0730] Both of the above options require that the receiver join the multicast repair tree before any data is given to the application. The method setLateJoinPreference is used to select one of the options listed above. Valid arguments to this call are:

[0731] LATE_JOIN_WITH_LIMITED_RECOVERY

[0732] LATE_JOIN_WITH_NO_RECOVERY

[0733] End of Transmission

[0734] When the sender application closes the socket, end of transmission is signaled throughout the multicast group. The sender notifies all members of this with a beacon packet that has the TXDONE flag set. This packet also includes the last data packet sequence number sent. The sender transmits this packet periodically until all of its immediate members acknowledge the receipt of all packets sent. The sender can then close its session.

[0735] When a member receives the Beacon packet with the TXDONE flag set, it immediately sends an ACK message to its head indicating whether it has received all the packets transmitted or requires more retransmissions. The receiver returns a SessionDone Exception to the application when the application has received all the packets.

[0736] When the repair head receives the Beacon packet with the TXDONE flag set, it communicates with its head just as a receiver does. The head must wait for all for all of its members to respond with their final ACKs before it can close the session. If a member requires retransmission, the head must retransmit all the packets required of its members prior to closing itself. If the Beacon from the sender with the TXDONE flag set is received but one or more members do not respond with their final ACK message, a Hello message is sent to these members with the same information contained in the Beacon packet. Members receiving this Hello message must respond in the same way they would had they received the Beacon. If the head still doesn't hear from its members after sending the Hello, it retries several times. After a period of time it gives up on the member and removes it from the member list.

[0737] When all members have either sent their final ACK message to the head or have been removed from the member list because they were not responsive, the head can close its session.

[0738] TRAM Operation

[0739] TRAM operation is best described by considering the TRAM protocol at the sender and at the receiver separately.

[0740] TRAM at the Sender

[0741] The sender application opens the TRAM session by specifying the transport profile. The transport profile includes details such as the multicast address, port, minimum and maximum rates of transmissions, Transport mode, and various other protocol related parameters. The sender TRAM, after validating the transport profile, joins the multicast group. As the Transport mode in this case is SEND_ONLY, the transport assumes the role of Group-head and starts generating the sender-beacon to initiate the RxGroup formation process. TRAM relies upon the application to decide when it is appropriate to start the multicast data transmission. TRAM maintains information such as the size of the tuned receiver community at anytime which can be polled by the application to make this decision.

[0742] As the application provides the multicast data to be transmitted, the messages are put on DataQ and are scheduled for transmission at the rate controlled by the slow start mechanism. The slow start mechanism involves starting the data transmission at a minimum rate and gradually increasing the data rate in steps until a suitable maximum rate is achieved. Under congestion, the sender TRAM opts to transmit at the minimum rate so as to alleviate and allow repair operations to take place. Sender TRAM provides no data rate guarantees other than attempting to hand over multicast data to the underlying network layer with in the transmission framework specified by the application. The rate at which the data messages are handed over to the lower layer is with reference to the messages on the DataQ (or messages that are being transmitted for the first time) and do not take into account the messages that are being retransmitted.

[0743] The data message is encapsulated in a TRAM header message and is sent to the multicast group. The TRAM header among other things, include a sequence number which enable the receiver TRAMs to order (if required) and detect packet loss. After transmission, the message is moved to the Retrans-Q. The RxGroup-members use a window mechanism to acknowledge the receipt of the multicast messages. The message on the RetransQ undergoes the state transition (described earlier) before being freed. If data cache usage is found to be above the high water mark, then the congestion control and analysis operation on the RetransQ is initiated to isolate and recover from the condition.

[0744] The RxGroup-members upon detecting data loss, requests retransmission from the RxGroup-head. The sender performs the retransmissions using the local TTL scope. If a retransmission request is made for a message that has been released from the data cache (typically as a result of re-affiliation), the sender informs the unavailability of the message via a Hello message. This is one of the rare occasions when the sender TRAM generates a Hello message.

[0745] The DATA_END sub message type in the data message indicates the end of data transmission. Further, to enable the receivers to identify that the data transmission has ended, the sender continues to send a few sender-beacons with data transmission complete bit set in the flag space. The sender-beacon also includes the sequence number of the last message. This will enable the receivers that may have missed the last message request retransmissions from their heads. When all the data messages have been successfully received, the members can terminate their RxGroup membership. The RxGroup-heads have to stay on until every member acknowledges every message on the RetransQ. Optionally the sender TRAM can be configured to remain active for a specified interval of time to gather certain statistics related to the multicast data transmission. The sender-beacon is used under this condition to maintain the RxGroup relationship.

[0746] TRAM at the Receiver

[0747] The receiver application starts the TRAM session by specifying the transport profile. The receiver TRAM, after validating the transport profile, joins the multicast group and stays idle until the sender-beacon is received. Upon receiving the sender-beacon or the multicast data message or a HA message from another node, the receiver TRAM starts participating in the RxGroup-formation process.

[0748] A RxGroup-member intending to be a RxGroup-head can optionally cache the multicast data before actually assuming the role. RxNode(s) can receive and store the multicast messages on their RetransQ but are not allowed to seek retransmissions until they are affiliated to a RxGroup-head. The receiver TRAMs acknowledge the received multicast messages with the help of the ACK messages.

[0749] RxGroup-members willing to perform the role of the head can send HA messages. The RxGroup-member starts performing the role of a head upon receiving the first AM from a RxNode. The Hello messages are initially generated using the extracted TTL from HB messages. If the multicast path to the member is not symmetric, then the TTL may not be appropriate. The member will inform the head if the Hellos are not being received. In this case the head will have to go through a correction phase until the member indicates that the Hellos are being received.

[0750] Retransmissions are multicast by the head (s) with a TTL scope that is just enough to reach its farthest RxGroup-member. The TTL, value is maintained and updated by the RxGroup-head every time a new member is accepted.

[0751] The TRAM at the receiver can be configured to continue or abort when late join or irrecoverable data loss is detected. If data loss is accepted, TRAM signals the event to the application.

[0752] FIG. 18 is a chart showing various messages and sub-messages used in TRAM. Multicast management, or MCAST_MANAGEMENT messages have Sub-Message types as follows: BEACON; HELLO; HA Head Advertisement; and, MS Member Solicitation. Multicast data, or MCAST_DATA messages have the Sub-Message types: DATA as a TRAM data message; and, DATA_RETXM for data re-transmission messages. Unicast messages, or UCAST_MANAGMENT messages have the Sub-Message types: AM Accept Membership Message; RM Reject Membership message; HELLO_Uni a hello message with an ACK request; ACK an acknowledge message; CONGESTION, a rate based congestion message; and, HB the TRAM head bind message.

[0753] FIG. 19 is a table showing the timers used by TRAM. The T_BEACON timer is the inter beacon message interval timer, and in an exemplary embodiment of the invention is set to 1,000 milliseconds (ms). The T_BEACON_FILLER timer is the inter beacon filer interval timer, and in an exemplary embodiment of the invention is set to 30 seconds (sec). The T_ACK_INTERVAL is computed at run time based on the current rate of data transmission and the size of the configured acknowledgment window. The T_HELLO timer is the inter Hello interval timer, and in an exemplary embodiment of the invention is set to one (1) per ACK interval. The T_MS timer is the inter MS interval timer, and in an exemplary embodiment of the invention is set to 500 milliseconds (ms).

[0754] FIG. 20 is a table showing counters used by TRAM. N_ACK_MISSES is the number of ACK messages that can be missed before a head declares the member as non-responsive, and in an exemplary embodiment of the invention is set to a value of four (4). N_HELLO_MISSES is the number of HELLO messages that a member has missed for the member to declare the head as non-responsive, and in an exemplary embodiment of the invention is set to a value of five (5). N_HB_RETXM HB head bind message can be sent before the member tries another head, and in an exemplary embodiment of the invention is set to a value of three (3). N_MS_RETXM is the number of times a MS member solicitation message needs to be sent before a head increases its TTL.

[0755] FIG. 21 through FIG. 30 give the fields of the different messages used in TRAM. The figures conventionally show 32 bits (bits 0-31) horizontally as a word. Successive 32 bit words are shown vertically. Each word is divided into 8 bit bytes, although some fields occupy two 8 bit bytes, or sixteen bits; and some occupy all 32 bits of a word. All of the messages have the first word having the four byte fields: Ver # giving the version number of the software; MType giving the message type; Sub-Type giving the message sub-type; and FLAGS giving eight 1 bit flags, to be described hereinbelow. Also, all messages have the “Length of the message in bytes” in the first two bytes of the second word. The other fields of each message are selected for the particular message, as shown is in FIG. 21-FIG. 30. The fields marked “Reserved” have not been assigned to a function.

[0756] FIG. 21 is a block diagram showing a multicast packet format for a sender Beacon Message. FIG. 22 is a block diagram showing a multicast packet format for a Data Message. FIG. 23 is a block diagram showing a multicast packet format for a HA Message. FIG. 24 is a block diagram showing a multicast packet form at for a MS Message. FIG. 25 is a block diagram showing a multicast packet format for a Hello Message. FIG. 26 is a block diagram of a unicast packet format for a ACK Message. FIG. 27 is a block diagram of a unicast packet format for a Hello Uni Message. FIG. 28 is a block diagram of a unicast packet format for a Head Bind Message. FIG. 29 is a block diagram of a unicast packet format for a Accept Membership Message. FIG. 30 is a block diagram of a unicast packet format for a Reject Membership Message.

[0757] FIG. 31 through FIG. 36 give the FLAG field for the indicated messages. The eight (8)bits of the flag field are shown as bit 7 through bit 0. Each bit is shown separately. Arrows lead to an explanation of the purpose of the bit. The bits which are not labeled have not been assigned a function, and so are reserved.

[0758] FIG. 31 is a block diagram of flag fields for a Sender Beacon Message. FIG. 32 is a block diagram of flag fields for a Hello Message. FIG. 33 is a block diagram of flag fields for a ACK Message. FIG. 34 is a block diagram of flag fields for a Hello Uni Message. FIG. 35 is a block diagram of flag fields for a HA Message. FIG. 36 is a block diagram of flag fields for a Bind Message.

[0759] 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.

[0760] 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 of FIG. 25, transmitted by repair head stations.

[0761] 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.

[0762] Furthermore, the terms and expressions which have been employed are used as terms of description and not of limitation, and there is no intention, in the use of such terms and expressions, of excluding any equivalents of the features shown and described or portions thereof, but it is recognized that various modifications are possible within the scope of the invention claimed. It is to be understood that the above described embodiments are simply illustrative of the principles of the invention. Various other modifications and changes may be made by those skilled in the art which embody the principles of the invention and fall within the spirit and scope thereof.