Method and system of service placement for service chaining

摘要

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.

主权项

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; andupdating 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.