Scalable Hierarchical Coarse-grained Timers

摘要

Several network servers and routing and signalling protocols need a large number of events to be scheduled off timers. Some of these applications can withstand a bounded level of inaccuracy in when the timer is scheduled. In this paper we describe a novel mechanism called "scalable hierarchical coarse grained timers" which can handle the scheduling of a large number of events while incurring a minimum of cpu and memory overhead. The techniques presented here were implemented on a commercial IP routing system and are used by the routing stack to damp flapping BGP routes. The paper reflects our experiences in carrying out this implementation and the subsequent performance analysis.