Method and apparatus for placing services in a network

• US 9,432,268 B2
• Filed: 01/28/2013
• Issued: 08/30/2016
• Est. Priority Date: 01/28/2013
• Status: Active Grant

• Current Assignee: Telefonaktiebolaget LM Ericsson
• Original Assignee: Telefonaktiebolaget LM Ericsson
• Inventors: Zhang, Ying, Beheshti-Zavareh, Neda
• Primary Examiner(s): Thieu, Benjamin M
• Application Number:
  US13/751,826
• Publication Number:
  US 20140215074A1
• Time in Patent Office: 1,310 Days
• Field of Search: 709/203, 709/223, 709/226
• US Class Current: 1/1
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04L 41/40 using virtualisation of network functions or resources, e.g. SDN or NFV entities
• CPC Class Codes: H04L 41/5045 Making service definitions prior to deployment

Abstract

Embodiments of the present disclosure include a method and apparatus for placing services in a network. The network and a set of services to be placed within the network are defined. A set of requirements for a plurality of subscribers is determined. Each requirement is a sequence of services to traverse for each subscriber. The services are placed such that a total delay or total distance is minimized for all subscribers.

Claims

1. A method for connecting services to a network controlled by a logically centralized controller, which comprises:

the logically centralized controller;

defining the network;

defining a set of services to be connected to the network;

determining a set of requirements for a plurality of subscribers, each requirement being a sequence of services to traverse for each subscriber;

connecting each service of the set of services to the network in a respective location such that a total delay or total distance is minimized for all subscribers, wherein the logically centralized controller is further operative for;

determining service dependencies for each service, wherein a service dependency for a current service operating to quantify how placing the current service at a location depends on location of other services in the set of services; and

connecting services of the set of services to the network where delay dependencies of a connected service match most closely with the service dependencies of the connected service;

wherein placing each service further comprises;

computing a dependency ratio;

computing a delay ratio;

computing a difference between the delay ratio and the dependency ratio for each location pair;

determining a sum over all differences; and

selecting a location having a least amount of differences.

2. The method of claim 1, wherein the set of services is connected to the network by the logically centralized controller in accordance with a greedy algorithm.

3. The method of claim 1, wherein the logically centralized controller comprises an Open Flow controller.

4. The method of claim 1, wherein dependencies between each individual service, other services in the set of services, and all ingress points are determined.

5. The method of claim 1, wherein determining the service dependencies comprises computing a dependency ratio by factoring a number of subscribers for a link of a service being placed over a total in degree of the service.

6. The method of claim 5, wherein the total in degree of the service is computed as the sum of all subscribers'"'"' traffic including an ingress point and all other services in the set of services.

7. The method of claim 1, wherein computing the dependency ratio comprises factoring a number of subscribers for a link of a service being placed over a total in degree of the service.

8. The method of claim 7, wherein the total in degree of the service is computed as the sum of all subscribers'"'"' traffic including an ingress point and all other services in the set of services.

9. The method of claim 1, wherein computing the delay ratio further comprises:

searching for all non-occupied locations in the defined network;

computing a delay between a current location and all other placed services and ingresses; and

computing a ratio of the delay over the sum of all delays.

10. An apparatus for connecting services to a network controlled by a logically centralized controller, the apparatus comprising:

a memory; and

a processor coupled to the logically centralized controller, the logically centralized controller configured to;

define the network;

define a set of services to be connected to the network;

determine a set of requirements for a plurality of subscribers, each requirement being a sequence of services to traverse for each subscriber;

connect each service of the set of services to the network in a respective location such that a total delay or total distance is minimized for all subscribers,

wherein the logically centralized controller is further configured to;

determine service dependencies for each service, wherein a service dependency for a current service is operative to quantify how placing the current service at a location depends on location of other services in the set of services; and

connect services of the set of services to the network where delay dependencies of a connected service match most closely with the service dependencies of the connected service;

wherein placing each service further comprises;

computing a dependency ratio;

computing a delay ratio;

computing a difference between the delay ratio and the dependency ratio for each location pair;

determining a sum over all differences; and

selecting a location having a least amount of differences.

11. The apparatus of claim 10, wherein the centralized controller comprises an Open Flow controller.

12. The apparatus of claim 10, wherein dependencies between each individual service, other services in the set of services, and all ingress points are determined.

13. The apparatus of claim 10, wherein determining the service dependencies comprises computing a dependency ratio by factoring a number of subscribers for a link of a service being placed over a total in degree of the service.

14. The apparatus of claim 13, wherein the total in degree of the service is computed as the sum of all subscribers'"'"' traffic including an ingress point and all other services in the set of services.