Bug 2503

Summary:	PriorityQueueScheduler
Product:	ns-3	Reporter:	Alexander Krotov <krotov>
Component:	core	Assignee:	Peter Barnes <pdbarnes>
Status:	RESOLVED FIXED
Severity:	enhancement	CC:	ns-bugs, tomh
Priority:	P5
Version:	ns-3-dev
Hardware:	All
OS:	All

Description Alexander Krotov 2016-09-18 16:16:25 UTC

I have implemented a scheduler based on priority_queue. According to scheduler benchmark, it is faster than map scheduler, but slower than fixed (see bug 2498) calendar scheduler. Unlike calendar scheduler, it should be safe to make priority queue scheduler default one, because it is just a general-purpose priority queue.

Code is available at:
https://github.com/avkrotov/ns-3-dev-git/commits/scheduler

I had to delete Scheduler::Remove method and replace it with Scheduler::Cancel everywhere, because std::priority_queue does not provide required interfaces. It is a well-known bug, see for example: https://stackoverflow.com/questions/19467485/c-priority-queue-removing-element-not-at-top

Anyway, I think replacing Scheduler::Remove with Scheduler::Cancel everywhere is an improvement. Scheduler::Cancel is never slower and Scheduler::Remove is not more safe or something. Providing two interfaces that actually do the same is confusing, in some places code even Cancel immediately after Remove.

Comment 1 Peter Barnes 2019-11-26 14:01:36 UTC

Cancel just marks the events as cancelled.  Remove actually removes them from the Scheduler, freeing memory.  There are cases where one or the other is a better choice, so I'd prefer to leave Remove as an option.

+1 to replace with Cancel(), making this a GCI task

+1 to implement priority_queue, making this a GCI task

Comment 2 Peter Barnes 2019-11-26 14:08:17 UTC

Need to add this to bench-simulator as well, making a GCI task.

Comment 3 Peter Barnes 2019-11-26 15:35:54 UTC

My mistake, I see the first commit *does* add it to bench-simulator.

Comment 4 Peter Barnes 2020-02-26 18:51:55 UTC

This is three contributions.

Complete the set of comparison operators (< == != >) for Event and EventKey
Alexander Krotov's PriorityQueueScheduler, from Bug 2503

GCI 2019 patch which implements Remove for the PriorityQueueScheduler (the underlying std::priority_scheduler doesn't support remove() natively.)

Upstream merge request:
https://gitlab.com/nsnam/ns-3-dev/-/merge_requests/199

Please DO NOT SQUASH these on merge.

Comment 5 Tom Henderson 2020-05-04 09:55:31 UTC

Added to ns-3-dev in a series of patches from Peter, starting at commit 4434c65c

Comment 6 Peter Barnes 2020-05-12 21:36:05 UTC

Replace Remove with Cancel merged in 1f3735f6f06d7b58d634c51e89af6f3bd9145deb