S-MATE: Secure Coding-based Multipath Adaptive Traffic Engineering

There have been several approaches to provisioning traffic between core network nodes in Internet Service Provider (ISP) networks. Such approaches aim to minimize network delay, increase network capacity, and enhance network security services. MATE (Multipath Adaptive Traffic Engineering) protocol has been proposed for multipath adaptive traffic engineering between an ingress node (source) and an egress node (destination). Its novel idea is to avoid network congestion and attacks that might exist in edge and node disjoint paths between two core network nodes. This paper builds an adaptive, robust, and reliable traffic engineering scheme for better performance of communication network operations. This will also provision quality of service (QoS) and protection of traffic engineering to maximize network efficiency. Specifically, we present a new approach, S-MATE (secure MATE) is developed to protect the network traffic between two core nodes (routers or switches) in a cloud network. S-MATE secures against a single link attack/failure by adding redundancy in one of the operational paths between the sender and receiver. The proposed scheme can be built to secure core networks such as optical and IP networks.


I. INTRODUCTION
There have been several proposals to adapt the traffic between core network nodes in Internet Service Provider (ISP) networks [7], [12], [14]. Elwalid et al. [7] proposed an algorithm for multipath adaptive traffic engineering between an ingress node (source) and an egress node (destination) in a communication network. Their novel idea is to avoid network congestion that might exist in disjoint paths between two core network nodes. They suggested load balancing among paths based on measurement and analysis of path congestion by using Multi-Protocol Label Switching (MPLS). MPLS is an emerging tool for facilitating traffic engineering unlike explicit routing protocols that allow certain routing methodology from hop-to-hop in a network with multiple core devices. The major advantage of MATE is that it does not require scheduling, buffer management, or traffic priority in the nodes.
Network coding is a powerful tool that has been recently used to increase the throughput, capacity, and performance of wired and wireless communication networks. Information theoretic aspects of network coding have been investigated in several research papers, see for example [1], [10], [18], and the list of references therein. It offers benefits in terms of energy efficiency, additional security, and reduced delay. Network coding allows the intermediate nodes not only to forward packets using network scheduling algorithms, but also to en- Fig. 1. The network model is represented by two network nodes, an ingress node (source) and an egress node (receiver). There are k link disjoint paths between the ingress and egress nodes. code/decode them through algebraic primitive operations [1], [9], [10], [18]. For example, data loss because of failures in communication links can be detected and recovered if the sources are allowed to perform network coding operations [5], [11], [13].
MATE, which was previously proposed by one of the authors of this paper, is a traffic load balancing scheme that is suitable for S-MATE (secure MATE) as will be explained later. MATE distributes traffic among the edge disjoint paths, so as to equalize the path delays. This is achieved by using adaptive algorithms. MATE inspired other traffic engineering solutions such as TexCP [14] and the measurement-based optimal routing solution [17]. In this paper, we will design a security scheme by using network coding to protect against an entity who cannot only copy/listen to the message, but can also fabricate new messages or modify the current ones. We aim to build an adaptive, robust, reliable traffic engineering scheme for better performance and operation of communication networks. The scheme will also provide provisioning quality of service (QoS) and protection of traffic engineering.
The rest of the paper is organized as follows. In Section II, we present the network model and assumptions. In Sections III and IV, we review the MATE scheme and propose a secure MATE scheme based on network coding. Section VI provides network protection using distributed capacities and QOS, and finally Section VII concludes the paper.

II. NETWORK MODEL AND ASSUMPTIONS
The network model can be represented as follows. Assume a given network represented by a set of nodes and links. The network nodes are core nodes that transmit outgoing packets to the neighboring nodes in certain time slots. The network nodes are ingress and egress nodes that share multiple edge and node disjoint paths.
We assume that the core nodes share k edge disjoint paths, as shown in Fig. 1, for one particular pair of ingress and egress nodes. Let N = {N 1 , N 2 , ...} be the set of nodes (ingress and egress) and let L = {L 1 ℓh , L 2 ℓh , ..., L k ℓh } be the set of paths from ingress node N ℓ to an egress node N h . Every path L i ℓh carries segments of independent packets from ingress node N ℓ to egress node N h . Let P ij ℓh be the packet sent from the ingress node N ℓ in path i at time slot j to the egress N h . For simplicity, we describe our scheme for one particular pair of ingress and egress nodes. Hence, we use P ij to represent a packet in path i at time slot j.
Assume there are δ rounds (time slots) in a transmission session. For the remaining paper, rounds and time slots will be used interchangeably . Packet P ij is indexed as follows: where ID N ℓ and X ij are, respectively, the sender ID and transmitted data from N ℓ in the path L i at time slot j. There are two types of packets: plain and encoded packets. A plain packet contains the unencoded data from the ingress to egress nodes as shown in Equation (1). An encoded packet contains encoded data from different incoming packets. For example, if there are k incoming packets to the ingress node N l , then the encoded data traversed in the protection path L i lh to the egress node N h are given by where the summation denotes the binary addition. The corresponding packet becomes The following definition describes the working and protection paths between two network switches as shown in Fig. 1.
Definition 1: The working paths in a network with k connection paths carry un-encoded (plain) traffic under normal operations. The protection paths provide alternate backup paths to carry encoded traffic. A protection scheme ensures that data sent from the sources will reach the receivers in case of attack/failure incidences in the working paths.
We make the following assumptions about the transmission of the plain and encoded packets.
i) The TCP protocol will handle the transmission and packet headers in the edge disjoint paths from ingress to egress nodes. ii) The data from the ingress nodes are sent in rounds and sessions throughout the edge disjoint paths to the egress nodes. Each session is quantified by the number of rounds (time slots) n. Hence, t δ j is the transmission time at the time slot j in session δ.
iii) The attacks and failures on a path L i may be incurred by a network incident such as an eavesdropper, link replacement, and overhead. We assume that the receiver is able to detect a failure (attacked link), and our protection strategy described in S-MATE is able to recover it. iv) We assume that the ingress and egress nodes share a set of k symmetric keys. Furthermore, the plain and encoded data are encrypted by using this set of keys. That is where m i is the message encrypted by the key i . Sharing symmetric keys between two entities (two core network nodes) can be achieved by using key establishment protocols described in [15], [16]. v) In this network model, we consider only a single link failure or attack; it is thus sufficient to apply the encoding and decoding operations over a finite field with two elements, denoted as F 2 = {0, 1}. The traffic from the ingress node to the egress node in edge disjoint paths can be exposed to edge failures and network attacks. Hence, it is desirable to protect and secure this traffic. We assume that there is a set of k connection paths that need to be fully guaranteed and protected against a single edge failure from ingress to egress nodes. We assume that all connections have the same bandwidth, and each link (one hop or circuit) has the same bandwidth as the path.

III. MATE PROTOCOL
MPLS (Multipath Protocol Label Switching) is an emerging tool for facilitating traffic engineering and out-of-band control. unlike explicit routing protocols, which allow certain routing methodology from hop-to-hop in a network with multiple core devices. As shown in Fig. 2, MATE assumes that several explicit paths between an ingress node and an egress node in a cloud network have been established. This is a typical setting which exists in operational Internet Service Provider (ISP) core networks (which implement MPLS). The goal of the ingress node is to distribute traffic across the edge disjoint paths, so that the loads are balanced. One advantage of this load balancing is to equalize path delays, and to minimize traffic congestion [7], [8].
The following are the key features of the MATE algorithm. 1) The traffic is distributed at the granularity of the IP flow level. This ensures that packets from the same flow follow the same path, and hence there is no need for packet resequencing at the destination. This is easily and effectively achieved by using a hashing function on the five tuple IP address. 2) MATE is a traffic load balancing scheme, which is suitable for S-MATE, as will be explained later. MATE distributes traffic among the edge disjoint paths, so as to equalize the path delays. This is achieved by using adaptive algorithms as shown in Fig. 2 and Reference [7] 3) It is shown that distributed load balancing (for each ingress egress pair) is stable and provably convergent. MATE assumes that several network nodes exist between ingress nodes as traffic senders, and egress nodes as traffic receivers. Furthermore, the traffic can be adapted by using switching protocols such as CR-LDP [6] and RSVP-TE [4]. An ingress node is responsible to manage the traffic in the multiple paths to the egress nodes so that traffic congestion and overhead are minimized. As shown in Fig. 2, Label Switch Paths (LSPs) from the ingress node to the egress node are provisioned before the actual packet transmissions occur. Then, once the transmissions start, the ingress node will estimate the congestion that might occur in one or more of the k edge disjoint paths. As stated in [7], the congestion measure is related to one of the following factors: delay, loss rate, and bandwidth. In general, each ingress node in the network will route the incoming packets into the k disjoint paths. One of these paths will carry the encoded packets, and all other k − 1 paths will carry plain packets. Each packet has its own routing number, so that the egress node will be able to manage the order of the incoming packet, and thus achieve the decoding operations.
MATE works in two phases [7]: a monitoring phase and a load balancing phase. These two phases will monitor the traffic and balance packets among all disjoint paths. One good feature of MATE is that its load balancing algorithms equalize the derivative of delay among all edge disjoint paths from an ingress node to an egress node. Furthermore, MATE's load balancing preserves packet ordering since load balancing is done at the flow level (which is identified by a 5-tuple IP address) rather than at the packet level.

IV. S-MATE SCHEME
In this section, we provide a scheme for securing MATE, called S-MATE (Secure Multipath Adaptive Traffic Engineering). The basic idea of S-MATE can be described as shown in Equation (4). S-MATE inherits the traffic engineering components described in the previous section and in [7], [8].
Without loss of generality, assume that the network traffic between a pair of ingress and egress nodes is transmitted in rounds from ingress to egress nodes y n . . .

(4)
k edge disjoint paths, each of which carries different packets. For simplicity, we assume that the number of edge disjoint paths and the number of rounds in one transmission session are equal. There are two types of packets: i) Plain Packets: These are packets P ij sent without coding, in which the ingress node does not need to perform any coding operations. For example, in the case of packets sent without coding, the ingress node N l sends the following packet to the egress node N h : The plain data x ij are actually the encryption of the message m ij obtained by using any secure symmetric encryption algorithm [15]. That is, where key i is a symmetric key shared between N l and N h . ii) Encoded Packets: These are packets y i sent with encoded data, in which the ingress node N l sends other incoming data. In this case, the ingress node N l sends the following packet to egress node N h : The encoded packet will be used in case any of the working paths is compromised. The egress node will be able to detect the compromised data, and can recover them by using the data sent in the protection path. Lemma 2: The S-MATE scheme is optimal against a single link attack.
What we mean by optimal is that the encoding and decoding operations are achieved over the binary field with the least computational overhead. That is, one cannot find a better scheme than this proposed encoding scheme in terms of encoding operations. Indeed, one single protection path is used in case of a single attack path or failure. The transmission is done in rounds (time slots), and hence linear combinations of data have to be from the same round time. This can be achieved by using the time slot that is included in each packet sent by the ingress node.
Lemma 3: The network capacity between the ingress node and the egress node is given by k − 1 in the case of one single attack path. node node y 1 x 21 x 31 x 41 x 51 x 11 y 2 x 32 x 42 x 52 x 12 x 22 y 3 x 43 x 53 x 13 x 23 x 33 y 4 x 54 x 14 x 24 x 34 x 44 y 5 Fig. 3. Working and protection edge disjoint paths between two core nodes. The protection path carries encoded packets from all other working paths between ingress and egress nodes.
Encoding Process: There are several scenarios where the encoding operations can be achieved. The encoding and decoding operations will depend mainly on the network topology; i.e., on how the senders and receivers are distributed in the network.
• The encoding operation is performed at only one ingress node N l . In this case, N l will prepare and send the encoded data over L i lh to the receiver N h . • We assume that k packets will be sent in every transmission session from the ingress node. Also, if the number of incoming packets is greater than k, then a mod function is used to moderate the outgoing traffic in k different packets. Every packet will be sent in a different path. • Incoming packets with large sizes will be divided into small chunks, each with an equal size. Decoding Process: The decoding process is performed in a similar way as explained in the previous works [2], [3].
We assume that the ingress node N l assigns the paths that will carry plain data as shown in Fig. 3. In addition, N l will encode the data from all incoming traffics and send them in one path. This will be used to protect any single link attacks/failures. The objective is to withhold rerouting signals or transmitted packets due to link attacks. However, we provide strategies that use network coding and reduced capacity at the ingress nodes. We assume that the source nodes (ingress) are able to perform encoding operations and the receiver nodes (egress) are able to perform decoding operations.
One of S-MATE's objectives is to minimize the delay of the transmitted packets. So, the packets from one IP address will be received in order on one path. The key features of S-MATE can be described as follows: • The traffic from the ingress node to the egress node is secured against eavesdroppers and intruders. • No extra paths in addition to the existing network edge disjoint paths are needed to secure the network traffic. • It can be implemented without adding new hardware or network components. The following example illustrates the plain and encoded data transmitted from five senders to five receivers. Example 4: Let N l and N h be two core network nodes (sender and receiver) in a cloud network. Equation (7) explains the plain and encoded data sent in five consecutive time slots from the sender to the receiver. In the first time slot, the first connection carries encoded data, and all other connections carry plain data. Furthermore, the encoded data are distributed among all connections in the time slots 2, 3, 4 and 5.
The encoded data y j , for 1 ≤ j ≤ 5, are sent as We notice that every message has its own time slot. Hence, the protection data are distributed among all paths for fairness.

V. A STRATEGY AGAINST TWO ATTACKED PATHS
In this section, we propose a strategy against two attacked paths (links), securing MATE against two-path attacks. The strategy is achieved using network coding and dedicated paths. Assume we have n connections carrying data from an ingress node to an egress node. All connections represent disjoint paths.
We will provide two backup paths to secure against any two disjoint paths, which might experience any sort of attacks. These two protection paths can be chosen using network provisioning. The protection paths are fixed for all rounds per session from the ingress node to the egress node, but they may vary among sessions. For example, the ingress node N l transmits a message x iℓ to the egress node N h through path L i ℓh at time t ℓ δ in round time ℓ in session δ. This process is explained in Equation (9)  x n1 x n2 x n3 . . . x nn . . . 5 All y ℓ j 's are defined as: The coefficients a ℓ i and b ℓ i are chosen over a finite field F q with q > n − 2, see [3] for more details. One way to choose these coefficients is by using the follow two vectors.
Therefore, the coded data is In the case of two failures, the receivers will be able to solve two linearly independent equations in two unknown variables. For instance, assume the two failures occur in paths number two and four. Then the receivers will be able to construct two equations with coefficients Therefore, we have One can multiply the first equation by α and subtract the two equations to obtain value of x 4ℓ . We notice that the encoded data symbols y jℓ and y kℓ are fixed per one session but it is varied for other sessions. This means that the path L j lh is dedicated to send all encoded data y j1 , y j2 , . . . , y jn .
Lemma 5: The network capacity of the protection strategy against two-path attacks is given by n − 2.
There are three different scenarios for two-path attacks, which can be described as follows: i) If the two-path attacks occur in the backup protection paths L j lh and L k lh , then no recovery operations are required at the egress node. ii) If the two-path attacks occur in one backup protection path say L j lh and one working path L i lh , then recovery operations are required. iii) If the two-path attacks occur in two working paths, then in this case the two protection paths are used to recover the lost data. The idea of recovery in this case is to build a system of two linearly independent equations with two unknown variables.

VI. NETWORK PROTECTION USING DISTRIBUTED CAPACITIES AND QOS
In this section, we develop a network protection strategy in which some connection paths have high priorities (less bandwidth and high demand). Let k be the set of available connections (disjoint paths from ingress to egress nodes). Let m be the set of rounds in every cycle. We assume that all connection paths might not have the same priority demands and working capacities. Connections that carry applications with multimedia traffic have higher priorities than those of applications carrying data traffic.. Therefore, it is required to design network protection strategies based on the traffic and sender priorities. Consider that available working connections k may use their bandwidth assignments in asymmetric ways. Some connections are less demanding in terms of bandwidth requirements than other connections that require full capacity frequently. Therefore, connections with less demand can transmit more protection packets, while other connections demand more bandwidth, and can therefore transmit fewer protection packets throughout the transmission rounds. Let m be the number of rounds and t δ i be the time of transmission in a cycle δ at round i. For a particular cycle i, let t be the number of protection paths against t link failures or attacks that might affect the working paths. We will design a network protection strategy against t arbitrary link failures as follows. Let the source s j send d i data packets and p i protection packets such that d j + p j = m. Put differently: In general, we do not assume that d i = d j and p i = p j . The encoded data y iℓ are given by We assume that the maximum number of attacks/failures that might occur in a particular cycle is t. Hence, the number of protection paths (paths that carry encoded data) is t. The selection of the working and protection paths in every round is performed by using a demand-based priority function at the senders's side. It will also depend on the traffic type and service provided on these protection and working connections. See Fig. 4 for ingress and egress nodes with five disjoint connections.
In Equation (17), every connection i is used to carry d i unencoded data x i1 , x i2 , . . . , x idi (working paths) and p i Fig. 4. Working and protection edge disjoint paths between two core nodes (ingress and egress nodes). Every path L i carries encoded and plain packets depending on the traffic priority p i and time t i . encoded data y i1 , y i2 , . . . , y ipi (protection paths) such that d i + p i = m.
Lemma 6: Let t be the number of connection paths carrying encoded data in every round. Then, the network capacity C N is given by Proof: The proof is straightforward from the fact that t protection paths exist in every round, and hence k − t working paths are available throughout all m rounds.

VII. CONCLUSION
In this paper, we have proposed the S-MATE scheme (secure multipath adaptive traffic engineering) for operational networks. We have used network coding of transmitted packets to protect the traffic between two core nodes (routers, switches, etc.) that could exist in a cloud network. Our assumption is based on the fact that core network nodes share multiple edge disjoint paths from the sender to the receiver. S-MATE can secure network traffic against single link attacks/failures by adding redundancy in one of the operational paths. Furthermore, the proposed scheme can be built to secure operational networks including optical and multipath adaptive networks. In addition, it can provide security services at the IP and data link layers.