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.

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< Object >	GetObject () 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< Object >	GetObject (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.

void	UnidirectionalAggregateObject (Ptr< Object > other)
	Aggregate an Object to another Object.

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.

SimpleRefCount &	operator= (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, bool permissive=false) 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.

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::Event >	Bucket
	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
Bucket *	m_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.

Related Symbols inherited from ns3::ObjectBase
static TypeId	GetObjectIid ()
	Ensure the TypeId for ObjectBase gets fully configured to anchor the inheritance tree properly.

Detailed Description

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

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.

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

Member Typedef Documentation

◆ Bucket

typedef std::list<Scheduler::Event> ns3::CalendarScheduler::Bucket

private

Calendar bucket type: a list of Events.

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

Constructor & Destructor Documentation

◆ CalendarScheduler()

ns3::CalendarScheduler::CalendarScheduler ( )

Constructor.

Definition at line 51 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 58 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 298 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] ev The new Event.

Definition at line 121 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 192 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]	newSize	The number of buckets.
[in]	newWidth	The size of the new buckets.

Definition at line 377 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 36 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] key The dimensionless time.

Returns: The bucket index.

Definition at line 112 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]	nBuckets	The number of buckets.
[in]	width	The bucket size, in dimensionless time units.
[in]	startPrio	The starting time.

Definition at line 86 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] ev Event to store in the event list

Implements ns3::Scheduler.

Definition at line 142 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 151 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 158 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 98 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] ev The event to remove

Implements ns3::Scheduler.

Definition at line 252 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 238 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] newSize The new number of buckets.

Definition at line 397 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 287 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 276 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] reverse If true, store events in decreasing time stamp order.

Definition at line 66 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 161 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 169 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 167 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 171 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 163 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 173 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 208 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 165 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] bucket The bucket to draw from.

Returns: The next event from the bucket.

Definition at line 190 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]	newEvent	The new event being inserted.
[in]	it	The current position in the bucket being examined.

Returns: true if the newEvent belongs before it.

Definition at line 197 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] bucket The bucket to pop from.

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

Referenced by DoRemoveNext(), and SetReverse().

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

src/core/model/calendar-scheduler.h
src/core/model/calendar-scheduler.cc

Public Member Functions

Static Public Member Functions

Private Types

Private Member Functions

Private Attributes

Additional Inherited Members

Detailed Description

Member Typedef Documentation

◆ Bucket

Constructor & Destructor Documentation

◆ CalendarScheduler()

◆ ~CalendarScheduler()

Member Function Documentation

◆ CalculateNewWidth()

◆ DoInsert()

◆ DoRemoveNext()

◆ DoResize()

◆ GetTypeId()

◆ Hash()

◆ Init()

◆ Insert()

◆ IsEmpty()

◆ PeekNext()

◆ PrintInfo()

◆ Remove()

◆ RemoveNext()

◆ Resize()

◆ ResizeDown()

◆ ResizeUp()

◆ SetReverse()

Member Data Documentation

◆ m_buckets

◆ m_bucketTop

◆ m_lastBucket

◆ m_lastPrio

◆ m_nBuckets

◆ m_qSize

◆ m_reverse

◆ m_width

◆ NextEvent

◆ Order

◆ Pop