q.h

Go to the documentation of this file.

/** \file q.h
                                                                                                         
  \brief Queueing  data structures
                                                                                                         
******************************************************************************/

#ifndef _Q
#define _Q

#ifdef __cplusplus
extern "C" {
#endif

#include "nm.h"
#include "pkt.h"

/**
  * \brief  Boilerplate placeholder for enum decls.
  * 
  */

typedef enum
{
  QDrr_c
} QTypes_c;

/**
  * \brief  Data structure for differentiated service based on class
  * of service. 
  * 
  * The class of service identified by a contiguous set of  integers 
  * starting from 0. COS is strict: when sending packets 
  * on the egress, we consider packets of class k only when there
  * are no packets of class k+1 or more.
  * 
  */


struct Q_Cos_t
{
  int numClasses;
  lsList *packetQueueArray; // numClasses long array of lsList, 
  // each lsList contains pointers to a  Pkt_ProcessPkt_t
  // the beginning of the list is the head of the queue
  // the end of the list is the end of the queue
  int numPktsInQueue;
};

typedef struct Q_Cos_t Q_Cos_t;

/**
  * \brief  Data structure for differentiated service based on DRR.

  * Arranged as a hashtable of individual queues; the hash
  * is from flow hashcodes to corresponding queues, which are just 
  * lists.  For now each queue is given a weight of 1, so there is
  * no weight information.
  * 
  */

struct Q_Drr_t
{
  st_table *flowToQueueTable;
  lsList qOfFlows;
  int numPktsInQueue;
  int numBytesInQueue;
};

typedef struct Q_Drr_t Q_Drr_t;


/**
  * \brief Data structure for keeping flow
  *
  */

struct Q_Flow_t
{
  lsList queue;
  unsigned int numBytes;
  unsigned int numPkts;
  double rate;
  util_timing_t startOfCurrentWindow;
  double numBytesExitedInWindow;

};

typedef struct Q_Flow_t Q_Flow_t;

// start of code that's being moved from rlp

/**
  *     \brief  Enum for the drop policies
  *
  */

typedef enum
{
  Q_DropTail_c,
  Q_DropRed_c
} Q_DropMethods_t;

/**
  *     \brief Enum for types of queues
  */

typedef enum
{
  Q_QueueTypeUndef_c,
  Q_QueueTypeCos_c,
  Q_QueueTypeFlow_c
} Q_QueueType_t;


/**
  *     \brief  Cos Queue structure used for actions
  *
  *     Cos Queue structure used for actions
  *
  */

struct Q_Q_t
{
  char *name;

  // could be a class based or flow based
  Q_QueueType_t type;

  // this make sense only for flow-based queueing
  Pkt_FlowType_t flowType;
  int flowMaxRate;
  int maxFlows;
  int maxBytesPerFlow;
  Q_DropMethods_t flowDropMethod;

  int maxRate;          // in bits-per-second

  double currentRate;       // in bits-per-second
  util_timing_t lastEntryTime;  // basically a pair of u_int_32_t set by the rdtsc instruction

  int currentPriority;      // can be positive/0/negative, used to decide when to come back to this queue
  // dynamically updated based on assigned priority
  int assignedPriority;     // can be positive/0/negative, assigned by used in rule

  int numPktsInQueue;
  double numPktsProcessed;  // total number of packets we've processed so far

  int numBytesInQueue;
  int maxAllowedBytes;      // if we have this number in the queue, the queue is stopped
  double numBytesEntered;
  double numBytesExited;

  Q_DropMethods_t dropMethod;

  // actual queueing structure for cos case
  int numClasses;
  Q_Cos_t *cosQ;

  // actual queueing structure for flow-based queuing case
  Q_Drr_t *flowQ;

  double timeWindowDuration;
  double numBytesExitedInWindow;
  util_timing_t startOfCurrentWindow;

};

typedef struct Q_Q_t Q_Q_t;


/**AutomaticStart*************************************************************/

/*---------------------------------------------------------------------------*/
/* Extern function prototypes                                                */
/*---------------------------------------------------------------------------*/


extern Q_Cos_t *Q_CosAlloc (int);
extern int Q_CosFree (Q_Cos_t *);
extern Q_Drr_t
  *Q_DrrAlloc (int (*flowCmp) (Pkt_EthernetHdr_t *, Pkt_EthernetHdr_t *),
           int (*flowHash) (Pkt_EthernetHdr_t *, int));
extern int Q_DrrFree (Q_Drr_t * aDrrStruct);
extern int Q_CosInsertPpBegin( Q_Cos_t *cosStruct, Pkt_ProcessPkt_t *anEthFrame, int classIndex );
extern int Q_CosInsertPpEnd (Q_Cos_t *, Pkt_ProcessPkt_t *, int);
extern int Q_CosInsertPpBeginEnd (Q_Cos_t *, Pkt_ProcessPkt_t *, int, int );
extern Pkt_ProcessPkt_t *Q_CosReadPp (Q_Cos_t * cosStruct);
extern Pkt_ProcessPkt_t *Q_CosReadHead (Q_Cos_t * cosStruct, int *classPtr);
extern Pkt_ProcessPkt_t *Q_CosHead (Q_Cos_t * cosStruct, int *classPtr);
extern Pkt_ProcessPkt_t *Q_CosHeadClass (Q_Cos_t * cosStruct, int classIndex);
extern int Q_CosNumClasses (Q_Cos_t * cosStruct);
extern int Q_DrrTestIsEmpty (Q_Drr_t * flowQueue);
extern int Q_CosTestIsEmpty (Q_Cos_t * cosStruct);
extern int Q_DrrInsertPpBegin (Q_Drr_t * drrStruct, Pkt_ProcessPkt_t * pp);
extern int Q_DrrInsertPpEnd (Q_Drr_t * drrStruct, Pkt_ProcessPkt_t * pp);
extern int Q_DrrInsertPpBeginEnd (Q_Drr_t * drrStruct, Pkt_ProcessPkt_t * pp,
                  int insertAtEnd);
extern Q_Flow_t *Q_DrrReadFlow (Q_Drr_t * drrStruct, Pkt_EthernetHdr_t * pkt);
extern Pkt_ProcessPkt_t *Q_DrrHead (Q_Drr_t * drrStruct);
extern Pkt_ProcessPkt_t *Q_DrrReadHead (Q_Drr_t * drrStruct);
extern st_table *Q_DrrReadFlowToQueueTable (Q_Drr_t * drrStruct);
extern int Q_DrrNumFlows (Q_Drr_t * drrStruct);
extern void Q_CosPrint (Q_Cos_t * cosData);
extern void Q_DrrPrint (Q_Drr_t * drrData);
extern Q_Flow_t *Q_AllocFlow ();
extern double Q_ComputeRate (util_timing_t startOfWindow,
                 double timeWindowDuration,
                 int numBytesExitedInWindow, int pktLength);
extern double Q_ComputeRateOld (util_timing_t lastTime,
                Pkt_EthernetHdr_t * pkt);
extern Q_Q_t *Q_AllocQ (char *name);

/**AutomaticEnd***************************************************************/
#ifdef __cplusplus
}
#endif

#endif /* _Q */