Deep Reinforcement Learning meets Graph Neural Networks: exploring a routing optimization use case论文

一、摘要

DRL可用于决策和自动控制等，可以解决自动驾驶网络中的优化问题（如路由优化）。然而，应用于网络的现有的基于DRL的解决方案无法泛化，这意味着在有新的未观察到的网络拓扑时，无法正常运行。原因是，现有的DRL使用标准神经网络（如全连接、卷积），这些网络不适合从图像结构的信息中学习。于是，本文将GNN集成到DRL代理中，并设计了一个特定于问题的动作空间以实现泛化。GNN 是深度学习模型，本质上是为了泛化不同大小和结构的图而设计的。这使得所提出的基于 GNN 的 DRL 代理能够在任意网络拓扑上学习和泛化。论文证明了所提出的模型有较好的泛化性。

二、背景

1. GNN：使用消息传递神经网络（MPNN），每个节点k接受来自所有邻居节点的消息N（k）。通过消息传递函数集合节点的隐藏状态进行传递，聚合各个来自邻居节点的信息后，更新，得到每个节点的新的隐藏状态。

2. DRL ：通过探索状态和动作空间的迭代过程来学习最优策略。给定一个状态s和动作a，缠身过一个新的状态s'和奖励r，目标时找到一种策略，在episode结束时最大化累计奖励。

三、网络优化场景

探讨基于GNN的DRL代理解决光传输网络（OTN）中的路由问题。DRL代理位于控制平面内，具有当前网络状态的全局视图，并且必须在每个流量需求到达时做出路由决策。将流量需求视为从源点到目标节点的流量。

在OTN场景中，DRL通过逻辑拓扑在电域做出路由决策，其中，节点代表可重新配置光分插复用器（ROADM）。边缘时连接它们的预定义光路。DRL代理接受三元组{src、des、bandwidth}定义的不同带宽要求的流量需求。

模型假设：

1.代理必须对每个传入流量需求做出顺序路透决策；

2. 流量需求不能拆分到多个路径；

3.之前的流量需求无法重新路由，并且它们会占用链路容量，直到事件结束。

四、基于GNN的DRL设计

DRL采用DQN算法，其中Q值由GNN计算。定义一个要解决的优化问题的环境，该环境存储网络拓扑和链路特征。此外，环境负责在执行某个操作后生成奖励，指示代理操作是否良好。

网络状态由拓扑链路的特征定义，包括链路容量和链路介数（betweenness）。前者表示链路上的可用容量，后者是从图论继承的中心性度量，指示有多少条路径可能穿过该链接。（介数有助于收敛到良好的策略）。介数的计算：穿过该链路的端到端路径的数量除以路径总数。

为了避免高维动作空间导致计算成本和速度的下降，我们必须限制为一个低维的动作空间。文中为源—目的节点对选择具有k=4个最短路径的集合，即将源—目的节点的操作集限制为k=4个候选路径。

为了表示动作，将其引入网络状态中。特别是，考虑一个额外的链路级特征，即应用路由操作后在链路上分配的带宽。

GNN architecture： 我们考虑链接实体，并在所有链接之间执行消息传递过程。我们选择链接实体，而不是节点实体，因为链路特征定义了OTN路由优化问题。当需要合并节点级功能（例如，I/O缓冲区大小，调度算法）的优化问题时，可以添加节点实体。

1、2行初始化链路才熟等，3-16行为一个while循环。7-9行计算候选路径的q值。第10-行贪婪的选择最大的q值。第11行得出该q值下的动作。第12行根据当前状态和动作，得出下一状态的网络参数等。第13行，有关状态转换的信息存储在经验回放缓冲区，稍后在15行agt.replay()中调用。每M次调用一次。

五、实验结果

性能及泛化性：

A. 评估设置

Tensorflow，Gym

考虑三种流量需求类型，ODU2、ODU3、ODU4，其带宽需求都是ODU0的倍数（8、32、64）。当DRL代理正确分配需求时，它会立即收到奖励，即当前流量需求的带宽，否则奖励为0。如果DRL代理选择的路径中的所有链路都有足够的可用容量来承载此类需求，则认为该需求被成功分配。

对于GNN模型，将链路的隐藏状态h_l设定为27个元素的向量。在每次GNN的前向传播中，使用32个样本批量执行T=7个消息传递步骤。使用的优化器是SGD随机梯度下降。学习率为10^(-4)，动量为0.9。以epsilon=1开始epsilon-greedy探索策略，在70次内保持该epsilon值，之后，称指数衰减。经验缓冲区存储4，000个样本，并以FIFO队列的形式实现。在读出函数中，使用L2正则化及dropout，系数均为0.1。折扣因子Gamma是0.95。

B. 方法（未完待续，复现代码中）