[go: up one dir, main page]

CN104836750B - 一种基于时间片轮转的数据中心网络流调度方法 - Google Patents

一种基于时间片轮转的数据中心网络流调度方法 Download PDF

Info

Publication number
CN104836750B
CN104836750B CN201510222086.7A CN201510222086A CN104836750B CN 104836750 B CN104836750 B CN 104836750B CN 201510222086 A CN201510222086 A CN 201510222086A CN 104836750 B CN104836750 B CN 104836750B
Authority
CN
China
Prior art keywords
flow
sdn switch
priority queue
data
low
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Active
Application number
CN201510222086.7A
Other languages
English (en)
Other versions
CN104836750A (zh
Inventor
李克秋
盛佩
齐恒
李文信
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Dalian University of Technology
Original Assignee
Dalian University of Technology
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Dalian University of Technology filed Critical Dalian University of Technology
Priority to CN201510222086.7A priority Critical patent/CN104836750B/zh
Publication of CN104836750A publication Critical patent/CN104836750A/zh
Application granted granted Critical
Publication of CN104836750B publication Critical patent/CN104836750B/zh
Active legal-status Critical Current
Anticipated expiration legal-status Critical

Links

Landscapes

  • Data Exchanges In Wide-Area Networks (AREA)

Abstract

本发明公开了一种基于时间片轮转的数据中心网络流调度方法，属于数据中心网络领域。该方法利用SDN技术，在具有冗余链路的数据中心网络中，综合考虑长流和短流的分布情况，动态地控制网络中流的转发，并能根据网络中流的大小，动态调整流在SDN交换机中的排队情况。本发明可实现数据流在数据中心网络中的负载均衡，并降低短流在互联网络中的延迟。

Description

一种基于时间片轮转的数据中心网络流调度方法
技术领域
本发明涉及一种基于时间片轮转的数据中心网络流调度方法，属于数据中心网络领域。
背景技术
数据中心作为高收益在线服务(web搜索，社交网络，广告系统和推荐系统)的关键基础设施，其网络性能越来越受到人们的关注。这些应用对数据中心网络产生了低延迟的需求。用户体验受应用响应速度的影响很大，甚至几百毫秒的延迟都能显著降低用户体验。例如，亚马逊发现延迟每增加100ms就会造成收入下降一个百分点。
web搜索应用是数据中心中的一种典型应用，其遵循partition-aggregate工作模式。在该工作模式下，不同设备具有不同的角色。它们分别为top-level aggregators(TLAs)、mid-level aggregators(MLAs)和工作节点。TLAs接收请求并将完成请求所需的计算分成几部分交给各个MLA。MLA继续将计算分成适当的规模交给各个工作节点。各个工作节点并行地执行具体的计算并将结果返回给MLA，每个MLA将接收到的结果合并后转发给相应的TLA。这种工作模式会导致数据中心网络中同时产生短数据流和长数据流。这种短数据流主要由不同层(level)的aggregators，或者是MLAs与工作节点的交互而产生。长数据流主要由工作节点执行大规模的后台并行计算而造成。对于交互式应用来说，减少短数据流的完成时间可以显著提高这种交互式应用的响应时间，但是这并不意味着可以完全的忽略由后台计算产生的长数据流。换句话说，这种由后台计算而产生的长数据流只需要得到一定的资源将所有的数据量传输完就可以，是对吞吐率敏感的流，而这种短数据流是对延迟敏感的。当延迟不敏感的长数据流和延迟敏感的短数据流共享相同的队列时，短数据流会因队列中长数据流的累积而经历较长的时延。同时，典型的流调度算法ECMP并未很好的解决网络拥塞问题，一旦链路发生拥塞又会进一步加重网络的延迟，从而造成短数据流迟迟不能完成。为了改善网络性能，一种高效的调度算法需要在不显著降低长数据流的传输性能的同时保证短数据流的延迟需求。
发明内容
为了达到这个目的，本发明提供了一种基于SDN且同时考虑长数据流和短数据流的网络流调度方法。首先，为了充分利用网络中的冗余线路，通过动态选路的方法均衡分配网络中的数据流，从而避免拥塞。其次，为减小短数据流的传输延迟，在交换设备中的出端口处配置两个具有不同优先级的FIFO队列，高优先级队列中存放短数据流的数据包，低优先级的队列中存放长数据流的数据包，使得短数据流优先长数据流发送，从而降低短数据流的延迟。
本发明采取的技术方案如下：
(1)采用支持OpenFlow协议的SDN交换机来构建互联网络。
(2)利用OpenFlow协议获取交换机间的链路使用情况，控制器通过向支持OpenFlow协议的SDN交换机发送ofp_port_stats_request消息来获取交换机间的链路信息。具体步骤如下：
a.每隔一定的时间间隔T1，控制器向网络中所有SDN交换机发送一次ofp_port_stats_request消息，并等待SDN交换机响应；
b.控制器收到ofp_port_stats的响应消息后触发PortStatsReceived事件，通过调用事件处理函数获取到目前为止该端口传输的总字节数；
c.计算当前传输总字节数与上次收集的传输总字节数的差值并除以时间间隔T1，该值可近似看作该端口当前所占带宽。
d.将计算得到的带宽值存储在结构{dpid,port,bandwidth}中，其中bandwidth既为端口的传输带宽。
(3)动态选路策略
利用网络中的冗余路径来减小网络拥塞的可能性，具体步骤如下：
a.当控制收到openflow交换机发送的packet-in消息后，触发PACKETIN事件，通过调用事件处理函数，控制器将流的标识<srcip,dstip,srcport,dstport,proto>解析出，并记录下来；
b.利用(2)中得到的不同链路的带宽使用情况，选取带宽利用率最低的那条链路作为数据流的转发路径；
c.将所选择的路径添加到相应SDN交换机的流表中，并通知交换机转发该流。
(4)利用OpenFlow协议获取各个流的已传输字节数，控制器通过向支持OpenFlow协议的SDN交换机发送ofp_flow_stats_request消息来获取各个流的已传输字节数。具体步骤如下：
a.每隔一定的时间间隔T2，控制器向网络中所有SDN交换机发送一次ofp_flow_stats_request消息，并等待SDN交换机响应；
b.控制器收到ofp_flow_stats的响应消息后触发FlowStatsReceived事件，通过调用事件处理函数获取流的已传输总字节数；
c.将流的已传输总字节数存储在结构<srcip,dstip,srcport,dstport,proto,transmitted>中，其中transmitted为已传输总字节数。
(5)队列调度策略
在不显著降低低优先级数据流输出性能的情况下，显著降低高优先级数据流的传输时延。具体步骤如下：
a.在交换设备的输出端口处设置两个具有不同优先级的队列，交换设备按时间片T3调度输出这两个队列内的数据；
b.交换设备优先将高优先级队列中的数据出队输出；
c.若在一个时间片内的某一时刻高优先级队列为空则转去调度低优先级队列，并标记该时间片已调度过低优先级队列，直到时间片用完；
d.若在一个时间片内高优先级队列始终不为空，则不调度低优先级队列，直到时间片用完；
e.当某一时间片用完时，检测是否连续两个时间片未调度低优先级队列，若是则下一个时间片转去调度低优先级队列，并标记已调度过低优先级队列，转步骤b；
f.若不是则转去步骤b。
(6)网络数据包入队策略，具体步骤如下：
a.初始时所有流都在高优先级队列中排队等待输出；
b.当(4)中发现某一个流的已传输字节数达到了某一个阈值，这个流将被视为一个长数据流；
c.控制器向交换机发送ofp_flow_mod消息，在交换机的流表中增加一条流表项，match为该流的标识，而action则为一enqueue动作，通知交换机将长数据流排到低优先级队列中；
d.交换机在收到匹配的数据流时，将该数据流排在低优先级队列中；
e.交换机在输出端口处按(5)中的方法对两个队列进行调度。
本发明的数据中心网络流调度方法同时考虑了网络中长数据流和短数据流的调度，动态调度网络流以均衡各个链路的工作负载，同时本方法设计了一种QOS功能，优先输出短流，以减少短数据流的排队延迟，同时又不显著“惩罚”长流。
附图说明
图1是本发明的测试网络拓扑示意图。
图2是本发明的系统架构图。
图3是本发明数据流调度的流程图。
图4是本发明队列调度的流程图。
具体实施方式
以下结合附图说明和技术方案进一步说明本发明的具体实施方式。
如图1所示，利用支持OpenFlow协议的SDN交换机组成一个测试网络，网络中每条链路的带宽均为100Mbps，同时为SDN交换机的每个端口配置两个具有不同优先级的队列。默认情况下，流在高优先级队列中排队等待发送。
如图2所示，使用POX作为控制器，安装调度模块，运行两个定时任务以收集网络中所有链路的统计信息和所有存在的数据流的统计信息。
如图3所示，当图1中的主机H1向主机H2发送一条数据流f1时，若网络中的交换机无法转发该流，则向POX控制器报告，要求转发该流。POX收到请求后开始为f1计算转发路径。
根据网络的拓扑信息，可知H1、H2之间拥有四条等价路径，基于定时任务T1收集的链路使用信息，查找当前链路最空闲的路径分配给流f1，假设为H1-E1-A1-C1-A3-E2-H2。下发流表到交换机E1、A1、C1、A3、E2，并控制E1转发该流。
定时任务T2每隔T2时间收集一次流的已发送字节数。当某条流的已发送字节数超过一定阈值时，则POX控制器判断该数据流为大数据流。POX控制器向交换机发送ofp_flow_mod消息，在交换机的流表中增加一条流表项，match为该流的标识，而action则为一enqueue动作，通知交换机将长数据流排到低优先级队列中。当交换机收到后续的匹配数据流时，将该数据流排在低优先级队列中等待交换机调度输出。
如图4所示，交换机以T3时间为一周期调度输出端口队列中的数据，我们称一个周期为一个时间片。初始时设置标志Flag为1，启动T3定时器。定时器任务主要分三个部分：
1.在高优先级队列不为空的情况下，循环出队高优先级队列中的数据。
2.在调度高优先级队列过程中，发现高优先级队列为空则转去调度低优先级队列，直到定时器超时。
3.当连续两个时间片未调度低优先级队列时，则将下一个时间片分配给低优先级队列。

Claims (1)

1.一种基于时间片轮转的数据中心网络流调度方法，其特征在于:
(1)采用支持OpenFlow协议的SDN交换机来构建互联网络；
(2)利用OpenFlow协议获取SDN交换机间的链路使用情况，控制器通过向支持OpenFlow协议的SDN交换机发送ofp_port_stats_request消息来获取SDN交换机间的链路信息；具体步骤如下：
a.每隔一定的时间间隔T1，控制器向网络中所有SDN交换机发送一次ofp_port_stats_request消息，并等待SDN交换机响应；
b.控制器收到ofp_port_stats的响应消息后触发PortStatsReceived事件，通过调用事件处理函数获取到目前为止该端口传输的总字节数；
c.计算当前传输总字节数与上次收集的传输总字节数的差值并除以时间间隔T1，该值看作该端口当前所占带宽；
d.将计算得到的带宽值存储在结构{dpid,port,bandwidth}中，其中bandwidth即为端口的传输带宽；
(3)动态选路策略
a.当控制器收到支持openflow协议的SDN交换机发送的packet-in消息后，触发PACKETIN事件，通过调用事件处理函数，控制器将流的标识<srcip,dstip,srcport,dstport,proto>解析出，并记录下来；
b.利用(2)中得到的不同链路的带宽使用情况，选取带宽利用率最低的那条链路作为数据流的转发路径；
c.将所选择的路径添加到相应SDN交换机的流表中，并通知SDN交换机转发该流；
(4)利用OpenFlow协议获取各个流的已传输字节数，控制器通过向支持OpenFlow协议的SDN交换机发送ofp_flow_stats_request消息来获取各个流的 已传输字节数；具体步骤如下：
a.每隔一定的时间间隔T2，控制器向网络中所有SDN交换机发送一次ofp_flow_stats_request消息，并等待SDN交换机响应；
b.控制器收到ofp_flow_stats的响应消息后触发FlowStatsReceived事件，通过调用事件处理函数获取流的已传输总字节数；
c.将流的已传输总字节数存储在结构<srcip,dstip,srcport,dstport,proto,transmitted>中，其中transmitted为已传输总字节数；
(5)队列调度策略
在不显著降低低优先级数据流输出性能的情况下，显著降低高优先级数据流的传输时延；具体步骤如下：
a.在SDN交换机的输出端口处设置两个具有不同优先级的队列，SDN交换机按时间片T3调度输出这两个队列内的数据；
b. SDN交换机优先将高优先级队列中的数据出队输出；
c.若在一个时间片内的某一时刻高优先级队列为空则转去调度低优先级队列，并标记该时间片已调度过低优先级队列，直到时间片用完；
d.若在一个时间片内高优先级队列始终不为空，则不调度低优先级队列，直到时间片用完；
e.当某一时间片用完时，检测是否连续两个时间片未调度低优先级队列，若是则下一个时间片转去调度低优先级队列，并标记已调度过低优先级队列，转步骤b；
f.若检测不是连续两个时间片未调度低优先级队列，则转去步骤b；
(6)网络数据包入队策略
a.初始时所有流都在高优先级队列中排队等待输出；
b.当(4)中发现某一个流的已传输字节数达到了某一个阈值，这个流将被视为一个长数据流；
c.控制器向SDN交换机发送ofp_flow_mod消息，在SDN交换机的流表中增加一条流表项，match为该流的标识，而action则为一enqueue动作，通知SDN交换机将长数据流排到低优先级队列中；
d.SDN交换机在收到匹配的数据流时，将该数据流排在低优先级队列中；
e.SDN交换机在输出端口处按(5)中的方法对两个队列进行调度。
CN201510222086.7A 2015-05-04 2015-05-04 一种基于时间片轮转的数据中心网络流调度方法 Active CN104836750B (zh)

Priority Applications (1)

Application Number Priority Date Filing Date Title
CN201510222086.7A CN104836750B (zh) 2015-05-04 2015-05-04 一种基于时间片轮转的数据中心网络流调度方法

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
CN201510222086.7A CN104836750B (zh) 2015-05-04 2015-05-04 一种基于时间片轮转的数据中心网络流调度方法

Publications (2)

Publication Number Publication Date
CN104836750A CN104836750A (zh) 2015-08-12
CN104836750B true CN104836750B (zh) 2017-12-05

Family

ID=53814394

Family Applications (1)

Application Number Title Priority Date Filing Date
CN201510222086.7A Active CN104836750B (zh) 2015-05-04 2015-05-04 一种基于时间片轮转的数据中心网络流调度方法

Country Status (1)

Country Link
CN (1) CN104836750B (zh)

Families Citing this family (12)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN106911593B (zh) * 2015-12-23 2019-09-13 中国科学院沈阳自动化研究所 一种基于sdn架构的工业控制网络队列调度方法
CN107087280A (zh) * 2016-02-16 2017-08-22 中兴通讯股份有限公司 一种数据传输方法及装置
CN105827547B (zh) * 2016-03-10 2019-02-05 中国人民解放军理工大学 一种降低数据中心网络中流传输完成时间的流调度方法
CN107040605B (zh) * 2017-05-10 2020-05-01 安徽大学 基于sdn的云平台资源调度与管理系统及其应用方法
CN107332786B (zh) * 2017-06-16 2019-08-13 大连理工大学 一种在服务链环境下保障数据流截止时间的调度方法
CN107154897B (zh) * 2017-07-20 2019-08-13 中南大学 Dcn中基于包散射的异构流隔离方法
CN109861923B (zh) 2017-11-30 2022-05-17 华为技术有限公司 一种数据调度方法及tor交换机
CN108777697A (zh) * 2018-04-09 2018-11-09 中国电信股份有限公司上海分公司 一种减缓sdn交换机到控制器的网络冲击负荷的方法
CN108390820B (zh) 2018-04-13 2021-09-14 华为技术有限公司 负载均衡的方法、设备及系统
CN110191061A (zh) * 2019-05-07 2019-08-30 荆楚理工学院 一种基于sdn技术的校园网管理系统
CN110166372B (zh) * 2019-05-27 2022-04-19 中国科学技术大学 在基于光电路交换机的数据中心中的在线调度协流的方法
CN111580886A (zh) * 2020-05-11 2020-08-25 上海英方软件股份有限公司 一种通过时间片轮转加载大量数据的方法及装置

Citations (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN101179487A (zh) * 2006-11-10 2008-05-14 中兴通讯股份有限公司 一种计算机网络数据包转发的队列管理方法
CN101179486A (zh) * 2006-11-10 2008-05-14 中兴通讯股份有限公司 一种计算机网络数据包转发的car队列管理方法
CN101188547A (zh) * 2006-11-17 2008-05-28 中兴通讯股份有限公司 结合虚拟监控组和car速率限制提高转发效率的路由器
CN101193051A (zh) * 2006-11-20 2008-06-04 中兴通讯股份有限公司 采用虚拟监控组提高转发速度和效率的路由器

Family Cites Families (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US7142513B2 (en) * 2002-05-23 2006-11-28 Yea-Li Sun Method and multi-queue packet scheduling system for managing network packet traffic with minimum performance guarantees and maximum service rate control

Patent Citations (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN101179487A (zh) * 2006-11-10 2008-05-14 中兴通讯股份有限公司 一种计算机网络数据包转发的队列管理方法
CN101179486A (zh) * 2006-11-10 2008-05-14 中兴通讯股份有限公司 一种计算机网络数据包转发的car队列管理方法
CN101188547A (zh) * 2006-11-17 2008-05-28 中兴通讯股份有限公司 结合虚拟监控组和car速率限制提高转发效率的路由器
CN101193051A (zh) * 2006-11-20 2008-06-04 中兴通讯股份有限公司 采用虚拟监控组提高转发速度和效率的路由器

Also Published As

Publication number Publication date
CN104836750A (zh) 2015-08-12

Similar Documents

Publication Publication Date Title
CN104836750B (zh) 一种基于时间片轮转的数据中心网络流调度方法
US20220200923A1 (en) Dynamic buffer management in data-driven intelligent network
CN101478483B (zh) 交换设备内实现分组调度的方法及交换设备
US6654374B1 (en) Method and apparatus to reduce Jitter in packet switched networks
US6714517B1 (en) Method and apparatus for interconnection of packet switches with guaranteed bandwidth
Hafeez et al. Detection and mitigation of congestion in SDN enabled data center networks: A survey
CN113438163B (zh) 一种基于路径隔离的数据中心网络混合流路由方法及系统
CN106533960A (zh) 一种基于Fat‑Tree结构的数据中心网络路由方法
CN108718283B (zh) 数据中心网络中集中式端网协调的tcp拥塞控制方法
CN103329490B (zh) 提高基于分组通信网络的数据传输质量的方法和通信网络
US8144588B1 (en) Scalable resource management in distributed environment
EP1810466A1 (en) Directional and priority based flow control between nodes
CN102752192B (zh) 基于SCTP的ForCES传输映射层的带宽分配方法
CN104767695B (zh) 一种数据中心中的任务级别的流调度方法
CN105490962A (zh) 一种基于OpenFlow网络的QoS管理方法
Imtiaz et al. Approaches to reduce the latency for high priority traffic in IEEE 802.1 AVB networks
CN106330710B (zh) 数据流调度方法及装置
CN115643220B (zh) 基于抖动时延的确定性业务传输方法和装置
Mliki et al. A comprehensive survey on carrier ethernet congestion management mechanism
Kaur et al. Core-stateless guaranteed throughput networks
JP5307745B2 (ja) トラヒック制御システムと方法およびプログラムならびに通信中継装置
CN114501544A (zh) 一种数据传输方法、装置和存储介质
TW200303670A (en) Inverse multiplexing of managed traffic flows over a multi-star network
Wadekar Enhanced ethernet for data center: Reliable, channelized and robust
KR101681613B1 (ko) 분산 병렬 데이터 전송 시스템에서 자원들을 스케줄링하기 위한 장치 및 그 방법

Legal Events

Date Code Title Description
C06 Publication
PB01 Publication
EXSB Decision made by sipo to initiate substantive examination
SE01 Entry into force of request for substantive examination
GR01 Patent grant
GR01 Patent grant