Selecting multiple paths in overlay networks for streaming data

• US 20050083848A1
• Filed: 10/20/2003
• Published: 04/21/2005
• Est. Priority Date: 10/20/2003
• Status: Active Grant

• Current Assignee: Mitsubishi Electric Research Laboratories, Inc. (Mitsubishi Electric Corporation)
• Original Assignee: Mitsubishi Electric Research Laboratories, Inc. (Mitsubishi Electric Corporation)
• Inventors: Shao, Huai-Rong, Ma, Zheng, Shen, Chia
• Granted Patent: US 7,388,841 B2
• Time in Patent Office: Days
• US Class Current: 370/238
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/123 Evaluation of link metrics techniques for monitoring network metrics H04L43/08
• CPC Class Codes: H04L 45/22 Alternate routing
• CPC Class Codes: H04L 45/42 Centralised routing
• CPC Class Codes: H04L 45/64 using an overlay routing layer
• CPC Class Codes: H04L 47/24 Traffic characterised by specific attributes, e.g. priority or QoS

Abstract

A method selects multiple paths between a server and a client in an overlay network where nodes are connected by links. The nodes include the server and the client. Each path includes a set of selected links. First, in each node, Quality of service metrics are measured of each link directly connecting the node to an immediate neighboring node. The metrics are transmitted to the server. In the server, a link correlation matrix based on the metrics and a path correlation matrix based on the link correlation matrix are determined. Then, the multiple paths are selected based only on the metrics, the link correlation matrix, and the path correlation matrix.

Claims

1. A method for selecting multiple paths between a server and a client in an overlay network having a plurality of nodes connected by links, the plurality of nodes including the server and the client, each path including a set of selected links, comprising:

measuring, in each node, quality of service metrics of each link directly connecting the node to an immediate neighboring node;

transmitting the metrics to the server;

maintaining, in the server, the metrics, a link correlation matrix based on the metrics, and a path correlation matrix based on the link correlation matrix; and

selecting the multiple paths based only on the metrics, the link correlation matrix, and the path correlation matrix.

2. The method of claim 1, further comprising:

streaming data from the server to the client via the multiple paths.

3. The method of claim 1, further comprising:

storing a copy of the data only at the server.

4. The method of claim 2, in which the streaming data are multimedia.

5. The method of claim 1, in which the link correlation matrix is

$\mathrm{Cr}$

( L ij , L mn ) = 1 / 2 + E ⁡

[ ( L ij - L _ ij ) ⁢

( L mn - L _ mn ) ] 2 ⁢

E ⁡

( L ij 2 ) - ( L _ ij ) 2 ⁢

E ⁡

( L mn 2 ) - ( E ⁡

( L _ mn ) ) 2 ,

where ij and mn are a pair of links connecting two nodes, E is an expectation, L_ij and L_mn are the metrics for link ij and link mn, and an average {overscore (L)}_ij=E(L_ij).

6. The method of claim 1, in which the metrics include bandwidth, latency, and packet loss rate of the link.

7. The method of claim 1, in which the measuring, transmitting, maintaining, and selecting are performed dynamically and periodically over a time window.

8. The method of claim 5, in which the path correlation matrix is

$\mathrm{Cr}$

( Path A , Path B ) = ∑

a ∈

A  

⁢

 

⁢

∑

b ∈

B  

⁢

 

⁢

Cr ⁡

( a , b ) ,

where the path_A includes a link set a ∈

A and the path B includes a link set b∈

B.

9. The method of claim 8, further comprising:

first selecting a first path based on the metrics;

updating an available bandwidth of each link according to previously selected paths;

determining a correlation cost (cc) for each link L with respect to a previous selected link set S of a path as

${\mathrm{Cr}}_S^L=\underset{a\in <br><br>S}{\overset{\text{\hspace{1em}<br><br>}}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{Cr}<br><br>\left(L,a\right);<br><br>$

combining the correlation cost and the metrics to obtain a cost for each link using a cost function

${\mathrm{Cost}}_S^L=\mathrm{\alpha <br><br>}·<br><br>{\mathrm{Cr}}_S^L+\underset{i=1}{\overset{R}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>{\mathrm{\alpha <br><br>}}_i<br><br>W_r<br><br>\left(i,j\right),$

where W are the metrics, and α and

α

_I are weighting factors; and

selecting a next shortest path based on the updated cost Cost_S^L; and

repeating the updating, determining, combining, and selecting until the plurality of paths have been selected.