System and method for scheduling message transmission and processing in a digital data network

• US 20040208181A1
• Filed: 05/07/2004
• Published: 10/21/2004
• Est. Priority Date: 04/23/1998
• Status: Active Grant

• Current Assignee: Avago Technologies International Sales Pte Limited (Broadcom, Inc.)
• Original Assignee: Emulex Design & Manufacturing Corp. (Broadcom, Inc.)
• Inventors: Williams, James B., Wells, David S., Gutierrez, Maria C., Clayton, Shawn A., Godiwala, Nitin D., Follett, David R.
• Granted Patent: US 7,295,557 B2
• Time in Patent Office: Days
• US Class Current: 370/395.4
• CPC Class Codes: H04L 47/50 Queue scheduling
• CPC Class Codes: H04L 47/6215 Individual queue per QOS, rate or priority
• CPC Class Codes: H04L 47/6225 Fixed service order, e.g. Round Robin
• CPC Class Codes: H04L 49/901 using storage descriptor, e.g. read or write pointers
• CPC Class Codes: H04L 49/9078 using an external memory or storage device

Abstract

A system includes a plurality of computers interconnected by a network including one or more switching nodes. The computers transfer messages over virtual circuits established thereamong. A computer, as a source computer for one or more virtual circuit(s), schedules transmission of messages on a round-robin basis as among the virtual circuits for which it is source computer. Each switching node which forms part of a path for respective virtual circuits also forwards messages for virtual circuits in a round-robin manner, and, a computer, as a destination computer for one or more virtual circuit(s), schedules processing of received messages in a round-robin manner. Round-robin transmission, forwarding and processing at the destination provides a degree of fairness in message transmission as among the virtual circuits established over the network. In addition, messages are transmitted in one or more cells, with the round-robin transmission being on a cell basis, so as to reduce delays which may occur for short messages if a long messages were transmitted in full for one virtual circuit before beginning transmission of a short message for another virtual circuit. For each virtual circuit, the destination computer and each switching node along the path for the virtual circuit can generate a virtual circuit flow control message for transmission to the source computer to temporarily limit transmission over the virtual circuit if the amount of resources being taken up by messages for the virtual circuit exceeds predetermined thresholds, further providing fairness as among the virtual circuits. In addition, each switching node or computer can generate link flow control messages for transmission to neighboring devices in the network to temporarily limit transmission thereto if the amount of resources taken up by all virtual circuits exceeds predetermined thresholds, so as to reduce the likelihood of message loss.

Claims

1. A transmit scheduler for use in scheduling transmission of message packets by a source device over a network, each message packet being associated with one of a plurality of virtual circuits, the transmit scheduler comprising:

A. a virtual circuit task list configured to identify virtual circuits for which message packets are to be transmitted; and

B. a transmit task control configured to sequence through the virtual circuit task list to identify successive virtual circuits for which message packets are to be transmitted and, for each identified virtual circuit, to enable data to be obtained for transmission by said transmitter in a respective message packet, thereby to facilitate transmission of message packets by the transmitter so that messages are transmitted in a round-robin manner as among ones of the virtual circuits for which the device is the source device;

2. A transmit scheduler as defined in claim 1 in which said virtual circuit task list is configured to-include a plurality of prioritized task lists, the transmit task control being configured to select among said prioritized task lists and, for each prioritized task list so selected, identify a virtual circuit for which message packets are to be transmitted.

3. A transmit scheduler as defined in claim 2 in which each virtual circuit is identified by a virtual circuit identifier, the virtual circuit identifiers each having a value within a range of virtual circuit identifier values, each of said prioritized task lists comprising a bit map including a bit associated with each virtual circuit identifier value in said range, transmit task control being configured to, for each virtual circuit for which a message packet is to be transmitted at the respective priority level, set the bit in the bit map of the respective prioritized task list associated with the virtual circuit'"'"'s virtual circuit identifier value, the transmit task control using the set bits to identify virtual circuits for which message packets are to be transmitted.

4. A transmit scheduler as defined in claim 2 in which one or more message packets are associated with a message, each message having a beginning, one of said prioritized task lists being associated with virtual circuits for which data for message packets associated with the beginning of a message is to be obtained and another of said prioritized task lists being associated with virtual circuits for which data for message packets associated with the beginning of a message have been obtained, the transmit task control being configured to select from each of said prioritized task lists at a selected rate.

5. A transmit scheduler as defined in claim 4 in which the transmit task control alternates between said prioritized task lists.

6. A transmit scheduler as defined in claim 2 in which message packet transmission for said virtual circuits can be rate limited, one of said prioritized task list comprising a rate limited task list, the transmit task control being configured to select from said rate limited task list at a rate related to the rate limit.

7. A receive scheduler for use in scheduling processing in connection with message packets received by a destination device over a network, each message packet being associated with one of a plurality of virtual circuits, the receive scheduler comprising:

A. a virtual circuit task list configured to identify virtual circuits for which message packets have been received; and

B. a receive task control configured to sequence through the virtual circuit task list to identify successive virtual circuits for which message packets have been received, and, for each identified virtual circuit, to enable the transfer of data associated with said message packets to a data store for use by a receive host in a round-robin manner.

8. A receive scheduler as defined in claim 7 in which said virtual circuit task list is configured to include a plurality of prioritized task lists, the receive task control being configured to select among said prioritized task lists and, for each prioritized task list so selected, identify a virtual circuit for which message packets are to be transmitted.

9. A receive scheduler as defined in claim 8 in which each virtual circuit is identified by a virtual circuit identifier, the virtual circuit identifiers each having a value within a range of virtual circuit identifier values, each of said prioritized task lists comprising a bit map including a bit associated with each virtual circuit identifier value in said range, the receive task control being configured to, for each virtual circuit for which a message packet has been received, provide that the bit in the bit map of an appropriate one of the respective prioritized task lists associated with the virtual circuit'"'"'s virtual circuit identifier value be set, the receive task control using the set bits to identify virtual circuits for which message packets are to be transmitted.

10. A receive scheduler as defined in claim 8 in which said network interface of said destination device further includes a buffer for buffering received message packets, one of said prioritized task lists being associated with virtual circuits for which the buffer contains at least one message packet associated with a virtual circuit and another of said prioritized task lists being associated with virtual circuits for which the buffer contains message packets associated with a virtual circuit at a selected buffer congestion level, the receive task control being configured to select from each of said prioritized task lists at a selected rate.

11. A receive scheduler as defined in claim 8 in which one or more message packets are associated with a message, each message having an end, one of said prioritized task lists comprising an end of message task list.