#1 speed up event scheduler

open
nobody
ns-2 (14)
5
2005-12-30
2005-12-30
Tom Henderson
No

From: "Xiaoliang (David) Wei" <weixl@caltech.edu>
Date: October 13, 2005 9:38:16 AM GMT+02:00
To: <end2end-interest@postel.org>
Subject: [e2e] A patch that speeds up the NS-2 simulation

I guess this may help some colleagues in e2e,
especially those who are using NS-2 to simulate high
speed long distance network. If you find that your
NS-2 simulation runs on a 200-second simulation for a
day, the patch may probably help. You can download the
patch and see detailed explanation from:

http://www.cs.caltech.edu/~weixl/technical/ns2patch/ns2patch.htm

In the patch, I only changed the event scheduler of
NS2. So, the patched NS-2 will give the same results
as the original one. Depending on different scenarios,
the patched NS2 runs faster in most the cases I
tested, sometimes 50 times faster. If you find any
problem, please let me know.:)

A little bit more details (See the link above for more
details):

The original NS2 scheduler is implemented by
Calendar Queue. Its performance is expected to be O(1)
on average but the real results may be much longer,
especially when the events are not evenly distributed
and the bucket-width is not "correct" for the event
distribution. This is unfortunately more common in
simulations of high speed long distance network, where
the events are clustered in bursts.

I add three changes:

1. Use the gaps between dequeued events, instead the
gaps between the events in the most crowded bucket, to
estimate the bucket-width.

2. Apply a scheme similar to SNOOPy Calendar Queue that
tunes the bucket-width dynamically

3. Inside a bucket, I changed the search of event
insertion point from forward-search to backward-search.

-David

Xiaoliang (David) Wei Graduate Student in
CS@Caltech
http://www.davidwei.org
====================================================

Discussion