Traffic monitor using leaky bucket with variable fill

Details Traffic monitor using leaky bucket with variable fill Traffic monitor using leaky bucket with variable fill

1999-06-09

2003-05-20

Yao, Kwang Bin (Department: 2662)

Multiplex communications

Data flow congestion prevention or control

Flow control of data transmission through a network

C370S389000, C370S428000, C370S395320

Reexamination Certificate

active

06567379

ABSTRACT:

A portion of the disclosure of this patent document contains material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure, as it appears in the Patent and Trademark Office patent file or records, but otherwise reserves all copyright rights whatsoever.
MICROFICHE APPENDIX
This specification contains a microfiche appendix in two parts A and B. The microfiche appendix consists of one (1) microfiche having 47 frames.
BACKGROUND
1. Field of the Invention
The invention relates to determining the most active traffic flow rates among many on a communications network and, in particular, to using an integrated circuit configured to create a table indicating flow rates for particular packet address identifications.
2. Related Art
FIG. 1
shows a block diagram of a switch
10
in a typical network
12
. As shown, a plurality of sources
14
A and
14
B, destinations
16
A and
16
B, and source/destination combinations
18
A and
18
B are connected to switch
10
. Switch
10
may receive a signal from source
14
A on line
20
which represents information contained in a typical packet form using a conventional Media Access Control (MAC) addressing protocol. Switch
10
receives the signal, examines the destination address identification in the packet, and directs the packet be sent using a second signal on, for example, line
22
to the correct destination such as destination
16
B.
It is of interest to monitor the traffic activity through a network device, such as switch
10
, so that the most active packet addresses are identified. Packet activity may be of interest for many network related reasons, including administration and maintenance requirements such as reconfiguration. Thus selected source addresses, destination addresses, and source/destination pair addresses may be of particular interest. Traffic activity is presently monitored using a remote device such as an RMON (Remote Monitor) Probe. This device is separate from switch
10
.
What is desired is an apparatus and method of identifying the packet identifications most frequently handled by a switch or other network device that is integral to the device itself. It is furthermore desirable that the apparatus be embodied in a single integrated circuit.
SUMMARY
In an embodiment of the invention, an integrated circuit is configured to act as a monitor that uses a modified “leaky bucket” model to distinguish the most active packet identifications handled by a network device such as a switch. In one embodiment the monitor creates a traffic activity table in random access memory (RAM) that contains the identification and an associated traffic activity value for each of the most active packet address identifications. The table contains a fixed number of available records, and each record has a field for a unique packet identification and a field for an associated activity value (a “bucket” associated with each identification).
The monitor periodically samples identifications of packets received by a switch. The sampled packet identification is stored in a buffer and is sequentially compared against each record in the traffic activity table. For each sampled packet identification, all activity table records are examined once. If the sampled identification matches an identification in the activity table, the associated activity value is increased (the bucket begins to fill). If the sampled identification does not match an identification in the current table record, the table record identification's associated activity value is decreased (the bucket leaks). Over time, if an activity value decreases to zero, the record is considered empty. If the sampled identification does not match any identification in the table, and if an empty record exists in the table, the sampled identification is placed in an empty record in the table and an initial value is assigned to its associated activity value.
The rate at which the activity values are increased and decreased is significant. For each comparison in which the sampled identification does not match a current table record identification, the matching activity value is decreased by a fixed amount (the bucket leaks at a fixed rate). But if a sampled identification matches a current table record identification, the matching activity value is increased by an amount inversely proportional to the activity value (the bucket is filled at a rate inversely proportional to the current bucket contents). The relationship between the inversely variable increase amount and the constant decrease amount yields an activity value upper limit that indicates how often a particular packet identification is being sampled (the inversely proportional fill rate and the constant leak rate signifies that for a particular number of times a particular packet identification is sampled, the bucket can only fill to a specified level). Conversely, a particular packet sample rate may be indicated by choosing a specified increase amount and upper limit corresponding to the particular packet sample rate (a particular packet's activity reaches a particular minimum when the bucket fills to a certain level).
The monitor increases the activity values using addends stored in a look up table. The addend table contains discrete activity value upper limits and a unique addend for each upper limit. Thus, if a sampled identification matches an existing identification in the activity table, the monitor examines the activity table's associated activity value, looks to the addend table to find the range in which the activity value falls, and determines the appropriate addend. The monitor then adds the addend to the current activity value and updates the current activity table record with the new activity value.
If a particular packet identification has been added to the activity table, but is not subsequently sampled, the matching activity value will eventually decrease to zero. When the activity value decreases to zero, the monitor considers the record containing the associated identification to be empty and places a new sampled identification in the activity table. The result is that the activity table is constantly updated and contains an activity value for the most significant packet identifications handled by the switch.
In one embodiment the monitor is implemented in an application specific integrated circuit (ASIC) contained in a network switch. The ASIC contains RAM, in which the activity table and other volatile information such as the sampled packet's identification is stored, and other circuits configured to perform the monitoring tasks in accordance with the present invention. The ASIC is connected to an external central processing unit, clock, and information busses.
The monitor ASIC is constructed using conventional techniques. In one embodiment the monitor circuits are specified using the VERILOG language and compiled using SYNOPSYS from a catalog of available circuits. The ASIC is then fabricated using conventional procedures and is installed in the switch for normal operation. In other embodiments a computer or other device is configured to implement the monitoring tasks in accordance with the invention. Computer readable media may be configured to store computer implemented instructions in accordance with the method of the present invention.


REFERENCES:
patent: 5274631 (1993-12-01), Bhardwaj
patent: 5473607 (1995-12-01), Hausman et al.
patent: 5615340 (1997-03-01), Dai et al.
patent: 5790799 (1998-08-01), Mogul
patent: 5852607 (1998-12-01), Chin
patent: 6094435 (2000-07-01), Hoffman et al.
patent: 6118760 (2000-09-01), Zaumen et al.
patent: 6295299 (2001-09-01), Haddock et al.
patent: 6381649 (2002-04-01), Carlson

Affiliated with

Also associated with

Rating

Traffic monitor using leaky bucket with variable fill does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Traffic monitor using leaky bucket with variable fill, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Traffic monitor using leaky bucket with variable fill will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3089929