Frame based traffic policing for a digital switch

• US 5,666,353 A
• Filed: 03/21/1995
• Issued: 09/09/1997
• Est. Priority Date: 03/21/1995
• Status: Expired due to Term

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Systems, Inc.
• Inventors: Hooshmand, Kambiz, Klausmeier, Daniel E., Corbalis, Charles M.
• Primary Examiner(s): Olms, Douglas W.
• Assistant Examiner(s): PHILLIPS, MATTHEW
• Application Number:
  US08/408,273
• Time in Patent Office: 903 Days
• Field of Search: 370/17, 370/58.1, 370/58.2, 370/58.3, 370/60, 370/60.1, 370/61, 370/91, 370/92, 370/93, 370/94.1, 370/230, 370/232, 370/233, 370/234, 370/905
• US Class Current: 370/230
• 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/5637 Leaky Buckets
• CPC Class Codes: H04L 2012/5648 Packet discarding, e.g. EPD, PTD
• CPC Class Codes: H04L 2012/5652 Cell construction, e.g. including header, packetisation, depacketisation, assembly, reassembly
• CPC Class Codes: H04Q 11/0478 Provisions for broadband connections

Abstract

A frame based traffic policing system that determines if incoming data cells are conforming or non-conforming according to the a traffic contract. The frame based traffic policing system first detects a cell at the beginning or end of a frame and determines if the frame conforms with a traffic contract. If the cell does not exceed the parameters of the traffic contract, then the frame based traffic policing system deems the cell as conforming. If the cell was the first cell of a frame, then frame based traffic policing system treats all the remaining cells in the frame as conforming or non-conforming depending upon if the first data cell was conforming or non-conforming. If the cell was the last cell of a frame, then frame based traffic policing system treats all the cells of the following frame as conforming or non-conforming depending upon if the last cell of a previous frame was conforming or non-conforming. In this manner, all the data cells are from the same frame receive the same treatment by the network. The frame based traffic policing system improves the throughout of the network since the network will be less likely to waste resources transmitting cells from a corrupted frame.

Claims

1. A method of regulating incoming traffic on a data communication link, the method comprising the steps of:

maintaining a counter for said communication link, said counter having a first limit;

receiving incoming cells on said data communication link, said incoming cells grouped into frames;

detecting if a received cell is a first cell in a frame,

treating the received cell as conforming if the received cell is a first cell of the frame and said counter is within said first limit;

treating the received cell as non-conforming if the received cell is a first cell of the frame and said counter is not within said first limit;

treating the received cell as conforming if the received cell is not a first cell of the frame and the first cell of the frame was conforming; and

treating the received cell as non-conforming if the received cell is not a first cell of the frame and the first cell of the frame was non-conforming.

2. The method of claim 1 further comprising the steps of:

incrementing said counter by an increment value when a cell is treated as conforming;

decrementing said counter by an amount proportional to an elapsed time.

3. The method as claimed in claim 2 wherein the counter has a second limit and said method further comprises the step of:

treating the received cell as non-conforming if the received cell is not a first cell of the frame and the counter exceeds said second limit.

4. The method as claimed in claim 1 wherein the non-conforming cells are discarded.

5. The method as claimed in claim 1 wherein the non-conforming cells are tagged as low priority such that said tagged cells are first to be dropped when congestion occurs.

6. The method as claimed in claim 1 wherein the counter is permitted to go above said first limit to accommodate an entire data frame.

7. The method as claimed in claim 1 wherein some of said cells are End-of-Frame cells and said End-of-Frame cells are always treated as conforming.

8. The method as claimed in claim 7 wherein said End-of-Frame cells are used to determine a start of a next frame.

9. The method as claimed in claim 4 wherein an End-of-Frame cell is treated as conforming when a respective frame from which said End-of-Frame cell belongs is conforming or when a frame following said End-of-Frame cell is conforming.

10. The method as claimed in claim 9 wherein said End-of-Frame cells are used to determine a start of a next frame.

11. An apparatus for regulating a data communication link, said data communication link receiving cells grouped into frames, the apparatus comprising the elements of:

a counter, the counter having a first limit;

a cell detection mechanism, the cell detection mechanism detecting if a received cell is a first cell of a frame; and

a traffic policing mechanism, the traffic policing mechanism determining a first cell of a frame to be conforming if the counter is below the first limit else determining said first cell of a frame to be non-conforming, the traffic policing mechanism determining a subsequent cell of said frame to be conforming if the first cell of the frame was conforming else determining said subsequent cell to be non-conforming.

12. The apparatus as claimed in claim 11 wherein the non-conforming cells are tagged as low priority such that said tagged cells are first to be dropped when congestion occurs.

13. The apparatus as claimed in claim 11 wherein said non-conforming cells are discarded.

14. The apparatus as claimed in claim 11 wherein the counter has a second limit and the traffic policing mechanism deems subsequent cells as non-conforming if said counter exceeds said second limit.

15. The apparatus as claimed in claim 14 wherein the counter is permitted to go above said first limit to accommodate a full data frame.

16. The apparatus as claimed in claim 11 wherein some of said cells are End-of-Frame cells and said End-of-Frame cells are always treated as conforming.

17. The apparatus as claimed in claim 16 wherein said End-of-Frame cells are used to determine a start of a next frame.

18. The apparatus as claimed in claim 11 wherein an End-of-Frame cell is treated as conforming when a respective frame from which said End-of-Frame cell belongs is conforming or when a frame following said End-of-Frame cell is conforming.

19. The apparatus as claimed in claim 18 wherein said End-of-Frame cells are used to determine a start of a next frame.

20. A method of regulating incoming traffic on a data communication link, said data communication link receiving cells, said cells organized into frames, said method comprising the steps of:

determining if a last cell of a frame would be conforming based upon a traffic policing function;

determining that cells in a subsequent frame following said last cell are nonconforming based upon whether said last cell was determined to be nonconforming.

21. The method as claimed in claim 20 wherein said traffic policing function is a continuous state leaky bucket algorithm.

22. The method as claimed in claim 20 wherein said traffic policing function is a virtual scheduling algorithm.

23. The method as claimed in claim 20 wherein said last cell of said frame is treated as conforming if said frame to which said last cell belongs was deemed to be conforming.

24. An apparatus for regulating a data communication link, said data communication link receiving cells grouped into frames, the apparatus comprising the elements of:

a counter, the counter having a first limit;

a cell detection mechanism, the cell detection mechanism detecting if a received cell is an End-of-Frame cell; and

a traffic policing mechanism, the traffic policing mechanism determining an End-of-Frame cell of a frame to be conforming if the counter is below the first limit else determining said End-of-Frame cell to be non-conforming, the traffic policing mechanism determining a subsequent frame to be conforming if said End-of-Frame cell was conforming else determining said subsequent frame to be non-conforming.

25. The apparatus as claimed in claim 24 wherein the non-conforming cells are tagged as low priority such that said tagged cells are first to be dropped when congestion occurs.

26. The apparatus as claimed in claim 24 wherein said non-conforming cells are discarded.

27. The apparatus as claimed in claim 24 wherein the counter has a second limit and the traffic policing mechanism deems subsequent cells as non-conforming if said counter exceeds said second limit.

28. The apparatus as claimed in claim 24 wherein the counter is permitted to go above said first limit to accommodate a full data frame.

29. The apparatus as claimed in claim 24 wherein said End-of-Frame cells are always treated as conforming.

30. The apparatus as claimed in claim 24 wherein said traffic policing mechanism is a continuous state leaky bucket algorithm.

31. The apparatus as claimed in claim 24 wherein said traffic policing mechanism is a virtual scheduling algorithm.

32. The apparatus as claimed in claim 24 wherein an End-of-Frame cell is treated as conforming if a frame to which said End-of-Frame cells belongs is conforming.