最近产能不足(摸鱼) 回来先继续往下开坑
《Shortest path routing algorithm with dynamic composite weights in SDN networks》
( Cite: D. Todorov, H. Valchanov and V. Aleksieva, "Shortest path routing algorithm with dynamic composite weights in SDN networks," 2021 International Conference Automatics and Informatics (ICAI), 2021, pp. 193-197, doi: 10.1109/ICAI52893.2021.9639512. )
Abstract
随着网络资源的增加，全球使用的路由算法无法提供适应的网络利用和Qos以满足终端的需要用户。SDN的引入可以更好的控制网络流量。本文提出了在SDN网络中最短路径路由动态复合权值算法（shortest path routing algorithm with dynamic composite weights）。
1 Introduction
开篇就说网络最近面临的压力越来越大吧啦吧啦，为了解决这些问题：自然就是要提升网络设备的处理能力，那自然就需要钞能力，但这显然不太合理。
传统的IP网络使用OSPF算法（基于Dijkstra的最短路径算法）。OSPF 路由静态地基于设备之间分配的权重来运行。路由表触发重新计算功能是在网络拓扑改变的前提下才进行。因此，在OSPF中，当报文发生拥塞时，即使总流量负载不高也不能通过替代路径发送。并且，他在交通阻塞的时候也不能提供需求的QoS。
为了提供灵活的网络管理和设置and动态and开销的有效性and适应性，SDN被发明了。然后介绍SDN就不多谈了直接跳到下一段。
路由算法可以被分为两类——分别是静态链路开销的路由算法and动态链路开销的路由算法。为了选到最佳路径，静态链路开销一般是基于跳数，距离or链路能力（serial口，e口，g口）。动态链路开销算法根据更复杂的指标(如可用链路容量、链路利用率或链路上的流量对可用带宽的计算)对报文流做出决策。 这提供了更好的QoS，因为每个包可以根据负载分布在不同的流上。
然后这个算法就是用动态节点(dynamic node)和链路权值(link weights)提供可选的流路径来改善QoS，为了实现自己的算法和测试，大佬们就自己开发了个Openflow controller然后在Mininet模拟器上操作。
2 RELATED WORK
介绍了一下大佬之前的具有源主机和目标主机之间链路发现的简单路由算法(simple routing algorithm with link discovery between source and destination hosts)，该算法是基于收集主机交换的ARP报文信息来填充内存中的“入流表”。每个交换机包含了这个网络中的所有信息，还有在那个接口能找到他们。该算法具有环路发现机制，防止了在网状拓扑中循环报文的传输。 这种算法是被定义为静态的算法，因为他并没有收起网络状态信息(NSI)，交通拥堵的时候也不会有网络路径的改变。它的主要优点是减少了网络流量，降低了控制器的总体负载。
下一段提了一嘴MHA( A Minimum Hop Algorithm )和 WSP ( Widest-Shortest Path Algorithm ) ，都是拓扑变化的时候才改变的时候才分配链路权值。
使用动态路由算法的控制器需要在一个比较短的间隔请求网络状态信息，目的是收集“准确的(当下的)”链路状态信息。控制器根据收集到的信息，计算出最合适的网络流向( flow )，以避免拥塞，满足网络需求。此外，这个控制器可以提供更好的网络利用率和保证一个更好的QoS。
在[9] ( Cite: A. Ali-Sadi, A. Al-Sherbaz, J. Xue, S. Turner, “Routing Algorithm Optimization for Software Defined Network WAN”, AIC-MITCSA, May 2016. ) 里面 大佬们介绍了 SFOP (Shortest-Feasible OpenFlow Path ) 算法 ，用于计算有着可行带宽and最低延迟的最佳路径。这个算法使用了两个参数用于计算最佳路径：i）当前状态的剩余带宽(IncBW)关联矩阵 ( incident matrix of remaining bandwidth (IncBW) for current state ) ，ii) 在现在的网络流向( flow )可能的带宽；在计算出最宽路径和最宽带宽后，该算法将最宽带宽与从交换机接收到的NSI进行比较。
另一个提供客户端和服务器之间连接负载均衡的动态路由算法是用于SDN的Extended Dijkstra最短路径算法 [10] ( Cite: W. Yahya, A. Basuki, J. Jiang, “The Extended Dijkstra’s-based Load Balancing for OpenFlow Network”, IJECE Vol. 5, No. 2, pp. 289-296, April 2015. ) 该算法将边缘权重和节点（交换机）权重都考虑上了，以寻求最合适的路径来规避堵塞。为了计算节点权重，该算法考虑通过该节点的流量之和、该节点每秒处理的流量位数和节点每秒可以处理的比特数。 计算边缘权重(edge weights)的方法是计算是通过这条边的流量、每秒由这条边处理的比特数和每秒可以处理的比特数之和。
静态路由算法相比于动态路由算法要更快的计算流路径，因为他们并不需要通过NSI来进行复杂的计算，以选最优路径。他们最明显的劣势是他们不能避免路径堵塞，不能提供可靠的网络负载平衡或者提供好的QoS。另一方面来说，动态路由算法引入更多的网络流量，并影响带宽，以收集所需的NSI 和可以提供更好的QoS。它们的主要缺点是考虑到未来的近似负荷。
3 PROPOSED ALGORITHM
话题回到了算法本身，是基于动态组合权值的最短路由算法。控制器使用OpenFlow协议以建立交换机双向的交流，以请求NSI和管理流表。这个控制器使用LLDP(Link Layer Discovery Protocol)去寻找交换机之间的链接，还用了ARP来寻找与交换机连接的主机。
A. System modules
Fig. 1 展示了该算法的系统模块，其中包含着最主要的模块是SDN控制器，还有两个子模块：连接模块和路由模块。
SDN控制器模块需要提供主要的功能是建立控制器和使用了OpenFlow协议的入网设备。它也支持用LLDP和ARP信息来收集交换机和主机的连接信息。控制器还使用了额外的交流包来对交换机的健康状态进行检查汇总（类同心跳报文？但是不单止关注着接入状态，估计还要关注网络传输的状态），同时NSI包用于从子模块中收集需要的信息以计算包发送的最佳路径。
连接模块需要提供的功能是映射已连接的交换机和连接的主机之间的链路，通过处理LLDP和ARP消息来识别连接的设备。这个模块同时也设计来操作和储存每一条链路和连接的NSI。其中含有RTT和交换机与链路吞吐量的计算逻辑。
路由模块需要提供的功能是主机之间最可靠的路径，基于连接模块提供的链路信息，然后给控制模块返回新的下一跳路径。为了计算该路径，路由模块使用了链路权值和节点权值，为了减少路径载荷来提供更好的QoS和更低的整体网络载荷。
B. Routing process
在与交换机建立了一个成功的连接之后，控制器需要将所有连接入网的设备进行一个全局的汇总。为了达成这个目的，控制器让Switch A从自己所有开启的端口发一个Packet Out报文，这个Packet Out报文里面包含LLDP包，携带的信息有：port number, MAC address, global identifier（switch的编号）
当LLDP包到达Switch B( Switch A的邻居 )，Switch B就会向控制器发送一个Packet In报文，因为这个从Switch A来的Packet Out报文的目的地址是广播，Switch B不知道怎么操作，所以就给控制器发一个Packet In报文。当控制器收到Switch B发来的包，它会添加一条链路记录，记录了交换机A的传递信息。如果Switch A发的Packet Out报文被主机收到了，主机就直接忽略掉。
为了找到交换机和主机之间的连接，控制器依赖于两个主机之间交换的ARP信息。然后就讲ARP怎么工作（不讲了）。当Switch收到两个host交换的ARP报文，就会给控制器发Packet In报文。
接下来，控制器创建一个后台任务，从交换机和监视器查询NSI，以观察网络状态变化。当控制器讲一个新的节点或者连接插入他自己的数据集，他就会先给“新人”分配一个默认的权值，直到收到Switch发来的“新人”的汇总与开销，才进行替换。
路由过程是基于Dijkstra最短路径算法的，使用了扩展的(extended?)节点和链路权重。SDN网络拓扑可以表现为一个带权的连接图 G=(V,E)，其中V代表一串节点，E代表着边缘。他们都不会是负值，因为这个算法只是要选更少负载的路。对于这个图：
用RTT(v)来表示控制器与节点交换的echo数据包的Round Trip Time的移动平均值；
用Throughput(v)和Throughput(e)表示所有流中v和e的移动平均吞吐量值；
用Capability(v) 来代表v能处理的平均带宽；
用Dropped(e)来代表e丢弃的数据包
(1)定义了节点权重的计算：
nw[v]=\frac{RTT(v) \times Throughput(v)}{Capability(v)}(1)
(2)则定义了边缘权重的计算：
ew[e]=\frac{Throughput(e)}{Bandwidth(e)-Dropped(e)}(2)
Throughput(e) 是基于(3)中调和(?)(harmonic)意义的移动平均权重。
R(t)=\frac{n+1}{\frac{n}{R(t)}+\frac{1}{R(n+1)}}(3)
式中，R(t)为调和均值，是一系列吞吐量测量值，其中t = 0,1,2，…，n-1。
式中单位说明：
RTT的测量单位是秒；
Throughput和Capability是千字节每秒；
对于测量Dropped packets，(2)式中使用的是丢掉的包数；
为了跟踪网络变化，控制器每15秒向所有节点进行请求，并计算新的权重，以及是否有任何节点或边缘挂掉了或添加了新的连接。
C. System workflow
在Fig. 2里面显示了算法的工作流程表。
- 握手报文在交换机之间交换，使用OpenFlow协议连接。在这个过程中，控制器和交换机对OpenFlow的最高版本进行协商，同时，交换机也将自己的状态信息（能力）发给控制器。如果在这个过程中有任何的错误发生，那该连接就会被双方终止掉，然后再重新建立一个新的连接。
- 当一个新的连接成功建立时，那控制器就会向交换机发送一个Flow Mod指令（集合），过程如下：控制器向交换机发送一个Flow Mod Reset信息，让它清空流表。然后再发指令让交换机将所有收到的包重定向到控制器。
- 当成功完成了配置步骤，控制器开启了Discovery Process，控制器就开启了Discovery Process，以收集交换机端口和它连接的设备的信息。为了达成这个目的，控制器让switch从他所有的端口发送LLDP信息。在这种方式下，控制器收集该拓扑的邻居信息。最后，控制器将网络信息保存在它的数据集中。
- 下一步，控制器起了一个后台的任务来间歇性的请求NSI和拓扑变化，同时也间歇性的计算节点和边缘权重。然后它开始监听进来的信息。如果接收到一个Packet In信息，控制器先检查它的以太网类型。
1）如果这个消息是ARP类型，并且是一个以广播为目的地址的报文，同时它也没有被存在任何的交换机连接中，控制器就会存储当前连接的源MAC地址和端口号。在这种方式下，控制器要确保没有重复的host links被创建，所以控制器指示交换机从他的所有端口(除了接收到消息的端口)传递消息。
2）当控制器收到了一个有目的MAC的Packet In消息，控制器就会检索所有设备的信息，然后计算出最佳路径。计算方法是Dijkstra算法，通过计算节点和边缘权重。最后，它生成一个流路径，使用Packet Out指令将消息发送到下一跳。 此外，控制器通过储存源MAC地址和目标IP地址来防止ARP环路。如果相同的信息从交换机发来，控制器就会直接忽略掉。
4. EXPERIMENTAL STUDY AND RESULTS
实验和结果就不放了，有兴趣的自己看吧，都是数据上的东西。
5.CONCLUSION
我来总结.jpg 这篇论文并不侧重算法，而是结构，fig. 2很好地反映了该结构的工作流程，也算是给广大研究者提供了新思路吧。但是并不是很重要的论文！！！读到一半有点点沉没成本的意味在里面了，不过也算是拓宽一下视野......顺便预告一下新坑：《Fat-trees: Universal networks for hardware-efficient supercomputing》，读读经典结构好了...
