Method and system for bandwidth allocation tracking in a packet data network
View Patent ↗In a metropolitan area network, a method and system for maintaining an accurate total of the amount of allocated bandwidth on the network. A plurality of incoming packets are assigned to a respective plurality of queues of a metropolitan area network switch. Using a fair arbitration scheme, the respective queues are configured to empty at a specified output rate. A finish time for each respective queue is computed, the finish time describing a time at which the respective queue will be emptied using the output rate. The plurality of queues are grouped into multiple groups in accordance with their respective finish times. The earliest group includes the reserved rates of those queues having a finish time indicating an empty condition at a first time increment. The second earliest group includes the reserved rates of those queues having a finish time indicating an empty condition at a second time increment later than the first time increment, and so on. The amount of allocated bandwidth on the network is determined by tracking the sum of the reserved rates of all the multiple groups. The first time increment, second time increment, and the like are indexed with respect to a schedule clock. The earliest group thus indicates those queues that will have an empty condition at a next time increment of the schedule clock. The determination of the amount of allocated bandwidth can be accomplished in real time, thereby allowing the efficient allocation of unallocated bandwidth in real time.
1. A network device comprising:
logic to group individual data flows into buckets, each bucket comprising a plurality of queues; and
logic to track an active and inactive status of the individual data flows in real time.
2. The network device of claim 1 , wherein the logic to group individual data flows into buckets, each bucket comprising a plurality of queues further comprises:
each bucket comprising queues having a same empty time.
3. The network device of claim 1 , further comprising:
logic to allocate the bandwidth of inactive flows to active flows in real time.
4. The network device of claim 3 , wherein the logic to allocate the bandwidth of inactive flows to active flows in real time further comprises:
logic to allocate the bandwidth based at least in part on finish times of the queues.
5. The network device of claim 1 , further comprising:
logic to track a total allocated bandwidth for all active data flows.
6. A network comprising:
one or more devices together comprising logic to group individual data flows into buckets, each bucket comprising a plurality of queues; and
logic to track an active and inactive status of the individual data flows in real time.
7. The network of claim 6 , wherein the logic to group individual data flows into buckets, each bucket comprising a plurality of queues further comprises:
each bucket comprising queues having a same empty time.
8. The network of claim 6 , further comprising:
logic to allocate the bandwidth of inactive flows to active flows in real time.
9. The network of claim 8 , wherein the logic to allocate the bandwidth of inactive flows to active flows in real time further comprises:
logic to allocate the bandwidth based at least in part on finish times of the queues.
10. The network of claim 6 , further comprising:
logic to track a total allocated bandwidth for all active data flows.
11. A process in a network device, comprising:
grouping individual network data flows into buckets implemented as data storage locations within the network device, each bucket comprising a plurality of queues; and
the network device tracking an active and inactive status of the individual data flows in real time.
12. The process of claim 11 , wherein grouping individual data flows into buckets, each bucket comprising a plurality of queues further comprises:
grouping the flows into buckets each bucket comprising queues having a same empty time.
13. The process of claim 11 , further comprising:
allocating the bandwidth of inactive flows to active flows in real time.
14. The process of claim 13 , wherein allocating the bandwidth of inactive flows to active flows in real time further comprises:
allocating the bandwidth based at least in part on finish times of the queues.
15. The process of claim 11 , further comprising:
tracking a total allocated bandwidth for all active data flows.