CN102186123B - Multicast-sharing and multilayer protection method based on subtrees in WDM (wavelength division multiplexer) optical network, - Google Patents

Abstract

The invention provides a subtree-based multicast sharing multi-layer protection method in a WDM optical network, which belongs to the technical field of network communication. The method includes establishing a working multicast forest, establishing a protection multicast forest, protecting a WDM layer, and leaving a service ; On the premise of considering single link failure, this method builds a multicast sharing protection method based on subtrees, and adopts subtree protection resource sharing strategy, optical path protection resource sharing strategy and wavelength link protection resource sharing strategy according to the different sharing granularity , reduce the number of damaged services when the physical link fails, can expand the application range of the traditional multicast sharing multi-layer protection method, consider multiple constraints when performing multi-layer protection, and provide multi-cast under multi-strategy Share a multi-layered approach to protection.

Description

A Subtree-Based Multicast Sharing Multilayer Protection Method in WDM Optical Network

technical field

The invention belongs to the field of network technology, and in particular relates to a subtree-based multicast sharing multi-layer protection method in a WDM optical network.

Background technique

With the rapid development of the Internet, people put forward new requirements for the capacity and performance of the communication system. Wavelength Division Multiplexing (WDM) technology can provide huge transmission capacity to meet the bandwidth requirements of Internet services. However, once a network failure occurs, it will cause a large number of business interruptions. At the same time, in order to reduce network operating costs and improve bandwidth resource utilization, the transmission network is gradually developing from the traditional IP over ATM over SDH/SONET over WDM multi-layer structure to the IP over WDM two-layer structure, and IP services are directly carried on WDM on the optical network.

Most of the traditional multicast shared multi-layer protection methods in optical networks only consider the shared multi-layer protection methods for link failures under single constraints, and their scope of application is narrow, without considering the constraints on the number of optical transceivers, sparse wavelength conversion constraints, etc. In the case of multiple constraints, there is no comprehensive consideration of reducing the number of recovery actions when a failure occurs and improving the resource utilization of the optical path.

Contents of the invention

Aiming at the problems existing in the above-mentioned prior art, the present invention provides a subtree-based multicast sharing multi-layer protection method in a WDM optical network. Under the premise of considering single link failure, the method constructs multicast protection based on subtree In the shared protection method, according to different sharing granularities, subtree protection resource sharing strategies, optical path protection resource sharing strategies, and wavelength link protection resource sharing strategies are adopted to reduce the number of damaged services when a physical link fails.

The subtree-based multicast sharing multi-layer protection method in the WDM optical network of the present invention comprises the following steps:

Step (1), establish a working multicast forest

A multicast traffic grooming algorithm is used to establish a working multicast forest for requests; if the multicast traffic grooming algorithm fails to groom, the algorithm ends.

Step (2), establish protection multicast forest

Step (2.1), physical link separation of optical path

Set the wavelength link on each physical link that the optical path passes through, and the cost of the optical path and subtree passing through these wavelength links is set to ∞;

Step (2.2), physical link separation of subtrees

设置光树的代价W_st，Step (2.2.1), press formula

Set the cost W _st of the light tree,

设置光路的代价W_ll，Press

Set the cost W _ll of the light path,

Find the destination node that is dredged by this subtree;

Among them: b _t , b _w , b _p , b _new respectively represent the total bandwidth, working bandwidth, protection bandwidth of the light path and the number of protection bandwidths that need to be newly allocated if the protection multicast forest passes through the light path, and α _ll is the number of logical links grade factor;

Step (2.2.2), start from the destination node and trace back the optical tree along the reverse direction of the service data flow, and record the wavelength links that guide the service data flow of these destination nodes;

Step (2.2.3), obtain its corresponding physical link according to these wavelength links, set the wavelength link on these physical links, the cost of the optical paths and subtrees passing through these wavelength links is set to ∞;

After setting the physical link separation from the working tree by the above method, use the multicast traffic grooming algorithm to establish a protection multicast forest for the request. If the creation of the protection multicast forest fails, then release the resources occupied by the working multicast forest. The algorithm Fail, end.

Step (3), protecting the WDM layer

表示可用于提供自共享保护的MC波长节点集合：Let T represent the working tree, S represent the working segment being processed, v _head and v _tail represent the wavelength nodes at the beginning and end of the working segment respectively, and V _mc represent the MC wavelength node on T (the amount of light splitting on the optical tree is less than the maximum value of the node non-wavelength nodes reached by wavelength conversion links) set of split numbers,

Indicates the set of MC wavelength nodes that can be used to provide self-shared protection:

Specific steps are as follows:

Step (3.1), initialization

The link costs of all admission links and logical links are set to ∞, and the link costs of all wavelengths on the physical links passed by the working tree are set to ∞;

Step (3.2), breadth-first traversal of the light tree to obtain all segmentation points and working segments, and provide protection for each working segment S according to the order of traversal, the method is as follows:

将v_head添加到

中，即

计算T上v_head的所有下游MC波长节点，将它们从

中删除；Step (3.2.1),

Add the v _head to

in, namely

Compute all downstream MC wavelength nodes of v _head on T, dividing them from

delete in

Step (3.2.2), calculating the set of physical links that the working section passes through:

设置其余的工作树未经过的物理链路上的波长链路代价；According to formula

Set the wavelength link cost on the physical link that the rest of the working tree does not pass through;

Among them, b _t , b _w , b _p , and b _new respectively represent the total bandwidth, working bandwidth, protection bandwidth of the optical path and the newly allocated protection bandwidth if the protection multicast forest passes through the optical path:

α _ll is the level of the logical link;

中所有MC波长节点到v_tail的代价最小的路径，然后从

个代价最小路径中再选出代价最小的路径；如果找到代价最小的路径，将该路径记作P_min，对应的中的节点为v_exp and；将P_min添加到v_exp and的保护段集合中，P_min经过的波长链路的使用状态标记为“被用于保护”；将保护段经过的波长链路的使用状态标记为“被用于保护”后，将工作段经过的物理链路添加到各波长链路的数组A₃中，如果未找到，转步骤(3.3)；Step (3.2.3), calculate respectively

The least-cost path from all MC wavelength nodes to v _tail in , and then from

Select the path with the minimum cost from the paths with the minimum cost; if the path with the minimum cost is found, record this path as P _min , and the corresponding The node in is v _{exp and} ; P _min is added to the protection section set of v _{exp and} , and the use state of the wavelength link that P _min passes through is marked as "used for protection"; the wavelength link that the protection section passes through After the use state is marked as "being used for protection", the physical link that the working section passes through is added to the array A ₃ of each wavelength link, if not found, go to step (3.3);

If all working segments are successfully protected, the algorithm ends successfully; otherwise, go to step (3.3);

Step (3.3), delete all protection sections on the subtree, for the wavelength link on each protection section, delete the physical link that the working section passes through from A ₃ , if A ₃ =Φ after deletion, the wavelength link The use state of the road is marked as "unused", otherwise the use state is not changed, the protection fails, and the algorithm ends.

Step (4), business departure

When the business leaves, it is necessary to release the resources occupied by the working multicast forest and the protection multicast forest. The release method of the working multicast forest resources is as follows:

Step (4.1), successively releasing the bandwidth occupied by each optical path of the working multicast forest and the protection multicast forest;

的光路，删除其保护路，将其标志为“WDM层未保护”状态，设置保护路经过的各波长链路的使用情况为“未使用”；Step (4.2), for WDM layer protection is provided but its workload is below the threshold

For the optical path, delete its protection path, mark it as "WDM layer unprotected" state, and set the usage status of each wavelength link that the protection path passes through to "unused";

Step (4.3), for the optical path whose used bandwidth is 0, delete this optical path: set the usage of each wavelength link that the optical path passes through as "unused"; add one to the number of optical transmitters at the source node of the optical path; Increment the number of receivers by one;

Step (4.4), successively releasing the occupied bandwidth on each optical tree of the work multicast forest and the protection multicast forest;

Step (4.5), after the bandwidth is released, for the WDM layer protection is provided but its workload is lower than the threshold The optical tree, delete all the protection sections of the optical tree, mark it as "WDM layer unprotected" state, set the usage of each wavelength link passed by each protection section as "unused";

Step (4.6), for the optical tree whose used bandwidth is 0, delete the optical tree: set the use of each wavelength link that the optical tree passes to be "unused"; add one to the number of optical transmitters at the source node of the optical path; Add one to the number of optical receivers at the destination node;

The release methods for protecting multicast forest resources are as follows:

Check in turn each subtree that the protection multicast forest passes through, and subtract the bandwidth corresponding to the physical link that the business working multicast forest passes through in the array _A1 of the subtree from the requested bandwidth of the service; if a certain physical link in _A1 The bandwidth corresponding to the path is 0, delete the physical link from _A1 , and reset the value of the protection bandwidth to the maximum value of the corresponding bandwidth of each physical link in _A1 ;

删除子树上的所有保护段；对于各保护段上的波长链路，将工作段经过的物理链路从A₃中删除；如果删除后A₃＝Φ，将该波长链路的使用状态标记为“未使用”，否则不改变使用状态。If the load of a subtree that provides WDM layer protection is below the threshold

Delete all protection segments on the subtree; for wavelength links on each protection segment, delete the physical link that the working segment passes through from A ₃ ; if A ₃ = Φ after deletion, mark the use state of the wavelength link It is "unused", otherwise the usage status will not be changed.

The subtree-based multi-cast sharing multi-layer protection method in the WDM optical network of the present invention can expand the application range of the traditional multi-cast sharing multi-layer protection method, consider multiple constraints when performing multi-layer protection, and provide multiple strategies The following multi-layer protection method for multicast sharing.

Description of drawings

Figure 1 is a schematic diagram of the evolution of the network structure from multi-layer overlapping to two-layer;

Figure 2 is a schematic diagram of an overlapping model;

FIG. 3 is a schematic diagram of a peer-to-peer model;

4 is a schematic diagram of a physical topology example (physical topology N);

FIG. 5 is a schematic diagram of a wavelength layered graph (wavelength layered graph G) corresponding to the physical topology N;

Fig. 6 is the schematic diagram of network model;

FIG. 7 is a schematic diagram of a network node;

Figure 8 is a wavelength layered diagram;

Figure 9 is a basic multi-layer auxiliary diagram;

Figure 10 is a multi-layer auxiliary diagram after adding the admission link;

FIG. 11 is a schematic diagram of a node splitting light first and then converting wavelength;

FIG. 12 is a schematic diagram of a node firstly converting wavelengths and then splitting light;

FIG. 13 is a schematic diagram of an MC wavelength node;

FIG. 14 is a schematic diagram of an example 1 of light tree segmentation;

FIG. 15 is a schematic diagram of an example 2 of light tree segmentation;

FIG. 16 is a schematic diagram of a third example of light tree segmentation;

FIG. 17 is a schematic diagram of an example 4 of light tree segmentation;

FIG. 18 is a schematic diagram of an example five of light tree segmentation;

Fig. 19 is a schematic diagram of self-sharing protection.

FIG. 20 is a schematic diagram of physical link separation of subtrees.

Detailed ways

The subtree-based multicast sharing multi-layer protection method in the WDM optical network of the present invention will be further described in detail below with reference to the accompanying drawings.

1. Optical network basic platform

1 Overview of IP over WDM network and its key technologies

1.1 WDM technology

The continuous high-speed growth of mobile services, 3G emerging services are ready to launch, and the vigorous development of Internet services such as distance education, video conferencing, video-on-demand, and e-commerce have led to explosive growth in data communication services. The explosive growth of business demands puts forward new requirements for the capacity, function and performance of the communication system.

The easiest way to increase the bandwidth of a communication system is to lay more optical fibers, but laying optical fibers is expensive, and is limited by physical conditions such as the natural environment, and the scalability is poor. Another method is to use Time Division Multiplexing (TDM) technology, which improves the transmission bit rate, but the transmission capacity of a single optical fiber is still limited, and the optical fiber bandwidth cannot be effectively used. In this context, Wavelength Division Multiplexing (WDM) technology came into being. Wavelength division multiplexing is a technology that transmits multiple optical carrier signals of different wavelengths in the same optical fiber. At the sending end, the optical carrier signals of different wavelengths are combined through a multiplexer (Multiplexer) and put into one optical fiber for transmission; at the receiving end, the optical carrier signals of different wavelengths are separated through a demultiplexer, and the machine into the original signal. Each wavelength in the optical fiber is transmitted independently without affecting each other, which greatly improves the transmission capacity of the optical fiber and makes wavelength division multiplexing the best way to expand network capacity. With the reduction of the cost of optical devices, and the breakthrough and maturity of new technologies such as DQPSK, DP-QPSK and other modulation technologies, electronic dispersion compensation, and super out-of-band FEC coding, the single wavelength is 40Gbit/s, and the transmission link capacity is 1.6Tbit/s, etc. The system is already commercially available. Japan's NEC and France's Alcatel have respectively achieved the latest world records for transmission capacity of 10.9Tbit/s (273×40Gbit/s) and 10.2Tbit/s (256×40Gbit/s) over a distance of 100km.

The traditional point-to-point WDM system structure adopts a simple linear method and expands capacity by wavelength channels, which can provide a large amount of original bandwidth. It needs to introduce large-capacity flexible optical node equipment at network nodes to convert it into an actual networking that can be flexibly applied. bandwidth, realize WDM layer interconnection, and build an optical transport network (Optical Transport Network, OTN). Such optical node equipment mainly includes reconfigurable optical fork multiplexer (Optical Add-Drop Multiplexer, OADM) and optical cross-connect (Optical Cross Connect, OXC). By introducing OADM at the intermediate node of the network, a group of selected wavelengths can be inserted or dropped locally, and traffic can be flexibly added or dropped. As the WDM network develops towards the mesh network, it is necessary to achieve greater granularity at the network hub node, including the processing of optical signals at the wavelength, waveband, and even fiber granularity. It is necessary to introduce OXC at the hub node. It mainly completes functions such as connection, bifurcation, protection and recovery at the wavelength, waveband and fiber level.

According to the application type, OXC can be divided into Fiber Cross Connect (FXC), Wavelength Selective Cross Connect (WSXC) and Wavelength Interchange Cross Connect (WIXC). FXC switches all wavelengths on an input fiber to any output fiber at one time; WSXC switches a wavelength on an input fiber to the same wavelength on any output fiber; WIXC has wavelength conversion capabilities and can Switch a wavelength on an input fiber to any wavelength on any output fiber. According to the implementation method, OXC can be divided into OXC (OEO-OXC, electric OXC) using electric cross-connect matrix and OXC (OOO-OXC, all-optical OXC) using all-optical cross-matrix. The electrical OXC converts optical signals into electrical signals through photoelectric conversion, and then converts them into optical signals for output after cross-connection processing. All-optical OXC does not require photoelectric conversion, and all crossovers are performed at the WDM layer. OADM and OXC only select wavelengths with local services to add and drop, and other wavelengths pass through network nodes unimpeded, which is called bypass. OADM and OXC have flexible reconfigurability, so that the network has wavelength routing capability, and establishes an end-to-end wavelength path (optical path, lightpath). With the continuous progress of OADM and OXC technology, WDM optical network gradually develops from linear and ring network to complete mesh network.

Although the OXC has flexible networking capabilities, the traditional OXC only has static configuration capabilities. In recent years, IP services have gradually become the main traffic of network communications. Due to the uncertainty and unpredictability of IP services, the requirements for dynamic configuration of network bandwidth are becoming more and more urgent. The manual configuration method is time-consuming, error-prone, and cannot be configured in time, and its shortcomings are gradually emerging. To adapt to the needs of new services, the WDM optical network must be able to make full use of the huge bandwidth capacity, reasonably allocate services, establish connections for services as soon as possible, and provide protection and recovery mechanisms. At the same time, it can also provide different service qualities according to service requirements Quality of Service, QoS) level of service. Automatic Switched Optical Network (Automatic Switched Optical Network, ASON) ^{[5, 6]} is produced under such a background. It can automatically manage the connection of the optical network. This optical network with an independent control plane is called an intelligent optical network.

The intelligent optical network can automatically discover changes in topology, resources and services; it can quickly and dynamically establish optical connections to realize the dynamic allocation of network resources; Provide protection and recovery; can provide more new high-speed and revenue-increasing services, such as ultra-bandwidth services and non-standard bandwidth services, on-demand bandwidth services, dynamic virtual ring configuration and end-to-end circuit configuration services, virtual optical network services, etc. At present, international standardization organizations such as the International Telecommunication Union (ITU-T), the Internet Engineering Task Force (IETF), the Optical Internet Forum (OIF) and the Optical Domain Service Interconnection Alliance (ODSI) are actively formulating relevant standards in the field of intelligent optical networks. Work.

1.2 Network Model

With the development of services such as video conferencing, Internet services are gradually diversified, and IP services have become the main data communication traffic. As the leading transmission network, WDM optical network provides huge transmission capacity. The integration of IP and WDM will become the trend of future network development. The interconnection model of the transmission network is also gradually developing from the traditional IP over ATM over SDH/SONET over WDM multi-layer overlapping structure to the IP over WDM two-layer structure, as shown in Figure 1. In a multi-layer overlapping network structure, the IP layer is used to provide services, the ATM layer provides quality of service (Quality of Service, QoS) guarantee for business connections, and the SDH/SONET layer uses its protection ring mechanism to provide protection and recovery mechanisms for the network. The WDM layer provides huge transmission bandwidth. However, in the multi-layer overlapping network structure, the cell mechanism of ATM brings a large extra overhead and reduces the bandwidth transmission efficiency. With the development of WDM optical network from ring network to mesh network, although the SDH/SONET protection mechanism is fast and effective, its protection cost is relatively high, and the SDH/SONET protection mechanism is no longer applicable. In order to reduce network operating costs and improve bandwidth resource utilization, the ATM layer and SDH/SONET layer gradually disappeared, and the transmission network eventually evolved into a two-layer network structure of IP over WDM, that is, IP services are directly transmitted on the WDM optical network.

In the IP over WDM network, there are three control models, which are overlap model, peer-to-peer model and extension model.

(1) Overlapping model

The overlapping model is also called the client-server model, proposed by ITU-T. As shown in Figure 2, in this model, the IP layer and the WDM layer are independent of each other, have their own control planes, run different routing protocols, and do not exchange routing information such as network topology between routing protocols. The IP layer and the WDM layer are connected together through the User to Network Interface (UNI). The WDM layer is composed of subnets, and the subnets are interconnected through the Network to Network Interface (NNI). This model can realize effective subnet division and facilitate the control and upgrade of each subnet. The IP layer can only see the optical paths established between edge devices in the WDM layer. In this model, the internal structure of the WDM layer network is transparent to the IP layer. The IP layer sends a service transmission request to the WDM layer through the UNI, and the WDM layer is responsible for the control of the optical path, and the intelligence of the network is fully reflected in the WDM layer. This model maximizes the control separation between the WDM layer and the IP layer. The disadvantage of the overlapping model is that the optical paths established between edge devices at the WDM layer are reflected as logical links at the IP layer, and the link state announcements of these links will cause a large network overhead.

(2) Peer-to-peer model

The peer-to-peer model was proposed by the IETF. As shown in Figure 3, in this model, the IP layer and the WDM layer are equal and managed by a unified control plane. The IETF named the control plane Generalized Multi-protocol Label Switching (GMPLS). In the peer-to-peer model, both the IP router and the OXC are called label switching routers (Label Switching Router, LSR). They run the same routing and signaling protocols, and exchange routing information such as link status with each other. The IP layer can see The internal structure of the WDM layer, the WDM layer is no longer transparent to the IP layer. In the peer-to-peer model, since the IP layer and the WDM layer are peer-to-peer, each LSR needs to exchange a large amount of link state and signaling control information, resulting in a large network overhead. The internal structure of the WDM network is no longer transparent to users, which is not conducive to the stability of the network and the division of subnets in the WDM network; the fault recovery mechanism of the IP layer and the WDM layer requires unified coordination and complicated control.

(3) Extended model

In the extended model, the IP layer and the WDM layer are independent of each other and run independent routing protocols, but they can exchange certain reachability information through UNI. For example, assign an IP address to the OXC in the WDM network, and then provide it to the IP layer through the WDM layer routing protocol to realize automatic path finding, etc. The key issue of this model is how to exchange reachability information at UNI.

The present invention is primarily directed to a peer-to-peer model.

1.3 Key technologies of IP over WDM network

In the IP over WDM network, the IP layer is used as the service provision layer, and the WDM layer is used as the transport layer. The key issue is how to realize the seamless connection between the IP layer and the WDM layer. GMPLS proposed by IETF provides a good solution. In addition, the bandwidth granularity of low-speed services received by IP is generally smaller than the capacity of a single wavelength, so how to effectively aggregate services in IP over WDM, and then use the WDM layer to carry these low-speed services, and provide corresponding protection/recovery mechanisms for services is an urgent problem. The problem. In order to solve the above-mentioned problems, key technologies such as GMPLS, traffic grooming, routing and wavelength allocation closely related to traffic grooming, and network survivability have been mainly proposed at present.

1.3.1GMPLS technology

GMPLS is the product of the development of Multi-Protocol Label Switching (MPLS) to WDM layer, and it effectively realizes the seamless integration of IP layer and WDM optical network. GMPLS inherits almost all excellent features such as traffic engineering in MPLS, and expands the MPLS protocol at the same time. GMPLS focuses on the control plane and supports multiple resource granularities such as packet switching, time-division switching, wavelength switching, and space-division switching (optical fiber switching). GMPLS also supplements and modifies the original signaling and routing protocols in MPLS, and designs a new link management protocol (Link Management protocol, LMP).

(1) Universal multi-protocol label

GMPLS defines five interface types, which are: (a) Packet Switch Capable (PSC): Packet switching, by identifying the packet boundary, and forwarding the packet according to the information in the packet header. (b) Layer 2 Switch Capable (L2SC): Perform cell switching, and forward cells according to the information in the cell header by identifying the passing boundary. (c) Time Division Multiplexing Capable (TDMC): Service forwarding according to TDM time slots. (d) Lambda Switch Capable (LSC): Forward services according to the optical wavelength or optical band carrying the service. (e) Fiber Switch Capable (FSC): Forwarding according to the actual position of the fiber in the physical space. GMPLS extends the label in MPLS, so that it can also mark TDM time slots, wavelengths, wave bands, and optical fibers. GMPLS uniformly marks IP data exchange, TDM circuit exchange and WDM optical exchange. Packet switching labels continue to use labels in MPLS, and redefine circuit switching and optical switching labels, including request labels, general labels, suggested labels, and set labels. Among them, the request label is used for the establishment of Label Switching Path (LSP); the general label is used to indicate the service transmission along the LSP after the LSP is established; the recommended label is used to configure the LSP to avoid the delay caused by reverse configuration , to quickly establish an optical connection; setting tags is used to limit the range of tags selected by downstream nodes.

(2) Universal Label Switching Path

Since GMPLS supports the exchange of different resource granularities, in order to avoid the waste of bandwidth resources when establishing an LSP, it is necessary to nest low-level LSPs (PSC, L2SC, TDMC, LSC, and FSC levels in turn) into high-level LSPs. It is called LSP classification. The LSP classification technology is realized through the GMPLS label stack, which allows low-level LSPs with the same ingress to converge, transparently pass through high-level LSPs, and then separate at the remote end. Using the LSP classification technology requires that the start and end device interfaces of each LSP be of the same type. The same interface means that an interface of a certain level can use a certain technology to multiplex multiple LSPs. In MPLS, to establish a bidirectional LSP, two unidirectional LSPs with opposite directions must be established, and the establishment time is prolonged and the signaling overhead is large. GMPLS has improved it, and can establish two-way LSP. When establishing a bidirectional LSP, it is required that the LSPs in both directions have the same traffic engineering parameters, including resource requirements and protection/restoration mechanisms. When GMPLS establishes a bidirectional LSP, the uplink and downlink paths use the same signaling message, and the two LSPs are established simultaneously, which effectively reduces the delay of LSP establishment and reduces the signaling overhead.

(3) Link management

In an optical network, the number of parallel optical fiber links between two adjacent OXCs and the number of wavelengths multiplexed in each optical fiber are huge. If a broadcast mechanism is provided for them separately, it will cause link maintenance and transmission during broadcasting. The amount of information is very large, and it is unrealistic to provide an IP address for each optical fiber and each wavelength at the same time. For this reason, GMPLS has adopted link bonding and unnumbered links to deal with this problem. If the parallel links belong to the same link group, then these links can be bonded to form a bonded link. The same link group refers to belonging to the same shared risk link group (Shared Risk LinkGroup, SRLG) number, the same link coding type, and the same protection/restoration type. This greatly reduces the size of the link state database and reduces the signaling overhead caused by broadcasting. The unnumbered link means that the address of the link is identified by a two-tuple (router ID, link number) instead of using an IP address. GMPLS has developed a link management protocol, which is responsible for functions such as control channel management, link summary, link verification, and fault management between two adjacent nodes, among which link verification and fault management are optional.

(4) Routing and signaling protocols

When GMPLS adopts general multi-protocol labels to establish LSP, factors of bandwidth and protection/recovery capability need to be considered, which requires nodes to record link state information. For this reason, GMPLS uses the two signaling protocols RSVP and LDP defined by MPLS traffic engineering respectively It is extended to RSVP-TE and CR-LDP, and parameters such as bandwidth, type, and protection/restoration mechanism of LSP are exchanged through signaling. Routing can either use the display routing method or the multi-hop method. In addition, GMPLS also expands the routing protocols OSPF and IS-IS used for traffic engineering control in the domain to OSPF-TE and IS-IS-TE respectively. Link management mechanisms such as link binding and link management protocols in GMPLS can reduce the overhead caused by maintaining link state information in routing and signaling protocols.

1.3.2 Routing and wavelength allocation

Given a set of connections, the process of creating an optical path and assigning a wavelength to each connection is called Routing and Wavelength Assignment (RWA). Connection requests can be divided into two types: static connection requests and dynamic connection requests. For static services, the set of service connection requests is given in advance, and its goal is to establish optical paths for these connection requests, and to minimize the network resources used globally, such as the number of wavelengths, the number of fibers, etc., that is, given a fixed number of Number of wavelengths to establish lightpaths for as many connection requests as possible. The problem of static routing and wavelength assignment is called Static Lightpath Establishment (SLE) problem. For dynamic services, when a connection request arrives, an optical path is established for it, and when the service leaves, the optical path is revoked. Its goal is to establish optical paths for dynamically arriving services, and reduce the blocking rate as much as possible, or maximize the number of optical paths established in the network at the same time. Dynamic routing and wavelength allocation is known as the Dynamic Lightpath Establishment (DLE) problem.

At present, the problem of routing and wavelength assignment is decomposed into two sub-problems of routing selection and wavelength assignment. First find an optimal route (such as the shortest path), and then check whether there is an available wavelength for assignment. If no wavelength can be assigned to the route because of the wavelength continuity constraint, then calculate the suboptimal route and continue to repeat the above process until a route that satisfies the wavelength continuity constraint is found, otherwise the connection request is blocked. Before finding the route, the method may have to iterate many times. To solve this problem, the concept of wavelength layered graph is proposed, which converts routing and wavelength allocation into graph theory, and simultaneously solves the problem of routing selection and wavelength allocation.

和

通过一条有向边

连接在一起，其中，

假设访问节点a∈A连接到波长路由器节点r∈R上。在G中，为每个访问节点a创建两个节点，一个代表业务生成部分(源)，另外一个代表业务终结部分(目的)。这两个节点分别标识为向G中添加

到节占

以及

到

的有向边。因此G中节点的个数|V|＝|R|×|W|+2×|A|；有向边的条数|E|＝2×|L|×|W|。例如，图4所示物理拓扑对应的波长分层图如图5所示。其中，每条波长路由器间的链路是由两条反向单向光纤组成的，每条光纤中波长数为2。通过波长分层图，路由和波长分配问题就变得相对简单了。只要在某个波长平面上找到了连接源和目的的路由，该路由就一定能够满足波长连续性约束。Define the network topology as N(R, A, L, W), where R is the set of wavelength router nodes, A is the set of access nodes, L is the undirected edge, and W is the number of available wavelengths in each physical link. Each access node is bound to a wavelength router and provides electro-optical conversion to support electrical switching. Each side is composed of two reverse unidirectional optical fibers, and each optical fiber can carry |W| wavelength channels. Define the wavelength layered graph model as G(V, E), which is a directed graph. The process of obtaining the wavelength hierarchical graph according to the physical topology N is as follows: each node i∈R in N is replicated |W| times in G, and these nodes are respectively identified as If a link l ∈ L connects router i and router j, where i, j ∈ R, then for any w ∈ W,

and

through a directed edge

connected together, where,

Assume that access node a∈A is connected to wavelength router node r∈R. In G, two nodes are created for each access node a, one represents the service generating part (source), and the other represents the service terminating part (destination). These two nodes are identified as Add to G

to save

as well as

arrive

The directed edge of . Therefore, the number of nodes in G |V|=|R|×|W|+2×|A|; the number of directed edges |E|=2×|L|×|W|. For example, the wavelength layer diagram corresponding to the physical topology shown in FIG. 4 is shown in FIG. 5 . Wherein, the link between each wavelength router is composed of two reverse unidirectional optical fibers, and the number of wavelengths in each optical fiber is 2. Through the wavelength hierarchical diagram, routing and wavelength allocation issues become relatively simple. As long as a route connecting the source and the destination is found on a certain wavelength plane, the route must be able to satisfy the wavelength continuity constraint.

1.3.3 Traffic flow grooming

The WDM optical network provides huge transmission capacity, and the system with a single wavelength capacity of 40Gbit/s has been commercialized. However, in practical applications, the requested bandwidth of each service is relatively low compared to the capacity of a single wavelength, such as OC-12, OC-48, and OC-192. Therefore, allocating a wavelength for each low-speed service request will cause a lot of bandwidth waste. Creating an optical path for each request will also increase the electrical switching cost of the network (for example, more optical transceivers need to be deployed), increasing the cost of the network. Most importantly, the number of available wavelengths in real networks is much less than the number of arriving low-speed services. Therefore, traffic grooming is a basic function that a WDM optical network must have to increase network throughput, improve wavelength resource utilization, and reduce network costs. Traffic grooming in a WDM optical network is a technology for converging low-speed services onto a high-speed optical path for transmission, with the goal of minimizing network costs or maximizing network throughput.

In a WDM optical network, traffic grooming needs to solve three problems: (1) establish optical paths, (2) allocate wavelengths to optical paths to meet wavelength continuity, and (3) route low-speed services on logical topologies. According to whether the service is predetermined, traffic grooming can be divided into two categories: static traffic grooming and dynamic traffic grooming. For static traffic grooming, these three problems can be solved together using an Integer Linear Programming (ILP) optimization method. However, for large networks, the complexity of problem solving increases, and heuristic algorithms are generally used to solve three problems separately. In dynamic traffic grooming, when a service connection request arrives, it first looks for a route on the logical topology. If the destination is unreachable or the bandwidth of the existing optical path is exhausted, a new optical path is created to carry the new service connection.

1.3.4 Network Survivability

Network survivability refers to the ability of the network to provide uninterrupted services after a failure occurs. With the development of WDM technology, hundreds of wavelengths can be multiplexed in a single fiber, and the capacity of each wavelength can reach tens or even hundreds of Gbit/s. Once a network failure (such as link failure, etc.) occurs, it will cause The service failure of the order of Tbit/s will cause serious impact. Therefore, the survivability of WDM optical network has become an important issue that people pay more and more attention to.

WDM layer survivability technologies can be divided into two categories: Protection and Restoration. Protection means that protection resources are pre-reserved for services when a service connection is established. Once a failure occurs, the services will be carried by the protection resources. Protection has a short protection switching time, but because protection resources need to be reserved in advance, and when no fault occurs, the protection resources are idle, so the resource utilization rate is low. Restoration means not reserving protection resources for services in advance, and when a fault occurs, according to the utilization of network resources at that time, rerouting is used to dynamically find idle resources to carry the affected services. Recovery has a high resource utilization rate, but because it dynamically looks for available resources to carry services after a fault occurs, the protection switching time is relatively long, and when the network load is heavy and there are not enough available resources, it will lead to fault recovery fail.

According to whether the protection resource is shared, the protection mechanism is divided into two categories: dedicated protection (Dedicated Protection) and shared protection (Shared Protection). In dedicated protection, the protection resource reserved for a certain working path is exclusive, and other protection paths cannot be used again. In shared protection, if two working paths will not fail at the same time (for example, the two working paths are separated by physical links), then they can share protection resources. From the perspective of resource utilization, shared protection has a higher resource utilization rate than dedicated protection. The higher the service intensity of the network, the more obvious the advantages of shared protection. In terms of protection switching time, dedicated protection is shorter than shared protection. This is because in dedicated protection, the protection resources are exclusive and can be pre-configured. Once a failure occurs, the affected services will be switched to the protection resources; while in shared protection, it is impossible to pre-judge which services will fail and cannot be configured in advance. After a fault occurs, devices such as OXC on the protection path are configured through a certain signaling mechanism, so the protection switching time is relatively long.

According to the granularity of protection, the protection mechanism can be divided into path protection, link protection and segment protection. Path protection refers to providing an end-to-end protection path for the working path. Link protection refers to calculating a protection path for each link on the working path. Once a fault occurs, both ends of the faulty link are responsible for service switching without the participation of the source and sink nodes. In section protection, the working road is first divided into sections, and then a protection road is calculated for each section, and the beginning and end of the section are responsible for fault recovery. In comparison, path protection has higher resource utilization, link protection does not require the source and sink nodes to participate in fault recovery, and has a faster protection switching time. Segment protection tries to find a balance between the two.

As one of the survivability technologies, the protection technology has a faster protection switching time and can meet the requirements of a large number of real-time services, so the present invention mainly relates to the protection technology.

2 network model

The network model can be described as a directed connected graph G _p (V, L, W), as shown in Figure 6. Among them, V, L, and W represent the node set of the network, the physical link set, and the wavelength set of each physical link, respectively; |V|, |L|, |W| represent the number of nodes, the number of physical links, and the Number of wavelengths in each physical link.

2.1 Network Node

Network nodes are composed of OXC and IP routers integrated together. Among them, the IP router is responsible for accepting service requests. OXC consists of a wavelength switching matrix, a low-speed service grooming matrix and a set of tunable optical transceivers (as shown in Figure 7). After the wavelength in the input fiber is demultiplexed, it can be directly switched to the corresponding wavelength of the output fiber through the wavelength switching matrix, or switched to the optical receiver to convert it into an electrical signal and enter the low-speed grooming matrix. The local business is processed by the IP router through the low-speed service data flow port, and the non-local business is converted into an optical signal through the optical transmitter, re-enters the wavelength switching matrix, and is switched to the corresponding wavelength of the corresponding optical fiber. That is to say, if a certain wavelength channel in the input fiber does not contain local services, it can be directly passed through the wavelength switching matrix to the output fiber, that is, bypassed; the wavelength channel with business up/down is down through the optical transceiver to the electrical domain for processing . Each network node maintains global link state information, including the use of wavelengths on each physical link, the use of bandwidth on each optical path, and so on.

In addition, the constraints considered in the present invention mainly include: constraints on the number of optical transceivers, constraints on wavelength continuity under sparse partial wavelength conversion, and sparse partial optical splitting constraints.

(1) Number of optical transceivers

Each network node deploys a certain number of optical transmitters and optical receivers, and the present invention assumes that the number of optical transmitters and optical receivers of the same node is the same.

(2) Wavelength conversion capability

According to whether the nodes have the wavelength conversion capability, the nodes can be divided into three categories: nodes without wavelength conversion capability, nodes with complete wavelength conversion capability, and nodes with partial wavelength conversion capability.

No wavelength conversion capability means that the wavelength channel in the input fiber can only be switched to the wavelength channel of the same wavelength in the output fiber through the wavelength switching matrix.

The full wavelength conversion capability means that a wavelength channel in an input fiber can be switched to a wavelength channel of any wavelength in an output fiber through a wavelength switching matrix.

Partial wavelength conversion capability, the wavelength channel in the input fiber can be switched to the wavelength channel of a certain range of wavelengths adjacent to the wavelength in the output fiber through the wavelength switching matrix. For example, if a node has partial wavelength conversion capability and its wavelength conversion range is 2, then wavelength λ ₄ can be converted to wavelengths λ ₂ , λ ₃ , λ ₅ and λ ₆ . Nodes with partial wavelength conversion capabilities may also have different wavelength conversion ranges.

In the present invention, for the convenience of description, the concept of wavelength conversion range is used to describe the wavelength conversion capability of nodes, and the wavelength conversion range of nodes without wavelength conversion capability is marked as 0, while the wavelength conversion range of nodes with full wavelength conversion capability is |W|.

(3) Light splitting ability

In a WDM optical network, to enable nodes to have multicast capability, optical splitters need to be deployed on nodes. According to the strength of splitting ability, network nodes can be divided into three categories: no splitting capability MI (Multicast Incapable), full splitting capability, and partial splitting capability.

No splitting ability means that a node can only send one input signal to one output port. If it is not a multicast destination node, it can only be used as an intermediate non-forking node of the multicast tree; if it is a multicast destination node, then It can only be used as a leaf node of a multicast tree.

Full splitting capability means that a node can send input signals to any number of output ports.

Partial splitting capability means that a node can send input signals to a certain number of output ports.

The latter two nodes are collectively called MC (Multicast Capable) nodes, which can be used not only as the destination node of the multicast tree, but also as the intermediate node of the optical tree. When used as an intermediate bifurcation node, there is no limit to the out-degree of a node with full splitting capability; for a node with partial splitting capability, if it is not a destination node, its out-degree cannot exceed its maximum splittable number; A node needs to split an optical signal to be dropped locally, and its outgoing degree cannot exceed its maximum splittable optical number minus one.

Same as the wavelength conversion capability, for the convenience of description, the present invention uniformly uses the maximum splittable number to describe the splitting capability of nodes, and sets the maximum splittable number of nodes without splitting capability to 1, while the wavelength conversion range of nodes with complete splitting is The degree of the node.

Nodes with both wavelength conversion and splitting capabilities have two node structures: (1) perform wavelength conversion first and then perform splitting; (2) perform splitting first and then perform wavelength conversion. The first type of node structure is simpler, and the two wavelengths separated must have the same wavelength, which has certain limitations. The second type of node structure is more flexible and is the direction of future development. Each of the split wavelengths can be converted into wavelengths, so the number of wavelength converters is relatively large. In addition, from the method point of view, the design method based on the first node structure is actually a special case of the second node structure (light splitting and conversion to the same wavelength), so the present invention adopts the second node structure.

2.2 Network link

Two network nodes are connected by a pair of unidirectional optical fibers with opposite transmission directions. Both fibers have the same set of wavelengths, and the number of wavelengths is |W|. The two optical fibers are separated by physical links, and the use of wavelengths and data transmission are independent of each other and do not affect each other.

2.3 Basic structure

For a given physical topology G _p (V, L, W), follow the steps below to construct a multi-layer auxiliary graph.

到波长节点

增加一条链路

称为波长链路，每条波长链路对应于其所在物理链路中一个波长。这样便构造出了波长分层图，其中每个波长对应的波长节点和波长链路构成的拓扑，称为波长平面。例如，根据图6中物理拓扑构造的波长分层图如图8所示(假设每条物理链路中波长数为2)。(1) Copy each node v _i ∈ V, i=1, 2, ..., |V|, copy |W| times, respectively marked as called wavelength nodes. All wavelength nodes copied from the same node have the same ID, which is their physical node ID. If there is a directed physical link l _ij from node v _i to node v _j , then for all w=1, 2, ...|W|, from wavelength node

to wavelength node

add a link

It is called a wavelength link, and each wavelength link corresponds to a wavelength in the physical link where it is located. In this way, a wavelength layered graph is constructed, in which the topology of wavelength nodes and wavelength links corresponding to each wavelength is called a wavelength plane. For example, the wavelength layer diagram constructed according to the physical topology in FIG. 6 is shown in FIG. 8 (assuming that the number of wavelengths in each physical link is 2).

以及

到

的波长链路标记为已使用，在逻辑拓扑上，增加v′₂到v′₄的逻辑链路，得到的多层辅助图如图9所示。(2) Copy each node v _i ∈ _V , i=1, 2, . Logical nodes are used to receive and terminate service connections, and can be understood as IP router nodes. If at the WDM layer, there is an optical path from node v _i to node v _j , then add a virtual link from node v' _i to node v' _j , which is called a logical link (the logical link is the optical path hereinafter ), the bandwidth of the logical link is the capacity of one wavelength (assuming that all optical paths are single-wavelength channels). The topology composed of logical nodes and logical links is called logical topology. Combining logical topology and wavelength layered graphs together constitutes the basic multi-layer auxiliary graph. Still taking the topology in FIG. 6 as an example, assume that an optical path from node v ₂ to node v ₄ is created at wavelength λ ₂ , and the optical path passes through intermediate node v ₃ . Put the wavelength layer on the map arrive

as well as

arrive

The wavelength link of is marked as used. In the logical topology, add the logical link from v′ ₂ to v′ ₄ , and the obtained multi-layer auxiliary diagram is shown in FIG. 9 .

2.4 Constraints on the number of optical transceivers

以及

到v′_i的接纳链路。When unblocking the traffic of the business, sometimes the route to the destination node cannot be found by using the existing logical link, and it is necessary to create a new optical path at this time. Each time a new optical path is created, the source node of the optical path needs to consume one optical transmitter, and the destination node consumes one optical receiver. As the receiving node of the service, the logical link needs to record the number of available optical transmitters and available optical receivers. As long as one of the source and destination nodes does not meet the requirements, the optical path cannot be established. In order to transform the digital constraints on the number of optical transceivers into the content of graph theory, the concept of admission links is used to describe the constraints on the number of optical transceivers. For any node v _i ∈ V, i=1, 2, ..., |V|, add v′ _i to

as well as

The admission link to v′ _i .

Taking Figure 9 as an example, assuming that the number of optical receivers and optical transmitters at each node is 2, since a new optical path is created from v ₂ to v ₄ , the number of available optical transmitters at v ₂ is reduced by one, and the number of available optical transmitters at v ₄ is The number of light receivers is reduced by one. Then the obtained multi-layer auxiliary diagram is shown in FIG. 10 , wherein the numbers next to the logical nodes, the front ones represent the number of available optical transmitters, and the latter ones represent the number of available optical receivers.

2.5 Constraints on wavelength conversion capability

The invention considers the constraint of the wavelength conversion capability of the sparse part, which can be solved by perfecting the multi-layer auxiliary graph.

w1＝1，2，...，|W|到w2＝max{1，w1-r}，...w1-1，w1+1，...min{|W|，w1+r}的虚链路，称为波长转换链路。For any node v _i ∈ V, its wavelength conversion range is r, then increase

w1 = 1, 2, ..., |W| to A virtual link of w2=max{1, w1-r},...w1-1, w1+1,...min{|W|, w1+r} is called a wavelength conversion link.

After the wavelength conversion capability is introduced, the structure of the optical path and optical tree has changed.

(1) Optical path

In a general sense, in order to meet the wavelength continuity constraint, the optical path requires that the wavelength links passed by the optical path have the same wavelength, that is, the optical path is composed of a group of wavelength links with the same wavelength. When creating a new optical path, it is only necessary to find the route linking the source and destination nodes on a certain wavelength plane. After considering the wavelength conversion capability, the wavelength links passed by the optical path can use different wavelengths. When creating a new optical path, it is no longer routed on a certain wavelength plane, but routed on a multi-layer auxiliary map. At this time, the optical path is an ordered set composed of wavelength links and wavelength conversion links.

(2) light tree

After wavelength conversion is introduced, each node on the optical tree is a wavelength node, and the link from the parent node to the child node may be a wavelength link or a wavelength conversion link.

3 link cost

The present invention adopts wavelength use load balancing on the physical link and bandwidth use load balancing on the optical path, so as to minimize the number of services affected when a physical link failure occurs.

In order to better realize load balancing, the present invention sets different levels for wavelength conversion links, logical links, admission links, and wavelength links, which are respectively called α _wcl , α _ll , α _al , and α _wll . The wavelength conversion link has the highest priority, followed by logical links, reception links, and wavelength links. The level factors vary greatly, such as 1, 100, 10000, and 1000000 respectively. The purpose is to analyze the number of wavelength conversion links and the number of logical links passed through according to the weight of each node obtained by the Dijkstra shortest path algorithm. , the number of admitted links and the number of wavelength links. This prompts the path with the least number of wavelength links to be selected first when selecting a path, followed by a path with a small number of accepted links, that is, a path with a small number of optical transceivers to reduce the number of new optical paths, and finally compare the logic Link usage.

Different optimization objectives can be achieved by changing the rank factors of the admission link and the wavelength link. In the example above, the main goal is to use the fewest number of wavelengths. If the admission link is set with a larger rank factor, then its optimization goal becomes to use the least number of optical transceivers, which is mainly applicable to the network where the number of optical transceivers is the main constraint.

3.1 Wavelength conversion link

Since the wavelength conversion link does not affect the load of the network except for the delay caused by wavelength conversion, the link cost of the wavelength conversion link is shown in Equation 3.1.

W _wcl = 1×α _wcl (3.1)

Because on the multi-layer auxiliary graph, there is a problem of continuous wavelength conversion when using the method introduced in section 2.5 to deal with the wavelength conversion capability of nodes. For example, if the change range of a certain node is 2, then wavelength λ ₅ can be converted to wavelength λ ₇ , but wavelength λ ₇ can be converted to λ ₉ , and wavelength λ ₅ can be converted to wavelength λ ₉ through two wavelength conversions. But the fact is that the wavelength range of this node is 2, and the wavelength λ ₅ cannot be converted to λ ₉ . In the present invention, when running Dijkstra algorithm pathfinding on the multi-layer auxiliary graph, when expanding a certain wavelength node, if its previous hop node is a wavelength node and has the same node ID as it, that is, its previous hop link If the path is a wavelength conversion link, then when the node is extended, the link cost of the wavelength conversion link in its neighbor edge is calculated as ∞ (the actual link cost of the wavelength conversion link is still 0). In this way, the problem that the wavelength conversion exceeds the wavelength conversion range due to the continuous two-hop wavelength conversion link is avoided. In the path calculated in this way, there can only be at most one wavelength conversion link before and after each node. The Dijkstra algorithm used later is all processed as above.

3.2 Logical link

Each logical link corresponds to an optical path at the WDM layer, and the bandwidth capacity of the logical link is the bandwidth capacity of the optical path. There are many ways to measure the load of a logical link, such as the number of LSPs (Label Switched Paths) carried on the logical link, the ratio of the used bandwidth to the total bandwidth, and so on. Considering that different services require different bandwidths, it is difficult to reflect the load of the optical path simply by the number of services, so the ratio of the used bandwidth to the total bandwidth is selected as the standard to measure the load of a logical link. The higher the ratio of the used bandwidth to the total bandwidth, the heavier the load on the logical link. This link should be avoided as much as possible during route selection, so a larger link cost should be set for this link. Similarly, a smaller link cost is set for a link with a lower proportion of the used bandwidth to the total bandwidth.

Let b _t , b _w , b _p , b _r denote the total bandwidth, working bandwidth, protection bandwidth and user request bandwidth of the logical link respectively, then the link cost of the logical link is shown in Equation 3.2.

${\mathrm{<span\; class="notranslate">\; W</span>}}_{\mathrm{<span\; class="notranslate">\; ll</span>}}<span\; class="notranslate">\; =</span>\left\{\begin{array}{cc}<span\; class="notranslate">\; \&infin;</span>& {\mathrm{<span\; class="notranslate">\; b</span>}}_{\mathrm{<span\; class="notranslate">\; t</span>}}<span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; b</span>}}_{\mathrm{<span\; class="notranslate">\; w</span>}}<span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; b</span>}}_{\mathrm{<span\; class="notranslate">\; p</span>}}<span\; class="notranslate">\; <</span>{\mathrm{<span\; class="notranslate">\; b</span>}}_{\mathrm{<span\; class="notranslate">\; r</span>}}\\ <span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; +</span>\frac{{\mathrm{<span\; class="notranslate">\; b</span>}}_{\mathrm{<span\; class="notranslate">\; w</span>}}<span\; class="notranslate">\; +</span>{\mathrm{<span\; class="notranslate">\; b</span>}}_{\mathrm{<span\; class="notranslate">\; p</span>}}}{{\mathrm{<span\; class="notranslate">\; b</span>}}_{\mathrm{<span\; class="notranslate">\; t</span>}}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; \&times;</span>{\mathrm{<span\; class="notranslate">\; \&alpha;</span>}}_{\mathrm{<span\; class="notranslate">\; ll</span>}}& {\mathrm{<span\; class="notranslate">\; b</span>}}_{\mathrm{<span\; class="notranslate">\; t</span>}}<span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; b</span>}}_{\mathrm{<span\; class="notranslate">\; w</span>}}<span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; b</span>}}_{\mathrm{<span\; class="notranslate">\; p</span>}}<span\; class="notranslate">\; \&Greater\; Equal;</span>{\mathrm{<span\; class="notranslate">\; b</span>}}_{\mathrm{<span\; class="notranslate">\; r</span>}}\end{array}\right.<span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 3.2</span>}<span\; class="notranslate">\; )</span>$

3.3 Acceptance link

The link cost of the admission link is used to reflect the use of optical transmitters and optical receivers at the node. For a certain node, when the node is used as the source node of the new optical path, an optical transmitter at the node is consumed; when the node is used as the destination node, an optical receiver is consumed, so for a certain node, the optical transmitter and optical receiver usage are independent of each other.

Let t _t , r _t , t _a , r _a represent the total number of optical transmitters, the total number of optical receivers, the number of available optical transmitters and the number of available optical receivers at the node respectively, then the logic corresponding to the node The link cost of the admission links from a node to all wavelength nodes corresponding to this node is shown in Equation 3.3.

${\mathrm{<span\; class="notranslate">\; W</span>}}_{\mathrm{<span\; class="notranslate">\; al</span>}}<span\; class="notranslate">\; =</span>\left\{\begin{array}{cc}<span\; class="notranslate">\; \&infin;</span>& {\mathrm{<span\; class="notranslate">\; t</span>}}_{\mathrm{<span\; class="notranslate">\; a</span>}}<span\; class="notranslate">\; =</span>{\mathrm{<span\; class="notranslate">\; t</span>}}_{\mathrm{<span\; class="notranslate">\; t</span>}}\\ <span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; +</span>\frac{{\mathrm{<span\; class="notranslate">\; t</span>}}_{\mathrm{<span\; class="notranslate">\; t</span>}}<span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; t</span>}}_{\mathrm{<span\; class="notranslate">\; a</span>}}}{{\mathrm{<span\; class="notranslate">\; t</span>}}_{\mathrm{<span\; class="notranslate">\; t</span>}}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; \&times;</span>{\mathrm{<span\; class="notranslate">\; \&alpha;</span>}}_{\mathrm{<span\; class="notranslate">\; al</span>}}& {\mathrm{<span\; class="notranslate">\; t</span>}}_{\mathrm{<span\; class="notranslate">\; a</span>}}<span\; class="notranslate">\; <</span>{\mathrm{<span\; class="notranslate">\; t</span>}}_{\mathrm{<span\; class="notranslate">\; t</span>}}\end{array}\right.<span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 3.3</span>}<span\; class="notranslate">\; )</span>$

The link cost of the admission link from all wavelength nodes corresponding to this node to its logical node is shown in formula 3.4.

${\mathrm{<span\; class="notranslate">\; W</span>}}_{\mathrm{<span\; class="notranslate">\; al</span>}}<span\; class="notranslate">\; =</span>\left\{\begin{array}{cc}<span\; class="notranslate">\; \&infin;</span>& {\mathrm{<span\; class="notranslate">\; r</span>}}_{\mathrm{<span\; class="notranslate">\; a</span>}}<span\; class="notranslate">\; =</span>{\mathrm{<span\; class="notranslate">\; r</span>}}_{\mathrm{<span\; class="notranslate">\; t</span>}}\\ <span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; +</span>\frac{{\mathrm{<span\; class="notranslate">\; r</span>}}_{\mathrm{<span\; class="notranslate">\; t</span>}}<span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; r</span>}}_{\mathrm{<span\; class="notranslate">\; a</span>}}}{{\mathrm{<span\; class="notranslate">\; r</span>}}_{\mathrm{<span\; class="notranslate">\; t</span>}}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; \&times;</span>{\mathrm{<span\; class="notranslate">\; \&alpha;</span>}}_{\mathrm{<span\; class="notranslate">\; al</span>}}& {\mathrm{<span\; class="notranslate">\; r</span>}}_{\mathrm{<span\; class="notranslate">\; a</span>}}<span\; class="notranslate">\; <</span>{\mathrm{<span\; class="notranslate">\; r</span>}}_{\mathrm{<span\; class="notranslate">\; t</span>}}\end{array}\right.<span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 3</span>}<span\; class="notranslate">\; .</span>\mathrm{<span\; class="notranslate">\; 4</span>}<span\; class="notranslate">\; )</span>$

3.4 wavelength link

The link cost of the wavelength link is used to reflect the load condition of the physical link to which the wavelength link belongs. The load of a physical link can be measured by the ratio of the number of used wavelengths to the total number of wavelengths. The wavelength link has four usage states: unused, used for constructing optical path, used for constructing optical tree, and used for protection.

Let w _{w and} w _p be the number of working wavelengths and protection wavelengths in the physical link to which the wavelength link belongs, respectively. If the wavelength link has been used, then its link cost is ∞, otherwise its link cost is as shown in Equation 3.5 Show.

${\mathrm{<span\; class="notranslate">\; W</span>}}_{\mathrm{<span\; class="notranslate">\; wll</span>}}<span\; class="notranslate">\; =</span>\left\{\begin{array}{cc}<span\; class="notranslate">\; \&infin;</span>& {\mathrm{<span\; class="notranslate">\; w</span>}}_{\mathrm{<span\; class="notranslate">\; w</span>}}<span\; class="notranslate">\; +</span>{\mathrm{<span\; class="notranslate">\; w</span>}}_{\mathrm{<span\; class="notranslate">\; p</span>}}<span\; class="notranslate">\; =</span><span\; class="notranslate">\; |</span>\mathrm{<span\; class="notranslate">\; W</span>}<span\; class="notranslate">\; |</span>\\ <span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; +</span>\frac{{\mathrm{<span\; class="notranslate">\; w</span>}}_{\mathrm{<span\; class="notranslate">\; w</span>}}<span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; w</span>}}_{\mathrm{<span\; class="notranslate">\; p</span>}}}{<span\; class="notranslate">\; |</span>\mathrm{<span\; class="notranslate">\; W</span>}<span\; class="notranslate">\; |</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; \&times;</span>{\mathrm{<span\; class="notranslate">\; \&alpha;</span>}}_{\mathrm{<span\; class="notranslate">\; wll</span>}}& {\mathrm{<span\; class="notranslate">\; w</span>}}_{\mathrm{<span\; class="notranslate">\; w</span>}}<span\; class="notranslate">\; +</span>{\mathrm{<span\; class="notranslate">\; w</span>}}_{\mathrm{<span\; class="notranslate">\; p</span>}}<span\; class="notranslate">\; <</span><span\; class="notranslate">\; |</span>\mathrm{<span\; class="notranslate">\; W</span>}<span\; class="notranslate">\; |</span>\end{array}\right.<span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 3</span>}<span\; class="notranslate">\; .</span>\mathrm{<span\; class="notranslate">\; 5</span>}<span\; class="notranslate">\; )</span>$

4 Subtree-based Multicast Sharing Multilayer Protection Algorithm

4.1 Protection resource sharing strategy

According to different sharing granularities, protection resource sharing strategies can be divided into subtree protection resource sharing strategies, optical path protection resource sharing strategies, and wavelength link protection resource sharing strategies.

4.1.1 Subtree Protection Resource Sharing Strategy

If two protection multicast forests use the same subtree, and their working multicast forests are separated by physical links, they can share protection bandwidth on that subtree.

为工作多播树经过物理链路e，保护多播树经过t的请求集合，对于任意e∈A₁，

b_r为务r的请求带宽。Let R _t be the request set of the protected multicast tree passing through the subtree t, _Er be the set of physical links passed by the working multicast tree requesting r, and the physical link passed by the working multicast tree of the protected multicast tree passing t collection of roads

For the working multicast tree through the physical link e, the set of requests for the protection multicast tree through t, for any e∈A ₁ ,

b _r is the requested bandwidth of service r.

Whenever a protection multicast forest is established for a new request, and the protection multicast forest passes through t, first list the light paths and subtrees passed by its working multicast forest, and then list the subtrees and light paths through physical links, remove duplicate physical links, keep only one physical link, and form an array A ₂ .

那么将e添加到A₁中，同时将令

为新业务的请求带宽；如果e∈A₁，令

该子树需要新分配的保护资源带宽

如果l上没有足够的空闲带宽，那么t不可用。For any e∈A ₂ , if

then add e to A ₁ and at the same time make

is the requested bandwidth of the new service; if e∈A ₁ , let

This subtree requires newly allocated protection resource bandwidth

If there is not enough free bandwidth on l, then t is not available.

4.1.2 Optical path protection resource sharing strategy

If two protection multicast forests use the same optical path, and their working multicast forests are separated by physical links, they can share protection bandwidth on this optical path.

为工作多播树经过物理链路e，保护多播树经过l的请求集合；对于任意e∈A₁，b_r为业务r的请求带宽。Let R _l be the request set of the protection multicast tree passing through optical path l; E _r be the collection of physical links passing through the working multicast tree of request r; the physical link passing through the working multicast tree of the protection multicast tree passing through l collection of

The set of requests for the working multicast tree to go through the physical link e and the protection multicast tree to go through l; for any e∈A ₁ , b _r is the requested bandwidth of service r.

Whenever a protection multicast forest is established for a new request, and the protection multicast forest passes through l, first list the light paths and subtrees passed by its working multicast forest, and then list the subtrees and light paths through physical link. There may be duplicates among these physical links. The duplicated physical links are removed, and only one physical link is reserved to form the array A ₂ .

那么将e添加到A₁中，同时将令

为新业务的请求带宽；如果e∈A₁，令

该光路需要新分配分配的保护资源带宽如果l上没有足够的空闲带宽，那么l不可用。For any e∈A ₂ , if

then add e to A ₁ and at the same time make

is the requested bandwidth of the new service; if e∈A ₁ , let

This lightpath requires a new allocation of allocated protection resource bandwidth If there is not enough free bandwidth on l, then l is unavailable.

4.1.3 Wavelength link protection resource sharing strategy

Wavelength link protection resource sharing means that during multicast shared segment protection, if two protection segments pass through the same wavelength link and their corresponding working segments are separated by physical links, they can share the wavelength link .

Each wavelength link l used by the protection section records the physical links that all the protection sections pass through and the requested working section passes through l, which is recorded as an array A ₃ . When looking for a protection segment for a working segment, if none of the physical links passed by the working segment is in the array _A3 corresponding to the wavelength link 1, then its protection segment can share the wavelength link.

4.2 Cost

When establishing a working multicast forest, since it does not involve the sharing of protection resources, the settings of its subtrees and optical path costs are the same as those of dedicated protection. However, when establishing a protection multicast forest, the settings of subtrees, optical paths and wavelength link costs are different from those when establishing a working multicast forest.

4.2.1 Subtree cost

In the case of protection resource sharing, when a protection multicast forest is established for service requests, the factors affecting the cost of a subtree are not only the load of the subtree, but also the amount of newly allocated protection bandwidth that the protection multicast forest needs to pass through the subtree.

Let b _t , b _w , b _p , b _new denote the total bandwidth, working bandwidth, protection bandwidth of the subtree and the newly allocated protection bandwidth if the protection multicast forest passes through the subtree, then the cost of the subtree for

${\mathrm{<span\; class="notranslate">\; W</span>}}_{\mathrm{<span\; class="notranslate">\; st</span>}}<span\; class="notranslate">\; =</span>\left\{\begin{array}{cc}<span\; class="notranslate">\; \&infin;</span>& {\mathrm{<span\; class="notranslate">\; r</span>}}_{\mathrm{<span\; class="notranslate">\; the\; groo</span>}\mathrm{<span\; class="notranslate">\; min</span>}\mathrm{<span\; class="notranslate">\; g</span>}}<span\; class="notranslate">\; <</span>{\mathrm{<span\; class="notranslate">\; Q</span>}}_{\mathrm{<span\; class="notranslate">\; the\; groo</span>}\mathrm{<span\; class="notranslate">\; min</span>}\mathrm{<span\; class="notranslate">\; g</span>}}\\ <span\; class="notranslate">\; \&infin;</span>& {\mathrm{<span\; class="notranslate">\; b</span>}}_{\mathrm{<span\; class="notranslate">\; t</span>}}<span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; b</span>}}_{\mathrm{<span\; class="notranslate">\; w</span>}}<span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; b</span>}}_{\mathrm{<span\; class="notranslate">\; p</span>}}<span\; class="notranslate">\; <</span>{\mathrm{<span\; class="notranslate">\; b</span>}}_{\mathrm{<span\; class="notranslate">\; new</span>}}\\ \frac{{\mathrm{<span\; class="notranslate">\; b</span>}}_{\mathrm{<span\; class="notranslate">\; w</span>}}<span\; class="notranslate">\; +</span>{\mathrm{<span\; class="notranslate">\; b</span>}}_{\mathrm{<span\; class="notranslate">\; p</span>}}}{{\mathrm{<span\; class="notranslate">\; b</span>}}_{\mathrm{<span\; class="notranslate">\; t</span>}}}& {\mathrm{<span\; class="notranslate">\; b</span>}}_{\mathrm{<span\; class="notranslate">\; t</span>}}<span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; b</span>}}_{\mathrm{<span\; class="notranslate">\; w</span>}}<span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; b</span>}}_{\mathrm{<span\; class="notranslate">\; p</span>}}<span\; class="notranslate">\; \&Greater\; Equal;</span>{\mathrm{<span\; class="notranslate">\; b</span>}}_{\mathrm{<span\; class="notranslate">\; new</span>}}\end{array}\right.<span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 4.1</span>}<span\; class="notranslate">\; )</span>$

4.2.2 Optical path cost

Let b _t , b _w , b _p , b _new denote the total bandwidth, working bandwidth, protection bandwidth of the optical path and the newly allocated protection bandwidth if the protection multicast forest passes through the optical path, then the link cost of the optical path is

${\mathrm{<span\; class="notranslate">\; W</span>}}_{\mathrm{<span\; class="notranslate">\; ll</span>}}<span\; class="notranslate">\; =</span>\left\{\begin{array}{cc}<span\; class="notranslate">\; \&infin;</span>& {\mathrm{<span\; class="notranslate">\; b</span>}}_{\mathrm{<span\; class="notranslate">\; t</span>}}<span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; b</span>}}_{\mathrm{<span\; class="notranslate">\; w</span>}}<span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; b</span>}}_{\mathrm{<span\; class="notranslate">\; p</span>}}<span\; class="notranslate">\; <</span>{\mathrm{<span\; class="notranslate">\; b</span>}}_{\mathrm{<span\; class="notranslate">\; new</span>}}\\ <span\; class="notranslate">\; (</span>\frac{{\mathrm{<span\; class="notranslate">\; b</span>}}_{\mathrm{<span\; class="notranslate">\; new</span>}}}{{\mathrm{<span\; class="notranslate">\; b</span>}}_{\mathrm{<span\; class="notranslate">\; t</span>}}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; +</span>\frac{{\mathrm{<span\; class="notranslate">\; b</span>}}_{\mathrm{<span\; class="notranslate">\; w</span>}}<span\; class="notranslate">\; +</span>{\mathrm{<span\; class="notranslate">\; b</span>}}_{\mathrm{<span\; class="notranslate">\; p</span>}}}{{\mathrm{<span\; class="notranslate">\; b</span>}}_{\mathrm{<span\; class="notranslate">\; t</span>}}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; \&times;</span>{\mathrm{<span\; class="notranslate">\; \&alpha;</span>}}_{\mathrm{<span\; class="notranslate">\; ll</span>}}& {\mathrm{<span\; class="notranslate">\; b</span>}}_{\mathrm{<span\; class="notranslate">\; t</span>}}<span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; b</span>}}_{\mathrm{<span\; class="notranslate">\; w</span>}}<span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; b</span>}}_{\mathrm{<span\; class="notranslate">\; p</span>}}<span\; class="notranslate">\; \&Greater\; Equal;</span>{\mathrm{<span\; class="notranslate">\; b</span>}}_{\mathrm{<span\; class="notranslate">\; new</span>}}\end{array}\right.<span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 4.2</span>}<span\; class="notranslate">\; )</span>$

4.2.3 Wavelength link cost

When using the MSSP algorithm to calculate WDM layer protection, if the wavelength link is not used or the usage status is "used for protection" and the wavelength can be shared, the link cost of the wavelength link is set according to formula 3.5, otherwise it is set to ∞ .

4.3 Shared segmentation method

Known network physical topology G _p (V, L, W) and multicast routing request r(v _s , D), where v _s , D∈V, v _s is the source node, D is the destination node set, and the request is established An ensemble of light trees satisfying the multiple constraints in Section 2.1.

As mentioned in Section 2.1, for network nodes with both wavelength conversion and splitting capabilities, the method of splitting first and then converting wavelengths is used, which is very different from the method of splitting after wavelength conversion, which is reflected in the multi-layer auxiliary diagram. As shown in Figure 11 and Figure 12. The solid line with arrows in the figure indicates the direction of service data flow on the optical tree, and the solid line without arrows indicates the link. The input wavelength shown in Figure 11 is λ ₂ , and the two wavelengths after splitting are converted to λ ₁ and λ ₃ respectively; The input wavelength shown in 12 is also λ ₂ , which becomes λ ₃ after wavelength conversion, and then splits, and the two wavelengths after splitting are both λ ₃ .

(1) The amount of light split at the wavelength node

The invention defines the number of splitting times of a wavelength node on the optical tree as the splitting amount of the wavelength node. When a wavelength node is not a destination node, the split amount of the wavelength node refers to the number of its child nodes; when the wavelength node is a destination node, as the destination node needs a copy of the service data flow, its The amount of light is the number of its child nodes plus one.

(2) MC wavelength node

The MC wavelength node refers to a wavelength node on the optical tree whose light splitting amount is smaller than the maximum number of splitting lights of the node and which is not reached through the wavelength conversion link.

的分光量为3，而不是2。图中由于

的分光量为3小于其最大分光数4，所以其是MC波长节点。如果节点v₁同时还是多播业务的目的节点，那么的分光量变为4，不可再分光，不再是MC波长节点。图中

由于其前一跳是波长转换链路，所以其不是MC波长节点。Figure 13 shows part of the multi-layer auxiliary diagram, in which the solid line with arrows indicates the direction of service flow on the multicast tree, v ₁ has wavelength conversion capability, and the maximum number of splits is 4. In the figure, because in actual operation, the optical signal is split three times at v ₁ , respectively to v ₂ , v ₃ , v ₄ , and then the optical signals to v ₂ and v ₄ are converted to λ ₁ in wavelength, so

The split amount is 3 instead of 2. In the figure due to

The splitting amount of 3 is less than its maximum splitting number of 4, so it is the MC wavelength node. If node _v1 is also the destination node of the multicast service at the same time, then The amount of splitting becomes 4, no further splitting is possible, and it is no longer an MC wavelength node. in the picture

Since its previous hop is a wavelength conversion link, it is not an MC wavelength node.

图15中

图16中

图17中

图18中

等都被称为工作段。In the present invention, the MC wavelength node whose output degree is not less than 2 is called a segmentation point, and the part between two segmentation points and between the segmentation node and the leaf node is called a working segment. Figure 14 to Figure 18 provide several working segments kind of form. Figure 14

Figure 15

Figure 16

Figure 17

Figure 18

etc. are called working segments.

其前一跳是波长转换链路，所以其不是MC波长节点，所以

不是段。In Figure 18, since all nodes adopt the strategy of splitting light first and then converting wavelength, node v ₁ needs to split light first and then convert wavelength to λ ₁ , because

Its previous hop is a wavelength conversion link, so it is not an MC wavelength node, so

Not a segment.

When performing protection, it is required that the protection section and the optical tree be separated by physical links. From the point of view of protection, an optical path can be provided for the working section from the logical node corresponding to the wavelength node at the head of the section to the logical node corresponding to the wavelength node at the end of the section. In this way, an optical transmitter and an optical receiver need to be consumed at the segment head node and the segment tail node respectively. Since the optical transmitter is used at the head of the segment, it has the ability to receive grooming services, and the source node of the optical tree is no longer the only node capable of receiving grooming services, which will lead to confusion in grooming and optical tree bandwidth allocation. Therefore, the present invention does not perform optical path protection on the segment.

Since a light split is released when the working segment is faulty, it is not necessary to consider the splitting degree of the first wavelength node of the segment when creating the protection segment.

4.4 Self-Sharing Protection

The self-sharing protection means that for a certain working segment, the working segment on the optical tree can be used for protection. For example, in Figure 19, for the segment v ₁ →v ₂ →v ₃ , you can create a new path from v ₅ to v ₃ , and then use v ₁ →v ₄ →v ₅ →v ₃ as v ₁ →v ₂ →v ₃ protection section, the present invention calls v ₁ →v ₄ →v ₅ the front protection section, and v ₅ →v ₃ the rear protection section. Similarly, v ₁ →v ₂ →v ₃ →v ₅ can be used as the protection segment of v ₁ →v ₄ →v ₅ . The wavelength channel and optical tree connecting the two end nodes to be found are separated by physical links.

After the self-sharing protection requirement, the segment tail wavelength node of the protection segment is the MC node. For example, in Figure 19, if the spectrometry of v ₅ is 2, then the segment v ₁ → v ₂ → v ₃ cannot be used to provide protection for other segments.

Two, the unicast sharing multi-layer protection method based on load balancing in the optical network of the present invention comprises the following steps:

Step (1), establish a working multicast forest

Establishing a working multicast forest is actually the process of traffic grooming for multicast requests. The multicast traffic grooming algorithm is used to build a working multicast forest for requests; if the multicast traffic grooming algorithm fails to groom, the algorithm ends;

Step (2), establish protection multicast forest

A protection multicast forest requires physical link separation from a working multicast forest.

Step (2.1) Physical Link Separation of Optical Paths

Set the wavelength link on each physical link that the optical path passes through, and the cost of the optical path and subtree passing through these wavelength links is set to ∞;

Step (2.2) Physical Link Separation of Subtrees

When establishing a working multicast forest for a request, when a certain subtree is used for grooming, if the grooming availability rate is not 100%, then the services carried on some links on the subtree are irrelevant to the request, that is, when these links When a fault occurs on the subtree, it does not affect the operation of the service; therefore, when setting up the separation of the physical links of the subtree, it is not simply to separate the wavelength links on the physical links that the subtree passes through, and the optical paths passing through these wavelength links. The cost of and subtree is set to ∞; the steps to set physical link separation are as follows:

Step (2.2.1) sets the cost of light tree and light path according to formula 4.1, 4.2, searches for the destination node that dredges with this subtree;

Step (2.2.2) trace back the optical tree along the reverse direction of the service data flow from the destination node, and record the wavelength links that guide the service data flow of these destination nodes;

Step (2.2.3) obtains its corresponding physical link according to these wavelength links, the wavelength link on these physical links is set, the cost of the optical paths and subtrees passing through these wavelength links is set to ∞;

For example, in Figure 20, the set of destination nodes of the light tree {v ₄ , v ₅ , v ₆ , v ₇ , v ₈ }, assuming that the destination nodes v ₆ , v ₇ and v ₈ in the request use the light tree for grooming, Then when the physical links of v ₁ → v ₂ , v ₂ → v ₃ and v ₃ → v ₄ fail, it will not affect the normal transmission of services, so when setting the physical link separation of this subtree, only need It is sufficient to set the physical links of the four edges v ₁ →v ₈ , v ₁ →v ₃ , v ₃ →v ₆ and v ₃ →v ₇ to be separated.

With this method of setting subtree physical link separation, the number of wavelength links, optical paths and subtrees that cannot be used due to physical link separation can be effectively reduced when creating a protected multicast forest, reducing the probability of grooming failure;

After successful grooming with the multicast traffic grooming algorithm, when allocating bandwidth resources for the protection of the multicast forest, the subtrees and the bandwidth resources on the optical path should be updated respectively according to the descriptions in Section 4.1.1 and 4.1.2, and the working multicast forest The set of passed physical links is updated to the array _A1 of subtrees and subpaths used in the protection of the multicast forest.

After the physical link separation from the working tree is set by the above method, use the SMTG algorithm to establish a protection multicast forest for the request. If the creation of the protection multicast forest fails, then release the resources occupied by the working multicast forest. The algorithm fails and ends.

Step (3), protecting the WDM layer

表示可用于提供自共享保护的MC波长节点集合：Let T represent the working tree, S represent the working segment being processed, v _head and v _tail represent the wavelength nodes at the beginning and end of the working segment respectively, and V _mc represent the MC wavelength node on T (the amount of light splitting on the optical tree is less than the maximum value of the node non-wavelength nodes reached by wavelength conversion links) set of split numbers,

Indicates the set of MC wavelength nodes that can be used to provide self-shared protection:

Specific steps are as follows:

Step (3.1), initialization.

The link costs of all admission links and logical links are set to ∞, and the link costs of all wavelengths on the physical links passed by the working tree are set to ∞;

Step (3.2), breadth-first traversal of the light tree to obtain all segmentation points and working segments. According to the traversal order, provide protection for each working segment S, the method is as follows:

将v_head添加到

中，即

计算T上v_head的所有下游MC波长节点，将它们从

中删除；Step (3.2.1)

Add the v _head to

in, namely

Compute all downstream MC wavelength nodes of v _head on T, dividing them from

delete in

Step (3.2.2) calculates the set of physical links that the working section passes through, and sets the wavelength link cost on the physical links that the remaining working trees do not pass through as described in section 4.2.2;

中所有MC波长节点到v_tail的代价最小的路径，然后从

个代价最小路径中再选出代价最小的路径；如果找到代价最小的路径，将该路径记作P_min，对应的

中的节点为v_exp and；将P_min添加到v_exp and的保护段集合中，P_min经过的波长链路的使用状态标记为“被用于保护”；将保护段经过的波长链路的使用状态标记为“被用于保护”后，将工作段经过的物理链路添加到各波长链路的数组A₃中，如果未找到，转步骤(3.3)；Step (3.2.3) calculates respectively

The least-cost path from all MC wavelength nodes to v _tail in , and then from

Select the path with the minimum cost from the paths with the minimum cost; if the path with the minimum cost is found, record this path as P _min , and the corresponding

The node in is v _{exp and} ; P _min is added to the protection section set of v _{exp and} , and the use state of the wavelength link that P _min passes through is marked as "used for protection"; the wavelength link that the protection section passes through After the use state is marked as "being used for protection", the physical link that the working section passes through is added to the array A ₃ of each wavelength link, if not found, go to step (3.3);

If all working segments are successfully protected, the algorithm ends successfully; otherwise, go to step (3.3);

Step (3.3), delete all protection sections on the subtree, for the wavelength link on each protection section, delete the physical link that the working section passes through from A ₃ , if A ₃ =Φ after deletion, the wavelength link The use state of the road is marked as "unused", otherwise the use state is not changed, the protection fails, and the algorithm ends.

Step (4), business departure

When the business leaves, it is necessary to release the resources occupied by the working multicast forest and the protection multicast forest. The release method of the working multicast forest resources is as follows:

Step (4.1), successively releasing the bandwidth occupied by each optical path of the working multicast forest and the protection multicast forest;

的光路，删除其保护路，将其标志为“WDM层未保护”状态，设置保护路经过的各波长链路的使用情况为“未使用”；Step (4.2), for WDM layer protection is provided but its workload is below the threshold

For the optical path, delete its protection path, mark it as "WDM layer unprotected" state, and set the usage status of each wavelength link that the protection path passes through to "unused";

Step (4.3), for the optical path whose used bandwidth is 0, delete this optical path: set the usage of each wavelength link that the optical path passes through as "unused"; add one to the number of optical transmitters at the source node of the optical path; Increment the number of receivers by one;

Step (4.4), successively releasing the occupied bandwidth on each optical tree of the work multicast forest and the protection multicast forest;

的光树，删除该光树的所有保护段，将其标志为“WDM层未保护”状态，设置各保护段经过的各波长链路的使用情况为“未使用”；Step (4.5), after the bandwidth is released, for the WDM layer protection is provided but its workload is lower than the threshold

The optical tree, delete all the protection sections of the optical tree, mark it as "WDM layer unprotected" state, set the usage of each wavelength link passed by each protection section as "unused";

Step (4.6), for the optical tree whose used bandwidth is 0, delete the optical tree: set the use of each wavelength link that the optical tree passes to be "unused"; add one to the number of optical transmitters at the source node of the optical path; Add one to the number of optical receivers at the destination node;

The release methods for protecting multicast forest resources are as follows:

Each subtree passed by the protection multicast forest is checked in turn, and the bandwidth corresponding to the physical link passed by the service working multicast forest in the array _A1 of the subtree is subtracted from the requested bandwidth of the service. If the bandwidth corresponding to a physical link in _A1 is 0, delete the physical link from _A1 , and reset the value of the protection bandwidth to the maximum value of the corresponding bandwidth of each physical link in _A1 ;

删除子树上的所有保护段；对于各保护段上的波长链路，将工作段经过的物理链路从A₃中删除；如果删除后A₃＝Φ，将该波长链路的使用状态标记为“未使用”，否则不改变使用状态。If the load of a subtree that provides WDM layer protection is below the threshold

Delete all protection segments on the subtree; for wavelength links on each protection segment, delete the physical link that the working segment passes through from A ₃ ; if A ₃ = Φ after deletion, mark the use state of the wavelength link It is "unused", otherwise the usage status will not be changed.

Claims (1)

1. a multi-layer protection method is shared in the multicast based on subtree in WDM optical-fiber network, it is characterized in that: comprise the steps:

Step (1), set up work multicast forest

Adopt multicast service amount congestion relief algorithm for asking to set up work multicast forest; If multicast service amount congestion relief algorithm is dredged unsuccessfully, algorithm finishes so;

Step (2), foundation protection multicast forest

The physical link of step (2.1), light path is separated

Wavelength span on each physical link of light path process is set, through the light path of these wavelength spans and the cost of subtree, is set to ∞;

The physical link of step (2.2), subtree is separated

Step (2.2.1), by formula $W_{\mathrm{st}}=\left\{\begin{array}{cc}\&infin;& r_{\mathrm{groo}\min g}<Q_{\mathrm{groo}\min g}\\ \&infin;& b_t-b_w-b_p<b_{\mathrm{new}}\\ \frac{b_w+b_p}{b_t}& b_t-b_w-b_p\&GreaterEqual;b_{\mathrm{new}}\end{array}\right.$ The cost W of light tree is set _st,

By formula $W_{\mathrm{ll}}=\left\{\begin{array}{cc}\&infin;& b_t-b_w-b_p<b_{\mathrm{new}}\\ \left(\frac{b_{\mathrm{new}}}{b_t}\right)(1+\frac{b_w+b_p}{b_t})\&times;{\mathrm{\&alpha;}}_{\mathrm{ll}}& b_t-b_w-b_p\&GreaterEqual;b_{\mathrm{new}}\end{array}\right.$ The cost W of light path is set _ll, search the destination node of dredging by this subtree;

Wherein: b _t, b _w, b _p, b _newif represent respectively, total bandwidth, bandwidth of operation, protection bandwidth and the protection multicast forest of this light path are through the newly assigned protection bandwidth of these light path needs number, α _llfor the grade factor of logical links, r _groomingfor light tree, dredge node availability factor, Q _groomingfor what arrange, dredge node availability factor threshold value;

Step (2.2.2), from destination node, start to recall light tree along the opposite direction of business data flow, the wavelength span of these destination node business data flow processes dredged in record;

Step (2.2.3), according to these wavelength spans, obtain its corresponding physical link, the wavelength span on these physical links is set, through the light path of these wavelength spans and the cost of subtree, be set to ∞;

With said method be provided with physical link with the tree of working separated after, utilize multicast service amount congestion relief algorithm to set up protection multicast forest for request, if protection multicast forest creates unsuccessfully, discharge so the resource taking in work multicast forest, algorithm is failed, end;

Step (3), protection WDM layer

Make T represent work tree, S represents the active section of processing, v _headand v _tailthe section head and the section coda wave meropodium point that represent respectively active section, V _mcrepresent the MC wavelength node set on T, described MC wavelength node is the non-wavelength node arriving by wavelength transfer link that the upper minute light quantity of light tree is less than the maximum light splitting number of node; Described wavelength node is by each node v _i∈ V, i=1,2 ..., | V|, copies | W| time, is labeled as respectively

wherein, V represents the node set of network, | V| represents the nodes of network;

represent to can be used for providing from the MC of share protect wavelength node set:

Concrete steps are as follows:

Step (3.1), initialization

The link cost of all receiving links, logical links is set to ∞, and on the physical link of work tree process, all wavelength span costs are set to ∞;

Step (3.2), breadth First traversal light tree, obtain all waypoints and active section, and by traversal order, for each active section S provides protection, method is as follows:

Step (3.2.1),

by v _headadd to

in,

calculate the upper v of T _headall downstreams MC wavelength node, by they from

middle deletion;

The physical link set of step (3.2.2), evaluation work section process:

According to formula $W_{\mathrm{ll}}=\left\{\begin{array}{cc}\&infin;& b_t-b_w-b_p<b_{\mathrm{new}}\\ \left(\frac{b_{\mathrm{new}}}{b_t}\right)(1+\frac{b_w+b_p}{b_t})\&times;{\mathrm{\&alpha;}}_{\mathrm{ll}}& b_t-b_w-b_p\&GreaterEqual;b_{\mathrm{new}}\end{array}\right.$ Remaining work is set and sets the wavelength span cost on the physical link of process not;

B wherein _t, b _w, b _p, b _newif represent respectively total bandwidth, bandwidth of operation, protection bandwidth and the newly assigned protection bandwidth of protection multicast forest these light path needs of the process number of this light path:

α _llit is the grade factor of logical links;

Step (3.2.3), calculating respectively in all MC wavelength nodes to v _tailthe path of Least-cost, then from

in individual Least-cost path, select again the path of Least-cost; If find the ，Jiang Gai path, path of Least-cost to be denoted as P _min, corresponding

in node be v _expand; By P _minadd v to _expandthe set of protection section in, P _minthe use status indication of the wavelength span of process is " being used to protection "; By protection section through the use status indication of wavelength span for " being used to protection " after, the physical link of active section process is added to the array A of each wavelength span ₃in, if do not found, go to step (3.3);

If all working section is all protected successfully, algorithm successfully finishes; Otherwise, go to step (3.3);

Step (3.3), delete all protections sections in subtree, for the wavelength span in each protection section, by the physical link of active section process from A ₃middle deletion, if A after deleting ₃=Φ, is " not using " by the use status indication of this wavelength span, otherwise does not change use state, protect unsuccessfully, algorithm finishes;

Step (4), business are left away

When business is left away, need to discharge the resource that work multicast forest and protection multicast forest take, the method for releasing of the multicast forest reserves of wherein working is as follows:

Step (4.1), discharge the bandwidth taking in work multicast forest and each light path of protection multicast forest successively;

Step (4.2), for WDM layer protection is provided but its operating load lower than threshold value

light path, delete its protection road, be masked as " WDM layer is not protected " state, the service condition that each wavelength span of protection road process is set is " not using ";

Step (4.3), for the light path that dedicated bandwidth is 0, delete this light path: the service condition that each wavelength span of light path process is set is " do not use "; Light path source node place optical transmitter number adds one; Destination node place optical receiver number adds one;

Step (4.4), discharge the bandwidth taking on each light tree of work multicast forest and protection multicast forest successively;

Step (4.5), discharged after bandwidth, for the protection of WDM layer is provided but its operating load lower than threshold value

light tree, delete all protections sections of this light tree, be masked as " WDM layer is not protected " state, service condition that each wavelength span of each protection section process is set is " use ";

Step (4.6), for dedicated bandwidth is 0 light tree, delete this light tree: the service condition that each wavelength span of light tree process is set is " not using "; Light path source node place optical transmitter number adds one; All destination nodes place optical receiver number adds one;

The method for releasing of the protection multicast forest reserves is as follows:

Each subtree of check protection multicast forest process successively, by the array A of this subtree ₁in the bandwidth corresponding to physical link of this vocational work multicast forest process deduct the bandwidth on demand of this business; If A ₁in bandwidth corresponding to certain physical link be 0, from A ₁this physical link of middle deletion, is re-set as A by the value of protection bandwidth ₁in the maximum of the corresponding bandwidth of each physical link;

If the load of certain subtree that the protection of WDM layer be provided is lower than threshold value

delete all protection sections in subtree; For the wavelength span in each protection section, by the physical link of active section process from A ₃middle deletion; If A after deleting ₃=Φ, is " not using " by the use status indication of this wavelength span, otherwise does not change use state.

Images