Large-scale timer management

• US 8,307,030 B1
• Filed: 04/20/2010
• Issued: 11/06/2012
• Est. Priority Date: 04/20/2010
• Status: Active Grant

• Current Assignee: Juniper Networks Incorporated
• Original Assignee: Juniper Networks Incorporated
• Inventors: Hu, Hanzhong
• Primary Examiner(s): DINH, KHANH Q
• Application Number:
  US12/763,869
• Time in Patent Office: 931 Days
• Field of Search: 709/203, 709/224, 709/228, 713/200
• US Class Current: 709/203
• CPC Class Codes: H04L 12/1403 Architecture for metering, charging or billing
• CPC Class Codes: H04L 43/022 by sampling
• CPC Class Codes: H04L 43/0876 Network utilisation, e.g. volume of load or congestion level

Abstract

In general, techniques are described for managing timers for large scale service statistics collection. For example, as described herein, a network device includes a timing wheel data structure defining a plurality of slots. A rate limiter selects up to a rate limit value of timer events stored in a first one of the slots, wherein the rate limit value is less than a total number of the plurality of timer events stored in the first one of the time slots. A timer service module services the selected timer events during the first time interval, wherein the timer service module defers at least one of the unserviced timer events from the first one of the slots to a second one of the slot. During a second time interval, the timer service module services at least one of the timer events deferred from the first one of the slots.

Claims

1. A method comprising:

storing, within a network device, a timing wheel data structure defining a plurality of slots, wherein the timing wheel data structure represents a span of time and the slots represent sequential time intervals;

during a first one of the time intervals, servicing up to a rate limit value of a plurality of timer events stored in a first one of the slots, wherein the rate limit value is less than a total number of the plurality of timer events stored in the first one of the time slots;

deferring at least one of the unserviced timer events from the first one of the slots to a second one of the slots that corresponds to a second one of the time intervals; and

during the second time interval, servicing at least one of the timer events deferred from the first one of the slots.

2. The method of claim 1,

wherein each one of the timer events is associated with a service session for a subscriber managed by the network device, and

wherein servicing up to the rate limit value of timer events comprises collecting service statistics for the service sessions associated with the timer events.

3. The method of claim 1, further comprising storing a data structure defining a wait pool to identify deferred timer events, and

wherein deferring at least one of the unserviced timer events from the first one of the slots comprises:

deleting the unserviced timer events from the first one of the time slots;

storing the unserviced timer events in the wait pool; and

during the second time interval, selecting at least one of the unserviced timer events in the wait pool and servicing the selected unserviced timer events.

4. The method of claim 3, further comprising modifying a timer event capacity of the wait pool responsive to memory availability for the network device.

5. The method of claim 3, further comprising dropping at least one of the unserviced timer events from the wait pool when a number of unserviced timer events stored by the wait pool exceeds a defer threshold.

6. The method of claim 5, further comprising:

upon dropping at least one of the unserviced timer events from the wait pool, marking the dropped, unserviced timer events as dropped,

wherein dropping at least one of the unserviced timer events from the wait pool comprises dropping unserviced timer events only when the unserviced timer events are not marked as dropped.

7. The method of claim 5, further comprising:

deleting the dropped, unserviced timer events from the wait pool; and

storing the dropped, unserviced timer events to one or more timing wheel slots in which the dropped, unserviced timer events were stored prior to being deferred.

8. The method of claim 1, further comprising servicing every timer event stored by the timing wheel, wherein an average timer event service rate of the network device exceeds an average timer event arrival rate of the network device.

9. The method of claim 1, further comprising:

during a third time interval, comparing a tick time of the timing wheel with a system time for the network device;

determining whether a skew between the tick time and system time is greater than a length of a time interval for the timing wheel;

determining whether a sum of (1) a number of timer events stored by a third slot that corresponds to the third time interval and (2) a number of timer events stored by a fourth slot that corresponds to a fourth time interval is fewer than the rate limit value, wherein the third time interval and the fourth time interval are contiguous in time; and

when the sum is fewer than the rate limit value, servicing the timer events stored by the third slot and the timer events stored by the fourth slot during the third time interval to synchronize the tick time and the system time.

10. The method of claim 1, further comprising servicing at least one of a plurality of timer events stored in the second one of the slots only when a number of timer events deferred from the first one of the slots is less than the rate limit value.

11. The method of claim 1,

wherein each one of the timer events specifies one or more criteria for matching one or more packet flows, and

wherein servicing up to the rate limit value of the timer events comprises collecting service statistics for packet flows that satisfy the criteria associated with the timer events.

12. A network device comprising:

a processor;

a memory storing a timing wheel data structure defining a plurality of slots, wherein the timing wheel data structure represents a span of time and the slots represent sequential time intervals;

a rate limiter executing on the processor to select up to a rate limit value of a plurality of timer events stored in a first one of the slots, wherein the rate limit value is less than a total number of the plurality of timer events stored in the first one of the time slots; and

a timer service module executing on the processor to service the selected timer events during the first time interval,

wherein the timer service module defers at least one of the unserviced timer events from the first one of the slots to a second one of the slots that corresponds to a second one of the time intervals, and

wherein the timer service module, during the second time interval, services at least one of the timer events deferred from the first one of the slots.

13. The network device of claim 12, wherein each one of the timer events is associated with a service session for a subscriber managed by the network device, and further comprising a statistics collection module to collect service statistics for the service sessions associated with the selected timer events when the timer service module services the selected timer events.

14. The network device of claim 12, further comprising an offload client to send the service statistics collected by the statistics collection module to a server.

15. The network device of claim 12, further comprising a wait pool data structure to identify and store deferred timer events,

wherein, to defer at least one of the unserviced timer events from the first one of the slots, the timer service module:

deletes the unserviced timer events from the first one of the time slots;

stores the unserviced timer events in the wait pool; and

during the second time interval, selects at least one of the unserviced timer events in the wait pool and services the selected unserviced timer events.

16. The network device of claim 15, wherein a timer event capacity of the wait pool is modifiable responsive to memory availability for the network device.

17. The network device of claim 15, further comprising a drop module to drop at least one of the unserviced timer events from the wait pool when a number of unserviced timer events stored by the wait pool exceeds a defer threshold.

18. The network device of claim 17,

wherein, upon dropping the second timer event from the wait pool, the drop module marks the dropped, unserviced timer events as dropped, and

wherein the drop module drops at least one of the unserviced timer events from the wait pool only when the unserviced timer events are not marked as dropped.

19. The network device of claim 17, wherein the drop module deletes the dropped unserviced timer events from the wait pool, and further comprising a timer insertion module to store the dropped, unserviced timer events to one or more timing wheel slots in which the dropped, unserviced timer events were stored prior to being deferred.

20. The network device of claim 12,

wherein the timer service module services every timer event stored by the timing wheel, and

wherein an average timer event service rate of the network device exceeds an average timer event arrival rate of the network device.

21. The network device of claim 12, wherein the timing wheel advances to a third slot, and further comprising a synchronization module to:

during a third time interval, compare a tick time of the timing wheel with a system time for the network device;

determine whether a skew between the tick time and system time is greater than a length of a time interval for the timing wheel; and

determine whether a sum of (1) a number of timer events stored by a third slot that corresponds to the third time interval and (2) a number of timer events stored by a fourth slot that corresponds to a fourth time interval is fewer than the rate limit value, wherein the third time interval and the fourth time interval are contiguous in time,

wherein, when the sum is fewer than the rate limit value, the timer service module services the timer events stored by the third slot and the timer events stored by the fourth slot during the third time interval to synchronize the tick time and the system time.

22. The network device of claim 12, wherein the timer service module services at least one of a plurality of timer events stored in the second one of the slots only when a number of timer events deferred from the first one of the slots is less than the rate limit value.

23. The network device of claim 12, further comprising a plurality of packet forwarding engines, wherein each packet forwarding engine manages one or more service sessions for the network device and includes a separate instance of the timing wheel, rate limiter, and timer service module.

24. A non-transitory computer-readable medium comprising instructions for causing a programmable processor to:

store, within a network device, a timing wheel data structure defining a plurality of slots, wherein the timing wheel data structure represents a span of time and the slots represent sequential time intervals;

during a first one of the time intervals, service up to a rate limit value of a plurality of timer events stored in a first one of the slots, wherein the rate limit value is less than a total number of the plurality of timer events stored in the first one of the time slots;

defer at least one of the unserviced timer events from the first one of the slots to a second one of the slots that corresponds to a second one of the time intervals; and

during the second time interval, service at least one of the timer events deferred from the first one of the slots.

25. The non-transitory computer-readable medium of claim 24, wherein the instructions further cause the processor to:

store a data structure defining a wait pool to identify deferred timer events, and

wherein, to defer at least one of the unserviced timer events from the first one of the slots, the instructions cause the processor to;

delete the unserviced timer events from the first one of the time slots;

store the unserviced timer events in the wait pool; and

during the second time interval, select at least one of the unserviced timer events in the wait pool and servicing the selected unserviced timer events.