LATTICE BASED TRAFFIC MEASUREMENT

摘要

Based on lattice theory and fomal concept analysis, a lattice of interconnected concepts is constructed from flow entries available at a communications switch. Each concept describes a subset of flows and a subset of the flow attributes. Based on user queries, the lattice is used to build disjoint sets of flows referred to as flowsets. Each user query specifies one or more of the flow attributes to be measured. Each flowset includes one or more of the flows to thereby enable sharing of the hardware counters among the flows. One hardware counter included in the switch is then assigned to each flowset. Preferrably, target concepts and projection concepts are identified in the lattice. A target concept describes flow attributes matching those of the user queries. A projection concept comprises intersections of the target concept extents in the lattice. Ground concepts are identified based on a mapping of flows to a semi-lattice defined by the projection concepts. A ground concept defines a group of flows forming a flowset. The framework described herein provides exact statistics and more flexibility in traffic measurement while minimizing the number of needed hardware counters.