分组网络上的低抖动业务调度

摘要

一种数据业务调度方法，包括：使用网络控制器选择经过网络节点的多个流；基于所述多个流的流速和网络节点的链路容量生成增广图；使用增广图计算用于流的流调度以最小化流的延迟或延迟变化；以及输出流调度。一种数据业务调度方法，包括：使用网络控制器获得网络的网络拓扑；基于网络拓扑生成增广图；将增广图转换成混合整数线性规划；使用混合整数线性规划来调度网络中的流以最小化流的延迟或延迟变化；以及输出流调度。

说明书

相关申请的交叉引用

本申请要求以下申请的优先权权益：

由William McCormick等人于2015年3月10日提交的题为“Optimization forScheduling Low Traffic jitter on a Packet Network”的第62/130,901号美国临时专利申请；

由Peter Ashwood-Smith等人于2014年10月31日提交的题为“Systems andMethods for CPRI Communication Over a Packet Switched Network”的第62/073,132号美国临时专利申请；以及

由William McCormick等人于2015年10月16日提交的题为“Low Jitter TrafficScheduling on a Packet Network”的第14/885,362m号美国专利申请，上述申请中的每一个的内容以引用的方式并入本文中，如同全文复制一样。

背景技术

通用公共无线电接口(Common Public Radio Interface，CPRI)是通常部署在基站内部的接口。CPRI使得无线电设备和无线电设备控制之间能够进行通信。在一些应用中，期望在延迟敏感网络上设置CPRI，使得无线电设备可以保持在远程站点处而无线电设备控制位于数据中心。每个CPRI流是具有恒定的源和目的地的恒定比特率流。CPRI流可以在添加或移除基站时被添加或移除。因此，它们是相对静态的，通常不会在当前的第三代和第四代无线网络中频繁改变。

CPRI具有几纳秒的严格抖动要求。在现有应用中，通过在接收器处对业务进行缓冲来处理抖动。当使用接收器缓冲时，缓冲器的大小需要被设计成保证抖动要求，其中抖动要求可以取决于前传网络的特性。接收器缓冲将延迟引入到CPRI流中。这种延迟被考虑在CPRI延迟预算中，这可能会减少前传网络中容许的传播延迟。通过用掉CPRI延迟预算的一部分来考虑接收器缓冲，无线电设备控制器的覆盖区域可能存在抵消减小。其他方法是基于将用光网络用于前传网络。然而，在某些情况下，创建光网络可能并不实际。另一种方法是基于使用以太网网络来承载CPRI业务。然而，在使用以太网网络设备创建专用点对点连接之外，以太网网络通常不能保证CPRI部署的低抖动要求。

发明内容

在一个实施方式中，本公开内容包括一种数据业务调度方法，该数据业务调度方法包括：使用网络控制器选择经过网络节点的多个流；使用网络控制器基于所述多个流的流速和网络节点的链路容量来生成增广图；响应于向所述多个流添加新的流的请求，使用网络控制器更新增广图；使用网络控制器基于更新后的增广图来确定使所述多个流的延迟或延迟变化最小化的针对新的流的流调度；以及使用网络控制器输出针对所述新的流的流调度。

在另一实施方式中，本公开内容包括一种装置，该装置包括被配置成获得网络拓扑的接收器和在操作上耦接至接收器的处理器，所述处理器被配置成：根据网络拓扑选择经过网络节点的流；基于流的流速和网络节点的链路容量生成增广图；使用增广图计算用于流的流调度以最小化流的延迟或延迟变化；以及输出流调度。

在又一实施方式中，本公开内容包括一种数据业务调度方法，该数据业务调度方法包括：使用网络控制器获得网络的网络拓扑；使用网络控制器基于网络拓扑来生成增广图；使用网络控制器将增广图转换成混合整数线性规划；使用网络控制器用混合整数线性规划来调度网络中的流以最小化流的延迟或延迟变化；以及使用网络控制器输出流调度。

根据下面结合附图和权利要求书进行的详细描述，将会更清楚地理解这些和其他特征。

附图说明

为了更透彻地理解本公开内容，现在参考下文结合附图和具体实施方式进行的简要描述，其中，相同的附图标记表示相同的部分。

图1是实施方式的网络通信系统的图示。

图2是实施方式的网络控制器的图示。

图3是实施方式的网络元件的图示。

图4是灵活时隙调度的时序图。

图5是网络节点配置的模型。

图6是实施方式的增广图的被配置成具有节点内网状互连的部分的图示。

图7是实施方式的增广图的被配置成具有节点内链的部分的图示。

图8是实施方式的可以被实现为增广图的网络的图示。

图9是实施方式的增广图的图示。

图10是实施方式的用于增广图的调度方法的流程图。

图11是实施方式的可用于增广图中的流调度的数据模型的图示。

图12是实施方式的线性规划结构的图示。

图13是实施方式的用于增广图的数据业务调度方法的流程图。

具体实施方式

首先应该理解，尽管下文提供了一个或更多个实施方式的说明性实现，但所公开的系统和/或方法可以使用任何数量的技术来实现，而无论该技术是否是当前已知或现有的。本公开内容决不应限于包括本文所说明并描述的示例性设计和实现的下文所说明的说明性实现、附图和技术，而是可以在所附权利要求书的范围以及其等同物的全部范围内进行修改。

本文所公开的是用于时间敏感网络如电气和电子工程师协会(Institute ofElectrical and Electronics Engineers，IEEE)802.1Qbv时间敏感网络上的业务工程的各种实施方式。业务工程可以包括生成网络的增广图(augmented graph)并且使用所生成的增广图来调度数据业务。可以对网络进行建模以构造用于全局调度的增广图。增广图被配置成对与传输周期相关联的多个时隙进行建模以及获取网络拓扑、网络资源可用性、链路传输延迟和节点切换延迟。增广图还被配置成使得能够在考虑带宽和延迟的情况下路由对网络的接入。

题为“Bridges and Bridged Networks-Amendment:Enhancements forScheduled Traffic”的IEEE 802.1Qbv规定了以太网交换机中的时间感知队列排出过程，其可以用于严格控制网络中的延迟和抖动。在最初于2012年6月公布的题为“Bridges andBridged Networks-Amendment：Enhancements for Scheduled Traffic”的IEEE标准草案中描述了关于IEEE 802.11Qbv网络的附加细节，该IEEE标准草案以引用的方式并入本文中，如同全文复制一样。该标准在交换机中使用门(例如，非常短的队列)的概念。交换机可以被编程有指定在特定时间将打开哪些门的调度。当门打开时，排队等该门的业务被许可进入交换机并且被转发至其目的地。与低速链路相比，高速链路被划分成更多的时隙，这与链路速度之比成比例。因此，在每秒10吉比特(Gbps)的链路可以具有4个时隙的情况下，针对相应的时间段，100Gbps链路将具有40个时隙并且400Gbps链路将具有160个时隙。

对于调度CPRI流的一般要求是使流上的延迟和抖动最小化。在常规以太网网络中，未经调度的流偶尔会在汇聚节点处发生冲突并引入抖动。数据业务调度优化程序的潜在目的则是使网络中的任何流的最大延迟最小化。然而，网络中的所有CPRI流可能不能被一次添加，而是会被递增地添加。一旦已经建立了流，则可能不能接受对流进行重定位，因为这将导致延迟或中断。在一次一个地将流置于网络中的情况下(或者将流引入到具有现有业务的网络的情况下)，可以使用递增数据业务调度算法。一次一个地建立流意味着优化目的将是使被给定至现有流调度的当前流的延迟最小化。

可能还期望类似于时分复用(time-division multiplexing，TDM)网络将网络划分成时隙。与TDM系统不同，提供了时隙大小配置的灵活性并且可以选择适合该问题的时隙大小。CPRI流速通常被限制为每秒614.4兆比特(Mbps)、1228.8Mbps和2457.6Mbps中之一。便利地，这些速率是最慢速率的整数倍。这样，以太网链路可以被划分成可以适应不同传输速率的时隙。使用固定分组大小给出了为整数倍的分组传输速率。

图1是实施方式的网络通信系统100的图示。网络通信系统100包括被互连以形成分组交换网络160的网络控制器110、主定时产生器120、数据源130、交换机140和数据宿150。网络通信系统100可以如图所示地进行配置或者如本领域的普通技术人员在阅读本公开内容后将会理解的任何其他合适配置进行配置。在一个实施方式中，网络控制器110是软件定义网络(software-defined network，SDN)控制器，其可以包括但不限于OpenDaylightSDN控制器和开放网络操作系统(Open Network Operating System，ONOS)SDN控制器。在另一个实施方式中，网络控制器110可以是非SDN网络控制器。网络控制器110被配置成针对分组交换网络160执行控制面功能和业务工程功能。例如，网络控制器110可以被配置成确定在分组交换网络160中传输的分组的最优路径以及调度网络通信系统100的网络节点(例如，数据源130和交换机140)处的分组的离开时间以使得用于在分组交换网络160上传输分组的延迟和抖动最小化。网络控制器110还可以被配置成执行其他控制面功能，包括但不限于对分组交换网络160的网络配置和网络监控。网络控制器110被配置成与网络通信系统100中的网络节点(例如，数据源130、交换机140和数据宿150)进行通信。例如，网络控制器110可以被配置成使用OpenFlow协议来与网络通信系统100中的网络节点进行通信。替选地，网络控制器110可以被配置成使用如本领域的普通技术人员在阅读本公开内容后将会理解的任何其他合适的通信协议来与网络通信系统100中的网络节点进行通信。主定时产生器120是主时钟或总控时钟。在IEEE 1588标准中描述了主定时产生器120的附加细节，该标准以引用的方式并入本文中，如同全文复制一样。尽管被图示为仅连接至数据宿150、交换机140和数据源130中的一些，但是应当理解，网络控制器110和主定时产生器120可以具有到网络100中的所有节点的在逻辑上的直接连接。

在图1所示的实施方式中，数据源130是无线电设备控制器，数据宿150是无线电设备。数据源130被配置成采用CPRI在分组交换网络160上与数据宿150中的至少一个进行通信。数据源130和数据宿150被配置成一起工作以提供服务于无线接入网络的一部分的无线电基站。交换机140被配置成连接分组交换网络160内的网络段以及在数据源130与数据宿150之间对分组进行路由。

图2是实施方式的网络控制器200的图示。网络控制器200被用在网络通信系统如图1中的网络通信系统100中。网络控制器200被配置成针对网络通信系统内的分组交换网络执行控制面功能和业务工程功能。网络控制器200可以被配置成使得其可以用作图1中的网络控制器110。

网络控制器200包括网络数据库202和调度器204。尽管在图2中未示出，但网络控制器200包括：存储网络数据库202的存储器；用于与分组交换网络中的节点(如分组交换网络160中的交换机140)互连的网络接口；以及至少一个处理器，该至少一个处理器与存储器和网络接口进行通信，用于处理指令以生成路径和调度以及将路径和调度提供至所互连的网络节点。网络数据库202填充有与网络的拓扑和操作特性有关的数据。例如，网络数据库202可以被配置成存储：标识网络中的网络节点(例如，图1中的数据源130、交换机140和数据宿150)的记录；用于互连网络节点的链路的标识符；指示每个链路的操作特性(例如，链路上的数据速率以及渡越时间或传输延迟)的记录；指示每个网络节点的操作特性(例如，每个数据源的数据速率、通过每个交换机的入站端口到出站端口的传输延迟以及每个交换机的吞吐量)的记录。

存储在网络数据库202中的至少一些数据可以在网络控制器200的初始化之前获得。网络数据库202可以随着网络的拓扑和操作特性的改变例如随着网络节点和链路的添加、移除、升级或故障而被更新。可以从网络节点或从连接至网络的专用监视器接收关于网络状况改变的更新。网络数据库202可以实时地或近似实时地被更新。

在部署后，调度器204与网络数据库202进行数据通信，并且被配置成生成在网络中传输的分组的路径以及调度在数据源处和在路径中的每个交换机处的分组的离开时间。离开调度表还可以标识要在每个数据源或交换机处使用的特定队列或端口。网络控制器200被配置成通过处理来自网络数据库202的记录来生成路径和调度，其中可以考虑网络的拓扑和操作特性，如每个网络节点处和通过每个链路的传输延迟。通过考虑网络特性，可以将路径和调度进行优化以使通过网络传输的每个分组的端到端的延迟和抖动最小化。例如，来自数据源或交换机的出站队列的分组传输可以被调度成在特定时隙中离开。时隙可以被选择成使得：当分组经过链路到达其目的地网络节点时，该分组可以由目的地网络节点立即在调度给该分组的时隙中转发。由此可以避免或使与等待可用时隙来转发分组相关联的延迟最小化。到达目的地网络节点的其他分组被调度成使得它们在前面的时隙或后面的时隙到达目的地网络节点。这样，其他分组可以在不用等待可用时隙的情况下被转发。以此方式，可以避免或使由于目的地节点处的多个到达分组争用传输资源而产生的延迟和抖动最小化。通过在数据源与数据宿之间的路径中的每个相继网络节点处调度时隙，分组可以在所调度的时隙中经过整个路径，使得可以避免或使端到端的延迟和抖动最小化。以此方式，CPRI业务的分组可以以符合CPRI要求的延迟和抖动通过网络进行传输。网络控制器200可以包括解算器或者可以被配置成与解算器交换数据。解算器的示例包括但不限于IBMILOG CPLEX优化器。

网络控制器200被配置成将所生成的路径和调度的至少一部分传输至数据源和交换机中的每一个以用于实现。例如，网络控制器200可以被配置成生成或输出可以被编程到网络内的网络节点上的调度(例如，调度文件)。数据源和交换机中的每一个可以被同步至公共时钟(例如，图1中的主定时产生器120)，这使得传输调度能够精确和准确地实现。网络控制器200可以响应于改变的网络拓扑或改变的操作特性来生成路径、更新先前确定的路径或更新调度。例如，当链路或网络节点被添加/移除时或者当数据源的数据速率改变时，网络控制器200可以生成或更新路径或调度。实际上，网络控制器200被配置为生成调度和路由规则，使得CPRI流中的分组沿着受控的路径被发送并且满足其调度。网络控制器200还可以周期性地生成或更新路径或调度。调度器204可以生成以下调度，该调度允许裕度或溢出以提供针对调度的任何偏差的容差，所述偏差例如为由数据源或交换机处的时钟误差而引起的偏差。在一个实施方式中，网络控制器200可以根据题为“Bridges and BridgedNetworks-Amendment：Enhancements for Scheduled Traffic”的IEEE 802.1Qbv的IEEE标准草案来生成和传输路由和调度数据。替选地，网络控制器200可以根据如本领域的普通技术人员在阅读本公开内容后将会理解的任何其他合适的协议来生成和传输路由和调度数据。

图3是实施方式的网络元件300的框图。网络元件300可以适于实现所公开的实施方式。网络元件300可以是通过网络、系统和/或域来传输或协助传输数据的任何装置(例如，MODEM、交换机、路由器、网桥、服务器、客户端、控制器等)。另外，网络元件300可以是本身不传输数据而是用作控制器的控制器。例如，网络元件300可以用于实现图1中的网络控制器110和图2中的网络控制器200。网络元件300包括端口310、收发器单元(Tx/Rx)320、处理器330和包括调度模块350的存储器340。端口310耦接至Tx/Rx 320，Tx/Rx 320可以是发送器、接收器或其组合。Tx/Rx 320可以经由端口310发送和接收数据。处理器330被配置成处理数据。存储器340被配置成存储用于实现本文所描述的实施方式的数据和指令。网络元件300还可以包括耦接至端口310和Tx/Rx 320的电光(electrical-to-optical，EO)部件和光电(optical-to-electrical，OE)部件，以用于接收和发送电信号和光信号。

处理器330可以通过硬件和软件来实现。处理器330可以被实现为一个或更多个中央处理单元(central processing unit，CPU)芯片、逻辑单元、核(例如，作为多核处理器)、现场可编程门阵列(field-programmable gate array，FPGA)、专用集成电路(applicationspecific integrated circuit，ASIC)和数字信号处理器(digital signal processor，DSP)。处理器330与端口310、Tx/Rx 320和存储器340进行通信。

存储器340包括磁盘、磁带驱动器或固态驱动器中的一个或更多个并且可以用作流上(over-flow)数据存储装置，以在程序被选择用于执行时存储这样的程序以及存储在程序执行期间被读取的指令和数据。存储器340可以是易失性的和非易失性的，并且可以是只读存储器(read-only memory，ROM)、随机存取存储器(random-access memory，RAM)、三元内容可寻址存储器(ternary content-addressable memory，TCAM)和静态随机存取存储器(static random-access memory，SRAM)。调度模块350通过处理器330实现以执行用于生成网络的增广图并且使用该增广图来调度网络的数据业务的指令。包括有调度模块350提供了对网络元件300的功能的改进。调度模块350还进行网络元件300到不同状态的转换。替选地，调度模块350被实现为在处理器330中存储的指令。

图4是灵活时隙调度的时序图400。每当分组准备好发送时，时隙应当是可用的，以消除或减少分组传输期间的抖动。图4示出了高CPRI分组速率402、中等CPRI分组速率404和低CPRI分组速率406。时隙408对应于最高传输速率，例如，时隙408可以具有2457.6Mbps的传输速率。帧410、412和414对应于最低传输速率。帧410包括高CPRI分组速率402的一个时隙408。帧412包括中等CPRI分组速率404的两个时隙408。帧414包括低CPRI分组速率406的四个时隙408。例如，帧414可以对应于614.4Mbps的传输速率。帧410、412和414中的时隙408的数量对应于最高数据速率与最低数据速率之比。可以根据以下因素得出时隙大小，所述因素包括但不限于流的比特率和网络中最慢链路的比特率。确定时隙大小可以包括：确定可用分组大小；挑选分组速率，该分组速率针对网络中最慢链路上的每个流类型给出每秒便利数目的分组；基于分组开销、抢占预算和时钟漂移预算，计算实际时隙大小；以及验证时隙大小足够大以足以承载期望分组大小。高CPRI分组速率402、中等CPRI分组速率404和低CPRI分组速率406可以被配置成具有如本领域普通技术人员在阅读本公开内容后将会理解的任何合适的帧大小。应当指出的是，如果网络足够快，则最高CPRI分组速率可能不会映射成每帧单个时隙。

作为示例，如果存在每秒2个、5个和7个分组的三种分组速率，则用于支持所有三种分组速率的帧将需要2×5×7＝70个时隙，以便构建用于不同的分组速率的无抖动调度。每帧时隙408的数量可以是不同分组速率的最小公倍数。在任意门假设的情况下，每帧大数量的时隙408可能不能很好地工作。例如，IEEE 802.1Qbv针对每个时隙408可能需要单独的队列，而每端口仅可用小数量的队列。在以太网帧中承载CPRI业务对时隙大小设定了界限，例如，时隙大小可以在50字节到1250字节之间。对于500字节即4000比特的分组大小，2457.6Mbps的比特率将需要每秒2457.6×10⁶/4000＝614400个分组，这对应于1627.6纳秒(nsec)的分组到达间隔时间。假设网络上的最慢链路速率是10Gbps，则1627.6纳秒的分组到达间隔时间使得能够支持最高达10×10⁹×1627.6＝16276比特(2034字节)的分组长度。时隙时间为1627.6纳秒，但在该时隙中传输500字节的数据。也可以提供时隙大小中的一些附加裕度。如果网络正在承载后台优先级业务，则可能需要启用IEEE802.1Qbv帧抢占，并且时隙可能需要包括足够的时间以允许交换机抢占低优先级帧。每个分组可以具有用于以太网以及用于需要被考虑的任何其他网络协议(例如，因特网协议(IP))分组报头的开销。还会存在一些开销以允许网络节点之间的例如纳秒量级的时钟漂移，其在10Gbps下转化成几十比特，而在100Gbps下转化成几百比特。

在由Peter Ashwood-Smith等人于2015年8月12日提交的第14/824,608号美国申请中描述了用于灵活时隙调度的附加信息，该美国申请以引用的方式并入本文中，如同全文复制一样。

图5是网络节点配置500的模型。网络节点配置500可以用于表示网络通信系统如图1中的网络通信系统100中的网络节点。网络节点配置500可以被建模为增广图的结合了时隙概念和时隙之间转换延迟概念的部分。网络节点配置500包括具有传入链路504和传出链路506的网络节点502。传入链路504被配置成用于10Gbps，传出链路506被配置成用于40Gbps。网络节点配置500可以如所示地进行配置或者以任何其他合适的配置进行配置。例如，传入链路504和/或传出链路506可以具有任何其他合适的分组速率。

图6是实施方式的增广图的被配置成具有节点内网状互连的部分600的图示。部分600被类似于图5中的网络节点配置500进行配置并且被配置成实现与图4中描述的灵活时隙调度类似的灵活时隙调度。部分600包括10Gbps的传入链路602和40Gbps的传出链路608。替选地，传入链路602和/或传出链路608可以具有任何其他合适的分组速率。基于用于计算灵活时隙的大小的计算，可以确定10Gbps的链路可以使用4个入向时隙604来承载帧650，并且40Gbps的链路可以使用16个出向时隙606来承载帧652。入向时隙604和出向时隙606还可以被称为增广图的顶点。较高速传出链路608上的提高的业务速率使得部分600能够在相同的帧时间内承载更多的出向时隙606。

使用部分600，可以使用最小延迟路径算法通过具有受控延迟特性的网络来构建路径。对于仅需要一个时隙的流，可以使用算法如Dijkstra算法来计算最小延迟路径。关于Dijkstra算法的附加细节在1959年6月11日出版的E.W.Dijkstra的“A Note on TwoProblems in Connexion with Graphs”中以及2008年出版的S.Skiena的“The AlgorithmDesign Manual”中有所描述，这两个文献以引用的方式合并在本文中，如同全文复制一样。替选地，可以使用其他算法如Bellman-Ford算法、A*搜索算法、Floyd-Warshall算法、Johnson算法或如本领域普通技术人员在阅读本公开内容后将会理解的任何其他合适的算法来计算最小延迟路径。用于计算最小延迟路径的算法的附加细节在1968年出版的P.E.Hart等人的“A Formal Basis for the Hueristic Determination of Minimum CostPaths”中、1962年出版的Robert W.Floyd的“Algorithm 97：Shortest Path”中以及1977年出版的Donald B.Johnson的“Efficient algorithms for shortest paths in sparsenetworks”中有所描述，这些文献全部以引用的方式并入本文中，如同全文复制一样。由于传输时间在网络中的每一步中被分配给每个流，所以最小延迟路径内在地是零抖动。需要多个时隙的流可能需要更复杂的路径计算和通过网络的多个路径。流可以是指业务流、单个分组、分组流或网络流，即从源到目的地的分组序列。路径是指流用来经过网络或经过网络的至少一部分的路线。流可以具有通过网络的多个路径。期望的是使跨每个路径的延迟相同。

在所有端口上的所有时隙之间使用逻辑链路610的全网状互连，将入向时隙604耦接至出向时隙606。逻辑链路610还可以被称为用于增广图的弧。每个入向时隙604连接至部分600上的每个出向时隙606。每个逻辑链路610可以被分配延迟(例如，传播延迟)，该延迟包含改变时隙时固有的延迟。延迟还可以包含部分600中的切换延迟。每个端口上的每个入向时隙604和出向时隙606变为部分600中的逻辑节点612或者与部分600中的逻辑节点612相关联。例如，如果部分600具有8个链路并且每个链路具有16个时隙，则需要构建总共8×16＝128个逻辑节点和(8×16)个时隙×每时隙(7×16)连接＝14,336个逻辑链路。

图7是实施方式的增广图的被配置成具有节点内链的部分700的图示。部分700被类似于图5中的网络节点配置500进行配置并且被配置成实现与图4中描述的灵活时隙调度类似的灵活时隙调度。部分700包括10Gbps传入链路702和40Gbps传出链路706。

在一个实施方式中，可以通过对增广图的被配置成具有节点内网状互连的部分如图6中的部分600应用最短路径算法来生成部分700。当将部分700的切换延迟视为常数时，全网状的逻辑链路(例如，来自图6的逻辑链路610)可以被替换为逻辑节点704A、704B、704C、704D、704E、704F、704G、704H、704I、704J、704K、704L、704M、704N、704P和704Q的链，它们可以被统称为逻辑节点704A-704Q。逻辑节点704A-704Q也可以被称为增广图的顶点。链中的逻辑节点704A-704Q由逻辑链路708连接，使得每个逻辑链路708具有表示节点中时隙到时隙改变时的传播延迟的延迟。逻辑链路708也可以被称为用于增广图的弧。链中的最后逻辑链路708连接回链的顶部以允许在持续时间上超过完整帧的延迟或允许来自前一传输周期的延迟。例如，链中的最后逻辑链路708从逻辑节点704Q连接至逻辑节点704A。部分700的切换延迟可以被合并到传入链路延迟中或合并到传出链路延迟中，只要对于增广图而言它是一致地进行的即可。

链中的逻辑节点704A-704Q的数量可以由部分700的传入链路702和传出链路706中的时隙的数量的最小公倍数来界定。在该示例中，4个时隙在逻辑节点704B、704F、704J和704N处的传入链路702上，而16个时隙在逻辑节点704A-704Q处的传出链路706上。4和16的最小公倍数是16，因此存在16个逻辑节点704A-704Q以表示增广图中的部分700。传入链路702跳过逻辑节点704A、704C至704E、704G至704I、704K、704M、704P和704Q以考虑与40Gbps链路相比在10Gbps链路上的每时隙较长的限期。可能有利的是具有整数倍的链路速率。

时隙与流的传输周期相关联。时隙大小可以被选择成具有整数时隙大小以在可能的情况下避免有理数时隙大小。以太网速率通常具有较小的最小公倍数，例如1Gbps、10Gbps、40Gbps、100Gbps和400Gbps。在许多情况下，可以进一步减少逻辑节点704A-704Q的数量。例如，对于具有16个时隙的40Gbps传入链路702和具有40个时隙的100Gbps传出链路706，最小公倍数是80。然而，这些逻辑节点中的许多可能不会被使用并且可能被移除，例如留下44个逻辑节点。

这种方法显著地提高了可伸缩性。内部逻辑节点704A-704Q的数量可以不是传入链路702和传出链路706上的时隙总数。然而，内部逻辑节点704A-704Q的数量仍然是上限。相反，逻辑节点704A-704Q的数量可以接近于最快链路上的时隙的数量。逻辑链路708的数量不再是时隙总数的多项式，而是可以与逻辑节点704A-704Q的数量相同。

图8是实施方式的可以被建模为增广图的网络800的节点图。网络800包括第一网络节点802、第二网络节点804和第三网络节点806。作为示例，第一网络节点802、第二网络节点804和第三网络节点806可以分别对应于数据源130、交换机140和数据宿150。第二网络节点804使用传入链路808耦接至第一网络节点802，传入链路808被配置成用于具有1000纳秒延迟的10Gbps。第二网络节点804使用传出链路810耦接至第三网络节点806，传出链路810被配置成用于具有100纳秒延迟的10Gbps。网络800可以如所示地进行配置或以任何其他合适的配置进行配置。例如，传入链路808和/或传出链路810可以具有任何其他合适的分组速率。

图9是实施方式的增广图900的图示。增广图900类似于图8中的网络800进行配置并且被配置成实现与图4中描述的灵活时隙调度类似的灵活时隙调度。增广图900包括第一网络节点902、第二网络节点904和第三网络节点906。第一网络节点902、第二网络节点904和第三网络节点906可以分别类似于图8中的第一网络节点802、第二网络节点804和第三网络节点806进行配置。第二网络节点904使用传入链路908耦接至第一网络节点902，传入链路908被配置成用于具有4个时隙912A、912B、912C和912D的10Gbps。第二网络节点904使用传出链路910耦接至第三网络节点906，传出链路910被配置成用于具有16个时隙914的40Gbps。第一网络节点902、第二网络节点904和第三网络节点906之间的链路(即，传入链路908和传出链路910)也可以被称为节点间链路或水平链路。

第一网络节点902被配置成具有类似于图7中的部分700的节点内链。第一网络节点902仅具有连接至其的10Gbps传入链路908，因此第一网络节点902具有4个逻辑节点916A、916B、916C和916D。被称为出向节点的新逻辑节点附接至每个网络节点。例如，第一出向节点918耦接至第一网络节点902，第二出向节点920耦接至第二网络节点904，并且第三出向节点922耦接至第三网络节点906。出向节点是在物理节点处终止的流的出向点。出向节点可能不是在数学上需要的，然而，它们可以简化用于构建优化程序的编程逻辑。第二网络节点904被配置成具有类似于图7中的部分700的节点内链。第二网络节点904具有连接至其的10Gbps传入链路908和40Gbps传出链路910，因此第二网络节点904具有总共16个逻辑节点924A、942B、924C、924D、924E、924F、924G、924H、924I、924J、924K、924L、924M、924N、924P和924Q，它们可以统称为924A-924Q。增广图900中的延迟由逻辑节点之间的间隔来表示。例如，逻辑节点924A-924Q中的每一个之间的间隔可以是大约200纳秒。传入链路908中的时隙912A耦接至第二网络节点904中的逻辑节点924F以表示传入链路908的1000纳秒链路延迟。第三网络节点906没有出向链路，因此第三网络节点906不具有时隙转换延迟并且仅包括一个逻辑节点926。

图10是实施方式的用于使用增广图的网络的调度方法1000的流程图。方法1000被实现成生成网络的增广图以及使用该增广图来调度网络中的流。方法1000可以通过网络控制器或网络元件例如图1中的网络控制器110、图2中的网络控制器200或图3中的网络元件300来实现。当使用与图9中的增广网络900类似的增广网络来调度数据业务时，可以采用方法1000。

在步骤1002，网络控制器选择经过网络节点的流，其中所述网络节点是将针对其来计算调度的网络节点。例如，网络可以是与图1中的分组交换网络160类似的分组交换网络。在步骤1004，网络控制器基于流的流速和网络节点的链路容量来生成增广图。可以与图9中的增广图900、图6中的部分600或图7中的部分700类似地生成增广图。网络控制器确定流所需的时隙数量。在一个实施方式中，网络控制器可以针对每个所需的时隙构建通过网络的一个路径。在步骤1006处，网络控制器使用增广图和最小延迟路径算法来计算用于流的流调度，以最小化流的延迟或延迟变化。例如，计算用于流的流调度可以包括采用类似于在2004年出版的Michal Pioro等人的“Routing，Flow，and Capacity Design inCommunications and Computer Networks”以及2008年出版的Robert Vanderbei的“Linear Programming foundations and Extensions”中描述的优化程序的路径计算，这两个文献均以引用的方式并入本文中，如同全文复制一样。作为示例，增广图中的网络节点可以表示为N_i。增广图中的网络节点之间的链路可以表示为L_ij，其中第一下标i标识转发网络节点，第二下标j标识接收网络节点。每个链路具有被表示为d_ij的一些延迟。通过网络的每个路径可以由F_k标识。优化变量则是标识路径是否使用链路的指示变量。指示变量可以表示为f_kij，其中第一下标k表示路径，第二下标i和第三下标j标识链路。

使用上述变量，可以针对优化过程定义约束，如流守恒约束和链路容量约束。流守恒约束可以包括但不限于流在每个网络节点守恒的约束。例如，对于所有j，约束是：

当j是流k的出向节点时(1)

当j是流k的入向节点时(2)

其他>

链路容量约束可以包括但不限于外部链路上的每个时隙仅由一个路径使用的约束。例如，对于所有外部链路L_ij，约束是：

0≤∑_kf_kij≤1。(4)

因为不能接受拆分路径，所以指示变量为0或1，

f_kij∈{0，1}。(5)

流的所有路径可以具有相同的延迟。新的变量t用于跟踪流延迟。问题中用于所有路径的这些约束则是：

另外，网络控制器可能希望通过使t最小化来使流的延迟最小化。优化变量的数量是要计算的路径的数量与逻辑节点和逻辑链路的总数的乘积。正在计算的路径的数量可以是可伸缩性的一个因素。替选地，如本领域的普通技术人员在阅读本公开内容后将会理解的，可以使用任何其他合适的业务工程算法来选择网络中要调度的流。

网络控制器可以可选地移除节点间链路中的流所使用的时隙。这些时隙不再可用于调度。在步骤1008处，网络控制器确定增广图中是否存在更多的流要调度。当增广图中存在更多的流要调度时，网络控制器返回至步骤1002。如果多个流准备好被同时调度，则一个好的启发是首先调度最高速率流。另外，当增广图中不存在更多流要调度时，网络控制器进行至步骤1010。

在步骤1010处，网络控制器输出流调度。流调度的示例包括但不限于调度文件、调度汇总和调度程序指令。例如，网络控制器可以生成并输出可以被编程到网络中的一个或更多个网络节点中的调度程序指令。另外地或替选地，网络控制器可以将流调度作为调度文件存储到存储器中。

图11是实施方式的可用于增广图中的流调度的数据模型1100的图示。在一个实施方式中，当网络控制器将网络拓扑加载到解算器中时，可以构建数据模型1100。在已经构建了数据模型1100中的数据结构之后，解算器将数据模型1100数据结构转换成用于网络的混合整数线性规划(mixed-integer linear program，MILP)。

网络包括使用链路1104耦接至第二网络节点1106A的第一网络节点1102A。第一网络节点1102A和第二网络节点1106A分别被建模为增广图的第一部分1102B和第二部分1106B。第一部分1102B和第二部分1106B被配置成具有类似于图7中的部分700的节点内链。第一部分1102B包括使用逻辑链路1122彼此连接的逻辑节点1120的链。第二部分1106B包括使用逻辑链路1126彼此连接的逻辑节点1124的链。链路1104被配置成具有与逻辑链路1128A、1128B、1128C和1128D对应的4个时隙。

通过将映射表关联至网络中的链路对象(例如，链路1104)和网络节点对象(例如，第一网络节点1102A和第二网络节点1106A)来对增广图进行建模。例如，第一网络节点1102A与第一网络节点映射(NodeMap)表1108相关联，第二网络节点1106A与第二节点映射表1116相关联，并且链路1104与出向时隙映射表1110、时隙延迟映射表1112和入向时隙映射表1114相关联。节点映射表包括网络节点的信息，包括但不限于用于网络节点的逻辑节点的数量、逻辑节点标识符、时隙标识符以及与移动至下一个逻辑节点或时隙相关联的延迟。例如，第一节点映射表1108和第二节点映射表1116均包括四个条目。每个条目标识逻辑节点或时隙以及与移动至下一逻辑节点或时隙相关联的延迟。出向时隙映射表1110、时隙延迟映射表1112和入向时隙映射表1114包括链路1104的信息并且用于实现第一部分1102B与第二部分1106B之间的逻辑链路1128A-1128D。出向时隙映射表1110标识第一部分1102B中的连接至第一部分1102B与第二部分1106B之间的逻辑链路1128A-1128D的时隙和逻辑节点1120。时隙延迟映射表1112标识与从第一部分1102B中的时隙或逻辑节点1120经由逻辑链路1128A-1128D移动至第二部分1106B中的时隙或逻辑节点1124相关联的延迟。在一个实施方式中，当时隙之间的延迟总是相同时，时隙延迟映射表1112可以是可选的。入向时隙映射表1114标识第一部分1102B中的时隙或逻辑节点1120与第二部分1106B中的时隙或逻辑节点1124之间的映射。

图12是实施方式的线性规划结构1200的框图。线性规划结构1200可以由采用用于求解混合整数线性规划的优化程序的网络控制器来使用。网络控制器可以被类似地配置成图1中的网络控制器110和图2中的网络控制器200。例如，一旦已经构建了增广图，则优化程序可以通过使用线性规划结构1200将增广图转换成混合整数线性规划。

线性规划结构1200可以被组织为表。表的列是优化变量，表的行是约束。优化变量可以通过路径被组织成块1202。对于每个路径，变量可以首先按(例如，物理网络节点之间的)外部链路排序，然后按内部链路排序。以针对每个路径一个新的块的方式重复块1202。在一个实施方式中，线性规划结构1200包括流守恒约束1204、链路/时隙使用约束1206和延迟约束1208。例如，这些约束可以被组织成使得在流守恒约束1204之后是链路/时隙使用约束1206和延迟约束1208。可以建立流守恒约束1204以确保通过网络节点或增广网络的流是守恒的。流守恒约束1204的示例是图10的步骤1002中的式(1)、(2)和(3)。可以建立链路/时隙使用约束1206以确保外部链路中的时隙只能使用一次。链路时隙使用约束1206的示例是图10的步骤1002中的式(4)。延迟约束1208的示例是图10的步骤1002中的式(6)。当流使用多个路径时，延迟约束1208可以包括具有相同延迟的多个条目。使用线性规划结构1200，优化程序可以递增地计算流或一次计算若干流。

图13是实施方式的用于增广图的数据业务调度方法1300的流程图。方法1300被实现成通过网络控制器或网络元件例如图1中的网络控制器110、图2中的网络控制器200或图3中的网络元件300来调度增广图中的流。当使用与图9中的增广图900类似的增广图来调度数据业务时，可以采用方法1300。

在步骤1302处，网络控制器获得网络的网络拓扑。例如，网络控制器可以使用链路层发现协议、链路状态协议(例如，开放式最短路径优先(open shortest path first，OSPF)协议或中间系统到中间系统(intermediate system to intermediate system，IS-IS)协议)、规划工具或者本领域普通技术人员在阅读本公开内容后将理解的任何其他协议或工具来获得网络拓扑。在步骤1304处，网络控制器基于网络拓扑来生成增广图。可以与图9中的增广图900、图6中的部分600或图7中的部分700类似地生成增广图。在步骤1306处，网络控制器将增广图转换成混合整数线性规划。例如，网络控制器可以获得约束(例如，图12中的流守恒约束1204、链路/时隙使用约束1206和/或延迟约束1208)，将该约束应用于网络拓扑和流请求，并且将网络拓扑加载到解算器中以创建混合整数线性规划。网络控制器可以通过使用分别类似于图11中的数据模型1100和图12中的线性规划结构1200的数据模型和线性规划结构来将增广图转换成混合整数线性规划。在步骤1308处，网络控制器使用混合整数线性规划来调度网络中的流，以使流的延迟或延迟变化最小化。可以以类似于图10中的方法1000的方式来调度网络中的流。例如，网络控制器可以从解算器中获得包括优化变量的解，以确定流调度。

在步骤1310处，网络控制器输出流调度。流调度的示例包括但不限于调度文件、调度汇总和调度程序指令。例如，网络控制器可以生成并输出可以被编程到网络中的一个或更多个网络节点中的调度程序指令。附加地或替选地，网络控制器可以将流调度作为调度文件存储在存储器中。

尽管本公开内容已经提供了若干实施方式，但应当理解，在不脱离本公开内容的精神或范围的情况下，所公开的系统和方法可以以许多其他具体形式来实施。本示例要被视为说明性而非限制性的，并且意在不限制于本文所给出的细节。例如，各种元件或部件可以被组合或合并在另一系统中，或者某些特征可以省略或不实施。

另外，在不脱离本公开内容的范围的情况下，各种实施方式中被描述和说明为分立或单独的技术、系统、子系统和方法可以与其他系统、模块、技术或方法进行组合或合并。被示出为或论述为彼此耦接或直接耦接或通信的其他项可以通过某种接口、设备或中间部件间接地耦接或通信，无论是采用电方式、机械方式或其他方式。在不脱离本文所公开的精神和范围的情况下，本领域的技术人员还可以确定并进行关于变化、替代和改变的其他示例。