GB2385499A

GB2385499A - Network transport protocol

Info

Publication number: GB2385499A
Application number: GB0203786A
Authority: GB
Inventors: Adam Francis Brown
Original assignee: VENATION Ltd
Current assignee: VENATION Ltd
Priority date: 2002-02-18
Filing date: 2002-02-18
Publication date: 2003-08-20
Also published as: AU2003207327A1; WO2003069836A8; GB0203786D0; WO2003069836A1

Abstract

A method of operating a sender is described which provides reliable transmission of a plurality of data packets over a network to a plurality of receivers. One or more of the receivers defines a set of receivers. Each data packet is transmitted to a chosen set of receivers and acknowledgement messages are received from each of the receivers. Each acknowledgement message contains a record of the packets that have been validly received by the receiver sending that acknowledgement packet. A record is generated of the transmission of each packet to each receiver in a data structure which is indexed by packet identity and receive identity. The data structure is combined with each received acknowledgement message so that the data structure then includes a record of which receiver is yet to acknowledge receipt of which data packet. Each data packet is then retransmitted to the set of receivers which the data structure indicates have yet to acknowledge receipt of the data packet, unless all receivers have acknowledged receipt.

Description

NETWORK TRANSPORT PROTOCOL The present invention relates to methods of transmitting a plurality of data packets over a network from a sender to a plurality of receivers, and apparatus adapted to carry out such methods. In particular, but not exclusively, the invention relates to methods and apparatus for providing reliable and efficient multicast of data packets.

In network terminology, sending a data packet over a network to a single receiver is known as unicasting, whereas sending a data packet to all receivers is known as broadcasting and sending a data packet to a subset of all receivers is known as multicasting. These three basic addressing concepts may be implemented in different ways on different types of physical network. On an Ethernet network, each receiver listens for and accepts packets having a unicast address unique to that receiver. Each receiver may also listen for and accept packets having a multicast address for which other receivers are also listening. All receivers listen for and accept packets having a broadcast address.

The well known Internet Transport Control Protocol (TCP) (Internet Standard 0007) provides a reliable and network friendly arrangement for the transfer of data packets between two network nodes.

The underlying addressing arrangement and delivery mechanism is provided by the Internet Protocol (IP).

At the IP level a network attempts to deliver a data packet to the addressee but does not guarantee delivery and does not inform the sender of a failed delivery, although some feedback may be obtained through related protocols such as the Internet Connection Management Protocol (ICMP). TCP uses IP as a delivery mechanism, but adds a layer of

communication in which the receiver acknowledges receipt of data packets and the sender resends data packets which have not been acknowledged. The sender also monitors the quality of the network connection to the receiver and adapts the way in which packets are sent accordingly, thus optimizing the use of the network for itself and also for other network users.

TCP has been highly successful and is used by most of the well known Internet application protocols such as HTTP, FTP and SMTP. However, it is specific to connections between two network nodes. If packets are to be transmitted from a single sender to multiple receivers then separate TCP connections must be established between the sender and each receiver.

This is wasteful of the resources of the sender, and impractical for large numbers of receivers. Because the same data may pass along a single network segment multiple times on the way to some or all of the receivers it is also wasteful of network resources.

Adapting TCP to provide the same reliability and congestion and flow control for multicast transmission, to avoid these limitations, is not a trivial task. If the sender is made responsible for ensuring reliable delivery and effective flow and congestion control to all multicast receivers then little would be gained over the use of multiple conventional TCP connections.

Various attempts have been made to construct reliable and efficient multicast protocols, with various degrees of success. The"Reliable Multicast Transport Protocol" (RMTP) as described, for example by J. C. Lin and S. Paul in Proceedings of the IEEE INFOCOM, 1996, pages 1414-1424, March 1996, organises the participating network nodes into a control tree.

Each intermediate node in the tree is responsible for buffering data received from its parent node, processing acknowledgements from its children nodes

and retransmitting lost packets. A child node periodically sends an acknowledgement packet to its parent containing a record of the position of the lower end of its current receive window and a fixedlength bit vector of receive window size indicating which packets have been received and which have not.

In RMTP, if the number of children nodes requesting retransmission of a certain packet exceeds a certain threshold then the packet is retransmitted by the parent using the multicast address listened to by all of its children. Otherwise, the packet is unicast to each of the requesting children. The parent maintains a retransmission queue. Each member of the queue contains the sequence number of a packet to be retransmitted and the network addresses of the requesting children nodes.

RMTP and similar prior art reliable multicast protocols make use of conventional IP multicast addressing. Data packets are initially multicast to all receivers in a particular region of a network. If retransmission is required then packets are either multicast again to all receivers or unicast to individual receivers. International Patent Publication WOOO/18068 discloses an alternative addressing arrangement in which a number of receivers are logically arranged into sets, each set representing one of the possible combinations of the receivers. Each set is assigned a separate multicast address, or unicast address for sets of one receiver, so that data can be multicast to any combination of the receivers using the multicast address for the appropriate set. Where it is desired to divide multicast data into a large number of different streams, for example to enable receivers to select more precisely what data they receive, the number of multicast addresses needed by a sender can be reduced by using this addressing arrangement. It would be

desirable to take advantage of a multicast addressing arrangement such as that set out in WOOO/18068 to provide an efficient and reliable method of multicasting data packets. However, known reliable multicast protocols would not be easy to adapt in this way. Such adaption would result in inefficient use of network and network node resources, as well as deriving sub-optimal benefit from this multicasting addressing arrangement. The invention seeks to address these and other problems associated with the related prior art.

Accordingly, the invention provides a method of operating a sender to provide reliable transmission of a plurality of data packets over a network to a plurality of receivers, each combination of one or more of the receivers defining a set of receivers, the method comprising the steps of: transmitting each packet to a chosen set of the receivers; and receiving acknowledgement messages from each of the receivers, each acknowledgement message containing a record of the packets validly received by the receiver sending the acknowledgement packet, characterised in that the method further comprises the steps of: making a record of the transmission of each packet to each receiver in a data structure indexed by packet identity and receiver identity; combining each received acknowledgement message with the data structure so that the data structure thereafter contains a record of which receiver has yet to acknowledge the receipt of which data packet; and retransmitting each data packet to the set of receivers which the data structure indicates have yet to acknowledge receipt of the data packet, unless all receivers have acknowledged receipt. Retransmission may occur, for example, if one or more receivers have yet to acknowledge receipt after a given time interval.

Since a data packet may be transmitted to just

one, more than one or all receivers, the recordal of transmission of a packet to particular receivers can be recorded very efficiently in a data structure indexed by receiver. However, since any one receiver issues acknowledgement messages relating to a plurality of packets received or not received by that receiver, it is also advantageous to maintain the transmission record in a data structure indexed by packet identity. Then, acknowledgement messages can be efficiently combined with the data structure so that it thereafter contains a record of which receiver has yet to acknowledge receipt of which data packet.

A transmission/acknowledgement record data structure of the claimed type also allows the selection of receivers for retransmission of a packet to be efficiently carried out.

A transmission/acknowledgement data structure of the claimed type can advantageously be accommodated in a two dimensional array, for example a two dimensional array in which an element indexed by packet identity and receiver identity is changed from a first to a second state when the packet is first sent to the receiver, and from the second state back to the first, or alternatively to a third state when acknowledgement of the packet is received by the sender from the receiver. The acknowledgement messages issued by receivers may conveniently comprise a one dimensional array indexed by packet identity, each element of the array being either in a first state, or in a second state acknowledging receipt of the indexed packet.

Conveniently, the transmission/acknowledgement data structure may be provided by a two dimensional bit map. Then, if acknowledgement messages each comprise a one dimensional bit map indicating package acknowledgement then a single and efficient XOR operation of the acknowledgement bit map with the corresponding part of the transmission/acknowledgement

data structure may be used to update the transmission/acknowledgement data structure. Of course, other operations could be used which compare a bit in the packet acknowledgement with a bit in the corresponding part of the transmission/acknowledgement data structure, and change the state of the data structure bit if the compared bits are different.

The method may be applied with particular advantage in an environment in which a different network address is allocated for packet transmission to each set of receivers. This is because the set of receivers to which retransmissions should be sent is then easily established by referring to the part of the transmission/acknowledgement data structure indexed by the appropriate packet identity. This part of the data structure can be used as an index or reference to establish the appropriate channel, or multicast address for the set, or unicast address if the set consists of only one receiver. Of course, unicast addressing can be used where desired, in place of multicasting, especially in a network region which is not multicast enabled.

Advantageously, the sender may maintain a timer based on the transmission time of a data packet, and carry out the step of retransmission on expiry of the timer. The duration of the timer may be set to try to optimise the overall data transfer rate and use of network resources. Other methods of determining when to retransmit a packet, for example following receipt of an acknowledgement packet indicating receipt of subsequent packets, may be used.

Preferably, the ! sender periodically transmits a heart beat message to all of the receivers, and each receiver transmits an acknowledgement message back to the sender following receipt of the heart beat message.

The invention also provides a sender computer

system adapted to provide reliable transmission of a plurality of data packets over a network to a plurality of receiver computer systems, each combination of one or more of the receivers defining a set of receivers, comprising: a send process adapted to transmit each packet to a chosen set of the receivers; a receive process adapted to receive from the receivers acknowledgement messages which each contain a record of the identity of packets validly received by the receiver sending the acknowledgement packet; and a cache adapted to make a record of the transmission of each packet to each receiver in a data structure indexed by packet identity and receiver identity, the cache being further adapted to combine each valid received acknowledgement message with the data structure so that the data structure thereafter contains a record of which receiver has yet to acknowledge the receipt of which data packet.

Preferably, the sender computer system is adapted to retransmit each data packet to the set of receivers, if any, which the data structure indicates have yet to acknowledge receipt of the data packet, for example on expiry of a retransmission timer for that packet.

The invention also provides a method of operating a sender computer to provide transmission of a plurality of data packets to a plurality of receivers over a network, in which each set of receivers defined by a combination of one or more of the receivers is allocated a network address for transmitting packets to the members of that set, the method comprising the steps of: monitoring messages received from the receivers; using the received messages to construct and maintain current connection records relating to the state or quality of the network connection between

the server and each receiver; and managing the transmission of data packets to each set of receivers using the connection records relating to the receivers in the set.

The method provides the advantage that transmission to a particular set can be controlled on the basis of the quality of the connection between the sender and only members of that set, avoiding transmission constraints being imposed by the quality of connections not relevant to that set. Furthermore, the connection information obtained during communication with members of a first set can also be used when communicating with members of a second set if the first and second sets have common members.

Preferably, the network address allocated to a set of two or more receivers is a multicast address at least locally unique to those receivers. A unique unicast address may be used for communication with each set which contains just one receiver.

Preferably, the method comprises the step of transmitting one or more data packets to a set of two or more of the receivers using the connection records of only one of the receivers of the set. For example, if the connection records comprise the round trip time between the sender and each of two or more receivers in a set, the transmission of data packets to that set can be controlled on the basis of the longest round trip time to and from any of the receivers in that set. Such control may make use of the round trip time in determining the duration of a packet timer the expiry of which triggers retransmission of the packet.

Advantageously, 'the connection records may comprise transmission window sizes, receiver window sizes, smoothed round trip times, round trip time variations, congestion window sizes and other parameters familiar to the skilled person in the context of known transport protocols such as TCP. The

connection records relating to the receivers in a set may be combined in a variety of ways to determine controlling parameters for transmission only to the members of that set using the multicast or unicast address allocated for that set. Typically, the connection records of the least favourable connection will be used, such as the smallest transmission or congestion window, but other schemes could be used such as the average of a set of parameters for different receivers.

The invention also provides a sender computer system adapted to send a plurality of data packets to a plurality of receiver computers over a network, in which each set of receivers defined by a combination of one or more of the receivers is allocated a different address for transmitting packets only to members of that set, the system comprising: a receive process adapted to receive messages from the receivers; a plurality of connection records relating to the status or quality of the connection between the sender computer system and each receiver; and a send process adapted to send data packets to each set of receivers with reference to the connection records relating to only the receivers in the set.

The invention also provides a method of configuring a network to provide transmission of a plurality of data packets from a sender to a plurality of receivers, comprising the steps of: defining a plurality of receiver groups, and allocating each receiver to one of the groups; defining a plurality of receiver sets, each set containing a different combination of receivers, each set containing receivers from only one receiver group; allocating a different network address to each receiver set; configuring the sender to use the network address allocated to a set when sending data packets to that

set; and configuring each receiver to accept data packets addressed to those sets of which the receiver is a member.

The invention also provides a network sender adapted to provide transmission of a plurality of data packets over a network to a plurality of receivers, each receiver being allocated to one of a plurality of receiver groups, each receiver of each group being a member of a plurality of receiver sets, each set containing a different combination of the receivers belonging to that group, for each set the sender being adapted to send data packets to the members of that set using a single network address different to the network address used to send data packets to any of the other sets.

Embodiments of the invention will now be described, by way of example only, and with reference to the drawings of which: figure 1 illustrates a network tree structure within the context of which the described embodiments may be put into effect; figure 2 shows a"host mask"data structure used to reference sets of the receivers associated with a particular sender ; figure 3 shows elements of a network node of the preferred embodiment; figure 4 illustrates a data packet sent or received by the network node of figure 3 ; figure 5 illustrates a heart beat message sent or received by the network node of figure 3 ; figure 6 illustrates an acknowledgement message sent or received by the network mode of figure 3; figure 7 shows the queue structure used by the send process of figure 3 to prioritise data packet transmission; and figure 8 illustrates a data structure maintained

by the cache of figure 3.

Figure 1 illustrates a network tree for distribution of data from a root node 10 to a plurality of leaf nodes 14, via one or more layers of intermediate nodes 12. At each level of the tree the same transport scheme is used to propagate data packets down the tree. A parent node acts as a sender to transmit a plurality of data packets to selected ones of its child nodes, which thereby act as receivers. Thus, in the context of the illustrated tree, the root node 10 acts only as a sender, the leaf nodes 14 act only as receivers, and the intermediate nodes 12 act both as receivers and senders to forward received data further down the tree.

In the preferred embodiment of the invention, which is suitable for, but not limited to use in a network tree arrangement such as that of figure 1, a sender stores in a cache a copy of any data it transmits, and periodically transmits a heart beat message to each of its receivers. Each receiver responds to a heart beat message by transmitting an acknowledgement message back to the sender. An acknowledgement message specifies data packets which the receiver has validly received. If a receiver has not acknowledged receipt of a data packet before a timer for that packet expires then the sender retransmits the data packet to that receiver.

The network tree of figure 1 is implemented using a conventional network of IP routers to connect the senders and receivers. Preferably, the routers are all IP multicast enabled. However, if one or more links is not IP multicast enabled then it is straightforward to adapt the addressing scheme used to make use of IP unicast addressing where necessary.

The data packets and messages are embedded within UDP (User Datagram Protocol-Internet Standard 0006) packets for transmission over the network. It is not

necessary to use a more sophisticated underlying protocol since reliability and flow and congestion control are implemented explicitly by the transport protocol of the preferred embodiment, although a wide variety of network protocols familiar to the skilled person other than UDP could, of course, be used. The use of UDP over IP to provide the underlying packet transport layer enables the preferred embodiment to operate over the publically accessible Internet, either in part or in whole.

Those receivers which are child nodes to a particular sender are logically grouped into sets.

Each set is defined by a combination of one or more of the receivers, and together the sets define all possible combinations of receivers for that sender.

Each set is then used to define a data channel. Each data channel directed to a single receiver is assigned an IP unicast address and each data channel directed to two or more receivers is preferably assigned an IP multicast address. A data packet or message can then be sent from a sender to any combination of its receivers by directing it to the appropriate data channel.

To avoid having to use too many IP multicast addresses between a sender and its receivers, the receivers to a particular sender are associated into a number of virtual groups, each virtual group containing up to eight receivers. A more practical number of receivers to include in each virtual group is six, for which fifty seven multicast and six unicast addresses are required using the scheme described above. Typical network routers can hold state for a few hundred multicast addresses, so that eight virtual groups of up to six receivers each is reasonably practical to implement over existing IP networks.

Figure 2 shows a"host mask"data structure used

to reference the receivers associated with a particular sender. The host mask is implemented as a 64 bit bit-map, treated as eight groups of eight bits.

Each group represents the receivers within one virtual group. As an example, to reference receivers 0,1, 5 and 7 in virtual group 1 the following host mask would be used: 00000000 11000101 00000000 00000000...

Referring now to figure 3, each network node 12 that acts both as a sender and a receiver is implemented using a server process 20, a security manager 22, a send process 24, a receive process 26, a cache 28, and an acknowledgement database 30. From the viewpoint of the send and receive processes the network 32 is seen as a UDP process appropriately configured to transmit UDP packets to and receive UDP packets from a number of other UDP processes associated with other server processes acting at other network nodes. The root node 10 and leaf nodes 14 of figure 1 may be implemented using the same or a similar arrangement to that illustrated in figure 3.

If required, the root node may be provided with an acknowledgement database 30, and the leaf nodes with caches 28, so that data communication can take place either up or down the tree.

The server process 20 provides appropriately sized data blocks for sending on particular data channels over the network 32 and specifies the class of service, or priority, to be used for each data block. As discussed'above, a different multicast or unicast address is associated with each channel, and a channel exists for all possible combinations of receivers in each virtual group. The network node 12 also receives data blocks on all relevant channels from its parent node. The remaining elements of

figure 3 provide the server process 20 with the means to send and receive data blocks reliably over the network 32 using the data channels.

For the network node 12 to send data the following steps occur: 1. the server process 20 passes a data block for a particular data channel and a particular class of service to the send process 24; 2. the send process 24 queues the data block in accordance with the specified class of service.

3. when the send process 24 is ready to send the data block it requests a security number from the security manager 22 and builds a data packet containing the data block, the security number, a packet identification number (packet ID) and other relevant information.

4. the data block, packet ID, data channel and class of service information are placed in the cache 28; 5. the send process 24 sends the data packet to the IP address specified for the data channel; and 6. the send process starts a retransmission timer for the packet.

For the network node 12 to receive data the following steps occur: 1. the receiver process 26 receives a data packet from the network 32 ; 2. the security number contained in the data packet is passed to the security manager 22 for checking; and 3. if the security number is invalid the packet is dropped. Otherwise, the packet ID is passed to the acknowledgement database 30

and the data is passed to the server process 20.

The send process 24 also periodically sends heart beat messages to all receivers. The frequency with which heart beat messages are sent may be varied to suit the speed and nature of the underlying network, but is preferably equal to several times the typical round trip time between a sender and a receiver. When a heart beat message is received by the receive process 26, the acknowledgement database 30 is used to construct an acknowledgement message specifying which packets within a current receive window have been received. This acknowledgement message is passed to the send process 24 for sending to the parent node which originated the heart beat message.

When an acknowledgement message is received by the receive process 26, the cache is modified to reflect which receivers have now acknowledged receipt of which data packet. When the timer for a particular data packet expires the packet is reconstructed from the information in the cache, retransmitted on the data channel corresponding to only those receivers which have not yet acknowledged receipt, and a new retransmission timer is started.

The security manager 22 operates using the authentication method described in W001/20872 A2, in which a sender process first securely transmits a list of security numbers to a receiver. A security number from the list is added to each data packet sent from the sender to the receiver. Each security number is used only once. Any data packet arriving with an unlisted or repeated'security number is rejected by the receiver. To prevent illicit introduction of packets into the data stream, the security numbers in each list are all independent such that knowledge of security numbers contained in previous packets provides no information on likely security numbers in

subsequent packets. Of course, various other types of security arrangements could be used, such as full data encryption and authentication schemes known in the art.

The receive process 26 receives data packets and messages addressed both to its own unicast address and to all the multicast addresses of data channels to which the receiver belongs. To ensure rapid processing of data received by UDP ports, the receive process 26 takes all data packets as soon as they arrive at an appropriate UDP port and places them in a single receive queue. Thus, incoming data is serialised and buffered for subsequent processing by the receive process 26.

To ensure swift processing, acknowledgement messages arriving at the receive process 26 are immediately authenticated by the security manager 22 and are then processed by the cache 28. Heart beats are also immediately authenticated by the security manager 22 and then passed to the acknowledgement database so that an acknowledgement message can be sent to the requesting host without delay. Data packets or messages failing authentication by the security manager are dropped.

Data packets placed in the receive queue are authenticated by the security manager 22. Each validly received data packet is recorded in the acknowledgement database and the data from the packet is then passed to the server process 20 for further processing.

The detailed structure of the data packets, heart beat messages and acknowledgement messages will now be described with reference to figures 4,5 and 6.

The data packet 40 illustrated in figure 4 comprises a 24 bit security number 42, a 2-bit version number 44 relating to the version of the described protocol, a 16-bit packet identification number

(packet ID) 46, a 1-bit acknowledgement flag 48, a 2bit priority code 50 and data block 54. The security number and the packet ID have already been discussed.

The acknowledgement flag is used to request immediate acknowledgement of the packet and all other packets received so far in a current receiver window, rather than waiting for the next heart beat message to arrive. The priority code represents fair, high, medium or low priority, as discussed below. The data packet 40 is embedded in a UDP packet sent across the network 32 using the multicast or unicast address associated with the data channel to which the packet belongs.

The heart beat message 60 illustrated in figure 5 comprises a 24-bit security number 62, an identification number 64 for the heart beat, a 2-bit version number 66 and a 6-bit host identification number 68. The host identification number encodes the identification of the receiver, from the perspective of the parent. As well as triggering acknowledgement messages from all the receivers to which the message is sent, embedded in unicast UDP packets, the periodic transmission of heart beat messages is used to verify that receivers are still responsive, even if no data is being sent.

The acknowledgement message 70 illustrated in figure 6 comprises a 24-bit security number 72, a 2bit version number 74, a 6-bit host identification number 76 encoding the identification of the acknowledging host, a 16-bit packet identification number 78, a 16-bit receiver window size 80, and an 8bit heart beat identification number 82. The receiver window size represents the amount of data, in kilobytes, which the receiver is currently willing to accept. The heart beat identification number 82 identifies which heart beat the acknowledgement packet 70 is in response to, thus enabling the sender of the

heart beat packet to calculate the current round trip time between itself and each receiver. A unique heart beat identification number is required because it is possible to have more than one heart beat packet present in the network between a sender and a receiver at any one time. IP networks for example, do not guarantee the ordering or timing of IP packet delivery.

The packet mask 84 is a bit mask in which a set bit represents acknowledgement of a particular data packet. The first set acknowledgement bit of the packet mask relates to the data packet specified by the packet identification number field 78, and subsequent bits correspond to subsequent packet identification numbers. The first set acknowledgement bit may be preceded by one or more unset bits, or zeros, in order to byte-align the bit mask.

Four classes of service are provided in the preferred embodiment. These are fair delivery, high priority, medium priority and low priority. As illustrated in figure 7, these classes of service are implemented by means of a priority queue complex 80 for each data channel. The priority queue complex 80 forms a part of the send process 24 illustrated in figure 3 and routes data blocks received from the

server 20 into one of the four sub queues 82,"FAIR", "HIGH","MEDIUM"and"LOW"in accordance with the class of service for each data block. Data blocks are taken from the subqueues and placed in the combined queue 84 in accordance with a traffic dominance table which defines the proportion of blocks to be taken from each subqueue in circumstances of any combination of the four queues containing at least one data block.

For example, if all four subqueues contain data blocks the proportions could be 53% fair, 27% high, 13% medium and 7% low, while if only the medium and low subqueues contained data blocks the proportions could

be 66% medium and 34% low, giving each priority level about twice the data rate of the next priority level down.

One or more data blocks are taken from each priority queue complex 80 in turn, for the construction of suitable data packets and transmission of these data packets over the network 32. The way in which transmission and retransmission of data packets over the network is controlled to make the most effective use of network resources will now be described.

Whenever a heart beat message 60 is sent out, the send process 24 records the time taken for an acknowledgement message 70 to return from each receiver. This time period is the round trip time Ri, for measurement j relating to receiver i. A smoothed round trip R,, and a round trip time variation AR,,, j are calculated using an algorithm very similar to that used in TCP (Internet Standard 007).

When a first measurement of raj is made, the following are set:

When subsequent measurements of R1. are made the following are set:

where-= 1/8 and p = 1/4.

As discussed above, when the send process 24 transmits a data packet on a data channel a

retransmission timer is started for that packet. The packet is retransmitted to any receivers which have not acknowledged receipt of the packet by the time the retransmission timer expires. The period of this retransmission timer is the"retransmission time out", which is based on a value AT, maintained for each receiver i. In the preferred embodiment the longest value of ATi for any of the receivers belonging to the appropriate data channel is used to set the retransmission timer for a packet sent to that channel, although other algorithms, for example taking account of more than one of the relevant ATi could be used.

ATi is updated following update of Ri. n and AR,,, using the following expression:

If AT1 is less than one second it is rounded up to one second, and it is not allowed to exceed a maximum value which is set to be at least 60 seconds. k is a constant set to 4.

When a retransmission timer expires before acknowledgements have been received from all relevant receivers the packet is retransmitted to all the receivers which have not yet acknowledged receipt, using double the timer length used for the previous transmission, subject to the maximum T1 discussed above. The send process keeps a record of the number of times a packet is retransmitted, recording this in the cache 28.

The acknowledgement message 70 illustrated in figure 6 contains a receiver window size field 80.

The value placed by a receiver in this field is equivalent to the amount of space remaining in the receiver's input buffer. The receiver window size for

each receiver is used by the send process 24 to limit the amount of data sent to prevent loss of data packets due to receiver buffer overflow.

The preferred embodiment implements a slow start algorithm which is very similar to that used by TCP.

The send process 24 maintains a congestion window size for each receiver which specifies the amount of data, in bytes, which can be sent to each receiver in a given time period. Ideally, the congestion window represents how much data can be put onto the network in half of one round trip time, which can be equated to the bandwidth multiplied by the delay of the appropriate network link at steady state, i. e. the maximum amount of data the network link itself can hold.

The congestion window size for each receiver is initially set to an estimate of the maximum segment size (MSS) for the connections between the sender and the receivers, although the actual MSS determined, for example, by a Path MTU Discovery process on a per receiver basis could be used.

The amount of data to be sent on a particular data channel in a given time period is determined by the lesser of the smallest congestion window of all the receivers on that channel and the smallest of the receiver window sizes 80 advertised by the receivers on the channel. For every data packet sent to a particular receiver which is acknowledged before the associated packet timer expires, the congestion window size for that receiver is doubled, until a congestion window size threshold for that receiver is reached, after which the congestion window size is increased by one MSS each time a packet is acknowledged. The congestion window size is not allowed to exceed the receive window size discussed above, and the congestion window size threshold is initially set to 64 Kbytes.

When a retransmission timer expires, because a packet was not acknowledged in time by one or more of the receivers to which it was sent, the congestion window size thresholds for the receivers failing to acknowledge the packet are set to half the current congestion window sizes for those receivers, but at least twice the MSS, and the congestion window sizes for those receivers are then set to the MSS. The send process 24 also adjusts flow control by measuring the maximum recent data rate of each data channel. The maximum data rate over a predetermined time period which is expected to include at least several slow start phases is used to set queue sizes and an estimated amount of data to send on each channel over a given send time period. The send time period is subdivided into ticks with a portion of the data to be sent over each channel being transmitted during each tick.

The cache 28 illustrated in figure 8 is used to record details of all packets which have been sent, but for which acknowledgements have not yet been received from all intended receivers. Details of packets are stored in the cache indexed by packet ID 90. Also stored in the cache area, in respect of each packet, are a host mask 92, the data payload 94 of each packet, retransmission state indicators 96 and a class of service indicator 98.

The number of times a packet has been retransmitted, to any data channel within each virtual group, is recorded in the retransmission state indicator 96 for each virtual group. The class of service indicator 98'records the class of service (discussed above) used for transmission and to be used for retransmission of each data packet.

The host mask 92 is of the same structure as the data structure shown in figure 2, being comprised of eight groups of eight bits each, each group

corresponding to one virtual group of receivers (VGO,..., VG7) and each bit corresponding to one receiver in the relevant virtual group. When a packet is first transmitted to one or more data channels in one or more virtual groups the bits for the receivers in those data channels are set to one.

The form of the acknowledgement messages 70 has already been discussed and illustrated in figure 6.

When an acknowledgement message 70 is received by the receive process 26 the packet mask 84 of the acknowledgement message and the corresponding part of the host mask column 92 of the cache for the receiver which sent the acknowledgement message are combined using an XOR operation. Thus packets sent to but not previously acknowledged by a receiver, and acknowledged in a packet mask 84 received from the same receiver have the corresponding bit in the cache set to zero. Packets sent to but not previously acknowledged by a receiver, and not acknowledged in a packet mask 84 received from the same receiver have the corresponding bit in the cache remaining as one.

If a particular packet is never sent to a particular receiver then the corresponding bit in the cache is always zero.

The cache host mask records 92 for each packet 90 in the cache provide a convenient way of maintaining a record of which receivers have yet to acknowledge which packets. When an acknowledgement timer expires the current cache host mask for the packet defines to which receivers the packet must be retransmitted, and the host mask can conveniently be used as input to software procedures for retransmitting the packet.

Claims

CLAIMS 1. A method of operating a sender to provide reliable transmission of a plurality of data packets over a network to a plurality of receivers, each combination of one or more of the receivers defining a set of receivers, the method comprising the steps of: transmitting each packet to a chosen set of the receivers; and receiving acknowledgement messages from each of the receivers, each acknowledgement message containing a record of packets validly received by the receiver sending the acknowledgement packet, characterised in that the method further comprises the steps of: making a record of the transmission of each packet to each receiver in a data structure indexed by packet identity and receiver identity; combining each valid received acknowledgement message with the data structure so that the data structure thereafter contains a record of which receiver has yet to acknowledge the receipt of which data packet; and retransmitting each data packet to the set of receivers which the data structure indicates have yet to acknowledge receipt of the data packet.
2. The method of claim 1 wherein the data structure comprises a two dimensional array indexed by packet identity and receiver identity, each element of the two dimensional array being in either a first state indicating that a packet has not been transmitted to a receiver, or has been transmitted and acknowledged, or in a second state indicating that a packet has been transmitted to a receiver but has not yet been acknowledged by that receiver.

<Desc/Clms Page number 25>
3. The method of claim 2 wherein each acknowledgement message comprises a one dimensional array indexed by packet identity, each element of the one dimensional array being in either a first state not acknowledging the receipt of a packet, or in a second state acknowledging receipt of a packet.
4. The method of claim 3 wherein the step of combining each received acknowledgement message with the data structure comprises a step of carrying out an XOR operation of the acknowledgement message array with the corresponding part of the data structure array.
5. The method of any preceding claim wherein a different network address is allocated for packet transmission to each set of receivers.
6. The method of any preceding claim wherein the network address for transmitting packets to a set comprising two or more receivers is a multicast address.
7. The method of any preceding claim wherein the network address for transmitting packets to a set comprising only one receiver is a unicast address.
8. The method of any preceding claim wherein the sender maintains a timer referenced to the time of transmission of a data packet, and the step of retransmission is carried out on expiry of the timer for that data packet :
9. The method of any preceding claim wherein the sender periodically transmits a heartbeat message to all of the receivers and each receiver transmits an acknowledgement message to the sender following

<Desc/Clms Page number 26>

receipt of the heartbeat message.
10. A method of operating a sender to provide transmission of a plurality of data packets to a plurality of receivers over a network, in which each set of receivers, defined by a combination of one or more of the receivers, is allocated a network address for transmiting packets to the members of that set, the method comprising the steps of: monitoring messages received from the receivers ; using the received messages to construct and maintain current connection records relating to the network connection between the sender and each receiver; and managing the transmission of data packets to each set of receivers with reference to the connection records relating to the receivers in the set, whereby current connection records are shared between transmissions to different sets having receivers in common.
11. The method of claim 10 further comprising the step of managing the transmission of one or more data packets to a set of two or more of the receivers using the connection record or records of only one of the receivers of the set.
12. The method of claim 10 or 11 wherein the connection records comprise records relating to network round trip time between the sender and each receiver.

f
13. The method of any of claims 10 to 12 further comprising the step of triggering the retransmission of a packet previously transmitted to a set of receivers by means of the expiry of a timer for that packet, the duration of the timer being calculated

<Desc/Clms Page number 27>

using the longest round trip time between the sender and any of the receivers in the set.
14. The method of claim 13 wherein the retransmission of a packet is addressed to the set of receivers to which the packet was previously transmitted and from which an acknowledgement of the packet was not received before the timer for that packet triggered.
15. The method of any of claims 10 to 14 wherein the connection quality records comprise records of a transmission window size in respect of each receiver for the transmission of packets from the sender to each receiver.
16. The method of claim 15 wherein the transmission window size for the transmission of a plurality of packets to a particular set of receivers is calculated using the smallest transmission window size for any of the receivers in that set.
17. A method of configuring a network to provide transmission of a plurality of data packets from a sender to a plurality of receivers, comprising the steps of: defining a plurality of receiver groups, and allocating each receiver to one of the groups; defining a plurality of receiver sets, each set containing a different combination of receivers, each set containing receivers from only one receiver group; allocating a different network address to each receiver set configuring the sender to use the network address allocated to a set when sending data packets to that set; and configuring each receiver to accept data packets addressed to those sets of which the receiver is a

<Desc/Clms Page number 28>

member.
18. The method of claim 17 wherein the receiver sets containing receivers from any one particular group together define all combinations of those receivers.
19. The method of claim 17 or 18 wherein a multicast address is allocated to each set of receivers containing more than one receiver and a unicast address is allocated to each set of receivers containing only one receiver.
20. A computer program product comprising computer program elements adapted to carry out the method steps of any of claims 1 to 19.
21. A computer readable medium comprising computer program elements adapted to carry out the method steps of any of claims 1 to 19 when executed on a suitable computer system.
22. Apparatus adapted to carry out the method steps of any of claims 1 to 19.
23. A network sender adapted to provide reliable transmission of a plurality of data packets over a network to a plurality of receivers, each combination of one or more of the receivers defining a set of receivers, comprising: a send process adapted to transmit each packet to a selected set of the receivers; a receive process adapted to receive from the receivers acknowledgement messages each containing a record of the identity of packets validly received by the receiver sending the acknowledgement packet; and a cache adapted to record the transmission of each packet to each receiver in a data structure

<Desc/Clms Page number 29>

indexed by packet identity and receiver identity, the cache being further adapted to combine each validly received acknowledgement packet with the data structure so that the data structure thereafter contains a record of which receiver has yet to acknowledge receipt of which data packet.
24. The sender of claim 23 adapted to retransmit a data packet to those receivers which the data structure indicates have yet to acknowledge receipt of the data packet previously transmitted to those receivers.
25. A network sender adapted to send a plurality of data packets to a plurality of receivers over a network, in which each set of receivers defined by a combination of one or more of the receivers is allocated a network address for the transmission of data packets to only members of that set, the system comprising : a receive process adapted to receive messages from the receivers; a plurality of connection records relating to the status of the network connection between the sender and each receiver; and a send process adapted to send data packets to each set of receivers with reference to the connection records relating to the receivers in the set.
26. A network sender adapted to provide transmission of a plurality of data packets over a network to a plurality of receivers, each receiver being allocated to one of a plurality of receiver groups, each receiver of each group being a member of a plurality of receiver sets, each set containing a different combination of the receivers belonging to that group, for each set the sender being adapted to send data

<Desc/Clms Page number 30>

packets to the members of that set using a single network address different to the network address used to send data packets to any of the other sets.
27. A network comprising the network sender of claim 26 and further comprising said plurality of receivers, each receiver being adapted to receive those of said data packets which are addressed to any set of which the receiver is a member.
28. A method of operating a sender substantially as herein described with reference to the accompanying drawings.
29. A method of configuring a network substantially as herein described with reference to the accompanying drawings.
30. A network sender substantially as herein described with reference to the accompanying drawings.