System and methods for improved network routing

Patent metadata

Field	Value
Publication number	US-9521067-B2
Application number	US-201314429660-A
Country	US
Kind code	B2
Filing date	Sep 27, 2013
Priority date	Sep 28, 2012
Publication date	Dec 13, 2016
Grant date	Dec 13, 2016

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 applied in at least one of the two or more nodes is dynamically adjusted, 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 number of branches 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.

2. The system of claim 1 , wherein the compute step includes:
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 syste

Assignees

• Univ Cornell

Inventors

• Michael Nithin
• Tang Ao

Classifications

• H04L45/123 Primary

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

• H04L47/17

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

• H04L45/24

  Multipath · CPC title

• H04L45/48

  Routing tree calculation · CPC title