📄 rout.c
字号:
/*****************************************************************************
*** Author: Hussein F. Salama ***
*** Date: September 9, 1994 ***
*** File: rout.c ***
*** Routing Algorithms ***
*****************************************************************************/
double TheNodeList::router(int alg, Node *source, int addr,
double &d, double &maxd, double &mind, double &h,
double &nodes) {
if (alg == pim) return(routerPIM(source, addr, d, maxd, mind, h, nodes));
else if ((alg == atm) || (alg == atm2))
return(routerWaters(alg, source, addr, d, maxd, mind, h, nodes));
else if ((alg == cstc) || (alg == cstcd))
return(routerCST(alg, source, addr, d, maxd, mind, h, nodes));
else if (alg == dksld) return(routerLD(source, addr, d, maxd, mind,h, nodes));
else if (alg == kmb) return(routerKMB(source, addr, d, maxd, mind, h, nodes));
else if (alg == bf) return(routerBF(source, addr, d, maxd, mind, h, nodes));
else if (alg == cao) return(routerCAO(source, addr, d, maxd, mind, h, nodes));
else if (alg == bsma) return(routerBSMA(source, addr, d, maxd, mind,h,nodes));
else if ((alg == dcdimst) || (alg == dimst))
return(routerDCDIMST(alg, source, addr, d, maxd, mind, h, nodes));
else if ((alg == opt) || (alg == copt))
return(routerOPT(alg, source, addr, d, maxd, mind, h, nodes));
else if (alg == dvmrp)
return(routerDVMRP(source, addr, d, maxd, mind, h, nodes));
else if (alg == bfnoadm)
return(routerBFNOADM(source, addr, d, maxd, mind, h, nodes));
else if (alg == cdks)
return(routerCDKS(source, addr, d, maxd, mind, h, nodes));
else {
//The Dijkstra's shortest path routing algorithms
NodeListEntry *tree, *tmp1, *tmp2;
Node *bestDest;
RoutingTableEntry *bestRout;
AdjacencyListEntry *bestAdj;
double bestCost;
int bestHop;
double totalCost = 0;
double *cost_matrix;
int *hop_matrix;
//First delete any previous routing for the this group and source set.
removeTree(source, addr);
//Locate the source to get the peak rate
SourceList *ss = source->sourceList();
int found = False;
while ((ss != NULL) && (found == False)) {
if ((ss->source()->type() != Background) &&
(ss->source()->address() == addr)) found = True;
else ss = ss->next();
};
double pk = ss->source()->peak();
double avg = ss->source()->average();
//Locate the MC group that contains the destination set
MCGroup *group = groupsHd;
while ((group != NULL) && (group->address() != addr))
group = group->next();
if (group != NULL) {
cost_matrix = new double[num];
hop_matrix = new int[num];
int i;
for (i = 0; i < num; i++) *(cost_matrix + i) = DBL_MAX;
if ((group->count() == 1) &&
(group->headm()->nodePtr()->name() == source->name())) {
source->addRoutingEntry(addr, source);
delete [] cost_matrix;
delete [] hop_matrix;
h = d = maxd = mind = 0;
nodes = 1;
return(0);
};
//The source is the first member in the tree
tree = new NodeListEntry;
tree->nodePtr(source);
source->addRoutingEntry(addr, source);
*(cost_matrix + source->name()) = 0;
*(hop_matrix + source->name()) = 0;
int done = False;
while (done == False) {
tmp1 = tree; //for each node already in the tree
bestCost = DBL_MAX; //infinity
bestAdj = NULL;
while (tmp1 != NULL) {
//find the routing table entry for the given group & source
RoutingTableEntry *rout = tmp1->nodePtr()->routingTable();
int found = False;
while ((rout != NULL) && (found == False)) {
if ((rout->address() == addr) && (rout->source() == source))
found = True;
else rout = rout->next();
};
//scan the adjacency list for the least cost (weight) link
AdjacencyListEntry *adj = tmp1->nodePtr()->adjacentNodes();
while (adj != NULL) {
int better = False;
double weight;
if ((fn == PEAK) && ((adj->peak() + pk) <=
(adj->linkCapacity() * ADMITRATIO)))
weight = adj->peak();
else if ((fn == AVERAGE) &&
((adj->average() + avg) <=
(adj->linkCapacity() * ADMITRATIO)))
weight = adj->average();
else weight = DBL_MAX;
switch (obj) {
case PLAIN:
if ((alg == dks) &&
((*(cost_matrix + tmp1->nodePtr()->name()) + weight) <
bestCost)) better = True;
if ((alg == mst) && (weight < bestCost)) better = True;
break;
case MULT:
if ((alg == dks) &&
((*(cost_matrix + tmp1->nodePtr()->name()) +
weight *
(*(hop_matrix + tmp1->nodePtr()->name()) + 1))
< bestCost)) better = True;
if ((alg == mst) && ((weight *
(*(hop_matrix + tmp1->nodePtr()->name()) + 1))
< bestCost)) better = True;
break;
case ADD:
if ((alg == dks) &&
((*(cost_matrix + tmp1->nodePtr()->name()) +
weight +
*(hop_matrix + tmp1->nodePtr()->name()) * ALPHA)
< bestCost)) better = True;
if ((alg == mst) && ((weight +
*(hop_matrix + tmp1->nodePtr()->name()) * ALPHA)
< bestCost)) better = True;
break;
};
//if the cost of that adjacent node is less than the best
//cost so far
if (better == True) {
tmp2 = tree;
found = False;
while ((tmp2 != NULL) && (found == False)) {
//check if that adjacent node is already in the tree
if (tmp2->nodePtr() == adj->nodePtr()) found = True;
else tmp2 = tmp2->next();
};
if (found == False) {
//if not update the bestCost ...etc.
if (alg == dks) {
switch (obj) {
case PLAIN:
bestCost =
*(cost_matrix + tmp1->nodePtr()->name()) + weight;
break;
case MULT:
bestCost = *(cost_matrix + tmp1->nodePtr()->name())
+ weight *
(*(hop_matrix + tmp1->nodePtr()->name())
+ 1);
break;
case ADD:
bestCost = *(cost_matrix + tmp1->nodePtr()->name())
+ weight +
*(hop_matrix + tmp1->nodePtr()->name())
* ALPHA;
break;
};
}
else {// case of mst
switch (obj) {
case PLAIN:
bestCost = weight;
break;
case MULT:
bestCost = weight *
(*(hop_matrix + tmp1->nodePtr()->name())
+ 1);
break;
case ADD:
bestCost = weight +
*(hop_matrix + tmp1->nodePtr()->name())
* ALPHA;
break;
};
};
bestDest = adj->nodePtr();
bestRout = rout;
bestAdj = adj;
bestHop = *(hop_matrix + tmp1->nodePtr()->name()) + 1;
};
};
adj = adj->next(); //repeat for all nodes adjacent to tmp1
};
tmp1 = tmp1->next(); //repeat for all nodes already in the tree
};
if (bestAdj == NULL) {
removeTree(source, addr);
tmp1 = tree;
while (tmp1 != NULL) {
tmp2 = tmp1->next();
delete tmp1;
tmp1 = tmp2;
};
delete [] cost_matrix;
delete [] hop_matrix;
return(LINKSAT);
}
else {
//Add the least cost node to the tree
tmp1 = new NodeListEntry;
tmp1->nodePtr(bestDest);
tmp1->next(tree);
tree = tmp1;
//update the link cost
double wght = bestAdj->peak() + pk; //link costs are proportional
//to the peak rates of the
//traffic crossing these
//links.
bestAdj->peak(wght);
double average = bestAdj->average() + avg;
bestAdj->average(average);
//and add it to the routing table of the best connection node
bestRout->addDestination(bestDest);
//create a new routing table entry for that node
tmp1->nodePtr()->addRoutingEntry(addr, source);
*(cost_matrix + bestDest->name()) = bestCost;
*(hop_matrix + bestDest->name()) = bestHop;
//Check if the tree contains all group members
tmp2 = group->headm();
int quit = False;
while ((tmp2 != NULL) && (quit == False)) {
int found = False;
tmp1 = tree;
while ((tmp1 != NULL) && (found == False)) {
if (tmp1->nodePtr() == tmp2->nodePtr()) found = True;
else tmp1 = tmp1->next();
};
if (tmp1 == NULL) quit = True; //if the tree doesn't include all
//group members yet.
tmp2 = tmp2->next();
};
if (quit == False) done = True;
}; //end bestCost >=
}; //end done
delete [] hop_matrix;
delete [] cost_matrix;
//prune nonmember leaves
prune(group, &tree, source, source, addr, NULL, pk, avg);
int dbViolation = False;
maxd = 0;
mind = DBL_MAX;
//calculate the expected end-to-end delay and the average number of hops
//and the cost per destination
tmp2 = group->headm();
double avgDelay = 0;
double avgHops = 0;
while (tmp2 != NULL) {
int gotit = False;
int hops = 0;
double delay = 0;
if (source != tmp2->nodePtr())
results(source, addr, source, tmp2->nodePtr(), delay, hops, gotit);
if (delay >= DELAYBOUND) dbViolation = True;
if (delay > maxd) maxd = delay;
if (delay < mind) mind = delay;
avgDelay += delay;
avgHops += hops;
tmp2 = tmp2->next();
};
avgDelay /= group->count();
avgHops /= group->count();
d = avgDelay;
h = avgHops;
//Calculate the total cost of the tree and delete the temp. tree
nodes = 0;
tmp1 = tree;
while (tmp1 != NULL) {
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -