[Home]CallGen

HomePage | RecentChanges | Preferences

Call Generation

There are two things about a call - The Call and the time to the next one.

A call generator needs to generate calls and space them with a time called the Inter Arrival Time.

CallRate is the calls per second, which is the long term average call rate.

A very Basic Call Generator - Leaky bucket using callBucket

This is a leaky bucket call generator. Add a decimal number of callsPerTick to the call bucket. When the bucket is too full end calls to empty the call bucket.

 onTimerTick( ) {

  if( Poission ){
    callsRequiredThisTick = PoissonDist( callsPerSecond/ticksPerSecond, rand() );  
  } else {
    // callsThisTick can be decimal.
    callsRequiredThisTick = callsPerSecond / tickRate;
  }

   // Integrate up the callsBucket
   callsBucket += callsRequiredThisTick;  
   while( callsBucket > 1.0 ){ 
     // Oportunity to send call, pick source destination and call type.
     callOpportunity();
     callsBucket -= 1.0; 
   }
 }

A very Basic Call Generator - Leaky bucket using timeBucket

This is a leaky bucket call generator.

 onTimerTick( ) {

   // nowTime is simulated and as precise as required. 
   // This is run once per time slice.
   // Normally this would go as fast at the hardware allows.

   // Move simulated time on by timerTick
   // nowTime is relative to real time
   nowTime = nowTime - timerTickTime;

   calls=0
   if ( nowTime > 0.0 ) { 
     // No calls needed
   } else {
     // Catch up simulated time with real time
     while ( nowTime  < 0.0 ){        
       //# Catch up with calls as simulated time is behind real time
       //# generate a time interval modulated by Neg Exp distribution
       // interArrivalTime = -Math.log(1-Math.random( ))  / CallsPerSecond;
       interArrivalTime = calculateNextInterArrivalTime( CallsPerSecond );
       sendCall();  // Call Opportunity - pick source,destination and call type 
       nowTime = nowTime + interArrivalTime;
     }
   }
 }

A very Basic Call Generator - Ideal

 while ( true ) }
   callOpportunity();
   waitInterArrivalTime()
 }

callOpportunity()

Every time around the loop there is a call opportunity to make a call. The function picks where the call is coming from, where it is going to, and any other characteristics. Tables could be used to supply these details or they can be randomly picked.

( see Chapter 4 Telecommincations Switching Principles, M T Hill,ISBN 04 04 621029 6 ) http://en.wikipedia.org/wiki/Exponential_distribution

Inter Arrival Time

The time between call choosen depends on the purpose of the call generator.

Sometime a fixed interval is required, sometimes a random one.

fixed Inter Arrival Time

A fixed interval is useful for testing the function of the system under test.

 Inter Arrival Time = 1 / CallRate

random Inter Arrival Time

( See Chapter 4 Telecommincations Switching Principles, M T HIll,ISBN 04 04 621029 6 )

A random interval represents independent callers. Often random call intervals uses the Negative Exponetial Distribution. This is used to model callers who make calls with no knowledge of other callers.

 InterArrivalTime = - log( 1-rand() ) / CallRate

Working out -log( 1-rand() ) is cpu intensive so it is a good idea to pre calculate these and store them in a table.

  for ( i = 0; i < tableMax ; i++ ){
    interArrivalTimeA[ i ] = - log( 1-rand() )
  }

  // step through random sequence in a repeated way - not very good.
  interArrivalTime = interArrivalTimeA[ i++ % tableMax )]

  // step through random sequence in a random way .
  interArrivalTime = interArrivalTimeA[ int( rand() * tableMax )]

or work out a table with the distribution stored in it.

  for ( i = 0; i < tableMax ; i++ ){
    interArrivalTimeA[ i ] = - log( ( 1.0*i / tableMax ) )
  }

  interArrivalTime = interArrivalTimeA[ int( rand() * tableMax )]

Notes on rand()

rand() returns a random number between 0 and 1 with a flat distribution.

average( rand(),rand(),... ) = 0.5 if the list is large enough.

sort( rand(),rand(),...) should produce a graph with equal distribution. This should be a straight line.

Let us consider the Inter Arrival Times again

Here is a list of ways of working Inter Arrival Times with different distributions.

 Inter Arrival Time = 1 / CallRate

 Inter Arrival Time = 2 * rand() / CallRate

 InterArrivalTime = - log( 1-rand() ) / CallRate

 InterArrivalTime = interArrivalTimeA[ rand()*tableMax ]  / CallRate

or generically

 InterArrivalTime = distA[]  / CallRate

The values -log( 1-rand()) need to sum to 1.

The values of distA[] need to sum to 1.

If you put -log(1- rand() ) into a spread sheet and work out values, how repeatable is the sum and average?

How many values in distA[] do you need to work out so that the sum is the same to within 1% ?

If we have n samples, and we add another sample, will the avergae change by more than say +/-1%:

  99% <  new average /  last average  < 101%

or

  99% <  average( value[0]..value[n+1] ) /  average( value[0]..value[ n ] )  < 101%

If all the values in distA[] = 1 the you need 1 value.

If all the values in distA[] = 1-rand() the you need 200 values, as 0 < rand() < 1 and average is 0.5.

If all the values in distA[] = -log ( 1-rand() ) the you need ? values, as 0 < -log ( 1-rand() ) < ~3

Note use Natural Logs, not log10. In Excel use -log( A1, exp(1) )

Lets explore working out 10 values, then randomly picking from the table.

 i	-LOG( 1-i )
 - -    - - - - - - 
 0	0
 0.1	0.105360516
 0.2	0.223143551
 0.3	0.356674944
 0.4	0.510825624
 0.5	0.693147181
 0.6	0.916290732
 0.7	1.203972804
 0.8	1.609437912
 0.9	2.302585093
 - -    - - - - - -
 0.45	0.792143836 Averages

With 10 values incremented by 0.1 -ln( 1- 10*0.1) ) = infinity With 9 values incremented by 0.1 -ln( 1- 9*0.1) ) = 2.302585093

Randomly picking from these 9 values would result in a call rate 79% below the required call rate.

We could add an off set, 0.05773 seems to make the average = 1

 i  	        -LOG(1-i)
 - - - -        - - - - - - 
 0.05773	0.059463421
 0.15773	0.171654651
 0.25773	0.298042221
 0.35773	0.442746503
 0.45773	0.611991247
 0.55773	0.815834724
 0.65773	1.07215538
 0.75773	1.417702472
 0.85773	1.950028618
 0.95773	3.163677664
 - - - -         - - - - - - 
 0.50773	1.00032969 Averages

If all the values in distA[] = -log ( 1-9*0.1 ) the you need about 3.16 * 100 values, as -log ( 1-9*0.1 ).

Negative Exponential

 InterArrivalTime = - log( 1-rand() ) / CallRate

This is a negative Exponential distribution.

If you measure the interarrival times, and work out and plot:

 -exp( InterArrivalTime * CallRate ) = 1 - rand().

You should get an equal distribution of probability.

If you sort the values -exp( InterArrivalTime * CallRate ) you should get a straight line.

What is the shape of the Poisson distribution

Wikipedia has an entry about the Poisson distribution. [1]

See also: [2] and [3]

  f(k,x) =  x^k / k!    * exp( -x )

where

  A in call Arrival rate 
  k is descrete number of calls starting in Interval.

also

  A can be Erlangs - Propotion of circuit occupancy. 
  k can be descrete number of calls in progress.

or as exp ( -A ) = 1 / exp( A )

  f(k,A) =  A^k / k!    / exp( A )

The formulae below sums to exp( A )

  //  for( A=1; A < Infinity ; A++ ){ // error

  for( k=1; k < Infinity ; k++ ){

    sum += sum A^k / k! 
  }

It also tends to blow up as A^k and k! are very big numbers when k is quite a small number.

The probability that k circuits are in use is:

 P(k)=A^k/k!*exp(-A) where A is erlangs of traffic.

So use A^k/k! = (A/k)*(A/(k-1)*..*(A/(1)

 for ( cnt = 1; cnt < maxCircuits ; cnt ++ ){
   t	= A / ( cnt )
   Pk	= t*Pk
   sumPk 	= sumPk+Pk
 }

Distributions

The Poisson Distribution is the decrete expression of:

  exp( X ) / exp( -x )

  where exp( X ) = SumForN=1ToInfinity( 1+ x^n/n!... )

What about measuring the Poisson distribution for say seconds and 1/10th Seconds.

These should be linked, and if a set of points is pure Poission, then it should fit for both seconds and 1/10th Seconds.

Call generation using A distribution

Start Timer with constant timer Tick.

 function PossionDist( A, rand() ) {
   // for a given traffic rate and probability work out how many calls to start.
   return numberOfCallsToStart
 }

 OnTimerTick() {
   numberOfCallsToStart = PossionDist( A, rand() )
   while( numberOfCallsToStart > 0 ){
     sendCall()
     numberOfCallsToStart --
   } 
 }

If the Timer tick is as fast as possible, this is the best you can get anyway. The calls will be bursty.

If the timer tick could go faster, then this is not the best you can get.


HomePage | RecentChanges | Preferences
This page is read-only | View other revisions
Last edited September 23, 2014 8:22 pm by dougrice.plus.com
Search:
dougFooter