Dynamic optimal path selection in multiple communications networks

• US 7,099,277 B2
• Filed: 02/20/2002
• Issued: 08/29/2006
• Est. Priority Date: 02/20/2002
• Status: Expired due to Fees

• Current Assignee: Mitsubishi Electric Research Laboratories, Inc. (Mitsubishi Electric Corporation)
• Original Assignee: Mitsubishi Electric Research Laboratories, Inc. (Mitsubishi Electric Corporation)
• Inventors: Vetro, Anthony, Sahinoglu, Zafer
• Primary Examiner(s): Nguyen, Steven
• Assistant Examiner(s): HAN, CLEMENCE S
• Application Number:
  US10/079,096
• Publication Number:
  US 20030156543A1
• Time in Patent Office: 1,651 Days
• Field of Search: None
• US Class Current: 370/238
• CPC Class Codes: H04L 12/5692 Selection among different networks
• CPC Class Codes: H04L 67/14 Session management for real-time applications in data packet communications networks H04L65/1066
• CPC Class Codes: H04L 67/303 Terminal profiles
• CPC Class Codes: H04L 67/306 User profiles
• CPC Class Codes: H04L 67/52 specially adapted for the location of the user terminal
• CPC Class Codes: H04L 67/565 Conversion or adaptation of application format or content adding application control or application functional data H04L67/561
• CPC Class Codes: H04L 69/329 in the application layer [OSI layer 7]
• CPC Class Codes: H04L 9/40 Network security protocols

Abstract

A method and system connects a first terminal via multiple networks to a second terminal. An environment description is acquired and parsed by a description parser into cost parameters using a set of rules. An objective function evaluates the cost parameters to determine an optimal path to connect the first terminal to the second terminal through the multiple networks using a switch. The selection of the optimal path can be done periodically during a particular application session.

Claims

1. A method for connecting a first terminal via a plurality of networks to a second terminal, comprising:

acquiring an environment description;

parsing the environment description into cost parameters using a set of rules;

modeling an objective function as a lattice;

evaluating the objective function using the cost parameters and a Viterbi decoder to solve for a minimum cost; and

selecting an optimal path through the plurality of networks based on a minimum cost to connect the first terminal to the second terminal.

2. The method of claim 1 wherein the environment description includes a network description for each of the networks.

3. The method of claim 2 wherein each of the networks includes a plurality of links, and each network description includes connection cost, bandwidth, utilization, and capacity of each link.

4. The method of claim 2 wherein each network description includes end-to-end delay, delay variation, error characteristics, and packet loss rate for each network.

5. The method of claim 4 wherein the objective function is:

$\begin{array}{cc}\underset{\_}{\min <br><br><br><br>\underset{\underset{\forall <br><br>i,j}{m=1}}{\overset{n-1}{\sum <br><br>}}<br><br>(C_{\mathrm{ij}}(}& {m,m+1)-R<br><br>\left(m,m+1\right))}^2,\end{array}$

where i and j are paths through the plurality of networks, C is a cost of selecting a different optimal path for a time interval including a maximum of n time slots, each time slot of length m, and R is a cost of meeting quality of service requirements.

6. The method of claim 1 wherein the environment description includes a terminal description for each terminal.

7. The method of claim 6 wherein each terminal description includes hardware and software descriptions for each terminal.

8. The method of claim 1 wherein the environment description includes a delivery description.

9. The method of claim 8 wherein the delivery description specifies transport protocols.

10. The method of claim 1 wherein the environment description includes a user preference description.

11. The method of claim 10 wherein the user preference description includes filtering, search, browsing, and display preferences.

12. The method of claim 10 wherein the user preference description includes user demographic information.

13. The method of claim 1 wherein the environment description includes a natural environment description.

14. The method of claim 13 wherein the natural environment description specifies a location and a type of location of each terminal.

15. The method of claim 1 wherein the environment description includes a service description.

16. The method of claim 15 wherein the service description specifies service capabilities.

17. The method of claim 1 wherein the acquiring, parsing, evaluating, and selecting is performed periodically to dynamically select the optimal path for a particular time interval.

18. The method of claim 1 wherein the optimal path passes through a subset of the plurality of networks.

19. The method of claim 1 wherein the evaluating considers content bandwidth requirements.

20. The method of claim 1 further comprising:

acquiring a content description of content;

parsing the content description into cost parameters of the content; and

evaluating the objective function using the cost parameters of the content;

adapting the content according to the parsed content description and the parsed environment description to form adapted content; and

delivering the adapted content over the selected optimal path.

21. The method of claim 1 wherein the cost parameters are known.

22. The method of claim 1 wherein the cost parameters are predicted.

23. The method of claim 1 wherein the cost parameters include a time dependent path cost parameter, and a traffic dependent quality of service parameter.

24. The method of claim 1 wherein the networks have different capacity and different available bandwidth.

25. The method of claim 1 wherein each network is defined by time-variant and time-independent cost parameters.

26. The method of claim 1 wherein the first terminal is a content server configured to transmit a video and the second terminal is a client terminal configured to receive the video.

27. A system for connecting a first terminal via a plurality of networks to a second terminal, comprising:

an environment parser periodically acquiring and parsing an environment description of the plurality of networks into cost parameters;

means for modeling an objective function as a lattice;

an evaluator evaluating the objective function to determine a minimum cost using the cost parameters and a Viterbi decoder;

means for selecting an optimum path through the plurality of networks based on the minimum cost; and

a switch connecting the first terminal to the second terminal via the optimal path for a predetermined time period.

28. A method for connecting a first terminal via a plurality of networks to a second terminal, comprising:

acquiring an environment description;

parsing the environment description into cost parameters using a set of rules;

evaluating an objective function using the cost parameters;

selecting an optimal path through the plurality of networks based on a minimum cost to connect the first terminal to the second terminal;

acquiring a content description of content;

parsing the content description into cost parameters of the content; and

evaluating the objective function using the cost parameters of the content;

adapting the content according to the parsed content description and the parsed environment description to form adapted content; and

delivering the adapted content over the selected optimal path.