Browse Prior Art Database

Integrated Services Digital Network Fast Call Matching Algorithm

IP.com Disclosure Number: IPCOM000105178D
Original Publication Date: 1993-Jun-01
Included in the Prior Art Database: 2005-Mar-19
Document File: 4 page(s) / 267K

Publishing Venue

IBM

Related People

Boutcher, DC: AUTHOR

Abstract

A fast algorithm for matching information about incoming Integrated Services Digital Network (ISDN) phone calls to a list of callers has been developed. The algorithm stores the information about ISDN phone calls (the "phonebook") in a balanced binary tree. This algorithm ensures that searching the phonebook grows logarithmically (as opposed to linearly) as the number of entries in the phonebook grows.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 52% of the total text.

Integrated Services Digital Network Fast Call Matching Algorithm

      A fast algorithm for matching information about incoming
Integrated Services Digital Network (ISDN) phone calls to a list of
callers has been developed.  The algorithm stores the information
about ISDN phone calls (the "phonebook") in a balanced binary tree.
This algorithm ensures that searching the phonebook grows
logarithmically (as opposed to linearly) as the number of entries in
the phonebook grows.

      The system maintains a list of callers from whom it is willing
to accept calls.  Each incoming call is matched against this list to
determine if it is acceptable.  For some systems (e.g. a banking
system controlling 1000 automated teller machines) this list could be
very large and very time consuming to search.  The algorithm stores
the phonebook information in a binary tree, and the tree is searching
in such a fashion that the branches of the tree which need to be
searched are quickly isolated.

It was assumed that the phonebook of acceptable callers will contain
three fields:

o   the caller's address (phone number)
o   the caller's subaddress (similar to an extension)
o   one field of user specified data (i.e. the name of the program
    which should talk on this connection)

      The fields stored in the phonebook are included in every
incoming call and matched against the phonebook to determine if the
call is acceptable.  The fields may contain an asterisk (*) to
indicate that any incoming value is acceptable.  When searching the
table the search is continued for all matches, and then the best
match (i.e. with the fewest asterisks) is used.  Fig. 1 shows an
example of how the system functions.

      By arranging the phonebook entries in a balanced binary tree we
can greatly reduce the search time for each incoming call.  A binary
tree is a data structure wherein each entry can point to two
additional entries.  These two additional entries are referred to as
"children".  Each of the children can, in turn, point to two other
sets of children.  Entries in the phonebook are compared by comparing
each field of the entry in turn.  If the fields are different we can
say that one is "greater" than the other.  If the fields are the
same, we continue on to examine the next field.  The binary tree is
arranged so that for each entry, one child will always have values
"less" than the current entry, and the other child will have values
greater than the current entry.  When searching for a specific entry
we can then examine the top entry in the tree.  If the value w...