CMU算法求网络瓶颈链路
又到了工作总结的日子了，这一个月来主要的工作就是围绕着求网络瓶颈链路展开，这里的求瓶颈链路是指知道端到端的性能来预测中间哪一环链路是瓶颈。对于这一问题，目前有三种算法，第一个是比较当前边与所有相邻边速度，如果当前边最小，说明是瓶颈的可能性越大。第二个是求流过当前边所有流的速度的方差，方差越小，瓶颈的可能性越大。第三个是参考一篇论文的算法，叫做CMU，它的目的并不是求出整个网络的瓶颈链路，而是求某条path中的瓶颈链路。
它的主要思想是对于当前path的每一条链路，它是瓶颈的可能性公式如下：
BottleneckScore=1-共享该链路并速度大于当前path速度的1.5倍的其他path数量/共享该链路其他path数量
其实算法的思路很像生活的交通网络，不过我们并不是通过探针（摄像头）来获取每条路的性能状况，而是只知道由A地到B地，以及由C地到D地的速度，如果他们俩的速度相近，都发生堵塞了，那么很可能就是他们共享的那一段路发生拥塞了。如果速度相差很大，那他们共享那一段路就绝不可能是拥塞道路。
今天我们主要讲第三种算法CMU。讲算法之前，首先讲一下，我们算法输入是分为训练集和测试集，他们的格式都一样，每一行都有一个访问记录所经过的所有节点编号，以及该次记录的访问速度，以空格分隔。然后，我们的数据结构有Path、LInk，Path类保存一次访问的节点列表和速度，以及解析每行数据的方法。Link类保存链路的两个节点信息以及经过它并且确认它的Bottleneck（瓶颈链路）的记录的速度列表。好了，准备工作都做好了，开始启动算法了。
我们需要两个数据结构保存读取的内容：
List<Path> pathList = new ArrayList<Path>();// 保存所有path
Map<Link, List<Integer>> allLinkMap = new HashMap<Link, List<Integer>>();// 保存所有出现过的link第一个就不多说了，第二个hashmap的key是link，这就意味着我们需要重写link的hashcode和equals方法，然后value的所有经过该link的path序号列表。
读取完数据后，开始进行算法计算了，具体代码如下：
private static Map<Integer, Bottleneck> findBottleneckSpeedUpgrade(
List<Path> pathList, Map<Link, List<Integer>> allLinkMap,
Set<Link> linkSet) {
// 保存每条path的bottleneck
Map<Integer, Bottleneck> pathBottleNeckMap = new HashMap<Integer, Bottleneck>();
for (Link link : allLinkMap.keySet()) {
List<Integer> linkPathList = allLinkMap.get(link);
if (linkPathList != null) {
for (Integer pathno : linkPathList) {
float currentBottleScore = calBottleNeckScore(link, pathno,
pathList, linkPathList);
if (pathBottleNeckMap.containsKey(pathno)) {
// 该path已经保存过，则比较当前link的bs与map里bottleneck的bs
if (currentBottleScore > pathBottleNeckMap.get(pathno)
.getBottleneckScore()) {
pathBottleNeckMap.get(pathno).setLink(link);
pathBottleNeckMap.get(pathno).setBottleneckScore(
currentBottleScore);
}
} else {
Bottleneck bottleneck = new Bottleneck();
bottleneck.setBottleneckScore(currentBottleScore);
bottleneck.setLink(link);
pathBottleNeckMap.put(pathno, bottleneck);
}
}
}
}
for (Integer pathno : pathBottleNeckMap.keySet()) {
Link currentLink = pathBottleNeckMap.get(pathno).getLink();
Path path = pathList.get(pathno);
LinkSpeed speed = new LinkSpeed(path.getNode(0), path.getNode(path
.getNodeList().size() - 1), path.getSpeed());
if (!linkSet.contains(currentLink)) {
currentLink.getSpeedList().add(speed);
linkSet.add(currentLink);
} else {
for (Link link : linkSet) {
if (link.equals(currentLink)) {
link.getSpeedList().add(speed);
}
}
}
}
return pathBottleNeckMap;
}参数说明：pathlist、allLinkMap就是第一步采集的，而linkSet是保存所有bottleneck的集合，返回的记录每条path的bottleneck，这里的Bottleneck类其实就是link对象加上一个bottleneckScore（也就是最开始讲的该link成为bottleneck的可能性）。这个方法里有两个for循环，第一个for循环是求出每条path的bottleneck，第二个for循环是把当前path的速度放入bottleneck的速度列表里，以便将来预测某条bottleneck的带宽，新加一条流经该bottleneck的path速度预测是多少。
这方法中用到了一个求链路bottleneck的方法：calBottleNeckScore，也就是算法的核心
/**
* 根据cmu算法算出一条link的bottleneckscore
*
* @param currentLink
* @param currentPath
* @param pathList
* @return
*/
public static float calBottleNeckScore(Link currentLink, int currentPathno,
List<Path> pathList, List<Integer> linkPathList) {
int exceedPathCount = 0, allPathCount = 0;
if (linkPathList != null) {
for (Integer pathno : linkPathList) {
if (currentPathno != pathno) {
allPathCount++;
if (pathList.get(currentPathno).getSpeed() * 1.5 < pathList
.get(pathno).getSpeed())
exceedPathCount++;
}
}
}
// for (Path path : pathList) {
// if (path != currentPath && path.containLink(currentLink)) {
// allPathCount++;
// if (path.getSpeed() > 1.5 * currentPath.getSpeed()) {
// exceedPathCount++;
// }
// }
// }
if (allPathCount == 0)
return 0;
return 1 - (float) exceedPathCount / (float) allPathCount;
}至此，算法大体完成，为了提高预测的准确度，你可以设计离散系数与bottleneck采样点个数的限制，例如离散系数要求小于1，采样点要求大于10，然后在测试阶段要求测试的记录所有链路都是训练时出现过的，测试的记录速度预测就是该path上所有bottleneck的最小速度，可以与真实的速度做个比较，求出算法误差率。
工作就总结到这儿了，整个项目代码地址：http://download.csdn.net/detail/xanxus46/7082781，希望对有兴趣的朋友有用。