Longest prefix matching operations on a value in multiple interspersed prefix length search spaces to determine an overall longest prefix matching result in a packet switching system

An apparatus, comprising:

• a packet switching device including:
• a plurality of line cards with each of the plurality of line cards including:
• a plurality of external physical interfaces that communicate packets external to the packet switching device, and a plurality of internal physical interfaces;
• a plurality of routing stage modules, with each of the plurality of routing stage modules including a plurality of fabric module physical interfaces;
• and
• a plurality of links communicatively coupling the plurality of internal physical interfaces with the plurality of fabric module physical interfaces;
• wherein each of the plurality of line cards includes a line card network processor that performs a first longest prefix matching (LPM) operation based on a destination address of an externally-received packet, received on one of the plurality of external physical interfaces, in a distribution stage search space to determine a first longest matching prefix and corresponding first LPM result including a first length value specifying a prefix length of the first longest matching prefix, with the externally-received packet and said first LPM result being distributed to a routing stage module of the plurality of routing stage modules;
• and
• wherein each of the routing stage modules includes a routing stage network processor that performs a second LPM operation on a destination address of a distributed packet associated with a particular first LPM result in a routing stage search space to determine a second longest matching prefix and corresponding second LPM result including a second length value specifying a prefix length of the second longest matching prefix, that selects as an overall LPM result the first LPM result when the first length value is greater than the second length value else the second LPM result, that forwards the distributed packet to a particular line card of the particular line cards identified based on the overall LPM result;
• and
• wherein the distribution stage search space and the routing stage search space include non-default route prefixes with interspersed prefix lengths matching a same destination address of a packet.

A method, comprising:

• performing operations by a packet switching device including:
• a plurality of line cards, a plurality of routing stage modules, and a plurality of links communicatively coupling the plurality of line cards with the plurality of routing stage modules;
• wherein said operations include:
• receiving a particular packet on an external interface of a particular line card of the plurality of line cards;
• performing, by the particular line card, a first longest prefix matching (LPM) operation based on a destination address of the particular packet in a distribution stage search space to determine a first longest matching prefix and corresponding first LPM result including a first length value specifying a prefix length of the first longest matching prefix, with the particular packet and said first LPM result being distributed to a particular routing stage module of the plurality of routing stage modules;
• performing, by the particular routing stage module despite the first LPM result associated with information for forwarding the particular packet but to determine if a routing stage search space includes a longer matching prefix, a second LPM operation based on the destination address of the particular packet in the routing stage search space to determine a second longest matching prefix and corresponding second LPM result including a second length value specifying a prefix length of the second longest matching prefix;
• selecting, by the particular routing stage module, as an overall LPM result the first LPM result when the first length value is greater than the second length value else the second LPM result;
• and
• forwarding the particular packet from the particular routing stage module to an identifiable line card of the plurality of line cards corresponding to the overall LPM result;
• wherein the distribution stage search space and the routing stage search space include non-default route prefixes with interspersed prefix lengths matching the destination address of the particular packet.