Collaborative Earth observation satellite constellations are arising as a new paradigm with important advantages in comparison with traditional monolithic systems. In this context, Disruptions Tolerant Networking (DTN) protocols were proposed to provide e cient and autonomous store-carry-and-forward data transport. Although a scheduled contact plan can be used to optimize routing and data delivery metrics, signi cant challenges remain in studying the ability to recover from unplanned events. In order to evaluate di erent routing schemes under failures, we propose a framework based on Markov Chains and Probabilistic Computation Tree Logic which allows its comparison in terms of either the expected throughput or the probability of ful lling a given mission. This approach provides considerable advantages with respect to traditional simulations since it allows the computation of expected values of network metrics instead of approximations without any error estimation.
Earth observation through small satellites [
However, the consequences of dividing a satellite
into a distributed system imply important technology
challenges which need to be tackled before any mission
can be deployed in space. Particularly, in this work we
will put the focus on the communications between
segments and with the ground stations. Regarding this
aspect, there exists a large number of technologies and
protocols which have been developed for the Internet,
but in general they are ine cient or unsuitable when
used on satellite networks, because orbiting
trajectories do not allow satellites to establish continuous and
stable end to end paths among them [
As a consequence, many satellite networks do not
satisfy the continuous connectivity principle between
their nodes and have remained outside of the Internet
paradigm because they have used incompatible
specialized protocols which usually require several
protocol adapters. However, NASA and other space
agencies have recently decided to develop and standardize
protocols which allow communication between these
kind of networks which are called Delay and
Disruption Tolerant Networks (DTN) [
The Bundle Protocol works as a new protocol layer
on top of the transport layer. Its function
consists in overcoming the limited connectivity by
applying a store-carry-and-forward approach. Under this
paradigm, data is grouped into packets called bundles
and they are transmitted as communication
opportunities are available. In the case of satellite networks,
the forthcoming episodes of communications and their
properties can be determined in advance based on
orbital dynamics. These types of deterministic DTNs
are known as scheduled DTNs and can take
advantage of a contact plan comprising the future network
connectivity in order to optimize data forwarding.
However, scheduled routing solutions such as Contact
Graph Routing (CGR) assumes the estimation of the
future topology status is highly accurate [
Regarding scheduling under uncertainties, the
authors have evaluated the behavior of the
state-of-theart routing algorithms by means of simulations [
This paper is structured as follow. In Section 2 we provide some background on routing in scheduled DTNs and the failures model considered here. Then, in Section 3 we describe the proposed framework. Afterwards, in in Section 4 we use our method in a case study. Finally, we discuss and summarize this work in Section 5. 2 2.1
In general, the DTN topology is time varying. This evolutionary nature can be captured by means of states, where each state is represented by a graph whose vertex are the network nodes and the links are the transmission opportunities available in that state. Each state is valid for a nite period of time, which is given by an initial time (tini) and a nal time (tend). Figure 1 shows a scenario with 3 nodes and a duration of 30 seconds divided into 3 states of 10 seconds each one. Other important contact attribute is the capacity, which represents the tra c volume that can be []sscoende -s002 itm :12 k s 0 1 0 :1 k s 0 3 0 2 : 3 k
Node 1
TO 3 Node 1 Node 1 transmitted through that contact. The capacity of a contact, between nodes i and j at state k, is symbolized here as Ci;j;k, and we will measure it in bytes. Thanks to orbital mechanics, it is possible to codify the future transmission opportunities in a contact plan, which can then be used to make e cient routing decisions either in a distributed way (by providing the contact plan to all nodes and executing then the routing algorithm in each node) or in a centralized way (by directly providing a route table for each tra c). Particularly, the state-of-the-art algorithm for routing in this kind of networks is CGR and it is mostly thought to be executed in a distributed manner. Thus, when a node needs to send data, CGR rst computes a route table considering many neighbors, and then it chooses the route which delivers the bundle as early as possible in time. Finally, the bundle is sent through the rst contact of that route. If the receiver node is not the nal destination, it will repeat the same procedure in a hop by hop basis until the bundle reaches the destination. Unexpected events like antenna pointing inaccuracies, interferences, energy outages or even equipment rest, could cause that a contact which is present in the contact plan actually does not happen. Then, the routing algorithm which had planned to send a bundle through that failing contact, will need to make another decision to react to the unexpected event.
In order to explain the fault model adopted in this work, let's consider the example scenario in Figure 1. If it is considered that Satellite 1 has data to send to ground station, then there are two routes available R1 which consists in two transmissions (from satellite 1 to 2 at time 0 and from satellite 2 to ground station at time 10) and R2 consisting in 1 transmission (from satellite 1 to ground station at time 20). If CGR is the routing algorithm, then it will choose R1 since this provides the best delivery time to reach the destination. However, if a failure is encountered in link2;3;k2, the tra c will not be able to be delivered because there will not be any extra routes from Node 2 to Node 3 in state 2. However, if a failure happens in link1;2;k1, the situation is di erent. In that case, we assume that Node 1 can realize that the transmission has failed and that a route R2 can still deliver the bundle to Node 3. Finally, link1;3;k3 can fail or succeed and considering all these possibilities allows us to compute the exact values of the quantitative properties of the network under failure. 3 3.1
We propose a framework consisting of 3 stages as showed in Figure 2. A Markov Chain model is generated in order to potentially encode all possible states of the network for a given tra c and routing algorithm. Therefore the following components are needed as inputs for the Model Builder stage: 1. The network contact plan, which must be annotated with the probability of failure of each link. 2. The network tra c, which consists in a list of bundles. Each bundle must have a source and destination node ID, a size and a time of generation. 3. The routing algorithm, which is provisioned by implementing a programming interface consisting of 2 methods used by the model generator engine.
The output of the model builder is a tree in which
each branch is a possible network execution. This
model is then translated to a PRISM model [
PN b=0 b P =?[F (delivered = i)]
N
Where N is the number of bundles in Tra c, and P=?[F (delivered=i)] is a Probabilistic Computation Tree Logic Formula (PCTL) which measures the probability of delivering i bundles in all the possible realization of the network.
Also, this model allows to compute the probability of ful lling a given mission. For the sake of simplicity, we will consider that we ful ll a mission by delivering at least a given fraction f of the total tra c. Then, the next PCTL formula computes the desired probability: P r(successf ul mission) = P =?[F (delivered >= f N )]
Furthermore, this model supports the speci cation of more complex mission properties like for example, those ones involving the delivery time. 3.2
The model is generated by the process described in Algorithm 1. It systematically explores all possible network states, generated by calling the genNextState method which interacts with the routing algorithm by means of the following interface: 1. route routing(state, bundle): This method must return a list of contacts (route) which encodes the made routing decisions. 2. void update(state, route): This method receives a route and it has to update the current state according to this routing decision. For example, in those algorithm (like CGR) which consider contact capacity, this method should update the residual capacity of each contact.
A detailed description of the genNextState routine is provisioned in Algorithm 2. Indeed, the main idea of this algorithm is to compute the routing decisions for the incoming tra c at a given state. Then, using this information it generates the state's children by considering any set of contact failures. In other words, given a set of contacts named as contacts to use that were chosen by the routing algorithm to be used at that moment, it takes any subset f ailure set 2 P(contacts to use) and computes a new child state by considering: 1) The bundles for which the routing algorithm choose a route which contains a contact belonging to failure set, stays in the sender node. 2) The bundles whose contacts does not belong to the failure set are now in the receiver node. After that, each child state is linked with the parent in the Markov Chain by an edge whose probability pl is given by: pl =
Y c 2failure set pf (c)
Y c 2failure setc (1 pf (c)) 4
In order to show the application of the proposed framework, we analyze the linear formation topology depicted in Figure 3, which is composed of 3 satellites bene ts of this disposition, satellites do not require complex transfer maneuvers if launched from the same vector. Also, since satellites perceive similar gravitational perturbations, signi cant savings in propellant for formation-keeping can be made. From a communications perspective, the topological stability of this formation also favors the simplicity of xed antennas against complex gimbal mounts or electroniFigure 2: The proposed framework cally steered antennas for inter satellite links (ISLs).
Similar topologies have been used in previous satellite
Algorithm 1: Generate Model Algorithm DTN studies [
from input status by making routing In this scenario we consider that each satellite gendecisions erates one bundle directed to ground station at time 1 contacts to use []; 0 and we set the failure probability in 0.1 for the ISLs 2 routing decision []; and 0.5 for the earth to satellite links (ESLs) . Regard3 for bundle in current.incomming bundles do ing contact capacity, it is assumed that all tra c can 4 selected route routing(state; bundle); be sent using any single contact and it will be avail5 routing decision:append((bundle; selected route)); able in the receiver node in the following time stamp (if a failure does not happen). Under this scenario, we 6 update(state; selected route); evaluate the probability of ful ll 3 di erent missions 7 contacts to use:append(selected route:contacts()); for each routing algorithm: Mission A is ful lled if at least one bundle is delivered to ground station. 8 for n of f aults 2 range(len(contacts to use)) Mission B requires that more than 1 bundle be dedo livered. While Mission C is ful lled if only if all the 9 comb generated tra c is delivered to the ground station. combinations(contacts to use; n of f aults); The results of the performed evaluation are showed for f ault set 2 comb do in Figure 4. There we can see that direct routing new state state:copy(); presents the highest probability of ful lling the Misfor bundle; contactinrouting decision do sion A since it always tries to send 1 bundle for each if contactinf ault set then contact with the ground station, and this maximizes new state:update(bundle; F AILU RE); the chances of delivering at least 1 bundle. On the other hand, CGR always tries to send all bundles else through the route with the best delivery time and in new state:update(bundle; SU CCESS); ilitkseleyagcearsneess)s cthoanacrersiveofbseefnodreinigt awtalsetaesst (1intrvaeryc ufonreach contact with the ground station ( which is a necessary condition in order to maximize the delivery of at least 1 tra c). However, as the mission requirements become more demanding CGR, which tries to download all the tra c for each of the 3 contacts, gets performances almost as good as the one gotten in the case of the least demanding mission. On the contrary, the behavior of direct routing is dramatically a ected that generate tra c for a unique ground station. In this formation satellites are equally spaced and follow very similar orbital trajectories. Among the many 17 p compute prob(f ail set; contacts to use); 18 current:add child(new state; p); 19 return current:get childs(); t=0 t=1 t=2 t=3 t=4 t=5
ISL
ESL when the mission requirements become more demanding. In this work we proposed a framework to systematically build a Markov Chain and encode all possible executions of a satellite network. Then, we gave a formula to compute the expected network throughput and the probability of ful lling a mission as a way of showing the kind of information we can get from the model. After that, we use the introduced method in a case study.
Regarding the comparison between this method and the simulation approach, we showed that this one allows to compute the expected values of the network metrics (like throughput and latency) instead of approximations. This constitutes a signi cant step since we are working in the de nition of a model to compute the best routing decisions under uncertainties, that is, the election of routes which maximize the expected throughput for a given network and tra c. Therefore, this framework will allow us to compare current routing solution with the optimal ones. From that analysis we expect to draw conclusion to improve the behavior of scheduled routing under uncertainties. Even more, we plan to contribute with the development of a fullycapable probabilistic CGR with enhanced uncertainty modeling, replication and recalculation features, which is very important for the DTN community since CGR is expected to be the de facto routing algorithm for this kind of networks.