Bug 2846 - Interference models produce negative interference because of roundoff.
Interference models produce negative interference because of roundoff.
Status: RESOLVED DUPLICATE of bug 2845
Product: ns-3
Classification: Unclassified
Component: wifi
ns-3-dev
All All
: P3 normal
Assigned To: sebastien.deronne
:
Depends on:
Blocks:
  Show dependency treegraph
 
Reported: 2018-01-08 19:23 EST by Peter Barnes
Modified: 2018-01-10 16:17 EST (History)
1 user (show)

See Also:


Attachments

Note You need to log in before you can comment on or make changes to this bug.
Description Peter Barnes 2018-01-08 19:23:48 EST
The Wifi InterferenceHelper, as well as the Spectrum model SpectrumInterference class, are vulnerable to roundoff, resulting in negative computed interference (Ix), and hence negative SINR, which triggers an assert.

There have been two recent reports on the users' list:
https://groups.google.com/forum/#!topic/ns-3-users/abB_fM7C4rs
https://groups.google.com/forum/#!topic/ns-3-users/t6L35V_eZ8M
It's not clear either user has a repeatable example :( 

The second thread traces it back to wifi/model/interference-helper.cc:243 InterferenceHelper::CalculateSnr().

It looks like Ix sources are being tracked in a list of deltas, stored as NiChange events.  Look at 220:AppendEvent() for example:

- it adds (or modifies, lines 230-231) a new NiChange:
235:  NiChange (event->GetStartTime (), event->GetRxPowerW (), event)

- it adds a decrement:
237:  NiChange (event->GetEndTime (), -event->GetRxPowerW (), event)

The callers of CalculateSnr() walk the list of NiChange, adding in the delta power stored in each NiChange, to compute the total Ix power.  

When the relevant span includes both ends (start and end) of an Ix event, the design of storing (startTime, +power) then (endTime, -power) leads to adding and subtracting the same value.  In between these addition and subtraction the absolute value of Ix being calculated can have changed significantly larger, leading to roundoff errors in the subtraction, ultimately resulting in negative values.

A quick look suggests SpectrumInterference has the same approach.

To prove that this is the problem a couple of things might help:

1.  Instrument to record the high water mark as the Ix is being computed. This should be significantly larger than the final (negative) Ix value, which lends credence to loss of precision hypothesis.

2.  Check the end result Ix value, if it's negative set it to m_firstPower (it's initial value).  This should be a simple two line patch which either user could test for us.

#2 is just a hack, not the real fix.  We shouldn't settle for this hack a. because it could mask other more serious issues in the future, and b. because there's a better fix.

The real fix is to refactor NiChange from (time, delta) to (time, power).  To add a new Ix record, 

1.  add two NiChange events for start time and and end time of the new Ix source.

2.  For the end time NiChange, set the power to the power of the previous entry (in time).  

3.  For all events in the interval [start, end) (including the new start event, but not the new end event) set power to the power of the entry before the new event.

Step 3 has the effect of adding the new Ix power to the old value, starting at the start time.  Step 2 has the effect of restoring the power to what it would have been, in the absence of the new Ix source, at the end time.  Notice that this algorithm *does not* require any subtraction, only addition.
Comment 1 sebastien.deronne 2018-01-10 16:17:34 EST
You opened 2 bugs for the same issue.

*** This bug has been marked as a duplicate of bug 2845 ***