近期再写一个网络仿真器，里面參考了Max-MinFairness算法，这是一种比較理想、公平的带宽分配算法。其思路主要例如以下：首先是算法的准备，考察某一时刻的网络中全部的flow，因为每条flow都有其各个link，因此能够得到各个link上全部流经的flow，然后開始迭代，各个link都把capacity平均分给全部流经的flow，接着每条flow的速度就等于其最小link分配的带宽，然后每条link的剩余带宽就等于link的capacity减去全部流经的flow的速度的总和，再然后把link的剩余带宽作为capacity又一次进行上面的迭代，直至全部flow在迭代中获得的带宽都小于一个阈值时，算法结束，带宽分配完毕。
让我们来分析这个算法并考虑怎样加速该算法的运行速度。首先，对于一些bottleneck的link，流经其的flow早早就不能分配带宽了，因此假设发如今某个迭代中某条link可以分配的带宽已经小于阈值，那么在下一轮迭代，全部流经其的flow都不再考察，即使某些flow并非以该link为bottleneck，因此，算法结束的条件可以改为当全部flow都不再考察的时候。这样对不正确呢，让我们分析一下。以该link为bottleneck的flow自然不用说了，所谓的bottleneck就是可以获取的带宽最小的link，那么最小的link已经不能分配带宽了，该flow自然不再考察。但不是以该link作为bottleneck的flow呢，它们有更小带宽的link，可是假设该link不是你的bottleneck，已经不能分配带宽了，那就刚不用说更小带宽的link了，所以这些flow也应该不再考察。好，算法的解说和分析就到这儿了，以下就是算法的实现，笔者採用的Java语言。
public Map<Integer, List<TrafficState>> run() {
Map<Integer, List<TrafficState>> resultMap = new HashMap<Integer, List<TrafficState>>();
int current = 0;
// PrintWriter resultWriter = new PrintWriter(resultFileName);
while (current < runtime) {
List<Integer> runningFlowList = new ArrayList<Integer>();
// the first traverse,add the new flows and remove the shopped flow
for (int i = 0; i < graph.traffics.size(); i++) {
Traffic currentTraffic = graph.traffics.get(i);
int starttime = currentTraffic.start;
if (starttime <= current && !currentTraffic.isStopped) {
List<Integer> linksList = currentTraffic.links;
if (currentTraffic.totlesize == 0) {
// start a new flow
currentTraffic.totlesize = currentTraffic.flowsize;
currentTraffic.leftsize = currentTraffic.totlesize;
for (Integer linkno : linksList) {
graph.links.get(linkno).trafficList
.add(currentTraffic);
}
}
// calculate the transfer bytes in a epoch
currentTraffic.epochsize = currentTraffic.speed
* ((float) period / 1000);
currentTraffic.leftsize -= currentTraffic.epochsize;
if (currentTraffic.leftsize <= 0
|| currentTraffic.end == current) {
// no more flowsize or time is up,stop it
currentTraffic.isStopped = true;
for (Integer linkno : linksList) {
graph.links.get(linkno).trafficList
.remove(currentTraffic);
}
} else
runningFlowList.add(i);
}
}
// print the measurement
if (printTimeSet.contains(current)) {
List<TrafficState> stateList = new ArrayList<TrafficState>();
for (Traffic traffic : graph.traffics) {
//not the stop flows and the start ones just now
if (!traffic.isStopped && traffic.totlesize != 0
&& traffic.speed != 0) {
TrafficState state = new TrafficState();
state.setBytes(traffic.epochsize);
state.setDestination(traffic.destination);
state.setSource(traffic.source);
state.setThruput(traffic.speed);
String pathString = traffic.source;
int lastNode = Integer.parseInt(traffic.source);
for (Integer linkno : traffic.links) {
if (lastNode == graph.links.get(linkno).source) {
pathString += ","
+ graph.links.get(linkno).target;
lastNode = graph.links.get(linkno).target;
} else {
pathString += ","
+ graph.links.get(linkno).source;
lastNode = graph.links.get(linkno).source;
}
// pathString += "," +
// graph.links.get(linkno).target;
}
state.setPathString(pathString);
state.setStarttime(traffic.start);
state.setFlowsize(traffic.flowsize);
state.setEndtime(traffic.end);
stateList.add(state);
}
}
resultMap.put(current, stateList);
}
// initialize all the links and traffics
for (Link link : graph.links) {
link.leftCapacity = link.capacity;
}
for (Traffic traffic : graph.traffics) {
traffic.speed = 0;
}
Set<Integer> finishedTrafficSet = new HashSet<Integer>();
// the second traverse,set the throughput of each flow in next
// iteration
while (finishedTrafficSet.size() < runningFlowList.size()) {
for (int i = 0; i < runningFlowList.size(); i++) {
if (!finishedTrafficSet.contains(runningFlowList.get(i))) {
Traffic currentTraffic = graph.traffics
.get(runningFlowList.get(i));
currentTraffic.increSpeed = Float.MAX_VALUE;
Link minLink = null;
for (Integer linkno : currentTraffic.links) {
Link currentLink = graph.links.get(linkno);
int existFlowNum = 0;// the number of exist flows
for (Traffic traffic : currentLink.trafficList) {
if (traffic.increSpeed != 0
|| traffic.speed == 0) {
existFlowNum++;
}
}
float currentLinkSpeed = (float) currentLink.leftCapacity
/ (float) existFlowNum;
if (currentLinkSpeed < currentTraffic.increSpeed) {
currentTraffic.increSpeed = currentLinkSpeed;
minLink = currentLink;
}
}
if (currentTraffic.increSpeed > 5)
currentTraffic.speed += currentTraffic.increSpeed;
else {
currentTraffic.increSpeed = 0;
if (minLink != null) {
for (Traffic traffic : minLink.trafficList) {
traffic.increSpeed = 0;
finishedTrafficSet.add(graph.traffics
.indexOf(traffic));
}
} else
finishedTrafficSet.add(runningFlowList.get(i));
}
}
}
// link left capacity decrease the traffic increase throughput
for (Link link : graph.links) {
for (Traffic traffic : link.trafficList) {
link.leftCapacity -= traffic.increSpeed;
}
}
}
current += period;
}
// resultWriter.close();
return resultMap;
}