Bug 799 - Interference helper is too slow
Interference helper is too slow
Status: RESOLVED FIXED
Product: ns-3
Classification: Unclassified
Component: wifi
ns-3-dev
All All
: P5 enhancement
Assigned To: Nicola Baldo
:
Depends on:
Blocks:
  Show dependency treegraph
 
Reported: 2010-01-28 07:43 EST by Kirill Andreev
Modified: 2010-08-02 11:22 EDT (History)
3 users (show)

See Also:


Attachments
Proposed fix (9.18 KB, patch)
2010-01-28 07:43 EST, Kirill Andreev
Details | Diff
Profile before fixes (91.40 KB, text/plain)
2010-01-28 07:44 EST, Kirill Andreev
Details
after fixes (89.60 KB, text/plain)
2010-01-28 07:45 EST, Kirill Andreev
Details
Unpack to scratch and run as "interference" (7.04 KB, application/octet-stream)
2010-06-30 07:29 EDT, Kirill Andreev
Details

Note You need to log in before you can comment on or make changes to this bug.
Description Kirill Andreev 2010-01-28 07:43:16 EST
I have looked through the code of InterferenceClass and have found, that NiChanges (interference profile) is calculated each time it needed on demand, and it consists of two parts:
1. Go through all events and form NiChanges.
2. Sort these NiChanges
3. Calculate ChunkSuccessRate

What I have done:
1. Keep sorted interference profile (NiChanges) instead of list of Events.
2. Using binary search when calculating noise-interference ratio.
3. PHY notifies about RX start/end, which is needed to cut interference profile.

We have tested a random static scenario of 500 nodes, each of them sends 100 1024-byte packets per seconds, and the density of the nodes is 10 nodes per square transmit range. The profiles and proposed fix are attached.
Comment 1 Kirill Andreev 2010-01-28 07:43:50 EST
Created attachment 738 [details]
Proposed fix
Comment 2 Kirill Andreev 2010-01-28 07:44:43 EST
Created attachment 739 [details]
Profile before fixes
Comment 3 Kirill Andreev 2010-01-28 07:45:25 EST
Created attachment 740 [details]
after fixes

All profiles are made on optimized build with --enable-static option
Comment 4 Kirill Andreev 2010-01-28 07:47:08 EST
Also it is worth to notice, that all regression tests are passed succesfully.
Comment 5 Nicola Baldo 2010-05-14 11:55:49 EDT
(In reply to comment #4)
> Also it is worth to notice, that all regression tests are passed succesfully.

I reviewed the proposed patch and it seems ok to me. The reduction in simulation time is very appealing. 

The only thing that makes me a little bit uncertain is that the fact that it passes unit and regression tests does not provide us with enough guarantees that the behavior is equivalent to the old code. This because there is no test suite covering the interference calculation, and the only regression test is wifi-wired-bridging, which might be a too simple scenario for this case.

On the other hand, I think that the multihop scenario with 500 nodes that you mentioned makes a much more meaningful regression test for the proposed patch. So, if you can confirm that for this scenario you get the same output before and after the application of the patch, then I agree with pushing the patch to ns-3-dev.
Comment 6 Kirill Andreev 2010-06-30 07:28:19 EDT
(In reply to comment #5)
> (In reply to comment #4)

> 
> On the other hand, I think that the multihop scenario with 500 nodes that you
> mentioned makes a much more meaningful regression test for the proposed patch.
> So, if you can confirm that for this scenario you get the same output before
> and after the application of the patch, then I agree with pushing the patch to
> ns-3-dev.
I have made a scenario with 200 nodes and density equal to 10 nodes per square RX-range. Every node generates broadcast traffic, and every station has a full MAC-queue, which is good for interference test. There are no difference in PCAP trace files.
Comment 7 Kirill Andreev 2010-06-30 07:29:25 EDT
Created attachment 931 [details]
Unpack to scratch and run as "interference"

Proposed test scenario.
Comment 8 Kirill Andreev 2010-06-30 07:35:27 EDT
This test scenario prints the following:
# node count, density, PDR (received / total sent), time scaling (real/model time)
#not patched:
200     10      0.0153717       74.5482
#patched:
200     10      0.0153717       55.9163

This is a debug version of one of the latest ns-3-dev.

Also it is worth to notice, that when node density is high -- the first top function in a profile is DcfManager's and timing relation calculations. When the density is low -- interference calculation affects performance much stronger.
Comment 9 Tom Henderson 2010-08-01 17:49:56 EDT
Assigning to Nicola to review and possibly commit
Comment 10 Nicola Baldo 2010-08-02 11:22:21 EDT
Kirill, thank you very much for doing this evaluation. 
I just pushed your patch to ns-3-dev
changeset:   6474:0894b2a245e9