##

4.2.3 The Calendar Queue Scheduler

The calendar queue scheduler
(Scheduler/Calendar../ns-2/scheduler.cc)
uses a data structure analogous to a one-year desk calendar,
in which events on the same month/day of multiple years can be recorded in
one day.
It is formally described in [6], and informally described
in Jain (p. 410) [15].
The implementation of Calendar queues in ns v2
was contributed by David Wetherall (presently at MIT/LCS).

The calendar queue scheduler since ns v2.33 is improved by the following
three algorithms:

- A heuristic improvement that changes the linear search direction
in enqueue operations. The original implementation searches the events in
a bucket in chronological order to find the in-order spot for the event
that is being inserted.
The new implementation searches the bucket in reverse chronological order
because the event being inserted is usually later than most of the events that are
already in the bucket.
- A new bucket width estimation that uses the average interval of
dequeued events as the estimation of bucket width. It is stated in
[6] that the optimal bucket width should be the average inverval of all events in the future.
The original implementation uses the average interval of future events currently in the most crowded bucket
as the estimation. This estimation is unstable because it is very likely
that many future events will be inserted into the bucket after this estimation, significantly changing the
averaged event interval in the bucket. The new implementation uses the observed event interval
in the past, which will not change, to estimate the event interval in future.
- SNOOPy Calendar Queue: a Calendar queue variant that dynamically
tunes the bucket width according to the cost trade-off between enqueue
operation and dequeue operation.
The SNOOPy queue improvement is described in [30].
In this implementation, there is one tcl parameter
`adjust_new_width_interval_ `
specifying the interval with which the SNOOPy queue should re-calculate the bucket width.
Setting this parameter to 0 turns off the SNOOPy queue algorithm and degrades the scheduler
back to the original Calendar Queue. In general, normal simulation users are
not expected to change this parameter.

The details of these improvements are described in [33].
The implementation of these three improvements was contributed by Xiaoliang (David) Wei at Caltech/NetLab.

Tom Henderson
2011-11-05