Browse Prior Art Database

Algorithm for producing a reduced set of pattern/group pairs to identify incoming request strings with a predetermined group.

IP.com Disclosure Number: IPCOM000010012D
Original Publication Date: 2002-Oct-09
Included in the Prior Art Database: 2002-Oct-09
Document File: 7 page(s) / 90K

Publishing Venue

IBM

Abstract

By identifying a set of pattern/group pairs, the complete list of mappings between request strings and groups needn't be installed into a running system. This has two advantages. Firstly it reduces the amount of storage required to store the mappings. Secondly if there are less patterns to be compared with an incoming request, CPU processing time for an incoming request is reduced.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 28% of the total text.

Page 1 of 7

  Algorithm for producing a reduced set of pattern/group pairs to identify incoming request strings with a predetermined group.

In general terms, the nature of this algorithm is to create a set of patterns which may be used to map a set of character strings to a set of groups.

    Given the assumptions listed below a set of patterns will be created that can be tested against a character string at run time to identify a pre-configured group. The advantages of this are discussed later.

The assumptions are as follows:

A finite set of known and fully enumerated character strings are available at configuration time.

A finite set of known and fully enumerated groups are available at configuration time.

A complete many to one mapping of character strings to groups is available at configuration time.

    The results of the algorithm are a set of patterns in the format of either a 'character string : group' or 'character string * : group', where '*' represents a simple wildcard whereby all strings which begin with the given character string map to the same group. This algorithm was created specifically for a remote method invocation application which needs to map runtime requests (received over the wire) to one of a set of pre-configured runtime characteristics. Therefore we will use the term 'Request String' instead of 'character string'. However, it is expected that this algorithm may have further uses beyond the one described.

    The problem was to reduce the amount of data needed to associate an incoming request string (e.g a method identifier or signature) with a predetermined grouping. Given any number of possible request strings, each associated with one of any number of groups, we defined an algorithm that would generate a set of generic and specific (as appropriate) pattern/group pairs. The patterns could then be used in a running system to identify an incoming request string with the group to which the request string was originally related.

    The grouping of request strings is desirable for a number of reasons including security (identifying groups of users with request strings they are allowed to run), workload management, system monitoring and statistics (gathering and collating of data based on groups of requests).

    It is not claimed that this algorithm will generate the statistically ideal minimum set of patterns for a given input set, only that they will be 'reasonably' optimised. We are aware of some potential avenues of further research in order to further optimise this algorithm.

The advantages of using this algorithm are as follows:

By identifying a set of pattern/group pairs, the complete list of mappings between request strings and groups needn't be installed into a running system. This has two advantages. Firstly it reduces the amount of storage

Page 2 of 7

required to store the mappings. Secondly if there are less patterns to be compared with an incoming request, CPU processing time for an incoming request is reduced.

This process c...