System and methods for improved network routing

Patent metadata

Field	Value
Publication number	US-RE49275-E
Application number	US-201316174685-A
Country	US
Kind code	E1
Filing date	Sep 27, 2013
Priority date	Sep 28, 2012
Publication date	Nov 1, 2022
Grant date	Nov 1, 2022

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.

First claim

What 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

Assignees

• Univ Cornell

Inventors

• Michael Nithin
• Tang Ao

Classifications

• H04L47/17

  Interaction among intermediate nodes, e.g. hop by hop · CPC title

• H04L45/24

  Multipath · CPC title

• H04L45/123 Primary

  Evaluation of link metrics (techniques for monitoring network metrics H04L43/08) · CPC title

• H04L45/48

  Routing tree calculation · CPC title

• H04L45/22

  Alternate routing · CPC title