초록 ▼

A coding approach for a robust and flexible network communication protocol is described. By using coding, it is possible to eliminate the need to track packet identities, and hence, it is possible to reduce coordination overhead associated with many conventional protocols. The method and system desc

A coding approach for a robust and flexible network communication protocol is described. By using coding, it is possible to eliminate the need to track packet identities, and hence, it is possible to reduce coordination overhead associated with many conventional protocols. The method and system described herein takes advantage of multiple paths, interfaces, mediums, servers, and storage locations available in a network. The proposed protocol allows quick response to congestion by load balancing over different network resources. The method also enables soft vertical hand-overs across heterogeneous networks. In one embodiment, a media file is divided into chunks and transmitted using a transport protocol tailored to meet delay requirements of media streaming applications. Also described are different coding strategies for chunk delivery based upon an urgency level of each chunk.

대표청구항 ▼

1. In a network, a method of transmitting data from a source node to a destination node, the method comprising: (a) forming linear combinations of packets at the source node, wherein the linear combinations of packets represent the data to be transmitted;(b) delivering the linear combinations of pac

1. In a network, a method of transmitting data from a source node to a destination node, the method comprising: (a) forming linear combinations of packets at the source node, wherein the linear combinations of packets represent the data to be transmitted;(b) delivering the linear combinations of packets formed at the source node from the source node to the destination node over multiple network paths, wherein no additional coding of the data is done between the source node and the destination node, wherein the source node includes a number of available tokens and delivering linear combinations of packets includes delivering a linear combination of packets for each token available at the source node;(c) providing feedback from the destination node to the source node in response to receipt of linear combinations, wherein the feedback is sent over the same network path that the corresponding linear combination was delivered over, wherein providing feedback includes returning corresponding tokens to the source node;(d) estimating congestion in individual network paths at the source node using feedback received from the destination node;(e) changing transmit rates within the multiple network paths based upon estimated congestion; and(f) forming new linear combinations of packets at the source node based on returned tokens associated with the feedback and delivering the new linear combinations of packets from the source node to the destination node. 2. The method of claim 1 wherein: providing feedback includes checking each linear combination received at the destination node to determine whether the linear combination is linearly independent from previously received linear combinations and sending an acknowledgement to the source node if the received linear combination is linearly independent from previously received linear combinations;each of the multiple network paths has a corresponding number of tokens that is indicative of an amount of data that can be transmitted within the path without acknowledgement; andchanging transmit rates within the multiple network paths includes changing a number of tokens associated with a first path. 3. The method of claim 1 further comprising repeating (c)-(e) until the original data is decoded at the destination node. 4. The method of claim 1 wherein the source is a server and the destination is a client. 5. The method of claim 1 wherein the linear combinations of packets are formed using a plurality of packets that represent a file. 6. The method of claim 1 wherein (a) and (b) are implemented in one of: a link layer;a transport layer; andan application layer. 7. The method of claim 1 wherein forming linear combinations of packets comprises generating a linear combination of packets at random or deterministically. 8. The method of claim 5 wherein the linear combinations of packets each comprise all packets which make up the file. 9. The method of claim 5 wherein the linear combinations of packets each comprise a subset of the packets which make up the file. 10. The method of claim 1 wherein forming linear combinations of packets comprises forming a random linear combination of a subset of packets in the plurality of packets. 11. The method of claim 10 wherein the subset of packets is selected randomly or deterministically. 12. The method of claim 1 wherein forming linear combinations of packets includes forming a first coded packet, the first coded packet including a first linear combination of packets and coefficients used to form the first linear combination of packets. 13. The method of claim 1 wherein the one or more network paths are established through one or more network interfaces at the client. 14. The method of claim 13 wherein the one or more network interfaces at the client includes multiple network interfaces that use one of: the same access technology or different access technologies. 15. The method of claim 14 wherein the access technology corresponds to one or more of Bluetooth, WiFi, 2G, 3G and 4G technologies. 16. The method of claim 1 wherein (a) is implemented in an application layer and (b) is implemented in a link layer or a transport layer. 17. The method of claim 16 wherein (b) is implemented using tunneling through a User Datagram Protocol (UDP) connection. 18. A method for transmitting a file between one or more servers and one or more clients through one or more network paths, the method comprising: (a) for M information packets, generating a number of linearly coded packets at a server, each linearly coded packet including a linear combination of the M information packets, wherein the M information packets represent data from the file to be transmitted to a client, wherein M is an integer greater than zero;(b) sending linearly coded packets from the server to the client, wherein the server includes a number of available tokens and sending linearly coded packets includes sending a linearly coded packet for each token available at the server;(c) upon reception of linearly coded packets at the client, providing feedback from the client to the server, wherein providing feedback includes returning corresponding tokens to the server;(d) based upon returned tokens associated with the feedback from the client, forming new linear combinations of packets at the server; and(e) delivering the new combinations of packets from the server to the client. 19. The method of claim 18 further comprising repeating (c)-(e) until the original file is decoded at the client. 20. The method of claim 18 wherein sending comprises transmitting linearly coded packets having a fixed packet size. 21. The method of claim 18 wherein the server uses tokens within the feedback provided by the client to estimate network conditions in the path from the server to the client. 22. The method of claim 18, wherein: sending linearly coded packets from the server to the client includes sending the linearly coded packets via multiple different paths;providing feedback from the client to the server includes sending the feedback via respective paths; anddelivering the new combinations of packets from the server to the client includes adjusting rates in the multiple different paths based on the feedback. 23. The method of claim 18, wherein the method includes transmitting the file from multiple servers to the client, wherein information packets stored at each different server either fully describe the file or include partial information about the file. 24. The method of claim 23, wherein information packets stored at each different server include partial information about the file and the partial information at the servers is stored in a coded fashion. 25. The method of claim 18, wherein: (a) and (d) are implemented in an application layer and (b) and (e) are implemented in a link layer or a transport layer. 26. The method of claim 25 wherein (b) and (e) are implemented using tunneling through a User Datagram Protocol (UDP) connection. 27. A method for transmitting original information between one or more sources and one or more destinations, the method comprising: (a) for M information packets, generating NM linearly coded packets at one of the one or more sources, wherein the M information packets represent the original information to be transmitted from at least one of the one or more sources to one of the one or more destinations, wherein M is an integer greater than zero; each of the NM linearly coded packets including a linear combination of the M information packets, wherein NM is an integer number of initial linearly coded packets to be generated at the one of the one or more sources;(b) delivering the NM linearly coded packets from the source to one of the one or more destinations, wherein the source includes a number of available tokens and delivering NM linear coded packets includes sending a linear coded packet for each token available at the server;(c) upon reception of linear coded packets at the destination, providing feedback from the destination to the source, wherein providing feedback includes returning corresponding tokens to the source;(d) based upon the feedback from the destination, forming a new linearly coded packet at the source, wherein forming a new linearly coded packet includes detecting a failure of delivery of a linearly coded packet associated with a first token and re-generating the first token within the source in response thereto; and(e) delivering the new linearly coded packet from the source to the destination. 28. The method of claim 27 further comprising repeating (c)-(e) until the original information is decoded at the destination. 29. The method of claim 27, wherein: (a) and (d) are implemented in an application layer and (b) and (e) are implemented in a link layer or a transport layer. 30. The method of claim 29 wherein (b) and (e) are implemented using tunneling through a User Datagram Protocol (UDP) connection. 31. A method of transmitting data from a source node to a destination node, the method comprising implementing a network coding based protocol technique in an application layer by tunneling network coded data over a User Datagram Protocol (UDP) connection such that all network coding operations and network coding control techniques are performed at the application layer on top of UDP and such that the coding operations are performed in an end-to-end manner between the source and destination node, wherein a number of linear combinations of packets delivered from the source node to the destination node is controlled by the use of tokens, wherein the source node includes a number of available tokens and a linear combination of packets is delivered from the source node to the destination node for each available token, wherein feedback is provided from the destination node to the source node in response to receipt of linear combinations, the feedback including corresponding tokens. 32. In a network utilizing a User Datagram Protocol (UDP), a method of transmitting data from a source node to a destination node, the method comprising: (a) in an application layer, forming linear combinations of packets at the source node wherein the linear combinations of packets represent the data to be transmitted;(b) in one of a link layer or a transport layer, delivering the same linear combinations of packets formed at the source node from the source node to the destination node over one or more network paths wherein no additional coding of the data is done between the source node and the destination node, wherein the source node includes a number of available tokens and delivering linear combinations of packets includes delivering a linear combination of packets for each token available at the source node;(c) providing feedback from the destination node to the source node in response to receipt of linear combinations, wherein providing feedback includes checking each linear combination received at the destination node to determine whether the linear combination is linearly independent from previously received linear combinations and sending an acknowledgement to the source node if the received linear combination is linearly independent from previously received linear combinations, wherein providing feedback includes returning corresponding tokens to the source node;(d) in the application layer, based upon the tokens within the feedback from the source node, forming new linear combinations of packets at the source node; and(e) in one of the link layer or the transport layer, delivering the new linear combinations of packets from the source node to the destination node. 33. The method of claim 32 wherein delivering the same linear combination of packets is implemented using a tunneling protocol through a UDP connection such that all coding operations and control techniques are performed at the application layer on top of UDP to provide a coding operation performed in an end-to-end manner. 34. In a network utilizing a User Datagram Protocol (UDP), a method of transmitting data from a source node to a destination node, the method comprising: (a) forming linear combinations of packets at the source node wherein the linear combinations of packets represent the data to be transmitted;(b) delivering the same linear combinations of packets formed at the source node from the source node to the destination node over one or more network paths wherein no additional coding of the data is done between the source node and the destination node, wherein the source node includes a number of available tokens and delivering linear combinations of packets includes delivering a linear combination of packets for each token available at the source node;(c) providing feedback from the destination node to the source node in response to receipt of linear combinations, wherein providing feedback includes checking each linear combination received at the destination node to determine whether the linear combination is linearly independent from previously received linear combinations and sending an acknowledgement to the source node if the received linear combination is linearly independent from previously received linear combinations, wherein providing feedback includes returning corresponding tokens to the source node;(d) based upon the tokens within the feedback from the source node, forming new linear combinations of packets at the source node; and(e) delivering the new linear combinations of packets from the source node to the destination node. 35. The method of claim 34 wherein forming linear combinations of packets at the source node comprises forming linear combinations of packets in an application layer. 36. The method of claim 34 wherein delivering the same linear combination of packets comprises delivering the same linear combination of packets in one of a link layer or a transport layer.