[Ns-developers] calendar queue

[Mathieu Lacage]

hi,

Thanks to David Wei And David Wetherall, who accepted the necessary
license change, I ported the ns2 calendar queue to ns3. To try it,
--SchedulerType=ns3::Ns2CalendarScheduler

regards,
Mathieu



On Fri, 2009-01-09 at 08:22 +0100, Mathieu Lacage wrote:
> 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
>