Multi-domain routing computation method and device, path computation element and routing network

Patent metadata

Field	Value
Publication number	US-9712426-B2
Application number	US-201314648835-A
Country	US
Kind code	B2
Filing date	Jul 18, 2013
Priority date	Nov 30, 2012
Publication date	Jul 18, 2017
Grant date	Jul 18, 2017

Abstract

Disclosed is a multi-domain routing computation method, including: when it is determined that there are two or more domains deployed with a Path Computation Elements (PCE) in a network, a routing path is computed, between a PCE of a first domain and a PCE of a last domain among the two or more domains deployed with a PCE, using an extended Backward-Recursive PCE-Based Computation (BRPC) algorithm, and the routing path is computed using a Routing Controller (RC) in domains other than the two or more domains deployed with a PCE. Further disclosed are a multi-domain routing computation device, a path computation element and a routing network. The present disclosure can improve greatly optimality of path computation and has a fairly high efficiency for the path computation.

First claim

The invention claimed is:

1. A multi-domain routing computation method, comprising:
when it is determined that there are two or more domains deployed with a Path Computation Elements (PCE) in a network, computing a routing path, between a PCE of a first domain and a PCE of a last domain among the two or more domains deployed with a PCE, using an extended Backward-Recursive PCE-Based Computation (BRPC) algorithm, and computing a routing path using a Routing Controller (RC) in domains other than the two or more domains deployed with a PCE;
wherein the computing a routing path, between a PCE of a first domain and a PCE of a last domain among the two or more domains deployed with a PCE, using an extended BRPC algorithm comprises:
after a PCE receives a trigger request for path computation, determining whether a domain where the PCE is located is the last domain, if it is the last domain, computing a Virtual Shortest Path Tree (VSPT) of said domain: if it is a non-last domain, further determining whether there is a domain deployed without a PCE between said domain where the PCE is located and a next domain deployed with a PCE downstream of a sequence of domains, if there is not, computing the VPST of said domain; if there is, taking, as extended link topology, an intra-domain abstract link of said domain deployed without a PCE and inter-domain link(s) between domains deployed without a PCE, combining the extended link topology with a link topology of said domain where the PCE is located, and computing the VSPT after the combination of link topology.

2. The method according to claim 1 , after the computing the VSPT of the combined link topology, further comprising:
indicating, as different types of routing paths, a routing path corresponding to a VSPT computed through the extended link topology and a routing path corresponding to a VSPT computed through said domain where the PCE is located.

3. The method according to claim 2 , after the computing a routing path, between a PCE of a first domain and a PCE of a last domain among the two or more domains deployed with a PCE, using an extended BRPC algorithm, further comprising:
transmitting signaling from a source node to a destination node;
when the signaling is routed to the routing path corresponding to a VSPT computed through said domain where the PCE is located, routing the signaling according to the routing path corresponding to the VSPT; and
when the signaling is routed to the routing path corresponding to a VSPT computed through the extended link topology, further computing an intra-domain strict hop path corresponding to a loose hop path of the domain deployed without a PCE, and routing the signaling according to a computed strict hop path.

4. The method according to claim 1 , further comprising:
after the VSPT is computed, if it is determined that said domain where the PCE is located is a non-first domain of the two or more domains deployed with a PCE, transmitting the computed VSPT to a next domain deployed with a PCE upstream of the sequence of domains.

5. The method according to claim 4 , the process that a PCE receives a trigger request for path computation comprises:
receiving, by the PCE, a path computation request message;
or receiving, by the PCE, a VSPT.

6. A multi-domain routing computation device, comprising a determination unit and a computation unit, wherein
the determination unit is configured to, when it is determined that there are two or more domains deployed with a Path Computation Element (PCE) in a network, trigger the computation unit; and
the computation unit is configured to compute a routing path, between a PCE of a first domain and a PCE of a last domain among the two or more domains deployed with a PCE, using an extended Backward-Recursive PCE-Based Computation (BRPC) algorithm, and compute a routing path using a Routing Controller (RC) in domains other than the two or more domains deployed with a PCE;
wherein the computation unit comprises a reception sub-unit, a first determination sub-unit, a second determination sub-unit, a first computation sub-unit and a second computation sub-unit, wherein
the reception sub-unit is configured to receive a trigger request for routing computation;
the first determination sub-unit is configured to determine whether, a domain where a PCE to which the computation unit is attributed is located, is a last domain, trigger the first computation sub-unit when it is determined that said domain is the last domain, and trigger the second determination sub-unit when it is determined that said domain is a non-last domain;
the second determination sub-unit is configured to determine whether there is a domain deployed without a PCE between said domain where a PCE to which the computation unit is attributed is located and a next domain deployed with a PCE downstream of a sequence of domains, trigger the first computation sub-unit when it is determined that there is not, and trigger the second computation sub-unit when it is determined that there is;
the first computation sub-unit is configured to compute a Virtual Shortest Path Tree (VSPT) of said domain where a PCE to which the computation unit is attributed is located; and
the second computation sub-unit is configured to take, as extended link topology, an intra-domain abstract link of said domain deployed without a PCE and inter-domain link(s) between domains deployed without a PCE, combine the extended link topology with a link topology of said domain where a PCE to which the computation unit is attributed is located, and compute the VSPT of the link topology after the combination.

7. The device according to claim 6 , wherein the computation unit further comprises an indication sub-unit configured to, after the second computation sub-unit computes the VSPT of the link topology after the combination, indicate, as different types of routing paths, a routing path corresponding to a VSPT computed through the extended link topology and a routing path corresponding to a VSPT computed through said domain where a PCE to which the computation unit is attributed is located.

8. The device according to claim 7 , further comprising a transmission unit and a routing unit, wherein
the transmission unit is configured to transmit signaling from a source node to a destination node; and
the routing unit is configured to: when the signaling is routed to the routing path corresponding to a VSPT computed through said domain where the PCE is located, route the signaling according to the routing path corresponding to the VSPT; and when the signaling is routed to the routing path corresponding to a VSPT computed through the extended link topology, further computing, using the RC, an intra-domain strict hop path corresponding to a loose hop path of the domain deployed without a PCE, and route the signaling according to a computed strict hop path.

9. The device according to claim 6 , wherein the computation unit further comprises a third determination sub-unit and a transmission sub-unit, wherein
the third determination sub-unit is configured to, after the VSPT is computed, when it is determined that said domain where the PCE is located is a non-first domain of the two or more domains deployed with a PCE, trigger the transmission sub-unit; and
the transmission sub-unit is configured to transmit the computed VSPT to a next domain deployed with a PCE upstream of the sequence of domains.

10. The device according to claim 9 , wherein the reception sub-unit is further configured to receive a path computation request message or receive the VSPT.

11. A Path Computation Element (PCE), comprising a reception unit, a first determination unit, a second determination

Assignees

• Zte Corp

Inventors

• Lu Gang
• Wang Dajiang

Classifications

• H04L45/02

  Topology update or discovery · CPC title

• H04L45/12

  Shortest path evaluation · CPC title

• H04L12/4625 Primary

  Single bridge functionality, e.g. connection of two networks over a single bridge · CPC title

• H04L45/04

  Interdomain routing, e.g. hierarchical routing · CPC title

• H04L45/16 Primary

  Multipoint routing · CPC title