Method for correlating behavior between two elements of a system to determine the presence of mutual interaction between the elements

[0002] This application claims the benefit of U.S. Provisional Patent Application Ser. No. 60/273,512, filed Mar. 7, 2001, and entitled “Using traffic to discover network topology,” incorporated herein by reference in its entirety.

[0003] The present invention relates to system behavior measurement and correlation in general, and applications therefor.

[0004] The practical application of behavior correlation techniques is well known in many fields of science and engineering. For example, correlations between levels of automobile traffic and traffic accidents often serve as both a starting point and a benchmark in road safety programs, while correlations between advertising expenditure over the course of an advertising campaign and consumer purchases are invaluable in determining return on investment and providing other measures of effectiveness.

[0005] Whether behavior correlation techniques may be used to determine the presence of mutual interaction between two elements of a system should be examined. Some systems, such as computer networks, have elements that mutually interact, such as by communicating with each other. Computer networks, for example, typically have many network devices that are physically and logically interconnected via communication links. While information about the devices, such as their network address, is typically readily available, information regarding how the devices are physically interconnected must typically be derived manually or by employing automatic topology discovery techniques. Thus, were behavior correlation techniques successfully applied to determine the presence of mutual interaction between elements of a computer network, such techniques could be used to determine how network devices are interconnected. Unfortunately, some systems, including computer networks, have mutually interacting elements whose behavior functions diverge over time with respect to one another, thus making behavior correlation difficult.

[0006] The present invention provides a method for correlating behavior between two elements of a system to determine the presence of mutual interaction between the elements.

[0007] In one aspect of the present invention there is provided a method for correlating behavior between two elements of a system to determine the presence of mutual interaction between the elements, the method including measuring the behavior of two elements of a system over time with respect to mutual interaction, thereby producing two behavior functions, expressing a plurality of constraints on a theoretical distance c between the behavior functions, and determining that the elements are behaving as mutually interacting elements where there exists an actual distance c satisfies the constraints.

[0008] In another aspect of the present invention the expressing step comprises maintaining an upper bound and a lower bound on the theoretical distance c, and the determining step comprises determining where the lower bound is smaller than or equal to the higher bound for any of the constraints.

[0009] In another aspect of the present invention the expressing step comprises expressing each of the constraints using at least two time-consecutive samples (a_n, a_n+1) of one of the functions and at least one sample (b_n) of the other of the functions that is time-intermediate the time-consecutive samples.

[0010] In another aspect of the present invention the expressing step comprises expressing each of the constraints as (a_n−b_n)≦c≦(a_n+1−b_n).

[0011] In another aspect of the present invention the expressing step comprises expressing each of the distances using at least two time-consecutive samples (a_n, a_n+1) of one of the functions and at least one sample (b_n) of the other of the functions that is taken at the same time as one of the time-consecutive samples.

[0012] In another aspect of the present invention the expressing step comprises expressing each of the constraints as (a_n−b_n)≦c≦(a_n+1−b_n).

[0013] In another aspect of the present invention there is provided a method for correlating behavior between two elements of a system to determine the presence of mutual interaction between the elements, the method including measuring the behavior of two elements of a system over time with respect to mutual interaction, thereby producing two behavior functions, expressing a plurality of constraints for a plurality of theoretical distances c_ibetween the behavior functions, and determining that the elements are behaving as mutually interacting elements where there exists a plurality of actual distances c_ithat satisfies the constraints.

[0014] In another aspect of the present invention the expressing step comprises maintaining an upper bound and a lower bound on each of the plurality of theoretical distances c_i, and the determining step comprises determining where the lower bound is smaller than or equal to the higher bound for any of the constraints.

[0015] In another aspect of the present invention the expressing step comprises expressing each of the constraints using a plurality of samples a_nof one of the functions taken at times a^t₁, a^t₂. . . , a^t_n, a first plurality of time-consecutive samples b_nand a second plurality of time-consecutive samples b^t_nof the other of the functions taken at times b^t₁, b^t₂. . . , b^t_n, where a^t₁≦b^t₁≦a^t₂≦b^t₂≦ . . . a^t_n≦b^t_n., and selecting each of the constraints from of a set of constraints defined by the pattern a₁−b₁≦c₁≦a₂−b₁a₂−b₂≦c₂≦min(a₂−b₁₊P(b′₂−b′₁), a₃−b₂)a₃−b₃≦c₃≦min(a₂−b₁₊P(b′₃−b′₁), a₃−b₂₊P(b′₃−b′₂), a₄−b₃).

[0016] In another aspect of the present invention there is provided apparatus for correlating behavior between two elements of a system to determine the presence of mutual interaction between the elements, the apparatus including means for measuring the behavior of two elements of a system over time with respect to mutual interaction, thereby producing two behavior functions, means for expressing a plurality of constraints on a theoretical distance c between the behavior functions, and means for determining that the elements are behaving as mutually interacting elements where there exists an actual distance c satisfies the constraints.

[0017] In another aspect of the present invention the expressing means comprises means for maintaining an upper bound and a lower bound on the theoretical distance c, and the determining means comprises means for determining where the lower bound is smaller than or equal to the higher bound for any of the constraints.

[0018] In another aspect of the present invention the expressing means comprises means for expressing each of the constraints using at least two time-consecutive samples (a_n, a_n+1) of one of the functions and at least one sample (b_n) of the other of the functions that is time-intermediate the time-consecutive samples.

[0019] In another aspect of the present invention the expressing means comprises means for expressing each of the constraints as (a_n−b_n)≦c≦(a_n+1−b_n).

[0020] In another aspect of the present invention the expressing means comprises means for expressing each of the distances using at least two time-consecutive samples (a_n, a_n+1) of one of the functions and at least one sample (b_n) of the other of the functions that is taken at the same time as one of the time-consecutive samples.

[0021] In another aspect of the present invention the expressing means comprises means for expressing each of the constraints as (a_n−b_n)≦c≦(a_n+1−b_n).

[0022] In another aspect of the present invention there is provided apparatus for correlating behavior between two elements of a system to determine the presence of mutual interaction between the elements, the apparatus including means for measuring the behavior of two elements of a system over time with respect to mutual interaction, thereby producing two behavior functions, means for expressing a plurality of constraints for a plurality of theoretical distances c_ibetween the behavior functions, and means for determining that the elements are behaving as mutually interacting elements where there exists a plurality of actual distances c_ithat satisfies the constraints.

[0023] In another aspect of the present invention the expressing means comprises means for maintaining an upper bound and a lower bound on each of the plurality of theoretical distances c_i, and where the determining means comprises means for determining where the lower bound is smaller than or equal to the higher bound for any of the constraints.

[0024] In another aspect of the present invention the expressing means comprises means for expressing each of the constraints using a plurality of samples a_nof one of the functions taken at times a^t₁, a^t₂. . . , a^t_n, a first plurality of time-consecutive samples b_nand a second plurality of time-consecutive samples b′_nof the other of the functions taken at times b^t₁, b^t₂. . . , b^t_n, where a^t₁≦b^t₁≦a^t₂≦b^t₂≦. . . a^t_n≦b^t_n., and means for selecting each of the constraints from of a set of constraints defined by the pattern a₁−b₁≦c₁≦a₂−b₁a₂−b₂≦c₂≦min(a₂−b₁₊P(b′₂−b′₁), a₃−b₂)a₃−b₃≦c₃≦min(b′₂), a₄−b₃).

[0025] The disclosures of all patents, patent applications, and other publications mentioned in this specification and of the patents, patent applications, and other publications cited therein are hereby incorporated by reference in their entirety.

[0026] The present invention will be understood and appreciated more fully from the following detailed description taken in conjunction with the appended drawings in which:

[0027] FIG. 1 is a simplified flowchart illustration of a method of behavior correlation, operative in accordance with a preferred embodiment of the present invention;

[0028] FIG. 2 is a simplified graphical illustration of behavior functions of two system elements, useful in understanding the method of FIG. 1;

[0029] FIG. 3 is a simplified flowchart illustration of a method of behavior correlation of mutually interacting system elements with diverging behavior functions, operative in accordance with a preferred embodiment of the present invention; and

[0030] FIG. 4 is a simplified graphical illustration of diverging behavior functions of two system elements, useful in understanding the method of FIG. 3.

[0031] Reference is now made to FIG. 1, which is a simplified flowchart illustration of a method of behavior correlation of mutually interacting system elements, operative in accordance with a preferred embodiment of the present invention, and additionally to FIG. 2, which is a simplified graphical illustration of behavior functions of two system elements, useful in understanding the method of FIG. 1. In the method of FIG. 1, the behavior of two elements of a system is measured over time with respect to mutual interaction. For example, in a computer network, the number of data packets transmitted by a device port A is measured over time, as is the number of data packets received by a device port B over the same time period (although the counters used might start with different values). In the present embodiment the behavior of A and B is expressed as monotonic increasing functions. Samples a₁, a₂. . . , a_nare taken of port A at times a^t₁, a^t₂. . . , a^t_n, as are samples b₁, b₂. . . , b_ntaken of port B at times b^t₁, b^t₂. . . , b^t_n, such that a^t₁≦b^t₁≦a^t₂≦b^t₂≦. . . a^t_n≦b^t_n. A series of constraints on a theoretical distance c between the behavior functions of A and B may then be expressed using multiple a_n−b_n−a_n+1sample groupings as follows:

[0032] (a₁−b₁)≦c≦(a₂−b₁)

[0033] (a₂−b₂)≦c≦(a₃−b₂)

[0034] . . .

[0035] (a_n−b_n)≦c≦(a_n+1−b_n)

[0036] Thus, for each constraint, at least two time-consecutive samples are taken from one of the behavior functions, and at least one sample is taken from the other of the behavior functions that is either time-intermediate the time-consecutive samples or that is taken at the same time as one of said time-consecutive samples. It will be appreciated that either of the behavior functions may serve as the source of a or b samples, provided that it is so used for each of the constraints.

[0037] If A and B are behaving as mutually interacting elements, then there exists an actual value c that satisfies all of the constraints. It may be seen that each constraint places an upper bound and a lower bound on c such that each inequality may act to tighten the bounds. Conversely, if there is no value c that satisfies the series of constraints, then it may be determined that A and B are not behaving as mutually interacting elements.

[0038] Some systems, including computer networks, have mutually interacting elements whose behavior functions diverge over time with respect to one another. For example, where a variable-length-packet switch mutually interacts with a fixed-length-cell switch, packets are converted into cells before transmission by the packet switch to the cell switch. Where a variable-length packet is not evenly divisible by the length of a fixed-length cell, the last cell is padded with zero bytes. Thus, a TCP/IP packet 1000 bytes in length is converted to 20 ATM cells of 56 bytes each, including an 8 byte header and 48 bytes of packet data, plus an additional ATM cell of 56 bytes in length, including an 8 byte header, the last 40 bytes of packet data, and 8 bytes of padding. In order to measure the behavior of the two switches over time with respect to mutual interaction, the behavior functions of the switches should be expressed in common units of measure. However, since the packet switch counts only packets and bit octets (bytes) of actual data transmitted, while the cell switch counts only received cells which may include padding, multiplying the number of cells received at the cell switch by the number of bytes in a cell is likely to result in a received byte count that exceeds the transmitted byte count, thus resulting in diverging behavior functions, since subsequently transmitted packets might have padded cells as well.

[0039] Reference is now made to FIG. 3, which is a simplified flowchart illustration of a method of behavior correlation of mutually interacting system elements with diverging behavior functions, operative in accordance with a preferred embodiment of the present invention, and additionally to FIG. 4, which is a simplified graphical illustration of diverging behavior functions of two system elements, useful in understanding the method of FIG. 3. In the method of FIG. 3, the behavior of two elements of a system where diverging behavior may be present is measured over time with respect to mutual interaction. For example, in a computer network, where a determination is to be made of the mutual interaction between a cell switch A and a packet switch B, the number of data cells received by cell switch A is measured over time, as is the number of data packets and data octets transmitted by packet switch B over the same time period (although the counters used might start with different values). In the present embodiment the behavior of A and B are expressed as diverging monotonic increasing functions due to cell padding as described hereinabove. Sample cell counts a₁, a₂. . . , a_nare taken of switch A at times a^t₁, a^t₂. . . , a^t_n, as are sample octet counts b₁, b₂. . . , b_n, and sample packet counts b′₁, b′₂. . . , b′_ntaken of switch B at times b^t₁, b^t₂. . . , b^t_n, such that a^t₁≦b^t₁≦a^t₂≦b^t₂≦ . . . a^t_n≦b^t_n. It may then be determined that A and B are behaving as mutually interacting elements if there exists a series of distances c₁, c₂, . . . c_n, between the behavior functions of A and B such that:

[0040] 1) a₁≦b₁+c₁≦a₂≦b₂+c₂≦ . . . b_n+cn

[0041] and

[0042] 2) for each (i,j) where i<j, c_j≦c_i+P(b′_j−b′_i),

[0043] where P is a padding factor, such as 48 or 56 bytes in the present example.

[0044] Thus, a series of constraints on theoretical distances c₁, c₂, . . . c_nmay be selected from of a set of constraints defined by the pattern below using multiple samples:

[0045] a₁−b₁≦c₁≦a₂−b₁

[0046] a₂−b₂≦c₂≦min(a₂−b₁+P(b′₂−b′₁), a₃−b₂)

[0047] a₃−b₃≦c₃≦min(a₂−b₁₊P(b′₃−b′₁), a₃−b₂₊P(b′₃−b′₂), a₄−b₃)

[0048] For each constraint an upper bound and a lower bound is maintained on the distance c_i, where the samples are used to tighten the bound. Should the lower bound be larger than the higher bound for any of the constraints, the elements cannot mutually interact. Thus, if there exist actual distances c_ibetween the diverging monotonic increasing functions of A and B that satisfies the series of constraints, then it may be determined that A and B are behaving as mutually interacting elements. Otherwise, it may be determined that A and B are not behaving as mutually interacting elements.

[0049] It is appreciated that one or more of the steps of any of the methods described herein may be omitted or carried out in a different order than that shown, without departing from the true spirit and scope of the invention.

[0050] While the methods and apparatus disclosed herein may or may not have been described with reference to specific hardware or software, it is appreciated that the methods and apparatus described herein may be readily implemented in hardware or software using conventional techniques.

[0051] While the present invention has been described with reference to one or more specific embodiments, the description is intended to be illustrative of the invention as a whole and is not to be construed as limiting the invention to the embodiments shown. It is appreciated that various modifications may occur to those skilled in the art that, while not specifically shown herein, are nevertheless within the true spirit and scope of the invention.