## 3 Real-Time Problem Description  
In [12], a real-time system is defined as one in which at least one task should produce correct results before a certain instant named deadline. In [35], several scheduling policies were analysed based on task parameters, such as the priority, period, computation time and deadlines, and sufficient conditions were stated for the different policies. The analysis was done first for the case of multiple tasks running on a monoprocessor system. In [36], it was proven that the scheduling of messages in local area networks with a unique link was an isomorphous problem. Based on these previous results, in this paper, the notation is extended to analyse the flow scheduling in data centre networks. A flow is a stream of data that is produced by a server and consumed by another one. There are different kinds of flows, such as multimedia ones, data files, cryptographic procedures and web search contents. Each flow \(f=(o_{f},d_{f},t_{f},p_{f})\) has a source server \(o_{f}\), a destination server \(d_{f}\), a size or duration \(t_{f}\) and a period \(p_{f}\). As flows are assumed to be periodic, they can be seen as a stream of activations. For each activation \(k\) of flow \(f\), \(r_{f}^{k}\) is the instant at which it is released or becomes ready for being transmitted, \(r_{f}^{1}=1\) and \(r_{f}^{k}=r_{f}^{k-1}+p_{f}\) for \(k>1\). In addition, each activation has a deadline \(v_{f}\) before which it must be sent. In a similar way, deadlines are also dynamic and are computed as \(v_{f}^{k}=r_{f}^{k}+p_{f}\) The deadline is a requirement, it is determined by the kind of application associated with the flow, and its formal definition is beyond this work as this is a property of the flow as is the size. A path in a DCN is a set of links and switches that communicate two different servers. In the fat-tree topology, all links are full duplex, and each server has several available paths to the rest of the servers in the DCN. However, there is only one link between it and the first level of switches named _edge_, as can be seen in Figure 1[13]. This means that there is a restriction both in flows going out of the server as those arriving to it. Only one flow at a time can be transmitted or received on each server. The real-time analysis is limited to the last link because all other switches have the same amount of inputs as outputs guaranteeing that all the incoming flows have an output port. The restriction in the last link limits the server capacity both for transmission and reception. The utilization factor or bandwidth requirement for each flow \(f\) can be computed as \(u_{f}=\frac{t_{f}}{p_{f}}\). This relation provides the link occupancy or the percentage of time it is used by each flow. Clearly, the link capacity is limited to 1, and if it is overflowed, some flows will not comply with time restrictions. The _last link_ can be analysed as a classical multitask/monoprocessor system as different flows have to be scheduled on a single link satisfying all deadlines. In [35], they proved the necessary conditions for the feasibility of this kind of systems, and it can be extended to this case as stated in Equation (1), where \(F_{i}^{o}\) and \(F_{i}^{d}\) are the sets of flows with origin or destination on server \(i\), respectively. \[\sum_{\forall f\in F_{i}^{o}}u_{f}\leq 1\quad\&\&\quad\sum_{\forall f\in F_{i}^{ d}}u_{f}\leq 1\quad\forall\text{ server }i \tag{1}\]  
However, Equation (1) is not sufficient to guarantee the schedulability of the flows. In fact, servers eventually exchange data with many others. Thus, two servers sending flows to the same destination interfere between them, and it is not sufficient to consider the utilization factor demand on the individual servers. It is for this that the time and path scheduling should be global, because it is impossible to transmit a flow from a server if it cannot be received at the destination.