最近再写一个网络仿真器,里面参考了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;
}
分享到:
相关推荐
图机器学习峰会-1-2 Fairness and Explainability in Graph Learning
图机器学习峰会-1-2 Fairness and Explainability in Graph Learning.pdf
ns-2中的dsdv算法源码,进行必要的配置就可把dsdv经编译加入到ns-2中。
进而,在满足最大最小公平(max-min fairness,MMF)准则的情况下,提出一种分布式能效最优算法(distributed EE maximization algorithm,DEMA)。仿真结果表明,所提算法较传统算法可以更好地兼顾系统的能效和吞吐...
FeICIC场景下保障能效的公平度最优化,涂思嘉,牛凯,本文主要研究了采用小区偏置和时域干扰协调技术的两层异构网络下的用户公平度及系统能量效率。分析异构网络下行性能,包括下行SIR
在仿真中,对以吞吐量最大化为目标的Maximal-Rate策略和考虑公平的Max-Min策略进行了对比,仿真结果表明,本算法有着与Maximal-Rate策略相当的吞吐量和比Max-Min策略更高的数据速率,因此本算法在效率和公平上作了很好的...
In particular, focusing on a typical NOMA scenario with two users, we optimize the power allocation strategies under both sum-rate maximization and max-min fairness criteria, where practical optical ...
The Transmission Control Protocol (TCP) has been extensively credited for the stability of the Internet.... However, the XCP equilibrium solves a constrained max-min fairness problem i
Amazon SageMaker的信用风险预测和可解释性 我们首先构建一个集成模型,该模型采用表格输入数据,并为每个模型和组合的集成结果产生多个预测结果。 输入功能包括请求者的财务信息(例如检查帐户状态,信用历史记录...
[文档WIP] 黑盒优化算法的Python实现。您可以在参考详细信息以及在的实现 安装 当前,您只能使用pip从源代码安装库: pip install https://github.com/hannanabdul55/seldonian-fairness/archive/master.zip 用法 ...
过度参数化的群体公平 仿真图 规范-贝塔 可训练的:最后一层 可训练的:所有层 1个 4 10
一种改进的用于LTE上行SC-FDMA系统的比例公平调度方案,陆兆新,,3GPP在过去的几年中开展了LTE系统的标准化工作。LTE上行系统采用峰均比较低的SC-FDMA作为多址接入方式。SC-FDMA有两种资源映射方式,L-FDMA
CFQ (Complete Fairness Queueing).
In data-intensive cluster computing platforms such as Hadoop YARN, efficiency and fairness are two important factors for system design and optimizations. Previous studies are either for efficiency or ...
建立公平的金融模型公平和偏见无疑是机器学习中的热门话题,因为它们对人们的生活产生了影响。 这在金融领域尤其重要,因为错误的决策会限制他们参与社会的能力。 我们研究如何定义公平以及法律如何定义公平。...
New efficient and practical v-fairness (t, n) multi-secret sharing schemes
AI公平我发现有关AI公平的笔记,参考资料和材料对我的研究很有帮助,并为我提供了帮助。阅读清单 博客文章: 博客文章: COMPAS与刑事司法 权衡和不可能的结果分类,校准,精度,召回率观测措施的固有局限性除了观察...