Robust NP-based data forwarding techniques that tolerate failure of control-based applications

• US 7,003,582 B2
• Filed: 06/20/2001
• Issued: 02/21/2006
• Est. Priority Date: 06/20/2001
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Vaidhyanathan, Natarajan, Basso, Claude, Verrilli, Colin Beaton, Yedavalli, Rama Mohan
• Primary Examiner(s): Lee, Thomas
• Assistant Examiner(s): ZHEN, LI B
• Application Number:
  US09/885,782
• Publication Number:
  US 20030009584A1
• Time in Patent Office: 1,707 Days
• Field of Search: 719/310, 370/395.31, 709/242
• US Class Current: 709/242
• CPC Class Codes: H04L 45/02 Topology update or discovery

Abstract

In a network environment including one or more network processing (NP) devices implementing for communicating packets, each NP device supporting a forwarding table comprising entries to enable forwarding of received data packets from a source device to a destination device according to a routing protocol via a network connection, the network device routing receiving updated forwarding table entries from one or more network control devices executing routing protocol applications, a system and method for updating forwarding table entries comprises: generating for each forwarding table entry update, a data structure indicating identification of the routing protocol application and a version of a particular routing protocol application instance generating the entry update, the data structure received by the forwarding table and incorporated within a respective forwarding table entry; identifying for deletion forwarding table entries having data structures matching a designated selection criteria; and, deleting the designated forwarding table entries. By doing this old forwarding table entries in the forwarding table are updated efficiently without disrupting packet forwarding process.

Claims

1. In a network environment including one or more network processing (NP) devices implemented for communicating packets, each NP device supporting a forwarding table comprising entries to enable forwarding of received data packets from a source device to a destination device according to a routing protocol via a network connection, said network processing device receiving forwarding table entries from one or more network control devices executing one or more routing protocol applications, a method for updating forwarding table entries of an existing forwarding table when a routing protocol application has failed in a network control device comprising:

a) generating for each forwarding table entry, a data structure indicating identification of the routing protocol application and a version of a particular routing protocol application instance generating said entry, said data structure received by said existing forwarding table and incorporated within a respective forwarding table entry;

b) upon re-starting a failed routing protocol application in a network control device, incrementing a version value of that re-started routing protocol application instance;

c) updating said data structures of the existing forwarding table entries with said incremented protocol application version values;

d) identifying for deletion those existing forwarding table entries having data structures matching a designated selection criteria including an indication of a prior protocol application version value; and

,

e) deleting said designated forwarding table entries, whereby forwarding table entries in said existing forwarding table are updated efficiently without disrupting packet forwarding process, and without disrupting network connectivity by having to reconstruct a new forwarding table.

2. The method for updating forwarding table entries in accordance with claim 1, wherein said selection criteria includes an identification of the routing protocol application, said identifying step d) including the step of identifying for deletion said forwarding table entries having g data structure indicating a specific routing protocol application.

3. The method for updating forwarding table entries in accordance with claim 1, wherein said selection criteria includes a range of values indicating versions of particular routing protocol application instances, said identifying step d) including the step of:

identifying for deletion said forwarding table entries having g data structure indicating a routing protocol application version value falling within a specific range of protocol application versions.

4. The method for updating forwarding table entries in accordance with claim 1, wherein said generating step a) is performed by one or more network control devices.

5. The method for updating forwarding table entries in accordance with claim 1, wherein said identifying step d) includes the step of generating said selection criteria.

6. The method for updating forwarding table entries in accordance with claim 1, wherein said step of generating said selection criteria is performed by said one or more network control devices.

7. The method for updating forwarding table entries in accordance with claim 1, wherein said forwarding table is a binary tree structure having leaves comprising said table entries, said identifying step d) including the step of implementing a scanning technique for ascertaining the indicated protocol application version number values at each of said leaves.

8. A system for ensuring packet routing in a networking environment including one or more network processing (NP) devices implemented for communicating packets, each NP device supporting a forwarding table comprising entries to enable forwarding of received data packets from a source device to a destination device according to a routing protocol via a network connection, said network processing device receiving forwarding table entries from one or more network control devices executing one or more routing protocol applications, said system comprising:

control mechanism for generating a data structure indicating identification of the routing protocol application and a version of a particular routing protocol application instance for each entry of an existing forwarding table, said control mechanism further incrementing a version value of a routing protocol application instance in response to re-starting that routing protocol application that has failed in a network control device;

communications interface for enabling forwarding of data structures updated to include said incremented version values of re-started routing protocol application instances to said NP device;

mechanism for incorporating received updated data structures into said forwarding table entry when updating said forwarding table entry; and

,

synchronization mechanism for identifying forwarding table entries having data structures matching a designated selection criteria that indicates a prior protocol application version value and deleting those forwarding table entries having data structures matching said designated selection criteria,

whereby forwarding table entries in said existing forwarding table are undated efficiently without disrupting packet forwarding process, and without disrupting network connectivity by having to reconstruct a new forwarding table.

9. The system as claimed in claim 8, wherein said selection criteria includes an identification of the routing protocol application, said synchronization mechanism identifying for deletion said forwarding table entries having data structure indicating said routing protocol application.

10. The system as claimed in claim 8, wherein said selection criteria includes a range of values indicating versions of particular routing protocol application instances, said synchronization mechanism identifying for deletion said forwarding table entries having a data structure indicating a routing protocol application version value falling within said range.

11. The system as claimed in claim 8, wherein said control mechanism further generates said selection criteria.

12. The system as claimed in claim 8, wherein said forwarding table is a binary tree structure having leaves comprising said table entries, said synchronization mechanism performing scanning of said leaves for ascertaining indicated protocol application version number values of the corresponding data structures at each of the leaves.