软件定义网络中路由更新和流量统计收集的延迟优化

摘要

由于流的动态性，一个软件定义网络通常需要频繁地对它的数据平面做路由更新，来优化如负载均衡等性能指标。大部分已有的解决方法都是基于当前的流的状态来确定一个新的路由方案，然后为当前的流更新转发路径。然而，由于TCAM（三态内容寻址存储器）流表上的更新操作速率较慢，在一个大规模且频繁更新的网络中，路由更新可能会带来严重的延迟。根据最近的研究结果，大部分数据流的持续时间都较短，且整个网络的负载在一段时间之后通常会显著变化，因此如果一次路由更新耗时过长，那么新的路由方案很可能已经不再高效了。除了路由更新外，流统计收集操作的效率也严重影响了网络的整体性能。在软件定义网络中，控制器需要频繁地收集数据平面上交换机的流统计信息作为一些网络应用（如路由更新、攻击检测等）的输入。然而已有的流统计收集方法可能会产生很高的延迟开销，进而会影响这类网络应用的性能。在本文中，我们针对软件定义网络中路由更新和流统计收集两大重要场景，对延迟优化展开研究。本文的主要贡献为:
　　提出了实时路由更新方法，结合控制平面上的路由选择和数据平面上的更新调度来优化网络性能。我们形式化地给出延迟满足的路由更新(DSRU)问题，并证明了它是Np-难的。我们提出了基于随机舍入的更新算法，并分析了算法的近似性能比。最后，我们将提出的方法部署在SDN实验平台和仿真平台上。实验与仿真的结果表明，与已有路由更新算法相比，我们的算法可以在保证得到非常接近的路由性能（只增加大约3％的链路负载率）的前提下，减少约60％的路由更新延迟。
　　针对流统计收集的延迟优化提出了基于掩码收集的延迟代价最优流统计收集(CO-FSC)方式。我们给出了一个近似比为f（f为每条流经过的交换机节点数的最大值）的基于舍入的算法，以及一个基于对偶转化的贪心算法。我们对提出的算法进行了大量的仿真实验，结果表明与已有算法相比，我们的算法可减少45％以上的延迟开销。

目录

声明

致谢

摘要

第1章 绪论

1．1 研究背景与意义

1．2 国内外研究现状

1．2．1．软件定义网络下的网络更新

1．2．2．软件定义网络下的流统计收集

1．3 研究内容

1．4 论文组织结构

1．5 本章小结

第2章 软件定义网络架构

2．1 OpenFlow协议

2．2 软件定义网络架构

2．2．1．转发设备

2．2．2．控制器

2．2．3．南向接口

2．2．4．北向接口

2．3 本章小结

第3章 基于路由选择和更新调度的实时网络更新

3．1 已有方法的不足

3．2 问题定义

3．2．1．网络模型

3．2．2．TCAM更新的延迟模型

3．2．3．无拥塞约束

3．2．4．一致性约束

3．2．5．延迟满足的路由更新(DSRU)问题定义

3．3 算法设计

3．3．1．问题的形式化

3．3．2．Dionysus算法介绍

3．3．3．基于规约的算法

3．3．4．分析

3．3．5．RRSU算法的修正

3．3．6．讨论

3．4 实验结果

3．4．1．性能指标和Benchmarks

3．4．2．Testbed实验

3．4．3．仿真结果

3．5 本章小结

第4章 流统计信息的获取—基于掩码的流统计收集

4．1 已有方法的不足

4．2 问题定义

4．3 算法设计

4．3．1．基于舍入的算法

4．3．2．近似比分析

4．3．3．基于对偶转化的贪心算法

4．4 实验结果

4．4．1．性能指标与环境设置

4．4．2．仿真实验

4．5 本章小结

第5章 总结与展望

5．1 全文工作总结

5．2 未来工作展望

参考文献

在读期间发表的学术论文与取得的研究成果