On the Trade-off Analysis of Centralized and Distributed Routing in Delay Tolerant Satellite Networks Pablo G. Madoery Juan A. Fraire Fernando D. Raverta Jorge M. Finochietto pablo.madoery juan.fraire fernando.raverta jorge.finochietto @alumnos.unc.edu.ar @unc.edu.ar @unc.edu.ar @unc.edu.ar CONICET, Instituto de Estudios Avanzados en Ingenierı́a y Tecnologı́a (IDIT) Universidad Nacional de Córdoba (UNC), Argentina 1 Introduction Large-scale satellite networks are becoming increas- Abstract ingly popular as a means to provide high quality im- agery, video and communication services around the Given that satellite networks cannot assume globe [1]. Efficient space-terrestrial communication continuous connectivity among nodes, an ar- technologies, capable of successfully moving large vol- chitecture known as Delay Tolerant Network- umes of data between space and ground networks, are ing (DTN) has been proposed as an appealing a key element in these networks. In this context, De- communication paradigm. However, as space lay Tolerant Networking (DTN) has been identified as networks continue to grow in both number a novel approach which can meet this goal in a cost- and size, the process of routing and forward- effective way by relaxing communication requirements ing traffic is rapidly becoming computation- and network infrastructure usually assumed in tradi- ally expensive and challenging. Since these tional protocols. The DTN architecture, originated networks usually exhibit predictable trajec- from deep-space and interplanetary networking, em- tories and communication opportunities, the braces the concept of occasionally-connected networks research community has proposed to provide that may suffer from frequent partitions, high delay, nodes with scheduled contact plans in advance and that may be comprised of more than one diver- in order to make distributed routing decisions gent set of protocols [2]. To this end, a bundle layer as they generate or receive traffic. On the that exists at a layer above the transport (or other) other hand, a more attractive solution for the layers of the network, employs a persistent storage on conservative space industry seems to be a cen- each DTN node to store-carry-and-forward data pack- tralized scheme. Based on a Software-Defined ets called bundles as transmission opportunities be- Network (SDN) approach, a route table can be come available. computed on ground and then provisioned to In the case of space-based networks, the forthcom- nodes in space, which would no longer run any ing episodes of communications and their properties routing intelligence on board, only forward- can be determined in advance based on orbital dynam- ing. In this work we analyze the dichotomy ics. These types of deterministic DTNs are known as between distributed and centralized routing scheduled DTNs, and can take advantage of a contact schemes in the context of DTN and provide plan comprising the future network connectivity in or- insights regarding important aspects to take der to optimize data forwarding. Indeed, as showed into account when designing and managing in previous works [3, 4, 5, 6, 7, 8], contact plans can satellite networks. be properly designed in order to optimize data deliv- ery and/or reduce energy consumption. Furthermore, the use of distributed routing solutions such as Con- Copyright c by the paper’s authors. Copying permitted for private and academic purposes. tact Graph Routing (CGR) [9, 10] allows each DTN In: Proceedings of the IV School of Systems and Networks node to make efficient routing decisions based on the (SSN 2018), Valdivia, Chile, October 29-31, 2018. Published beforehand provisioned contact plan as they generate at http://ceur-ws.org or receive traffic. On the other hand, a more attractive and con- trollable solution for the conservative space industry seems to be a centralized Software Defined Network- ing (SDN) approach [11]. In this case, each route table can be computed with a CGR or other routing algo- rithms on ground, and then provisioned to nodes in space, which would no longer run any routing intelli- gence on-board, only forwarding. In this context, the present work aims to provide Figure 1: Store-carry-and-forward flow in space DTNs an analysis on the trade-off between a distributed and bundle can be transmitted. Therefore each temporal a centralized utilization of CGR algorithms. In Sec- route is conformed by a sequence of contacts, which, tion 2 we provide some background on how routing as we describe in the next section, result predictable is carried out in space DTNs. Then, in Section 3 we in space DTNs and can be exploited with different describe the specific routing schemes which will be an- schemes in order to achieve a good network perfor- alyzed by means of simulations. Afterwards, in Sec- mance. tion 4 we evaluate the schemes through simulations of two realistic satellite constellations. Finally, we dis- 2.3 Workflow in Space DTNs cuss the relevance of the results and summarize them in Section 5. As shown in Figure 2, the workflow in space DTNs goes through four stages: (i ) planning, (ii ) routing, 2 Background (iii ) enqueuing and (iv ) forwarding. In the planning stage (i ), contact plans are deter- 2.1 Store-Carry-and-Forward mined by a central entity (a ground station or a Mis- In DTN, Bundle Protocol data units (called bundles) sion Operation Center (MOC)) based on the estima- are forwarded in a store-carry-and-forward fashion tion of future episodes of communication. This task without assuming the next-hop node will instantly be involves taking into account the physical disposition available to respond. Figure 1 illustrates a typical de- and orientation of nodes through time as well as their layed and disrupted space-terrestrial network where a communication system configuration (antenna, modu- rover in another planet (node 1) needs to send bun- lation, transmission power, etc.). As a result, orbital dles to a ground station (node 3). Since there is no propagators and communication models are combined direct communication between the source and destina- to determine the contact plan which can be further tion nodes, data needs to go through an intermediate tuned to reduce energy consumption or remove con- satellite (node 2). However, because of signal prop- flicting contacts [6, 7, 8]. Furthermore, unlike the In- agation, the transmission opportunity window (a.k.a. contact) between node 1 and 2 is highly delayed, for- Topology Predictable but bidding node 1 to assume node 2 can instantaneously there can be confirm reception of bundles. Also, the communica- Traffic uncertainties tion between nodes 2 and 3 is temporarily disrupted and will not be available until a time specified in the i Compute future. Thus, once bundles are received in node 2, it Planning Contact decides to retain and carry in-transit data in its local Plans storage until reaching the ground station communi- cation range, allowing the final data transmission to ii Compute start. In this type of scenarios, the lack of a stable Routing Route Table end-to-end path restricts the utilization of end-to-end feedback messages and encourage error detection and correction, security, and other network features to be iii Enqueue implemented on a hop-by-hop basis. Enqueuing Traffic 2.2 Temporal Routes iv Send It should be noted that, in this kind of networks, rout- Forwarding Traffic ing involves not only determining the next-hop node, but also considering time variables such as when the next-hop will be available or when is the latest time a Figure 2: Workflow in space DTNs ternet, network traffic can be predicted in some types ers. However, this advantage comes at the expense of of satellite networks such as Earth observation mis- having to provide additional routes to cover the un- sions where data acquisitions are generated by oper- certainties with respect to the topology and/or the ator commands. In general, although there can be traffic generated. On the other hand, the distributed uncertainties regarding the topology or the traffic in approach provides a greater routing intelligence and the future, both have a predictable nature and can be computation effort to satellites, which allows to toler- used as a valuable input in the planning stage. After- ate faults and uncertainties without incurring in the wards, a routing procedure (ii ) takes the contact plan routes information overhead. In this work we will as input to compute a route table, which can then be analize this trade-off by means of satellite constella- used by satellites to send bundles to destination. Cur- tion simulations. Particularly, we will put the focus rently, the most investigated routing scheme for pre- on the schemes described in the next section. dictable DTNs is Contact Graph Routing (CGR) [9] and is therefore considered in this work. This stage 3 System Model can be accomplished in two different ways. In a cen- Regarding the distributed CGR strategy, we will con- tralized approach, both the contact plan and the route sider two different possibilities. On the one hand, table are computed by a central entity, after which it is we will call Distributed CGR Full Route Table to the distributed to all satellites. In a distributed approach, state-of-the-art algorithm as it is implemented in the only the contact plan is provided to satellites, after ION 3.5.0 flight software. In this case, each node com- which it can be used to compute routes when neces- putes a complete route table to a given destination sary and by demand. Then, either in the centralized whenever it receives a bundle for that destination. In or distributed scheme, when a local or in-transit data other words, the route table has as many entries as bundle needs to be sent, satellites carry out an en- routes is able to discover the CGR algorithm. The in- queuing process (iii ), which consists in traversing the terested reader is refereed to [12] for a detailed imple- route table, selecting the best valid route to destina- mentation of this routing protocol. On the other hand, tion, and enqueuing the bundle to the neighbor node we will call Distributed CGR Limited Route Table to corresponding to the first contact of the selected route. a modified version of CGR where the route table to a Finally, when a contact with a neighbor node occurs, destination is limited to one route per neighbor. That satellites perform the forwarding process (iv ) by dis- means that there can be only one route to a given des- patching all the bundles enqueued to that neighbor. tination through a certain next neighbor node. This strategy was proposed, described in detail, and com- 2.4 Schemes Comparison pared with others in the work presented in [10]. A conceptual comparison of the distributed and cen- With respect to the centralized strategy, we will call tralized use of CGR routing is summarized in Table 1. Centralized CGR Full Route Table to the scheme in The main advantage of the centralized scheme is given which a central MOC node, analogous to a SDN con- by the reduction of the computation effort that will be troller, is in charge of computing and providing the performed on constrained on-board satellite comput- complete route table for each other node in the net- Table 1: Comparison of distributed and centralized use of CGR Distributed CGR Centralized CGR Each node has the intelligence to calculate A central node (i.e., mission control on ground) route tables in orbit and by-demand based calculates and distributes route tables in advance. on a previously distributed contact plan. Will calculate several routes that probably Will calculate those routes that are strictly will not be finally used (high provisioning necessary to forward traffic (scales better). and memory overhead). Reaction to unexpected events will require Better adapt and react to unexpected events alternatives routes distributed in the route table (unexpected traffic sources, contact failures, etc). (high provisioning and memory overhead). Difficult to optimize and control what each node Allow for more controlled calculation and calculates in the end, thus how the traffic will flow. optimization of the whole network. In-orbit nodes need to use its local processor Free in-orbit nodes resource-constrained to calculate route tables processors from calculating complex paths. (high in-orbit processing overhead). Ground stations (EID 1 to 6) Ground targets (EID 7 to 31) Satellites (EID 32 to 47) MOC (EID 48) 28 3 27 23 21 22 5 2 24 18 20 47 26 17 25 19 16 12 14 15 Walker formation: 11 29 31 ISLs on intersection 10 of orbital planes 47 Along-track 9 formation: 6 13 4 Permanent 30 1 ISLs 8 D enalP C 7 32 32 a) b) Figure 3: Simulation case studies: a) Walker formation, b) Along-track formation work. To this end, the same CGR used in distributed observation missions, data-collection or high-latency approaches was executed on the topology on a cen- communication systems. If used for Earth observation, tralized node and resulting paths were recorded and the ground target locations would represent points of provisioned to nodes in advance. Once nodes receive interest from which on-board instrumentation can ac- their respective route tables, they only need to make quire optical or radar images, or other remote sensing enqueuing and forwarding decisions. Unlike the dis- data. If used for data-collection or high-latency com- tributed case, if the full route table were limited in this munication systems, ground targets would stand for case, nodes would not be able to compute new routes ground-based equipment relaying either science or lo- on demand in the case of uncertainties or unexpected cal user data. In both cases, data sent from ground events. Given that this would provoke a considerable targets are addressed via orbiting satellites to the performance reduction in terms of bundles delivered, centralized MOC. We consider a bi-directional pub- we will not consider a Centralized CGR Limited Route lish/subscribe traffic pattern from all ground targets Table strategy in the present analysis. to the MOC and reversal. In particular, each ground target generates an increasing number of bundles of 125 KBytes to be delivered to the MOC. In turn, the 4 Simulation Analysis MOC sends an increasing number of bundles to each In order to analyze the proposed schemes, we have ground target. Besides, the transmission data-rates adapted and extended a discrete event-driven simu- for both inter-satellite and Earth-to-satellite links are lator publicly available called DtnSim [13]. We run set to 100 Kbps. simulations of the two realistic satellite constellations We quantify the routes information overhead of the depicted in Figure 3. A walker-delta formation (a) and schemes proposed in Section 3 through the number a sun-synchronous along-track constellation (b), both of route table entries created in each case. Figures 4 composed of 16 cross-linked LEO satellites (max. link a) and 4 b) show the results for the walker-formation range of 1000 Km at 500 Km height) with ids 32-47, and along-track scenarios respectively. The Central- 25 ground target points (e.g., user terminals) with ids ized CGR, Full Route Table strategy provides the same 7-31, and 6 ground stations with ids 1-6 connected quantity of route table entries independently of the in- through Internet to a central MOC node with id 48. creasing traffic, given that this scheme is proactive in These scenarios have been previously presented in [10] terms of routes computation and does not take into and are reconsidered in this analysis under a time hori- account the traffic generation. As we previously dis- zon of 6 hours. cussed, this overhead information is necessary in or- The chosen constellations are suitable for Earth der to face uncertainties both in the predicted topol- 35000 computed but not used by the centralized scheme as compared to distributed schemes. Although this study 30000 suggests that distributed approaches are appealing re- Route Table Entries garding the use of computed information, other rele- 25000 vant aspects like the cost of processing in space nodes Centralized CGR, Full Route Table Distributed CGR, Full Route Table and the required controllability of the network need to 20000 Distributed CGR, Limited Route Table be taken into account when deciding the most appro- 15000 priate scheme. Future work will explore other compar- ison metrics between distributed and centralized rout- 10000 ing in order to derive a complete evaluation framework that facilitates future space DTN designers to make an 5000 informed decision on the optimal routing strategy. 0 200 400 600 800 1000 1200 1400 References Bundles Sent a) [1] J. Alvarez and B. Walls, “Constellations, clusters, and communication technology: Expanding small 30000 satellite access to space,” in 2016 IEEE Aerospace Conference, March 2016, pp. 1–11. 25000 Route Table Entries [2] V. Cerf, S. Burleigh, A. Hooke, L. Torgerson, 20000 R. Durst, K. Scott, K. Fall, and H. Weiss, “Delay-tolerant networking architecture,” In- 15000 ternet Requests for Comments, RFC Editor, RFC 4838, April 2007. [Online]. Available: 10000 http://www.rfc-editor.org/rfc/rfc4838.txt 5000 [3] P. Muri et al., “Topology design and perfor- mance analysis for networked earth observing 0 small satellites,” in MILCOM Proceedings, Bal- 200 400 600 800 1000 1200 1400 timore, Maryland, Nov 2011, pp. 1940–1945. Bundles Sent b) [4] M. Huang, S. Chen, Y. Zhu, and Y. Wang, “Cost- efficient topology design problem in time-evolving Figure 4: Results for the a) Walker-formation scenario delay-tolerant networks,” in IEEE GLOBECOM, and the b) Along-track formation scenario Dec 2010, pp. 1–5. ogy or the traffic generated. On the other hand, [5] J. A. Fraire and J. M. Finochietto, “Design chal- the distributed approaches compute route tables as lenges in contact plans for disruption-tolerant traffic is generated and routed through intermediate satellite networks,” Communications Magazine, nodes. Therefore, these schemes compute a much IEEE, vol. 53, no. 5, pp. 163–169, May 2015. smaller number of routes. Besides, as expected, the Distributed CGR, Limited Route Table scheme gener- [6] J. A. Fraire, P. G. Madoery, and J. M. Finochi- ates fewer route table entries than Distributed CGR, etto, “On the design and analysis of fair contact Full Route Table. plans in predictable delay-tolerant networks,” IEEE Sensors Journal, vol. 14, no. 11, pp. 3874– 5 Conclusions 3882, Nov 2014. In this work, we have described and analyzed as- [7] J. Fraire and J. Finochietto, “Routing-aware pects concerning distributed and centralized routing fair contact plan design for predictable delay solutions for satellite-based Delay Tolerant Networks tolerant networks,” Ad Hoc Networks, vol. 25, (DTNs). The centralized approach was evaluated as pp. 303 – 313, 2015, new Research Challenges a means to implement a Software Defined Networking in Mobile, Opportunistic and Delay-Tolerant (SDN) paradigm into DTN space networking. Networks Energy-Aware Data Centers: Ar- We have evaluated the route table entries metric in chitecture, Infrastructure, and Communication. two realistic satellite constellations and the results pro- [Online]. Available: http://www.sciencedirect. vided evidences on the quantity of routes which were com/science/article/pii/S1570870514001371 [8] J. A. Fraire, P. G. Madoery, and J. M. Finochietto, “Traffic-aware contact plan design for disruption-tolerant space sensor networks,” Ad Hoc Networks, vol. 47, pp. 41 – 52, 2016. [Online]. Available: http://www.sciencedirect. com/science/article/pii/S1570870516301032 [9] G. Araniti, N. Bezirgiannidis, E. Birrane, I. Bisio, S. Burleigh, C. Caini, M. Feldmann, M. Marchese, J. Segui, and K. Suzuki, “Contact graph rout- ing in dtn space networks: overview, enhance- ments and performance,” IEEE Comms. Maga- zine, vol. 53, no. 3, pp. 38–46, March 2015. [10] J. A. Fraire, P. Madoery, S. Burleigh, M. Feld- mann, J. Finochietto, A. Charif, N. Zergainoh, and R. Velazco, “Assessing contact graph routing performance and reliability in distributed satel- lite constellations,” Hindawi Journal of Computer Networks and Communicationse, in Press. [11] S. Xu, X. Wang, and M. Huang, “Software- defined next-generation satellite networks: Archi- tecture, challenges, and solutions,” IEEE Access, vol. 6, pp. 4027–4041, 2018. [12] “Interplanetary Overlay Network (ION),” http:// sourceforge.net/projects/ion-dtn/. [13] J. A. Fraire, P. G. Madoery, F. Raverta, J. M. Finochietto, and R. Velazco, “Dtnsim: Bridg- ing the gap between simulation and implementa- tion of space-terrestrial dtns,” in Space Mission Challenges for Information Technology (SMC- IT), 2017 IEEE Int. Conference on, Sept 2017.