Method for facilitating forwarding of data packets through a node of a data transfer network using multiple types of forwarding tables

• US 7,539,772 B2
• Filed: 08/20/2007
• Issued: 05/26/2009
• Est. Priority Date: 12/17/2003
• Status: Expired due to Fees

• Current Assignee: GlobalFoundries, Inc.
• Original Assignee: International Business Machines Corporation
• Inventors: Herring, Jay R., Rider, Scot H.
• Primary Examiner(s): Tran; Philip B
• Application Number:
  US11/841,163
• Publication Number:
  US 20070280248A1
• Time in Patent Office: 645 Days
• Field of Search: 709238-242, 709/245, 709/219, 370/351, 370/395.31
• US Class Current: 709/238
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/54 Organization of routing tables
• CPC Class Codes: H04L 45/742 Route cache; Operation thereof

Abstract

A method is provided for reducing size of memory required for a switching node'"'"'s forwarding table by employing forwarding tables of different types to map received data packets addressed to downstream nodes and upstream nodes to appropriate output ports of the switching node. The method includes receiving a data packet at a data transfer node of a network and selecting a forwarding table from multiple types of forwarding tables accessible by the node based on an attribute associated with the received data packet, and mapping the data packet to an output port of the node utilizing the forwarding table selected from the multiple types of forwarding tables based on the attribute associated with the packet.

Claims

1. A packet processing method for a node of a data transfer network, said method comprising:

receiving a data packet at a node of the data transfer network;

selecting a forwarding table from a plurality of types of forwarding tables, said selecting being based on an attribute associated with the data packet and including determining whether a value of the attribute falls within a defined range of attribute values, the defined range of attribute values being defined by at least one changeable value-range parameter, and applying a transformation to the value of the attribute, the transformation mapping a plurality of values of the attribute to a table index value, wherein the plurality of values of the attribute are assigned to a same port and wherein the transformation is defined by a changeable value-transformation parameter;

mapping the data packet to an output port of the node, said mapping utilizing the forwarding table selected by said selecting; and

wherein the plurality of types of forwarding tables comprises the linear forwarding table and the random forwarding table, and wherein the linear forwarding table is located in a memory space by a linear-forwarding-table base address and a linear-forwarding-table mask, and a remaining portion of the memory space is assigned to the random forwarding table.

2. The method of claim 1, wherein the plurality of types of forwarding tables further comprises a content-addressable memory forwarding table.

3. The method of claim 1, wherein the attribute comprises a destination address of the received data packet.

4. A method of configuring a node of a data transfer network comprising:

providing a plurality of types of forwarding tables, the forwarding tables being used in mapping received data packets to output ports of the node;

dynamically selecting, by selection logic, a forwarding table from the plurality of types of forwarding tables for a data packet received by the node, the selection logic utilizing an attribute associated with the data packet in the selecting;

mapping, by mapping logic, the received data packet to an output port of the node, the mapping utilizing the forwarding table dynamically selected by the selection logic for the received data packet;

wherein the plurality of types of forwarding tables include a linear forwarding table and the mapping logic further comprises attribute-transformation logic, the attribute-transformation logic mapping a plurality of attribute values of received data packets to a linear forwarding table index of the linear forwarding table, thereby reducing required entries in the linear forwarding table; and

wherein the plurality of types of forwarding tables comprises the linear forwarding table and the random forwarding table, and wherein the linear forwarding table is located in a memory space by a linear-forwarding-table base address and a linear-forwarding-table mask, and a remaining portion of the memory space is assigned to the random forwarding table.

5. The method of claim 4, wherein the plurality of types of forwarding tables further comprises a content-addressable memory forwarding table.

6. The method of claim 4, wherein the method further comprises providing at least one changeable selection parameter used by the selection logic for selecting a forwarding table.

7. The method of claim 4, wherein the mapping logic further comprises a changeable attribute-transformation parameter, the changeable attribute-transformation parameter being employed in the mapping of the plurality of attribute values.

8. The method of claim 7, wherein the attribute-transformation logic comprises logic for discarding a number of bits indicated by the attribute-transformation parameter from the plurality of attribute values.