Method and apparatus for content-based packet routing using compact filter storage and off-line pre-computation

• US 20030223408A1
• Filed: 03/28/2003
• Published: 12/04/2003
• Est. Priority Date: 03/28/2002
• Status: Active Grant

• Current Assignee: Precache Incorporated
• Original Assignee: Precache Incorporated
• Inventors: Yang, Ping-Fai, Chen, Tsu-Wei, Rosenblum, David S., Fung, Alex W. P.
• Granted Patent: US 7,653,753 B2
• Time in Patent Office: Days
• US Class Current: 370/352
• CPC Class Codes: H04L 45/306 Route determination based on the nature of the carried application

Abstract

A method and apparatus provide for content-based routing of packets in a publish-subscribe network. A packet is received via the network. A map specifying computed filter coverage in an attribute space is accessed. Content of the packet is inspected for a routing decision for the packet. The map is used for the routing decision for the packet. The packet is routed based upon the inspected content of the packet and the map. A router for content-based routing of packets in a publish-subscribe network, comprising modules for performing this method is provided. A network including a plurality of such routers is provided. A computer-readable medium including instructions for performing this method is provided.

Claims

1. A method for content-based routing of packets in a publish-subscribe network, comprising:

receiving a packet in the network;

accessing a map specifying filter coverage in an attribute space;

inspecting content of the packet for use in a routing decision for the packet;

using the map to assist in a routing decision for the packet;

making a routing decision based upon the inspected content of the packet and the map; and

routing the packet based on the routing decision.

2. The method of claim 1, wherein the making a routing decision step further includes matching the content to a corresponding subscription.

3. The method of claim 2, wherein the matching step includes using a plurality of conjunctive filters in order to identify a match.

4. The method of claim 2, wherein the matching step includes performing attribute tests.

5. The method of claim 1, wherein the making a routing decision step includes using the map online.

6. The method of claim 1, further comprising precomputing filter coverage off-line or with background processing.

7. The method of claim 1, further comprising precomputing filter coverage wherein the precomputing step includes approximating and reducing filter expressions.

8. The method of claim 1, further comprising computing filter coverage wherein the computing filter coverage includes spatially quantizing attribute space into a grid comprising grid cells.

9. The method of claim 8, wherein the computing filter coverage includes:

combining filter coverage information and the grid; and

generating the map based on a union of actions predicated by filter coverage information in each grid cell.

10. A router for content-based routing of packets in a publish-subscribe network, comprising modules for executing the method recited in claim 1.

11. A network comprising a plurality of routers according to claim 10.

12. A computer-readable medium comprising instructions for performing the method recited in claim 1.

13. A method for use in content-based routing of packets, comprising:

(a) spatially quantizing attribute space, wherein the spatially quantizing step creates a grid including grid cells;

(b) identifying the grid cells covered by a plurality of filters, wherein each filter has at least one predicated attribute; and

(c) updating a content-based routing (CBR) table with action rules predicated by the plurality of filters that cover the grid cells identified in step (b).

14. The method of claim 13, further comprising the step of:

determining if one or more distinct filters are inserted or removed from a node; and

executing steps (b) and (c) at the node based on a determination that one or more distinct filters are inserted or removed from the node.

15. The method of claim 13, further comprising the steps of:

receiving published packets; and

plotting the received packets to the grid.

16. The method of claim 15, wherein for packets plotted to grid cells that are completely covered by the computed filter coverage information, the method further comprises:

checking the CBR table to determine routing actions for packets plotted to the completely covered grid cells.

17. The method of claim 16, further comprising:

determining if the network traffic is above a set threshold; and

,

routing the published packets based on the determined routing actions, if the network traffic is determined to be above the set threshold.

18. The method of claim 17, further comprising:

performing leakage reduction, if the network traffic is determined to be at or below the set threshold.

19. The method of claim 18, wherein the performing leakage reduction step includes one-dimension exact matching.

20. The method of claim 18, wherein the performing leakage reduction step includes cross-producting.

21. The method of claim 18, wherein the performing leakage reduction step includes the formation of multiple grids and CBR tables according to the full set of subset of the permutations of a limited number and a variety of attributes.

22. The method of claim 17, further comprising:

determining if there are any reduced filter predicates or packets plotted to partially covered grid cells, if the network traffic is determined to be at or below the set threshold;

performing predicate-by-predicate filter matching to determine routing actions for any reduced filter predicates and any packets plotted to partially covered grid cells, if there are determined to be reduced filter predicates or packets plotted to partially covered grid cells; and

,

routing the packets based on determined routing actions.

23. The method of claim 13, further comprising reducing filter expressions.

24. The method of claim 13, wherein step (a) includes adaptive quantizing the attribute space.

25. The method of claim 24, wherein the adaptive quantizing step adaptively quantizes the attribute space based on packet distribution information.

26. The method of claim 13, wherein the spatially quantizing step spatially quantizes the attribute space based on packet distribution information.

27. The method of claim 13, wherein the spatially quantizing step updates the grid based on packet distribution information.

28. The method of claim 13, wherein step (c) generates or updates an action bit mask for a grid cell that is covered by the computer filter coverage information.

29. The method of claim 13, wherein step (c) generates or updates a linked list of action for a grid cell that is covered by the computer filter coverage information.

30. The method of claim 13, further comprising updating parameters for covered cells in the CBR table, wherein the parameters include statistical information about the filter distribution.

31. The method of claim 13, further comprising collecting statistical information about packet distribution, wherein the packet distribution information is used in step (a).

32. The method of claim 13, wherein steps (a) through (c) are performed offline.

33. The method of claim 13, further comprising performing content based routing (CBR), wherein only the CBR table and the rules in the CBR table are used to perform the CBR.

34. An apparatus for content-based routing of packets in a publish-subscribe network, comprising modules for executing the method recited in claim 13.

35. The apparatus of claim 34, wherein the apparatus is a router.

36. A network comprising a plurality of routers that comprise modules for executing the method recited in claim 13.

37. A computer-readable medium comprising instructions for performing the method recited in claim 13.