=Paper=
{{Paper
|id=Vol-2178/SSN2018_paper_32
|storemode=property
|title=On the Trade-off Analysis of Centralized and Distributed Routing in Delay Tolerant Satellite Networks
|pdfUrl=https://ceur-ws.org/Vol-2178/SSN2018_paper_32.pdf
|volume=Vol-2178
|authors=Pablo Madoery,Juan Fraire,Fernando Raverta,Jorge Finochietto
|dblpUrl=https://dblp.org/rec/conf/ssn/MadoeryFRF18
}}
==On the Trade-off Analysis of Centralized and Distributed Routing in Delay Tolerant Satellite Networks==
https://ceur-ws.org/Vol-2178/SSN2018_paper_32.pdf
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.