Method and device for managing allocation of data transmission paths in a meshed communications network, corresponding computer program product and storage means

• US 8,385,324 B2
• Filed: 03/18/2009
• Issued: 02/26/2013
• Est. Priority Date: 03/20/2008
• Status: Active Grant

• Current Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Original Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Inventors: Achir, Mounir, Lagrange, Pascal
• Primary Examiner(s): Sheikh, Ayaz
• Assistant Examiner(s): HAMPTON, TARELL A
• Application Number:
  US12/406,747
• Publication Number:
  US 20090257386A1
• Time in Patent Office: 1,441 Days
• Field of Search: 370/329, 370/351, 370/310, 370/328, 709/238, 709/241
• US Class Current: 370/351
• CPC Class Codes: H04L 25/14 Channel dividing arrangements , i.e. in which a single bit stream is divided between several baseband channels and reassembled at the receiver
• 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/243 using M+N parallel active paths
• CPC Class Codes: H04W 40/16 based on interference
• CPC Class Codes: H04W 40/20 based on geographic position or location

Abstract

A method for managing allocation of paths for transmission, in packets of symbols, of at least a first data content, each content being transmitted from a source node up to a destination node in a meshed communications network comprising a plurality of nodes, each destination node receiving a plurality of copies of a same packet of symbols of the content transmitted to said destination node by a source node, each copy being received by the destination node via a distinct transmission path directly from the source node or via at least one relay node of the meshed communications network, the packets being encoded with an error correction code enabling decoding by erasure of packets symbols. Such a method comprises the following steps: selecting a set of transmission paths from the source node up to the destination node for the transmission of copies of at least one packet of the first content, for which an estimated first number of erasures of symbols of the at least one packet is smaller than a determined threshold, the first number of erasures being estimated from a piece of information on quality of transmission that is determined and associated with each of the selected transmission paths, the threshold being determined as a function of an erasure correction capability of the error correction code; allocating the selected transmission paths to the transmission of the first content from said source node up to said destination node.

Claims

1. A method for managing an allocation of paths for transmission in packets of symbols of at least a first data content, said first data content being transmitted from a source node up to a destination node in a meshed communications network comprising a plurality of nodes, the destination node receiving a plurality of copies of packets of symbols of the first data content transmitted to said destination node by the source node, each copy being received through a distinct transmission path from said source node directly or through at least one relay node of the meshed communications network, said packets being encoded with an error correction code enabling decoding by erasure of packets symbols, the method comprising the steps of:

selecting a set of transmission paths from said source node up to said destination node for the transmission of copies of at least one packet of said first data content, for which an estimated first number of erasures of the symbols of said at least one packet is smaller than a determined threshold, said first number of erasures being estimated from a piece of information on a quality of transmission that is determined and associated with each of said selected transmission paths, said threshold being determined as a function of an erasure correction capability of said error correction code; and

allocating said selected transmission paths to the transmission of said first data content from said source node up to said destination node.

2. The method according to claim 1, wherein said piece of information on the quality of transmission associated with a selected transmission path is a bit error rate determined for said selected transmission path, and

wherein a number of erasures is estimated from the following formula:

3. The method according to claim 1, wherein the method further comprises, prior to said selecting step, preliminary steps of determining a set of last relay nodes, said last relay nodes being capable of communicating directly with the destination node, and of determining possible transmission paths from said source node up to each of said last relay nodes,

and wherein the selecting step is performed on the basis of the determined possible transmission paths.

4. The method according to claim 3, wherein said step of determining possible transmission paths is performed by selecting a single transmission path for each of the last relay nodes among possible transmission paths for said last relay node.

5. The method according to claim 4, wherein said single transmission path is selected as a function of a piece of information on the quality of transmission associated with said possible transmission paths for said last relay node.

6. The method according to claim 5, wherein said piece of information on the quality of transmission associated with said possible transmission paths corresponds to a piece of information on a bit error rate associated with said possible transmission paths.

7. The method according to claim 6, wherein said piece of information on the quality of transmission associated with said possible transmission paths further corresponds to a piece of information representing the relative position of the last relay nodes in relation to the destination node.

8. The method according to claim 1, wherein the method further comprises a step of determining a set of non-selected transmission paths corresponding to transmission paths present in a reference allocation for the transmission of said first data content from said source node up to said destination node and not selected during the selecting step.

9. The method according to claim 8, wherein the method further comprises a second allocating step of allocating at least one of said non-selected transmissions paths to a requesting destination node for a transmission of a second data content.

10. The method according to claim 9, wherein, prior to said second allocating step, said requesting destination node is a destination node for which a set of transmission paths is allocated, for which an estimated second number of erasures is greater than said predetermined threshold.

11. The method according to claim 1, wherein the method further comprises a step of determining a new retransmission table, representing a distribution and an occupation of bandwidth in the network, performed as a function of said step of allocating said selected transmission paths.

12. The method according to claim 11, wherein the method further comprises steps of:

determining a first number of nodes, which are destination nodes for given data contents, having a set of allocated transmission paths for which an estimated number of erasures is smaller than said predetermined threshold, if said new retransmission table is used; and

comparing the first determined number of nodes with a second number of nodes, which are destination nodes for said given data contents, having a set of allocated transmission paths for which an estimated number of erasures is smaller than said predetermined threshold, if a reference retransmission table is used,

wherein said new retransmission table is adopted if the result of said comparison verifies at least one condition.

13. The method according to claim 12, wherein said condition belongs to the group comprising:

the first number of nodes is greater than the second number of nodes; and

the bandwidth used with the new retransmission table is smaller than the bandwidth used with the reference retransmission table.

14. A non-transitory computer-readable storage medium, storing a set of instructions that may be run by a computer in order to implement a method for managing an allocation of paths for transmission in packets of symbols of at least a first data content, said first data content being transmitted from a source node up to a destination node in a meshed communications network comprising a plurality of nodes, the destination node receiving a plurality of copies of packets of symbols of the first data content transmitted to said destination node by the source node, each copy being received via a distinct transmission path directly from said source node or via at least one relay node of the meshed communications network, said packets being encoded with an error correction code enabling decoding by erasure of packet symbols,

and said method comprising steps for:

selecting a set of transmission paths from said source node up to said destination node for the transmission of copies of at least one packet of said first data content, for which an estimated first number of erasures of the symbols of said at least one packet is smaller than a determined threshold, said first number of erasures being estimated from a piece of information on a quality of transmission that is determined and associated with each of said selected transmission paths, said threshold being determined as a function of an erasure correction capability of said error correction code; and

allocating said selected transmission paths to the transmission of said first content from said source node up to said destination node.

15. A manager device for managing an allocation of paths for transmission in packets of symbols of at least a first data content, said first data content being transmitted from a source node up to a destination node in a meshed communications network comprising a plurality of nodes, said destination node receiving a plurality of copies of packets of symbols of the first data content transmitted to said destination node by said source node, each copy being received via a distinct transmission path directly from said source node or via at least one relay node of the meshed communications network, said packets being encoded with an error correction code enabling decoding by erasure of packet symbols,

wherein the device comprises:

selecting means for selecting a set of transmission paths from said source node up to said destination node for the transmission of copies of at least one packet of said first data content, for which an estimated first number of erasures of the symbols of said at least one packet is smaller than a determined threshold, said first number of erasures being estimated from a piece of information on a quality of transmission that is determined and associated with each of said selected transmission paths, said threshold being determined as a function of an erasure correction capability of said error correction code; and

allocating means for allocating said selected transmission paths to the transmission of said first content from said source node up to said destination node.

16. The manager device according to claim 15, wherein said piece of information on the quality of transmission associated with a selected transmission path is a bit error rate determined for said selected transmission path, and

wherein the device further comprises means for estimating a number of erasures from the following formula:

17. The manager device according to claim 15, wherein the device further comprises means for, prior to the selecting by the selecting means, performing preliminary steps of determining a set of last relay nodes, said last relay nodes being capable of communicating directly with the destination node, and determining possible transmission paths from said source node up to each of said last relay nodes,

and wherein said selecting by said selecting means is performed on the basis of the determined possible transmission paths.

18. The manager device according to claim 17, wherein said determining possible transmission paths is performed by selecting a single transmission path for each last relay node among possible transmission paths for said last relay node.

19. The manager device according to claim 15, wherein the device further comprises second determining means for determining a set of non-selected transmission paths corresponding to transmission paths present in a reference allocation for the transmission of said first data content from said source node up to said destination node and not selected by said selecting means.

20. The manager device according to claim 19, wherein the device further comprises second allocating means for allocating at least one of said non-selected transmissions paths to a requesting destination node for a transmission of a second data content, said requesting destination node being a destination node for which, prior to said allocating by said second allocating means, a set of transmission paths is allocated, for which an estimated second number of erasures is greater than said predetermined threshold.