Hi,
i attach 1 patch which can improve the performance (patch for the scheduler).
Please take a look for detailed information. Please let me know, whether it
helps in your case (if you use it).
Best regards,
Robert
Last thing: the patch is for ns-2.30 (ns-allinone-2.30).
On Donnerstag, 12. November 2009, Jonathan Kirchhoff wrote:
> Hi,
>
> I'm doing simulations of wireless ad-hoc routing protocols using
> nsclick. Everything appears to be working just fine, but in comparison
> to native NS-2 simulations, the ones using nsclick seem to be taking
> ages to finish. Here's an example:
>
> Native : 02:14min
> Nsclick: 12:34min
>
> Same protocol, scenario and simulated time.
>
> Is this something to be expected, or is the reason more likely to be
> found in my protocol implementation or simulation setup?
>
> Thanks!
>
> Regards
> Jonathan
> _______________________________________________
> click mailing list
> [email protected]
> https://amsterdam.lcs.mit.edu/mailman/listinfo/click
diff -urN ns-2.31/common/scheduler.cc ns-2.31-scheduler-doc/common/scheduler.cc
--- ns-2.31/common/scheduler.cc 2006-02-21 07:20:18.000000000 -0800
+++ ns-2.31-scheduler-doc/common/scheduler.cc 2007-11-11 22:39:02.000000000 -0800
@@ -581,6 +581,17 @@
} class_calendar_sched;
CalendarScheduler::CalendarScheduler() : cal_clock_(clock_) {
+ bind("adjust_new_width_interval_", &adjust_new_width_interval_);
+ bind("min_bin_width_", &min_bin_width_);
+ if (adjust_new_width_interval_) {
+ avg_gap_ = -2;
+ last_time_ = -2;
+ gap_num_ = 0;
+ head_search_ = 0;
+ insert_search_ = 0;
+ round_num_ = 0;
+ time_to_newwidth = adjust_new_width_interval_;
+ }
reinit(4, 1.0, cal_clock_);
}
@@ -595,47 +606,46 @@
CalendarScheduler::insert(Event* e)
{
int i;
- if (cal_clock_ > e->time_) {
+ double newtime = e->time_;
+ if (cal_clock_ > newtime) {
// may happen in RT scheduler
- cal_clock_ = e->time_;
+ cal_clock_ = newtime;
i = lastbucket_ = CALENDAR_HASH(cal_clock_);
} else
- i = CALENDAR_HASH(e->time_);
+ i = CALENDAR_HASH(newtime);
- Event *head = buckets_[i].list_;
- Event *before=0;
+ Bucket* current=(&buckets_[i]);
+ Event *head = current->list_;
+ Event *after=0;
if (!head) {
- buckets_[i].list_ = e;
+ current->list_ = e;
e->next_ = e->prev_ = e;
++stat_qsize_;
- ++buckets_[i].count_;
+ ++(current->count_);
} else {
- bool newhead;
- if (e->time_ >= head->prev_->time_) {
- // insert at the tail
- before = head;
- newhead = false;
+ insert_search_++;
+ if (newtime < head->time_) {
+ // e-> head -> ...
+ e->next_ = head;
+ e->prev_ = head->prev_;
+ e->prev_->next_ = e;
+ head->prev_ = e;
+ current->list_ = e;
+ ++stat_qsize_;
+ ++(current->count_);
} else {
- // insert event in time sorted order, FIFO for sim-time events
- for (before = head; e->time_ >= before->time_; before = before->next_)
- ;
- newhead = (before == head);
- }
-
- e->next_ = before;
- e->prev_ = before->prev_;
- before->prev_ = e;
- e->prev_->next_ = e;
- if (newhead) {
- buckets_[i].list_ = e;
- //assert(e->time_ <= e->next_->time_);
- }
- //assert(e->prev_ != e);
- if (e->prev_->time_ != e->time_) {
- // unique timing
- ++stat_qsize_;
- ++buckets_[i].count_;
+ for (after = head->prev_; newtime < after->time_; after = after->prev_) { insert_search_++; };
+ //...-> after -> e -> ...
+ e->next_ = after->next_;
+ e->prev_ = after;
+ e->next_->prev_ = e;
+ after->next_ = e;
+ if (after->time_ < newtime) {
+ //unique timing
+ ++stat_qsize_;
+ ++(current->count_);
+ }
}
}
++qsize_;
@@ -710,6 +720,7 @@
Event *e, *min_e = NULL;
#define CAL_DEQUEUE(x) \
do { \
+ head_search_++; \
if ((e = buckets_[i].list_) != NULL) { \
diff = e->time_ - cal_clock_; \
if (diff < diff##x##_) { \
@@ -769,6 +780,34 @@
if (!e)
return 0;
+ if (adjust_new_width_interval_) {
+ if (last_time_< 0) last_time_ = e->time_;
+ else
+ {
+ gap_num_ ++;
+ if (gap_num_ >= qsize_ ) {
+ double tt_gap_ = e->time_ - last_time_;
+ avg_gap_ = tt_gap_ / gap_num_;
+ gap_num_ = 0;
+ last_time_ = e->time_;
+ round_num_ ++;
+ if ((round_num_ > 20) &&
+ (( head_search_> (insert_search_<<1))
+ ||( insert_search_> (head_search_<<1)) ))
+ {
+ resize(nbuckets_, cal_clock_);
+ round_num_ = 0;
+ } else {
+ if (round_num_ > 100) {
+ round_num_ = 0;
+ head_search_ = 0;
+ insert_search_ = 0;
+ }
+ }
+ }
+ }
+ };
+
int l = lastbucket_;
// update stats and unlink
@@ -828,10 +867,32 @@
void
CalendarScheduler::resize(int newsize, double start)
{
- double bwidth = newwidth(newsize);
-
- if (newsize < 4)
- newsize = 4;
+ double bwidth;
+ if (newsize == nbuckets_) {
+ /* we resize for bwidth*/
+ if (head_search_) bwidth = head_search_; else bwidth = 1;
+ if (insert_search_) bwidth = bwidth / insert_search_;
+ bwidth = sqrt (bwidth) * width_;
+ if (bwidth < min_bin_width_) {
+ if (time_to_newwidth>0) {
+ time_to_newwidth --;
+ head_search_ = 0;
+ insert_search_ = 0;
+ round_num_ = 0;
+ return; //failed to adjust bwidth
+ } else {
+ // We have many (adjust_new_width_interval_) times failure in adjusting bwidth.
+ // should do a reshuffle with newwidth
+ bwidth = newwidth(newsize);
+ }
+ };
+ //snoopy queue calculation
+ } else {
+ /* we resize for size */
+ bwidth = newwidth(newsize);
+ if (newsize < 4)
+ newsize = 4;
+ }
Bucket *oldb = buckets_;
int oldn = nbuckets_;
@@ -856,13 +917,20 @@
} while (e != tail);
}
}
- delete [] oldb;
+ head_search_ = 0;
+ insert_search_ = 0;
+ round_num_ = 0;
+ delete [] oldb;
}
// take samples from the most populated bucket.
double
CalendarScheduler::newwidth(int newsize)
{
+ if (adjust_new_width_interval_) {
+ time_to_newwidth = adjust_new_width_interval_;
+ if (avg_gap_ > 0) return avg_gap_*4.0;
+ }
int i;
int max_bucket = 0; // index of the fullest bucket
for (i = 1; i < nbuckets_; ++i) {
diff -urN ns-2.31/common/scheduler.h ns-2.31-scheduler-doc/common/scheduler.h
--- ns-2.31/common/scheduler.h 2005-07-26 18:13:42.000000000 -0700
+++ ns-2.31-scheduler-doc/common/scheduler.h 2007-11-11 22:39:02.000000000 -0800
@@ -154,6 +154,16 @@
const Event* head();
protected:
+ double min_bin_width_; // minimum bin width for Calendar Queue
+ unsigned int adjust_new_width_interval_; // The interval (in unit of resize time) for adjustment of bin width. A zero value disables automatic bin width adjustment
+ unsigned time_to_newwidth; // how many time we failed to adjust the width based on snoopy-queue
+ long unsigned head_search_;
+ long unsigned insert_search_;
+ int round_num_;
+ long int gap_num_; //the number of gap samples in this window (in process of calculation)
+ double last_time_; //the departure time of first event in this window
+ double avg_gap_; //the average gap in last window (finished calculation)
+
double width_;
double diff0_, diff1_, diff2_; /* wrap-around checks */
diff -urN ns-2.31/doc/ns.bib ns-2.31-scheduler-doc/doc/ns.bib
--- ns-2.31/doc/ns.bib 2003-12-13 22:52:40.000000000 -0800
+++ ns-2.31-scheduler-doc/doc/ns.bib 2007-11-11 22:40:56.000000000 -0800
@@ -998,6 +998,25 @@
crossref = "McCaXX:wb"
}
+...@inproceedings{tan00snoopyqueue,
+ author = "Kah Leong Tan and Li-Jin Thng",
+ title = "SNOOPy Calendar Queue",
+ booktitle = "Proceedings of the 32nd conference on Winter simulation Orlando, Florida",
+ pages = {487-495},
+ year = 2000
+}
+
+...@inproceedings{weicao06nslinuxtcp,
+ author = "Xiaoliang (David) Wei and Pei Cao",
+ title = "{NS-2 TCP-Linux: an NS-2 TCP implementation with congestion control algorithms from Linux}",
+ booktitle = "{WNS2 '06: Proceeding from the 2006 workshop on ns-2: the IP network simulator}",
+ year = {2006},
+ pages = {9},
+ publisher = {ACM Press},
+ address = {New York, NY, USA},
+}
+
+
@string{usc = "University of Southern California"}
@string{usc-isi = "USC/Information Sciences Institute"}
@string{ieee-computer = "{IEEE} Computer"};
diff -urN ns-2.31/doc/sim.tex ns-2.31-scheduler-doc/doc/sim.tex
--- ns-2.31/doc/sim.tex 2003-04-03 12:36:52.000000000 -0800
+++ ns-2.31-scheduler-doc/doc/sim.tex 2007-11-11 22:39:02.000000000 -0800
@@ -151,6 +151,38 @@
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:
+\begin{itemize}
+ \item A heuristic improvement that changes the linear search direction
+in enqueue operations. The original implementation searches the events in
+a bucket in \emph{chronological order} to find the in-order spot for the event
+that is being inserted.
+The new implementation searches the bucket in \emph{reverse chronological order}
+because the event being inserted is usually later than most of the events that are
+already in the bucket.
+ \item A new bucket width estimation that uses the average interval of
+\emph{dequeued events} as the estimation of bucket width. It is stated in
+\cite{Brow88:Calendar} that the optimal bucket width should be the \emph{average inverval of all events in the future}.
+The original implementation uses the average interval of \emph{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.
+ \item 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 \cite{Tan00SNOOPyQueue}.
+In this implementation, there is one tcl parameter {\tt 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.
+\end{itemize}
+The details of these improvements are described in \cite{WeiCao06NSLinuxTCP}.
+
+The implementation of these three improvements was contributed by Xiaoliang (David) Wei at Caltech/NetLab.
+
\subsection{The Real-Time Scheduler}
\label{sec:rtsched}
diff -urN ns-2.31/tcl/lib/ns-default.tcl ns-2.31-scheduler-doc/tcl/lib/ns-default.tcl
--- ns-2.31/tcl/lib/ns-default.tcl 2006-10-22 22:33:16.000000000 -0700
+++ ns-2.31-scheduler-doc/tcl/lib/ns-default.tcl 2007-11-11 22:39:35.000000000 -0800
@@ -72,6 +72,9 @@
Scheduler/RealTime set maxslop_ 0.010; # max allowed slop b4 error (sec)
+Scheduler/Calendar set adjust_new_width_interval_ 10; # the interval (in unit of resize times) we recalculate bin width. 0 means disable dynamic adjustment
+Scheduler/Calendar set min_bin_width_ 1e-18; # the lower bound for the bin_width
+
#
# Queues and associated
#
_______________________________________________
click mailing list
[email protected]
https://amsterdam.lcs.mit.edu/mailman/listinfo/click
