الگوریتم های حفاظتی ترکیبی در تئوری بازی ها در شبکه های نوری چنددامنه ای

With the network size increasing, the optical backbone is divided into multiple domains and each domain has its own network operator and management policy. At the same time, the failures in optical network may lead to a huge data loss since each wavelength carries a lot of traffic. Therefore, the survivability in multi-domain optical network is very important. However, existing survivable algorithms can achieve only the unilateral optimization for profit of either users or network operators. Then, they cannot well find the double-win optimal solution with considering economic factors for both users and network operators. Thus, in this paper we develop the multi-domain network model with involving multiple Quality of Service (QoS) parameters. After presenting the link evaluation approach based on fuzzy mathematics, we propose the game model to find the optimal solution to maximize the user’s utility, the network operator’s utility, and the joint utility of user and network operator. Since the problem of finding double-win optimal solution is NP-complete, we propose two new hybrid protection algorithms, Intra-domain Sub-path Protection (ISP) algorithm and Inter-domain End-to-end Protection (IEP) algorithm. In ISP and IEP, the hybrid protection means that the intelligent algorithm based on Bacterial Colony Optimization (BCO) and the heuristic algorithm are used to solve the survivability in intra-domain routing and inter-domain routing, respectively. Simulation results show that ISP and IEP have the similar comprehensive utility. In addition, ISP has better resource utilization efficiency, lower blocking probability, and higher network operator’s utility, while IEP has better user’s utility.

In Wavelength-Division-Multiplexing (WDM) optical networks, the failures may lead to a huge data loss since each wavelength carries a lot of traffic [1]. Therefore, survivability including protection method and restoration method to ensure the service continuity and quality in the network is very important [2] and [3]. In protection method [4] and [5], the backup resources are pre-assigned to the primary resources during the connection setup, and then the traffic carried by the primary resources can be directly switched to the backup resources if the failures occur. In restoration method [6], the backup resources are dynamically searched to carry the traffic if the primary resources are unavailable due to the failures. Current works mostly focused on the protection method since it has faster failure recovery to satisfy a lot of real-time demands in the network [4], [5] and [6]. At the same time, with the network size increasing, the current optical backbone actually is divided into multiple domains and each domain has its own network operator and management policy for independent routing and failure recovery. Since the development of multi-domain optical networks is the trend of next-generation intelligent optical networks, the survivability in multi-domain optical networks becomes an important and challenging issue [7] and [8]. Compared to single-domain network, the survivability in multi-domain network is more difficult since the network information of multi-domains is not accurate for searching the primary and backup resources. The reason for this is that each domain distributes only the partial information to other domains due to the constraints of network security, scalability, etc. In addition, the inter-domain failure recovery needs the cooperation among different domains that also increases the difficulty of survivability in multi-domain network. In order to solve the survivability in multi-domain optical network, the authors in Ref. [9] proposed a path protection algorithm to address the issues of inter-domain routing and single-link failure protection based on the Full Mesh Abstracted (FMA) virtual topology [10]. In Ref. [11], the authors presented a sub-path protection algorithm, in which each demand will be firstly assigned to an end-to-end inter-domain working path, then the working path will be separated to multiple working sub-paths based on the different domain ranges traversed by the working path, and finally each working sub-path will be assigned to a link-disjoint backup sub-path in the same domain. In Ref. [12], the authors proposed a differentiated protection scheme where different domains can use the different protection strategies, such as shared protection and dedicated protection. In Ref. [13], the authors presented a multi-domain p-cycles protection based on the limited information. In Ref. [14], the authors developed a multi-domain Hamiltonian cycle protection, in which a global Hamiltonian cycle protects the inter-domain failures in the multi-domain network and multiple local Hamiltonian cycles protect the intra-domain failures in each single-domain network. In Ref. [15], the authors proposed the segment-shared protection algorithm for dynamic connections in multi-domain optical mesh networks. In Ref. [16], the authors considered the graph partitioning and devised the multi-domain survivable algorithm. In multi-domain network, there are multiple independent network operators and multiple independent users. On the one hand, the network operators will compete with each other to pursue the individual maximal profit by providing the limited resources to attract more users. On the other hand, the users will expect to obtain higher Quality of Service (QoS) from the network operators by paying less cost. Therefore, the interdependence and conflict of interest exist between different network operators and users. However, the existing survivable algorithms and schemes [9], [10], [11], [12], [13], [14], [15] and [16] in multi-domain optical network considered only the engineering and technology issues to assign the network resources to the users with assuming the cooperation between users and network operators. Therefore, they all ignored the practical and important issue that is related with the economical factor and profit. Thus, these existing algorithms and schemes can achieve only the unilateral optimization for profit of either users or network operators, and they cannot well find the double-win optimal solution for both users and network operators. Although the authors in Refs. [17], [18], [19], [20] and [21] studied the routing problem based on game theory with considering the economical factor and profit for both users and network operators, they focused on only the theoretical analysis for pricing strategy for single-domain network and they did not study the survivability in multi-domain network. In Ref. [22], although the authors developed an inter-domain routing based on game theory in multi-domain optical network, they neither address the survivability nor solve the double-win optimal solution for both users and network operators. Therefore, the survivability with economical factor and profit for both users and network operators in multi-domain optical network is still an open and challenging issue which motivates our work. In this paper, we develop the logical topology model with considering the QoS parameters of delay, bit error rate (BER) and the number of available wavelengths based on FMA scheme for multi-domain optical network. Then, we present the link pricing method for physical and logical links, respectively. Since both network operators and users need to compute their own utilities to measure their own profits, we propose the link evaluation approach based on fuzzy mathematics. Further, we present the game model to find the optimal solution to maximize the user’s utility, the network operator’s utility and the joint utility of user and network operator based on the QoS requirements of each demand for achieving the double-win. Since the problem of finding the optimal double-win solution is NP-complete, we propose two novel hybrid protection algorithms, Intra-domain Sub-path Protection (ISP) algorithm and Inter-domain End-to-end Protection (IEP) algorithm, based on our proposed game model. The hybrid protection means that the intelligent algorithm based on Bacterial Colony Optimization (BCO) [23] and the heuristic algorithm are used to solve the survivability in intra-domain routing and inter-domain routing, respectively. In ISP, we allocate an end-to-end inter-domain working path for each demand, and then we calculate a link-disjoint backup sub-path for each intra-domain working sub-path. In IEP, we allocate two end-to-end inter-domain paths for each demand, one is working path and the other one is backup path. Simulation results show that the two algorithms have the similar comprehensive utility. In addition, ISP has better resource utilization efficiency, lower blocking probability and higher network operator’s utility, while IEP has better user’s utility. To the best of our knowledge, the work in this paper is the first study addressing the survivability based on game theory with considering the economic factors in multi-domain optical network. The rest of this paper is organized as follows: Section 2 is the problem statement; Section 3 presents the link evaluation approach; Section 4 proposes the game model; Section 5 describes the BCO routing algorithm; Section 6 develops the heuristic routing algorithm; Section 7 is for simulation and analysis; Section 7 concludes this paper.

This paper developed the multi-domain optical network model with considering multiple QoS parameters, presented the link evaluation approach based on fuzzy mathematics, and further proposed the game model to find the double-win optimal solution to maximize the user’s utility, the network operator’s utility, and the joint utility of user and network operator. Since the problem of finding double-win optimal solution for users and network operators is NP-complete, we proposed two hybrid protection algorithms ISP and IEP. In ISP, we allocate an end-to-end inter-domain working path for each demand and then calculate a link-disjoint backup sub-path for each intra-domain working sub-path. In IEP, we allocate two end-to-end inter-domain paths for each demand, one is working path and the other one is backup path. Simulation results show that the ISP and IEP have similar comprehensive utility. In addition, ISP has better resource utilization efficiency, lower blocking probability and higher network operator’s utility, while IEP has better user’s utility.