Apparatus and method for switching packets using tree memory
First Claim
1. A device for switching packets, comprisinga first memory coupled to a network interface, said first memory being large enough to hold a packet data word;
- a comparator having a first input coupled to said first memory and having a second input;
a second memory having a first input coupled to a comparison output of said comparator, and having a second input, said first and second inputs of said second memory collectively referencing a location in said second memory;
at least part of said location comprising a next data word and being coupled to said second input of said comparator;
at least part of said location comprising a next address and being coupled to said second input of said second memory; and
at least part of said location comprising a next instruction word, said next instruction word being coupled to an instruction decoder.
5 Assignments
0 Petitions
Accused Products
Abstract
A device for switching packets at high speed. For each packet, the A device matches packet data with protocols, to determine how to switch the packet. Matching of data with protocols is highly parallel; the device simultaneously retrieves a data byte, compares a data byte with a protocol byte, tests a comparison result, and executes a processor instruction. A switching engine having a comparator and a decision tree memory. The comparator includes three outputs for indicating a comparison result (less-than, equal-to, or greater-than). The tree memory includes three corresponding banks of addressable memory. Each memory location comprises an entry for a next location, an entry for a next protocol byte, and an entry for a processor instruction. A set of protocol tests are assembled into the tree memory, and a set of routing tables are dynamically generated into the tree memory.
-
Citations
36 Claims
-
1. A device for switching packets, comprising
a first memory coupled to a network interface, said first memory being large enough to hold a packet data word; -
a comparator having a first input coupled to said first memory and having a second input; a second memory having a first input coupled to a comparison output of said comparator, and having a second input, said first and second inputs of said second memory collectively referencing a location in said second memory; at least part of said location comprising a next data word and being coupled to said second input of said comparator; at least part of said location comprising a next address and being coupled to said second input of said second memory; and at least part of said location comprising a next instruction word, said next instruction word being coupled to an instruction decoder. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17)
-
-
18. A device for switching packets, comprising
means for receiving a packet from a first one network interface of a plurality of network interfaces; -
a tree memory comprising a set of locations each having a next data word, a next address and a next instruction word, said set of locations comprising a first region comprising a tree program for routing packets in response to a set of static routing information about a network coupled to said first one network interface; means for receiving dynamic routing information about said network; means for compiling said dynamic routing information into a second region in said set of locations; and means for sending said packet to a second one of said plurality of network interfaces in response to said tree memory. - View Dependent Claims (19, 20, 21, 22, 23)
-
-
24. A device for switching packets, comprising
means for receiving a packet from a first one of a rality of network interfaces; -
means for preparing an interface register in response to said packet; a tree memory having a set of locations each having a next data word, a next address and a next instruction word; an instruction decoder coupled to said next instruction, word and to a result register; means for signaling said tree memory to process said packet; means for altering said packet in response to said result register; means for selecting a second one of said plurality of network interfaces in response to said result register; means for sending said packet to said second one network interface.
-
-
25. A device for switching packets, comprising
means for receiving a packet from a first one of a plurality of network interfaces; -
means for sending said packet to a second one of said plurality of network interfaces; means for switching said packet from said first one network interface to said second one network interface; said means for switching having a clock cycle time defined to equal a shortest time needed to decode a processor instruction, and having a clock cycle rate defined to equal an inverse of said clock cycle time; said means for switching having a packet switching rate defined to equal an average rate of switching packets from said first to said second one network interface, said average rate being determined for a substantial time period that is not predetermined, said average being true for a packet traffic distribution that is not predetermined, and said average rate being sustainable in excess of a selected value for a substantial period of time; said clock cycle rate divided by said packet switching rate being less than about 100 clock cycles per packet switched. - View Dependent Claims (26, 27)
-
-
28. A device for switching packets, comprising
means for receiving information from a network interface coupled to a network, said information comprising destination addresses; -
means for converting said information to tree programs for a tree memory, said tree programs comprising data in a set of locations for said tree memory, said data selected in response to said information; means for executing said tree programs; wherein each one of said tree programs comprises a tree structure, said tree structure comprising a root node, a plurality of nonterminal branch nodes coupled to said root node, and a set of terminal nodes coupled to said nonterminal branch nodes, each one of said nonterminal branch nodes having a plurality of said nodes coupled thereto; wherein each nonterminal branch node in said tree structure comprises a register for storing a data item for comparison and an instruction word. - View Dependent Claims (29, 30, 31)
-
-
32. A device for switching packets, comprising
means for receiving information from a network interface coupled to a network, said information comprising destination addresses; -
means for converting said information to tree programs for a tree memory, said tree programs comprising data in a set of locations for said tree memory, said data selected in response to said information; means for executing said tree programs; wherein said tree memory comprises a comparator having a first input coupled to said tree first memory and having a second input; a second memory having a first input coupled to a comparison output of said comparator, and having a second input, said first and second inputs of said second memory collectively referencing a location in said second memory; at least part of said location comprising a next data word and being coupled to said second input of said comparator; at least part of said location comprising a next address and being coupled to said second input of said second memory; and at least part of said location comprising a next instruction word and being coupled to an instruction decoder.
-
-
33. A device for switching packets, comprising
means for receiving information from a network interface coupled to a network, said information comprising destination addresses; -
means for converting said information to tree programs for a tree memory, said tree programs comprising data in a set of locations for said tree memory, said data selected in response to said information; means for executing said tree programs; wherein said means for converting comprises means for generating a tree program for recognizing a set of destination addresses in said information; means for placing said tree program in a tree memory for execution.
-
-
34. A device for switching packets, comprising means for receiving information from a network interface coupled to a network, said information comprising destination addresses;
-
means for converting said information to tree programs for a tree memory, said tree programs comprising data in a set of locations for said tree memory, said data selected in response to said information; means for executing said tree programs; wherein said means for converting comprises means for generating a weighted tree of destination addresses; and means for generating a tree program responsive to said weighted tree, wherein said tree program comprises at least one call upon a high-level processor for processing a packet, and wherein said tree program is limited to a predetermined size, and wherein said tree program is structured to have a minimum likelihood per packet of executing said call.
-
-
35. A method of packet switching, comprising
coupling a data word from a packet received from a first one of a plurality of network interfaces to a first input of a comparator; -
addressing a memory in response to an output of said comparator; retrieving an output of said memory; coupling at least part of said output of said memory to a second input of said comparator; coupling at least part of said output of said memory to an address input of said memory; coupling at least part of said output of said memory to an instruction decoder, said instruction decoder being coupled to a processing element; repeating said steps of coupling a data word, addressing, retrieving, coupling to a second input, coupling to an address input, and coupling to a processing element, at least until said processing element prepares a result data word indicative of a second one of said plurality of network interfaces, and said instruction decoder recognizes a part of said output as indicative of readiness to switch said packet; and sending said packet to said second one of said plurality of network interfaces.
-
-
36. A method for switching packets, comprising
receiving a packet from a first one of a plurality of network interfaces; -
performing a plurality of tree memory operations, each said tree memory operation comprising simultaneously (a) retrieving a first data word from said packet, (b) comparing a second data word from said packet with a test data word, (c) executing a processor instruction in response to a prior tree memory operation, and (d) selecting a next tree memory operation in response to said prior tree memory operation; at least one said step of executing a processor instruction comprising preparing a result data word indicative of a second one of said plurality of network interfaces; and sending said packet to said second one of said plurality of network interfaces.
-
Specification