Efficient implementation of wildcard matching on...

Details Efficient implementation of wildcard matching on... Efficient implementation of wildcard matching on...

2002-07-19

2008-08-12

Chan, Wing F. (Department: 2619)

Multiplex communications

Pathfinding or routing

Switching a message which includes an address header

C370S401000, C703S007000

Reexamination Certificate

active

07411954

ABSTRACT:
Packet routing via payload inspection at routers in a core of a distributed network. Packets include subjects and attributes in addition to routing information. The subjects correspond with particular types of content for subscriptions, and the attributes encapsulate the data or content. The routers store filters corresponding with subscriptions to content. The subscriptions can include wildcards, which are converted to filters using routing rules that constrain sizes of fields for the subscription. Upon receiving a packet, a router inspects the payload section of the packet containing the attributes in order to retrieve the attributes and apply them to the filters for the subscriptions. If an attribute satisfies a filter, the packet is routed to the next link. If the attributes do not satisfy the filters, the router discards the packet. These routing decisions are distributed among routers in the network core.

REFERENCES:
patent: 5974417 (1999-10-01), Bracho et al.
patent: 6021443 (2000-02-01), Bracho et al.
patent: 6321267 (2001-11-01), Donaldson
patent: 6336119 (2002-01-01), Banavar et al.
patent: 6347087 (2002-02-01), Ganesh et al.
patent: 6523068 (2003-02-01), Beser et al.
patent: 6850980 (2005-02-01), Gourlay
patent: 6993023 (2006-01-01), Foster et al.
patent: 6999478 (2006-02-01), D'Angelo
patent: 7065082 (2006-06-01), Ganesh et al.
patent: 2002/0067726 (2002-06-01), Ganesh et al.
patent: 2002/0087881 (2002-07-01), Harif
patent: 2002/0150093 (2002-10-01), Ott et al.
patent: 2002/0162025 (2002-10-01), Sutton et al.
patent: 2003/0154302 (2003-08-01), Rosenblum
patent: 2004/0027995 (2004-02-01), Miller et al.
patent: 2004/0076155 (2004-04-01), Yajnik et al.
Search Report issued on Mar. 29, 2004 in counterpart foreign application in WIPO under application No. PCT/US03/21338.
Gupta, P., et al., Algorithms for Packet Classification. IEEE Network, pp. 24-32, Mar./Apr. 2001.
Srinivasan, V., et al., Fast and Scalable Layer Four Switching. In Proceedings of SIGCOMM '98, pp. 191-202, 1998.
Gupta et al., Packet Classification on Multiple Fields, Proceedings of ACM SIGCOMM '99, pp. 147-160, Aug. 1999.
Lakshman, T., et al., High Speed Policy-based Packet Forwarding Using Efficient Multi-dimensional Range Matching. In Proc. ACM SIGCOMM '98, pp. 203-214, 1998.
Srinivasan, V., et al., Packet Classification using Tuple Space Search. In Proceedings of ACM SIGCOMM '99, pp. 135-146, Sep. 1999.
Adiseshu,,H., et al., Packet filter management for layer 4 switching. In Proceedings of IEEE INFOCOM, 1999.
Buddhikot, M., et al., Space decomposition techniques for fast layer-4 switching. In Proceedings of IFIP Workshop on Protocols for High Speed Networks, Salem, Massachusetts, pp. 25-41, Aug. 25-28, 1999.
Gupta et al., Packet Classification Using Hierachical Intelligent Cuttings. In Proceedings Hot Interconnects VII, Aug. 1999.
Warkhede, P.R., et al., Fast Packet Classification for Two-Dimensional Conflict-Free Filters. In Proc. INFOCOM, pp. 1434-1443, 2001.
Waldvogel, M., Multi-Dimensional Prefix Matching Using Line Search. In Proceedings of IEEE Local Computer Networks, pp. 200-207, Nov. 2000.
Eppstein, D., et al., Internet packet filter management and rectangle geometry. In Proceedings of the 12thAnnual ACM—SIAM Symposium on Discrete Algorithms (SODA 2001), pp. 827-835, Washington, DC., Jan. 2001.
Feldmann, A., Tradeoffs for packet classification. In Proc. INFOCOM, vol. 3, pp. 1193-1202. IEEE, Mar. 2000.
Woo, T., A Modular Approach to Packet Classification: Algorithms and results. In Proc. IEEE INFOCOM, Tel-Aviv, Israel, pp. 1213-1222, Mar. 2000.
Eugster, P., et al., Event Systems, How to Have Your Cake and Eat It Too, In 22ndInternational Conference on Distributed Computing Systems Workshops (ICDCSW '02), Vienna, Austria, Jul. 2-5, 2002.

Affiliated with

Also associated with

Rating

Efficient implementation of wildcard matching on... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Efficient implementation of wildcard matching on..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient implementation of wildcard matching on... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-4007361