Routing method and apparatus for optimising auto-tunnelling in a heterogeneous network

• US 7,349,427 B1
• Filed: 08/21/2002
• Issued: 03/25/2008
• Est. Priority Date: 12/21/2001
• Status: Expired due to Fees

• Current Assignee: RPX Clearinghouse LLC (RPX Corporation)
• Original Assignee: Nortel Networks Limited (Nortel Networks Corporation)
• Inventors: Houston, Allen, Gilmore, Derek, Canning, Terence
• Primary Examiner(s): Vu, Huy D.
• Assistant Examiner(s): MATTIS, JASON E
• Application Number:
  US10/225,541
• Time in Patent Office: 2,043 Days
• Field of Search: 370/466, 370/467, 370/400
• US Class Current: 370/466
• CPC Class Codes: H04L 12/4633 Interconnection of networks using encapsulation techniques, e.g. tunneling
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/12 Shortest path evaluation
• CPC Class Codes: H04L 45/52 Multiprotocol routers

Abstract

In the preferred embodiment, the invention provides a modified Shortest Path First routing algorithm for use in a heterogeneous network. The routing algorithm is modified to include predetermined heterogeneous characteristics of the network nodes and to take these characteristics into account when calculating the shortest paths. For example, information may be included in the algorithm which identifies heterogeneous network nodes as it calculates shortest paths. Once a node has been identified as heterogeneous, i.e., capable of supporting at least two protocol sets, this information is carried over into subsequent path entries created by the routing algorithm. The algorithm then uses the encapsulation capability identifier in the calculation of the shortest paths by including the cost of auto-tunneling between heterogeneous nodes to be taken into account when determining the short path.

Claims

1. A method of routing data packets in a heterogeneous network from a first network node, the method comprising the steps of:

creating entries in at least one database associated with said first network node, each entry relating to at least one respective path from said first network node to a respective destination node in the network;

determining, when creating an entry, if a network node located along said at least one respective path is a heterogeneous network node;

associating with each created entry, additional information comprising at least one heterogeneous characteristic of said heterogeneous network node, said at least one heterogeneous characteristic comprising a metric cost for encapsulating data packets provided in a form compliant with a first protocol set into a form compliant with a second protocol set;

creating subsequent entries in respect of paths to other network nodes;

associating said additional information with said subsequent entries; and

determining an optimum path along which said data packets are to be routed in dependence on said additional information.

2. A method as claimed in claim 1, wherein in the step of associating with each created entry, at least one heterogeneous characteristic comprises an additional field for a transport protocol indicator (TPID field) in said at least one database.

3. A method as claimed in claim 1, wherein in the step of associating with each created entry, at least one heterogeneous characteristic comprises an indicator that terminating tunnelling at said heterogeneous network node provides the least number of encapsulations along said at least one respective path.

4. A method as claimed in claim 1, wherein in the step of associating with each created entry, at least one heterogeneous characteristic comprises the encapsulation capability of the heterogeneous network node between a first protocol set and a second protocol set.

5. A method of routing data packets in a network as claimed in claim 1, wherein at least one characteristic identifies a heterogeneous network node as an optimum heterogeneous network node providing the lowest number of encapsulations/de-encapsulations along said at least one path to the destination node.

6. A method of routing data packets as claimed in claim 1, wherein said at least one database associated with said first network node comprises a first database for holding entries in respect of tentative paths to network nodes, and a second database for holding entries in respect of shortest paths to network nodes, the method further comprising the steps of:

deriving at least some of the entries in said second database from respective entries in said first database, wherein at least one characteristic indicates the cost of sending a data packet from the first node to the destination node of the entry, and

creating an entry in said second database in respect of the entry in the first database having the lowest cost indicator.

7. A method of routing data packets as claimed in claim 1, wherein said at least one database associated with said first network node comprises a first database for holding entries in respect of tentative paths to network nodes, and a second database for holding entries in respect of shortest paths to network nodes, the method further comprising the steps of:

deriving at least some of the entries in said second database from respective entries in said first database, wherein the additional information associated with each entry in said first database comprises an indication of the cost of sending a data packet from the first node to the destination node of the entry in accordance with a first protocol, and

creating an entry in said second database in respect of each entry in said first database having additional information indicating a different protocol set but having the same cost indicator.

8. A method of routing data packets as claimed in claim 1, wherein said at least one database associated with said first network node comprises a first database for holding entries in respect of tentative paths to network nodes, and a second database for holding entries in respect of shortest paths to network nodes, the method further comprising the steps of:

deriving at least some of the entries in said second database from respective entries in said first database, wherein the additional information associated with each entry in said first database comprises an indication of the cost of sending a data packet from the first node to the destination node of the entry in accordance with a first protocol, and

discarding an entry in said second database if its cost exceeds a tunnelling cost where at least one other entry exists to the same destination with the same protocol.

9. A method as claimed in claim 1, in which each database entry relating to at least one path to a destination node includes, in respect of the, or each path, a respective multi-protocol field for carrying said identifying information, wherein the, or each, multi-protocol field is set to identify a heterogeneous router in the respective path, or to indicate that no known heterogeneous router exists in said respective path.

10. A method as claimed in any one of claims 6, 7, or 8, wherein, when creating an entry in said first database in respect of at least one path to a destination node, the apparatus is arranged to determine if the destination node is a heterogeneous network node supporting at least two protocol sets only if at least one of a, or each, multi-protocol field is set to indicate that no other known heterogeneous network node exists in the respective path.

11. A method as claimed in claim 9, whereupon determining that said destination node supports is a heterogeneous network node supporting at least two protocol sets, the apparatus is arranged to set the respective multi-protocol field to identify said destination node.

19. A computer program product comprising computer useable instructions for causing a computer to implement the method as claimed in claim 1 or 2.

12. A method of routing data packets in a heterogeneous network from a first network node, the method comprising the steps of:

creating entries in at least one database associated with said first network node, each entry relating to at least one respective path from said first network node to a respective destination node in the network;

determining, when creating an entry, if a network node located along said at least one path is a heterogeneous network node;

associating with each heterogeneous network node an entry identifying at least one characteristic of said heterogeneous network node;

creating subsequent entries in respect of paths to other network nodes;

associating said heterogeneous characteristic information with said subsequent entries; and

determining an optimum path along which said data packets are to be routed in dependence on said heterogeneous characteristic information, wherein at least one characteristic of said heterogeneous network node indicates an encapsulation cost for encapsulating data packets provided in accordance with a first protocol set into a second protocol set.

13. A method as claimed in claim 12, wherein the encapsulation cost is predetermined for each heterogeneous node in the network.

14. Apparatus arranged to implement a method of routing data packets in a heterogeneous network from a first network node, the apparatus comprising:

means arranged to create entries in at least one database associated with said first network node, each entry relating to at least one respective path from said first network node to a respective destination node in the network,

means arranged to determine, when creating an entry, if a network node located along said at least one path is a heterogeneous network node,

means arranged to associate with each heterogeneous network node an entry identifying at least one characteristic of said heterogeneous network node, and

means arranged to create subsequent entries in respect of paths to other network nodes, and

means arranged to associate said heterogeneous characteristic information with said subsequent entries by determining an optimum path along which said data packets are to be routed in dependence on said heterogeneous characteristic information, wherein at least one characteristic of said heterogeneous network node indicates an encapsulation cost for encapsulating data packets providing in accordance with a first protocol set into a second protocol set.

15. Apparatus as claimed in claim 14, wherein said characteristic information identifies an optimum heterogeneous router providing the least number of encapsulations/de-encapsulations of data packets along said at least one path to the destination node.

16. An apparatus as claimed in claim 14, said first network node includes a first database for holding entries in respect of tentative paths to network nodes, and a second database for holding entries in respect of shortest paths to network nodes, the apparatus being arranged to derive at least some of the entries in said second database from respective entries in said first database.

17. A network node comprising an apparatus as claimed in claim 14.

18. A heterogeneous network comprising a plurality of network nodes, at least one of said plurality of network nodes comprising an apparatus as claimed in claim 17.

20. Apparatus arranged to implement a method of routing data packets in a heterogeneous network from a first network node, the apparatus comprising:

a processing component arranged to create entries in at least one database associated with said first network node, each entry relating to at least one respective path from said first network node to a respective destination node in the network,

a processing component arranged to determine, when creating an entry, if a network node located along said at least one path is a heterogeneous network node,

a processing component arranged to associate with each heterogeneous network node an entry identifying at least one characteristic of said heterogeneous network node, and

a processing component arranged to create subsequent entries in respect of paths to other network nodes, and

a processing component arranged to associate said heterogeneous characteristic information with said subsequent entries by determining an optimum path along which said data packets are to be routed in dependence on said heterogeneous characteristic information, wherein at least one characteristic of said heterogeneous network node indicates an encapsulation cost for encapsulating data packets providing in accordance with a first protocol set into a second protocol set.