Optimization framework for multi-tenant data centers

Patent metadata

Field	Value
Publication number	US-9813301-B2
Application number	US-201514830303-A
Country	US
Kind code	B2
Filing date	Aug 19, 2015
Priority date	Aug 20, 2014
Publication date	Nov 7, 2017
Grant date	Nov 7, 2017

Abstract

Systems and methods for decoupled searching and optimization for one or more data centers, including determining a network topology for one or more networks of interconnected computer systems embedded in the one or more data center, searching for routing candidates based on a network topology determined, and updating and applying one or more objective functions to the routing candidates to determine an optimal routing candidate to satisfy embedding goals based on tenant requests, and to embed the optimal routing candidate in the one or more data centers.

First claim

What is claimed is:

1. A computer implemented method for decoupled searching and optimization for one or more data centers, comprising:
determining a network topology for one or more networks of interconnected computer systems embedded in the one or more data centers;
searching for routing candidates based on a network topology determined;
refining a search space for the searching for routing candidates using a scaled exhaustive search, the scaled exhaustive search comprising searching only selected switches and/or hypervisors for all spanning trees that satisfy a pre-determined size constraint specified during the refining a search space; and
updating and applying one or more objective functions to the routing candidates to determine an optimal routing candidate to satisfy embedding goals based on tenant requests, and to embed the optimal routing candidate in the one or more data centers.

2. The method of claim 1 , further comprising determining Virtual Terminal Network (VTN) infoimation, wherein the VTN information includes a list of Virtual Machines (VMs) in the VTN and a hypervisor hosting each of the VMs.

3. The method of claim 1 , wherein the searching further comprises:
determining all common nodes for a hypervisor set;
locating one downward path from each common node to each hypervisor in the hypervisor set for each common node in a plurality of common nodes; and
combining paths from all common nodes to each hypervisor to generate one routing candidate.

4. The method of claim 1 , wherein the objective functions include a combination function which balances weights of latency, bandwidth, and a number of hops.

5. The method of claim 1 , wherein the optimal routing candidate is embedded in a Virtual Terminal Network (VTN) by configuring switches.

6. The method of claim 1 , further comprising aggregating configuration tasks in a network action container to reduce an overall configuration delay in the one or more networks.

7. A system for decoupled searching and optimization for one or more data centers, comprising:
a querying device, connected to one or more networks of interconnected computer systems, to receive a tenant request, the tenant request including one or more embedding goals;
a search router responsive to the tenant request to determine a network topology of the one or more networks of interconnected computer systems,
wherein the search router locates routing candidates based on a detetinined network topology, and
wherein the search router is configured to refine a search space for searching for routing candidates using a scaled exhaustive search, the scaled exhaustive search comprising searching only selected switches and/or hypervisors for all spanning trees that satisfy a pre-determined size constraint specified during the refining of the search space; and

an optimizer for updating and applying one or more objective functions to the routing candidates to determine an optimal routing candidate to satisfy embedding goals based on tenant requests, and for embedding the optimal routing candidate in the one or more data centers.

8. The system of claim 7 , wherein the search router is further configured to determine Virtual Terminal Network (VTN) information, wherein the VTN information includes a list of Virtual Machines (VMs) in the VTN and a hypervisor hosting each of the VMs.

9. The system of claim 7 , wherein the search router is further configured to:
determine all common nodes for a hypervisor set;
locate one downward path from each common node to each hypervisor in the hypervisor set for each common node in a plurality of common nodes; and
combine paths from all common nodes to each hypervisor to generate one routing candidate.

10. The system of claim 7 , wherein the objective functions include a combination function which balances weights of latency, bandwidth, and a number of hops.

11. The system of claim 7 , wherein the optimal routing candidate is embedded in a Virtual Terminal Network (VTN) by configuring switches.

12. The system of claim 7 , further comprising a network action container for aggregating configuration tasks to reduce an overall configuration delay in the one or more networks.

13. A non-transitory computer-readable storage medium comprising a computer readable program, wherein the computer readable program when executed on a computer causes the computer to perform the steps of:
determining a network topology for one or more networks of interconnected computer systems embedded in the one or more data centers;
searching for routing candidates based on a network topology determined;
refining a search space for the searching for routing candidates using a scaled exhaustive search, the scaled exhaustive search comprising searching only selected switches and/or hypervisors for all spanning trees that satisfy a pre-determined size constraint specified during the refining a search space; and
updating and applying one or more objective functions to the routing candidates to determine an optimal routing candidate to satisfy embedding goals based on tenant requests, and to embed the optimal routing candidate in the one or more data centers.

14. The computer-readable storage medium of claim 13 , wherein the searching further comprises:
determining all common nodes for a hypervisor set;
locating one downward path from each common node to each hypervisor in the hypervisor set for each common node in a plurality of common nodes; and
combining paths from all common nodes to each hypervisor to generate one routing candidate.

15. The computer-readable storage medium of claim 13 , wherein the optimal routing candidate is embedded in a Virtual Terminal Network (VTN) by configuring switches.

Assignees

• Nec Lab America Inc
• Nec Corp

Inventors

• Xu Qiang
• Lumezanu Cristian
• Liu Zhuotao
• Arora Nipun
• Sharma Abhishek
• Zhang Hui
• Jiang Guofei

Classifications

• H04L45/123

  Evaluation of link metrics (techniques for monitoring network metrics H04L43/08) · CPC title

• G06F9/45533

  Hypervisors; Virtual machine monitors · CPC title

• H04L41/083

  for increasing network speed · CPC title

• H04L45/124

  using a combination of metrics · CPC title

• H04L43/087

  Jitter · CPC title