Nasser Yazdani

US Patent:

6859455, Feb 22, 2005

Filed:

Nov 10, 2000

Appl. No.:

09/710193

Inventors:

Nasser Yazdani - Creve Coeur MO, US
Paul Seungkyu Min - Clayton MO, US

International Classification:

H04L012/28

US Classification:

370392, 370401

Abstract:

A method and apparatus are provided for building a searchable multi-dimensional index tree that indexes a plurality of data objects. In one aspect of the invention, the index tree divides dataspace into three subspaces and indexes the data objects using a single dimension. If too many data objects map to the same point in that dimension, the dimension is switched to a new dimension of the data object and the data object is indexed using the new dimension. A split node having a split value is used to keep track of the indexing. In another aspect of the invention, the index tree divides dataspace into two subspaces, and equal bits are used in the split nodes to track the content of the data objects in the subspaces. If too many data objects sharing the same key within the same dimension map to a single point, then the dimension is switched to a new dimension and the data objects are indexed using the new dimension. Also disclosed is the multi-dimensional index tree itself as well as a router that uses the multi-dimensional index tree of the present invention to provide packet classification functions.

US Patent:

6614789, Sep 2, 2003

Filed:

Dec 29, 1999

Appl. No.:

09/474452

Inventors:

Nasser Yazdani - Creve Coeur MO 63146
Paul Seungkyu Min - Clayton MO 63105

International Classification:

H04L 1228

US Classification:

370392, 370401

Abstract:

A method and apparatus is provided for comparing and sorting data strings of different lengths, in a given character set, and modifying the data such that queries can be run using different search trees. Three different search trees are provided, including: a binary prefix tree and two m_way tree structures, a static m_way prefix tree and a dynamic m_way prefix tree. The data strings may be prefixes of addresses in TCP/IP protocols and searching may be performed using a host address of a computer network. The method further provides for transmitting packet information associated with the network address. Additionally, switching packets in layer and of the TCP/IP protocol and sending the packets to designated ports of a device is provided. The method may also provide differentiated service or data protection, such as a firewall, based on packet classification information.