[go: up one dir, main page]
More Web Proxy on the site http://driver.im/

CN115484205B - 确定性网络路由与队列调度方法及装置 - Google Patents

确定性网络路由与队列调度方法及装置 Download PDF

Info

Publication number
CN115484205B
CN115484205B CN202210822548.9A CN202210822548A CN115484205B CN 115484205 B CN115484205 B CN 115484205B CN 202210822548 A CN202210822548 A CN 202210822548A CN 115484205 B CN115484205 B CN 115484205B
Authority
CN
China
Prior art keywords
network
agent
deterministic
forwarding
queue
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
CN202210822548.9A
Other languages
English (en)
Other versions
CN115484205A (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.)
Beijing University of Posts and Telecommunications
Original Assignee
Beijing University of Posts and Telecommunications
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 Beijing University of Posts and Telecommunications filed Critical Beijing University of Posts and Telecommunications
Priority to CN202210822548.9A priority Critical patent/CN115484205B/zh
Publication of CN115484205A publication Critical patent/CN115484205A/zh
Application granted granted Critical
Publication of CN115484205B publication Critical patent/CN115484205B/zh
Active legal-status Critical Current
Anticipated expiration legal-status Critical

Links

Classifications

    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H04L45/12—Shortest path evaluation
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H04L45/12—Shortest path evaluation
    • H04L45/123—Evaluation of link metrics
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L47/00—Traffic control in data switching networks
    • H04L47/50—Queue scheduling
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L49/00—Packet switching elements
    • H04L49/90—Buffering arrangements

Landscapes

  • Engineering & Computer Science (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Signal Processing (AREA)
  • Data Exchanges In Wide-Area Networks (AREA)

Abstract

本公开提供一种确定性网络路由与队列调度方法及装置，属于计算机技术领域，该方法包括：创建一个计算转发路径的智能体Ar和一个计算沿路径各节点处的转发周期的智能体Ac；智能体Ar和智能体Ac共享奖励以全局网络状态作为评价网络的输入，以状态价值作为评价网络的输出，以最大化期望奖励为优化目标，不断更新网络，选择最优的路由和最优的转发队列来指定确定性流的转发路径和沿途各节点处的周期偏移信息。本公开提供的确定性网络路由与队列调度方法及装置，能够适应环境的动态性，不需要人为建立复杂的静态模型，能够实时调整调度策略以适应新的环境。

Description

确定性网络路由与队列调度方法及装置
技术领域
本公开涉及通信技术领域，尤其涉及一种确定性网络路由与队列调度方法及装置。
背景技术
在满足确定性网络低延迟要求方面，现有的大部分工作均采用在时间敏感型网络(Time Sensitive Network,TSN)第二层网络中优化输出端口的门控列表(IEEE 802.1Qbv)来进行流量调度的方案。在第三层的确定性网络方面也有一些从各个角度来优化调度方案以实现确定性网络服务的工作。但这些工作中提出的基于优化模型的解决方案不具备可拓展性、启发式算法可能导致局部最优从而不能实现高效的优化。在使用深度强化学习模型的解决方案中，采取在每一跳选下一跳的方式来提高确定性服务质量，但仍采用传统队列管理方案，优化效果有限；基于优化模型的求解方案，存在求解速度慢、启发式算法可能无法达到更好的网络性能等问题。除此之外，采取传统的基于优化模型的方案时，新流量需求的产生将导致网络中已被部署的所有流的配置方案被取消，此时需对重组的流量矩阵计算新的配置方案，如果涉及到更多的节点，由此导致的交互会使延迟增大。
发明内容
有鉴于此，本公开的目的在于提出一种确定性网络路由与队列调度方法及装置。
基于上述目的，本公开提供了一种确定性网络路由与队列调度方法，包括：
创建一个计算转发路径的智能体Ar和一个计算沿路径各节点处的转发周期的智能体Ac；智能体Ar和智能体Ac共享奖励在多智能近端策略优化MAPPO模型中智能体Ar和智能体Ac对应一个Actor网络，智能体Ar和智能体Ac共享一个Critic网络；
以全局网络状态作为评价网络的输入，以状态价值作为评价网络的输出，以最大化期望奖励为优化目标，不断更新网络，选择最优的路由和最优的转发队列来指定确定性流的转发路径和沿途各节点处的周期偏移信息。
可选地，以全局网络状态作为评价网络的输入，以状态价值作为评价网络的输出，以最大化期望奖励为优化目标，不断更新网络，包括：
初始化网络环境；
分别将网络状态输入到智能体Ar和智能体Ac对应Actor网络，获得联合策略Action；
执行策略，获得下一时刻运行状态和全局奖励，并将前后运行状态、策略和奖励存储到缓冲器内；
在达到训练周期的情况下，从缓冲器内获取经验，分别更新Critic网络和Actor网络。
可选地，所述方法还包括：
在未达到训练周期的情况下，再次将网络状态输入到智能体Ar和智能体Ac对应Actor网络，获得联合策略Action。
可选地，所述方法还包括：
判断迭代次数是否达到最大值；
在迭代次数未达到最大值的情况下，再次初始化网络环境。
可选地，所述方法还包括：
判断迭代次数是否达到最大值；
在迭代次数达到最大值的情况下，若模型收敛，则输出最优的路由和最优的转发队列。
可选地，所述方法还包括：
确定训练轮数和更新周期，并初始化迭代变量。
可选地，所述奖励为资源利用率方差和转发时延的综合指数。
本公开还提供了一种确定性网络路由与队列调度装置，包括：
模型构建模块，用于创建一个计算转发路径的智能体Ar和一个计算沿路径各节点处的转发周期的智能体Ac；智能体Ar和智能体Ac共享奖励；在多智能近端策略优化MAPPO模型中智能体Ar和智能体Ac对应一个Actor网络，智能体Ar和智能体Ac共享一个Critic网络；
调度模块，用于以全局网络状态作为评价网络的输入，以状态价值作为评价网络的输出，以最大化期望奖励为优化目标，不断更新网络，选择最优的路由和最优的转发队列来指定确定性流的转发路径和沿途各节点处的周期偏移信息。
本公开还提供了一种电子设备，包括存储器、处理器及存储在存储器上并可在处理器上运行的计算机程序，所述处理器执行所述程序时实现上述确定性网络路由与队列调度方法。
本公开还提供了一种非暂态计算机可读存储介质，所述非暂态计算机可读存储介质存储计算机指令，所述计算机指令用于使计算机执行上述确定性网络路由与队列调度方法。
从上面所述可以看出，本公开提供的确定性网络路由与队列调度方法及装置，能够适应环境的动态性，不需要人为建立复杂的静态模型，能够实时调整调度策略以适应新的环境。
附图说明
为了更清楚地说明本公开或相关技术中的技术方案，下面将对实施例或相关技术描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本公开的实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他的附图。
图1为本公开实施例的确定性网络路由与队列调度方法的示意图；
图2为本公开实施例的系统架构示意图；
图3为本公开实施例的基于MAPPO的确定性网络流路由和队列调度算法结构示意图；
图4为本公开实施例的基于MAPPO的确定性网络流路由和队列调度算法流程示意图；
图5为本公开实施例的确定性网络路由与队列调度装置的示意图；
图6为本公开实施例的电子设备的示意图。
具体实施方式
为使本公开的目的、技术方案和优点更加清楚明白，以下结合具体实施例，并参照附图，对本公开进一步详细说明。
需要说明的是，除非另外定义，本公开实施例使用的技术术语或者科学术语应当为本公开所属领域内具有一般技能的人士所理解的通常意义。本公开实施例中使用的“第一”、“第二”以及类似的词语并不表示任何顺序、数量或者重要性，而只是用来区分不同的组成部分。“包括”或者“包含”等类似的词语意指出现该词前面的元件或者物件涵盖出现在该词后面列举的元件或者物件及其等同，而不排除其他元件或者物件。
本发明涉及网络通信与机器学习技术领域，具体为一种基于深度强化学习的确定性网络路由与队列调度方法。本发明针对确定性网络业务场景，基于实时网络状态和确定性需求进行路由和队列决策，采用多智能体深度强化学习算法，对确定性网络流通过最优路径和最优队列调度方案下发至数据层面指导转发，进而实现保证确定性服务的同时最大化网络资源的利用率。
确定性网络对网络性能提出了更为严格的要求，如有界的时延和抖动等，传统的基于统计概率优化平均性能的方式在此场景下将造成较大的损失。本发明提出了一种基于深度强化学习的确定性网络路由和队列联合调度方法，使用周期队列转发功能在第三层动态地利用第二层的排队和调度功能，并结合深度强化学习技术的决策能力，使用多智能体对路由和调度统筹考虑，以解决三层确定性网络的确定性传输问题，保证最大限度地提高网络对确定性网络流的可承载数量。涉及网络通信与机器学习技术领域，包括设计基于SDN的路由和队列的联合调度算法；构建确定性网络背景下的深度强化模型，包括网络状态、动作空间和奖励的设计；设计决策模型的训练方案。
软件定义网络(Software Defined Network,SDN)是一种新型的网络架构。它的基本思想是将传统分布式网络的控制平面和数据平面彻底解耦，并使用一个逻辑集中的控制器来控制整个分布式的数据平面，从而实现集中式的网络管理和配置，提高了网络管理的效率并降低了网络配置的复杂度。当控制器接收到用户的确定性服务请求时，分析此确定性流的特征信息并根据网络拓扑和状态信息以及确定性网络能力来计算显式路径和资源预留信息，若能成功分配，则响应该服务请求。结合SDN技术，确定性网络在保障确定性服务方面会变得更加灵活敏捷。
随着互联网和通信网络的发展，在许多新兴业务领域都出现了一些对网络服务具有确定性需求的应用，如工业控制、车联网和智能电网等。满足这类确定性的服务需求已经成为网络技术发展的关键驱动力。然而传统的互联网协议(Internet Protocol,IP)网络只提供尽力而为的服务，即便是存在一些服务质量策略，如差异化服务(Diffserv)和拥塞控制等，但由于网络中存在微突发流，这些机制只能提供基于概率统计上的平均性能的优化，并不能满足确定性服务的要求，如零丢包率、有界的延迟和抖动等。
为满足这类应用的确定性服务需求，国际互联网工程任务组(InternetEngineering Task Force,IETF)成立确定性网络(Deterministic Detwork，DetNet)工作组分别对以太网的链路层和网络层进行优化，提升其对时间敏感流传输的支撑能力。主要是在动态网络配置、资源编排、路径规划、路由转发和多径转发等方面对以太网L3层进行优化。
为实现在网络三层中的确定性转发服务，IETF确定性网络小组提出了周期指定队列和转发(Cycle Specified Queuing and Forwarding,CSQF)机制的草案标准。它是循环队列转发(Cycle Queuing and Forwarding,CQF)的演变，与CQF相比，CSQF增加了使用更多的队列来实现节点之间的松散同步和高级调度的可能性。CSQF在第三层运行，它允许使用分段路由(SR)对数据包进行灵活的路由和调度。通过使用SR标签栈来明确说明每个中间节点在接收和处理数据包后应该在哪个端口(路由)和哪个队列(调度)进行传输。
深度强化学习(Deep Reinforcement Learning,DRL)是机器学习中的一个子领域，结合了强化学习(Reinforcement Learning,RL)和深度神经网络(Deep NeuralNetwork,DNN)。强化学习通过智能体不断与环境进行交互，能够自动学习不同状态下应该采取的最优动作(即策略)，以最大化所获奖励。深度强化学习将深度神经网络纳入解决方案，DNN强大的表示能力可以充分拟合最优策略，能很好的适应复杂环境。
多智能体深度强化学习(Multi-Agent Deep Reinforcement Learning,MADRL)将深度强化学习的思想和算法用于多智能体系统的学习和控制中。多智能体系统中每个智能体的策略不只取决于自身的策略和环境的反馈,同时还受到其他智能体的行为和合作关系的影响。
在满足确定性网络低延迟要求方面，现有的大部分工作均采用在时间敏感型网络(Time Sensitive Network,TSN)第二层网络中优化输出端口的门控列表(IEEE 802.1Qbv)来进行流量调度的方案。在第三层的确定性网络方面也有一些从各个角度来优化调度方案以实现确定性网络服务的工作。但这些工作都没有考虑除队列的调度之外，路由的选择也对优化网络性能的提升具有很大的影响，并忽略了大规模确定性网络具有动态流量的特性。这些工作中提出的基于优化模型的解决方案不具备可拓展性、启发式算法可能导致局部最优从而不能实现高效的优化。在使用深度强化学习模型的解决方案中，采取在每一跳选下一跳的方式来提高确定性服务质量，但仍采用传统队列管理方案，优化效果有限；基于优化模型的求解方案，存在求解速度慢、启发式算法可能无法达到更好的网络性能等问题。除此之外，采取传统的基于优化模型的方案时，新流量需求的产生将导致网络中已被部署的所有流的配置方案被取消，此时需对重组的流量矩阵计算新的配置方案，如果涉及到更多的节点，由此导致的交互会使延迟增大。
本发明所要解决的技术问题在于，发明一种基于深度强化学习的确定性网络路由和队列的联合调度方法，实现在三层IP网络中确定性的数据传输，即有界的抖动和端到端延迟。现有的解决方法中采用的单一路由或者队列调度的优化方案将限制网络优化的性能边界，即便是将路由和队列结合的方案也是基于特定的优化模型建模，难以适应动态的网络环境，而其信息收集和集中计算的开销较大，会导致额外的延迟，进而无法及时应对动态流量，采用的启发式算法又容易陷入局部最优，难以保证全局最优。
基于以上信息，本方法采用的基于深度强化学习的决策方案更能适应动态的网络环境，可以及时应对动态流量，将路由和队列联合调度的机制扩展了探索最优方案的边界，基于SDN的网络架构中控制器可收集网络全局视图与确定性网络流的需求信息输入到深度强化学习智能体，智能体根据状态信息计算得到路由和队列调度方案，由控制器以SID标签栈的形式下发至转发平面，可控制数据包在何处(路由)何时(队列调度)被转发，从而达到确定性服务目标。
图1为本公开实施例的确定性网络路由与队列调度方法的示意图，如图1所示，本公开实施例提供一种确定性网络路由与队列调度方法，其执行主体可以为电子设备，例如，计算机等，该方法包括：
步骤101、创建一个计算转发路径的智能体Ar和一个计算沿路径各节点处的转发周期的智能体Ac；智能体Ar和智能体Ac共享奖励在多智能近端策略优化MAPPO模型中智能体Ar和智能体Ac对应一个Actor网络，智能体Ar和智能体Ac共享一个Critic网络；
步骤102、以全局网络状态作为评价网络的输入，以状态价值作为评价网络的输出，以最大化期望奖励为优化目标，不断更新网络，选择最优的路由和最优的转发队列来指定确定性流的转发路径和沿途各节点处的周期偏移信息。
具体地，图2为本公开实施例的系统架构示意图，如图2所示，本发明面向确定性网络场景，使用周期转发队列功能划分队列调度周期，并采用深度强化学习模型，以全局网络状态作为评价网络的输入，以状态价值作为评价网络的输出，算法以最大化期望奖励为优化目标，不断更新网络。为了利用多智能体深度强化学习对确定性服务进行路由和队列的联合调度，通过选择最优的路由和最优的转发队列来指定确定性流的转发路径和沿途各节点处的周期偏移信息。算法创建两个智能体，一个智能体计算转发路径，一个智能体计算转发周期，按照已完成的多智能体深度强化学习框架，智能体共享奖励，将奖励值设置为资源利用率方差和转发时延的综合指数。当调度一个确定性网络流时，若智能体计算所得方案中的每条链路和选定的周期内都有足够的容量且满足时延要求，则此需求可以成功分配，由控制器的策略下发模块生成SID标签栈下发至数据层面指导转发。
本发明将确定性流的特征以<src,dst,period,delay,bw>五元组表示，分别描述了确定性流的信息：源和目的端口、周期、时延上限以及带宽。在支持CSQF的设备内部，让每个端口保留Nnd(Nnd＝3)个队列给确定性流，在全网所有节点处划分以10μs为基础周期的调度周期C，即在每一个节点的每个队列的资源划分为C个周期，此时，端到端的最大抖动为20μs，符合标准超低延迟要求。在不丧失一般性的情况下，假设整个网络的周期在同一时间开始，并且每个端口/链接的超周期长度C是相同的。
本发明将网络抽象为一个无向图其中，/>与ε为该网络的点集与边集，εc为链路资源的集合，εc中每条链路的信息包括链路的剩余带宽，CSQF队列占用情况，ε为设备间的通信链路的集合。以/>表示确定性网络流的集合，每个服务由＜src,dst,period,delay,bw>五元组表示，分别描述了确定性流的信息：源和目的端口、周期、时延上限以及带宽。以pf和rf表示本算法最终为数据流f∈F所选择的转发路径和转发周期偏移。
图3为本公开实施例的基于MAPPO的确定性网络流路由和队列调度算法结构示意图，如图3所示，智能体Ar和智能体Ac共享奖励在多智能近端策略优化MAPPO模型中智能体Ar和智能体Ac对应一个Actor网络，智能体Ar和智能体Ac共享一个Critic网络。
对于算法中的智能体来说，在某一环境状态下，发出某一动作，将得到环境的反馈即奖励，环境的状态也随之改变，在新的状态下，智能体继续发出动作、获得反馈，持续与环境交互。以A表示智能体的集合，以Ar表示代理计算路由的智能体，以Ac表示代理计算转发周期的智能体。
对于智能体Ar，状态的公式描述如下：
其中，表示网络链路状态，/>LU表示边的链路利用率，D表示边的端到端时延。
动作集的公式描述如下：
动作的公式描述如下：
ar＝pf,pf∈Pf
对于智能体Ac，状态的公式描述如下：
动作集的公式描述如下：
动作的公式描述如下：
ac＝rf,rf∈Rf
智能体共享奖励为资源利用率方差和转发时延的综合指数，公式描述如下：
其中，std(LU)表示链路利用率标准差，fbw为确定性网络流f所需带宽，即分配给该服务的带宽，Df为智能体为确定性服务流f所选择的转发路径pf和转发周期偏移rf后的传输时延，该时延包括两部分，(i)节点间链路的传播延迟之和(ii)中间节点的周期偏移的总和/> 表示确定性网络流f在边e上的周期偏移量。fdelay为确定性网络流f要求的端到端时延上限，只有在保证满足该条件的情况下，才能传输数据，否则将拒绝该服务请求，α,β,γ为权重参数。
可选地，以全局网络状态作为评价网络的输入，以状态价值作为评价网络的输出，以最大化期望奖励为优化目标，不断更新网络，包括：
初始化网络环境；
分别将网络状态输入到智能体Ar和智能体Ac对应Actor网络，获得联合策略Action；
执行策略，获得下一时刻运行状态和全局奖励，并将前后运行状态、策略和奖励存储到缓冲器内；
在达到训练周期的情况下，从缓冲器内获取经验，分别更新Critic网络和Actor网络。
可选地，所述方法还包括：
在未达到训练周期的情况下，再次将网络状态输入到智能体Ar和智能体Ac对应Actor网络，获得联合策略Action。
可选地，所述方法还包括：
判断迭代次数是否达到最大值；
在迭代次数未达到最大值的情况下，再次初始化网络环境。
可选地，所述方法还包括：
判断迭代次数是否达到最大值；
在迭代次数达到最大值的情况下，若模型收敛，则输出最优的路由和最优的转发队列。
可选地，所述方法还包括：
确定训练轮数和更新周期，并初始化迭代变量
图4为本公开实施例的基于MAPPO的确定性网络流路由和队列调度算法流程示意图，如图4所示，基于MAPPO的确定性网络流路由和队列调度算法具体包括如下步骤：
1、首先创建网络的拓扑模型及计算节点信息，拓扑中存在m个点，例如，m≥30，其中包括计算节点n个，例如，n≥8，让每个端口保留Nnd(Nnd＝3)个队列给确定性流，在全网所有节点处划分以10μs为基础周期的调度周期C，即在每一个节点的每个队列的资源划分为C个周期，全网所有节点同时开始周期。拓扑中链路带宽设置为统一值x MB/s，x≥40。
2、初始化变量，设初始迭代次数i＝0，最大迭代次数为i_max，例如，i_max≥1000000，i_max基于实际需求进行设定。设置经验回放池，长度为n，例如，n>＝5000。
3、创建2个智能体对象实例，一个智能体Ar代表计算路由路径，一个智能体Ac代表计算转发周期，在MAPPO模型中每个智能体对应着一个Actor网络，2个智能体共享一个Critic网络，均采用三层全连接的神经网络，随机初始化网络参数。
4、随机产生确定性网络流，每一个确定性网络流f的信息由五元组＜src,dst,period,delay,bw＞五元组，分别描述了确定性流的特征：源目的端口、周期、时延上限以及带宽。通过从顶点集合中均等概率地选择2个值来创建源节点和目的节点，数据包长度为100～1500B。通常流发送周期从集合{1,2,4,8}ms中随机抽取，时延上界服从最小值20ms最大值50ms的正态分布；流的带宽服从最小值5MB/s最大值20MB/s的正态分布。
5、初始State设为网络拓扑、确定性网络流需求、链路资源及网络链路状态的组合
6、开始迭代，使i的值增加1。各智能体生成动作。代理计算路由的智能体Ar通过Actor网络从动作集Pf中选取Q值最大的生成动作数组ar＝[pf,k1,pf,k2,…,pf,|k|]，pf,ki表示网络流f被分配到的路径链路编号1～m，数组大小为路径长度。代理计算转发周期的智能体Ac的Actor网络动作集Rf中选取Q值最大的生成动作数组ar＝[rf,k1,rf,k2,...,rf,|k|]，rf,k表示网络流f被分配到的路径链路编号处的转发周期偏移，数组大小为路径长度。
7、将智能体Ar计算出的转发路径、智能体Ac给出的转发周期重组成联合动作Action＝(ar,ac)，可以确定为确定性网络流在何处pf何时rf转发，作为路径和队列调度规划方案应用于网络。
8、在网络中生成相应的确定性网络流，获取网络中的链路利用率、传输时延和各节点处的停留时延，从而计算出计算链路利用率方差和总时延Df，根据指定的这二者的权重指数得出即奖励(Reward)。
9、将状态State'设为网络拓扑、确定性网络流需求、链路资源及网络链路状态的组合将State，Action＝(ar,ac)，Reward，State'存入经验回放池中供模型迭代学习参考。
10、重复第4步到第9步，直到经验回放池满。
11、各智能体根据经验回放池更新策略，更新过程如下：
12、将第11步得到的最新State'输入到Critic网络，得到状态的v'值，计算折扣奖励R[t]＝r[t[+δ1*r[t+1]+…+δT-t*r[t_]，得到R＝[R[0],R[1],…,R[t],…R[t_]]，其中t_是最后一个时间步，δ是折扣因子。
13、将经验回放池中的所有State输入Critic网络，得到所有状态的V_值，计算优势函数
14、计算Critic网络的损失(loss)函数，反向传播更新Critic网络，Critic网络的loss函数的表达式如下：
15、对于每个智能体的Actor网络，将存储的所有State组合输入Actor-old和Actor-new网络(网络结构一样)，分别得到正态分布Normal1和Normal2，将存储的所有Action组合为Actions输入到正态分布Normal1和Normal2，得到每个Actions对应的prob1和prob2，然后用prob2除以prob1得到重要性权重ratio。
16、对于每个智能体的Actor网络，计算Actor网络的loss函数，反向传播更新Actor-new网络，Actor网络的loss函数的表达式如下：
ratio为第15步中得到的重要性权重，∈是学习率，clip(ratio,1-∈,1+∈)表示将超出(1-∈,1+∈)范围的ratio裁剪掉。
17、重复步骤第15和16步，例如，重复10次后，用Actor-new网络的参数更新Actor-old网络。
18、判断迭代次数i是否超过最大迭代次数i_max，若不超过，返回第4步，继续迭代，若超过，则算法结束，此时算法可以根据输入的状态输出最优的路由和最优的转发队列。
本发明面向确定性网络，使用基于MAPPO的确定性网络流路由和队列调度算法实现确定性网络流的转发，一个智能体负责计算转发路径，一个智能体负责计算沿路径各节点处的转发周期，两个智能体共享联合动作的奖励，经过多次迭代学习后，在保障确定性服务的同时可避免计算节点负载过大或网络拥堵导致用户总体体验下降的风险。本发明设计的确定性网络流调度算法能够适应环境的动态性，不需要人为建立复杂的静态模型，能够实时调整调度策略以适应新的环境。
需要说明的是，本公开实施例的方法可以由单个设备执行，例如一台计算机或服务器等。本实施例的方法也可以应用于分布式场景下，由多台设备相互配合来完成。在这种分布式场景的情况下，这多台设备中的一台设备可以只执行本公开实施例的方法中的某一个或多个步骤，这多台设备相互之间会进行交互以完成所述的方法。
需要说明的是，上述对本公开的一些实施例进行了描述。其它实施例在所附权利要求书的范围内。在一些情况下，在权利要求书中记载的动作或步骤可以按照不同于上述实施例中的顺序来执行并且仍然可以实现期望的结果。另外，在附图中描绘的过程不一定要求示出的特定顺序或者连续顺序才能实现期望的结果。在某些实施方式中，多任务处理和并行处理也是可以的或者可能是有利的。
基于同一发明构思，与上述任意实施例方法相对应的，本公开还提供了一种确定性网络路由与队列调度装置。
图5为本公开实施例的确定性网络路由与队列调度装置的示意图，如图5所示，所述确定性网络路由与队列调度装置，包括模型构建模块501和调度模块502，其中：
模型构建模块501用于创建一个计算转发路径的智能体Ar和一个计算沿路径各节点处的转发周期的智能体Ac；智能体Ar和智能体Ac共享奖励在多智能近端策略优化MAPPO模型中智能体Ar和智能体Ac对应一个Actor网络，智能体Ar和智能体Ac共享一个Critic网络；
调度模块502用于以全局网络状态作为评价网络的输入，以状态价值作为评价网络的输出，以最大化期望奖励为优化目标，不断更新网络，选择最优的路由和最优的转发队列来指定确定性流的转发路径和沿途各节点处的周期偏移信息。
可选地，以全局网络状态作为评价网络的输入，以状态价值作为评价网络的输出，以最大化期望奖励为优化目标，不断更新网络，包括：
初始化网络环境；
分别将网络状态输入到智能体Ar和智能体Ac对应Actor网络，获得联合策略Action；
执行策略，获得下一时刻运行状态和全局奖励，并将前后运行状态、策略和奖励存储到缓冲器内；
在达到训练周期的情况下，从缓冲器内获取经验，分别更新Critic网络和Actor网络。
可选地，所述方法还包括：
在未达到训练周期的情况下，再次将网络状态输入到智能体Ar和智能体Ac对应Actor网络，获得联合策略Action。
可选地，所述方法还包括：
判断迭代次数是否达到最大值；
在迭代次数未达到最大值的情况下，再次初始化网络环境。
可选地，所述方法还包括：
判断迭代次数是否达到最大值；
在迭代次数达到最大值的情况下，若模型收敛，则输出最优的路由和最优的转发队列。
可选地，所述方法还包括：
确定训练轮数和更新周期，并初始化迭代变量。
可选地，所述奖励为资源利用率方差和转发时延的综合指数。
为了描述的方便，描述以上装置时以功能分为各种模块分别描述。当然，在实施本公开时可以把各模块的功能在同一个或多个软件和/或硬件中实现。
上述实施例的装置用于实现前述任一实施例中相应的确定性网络路由与队列调度方法，并且具有相应的方法实施例的有益效果，在此不再赘述。
基于同一发明构思，与上述任意实施例方法相对应的，本公开还提供了一种电子设备，包括存储器、处理器及存储在存储器上并可在处理器上运行的计算机程序，所述处理器执行所述程序时实现上任意一实施例所述的确定性网络路由与队列调度方法。
图6示出了本实施例所提供的一种更为具体的电子设备硬件结构示意图，该设备可以包括：处理器1010、存储器1020、输入/输出接口1030、通信接口1040和总线1050。其中处理器1010、存储器1020、输入/输出接口1030和通信接口1040通过总线1050实现彼此之间在设备内部的通信连接。
处理器1010可以采用通用的CPU(CentralProcessingUnit，中央处理器)、微处理器、应用专用集成电路(ApplicationSpecificIntegratedCircuit，ASIC)、或者一个或多个集成电路等方式实现，用于执行相关程序，以实现本说明书实施例所提供的技术方案。
存储器1020可以采用ROM(ReadOnlyMemory，只读存储器)、RAM(RandomAccessMemory，随机存取存储器)、静态存储设备，动态存储设备等形式实现。存储器1020可以存储操作系统和其他应用程序，在通过软件或者固件来实现本说明书实施例所提供的技术方案时，相关的程序代码保存在存储器1020中，并由处理器1010来调用执行。
输入/输出接口1030用于连接输入/输出模块，以实现信息输入及输出。输入输出/模块可以作为组件配置在设备中(图中未示出)，也可以外接于设备以提供相应功能。其中输入设备可以包括键盘、鼠标、触摸屏、麦克风、各类传感器等，输出设备可以包括显示器、扬声器、振动器、指示灯等。
通信接口1040用于连接通信模块(图中未示出)，以实现本设备与其他设备的通信交互。其中通信模块可以通过有线方式(例如USB、网线等)实现通信，也可以通过无线方式(例如移动网络、WIFI、蓝牙等)实现通信。
总线1050包括一通路，在设备的各个组件(例如处理器1010、存储器1020、输入/输出接口1030和通信接口1040)之间传输信息。
需要说明的是，尽管上述设备仅示出了处理器1010、存储器1020、输入/输出接口1030、通信接口1040以及总线1050，但是在具体实施过程中，该设备还可以包括实现正常运行所必需的其他组件。此外，本领域的技术人员可以理解的是，上述设备中也可以仅包含实现本说明书实施例方案所必需的组件，而不必包含图中所示的全部组件。
上述实施例的电子设备用于实现前述任一实施例中相应的确定性网络路由与队列调度方法，并且具有相应的方法实施例的有益效果，在此不再赘述。
基于同一发明构思，与上述任意实施例方法相对应的，本公开还提供了一种非暂态计算机可读存储介质，所述非暂态计算机可读存储介质存储计算机指令，所述计算机指令用于使所述计算机执行如上任一实施例所述的确定性网络路由与队列调度方法。
本实施例的计算机可读介质包括永久性和非永久性、可移动和非可移动媒体可以由任何方法或技术来实现信息存储。信息可以是计算机可读指令、数据结构、程序的模块或其他数据。计算机的存储介质的例子包括，但不限于相变内存(PRAM)、静态随机存取存储器(SRAM)、动态随机存取存储器(DRAM)、其他类型的随机存取存储器(RAM)、只读存储器(ROM)、电可擦除可编程只读存储器(EEPROM)、快闪记忆体或其他内存技术、只读光盘只读存储器(CD-ROM)、数字多功能光盘(DVD)或其他光学存储、磁盒式磁带，磁带磁磁盘存储或其他磁性存储设备或任何其他非传输介质，可用于存储可以被计算设备访问的信息。
上述实施例的存储介质存储的计算机指令用于使所述计算机执行如上任一实施例所述的确定性网络路由与队列调度方法，并且具有相应的方法实施例的有益效果，在此不再赘述。
所属领域的普通技术人员应当理解：以上任何实施例的讨论仅为示例性的，并非旨在暗示本公开的范围(包括权利要求)被限于这些例子；在本公开的思路下，以上实施例或者不同实施例中的技术特征之间也可以进行组合，步骤可以以任意顺序实现，并存在如上所述的本公开实施例的不同方面的许多其它变化，为了简明它们没有在细节中提供。
另外，为简化说明和讨论，并且为了不会使本公开实施例难以理解，在所提供的附图中可以示出或可以不示出与集成电路(IC)芯片和其它部件的公知的电源/接地连接。此外，可以以框图的形式示出装置，以便避免使本公开实施例难以理解，并且这也考虑了以下事实，即关于这些框图装置的实施方式的细节是高度取决于将要实施本公开实施例的平台的(即，这些细节应当完全处于本领域技术人员的理解范围内)。在阐述了具体细节(例如，电路)以描述本公开的示例性实施例的情况下，对本领域技术人员来说显而易见的是，可以在没有这些具体细节的情况下或者这些具体细节有变化的情况下实施本公开实施例。因此，这些描述应被认为是说明性的而不是限制性的。
尽管已经结合了本公开的具体实施例对本公开进行了描述，但是根据前面的描述，这些实施例的很多替换、修改和变型对本领域普通技术人员来说将是显而易见的。例如，其它存储器架构(例如，动态RAM(DRAM))可以使用所讨论的实施例。
本公开实施例旨在涵盖落入所附权利要求的宽泛范围之内的所有这样的替换、修改和变型。因此，凡在本公开实施例的精神和原则之内，所做的任何省略、修改、等同替换、改进等，均应包含在本公开的保护范围之内。

Claims (8)

1.一种确定性网络路由与队列调度方法，包括：
创建一个计算转发路径的智能体Ar和一个计算沿路径各节点处的转发周期的智能体Ac；智能体Ar和智能体Ac共享奖励在多智能近端策略优化MAPPO模型中智能体Ar和智能体Ac对应一个Actor网络，智能体Ar和智能体Ac共享一个Critic网络；其中，奖励/>为资源利用率方差和转发时延的综合指数；
以全局网络状态作为评价网络的输入，以状态价值作为评价网络的输出，以最大化期望奖励为优化目标，不断更新网络，选择最优的路由和最优的转发队列来指定确定性流的转发路径和沿途各节点处的周期偏移信息；
其中，所述以全局网络状态作为评价网络的输入，以状态价值作为评价网络的输出，以最大化期望奖励为优化目标，不断更新网络进一步包括：
初始化网络环境；
分别将网络状态输入到智能体Ar和智能体Ac对应Actor网络，获得联合策略Action；
执行策略，获得下一时刻运行状态和全局奖励，并将前后运行状态、策略和奖励存储到缓冲器内；
在达到训练周期的情况下，从缓冲器内获取经验，分别更新Critic网络和Actor网络。
2.根据权利要求1所述的确定性网络路由与队列调度方法，其中，所述方法还包括：
在未达到训练周期的情况下，再次将网络状态输入到智能体Ar和智能体Ac对应Actor网络，获得联合策略Action。
3.根据权利要求1所述的确定性网络路由与队列调度方法，其中，所述方法还包括：
判断迭代次数是否达到最大值；
在迭代次数未达到最大值的情况下，再次初始化网络环境。
4.根据权利要求1所述的确定性网络路由与队列调度方法，其中，所述方法还包括：
判断迭代次数是否达到最大值；
在迭代次数达到最大值的情况下，若模型收敛，则输出最优的路由和最优的转发队列。
5.根据权利要求1所述的确定性网络路由与队列调度方法，其中，所述方法还包括：
确定训练轮数和更新周期，并初始化迭代变量。
6.一种确定性网络路由与队列调度装置，包括：
模型构建模块，用于创建一个计算转发路径的智能体Ar和一个计算沿路径各节点处的转发周期的智能体Ac；智能体Ar和智能体Ac共享奖励在多智能近端策略优化MAPPO模型中智能体Ar和智能体Ac对应一个Actor网络，智能体Ar和智能体Ac共享一个Critic网络；其中，奖励/>为资源利用率方差和转发时延的综合指数；
调度模块，用于以全局网络状态作为评价网络的输入，以状态价值作为评价网络的输出，以最大化期望奖励为优化目标，不断更新网络，选择最优的路由和最优的转发队列来指定确定性流的转发路径和沿途各节点处的周期偏移信息；
其中，所述调度模块，还用于初始化网络环境；分别将网络状态输入到智能体Ar和智能体Ac对应Actor网络，获得联合策略Action；执行策略，获得下一时刻运行状态和全局奖励，并将前后运行状态、策略和奖励存储到缓冲器内；在达到训练周期的情况下，从缓冲器内获取经验，分别更新Critic网络和Actor网络。
7.一种电子设备，包括存储器、处理器及存储在存储器上并可在处理器上运行的计算机程序，其特征在于，所述处理器执行所述程序时实现如权利要求1至5任意一项所述的确定性网络路由与队列调度方法。
8.一种非暂态计算机可读存储介质，其特征在于，所述非暂态计算机可读存储介质存储计算机指令，所述计算机指令用于使计算机执行权利要求1至5任意一项所述的确定性网络路由与队列调度方法。
CN202210822548.9A 2022-07-12 2022-07-12 确定性网络路由与队列调度方法及装置 Active CN115484205B (zh)

Priority Applications (1)

Application Number Priority Date Filing Date Title
CN202210822548.9A CN115484205B (zh) 2022-07-12 2022-07-12 确定性网络路由与队列调度方法及装置

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
CN202210822548.9A CN115484205B (zh) 2022-07-12 2022-07-12 确定性网络路由与队列调度方法及装置

Publications (2)

Publication Number Publication Date
CN115484205A CN115484205A (zh) 2022-12-16
CN115484205B true CN115484205B (zh) 2023-12-01

Family

ID=84422719

Family Applications (1)

Application Number Title Priority Date Filing Date
CN202210822548.9A Active CN115484205B (zh) 2022-07-12 2022-07-12 确定性网络路由与队列调度方法及装置

Country Status (1)

Country Link
CN (1) CN115484205B (zh)

Families Citing this family (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN115987910A (zh) * 2022-12-22 2023-04-18 网络通信与安全紫金山实验室 基于动态运算的队列门控调度方法、系统和存储介质
CN115987913B (zh) * 2022-12-26 2024-10-22 苏州浪潮智能科技有限公司 队列优先级调整方法、装置、电子设备及存储介质
CN117499491B (zh) * 2023-12-27 2024-03-26 杭州海康威视数字技术股份有限公司 基于双智能体深度强化学习的物联网服务编排方法及装置
CN118018382B (zh) * 2024-04-09 2024-06-21 南京航空航天大学 大规模广域开放网络中分布式确定性控制器协同管理方法

Citations (8)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN108765096A (zh) * 2018-06-07 2018-11-06 冯瑞新 一种云网络下共享式卫生间系统
CN112437020A (zh) * 2020-10-30 2021-03-02 天津大学 一种基于深度强化学习的数据中心网络负载均衡方法
AU2021101685A4 (en) * 2021-04-01 2021-05-20 Arun Singh Chouhan Design and development of real time automated routing algorithm for computer networks
CN113328938A (zh) * 2021-05-25 2021-08-31 电子科技大学 一种基于深度强化学习的网络自主智能管控方法
CN113359480A (zh) * 2021-07-16 2021-09-07 中国人民解放军火箭军工程大学 基于mappo算法多无人机与用户协同通信优化方法
CN113791634A (zh) * 2021-08-22 2021-12-14 西北工业大学 一种基于多智能体强化学习的多机空战决策方法
CN114286413A (zh) * 2021-11-02 2022-04-05 北京邮电大学 Tsn网络联合路由选择与流分配方法及相关设备
CN114499648A (zh) * 2022-03-10 2022-05-13 南京理工大学 基于多智能体协作的无人机集群网络智能多跳路由方法

Family Cites Families (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US9628504B2 (en) * 2015-03-09 2017-04-18 International Business Machines Corporation Deploying a security appliance system in a high availability environment without extra network burden
US10681128B2 (en) * 2016-10-12 2020-06-09 Cisco Technology, Inc. Deterministic stream synchronization
CN111694365B (zh) * 2020-07-01 2021-04-20 武汉理工大学 一种基于深度强化学习的无人船艇编队路径跟踪方法
CN114745317B (zh) * 2022-02-09 2023-02-07 北京邮电大学 面向算力网络的计算任务调度方法及相关设备

Patent Citations (8)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN108765096A (zh) * 2018-06-07 2018-11-06 冯瑞新 一种云网络下共享式卫生间系统
CN112437020A (zh) * 2020-10-30 2021-03-02 天津大学 一种基于深度强化学习的数据中心网络负载均衡方法
AU2021101685A4 (en) * 2021-04-01 2021-05-20 Arun Singh Chouhan Design and development of real time automated routing algorithm for computer networks
CN113328938A (zh) * 2021-05-25 2021-08-31 电子科技大学 一种基于深度强化学习的网络自主智能管控方法
CN113359480A (zh) * 2021-07-16 2021-09-07 中国人民解放军火箭军工程大学 基于mappo算法多无人机与用户协同通信优化方法
CN113791634A (zh) * 2021-08-22 2021-12-14 西北工业大学 一种基于多智能体强化学习的多机空战决策方法
CN114286413A (zh) * 2021-11-02 2022-04-05 北京邮电大学 Tsn网络联合路由选择与流分配方法及相关设备
CN114499648A (zh) * 2022-03-10 2022-05-13 南京理工大学 基于多智能体协作的无人机集群网络智能多跳路由方法

Non-Patent Citations (2)

* Cited by examiner, † Cited by third party
Title
基于深度强化学习的电力通信网路由策略;朱小琴;袁晖;王维洲;魏峰;张驯;赵金雄;;科学技术创新(36);全文 *
多智能体博弈学习研究进展;罗俊仁;《系统工程与电子技术》;全文 *

Also Published As

Publication number Publication date
CN115484205A (zh) 2022-12-16

Similar Documents

Publication Publication Date Title
CN115484205B (zh) 确定性网络路由与队列调度方法及装置
Shu et al. Multi-user offloading for edge computing networks: A dependency-aware and latency-optimal approach
Wu et al. Multi-agent DRL for joint completion delay and energy consumption with queuing theory in MEC-based IIoT
CN114286413B (zh) Tsn网络联合路由选择与流分配方法及相关设备
Kim et al. Multi-agent reinforcement learning-based resource management for end-to-end network slicing
Jamil et al. IRATS: A DRL-based intelligent priority and deadline-aware online resource allocation and task scheduling algorithm in a vehicular fog network
Shu et al. Dependency-aware and latency-optimal computation offloading for multi-user edge computing networks
CN113064671A (zh) 基于多智能体的边缘云可扩展任务卸载方法
CN114745317A (zh) 面向算力网络的计算任务调度方法及相关设备
CN116541106A (zh) 计算任务卸载方法、计算设备及存储介质
EP4024212B1 (en) Method for scheduling inference workloads on edge network resources
Beraldi et al. Sequential randomization load balancing for fog computing
Zheng et al. Learning based task offloading in digital twin empowered internet of vehicles
Hu et al. Dynamic task offloading in MEC-enabled IoT networks: A hybrid DDPG-D3QN approach
CN117749796A (zh) 一种云边算力网络系统计算卸载方法及系统
Chen et al. Twin delayed deep deterministic policy gradient-based intelligent computation offloading for IoT
Li et al. Profit driven service provisioning in edge computing via deep reinforcement learning
CN116418808A (zh) 一种mec的联合计算卸载和资源分配方法及装置
Bensalem et al. Towards optimal serverless function scaling in edge computing network
Belkout et al. A load balancing and routing strategy in fog computing using deep reinforcement learning
Mukherjee et al. Timed loops for distributed storage in wireless networks
CN115225512A (zh) 基于节点负载预测的多域服务链主动重构机制
Aguirre-Guerrero et al. Congestion control for a fair packet delivery in WSN: from a complex system perspective
Liu et al. Dependency-aware task offloading for vehicular edge computing with end-edge-cloud collaborative computing
Hasan et al. Internet of things task scheduling in cloud environment using particle swarm optimization

Legal Events

Date Code Title Description
PB01 Publication
PB01 Publication
SE01 Entry into force of request for substantive examination
SE01 Entry into force of request for substantive examination
GR01 Patent grant
GR01 Patent grant