Network switch with deterministic longest prefix match lookup

An integrated circuit for a network switch, comprising:

• an input port to receive network packets;
• an output port to transmit the network packets;
• switching logic intermediate the input port and output port, the switching logic comprising:
• a packet pipeline including a plurality of serially-coupled stages for performing longest prefix matching lookups on the network packets received at the input port;
• and
• a plurality of memory blocks wherein each memory block is assigned to at most one of the plurality of serially-coupled stages in the packet pipeline, but at least one of the plurality of serially-coupled stages is coupled to multiple of the plurality of memory blocks, the plurality of memory blocks being configured to obtain addresses for forwarding the packets when the packets are transmitted from the output port;
• wherein each packet passes through each stage of the pipeline, and each stage performs a longest prefix matching operation on the packet in its stage.

A method of performing longest prefix matching lookups in a network switch, comprising:

• transmitting packets through the network switch using a pipeline including multiple pipeline stages that are serially coupled together, wherein each pipeline stage is associated with a respective group of one or more packet prefix lengths;
• configuring memory blocks so that each memory block is associated with at most one of the multiple pipeline stages and at least one stage of the multiple pipeline stages is coupled to multiple memory blocks, and wherein at least one memory block is dynamically re-assigned from a first stage to a second stage, the second stage being different from the first stage;
• at each pipeline stage, performing a longest prefix matching lookup in all of the memory blocks that are associated with the pipeline stage;
• and
• determining a forwarding address for the packet using the longest prefix matching lookup found by the multiple pipeline stages.