# US 2015/0104166 A1 · Suurballe-based Cloud Service Embedding Procedure in Software-Defined Flexible-Grid Optical Transport Networks

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2015/0104166 A1
- Document ID: US20150104166A1
- Status: Published application
- Kind: A1
- Application number: 14/510,163
- Filed: 2014-10-09
- Published: 2015-04-16
- Earliest claimed: 2013-10-10
- Assignees: NEC Laboratories America, Inc.
- Applicants: NEC Laboratories America, Inc.
- Inventors: Ankitkumar Patel; Philip Nan Ji
- Web page: https://patentgrep.com/patent/US20150104166A1

## CPC

- H04L 45/128: for finding disjoint paths
- H04J 14/0257: {Wavelength assignment algorithms}
- H04J 14/0271: {Impairment aware routing}
- H04J 14/0289: {Optical multiplex section protection}
- H04J 14/0295: {Shared protection at the optical channel (1:1, n:m)}
- H04J 14/0297: {Optical equipment protection}
- H04L 45/22: {Alternate routing}
- H04L 45/62: {Wavelength based (optical switching H04Q11/0062)}
- H04Q 11/0066: {Provisions for optical burst or packet networks}
- H04Q 2011/0073: {Provisions for forwarding or routing, e.g. lookup tables}
- H04Q 2011/0081: {Fault tolerance; Redundancy; Recovery; Reconfigurability}
- H04Q 2011/0086: {Network resource allocation, dimensioning or optimisation}
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)
- H04J: MULTIPLEX COMMUNICATION (transmission in general H04B; peculiar to transmission of digital information H04L5/00; systems for the simultaneous or sequential transmission of more than one television signal H04N7/08; in exchanges H04Q11/00; stereophonic systems H04S)
- H04Q: SELECTING (switches, relays, selectors H01H; wireless communication networks H04W)

## Abstract

We propose an efficient procedure, namely disjoint pair procedure based cloud service embedding procedure that first maps working and backup virtual nodes over physical nodes while balancing computational resources of different types, and finally, maps working and backup virtual links over physical routes while balancing network spectral resources using the disjoint pair procedure.

## Claims

### Claim 1

A method comprising the steps of:
implementing by a computer a cloud service embedding in a software defined flexible grid optical transport network, the implementing comprising:
mapping working and backup virtual nodes over physical nodes;
mapping working and backup virtual links over physical routes which comprises:
finding two pairs of node-disjoint routes using a disjoint pair procedure on an auxiliary graph;
selecting a maximum number of virtual links whose node-disjoint routes are partitioned into two separate groups;
allocating spectrum at lowest available wavelength on a selected physical route for a virtual link; and
finding two pairs of node-disjoint routes using the disjoint pair procedure while modifying the auxiliary graph.

### Claim 2 (depends on 1)

The method of claim 1, wherein the disjoint pair procedure comprises Suurballe's procedure.

### Claim 3 (depends on 1)

The method of claim 1, wherein the mapping working and backup virtual nodes over physical nodes comprises arranging virtual nodes in a descending order of average requested computing resources.

### Claim 4 (depends on 3)

The method of claim 3, wherein the mapping working and backup virtual nodes over physical nodes comprises mapping working and backup virtual nodes to physical nodes with those having first and second largest average ration of available to offered computing resources of requested types.

### Claim 5 (depends on 1)

The method of claim 1, wherein the step of finding two pairs of node-disjoint routes using a disjoint pair procedure on an auxiliary graph comprises considering cost of a physical link as a single hop and its physical distance and selecting a pair of node disjoint routes that cumulatively minimizes a required spectrum while not requiring any modification to the auxiliary graph while carrying out the disjoint pair procedure.

### Claim 6 (depends on 1)

The method of claim 1, wherein the step of selecting a maximum number of virtual links comprises the routes in one group being also node disjoint to routes of other group.

### Claim 7 (depends on 1)

The method of claim 1 wherein the step of allocating spectrum at lowest available wavelength on a selected physical route for a virtual link comprises minimizing fragmentation of spectrum and increasing probability of mapping virtual links over physical routes.

### Claim 8 (depends on 1)

The method of claim 1, wherein the step of finding two pairs of node-disjoint routes using the disjoint pair procedure while modifying the auxiliary graph comprises considering cost of a physical link as a single hop and its physical distance, and selecting a pair of node-disjoint routes that cumulatively minimizes the required spectrum while modifying the auxiliary graph while applying the disjoint pair procedure to ensure a survivable mapping of a virtual link with respect to already mapped virtual links.

### Claim 9 (depends on 1)

The method of claim 1, wherein the disjoint pair procedure comprises finding spectrum required for a modulation format along a route at a lowest available wavelength while observing the wavelength and spectrum continuity constraints and spectrum conflict constraint and provisioning working and backup virtual links on respective routes using respective modulation formats by allocating spectrum at found wavelengths respectively and provisioning virtual nodes by reserving computational resources of each type at selected physical nodes.

### Claim 10 (depends on 1)

The method of claim 1, wherein the step of selecting a maximum number of virtual links whose node-disjoint routes are partitioned into two separate groups comprises finding a first set A of virtual links wherein one of the node-disjoint routes of a virtual link within the first set A being in a second set W, the other node-disjoint route of the virtual link within the first set A being in a third set B, the routes in the second set W also being node-disjoint with the routes in the third set B, finding the first set A with maximum number of virtual links, the found node-disjoint routes of the virtual links in the first set A being considered as a solution or mapping virtual links over physical routes.

### Claim 11 (depends on 1)

The method of claim 1, wherein the step of selecting a maximum number of virtual links whose node-disjoint routes are partitioned into two separate groups comprises a shortest route among the node disjoint physical routes being considered as a mapping of working virtual links and the other route being considered as a mapping backup virtual links, the routes of working virtual links and backup virtual links being denoted as PijW and Pijb, respectively, and modulation formats of the working virtual link and backup virtual link being denoted MijW and MijW, respectively, for each virtual link VL(i,j) within a first set.

### Claim 12

A non-transitory storage medium configured with instructions for a computer to carry out the following steps:
implementing by a computer a cloud service embedding in a software defined flexible grid optical transport network, the implementing comprising:
mapping working and backup virtual nodes over physical nodes;
mapping working and backup virtual links over physical routes which comprises:
finding two pairs of node-disjoint routes using a disjoint pair procedure on an auxiliary graph;
selecting a maximum number of virtual links whose node-disjoint routes are partitioned into two separate groups;
allocating spectrum at lowest available wavelength on a selected physical route for a virtual link; and
finding two pairs of node-disjoint routes using the disjoint pair procedure while modifying the auxiliary graph.

### Claim 13 (depends on 12)

The medium of claim 12, wherein the mapping working and backup virtual nodes over physical nodes comprises arranging virtual nodes in a descending order of average requested computing resources.

### Claim 14 (depends on 13)

The medium of claim 13, wherein the mapping working and backup virtual nodes over physical nodes comprises mapping working and backup virtual nodes to physical nodes with those having first and second largest average ration of available to offered computing resources of requested types.

### Claim 15 (depends on 12)

The medium of claim 12, wherein the step of finding two pairs of node-disjoint routes using a disjoint pair procedure on an auxiliary graph comprises considering cost of a physical link as a single hop and its physical distance and selecting a pair of node disjoint routes that cumulatively minimizes a required spectrum while not requiring any modification to the auxiliary graph while carrying out the disjoint pair procedure.

### Claim 16 (depends on 12)

The medium of claim 12 wherein the step of allocating spectrum at lowest available wavelength on a selected physical route for a virtual link comprises minimizing fragmentation of spectrum and increasing probability of mapping virtual links over physical routes.

### Claim 17 (depends on 12)

The medium of claim 12, wherein the step of finding two pairs of node-disjoint routes using the disjoint pair procedure while modifying the auxiliary graph comprises considering cost of a physical link as a single hop and its physical distance, and selecting a pair of node-disjoint routes that cumulatively minimizes the required spectrum while modifying the auxiliary graph while applying the disjoint pair procedure to ensure a survivable mapping of a virtual link with respect to already mapped virtual links.

### Claim 18 (depends on 12)

The medium of claim 12, wherein the disjoint pair procedure comprises finding spectrum required for a modulation format along a route at a lowest available wavelength while observing the wavelength and spectrum continuity constraints and spectrum conflict constraint and provisioning working and backup virtual links on respective routes using respective modulation formats by allocating spectrum at found wavelengths respectively and provisioning virtual nodes by reserving computational resources of each type at selected physical nodes.

### Claim 19 (depends on 12)

The medium of claim 12, wherein the step of selecting a maximum number of virtual links whose node-disjoint routes are partitioned into two separate groups comprises finding a first set A of virtual links wherein one of the node-disjoint routes of a virtual link within the first set A being in a second set W, the other node-disjoint route of the virtual link within the first set A being in a third set B, the routes in the second set W also being node-disjoint with the routes in the third set B, finding the first set A with maximum number of virtual links, the found node-disjoint routes of the virtual links in the first set A being considered as a solution or mapping virtual links over physical routes.

### Claim 20 (depends on 12)

The medium of claim 12, wherein the step of selecting a maximum number of virtual links whose node-disjoint routes are partitioned into two separate groups comprises a shortest route among the node disjoint physical routes being considered as a mapping of working virtual links and the other route being considered as a mapping backup virtual links, the routes of working virtual links and backup virtual links being denoted as PijW and Pijb, respectively, and modulation formats of the working virtual link and backup virtual link being denoted MijW and MijW, respectively, for each virtual link VL(i,j) within a first set.
