Dynamic routing over secure networks

• US 6,744,774 B2
• Filed: 06/27/2002
• Issued: 06/01/2004
• Est. Priority Date: 06/27/2002
• Status: Expired due to Term

• Current Assignee: Nokia Technologies Oy (Nokia Corporation)
• Original Assignee: Nokia, Inc. (Nokia Corporation)
• Inventors: Sharma, Atul
• Primary Examiner(s): Jung, Min
• Application Number:
  US10/180,081
• Publication Number:
  US 20040001497A1
• Time in Patent Office: 705 Days
• Field of Search: 370/401, 370/402, 370/409, 370/465, 370/254, 370/255, 370/257, 709/242, 709/238
• US Class Current: 370/401
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/03 by updating link state protocols
• CPC Class Codes: H04L 45/033 by updating distance vector protocols
• CPC Class Codes: H04L 45/12 Shortest path evaluation
• CPC Class Codes: H04L 45/302 Route determination based on requested QoS
• CPC Class Codes: H04L 45/48 Routing tree calculation
• CPC Class Codes: H04L 63/0272 Virtual private networks
• CPC Class Codes: H04L 63/164 at the network layer

Abstract

Systems and methods are provided for routing packets on a network based on interface information of a routing gateway or a neighboring gateway. One embodiment includes updating a routing table using interface information shared by a neighboring router. Another embodiment includes making routing decisions based on interface information from a neighboring router. A further embodiment includes making routing decisions based on priorities determined from interface information. Another embodiment includes the steps of updating a routing table on a first gateway, which includes the steps of receiving data disclosing interface information on a neighboring second gateway, and updating a routing table based on the interface information. The interface information for the neighboring second gateway includes identification of communication interfaces on the second gateway, an interface type for each of the interfaces, and a physical type interface on which each virtual type interface is overlaid.

Claims

1. A method of updating a routing table on a first gateway, the method comprising the steps of:

receiving data disclosing interface information on a neighboring second gateway, the interface information comprising;

an interface_id for each one of communication interfaces located on the second gateway, the interface_id comprising an identification of the corresponding communication interface; and

identification of a neighbor connected to each one of the interfaces; and

updating the routing table to include at least some of the interface information.

2. A method of updating a routing table on a first gateway, the method comprising the steps of:

receiving data disclosing interface information on a neighboring second gateway, the interface information comprising;

an interface id for each one of communication interfaces located on the second gateway, the interface id comprising an identification of the corresponding communication interface; and

identification of a neighbor connected to each one of the interfaces; and

updating the routing table to include at least some of the interface information;

wherein the interface information further comprises;

an interface type for each one of the communication interfaces, the interface type comprising one of a virtual type and a physical type.

3. The method of claim 2, wherein the interface information further comprises:

overlay information for a virtual type interface of the communication interfaces, the overlay information identifying a physical type interface of the communication interfaces on which the virtual type interface is overlaid.

4. The method of claim 2, wherein the first gateway uses a distance-vector routing protocol and the step of receiving data comprises the steps of:

receiving a routing message from the second gateway, the routing message comprising distance vector information for transmitting messages between the second gateway and destination gateways connected to the second gateway, the routing message further comprising a nexthop_link indicator for each destination gateway, the nexthop_link indicator comprising information disclosing the interface_id for one of the interfaces on the second gateway that corresponds to a nexthop from the second gateway toward a destination gateway associated with the nexthop_link indicator; and

receiving an interface message from the second gateway.

5. The method of claim 4, wherein the interface message comprises an interface list disclosing:

the interface type corresponding to each one of the communication interfaces,

a neighbor connected to each one of the communication interfaces, and

for each virtual type interface, overlay information identifying a physical type interface of the communication interfaces on which the virtual type interface is overlaid.

6. The method of claim 4 wherein the distance-vector protocol comprises a protocol known as Routing Information Protocol (RIP) and the routing message comprises a Response Message.

7. The method of claim 4, wherein each one of the nexthop_link indicators points to a corresponding entry in the interface message.

8. The method of claim 4, wherein the step of updating the routing table comprises inserting the nexthop_link indicator in the routing table.

9. The method of claim 2, wherein the routing table comprises a global routing table and the method further comprises the step of updating routing priorities on the global routing table for the first gateway based on the interface information.

10. A method of updating a routing table on a first gateway, the method comprising the steps of:

receiving data disclosing interface information on a neighboring second gateway, the interface information comprising;

an interface id for each one of communication interfaces located on the second gateway, the interface id comprising an identification of the corresponding communication interface; and

identification of a neighbor connected to each one of the interfaces; and

updating the routing table to include at least some of the interface information;

wherein the gateway uses a link state routing protocol and the step of receiving data comprises the step of receiving a routing message from the second gateway, the routing message comprising link state information and overlay information, the overlay information identifying a physical type interface of the communication interfaces on which a virtual type interface of the communication interfaces is overlaid.

11. The method of claim 10, wherein the routing message further comprises an interface_id for each one of the communication interfaces, the interface_id identifying one of the communication interfaces on the second gateway.

12. The method of claim 10, wherein the link state routing protocol comprises a protocol known as Open Shortest Path First (OSPF) and the routing message comprises a link state advertisement.

13. The method of claim 10, further comprising the step of inserting a nexthop_link indicator for each route in the routing table, the nexthop_link indicator comprising information disclosing the interface_id for one of the interfaces on the second gateway that corresponds to a neighbor gateway associated with the corresponding route.

14. A method of updating a routing table on a first gateway, the method comprising the steps of:

receiving data disclosing interface information on a neighboring second gateway, the interface information comprising;

an interface id for each one of communication interfaces located on the second gateway, the interface id comprising an identification of the corresponding communication interface; and

identification of a neighbor connected to each one of the interfaces;

updating the routing table to include at least some of the interface information; and

updating an interface table, the interface table comprising information disclosing;

the interface_id for each one of communication interfaces located on the second gateway;

the interface type for each interface_id, the interface type comprising one of a virtual type and a physical type;

a neighbor connected to each one of the interfaces; and

a physical type interface on which each virtual type interface is overlaid.

15. The method of claim 14, wherein the first gateway uses a distance vector routing protocol and the interface table is updated based on an interface message received from the second gateway.

16. The method of claim 14, wherein the first gateway uses a link state routing protocol and the interface table is updated based on information provided in a link state advertisement, the link state advertisement comprising information identifying the interfaces on the second gateway, a type of each one of the interfaces on the second gateway, a neighbor gateway connected to each one of the interfaces, and overlay information disclosing a physical interface of the communication interfaces on which a virtual interface of the communication interfaces is overlaid.

17. A method of routing a data packet at a first gateway, the method comprising the steps of:

receiving the data packet;

choosing a first route for routing the packet based on a routing protocol, the first route comprising a first next hop to a second gateway and a second next hop from the second gateway to a third gateway;

determining an interface on the second gateway corresponding to the second next hop;

identifying the third gateway based on the interface; and

if the identity of the third gateway matches the first gateway, choosing a second potential route excluding the second gateway.

18. The method of claim 17, wherein the step of determining an interface comprises the step of consulting a routing table on the first gateway.

19. A method of routing a data packet at a first gateway, the method comprising the steps of:

receiving the data packet;

choosing a first route for routing the packet based on a routing protocol, the first route comprising a first next hop to a second gateway and a second next hop from the second gateway to a third gateway;

determining an interface on the second gateway corresponding to the second next hop;

identifying the third gateway based on the interface; and

if the identity of the third gateway matches the first gateway, choosing a second potential route excluding the second gateway;

wherein the step of determining an interface comprises the step of consulting a routing table on the first gateway, the routing table comprises a nexthop_link indicator for the first route, the nexthop_link indicator comprising information identifying an interface on the second gateway that corresponds to the first route and a pointer pointing to an entry in an interface table for the second gateway corresponding to the interface.

20. The method of claim 19, wherein the routing protocol is selected from the group consisting of distance vector protocols and link state protocols.

21. The method of claim 19, wherein the entry in the interface table comprises:

an interface_id identifying the interface on the second gateway;

an interface type corresponding to the interface, the interface type comprising one of a virtual type and a physical type;

a neighbor connected to the interface; and

if the interface type is a virtual type, overlay information identifying a physical type interface on which the virtual type interface is overlaid.

22. A method of routing a data packet at a gateway, the method comprising the steps of:

updating a routing table on a gateway, the routing table comprising a first route and a second route, the step of updating comprising the steps of;

determining a local interface for each one of the routes;

determining an interface type for each one of the local interfaces; and

assigning a priority to each one of the routes based on the corresponding interface type; and

choosing between the first route and the second route based on the corresponding priorities.

23. A method of routing a data packet at a gateway, the method comprising the steps of:

updating a routing table on a gateway, the routing table comprising a first route and a second route, the step of updating comprising the steps of;

determining a local interface for each one of the routes;

determining an interface type for each one of the local interfaces; and

assigning a priority to each one of the routes based on the corresponding interface type; and

choosing between the first route and the second route based on the corresponding priorities;

wherein the interface type for the first route interface comprises a virtual type and the interface type for the second route interface comprises a physical type, the method further comprising the steps of assigning a higher priority to the first route than to the second route, the step of choosing comprising the step of selecting the first route.

24. The method of claim 23, wherein a cost associated with said first route is higher than a cost associated with said second route.

25. A method of routing a data packet at a gateway, the method comprising the steps of:

updating a routing table on a gateway, the routing table comprising a first route and a second route, the first route having a higher cost determined by a metric than the second route, the first route comprising a single hop to the destination, the second route comprising more than one hop to the destination, the step of updating comprising the step of assigning a priority to each one of the routes based on the whether the route comprises one hop or more than one hop, the priority associated with the first route being higher than the second route; and

choosing between the first route and the second route based on the corresponding priorities.

26. A first gateway adapted to forward data packets, the gateway comprising:

a first communications interface;

a memory; and

a processor for performing steps according to instructions stored in the memory, the steps comprising;

receiving via the first communications interface data disclosing interface information on a neighboring second gateway, the interface information comprising;

an interface_id for each one of communication interfaces located on the second gateway, the interface_id comprising an identification of the corresponding second gateway interface; and

identification of a neighbor connected to each one of the second gateway interfaces; and

updating a routing table stored in the memory to include at least some of the interface information.

27. A first gateway adapted to forward data packets, the gateway comprising:

a first communications interface;

a memory; and

a processor for performing steps according to instructions stored in the memory, the steps comprising;

receiving via the first communications interface data disclosing interface information on a neighboring second gateway, the interface information comprising;

an interface id for each one of communication interfaces located on the second gateway, the interface_id comprising an identification of the corresponding second gateway interface; and

identification of a neighbor connected to each one of the second gateway interfaces; and

updating a routing table stored in the memory to include at least some of the interface information;

wherein the interface information further comprises;

overlay information for a virtual type interface of the second gateway interfaces, the overlay information identifying a physical type interface of the second gateway interfaces on which the virtual type interface is overlaid.

28. The first gateway of claim 27, wherein the interface information further comprises:

an interface type for each one of the second gateway interfaces, the interface type comprising one of a virtual type and a physical type.

29. The first gateway of claim 27, wherein the first gateway uses a distance-vector routing protocol and the step of receiving data comprises the steps of:

receiving via the first communications interface a routing message from the second gateway, the routing message comprising distance vector information for transmitting messages between the second gateway and destination gateways connected to the second gateway, the routing message further comprising a nexthop_link indicator for each destination gateway, the nexthop_link indicator comprising information disclosing the interface_id for one of the interfaces on the second gateway that corresponds to a nexthop from the second gateway toward a destination gateway associated with the nexthop_link indicator; and

receiving an interface message from the second gateway.

30. The first gateway of claim 29, wherein the interface message comprises an interface list disclosing:

the interface type corresponding to each one of the second gateway interfaces,

a neighbor connected to each one of the communication interfaces, and

for each virtual type interface, overlay information identifying a physical type interface of the communication interfaces on which the virtual type interface is overlaid.

31. The first gateway of claim 29, wherein the step of updating the routing table comprises inserting the nexthop_link indicator in a routing table.

32. The first gateway of claim 27, wherein the first gateway uses a link state routing protocol and the step of receiving data comprises the step of receiving a routing message from the second gateway, the routing message comprising link state information and overlay information, the overlay information identifying a physical type interface of the communication interfaces on which each virtual type interface of the communication interfaces is overlaid.

33. The first gateway of claim 32, wherein the routing message further comprises an interface_id for each one of the second gateway interfaces, the interface_id identifying one of the second gateway interfaces.

34. The first gateway of claim 27, wherein the processor performs the further step comprising updating routing priorities on a global routing table for the first gateway based on the interface information.

35. A first gateway adapted to forward data packets, the gateway comprising:

a communications interface;

a memory; and

a processor for performing steps according to instructions stored in the memory, the steps comprising;

receiving a data packet via the communications interface;

choosing a first route for routing the packet based on a routing protocol, the first route comprising a first next hop to a second gateway and a second next hop from the second gateway to a third gateway;

determining an interface on the second gateway corresponding to the second next hop;

identifying the third gateway based on the second gateway interface; and

if the identity of the third gateway matches the first gateway, choosing a second potential route excluding the second gateway.

36. A gateway adapted to forward data packets, the gateway comprising:

a plurality of communications interfaces;

a memory; and

a processor for performing steps according to instructions stored in the memory, the steps comprising;

updating a routing table on the gateway, the routing table comprising a first route and a second route, the step of updating comprising the steps of;

determining a local interface of the plurality of communication interfaces for each one of the routes;

determining an interface type for each one of the local interfaces; and

assigning a priority to each one of the routes based on the corresponding interface type;

receiving a data packet via the communications interface;

choosing between the first route and the second route for forwarding the data packet based on the corresponding priorities; and

forwarding the data packet.

37. A gateway adapted to forward data packets, the gateway comprising:

a plurality of communications interfaces;

a memory; and

a processor for performing steps according to instructions stored in the memory, the steps comprising;

updating a routing table on the gateway, the routing table comprising a first route and a second route, the step of updating comprising the steps of;

determining a local interface of the plurality of communication interfaces for each one of the routes;

determining an interface type for each one of the local interfaces; and

assigning a priority to each one of the routes based on the corresponding interface type;

receiving a data packet via the communications interface;

choosing between the first route and the second route for forwarding the data packet based on the corresponding priorities; and

forwarding the data packet;

wherein the interface type for the first route interface comprises a virtual type and the interface type for the second route interface comprises a physical type, the method further comprising the steps of assigning a higher priority to the first route than to the second route, and the step of choosing comprises the step of selecting the first route.

38. A computer readable medium for storing computer readable instructions for performing steps on a first gateway, the steps comprising:

receiving data disclosing interface information on a neighboring second gateway, the interface information comprising;

an interface_id for each one of communication interfaces located on the second gateway, the interface_id comprising an identification of the corresponding second gateway interface; and

identification of a neighbor connected to each one of the second gateway interfaces; and

updating a routing table stored to include at least some of the interface information.

39. A computer readable medium for storing computer readable instructions for performing steps on a first gateway, the steps comprising:

receiving a data packet;

choosing a first route for routing the packet based on a routing protocol, the first route comprising a first next hop to a second gateway and a second next hop from the second gateway to a third gateway;

determining an interface on the second gateway corresponding to the second next hop;

identifying the third gateway based on the second gateway interface; and

if the identity of the third gateway matches the first gateway, choosing a second potential route excluding the second gateway.