Method and system of service placement for service chaining

Patent metadata

Field	Value
Publication number	US-9319324-B2
Application number	US-201314099401-A
Country	US
Kind code	B2
Filing date	Dec 6, 2013
Priority date	Dec 6, 2013
Publication date	Apr 19, 2016
Grant date	Apr 19, 2016

Abstract

A method for placing services at network devices is disclosed. A network contains a plurality of network devices and the network offers a set of services to subscribers. Each subscriber of the network utilizes a subset of the set of service, where an order of the services is not predefined. The method starts with ordering the services from the most utilized service to the least utilized, and selects services from the most utilized to the least utilized. For each service, a network device is selected so that placing the service adds a least sum of additional delay based on services already placed in the network, and a path for each subscriber utilizing the service is updated to include the service, where the path is an ordered chain of services, and where the service is inserted in the path to result in minimum addition to delay to the subscriber.

First claim

What is claimed is:

1. A method implemented at a network device of a network, wherein the network contains a plurality of network devices, wherein the network offers a set of services to subscribers, wherein each subscriber of the network utilizes a subset of the set of services, wherein the subset of the set of services is included in a chain of services for each subscriber, wherein an order of entries within the chain of services is determined by the network device, wherein traversing the plurality of network devices causes delay to the subscribers, and wherein the method associates a service with one of the plurality of network devices of the network when a group of one or more services have not been placed, the method comprising:
ordering the group of one or more services from one utilized by the largest number of subscribers to one utilized by the least number of subscribers;
selecting services from the one utilized by the largest number of subscriber to the one utilized by the least number of subscribers; and
for each service,
selecting one network device of the network for the service, the selecting includes calculating sums of additional delays if the service is to be placed at different network devices of the network and identifying the one network device resulting in a least sum of additional delay; and
updating a path for each subscriber utilizing the service to include the service, wherein the path is an ordered chain of services included in the subset of the set of services the subscriber utilizing, and wherein the updating includes calculating additional delays if the service is inserted at different positions within the ordered chain of services and identifying a position for the service in the path resulting in a minimum addition to the delay to the subscriber.

2. The method of claim 1 , wherein information about delay to the subscribers is based on at least one of a historical data of the subscribers of network during a time period and link delay information provided.

3. The method of claim 1 , wherein each chain of services including an ingress at the beginning of the chain and an egress at the end of the chain, and wherein each of the ingress and egress is one network device of the network.

4. The method of claim 1 , wherein each sum of additional delay based on services already place in the network is a sum of additional delay caused by placing the service at one network device for all existing paths including the service.

5. The method of claim 1 , wherein the delay caused to subscribers is weighted differently at different links of the network.

6. The method of claim 1 , wherein services are weighted differently when calculating the sum of additional delay.

7. The method of claim 1 , wherein the group of unplaced services includes all services provided by the network.

8. The method of claim 1 , wherein the network is a software-defined networking (SDN) system and the method is performed by a controller of the SDN system.

9. A network device coupled to a network, wherein the network contains a plurality of network devices, wherein the network offers a set of services to subscribers, wherein each subscriber of the network utilizes a subset of the set of services, wherein the subset of the set of services is included in a chain of services for each subscriber, wherein an order of entries within the chain of services is to be determined by the network device, wherein traversing the plurality of network devices causes delay to the subscribers, and wherein the network device associates a service with one of the plurality of the network device when a group of one or more services have not been place, the network device comprising:
a service allocation processor for allocating services to the plurality of network devices, the service allocation processor including:
a service selector configured to order the group of one or more services from one utilized by the largest number of subscribers to one utilized by the least number of subscribers, and
the service selector further configured to select services from the one utilized by the largest number subscribers to the one utilized by the least number of subscribers;

for each service,
a service placing logic configured to select one network device of the network for the service, the selection includes a calculation of sums of additional delays if the service is to be placed at different network devices of the network and identification of the one network device resulting in a least sum of additional delay; and
a path planner configured to update a path for each subscriber utilizing the service to include the service, wherein the path is an ordered chain of services included in the subset of the set of services the subscriber utilizing, and wherein the update includes a calculation of additional delays if the service is inserted at different positions within the ordered chain of services and identification of a position for the service in the path resulting in a minimum addition to the delay to the subscriber.

10. The network device of claim 9 , further comprising a traffic flow interface configured to collect information about the delay to the subscribers and the subset of the set of services utilized by the subscribers during a time period.

11. The network device of claim 9 , wherein each chain of services including an ingress at the beginning of the chain and an egress at the end of the chain, and wherein each of the ingress and egress is one network device of the network.

12. The network device of claim 9 , wherein each sum of additional delay based on services already place in the network is a sum of additional delay caused by placing the service at one network device for all existing paths including the service.

13. The network device of claim 9 , wherein the delay caused to the subscriber is weighted differently at different links of the network.

14. The network device of claim 9 , wherein services are weighted differently when calculating the sum of additional delay.

15. The network device of claim 9 , wherein the group of unplaced services includes all services provided by the network.

16. The network device of claim 9 , wherein the network is a software-defined networking (SDN) system and the method is performed by a controller of the SDN system.

17. A non-transitory machine-readable storage medium having instructions stored therein, which when executed by a processor, causes the processor to perform operations implemented at a network device of a network, wherein the network contains a plurality of network devices, wherein the network offers a set of services to subscribers, wherein each subscriber of the network utilizes a subset of the set of services, wherein the subset of the set of services is included in a chain of services for each subscriber, wherein an order of entries within the chain of services is determined by the network device, wherein traversing the plurality of network devices causes delay to the subscribers, and wherein the operations associate a service with one of the plurality of network devices of the network when a group of one or more services have not been placed, the operations comprising:
ordering the group of one or more services from one utilized by the largest number of subscribers to one utilized by the least number of subscribers;
selecting services from the one utilized by the largest number of subscribers to the one utilized by the least number of subscribers; and
for each service,
selecting one network device of the network for the service, the selecting includes calcula

Assignees

• Ericsson Telefon Ab L M

Inventors

• Beheshti-Zavareh Neda
• Zhang Ying

Classifications

• H04L45/0377

  for service chaining · CPC title

• H04L45/20

  Hop count for routing purposes, e.g. TTL · CPC title

• H04L47/2408 Primary

  for supporting different services, e.g. a differentiated services [DiffServ] type of service · CPC title

• H04L45/02

  Topology update or discovery · CPC title

• H04L45/121

  by minimising delays · CPC title