#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <strings.h>
#include <assert.h>
#include <iostream.h>
// Integration of Ashish's RED and asim
#define _RED_ROUTER_MAIN_
#include "asim.h"
#define sp " "
// Optimization
#include<vector>
using namespace std;
typedef struct c{
int no; // no of edges in the connection
double delay; // total delay;
double drop; // total drop prob
double p_tput;
double t;
// The short flow stuff
int is_sflow; // boolean to indicate whether there is a short flow
double slambda; // The arrival rate of the connections
int snopkts; // average of no of packets each short flow givies
RedRouter * red;
int scaled; // Whether this flow has been scaled or not
}flow_stats;
typedef struct n{
int red; // flag to notify whether its a red queue or not
double pmin, pmax, minth, maxth; // RED parameters
double lambda; // Arrival rate - Packets per second
double plambda; // Temp lambda value. previous lambda
double tlambda;
double mu; // Consumption rate - Packets per second
double prop; // Propagation delay of the link
double qdelay; // Store the queuing delay for each link
int buffer; // Total buffer
double drop; // probability of drop
int nflows; // Number of flows through this link
vector<int> theflows; // The flows through this link
double scaled_lambda;
double unscaled_lambda;
double utput; // unscaled tput
double uc; // unscaled capacity
// RED
RedRouter * redrouter;
}link_stats;
class asim {
public:
// data structures
int nConnections; // Number of connections
int K, MaxHops; //
int nLinks; // Number of links
int **Adj; // Stores the edge list of each connection
int *nAdj; // Stores the no of edges per connection
link_stats* links;
flow_stats* flows;
double min(double x, double y){
return (x<y)?x:y;
}
double padhye(double rtt, double p){
double rto = 1;
double t=1;
t = rtt*sqrt(2*p/3)+rto*min(1,(3*sqrt(3*p/8)))*p*(1+32*p*p);
return min(20/rtt,1/t);
}
double Po(double rho, int K){
if(rho==1)
return 1.0/(K+1);
double t;
t=(1.0*(1-rho))/(1.0-pow(rho,K));
return t;
}
double Pk(double rho, int K, int k){
if(rho==1)
return 1.0/(K+1);
if(rho==0)
return 0;
double t;
// M/M/1/K
t=((1-rho)*pow(rho,k))/(1-pow(rho,K+1));
return t;
}
double Lq(double rho, int K){
double t1,t2;
if(rho==1){
return (1.0*K*(K-1))/(2.0*(K+1));
}
t1=rho*1.0/(1-rho);
t2=rho*1.0/(1-pow(rho,K+1));
t2*=K*pow(rho,K)+1;
return (t1-t2)/2;
}
double get_link_drop(int x){
assert(x<nLinks);
return links[x].drop;
}
double get_link_delay(int x){
assert(x<nLinks);
return links[x].qdelay + links[x].prop ;
}
double get_link_qdelay(int x){
assert(x<nLinks);
return links[x].qdelay;
}
double get_link_pdelay(int x){
assert(x<nLinks);
return links[x].prop;
}
double get_link_tput(int x){
assert(x<nLinks);
return links[x].lambda;
}
double get_flow_delay(int x){
assert(x<nConnections);
return flows[x].delay;
}
double get_flow_tput(int x){
assert(x<nConnections);
return flows[x].p_tput;
}
double get_flow_drop(int x){
assert(x<nConnections);
return flows[x].drop;
}
void GetInputs(char *argv) {
// Init links and connections
nConnections = 0;
nLinks = 0;
// Start the reading process
FILE *f;
f = fopen(argv,"r");
assert(f);
char s[256];
while (fgets(s, 255, f)) {
// Read a token
char *t;
t = strtok(s, " \t\n");
// Ignore comments
if (!t || !t[0] || (t[0] == '#') || !strncasecmp(t, "comment", 6))
continue;
// Define the number of connections
if (!strcasecmp(t,"n")) {
t = strtok(NULL," \t");
assert(t);
nConnections = atoi(t);
assert(nConnections > 0);
assert(nConnections >= 0);
nAdj = new int[nConnections];
Adj = new int*[nConnections];
flows = new flow_stats[nConnections];
for (int i=0; i<nConnections; ++i)
nAdj[i] = -1;
continue;
}
// Define the number of links
else if (!strcasecmp(t,"m")) {
t = strtok(NULL," \t");
assert(t);
// #of links defined
nLinks = atoi(t);
assert(nLinks > 0);
// Allocate space for sotring lambdas and mus
links = new link_stats[nLinks];
continue;
}
// Enter each route
else if (!strcasecmp(t,"route")) {
assert (nConnections > 0);
assert (nLinks > 0);
t = strtok(NULL," \t");
assert(t);
int i = atoi(t);
assert(i > 0 && i<= nConnections);
i--;
// We dunno whether this will be short flow specs
flows[i].is_sflow = 0; // Lets assume its a normal flow
flows[i].drop = 0; // Assume ideal case to start off
flows[i].scaled = 0; // Not scaled as yet
t = strtok(NULL," \t");
assert(t);
nAdj[i] = atoi(t);
assert(nAdj[i] > 0 && nAdj[i] <= nLinks);
// We know how many links it will use
Adj[i] = new int[nAdj[i]];
for (int j=0; j<nAdj[i]; ++j) {
t = strtok(NULL," \t");
assert(t);
int l = atoi(t);
assert(l > 0 && l <= nLinks);
l--;
Adj[i][j] = l;
}
if (MaxHops < nAdj[i]) MaxHops = nAdj[i];
t = strtok(NULL," \t");
// assert(t);
// Short flows stuff
if (t && !strcasecmp(t,"sh")) {
// There are short flows on this route.
flows[i].is_sflow = 1;
// read the slambda
t = strtok(NULL," \t");
assert(t);
double tmp = atof(t);
flows[i].slambda = tmp;
// read the snopkts
t = strtok(NULL," \t");
assert(t);
int tmpi = atoi(t);
flows[i].snopkts = tmpi;
}
// For cbr
// Treat almost like a short flow!
if (t && !strcasecmp(t,"cbr")) {
// There are short flows on this route.
flows[i].is_sflow = 2;
// read the rate
t = strtok(NULL," \t");
assert(t);
double tmp = atof(t);
flows[i].slambda = tmp;
flows[i].snopkts = 1;
}
// Now, let us put the flows in persective
// Insert the flow id trhough all the links
int l_;
for(int j=0;j<nAdj[i];j++){
l_ = Adj[i][j];
(links[l_].theflows).push_back(i);
links[l_].nflows++;
if(flows[i].is_sflow){
links[l_].lambda+=flows[i].slambda*flows[i].snopkts;
}
}
continue;
}
else if(!strcasecmp(t,"link")){
assert (nLinks > 0);
// Get the link number
t = strtok(NULL," \t");
assert(t);
int i = atoi(t);
assert(i > 0 && i<= nLinks);
i--;
// Get the prop delay
t = strtok(NULL," \t");
assert(t);
double p = atof(t);
assert(p>=0);
links[i].prop = p;
// Get the lambda for this link
t = strtok(NULL," \t");
assert(t);
p = atof(t);
assert(p>=0);
links[i].lambda = 0;
links[i].tlambda = p;
links[i].plambda = p;
// Get the mu for this link
t = strtok(NULL," \t");
assert(t);
p = atof(t);
assert(p>=0);
links[i].mu = p;
// Get the buffer for this link
t = strtok(NULL," \t");
assert(t);
int t1 = atoi(t);
assert(t1>0);
links[i].buffer = t1;
// Check for RED Q or not
t = strtok(NULL," \t");
if(t && !strcasecmp(t,"red")){
// must be a red queue
// input red parameters
// all parameters between 0 and 1
links[i].red=1;
// get minth
t = strtok(NULL," \t");
double dt = atof(t);
//assert(dt>=0 && dt<=1);
links[i].minth=dt;
// get pmin
t = strtok(NULL," \t");
dt = atof(t);
//assert(dt>=0 && dt<=1);
links[i].pmin=dt;
// get maxth
t = strtok(NULL," \t");
dt = atof(t);
//assert(dt>=0 && dt<=1);
links[i].maxth=dt;
// get pmax
t = strtok(NULL," \t");
dt = atof(t);
//assert(dt>=0 && dt<=1);
links[i].pmax=dt;
// Invoke Ashish's RED module ... ignore pmin .....
links[i].redrouter = new RedRouter((int)links[i].minth,
(int)links[i].maxth,
links[i].pmax);
assert(links[i].red);
}
else{
links[i].red=0;
}
links[i].nflows = 0; // init the num of flows
continue;
}
assert(0);
}
// Check whether everything is all right
assert (nConnections > 0);
assert (nLinks > 0);
for (int i=0; i<nConnections; ++i)
assert(nAdj[i] > 0);
}
double redFn(double minth, double pmin,
double maxth, double pmax, double qlength){
assert(qlength>=0 && qlength<=1);
assert(pmax>=0 && pmax<=1);
assert(pmin>=0 && pmin<=1);
assert(minth>=0 && minth<=1);
assert(maxth>=0 && maxth<=1);
assert(maxth>=minth);
assert(pmax>pmin);
double t;
if(qlength<minth)
return 0;
if(qlength>maxth)
return 1;
return pmin + (qlength-minth)/(pmax-pmin);
}
void CalcLinkStats(int flag = 0){
// flag = 1 means enable RED
// Calculate Link delays ... basically queuing delays
for(int i=0; i<nLinks; i++){
double rho = links[i].lambda/links[i].mu;
double qlength = Lq(rho,links[i].buffer);
links[i].qdelay = qlength/links[i].mu;
links[i].drop = Pk(rho,links[i].buffer,links[i].buffer);
// cout << "Link " << i << " has drop prob = " << links[i].drop << endl;
// Special code for RED gateways
if(flag){
if(links[i].red){
double minth, maxth, pmin, pmax, delay,p;
minth = links[i].minth;
maxth = links[i].maxth;
pmin = links[i].pmin;
pmax = links[i].pmax;
// The RED approx.
p=(links[i].redrouter)->ComputeProbability(rho, delay);
links[i].drop = p;
qlength = Lq(rho*(1-p), links[i].buffer);
links[i].qdelay = delay;
}
}
// cout << i << sp << "rho = " << rho << " delay = " << links[i].qdelay << " and drop = " << links[i].drop << endl;
}
}
void CalcPerFlowStats(){
for(int i=0; i<nConnections; i++){
double d = 0, p = 1 ;
// Calculate drops and delays
for(int j=0;j<nAdj[i];j++){
d += 2*links[Adj[i][j]].prop + links[Adj[i][j]].qdelay;
p *= 1-links[Adj[i][j]].drop;
}
p = 1-p;
//cout << "Flow " << i << " has drop prob = " << p << endl;
flows[i].no = nAdj[i];
flows[i].delay = d;
flows[i].drop = p;
flows[i].t = flows[i].p_tput;
// p is the end2end drop prob
// If its normal flow, calculate Padhye's stuff
// If its short flow, use our approximations
// Nothing more
if(flows[i].is_sflow==1){
// If k flows come and each each flow has n packets to
// send then
double t = (flows[i].slambda*flows[i].snopkts);
flows[i].p_tput = t/(1-p);
}
else if(flows[i].is_sflow==2){
// For CBR, dont divide by 1-p unlike short flows.
// If rate is x and prob is p, net goodput is x(1-p)
flows[i].p_tput = flows[i].slambda*(1-p);
// cout << "cbr stuff - tput = " << flows[i].p_tput << endl;
}
else{
// regular bulk TCP connections, Padhye et. al.
if(!p){
// cout << "Oops, something wrong";
}
flows[i].p_tput = padhye(d,p);
}
// cout << "connection " << sp << i << sp << d << sp << p;
//cout << sp << flows[i].p_tput << endl;
}
}
void PrintData(){
for(int i=0;i<nLinks;i++){
cout << i << sp << links[i].lambda << sp << links[i].mu;
cout << sp << links[i].buffer << endl;
}
}
void PrintResults(){
for(int i=0;i<nLinks;i++){
printf("l %d qdel %.5lf drop %.5lf lam %.3lf\n", i+1, links[i].qdelay, links[i].drop,links[i].lambda);
}
for(int i=0; i<nConnections; i++){
printf("c %d gput %.5lf drop %.5lf e2edel %.5lf\n", i+1,
flows[i].p_tput,
flows[i].drop,
flows[i].delay);
}
}
void UpdateHelper(int flag=0){
// if flag = 1 then update only when link is unscaled as of now
// if flag = 0 then do the usual update
for(int i=0; i<nLinks; i++){
links[i].tlambda=0;
}
for(int i=0; i<nConnections; i++){
if(!flag || !flows[i].scaled)
for(int j=0;j<nAdj[i];j++){
if(flows[i].is_sflow==2){
// cbr flow
links[Adj[i][j]].tlambda += flows[i].slambda*(1-links[Adj[i][j]].drop);
//cout << "cbr flow " << i << " adding " << flows[i].slambda*(1-links[Adj[i][j]].drop)
// << " to link " << j << " tlam = " << links[Adj[i][j]].tlambda << endl;
}
else
links[Adj[i][j]].tlambda += flows[i].p_tput;
}
// cout << flows[i].p_tput << "\n";
}
}
void Update(int niter){
UpdateHelper();
for(int i=0; i<nLinks; i++){
links[i].plambda = links[i].lambda;
double t;
double tk=links[i].mu*(1.05)+5;
if(niter){
if(links[i].tlambda>tk)
//t = pow((sqrt(links[i].lambda)+sqrt(links[i].mu+5))/2,2);
t = ((links[i].lambda)+tk)/2;
// t = exp((log(links[i].lambda)+log(links[i].mu+5))/2);
else
//t = pow((sqrt(links[i].tlambda)+sqrt(links[i].lambda))/2,2);
t= ((links[i].tlambda)+(links[i].lambda))/2;
// t = exp((log(links[i].tlambda)+log(links[i].lambda))/2);
}
else t = links[i].tlambda;
links[i].lambda = t; // Update the lambda ..........
}
}
int allscaled(){
//cout << nConnections;
for(int i=0; i<nConnections; i++)
if(!flows[i].is_sflow && !flows[i].scaled){
//cout << "Connection " << i << " not scaled as yet\n";
return 0;
}
cout << "All are scaled\n";
return 1;
}
void newupdate(int niter){
// 1st init all unscaled tputs and cap
for (int i=0;i<nLinks;i++){
links[i].uc = links[i].mu*(1.05);
links[i].utput = 0;
}
// calc all the unscaled tputs and C set all short flows
// to be scaled already
for(int i=0; i<nConnections; i++){
if(flows[i].is_sflow)
flows[i].scaled = 1;
else
flows[i].scaled = 0;
for(int j=0;j<nAdj[i];j++){
if(flows[i].is_sflow)
links[Adj[i][j]].uc -= flows[i].p_tput;
else
links[Adj[i][j]].utput += flows[i].p_tput;
}
}
//for(int i =0; i<nLinks; i++ ){
//cout << i << sp << links[i].uc << sp << links[i].utput << endl;
//}
double maxgamma; // most congested link
int bneck;
double t;
bneck = -1;
maxgamma = 0;
for(int i=0; i<nLinks; i++){
if(links[i].uc){
t=links[i].utput/links[i].uc;
if(t > maxgamma){
bneck = i;
maxgamma = t;
}
}
}
while(bneck+1){
//cout << "bneck = " << bneck << sp << links[bneck].uc << sp << links[bneck].utput << sp << maxgamma << sp << links[bneck].nflows <<endl;
for(int i=0; i<links[bneck].nflows; i++){
// For all the connections passing through this link
int t = links[bneck].theflows[i]; // get a connection id
// cout << i<< sp << t << sp ;
// Now reduce its p_tput iff its not a short flow
// For short flows we dont do scaling
if(!flows[t].is_sflow && !flows[t].scaled){
flows[t].p_tput /= maxgamma;
//cout << "Flow " << t << " getting scaled to << " << flows[t].p_tput;
flows[t].scaled = 1; // we have scaled this flow already
for(int j=0;j<nAdj[t];j++){
// subtract this scaled throughout from all teh links that
// have this flow.
links[Adj[t][j]].uc -= flows[t].p_tput;
links[Adj[t][j]].utput -= flows[t].p_tput*maxgamma;
// cout << sp << Adj[i][j];
}
//cout << endl;
}
}
//cout << links[bneck].uc << sp << links[bneck].utput << endl;
links[bneck].uc = 0;
bneck = -1;
maxgamma = 0;
for(int i=0; i<nLinks; i++){
if(links[i].uc){
t=links[i].utput/links[i].uc;
if(t > maxgamma){
bneck = i;
maxgamma = t;
}
}
}
}
Update(niter);
}
asim(){
//cout << "Reached here\n";
}
};
int main(int argc, char **argv) {
int niter = 0;
// error if usage is wrong
if (argc != 2) {
fprintf(stderr,"Usage: %s <InputFile>\n", argv[0]);
exit(-1);
}
asim sim;
sim.GetInputs(argv[1]);
//sim.PrintResults();
//cout << "Read the input .... \n";
for(int i=0; i<3; i++){
sim.CalcLinkStats(1);
//cout << "Calculated link delays ... \n";
sim.CalcPerFlowStats();
//cout << "Calculated per flow delays ... \n";
//cout << " ------------------------------\n";
sim.newupdate(niter);
//sim.PrintResults();
//cout << " ------------------------------\n";
}
sim.PrintResults();
}
syntax highlighted by Code2HTML, v. 0.9.1