A Discrete-Event Network Simulator
API
Loading...
Searching...
No Matches
ns3::CalendarScheduler Class Reference

a calendar queue event scheduler More...

#include "calendar-scheduler.h"

+ Inheritance diagram for ns3::CalendarScheduler:
+ Collaboration diagram for ns3::CalendarScheduler:

Public Member Functions

 CalendarScheduler ()
 Constructor.
 
 ~CalendarScheduler () override
 Destructor.
 
void Insert (const Scheduler::Event &ev) override
 Insert a new Event in the schedule.
 
bool IsEmpty () const override
 Test if the schedule is empty.
 
Scheduler::Event PeekNext () const override
 Get a pointer to the next event.
 
void Remove (const Scheduler::Event &ev) override
 Remove a specific event from the event list.
 
Scheduler::Event RemoveNext () override
 Remove the earliest event from the event list.
 
- Public Member Functions inherited from ns3::Scheduler
 ~Scheduler () override=0
 Destructor.
 
virtual void Insert (const Event &ev)=0
 Insert a new Event in the schedule.
 
virtual bool IsEmpty () const =0
 Test if the schedule is empty.
 
virtual Event PeekNext () const =0
 Get a pointer to the next event.
 
virtual void Remove (const Event &ev)=0
 Remove a specific event from the event list.
 
virtual Event RemoveNext ()=0
 Remove the earliest event from the event list.
 
- Public Member Functions inherited from ns3::Object
 Object ()
 Constructor.
 
 ~Object () override
 Destructor.
 
void AggregateObject (Ptr< Object > other)
 Aggregate two Objects together.
 
void Dispose ()
 Dispose of this Object.
 
AggregateIterator GetAggregateIterator () const
 Get an iterator to the Objects aggregated to this one.
 
TypeId GetInstanceTypeId () const override
 Get the most derived TypeId for this Object.
 
template<typename T >
Ptr< T > GetObject () const
 Get a pointer to the requested aggregated Object.
 
template<>
Ptr< ObjectGetObject () const
 Specialization of () for objects of type ns3::Object.
 
template<typename T >
Ptr< T > GetObject (TypeId tid) const
 Get a pointer to the requested aggregated Object by TypeId.
 
template<>
Ptr< ObjectGetObject (TypeId tid) const
 Specialization of (TypeId tid) for objects of type ns3::Object.
 
void Initialize ()
 Invoke DoInitialize on all Objects aggregated to this one.
 
bool IsInitialized () const
 Check if the object has been initialized.
 
- Public Member Functions inherited from ns3::SimpleRefCount< Object, ObjectBase, ObjectDeleter >
 SimpleRefCount ()
 Default constructor.
 
 SimpleRefCount (const SimpleRefCount &o)
 Copy constructor.
 
uint32_t GetReferenceCount () const
 Get the reference count of the object.
 
SimpleRefCountoperator= (const SimpleRefCount &o)
 Assignment operator.
 
void Ref () const
 Increment the reference count.
 
void Unref () const
 Decrement the reference count.
 
- Public Member Functions inherited from ns3::ObjectBase
virtual ~ObjectBase ()
 Virtual destructor.
 
void GetAttribute (std::string name, AttributeValue &value) const
 Get the value of an attribute, raising fatal errors if unsuccessful.
 
bool GetAttributeFailSafe (std::string name, AttributeValue &value) const
 Get the value of an attribute without raising errors.
 
virtual TypeId GetInstanceTypeId () const =0
 Get the most derived TypeId for this Object.
 
void SetAttribute (std::string name, const AttributeValue &value)
 Set a single attribute, raising fatal errors if unsuccessful.
 
bool SetAttributeFailSafe (std::string name, const AttributeValue &value)
 Set a single attribute without raising errors.
 
bool TraceConnect (std::string name, std::string context, const CallbackBase &cb)
 Connect a TraceSource to a Callback with a context.
 
bool TraceConnectWithoutContext (std::string name, const CallbackBase &cb)
 Connect a TraceSource to a Callback without a context.
 
bool TraceDisconnect (std::string name, std::string context, const CallbackBase &cb)
 Disconnect from a TraceSource a Callback previously connected with a context.
 
bool TraceDisconnectWithoutContext (std::string name, const CallbackBase &cb)
 Disconnect from a TraceSource a Callback previously connected without a context.
 

Static Public Member Functions

static TypeId GetTypeId ()
 Register this type.
 
- Static Public Member Functions inherited from ns3::Scheduler
static TypeId GetTypeId ()
 Register this type.
 
- Static Public Member Functions inherited from ns3::Object
static TypeId GetTypeId ()
 Register this type.
 
- Static Public Member Functions inherited from ns3::ObjectBase
static TypeId GetTypeId ()
 Get the type ID.
 

Private Types

typedef std::list< Scheduler::EventBucket
 Calendar bucket type: a list of Events.
 

Private Member Functions

uint64_t CalculateNewWidth ()
 Compute the new bucket size, based on up to the first 25 entries.
 
void DoInsert (const Scheduler::Event &ev)
 Insert a new event in to the correct bucket.
 
Scheduler::Event DoRemoveNext ()
 Remove the earliest event.
 
void DoResize (uint32_t newSize, uint64_t newWidth)
 Resize the number of buckets and width.
 
uint32_t Hash (uint64_t key) const
 Hash the dimensionless time to a bucket.
 
void Init (uint32_t nBuckets, uint64_t width, uint64_t startPrio)
 Initialize the calendar queue.
 
void PrintInfo ()
 Print the configuration and bucket size distribution.
 
void Resize (uint32_t newSize)
 Resize to a new number of buckets, with automatically computed width.
 
void ResizeDown ()
 Halve the number of buckets if necessary.
 
void ResizeUp ()
 Double the number of buckets if necessary.
 
void SetReverse (bool reverse)
 Set the insertion order.
 

Private Attributes

Bucketm_buckets
 Array of buckets.
 
uint64_t m_bucketTop
 Priority at the top of the bucket from which last event was dequeued.
 
uint32_t m_lastBucket
 Bucket index from which the last event was dequeued.
 
uint64_t m_lastPrio
 The priority of the last event removed.
 
uint32_t m_nBuckets
 Number of buckets in the array.
 
uint32_t m_qSize
 Number of events in queue.
 
bool m_reverse = false
 Bucket ordering.
 
uint64_t m_width
 Duration of a bucket, in dimensionless time units.
 
Scheduler::Event &(* NextEvent )(Bucket &bucket)
 Get the next event from the bucket, according to m_reverse.
 
bool(* Order )(const EventKey &newEvent, const EventKey &it)
 Ordering function to identify the insertion point, according to m_reverse.
 
void(* Pop )(Bucket &)
 Pop the next event from the bucket, according to m_reverse.
 

Additional Inherited Members

- Protected Member Functions inherited from ns3::Object
 Object (const Object &o)
 Copy an Object.
 
virtual void DoDispose ()
 Destructor implementation.
 
virtual void DoInitialize ()
 Initialize() implementation.
 
virtual void NotifyNewAggregate ()
 Notify all Objects aggregated to this one of a new Object being aggregated.
 
- Protected Member Functions inherited from ns3::ObjectBase
void ConstructSelf (const AttributeConstructionList &attributes)
 Complete construction of ObjectBase; invoked by derived classes.
 
virtual void NotifyConstructionCompleted ()
 Notifier called once the ObjectBase is fully constructed.
 

Detailed Description

a calendar queue event scheduler

Introspection did not find any typical Config paths.

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).

This class uses a vector of buckets; each bucket covers a uniform time span. The bucket index for an event with timestamp ts is (ts / m_width) % m_nBuckets. This class automatically adjusts the number of buckets to keep the average occupancy around 2. Buckets themselves are implemented as a std::list<>, and events are kept sorted within the buckets.

Time Complexity
Operation Amortized Time Reason
Insert() ~Constant Ordering within bucket; possible resize
IsEmpty() Constant Explicit queue size
PeekNext() ~Constant Search buckets
Remove() ~Constant Search within bucket; possible resize
RemoveNext() ~Constant Search buckets; possible resize
Memory Complexity
Category Memory Reason
Overhead 2 x sizeof (*) + size_t
(24 bytes)
std::list
Per Event 2 x sizeof (*) std::list
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.
While inserion sort is not discussed in the original article, its implementation appears to dramatically affect performance. The default implementation sorts buckets in increasing (chronological) order. The alternative, sorting buckets in decreasing order, was adopted in NS-2 because they observed that new events were more likely to be later than already scheduled events. In this case sorting buckets in reverse chronological order reduces enqueue time.


Attributes

  • Reverse: Store events in reverse chronological order
    • Set with class: ns3::BooleanValue
    • Underlying type: bool
    • Initial value: false
    • Flags: construct

No TraceSources are defined for this type.
Size of this type is 120 bytes (on a 64-bit architecture).

Definition at line 93 of file calendar-scheduler.h.

Member Typedef Documentation

◆ Bucket

Calendar bucket type: a list of Events.

Definition at line 169 of file calendar-scheduler.h.

Constructor & Destructor Documentation

◆ CalendarScheduler()

ns3::CalendarScheduler::CalendarScheduler ( )

Constructor.

Definition at line 62 of file calendar-scheduler.cc.

References Init(), m_qSize, and NS_LOG_FUNCTION.

+ Here is the call graph for this function:

◆ ~CalendarScheduler()

ns3::CalendarScheduler::~CalendarScheduler ( )
override

Destructor.

Definition at line 69 of file calendar-scheduler.cc.

References m_buckets, and NS_LOG_FUNCTION.

Member Function Documentation

◆ CalculateNewWidth()

uint64_t ns3::CalendarScheduler::CalculateNewWidth ( )
private

Compute the new bucket size, based on up to the first 25 entries.

Returns
The new width.

Definition at line 309 of file calendar-scheduler.cc.

References DoInsert(), DoRemoveNext(), m_bucketTop, m_lastBucket, m_lastPrio, m_qSize, and NS_LOG_FUNCTION.

Referenced by Resize().

+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ DoInsert()

void ns3::CalendarScheduler::DoInsert ( const Scheduler::Event ev)
private

Insert a new event in to the correct bucket.

Parameters
[in]evThe new Event.

Definition at line 132 of file calendar-scheduler.cc.

References Hash(), ns3::Scheduler::Event::key, m_buckets, ns3::Scheduler::EventKey::m_ts, ns3::Scheduler::EventKey::m_uid, NS_LOG_FUNCTION, NS_LOG_LOGIC, and Order.

Referenced by CalculateNewWidth(), DoResize(), and Insert().

+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ DoRemoveNext()

Scheduler::Event ns3::CalendarScheduler::DoRemoveNext ( )
private

Remove the earliest event.

Returns
The earliest event.

Definition at line 203 of file calendar-scheduler.cc.

References Hash(), IsEmpty(), ns3::Scheduler::Event::key, m_buckets, m_bucketTop, ns3::Scheduler::EventKey::m_context, m_lastBucket, m_lastPrio, m_nBuckets, ns3::Scheduler::EventKey::m_ts, ns3::Scheduler::EventKey::m_uid, m_width, NextEvent, NS_ASSERT, NS_LOG_FUNCTION, and Pop.

Referenced by CalculateNewWidth(), and RemoveNext().

+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ DoResize()

void ns3::CalendarScheduler::DoResize ( uint32_t  newSize,
uint64_t  newWidth 
)
private

Resize the number of buckets and width.

Parameters
[in]newSizeThe number of buckets.
[in]newWidthThe size of the new buckets.

Definition at line 388 of file calendar-scheduler.cc.

References DoInsert(), Init(), m_buckets, m_lastPrio, m_nBuckets, and NS_LOG_FUNCTION.

Referenced by Resize().

+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ GetTypeId()

TypeId ns3::CalendarScheduler::GetTypeId ( )
static

Register this type.

Returns
The object TypeId.

Definition at line 47 of file calendar-scheduler.cc.

References ns3::TypeId::ATTR_CONSTRUCT, ns3::MakeBooleanAccessor(), ns3::MakeBooleanChecker(), ns3::TypeId::SetParent(), and SetReverse().

Referenced by SimulatorTestSuite::SimulatorTestSuite().

+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ Hash()

uint32_t ns3::CalendarScheduler::Hash ( uint64_t  key) const
inlineprivate

Hash the dimensionless time to a bucket.

Parameters
[in]keyThe dimensionless time.
Returns
The bucket index.

Definition at line 123 of file calendar-scheduler.cc.

References m_nBuckets, m_width, and NS_LOG_FUNCTION.

Referenced by DoInsert(), DoRemoveNext(), Init(), and Remove().

+ Here is the caller graph for this function:

◆ Init()

void ns3::CalendarScheduler::Init ( uint32_t  nBuckets,
uint64_t  width,
uint64_t  startPrio 
)
private

Initialize the calendar queue.

Parameters
[in]nBucketsThe number of buckets.
[in]widthThe bucket size, in dimensionless time units.
[in]startPrioThe starting time.

Definition at line 97 of file calendar-scheduler.cc.

References Hash(), m_buckets, m_bucketTop, m_lastBucket, m_lastPrio, m_nBuckets, m_width, and NS_LOG_FUNCTION.

Referenced by CalendarScheduler(), and DoResize().

+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ Insert()

void ns3::CalendarScheduler::Insert ( const Scheduler::Event ev)
overridevirtual

Insert a new Event in the schedule.

Parameters
[in]evEvent to store in the event list

Implements ns3::Scheduler.

Definition at line 153 of file calendar-scheduler.cc.

References DoInsert(), m_qSize, NS_LOG_FUNCTION, and ResizeUp().

+ Here is the call graph for this function:

◆ IsEmpty()

bool ns3::CalendarScheduler::IsEmpty ( ) const
overridevirtual

Test if the schedule is empty.

Returns
true if the event list is empty and false otherwise.

Implements ns3::Scheduler.

Definition at line 162 of file calendar-scheduler.cc.

References m_qSize, and NS_LOG_FUNCTION.

Referenced by DoRemoveNext(), PeekNext(), Remove(), and RemoveNext().

+ Here is the caller graph for this function:

◆ PeekNext()

Scheduler::Event ns3::CalendarScheduler::PeekNext ( ) const
overridevirtual

Get a pointer to the next event.

This method cannot be invoked if the list is empty.

Returns
A pointer to the next earliest event. The caller takes ownership of the returned pointer.

Implements ns3::Scheduler.

Definition at line 169 of file calendar-scheduler.cc.

References ns3::Scheduler::Event::impl, IsEmpty(), ns3::Scheduler::Event::key, m_buckets, m_bucketTop, ns3::Scheduler::EventKey::m_context, m_lastBucket, m_nBuckets, ns3::Scheduler::EventKey::m_ts, ns3::Scheduler::EventKey::m_uid, m_width, NextEvent, NS_ASSERT, and NS_LOG_FUNCTION.

+ Here is the call graph for this function:

◆ PrintInfo()

void ns3::CalendarScheduler::PrintInfo ( )
private

Print the configuration and bucket size distribution.

Definition at line 109 of file calendar-scheduler.cc.

References m_buckets, m_nBuckets, m_width, and NS_LOG_FUNCTION.

◆ Remove()

void ns3::CalendarScheduler::Remove ( const Scheduler::Event ev)
overridevirtual

Remove a specific event from the event list.

This method cannot be invoked if the list is empty.

Parameters
[in]evThe event to remove

Implements ns3::Scheduler.

Definition at line 263 of file calendar-scheduler.cc.

References Hash(), ns3::Scheduler::Event::impl, IsEmpty(), ns3::Scheduler::Event::key, m_buckets, m_qSize, ns3::Scheduler::EventKey::m_ts, ns3::Scheduler::EventKey::m_uid, NS_ASSERT, NS_LOG_FUNCTION, and ResizeDown().

+ Here is the call graph for this function:

◆ RemoveNext()

Scheduler::Event ns3::CalendarScheduler::RemoveNext ( )
overridevirtual

Remove the earliest event from the event list.

This method cannot be invoked if the list is empty.

Returns
The Event.

Implements ns3::Scheduler.

Definition at line 249 of file calendar-scheduler.cc.

References DoRemoveNext(), IsEmpty(), ns3::Scheduler::Event::key, m_bucketTop, m_lastBucket, m_qSize, ns3::Scheduler::EventKey::m_ts, ns3::Scheduler::EventKey::m_uid, NS_ASSERT, NS_LOG_FUNCTION, NS_LOG_LOGIC, and ResizeDown().

+ Here is the call graph for this function:

◆ Resize()

void ns3::CalendarScheduler::Resize ( uint32_t  newSize)
private

Resize to a new number of buckets, with automatically computed width.

Parameters
[in]newSizeThe new number of buckets.

Definition at line 408 of file calendar-scheduler.cc.

References CalculateNewWidth(), DoResize(), and NS_LOG_FUNCTION.

Referenced by ResizeDown(), and ResizeUp().

+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ ResizeDown()

void ns3::CalendarScheduler::ResizeDown ( )
private

Halve the number of buckets if necessary.

Definition at line 298 of file calendar-scheduler.cc.

References m_nBuckets, m_qSize, NS_LOG_FUNCTION, and Resize().

Referenced by Remove(), and RemoveNext().

+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ ResizeUp()

void ns3::CalendarScheduler::ResizeUp ( )
private

Double the number of buckets if necessary.

Definition at line 287 of file calendar-scheduler.cc.

References m_nBuckets, m_qSize, NS_LOG_FUNCTION, and Resize().

Referenced by Insert().

+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ SetReverse()

void ns3::CalendarScheduler::SetReverse ( bool  reverse)
private

Set the insertion order.

This can only be used at construction, as invoked by the Attribute Reverse.

Parameters
[in]reverseIf true, store events in decreasing time stamp order.

Definition at line 77 of file calendar-scheduler.cc.

References m_reverse, NextEvent, NS_LOG_FUNCTION, Order, and Pop.

Referenced by GetTypeId().

+ Here is the caller graph for this function:

Member Data Documentation

◆ m_buckets

Bucket* ns3::CalendarScheduler::m_buckets
private

Array of buckets.

Definition at line 172 of file calendar-scheduler.h.

Referenced by ~CalendarScheduler(), DoInsert(), DoRemoveNext(), DoResize(), Init(), PeekNext(), PrintInfo(), and Remove().

◆ m_bucketTop

uint64_t ns3::CalendarScheduler::m_bucketTop
private

Priority at the top of the bucket from which last event was dequeued.

Definition at line 180 of file calendar-scheduler.h.

Referenced by CalculateNewWidth(), DoRemoveNext(), Init(), PeekNext(), and RemoveNext().

◆ m_lastBucket

uint32_t ns3::CalendarScheduler::m_lastBucket
private

Bucket index from which the last event was dequeued.

Definition at line 178 of file calendar-scheduler.h.

Referenced by CalculateNewWidth(), DoRemoveNext(), Init(), PeekNext(), and RemoveNext().

◆ m_lastPrio

uint64_t ns3::CalendarScheduler::m_lastPrio
private

The priority of the last event removed.

Definition at line 182 of file calendar-scheduler.h.

Referenced by CalculateNewWidth(), DoRemoveNext(), DoResize(), and Init().

◆ m_nBuckets

uint32_t ns3::CalendarScheduler::m_nBuckets
private

Number of buckets in the array.

Definition at line 174 of file calendar-scheduler.h.

Referenced by DoRemoveNext(), DoResize(), Hash(), Init(), PeekNext(), PrintInfo(), ResizeDown(), and ResizeUp().

◆ m_qSize

uint32_t ns3::CalendarScheduler::m_qSize
private

Number of events in queue.

Definition at line 184 of file calendar-scheduler.h.

Referenced by CalendarScheduler(), CalculateNewWidth(), Insert(), IsEmpty(), Remove(), RemoveNext(), ResizeDown(), and ResizeUp().

◆ m_reverse

bool ns3::CalendarScheduler::m_reverse = false
private

Bucket ordering.

If false (default), store events in increasing time stamp order. If true, store events in decreasing time stamp order.

Definition at line 219 of file calendar-scheduler.h.

Referenced by SetReverse().

◆ m_width

uint64_t ns3::CalendarScheduler::m_width
private

Duration of a bucket, in dimensionless time units.

Definition at line 176 of file calendar-scheduler.h.

Referenced by DoRemoveNext(), Hash(), Init(), PeekNext(), and PrintInfo().

◆ NextEvent

Scheduler::Event &(* ns3::CalendarScheduler::NextEvent) (Bucket &bucket)
private

Get the next event from the bucket, according to m_reverse.

Parameters
[in]bucketThe bucket to draw from.
Returns
The next event from the bucket.

Definition at line 201 of file calendar-scheduler.h.

Referenced by DoRemoveNext(), PeekNext(), and SetReverse().

◆ Order

bool(* ns3::CalendarScheduler::Order) (const EventKey &newEvent, const EventKey &it)
private

Ordering function to identify the insertion point, according to m_reverse.

Parameters
[in]newEventThe new event being inserted.
[in]itThe current position in the bucket being examined.
Returns
true if the newEvent belongs before it.

Definition at line 208 of file calendar-scheduler.h.

Referenced by DoInsert(), and SetReverse().

◆ Pop

void(* ns3::CalendarScheduler::Pop) (Bucket &)
private

Pop the next event from the bucket, according to m_reverse.

Parameters
[in]bucketThe bucket to pop from.

Definition at line 213 of file calendar-scheduler.h.

Referenced by DoRemoveNext(), and SetReverse().


The documentation for this class was generated from the following files: