node2.h

一个linux下的各种组播路由算法编程

/*
 * Copyright (c) 1995 Center for Advanced Computing and Communications (CACC),
 * North Carolina State University at Raleigh.
 * All rights reserved.
 * Permission to use, copy, modify, and distribute this software and its
 * documentation for any purpose and without fee is hereby granted, provided
 * that the above copyright notice appear in all copies and that both that
 * copyright notice and this permission notice appear in supporting
 * documentation.  The CACC makes no representations about the
 * suitability of this software for any purpose.  It is provided "as is"
 * without express or implied warranty.
 */


/*****************************************************************************
***                      Author: Hussein F. Salama                         ***
***                       Date: September 9, 1994                          ***
***                            File: node2.h                               ***
***         A library defining node, routing tables, sources,              ***
***         adajacency lists and networks management operations            *** 
*****************************************************************************/

#ifndef NODE2_H
#define NODE2_H

#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <float.h>
#include <limits.h>
//#include <string.h>

#define False 0
#define True  1

//#define RAND_REF  (INT_MAX + 0.1)   //For Sun Sparc stations and DEC stations
#define RAND_REF (RAND_MAX + 0.1)     //For IBM RS6000's and Solaris

#define FIFO     1
#define PRIORITY 2
#define QTYPE FIFO


//The bit loss prob. due to buffer overflow

#define epsilon 1e-6

//The upper bound on delay
//I made the variable in the class TheNodeList
//#define DELAYBOUND   .025    //25 msecs
//#define DELAYSTEP    .002    //2 msec for use with Polyzos algorithm


//Reasons for rejecting multicast sessions

#define LINKSAT      DBL_MAX
#define DBVIOL       (DBL_MAX / 2.0)
#define SATORDB      (DBL_MAX / 3.0)
#define NOGROUP      (DBL_MAX / 4.0)
#define CONFLICT     (DBL_MAX / 5.0)
#define FAILURE      (DBL_MAX / 10.0)
#define GOOD         (DBL_MAX / 20.0)

//initial batches to skip when doing the statistics

#define SKIPPEDBATCHES 1

// The type of traffic

#define Background   0
#define Realtime     1
#define Nonsense     2

#define PRIORITYLEVELS 1

//Geographic distances spanned by the network, roughly the area of the USA

#define WIDTH   4000.0              // 4000 Km
#define HEIGHT  2400.0              // 2400 Km
#define RATIO   (HEIGHT / WIDTH)



// The components contributing to the end-to-end delay

//#define LINKCAPACITY    155.2e6
#define BYTE            8
#define CELLSIZE        53 * 8
#define CELLBYTES       53
//#define Ttransmission   (CELLSIZE / LINKCAPACITY)
#define Tswitching      30e-6
#define LIGHTSPEED      3e5    // Km/sec
#define PROPSPEED       ((2.0 / 3.0)  * LIGHTSPEED)
//#define PROPSPEED       LIGHTSPEED
#define Tpropagation    (WIDTH / PROPSPEED)   
                               //(sec/ maximum horizontal distance)

//To allow heterogenous link capacities use the following:

#define OC1  51.7e06
#define OC3  155.2e06
#define OC12 620.8e06
#define OC48 2483.2e06 
#define MAXCAPACITY OC48
//Define the time slot for the discrete random sources

#define TIMESLOT (CELLSIZE / OC48)

#define DIMENSION ((int)(MAXCAPACITY/1e6)+2) //For histogram statistics

// The parameters below are for the IBP sources

#define IDLE      0                  
#define ACTIVE    1
#define NEXT      2

#define MAXATTEMPTS 10000
#define DEGREEERROR 0

//Traffic Models

#define IBP         1
#define VOICE       2
#define VIDEO       3
#define BACKGROUND  4

//Define the mean batch size for the background model which is a batch
//version of Maglaris video model

#define MEANBATCH   10


//Define routing algorithms

#define dksld  0   //Dijkstra's least-delay
#define kmb    1   //KMB heuristic for unconstrained Steiner tree

#define atm2   2   //Modified Waters ATM heuristic
#define cao    3   //Tenet constrained adaptive routing algorithm
#define bsma   4   //UCSC constrained algorithm
#define cstc   5   //2nd constrained MC heuristic by Polyzos

#define cstcd  6   //1st constrained MC heuristic by Polyzos
#define atm    7   //Waters ATM heuristic

#define bf     8   //Bellman-Ford least-cost alg.  
#define dks    9   //Dijkstra's least-cost alg.
#define pim    10  //PIM routing alg.
#define mst    11  //MST heuristic
#define dcdimst 12 //delay-constrained directed MST
#define copt    13 //optimal branch and bound based constr. Steiner tree alg.
#define opt     14 //optimal branch and bound based unconstr. Steiner tree alg.
#define dimst   15
#define dvmrp   16
#define bfnoadm 17
#define cdks    18

//For the confidence intervals

#define Acceptable .1

//Different link cost metrics

#define PEAK     1
#define AVERAGE  2

//Different link objective metrics

#define PLAIN   1
#define MULT    2
#define ADD     3

//I will make ALPHA a variable of the class TheNodeList
//#define ALPHA   15   //in Mbps A constant to be used weith the additive link
                       //objective function.

class Node;
class TheNodeList;

#include "graphics.h"
#include "queue.h"
#include "event.h"

class Source {   // A traffic source, can be IBP, MMPP .... etc.

   protected:
      Node* nd;      //each source points to the node it is connected to.
      int stype;     //background traffic:             stype = 0
                     //multicast or unicast traffic:   stype = 1
      int spriority; //priority of the traffic generated by the source  
      int   addr;    //the address field in the data packets from that source
                     //the multicast group address
                     //addr = adjacent node name for background traffic
      int mdl;       //model used: IBP, MMPP ...etc.
      double pk;     //peak rate
      unsigned long sn; //sequence number of the last cell generated
      double avg;    //the average bit rate
      virtual double generateNext(int &jStop, int &size) = 0;
		     // traffic generator

   public:
      Source() {};
      virtual ~Source() {};
      virtual Node  *nodePtr() { return(nd); };
      virtual void  nodePtr(Node* n) { nd = n; };
      virtual int   type() { return(stype); };
      virtual void  type(int t) { stype = t; };
      virtual int   priority() { return(spriority); };
      virtual void  priority(int pr) { spriority = pr; };
      virtual int   address() { return(addr); };
      virtual void  address(int a) { addr = a; };
      virtual int   model() { return(mdl); };
      virtual void  model(int m) { mdl = m; };
      virtual double peak() { return(pk); };
      virtual void   peak(double p) { pk = p; };
      virtual double average() { return(avg); };
      virtual void average(double a) { avg = a; };
      virtual unsigned long seqNum() { return(sn); };
      virtual void seqNum(unsigned long n) { sn = n; };
      virtual void  sourceToNode(Data *d, double t_global, TheEventList *E,
                                          TheNodeList *N, int stats);  
                                    //generate a packet and put it in the
                                    //appropriate queue for transmission
}; //Source

class IBPSource : public Source {

   private:
      double brst;  //c2 as given for IBP sources
      double on_slot;
      double off_slot;
      double on_off;  // (1-p) for an IBP process
      double off_on;  // (1-q) for an IBP process
      double generateNext(int &jStop, int &size);

   public:
      IBPSource(int type, int priority, Node* n, int a,
                double peak, double average, double burst);
      ~IBPSource() {};
      double burst() { return(brst); };
      double onSlot() { return(on_slot); };
      double offSlot() { return(off_slot); };
      double onOff() { return(on_off); };
      double offOn() { return(off_on); };

}; //IBPSource

class VoiceSource : public Source {

   private:
      double brst;  //average burst size in time units
      double ro;   //avg rate / peak rate
      double on_slot; //1 / peak rate
      double off_slot;//1 / link capacity
      double on_off;  // prob. of going from on to off
      double off_on;  // prob. of going from off to on
      double generateNext(int &jStop, int &size);

   public:
      VoiceSource(int type, int priority, Node* n, int a,
                  double peak, double rho, double burst);
      ~VoiceSource() {};
      double burst() { return(brst); };
      double rho() { return(ro); };
      double onSlot() { return(on_slot); };
      double offSlot() { return(off_slot); };
      double onOff() { return(on_off); };
      double offOn() { return(off_on); };
}; //VoiceSource

class VideoSource : public Source {

   private:
      //refer to Maglaris paper for the model B of video
      double brst;  //average burst size in time units
      double ro;   //avg rate / peak rate
      double alpha;
      double beta;
      int m;
      double p; //prob. of transition to a higher state = (m - i) * p 
      double q; //prob. of transition to a lower state = i * q
                // i is the currentState
      int currentState;
      double currentSlot;
      double off_slot;
      double generateNext(int &jStop, int &size);

   public:
      VideoSource(int type, int priority, Node* n, int a, 
                       double peak, double rho, double burst);
      ~VideoSource() {};
      double burst() { return(brst); };
      double rho() { return(ro); };
}; //VideoSource

class BackgroundSource : public Source {

   private:
      //refer to Maglaris paper for the model B of video
      double brst;  //average burst size in time units
      double ro;   //avg rate / peak rate
      double alpha;
      double beta;
      int m;
      double p; //prob. of transition to a higher state = (m - i) * p 
      double q; //prob. of transition to a lower state = i * q
                // i is the currentState
      int currentState;
      double currentSlot;
      double off_slot;
      double generateNext(int &jStop, int &size);

   public:
      BackgroundSource(int type, int priority, Node* n, int a, 
                       double peak, double rho, double burst);
      ~BackgroundSource() {};
      double burst() { return(brst); };
      double rho() { return(ro); };
}; //BackgroundSource

class SourceList {   // An element of a linked list of source pointers

   private:
      Source *srce;    //pointer to source
      SourceList *n;   //pointer to the next list entry

   public:
      SourceList() { srce = NULL; n = NULL; };
      ~SourceList() { delete srce; };
      Source *source() { return(srce); };
      void   source(Source *s) { srce = s; };
      SourceList *next() { return(n); };
      void next(SourceList *nn) { n =nn; };
      
}; //SourceList

class NodeListEntry {   // An element of a doubly linked list of node pointers

   private:
      Node *nd;           //pointer to node
      NodeListEntry *n;   //pointer to the next list entry
      NodeListEntry *p;   //pointer to the previous list entry
   public:
      NodeListEntry() { nd = NULL; n = NULL; p = NULL; };
      Node *nodePtr() { return(nd); };
      void nodePtr(Node *n) { nd = n; };
      NodeListEntry *next() { return(n); };
      void next(NodeListEntry *nn) { n =nn; };
      NodeListEntry *previous() { return(p); };
      void previous(NodeListEntry *pp) { p = pp; };

}; //NodeListEntry

class RoutingTableEntry {   // An entry in a lookup table for addresses and the
                            // corresponding destinations from a node

   private:
      int                 addr;  // The address is the key used for comparison
      Node                *s;    // The source node
      NodeListEntry       *d;    // the head of a linked list of next-hop
                                 // nodes
      RoutingTableEntry   *n;    // points to the next routing table entry