System and methods for improved network routing

Abstract

Known intra-domain routing methods (e.g., OSPF and IS-IS) are link-state routing protocols with hop-by-hop forwarding that sacrifice optimal traffic engineering for ease of implementation and management. Known optimal traffic engineering procedures are either not link-state methods or require source routing—characteristics that make them difficult to implement. Certain embodiments of the present invention include a fully distributed, adaptive, link-state routing protocol with hop-by-hop forwarding configured to achieve optimal traffic engineering. Such embodiments facilitate significant performance improvements relative to known intra-domain routing methods and decrease network infrastructure requirements.

Claims

1. A system for improving routing of a commodity through a network, comprising: a processor; a main memory in communication with the processor via a communication infrastructure and storing instructions that, when executed by the processor, cause the processor to: recognize two or more nodes in the network; ascertain one or more links between the two or more nodes in the network; assign a price value to each of the one or more links between the two or more nodes in the network; receive a request for routing at least one unit of the commodity from a source node to a destination node in the network; and .[.compute an optimal next node subsequent to the source node, wherein a split ratio applied.]. .Iadd.route the at least one unit of the commodity from the source node to the destination node in the network, wherein the routing of the at least one unit of the commodity is based at least in part on applying a dynamically adjusted split ratio weighting factor in at least one of the two or more nodes in a pathway between the source node and the destination node in the network, the split ratio weighting factor being computed .Iaddend.in .Iadd.the .Iaddend.at least one of the two or more nodes .[.is dynamically adjusted, a split ratio weighting factor expressed as,.]. .Iadd.in the pathway between the source node and the destination node in the network according to: .Iaddend. $\mathrm{if}{r}_u^t>0,{\dot{\alpha }}_{u,v}^t=-\frac{{\alpha }_{u,v}^t\delta }{{\eta }_u^t{r}_u^t},v\ne \overline{v}[{\dot{\alpha }}_{u,v}^t=-\underset{v:\left(u,v\right)\in 𝔼,v\ne \overline{v}}{.Math.}{\dot{\alpha }}_{u,v}^t]{\dot{\alpha }}_{u,\overline{v}}^t=-\underset{v:\left(u,v\right)\in 𝔼,v\ne \overline{v}}{.Math.}{\dot{\alpha }}_{u,v}^t\mathrm{else}\mathrm{if}{r}_u^t=0,{\alpha }_{u,v}^t=0,v\ne \overline{v}{\alpha }_{u,\overline{v}}^t=1$ wherein η represents .Iadd.a product of .Iaddend.a number of branches .Iadd.at junctions, .Iaddend.u represents a source node, t represents a destination node, α represents a split ratio, r represents a rate of incoming traffic, δ represents a rate traffic shifts between the one or more links, and (u, v) ϵ E and (u, v) is part of a shortest path to t from u.Iadd.; and wherein the network is an electronic data network.Iaddend..

2. The system of claim 1, wherein the .[.compute step includes.]. .Iadd.split ratio weighting factor is further computed by.Iaddend.: using Dijkstra's method with tie-breaking based on a node index; surveying a shortest pathway from the source node to the destination node; initializing the branch cardinality (η.sub.u.sup.t)for the shortest pathway from the source node to the destination node; and at every subsequent node, setting η.sub.u.sup.t←η.sub.u.sup.tb, wherein .[.η represents a number of branches, u represents a source node, t represents a destination node, and.]. b represents a number of branches from a particular junction.

3. The system of claim 1, wherein the commodity is an information packet.

.[.4. The system of claim 1, wherein the network is an electronic data network..].

5. .[.The system of claim 1,.]. .Iadd.A system for improving routing of a commodity through a network, comprising: a processor; a main memory in communication with the processor via a communication infrastructure and storing instructions that, when executed by the processor, cause the processor to: recognize two or more nodes in the network; ascertain one or more links between the two or more nodes in the network; assign a price value to each of the one or more links between the two or more nodes in the network: receive a request for routing at least one unit of the commodity from a source node to a destination node in the network; and route the at least one unit of the commodity from the source node to the destination node in the network, wherein the routing of the at least one unit of the commodity is based at least in part on applying a dynamically adjusted split ratio weighting factor in at least one of the two or more nodes in a pathway between the source node and the destination node in the network, the split ratio weighting factor being computed in the at least one of the two or more nodes in the pathway between the source node and the destination node in the network according to: $\mathrm{if}{r}_u^t>0,{\dot{\alpha }}_{u,v}^t=-\frac{{\alpha }_{u,v}^t\delta }{{\eta }_u^t{r}_u^t},v\ne \overline{v}{\dot{\alpha }}_{u,\overline{v}}^t=-\underset{v:\left(u,v\right)\in 𝔼,v\ne \overline{v}}{.Math.}{\dot{\alpha }}_{u,v}^t\mathrm{else}\mathrm{if}{r}_u^t=0,{\alpha }_{u,v}^t=0,v\ne \overline{v}{\alpha }_{u,\overline{v}}^t=1$ wherein η represents a product of a number of branches at junctions, u represents a source node, t represents a destination node, α represents a split ratio, r represents a rate of incoming traffic, δ represents a rate traffic shifts between the one or more links, and (u, v) ϵ E and (u, v) is part of a shortest path to t from u; and .Iaddend. wherein each of the two or more nodes is a router.

6. The system of claim 1, wherein each of the two or more nodes is a computer system.

.[.7. A method for routing electronic data packets in a network, the method comprising: one or more processors executing a process to: identify a plurality of network nodes in a network, wherein packets are sent between a source node of the plurality of network nodes, and a destination node of the plurality of network nodes; for each packet, performing a calculation of a split ratio at each node on an ongoing basis, wherein the split ratio comprises a selection of which node-to-node route each packet takes to go from a source destination node to a destination node, wherein calculating the split ratio at each node comprises, taking into account each node's current knowledge of shortest paths to a destination node for a packet; and decreasing a number of packets forwarded to a node that is not in a shortest path to the destination node, wherein the rate of decrease is proportional to a value of a current split ratio..].

.[.8. The method claim 7, wherein the one or more processors comprise one or more routers associated with network nodes, and wherein not all of the routers are required to perform the process..].

.[.9. The method of claim 7 wherein performing the calculation of the split ratio at each node comprises receiving network link state information, and does involve information regarding demand at nodes..].

.[.10. The method of claim 9, wherein the link state information comprises one or more of a number of packets between nodes, and a number of packets per unit of distance between nodes..].

.[.11. The method of claim 7, wherein the process comprises calculating a weighting factor for the split ratio at each node for each possible next node..].

.[.12. The method of claim 7, wherein the process comprises iteratively modifying packet forwarding at each node, comprising: a node determining whether there are packets currently destined for a given destination node; if there are no packets currently destined for the given destination node, the node forwarding newly received packets to the given destination node along a shortest path; if there are packets currently destined for the given destination node, the node adjusting a number of packets forwarded to the given destination node..].

.[.13. The method of claim 12, wherein adjusting the number of packets comprises reducing a number of packets along non-shortest routes and increasing the number of packets along currently calculated shortest paths..].

.[.14. The method of claim 13, wherein adjusting is performed iteratively until an optimal route is obtained..].

.[.15. The method of claim 8, wherein the performance of the process by a subset of the one or more routers, including one of the one or more routers, improves traffic in the network..].

.[.16. The method of claim 7 wherein the one or more processors comprise one or more routers associated with network nodes, and a central processor, and wherein the central processor performs the process for each node and transmits results to each node for use in routing network traffic..].

.Iadd.17. A system comprising: at least one node including a link-state router (LSR), wherein the at least one node is coupled to a network including a plurality of nodes coupled via a plurality of links; wherein the LSR is configured to include a plurality of routing components; wherein the LSR is configured to receive feedback including link state information of the plurality of links; wherein at least one of the plurality of routing components is configured: to use the link state information to characterize current knowledge of a shortest path to a destination node in the network; to select a split ratio that incrementally increases traffic along a first one of the plurality of links that corresponds to the shortest path to the destination node and incrementally decreases traffic along at least a second one of the plurality of links that corresponds to at least one other path to the destination node; and to determine a best route through the network by determining, using the selected split ratio, at least one optimal subsequent node of the plurality of nodes; wherein the determination of the at least one optimal subsequent node is repeated at each optimal subsequent node, based at least in part on split ratios selected at each optimal subsequent node using current knowledge of the shortest path to the destination node at each optimal subsequent node, until the destination node is reached; and wherein the LSR is configured to control routing of traffic using the best route..Iaddend.

.Iadd.18. The system of claim 17, wherein the at least one routing component includes at least one objective function, wherein resultant values generated by the at least one objective function adaptively characterize the network..Iaddend.

.Iadd.19. The system of claim 18, wherein the determination of the best route includes applying the at least one objective function to the link state information..Iaddend.

.Iadd.20. The system of claim 19, wherein the adaptive characterization of the network comprises recognizing changes in parameters of the network based at least in part on feedback of the link state information of the plurality of links, and adapting the characterization of the network in response to the changes in the parameters..Iaddend.

.Iadd.21. The system of claim 20, wherein the at least one routing component dynamically adapts to changes in traffic on the network..Iaddend.

.Iadd.22. The system of claim 20, wherein the parameters include changes in network topology..Iaddend.

.Iadd.23. The system of claim 20, wherein the parameters include variations in network traffic..Iaddend.

.Iadd.24. The system of claim 20, wherein the parameters include the link state information..Iaddend.

.Iadd.25. The system of claim 24, wherein the link state information comprises a numerical description of a state of at least one of the plurality of links..Iaddend.

.Iadd.26. The system of claim 24, wherein the link state information comprises a valuation of an amount of traffic on at least one of the plurality of links..Iaddend.

.Iadd.27. The system of claim 24, wherein the link state information comprises one or more of a number of packets between nodes, and a number of packets per unit of distance between nodes..Iaddend.

.Iadd.28. The system of claim 20, wherein the adaptive characterization of the network using the feedback of the link state information obviates pre-assigned network traffic information in order to compute link weights..Iaddend.

.Iadd.29. The system of claim 20, wherein the adaptive characterization of the network obviates pre-assigned network traffic information in order to begin routing traffic using the best route..Iaddend.

.Iadd.30. The system of claim 20, wherein the control of the routing by the at least one routing component based at least in part on the adaptive characterization of the network obviates routing based at least in part on coordination of the at least one node with others of the plurality of nodes..Iaddend.

.Iadd.31. The system of claim 17, wherein the at least one node including the LSR includes a single node including the LSR..Iaddend.

.Iadd.32. The system of claim 17, wherein the at least one node including the LSR includes two or more nodes each including the LSR..Iaddend.

.Iadd.33. The system of claim 17, wherein the at least one node including the LSR includes the plurality of nodes each including the LSR..Iaddend.

.Iadd.34. The system of claim 17, wherein the link state information is received at the LSR of the at least one node asynchronously relative to any other node of the plurality of nodes..Iaddend.

.Iadd.35. The system of claim 19, wherein the applying of the at least one objective function to the link state information at the at least one node is asynchronous relative to any other node of the plurality of nodes..Iaddend.

.Iadd.36. The system of claim 19, wherein the link state information includes updated link state information..Iaddend.

.Iadd.37. The system of claim 36, wherein the determination of the best route includes dynamically adjusting the route at the at least one node in response to the updated link state information..Iaddend.

.Iadd.38. The system of claim 37, wherein the dynamic adjusting is performed iteratively until an optimal route is obtained, wherein the optimal route is a route that minimizes the objective function..Iaddend.

.Iadd.39. The system of claim 38, wherein the dynamic adjusting of an iteration includes applying the at least one objective function to the updated link state information received during the iteration..Iaddend.

.Iadd.40. The system of claim 39, wherein the dynamic adjusting comprises reducing a number of packets along non-shortest paths to the destination node..Iaddend.

.Iadd.41. The system of claim 39, wherein the dynamic adjusting comprises increasing a number of packets along the shortest path to the destination node..Iaddend.

.Iadd.42. The system of claim 39, wherein the dynamic adjusting comprises, for each packet to be routed to the destination node during each iteration, selection of a route each packet takes through the network using the selected split ratio..Iaddend.

.Iadd.43. The system of claim 42, wherein the dynamic adjusting comprises decreasing a number of packets forwarded to a node that is not in a shortest path to the destination node..Iaddend.

.Iadd.44. The system of claim 43, wherein the rate of decrease is proportional to a value of the selected split ratio..Iaddend.

.Iadd.45. The system of claim 19, wherein the best route is determined by minimizing the at least one objective function using the link state information..Iaddend.

.Iadd.46. The system of claim 45, wherein the best route is an optimal route between a source node and the destination node of the plurality of nodes..Iaddend.

.Iadd.47. The system of claim 46, wherein the best route comprises a lowest cost route through the network..Iaddend.

.Iadd.48. The system of claim 46, wherein the best route comprises a shortest route through the network..Iaddend.

.Iadd.49. The system of claim 19, wherein the at least one routing component is configured to iteratively apply in real time the at least one objective function to the link state information and generate a plurality of link weights comprising a link weight for each link of the plurality of links..Iaddend.

.Iadd.50. The system of claim 49, wherein the at least one routing component is configured to determine at least one route for tenant traffic flow according to the plurality of link weights..Iaddend.

.Iadd.51. The system of claim 50, wherein the control of the routing of the tenant traffic flow comprises continually adapting the at least one route in response to changes in the link state information as processed by the at least one objective function..Iaddend.

.Iadd.52. The system of claim 17, wherein the control of the routing comprises controlling routing of traffic to a next node of the best route via a single path..Iaddend.

.Iadd.53. The system of claim 17, wherein the control of the routing comprises controlling routing of traffic to a next node of the best route via a plurality of paths..Iaddend.

.Iadd.54. The system of claim 17, wherein the control of the routing at the at least one node is independent of routing decisions of any other node of the plurality of nodes..Iaddend.

.Iadd.55. The system of claim 17, wherein the LSR is configured to operate in conjunction with a plurality of routing systems of other nodes of the plurality of nodes..Iaddend.

.Iadd.56. The system of claim 17, wherein the at least one node includes a control plane that is separate and distinct from a data plane..Iaddend.

.Iadd.57. The system of claim 56, wherein the control plane is distributed among the plurality of nodes..Iaddend.

.Iadd.58. The system of claim 56, wherein the control plane comprises at least one of software and hardware..Iaddend.

.Iadd.59. The system of claim 56, wherein the data plane comprises at least one of software and hardware..Iaddend.

.Iadd.60. The system of claim 17, wherein the at least one routing component includes a software-defined algorithm executing in the at least one node, wherein the at least one routing component is configured to interoperate with other network components of the at least one node..Iaddend.

.Iadd.61. The system of claim 60, wherein the other network components of the at least one node include one or more of logic components, interconnect components, ports, memory components, input/output components, and algorithms..Iaddend.

.Iadd.62. The system of claim 17, wherein at least one routing component is configured to use the link state information to adaptively characterize the network..Iaddend.

.Iadd.63. The system of claim 62, wherein at least one routing component is configured to iteratively determine the best route through the network based at least in part on the adaptive characterization..Iaddend.

.Iadd.64. The system of claim 17 wherein selecting the split ratio comprises computing a split ratio weighting factor expressed as: $\mathrm{if}{r}_u^t>0,{\dot{\alpha }}_{u,v}^t=-\frac{{\alpha }_{u,v}^t\delta }{{\eta }_u^t{r}_u^t},v\ne \overline{v}{\dot{\alpha }}_{u,\overline{v}}^t=-\underset{v:\left(u,v\right)\in 𝔼,v\ne \overline{v}}{.Math.}{\dot{\alpha }}_{u,v}^t\mathrm{else}\mathrm{if}{r}_u^t=0,{\alpha }_{u,v}^t=0,v\ne \overline{v}{\alpha }_{u,\overline{v}}^t=1$ wherein η represents a product of a number of branches at junctions, u represents a source node, t represents a destination node, α represents the split ratio, r represents a rate of incoming traffic, δ represents a rate traffic shifts between the plurality of links, and (u, v) ϵ E and (u, v) is part of a shortest path to t from u..Iaddend.

.Iadd.65. The system of claim 18, wherein computing the split ratio weighting factor comprises: using Dijkstra's method with tie-breaking based on a node index; surveying the shortest path from the source node to the destination node; initializing the branch cardinality (η.sub.u.sup.t) for the shortest path from the source node to the destination node; and at every subsequent node, setting η.sub.u.sup.t←η.sub.u.sup.tb, wherein η represents a number of branches, u represents a source node, t represents a destination node, and b represents a number of branches from a particular junction..Iaddend.

.Iadd.66. The system of claim 17, wherein the traffic comprises one or more information packets..Iaddend.

.Iadd.67. The system of claim 17, wherein the network is an electronic data network..Iaddend.

.Iadd.68. The system of claim 17, wherein each of the plurality of nodes is a router..Iaddend.

.Iadd.69. The system of claim 17, wherein each of the plurality of nodes is a computer system..Iaddend.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) The preferred embodiments of the invention will be described in conjunction with the appended drawings provided to illustrate and not to limit the invention, where like designations denote like elements, and in which:

(2) FIG. 1 illustrates an example of a network;

(3) FIG. 2A illustrates an example of a network having two nodes according to the present invention;

(4) FIG. 2B illustrates an example of a network having three nodes according to the present invention;

(5) FIG. 2C illustrates another example of a network having three nodes according to the present invention

(6) FIG. 2D illustrates an example of a network having a plurality of nodes according to the present invention;

(7) FIG. 3 illustrates a comparison of an embodiment of the present invention with Gallager's distance-vector approach known in the art;

(8) FIG. 4 illustrates a shortest path tree in a network along with a branch of that tree highlighted;

(9) FIG. 5A illustrates an example of a network according to the present invention;

(10) FIG. 5B illustrates a comparison of solutions provided by different procedures seeking to identify the optimal solution to a network routing problem;

(11) FIG. 6 illustrates an Abilene network;

(12) FIG. 7A illustrates a comparison of the optimality gap between an embodiment of the present invention over a number of iterations having different network loads in the Abilene network;

(13) FIG. 7B illustrates a comparison of the optimality gap between an embodiment of the present invention over a number of iterations having different network loads in a 4×4 mesh network;

(14) FIG. 7C illustrates a comparison of the optimality gap between an embodiment of the present invention over a number of iterations having different network loads in a hierarchical 50 node network;

(15) FIG. 8A illustrates a comparison of the optimality gap between an embodiment of the present invention over a number of iterations having different step-sizes in the Abilene network;

(16) FIG. 8B illustrates a comparison of the optimality gap between an embodiment of the present invention over a number of iterations having different step-sizes in a 4×4 mesh network;

(17) FIG. 8C illustrates a comparison of the optimality gap between an embodiment of the present invention over a number of iterations having different step-sizes in a hierarchical 50 node network;

(18) FIG. 9A illustrates a comparison of the optimal performance and an embodiment of the present invention in the Abilene network;

(19) FIG. 9B illustrates a comparison of the optimal performance and an embodiment of the present invention in a 4×4 mesh network;

(20) FIG. 9C illustrates a comparison of the optimal performance and an embodiment of the present invention in a hierarchical 50 node network;

(21) FIG. 10A illustrates a comparison of a known procedure (OSPF with optimized link weights) and an embodiment of the present invention in the Abilene network;

(22) FIG. 10B illustrates a comparison of a known procedure (OSPF with optimized link weights) and an embodiment of the present invention in a 4×4 mesh network;

(23) FIG. 10C illustrates a comparison of a known procedure (OSPF with optimized link weights) and an embodiment of the present invention in a hierarchical 50 node network;

(24) FIG. 11A illustrates the evolution of optimality gap for the Abilene network as the number of iterations increase with varying demand matrices;

(25) FIG. 11B illustrates evolution of split ratios to Chicago, Kansas City and Atlanta for traffic destined to LA at the Indianapolis node in Abilene network;

(26) FIG. 12 illustrates evolution of the optimality gap for a randomly generated 100 node network with varying step-sizes;

(27) FIG. 13A illustrates iterations required to converge increase with increasing delay at step-size=0.1;

(28) FIG. 13B illustrates iterations required to converge increase with increasing difference in rate of execution at step-size=0.001);

(29) FIG. 14A illustrates a network embodiment of the present invention;

(30) FIG. 14B illustrates a network embodiment of the present invention;

(31) FIG. 14C illustrates a NetFPGA 1G Board according to the present invention;

(32) FIG. 15 illustrates another network embodiment of the present invention;

(33) FIG. 16 illustrates the evolution of the split ratios at a node in the network;

(34) FIG. 17 illustrates the evolution of the split ratios at a node in the network in presence of additional short-term traffic variations;

(35) FIG. 18 illustrates an exemplary computer system; and

(36) FIG. 19 illustrates an exemplary cloud computing system.

DETAILED DESCRIPTION OF EMBODIMENTS OF THE INVENTION

(37) The question of how to route information packets through an electronic data network can be defined more generally as a multi-commodity flow (“MCF”) problem. For a given directed graph, G=(V,E) with node/router set V and edge/link, set E with link capacities c.sub.u,v; ∀ (u,v)ϵE, and demands D(s,t) defined as the rate required for communication from s to t, the MCF problem can been summarized below.

(38) $\underset{f_{u,v}^t}{\min }\Phi \left(f\right)$$s.t.\underset{v:\left(s,v\right)\in 𝔼}{.Math.}{f}_{s,v}^t-\underset{u:\left(u,s\right)\in 𝔼}{.Math.}{f}_{u,s}^t=D\left(s,t\right),\forall s\ne t$$f_{u,v}=\underset{t\in 𝕍}{.Math.}{f}_{u,v}^t\le c_{u,v},\forall \left(u,v\right)$$f_{u,v}^t\ge 0$

(39) Commodities are defined in terms of their final destination t. ƒ.sub.u,v.sup.t is the flow on link (u,v) corresponding to commodity t and ƒ.sub.u,v is the total flow on link (u,v). The cost function, Φ, is typically selected to be a convex function of the link rate vector ƒ={ƒ.sub.u,v}, ∀ (u,v)ϵE. For example, if the M/M/1 delay formula is used for the cost function, then Φ (ƒ)=Σ.sub.u,v Φ.sub.u,v (ƒ.sub.u,v)=Σ.sub.u,v ƒ.sub.u,v/(c.sub.u,v−ƒ.sub.u,v). Throughout this application, this cost function will be used unless specified otherwise. It is also assumed that Φ′.sub.u,v (ƒ.sub.u,v).sub..fwdarw..sub.∞ when ƒ.sub.u,v.fwdarw.c.sub.u,v. This element captures the common practice of not allowing links to operate too close to their capacity. For the purposes of this application, given a function γ(χ(τ)), the character γ′ to represent the derivative of χ with respect to χ and {dot over (γ)} to represent the time (τ) derivative of γ.

(40) Using the first derivative of the cost function as the price of a link in distance calculations permits the achievement of an optimal solution. The price of the link (u,v) is defined as w.sub.u,v=Φ′.sub.u,v(ƒ.sub.u,v), the price of a path p as Σ.sub.u,vϵp w.sub.u,v and the price at a node u to a destination t as,

(41) $\begin{array}{cc}{q}_u^t=\underset{v:\left(u,v\right)\in 𝔼}{.Math.}{\alpha }_{u,v}^t\left[w_{u,v}+q_v^t\right]& \left(1\right)\end{array}$
where q.sub.t.sup.t=0. The price at a node can be interpreted as the average price to the destination from that node where the average is taken over all outgoing edges to the destination weighted by the split ratios along those edges. If instead the average is done over all possible paths, Equation (1) can be stated without recursion as,

(42) $\begin{array}{cc}{q}_u^t=\underset{p\in P_{u,t}}{.Math.}{d}_p\underset{\left(i,j\right)\in p}{.Math.}{\alpha }_{i,j}^t& \left(2\right)\end{array}$
where P.sub.u,t is the set of paths from u to t and d.sub.p=Σ.sub.(u,v)ϵp w.sub.u,v.

(43) As identified above, the selection of which packets or how many packets follow which path through which nodes is termed a “split ratio”. A split ratio may be determined for each commodity (e.g., information packet) at every node. More specifically, each router's split ratios are adjusted and traffic is moved from one outgoing link to another. Such embodiments only control the next hop on a packet path, which is hop-by-hop routing. If the entire path rate was controlled, the system would be using source routing. Also, the split ratio determination may include favoring links that form the shortest pathway, even though the average price via the next hop node may not be the lowest. If the lowest average price was prioritized, this is termed “Gallager's approach”, which is a distance vector solution (Gallager's approach is compared with an embodiment of the present invention in FIG. 3. The dashed line represents Gallager's approach and the solid line represents an embodiment of the present invention.)

(44) In addition, the split ratio determination may include adapting the split ratios dynamically and incrementally by decreasing the packet traffic along links that belong to non-shortest paths while increasing along the link that is part of the shortest path at every router. In contrast, if split ratios are set to send packets only to the links leading to the currently calculated shortest path, then the result is OSPF with weights, w.sub.u.v.

(45) Certain portions of certain embodiments of the present invention are configured to address specific scenarios that may occur in a network. One scenario is illustrated in FIG. 2A. One or more information packets 52 are available for routing through the network 50. The rate of demand 53 for routing information packets 52 may be represented by “r”. Upon reaching node A, the one or more information packets 52 may be sent along a first link 54 or a second link 56. In the illustrated embodiment, the first link 54 has a more expensive “price” according to some criteria (e.g., longer distance, lower reliability, etc.). The more expensive price is represented by the character “w.sub.l”. The second link 56 has a less expensive price and is represented by the character “w.sub.s”.

(46) Given w.sub.l>w.sub.s, a strategy to reach optimal use of the first link and the second link might be to dynamically shift traffic from the more expensive link to the cheaper link at some rate δ>0 until the prices of the two links become the same. The split ratio for the first link 54 at node A is represented by α.sub.l and the split ratio for the second link 56 is represented by α.sub.s. In certain embodiments, the traffic over the first link 54 is decreased and traffic at the second link is increased. The α.sub.l value may be decreased while the α.sub.s value is increased at rate δ/r. In such embodiments, the first link price is w.sub.l=Φ.sub.l′(α.sub.lr) and the second link price w.sub.s=Φ.sub.s′(α.sub.sr).

(47) There are at least two ways to interpret and generalize the intuition gained from this scenario. Both give the same solution for this very simple example but in general will lead to different dynamics and possibly different split ratios. One interpretation, which forms the basis of procedures used in certain known methods, is that the router shifts traffic headed to neighbor nodes with higher average price to the neighbor node with the lowest average price.

(48) A second interpretation, which is the basis of certain embodiments of the present invention, is that the router shifts traffic from links along more expensive paths to the link along the path with the lowest price. Mathematically, the following update rule for the split ratios is:

(49) $\begin{array}{cc}{\stackrel{.}{\alpha }}_{u,v}^t=-\frac{\delta }{r_u^t}& \left(3\right)\end{array}$
where (u, v)ϵE but is not on the shortest path from u to destination t and r.sub.u.sup.t is the incoming rate at node u at destination t.

(50) However, as a potential counter-example to this interpretation, some version of the scenario described in FIG. 2B may be relevant. FIG. 2B illustrates traffic demand of rate r from node A to node C. In the network, there is a first node (node A), a second node (node B), and a third node (node C). There is a first link 54 between node B and node C, a second link 56 between node B and node C, a third link 58 between node A and node B, and a fourth link 60 between node A and node C. The initial splits at node A are represented by α.sub.m for the fourth link along an intermediate price link with price w.sub.m and a.sub.w along the more expensive route with price w.sub.B+w.sub.l for the third link, assuming a.sub.l=1 initially. The relationship between the initial link prices are assumed to be w.sub.l>w.sub.m>w.sub.s+w.sub.B, i.e., the third link (A,B) is along the shortest path from node A to node C, but node B also has the most expensive way to reach node C. The concern is that, if node A shifts traffic from the intermediate price link to the link with price w.sub.B, the cost might increase as node B currently routes traffic only through the most expensive link (α.sub.l=1). But because the selection at node B decreases α.sub.l and increases α.sub.s (in conjunction with the changes at node A), the total cost does in fact decrease. More precisely, the cost derivative can be calculated as follows,

(51) $\stackrel{.}{\Phi }=-r\times \frac{\delta }{r}\times w_m+r\times \frac{\delta }{r}\times \left(w_B+w_l\right)-r_B\times \frac{\delta }{r_B}\times w_l+r_B\times \frac{\delta }{r_B}\times w_s=-\delta \left(w_m-w_B-w_s\right)\le 0$
where r.sub.B is the incoming rate to C at B and the inequality follows from the relationship between the prices.

(52) The scenario illustrated in FIG. 2B can be used to illustrate the difference between certain embodiments of the present invention and Gallager's technique which arises from the fact that the link leading to the neighbor with the lowest average price (path A-C with price w.sub.m) may not lead to the cheapest path (path A-B-C with price w.sub.B+w.sub.s). FIG. 3 shows the trajectories taken by the two different methods to converge to the optimal solution for the illustrated topology. To simulate the long link between node B and node C, an intermediate dummy node D may be introduced that splits the bottom link between B and C into two equal capacity links. The capacities used could be (A,B)=5, (B,C)=10, (A,C)=(B,D)=(D,C)=3. The single demand is D(A,C)=r. The rate r=1 and initially α.sub.w=α.sub.m=0.5 and α.sub.l=1. At each node, the split ratios to a given destination have to add up to the value 1. Accordingly, only one split ratio is calculated at each node because the value of that split ratio automatically defines the value of the other at each node. Using Gallager's method, initially, as can be seen, following the lowest average price path to the destination (A,C), there is an increase in the value of α.sub.m. Also, the trajectory of the method (gradient descent) is perpendicular to the objective function contour curves. On the other hand, using an embodiment of the present invention, both split ratios are decreased initially. The trajectory based on an embodiment of the present invention is usually not perpendicular to the contour curves, which represent the cost of the network. However, the trajectory still goes along a descent direction and drives the total cost down.

(53) The scenario illustrated in FIG. 2C is configured to exemplify why Equation 3 is not sufficient to decrease network cost along any trajectory. FIG. 2C illustrates k intermediate price links from router A to router C, each of which gets α.sub.m/k fraction of the demand. The relationship between the link prices is the same as in the example illustrated in FIG. 2B. The shifting of traffic in an unrestricted fashion from the intermediate price links to router B with α.sub.l=1, might result in an increase in the cost. The following calculation shows how the cost may increase.

(54) $\stackrel{.}{\Phi }=-k\times r\times \frac{\delta }{r}\times w_m+k\times r\times \frac{\delta }{r}\times \left(w_B+w_l\right)-r_B\times \frac{\delta }{r_B}\times w_l+r_B\times \frac{\delta }{r_B}\times w_s=-k\delta w_m+\delta \left({\mathrm{kw}}_B+w_s\right)+\left(k-1\right){\delta w}_l$
which may be positive for k>1. Accordingly, to avoid increasing the cost, a weighting factor of the split ratio itself is added to the Equation below.

(55) $\begin{array}{cc}{\stackrel{.}{\alpha }}_{u,v}^t=-\frac{{\alpha }_{u,v}^t\delta }{r_u^t}& \left(4\right)\end{array}$
where (u, v)ϵE, but is not on the shortest path from u to destination t.

(56) With the new rule (Equation 4), the cost derivative can be evaluated as follows.

(57) $=-k\times r\times \frac{\delta {\alpha }_m}{\mathrm{rk}}\times w_m+\mathrm{kr}\times \frac{\delta {\alpha }_m}{\mathrm{rk}}\times \left(w_B+w_l\right)-r_B\times \frac{\delta }{r_B}\times w_l+r_B\times \frac{\delta }{r_B}\times w_s=-\delta \left[{\alpha }_m{w}_m+\left(1-{\alpha }_m\right)\left(w_B+w_l\right)\right]+\delta \left(w_B+w_l\right)-\delta w_l+\delta w_s=-\delta \left[{\alpha }_m{w}_m+\left(1-{\alpha }_m\right)\left(w_B+w_l\right)\right]+\delta \left(w_B+w_s\right)\le 0$
Where the last inequality follows from the fact that the average prices from router A to router C, which is α.sub.mw.sub.m+(1−α.sub.m)(w.sub.B+w.sub.l) has to be at least as large as the price of the shortest path from A to C, which is w.sub.B+w.sub.s.

(58) Additional adaptations to the Equation 4 can be made to improve the likelihood that its application will result in a decrease in cost of the network. The scenario in FIG. 2D includes multiple inputs. The link weights as illustrated are w.sub.l>w.sub.s>w.sub.s+w.sub.B. In the illustrated embodiment, there are k sources (e.g., demands D(A.sub.i, C)=r, I=1, . . . , k) that have information packets to be sent to node C. Shifting traffic in an unrestricted manner from all the sources to router B with α.sub.m=1 may cause the total cost to increase as shown by the calculations below.

(59) $$\begin{gathered} \stackrel{.}{\Phi }=-k\times r\times \frac{\delta {\alpha }_m}{r}\times w_{m}k\times r\times \frac{\delta {\alpha }_m}{r}\times \left(w_B+w_l\right)-r_B\times \frac{\delta }{r_B}\times w_l+r_B\times \frac{\delta }{r_B}\times w_s= \\ -k\delta \left[{\alpha }_m{w}_m+\left(1-{\alpha }_m\right)\left(w_B+w_l\right)\right]+\left(k-1\right)\delta w_l+\delta \left({\mathrm{kw}}_B+w_s\right) \end{gathered}$$
which may be positive for k>1.

(60) Once again it is possible to modify the rule for the split ratios from δα.sub.u,v.sup.t/r.sub.u.sup.t to δα.sub.u,v.sup.t/η.sub.u.sup.tr.sub.u.sup.t. In certain embodiments, the η.sub.u.sup.t=k while for a general network, η.sub.u.sup.t may be calculated according to a method specified later in this application. The calculation for determining the routing of information packets is updated to:

(61) 0$\begin{array}{cc}{\stackrel{.}{\alpha }}_{u,v}^t=-\frac{{\alpha }_{u,v}^t\delta }{{\eta }_u^t{r}_u^t}& \left(5\right)\end{array}$
where (u, v)ϵE, but is not on the shortest path from u to destination t.

(62) Overall, embodiments of the present invention results in split ratios for all the links converging to a set where every element of the set achieves the global optimum to the MCF problem and accordingly achieves optimal traffic engineering for the network. To illustrate, a few more notations are defined below.

(63) For a particular destination t at node s,

(64) $r_s^t=\underset{u:\left(u,s\right)\in 𝔼}{.Math.}{f}_{u,s}^t+D\left(s,t\right)$
the inflow rate to a node s destined to t, which, because of node flow balance requirements is also the outflow at s to t. The character α is also used without indexing to represent the set of all the split ratios from all the routers in the network. At a router u, α.sub.u,v.sup.t controls the fraction of traffic to destination t that uses outgoing link (u, v) while satisfying α.sub.u,v.sup.t≥0 and Σ.sub.v:(u,v)ϵEα.sub.u,v.sup.t=1.

(65) Branch cardinality is used to make sure that nodes that are farther away from a destination node are more conservative in how much traffic they shift to the shortest path leading to the destination. As noted earlier, if nodes simply shifted a large percentage or all of their traffic to the shortest node, the performance of the network would be poor. OSPF is an example of the latter. The characters η.sub.u.sup.t, which represent the branch cardinality, are defined as the product of the number of branches encountered in traversing the shortest path tree (e.g., route) rooted at t from t to u. Being a link-state routing method, each node u has the link-state information to run Dijkstra's method to compute the shortest path tree to destination t. Every node has to independently determine the same shortest path tree to permit the method to proceed as desired. At any stage of Dijkstra's method, if there is ambiguity as to which node should be added next, tie-breaking based on node index is used. For the purposes of the present application, a “node index” is an identifier that uniquely describes each node in a network. Examples include a MAC address, IP address, etc.

(66) An exemplary calculation of η.sub.u.sup.t is illustrated in method steps below. More specifically, the method steps are configured to calculate η.sub.u.sup.t{w.sub.e ∀.sub.eϵE}. 1. Compute shortest path tree for destination t using Dijkstra's method with tie-breaking based on node index 2. Traverse the tree from t to u 3. Initialize η.sub.u.sup.t←1 4. At every junction, do η.sub.u.sup.t←η.sub.u.sup.tb, where b is the number of branches from that junction

(67) The overall link-state routing method can be used to control the evolution of the destination specific split ratio α.sub.u,v.sup.t for any node u. Suppose that (u, υ)ϵE and (u, υ) is part of the shortest path to t from u. Then, certain embodiments of the present invention calculate the split ratios as follows.

(68) $\begin{array}{cc}\mathrm{if}{r}_u^t>0,{\stackrel{.}{\alpha }}_{u,v}^t=-\frac{{\alpha }_{u,v}^t\delta }{{\eta }_u^t{r}_u^t},v\ne \stackrel{\_}{v}& \left(6\right)\\ {\stackrel{.}{\alpha }}_{u,\stackrel{\_}{v}}^t=-\underset{u:\left(u,\upsilon \right)\in 𝔼,v\ne \stackrel{\_}{v}}{.Math.}{\stackrel{.}{\alpha }}_{u,v}^t& \left(7\right)\\ \mathrm{else}\mathrm{if}{r}_u^t=0,{\alpha }_{u,v}^t=0,v\ne \stackrel{\_}{v}& \left(8\right)\\ {\alpha }_{u,\stackrel{\_}{v}}^t=1& \left(9\right)\end{array}$

(69) The equations above specify how to iteratively decide modifying packet forwarding at each router. First, each node checks to see whether it has traffic to a given destination. If it does not already have traffic going to a destination, it forwards all newly received packets to that destination along the shortest path to that destination. If it does already have traffic going to a destination, it adjusts what fraction of traffic it forwards along its different outgoing links according to the equations. As noted in the case studies earlier, it reduces the traffic along non-shortest paths and increases it along the outgoing link leading to the currently calculated shortest path. This procedure is iteratively followed until the optimal solution is obtained.

(70) To prove the optimality of the above link-state hop-by-hop method, two lemmas will be analyzed. The first Lemma relates the node prices to the link weights for each destination t. More specifically,

(71) Lemma 1.

(72) $\underset{u\in 𝕍}{.Math.}D\left(u,t\right)q_u^t=\underset{\left(u,v\right)\in 𝔼}{.Math.}{f}_{u,v}^t{w}_{u,v}$

(73) It analytically states the intuitive idea that the total price of sending traffic to meet the demand in the network, as defined by the sum of the products of the traffic demand rate and the node price for each demand node, is equal to the sum over all links of the price of sending traffic through each link. The second lemma describes how to calculate the time rate of change of network cost.

(74) $\begin{array}{cc}\underset{\left(u,v\right)\in 𝔼}{.Math.}{\stackrel{.}{f}}_{u,v}^t{w}_{u,v}=\underset{u\in 𝕍}{.Math.}\underset{\left(u,v\right)\in 𝔼}{.Math.}{r}_u^t{\stackrel{.}{\alpha }}_{u,v}^t\left[w_{u,v}+q_u^t\right].& \mathrm{Lemma}2\end{array}$

(75) The second Lemma captures the fact that the change in network cost can either be expressed in terms of the change in the link flow rates, i.e., how each link affects the network cost or in terms of the change in the split ratios at each node, i.e., how each node affects the network cost.

(76) Next, certain method embodiments of the present invention are summarized in the following Theorem.

(77) Theorem. In a network, at every node u, for every destination t, let the evolution of the split ratios be defined by equations (6)-(9). Then, starting from any initial conditions, α converges to the largest invariant set {α|Φ(ƒ)=0} and any element of this set yields an optimal solution to the MCF problem. This result is proved in three steps of the following proof.

(78) Proof. First, it is shown that {dot over (Φ)}(ƒ)≤0. Then, this result invokes LaSalle's Invariance Principle for hybrid systems to assert that α converges to the largest invariant set in {α|(ƒ)=0}. Third, it is shown that any element of this set is an optimal solution to the MCF problem.

(79) First in this part of the method is step 1, in which the following is true.

(80) $\stackrel{.}{\Phi }\left(f\right)=\underset{t\in 𝕍}{.Math.}\underset{\left(u,v\right)\in 𝔼}{.Math.}{\stackrel{.}{f}}_{u,v}^t{w}_{u,v}=\underset{t\in 𝕍}{.Math.}{\stackrel{.}{\Phi }}^t\left(f\right)$
where {dot over (Φ)}.sup.t(ƒ)=Σ.sub.(u,v)ϵE{dot over (f)}.sub.u,v.sup.tw.sub.u,v is the rate of change of the network cost as the flows to destination t change. Consequently, if {dot over (Φ)}.sup.t(ƒ)≤0 for each destination t, then {dot over (Φ)}(ƒ). From Lemma 2,

(81) ${\stackrel{.}{\Phi }}^t\left(f\right)=\underset{\left(u,v\right)\in 𝔼}{.Math.}{\stackrel{.}{f}}_{u,v}^t{w}_{u,v}=\underset{u\in 𝕍}{.Math.}\underset{\left(u,v\right)\in 𝔼}{.Math.}{r}_u^t{\stackrel{.}{\alpha }}_{u,v}^t\left[w_{u,v}+q_v^t\right]$

(82) This part of the step 1 method is configured to decompose the change in cost to a particular destination t, by grouping the terms from the summation derived in Lemma 2, using the branches of the shortest path tree rooted at that destination. More precisely, a branch (B) is defined as the set of nodes on the path from a leaf node on the shortest path tree to the destination node t. Given the definition, some intermediate nodes clearly will be shared among multiple branches. The change in cost contributed by these nodes is properly divided among the different branches that pass through these routers in the following way. Each node u has a corresponding η.sub.u.sup.t value which appears in the denominator of the expression for the change in cost. When grouping terms, for a particular branch passing through an intermediate node, to only take a fraction, 1/π.sub.u.sup.B, of the change in cost contributed by the intermediate node, to be summed with that branch so that π.sub.u.sup.Bη.sub.u.sup.t, for that node u is the same as the branch cardinality of the leaf router which defines the branch. Consequently, π.sub.u.sup.Bη.sub.u.sup.t will be the same for all routers u encountered in a traversal from the leaf router of the branch to the destination. Given the definition of η.sub.u.sup.t and π.sub.u.sup.B, one can check Σ.sub.B1/π.sub.u.sup.B=1, so the total contributing form node u is distributed over different branches. See the following equation.

(83) $\underset{u\in 𝕍}{.Math.}\underset{\left(u,v\right)\in 𝔼}{.Math.}{r}_u^t{\stackrel{.}{\alpha }}_{u,v}^t\left[w_{u,v}+q_v^t\right]=\underset{\forall ℬ}{.Math.}\underset{u\in ℬ}{.Math.}\frac{1}{{\pi }_u^{ℬ}}\underset{\left(u,v\right)\in 𝔼}{.Math.}{r}_u^t{\stackrel{.}{\alpha }}_{u,v}^t\left[w_{u,v}+q_u^t\right]$
For a given branch B, with n nodes numbered 1, . . . , n from the leaf node to the destination, as noted above, 1/π.sub.u.sup.B is the fraction of the change in cost due to node u that it contributes to the branch summation. For ease of notation, in what follows, the character η will be used to represent every router u that belongs to the branch B. For any uϵ{1, 2, . . . , n−1}, the following equation applies:

(84) $\begin{array}{cc}\frac{1}{{\pi }_u^{ℬ}}\underset{\left(u,v\right)\in 𝔼}{.Math.}{r}_u^t{\stackrel{.}{\alpha }}_{u,v}^t\left[w_{u,v}+q_u^t\right]=-\frac{\delta }{\eta }\left(q_u^t-w_{u,u+1}-q_{u+1}^t\right)& \left(10\right)\end{array}$
If r.sub.u.sup.t=0, following equations (8) and (9), the left hand side of (10) is zero because {dot over (α)}.sub.u,v.sup.t=0, the right hand side of (10) is also zero because α.sub.u,u+1.sup.t=1. If r.sub.u.sup.t>0, (10) is still valid because of the following.

(85) $\begin{array}{c}\frac{1}{{\pi }_u^{ℬ}}\underset{\left(u,v\right)\in 𝔼}{.Math.}{r}_u^t{\stackrel{.}{\alpha }}_{u,v}^t\left[w_{u,v}+q_u^t\right]=-\frac{\delta }{\eta }\left(\begin{array}{c}\underset{\left(u,v\right)\in 𝔼}{.Math.}{\alpha }_{u,v}^t\left[w_{u,v}+q_u^t\right]-\\ \underset{\left(u,v\right)\in 𝔼}{.Math.}{\alpha }_{u,v}^t\left[w_{u,u+1}+q_{u+1}^t\right]\end{array}\right)\\ =-\frac{\delta }{\eta }\left(q_u^t-w_{u,u+1}-q_{u+1}^t\right)\end{array}$

(86) Therefore

(87) 0$\begin{array}{c}\underset{u\in ℬ}{.Math.}\frac{1}{{\pi }_u^{ℬ}}\underset{\left(u,v\right)\in 𝔼}{.Math.}{r}_u^t{\stackrel{.}{\alpha }}_{u,v}^t\left[w_{u,v}+q_u^t\right]=\underset{u=1}{\overset{n-1}{.Math.}}-\frac{\delta }{\eta }\left(q_u^t-w_{u,u+1}-q_{u+1}^t\right)\\ =-\frac{\delta }{\eta }\left[q_1^t-w_{1,2}-.Math.-w_{n-1,n}\right]\le 0\end{array}$

(88) The last inequality follows from the fact that the average price from the leaf router (node 1) to the destination (node n) which can be thought of as an average over paths from Equation (2), has to be no less than the price of the shortest path. Note that this relationship holds with equality only when the node price of the leaf node is the same as the price of the shortest path which means that all the traffic from every node in the branch to the destination is along shortest paths to the destination.

(89) Then, the result is as follows.

(90) $\begin{array}{cc}\stackrel{.}{\Phi }=\underset{t}{.Math.}{\stackrel{.}{\Phi }}^t\left(f\right)=\underset{\left(u,v\right)\in 𝔼}{.Math.}{\stackrel{.}{f}}_{u,v}^t{\Phi }^{\prime }\left(f_{u,v}\right)\le 0& \left(11\right)\end{array}$

(91) The next step is related to convergence. Given the control laws, it is clear that {dot over (Φ)}(ƒ)≤0. In order to show convergence, the language of hybrid automata is used to model the dynamics of this system and methods. Specifically, embodiments of this invention are an example of a non-blocking, deterministic, and continuous hybrid automaton. Consequently, invoking a generalization of LaSalle's Invariance Principle to hybrid automata ensures that the set of split ratios converges to the largest invariant set within {α|{dot over (Φ)}(ƒ)=0}.

(92) The subsequent step is related to optimality. For {dot over (Φ)}(ƒ)=0 to be true, {dot over (Φ)}(ƒ)=0 which implies that the change in cost along each branch is as follows.

(93) $\underset{u\in ℬ}{.Math.}\frac{1}{{\pi }_u^{ℬ}}\underset{\underset{\mathrm{such}\mathrm{that}u\in ℬ}{\left(u,v\right)\in 𝔼}}{.Math.}{r}_u^t{\stackrel{.}{\alpha }}_{u,v}^t\left[w_{u,v}+q_v^t\right]=0$
for every t.

(94) From the preceding analysis, the change in cost along a branch B is zero only when all the traffic from the nodes that belong to the branch is being routed to the destination through shortest paths with respect to the link prices. Since this is a necessary and sufficient condition for optimality in MCF, the proof is complete.

(95) Next, as an illustrative example to help understand the first step of the above proof, a sample shortest path tree is analyzed and the corresponding cost change calculations are identified explicitly. A shortest path tree is illustrated in FIG. 4. The number of branches that the tree is divided into is determined by the number of leaf nodes. In the illustrated example, the shortest path tree rooted at t has 12 leaf routers and, consequently, the summation is divided into 12 branches. Following the method for the calculation of η, η.sub.i.sup.t=1, η.sub.h.sup.t=3, η.sub.g.sup.t=9 and η.sub.s.sup.t=18.

(96) As noted in the proof, the change in the cost function due to the routers increasing traffic along the links in the shortest path tree can be calculated using Lemma 2. In order to evaluate it, the terms in the summation are divided and grouped per branch. For routers downstream to a leaf router in a branch, only a fraction of the change in the cost contributed by the downstream router is selected where the fraction is determined by the need to have the same η for all routers in the summation for a branch. The contribution to the change in the cost by the routers for the highlighted branch can be calculated as follows,

(97) $\underset{u\in ℬ}{.Math.}\frac{1}{{\pi }_u^{ℬ}}\underset{\left(u,v\right)\in 𝔼}{.Math.}{r}_u^t{\stackrel{.}{\alpha }}_{u,v}^t\left[w_{u,v}+q_u^t\right]=-r_s^t\underset{\left(s,v\right)\in 𝔼}{.Math.}\frac{{\alpha }_{s,v}^t\delta }{{\eta }_s^t{r}_s^t}\left[w_{s,v}+q_u^t\right]+r_s^t\underset{\left(s,v\right)\in 𝔼}{.Math.}\frac{{\alpha }_{s,v}^t\delta }{{\eta }_s^t{r}_s^t}\left[w_{s,g}+q_g^t\right]-r_g^t\underset{\left(g,v\right)\in 𝔼}{.Math.}\frac{{\alpha }_{g,v}^t\delta }{2{\eta }_g^t{r}_g^t}\left[w_{g,v}+q_v^t\right]+r_g^t\underset{\left(g,v\right)\in 𝔼}{.Math.}\frac{{\alpha }_{g,v}^t\delta }{2{\eta }_g^t{r}_g^t}\left[w_{g,h}+q_h^t\right]-r_h^t\underset{\left(h,v\right)\in 𝔼}{.Math.}\frac{{\alpha }_{h,v}^t\delta }{6{\eta }_h^t{r}_h^t}\left[w_{h,v}+q_v^t\right]+r_h^t\underset{\left(h,v\right)\in 𝔼}{.Math.}\frac{{\alpha }_{h,v}^t\delta }{6{\eta }_h^t{r}_h^t}\left[w_{h,i}+q_i^t\right]-r_i^t\underset{\left(i,v\right)\in 𝔼}{.Math.}\frac{{\alpha }_{i,v}^t\delta }{18{\eta }_i^t{r}_i^t}\left[w_{i,v}+q_v^t\right]+r_i^t\underset{\left(i,v\right)\in 𝔼}{.Math.}\frac{{\alpha }_{i,v}^t\delta }{18{\eta }_h^t{r}_i^t}\left[w_{i,t}\right]=-\frac{\delta }{{\eta }_s^t}\left[q_s^t-w_{s,g}-w_{g,h}-w_{h,i}-w_{i,t}\right]\le 0$

(98) As shown in FIG. 3, the present invention may follow a different trajectory from Gallager's method in searching for an optimal solution. But in that case, both methods converged to the same optimal solution. In general, because MCF problem is strictly convex in link rates (ƒ.sub.u,v) and only convex in flow rates (ƒ.sub.u,v.sup.t), there can be multiple optimal solutions in terms of the flow rates. For example, FIG. 5A illustrates an example of a network topology. Each link in the network has capacity of 5 and there are two demands D(1, 4)=D(1, 5)=2. The initial routes supplied to the different methods are (1-3-2-4) and (1-2-4-5), i.e., α.sub.1,2.sup.4=0 and α.sub.1,2.sup.5=1. FIG. 5B includes a graph of solutions provided by an embodiment of the present invention—designated as “HALO”. Clearly, each method generates a different optimal solution, all of which satisfy α.sub.1,2.sup.4+α.sub.1,2.sup.5=1; an optimality condition which follows from the fact that at optimum, ƒ.sub.3,2=0 and the resulting symmetry of the problem.

(99) Before reviewing how embodiments of the present invention may interact with a single-path routing method, certain terms are defined. First, for the purposes of this application, a “single-path method used to make routing decisions” is a router that uses a set of link weights to calculate the shortest path to the destination and makes forwarding decisions based on that shortest path. Also, if the single-path router calculations are triggered as often as that in the present invention, examples can be illustrated in which the routes in the network will oscillate and not settle down. This is because the single-path method moves all the traffic from one path to another instead of just a fraction. Also, a notion of time-scale separation between how often the method of the present invention is triggered and the single-path method is triggered. In certain embodiments, the subset of routers running the present invention will execute the method in between slower single-path calculations. Given this set up, the two methods can work with either the same link weights or method-specific link weights. Since local optimization methods exist for calculating single-path method link weights and because method-specific calculations can be triggered on the receipt of new method-specific link weights, the use of method-specific link weights generally are broadcast by each router at different timescales. However, this assumption is more important from an implementation perspective than for the argument that follows.

(100) Another useful assumption is that each router is aware of the method that the other routers in the network are using. With the time-scale separation and the assumption that every router is aware of the specific method running at every other router, for a given destination, the ‘single-path’ routers have a pruning effect on the network from the perspective of the routers running an embodiment of the present invention, i.e., the outgoing links that are not used by them are effectively not a part of the network topology. Assuming that every router is aware of the specific method running at every other router, the nodes running embodiments of the present invention will base their calculations on this reduced network and attain the optimal routing solution for this network. Essentially, the routers implementing an embodiment of the present invention increase the search space for finding a better routing solution and thus improve network performance.

(101) Certain embodiments of the present invention can be evaluated for certain performance metrics, specifically, the optimality, rate of convergence to the optimal solution, adaptivity as the traffic changes, and asynchronous environments and its interaction with single path routing methods. The evaluations may be performed on three network topologies—the benchmark Abilene network (FIG. 6), a 4×4 Mesh network and a two-level hierarchical 50 node network. The 4×4 Mesh network may be selected to study the effects of intermediate routing loops on the optimality of the present invention as this topology is particularly prone to such loops while the hierarchical network may be selected to mimic larger networks with high capacity backbone links and lower capacity local links. An additional test may be performed on an even larger randomly generated 100 node network in order to confirm that the method converges quickly for large networks. Randomly generated traffic demands may be used for the mesh network and the hierarchical network while for the Abilene network uniform traffic demand is used. In any of the three cases, the demand may be scaled up until at least one link in the network is close to saturation at the optimal solution.

(102) Regarding convergence, the speed of convergence depends on the step-size. In certain embodiments, the step size is the unit of time with which the changes in the split ratios calculated in Equations (6)-(9) is multiplied to determine how much to vary the split ratios from one time slot to the next. The metric, network load is defined as the ratio of the total traffic on the network to its total capacity. In general, smaller step-sizes improve convergence of an embodiment of the present invention to the optimal solution at the expense of speed of convergence.

(103) This concept is illustrated in FIG. 8A-FIG. 8C. However, as illustrated in FIG. 8A and FIG. 8C, larger step-sizes quickly approach the optimal solution though they can be prone to oscillations which prevent convergence to optimality. Often, it is sufficient to come to some neighborhood of the optimal solution and small oscillations around the optimal solution are acceptable. In such situations, a larger step-size may be used. In certain embodiments, e.g., for the larger 100 node network (illustrated in FIG. 12) the system and method was fairly quick, converging to a small neighborhood of the optimal solution within a few hundred iterations.

(104) Another factor that affects the rate of convergence of the system and methods is the load on the network. The maximum network load for the Abilene network may be 24.6%, mesh network may be 26.1% and the hierarchical network may be 5.3%. These values indicate the point at which further scaling up the demand for the given traffic pattern would exceed the capacity of at least one link in the network, even with optimal routing. From FIG. 7, it is clear that the system and methods take more iterations to converge to the optimal solution for more heavily loaded networks. The present invention converges to the optimal solution on the order of a thousand iterations. Given that link-state advertisements can be broadcast on the order of milliseconds, the possibility of convergence times of less than a second to a few seconds for the method on networks where transmission/propagation delay of the link-state advertisements is not a limiting factor.

(105) Regarding performance, the optimal solution may be calculated for the test networks by solving the corresponding MCF problem using cvx method known in the art or another method known in the art under different network load conditions. The objective value obtained by using the present invention matched the optimal solution for each test case as can be seen from FIG. 9A-FIG. 9C. Also, the intermediate routing loops produced while determining the optimal solution for the mesh network did not affect the optimality of the system and methods.

(106) In FIG. 10, the performance of an embodiment of the present invention is compared with OSPF boosted by better weight settings obtained from the methods of the TOTEM toolbox for demand matrices that placed increasing loads on the test networks. The local search method used by TOTEM minimizes a piecewise-linear approximation of the convex cost function. As described above, the power of optimality is demonstrated by the performance improvements on the order of 1000%.

(107) To illustrate how certain embodiments of the present invention are configured to dynamically adapt to changes in traffic on the network, FIG. 11 illustrates the evolution of the optimality gap as a traffic matrix undergoes changes under different network load conditions in the Abilene network. In this example, after around 300 iterations the network load is changed by changing 20% of the flows in the network. As can be seen, the method quickly adapts and the optimality gap increases very little before beginning to converge to the new optimal solution. The traffic pattern is again changed by varying 50% of the flows in the network after 800 iterations. This time the change in the optimality gap is greater but the convergence to the new optimal value is seen to be quicker. The traffic pattern in the network is changed two more times and as can be observed from the figure in both cases the method quickly converges to the new optimal solution.

(108) A closely related concept to certain embodiments of the system and methods of the present invention is the evolution of the split ratios at individual routers. A plot of the evolution of the split ratios from Indianapolis to Los Angeles is illustrated in FIG. 11B. For the test traffic, the initial sub-optimal allocation of split ratios is quickly corrected as the present invention reduces traffic sent to Chicago and increases traffic sent to Kansas City and Atlanta.

(109) In dynamic network environments, random delays can affect the time it takes for link-state information to reach every node in the network as required by certain embodiments of the method. Note that without synchronized link-state updates, facets of the present invention, e.g., calculating the shortest path tree and η.sub.u.sup.t may be affected. There are at least two ways to approach this problem. The first is to allow enough time between successive iterations of the running method so that every node has access to the most up-to-date link-state information. The second is to let the nodes execute the steps of the present invention despite asynchronous link-state updates. It is also possible for asynchronous behavior to arise despite synchronized link-state updates due to some subset of the nodes executing the steps faster than the other nodes. FIG. 13A illustrates data regarding how the present invention may operate in the presence of asynchronous link-state updates and asynchronous executions, using uniform traffic on the Abilene network. In order to simulate asynchronous behavior, the nodes in the network could be numbered and divided into two groups. For asynchronous link-state updates, at every iteration, the even numbered nodes may receive link-states without any delay while the odd numbered nodes may receive link-states from the even numbered nodes after a fixed delay. Consequently, at each execution of the method, the two sets of nodes could have different views of the network link-states. The fixed delay could then be varied to generate the results reported in FIG. 13A. For asynchronous execution of an embodiment of the present invention, the odd numbered nodes could be forced to execute the steps of the present invention slower than the even numbered nodes. The difference in the rate of execution was varied in order to obtain the results reported in FIG. 13B. Different step-sizes could be used to prevent oscillations in the two cases. Despite the asynchronous implementation, the embodiment of the present invention still converges to within 1% of the optimal solution. Additionally, there may be a steady increase in the number of iterations required by the embodiments of the present invention as the delay in propagating the link-states or the difference in the rate of executing the present invention increases.

(110) FIG. 14A illustrates the topology of an embodiment of the present invention. More specifically, the illustrated network includes a first node 80A (also called node A), a second node 80B (also called node B), a third node 80C (also called node C), and a fourth node 80D (also called node D), however, a network 50 may include any number of nodes 80. Each network node 80 has two ports 82. Each node 80 may be connected to a NetFPGA 1G platform configured to act as a router.

(111) FIG. 14B includes a photograph of a network of computers according to the present invention.

(112) FIG. 14C illustrates a NetFPGA 1G Board according to the present invention. The NetFPGA is a generally reconfigurable hardware platform configured for high speed networking. A NetFPGA platform includes all of the logic resources, memory and Gigabit Ethernet interfaces to build a complete switch, router, and/or security device. Because the entire datapath may be implemented in hardware, the NetFPGA platform may support back-to-back packets at full Gigabit line rates and has a processing latency measured in only a few clock cycles. An exemplary embodiment of a NetFPGA includes a field programmable gate array logic, Gigabit Ethernet networking ports, static random access memory, double-date rate random access memory, Multi-gigabit I/O, standard PCI form factor, hardware debugging ports, and flexible code.

(113) To quickly achieve multipath functionality in the network 50, packet forwarding decisions may be transferred from the firmware to higher level software which could be easily modified via SCONE (Software Component of NetFPGA). A new table may be added to the software to store the split ratios in addition to the routing table provided in the reference router implementation for the NetFPGA platform. Then a random number generator may be used in conjunction with the routing table and the split ratios table to forward traffic as needed.

(114) Then, the link-state update packets are modified to be broadcast frequently enough to ensure relatively quick convergence of the method and to modify their payload to transmit the link rates. For example, the link-states may be set to broadcast every 250 milliseconds. The network cost function may be represented as Σ.sub.(u,v)ϵEƒ.sub.u,v.sup.2, which results in 2.sub.u,v as the price of each link. Other components of the method such as retrieving the incoming rate into each board and the outgoing rate on each link can be easily obtained from the NetFPGA registers. Also, Dijkstra's method is changed to run with the new link weights instead of hop-count as it was doing in the Reference Router implementation in SCONE.

(115) To further test the system and methods, video traffic may be sent using, for example, a VLC Media Player as a video server from node B to node C. As described above, the KKT conditions of the multi-commodity flow problem are what permit focusing on shortest paths based on the price and use that to claim optimality of the method. From the KKT conditions of the MCF problem, for the given cost function, it is easy to see that the values of the split ratios at optimality should be α.sub.B,A.sup.C=0.25 and α.sub.B,C.sup.C=0.75. The evolution of the split ratios in such an embodiment as captured using SCONE, which comes with the NetFPGA platform, is presented in FIG. 16. Clearly, about 25% of the traffic is sent along the longer path through Port 2 while the rest is sent along the shorter path via Port 1.

(116) In the same network 50 embodiment illustrated in FIG. 15, a flow resulted in a clogged link between node A and node D for about 15 seconds (e.g., using the JPerf tool). The evolution of the split ratios from node B to node C when the heavy flow between node A and node D came online and then stopped is presented in FIG. 17. Initially, α.sub.B,C.sup.C increases to 1 before dropping back down to 0.75 once the large flow stops. The extra traffic that can be seen while the flow from node A to node D is in progress is because some of the traffic is routed via (A,B).fwdarw.(B,C).fwdarw.(C,D). However, most of the traffic from node B to node C is clearly routed via Port 1.

(117) As stated above, certain embodiments of the present invention include an optimal, link-state, hop-by-hop routing method. Advantageously, certain embodiments of the present invention may facilitate capital savings for ISPs by reducing investments in infrastructure to keep utilization of the networks manageable by current suboptimal procedures). In addition, the present invention may facilitate performance benefits for consumers.

(118) Throughout this application, certain systems and methods have been described. Certain embodiments of the systems include a computer system and certain of the method steps may be implemented by a computer system. FIG. 18 illustrates such an exemplary computer system 200. One or more computer systems 200 may carry out the methods presented herein as computer code.

(119) Computer system 200 includes an input/output display interface 202 connected to communication infrastructure 204—such as a bus —, which forwards data such as graphics, text, and information, from the communication infrastructure 204 or from a frame buffer (not shown) to other components of the computer system 200. The input/output display interface 202 may be, for example, a keyboard, touch screen, joystick, trackball, mouse, monitor, speaker, printer, Google Glass® unit, web camera, any other computer peripheral device, or any combination thereof, capable of entering and/or viewing data.

(120) Computer system 200 includes one or more processors 206, which may be a special purpose or a general-purpose digital signal processor that processes certain information. Computer system 200 also includes a main memory 208, for example random access memory (“RAM”), read-only memory (“ROM”), mass storage device, or any combination thereof. Computer system 200 may also include a secondary memory 210 such as a hard disk unit 212, a removable storage unit 214, or any combination thereof. Computer system 200 may also include a communication interface 216, for example, a modem, a network interface (such as an Ethernet card or Ethernet cable), a communication port, a PCMCIA slot and card, wired or wireless systems (such as Wi-Fi, Bluetooth, Infrared), local area networks, wide area networks, intranets, etc.

(121) It is contemplated that the main memory 208, secondary memory 210, communication interface 216, or a combination thereof, function as a computer usable storage medium, otherwise referred to as a computer readable storage medium, to store and/or access computer software including computer instructions. Certain embodiments of a computer readable storage medium do not include any transitory signals or waves. For example, computer programs or other instructions may be loaded into the computer system 200 such as through a removable storage device, for example, a floppy disk, ZIP disks, magnetic tape, portable flash drive, optical disk such as a CD or DVD or Blu-ray, Micro-Electro-Mechanical Systems (“MEMS”), nanotechnological apparatus. Specifically, computer software including computer instructions may be transferred from the removable storage unit 214 or hard disc unit 212 to the secondary memory 210 or through the communication infrastructure 204 to the main memory 208 of the computer system 200.

(122) Communication interface 216 allows software, instructions and data to be transferred between the computer system 200 and external devices or external networks. Software, instructions, and/or data transferred by the communication interface 216 are typically in the form of signals that may be electronic, electromagnetic, optical or other signals capable of being sent and received by the communication interface 216. Signals may be sent and received using wire or cable, fiber optics, a phone line, a cellular phone link, a Radio Frequency (“RF”) link, wireless link, or other communication channels.

(123) Computer programs, when executed, enable the computer system 200, particularly the processor 206, to implement the methods of the invention according to computer software including instructions.

(124) The computer system 200 described herein may perform any one of, or any combination of, the steps of any of the methods presented herein. It is also contemplated that the methods according to the invention may be performed automatically, or may be invoked by some form of manual intervention.

(125) The computer system 200 of FIG. 18 is provided only for the purposes of illustration, such that the invention is not limited to this specific embodiment. It is appreciated that a person skilled in the relevant art knows how to program and implement the invention using any computer system.

(126) The computer system 200 may be a handheld device and include any small-sized computer device including, for example, a personal digital assistant (“PDA”), smart handheld computing device, cellular telephone, or a laptop or netbook computer, hand held console or MP3 player, tablet, or similar hand held computer device, such as an iPad®, iPad Touch® or iPhone®.

(127) FIG. 19 illustrates an exemplary cloud computing system 300 that may be used to implement the methods according to the present invention. The cloud computing system 300 includes a plurality of interconnected computing environments. The cloud computing system 300 utilizes the resources from various networks as a collective virtual computer, where the services and applications can run independently from a particular computer or server configuration making hardware less important.

(128) Specifically, the cloud computing system 300 includes at least one client computer 302. The client computer 302 may be any device through the use of which a distributed computing environment may be accessed to perform the methods disclosed herein, for example, a traditional computer, portable computer, mobile phone, personal digital assistant, tablet to name a few. The client computer 302 includes memory such as random access memory (“RAM”), read-only memory (“ROM”), mass storage device, or any combination thereof. The memory functions as a computer usable storage medium, otherwise referred to as a computer readable storage medium, to store and/or access computer software and/or instructions.

(129) The client computer 302 also includes a communications interface, for example, a modem, a network interface (such as an Ethernet card), a communications port, a PCMCIA slot and card, wired or wireless systems, etc. The communications interface allows communication through transferred signals between the client computer 302 and external devices including networks such as the Internet 304 and cloud data center 306. Communication may be implemented using wireless or wired capability such as cable, fiber optics, a phone line, a cellular phone link, radio waves or other communication channels.

(130) The client computer 302 establishes communication with the Internet 304 —specifically to one or more servers—to, in turn, establish communication with one or more cloud data centers 306. A cloud data center 306 includes one or more networks 310a, 310b, 310c managed through a cloud management system 308. Each network 310a, 310b, 310c includes resource servers 312a, 312b, 312c, respectively. Servers 312a, 312b, 312c permit access to a collection of computing resources and components that can be invoked to instantiate a virtual machine, process, or other resource for a limited or defined duration. For example, one group of resource servers can host and serve an operating system or components thereof to deliver and instantiate a virtual machine. Another group of resource servers can accept requests to host computing cycles or processor time, to supply a defined level of processing power for a virtual machine. A further group of resource servers can host and serve applications to load on an instantiation of a virtual machine, such as an email client, a browser application, a messaging application, or other applications or software.

(131) The cloud management system 308 can comprise a dedicated or centralized server and/or other software, hardware, and network tools to communicate with one or more networks 310a, 310b, 310c, such as the Internet or other public or private network, with all sets of resource servers 312a, 312b, 312c. The cloud management system 308 may be configured to query and identify the computing resources and components managed by the set of resource servers 312a, 312b, 312c needed and available for use in the cloud data center 306. Specifically, the cloud management system 308 may be configured to identify the hardware resources and components such as type and amount of processing power, type and amount of memory, type and amount of storage, type and amount of network bandwidth and the like, of the set of resource servers 312a, 312b, 312c needed and available for use in the cloud data center 306. Likewise, the cloud management system 308 can be configured to identify the software resources and components, such as type of Operating System (“OS”), application programs, and the like, of the set of resource servers 312a, 312b, 312c needed and available for use in the cloud data center 306.

(132) The present invention is also directed to computer products, otherwise referred to as computer program products, to provide software to the cloud computing system 300. Computer products store software on any computer useable medium, known now or in the future. Such software, when executed, may implement the methods according to certain embodiments of the invention. Examples of computer useable mediums include, but are not limited to, primary storage devices (e.g., any type of random access memory), secondary storage devices (e.g., hard drives, floppy disks, CD ROMS, ZIP disks, tapes, magnetic storage devices, optical storage devices, Micro-Electro-Mechanical Systems (“MEMS”), nanotechnological storage device, etc.), and communication mediums (e.g., wired and wireless communications networks, local area networks, wide area networks, intranets, etc.). It is to be appreciated that the embodiments described herein may be implemented using software, hardware, firmware, or combinations thereof.

(133) The cloud computing system 300 of FIG. 19 is provided only for the purposes of illustration and does not limit the invention to this specific embodiment. It is appreciated that a person skilled in the relevant art knows how to program and implement the invention using any computer system or network architecture.

(134) Certain embodiments of the present invention also may be implemented by utilizing software defined networks. In such embodiments, the system and methods may exist on the application layer in the context of software defined networking.

(135) While the disclosure is susceptible to various modifications and alternative forms, specific exemplary embodiments of the present invention have been shown by way of example in the drawings and have been described in detail. It should be understood, however, that there is no intent to limit the disclosure to the particular embodiments disclosed, but on the contrary, the intention is to cover all modifications, equivalents, and alternatives falling within the scope of the disclosure as defined by the appended claims.