ATM cell scheduler which uses a heap memory and associates timestamps with each channel

A method of scheduling the transmission of packet cells associated with a plurality of communications channels, comprising the steps of:

• sorting channel entries in a heap memory, each channel entry comprising a timestamp value associated with each channel, the timestamp value indicating a time at which the transmission of a cell for the associated channel is next due, the sorting step identifying a root channel entry corresponding to the next due channel;
• comparing the timestamp value of the root channel entry to a global time generated by a reference timer;
• and
• responsive to the comparing step determining that the global time has at least reached the timestamp value of the root channel entry, issuing a transmit credit for the channel associated with the root channel entry;
• after the step of issuing a transmit credit, retrieving an allowed cell rate value from a parameter memory for the channel associated with the root channel entry;
• deriving a new timestamp value for the channel associated with the root channel entry, the deriving step comprising:
• generating an offset timestamp value based upon a scheduler clock frequency divided by the allowed cell rate value;
• adding the offset timestamp value to a base timestamp value to produce the new timestamp value;
• and
• after the deriving step, repeating the sorting, comparing, and issuing steps.

A method of scheduling the transmission of packet cells associated with a plurality of communications channels, comprising the steps of:

• sorting channel entries in a heap memory, the sorting step performed by circuitry in a scheduler integrated circuit, each channel entry comprising a timestamp value associated with each channel, the timestamp value indicating a time at which the transmission of a cell for the associated channel is next due, the sorting step identifying a root channel entry corresponding to the next due channel, and the sorting step comprising:
• identifying first and second groups of the plurality of channels, the first group of the plurality of channels having timestamp values that are nearer due than the timestamp values of the second group of the plurality of channels;
• storing channel entries for the first group of the plurality of channels in a first parameter memory implemented in the scheduler integrated circuit;
• and
• storing channel entries for the second group of the plurality of channels in a second parameter memory implemented into memory external to the scheduler integrated circuit;
• comparing the timestamp value of the root channel entry to a global time generated by a reference timer;
• and
• responsive to the comparing step determining that the global time has at least reached the timestamp value of the root channel entry, issuing a transmit credit for the channel associated with the root channel entry.

A method of scheduling the transmission of packet cells associated with a plurality of communications channels, comprising the steps of:

• sorting channel entries in a heap memory, each channel entry comprising a timestamp value associated with each channel, the timestamp value indicating a time at which the transmission of a cell for the associated channel is next due, the sorting step identifying a root channel entry corresponding to the next due channel;
• comparing the timestamp value of the root channel entry to a global time generated by a reference timer;
• and
• responsive to the comparing step determining that the global time has at least reached the timestamp value of the root channel entry, issuing a transmit credit for the channel associated with the root channel entry;
• after the step of issuing a transmit credit, retrieving an allowed cell rate value for the one of the plurality of channels associated with the root channel entry;
• deriving a new timestamp value for the channel associated with the root channel entry, the deriving step comprising:
• generating an offset timestamp value based upon a scheduler clock frequency divided by the allowed cell rate value;
• adding the timestamp value for the channel associated with the root channel entry to the offset timestamp value to derive a future credit time value;
• comparing the future credit time value with the global time;
• responsive to the comparing step determining that the future credit time value is later than the global time, setting the new timestamp value to the future credit time value;
• and
• responsive to the comparing step determining that the future credit time value is earlier than the global time, adding the offset timestamp value to the global time to generate the new timestamp value;
• and
• after the deriving step, repeating the sorting, comparing, and issuing steps.

A network hub and ATM translator system, comprising:

• a host controller, having an interface for receiving local communications;
• and
• an ATM translator subsystem, comprising:
• a transceiver interface, coupled to a high data rate communications facility;
• segmentation and reassembly circuitry, coupled to the transceiver interface and to the host controller;
• parameter memory, for storing entries associated with each of a plurality of ATM communications channels;
• and
• a scheduler, coupled to the parameter memory and to the segmentation and reassembly processor, for scheduling the transmission of packet cells associated with the plurality of ATM communications channels by a sequence of operations, the scheduler comprising:
• heap sort circuitry for sorting channel entries in the parameter memory, each channel entry comprising a timestamp value associated with each channel, the timestamp value indicating a time at which the transmission of a cell for the associated channel is next due, and for identifying a root channel entry corresponding to the next due channel;
• a reference timer for generating a global time;
• a comparator for comparing the timestamp value of the root channel entry to the global time;
• and
• source behavior processor circuitry, coupled to the segmentation and reassembly circuitry issuing a transmit credit for the channel associated with the root channel entry.