Arqon: A suite of control applications enabling a reliable quantum network Scarlett Gauthier∗, Thomas R. Beauchamp∗ , Stephanie Wehner April 13, 2026 proposed a centrally controlled quantum network architecture which is designed to provide this service in a way that is compatible with the state of the art operating systems for quantum processing nodes, QNodeOS [34] and its upgrade Qoala [95]. The network architecture in [7] is modular, in the sense that it is defined to consist of a set of core functionalities, which may be implemented in separate control applications that can each be modified or upgraded independently of the others. A control application packages related network functionalities such as admission control and schedule computation, and provides specific algorithms implementing these functionalities. The network architecture is centered around the periodic computation and distribution of network schedules, enabling internal resources and end nodes to receive schedules in advance of the times at which they can be executed. In a proof of principle implementation and evaluation [7], the proportion of satisfied demands decreased substantially as the number of submitted demands increased, exposing a need for improved control applications. More broadly, an outstanding challenge in the design of quantum network architectures is to develop control applications that can deliver reliable service to end nodes. In computer networking, a system or protocol is reliable if it is able to consistently deliver services to their intended recipients without error or significant delay [74]. Adapting this principle to the service of a quantum network, we define the essential features of reliable service:
arXiv:2604.08692v1 [quant-ph] 9 Apr 2026
Abstract A quantum network’s purpose is to enable users to execute applications on end nodes. This requires the network to provide the service of creating entangled links between those nodes. Users of mature networks, such as the internet or the telephone network expect accepted service demands to be met reliably. We first define reliability requirements that extend classical computer network concepts to quantum network service delivery. We then introduce Arqon, a suite of control applications designed to deliver reliable service in centrally controlled quantum networks. We demonstrate through both analytic and numerical evaluation that Arqon satisfies all reliability requirements for accepted demands. These evaluations consider static network topologies. We provide a complete Python implementation and perform complexity analysis showing that admission control scales as O(k 3 ) in the number of incoming demands k and schedule computation scales as O(N 3 ) in the number of accepted demands to schedule N .
I.
Introduction
A quantum network enables users to execute applications that enable new functionalities. These include secure remote computation [3, 18, 23], secure communication which does not rely on computational assumptions [8, 41], fast coordination of decisions between remote parties without the real-time exchange of messages [51, 36, 89, 19, 96], anonymous leader election [88], and improvements in the (R1) demands receive accept/reject responses; precision of metrology [60, 47]. These applications require quantum communication between quantum devices, sup- (R2) accepted demands are satisfied with a tolerably high probability; plementing the classical communication which underpins classical network applications. Entangled links between (R3) accepted demands are satisfied before their deadlines; end nodes, known as end-to-end links, are key resources that can enable arbitrary quantum communication operations. The service that a quantum network must provide (R4) and the amount or frequency of demands from other to end nodes is to create these end-to-end entangled links users does not disrupt service to accepted demands. according to the quality, quantity, and time based requireArqon is a suite of control applications for the centrally ments of the end node applications. controlled quantum network architecture in [7], which is To correctly schedule the quantum communication operdesigned to overcome the challenge of delivering reliable ations needed in local application execution, the operating service to end nodes. Arqon comprises four control apsystems of programmable end nodes may rely on a netplications: A Network Manager, a Demand Manager, a work schedule. This schedule dictates when the nodes can Network Scheduler, and a Schedule Manager. The Netaccess internal resources of the network to attempt endwork Manager is responsible for maintaining an accurate to-end entangled link generation. In [7], Beauchamp et al. overview of the network, including all components and the ∗ These authors contributed equally. entanglement generation capabilities of the components. 1
The Demand Manager is responsible for all processes that explicitly relate to demands, such as registration of new demands, creating accept/reject responses to send to end nodes, and re-formatting demands into an internal representation. The Network Scheduler produces network schedules based on end node demands. In addition to a Compute Schedule process, the Network Scheduler also includes an Admit Tasks process that determines whether demands are accepted for service or rejected. Finally, the Schedule Manager directs the distribution of network schedules to all network components. In this work we make the following contributions:
II.
Related Work
The Arqon suite of control applications is designed to integrate with the centrally controlled quantum network architecture defined in [7]. This architecture is compatible with the network protocol stack proposed by Dahlberg et al. in [30], where the stack is decomposed into layers, each of which exposes a functionality to the layer above and exploits the functionality of the layer below, as in the classical OSI network model [101]. We make use of the terminology of this network stack. The physical layer of the network is responsible for attempting entanglement generation. Above the physical layer is the link layer, which manages link level entanglement generation, transforming it into a robust service. The link layer service was experimentally realized in Pompili et al. in [77], demonstrating it’s viability as a functional layer of a quantum network. Operations such as scheduling entanglement swaps in a repeater chain and aligning entanglement generation with the memory management service of a quantum node are functions of the link layer. The network architecture [7] defines a centrally controlled structure for the network layer, which is responsible for coordinating endto-end entanglement generation. The combination of this architecture with the Arqon suite of control applications constitutes an implementation of the network layer. Experiments on leading quantum network hardware platforms present a major technological challenge: the expected time to generate an entangled link between neighboring nodes at metropolitan distance scales is almost as long as the maximum storage time. In a state-of-the-art demonstration based on trapped ion nodes [67] the average reported time to generate one entangled pair over an effective 10 km link was 450 ms, while the average maximum storage time was 550 ms with a standard deviation of 36 ms. In networks where the maximum storage time of entangled links does not exceed by orders of magnitude the time required to generate such a link, the multiple neighboring entangled links required to construct an endto-end link will rarely co-exist. To overcome this technical challenge, Arqon produces network schedules that simultaneously allocate nodes along end-to-end routes for durations of time calculated based on end-to-end entanglement generation rates. This method of resource allocation is reminiscent of circuit switching in wired telephone networks [33, 87], Frame Relay [14, 98], and Autonomous Transfer Mode (ATM) networks [56, 87, 85]. In wired telephone networks, multiple calls share physical links through time division multiplexing (TDM), where each call receives a guaranteed time slot within a frame that repeats at fixed frequency for the entire call duration [33, 87]. The maximum number of simultaneous calls is determined by the number of time slots per frame on each link along a route. In ATM networks, multiple virtual circuits share physical links through statistical multiplexing of 53-byte cells transmitted on demand rather than on fixed schedules [56, 87]. Users requesting virtual circuits provide traffic contracts specifying bounds on data production: sustained cell rate (average longterm rate), peak cell rate (maximum rate), and maxi-
• We introduce Arqon, the first suite of control applications for a quantum network architecture capable of delivering reliable service to all accepted demands. To make this achievement precise, we propose a set of reliability requirements for service from a quantum network. We deliver a full performance analysis of our Network Scheduler control application, proving that it can meet the proposed requirements. Moreover, we validate in simulation Arqon’s performance for a variety of network topologies and sets of demands. • We provide a Python implementation of Arqon that enables researchers to simulate realistic multi-user quantum networks, investigate performance under diverse traffic patterns, and develop extensions to our control algorithms. In particular, the Arqon simulator allows configuration of a network topology, the entanglement generation capabilities (success rate and fidelity) between end nodes, and sets of end node application requirements. • We prove that the operational complexity of our implementation of the Network Scheduler is O k2R (N + k)2 + R + (N + R)2 + N 3 R , where N is the current number of accepted demands to schedule, k is the number of internal representations of new demands requiring an accept/reject decision, and R is the number of internal resources in the network (network components that are not end nodes). In our evaluations, we observe that the time to produce a network schedule (tcompute ) is always significantly less than the allowed time, known as a scheduling interval (T SI ). That is, tcompute ≪ T SI . The notation used throughout this paper is summarized in Table 4, included in Appendix A. The rest of this paper is organized as follows: In Section II we discuss related work. In Section III we discuss design considerations for Arqon. In Section IV we define each control application in turn. In Section V we state and prove performance results for the abstractly defined control applications. In Section VI we discuss a specific implementation of Arqon in Python. In Section VII we provide an operational complexity analysis of this implementation. In Section VIII we discuss results from numeric simulations. Finally, we conclude in Section IX and discuss our outlook on future research goals. 2
mum burst size (longest burst at peak rate). AdmisIII. Design Considerations sion control evaluates these contracts and, if accepted, calculates effective bandwidth to reserve along the entire Our task is to design a suite of control applications, which route for the virtual circuit’s duration [85]. Frame Relay when integrated into the modular architecture defined uses similar mechanisms to ATM but with variable-length in [7], create a quantum network satisfying all of the reliframes (1 to 8,192 bytes) and a simpler single-service-class ability requirements (R1)-(R4). From these requirements quality of service model with three parameters: a guar- we derive the following core considerations which guide anteed data transfer rate (Committed Information Rate the design of the Arqon suite of control applications. (CIR)), an allowed burst size at the CIR and a maximum amount that a burst may exceed the CIR [14, 98]. III.i. Core Considerations In contrast, Arqon schedules exclusive end-to-end physical access for demand-dependent durations separated by (C1) Algorithms that handle time-sensitive network scheduling must execute within bounded time, requirdemand-dependent minimum separation intervals when ing operational complexity that is polynomial in the routes fully release access. Network-wide schedules are number of demands. pre-computed sequentially for extended scheduling intervals that are long relative to typical access durations. Ar(C2) Service agreements must be created for accepted deqon’s admission control evaluates user demands, with acmands, defining the type and quality of service that cepted demands receiving service agreements guaranteeArqon commits to provide. In complement, rejection ing a minimum scheduling frequency per interval while messages must be sent to rejected demands. respecting minimum separation requirements. (C3) A demand may be accepted by Arqon if and only if acceptance will not disrupt any existing service agreements. Many proposals of quantum network architectures and protocols, including those of [26, 76, 49, 93, 39, 92, 4, 99], have considered the problem of coordinating the gen- (C4) Arqon must support dynamic updates of the network topology by allowing new nodes to register and reeration of end-to-end entangled links, requiring the use moving network components that fail or become unof network resources. Van meter et al. in [92] further responsive. proposed a framework for routing of entanglement across many smaller networks, and identified the types of protoService agreements will be formally defined in Seccols required to do so. A common feature of these archition IV, following necessary preliminaries. tectures and protocols is that they do not aim to provide end nodes with a guaranteed quality of service and they do not develop protocols for preventing arriving requests III.ii. Network Model from disrupting service to existing requests. In contrast, We consider a centrally controlled quantum network where Arqon is designed to provide end nodes with guaranteed user controlled end nodes submit demands encoding apquality of service agreements which derive from end node plication execution requirements [7]. Demands are not for application execution requirements and it incorporates an single entangled pairs, but rather for repeated creation of admission control process that can reject arriving demands packets containing multiple entangled links, with a minito prevent disrupting existing service agreements. mum separation time between packets, until the demand expires. The network can be classified as a generate-whenrequested network, where end-to-end entangled links are In [84] Skrzypczyk et al. defined a quantum network created to serve these demands. This means we do not architecture for meeting quality of service requirements in assume that end-to-end entangled links can be stored bemulti-user quantum networks. Quality of service was de- tween any two scheduled periods of time. This type of fined with respect to classically inspired metrics (through- network is implementable with the technological maturity put and jitter of entangled link generation) and quan- of current devices and those that will exist in the coming tum specific metrics (fidelity of generated entanglement). years. In the following sub-section, we introduce the netThe architecture employs Time-Division Multiple-Access work components that can be used to construct a general (TDMA) [82] scheduling with fixed-duration time slots, purpose quantum network. granting contention-free access to all qubits along a demand’s assigned route for integer numbers of consecutive III.ii.a. Network Components slots. The authors identified the need for an admission control protocol to prevent arriving demands from disrupt- At the physical layer, a general quantum network may coning service to existing demands. However, no admission sist of a heterogeneous mixture of quantum nodes and the control protocol was defined or implemented, leaving the interfaces between them, in an arbitrary topology. Figarchitecture unable to satisfy reliability requirement (R4). ure 1 represents a possible network topology as a graph, In contrast, Arqon defines a concrete admission control where network components are illustrated as colored nodes protocol which rejects demands that cannot be satisfied and edges connecting components indicate logical connecwithout disrupting service to accepted demands. tions. We consider the following network components: 3
Legend Central Controller
End Node Metropolitan Hub
I1 H1
EGI
B.B. Logic J1
B1
J2
Junction (Border) Node
I3 H2
Long Distance Backbone Repeater Node
I2
Control Processor
Figure 1: Example quantum network resource graph G = (V, E) for a quantum network where the resources to be shared are a long distance backbone channel B1 , two junction nodes J1 , J2 , and three entanglement generation interfaces I1 , I2 , I3 grouped into two metropolitan hubs (H1 and H2 ). Edges represent logical connections, that is if (v1 , v2 ) ∈ E, then it is possible to create an optical path between components v1 and v2 , possibly via some optical switch. • End Nodes These devices execute programs realizing part of a quantum network application, operate under independent (local) control, and accept input from users. An end node may be a quantum processing node with some quantum memory capabilities, as in [79, 78, 64, 69, 29, 91, 25, 24], or a device without quantum memory which is capable of preparing/measuring photons, as in [37, 12]. Any end node can also perform classical operations, such as arithmetic operations and classical communication. Resources within the end nodes are managed locally, for example by the operating system QNodeOS [34] or its upgrade Qoala [95], and are therefore not under the direct control of any network controller. The local control includes a quantum network agent, which is a process responsible for communicating with a central network controller. This agent submits demands to the central network controller, retrieves and installs network schedules and processes network status messages.
detection-in-midpoint protocols (e.g., heralded entanglement generation [21, 38]) use Bell-State Analyzers (BSAs) [16, 71, 97]; source-inmidpoint protocols [57] use entangled photon sources; and sender-receiver protocols use only optical channels [13, 31, 73]. Each EGI can only facilitate the generation of entangled links between a single pair of nodes at any one time. – Switches A switch is a reconfigurable interface that routes signals between different paths. Optical switches are compatible with fiber-based or free-space implementations (where light travels through air or vacuum). In both cases, an optical switch enables dynamic, high-speed reconfiguration of signal paths, supporting efficient routing. Switches allow the metropolitan hub to allocate pairs of nodes optical access to EGIs according to the network schedule. • Long-Distance Backbones A long-distance backbone is a repeater chain consisting of a linear sequence of repeater nodes, such as those in [21, 38, 83, 81, 80]. The network treats each backbone as a single component that produces entangled links between its two border nodes [68] at a fixed rate and average fidelity. A long-distance backbone controller configures the repeater chain according to a repeater policy (see e.g. [17, 55, 46]). The repeater nodes and border nodes are automated components that strictly implement a repeater policy without supporting additional control logic.
• Central Controller The purpose of the central controller is to produce network schedules in response to demands from end nodes. To do so, the central controller also maintains information about the overall network topology and the entanglement generation capabilities of each component in the network. The central controller hosts a suite of control applications which implement its various functionalities. • Metropolitan Hubs A metropolitan hub facilitates a scalable method of multi-user network access [42, 43]. A metropolitan hub contains a logical control element which enforces the network schedule by controlling the physical devices used to realize the schedule. These devices are:
• Junction Nodes A junction node is a border node equipped with additional control logic to support network branching. They provide an interface between multiple repeater chains and between repeater chains and a metropolitan hub. They have the physical capabilities to execute remote entanglement generation protocols, store the resulting entangled links, and perform entanglement swaps. The logical controller of a
– Entanglement Generation Interfaces (EGIs) These devices mediate entangled link generation between neighboring nodes via remote entanglement generation protocols [13, 57]. Different protocols require different EGIs: 4
junction node manages local resources (such as quan- ticular, the time required to send a message over the intum memories) to execute the network schedule. ternet varies, and a difference of several ms may occur in the communication times of repeated messages between a fixed sender and receiver. III.ii.b. Independently Programmed End Nodes An additional type of timing consideration is that entanMulti-node quantum network applications are partitioned glement generation involves sequential non-overlapping atinto separate single-node programs that are run concur- tempts, each with a particular sequence of operations, setrently on different end nodes. The central controller is not ting a minimum period and maximum rate for the process. aware of the programs on independent end nodes. Each This also means operations cannot change mid-attempt program contains instructions for local classical and quan- without disrupting entanglement generation. The large tum computations, and programs on separate end nodes differences in timescales between the physical layer and interact with each other only through classical messaging higher layers of the network stack imply that scheduling and entanglement generation [95]. and triggering of actions at the physical layer is not a funcThis hybrid classical-quantum programming model has tion of any higher layer of the network stack, but is the an important implication for resource management: pro- responsibility of dedicated and sophisticated electronics grams can be structured into sub-routines such that quan- that are key components of the physical layer. tum states required by one sub-routine need not persist through following sub-routines. Individual quantum states III.v. Architecture therefore need not be stored for the entire program duraWe state key features of our network architecture [7], as tion. we make frequent reference to these features when defining the Arqon control applications. III.iii. Physical Considerations For simplicity, we assume quantum network applications are executed between two end nodes. However, our archiGeneration of end-to-end entanglement requires impletecture is directly compatible with applications involving menting some intermediary protocols, in particular permultiple end nodes. forming many physical attempts to generate entanglement between neighboring network components. Each of these physical attempts only succeeds probabilistically, resulting in some average rate of successfully generating end-to-end entangled links. Successfully generated entangled links are stored in quantum memories, which are subject to timedependent errors due to environmental interactions [102, 90]. These decoherence processes limit the storage time, characterized by the memory coherence time [66, 75, 100]. To execute a sub-routine of an application program that requires a packet of entangled links, all links must remain sufficiently coherent throughout the duration of the subroutine. Consequently, all links in a packet must be generated within a time window w determined by both the quantum memory coherence times and the sub-routine execution duration. The probability that a batch of attempts to generate end-to-end entangled links succeeds and the packet generation window w are not simply modeling parameters, they are inherited from the physical capabilities of the network components. III.iv.
III.v.a.
Application Sessions
The aim of users of a quantum network is to successfully run applications. To do so, they execute hybrid classicalquantum programs on independent end nodes. As many hybrid programs have probabilistic outcomes, it is often required to execute the same program many times to extract a useful and reliable output. Realizing a single execution of a quantum network application requires each collaborating end node to successfully execute their local program. We refer to each of these individual executions of an application as an application instance. In practice, applications are typically associated with a deadline, before which all application instances must be executed. To capture these requirements, we define an application session. Definition 1 (Application Session). Suppose end nodes N = (node1, node2, ...) wish to execute application App at least N inst times, before time texpiry . Then we write the corresponding application session as S = (session_id, N , APP, N inst , texpiry ), (1)
Timescales
The time required for network elements to complete actions can only be estimated with finite precision. At the physical layer, actions have precisely characterized durations, allowing for accurate synchronization between multiple nodes, with timing precision ranging from tens of picoseconds (ps) to microseconds (µs) to milliseconds (ms), depending on the operations [78, 34]. Precise timing of a sequence of operations is crucial for processes like entanglement generation [11, 54, 69, 64, 25, 24, 65]. In contrast, at higher layers of the network stack, actions have variable durations and latencies, limiting feasible timing precision to µs or ms [59, 86, 20]. In par-
where session_id is a unique identifier for the session. To ensure feasibility, it is necessary that the specified expiry time, texpiry , is longer than any time-scale of the network. To establish a common understanding of how to locally configure programs for executing an application session (1) and ensure appropriate resource allocation, the end nodes in N execute two processes: a network capability update and capability negotiation [7]. In the network capability update, each node independently queries a network capability table obtained from the central controller 5
Demand Registration Admit Tasks Compute Schedule Distribute Schedule Execute Schedule k−3
k−2
k−1 Scheduling Interval
k
k+1
Figure 2: Process sequence resulting in execution of a network schedule in scheduling interval k. The hatched, colorful processes are executed in the indicated scheduling intervals in order to produce and distribute the schedule which will be executed in scheduling interval k. The grey processes highlight the periodic nature of our architecture. to retrieve end-to-end entanglement generation capabiliAs a new addition to the model from [7], we introduce ties for each suitable path, including the average entan- a service error parameter, ϵservice , associated with a ded glement generation rate and the corresponding minimum mand d. This parameter allows precise specification of fidelity of entangled pairs. In capability negotiation, the the reliability requirement (R2) for each demand d, end nodes in N communicate to coordinate their local reP[demand d is satisfied] ≥ (1 − ϵservice ). (4) source requirements for executing application programs, d using the acquired network capabilities as input. In a deployment of Arqon, the service error parameter may be chosen according to service contracts (i.e. conIII.v.b. Application Demands tracts between the network operator and its clients) or Based on their requirements, application sessions on end priority classes associated with the demand. In some imnodes submit demands for packets of entanglement gener- plementations, it may be set by the central controller. ation to the network. A distinct group of end nodes may simultaneously host multiple application sessions, hence III.v.c. Periodic Computation and Distribution the group may be associated with multiple demands at of Schedules once. The central controller must regularly accept demands, as Definition 2 (Demand). Application sessions register well as compute and distribute network schedules. Each demands. These demands have the format schedule is associated with a version identifier and covers an identical execution time known as the scheduling interraw minsep expiry inst d = (p; t ;t ;N ) (2) val (denoted T SI ). Figure 2 is an illustrated overview of where p = (w, s, F ) defines a packet of s pairs to be gen- the process sequence that enables execution of a network erated within time window w, with minimum fidelity F ; schedule for a scheduling interval k. In our network architecture there is a constant schedultminsep is a minimum time separation between attempts to ing offset, in terms of a number of scheduling intervals, expiry generate packets, t is the expiry time of the applibetween the interval at which a demand passes demand inst cation session, N is the number of successes required registration and the time at which the first schedule involvto satisfy the demand. A demand is associated with iming the demand will be executed if accepted. In Figure 2, a plementation specific metadata, denoted Md . The full descheduling offset of two scheduling intervals is illustrated. mand can then be represented as To account for this offset, when demands are registered start is calculated and d = (draw , Md ). (3) their earliest possible start time t added to the internal representation of the demand. The metadata accompanying a demand is implementation specific and should include source and destination III.v.d. Packet Generation Attempts identifiers for the end nodes. Analogously to the metadata which accompanies a data packet in the classical internet, Network schedules allocate packet generation atmetadata can be used to inform control processes, includ- tempts (PGAs) to accepted demands. A PGA always has ing routing. some duration E, success probability ppacket , and reserves In our original formulation [7], the raw demand in- internal resources on an end-to-end route through the cluded a parameter Rpacket specifying the average re- network. PGAs are associated with a success probability quested rate of successful packet generation until the ex- due to the probabilistic nature of generating entangled piry time texpiry . We have removed Rpacket from (2), as the links. It is impossible to guarantee that a packet will be number of instances N inst and expiry time texpiry together generated when any finite execution time is allocated to specify an average rate of packet generation. a PGA. 6
A minimum separation time between successful packet generation, tminsep , is specified as part of a demand. In the PGA framework, this is enforced as a minimum separation time between subsequently scheduled PGAs for the same demand. This minimum separation is included to ensure that there is sufficient time for the local runtime environment on end nodes to execute local operations before the next allocated period of time for generating entangled links begins. Examples of these local operations are additional blocks of quantum operations in the application program, or operations to reset the hardware between subsequent attempts to generate a packet.
The minimum allocation is a number NγSI of PGAs that d must be scheduled for the PGT γd in each scheduling interval between tstart and its expiry time, in order to ensure the demand will be satisfied with at least probability (1 − ϵservice ). d Definition 4 (Minimal allocation). Let γd be a PGT for demand d, let tstart be the start time of the first scheduling interval in which demand d may be scheduled, and let nSI = ⌈(texpiry − tstart )/T SI ⌉. Let NγSI be such that if d d d X ∼ Binomial(NγSI nSI , ppacket ), γd d
(5)
P[X < Ndinst ] < ϵservice . d
(6)
then III.v.e.
Packet Generation Tasks
Packet Generation Tasks (PGTs) are the internal demand representation format in our network architecture [7]. They are persistent tasks requiring the central controller to schedule PGAs to serve an accepted demand until it expires or is terminated. To create a PGT γ from a demand it is necessary to determine a suitable duration Eγ and packet success probability ppacket for the PGAs. These γ key parameters of a PGA must be set based on the endto-end entanglement generation capabilities along a particular path. For this reason, a PGT γ is created for a particular end-to-end entanglement generation path πγ . We formally define PGTs in Section IV.ii.b.
IV.
Let #d (S) be the number of PGAs for demand d scheduled in schedule S. Then we say a demand receives minimal allocation in schedule S if #d (S) >= NγSI . d In the rest of this section we describe each control application in turn, beginning with the Network Manager. IV.i.
Network Manager
The Network Manager is responsible for maintaining an accurate overview of all network components, their relevant capabilities, and current statuses. Its most basic function is to compose and maintain a graph G = (V, E), called the network resource graph. The vertices V are network components, and the logical connections between components are indicated by the set of edges E. The Network Manager sets the duration of a scheduling interval, which is a global parameter that must be communicated to the other control applications. The other core processes of the Network Manager are Node Registration, Path Computation and a Network Capabilities Manager (NCM). The Network Manager provides two interfaces to the central controller, known as the node (NM:N) interface and the network capabilities (NM:NC) interface, and an internal interface to the other control applications, known as the path (NM:P) interface. The node interface is used by nodes (re-)joining the network to register themselves. The network capabilities interface allows end nodes to obtain information about the entanglement generation capabilities of the network. The path interface allows other Arqon control applications to access information about the paths in the network either by requesting a data structure called the path partition, denoted Π, or by requesting sets of paths between specific pairs of nodes.
Arqon Suite of Control Applications
Arqon consists of four control applications: Network Manager, a Demand Manager, a Network Scheduler, and a Schedule Manager. These control applications are hosted by a central controller, such as an implementation of an Software Defined Network (SDN) controller [62, 50, 70, 61]. The central controller manages all communication with other network components. Figure 3 is a systems interaction diagram that provides an overview of the control applications and their shared interfaces. To allow the clearest possible description of the Arqon control applications, we first define the service agreements that Arqon creates when a demand is accepted for service, which is accompanied by delivery of an ACCEPT message to the end node(s) that submitted the demand. Service agreements may only be updated or canceled in the case of network component failure(s) disrupting the compatible end-to-end entanglement generation routes through the network.
IV.i.a. Network Resource Graph Definition 3 (Service Agreement). The service agreement created for an accepted demand is a guarantee from Arqon The network resource graph, G = (V, E) is an undirected graph in which all the schedulable components in the netthat: work are vertices. The set of vertices can be decomposed “In every scheduling interval between tstart and as V = E ⊔ R where E is the set of end nodes and R is the demand being terminated or expiring, at least the set of schedulable internal resources: EGIs (I), junca number of PGAs called a minimal allocation tion nodes (J) and long-distance backbones (B). Each will be scheduled for the PGT accepted to realize long-distance backbone is allocated as a single unit and the demand.” is therefor represented by a single vertex in the network 7
Arqon DM:B
«Component»
Network Scheduler
DM:DS
«Component»
Demand Manager
SM:SD
«Component»
NM:P
DM:D
«Component»
Network Manager
NM:N
Schedule Manager
NM:NC
SM:S Y
X
Z
Central Controller Figure 3: System Component diagram for Arqon. The interfaces CC:II are described in the main text. The interface X allows Arqon to update the status of demands, interface Y allows Arqon to retrieve the current capabilities of network nodes and Z allows Arqon to push network schedules to components. register itself with the central controller. This is handled by the Node Registration process of the Network Manager via the node (NM:N) interface with the central controller. When nodes register with the Network Manager it assigns a unique node ID that Arqon uses in the creation and distribution of network schedules, and it triggers updates to the network resource graph and the network capabilities table maintained by the NCM. A registration response is returned to the node with the assigned node ID.
resource graph. A network resource graph for a dumbbell network connecting two metropolitan areas across a long-distance backbone is illustrated in Figure 1. The edges of the network resource graph G represent the logical connections between components. For example, if a metropolitan hub contains two EGIs which can be accessed by end node e, G has an edge between e and each of these EGIs. In practice, such a setup could be realized with a single physical connection from the end node to an optical switch located at the metropolitan hub. The optical switch could then be configured to open a physical path from the end node to either of the specific EGIs. A path π = (v0 , v1 , ..., vk ) through the network resource graph G is a sequence of vertices vi ∈ V where for each adjacent pair (vi , vi+1 ) there is an edge e ∈ E connecting vi and vi+1 , and no vertex is visited more than once. It is only possible to serve demands for end-to-end entanglement generation if there is at least one path through the internal resources connecting two end nodes. If such a path exists between all pairs of end nodes, the network resource graph is internally connected.
IV.i.c.
Path Computation identifies which paths through the network resource graph are suitable for generating end-to-end entangled links between any two end nodes. It is not a time-critical process and is only triggered by updates to the network resource graph. As end nodes are under local control only, valid end-to-end entanglement generation paths do not traverse end nodes. Definition 6 (Valid entanglement generation paths). Let G be a network resource graph with end nodes E. Let π = (π0 , ..., πk ) be a path in G. Then we say that π is a valid entanglement generation path if:
Definition 5 (Internally Connected). We say that a network resource graph G = (V, E) with end nodes E is internally connected if for all pairs of nodes v, v ′ ∈ V, there exists a path π = (v, π1 , ..., πk−1 , v ′ ) in G such that ∀i, πi ∈ / E.
1. π0 ̸= πk 2. π0 , πk ∈ E
End-to-end paths must not pass through end nodes, because these are under local control only and are not bound to execute network schedules. IV.i.b.
Path Computation
3. ∀i = 1, ..., k − 1; πi ∈ / E. We denote the set of all valid entanglement generation paths by Pvalid .
Node Registration
The number of valid entanglement generation paths When a node joins the network for the first time, or re- through a network with resource graph G is O(2|V| ). For joins the network after a period of inactivity, it needs to large networks, this can quickly grow to a size which is 8
infeasible to efficiently compute. Therefore, implementations of Arqon may benefit from reducing the set of valid entanglement generation paths to a set of allowable paths by imposing additional restrictions on the paths which may be used to realize a demand. The outcome of Path Computation is a data structure called the path partition, Π, which is a disjoint partition of all valid or allowable entanglement generation paths. In Section VI we define a specific path partition, but Arqon is compatible with any disjoint partition of Pvalid . Looking forward, a disjoint path partition is useful in enabling efficient scheduling of network resources, as non-overlapping paths can be simultaneously scheduled to produce entanglement serving different demands without any ill effects. IV.i.d.
Demand Manager «Component» Demand Registration
Metadata checks
D
Create PGTs
D {γ}
Sanity Checks
NM:P
PASS/ FAIL D
{π}
«Component»
{γ}
«Component» Buffer Manager
Intake and Status Manager
DM:DS
DM:B
Network Capabilities Manager
The NCM maintains a network capabilities table containing the end-to-end entanglement generation capabilities of each path π ∈ Π. The network capabilities table has a version identifier that is incremented with each update. The demands issued by end nodes (see (2) and (3)) include a minimum fidelity F , a number of instances N inst , and an expiry time texpiry , all of which are not arbitrary, but should be informed by the entanglement generation capabilities along paths π ∈ Π. To obtain this information, end nodes query the central controller for their entries of the network capabilities table [7]. The metadata that is included with a demand includes the network capability version id, which is used by the Demand Manager to screen demands before registering them. Other Arqon control applications also need to read the entanglement generation capabilities along end-to-end routes, in particular the Demand Manager. For this reason, the path partition Π is updated by the Network Capabilities Manager to specify these capabilities for each path π ∈ Π. In practice, the NCM may establish the end-to-end entanglement generation capabilities in a variety of ways. A direct method would be for the central controller to periodically schedule blocks of time for characterization of end-to-end routes. An implementation may include a method of determining the entanglement generation capabilities of an end-to-end route from the capabilities of every link in the route individually.
X
DM:D
Figure 4: Detailed diagram of the internals of the Demand Manager. The arrows show the process of registering a demand, showing how the demand submission D is passed from metadata checks to Create PGTs. The relevant paths {π} are obtained via the NM:P interface, before the created PGTs {γ} are also passed to the sanity checks. Finally, any PGTs which pass the sanity checks are passed to the buffer manager and an PASS/FAIL message is sent back to the intake and status manager as appropriate. The interface X provided by the central controller is used to update the statuses of demands at the relevant end nodes. DM:B interface allows the Network Scheduler to retrieve a buffer of registered demands and a buffer of demands to terminate, held by the Buffer Manager. Finally, the DM:D interface is an interface to the central controller through which the Demand Manager retrieves arriving demands and termination requests for existing demands. The Demand Manager with all internal components and interfaces is illustrated in Figure 4. IV.ii.a.
Intake and Status Manager
The Intake and Status Manager is the first process which a demand interacts with. For every incoming demand it first assigns a unique demand ID and creates an entry in a ledger of demand statuses, with an initial status flag indicating that the demand is not yet registered. The deIV.ii. Demand Manager mand status flag is updated as it progresses through each The Demand Manager, is responsible for receiving, screen- further processing step. The demand is not removed from ing and registering incoming demands, converting de- the status ledger until it is either rejected, expires, or is mands into PGTs, maintaining an accurate ledger of de- terminated by the end nodes. Each incoming demand is mand statuses, and creating the status messages that the added to a First In First Out (FIFO) queue, where it recentral controller sends to end nodes. These processes are mains until a worker of the Demand Registration process implemented by an Intake and Status Manager, a Demand removes it. An implementation may also specify an alterRegistration process, and a Buffer Manager. The Demand native queuing system for Demand Registration, including Manager provides three interfaces: the DemandStatus a priority based queuing system. The Intake and Status Manager interprets PASS/FAIL (DM:DS) interface, the Buffer (DM:B) interface and the Demand (DM:D) interface. The DM:DS interface is used outcomes received from Demand Registration and by the Network Scheduler to update demand statuses with ACCEPT/REJECT outcomes received from the Network ACCEPT/REJECT outcomes after admission control. The Scheduler through the DM:DS interface. Upon receipt of a 9
FAIL or REJECT outcome it issues a demand rejection message to end nodes, with an error code indicating whether the demand failed in Demand Registration (FAIL) or was rejected by the Network Scheduler (REJECT). Upon receipt of a PASS or ACCEPT outcome, it updates the status of the demand. For an ACCEPT outcome the Intake and Status Manager further creates a demand acceptance message for end nodes, which includes a service agreement. IV.ii.b.
Demand Registration
Demand Registration comprises three phases: a metadata check, the creation of a set of Packet Generation Tasks (PGTs), and implementation specific sanity checks. There are a finite number of parallel instances of the Demand Registration process, known as workers, each of which handles the registration of one demand at a time. Workers return a PASS/FAIL outcome for each demand to the Intake Manager and take the next demand from the demand queue, as long as it is not empty. An implementation may specify any number of workers, including just a single worker. 1. Metadata check: The following assertions must be true for a demand to be valid: (a) The network capability version identifier is of the expected data type and corresponds to the latest version; (b) Both end node id’s correspond to registered nodes and are of the expected data type; (c) There is an allowed/valid path π connecting the source and destination nodes; (d) The message is a well-formatted demand adhering to the format in (2). (e) Each of N inst , F, w, s > 0 and all fields are of the expected data type. (f) The expiry time texpiry is later than tstart , texpiry > tstart . These assertions are necessary to ensure that a demand can be handled in a consistent manner by the network. Additional metadata checks may be specified by an implementation. 2. Create Packet Generation Tasks: A PGT is associated with a particular path from the source to destination end node. To create a PGT γd for a demand d with a path πγd ∈ Π it is necessary to set the duration of the PGAs (Eγd ), to calculate the packet success probability (ppacket ), and to calculate the minimum γd allocation (NγSI ). In Section VI, we specify a particd ular method of setting Eγd and calculating ppacket . γd The minimal allocation (Definition 4) is the key parameter of the service agreement that Arqon creates for each accepted demand. It depends on the service error parameter, ϵservice , which is either specified by d the end nodes as part of the demand, or set by the central controller. 10
Definition 7 (Packet Generation Task). A packet generation task is a tuple γ = (Eγ , NγSI , πγ , tminsep , texpiry , tstart ) γ γ γ
(7)
where Eγ is the execution time of each packet generation attempt (PGA), NγSI is the minimum allocation for γ, πγ ∈ Π is a valid entanglement generation path and tminsep , texpiry are as in the raw demand (2), and γ γ tstart is the first scheduling interval in which a PGA γ for γ could be scheduled, based on the scheduling offset. In general, there may be multiple valid entanglement generation paths between two end nodes. Each of these paths is only suitable to realize the demand if its average rate of end-to-end entanglement generation is high enough so that demanded sd pairs can be generated within a window of time wd with a non-zero probability ppacket > 0. In the Create PGTs phase of γd Demand Registration each demand d is mapped to a set Γd of suitable PGTs, from which at most one particular PGT γ will be accepted by the Network Scheduler. This also means that a routing decision for a demand d is not made until the Admit Tasks process of the Network Scheduler, where a particular γ ∈ Γd may be accepted for scheduling. 3. Implementation specific sanity checks: Once Γd is constructed, then each possible PGT γ ∈ Γd may undergo further sanity checks. If a PGT γ fails a sanity check, then it is removed from Γd . We define one necessary sanity check, to verify that for each proposed PGT γ ∈ Γd Eγ ≤ T SI ,
(8)
meaning that the execution time of a single PGA of the PGT γ must not exceed the scheduling interval. If all PGTs fail the sanity check, then the demand is marked as invalid and a FAIL outcome is returned to the Intake Manager. Otherwise, a PASS outcome is returned to the Intake Manager and Γd is passed to the Buffer Manager to be added to the demand intake buffer, denoted Γ. IV.ii.c.
Buffer Manager
The sets of PGTs Γd which can realize each demand d that passes Demand Registration are needed as an input to the Network Scheduler control application. Between Demand Registration and the Network Scheduler however there is a type of timing boundary, in that the Network Scheduler executes a set of periodic processes once per scheduling interval, whereas Demand Registration occurs based on the queue arrival dynamics of demands and the availability of workers. Due to this mismatch in process timings, the set of PGTs γd for each registered demand d are placed into a task intake buffer Γ, which is maintained by the Buffer Manager.
Algorithm 1: Algorithm for the main process of the Network Scheduler control application. UpdateFillingClasses, AdmitTasks and ComputeNewSchedule are given in Algorithms 4, 5 and 3 respectively.
Network Scheduler «Component» Compute Schedule «Component» Admit Tasks Γ
DM:DS
Φ
«Subprocess» Minimal
Function NetworkScheduler: Input : Set of filling classes Φ Output: List of accepted PGTs A, network schedule S while True do Get Π from the Network Manager ; Get τ, Γ from the Demand Manager; Set Φ, ξ ← UpdateFillingClasses(Φ, τ, Π) ; Set Φ, A ← AdmitTasks(Γ, Φ, ξ); Send (A, Γ \ A) to the Demand Manager; Set S ← ComputeSchedule(Φ) ; Send S to the Schedule Manager; sleep until the start of the next scheduling interval; end end
Φ, S Φ «Subprocess» Bonus
DM:B
τ
NM:P
«Component» Update Filling Classes
Π
Φ S «Subprocess» Distribution
SM:SD
Figure 5: Detailed diagram of the Network Scheduler. Arrows show the movement of the set of filling classes Φ and the network schedule S through the scheduling process. Within the Buffer Manager, Γ is write only. In contrast, the Demand Manager exposes Γ to the Network Scheduler control application via the DM:B interface, but the buffer is exposed with read only access. The structure used to represent what is read from the task intake buffer by the Network Scheduler is referred to as the task intake object and is also denoted Γ for simplicity. After the buffer has been read by the Network Scheduler, the Buffer Manager must implement a flush of the buffer. In an implementation, the Buffer Manager may flush the entire buffer after each read. Alternatively, it may be that the Network Scheduler only reads a maximum number M of sets of PGTs Γi , i ∈ {0, 1, · · · , M − 1} from the buffer in each read. In that case the Buffer Manager may implement a flush of only the top M sets of PGTs after a read. Similarly, it needs to maintain a buffer of requests from end nodes to terminate demands, called the termination buffer τ . As with Γ, this is write-only from the within the Buffer Manager itself, and via the DM:B interface it is exposed in read-only form to the Network Scheduler. Unlike Γ, the Network Scheduler should always read the entire termination buffer. Once this has occurred, the entire buffer is flushed so that it is ready to receive more termination requests in the next scheduling interval. IV.iii.
Network Scheduler
The Network Scheduler is responsible for determining which PGTs to accept and for producing network schedules that uphold service agreements with end nodes. These network schedules must include a minimum allocation of PGAs for each accepted PGT. It includes an Admit Tasks process that examines PGTs γ ∈ Γ in the task intake buffer and determines if they can be accepted without disrupting already accepted PGTs. It also includes a Compute Schedule process that occurs after Admit Tasks and produces these network schedules. This control ap11
plication is time critical, as its processes must start and complete within a single scheduling interval to ensure distribution and execution of a network schedule will not be delayed. Algorithm 1 for NetworkScheduler is an overview of the main loop of the Network Scheduler control application, and Figure 5 illustrates the Network Scheduler with all internal components. In our network model, we assume that each network component can only be scheduled to execute PGAs for a single PGT at any given time, and each PGA is nonpreemptive. Two different PGAs γ1 and γ2 can be scheduled simultaneously as long as πγ1 ∩ πγ2 = ∅. To account for these considerations, Arqon structures network schedules as a set of aligned resource schedules, one per network component. To schedule a PGA for a PGT γ, all resources on the path πγ of the PGT must be simultaneously available for an uninterrupted period of time that is at least as long as the PGA duration Eγ . As illustrated in Figure 6, it is possible for a network schedule to contain gaps of time in which certain resources have no PGAs scheduled, but the subsequently scheduled PGAs can not be started earlier due to the requirement that all resources on the path πγ be simultaneously available. Figure 6 also illustrates that there are situations in which the total amount of available time on a network resource is greater than or equal to a PGA duration, however the available time is non-consecutive and therefore the PGA cannot actually be scheduled. To determine which PGTs can be simultaneously scheduled, Arqon leverages a partition of active PGTs into cells called filling classes that are based on the path partition Π. Active PGTs are those that have been accepted in some scheduling interval and have neither expired nor been terminated. The filling classes are used by both Admit Tasks and Compute Schedule.
J1
γ1
I1
γ1
I2
γ1
γ2
γ3 γ3
γ2
γ5
γ2
I3
γ4
γ3
0
γ6 T SI
Figure 6: Excerpt from a possible network schedule for four components J1 , I1−3 and a set of PGTs γ1−6 . PGAs for a PGT γi are illustrated by gray boxes scheduled simultaneously on every component on their path πγi . PGAs for γ4 and γ6 , illustrated by red boxes, can not be added to the schedule because I1 (for γ4 ) and I3 (for γ6 ) are not available for sufficiently long blocks of uninterrupted time before the end of the scheduling interval, illustrated by the red line labeled T SI . Definition 8 (Filling Classes). Let Π = {Πϕ } be a disjoint partition of a set of paths P and let Z be a set of PGTs such that ∀γ ∈ Z, ∃ϕ s.t. πγ ∈ Πϕ . The set of filling classes Φ ⊂ 2Z × Π has elements ϕ = (Zϕ , Πϕ ),
(9)
where Zϕ = {γ ∈ Z : πγ ∈ Πϕ }. The set of paths P in Definition 8 may be either the set of valid entanglement generation paths Pvalid , or a further restriction to a set of allowed paths Pallowed . Remark IV.1. The set of filling classes Φ are essentially containers ϕ ∈ Φ for active PGTs, based on the cells of the path partition Πϕ ∈ Π. The set of filling classes does not need to be populated by PGTs, which means that Φ can be created based on the path partition Π and an empty set of PGTs Z = ∅. Once created, the set of filling classes may be updated by populating the containers ϕ ∈ Φ with a set of PGTs Z ̸= ∅. To identify which resources are required by at least one path in a filling class we introduce the mapping of associated resources between a set of paths and the set of resources on at least one path in the set.
partition from the Network Manager via the NM:P interface and check for a change to the version id. In case of an update to the path partition, the filling classes are rebuilt. There may be one or more PGTs γ for which the path πγ is no longer in the path partition. In that case, Update Filling Classes must apply a missing path rule. The default missing path rule is to attempt to re-admit the demand as an alternative PGT γ ′ realizing the demand, for which πγ ′ is in the updated path partition. This may result in an update the service agreement for the demand to reflect the minimal allocation of the alternate PGT. If no alternate PGT can be admitted then Update Filling Classes removes the PGT and updates the demand status to removed so that the Demand Manager can notify the end nodes and cancel the service agreement. Update Filling Classes is also responsible for removing terminated or expired PGTs. To check for PGT terminations, the Network Scheduler reads the termination buffer τ from the Demand Manager via the DM:B interface. Every PGT is checked and those for which there is a termination message or the expiry time has been reached are removed from their filling class. The full process Update Filling Classes is described by Algorithm 4, UpdateFillingClasses in Appendix B.
Definition 9 (Associated Resources). Let P be a set of paths and let R be the set of resources which are on some IV.iii.b. Admit Tasks path in P. Let {πx }x ⊂ P. The resources associated with {πx }x are indicated by ξ {πx }x , as defined by the The process Admit Tasks is described in full by Algo-′ rithm 5, AdmitTasks in Appendix B. It tests PGTs γ following mapping: in the task intake buffer Γ to determine whether there is P R ξ:2 →2 (10) sufficient time available to schedule a minimum allocation SI {πx }x 7→ {r ∈ R : ∃π ∈ {πx }x s.t. r ∈ π}. (11) Nγ of PGAs in subsequent scheduling intervals without disrupting service to any active PGTs. Before testing any new PGTs γ ′ ∈ Γ, it calculates the time required to schedIV.iii.a. Update Filling Classes ule a minimum allocation of each active PGT and reduces In every scheduling interval, the first process that the the available time on all resources associated with the Network Scheduler does is Update Filling Classes. This PGTs filling class by this duration. The function Calcuprocess happens first, as both Admit Tasks and Compute lateRequiredTime, defined in Algorithm 2 implements Schedule require the updated set of filling classes as input. this calculation. Recall that PGAs for a PGT γ must be The Network Scheduler carries forward the filling classes scheduled for uninterrupted periods of duration Eγ on all from a scheduling interval to the subsequent one. How- components in πγ . Gaps of time between PGAs of PGTs ever, before proceeding it is necessary to retrieve the path in the same filling class are not treated as available time 12
Algorithm 2: Calculation of an upper bound on the minimum required time to schedule a minimum allocation of PGAs NγSI for every PGT γ ∈ Zϕ in a filling class ϕ. Function CalculateRequiredTime: Input : Filling class ϕ = (Zϕ , Πϕ ) Output: Required time for filling class, R(Zϕ ) SI Order PGTs γ ∈ Zϕ by a set of indices X = {1, · · · , |Zϕ |} such that NxSI ≤ Nx+1 ; Set M ← |Zϕ | ; Set nϕ0 ← N0SI− 1; PM −1 Set cϕ0 ← max max Ey + tminsep , y=0 Ey ; y y∈{0,···M −1}
for x ∈ {1, · · · , M − 1} do SI Set nϕx ← NxSI − Nx−1 ; Set cϕx ← max
max
y∈{x,···M −1}
PM −1 Ey + tminsep , y=x Ey y
;
end Set R(Zϕ ) ←
M −1 P x=0
(nϕx · cϕx + Ex ) ;
return R(Zϕ ) end
by Admit Tasks, because they may not be long enough to allow a PGA to be scheduled. By reducing the available time for all resources associated with a PGTs filling class, rather than just for the resources on the PGTs path, Admit Tasks avoids considering gaps between PGAs as available time. This simplification prioritizes the satisfaction of service agreements, but it may induce an overestimation of the required time and limit the number of accepted PGTs. Incoming PGTs in the task intake buffer are organized into sets Γd ∈ Γ by the demand they realize, with each specific PGT γd′ ∈ Γd corresponding to a different path between the end nodes. For each of these PGTs, Admit Tasks repeats the calculation of CalculateRequiredTime with γd′ included in the filling class it would be in (the filling class ϕ such that πγd′ ∈ Πϕ ). This required time is compared to the duration of the scheduling interval. If it is less than or equal to the scheduling interval the PGT is accepted, the other PGTs in Γd are removed and the demand status is set to accepted. Otherwise, the PGT is rejected and Admit Tasks checks the next PGT γd′′ ∈ Γd , until either one is accepted or no alternatives remain – in which case the demand status is set to rejected. If Admit Tasks accepts a particular PGT to realize a demand, it fixes the path along which the demand will be served. Hence Admit Tasks performs the function of routing. IV.iii.c.
Compute Schedule
The Network Scheduler computes the network schedule for all components of the network, including end nodes. The schedules of network components are aligned such that a PGA for the PGT γ with path πγ is added to the schedule of every component on the path πγ , so that the PGA covers the same span of time in each component schedule. Due to this alignment, it suffices to refer to a single network schedule S, although the schedule is actually a set of individual schedules for each component of the network. 13
The Compute Schedule process is described by the function ComputeSchedule in Algorithm 3. It is a timecritical process that must compute a schedule including a minimal allocation of PGAs (Definition 4) for every accepted PGT once per scheduling interval. This is essential for satisfying the service agreements established with accepted demands (Definition 3). Hence, the computation time must not exceed the scheduling interval. A secondary aim of the Compute Schedule process is to minimize the amount of idle time in which no PGAs are scheduled on internal resources. It is divided into two phases: a minimal allocation phase which is time-critical and must be completed by the end of a scheduling interval, and a subsequent bonus allocation phase which can be cut off at any time without consequences for service agreements. The minimal allocation phase relies on DirectAllocation, Algorithm 6 in Appendix B, which produces a schedule for one filling class at a time. The DirectAllocation algorithm is fundamentally based on a modification of the classical Round Robin scheduling algorithm. A schedule S is constructed by calculating a direct allocation schedule for each filling class ϕ ∈ Φ which includes a minimal allocation of PGAs for every PGT γ ∈ Zϕ , and sequentially inserting the direct allocation schedules into S according to a partial ordering of ϕ ∈ Φ. A partial ordering of the filling classes ϕ ∈ Φ is specified in an implementation and derives from the path partition Π which determines the structure of Φ. The same logic underpins both the DirectAllocation scheduling algorithm and the CalculateRequiredTime function (Algorithm 2) from the Admit Tasks process. CalculateRequiredTime essentially calculates the duration of a schedule that would be produced by the DirectAllocation algorithm, which actually adds PGAs to a network schedule. In this way, Admit Tasks leverages insight into the Compute Schedule process when determining which PGTs to admit. The bonus allocation phase relies Algo-
B J1 J2 PGT ID PGT 0 PGT 1 PGT 2 PGT 3 PGT 4 PGT 5 PGT 6
I1 I2 I3 E1 E2 E3 E4 E5 E6 0
100
200
300
400
500
Time (s)
Figure 7: An example network schedule produced by ComputeSchedule for a simplified version of the dumbbell topology network illustrated in Figure 1, with a six end nodes and seven active PGTs. End nodes E1−2 connect to I1 , E3−4 connect to I2 , and E5−6 connect to I3 . The PGTs are configured as examples, with different values for their minimal allocations, minimum separations between PGAs, and PGA durations. They are organized into the specific filling classes defined in Section VI, so that ZϕB = {γ0 , γ6 }, ZϕJ1 = {γ5 , γ1 }, ZϕI1 = {γ3 }, ZϕI2 = {γ2 }, ZϕI3 = {γ4 }. Solid (hatched) color boxes represent PGAs for PGTs of the matching color scheduled by the minimal (bonus) allocation phases of Compute Schedule. The vertical blue dashed line indicates the end of the required time to schedule a minimal allocation of PGAs for each PGT. The red vertical dashed line indicates the end of a scheduling interval. is the number of active PGTs and R = |R| is the number of resources in the network. In contrast, the bonus allocation phase has operational complexity O(N 3 R). In the two phase system implemented by ComputeSchedule, the bonus allocation phase can be cut off by the end of the scheduling interval without impacting demand service agreements. When the scheduling offset is set to two scheduling intervals there is an entire scheduling interval to distribute schedules (as in Figure 2) and it is possible to cut off schedule computation arbitrarily close to the end An example network schedule produced by Comof a scheduling interval. puteSchedule is illustrated in Figure 7. This schedule is for a simplified version of the dumbbell topology network illustrated in Figure 1, with six end nodes instead of fif- IV.iv. Schedule Manager teen. There are seven active PGTs in the example, config- The Schedule Manager control application stores the curured to have different values for their minimal allocations, rent and subsequent network schedules and formats the minimum separations between PGAs, and PGA durations. component schedules for distribution. It offers two inThe solid (hatched) colored boxes represent PGAs sched- terfaces, the schedule distribution (SM:SD) interface and uled during the minimal (bonus) allocation phase. The the schedule (SM:S) interface. The SM:SD interface is an DirectAllocation schedule for each filling class has a internal interface which allows the Network Scheduler to block like structure and may include gaps of time in which push new schedules to the schedule manager as they are no PGAs are scheduled. These gaps of time carry for- computed. The SM:S interface is an external interface ward into the minimal allocation part of the schedule S which allows network components to request the current built from concatenated direct allocation schedules. In the or next schedule. The Schedule Manager consumes the Z bonus allocation phase, additional PGAs are scheduled in interface with the central controller, enabling it to push some of these gaps, improving the resource utilization and network schedules for distribution to components. decreasing idle time. rithm 7, RoundRobinBonus of Appendix B, which is also based on a modification of the classical Round Robin scheduling algorithm. In this phase Compute Schedule passes again through the schedule constructed during the minimal allocation phase, and wherever possible schedules additional PGAs. This decreases the idle time of each resource in the network, as well as decreasing the expected time to generate all Ndinst packets of each accepted demand d.
The time complexity of the Compute Schedule process V. Performance Analysis motivates the division of the process into the minimal and bonus allocation phases. In Appendix D we prove that an Upholding the service agreement that Arqon establishes implementation of the minimal allocation phase has op- for each accepted demand (Definition 3) is essential to erational complexity O(N R) + O(N 2 ), where N = |ZΦ | ensure the delivery of reliable service. Here we develop 14
theorem is non-trivial and relies upon many intermediate results, each of which is stated and proved in Appendix C. The statement requires the set of filling classes to be wellbehaved. This property, defined formally in Appendix C, means that a method of comparison between filling classes can be defined consistently based on the resources associated with the filling classes.
Algorithm 3: Overall scheduling algorithm for creating network schedules. DirectAllocation and RoundRobinBonus are respectively as in Algorithms 6 and 7 in Appendix B. Function MinimalAllocation: Input : Set of Filling Classes Φ, network schedule S Output: Updated network schedule S. for ϕ ∈ Φ do SP = DirectAllocation(ϕ, S, t0 + ′ ϕ′ <ϕ R(Zϕ )); end end Function BonusAllocation: Input : Set of Filling Classes Φ, network schedule S Output: Updated network schedule S. for ϕ ∈ Φ do S = RoundRobinBonus(ϕ, S); end end Function ComputeSchedule: Input : Set of Filling classes Φ Output: Compiled Schedule S̃ Initialise new empty schedule S; Set S ← MinimalAllocation(Φ, S); Set S ← BonusAllocation(Φ, S); end
Theorem V.2 (Minimal Allocation is guaranteed). Let d be a demand accepted by Arqon as the PGT γd . Suppose πγd ∈ Π in every relevant scheduling interval. Suppose Φ is a well-behaved set of filling classes. Then, in every relevant scheduling interval the schedule S = ComputeSchedule(Φ) contains at least NγSI PGAs d of the PGT γd . Moreover, the duration of S does not exceed T SI . Proof: Theorem V.1. To satisfy the service agreement it is necessary that 1. The schedule is computed before the end of each relevant scheduling interval; 2. The schedule is retrieved successfully by every component on πγd in every relevant scheduling interval; 3. The schedule contains at least NγSI PGAs of the PGT d γd . 4. The duration of the schedule S does not exceed the duration of one scheduling interval T SI .
the performance analysis of Arqon , by stating and proving results which qualify the operating conditions under which Arqon is guaranteed to satisfy these service agreements. As a supplement to these results, we motivate the connection between satisfaction of service agreements and successful execution of quantum network applications by end nodes. We prove that satisfaction of a service agreement for a demand d with service error parameter ϵservice d translates into end nodes successfully generating all packets of pairs required to execute their targeted application ). with probability at least (1 − ϵservice d We define relevant scheduling intervals as those that are relevant to the satisfaction of the service agreement.
Property 4. ensures that no schedules overruns the scheduling interval, which would prevent complete execution of the schedule for the subsequent scheduling interval. In the hypothesis, it is assumed that 1. and 2. hold. Properties 3. and 4. are guaranteed by Theorem V.2, a full proof of which is given in Appendix C. An application session succeeds if N inst instances of the quantum application are successfully executed by the end nodes which register it. For this to be possible, at least N inst packets of end-to-end links must be successfully generated. In this way, application success hinges upon the receipt of minimal service.
Definition 11 (Minimal service). Recall from Definition 2 that a demand d from an application session on end Definition 10 (Relevant scheduling intervals). The rel- nodes specifies at least N inst packets to be generated. We d evant scheduling intervals for an accepted demand d are say that an application session achieves minimal service those between tstart and the scheduling interval in which if at least N inst packets of end-to-end links are successfully d d the demand is either terminated or expires. generated before the demand’s expiry time.
Theorem V.1 (Deterministic Satisfaction of Service Agreements). Let d be a demand accepted by Arqon as the PGT γd . Suppose the path partition Π remains static in all relevant scheduling intervals for d and that every component on the path πγd retrieves each network schedule before its start time. Then, Arqon deterministically satisfies the service agreement for demand d. To prove Theorem V.1, which is our main performance result, we first state the following theorem, a proof of which is given in Appendix C. The proof of the following 15
Lemma V.3. Let d be a demand accepted as a PGT γd for which Arqon satisfies the service agreement. Suppose all nodes on the path πγd attempt all scheduled PGAs. Then, the application session which submitted d achieves minimal service with probability at least (1 − ϵservice ). d Proof. (Lemma V.3) By the hypothesis, the service agreement for demand d is satisfied and all nodes on the path πγd of the PGT γ realizing the demand attempt all scheduled PGAs. Let x be the total number of packets generated for d as a result of the PGAs attempted. There
are two possible scenarios in which a service agreement is satisfied: the demand is either terminated or expires. We are only concerned with demands that expire. If d was terminated, then we may assume that either Ndinst packets were successfully generated and the application session achieved minimum service, or the application session instance was canceled for some reason unknown to the central controller – in which case the service agreement is also terminated. It follows from the Definition 4 of the minimal allocation that if NγSI PGAs are attempted in d expiry SI start each of n = ⌈(td − td )/T SI ⌉ scheduling intervals, then the number x of successfully generated packets satisfies x ≥ Ndinst with probability at least (1 − ϵservice ). d
VI.
Implementation
We have developed a particular implementation of Arqon written in Python [6] that is designed to enable configurable simulations of realistic networks. We define a family of network topologies that adheres to a set of physically motivated principles and limit the scope of our implementation to this family of networks. Crucially, our implementation includes the specification of a set of allowed paths Pallowed , a specification of the path partition Π, and the specific choice of filling classes Φ induced by Π. The specific choice of filling classes thus defined has the property of being well-behaved, ensuring compatibility with the performance results in Section V. To enable numeric evaluations of heterogeneous networks from within this family, with a diverse range of entanglement generation capabilities, we implement a method of generating a network capabilities table which relies on input parameters for mean and standard deviations of the entanglement generation rate and fidelity on fixed length paths, and an scaling calculation based on the length of end-to-end paths. The full details of our implementation are provided by our open source simulator and its documentation [6]. Here we highlight key features, particularly those that are relevant to the numeric evaluations in Section VIII. VI.i.
End Nodes
Quantum Computing (BQC) [3, 18], quantum teleportation [9, 53], or any of these applications combined with entanglement purification [35, 10]. We derive the minimum entanglement fidelity and number of pairs requirements from resources [1, 32, 53, 53, 35]. We treat teleportation type applications as test-applications, which may be used to validate near term quantum network deployments. For this reason, we simply require an entanglement fidelity of greater than 0.5 for teleportation, which is the classical bound. VI.ii.a.
Assigning Applications
Each application we define in [6] specifies critical information required to produce a valid demand. In particular this includes the (minimum) window duration w. For real end nodes, the maximum memory lifetimes of qubits will affect which application programs can be supported, as these set hard upper bounds for window durations. Application programs don’t have an inherent window. In a deployed setting, the local runtime of an end node must set a window based not only on qubit memory lifetimes but also on the duration of time in which a generated packet must remain in memory when executing an instance of the application program. We define a minimum window for an application based on an estimate of how long exemplary quantum hardware may require to execute an application instance. We model the quantum hardware of end nodes based on either the NV center in diamond [48, 22, 40, 78] or trapped ion platforms [27, 15, 67, 63]. We use data from [78] for the NV platform and from [63] for the trapped ion platform to set the memory lifetimes of individual end nodes to currently experimentally achievable lifetimes in a networked setting (i.e. memory lifetime while simultaneously attempting entanglement generation). Then, when randomly assigning applications to end nodes, we ensure that the memory lifetime of the end node can support the requirements of the application. In a deployment, some end nodes may be operated as server nodes, for example for serving BQC applications, where less powerful end nodes may be the requesting clients. To support such use cases, we implement a registration of end nodes as either discoverable or not. Practically, a server should be discoverable. When assigning applications, we use use this discoverable property as a proxy for a node being a server or a client. We only assign applications between two clients, or between a client and a server. By mocking these constraints when assigning applications to end nodes, we are effectively replicating some of the behaviors of capability negotiation, without fully implementing such a protocol.
Our implementation is not intended to provide a detailed simulation of end nodes. However, we implement a simple physically motivated model for assigning applications to end nodes and configuring application demands, and we implement demand submission and termination behaviors of end nodes because they are critical for simulating Arqon. In a deployed network, user input will determine which applications an end node runs. We define a set of realistic quantum network applications and implement a method of assigning these applications to end nodes [6]. VI.ii.b.
Demand Submission
For each application assigned to an end node, we draw the initial demand submission time from a Uniform[0, texpiry ) rel start expiry We define a dictionary of possible applications [6] based distribution, where texpiry = t + t is the relative rel on minimum fidelity and number of entangled pair require- expiry time. This ensures that the initial demand submisments of Quantum Key Distribution (QKD) [41, 8], Blind sions are not all clustered together around the start of a VI.ii.
Applications
16
simulation and mocks the demand submission process by node (v ∈ J), or a long-distance backbone (v ∈ B). Thereindependent end nodes. Thereafter, whenever a demand fore, the set of vertices V in the network resource graph is obtains minimal service (and is then terminated), expires a disjoint union of component types, or is removed from the network, a new demand is submitV = E ⊔ I ⊔ J ⊔ B. (13) ted time Exponential(tresubmit ) later, where the value of tresubmit , the average resubmission time, is set separately To further define a family of internallyconnected netfor each application source assigned to an end node. works we introduce a constraint on the V2 possible edges to a set of allowed edges, denoted E ∗ . The definition of VI.iii. Creating Packet Generation Tasks allowed edges is based on three principles: To create a PGT γd for a demand d there needs to be a 1. An EGI is always needed for entanglement generation method of calculating Eγd , the execution time of a PGA between two nodes with entanglement generation capacket for γd , pγd , the packet generation probability for a pabilities [13, 58]. PGA of duration Eγ , and NγSI , the minimum allocation of d PGAs for γd . These calculations depend on the demand 2. Entanglement swapping must always be mediated by parameters, the service error parameter ϵservice , and the a node that has at least one qubit with entanglement d rate of successful entanglement generation along the path generation capabilities and an additional qubit with πγd of γd . In our implementation ϵservice is a configurable some memory capabilities [38, 17, 78, 94]. d parameter set by the central controller and the same value 3. Long-distance backbones always own a private set of is used for every demand d. EGIs, both internally to the long-distance backbone, To calculate possible values of Eγd for a PGT γd we use as well as at the end points where they are exposed approximations by Naus from [72] for the probability of k to other network components [38, 80, 81, 83, 63]. successes in a window w given a rate of average successes λ. For a specified rate of entanglement generation success, The set of edges E in a network resource graph must be these approximations are used to calculate possible pairs a subset of the set of allowed edges, E ⊆ E ∗ . Informally, packet for a PGT γd as in the following types of edges are allowed: (e, i), (i, j), (j, b), Eγd and pγd . To calculate NγSI d Definition 4 we use Hoeffding’s inequality [52]. This cal- where e ∈ E, i ∈ I, j ∈ J, b ∈ B and allowed edges are culation depends on the value of ppacket . See Appendix E reflexive, so that (e, i) is an allowed edge means that also γd for more information about the calculation of Eγ based (i, e) is an allowed edge. A formal definition of the set on ppacket , and [6] for the Python implementation of these E ∗ of allowed edges is stated in Appendix E. For details calculations. on generating random network topologies from within this We set the final values for Eγ , ppacket , and NγSI based family of networks, see [6]. γ on the solution of Definition 12 (Local Area). Let G = (V, E) be a network packet SI minsep pγd = argmin Nγd (p) Eγd (p) + tγd . (12) resource graph, and B the set of long-distance backbones. p Let EB = {(e1 , e2 ) ∈ E | e1 , e2 ∈ B} and EB = E \ EB . Let The quantity minimized in (12) captures a notion of how much load will be placed on the network by accepting the PGT. The calculation therefore optimizes the selection of ppacket for the value that minimizes the load. VI.iv.
GB := (V \ B, EB )
Network Topology
We specify a set of physically motivated constraints on the network resource graph which define a family of networks. These constraints help to ensure that the network topology of any network we simulate represents a physically realizable quantum network. In a deployment of Arqon these constraints will be replaced by simple input of the actual network topology and the logical connections present in the network. If a deployed network is also an element of our broad family of networks, then it may be equipped with Pallowed and Π as in our implementation.
(14)
be the subgraph of G formed by removing every longdistance backbone vertex and corresponding edges. Then the local areas of G are the (maximal) internally connected sub-components of GB . The set of local areas is denoted L. The concept of a local area is introduced to aid in describing the scale of a quantum network. Local areas induce a structure on the network resource graph such that it can be decomposed into the graph GB and a graph GC which contains only local areas and long distance backbones. The graph GC captures the local area connectivity of G. VI.v.
Path Computation
The set of allowed paths Pallowed ⊂ Pvalid is a restriction on the set of valid entanglement generation paths. In ApThe first constraint we impose is to consider only inter- pendix E we formally define Pallowed following a construcnally connected network resource graphs (Definition 5). tion which minimizes the number of long-distance backEvery network component v ∈ V is uniquely identified as bones traversed, rather than strictly minimizing the abeither an end node (v ∈ E), an EGI (v ∈ I), a junction solute number of hops in a path. This construction is VI.iv.a.
Network Resource Graph
17
motivated by the expectation that a relatively large loss For any network schedule in which a PGT γ cannot of entanglement generation success rate will result from reach the termination criteria of obtaining minimal sertraversing of a long-distance backbone, as compared to vice (i.e. less PGAs are scheduled than the remaining intraversing multiple hops within a local area [28, 63, 80]. stances to execute), we determine the number of packets generated by drawing from a Binomial distribution with Definition 13 (Specific choice of path partition). Let probability of success ppacket . Otherwise, we sample from γ G = (V, E) be an internally connected resource graph and a Bernoulli distribution with probability of success ppacket γ let E ⊆ E ∗ . Let L = {Li = (Vi , Ei )} be the set of local ar- for each PGA in turn. This two-stage approach allows eas of G. Let Ji = J ∩ Vi be the junction nodes in sub- us to minimize the time required to simulate execution of graph Li . Denote by π = (π1 , π2 , · · · ) a path π with ver- network schedules, while still allowing accurate reporting tices πi ∈ V. of when minimal service is obtained. We define the partition Π of Pallowed in the following manner:
VII.
ΠB = {π ∈ Pallowed : ∃k s.t. πk ∈ B}
Complexity Analysis
Arqon must produce a new network schedule every scheduling interval, with a total computation time not exceeding the scheduling interval. To validate that this j∈J is feasible, we analyze the operational complexity of our where Pallowed is as defined Appendix E, Definition 24. implementation of the Network Scheduler control application. Our operational complexity analysis is based on determining which fundamental operations, such as value Lemma VI.1. assignment, list insertion, list appending, list sorting, etc. Π = {ΠB } ∪ {Πj }j∈J ∪ {Πi }i∈I , (15) occur in the implementations of our algorithms, as in Listings 1-8 in Appendix F. For each fundamental operation, where ΠB , ΠJj ∀j, and ΠIi ∀i are as in Definition 13, is a such as value assignment, we determine the time comdisjoint partition of Pallowed . plexity of the operation, for example: value assignment is O(1). We therefore calculate the time complexity of Proof. See Appendix E. our algorithms based on the number of operations of each type, and the time complexity of each type of operation. VI.vi. Network Capabilities The details of our analysis are given in Appendix D. The network capabilities manager populates the network VII.1. The complete program Netcapabilities table using a simple heuristic model when the Theorem workScheduler has operational complexity network is initialized. Our implementation does not in clude dynamic update handling for the capabilities of net R 2 2 3 O k2 (N + k) + R + (N + R) + N R , (17) work components or paths through the network. See [6] for full details of the model. where R = |R| is the number of internal resources in the network, N = |ZΦ | is the number of active PGTs, and VI.vii. Filling Classes k = |Γ| is the number of PGTs in the task intake object. The properties of the set of filling classes are directly inherited from the specific choice of path partition, which Proof. The program NetworkScheduler consists of defines their structure (Definition 13). The specific choice the program sequence UpdateFillingClasses, AdmitTasks, and ComputeSchedule. By Lemma D.8 Upof filling classes can be written as dateFillingClasses has operational complexity Φ = {ΦB } ∪ {ΦJj }j∈J ∪ {ΦIi }i∈I . (16) O((N + R)2 ). (18) In Appendix E we prove that this specific choice of filling By Theorem D.10 AdmitTasks has operational complexclasses has the property of being well-behaved. ity R 2 O k2 (N + k) + R . (19) VI.viii. Execution of Network Schedules ΠJj = {π ∈ Pallowed \ Πb : ∃k s.t. πk ∈ Jj }, ∀j ∈ J [ J I Πi = {π ∈ Pallowed \ (Πb ∪ Πj ) : ∃k s.t. πk = i}, ∀i ∈ I,
Since we do not implement a detailed model of end nodes, in our implementation we mock the execution of network schedules by sampling random variables to determine how many PGAs successfully generate packets. We then assume that whenever a packet is generated as the result of a PGA, then the corresponding application instance is successfully executed. Our implementation does include session termination behavior in which end nodes terminate application sessions after they have obtained minimal service. 18
The program ComputeSchedule consists of a minimal allocation phase, a bonus allocation phase, and a schedule compilation phase. The minimal allocation phase contributes (Lemma D.12) O(N R) + O(N 2 )
(20)
to the operational complexity. The bonus allocation phase contributes (Lemma D.13) O(N 3 R).
(21)
(22)
Overall, the program NetworkScheduler has operational complexity, O k2R (N + k)2 + R + (N + R)2 + O(N 3 R).
Our implementation of the Network Scheduler has an operational time complexity with a polynomial dependency on the number of active PGTs N and the size of the task intake buffer k. However, there is an exponential dependence on the number of resources in the network, R. In a deployment, the number of resources is expected to be relatively static, and will typically act as a constant factor in the operational complexity of the Network Scheduler. Nevertheless, the exponential dependence on R does indicate that Arqon is best suited for networks in which R < 1000. This result conforms with the heuristic expectation that distributed control architectures are more suitable than centrally controlled network architectures for very large networks [5].
VIII.
Evaluation
Arqon is designed to deliver reliable service, according to reliability requirements (R1)-(R4). The first requirement, (R1) is satisfied by design, as all demands receive accept/reject messages from the demand manager within two scheduling intervals following their registration [6]. By Theorem VII.1, which captures the overall operational complexity of the Network Scheduler control application, it is expected that network schedules can always be computed in time to be delivered. Then, by Theorem V.1, it is expected that Arqon satisfies requirements (R2)-(R4) as long as the path partition Π remains static throughout an evaluation. However, from the perspective of a network operator, there remain several relevant questions regarding the manner in which reliable service is delivered, including the following.
1.0010
20
1.0005
15
1.0000
10 5
0.9995 7
10 s
0.9990
0 0
200
400 Time (hours)
600
Number of Active PGTs (a.u.)
O(N 3 R).
Proportion of Accepted Demands Which Obtain Minimum Service (a.u.)
Compiling the resulting schedule contributes only O(N R) (Lemma D.14). The total operational complexity of ComputeSchedule is therefore dominated by the bonus allocation phase and is given by Theorem D.15 as
800
Figure 8: Proportion of accepted demands which obtain minimal service (left, blue) and the number of active PGTs (right, orange), compared to the time at which the scheduling interval occurs. The scheduling interval duration 30 minutes and the data corresponds to a simulated 10 weeks of continuous network operation. Shaded regions show 1 standard deviation of the mean. In this section we first validate that Arqon delivers reliable service on static network topologies and then address these questions, which capture additional performance metrics. Finally, we validate our operational complexity analysis of the Network Scheduler with thorough numeric evaluations that supply concrete time values for computation times in a variety of parameter regimes. In all simulations, the demands for service submitted by pairs of end nodes are based on the real minimum fidelity requirements of BQC (2, 6, or 10 qubit) [32, 53], e91 based QKD [1], teleportation [53], or any of these applications pre-pended by purification following the DEJMPS protocol [35] of the bipartite entangled pairs. The other parameters of each demand, such as the number of pairs and the window duration are set based on the application and the network capabilities database for that simulation [6]. Lists of the applications simulated in each simulation are included as JSON files in [6]. VIII.i.
Service Reliability
To meet the reliability requirements (R2)-(R4), Arqon must satisfy demands before their deadlines and the arrival of new demands must not disrupt service to already accepted demands. A demand is satisfied when its associ(Q1) What effect does the service error parameter ϵservice ated application session achieves minimal service (Definihave on the service delivered? tion 11). By Lemma V.3, if the service agreement for a (Q2) How quickly does Arqon satisfy service agreements, demand d is satisfied, then the corresponding application session achieves minimal service with at least probability relative to demand expiry times? (1 − ϵservice ). d (Q3) What impact does the bonus allocation phase of the We validate that Arqon delivers reliable service first Compute Schedule process of the Network Scheduler with simulations of a network with the dumbbell topology have on the service delivered? illustrated in Figure 1, and with ϵservice = 1e − 5 for all (Q4) What proportion of submitted demands are accepted? demands. Then, we validate that the reliability of service delivery is not conditional on a specific network topology (Q5) What impact does the specific choice of filling classes or number of demand sources by simulating random net(16) have on which of the registered PGTs are ac- work topologies from the family of networks defined in cepted by Admit Tasks? Section VI. 19
VIII.i.a.
Dumbbell Topology Network
We simulate one thousand randomly seeded runs, each corresponding to 846 hours (1694 half hour scheduling intervals) of continuous operation of the dumbbell topology network in Figure 1. In every run, applications are assigned to 80% of all possible end node pairings connected by a route in ΠIi ∀i ∈ I, 10% of all end node pairings connected by a route in ΠJj ∀j ∈ J, and 10% of all end node pairings connected by a route in ΠB . As long as at least one of the nodes assigned the application is ‘not discoverable’ (see Section VI), then the application session submits demands for service. These simulations included an average of 18 demand sources, with the (static) number per simulation ranging from 3 to 26. Figure 8 shows how two metrics vary over time for the dumbbell topology simulations: (1) the proportion of accepted demands that obtain minimal service, and (2) the number of active PGTs at any given time. For the minimal service proportion metric, time corresponds to when each demand was accepted as a particular PGT. Across all one thousand simulation runs, a total of 180,662 accepted demands reached their expiry times. With the stringent value of ϵservice = 1e−5 used in these simulations, Lemma V.3 predicts that at most 2 accepted demands should fail to obtain minimal service. The simulation results confirm this expected behavior: all accepted demands obtained minimal service (proportion = 1.0, standard deviation = 0).These outcomes validate that the service delivered satisfies reliability requirements (R2) and (R3). The variation in the number of active PGTs over time enables validating that arriving demands do not disrupt service to already accepted demands (R4). Starting from network initialization at time zero, pairs of end nodes begin submitting demands and some of these are accepted as specific PGTs by Admit Tasks. In these simulations, the time at which different end node pairs submit their first demand is uniformly distributed over the first 107 seconds of network operation. This process results in the number of PGTs to schedule increasing over time, before reaching a steady state average of 15.5 PGTs after about 278 hours (107 seconds) of continuous operation. The ramp-up in the number of PGTs to schedule has no impact on the proportion of demands obtaining minimal service, confirming that (R4) is satisfied. VIII.i.b.
Random Network Topologies
The random topologies we simulate are parameterized in Table 1 by the number of long-distance backbones, the number of local areas, and the number of end nodes in the network. For each parameterization, we randomly generate ten network topologies and then, we simulate ten randomly seeded runs for every topology. Every run corresponds to 757 hours (1514 half hour scheduling intervals) of continuous operation. In every run we assign application sessions to 20% of all possible end node pairings connected by a route in ΠIi ∀i ∈ I, 15% of end node pairings connected by a route in ΠJj ∀j ∈ J, and 5% of end node 20
Long-distance Backbones
Local Areas
End Nodes
1 2 2 2 2 3 5 6 7 12
2 2 2 3 3 3 4 3 5 4
15 15 50 30 50 30 40 35 50 40
Table 1: Parametrization of the randomly generated topologies simulated. pairings connected by a route in ΠB . To address (Q1) and study the impact of different values for the ϵservice parameter, we perform each simulation with five different settings: ϵservice ∈ {1e − 5, 0.001, 0.01, 0.1, 0.5}. In Table 2 we record the proportion of accepted demands which obtain minimal service, which is always greater than the lower bound of (1 − ϵservice ) predicted by Lemma V.3. These results validate that Arqon delivers reliable service for a wide range of network topologies and number of demand sources. VIII.ii.
Additional Performance Metrics
The average values of performance metrics addressing (Q1)-(Q3) are reported in Table 2. To characterize the impact of the bonus allocation phase of Compute Schedule, we disabled this feature and repeated all simulations of randomly generated network topologies with the same random seeds as in the simulations with default Arqon. The total proportion of accepted demands which obtain minimal service in these simulations was always > 99%, both with and without the bonus allocation phase. This outcome persisted even when ϵservice was relaxed to the very high value of 0.5, which Lemma V.3 predicts to allow up to 50% of demands to fail to obtain minimal service. These results indicate that Arqon over-serves accepted demands, as compared to the service error parameter ϵservice . As this effect persists when the bonus allocation phase is disabled, we trace the cause of this excess service to how Arqon calculates the minimal allocation for each demand (Definition 4), which has proven to be a large overestimate. Application sessions on end nodes may benefit from over-service of accepted demands, but wider network performance metrics such as the proportion of accepted demands may suffer from over-service to demands. In an alternate implementation, this may be addressed by replacing the method which solves the the system of equations determining the minimal allocation with a weaker solution that determines smaller values for the minimal allocation.
20
107 s paccepted = 0.15
0.8
15 0.6 10 0.4 5
0.2 0.0
0
200
400 Time (hours)
600
800
Number of Active PGTs (a.u.)
Proportion of Submitted Demands Accepted (a.u.)
1.0
0
Figure 9: Proportion of submitted demands which are accepted at a specific time (left, blue) and the number of active PGTs (right, orange) over time. Application sessions are first created at times that are uniformly distributed over the first 107 s of network operation, emphasized by the vertical black dotted line. The horizontal dashed blue line indicates the average of the points after the black dotted line. Arqon schedules a minimal allocation of PGAs for all active PGTs in every scheduling interval, regardless of whether or not the expected number of successfully generated packets, E[# successful PGAs] = N PGAs scheduled × ppacket (23) already exceeds the number of required successes (N inst ). To prevent over-serving demands, an alternate implementation may decrease the minimal allocation for PGTs following the scheduling interval in which (23) exceeds N inst . The data in Table 2 also addresses (Q2) and (Q3). (Q2): Arqon satisfies service agreements for accepted demands significantly in advance of demand expiry times. This is true for all ϵservice values simulated and remains true if the bonus allocation phase of Compute Schedule is disabled. (Q3): The bonus allocation phase significantly impacts how quickly an accepted demand obtains minimum service, relative to its expiry time. The mean service to expiry time more than doubles when the bonus allocation phase is disabled. Approximately half of all PGAs scheduled by Arqon are scheduled by the bonus allocation phase of Compute Schedule, regardless of the value of ϵservice . This proportion directly accounts for the speedup of the service to expiry time introduced by this phase.
VIII.ii.a.
demands may translate into long wait times to receive a service agreement, a result of demands needing to be resubmitted multiple times. For simulations of the Dumbbell topology network, Figure 9 plots the average proportion of submitted demands that are accepted by Admit Tasks per scheduling interval and the number of active PGTs in each scheduling interval. The proportion of demands accepted as some particular PGT decreases as a function of the number of active PGTs. It reaches a steady state value of 0.15 after 107 s, after which time all application sessions have submitted at least one demand. When demands are rejected, terminated, or expire, application sessions on end nodes submit new demands following a Poisson process with a session specific resubmission rate. For the simulations of randomly generated network topologies, the average proportion of demands accepted and the proportion of demands which pass demand registration, both with default Arqon and with the bonus allocation phase of Compute Schedule disabled are recorded in Table 3. With default Arqon, for all values of ϵservice simulated the average proportion of demands accepted was between 0.12 and 0.22. In contrast, the proportion of demands which passed Demand Registration always exceeded 0.98. Therefore, almost all rejected demands are rejected by Admit Tasks rather than be Demand Registration. With bonus allocation disabled, the average proportion of demands accepted decreased by at least 0.036 for every simulated value of ϵservice , and by up to 0.073 for ϵservice = 0.5. In all simulations (dumbbell topology and random network topologies), the average proportion of demands accepted is low. This indicates that the average load on the network in our simulations is similar to the maximum supportable load calculated by Admit Tasks. Combined with the results from Table 2 which indicate Arqon over-serves accepted demands, we expect that the acceptance criterion of Admit Tasks is more stringent than is necessary to satisfy reliability requirement (R4). An alternate implementation of Arqon may modify the function CalculateRequiredTime, with which AdmitTasks calculates the time required to schedule a minimal allocation of all active PGTs. A possible modification would be to omit from the calculation any accepted PGTs γ for which the expected number of successfully generated packets (23), already exceeds the required number, Nγinst . VIII.ii.b.
Proportion of Demands Accepted
The proportion of submitted demands that are accepted, the subject of (Q4), is a performance metric that captures information about the load on a network relative to the tolerance of Arqon’s admission control algorithm (Admit Tasks). It is a metric that directly impacts application sessions on end nodes, as a low proportion of accepted 21
Profiling Accepted PGTs
To address (Q5) Figure 10 plots the number of submitted PGTs (Figure 10a) and the number of accepted PGTs (Figure 10b) in each filling class. There is one data point for each scheduling interval, for each network topology parameterization in Table 1. Data points are averages over the ten random topologies generated from each parameterization and the randomly seeded simulations for each topology. The number of active PGTs in one filling class can impact the proportion of PGTs admitted to another filling class because Admit Tasks reserves time for active PGTs
ϵservice
Mean Proportion of Accepted Demands Which Obtain Minimal Service
Mean Service to Expiry Time
Mean Proportion of PGAs Scheduled in Bonus Allocation
Default Arqon: Bonus Allocation Enabled in Compute Schedule
1e-05 0.001 0.01 0.1 0.5
1.0000 1.0000 1.0000 1.0000 0.9998
0.3706 0.3777 0.3809 0.3847 0.3837
0.4950 0.5279 0.5382 0.5386 0.5423
with Bonus Allocation Disabled in Compute Schedule
1e-05 0.001 0.01 0.1 0.5
1.0000 1.0000 1.0000 0.9998 0.9956
0.7481 0.8194 0.8483 0.8639 0.8646
0 0 0 0 0
Table 2: Additional performance metrics addressing (Q1)-(Q3) from simulations of the randomly generated network topologies parameterized in Table 1. ϵservice
Total proportion of Demands Accepted
Total Proportion of Registered Demands Accepted
Total Proportion of Demands which Pass Demand Registration
Default Arqon: Bonus Allocation Enabled in Compute Schedule
1e-05 0.001 0.01 0.1 0.5
0.127 0.123 0.102 0.120 0.211
1e-05 0.001 0.01 0.1 0.5
0.073 0.087 0.042 0.055 0.138
0.131 0.128 0.105 0.123 0.222
0.992 0.991 0.993 0.993 0.984
with Bonus Allocation Disabled in Compute Schedule
0.077 0.096 0.047 0.069 0.155
0.992 0.986 0.991 0.982 0.977
Table 3: The total proportion of demands registered and accepted as particular PGTs, addressing (Q4), in simulations of the randomly generated network topologies parametrized in Table 1. on the resources associated with their filling classes. In our implementation of Arqon, we employ the specific choice of filling classes (16) derived from the path partition in Definition 13. In this path partition, all paths which contain at least one long-distance backbone are in the same cell of the partition. For network topologies with a large number of local areas and long-distance backbones, the result is that PGTs with paths between only two local areas are in the same filling class as PGTs with paths between multiple local areas. In Figure 10 there is some clustering of the registered PGTs (Figure 10a) based on the number of local areas in the network parameterization. In contrast, after Admit Tasks (Figure 10b) there is clear clustering of the active PGTs based on the unique network topology parameterization, with ten data groupings visible in each subfigure, each corresponding to one of the ten distinct network parameterizations. 22
For all network parameterizations simulated, the number of registered PGTs in a junction (ΦJj ∀j ∈ J) or interface (ΦIi ∀i ∈ I) filling class increases nearly monotonically with the number of registered PGTs in the backbone filling class (Figure 10a). Similarly, the number of registered PGTs in an interface filling class increases nearly monotonically with the number of registered PGTs in a junction filling class. The relative number of PGTs registered in each filling class derives immediately from the simulation configuration, which sets the number of application sessions between end nodes connected by routes in interface, junction, and backbone filling classes. After Admit Tasks (Figure 10b), there remains a nearly monotonic increase in the number of active PGTs in an interface filling class with the number of accepted PGTs in a junction filling class. In contrast, the numbers of active PGTs in a junction or interface filling class relative to the number in the backbone filling class indicate a different relationship.
The number of PGTs accepted to the backbone filling class inhibit acceptance of PGTs to both junction and interface filling classes. To combat this effect an alternate implementation of Arqon may define a path partition which sub-divides the backbone cell of the partition ΠB based on the number of local areas traversed by a path.
by Algorithm 6, contributes O(N R)+O(N 2 ) and contains no branching. The total number of operations depends on N , but not on particular PGT characteristics. The resulting network schedule may contain gaps during which no PGAs are scheduled, as illustrated in Figure 7. The bonus allocation phase, implemented by Algorithm 7 attempts to fill these gaps. It contributes O(N 3 R), which dominates the overall complexity. Its branching behavior VIII.iii. Numerical Complexity Analysis depends non-trivially on the number and duration of gaps, In every simulation conducted, Arqon was able to compute the execution times Eγ (∀γ ∈ ZΦ ) of PGAs that may be the network schedule much faster than the cutoff time for added, and the minimum separation tminsep (∀γ ∈ ZΦ ) beγ schedule distribution (tcompute ≪ T SI ). The average time tween PGAs of each PGT. to produce a network schedule for each of the random To illustrate this branching behavior, we consider a spetopologies simulated is recorded in Table 5 in Appendix D. cific set of PGTs (ZΦ∗ ) with the following structure: The maximum of the average times required to produce • the first PGT γ0 has tminsep = 200 seconds, and all a network schedule was less than 0.25 seconds (tcompute ), γ0 other PGTs γi , i > 0 have tminsep = 0; whereas the duration of the scheduling interval was 1800 γi seconds (T SI ). • Eγ = 1 second, ∀γ ∈ ZΦ∗ ; In Section VII we proved Theorem VII.1, which states that the full program NetworkScheduler has opera• NγSI = 20, ∀γ ∈ ZΦ∗ . tional complexity that is polynomial in the number of PGTs in the task intake buffer (k = |Γ|) and the number To study this scenario, the scheduling interval was set to of active PGTs (N = |ZΦ |), but exponential in the total eight thousand seconds (T SI = 8000) and we repeated number of internal resources in the network (R = |R|). We schedule computation for scenarios with |ZΦ∗ | ranging from validate our complexity analysis with numerical results, five to four hundred, in steps of five. In Figure 12 the schedule computation time, decomdemonstrating how operational complexity translates to execution time for various combinations of k, N , and R. posed into the minimal allocation phase (left), the bonus First, we assess the computation time of AdmitTasks us- allocation phase (middle) and the overall computation ing randomly generated sets of active PGTs (ZΦ and PGTs time (right), is plotted against N . Data points are the in the task intake buffer (Γ). The methods for generat- average over fifty independent repetitions and error bars ing these random sets are included in our simulator [6]. indicate one standard deviation. The time to complete Second, we evaluate ComputeSchedule with a carefully the minimal allocation phase (left) is increasing in N and designed set of PGTs to schedule (ZΦ∗ ) for which specific al- a polynomial fit validates that it has O(N 2 ) complexity gorithm characteristics produce clear features in the com- (left). The time to complete the bonus allocation phase putation time. This second evaluation complements our (middle) exhibits non-trivial variation with N , yet all feaearlier simulations on random network topologies, where tures are explained by our algorithmic analysis. Whenever there is a gap in the schedule, the Bonusschedule computation times were consistently aligned with RoundRobin algorithm checks the next PGT in round the complexity analysis. robin order to determine if all the required resources are available (O(R) operation). Checking γ0 additionally reVIII.iii.a. Admit Tasks quires both checking for both past and future minsep viminsep ̸= 0. For small N , numerous gaps The operational complexity of AdmitTasks is given by olations, since tγ0 exist and the round robin index frequently revisits γ0 , re(19). Figure 11 plots the computation time against k for sulting in the initial spike in computation time. The most constant N (left) and against N , for constant k (right). time-intensive operation occurs when filling gaps between Each data point is the average over one hundred randomly two already scheduled PGAs, which requires list insertion generated ZΦ and Γ pairs, with error bars indicating one 3 (O(N ) in our implementation). When no gaps exist but standard deviation. Polynomial fits of O(k ) (left) and 2 time remains in the scheduling interval, PGAs can simply O(N ) (right) confirm scaling consistent with (19), validating Theorem D.10. Importantly, these results demon- be appended to the schedule (O(1)). For N < 200, gaps strate that AdmitTasks is fast enough to process a large exists in the schedule output by the minimal allocation number of incoming PGTs (k) within a single scheduling phase, and these are filled by list insertion. For N ≥ 200, interval, even when there are many active PGTs (N ). For no gaps remain and new PGAs are only appended to the example, one thousand incoming PGTs (k = 1000) are schedule by RoundRobinBonus. This transition proprocessed in less than seven seconds when there are al- duces the local maximum at N = 200. As N increases further, the number of PGAs that can be appended to ready one thousand active PGTs (N = 1000). the schedule decreases, until N = 400 where the schedule output by the minimal allocation phase has no gaps VIII.iii.b. Compute Schedule and occupies the entire scheduling interval. A polynomial The operational complexity of ComputeSchedule is fit validates O(N 3 ) complexity for the bonus allocation given by (22). The minimal allocation phase, implemented phase. The overall complexity (right) confirms the result 23
(a) Number of Registered PGTs
(b) Number of Active PGTs
Figure 10: Profiling of PGTs registered by Demand Registration and active PGTs accepted by Admit Tasks based on their filling classes [backbone (ΦB ), junction (ΦJj ∀j ∈ J), and interface (ΦIi ∀i ∈ I) filling classes]. There is one data point for each scheduling interval, for each network topology parameterization in Table 1. Data is averaged over the ten random topologies generated from each parameterization, and ten randomly seeded simulations for each topology.
6
N=50 N=250 N=500
7
N=750 N=1000
Average Computation Time (s)
Average Computation Time (s)
7
5 4 3 2 1 0
6
k=50 k=250 k=500
k=750 k=1000
5 4 3 2 1 0
200 400 600 800 1000 k: Number of Incoming PGTs (a.u.)
200 400 600 800 1000 N : Number of Active PGTs (a.u.)
Figure 11: Average computation time of Admit Tasks for N = |ZΦ | active PGTs and k = |Γ| incoming PGTs requiring an accept/reject decision from Admit Tasks. Each data point is the average of 100 randomly generated ZΦ , Γ pairs and error bars show one standard deviation. Data points are fitted with polynomials of O(k 3 ) (left) and O(N 2 ) (right).
24
Schedule Computation Time (s)
O(N 2 ) Minimal
0.15
0.10
0.05
0.00 0
200
400
O(N 3 ) Bonus
5
5
4
4
3
3
2
2
0 200 400 N : Number of Active PGTs (a.u.)
O(N 3 ) Overall
0
200
400
Figure 12: Average computation time of the minimal (left) and bonus (middle) allocation phases of Compute Schedule, and overall computation time (right), plotted against the number of active PGTs N = |ZΦ∗ |. Each data point is the average of 50 repetitions of Compute Schedule for a set of active PGTs ZΦ∗ . Error bars show one standard deviation. Polynomial fits to the data are based on least squares fitting. of Theorem D.15, showing that the schedule computation contrast, many quantum network architectures implement time is dominated by the bonus allocation phase and has scheduling algorithms which rely on optimization, which O(N 3 ) complexity. See Appendix D for full details of our is generally slower than direct calculation of a schedule. Arqon’s admission control process, which ensures arrivcomplexity analysis. ing demands do not disrupt service to accepted demands, comes at the cost of rejecting some demands. In simulaIX. Conclusion and Outlook tions based on our proof of principle implementation we observed that there is scope to increase the proportion We have designed Arqon, a novel suite of control appli- of demands that Arqon accepts. We proposed modifying cations for a centrally controlled quantum network that the calculation which Arqon’s admission control process establishes and satisfies well-defined service agreements uses to estimate load on the network. To further increase with end nodes. These service agreements address real- the resource utilization and proportion of demands that istic application execution requirements on programmable may be accepted, we proposed defining a path partition end nodes, so that satisfying a service agreement implies that differentiates between paths through the network that that user applications can succeed. In contrast to existing cross one or multiple long-distance backbones. quantum network control architectures, Arqon includes an The performance of any quantum network architecture admission control mechanism which prioritizes service to needs to be tested in a real world deployment. We have already accepted demands over incoming demands, pre- developed an implementation of Arqon in Python as a venting service disruptions. simulator. The next step is to create a real-time impleWe extended the concept of reliable service from classi- mentation of Arqon, integrate it with an SDN-controller, cal computer networks and demonstrated through analysis and use the integrated system to produce network schedand numeric evaluations with a proof of principle imple- ules for the components of a test-bed quantum network. mentation that Arqon provides reliable service to all ac- Such a demonstration would bring scalable quantum netcepted demands in static network topologies. We designed working one step closer to reality. Arqon to respond to changes in network topology or capabilities. In our proof of principle implementation we did X. Acknowledgements not implement the mechanisms for handling these updates. A future research direction is to create concrete implemenSG, TRB and SW acknowledge funding from the Quantum tations of these mechanisms and evaluate the robustness Internet Alliance (QIA). QIA has received funding from of Arqon against changes to topology and capabilities in the European Union’s Horizon Europe research and innoa variety of parameter regimes. vation programme under grant agreement No. 101102140. We developed fast algorithms for producing network SW also acknowledges funding from NWO VICI. schedules and executing a demand admission control process, and demonstrated numerically that each algorithm References can process up to one thousand demands in less than 7 seconds. The core of these algorithms relies on directly [1] S. Abruzzo, S. Bratzik, N. K. Bernardes, H. Kampercalculating how a minimal allocation of PGAs for all acmann, P. van Loock, and D. Bruß. “Quantum repeaters tive PGTs can be scheduled in each scheduling interval. In 25
and quantum key distribution: Analysis of secret-key rates”. In: Physical Review A 87.5 (May 2013). issn: 1094-1622. doi: 10.1103/physreva.87.052315. [2]
S. E. Alm. “On the distributions of the scan statistics of a Poisson process”. In: Probability and Mathematical Statistics, Essays in honour of Carl-Gustav Esseen (1983). Uppsala, Sweden, pp. 1–9.
[3]
P. Arright and L. Salvail. “Blind Quantum Computation”. In: International Journal of Quantum Information 04.05 (2006), pp. 883–898.
[4]
L. Bacciottini, M. G. D. Andrade, S. Pouryousef, E. A. V. Milligen, A. Chandra, N. K. Panigrahy, N. S. V. Rao, G. Vardoyan, and D. Towsley. “Leveraging Internet Principles to Build a Quantum Network”. In: IEEE Network (2025), pp. 1–1. doi: 10 . 1109 / MNET . 2025 . 3569494.
[5]
P. Baran. “On Distributed Communications Networks”. In: IEEE Transactions on Communications Systems 12.1 (1964), pp. 1–9. doi: 10.1109/TCOM.1964.1088883.
[6]
T. Beauchamp, S. Gauthier, and S. Wehner. Code and Data for for Arqon: A Suite of Control Applications Enabling Reliable Quantum Networks. 2026. doi: 10.4121/ 97e0f340-6cc2-4908-9670-8308fed3e2ec.
[7]
T. R. Beauchamp, H. Jirovská, S. Gauthier, and S. Wehner. “A Modular Quantum Network Architecture for Integrating Network Scheduling with Local Program Execution”. In: IEEE Transactions on Quantum Engineering (2025), pp. 1–31. doi: 10 . 1109 / TQE . 2025 . 3624658.
[8]
C. H. Bennett and G. Brassard. “Quantum cryptography: Public key distribution and coin tossing”. In: Proceedings of the International Conference on Computers, Systems & Signal Processing, Bangalore, India. Vol. 1. Bangalore, India: IEEE, 1984, pp. 175–179. doi: https: //doi.org/10.1016/j.tcs.2014.05.025.
[9]
[10]
[11]
[12]
C. H. Bennett, G. Brassard, C. Crépeau, R. Jozsa, A. Peres, and W. K. Wootters. “Teleporting an unknown quantum state via dual classical and Einstein-PodolskyRosen channels”. In: Phys. Rev. Lett. 70 (13 Mar. 1993), pp. 1895–1899. doi: 10.1103/PhysRevLett.70.1895. C. H. Bennett, G. Brassard, S. Popescu, B. Schumacher, J. A. Smolin, and W. K. Wootters. “Purification of Noisy Entanglement and Faithful Teleportation via Noisy Channels”. In: Physical Review Letters 76.5 (Jan. 1996), pp. 722–725. issn: 1079-7114. doi: 10.1103/physrevlett.76.722. H. Bernien, B. Hensen, W. Pfaff, G. Koolstra, M. S. Blok, L. Robledo, T. H. Taminiau, M. Markham, D. J. Twitchen, L. Childress, and R. Hanson. “Heralded entanglement between solid-state qubits separated by three metres”. In: Nature 497.7447 (Apr. 2013), pp. 86– 90. R. C. Berrevoets, T. Middelburg, R. F. L. Vermeulen, L. D. Chiesa, F. Broggi, S. Piciaccia, R. Pluis, P. Umesh, J. F. Marques, W. Tittel, and J. A. Slater. “Deployed measurement-device independent quantum key distribution and Bell-state measurements coexisting with standard internet data and networking equipment”. In: Communications Physics 5.1 (2022), p. 186. doi: 10. 1038/s42005-022-00964-6.
26
[13]
H. K. Beukers, M. Pasini, H. Choi, D. Englund, R. Hanson, and J. Borregaard. “Remote-Entanglement Protocols for Stationary Qubits with Photonic Interfaces”. In: PRX Quantum 5.1 (Mar. 2024). issn: 2691-3399. doi: 10.1103/prxquantum.5.010202.
[14]
R. Bhardwaj and B. Jabbari. “ISDN frame relay and its congestion control”. In: International Journal of Satellite Communications 9.5 (1991), pp. 363–380. doi: https://doi.org/10.1002/sat.4600090513. eprint: https : / / onlinelibrary . wiley . com / doi / pdf / 10 . 1002/sat.4600090513.
[15]
B. B. Blinov, D. L. Moehring, L.-M. Duan, and C. Monroe. “Observation of entanglement between a single trapped atom and a single photon”. In: Nature 428.6979 (Mar. 2004), pp. 153–157. doi: 10.1038/nature02377.
[16]
S. L. Braunstein and A. Mann. “Measurement of the Bell operator and quantum teleportation”. In: Physical Review A 51.3 (1995), R1727. doi: https://doi.org/ 10.1103/PhysRevA.51.R1727.
[17]
H.-J. Briegel, W. Dür, J. I. Cirac, and P. Zoller. “Quantum Repeaters: The Role of Imperfect Local Operations in Quantum Communication”. In: Physical Review Letters 81.26 (Dec. 1998), pp. 5932–5935. doi: 10.1103/ physrevlett.81.5932.
[18]
A. Broadbent, J. Fitzsimons, and E. Kashefi. “Universal Blind Quantum Computation”. In: 2009 50th Annual IEEE Symposium on Foundations of Computer Science. Atlanta, Georgia, USA: IEEE, Oct. 2009, pp. 517–526. doi: 10.1109/focs.2009.36.
[19]
C. Brukner, N. Paunkovic, T. Rudolph, and V. Vedral. Entanglement-assisted Orientation in Space. 2005. arXiv: quant-ph/0509123.
[20]
G. C. Buttazzo. Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications. third. New York, NY, USA: Springer Science + Business Media, 2011. isbn: 978-1-4614-0675-4.
[21]
C. Cabrillo, J. I. Cirac, P. García-Fernández, and P. Zoller. “Creation of entangled states of distant atoms by interference”. In: Phys. Rev. A 59 (2 Feb. 1999), pp. 1025–1033.
[22]
L. Childress and R. Hanson. “Diamond NV centers for quantum computing and quantum networks”. In: MRS Bulletin 38.2 (2013), pp. 134–138. doi: 10.1557/mrs. 2013.20.
[23]
A. M. Childs. “Secure assisted quantum computation”. In: Quantum Information and Computation 5.6 (Sept. 2005). issn: 1533-7146. doi: 10.26421/qic5.6.
[24]
C. W. Chou, J. Laurat, H. Deng, K. S. Choi, H. de Riedmatten, D. Felinto, and H. J. Kimble. “Functional Quantum Nodes for Entanglement Distribution over Scalable Quantum Networks”. In: Science 316.5829 (June 2007), pp. 1316–1320. doi: 10 . 1126 / science . 1140300.
[25]
C. W. Chou, H. de Riedmatten, D. Felinto, S. V. Polyakov, S. J. van Enk, and H. J. Kimble. “Measurement-induced entanglement for excitation stored in remote atomic ensembles”. In: Nature 438.7069 (Dec. 2005), pp. 828–832.
[26]
C. Cicconetti, M. Conti, and A. Passarella. “Request Scheduling in Quantum Networks”. en. In: IEEE Transactions on Quantum Engineering 2 (2021), pp. 2–17. issn: 2689-1808. doi: 10.1109/TQE.2021.3090532.
[38]
L.-M. Duan, M. D. Lukin, J. I. Cirac, and P. Zoller. “Long-distance quantum communication with atomic ensembles and linear optics”. In: Nature 414.6862 (Nov. 2001), pp. 413–418.
[27]
J. I. Cirac and P. Zoller. “Quantum Computations with Cold Trapped Ions”. In: Phys. Rev. Lett. 74 (20 May 1995), pp. 4091–4094. doi: 10.1103/PhysRevLett.74. 4091.
[39]
[28]
T. Coopmans, S. Brand, and D. Elkouss. “Improved analytical bounds on delivery times of long-distance entanglement”. In: Physical Review A 105.1 (Jan. 2022). issn: 2469-9934. doi: 10.1103/physreva.105.012608.
W. Dür, H.-J. Briegel, J. I. Cirac, and P. Zoller. “Quantum repeaters based on entanglement purification”. In: Physical Review A 59.1 (Jan. 1999). Publisher: American Physical Society, pp. 169–181. doi: 10 . 1103 / PhysRevA.59.169.
[40]
M. V. G. Dutt, L. Childress, L. Jiang, E. Togan, J. Maze, F. Jelezko, A. S. Zibrov, P. R. Hemmer, and M. D. Lukin. “Quantum Register Based on Individual Electronic and Nuclear Spin Qubits in Diamond”. In: Science 316.5829 (2007), pp. 1312–1316. doi: 10.1126/ science.1139831.
[41]
A. K. Ekert. “Quantum cryptography based on Bell’s theorem”. In: Phys. Rev. Lett. 67 (6 Aug. 1991), pp. 661– 663. doi: 10.1103/PhysRevLett.67.661.
[42]
S. Gauthier, G. Vardoyan, and S. Wehner. “An Architecture for Control of Entanglement Generation Switches in Quantum Networks”. In: IEEE Transactions on Quantum Engineering 4 (2023), pp. 1–17. doi: 10.1109/TQE.2023.3320047.
[43]
S. Gauthier, T. Vasantam, and G. Vardoyan. “OnDemand Resource Allocation for a Quantum Network Hub”. In: IEEE Transactions on Quantum Engineering 7 (2026), pp. 1–30. doi: 10.1109/TQE.2025.3641834.
[44]
J. Glaz and N. Balakrishnan, eds. Scan Statistics and Applications. Boston, MA: Birkhäuser Boston, 1999. isbn: 978-0-8176-4041-5. doi: 10.1007/978- 1- 46121578-3.
[45]
J. Glaz, J. I. Naus, and S. Wallenstein. Scan statistics. Springer series in statistics. New York: Springer, 2001. isbn: 978-0-387-98819-1.
[46]
K. Goodenough, T. Coopmans, and D. Towsley. “On noise in swap ASAP repeater chains: exact analytics, distributions and tight approximations”. In: Quantum 9 (May 2025), p. 1744. issn: 2521-327X. doi: 10.22331/ q-2025-05-15-1744.
[29]
[30]
[31]
[32]
J. P. Covey, H. Weinfurter, and H. Bernien. “Quantum networks with neutral atom processing nodes”. en. In: npj Quantum Information 9.1 (Sept. 2023). Number: 1 Publisher: Nature Publishing Group, pp. 1–12. issn: 2056-6387. doi: 10.1038/s41534-023-00759-9. A. Dahlberg, M. Skrzypczyk, T. Coopmans, L. Wubben, F. Rozpędek, M. Pompili, A. Stolk, P. Pawełczak, R. Knegjens, J. d. O. Filho, R. Hanson, and S. Wehner. “A Link Layer Protocol for Quantum Networks”. In: Proceedings of the ACM Special Interest Group on Data Communication. Aug. 2019, pp. 159–173. doi: 10.1145/ 3341302.3342070. S. Daiss, S. Langenfeld, S. Welte, E. Distante, P. Thomas, L. Hartung, O. Morin, and G. Rempe. “A quantum-logic gate between distant quantum-network modules”. In: Science 371.6529 (2021), pp. 614–617. doi: 10.1126/science.abe3150. eprint: https://www. science.org/doi/pdf/10.1126/science.abe3150. B. Davies, T. Beauchamp, G. Vardoyan, and S. Wehner. “Tools for the Analysis of Quantum Protocols Requiring State Generation Within a Time Window”. In: IEEE Transactions on Quantum Engineering 5 (2024), pp. 1– 20. doi: 10.1109/TQE.2024.3358674.
[33]
C. G. Davis. “An experimental pulse code modulation system for short-haul trunks”. In: The Bell System Technical Journal 41.1 (1962), pp. 1–24. doi: 10.1002/j. 1538-7305.1962.tb03261.x.
[34]
C. Delle Donne et al. “An operating system for executing applications on quantum network nodes”. In: Nature 639.8054 (Mar. 2025), pp. 321–328. doi: 10.1038/ s41586-025-08704-w.
[47]
D. Gottesman, T. Jennewein, and S. Croke. “LongerBaseline Telescopes Using Quantum Repeaters”. In: Phys. Rev. Lett. 109 (7 2012), p. 070503. doi: 10.1103/ PhysRevLett.109.070503.
[35]
D. Deutsch, A. Ekert, R. Jozsa, C. Macchiavello, S. Popescu, and A. Sanpera. “Quantum Privacy Amplification and the Security of Quantum Cryptography over Noisy Channels”. In: Physical Review Letters 77.13 (Sept. 1996), pp. 2818–2821. issn: 1079-7114. doi: 10. 1103/physrevlett.77.2818.
[48]
A. Gruber, A. Dräbenstedt, C. Tietz, L. Fleury, J. Wrachtrup, and C. von Borczyskowski. “Scanning Confocal Optical Microscopy and Magnetic Resonance on Single Defect Centers”. In: Science 276.5321 (1997), pp. 2012–2014. doi: 10.1126/science.276.5321.2012.
[36]
D. Ding and L. Jiang. Coordinating Decisions via Quantum Telepathy. arXiv:2407.21723. Sept. 2024. doi: 10. 48550/arXiv.2407.21723.
[49]
[37]
P. Drmota, D. Nadlinger, D. Main, B. Nichol, E. Ainley, D. Leichtle, A. Mantri, E. Kashefi, R. Srinivas, G. Araneda, C. Ballance, and D. Lucas. “Verifiable Blind Quantum Computing with Trapped Ions and Single Photons”. In: Physical Review Letters 132.15 (Apr. 2024). issn: 1079-7114. doi: 10 . 1103 / physrevlett . 132.150604.
H. Gu, R. Yu, Z. Li, X. Wang, and F. Zhou. “ESDI: Entanglement Scheduling and Distribution in the Quantum Internet”. In: 2023 32nd International Conference on Computer Communications and Networks (ICCCN) (2023), pp. 1–10. doi: 10 . 1109 / ICCCN58024 . 2023 . 10230193.
[50]
J. M. Halpern, R. HAAS, a. doria avri, L. Dong, W. Wang, H. M. Khosravi, J. H. Salim, and R. Gopal. Forwarding and Control Element Separation (ForCES) Protocol Specification. Request for Comments RFC 5810. Num Pages: 124. Internet Engineering Task Force, Mar. 2010. doi: 10.17487/RFC5810.
27
[51]
M. Hasanpour, S. Shariat, P. Barnaghi, S. A. Hoseinitabatabaei, S. Vahid, and R. Tafazolli. “Quantum load balancing in ad hoc networks”. en. In: Quantum Information Processing 16.6 (Apr. 2017), p. 148. issn: 15731332. doi: 10.1007/s11128-017-1578-y.
[62]
D. Kreutz, F. M. V. Ramos, P. E. Veríssimo, C. E. Rothenberg, S. Azodolmolky, and S. Uhlig. “SoftwareDefined Networking: A Comprehensive Survey”. In: Proceedings of the IEEE 103.1 (Jan. 2015), pp. 14–76. issn: 1558-2256. doi: 10.1109/JPROC.2014.2371999.
[52]
W. Hoeffding. “Probability Inequalities for Sums of Bounded Random Variables”. In: Journal of the American Statistical Association 58.301 (1963), pp. 13–30. doi: 10.1080/01621459.1963.10500830. eprint: https: //www.tandfonline.com/doi/pdf/10.1080/01621459. 1963.10500830.
[63]
V. Krutyanskiy, M. Canteri, M. Meraner, J. Bate, V. Krcmarsky, J. Schupp, N. Sangouard, and B. P. Lanyon. “Telecom-Wavelength Quantum Repeater Node Based on a Trapped-Ion Processor”. In: Phys. Rev. Lett. 130 (21 May 2023), p. 213601. doi: 10.1103/PhysRevLett. 130.213601.
[53]
M. Horodecki, P. Horodecki, and R. Horodecki. “General teleportation channel, singlet fraction, and quasidistillation”. In: Phys. Rev. A 60 (3 Sept. 1999), pp. 1888–1898. doi: 10.1103/PhysRevA.60.1888.
[64]
[54]
P. C. Humphreys, N. Kalb, J. P. J. Morits, R. N. Schouten, R. F. L. Vermeulen, D. J. Twitchen, M. Markham, and R. Hanson. “Deterministic delivery of remote entanglement on a quantum network”. In: Nature 558.7709 (June 2018). arXiv:1712.07567, pp. 268– 273. issn: 0028-0836, 1476-4687. doi: 10.1038/s41586018-0200-5.
V. Krutyanskiy, M. Galli, V. Krcmarsky, S. Baier, D. A. Fioretto, Y. Pu, A. Mazloom, P. Sekatski, M. Canteri, M. Teller, J. Schupp, J. Bate, M. Meraner, N. Sangouard, B. P. Lanyon, and T. E. Northup. “Entanglement of Trapped-Ion Qubits Separated by 230 Meters”. In: Phys. Rev. Lett. 130 (5 Feb. 2023), p. 050803. doi: 10.1103/PhysRevLett.130.050803.
[65]
T. van Leent, M. Bock, F. Fertig, R. Garthoff, S. Eppelt, Y. Zhou, P. Malik, M. Seubert, T. Bauer, W. Rosenfeld, W. Zhang, C. Becher, and H. Weinfurter. “Entangling single atoms over 33 km telecom fibre”. In: Nature 607.7917 (July 2022), pp. 69–73.
[66]
C. Liu, Z. Dutton, C. H. Behroozi, and L. V. Hau. “Observation of coherent optical information storage in an atomic medium using halted light pulses”. In: Nature 409 (2001), pp. 490–493. doi: 10.1038/35054017.
[67]
W.-Z. Liu et al. “Long-lived remote ion-ion entanglement for scalable quantum repeaters”. In: Nature (Feb. 2026). doi: 10.1038/s41586-026-10177-4.
[68]
S. Maiti, G. Avis, S. Kar, and S. Wehner. Requirements for Teleportation in an Intercity Quantum Network. 2026. arXiv: 2602.04869.
[69]
P. Maunz, D. L. Moehring, S. Olmschenk, K. C. Younge, D. N. Matsukevich, and C. Monroe. “Quantum interference of photon pairs from two remote trapped atomic ions”. In: Nature Physics 3.8 (2007), pp. 538–541.
[70]
N. McKeown, T. Anderson, H. Balakrishnan, G. Parulkar, L. Peterson, J. Rexford, S. Shenker, and J. Turner. “OpenFlow: enabling innovation in campus networks”. en. In: ACM SIGCOMM Computer Communication Review 38.2 (Mar. 2008), pp. 69–74. issn: 01464833. doi: 10.1145/1355734.1355746.
[71]
M. Michler, K. Mattle, H. Weinfurter, and A. Zeilinger. “Interferometric Bell-state analysis”. In: Physical Review A 53.3 (1996), R1209.
[72]
J. I. Naus. “Approximations for Distributions of Scan Statistics”. In: Journal of the American Statistical Association 77.377 (1982). Publisher: [American Statistical Association, Taylor & Francis, Ltd.], pp. 177–183. issn: 0162-1459. doi: 10.2307/2287786.
[73]
C. T. Nguyen, D. D. Sukachev, M. K. Bhaskar, B. Machielse, D. S. Levonian, E. N. Knall, P. Stroganov, R. Riedinger, H. Park, M. Lon čar, and M. D. Lukin. “Quantum Network Nodes Based on Diamond Qubits with an Efficient Nanophotonic Interface”. In: Phys. Rev. Lett. 123 (18 Oct. 2019), p. 183602. doi: 10.1103/ PhysRevLett.123.183602.
[74]
L. Peterson and B. Davie. Computer Networks: A Systems Approach. Open-source edition available at https: //book.systemsapproach.org/, licensed under CC BY 4.0. Elsevier, 2012. Chap. 2.5.
[55]
[56]
Á. G. Iñesta, G. Vardoyan, L. Scavuzzo, and S. Wehner. “Optimal entanglement distribution policies in homogeneous repeater chains with cutoffs”. en. In: npj Quantum Information 9.1 (May 2023). Number: 1 Publisher: Nature Publishing Group, pp. 1–7. issn: 2056-6387. doi: 10.1038/s41534-023-00713-9. R. Jain. “Congestion control and traffic management in ATM networks: Recent advances and a survey”. In: Computer Networks and ISDN Systems 28.13 (1996). ATM/NII, pp. 1723–1738. issn: 0169-7552. doi: https: //doi.org/10.1016/0169-7552(96)00012-8.
[57]
C. Jones, D. Kim, M. T. Rakher, P. G. Kwiat, and T. D. Ladd. “Design and analysis of communication protocols for quantum repeater networks”. In: New Journal of Physics 18.8 (Aug. 2016), p. 083015. doi: 10.1088/ 1367-2630/18/8/083015.
[58]
C. Jones, D. Kim, M. T. Rakher, P. G. Kwiat, and T. D. Ladd. “Design and analysis of communication protocols for quantum repeater networks”. In: New Journal of Physics 18.8 (Aug. 2016), p. 083015. doi: 10.1088/ 1367-2630/18/8/083015.
[59]
N. Joukov, A. Traeger, R. Iyer, C. P. Wright, and E. Zadok. “Operating system profiling via latency analysis”. In: Proceedings of the 7th Symposium on Operating Systems Design and Implementation. OSDI ’06. Seattle, Washington: USENIX Association, 2006, pp. 89– 102. isbn: 1931971471.
[60]
[61]
P. Kómár, E. M. Kessler, M. Bishof, L. Jiang, A. S. Sørensen, J. Ye, and M. D. Lukin. “A quantum network of clocks”. In: Nature Physics 10.8 (June 2014), pp. 582– 587. issn: 1745-2481. doi: 10.1038/nphys3000. W. Kozlowski, F. Kuipers, and S. Wehner. “A P4 Data Plane for the Quantum Internet”. In: Proceedings of the 3rd P4 Workshop in Europe. CoNEXT ’20: The 16th International Conference on emerging Networking EXperiments and Technologies. Barcelona Spain: ACM, Dec. 2020, pp. 49–51. isbn: 978-1-4503-8181-9. doi: 10.1145/ 3426744.3431321.
28
[75]
D. F. Phillips, A. Fleischhauer, A. Mair, R. L. Walsworth, and M. D. Lukin. “Storage of Light in Atomic Vapor”. In: Physical Review Letters 86.5 (2001), pp. 783–786. doi: 10.1103/PhysRevLett.86.783.
[76]
A. Pirker and W. Dür. “A quantum network stack and protocols for reliable entanglement-based networks”. In: New Journal of Physics 21.3 (Mar. 2019). Publisher: IOP Publishing, p. 033003. issn: 1367-2630. doi: 10 . 1088/1367-2630/ab05f7.
[77]
[78]
M. Pompili, C. Delle Donne, I. te Raa, B. van der Vecht, M. Skrzypczyk, G. Ferreira, L. de Kluijver, A. J. Stolk, S. L. N. Hermans, P. Pawełczak, W. Kozlowski, R. Hanson, and S. Wehner. “Experimental demonstration of entanglement delivery using a quantum network stack”. en. In: npj Quantum Information 8.1 (Oct. 2022). Number: 1 Publisher: Nature Publishing Group, pp. 1–10. issn: 2056-6387. doi: 10.1038/s41534-022-00631-2. M. Pompili, S. L. N. Hermans, S. Baier, H. K. C. Beukers, P. C. Humphreys, R. N. Schouten, R. F. L. Vermeulen, M. J. Tiggelman, L. dos Santos Martins, B. Dirkse, S. Wehner, and R. Hanson. “Realization of a multinode quantum network of remote solid-state qubits”. In: Science 372.6539 (Apr. 2021). Publisher: American Association for the Advancement of Science, pp. 259–264. doi: 10.1126/science.abg1919.
[88]
S. Tani, H. Kobayashi, and K. Matsumoto. “Exact Quantum Algorithms for the Leader Election Problem”. en. In: ACM Transactions on Computation Theory 4.1 (Mar. 2012), pp. 1–24. issn: 1942-3454, 1942-3462. doi: 10.1145/2141938.2141939.
[89]
J. Tucker, P. Strange, P. Mironowicz, and J. Quintanilla. “Quantum-assisted rendezvous on graphs: explicit algorithms and quantum computer simulations”. In: New Journal of Physics 26.9 (Sept. 2024), p. 093038. issn: 1367-2630. doi: 10.1088/1367-2630/ad78f8.
[90]
W. G. Unruh. “Maintaining coherence in quantum computers”. In: Phys. Rev. A 51 (2 Feb. 1995), pp. 992–997. doi: 10.1103/PhysRevA.51.992.
[91]
M. Uphoff, M. Brekenfeld, G. Rempe, and S. Ritter. “An integrated quantum repeater at telecom wavelength with single atoms in optical fiber cavities”. In: Applied Physics B 122.3 (Mar. 2016). issn: 1432-0649. doi: 10. 1007/s00340-015-6299-2.
[92]
R. Van Meter, R. Satoh, N. Benchasattabuse, T. Matsuo, M. Hajdušek, T. Satoh, S. Nagayama, and S. Suzuki. “A Quantum Internet Architecture”. In: 2022 IEEE International Conference on Quantum Computing and Engineering (QCE). arXiv:2112.07092. Sept. 2022, pp. 341–352. doi: 10 . 1109 / QCE53715 . 2022 . 00055.
[79]
M. Ruf, N. H. Wan, H. Choi, D. Englund, and R. Hanson. “Quantum networks based on color centers in diamond”. In: Journal of Applied Physics 130.7 (Aug. 2021), p. 070901. issn: 0021-8979. doi: 10 . 1063 / 5 . 0056534.
[93]
R. Van Meter, T. Satoh, T. D. Ladd, W. J. Munro, and K. Nemoto. “Path Selection for Quantum Repeater Networks”. In: Networking Science 3.1-4 (Dec. 2013). arXiv:1206.5655, pp. 82–95. issn: 2076-0310, 2076-0329. doi: 10.1007/s13119-013-0026-2.
[80]
N. Sangouard, R. Dubessy, and C. Simon. “Quantum repeaters based on single trapped ions”. In: Phys. Rev. A 79 (4 Apr. 2009), p. 042340. doi: 10.1103/PhysRevA. 79.042340.
[94]
[81]
N. Sangouard, C. Simon, H. de Riedmatten, and N. Gisin. “Quantum repeaters based on atomic ensembles and linear optics”. In: Rev. Mod. Phys. 83 (1 Mar. 2011), pp. 33–80. doi: 10.1103/RevModPhys.83.33.
G. Vardoyan, S. Guha, P. Nain, and D. Towsley. “On the Exact Analysis of an Idealized Quantum Switch”. In: SIGMETRICS Perform. Eval. Rev. 48.3 (Mar. 2021), pp. 79–80. issn: 0163-5999. doi: 10 . 1145 / 3453953 . 3453971.
[95]
B. van der Vecht, A. T. Yücel, H. Jirovská, and S. Wehner. Qoala: an Application Execution Environment for Quantum Internet Nodes. arXiv:2502.17296. Feb. 24, 2025. doi: 10.48550/arXiv.2502.17296. arXiv: 2502. 17296.
[96]
G. Viola and P. Mironowicz. “Quantum strategies for rendezvous and domination tasks on graphs with mobile agents”. In: Physical Review A 109.4 (Apr. 2024). issn: 2469-9934. doi: 10.1103/physreva.109.042201.
[97]
P. Walther and A. Zeilinger. “Experimental realization of a photonic Bell-state analyzer”. In: Physical Review A 72.1 (2005), p. 010302. doi: https://doi.org/10. 1103/PhysRevA.72.010302.
[98]
A. Waters and K. Ab-Hamid. “Congestion control for frame relay networks”. In: IEE Colloquium on Frame Relay. 1992, pp. 3/1–3/4.
[99]
S.-y. Yu, E. Perego, J. Phillips, Y.-W. Cheah, P. Umesh, G. Gao, J. Liu, E. Kissel, M. Bregar, K. Sun, Q. Wu, R. Valivarthi, E. Saglamyurek, W. Wu, M. Spiropulu, H. Häffner, and I. Monga. “A Two-Level Control Framework for Quantum Networks”. In: 2025 IEEE International Conference on Quantum Computing and Engineering (QCE). Vol. 01. 2025, pp. 1302–1311. doi: 10. 1109/QCE65121.2025.00145.
[82]
[83]
[84]
[85]
T. Sekimoto and J. Puente. “A Satellite Time-Division Multiple-Access Experiment”. In: IEEE Transactions on Communication Technology 16.4 (1968), pp. 581– 588. doi: 10.1109/TCOM.1968.1089895. C. Simon, H. de Riedmatten, M. Afzelius, N. Sangouard, H. Zbinden, and N. Gisin. “Quantum Repeaters with Photon Pair Sources and Multimode Memories”. In: Phys. Rev. Lett. 98 (19 May 2007), p. 190503. doi: 10.1103/PhysRevLett.98.190503. M. Skrzypczyk and S. Wehner. An Architecture for Meeting Quality-of-Service Requirements in Multi-User Quantum Networks. arXiv:2111.13124. Nov. 2021. K. Steenhaut, K. Degieter, W. Brissinck, and E. Dirkx. “Scheduling and admission control policies: A case study for ATM”. In: Computer Networks and ISDN Systems. Signaling and Management of ATM Networks 29.5 (Apr. 1, 1997), pp. 539–554. issn: 0169-7552. doi: 10.1016/S0169-7552(96)00118-3.
[86]
A. S. Tanenbaum. Modern Operating Systems. second. Upper Saddle River, NJ, USA: Prentice Hall PTR, 2001.
[87]
A. S. Tanenbaum. Computer Networks. 4th. Upper Saddle River, New Jersey: Prentice Hall PTR, 2003, p. 912. isbn: 978-0130661029.
29
[100]
R. Zhao, Y. O. Dudin, S. D. Jenkins, C. J. Campbell, D. N. Matsukevich, T. A. B. Kennedy, and A. Kuzmich. “Long-lived quantum memory”. In: Nature Physics 5 (2 Feb. 2009), pp. 100–104. doi: 10.1038/nphys1152.
[101]
H. Zimmermann. “OSI Reference Model - The ISO Model of Architecture for Open Systems Interconnection”. In: IEEE Transactions on Communications 28.4 (1980), pp. 425–432. doi: 10.1109/TCOM.1980.1094702.
[102]
W. H. Zurek. “Environment-induced superselection rules”. In: Phys. Rev. D 26 (8 Oct. 1982), pp. 1862– 1880. doi: 10.1103/PhysRevD.26.1862.
Appendices A.
Notation
The notation used throughout this paper is summarized in Table 4.
B.
Network Scheduler Algorithms
In this appendix we provide pseudocode algorithms for all processes of the Network Scheduler for which an algorithm is specified in the main text. These are as follows: – UpdateFillingClasses, Algorithm 4 for Update Filling Classes. – AdmitTasks, Algorithm 5 for Admit Tasks. – DirectAllocation, Algorithm 6, which implements the inner loop of the minimal allocation phase of Compute Schedule. – BonusRoundRobin, Algorithm 7, which implements the inner loop of the bonus allocation phase of Compute Schedule. – nextStartTime, allResourcesAvailable and getLeft[Right]MinsepViolations are all in Algorithm 8. These functions are used by the BonusRoundRobin algorithm to determine whether additional PGAs can be added to a network schedule.
30
Algorithm 4: Algorithm for Update Filling Classes. The functions BuildFillingClasses, AssignFillingClass, and ApplyRuleMissingPath may be re-defined by an implementation, or they may follow the default implementation of Section VI. Function UpdateFillingClasses: Input : Set of filling classes Ψ = {Zψ , Πψ }ψ , Path partition Π, Set of terminated PGTs τ . Output: Updated set of filling classes Φ = {Zϕ , Πϕ }ϕ , Mapping of associated resources ξ. Set Γ∗ ← ∅ ; Set Φ, ξ ← BuildFillingClasses(Z = ∅, Π) ; for ψ ∈ Ψ do for γ ∈ Zψ do ≤ CurrentTime if γ ∈ τ or texpiry γ then continue; end if ∃ϕ s.t. πγ ∈ Πϕ then Set Φ ← AssignFillingClass(γ, Φ); else Set Γ∗ ← Γ∗ ∪ γ ; end end end for γ ∈ Γ∗ do Set Φ ← ApplyRuleMissingPath(γ, Φ) ; end end return Φ, ξ;
Symbol S N N inst texpiry p = (w, s, F ) tminsep d = (draw , Md ) ϵservice d γ Eγ ppacket γ tstart γ δ(γ, t; r) G = (V, E) E⊂V I⊂V J ⊂V B⊂V R=I ⊔J ⊔B R = |R| L ∗ E ⊂E π = (π0 , · · · , πk ) Pvalid Pallowed ⊂ Pvalid Π = {Πϕ } τ Γ Γd ⊆ Γ k = |Γ| S T SI tcompute Φ ϕ = (Zϕ , Πϕ ) ZΦ N = |ZΦ | ξ
Definition Applications An application session A set of end nodes which hosts an application session A number of application instances required to complete an application session The expiry time of an application session and demand Demands A packet of s end-to-end links to be generated within time window w, with minimum fidelity F A minimum required time separation between attempts to generate a packet The full demand consists of the raw demand draw and demand metadata Md The service error parameter for a demand d Packet Generation Tasks A PGT The duration of PGAs for the PGT γ The probability a PGA of duration Eγ successfully produces the required packet of links The earliest time that a PGA for a PGT γ could be scheduled if it is accepted A PGA for a PGT γ scheduled at time t on resource r Network Topology and Components A network resource graph with vertices V and edges E The set of end nodes The set of entanglement generation interfaces The set of junction nodes The set of long-distance backbones Set of all internal resources in a network Number of internal resources in a network The set of local areas of G A set of allowed edges of a network resource graph G Paths a path through the network resource graph from source node π0 to destination node πk The set of valid entanglement generation paths A set of allowed paths, further restricted from the set of valid paths A disjoint partition of Pvalid or Pallowed Demand Manager The demand termination buffer The PGT intake buffer A set of PGTs in the task intake buffer which can realize a demand d Number of PGTs in the task intake buffer Network Scheduler A network schedule The duration of a scheduling interval The computation time of the Network Schedule application The set of filing classes A filling class based on the cell of the path partition Πϕ so that πγ ∈ Πϕ ∀γ ∈ Zϕ The set of all active PGTs Number of active PGTs Mapping from a set of paths to the associated internal resources
Table 4: Summary of the notation used throughout this paper. The notation f [i] indicates the ith entry of a vector, tuple, matrix or dictionary-like object f .
31
Algorithm 5: The Admit Tasks process of the Network Scheduler is implemented by the function AdmitTasks. The helper function GetFillingClass returns the filling class of a task if it exists, or else it raises a FillingClassError. The function CalculateRequiredTime is defined in Algorithm 2. Function AdmitTasks: Input : Task Intake Object Γ, Set of filling classes Φ = {Zϕ , Πϕ }ϕ , Set of live network resources R. Output: Set of Filling classes Φ, List of accepted PGTs A. Set Tξr ← T SI for r ∈ R ; for ϕ ∈ Φ do R(Zϕ ) = CalculateRequiredTime(Zϕ ) ; for r ∈ ξ(Πϕ ) do Set Tξr ← Tξr − R(Zϕ ) ; end end while Γ ̸= 0 do Set Γd ← Γ[0] ; while Γd ̸= 0 do Set γ ← Γd [0] ; try: Set ϕ ← GetFillingClass(γ) ; except FillingClassError: Set Γd ← Γd \ γ ; continue; end Set Z̃ϕ ← Zϕ + γ; Set Accept ← True ; Set Tξr ← Tξr + R(Zϕ ) for r ∈ ξ(Πϕ ) ; Set R(Z˜ϕ ) ← CalculateRequiredTime(Z˜ϕ ) ; for r ∈ ξ(Πϕ ) do if Tξr − R(Z˜ϕ ) < 0 then Set Accept ← False ; Set Γd ← Γd \ γ ; if Γd = 0 then Set Γ ← Γ \ Γd ; end break; end end if Accept then Set A ← A + γ ; Set Zϕ ← Z˜ϕ ; Set R(Zϕ ) ← R(Z˜ϕ ) ; Set Tξr ← Tξr − R(Zϕ ) for r ∈ ξ(Πϕ ) ; Set Γ ← Γ \ Γd ; break; end end end return Φ, A end
32
Algorithm 7: Algorithm for the inner loop of the bonus allocation phase of Compute Schedule. Z|ϕ|,k = {k, k + 1, ..., |ϕ| − 1, 0, 1, ..., k − 1)}. δ(γ, t; r) is a PGA for a PGT γ scheduled at time t on resource r. The subroutines nextStartTime, allResourcesAvailable and getLeft[Right]MinsepViolations are specified in Algorithm 8.
Algorithm 6: Scheduler for direct allocation of PGA start times for all PGTs in a single filling class ϕ. NxSI is the number of PGAs, each with duration Ex , of PGT γx that need to be scheduled. Function DirectAllocation: Input : Filling class ϕ = Zϕ , Πϕ with Zϕ = (γ0 , ..., γM −1 ), network schedule S, start time t0 . Output: Updated network schedule S. Order PGTs γ ∈ Zϕ by a set of indices SI X = {1, · · · , |Zϕ |} such that NxSI ≤ Nx+1 Set M ← |Zϕ | Set cx← PM max max Ey + tminsep , E y y=x y ;
Function RoundRobinBonus: Input : Filling class ϕ, network schedule S. Output: Updated network schedule S. Set T rel ← {}; Set test ← nextStartTime(S, T rel , 0); Set k ← 0; while test < T SI do for i ∈ Z|ϕ|,k do Set Cresource ← allResourcesAvailable(γi , test ; S) Set VLM S ← getLeftMinsepViolations(γi , test ; S) Set VRM S ← getRightMinsepViolations(γi , test ; S) Set Cminsep ← VLM S ∪ VRM S = ∅; if Cresource ∧ Cminsep ∧ test + Eγi < T SI then for r ∈ πγi do Add PGA δ(γi , test ; r) to Sr ; end Set k ← i; else if VLM S ̸= ∅ then minsep Append maxδ∈VLM S (tend ) to δ ∗ + t γi rel T end end Set test ← nextStartTime(S, T rel , test ); end end
y∈{x,···M }
SI Set nx ← NxSI − Nx−1 for x ≥ 1; SI Set n0 ← N0 − 1; Set tstart ← t0 ; for m = 0, ..., M − 1 do for k = 0, ..., nm − 1 do for x = m, ..., MP − 1 do x Set toffset ← y=m Ey ; for r ∈ πγx do Add PGA δ(γx , tstart + kcm + toffset ; r) to S[r]; end end end for r ∈ πγx do Add PGA δ(γm , tstart + nm cm ; r) to S[r]; end Set tstart ← tstart + nm cm + Em ; end end
33
Algorithm 8: Auxiliary algorithms used in BonusRoundRobin, Algorithm 7. Function nextStartTime: Input : Network Schedule S, list of release times T̂ rel , current time t Output:S next possible start time test , updated set of release times T rel ′ Set S = r∈R {δ ∈ Sr : tend > t}; δ ′ rel if S = ∅ ∧ T̂ = ∅ then return ∞ end Set ts = min{tend : δ ∈ S ′ }; δ Set tr = min T̂ rel ; if tr ≤ ts then Set T rel ← T̂ rel \ tr ; end return min{ts , tr }, T rel ; end Function allResourcesAvailable: Input : PGT γ, time t, network schedule S Output: boolean for r ∈ πγ ∩ R do if r is not available in [t, t + Eγ ) then return False end ; end return True; end Function getLeftMinsepViolations: Input : PGT γ, time t, network schedule S Output: set of conflicting PGAs, VLM S Set VLM S ← ∅; for r ∈ πγ ∩ R do minsep Set S ′ ← {δ ∈ Sr : [tstart , tend , t] ̸= ∅}; δ δ ) ∩ (t − tγ MS MS ′ Set VL ← VL ∪ {δ ∈ S : demandID(δ) = demandID(γ)}; end return VLM S ; end Function getRightMinsepViolations: Input : PGT γ, time t, network schedule S Output: set of conflicting PGAs, VRM S Set VLM S ← ∅; for r ∈ πγ ∩ R do minsep Set S ′ ← {δ ∈ Sr : [tstart , tend ) ̸= ∅}; δ δ ) ∩ (t, t + tγ Set VRM S ← VRM S ∪ {δ ∈ S ′ : demandID(δ) = demandID(γ)}; end return VRM S ; end
34
As the ordering ≥ξ is only a partial order, there may exist non-comparable elements of Φ using ≥ξ . In particThe main goal of this Appendix is to prove Theorem V.2, ular, if ξ(Πψ ) ∩ ξ(Πϕ ) = ∅ then ψ and ϕ do not have a which is a statement about the performance of the Net- determinate order under ≥ξ . work Scheduler control application. To prove this theoRecall that the network resource graph G, from which rem, we first develop a series of intermediate results which the set of valid paths Pvalid and the path partition Π of support the final analysis. This section is organized as Pvalid are derived, may have the property of being interfollows: nally connected. In that case we write that the path partition Π describes an internally connected network. 1. We define a method of comparing filling classes and a well-behaved property for an abstract set of filling Definition 15 (Well-behaved set of filling classes). Let classes. Subsequent results for the performance of the Φ = {ϕ0 , ϕ1 , ..., ϕn−1 } be a set of filling classes defined by Admit Tasks and Compute Schedule processes require the path partition Π. Let ξ be the mapping of between a an abstract set of filling classes to have this property. set of paths and their associated resources. We say that Φ is well-behaved if the following conditions are met: 2. We define sequentially valid schedules, define condi1. ∀i ̸= j, ξ(Πϕi ) ̸= ξ(Πϕj ) tions under which a schedule for a single filling class 2. ∀i ̸= j, ξ(Πϕi ) ∩ ξ(Πϕj ) ̸= ∅ =⇒ ξ(Πϕi ) ⊂ ξ(Πϕj ) ∨ may be guaranteed to be sequentially valid, and we ξ(Πϕj ) ⊂ ξ(Πϕi ). calculate the required duration of sequentially valid With the ordering ≤ξ , condition 2. may be re-stated as: schedules for a single filling class.
C.
Performance Analysis
2’. ∀i ̸= j, ξ(Πϕi ) ∩ ξ(Πϕj ) ̸= ∅ =⇒ ϕj >ξ ϕi ∨ ϕi >ξ ϕj .
3. We define valid schedules and prove that the compute schedule process produces valid schedules.
These conditions ensure that firstly no two filling classes 4. We prove that the admission control process is sound, can be associated with exactly the same set of resources meaning that newly accepted demands do not disrupt and secondly that if there is any overlap of associated resources between filling classes then the filling classes are existing service agreements (C3). comparable. 5. We prove Theorem V.2. Lemma C.2. Let the path partition Π describe an internally connected network. Let C.i. Filling Classes Φ = {ϕn−1 , ϕn−2 , · · · , ϕ1 , ϕ0 } be a well-behaved set of filling classes defined by Π. Then under ≤ξ as in In this section we first prove that each PGT is only in a Definition 14, there is a unique greatest element of Φ. single filling class, as long as the path partition Π which defines Φ is disjoint. This result is used later in the proof Proof. The existence of a path partition Π with at least of C.4. We then build up towards defining a well-behaved one cell in the partition defines a set of filling classes with property for an abstract set of filling classes, required by at least one filling class. In the case that the partition has Theorem V.2. As a pre-curser, we define a method of com- only a single cell Π0 , then there is a single filling class ϕ0 , paring filling classes, ≤ξ . Finally in this section we prove and ϕ0 is a unique greatest element of Φ. Suppose therefore that the path partition has n > 1 that a well-behaved set of filling classes in an internally cells, and therefore defines a set of n > 1 filling classes connected network has a unique greatest element under Φ. For the sake of contradiction, suppose Φ has no unique the ordering ≤ξ . This result is used later in the proof of greatest element. Theorem C.7. Then there exists i, j such that there is no k satisfying Lemma C.1. Let Π = {Πϕ } be a disjoint path partition ϕk >ξ ϕi and ϕk >ξ ϕj . Such ϕi , ϕj are greatest elements and Φ the set of filling classes defined by Π. Let Z be a set of Φ. As ϕ is well-behaved, we must have that ϕi and ϕj of PGTs such that ∀γ ∈ Z, ∃ϕ ∈ Φ s.t. πγ ∈ Πϕ . Then, are incomparable under ≥ξ and so ξ(Πϕi ) ∩ ξ(Πϕj ) = ∅. {Zϕ } is a disjoint partition of Z. As Π describes an internally connected network, there exists some path π ∗ which passes through nodes in ξ(Πϕi ) Proof. (Disjointedness) Suppose ∃γ ∈ Z such that γ ∈ Zϕ and nodes in ξ(Πϕj ). As Π is a disjoint partition, there and γ ∈ Zψ . This implies that πγ ∈ Πϕ and πγ ∈ Πψ , exists a unique k ∗ such that π ∗ ∈ Πϕ ∗ . As π ∗ passes k which implies Πϕ ∩ Πψ ̸= ∅. This contradicts that Π is a through nodes in ξ(Πϕi ), we must have that ξ(Πϕ ∗ ) ∩ k disjoint partition and so no such γ may exist. ξ(Πϕi ) ̸= ∅. As Φ is well-behaved, this implies that either ξ(Πϕi ) ⊂ ξ(Πϕk∗ ) or ξ(Πϕk∗ ) ⊂ ξ(Πϕi ). If the former case (Completeness) By the hypothesis, ∀γ ∈ Z, ∃ϕ ∈ Φ such holds, then ϕk∗ >ξ ϕi , contradicting that ϕi is a greatest that πγ ∈ Πϕ . Hence every γ ∈ Z is a member of some element of Φ. If the latter case holds, then ξ({π ∗ }) ⊆ Zϕ . ξ(Πϕk∗ ) ⊂ ξ(Πϕi ). However, as ξ({π ∗ }) ∩ ξ(Πϕj ) ̸= ∅, then ξ(Πϕi ) ∩ ξ(Πϕj ) ̸= ∅ contradicting that ϕi and ϕj are Definition 14 (Comparison of filling classes). We define incomparable under ≥ξ . a partial order on Φ by ϕ >ξ ψ ⇔ ξ(Πψ ) ⊂ ξ(Πϕ ), with The same logic applies symmetrically to ϕj , and thereequality iff ξ(Πψ ) = ξ(Πϕ ). fore no such i, j can exist and the result holds. 35
Proof. By the hypothesis, the schedule S contains exactly N PGAs of each γ ∈ Zϕ . Suppose j ≤ N − 2. Beginning In the following, we first introduce a property called a minfrom s0,j , the start time of the j th PGA of PGT γ0 , resep violation. We then make use of this property to define peated application of conditions c1 and c2 generate the a sequentially valid schedule for a single filling class. We sequence of start and end times of the j th PGAs of each then prove that a scheduling method that adheres to three PGT γx , simple conditions produces sequentially valid schedules for x−1 a single filling class. X sx,j = s0,j + Eγy , ∀x ≥ 1, (27) Definition 16 (Minsep violation). Let S be a schedule for y=0 filling class ϕ with Zϕ = {γ0 , · · · , γM −1 } with start times x X sx,i and end times ex,i for the ith scheduled PGA of PGT ex,j = s0,j + Eγy , ∀x ≥ 0. (28) γx , where x ∈ {0, · · · , M − 1}. We say a minsep violay=0 tion occurs in S if ∃x, i such that sx,i+1 − ex,i < tminsep . γx (⇒) Suppose the schedule S has properties c1 and c2 of Definition 17 (Sequentially valid). A schedule is said to a sequentially valid schedule. By (24), the start time for be sequentially valid if it has the following two proper- the (j +1)th PGA of PGT γ0 must satisfy s0,j+1 ≥ eM −1,j . ties: By (28), that is 1. No two PGAs are scheduled simultaneously, and M −1 X s0,j+1 ≥ s0,j + Eγy . (29) 2. No minsep violations occur. C.ii.
Schedules for a Single Filling Class
y=0
We now define two simple conditions on the start and end times of PGAs in a network schedule that are com- By (25), ∀x ≥ 0, patible with sequentially valid schedules. s
(30) Definition 18 (First and Second Sequential Scheduling Combining (27) and (30), ∀x ≥ 1, Conditions). Let S be a schedule for an arbitrary filling x−1 x−1 class ϕ = (Zϕ , Πϕ ), populated by PGTs Zϕ = {γx }x . Let X X Eγx ) ≥ Eγx + tminsep Eγx − (s0,j + s0,j+1 + sx,i and ex,i denote the start and end times, respectively, γx y=0 y=0 for the ith PGA from PGT γx . Let Eγx denote the execution time of a PGA for PGT γx . The sequential s0,j+1 − s0,j ≥ Eγx + tminsep (31) γx scheduling conditions are, Combining (30), which holds for x ≥ 0 and (31), which (Condition c1 ): holds for x ≥ 1, ex,i = sx,i + Eγx , ∀x ≥ 0, (24) s0,j+1 − s0,j ≥ max(Eγx + tminsep ). (32) γx x and, (Condition c2 ): The combined requirement from (29) and (32) is, minsep . x,j+1 − sx,j ≥ Eγx + tγx
sx,i = ex−1,i , ∀x ≥ 1. C.ii.a.
(25)
s0,j+1 − s0,j ≥ max
Calculating the required duration of sequentially valid schedules
max(Eγx + tminsep ), γx x
(⇐) Suppose the start ∀i ∈ {0, · · · , N − 2} satisfy (26). It follows from (26) and (28),
M −1 X
Eγy .
y=0
times
s0,i , s0,i+1
Lemma C.3. Let ϕ = (Zϕ , Πϕ ) with Zϕ = {γ0 , ..., γM −1 } be a filling class such that ∀γ ∈ Zϕ , the minimum alM −1 X location satisfies NγSI = N . Let S be a schedule for ϕ s0,j+1 ≥ Eγx + s0,j satisfying the sequential scheduling conditions, (24) and y=0 (25). The schedule S is sequentially valid if and only if s0,j+1 ≥ eM −1,j . (33) ∀i = 0, ..., N − 2: Condition c2 guarantees that the j th PGAs of any PGT are X s0,i+1 − s0,i ≥ max max Eγ + tminsep , E . γ non-overlapping. Then, (33) guarantees that the (j + 1)th γ γ∈Zϕ γ∈Zϕ and j th PGAs of any PGT are non-overlapping. Since j (26) is arbitrary, it follows that S has property c1 . In consideration of property c2 , it follows from (26) that, Once the start time of the very first PGA of PGT γ is 0
known, conditions (24) and (25) define a method of adding the ith PGA of PGTs γx = {γ1 , · · · , γM −1 } to a schedule, but these conditions do not specify how to add the (i+1)th PGA of PGT γ0 to the schedule. For that, (26) is required to ensure the schedule produced is sequentially valid. The very first PGA of PGT γ0 can be added at an arbitrary start time t0 .
36
s0,j+1 ≥ max(Eγy + tminsep ) + s0,j . γy y≥0
(34)
Combination of (27) for sx,j+1 with (34) gives, sx,j+1 ≥ max(Eγy + tminsep ) + s0,j + γy y≥0
x−1 X y=0
Eγy ,
(35)
γ0 γ1 .. .
γk−1 γk γk+1 .. . γM −1
..
..
.
..
t0
..
.
..
.
M −1 P
..
. n0 · c 0
Ey c0
y=0
..
.
.
.
c1 + E 0 + n 0 · c 0
t
E0 + n0 · c0
Figure 13: Example DirectAllocation schedule for a filling class ϕ populated by PGTs Zϕ = {γ0 , γ1 , · · · , γM −1 }. In this example, N0SI = 3, hence task γ0 drops out after n0 = 2 executions of cycle c0 . Then, one final PGA for γ0 is scheduled. All other PGTs γx in the example satisfy NxSI > 4, hence they occur in at least two executions of cycle c1 . Here also it is illustrated that in cycle c0 , task γ0 is the task which satisfies the maximum in (48), hence the amount of idle time inserted in c1 differs from that inserted in c0 . which holds for x ≥ 1. Subtracting (28) from (35), for let sx,i and ex,i identify the start and end times of the ith PGA of PGT γx added to the schedule. When the ith x ≥ 1 gives PGA of PGT γx is added to the schedule, the start and sx,j+1 − ex,j ≥ max(Eγy + tminsep ) − E γx end times are specified by condition c1 of Lemma C.3, γy y≥0 ≥ tminsep . γx
(36)
ex,i = sx,i + Eγx , ∀x ∈ {0, · · · , M − 1}.
(38)
Similarly, for x = 0, subtracting (28) for e0,j from (34) Let the term cycle 0 refer to a schedule consisting of the gives, ) according to ith PGA from each PGT γx ∈ ϕ (i ≤ NγSI 0 (38) and the second sequential scheduling condition (25), s0,j+1 − e0,j ≥ max(Eγy + tminsep ) − E γ0 γy y≥0 sx,i = ex−1,i , ∀x ∈ {0, · · · , M − 1}. (39) ≥ tminsep . (37) γ0 Let cycle 0 also include an idle time of duration I0 followSince j is arbitrary, it follows that S has property c2 , no ing the ith PGA of PGT γM −1 , so that minsep violations occur in S. M −1 X s0,i+1 = s0,i + Ey + I 0 . (40) Proposition C.4. Let ϕ = (Zϕ , Πϕ ) be a filling class. y=0 Let R(Zϕ ) = CalculateRequiredTime(Zϕ ) denote the output of Algorithm 2. Then, R(Zϕ ) is an upper bound for Note that cycle 0 has the property that no two PGAs are the minimum time required to execute a sequentially valid scheduled simultaneously. By the hypothesis, supposing schedule which contains NγSI PGAs of every PGT γ ∈ Zϕ . that the required network resources to execute a PGA are Wherever it is relevant to do so, throughout the proof of Proposition C.4 we refer to Figure 13. Note that the Figure is not required for any of the arguments in the proof. The Figure simply provides a visual illustration of the concepts introduced in the proof, easing their comprehension. Proof. To upper bound the minimum amount of time required to execute NγSI PGAs of every PGT γ ∈ Zϕ such that no two PGAs are scheduled simultaneously and no minsep violations occur, it is sufficient to account for the time required, R, to execute a specific schedule that meets these criteria. We first describe a method of scheduling PGAs based on the conditions in Lemma C.3 and which leverages the possibility of inserting idle time into a schedule. We then demonstrate that this method of scheduling results in a particularly simple calculation of the required time R. Let M = |Zϕ | and let X be an ordering of Zϕ such that NγSI ≤ NγSI , ∀x ∈ {0, · · · , M − 1}. As in Lemma C.3, x x+1 37
available, it is possible to schedule a PGA as long as doing so does not introduce a minsep violation. Since cycle 0 meets the conditions that no two PGAs are scheduled simultaneously and no minsep violations occur, it is possible to commence the schedule with an iteration of cycle 0. In Figure 13, an iteration of cycle 0 with idle time I0 = 0 is illustrated between time t0 and the first dotted line. If NγSI > 2, then after the first iteration of cycle 0 all PGTs 0 γx ∈ ϕ have at least 2 PGAs which remain to be scheduled. Let us consider a scheduling method where the objective is to schedule an identical repetition of cycle 0. The earliest possible start time for this repetition of cycle 0 is the earliest possibility for s0,1 . The duration of the idle time I0 included in cycle 0 is set such that s0,1 occurs as soon as is possible, without violating the two requirements. By Lemma C.3, with N = NγSI , to ensure the schedule meets 0 the requirements that no two PGAs are scheduled simultaneously and no minsep violations occur, two cases can arise for s0,1 and I0 .
Case 1: If M −1 X
It follows from (45), (46), (47) and Lemma C.3 (with N = NγSI ) that if the duration cm of cycle m is m
Eγy ≥ tminsep ∀x ∈ {0, · · · , M − 1}, γx
(41)
y=0|y̸=x
cm = max
y∈{m,···M −1}
then, s0,1 =
M −1 X y=0
I0 = 0. Case 2: If (41) doesn’t hold, there exists at least one task x such that M −1 X
y=m
n0 = NγSI −1 0
(49)
cycles. In general, nm cycles of duration cm will be scheduled by our scheduling method, with nm given by,
(43)
Eγy < tminsep . γx
−1 X M Eγy + tminsep , E γy , (48) γy
then the schedule has the properties that no two PGAs are scheduled simultaneously, and no minsep violations occur. Exactly nm iterations of cycle m, with duration cm , occur before the subsequent drop out point. The first task (task zero) will drop out after
(42)
E γy ,
max
nm = NγSI − NγSI . m m−1
y=0|y̸=x
Then,
(50)
Px
s0,1 = I0 =
max
minsep
y∈{0,··· ,M −1}
max
y∈{0,··· ,M −1}
Eγy + tγy
(44)
,
(Eγy + tminsep )− γy
After y=0 ny cycles, NxSI − 1 PGAs for PGT γx have been added to the schedule, since
M −1 X
x X
Eγy .
ny = n0 +
y=0
x X
nm
y=1
y=0
= NγSI −1+ 0
Figure 13 illustrates a scenario where case 2 applies. The first dotted line in the figure indicates the time given by (42), and the second dotted line indicates the time given by (44). Let the term cycle m refer to a schedule consisting of the ith PGA from each PGT γx ∈ ϕ such that ex,i = sx,i + Eγx , ∀x ∈ {m, · · · , M − 1}
(45)
sx,i = ex−1,i , ∀x ∈ {m, · · · , M − 1},
(46)
x X
(NγSI − NγSI ) y y−1
y=1
=
x X
NγSI − y
y=0
x−1 X
NγSI −1 y
y=0
= NγSI − 1. x After it’s drop out point, each task is scheduled one final time. In total these individual executions contribute M −1 P an amount of time Eγy to the required time. In to-
and the ith PGA of PGT γM −1 is followed by idle time Im so that M −1 X sm,i+1 = sm,i + Eγy + Im . (47)
y=0
tal, following our scheduling method, the time required to execute NγSI PGAs of every task γ ∈ Zϕ is
y=m
Note that cycle m no longer includes PGAs for the PGTs {γ0 , · · · , γm }. The basis of the scheduling method is to continue scheduling cycles of PGA executions according to (45), (46) and (47), which preserve the ordering X. However, we only need to schedule NγSI PGAs for PGT γx . Therex fore, it is necessary to account for when a PGT γx drops out of a cycle, meaning that NγSI − 1 PGAs of the PGT x have already been scheduled by previous cycles. After a drop out point, the PGT that is dropping out needs to be scheduled a final time. Earlier we assumed NγSI > 2. 0 In accounting for when PGTs drop-out, we address the other possibilities, NγSI = 1, 2. Due to the ordering X, it 0 will always be the case that the PGT or PGTs dropping out at a drop out point are the first PGTs of the cycle. Figure 13 illustrates a scenario wherein NγSI = 3, hence 0 it is indicated that cycle c0 is repeated n0 = 2 times, after which point γ0 drops out, marking a transition in the schedule from cycle 0 to cycle 1. The final execution of γ0 is scheduled before cycle 1 begins. 38
R(Zϕ ) =
M −1 X
(nx · cx + Eγx )
(51)
x=0
= CalculateRequiredTime(Zϕ ).
C.iii.
(52)
The Compute Schedule process produces valid schedules
In this section we first extend the definition of sequentially valid schedules, which is only suitable for schedules covering a single filling class, to a definition of valid schedules for multiple filling classes. To do so, we first define the notion of a resource conflict. Then, we analyze the Compute Schedule process (Algorithm 3). This process includes a minimal allocation phase that relies on the DirectAllocation (Algorithm 6) subroutine and a bonus allocation phase that relies on the RoundRobinBonus (Algorithm 7) subroutine. We prove that the schedules produced by Compute Schedule are valid and always include a minimum allocation of PGAs for every active PGT.
Definition 19 (Resource Conflict). Let Φ be a set of filling classes and ZΦ the set of active PGTs in Φ. Let S be a schedule for the PGTs ZΦ with start times sγ,i and end times eγ,i for the ith scheduled PGA of PGT γ, ∀γ ∈ ZΦ . We say a resource conflict occurs in S if ∃γ, γ ′ , ∃i, j such that ξ(πγ ) ∩ ξ(πγ′ ) ̸= ∅, and sγ,i ≤ sγ ′ ,j < eγ,i . Definition 20 (Valid schedule). A schedule is said to be valid if it has the following two properties: 1. No resource conflicts occur, and 2. No minsep violations occur. Note that the first condition of a valid schedule, prohibiting resource conflicts, is a weaker condition than the first condition of a sequentially valid schedule, prohibiting any two PGAs from being scheduled simultaneously. The later condition guarantees that there are no resource conflicts within the same filling class, but it would also prevent simultaneously scheduling PGAs from different filling classes, even if they do not have overlapping resource requirements. Corollary C.5. The DirectAllocation scheduling algorithm (Algorithm 6) implements the specific scheduling method described in the proof of Proposition C.4. Proof. The result follows by direct comparison of Algorithm 6 and the proof of Proposition C.4. By Corollary C.5 and Proposition C.4, DirectAllocation produces a valid schedule for a filling class ϕ = (Zϕ , Πϕ ) which requires an execution time R(Zϕ ) = CalculateRequiredTime(Zϕ ), as given by the output of Algorithm 2. We subsequently refer to this method of scheduling simply as direct allocation. Proposition C.4 makes it possible to account for the duration of a valid schedule for a single filling class. To progress towards proving Theorem V.2, it is necessary to account for the duration of a valid schedule for a set of filling classes. The next results build towards the required accounting. It is possible for a set of filling classes Θ = {θ0 , θ1 , · · · , θM −1 } to have the property of being totally ordered, according to some ordering ≥. If Θ is totally ordered by an arbitrary ordering ≥, then θi−1 ≥ θi ≥ θi+1 ∀i ∈ {0, 1, · · · , M − 1}. In general a set of filling classes Φ may only be partially ordered by an arbitrary ordering ≥, in which case there exist incomparable elements ϕ and ψ such that neither ϕ ≥ ψ, nor ψ ≥ ϕ.
where R(Zθl ) = CalculateRequiredTime(Zθl ) is the output of Algorithm 2. Proof. To upper bound the minimum amount of time required to execute NγSI PGAs of every PGT γ ∈ ZΘ , we build upon the proof of Proposition C.4 and calculate the time required to execute a specific schedule for Θ including NγSI executions of each PGT γ ∈ ZΘ . Let M be the number of filling classes in Θ. By the hypothesis, Θ is totally ordered, according to some particular ordering ≥, such that θ0 ≥ θ1 ≥ · · · ≥ θM −1 . The only restrictions which can disallow scheduling a PGA at a certain time are that it would introduce a resource conflict or a minsep violation. By Lemma C.1, every PGT γ is associated with a single filling class. Since minsep violations may only occur between PGAs of the same PGT, no minsep violations may occur between PGTs in different filling classes. Hence, in building a schedule for Θ it is always possible to schedule back-to-back executions of a sequentially valid schedule for filling class θl and a sequentially valid schedule for filling class θl+1 . With the given ordering, the greatest element is scheduled first, and back-to-back executions mean that the start time of the schedule for filling class θl+1 is equal to the end time of the schedule for filling class θl . In this scheme no two PGAs are ever scheduled simultaneously, hence no resource conflicts can occur. To construct a specific schedule for Θ, it is thus sufficient to proceed by using direct allocation scheduling to schedule NγSI executions of all PGTs γ ∈ Zθ0 . By Proposition C.4, this schedule has duration R(Zθ0 ). To continue construction of the schedule for Θ, use direct allocation scheduling to construct a schedule for each filling class θl , l ∈ {2, · · · , M − 1} and append this schedule to the end of the schedule for filling class θl−1 . The total time required to execute this specific schedule for Θ is R̃(ZΘ ) =
M −1 X
R(Zθl ).
l=0
The ordering ≥ξ introduced in Definition 14 serves as an example of a specific ordering which may totally order the filling classes Θ in Proposition C.6. Two filling classes are incomparable under ≥ξ whenever ξ(ϕ) ∩ ξ(ψ) = ∅. The following theorem extends the result of Proposition C.6 from a set of totally ordered filling classes to a set of well-behaved filling classes, partially ordered by ≥ξ , as in Definition 14. The extension is non-trivial, and requires accounting for how the totally ordered subsets of Φ can be consistently added to a schedule without introducing resource conflicts. Proposition C.6. Let Θ be a totally ordered set of filling A set Φ that is partially ordered by an order ≤ contains classes conforming to Definition 8. Let ZΘ denote the totally ordered subsets. If Θ = {θ0 , θ1 , θ2 } is a totally orset of active PGTs in Θ. The minimum time required to dered subset of Φ, then {θ0 }, {θ1 }, {θ2 }, {θ0 , θ1 }, {θ1 , θ2 }, execute a valid schedule in which there are NγSI PGAs of and {θ0 , θ2 } are also totally ordered subsets of Φ. In this every PGT γ ∈ ZΘ is upper bounded by the quantity example, only Θ is a candidate for a maximally sized toX R̃(ZΘ ) = R(Zθl ), (53) tally ordered subset of Φ, as all of the other totally ordered subsets listed are subsets of Θ. θl ∈Θ 39
Theorem C.7. (Good Accounting) Let Φ be a set of well-behaved filling classes, partially ordered by ≥ξ . Let ZΦ denote the set of active PGTs in Φ. Let Ω = {Θ0 , Θ1 , · · · , Θn } be the set of all totally ordered subsets of Φ, of which there are a number n, for some n ∈ N, n ≥ 0. The minimum time required to execute a valid schedule in which there are NγSI PGAs of every PGT γ ∈ ZΦ is upper bounded by R(ZΦ ) = max R̃(ZΘi ), Θi ∈Ω
(54)
where R̃(ZΘi ) is given by (53). Proof. (Good Accounting.) Suppose that path partition Π describes an internally connected network. Let Ωmax be the set of maximally sized elements of Ω, Ωmax := {Θi ∈ Ω | ∀i′ ̸= i, Θi ⊂ Θi′ },
(55)
until we arrive at an element j ≤ min(k, k ′ ) such that (ω \ ϕj−1 ) ∩ (ω ′ \ ϕ′j−1 ) = ∅. As a remark, note that a singleton ω = ϕ ∈ Φ can be a maximal element of Ω as long as ξ(Πϕ ) ∩ ξ(Πϕ′ ) = ∅, ∀ϕ′ ̸= ϕ ∈ Φ. We now proceed to construct a schedule S for Φ, with start time t0 , by constructing schedules ∀ω ∈ Ωmax . For every ω ∈ Ωmax , identify αω , the unique greatest element of ω according to the order ≥ξ . The existence of this unique greatest element is guaranteed by Lemma C.2. Let Sω be a direct allocation schedule for αω with start time sαω = t0 . By Corollary C.5, the end time of the schedule Sω is eαω = t0 + R(αω ). Define ω̃ = ω \ αω , a temporary update of ω excluding the greatest element. Now, by Lemma C.2, ω̃ has a unique greatest element βω , according to the order ≥ξ . Append to schedule Sω a direct allocation schedule for βω with start time sβω = eαω . By Corollary C.5, the end time of the schedule Sω is eβω = t0 + R(αω ) + R(βω ). Update ω̃ = ω \ {αω , βω }. Continue in this manner until there are no remaining filling classes in ω̃, i.e. until ω̃ = ∅. Then, Sω is a schedule for ω constructed in the manner of the proof of Proposition P C.6 which has start time t0 and end time eω = t0 + R(ϕω ). Hence the required execution
where the inclusion ⊂ is the usual set inclusion. Whenever Ω ̸= ∅, it follows by definition that Ωmax ̸= ∅. Note that ∀ϕ ∈ Φ, ∃ω ∈ Ωmax such that ϕ ∈ ω. Therefore, Ωmax contains a total number of elements m such that 0 ≤ m ≤ n. Denote the elements as Ωmax = {ω0 , ω1 , · · · , ωm−1 }. Consider elements ω, ω ′ ∈ Ωmax , where ω = {ϕ0 , . . . , ϕk−1 } consists of k filling classes ordered by ≥ξ , and ω ′ = {ϕ′0 , · · · , ϕ′k′ −1 } consists of k ′ filling classes ordered ϕ∈ω by ≥ξ . The ordering implies that ϕ0 is the greatest eletime of S is R̃(ω), as given by (53). ω ment of ω under ≥ξ and ϕ′0 is the greatest element of ω ′ Claim 1 ensures that ∀ω, ω ′ ∈ Ωmax the schedules Sω , under ≥ξ . As a preliminary, we prove the following claim: Sω′ are consistent, meaning if ∃ϕ ∈ ω ∩ ω ′ , then the start time sϕω assigned to ϕ in schedule Sω is the same as the Claim 1: Whenever ω ∩ ω ′ ̸= ∅, then for some index ′ ′ th start time sϕω′ assigned to ϕ in schedule Sω ′ , 0 ≤ j ≤ min(k, k ), ω and ω are identical up to this j element. That is, ϕ0 = ϕ′0 , ϕ1 = ϕ′1 , · · · , ϕj−1 = ϕ′j−1 . s =s . (60) ϕω
ϕω ′
We proceed recursively and by contradiction. In the It follows immediately that base case, suppose for the sake of contradiction that ϕ0 ̸= ϕ′0 . Since ω ∩ ω ′ ̸= ∅, ∃ϕ such that ϕ ∈ ω and ϕ ∈ ω ′ . eϕω = eϕω′ , (61) Since ϕ0 , ϕ′0 are respectively the greatest elements of ω since in both Sω and Sω′ , the schedule for ϕ is a direct and ω ′ under the ordering ≥ξ , allocation schedule with start times obeying (60). ξ(Πϕ ) ⊂ ξ(Πϕ0 ), (56) Therefore, ∀ω, ω ′ ∈ Ωmax , the schedules Sω , Sω′ are ′ ξ(Πϕ ) ⊂ ξ(Πϕ′0 ). (57) either independent, which happens when ω ∩ ω = ∅, or else the schedules are consistent. To construct the full Therefore, ξ(Πϕ0 ) ∩ ξ(Πϕ′0 ) ̸= ∅. There are three possible schedule S, it is therefore sufficient to loop through the cases. In the first case, ξ(Πϕ0 ) = ξ(Πϕ′0 ), and we arrive schedules Sω , ∀ω ∈ Ωmax . For every schedule Sω , ∀ϕ ∈ ω, at the contradiction that ϕ0 = ϕ′0 , since Φ is well-behaved. if S does not already include the start time sϕ and end In the second case, time eϕ for ϕ, these start and end times are added to S. This method guarantess that no resource conflicts occur ξ(Πϕ0 ) ⊂ ξ(Πϕ′0 ). (58) in S. Furthermore, since ∀ϕ ∈ Φ, ∃ω ∈ Ωmax such that ϕ ∈ ω, the schedule S constructed in this manner includes Then, a direct allocation schedule ∀ϕ ∈ Φ. Hence, the schedule ′′ ′ ω = {ϕ0 , ϕ0 , ϕ1 , · · · , ϕk−1 } (59) S includes NγSI PGAs of every PGT γ ∈ ZΦ such that no is a totally ordered subset of Φ such that ω ⊂ ω ′′ , and we minsep violations occur. arrive at the contradiction that ω ∈ Ωmax . In the third Let ω ∗ ∈ Ωmax indicate a set with schedule Sω∗ which case, ξ(Πϕ′0 ) ⊂ ξ(Πϕ0 ) and the argument follows the same is a solution to logic as in the second case. Sω∗ = max R̃(Zω ), (62) If (ω \ ϕ0 ) ∩ (ω ′ \ ϕ′0 ) = ∅, then ω, ω ′ are only identiω∈Ωmax cal up to the 1st element. Otherwise, we can repeat the argument from the base case with ω \ ϕ0 and ω \ ϕ′0 as where Zω denotes the set of PGTs which occupy the set the basis. This recursive argumentation can be repeated of filling classes ω. Whenever Ωmax ̸= ∅, there exists such 40
an ω ∗ , Sω∗ , which need not be unique. The amount of time required to execute the schedule S is the amount of time required to execute Sω∗ . This concludes the proof in the case that the path partition Π describes an internally connected network.
C.iii.a.
Admit Tasks is Sound
For the Admit Tasks process to be sound, it must guarantee that newly accepted demands do not disrupt existing service agreements ((C3)). Before proceeding, it is useful to introduce definitions describing the availability of resources and how much time has already been reserved on In the case that the path partition Π describes a net- a network resource. work that is disconnected, partition Π into it’s internally connected sub-networks. The preceding proof then applies Definition 21 (Resource Availability). A resource is to each internally connected sub-network. Let {S} denote available between times t1 and t2 if there are no scheduled the set of schedules produced for the set of internally con- PGAs for any PGTs at any time between t1 and t2 . The nected sub-networks. The schedules S ∈ {S} are inde- total amount of time available on each resource r ∈ R pendent and have no resource conflicts since the schedules is a non-negative number are for sub-networks of the path partition, which have no Tξr ∈ [0, T SI ]. (65) resources in common. Each schedule S ∈ {S} has start time t0 and some end time eS ≥ t0 . Therefore, the set of Definition 22 (Time Reserved on a Resource). Let r ∈ R schedules S ∈ {S} constructs a schedule S for Φ in which and let Tξr be the total amount of time available on r. A NγSI PGAs of every PGT γ ∈ Φ are scheduled, no minsep duration of time T is reserved on resource r by decreconflicts occur, and no resource conflicts occur. Moreover, menting the available time by T , ∃S ∗ with end time eS ∗ which satisfies eS ∗ = max eS . The S∈{S} Tξr ← Tξr − T. (66) schedule S has required execution time eS ∗ = R(Φ), given by (54). We say it is possible to reserve time T on resource r if (66) is positive. A reservation of time with duration T may be canceled by incrementing the available time on resource r by T , Corollary C.8. The MinimalAllocation function (AlTξr ← Tξr + T. gorithm 3) implements the specific scheduling method described in the proof of Theorem C.7 (Good Accounting). Note that in the proofs of Propositions C.4 and C.6 it was assumed that the required network resources to exProof. The result follows by direct comparison of Algo- ecute a PGT are available. It remains to be shown that rithm 3 and the proof of Theorem C.7. In particular, Algorithm 5 guarantees that a PGT is only accepted if it is note that the MinimalAllocation function in Com- possible to reserve sufficient time on the required network puteSchedule makes use of the partial ordering of the resources. filling classes in building the schedule S with start time ′ t0 . To construct S, ∀ϕ ∈ Φ, a direct allocation schedule Theorem C.9 (Admit Tasks is Sound). Let γ ∈ Γ, let for ϕ is inserted into S with start time sϕ and end time Φ be a well-behaved set of filling classes with the set of active PGTs ZΦ , and suppose ∃ϕ ∈ Φ such that πγ ′ ∈ Πϕ . eϕ = sϕ + R(ϕ). The start time sϕ is set according to Then, γ ′ is accepted by Admit Tasks as implemented by X to execute a minimal alsϕ = t0 + R(ϕ′ ). (63) Algorithm 5 if the time required ′ location schedule for Z + γ is less than or equal to the Φ ϕ ′ >ξ ϕ scheduling interval. That is, The identification of ϕ′ >ξ ϕ, implicitly describes that R(ZΦ + γ ′ ) ≤ T SI , (67) MinimalAllocation identifies the subset ω ⊂ Ω of all totally ordered subsets of Φ for which ω ∩ ϕ ̸= 0. By (63), where R(·) is as in (54). ∀ϕ′ ≥ξ ϕ, sϕ′ < sϕ and moreover Proof. Throughout, let R(Θ) denote the time required to sϕ = max eϕ′ , (64) execute a minimal allocation schedule for a set of filling ϕ ′ >ξ ϕ classes Θ, as given by (54), and let R(θ) denote the time required to execute a direct allocation schedule for a single which is exactly how sϕ is assigned in the proof of Theo- filling class θ, as given by (52) . rem C.7. The set of active PGTs ZΦ satisfies R(ZΦ ) ≤ T SI , as every active PGT was previously accepted by Admit Tasks. As a consequence of Theorem C.7, given the set of fill- In the special case where there are no active PGTs, i.e. ing classes Φ as input, the minimal allocation phase of ZΦ = ∅ and N = |ZΦ | is zero, this still holds as Compute Schedule (Algorithm 3) produces a valid schedR(ZΦ = ∅) = 0 ⇒ R(ZΦ ) ≤ T SI . ule which includes NγSI PGAs of every PGT γ ∈ Φ. The schedule requires execution time R(Φ), as given by (53). In that case also We subsequently refer to this method of scheduling simply as minimal allocation scheduling. Zϕ = ∅ ∧ R(Zϕ ) = 0 ∀ϕ ∈ Φ. 41
This situation must occur at least the very first time Admit Tasks executes, and may occur in some scheduling interval k if all active PGTs expire or are terminated by Update Filling Classes, which precedes Admit Tasks. In the first step of AdmitTasks, the available time Tξr on each resource r ∈ R is reset to the duration of the scheduling interval, T SI . For each filling class ϕ ∈ Φ, the amount of time R(Zϕ ) required to execute a direct allocation schedule is calculated. Then, ∀r ∈ ξ(Πϕ ) the time reserved on r is incremented by R(Zϕ ). By Corollary C.8, sequentially reserving the time required to execute a direct allocation schedule on a resource r ∈ ξ(Πϕ ), ∀ϕ, is equivalent to reserving time on the the resource according to a minimal allocation schedule. Let M ZΦ denote the maximum amount of time reserved on any resource for the set of active PGTs ZΦ , M ZΦ := max(T SI − Tξr ). r∈R
By Corollary C.8 this is equal to the duration of the minimal allocation schedule for ZΦ . Overall, M ZΦ = R(ZΦ ) ≤ T SI . At this point, the task γ ′ is considered by AdmitTasks. By the hypothesis, ∃ϕ ∈ Φ such that πγ ′ ∈ Πϕ , so GetFillingClass returns the filling class ϕ. The next step of AdmitTasks is to add the PGT γ ′ to Z̃ϕ = Zϕ + γ ′ , a temporary update of the set of active PGTs in filling class ϕ. The Accept variable is initialized as True. The time reservation of amount R(Zϕ ) is then canceled on every resource r ∈ ξ(Πϕ ). Next, the time R(Z̃ϕ ) required to execute a direct allocation schedule for Z̃ϕ is calculated. By the proof of Proposition C.4 and Corollary C.5, the direct allocation schedule for ϕ may include idle time based on the values of tminsep , ∀γ ∈ Zϕ . For this reason, it is posγ sible that the time required to execute a direct allocation schedule of Z̃ϕ , R(Z̃ϕ ) is not substantially greater than R(Zϕ ), and it may be that R(Z̃ϕ ) = R(Zϕ ). Canceling the time reservation of R(Zϕ ) allows for correct comparison of R(Z̃ϕ ) to the available time on all resources r ∈ ξ(Πϕ ). Overall, R(Zϕ ) ≤ R(Z˜ϕ ). For every resource r ∈ ξ(Πϕ ), the time Tξr available on resource r is compared to the required time R(Z̃ϕ ). If ∃r ∈ ξ(Πϕ ) such that
Since we condition on all comparisons (68) passing, Tξr − R(Z̃ϕ ) ≥ 0, ∀r ∈ ξ(Πϕ ).
(70)
Hence it is guaranteed that ′
Tξr∗ = T SI − M ZΦ +γ ≥ 0.
(71)
Combining (69) and (71), R(ZΦ + γ ′ ) ≤ T SI .
(72)
Theorem C.9 (Admit Tasks is Sound) conditioned on inclusion of the path πγ ′ ∈ Πϕ for some ϕ ∈ Φ. The following Lemma addresses PGTs γ ′ ∈ Γ for which ∃ ϕ such that πγ ′ ∈ Πϕ . This can happen in a network with a dynamically evolving network resource graph. For example, if a resource on the path πγ becomes unresponsive between the time at which the demand was registered and the time at which Γ is retreived by the Network Scheduler. Lemma C.10. Suppose γ ′ ∈ Γ and ∃ ϕ such that πγ ′ ∈ Πϕ . Then, γ ′ is rejected by AdmitTasks. Proof. Let d be the demand associated with γ ′ . Let Γd ⊆ Γ denote set PGTs in Γ associated with the demand d. The AdmitTasks function calls the GetFillingClass function for the PGT γ ′ . If ∃ ϕ such that πγ ′ ∈ Πϕ , then GetFillingClass raises a FillingClassError, the PGT γ ′ is removed from Γd , and the PGT γ ′ is rejected by AdmitTasks. Remark C.11. When a PGT γ ′ which realizes a demand d is accepted, the final step of AdmitTasks is to remove the set of alternative PGTs Γd ⊆ Γ associated with the same demand. Hence Γ is updated to Γ \ Γd . This ensures that at most one PGT is admitted per demand. C.iv.
Minimal Allocation is Guaranteed
It is now possible to prove one of our main results, Theorem V.2 (Minimal Allocation is Guaranteed). This theorem underpins the proof of Theorem V.1 (Deterministic Satisfaction of Service Agreements) in Section V. The following theorem assumes that the set of filling classes is well-behaved. In our implementation of Arqon Tξr − R(Z̃ϕ ) < 0, (68) (Section VI) we specify a path partition and the set of filling classes it induces. Then, we prove that this specific then the Accept variable is set to false, the PGT γ is set of filling classes is well-behaved. This is sufficient to removed from Γ, and γ ′ receives a reject decision. Other- demonstrate the existence of well-behaved sets of filling wise, the value of Accept remains true, the set of active classes. PGTs Zϕ is updated to Z̃ϕ , and the available time on each associated resource r ∈ ξ(Z̃ϕ ) is decremented by the re- Theorem V.2 (Minimal Allocation is guaranteed). ′ quired time for the filling class, R(Z̃ϕ ). Define M ZΦ +γ Let d be a demand accepted by Arqon as the PGT and r∗ respectively as the maximum amount of time re- γd . Suppose πγd ∈ Π in every relevant scheduling interserved on any resource due to the PGTs in ZΦ + γ ′ and val. Suppose Φ is a well-behaved set of filling classes. the resource on which the maximum reservation occurs. Then, in every relevant scheduling interval the schedule S = ComputeSchedule(Φ) contains at least NγSI PGAs By Corollary C.7, d of the PGT γ . Moreover, the duration of S does not exd ′ M ZΦ +γ = R(ZΦ + γ ′ ). (69) ceed T SI . 42
Proof. By Theorem C.9, the time required to execute a minimum allocation schedule does not exceed the scheduling interval T SI . It remains to show that given a schedule Sk as input, the bonus allocation phase of Compute Schedule cannot extend the required execution time of the schedule Sk to beyond T SI . The BonusAllocation function in Algorithm 3 for Compute Schedule takes the schedule Sk as input, and ∀ϕ ∈ Φ, it returns an update of the schedule, Sk = RoundRobinBonus(ϕ, Sk ). RoundRobinBonus, given by Algorithm 7 may insert PGAs of a PGT γ into the schedule Sk . Before any PGA may be added, the following condition is checked: test + Eγ < T SI .
(73)
Algorithm 9: Simplified representation of RoundRobinBonus. Function RoundRobinBonus: Input : Filling class ϕ, network schedule S input . Output: Updated network schedule S. Set T rel ← {}; Set test ← 0; Set k ← 0; while test < T SI do S, T̂ rel ← f (S, T rel , test ); Set test , T rel ← nextStartTime(S, T̂ rel , test ); end end
Condition (73) ensures that a PGA is only added to schedule Sk if the time required to execute the updated schedule Sk does not exceed T SI . Hence, after all updates are made and to Sk in the bonus allocation phase, the time required to test execute Sk does not exceed T SI . 0 = 0,
T0rel = ∅,
T̂0rel = ∅,
S0 = S input .
(76)
Note that NextStartTime removes a release time from the set of release times to consider if it is the next start time, so in general T̂krel ̸= Tkrel . Similarly, if a PGA is scheduled, then f will add a We now develop the complexity analysis of the Network release time to the set of release times to consider, so Scheduler, from which we derive and prove Theorem VII.1 T rel ̸= T̂ rel in general. i i+1 in Section VII. We calculate the complexity in terms of the We first show that the next earliest start time test is k number of active PGTs N = |ZΦ | in the set of filling classes smaller than any remaining release times to consider. Φ, the number of active PGTs Nϕ = |Zϕ | in a single filling rel class ϕ, the number of PGTs k = |Γ| in the task intake Lemma D.1. test k < min Tk . object, and the number of internal resources R = |R|. To bound the complexity of a process, it must eventu- Proof. Recall that δ = (γ, t; r) ∈ S̃ is a PGA for PGT ally halt on any input. Unlike the other processed of the γ scheduled at start time t on resourceendr in a schedule Network Scheduler, which are based on loops with a finite S̃. The end time of such a PGA δ is tδ = t + Eγ . We There are two number of iterations, the bonus allocation phase is based examine the affect of nextStartTime. end ′ cases to consider. If min{t : δ ∈ S } < min T̂krel , then δ k on RoundRobinBonus, which contains a while loop. To bound the operational complexity of RoundRobinend test : δ ∈ S ′ } < min T̂krel = min Tkrel . k = min{tδ Bonus, it is necessary to demonstrate that this algorithm halts on any input. : δ ∈ Sk′ }, then Otherwise, if min T̂krel ≤ min{tend δ In this Appendix we first prove that RoundRobinBonus halts on any input, and then we bound the com- test = min T̂ rel , and T rel = T̂ rel \{test } =⇒ test < min T rel . k k k k k k plexity of each process of NetworkScheduler.
D.
D.i.
Complexity Analysis of the Network Scheduler
Round Robin Bonus Halts
To prove that RoundRobinBonus, Algorithm 7, halts on any input we need to show that in finite time the earliest start time test is updated by RoundRobinBonus to a value that exceeds the scheduling interval, test > T SI . Let us simplify the representation of the algorithm in the following manner: In Algorithm 9 the function f represents the action of the for loop in Algorithm 7. To prove that the algorithm halts, we need the sequences Si , T̂irel , Tirel and test i , where rel Si+1 , T̂i+1 = f (Si , Tirel , test i ), rel rel est test i+1 , Ti+1 = nextStartTime(Si+1 , T̂i+1 , ti ),
Next we show that new release times are only added when test is the end time of a PGA in the schedule. Lemma D.2. Suppose that for some test k , ∄δ ∈ Sk such end that test k = tδ . Then, following the application of f as rel in (74), T̂k+1 = Tkrel , i.e. no release times are added by f .
Proof. Suppose not. Then there exists some time t∗ such rel that t∗ ∈ T̂k+1 but t∗ ̸∈ Tkrel . This implies there exists a minsep ∗ PGA δ from a PGT γ ∗ such that t∗ = tend and δ ∗ + tγ ∗ est end est tk−1 < tδ∗ ≤ tk . end As test k−1 < tδ ∗ , by the action of nextStartTime we est end est end (74) must have that tk ≤ tδ∗ . This implies that tk = tδ∗ . est But this contradicts the assumption that tk is not an end (75) time of any scheduled PGA and so no such δ ∗ , t∗ exist. 43
We now show that test i , which is updated in each loop the number of release times in the set of release times ′ of RoundRobinBonus by nextStartTime is strictly in- cannot increase until test = tend l δ ′ for some δ ∈ S∞ . Hence rel rel creasing. for k + 1 ≤ i ≤ l, |T̂irel | ≤ |T̂k+1 |. Furthermore, |T̂k+1 | < |Z | < ∞ as each PGT can only contribute one release Φ est Lemma D.3. For all i > 0, test end i+1 − ti > 0. time. Therefore, after at most l = |ZΦ | steps, test k+l = tδ ′ ′ for some δ ∈ S . ∞ Proof. We proceed by induction on the iteration index i. For the base case i = 0. Consider the action of f on Corollary D.5 (Visit every end time). Let δ be a PGA S0 , T0rel , test 0 . The only way for a new time to be added in S∞ with end time tend rel δ . Then there exists some k < ∞ to T is from a past minsep violation. As there are no such that test = tend . k δ PGAs scheduled before time t = 0, there cannot be any past minsep violations at test 0 . Therefore, there are no new Proof. As PGAs can only be scheduled at the current release times added to T0rel by f and so T̂1rel = T0rel = ∅. value of test , any new end times are in the future and Now consider the action of nextStartTime on will therefore not be skipped over. The number of PGAs rel S1 , T̂1rel , test = ∅ and nextStartTime only re- in S∞ is countable, therefore let us enumerate them by 0 . As T̂ moves elements from T̂ rel , we must have T1rel = ∅. More- δ0 , δ1 , ... such that tend ≤ tend . Then by the previous δi δi+1 over, there are no release times to consider, and so the corollary we have that there exists some l < k|Z | such Φ next earliest start time must come from the earliest end that test = tend . l δk time of a PGA in S1 , i.e. Finally, we show that for every time c > 0, test exceeds k end test = min t ≥ min E > 0, (77) γ 1 δ c in a finite number of steps. γ∈ZΦ δ∈S1 and the base case follows. Suppose now that the result holds for all i ≤ k. We need to consider two cases, whether test k+1 is an end time rel of a PGA in Sk+1 or whether it is a release time in T̂k+1 . In the first case, we have that nextStartTime explicitly only considers PGAs with end times greater than test k and est so we must have test k+1 > tk . In the latter case, suppose rel that ∃t∗ ∈ T̂k+1 such that t∗ < test k , i.e. nextStartTime est would choose tk+1 = t∗ . rel There are two ways for t∗ to get into T̂k+1 , either carried forward from (75) in iteration k or from (74) in iteration k + 1. By Lemma D.1 the time returned by nextStartTime is less that the minimum value in Tkrel , so it must be that t∗ was added by f as in (74), in iteration k + 1. In particular, ∃δ ∗ ∈ Sk such that δ ∗ is a left-minsep violation minsep ∗ end for some PGT γ ∗ at time test > test . k , i.e. t = tδ ∗ +tγ ∗ ∗ est ∗ This contradicts that t < t , and so no such t can exist. est Therefore, test and the result follows. k+1 > tk
Lemma D.6. For each filling class ϕ ∈ Φ, BonusRoundRobin(ϕ, S input ) generates the sequences (74) and (75) such that ∀c ≥ 0 there exists k < ∞ for which test k ≥ c.
Proof. As every PGT in Zϕ has a finite expiry time, after which no further PGAs are scheduled, there are only a finite number of PGAs in S∞ . We consider two cases, c < maxδ∈S∞ tend and c ≥ maxδ∈S∞ tend δ δ . In the former case, there exists some end time tend δ ∗ > c. By Corollary D.5, the sequence (test ) reaches tend i δ ∗ in finite time and so exceeds c in finite time. In the latter case, consider the values that (test i ) takes after reaching the last end time in S∞ . Let k be such rel = maxδ∈S∞ tend that test k δ , and let T̂k+1 be the set of release times to consider after test . As each PGT can only k rel contribute at most one release time to T̂k+1 , we have rel r = |T̂k+1 | ≤ |Zϕ | < ∞. Furthermore, we have that rel rel | − 1 for i = 1, ..., r. Therefore, we have |T̂k+i+1 | = |T̂k+i rel est that T̂ = ∅. Moreover, at test We now show that the sequence tk visits the end time k+r k+r there are no future end times (as nothing can be added to schedule which of every scheduled PGA in a finite number of steps. To end est ends after max t < t ) and no release times as do so, we introduce the notation δ∈S∞ δ k+r rel T̂k+r = ∅. Therefore, the action of nextStartTime is est S∞ := lim Sk . (78) to set test k+r+1 = ∞ > c. Therefore (ti ) hits ∞ in a fik→∞ nite number of time steps and hence exceeds c in a finite As Sk is strictly increasing, in the sense that PGAs can number of time steps. only be added to a schedule, this limit is well-defined. Note that in the limit k → ∞ we don’t impose a cutoff at We can now prove that RoundRobinBonus(ϕ, S) the end of a scheduling interval, and instead assume the functions f and NextStartTime are applied as long as halts on all inputs. the algorithm does not halt. Theorem D.7. For all possible inputs ϕ, S, Corollary D.4 (Finite number of steps between end RoundRobinBonus(ϕ, S) halts. end times). Let test be the end time of a PGA k < maxδ∈S∞ tδ Proof. Suppose not. Then the algorithm must enter an in S∞ . Then ∃l < ∞ such that test k+l is also the end time infinite loop somewhere. The For loop has finite numof a PGA in S∞ . ber of steps, |Zϕ |, so will always exit. We define a ‘cycle’ est end Proof. Consider test for i > k. If t = ̸ t , for some of the round-robin scheduler to be each time the While ′ i i δ δ ′ ∈ S∞ , then test must be a release time. By Lemma D.2, condition is checked. Note that each cycle the value of i 44
test is incremented by nextStartTime as per the sequences (74), (75) and by Lemma D.3 test increases with each cycle. The program halts when test > T SI . By Lemma D.6 this occurs in a finite number of cycles and so the program will always halt.
O(N R) time. Subsequently, updating the set of removed tasks requires creating and assigning a list of length O(N ). Therefore, building the set of filling classes takes O(1) time if there is no change to the path partition and O(R2 + N R + N ) time otherwise. To remove the terminated and expired demands, each filling class ϕ ∈ Φ is treated in turn. For a given filling D.ii. Complexity Analysis class ϕ with Nϕ active PGTs, each PGT is iterated over We determine the complexity of NetworkScheduler and if it is in the set of terminated demands it is removed, as in Algorithm 1 by examining each of the sub- or if it has expired it is removed. Checking if a PGT is in routines: UpdateFillingClasses, AdmitTasks, and the terminated set is an O(1) operation (set membership). ComputeSchedule. Checking if a PGT has expired is also an O(1) operation. Therefore, removing the terminated or expired PGTs takes O(Nϕ ) time. D.ii.a. Update Filling Classes After the PGTs are removed, the required time is reFirst, we examine the complexity of UpdateFilling- calculated (CalculateRequiredTime(ϕ), implemented Classes, Algorithm 4, as implemented in Listing 5. by lines 52-63 in Listing 6), at a cost of O(Nϕ2 ) – see Lemma D.9. Therefore, updating each filling class takes Lemma D.8. UpdateFillingClasses as implemented O(N 2 ) time, for a total of O(N 2 ) time across all filling ϕ in listing 5 has operational complexity O((N + R)2 ). classes. Updating the lists of removed and expired demands are Proof. The algorithm is split into two phases: building the O(Nϕ ) or O(N ) ((once we sum over all filling classes) opset of filling classes from Π and then removing terminated erations, so are sub-leading. and expired demands from each filling class. Therefore, the overall complexity is If the path partition is unchanged, the old set of filling classes can be brought forward and there are no required O(R2 + N R + N ) + O(N 2 ) = O((N + R)2 ). operations. Otherwise, we build a set of filling classes from the new path partition. We create one filling class per cell of the path partition, then sort them and finally create a dictionary holding the ordering. Creating a filling class is D.ii.b. Admit Tasks an O(1) operation, as it only requires value assignment. To calculate how many filling classes there can be, con- We now show the complexity of Admit Tasks, Algorithm 5, sider the specific choice of filling classes given in Defini- as implemented by Listing 4. It makes use of some of tion 13. Let |B| be the number of long-distance backbones, the methods of a filling class, implemented in Listing 6. |J| the number of junction nodes and |I| be the number First we determine the operational complexity of CalculateRequiredTime, which Admit Tasks uses to reserve of EGIs in the network, so |B| + |J| + |I| = R. There is a single backbone partition ΠB . Each set of time for the minimum allocation of PGAs of active PGTs junction nodes Ji is disjoint, and so there are at most on all resources associated with a filling class. |J| junction filling classes. Each EGI contributes a filling class, so there are I EGI filling classes. Therefore there Lemma D.9. CalculateRequiredTime(ϕ) for a fillin Listing 6 has operational are at most 1 + |J| + |I| < R filling classes, and so there ing class ϕ as implemented 2 complexity O(N ). ϕ are O(R) filling classes. Creating all of the filling classes is thus O(R). Sorting Proof. Calculating the total required time requires calcuthe set of filling classes is O(R log(R)). Computing the lating the vector of cycle times cϕ = (cϕ ) and the vector of i dictionary holding the ordering requires a double iteration cycle numbers nϕ = (nϕ ) as in the proof of Proposition C.4 i 2 of the list of filling classes, which takes O(R ) time. The in Appendix C. Calculating each of the nϕi each requires implementation of these processes is given in Listing 7. a single value assignment and subtraction, an O(1) operThe remaining assignments in lines 14-16 of Listing 7 ation, for a total of O(Nϕ ) operations. take O(1) time, because a None value is always assigned Calculating cϕk has the following steps: We obtain the in NetworkScheduler. These properties are never initialized in this main loop and are only initialized in the list of end times plus minseps for each PGT with index numeric complexity evaluations of Section VIII, resulting greater than or equal to k, which has complexity O(N −k). in Figures 11 and 12. The overall complexity of construct- Obtaining the sum of the execution times is also O(N −k). Finding the maximum of this list and the sum of the exing the set of filling classes is thus O(R2 ). ecutions times is an O(log(N − k)) operation. Combining If the path partition changes, we attempt to re-add each these three steps, the total complexity for computing each PGT γ to a filling class. This requires an O(R) lookup to of the cϕk is O(N − k). The total complexity for computing find the correct filling class and then O(1) time to add γ PNϕ −1 ϕ 2 to the filling class. Note that re-calculating the minimum the ci is then k=0 O(Nϕ − k) = O(Nϕ ). Once we have the nϕi and the cϕi terms, we need to calculate nϕ .cϕ , which requires O(Nϕ ) multiplications, O(Nϕ )
required time for the filling class is delayed until the end of this whole routine. Therefore, re-adding PGTs takes
45
additions and one value assignment, for an overall complexity of O(Nϕ ). Combining these calculations, the total complexity is 2
O(Nϕ ) + O(Nϕ )
+ O(Nϕ ) = O(Nϕ2 ).
Therefore, determining an accept/reject decision for a PGT γ has total complexity
(79)
O(R) + O(Nϕ2 ) + O(R) + O(1) = O(Nϕ2 ) + O(R).
Each demand in Γ contributes at most one PGT into Zϕ , so we can bound |Nϕ | above by N + k, and the total complexity of making a determination for γ is O((N +k)2 +R) Theorem D.10. AdmitTasks as implemented in ListFor each possible path π along which PGAs for a ing 4, operating on a set of filling classes Φ as implemented demand d can be realized, there is a constant finite in Listing 7, has operational complexity number of entanglement generation protocols which can number of possible 2 R 2 O(k[(N + k) + R]2 + R ). (80) be employed. Therefore, the total PGTs for a given demand is O(2R ). There are k deProof. Initially AdmitTasks calculates and sets the cur- mands for which a decision needs to be made. Thererent available time on each resource r ∈ R. Setting the fore the overall computational complexity is given by 2 R 2 initial available time of a full scheduling interval requires O(k[(N + k) + R]2 + R ). O(R) value assignments (each O(1)). In our implementation of the filling classes the total required time is stored D.ii.c. Compute Schedule as a property of a filling class, so we can get the total reWe determine the complexity of Compute Schedule by first quired time in O(1) (amortized) time. Each filling class is determining the complexity of it’s subprocesses. Fundaassociated with O(R) resources, so decrementing the time mentally, computing schedules requires adding PGAs to available (O(1)) for all resources associated with a particthe network schedule, which is implemented as in Listular filling class takes O(R) time. There are O(R) filling ing 8. Compute Schedule has three phases: minimal classes in total, so the initialization of the routine takes allocation, bonus allocation, and schedule compilation. O(R2 ) + O(R) = O(R2 ) time in total. The minimal allocation phase computes direct allocation Next AdmitTasks determines whether to admit a parschedules (DirectAllocation, Algorithm 6, Listing 1) ticular PGT γ ∈ Γ. To find the filling class of γ we check for each filling class. The bonus allocation phase attempts each filling class ϕ sequentially to determine if the path is to add PGAs to the direct allocation schedules for each fillin the cell Πϕ of the path partition. Each filling class can ing class, according to BonusRoundRobin, Algorithm 7, be obtained in O(1) time (dictionary query), performing which is implemented in Listing 2. Schedule compilation the inclusion check is O(1) (set inclusion), and there are (CompileSchedule) is implemented in Listing 8. O(R) filling classes, for a total of O(R) operations. Suppose we find a filling class ϕ for γ, and let Nϕ = |Zϕ |. Lemma D.11. Let the format of the network schedule First, we need to remove the contribution from the PGTs be as implemented in Listing 8. Then, appending a PGA in Zϕ to the reserved time on each resource associated to the schedule has complexity O(R). Inserting a PGA with ϕ. Updating each of the O(R) resources takes O(1) anywhere else in the schedule has complexity O(RN ). time (dictionary parameter query, subtraction, value asProof. The process of scheduling a PGA for a PGT γ can signment) for a total complexity of O(R). We can then add γ to Zϕ . To do so, first we need be decomposed into three parts. Firstly, we get the reto determine at which index in the ordering it should be source schedules for the individual resources on the path inserted to preserve the ordering by N SI . In our imple- πγ . The network schedule is implemented as a dictiomentation this takes O(Nϕ ) time as we examine each el- nary of resource schedules keyed by their resource idenement in sequence. Once the index i is found, γ can be tifier, so we simply loop through the path πγ and retrieve inserted into the list, which takes O(Nϕ − i) time. Finally, each schedule in turn (dictionary query, O(1)). Therefore, adding γ to Zϕ means the minimum required time needs to the complexity of getting all the schedules to update is be recomputed, which by Lemma D.9 takes O(Nϕ2 ) time. O(|πγ |) = O(R). Secondly, for each resource in πγ , we need to configure Therefore, the total operational complexity of adding γ to the PGA(s) to be scheduled, as in lines 53-56 of Listing 8. Zϕ is O(Nϕ ) + O(Nϕ − i) + O(Nϕ2 ) = O(Nϕ2 ). Once the perspective PGT has been added to its filling This takes O(1) time. Finally, we need to add the constructed PGA(s) to the class, we need to check if R(Zϕ ) ≤ T SI , in which case the PGT can be accepted. Updating the reserved time on resource schedule Sr . If a PGA can be appended to the each resource associated with ϕ takes O(1) time (dictio- end of the resource schedule whilst maintaining time ornary query, addition, value assignment) Checking (float dering of all scheduled PGAs, adding the PGA has the comparison, O(1)) that the available time for all O(R) same (amortized) complexity as appending to a list, which is O(1). If it is not known at which index a new PGA resources is positive takes a total of O(R) time. If this condition is met (i.e. the PGT is accepted), then needs to be inserted to maintain time ordering, then it updating the dictionary of accepted demands takes O(1) can be obtained using binary search in time O(log |Sr |). time. Otherwise, if the PGT is rejected, then we need As Sr is a list of PGAs, the total number of which is to undergo the same procedure as above but in reverse, O(N ), we have that finding the index required is O(log N ). Let q be the index at which the new PGA should be which has at worst the same complexity. 46
inserted. Then performing the insertion has complexity O(|Sr | − q) = O(N ). The total complexity of parts two and three combined is then O(1) when appending and O(N ) otherwise. Since these parts need to be repeated for each resource on the path πγ , in total the complexity is O(R) when appending and O(RN ) otherwise. Lemma D.12. DirectAllocation(ϕ), as implemented in Listing 1 for a filling class ϕ, operating on a network schedule as implemented in Listing 8, has computational complexity O(Nϕ R) + O(Nϕ2 ). (81) Proof. The total P number of PGAs to be scheduled from filling class ϕ is γ∈ϕ NγSI = O(Nϕ ). This holds since ∀γ, NγSI is a positive integer. We proceed through Listing 1 line-by-line. In initializing the routine, lines 11-15, we obtain the logger, set cycle_start_time and set up one pointer for each resource. These are either value assignment or dictionary query operations, which are all O(1). In lines 17-45 we construct the schedule. The PGTs in a filling class are ordered by a set of indices X SI such that NxSI ≤ Nx+1 . For each γx in increasing order x = {0, 1, · · · , |Zϕ |}, we add all NγSI PGAs for γx to the x schedule. In lines 19-21 we retrieve the new cycle time (dictionary query, O(1)) and reset the cycle counter k (value assignment, O(1)). This portion has total complexity O(1). The two for loops, in lines 23-31 add all the PGAs for the PGT γx to the schedule, for each cycle in turn. For each of these PGAs, the offset of the start time from the start of the cycle is calculated in line 25. This requires summing the elements of a list of length order O(Nϕ ), so it is an O(Nϕ ) operation. Then the PGA needs to be added to the schedule. By Lemma D.11, this has complexity O(R) as, by construction, DirectAllocation only appends PGAs to the end of resource schedules. Therefore, the total complexity incurred from adding a PGA to the schedule is O(R) + O(Nϕ ). Lines 33-42 simply schedule one last PGA for each PGT following the end of it’s last cycle, as discussed in the proof of Proposition C.4. The total complexity is thus given by
_get_next_start_time: With the implementation of the network schedule in Listing 8, getting the end times to consider relies on getting each resource schedule ∀r ∈ R (dictionary query, O(1)) and then retrieving the end time of a specified PGA (list element retrieval at known index, O(1)). Therefore, getting the PGA end times to consider has a total complexity of O(R). The minimal end time is determined by minimizing over the set of end times to consider, an O(R) operation. Therefore, the total complexity to get the next end time is O(R) + O(R) = O(R). The next release time is determined by minimizing over the list of release times supplied as an input to the subroutine. Each PGT in ϕ can contribute at most one release time to this list for a total of O(Nϕ ) elements. Therefore, finding the next release time is O(Nϕ ). The next start time is the minimum of the next end time and the next release time. Calculating it takes O(1) time (comparing two values). If the next start time is the next end time, the set of schedule pointers is updated. To update the pointers, for each resource in R, we check if the pointed PGA ends before or at the next start time (dictionary query, O(1), and list item retrieval at known index, O(1)). If so, the pointer is incremented by two (O(1)). Therefore, the total complexity for updating the pointers is O(R). Alternatively, if the next start time is the next release time, we remove the next start time from the set of release times, which is an O(1) operation. Therefore, the contributions from getting the next end time, the next release time, finding the minimum of these and then updating the release times/schedule pointers gives a total complexity of O(R) + O(Nϕ )+O(1) + O(R) = O(R) + O(Nϕ ).
(84)
_resources_available: To check if all the resources required to schedule a PGA from PGT γ are available, we perform the following steps: For each resource in πγ , we check if the pointed PGT is active at time test . This consists of a dictionary query to get the resource schedule O(1), list retrieval at a known index (O(1)) and a constant number of comparisons (O(1)). Therefore, checking if one resource is available at time test is an O(1) operation. The total from checking all resources is then O(|πγ |) = O(R). O(1) + O(Nϕ ) + O(Nϕ )(O(R) + O(Nϕ )) _future_minsep_violations: To check if there are 2 minium separation violations in the future for a PGA from = O(Nϕ ) + O(Nϕ R). (82) PGT γ, it suffices to check only the resource schedule from the first internal resource in πγ . Getting the relevant resource and its resource schedule is an O(1) operation (list Lemma D.13. RoundRobinBonus(ϕ) as implemented retrieval from known index, dictionary query). Initializin Listing 2 for a filling class ϕ operating on a network ing the offset variable is also O(1). Each check which schedule as implemented in Listing 8 has operational com- is performed is an O(1) operation (comparison, property plexity retrieval, value assignment). The number of scheduled O(N 2 Nϕ R)). (83) PGAs to check is only bounded by the size of the schedule, and so there are O(N ) checks to perform. Combining the contributions from obtaining the resource schedule, Proof. The overall complexity depends on the complexity initializing the counter and then performing the checks of the subroutines which are detailed in Algorithm 8 and gives a total complexity of O(N ). implemented in Listing 2. _past_minsep_violations: The process is the same 47
as for _future_minsep_violations, so the complexity is O(N ). We now move to the main loop of the algorithm. The maximum number of cycles is the same as the maximum number of possible start times. Each possible start time corresponds to the end of some PGA in the schedule, so there are at most T SI = O(N ) Eγ + tminsep γ ϕ∈Φ γ∈Zϕ X X
(85)
possible start times. The expression (85) dictates that every PGT can contribute at most a number of PGAs based on how many times the PGA duration plus minsep fits within the scheduling interval. Thus the number of cycles is O(N ). In each cycle there are Nϕ rounds, during each of which _resources_available, _future_minsep_violations, _past_minsep_violations are called. The algorithm may also add a PGA to the schedule, which by Lemma D.11 takes O(RN ) time as these PGAs typically need to be inserted intro the schedule rather than appended to the end. At the end of each cycle, _get_next_start_time is called. Overall, the complexity is O(N ) O(Nϕ ) O(R) + O(N ) + O(N ) + O(N R) +O(R) + O(Nϕ ) = O(N 2 Nϕ R). (86)
D.iii.
Numeric Evaluation
In Section VIII we discuss the simulation of randomly generated network topologies, parametrized by the number of long-distance backbones, local areas, and end nodes in the network. Table 5 compiles the average schedule computation times for each of these parametrizations. The time to compute the schedule is broken down by the processes Update Filling Classes, Admit Tasks, and Compute Schedule (without the Compile Schedule process). The total time to produce the network schedule includes the time for each of these processed and Compile Schedule.
E.
Implementation: Supporting Results and Formal Definitions
In this section we provide formal definitions for the set of allowed edges in a network resource graph and for the set of allowed entanglement generation paths that we consider in our implementation of Arqon. Then, we prove the supporting results Lemma VI.1 and Lemma E.1 describing the properties of the specific choice of path partition and the set of filling classes it induces. Finally, we discuss our methods of setting the duration of a PGA for a given ppacket . E.i.
Allowed Edges in a Network Resource Graph
Definition 23 (Set of Allowed Edges, E ∗ ). Let vi , vj ∈ V be two vertices in the network resource graph. An edge e = (vi , vj ) is an allowed edge if the following conditions are satisfied: Lemma D.14. Given that the network schedule is implemented as in Listing 8, CompileSchedule has oper1. If vi ∈ E then vj ∈ I. Reflexively, if vj ∈ E, then ational complexity O(N R). v ∈ I. i
Proof. The schedule is implemented as a dictionary of lists 2. If vi ∈ B, then vj ∈ J. Reflexively, if vj ∈ B, then of PGAs, one per internal resource in the network, called a vi ∈ J. resource schedule. Therefore, the only operation required is to convert each PGA into its transmission format. This 3. If vi ∈ J ∧ vj ∈ B, then vj ∈ I. Reflexively, if takes constant time for each PGA. There are O(N ) PGAs vj ∈ J ∧ v i ∈ B, then vi ∈ I. in each resource schedule and O(R) resource schedules, and so the overall complexity for compiling the schedule The set of allowed edges is is O(N R). E ∗ := {(vi , vj ) | (1. ∨ 2. ∨ 3.) ∧ vi , vj ∈ V}. (89) Theorem D.15. The program ComputeSchedule has operational complexity E.ii. The set of allowed entanglement generaO(N 3 R).
tion paths
(87)
Definition 24 (Allowed entanglement generation paths). Let G = (V, E) be an internally connected network resource graph with V = E ⊔ I ⊔ J ⊔ B and E ⊆ E ∗ . Let L be the Proof. By Lemmas D.12, D.13 and D.14 the total com- set of local areas of G. Define plexity is given by X X πe,e′ = π = (e, v1 , · · · , vk , e′ ) ∈ Pvalid , (90) 2 O(Nϕ R) + O(N Nϕ R) + O(N R) ϕ∈Φ ϕ∈Φ the set of all valid entanglement generation paths be3 3 = O(N R) + O(N R) = O(N R). (88) tween two specific end nodes e, e′ ∈ E, of variable length k = |πe,e′ | − 2. The set Pallowed ⊂ Pvalid of allowed entanglement generation paths is a restriction of the set 48
Long-distance Backbones
Local Areas
End Nodes
Time to Update Filling Classes (s)
Time to Admit PGTs (s)
Time to Compute Schedule (s) (without Compilation)
Total Time to Produce Network Schedule (s)
1 2 2 2 2 3 5 6 7 12
2 2 2 3 3 3 4 3 5 4
15 15 50 30 50 30 40 35 50 40
0.00011 0.00011 0.00025 0.00017 0.00027 0.00018 0.00031 0.00022 0.00059 0.00034
0.00017 0.00019 0.00180 0.00051 0.00147 0.00061 0.00133 0.00121 0.00291 0.00182
0.00683 0.00707 0.03461 0.02276 0.04741 0.02406 0.06215 0.03738 0.13799 0.08051
0.05268 0.05246 0.09126 0.07343 0.10465 0.07529 0.11797 0.09196 0.20227 0.14175
Table 5: Average computation times for each process of the Network Scheduler control application, from the simulations of randomly generated network topologies parametrized by Table 1. These values are based on the simulations with default Arqon, where the bonus allocation phase of the Compute Schedule process is enabled. of valid entanglement generation paths, as follows Pallowed = πe,e′ ∀e, e′ ∈ E πe,e′ ∈ B ∗ (e, e′ ) ∧ ∗ ′ ∗ ∀Ly ∈ L, πe,e′ ∈ Ly (e, e , b ) , (91) where k=|πe,e′ |−2 ∗
1(vx ∈B) = b∗(e,e ) }, (92) ′
X
′
B (e, e ) = {πe,e′
x=1
L∗y (e, e′ ,b∗ ) = πe,e′ ∈ B ∗ (e, e′ ) k=|πe,e′ |−2
1(vx ∈Ly ) 1(vx ∈I) = ly∗ (e, e′ , b∗ ) , (93)
X x=1
and k=|πe,e′ |−2 ∗
′
b (e, e ) = min πe,e′
1(vx ∈B) ,
(94)
1(vx ∈Ly ) 1(vx ∈I) ,
(95)
X x=1
k=|πe,e′ |−2
ly∗ (e, e′ , b∗ ) = min πe,e′
X x=1
and 1(A) is an indicator function that takes value 1 if A is true and value 0 if A is false. Allowed paths are restricted to those that minimize the number of backbones traversed in the path between two end nodes. Of those paths, they are also shortest paths within each local area. E.iii.
Proof of Lemma VI.1. Disjointness: By construction, if a path is in ΠB it cannot be in any ΠJj nor any ΠIi , and likewise paths in any ΠJj cannot be in any ΠIi . Therefore, it suffices to show that any path can be in at most one ΠJj or at most one ΠIi . Suppose that there exists some π, i, i′ with i ̸= i′ such that π ∈ ΠIi and π ∈ ΠIi′ . By definition of the set of allowed edges E ∗ , (i, i′ ) ∈ / E ∗ . Since E ⊆ E ∗ , (i, i′ ) ∈ / E, ′ thus p = (u, ..., i, •, ..., i , ..., v) for some end nodes u, v ∈ E. The only allowed edges (i, •) are (i, w) for some w ∈ E, or (i, j) for some j ∈ J. In the former case, this implies p∈ / Pvalid and hence also p ∈ / Pallowed . In the latter case, ∃k s.t. j ∈ Jk =⇒ p ∈ ΠJk . In both cases, this contradicts that p ∈ ΠIi . Therefore, no such p, i, i′ can exist. Suppose instead that there exists p, j, j ′ with j ̸= j ′ such that p ∈ ΠJj and p ∈ ΠJj′ . By the definitions of E ∗ and Pallowed , the only paths from nodes in Jj to nodes in Jj ′ is via some b ∈ B. Therefore, there exists some k such that pk = b and thus p ∈ ΠB . This contradicts that p ∈ ΠJi and so no such p, j, j ′ can exist Completeness: We proceed by construction. Consider some path p = (e, •, ...), for e ∈ E. By definition of E ∗ , and since E ⊆ E ∗ , the only possible edges (e, •) are of the form (e, i) for some i ∈ I. Then, p = (e, i, •, · · · ), for some i ∈ I. By definition of E ∗ , and since E ⊆ E ∗ , the only allowed edges are of the form (i, e′ ) for some e′ ∈ E, or (i, j) for some j ∈ J. In the former case, p ∈ Πi . In the later case, since the Jk form a disjoint partition of J, ∃k such that j ∈ Jk . Therefore, if p ∈ / ΠB , then p ∈ ΠJk . B Otherwise, p ∈ Π . Therefore, all paths in Pallowed are in some Π, and so Π forms a disjoint partition of Pallowed .
Specific Choice of Path Partition E.iv.
Lemma VI.1. Π = {ΠB } ∪ {Πj }j∈J ∪ {Πi }i∈I ,
Specific Choice of Filling Classes
Here we prove that the specific choice of filling classes used (15) in our implementation is well-behaved. Lemma E.1 (The Specific Choice of Filling Classes is Well-Behaved). Let G be an internally connected network
where ΠB , ΠJj ∀j, and ΠIi ∀i are as in Definition 13, is a disjoint partition of Pallowed . 49
in Pallowed that does not contain backbone vertices. However, since G is internally connected (Definition 5), there exists a path πb ∈ Pallowed that:
resource graph. The specific choice of filling classes Φ defined in (16) is a well-behaved set of filling classes. Proof. Let L = {Li = (Vi , Ei )} be the set of local areas of G. Let Ji = J ∩ Vi be the junction nodes in sub-graph Li . We need to show that Φ satisfies both conditions of Definition 15.
i. contains at least one backbone vertex (so πb ∈ ΠB ), ii. and traverses through resource r (since G is internally connected and Pallowed does not decrease the network connectivity, but only restricts to a particular type of shortest path between any two nodes).
1. Distinct Resource Sets: Claim: ∀ϕ, ϕ′ ∈ Φ with ϕ ̸= ϕ′ , we have ξ(Πϕ ) ̸= ξ(Πϕ′ ). Proof: We consider all possible pairs of distinct filling classes:
Therefore, r ∈ ξ(ΠB ). Since r was arbitrary, ξ(Πϕ′ ) ⊆ ξ(ΠB ). Moreover, the inclusion is proper, as B ∩ ξ(Πb ) ̸= ∅ while B ∩ ξ(Πϕ′ ) = ∅ (from Condition 1). Hence, ξ(Πϕ′ ) ⊂ ξ(ΠB ).
(a) ϕ = ϕB and ϕ′ = ϕJj for some j ∈ J. Since every path π ∈ ΠB contains at least one backbone node b ∈ B, we have B ∩ ξ(ΠB ) ̸= ∅. By definition, ΠJj ⊆ Pallowed \ ΠB , so paths in ΠJj contain no backbone nodes. Therefore B ∩ ξ(ΠJj ) = ∅. It follows that ξ(ΠB ) ̸= ξ(ΠJj ).
(b) ϕ = ϕJj and ϕ′ = ϕJj′ for j ̸= j ′ ∈ J. In case 1. (c), we noted that, with the exclusion of end nodes, local areas have disjoint vertex sets. Since paths in ΠJj , respectively ΠJj′ , are entirely contained in the local areas Lj , respectively Lj ′ , ξ(ΠJj ) ∩ ξ(ΠJj′ ) = ∅ and this case does not satisfy the premise of condition 2.
(b) ϕ = ϕB and ϕ′ = ϕIi for some i ∈ I. Similarly to case (a), ΠIi ⊆ Pallowed \ ΠB , so B ∩ ξ(ΠIi ) = ∅. But B ∩ ξ(ΠB ) ̸= ∅, so B I ξ(Π ) ̸= ξ(Πi ).
(c) ϕ = ϕJj and ϕ′ = ϕIi for some j ∈ J and i ∈ I. There are two sub-cases. If i ∈ / Vj , then ξ(ΠJj ) ∩ ξ(ΠIi ) = ∅, since distinct local areas have distinct vertex sets. Hence this subcase does not satisfy the premise of condition 2. Alternatively, i ∈ Vj and ξ(ΠJj ) ∩ ξ(ΠIi ) ̸= ∅. In this sub-case, consider arbitrary r ∈ ξ(ΠIi ). Then ∃πi ∈ ΠIi such that r ∈ πi . By definition of ΠIi and the set of local areas, all vertices in πi are in Vj . By the internal connectivity of local area Lj , there exists an allowed path πj ∈ Lj that:
(c) ϕ = ϕJj and ϕ′ = ϕJj′ for j ̸= j ′ ∈ {1, · · · , |L|}. Paths π ∈ ΠJj contain at least one junction node from Jj and paths π ′ ∈ ΠJj′ contain at least one junction node from Jj ′ . Since, with the exclusion of end nodes, local areas have disjoint vertex sets (by Definition 12 of local areas), Jj ∩ Jj ′ = ∅. Therefore, ξ(ΠJj ) ̸= ξ(ΠJj′ ). (d) ϕ = ϕJj and ϕ′ = ϕIi for some j ∈ J and i ∈ I. By definition, paths in ΠIi contain no junction nodes. Therefore, ξ(ΠIi ) ∩ Jj ′ = ∅, ∀j ′ . Paths in ΠJj on the other hand contain at least one junction node j ′ ∈ Jj , hence ξ(ΠJj ) ∩ Jj ̸= ∅. Therefore, ξ(ΠJj ) ̸= ξ(ΠIi ).
i. Contains at least one junction j ′ ∈ Jj (so πj ∈ ΠJj ), ii. and traverses resource r. Therefore, r ∈ ξ(ΠJj ). Since r was arbitrary, ξ(ΠIi ) ⊆ ξ(ΠJj ). Moreover, the inclusion is proper since, from 1. (d), Jj ∩ ξ(ΠJj ) ̸= ∅ while Jj ∩ ξ(ΠIi ) = ∅. Hence, ξ(ΠIi ) ⊂ ξ(ΠJj ).
(e) ϕ = ϕIi and ϕ′ = ϕIi′ for i ̸= i′ ∈ I. By definition, paths in ΠIi must contain the entanglement generation interface i, similarly paths in ΠIi′ must contain the entanglement generation interface i′ . Based on Definition 23 of allowed edges, E ∗ , each path in ΠIi (ΠIi′ ) can contain at most one entanglement generation interface. It follows that ξ(ΠIi ) ̸= ξ(ΠIi′ ), and moreover ξ(ΠIi ) ∩ ξ(ΠIi′ ) = ∅. 2. Intersection of Associated Resources: Claim: ∀ϕ, ϕ′ ∈ Φ with ϕ ̸= ϕ′ , if ξ(Πϕ )∩ξ(Πϕ′ ) ̸= ∅, then either ξ(Πϕ ) ⊂ ξ(Πϕ′ ) or ξ(Πϕ′ ) ⊂ ξ(Πϕ ).
(d) ϕ = ϕIi and ϕ′ = ϕIi′ for i ̸= i′ ∈ I. In 1. (e) we showed that ξ(ΠIi ) ∩ ξ(ΠIi′ ) = ∅, and thus this case does not satisfy the premise of condition 2.
E.v.
Determining the PGA Execution Time
We need to determine the duration of time Ed s.t.
Proof: In consideration of the structure of the specific choice of path partition, we analyze each case where sets of associated resources can intersect:
P [packet generated before time Ed ] ≥ ppacket .
(96)
For packets p with s = 1, this can be done with the ge(a) ϕ = ϕB and ϕ′ ∈ {ϕJj : j ∈ J, ϕIi : i ∈ I}. ometric/exponential distribution, but for packets where Consider arbitrary r ∈ ξ(Πϕ′ ). Then, ∃π ∈ Πϕ′ the number of requested pairs s > 1, the exact calculasuch that r ∈ π. By Definition 13, π is a path tion of (96) is not known. There are however results from 50
scan statistics which give very accurate estimations of this probability for a known number of attempts to generate entanglement m and probability of each attempt succeeding. Such results can be found in, e.g. [2, 72, 45, 44]. We translate between a number of attempts m of some concrete duration and each with a probability of success psucc and the rate of successful link generation Rπ on an end-to-end path π for a total duration of time Ed . For full details of our treatment of this problem, see [7], Appendix C. Every PGA from a demand d is ultimately assigned an execution time Ed that is long enough that each PGA succeeds with probability ppacket .
51
F. F.i.
Compute Network Schedule
F.i.a. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45
Code Listings
Minimal Allocation
def minimal_allocation_scheduler ( filling_class : FillingClass , n e t w o r k _ s c h e d u l e : NetworkSchedule , start_time : f l o a t ): i f not f i l l i n g _ c l a s s : return n e t w o r k _ s c h e d u l e . add_tasks_minimal ( f i l l i n g _ c l a s s ) # l o g g e r = LogManager . g e t _ r e s o u r c e _ s c h e d u l e r _ l o g g e r ( ) cycle_start_time = start_time p o n t e r s = { r : −100 f o r r i n n e t w o r k _ s c h e d u l e . s c h e d u l e . k e y s ( ) } f o r i in range ( len ( f i l l i n g _ c l a s s ) ) : cycle_time = f i l l i n g _ c l a s s . cycle_times [ i ] k = 0 f o r k i n r a n g e ( f i l l i n g _ c l a s s . numbers_of_cycles [ i ] ) : f o r j , t a s k i n enumerate ( f i l l i n g _ c l a s s [ i : ] ) : o f f s e t = sum ( t . e x e c u t i o n _ t i m e f o r t i n f i l l i n g _ c l a s s [ i : i + j ] ) _ s t a r t _ t o _ s c h e d u l e = time . p r o c e s s _ t i m e ( ) network_schedule . schedule_packet_generation_attempt ( task , cycle_start_time + cycle_time ∗ k + o f f s e t , True , pga_id=sum ( f i l l i n g _ c l a s s . numbers_of_cycles [ : i ] ) + k , s c h e d u l e _ p o i n t e r s=p o n t e r s ) _ s t a r t _ t o _ s c h e d u l e = time . p r o c e s s _ t i m e ( ) network_schedule . schedule_packet_generation_attempt ( filling_class [ i ] , cycle_start_time + cycle_time ∗ ( f i l l i n g _ c l a s s . numbers_of_cycles [ i ] ) , True , pga_id=sum ( f i l l i n g _ c l a s s . numbers_of_cycles [ : i ]) + k, s c h e d u l e _ p o i n t e r s=p o n t e r s ) c y c l e _ s t a r t _ t i m e += f i l l i n g _ c l a s s [ i ] . e x e c u t i o n _ t i m e + ( f i l l i n g _ c l a s s . numbers_of_cycles [ i ] ) ∗ c y c l e _ t i m e
Listing 1: Implementation of the minimal allocation phase of Compute Schedule, via the DirectAllocation scheduler, Algorithm 6. Note that rather than returning an updated network schedule, this subroutine simply updates the provided NetworkSchedule object.
F.i.b. 1 2 3 4 5 6 7 8 9 10 11 12 13 14
Bonus Round Robin
d e f bonus_phase_round_robin_scheduler ( filling_class : FillingClass , n e t w o r k _ s c h e d u l e : NetworkSchedule , ): # l o g g e r = LogManager . g e t _ r e s o u r c e _ s c h e d u l e r _ l o g g e r ( ) i f not f i l l i n g _ c l a s s : return _resources = [ r f o r r in network_schedule . s c h e d u l e . keys ( ) not r & 1 << get_component_id_size ( ) − 1 ] schedule_pointers = { r : 0 f o r r in _resources }
52
if
15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89
release_times_to_consider = set () round_robin_index = 0 next_start_time = 0 n e t w o r k _ s c h e d u l e . add_tasks_bonus ( f i l l i n g _ c l a s s ) d e f _get_next_start_time ( ) −> f l o a t | None : n o n l o c a l next_start_time end_times = { r : n e t w o r k _ s c h e d u l e . s c h e d u l e [ r ] [ s c h e d u l e _ p o i n t e r s [ r ] ] . end_time f o r r in _resources i f s c h e d u l e _ p o i n t e r s [ r ] < l e n ( network_schedule . s c h e d u l e [ r ] ) } # l o g g e r . debug ( f ’ c o n s i d e r i n g end t i m e s : { end_times } ’ ) _next_end_time = min ( end_times . v a l u e s ( ) ) i f end_times . v a l u e s ( ) e l s e i n f # l o g g e r . debug ( f " n e x t end time : {_next_end_time } " ) _minimising_resources = [ r f o r r i n end_times . k e y s ( ) i f math . i s c l o s e ( end_times [ r ] , _next_end_time ) ] i f _next_end_time != i n f e l s e
[]
_index , _next_release_time = min ( enumerate ( r e l e a s e _ t i m e s _ t o _ c o n s i d e r ) , key=lambda t : t [ 1 ] ) i f release_times_to_consider e l s e (0 , i n f ) # l o g g e r . debug ( f " c o n s i d e r i n g r e l e a s e t i m e s : { r e l e a s e _ t i m e s _ t o _ c o n s i d e r } " ) # l o g g e r . debug ( f " n e x t r e l e a s e time : { _next_release_time } " ) i f _next_end_time == i n f and _next_release_time == i n f : r e t u r n None i f _next_end_time <= _next_release_time : f o r r in _minimising_resources : s c h e d u l e _ p o i n t e r s [ r ] += 2 i f _next_end_time i n r e l e a s e _ t i m e s _ t o _ c o n s i d e r : r e l e a s e _ t i m e s _ t o _ c o n s i d e r . remove ( _next_end_time ) # l o g g e r . debug ( " A l s o removed end time from r e l e a s e _ t i m e s _ t o _ c o n s i d e r " ) r e t u r n _next_end_time else : r e l e a s e _ t i m e s _ t o _ c o n s i d e r . remove ( _next_release_time ) r e t u r n _next_release_time d e f _ t a s k _ i n d i c e s _ t o _ i n s p e c t ( s t a r t : i n t ) −> G e n e r a t o r [ i n t , None , None ] : f o r i in range ( len ( f i l l i n g _ c l a s s ) ) : yield ( start + i ) % len ( f i l l i n g _ c l a s s ) d e f _ r e s o u r c e s _ a v a i l a b l e ( _tts : P a c k e t G e n e r a t i o n T a s k ) −> b o o l : f o r r e s o u r c e i n _tts . path [ 1 : − 1 ] : i f s c h e d u l e _ p o i n t e r s [ r e s o u r c e ] >= l e n ( network_schedule . s c h e d u l e [ r e s o u r c e ] ) : continue i f network_schedule . s c h e d u l e [ r e s o u r c e ] [ s c h e d u l e _ p o i n t e r s [ r e s o u r c e ] ] . start_time < next_start_time + candidate_task . execution_time : return False r e t u r n True d e f _ f u t u r e _ m i n s e p _ v i o l a t i o n ( _tts : P a c k e t G e n e r a t i o n T a s k ) −> b o o l : _ r e f e r e n c e _ r e s o u r c e = _tts . path [ 1 ] _schedule_except = n e t w o r k _ s c h e d u l e . s c h e d u l e [ _ r e f e r e n c e _ r e s o u r c e ] offset = 0 while ( schedule_pointers [ _reference_resource ] + o f f s e t < len ( _schedule_except ) and _schedule_except [ schedule_pointers [ _reference_resource ] + o f f s e t
53
90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164
] . s t a r t _ t i m e < n e x t _ s t a r t _ t i m e + _tts . e x e c u t i o n _ t i m e + _tts . minsep ): i f _schedule_except [ schedule_pointers [ _reference_resource ] + o f f s e t ] . t a s k _ i d == _tts . t a s k _ i d : r e t u r n True o f f s e t += 1 return False d e f _ pa s t _ min s e p _v i o l at i o n ( _tts : P a c k e t G e n e r a t i o n T a s k ) −> Tuple [ b o o l , f l o a t | None ] : _ r e f e r e n c e _ r e s o u r c e = _tts . path [ 1 ] _schedule_excerpt = network_schedule . s c h e d u l e [ _reference_resource ] o f f s e t = 1 i f schedule_pointers [ _reference_resource ] < len ( _schedule_excerpt ) e l s e 2 while ( s c h e d u l e _ p o i n t e r s [ _ r e f e r e n c e _ r e s o u r c e ] − o f f s e t >= 0 and ( _schedule_excerpt [ schedule_pointers [ _reference_resource ] − offset ] . end_time > n e x t _ s t a r t _ t i m e − _tts . minsep and not np . i s c l o s e ( _schedule_excerpt [ schedule_pointers [ _reference_resource ] − offset ] . end_time , n e x t _ s t a r t _ t i m e − _tts . minsep ) ) ): i f _schedule_excerpt [ schedule_pointers [ _reference_resource ] − offset ] . t a s k _ i d == _tts . t a s k _ i d : r e t u r n True , _ s c h e d u l e _ e x c e r p t [ schedule_pointers [ _reference_resource ] − offset ] . end_time + _tts . minsep o f f s e t += 1 i f schedule_pointers [ _reference_resource ] − o f f s e t < 0: break r e t u r n F a l s e , None if
a l l ( network_schedule . s c h e d u l e [ r ] [ 0 ] . start_time > 0 f o r r in s c h e d u l e _ p o i n t e r s . keys ( ) i f network_schedule . s c h e d u l e [ r ] ) : n e x t _ s t a r t _ t i m e = min ( n e t w o r k _ s c h e d u l e . s c h e d u l e [ r ] [ 0 ] . end_time f o r r i n schedule_pointers . keys ( ) )
while next_start_time < network_schedule . l e n g t h : c y c l e _ s t a r t _ t i m e = time . p r o c e s s _ t i m e ( ) f o r i n d e x i n _ t a s k _ i n d i c e s _ t o _ i n s p e c t ( round_robin_index ) : candidate_task = f i l l i n g _ c l a s s [ index ] # l o g g e r . debug ( f ’ c a n d i d a t e _ t a s k : { c a n d i d a t e _ t a s k } ’ ) if ( not _ r e s o u r c e s _ a v a i l a b l e ( c a n d i d a t e _ t a s k ) or _future_minsep_violation ( candidate_task ) or next_start_time > candidate_task . expiry_time o r n e x t _ s t a r t _ t i m e + c a n d i d a t e _ t a s k . e x e c u t i o n _ t i m e >= n e t w o r k _ s c h e d u l e . l e n g t h ): continue p a s t _ m i n s e p _ v i o l a t i o n , r e l e a s e _ t i m e = _ p as t _ m i ns e p _ vi o l a t io n ( candidate_task )
54
165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195
i f past_minsep_violation : i f release_time > next_start_time : r e l e a s e _ t i m e s _ t o _ c o n s i d e r . add ( r e l e a s e _ t i m e ) continue network_schedule . schedule_packet_generation_attempt ( candidate_task , next_start_time , False , s c h e d u l e _ p o i n t e r s=s c h e d u l e _ p o i n t e r s ) round_robin_index = i n d e x + 1 old_start_time = 0 + next_start_time n e x t _ s t a r t _ t i m e = _get_next_start_time ( ) i f n e x t _ s t a r t _ t i m e i s None : return a s s e r t old_start_time < next_start_time # l o g g e r . debug ( f " Completed c y c l e i n time { time . p r o c e s s _ t i m e ( ) − c y c l e _ s t a r t _ t i m e : . 5 g } " ) i f n e x t _ s t a r t _ t i m e i s None : break # l o g g e r . debug ( f " n e x t s t a r t time i s { n e x t _ s t a r t _ t i m e } " ) pass
Listing 2: Implementation of Algorithm 7 (BonusRoundRobin) in Python. Note that rather than returning an updated network schedule, this subroutine simply updates the provided NetworkSchedule object.
F.i.c. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36
Complete Scheduler
def complete_schedule_scheduler ( filling_classes : SetOfFillingClasses , n e t w o r k _ s c h e d u l e : NetworkSchedule , ) −> Tuple [ f l o a t , f l o a t ] : l o g g e r = LogManager . g e t _ r e s o u r c e _ s c h e d u l e r _ l o g g e r ( ) _start_minimal = time . p r o c e s s _ t i m e ( ) l o g g e r . i n f o ( " Computing ␣ Minimal ␣ S c h e d u l e " ) for f i l l i n g _ c l a s s in f i l l i n g _ c l a s s e s . a l l _ f i l l i n g _ c l a s s e s : l o g g e r . debug ( f " S t a r t i n g ␣ t o ␣ compute ␣ minimal ␣ s c h e d u l e ␣ f o r ␣ f i l l i n g ␣ c l a s s ␣ { f i l l i n g _ c l a s s } " ) s t a r t _ t i m e = sum ( f c . minimum_service_time f o r f c i n filling_classes . preceding_filling_classes [ filling_class ]) m i n i m a l _ a l l o c a t i o n _ s c h e d u l e r ( f i l l i n g _ c l a s s , network_schedule , start_time ) minimal_time = time . p r o c e s s _ t i m e ( ) − _start_minimal l o g g e r . debug ( f " Completed ␣ minimal ␣ phase ␣ i n ␣ time ␣ { time . p r o c e s s _ t i m e ( ) ␣−␣ _start_minimal : . 5 g } " ) _start_bonus = time . p r o c e s s _ t i m e ( ) l o g g e r . i n f o ( " Computing ␣ Bonus ␣ S c h e d u l e " ) for fc in f i l l i n g _ c l a s s e s . a l l _ f i l l i n g _ c l a s s e s : l o g g e r . debug ( f " S t a r t i n g ␣ t o ␣ compute ␣ bonus ␣ s c h e d u l e ␣ f o r ␣ f i l l i n g ␣ c l a s s ␣ { f c } " ) bonus_phase_round_robin_scheduler ( f c , n e t w o r k _ s c h e d u l e ) bonus_time = time . p r o c e s s _ t i m e ( ) − _start_bonus l o g g e r . debug ( f " Completed ␣ bonus ␣ phase ␣ i n ␣ time ␣ { time . p r o c e s s _ t i m e ( ) ␣−␣ _start_bonus : . 5 g } "
55
37 38 39
) r e t u r n minimal_time , bonus_time
Listing 3: Implementation of Algorithm 3 in Python.
F.ii. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48
Admit New Tasks
d e f admit_new_tasks ( f i l l i n g _ c l a s s e s : S e t O f F i l l i n g C l a s s e s , t a s k _ i n t a k e _ o b j e c t : D i c t [ i n t , L i s t [ P a c k e t G e n e r a t i o n T a s k ] ] , r e s o u r c e s : L i s t [ i n t ] ) −> D i c t [ i n t , i n t ] : """ ␣ ␣ ␣ ␣ : param␣ f i l l i n g _ c l a s s e s : ␣ s e t ␣ o f ␣ f i l l i n g ␣ c l a s s e s ␣ ␣ ␣ ␣ : param␣ t a s k _ i n t a k e _ o b j e c t : ␣ t a s k ␣ i n t a k e ␣ o b j e c t ␣ i n ␣ f o r m a t ␣ {demand_id : [ PGT] } ␣ ␣ ␣ ␣ : param␣ r e s o u r c e s : ␣ l i s t ␣ o f ␣ r e s o u r c e s ␣ ␣ ␣ ␣ : r e t u r n : ␣ l i s t ␣ o f ␣ a c c e p t e d ␣ demands ␣␣␣␣""" l o g g e r = LogManager . g e t _ a d m i s s i o n _ c o n t r o l _ l o g g e r ( ) available_time = { r : get_scheduling_interval_duration () for r in resources } for f i l l i n g _ c l a s s in f i l l i n g _ c l a s s e s . a l l _ f i l l i n g _ c l a s s e s : for resource in f i l l i n g _ c l a s s . associated_resources : a v a i l a b l e _ t i m e [ r e s o u r c e ] −= f i l l i n g _ c l a s s . minimum_service_time accepted_demands = {} f o r demand i n t a s k _ i n t a k e _ o b j e c t : l o g g e r . i n f o ( f " C o n s i d e r i n g ␣demand␣ {demand} " ) f o r pgt_to_admit i n t a s k _ i n t a k e _ o b j e c t [ demand ] : l o g g e r . i n f o ( f " C o n s i d e r i n g ␣PGT␣ { pgt_to_admit } " ) try : f i l l i n g _ c l a s s = f i l l i n g _ c l a s s e s . g e t _ f i l l i n g _ c l a s s ( pgt_to_admit ) except F i l l i n g C l a s s E r r o r : l o g g e r . i n f o ( f " R e j e c t e d ␣PGT␣ { pgt_to_admit } ␣ b e c a u s e ␣ no ␣ f i l l i n g ␣ c l a s s ␣ was ␣ found " ) continue for resource in f i l l i n g _ c l a s s . associated_resources : a v a i l a b l e _ t i m e [ r e s o u r c e ] += f i l l i n g _ c l a s s . minimum_service_time f i l l i n g _ c l a s s . add_packet_generation_task ( pgt_to_admit ) i f a l l ( a v a i l a b l e _ t i m e [ r e s o u r c e ] − f i l l i n g _ c l a s s . minimum_service_time > 0 f o r r e s o u r c e i n f i l l i n g _ c l a s s . associated_resources ) :
accepted_demands [ demand ] = pgt_to_admit . t a s k _ i d for resource in f i l l i n g _ c l a s s . associated_resources : a v a i l a b l e _ t i m e [ r e s o u r c e ] −= f i l l i n g _ c l a s s . minimum_service_time l o g g e r . debug ( f " Remaining ␣ a v a i l a b l e ␣ time : ␣ { a v a i l a b l e _ t i m e } " ) l o g g e r . i n f o ( f " a c c e p t e d ␣demand : ␣ {demand} ␣ with ␣PGT␣ { pgt_to_admit } " ) break else : l o g g e r . i n f o ( f " r e j e c t e d ␣PGT␣ f o r ␣ i n s u f f i c i e n t ␣ time . ␣Demand␣ID : ␣ {demand } , ␣PGT: ␣ { pgt_to_admit } " ) f i l l i n g _ c l a s s . remove ( pgt_to_admit ) for resource in f i l l i n g _ c l a s s . associated_resources : a v a i l a b l e _ t i m e [ r e s o u r c e ] −= f i l l i n g _ c l a s s . minimum_service_time r e t u r n accepted_demands
Listing 4: Implementation of Algorithm 5 in Python.
F.iii.
Update Filling Classes
56
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36
c l a s s CompletedDemands : expired_demands : L i s t [ i n t ] = d a t a c l a s s e s . f i e l d ( d e f a u l t _ f a c t o r y= l i s t ) removed_demands : L i s t [ i n t ] = d a t a c l a s s e s . f i e l d ( d e f a u l t _ f a c t o r y= l i s t ) terminated_demands : L i s t [ i n t ] = d a t a c l a s s e s . f i e l d ( d e f a u l t _ f a c t o r y= l i s t ) @property d e f all_removed_demands ( s e l f ) : r e t u r n s e l f . removed_demands + s e l f . terminated_demands + s e l f . expired_demands def update_filling_classes ( o l d _ f i l l i n g _ c l a s s e s : S e t O f F i l l i n g C l a s s e s | None , p a t h _ p a r t i t i o n : L i s t [ S e t [ Tuple [ i n t , . . . ] ] ] | None , termination_buffer : Set [ i n t ] , expiration_cutoff_time : f l o a t ) −> Tuple [ SetOfFillingClasses , CompletedDemands , ]: completed_demands = CompletedDemands ( ) i f p a t h _ p a r t i t i o n i s not None : new_filling_classes = SetOfFillingClasses ( path_partition ) f a i l e d _ t a s k s = n e w _ f i l l i n g _ c l a s s e s . a d d _ p ac k e t _ g e n er a t i o n _ ta s k s ( o l d _ f i l l i n g _ c l a s s e s . a l l _ t a s k s if old_filling_classes else [ ] ) completed_demands . removed_demands = [ t . parent_demand_id f o r t i n f a i l e d _ t a s k s ] else : new_filling_classes = old_filling_classes expired , terminated = n e w _ f i l l i n g _ c l a s s e s . update_live_tasks ( termination_buffer , expiration_cutoff_time ) completed_demands . expired_demands = [ t a s k . parent_demand_id f o r t a s k i n e x p i r e d ] completed_demands . terminated_demands = [ t a s k . parent_demand_id f o r t a s k i n t e r m i n a t e d ] r e t u r n n e w _ f i l l i n g _ c l a s s e s , completed_demands
Listing 5: Implementation of Algorithm 4 (UpdateFillingClasses)
57
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74
c l a s s F i l l i n g C l a s s ( L i s t [ PacketGenerationTask ] ) : d e f __init__ ( s e l f , p a t h _ p a r t i t i o n : S e t [ Tuple [ i n t , . . . ] ] ) −> None : s u p e r ( ) . __init__ ( ) s e l f . _ p a t h _ p a r t i t i o n : S e t [ Tuple [ i n t , . . . ] ] = p a t h _ p a r t i t i o n s e l f . _ a s s o c i a t e d _ r e s o u r c e s : S e t [ i n t ] | None = None s e l f . _numbers_of_cycles : L i s t [ i n t ] | None = None s e l f . _cycle_times : L i s t [ f l o a t ] | None = None s e l f . _minimum_service_time : f l o a t | None = None d e f _ c a l c u l a t e _ a s s o c i a t e d _ r e s o u r c e s ( s e l f ) −> None : s e l f . _associated_resources = set ( [ r f o r path i n s e l f . _ p a t h _ p a r t i t i o n f o r r i n path [ 1 : − 1 ] ] ) @property def path_partition ( s e l f ) : return s e l f . _path_partition @property def associated_resources ( s e l f ) : i f s e l f . _ a s s o c i a t e d _ r e s o u r c e s i s None : s e l f . _calculate_associated_resources () return s e l f . _associated_resources @property d e f a s s o c i a t e d _ n o d e s ( s e l f ) −> S e t [ i n t ] : r e t u r n { r f o r path i n s e l f . _ p a t h _ p a r t i t i o n f o r r i n path } def calculate_cycle_times ( s e l f ) : # s e l f . s o r t ( key=lambda t a s k : t a s k . minimum_allocation ) s e l f . _cycle_times = [ max ( [ t . e x e c u t i o n _ t i m e + t . minsep f o r t i n s e l f [ i : ] ] + [ sum ( t . e x e c u t i o n _ t i m e f o r t i n s e l f [ i : ] ) ] ) f o r i i n range ( len ( s e l f ) ) ] pass def calculate_numbers_of_cycles ( s e l f ) : # s e l f . s o r t ( key=lambda t a s k : t a s k . minimum_allocation ) _ l i s t = [ t . minimum_allocation f o r t i n s e l f ] f o r i i n r a n g e ( l e n ( s e l f ) − 1 , 0 , −1) : _list [ i ] = _list [ i ] − _list [ i − 1] _ l i s t [ 0 ] −= 1 s e l f . _numbers_of_cycles = _ l i s t d e f calculate_minimum_service_time ( s e l f ) −> None : s e l f . _minimum_service_time = sum ( x ∗ y f o r x , y i n z i p ( s e l f . numbers_of_cycles , s e l f . c y c l e _ t i m e s ) ) + sum ( t . execution_time f o r t in s e l f ) d e f remove_expired_tasks ( s e l f , c u t o f f _ t i m e : f l o a t ) −> L i s t [ PacketGenerationTask ] : expired_tasks = [ task f o r task in s e l f i f t a s k . e x p i r y _ t i m e <= c u t o f f _ t i m e ] s e l f [ : ] = [ t a s k f o r t a s k i n s e l f i f t a s k not i n e x p i r e d _ t a s k s ] return expired_tasks d e f remove_terminated_demands ( s e l f , terminated_demands : I t e r a b l e [ i n t ] ) −> \ L i s t [ PacketGenerationTask ] : terminated_tasks = [ task f o r task in s e l f i f t a s k . parent_demand_id i n terminated_demands ] s e l f [ : ] = [ t a s k f o r t a s k i n s e l f i f t a s k not i n t e r m i n a t e d _ t a s k s ] return terminated_tasks def update_live_tasks ( self , terminated_demands : S e t [ i n t ] ,
58
75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149
current_time : f l o a t ) −> Tuple [ L i s t [ PacketGenerationTask ] , L i s t [ PacketGenerationTask ] , ]: e x p i r e d _ t a s k s = s e l f . remove_expired_tasks ( c u r r e n t _ t i m e ) t e r m i n a t e d _ t a s k s = s e l f . remove_terminated_demands ( terminated_demands ) if
self : s e l f . calculate_numbers_of_cycles ( ) s e l f . calculate_cycle_times () s e l f . calculate_minimum_service_time ( ) else : s e l f . _numbers_of_cycles = None s e l f . _cycle_times = None s e l f . _minimum_service_time = None return expired_tasks , terminated_tasks @property d e f numbers_of_cycles ( s e l f ) : i f s e l f . _numbers_of_cycles i s None o r l e n ( s e l f . _numbers_of_cycles ) != l e n ( s e l f ) : s e l f . calculate_numbers_of_cycles ( ) r e t u r n s e l f . _numbers_of_cycles @property def cycle_times ( s e l f ) : i f s e l f . _cycle_times i s None o r l e n ( s e l f . _cycle_times ) != l e n ( s e l f ) : s e l f . calculate_cycle_times () r e t u r n s e l f . _cycle_times @property d e f minimum_service_time ( s e l f ) : i f not s e l f : return 0 if
s e l f . _minimum_service_time i s None : s e l f . calculate_minimum_service_time ( ) r e t u r n s e l f . _minimum_service_time d e f add_packet_generation_task ( s e l f , t a s k : P a c k e t G e n e r a t i o n T a s k ) : i f not i s i n s t a n c e ( t a s k , P a c k e t G e n e r a t i o n T a s k ) : r a i s e TypeError ( f ’ Task ␣ must ␣ be ␣ o f ␣ t y p e ␣ P a c k e t G e n e r a t i o n T a s k ␣ ( p r o v i d e d ␣ t y p e ␣ { t y p e ( t a s k ) } ) ’ ) _i = 0 w h i l e _i < l e n ( s e l f ) and s e l f [ _i ] . minimum_allocation < t a s k . minimum_allocation : _i += 1 s e l f . i n s e r t ( _i , t a s k ) s e l f . _numbers_of_cycles = None s e l f . _cycle_times = None s e l f . _minimum_service_time = None def clear ( s e l f ) : super () . c l e a r () s e l f . _numbers_of_cycles = None s e l f . _cycle_times = None s e l f . _minimum_service_time = None d e f append ( s e l f , t a s k : P a c k e t G e n e r a t i o n T a s k ) : i f not i s i n s t a n c e ( t a s k , P a c k e t G e n e r a t i o n T a s k ) : r a i s e TypeError ( f " Task ␣ must ␣ be ␣ o f ␣ t y p e ␣ P a c k e t G e n e r a t i o n T a s k ␣ ( p r o v i d e d ␣ t y p e ␣ { t y p e ( t a s k ) } ) " ) else : s u p e r ( ) . append ( t a s k ) s e l f . _numbers_of_cycles = None s e l f . _cycle_times = None s e l f . _minimum_service_time = None d e f remove ( s e l f , __value ) : s u p e r ( ) . remove ( __value )
59
150 151 152
s e l f . _numbers_of_cycles = None s e l f . _cycle_times = None s e l f . _minimum_service_time = None
Listing 6: Implementation of a single filling classes ϕ. Any properties of a filling class (e.g. minimum_service_time) which are None when called are calculated and stored. This means that subsequent calls to get the property only require O(1) time rather than recomputing the value each time. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53
class SetOfFillingClasses : d e f __init__ ( s e l f , p a t h _ p a r t i t i o n : L i s t [ S e t [ Tuple [ i n t ,
. . . ] ] ] ) −> None :
s e l f . _all_filling_classes : List [ FillingClass ] = [ FillingClass ( partition ) for partition in path_partition ] s e l f . _ a l l _ f i l l i n g _ c l a s s e s . s o r t ( r e v e r s e=True ) s e l f . _ p r e c e d i n g _ f i l l i n g _ c l a s s e s : Dict [ F i l l i n g C l a s s , Set [ F i l l i n g C l a s s ] ] = { f c : { _fc f o r _fc i n s e l f . _ a l l _ f i l l i n g _ c l a s s e s i f _fc > f c } i f f c . p a t h _ p a r t i t i o n e l s e s e t () for fc in self . _all_filling_classes } s e l f . _ i n t e r f a c e _ f i l l i n g _ c l a s s e s : L i s t [ F i l l i n g C l a s s ] | None = None s e l f . _ l o c a l _ a r e a _ f i l l i n g _ c l a s s e s : L i s t [ F i l l i n g C l a s s ] | None = None s e l f . _ b a c k b o n e _ f i l l i n g _ c l a s s e s : L i s t [ F i l l i n g C l a s s ] | None = None d e f a d d_ p a c k e t _ ge n e r a t i on _ t a s k s ( s e l f , pgts_to_add : I t e r a b l e [ P a c k e t G e n e r a t i o n T a s k ] ) −> L i s t [ P a c k e t G e n e r a t i o n T a s k ] : f a i l e d _ t a s k s : L i s t [ PacketGenerationTask ] = [ ] f o r pgt i n pgts_to_add : try : s e l f . g e t _ f i l l i n g _ c l a s s ( pgt ) . add_packet_generation_task ( pgt ) except F i l l i n g C l a s s E r r o r : f a i l e d _ t a s k s . append ( pgt ) return failed_tasks def update_live_tasks ( self , terminated_demands : S e t [ i n t ] , current_time : f l o a t ) −> Tuple [ L i s t [ PacketGenerationTask ] , L i s t [ PacketGenerationTask ] , ]: expired_tasks = [ ] terminated_tasks = [ ] for f i l l i n g _ c l a s s in s e l f . a l l _ f i l l i n g _ c l a s s e s : _ex , _term = f i l l i n g _ c l a s s . u p d a t e _ l i v e _ t a s k s ( terminated_demands , current_time ) e x p i r e d _ t a s k s . e x t e n d ( _ex ) t e r m i n a t e d _ t a s k s . e x t e n d ( _term ) return expired_tasks , terminated_tasks d e f g e t _ f i l l i n g _ c l a s s ( s e l f , pgt : P a c k e t G e n e r a t i o n T a s k ) −> F i l l i n g C l a s s : for f i l l i n g _ c l a s s in s e l f . _all_filling_classes : i f pgt . path i n f i l l i n g _ c l a s s . p a t h _ p a r t i t i o n : return f i l l i n g _ c l a s s r a i s e F i l l i n g C l a s s E r r o r ( "No␣known␣ f i l l i n g ␣ c l a s s ␣ f o r ␣ pgt " )
Listing 7: Implementation of the set of filling classes Φ. Any properties of a filling class (e.g. minimum_service_time) which are None when called are calculated and stored. This means that subsequent calls to get the property only require O(1) time rather than recomputing the value each time.
F.iv. 1 2
Network Schedules
c l a s s PacketGenerationAttempt ( ArqonDataRecord ) : src : int
60
3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64
dst : int start_time : f l o a t end_time : f l o a t task_id : i n t demand_id : O p t i o n a l [ i n t ] pga_id : O p t i o n a l [ i n t ] is_minimal : b o o l c l a s s R e s o u r c e S c h e d u l e ( L i s t [ PacketGenerationAttempt ] ) : d e f __init__ ( s e l f , r e s o u r c e _ i d : i n t , s e q : t u p l e = ( ) ) : s u p e r ( ) . __init__ ( s e q ) s e l f . _resource_id = resource_id @property def resource_id ( s e l f ) : r e tu r n s e l f . _resource_id
d e f add_pga ( s e l f , __object : PacketGenerationAttempt , p o i n t e r : O p t i o n a l [ i n t ] = None ) : """ ␣ ␣ ␣ ␣ ␣ ␣ ␣ ␣ re −w r i t t e n ␣ append ␣ method ␣ t o ␣ e n s u r e ␣ time−o r d e r i n g ␣ o f ␣PGAs . ␣ ␣ ␣ ␣ ␣ ␣ ␣ ␣ : param␣ __object : ␣ PacketGenerationAttempt ␣ t o ␣ add ␣ t o ␣ r e s o u r c e ␣ s c h e d u l e . ␣ ␣ ␣ ␣ ␣ ␣ ␣ ␣ : param␣ p o i n t e r : ␣ i n d e x ␣ o f ␣PGA␣ p r e c e d i n g ␣ r e q u e s t e d ␣ time ␣␣␣␣␣␣␣␣""" i f not i s i n s t a n c e ( __object , PacketGenerationAttempt ) : r a i s e TypeError ( f " Only ␣ t y p e ␣ PacketGenerationAttempt ␣ i s ␣ a l l o w e d . ␣ ( s u p p l i e d ␣ { t y p e ( __object ) }) " ) else : i f not s e l f : s u p e r ( ) . append ( __object ) return if
p o i n t e r i s None : p o i n t e r = _bs ( s e l f , __object . end_time ) if
pointer > 0: s e l f . i n s e r t ( p o i n t e r + 1 , __object ) e l i f s e l f [ p o i n t e r ] . end_time < __object . end_time : s e l f . i n s e r t ( 1 , __object ) else : s e l f . i n s e r t ( 0 , __object ) else : if
p o i n t e r == 0 : s e l f . i n s e r t ( p o i n t e r , __object ) e l i f pointer > 0: s e l f . i n s e r t ( p o i n t e r , __object ) e l i f pointer < 0: s u p e r ( ) . append ( __object )
return { " node " : s e l f . r e s o u r c e _ i d , " p a c k e t _ g e n e r a t i o n _ a t t e m p t s " : [ pga . t o _ d i c t ( ) f o r pga i n s e l f ] }
c l a s s NetworkSchedule : d e f __init__ ( s e l f , s t a r t _ t i m e : f l o a t , l e n g t h : f l o a t , r e s o u r c e s : L i s t [ i n t ] , None = None ) :
i d e n t i f i e r : int |
s e l f . _schedule : Dict [ int , ResourceSchedule ] = { r : ResourceSchedule ( r ) f o r r in r e s o u r c e s }
Listing 8: Implementation of the network schedule.
61