System and Method for End- or Service-Node Placement Optimization

• US 20120265868A1
• Filed: 04/11/2012
• Published: 10/18/2012
• Est. Priority Date: 04/13/2011
• Status: Active Grant

• Current Assignee: NEC Corporation
• Original Assignee: NEC Laboratories America Inc (NEC Corporation)
• Inventors: Zhang, Yueping, Jiang, Guofei, Wu, Zhenyu
• Granted Patent: US 9,124,496 B2
• Time in Patent Office: Days
• US Class Current: 709/223
• CPC Class Codes: H04L 41/0833 for reduction of network energy consumption

Abstract

A method for producing a set of optimized node placement solutions for plural nodes of a computer network includes temporarily relocating movable ones of the nodes in the network; for each temporarily relocated movable node, determining a thermal energy of the network resulting from its temporary relocation in the network; for each temporarily relocated movable node, determining a potential energy reduction in the network resulting from its temporary relocation in the network; for each temporarily relocated movable node, determining whether to accept or reject its temporary relocation in the network; accepting the temporary relocation if an acceptance probability is greater than a randomly generated number, the acceptance probability being a function of the potential energy reduction in the network; and repeating the aforementioned steps to generate a set of optimized node placement solutions.

Claims

1. A method for producing a set of optimized node placement solutions for plural nodes of a computer network, the method comprising the steps of:

a) temporarily relocating, in a computer process, movable ones of the nodes in the network;

b) for each temporarily relocated movable node, determining in a computer process, a thermal energy of the network resulting from its temporary relocation in the network;

c) for each temporarily relocated movable node, determining, in a computer process, a potential energy reduction in the network resulting from its temporary relocation in the network;

d) for each temporarily relocated movable node, determining, in a computer process, whether to accept or reject its temporary relocation in the network;

e) accepting the temporary relocation in a computer process, if an acceptance probability is greater than a randomly generated number, the acceptance probability being a function of the potential energy reduction in the network; and

f) repeating steps a-e to generate a set of optimized node placement solutions.

2. The method according to claim 1, further comprising the step of:

for each temporarily relocated movable node, allowing the thermal energy resulting from its temporary relocation in the network, to dissipate.

3. The method according to claim 1, further comprising the step of:

rejecting the temporary relocation in a computer process, if the acceptance probability is less than the randomly generated number, prior to step f.

4. The method according to claim 3, further comprising the step of:

applying a penalty to each of the rejected nodes.

5. The method according to claim 4, further comprising the steps of:

for each rejected node, temporarily relocating it to a different location in the network, in a computer process and repeating steps b-d;

accepting the temporary relocation in a computer process, if the acceptance probability is greater than a randomly generated number; and

removing the penalty.

6. The method according to claim 1, further comprising the step of:

determining, in a computer process, which ones of the nodes of the network can be relocated prior to step a, wherein the nodes that are capable of being relocated are the movable nodes.

7. The method according to claim 1, further comprising the step of:

selecting, in a computer process, a first one of the movable nodes to temporarily relocate in the network prior to step a.

8. The method according to claim 7, further comprising the step of:

selecting, in a computer process, a second one of the movable nodes to temporarily relocate in the network prior to step a and after the temporary relocation of the first one of the movable nodes has been accepted.