Multiple ACK windows providing congestion control in reliable multicast protocol

• US 6,505,253 B1
• Filed: 06/18/1999
• Issued: 01/07/2003
• Est. Priority Date: 06/30/1998
• Status: Expired due to Term

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems (Oracle Corporation)
• Inventors: Perlman, Radia J., Chiu, Dah Ming, Hanna, Stephen R., Kadansky, Miriam C., Wesley, Joseph S., Hurst, Stephen A., Rosenzweig, Philip M.
• Primary Examiner(s): Maung, Zarni
• Assistant Examiner(s): Hu, Jinsong
• Application Number:
  US09/336,659
• Time in Patent Office: 1,299 Days
• Field of Search: 709/235, 709/224, 709/232, 709/106, 709/107, 709/227, 709/103, 370/229, 370/468, 370/408, 370/235, 395/650, 395/200, 395/800
• US Class Current: 709/235
• CPC Class Codes: H04L 1/1832 Details of sliding window management
• CPC Class Codes: H04L 12/185 with management of multicast group membership
• CPC Class Codes: H04L 12/1868 Measures taken after transmission, e.g. acknowledgments
• CPC Class Codes: H04L 2001/0093 Point-to-multipoint
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/15 in relation to multipoint traffic arrangements for broadcast or multicast in data networks H04L12/18
• CPC Class Codes: H04L 47/263 Rate modification at the source after receiving feedback
• CPC Class Codes: H04L 47/27 Evaluation or update of window size, e.g. using information derived from acknowledged [ACK] packets

Abstract

A multicast repair tree is established, the repair tree having one sender station and a plurality of repair head stations. A repair head station has an affiliated group of member stations. A repair head station retransmits a lost message to its affiliated group of member stations upon receipt from a member station of a NACK message indicating that the selected message was not received. Acknowledgment windows (ACK windows) are established in a member station for transmission of ACK or NACK message by the member station. A number of messages transmitted by the sender station during a transmission window is established. Also a same size of ACK window is established in the receiving stations, with a slot in the ACK window corresponding to each message transmitted by the repair head station. Each receiving station is assigned a slot in the ACK window during which time that receiving station transmits its ACK or NACK messages. Thus the ACK window slots assigned to receiver stations for transmission of ACK/NACK windows are staggered so that different receiver stations transmit their ACKNACK messages at different times. The slot for a particular receiver station to use may be assigned by a random process.

Claims

1. A method for controlling congestion in a computer network during multicast transmission, comprising:

establishing a multicast repair tree having one sender station and a plurality of repair head stations, a one of said repair head stations retransmitting a selected message received from said sender station to an affiliated group of member stations upon receipt from a member station of an information message (ACK/NACK message) indicating that said selected message was not received;

establishing a plurality of acknowledgment windows in a member station for transmission of said ACK/NACK message by said member station, each member station choosing one of said plurality of acknowledgment windows for transmission of its ACK/NACK mes-sage; and

transmitting said ACK/NACK message by a member station during its chosen acknowledgment window.

2. The method of claim 1 further comprising:

establishing thirty two (32) said acknowledgment windows; and

choosing by a member station one of said acknowledgment windows for transmission of its ACK/NACK message.

3. The method of claim 2 wherein said choosing step further comprises:

selecting said one of said acknowledgment windows by a random process.

4. The method of claim 2 wherein said choosing step further comprises:

selecting said one of said acknowledgment windows in response to receipt of a management message from a repair head station.

5. The method of claim 1 further comprising:

setting a transmission window to transmit N messages during one window;

assigning N ACK window slots in said member station;

assigning a member station one of said ACK acknowledgment windows for said member station to transmit its ACK/NACK message.

6. A method for controlling congestion in a computer network during multicast transmission, comprising:

establishing a multicast repair tree having one sender station and a plurality of repair head stations, one of said repair head stations retransmitting a selected message received from said sender station to an affiliated group of member stations upon receipt from a particular member station of said affiliated group of member stations of an information message (ACK/NACK message) indicating that said selected message was not received;

establishing a plurality of acknowledgment windows in a member station for transmission of said ACK/NACK message by said member station;

choosing by each member station one of said plurality of acknowledgment windows for transmission of its ACK/NACK message, where said choosing is done by a random process, wherein different member stations use acknowledgement windows chosen randomly from said plurality of acknowledgment windows;

transmitting said ACK/NACK message by a member station during its chosen acknowledgment window.

7. A method for controlling congestion in a computer network during multicast transmission, comprising:

establishing a multicast repair tree having one sender station and a plurality of repair head stations, each repair head station of said plurality of repair head stations transmitting multicast messages received from said sender station to member stations affiliated with said each repair head station, one of said repair head stations retransmitting a selected message received from said sender station upon receipt of an information message (ACK/NACK message) from a particular member station affiliated with said one of said repair head stations indicating that said selected message was not received;

establishing a plurality of acknowledgment windows in a member station for transmission of said ACK/NACK message by said member station;

choosing by each member station one of said plurality of acknowledgment windows for transmission of its ACK/NACK message, where said choosing is done by a random process, wherein different member stations use acknowledgement windows chosen randomly from said plurality of acknowledgment windows; and

transmitting said ACK/NACK message by a member station during its chosen acknowledgment window.

8. A method for controlling congestion in a computer network during multicast transmission, comprising:

establishing a multicast repair tree having one sender station and a plurality of repair head stations, each repair head station of said plurality of repair head stations transmitting multicast messages received from said sender station to member stations affiliated with said each repair head station, one of said repair head stations retransmitting a selected message received from said sender station upon receipt of an information message (ACK/NACK message) from a particular member station affiliated with said one of said repair head stations indicating that said selected message was not received;

establishing a plurality of acknowledgment windows in a member station for transmission of said ACK/NACK message by said member station;

choosing by each member station one of said plurality of acknowledgment windows for transmission of its ACK/NACK message;

transmitting said ACK/NACK message by a member station during its chosen acknowledgrnent window.

9. The method of claim 8, wherein said choosing step further comprises:

selecting said one of said plurality of acknowledgment windows for transmission of its ACK/NACK message by a random process, wherein different member stations use acknowledgement windows chosen randomly from said plurality of acknowledgment windows.

10. The method of claim 9, wherein said choosing step further comprises:

selecting said one of said plurality of acknowledgment windows for transmission of its ACK/NACK message in response to a management message received from a another repair head station.

11. The method of claim 9, wherein said choosing step further comprises:

selecting said one of said plurality of acknowledgment windows for transmission of its ACK/NACK message in response to a management message received from said sender station.