Per-flow traffic estimation
View Patent ↗A method of estimating per-flow traffic in a network of nodes interconnected by links samples an incoming traffic stream to a node. A sampling interval is derived based on a desired level of accuracy. The number of two-run occurrences for each flow is tracked in the sample stream. The number of two-runs per flow is then employed to generate an estimate of the traffic of the flow.
1. A computer-implemented method of generating proportions of traffic for flows in a network node, the method comprising the steps of:
(a) the computer generating a sampling interval based on a given accuracy level;
(b) the computer measuring a number of runs for each flow during the sampling interval, each run being a predetermined plurality N of consecutive samples belonging to the same flow, where N is a positive integer greater than 1 and less than the total number of consecutive samples belonging to the same flow;
(c) the computer generating a proportion of flow for each flow based on the corresponding number of runs; and
(d) the computer using the generated proportion of flow to monitor the network node.
2. The invention of claim 1 , further comprising the step of the computer generating a variance for each proportion of flow.
3. The invention of claim 2 , wherein the step of generating the variance generates the variance σ(f) for each proportion p(f) of each flow f as:
σ
(
f
)
=
(
1
-
p
(
f
)
)
(
1
+
p
(
f
)
)
(
1
+
3
p
(
f
)
+
p
2
(
f
)
(
2
+
p
(
f
)
)
2
.
4. The invention of claim 1 , further comprising the step of the computer generating a confidence interval for each flow.
5. The invention of claim 1 , wherein, in step (c), the computer generates each proportion p(f) of each flow f as
p
(
f
)
=
1
2
(
N
2
(
f
)
T
R
+
4
N
2
(
f
)
T
R
+
(
N
2
(
f
)
T
R
)
2
)
,
where T R is the sample interval and N 2 (f) is the number of runs for flow f.
6. The invention of claim 1 , wherein N is 2.
7. The invention of claim 1 , wherein the method is implemented in a processor of a network controller of the node.
8. A network of interconnected nodes having at least one node comprising a processor generating proportions of traffic for flows in a network node, the processor comprising:
a first processing module adapted to generate a sampling interval based on a given accuracy level;
a second processing module adapted to measure a number of runs for each flow during the sampling interval, each run being a predetermined plurality N of consecutive samples belonging to the same flow, where N is a positive integer greater than 1 and less than the total number of consecutive samples belonging to the same flow; and
a third processing module adapted to generate a proportion of flow for each flow based on the corresponding number of runs;
wherein the generated proportion of flow is used to monitor the network node.
9. A computer-readable storage medium having stored thereon a plurality of instructions, the plurality of instructions including instructions which, when executed by a processor, cause the processor to implement a method for generating proportions of traffic for flows in a network node, the method comprising the steps of:
(a) generating a sampling interval based on a given accuracy level;
(b) measuring a number of runs for each flow during the sampling interval, each run being a predetermined plurality N of consecutive samples belonging to the same flow, where N is a positive integer greater than 1 and less than the total number of consecutive samples belonging to the same flow;
(c) generating a proportion of flow for each flow based on the corresponding number of runs; and
(d) using the generated proportion of flow to monitor the network node.