Method and apparatus for multi-tiered data multicasting

METHOD AND APPARATUS FOR MULTI-TIERED

DATA MULTICASTING

0003Reference to Related Application

0004The present application claims the benefit of provisional Application Serial No.

000560/173,872 filed on December 30, 1999, which is hereby incorporated herein by reference.

BACKGROUND

0007Field of the Disclosure

0008The present disclosure relates to multicasting of data, and in particular to a method and

0009apparatus for multi-tiered data multicasting.

0010Description of the Related Art

0011There are several fundamental types of methods for transmitting data on a network,

0012including IP Unicast designed to transmit data (or a packet) from sender to a single receiver and

0013IP Broadcast designed to transmit data from a sender to an entire subnetwork. A third method,

0014known generally as multicasting, involves the transmission of a message from one node in a

0015network to a plurality of other nodes in such a way that the sending node does not need to send

0016the data individually to each of the receiving nodes.

0017Multicasting has been carried out on local area networks. In Ethernet type single

0018transmission line networks, multicasting is carried out by addressing the message to the appropriate receiving nodes. All the receiving nodes receive the package at the same time, as all

0019the nodes can listen to the single transmission line contemporaneously. Multicasting may also

0020be implemented in token ring based networks. In token ring based networks, multicast packages

0021travel around the ring and are retrieved by the intended recipients, and passed on.

0022It is impractical for the traditional multicast type systems mentioned above to be used on

0023wide area networks such as the Internet due to the huge amount of bandwidth required.

0024Accordingly, more recently, systems have been developed for multicasting over wide area

0025networks, including the Internet. One system which attempts to deal with multicasting over

0026wide area networks is referred to as IP Multicast.

0027In an IP Multicast type system, all receivers are configured as members of the same

0028multicast group. A sender sends an IP packet to a multicast address and lets the network

0029forward a copy of the packet to each group of hosts. The group member node then informs the

0030next network node along the shortest route to the multicasting node which may then elect to join

0031the multicast group, and so on up the chain to the multicasting node. These group member

0032nodes then provide a tree distribution structure which allows a package to be multicast to all

0033destination nodes.

0034However, the IP Multicast type system does not take into account the different

0035bandwidths available on the different links. IP Multicast is designed for realtime transmissions,

0036and if a node cannot receive at the rate of transmission of the sending node, the receiving node

0037must be selective in the packets it receives. That is, in IP Multicast, the sender sends data to

0038multiple receivers with a User Data Protocol (UDP). The UDP, unlike TCP, only malces a best

0039effort to deliver data. If a transmission error occurs, the packet is discarded. This may work fine for sound or picture transmissions, as the packet structure can be set up so that a lower

0040quality version of the transmission can be received when receiving only a subset of the packets.

0041For example, this might be done by putting lower frequency components of the transmission in

0042certain packets and higher frequency components in other packets which can be discarded if

0043necessary. However, this system may not be adequate in all instances, including those in which

0044a higher quality transmission is required. Accordingly, although a system such as IP Multicast

0045can be used for non-critical transmissions, wherein a receiving node can compensate for lost

0046packets, it may not be suitable in situations where a package is to be multicast, and each

0047receiving node is to receive each packet constituting the transmitted package.

0048Various other problems may occur with the above-mentioned systems, particularly when

0049different receiving nodes have different bandwidth connections to the transmitting node.

0050Transmitting a package at the bandwidth of the lowest link on the network is highly inefficient,

0051as nodes with high bandwidth connections have to spend a much longer period receiving the

0052package, unnecessarily tying up resources on these nodes. Transmitting the package at a higher

0053data rate than can be received by a receiving node with the lower bandwidth connection will

0054lead to many of the packets not reaching some destination nodes. Different nodes in the

0055network might discard different packets, and therefore if the nodes need to receive all packets,

0056the transmitting node might have to retransmit a substantial portion of the package several

0057times.

0058Attempts can be made to overcome these problems by partitioning the receiving nodes

0059into groups according to bandwidth capability. Certain packets may then be designated to be

0060received by the lower bandwidth groups, and other packets designated as ones which can be discarded. Ignoring packets which might be lost for other reasons, such as local network

0061congestion, when packets need to be resent to the nodes with lower bandwidth connections, each

0062of these nodes will be missing the same designated packets. The sending node therefore only

0063has to retransmit these missing packets. Although this may be more efficient than a system

0064where different packets are resent to different nodes, when a packet is resent, it still has to travel

0065all the links in the network from the sending node to the receiving node. This requires the use of

0066a large amount of bandwidth and processor time in the routing nodes, and in particular, in the

0067transmitting node which has to handle all the "negative acknowledgments" (NAcks) requesting

0068retransmission of packets.

0069In most networks, generally nodes on the periphery have low bandwidth connections,

0070while links between higher level nodes, which will often form the higher level branch nodes in a

0071multicasting distribution tree, have higher bandwidth. The systems presently in place do not

0072make efficient use of this generally hierarchical pattern of bandwidth which exists in most

0073networks.

SUMMARY

0075A method for multicasting data on a network, the network including a plurality of nodes

0076for routing data, the nodes including connections forming a distribution tree. The method

0077comprises receiving at a storing node, data sent from a higher level node on the network,

0078storing the received data in memory at the storing node and transmitting the data stored at the

0079storing node to lower level nodes on the network, wherein any communication required for the

0080transmission of such data to the lower level nodes on the network is not passed further up the distribution tree. The method may further comprise creating a list at the storing node

0081identifying the data transmitted to the lower level nodes on the network. The method may

0082further comprise transmitting the list to the lower level nodes on the network. Each lower level

0083node may compare data actually received, to the data identified in list to determine if all data

0084arrived, and if a lower level node determines that at least a part of the data did not arrive, a

0085negative acknowledgment may be sent back up the tree. When the node that sent the data

0086receives the negative acknowledgment, it may intercept the negative acknowledgment and not

0087send the negative acknowledgment any further up the tree. When the node that sent the data

0088receives the negative acknowledgment, it may determine what data was not received by the

0089node below and resend the at least part of the data not received back down the tree to the node

0090that sent the negative acknowledgment. Each storing node may maintain a list of the lower

0091level nodes to which it is responsible for sending the data. Each lower level node may send a

0092positive acknowledgment back up the tree to the node responsible for sending the data to it,

0093when the data has been received. After a storing node receives positive acknowledgments from

0094each of the nodes on its list of the lower level nodes to which it is responsible for sending the

0095data, the storing node may delete the data from memory. After the storing node receives

0096positive acknowledgments from each of the nodes on its list of the lower level nodes to which it

0097is responsible for sending the data, the storing node may send a positive acknowledgment up

0098the tree to a storing node responsible for sending it the data.

0099An apparatus is also disclosed for serving as a node on a network of nodes for routing

0100data, the network nodes including connections forming a characteristic distribution tree. The

0101apparatus comprises an input for receiving data from a higher level node on the network, at least one output for outputting the data to lower level nodes on the network and storage for

0102storing the data, wherein the apparatus is responsible for transmitting all the data it has stored to

0103the lower level nodes, and wherein any communication required for the transmission of such

0104data is not passed further up the distribution tree.

0105A computer readable medium is disclosed including computer executable code for

0106multicasting data on a network, the network including a plurality of nodes for routing data, the

0107nodes including comiections forming a characteristic distribution tree. The computer readable

0108medium comprises code for receiving at a storing node, data sent from a higher level node on

0109the network, code for storing the received data in memory at the storing node and code for

0110transmitting the data stored at the storing node to lower level nodes on the network, wherein

0111any communication required for the transmission of such data to the lower level nodes on the

0112network is not passed further up the distribution tree.

BRIEF DESCRIPTION OF THE DRAWINGS

0114A more complete appreciation of the present disclosure and many of the attendant

0115advantages thereof will be readily obtained as the same becomes better understood by

0116reference to the following detailed description when considered in connection with the

0117accompanying drawings, wherein:

0118Figure 1 shows an example of a network upon which the present disclosure may be

0119applied;

0120Figure 2 shows a spanning tree superimposed upon the network shown in Figure 1;

0121Figure 3 is a diagram for explaining the hierarchal nature of a spanning tree; Figure 4 shows an example of a branch of a multicast tree;

0122Figure 5 is a flow chart for describing a process that may be performed by a storing

0123node according to the present disclosure;

0124Figure 6 is a flow chart for describing another process that may be performed by a

0125storing node according to the present disclosure;

0126Figure 7 is a flow chart for describing steps performed at a distribution node if the

0127spanning tree should change;

0128Figures 8A and 8B are flow charts describing processes performed by a storing node

0129according to another embodiment;

0130Figure 9 is a flow chart for describing processes performed by a storing node according

0131to another embodiment; and

0132Figure 10 is a block diagram showing exemplary elements of a storing node according

0133to an embodiment.

DETAILED DESCRIPTION

0135In describing the embodiments illustrated in the drawings, specific terminology is

0136employed for sake of clarity. However, the present disclosure is not intended to be limited

0137to the specific terminology so selected and it is to be understood that each specific element

0138includes all technical equivalents which operate in a similar manner.

0139The method and system for multi-tiered multicasting as described in the present

0140disclosure are ideally suited to operate on any network on which the bandwidth for a particular

0141set of packages might vary over different network links. Most networks that consist of more than a single unabridged LAN will have links of varying bandwidth. An example of such a

0142network is shown in Figure 1 and is referred to generally as network system 1. Distribution

0143server node (DS) 10 is capable of multicasting packets of data which together form a package,

0144to one or more nodes in the network. The nodes designated to receive multicasting packets of

0145data for a particular transmission are also identified as target nodes (T) 14. Nodes between the

0146distribution node 10 and the target nodes (T) 14 used for relaying the packets for a particular

0147transmission, are referred to herein as relay nodes (R) 12. It should be noted that the relay

0148nodes 12 and the target nodes 14 may change for particular transmissions. A node may be a

0149workstation, laptop, server, router, etc. Network 1 has appropriate routing set up so that any

0150particular transmission of a set of packets between a first node and a second node will follow

0151the same non-looping route. Such routing mechanisms are well known in the art for various

0152different network architectures, such as Local Area Network (LAN) bridging arrangements,

0153Asynchronous Transfer Mode (ATM) networks and X25 networks, and such routing issues will

0154therefore not be described in further detail herein.

0155When a single non-looping route is normally used between any two nodes, any set of

0156routes from a single distribution node to any set of target nodes will form a tree (spanning tree)

0157with the distribution node at the top of the tree, and the target nodes forming other nodes in the

0158tree. An example of such a tree is depicted in Figure 2, which shows a spanning tree

0159superimposed on the network of Figure 1. The solid lines with arrows, identify the routes taken

0160when packets are sent from distribution node 10 to one or more target nodes 14. Such a tree

0161does not have to be defined explicitly if the routing mechanism used allows only a single route

0162between any two nodes. The spanning tree can be generated for a particular distribution node and set of target nodes before implementing the distribution mechanism of the present system

0163to be described below. That is, the routing might change dynamically because of network

0164problems, congestion or the like. The present system and method can easily be designed to

0165handle such dynamic changes, as will become apparent.

0166This embodiment of the present system sends packages of data as multiple packets of

0167data across a network from a distribution server (DS) 10 to one or more destination or target

0168nodes (T) 14 on network 1. It will be appreciated that the distribution server 10 does not need

0169to be located at a particular node in the network, but might be different for different packages.

0170In this case, a spanning tree will be present, or can be created, for any set of nodes required.

0171For example, if a node 12 is acting as the distribution server, a spanning tree could be generated

0172for node 12 and the appropriate set of target nodes before implementing the distribution

0173mechanism of the present disclosure. As will be described below, the distribution server is

0174capable of instructing a node that it is part of a distribution group.

0175In most network arrangements, the server acting as the distribution node will have a high

0176bandwidth connection to its nearest neighbors, and will often be in a fairly central location in the

0177network in direct connection with the highest bandwidth links of the network. The target nodes

0178will often be at the periphery of the network, and may, for example, be at remote locations with

0179modem connections to the overall network. Therefore, the spanning tree formed between the

0180distribution server and the target nodes will typically include higher bandwidth links at the top

0181of the tree and lower bandwidth links at the bottom of the tree. However, although the network

0182arrangement need not necessarily fit this model, the closer the tree is to fitting this model, the

0183higher the bandwidth savings associated therewith will be for the present system and method. If the distribution server is on a low bandwidth connection to the rest of the network, packages to

0184be delivered will generally have to be distributed over low bandwidth links to the higher

0185bandwidth linlcs before being passed back down to other lower bandwidth linlcs associated with

0186the target nodes. This will lead to a tree with low bandwidth links at the very top of the tree, but

0187the lower parts of the tree will still have a decreasing bandwidth structure as described above,

0188and the present method and system will accordingly improve bandwidth usage over these parts

0189of the network.

0190In addition, if the distribution server is on a low bandwith link, the system may also be

0191arranged such that the distribution server is capable of looking for a node to transmit the data to

0192that has higher bandwith links to its nodes, thereby improving bandwith usage higher in the tree.

0193The hierarchal nature of a spanning tree, for use in explaining an embodiment of the

0194present disclosure, is shown more clearly in Fig. 3 and is referred to generally as tree 100. Tree

0195100 includes DS 10 at the top of the tree, and target nodes 24-31. Each node is connected to a

0196link 4. Although linlcs 4 are described as providing a connection between nodes, it should be

0197clear that this need not necessarily refer to a physical connection. Nodes 21, 24 and 25 function

0198as storing nodes as will be described later below.

0199According to this embodiment, a package is multicast from the DS 10 to each of its child

0200nodes, which in this embodiment are relay node 20 and target node 21 in the tree, as a sequence

0201of packets. The addresses of the child nodes which are to receive the package are incorporated

0202in the addressing of the package. For example, such addressing may be achieved by assigning a

0203recipient group address to the package, using a similar mechanism to that used by IP Multicast.

0204However unlike IP Multicast, in which a user's host application requests membership in a multicast host group associated with a particular multicast, in the present system, intermediate

0205nodes are instructed that they are group members by distribution node 10, rather than choosing

0206to become group members themselves as occurs in IP Multicast. The nodes can be instructed

0207that they form part of the multicast group by unicasting an initialization message to each target

0208node. Each intermediate node that the unicast message passes through is instructed that it forms

0209part of the distribution group. Each intermediate node may maintain a list of its own child

0210nodes, so that it is able to assist in the multicasting of a packet to the associated group. It will be

0211appreciated that a large number of methods may be used to provide intermediate routing nodes

0212with the necessary information to forward a packet addressed to a certain group of nodes to the

0213appropriate child nodes. Routing information could even be encapsulated with each packet,

0214although this may not be the most bandwidth efficient manner of accomplishing the task.

0215According to the present embodiment, when a package is multicast from the distribution

0216node 10, it will be multicast as a sequence of packets. The rate at which the packets can be sent

0217along each of the linlcs 4 from the distribution node 10 to its child nodes 20, 21 may vary

0218depending on the overall bandwidth of the links 4 and the amount of other traffic passing along

0219the linlcs. There are other methods by which the distribution node 10 could transmit the packets

0220to the child nodes, and the most efficient of these will depend on various hardware and protocol

0221considerations. For example, if the transmission is taking place over a standard packet-

0222switching router, the packets may be placed in a queue associated with each link along with

0223other traffic which is also being transmitted along the linlcs. The packets may then be sent using

0224a "fair queuing" type algorithm, by which packets in a particular package being sent between a

0225particular source and destination are sent in fairly regularly spaced time-multiplexed slots. The rate of packet transmission between nodes is based on various weighting factors and

0226the amount of network traffic passing along the links 4. If packets constituting a package are

0227added to the queue at a greater rate than they can be sent with the bandwidth allocated to them,

0228packets may be discarded. Accordingly, if this were to occur in an intermediate node, the

0229percentage of packets that will malce it to each of its child nodes may vary depending on the

0230bandwidth and traffic flow on each of the linlcs. If, for example, the child nodes 20, 21 are all

0231located on the same unabridged LAN, the package could be multicast from the distribution node

0232to each child node simultaneously. However, there is still the possibility that packets could be

0233lost and not reach any of the child nodes, depending on the queuing algorithm and the protocol

0234being used.

0235To avoid packets being lost, according to an embodiment of the present system and

0236method, some intermediate nodes are enabled to store packets. These nodes are referred to

0237herein as storing nodes. Storing nodes may perform some or all of the functions typically

0238associated with the other nodes on the network, including relaying data to the target nodes on

0239the network. A storing node may itself function as a target node. When a storing node is also a

0240target node, it is referred to herein as a storing target node. When packets forming part of a

0241multicast are received by a storing node, the storing node is programmed to retain in memory a

0242copy of each packet forming the package. The storing node then forwards the packet to each of

0243its child nodes using whatever mechanism is most appropriate. For example, as described

0244above, the packets can be added to the appropriate queues for the appropriate network links and

0245distributed using the "fair queuing" type algorithm.

0246A block diagram of a storing node is shown in Fig. 10. In addition to including the hardware and software necessary for routing data to the appropriate destination, the storing

0247nodes include one or more software applications 42 for performing one or more of the processes

0248described below. The storing node also includes memory 44. Memory 44 may include memory

0249for storing applications performed by the storing node, work area memory, memory for

0250providing the queues used for storing data being routed to the appropriate destination nodes, etc.

0251Although shown separately, Applications 42 may be stored in memory 44. Storing node 25

0252includes input 40 for receiving data communicated via link 4. Storing node 25 may also include

0253one or more outputs 46 for routing the data via one or more linlcs 4 to destination nodes.

0254In the example shown in Fig. 3, nodes 20 and 21 are child nodes of distribution node 10,

0255with node 21 being a storing node. Nodes 24 and 25 are storing nodes and target nodes (storing

0256target nodes). Nodes 26-31 are target nodes, and nodes 20 and 22 in this example, serve as relay

0257nodes.

0258If a packet is not received, for example, by node 25, and it has been determined by node

025925 that it is likely that the packet should have been received, node 25 will send a Negative

0260Acknowledgment (NAck) back up the tree requesting that the packet be resent. However,

0261instead of sending the NAck up the tree to distribution node 10, the parent storing node 21

0262(parent with respect to node 25), which has maintained a copy of the packet, will receive the

0263NAck from node 25 preventing it from going further up the tree, identify the packet not received

0264and re-queue the packet for sending to node 25 without any communication passing further up

0265the tree. Thus, once a packet has reached a storing node, the packet does not need to be resent

0266over any linlcs in the tree which are higher than that node in the tree. This greatly reduces

0267bandwidth requirements, and substantially eliminates any overloading of the distribution node 10 if each target node communicates directly with the distribution node. It should be noted that

0268not all branching nodes in the tree need to store the package, and non-storing branching nodes

0269(e.g., nodes 20, 22) would just pass a NAck on up the tree until the distribution node 10 or a

0270storing node is reached which can deal with the NAck.

0271As mentioned above, a node should be capable of determining whether a packet that was

0272sent to it has been received. This can be accomplished in several ways. For example, a package

0273forming a "sent packets list" can be transmitted periodically by the parent node to its child

0274node(s) enclosing a list of the packets it has queued, identifying packets sent and/or packets that

0275will be sent. The child node can then ascertain whether any packets have been lost, by

0276comparing a list of packets which have been received with the packets identified in the "sent

0277packets list". The child node can then send NAcks for those packets not received. The "sent

0278packets list" may be sent by the parent node at substantially different times to the packets

0279referenced, so that it would be less likely that any congestion causing packets to be missed

0280would interfere with the transmission of the packets forming the "sent packets list".

0281Fig. 5 is a flow diagram illustrating a technique capable of being performed by storing

0282nodes in the system according to an embodiment. A packet is received from a parent node and

0283stored (step S10). In step SI 2, a determination is made whether the received packet forms part

0284of a "sent packets list" (Step S12). If the packet is not part of a "sent packets list" (No, Step

0285SI 2), a determination is made whether the packet is for this node (e.g., whether this node is a

0286target node for the packet). If the data packet is not for this node (No, Step S26), information

0287identifying the packet is added to this nodes own "sent packets list" (Step S28). The packet is

0288then queued to be sent to the node(s) lower in the free (Step S30). The packets in the queue will be sent to nodes below in due course using, for example, a "fair queuing" type algorithm. The

0289process then returns to Step S10. If the packet is for this node (Yes, Step S26) (e.g., this node is

0290a target node) the packet is processed by the node in a normal manner (Step S32). Infoπnation

0291identifying the packet is then added to a "received packets list" (Step S34). A determination is

0292then made whether the packet is also to be forwarded to nodes below. If the packet is not to be

0293forwarded to other nodes (No, Step S36), the process then returns to Step S10. If the packet is

0294to be forwarded to other nodes, (Yes, Step S36), information identifying the packet is added to

0295this node's "sent packets list" (Step S28). The packet is then queued (Step S30) and the process

0296returns to Step S10.

0297If the received packet is part of a "sent packets list" (Yes, Step S12), a determination is

0298made whether all packets for the "sent packets list" have been received (Step S14). If not all

0299packets for the "sent packets list" have been received (No, Step S14), the process returns to Step

0300S10 to wait for the next packet. If all packets for the "sent packets list" have been received from

0301the parent node (Yes, Step S14), a comparison is made between the received packets list created

0302in this node in Step S34 and the packets sent to this node as identified in the "sent packets list"

0303received from the node above (Step SI 6). If all packets sent to this node from the node above

0304have been received (Yes, Step SI 8), the process ends and the "received packet list" can be

0305purged if desired (Step S20). If all packets have not been received (No, Step SI 8), a negative

0306acknowledgment (NAck) is sent up the tree (Step S22) to indicate that one or more packets have

0307not been received. Information may be also sent along with the NAck identifying the packets

0308not received. This enables the parent node to then resend only those packets which were not

0309received at this node. Periodically, a package containing the "sent packets list" created at this node in step S28, indicating the packets sent from this node to any nodes below, will be sent,

0310typically in the form of a series of packets to the nodes below. The package is a list of packets

0311the parent has queued up to that point.

0312As shown in Fig. 6, when a storing node receives a negative acknowledgment (NAck)

0313from a node below (Step S50), the NAck is examined to determine which packets were not

0314received (Step S52) by examining information accompanying the NAck identifying the packets

0315not received. The packets that were not received can then be requeued and resent (Step S54).

0316Another method of determining whether all packets have been received at a child node is

0317to attach a reference to a previous queued packet, to each packet being queued, so that any break

0318in the chain of queued packets reaching the child node can easily be spotted.

0319Fig. 7 will now be used to describe the steps performed if the routing tree changes. If a

0320node becomes inoperative or another problem occurs which results in a new spanning tree

0321between the distribution node and the target nodes, each node with a changed routing table

0322could be provided with functionality to send a message to the distribution node, alerting it to the

0323change in spanning tree configuration. When such a message is received at the distribution node

0324(Step S60), the distribution node sends out another set of unicasts to the target nodes (Step S62)

0325as described above, whereby branclnng nodes involved in the multicast can be made aware of

0326their new child nodes. The multicast can then continue thereafter. The new multicast routing

0327could be weighted to take advantage of those nodes which have part of a package already stored,

0328wherever possible. For example, the system can be arranged so that as many portions of the

0329original tree as possible remain the same so that nodes which already have a part of the package

0330do not need to receive the entire package again. Another embodiment is described with reference to Figure 4, which shows a branch of a

0331spanning tree. According to this embodiment, each storing node (e.g., nodes 82, 84 and 85) is

0332able to delete its copy of the stored package (assuming it is not also a target node) as soon as it is

0333no longer required by any nodes below it in the tree, hi this embodiment, each storing node is

0334capable of determining when all the storing nodes and target nodes to which it is responsible for

0335sending packets have received those packets. The nodes to which a storing node is responsible

0336for sending packets may be referred to herein as dependent nodes. In the example shown in

0337Figure 4, the dependent nodes of storing node 80 are storing node 82, storing target node 84 and

0338target node 87 with nodes 81, 83 being intermediate relay nodes. Target nodes 88 and 89 are

0339dependent on storing target node 84. Storing target node 85 and target node 86 are dependent

0340on storing node 82. Target nodes 90 and 91 are dependent on storing target node 85. Nodes 81

0341and 83 do not take part in the node dependency as they simply relay the packets.

0342In this embodiment, when a package is being sent, knowledge of receipt of the complete

0343package by all target nodes and storing nodes in the tree is propagated recursively back up the

0344tree. That is, when target nodes have received the complete package they send positive

0345acknowledgments back up the tree. In addition, when a storing node receives positive

0346acknowledgments from the nodes to which it is responsible for sending the package, the storing

0347node sends a positive acknowledgment back up the tree. Once a storing node has received a

0348positive acknowledgment from all its dependent nodes, it knows it can erase its copy of the

0349package (assuming it is not a target node) and send a positive acknowledgment to this effect

0350back up the tree where it is received by the storing node above and prevented from going further

0351up the free. Likewise, once the storing node above has received a positive acknowledgment from all its dependent nodes, it can delete its copy of the package (also assuming it is not a

0352target node) and send a positive acknowledgment back up the tree, and so forth. Once the

0353distribution node has received acknowledgments from all its dependent nodes, the package has

0354been received by all the target nodes.

0355One method for accomplishing this task will now be described by reference to the flow

0356charts of Figs. 8 A, 8B. According to this embodiment, the distribution node performs a

0357provisional set of unicasts of an initialization message that are relayed to all target nodes. This

0358could be the same set of unicast initialization message packets used to set up the multicast

0359groups as discussed above. As shown in Fig. 8A, the initialization message is unicast by the

0360distribution node to all target nodes (Step S80). When this initialization message is received at a

0361storing node (Step S82), the storing node forwards the unicast initialization message on to the

0362target node(s) (Step S84). In addition, in response to receipt of the initialization message, each

0363storing node and target node sends an identification packet identifying itself, back up the tree

0364(Step S86) and the process ends. The first storing node that receives this identification message

0365being sent back up the tree adds the node identified therein to its list of dependent nodes. For

0366example, as shown in Fig. 8B, when the identification packet from a storing node below is

0367received (Step S88) a storing node will add the node identified in the identification packet to its

0368list of dependent nodes (Step S90) and the process ends. The identification packet is not passed

0369any further back up the tree. Of course, the node making a record of its dependent nodes will

0370itself have already sent a packet identifying itself to the node on which it is dependent and so on

0371and so on until each node is aware of its dependent nodes. Each storing node needs only send

0372such an identifying message once, no matter how many test messages pass through it. Now, when a storing node sends the packets of data forming an actual package down the

0373tree, the storing node can determine whether positive aclcnowledgments have been received

0374from each of its dependent nodes acknowledging receipt of the package. As shown in Fig. 9,

0375after a storing node receives a positive acknowledgment (Step S92) a determination is made

0376whether positive aclcnowledgments have been received from all dependent nodes (Step S94). If

0377not all positive aclcnowledgments have been received (No, Step S94), the process returns to Step

0378S92. If all dependent nodes responded with positive aclcnowledgments (Yes, Step S94), a

0379determination is made whether this node is a target node. If the node is a target node (Yes, Step

0380S96), the positive acknowledgment is sent up the tree (Step SI 00) without deleting the package.

0381If not a target node (No, Step S96), the package can be deleted from memory (Step S98) prior

0382to the positive acknowledgment being sent up the tree (Step SI 00).

0383An example of this process will now be described by reference to Fig. 4. This example

0384assumes that the test message has been successfully distributed and that each storing node is

0385aware of its dependent nodes. This example also assumes a package consisting of several

0386packets is being sent to target nodes 85, 86, 90 and 91. When the packets are received at storing

0387node 80, they are stored, queued and forwarded to storing node 82. Storing node 82 stores and

0388queues the packets, forwarding them to storing target node 85 and target node 86. Storing target

0389node 85 stores and queues the packets, forwarding them to target nodes 90, 91. Upon receipt of

0390the complete package, target nodes 90 and 91 each send positive aclcnowledgments to storing

0391target node 85. Storing target node 85, also being a target node, will not delete its copy of the

0392package upon receipt of the positive acknowledgments. Storing target node 85 will then send a

0393positive acknowledgment to storing node 82, indicating that its dependent nodes successfully received the sent packets. Upon receipt of the complete package, target node 86 will also send a

0394positive acknowledgment to storing node 82. Upon receipt of the positive acknowledgments

0395from its dependent nodes, storing node 82 can delete its copy of the package. Storing node 82

0396will then send a positive acknowledgment up the tree to storing node 80 indicating that its

0397dependent nodes successfully received the sent packets. This continues up the tree to the

0398distribution node. When the distribution node receives the last positive acknowledgment from

0399its dependent nodes, the distribution node determines that the package has been received at each

0400target node.

0401Nodes receiving positive aclcnowledgments, may also send acknowledgments of receipt

0402back down the tree to the dependent nodes in question, so that the dependent nodes are aware

0403the positive acknowledgments have been received. In this way, the dependent nodes do not

0404need to keep re-sending positive acknowledgments up the tree. It should be noted that this

0405technique can be used on the packet level, rather than the package level, or even a "sub-package

0406level" somewhere in between.

0407The present disclosure may be conveniently implemented using one or more

0408conventional general purpose digital computers and/or servers programmed according to the

0409teachings of the present specification. Appropriate software coding can readily be prepared

0410by skilled programmers based on the teachings of the present disclosure. The present

0411disclosure may also be implemented by the preparation of application specific integrated

0412circuits or by interconnecting an appropriate network of conventional components.

0413Numerous additional modifications and variations of the present disclosure are

0414possible in view of the above-teachings. It is therefore to be understood that within the scope of the appended claims, the present disclosure may be practiced other than as specifically

0415described herein.