Accelerated per-flow traffic estimation
AssigneeLucent Technologies Inc.
InventorsFang Hao, Muralidharan S. Kodialam, Tirunell V. Lakshman
Life of this patent
Estimating the term…
Abstract
A method of estimating per-flow traffic in a network of nodes interconnected by links splits the incoming traffic stream to a node into a number of parallel sub-streams by flow assignment using a hash function. Since each flow in the incoming traffic stream constitutes a larger fraction of the traffic in its sub-stream, the probability of obtaining two-runs increases. The number of two-runs per flow is then employed to generate an estimate of the traffic of the flow.
Claims12
A method of generating proportions of traffic for flows in a network node, the method comprising the steps of:
- (a) determining, based on a hashing function, to which sub-stream a packet of a flow of an input packet stream the packet belongs to;
- (b) updating, for each flow, i) a total sample count, ii) a sub-stream sample count for each sample stream, and iii) a sampling interval;
- (c) measuring a number of runs for each flow, each run being a predetermined plurality of consecutive samples belonging to the same flow;
- (d) testing whether the sampling interval satisfies a predefined accuracy level;
- (e) generating, if the sampling interval satisfies a predefined accuracy level, a proportion of flow in the input packet stream for each flow based on the corresponding number of runs;
- and
- (f) using the generated proportion of flow to monitor the network node.
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 determine, based on a hashing function, to which sub-stream a packet of a flow of an input packet stream the packet belongs to;
- a second processing module adapted to update, for each flow, i) a total sample count, ii) a sub-stream sample count for each sample stream, and iii) a sampling interval;
- a third processing module adapted to measure a number of runs for each flow, each run being a predetermined plurality of consecutive samples belonging to the same flow;
- a fourth processing module adapted to testing whether the sampling interval satisfies a predefined accuracy level;
- and
- a fifth processing module adapted to generating, if the sampling interval satisfies a predefined accuracy level, a proportion of flow in the input packet stream for each flow based on the corresponding number of runs.
A computer-readable 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) determining, based on a hashing function, to which sub-stream a packet of a flow of an input packet stream the packet belongs to;
- (b) updating, for each flow, i) a total sample count, ii) a sub-stream sample count for each sample stream, and iii) a sampling interval;
- (c) measuring a number of runs for each flow, each run being a predetermined plurality of consecutive samples belonging to the same flow;
- (d) testing whether the sampling interval satisfies a predefined accuracy level;
- and
- (e) generating, if the sampling interval satisfies a predefined accuracy level, a proportion of flow in the input packet stream for each flow based on the corresponding number of runs.
Dependencies are inferred from the claim text.