Redundant routing with deadlines in data networks

• US 6,661,775 B1
• Filed: 08/05/1999
• Issued: 12/09/2003
• Est. Priority Date: 08/05/1999
• Status: Expired due to Term

• Current Assignee: WSOU Investments, LLC (WSOU Holdings, LLC)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Yener, Bulent, Nakayama, Marvin Kunio
• Primary Examiner(s): Kizou, Hassan
• Assistant Examiner(s): Elallam, Ahmed
• Application Number:
  US09/368,931
• Time in Patent Office: 1,587 Days
• Field of Search: 370/218, 370/229, 370/230.1, 370/231-235, 370/242, 370/244, 370/245, 370/252, 370/253, 370/255, 370/351, 370/389, 370/390, 370/394, 370/395.1, 370/395.2, 370/395.4, 370/395.43, 370/400, 370/412, 370/432, 370/437, 370/450, 370/902, 709/103-105, 709/232-238
• US Class Current: 370/230.1
• CPC Class Codes: H04L 45/24 Multipath
• CPC Class Codes: H04L 45/302 Route determination based on requested QoS
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/24 Traffic characterised by specific attributes, e.g. priority or QoS
• CPC Class Codes: H04L 47/28 in relation to timing considerations
• CPC Class Codes: H04L 47/36 by determining packet size, e.g. maximum transfer unit [MTU]
• CPC Class Codes: H04L 47/43 Assembling or disassembling of packets, e.g. segmentation and reassembly [SAR]
• CPC Class Codes: H04L 67/06 specially adapted for file transfer, e.g. file transfer protocol [FTP]
• CPC Class Codes: H04L 69/14 Multichannel or multilink protocols
• CPC Class Codes: H04L 69/329 in the application layer [OSI layer 7]
• CPC Class Codes: H04L 69/40 for recovering from a failure of a protocol instance or entity, e.g. service redundancy protocols, protocol state redundancy or protocol service redirection management of faults, events, alarms or notifications in data switching networks H04L41/06
• CPC Class Codes: H04L 9/40 Network security protocols

Abstract

A method and message router that breaks up files to be transferred over a network connection within a specified deadline into fixed-sized pieces. Each piece contains enough redundant information so that a subset (but not all) of the pieces will be sufficient to construct the file at the destination. The method and router determine optimal values for the number of pieces the file should be split into and the subset of pieces required to reconstruct the full contents of the file in order to maximize the probability that the file can be reconstructed at the destination by the specified deadline. The method and router provide an expected QoS guarantee by using redundancy with a deadline rather than reservations.

Claims

1. A computer implemented method of transmitting a file within a time deadline from an origin to a destination connected to a computer network, comprising the steps of:

inputting at the origin network information, the network information comprising an identity of physical links between the origin and destination and performance parameters associated with each link;

computing a virtual network topology based on the physical link information, the virtual topology including a plurality of virtual links between the origin and destination;

splitting the file into a plurality of fixed-size pieces to be transmitted to the destination over respective virtual links and reconstructed within the time deadline, each of the fixed-size pieces containing redundant information so that only a subset of the plurality of pieces is required to reconstruct the file; and

transmitting the plurality of pieces to the destination over their respective virtual links.

2. The method of claim 1 wherein said splitting step comprises:

determining an optimal number of pieces and an optimal piece size such that a probability that the determined optimal number of pieces of the optimal piece size will be reconstructed at the destination within the time deadline; and

splitting the file into the optimal number of pieces, each piece being of the determined optimal size.

3. The method of claim 2 wherein said step of splitting the file into the optimal number of pieces is performed using an information dispersal algorithm.

4. The method of claim 2 wherein said determining step is performed using a single piece constraint.

5. The method of claim 4 wherein said determining step uses a rate distribution of the virtual links to determine an expected traffic along the virtual links.

6. The method of claim 5 wherein said rate distribution is a geometric rate distribution.

7. The method of claim 5 wherein said rate distribution is an uniform rate distribution.

8. The method of claim 5 wherein said rate distribution includes a rate penalty function to determine an impact of performance of the virtual links due to transmitting the pieces over the virtual links.

9. The method of claim 8 wherein the penalty function is a linear function of a number of the fixed-size pieces, a size of the pieces and a size of the file.

10. The method of claim 8 wherein the penalty function is a quadratic function of a number of the fixed-size pieces, a size of the pieces and a size of the file.

11. The method of claim 8 wherein the penalty function is an exponential function of a number of the fixed-size pieces, a size of the pieces and a size of the file.

12. The method of claim 2 wherein said determining step is performed using an arbitrary piece constraint.

13. The method of claim 12 wherein said determining step uses a rate distribution of the virtual links to determine an expected traffic along the virtual links.

14. The method of claim 13 wherein said rate distribution is a geometric rate distribution.

15. The method of claim 13 wherein said rate distribution is an uniform rate distribution.

16. The method of claim 13 wherein said rate distribution includes a rate penalty function to determine an impact of performance of the virtual links due to transmitting the pieces over the virtual links.

17. The method of claim 16 wherein the penalty function is a linear function of a number of the fixed-size pieces, a size of the pieces and a size of the file.

18. The method of claim 16 wherein the penalty function is a quadratic function of a number of the fixed-size pieces, a size of the pieces and a size of the file.

19. The method of claim 16 wherein the penalty function is an exponential function of a number of the fixed-size pieces, a size of the pieces and a size of the file.

20. A computer implemented method of providing an expected quality of service guarantee to an application of computer network, comprising the steps of:

inputting a file and a time deadline to an origin of the network from the application;

inputting at the origin network information, the network information comprising an identity of physical links between the origin and a destination of the network and performance parameters associated with each link;

computing a virtual network topology based on the physical link information, the virtual topology including a plurality of virtual links between the origin and destination;

splitting the file into a plurality of fixed-size pieces to be transmitted to the destination over respective virtual links and reconstructed within the time deadline, each of the fixed-size pieces containing redundant information so that only a subset of the plurality of pieces is required to reconstruct the file;

transmitting the plurality of pieces to the destination over their respective virtual links;

receiving the pieces at the destination; and

reconstructing the file from a subset of the received pieces.

21. The method of claim 20 wherein said splitting step comprises:

determining an optimal number of pieces and an optimal piece size such that a probability that the determined optimal number of pieces of the optimal piece size will be reconstructed at the destination within the time deadline; and

splitting the file into the optimal number of pieces, each piece being of the determined optimal size.

22. The method of claim 21 wherein said step of splitting the file into the optimal number of pieces is performed using an information dispersal algorithm.

23. The method of claim 21 wherein said determining step is performed using a single piece constraint.

24. The method of claim 23 wherein said determining step uses a rate distribution of the virtual links to determine an expected traffic along the virtual links.

25. The method of claim 24 wherein said rate distribution is a geometric rate distribution.

26. The method of claim 24 wherein said rate distribution is an uniform rate distribution.

27. The method of claim 24 wherein said rate distribution includes a rate penalty function to determine an impact of performance of the virtual links due to transmitting the pieces over the virtual links.

28. The method of claim 27 wherein the penalty function is a linear function of a number of the fixed-size pieces, a size of the pieces and a size of the file.

29. The method of claim 27 wherein the penalty function is a quadratic function of a number of the fixed-size pieces, a size of the pieces and a size of the file.

30. The method of claim 27 wherein the penalty function is an exponential function of a number of the fixed-size pieces, a size of the pieces and a size of the file.

31. The method of claim 21 wherein said determining step is performed using an arbitrary piece constraint.

32. The method of claim 21 wherein said determining step uses a rate distribution of the virtual links to determine an expected traffic along the virtual links.

33. The method of claim 32 wherein said rate distribution is a geometric rate distribution.

34. The method of claim 32 wherein said rate distribution is an uniform rate distribution.

35. The method of claim 32 wherein said rate distribution includes a rate penalty function to determine an impact of performance of the virtual links due to transmitting the pieces over the virtual links.

36. The method of claim 35 wherein the penalty function is a linear function of a number of the fixed-size pieces, a size of the pieces and a size of the file.

37. The method of claim 35 wherein the penalty function is a quadratic function of a number of the fixed-size pieces, a size of the pieces and a size of the file.

38. The method of claim 35 wherein the penalty function is an exponential function of a number of the fixed-size pieces, a size of the pieces and a size of the file.

39. A computer network router, comprising:

a controller, said controller being coupled to a computer network, said controller transmitting a file within a time deadline to a destination router connected to the computer network by;

inputting network information, the network information comprising an identity of physical links between said router and the destination router and performance parameters associated with each link;

computing a virtual network topology based on the physical link information, the virtual topology including a plurality of virtual links between said router and the destination;

splitting the file into a plurality of fixed-size pieces to be transmitted to the destination over respective virtual links and reconstructed within the time deadline, each of the fixed-size pieces containing redundant information so that only a subset of the plurality of pieces is required to reconstruct the file; and

transmitting the plurality of pieces to the destination over their respective virtual links.

40. The router of claim 39 wherein said controller splits the file by:

determining an optimal number of pieces and an optimal piece size such that a probability that the determined optimal number of pieces of the optimal piece size will be reconstructed at the destination within the time deadline; and

splitting the file into the optimal number of pieces, each piece being of the determined optimal size.

41. The router of claim 39 wherein said controller splits the file into the optimal number of pieces by using an information dispersal algorithm.

42. The router of claim 39 wherein said controller determines the optimal number of pieces and the optimal piece size using a single piece constraint.

43. The router of claim 42 wherein said controller determines the optimal number of pieces and the optimal piece size using a rate distribution of the virtual links to determine an expected traffic along the virtual links.

44. The router of claim 43 wherein said rate distribution is a geometric rate distribution.

45. The router of claim 43 wherein said rate distribution is an uniform rate distribution.

46. The router of claim 43 wherein said rate distribution includes a rate penalty function to determine an impact of performance of the virtual links due to transmitting the pieces over the virtual links.

47. The router of claim 46 wherein the penalty function is a linear function of a number of the fixed-size pieces, a size of the pieces and a size of the file.

48. The router of claim 46 wherein the penalty function is a quadratic function of a number of the fixed-size pieces, a size of the pieces and a size of the file.

49. The router of claim 46 wherein the penalty function is an exponential function of a number of the fixed-size pieces, a size of the pieces and a size of the file.

50. The router of claim 40 wherein said controller splits the file into the optimal number of pieces by using an arbitrary piece constraint.

51. The router of claim 50 wherein said controller determines the optimal number of pieces and the optimal piece size using a rate distribution of the virtual links to determine an expected traffic along the virtual links.

52. The router of claim 51 wherein said rate distribution is a geometric rate distribution.

53. The router of claim 51 wherein said rate distribution is an uniform rate distribution.

54. The router of claim 51 wherein said rate distribution includes a rate penalty function to determine an impact of performance of the virtual links due to transmitting the pieces over the virtual links.

55. The router of claim 54 wherein the penalty function is a linear function of a number of the fixed-size pieces, a size of the pieces and a size of the file.

56. The router of claim 54 wherein the penalty function is a quadratic function of a number of the fixed-size pieces, a size of the pieces and a size of the file.

58. The router of claim 39 wherein said controller is a programmed processor.

59. The router of claim 39 wherein said controller is an application specific integrated circuit.

57. The router of 54 wherein the penalty function is an exponential function of a number of the fixed-size pieces, a size of the pieces and a size of the file.

60. A computer system comprising:

a network communication medium;

a first router coupled to said communication medium;

a second router coupled to said communication medium and in communication with said first router;

said first router having a first controller, said first controller transmitting a file within a time deadline to said second router by;

inputting network information, the network information comprising an identity of physical links between said first router and said second router and performance parameters associated with each link;

computing a virtual network topology based on the physical link information, the virtual topology including a plurality of virtual links between said first router and said second router;

splitting the file into a plurality of fixed-size pieces to be transmitted to said second router over respective virtual links and reconstructed within the time deadline, each of the fixed-size pieces containing redundant information so that only a subset of the plurality of pieces is required to reconstruct the file;

transmitting the plurality of pieces to the destination over their respective virtual links; and

said second router having a second controller, said second controller receiving the transmitted pieces and reconstructing the file from a subset of the received pieces.

61. The system of claim 60 wherein said first controller splits the file by:

determining an optimal number of pieces and an optimal piece size such that a probability that the determined optimal number of pieces of the optimal piece size will be reconstructed at the destination within the time deadline; and

splitting the file into the optimal number of pieces, each piece being of the determined optimal size.

62. The system of claim 61 wherein said first controller splits the file into the optimal number of pieces by using an information dispersal algorithm.

63. The system of claim 61 wherein said first controller determines the optimal number of pieces and the optimal piece size using a single piece constraint.

64. The system of claim 61 wherein said first controller determines the optimal number of pieces and the optimal piece size using a rate distribution of the virtual links to determine an expected traffic along the virtual links.

65. The system of claim 64 wherein said rate distribution is a geometric rate distribution.

66. The system of claim 64 wherein said rate distribution is an uniform rate distribution.

67. The system of claim 64 wherein said rate distribution includes a rate penalty function to determine an impact of performance of the virtual links due to transmitting the pieces over the virtual links.

68. The system of claim 67 wherein the penalty function is a linear function of a number of the fixed-size pieces, a size of the pieces and a size of the file.

69. The system of claim 67 wherein the penalty function is a quadratic function of a number of the fixed-size pieces, a size of the pieces and a size of the file.

70. The system of claim 67 wherein the penalty function is an exponential function of a number of the fixed-size pieces, a size of the pieces and a size of the file.

71. The system of claim 61 wherein said first controller splits the file into the optimal number of pieces by using an arbitrary piece constraint.

72. The system of claim 71 wherein said first controller determines the optimal number of pieces and the optimal piece size using a rate distribution of the virtual links to determine an expected traffic along the virtual links.

73. The system of claim 72 wherein said rate distribution is a geometric rate distribution.

74. The system of claim 72 wherein said rate distribution is an uniform rate distribution.

75. The system of claim 72 wherein said rate distribution includes a rate penalty function to determine an impact of performance of the virtual links due to transmitting the pieces over the virtual links.

76. The system of claim 75 wherein the penalty function is a linear function of a number of the fixed-size pieces, a size of the pieces and a size of the file.

77. The system of claim 75 wherein the penalty function is a quadratic function of a number of the fixed-size pieces, a size of the pieces and a size of the file.

79. The system of claim 61 wherein said first controller is a programmed processor.

80. The system of claim 61 wherein said first controller is an application specific integrated circuit.

81. The system of claim 61 wherein said second controller is a programmed processor.

82. The system of claim 61 wherein said second controller is an application specific integrated circuit.

83. The system of claim 61 wherein said communication medium is connected to a high-speed packet switching network.

84. The system of claim 61 wherein said communication medium is connected to the Internet.

78. The system of 75 wherein the penalty function is an exponential function of a number of the fixed-size pieces, a size of the pieces and a size of the file.