Routing method and system

• US 20060159020A1
• Filed: 01/19/2006
• Published: 07/20/2006
• Est. Priority Date: 01/19/2005
• Status: Active Grant

• Current Assignee: Tejas Networks
• Original Assignee: Tejas Israel Ltd.
• Inventors: Porat, Haim
• Granted Patent: US 7,961,638 B2
• Time in Patent Office: Days
• US Class Current: 370/235
• CPC Class Codes: H04L 41/0803 Configuration setting
• CPC Class Codes: H04L 41/0856 by backing up or archiving configuration information
• CPC Class Codes: H04L 43/0882 Utilisation of link capacity
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/22 Alternate routing
• CPC Class Codes: H04L 45/243 using M+N parallel active paths
• CPC Class Codes: H04L 45/38 Flow based routing
• CPC Class Codes: H04L 45/42 Centralised routing

Abstract

A method for routing data over a telecommunications carrier network including at least two switching devices defining at least one physical link, the method including defining in advance a plurality of traffic flows, each associated with specific routing through at least one of the physical links in the network; configuring a routing system according to the traffic flows; collecting data of traffic transmitted over at least some of the traffic flows, calculating traffic statistics, from the collected data, for each of the flows in the network; and re-calculating the routing system configuration utilizing the calculated traffic statistics.

Claims

1. A method for routing data over a telecommunications carrier network including at least two switching devices defining at least one physical link, the method comprising:

defining in advance a plurality of traffic flows, each associated with specific routing through at least one of said physical links in the network;

configuring a routing system according to said traffic flows;

collecting data of traffic transmitted over at least some of said traffic flows,

calculating traffic statistics for each of said flows in the network, based on said collected data; and

re-calculating the routing system configuration utilizing said calculated traffic statistics.

2. The method according to claim 1, wherein said step of defining in advance includes receiving said traffic flows from a user.

3. The method according to claim 1, wherein said step of defining in advance includes storing definitions of said plurality of traffic flows in a prepared database.

4. The method according to claim 1, further comprising reconfiguring network devices in the network according to said re-calculated routing system configuration.

5. The method according to claim 4, wherein the reconfiguring step includes reconfiguring substantially simultaneously the network devices.

6. The method according to claim 1, further comprising:

defining in advance at least one pre-selected criterion for recalculation of said routing system configuration;

determining whether at least one of said pre-selected criteria is met; and

wherein the re-calculating step includes re-calculating the routing system configuration only when the least one pre-selected criteria is met.

7. The method according to claim 6, wherein said pre-selected criteria for recalculation of the routing system configuration are selected from the group including:

a change in network topology;

a change in at least one logical link;

a change in at least one selected monitored statistic;

a change of bandwidth utilization of at least one logical link above a pre-defined probability threshold value;

passage of a pre-selected period of time;

a change in a Quality of Service requirement;

a repeating pattern of bandwidth utilization.

8. The method according to claim 4, further comprising the step of determining whether the re-calculated routing system configuration improves at least one selected metric in said network, before said step of reconfiguring.

9. The method according to claim 8, wherein said metric is selected from:

Better network throughput;

Utilizing shortest possible paths;

Providing even distribution and use of network bandwidth resources;

Minimizing a

$\mathrm{ratio}<br><br>\frac{\sum <br><br>\mathrm{PIR}-\sum <br><br>\mathrm{CIR}}{\mathrm{Link\_Capacity}-\sum <br><br>\mathrm{CIR}}$

to a predefined or calculated value, for each and every link;

Limiting aggregated CIR and MBS traffic at any physical link to less than a value set by the user; and

Minimizing an overall cost of said routes.

10. The method according to claim 1, wherein the telecommunications carrier network is an Ethernet network.

11. The method according to claim 10, further including associating a specific Quality of Service with each of said plurality of logical links.

12. The method according to claim 10, further comprising assigning a private network address to each of said devices.

13. The method according to claim 12, wherein each said private network address includes information relating to at least one of said traffic flows.

14. The method according to claim 1, further comprising storing said traffic statistics.

15. The method according to claim 1, wherein said steps of defining through re-calculating are implemented off-line.

16. The method according to claim 1, wherein at least one of said switching devices includes a processor, and said steps of defining through re-calculating are implemented in said processor.

17. The method according to claim 16, further comprising implementing an initialization mode for the network, comprising the steps of:

inputting initial topology parameters into said processor;

inputting into said processor at least one pre-selected criterion for re-calculation of the routing system configuration;

causing the processor to devise a provisioning table from said initial parameters;

defining all required logical links;

performing a sanity check;

computing preliminary routes according to said input initial parameters, after successfully passing the sanity check;

preparing routing tables according to said preliminary routes; and

configuring all network devices by transferring said prepared routing tables to said network devices together with configuration commands.

18. The method according to claim 1, further including:

inputting a threshold value of probability of bandwidth utilization and a minimum period of time over which said probability must exceed said threshold value in a network;

calculating a bandwidth utilization probability value for each logical link;

comparing said calculated bandwidth utilization probability value with said input bandwidth utilization probability threshold value;

comparing a calculated period of time of said probability with the input time threshold value; and

if the value of the probability of bandwidth utilization over time exceeds the permitted threshold values, recalculating said routing system configuration; and

implementing said recalculated routing system configuration.

19. The method according to claim 18, further comprising the step of determining whether the recalculated routing system configuration increases throughput through said network, before said step of implementing.

20. The method according to claim 18, further comprising providing a configuration change mode of operation for the network comprising:

inputting to said processor new parameters for a configuration change;

providing a new provisioning table based on said input traffic flows and said new parameters;

reconfiguring all added and/or removed physical links;

recalculating said routing system configuration utilizing said newly input parameters, together with said calculated traffic statistics; and

reconfiguring all said network devices with new routing tables utilizing said recalculated routing system configuration.

21. The method according to claim 1, further comprising continually repeating said steps of collecting and calculating.

22. The method according to claim 1,

further comprising storing said calculated statistics;

and wherein;

said step of calculating includes calculating, from said stored statistics, updated traffic statistics for each of said flows in the network.

23. The method according to claim 16, wherein said processor includes a computer program for defining a routing scheme for routing the data through the network, for configuring the switching devices according to the routing scheme, for determining whether at least one pre-selected criterion for reconfiguring the switching devices has been met, for re-defining the routing scheme when at least one of the criteria has been met, and for reconfiguring the switching devices according to the re-defined routing scheme.

24. The method according to claim 16, wherein each switching device includes an identical computer program for defining a routing scheme for routing the data through the network, for configuring the switching devices according to the routing scheme, for determining whether at least one pre-selected criterion for reconfiguring the switching devices has been met, for identically re-defining the routing scheme when at least one of the criteria has been met, and for reconfiguring the switching devices according to the re-defined routing scheme.

25. A network management station for a telecommunications carrier network, comprising:

a processor configured to receive definitions of a plurality of traffic flows, each of the traffic flows associated with specific routing though at least one physical link in the network,

the processor further configured to

configure a routing system according to the traffic flows,

receive collected data of traffic transmitted over at least some of the traffic flows,

determine traffic statistics for each of the traffic flows in the network based on the collected data, and

re-calculate the routing system configuration utilizing the calculated traffic statistics.

26. The network management station according to claim 25, further comprising:

a user interface, the processor configured to receive said definitions of the plurality of traffic flows from a user via the user interface.

27. The network management station according to claim 25, wherein said processor is further configured to assign a private network address to each of said devices.

28. The network management station according to claim 27, wherein each said private network address includes information relating to at least one of said traffic flows.

29. A switching device for a telecommunications carrier network, comprising:

a processor configured to receive definitions of a plurality of traffic flows, each of the traffic flows associated with specific routing though at least one physical link in the network,

the processor further configured to

configure a routing system according to the traffic flows,

receive collected data of traffic transmitted over at least some of the traffic flows,

determine traffic statistics for each of the traffic flows in the network based on the collected data, and

re-calculate the routing system configuration utilizing the calculated traffic statistics.

30. The switching device according to claim 29, further comprising:

a user interface, the processor configured to receive said definitions of the plurality of traffic flows from a user via the user interface.

31. The switching device according to claim 29, wherein said processor is further configured to assign a private network address to each of said devices.

32. The network management station according to claim 31, wherein each said private network address includes information relating to at least one of said traffic flows.

33. A computer-readable storage medium containing a set of instructions for a computer, the set of instructions, when executed by the computer, causing the computer to perform the following steps:

configuring a routing system for a telecommunications carrier network according to pre-defined traffic flows, each of the traffic flows associated with specific routing though at least one physical link in the network;

collecting data of traffic transmitted over at least some of the traffic flows;

calculating traffic statistics for each of the traffic flows in the network, based on the collected data; and

re-calculating the routing system configuration utilizing the calculated traffic statistics.

34. The computer-readable storage medium according to claim 33, wherein the set of instructions, when executed by the computer, further cause the computer to perform the following steps:

receiving the pre-defined traffic flows from a user.

35. The computer-readable storage medium according to claim 34, wherein the receiving step includes receiving the pre-defined traffic flows from the user via a user interface.

36. The computer-readable storage medium according to claim 33, wherein the set of instructions, when executed by the computer, further cause the computer to perform the following steps:

to assign a private network address to each of said devices.

37. The computer-readable storage medium according to claim 36, wherein the set of instructions, when executed by the computer, further cause the computer to generate each said private network address and include information relating to at least one of said traffic flows.