METHOD AND DEVICE FOR MANAGING ALLOCATION OF DATA TRANSMISSION PATHS IN A MESHED COMMUNICATIONS NETWORK, CORRESPONDING COMPUTER PROGRAM PRODUCT AND STORAGE MEANS

• US 20090257386A1
• Filed: 03/18/2009
• Published: 10/15/2009
• 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
• Granted Patent: US 8,385,324 B2
• Time in Patent Office: Days
• US Class Current: 370/329
• 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. 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 packets of symbols of a content transmitted to said destination node by a 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, wherein it comprises 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 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 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;

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

2. Method according to claim 1, wherein said piece of information on 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. Method according to claims 1, wherein it comprises 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. 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. Method according to claim 4, wherein said single transmission path is selected as a function of a piece of information on quality of transmission associated with said possible transmission paths for said last relay node.

6. Method according to claim 5, wherein said piece of information on 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. Method according to claim 6, wherein said piece of information on 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. Method according to claim 1, wherein it 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 content from said source node up to said destination node and not selected during the selecting step.

9. Method according to claim 8, wherein it further comprises a 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. Method according to claim 9, wherein, prior to said 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. Method according to claim 1, wherein it 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 or steps of allocating transmission paths.

12. Method according to claim 11, wherein it further comprises steps of:

determining a first number of nodes, which are destination nodes for given 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;

comparing the first determined number of nodes with a second number of nodes, which are destination nodes for said given 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;

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

13. Method according to claim 12, wherein said condition belongs to the group consisting of:

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

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

14. Computer-readable storage means, storing a set of instructions that may be run by a computer in order to implement a method for managing allocation 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 packets of symbols of a content transmitted to said destination node by a 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 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 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;

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

15. Manager device 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 packets of symbols of a content transmitted to said destination node by a 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 it comprises:

first 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 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 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;

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

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

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

17. Manager device according to claims 15 or 16, wherein it comprises means for preliminary determining a set of last relay nodes, said last relay nodes being capable of communicating directly with the destination node, and first means for determining possible transmission paths from said source node up to each of said last relay nodes, and wherein said first selecting means are thus activated by said first determining means from the determined possible transmission paths.

18. Manager device according to claim 17, wherein said first determining means are activated by second selecting means, said second selecting means being means for selecting a single transmission path for each last relay node among possible transmission paths for said last relay node.

19. Manager device according to claim 16, wherein it further comprises second 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 content from said source node up to said destination node and not selected by said first selecting means.

20. Manager device according to claim 19, wherein it further comprises second 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 step, a set of transmission paths is allocated, for which an estimated second number of erasures is greater than said predetermined threshold.