Computationally efficient analysis and management of systems modeled as networks

Patent metadata

Field	Value
Publication number	US-11522807-B2
Application number	US-202117373261-A
Country	US
Kind code	B2
Filing date	Jul 12, 2021
Priority date	Sep 10, 2020
Publication date	Dec 6, 2022
Grant date	Dec 6, 2022

Abstract

A technique is described for quantifying a change in a system parameter in response to a perturbation of another system parameter. The technique identifies a region of influence of the perturbation and limits the propagation of the perturbation to the identified region.

First claim

What is claimed is:

1. A method for determining a change in a first system parameter in response to an incremental change in a second system parameter, the method comprising performing by a processor the steps of:
generating a bottleneck structure representing the system, the bottleneck structure:
comprising a plurality of elements, each element representing a respective system resource or a respective user of one or more system resources; and
having a plurality of levels, respective elements at successive levels indicating increasing resource utilization, resource availability, or resource requirements;

receiving an element identifier identifying one of the plurality of elements;
selecting elements that are directly impacted by a change in a parameter associated with the identified element, and determining, for each selected element, a respective initial incremental change in a respective associated parameter;
recursively propagating the respective initial incremental changes through the bottleneck structure; and
deriving a change in the first system parameter by accumulating respective changes in respective parameters associated with elements of a specified type of the bottleneck structure.

2. The method of claim 1 , wherein the plurality of elements comprises:
one or more resource elements, wherein a resource element represents a resource parameter of a corresponding system resource; and
one or more user elements, wherein a user element represents a utilization parameter of a corresponding user of the system.

3. The method of claim 1 , wherein the parameter associated with the identified element comprises resource utilization, resource availability, or resource requirements.

4. The method of claim 1 , wherein the parameter associated with one of the selected elements comprises resource utilization, resource availability, or resource requirements.

5. The method of claim 1 , wherein the identified element comprises a resource element or a user element.

6. The method of claim 1 , wherein the directly impacted elements comprise resource elements or user elements.

7. The method of claim 1 , wherein the plurality of elements comprises:
one or more resource elements of a first type, wherein a resource element of the first type represents a resource parameter of a corresponding system resource of the first type; and
one or more resource elements of a second type, wherein a resource element of the second type represents a resource parameter of a corresponding system resource of the second type.

8. The method of claim 1 , wherein:
the plurality of elements comprises:
one or more link elements corresponding, respectively, to one or more links in a network; and
one or more flow elements corresponding, respectively, to one or more network flows;

flow elements at a first level correspond to flows having smaller flow rates than rates of flows corresponding to flow elements at a second level;
the element identifier identifies a link element; and
the first system parameter comprises total network flow throughput.

9. The method of claim 1 , wherein the step of recursively propagating the respective initial incremental changes through the bottleneck structure comprises:
propagating a first initial incremental change through the bottleneck structure at a first processor; and
propagating in parallel a second initial incremental change through the bottleneck structure at a second processor.

10. The method of claim 1 , wherein the step of recursively propagating the respective initial incremental changes through the bottleneck structure comprises applying a propagation rule corresponding to a type of the selected elements.

11. The method of claim 1 , wherein the step of recursively propagating comprises storing in a heap structure identifiers of one or more of the plurality of elements.

12. The method of claim 11 , wherein:
the heap structure comprises a two-key heap structure, wherein:
a first key represents a base value of a parameter associated with an element of the bottleneck structure; and
a second key represents a increment to the base value, the increment being positive, zero, or negative.

13. A computing apparatus for determining a change in a first system parameter of a system in response to an incremental change in a second system parameter, the computing apparatus comprising:
a first processor; and
a first memory in electrical communication with the first processor, and comprising instructions that, when executed by a processing unit that comprises one or more computing units, wherein one of the one or more computing units comprises the first processor or a second processor, and wherein the processing unit is in electronic communication with a memory module that comprises the first memory or a second memory, program the processing unit to:
generate a bottleneck structure representing the system, the bottleneck structure:
comprising a plurality of elements, each element representing a respective system resource or a respective user of one or more system resources; and
having a plurality of levels, respective elements at successive levels indicating increasing resource utilization, resource availability, or resource requirements;

receive an element identifier identifying one of the plurality of elements;
select elements that are directly impacted by a change in a parameter associated with the identified element, and determine, for each selected element, a respective initial incremental change in a respective associated parameter;
propagate recursively the respective initial incremental changes through the bottleneck structure; and
derive a change in the first system parameter by accumulating respective changes in respective parameters associated with elements of a specified type of the bottleneck structure.

14. The computing apparatus of claim 13 , wherein the plurality of elements comprises:
one or more resource elements, wherein a resource element represents a resource parameter of a corresponding system resource; and
one or more user elements, wherein a user element represents a utilization parameter of a corresponding user of the system.

15. The computing apparatus of claim 13 , wherein the parameter associated with the identified element comprises resource utilization, resource availability, or resource requirements.

16. The computing apparatus of claim 13 , wherein the parameter associated with one of the selected elements comprises resource utilization, resource availability, or resource requirements.

17. The computing apparatus of claim 13 , wherein the identified element comprises a resource element or a user element.

18. The computing apparatus of claim 13 , wherein the directly impacted elements comprise resource elements or user elements.

19. The computing apparatus of claim 13 , wherein the plurality of elements comprises:
one or more resource elements of a first type, wherein a resource element of the first type represents a resource parameter of a corresponding system resource of the first type; and
one or more resource elements of a second type, wherein a resource element of the second type represents a resource parameter of a corresponding system resource of the second type.

20. The computing apparatus of claim 13 , wherein:
the plurality of elements comprises:
one or more link elements corresponding, respectively, to one or more links in a network; and
one or more flow elements corresponding, respectively, to one or more network flows;

flow eleme

Assignees

• Reservoir Labs Inc

Inventors

• Ros-Giralt Jordi
• Amsel Noah
• Yellamraju Sruthi
• Lethin Richard A

Classifications

• H04L47/748

  Negotiation of resources, e.g. modification of a request · CPC title

• H04L47/26

  using explicit feedback to the source, e.g. choke packets · CPC title

• H04L47/745 Primary

  Reaction in network · CPC title

• H04L47/801

  Real time traffic · CPC title

• H04L47/762

  triggered by the network · CPC title