Traffic shaping system with transmit latency feedback for asynchronous transfer mode networks

• US 5,515,363 A
• Filed: 06/30/1994
• Issued: 05/07/1996
• Est. Priority Date: 06/30/1994
• Status: Expired due to Term

• Current Assignee: Enterasys Networks Incorporated (Extreme Networks, Inc.)
• Original Assignee: Digital Equipment Corporation (HP Inc.)
• Inventors: Ramakrishnan, Kadangode K., Koning, G. Paul, De-Leon, Moshe, Ben-Nun, Michael, Ben-Michael, Simoni, Roman, Peter J.
• Primary Examiner(s): Olms, Douglas W.
• Assistant Examiner(s): BLUM, RUSSELL
• Application Number:
  US08/268,605
• Time in Patent Office: 677 Days
• Field of Search: 370/17, 370/58.2, 370/58.3, 370/60, 370/60.1, 370/61, 370/84, 370/85.6, 370/94.1, 370/94.2, 340/825.5, 340/825.51
• US Class Current: 370/232
• CPC Class Codes: H04L 12/5602 Bandwidth control in ATM Networks, e.g. leaky bucket
• CPC Class Codes: H04L 2012/5636 Monitoring or policing, e.g. compliance with allocated rate, corrective actions
• CPC Class Codes: H04L 2012/5679 Arbitration or scheduling

Abstract

A system for controlling the transmission of cells from a network node over multiple Virtual Circuits (VCs) is disclosed. The system performs traffic shaping, as required by connection based systems such as Asynchronous Transfer Mode (ATM), for each VC connected with a network node, so that the Quality of Service (Qos) parameters established when the connection was established are not exceeded. The system includes a process for scheduling the transmission of cells from the network node. The scheduling process periodically scans a table having entries corresponding to virtual circuits connected with the network node. During each scan of the table, the scheduler increments a sustainable rate accumulator field, a peak rate accumulator field, and a latency accumulator field of each table entry that corresponds with a virtual circuit that is open, and for which there is a cell ready to be transmitted. The scheduler further determines if the sustainable rate accumulator value is greater than or equal to a predetermined value and whether the peak rate accumulator value is greater than or equal to a predetermined value. If both conditions are true, then a cell may be transmitted on the virtual circuit corresponding with that table entry. The system further provides that transmissions are scheduled on virtual circuits having the greatest latency since previous transmissions.

Claims

1. A method for controlling the transmission of cells from a network node, comprising the steps of:

periodically scanning a table, said table having one or more entries, each one of said entries corresponding to a virtual circuit connected with said network node, said step of scanning including incrementing a first accumulator, a second accumulator and a third accumulator in each one of said table entries, said third accumulator value reflecting the time since the last transmission on said virtual circuit corresponding with said one of said table entries, and setting a transmit enable bit in each said table entry having a first accumulator value greater than or equal to a first predetermined value and having a second accumulator value greater than or equal to a second predetermined value;

selecting, responsive to said step of scanning, one of said table entries having said transmit enable bit set and having a third accumulator value equal to or greater than the third accumulator value of any other table entry having said transmit enable bit set; and

transmitting, responsive to said step of selecting, a cell on a virtual circuit associated with said selected one of said table entries.

2. A system for controlling the transmission of cells from a network node, comprising:

a scheduling table having one or more entries, each entry indicating a virtual circuit and having a first rate accumulator field, a second rate accumulator field, a latency accumulator field, a first predetermined value, a second predetermined value and a latency increment field;

means for periodically scanning each said scheduling table entry every time period T, said scanning including incrementing said first rate accumulator field and said second rate accumulator field and adding the value of said latency increment field to said latency accumulator field;

means, responsive to said means for periodically scanning, for selecting one of said one or more scheduling table entries having said first rate accumulator field value greater than or equal to said first predetermined value and said second rate accumulator field value greater than or equal to said second predetermined value and having a latency accumulator field value greater than or equal to said latency accumulator field value of any other of said one or more scheduling table entries also having said first rate accumulator field value greater than or equal to said first predetermined value and said second rate accumulator field value greater than or equal to said second predetermined value; and

means, responsive to said means for selecting, for transmitting a cell on a virtual circuit indicated by said selected one of said one or more scheduling table entries.

3. The system as in claim 2, wherein the value of said latency increment field for a given one of said one or more scheduling table entries is inversely related to a Cell Delay Variation (CDV) tolerance parameter specified in a connection request issued by a user for a virtual circuit indicated by said given one of said one or more scheduling table entries.

4. The system of claim 2, wherein said first predetermined value for a given one of said one or more scheduling table entries equals the inverse of a predetermined sustainable cell rate limit for the virtual circuit indicated by said given one of said one or more scheduling table entries divided by said time period T, and said means for periodically scanning increments said first rate accumulator field by adding an increment value to said first rate accumulator field value, said increment value equal to 1.

5. The system of claim 4, wherein said second predetermined value for a given one of said one or more entries equals the inverse of a predetermined peak cell rate limit for the virtual circuit indicated by said given one of said one or more scheduling table entries divided by said time period T, and said means for periodically scanning increments said second rate accumulator by adding an increment value to said second rate accumulator field value, said increment value equal to 1.

6. The system of claim 2, wherein said first predetermined value for each of said one or more entries equals 1, and said means for periodically scanning increments said first rate accumulator of a given scheduling table entry by adding an increment value to said first rate accumulator field value, wherein said increment value equals a number of cells that may be transmitted by said network node during said time period T on a virtual circuit indicated by said given scheduling table entry, without exceeding a predetermined sustainable rate of transmission permitted for said indicated virtual circuit.

7. The system of claim 6, wherein said second predetermined value for each of said one or more entries equals 1, and said means for periodically scanning increments said second rate accumulator field of a given scheduling table entry by adding an increment value to said second rate accumulator field value, said increment value equal to a number of cells that may be transmitted on a virtual circuit indicated by said given scheduling table entry during said time period T without exceeding a predetermined peak rate of transmission permitted for said indicated virtual circuit.

8. The system of claim 5 or claim 7, further comprising:

one or more transmit queues, each transmit queue having zero or more entries, each transmit queue entry indicating a packet to be transmitted and a virtual circuit on which said packet is to be transmitted, said packet consisting of one or more cells;

each scheduling table entry corresponding with one of said one or more transmit queues;

a virtual circuit table having one or more entries, each entry corresponding with a virtual circuit established with said network node, each entry having a first rate accumulator field, a second rate accumulator field, a first predetermined value field, a second predetermined value field and a latency increment field; and

scheduler table loading means, responsive to a new entry arriving at the head of one of said one or more transmit queues, and further responsive to said scheduling table and said virtual circuit table, for determining a virtual circuit `C` indicated by said entry at the head of said transmit queue, for determining a virtual circuit table entry `E` corresponding with said virtual circuit `C`, and for copying the values of said first rate accumulator field and said second rate accumulator field of virtual circuit table entry `E` into said first rate accumulator field and said second rate accumulator field of a scheduling table entry corresponding with said one of said one or more transmit queues.

9. The system of claim 8, said scheduler table loading means further copying said latency increment field value in said virtual circuit table entry `E` into the latency increment field of said scheduling table entry corresponding with said one of said one or more transmit queues.

10. The system of claim 9, further comprising:

means, responsive to said means for selecting and said means for transmitting, for processing said selected one of said one or more entries, said processing including subtracting said first predetermined value from said first rate accumulator field value, subtracting said second predetermined value from said second rate accumulator field value and zeroing said latency accumulator field.

11. The system of claim 10, further comprising:

means, responsive to a new entry arriving at the head of one of said one or more transmit queues, and further responsive to said scheduling table and said virtual circuit table, and operating prior to said scheduling table loading means, for copying said first rate accumulator field value and said second rate accumulator field value of said scheduling table entry corresponding with said one of said one or more transmit queues into said first rate accumulator field and said second rate accumulator field of a virtual circuit table entry indicated by said scheduling table entry corresponding with said one of said one or more transmit queues.

12. The system of claim 2, wherein said time period T is equal to one cell time, where said one cell time is a time period equal to the amount of time required by said network node to transmit one cell onto said network.

13. The system of claim 2, each of said one or more scheduling table entries further including a limit field having a limit value, wherein said means for periodically scanning further comprises setting said first rate accumulator field value to said limit value when said first rate accumulator field value is greater than said limit value after said first rate accumulator field is incremented.

14. The system of claim 2, wherein said incrementing of said second rate accumulator field in said means for periodically scanning is responsive to said value of said second rate accumulator field being less than said second predetermined value.

15. The system of claim 2, further comprising:

each one of said one or more scheduling table entries including a priority field having a value equal to the priority of traffic on said virtual circuit indicated by said scheduling table entry; and

said means for selecting selecting one of said one or more scheduling table entries having a higher priority than any other of said one or more scheduling table entries also having said first rate accumulator field value greater than or equal to said first predetermined value and said second rate accumulator field value greater than or equal to said second predetermined value.