基于流量开销模型优化互联和路由策略的理论研究和实际应用

Peering strategy and routing strategy have significant implications on ISPs' business. However, previous research efforts in this area focused only on how to accomplish particular traffic distribution goals through routing selection, without any considerations on the influence of peering strategy on routing strategy and ISPs' business. Almost all of the few works on peering strategy are about peering negotiation techniques or peering conditions. There lacks mathematical formulation and analysis of optimizing ISPs networks by making proper peering decisions and routing decisions...In this research effort, we formulate ISPs' peering and routing strategy as an optimization problem based on a reasonable abstraction of ISP networks. We propose a traffic cost distribution model to solve the optimization problem using greedy algorithms that can be applied in real networks. We further study the challenges, such as forwarding loops and configuration automation, during updating network configurations to implement the optimal strategy derived by greedy algorithms. Finally, based on these research results, we design and implement a prototype to help network operators make decisions and configure networks. The decision support and result prediction functions of our prototype are necessary complement to current network management systems that focus only on monitoring of historical and real-time network status.

互联决策和路由决策是ISP运营中最重要的两个问题。之前该领域的研究主要集中在通过路由选择实现特定的流量分布目标，忽视了互联决策对路由决策和ISP业务的影响。而对互联决策的少量研究则侧重在互联协商的过程和互联建立的条件上，缺少对通过互联决策优化ISP业务的数学建模研究。本课题在对网络进行合理抽象的基础上，对ISP通过互联和路由决策优化网络的行为进行数学建模。基于流量开销分配模型，研究实际网络可用的互联和路由策略优化算法。并分析在更新网络配置实现优化策略的过程中的性能稳定性和自动化问题，研究其解决方案。在这些研究的基础上，实现支持预测分析和交互调整的互联和路由策略优化的决策支持和自动化系统。该系统的预测分析和决策支持功能，是对目前网络管理系统仅关注网络历史和当前状态监控的必要补充。

互联决策和路由决策是 ISP 运营中最重要的两个问题。之前该领域的研究主要集中在通过路由选择实现特定的流量分布目标,忽视了互联决策对路由决策和 ISP 业务的影响。而对互联决策的少量研究则侧重在互联协商的过程和互联建立的条件上,缺少对通过互联决策优化ISP业务的数学建模研究。.课题的主要研究内容和研究成果如下：.（1）.互联和路由策略优化算法.第一，基于Shapley Value和合作博弈的理论基础，课题组提出了最优供应商选择算法。利用全球互联网的域间拓扑数据，发现目标ISP（待优化网络）的竞争ISP和合作ISP，根据本地ISP的域间流量特性，计算各潜在互联对象的互联价值，从而选择最优的互联供应商。.第二，提出了最优对等互联供应商选择算法。我们总结提出三个免费对等互联的可测量评估标准：接入点地理位置间的距离、假设对等互联建立后该链路上的流量、以及潜在对等互联对象在全网中的层次地位。基于这三个评价指标，可以建立对等互联评估框架，不断缩小潜在互联对象集合，完成对等互联运营商的选择。.第三，在路由策略方面，进行了路由绕行情况和路由优化性评估研究。我们通过traceroute测量获取全球路由的数据集。利用CAIDA和PEERDB的数据，理解造成绕行的原因，针对这些原因提出优化策略。.第四，特别针对中国互联路由的情况进行绕行分析。测量结果显示，运营商之间较为广泛的存在非必要的国际绕行，对网络性能产生了重要影响。此外，我们结合国际国内的域间结算情况，分析了产生绕行的潜在原因。.（2）.网络管理的自动配置算法.课题组针对两种典型的网络场景进行了自动配置策略的研究。.第一，提出了云网络里的多播路由配置策略算法。通过设计实现多播路由树的自动生成算法，提高了多播路由树的路由效率，并具有良好的可扩展性。.第二，基于现有的ElasticSwitch，提出了服务质量控制自动配置策略算法，帮助网络管理人员实现了服务质量控制的自动配置。.（3）.网络管理智能决策信息系统的原型设计研发 .该信息系统从多个信息源采集对网络管理决策有帮助的数据，通过该系统的界面统一提供给网络管理员，并支持各种查询分析功能。同时，该系统包括了本课题中提出的供应商互联选择策略优化算法、免费对等互联策略优化，为网络管理员提供直接的决策支持。