Fair scheduling in broadcast environments

• US 6,870,809 B1
• Filed: 10/08/1999
• Issued: 03/22/2005
• Est. Priority Date: 10/08/1999
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Vaidya, Nitin, Bahl, Paramvir
• Primary Examiner(s): Vu, Huy D.
• Assistant Examiner(s): RYMAN, DANIEL J
• Application Number:
  US09/415,901
• Time in Patent Office: 1,992 Days
• Field of Search: 370/235, 370/429, 370/448, 370/445, 370/447, 370/910, 370/229, 370/230, 370/232, 370/233, 370/234, 370/238, 370/400, 370/401, 370/412, 370/413, 370/415, 370/449, 370/468, 370/477
• US Class Current: 370/229
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/13 in a LAN segment, e.g. ring or bus
• CPC Class Codes: H04L 47/28 in relation to timing considerations
• CPC Class Codes: H04W 72/535 based on resource usage policies
• CPC Class Codes: H04W 74/085 collision avoidance

Abstract

Fair scheduling in broadcast environments is disclosed. In one embodiment, a computerized system includes a link through which packets are transmitted, and a plurality of nodes. Each node transmits a packet through the link when counting from a back-off interval reaches a predetermined transmission time. The back-off interval for each packet is based on at least a start tag of the packet, which is assigned to the packet when it arrives at or within the node for transmission over the link, such as at a controller (e.g., a medium-access controller, or MAC) of the node.

Claims

1. A method for fair scheduling comprising:

receiving a packet at a node;

assigning a start tag to the received packet, the start tag based, at least in part, on a maximum of a time measured by a virtual clock when the packet was received and a finish tag of a previously received packet, wherein the finish tag is based, at least in part, on a start tag of the previously received packet; and

transmitting the received packet at a time based, at least in part, on the assigned start tag, wherein transmitting the received packet comprises;

attempting to transmit the received packet;

assigning a back-off interval based, at least in part, on the assigned start tag minus a time measured by the virtual clock at a time when an attempt is made to transmit the received packet; and

transmitting the received packet after the back-off interval has expired.

2. The method according to claim 1 wherein the virtual clock is reset only once to zero and is updated whenever a packet is transmitted on the node.

3. The method according to claim 1 further comprising updating the virtual clock in response to the received packet being transmitted, wherein the virtual clock is based, at least in part, on a maximum of a time measured by the virtual clock when the received packet was transmitted and the assigned start tag of the received packet.

4. The method according to claim 1 further comprising assigning a finish tag based, at least in part, on the assigned start tag of the received packet.

5. The method according to claim 1 further comprising assigning a finish tag based, at least in part, on the assigned start tag plus a scaling factor multiplied by a length of the received packet divided by a weight of the node.

6. A machine-readable medium having computer-executable instructions for performing steps comprising:

receiving a packet at a node;

assigning a start tag to the received packet, the start tag based, at least in part, on a maximum of a time measured by a virtual clock when the packet was received and a finish tag of a previously received packet, wherein the finish tag is based, at least in part, on a start tag of the previously received packet; and

transmitting the received packet at a time based, at least in part, on the assigned start tag, wherein transmitting the received packet comprises;

attempting to transmit the received packet;

assigning a back-off interval based, at least in part, on the assigned start tag minus a time measured by the virtual clock at a time when an attempt is made to transmit the received packet; and

transmitting the received packet after the back-off interval has expired.

7. The medium of claim 6 wherein the virtual clock is reset only once to zero and is updated whenever a packet is transmitted on the node.

8. The medium of claim 6 having further computer-executable instructions for updating the virtual clock in response to the received packet being transmitted, wherein the virtual clock is based, at least in part, on a maximum of a time measured by the virtual clock when the received packet was transmitted and the assigned start tag of the received packet.

9. The medium of claim 6 having further computer-executable instructions for assigning a finish tag based, at least in part, on the assigned start tag of the received packet.

10. The medium of claim 6 having further computer-executable instructions for assigning a finish tag based, at least in part, on the assigned start tag plus a scaling factor multiplied by a length of the received packet divided by a weight of the node.

11. A computer system comprising:

an application generating a packet for transmission through a link operatively coupled to a computer; and

a controller to receive the packet, assign a start tag for the received packet based, at least in part, on a maximum of a time measured by a virtual clock when the packet was received and a finish tag of a previously received packet, wherein the finish tag is based, at least in part, on a start tag of the previously received packet, and transmit the received packet at a time based, at least in part, on the assigned start tag, wherein transmitting the received packet comprises;

attempting to transmit the received packet;

assigning a back-off interval based, at least in part, on the assigned start tag minus a time measured by the virtual clock at a time when an attempt is made to transmit the received packet; and

transmitting the received packet after the back-off interval has expired.