1. A high speed data stream monitoring system for monitoring and ascertaining desired characteristics of a high speed data stream flowing in a network, the data in the data stream being in the form of serial tuples, the monitoring system comprising:
means for evaluating new tuples arriving in the stream, the means for evaluating including computation means for running a query plan on new tuples arriving in the stream, the query plan including a set of high level queries and a set of different low level queries, the low level queries being characterized by different sets of predicates to be evaluated on the tuples as part of the queries, the set of different low level queries including a plurality of different low level queries sharing a common predicate,
a predicate prefilter outside of the query plan that includes a set of predicates selected from the low level query predicates including a common predicate shared by different low level queries and that evaluates the selected predicates on a new tuple arriving in the stream before running any of the low level queries on the tuple and produces a predicate signature for each new tuple in response to the evaluation;
means for assigning a predicate signature to each of the low level queries,
means for determining those low level queries which have a predicate signature compatible with the predicate signature of the tuple produced by the prefilter;
means for applying to the tuple only those low level queries determined to have a predicate signature compatible with the predicate signature of the tuple produced by the prefilter, along with selected high level queries, to ascertain the desired characteristics of the high speed data stream;
whereby low level queries that do not have a compatible bit signature are not applied to the tuple by the monitoring system and the computation means has a computation load for running the query plan that is reduced.
2. The high speed data stream management system claimed in claim 1 wherein the high level queries are high level filtering-transformation-aggregation queries and the low level queries are low level filtering-transformation-aggregation queries.
3. The high speed data stream management system claimed in claim 1 wherein the predicates selected to be evaluated in the prefilter have an execution cost that is less than a value C, where C is an execution cost chosen to be less than the execution cost of executing a low level query.
4. The high speed data stream management system claimed in claim 3 wherein the predicates selected to be evaluated in the prefilter include both base predicates and groups of base predicates that are present in the low level queries.
5. The high speed data stream management system claimed in claim 4 wherein the groups of base predicates are selected to reduce overlapping predicates.
6. The high speed data stream management system claimed in claim 3 wherein the predicates selected to be evaluated in the prefilter are the predicates that require the fewest attribute unpacking operations to evaluate.
7. The high speed data stream management system claimed in claim 1 wherein the predicate signature for each tuple is a bit vector with bits representing the presence and absence of selected predicates in the tuple, and wherein the predicate signature assigned to a low level query has bits representing predicates that are required to be present by the low level query, and wherein the means for invoking a low level query compares the bits in the tuple bit vector with the bits in the low level query bit signature.
8. A method for operating a high speed data stream monitoring system for monitoring and ascertaining desired characteristics of a high speed data stream flowing in a network, the data in the data stream being in the form of serial tuples, the monitoring method evaluating new tuples arriving in the stream with computation means running a query plan on new tuples arriving in the stream, the query plan including a set of high level queries and a set of different low level queries, the low level queries being characterized by sets of different predicates to be evaluated on the tuples as part of the queries, the set of different low level queries including a plurality of different low level queries sharing a common predicate, the method comprising:
prefiltering the tuples outside of the query plan with a set of predicates selected from the low level query predicates including a common predicate shared by different low level queries to evaluate a new tuple arriving in the stream before running any of the low level queries on the tuple and to determine if the selected predicates evaluate to true in the tuple;
generating a tuple predicate signature representing the selected predicates that evaluate to true in the tuple;
assigning a predicate signatures to each of the low level queries
determining those low level queries that have signatures that are compatible with the tuple predicate signature;
applying to the tuple only those low level queries determined to have signatures compatible with the tuple predicate signature, along with selected high level queries, to ascertain the desired characteristics of the high speed data stream;
whereby low level queries that have predicate signatures that are not compatible with the tuple predicate signature are not applied to the tuple and the computation means has a computational load for running the query plan that is reduced.
9. The method claimed in claim 8 wherein the selected predicates evaluated by prefiltering have an execution cost that is less than a value C, where C is a cost chosen to be less than the cost of executing a low level query.
10. The method claimed in claim 9 where the predicates selected to be evaluated by prefiltering include both base predicates and groups of base predicates that are present in the low level queries.
11. The method claimed in claim 10 where the groups of base predicates have been selected to reduce overlapping predicates.
12. The method claimed in claim 9 where the predicates selected to be evaluated by prefiltering are predicates selected to require the fewest attribute unpacking operations to evaluate.
13. The method claimed in claim 8 wherein the predicate signature for each tuple is a bit vector with bits representing the presence and absence of selected predicates in the tuple, and wherein the predicate signature assigned to a low level query has bits representing predicates that are required to be present by the low level query, and wherein invoking a query compares the bits in the tuple bit vector with the bits in the low level query bit signature.
14. The method claimed in claim 8 wherein the high level queries are high level filtering-transformation-aggregation queries and the low level queries are low level filtering-transformation-aggregation queries.
15. A method for selecting predicates to be evaluated in a prefilter in a high speed data stream monitoring system for monitoring and ascertaining desired characteristics of a high speed data stream flowing in a network, the data in the data stream being in the form of serial tuples, the monitoring method evaluating new tuples arriving in the stream with computation means running a query plan on new tuples arriving in the stream, the query plan including a set of high level queries and a set of different low level queries, the different low level queries being characterized by different sets of predicates to be evaluated on the tuples and each of the low level queries being assigned a predicate signature, the prefilter evaluating a new tuple arriving in the stream before running any of the low level queries on the tuple with predicates selected from the low level query predicates to determine if the selected predicates are present in the tuple and to create a tuple predicate signature to be compared to a predicate signature assigned to a low level query to cause the computation means to apply to the tuple only those low level queries on the tuple that have a predicate signature matching the tuple predicate signature, the prefilter predicate selection method comprising:
identifying base predicates in the low level queries;
establishing an execution cost C for processing of predicates, where C is chosen to be less than the cost of executing a low level query;
selecting base predicates with a cost level below the established level C; and
placing the selected base predicates with a cost level below the established level C in the prefilter.
16. The method claimed in claim 15 further comprising:
combining the selected base predicates into groups of two or more predicates present in one or more low level queries.
17. The method claimed in claim 16 wherein combining the base predicates into groups comprises:
constructing a matrix M to represent the predicates with a cost level below the established level C and their corresponding low level queries; and
applying a rectangle covering heuristic to the matrix M to locate groups of predicates present in one or more low level queries.
18. The method claimed in claim 17 further comprising:
removing rectangle overlaps to produce a set of groups of predicates which do not duplicate predicate presence in the groups.
19. The method claimed in claim 16 wherein the predicates are assigned priority according to the attribute unpacking operations that are required to evaluate them.
20. The method claimed in claim 15 wherein the prefilter has a limited bit budget, further comprising:
assigning a priority to the selected predicates; and
adding the selected predicates to the prefilter to the limit of the bit budget in priority order.
21. The method claimed in claim 20 wherein the predicates are selected by constructing a matrix M to represent the predicates and their corresponding queries, and a rectangle covering heuristic is applied to the matrix M to locate groups of predicates present in one or more queries, and wherein the predicates are assigned priority according to their identification by the rectangle covering heuristic.
22. The method claimed in claim 20 wherein the predicates are assigned priority according to their selectivities such that their choice will result in minimum application of low level queries.
23. The method as claim in claim 15 wherein the established execution cost C is 10 operations.
The claims below are in addition to those above.
All refrences to claim(s) which appear below refer to the numbering after this setence.
1. A method for routing a service on a service overlay network comprising:
step A: receiving, by a current service routing entity, a service request, and selecting, by the current service routing entity, according to the routing code of a home service routing entity of a service, from its own service routing table, a second service routing entity corresponding to a routing code that has a most adjacency relationship with the routing code;
if the second service routing entity is not the current service routing entity itself, forwarding, by the current service routing entity, the service request to the second service routing entity, wherein the service request carries the routing code of the home service routing entity, setting the second service routing entity as the current service routing entity, and performing step A until the second service routing entity selected by the current service routing entity is the current service routing entity itself; and
if the second service routing entity is the current service routing entity itself, setting the current service routing entity as a first most adjacent service routing entity, and obtaining, by the first most adjacent service routing entity, service registration information of the service from service registration entity corresponding to the first most adjacent service routing entity, and wherein the first most adjacent service routing entity sends the service request to a service provider according to an endpoint address of the service provider in the service registration information.
2. The method according to claim 1, wherein the service request carries a service address, and the service address comprises an identity of the service and an identity of the home service routing entity.
3. The method according to claim 2, wherein if the receiving, by the current service routing entity, the service request comprises receiving the service request from a service requester, the current service routing entity is set as an access service routing entity, and wherein after receiving the service request, the access service routing entity obtains the identity of the home service routing entity by parsing the service address carried in the service request and sends the identity of the home service routing entity to a self-organized management entity to acquire the routing code of the home service routing entity from the self-organized management entity.
4. The method according to claim 1, wherein the routing code comprises a service type code and a node code.
5. The method according to claim 4, wherein in the step A, the current service routing entity selects, from its own service routing table, a service routing entity a service type code of which is the same as a service type code of the home service routing entity and a node code of which is most adjacent to a node code of the home service routing entity as the second service routing entity.
6. The method according to claim 1, wherein before receiving, by the current service routing entity, the service request, the method further comprises:
step B: receiving, by an intermediate service routing entity, the routing code of a newly joined service routing entity and selecting a next-hop service routing entity that has a most adjacency relationship with the routing code from its own service routing table;
if the next-hop service routing entity is not the intermediate service routing entity itself, sending, by the intermediate service routing entity, a service routing table update message to the next-hop service routing entity, wherein the service routing table update message carries the routing code of the newly joined service routing entity;
if the routing code of the newly joined service routing entity is more adjacent to a routing code of the intermediate service routing entity than a routing code of at least one neighboring service routing entity in the service routing table of the intermediate service routing entity, updating, by the intermediate service routing entity, its own service routing table by adding the newly joined service routing entity, setting the next-hop service routing entity as the intermediate service routing entity, and performing step B until the next-hop service routing entity selected by the intermediate service routing entity is the intermediate service routing entity itself; and
if the next-hop service routing entity is the intermediate service routing entity itself, setting the intermediate service routing entity as a second most adjacent service routing entity, sending, by the second most adjacent service routing entity, its own service routing table to the newly joined service routing entity, and updating the service routing table of the second most adjacent service routing entity by adding the newly joined service routing entity.
7. The method according to claim 1, wherein before receiving, by the current service routing entity, the service request, the method further comprises:
obtaining, by an exiting service routing entity, from its corresponding first service registration entity, all service registration information stored on the first service registration entity;
selecting, by the exiting service routing entity, from a service routing table, a third most adjacent service routing entity that has a most adjacency relationship in terms of routing codes with the exiting service routing entity and sending a service routing entity exit request that carries the service registration information to the third most adjacent service routing entity;
registering, by the third most adjacent service routing entity, the service registration information with its corresponding second service registration entity;
deleting, by the third most adjacent service routing entity, the exiting service routing entity from its own service routing table, and sending a service routing table update message to a neighboring service routing entity in the service routing table; and
after receiving, by the neighboring service routing entity, the service routing table update message, if a service routing table of the neighboring service routing entity comprises the exiting service routing entity, deleting the exiting service routing entity from the service routing table.
8. A method for newly joining a service overlay network comprising:
step C: receiving, by a current service routing entity, the routing code of a newly joined service routing entity and selecting a next-hop service routing entity that has a most adjacency relationship with the routing code from its own service routing table;
if the next-hop service routing entity is not the current service routing entity itself, sending, by the current service routing entity, a service routing table update message to the next-hop service routing entity, wherein the service routing table update message carries the routing code of the newly joined service routing entity;
if the routing code of the newly joined service routing entity is more adjacent to the routing code of the current service routing entity than a routing code of at least one neighboring service routing entity in the service routing table of the current service routing entity, updating, by the current service routing entity, its own service routing table by adding the newly joined service routing entity, setting the next-hop service routing entity as the current service routing entity, and performing step C until the next-hop service routing entity selected by the current service routing entity is the current service routing entity itself; and
if the next-hop service routing entity is the current service routing entity itself, setting the current service routing entity as the most adjacent service routing entity, sending, by the most adjacent service routing entity, its own service routing table to the newly joined service routing entity, and updating the service routing table of the most adjacent service routing entity by adding the newly joined service routing entity.
9. The method according to claim 8, wherein if receiving, by the current service routing entity, the routing code of the newly joined service routing entity is acquiring a routing code that is allocated by a self-organized management entity for the newly joined service routing entity from the self-organized management entity by receiving an addition guidance request of the newly joined service routing entity, the current service routing entity is the guidance service routing entity, and the newly joined service routing entity joins the service overlay network for the first time.
10. The method according to claim 9, wherein if receiving, by the current service routing entity, the routing code of the newly joined service routing entity comprises obtaining the routing code of the newly joined service routing entity from a guidance request by receiving the addition guidance request of the newly joined service routing entity, setting the current service routing entity as the guidance service routing entity, wherein the newly joined service routing entity joins the service overlay network not for the first time.
11. The method according to claim 9, wherein before receiving, by the guidance service routing entity, the addition guidance request sent by the newly joined service routing entity, the method further comprises:
sending, by the newly joined service routing entity, a guidance service routing entity allocation request to the self-organized management entity; and
after receiving the guidance service routing entity allocation request, allocating, by the self-organized management entity, a guidance service routing entity for the newly joined service routing entity and returning a guidance service routing entity allocation response to the newly joined service routing entity to notify the newly joined service routing entity of an endpoint address of the guidance service routing entity.
12. The method according to claim 9, wherein receiving, by the guidance service routing entity, the addition guidance request of the newly joined service routing entity and acquiring the routing code allocated by the self-organized management entity for the newly joined service routing entity from the self-organized management entity comprises:
receiving, by the guidance service routing entity, the addition guidance request sent by the newly joined service routing entity;
requesting, by the guidance service routing entity, a context awareness for context information;
returning, by the context awareness, the context information requested by the guidance service routing entity;
after receiving the context information sent by the context awareness, sending, by the guidance service routing entity, a service routing entity addition request to the self-organized management entity, wherein the service routing entity addition request carries the identity of the newly joined service routing entity and the context information or further comprising the service type of the newly joined service routing entity;
allocating, by the self-organized management entity, a routing code for the newly joined service routing entity, wherein the routing code comprises a service type code and a node code; and
sending, by the self-organized management entity, a service routing entity addition response to the guidance service routing entity, wherein the service routing entity addition response carries the routing code.
13. The method according to claim 12, wherein allocating, by the self-organized management entity, the routing code for the newly joined service routing entity comprises:
if the service type of the newly joined service routing entity is specified, and its service type code is ca, among the service routing entities that have a same service type on the service overlay network, selecting, by the self-organized management entity, a second service routing entity that meets a regulated requirement with the newly joined service routing entity;
if a node code in the routing code of the second service routing entity is c1, allocating a node code c2 that is adjacent to c1 and is not allocated for the newly joined service routing entity, the service type code in the routing code of the newly joined service routing entity is ca, and wherein the node code is c2;
if no service routing entities that have a same service type exist on the service overlay network, allocating, by the self-organized management entity, a node code c at random, wherein the service type code in the routing code of the newly joined service routing entity is ca, and wherein the node code is c; and
if the service type of the newly joined service routing entity is not specified, selecting, by the self-organized management entity, on the service relay network, a second service routing entity that meets a regulated requirement with the newly joined service routing entity; and
if the service type of the second service routing entity is B, the service type code in the routing code of the second service routing entity is cb, and the node code is c1, the service type code allocated for the newly joined service routing entity is cb, allocating a node code c2 that is adjacent to the c1 and is not allocated, wherein the service type code in the routing code of the newly joined service routing entity is cb, and wherein the code node is c2.
14. The method according to claim 9, further comprising:
after receiving the service routing table sent by the most adjacent service routing entity, setting, by the newly joined service routing entity, its own service routing table of the newly joined service routing entity;
sending, by the newly joined service routing entity, a guidance service routing entity addition request to the self-organized management entity; and
returning, by the self-organized management entity, a guidance service routing entity addition response to the newly joined service routing entity.
15. The method according to claim 10, further comprising:
after receiving the service routing table sent by the most adjacent service routing entity, setting, by the newly joined service routing entity, its own service routing table of the newly joined service routing entity;
sending, by the newly joined service routing entity, a guidance service routing entity allocation request to the self-organized management entity; and
returning, by the self-organized management entity, a guidance service routing entity allocation response to the newly joined service routing entity.
16. A method for exiting a service overlay network comprising:
obtaining, by an exiting service routing entity, from its corresponding first service registration entity, all service registration information stored on the first service registration entity;
selecting, by the exiting service routing entity, from a service routing table, a most adjacent service routing entity that has a most adjacency relationship in terms of routing codes with the exiting service routing entity and sending a service routing entity exit request that carries the service registration information to the most adjacent service routing entity;
registering, by the most adjacent service routing entity, the service registration information with its corresponding second service registration entity;
deleting, by the most adjacent service routing entity, the exiting service routing entity from its own service routing table and sending a service routing table update message to a neighboring service routing entity in the service routing table; and
after the neighboring service routing entity receives the service routing table update message, if a service routing table of the neighboring service routing entity comprises the exiting service routing entity, deleting the exiting service routing entity from the service routing table.
17. A service overlay network system comprising:
a service routing entity configured to receive a service request and select, according to the routing code of a home service routing entity of the service, from its own service routing table, a second service routing entity corresponding to a routing code that has a most adjacency relationship with the routing code, wherein if the second service routing entity is not the current service routing entity itself, the service routing entity forwards the service request to the second service routing entity;
a most adjacent service routing entity, wherein when the second service routing entity selected by the service routing entity is the service routing entity itself, configured to set the service routing entity as the most adjacent service routing entity, send a service registration information query request to a service registration entity, receive service registration information returned by the service registration entity, and send the service request to a service provider according to an endpoint address of the service provider in the service registration information; and
the service registration entity configured to receive the service registration information query request sent by the most adjacent service routing entity and send the service registration information to the most adjacent service routing entity.
18. The service overlay network system according to claim 17, further comprising:
a service requester configured to send the service request to an access service routing entity and receive a service response returned by the access service routing entity;
the access service routing entity, wherein when receiving, by the service routing entity, the service request comprises receiving the service request from the service requester, the service routing entity is set as the access service routing entity and is configured to send a request that carries an identity of a home service routing entity to a self-organized management entity and receive the routing code of the home service routing entity returned by the self-organized management entity, wherein, the access service routing entity selects, according to the routing code, a second service routing entity corresponding to a routing code that has a most adjacency relationship with the routing code from its own service routing table, and if the second service routing entity is not the access service routing entity itself, the access service routing entity forwards the service request to the second service routing entity and forwards the service response to the service requester;
the self-organized management entity configured to receive the request that carries the identity of the home service routing entity sent by the access service routing entity, query the routing code of the home service routing entity according to the identity of the home service routing entity, and send the routing code to the access service routing entity; and
a service provider configured to receive the service request forwarded by the most adjacent service routing entity and send the service response to the most adjacent service routing entity.
19. A service overlay network system comprising:
a service routing entity configured to receive the routing code of a newly joined service routing entity and select a next-hop service routing entity that has a most adjacency relationship with the routing code from its own service routing table, wherein, if the next-hop service routing entity is not the service routing entity itself, the service routing entity sends a service routing table update message to the next-hop service routing entity, wherein the service routing table update message carries the routing code of the newly joined service routing entity, wherein if the routing code of the newly joined service routing entity is more adjacent to the routing code of the service routing entity than a routing code of at least one neighboring service routing entity in the service routing table of the service routing entity, the service routing entity updates its own service routing table by adding the newly joined service routing entity; and
a most adjacent service routing entity, wherein if the next-hop service routing entity selected by the service routing entity is the service routing entity itself, configured to set the service routing entity as the most adjacent service routing entity, send a service routing table to the newly joined service routing entity, and update its own service routing table of the most adjacent service routing entity by adding the newly joined service routing entity.
20. A service overlay network system comprising:
an exiting service routing entity configured to send a service registration information request to its corresponding first service registration entity and receive all service registration information stored on the first service registration entity sent by the first service registration entity, wherein, the exiting service routing entity selects from its own service routing table, a most adjacent service routing entity that has a most adjacency relationship in terms of routing codes with the exiting service routing entity and sends a service routing entity exit request that carries the service registration information to the most adjacent service routing entity;
the first service registration entity configured to receive the service registration information request sent by the exiting service routing entity and send all service registration information stored on the first service registration entity to the exiting service routing entity;
a most adjacent service routing entity configured to receive the service routing entity exit request sent by the exiting service routing entity and register the service registration information with its corresponding second service registration entity, wherein the most adjacent service routing entity deletes the exiting service routing entity from its own service routing table and sends a service routing table update message to a neighboring service routing entity in the service routing table;
a second service registration entity configured to accept registration of the service registration information sent by the most adjacent service routing entity and return a registration response to the most adjacent service routing entity; and
the neighboring service routing entity configured to receive the service routing table update message sent by the most adjacent service routing entity, wherein if a service routing table of the neighboring service routing entity comprises the exiting service routing entity, the neighboring service routing entity deletes the exiting service routing entity from its own service routing table.