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,希望对有兴趣的朋友有用。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏大数据挖掘DT机器学习

从互联网巨头数据挖掘类招聘笔试题目看我们还差多少

1 从阿里数据分析师笔试看职业要求 以下试题是来自阿里巴巴招募实习生的一次笔试题,从笔试题的几个要求我们一起来看看数据分析的职业要求。 一、异常值是指什么?请列...

39670
来自专栏机器之心

令人困惑的TensorFlow!

我叫 Jacob,是 Google AI Resident 项目的研究学者。我是在 2017 年夏天加入该项目的,尽管已经拥有了丰富的编程经验,并且对机器学习的...

15830
来自专栏程序员叨叨叨

8.3 入口函数

通常高级语言程序中只有一个入口函数,不过由于着色程序分为顶点程序和片断程序,两者对应着图形流水线上的不同阶段,所以这两个程序都各有一个入口函数。

18440
来自专栏大数据文摘

你的数据科学python编程能力过关吗?看看这40道题你能得几分

17430
来自专栏swag code

编程:判断一个数是否是奇数?(93.7%的人会写错)

看似是对的,但是每执行四次(四分之一错误)便会有一个错误的结果(用数据说话)。考虑到负奇数的情况,它除以2的结果就不会是1。因此,返回值是false,而这样是不...

9640
来自专栏图形学与OpenGL

OpenGL开发库的详细介绍zz

开发基于OpenGL的应用程序,必须先了解OpenGL的库函数。它采用C语言风格,提供大量的函数来进行图形的处理和显示。OpenGL库函数的命名方式非常有规律...

32330
来自专栏阮一峰的网络日志

贝叶斯推断及其互联网应用(三):拼写检查

(这个系列的第一部分介绍了贝叶斯定理,第二部分介绍了如何过滤垃圾邮件,今天是第三部分。) 使用Google的时候,如果你拼错一个单词,它会提醒你正确的拼法。 比...

426120
来自专栏take time, save time

你所能用到的BMP格式介绍(一)

这些说明是我担任学校多媒体技术助教自己编写的实验说明,呕心沥血结合C++详细介绍BMP格式。  原理篇: 一、编码的意义。        让我们从一个简单的问题...

34370
来自专栏一心无二用,本人只专注于基础图像算法的实现与优化。

解析opencv中Box Filter的实现并提出进一步加速的方案(源码共享)。

  说明:本文所有算法的涉及到的优化均指在PC上进行的,对于其他构架是否合适未知,请自行试验。       Box Filter,最经典的一种领域操作,在无数...

56270
来自专栏Golang语言社区

麻将游戏数据结构和AI算法

用休息时间零零散散写完了网络麻将游戏,感觉其中有不少值得记录的东西。 基础数据结构     数据结构确定决定了程序的开发难易程度,就像是游戏的骨架,对于电脑AI...

1.1K20

扫码关注云+社区

领取腾讯云代金券