M-trie based packet processing

Details M-trie based packet processing M-trie based packet processing

2006-12-12

2006-12-12

Vu, Huy D. (Department: 2665)

Multiplex communications

Pathfinding or routing

Switching a message which includes an address header

C370S395400

Reexamination Certificate

active

07149216

ABSTRACT:
In an embodiment, different aspects of a packet header and data included in the packet are singled out for attention, rather that just the four byte IP destination address. Different information is included in nodes of the trie that enables matching and branching on different header fields. In an embodiment, the ACL of a configuration file in a router or switch is compiled into a trie data structure located in the memory of the router or switch. In an embodiment, a trie data structure is used to map a multicast packet header by a sequence of nodes that match on destination address or source address.

REFERENCES:
patent: 4491945 (1985-01-01), Turner
patent: 4679189 (1987-07-01), Olson et al.
patent: 4893304 (1990-01-01), Giacopelli et al.
patent: 5088032 (1992-02-01), Bosack
patent: 5249292 (1993-09-01), Chiappa
patent: 5271004 (1993-12-01), Proctor et al.
patent: 5309437 (1994-05-01), Perlman et al.
patent: 5434863 (1995-07-01), Onishi et al.
patent: 5440550 (1995-08-01), Follett
patent: 5509006 (1996-04-01), Wilford et al.
patent: 5519858 (1996-05-01), Walton et al.
patent: 5524254 (1996-06-01), Morgan et al.
patent: 5651002 (1997-07-01), Van Seters et al.
patent: 5684797 (1997-11-01), Aznar et al.
patent: 5684954 (1997-11-01), Kaiserswerth et al.
patent: 5774698 (1998-06-01), Olnowich
patent: 5842224 (1998-11-01), Fenner
patent: 5870382 (1999-02-01), Tounai et al.
patent: 5909440 (1999-06-01), Ferguson et al.
patent: 6011795 (2000-01-01), Varghese et al.
patent: 6041053 (2000-03-01), Douceur et al.
patent: 6091725 (2000-07-01), Cheriton et al.
patent: 6157641 (2000-12-01), Wilford
patent: 6212183 (2001-04-01), Wilford
patent: 6212184 (2001-04-01), Venkatachary et al.
patent: 6243667 (2001-06-01), Kerr et al.
patent: 6308219 (2001-10-01), Hughes
patent: 6385170 (2002-05-01), Chiu et al.
patent: 6553002 (2003-04-01), Bremer et al.
patent: 6590894 (2003-07-01), Kerr et al.
patent: 6704313 (2004-03-01), Duret et al.
patent: 2001/0012295 (2001-08-01), Wilford
patent: 2001/0051864 (2001-12-01), Kerr et al.
patent: 2350534 (2000-11-01), None
patent: WO 94/01828 (1994-01-01), None
patent: WO 96/34479 (1996-10-01), None
patent: WO 9959303 (1999-11-01), None
patent: WO 200077984 (2000-12-01), None
Shang-Tse Chuang et al. “Matching Output Queueing with a Combined Input and Output Queued Switch”. Stanford CSL-TR-98-758.
Willibald Doeringer et al. “Routing on Longest-Matching Prefixes”. IEEE/ACM Transactions on Networking, vol. 4. No. 1. Feb. 1996.
Jim Duffy. “Cisco goes with the flow”. San Jose, Calfornia. May 3, 1996.
Pankaj Gupta et al. “Scheduling Algorithms for an Input-Queued Variable Length Packet Switch”. Stanford University. p. 1-34.
Nick McKeown et al. “Bridges, Routers and Switches”. Department of Electrical Engineering. Stanford University, Stanford, CA 94305-9030.
Tong-Bi Pei et al. “VLSI Implementation of Routing Tables: Tries and Cams”. Department of Electrical Engineering. Center for Telecommunications Research. Columbia University. 1991 IEEE.
Paul F. Tsuchiya. “A Search Algorithm for Table Entries with Non-contiguous Wildcarting”. Bellcore.

Affiliated with

Also associated with

Rating

M-trie based packet processing does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with M-trie based packet processing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and M-trie based packet processing will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3708724