Max-Min Fairness带宽分配算法

最近再写一个网络仿真器,里面参考了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;
	}

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏CDA数据分析师

工具 | Python数据结构:树的基本概念

树的例子 树(Tree)在计算机科学里应用广泛,包括操作系统,图形学,数据库和计算机网络。树和真正的树有许多相似的地方,也包括根、树枝和叶子,它们的不同在于计算...

20510
来自专栏数据科学学习手札

(数据科学学习手札06)Python在数据框操作上的总结(初级篇)

数据框(Dataframe)作为一种十分标准的数据结构,是数据分析中最常用的数据结构,在Python和R中各有对数据框的不同定义和操作。 Python 本文涉及...

6185
来自专栏苦逼的码农

【算法实战】生成窗口最大值数组

做算法题了,题的难度我们分为“士,尉,校,将”四个等级。这个算法题的模块是篇幅比较小的那种模块。首先是给出一道题的描述,之后我会用我的想法来做这道题,今天算是算...

1102
来自专栏机器之心

业界 | 谷歌开源DeepLearn.js:可实现硬件加速的机器学习JavaScript库

选自GitHub 机器之心编译 参与:蒋思源、路雪 deeplearn.js 是一个可用于机器智能并加速 WebGL 的开源 JavaScript 库。de...

3668
来自专栏青玉伏案

iOS开发之Masonry框架源码解析

Masonry是iOS在控件布局中经常使用的一个轻量级框架,Masonry让NSLayoutConstraint使用起来更为简洁。Masonry简化了NSLay...

2068
来自专栏AI科技大本营的专栏

入门 | 海量数据处理算法总结【超详解】

作者 | Angel_Kitty ➤1. Bloom Filter 【Bloom Filter】 Bloom Filter(BF)是一种空间效率很高的随机数据...

4219
来自专栏PPV课数据科学社区

Pandas速查卡-Python数据科学

Josh Devlin 2017年2月21日 Pandas可以说是数据科学最重要的Python包。 它不仅提供了很多方法和函数,使得处理数据更容易;而且它已经...

3887
来自专栏何俊林

如何学习OpenGL Shader开发?

shader也称着色器,着色器是运行在GPU上的小程序,着色器是一种C风格语言——GLSL。

2002
来自专栏机器学习实践二三事

Python-OpenCV(5)

这次咱们比较下,python的函数、numpy的函数和OpenCV的函数的效率问题,让大家对功能相同的情况下如何选择合适的函数有比较直观的认识 程序(语句)运行...

2117
来自专栏潇涧技术专栏

Python Algorithms - C2 The basics

本节主要介绍了三个内容:算法渐近运行时间的表示方法、六条算法性能评估的经验以及Python中树和图的实现方式。

1032

扫码关注云+社区