Highly scalable subscription matching for a content routing network

A method of matching subscriptions to published documents in a content-router, comprising:

• receiving subscription information;
• receiving published documents;
• storing said subscription information and said published documents in memory;
• instructing a subscription matching accelerator of the locations in memory of said published documents;
• transferring portions of said stored published documents from said memory to said accelerator on an as-needed basis;
• providing said subscription information to said accelerator;
• and
• processing said portions in said accelerator to perform subscription matching in said subscription matching accelerator independently of other functions performed within the content-router using a non-finite automaton, and
• wherein said non-finite automaton combines a self-loop state and predecessor state into a single data structure, caches a handle when there is only one outgoing arc, indicates whether a collision occurs for any outgoing arcs to reduce memory bandwidth, flags whether a destination state needs to be added to execution stack, splits an execution stack into normal states and self-loop states, and uses a level recovery stack to free allocated memory in the execution stack.

An apparatus for matching subscriptions to published documents in a content-routed network, comprising:

• a processor;
• a memory for storing subscription information and a published documents under the control of said processor;
• a subscription matching accelerator for performing subscription matching;
• said processor being configured to transfer portions of said stored published document from said memory to said accelerator on an as-needed basis;
• and
• wherein subscription matching is performed in said subscription matching accelerator independently of said processor, and
• wherein said accelerator is configured to perform said subscription matching for multi-level documents using a non-finite automaton containing normal and self-loop states,
• an execution stack for storing said normal and self-loop states, memory slots within said execution stack being associated with respective pointers, and said normal and self-loot, states being organized as distinct groups within said execution stack,
• a logic unit for writing the current free pointer for both the normal and self-loop states is written to an execution stack recovery stack which maintains the normal and self-loop free pointers for each document level each time a new start element event is received,
• the logic unit being configured to read the head of the execution recovery stack when end elements are received and the reinitialize the free pointers normal and self-loop free pointers the read values.