Apparatus and method for switching packets using tree memory

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.

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.

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.

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.

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.

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.

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.

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.

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.