可改良网络堵塞,多路径路由技术

新型网管系统Fastpass 可改善网络堵塞

麻省理工学院研究人员成功研制出一款名为Fastpass的新型网络管理系统,研究人员称Fastpass可减少网络出现大面积堵塞时的等待时间。麻省理工学院的研究团队将会在八月中旬召开的ACM数据通信专业组(ACM
Special Interest Group on Data Communication)会议上报告其研究结果。

图片 1

众所周知,在数据中心里,每当有人发出请求时,一些载有信息的数据包就会经过路由器从一个端口传送到另一个端口。而很多人同时发出请求时,这些数据包有可能会积压在路由器里,原因是路由器会将那些来不及处理的包存放在队列中等候处理。

图片 2

图中显示延迟减少(浅蓝:Fastpass,浅红:参考系统)

而Fastpass的系统核心就是一个被称之为“仲裁”(arbiter)的中央服务器。麻省理工学院研究人员表示,每当路由器或其他一些网络节点(如交换机或网桥等)收到用户请求需要发数据时,就会首先将请求发给“仲裁”。“仲裁”的角色有点像个管理所有网络节点和请求的监督员。由于“仲裁”知道网络系统的状况,所以可以根据一些可行的时隙分配和路径分配算法确定最佳的网络路径和发送数据的最佳时间,以防止数据包在网络内的积压。

摘录麻省理工学院研究文章的一段,从技术角度介绍了Fastpass系统:

端点与“仲裁”之间的通信采用Fastpass控制协议(FCP)。FCP协议属于可靠性协议,用于传达端点发给“仲裁”的请求以及将“仲裁”分配的时隙和路径传达给请求的发送者。FCP必须在相互冲突的要求之间找到平衡:包括尽量小地消耗网络带宽、实现低延迟和在不中断端点的通信的前提下处理数据包的丢失和“仲裁”失效的情况。FCP的可靠性采用超时和集中请求(Aggregate
demands)的ACK(确认)机制。端点将超过几微秒内的分配请求集中在一个数据包里发给“仲裁”。这样集中发请求数据包后可以降低请求的开销,继而有限度地降低在“仲裁”端的等待时间。——麻省理工学院

据悉,麻省理工学院研究团队在Facebook数据中心测试过Fastpass,结果发现路由器的平均队列长度减少了99.6%。即使在网络繁忙期间,使用Fastpass后也可以将发送请求与收到回应的时间从3.56(微秒)降到0.23微秒​​。

可改善网络堵塞
麻省理工学院研究人员成功研制出一款名为Fastpass的新型网络管理系统,研究人员称Fastpass可减少网络…

麻省理工学院研究人员成功研制出一款名为Fastpass的新型网络管理系统,研究人员称Fastpass可减少网络出现大面积堵塞时的等待时间。麻省理工学院的研究团队将会在八月中旬召开的ACM数据通信专业组(ACM
Special Interest Group on Data Communication)会议上报告其研究结果。

最近自己研究了下多路径路由技术,一来和一个项目相关,提前预热,为以后专业知识打基础,二来培养自己一个新领域快速学习和总结能力。

图片 3

目前网络中路由方案大多为单路径路由,基于给定限制寻找一条最优路径,只有该路径失效时才会重新计算或者选用备用路径,这种做法有以下三个不足:

众所周知,在数据中心里,每当有人发出请求时,一些载有信息的数据包就会经过路由器从一个端口传送到另一个端口。而很多人同时发出请求时,这些数据包有可能会积压在路由器里,原因是路由器会将那些来不及处理的包存放在队列中等候处理。

  • 大部分情况下其他多数路径都处于空闲状态,不能很好地利用网络资源
  • 当数据量较大时,容易造成网络拥塞
  • 不能很好实现业务驱动网络,由于业务对网络要求不同,如带宽、时延、丢包率等,但单路径路由不会进行区分服务。
    本文主要介绍一下两方面的内容,一是目前主流用到的多路径技术,包括ECMP、WCMP、OSPF-OMP,二是学术界比较有影响的多路径思路

图片 4

ECMP总结:

ECMP(等价多路径)是一种路由技术,实现将数据包在不同的路径上传输,原理相对简单,首先计算出网络中两个节点的最短路径,如果有多条等价最短路径,则进行负载均衡,这也是ECMP最大局限性所在,表现为:首先在一个网络中,等价最短路径限制太强,再者将流量平均分配到不同路径上没有考虑到网络实际能力,比如两条等价最短路径若带宽不对称,平均分配流量可能造成一条链路拥塞而另一条相对空闲。

图中显示延迟减少(浅蓝:Fastpass,浅红:参考系统)

ECMP具体实现过程

ECMP基于hash算法,主要包括以下步骤
1、
key值的生成。路由器选择数据包的一个头部字段(如源地址、目的地址等)通过hash算法得到一个键值key。
2、
查找hash表,看该键值落在哪个具体,该区域对应的下一跳就是该数据转发的下一个目的地。
假如说找到四条等价最短路径,即有四个下一跳可供选择,分配的表大小为keyspace.size,则每个下一跳负责的区域大小为

         regionsize = keyspace.size / #{nexthops}  

区域序号为:

         region = key / regionsize;

由此找出了对应的下一跳地址。
值得注意的是,ECMP只是实现了粗粒度的控制,每个流走的路径是一样的,不存在数据包重新排序问题,细粒度的负载均衡是基于数据包。值得进一步思考的是当端口失效或者新加一条通路时重排序问题。在文献[1]中有提到。ECMP原理在OSPF中使用。

而Fastpass的系统核心就是一个被称之为“仲裁”(arbiter)的中央服务器。麻省理工学院研究人员表示,每当路由器或其他一些网络节点(如交换机或网桥等)收到用户请求需要发数据时,就会首先将请求发给“仲裁”。“仲裁”的角色有点像个管理所有网络节点和请求的监督员。由于“仲裁”知道网络系统的状况,所以可以根据一些可行的时隙分配和路径分配算法确定最佳的网络路径和发送数据的最佳时间,以防止数据包在网络内的积压。

WCMP

Weighted Cost Multipathing
,为了解决数据中心流量负载均衡问题而提出[2],主要针对ECMP存在的问题进行了改善

图片 5

Paste_Image.png

如图,简单解释下,将数据从S10发送到S12,利用ECMP,即流量在各个出口链路上平均分配,但实际到S20有两条上行链路而到S12只有一条下行链路,导致S20,S21,S22下行数据不公平,不能很好利用资源。若在各个链路上采取
1:1:2:2分配,即WCMP原则,实现流量的平均分配。

摘录麻省理工学院研究文章的一段,从技术角度介绍了Fastpass系统:

WCMP实现原理

图片 6

Paste_Image.png

0-3为ECMP等价选路,4-15为WCMP按权重分配。

端点与“仲裁”之间的通信采用Fastpass控制协议(FCP)。FCP协议属于可靠性协议,用于传达端点发给“仲裁”的请求以及将“仲裁”分配的时隙和路径传达给请求的发送者。FCP必须在相互冲突的要求之间找到平衡:包括尽量小地消耗网络带宽、实现低延迟和在不中断端点的通信的前提下处理数据包的丢失和“仲裁”失效的情况。FCP的可靠性采用超时和集中请求(Aggregate
demands)的ACK(确认)机制。端点将超过几微秒内的分配请求集中在一个数据包里发给“仲裁”。这样集中发请求数据包后可以降低请求的开销,继而有限度地降低在“仲裁”端的等待时间。——麻省理工学院

multipath TCP

图片 7

Paste_Image.png

同时打开多个 TCP
会话,这种方式将数据分成多个部分,然后每个会话发送其中的部分。有效开放多个并行的
TCP 会话,为MulTCP,在一个 TCP 会话模拟多个并行的 TCP
会话的行为。这些行为为并行的 TCP
会话假设相同的端点几相同的端到端网络路径。一个使用多个并行会话的 TCP
进化,但试图通过网络以多种路径传输这些会话,这就是多路径 TCP。

参考文献:
[1] Hopps C E. Analysis of an equal-cost multi-path algorithm[J].

  1. [2] Zhou J, Tewari M, Zhu M, et al. WCMP: Weighted cost multipathing
    for improved fairness in data centers[C]//Proceedings of the Ninth
    European Conference on Computer Systems. ACM, 2014: 5.
    [3]
    https://www.oschina.net/translate/mptcp
    [4] He J, Rexford J. Toward internet-wide multipath routing[J]. IEEE
    network, 2008, 22(2).

据悉,麻省理工学院研究团队在Facebook数据中心测试过Fastpass,结果发现路由器的平均队列长度减少了99.6%。即使在网络繁忙期间,使用Fastpass后也可以将发送请求与收到回应的时间从3.56(微秒)降到0.23微秒​​。

【编辑推荐】

相关文章

Post Author: admin

发表评论

电子邮件地址不会被公开。 必填项已用*标注