Industrial Technology Research Institute

Reti Corporation

Tsern-Huei Lee

Kuen-Rong Hsieh

Yih-Woei Liang

Jinshuan Eric Lee

Nai-Lun Huang

An-Bang Chang

A compressed pattern matching based on LZW compressed sequences with a simple bitmap-based realization of the Amir-Benson-Farach algorithm is provided. A suffix trie for a searched pattern is determined and a LZW trie is constructed for a compressed data. For each data chunk in the compressed data a variety of information is determined and a node is added to the LZW trie. The queries used to determine the information are implemented through bitmaps, and allowing identification of all occurrence of the searched pattern.

Apparatus and methods for searching a pattern in a compressed data

The present invention discloses a network access admission controller and the method used to determine its schedulability. The basic principle involves determining, for all the connections to be checked, if there is any time slot, among all the time slots within a cycle, that will satisfy the scheduling property without the possible misjudgment of schedulability found in the conventional technology. The inventive method of determining schedulability makes its judgment based on packets issued by all the connections and on each of these connections individually. In particular, a determination is made regarding whether there is a particular time slot, among all the time slots, corresponding to the cycle of connection under evaluation, such that all the time slots prior to it are capable of processing the previously issued packets from the connections having higher priority than this particular time slot. When the connections all have a time slot that satisfies the above conditions, a connection is determined to be schedulable. However, when any of the connections fail to have a time slot that satisfies the above conditions, a connection is determined not to be schedulable.

Admission controller for network access

Growing community of inventors

Hsinchu, Taiwan

Tsern-Huei Lee