Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
1999-12-27
2003-06-17
Baker, Stephen M. (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
Reexamination Certificate
active
06581175
ABSTRACT:
FIELD OF THE INVENTION
The invention generally relates to computer networks and, more particularly, the invention relates to an apparatus and method of requesting retransmission of a message across a network.
BACKGROUND OF THE INVENTION
Various data transport protocols specify that upon receipt of a given message across a network, a receiving network device (“receiver”) may transmit a positive acknowledgment message to a sending network device (“sender”) to acknowledge that the given message was successfully received. In addition, upon detecting that a given message was not successfully received, such protocols often also specify that the receiver is to transmit a negative acknowledgment message to the sender to acknowledge that the given message was not successfully received. Upon receipt of a negative acknowledgment message, the sender may take some action, such as re-transmitting the given message to the receiver. Use of such protocols improves the reliability of data transmissions across a network, such as the Internet.
One such protocol that utilizes positive and negative acknowledgment messages is known as the Pragmatic General Multicast protocol (“PGM”), which is utilized to specify data transport for multicast transmissions. As known in the art, multicasting is a well-known method of transmitting messages to selected groups of users across a network. In accord with the PGM specification, a single PGM multicast message typically comprises a plurality of message segments that each are identified by a sequence number. For example, a given message from a sender to a receiver may include message segments ranging from sequence number one to sequence number twelve.
PGM utilizes two types of negative acknowledgment messages (“NAKS”), namely single NAKS and range NAKS. A single NAK identifies a single message segment (of a specific message) that was not received by the receiver, while a range NAK identifies a range of message segments (of a specific message) that were not received by the receiver. For example, a single NAK for the above exemplary message may indicate that message segment number five was not received. As another example, an exemplary range NAK for such exemplary message may indicate that message segments five through nine were not received by the receiver.
A network element between the sender and the receiver typically stores received NAKS in memory. Accordingly, newly received NAKS are compared against NAKS in memory to check for overlapping ranges. For example, a newly received range NAK for message segments four and five may be checked against the above noted range NAK (i.e., the range NAK for message segments five through nine). In a similar manner, when a confirmation message from a sender is received by the network element (i.e., confirming that a NAK was received by the sender), the network element also must check against the NAKS in memory for overlapping ranges. Furthermore, upon receipt of a message segment from a sender, the network element again must check the memory to determine which NAKS request retransmission of the received message segment. Moreover, the network element also maintains a listing of each receiver and their associated NAKS.
This process of repeatedly comparing and determining which sender requested which message segments places a large computational burden on the network element. In addition, NAKS having overlapping message segment ranges for the same receiver commonly are transmitted, thus unnecessarily adding data traffic to the network.
SUMMARY OF THE INVENTION
In accordance with one aspect of the invention, an apparatus and method of requesting retransmission of at least a portion of a message (having a plurality of message segments) from a sender utilizes message units in a memory device for storing data relating to retransmit messages. In particular, each message unit in the memory has data for one message segment. To that end, a given retransmit message requesting retransmission of a set of message segments to a given receiver is received from the given receiver. The given retransmit message then is parsed to determine both the identity of the given receiver, and the identity of the set of message segments requested by the given receiver. A message unit then is produced in the memory for each of the set of message segments that does not have an existing message unit in memory. Data representing the identity of the given receiver then is added to all message units for the set of message segments.
In preferred embodiments, each message unit is identified by an identifier, and each message unit is indexed based upon the identifier of its associated message segment. The message units in memory may form a queue, or some other structure. The message initially may be transmitted in accord with a data transport protocol that utilizes negative acknowledgment messages. The set of message segments may include a plurality of message segments, or one message segment.
In some embodiments, it is determined if the sender has forwarded a confirmation message indicating its receipt of a retransmit message relating to each of the set of message segments. If determined that the sender has not forwarded the confirmation message for at least one of the set of segments, then a new retransmit message is forwarded to the sender. The new retransmit message includes data relating to the at least one of the set of message segments. The new retransmit message may be aggregated with data relating to a plurality of message segments in the set of message segments.
In accordance with another aspect of the invention, an apparatus and method of requesting retransmission of a portion of a message having a plurality of message segments (that each are identified by a sequence identifier) indexes message units based upon the sequence identifiers. Prior to requesting retransmission, the message initially is transmitted toward a given receiver by a sender via an acknowledgment data transport protocol that requests retransmission of message segments. To that end, a retransmit message requesting retransmission of a plurality of missing message segments is received from the given receiver. The retransmit message then is segmented to add message segment data to a plurality of message units. Each message unit includes data for no more than one of the plurality of message segments. As noted above, the message units consequently are indexed based upon the sequence identifiers. The message segments are accessible by their sequence identifiers.
In some embodiments of this aspect of the invention, a given message unit having data relating to a given message segment is accessed. It then is determined, based upon the data in the given message unit, if the sender has forwarded a given confirmation message that indicates its receipt of a retransmit message relating to the given message segment. A new retransmit message requesting retransmission of the given message segment may be forwarded to the sender if it is determined that the sender has not forwarded the given confirmation message.
In accordance with another aspect of the invention, a method of re-transmitting a segmented message initially transmitted toward a given receiver by a sender via an acknowledgment data transport protocol (that requests retransmission of missing message segments) first receives a retransmit message from the receiver. The retransmit message requests retransmission of a set of message segments. A set of message units relating to the set of message units then are accessed. Each message unit in the set of message units includes data for no more than one of the set of message segments. A message unit is produced for each message segment in the set of message segments that does not have an existing message unit in the set of message units. All of the message segments are stored in a memory device (i.e., a distributed or single memory device). A new retransmit message is generated based upon the data in the message units in the memory device. The new retransmit message includes a request to retransmit
Cai Xiangrong
Crump Richard
Doong Janet
Baker Stephen M.
Nortel Networks Limited
Steubing McGuinness & Manaras LLP
LandOfFree
Apparatus and method of requesting retransmission of a... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Apparatus and method of requesting retransmission of a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Apparatus and method of requesting retransmission of a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3087426