Method and apparatus for fairly sharing excess bandwidth and packet dropping amongst subscribers of a data network

1. A method comprising:

monitoring a plurality of data flows at an ingress of an electronic switch fabric (ESF) to determine conformance with a respective subscribed bandwidth allocation associated with each data flow of the plurality of data flows;

determining at the ingress of the ESF and at an egress of the ESF whether there is excess bandwidth;

responsive to determining that there is no excess bandwidth, at the ESF:

determining an actual rate of over-subscribing for the at least one data flow by at least:

determining a difference between a rate of traffic flow for the at least one data flow and the respective subscribed bandwidth allocation associated with the at least one data flow and

determining a ratio between the difference and the rate of traffic flow for the at least one data flow, and

restricting one or more data flows of the plurality of data flows from exceeding the respective subscribed bandwidth allocation associated with at least one data flow of the one or more data flows, wherein restricting the one or more data flows comprises dropping attempted excess data in proportion to the actual rate of over-subscribing of the subscribed bandwidth allocation for the at least one data flow; and

responsive to determining that there is excess bandwidth at the ESF, permitting each of the one or more data flows to exceed the respective subscribed bandwidth allocation up to an extent of the excess bandwidth.

2. The method of claim 1 , further comprising additionally billing for exceeding the respective subscribed bandwidth allocation of the one or more data flows.

3. The method of claim 1 , wherein permitting the one or more data flows to exceed the respective subscribed bandwidth allocation comprises allocating a fair share of the excess bandwidth to each of the one or more data flows.

4. The method of claim 3 , further comprising:

billing based on the respective fair share allocated to the one or more data flows.

5. The method of claim 3 wherein allocating the fair share of the excess bandwidth to each of the one or more data flows comprises allocating the fair share of the excess bandwidth in proportion to the respective rate of over-subscribing of the respective subscribed bandwidth allocation.

6. The method of claim 1 further comprising:

monitoring an egress queue depth to determine destination queue depth status, and wherein restricting the one or more data flows comprises dropping the attempted excess data based on the destination queue depth status.

7. The method of claim 6 wherein permitting the one or more data flows to exceed the respective subscribed bandwidth allocation comprises billing based on the destination queue depth status.

8. The method of claim 6 wherein monitoring the plurality of data flows comprises monitoring the plurality of data flows based on the destination queue depth status.

9. The method of claim 8 wherein a drop probability function is generated in response to the actual rate of over-subscribing of the respective subscribed bandwidth allocation and the destination queue depth status.

10. The method of claim 9 wherein the drop probability function comprises a digitized input for each of at least three conditions, wherein the at least three conditions comprise: data flow within the respective subscribed bandwidth allocation; out-of-contract but within a predetermined burst size; and both out-of-contract and out-of-burst size.

11. The method of claim 10 wherein the drop probability function comprises a combination of the at least three conditions.

12. An apparatus, comprising:

an output scheduler, configured to determine a depth of an egress queue;

one or more flow monitors, configured to at least:

monitor a plurality of data flows at an ingress to determine conformance with a respective subscribed bandwidth allocation associated with each data flow,

determine a difference between a rate of traffic flow for at least one data flow and the respective subscribed bandwidth allocation associated with the at least one data flow, and

determine an actual rate of over-subscribing of the subscribed bandwidth allocation for the at least one data flow of the plurality of data flows based on a ratio between the difference and the rate of traffic flow for the at least one data flow; and

one or more gates, wherein at least one gate of the one or more gates is configured to at least:

receive the egress queue depth;

drop excess data for the at least one data flow based on the actual rate of over-subscribing of the subscribed bandwidth allocation for the at least one data flow, responsive to a determination that there is no excess bandwidth based on the egress queue depth; and

permit each of one or more data flows to exceed the respective subscribed bandwidth allocation for each of the one or more data flows up to the extent of the excess bandwidth, responsive to a determination that there is excess bandwidth based on the egress queue depth.

13. The apparatus of claim 12 further comprising a billing mechanism configured to additionally bill for exceeding the respective subscribed bandwidth allocation of the one or more data flows.

14. The apparatus of claim 12 wherein the at least one gate is further configured to allocate a fair share of the excess bandwidth to each of the one or more data flows.

15. The apparatus of claim 14 , further comprising:

a billing mechanism configured to bill based on the respective fair share allocated to each of the one or more data flows.

16. The apparatus of claim 14 wherein the at least one gate is further configured to allocate the fair share of the excess bandwidth in proportion to the respective rate of over-subscribing of the respective subscribed bandwidth allocation.

17. The apparatus of claim 12 , further comprising a billing mechanism configured to bill based on the destination queue depth status.

18. The apparatus of claim 12 , wherein the one or more flow monitors are further configured to monitor the plurality of data flows based on the egress queue depth.

19. The apparatus of claim 12 , wherein the one or more flow monitors are further configured to generate a drop probability function in response to the actual rate of over-subscribing of the respective subscribed bandwidth allocation and the egress queue depth.

20. The apparatus of claim 19 wherein the drop probability function comprises a digitized input for each of at least three conditions, wherein the at least three conditions comprise: data flow within the respective subscribed bandwidth allocation; out-of-contract but within a predetermined burst size; and both out-of-contract and out-of-burst size.

21. The apparatus of claim 20 wherein the drop probability function comprises a combination of the at least three conditions.

22. The apparatus of claim 20 wherein at least one of the one or flow monitors is configured to receive data packets from a corresponding plurality of data line cards, and to determine a condition of the at least three conditions is met for the received data packets.

23. The apparatus of claim 22 , wherein the at least one gate is further configured to communicate a decision for each of the received data packets to a switch router, and wherein the switch router is configured to add received data packets to the egress queue based on the determined condition of the at least three conditions for the received data packets.

24. The apparatus of claim 23 wherein the output scheduler comprises an adaptive data scheduler.

25. The apparatus of claim 24 wherein the adaptive data scheduler enables differentiated services for various different types of the plurality of data flows.

26. A method, comprising:

determining, at an electronic switch fabric (ESF), bandwidth utilization conformance of a plurality of data flows, each data flow sent from an ingress port to an egress port, by monitoring each data flow of the plurality of data flows at its respective ingress port;

determining, at the ESF, whether there is excess bandwidth at any of the egress ports of the plurality of data flows;

responsive to determining there is no excess bandwidth at a given egress port:

determining an actual rate of over-subscribing for at least one particular data flow egressing via the given egress port by at least:

determining a difference between a rate of traffic flow for the at least one particular data flow and a subscribed bandwidth allocation for the at least one particular data flow and

determining a ratio between the difference and the rate of traffic flow for the at least one data flow, and

dropping, at the ESF, attempted excess data in proportion to the actual rate of over-subscribing for the at least one particular data flow egressing via the given egress port while passing data within the subscribed bandwidth allocation for the at least one particular data flow; and

responsive to determining there is excess bandwidth at a given egress port, permitting, at the ESF, the at least one particular data flow to exceed the subscribed bandwidth allocation for the at least one particular data flow up to an extent of the excess bandwidth.

27. The method of claim 26 , further comprising: generating billing information for the particular data flow exceeding the subscribed bandwidth allocation for the at least one particular data flow.

28. The method of claim 26 , wherein a subset of the plurality of data flows exceed their respective subscribed bandwidth allocations and wherein permitting the at least one particular data flow to exceed the subscribed bandwidth allocation for the at least one particular data flow comprises: allocating a fair share of the excess bandwidth to each data flow in the subset of data flows.

29. The method of claim 28 , further comprising: generating billing information for each of the allocated fair shares.

30. The method of claim 26 , wherein allocating the fair share comprises allocating the fair share of the excess bandwidth in proportion to a respective rate of over-subscribing.

31. The method of claim 26 , further comprising: determining a destination queue depth status for each data flow of the plurality of data flows by monitoring an egress queue depth for the data flow; and wherein dropping attempted excess data further comprises dropping attempted excess data based on the egress queue depth.

32. The method of claim 26 , wherein dropping attempted excess data comprises using a drop probability function to drop attempted excess data.

33. The method of claim 32 , wherein the actual rate of over-subscribing for each of the at least one particular data flow is digitized into one of at least three conditions, the at least three conditions comprising: within the subscribed bandwidth allocation for the at least one particular data flow, out-of-contract but within burst size, and out-of-contract and out-of-burst-size.

34. The method of claim 33 , wherein the drop probability function comprises a combination of the at least three conditions.

35. A non-transitory computer-readable medium having instructions stored thereon, the instructions comprising:

instructions to monitor a plurality of data flows at an ingress of an electronic switch fabric (ESF) to determine conformance with a respective subscribed bandwidth allocation associated with each data flow of the plurality of data flows;

instructions to determine at the ingress of the ESF and at an egress of the ESF whether there is excess bandwidth;

instructions, responsive to determining that there is no excess bandwidth, to:

determine an actual rate of oversubscribing for the at least one data flow by at least:

determine a difference between a rate of traffic flow for the at least one data flow and the respective subscribed bandwidth allocation associated with the at least one data flow and

determine a ratio between the difference and the rate of traffic flow for the at least one data flow, and

restrict one or more data flows of the plurality of data flows from exceeding the respective subscribed bandwidth allocation associated with at least one data flow of the one or more data flows, wherein restricting the one or more data flows comprises dropping attempted excess data in proportion to the actual rate of over-subscribing of the subscribed bandwidth allocation for the at least one data flow; and

instructions to, responsive to determining that there is excess bandwidth at the ESF, permit each of the one or more data flows to exceed the respective subscribed bandwidth allocation up to an extent of the excess bandwidth.

36. The non-transitory computer-readable medium of claim 35 , further comprising instructions to additionally bill for exceeding the respective subscribed bandwidth allocation of the one or more data flows.

37. The non-transitory computer-readable medium of claim 35 , wherein the instructions to permit the one or more data flows to exceed the respective subscribed bandwidth allocation comprise instructions to allocate a fair share of the excess bandwidth to each of the one or more data flows.

38. The non-transitory computer-readable medium of claim 37 , further comprising instructions to bill based on the respective fair share allocated to the one or more data flows.

39. The non-transitory computer-readable medium of claim 35 , wherein the instructions to allocate the fair share of the excess bandwidth to each of the one or more data flows comprise instructions to allocate the fair share of the excess bandwidth in proportion to the respective rate of over-subscribing of the respective subscribed bandwidth allocation.

40. The non-transitory computer-readable medium of claim 35 , further comprising instructions to monitor an egress queue depth to determine destination queue depth status, and wherein the instructions to restrict the one or more data flows comprise instructions to drop the attempted excess data based on the destination queue depth status.

41. The non-transitory computer-readable medium of claim 40 , wherein the instructions to permit the one or more data flows to exceed the respective subscribed bandwidth allocation comprise instructions to bill based on the destination queue depth status.

42. The non-transitory computer-readable medium of claim 40 , wherein the instructions to monitor the plurality of data flows comprise instructions to monitor the plurality of data flows based on the destination queue depth status.

43. The non-transitory computer-readable medium of claim 42 , wherein a drop probability function is generated in response to the actual rate of over-subscribing of the respective subscribed bandwidth allocation and the destination queue depth status.

44. The non-transitory computer-readable medium of claim 43 , wherein the drop probability function comprises a digitized input for each of at least three conditions, wherein the at least three conditions comprise: data flow within the respective subscribed bandwidth allocation; out-of-contract but within a predetermined burst size; and both out-of- contract and out-of-burst size.

45. The non-transitory computer-readable medium of claim 44 , wherein the drop probability function comprises a combination of the at least three conditions.