HK1082858B - Packet routing via payload inspection and subscription processing in a publish-subscribe network - Google Patents

Description

Packet routing through payload inspection and order processing in a publish-order network

Related reference application

This application is related to the following applications, all of which are incorporated herein by reference, and which may at least be construed as: u.s. provisional application No. 60/312,074 entitled "packet routing via payload inspection", filed on 8/15/2001; U.S. provisional application serial No. 60/312,077 entitled "method and apparatus for content-based routing and filtering in a router using channels", filed on 8/15/2001; U.S. provisional application serial No. 60/312,076 entitled "method of sending and receiving boolean functions over a network" filed on 8/15/2001; U.S. provisional application serial No. 60/312,075 entitled "method for storing boolean functions over a network for assignment, modification, reuse, and transmission," applied for 8/15/2001; U.S. provisional application serial No. 60/329,526 entitled "efficient implementation of wildcard matching over variable-size domains in content-based routing" filed on 10/17/2001.

Technical Field

The present invention relates to a method and apparatus for routing packets in a packet load check-based network core, and a method and apparatus for processing orders in a publish-order network.

Background

Network bandwidth is increasing exponentially. However, the network infrastructure (including routers, servers, daemons, protocols, etc.) still uses relatively old technology. As a result, Internet applications and network routers cannot keep up with the rate of bandwidth development. At the same time, more and more devices and applications are becoming available on the web. The load on the network nodes of these devices and applications grows very fearful. The increase in network load and the number of applications also makes network application implementation and maintenance more complex. As a result, the increase in network bandwidth and the ubiquitous use of network devices and applications can lead to data routing and transmission problems in legacy network infrastructure, particularly when publishing content to an orderer.

One network model that can push information from a server to a client is the publish-order model. In the model, the server becomes a simple publisher of information without regard to which clients may be interested in the information, or where the information is located in the network. As information becomes available to be published, the client becomes the orderer of the information, regardless of the details of where the information is published on the network. The network is then responsible for efficiently routing the published information to the orderer, activating the order by matching the information, and doing all this in a manner that is transparent to both the publisher and the orderer.

Because the complexity of the server is greatly reduced in the publish-order model, the differences between heavyweight servers and lightweight clients begin to disappear, or even merge into a peer concept, either the publisher, the orderer, or both. Most types of applications have a natural affinity for publish-order type interactions between peers. A common theme under many of these applications is that the information that is published and ordered takes the form of events. For example, an investor purchases or sells a stock, resulting in a change in the price of the stock. Traffic accidents occur on highways together, resulting in traffic congestion on highways. A software vulnerability in a software system is discovered resulting in a patch that needs to be developed for the user of the software. In an Internet game, a player fires, causing the avatar of another player to die. All of these examples are events that may be of interest to most orderers and can be propagated over a network notifying those orderers that the event has occurred. Thus, an event is simply a separate, concise message of possible interest that occurs at a certain time and a certain location on the network.

Another example relates to scheduled broadcasts, which have different characteristics than applications that contain only asynchronous events, which means that the time of an event is unpredictable and random. First, the event is scheduled to occur at a time that is well known. An event then need not be compressed information. Instead, it may be large-scale data. Indicating such heavy load data to the portions of the network where interested orderers are found requires substantial work from the server.

Typically, in the publish-order model, the server or publisher performs routing decisions for the network to instruct the network where to send the published content. The publisher stores its order for publishing content. When new content is received or generated, the publisher compares the content to each order to determine a match. If the content (event) satisfies a certain order, the publisher pushes the content to the corresponding orderer via the network. This traditional publish-order model places a heavy burden on publishers, particularly as more devices become available on the network and the number of orderers increases. One complementary approach is quite bad-the orderer evaluates his order on all distribution events.

With the convergence of increasingly unclear applications on the Internet, the possibility of using event notifications becomes endless. However, those possibilities require more efficient methods to make routing decisions and to decide when an event satisfies an order to ease the burden on the publisher. Thus, a generally in-depth, persistent event notification service can provide tremendous value-added benefits to Internet applications and other applications and implementations thereof.

Disclosure of Invention

A first method and apparatus consistent with the present invention provides packet processing in a network. A received packet has a header field and a payload (payload) field. The payload field of the packet is examined at the network core to decide how to process the packet, and the packet is selectively processed based on the examination result.

A second method and apparatus consistent with the present invention provides channel configuration to facilitate content-based routing. The channel provides a logical communication path between a plurality of nodes in the publish-order network. The channel is configured to perform content-based routing of information over the communication path and to select a message format for transmission over the communication path based on the channel.

A third method and apparatus consistent with the present invention provides transmission decisions (prefixes) in a publish-order network. A received expression includes a boolean predicate associated with an order. The expression is encoded as a message for transmission in the network for content-based routing, and the message is transmitted to at least one router in a core of the network for providing content-based routing to an order.

A fourth method and apparatus consistent with the present invention provides order storage for a publish-order network. A structure for storing an order in the network is specified. The structure is divided into a plurality of sub-expressions, and the sub-expressions are used to collectively designate a particular order. A boolean decision is associated with at least one of the sub-expressions of the special order and the boolean decision indicates a notification element for the special order in order to provide content-based routing to the order.

A fifth method and apparatus consistent with the present invention provides packet routing in a network. A received packet has a header field and a payload field. The payload field of the packet is examined to determine how to route the packet using a routing rule that includes a wildcard field size in the payload field, and the packet is selectively routed based on the examination.

Drawings

Together with the description, the drawings serve to describe and explain the advantages and principles of the invention.

Fig. 1 illustrates intelligent routing for a network core.

FIG. 2 is a network diagram illustrating intelligent routers for publishers and orderers.

Fig. 3 illustrates the network infrastructure of an intelligent router and a core router.

FIG. 4 illustrates the hardware components of an intelligent router.

FIG. 5 illustrates a publisher and orderer machine.

Fig. 6 illustrates a channel manager of an intelligent router.

Figure 7 illustrates software components of a user machine interfacing with an intelligent router machine.

FIG. 8 illustrates software components of an intelligent router.

Fig. 9 illustrates a packet structure of one message.

FIG. 10 is a flow diagram of a publisher method.

FIG. 11 is a flow chart of an orderer method.

FIG. 12 is a diagram of a channel and orderer screen.

Fig. 13 is a flow chart diagram of a method of content-based routing.

FIG. 14 is a flow chart of a caching method.

FIG. 15 illustrates caching indexes.

Fig. 16 is a flow chart of a proxy method of outgoing messages.

Fig. 17 is a flow chart of a proxy method of inbound messages.

Fig. 18 illustrates an example of message encoding.

FIG. 19 is a database structure diagram of a stored order.

FIG. 20 is a flow chart diagram of a wildcard method.

Detailed Description

SUMMARY

An Internet-scale or other distributed network-scale event notification system may provide applications through a powerful, flexible implementation of a publish-order network. In the system, an application uses event notification Application Program Interfaces (APIs) to issue notifications, and/or order notifications, and accepts notifications when events occur in the network.

A notification in the system is given a topic, which is a string or other structure, that classifies the kind of information that the notification encapsulates. Also, a notification is completed by a set of attributes that contain details of the notification. For example, an application may use the subject matter to issue a notification about a new york security exchange traded transaction, the subject matter referencing the new york security exchange and attribute symbols and price. The application may issue a personal notification with special attribute values, such as a symbol equivalent to SNE (stock exchange number of sony corporation) and a price equivalent to 85.25. If the attributes in a notification are not all predetermined, then the attributes will be found in all notifications having the same subject family as a result. However, to provide additional detailed event information, the publisher may add arbitrary attributes on a per notification or other basis. Thus, not all, or even any, of the attributes need to be predetermined.

In the system, the orderer is not limited to ordering only the subject or the entire channel. The channels are further explained and defined as follows. They include a hierarchical structure indicating one or more levels such as a topic domain and related sub-domains (sub-topics). In this way, the orderer may provide more interesting fine-tune expressions by specifying a content-based filter (filter) on these notification attributes. For example, an orderer may order a notification that all shares of stocks owned by the orderer are referenced on a topic with a symbol equal to SNE and a price greater than 90.00 (perhaps indicating a sell opportunity for shares of stocks owned by the orderer). All notifications matching the order may be delivered to the orderer through a callback (callback) or other type of function provided by the orderer when registering their order or otherwise. An order may be broken down into multiple filters.

The call back may perform a number of calculations, including simply such as writing a message to a terminal or sending an email, more complicated such as initiating the sale of stock shares, more complicated such as initiating a new publish-order activity (e.g., replacing an existing order with a new order purchased at 75.00, or publishing a new notification that the orderer's portfolio has been revised).

For example, an application gets the help of an agent in its activities of publishing and ordering. These agents may be implemented with or by agents. These agents, when in use, provide network connectivity for the outgoing notifications and orders and send incoming matching notifications to the orderer. Once a notification enters the network, the system's router network propagates the notification to all orderers whose orders match the notification. One implementation is to broadcast the notification to all points of the network and then let the application agents decide whether the notification is relevant to their orderer. However, this is an unnecessarily scalable approach-due to message transport load, the network typically crashes quickly, especially when a large number of active and lengthy publishers are present. And even when sufficient bandwidth is not an issue, the orderer may crash by handling so many notifications.

The typical network of the system is more efficient in its routing of notifications. First, it may use multicast routing to ensure that a notification can be propagated, e.g., at most once on any connection of the network. It can then use a number of optimization methods on the filter to reduce the propagation of notifications as much as possible.

Figure 1 conceptually illustrates the intelligent routing in one network core. A publisher 14 transmits content in messages to a network core 10 for a publish-order network via an edge router 16. A publish-order network includes any type of network that routes data or content from a publisher to an orderer. The content is transmitted via one or more channels 18 representing logical connections between routers or other devices. An intelligent router 12 in the network core 10 determines whether to route or forward the message. In particular, intelligent router 12 may determine whether the message includes the contents of an order placed by an orderer 24.

Each order encapsulates a subject filter and an attribute filter. The router may extend a topic filter to a set of matching topics and incorporate an attribute filter on a per topic basis. An intelligent router evaluates the subject filter and the subject of the notification and evaluates the attribute values in the attribute filter and the notification. The syntax of the topic filter can be in wildcards and the syntax of the attribute filter can be in boolean expressions, both of which are explained in more detail below. The term "filter" is used to describe a set of events that an orderer is interested in receiving from a publisher. Routing rules are generated from the filters and used by the intelligent routers to make routing decisions.

Thus, for example, if the message 26 and the entire set of filters are not satisfied, the intelligent router 12 ends (discards) the message 26, meaning that the message is no longer forwarded. If a message 20 is satisfied by one of the entire set of filters, as evaluated by the topic and attribute filters, the intelligent router 12 routes (forwards) the message 20 according to all routing and/or behavior rules specified for the matching filter, or via the edge router 22 and possibly other devices to the orderer 24, or performs other internal functions of the router 12 with the message 20. This search continues until the entire filter set is exhausted, or all rules are decided upon, whichever comes first.

This intelligent content-based routing at a network core provides real-time data transmission, such as alerts and update data. Examples of real-time data transmission for alerts include, but are not limited to: stock quotes, transactions, news, travel, weather, fraud identification, security, telematics, factory automation, supply chain management, and network management. Real-time data transmission for updates includes, but is not limited to: software upgrades, virucidal updates, movie and music transmission, workflow, storage management, and cache coherency. Many other applications are possible for the transfer of information for orders.

Table 1 illustrates the storage of orders filtered by topic and predicate. They may exist anywhere in the network in any desired or necessary data structure type. These decisions are components of the order, as explained below. Orders may be expressed in any manner, examples of which are provided below.

Table 2 provides an example of a publish-order for a quote server. The examples are provided for illustration only, and an order may include any number and type of parameters for any type of data or content.

These decisions provide boolean expressions for the order and these topics provide an indication of a channel for the order. Orders can be expressed in many different ways. The use of boolean expressions is only an example and provides the ability to easily convert the order to a topic filter and an attribute filter for content-based routing. Alternatively, the presentation order may not specify a topic, but use of a topic or channel (explained further below) may provide an association for interpreting and applying filters to attributes.

Routing decisions can be implemented at the network core and distributed throughout the network, thereby alleviating the processing burden on the publishers and orderer machines and greatly enhancing the efficiency of the network. FIG. 1 illustrates, for purposes of illustration only, one publisher, one orderer, and one intelligent router; implementations may include multiple publishers, multiple orderers, and multiple intelligent routers. The term intelligent router is directed to a router or other entity capable of making routing decisions by examining the payload of a packet or message at a network core or other location.

Network infrastructure

FIG. 2 is a network diagram illustrating intelligent routers for publishers and orderers. As explained below, a routing entity 30 providing channel services is effectively layered over a network infrastructure (ifrasstructure) in order to route messages between intelligent routers. A publisher 32 conceptually includes an application 34 that receives indications of published content, such as a pointer to obtain the content, and an agent 36 that encodes the content for transmission over the network via the channel service 30. The logically interconnected sets of intelligent routers 38, 40, 42, 44, 46, and 48 route the content from the publishers for orders using routing rules generated from the topic filters and attribute filters. The plurality of connections 39, 41, 43, and 45 provide logical connections for the intelligent routers 38, 40, 42, 44, 46, and 48. Other connections 37 and 47 provide logical connections between the publisher 32 and the intelligent router 38, and the orderer 54 and the intelligent router 46, respectively. The order maker 54 includes an agent 50 that checks and receives the content of the order, and an application 52 that presents the content.

For example, a channel may comprise a collection of logically multicast connections implemented in a distributed fashion. A channel in the described embodiment is a logically associated collection of network resources that serve the communication between publishers and orderers to exchange content. The content is categorized according to the channel's topic namespace, and these resources are managed, controlled, and served via the channel service provided by the channel manager. Multiple channels may share the same resources. A channel may provide a high-level directory service, as an example, but not limited to: publisher and orderer information, authentication and authorization information, message type, management information, and billing information. Channels may also provide persistence via caching, fast data distribution mechanisms, security, and user and network management. Channels may be used for other purposes as well.

The filtering by the intelligent router may occur at the network core to distribute routing decisions. In addition, the intelligent router may also act as an edge router, connecting a user device, such as a publisher or an orderer, to the network core. Similarly, the device connected to the network may act as a publisher that pushes content to the orderer via routing decisions of the network, or may act as an orderer that receives pushed content. These intelligent routers and channels may be connected in any configuration as needed or desired for a particular application, and the configuration shown in FIG. 2 is given for illustrative purposes only.

Fig. 3 is a schematic diagram of the network infrastructure of an intelligent router and a conventional backbone router, and fig. 3 also illustrates the logical connections between channels. The intelligent routers in this example use backbone routers already in the network, such as the Internet or other distributed network, and these intelligent routers are effectively layered on the backbone routers. In this example, Internet Service Provider (ISP) networks 58, 59, and 60, each include several backbone routers for conventional routing of messages or packets. A plurality of intelligent routers 61-70 are connected to one or more backbone routers within the ISP networks 58, 59 and 60. The intelligent routers 61-70 are likewise interconnected by a plurality of links 73-85, 73-85 meaning links, and these links may also connect end user devices. The intelligent routers 61-70 may be controlled by one or more administrator machines, such as entity 71, and one or more Virtual Private Network (VPN) controllers, such as entity 72. ISP networks 58, 59 and 60 may also be connected to publisher and orderer machines (not shown in FIG. 3). The backbone routers in ISPs 58, 59, and 60 are interconnected in any conventional manner within the existing network infrastructure.

As shown, the intelligent routers 61-70 and links 73-85 may be implemented using existing network infrastructure, and they provide content-based routing at the network core. These links 73-85 represent logical connections between the intelligent routers 61-70 and may be implemented using existing network infrastructure or other equipment. For example, a link may be implemented using a logical connection called a tunnel. A tunnel comprises hardware and possibly software, network infrastructure for implementing a link, and a tunnel may be a component of multiple channels. These channels provide a logical structure for specific types of content and then provide associations for attributes transmitted on these channels, facilitating content-based routing in intelligent routers. While the intelligent router may make routing decisions without channels, these channels facilitate efficiency of content-based routing by the intelligent router in the network core.

This embodiment includes the use of channels and links. A link is a connection between two routers (albeit intelligent routers). A channel is a network entity comprising a (usually large) set of routers, statically or dynamically configured by interconnecting links to achieve one-to-many or many-to-many logical connections. In particular, a channel is an upper logical entity that describes the basic characteristics of the channel. There may be multiple themes under a channel. Each topic will form a subnet (e.g., a multicast tree) that includes a collection of interconnected routers. These topic-based subnets may be assigned, adapted, and configured in different ways. The channel, the set of all sub-networks under which the topic is formed, resembles a grid (mesh) of networks.

Fig. 4 is a hardware component diagram of an intelligent router 92, consistent with any other intelligent router for reference. One network node 90 may include an intelligent router 92 connected to a conventional backbone router 95. The intelligent router 92 includes a processor 93 coupled to a memory 94 and a secondary storage 97 (e.g., which may be implemented as a separate machine), any of which may store data, may also cache data, and store applications for execution by the processor 93. Secondary storage 97 provides stable data storage. Under software control as explained below, the processor 93 provides instructions to the backbone router 95 to route (forward) or not route (drop) messages or packets based on the routing rules for the orders generated from the topic and attribute filters. Although this is shown as being implemented in a separate processor controlled device, alternatively, the intelligent router 92 may be implemented in an Application Specific Integrated Circuit (ASIC) in the backbone routing 95, possibly with embedded software to provide intelligent routing functionality in hardware. These intelligent routing functions may alternatively be implemented in one or more routing devices using a combination of software and hardware.

FIG. 5 is a diagrammatic view of a publisher and orderer machine. One publisher machine 100 or 118 may include the following components: a memory 102 stores one or more publisher applications 104 and a broker application 105; a secondary storage device 112 providing stable data storage; an input device 108 for inputting information or commands; a processor 114 for executing applications stored in the memory 102 or received from other storage devices; an output device 110 for outputting information; and a display device 116 for providing a visual display of information.

An order maker machine 122 or 140 may include the following components: a memory 124 storing one or more applications 126 and a proxy application 128; a secondary storage device 130 providing stable data storage; an input device 132 for inputting information or commands; a processor 134 for executing applications stored in memory 124 or received from other storage devices; an output device 136 for outputting information; and a display device 138 for providing a visual display of information. The publisher and orderer machines may include more or fewer components, or different components, and be configured in any configuration.

The publisher machines 100 and 118 and the order placer machines 122 and 140 are connected via the network 120 as described above. Network 120 includes intelligent routers that provide distributed routing of data or content through packets or messages within a network core. Although only two publisher and orderer machines are shown, network 120 may include more publisher and orderer machines. These publisher and orderer machines may be implemented using any processor-controlled device, such as, but not limited to, the following: a server; a personal computer; a notebook computer; a personal digital assistant; a telephone; a cellular telephone; a pager; or other device. The intelligent router-enabled network 120 may include any wired or wireless distributed network, with wired devices, wireless devices, or both. Network 120 may also potentially use existing or legacy network infrastructure.

Fig. 6 is a schematic diagram of a channel manager 150 for an intelligent router. In the example, the channel manager 150 is implemented with a plurality of servers 152, 154, and 156. Each server includes its own local storage 158, 160, and 162. The intelligent routers 164, 166 and 168 contact the channel manager to obtain information about the particular channel. The channel manager may also provide data persistence, deactivation functions, or other functions. The channel manager provides channel services including such details as a database or collection of databases anywhere in the network, information related to the channels, characteristics of data persistence, publisher and orderer user information, and infrastructure information. The infrastructure information includes, for example, the identity of an intelligent router and its associated tunnel, the subject of the channels, and the attributes of the channels (one name and type for each attribute). The packets or messages may also carry information relating to the channel, including identification of fixed and variable attributes.

A user may download channel information while online. For example, a user may register using a username and password. When a user is authenticated for logoff, the user may open (invoke) a channel and obtain information for the channel from the channel manager. The publisher may use this information when publishing content, and the orderer may use this information for entering and registering orders.

In the example, each channel manager 152, 154, and 156 acts as a preference for each intelligent router. Specifically, each intelligent router in this example has two IP addresses, one for the preferred channel manager and one for the backup channel manager. These intelligent routers use those IP addresses to contact the manager and obtain channel information. When the preference fails, the intelligent router contacts the backup channel manager. The channel managers 152, 154, and 156 share data, as indicated by the lines connecting them, concerning channel attributes and other information. Each channel manager also has a designated backup so that once the channel manager fails, the other can take over his processing. The devices in the network may use commands to obtain channel information, an example of which is given in table 3. Alternatively, the intelligent router may have only one primary channel manager, or more than two channel managers.

Fig. 7 is a diagram of software components in a stack 180 in a user machine or device connected to a network having an intelligent router. The user machine may act as a publisher, an order maker, or both, and it may include the example devices identified above. The stack 180 may include one or more user applications 182 that may receive orders from a user, channel information from a publisher, or published content or data. The user applications 182 may also include any other type of application executed by a user machine or device.

The stack 180 may also include an agent 184, an event library 186, a cache library 188, a channel library 190, a message library 192, and a sender library 194. The agents 184 are used to establish network connections or other functions and table 3 gives an example of commands implemented by the agents 184, which may use agent commands or other types of commands. The event repository 186 records events, or other events or information, associated with a user machine. The cache library 188 provides local data caching. The channel library 190 stores identification and other information of channels. The sender library 194 gives connectivity to a control path 196, a channel manager 198, and one or more intelligent routers 200, and it may include the exemplary functions indicated in table 4. The message store 192 provides a connection to a data path 204.

Tables 5-9 give examples of message Application Programming Interfaces (APIs) in the C programming language. Tables 5 and 6 give examples of APTs for send and get messages. Tables 7 and 8 give examples of APIs for sending and retrieving notifications. Table 9 gives examples of APIs for sending and retrieving control messages. These APIs and other APIs, programs, and data structures in this description are given only as examples of specific functions or features that may be implemented in any type of APIs or other software entities in any programming language.

TABLE 5
	API example for sending a message
PC_Status PC_msg_init(ChannelHandle ch，PC_UNIT chld，PC_UNIT userid，PC_TypeInfo*MsgType，PC_UNIT msgTypeSize，PC_msg_SessionHandle*sess)；PC_Status PC_msg_cleanup(PC_msg_SessionHandle sess)；PC_Status PC_msg_closeTransport(PC_msg_SessionHandle sess)；PC_status PC_msg_create(PC_msg_SessionHandle s，PC_msg_DataType dType，PC_msg_MsgHandle*msg)；PC_status PC_msg_delete(PC_msg_MsgHandle msg)；PC_status PC_msg_clone(PC_msg_MsgHandle org，PC_msg_MsgHandle*new)；

PC_status PC_msg_setSubject(PC_msg_MsgHandle msg，PC_char*subject)；PC_status PC_msg_setSubjectint(PC_msg_MsgHandle msg，PC_USHORT*subjectArray，PC_UNIT arraysize)；PC_status PC_msg_setAttrByNameInt(PC_msg_MSGHandle msg，const PC_char*name，PC_INT value)；//for each typePC_status PC_msg_setAttrByPosInt(PC_msg_MsgHandle msg，PC_UNIT attributePos，PC_INT Value)；//for each typePC_status PC_msg_addAttrInt(PC_msg_MsgHandle msg，const PC_char*name，PC_INT value)；//for each typePC_status PC_msg_send(PC_msg_MsgHandle msg)；

TABLE 6
	API example for obtaining a message
typedef struct_attribute{PC_char *name；PC_TypeCode type；void *value；PC_UNIT arraySize；}PC_msg_Attribute；typedef struct_attributeArray{PC_UNIT size；PC_mas_Attribute**attrs；}PC_msg_AttributeArray；PC_Status PC_msg_init(ChannelHandle ch，PC_UNIT chld，PC_UNIT userid，PC_TypeInfo*MsgType，PC_INT msgTypeSize，PC_msg_SessionHandle*sess)；PC_Status PC_msg_cleanup(PC_msg_SessionHandle sess)；PC_Status PC_msg_recv(PC_msg_SessionHandle sh，PC_msg_MsgHandle*msg)；PC_Status PC_msg_ctrlRecv(PC_msg_SessionHandle sh，PC_msg_MsgHandle*msg)；PC_Status PC_msg_getSequenceNum(PC_msg_MsgHandle msg，PC_UINT*seqNo)；PC_Status PC_msg_getPublisherInfo(PC_msg_MsgHandle msg，PC_msg_PublicInfo*pub)；PC_Status PC_msg_getSubject(PC_msg_MsgHandle msg，PC_char**subject)；PC_Status PC_msg_getSubjectInt(PC_msg_MsgHandlemsg，PC_USHORT**subjectAIray，PC_INT*size)；PC_Status PC_msg_getDataType(PC_msg_MsgHandle hMsg，

PC_msg_DataType*dataType)；PC_Status PC_msg_getAttrByPosInt(PC_msg_MsgHandle msg，PC_UINT pos，PC_INT*val)；//for each typePC_Status PC_msg_getAttrValueByNameInt(PC_msg_MsgHandle msg，const PC_char*name，PC_INT*val)；PC_Status PC_msg_getAttrTypes(PC_msg_MsgHandle msg，PC_TypeCode*Types，PC_INT*arraySize)；PC_Status PC_msg_getAttributeByPos(PC_msg_MsgHandle msg，PC_UINT attributePos，PC_msg_Attribute**attr)；PC_Status PC_msg_getAttribiiteByName(PC_msg_MsgHandle msg，const PC_char*name，PC_msg_Attribute**attr)；PC_Status PC_msg_getPredefinedAttributes(PC_msg_MsgHandle msg，PC_msg_AttributeArray**attrs)；PC_Status PC_msg_getDiscretionaryAttributes(PC_msg_MsgHandle msg，PC_msg_AttributeArray**attrs)；Void PC_msg_freeAttribute(PC_msgAttribute*attr)；Void PC_msg_freeAttributeArray(PC_msg_AttributeArray*attrArray)；

TABLE 7
	Example API for sending a notification
ChannelHandle ch；PC_msg_MsgHandle msg；PC_msg_SessionHandle sh；PC_msg_TypeInfo Types[2]；Types[0].type＝PC_STRING_TYPE；Types[0].name＝″company″Types[1].type＝PC_INT_TYPE；Types[1].name＝″stockvalue″PC_msg_init(ch，chld，userld，Types，2，&sh)PC_msg_create(sh，PC_MSG_DATA，&msg)；PC_msg_setAttrValueByNameInt(msg，″stockvalue″，100)；PC_msg_setAttrValueByPosString(msg，1，“PreCache”)；PC_msg_addAttrString(msg，″comment″，″mycomments″)；PC_msg_send(msg)；PC_msg_delete(msg)；PC_msg_closeTransport(sh)；

PC_msg_cleanup(sh)；

TABLE 8
	API example for receiving a notification
ChannelHandle ch；PC_msg_MsgHandle msg:PC_msg_SessionHandle sh；PC_msg_TypeInfo Types[2]；PC_msg_AttributeArray *attrArray；PC_char*company；PC_INT value；Types[0].type＝PC_STRING_TYPE；Types[0].name＝″company″Types[1].type＝PC_INT_TYPE；Types[1].name＝″stockvalue″PC_msg_init(ch，chld，userld，Types，2，&sh)；While(1){PC_msg_recv(sh，&msg)；PC_msg_getAttrValueByPosStrmg(msg，0，&company)；PC_msg_getAttrValueByNameInt(msg，″stockvalue″，&value)；PC_msg_getDynamicAttributes(msg，&attrArray)；PC_msg_freeAttnbuteArray(attrArray)；PC_msg_delete(msg)；}PC_msg_closeTransport(sh)；PC_msg_cleanup(sh)；

Fig. 8 is a schematic diagram of software components 210 of an intelligent router such as those described above and the intelligent router 92 shown in fig. 4. The software components 210 may be stored in the memory 94 for execution by the processor 93 within the intelligent router 92. Components 210 include a filter daemon 212, a transmitter 214, a routing daemon 216, and a cache manager 218. The filter daemon 212 provides filtering for content based routing, processing content for orders according to routing rules, as will be explained below. The transmitter 214, which gives control message communications such as those needed to propagate filters via path 220, may also provide the user with a login point and a secure socket (socket) with a channel manager to enhance network security. In other words, in this example, the user is not directly connected to the channel manager, but is switched to another implementation. The sender 214 obtains attributes (name-value pairs) from a channel manager using control messages.

The routing daemon provides communication with the data path 222, which may occur via a conventional backbone router or other routing device as shown in fig. 4. The cache manager 218 provides local data caching on the network nodes that contain the respective intelligent routers. The operation of the cache manager 218 is explained further below, and it may provide distributed caching of data throughout the network core.

Content-based routing may be implemented at the kernel level as an alternative to implementation at the application level. Separation of the kernel-accessible memory and application-layer access. To run content-based routing in the application requirements, message data is copied from the kernel storage area to the application area, and the context of the application is exchanged from the kernel to the routing application. Both of which result in substantial overhead. If instead the kernel is modified to support content-based routing, the routing occurs faster than the overhead described above.

Due to the described features of content-based routing in the kernel, the routing daemon 216 may or may not be able to send or receive data directly via data path 222, but rather is implementation dependent. The daemon is a process running at the application layer, pre-computes the content-based routing table, and then injects it into the kernel. Once injected, however, the routing table may be used by the core to make routing decisions. Similarly, the filter daemon precomputes the filter table and then injects it into the kernel. In the kernel implementation, neither the routing daemon nor the filtering daemon directly interact with the data path.

Fig. 9 is a diagram of a packet structure 230 of a message, possibly including the contents of an order. A packet or message for content-based routing includes a header field and a payload field. The header field indicates routing or other information. The payload field indicates data or content, or an indication of said data or content. The packet structure 230 includes an IP header 232, a User Datagram Protocol (UDP) Transmission Control Protocol (TCP) header 234, a length value 238, one or more subject fields 240, and one or more attributes 242. The package structure 230 illustrates a length value and the underlying structure of the subject and the attributes. A packet for use in content-based routing may also include other or different elements, such as those shown below in the example of fig. 18, and the packet for content-based routing may be configured in any manner. Also, the attributes may include any attribute attached to the end of the message. These arbitrary attributes are special information that is added by the publisher (or even the router) and need not be transmitted in the message format described above for the channel.

Publisher and orderer method

Fig. 10 is a flow diagram of a publisher method 250 for a publisher to set up a channel and publish content. For example, the method 250 may be implemented in a software module, including the broker 106, executed by the processor 114 of the publisher machine 100. In method 150, the broker 106 in the publisher machine receives a creation of a publisher as a broker for a channel (step 252). The agent provides network communications. The proxy 106 determines a message format for the channel via an interface (step 253), and the format information may be obtained from, for example, the channel manager or other entity in the network. The proxy 106 uses the received channel information to set up a proxy for the channel (step 254), which includes receiving attributes of the channel (step 256), and creating a notification on the channel (step 258). The notification provides content to a device listening to the content on the channel. The attributes define parameters and characteristics for the notification.

The agent 106 transmits the Identification (ID) of the channel and content information to an intelligent router in the network core or elsewhere for processing the order (step 260). The publisher assigns the attributes of the notification with appropriate values (step 261) and the publisher publishes the content on the notification, consistent with the attributes of the channel (step 262). Step 260 and 262 in this example accomplish the issuing of the notification, and alternatively, different or additional steps may be included depending on the particular implementation. Thus, the information associated with a notification in this example is divided into an ordered sequence of attributes, each having a name, a location in the notification (starting with 1), a type and a value. Alternatively, the attributes may have different characteristics depending on the particular implementation. For example, the attributes may include predefined attributes, discretionary attributes, or both.

The intelligent router may use the channel ID in a packet to derive attributes for the corresponding channel that determine the structure or format of the packet transmitted via the channel. In particular, each package may contain a header tag associated with a channel ID and other information such as publisher ID and subject. These tags can be used to map a topic to a number in the message format, an example of which is shown in FIG. 18. Small integer values, such as 16-bit values, may be used for these numbers. Alternatively, any other type of number or information may be used to map these topics. Mapping topics to numbers may provide particular benefits; for example, it may save space in the message format and provide a uniform or standard way to specify topics within messages so that they can be quickly located and identified. The intelligent router may store the mapping locally or, alternatively, use the numbers to retrieve the corresponding topic remotely by a command.

Table 10 illustrates one structure for mapping numbers to topics, in this example using integer values. The theme tree parameters in the table indicate that a theme can comprise one or more theme domains to form a hierarchical relationship; for example, a topic tree may include a string of topic fields, bounded by special symbols. An example of a subject tree is given in table 2. As an example, a topic tree quote. nyse includes a topic "quots" and a sub-domain "nyse", both parts being separated by a ". multidot.. In addition to using periods and strings that specify the type of URL, the subject tree may be specified in any way, using any characters and symbols as delimiters.

Thus, knowing the packet format or structure for a particular channel, the intelligent router can quickly locate topics and attributes, or other information, in the packet for content-based routing. For example, a channel may specify the byte position of the subject and attributes transmitted on the channel, which may be conveniently located by computing the bytes in the package. Alternatively, the intelligent router may analyze the package to locate topics and attributes. Or other information.

Table 11 gives an example of a publisher program written in the C + + language. Table 12 gives an example of an API for creating a channel. Table 13 gives an example of a channel profile maintained by a channel manager (see fig. 6) and gives information about the channels. Alternatively, the system may have a global channel manager that provides IP addresses for geographically distributed servers that can share the processing burden as local channel managers.

TABLE 11
	Publisher program example
#include“PC_evn_Notification.h”#mclude″PC_evn_Proxy.h″using namespace precache::event；int main(int argc，char argv[]){PC_UINT QuotesRUs＝myChannelofInterest；//channel IDPC_UINT myID＝myPublisherID；//publisher IDtry{

Proxy p(QuotesRUs，myID)；Notification nl(p，″quotes.nyss″)；nl.SetPredefinedAttr(“symbol”，″LUS″)；nl.SetPredefinedAttr(“price”，95.73)；p.Publish(nl)；Notification n2(p，″quotes.nyse″)；n2.SetPredefinedAttr(1，″SNE″)；//attribute symbol is in position 1n2.SetPredefinedAttr(2，80.18)；//attribute price is in position 2p.Publish(n2)；}catch(InvalidChannelException icex){cerr＜＜″bad channel″＜＜endl；}catch(InvalidSubjectException isex){}catch(InvalidNotificationException inex){cerr＜＜″bad notification″＜＜endl；}catch(Exception ex){cerr＜＜′″unknown error＜＜endl；}}

TABLE 12
	API example for creating a channel
PC_Status rc；rc＝PC_chn_create(Provider_info，authinfo，ConfigurationFile，&hChannel)；

/*the first one primary channel manager*/rc＝PC_chn_addChannelManager(hChannel，″10.0.1.1″)；/*secondary channel manager*/rc＝PC_chn_addChannelManager(hChannel，″10.0.2.2″)；*/rc＝PC_chn_setProperties(hChannel，ConfigurationFile)；/*Set the message type(only in fixed part of the message)by using rc＝PC_chn_setAttributeType(hChannel，name，position，attributeType).The type information is propagated to all edge routers.*/rc＝PC_chn_setAttributeType(hChannel，“Priority”，1，PC_UINT16JTYPE)；rc＝PC_chn_setAttributeType(hChannel，“Alarm_Name”，2，PC_STRING_TYPE)；rc＝PC_chn_setAttributeType(hChannel，″Alaim_Time″，3，PC_INT32_TYPE)；rc＝PC_chn_updateAttribute(hChannel)；rc＝＝PC_chn_close(hChannel)；/*finish channel creation*/

Watch 13
	An example of a channel profile
#Channel Setup-Read by Channel API，event and messaging#Each channel entry information is tagged with the#type of information e.g.#[ChannelComm 5]for Channel 5 Communication relatedinformation#[ChannelSubjects 5]for subject related information in channel 5#[ChannelAttributes 5]for attribute information in channel 5#

#The Channel id is appended to the tag to indicate#the channel that the information belongs to#e.g.[ChannelComm 5]indicates routing information#for channel 5.##All the fields need not be set.For example if#running with the central server，the MulticastIP is#not needed.[ChannelComm 5]MulticastIP＝225.0.0.1RouterIP＝test3RouterPort＝12345ProxyPort＝9015ProxyCtrlPort＝9016[ChannelSubjects 5]NumberOfSubjects＝2subjectl＝#.SUBSCRIPTIONmappmgl＝0.100subject2＝Quotes.Nysemapping2＝102.101[ChannelAttributes 5]NumberO￡Attributes＝4name1＝StockIdtypel＝PC_UINT_TYPEname2＝＝Companytype2＝PC_charARRAY_TYPEname3＝Pricetype3＝＝PC_FLOAT_TYPEname4＝＝Volumetype4＝PC_UNIT_TYPE

FIG. 11 is a flow chart of an orderer method 264 for receiving and processing orders. The method 266 may be implemented, for example, as a software module including the agent 128 executed by the processor 134 in the order maker machine 122. In method 264, a Graphical User Interface (GUI) presents the user with an indication of the available channels (step 266), which may be accomplished by application 126. Information identifying the channel may be received from, for example, a channel manager that provides channel-related information. Any type of application 126 may present the identification of the channel in any particular method or format. The application receives a channel selection from a user (step 268) and invokes an API or other program for the selected channel (step 270). The API displays the order option for the channel corresponding to the selected item to the user (step 272). The API receives the order value from the user (step 274) and sends the order to the agent 128 for processing, as explained below (step 276).

The parameters of the order may include decisions such as those illustrated in table 1. Each channel uses its own API in order to process the order according to the particular requirements or parameters of the corresponding channel. These APIs may include web-based or Java-based APIs, such as those used to receive orders, and may use any type of user interface and process to receive order information and pass it to the agent application.

FIG. 12 is a conceptual illustration of channel and orderer screens or GUIs 278 and 284 that may be used with method 264 to receive an order. Screen 278 includes a plurality of sections 282 identifying one of the possible channels that the user may select. When a particular channel is selected, screen 284 is shown accepting a user's order value in a section 286. A user may select a portion 288 to submit an order or a portion 290 to cancel an order. Screens 278 and 284 may be web pages formatted in hypertext markup language (HTML) or any other form. Also, the screen may include any portion or configuration of content, for example, text, graphics, pictures, colors, or multimedia information, in order to provide a user-friendly and visual, attractive interface to the ordering party. The screen may also include a toolbar 280, providing, for example, conventional browsing functions.

Table 14 gives an example of an orderer program written in the C + + language.

TABLE 14
	Example orderer procedure
#include<unistd.h>#include<iostream>#k c.jde“PC_evn_Filter.h”#include″PC_evn_Subscription.h″#include“PC_evn_Proxy.h″

using namespace precache::event；class SubscriberApp:public Subscriber{private:PC_UNIT notificationCount＝0；public:SubscriberApp(){}？？default constructorvoid run()){PC_UNIT QuotesRUs＝myChannelofInterest；//channel IDPC_UINT myID＝myPublisherID；//publisher IDtry{Proxy p(QuotesRUs，myID)；FilterFactory*factory＝FilterFactory::GetFilterFactoryO；Filter* f＝factory-＞CreateFilter(p，“symbol＝\”LU\””)；PC_INT cl＝0；SubscriptionHandle sh＝p.Subscribe(“quotes.nyse”，f，this，(void*)&cl)；while(notificationCount＜2){//let notifyO get some notificationssleep(5)；}p.Unsubscribe(sh)；}catch(InvalidChannelException icex){cerr＜＜“bad channel”＜＜endl；}catch(InvalidSubjectException isex){cerr＜＜“bad subject”＜＜endl；}catch(InvalidChannelException ifex){cerr＜＜″bad filter″＜＜endl；}catch.(InvalidSubscriptionHandleException ishex){cerr＜＜″bas subscription handle″＜＜endl；}catch(Exception ex){cerr＜＜“unknown error”＜＜endl；}}void Notify(Notification*n，void*c)//this is the callback method

{if(*(PC_INT*)c＝＝0){//check the closure objectPC_STRING symbol；PC_FLOAT price；n-＞GetPredefinedAttr(“symbol”，symbol)；n-＞GetPredefinedAttr(″price″，price)；cout＜＜″The price of″＜＜symbol＜＜″is″＜＜price＜＜endl；；notificationCount++；}}}；int main(int argc，char argv[]){SubscriberApp a；a.run()；}

Content-based routing via payload inspection and channel

Fig. 13 is a flow diagram of content-based routing via payload inspection method 300. The method 300 may be implemented in a software module executed by the processor 93 in the intelligent router 92, as described by the filter daemon 212. Alternatively, it may be implemented in an ASIC, or in a combination of hardware and software. The content-based routing illustrated in method 300 may be performed in an intelligent router anywhere in the network, such as in a network core or in an edge router.

Typically, content-based routing involves examining the payload field of a packet to determine how to process the packet. Such content-based routing methods may include processing an order table (e.g., using filters), subject to subject, and attribute to attribute comparisons, a message and routing rules, such as in any order, to determine routing of the message, and performing the processing in a network core. These rules may include rules governing the internal processing of the router or any rules associated with a filter. In this way, these routing decisions may be distributed throughout the network core. The use of the theme of the channel representation determines the format of a message and thus provides an intelligent router with a way to quickly locate attributes within the message, for example by knowing their byte position within a message or packet for a particular channel.

In the method 300, the intelligent router 92 receives a packet of messages (step 302). It determines the channel ID of the corresponding message from the packet (step 304) and acquires the attribute of the channel using the channel ID (step 306). In this example, the type of channel (as determined by the channel ID) determines the location of the attributes within the package. These attributes for a channel may be stored locally or obtained remotely, such as via a channel manager. The intelligent router 92 obtains a filter that corresponds to an order (step 308). The filter includes one or more attribute tests, typically a set of attribute tests for an order. The intelligent router 92 applies the attributes in the package to the corresponding test set of attributes in the filter description (step 310).

If all of the attribute tests in the filter description yield positive results (step 312), meaning that these attributes satisfy all of the attribute tests, the intelligent router executes a set of functions specified by the rules associated with the filter (step 314). These functions may include, for example, routing the packet to the next link and/or performing certain actions or calculations with the contents of the packet as specified by the rules at the local router. The action or next link may be identified in a data structure that specifies the corresponding order. When the rule is a link, it typically identifies the next network node to receive the packet, which may include an intelligent router, backbone router, a network connection device, or other entity. Alternatively, the next link may be indicated in other ways or related to the order.

If all of the attribute tests in the filter description fail to produce a positive result (step 312), meaning that these attributes fail to satisfy all of the attribute tests, the filter is declared to be unmatched (step 315). The intelligent router recursively performs the above until all the attribute tests in the filter are exhausted, or a first negative result is encountered, whichever comes first.

Once all the attribute tests of the filter have been processed, the intelligent router determines whether more routers are present (step 316), and if so, returns to step 308 to obtain the next set of attribute tests for the filter to process the attributes. The matching process continues (steps 308, 310, 312, 314, 315, and 316) until each filter is exhausted, or the results of all actions or routing rules can be determined, whichever comes first. If the packet fails to satisfy either filter, it will be finished (dropped) and not passed forward.

The intelligent router 92 may be ordered through the filters in any particular order. For example, as shown in Table 15, the intelligent router may store filters for orders in a file or routing table and linearly order them to apply attributes to the filters (attribute test set). Alternatively, the routing table may include links or pointers to the filters.

The content-based routing may optionally use more than one method simultaneously, depending on the application and performance enhancement heuristics, such as traffic condition-based switching algorithms. The filters used for processing may be optionally encrypted, decrypted, transmitted and combined at a router in the network to perform inspection of the payload field of content-based routing. For example, an order such as price > $3.54122 may be truncated to price > $3.54 because it is known that the release in the application does not contain the circulation attribute after the last two decimal places. Similarly, foreign currency may be converted to U.S. currency, for example, when a publication sent overseas arrives at the first router located in the U.S.

As an alternative to the linear approach, the intelligent router 92 may select filters to process in other orders, or according to different algorithms, which may increase the speed and efficiency of the processing. Table 16 gives examples of orders and their corresponding links; in these examples, the topic is associated with a particular channel and the order for the topic may be represented by the routing rules of the filter. The topics may include network addresses such as Uniform Resource Locators (URLs) that specify a source of the content.

Network node caching

FIG. 14 is a flow chart of a caching method 320. The method 320 may be implemented in a software module executed by the processor 93 of the intelligent router 92, as shown by the cache manager 218. Alternatively, it may be implemented in an ASIC, or in a combination of hardware and software, and may be the same or a different physical device than the corresponding intelligent router. In method 320, the intelligent router 92 receives a message with data and content, a channel ID, and a topic (step 322). The intelligent router 92 time stamps the data (step 324) and caches it locally, such as the memory 94 or the secondary storage 97 (step 326). It indexes the cached data with the channel ID, topic, and timestamp (step 328).

If the intelligent router 92 receives a request for data (step 330), it uses the index to retrieve the cached data based on the request (step 332). The intelligent router 92 transmits the cached data to the backbone router 95 or other routing entity as a final transmission to the requester or others. Method 320 may be repeatedly performed for continued caching of data and retrieval of cached data in response to corresponding requests.

Fig. 15 is a diagram of the method 320 for creating a cache index (336). The cache index (336) receives data (338) and stores (340) in time stamps. As the data is collected, it is labeled with each interval δ t, where δ t represents the time between two markers, e.g., t₂-t₁. Alternatively, an index type that is time stamped in any other manner may be used.

Table 17 conceptually illustrates an index of cached data. Table 18 conceptually illustrates a data structure that stores a connection history for a cache. Table 19 provides an example of a data structure for caching data locally at a network node having an intelligent router.

The time stamps may occur at any fixed or variable time interval. For example, data may be cached and indexed once every five minutes. When a command is received to retrieve cached data for a specified time and subject (e.g., # getCache), the channel manager 218 uses the cache index to determine if it can retrieve the cached data corresponding to the request, see step 332.

Each topic or channel may include its own IP address in the multicast tree, as well as a set of intelligent routers. Thus, table 18 represents the connection history between these routers, which may be stored in the local user machine; if an edge router fails, the machine can access the connection history to decide how to go back up, reconnecting the router for that channel when the edge router comes back online. For example, it may also disconnect for a period of time and execute a get cache command to get any pending content for the order.

Watch 19
	Example of a cache data Structure for an Intelligent Router
Channel node
	Struct ChannelNode{PC_UINT unChanld；PC_AttributeInfo *pAttdnfo；

PC_BOOL bPersistent；/*Persistent or RT*/PC_UINT unTimeout；PC_UINT unTimeGranularity；/*in minutes*/PC_INT nDirFd；HashTable *pFirstLevelSubjs；}
	Topic node
Struct SubjectNode{PC_USHORT unSubjectld；PC_UINT unSubjLevel；Void pParent；/Channel or Subject*/PC_INT nDirFd；HashTable *pNextLevelSubjs；DataNode *pData；}
	Data node
Struct DataNode{PCJNT nDirFd；SubjectNode *pParent；LastTimeGrainNode *pLastTGrainData；DLIST *pStoredData；/*list StoredTimeGrainNode*/PC_Mutex mStoredDataLock；}
	Storage time granularity node
Struct StoredTimeGrainNode{PC_UINT unStartTime；/*in minutes*/Chanld；PC_UINT unEndTime；/*in minutes*/PC_INT nFd；}
	Final time granularity node
Struct LastTimeGrainNode{PC_char pLastTGrainData；/could be a list*/PC_UINT unLastTGrainStartTime；PC_BOOL bReadyTo Store；

PC_Mutex mCachedDataLock；}

These exemplary data structures include this information. A subject node contains a subject identifier, a subject layer, a pointer to a parent channel or subject node, a file descriptor for its own directory, a hash table pointer containing its next layer of subject nodes, and a data node pointer. A data node includes a pointer to its subject parent, a file descriptor for the data directory, a circular buffer containing data structures for storing data on each storage device, the head and tail of the buffer, and a lock to lock the data node during retrieval and storage. The storage time granularity (grain) node is a node representing a real data file, and the final time granularity node represents a final buffer that is not yet stored to the storage device but remains in the memory. In this example, the cache and data storage threads use mutual exclusion of the final time granularity nodes to prevent simultaneous access to the final time granularity nodes.

Proxy processing

FIG. 16 is a flow chart of an agent method 350 for an outgoing order message. The method 350 may be implemented in a software module represented by the agent 128 for execution by the processor 134 of the user (orderer) machine 122. In the method 350, the agent 128 receives an order via the method described in FIGS. 11 and 12 (step 352). The agent 128 creates a string, specifies a boolean expression for the order (step 354), and analyzes the string to check for any possible errors in the order (step 356). If an error exists, the agent 128 may present an error message to the user (step 360) so that the user can correct the error and reenter the order. If the order does not contain an error (step 358), the agent 128 stores the expression in a data structure, an example of which is given below (step 362). The agent 128 converts the unequal expressions in the data structure that have the modification rights to a positive form (step 364) and converts the data structure to a corresponding Disjunctive Normal Form (DNF) structure (step 366). The agent 128 also simplifies the AND expression in the DNF structure to include only range filters AND membership tests (step 368).

The DNF is a well-known canonical form in which boolean expressions are represented as one OR more sub-expressions OR (OR), called disjunct. For example, the boolean expression (price ═ 10AND (symbol ═ LU "OR" symbol ═ T ")) has an equivalent DNF, which is ((price ═ 10AND symbol ═ LU") OR (price ═ 10AND symbol ═ 1 ")).

The conversion in step 364 involves converting an expression with an inequality operator (e.g., the possible syntax notation | ═) to an equivalent positive form that indicates all allowed values, rather than one not allowed. This conversion is performed before the DNF is created and is necessary because the router in this example requires the formula to be in an affirmative form. For example, the expression (price | ═ 80) can be converted into an equivalent expression (price < ═ 79OR price > - > 81).

The translation in step 368 is performed after the DNF is created AND involves additional simplification of the resulting AND expression, which in this example also simplifies the operation of the router. In particular, the AND (AND) of multiple attribute tests for the same attribute may be reduced to a canonical "range filter" having a lower limit, an upper limit, a lower limit AND an upper limit, or a single value in the case of equivalent tests. The particular type of range filter is encoded according to table 22.

For example, the expression (price > -. Other types of examples after simplification are as follows: (price > ═ 20) (with a lower limit); (price > ═ 80) (upper limit only); and (price ═ 50) (single value). In creating these range filters, some of the sub-expressions may be reduced to true or false, in which case the sub-expressions may be eliminated according to the rules of Boolean algebra, thereby further optimizing the encoding of the expressions in the message. For example, the expression (price > - < 50AND price ≦ 20) reduces to false because no value of "price" can satisfy the expression. In the special case where the entire filter expression is reduced to false, the proxy does not need to create a message at all, and unnecessary work by the router can be mitigated.

If the subject filter contains wildcards, the agent 128 can optionally convert them as explained below (step 370). Otherwise, any wildcards may be converted in the network, rather than on the user's machine or other device. In such an embodiment, the syntax of the topic filter is the only syntax that uses wildcards, and the syntax of the property filter is the only syntax that uses Boolean expressions. Alternatively, implementations may use different or various types of syntax for the topic filter and the property filter.

The proxy 128 encodes the resulting DNF expression into a message (step 372) and transmits the message to an intelligent router (step 374). The encoding involves converting the order into a flat message format, which means that it consists of a string of data. Such transmission includes propagating routing rules generated from the subject and attribute filters for the order to one or more intelligent routers or other routing entities in the network. For example, order expressions may be mapped into a conventional packet structure for propagation.

The encoding of step 372 includes formatting the order for a channel into a message format of a message API, which is propagated through the channels. For example, an order is internally notified as a notification of topic #. Since there are a variable number of subject filter fields and a variable number of attribute tests, one pair of bytes is used to store the number of subject filter fields and another pair of bytes is used to store the number of attribute tests. The individual fields of the subject filter are thus grouped sequentially, for example, in their assigned order in the original order, and each is arranged in two bytes as part of the message. The wildcard fields can be arranged as follows.

In grouping attribute tests, the operands to the tests are grouped at the end of the message in a manner similar to grouping the attribute values of a notification. Before grouping property tests and operands, they are sorted into positional order with tests on predefined properties, followed by tests on any properties in name order, by the order of the properties in each disjunct of the DNF. Further, the set of associated tests on each disjunctive term magnitude attribute is reduced to canonical form, e.g., the range filter has one constraint (left or right open domain, or equal test) or two constraints (closed domain between two distinct constraints). The remaining information about the test is encoded in two byte pairs, in the same order as the operands; the sequence of two byte pairs is immediately placed in the message, followed by the two byte encoding sequence of the topic filter field. The two byte pairs may be grouped into a form, a bit-string encoded sequence for attribute testing, which may be used to represent other types of encoding in addition to the two byte pairs. Examples of property testing are given below.

The encoding mode of the attribute test is described in table 20. Table 21 illustrates encoding of two byte pairs and table 22 illustrates encoding of operand IDs with two byte pairs.

Because the two byte pair for a test already indicates the type of test operand and whether the test applies to a predefined or arbitrary attribute, there is no need to group the number of tests performed on any attribute or type thereof. The design assumes that there are no more than 127 predefined attributes in a notification. Alternatively, the design may encode the property test with more bits.

While the grouping transformation customizes and aggregates the attribute tests based on the DNF of the attribute filter, an infrastructure element (e.g., a router) may choose to evaluate the tests in other orders (perhaps dynamically deriving data based on the likelihood of success or failure of the different tests) to make the evaluation of the entire attribute filter more efficient. The order ID field of the message is a value generated by the agent to uniquely assign the order to the agent's edge router for modification or cancellation in subsequent requests. In particular, the dynamic modification of the attribute filter for an order is propagated using the message format shown in the example of FIG. 18, except that the subject is #. RESUBSCRIPTION, and the order ID is the ID of the previously modified registered order. A cancel order propagates to the order ID field with the message format of fig. 18, with the topic # UNSUBSCRIPTION, and the order ID is the previously registered order that was cancelled.

An example is given below illustrating the conversion and encoding by the above described agent. Consider the following attribute filter expression as an example: price ═ 10and (symbol ═ LU "or (volume > -1000 and volume < ═ 10000)). FIG. 19 shows a Unified Modeling Language (UML) diagram 390 depicting the objects used by the agent in step 362 to store the expression. The diagram illustrates a hierarchical relationship specifying an order, which may include variable values, constant values, or both. Depending on the specific implementation, the objects in the graph may be instances of filter classes. Each simple filter object describes a value of an attribute for storing information about a corresponding attribute test of a filter expression. In the representation of fig. 19, one OR filter 396 connects the two AND filters 392 AND 400. The AND filter 392 comprises a simple filter 394 with the attributes of the order. Likewise, the OR filter 396 contains a simple filter 398 AND the AND filter 400 contains simple filters 402 AND 404.

For the purposes of this example, assume that attributes price, symbol, and volume are predefined attributes for the associated channel, and that they are defined at locations 0, 1, and 2, respectively. Further, assume that the types of attributes are unsigned integer (type code 6), character array (type code 12), and unsigned integer (type code 6), respectively.

Consider the next order that contains the attribute filter expression of the example above as its attribute filter. FIG. 18 illustrates composing the order into a message. The left schematic 386 of fig. 18 shows the actual message content and the right schematic 388 gives a legend for the different parts of the message. Each illustrated width in this example is 4 bytes. Before marshalling, the filter has been converted to its equivalent DNF: (price > -.

The 16-bit attribute test code is displayed as a bit sequence, and the interval shows the separation between different parts. Note that the two tests on price in this example cannot be combined because they are in separate disjuncts and they can be grouped separately, with no right boundary ("right open field") in the range. On the other hand, two tests on a volume can be joined because they are in the same disjunct and they are grouped together as a single "closed-domain" test.

Finally, note also that some fields may be described as "hypothetical," meaning that the values of these fields are arbitrarily chosen in this example and are generally independent of the orders being grouped. Additionally, the topic filter for the order is arbitrarily chosen to be ">" which matches any topic defined by the associated channel. The examples described above and shown in fig. 18 and 19 are for illustrative purposes only, and the groupings may be used with any other type of order. Likewise, the method 350 is merely an example given of a group order and they may be grouped in any other manner.

Fig. 17 is a flow chart of a proxy method 376 for an incoming message. The method 376 may be implemented by the agent 128 and the application 126 on the user's machine 122. In the method 376, the agent 128 receives a message from an intelligent router corresponding to an order (step 378). The agent 128 determines a channel corresponding to the order (step 380), such as by channel ID in the message, and invokes an API for the channel (step 382). The API presents the order data in a GUI or other form on the user's machine (step 384). The processing of the incoming message may use a process of decoding the data, as opposed to the encoding process described above, and the decoding (as opposed to encoding) may be performed in a router or other network entity.

Wildcard character processing

Fig. 20 is a flow chart of a wildcard method 410. The method instantiates a set of routing rules for the filter to convert wildcards in the order expression. The method 410 may be implemented by a software module represented by the agent 128, executed by the processor 134 of the user machine 122. Alternatively, the wildcards may be processed by the processor 93 in the network, under software control of the intelligent router 92 or in a corresponding function contained in the ASIC 91. The wildcards include open fields or variable length fields, examples of which are given in table 21.

In the method 410, the agent 128 or other entity receives an order with wildcards (step 412). The topic length of the order may be specified by a publisher at the time of publication of the content, and the topic may be pre-processed on the publisher machine, e.g., to calculate the domain of the topic and then obtain the number (length) of domains. The agent 128 calculates the number of fields in the filter operand (step 414) and initializes a new rule (filter), i.e., field length N (step 416). The agent 128 takes the subdomain of the order (step 418) and determines whether the filter operand subdomain O [ i ] is a wildcard (step 420). If the filter operand subdomain is not a wildcard, then the agent 128 adds a conjoin phrase to the rule, field [ i ] ═ O [ i ] (step 422). If the filter operand has multiple subfields (step 424), the agent 128 returns to step 418 to process additional subfields. The parameter "i" represents a field, where i is an integer representing the number of fields in this example.

After processing the subfields, the agent 128 determines whether the last filter operand subfield is ">" (step 426), and if so, it changes the length constraint of the field to length > N-1 (step 428). The wildcard process can use any type of notation, and ">" is just one example of this. In this example, "a >" may mean a.b, a.c, a.d, etc., and all sub-topics of all levels thereof (e.g., a.b.x, a.c.x, a.b.x.y, etc.). Other symbols may be used for other implementations of wildcards.

If necessary, the proxy 128 propagates the translation rules to the intelligent router or other entity in the network (step 430). Thus, the method processes the rules without wildcards by converting the wildcards through subdomain iterations, which means that the rules do not contain wildcards. The conversion of wildcards can occur anywhere in the network, such as on the orderer machine or in an intelligent router. The transformation may occur in one entity while the transformation rules are propagated to other entities, or the transformation may occur dynamically.

Table 23 gives, along with examples, a summary of these routing rules for handling wildcards. These routing rules may be generated within the intelligent router or generated in other network entities and propagated towards the intelligent router. In addition, the routing rules in table 23 are for illustrative purposes only, and other routing rules may also convert wildcards.

While the invention has been described in conjunction with a specific embodiment, it is to be understood that many modifications will be apparent to those skilled in the art, and that it is intended that the application cover any and all modifications, or variations therein. For example, different types of publisher machines, user or orderer machines, configurations of channels and channels, and hardware and software implementations of content-based routing and other functions may be employed without departing from the scope of the present invention. The invention is limited only as defined in the following claims and equivalents thereto.

Claims (18)

1. A method of communicating decisions in a publish-order network, comprising:

receiving an expression comprising a boolean predicate associated with an order;

encoding said expression into a message for transmission in said network for content-based routing, wherein said encoding step comprises converting said expression into a corresponding disjunctive normal form; and is

Transmitting the message to at least one router of a network core for providing content-based routing to the order.

2. The method of claim 1, wherein said encoding step comprises converting said expression to a monotonic message format.

3. The method of claim 1, wherein the receiving step comprises receiving conjunctive, disjunctive, or negative terms of the decision.

4. The method of claim 1, wherein the encoding step comprises converting the disjunctive normal form into a bit-string encoded sequence of corresponding property tests.

5. The method of claim 1, wherein the encoding step comprises converting unequal parameters in the expression to a deterministic form.

6. The method of claim 1, wherein the encoding step comprises simplifying AND expressions in the disjunctive normal form, including range filters AND membership tests.

7. The method of claim 1, further comprising:

receiving the order; and is

Creating the expression from the order.

8. The method of claim 1, further comprising analyzing the expression to check for errors in the order.

9. The method of claim 1, further comprising storing the expression in a data structure.

10. An apparatus for communicating decisions in a publish-order network, comprising:

a receiving module for receiving an expression comprising a boolean predicate relating to an order;

an encoding module that encodes the expression into a message for transmission in the network for content-based routing, wherein the encoding module includes a module for converting the expression into a corresponding disjunctive normal form; and is

A transmission module for transmitting the message to at least one router of a network core for providing content-based routing to the order.

11. The apparatus of claim 10, wherein said encoding module comprises a module for converting said expression to a monotonic message format.

12. The apparatus of claim 10, wherein the means for receiving comprises means for receiving conjunctive, disjunctive, or negative terms of the determination.

13. The apparatus of claim 10, wherein the encoding module comprises a module for converting the disjunctive normal form into a bit-string encoding sequence of corresponding property tests.

14. The apparatus of claim 10, wherein the encoding module comprises a module for transforming unequal parameters in the expression into a deterministic form.

15. The apparatus of claim 10, wherein the encoding means comprises means for simplifying AND expressions in the disjunctive normal form to include range filters AND membership tests.

16. The apparatus of claim 10, further comprising:

means for receiving the order; and

means for creating the expression from the order.

17. The apparatus of claim 10, further comprising a module for analyzing the expression to check for errors in the order.

18. The apparatus of claim 10, further comprising means for storing the expression in a data structure.