Consistent sampling for network traffic measurement

• US 6,873,600 B1
• Filed: 10/16/2000
• Issued: 03/29/2005
• Est. Priority Date: 02/04/2000
• Status: Expired due to Term

• Current Assignee: AT&T Corporation (AT&T, Inc.)
• Original Assignee: AT&T Corporation (AT&T, Inc.)
• Inventors: Duffield, Nicholas G., Grossglauser, Matthias
• Primary Examiner(s): Pham, Chi
• Assistant Examiner(s): LY, ANH VU H
• Application Number:
  US09/688,335
• Time in Patent Office: 1,625 Days
• Field of Search: 370/230, 370/231, 370/235, 370/252, 370/352, 370/389, 370/392, 370/400, 370/428, 370/353, 370/395.32, 370/229, 370/241, 370/253, 379/112.01, 379/112.06, 379/112.05, 379/133
• US Class Current: 370/252
• CPC Class Codes: H04L 43/024 by adaptive sampling
• CPC Class Codes: H04L 43/50 Testing arrangements

Abstract

Traffic measurement should make it possible to obtain the spatial flow of traffic through the domain, i.e., the paths or trajectories followed by packets between any ingress and egress point of the domain. A method of sampling packet trajectories in a packet switching network allows the direct inference of traffic flows through a measurement domain by observing the trajectories of a subset of all packets traversing the network. A method which assumes that the measurement domain does not change comprises the steps of selecting packets for sampling in accordance with a sampling function of the packet content and generating a practically unique label for each sampled packet. The method does not rely on routing state, its implementation cost is small, and the measurement reporting traffic is modest and can be controlled precisely. Using the same hash function will yield the same sample set of packets in the entire domain, and enables us to reconstruct packet trajectories. An alternate embodiment which assumes no constraints and that the measurement domain may change comprises the steps of applying a sampling function and altering an invariant bit position as a signaling flag in each packet selected for sampling.

Claims

1. A method of sampling internet protocol traffic over links of an internet protocol network comprising the steps of

sampling packets at network traffic points as a function of an internet protocol packet content, and

generating a packet label for each sampled packet, wherein a sampling interval for a given period is determined by the upper bound of a sampled packet'"'"'s expected lifetime.

2. Circuit apparatus for sampling internet protocol traffic over links of an internet protocol network for use in sampling traffic at network traffic points comprising

a processor for computing a sampling function, responsive to the sampling function, for determining packets to be sampled, and for generating a label for each sampled packet, said processor for determining a sampling interval by the upper bound of a sampled packet'"'"'s expected lifetime.