Generator of Self-Similar Traffic

(version 3)

Model
List of Files
Overview and Quick Start
Example: Estimating Hurst parameter using var-time log-log plot
Q & A


  

Model

[ Top ]
To generate self-similar traffic, we used the method described in M. S. Taqqu, W. Willinger, and R. Sherman, "Proof of a fundamental result in self-similar traffic modeling," ACM/SIGCOMM Computer Communication Review, vol. 27, pp. 5-23, 1997. In this method, the resulting self-similar traffic is obtained by aggregating multiple sub-streams, each consisting of alternating Pareto-distributed on/off periods.
Pareto distribution is a heavy-tailed distribution with the probability-density function f(x) = αbα/xα+1, x ≥ b, where α is a shape parameter, and b is a location parameter. Pareto distribution with 1 < α < 2 has a finite mean and an infinite variance. To generate Pareto-distributed values, the following formula may be used: XPareto = b/[U1/α], where U is a uniform random variable (0 ≤ U ≤ 1).
In versions 1 and 2 of traffic generator, each sub-stream generated packets of constant size. Thus, to generate Ethernet packets of all possible sizes from 64 to 1518 bytes, at least 1455 sub-streams where necessary. In this version, sub-streams (objects of class Stream) are responsible for generating the burst sizes only. The packets to fill those bursts are generated using externally-supplied callback function. There are three classes derived from the abstract class Stream:
StreamPareto Generates on/off periods with lengths following Pareto distribution.
StreamExpon Generates on/off periods with lengths following negative exponential distribution.
StreamCBR Generates on/off periods with constant lengths.
The load generated by one sub-stream is measured as λ=E[on]/(E[on]+E[off]), where E[on] and E[off] are expected lengths of on and off periods respectively. All sub-streams generate equal loads. The expected size of on period (E[on]) is specified externally. The expected size of off period (E[off]) is calculated based on the target load λ: E[off]=E[on]*(1/λ - 1). The total load generated by the traffic generator is equal the sum of loads generated by all sub-streams: Λ = ∑iλi.

List of Files

[ Top ]
_types.h Contains general type definitions and macros. (Refer to Discrete Event Simulation Library.)
MersenneTwister.h Mersenne Twister random number generator is designed by Makoto Matsumoto and Takuji Nishimura. This file is Mersenne Twister RNG implemented as C++ class by Rick Wagner.
_rand_MT.h Contains routines for generating random values. Most of these are just wrapper functions for Mersenne Twister class.
avltree.h Contains class declarations for AVL tree structure. AVL tree structure is discovered by Adelson-Velsky and Landis (G.M. Adelson-Velskii and E.M. Landis, "An algorithm for the organization of information," Soviet Math. Dokl., 3:1259--1262, 1962). AVL tree is used here to store sub-streams sorted in order of burst arrival time and to add and retrieve elements in O(logN) time.
trf_gen_v3.h Declares the following classes used to generate synthetic traffic: 
     class Packet
     class Stream
     class StreamPareto
     class StreamExpon
     class StreamCBR
 
     class PacketGenerator
     class PacketGeneratorDist
     class PacketGeneratorDist


Overview and Quick Start

 [ Top ]
The traffic generator produces not a complete Ethernet packet, but rather a trace describing packet size, arrival time, and the identification of the source which produced this packet. The packet trace is described by the following structure: 
    struct Packet
    {
        source_id_t  SourceId;
        pckt_size_t  PcktSize;
        pause_size_t Interval;
    };
source_id_t SourceId A 16-bit source identifier.
pckt_size_t PcktSize 16-bit packet size (in bytes).
pause_size_t Interval 32-bit interval (in bytes) between the arrival of the previous packet and arrival of the current packet. The arrival time corresponds to the reception of the last bit of a packet. For example, if PcktSize = 100 and Interval = 250, then the inter-packet gap is 250-100 = 150 bytes.
If it is desired for generator to produce a structure resembling an Ethernet frame, another class should be derived from class PacketGenerator to do so. The traffic generator can be instantiated in several different ways. The most generic constuction is the following: 
    PacketGenerator( source_id_t     source_id,
                     pckt_size_t     inter_packet_gap, 
                     float           mean_burst,
                     PF_STREAM_CTOR  pf_strm,
                     PF_PCKT_SIZE    pf_size,
                     int16s          pool_size,
                     load_t          load )
source_id_t source_id A 16-bit identifier by which all packets generated by given source may be identified.
pckt_size_t inter_packet_gap Size of inter-packet gap. This parameter includes everything that is located between last bit of FCS and the first bit of DA of the next packet. In Ethernet, this should include 12-byte IFG and 8-byte preamble.
float mean_burst Average burst length of an individual sub-stream. The average burst length of the aggregated stream will be larger, because during aggregation, multiple bursts join together.
PF_STREAM_CTOR pf_strm Pointer to a function that creates sub-streams. Here, a caller has a choice of creating StreamPareto, StreamExpon, or StreamCBR objects, or a combination of those. Examples of such callback functions: 
GEN::Stream* CreateStream( GEN::load_t load, 
                           float mean_burst )
{
    return new GEN::StreamPareto( load, 
                                  mean_burst, 
                                  SHAPE_PARETO );
}
or 
GEN::Stream* CreateStream( GEN::load_t load, 
                           float mean_burst )
{
    return new GEN::StreamExpon( load, 
                                 mean_burst );
}
PF_PCKT_SIZE pf_size Pointer to a function that returns packet sizes. Here, a caller can specify the desired distribution for packet sizes.
int16s pool_size Number of sub-stream to aggregate into a final stream.
load_t load Target load of the aggregated stream (0 - 1.0).
The following example illustrates how traffic generator can be instantiated and packets generated. 
    #include 
    #include "trf_gen_v3.h"

    using namespace std;

    #define MIN_IFG         20    /* minimum inter-frame gap */
    #define MIN_PACKET_SIZE 64    /* minimum packet size */
    #define MAX_PACKET_SIZE 1518  /* maximum packet size */

    #define SHAPE_PARETO    1.4F  /* alpha parameter for 
                                     pareto distribution */

    #define MEAN_BURST_SIZE 4000  /* mean burst size of an
                                     individual sub-stream */

    #define TARGET_LOAD     0.5F  /* load to be produced by 
                                     traffic generator */

    #define SUB_STREAMS     256   /* number of sub-streams 
                                     to aggregate */


    /////////////////////////////////////////////////////////////
    // Callback function that creates new sub-stream object
    /////////////////////////////////////////////////////////////
    GEN::Stream* CreateStream( GEN::load_t load, float mean_burst )
    {
        return new GEN::StreamPareto( load, 
                                      mean_burst, 
                                      SHAPE_PARETO );
    }

    /////////////////////////////////////////////////////////////
    // Callback function that generates packet sizes 
    // with a desired distribution
    /////////////////////////////////////////////////////////////
    GEN::pckt_size_t PacketSize( void )
    {
        // in this example, use uniformly distributed packet 
        // sizes between 64 and 1518 bytes
        return (GEN::pckt_size_t)(_uniform_int_(MIN_PACKET_SIZE, 
                                                MAX_PACKET_SIZE));
    }

    /////////////////////////////////////////////////////////////
    // 
    /////////////////////////////////////////////////////////////
    int main(void)
    {
        GEN::Packet pckt;

        // instantiate traffic generator
        GEN::PacketGenerator SRC( 0,
                                  MIN_IFG, 
                                  MEAN_BURST_SIZE,
                                  CreateStream,
                                  PacketSize,
                                  SUB_STREAMS,
                                  TARGET_LOAD );     

        // output 1 mln traces
        for( int32s trace = 0; trace < 1000000; trace++ )
        {
            pckt = SRC.GetNextPacket();

            cout << trace         << ";" 
                 << pckt.PcktSize << ";" 
                 << pckt.Interval << endl;
        }

        return 0;
    }
If probabilities or frequencies of packet sizes are known, say, from an empirical observation, the template class PacketGeneratorDist may be used: 
    template< class T, int32s N, T (*PF_FREQUENCY)(int32s) > 
    class PacketGeneratorDist
T Type of elements representing probabilities or frequencies (counts). To improve the performance it is desirable to make T an integer.
N Number of distinct elements in the entire sample space. To generate
T (*PF_FREQUENCY)(int32s) A pointer to callback function that returns probability or frequency of an element with index i.
The class PacketGeneratorDist declares the following constructor: 
    PacketGeneratorDist( source_id_t     source_id, 
                         pckt_size_t     inter_packet_gap, 
                         float           mean_burst,
                         PF_STREAM_CTOR  pf_strm,
                         int16s          pool_size,
                         load_t          load )
The descriptions of all the arguments are the same as in the constructor of class PacketGenerator above. The following code illustrates how to generate packets with a generic distribution. This example uses upstream packet size distribution measured at a CATV head-end. 
    #include 
    #include "trf_gen_v3.h"
    #include "broadcom_pdf.h"

    using namespace std;

    #define MIN_IFG         20    /* minimum inter-frame gap */
    #define MIN_PACKET_SIZE 64    /* minimum packet size */
    #define MAX_PACKET_SIZE 1518  /* maximum packet size */

    #define SHAPE_PARAMETER 1.4F  /* alpha parameter for 
                                     pareto distribution */

    #define MEAN_BURST_SIZE 4000  /* mean burst size of an
                                     individual sub-stream */

    #define TARGET_LOAD     0.5F  /* load to be produced by 
                                     traffic generator */

    #define SUB_STREAMS     256   /* number of sub-streams 
                                     to aggregate */


    /////////////////////////////////////////////////////////////
    // Callback function that creates new sub-stream object
    /////////////////////////////////////////////////////////////
    GEN::Stream* CreateStream( GEN::load_t load, float mean_burst )
    {
        return new GEN::StreamPareto( load, 
                                      mean_burst, 
                                      SHAPE_PARAMETER );
    }

    /////////////////////////////////////////////////////////////
    // Callback function that returns (normalized) frequency of 
    // packets of size n
    /////////////////////////////////////////////////////////////
    int32s broadcom_frequency( int32s n )
    {
        return round( upstrm_size_pdf[n] * 0x7FFFFFFFL );
    }

    /////////////////////////////////////////////////////////////
    // 
    /////////////////////////////////////////////////////////////
    int main(void)
    {
        GEN::Packet pckt;

        // instantiate traffic generator
        GEN::PacketGeneratorDist< int32s, 
                                  MAX_PACKET_SIZE + 1, 
                                  broadcom_frequency > 
                          
                            SRC ( 0, 
                                  MIN_IFG, 
                                  MEAN_BURST_SIZE,
                                  CreateStream, 
                                  SUB_STREAMS, 
                                  TARGET_LOAD );

        // output 1 mln traces
        for( int32s trace = 0; trace < 1000000; trace++ )
        {
            pckt = SRC.GetNextPacket();

            cout << trace         << ";" 
                 << pckt.PcktSize << ";" 
                 << pckt.Interval << endl;
        }

        return 0;
    }
[ Top ]
 
This page was last modified on Saturday, 13-Dec-2014 19:05:36 MST.
For all inquiries send e-mail to info@glenkramer.com