徐明伟 ¹ , 夏安青 ¹ , 杨芫 ¹ , 王宇亮 ² , 桑猛 ²
1. 清华大学 计算机科学与技术系, 北京 100084;
2. 比威网络技术有限公司, 北京 100084

收稿日期: 2016-08-03
基金项目: 国家“八六三”高技术项目（2015AA015701）
作者简介: 徐明伟(1971-),男,教授。E-mail:xmw@cernet.edu.cn


摘要：建设天地一体化网络是中国的一项重要工程。在空间网络中引入IP协议族及相关路由技术能充分发挥互联网的长处，更加快速和高效地实现多网融合。然而，空间网络的特殊性使得传统互联网的路由技术不能直接被使用。该文提出一种基于传统域内路由协议OSPF的天地一体化网络域内路由协议OSPF+，利用卫星运动轨迹可以预先计算的规律，引入拓扑预测，结合扩展的邻居状态机来优化链路状态数据库的同步，在空间网络自治系统中实现低开销、高稳定性的自适应动态路由。模拟实验结果表明：OSPF+能在约1 s的时间内快速完成路由收敛，且达到98%以上的稳定性。
关键词： 天地一体化网络 空间网络 卫星网络 域内路由协议
Intra-domain routing protocol OSPF+ for integrated terrestrial and space networks
XU Mingwei¹, XIA Anqing¹, YANG Yuan¹, WANG Yuliang², SANG Meng²
1.Department of Computer Science and Technology, Tsinghua University, Beijing 100084, China;
2.BitWay Network Technology Company, Beijing 100084, China


Abstract:Constructing an integrated terrestrial and space network is one of the key projects in China. Heterogeneous networks can be efficiently integrated using the IP protocol family in space networks to leverage the advantages of the Internet. However, traditional routing techniques cannot be used directly due to the special characteristics of space networks. This paper describes an extended traditional intra-domain routing protocol based on OSPF for network communications in space. The protocol uses topology predictions based on the regular motion of satellites and extends the neighbor state machine to optimize the synchronization of link-state databases to achieve efficient, stable dynamic self-adaptive routing. Simulations show that this protocol has a convergence time of less than 1 second and greater than 98% stability.
Key words: integrated terrestrial and space networkspace networkssatellite networksintra-domain routing protocol
互联网技术的飞速发展，使得在太空内实现不间断通信成为可能。随着中国在空间探索、应急通信、海洋考察等领域应用需求的不断扩张，建设由空间网络、地面互联网和移动通信网深度融合的天地一体化网络迫在眉睫。实现空间网络与地面互联网和移动通信网高效融合的关键在于实现互联网的核心层——网络层的融合。在互联网诞生之初，网络层和IP协议族的出现打破了异构网络之间的界限，实现了全球互联。在空间网络中引入IP协议族能充分发挥互联网技术的长处，用较低的开销更快速地实现天地一体化网络。
然而，现有的互联网路由技术不能直接用于空间网络，这是因为： 互联网拓扑结构较为稳定，路由器节点分布在用户集中的区域，且节点不受能耗、体积、重量等因素限制，性能较高； 而空间网络主要由同步轨道(GEO)卫星、中轨道(MEO)卫星和低轨道(LEO)卫星组成，部分节点如低轨卫星节点相对地面高速运动，拓扑动态性强，节点的分布由卫星轨道等物理特性决定，导致用户流量分布不均匀，且空间路由器节点的能耗、体积、重量都受到卫星承载能力的限制，性能较低。此外，空间链路还具有高延时、低带宽、高误码率等特点。传统的路由协议在空间网络中会面临链路状态通告频繁、路由重计算开销大、路由收敛缓慢、路径所提供的服务质量难以满足要求等问题。因此，亟需设计面向天地一体化网络并适应空间网络特点的路由协议。由于多网融合的需求，天地一体化网络与互联网一样需要域间路由协议与域内路由协议。为了在空间网络自治系统中实现低开销、高稳定性的自适应动态域内路由协议，需要充分利用组成空间网络的卫星的运动具有的规律性和可计算性。
本文提出一种基于传统域内路由协议OSPF的天地一体化网络域内路由协议OSPF+。OSPF+在传统的域内路由协议OSPF的基础上引入了拓扑预测功能，结合扩展的邻居状态机来优化链路状态数据库的同步，降低了链路状态洪泛和路由重计算的开销，提高了协议的运行效率和稳定性。模拟实验结果表明： OSPF+能在约1s的时间内快速完成路由收敛，且达到98%以上的稳定性，远远优于OSPF。
1 相关工作随着通信卫星技术的发展和星上设备路由、交换能力的提高，卫星之间可以通过星间链路组成网络，以提供更丰富的服务，代表性的系统包括Inmarsat、铱星、TSAT(transformational satellite communications system)等。空间网络依据组成网络的卫星是否在同一轨道高度上可以分为单层卫星网络和多层卫星网络，位于不同层的卫星之间通过层间链路进行通信。因此，空间网络路由方案可分为单层和多层卫星网络路由方案。
在单层卫星网络路由方案中，最先提出的是基于连接的路由方案。这类方案通常采用虚拟拓扑策略^[1]，根据卫星的运动情况划分出一系列离散的时间片，集中式地为每个时间片内的拓扑计算路由并通告到每个卫星节点。在这一背景下，很多研究将优化目标定为最小化链路转交，以增加每个时间片的长度，减少路由计算、通告和切换的开销。例如Werner等^[2]提出使用ATM(asynchronous transfer mode)技术建立路径，通过选择合适的路径来最小化路径转交； Chang等^[3]使用有限状态机给拓扑变化建模并优化路由更新； Cao等^[4]则利用交叉熵模型启发式地求解按需路由的快速收敛问题。这类基于连接的路由方案的另一个优化目标是减少新加入连接的阻塞概率，主要应用于传统电信行业的实时话音通信等业务。采用这类方案的网络与基于IP技术的互联网融合时会有较大的开销。此外，这类方案抵抗卫星节点和链路故障的能力较为欠缺。
单层卫星网络路由也可以采用分布式计算的方法，这类方法通常采用虚拟节点策略^[5]，充分利用同一轨道高度卫星间相对位置的变化较小的特点来寻址和路由，从而避免时间片的划分。典型方案包括Hashimoto等^[6]提出的基于IP的方案、Ekici等^[7]提出的基于数据报的方案等。然而，已有的方案没有充分继承互联网动态路由协议的优点，例如对故障的抵抗能力还较低，甚至有可能发生路由环路。
多层卫星网络的引入使得路由方案的设计更加灵活。其主要目标一方面在于利用位于更高层的卫星更广的覆盖面积减少路径经过的跳数，以提供更好的服务质量，例如Lee等^[8]提出的方案； 另一方面在于将卫星分组管理，由上层卫星收集拓扑和路由信息，计算后下发给下层卫星，以提供更好的可扩展性，例如Akyildiz等^[9]提出的方案。近些年来，这类方案的研究比单层卫星网络路由的研究更受关注^[10-11]。Lu等^[12]对卫星网路路由研究做了较全面的综述，在此不再赘述。
本文的工作属于卫星网络分布式路由方案，主要目标不是设计复杂的算法和机制来满足特定的需求，而是期望以较小的开销来解决传统互联网的域内路由协议运用在卫星网络中的问题，使空间网络与互联网的高效融合成为可能。本文方案并不局限于单层或多层网络，因为在天地一体化网络的架构中，不同层次的网络可以通过划分自治域的方式来充分利用高层卫星并加强路由可扩展性，本文关注的重点在域内路由。此外还需要说明的是，本文讨论的路由方案(包括前面提到的相关工作)属于建立实时通信的路由方案，而延迟容忍网络中的路由方案^[13]属于不同的通信模式，不在本文讨论的范畴。
2 OSPF+设计与实现OSPF是互联网中广泛使用的域内路由协议。OSPF通过Hello协议动态维护邻居状态，通过链路状态数据库(link state database，LSDB)的洪泛使域内网络所有节点拥有一致的全网拓扑信息，并使用Dijkstra算法计算到达目的节点的最短路径。当拓扑发生变化时，域内网络中所有节点重新获取一致的拓扑信息并计算路由的过程称为域内路由收敛(简称路由收敛)。空间网络中拓扑变化较为频繁，如果路由频繁收敛则会造成带宽等资源的开销，在收敛过程中还可能产生路由黑洞和环路，造成分组丢失和通信中断。OSPF+协议继承了OSPF的基本功能，并设计了相应的机制来避免不必要的路由收敛和加速必要的路由收敛。首先，OSPF+采用虚拟节点策略来对卫星节点进行寻址和路由，同一卫星节点及其接口始终采用固定的IP地址，避免了由于卫星相对地球表面的位置变化导致的地址变化，从而避免由此导致的路由收敛。然而即使如此，卫星节点之间的相对位置还是会有一定程度的变化。
空间网络中的拓扑变化大致可以分为2类。一类是由于通信信道受辐射干扰造成误码导致空间链路短时间内中断。这类拓扑变化虽然会造成一定的数据包丢失，但远远比不上路由重新收敛一次的开销，此时应该避免路由收敛。另一类是由于卫星运动到特定区域造成天线无法对正，例如对于极地轨道星座，在极地附近同一高度不同轨道的卫星之间的链路将被关闭。这类拓扑变化导致特定的链路在较长一段时间不可用，使用了它们的路径必须重新进行计算，此时路由收敛不可避免。然而由于这类拓扑变化可以根据卫星运动的规律性提前计算出来，因此可以对这类路由收敛进行加速，使得网络快速重新回到端到端可达的状态。
基于上述分析，本文设计了OSPF+协议，引入了拓扑预测功能，结合扩展的邻居状态机来优化链路状态数据库的同步，降低了链路状态洪泛和路由重计算的开销，提高了协议的运行效率和稳定性。基于一款商用路由器实现了OSPF+协议，其路由软件基于Quagga-0.99.21 版本。该路由器将作为天地一体化网络演示系统原型的重要组成部分，为未来制造真实上星的空间路由器奠定基础。
2.1 拓扑预测的引入拓扑预测的目的在于使每个空间路由器节点知晓其所连接的链路发生的状态变化是否由于卫星运动所导致。这一信息可以通过预测的链路开始时刻和链路结束时刻这2个参数来进行抽象。为了计算这2个参数，首先将卫星轨道六参数(半长轴、偏心率、倾角、升交点黄道经度、近日点幅角和指定历元的平近点角)作为输入，使用SGP4(simplified general perturbations No.4)或SDP4(simplified deep space perturbations No.4)^[14]算法计算出任意时刻卫星的位置矢量和速度矢量，然后根据卫星姿态和每个接口(天线)的可见范围参数判断邻居卫星节点间是否能建立链路。为了较为精确地计算出连接开始和结束的临界时间，可以采用限定误差的二分查找算法进行搜索。
对于OSPF+来说，每个空间路由器只需要知道自己与邻居节点间的链路情况，而每个卫星通常都有专门的控制计算机保存自己的轨道六参数，因此还需要知道邻居的轨道参数情况。一种方法是利用Hello报文来传递卫星的轨道参数。OSPF的Hello报文中预留了一些可选项，OSPF+可以增加专门的标志位来实现Hello报文携带轨道参数。由于每个轨道参数占4 B，OSPF+对一条链路只增加了4 B×6×2=48 B的开销。然而这种方法需要空间路由器进行较多的计算，不适用于一些计算和存储能力有限的小型卫星。另一种方案是利用地面设备强大的计算能力，直接计算出空间网络中各条链路的开始和结束时刻，并通告给对应的卫星节点。这样做降低了对卫星计算能力的要求，并能减少星上能源消耗，延长使用寿命。图 1给出了本文实现的采用集中式计算进行拓扑预测的OSPF+系统结构。

图 1 OSPF+系统结构

图选项

2.2 邻居状态机的扩展在OSPF协议中，当发现邻居不可达时，不分原因统一将邻居状态置为Down。OSPF+对邻居状态机进行了扩展，新增了Leaving状态，分别针对不同原因的拓扑变化进行处理。节2提到的第1类拓扑变化属于不可预测的瞬时链路中断，可以通过Hello协议检测出来，此时邻居状态保持Full不变以避免不必要的路由收敛； 而第2类拓扑变化属于可以预测的链路中断，此时将邻居状态从Full转换到Leaving，表示双方只是暂时不可达，而不是Down。对于星间链路故障，与传统OSPF协议相同，将邻居状态置为Down。扩展以后的邻居状态机如图 2所示。

图 2 OSPF+邻居状态机

图选项

当邻居状态为Leaving时，路由器仍然需要产生链路状态通告(link-state advertisement，LSA)并通告给网络中其他节点。此外，该路由器本身还可能会收到来自其他节点的LSA。OSPF+为Leaving邻居状态建立NewLSAsList列表，用于保存收到的这类LSA。Leaving状态将保持到发生以下事件之一为止：
1) 当收到邻居的Hello报文时，状态从Leaving转换到ExChange，并准备进行数据库同步，此时仅需同步NewLSAsList中的内容；
2) 当在一个轨道周期内未收到邻居的Hello报文时，状态由Leaving转换到Down；
3) 若NewLSAsList中LSA数量超出存储空间限制，状态由Leaving转换到Down。
OSPF+的邻居状态机更加全面而准确地描述了空间网络的邻居状态及它们之间的转换关系。Leaving状态的引入使得当邻居恢复可达时，跳过了握手和协商过程而直接进入ExChange状态，并利用上一次协商的主从关系进行链路状态数据库的同步，减少了协议开销； 同时利用NewLSAsList提高了同步效率，无须同步整个数据库。最后，通过与拓扑预测相结合，当可预测的链路断开发生时，OSPF+不用等待4个Hello报文的周期，可直接判断邻居不可达，加速了路由收敛。
2.3 讨 论除了协议本身，影响OSPF+性能的一个重要因素是链路权值的设置。为了减小频繁配置链路权值带来的开销，应当尽可能采用固定的链路权值。传播延迟、流量均衡、误码率等都是设置星间链路权值时所需要考虑的因素。此外，由于卫星的高速移动，接入的用户发生和流量需求也在发生变化，如何使用相对静态的链路权值满足随时间和空间动态变化的流量需求是空间网络路由中一个具有重要意义的研究课题。本文将一条星间链路的权值设为其传播延迟的最大值，以最小化传播延迟带来的端到端延迟。
OSPF+作为自适应的动态路由协议，突破了很多已有空间网络路由技术依赖于固定星座结构的限制，更加适应天地一体化网络灵活多变的组网趋势，且可以通过合理的链路权值配置实现等权值多路径传输，通过IP地址划分满足多种业务需求，以及通过层次化路由满足可扩展性的需求。
3 实验性能评估基于实现的OSPF+原型系统，搭建了仿真环境，利用模拟的星间链路来验证协议的有效性。然而由于设备数量的限制，难以仿真得出大规模网络中的协议性能。因此在NS2网络模拟软件中实现了OSPF+协议，利用卫星工具箱软件(STK)生成真实的星历数据并构建模拟场景。网络包含14个LEO卫星，分布在4条相同高度均为776 km的极地轨道上，4条轨道在初始时刻与0°经线的夹角分别为43°、 106°、 169°和201°，每条轨道包含的卫星个数分别为5、 5、 2和2。 整个网络共包含10条轨道内链路和8条轨道间链路。模拟总时长为两个系统周期即2×6 024 s。 图 3给出了模拟进行到第 550 s 时平面化之后网络的拓扑结构。图 4则显示了一个系统周期内8条轨道间链路随模拟时间变化的连通情况。

图 3 550 s时卫星网络平面拓扑

图选项

图 4 轨道间链路连通情况

图选项

本文模拟了5种星间链路参数组合，其链路带宽依次为1 000、 1 000、 100、 100和10 Mb/s。 传播延时依次为25、15、15、15和15 ms，误码率依次为10^-6、 10^-6、 10^-6、 10^-4和10^-4。本文比较了OSPF+和传统OSPF，评价指标为路由收敛时间和稳定性。其中路由稳定性的定义为： 网络中接连两次发生链路中断的时间段内路由协议未处于收敛过程的时间除以接连两次链路中断的时间间隔。
图 5显示了不同星间链路参数下的模拟实验结果。可以看到每一组实验结果的差别很小，说明链路带宽、延时和误码率对于路由收敛的影响很小。 OSPF+的平均路由收敛时间小于1 s，比OSPF的缩短了40 s左右。这是因为OSPF对于链路中断时邻居不可达的判断需要4个Hello报文周期的时间，而OSPF+可以根据拓扑预测的结果直接判断。路由稳定性方面，OSPF+达到了接近100%的稳定性，而OSPF则不到80%。图 6显示了当链路参数为10 Mb/s、 15 ms、 10^-4时的实验结果随时间的变化。可以看到除了OSPF的稳定性，其他指标的变化程度都不大。这表示在某些时刻，OSPF需要花费大量的时间来进行路由收敛。OSPF+通过合理的设计，有效避免了不必要的路由收敛，加速了必要的路由收敛，取得了预期的效果。

图 5 不同链路参数下的路由收敛时间与稳定性

图选项

图 6 路由收敛时间与稳定性随时间的变化

图选项

4 结 论本文设计并实现了天地一体化网络中的域内路由协议OSPF+。在传统互联网域内路由协议OSPF的基础上，结合空间卫星网络的特点，引入了拓扑预测以区分链路中断发生的原因，并设计了扩展的邻居状态机，提高了协议在处理不同原因链路中断时的效率。基于真实卫星数据的模拟实验验证了OSPF+的有效性。

参考文献

[1]	Journal of Central South University(Science and Technology), 41(2):649-654.--> Chang H S, Kim B W, Lee C G, et al. Topological design and routing for low-earth orbit satellite networks[C]//Proc of IEEE GLOBECOM. Piscataway, NJ, USA:IEEE Press, 1995:529-535.
[2]	Journal of Central South University(Science and Technology), 41(2):649-654.-->Werner M, Delucchi C, Vogel H J, et al. ATM-based routing in LEO/MEO satellite networks with intersatellite links[J]. IEEE Journal on Selected Areas in Communications, 1997, 15(1): 69–82. DOI:10.1109/49.553679
[3]	Journal of Central South University(Science and Technology), 41(2):649-654.-->Chang H S, Kim B W, Lee C G, et al. FSA-based link assignment and routing in low-earth orbit satellite networks[J]. IEEE Transactions on Vehicular Technology, 1998, 47(3): 1037–1048. DOI:10.1109/25.704858
[4]	Journal of Central South University(Science and Technology), 41(2):649-654.--> Cao J H, Stefanovic M. Cross entropy accelerated ant routing in satellite networks[C]//Proc of the American Control Conf. Piscataway, NJ, USA:IEEE Press, 2010:5080-5087.
[5]	Journal of Central South University(Science and Technology), 41(2):649-654.-->Lu Y, Sun F, Zhao Y. Virtual topology for LEO satellite networks based on earth-fixed footprint mode[J]. IEEE Communications Letters, 2013, 17(2): 357–360. DOI:10.1109/LCOMM.2013.011113.122635
[6]	Journal of Central South University(Science and Technology), 41(2):649-654.--> Hashimoto Y, Sarikaya B. Design of IP-based routing in a LEO satellite network[C]//Proc of the 3rd International Workshop on Satellite-Based Information Services. New York, NY, USA:ACM, 1998:81-88.
[7]	Journal of Central South University(Science and Technology), 41(2):649-654.-->Ekici E, Akyildiz I F, Bender M D. A distributed routing algorithm for datagram traffic in LEO satellite networks[J]. IEEE/ACM Transactions on Networking, 2001, 9(2): 137–147. DOI:10.1109/90.917071
[8]	Journal of Central South University(Science and Technology), 41(2):649-654.--> Lee J, Kang S. Satellite over satellite (SOS) network:A novel architecture for satellite network[C]//Proc of IEEE INFOCOM. Tel Aviv, Israel:IEEE Press, 2000:315-321.
[9]	Journal of Central South University(Science and Technology), 41(2):649-654.-->Akyildiz I F, Ekici E, Bender M D. MLSR:A novel routing algorithm for multilayered satellite IP networks[J]. IEEE/ACM Transactions on Networking, 2002, 10(3): 411–424. DOI:10.1109/TNET.2002.1012371
[10]	Journal of Central South University(Science and Technology), 41(2):649-654.-->Long F, Xiong N, Vasilakos A V, et al. A sustainable heuristic QoS routing algorithm for pervasive multi-layered satellite wireless networks[J]. Wireless Networks, 2010, 16(6): 1657–1673. DOI:10.1007/s11276-009-0220-z
[11]	Journal of Central South University(Science and Technology), 41(2):649-654.-->Nishiyama H, Kudoh D, Kato N, et al. Load balancing and QoS provisioning based on congestion prediction for GEO/LEO hybrid satellite networks[J]. Proceedings of the IEEE, 2011, 99(11): 1998–2007. DOI:10.1109/JPROC.2011.2157885
[12]	Journal of Central South University(Science and Technology), 41(2):649-654.-->卢勇, 赵有健, 孙富春, 等. 卫星网络路由技术[J]. 软件学报, 2014, 25(5): 1085–1100.LU Yong, ZHAO Youjian, SUN Fuchun, et al. Routing Techniques on Satellite Networks[J]. Journal of Software, 2014, 25(5): 1085–1100. (in Chinese)
[13]	Journal of Central South University(Science and Technology), 41(2):649-654.-->林闯, 董扬威, 单志广. 基于DTN的空间网络互联服务研究综述[J]. 计算机研究与发展, 2014, 51(5): 931–943.LIN Chuang, DONG Yangwei, SHAN Zhiguang. Research on space internetworking service based on DTN[J]. Journal of Computer Research and Development, 2014, 51(5): 931–943. (in Chinese)
[14]	Journal of Central South University(Science and Technology), 41(2):649-654.--> Lewandowski A, Burda R, and Wietfeld C. A multiscale real-time navigation and communication satellite simulation model for OMNeT++[C]//Proceedings of the 1st International Conference on Simulation Tools and Techniques for Communication, Networks and Systems & Workshops. Marseille, France:ACM, 2008, 87:1-8.