Time aware path computation

• US 10,476,756 B2
• Filed: 02/03/2015
• Issued: 11/12/2019
• Est. Priority Date: 02/03/2015
• Status: Active Grant

• Current Assignee: Telefonaktiebolaget LM Ericsson
• Original Assignee: Telefonaktiebolaget LM Ericsson
• Inventors: Bruno, Gianmarco, Ceccarelli, Daniele, Lazzeri, Francesco, Nijhof, Jeroen
• Primary Examiner(s): Ly, Anh Vu H
• Application Number:
  US15/546,541
• Publication Number:
  US 20180019930A1
• Time in Patent Office: 1,743 Days
• Field of Search: None
• CPC Class Codes: H04L 41/147 for predicting network behaviour
• CPC Class Codes: H04L 41/40 using virtualisation of network functions or resources, e.g. SDN or NFV entities
• CPC Class Codes: H04L 45/20 Hop count for routing purposes, e.g. TTL
• CPC Class Codes: H04L 45/42 Centralised routing
• CPC Class Codes: H04L 47/827 Aggregation of resource allocation or reservation requests
• CPC Class Codes: H04L 47/83 based on usage prediction

Abstract

A path computation method involves receiving (200) a request for computation of a new path in the network, the request indicating a future time interval when the path is desired. Subsequently a future network status is generated (210, 212, 214), having a representation of availability of path resources at the future time interval, based on selected paths already reserved at that future time interval. Then there is a step of computing (220) which of the path resources to select for the new path according to the future network status. By generating this future network status when the future time interval is known, it can be generated in respect of a limited time interval rather than covering all possible future reservable times. Thus the benefits of time aware path computation can be achieved without the need for maintaining a huge database of availability at all future times, of all the path resources.

Claims

1. A path computation method for use in a communications network having path resources usable for implementing paths, the method having steps of:

receiving a request for computation of a new path in the network, the request indicating a future time interval when the new path is desired;

selecting paths in a log which have path resource reservations at the future time interval;

sending Path reservation requests for the selected path;

subsequently generating a future network status at the future time interval based on the selected paths, having at least a representation of availability of respective ones of the path resources at the future time interval, the generating step being based on a selection from a log of paths already reserved, represented in terms of path resource reservations for each respective reserved path, at least some of the path resource reservations having an associated time interval, and the selection comprising at least those of the reserved paths whose associated time interval corresponds to the future time interval; and

computing which of the path resources to select for the new path according to the future network status.

2. The method of claim 1, the step of generating the future network status having the step of deriving values of availability for respective ones of the path resources with reduced time resolution than a resolution provided in the associated time of resource reservation in the log.

3. The method of claim 1, the generating step having the step of accumulating for each path resource the reservations in respect of that path resource, from the selected paths, and determining an availability from the accumulated reservations.

4. The method of claim 1, having a step of selecting from the log the reserved paths having path resource reservations at the future time interval by a path computation element, the step of generating the future network status and the step of computing the new path also being carried out by the path computation element.

5. The method of claim 4, having a step of updating the log of paths already reserved, and carried out by the path computation element.

6. The method of claim 1, having a step of using a path computation client to select the paths in the log which have path resource reservations at the future time interval, and to send path reservation requests for the selected paths to a path computation element, to enable the path computation element to carry out the step of generating the future network status at the future time interval, and the path computation element being configured to carry out the step of computing the new path.

7. The method of claim 1, having the subsequent step of generating a future network status for a different time interval, different from the future time interval, by detecting, from the log, differences in path resource reservations compared to those at the future time interval, and making corresponding changes to the representation of availability of respective ones of the path resources according to the differences.

8. The method of claim 1, the paths being label switched paths.

9. The method of claim 1, the network having a software defined network controller, the steps of receiving the request, subsequently generating the future network status, and computing the new path being carried out by the software defined network controller, with the path resources being represented as abstracted versions of actual path resources.

15. A non transitory machine readable medium having instructions stored thereon which when executed by a processor cause the processor to carry out a path computation method as set out in claim 1.

10. A path computation method for use in a communications network having path resources usable for implementing paths, the method having steps of:

receiving a request for computation of a new path in the network, the request indicating a future time interval when the path is desired,

making a selection from a log of paths already reserved represented in terms of path resource reservations for each respective reserved path, at least some of the path resource reservations having an associated time interval, and the selection comprising at least those of the reserved paths whose associated time interval corresponds to the future time interval,

sending the selected paths as reservation requests to a path computation element, to enable the path computation element to generate a future network status at the future time interval having at least a representation of availability of the path resources at the future time interval, and

sending the request to the path computation element to enable the path computation element to compute which path resources to select for the new path according to the future network status.

11. Apparatus for path computation in a communications network having path resources usable for implementing paths, the apparatus having:

an interface arranged to receive a request for computation of a new path in the network, the request indicating a future time interval when the new path is desired; and

a processor configured to;

select paths in a log which have path resource reservations at the future time interval;

send path reservation requests for the selected paths; and

generate a future network status at the future time interval based on the selected paths, having at least a representation of availability of respective ones of the path resources at the future time interval, the generating being based on a selection from a log of paths already reserved represented in terms of path resource reservations for each respective reserved path, at least some of the path resource reservations having an associated time interval, and the selection comprising at least those of the reserved paths whose associated time interval corresponds to the future time interval, and

the processor being configured to compute which of the path resources to select for the new path according to the future network status.

12. The apparatus of claim 11, the processor comprising a path computation element also being configured to select from the log the reserved paths having path resource reservations at the indicated future time interval.

13. The apparatus of claim 12, wherein the path computation element is being arranged to update the log of paths already reserved.

14. Apparatus for path computation in a communications network having path resources for implementing paths, the apparatus having:

an interface for receiving a request for computation of a new path in the network, the request indicating a future time interval when the path is desired; and

a processor configured to;

make a selection from a log of paths already reserved represented in terms of path resource reservations for each respective reserved path, at least some of the path resource reservations having an associated time interval, and the selection comprising at least those of the reserved paths whose associated time interval corresponds to the future time interval, and

to send the selected paths as reservation requests to a path computation element, to enable the path computation element to generate a future network status at the future time interval, and

the processor being configured to send the request to the path computation element to enable it to compute which path resources to select for the new path.