Patent ID: 6963868
Filing Date: 2005-11-08
Classification: H04L,Y10S

Abstract:
1. A computer-implemented tree structure for organizing routing information to be used in processing messages within a network node, each message being associated with a search key “n” bits in length; said processing including a determination of where to send the message next in order to get the message closer to the desired destination; said structure comprising a direct table (DT) comprised of 2 one or more pattern search control blocks (PSCB's) comprised of 2 each said PSCB entry and direct table entry including a pointer to data associated with a specific route, if at this point a specific routing table entry is a potential match to said search key; each said PSCB entry and direct table entry including a pointer to a subsequent PSCB if the end of a search trail is not identified; each said PSCB entry and direct table entry also including an indication if the search has been resolved to the end of the search trail; means to walk through the tree structure to a trail end; said tree structure including one or more search trails each starting at one of said entries in said direct table, continuing through zero or more PSCBs as guided by linked pointers, and ending at a PSCB or direct table entry containing an end of the search trail entry; and means to access data using a pointer in said PSCB containing an end of search trail entry and to return search results.