Layer-3 network routing with RPR layer-2 visibility

• US 7,551,599 B2
• Filed: 03/29/2004
• Issued: 06/23/2009
• Est. Priority Date: 03/29/2004
• Status: Active Grant

• Current Assignee: Smart Path Connections LLC
• Original Assignee: Corrigent Systems Ltd. (Orckit-Corrigent )
• Inventors: Levit, Alex, Agmon, Gideon, Menahemi, Zvika, Solomon, Ronen
• Primary Examiner(s): Chan, Wing F
• Assistant Examiner(s): Jones, Prenell P
• Application Number:
  US10/812,321
• Publication Number:
  US 20050213558A1
• Time in Patent Office: 1,912 Days
• Field of Search: 370/351, 370/419, 370/223, 370/392, 370/254, 370/222, 370/238, 370/405, 370/406, 370/221, 370/230, 370/255, 370/401, 709/238, 709/227, 709/201, 709/239, 709/242, 709/224, 709/223, 705/1, 705/10
• US Class Current: 370/351
• CPC Class Codes: H04L 12/42 Loop networks
• CPC Class Codes: H04L 12/4633 Interconnection of networks using encapsulation techniques, e.g. tunneling
• 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/22 Alternate routing

Abstract

Routing tables of OSI layer-3 network elements are modified in order to enable entry to a RPR subnet at different entry points. This enables virtual tunnels or routing paths to utilize all existing entry links to the RPR subnet and to minimize cost factors, such as the number of RPR spans required to traverse the RPR subnet from the entry point to a destination RPR node. The routing tables of RPR subnet elements are modified, such that traffic leaving different elements but destined for the same network location outside the RPR subnet may have individualized RPR exit nodes. The respective RPR exit points for the network elements are chosen to minimize cost factors, such as the number of RPR spans required to reach the exit node from each RPR node.

Claims

1. A method for obtaining ingress to a layer-2 ring network to reach nodes thereof, said nodes including ingress nodes that couple said ring network to an external layer-3 network, the method comprising the steps of:

in said ingress nodes, creating entries in a host table, each of said entries comprising an address of a respective one of said nodes of said ring network and a metric determined responsively to a topology of said ring network;

thereafter uploading said host table to external elements of said layer-3 network;

defining paths from said external elements to designated ones of said nodes of said ring network, by selecting one of said ingress nodes for each of said paths responsively to said metric; and

transmitting data from network elements that are external to said ring network to at least one of said nodes via a selected one of said paths.

2. The method according to claim 1, wherein said ring network is a RPR subnet.

3. The method according to claim 1, wherein said ingress nodes are selected responsively to a minimum value of said metric.

4. The method according to claim 1, wherein said ingress nodes are selected responsively to a maximum value of said metric.

5. The method according to claim 1, wherein said step of defining paths is performed in each of one or more of said external elements.

6. The method according to claim 1, wherein said step of defining paths comprises dynamically defining virtual tunnels.

7. The method according to claim 1, wherein said layer-3 network is an IP network, and wherein said step of uploading comprises flooding router LSA'"'"'s with a mask.

8. The method according to claim 7, wherein said step of flooding comprises flooding stub networks.

9. The method according to claim 7, wherein said mask is a 32-bit mask.

10. The method according to claim 1, wherein said step of uploading comprises external LSA advertising to said layer-3 network.

11. The method according to claim 1, wherein said metric comprises a cost factor that is computed between one of said ingress nodes and said respective one of said nodes.

12. The method according to claim 11, wherein said cost factor varies with a number of layer-2 spans between said one ingress node and said respective one of said nodes.

13. The method according to claim 11, wherein said step of defining paths comprises computing a total cost based on said cost factor and on interface costs that are assigned in said layer-3 network, and selecting said paths so as to minimize said total cost.

14. The method according to claim 1, wherein said metric is determined responsively to a number of hops between said ingress nodes and said respective one of said nodes.

15. The method according to claim 14, wherein said ingress nodes are configured with an interface cost on said layer-3 network, and wherein said metric is determined proportionally to said interface cost and to said number of hops.

16. The method according to claim 14, wherein said ingress nodes are configured with an interface cost on said layer-3 network, and wherein said metric is determined by said interface cost divided by said number of hops.

17. A computer software product, including a computer-readable medium in which computer program instructions are stored, which instructions, when read by a computer, cause the computer to perform a method for obtaining ingress from an external layer-3 network to a layer-2 ring network to reach nodes thereof, comprising the steps of:

configuring ingress nodes of said ring network to create entries in a host table, each of said entries comprising an address of a respective one of said nodes of said ring network and a metric;

configuring said ingress nodes to thereafter upload said host table to external elements of a data network that interfaces with said ring network via said ingress nodes;

configuring said external elements to define paths from said external elements to designated ones of said nodes of said ring network, each of said paths leading through a selected one of said ingress nodes responsively to said metric; and

transmitting data from network elements that are external to said ring network to at least one of said nodes via a selected one of said paths.

18. The computer software product according to claim 17, wherein said ring network is a RPR subnet.

19. The computer software product according to claim 17, wherein said ingress nodes are selected responsively to a minimum value of said metric.

20. The computer software product according to claim 17, wherein said ingress nodes are selected responsively to a maximum value of said metric.

21. The computer software product according to claim 17, wherein said paths are virtual tunnels.

22. The computer software product according to claim 17, wherein said ingress nodes are configured to upload said host table by flooding router LSA'"'"'s with a mask.

23. The computer software product according to claim 22, wherein flooding comprises flooding stub networks.

24. The computer software product according to claim 22, wherein said mask is a 32-bit mask.

25. The computer software product according to claim 17, wherein said ingress nodes are configured to upload said host table by external LSA advertising to said data network.

26. The computer software product according to claim 17, wherein said metric comprises a cost factor that is computed between one of said ingress nodes and said respective one of said nodes.

27. The computer software product according to claim 26, wherein said cost factor varies with a number of layer-2 spans between said one ingress node and said respective one of said nodes.

28. The computer software product according to claim 26, wherein said paths are defined by computing a total cost based on said cost factor and on interface costs that are assigned in said layer-3 network, and selecting said paths so as to minimize said total cost.

29. The computer software product according to claim 17, wherein said metric comprises a number of hops between said ingress nodes and said respective one of said nodes.

30. The computer software product according to claim 29, wherein said ingress nodes are configured with an interface cost on said layer-3 network, and wherein said metric is determined proportionally to said interface cost and to said number of hops.

31. The computer software product according to claim 29, wherein said ingress nodes are configured with an interface cost on said layer-3 network, and wherein said metric is determined by said interface cost divided by said number of hops.

32. A network routing system for obtaining ingress from an external layer-3 network to a layer-2 ring network to reach nodes thereof, comprising:

first routers disposed in ingress nodes of said ring network, said first routers being configured for creating entries in a host table, each of said entries comprising an address of a respective one of said nodes of said ring network and a metric;

said first routers being further configured for uploading said host table to external elements of a data network that interfaces with said ring network via said ingress nodes;

a second router disposed in at least one of said external elements, said second router being configured for defining paths from said external elements to designated ones of said nodes of said ring network, each of said paths leading through a selected one of said ingress nodes responsively to said metric; and

transmitting data from network elements that are external to said ring network to at least one of said nodes via a selected one of said paths.

33. The network routing system according to claim 32, wherein said ring network is a RPR subnet.

34. The network routing system according to claim 32, wherein said ingress nodes are selected responsively to a minimum value of said metric.

35. The network routing system according to claim 32, wherein said ingress nodes are selected responsively to a maximum value of said metric.

36. The network routing system according to claim 32, wherein said paths are virtual tunnels.

37. The network routing system according to claim 32, wherein said first routers perform uploading by flooding router LSA'"'"'s with a mask.

38. The network routing system according to claim 37, wherein said step of flooding comprises flooding stub networks.

39. The network routing system according to claim 37, wherein said mask is a 32-bit mask.

40. The network routing system according to claim 32, wherein said first routers perform uploading by external LSA advertising to said data network.

41. The network routing system according to claim 32, wherein said metric comprises a cost factor that is computed between one of said ingress nodes and said respective one of said nodes.

42. The network routing system according to claim 41, wherein said cost factor varies with a number of layer-2 spans between said one ingress node and said respective one of said nodes.

43. The network routing system according to claim 41, wherein said paths are defined by computing a total cost based on said cost factor and on interface costs that are assigned in said layer-3 network, and selecting said paths so as to minimize said total cost.

44. The network routing system according to claim 32, wherein said metric comprises a number of hops between said ingress nodes and said respective one of said nodes.

45. The network routing system according to claim 44, wherein said ingress nodes are configured with an interface cost on said layer-3 network, and wherein said metric is determined proportionally to said interface cost and to said number of hops.

46. The network routing system according to claim 44, wherein said ingress nodes are configured with an interface cost on said layer-3 network, and wherein said metric is determined by said interface cost divided by said number of hops.

47. A method for obtaining egress from a layer-2 ring network to an external layer-3 network, comprising the steps of:

in nodes of said ring network creating entries in a host table, each of said entries comprising an address of a respective one of said nodes of said ring network and a metric determined responsively to a topology of the ring network;

defining paths from said nodes through egress nodes of said ring network to external elements in said external layer-3 network;

selecting one of said paths responsively to said metric; and

transmitting data from at least one of said nodes via said selected one of said paths to network elements that are external to said ring network.

48. The method according to claim 47, wherein said ring network is a RPR subnet.

49. The method according to claim 47, wherein said egress nodes are selected responsively to a minimum value of said metric.

50. The method according to claim 47, wherein said egress nodes are selected responsively to a maximum value of said metric.

51. The method according to claim 47, wherein said step of defining paths comprises dynamically defining virtual tunnels.

52. The method according to claim 47, further comprising the step of memorizing said paths in said host table of said nodes.

53. The method according to claim 47, wherein said metric comprises a cost factor that is computed between one of said egress nodes with said ring network and said respective one of said nodes.

54. The method according to claim 53, wherein said cost factor varies with a number of layer-2 spans between said one egress node and said respective one of said nodes.

55. The method according to claim 53, wherein said paths are defined by computing a total cost based on said cost factor and on interface costs that are assigned in said layer-3 network, and selecting said paths so as to minimize said total cost.

56. The method according to claim 47, wherein said metric comprises a number of hops between said egress nodes and said respective one of said nodes.

57. The method according to claim 56, wherein said egress nodes are configured with an interface cost on said layer-3 network, and wherein said metric is determined proportionally to said interface cost and to said number of hops.

58. The method according to claim 56, wherein said egress nodes are configured with an interface cost on said layer-3 network, and wherein said metric is determined by said interface cost divided by said number of hops.

59. A computer software product, including a computer-readable medium in which computer program instructions are stored, which instructions, when read by a computer, cause the computer to perform a method for obtaining egress from a layer-2 ring network to an external layer-3 network comprising the steps of:

in nodes of said ring network creating entries in a host table, each of said entries comprising an address of a respective one of said nodes of said ring network and a metric;

defining paths from said nodes through egress nodes of said ring network;

selecting one of said paths responsively to said metric; and

transmitting data from said nodes via said selected paths to network elements that are external to said ring network.

60. The computer software product according to claim 59, wherein said ring network is a RPR subnet.

61. The computer software product according to claim 59, wherein said egress nodes are selected responsively to a minimum value of said metric.

62. The computer software product according to claim 59, wherein said egress nodes are selected responsively to a maximum value of said metric.

63. The computer software product according to claim 59, wherein said step of defining paths comprises dynamically defining virtual tunnels.

64. The computer software product according to claim 59, further comprising a step of memorizing said paths in said host table of said nodes.

65. The computer software product according to claim 59, wherein said metric comprises a cost factor that is computed between one of said egress nodes with said ring network and said respective one of said nodes.

66. The computer software product according to claim 65, wherein said cost factor varies with a number of layer-2 spans between said one egress node and said respective one of said nodes.

67. The computer software product according to claim 65, wherein said paths are defined by computing a total cost based on said cost factor and on interface costs that are assigned in said layer-3 network, and selecting said paths so as to minimize said total cost.

68. The computer software product according to claim 59, wherein said metric comprises a number of hops between said egress nodes and said respective one of said nodes.

69. The computer software product according to claim 68, wherein said egress nodes are configured with an interface cost on said layer-3 network, and wherein said metric is determined proportionally to said interface cost and to said number of hops.

70. The computer software product according to claim 68, wherein said egress nodes are configured with an interface cost on said layer-3 network, and wherein said metric is determined by said interface cost divided by said number of hops.

71. A network routing system for obtaining egress from a layer-2 ring network to an external layer-3 network comprising:

a plurality of routers disposed in nodes of said ring network, said routers being configured for creating entries in a host table, each of said entries comprising an address of a respective one of said nodes of said ring network and a metric, said routers being further configured for defining paths from said nodes through egress nodes of said ring network, for selecting one of said paths responsively to said metric; and

for transmitting data from said nodes via said selected paths to network elements that are external to said ring network.

72. The network routing system according to claim 71, wherein said ring network is a RPR subnet.

73. The network routing system according to claim 71, wherein said egress nodes are selected responsively to a minimum value of said metric.

74. The network routing system according to claim 71, wherein said egress nodes are selected responsively to a maximum value of said metric.

75. The network routing system according to claim 71, wherein said paths are dynamic virtual tunnels.

76. The network routing system according to claim 71, wherein said paths are stored in said host table.

77. The network routing system according to claim 71, wherein said metric comprises a cost factor that is computed between one of said egress nodes with said ring network and said respective one of said nodes.

78. The network routing system according to claim 77, wherein said cost factor varies with a number of layer-2 spans between said one egress node and said respective one of said nodes.

79. The network routing system according to claim 77, wherein said paths are defined by computing a total cost based on said cost factor and on interface costs that are assigned in said layer-3 network, and selecting said paths so as to minimize said total cost.

80. The network routing system according to claim 71, wherein said metric comprises a number of hops between said egress nodes and said respective one of said nodes.

81. The network routing system according to claim 80, wherein said egress nodes are configured with an interface cost on said layer-3 network, and wherein said metric is determined proportionally to said interface cost and to said number of hops.

82. The network routing system according to claim 80, wherein said egress nodes are configured with an interface cost on said layer-3 network, and wherein said metric is determined by said interface cost divided by said number of hops.

83. A method for routing data through a layer-2 ring network, said ring network having interface nodes with external network elements of a data network and non-interface nodes, comprising the steps of:

in said interface nodes of said ring network creating first entries in a first host table, each of said first entries comprising an address of a respective one of said non-interface nodes and a first metric;

thereafter uploading said first host table to said external network elements; and

using said first host table identifying optimum ingress paths from said external network elements to said non-interface nodes, each of said ingress paths leading through one of said interface nodes responsively to said first metric;

in said non-interface nodes of said ring network creating second entries in a second host table, each of said second entries comprising an address of a respective one of said interface nodes and a second metric;

using said second host table identifying optimum egress paths from said non-interface nodes through different ones of said interface nodes of said ring network, responsively to said second metric; and

transmitting data to and from said ring network via said ingress paths and said egress paths.

84. The method according to claim 83, wherein said ring network is a RPR subnet.