CN105634941A

CN105634941A - Cross-domain path calculation method and device

Info

Publication number: CN105634941A
Application number: CN201410625836.0A
Authority: CN
Inventors: 盛伟; 卢刚; 李晓建
Original assignee: ZTE Corp
Current assignee: ZTE Corp
Priority date: 2014-11-07
Filing date: 2014-11-07
Publication date: 2016-06-01
Also published as: WO2016070670A1

Abstract

The present invention provides a cross-domain path calculation method and device. The method comprises the steps of using a father path calculation element (PCE) to calculate an optimal domain sequence according to an inter-domain route strategy; in the calculated domain sequence, using the father PCE to schedule child PCEs to calculate all intra-domain path routes parallelly; using the father PCE to select an optimal cross-domain path according to the intra-domain paths calculated by the son PCEs successfully; using the father PCE to require the child PCEs to parallelly calculate the intra-domain path segment reserved resources of the selected cross-domain path; after all child PCEs reserve the path resources successfully, using the father PCE to return the selected cross-domain path as a cross-domain path calculation result. According to the present invention, the calculation efficiency is improved further while the cross-domain path calculation success rate is guaranteed.

Description

The computational methods in a kind of cross-domain path and device

Technical field

The present invention relates to the path computation technique of the communications field, specifically, be computational methods and the device in a kind of cross-domain path.

Background technology

In MPLS-TE (multiprotocol label switching-traffic engineering)/GMPLS (Generalized Multiprotocol Label exchange) network application, needing quickly to calculate the end-to-end label switched path TE-LSP of the optimum based on traffic engineering (traffic engineering-label switched path), the purpose of network is quickly set up, recovers and optimized to the business that reaches. The path-calculating element based on RFC4655 agreement (PCE) framework that IETF (Internet Engineering Task group) tissue proposes achieves this function, PCE managing network flow data, has end-to-end TE-LSP path computation capabilities.

The factors such as safety Network Based, performance, management, MPLS/GMPLS network will belong to common address range of management or follow the set of node of same paths computation rule and be divided into a territory (DOMAIN), multiple territories that large scale network is connected by domain-to-domain link form, each territory has at least one PCE, manage in this territory and data on flows between territory, and calculate end-to-end TE-LSP path. Fig. 1 is 4 territory MPLS-TE/GMPLS network topological diagrams, node representative domain boundary node in annular broken (includes node N11, N12, N13, the N14 in territory 1, node N21, N22, N23, N24, the N25 in territory 2, node N31, N32, N33, the N34 in territory 3, node N41, N42, N43, the N44 in territory 4), PCE1, PCE2, PCE3, PCE4 are a territory PCE server in territory 1, territory 2, territory 3, territory 4 respectively, it is all connected to main PCE, safeguards data on flows storehouse and be responsible for the path computing of this domain node request.

In multiple-domain network, in the territory of each territory PCE management, data on flows maintains secrecy mutually, the sub-PCE of single domain cannot obtain the territory internal information in other territory, path in the territory in other territory can not be calculated, therefore, any single domain PCE cannot complete independently cross-domain end-to-end TE-LSP path computing, it is necessary to multiple domain PCE cooperates, route segment in this territory, territory calculated by every territory PCE, is spliced into complete cross-domain path. Between PCE, PCEP (path computation element communication protocol) message according to RFC5440 protocol definition interacts, and has the cross-domain Path Method of PCE Collaboration computing more than three kinds at present.

Method 1, based on RFC5152 agreement many PCE by territory calculate cross-domain Path Method.

First territory PCE receives the cross-domain path request of calculating, calculate inter-domain path route and return source node, inter-domain routing node sets up cross-domain path according to RSVP-TE (RSVP-traffic engineering) agreement, PATH signaling is transmitted along inter-domain routing, path reservation resource between computational fields, source node and territory enter boundary node and receive between territory after PATH signaling, this territory PCE is asked to calculate path route in territory, PATH signaling is transmitted along intra-area routes, path reservation resource in computational fields, after destination node receives PATH signaling, along between territory, intra-area routes reverse return RESV signaling, path resources is distributed at each node, complete cross-domain path to set up.

As in figure 2 it is shown, first node SRC receives the cross-domain path request setting up first node SRC to destination node DST, calculating cross-domain path to PCE1 request, PCE1 is between territory in topology, and calculating optimum inter-domain path route according to intra domain routing policy is: SRC, node BN_EX1, node BN_EN2, node BN_EX2, node BN_EN3, DST, result of calculation returns SRC, message stream (1), transmits PATH signaling, SRC along inter-domain routing, BN_EN2, BN_EN3 receives between territory after PATH signaling, asks PCE1 respectively, PCE2, PCE3 calculates territory 1, territory 2, in the territory in territory 3, path route, is shown in message stream (2), (5), (8), in territory PATH signaling along path reservation territory 1 in territory, territory 2, path resources in territory 3, is shown in message stream (3), (6), (9), after destination node DST receives PATH message, along cross-domain path route reverse return RESV signaling, path resources in territory between distribution territory, see message stream (10), first node SRC receives RESV signaling, completes cross-domain path and sets up.

This method path computing is included in path and sets up in process, it is divided in territory by the cross-domain path that first territory PCE calculates route segment, along inter-domain path PATH signaling direction, routeing by path in the PCE computational fields of territory, in territory, each node of path P ATH signaling calculates reserved path resource. This method is once only capable of calculating a cross-domain path, though calculating time less, it is low to be calculated as power, and in arbitrary territory, path computing failure all can cause the failure of cross-domain path computing, failure backtracking is reruned and is realized complexity, and the cross-domain path not necessarily network optimum calculated.

Method two, reverse recursive path computation (BRPC) method based on RFC5441 agreement.

First territory PCE receives the cross-domain path request of calculating, optimum territory sequence is calculated according to intra domain routing policy, start downstream territory PCE from first territory PCE and send BRPC path computing request message, until tail territory PCE receives BRPC path computing request message, tail territory PCE calculates the shortest path tree (VSPT) entering boundary node from tail territory to destination node, territory VSPT is returned territory, upstream PCE, territory, upstream PCE calculates this territory and enters the boundary node VSPT through downstream domain VSPT arrival destination node, continue VSPT result of calculation is returned territory, upstream PCE, only receive downstream domain VSPT to first territory PCE, calculate the source node shortest path to destination node as cross-domain path computation result.

As shown in Figure 3, PCE1 receives the cross-domain path request of computing node N11 to node N32, calculating optimum sequence territory, territory 1, territory 2, territory 3, PCE1 to PCE2 transmission BRPC computation requests, PCE2 sends BRPC computation requests to PCE3, PCE3 calculates VSPT (territory 3), return to PCE2, PCE2 and calculate VSPT (territory 2), return to PCE1, PCE1 calculates VSPT (territory 1), the i.e. cross-domain path of the optimum of N11 to N32.

This method is in specified domain sequence, and traversal calculates whole cross-domain paths, selects optimum cross-domain route result, is calculated as power higher, but computational efficiency is poor, it is necessary to each territory PCE order calculates route segment in whole territory.

Method three, the cross-domain path calculation method of grade PCE framework based on RFC6805 agreement.

Path-calculating element is divided into father and son's PCE two-stage, and sub-PCE safeguards domain topology information, floods topology information between territory to father PCE, and father PCE safeguards topology information between territory, decreases topology information flooding scale between territory, improves topological convergence and path computing speed. The cross-domain path of father and son's PCE Collaboration computing, father PCE calculates whole inter-domain paths route in cross-domain path between territory in topology, going out route segment in whole territory according to inter-domain routing scheduling sublayer PCE parallel computation, father PCE, from route segment in the successful territory of calculating, splices and selects optimum cross-domain path.

As shown in Figure 4, PCE1, PCE2, PCE3, PCE4 is four subdomain PCE respectively, after father PCE receives the cross-domain path computing request of N11 to the N32 from PCE1, between territory in topology, calculate whole 4 cross-domain path inter-domain routings: one is N11, N13, N25, N22, N31, N32, two is N11, N13, N25, N24, N33, N32, three is N11, N13, N41, N43, N33, N32, four is N11, N14, N44, N43, N33, N32, father PCE asks sub-PCE to calculate route segment in whole territories: N11 to N13 in PCE1 computational fields 1, path in two territories of N11 to N14, N25 to N22 in PCE2 computational fields 2, path in two territories of N25 to N24, N31 to N32 in PCE3 computational fields 3, path in two territories of N33 to N32, N41 to N43 in PCE4 computational fields 4, path in two territories of N44 to N43, path computation result in territory is returned father PCE by whole sub-PCE, father PCE selects to calculate successful optimum cross-domain path.

This method is in network-wide basis, route segment in the whole territory of sub-PCE parallel computation, each territory, father PCE splices and selects optimum cross-domain path, computational efficiency is higher, but, this method is only applicable between simple field topological network, when when between territory, topology is complicated, in calculative territory, route segment increases, and computational efficiency reduces. In order to improve computational efficiency, by restricting the father PCE inter-domain path number of routes once calculated, reduce number of paths in the sub-PCE territory calculated, but be likely to be due to father PCE and do not hit optimum cross-domain path route, reduce and be calculated as power.

Above-mentioned PCE more than three kinds cooperates cross-domain path calculation method, there is bigger conflict being calculated as in power and computational efficiency.

Summary of the invention

The technical problem to be solved in the present invention is to provide a kind of new cross-domain path computing scheme, while ensureing cross-domain path computing success rate, further increases computational efficiency.

In order to solve the problems referred to above, the invention provides the computational methods in a kind of cross-domain path, including:

Father path computing unit PCE calculates optimum territory sequence according to intra domain routing policy;

In calculated described territory sequence, path route in the whole territory of described father's PCE scheduling sublayer PCE parallel computation;

Described father PCE calculates, according to described sub-PCE, the cross-domain path that in successful territory, Path selection is optimum;

The reserved resource of route segment in the territory in the described father PCE request cross-domain path selected by described sub-PCE parallel computation;

After the success of whole sub-PCE reserved path resources, described father PCE returns to selected cross-domain path as cross-domain path computation result.

Alternatively, described method also includes:

When there is the territory that in whole territory, path computing is failed:

Described father PCE is when the intermediate field that this territory is described territory sequence, and arranging this territory is failure domain; When the number in the territory in the tail territory that this territory is described territory sequence and described territory sequence is more than 2, the territory, upstream arranging this territory is failure domain; When the number in the territory in the first territory that this territory is described territory sequence and described territory sequence is more than 2, the downstream domain arranging this territory is failure domain; Described father PCE recalculates the territory sequence of optimum and carries out subsequent operation after getting rid of set described failure domain;

Described father PCE is when only existing two territories in the first territory that this territory is described territory sequence and described territory sequence, or when only existing two territories in the tail territory that this territory is described territory sequence and described territory sequence, returning cross-domain path computation result is unsuccessfully.

Alternatively, described father PCE includes according to the cross-domain path that Path selection in the successful territory of described sub-PCE calculating is optimum:

Described sub-PCE is calculated path in successful territory and associates with abstracting link by described father PCE, and in territory, path metric goal setting becomes abstracting link metric objective, deletes and calculates the abstracting link that in failed territory, path is corresponding;

Described father PCE described abstracting link and domain-to-domain link construct cross-domain path computing topology, according to intra domain routing policy, calculate according to the tactic whole cross-domain paths of described path metric desired value;

Described father PCE selects currently most cross-domain path.

Alternatively, described method also includes:

When selected cross-domain path reservation resource failure, select the reserved resource of route segment in the territory in the cross-domain path selected by sub-PCE parallel computation described in next excellent cross-domain path request according to described path metric desired value.

Alternatively, described in calculated described territory sequence, in the whole territory of father's PCE scheduling sublayer PCE parallel computation, path route includes:

Described father PCE, according to calculated territory sequence order, travels through the domain-to-domain link in every territory and upstream and downstream territory, determines entering boundary node group and going out boundary node group of each subdomain respectively; Creating path computing request in boundary node and the m*n bar territory that goes out between boundary node, m is for entering boundary node number, and n is for going out boundary node number, and first territory enters boundary node group and only comprises source node, and tail territory goes out boundary node group and only comprises destination node;

Described father PCE sends path computing request in described territory to each sub-PCE.

Present invention also offers the calculation element in a kind of cross-domain path, be arranged in father path computing unit PCE; Described device includes:

Territory sequence computing module, for calculating optimum territory sequence according to intra domain routing policy;

Scheduler module, path route in the whole territory of scheduling sublayer PCE parallel computation in calculated described territory sequence;

Select module, for calculating, according to described sub-PCE, the cross-domain path that in successful territory, Path selection is optimum;

Request module, for asking the reserved resource of route segment in the territory in the cross-domain path selected by described sub-PCE parallel computation;

Result returns module, for when, after the success of whole sub-PCE reserved path resources, returning to selected cross-domain path as cross-domain path computation result.

Alternatively, described device also includes:

Failure domain arranges module, and for when there is the territory that in whole territory, path computing is failed, if the intermediate field that this territory is described territory sequence, then arranging this territory is failure domain; If the number in the territory in the tail territory that this territory is described territory sequence and described territory sequence is more than 2, then the territory, upstream arranging this territory is failure domain; If the number in the territory in the first territory that this territory is described territory sequence and described territory sequence is more than 2, then the downstream domain arranging this territory is failure domain; If the first territory that this territory is described territory sequence and described territory sequence only exist two territories, or the tail territory that this territory is described territory sequence and described territory sequence only exist two territories, it indicates that described result returns module, and to return cross-domain path computation result be unsuccessfully;

Failure domain gets rid of module, calculates optimum territory sequence for restarting described territory sequence computing module after getting rid of set described failure domain.

Alternatively, described selection module refers to according to the cross-domain path that Path selection in the successful territory of described sub-PCE calculating is optimum:

Described sub-PCE is calculated path in successful territory and associates with abstracting link by described selection module, and in territory, path metric goal setting becomes abstracting link metric objective, deletes and calculates the abstracting link that in failed territory, path is corresponding; Construct cross-domain path computing topology with described abstracting link and domain-to-domain link, according to intra domain routing policy, calculate according to the tactic whole cross-domain paths of path metric desired value; Select currently most cross-domain path.

Alternatively, described request module is additionally operable to when selected cross-domain path reservation resource failure, selects the reserved resource of route segment in the territory in the cross-domain path selected by sub-PCE parallel computation described in next excellent cross-domain path request according to described path metric desired value.

Alternatively, described scheduler module in calculated described territory sequence in the whole territory of scheduling sublayer PCE parallel computation path route refer to:

Described scheduler module, according to calculated territory sequence order, travels through the domain-to-domain link in every territory and upstream and downstream territory, determines entering boundary node group and going out boundary node group of each subdomain respectively; Creating path computing request in boundary node and the m*n bar territory that goes out between boundary node, m is for entering boundary node number, and n is for going out boundary node number, and first territory enters boundary node group and only comprises source node, and tail territory goes out boundary node group and only comprises destination node; Path computing request in described territory is sent to each sub-PCE.

Compared with prior art, the cross-domain path computing scheme that the present invention proposes, based on grade PCE framework, in the sequence of optimum territory, sub-PCE parallel computation forms route segment in the territory in cross-domain path, path route and resource reservation in territory is calculated separately, decreases path resources amount of calculation in the computer capacity in territory and reserved territory, improve computational efficiency, it is possible to meet network application better. It addition, present invention introduces failure domain backtracking algorithm, it is ensured that calculate cross-domain path at the whole network, improve and be calculated as power.

Accompanying drawing explanation

Fig. 1 is MPLS-TE/GMPLS example network topology figure;

Fig. 2 is that many PCE calculate cross-domain path schematic diagram by territory;

Fig. 3 is that BRPC method calculates cross-domain path schematic diagram;

Fig. 4 is that grade PCE framework calculates cross-domain path schematic diagram;

Fig. 5 is the schematic flow sheet of the computational methods in a kind of cross-domain path of the present invention;

Fig. 6 is the flow chart of father and son's cross-domain Path Method of PCE Collaboration computing in one example of the present invention;

Fig. 7 (a) is one of schematic diagram of territory sequence in the embodiment of the present invention;

Fig. 7 (b) is one of schematic diagram of territory boundary node group in the embodiment of the present invention;

Fig. 7 (c) is one of cross-domain path computing topology schematic diagram in the embodiment of the present invention;

Fig. 7 (d) is one of cross-domain path schematic diagram selected in the embodiment of the present invention;

Fig. 7 (e) is one of cross-domain path schematic diagram that in the embodiment of the present invention, resource is assigned;

Fig. 8 (a) is two of the cross-domain path computing topology schematic diagram in the embodiment of the present invention;

Fig. 8 (b) is two of the cross-domain path schematic diagram selected in the embodiment of the present invention;

Fig. 8 (c) is the two of the cross-domain path schematic diagram that in the embodiment of the present invention, resource is assigned;

Fig. 9 (a) is three of the cross-domain path computing topology schematic diagram in the embodiment of the present invention;

Fig. 9 (b) is in the embodiment of the present invention one the two of the schematic diagram of territory sequence;

Fig. 9 (c) is in the embodiment of the present invention the two of the schematic diagram of territory boundary node group;

Fig. 9 (d) is three of the path topology intention in the embodiment of the present invention;

Fig. 9 (e) is three of the cross-domain path schematic diagram selected in the embodiment of the present invention;

Fig. 9 (f) is the three of the cross-domain path schematic diagram that in the embodiment of the present invention, resource is assigned.

Detailed description of the invention

Below in conjunction with drawings and Examples, technical scheme is described in detail.

If it should be noted that do not conflict, the embodiment of the present invention and each feature in embodiment can be combined with each other, all within protection scope of the present invention. Although it addition, illustrate logical order in flow charts, but in some cases, it is possible to perform shown or described step with the order being different from herein.

A kind of computational methods in cross-domain path, as it is shown in figure 5, include:

Father PCE calculates optimum territory sequence according to intra domain routing policy;

The present invention is based on grade PCE framework, from the sequence of optimum territory, in this territory sequence, traversal calculates whole cross-domain paths route, route segment route and the cross-domain path resources of reserved appointment in many sub-PCE parallel computation territories, reduce the path resources time in sub-PCE serial computing and reserved many co-domains, improve computational efficiency.

Described method can also include:

When there is the territory that in whole territory, path computing is failed:

So recalling algorithm by failure domain, territory sequence of reruning, the whole network calculates cross-domain path, it is ensured that be calculated as power.

Described father PCE calculates, according to described sub-PCE, the cross-domain path that in successful territory, Path selection is optimum and includes:

Described father PCE described abstracting link and domain-to-domain link construct cross-domain path computing topology, according to intra domain routing policy, calculate according to the tactic whole cross-domain paths of path metric desired value;

Described father PCE selects currently most cross-domain path.

Described intra domain routing policy can be specified in advance or select according to prior art.

Further, described method can also include: if selected cross-domain path reservation resource failure, then selects the reserved resource of route segment in the territory in the cross-domain path selected by sub-PCE parallel computation described in next excellent cross-domain path request according to path metric desired value.

Described in calculated described territory sequence, in the whole territory of father's PCE scheduling sublayer PCE parallel computation, path route specifically may include that

Fig. 6 is in one example of the present invention, father and son's PCE Collaboration computing cross-domain path flow process, figure only describes the calculation process of a sub-PCE and father and son PCE cooperation message stream. The message that cooperates between father and son PCE adopts RFC5440 agreement PCEP message format, and father and son PCE cooperation message is as follows:

Message 1:InterPath_REQ, the first sub-PCE in territory is sent to the cross-domain path computing request message of father PCE, PCRep message type;

Message 2:IntraPath_REQ, father PCE are sent in a plurality of territory of sub-PCE path computing request message, PCRep message type;

Message 3:IntraPath_RSP, sub-PCE return to path computation result message in a plurality of territory of father PCE, PCRep type of message;

Message 4:IntraAlloc_REQ, father PCE are sent in the reserved specified domain of sub-PCE path resources request message, PCNtf type of message;

Path resources results messages in message 5:IntraAlloc_RSP: the sub-PCE reserved specified domain returning to father PCE, PCNtf type of message;

Message 6:InterPath_RSP, father PCE return to the cross-domain path computation result message of sub-PCE, PCRep type of message.

It is as follows that father PCE calculates process:

Step 101: father PCE receives the first cross-domain path computing request InterPath_REQ message of the sub-PCE in territory, or calculates the failure domain made new advances, territory of fixing a breakdown calculates optimum territory sequence according to intra domain routing policy;

Step 102: if territory sequence calculates unsuccessfully, performs step 115, returns the failure of cross-domain path computing, if it is successful, perform step 103;

Step 103: described father PCE, according to calculated territory sequence order, travels through the domain-to-domain link in every territory and upstream and downstream territory, it is determined that enter out boundary node group, i-th subdomain enters out boundary node group and describes as follows:

BN_en (i, 1) ..., and BN_en (i, m) }: the m of territory i enters boundary node, first territory m=1;

BN_ex (i, 1) ..., and BN_ex (i, n) }: the n of territory i goes out boundary node, tail territory n=1;

First territory enters boundary node group and only comprises source node, tail territory goes out boundary node group and only comprises destination node, create out path computing request in the territory between boundary node, in territory, path becomes abstracting link between the territory building cross-domain path, creates path computing request in i-th subdomain m*n bar territory described above;

Step 104: described father PCE asks path route in each sub-PCE computational fields, and the sub-PCE in all territories sends IntraPath_REQ message in the sequence of territory;

Step 105: described father PCE receives path responses IntraPath_RSP message in the sub-PCE territory returned, if path computing failure in whole territory, performs step 106, otherwise, performs step 108;

Step 106: described father PCE adopts failure domain backtracking algorithm, it is determined that all in territory behind path computing failure subdomain position in the sequence of territory, performs following process:

1) position is in first territory: if downstream domain is tail territory, the failure of cross-domain path computing, performs step 115, if downstream domain is not tail territory, arranging downstream domain is failure domain, performs step 107;

2) position is at intermediate field: arranging this territory is failure domain, performs step 107;

3) position is in tail territory: if Yu Shishou territory, upstream, the failure of cross-domain path computing, performing step 115, if not first territory, arranging territory, upstream is failure domain, performs step 107;

Step 107: failure territory is increased to failure domain sequence by described father PCE, returns and performs step 101, it may be assumed that recalls the territory sequence made new advances of reruning, calculates cross-domain path;

Step 108: follow data confidentiality principle in territory, according to RFC5220 agreement, the IntraPath_RSP message that father PCE receives, the ERO being calculated as path in merit territory in message adopts Path-Key form, described father PCE associates calculating path P ath-Key in successful territory with corresponding abstracting link, in territory, path metric target (metricobject) is arranged to abstracting link metric objective, deletes and calculates the abstracting link that in failed territory, path is corresponding;

Step 109: described father PCE determines whether to receive the IntraPath_RSP message of the sub-PCE in whole territories in the sequence of territory, if it did not, continue waiting for receiving the sub-PCE in territory to calculate response, if all received, performs step 110;

Step 110: construct cross-domain path computing topology with cross-domain abstracting link and domain-to-domain link, according to intra domain routing policy, adopt suitable routing algorithm, calculate according to the tactic whole cross-domain paths of path metric desired value;

Step 111: select currently most cross-domain path, it is determined whether success, if it fails, perform step 115, returns the failure of cross-domain path computing, if it is successful, perform step 112;

Step 112: ask sub-PCE to calculate path reservation resource in the territory in selected optimum cross-domain path, send IntraAlloc_REQ message to sub-PCE;

Step 113: receive the reserved resource response IntraAlloc_RSP message of sub-PCE, judge that in the reserved territory of sub-PCE, whether path resources is successful, if failure, by this cross-domain route deletion or be demarcated as unavailable after perform step 111, that is: next excellent cross-domain path computing is selected to reserve resource, if it is successful, perform step 114;

Step 114: judge whether selected cross-domain path completes route segment resource in reserved territory, if it is not complete, wait that sub-PCE reserves resource response message, if completing, performing step 115 and returning the success of cross-domain path computing;

Step 115: return cross-domain path computation result InterPath_RSP message to the sub-PCE in all territories, terminates father PCE and calculates process.

The calculating process of sub-PCE is as follows:

Step 201: the first sub-PCE in territory receives the cross-domain path computing request of source node, sends cross-domain path computing request InterPath_REQ message to father PCE, thus triggering described step 101;

Step 202: sub-PCE receives path computing request IntraPath_REQ message in the described father PCE m*n bar territory sent, select suitable routing algorithm, calculate the route of optimal path in m*n bar territory, adopt Path-Key form to generate and calculates the ERO information in path in successful territory, to father PCE transmission IntraPath_RSP message;

Step 203: sub-PCE receives path resources request IntraAlloc_REQ message in the described father PCE reserved specified domain sent, call path node and link reserves resource in reserved resource algorithm computational fields, return path resources result IntraAlloc_RSP message in reserved territory to father PCE;

Step 204: sub-PCE receives the described father PCE cross-domain path computation result InterPath_RSP message sent, and discharges path data in not selected territory, this territory;

Step 205: judge that book PCE is whether as the sub-PCE in first territory in cross-domain path, if it is not, terminate sub-PCE to calculate process, if it is, perform step 206;

Step 206: cross-domain path computation result is returned source node, terminates sub-PCE and calculates process.

The calculation element in a kind of cross-domain path, is arranged in father path computing unit PCE; Described device includes:

Described device can also include:

Wherein, described selection module specifically may refer to according to the cross-domain path that Path selection in the successful territory of described sub-PCE calculating is optimum:

Further, described request module can be also used for when selected cross-domain path reservation resource failure, selects the reserved resource of route segment in the territory in the cross-domain path selected by sub-PCE parallel computation described in next excellent cross-domain path request according to described path metric desired value.

Further, described scheduler module in calculated described territory sequence in the whole territory of scheduling sublayer PCE parallel computation path route specifically may refer to:

For convenience of understanding, by several embodiments, present invention application in multiple-domain network is described. In 4 territory MPLS-TE/GMPLS networks shown in Fig. 1, request calculate source node (also referred to as headed by node) the cross-domain path of optimum of N11 to destination node N32.

Embodiment one: path computing and the successful situation of resource reservation in sub-PCE territory

Father PCE controls to calculate cross-domain path flow process, and the cross-domain path of scheduling sublayer PCE parallel computation route and reserves path resources in specified domain, and the present embodiment, by calculating the change of topology between father PCE territory, describes cross-domain path calculation process:

1) father PCE receives the first sub-PCE in the territory cross-domain path request message of calculating forwarded, according to intra domain routing policy, it is determined that optimum territory sequence: territory 1, territory 2, territory 3, sees Fig. 7 (a);

2) according to territory 1, territory 2, territory 3 order, what father PCE determined each territory enters out boundary node group, sees Fig. 7 (b):

	Enter boundary node group	Go out boundary node group
			Territory 1 (PCE1)	{N11}	{ N12, N13}
Territory 2 (PCE2)	{ N21, N25}	{ N22, N23, N24}
			Territory 3 (PCE3)	{ N31, N33, N34}	{N32}

3) father PCE travel through each subdomain enter out boundary node to combination, construct and send all enter boundary node to path computing request in the territory go out boundary node to each sub-PCE, it is exactly specifically: request PCE1 calculates path computing in two territories of N11 to N12, N11 to N13, request PCE2 calculates path in N21 to N22, N21 to N23, N24 to N22, N25 to N22, six territories of N25 to N23, N25 to N24, and request PCE3 calculates path in N31 to N32, three territories of N33 to N32, N34 to N32;

4) path in the optimum territory of PCE1, PCE2, PCE3 parallel computation how point-to-multipoint (MP2MP), for improving path computing efficiency further, can by MP2MP path computing on identical topology resource, resolve into the optimal path parallel computation of multiple point-to-multipoint (P2MP), as: the MP2MP calculating of 2 o'clock to 3 o'clock is resolved into 2 P2MP parallel computations by PCE2, calculate the route in path in 6 territories of optimum simultaneously, only comprise through node and link routing iinformation, it does not have Preserved node and link circuit resource.

Sub-PCE is according to RFC5220 agreement, generate and calculate the Path-Key in path in successful territory, father PCE is returned by the ERO of the PcRep message of PCEP, such as with " jj-PKxxyy ", Path-Key path is described: jj representative domain sequence number, xx represents sequence number in source end node territory, and yy represents sequence number in egress nodes domains;

5) father PCE receives in the territory of whole sub-PCE after path computing response, (in such as territory 1, path N11 to N12 is as abstract path 1-PK12 as abstracting link will to calculate path in successful territory, in territory 2, path N21 to N23 is as abstract path 2-PK13 etc.), path metric desired value (Metricobject) in territory is assigned to the abstracting link in territory, along territory sequence, the cross-domain path computing topology constructed by domain-to-domain link and abstracting link is as shown in Fig. 7 (c), present example adopts KSP algorithm, but it is not restricted to this algorithm, calculate the whole cross-domain path according to the sequence of path metric desired value:

1st is excellent: N11,1-PK12, N12, N21,2-PK13, N23, N34,3-PK42, N32;

2nd is excellent: N11,1-PK12, N12, N25,2-PK52, N22, N31,3-PK12, N32;

3rd is excellent: N11,1-PK12, N12, N21,2-PK14, N24, N33,3-PK32, N32;

...;

6) father PCE selects currently most cross-domain path: N11,1-PK12, N12, N21,2-PK13, N23, N34,3-PK42, N32, as shown in Fig. 7 (d), now, 1-PK12,2-PK13,3-PK42 dotted line connects, and represents but without path resources in reserved territory;

7) father PCE asks path 1-PK12,2-PK13,3-PK42 resource in the reserved specified domain of PCE1, PCE2, PCE3;

8) PCE1, PCE2, PCE3 complete in territory the link circuit resource of path 1-PK12,2-PK13,3-PK42 node parallel and reserve, and result returns father PCE;

9) after father PCE receives the reserved successful message of resource of PCE1, PCE2, PCE3, cross-domain path computation result is returned to PCE1, PCE2, PCE3, PCE4, now reserve path resources in territory, 1-PK12,2-PK13,3-PK42 solid line connects, as shown in Fig. 7 (e), father PCE terminates to calculate.

10) sub-PCE receives cross-domain path computation result, each sub-PCE is path in the ERO information searching territory returning to cross-domain path, path data in the territory that release does not find, PCE1, PCE2, PCE3 discharge path data in the territory outside 1-PK12,2-PK13,3-PK42 respectively, and PCE4 need not discharge path data in any territory;

11) PCE1 is the first sub-PCE in territory, returns cross-domain path computation result to first node N11, and sub-PCE terminates to calculate.

Embodiment two: the situation that in sub-PCE part territory, path computing is failed

Process above and the step 1 of embodiment one) to 4) identical.

The difference is that, in the present embodiment, path failure in two territories of N21 to N22, N21 to N23 in PCE2 computational fields 2, path computing success in other territory, father PCE generates cross-domain path computing topology as shown in Fig. 8 (a), and topology does not comprise N21 to N22 and N21 and arrives two abstracting link of N23.

Subsequent step is referred to embodiment one, with embodiment one the difference is that, the cross-domain path of optimum that in the present embodiment, father PCE calculates and selects is: N11,1-PK12, N12, N25,2-PK52, N22, N31,3-PK12, N32, as shown in Fig. 8 (b), now, 1-PK12,2-PK52,3-PK12 dotted line connects, and represents but without path resources in reserved territory; Correspondingly, father PCE specifies path 1-PK12,2-PK52,3-PK12 resource success in the reserved territory of PCE1, PCE2, PCE3, as shown in Fig. 8 (c), has then proceeded to cross-domain path computing.

Embodiment three: the situation that in the whole territory of sub-PCE, path computing is failed

After father PCE receives cross-domain path computing request, calculating sequence territory, territory 1, territory 2, territory 3, request PCE1, PCE2, PCE3 calculate route segment in each territory; This part can referring to the step 1 of embodiment one) to 4).

In the present embodiment, path all failures in the territory of PCE2 computational fields 2, as shown in Fig. 9 (a), father PCE performs failure domain backtracking and calculates, and arranges territory 2 for failure domain, calculate make new advances sequence territory, territory 1, territory 4, territory 3, as shown in Fig. 9 (b); Enter out boundary node group according to what this sequence father PCE determined each territory, see shown in Fig. 9 (c).

Main PCE asks PCE1, PCE4 and PCE3 to work in coordination with cross-domain path computing. Subsequent step is referred to embodiment one, with embodiment one the difference is that, the cross-domain path computing topology constructed by domain-to-domain link and abstracting link in the present embodiment is as shown in Fig. 9 (d); The cross-domain path of optimum that father PCE calculates and selects is: N11,1-PK13, N13, N41,4-PK12, N42, N31,3-PK12, N32, as shown in Fig. 9 (e), now, 1-PK13,4-PK12,3-PK12 dotted line connects, and represents but without path resources in reserved territory; Correspondingly, father PCE specifies path 1-PK13,4-PK12,3-PK12 resource success in the reserved territory of PCE1, PCE4, PCE3, as shown in Fig. 9 (f), has then proceeded to cross-domain path computing.

Further, if on new sequence territory, territory 1, territory 4, territory 3, in whole territories of PCE4, path also calculates failure, father PCE continues territory 4 is arranged to failure domain, recalculates territory sequence, after Fig. 1 network gets rid of territory 2 and territory 4, territory 1 is unreachable to territory 3, returns the failure of cross-domain path computing.

The method adopting the backtracking of this failure domain of this example, at the whole network by excellent to bad computational fields sequence, until successfully calculating optimum cross-domain path, or till returning and calculating unsuccessfully.

Embodiment four: the situation that in the reserved specified domain of sub-PCE, path resources is failed

This example calculation calculate before cross-domain path process with the step 1 of embodiment one) to 5) identical, be also obtain the topology as shown in Fig. 7 (c);

Father PCE selects currently most cross-domain path: N11,1-PK12, N12, N21,2-PK13, N23, N34,3-PK42, N32, as shown in Fig. 7 (d), it is intended that path resources in PCE1, PCE2, PCE3 reserved 1-PK12,2-PK13,3-PK42 territory respectively;

In the present embodiment, father PCE receives path resources response: PCE1 in computational fields and returns the reserved resource success of 1-PK12, PCE2 returns the reserved resource failure of 2-PK13, PCE3 returns the reserved resource success of 3-PK42, path 1-PK12,2-PK13,3-PK42 resource reservation result in father's PCE recording domain, select next excellent cross-domain path: N11,1-PK12, N12, N25,2-PK52, N22, N31,3-PK12, N32, as shown in Fig. 8 (b); Path resources in path 1-PK12 reserved territory in territory, father PCE only asks PCE2, PCE3 to reserve path resources in 2-PK52,3-PK12 territory, after success as shown in Fig. 8 (c), has continued cross-domain path calculation process. By that analogy, father PCE receives path resources failure response message in the reserved territory of sub-PCE, is selected by next excellent cross-domain path, asks sub-PCE to reserve and chooses path resources in territory not reserved in cross-domain path.

Certainly; the present invention also can have other various embodiments; when without departing substantially from present invention spirit and essence thereof; those of ordinary skill in the art are when can make various corresponding change and deformation according to the present invention, but these change accordingly and deform the scope of the claims that all should belong to the present invention.

Claims

1. the computational methods in cross-domain path, including:

2. the method for claim 1, it is characterised in that also include:

When there is the territory that in whole territory, path computing is failed:

3. the method for claim 1, it is characterised in that described father PCE calculates, according to described sub-PCE, the cross-domain path that in successful territory, Path selection is optimum and includes:

Described father PCE selects currently most cross-domain path.

4. method as claimed in claim 3, it is characterised in that also include:

5. the method for claim 1, it is characterised in that described in calculated described territory sequence, in the whole territory of father's PCE scheduling sublayer PCE parallel computation, path route includes:

6. the calculation element in cross-domain path, is arranged in father path computing unit PCE; It is characterized in that, described device includes:

7. device as claimed in claim 6, it is characterised in that also include:

8. device as claimed in claim 1, it is characterised in that described selection module calculates, according to described sub-PCE, the cross-domain path that in successful territory, Path selection is optimum and refers to:

9. device as claimed in claim 8, it is characterised in that:

Described request module is additionally operable to when selected cross-domain path reservation resource failure, selects the reserved resource of route segment in the territory in the cross-domain path selected by sub-PCE parallel computation described in next excellent cross-domain path request according to described path metric desired value.

10. device as claimed in claim 9, it is characterised in that described scheduler module in calculated described territory sequence in the whole territory of scheduling sublayer PCE parallel computation path route refer to: