Multiplex communications – Fault recovery
Reexamination Certificate
1999-06-18
2003-01-14
Kizou, Hassan (Department: 2662)
Multiplex communications
Fault recovery
C370S254000, C370S390000, C370S408000, C709S238000, C340S870030
Reexamination Certificate
active
06507562
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to multicast communication in computer networks, and more particularly to optimization of a repair tree in reliable multicast protocol.
BACKGROUND OF THE INVENTION
Communication between computers in a computer network can be established by one of several methods. These include unicast messaging (where a source station and a destination station exchange messages over a point to point path), broadcast communication (where a sender station transmits messages which may be received by all stations attached to the network), multicast communication (where a sender station transmits messages which may be received by a predetermined group of stations), and so forth.
Reliable point to point communication is established by use of sequence numbers in packets transmitted by a sending station, and by the receiving station transmitting an acknowledgement message (ACK message) or a negative acknowledgement message (NACK message) to the sending station. The sending station maintains a buffer containing messages which it has transmitted, and upon receipt of an ACK message indicating that a packet having a particular sequence number has been received, the sending station flushes that packet from its buffer. In the event that the sending station either receives a NACK message, or does not receive an ACK message during a certain timing period, then the sending station uses its buffer to retransmit the packet. Reliable unicast communication is established by requiring the sending station to retransmit packets until it has received an ACK message for each packet which it transmitted. An example of a reliable unicast protocol is the well known TCP/IP protocol.
A problem in reliable multicast transmission is that the sending station must respond to ACK or NACK messages transmitted by all of the receiving stations. If there are only a few receiving stations, such as for example ten (10) or so receiving stations, then receiving buffers in the transmitting station can handle the ACK or NACK traffic. However where there are hundreds of receiving stations, or thousands, or millions of receiving stations, the large number of ACK or NACK messages overwhelm the transmitting station.
It is standard engineering practice in the design of computer networks for a network manager (a person) to use a network management computer program to establish a repair tree for multicast communication. The manager assigns particular stations to be repair head stations for a particular group of receiving stations. The group of receiving stations along with the repair head station are referred to as a “repair group”, with a repair head station and member stations. The repair head stations provide a solution to the problem of too many ACK or NACK messages flooding the sending station by the repair head stations receiving, and reacting to, the ACK or NACK messages transmitted by member stations of their repair group.
A problem with establishing a repair tree having a plurality of repair head stations in a reliable multicast protocol is that the locations of the member stations may not be optimum for the repair head stations established by the network manager. For example, if the repair head stations are established in the United States, and the member stations are in Europe, Japan, and South America, then retransmitting repair packets is very expensive. And the network manager may not have complete information when he establishes the repair groups, and so he does not realize that he is imposing a very expensive solution on the repair tree.
Further, a second problem with a network manager establishing a repair tree is that the topology of the repair tree cannot respond to changes in network configuration. That is, in the network links go down, new links are established, routers go down, new routers come on line, etc., and if any of these changes affects to established repair tree, then the repair tree may become inoperative.
There is needed a method and apparatus to help establish an optimum topological arrangement of a repair tree in reliable multicast transmission, especially when the receiving stations are widely separated, and to establish a simple method for the repair tree to respond to changes in the topology of the network.
SUMMARY OF THE INVENTION
Receiver stations located close together in a computer network dynamically form a multicast repair tree by a plurality of receiver stations choosing a repair head station from among the closely located receiver stations.
A receiver station calculates its distance from a repair head station by subtracting the decremented TTL value read from the IP header from the initial value of the TTL parameter carried in field TTL SCOPE of HELLO messages, transmitted by repair head stations.
Using a criteria that a closer repair head station is a more optimum repair head station, receiver stations listen to each received HELLO message, calculate the distance to the repair head station, and reaffiliate with the closest repair head station.
REFERENCES:
patent: 5036518 (1991-07-01), Tseung
patent: 5355371 (1994-10-01), Auerbach et al.
patent: 5675741 (1997-10-01), Aggarwal et al.
patent: 5748736 (1998-05-01), Mittra
patent: 5831975 (1998-11-01), Chen et al.
patent: 5905871 (1999-05-01), Buskens et al.
patent: 6104695 (2000-08-01), Wesley et al.
patent: 6151633 (2000-11-01), Hurst et al.
patent: 6185698 (2001-02-01), Wesley et al.
patent: 6192404 (2001-02-01), Hurst et al.
patent: 6269085 (2001-07-01), Provino et al.
patent: 6275859 (2001-08-01), Wesley et al.
patent: 6427166 (2002-07-01), Hurst et al.
Bell et al., “Review if Point-to-point Network Routing Algorithm, ” IEEE, Jan. 24, pp. 1-5.*
U.S. patent application Ser. No. 09/336,699.
U.S. patent application Ser. No. 09/336,659.
U.S. patent application Ser. No. 09/336,671.
U.S. patent application Ser. No. 09/336,670.
Internet Research Task Force Reliable Multicast Meeting, Sep. 1997, http://www.east.isi.edu/RMRG
otes-rev0.html, 1-25.
Chiu Dah Ming
Hanna Stephen R.
Hurst Stephen A.
Kadansky Miriam C.
Perlman Radia J.
Cesari and McKenna LLP
Kizou Hassan
Qureshi Afsar M.
LandOfFree
DYNAMIC OPTIMIZATION FOR RECEIVERS USING DISTANCE BETWEEN 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 DYNAMIC OPTIMIZATION FOR RECEIVERS USING DISTANCE BETWEEN A..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and DYNAMIC OPTIMIZATION FOR RECEIVERS USING DISTANCE BETWEEN A... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3023091