A novel approach to quality-of-service provisioning in trusted relay Quantum Key Distribution networks

168 IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 28, NO. 1, FEBRUARY 2020 A Novel Approach to Quality-of-Service Provisioning in Trusted Relay Quantum Key Distribution Networks Miralem Mehic ,Member, IEEE, Peppino Fazio, Member, IEEE,StefanRass ,Member, IEEE, Oliver Maurhart, Member, IEEE, Momtchil Peev, Member, IEEE, Andreas Poppe, Member, IEEE, Jan Rozhon, Member, IEEE, Marcin Niemiec, Senior Member, IEEE, and Miroslav Voznak ,Senior Member, IEEE Abstract— In recent years, noticeable progress has been made in the development of quantum equipment, reflected through the number of successful demonstrations of Quantum Key Distribution (QKD) technology. Although they showcase the great achievements of QKD, many practical difficulties still need to be resolved. Inspired by the significant similarity between mobile ad-hoc networks and QKD technology, we propose a novel quality of service (QoS) model including new metrics for determining the states of public and quantum channels as well as a comprehensive metric of the QKD link. We also propose a novel routing protocol to achieve high-level scalability and minimize consumption of cryptographic keys. Given the limited mobility of nodes in QKD networks, our routing protocol uses the geographical distance and calculated link states to determine the optimal route. It also benefits from a caching mechanism and detection of returning loops to provide effective forwarding while minimizing key consumption and achieving the desired utilization of network links. Simulation results are presented to demonstrate the validity and accuracy of the proposed solutions. Index Terms— Quantum key distribution, quality of service, routing protocol, real-time traffic. I. INTRODUCTION DURING the 30 years since the discovery of the first quantum protocol [1], quantum technology has grown significantly and is rapidly approaching high levels of maturity. Manuscript received December 4, 2017; revised May 25, 2018 and December 15, 2018; accepted November 9, 2019; approved by IEEE/ACM TRANSACTIONS ON NETWORKING Editor P. Papadimitratos. Date of publication December 17, 2019; date of current version February 14, 2020. This work was supported in part by the H2020 project OpenQKD under Grant 857156, in part by the institutional grant SGS conducted at the Technical University of Ostrava under Grant SP2019/41, in part by the ESF in Science without borders project within the Operational Programme Research, Development and Education under Grant CZ.02.2.69/0.0/0.0/16 027/0008463, and in part by the Ministry of Education, Science and Youth of Canton Sarajevo, Bosnia and Herzegovina, under Grant 11/05-14-27719-1/19. (Corresponding author: Miralem Mehic.) M. Mehic is with the Department of Telecommunications, Faculty of Electrical Engineering, University of Sarajevo, 71000 Sarajevo, Bosnia and Herzegovina, and also with the VSB–Technical University of Ostrava, 708 33 Ostrava-Poruba, Czech Republic (e-mail: miralem.m[email protected]). P. Fazio, J. Rozhon, and M. Voznak are with the VSB–Technical University of Ostrava, 708 00 Ostrava, Czech Republic. S. Rass is with the System Security Group, Institute of Applied Informatics, Universitaet Klagenfurt, 9020 Klagenfurt, Austria. O. Maurhart and A. Poppe are with the Security and Communication Technologies, Center for Digital Safety and Security, AIT Austrian Institute of Technology GmbH, 1220 Vienna, Austria. M. Peev is with the Optical and Quantum Laboratory, Munich Research Center, Huawei Technologies Duesseldorf GmbH, 80992 Munich, Germany. M. Niemiec is with the Department of Telecommunications, AGH University of Science and Technology, 30-059 Krakow, Poland. Digital Object Identifier 10.1109/TNET.2019.2956079 The next natural step in the evolution of quantum systems is to study their performance, suitability and convergence with applications used in everyday life. Significant progress in the development of quantum equipment has been reflected through a number of successful demonstrations of QKD networks [2]–[7] but without showing the clear suitability to assess how such networks compete with their classical counterparts under real-life conditions and in real-time traffic. The traffic in these networks was mainly considered with equal importance, and it was treated with the same priority. While such approach may be acceptable for some applications, it is not suitable for voice, video and collaborative applications. Since not all network traffic is equal, it should not be treated equally. Hence, different applications may have different service requirements with respect to the quality of service (QoS). This paper addresses the question of using real-time communication in QKD networks by considering QoS mechanisms. The primary goal is to provide an adequate QoS model that includes traffic classification and marking mechanisms, QKD link metrics that can be used to describe the state of the network accurately, and a scalable routing protocol that minimizes the consumption of key material through the equitable utilization of network resources. QKD networks differ from traditional networks in several aspects: •Although theoretical and pioneering results have been published in the field of quantum repeaters and quantum relays [8]–[10], in practice they remain unachievable with current technology1[11], [13]. Therefore, communication is realized in a hop-by-hop [2] or key relay manner [3], [14]. Both methods rely on the assumption that all nodes along the path between the sender and the receiver must be fully trusted, forming a trusted relay QKD network [2], [15], [16]. 1The idea behind implementing quantum routers is to use quantum entanglement of photons to communicate over different quantum channels. In short, it means that multiple particles are linked together such that the measurement of one particle’s quantum state determines the possible quantum states of the other particles. Even when the particles are separated by a considerable distance, they still make up a joint quantum system. The fidelity of a quantum state decreases exponentially with the distance of its qubits due to noisy quantum channels [11], [12]. In addition, quantum memory is required to implement a quantum repeater according to [9], [10]. Although implementations of quantum memories exist, which can store a qubit for between several milliseconds to one second or even more, this is still too short for practical applications. This work is licensed under a Creative Commons Attribution 4.0 License. For more information, see http://creativecommons.org/licenses/by/4.0/ MEHIC et al.: NOVEL APPROACH TO QoS PROVISIONING IN TRUSTED RELAY QKD NETWORKS 169 •Nodes are connected with QKD logical links, referred to below as links, which employ two distinct channels: a quantum channel, which is used for transmission of raw cryptographic keys encoded in certain photon properties, and a public channel, used for verification and processing of the exchanged values. Each quantum channel is always a point-to-point connection between exactly two nodes [17], while public channels can be implemented as any conventional connection which can include an arbitrary number of intermediate devices [18]. •The key rate is interconnected with a length of optical fiber such that a longer distance implies a lower key rate due to absorption and scattering of photons [11], [19]–[22]. Although key rates of 1 Mbps and above have been achieved [5], [23]–[25], such solutions are limited to very short distances. Therefore, both endpoints of the corresponding link implement key buffers (storages) of limited capacity, which are gradually filled at their maximum key rate with the processed cryptographic key, referred to below as key material, and subsequently used for encryption/decryption of data flow [17], [26]. Key material denotes the symmetric cryptographic keys that are generated during the QKD process, stored in buffers (storages) and used subsequently for cryptographic operations over user traffic. •Without key material, cryptographic operations cannot be performed, and a link can be described as temporarily unavailable [15]. To provide information-theoretically secure (ITS) communication, the key tends to be applied with a One-Time Pad (OTP) cipher and authenticated using an ITS message authentication scheme such as Wegman-Carter when communicating over a public channel [27]–[29]. As a result, ITS communication requires more bits of key material than the length of the secured message [17]. The type of encryption algorithm used and the volume of network traffic to be encrypted determines the key storage emptying speed, referred to as the key consumption rate. The key consumption rate denotes the rate of key material being taken from buffers (storages) and used for cryptographic operations. Similarly, the charging key rate (or simply key rate) denotes the rate of new key material generation, that is, the rate of adding new keys to the buffers (storages) [3], [17], [30]. •To meet the requirement to bypass untrusted nodes, in practice, QKD networks are usually deployed as overlay point-to-point networks which exhibit selfish behavior, acting strategically to optimize performance and resulting in dynamic and unpredictable link performance [17], [26], [31]–[33]. Overlay networks use existing underlying networks in an attempt to implement a better service; one of their most important features is the independence of the path offered by Internet service providers (ISP). This paper is organized as follows: Section II covers related work, Section III points out the significant resemblance between QKD and ad-hoc networks, and Section IV defines the requirements for providing QoS in QKD networks. In Section V we propose a novel QoS model including a GPSRQ routing protocol. The simulation setup is presented in Section VII, with Section VII-A presenting the evaluation of obtained results. Section VIII concludes the paper. II. RELATED WORK Given the common assumption that all nodes along a path in a QKD network must be fully trusted [15], [16], QKD networks were mainly analyzed from two aspects: security and network performance. The idea of passive eavesdropping, in which the adversary may use eavesdropping not to extract information but to redirect the data flow towards a node under their control, has been analyzed in [34]. Following a similar idea, stochastic routing has been proposed to avoid deterministic routing which is used in traditional routing protocols [35], [36]. Game-theoretic techniques have been used to find an optimal balance between interdependent service quality criteria with distinct performance indicators [37]. QoS in QKD networks deployed previously has been largely neglected, stating that it is somehow achievable without any difficulties. Therefore, the Open Shortest Path First (OSPFv2) routing protocol has been modified to use the amount of key material as the routing metric while ignoring the performance of the public channel [26], [38]. In [39], the author proposes using unencrypted and non-authenticated communication for the dissemination of OSPFv2 routing packets; this is simple prey for an eavesdropper who is assumed to have unlimited resources at their disposal, especially when passive eavesdropping is taken into account [34]. In [40], [41], unmodified OSPFv2 was combined with reserving key material resources. Considering the interdependence of the public and quantum channels [42], reservation of key material resources does not solve the problem of QoS since the routing path may be inadequate for quantum channels. III. SIMILARITIES BETWEEN QKD AND MANET TECHNOLOGIES The specific QKD issues and constraints described above pose significant challenges in QKD network design. However, by analyzing the characteristics of QKD networks, we note similarities with Mobile Ad Hoc Networks (MANET) [43]–[45]. First, we specify the main characteristics of QKD technology from a simple point of view: •QKD links, described above, due to features of quantum channels, are always implemented in point-to-point behavior, and they can be roughly characterized by two features: limited distance and key rate inversely proportional to the distance [17]. Additionally, QKD links may become unavailable when there is no enough key material or when the public channel is congested [42]. Such behavior is similar to Wi-Fi links which are limited in length and where the communication speed depends on the user’s distance from the transmitter. •One of the main features of QKD networks is the absence of a quantum repeater or quantum router in practice, therefore communication is usually performed on a hopby-hop basis [13], [17]. In MANET, communication takes place on a hop-by-hop basis, and mobile nodes are typically powered by batteries, 170 IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 28, NO. 1, FEBRUARY 2020 placing special attention on energy-aware solutions. The nodes connect themselves in a decentralized, self-organizing manner with no authority in charge of managing and controlling the network [44], [46]. The battery power in MANET nodes can be easily linked to the amount of key material in QKD key storages. Given the node without a power supply (empty batteries) is not an active member of the network, the same analogy is valid for QKD networks where the node without available key material cannot be used for data transmission. The range limitations of wireless links can be mapped to the limitations in the length of QKD links, while the absence of dedicated network infrastructure (such as a router) is common to MANET and QKD. Here we recognize the significant similarity between these two technologies, allowing us to propose a new approach to addressing QKD network issues. IV. QOSIN QKD NETWORKS The specific QKD constraints described above lead to the conclusion that this type of network provides weak support to QoS. A. QoS Models 1) Integrated Service and QKD Networks: The basic concept of the Integrated Service (IntServ) model is a per-flow resource reservation using the Signaling Resource ReSerVation Protocol (RSVP) before data transmission [47]. In our view, the IntServ model is not suitable for QKD networks because of the following: •An inability to guarantee the reservation: when QoS is provided in an IP network, an IP router has complete control over its packet buffers and the output link bandwidth, and can directly schedule these resources. In contrast, in an overlay network, the node cannot directly access the available resources in the overlay path. It can only rely on measurement techniques where high accuracy cannot be guaranteed and it cannot directly control or reserve resources in the underlying network. The only thing that a node in a QKD network is able to do is to guarantee resources of a quantum channel by reserving key material in key storages. However, considering the interdependence of public and quantum channels in a QKD link [42], such reservation does not constitute any gain. •Signaling: RSVP is an out-of-band signalization protocol which means that signaling packets contend for network resources with data packets and consume a substantial amount of scarce key material and network resources. 2) Differentiated Service and QKD Networks: Differentiated Service (DiffServ) uses Differentiated Services Code Point (DSCP) bits in the IP header and a base set of packet forwarding rules known as Per-Hop-Behavior. DiffServ is known as an edge-provisioning model, and it does not provide any QoS guarantees per se [48]. The application of DiffServ in its original form is limited in a QKD network due to the following: •Edge router selection: existing QKD technology limits the deployment of a QKD network to the metropolitan scale2[2], [3], [5], [6], [49], [50]. In such a network, it is necessary to clearly define the edge routers which play a key role in the processing of traffic. •Lack of Service Level Agreement: each network node needs to comply with the rules for the classification and processing of traffic of different priorities. However, since the Service Level Agreement (SLA) concept is not defined in a QKD network, it is questionable how nodes of potentially different domains can negotiate traffic rules. B. QoS Signalization in QKD Networks In general, the QKD protocol which establishes a new key material consists of six successive stages: a physical exchange of quantum states between a pair of devices, extraction of the raw key (sifting), error rate estimation, reconciliation, privacy amplification, and authentication [51], [52]. Only the first stage is performed over a quantum channel; all other stages are performed over a public channel, resulting in the communication referred to as QKD post-processing. We propose an extension of authenticated packets with signaling data which provides an elegant way of tackling the problem of distribution of signaling information without introducing additional traffic overheads [53]. C. QoS Routing in QKD Networks In our view, a routing protocol well-suited for operation in dynamic QKD networks should meet the following main design objectives: •Reducing the consumption of scarce key material by choosing the shortest path considering both channels of the QKD link. The routing algorithm needs to find a balance between the requirements, since a path that meets the requirements of the public channel may not be suitable for the quantum channel and vice versa [17], [42]. •Given that the main objective of QKD is to provide ITS communication, routing packets need to be encrypted and authenticated [17], [54]. This means that the number of routing packets needs to be minimized to preserve scarce key material. •To prevent denial of service, it is necessary to minimize knowledge about the utilized routing path by reducing the broadcast of routing packets [34]. •The routing protocol should be scalable to different network sizes. •Due to a low key charging rate and overlay networking mode, link interruptions are common in QKD networks. Hence, the routing protocol should be robust enough to find an adequate replacement path. In general, routing solutions can be divided into three broad categories: source, hierarchical and distributed routing. The performance of source routing algorithms relies on the availability of precise link state information, while the dynamic nature of QKD networks makes the available 2In 2014, a QKD system connecting the cities of Hefei-Chaohu-Wuhu (HCW) in China with a total of nine QKD nodes was reported in [6]. Thirteen QKD devices within nine nodes in total were employed to support the two QKD networks and the intercity QKD link. MEHIC et al.: NOVEL APPROACH TO QoS PROVISIONING IN TRUSTED RELAY QKD NETWORKS 171 link state information inherently imprecise. Given that the constant maintenance of link state information is mostly done by periodic flooding, this solution is inadequate for QKD networks. Although several examples exist of hierarchical network organization[4]–[6], in our opinion, such organization is not suitable for QKD networks since nodes of upper hierarchical levels represent a potentially easy target for the attack to disassemble the network. In distributed routing, the computation of the path is shared among network nodes on a periodic basis (proactive) or only when a routing path is requested (reactive). Proactive routing protocols mainly use the static update period time for keeping routes up-to-date, which contradicts the dynamic nature of QKD networks. Therefore, in overlay networks, reactive routing performs better in terms of efficiency and stability than proactive routing [55], [56]. V. FQKD: A FLEXIBLE QUALITY OF SERVICE MODEL FOR QKD NETWORKS To overcome problems of providing QoS in a dynamic environment, we present a flexible QoS model for QKD networks (FQKD). Our model avoids a centralized resource management scheme or reservation of resources mechanism. Instead, we turn to a distributed approach to control traffic loads by providing soft-QoS constraints without flow or session state information maintained in support of end-to-end communication. FQKD defines three roles for nodes in a QKD network: ingress, interior and egress. Each node can take any of these roles depending on the position in network flow. A source node which sends data is referred to as an ingress node. Interior nodes are nodes that forward data to the final destination node, which is referred to as an egress node. A. Provisioning and Conditioning As shown in Fig 1, the FQKD model consists of a sender-based classifier, waiting queues, local node-based admission controller, crypto module and dynamic regulation of admitted sessions at the MAC layer. The classifier is input at the ingress node to distinguish between traffic classes by marking the DSCP field in the IP packet header. FQKD distinguishes between three traffic classes with corresponding DSCP values: best-effort, real-time and premium class. For each class, separate waiting queues are defined and processed by priority. The packets are forwarded by interior nodes in per-hop behaviour associated with the assigned DSCP value. Considering that nodes in QKD networks continuously generate new keys at their maximum rate3[26], before setting the route, the routing protocol contacts the admission controller to filter those links to its neighbors that have sufficient resources to serve the classified network packet. The routing protocol calculates the path and the packet is forwarded to the MAC layer for further processing. Otherwise, if no available link is found, the packet waits in the queue for reprocessing. In FQKD, additional waiting queues are installed between the 3QKD nodes aim to generate as much key material as possible. Therefore, nodes continuously generate traffic at the highest rate allowed by the network. More information about the impact of public channel states on the intensity of the key rate can be found in [42]. Fig. 1. FQKD model. First, the incoming application package is classified and forwarded to the routing protocol which contacts the admission control to verify there are sufficient resources for processing the data. If true, the packet is stored in the appropriate waiting queue and encrypted before sending to the network. Arrows denote communication between model elements and the flow of the processed packet. L3 and L4 TCP/IP layer to avoid conflicts in decision making which could lead to inaccurate routing. Suppose the queues are implemented on the data link layer (L2) only, and suppose that they are half filled with packets. Since the routing protocol used the routing metric that at the time t1of calculating the route had a different value from the time t2when the packet came online in the queue to be served, it follows that significant changes to the state of links in the time interval Δt=t2−t1could occur, which can lead to inaccurate and incorrect routing. Instead, by exploiting higher level waiting queues, the packet for which the route is calculated will be directly forwarded to lower layers and immediately sent to the network. This implies the usage of one set of waiting queues (set of three waiting queues for best-effort, real-time and premium traffic classes) for all network interfaces. Using queuing at the L2 layer is not excluded, but additional attention is given to queues at a higher level due to the dynamic nature of the network. Assuming the key rate is constant in time when the quantum channel has a fixed length [17], [26], it is evident that the key storage can be identified with the Token Bucket traffic shaping mechanism as shown in Fig. 2. This simplifies the view of the admission controller, which behaves as the traffic conditioner. The volume of traffic over the QKD link is limited by the amount of key material in key storage which is used for encryption or authentication of data over that link. The key material storage of link kbetween nodes aand bcan be represented using following parameters: •The time measurement moment t, •The average key generation rate rk, measured in bits per seconds and used to indicate the charging rate of the storage, 172 IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 28, NO. 1, FEBRUARY 2020 Fig. 2. Traffic processing in the FQKD model. •The key material storage depth Mmax,k,usedtoindicate the capacity of the storage, •The current value Mcur,k(t), representing the amount of key material in the storage at the time of measurement t, where it holds that Mcur,k(t)≤Mmax,k. •The threshold value Mthr,a,b(t)or simply Mthr,k(t) described in more detail below, •QKD is also known as Quantum Key Growing [57], [58] or Quantum Key Expansion [59], since it needs a small amount of key material pre-shared between parties (denoted with Mmin,k) to establish a larger amount of the secret key material. This pre-shared key material is used for QKD post-processing and authentication [29], [59]. The amount of key material over a time interval Tdepends on the key generation rate and the available amount of key material in the storage, and can be calculated using Equation (1). The average operational rate, that is the rate at which packets can be served over an interval T, can be calculated using Equation (2). As T→∞, the operational rate Ak(T) approaches the charging key rate rk. Dk(T)≤rk·T+Mcur,k(T)−Mmin,k(T)(1) Ak(T)=Dk(T) T=rk+Mcur,k(T)−Mmin,k(T) T(2) However, the overall amount of traffic data that can be transmitted over link kin a time interval Tcan be calculated by dividing the value obtained from Equation (1) and the ratio Lkwhich is the quotient of key length used for encryption with authentication and the length of the data message. Note that for ITS communication, which usually involves the OTP cipher and Wegman-Carter authentication, more bits of key material than the length of the data message are required (Lk>1) [17]. An incoming packet is served from the queue only if there is enough key material in the storage. Otherwise, the packet remains in the queue waiting for storage to be charged. The length of the queue is limited, and traffic-shaping algorithms are in charge of packet management operations. To avoid blocking work due to the lack of the key material used to generate new key material, special attention is placed on the categorization of the traffic. If storage stops charging, the purpose of the link loses functionality. Therefore, the traffic generated by the post-processing application has the highest Fig. 3. Simple topology showing the calculation of Mthr: a) the traffic is routed along the route a-b-c-e; b) the traffic is routed along the path a-b-c regardless of key material depletion of link c-e; c) calculated Mthr values based on Mcur values of all links connected to a given node. priority and is sorted in the premium queue. Only traffic from post-processing applications can use the key material when Mcur,k(t)≤Mmin,k while the traffic from the other two queues is served only when Mcur,k(t)>M min,k. The threshold value Mthr is proposed to increase the stability of QKD links, where Mthr,k(t)≤Mmax,k. The parameter is explained by considering the simple topology shown in Fig. 3 where node aneeds to communicate with remote node e. Suppose the routing protocol uses only information about the state of its links with its neighbors. Then, assuming that all network links have the same performance of public channels, we consider only the state of key storages which are marked next to links as shown in Fig. 3-a. Upon receipt of the packet from node a, the routing protocol on node b selects path b-c since the link b-d has a lower performance. However, if node bdoes not consider the state of links that are more than one hop away, the traffic may stuck on the link between nodes band casshowninFig.3-b.Toavoid such behaviour, we propose using the Mthr value. Each node icalculates value Lisummarizing the Mcur values of links to its neighbors and dividing it by the number of its neighbors Ni using Equation (3). Then, each node exchanges calculated value of Liwith its neighbors. The minimum value denoted by Equation (4) is accepted as a reference threshold value of the link. Li=Ni k=0 Mcur,i,k Ni (3) Mthr,i,j =min{Li,L j}(4) As shown in Fig. 3-c, node bcalculates Lb=36.66, while node ccalculates Lc=25. The threshold value of the link MEHIC et al.: NOVEL APPROACH TO QoS PROVISIONING IN TRUSTED RELAY QKD NETWORKS 173 Fig. 4. Qmof link between nodes sand ifor different values of Mthr; Mmax,s,i =100. b-c is set to Mthr,b,c =25and it is included in link metric calculation as described in Section V-B. The higher the value of Mthr, the better the state of links that are more than one hop away. B. QKD Link Metric Popular metrics from conventional networks which describe the state of the communication link cannot be adequately used in QKD networks since they only describe the public channel. Therefore, we propose new metrics that clearly define the state of the QKD link taking into account its most essential features. 1) The Quantum Channel Status Metric: At the moment of serving the packet, the remaining key material in the key storage is the main factor contributing to the link’s availability; this is because without key material, cryptographic operations cannot be performed and secure communication over the link is not possible. We use Equation (6) to express the state of the quantum channel between nodes sand i,whereQfrac,s,i is the ratio of the squared amount of key material at the time of measurement (Mcur,s,i2) multiplied by the threshold value (Mthr,s,i) and the cubed capacity of the key storage (Mmax,s,i3) as defined by Equation (5). Qfrac,s,i is in the range [0,1], and it highlights the current amount of key material on closest links in relation to the amount of key material of links that are further away since more distant links are unreachable when links to neighbors are unavailable. Qfrac,s,i =Mcur,s,i2·Mthr,s,i Mmax,s,i3(5) Qm,s,i =1−Qfrac,s,i e(1−Qfrac,s,i )(6) Qm,s,i is the utility function associated with the key material level of the link. Qm,s,i uses an exponential formula to address the fact that the lower the amount of key material in the storage, the more critical the situation, and the less time is left for the routing protocol to react. The value of Qm,s,i is normalized as a grade ranging from 0 to 1 as shown in Fig. 4, where a lower value means a better quantum channel state. In the example shown in Fig. 3-c, the routing protocol should favor the link b-d since Qm,b,d <Q m,b,c. 2) The Public Channel Status Metric: Instead of using popular approaches from conventional or overlay networks [31], [60], we use meta-data of keys such as the time duration of the key establishment process to assess the state of the public channel effectively. We define Pm,s,i with Equation (7) to evaluate the state of the public channel between nodes sand iwhere Tlast,s,i is the length of time spent on the establishment of the key material at the time of measurement and Tmaximal,s,i is the maximum time that can be tolerated for the establishment of the key. Tmaximal,s,i is calculated as the double value of the average duration of key material establishment process, in the long run, denoted as Taverage in Equation (8). Pm,s,i =Tlast,s,i +Δt Tmaximal,s,i (7) Tmaximal,s,i =2·Taverage (8) Δtis used to describe the freshness of the information and is defined as the difference between the current time of the measurement and the time when the Tlast,s,i is recorded. Note that Taverage is not equal for all links of the network since it depends on the load of the network, types of quantum and network devices, QKD post-processing application and the state of the public channel.4The value of Pm,s,i mainly falls in the range [0,1] where the lower value means a better public channel state. Values greater than 1 indicate that the link has a problem with establishing new key material, and such links should not be considered. 3) The Overall QKD Link Status Metric: Key material depletion is not the same for all links since it depends on the type of encryption algorithm used and the volume of network traffic to be encrypted. For example, a QKD link between nodes sand ihaving a low value of Qm,s,i may be suitable for a network flow encrypted with less secure algorithms which require less key material than OTP (such as the AES cipher), but it may not be suitable for encryption using OTP. Thus, factor αwhich reflects the balance between the requirements is introduced in Equation (9) to compensate for this effect using the utility functions of the quantum and public channel in the [0,1] range where a lower value means a better overall link state. Rm,s,i =α·Qm,s,i +(1−α)·Pm,s,i (9) Parameter αtakes the value in the [0,1] range; if the OTP cipher is used, we suggest the value of α=0.5. This means that both channels of the QKD link are considered equally. If the AES cipher is used, αcan be set to a lower value to 4In practice, the QKD link employs three channels. The QKD quantum-channel and the QKD distillation-channel are usually referred to as the quantum channel and public channel, respectively. The third channel is known as the (time-stable) synchronization channel and cannot be separated from the quantum channel physically to two fibers, because it delivers time references. From the perspective of higher network layers, the synchronization channel is part of the key generation (growing) process. If the impact of this channel on the entire process were to be considered, the signals in the synchronization channel need to be sufficiently large so that even co-propagating classical channels or spoiled signals are irrelevant and key generation is disturbed. Such major non-synchronization would be reflected in the overall duration of the key generation process, which is considered using Equation (7). 174 IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 28, NO. 1, FEBRUARY 2020 put a greater emphasis on the public channel due to its lower requirements for key material, depending how frequently it is refreshed and the length of the AES key used. VI. GREEDY PERIMETER STATELESS ROUTING PROTOCOL FOR QKD NETWORK Driven by the similarities between the MANET and QKD networks discussed in Section III, we present the Greedy Perimeter Stateless Routing Protocol for QKD networks (GPSRQ). The primary motivation for designing GPSRQ is to minimize the number of routing packets and to achieve high-level scalability by using distributed geography reactive routing. We assume that all nodes know the geographical locations of all other network nodes they wish to communicate with. Therefore, there is no periodic flooding of the node location details, and we assume a location registration and lookup service that maps the node address to a location. This paper does not deal with implementation details of such a service, but we assume it can be implemented using internal or other communication channels [61]. As indicated in Section IV-B, authenticated packets in QKD post-processing can be used to exchange information about the geographical position of nodes effectively. Although several experiments have been conducted regarding mobile QKD networking [62]–[66], due to the high sensitivity of quantum equipment to various environmental factors5and relatively low key generation rates in free-space QKD links [24], [59], [68]–[70], in this paper we assume that QKD networks are composed of static nodes representing secure access points6. We follow the idea “the greater the distance separating two nodes, the slower they appear to be moving with respect to each other” outlined in [71] to implement caching in GPSRQ, which is discussed further below. GPSRQ sets up a network without hierarchical organization, which means that all nodes in the network are of equal importance. Nodes do not exchange routing tables, which significantly minimizes the consumption of scarce key material and reduces the probability of passive eavesdropping [34]. Route selection, that is the decision about the next hop, is made in per-hop behavior such that the packet is moved closer to the destination based on the states of links in the local environment and on the geographical distance from the node. An eavesdropper is not able to intercept routing packets and find out the exact route to the destination, since it is not known at which node’s network interface the packet will be forwarded until the last moment. GPSRQ uses two packet forwarding algorithms: greedy forwarding and recovery mode forwarding. A. Greedy Forwarding By definition, greedy forwarding entails forwarding to the neighbor geographically closest to the destination. An example 5The key rate may vary due to humidity, temperature, stability of devices, global radiation, pressure, dust, sunshine duration or other factors [17], [67]. 6Low mobility within a geographic region or slow node movement are supported as long as the service for distributing geographic locations of nodes can accurately and safely distribute locations to all nodes in the network. Fig. 5. Ingress node awhich is surrounded by three adjacent nodes b,d, and k, aims to communicate with the egress node g. In the absence of a path over node b, node awrites in the internal cache that it is not possible to route packets along the path a-b towards the region marked with a circle of radius d(b,g)/2 with the center in node g. Any further request for routing towards any node which is placed in the defined circle region will be ignored over the route via node b, and an alternative route needs to be found. of greedy forwarding is shown in Fig. 5, where ingress node awhich is surrounded by three adjacent nodes b,d,andk, needs to communicate with egress node g. Ingress node a forwards the packet to b, as the Euclidean distance between band gis smaller than the distance between gand any of a’s other neighbors. Such greedy forwarding is repeated on interior nodes and it stops when the packet reaches its destination. GPSRQ aims to maximize network utilization by using different paths for different traffic classes. It uses Equation (10) to calculate the path to forward the packet: Fa,g,v =1−β·Ra,v +β·Gv,d (10) where Ra,v denotes the state of link between source node aand neighboring node vusing Equation (9) and Gv,g represents the Euclidean distance between neighboring node v and destination node g, for each node vwhich belongs to the set Naof all neighbors of source node a,∀v∈Na. All routes towards the destination are sorted in descending order using Equation (10) and the route with the lowest value is used. GPSRQ uses parameter βwith a value in the [0,1] range to manage network utilization by choosing between forwarding along the geographically shortest route or the route that has the most available resources. We discuss simulation results for different values of βin Section VII-A5. Greedy forwarding relies on the knowledge of the geographical location and state of links to neighbors, which results in a high level of network scalability. However, in some cases, the route to the destination requires forwarding the packet over a neighboring node which is geographically further from the destination than the node which forwards the packet. In cases when a local maximum occurs, an alternative recovery-mode forwarding is used. To increase scalability and exclude routes which do not lead to the destination, we propose a robust caching mechanism to preserve key material consumption. Consider the example shown in Fig. 5 where we further suppose that link b-f is unavailable due to a lack of key material. When node brealizes there is only one interface MEHIC et al.: NOVEL APPROACH TO QoS PROVISIONING IN TRUSTED RELAY QKD NETWORKS 175 available (the interface which was used to receive the packet from node a), it marks a “loop” field in the GPSRQ packet header and returns the packet back to node a. Then, node a calculates the Euclidean distance d(b,g) between node band destination node gand writes in its internal cache memory that it is not possible to route towards the region which is marked with a circle of radius d(b,g)/2 and the center in node galong the path a-b. Upon receiving any further requests for routing towards the node placed in the defined circle region, node a will ignore the route over node bandlookforanalternative route. The validity of cached record is set to time interval defined using Equation (11): Tcache =Tmaximal,b,g/2(11) where Tmaximal,b,g is defined by Equation (8). The overall goal is to reduce the dynamics of the network topology changes using the scalable cache mechanism. In Section VII-A6, we discuss the impact of different values on cache validity. After the cached record expires, the node is allowed to try establishing the connection once again. In the event when GPSRQ detects there is no neighbor closer to the destination, it enters recovery mode. B. Recovery Mode Forwarding Recovery mode involves using the well-known right-hand rule which states that the next edge from node kupon arriving from node ais edge (k,j) which is sequentially counterclockwise to edge (a,k) [72]. However, for first forwarding, the packet is forwarded along edge (a,k) which is counterclockwise to node afrom line ag. The packet stays in recovery mode until it reaches a node which is closer to the destination than the node where forwarding in recovery mode started. To avoid routing loops, the GPSRQ header contains information about the IP address of the node at which the packet entered recovery mode and the outgoing interface which was used for first forwarding. If the loop is detected by analyzing the packet header, the packet is returned to the previous node for rerouting and adding a new entry to the node’s internal cache memory. If the public channel of link j-i is unavailable, there is no available path to destination g. Source node aforwards the packet to node kwhich forwards the packet to node jin greedy forwarding mode. Since link j-i is unavailable, node jis not able to find any neighbor closer to the destination so it enters recovery mode, sets the value of the field “inRec” to 1, writes its IP address to the header field “recPosition”, writes the interface number which leads to node lin the “recIF” header field and forwards the packet to node lsince it is on the first edge counterclockwise about jfrom the line jg as required by the right-hand rule. Upon receipt of the packet, node linspects the header and remains in recovery mode since node jin which the packet entered recovery mode is closer to the destination g. Then, the packet is forwarded to node kwhich forwards the packet back to node j. When node jdetects its IP address from the header field “recPosition”, it adds a record to the internal cache memory stating that it is not possible to reach destination node gvia node lby adding a record consisting of the triple: IP address Fig. 6. Packet encapsulation with the QKD header and QKD command header. TABLE I GPSRQ PACKET HEADER FIELDS USED IN RECOVERY MODE FORWARDING of hop l, the radius of circle region d(l,g)/2 and the value of the circle center which is set to the location of node g.Given that there is no other interface available, node jsets GPSRQ header field “loop” to 1and returns the packet to node kwhich adds a record to its cache memory stating that it is not possible to reach destination node gvia node j. Then, node ksets the field “loop” to 2and tries again with greedy forwarding where node jis excluded as the next hop. The packet is forwarded to node lwhich forwards the packet to node j. Since node jdoes not have any other interface available, it will set the value of header field “loop” to 1, and return the packet to node lwhich will add to its cache memory a record stating that it is not possible to reach destination node gover node j. The packet is returned to node kand then it is returned to node a.This procedure is repeated until a feasible path to the destination is found. Otherwise, if no available path is found, the packet is gradually returned to the source node which is allowed to discard the packet while keeping updated records in the cache memory of other nodes. C. GPSRQ Protocol Implementation To make the routing operation easier, encryption and authentication are performed on the data link TCP/IP layer [17], [73]. However, in previously deployed QKD networks the QKD header was transported unencrypted [74]. A denial-of-service attack is possible if an eavesdropper is able to block high importance packets such as routing packets or post-processing operation packets which would disable the link [75] or divert traffic to the node under an attacker’s control [34]. Therefore, we propose using the QKD Command header, which is encrypted together with the packet payload (Fig. 6). Instead of adding the GPSRQ header to the packet, which would increase the amount of key used for encryption, values from the GPSRQ header which are listed in Table I are rearranged to the QKD header and QKD command header before transmission. Upon receiving the packet, the values are moved from the QKD header and QKD command header to the GPSRQ header. 176 IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 28, NO. 1, FEBRUARY 2020 In typical multimedia communication protocols, excessively delayed packets are not used for the reconstruction of transmitted data at the receiver [76]. We propose the extension of the QKD header by including Timestamp and MaxDelay fields to carry the packet’s timestamp and maximum tolerated delay, respectively. The values of these fields are written at the ingress node, while the GPSRQ at the interior node checks the values before forwarding the packet, including the previously mentioned field “loop”. If the value of the “loop” field is equal to 2, the packet was in a loop which was later avoided and marked in the internal cache in the previous nodes, so no action is taken against the packet. If the value of the “loop” field is equal to 0, it means that the packet was not previously in the loop. Then, GPSRQ checks whether the delay of the packet, which is calculated as the difference between the current timestamp and the Timestamp value, is greater than the MaxDelay. If this is true, GPSRQ sets the “loop” field to 1 and returns the packet to the previous-hop which will result in adding a new entry to the internal cache in previous nodes as mentioned earlier. The function of the Timestamp and MaxDelay fields is similar to the Time-to-Live (TTL) field in the IP header of conventional networks, but with the aim of minimizing the consumption of scarce key material in QKD network. VII. SIMULATION SETUP To ensure simulations are independent of the topology or characteristics of any specific network, random graphs were constructed. Random network topologies were generated using the Waxman model [77], which is recommended for small and medium-size networks which include locality aspects such as QKD networks [2], [6], [49]. Additionally, the Waxman model corresponds to the requirement for the implementation of QKD networks without hierarchical multi-plane organization [78] since it spreads nodes randomly on a grid and adds links randomly, such that the probability Peof interconnecting two nodes in a single plane is parameterized by the Euclidean distance separating them, as defined using Equation (12): Pe(u, v)=Θ·exp−d(u,v) Ω·Λ(12) where d(u, v)is the Euclidean distance between nodes uand v, Λdenotes the maximum possible distance between two nodes where 0<Ω,Θ≤1. The parameter choices are constrained to assure Pe(u, v)∈[0,1]. In total, 1290 simulations were performed with 30 randomly generated simulation seeds defining random network topologies and random values of the initial amount of key material in key storages. We evaluated GPSRQ (β=0.6;Taverage =5) against OSPFv2 which was used in previously deployed QKD networks [17], [26], [39]–[41], and against DSDV which was used in our previous work [75]. The simulation was performed using the QKD Network Simulation Model (QKDNetSim) [79] to deploy GPSRQ and DSDV while NS-3-DCE v.1.9 was used to deploy the OSPFv2 routing protocol [80]. We used the BRITE topology generator to generate random topologies according to the Waxman model since it is supported under NS-3 and the source code is freely available [81]. NS-3-DCE and QKDNetSim were set to share Fig. 7. The number and average sizes of routing packets. the same seed file to generate random values which enabled us to use the same random topologies with the same configuration values in QKDNetSim and NS-3DCE. Simulations included static networks with 10, 20, 30, 40, 50, 60 and 70 nodes which were randomly placed in a rectangular region and connected to QKD links with the following settings: minimal amount of key material 1 Mbyte; maximal amount 100 Mbyte; initial amount randomly generated in the [0.5, 25] MByte range; maximal bandwidth of the link set to 10 Mbps; charging key rate set to 100 kbps with the charging key period of seven seconds. The Waxman router model was used with the following parameter values: m=2;Λ = 100;Ω=0.4;Θ=0.4;The first node was set as the source of traffic, while the last randomly placed node was set as the destination. The source node generated UDP traffic with a 1 Mbps rate and fixed packet size of 512 bytes which were encrypted using OTP and authenticated using VMAC with a 32-bit authentication tag [27]–[29]. The duration of the simulation was 150 seconds, while the capacity of waiting queues per device on the L2 and L4 layers (used for GPSRQ only) was set to 1000 packets. The parameters not given here are the default parameters of QKDNetSim and NS-3-DCE. In following sections, simulation results are presented using box-plot graphs. A. Simulation Results and Evaluation Although GPSRQ can achieve valuable results on non-planar graphs, one of the drawbacks of GPSRQ is the massive consumption of key material in non-planar networks since geographical routing cannot quickly determine the shortest path towards the destination which leads to unnecessary forwarding. It is, therefore, advisable to convert non-planar graphs into planar graphs in which geographic routing protocols can be effectively used. Instead of using the heuristic to exclude the intersecting edges [82], we modified the BRITE random topology generator to generate random planar Gabriel Graphs7(GG) which are defined as follows: “An edge (u, v) exists between vertices uand vif no other vertex wis present within the circle whose diameter is the Euclidean distance d(u,v)” [83], [84]. 1) Routing Protocol Overhead: Fig. 7 shows the routing protocol overhead, measured by the number and average sizes 7The BRITE random generator with Gabriel Graph module is available at https://bitbucket.org/mickeyze/brite-planar-graph