Routing table for forwarding Internet Protocol (IP) packets through a communications network
View Patent ↗Described are a system and computer-implemented method for searching and updating a routing table for forwarding IP packets through a communications network. Records containing IP address prefixes are organized in a binary tree data structure. When inserting a new record, one of the records in the binary tree data structure is identified as an enclosing record having an associated record data range that encloses record data of the new record. An enclosing pointer of the new record is set to point to the identified enclosing record. When searching for a longest matching prefix for a destination IP address, the binary tree data structure is traversed and one of the records in the binary tree data structure is identified as an enclosing record, which is returned as the longest matching prefix.
1. A method of adding a new record to a plurality of records organized in a binary tree structure, the method comprising:
identifying one of the records organized in the binary tree structure as an enclosing record having an associated record data range that encloses record data of the new record;
setting an enclosing pointer of the new record to point to the identified enclosing record; and
identifying one of the records organized in the binary tree structure as a neighboring record of the new record, and setting a neighboring pointer of the new record to point to the neighboring record.
2. The method of claim 1 , further comprising identifying each record organized in the binary tree structure with record data that are enclosed by a record data range associated with the record data of the new record, and setting an enclosing pointer of each identified enclosed record to point to the new record.
3. The method of claim 1 , further comprising organizing the plurality of records according to a second data structure, inserting the new record into an insertion location in the second data structure, and inserting the new record into an insertion location in the binary tree structure.
4. The method of claim 1 , wherein the record data of the new record include an IP address prefix.
5. The method of claim 1 , further comprising identifying one of the records organized in the binary tree structure as a previous record having record data that more closely precedes in order the record data of the new record than any of the other records in the binary tree data structure.
6. The method of claim 5 , further comprising setting a next pointer of the previous record to point to the new record.
7. The method of claim 5 , wherein the step of identifying the enclosing record includes determining whether a record data range associated with the record data of the previous record encloses the record data of the new record.
8. The method of claim 5 , wherein the step of identifying the enclosing record includes following an enclosing pointer of the previous record to a candidate enclosing record in the binary tree structure if the record data range associated with the record data of the previous record does not enclose the record data of the new record.
9. The method of claim 1 , further comprising identifying one of the records organized in the binary tree structure as a next record having record data that more closely follows in order the record data of the new record than any other record in the binary tree data structure.
10. The method of claim 9 , further comprising setting a next pointer of the new record to point to the next record.
11. The method of claim 9 , further comprising setting an enclosing pointer of the next record to point to the new record if a record data range associated with the record data of the new record encloses record data of the next record.
12. The method of claim 9 , further comprising traversing a neighboring pointer of the next record to a neighboring record.
13. The method of claim 12 , further comprising setting an enclosing pointer of the neighboring record to point to the new record if a record data range associated with the record data of the new record encloses record data of the neighboring record.
14. A method of determining a route for an IP packet having a destination IP address, the method comprising:
organizing a plurality of records in a binary tree structure, each record having record data that include an IP address prefix for use in routing IP packets;
determining that the binary tree structure lacks a given record with record data that match the destination IP address;
identifying one of the records organized in the binary tree structure as a previous record having record data that more closely precede in order the record data of a new record than any of the other records in the binary tree structure; and
determining that the record data of the previous record are the longest matching prefix in the plurality of records for the destination IP address if the record data range associated with the record data of the previous record encloses the record data of the new record.
15. The method of claim 14 , further comprising traversing an enclosing pointer from the previous record to a candidate enclosing record if the record data range associated with the record data of the previous record does not enclose the record data of the new record.
16. The method of claim 15 further comprising determining that the record data of the candidate enclosing record is the longest matching prefix in the plurality of records for the destination IP address if a record data range associated with the record data of the candidate enclosing record encloses the record data of the new record.
17. The method of claim 14 , further comprising searching for the given record along a search path determined by the binary tree structure until a record is accessed that indicates that the binary tree structure is in an intermediate state, and searching for the given record along a second search path determined by the second data structure in response to the record that indicates that the binary tree structure is in an intermediate state.