From c36d15fa17cb573585e0b3841b89420b56bf18a4 Mon Sep 17 00:00:00 2001 From: Arnaud Giersch Date: Thu, 24 Feb 2011 16:37:10 +0100 Subject: [PATCH 1/1] Add reference code for Makhoul's algorithm. --- makhoul.txt | 229 ++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 229 insertions(+) create mode 100644 makhoul.txt diff --git a/makhoul.txt b/makhoul.txt new file mode 100644 index 0000000..344206a --- /dev/null +++ b/makhoul.txt @@ -0,0 +1,229 @@ +Makhoul's algorithm... several versions for source code... +========================================================== + +powwow:/home/makhoul# find . -name Fusion.cc -exec md5sum {} + +powwow:/home/makhoul# find . -name Fusion.cc -ls + + +238d74aac45bec21460e151295598764 ./Desktop/A.Makhoul/DiffusOMNET/Fusion.cc +--- +5541828 8 -rw-r--r-- 1 makhoul and 6631 mai 14 2007 ./Desktop/A.Makhoul/DiffusOMNET/Fusion.cc +,---- +| void BRITENode::updateLoad(){ +| +| double deltaSum = 0.; +| double deltaMin = this->load; +| for (int i = 0; i < gateSize("out"); i++) { +| double delta1 = this->load - neighborsLoad[i]; +| if (delta1 > epsilonDelta) { +| delta[i] = delta1; +| deltaSum += delta1; +| if (deltaMin > delta1) +| deltaMin = delta1; +| } else +| delta[i] = 0; +| } +| double alpha = deltaMin / (deltaMin + deltaSum); +| for (int i = 0; i < gateSize("out"); i++) { +| double transfer = alpha * delta[i]; +| totalSend[i] += transfer; +| this->load -= transfer; +| +| } +| } +`---- + + +8f5c3e7c5358626bc06726d888d912af ./Desktop/A.Makhoul/Abdallah-Makhoul/Recherche/Diffus-OMNET/Fusion.cc +8f5c3e7c5358626bc06726d888d912af ./Desktop/AbdallahMakhoul/Recherche/Diffus-OMNET/Fusion.cc +--- +5540991 8 -rw-r--r-- 1 makhoul and 8001 juin 12 2007 ./Desktop/A.Makhoul/Abdallah-Makhoul/Recherche/Diffus-OMNET/Fusion.cc +6497742 8 -rw-r--r-- 1 makhoul and 8001 juin 12 2007 ./Desktop/AbdallahMakhoul/Recherche/Diffus-OMNET/Fusion.cc +,---- +| void BRITENode::updateLoad(){ +| +| double deltaSum = 0.; +| double deltaMin = this->load; +| for (int i = 0; i < gateSize("out"); i++) { +| double delta1 = this->load - neighborsLoad[i]; +| if (delta1 > epsilonDelta) { +| delta[i] = delta1; +| deltaSum += delta1; +| if (deltaMin > delta1) +| deltaMin = delta1; +| } else +| delta[i] = 0; +| } +| double alpha = deltaMin / (deltaMin + deltaSum); +| for (int i = 0; i < gateSize("out"); i++) { +| double transfer = alpha * delta[i]; +| totalSend[i] += transfer; +| this->load -= transfer; +| +| } +| } +`---- + + +d0b4ef1a4553ff1c9c408390818cf925 ./FusionOmnet/Fusion.cc +--- +5516053 12 -rw-r--r-- 1 makhoul and 9732 juil. 13 2007 ./FusionOmnet/Fusion.cc +,---- +| void BRITENode::updateLoad(){ +| totalSent = 0.; +| const double alpha = 1.0 / (gateSize("out") + 1); +| const double epsilon = 1.0e-4; +| +| int nDelta = 0; +| for (int i = 0; i < gateSize("out"); i++) { +| double d = this->load - neighborsLoad[i]; +| if (d > epsilon) { +| Delta[nDelta].delta = d; +| Delta[nDelta].index = i; +| nDelta++; +| } +| } +| +| std::sort(Delta, Delta + nDelta, DeltaCompDec()); +| +| double neighborLoadMax = 0.0; // maximum load of neighbors to which +| // something has been sent +| for (int i = 0; i < nDelta; i++) { +| int index = Delta[i].index; +| double delta = this->load - neighborsLoad[index]; +| if (delta <= epsilon) +| break; +| +| #if 0 +| delta = Delta[i].delta; // does not work well... +| #endif +| +| double transfer = alpha * delta; +| double transferMax = +| std::min(this->load - neighborLoadMax, +| (this->load - neighborsLoad[index]) / 2.0); +| +| if (transfer > transferMax) // ping-pong violated? +| transfer = transferMax; +| +| totalSend[index] += transfer; +| this->load -= transfer; +| +| double newNeighborLoad = neighborsLoad[index] + transfer; +| if (newNeighborLoad > neighborLoadMax) +| neighborLoadMax = newNeighborLoad; +| } +| +| // double transfer = alpha * Delta[i].delta; +| // if((this->load - totalSent) >= neighborsLoad[Delta[i].index] + transfer) +| // break; +| // else { +| // totalSend[i] += transfer; +| // this->load -= transfer; +| // totalSent+=transfer; +| // } +| // } +| +| // double deltaMax = 1.0e-3; // we consider only positive deltas +| // int iMax = -1; // invalid value +| // for (int i = 0; i < gateSize("out"); i++) { +| // Delta[i].delta = this->load - neighborsLoad[i]; +| // if (Delta[i].delta > deltaMax) { +| // deltaMax = Delta[i].delta; +| // iMax = Delta[i].index; +| // } +| // } +| +| // if (iMax != -1) { +| // double transfer = alpha * Delta[iMax].delta; +| // totalSend[iMax] += transfer; +| // this->load -= transfer; +| // } +| } +`---- + + +69f9baf76eb24e0e6cfa539d21c9b6f6 ./Bureau/Fusion.cc +69f9baf76eb24e0e6cfa539d21c9b6f6 ./Bureau/Simulations-Fusion-Omnet/Fusion.cc +69f9baf76eb24e0e6cfa539d21c9b6f6 ./Desktop/A.Makhoul/Abdallah-Makhoul/Recherche/Simulations-Fusion-Omnet/Fusion.cc +69f9baf76eb24e0e6cfa539d21c9b6f6 ./Desktop/AbdallahMakhoul/Recherche/Simulations-Fusion-Omnet/Fusion.cc +69f9baf76eb24e0e6cfa539d21c9b6f6 ./Simulations-Fusion-Omnet/Fusion.cc +--- +5516032 12 -rw-r--r-- 1 makhoul and 11160 nov. 7 2008 ./Bureau/Fusion.cc +5524854 12 -rw-r--r-- 1 makhoul and 11160 nov. 7 2008 ./Bureau/Simulations-Fusion-Omnet/Fusion.cc +5541114 12 -rw-r--r-- 1 makhoul and 11160 nov. 28 2007 ./Desktop/A.Makhoul/Abdallah-Makhoul/Recherche/Simulations-Fusion-Omnet/Fusion.cc +6497957 12 -rw-r--r-- 1 makhoul and 11160 nov. 28 2007 ./Desktop/AbdallahMakhoul/Recherche/Simulations-Fusion-Omnet/Fusion.cc +5516082 12 -rw-r--r-- 1 makhoul and 11160 nov. 7 2008 ./Simulations-Fusion-Omnet/Fusion.cc +,---- +| void BRITENode::updateLoad(){ +| totalSent = 0.; +| const double alpha = 1.0 / (gateSize("out") + 1); +| const double epsilon = par("erreur"); +| +| int nDelta = 0; +| for (int i = 0; i < gateSize("out"); i++) { +| double d = this->load - neighborsLoad[i]; +| if (d > epsilon) { +| Delta[nDelta].delta = d; +| Delta[nDelta].index = i; +| nDelta++; +| } +| } +| +| std::sort(Delta, Delta + nDelta, DeltaCompDec()); +| +| double neighborLoadMax = 0.0; // maximum load of neighbors to which +| // something has been sent +| for (int i = 0; i < nDelta; i++) { +| int index = Delta[i].index; +| double delta = this->load - neighborsLoad[index]; +| if (delta <= epsilon) +| break; +| +| #if 0 +| delta = Delta[i].delta; // does not work well... +| #endif +| +| double transfer = alpha * delta; +| double transferMax = +| std::min(this->load - neighborLoadMax, +| (this->load - neighborsLoad[index]) / 2.0); +| +| if (transfer > transferMax) // ping-pong violated? +| transfer = transferMax; +| +| totalSend[index] += transfer; +| this->load -= transfer; +| +| double newNeighborLoad = neighborsLoad[index] + transfer; +| if (newNeighborLoad > neighborLoadMax) +| neighborLoadMax = newNeighborLoad; +| } +| +| // double transfer = alpha * Delta[i].delta; +| // if((this->load - totalSent) >= neighborsLoad[Delta[i].index] + transfer) +| // break; +| // else { +| // totalSend[i] += transfer; +| // this->load -= transfer; +| // totalSent+=transfer; +| // } +| // } +| +| // double deltaMax = 1.0e-3; // we consider only positive deltas +| // int iMax = -1; // invalid value +| // for (int i = 0; i < gateSize("out"); i++) { +| // Delta[i].delta = this->load - neighborsLoad[i]; +| // if (Delta[i].delta > deltaMax) { +| // deltaMax = Delta[i].delta; +| // iMax = Delta[i].index; +| // } +| // } +| +| // if (iMax != -1) { +| // double transfer = alpha * Delta[iMax].delta; +| // totalSend[iMax] += transfer; +| // this->load -= transfer; +| // } +| } +`---- -- 2.39.5