The emergence of mega-constellations of interconnected satellites has a major impact on the integration of cellular wireless and non-terrestrial networks (NTN). This paper studies the problem of running a federated learning (FL) algorithm within a low Earth orbit (LEO) constellation of satellites connected with intra-orbit inter-satellite links (ISL). Satellites apply on-board machine learning and transmit the local parameters to the parameter server (PS). The main contribution is a novel approach to enhance FL in satellite constellations using intra-orbit ISLs. The key idea is to rely on the predictability of satellite visits to create a system design in which ISLs mitigate the impact of intermittent connectivity and transmit the aggregated parameters to the PS. We first devise a synchronous FL, which is then extended towards an asynchronous FL for the case of sparse satellite visits to the PS. An efficient use of the satellite resources is attained by sparsification-based compression the aggregated parameters of each orbit before forwarding to the PS. Performance is evaluated in terms of accuracy and the required size of data to be transmitted. The numerical results indicate a faster convergence rate of the presented approach compared with the state-of-the-art FL on satellite constellations.

Low Earth orbit, mega-constellations, intra-orbit inter-satellite links, federated learning, sparsification.

§ INTRODUCTION

Satellite constellations have been an essential component of modern communication and remote sensing systems for decades.
Recent advances in satellite technology and the emergence of interconnected mega constellations in leo, are revolutionizing the way we collect and process data from space <cit.>. Unlike the previous cellular generations that were exclusively focused on terrestrial networks, mega-constellations and Non-Terrestrial Networks (NTN) are seen as the integral part of 5G and the upcoming 6G wireless systems <cit.>.
Consisting of thousands of satellites, these constellations have the potential to process vast amounts of data. Conventional central processing of this collected data involves significant challenges, including communication delays, limited bandwidth and storage, as well as data ownership concerns <cit.>. The on-board intelligence of satellites increases steadily <cit.>, pushing towards
in-orbit data preservation and learning to conserve bandwidth and energy, avoid overloading of gsl, and enable native ai in space.

sfl has emerged as a promising solution to address these challenges <cit.>, as an instance of distributed ml that enables satellites to collaboratively learn a  model without exchanging raw data. With fl, each satellite trains a local model with its own data and sends only the updated model parameters to be aggregated at a central ps. FL has the potential to reduce both communication cost and training delay.
The first step towards sfl was made in <cit.>, where each satellite acts as an individual collaborator towards the ps, located within a terrestrial gs. As <cit.> does not assume existence of isl, the synchronization of intermediate results with the ps requires direct link from each satellite to the gs. Each leo satellite has only a very short communication window  per orbital period towards the terrestrial ps. This, as well as the fact the link between a fixed gs and a satellite vanishes behind the horizon for several hours after a few orbital periods, leads to a connectivity bottleneck that severely inhibits convergence speed of a plain fl. Thus, instead of using conventional synchronous fl, <cit.> advantageously uses the sporadic, but predictable, satellite connectivity to roll out an asynchronous aggregation.

Newer satellites, especially within the context of mega constellations <cit.>, rely increasingly on isl and multi-hop routing. In this paper, we consider a sfl setup with isl, focusing on links between adjacent satellites within the same orbital plane, as in that case the satellites have stable relative positions and thereby stable links.
However, a direct implementation of multi-hop routing leads to network traffic growing quadratically in the number of satellites and a high load on links towards the ps, as each client update will be treated as a common unicast message. Leveraging the structure of fl traffic along with in-network aggregation <cit.>, communication can be limited to a single outgoing message per satellite and a global iteration during the aggregation phase. Moreover, most of these transmissions use intra-orbit isl instead of the more challenging ps link, resulting energy saving and reduced communication load at the ps.

Global model distribution (left) and collection of local updates (right) using intra-orbit inter-satellite communication.

<ref> illustrates the key idea through an example of connectivity bottleneck in sfl using
two satellites at 550 altitude, spaced 45 apart within the same orbital plane.
The ps is located in a gs and both satellites are participating in a fl procedure with their local data sets.
A single pass over the gs, i.e., the time the satellite and the gs can communicate, is less than 10 minutes, while a single orbital period is 95 minutes.
Assume that the computation of this update takes $15$ minutes. Let one of the satellites be selected by the ps to compute an update to the global model. The satellite will collect the current global model on the first pass and return the result on the next pass. This incurs a delay of roughly one orbital period, which is more than one hour in excess of the computation time.
If both satellites are supposed to compute an update then,
upon the first pass, each satellite will collect the current model version and start computing. The first satellite will pass the ps for the second time and deliver the update. However, in a synchronous fl procedure, the ps will not update the global model until all updates are received. Hence, the first satellite will not have a new model version available to iterate upon during the offline period following the second pass. Differently from this, when isl are available, the first satellite can transmit this global model to the second satellite directly after receiving it. Then, both satellites compute the update in parallel and the second satellite can collect and deliver both updates to the gs during its first pass. This is illustrated in <ref>. The time for a single global iteration is reduced from over one orbital period to less than 20 minutes by this approach, while the traffic at the ps is reduced by 50. Implementing this idea requires careful system design and route planning, relying upon the inherent determinism of satellite movement.

The objective of this paper is to present a system design for sfl
within a leo satellite mega-constellation in which the satellites within the same orbital plane are connected via isl to the adjacent nodes, forming a ring network. Each satellite has the capability to communicate with an out-of-orbit entity, such as gs, that orchestrates the training process. The external orchestration is needed as the satellites are not necessarily able to communicate across orbital planes; at the same time it creates a connectivity bottleneck. The contributions of this paper are:

* Design of a distributed system for sfl, supporting client clustering, synchronous and asynchronous orchestration, and consistent decentralized routing decisions.

* Development of a communication scheme for sfl that takes advantage of intra-orbit isl. Due to the co-design of predictive routing and in-network aggregation, the convergence time is reduced markedly, while not increasing the communication load.

* Extension of the proposed communication scheme to accommodate gradient sparsification and in-network aggregation for bandwidth-efficiency. This includes the development of a novel estimator for the number of non-zero elements in the sum of sparse vectors.

* An effective method to prevent biased solutions for asynchronous aggregation in satellite constellations connected with isl. This is necessary after improving connectivity with isl, as simple opportunistic scheduling can result in a small subset of clusters dominating the training process for several hours.

* We have evaluated the performance of the proposed system in several setups. The numerical results highlight a major increase in convergence speed (${\sim}7$ times) due to the use of isl and ${\sim}10$ times reduction of communication load based on our in-network aggregation approach.

We remark that the proposed system is agnostic to the actual fo procedure, as long as it supports partial aggregation as discussed in <ref>. Hence, the system performance can be further improved using conventional fine-tuning of fo algorithms and ml model-specific hyperparameters <cit.>. Finally, we
note that the primary performance metric in this paper is the convergence time measured by a (simulated) wall clock. Conventional metrics for fl algorithms are model test accuracy versus the number of global iterations or the number of gradient computations. This is sensible as the focus in these studies is on improved computational efficiency. Instead, the key challenge that sets sfl apart from conventional scenarios is the connectivity bottleneck implied by the laws of orbital mechanics, potentially leading to extensive delays between iterations. Success in overcoming these obstacles is best measured in the number of global iterations the distributed system can manage within a certain period. As with any communication system, another important metric is bandwidth-efficiency, especially in gsl.

§.§ Related Work

A detailed technical model of sfl was introduced <cit.>, while <cit.> considered it in a more general context of satellite-based computing networks. A broad overview of the different scenarios encountered in sfl, together with a discussion of the technical challenges for each scenario, is presented in <cit.>. The technical details of several of the ideas sketched in <cit.> are provided in this paper. Aerial fl <cit.> is a setup that is complementary to sfl, in which the ps is operated within a satellite to orchestrate a planet-side fl process. Closely related to that are the satellite-assisted iort system architectures considered in <cit.> and <cit.>.

A broad classification of current work on sfl can be made based on the presence and usage of isl. The model in <cit.> considers the case without isl, identifies the connectivity bottleneck, and proposes a satellite-specific asynchronous fl algorithm as solution. This work is extended in <cit.> with a scheduling algorithm that exploits the inherent determinism of satellite trajectories. Another scheduling approach based on buffered asynchronous fl is proposed in <cit.>, aiming to balance local model staleness and idle times. Lacking a thorough benchmark against the state-of-the-art, the gain of the complicated scheduling algorithm in <cit.> remains an open question. Staleness in asynchronous sfl is further investigated in <cit.>, which introduces an asynchronous update rule based on the notion that staleness effects in sfl are similar in consecutive training epochs. In <cit.> the connection bottleneck is tackled by combining synchronous orchestration with a dynamic aggregation rule that ignores stragglers. However, the primary reason for the feasibility of synchronous terrestrial orchestration is the usage of multiple geographically distributed gs that act as a distributed ps. While the authors observe correctly that latency between gs is small compared to gsl, mechanisms to either ensure consistency between gs or a hierarchical fl approach would be required in a practical system implementation of <cit.>.

An alternative means to improving connectivity is the usage of isl instead of a distributed ps, as proposed in the conference version of this paper <cit.>. The communication strategy from <cit.> is adopted in <cit.> and combined with a distributed ps implemented within interconnected haps. This is extended in <cit.> to asynchronous aggregation with multiple haps. A modified version of <cit.> is proposed in <cit.>, consisting of a decentralized implementation of predictive routing, which might lead to inconsistent routing decisions, and the absence of incremental aggregation (see <ref>), which leads to a quadratic traffic growth within each orbital plane.

fl in a completely connected satellite constellation is considered in <cit.>, in which training participation is required only from the satellites that are within a cluster that is close to the gs. A decentralized learning system, without ps, leveraging inter- and intra-orbit isl is proposed in <cit.>. Decentralized learning in leo satellite constellations under very realistic satellite system assumptions is considered in <cit.> for a semi-supervised classification task.
Finally, <cit.> treats fl-aware routing and resource allocation for sfl.

In applying FL over the satellite constellations, large-scale ML models are required to process the high-resolution images. In this regard,
huge amount of training parameters must be sent to the PS in each iteration of fl. 50-layer ResNet and VGGNet, for instance, have approximately 26 and 138 million parameters, respectively <cit.>. It is necessary to find more efficient approaches to improve the communication efficiency in satellite constellations due to the strict bandwidth constraint. Promising approaches such as quantization and sparsification are required to reduce the size of training parameters, communicated in fl <cit.>. Accordingly, the authors in <cit.> proposed sparsifying the gradient updates by only transmitting the $K$ significant components. This algorithm was empirically explored with both recurrent and convolutional networks in <cit.>.

§.§ Notation
Scalars are represented in a normal font $x$, while vectors in bold $\vec{x}$. The Euclidean norm of a vector $\vec{x}$ is $||\vec{x}||$. The angle between two vectors $\vec{x_1}$ and $\vec{x_2}$ is $\angle (\vec{x_1},\vec{x_2})$.
Sets are denoted by $\mathcal X$, and the cardinality of $\mathcal X$ is $|\mathcal X|$. Removing an element $x_i$ from the set $\mathcal X$ is denoted by $\mathcal X \setminus \{ x_i \}$.

In a graph $\mathcal G = (\mathcal V, \mathcal E)$ with vertices $\mathcal V$ and edges $\mathcal E$, the neighborhood of any vertex $v \in\mathcal V$ is denoted as $\mathcal N(v)$. If $\mathcal G$ is directed, $\mathcal N^-(v)$ and $\mathcal N^+(v)$ denote the incoming and outgoing neighborhood of $v$, respectively.
The operators $\Pr(\cdot)$, $\mathds E$, and $I(\cdot)$ are the probability, expected value, and indicator function, respectively. Integer rounding is denoted by $\lfloor{\cdot\rfloor}$ and $\lceil{\cdot\rceil}$.

§ SYSTEM MODEL

The constellation has $P$ orbital planes, where each orbit $p$ contains $K_p$ satellites $\mathcal K_p$ such that $\mathcal K_{p_1} \cap \mathcal K_{p_2} = \emptyset$, for all $p_1 \neq p_2$. The set of all satellites within the constellation is denoted as $\mathcal K = \bigcup_{p = 1}^P \mathcal K_p = \{ k_{1,1},\dots,k_{P,K_P} \}$ with the total number of satellites $K = \sum_{p=1}^P K_p$.

Each satellite $k$ follows a trajectory $\vec s_k(t)$ around Earth with orbital period $T_p = 2 \pi \sqrt{\frac{a_k^3}{\mu}}$, i.e., $\vec s_k(t) \approx \vec s_k(t+ n T_p)$ for all integer $n$, where $a_k$ is the semi-major axis of satellite $k$ and $\mu = 3.98 \times 10^{14}\,\si{\meter^3/\second^2}$ is the geocentric gravitational constant. For circular orbits, the semi-major axis is $a_k = r_E + h_k$ with $h_k$ being the satellite's altitude above the Earth's surface and $r_E = 6371\,\si{\km}$ the Earth radius. The satellites within an orbital plane $p$ follow the same trajectory and are assigned unique IDs $\mathcal K_p =\{ k_{p,1}, \dots, k_{p,K_p}\}$ such that satellite $k_{p,i+1}$ is behind $k_{p,i}$. If the satellites are distributed equidistantly within the orbital plane, we have
$\vec s_{k_{p,1}}(t) \approx \vec s_{k_{p,2}}(t - T_p / K_p) \approx \vec s_{k_{p,3}}(t - 2 T_p / K_p) \approx \dots$.[Under the assumption of perfect Keplerian orbits, we can replace '$\approx$' with '$=$' in all statements on trajectories. With real-world orbits being subject to orbital perturbations and station keeping maneuvers, these relations do not hold exactly and we only state them here to introduce notation and some general concepts on an abstraction level suitable for this paper.] Coordinates are in an Earth-centric reference frame.

A Walker Delta constellation with $K = 40$ satellites and $P = 5$ orbits.

§.§ Communication Model

Each satellite has three communication devices, two of which  are for intra-orbit communications. The third one is for communication outside of its orbital plane, either a ground-to-satellite link or an isl towards a satellite in another orbit. Communication with an Earth-based gs is feasible if the satellite is visible from the gs at an elevation angle $\frac{\pi}{2} - \angle (\vec s_{GS}, \vec s_k(t) - \vec s_{GS}) \ge \alpha_e$, where $\alpha_e$ is the minimum elevation angle <cit.> and $\vec s_{GS}$ is the position of the gs. While this condition is satisfied, we assume communication is possible at a fixed rate. For isl, communication is feasible if the line of sight is not obstructed by the Earth. With lower atmospheric layers degrading the link quality, a sensible assumption is to consider an isl to be feasible if it does not enters the atmosphere below the Thermosphere <cit.>, starting at approximately 80 above sea level. This translates to a maximum slant range $d_\mathrm{Th}(t; k_1, k_2) = \sqrt{\norm{\vec s_{k_1}(t)}^2 - r_T^2} + \sqrt{\norm{\vec s_{k_2}(t)}^2 - r_T^2}$ for any two satellites $k_1, k_2$, where $r_T = r_E + \SI{80}{\km}$. For circular orbits, this threshold is the constant
$d_\mathrm{Th}(k_1, k_2) = \sqrt{{(h_{k_1}+r_E)^2}-{r_T^2}}+\sqrt{{(h_{k_2}+r_E)^2}-{r_T^2}}$.
We assume communication at a fixed rate is possible between satellites $k_1$ and $k_2$ if their distance at time $t$ is $d(t; k_1, k_2) \leq d_\mathrm{Th}(t; k_1, k_2)$.

The most stable link usage is to connect each satellite to its two closest orbital neighbors, effectively forming a ring network <cit.>. The two neighbors of satellite $k_{p,i}$ are $\mathcal N(k_{p_i}) = \{ k_{p,i-1}, k_{p,i+1} \}$. Here, the satellite indices $i-1$ and $i+1$ are modulo $K_p$, which is a convention we will adopt throughout this paper until further notice.
Following the previous discussion,
the data rate between any two satellites
$k_1, k_2 \in\mathcal K$ within the constellation is fixed to
$r(t; k_1, k_2) = \rho_{k_1, k_2}$ if $k_2 \in \mathcal N(k_1)$ and communication is feasible, and zero otherwise. For the out-of-orbit communication link, we assume there is a single communication partner of interest, denoted as the ps. Then, the rate function of satellite $k$'s, $k\in\mathcal K$, link towards the ps is similarly defined as $r_\mathrm{PS}(t; k) = \rho_{k,\mathrm{PS}}$ if communication is feasible and zero otherwise.

§.§ Computation Model

The satellites within the constellation collaboratively train a ml model from data $\mathcal D$ collected at the satellites. The ml model is known at all satellites and fully defined by its model parameter vector $\vec w \in\mathds R^{n_d}$. The goal is to find a solution to the optimization problem

\begin{equation} \label{eq:opt}
\min\nolimits_{\vec w}\enskip F(\vec w),
\end{equation}

where the global loss function $F(\vec w) = \frac{1}{D} \sum_{\vec x\in\mathcal D} f(\vec x; \vec w)$, with $D = |\mathcal D|$, measures the performance of the ml model with respect to the data set $\mathcal D$ for a certain set of model parameters $\vec w$ and a potentially nonconvex per-sample loss function $f(\vec x; \vec w)$.

Regarding <ref>, we make two fundamental assumptions: (i) the computational resources at the satellites are limited such that a distributed solution of <ref> is necessary; (ii)  the data set $\mathcal D$ is distributed across the constellation and communicating this data is not feasible; i.e., each satellite has a local data set $\mathcal D_k$ such that $\mathcal D = \bigcup_{k\in\mathcal K} \mathcal D_k$, which is not shared with any other participants in the training process.
Due to the local data sets assumption and the limited connectivity, this distributed ml scenario is an instance of a fl <cit.>. However, in contrast to a conventional fl setup, here client participation is under central control, the connectivity is mostly deterministic and predictable, and the number of devices is orders of magnitude lower.

In fl, <ref> is solved iteratively using a modified dsgd procedure.[While this paper is focusing on dsgd-based optimization, the extension to many other iterative distributed optimization algorithms for training ml models is straightforward.]
This algorithm is motivated by the linearity of the gradient and the observation that the objective function is separable as $F(\vec w) = \frac{1}{D} \sum_{k\in\mathcal K} D_k F_k(\vec w)$ with $F_k(\vec w) = \frac{1}{D_k} \sum_{\vec x\in\mathcal D_k} f(\vec x; \vec w)$
and $D_k = |\mathcal D_k|$.
The optimization process is orchestrated by a central ps, which maintains the current iteration of the global model parameters $\vec w$, distributes these to the clients for further refinement, and collects the results. In contrast to conventional fl, we assume that every client participates in every iteration of the solution process due to the relatively small number of clients.
Since satellites within the constellation are only connected to their orbital neighbors, communication across orbital planes is only feasible via the out-of-constellation link. Hence, it is only natural to assume the ps to be either located in a gs or in a satellite outside the constellation. Details of the ps operation will be discussed in <ref>.

§.§.§ Client Operation

Each satellite $k\in\mathcal K$ runs a process to handle all application-layer communications related to the fl training.
This procedure will be designed in <ref>. Upon receiving an updated global parameter vector $\vec w^n$, it launches the learning procedure outlined in <ref> in a separate thread for concurrent execution.
This learning procedure then computes an update to $\vec w^n$ based on the local data set $\mathcal D_k$. After initialization in line <ref>, the loss function $F_k(\vec w)$ is minimized in $I$ local epochs using permutation-based mini-batch sgd in lines <ref>–<ref>. Instead of directly transmitting the updated model parameters $\vec{w}^{n,i}_k$, the effective gradient $\vec g_k(\vec{w}^{n}_{k})$ is computed in line <ref>. While both representation $\vec{w}^{n,i}_k$ and $\vec g_k(\vec{w}^{n}_{k})$ are theoretically equivalent, the latter is often easier to compress. This is optionally done in line <ref> by calling the procedure CompressGradient, which will be defined in <ref>. Without compression, CompressGradient is simply the identity function, i.e., $\bar{\vec g}_{k}(\vec{w}^{n}_{k}) = \vec{g}_k(\vec{w}^{n}_{k})$. In a slight modification of the usual approach, <ref> returns the compressed effective gradient scaled by $D_k$ in line <ref>.

Satellite Learning Procedure
[1]
ClientOpt$\vec w$
initialize $\vec{w}_k^{n,0} = \vec{w}^n, \quad i = 0$
$I$ epochs
$I$ epochs of mini-batch SGD
$\tilde{\mathcal D}_k \gets $ Randomly shuffle $\mathcal D_k$
$\mathscr B \gets $ Partition $\tilde{\mathcal D}_k$ into mini-batches of size $B$
each batch $\mathcal B\in\mathscr B$
$\vec{w}_k^{n,i+1} \gets \vec{w}_k^{n,i} - \frac{\eta}{|\mathcal B|} \nabla_{\vec{w}} \left(\sum_{\vec x\in\mathcal B} f(\vec x; \vec w) \right)$
$i \gets i + 1$

$\vec{g}_k(\vec{w}^{n}_{k}) \gets \vec{w}^{n,i}_{k}-\vec{w}^{n,0}_{k}$
Compute effective gradient
$\bar{\vec g}_{k}(\vec{w}^{n}_{k}) \gets \Call{CompressGradient}{\vec{g}_k(\vec{w}^{n}_{k})}$
Apply gradient compression (e.g., sparsification)
$D_k \bar{\vec g}_{k}(\vec{w}^{n}_{k})$

Note that the subsequent results do not rely on the explicit implementation of the sgd procedure in lines <ref>–<ref>. The only requirement is that the updated model parameters can be incorporated into the global model based on effective gradients using the update rules presented in <ref>. However, we will use the implementation in <ref> throughout this paper.

For the routing procedure developed in <ref>, we will require an accurate estimate of the time to run <ref>. Apart from scheduling delays due to multi-task computing, the runtime directly depends on the number of processor cycles for each operation in <ref>. These are hardware-dependent, deterministic, and can be determined offline before deployment <cit.>. First, consider a single epoch. The local data set is shuffled and divided into
$\left\lceil \frac{D_k}{B} \right\rceil$ mini-batches. This process takes $c_\mathrm{epoch}$ CPU cycles per sample. Computation of the stochastic gradients requires, in total, $n_d D_k c_\mathrm{s}$ CPU cycles, where $c_\mathrm{s}$ is the number of cycles to process one sample for a single dimension of $\vec w$. Executing the gradient step takes, per mini-batch, $n_d c_\mathrm{step}$ clock cycles.
Thus, one epoch requires a total of
$D_k c_\mathrm{epoch} + n_d D_k c_\mathrm{s} + \left\lceil \frac{D_k}{B} \right\rceil n_d c_\mathrm{step}$
CPU cycles.
After $I$ epochs, a final gradient step taking $n_d c_\mathrm{step}$ cycles is performed to compute the effective gradient. The gradient compression takes an additional $c_\mathrm{compress}$ cycles (see <ref>) and is assumed zero if no compression is used.
Passing the result to the communication stack takes, together with other overhead occurring due to, e.g., process setup and termination, a total of $c_\mathrm{os}$ cycles. The runtime of <ref> is

\begin{equation} \label{eq: Time of learning}
t_l(k) = \frac{I D_k (c_\mathrm{epoch} + n_d c_\mathrm{s}) + c_\mathrm{step} n_d \left( I \left  \lceil \frac{D_k}{B} \right\rceil + 1\right) + c_\mathrm{compress} + c_\mathrm{os}}{\nu_k},
\end{equation}

where $\nu_k$ is the CPU frequency at satellite $k$.

§ ORCHESTRATION OF SATELLITE FEDERATED LEARNING

Federated learning uses a conventional client-server architecture to orchestrate the training process. While the clients compute the stochastic gradient steps for <ref>, the ps is responsible for aggregating these gradient steps, updating the global model parameters, and distributing the updated parameter vector to the clients.
In a conventional fl setup, the ps is also responsible for client scheduling, modeled as an uniform sampling of a subset of clients in each global iteration. Given that fl operates on a massive number of clients, this is equivalent to a two-stage sgd step, the first step being a client selection and the second computation. Instead, sfl operates with significantly fewer (orders of magnitude) clients and each client has a much larger share of the total data, exhibiting a non-negligible contribution to the unbiased  model convergence. Hence, it is reasonable that all clients participate in every global iteration.

Connectivity towards the workers is necessary for synchronization of the training process. In sfl, the communication window from a single leo satellite towards a ground-based ps is usually in the order of a few minutes, followed by an offline period due to Earth blockage, ranging from one orbital period up to several hours. As shown in <cit.>, the conventional FedAvg operation of collecting all local updates before creating a new global model iteration leads to severe delays in the training process. This bottleneck can be partially mitigated by modifying FedAvg for asynchronous operation <cit.>.
Compared to synchronous fl, asynchronous fl has a
slower convergence speed in terms of gradient steps. For ground-orchestrated sfl without isl, this decrease is greatly outweighed by the reduction in the delay between gradient steps, resulting in much faster overall convergence speed, measured in wall time. Leveraging isl, the optimal ps operation very much depends on the ps location and resulting connectivity patterns <cit.>. We will introduce both orchestration approaches in a unified manner in <ref>.
The actual aggregation rule at the ps is easily exchangeable as long as additivity of individual client updates holds. This broadens the contribution of <ref>, as it allows to improve the ps operation while preserving the dense connectivity patterns enabled by isl.

§.§ Synchronous Orchestration

A synchronous fl ps, exemplified by FedAvg <cit.>, repeats the
following steps until a termination criterion for the global model is met:

* Transmit the global model parameters $\vec{w}$ to the scheduled clients;

* Wait for the clients to run <ref> and return their results;

* Aggregate the received gradients and update the global model parameters.

The difference between fl algorithms is in the computation of gradients in <ref> and the update rule in Step 3). While we focus on FedAvg here, the extension to many other algorithms is trivial.

Consider global iteration $n$ and assume all clients are scheduled to participate in this iteration. Plain FedAvg implements the update rule
$\vec w^{n+1} = \frac{1}{D} \sum_{k = 1}^K D_k \vec w_k^{n}$,
where $\vec w^{n}_k$ is the updated parameter vector of client $k$. An equivalent update rule based on effective gradients $\vec g_k(\vec w^n_k)$, as transmitted by <ref>, is

\begin{equation} \label{eq: FedISLSyncc}
\vec w^{n+1} = \frac{1}{D} \sum_{k=1}^K D_k \left( \vec w_k^{n,i} - \vec w_k^{n,0} \right) + \frac{1}{D} \sum_{k=1}^K D_k \vec w_k^{n,0}
= \vec w^{n} + \frac{1}{D} \sum_{k=1}^K D_k \vec g_k(\vec w_k^n).
\end{equation}

A common generalization is to add a global server learning rate $\eta_s$ to this update rule, i.e.,
$\vec w^{n+1} = \vec w^{n} - \eta_s \vec\gamma^n$, where $\vec\gamma^n = -\frac{1}{D} \sum_{k=1}^K D_k \vec g_k(\vec w_k^n)$ <cit.>.

The complete algorithm for ps operation in the sfl scenario, in relation to the client update procedure in <ref>, is given in <ref>. This is a modified version of the delay-tolerant FedAvg implementation in <cit.>. It is initialized in line <ref>, where a set of client clusters $\mathscr C$ is defined. This is required for the efficient use of isl in <ref>. The idea is to treat each cluster as if it were an individual user, receiving the current parameter vector only once and also delivering a single effective gradient per global iteration. For now, as well as for scenarios without isl, it can be assumed that satellite/client $k$ is mapped to cluster $\mathcal C_k$, with $P$ clusters in total. The ps maintains the training process until the sequence $\{ \vec w^1, \vec w^2, \dots \}$ satisfies the termination criterion in line <ref>. Each iteration of this outer loop corresponds to a global iteration, counted as $n$. The sets $\mathcal T^n$ and $\mathcal R^n$ track the transmission of $\vec w^n$ and reception of the gradient update to $\vec w^n$ per client group, respectively. Hence, the inner loop in line <ref>–<ref> runs until updates have been received from all clusters in $\mathscr C$. This loop blocks until a satellite connects to the ps in line <ref>. Note that this could also mean continuing a connection that was not terminated the previous iteration. A message from the satellite is received that either requests the transmission of the current parameter vector or contains the update from the satellite's cluster.

Synchronous PS Operation
[1]
initialize global iteration $n = 0$, model $\vec{w}^0$,
and client clusters $\mathscr C = \{ \mathcal C_1, \mathcal C_2, \dots \}$
termination criterion not met
Set $n \gets n + 1$, $\mathcal T^n = \mathcal R^n = \emptyset$, $\vec w^n \gets \vec w^{n-1}$
$|\mathcal R^n| < |\mathscr C|$
Wait until connection from satellite $k$:
Receive message $m$
Find $p$ such that $k \in \mathcal C_p$
$p \notin \mathcal T^n$ and $m$ is request for data
Transmit $\vec w^{n-1}$ to satellite $k$
Upon successful transfer, add $p$ to $\mathcal T^n$
$p \notin \mathcal R^n$
and $m$ contains gradient update $\vec\gamma_p$
$\tilde{\vec\gamma}_p \gets \Call{UncompressGradient}{\vec\gamma_p}$
$\vec w^n \gets \vec w^n + \frac{1}{D} \tilde{\vec\gamma}_p$
Add $p$ to $\mathcal R^n$
Acknowledge reception to $k$
$|\mathcal R^n| < |\mathscr C|$
Terminate connection

Asynchronous PS Operation
[1]
initialize global iteration $n = 0$, model $\vec{w}^0$, $\mathcal A = \mathcal B = \emptyset$,
and client clusters $\mathscr C = \{ \mathcal C_1, \mathcal C_2, \dots \}$
Wait until connection from satellite $k$:
Receive message $m$
Find $p$ such that $k \in \mathcal C_p$
$p \in \mathcal A$ and $m$ contains gradient update $\vec\gamma_p$
$\tilde{\vec\gamma}_p \gets \Call{UncompressGradient}{\vec\gamma_p}$
$\vec w^n \gets \vec w^n + \frac{1}{D} \tilde{\vec\gamma}_p$
$\mathcal A \gets \mathcal A \setminus \{ p \}$
Acknowledge reception to $k$
Wait for new message $m$

termination criterion is met
$\mathcal B \gets \{ 1, 2, \dots, P \} \setminus \mathcal A$
$\mathcal A = \emptyset$
Terminate loop (and connection)
$\mathcal B \gets \emptyset$

$p \notin \mathcal A \cup \mathcal B$ and $m$ is request for data
Transmit $\vec w^{n-1}$ to satellite $k$
Upon successful transfer, add $p$ to $\mathcal A$
Terminate connection

If the satellite requests transmission of $\vec w^n$ and it was not yet delivered to its cluster, it will be transmitted in line <ref>. Successful reception must be acknowledged by the satellite. A possible implementation is the Bundle protocol's custody transfer <cit.>. Then, this cluster is marked as having received the transmission in line <ref>. All subsequent transmission requests for $\vec w^n$ to satellites of this cluster will be rejected by terminating the connection in line <ref>. If the satellite transmits an update $\vec\gamma_p$ to $\vec w^n$ and the cluster has not yet transmitted an update in the iteration, the compression applied in line <ref> of <ref> is decoded in line <ref>. Without compression, UncompressGradient is the identity function. Then, the update rule <ref> is applied in line <ref>. incrementally (see also line <ref>) and relies on the received gradient already being scaled by $D_k$. Unless the current iteration is finished, the connection is terminated in <ref>.

§.§ Asynchronous Orchestration

As opposed to synchronous operation, in asynchronous ps operation  the ps does not delay the global model update until all clients have delivered their local updates. Instead, it opportunistically  incorporates received gradient updates into a new iteration of the global model, which is subsequently distributed to the clients. Consequently, clients simultaneously operate on different version of the model parameters and gradient updates are typically based on an outdated version of the model parameters, reducing the convergence speed and, potentially, numerical problems. For sfl, this stalenenss, i.e., the age of the local model with respect to the current global model, is bounded due to the quasiperiodicity of this scenario. Hence, we are operating in the partially asynchronous domain, which leads to, generally speaking, much better convergence properties than in totally asynchronous scenarios with unbounded delays <cit.>.

Inspired by <cit.>, an asynchronous version of <ref> is proposed in <ref>. It consists of the same functional blocks  as <ref>: Wait for incoming connections in lines <ref>–<ref>, incorporate and acknowledge gradient updates in lines <ref>–<ref>, run until global convergence (lines <ref>–<ref>), and transmit the current version of the model parameters in lines <ref>–<ref>. The main difference is that, in <ref>, the nested loop ensures that every cluster adds their update to the global model before this new version is transmitted to any client. Instead, <ref> directly incorporates every received update and immediately starts using this new version to answer requests for data. To avoid race conditions within the clusters, <ref> uses the set $\mathcal A$ to track active clusters, i.e., clusters that received the model parameters and did not yet return an update.

Another difference is that the global termination criterion, after being first met, might not remain valid after receiving the outstanding updates from active clusters. To handle this, whenever a new global model satisfies the termination criterion, all inactive clusters in $\mathcal B$, including the currently connected, are blocked from further computations. This is repeated until no active cluster remains. If the termination criterion is violated for any update, all blocks are removed in line <ref> and the algorithm resumes normal operation.

§ INTRA-ORBIT AGGREGATION FOR SATELLITE FL

Convergence in sfl is mainly impaired by the connectivity bottleneck between satellites and the ps.
We have discussed algorithmic approaches to this obstacle in the previous section. With the availability of isl, these can be complemented by multi-hop routing to close gaps in connectivity. <Ref> illustrates the potential gain for a constellation having five orbital planes, each with eight satellites, displaying the connection of a single satellite from each plane towards a ps. Using multi-hop routes within the orbital plane leads to significantly prolonged online periods as compared to the sporadic point-to-point connectivity. For simplicity, we focus on synchronous orchestration first and review the specifics for asynchronous orchestration in <ref>.

[ps located in a gs in Bremen, Germany.]
[xscale=1.8, node distance =  3.5mm,
every node/.style=font=,
fill = Crimson,
draw = none,
fill = Grey,
fill = Lavender,
fill = WhiteSmoke,

[labelnode] (l0) $\mathcal C_{1}$;
[labelnode, below=of l0] (l1) $\mathcal C_{2}$;
[labelnode, below=of l1] (l2) $\mathcal C_{3}$;
[labelnode, below=of l2] (l3) $\mathcal C_{4}$;
[labelnode, below=of l3] (l4) $\mathcal C_{5}$;

ıin 0, 1, ..., 4

[anchor = west, font=] (ttı) at ($(l\i.east) + (32.4mm,1.5*\by)$) 1 satellite;
[anchor = west, font=] at ($(tt\i.west) + (0,-3*\by)$) 8 satellites;

[transform canvas=yshift=1.5]
[bar] ($(l0.east)+(3.587mm,\by)$) rectangle ($(l0.east)+(4.2695mm,-\by)$);
[bar] ($(l0.east)+(7.57mm,\by)$) rectangle ($(l0.east)+(8.263mm,-\by)$);
[bar] ($(l0.east)+(11.5975mm,\by)$) rectangle ($(l0.east)+(12.2875mm,-\by)$);
[bar] ($(l0.east)+(15.597mm,\by)$) rectangle ($(l0.east)+(16.289mm,-\by)$);
[bar] ($(l0.east)+(19.593mm,\by)$) rectangle ($(l0.east)+(20.1625mm,-\by)$);

[bar] ($(l1.east)+(7.339mm,\by)$) rectangle ($(l1.east)+(7.7025mm,-\by)$);
[bar] ($(l1.east)+(11.087mm,\by)$) rectangle ($(l1.east)+(11.747mm,-\by)$);
[bar] ($(l1.east)+(15.04mm,\by)$) rectangle ($(l1.east)+(15.736mm,-\by)$);
[bar] ($(l1.east)+(19.0655mm,\by)$) rectangle ($(l1.east)+(19.753mm,-\by)$);
[bar] ($(l1.east)+(23.0745mm,\by)$) rectangle ($(l1.east)+(23.771mm,-\by)$);
[bar] ($(l1.east)+(27.0635mm,\by)$) rectangle ($(l1.east)+(27.6905mm,-\by)$);
[bar] ($(l1.east)+(31.2425mm,\by)$) rectangle ($(l1.east)+(31.265mm,-\by)$);

[bar] ($(l2.east)+(18.601mm,\by)$) rectangle ($(l2.east)+(19.222mm,-\by)$);
[bar] ($(l2.east)+(22.515mm,\by)$) rectangle ($(l2.east)+(23.2115mm,-\by)$);
[bar] ($(l2.east)+(26.5315mm,\by)$) rectangle ($(l2.east)+(27.219mm,-\by)$);
[bar] ($(l2.east)+(30.5495mm,\by)$) rectangle ($(l2.east)+(31.2455mm,-\by)$);

[bar] ($(l3.east)+(0.143mm,\by)$) rectangle ($(l3.east)+(0.8095mm,-\by)$);
[bar] ($(l3.east)+(4.176mm,\by)$) rectangle ($(l3.east)+(4.584mm,-\by)$);
[bar] ($(l3.east)+(26.137mm,\by)$) rectangle ($(l3.east)+(26.692mm,-\by)$);
[bar] ($(l3.east)+(29.998mm,\by)$) rectangle ($(l3.east)+(30.6895mm,-\by)$);

[bar] ($(l4.east)+(3.6255mm,\by)$) rectangle ($(l4.east)+(4.318mm,-\by)$);
[bar] ($(l4.east)+(7.621mm,\by)$) rectangle ($(l4.east)+(8.307mm,-\by)$);
[bar] ($(l4.east)+(11.6245mm,\by)$) rectangle ($(l4.east)+(12.1495mm,-\by)$);

[transform canvas=yshift=-1.5]
[bar] ($(l0.east)+(0.2235mm,\by)$) rectangle ($(l0.east)+(21.0925mm,-\by)$);
[bar] ($(l0.east)+(21.1175mm,\by)$) rectangle ($(l0.east)+(21.5485mm,-\by)$);
[bar] ($(l0.east)+(21.6375mm,\by)$) rectangle ($(l0.east)+(21.993mm,-\by)$);
[bar] ($(l0.east)+(22.174mm,\by)$) rectangle ($(l0.east)+(22.4185mm,-\by)$);
[bar2] ($(l0.east)+(0,-\by-1*\dy)+(3.587mm,\dy)$) rectangle ($(l0.east)+(0,-\by-1*\dy)+(4.2695mm,-\dy)$);
[bar2] ($(l0.east)+(0,-\by-1*\dy)+(7.57mm,\dy)$) rectangle ($(l0.east)+(0,-\by-1*\dy)+(8.263mm,-\dy)$);
[bar2] ($(l0.east)+(0,-\by-1*\dy)+(11.5975mm,\dy)$) rectangle ($(l0.east)+(0,-\by-1*\dy)+(12.2875mm,-\dy)$);
[bar2] ($(l0.east)+(0,-\by-1*\dy)+(15.597mm,\dy)$) rectangle ($(l0.east)+(0,-\by-1*\dy)+(16.289mm,-\dy)$);
[bar2] ($(l0.east)+(0,-\by-1*\dy)+(19.593mm,\dy)$) rectangle ($(l0.east)+(0,-\by-1*\dy)+(20.1625mm,-\dy)$);
[bar2] ($(l0.east)+(0,-\by-3*\dy)+(3.0975mm,\dy)$) rectangle ($(l0.east)+(0,-\by-3*\dy)+(3.771mm,-\dy)$);
[bar2] ($(l0.east)+(0,-\by-3*\dy)+(7.0675mm,\dy)$) rectangle ($(l0.east)+(0,-\by-3*\dy)+(7.762mm,-\dy)$);
[bar2] ($(l0.east)+(0,-\by-3*\dy)+(11.095mm,\dy)$) rectangle ($(l0.east)+(0,-\by-3*\dy)+(11.784mm,-\dy)$);
[bar2] ($(l0.east)+(0,-\by-3*\dy)+(15.099mm,\dy)$) rectangle ($(l0.east)+(0,-\by-3*\dy)+(15.794mm,-\dy)$);
[bar2] ($(l0.east)+(0,-\by-3*\dy)+(19.0905mm,\dy)$) rectangle ($(l0.east)+(0,-\by-3*\dy)+(19.6895mm,-\dy)$);
[bar2] ($(l0.east)+(0,-\by-5*\dy)+(2.6105mm,\dy)$) rectangle ($(l0.east)+(0,-\by-5*\dy)+(3.273mm,-\dy)$);
[bar2] ($(l0.east)+(0,-\by-5*\dy)+(6.566mm,\dy)$) rectangle ($(l0.east)+(0,-\by-5*\dy)+(7.262mm,-\dy)$);
[bar2] ($(l0.east)+(0,-\by-5*\dy)+(10.592mm,\dy)$) rectangle ($(l0.east)+(0,-\by-5*\dy)+(11.28mm,-\dy)$);
[bar2] ($(l0.east)+(0,-\by-5*\dy)+(14.6mm,\dy)$) rectangle ($(l0.east)+(0,-\by-5*\dy)+(15.297mm,-\dy)$);
[bar2] ($(l0.east)+(0,-\by-5*\dy)+(18.5895mm,\dy)$) rectangle ($(l0.east)+(0,-\by-5*\dy)+(19.2125mm,-\dy)$);
[bar2] ($(l0.east)+(0,-\by-7*\dy)+(2.126mm,\dy)$) rectangle ($(l0.east)+(0,-\by-7*\dy)+(2.774mm,-\dy)$);
[bar2] ($(l0.east)+(0,-\by-7*\dy)+(6.0655mm,\dy)$) rectangle ($(l0.east)+(0,-\by-7*\dy)+(6.762mm,-\dy)$);
[bar2] ($(l0.east)+(0,-\by-7*\dy)+(10.0885mm,\dy)$) rectangle ($(l0.east)+(0,-\by-7*\dy)+(10.776mm,-\dy)$);
[bar2] ($(l0.east)+(0,-\by-7*\dy)+(14.101mm,\dy)$) rectangle ($(l0.east)+(0,-\by-7*\dy)+(14.798mm,-\dy)$);
[bar2] ($(l0.east)+(0,-\by-7*\dy)+(18.0895mm,\dy)$) rectangle ($(l0.east)+(0,-\by-7*\dy)+(18.732mm,-\dy)$);
[bar2] ($(l0.east)+(0,-\by-7*\dy)+(22.174mm,\dy)$) rectangle ($(l0.east)+(0,-\by-7*\dy)+(22.4185mm,-\dy)$);
[bar2] ($(l0.east)+(0,-\by-9*\dy)+(1.645mm,\dy)$) rectangle ($(l0.east)+(0,-\by-9*\dy)+(2.274mm,-\dy)$);
[bar2] ($(l0.east)+(0,-\by-9*\dy)+(5.566mm,\dy)$) rectangle ($(l0.east)+(0,-\by-9*\dy)+(6.263mm,-\dy)$);
[bar2] ($(l0.east)+(0,-\by-9*\dy)+(9.5845mm,\dy)$) rectangle ($(l0.east)+(0,-\by-9*\dy)+(10.2725mm,-\dy)$);
[bar2] ($(l0.east)+(0,-\by-9*\dy)+(13.6015mm,\dy)$) rectangle ($(l0.east)+(0,-\by-9*\dy)+(14.298mm,-\dy)$);
[bar2] ($(l0.east)+(0,-\by-9*\dy)+(17.5905mm,\dy)$) rectangle ($(l0.east)+(0,-\by-9*\dy)+(18.249mm,-\dy)$);
[bar2] ($(l0.east)+(0,-\by-9*\dy)+(21.6375mm,\dy)$) rectangle ($(l0.east)+(0,-\by-9*\dy)+(21.993mm,-\dy)$);
[bar2] ($(l0.east)+(0,-\by-11*\dy)+(1.167mm,\dy)$) rectangle ($(l0.east)+(0,-\by-11*\dy)+(1.7735mm,-\dy)$);
[bar2] ($(l0.east)+(0,-\by-11*\dy)+(5.0685mm,\dy)$) rectangle ($(l0.east)+(0,-\by-11*\dy)+(5.764mm,-\dy)$);
[bar2] ($(l0.east)+(0,-\by-11*\dy)+(9.081mm,\dy)$) rectangle ($(l0.east)+(0,-\by-11*\dy)+(9.769mm,-\dy)$);
[bar2] ($(l0.east)+(0,-\by-11*\dy)+(13.1015mm,\dy)$) rectangle ($(l0.east)+(0,-\by-11*\dy)+(13.7965mm,-\dy)$);
[bar2] ($(l0.east)+(0,-\by-11*\dy)+(17.092mm,\dy)$) rectangle ($(l0.east)+(0,-\by-11*\dy)+(17.7625mm,-\dy)$);
[bar2] ($(l0.east)+(0,-\by-11*\dy)+(21.1175mm,\dy)$) rectangle ($(l0.east)+(0,-\by-11*\dy)+(21.5485mm,-\dy)$);
[bar2] ($(l0.east)+(0,-\by-13*\dy)+(0.693mm,\dy)$) rectangle ($(l0.east)+(0,-\by-13*\dy)+(1.2715mm,-\dy)$);
[bar2] ($(l0.east)+(0,-\by-13*\dy)+(4.5725mm,\dy)$) rectangle ($(l0.east)+(0,-\by-13*\dy)+(5.266mm,-\dy)$);
[bar2] ($(l0.east)+(0,-\by-13*\dy)+(8.577mm,\dy)$) rectangle ($(l0.east)+(0,-\by-13*\dy)+(9.267mm,-\dy)$);
[bar2] ($(l0.east)+(0,-\by-13*\dy)+(12.601mm,\dy)$) rectangle ($(l0.east)+(0,-\by-13*\dy)+(13.295mm,-\dy)$);
[bar2] ($(l0.east)+(0,-\by-13*\dy)+(16.594mm,\dy)$) rectangle ($(l0.east)+(0,-\by-13*\dy)+(17.274mm,-\dy)$);
[bar2] ($(l0.east)+(0,-\by-13*\dy)+(20.6055mm,\dy)$) rectangle ($(l0.east)+(0,-\by-13*\dy)+(21.0925mm,-\dy)$);
[bar2] ($(l0.east)+(0,-\by-15*\dy)+(0.2235mm,\dy)$) rectangle ($(l0.east)+(0,-\by-15*\dy)+(0.768mm,-\dy)$);
[bar2] ($(l0.east)+(0,-\by-15*\dy)+(4.079mm,\dy)$) rectangle ($(l0.east)+(0,-\by-15*\dy)+(4.768mm,-\dy)$);
[bar2] ($(l0.east)+(0,-\by-15*\dy)+(8.074mm,\dy)$) rectangle ($(l0.east)+(0,-\by-15*\dy)+(8.765mm,-\dy)$);
[bar2] ($(l0.east)+(0,-\by-15*\dy)+(12.1mm,\dy)$) rectangle ($(l0.east)+(0,-\by-15*\dy)+(12.7915mm,-\dy)$);
[bar2] ($(l0.east)+(0,-\by-15*\dy)+(16.096mm,\dy)$) rectangle ($(l0.east)+(0,-\by-15*\dy)+(16.7825mm,-\dy)$);
[bar2] ($(l0.east)+(0,-\by-15*\dy)+(20.098mm,\dy)$) rectangle ($(l0.east)+(0,-\by-15*\dy)+(20.632mm,-\dy)$);
[bar] ($(l1.east)+(6.9105mm,\by)$) rectangle ($(l1.east)+(7.168mm,-\by)$);
[bar] ($(l1.east)+(7.339mm,\by)$) rectangle ($(l1.east)+(7.7025mm,-\by)$);
[bar] ($(l1.east)+(7.785mm,\by)$) rectangle ($(l1.east)+(8.2215mm,-\by)$);
[bar] ($(l1.east)+(8.241mm,\by)$) rectangle ($(l1.east)+(29.5745mm,-\by)$);
[bar] ($(l1.east)+(29.5885mm,\by)$) rectangle ($(l1.east)+(30.0315mm,-\by)$);
[bar] ($(l1.east)+(30.107mm,\by)$) rectangle ($(l1.east)+(30.4785mm,-\by)$);
[bar] ($(l1.east)+(30.639mm,\by)$) rectangle ($(l1.east)+(30.909mm,-\by)$);
[bar] ($(l1.east)+(31.2425mm,\by)$) rectangle ($(l1.east)+(31.265mm,-\by)$);
[bar2] ($(l1.east)+(0,-\by-1*\dy)+(7.339mm,\dy)$) rectangle ($(l1.east)+(0,-\by-1*\dy)+(7.7025mm,-\dy)$);
[bar2] ($(l1.east)+(0,-\by-1*\dy)+(11.087mm,\dy)$) rectangle ($(l1.east)+(0,-\by-1*\dy)+(11.747mm,-\dy)$);
[bar2] ($(l1.east)+(0,-\by-1*\dy)+(15.04mm,\dy)$) rectangle ($(l1.east)+(0,-\by-1*\dy)+(15.736mm,-\dy)$);
[bar2] ($(l1.east)+(0,-\by-1*\dy)+(19.0655mm,\dy)$) rectangle ($(l1.east)+(0,-\by-1*\dy)+(19.753mm,-\dy)$);
[bar2] ($(l1.east)+(0,-\by-1*\dy)+(23.0745mm,\dy)$) rectangle ($(l1.east)+(0,-\by-1*\dy)+(23.771mm,-\dy)$);
[bar2] ($(l1.east)+(0,-\by-1*\dy)+(27.0635mm,\dy)$) rectangle ($(l1.east)+(0,-\by-1*\dy)+(27.6905mm,-\dy)$);
[bar2] ($(l1.east)+(0,-\by-1*\dy)+(31.2425mm,\dy)$) rectangle ($(l1.east)+(0,-\by-1*\dy)+(31.265mm,-\dy)$);
[bar2] ($(l1.east)+(0,-\by-3*\dy)+(6.9105mm,\dy)$) rectangle ($(l1.east)+(0,-\by-3*\dy)+(7.168mm,-\dy)$);
[bar2] ($(l1.east)+(0,-\by-3*\dy)+(10.6035mm,\dy)$) rectangle ($(l1.east)+(0,-\by-3*\dy)+(11.248mm,-\dy)$);
[bar2] ($(l1.east)+(0,-\by-3*\dy)+(14.5395mm,\dy)$) rectangle ($(l1.east)+(0,-\by-3*\dy)+(15.2365mm,-\dy)$);
[bar2] ($(l1.east)+(0,-\by-3*\dy)+(18.562mm,\dy)$) rectangle ($(l1.east)+(0,-\by-3*\dy)+(19.2495mm,-\dy)$);
[bar2] ($(l1.east)+(0,-\by-3*\dy)+(22.5755mm,\dy)$) rectangle ($(l1.east)+(0,-\by-3*\dy)+(23.272mm,-\dy)$);
[bar2] ($(l1.east)+(0,-\by-3*\dy)+(26.5635mm,\dy)$) rectangle ($(l1.east)+(0,-\by-3*\dy)+(27.2095mm,-\dy)$);
[bar2] ($(l1.east)+(0,-\by-3*\dy)+(30.639mm,\dy)$) rectangle ($(l1.east)+(0,-\by-3*\dy)+(30.909mm,-\dy)$);
[bar2] ($(l1.east)+(0,-\by-5*\dy)+(10.123mm,\dy)$) rectangle ($(l1.east)+(0,-\by-5*\dy)+(10.748mm,-\dy)$);
[bar2] ($(l1.east)+(0,-\by-5*\dy)+(14.0405mm,\dy)$) rectangle ($(l1.east)+(0,-\by-5*\dy)+(14.737mm,-\dy)$);
[bar2] ($(l1.east)+(0,-\by-5*\dy)+(18.058mm,\dy)$) rectangle ($(l1.east)+(0,-\by-5*\dy)+(18.746mm,-\dy)$);
[bar2] ($(l1.east)+(0,-\by-5*\dy)+(22.0755mm,\dy)$) rectangle ($(l1.east)+(0,-\by-5*\dy)+(22.7715mm,-\dy)$);
[bar2] ($(l1.east)+(0,-\by-5*\dy)+(26.0645mm,\dy)$) rectangle ($(l1.east)+(0,-\by-5*\dy)+(26.7255mm,-\dy)$);
[bar2] ($(l1.east)+(0,-\by-5*\dy)+(30.107mm,\dy)$) rectangle ($(l1.east)+(0,-\by-5*\dy)+(30.4785mm,-\dy)$);
[bar2] ($(l1.east)+(0,-\by-7*\dy)+(9.646mm,\dy)$) rectangle ($(l1.east)+(0,-\by-7*\dy)+(10.2475mm,-\dy)$);
[bar2] ($(l1.east)+(0,-\by-7*\dy)+(13.543mm,\dy)$) rectangle ($(l1.east)+(0,-\by-7*\dy)+(14.2385mm,-\dy)$);
[bar2] ($(l1.east)+(0,-\by-7*\dy)+(17.554mm,\dy)$) rectangle ($(l1.east)+(0,-\by-7*\dy)+(18.2425mm,-\dy)$);
[bar2] ($(l1.east)+(0,-\by-7*\dy)+(21.5755mm,\dy)$) rectangle ($(l1.east)+(0,-\by-7*\dy)+(22.27mm,-\dy)$);
[bar2] ($(l1.east)+(0,-\by-7*\dy)+(25.566mm,\dy)$) rectangle ($(l1.east)+(0,-\by-7*\dy)+(26.239mm,-\dy)$);
[bar2] ($(l1.east)+(0,-\by-7*\dy)+(29.5885mm,\dy)$) rectangle ($(l1.east)+(0,-\by-7*\dy)+(30.0315mm,-\dy)$);
[bar2] ($(l1.east)+(0,-\by-9*\dy)+(9.1725mm,\dy)$) rectangle ($(l1.east)+(0,-\by-9*\dy)+(9.745mm,-\dy)$);
[bar2] ($(l1.east)+(0,-\by-9*\dy)+(13.0475mm,\dy)$) rectangle ($(l1.east)+(0,-\by-9*\dy)+(13.74mm,-\dy)$);
[bar2] ($(l1.east)+(0,-\by-9*\dy)+(17.05mm,\dy)$) rectangle ($(l1.east)+(0,-\by-9*\dy)+(17.74mm,-\dy)$);
[bar2] ($(l1.east)+(0,-\by-9*\dy)+(21.0745mm,\dy)$) rectangle ($(l1.east)+(0,-\by-9*\dy)+(21.7675mm,-\dy)$);
[bar2] ($(l1.east)+(0,-\by-9*\dy)+(25.068mm,\dy)$) rectangle ($(l1.east)+(0,-\by-9*\dy)+(25.7495mm,-\dy)$);
[bar2] ($(l1.east)+(0,-\by-9*\dy)+(29.0775mm,\dy)$) rectangle ($(l1.east)+(0,-\by-9*\dy)+(29.5745mm,-\dy)$);
[bar2] ($(l1.east)+(0,-\by-11*\dy)+(8.704mm,\dy)$) rectangle ($(l1.east)+(0,-\by-11*\dy)+(9.2405mm,-\dy)$);
[bar2] ($(l1.east)+(0,-\by-11*\dy)+(12.554mm,\dy)$) rectangle ($(l1.east)+(0,-\by-11*\dy)+(13.242mm,-\dy)$);
[bar2] ($(l1.east)+(0,-\by-11*\dy)+(16.5465mm,\dy)$) rectangle ($(l1.east)+(0,-\by-11*\dy)+(17.238mm,-\dy)$);
[bar2] ($(l1.east)+(0,-\by-11*\dy)+(20.573mm,\dy)$) rectangle ($(l1.east)+(0,-\by-11*\dy)+(21.2645mm,-\dy)$);
[bar2] ($(l1.east)+(0,-\by-11*\dy)+(24.5695mm,\dy)$) rectangle ($(l1.east)+(0,-\by-11*\dy)+(25.258mm,-\dy)$);
[bar2] ($(l1.east)+(0,-\by-11*\dy)+(28.5705mm,\dy)$) rectangle ($(l1.east)+(0,-\by-11*\dy)+(29.1105mm,-\dy)$);
[bar2] ($(l1.east)+(0,-\by-13*\dy)+(8.241mm,\dy)$) rectangle ($(l1.east)+(0,-\by-13*\dy)+(8.733mm,-\dy)$);
[bar2] ($(l1.east)+(0,-\by-13*\dy)+(12.063mm,\dy)$) rectangle ($(l1.east)+(0,-\by-13*\dy)+(12.744mm,-\dy)$);
[bar2] ($(l1.east)+(0,-\by-13*\dy)+(16.0435mm,\dy)$) rectangle ($(l1.east)+(0,-\by-13*\dy)+(16.7365mm,-\dy)$);
[bar2] ($(l1.east)+(0,-\by-13*\dy)+(20.071mm,\dy)$) rectangle ($(l1.east)+(0,-\by-13*\dy)+(20.761mm,-\dy)$);
[bar2] ($(l1.east)+(0,-\by-13*\dy)+(24.0715mm,\dy)$) rectangle ($(l1.east)+(0,-\by-13*\dy)+(24.7645mm,-\dy)$);
[bar2] ($(l1.east)+(0,-\by-13*\dy)+(28.066mm,\dy)$) rectangle ($(l1.east)+(0,-\by-13*\dy)+(28.6415mm,-\dy)$);
[bar2] ($(l1.east)+(0,-\by-15*\dy)+(7.785mm,\dy)$) rectangle ($(l1.east)+(0,-\by-15*\dy)+(8.2215mm,-\dy)$);
[bar2] ($(l1.east)+(0,-\by-15*\dy)+(11.574mm,\dy)$) rectangle ($(l1.east)+(0,-\by-15*\dy)+(12.2455mm,-\dy)$);
[bar2] ($(l1.east)+(0,-\by-15*\dy)+(15.541mm,\dy)$) rectangle ($(l1.east)+(0,-\by-15*\dy)+(16.236mm,-\dy)$);
[bar2] ($(l1.east)+(0,-\by-15*\dy)+(19.5685mm,\dy)$) rectangle ($(l1.east)+(0,-\by-15*\dy)+(20.257mm,-\dy)$);
[bar2] ($(l1.east)+(0,-\by-15*\dy)+(23.573mm,\dy)$) rectangle ($(l1.east)+(0,-\by-15*\dy)+(24.2685mm,-\dy)$);
[bar2] ($(l1.east)+(0,-\by-15*\dy)+(27.564mm,\dy)$) rectangle ($(l1.east)+(0,-\by-15*\dy)+(28.168mm,-\dy)$);
[bar] ($(l2.east)+(15.4025mm,\by)$) rectangle ($(l2.east)+(15.632mm,-\by)$);
[bar] ($(l2.east)+(15.825mm,\by)$) rectangle ($(l2.east)+(16.171mm,-\by)$);
[bar] ($(l2.east)+(16.2685mm,\by)$) rectangle ($(l2.east)+(16.6925mm,-\by)$);
[bar] ($(l2.east)+(16.723mm,\by)$) rectangle ($(l2.east)+(32.4mm,-\by)$);
[bar2] ($(l2.east)+(0,-\by-1*\dy)+(18.601mm,\dy)$) rectangle ($(l2.east)+(0,-\by-1*\dy)+(19.222mm,-\dy)$);
[bar2] ($(l2.east)+(0,-\by-1*\dy)+(22.515mm,\dy)$) rectangle ($(l2.east)+(0,-\by-1*\dy)+(23.2115mm,-\dy)$);
[bar2] ($(l2.east)+(0,-\by-1*\dy)+(26.5315mm,\dy)$) rectangle ($(l2.east)+(0,-\by-1*\dy)+(27.219mm,-\dy)$);
[bar2] ($(l2.east)+(0,-\by-1*\dy)+(30.5495mm,\dy)$) rectangle ($(l2.east)+(0,-\by-1*\dy)+(31.2455mm,-\dy)$);
[bar2] ($(l2.east)+(0,-\by-3*\dy)+(18.125mm,\dy)$) rectangle ($(l2.east)+(0,-\by-3*\dy)+(18.721mm,-\dy)$);
[bar2] ($(l2.east)+(0,-\by-3*\dy)+(22.018mm,\dy)$) rectangle ($(l2.east)+(0,-\by-3*\dy)+(22.713mm,-\dy)$);
[bar2] ($(l2.east)+(0,-\by-3*\dy)+(26.0275mm,\dy)$) rectangle ($(l2.east)+(0,-\by-3*\dy)+(26.716mm,-\dy)$);
[bar2] ($(l2.east)+(0,-\by-3*\dy)+(30.0495mm,\dy)$) rectangle ($(l2.east)+(0,-\by-3*\dy)+(30.744mm,-\dy)$);
[bar2] ($(l2.east)+(0,-\by-5*\dy)+(17.6525mm,\dy)$) rectangle ($(l2.east)+(0,-\by-5*\dy)+(18.2185mm,-\dy)$);
[bar2] ($(l2.east)+(0,-\by-5*\dy)+(21.523mm,\dy)$) rectangle ($(l2.east)+(0,-\by-5*\dy)+(22.2145mm,-\dy)$);
[bar2] ($(l2.east)+(0,-\by-5*\dy)+(25.5235mm,\dy)$) rectangle ($(l2.east)+(0,-\by-5*\dy)+(26.2135mm,-\dy)$);
[bar2] ($(l2.east)+(0,-\by-5*\dy)+(29.5485mm,\dy)$) rectangle ($(l2.east)+(0,-\by-5*\dy)+(30.241mm,-\dy)$);
[bar2] ($(l2.east)+(0,-\by-7*\dy)+(17.1845mm,\dy)$) rectangle ($(l2.east)+(0,-\by-7*\dy)+(17.7135mm,-\dy)$);
[bar2] ($(l2.east)+(0,-\by-7*\dy)+(21.0295mm,\dy)$) rectangle ($(l2.east)+(0,-\by-7*\dy)+(21.7165mm,-\dy)$);
[bar2] ($(l2.east)+(0,-\by-7*\dy)+(25.02mm,\dy)$) rectangle ($(l2.east)+(0,-\by-7*\dy)+(25.712mm,-\dy)$);
[bar2] ($(l2.east)+(0,-\by-7*\dy)+(29.047mm,\dy)$) rectangle ($(l2.east)+(0,-\by-7*\dy)+(29.738mm,-\dy)$);
[bar2] ($(l2.east)+(0,-\by-9*\dy)+(16.723mm,\dy)$) rectangle ($(l2.east)+(0,-\by-9*\dy)+(17.2055mm,-\dy)$);
[bar2] ($(l2.east)+(0,-\by-9*\dy)+(20.5385mm,\dy)$) rectangle ($(l2.east)+(0,-\by-9*\dy)+(21.218mm,-\dy)$);
[bar2] ($(l2.east)+(0,-\by-9*\dy)+(24.517mm,\dy)$) rectangle ($(l2.east)+(0,-\by-9*\dy)+(25.2105mm,-\dy)$);
[bar2] ($(l2.east)+(0,-\by-9*\dy)+(28.545mm,\dy)$) rectangle ($(l2.east)+(0,-\by-9*\dy)+(29.2345mm,-\dy)$);
[bar2] ($(l2.east)+(0,-\by-11*\dy)+(16.2685mm,\dy)$) rectangle ($(l2.east)+(0,-\by-11*\dy)+(16.6925mm,-\dy)$);
[bar2] ($(l2.east)+(0,-\by-11*\dy)+(20.05mm,\dy)$) rectangle ($(l2.east)+(0,-\by-11*\dy)+(20.72mm,-\dy)$);
[bar2] ($(l2.east)+(0,-\by-11*\dy)+(24.015mm,\dy)$) rectangle ($(l2.east)+(0,-\by-11*\dy)+(24.71mm,-\dy)$);
[bar2] ($(l2.east)+(0,-\by-11*\dy)+(28.042mm,\dy)$) rectangle ($(l2.east)+(0,-\by-11*\dy)+(28.7305mm,-\dy)$);
[bar2] ($(l2.east)+(0,-\by-11*\dy)+(32.0475mm,\dy)$) rectangle ($(l2.east)+(0,-\by-11*\dy)+(32.4mm,-\dy)$);
[bar2] ($(l2.east)+(0,-\by-13*\dy)+(15.825mm,\dy)$) rectangle ($(l2.east)+(0,-\by-13*\dy)+(16.171mm,-\dy)$);
[bar2] ($(l2.east)+(0,-\by-13*\dy)+(19.564mm,\dy)$) rectangle ($(l2.east)+(0,-\by-13*\dy)+(20.2215mm,-\dy)$);
[bar2] ($(l2.east)+(0,-\by-13*\dy)+(23.5135mm,\dy)$) rectangle ($(l2.east)+(0,-\by-13*\dy)+(24.21mm,-\dy)$);
[bar2] ($(l2.east)+(0,-\by-13*\dy)+(27.539mm,\dy)$) rectangle ($(l2.east)+(0,-\by-13*\dy)+(28.2265mm,-\dy)$);
[bar2] ($(l2.east)+(0,-\by-13*\dy)+(31.5485mm,\dy)$) rectangle ($(l2.east)+(0,-\by-13*\dy)+(32.2455mm,-\dy)$);
[bar2] ($(l2.east)+(0,-\by-15*\dy)+(15.4025mm,\dy)$) rectangle ($(l2.east)+(0,-\by-15*\dy)+(15.632mm,-\dy)$);
[bar2] ($(l2.east)+(0,-\by-15*\dy)+(19.081mm,\dy)$) rectangle ($(l2.east)+(0,-\by-15*\dy)+(19.722mm,-\dy)$);
[bar2] ($(l2.east)+(0,-\by-15*\dy)+(23.0135mm,\dy)$) rectangle ($(l2.east)+(0,-\by-15*\dy)+(23.7105mm,-\dy)$);
[bar2] ($(l2.east)+(0,-\by-15*\dy)+(27.035mm,\dy)$) rectangle ($(l2.east)+(0,-\by-15*\dy)+(27.7225mm,-\dy)$);
[bar2] ($(l2.east)+(0,-\by-15*\dy)+(31.0495mm,\dy)$) rectangle ($(l2.east)+(0,-\by-15*\dy)+(31.746mm,-\dy)$);
[bar] ($(l3.east)+(0.143mm,\by)$) rectangle ($(l3.east)+(4.1285mm,-\by)$);
[bar] ($(l3.east)+(4.176mm,\by)$) rectangle ($(l3.east)+(4.584mm,-\by)$);
[bar] ($(l3.east)+(4.7015mm,\by)$) rectangle ($(l3.east)+(5.02mm,-\by)$);
[bar] ($(l3.east)+(5.251mm,\by)$) rectangle ($(l3.east)+(5.43mm,-\by)$);
[bar] ($(l3.east)+(23.897mm,\by)$) rectangle ($(l3.east)+(24.094mm,-\by)$);
[bar] ($(l3.east)+(24.312mm,\by)$) rectangle ($(l3.east)+(24.6395mm,-\by)$);
[bar] ($(l3.east)+(24.753mm,\by)$) rectangle ($(l3.east)+(25.163mm,-\by)$);
[bar] ($(l3.east)+(25.2055mm,\by)$) rectangle ($(l3.east)+(32.4mm,-\by)$);
[bar2] ($(l3.east)+(0,-\by-1*\dy)+(0.143mm,\dy)$) rectangle ($(l3.east)+(0,-\by-1*\dy)+(0.8095mm,-\dy)$);
[bar2] ($(l3.east)+(0,-\by-1*\dy)+(4.176mm,\dy)$) rectangle ($(l3.east)+(0,-\by-1*\dy)+(4.584mm,-\dy)$);
[bar2] ($(l3.east)+(0,-\by-1*\dy)+(26.137mm,\dy)$) rectangle ($(l3.east)+(0,-\by-1*\dy)+(26.692mm,-\dy)$);
[bar2] ($(l3.east)+(0,-\by-1*\dy)+(29.998mm,\dy)$) rectangle ($(l3.east)+(0,-\by-1*\dy)+(30.6895mm,-\dy)$);
[bar2] ($(l3.east)+(0,-\by-3*\dy)+(3.661mm,\dy)$) rectangle ($(l3.east)+(0,-\by-3*\dy)+(4.1285mm,-\dy)$);
[bar2] ($(l3.east)+(0,-\by-3*\dy)+(25.666mm,\dy)$) rectangle ($(l3.east)+(0,-\by-3*\dy)+(26.1865mm,-\dy)$);
[bar2] ($(l3.east)+(0,-\by-3*\dy)+(29.5055mm,\dy)$) rectangle ($(l3.east)+(0,-\by-3*\dy)+(30.191mm,-\dy)$);
[bar2] ($(l3.east)+(0,-\by-5*\dy)+(3.152mm,\dy)$) rectangle ($(l3.east)+(0,-\by-5*\dy)+(3.6685mm,-\dy)$);
[bar2] ($(l3.east)+(0,-\by-5*\dy)+(25.2055mm,\dy)$) rectangle ($(l3.east)+(0,-\by-5*\dy)+(25.6775mm,-\dy)$);
[bar2] ($(l3.east)+(0,-\by-5*\dy)+(29.015mm,\dy)$) rectangle ($(l3.east)+(0,-\by-5*\dy)+(29.6925mm,-\dy)$);
[bar2] ($(l3.east)+(0,-\by-7*\dy)+(2.646mm,\dy)$) rectangle ($(l3.east)+(0,-\by-7*\dy)+(3.2025mm,-\dy)$);
[bar2] ($(l3.east)+(0,-\by-7*\dy)+(24.753mm,\dy)$) rectangle ($(l3.east)+(0,-\by-7*\dy)+(25.163mm,-\dy)$);
[bar2] ($(l3.east)+(0,-\by-7*\dy)+(28.527mm,\dy)$) rectangle ($(l3.east)+(0,-\by-7*\dy)+(29.1945mm,-\dy)$);
[bar2] ($(l3.east)+(0,-\by-9*\dy)+(2.143mm,\dy)$) rectangle ($(l3.east)+(0,-\by-9*\dy)+(2.7315mm,-\dy)$);
[bar2] ($(l3.east)+(0,-\by-9*\dy)+(24.312mm,\dy)$) rectangle ($(l3.east)+(0,-\by-9*\dy)+(24.6395mm,-\dy)$);
[bar2] ($(l3.east)+(0,-\by-9*\dy)+(28.0415mm,\dy)$) rectangle ($(l3.east)+(0,-\by-9*\dy)+(28.6955mm,-\dy)$);
[bar2] ($(l3.east)+(0,-\by-9*\dy)+(31.9875mm,\dy)$) rectangle ($(l3.east)+(0,-\by-9*\dy)+(32.4mm,-\dy)$);
[bar2] ($(l3.east)+(0,-\by-11*\dy)+(1.6415mm,\dy)$) rectangle ($(l3.east)+(0,-\by-11*\dy)+(2.256mm,-\dy)$);
[bar2] ($(l3.east)+(0,-\by-11*\dy)+(23.897mm,\dy)$) rectangle ($(l3.east)+(0,-\by-11*\dy)+(24.094mm,-\dy)$);
[bar2] ($(l3.east)+(0,-\by-11*\dy)+(27.559mm,\dy)$) rectangle ($(l3.east)+(0,-\by-11*\dy)+(28.1965mm,-\dy)$);
[bar2] ($(l3.east)+(0,-\by-11*\dy)+(31.488mm,\dy)$) rectangle ($(l3.east)+(0,-\by-11*\dy)+(32.1845mm,-\dy)$);
[bar2] ($(l3.east)+(0,-\by-13*\dy)+(1.141mm,\dy)$) rectangle ($(l3.east)+(0,-\by-13*\dy)+(1.777mm,-\dy)$);
[bar2] ($(l3.east)+(0,-\by-13*\dy)+(5.251mm,\dy)$) rectangle ($(l3.east)+(0,-\by-13*\dy)+(5.43mm,-\dy)$);
[bar2] ($(l3.east)+(0,-\by-13*\dy)+(27.08mm,\dy)$) rectangle ($(l3.east)+(0,-\by-13*\dy)+(27.696mm,-\dy)$);
[bar2] ($(l3.east)+(0,-\by-13*\dy)+(30.9895mm,\dy)$) rectangle ($(l3.east)+(0,-\by-13*\dy)+(31.686mm,-\dy)$);
[bar2] ($(l3.east)+(0,-\by-15*\dy)+(0.642mm,\dy)$) rectangle ($(l3.east)+(0,-\by-15*\dy)+(1.295mm,-\dy)$);
[bar2] ($(l3.east)+(0,-\by-15*\dy)+(4.7015mm,\dy)$) rectangle ($(l3.east)+(0,-\by-15*\dy)+(5.02mm,-\dy)$);
[bar2] ($(l3.east)+(0,-\by-15*\dy)+(26.6055mm,\dy)$) rectangle ($(l3.east)+(0,-\by-15*\dy)+(27.1955mm,-\dy)$);
[bar2] ($(l3.east)+(0,-\by-15*\dy)+(30.493mm,\dy)$) rectangle ($(l3.east)+(0,-\by-15*\dy)+(31.1875mm,-\dy)$);
[bar] ($(l4.east)+(0.1035mm,\by)$) rectangle ($(l4.east)+(12.6145mm,-\by)$);
[bar] ($(l4.east)+(12.647mm,\by)$) rectangle ($(l4.east)+(13.066mm,-\by)$);
[bar] ($(l4.east)+(13.169mm,\by)$) rectangle ($(l4.east)+(13.5065mm,-\by)$);
[bar] ($(l4.east)+(13.711mm,\by)$) rectangle ($(l4.east)+(13.9255mm,-\by)$);
[bar] ($(l4.east)+(32.3945mm,\by)$) rectangle ($(l4.east)+(32.4mm,-\by)$);
[bar2] ($(l4.east)+(0,-\by-1*\dy)+(3.6255mm,\dy)$) rectangle ($(l4.east)+(0,-\by-1*\dy)+(4.318mm,-\dy)$);
[bar2] ($(l4.east)+(0,-\by-1*\dy)+(7.621mm,\dy)$) rectangle ($(l4.east)+(0,-\by-1*\dy)+(8.307mm,-\dy)$);
[bar2] ($(l4.east)+(0,-\by-1*\dy)+(11.6245mm,\dy)$) rectangle ($(l4.east)+(0,-\by-1*\dy)+(12.1495mm,-\dy)$);
[bar2] ($(l4.east)+(0,-\by-3*\dy)+(3.124mm,\dy)$) rectangle ($(l4.east)+(0,-\by-3*\dy)+(3.8145mm,-\dy)$);
[bar2] ($(l4.east)+(0,-\by-3*\dy)+(7.123mm,\dy)$) rectangle ($(l4.east)+(0,-\by-3*\dy)+(7.814mm,-\dy)$);
[bar2] ($(l4.east)+(0,-\by-3*\dy)+(11.1195mm,\dy)$) rectangle ($(l4.east)+(0,-\by-3*\dy)+(11.6825mm,-\dy)$);
[bar2] ($(l4.east)+(0,-\by-5*\dy)+(2.6215mm,\dy)$) rectangle ($(l4.east)+(0,-\by-5*\dy)+(3.3105mm,-\dy)$);
[bar2] ($(l4.east)+(0,-\by-5*\dy)+(6.6245mm,\dy)$) rectangle ($(l4.east)+(0,-\by-5*\dy)+(7.319mm,-\dy)$);
[bar2] ($(l4.east)+(0,-\by-5*\dy)+(10.6165mm,\dy)$) rectangle ($(l4.east)+(0,-\by-5*\dy)+(11.2105mm,-\dy)$);
[bar2] ($(l4.east)+(0,-\by-7*\dy)+(2.1185mm,\dy)$) rectangle ($(l4.east)+(0,-\by-7*\dy)+(2.8065mm,-\dy)$);
[bar2] ($(l4.east)+(0,-\by-7*\dy)+(6.126mm,\dy)$) rectangle ($(l4.east)+(0,-\by-7*\dy)+(6.822mm,-\dy)$);
[bar2] ($(l4.east)+(0,-\by-7*\dy)+(10.1155mm,\dy)$) rectangle ($(l4.east)+(0,-\by-7*\dy)+(10.7345mm,-\dy)$);
[bar2] ($(l4.east)+(0,-\by-7*\dy)+(32.3945mm,\dy)$) rectangle ($(l4.east)+(0,-\by-7*\dy)+(32.4mm,-\dy)$);
[bar2] ($(l4.east)+(0,-\by-9*\dy)+(1.615mm,\dy)$) rectangle ($(l4.east)+(0,-\by-9*\dy)+(2.3025mm,-\dy)$);
[bar2] ($(l4.east)+(0,-\by-9*\dy)+(5.627mm,\dy)$) rectangle ($(l4.east)+(0,-\by-9*\dy)+(6.324mm,-\dy)$);
[bar2] ($(l4.east)+(0,-\by-9*\dy)+(9.615mm,\dy)$) rectangle ($(l4.east)+(0,-\by-9*\dy)+(10.2545mm,-\dy)$);
[bar2] ($(l4.east)+(0,-\by-9*\dy)+(13.711mm,\dy)$) rectangle ($(l4.east)+(0,-\by-9*\dy)+(13.9255mm,-\dy)$);
[bar2] ($(l4.east)+(0,-\by-11*\dy)+(1.1115mm,\dy)$) rectangle ($(l4.east)+(0,-\by-11*\dy)+(1.799mm,-\dy)$);
[bar2] ($(l4.east)+(0,-\by-11*\dy)+(5.1275mm,\dy)$) rectangle ($(l4.east)+(0,-\by-11*\dy)+(5.824mm,-\dy)$);
[bar2] ($(l4.east)+(0,-\by-11*\dy)+(9.116mm,\dy)$) rectangle ($(l4.east)+(0,-\by-11*\dy)+(9.772mm,-\dy)$);
[bar2] ($(l4.east)+(0,-\by-11*\dy)+(13.169mm,\dy)$) rectangle ($(l4.east)+(0,-\by-11*\dy)+(13.5065mm,-\dy)$);
[bar2] ($(l4.east)+(0,-\by-13*\dy)+(0.6075mm,\dy)$) rectangle ($(l4.east)+(0,-\by-13*\dy)+(1.296mm,-\dy)$);
[bar2] ($(l4.east)+(0,-\by-13*\dy)+(4.628mm,\dy)$) rectangle ($(l4.east)+(0,-\by-13*\dy)+(5.3235mm,-\dy)$);
[bar2] ($(l4.east)+(0,-\by-13*\dy)+(8.6175mm,\dy)$) rectangle ($(l4.east)+(0,-\by-13*\dy)+(9.286mm,-\dy)$);
[bar2] ($(l4.east)+(0,-\by-13*\dy)+(12.647mm,\dy)$) rectangle ($(l4.east)+(0,-\by-13*\dy)+(13.066mm,-\dy)$);
[bar2] ($(l4.east)+(0,-\by-15*\dy)+(0.1035mm,\dy)$) rectangle ($(l4.east)+(0,-\by-15*\dy)+(0.7935mm,-\dy)$);
[bar2] ($(l4.east)+(0,-\by-15*\dy)+(4.127mm,\dy)$) rectangle ($(l4.east)+(0,-\by-15*\dy)+(4.821mm,-\dy)$);
[bar2] ($(l4.east)+(0,-\by-15*\dy)+(8.1195mm,\dy)$) rectangle ($(l4.east)+(0,-\by-15*\dy)+(8.798mm,-\dy)$);
[bar2] ($(l4.east)+(0,-\by-15*\dy)+(12.1335mm,\dy)$) rectangle ($(l4.east)+(0,-\by-15*\dy)+(12.6145mm,-\dy)$);

[-latex, shorten <= -3mm] ($(l4.south east)+(0,-3mm)$) – ++(32.4mm,0cm) – +(3mm,0) node (label) [below right, inner xsep = 0] $t/h$;
/in 0/0, 5.4/, 10.8/6, 16.2/, 21.6/12, 27/, 32.4/18
($(l4.south east) + (\x mm, 3pt-3mm)$) – +(0, -6pt) node [below] ;

ıin 0,1,...,4

[bg] ($(l\i.east)+(0,2.5*\by)+(-.28mm,0.5mm)$) rectangle ++($(32.4mm,-5*\by-16*\dy) + (2*.28mm, -1mm)$);

[bgbar] ($(l\i.east)+(0,2.5*\by)$) rectangle ++($(32.4mm,-2*\by)$);
[bgbar] ($(l\i.east)+(0,-0.5*\by)$) rectangle ++($(32.4mm,-2*\by)$);

anchor=south east, inner sep = 2pt, ampersand replacement = &, yshift = 4pt,
every node/.style=anchor=center, font=, inner xsep = .3333em
] at (current bounding box.north east -| label.west)
(0,0) – (-1pt,0);
[bar] (0,-1.2mm) rectangle (6mm, 1.2mm); &
Online; &
(0,0) – (-2mm,0);
[bgbar] (0,-1.2mm) rectangle (6mm, 1.2mm); &

[ps located in a satellite in equitorial circular orbit with altitude 500.]
[xscale=1.8, node distance =  3.5mm,
every node/.style=font=,
fill = Crimson,
draw = none,
fill = Grey,
fill = Lavender,
fill = WhiteSmoke,

[labelnode] (l0) $\mathcal C_{1}$;
[labelnode, below=of l0] (l1) $\mathcal C_{2}$;
[labelnode, below=of l1] (l2) $\mathcal C_{3}$;
[labelnode, below=of l2] (l3) $\mathcal C_{4}$;
[labelnode, below=of l3] (l4) $\mathcal C_{5}$;

ıin 0, 1, ..., 4

[anchor = west, font=] (ttı) at ($(l\i.east) + (32.4mm,1.5*\by)$) 1 satellite;
[anchor = west, font=] at ($(tt\i.west) + (0,-3*\by)$) 8 satellites;

[transform canvas=yshift=1.5]

[bar] ($(l0.east)+(0.0mm,\by)$) rectangle ($(l0.east)+(1.280773237643246mm,-\by)$);
[bar] ($(l0.east)+(2.22213219122584mm,\by)$) rectangle ($(l0.east)+(3.741057992823244mm,-\by)$);
[bar] ($(l0.east)+(18.76904734344253mm,\by)$) rectangle ($(l0.east)+(20.786780877416366mm,-\by)$);
[bar] ($(l0.east)+(21.30434078018289mm,\by)$) rectangle ($(l0.east)+(23.850885519157313mm,-\by)$);
[bar] ($(l0.east)+(25.31730524366246mm,\by)$) rectangle ($(l0.east)+(26.168653779372615mm,-\by)$);

[bar] ($(l1.east)+(0.6844542192383367mm,\by)$) rectangle ($(l1.east)+(0.8944785276073639mm,-\by)$);
[bar] ($(l1.east)+(2.773446000694522mm,\by)$) rectangle ($(l1.east)+(5.304989003356867mm,-\by)$);
[bar] ($(l1.east)+(5.642528070378516mm,\by)$) rectangle ($(l1.east)+(7.870285912721382mm,-\by)$);
[bar] ($(l1.east)+(22.928278735964806mm,\by)$) rectangle ($(l1.east)+(24.169672415788867mm,-\by)$);
[bar] ($(l1.east)+(25.339807848130572mm,\by)$) rectangle ($(l1.east)+(27.897603889339045mm,-\by)$);
[bar] ($(l1.east)+(28.63268896863063mm,\by)$) rectangle ($(l1.east)+(30.399143419377243mm,-\by)$);

[bar] ($(l2.east)+(6.8576687116564425mm,\by)$) rectangle ($(l2.east)+(9.01416830651696mm,-\by)$);
[bar] ($(l2.east)+(9.404213450630865mm,\by)$) rectangle ($(l2.east)+(11.947007755527263mm,-\by)$);
[bar] ($(l2.east)+(13.642203958791523mm,\by)$) rectangle ($(l2.east)+(14.159763861558051mm,-\by)$);
[bar] ($(l2.east)+(29.4052783887024mm,\by)$) rectangle ($(l2.east)+(31.90306748466258mm,-\by)$);
[bar] ($(l2.east)+(32.08683875448547mm,\by)$) rectangle ($(l2.east)+(32.4mm,-\by)$);

[bar] ($(l3.east)+(10.998147933788635mm,\by)$) rectangle ($(l3.east)+(12.412061581201527mm,-\by)$);
[bar] ($(l3.east)+(13.44343095265656mm,\by)$) rectangle ($(l3.east)+(16.00122699386503mm,-\by)$);
[bar] ($(l3.east)+(16.863826831809245mm,\by)$) rectangle ($(l3.east)+(18.48026391943512mm,-\by)$);

[bar] ($(l4.east)+(0.0mm,\by)$) rectangle ($(l4.east)+(0.04312999189720994mm,-\by)$);
[bar] ($(l4.east)+(17.49765019099433mm,\by)$) rectangle ($(l4.east)+(20.01794189142262mm,-\by)$);
[bar] ($(l4.east)+(20.299224447273993mm,\by)$) rectangle ($(l4.east)+(22.598240537099205mm,-\by)$);

[transform canvas=yshift=-1.5]

[bar] ($(l0.east)+(0.0mm,\by)$) rectangle ($(l0.east)+(1.280773237643246mm,-\by)$);
[bar] ($(l0.east)+(1.5395531890265055mm,\by)$) rectangle ($(l0.east)+(4.101099664313002mm,-\by)$);
[bar] ($(l0.east)+(4.363630049774277mm,\by)$) rectangle ($(l0.east)+(6.921426090982754mm,-\by)$);
[bar] ($(l0.east)+(7.183956476444038mm,\by)$) rectangle ($(l0.east)+(9.741752517652506mm,-\by)$);
[bar] ($(l0.east)+(10.01178377126982mm,\by)$) rectangle ($(l0.east)+(12.565829378400283mm,-\by)$);
[bar] ($(l0.east)+(12.828359763861558mm,\by)$) rectangle ($(l0.east)+(15.386155805070032mm,-\by)$);
[bar] ($(l0.east)+(15.656187058687348mm,\by)$) rectangle ($(l0.east)+(18.206482231739784mm,-\by)$);
[bar] ($(l0.east)+(18.4765134853571mm,\by)$) rectangle ($(l0.east)+(21.026808658409536mm,-\by)$);
[bar] ($(l0.east)+(21.30434078018289mm,\by)$) rectangle ($(l0.east)+(23.850885519157313mm,-\by)$);
[bar] ($(l0.east)+(24.120916772774624mm,\by)$) rectangle ($(l0.east)+(26.671211945827064mm,-\by)$);
[bar] ($(l0.east)+(26.952494501678434mm,\by)$) rectangle ($(l0.east)+(29.491538372496827mm,-\by)$);
[bar] ($(l0.east)+(29.769070494270178mm,\by)$) rectangle ($(l0.east)+(32.31186479916658mm,-\by)$);
[bar2] ($(l0.east)+(0,-\by-1*\dy)+(0.0mm,\dy)$) rectangle ($(l0.east)+(0,-\by-1*\dy)+(1.280773237643246mm,-\dy)$);
[bar2] ($(l0.east)+(0,-\by-1*\dy)+(2.22213219122584mm,\dy)$) rectangle ($(l0.east)+(0,-\by-1*\dy)+(3.741057992823244mm,-\dy)$);
[bar2] ($(l0.east)+(0,-\by-1*\dy)+(18.76904734344253mm,\dy)$) rectangle ($(l0.east)+(0,-\by-1*\dy)+(20.786780877416366mm,-\dy)$);
[bar2] ($(l0.east)+(0,-\by-1*\dy)+(21.30434078018289mm,\dy)$) rectangle ($(l0.east)+(0,-\by-1*\dy)+(23.850885519157313mm,-\dy)$);
[bar2] ($(l0.east)+(0,-\by-1*\dy)+(25.31730524366246mm,\dy)$) rectangle ($(l0.east)+(0,-\by-1*\dy)+(26.168653779372615mm,-\dy)$);
[bar2] ($(l0.east)+(0,-\by-3*\dy)+(0.0mm,\dy)$) rectangle ($(l0.east)+(0,-\by-3*\dy)+(0.6582011806922082mm,-\dy)$);
[bar2] ($(l0.east)+(0,-\by-3*\dy)+(1.5395531890265055mm,\dy)$) rectangle ($(l0.east)+(0,-\by-3*\dy)+(4.101099664313002mm,-\dy)$);
[bar2] ($(l0.east)+(0,-\by-3*\dy)+(5.106215997221902mm,\dy)$) rectangle ($(l0.east)+(0,-\by-3*\dy)+(6.550133117258942mm,-\dy)$);
[bar2] ($(l0.east)+(0,-\by-3*\dy)+(21.58562333603426mm,\dy)$) rectangle ($(l0.east)+(0,-\by-3*\dy)+(23.66711424933442mm,-\dy)$);
[bar2] ($(l0.east)+(0,-\by-3*\dy)+(24.120916772774624mm,\dy)$) rectangle ($(l0.east)+(0,-\by-3*\dy)+(26.671211945827064mm,-\dy)$);
[bar2] ($(l0.east)+(0,-\by-3*\dy)+(28.227642088204657mm,\dy)$) rectangle ($(l0.east)+(0,-\by-3*\dy)+(28.95147586526218mm,-\dy)$);
[bar2] ($(l0.east)+(0,-\by-5*\dy)+(1.8808426901261701mm,\dy)$) rectangle ($(l0.east)+(0,-\by-5*\dy)+(3.5310336844542167mm,-\dy)$);
[bar2] ($(l0.east)+(0,-\by-5*\dy)+(4.363630049774277mm,\dy)$) rectangle ($(l0.east)+(0,-\by-5*\dy)+(6.921426090982754mm,-\dy)$);
[bar2] ($(l0.east)+(0,-\by-5*\dy)+(7.982798935061935mm,\dy)$) rectangle ($(l0.east)+(0,-\by-5*\dy)+(9.362958675772655mm,-\dy)$);
[bar2] ($(l0.east)+(0,-\by-5*\dy)+(24.402199328626004mm,\dy)$) rectangle ($(l0.east)+(0,-\by-5*\dy)+(26.53244588494039mm,-\dy)$);
[bar2] ($(l0.east)+(0,-\by-5*\dy)+(26.952494501678434mm,\dy)$) rectangle ($(l0.east)+(0,-\by-5*\dy)+(29.491538372496827mm,-\dy)$);
[bar2] ($(l0.east)+(0,-\by-5*\dy)+(31.13047806459081mm,\dy)$) rectangle ($(l0.east)+(0,-\by-5*\dy)+(31.734297951151763mm,-\dy)$);
[bar2] ($(l0.east)+(0,-\by-7*\dy)+(4.693668248639888mm,\dy)$) rectangle ($(l0.east)+(0,-\by-7*\dy)+(6.41511749045028mm,-\dy)$);
[bar2] ($(l0.east)+(0,-\by-7*\dy)+(7.183956476444038mm,\dy)$) rectangle ($(l0.east)+(0,-\by-7*\dy)+(9.741752517652506mm,-\dy)$);
[bar2] ($(l0.east)+(0,-\by-7*\dy)+(10.870633175136012mm,\dy)$) rectangle ($(l0.east)+(0,-\by-7*\dy)+(12.164532932052321mm,-\dy)$);
[bar2] ($(l0.east)+(0,-\by-7*\dy)+(27.218775321217734mm,\dy)$) rectangle ($(l0.east)+(0,-\by-7*\dy)+(29.409028822780414mm,-\dy)$);
[bar2] ($(l0.east)+(0,-\by-7*\dy)+(29.769070494270178mm,\dy)$) rectangle ($(l0.east)+(0,-\by-7*\dy)+(32.31186479916658mm,-\dy)$);
[bar2] ($(l0.east)+(0,-\by-9*\dy)+(7.510244241231624mm,\dy)$) rectangle ($(l0.east)+(0,-\by-9*\dy)+(9.284199560134272mm,-\dy)$);
[bar2] ($(l0.east)+(0,-\by-9*\dy)+(10.01178377126982mm,\dy)$) rectangle ($(l0.east)+(0,-\by-9*\dy)+(12.565829378400283mm,-\dy)$);
[bar2] ($(l0.east)+(0,-\by-9*\dy)+(13.75096654705406mm,\dy)$) rectangle ($(l0.east)+(0,-\by-9*\dy)+(14.973608056488018mm,-\dy)$);
[bar2] ($(l0.east)+(0,-\by-9*\dy)+(30.03535131380947mm,\dy)$) rectangle ($(l0.east)+(0,-\by-9*\dy)+(32.27436045838639mm,-\dy)$);
[bar2] ($(l0.east)+(0,-\by-11*\dy)+(10.31931936566732mm,\dy)$) rectangle ($(l0.east)+(0,-\by-11*\dy)+(12.168283366130344mm,-\dy)$);
[bar2] ($(l0.east)+(0,-\by-11*\dy)+(12.828359763861558mm,\dy)$) rectangle ($(l0.east)+(0,-\by-11*\dy)+(15.386155805070032mm,-\dy)$);
[bar2] ($(l0.east)+(0,-\by-11*\dy)+(16.642551221206165mm,\dy)$) rectangle ($(l0.east)+(0,-\by-11*\dy)+(17.775182312767683mm,-\dy)$);
[bar2] ($(l0.east)+(0,-\by-13*\dy)+(13.135895358259058mm,\dy)$) rectangle ($(l0.east)+(0,-\by-13*\dy)+(15.037365435814328mm,-\dy)$);
[bar2] ($(l0.east)+(0,-\by-13*\dy)+(15.656187058687348mm,\dy)$) rectangle ($(l0.east)+(0,-\by-13*\dy)+(18.206482231739784mm,-\dy)$);
[bar2] ($(l0.east)+(0,-\by-13*\dy)+(19.526635027202225mm,\dy)$) rectangle ($(l0.east)+(0,-\by-13*\dy)+(20.580507003125355mm,-\dy)$);
[bar2] ($(l0.east)+(0,-\by-15*\dy)+(0.0mm,\dy)$) rectangle ($(l0.east)+(0,-\by-15*\dy)+(0.9282324343095271mm,-\dy)$);
[bar2] ($(l0.east)+(0,-\by-15*\dy)+(15.952471350850796mm,\dy)$) rectangle ($(l0.east)+(0,-\by-15*\dy)+(17.91769880773238mm,-\dy)$);
[bar2] ($(l0.east)+(0,-\by-15*\dy)+(18.4765134853571mm,\dy)$) rectangle ($(l0.east)+(0,-\by-15*\dy)+(21.026808658409536mm,-\dy)$);
[bar2] ($(l0.east)+(0,-\by-15*\dy)+(22.425720569510357mm,\dy)$) rectangle ($(l0.east)+(0,-\by-15*\dy)+(23.370829957170972mm,-\dy)$);

[bar] ($(l1.east)+(0.0mm,\by)$) rectangle ($(l1.east)+(2.4846625766871138mm,-\by)$);
[bar] ($(l1.east)+(2.765945132538492mm,\by)$) rectangle ($(l1.east)+(5.304989003356867mm,-\by)$);
[bar] ($(l1.east)+(5.597522861442298mm,\by)$) rectangle ($(l1.east)+(8.136566732260672mm,-\by)$);
[bar] ($(l1.east)+(8.414098854034027mm,\by)$) rectangle ($(l1.east)+(10.956893158930434mm,-\by)$);
[bar] ($(l1.east)+(11.238175714781802mm,\by)$) rectangle ($(l1.east)+(13.784720453756226mm,-\by)$);
[bar] ($(l1.east)+(14.058502141451553mm,\by)$) rectangle ($(l1.east)+(16.605046880425974mm,-\by)$);
[bar] ($(l1.east)+(16.878828568121303mm,\by)$) rectangle ($(l1.east)+(19.43287417525177mm,-\by)$);
[bar] ($(l1.east)+(19.699154994791055mm,\by)$) rectangle ($(l1.east)+(22.25320060192152mm,-\by)$);
[bar] ($(l1.east)+(22.523231855538835mm,\by)$) rectangle ($(l1.east)+(25.077277462669294mm,-\by)$);
[bar] ($(l1.east)+(25.339807848130572mm,\by)$) rectangle ($(l1.east)+(27.897603889339045mm,-\by)$);
[bar] ($(l1.east)+(28.163884708878335mm,\by)$) rectangle ($(l1.east)+(30.72168075008681mm,-\by)$);
[bar] ($(l1.east)+(30.984211135548087mm,\by)$) rectangle ($(l1.east)+(32.4mm,-\by)$);
[bar2] ($(l1.east)+(0,-\by-1*\dy)+(0.6844542192383367mm,\dy)$) rectangle ($(l1.east)+(0,-\by-1*\dy)+(0.8944785276073639mm,-\dy)$);
[bar2] ($(l1.east)+(0,-\by-1*\dy)+(2.773446000694522mm,\dy)$) rectangle ($(l1.east)+(0,-\by-1*\dy)+(5.304989003356867mm,-\dy)$);
[bar2] ($(l1.east)+(0,-\by-1*\dy)+(5.642528070378516mm,\dy)$) rectangle ($(l1.east)+(0,-\by-1*\dy)+(7.870285912721382mm,-\dy)$);
[bar2] ($(l1.east)+(0,-\by-1*\dy)+(22.928278735964806mm,\dy)$) rectangle ($(l1.east)+(0,-\by-1*\dy)+(24.169672415788867mm,-\dy)$);
[bar2] ($(l1.east)+(0,-\by-1*\dy)+(25.339807848130572mm,\dy)$) rectangle ($(l1.east)+(0,-\by-1*\dy)+(27.897603889339045mm,-\dy)$);
[bar2] ($(l1.east)+(0,-\by-1*\dy)+(28.63268896863063mm,\dy)$) rectangle ($(l1.east)+(0,-\by-1*\dy)+(30.399143419377243mm,-\dy)$);
[bar2] ($(l1.east)+(0,-\by-3*\dy)+(3.411019793957634mm,\dy)$) rectangle ($(l1.east)+(0,-\by-3*\dy)+(3.853571015163797mm,-\dy)$);
[bar2] ($(l1.east)+(0,-\by-3*\dy)+(5.597522861442298mm,\dy)$) rectangle ($(l1.east)+(0,-\by-3*\dy)+(8.136566732260672mm,-\dy)$);
[bar2] ($(l1.east)+(0,-\by-3*\dy)+(8.507859705984485mm,\dy)$) rectangle ($(l1.east)+(0,-\by-3*\dy)+(10.686861905313119mm,-\dy)$);
[bar2] ($(l1.east)+(0,-\by-3*\dy)+(25.737353860400507mm,\dy)$) rectangle ($(l1.east)+(0,-\by-3*\dy)+(27.050005787706905mm,-\dy)$);
[bar2] ($(l1.east)+(0,-\by-3*\dy)+(28.163884708878335mm,\dy)$) rectangle ($(l1.east)+(0,-\by-3*\dy)+(30.72168075008681mm,-\dy)$);
[bar2] ($(l1.east)+(0,-\by-3*\dy)+(31.50552147239264mm,\dy)$) rectangle ($(l1.east)+(0,-\by-3*\dy)+(32.4mm,-\dy)$);
[bar2] ($(l1.east)+(0,-\by-5*\dy)+(6.163838407223059mm,\dy)$) rectangle ($(l1.east)+(0,-\by-5*\dy)+(6.793911332330132mm,-\dy)$);
[bar2] ($(l1.east)+(0,-\by-5*\dy)+(8.414098854034027mm,\dy)$) rectangle ($(l1.east)+(0,-\by-5*\dy)+(10.956893158930434mm,-\dy)$);
[bar2] ($(l1.east)+(0,-\by-5*\dy)+(11.384442643824517mm,\dy)$) rectangle ($(l1.east)+(0,-\by-5*\dy)+(13.503437897904845mm,-\dy)$);
[bar2] ($(l1.east)+(0,-\by-5*\dy)+(28.542678550758197mm,\dy)$) rectangle ($(l1.east)+(0,-\by-5*\dy)+(29.937840027780993mm,-\dy)$);
[bar2] ($(l1.east)+(0,-\by-5*\dy)+(30.984211135548087mm,\dy)$) rectangle ($(l1.east)+(0,-\by-5*\dy)+(32.4mm,-\dy)$);
[bar2] ($(l1.east)+(0,-\by-7*\dy)+(8.95041092719065mm,\dy)$) rectangle ($(l1.east)+(0,-\by-7*\dy)+(9.696747308716287mm,-\dy)$);
[bar2] ($(l1.east)+(0,-\by-7*\dy)+(11.238175714781802mm,\dy)$) rectangle ($(l1.east)+(0,-\by-7*\dy)+(13.784720453756226mm,-\dy)$);
[bar2] ($(l1.east)+(0,-\by-7*\dy)+(14.253524713508511mm,\dy)$) rectangle ($(l1.east)+(0,-\by-7*\dy)+(16.323764324574597mm,-\dy)$);
[bar2] ($(l1.east)+(0,-\by-7*\dy)+(31.3555041092719mm,\dy)$) rectangle ($(l1.east)+(0,-\by-7*\dy)+(32.4mm,-\dy)$);
[bar2] ($(l1.east)+(0,-\by-9*\dy)+(11.729482579002207mm,\dy)$) rectangle ($(l1.east)+(0,-\by-9*\dy)+(12.607084153258485mm,-\dy)$);
[bar2] ($(l1.east)+(0,-\by-9*\dy)+(14.058502141451553mm,\dy)$) rectangle ($(l1.east)+(0,-\by-9*\dy)+(16.605046880425974mm,-\dy)$);
[bar2] ($(l1.east)+(0,-\by-9*\dy)+(17.13385808542655mm,\dy)$) rectangle ($(l1.east)+(0,-\by-9*\dy)+(19.13658988308832mm,-\dy)$);
[bar2] ($(l1.east)+(0,-\by-11*\dy)+(14.531056835281865mm,\dy)$) rectangle ($(l1.east)+(0,-\by-11*\dy)+(15.494918393332561mm,-\dy)$);
[bar2] ($(l1.east)+(0,-\by-11*\dy)+(16.878828568121303mm,\dy)$) rectangle ($(l1.east)+(0,-\by-11*\dy)+(19.43287417525177mm,-\dy)$);
[bar2] ($(l1.east)+(0,-\by-11*\dy)+(19.999189721032526mm,\dy)$) rectangle ($(l1.east)+(0,-\by-11*\dy)+(21.953165875680057mm,-\dy)$);
[bar2] ($(l1.east)+(0,-\by-13*\dy)+(0.0mm,\dy)$) rectangle ($(l1.east)+(0,-\by-13*\dy)+(2.233383493459894mm,-\dy)$);
[bar2] ($(l1.east)+(0,-\by-13*\dy)+(17.32513022340549mm,\dy)$) rectangle ($(l1.east)+(0,-\by-13*\dy)+(18.394003935640693mm,-\dy)$);
[bar2] ($(l1.east)+(0,-\by-13*\dy)+(19.699154994791055mm,\dy)$) rectangle ($(l1.east)+(0,-\by-13*\dy)+(22.25320060192152mm,-\dy)$);
[bar2] ($(l1.east)+(0,-\by-13*\dy)+(22.879523092950578mm,\dy)$) rectangle ($(l1.east)+(0,-\by-13*\dy)+(24.76974186827179mm,-\dy)$);
[bar2] ($(l1.east)+(0,-\by-15*\dy)+(0.0mm,\dy)$) rectangle ($(l1.east)+(0,-\by-15*\dy)+(2.4846625766871138mm,-\dy)$);
[bar2] ($(l1.east)+(0,-\by-15*\dy)+(2.765945132538492mm,\dy)$) rectangle ($(l1.east)+(0,-\by-15*\dy)+(5.053709920129646mm,-\dy)$);
[bar2] ($(l1.east)+(0,-\by-15*\dy)+(20.130454913763163mm,\dy)$) rectangle ($(l1.east)+(0,-\by-15*\dy)+(21.278087741636767mm,-\dy)$);
[bar2] ($(l1.east)+(0,-\by-15*\dy)+(22.523231855538835mm,\dy)$) rectangle ($(l1.east)+(0,-\by-15*\dy)+(25.077277462669294mm,-\dy)$);
[bar2] ($(l1.east)+(0,-\by-15*\dy)+(25.752355596712587mm,\dy)$) rectangle ($(l1.east)+(0,-\by-15*\dy)+(27.58631786086352mm,-\dy)$);

[bar] ($(l2.east)+(0.0mm,\by)$) rectangle ($(l2.east)+(0.6619516147702279mm,-\by)$);
[bar] ($(l2.east)+(0.9357333024655616mm,\by)$) rectangle ($(l2.east)+(3.4860284755179993mm,-\by)$);
[bar] ($(l2.east)+(3.7560597291353135mm,\by)$) rectangle ($(l2.east)+(6.306354902187751mm,-\by)$);
[bar] ($(l2.east)+(6.583887023961104mm,\by)$) rectangle ($(l2.east)+(9.126681328857511mm,-\by)$);
[bar] ($(l2.east)+(9.404213450630865mm,\by)$) rectangle ($(l2.east)+(11.947007755527263mm,-\by)$);
[bar] ($(l2.east)+(12.235791179534672mm,\by)$) rectangle ($(l2.east)+(14.767334182197015mm,-\by)$);
[bar] ($(l2.east)+(15.056117606204424mm,\by)$) rectangle ($(l2.east)+(17.617664081490915mm,-\by)$);
[bar] ($(l2.east)+(17.891445769186255mm,\by)$) rectangle ($(l2.east)+(20.49424701933095mm,-\by)$);
[bar] ($(l2.east)+(20.711772195856007mm,\by)$) rectangle ($(l2.east)+(23.34082648454682mm,-\by)$);
[bar] ($(l2.east)+(23.558351661071878mm,\by)$) rectangle ($(l2.east)+(26.209908554230818mm,-\by)$);
[bar] ($(l2.east)+(26.386178955897673mm,\by)$) rectangle ($(l2.east)+(29.04523671721264mm,-\by)$);
[bar] ($(l2.east)+(29.247760157425628mm,\by)$) rectangle ($(l2.east)+(31.90306748466258mm,-\by)$);
[bar] ($(l2.east)+(32.08683875448547mm,\by)$) rectangle ($(l2.east)+(32.4mm,-\by)$);
[bar2] ($(l2.east)+(0,-\by-1*\dy)+(6.8576687116564425mm,\dy)$) rectangle ($(l2.east)+(0,-\by-1*\dy)+(9.01416830651696mm,-\dy)$);
[bar2] ($(l2.east)+(0,-\by-1*\dy)+(9.404213450630865mm,\dy)$) rectangle ($(l2.east)+(0,-\by-1*\dy)+(11.947007755527263mm,-\dy)$);
[bar2] ($(l2.east)+(0,-\by-1*\dy)+(13.642203958791523mm,\dy)$) rectangle ($(l2.east)+(0,-\by-1*\dy)+(14.159763861558051mm,-\dy)$);
[bar2] ($(l2.east)+(0,-\by-1*\dy)+(29.4052783887024mm,\dy)$) rectangle ($(l2.east)+(0,-\by-1*\dy)+(31.90306748466258mm,-\dy)$);
[bar2] ($(l2.east)+(0,-\by-1*\dy)+(32.08683875448547mm,\dy)$) rectangle ($(l2.east)+(0,-\by-1*\dy)+(32.4mm,-\dy)$);
[bar2] ($(l2.east)+(0,-\by-3*\dy)+(9.67424470424818mm,\dy)$) rectangle ($(l2.east)+(0,-\by-3*\dy)+(11.87949994212293mm,-\dy)$);
[bar2] ($(l2.east)+(0,-\by-3*\dy)+(12.235791179534672mm,\dy)$) rectangle ($(l2.east)+(0,-\by-3*\dy)+(14.767334182197015mm,-\dy)$);
[bar2] ($(l2.east)+(0,-\by-3*\dy)+(16.57504340780183mm,\dy)$) rectangle ($(l2.east)+(0,-\by-3*\dy)+(16.912582474823477mm,-\dy)$);
[bar2] ($(l2.east)+(0,-\by-3*\dy)+(32.22560481537215mm,\dy)$) rectangle ($(l2.east)+(0,-\by-3*\dy)+(32.4mm,-\dy)$);
[bar2] ($(l2.east)+(0,-\by-5*\dy)+(12.490820696839917mm,\dy)$) rectangle ($(l2.east)+(0,-\by-5*\dy)+(14.756082879962962mm,-\dy)$);
[bar2] ($(l2.east)+(0,-\by-5*\dy)+(15.056117606204424mm,\dy)$) rectangle ($(l2.east)+(0,-\by-5*\dy)+(17.58766060886677mm,-\dy)$);
[bar2] ($(l2.east)+(0,-\by-7*\dy)+(0.0mm,\dy)$) rectangle ($(l2.east)+(0,-\by-7*\dy)+(0.22690126172010405mm,-\dy)$);
[bar2] ($(l2.east)+(0,-\by-7*\dy)+(15.311147123509668mm,\dy)$) rectangle ($(l2.east)+(0,-\by-7*\dy)+(17.617664081490915mm,-\dy)$);
[bar2] ($(l2.east)+(0,-\by-7*\dy)+(17.891445769186255mm,\dy)$) rectangle ($(l2.east)+(0,-\by-7*\dy)+(20.40798703553652mm,-\dy)$);
[bar2] ($(l2.east)+(0,-\by-9*\dy)+(0.0mm,\dy)$) rectangle ($(l2.east)+(0,-\by-9*\dy)+(0.6619516147702279mm,-\dy)$);
[bar2] ($(l2.east)+(0,-\by-9*\dy)+(2.019608751012847mm,\dy)$) rectangle ($(l2.east)+(0,-\by-9*\dy)+(3.0209746498437373mm,-\dy)$);
[bar2] ($(l2.east)+(0,-\by-9*\dy)+(18.127723116101397mm,\dy)$) rectangle ($(l2.east)+(0,-\by-9*\dy)+(20.49424701933095mm,-\dy)$);
[bar2] ($(l2.east)+(0,-\by-9*\dy)+(20.711772195856007mm,\dy)$) rectangle ($(l2.east)+(0,-\by-9*\dy)+(23.228313462206273mm,-\dy)$);
[bar2] ($(l2.east)+(0,-\by-11*\dy)+(0.0mm,\dy)$) rectangle ($(l2.east)+(0,-\by-11*\dy)+(0.3881699270748943mm,-\dy)$);
[bar2] ($(l2.east)+(0,-\by-11*\dy)+(0.9357333024655616mm,\dy)$) rectangle ($(l2.east)+(0,-\by-11*\dy)+(3.4860284755179993mm,-\dy)$);
[bar2] ($(l2.east)+(0,-\by-11*\dy)+(4.903692557008915mm,\dy)$) rectangle ($(l2.east)+(0,-\by-11*\dy)+(5.822548906123394mm,-\dy)$);
[bar2] ($(l2.east)+(0,-\by-11*\dy)+(20.948049542771148mm,\dy)$) rectangle ($(l2.east)+(0,-\by-11*\dy)+(23.34082648454682mm,-\dy)$);
[bar2] ($(l2.east)+(0,-\by-11*\dy)+(23.558351661071878mm,\dy)$) rectangle ($(l2.east)+(0,-\by-11*\dy)+(26.048639888876032mm,-\dy)$);
[bar2] ($(l2.east)+(0,-\by-13*\dy)+(1.2207662923949547mm,\dy)$) rectangle ($(l2.east)+(0,-\by-13*\dy)+(3.2685032989929423mm,-\dy)$);
[bar2] ($(l2.east)+(0,-\by-13*\dy)+(3.7560597291353135mm,\dy)$) rectangle ($(l2.east)+(0,-\by-13*\dy)+(6.306354902187751mm,-\dy)$);
[bar2] ($(l2.east)+(0,-\by-13*\dy)+(7.8140294015511005mm,\dy)$) rectangle ($(l2.east)+(0,-\by-13*\dy)+(8.609121426090983mm,-\dy)$);
[bar2] ($(l2.east)+(0,-\by-13*\dy)+(23.764625535362896mm,\dy)$) rectangle ($(l2.east)+(0,-\by-13*\dy)+(26.209908554230818mm,-\dy)$);
[bar2] ($(l2.east)+(0,-\by-13*\dy)+(26.386178955897673mm,\dy)$) rectangle ($(l2.east)+(0,-\by-13*\dy)+(28.86521588146777mm,-\dy)$);
[bar2] ($(l2.east)+(0,-\by-15*\dy)+(4.041092719064706mm,\dy)$) rectangle ($(l2.east)+(0,-\by-15*\dy)+(6.137585368676926mm,-\dy)$);
[bar2] ($(l2.east)+(0,-\by-15*\dy)+(6.583887023961104mm,\dy)$) rectangle ($(l2.east)+(0,-\by-15*\dy)+(9.126681328857511mm,-\dy)$);
[bar2] ($(l2.east)+(0,-\by-15*\dy)+(10.709364509781228mm,\dy)$) rectangle ($(l2.east)+(0,-\by-15*\dy)+(11.399444380136586mm,-\dy)$);
[bar2] ($(l2.east)+(0,-\by-15*\dy)+(26.584951962032648mm,\dy)$) rectangle ($(l2.east)+(0,-\by-15*\dy)+(29.04523671721264mm,-\dy)$);
[bar2] ($(l2.east)+(0,-\by-15*\dy)+(29.247760157425628mm,\dy)$) rectangle ($(l2.east)+(0,-\by-15*\dy)+(31.68554230813752mm,-\dy)$);

[bar] ($(l3.east)+(0.0mm,\by)$) rectangle ($(l3.east)+(1.88459312420419mm,-\by)$);
[bar] ($(l3.east)+(2.1583748118995283mm,\by)$) rectangle ($(l3.east)+(4.71242041902998mm,-\by)$);
[bar] ($(l3.east)+(4.974950804491265mm,\by)$) rectangle ($(l3.east)+(7.532746845699732mm,-\by)$);
[bar] ($(l3.east)+(7.7990276652390325mm,\by)$) rectangle ($(l3.east)+(10.3568237064475mm,-\by)$);
[bar] ($(l3.east)+(10.619354091908782mm,\by)$) rectangle ($(l3.east)+(13.177150133117262mm,-\by)$);
[bar] ($(l3.east)+(13.44343095265656mm,\by)$) rectangle ($(l3.east)+(16.00122699386503mm,-\by)$);
[bar] ($(l3.east)+(16.26375737932631mm,\by)$) rectangle ($(l3.east)+(18.82155342053478mm,-\by)$);
[bar] ($(l3.east)+(19.08783424007408mm,\by)$) rectangle ($(l3.east)+(21.645630281282553mm,-\by)$);
[bar] ($(l3.east)+(21.904410232665825mm,\by)$) rectangle ($(l3.east)+(24.465956707952305mm,-\by)$);
[bar] ($(l3.east)+(24.732237527491606mm,\by)$) rectangle ($(l3.east)+(27.286283134622057mm,-\by)$);
[bar] ($(l3.east)+(27.54881352008335mm,\by)$) rectangle ($(l3.east)+(30.10660956129181mm,-\by)$);
[bar] ($(l3.east)+(30.376640814909134mm,\by)$) rectangle ($(l3.east)+(32.4mm,-\by)$);
[bar2] ($(l3.east)+(0,-\by-1*\dy)+(10.998147933788635mm,\dy)$) rectangle ($(l3.east)+(0,-\by-1*\dy)+(12.412061581201527mm,-\dy)$);
[bar2] ($(l3.east)+(0,-\by-1*\dy)+(13.44343095265656mm,\dy)$) rectangle ($(l3.east)+(0,-\by-1*\dy)+(16.00122699386503mm,-\dy)$);
[bar2] ($(l3.east)+(0,-\by-1*\dy)+(16.863826831809245mm,\dy)$) rectangle ($(l3.east)+(0,-\by-1*\dy)+(18.48026391943512mm,-\dy)$);
[bar2] ($(l3.east)+(0,-\by-3*\dy)+(13.803472624146309mm,\dy)$) rectangle ($(l3.east)+(0,-\by-3*\dy)+(15.29614538719759mm,-\dy)$);
[bar2] ($(l3.east)+(0,-\by-3*\dy)+(16.26375737932631mm,\dy)$) rectangle ($(l3.east)+(0,-\by-3*\dy)+(18.82155342053478mm,-\dy)$);
[bar2] ($(l3.east)+(0,-\by-3*\dy)+(19.747910637805298mm,\dy)$) rectangle ($(l3.east)+(0,-\by-3*\dy)+(21.28933904387082mm,-\dy)$);
[bar2] ($(l3.east)+(0,-\by-5*\dy)+(0.0mm,\dy)$) rectangle ($(l3.east)+(0,-\by-5*\dy)+(1.5920592661187625mm,-\dy)$);
[bar2] ($(l3.east)+(0,-\by-5*\dy)+(16.61629818266003mm,\dy)$) rectangle ($(l3.east)+(0,-\by-5*\dy)+(18.17272832503762mm,-\dy)$);
[bar2] ($(l3.east)+(0,-\by-5*\dy)+(19.08783424007408mm,\dy)$) rectangle ($(l3.east)+(0,-\by-5*\dy)+(21.645630281282553mm,-\dy)$);
[bar2] ($(l3.east)+(0,-\by-5*\dy)+(22.620743141567317mm,\dy)$) rectangle ($(l3.east)+(0,-\by-5*\dy)+(24.102164602384548mm,-\dy)$);
[bar2] ($(l3.east)+(0,-\by-7*\dy)+(0.0mm,\dy)$) rectangle ($(l3.east)+(0,-\by-7*\dy)+(1.88459312420419mm,-\dy)$);
[bar2] ($(l3.east)+(0,-\by-7*\dy)+(2.4846625766871138mm,\dy)$) rectangle ($(l3.east)+(0,-\by-7*\dy)+(4.408635258710504mm,-\dy)$);
[bar2] ($(l3.east)+(0,-\by-7*\dy)+(19.425373307095725mm,\dy)$) rectangle ($(l3.east)+(0,-\by-7*\dy)+(21.056812131033688mm,-\dy)$);
[bar2] ($(l3.east)+(0,-\by-7*\dy)+(21.904410232665825mm,\dy)$) rectangle ($(l3.east)+(0,-\by-7*\dy)+(24.465956707952305mm,-\dy)$);
[bar2] ($(l3.east)+(0,-\by-7*\dy)+(25.508577381641395mm,\dy)$) rectangle ($(l3.east)+(0,-\by-7*\dy)+(26.90748929274222mm,-\dy)$);
[bar2] ($(l3.east)+(0,-\by-9*\dy)+(0.0mm,\dy)$) rectangle ($(l3.east)+(0,-\by-9*\dy)+(0.8719759231392553mm,-\dy)$);
[bar2] ($(l3.east)+(0,-\by-9*\dy)+(2.1583748118995283mm,\dy)$) rectangle ($(l3.east)+(0,-\by-9*\dy)+(4.71242041902998mm,-\dy)$);
[bar2] ($(l3.east)+(0,-\by-9*\dy)+(5.353744646371108mm,\dy)$) rectangle ($(l3.east)+(0,-\by-9*\dy)+(7.225211251302231mm,-\dy)$);
[bar2] ($(l3.east)+(0,-\by-9*\dy)+(22.241949299687466mm,\dy)$) rectangle ($(l3.east)+(0,-\by-9*\dy)+(23.929644634795697mm,-\dy)$);
[bar2] ($(l3.east)+(0,-\by-9*\dy)+(24.732237527491606mm,\dy)$) rectangle ($(l3.east)+(0,-\by-9*\dy)+(27.286283134622057mm,-\dy)$);
[bar2] ($(l3.east)+(0,-\by-9*\dy)+(28.385160319481425mm,\dy)$) rectangle ($(l3.east)+(0,-\by-9*\dy)+(29.716564417177914mm,-\dy)$);
[bar2] ($(l3.east)+(0,-\by-11*\dy)+(2.574672994559559mm,\dy)$) rectangle ($(l3.east)+(0,-\by-11*\dy)+(3.767311031369368mm,-\dy)$);
[bar2] ($(l3.east)+(0,-\by-11*\dy)+(4.974950804491265mm,\dy)$) rectangle ($(l3.east)+(0,-\by-11*\dy)+(7.532746845699732mm,-\dy)$);
[bar2] ($(l3.east)+(0,-\by-11*\dy)+(8.234078018289155mm,\dy)$) rectangle ($(l3.east)+(0,-\by-11*\dy)+(10.038036809815953mm,-\dy)$);
[bar2] ($(l3.east)+(0,-\by-11*\dy)+(25.054774858201185mm,\dy)$) rectangle ($(l3.east)+(0,-\by-11*\dy)+(26.80997800671374mm,-\dy)$);
[bar2] ($(l3.east)+(0,-\by-11*\dy)+(27.54881352008335mm,\dy)$) rectangle ($(l3.east)+(0,-\by-11*\dy)+(30.10660956129181mm,-\dy)$);
[bar2] ($(l3.east)+(0,-\by-11*\dy)+(31.272994559555503mm,\dy)$) rectangle ($(l3.east)+(0,-\by-11*\dy)+(32.4mm,-\dy)$);
[bar2] ($(l3.east)+(0,-\by-13*\dy)+(5.383748118995256mm,\dy)$) rectangle ($(l3.east)+(0,-\by-13*\dy)+(6.643893969209401mm,-\dy)$);
[bar2] ($(l3.east)+(0,-\by-13*\dy)+(7.7990276652390325mm,\dy)$) rectangle ($(l3.east)+(0,-\by-13*\dy)+(10.3568237064475mm,-\dy)$);
[bar2] ($(l3.east)+(0,-\by-13*\dy)+(11.106910522051162mm,\dy)$) rectangle ($(l3.east)+(0,-\by-13*\dy)+(12.850862368329665mm,-\dy)$);
[bar2] ($(l3.east)+(0,-\by-13*\dy)+(27.8676004167149mm,\dy)$) rectangle ($(l3.east)+(0,-\by-13*\dy)+(29.68281051047575mm,-\dy)$);
[bar2] ($(l3.east)+(0,-\by-13*\dy)+(30.376640814909134mm,\dy)$) rectangle ($(l3.east)+(0,-\by-13*\dy)+(32.4mm,-\dy)$);
[bar2] ($(l3.east)+(0,-\by-15*\dy)+(8.185322375274914mm,\dy)$) rectangle ($(l3.east)+(0,-\by-15*\dy)+(9.535478643361504mm,-\dy)$);
[bar2] ($(l3.east)+(0,-\by-15*\dy)+(10.619354091908782mm,\dy)$) rectangle ($(l3.east)+(0,-\by-15*\dy)+(13.177150133117262mm,-\dy)$);
[bar2] ($(l3.east)+(0,-\by-15*\dy)+(13.987243893969202mm,\dy)$) rectangle ($(l3.east)+(0,-\by-15*\dy)+(15.663687926843387mm,-\dy)$);
[bar2] ($(l3.east)+(0,-\by-15*\dy)+(30.68042597522861mm,\dy)$) rectangle ($(l3.east)+(0,-\by-15*\dy)+(32.4mm,-\dy)$);

[bar] ($(l4.east)+(0.0mm,\by)$) rectangle ($(l4.east)+(0.1031369371455014mm,-\by)$);
[bar] ($(l4.east)+(0.34316471813867205mm,\by)$) rectangle ($(l4.east)+(2.953466836439401mm,-\by)$);
[bar] ($(l4.east)+(3.1859937492765376mm,\by)$) rectangle ($(l4.east)+(5.826299340201409mm,-\by)$);
[bar] ($(l4.east)+(6.010070610024304mm,\by)$) rectangle ($(l4.east)+(8.665377937261255mm,-\by)$);
[bar] ($(l4.east)+(8.864150943396227mm,\by)$) rectangle ($(l4.east)+(11.52695913878921mm,-\by)$);
[bar] ($(l4.east)+(11.703229540456073mm,\by)$) rectangle ($(l4.east)+(14.351035999536986mm,-\by)$);
[bar] ($(l4.east)+(14.572311610140066mm,\by)$) rectangle ($(l4.east)+(17.197615464752868mm,-\by)$);
[bar] ($(l4.east)+(17.42264150943396mm,\by)$) rectangle ($(l4.east)+(20.01794189142262mm,-\by)$);
[bar] ($(l4.east)+(20.299224447273993mm,\by)$) rectangle ($(l4.east)+(22.85327005440445mm,-\by)$);
[bar] ($(l4.east)+(23.138303044333835mm,\by)$) rectangle ($(l4.east)+(25.6735964810742mm,-\by)$);
[bar] ($(l4.east)+(25.958629471003587mm,\by)$) rectangle ($(l4.east)+(28.50517420997801mm,-\by)$);
[bar] ($(l4.east)+(28.778955897673338mm,\by)$) rectangle ($(l4.east)+(31.321750202569746mm,-\by)$);
[bar] ($(l4.east)+(31.60303275842111mm,\by)$) rectangle ($(l4.east)+(32.4mm,-\by)$);
[bar2] ($(l4.east)+(0,-\by-1*\dy)+(0.0mm,\dy)$) rectangle ($(l4.east)+(0,-\by-1*\dy)+(0.04312999189720994mm,-\dy)$);
[bar2] ($(l4.east)+(0,-\by-1*\dy)+(17.49765019099433mm,\dy)$) rectangle ($(l4.east)+(0,-\by-1*\dy)+(20.01794189142262mm,-\dy)$);
[bar2] ($(l4.east)+(0,-\by-1*\dy)+(20.299224447273993mm,\dy)$) rectangle ($(l4.east)+(0,-\by-1*\dy)+(22.598240537099205mm,-\dy)$);
[bar2] ($(l4.east)+(0,-\by-3*\dy)+(0.0mm,\dy)$) rectangle ($(l4.east)+(0,-\by-3*\dy)+(0.1031369371455014mm,-\dy)$);
[bar2] ($(l4.east)+(0,-\by-3*\dy)+(0.34316471813867205mm,\dy)$) rectangle ($(l4.east)+(0,-\by-3*\dy)+(2.8634564185669666mm,-\dy)$);
[bar2] ($(l4.east)+(0,-\by-3*\dy)+(20.317976617664083mm,\dy)$) rectangle ($(l4.east)+(0,-\by-3*\dy)+(22.85327005440445mm,-\dy)$);
[bar2] ($(l4.east)+(0,-\by-3*\dy)+(23.160805648801944mm,\dy)$) rectangle ($(l4.east)+(0,-\by-3*\dy)+(25.414816529690935mm,-\dy)$);
[bar2] ($(l4.east)+(0,-\by-5*\dy)+(0.5831924991318428mm,\dy)$) rectangle ($(l4.east)+(0,-\by-5*\dy)+(2.953466836439401mm,-\dy)$);
[bar2] ($(l4.east)+(0,-\by-5*\dy)+(3.1859937492765376mm,\dy)$) rectangle ($(l4.east)+(0,-\by-5*\dy)+(5.683782845236718mm,-\dy)$);
[bar2] ($(l4.east)+(0,-\by-5*\dy)+(20.97430258131728mm,\dy)$) rectangle ($(l4.east)+(0,-\by-5*\dy)+(21.360597291353162mm,-\dy)$);
[bar2] ($(l4.east)+(0,-\by-5*\dy)+(23.138303044333835mm,\dy)$) rectangle ($(l4.east)+(0,-\by-5*\dy)+(25.6735964810742mm,-\dy)$);
[bar2] ($(l4.east)+(0,-\by-5*\dy)+(26.037388586641967mm,\dy)$) rectangle ($(l4.east)+(0,-\by-5*\dy)+(28.231392522282672mm,-\dy)$);
[bar2] ($(l4.east)+(0,-\by-7*\dy)+(3.403518925801604mm,\dy)$) rectangle ($(l4.east)+(0,-\by-7*\dy)+(5.826299340201409mm,-\dy)$);
[bar2] ($(l4.east)+(0,-\by-7*\dy)+(6.010070610024304mm,\dy)$) rectangle ($(l4.east)+(0,-\by-7*\dy)+(8.504109271906469mm,-\dy)$);
[bar2] ($(l4.east)+(0,-\by-7*\dy)+(23.734622062738744mm,\dy)$) rectangle ($(l4.east)+(0,-\by-7*\dy)+(24.28593587220744mm,-\dy)$);
[bar2] ($(l4.east)+(0,-\by-7*\dy)+(25.958629471003587mm,\dy)$) rectangle ($(l4.east)+(0,-\by-7*\dy)+(28.50517420997801mm,-\dy)$);
[bar2] ($(l4.east)+(0,-\by-7*\dy)+(28.902720222247947mm,\dy)$) rectangle ($(l4.east)+(0,-\by-7*\dy)+(31.051718948952423mm,-\dy)$);
[bar2] ($(l4.east)+(0,-\by-9*\dy)+(6.220094918393332mm,\dy)$) rectangle ($(l4.east)+(0,-\by-9*\dy)+(8.665377937261255mm,-\dy)$);
[bar2] ($(l4.east)+(0,-\by-9*\dy)+(8.864150943396227mm,\dy)$) rectangle ($(l4.east)+(0,-\by-9*\dy)+(11.320685264498206mm,-\dy)$);
[bar2] ($(l4.east)+(0,-\by-9*\dy)+(26.50244241231624mm,\dy)$) rectangle ($(l4.east)+(0,-\by-9*\dy)+(27.215024887139705mm,-\dy)$);
[bar2] ($(l4.east)+(0,-\by-9*\dy)+(28.778955897673338mm,\dy)$) rectangle ($(l4.east)+(0,-\by-9*\dy)+(31.321750202569746mm,-\dy)$);
[bar2] ($(l4.east)+(0,-\by-9*\dy)+(31.783053594165995mm,\dy)$) rectangle ($(l4.east)+(0,-\by-9*\dy)+(32.4mm,-\dy)$);
[bar2] ($(l4.east)+(0,-\by-11*\dy)+(9.040421345063082mm,\dy)$) rectangle ($(l4.east)+(0,-\by-11*\dy)+(11.52695913878921mm,-\dy)$);
[bar2] ($(l4.east)+(0,-\by-11*\dy)+(11.703229540456073mm,\dy)$) rectangle ($(l4.east)+(0,-\by-11*\dy)+(14.141011691167957mm,-\dy)$);
[bar2] ($(l4.east)+(0,-\by-11*\dy)+(29.292765366361845mm,\dy)$) rectangle ($(l4.east)+(0,-\by-11*\dy)+(30.110359995369837mm,-\dy)$);
[bar2] ($(l4.east)+(0,-\by-11*\dy)+(31.60303275842111mm,\dy)$) rectangle ($(l4.east)+(0,-\by-11*\dy)+(32.4mm,-\dy)$);
[bar2] ($(l4.east)+(0,-\by-13*\dy)+(11.860747771732834mm,\dy)$) rectangle ($(l4.east)+(0,-\by-13*\dy)+(14.351035999536986mm,-\dy)$);
[bar2] ($(l4.east)+(0,-\by-13*\dy)+(14.572311610140066mm,\dy)$) rectangle ($(l4.east)+(0,-\by-13*\dy)+(16.96133811783771mm,-\dy)$);
[bar2] ($(l4.east)+(0,-\by-13*\dy)+(32.07933788632944mm,\dy)$) rectangle ($(l4.east)+(0,-\by-13*\dy)+(32.4mm,-\dy)$);
[bar2] ($(l4.east)+(0,-\by-15*\dy)+(14.681074198402586mm,\dy)$) rectangle ($(l4.east)+(0,-\by-15*\dy)+(17.197615464752868mm,-\dy)$);
[bar2] ($(l4.east)+(0,-\by-15*\dy)+(17.42264150943396mm,\dy)$) rectangle ($(l4.east)+(0,-\by-15*\dy)+(19.777914110429446mm,-\dy)$);

[-latex, shorten <= -3mm] ($(l4.south east)+(0,-3mm)$) – ++(32.4mm,0cm) – +(3mm,0) node (label) [below right, inner xsep = 0] $t/h$;
/in 0/0, 5.4/, 10.8/3, 16.2/, 21.6/6, 27/, 32.4/9
($(l4.south east) + (\x mm, 3pt-3mm)$) – +(0, -6pt) node [below] ;

ıin 0,1,...,4

[bg] ($(l\i.east)+(0,2.5*\by)+(-.28mm,0.5mm)$) rectangle ++($(32.4mm,-5*\by-16*\dy) + (2*.28mm, -1mm)$);

[bgbar] ($(l\i.east)+(0,2.5*\by)$) rectangle ++($(32.4mm,-2*\by)$);
[bgbar] ($(l\i.east)+(0,-0.5*\by)$) rectangle ++($(32.4mm,-2*\by)$);

anchor=south east, inner sep = 2pt, ampersand replacement = &, yshift = 4pt,
every node/.style=anchor=center, font=, inner xsep = .3333em
] at (current bounding box.north east -| label.west)
(0,0) – (-1pt,0);
[bar] (0,-1.2mm) rectangle (6mm, 1.2mm); &
Online; &
(0,0) – (-2mm,0);
[bgbar] (0,-1.2mm) rectangle (6mm, 1.2mm); &

Connectivity towards the ps from within a 60: 40/5/1 Walker delta constellation. That is, a constellation of 40 satellites having 60 inclined circular orbits and altitude 2000. The satellites are distributed evenly among five orbital planes, which are spaced equidistantly around Earth. Clusters $\mathcal C_p$ are defined as either a single satellite per orbital plane or all satellites within an orbital plane. In the second case, a cluster is considered having a connection to the ps if at least one satellite of the cluster can communicate with the ps. Per-satellite connectivity towards the ps is displayed in gray below the cluster connectivity.

Communication for fl involves two primary tasks, parameter vector distribution and collection of gradient updates. A direct approach to implementing these, leveraging isl for multi-hop routing, are conventional dtn techniques for satellite networks, e.g., cgr in combination with the Bundle protocol <cit.>. Then, parameter vector distribution is a multicast message from the ps towards all satellites in $\mathcal K$, while gradient updates are communicated as unicast messages from individual satellites towards the ps. However, the number of these unicast transmissions scales quadratically in the number of satellites per orbital plane. This can be reduced to a linear increase with in-network aggregation.

§.§ Incremental Aggregation

Consider the ps update rule from <ref>, within the global iteration $n$. The ps is primarily interested in the sum of effective gradients instead of individual gradient updates. Hence, the updates from all satellites within an orbital plane $\mathcal K_p$ can be collected at a single satellite $s_p^n \in \mathcal K_p$ for transmission to the ps. Instead of transmitting the individual gradient updates $\{ D_k \bar{\vec g}_k(\vec w_k^n) \}_{k\in\mathcal K_p}$, this satellite sends the linear combination $\sum_{k\in\mathcal K_p} D_k \bar{\vec g}_k(\vec w_k^n)$ to the ps. Following <ref>, the ps then treats the satellites in $\mathcal K_p$ as the client cluster $\mathcal C_p$ and incorporates their joint update.

This approach can be extended to intra-cluster communication. Suppose the sink satellite $s^n_p$ is known to all satellites in $\mathcal K_p$. Then, each satellite can easily determine a shortest-path in-tree, rooted at and oriented towards $s^n_p$, for $\mathcal K_p$ <cit.>. For $K_p$ odd, this tree is unique. For $K_p$ even, two equal length paths exist for the satellite farthest away from $s^n_p$. Denote this satellite $k_{p,i}$ and resolve this ambiguity by choosing the tree where $k_{p,i+1}$ is the parent node of $k_{p,i}$.
We denote this directed graph as the aggregation tree $\mathcal G_p^n = (\mathcal K_p, \mathcal E_p^n)$, with vertex set $\mathcal K_p$ and edge set $\mathcal E_p^n$. Its computation is illustrated in <Ref>.

[grow=right, every node/.style=font=, sat/.style=circle,draw=black, inner sep = 0, minimum width = .7cm, color = black, edge from parent/.style=draw,latex-,color = black,sibling distance=10mm,level distance=13mm, every path/.append style=thick]

[yscale = .8]
ıin 1, 2, ..., 8
[sat] (satı) at (-ı*45-90:1.7cm) $k_{p,\i}$;

[-latex,radius=2.3cm] (75:2.3) arc [start angle=75, delta angle=30] node [midway, yshift=7pt] rotation ;

ı[remember=ıas (initially 2)] in 1, 8, 7, 6
[out=-18,in=198,relative,latex-] (sat) to (satı);

ı[remember=ıas (initially 2)] in 3, 4, 5
[out=-18,in=198,relative,-latex] (satı) to (sat);

[out=-18,in=198,relative,-latex, color = gray] (sat6) to (sat5);

[sat] (ps) [left=of sat2] PS;
[latex-] (ps) – (sat2);

[every node/.append style=sat]
[right=2.5cm of sat6] (root) $k_{p,2}$
child node $k_{p,1}$ child node $k_{p,8}$ child node$k_{p,7}$ child node$k_{p,6}$
child node $k_{p,3}$ child node $k_{p,4}$ child node$k_{p,5}$;

[anchor=west] at ($(root.west)+(0,1.4cm)$) Aggregation tree $\mathcal G_p^n$:;

[shorten <= 5mm, shorten >= 5mm, thick, double distance=1pt, -Implies[], bend left] (sat6) to (root);

Routing tree for incremental aggregation in orbital plane $p$. Satellite $k_{p,2}$ acts as sink node. Satellite $k_{p,6}$ has two shortest-path routes to sink. This is resolved unambiguously by the routing algorithm.

Let $\mathcal N_{\mathcal G_p^n}^-(k) = \{ y \in\mathcal K_p : (y, k) \in \mathcal E_p^n \}$ be the incoming neighborhood of $k$ on $\mathcal G_p^n$.
Based on $\mathcal G_p^n$, each satellite $k\in\mathcal K_p$ knows exactly which gradient updates it needs to forward. After local computation completes, node $k$ waits until all updates from the satellites in $\mathcal N_{\mathcal G_p^n}^-(k)$ are received via isl. This might have already happened during the local computation phase. Then, the outgoing partial aggregate of satellite $k$ is computed as

\begin{equation} \label{eq:partialaggregate}
\vec\gamma^n_k = {D_k} \bar{\vec{g}}_k(\vec{w}_k^{n}) + \sum_{y \in \mathcal N_{\mathcal G_p^n}^-(k)} \vec\gamma^n_y
\end{equation}

and transmitted via isl to the next hop $p \in \mathcal N_{\mathcal G_p^n}^+(k) = \{ y \in\mathcal K_p : (k, y) \in \mathcal E_p^n \}$. If $k$ is the current[Please refer to <ref> for a failure handling procedure that might change the sink node after initial assignment.] sink node, i.e., $|\mathcal N_{\mathcal G_p^n}^+(k)|= 0$, $\vec\gamma^n_k$ is the joint aggregate of client cluster $\mathcal C_g = \mathcal K_p$ and transmitted to the ps once the link becomes available.

§.§ Parameter Vector Distribution

<Ref> treat client clusters as if they were a single node, i.e., the ps expects to receive a single (joint) update per client cluster and transmits the model parameter vector only once per global iteration to each cluster. The previous subsection provides ample reason for the first design choice. Transmitting the parameter vector only once is also sensible for several reasons. First of all, it is what ideally happens if the ps transmits a multicast message towards the nodes in $\mathcal K_p$ using the Bundle protocol. As noted before, using the Bundle protocol's custody transfer (or similar) to safeguard point-to-point transmissions involving the ps is a fundamental assumption in this paper. Second, using multicast messages and multi-hop routing considerably reduces delay and the communication effort for the ps. Finally, this provides a natural leader election mechanism for coordinating the sink node selection.

The ps sends the model parameters $\vec w^n$ in iteration $n$ to a single satellite $k$ per cluster $\mathcal C_p$. Satellite $k$ is then responsible for determining an appropriate sink node $s_p^n$ using the procedure described in <ref>. Subsequently, satellite $k$ propagates its routing decision together with $\vec w^n$ through both isl to its neighbors $\mathcal N(k)$ and starts the local training $\textsc{ClientOpt}(\vec w^n)$.
All other satellites, upon reception of new model parameters $\vec w^n$ via one of the isl, forward the model parameters to their next neighbor that did not receive $\vec w^n$ and start the local training $\textsc{ClientOpt}(\vec w^n)$.
Subsequent receptions of $\vec w^n$ are silently dropped upon reception. This ensures that the propagation of $\vec w^n$ through the orbital plane stops once every satellite received it.

[Synchronous orchestration]
[Asynchronous orchestration]
Process interaction during parameter vector distribution, incremental aggregation, and ps synchronization. Satellites 1 and 14 act as sink nodes, while satellites 5 and 11 receive and distribute the parameter vector from the ps. We can remove this figure if at the end, the page numbers will be more than 30.

§.§ Predictive Routing

The final missing piece to this routing approach is a procedure to determine the sink node $s^n_p$. This decision must be made before the local training procedure completes on any satellite in the client cluster.
From a timing perspective, the ideal sink node completes computing <ref> immediately before its link towards the ps becomes available.
Predicting the future state of a satellite constellation is possible with high accuracy due to the determinism of satellite movement <cit.>. Here, we assume the availability of an orbital propagator with low computational complexity and (relatively) low precision like SGP4 <cit.>. We also assume availability of fairly recent information on the constellation state, e.g., in the form of tle <cit.>, distributed by the satellite operator. The sink node can be determined from the orbital positions of the ps and satellites $\mathcal K_p$ at the time when intra-orbit aggregation completes. This requires a prediction of the time $T_p^n$ to 1) distribute the model parameters; 2) compute the local updates; and 3) deliver these updates to candidate sink nodes. The computation time can be estimated using $t_l(k)$ in <ref>. The time to transmit a vector $\vec v$ via intra-orbit isl between two satellites $k_1$ and $k_2\in\mathcal N(k_1)$ is upper bounded as
$t_c(\vec v, t; k_1, k_2) \le \frac{S(\vec v)}{\rho_{k_1,k_2}} + \frac{\max_t d(t; k_1, k_2)}{c_0}$,
where $c_0$ is the vacuum speed of light, $S(\vec v)$ is the storage size of $\vec v$ and $d(t; k_1, k_2)$ is constant in $t$ for circular orbits. For uncompressed gradients, $S(\vec w^n) = n_d \omega$, where $\omega$ is the storage size of a single element of model parameter, usually 16-bit or 32-bit floating point number.

A precise solution for $T_p^n$ should take into account that satellites start their learning procedure at different times depending on the number of hops the global model parameters need to travel. Even when distribution takes place over shortest-distance paths, the completion time is different for each potential sink node in $\mathcal K_p$. Hence, predictions on the constellation state must be made for up to $K_p$ time instants and the computational complexity for determining the sink node  scales at least linearly in $K_p$.
A considerably simpler approach is to assume distribution takes place over shortest-distance paths and make a worst-case estimate for the aggregation phase. Combined with assuming a symmetric orbital distribution of satellites and equal isl capabilities, i.e., $d_p = \max_t d(t; k_1, k_2)$ and $\rho_p = \rho_{k_1,k_2}$ for all $k_1 \in\mathcal K_p, k_2 \in\mathcal N(k_1)$, we obtain

\begin{equation}
T_{p}^n \le
\left\lceil \frac{K_p}{2} \right\rceil \left( \frac{S(\vec w^n)}{\rho_p} + \frac{d_p}{c_0} \right)
\max_{k\in\mathcal K_p} t_l(k)
\left\lceil \frac{K_p}{2} \right\rceil \left( \frac{\max_{k\in\mathcal K_p}S(\bar{\vec g}_k(\vec w_k^n))}{\rho_p} + \frac{d_p}{c_0} \right).
\end{equation}

Under constant-length gradient compression and equal in-cluster computation times, becomes:

\begin{equation}\label{eq: aggregationtime}
T_{p}^n \le \hat T_p^n =
\left\lceil \frac{K_p}{2} \right\rceil \left(
\frac{S(\vec w^n) + S(\bar{\vec g}_{k_1}(\vec w_{k_1}^n))}{\rho_p}
+ \frac{2 d_p}{c_0}
\right)
\end{equation}

for any $k_1 \in\mathcal K_p$. This bound overestimates the time for communications. However, this part is likely small compared to the computation time. Taking into account the inaccuracies of orbital prediction,[tle data has an initial accuracy of roughly 1km and then decays quickly <cit.>.] local clock deviations, and computational delays due to, e.g., multitasking, interrupts, or priority scheduling, slightly overestimating the time to completion seems reasonable.
The major advantage of using the simple estimate in <ref> is that the constellation state needs only be predicted for a single time instant. Thus, the computational effort remains constant in $K_p$.

Based on the estimate $\hat T_p^n$, the satellite that took custody of $\vec w^n$ computes the positions of the ps and all satellites in its orbital plane at time $t_p^n + \hat T_p^n$, where $t_p^n$ is the expected local time after determining $s_p^n$. It then selects the satellite with the shortest Euclidean distance to the ps as sink node $s_p^n$ and starts the model distribution (cf. <ref>).

§.§ Failure Handling

The most critical routing error occurs if the sink node completes incremental aggregation directly after its communication window to the ps has closed. This could introduce large delays with significant impact on the global fl process. The straightforward mitigation approach is to use conventional dtn multi-hop routing to deliver the cluster update to the ps. However, this is unnecessary if the sink node token is passed once the designated communication window closes. Specifically, upon receiving the model parameters, the sink node $s_p^n = k_{p,i}$ determines the predicted time of completion for incremental aggregation as

\begin{equation} \label{eq:failure:time}
T_c =
t + t_l(s_p^n) +
\left\lceil \frac{K_p}{2} \right\rceil \left(
\frac{S(\bar{\vec g}_{s_p^n}(\vec w_{s_p^n}^n))}{\rho_p}
+ \frac{2 d_p}{c_0},
\right)
\end{equation}

where $t$ is the current (local) time, and the ps communication window such that $T_c \in [t_1, t_2]$. After time $t_1$, the sink node actively monitors the link towards the ps and, upon detecting the
closure of the communication window, it passes the sink node role to its neighbor $k_{p,i+1}$. Then, satellites $k_{p,i}$ and $k_{p,i+1}$ update their aggregation trees and start normal operation in their new role. The new sink takes $t_1$ as the current time, the old sink checks whether it can compute and forward <ref>, while the other satellites in $\mathcal K_p$ do not need to be informed of this change.

§.§ Algorithm

The satellite operation described above is summarized in <ref>. This procedure runs until a stop message is received from the ps, either directly or via isl. The parameter vector distribution is handled in lines <ref>–<ref>. Lines <ref>–<ref> are for failure handling and move the satellite back into the aggregation phase to take over the sink node role. The training procedure is launched concurrently, e.g., in a separate thread, in line <ref>. <Ref> continues immediately with line <ref>, which starts the incremental aggregation phase by computing $\mathcal G_p^n$.

If the satellite is the current sink node, it waits for incoming results and its own computation to finish.
Should the designated ps communication window pass in the meantime, an interrupt is generated according to the procedure described in <ref>. It triggers the handover procedure in lines <ref>–<ref>, which passes the sink node token and restarts the local aggregation phase.
Otherwise, once all results are ready, the sink node computes the final cluster aggregate in line <ref>, waits for the ps to become available, and transmits the results.

All other satellites execute lines <ref>–<ref>. If the local training is complete and the expected incoming partial aggregate is received, the satellite computes <ref> and forwards the result to the next hop in line <ref>. It then returns to line <ref> to wait for a new global iteration or take over as sink node. If the satellite is tasked with taking over as sink node, it updates the relevant parameters in line <ref> and restarts the aggregation phase.

Satellite Operation

[1]
Initialize global iteration $n = 0$, satellite ID $k = k_{p,i}$
and orbital plane ID $p$

Wait for incoming isl or start of PS connectivity window
received $(s_p^{n+1}, \vec w^{n+1})$ from satellite $l$
$n \gets n + 1$
Forward $(s_p^n, \vec w^n)$ to $\mathcal N(k)\setminus \{ l \}$
received sink token from satellite $l$
Set $t_1$ to current time and update $s_p^n \gets k$
Goto line <ref>
connected to ps
Request parameters $\vec w^{n+1}$ and wait for reply
received $\vec w^{n+1}$
Acknowledge reception to ps and set $n \gets n+1$
Compute $t_p^n + \hat T_p^n$ and determine $s_p^n$
cf. <ref>
Transmit $(s_p^n, \vec w_p^n)$ to $\mathcal N(k)$
Goto line <ref>

Execute concurrently $D_k \bar{\vec g_k}(\vec w_k^n) \gets \Call{ClientOpt}{\vec w^{n}}$
Compute aggregation tree $\mathcal G_p^n$
cf. <ref>

$k$ is sink satellite
Initialize handover interrupt
cf. <ref>
[t]=2emWait for  ClientOpt and results from $\mathcal N^-_{\mathcal G_p^n}(k)$
until handover interrupt
handover interrupt

Pass sink token to $k_{p,i+1}$
Update $s_p^n \gets k_{p,i+1}$
Goto line <ref>

Compute $\vec\gamma_k^n$ as in <ref>
Wait for connection to ps
Transmit $\vec\gamma_k^n$ and wait for acknowledgement

Wait for [t].73 ClientOpt and results from $\mathcal N^-_{\mathcal G_p^n}(k)$  or sink token
sink token
Set $t_1$ to current time and update $s_p^n \gets k$
Goto line <ref>
Compute $\vec\gamma_k^n$ as in <ref>
Transmit $\vec\gamma_k^n$ to next hop $p \in \mathcal N^+_{\mathcal G_p^n}(k)$

Goto line <ref>

§.§ Asynchronous Orchestration

The primary reason for asynchronous orchestration is long connectivity gaps due to orbital mechanics.
These outages are considerably reduced by the techniques developed in this section.
As there is no apparent benefit of per-client asynchronous updates over using (synchronous) client clusters, the system performance under asynchronous aggregation is expected to benefit significantly from incremental intra-orbit aggregation. In fact, the proposed fl system can be implemented such that the clients are agnostic to the ps operation.

However, in some scenarios the improved connectivity can result in a large number of updates from a small group of client clusters. This can lead to heavily biased solutions and other convergence issues. One such problematic scenario could be <ref> combined with a short learning time $t_l(k)$.
A simple solution to this issue is to set a maximum update frequency per cluster, i.e., fix a minimum time $T_u$ between updates. In a completely trusted system (as is likely the case in sfl), this can be implemented by
1) modifying line <ref> in <ref> to use $\max\{ \hat T_p^n,\ T_u \}$ instead of $\hat T_p^n$;
2) distributing the time stamp $t_p^n + T_u$ together with the model parameters and designated sink node; and
3) not sending any updates to the ps before $t_p^n + T_u$, unless this would result in missing the planned communication window (modify line <ref> in <ref>).
Alternatively, the ps could simply refuse sending the current global model parameters to a cluster if the update frequency is too high.

§ SPARSIFICATION-BASED GRADIENT COMPRESSION

Synchronizing large-scale ml models requires transmitting massive amounts of data. A widely employed method to reduce the communication cost is to truncate the effective gradients prior to transmission to only contain the elements with largest magnitude, while setting the other elements to zero. This is known as sparsification <cit.>, as the resulting vectors are communicated in sparse vector encoding. With practical sparsification ratios $q$ in the range of 110, the size of a single effective gradient vector can be reduced by approximately 8098.

However, while a single sparsified vector has a deterministic length of $\lfloor n_d q \rfloor$ nonzero elements, the sum of multiple sparse length-$\lfloor n_d q \rfloor$ vectors has nondeterministic length. This leads to variable transmission lengths and, hence, uncertainties in the predictive routing procedure. In this section, we develop an estimator for sparse vectors subject to incremental aggregation based on probabilistic modeling of the weight vectors. Before, we briefly review fl gradient sparsification.

§.§ Gradient Sparsification for FL

Each client transmits only the $\lfloor n_d q \rfloor$ largest magnitude elements from its effective gradient vector $\vec g_k(\vec w_k^n)$. This truncation operation is denoted as $\mathsf{Top}_{q}$. A common method to improve the training performance under gradient sparsification is to track the accumulated sparsification error in a residual vector $\vec\Delta_k^n$. The effect is that small magnitude elements, which would be ignored in every iteration, are aggregated over several iterations and will survive sparsification at some point.

The complete sparsification procedure, for an effective gradient $\vec g_k(\vec w_k^n)$, is
to accumulate the previous sparsification error into the effective gradient as $\vec g_k^\mathrm{acc}(\vec w_k^n) \gets \vec g_k(\vec w_k^n) + \vec\Delta_k^{n-1}$, then compute the sparse gradient for transmission as $\bar{\vec g}_k(\vec w_k^n) \gets \mathsf{Top}_{q}(\vec g_k^\mathrm{acc}(\vec w_k^n))$, and update the sparsification error as $\vec\Delta_k^n \gets \vec g_k^\mathrm{acc}(\vec w_k^n) - \bar{\vec g}_k(\vec w_k^n)$.
Convergence of sgd with this sparsification procedure is established in <cit.>. The CompressGradient procedure in <ref> is implemented as exactly these three steps, with $\bar{\vec g}_k(\vec w_k^n)$ being the return value. Then, UncompressGradient simply converts the sparse vector back to its full-length representation, and the summation in <ref> is implemented as a conventional sparse vector addition <cit.>.

§.§ Predictive Routing for Sparse Incremental Aggregation

The predictive routing procedure in <ref> relies on knowledge of the storage size $S(\bar{\vec g}_k(\vec w_k^n))$. With sparsification applied, the estimates in <ref> remain no longer valid. Indeed, the relevant length is $S(\vec\gamma_k^n)$ which is no longer constant over the aggregation path. To this end, first consider the following lemma.

Consider $L$ iid random vectors $\vec X_1, \dots, \vec X_L$ of dimension $n_d$. Let $\tilde{\vec X}_l = \mathsf{Top}_q(\vec X_l)$ for all $l = 1, \dots, L$. Then, the expected number of nonzero elements in $\vec X_\Sigma = \sum_{l=1}^L \tilde{\vec X}_l$ is $n_d - n_d \left( 1 - \frac{n_a}{n_d} \right)^L$, where $n_a = \lfloor n_d q \rfloor$ is the number of nonzero elements in each summand.

Consider the vector $\vec X_l = (X_{l,1}, \dots, X_{l,n_d})$ and let $A_{l,i}$ be the event that $\vec X_{l,i}$ is zero after the $\mathsf{Top}_q$ operation. The probability that $A_{l,i}$ occurs is $1 - \frac{n_a}{n_d}$ <cit.>.
Further, let $A_{i}$ be the event that element $i$ is zero after $\mathsf{Top}_q$ in all $L$ vectors. Then, due to independence,
$\Pr(A_i) = \Pr\bigg(\bigcap_{l=1}^L A_{l,i}\bigg) = \prod_l \Pr( A_{l,i} ) = \bigg( 1 - \frac{n_a}{n_d} \bigg)^L\!.$
Observe that $A_i$ is the event that the $i$th element of $\vec X_\Sigma$ is zero. Thus, the expected number of zero elements in $\vec X_\Sigma$ is
$\mathds E\left[ \sum_{i=1}^{n_d} I(A_i) \right] = \sum_i \mathds E\left[ I(A_i) \right] = \sum_i \Pr(A_i) = n_d \bigg( 1 - \frac{n_a}{n_d} \bigg)^L\!,$
where $I(\cdot)$ is the indicator function that takes value 1 if $A_i$ occurs and 0 otherwise.

Based on this lemma, we can make a reasonable estimate on the number of transmitted bits during incremental aggregation.

The expected total number of transmitted bits over $H$ hops of incremental aggregation is upper bounded as
$n_d (\omega + \lceil \log_2 n_d \rceil) \left[ H + 1 - \frac{n_d}{n_a} \left[ 1 - \left(1 - \frac{n_a}{n_d} \right)^{H+1} \right] \right]$,
where $n_a = \lfloor n_d q \rfloor$.

Let $P_h = (k_1, k_2, \dots, k_{h+1})$, for $h = 1, 2, \dots, H$, be an increasing sequence of nested paths. Consider incremental aggregation over path $P_H$ starting at $k_1$. Denote by $S(P_h)$ the total number of bits transmitted over path $P_h$. Then, $S(P_1) = S(\vec\gamma_{k_1}^n)$ and $S(P_h) = S(\vec \gamma_h^n) + S(P_{h-1})$ for $h > 1$, where $\vec\gamma_k^n$ is the outgoing aggregate at node $k$ as defined in <ref>. At $k_1$, the outgoing aggregate has storage size $S(\vec\gamma_{k_1}^n) = n_a (\omega + \lceil \log_2 n_d \rceil)$, where  $\lceil \log_2 n_d \rceil$ accounts for the storage space of element indices in the sparse representation <cit.>.

At subsequent nodes $k_h$, $h > 1$, the outgoing aggregate has size $S(\vec\gamma_{k_{h}}^n) = S(D_{k_{h}} \bar{\vec g}_{k_{h}}(\vec w_{k_{h}}^n) + \vec\gamma_{k_{h-1}}^n)$. Modelling $\vec w_k^n$ as an iid random vector and assuming the gradients of the nodes along $P_H$ are independent, we obtain 		$\mathds E[S(\vec\gamma_{k_{h}}^n)] = (\omega + \lceil \log_2 n_d \rceil) \left(n_d - n_d \left( 1 - \frac{n_a}{n_d} \right)^h \right)$ from <ref>.
Further, observe that $S(\vec\gamma_{k_1}^n) = n_d - n_d \left( 1 - \frac{n_a}{n_d} \right)$. Then, by recursion,
$\mathds E[S(P_H)] = \sum_{h = 1}^H \mathds E[S(\vec\gamma_h^n)]= n_d (\omega + \lceil \log_2 n_d \rceil) \left[H - \sum_{h=1}^H\left( 1 - \frac{n_a}{n_d} \right)^h \right]$, and due to the geometric sum identity, $\mathds E[S(P_H)] = n_d (\omega + \lceil \log_2 n_d \rceil) \left[H + 1 - \frac{n_d}{n_a} \left(1 - \left( 1 - \frac{n_a}{n_d} \right)^{H+1}\right) \right]$.

Finally, observe that for dependent gradients the positions of the nonzeros after $\mathsf{Top}_q$ will be correlated. Hence, with the notation from the proof of <ref>, $\Pr(A_{l,i}) \le \Pr(A_{l,i} | A_{l,i-1} \cdots A_{l,1})$. Thus, $\Pr(A_i) \ge \left( 1 - \frac{n_a}{n_d} \right)^L$ and $\mathds E\left[ \sum_i I(A_i) \right] \ge n_d \left( 1 - \frac{n_a}{n_d} \right)^L$.

Leveraging <ref>, we replace $\left\lceil \frac{K_p}{2} \right\rceil S(\bar{\vec g}_{k_1}(\vec w_{k_1}^n)$ in <ref> with

\begin{equation}
n_d (\omega + \lceil \log_2 n_d \rceil) \left[ \left\lceil \frac{K_p}{2} \right\rceil + 1 - \frac{n_d}{n_a} \left[ 1 - \left(1 - \frac{n_a}{n_d} \right)^{\left\lceil \frac{K_p}{2} \right\rceil+1} \right] \right],
\end{equation}

to account for sparsification in the predicted routing procedure. This will overestimate the communication effort as it does not account for the dependence between gradients. However, a tighter bound would require assumptions on a random distribution for elements of $\vec w$ and experimental calibration of correlation between gradients. If this precision is required, the measured data could also be used to directly train a simple ml estimator for the aggregated vector length.

§.§ Fixed-length Transmission

§.§.§ Fixed-length sparsity

To provide a fixed-length gradient vector after sparsification in the presented scenario, compressed sensing (CS) approach can accomplish this. Accordingly, the PS uses approximate message passing (AMP) to reconstruct the received gradients <cit.>. In a CS problem, the aim is to choose the sparsest signal that can reconstruct a signal close to the observed one.

Each satellite employs local error accumulation and derives $\vec{g}_k^{ac}(\vec{w}_k^{n,I})$ as <ref>, which then sparses it and derives $\overline{\vec{g}}_k(\vec{w}_k^{n,I})$, by applying $\mathsf{Top}_{q}$ as <ref>. Each satellite applies the random projection matrix, $\vec{Q}$, on $\overline{\vec{g}}_k(\vec{w}_k^{n,I})$ as

\begin{equation}
\vec{g}_k^{cs}(\vec{w}_k^{n,I}) = \vec{Q} \/ \overline{\vec{g}}_k(\vec{w}_k^{n,I}).
\label{eq: AMP_Q}
\end{equation}

Satellite $k$ transmits $\vec{g}_k^{cs}(\vec{w}_k^{n,I})$ to the nearby satellite. Here, we have $\overline{\vec{g}}_k(\vec{w}_k^{n,I}) \in R^{n_d}$, $\vec{Q} \in {R^{n_s \times n_d}}$ and $\vec{g}^{cs}_k(\vec{w}_k^{n,I}) \in {R^{n_s}}$, where $n_s \leq n_d$. Each satellite $i$ after applying the random projection matrix on its own gradient vector and deriving $
\vec{g}^{cs}_i(\vec{w}_i^{n,I})$, adds it to the received $\vec{g}_k^{cs}(\vec{w}_k^{n,I})$, transmits to the other nearby satellite. In this approach, the length of the resulted vectors of all satellites in orbit $p$ are the same. Finally, the sink satellite transmits $\sum_{k=1}^{K_p} D_k \vec{g}_k^{cs}(\vec{w}_k^{n,I})$ towards the PS. The PS uses AMP approach to derive $\overline{\vec{g}}_p(\vec{w}_p^{n,I}) = \sum_{k=1}^{K_p} D_k \overline{\vec{g}}_k(\vec{w}_k^{n,I})$ as

\begin{equation} \label{AMP-PS}
\begin{aligned}
& \underset{\sum_{k=1}^{K_p} D_k \overline{\vec{g}}_k(\vec{w}_k^{n,I})}{\text{min}}
& & \|\sum_{k=1}^{K_p} D_k \overline{\vec{g}}_k(\vec{w}_k^{n,I})\|_0\\
& \text{subject to}
& & \sum_{k=1}^{K_p}\vec{g}_k^{cs}(\vec{w}_k^{n,I}) =\sum_{k=1}^{K_p} \vec{Q}\overline{\vec{g}}_k(\vec{w}_k^{n,I}),
\end{aligned}
\end{equation}

where $||.||_0$ refers to the 0-norm. The PS derives $\tilde{\vec{g}}_p(\vec{w}_p^{n,I})$ for each orbit $p$ which is a noisy version of $\overline{\vec{g}}_p(\vec{w}_p^{n,I})$. These PS processes determine the PSOp(.) in <ref>. The difference between $\tilde{\vec{g}}_p(\vec{w}_p^{n,I})$ and $\overline{\vec{g}}_p(\vec{w}_p^{n,I})$ relates to the value of $n_s$. In this algorithm, the length of each transmitted vector from orbit $p$ is expressed as $L_{p}^{f} = n_s$

\begin{equation}
S_{f} = n_s K_p s.
\end{equation}

\begin{equation}
L_{p}^{f} = n_s.
\end{equation}

and the size of transmitted data in incremental aggregation will be $S_{{p}}^{f} = K_p n_s s $.

The satellite operations of fixed-length and variable-length sparsification approaches follow the same procedures as <ref> with some differences in $\vec{m}(.)$ and SatPostLearnOpt(.). In variable-length sparsification, $\vec{m}_i(\vec{w}_i^{n,I}) = \vec{h}_i(\vec{w}_i^{n,I}) $ and in fixed-length sparsification, $\vec{m}_i(\vec{w}_i^{n,I})=\vec{g}_i^{cs}(\vec{w}_i^{n,I})$. Moreover, the SatPostLearnOpt(.) for these two sparsification-based algorithm is defined as <ref>. Here, for variable-length sparsification approach, SatSparOp(.) and SatSparRevOp(.) in <ref> derives $\vec{h}_{i}(\vec{w}_{i}^{n,I})$ and changes into $\vec{g}_{i}(\vec{w}_{i}^{n,I})$ as defined in <ref>, respectively. For the fixed-length sparsification, these two functions just return the input.

SatPostLearnOp(.) for fixed-length sparsification
[1]
Apply <ref> and <ref> on $\vec{g}_i(\vec{w}_i^{n,I})$ and derive $\overline{\vec{g}}_k(\vec{w}_k^{n,I})$
Apply <ref> on $\overline{\vec{g}}_k(\vec{w}_k^{n,I})$ and derive $\vec{g}_k^{cs}(\vec{w}_k^{n,I})$
$\vec{m}_k(\vec{w}_{k}^{n,I}) = \vec{g}_k^{cs}(\vec{w}_k^{n,I})$

§ PERFORMANCE EVALUATION

We evaluate the performance of the proposed system design for four representative scenarios. The worker satellites are organized either in a 60: 40/5/1 Walker Delta or a 85: 40/5/1 Walker star constellation, both at an altitude of 2000. The notation $i\!:\!t/p/f$ indicates a constellation with $p$ evenly spaced circular orbital planes at inclination $i$, each having $t/p$ equidistant satellites. The phasing parameter $f$ defines the relative shift in raan between adjacent orbital planes and amounts to 9 in this particular setup <cit.>. Subsequently, we identify these constellations as and , respectively.
These constellations are combined with a ps located either in a terrestrial gs located in Bremen, Germany, or in a leo satellite orbiting at an altitude of 500 in the equatorial plane.

Communication links are modelled as complex Gaussian channels with fspl. Then, the maximum achievable rate between nods $k$ and $i$ using a bandwidth $B$ is $\rho(k,i) = B \log_2 \left(1+\mathrm{SNR}(k,i)\right)$. The
$\mathrm {SNR}(k,i) = \frac{P_t G_{k}(i) G_{i}(k) }{N_0  L(k,i)}$ is defined by the transmit power $P_t$, the noise spectral density $N_0 = k_B T B$ at receiver temperature $T$, and average antenna gains $G_j(l)$ at node $j$ towards node $l$, with $k_B$ being the Boltzman constant. The fspl is $L(k,i) = \left(4\pi f_c d(k, i) / c_0\right)^2$, where $f_c$ is the carrier frequency and $d(k, i)$ the distance between nodes $k$ and $i$ <cit.>. We assume fixed rate links operating at the minimum rate supported by the link. This is equivalent to selecting $d(k, i)$ as the maximum communication distance $d_\mathrm{Th}(k, i)$ between these nodes. Following <cit.>, we set  $f_c = \SI{20}{\giga\Hz}$, $B = \SI{500}{\mega\Hz}$, $P_t = \SI{40}{\dBm}$, $T = \SI{354}{\kelvin}$, and the antenna gains to 32.13.

Numerical ml performance is evaluated based on the two most widely used benchmarks. The first is a conventional $\num{7850}$-parameter logistic regression model trained on the MNIST dataset, $28 \times 28$ pixel greyscale images of handwritten digits ranging from 0 to 9 <cit.>.
The other is a deep CNN with 122570 parameters from <cit.>, trained on the CIFAR-10 dataset <cit.>, which includes 10 classes with $32 \times 32$ RGB images. The data samples are either evenly distributed at random among the satellites, which is the iid setting, or in a non-iid fashion using a Dirichlet distribution with parameter 0.5 <cit.>. We use a batch size of ten, run five local epochs, and take the learning rate as 0.1. A computation time $t_l$ of 60 and 480 is assumed for MNIST and CIFAR-10, respectively. The simulation is build upon the FedML framework <cit.>.

§.§ Synchronous and Asynchronous Orchestration

We start by evaluating the benefits of isl for synchronous orchestration as detailed in <ref>. Without employing isl, this is the vanilla fl approach as first proposed in <cit.>.