[Ns-developers] First Stab at Validation and Verification

Tue Apr 21 09:20:21 PDT 2009

Hi George,

> Some random thoughts about this.
> 
> You refer to RFC793 as the TCP specification; while this is 
> true, the  
> ns-3 model
> is based on RFC2581.

That was just intended to be an example of how some version of TCP might
operate according to a "spec"; and not according to a real-world physical
process of some kind.  Thanks for the info, though.

> You discuss observing the real-world implementation of the artifact  
> being modeled
> as the "baseline" or "true" behavior.  There is no TCP 
> implementation  
> that I am
> aware of that follows the RFC precisely.

The point is that the TCP has some defined behavior we are trying to
simulate.  This is the abstract model.  The abstract model might be RFC 793
with Craig's strange changes.  It might be RFC2581 with George's additions.
It might be RFC2581.  This defines the behavior and is the specification.
The goal then becomes to ensure that the implementation behaves according to
abstract model -- i.e., that I implemented RFC2581 and "George's additions"
correctly.

>  For example Linux  
> implementations use a
> non-standard (no RFC) implementation called "BIC TCP", and later  
> "CUBIC TCP".
> So it's not clear how the discussion here can reasonably be 
> applied to  
> the ns3 TCP.

Somewhere we have to decide what ns3 TCP is and what it should do.  Then we
can write verification tests to make sure that the simulation model actual
does what we advertise it to do.  If that is RFC 2581, then we need to write
verification tests to make sure that ns-3 TCP follows RFC 2581.

> In our case, the validation is whether or not our model does what is  
> specified in
> RFC 2581.

Exactly.

> Further, there is no randomness at all in TCP, either as implemented  
> in ns3 or in
> actual implementations. GIven the same set of stimuli, the TCP  
> implementations
> will always behave in exactly the same way.  The only non- 
> deterministic behavior
> in implementations of TCP is in the timeout values, which will only  
> occur on scheduler
> interrupts, and not exactly to the microsecond specified.  So the  
> discussion about random
> variables, while very nice and correct, is not precisely applicable  
> here.  

I tried to explain this, but I guess I didn't do a very good job.  A
software process which is implemented according to some specification, is
not based on physical processes and may not have random variation.  Thus
verification is the real process you would use to make sure that TCP works
according to its spec.  You make sure that the implementation accurately
reflects the abstract model which is the spec.  This is what I called
verification in the document.  I'm not suggesting that there are random
processes in TCP.  That's the distinction I'm trying to draw using the term
verification instead of validation.

> There is randomness
> of course in things that happen outside of TCP (for example packet  
> losses in a queue that
> is overloaded by a large HTTP transfer).

If a model is going to simulate some randomness or physical process then you
need to deal with the randomness.  I called this validation -- and I have in
mind things like wireless transmission range.  If a model is going to
implement a specification without random processes, you need to do a
deterministic tests.  I called this verification and had in mind TCP.

One issue here is that some people seem to want to remove this distinction.
The distinction is important to other people.

> Do you think it might make sense to use a different baseline for the  
> discussion, perhaps
> the path loss models or something else with true randomness?

Actually, TCP is in the document because it doesn't deal with randomness and
illustrates a distinction I wanted to make.  Hopefully, the distinction I'm
making between validation and verification, stochastic and deterministic
processes becomes clear, even if it doesn't manifest in a directory
structure in the final product.  Eventually a wifi test suite might include
tests to validate physical processes that definitely will be based on random
variables (validation of transmission range) and might also have spec-based
tests (verification: if in state X and receive packet type Y then jump to
state S).  We don't want to split up the wifi tests into two different
suites I think.

> 
> George
> 
> --------------------------------------------------
> George Riley
> Associate Professor
> Georgia Tech
> Electrical and Computer Engineering
> riley at ece.gatech.edu
> 404-894-4767
> Klaus Advanced Computing Building
> Room 3360
> 266 Ferst Drive
> Atlanta, Georgia 30332-0765
> 
> ECE4110 Web page:
> http://users.ece.gatech.edu/~riley/ece4110/
> 
> ECE4112 Web page:
> http://users.ece.gatech.edu/~riley/ece4112/
> 
> 
> 
> 
> 
> 
> 
> 
> 
> On Apr 17, 2009, at 7:10 PM, <craigdo at ee.washington.edu> 
> <craigdo at ee.washington.edu 
>  > wrote:
> 
> > Hi All,
> >
> > Some of you may have noticed that I've been pondering what to do  
> > about validation and verification of ns-3 models.  I've played
> > around a bit and have an example put together that does some  
> > statistical validation of a subset of our random number generators.
> >
> > Some folks around here have expressed an interest in getting this  
> > cleaned up and checked in fairly quickly.  So even though this is
> > not even close to fully baked I thought I'd socialize what 
> I have.   
> > Feel free to comment or tell me I'm on crack, as another one of
> > the developers is fond of saying.
> >
> > The high-level idea is to sharpen our models for what we consider  
> > system/integration/regression tests.  Right now we have regression
> > tests that are basically example programs we have pressed into  
> > double duty.  We want to move toward purpose-build 
> verification tests
> > and away from the trace-file-based example program hacks we have  
> > today.  We also want to add some form of validation framework where
> > people can demonstrate that their models are connected with some  
> > kind of reality.  As a byproduct of this validation and
> > verification test effort, we would like to see something 
> that can be  
> > used as a regression suite and as a side-effect also generate
> > something that can be used on a validation and verification 
> website  
> > (pretty pictures).
> >
> > I've put together some words on the wiki.  They're kind of  
> > incomplete ramblings and thoughts right now, but you can probably  
> > get a
> > decent flavor of where I'm going (don't hold me to anything):
> >
> > http://www.nsnam.org/wiki/index.php/VerificationValidationAndTesting
> >
> > As it stands, the two areas of verification and validation 
> are quite  
> > separate, but they'll most likely get folded together as things
> > develop.
> >
> > I have random number generator tests built that do statistical  
> > validation, generate pretty plots and can be run as 
> regression tests.
> > I'll eventually integrate them into waf, but they are stand-alone  
> > right now.  As an example of a validation wiki, I put together the
> > following:
> >
> > http://www.nsnam.org/wiki/index.php/StochasticModelValidation
> >
> > It's not intended to be complete and thorough (although the chi  
> > square tests are real) just a demonstration of where we are headed.
> >
> > The code can be found at:
> >
> > http://code.nsnam.org/craigdo/ns-3-valver
> >
> > with the rng tests in validation/rng and the beginnings of a TCP  
> > verification test in verification/tcp (not much there yet).
> >
> > If you have any plans or ideas please don't hesitate to let 
> me know  
> > about them.  If you are doing validation tests on your own, I'd
> > love to figure out how to make it easy to integrate them.
> >
> > Regards,
> >
> > -- Craig
> >
> 
> 