[e2e] A patch that speeds up the NS-2 simulation

[Xiaoliang (David) Wei]

     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 at Caltech
http://www.davidwei.org
====================================================