Method and system of service placement for service chaining

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.

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