Fair scheduling of ATM cell transmissions during overscheduled conditions

• US 6,115,360 A
• Filed: 12/19/1997
• Issued: 09/05/2000
• Est. Priority Date: 11/21/1997
• Status: Expired due to Term

• Current Assignee: Texas Instruments, Inc.
• Original Assignee: Texas Instruments, Inc.
• Inventors: Karguth, Brian J., Quay, Jeffrey R.
• Primary Examiner(s): Nguyen, Chau
• Assistant Examiner(s): Schuppner, Suibel M. H.
• Application Number:
  US08/994,332
• Time in Patent Office: 991 Days
• Field of Search: 370/395, 370/230, 370/232, 370/235, 370/236, 370/412, 370/468
• US Class Current: 370/235
• CPC Class Codes: H04L 12/5602 Bandwidth control in ATM Networks, e.g. leaky bucket
• CPC Class Codes: H04L 2012/5616 Terminal equipment, e.g. codecs, synch.
• CPC Class Codes: H04L 2012/5651 Priority, marking, classes
• CPC Class Codes: H04L 2012/5679 Arbitration or scheduling
• CPC Class Codes: H04Q 11/0478 Provisions for broadband connections

Abstract

A network hub and Asynchronous Transfer Mode (ATM) translator system (5) for use in a Local Area Network (LAN)-based communications system is disclosed. The network hub and ATM translator system (5) includes a host controller (10) that serves as the LAN hub, and which interfaces with a translator card (15) which includes a segmentation and reassembly device (12) in connection with SONET receive/transmit circuitry (20) that communicates with a transceiver (22) to transmit and receive ATM packet cells over a communications facility (FO). The translator card (15) also includes a scheduler (14) that includes a heap sort state machine (36) which maintains a sorted list of entries, in a heap fashion, in on-chip parameter memory (44) and off-chip parameter memory (18). The entries include, for each ATM channel, a channel identifier and a timestamp that indicates the time at which the next cell for the channel will be due for transmission. A due comparator (40) compares the timestamp of the root value in the heap (i.e., the channel with the next due cell) to a global time generated by a reference timer (38), and indicates to a source behavior processor (24) in the scheduler (14) that a cell is due for transmission. The scheduler than issues a transmit credit for the cell, and communicates this event with the SAR device (12) to effect the transmission as appropriate.

Claims

1. A method of allocating bandwidth for a plurality of communications channels, comprising the steps of:

determining an allowed cell rate value for each of the plurality of channels;

issuing a transmission credit for one of the plurality of channels having a lowest timestamp value;

for the channel for which a transmission credit was most recently issued in the issuing step, generating an offset timestamp value based upon a scheduler clock frequency divided by the allowed cell rate value for the channel;

adding a previous timestamp value for the channel, the previous timestamp value corresponding to a time at which the transmission credit was most recently generated, to the offset timestamp value to derive a future credit time value;

comparing the future credit time value with a global time; and

responsive to the comparing step determining that the future credit time value is later than the global time, setting a 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

repeating the issuing step.

2. The method of claim 1, further comprising:

storing the allowed cell rate values in a parameter memory, in association with the corresponding channels.

3. The method of claim 1, further comprising:

after the setting or adding step, as the case may be, sorting the plurality of channels according to their timestamp values.

4. The method of claim 3, further comprising:

responsive to the most recently generated new timestamp value matching a timestamp value associated with another of the plurality of channels, ordering the channel associated with the most recently generated new timestamp value after the another of the plurality of channels having the matching timestamp value.

5. 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;

circuitry for sorting channel entries in the parameter memory, according to 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, a root channel entry in the parameter memory 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;

processor circuitry, coupled to the segmentation and reassembly circuitry issuing a transmit credit for the channel associated with the root channel entry; and

circuitry for deriving a new timestamp value for the channel associated with the root channel entry, comprising;

a divider for generating an offset timestamp value based upon a scheduler clock frequency divided by the allowed cell rate value;

an adder for adding the offset timestamp value to a base timestamp value to produce the new timestamp value;

a multiplexer, having a first input for receiving the global time from the reference timer, having a second input for receiving the timestamp value of the root channel entry, having an output coupled to the adder to communicate the base timestamp value thereto, and having a control input for selecting either the global time or the timestamp value of the root channel entry for the base timestamp value; and

a multiplexer control function, for generating a select signal applied to the control input of the multiplexer, by performing the operations of;

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; and

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.

6. The system of claim 5, wherein the sorting circuitry comprises:

a heap sort state machine.

7. The system of claim 6, wherein the scheduler is integrated into a single integrated circuit.

8. The system of claim 5, wherein the scheduler further comprises:

on-chip parameter memory implemented into the same integrated circuit with the scheduler, for storing timestamp values associated with a first group of the plurality of channels;

wherein the parameter memory is external to the scheduler integrated circuit, and is for storing timestamp values associated with a second group 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.