Bug 799

Summary:	Interference helper is too slow
Product:	ns-3	Reporter:	Kirill Andreev <andreev>
Component:	wifi	Assignee:	Nicola Baldo <nicola>
Status:	RESOLVED FIXED
Severity:	enhancement	CC:	andreev, ns-bugs, tomh
Priority:	P5
Version:	ns-3-dev
Hardware:	All
OS:	All
Attachments:	Proposed fix Profile before fixes after fixes Unpack to scratch and run as "interference"

Description Kirill Andreev 2010-01-28 07:43:16 UTC

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 UTC

Created attachment 738 [details]
Proposed fix

Comment 2 Kirill Andreev 2010-01-28 07:44:43 UTC

Created attachment 739 [details]
Profile before fixes

Comment 3 Kirill Andreev 2010-01-28 07:45:25 UTC

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 UTC

Also it is worth to notice, that all regression tests are passed succesfully.

Comment 5 Nicola Baldo 2010-05-14 11:55:49 UTC

(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 UTC

(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 UTC

Created attachment 931 [details]
Unpack to scratch and run as "interference"

Proposed test scenario.

Comment 8 Kirill Andreev 2010-06-30 07:35:27 UTC

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 UTC

Assigning to Nicola to review and possibly commit

Comment 10 Nicola Baldo 2010-08-02 11:22:21 UTC

Kirill, thank you very much for doing this evaluation. 
I just pushed your patch to ns-3-dev
changeset:   6474:0894b2a245e9