Classifications

• • H—ELECTRICITY
  • H04—ELECTRIC COMMUNICATION TECHNIQUE
  • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
  • H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
  • H04L9/40—Network security protocols
• • H—ELECTRICITY
  • H04—ELECTRIC COMMUNICATION TECHNIQUE
  • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
  • H04L69/00—Network arrangements, protocols or services independent of the application payload and not provided for in the other groups of this subclass
  • H04L69/12—Protocol engines
• • H—ELECTRICITY
  • H04—ELECTRIC COMMUNICATION TECHNIQUE
  • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
  • H04L69/00—Network arrangements, protocols or services independent of the application payload and not provided for in the other groups of this subclass
  • H04L69/30—Definitions, standards or architectural aspects of layered protocol stacks
  • H04L69/32—Architecture of open systems interconnection [OSI] 7-layer type protocol stacks, e.g. the interfaces between the data link level and the physical level

Definitions

• Information flows within or between computers must have a structure that allows meaning to be extracted in order to be useful.
• the encoding of the information is generally termed its syntax and the term semantics is used for the meaning of the information, which may imply actions to be taken.
• the information flows are many and various; usually specific non-general methods are associated with the processing of each type and level of such flows within the computer.
• Frames are a general way of representing information and its structure in artificial intelligence systems. Essentially, a frame is a set of attributes and each attribute in a frame has a type and a value. Furthermore, any attribute can itself be a frame. Many of the information flows within or between computers can be represented as sequences of frames. A general apparatus and method in accordance with the invention processes information flows which can be represented as sequences of frames. Preferred embodiments of the invention encapsulate the common processing of frames in a single processing engine that can efficiently handle information flows possessing a wide variety of syntactic and semantic characteristics.
• Preferred embodiments deal abstractly with the information flows, relying on one class of lower level routines (termed 'adapter routines') to provide inputs and on other classes of lower level routines (termed 'action routines') to implement any concrete actions necessary to accomplish the processing task.
• the adapter and action routines can be made simpler and smaller and thus easier to program.
• the processing engine includes a common core engine and a plurality of support routines.
• the support routines operate on at least one hierarchical memory store, such as a stack of attributes and a stack of frames.
• the support routines can also generate synthetic attributes for storage in the stack of attributes.
• the processing engine is preferably reentrant and capable of multi-threading.
• the information flows can represent various kinds of information.
• the information flow can be a protocol-based stream of data between computers for intercomputer communications.
• the information flow can also represent intracomputer communications, such as configuration and environment information.
• the processing engine can also be viewed as a language processor.
• FIG. IA is a block diagram illustrating a prior art system for interchanging information over a computer network.
• FIG. IB is a representive electronic mail message processable by the prior art system of FIG. IA.
• FIG. 2 is a simplified block diagram illustrating a basic embodiment of the invention.
• FIG. 3 is a more detailed block diagram of a preferred embodiment of the invention.
• FIG. 4 is a schematic diagram of a preferred embodiment of an initialized memory store.
• FIG. 5 is a schematic diagram of a representative memory store of FIG. 4 with data stored therein.
• FIG. 6 is a schematic diagram of the memory store of FIG. 5 after invocation of the 'endFrame' routine 125 of FIG. 3.
• FIG. 7 is a schematic diagram of the memory store of FIG. 6 after invocation of the 'setAttribute' routine 135 of FIG. 3.
• FIG. 8 is a schematic diagram of the memory store of FIG. 7 after invocation of the 'upAttribute' routine 145 of FIG. 3.
• FIG. 9 is a block diagram of a preferred embodiment of the invention employing parallel processing and pipelining techniques.
• FIG. 10 is a block diagram of a memory construct for the system of FIG. 9.
• FIG. IA is a block diagram illustrating a prior art system for interchanging information over a computer network.
• two computers 1, 2 are exchanging information over a computer network 3, such as Ethernet, which has its own defined commumcation protocols.
• the first computer 1 includes layers of procedures to translate the data from the network protocol into information which can be presented to a user.
• the computers 1, 2 have identical internal procedural layers. However, the two computers 1, 2 may typically translate through different layers of protocols.
• FIG. 2 is a representive electronic mail message processable by the prior art system of FIG. IA.
• a network interface routine receives the information flows from the network and processes the network protocol layer.
• a Transmission Control Protocol (TCP) procedure processes the TCP layer.
• a Simple Mail Transport Protocol (SMTP) procedure processes the SMTP layer.
• An RFC822 procedure processes the mail protocol layer.
• a user procedure displays the information to the user. Messages created by the user are converted by the respective computer procedures into the network protocol for transmission across the network 3 to the destination computer.
• Preferred embodiments of the computing systems in accordance with the invention facilitate the separation of the primary task of processing an appropriate information flow into three distinct subtasks, one of which is a processing engine that is universally applicable to all such information flows.
• the information flows can be viewed as frames as defined by Marvin
• FIG. 2 is a schematic block diagram of a basic embodiment of the invention.
• a processing engine 10 has as its responsibilities: 1) validation that the information flow is a sequence of frames, and 2) the primary control logic including iteration and recursion to process the sequence.
• At least one adapter routine 20 is responsible for scanning an incoming information flow l j , recognizing frame boundaries and attributes, and signalling the processing engine 10 as they are encountered.
• a plurality of action routines 30 are responsible for implementing the actual processing of the components of the information flow l j when activated by the processing engine 10. The action routines 30 can also generate outgoing information flows I 0 , which can be recursively processed through an adapter routine 20.
• the adapter routine 20 and the action routines 30 are specifically written by a programmer for the target computer. Preferably, there are multiple adapter routines 20, each specifically written for a particular protocol. As will be shown below, the processing engine 10, the adapter routines 20 and the action routines 30 are very simple to program because the incoming information flows l j are treated as sequences of frames of data.
• FIG. 3 is a schematic block diagram of a preferred embodiment of the invention.
• the larger arrows represent control signals and the smaller arrows extending from dots represent data flow.
• General purpose routines of the processing engine are shown unshaded, whereas non-general purpose routines (specifically programmed for the environment) are shown shaded in the figure.
• the processing engine 10 is illustrated as having two major components, a reentrant frame processor (FRAP) 12 which acts as the core engine and multiple memory contexts 100.
• the processing engine 10 communicates with multiple context-linked adapter routines 20, which receive multiple incoming information flows l j , at least one information flow per adapter 20.
• the processing engine 10 is triggered by multiple potential caller routines 50. Typically, each caller routine 50 acquires at least one context to avoid conflicts.
• the processing engine 10 also communicates with general purpose action routines 30 and special context-linked action routines 60, 70, 80.
• each memory context 100 is maintained by a plurality of support routines.
• the support routines include a 'putFrame' routine 5, a 'putAttribute' routine 110, a 'startFrame' routine 115, a 'process Attribute' routine 120, an 'endFrame' routine 125, an 'initContext' routine 130, a 'setAttribute' routine 135, a 'getAttribute' routine 140, an 'upAttribute' routine 145 and possibly other support routines shown generally as 150.
• Each adapter routine 20 is associated with a respective memory context. As illustrated, the first adapter 21 receives an information flow I 21 and is associated with a respective memory context 101. Likewise, a second adapter 22 receives an information flow I 22 and is associated with a respective memory context 102.
• 'checkFrame' routines 60 are also illustrated.
• 'initFrame' routines 70 and 'finishFrame' routines 80 are associated with a respective memory context and adapter pair.
• the first adapter routine 21 is associated with a first memory context 101, a first 'checkFrame' routine 61, a first 'initFrame' routine 71, and a first 'finishFrame' routine 81.
• routines are invoked, the specific routine called depends upon the context. In the case of memory, the hierarchal memory store used also depends on the context.
• the general purpose action routines 30 can also create outgoing information flows I 0 which may then wrap around and be processed through another invocation of the frame processor 12. This is typically accomplished by an action routine 30 invoking the frame processor 12 again in the role of a caller routine.
• the caller routine 51 first invokes an 'initContext' routine 130 to create a new context and associate the various routines, information flows, and memory with that context. A unique identifier for the context is returned to the caller 51.
• the caller 51 then triggers the frame processor 12 and passes the context.
• the frame processor 12 then signals a respective adapter routine 21 which is monitoring an incoming information flow I 21 .
• the adapter routine 21 signals the frame processor 12 with a START OF FRAME or an END OF FRAME or an ATTRIBUTE signal.
• the frame processor 12 Upon receiving a START OF FRAME signal, the frame processor 12 signals the respective 'startFrame' routine 115 passing the context.
• the 'startFrame' routine 115 retrieves the current and new frame names from memory.
• the 'startFrame' routine 115 then invokes a respective 'checkFrame' routine 61 passing the context, the current frame name and the new frame name.
• the 'checkFrame' routine 61 may also call other action routines 30 passing the context, current frame name and new frame name.
• the 'startFrame' routine 115 then makes the new frame the current frame and invokes a respective 'initFrame' routine 71 passing the context, the current frame name and enclosing frame name.
• the 'initFrame' routine 71 may also call other action routines 30, passing the context, current frame name and enclosing frame name.
• the frame processor 12 may then receive an ATTRIBUTE signal from the adapter routine 21. In response to the ATTRIBUTE signal, the frame processor 12 invokes the 'process Attribute' routine 120, passing the context, to store the attribute in memory.
• the frame processor 12 may next receive an END OF FRAME signal from the adapter routine 21. In response, the frame processor 12 invokes the 'endFrame' routine 125 with the context.
• the 'endFrame' routine 125 retrieves the frame name from the memory context and invokes the 'finishFrame' routine 81.
• the finish frame routine 81 is passed the context and frame name.
• the 'finishFrame' routine 81 also invokes action routines 30, passing the name and context.
• the frame processor 12 keeps track of signals. Indeed, the frame processor 12 does not receive any values, only signals. By using context memory the frame processor 12 can be made reentrant and multi-threaded. These and other routines will be described in more detail below.
• the memory context is a hierarchical memory store having a unique identifier. Each memory context matches two stacks: a frame stack and an attribute stack. Each attribute is associated with a frame. In the stacks, the most recently stored and therefore most likely to be needed attributes are at the top of the stack, where they are readily available for processing. If further attributes are needed and they are not supplied with the top frame, the stacks can be scanned from top to bottom to inherit the attribute from below (i.e., an outer frame layer).
• a context has three associated information streams: an input stream, an output stream and an error output stream. It should be noted that context memory 100 is not necessary for the invention, however the use of context memory 100 offers certain advantages.
• This instance of the processing system comprises a formal grammar which, although expressed here in English, can be translated directly into an executable computer procedure by any of several grammar translators such as YACC or BISON.
• words in quotes represent essential elements of the grammar with particular meanings: 1) words that are all capitals represent input signals to the processing engine from the adapter routine; 2) words that are mixed case and begin with a capital are used internally within the processing engine and are derived from the inputs through the rules of the grammar; and 3) words that are mixed case and begin with a lower case letter are routines that are invoked by the frame processor 12.
• a 'FrameList' is: a. a 'Frame' or b. a 'Frame' list followed by a 'Frame'.
• a 'FrameList' is a sequence of frames which may consist of just one
• a 'Frame' is: a. a 'START_OF_FRAME' (execute the 'startFrame' routine) followed by a 'SubFrameList' followed by an 'END OF FRAME' (execute the 'endFrame' routine) or b. a 'START_OF_FRAME' followed by an 'END_OF_FRAME' (execute the 'startFrame' routine then execute the 'endFrame' routine).
• a 'Frame' has a start ('START OF FRAME') and an end ('END OF FRAME') and optionally contains a 'SubFrameList'; routines
• a 'SubFrameList' is: a. a 'SubFrame' or b. a 'SubFrameList' followed by a 'SubFrame' .
• a 'SubFrameList' is a sequence of SubFrames which may consist of just one 'SubFrame'. This rule provides the second level of iteration in the control strucmre of the processing engine 10.
• a SubFrame' is: a. a 'Frame' or b. an 'ATTRIBUTE' (execute the 'process Attribute' routine).
• a 'SubFrame' is either itself a 'Frame' or it is an 'Attribute', in which case the action routine 'processAttribute' is invoked. This rule provides the recursion in the control structure of the processing engine 10.
• FrameList Frame
• the basic embodiment described with reference to FIG. 2 can be supplemented with general purpose action routines that facilitate the processing of frames and their attributes.
• most of these supplemental routines are private, which means they can only be invoked by the processing engine itself.
• One routine is public, which means that non-general action routines may invoke it.
• the invocation of an action routine associated with a frame is referenced.
• There are many ways to perform such an association including: associating all frames with one such routine, using the name of the frame to determine a routine to invoke, using the available attributes of the frame to determine the routine, etc. Making a correspondence between frames and object classes in an object-oriented programming environment is another way to provide the association.
• These routines work with frame names and with attribute names and values; any or all of these items may be complex, i.e., consist of an associated collection of data items, any of which may also be complex.
• the private 'startFrame' support routine 115 first calls a non-general action routine (e.g. 'checkFrame' 61) and passes it two values: the name (if it has one) of current frame and the name (if it has one) of the new frame being started.
• the name of the current frame is derived from the hierarchical memory store of frame names described below.
• the name of the new frame may have been passed from the adapter routine 21 to the processing engine 10 and then to the 'startFrame' routine 115 or it may have been made available in some other way to the routine, but in any case it is provisionally stored in memory at this point.
• the purpose of calling the 'checkFrame' routine 61 is to allow a routine associated with the current frame to be executed prior to the full initialization of the new frame. Such a routine can perform any sort of processing and might typically check the validity of processing the new frame within the current frame. If the 'checkFrame' routine 61 returns an error, then the 'startFrame' routine 115 may cause the new frame to be skipped, including its attributes and any contained frames to any depth.
• the 'startFrame' routine 115 next triggers the permanent storage of the name of the new frame, which then becomes the current frame.
• Frame names are used to dynamically construct a computer memory space that contains the name of the active frame at each hierarchical level.
• the current frame is at the highest level and the lowest level is always occupied by an implicit frame, typically named 'ROOT', which logically contains all the other frames and is present upon initialization of the system and support routines.
• FIG. 4 is a schematic diagram of a preferred embodiment of an initialized memory store.
• the computer memory space comprises a hierarchical memory store of frame names (stack FRAME) privately kept by the general purpose action routines and directly accessible only by them.
• the hierarchical memory store of frame names is associated with a corresponding store of attribute names (stack ATTR) and values as described below.
• the 'ROOT' frame is associated with a null attribute 'NULL', but particular attributes and values may be stored on the ATTR stack and associated with the 'ROOT' frame to be inherited by later frames, as will be described below.
• FIG. 5 is a schematic diagram of a representative memory store of FIG. 4 with data stored therein.
• the memory store of attribute names and values is logically organized as a last-in-first-out stack in such a way that attribute names and values can be accessed sequentially in reverse order (from last in to first out) and such that all the attribute names and values associated with the current frame can be removed from the stack.
• the memory store of attribute names and associated values is privately kept by the non-general purpose action routines and is directly accessible only by them.
• the 'startFrame' support routine 115 then calls a non- general action routine (e.g. 'initFrame' 71) and passes it two values: the name (if it has one) of the new frame, which is now the current frame, and the name (if it has one) of the parent frame.
• the frame names are derived from the hierarchical memory store of frame names described above. The purpose of calling the
• 'initFrame' routine 71 is to allow a routine associated with the current (new) frame to be executed prior to the processing of attributes and/or contained frames. Such a routine can perform any sort of processing and may typically check the validity of processing the current (new) frame within the parent frame. If the 'initFrame' routine 71 returns an error then the 'startFrame' routine 115 may cause the current (new) frame to be skipped, including its attributes and any contained frames to any depth.
• the private 'processAttribute' support routine 120 triggers the storage of the attribute name and associated value in memory associated with the hierarchical memory store of frame names.
• the attribute name and value may have been passed from the adapter routine to the processing engine 10 and then to the 'processAttribute' routine 120 or they may have been made available in some other way to the routine.
• the private 'endFrame' support routine 125 calls a non-general action routine
• FIG. 6 is a schematic diagram of the memory store of FIG. 5 after invocation of the 'endFrame' routine 125. Note that frame F3 and its associate attributes A4, A5 have been popped from the stacks and the current frame is now F2.
• the public 'getAttribute' support routine 140 is typically invoked from a non-general action routine associated with a frame. It expects to be passed an attribute name, then logically scans the stack of attribute names and values in reverse order (from last in to first out) until a matching name is found or until all candidate attributes in the stack have been scanned. If a matching name is found, it returns the associated value to the caller, otherwise it notifies the caller that the attribute was not found.
• the attribute values are logically presented in a hierarchical manner wherein the latest value stored with a particular name is always the one returned, overriding any previous values associated with that name and set at the same frame level or at higher levels.
• This scheme provides for inheritance of attributes by enclosed frames wherein a frame for which the adapter routine did not provide an attribute from the info ⁇ nation flow can inherit that attribute from an enclosing frame higher in the hierarchy and the attribute value provided is always the closest one that is associated with an active frame. Referring again to FIGS. 5 and 6, the attribute A2 associated with frame Fl is overridden by the attribute A2 associated with the more current frame F2. These attributes can have different values.
• Additional support routines also add useful extensions to the basic embodiment described above, enabling the definition of sequences of frames and their processing that can be sufficiently complex as to comprise a family of computer languages.
• the public 'setAttribute' support routine 135 is typically invoked from a non-general action routine associated with a frame. It expects to be passed an attribute name and value and places them in the private hierarchical memory stores shared with the other support routines. Attributes set this way are termed synthetic attributes as they are created by action routines rather than being received in the information flow itself.
• the 'setAttribute' routine 135 stores the attribute in association with the current frame as if it were received from the information flow. The effect of this facility is to provide a way for action routines associated with the current frame to pass information to each other and to enclosed frames via inheritance.
• FIG. 7 is a schematic diagram of the memory store of FIG. 6 after invocation of the 'setAttribute' routine 135. Attribute A6 is placed on the attribute stack (ATTR) and associated with the current frame F2 (determined from FIG. 6).
• the public 'upAttribute' support routine 145 is also typically invoked from a non-general action routine associated with a frame. It too expects to be passed an attribute name and value and places them in the private hierarchical memory stores shared with the other support routines. However, the synthetic attribute thus created is associated with its immediate parent frame, not with the current frame.
• FIG. 8 is a schematic diagram of the memory store of FIG. 7 after invocation of the 'upAttribute' routine 145. Attribute A7 has been placed on the attribute stack (ATTR) and associated with the parent frame Fl . The current frame F2 retains an association with its attributes A2, A6.
• this facility provides a way for action routines to return values up the hierarchy so that they can be retrieved and acted upon by action routines associated with frames at a higher level. Additionally the synthetic attribute can be inherited by downstream frames (frames encountered subsequently in the info ⁇ nation flow) outside of the hierarchical sub-tree headed by the cu ⁇ ent frame.
• this routine provides a general facility for resolving frames into attributes. That is, the frame, and all of its attributes and enclosed frames if any, can be viewed as being replaced in the information flow by synthetic attributes which are set by the action of this routine.
• other useful public support routines 150 or special purpose attributes can make additional facilities available to action routines.
• one class of routines can provide more detailed and/or complete access to the hierarchical memory store, enabling an action routine to walk through the active frames and attributes, possibly retrieving more detailed information about each element.
• Another class of routines or synthetic attributes can provide ways of affecting the processing of frames, e.g. skipping the remaining processing of a frame and its attributes and enclosed frames.
• Another class of routines or attributes can allow a frame or an action routine associated with a frame to disable or modify access to the public support routines by the action routines associated with enclosed frames; this could enable a hierarchically based security scheme in which enclosing frames and their action routines control the privileges of the action routines of enclosed frames.
• An additional class of synthetic attributes can modify the normal retrieval of attribute values, for example a special type of synthetic attribute could nullify or mask the presence of an attribute from any downstream action routine within the scope of the synthetic attribute's associated frame.
• Additional support routines and minor modifications to the other routines further extend the basic embodiment described above such that it can be more compactly implemented, lessens the burden on programmers of action routines, and is fully reentrant and capable of multi-threading, i.e., capable of processing multiple information flows at one time without collision.
• the public 'initContext' routine 130 takes as arguments the information necessary to invoke four non-general routines: an 'adapter' routine 21 , a 'checkFrame' routine 61 an 'initFrame' routine 71, and a 'finishFrame' routine 81; and the information necessary to invoke three information flows: 'input', 'output', and 'error output'. It initializes a new hierarchical memory store (a memory context) distinct from any others and returns a unique item called a context that links together the four routines, the information flows, and the new memory context such that they can be used by other routines. Multiple contexts can be active at once.
• Each general routine and each non- general routine invoked by a general routine receives a context as an argument in addition to any other arguments.
• a new context can be grafted onto an existing context such that the memory store of the existing context appears as an enclosing or a superior memory hierarchy of the new context. Any number of these contexts can exist in parallel, defining a tree-structured memory construct.
• Each thread of execution establishes at least one memory context.
• the core engine manages the trees of memory context in such a way that memory can be safely shared among the executing threads.
• the public 'putFrame' support routine 105 is typically invoked from an adapter routine. It is passed the frame name and prepares the memory context for storage of the name. Similarly, the public 'putAttribute' support routine 110 is passed an attribute name and value and prepares the memory context for their storage.
• the core implementation of the processing engine 10 is simplified because it does not need to receive the names and values, store them internally, and pass them to other routines. This speeds up the execution of the system and reduces its internal memory requirements substantially.
• routines could manipulate contexts.
• a routine could make a copy of the contents of a context, cloning the state of the hierarchical memory store for use in a new context.
• Other routines could be devised to merge memory contexts.
• a preferred processing engine in accordance with the invention provides at least two services based upon multi-threading: automatic "parallel processing" of serial frame sequences and pipelines of frame sequences between threads ("threaded pipes"). Parallel processing occurs automatically when an adapter routine receives a sequence of frames; as each complete frame is received, the general engine dispatches a thread of execution to process the frame and then immediately invokes its adapter routine to obtain the next frame.
• FIG. 9 is a block diagram of a prefe ⁇ ed embodiment of the invention employing parallel processing and pipelining techniques. Illustrated in a calling application 100 for processing information flows from a source 105.
• the application 100 invokes the frame processor 110.
• the frame processor 110 can execute a first TCP adapter 120 and a plurality of TCP action routines 130a, 130b, 130c in parallel.
• the TCP adapter 120 recognizes a TCP request stream from the source 105.
• the acmal protocol is processed by the action routines 130.
• Each action routine 130a can execute a plurality of frame processors 140a, 150a, 160a in parallel to process the frame sequence from the source 105.
• Initial frame processor 140a invokes a second TCP adapter 142a which recognizes the frames from the TCP port. Attributes from the second TCP adapter 142a are fed through a TCP frame processor 140a to a second TCP action routine 144a.
• the second TCP action routine 144a places a sequence of parsed frames in a pipe output 146a.
• the encompassing TCP action routine 130a has, for example, invoked an SMTP frame processor 150a which removes the sequence of frames from the TCP pipe ou ⁇ ut 146a into an SMTP pipe input 152a.
• the sequence of frames are processed by the SMTP frame processor 150a using an SMTP action routine 154a which places a parsed sequence of frames into an SMTP pipe output 156a.
• a MIME frame processor 160a receives the SMTP output in its pipe input 162a.
• These sequence of frames are processed by the MIME frame processor 160a using a MIME action routine 164a.
• additional frame processors can further process the sequence of frames.
• FIG. 10 is a block diagram of a memory construct for the system of FIG. 9.
• a memory store for the application route 210 and the memory store for the first TCP adapter 220 are encompassed by a common memory context 215.
• Each of the TCP action routines 130a, 130b, 130c of FIG. 9 have a respective memory store 230a, 230b, 230c which each have a respective memory context 235a, 235b, 235c as illustrated.
• the TCP frame processor 140a, SMTP frame processor 150a, and the MIME frame processor 160a have a respective memory store 240a, 250a, 260a which are encompassed by a respective memory context 245a, 255a, 265a.
• Control structures for recursion and iteration are some of the most difficult and error prone aspects of computer programming. Multi-threading is likewise very difficult to incorporate into programs.
• the processing engine 10 makes the remaining tasks of developing a computer procedure for processing an information flow much simpler than cu ⁇ ent practice normally allows. Additionally, by facilitating a logical separation of tasks, the use of the processing engine 10 can result in computer programs with highly independent, reusable components. Hence, the processing engine 10 can make it easier to process information flows.
• the processing engine 10 is very regular and compact, it can be implemented in a small and fast computational routine. In preferred embodiments, the processing engine 10 may be significantly faster than the techniques used in the prior art.
• the processing engine 10 is also universal. Typically, several layers of info ⁇ nation flows must be processed within a computer, wherein upper layers are logically or physically encapsulated widiin the layer below them. Similarly, a computer may need to process many information flows in parallel at the same time. In each of these cases or even in the combined case, a single instance of the frame processor 12 can be used as a core process, given appropriate adapter and action routines and utilizing standard techniques for task and memory management. Hence use of the processing engine greatly reduce the complexity of information flow processing in computing by decreasing the number of computational components involved, providing a common architecture and single core process for the remaining components, and simplifying each remaining component.
• the processing engine 10 makes it possible to efficiently harness more complex forms of information flow than cu ⁇ ent practice allows. Because the method encapsulates recursion, it makes it easy for the full recursive power of frames to be used in information flows. This in m adds another dimension to the design of such flows without increasing the difficulty of creating processing routines to handle them. Therefore designers of information flows can put more complexity into their designs because the system can easily be used to process them. For example, the International Standards Organization (ISO) specification of Abstract Syntax Notation 1 (ASN.1) and the Basic Encoding Rules is an extremely powerf l and efficient protocol which has languished because the protocol is difficult to understand and process. The processing engine 10 makes it easier to use this protocol.
• ISO International Standards Organization
• ASN.1 Abstract Syntax Notation 1
• Basic Encoding Rules is an extremely powerf l and efficient protocol which has languished because the protocol is difficult to understand and process.
• the processing engine 10 makes it easier to use this protocol. Example Uses for the System
• a computer program executes in a computer, information is initially passed to it in various forms from the computer operating system and other sources.
• sources may include, but are not limited to, command line arguments, environment variables, configuration files and the results of system calls.
• the main portion of the computer program can be insulated from direct contact with its operating environment and therefore be more easily ported between environments.
• values can be placed on die attribute stack at start-up by associating the values with the 'ROOT' frame.
• the layers can be kept distinct (through different adapter and action routines) but the overall processing can be simplified, made more compact, and speeded up by incorporating the invention in the processing core.
• the computer system operates 2-3 times faster than directly programmed approaches used in the prior art and is about 20-30 times smaller when combined with an embodiment which operates with the operating system.
• Some information flows represent information to be displayed on a screen or to be printed. Special purpose interpreters are typically used to accomplish this rendering.
• the invention can be used to develop more general purpose interpreters with a common core engine if the information flows can be represented as sequences of frames.
• Another example is security encryption, where the technique is naturally processed in layers. Those layers can be expressed as frames which are easily handled by the processing engine.
• the processing engine 10 is sufficiently compact that it can be easily implemented in hardware or firmware. This can make the processing engine very useful for inclusion in any special purpose device that needs to communicate with other devices, including, but not limited to, electronic appliances, machine tools and medical instruments. Additionally, such devices can use the processing engine for processing internal information flows. For example, a printer can use the technique described in the preceding paragraph with a ROM-based implementation of the invention.
• Appendix A attached hereto is a complete frame processor implementation for a simple sample protocol.
• a lexical scanner (lexer) breaks the input protocol into tokens.
• the lexer understands a parentheses-based protocol, an example of which might look like this: (Fl(al vl)(a2 v2)).
• This can be read as 'Frame' instance named 'Fl ' that has two 'Attributes', 'al' and 'a2', whose values are 'vl' and 'v2' respectively.
• Frames can nest, so (Fl(al vl)(F2(a2 vs))(a3 vd)) is valid (also attributes and frames can be mixed in any order at any level).
• the lexer does not need to handle hierarchy, it only needs to recognize the tokens and pass them on to the next procedure.
• This example core engine only deals with symbolic tokens passed by the lexer and not with the protocol itself. Hence the core engine can handle any protocol that conforms to its semantic model, given a suitable lexer.
• the only tokens acceptable to the frame processor are: FRAME TYPE, END OF FRAME, and ATTRIBUTE.
• the frame processor forms a hierarchical strucmre based upon the input from the lexer and maintains internal data structures (stack and heap) that comprise a scoped symbol table of attribute-value pairs. This enables scoped inheritance of attributes by nested frames.
• the 'action' routines consist of 'main', which calls the frame processor (FREDI) after performing any necessary initialization, e.g. , setting STDIN and STDOUT, and has 'callback' routines which the frame processor calls at defined points in protocol processing: when a frame is initialized, when a sub-frame is encountered, and when the end of a frame is encountered.
• the callback routines can access attribute values with a 'get' routine that returns the properly scoped value and then do whatever.
• the action routines are completely independent of the details of the input protocol, insulated by me frame processor.
• Appendix C attached hereto is the source version of a binary library that provides the core frame processing engine for the example of Appendix B.
• the attached version of the source code handles synthetic attributes including the 'upAttribute' facility.
• the engine is nearly reentrant because the static storage requirements have been reduced to about 100 bytes. These 100 bytes can be made part of each context to make the routines reentrant.
• subframes subframe I subframes subframe
• iFrame-H-; asFrameEntry[iFrame].pcAttributes asFrameEntry[iFrame-l].pcAttributes; strcpy (asFrameEntry [iFrame] . aczFrameType, pcz) ; ⁇
• ⁇ PARSE_FRAME_TYPE> ⁇ WORD ⁇ ⁇ yylval.string strdup(yytext); retum (FRAME TYPE); .
• peb_act peb_act.o peb_actl .o peb_act2.o peb_gen.o peb_lex.o libfredi.a
• Fredi-based processors have a simple stmcmre that facilitates the partition of functions into modules that are themselves relatively simple, hopefully decreasing the overall complexity of building and maintaining complex protocol processing programs.
• Fredi views all input as a balanced recursive set of 'frames' and maintains a scoped symbol table to support processing them. Frames have any number of attributes which themselves can be frames. Fredi only deals in 'abstract' syntax; the programmer provides the translation to and from the 'transfer' syntax used 'on the wire'. The programmer also provides the semantic processing.
• the standard fredi routines are encapsulated as a library of functions that require certain 'callback' routines to be provided by the programmer. Thus the fredi routines can be viewed as 'middleware'.
• the programmer also creates a 'generator' routine as well to output the transfer syntax based upon the abstract syntax and semantics.
• the programmer gets from fredi:
• pczFrameType is the cu ⁇ ent (enclosing) frame type
• pczSubFrmType is the new frame type
• frame level is at the cunent
• frInitFrm (char *pczSubFrmType, char *pczFrmType); /* Called after frChkFrmwhen a new frame is encountered;
• pczSubFrmType is the cu ⁇ ent (new) frame type
• pczFrameType is the enclosing frame type
• frame level is at the cunent (new) frame - no attributes will have been set.
• fredi implements simple versions of some routines when only 'string' versions of attributes are of interest. However, fredi can handle arbitrary values up to about 8K (cunently). fredi can handle a pointer as the value of an attribute, so BLOBs should be passed as pointers. Future versions of fredi will do 'garbage collection' on such pointers, but currently the programmer is responsible for deallocating memory.
• Retums 0 normally; retums -1 on the call subsequent to the call in which the last attribute was retumed.
• int frSkipFrm(void); /* Causes fredi to skip to the end ofthe frame, including skipping all contained frames.
• the end of frame routine will be called for the frame. Allows the programmer to 'bail out' if things go bad, e.g. database failure, and may have other uses... */
• Contemplated uses include identifying me starting and next offsets ofthe raw input in a file or buffer such that a raw frame including its contents can be sent transparently somewhere else. Always retums 0 (cunently). The frame is not 'committed' until me lexer returns with
• Updates values in the cunent frame Contemplated to be called when end of frame is reached in order to update values. If any ofthe integer arguments is set to -1 before the call, or if pvsrHndl is set to NULL, then that value is not updated. */
• void sendFrameType (char *pczFrameType); void sendAttribute(char *pczAttrName, char *pczAttrValue); void sendEndOfFrame(void); void sendEndOfContent(void);
• int iAttrNames sizeof(apczAttrName) / sizeof(apczAttrName[0]); int i; char * pczAttrValue;
• frameList frameList frame
• SubFrameList SubFrameList subFrame
• subFrame ATTRIBUTE ⁇ frDoAttrO; ⁇ I frame;
• int frSetAttrBin ( char *pczAttrNm, char *pczAttrValStr, void *pvAttrValBin, int iAttrValType, int iAttrValBinLen, int iAttrStat ) ⁇ psAttrEnt psAttrEntTmp; int iRetum;
• piAttrValType psAttrEntNxt->iAttrValType; -58/ 19-
• pczAttrValStrCpy strcpy(psAttrEntNxt->pczAttrValStrCpy, psAttrEntNxt->pczAttrValStr);
• strcpy (char *)psF ⁇ mEntNew + sizeof(sFrmEnt), pczFrmType);
• frlnitFrm frGetFimType ⁇ sFrmEntTail
• frGetFrmType psF-mEntTail->psFrmEntNxt
• frSetAttrBin ( aczAttrNm, aczAttrValStr, pvAttrValBin, iAttrValType, iAttrValBinLen, iAttrStat

Landscapes

• Engineering & Computer Science (AREA)
• Computer Security & Cryptography (AREA)
• Computer Networks & Wireless Communication (AREA)
• Signal Processing (AREA)
• Computer And Data Communications (AREA)
• Devices For Executing Special Programs (AREA)
• Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
• Communication Control (AREA)

Applications Claiming Priority (3)

Publications (1)

Family

ID=21707600

Family Applications (1)

Country Status (4)

Families Citing this family (1)

Family Cites Families (2)

• 1996
  • 1996-09-13 EP EP96931550A patent/EP0850529A2/de not_active Withdrawn
  • 1996-09-13 JP JP9513475A patent/JPH11512852A/ja active Pending
  • 1996-09-13 WO PCT/US1996/014663 patent/WO1997012339A2/en not_active Ceased
  • 1996-09-13 CA CA002228593A patent/CA2228593A1/en not_active Abandoned

Non-Patent Citations (1)

Also Published As

Similar Documents

Legal Events