USRE49275EActiveUtility
System and methods for improved network routing
Est. expirySep 28, 2032(~6.2 yrs left)· nominal 20-yr term from priority
H04L 47/17H04L 45/24H04L 45/123H04L 45/48H04L 45/22
62
PatentIndex Score
1
Cited by
23
References
69
Claims
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
exact text as granted — not AI-modifiedWhat is claimed is:
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 appliedroute 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 is dynamically adjusted, a split ratio weighting factor expressed as,in the pathway between the source node and the destination node in the network according to:
if
r
u
t
>
0
,
α
˙
u
,
v
t
=
-
α
u
,
v
t
δ
η
u
t
r
u
t
,
v
≠
v
¯
[
TagBox[StyleBox["[", Rule[FontWeight, "Bold"]], "["]
α
˙
u
,
v
t
=
-
∑
v
:
(
u
,
v
)
∈
𝔼
,
v
≠
v
¯
α
˙
u
,
v
t
]
TagBox[StyleBox["]", Rule[FontWeight, "Bold"]], "]"]
α
˙
u
,
v
¯
t
=
-
∑
v
:
(
u
,
v
)
∈
𝔼
,
v
≠
v
¯
α
˙
u
,
v
t
else
if
r
u
t
=
0
,
α
u
,
v
t
=
0
,
v
≠
v
¯
α
u
,
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
wherein the network is an electronic data network.
2. The system of claim 1 , wherein the compute step includes split ratio weighting factor is further computed by:
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 (η u t )for the shortest pathway from the source node to the destination node; and
at every subsequent node, setting η u t ←η u t b, 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 , 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:
if
r
u
t
>
0
,
α
˙
u
,
v
t
=
-
α
u
,
v
t
δ
η
u
t
r
u
t
,
v
≠
v
¯
α
˙
u
,
v
¯
t
=
-
∑
v
:
(
u
,
v
)
∈
𝔼
,
v
≠
v
¯
α
˙
u
,
v
t
else
if
r
u
t
=
0
,
α
u
,
v
t
=
0
,
v
≠
v
¯
α
u
,
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
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.
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.
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.
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.
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.
21. The system of claim 20, wherein the at least one routing component dynamically adapts to changes in traffic on the network.
22. The system of claim 20, wherein the parameters include changes in network topology.
23. The system of claim 20, wherein the parameters include variations in network traffic.
24. The system of claim 20, wherein the parameters include the link state information.
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.
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.
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.
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.
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.
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.
31. The system of claim 17, wherein the at least one node including the LSR includes a single node including the LSR.
32. The system of claim 17, wherein the at least one node including the LSR includes two or more nodes each including the LSR.
33. The system of claim 17, wherein the at least one node including the LSR includes the plurality of nodes each including the LSR.
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.
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.
36. The system of claim 19, wherein the link state information includes updated link state information.
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.
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.
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.
40. The system of claim 39, wherein the dynamic adjusting comprises reducing a number of packets along non-shortest paths to the destination node.
41. The system of claim 39, wherein the dynamic adjusting comprises increasing a number of packets along the shortest path to the destination node.
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.
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.
44. The system of claim 43, wherein the rate of decrease is proportional to a value of the selected split ratio.
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.
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.
47. The system of claim 46, wherein the best route comprises a lowest cost route through the network.
48. The system of claim 46, wherein the best route comprises a shortest route through the network.
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.
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.
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.
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.
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.
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.
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.
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.
57. The system of claim 56, wherein the control plane is distributed among the plurality of nodes.
58. The system of claim 56, wherein the control plane comprises at least one of software and hardware.
59. The system of claim 56, wherein the data plane comprises at least one of software and hardware.
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.
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.
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.
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.
64. The system of claim 17 wherein selecting the split ratio comprises computing a split ratio weighting factor expressed as:
if
r
u
t
>
0
,
α
˙
u
,
v
t
=
-
α
u
,
v
t
δ
η
u
t
r
u
t
,
v
≠
v
¯
α
˙
u
,
v
¯
t
=
-
∑
v
:
(
u
,
v
)
∈
𝔼
,
v
≠
v
¯
α
˙
u
,
v
t
else
if
r
u
t
=
0
,
α
u
,
v
t
=
0
,
v
≠
v
¯
α
u
,
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.
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 (η u t ) for the shortest path from the source node to the destination node; and at every subsequent node, setting η u t ←η u t b, 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.
66. The system of claim 17, wherein the traffic comprises one or more information packets.
67. The system of claim 17, wherein the network is an electronic data network.
68. The system of claim 17, wherein each of the plurality of nodes is a router.
69. The system of claim 17, wherein each of the plurality of nodes is a computer system.Cited by (0)
No later patents cite this yet.
References (0)
No backward citations on record.