Redundant routing with deadlines in data networks
AssigneeLucent Technologies Inc.
InventorsMarvin Kunio Nakayama, Bulent Yener
Life of this patent
Estimating the term…
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.
Claims84
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.
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.
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.
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.
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.
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.
Dependencies are inferred from the claim text.