[Ns-developers] calendar queue

[Mathieu Lacage]

hi,

I just pushed in ns-3-dev an implementation of the original 1988
calendar queue as well as a new command-line option
--SchedulerType=MyTypeId to switch event schedulers. The default is
still the std::map-based event scheduler.

For those interested, here is a copy of the relevant header
(src/simulator/calendar-scheduler.h):

/**                                                                                                                                                                   
 * \ingroup scheduler                                                                                                                                                 
 * \brief a calendar queue event scheduler                                                                                                                            
 *                                                                                                                                                                    
 * This event scheduler is a direct implementation of the algorithm known as a calendar queue.                                                                        
 * first published in 1988 in "Calendar Queues: A Fast O(1) Priority Queue Implementation for                                                                         
 * the Simulation Event Set Problem" by Randy Brown. There are many refinements published                                                                             
 * later but this class implements the original algorithm (to the best of my knowledge).                                                                              
 *                                                                                                                                                                    
 * Note: This queue is much slower than I expected (much slower than the std::map queue)                                                                              
 * and this seems to be because the original resizing policy is horribly bad. This is                                                                                 
 * most likely the reason why there have been so many variations published which all                                                                                  
 * slightly tweak the resizing heuristics to obtain a better distribution of events                                                                                   
 * across buckets.                                                                                                                                                    
 */

To summarize, it's slow as hell. I might have screwed up small heuristic
details so, if someone wants to look at it or to use it as a basis to
implement a dynamic calendar queue or a snoopy calendar queue, be my
guest.

regards,
Mathieu