Computationally efficient analysis and management of systems modeled as networks
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.
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 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.
21. The computing apparatus of claim 13 , wherein:
the processing unit comprises a first computing unit and a second computing unit; and
to propagate recursively the respective initial incremental changes through the bottleneck structure, the instructions program the processing unit to:
propagate a first initial incremental change through the bottleneck structure using the first computing unit; and
propagate, in parallel, a second initial incremental change through the bottleneck structure using the second computing unit.
22. The computing apparatus of claim 13 , wherein to propagate recursively the instructions program the processing unit to store in a heap structure identifiers of one or more of the plurality of elements.
23. The computing apparatus of claim 22 , 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.
24. The computing apparatus of claim 13 , wherein to propagate recursively the respective initial incremental changes through the bottleneck structure, the instructions program the processing unit to apply a propagation rule corresponding to a type of the selected elements.