1. Field of the Invention
The present invention generally relates to a method and apparatus for determining whether an event-occurrence time lies after a predetermined timeout-value.
2. Description of the Related Art
Communication systems move more and more towards keeping a state for individual data flows (e.g., for quality-of-service (QOS) features). With several thousand flows on a high-speed network link, the maintenance and handling of a per-flow state require considerably large memories. High-speed systems require on-chip implementation of this memory, and here memory size is critical. Even single bits that are saved on a per-flow state can help reduce the memory size, and hence the chip size, and thus make it cheaper.
A common piece of information that is kept as a part of a flow state is a time-stamp (e.g., the point in time) when the last packet of a flow arrived. These time stamps are mostly used to compare the idle-time of a flow (i.e., the difference between the time-stamp and the actual system time at the time of the arrival of the next packet), to a configured time-out value which may be identical for all state entries. The system time is usually implemented as a bit vector that counts ticks of the system clock. For a system clock rate of 350 MHz and a system wrap time of higher than one second, the time vector has a size of at least 29 bits. If state is kept for a number of 16 k flows, then the time stamps alone require 464 kb (=58 kB) of memory.
In U.S. Pat. No. 5,978,928, a system and method for managing a time-stamp is proposed wherein a table of time stamps is maintained. Each time-stamp corresponds to the age of a block of data. The age of the data is determined from the value of the time-stamp in the table. When a block of data is written, the time-stamp corresponding to the data is individually reset by writing a zero to the stamped value. Each stamp is aged by updating the time stamps at predetermined time intervals.
Aging a time-stamp includes reading the time-stamp, determining whether to advance the time-stamp, and advancing the time-stamp. A random number is generated for each time-stamp. The random number is compared to an increment threshold value. If the random number matches the increment threshold value, then the time-stamp is incremented.
However, a major drawback of this solution, apart from relying on randomness, is the need to update the entire state table in regular intervals.
U.S. Pat. No. 5,974,053 discloses an apparatus for providing service to entities. The apparatus includes a server for providing the service, and a plurality of entities which require the service of the server. A scheduler is provided for scheduling when each of the entities receives the service of the server. A time-stamp mechanism provides a longer-format time-stamp to a requesting entity of the plurality of entities whenever the requesting entity requests service from the server.
Further, the apparatus includes a device for compressing the longer-format time-stamp into a corresponding shorter-format window-based time-stamp and storing the shorter-format window based time-stamp. The scheduler schedules service by the server of the requesting entity based on the shorter-format window-based time-stamp stored in the memory. The window-based time-stamp is used to assign service times to entities. However, the window is non-adjustable in its size or position within the larger-format time-stamp.
USPTO Backgrounds
USPTO Backgrounds