Electrical computers and digital processing systems: multicomput – Computer-to-computer protocol implementing – Computer-to-computer data transfer regulating
Reexamination Certificate
2001-03-14
2004-10-19
Meky, Moustafa M. (Department: 2157)
Electrical computers and digital processing systems: multicomput
Computer-to-computer protocol implementing
Computer-to-computer data transfer regulating
C709S217000, C370S352000
Reexamination Certificate
active
06807578
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to multicast transmission of information across a data network. More particularly this invention relates to a technique for suppressing requests for retransmission of missing information by recipients at a downstream link of a mostly one-way data network.
2. Description of the Related Art
The push model for distributing data over the Internet and other client server networks has become more widespread in recent years. In modern versions of this model a server “multicasts” data to an interested subset of clients on the network, known as a “multicast group”. Whoever is interested becomes a listener by joining the group.
By their nature, push applications are closer to the broadcasting paradigm of radio and television than to the interactive paradigm of the World Wide Web. As such, broadband networks, such as cable TV or satellite, can be used as a very efficient medium for the transmission of “pushed data”. Unfortunately, currently these networks are one-way only. That is to say, data such as a television program is sent from a broadcasting facility (the head-end) to several receivers (end-users) without any feedback. As such, these networks are inappropriate for popular interactive push applications since the latter require a return channel. Although attempts to upgrade the current public network infrastructure are underway in several places around the world, it will take some years until reliable two-way broadband networks are commonplace and therefore, a mechanism for multicasting over one-way broadband networks is desirable.
In conventional unicast transmission, there are well known handshaking protocols that insure that blocks of data have been correctly received by the downstream recipient. The sender is easily able to determine whether a block of data requires retransmission, and can maintain awareness of the state of the recipient with little computational overhead. Without modifications, the unicasting techniques become unwieldy when applied to multicast transmission. Large numbers of recipients asynchronously requesting retransmissions are likely to produce congestion of the data network and degrade its performance. Furthermore, in the case of hierarchical multicasting arrangements, the algorithms based on estimating the paths to the recipient do not generalize well to tree structures, and the model of the communication as a conversation between sender and recipient does not stand up well.
Various techniques have been attempted to minimize requests for retransmission, such as the formation of token rings, and the use of a central controller. However these techniques have had limited success due to problems of scalability, and the need to secure group-wide agreement. The latter approach is difficult in the case of groups having transient membership.
In the document,
A Reliable Multicast Framework for Light
-
weight Sessions and Application Level Framing
, Sally Floyd et al., SIGCOMM '95, Cambridge Mass. (1 Sep. 1995), it is proposed to employ a model known as Application Level Framing. This is a decentralized approach, in which all traffic is multicast. Each session has a bandwidth limit, below which group members send multicast reports advising of their current state. Receivers learn of missing data either by examination of their received sequences, or by evaluation of a multicast report from another group member. Repair requests are multicast among the group. When a node is in receipt of a request or reply concerning a data element which it lacks, it suppresses its own request for repair. After receiving content from the server
10
, the receivers
12
,
14
,
16
may transmit acknowledgements or negative acknowledgements reflecting their current state. The reports are limited such that they do not exceed more than a predetermined percentage of the network's bandwidth, in order to prevent network congestion. Nevertheless, there is necessarily some degradation of network performance.
The document,
Reliable Multicast Transport Protocol
, Shioshita, Teruji et al., Draft Document for the 37
th
IETF, Feb. 7, 1997, proposes a transport control mechanism to enable reliable multicast data transfer to a large number of receivers on a TCP/IP network from a server in parallel. This protocol promotes short delivery time, as the data is transferred only once, and conserves bandwidth because only one copy of the data is sent to the server. It has the advantage of requiring only a single session regardless of the number of receivers. However, despite some optimizations, there remains a requirement for receiver confirmation by ACK/NAK responses and the retransmission of data to selected receivers based on the information associated with the NAK response are disadvantages, as large numbers of receivers issuing ACK/NAK responses can still cause network congestion.
Another known multicast transport protocol is proposed in
Starburst Multicast File Transfer Protocol
(
MFTP
)
Specification
. Miller, K. et al., Internet Draft, April 1998. This protocol operates in the Application Layer.
In copending U.S. application Ser. No. 09/138,994, filed Aug. 24, 1998, of common assignee herewith, and hereby incorporated by reference, a technique of IP multicasting over existing broadband networks without using a return link is disclosed. This technique allows the issues of multicast group membership and error detection and recovery to be handled locally within an end-user terminal, without need for returning data to a host. According to the technique a single data transmitter sends a group of data items to a subset of possible receivers over a one-way channel. Each data item is divided into blocks which are encapsulated to form datagrams, each including a block sequence number, a data item identifier, and a timestamp indicating the age of the data item. A group directory is regularly sent by the transmitter to each of the possible receivers. The group directory contains information for all groups of data items, enabling each receiver to select the group of data item it wishes to receive. Reliability is provided by periodic retransmission of missing data. Despite these advantages, significant problems remain.
SUMMARY OF THE INVENTION
It is a primary advantage of some aspects of the present invention that missing elements in a multicast transmission can be supplied while processing a minimum number of repair requests from clients.
It is another advantage of some aspects of the invention that network congestion is minimized during multicasting.
It is yet another advantage of some aspects of the invention that network traffic is optimized during multicast transmission.
These and other advantages of the present invention are attained by a multicasting system suitable for use in data network caches, software distribution arrangements, and content provider applications in general. Content is multicast from a sender to a plurality of receivers over a data network, such as the Internet. Each receiver independently determines whether it is missing elements or packets of the content. Receivers having missing content each initiate a random timer. The receiver having the shortest random interval unicasts a negative acknowledgement to the sender. The sender immediately multicasts the negative acknowledgement to the other receivers. All other receivers having the same missing packet thereupon suppress their own negative acknowledgements as to that packet. A repair transmission is then multicast by the sender to all receivers. In some embodiments, the repair transmission could be multicast by a receiver possessing the missing packet. The random intervals have upper and lower bounds according to the round trip transmission time and the size of the largest missing data element.
The invention provides a method of transmitting data over a communications network, which includes multicasting content in a first multicast over a data network from a sender to a multicast group. The group comprises a plurality of receivers. Concurrent
Gershinsky Gidon
Rochwerger Benny
Satran Julian
Darby & Darby
International Business Machines corporation
Meky Moustafa M.
LandOfFree
Nack suppression for multicast protocols in mostly one-way... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Nack suppression for multicast protocols in mostly one-way..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Nack suppression for multicast protocols in mostly one-way... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3280367