System and method employing last occurrence and sliding...

Details System and method employing last occurrence and sliding... System and method employing last occurrence and sliding...

1999-11-15

2002-04-09

Shah, Sanjiv (Department: 2172)

Data processing: database and file management or data structures

Database design

Data structure types

C707S793000, C709S232000, C709S233000

Reexamination Certificate

active

06370520

ABSTRACT:

FIELD OF THE INVENTION
The present invention relates generally to computational systems and methods, and more particularly, to a system and method for obtaining minimum and maximum values from a set of sample parameter values using a table of last occurrence and a sliding window. The present invention is particularly useful in systems that manage information transfers over a network through use of a cell prioritization scheme.
BACKGROUND OF THE INVENTION
In many systems which routinely perform computations on a set of discrete variables or parameter values, it is often necessary to compute the minimum and maximum values from the set of parameter values. A traditional approach involves storing all of the parameter values in a memory, sorting the parameter values, and then obtaining the minimum and maximum values from the sorted list of values. In a system in which new data is added on a continuous basis, this traditional approach becomes very time consuming and potentially very costly in terms of memory resources and computing overhead.
In the communications industry, for example, certain systems are required to perform minimum and/or maximum determinations on a repetitive basis and at a relatively high speed. For example, one particular communications technology, referred to as asynchronous transfer mode (ATM), typically utilizes a number of switches or nodes to facilitate the rapid transfer of information cells between source and destination end-stations. Various schemes have been developed to discriminate between cells which are to be accepted by a particular node and cells which are to be discarded by the node. It may be desirable to prioritize cells received by a node using a rating scheme that assigns a priority identifier to each cell, such that the priority identifier indicates the importance of the cell relative to other cells received by the node. It would further appear desirable to implement an information collecting strategy at the node that exploits a high speed, low-overhead minimum and/or maximum priority identifier determination procedure.
There is a need for an improved approach to determining the minimum and/or maximum values from a set of values which increases in size over time, and a need for an approach which requires reduced memory requirements and processing overhead. There is an additional need for such an approach which can be exploited in high-speed ATM switches. The present invention fulfills these and other needs.
SUMMARY OF THE INVENTION
The present invention is directed to a system and method for determining the minimum and/or maximum values from a number of sample parameter values. A table of last occurrence (TOLO-table) is employed, together with a sliding window or filter, to greatly enhance the speed and efficiency when determining the minimum and/or maximum value from a number of sample parameter values that fall within the sliding window. The values of the sample parameters processed using the TOLO-table are typically discrete in nature and restricted to N number of different possible values (e.g., p
i
=p
1
, p
2
, . . . p
N
).
A TOLO-table typically includes a parameter column for storing entries for each one of a limited number of discrete parameter values, such as integers or alphabetic letters, for example. The TOLO-table also includes a time stamp column which provides entries for storing time of receipt data associated with each of the parameter values defined in the parameter column. Alternatively, an order number column, rather than a time stamp column, may be employed for storing number order entries corresponding to the order in which the parameter values occur or are received. Every time a parameter value is received, the time stamp or order number entry associated with the parameter value is updated to the current time or order number. The most recent or last occurrence of a particular parameter value is thus recorded in the TOLO-table.
The minimum and/or maximum values of a set of parameter values maintained in the TOLO-table may be obtained using a sliding window which may be adjusted in size or duration. The sliding window may be defined on the basis of time or by a selected number of sample parameter values. The parameter values falling within the sliding window are scanned to determine the minimum and/or maximum of the applicable parameter values. The TOLO-table also provides an accurate basis for determining whether there has been at least one occurrence of a particular parameter value within the sliding window, in addition to the minimum and/or maximum parameter values.
A minimum/maximum determination methodology that employs a TOLO-table and sliding window in accordance with the principles of the present invention may be used in a wide variety of applications, and is particularly useful in ATM network applications. In one embodiment of an ATM service model, each cell of information is assigned a priority value which determines, in part, the importance of the cell relative to other cells being transmitted through the network. A network node accepts or discards a newly arriving cell based on the priority level of the cell and a threshold priority level computed by the node. If requested, the network node may inform the source about a typical threshold priority level that has been computed in the node. One possible implementation for determining this typical threshold priority level includes the determination of the highest priority level among a set of computed threshold priority levels. A TOLO-table may be used for determining this information.


REFERENCES:
patent: 5262969 (1993-11-01), Ishihara
patent: 5400329 (1995-03-01), Tokura et al.
patent: 5532948 (1996-07-01), Kohno et al.
patent: 5754754 (1998-05-01), Dudley et al.
patent: 5856972 (1999-01-01), Riley et al.
patent: 5857147 (1999-01-01), Gardner et al.
patent: 5864536 (1999-01-01), Foglar
patent: 5889761 (1999-03-01), Yamato
patent: 5909443 (1999-06-01), Fichou et al.
patent: 6041039 (2000-03-01), Kilkki et al.
patent: 6081505 (2000-06-01), Kilkki
patent: 6081843 (2000-06-01), Kilkki et al.
patent: 6163808 (2000-12-01), Kilkki
patent: 6167030 (2000-12-01), Kilkki et al.
patent: 0 903 894 (1999-03-01), None
Technical Committee, Traffic Management Specification Version 4.0, af-tm-0056.000, pp. 1-59 (Apr. 1996).
Integrated Services Digital Network (ISDN) Overall Network Aspects and Functions, Traffic Control and Congestion Control in B-ISDN, ITU-T Recommendation I.371, pp. 1-27 (Mar. 1993).
“What are the meaning of CBR, VBR, ABR, UBR?”, http://cell-relay.indiana.edu/cell-relay/FAQ/ATM-FAQ/d/d19.html, maintained by Carl Symbroski, last changed Aug. 20, 1996, pp. 1-2 (updated Feb. 6, 1997).
“ATM Lecture”, http://syllabus.syr.edu/Ist/Mweschen/Ist656/Week4/lecture/atm/atm.html, pp. 1-5 (updated Feb. 6, 1997).
Livio Lambarelli, CSELT (editor), “ATM Service Categories: The Benefits to the User,” http://www.atmforum.com/atmforum/service_categories.html, Torino, Italy, pp. 1-10 (updated Jan. 29, 1997).
Gary Kessler, “An Overview of ATM Technology,” Jan. 1995, http://www.hill.com/personal/gck/atm_overview.html, pp. 1-10 (updated Feb. 13, 1997).
Engui Yao, “ATM—The New Technology for Tomorrow's B-ISDN,” Dec. 1994, http://www2.msstate.edu/~ey1/paper/tkt8793paper.html, pp. 1-23 (updated Oct. 30, 1996).

Affiliated with

Also associated with

Rating

System and method employing last occurrence and sliding... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with System and method employing last occurrence and sliding..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method employing last occurrence and sliding... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2825742