JP5587735B2 - Data transmission method and network node - Google Patents

Description

  The present invention relates to a network coding technique, and more particularly to a network coding-based data transmission method and a network node.

  The network encoding technique is a technique for encoding data packets in a network layer. In the technique, it is recognized that a node in a network encodes a received packet, generates a new packet, and then forwards it. Currently, network coding technology is mainly applied to large-scale file distribution, that is, a service that distributes a large amount of information from a source node or server to other nodes in the network, for example, point-to-point (P2P) file transmission. Concentrate on services or P2P streaming services.

は、ガロア体（Ｇａｌｏｉｓ ｆｉｅｌｄ）からランダムに選択した係数であり、それらをそれぞれ元の情報セグメントＳ_１，Ｓ_２，Ｓ_３，…，Ｓ_ｎと乗算して得られる積を加算した後、Ｅ１を得る。即ち、

である。Ｅ２の生成方式は類似している。本例において、ネットワークノードＡはファイル配信のソースノードから新たな情報セグメントＥ１とその対応する係数を受信した後、ネットワーク内の他のノードに新たな情報セグメントをブロードキャストまたはマルチキャストする。ネットワークノードＡのキャッシュに情報セグメントＥ２が既に記憶されているため、ネットワークノードＡは情報セグメントＥ１と情報セグメントＥ２に対して線形符号化を行い、新たな情報セグメントＥ３を得た後、ブロードキャストまたはマルチキャストする。ここで、ネットワークノードＡが情報セグメントＥ３を生成する手順は以下の通りである。ネットワークノードＡはガロア体から係数ｃ１およびｃ２をランダムに選択し、次にそれらをそれぞれＥ１およびＥ２と乗算し、得られる積を加算して、Ｅ３を得る。Ｅ１、Ｅ２が両方とも元の情報セグメントＳ_１，Ｓ_２，Ｓ_３，…，Ｓ_ｎの線形符号であるため、Ｅ３もこのｎ個の元の情報セグメントの線形符号となる。説明すべきものとして、ネットワークノードＡは新たなセグメントＥ３をブロードキャストまたはマルチキャストすると共に、Ｅ３に対応する係数ベクトル

および

もブロードキャストまたはマルチキャストする。ネットワーク内の各ネットワークノードは新たな情報セグメントを受信した後、類似の処理を行う。このようにして、各ネットワークノードは、ｎ個の相関のない情報セグメントおよびその係数を受信しさえすれば、元のファイルを復元することができる。 FIG. 1 shows a simple example of network coding. In large file distribution applications, the file delivered by the source node is too large, but the transmission bandwidth is finite, so before the file is transmitted, the source node first converts the original file into n original information segments. _{(segment) S 1, S 2} , S 3, ..., is divided into _{S n,} then performing a linear coding relative to the n elements of information segments, the new information segments E1, E2, ..., Is generated and transferred over the network with the corresponding coefficients. Accordingly, Ei all source information segment S _{1 is,} S 2, _{S 3, ...,} a linear combination of S _n, its length is the same as the original information segment, the distinction, one to each of Ei Part or all of the original information segment information is attached. In FIG.

Is a coefficient selected at random from the Galois (Galois field), which each source of information segments _{S 1, S 2, S 3} , ..., after adding the product obtained by multiplying the _{S n,} E1 Get. That is,

It is. The generation method of E2 is similar. In this example, the network node A receives the new information segment E1 and its corresponding coefficient from the file distribution source node, and then broadcasts or multicasts the new information segment to other nodes in the network. Since the information segment E2 is already stored in the cache of the network node A, the network node A performs linear encoding on the information segment E1 and the information segment E2, obtains a new information segment E3, and then performs broadcast or multicast. To do. Here, the procedure in which the network node A generates the information segment E3 is as follows. Network node A randomly selects coefficients c1 and c2 from the Galois field, then multiplies them by E1 and E2, respectively, and adds the resulting products to obtain E3. E1, E2 original information segment _S 1 is _{both, S 2, S 3, ...} , because it is a linear code of _{S n,} E3 also a linear code of the n pieces of original information segment. As an illustration, network node A broadcasts or multicasts a new segment E3 and a coefficient vector corresponding to E3.

and

Also broadcast or multicast. Each network node in the network performs a similar process after receiving a new information segment. In this way, each network node can restore the original file as long as it receives n uncorrelated information segments and their coefficients.

  As one skilled in the art understands, if network coding is not employed, an original information segment (eg, the beginning of a file) may have already been held by many network nodes on the network. That is, while having a relatively high degree of popularity, some original information segment (the tail portion of the file) is very rare on the network, that is, has a relatively low degree of popularity. In this case, the network node needs to determine which information segment is received first based on the information segment already received by the network node. For example, to avoid a file download failure due to a network node with scarce resources dynamically leaving, the network node generally downloads the original information segment with a relatively low popularity first. select. However, after employing network coding, all information segments propagated in the network are linear combinations of the original information segments, so all information segments have the same popularity. In this case, the network node does not need to determine which information segment needs to be received first. At the same time, the problem of scarce resources is eliminated. In this way, the impact on other network nodes due to the dynamic joining or leaving of the network node is also reduced.

  In the above method, the network node only decodes to obtain the entire file after waiting for a sufficiently large number of network encoded information segments. Therefore, the above method is not applied to a P2P streaming service that requires viewing while downloading. Therefore, a network encoding method applied to the P2P streaming service is provided.

  In this method, each information segment is further divided into a plurality of information blocks. A seed participating in the P2P streaming service first performs network coding between information blocks in one information segment before data transfer. In this way, a peer can receive a sufficiently large number of network-encoded information blocks and then decode them to obtain information segments. Thus, the method of performing network coding between information blocks in an information segment can support a plurality of seeds transmitting an information segment to one peer at the same time. Thereby, the time for transmitting a certain information segment is shortened, and the viewing waiting time of the peer user is reduced.

ここで、ｑは有限体（ＧＦ）の大きさを表し、ｎは、１つのファイルの分割された情報セグメント数、または、１つの情報セグメントにおける情報ブロック数を表する。例えば、ＧＦの大きさが２５６であって、１つの情報セグメントに１２８個の情報ブロックが含まれる場合、１つの情報セグメントの送信に必要な制御オーバヘッドは、１６．３８４Ｋｂｙｔｅｓに達することになる。 However, in the above two methods, regardless of whether it is an information segment or an information block, the coding coefficient is randomly selected, that is, randomly generated (such a method). Is called random network coding). Also, in order to be able to be decoded at the peer, the generated coding coefficients must be transmitted together with the information segment or information block. Therefore, it has a relatively high control overhead (COH: Control Overhead). Usually, the size of the control overhead in the above method can be calculated by the following Equation 1.
[Formula 1]

Here, q represents the size of a finite field (GF), and n represents the number of information segments divided in one file or the number of information blocks in one information segment. For example, if the size of GF is 256 and one information segment includes 128 information blocks, the control overhead required for transmission of one information segment will reach 16.384 Kbytes.

ここで、ｑは有限体（ＧＦ）の大きさを表し、ｎは、１つのファイルの分割された情報セグメント数、または、１つの情報セグメントにおける情報ブロック数を表する。数式２から分かるように、有限体の大きさが、復号化失敗確率の決定的な要素である。例えば、有限体の大きさを１２８にする場合、復号化失敗確率は１０^−２オーダーとなる。 In addition, since the coding coefficients of random network coding are generated randomly, it is not possible to guarantee 100% that the generated coding coefficients are linearly independent from each other. Thus, even if a peer has already received n information segments or information blocks, it cannot always be correctly decoded. That is, there is a case where decoding fails. The decoding failure probability of the network encoding method can be calculated by the following Equation 2.
[Formula 2]

Here, q represents the size of a finite field (GF), and n represents the number of information segments divided in one file or the number of information blocks in one information segment. As can be seen from Equation 2, the size of the finite field is a decisive factor of the decoding failure probability. For example, when the size of the finite field is set to 128, the decoding failure probability is on the order of 10 ⁻² .

  In order to solve the above technical problem, the present invention provides a data transmission method and a network node. As a result, the control overhead can be reduced, while the decoding failure probability can be reduced.

  In the data transmission method according to the embodiment of the present invention, each of peers and seeds is a network in which any n column vectors (n represents the number of data units divided from transmission target data) are linearly independent from each other. After generating the coding coefficient table and the peer knows all seeds from the tracker, each peer sends a download request including the requested download target data ID and network coding coefficient ID to each seed. Obtains the corresponding column vector from the network coding coefficient table generated by itself according to the coding coefficient ID attached to the received download request, and sets it as a network coding coefficient. Data indicated by the data ID attached to the download request by the network coding coefficient Network encoding is performed on the included data units and the encoded data units are transmitted to the peer, and each peer receives network encoded data units from each seed, and n After receiving the data unit, decryption is performed to obtain download target data.

  Here, generating the network coding coefficient table for each of the peer and the seed includes generating a matrix in which the peer and the seed each have a radix of n or more to form the network coding coefficient table. . Preferably, the matrix radix is 2n. In the present specification, an example of generating a matrix whose radix is n or more, that is, an example of constructing a Vandermonde matrix is provided.

  Each of the peer and the seed generates a network coding coefficient table by generating at least two matrices in which the peer and the seed have different radixes and the radix is not less than n, depending on the size of n. Including selecting one matrix to be a network coding coefficient table.

  Specifically, when the peer and the seed respectively generate four matrices having radixes of 64, 128, 256, and 512, and the number of data units included in the download target data is 32 or less, the radix is 64. Is selected as a network coding coefficient table, and when the number of data units included in the data to be downloaded is greater than 32 and less than or equal to 64, a matrix having a radix of 128 is selected and network coding is performed. When the number of data units included in the download target data is greater than 64 and less than or equal to 128 as a coefficient table, a matrix having a radix of 256 is selected to form a network coding coefficient table, and data included in the download target data Matrix with radix 512 if the number of units is greater than 128 and less than or equal to 256 Select, and network coding coefficient table may involve.

  When the peer knows all seeds from the tracker, the peer sends a seed list request message to the tracker, requesting the tracker for information on all seeds that can provide data, and the tracker requests the seed list request message. , The process returns to the peer a seed ID list including all seed IDs, and the peer knows all seeds providing data by the seed ID list returned from the tracker.

  The network coding coefficient ID includes a coding coefficient modulo value and a coding coefficient index, and each seed is generated from the network coding coefficient table generated by itself according to the coding coefficient ID attached to the received download request. , Acquiring a corresponding column vector and setting it as a network coding coefficient means that each seed is a network coding coefficient table of a column vector selected as a coding coefficient by the following calculation formula i = x × k + y. Where i is the column vector number in the network coding coefficient table, x is the coding coefficient modulo value, y is the coding coefficient index, and k is non-negative. It is an integer.

  Here, although the encoding coefficient modulo value attached to the download request transmitted from the peer to each seed is the same, the encoding coefficient index is not the same.

  The peer receives each network encoded data unit from each seed, and after receiving n data units, the decoding is performed by the peer in the download request sent to each seed. The corresponding column vector is acquired from the network coding coefficient table generated by the network coding coefficient ID generated by itself and used as the coding coefficient of each seed. Then, each seed is coded according to the coding coefficient of each seed. Decoding for n data units from.

  The network coding coefficient ID includes a coding coefficient modulo value and a coding coefficient index, and the network coding coefficient generated by the peer itself by the network coding coefficient ID attached to the download request transmitted to each seed. Obtaining a corresponding column vector from the coefficient table and using it as the encoding coefficient of each seed means that the peer is selected as an encoding coefficient in each seed by the following formula i = x × k + y. Respectively, wherein i is a column vector number in the network coding coefficient table, x and y are coding coefficients modulo values of one seed, and It is a coding coefficient index, and k is a non-negative integer.

  The data is one file, and the data unit is at least one information segment obtained by dividing the file. Alternatively, the data is one of a plurality of information segments obtained by dividing one file, and the data unit is at least one data block included in the data segment.

  The network node provided by the embodiment of the present invention generates a network coding coefficient table in which any n columns (n represents the number of data units divided from transmission target data) are all linearly independent. Network coding coefficient table generating means, seed information obtaining means for obtaining all seeds for providing data from the tracker, and a required download target data ID and network coding coefficient ID for each seed. A download request generation means for generating a download request including at least a download request and transmitting the download request to a corresponding seed, and for each seed, the network encoding coefficient ID in the generated download request is generated by itself. Corresponding column from network coding coefficient table After obtaining the vector data, the coding coefficient generation means for obtaining the network and obtaining the network coding coefficient of each seed, and receiving the network-encoded data unit from each seed, and receiving the n data units, Data receiving / decoding means for performing decoding using network coding coefficients to obtain download target data.

  Here, the network coding coefficient table generating means generates a network coding coefficient matrix generation module that generates at least one matrix having a different radix and having a radix of n or more, and the size of n A network coding coefficient table selection module that selects one of at least one matrix to be a network coding coefficient table.

  The other network nodes provided by the embodiments of the present invention include a network coding coefficient table in which any n columns (n represents the number of data units divided from transmission target data) are all linearly independent. Network coding coefficient table generating means for generating a download request receiving means for receiving a download request from a peer, and a network coding coefficient generated by the network coding coefficient ID attached to the received download request The corresponding column vector is obtained from the table and designated as a coding coefficient generating means to be used as a network coding coefficient, and the data ID attached to the download request stored in itself by the obtained network coding coefficient. Network coding for data units included in the encoded data Go and comprises a network coding means for transmitting the encoded data units to a peer, a.

  Here, the network coding coefficient table generating means generates a network coding coefficient matrix generation module that generates at least one matrix having a different radix and having a radix of n or more, and the size of n A network coding coefficient table selection module that selects one of at least one matrix to be a network coding coefficient table.

  In the data transmission process, each seed does not select a coding coefficient randomly, but selects a coding coefficient by a coding coefficient modulo value and a coding coefficient index attached to a download request transmitted from a peer. Thus, each seed does not need to report the coding coefficient to the peer when sending the network encoded data unit to the peer. As a result, the control overhead in the data transmission process can be greatly reduced.

  In addition, since any n column vectors in the network coding coefficient table generated at each network node are all linearly independent, the network encoded data unit is also linearly independent. In this way, the peer can successfully decode and obtain the data to be transmitted as long as it correctly receives n data units, no matter what seed it receives.

It is a figure which shows the simple example of network encoding. 3 is a flowchart of a network coding based data transmission method according to an embodiment of the present invention; It is a figure which shows that a network coding coefficient table and each seed select a network coding coefficient. It is a figure which shows the internal structure of the network node which is a peer. It is a figure which shows the internal structure of the network node which is a seed. When adopting the method according to the embodiment of the present invention and the conventional random network coding method, the control overhead is a curve that varies with the number of information blocks included in each information segment. When the method according to the embodiment of the present invention and the conventional random network encoding method are employed, the control overhead is a curve that varies with the number of information segments included in the file to be downloaded.

  In order to solve the above problems, an embodiment of the present invention provides a network coding based data transmission method. As shown in FIG. 2, the method mainly includes the following steps.

  In step 101, each network node in the network generates a network coding coefficient table (Network Coding Table).

  Here, each of the above nodes includes a seed for providing data and a peer that requires data download.

  The network coding coefficient table limits the range of network coding coefficients. Each node selects at least one column vector in the network coding coefficient table as a coding coefficient of transmission target data. As a matter of explanation, the network coding coefficient table generated at each network node needs to satisfy the following conditions so that the network coded data transmitted from different network nodes does not become redundant. That is, arbitrary n column vectors in the network coding coefficient table are linearly independent from each other, where n is the number of data units divided from the transmission target data, that is, network coding needs to be performed. It represents the number of a certain data unit, for example, the number of information segments obtained by dividing a file to be downloaded in the P2P file transmission service, or the number of information blocks included in each information segment in the P2P streaming service.

  When the above method is applied to a P2P application, each network node (including a seed for providing data and a peer that requires data download) simultaneously installs the network when installing the P2P application software. An encoding coefficient table can be generated.

  In step 102, the peer knows all seeds from the tracker, and then transmits a download request to each seed. The download request includes at least the requested download target data ID and the network coding coefficient ID.

  Specifically, in this step, the peer first requests the information of all seeds that can provide data by sending a seed list request message to the tracker, and the tracker receives the seed list request message. Thereafter, a seed ID list including IDs of all seeds is returned to the peer, and the peer knows all seeds providing data by the seed ID list returned from the tracker.

  In this step, the download target data may be one file or one of a plurality of information segments obtained by dividing one file.

  In this step, the network coding coefficient ID included in the download request indicates the position in the network coding coefficient table of the coding coefficient used when one seed performs network coding. Preferably, the network coding coefficient ID may include a coding coefficient modulo value and a coding coefficient index. In this case, the column vector number i selected as an encoding coefficient in each seed can be calculated by the following calculation formula i = x × k + y. Here, x is a coding coefficient modulo value, y is a coding coefficient index, and k is a non-negative integer (including 0 and a positive integer). In order to ensure that the coding coefficient selected for each seed is different, preferably the coding coefficient modulo value attached to the download request sent from the peer to each seed is the same while the coding coefficient index Are not the same.

  In step 103, each seed obtains a corresponding column vector from the network coding coefficient table generated by itself according to the coding coefficient ID attached to the received download request, and sets it as a network coding coefficient.

  As described above, in this step, when the network coding coefficient ID includes a coding coefficient modulo value and a coding coefficient index, each seed is calculated according to the following formula i = xx × k + y according to its own network code. A quantization coefficient vector is calculated. Here, x is a coding coefficient modulo value, y is a coding coefficient index, and k is a non-negative integer (including 0 and a positive integer).

  In step 104, each seed is encoded by performing network encoding on the data unit included in the data indicated by the data ID attached to the download request according to the acquired network encoding coefficient. Send data unit to peer.

  In this step, when the data is one file, the data unit is at least one information segment obtained by dividing the file. When the data is one of a plurality of information segments obtained by dividing one file, the data unit is at least one data block included in the data segment.

  In step 105, the peer receives network encoded data units from each seed, receives n data units, and performs decoding to obtain download target data.

  Also in this step, the peer first obtains a corresponding column vector from the network coding coefficient table generated by itself by the network coding coefficient ID attached to the download request transmitted to each seed, The data to be downloaded is obtained by performing decoding on the data unit from each seed using the coding coefficient of each seed after the coding coefficient of the seed. Specifically, when the network coding coefficient ID includes a coding coefficient modulo value and a coding coefficient index, a peer is selected as a coding coefficient at each seed according to the following calculation formula i = x × k + y. The numbers of the column vectors in the network coding coefficient table are respectively calculated. Here, i is the column vector number in the network coding coefficient table, x and y are the coding coefficient modulo value and coding coefficient index of one seed, respectively, and k is a non-negative integer.

  As can be seen, the coding coefficients used in the above method are neither randomly generated nor fixed in advance. Therefore, the network coding method used in the above method may be called semi-static network coding.

  In the above data transmission process, each seed does not select a coding coefficient at random, but selects a coding coefficient according to a coding coefficient modulo value and a coding coefficient index attached to a download request transmitted from a peer. Thus, each seed does not need to report the coding coefficients to the peer when transmitting a network encoded data unit (information segment or information block) to the peer. As a result, the control overhead in the data transmission process can be greatly reduced.

  Also, since any n column vectors in the network coding coefficient table generated at each network node are all linearly independent, the network-encoded data unit (information segment or information block) is also linearly independent. In this way, a peer can successfully decode and transmit data to be transmitted as long as it correctly receives n data units (information segments or information blocks), no matter which seed it receives data from. Can be obtained.

  Hereinafter, a method for generating a network coding coefficient table will be described in detail with reference to a specific example.

As described above, the network coding coefficient table needs to satisfy the following condition so that the network coded data transmitted from different seeds does not become redundant. That is, any n column vectors in the network coding coefficient table are all linearly independent, where n is the number of data units included in the transmission target data, for example, information segments included in one file Or the number of information blocks included in one information segment. Usually, the number of information blocks included in one information segment is between 32 and 256. Therefore, it may be assumed that 32 ≦ n ≦ 256. The network coding coefficient table may adopt the form of matrix A shown in Equation 3 below.
[Formula 3]

  As described above, if any n columns in the matrix A are linearly independent, that is, if the cardinality of the matrix A is n, the data obtained by using the column vector in the matrix A as an encoding coefficient Redundant information is not included between units (information segments or information blocks). In this case, even if the peer receives data from any seed, as long as it correctly receives n data units, it can always successfully decode and obtain the original data. That is, as long as it is ensured that the base of the matrix A is n or more, the decoding failure probability can be greatly reduced. Preferably, the radix of A should be set to be larger than n in consideration of factors such as the dynamic separation of network nodes and link errors. Preferably, the radix of A may be set to 2n. For example, when n is 256, the radix of A may be set to 512.

  As can be seen from the mathematical analysis, a sufficient condition to ensure that the radix of A is n is that the size of the finite field (GF) is n. In the present specification, an example of constructing the matrix A whose radix is n is provided.

The Vandermonde matrix is a matrix having typical characteristics, and can be expressed by the following Equation 4.
[Formula 4]

を満足する。つまり、α_ｉ≠α_ｊさえあれば、有限体（ＧＦ）の大きさがｎである場合、ヴァンデルモンド行列から構成されたＡは、基数がｎであることを満足でき、即ち、任意のｎ列の線形独立を満足できる。 The matrix has the following properties:

Satisfied. That is, as long as α _i ≠ α _j, if the size of the finite field (GF) is n, A constructed from the Vandermonde matrix can satisfy that the radix is n, that is, any n Satisfy the linear independence of the columns.

  In actual application, after determining the size of the finite field, that is, the radix of the matrix A, according to the number of data units included in the download target data, the condition that any n column vectors are linearly independent from each other is set. A satisfied matrix A is constructed from the above Vandermonde matrix. Specifically, each network node can generate a matrix having a radix of n or more to form the network coding coefficient table.

  Examples of the present invention will be described below in detail with examples. FIG. 3 is a diagram illustrating a network coding coefficient table and each seed selecting a network coding coefficient.

  First, each network seed in the network generates a network coding coefficient table as shown in FIG. When downloading certain data, Peer first selects an appropriate seed from the SeedID list fed back from the tracker. Suitable seeds include Seed1, Seed2, Seed3, and Seed4. Next, Peer selects a coding coefficient modulo value Mod and a coding coefficient index Index for each Seed. For example, the Mod selected for Seed1 is 8, the Index is 1, the Mod selected for Seed2 is 8, the Index is 2, and the Mod selected for Seed3. Is 8, the Index is 3, the Mod selected for Seed 4 is 8, and the Index is 4. Peer then sends the selected coding coefficient modulo value and coding coefficient index to the corresponding seed. After that, Seed1, Seed2, Seed3, and Seed4 select the encoding coefficient based on these two pieces of information, and then code the information segment of one file or the information block included in one information segment. Can be made. For example, Seed 1 selects a column vector whose (number MOD 8) is 1 in the network coding coefficient table as a coding coefficient (for example, the first, ninth, 17... Columns). Seed 2 selects a column vector having (number MOD 8) of 2 in the network coding coefficient table as a coding coefficient (for example, the second, 10, 18,... Columns). Seed 3 selects a column vector having (number MOD 8) of 3 in the network coding coefficient table and sets it as a coding coefficient (for example, the third, eleventh,... Column). Seed 4 selects a column vector having (number MOD 8) of 4 in the network coding coefficient table as a coding coefficient (for example, columns 4, 12, 20,...). When the coding coefficient is selected according to the above rule, it can be ensured that each Seed does not use the same coding coefficient and that the coding coefficient used in each Seed is linearly independent.

  In order to further reduce the amount of computation of the network node and further optimize the performance of the above method, the radix of the network coding coefficient matrix, that is, the finite field (GF), depends on the number of data units included in the download target data. In addition, the size of the generated network coding coefficient table may be dynamically adjusted. For example, when the data unit included in the download target data is relatively small, a matrix having a relatively small radix may be generated and used as the network coding coefficient table. In an actual application, the network node generates in advance a plurality of matrices having different radixes and the radix is n or more to obtain a candidate network coding coefficient table, and the number of data units included in the download target data Thus, one appropriate network coding coefficient table may be selected from all candidate network coding coefficient tables. Then, the coding coefficient is obtained from the selected network coding coefficient table. For example, each node in the network generates four matrices with bases 64, 128, 256, and 512, respectively. The only difference is that the finite field sizes of the four matrices are GF (64), GF (128), GF (256), and GF (512), respectively. After receiving a download request from a peer, if the number of data units included in the download target data is 32 or less, the seed selects a matrix having a radix of 64 as a network coding coefficient table, and download data When the number of data units included in the data is greater than 32 and less than or equal to 64, a matrix having a radix of 128 is selected as the network coding coefficient table, and the number of data units included in the download target data is greater than 64 and If the number is 128 or less, a matrix whose base is 256 is selected as a network coding coefficient table, and if the number of data units included in the download target data is greater than 128 and 256 or less, the matrix whose base is 512 To select a network coding coefficient table. As can be understood by those skilled in the art, in the above method, when the number of data units included in the download target data is relatively small, the calculation amount of the network node can be further reduced. Thereby, the purpose of optimizing the performance of the network node can be achieved.

  In addition to the above method, the present invention also provides an internal configuration of a network node that is a peer and a network node that is a seed.

  Here, FIG. 4 shows an internal configuration of a network node as a peer. As shown in FIG. 4, the network node mainly has a network coding coefficient table in which any n columns (n represents the number of data units divided from transmission target data) are linearly independent. Transmission target network coding coefficient table generating means to be created, seed information obtaining means for obtaining all seeds providing data from the tracker, and required download target data ID and network coding for each seed A download target download request generating means for generating a download request including at least a coefficient ID and transmitting the download request to a corresponding seed, and for each of the seeds, according to the network encoding coefficient ID in the generated download request Network coding coefficient table generated by itself From which the corresponding column vector is obtained, and the coding coefficient generating means to obtain the network coding coefficient of each seed, and the network encoded data unit is received from each seed, and n data units are received. And data receiving / decoding means for performing decoding by using the network coding coefficient of each seed to obtain download target data.

  Further, the network coding coefficient table generation means includes a network coding coefficient matrix generation module that generates at least one matrix having a different radix and a radix of n or more, and at least generated by the size of n. And a network coding coefficient table selection module that selects one from one matrix to be a network coding coefficient table.

  FIG. 5 shows an internal configuration of a network node as a seed. As shown in FIG. 5, the network node mainly has a network coding coefficient table in which any n columns (n represents the number of data units divided from transmission target data) are linearly independent. A network coding coefficient table generated by the network coding coefficient table generating means to be created, a download request receiving means for receiving a download request from a peer, and a network coding coefficient ID attached to the received download request From the coding coefficient generation means that obtains a corresponding column vector as a network coding coefficient and the acquired network coding coefficient, it is indicated by the data ID attached to the download request stored in itself. Network coding is applied to the data unit included in Comprising a network coding section for transmitted data units to a peer, a.

  Further, the network coding coefficient table generation means includes a network coding coefficient matrix generation module that generates at least one matrix having a different radix and a radix of n or more, and at least generated by the size of n. A network coding coefficient table selection module that selects one from one matrix to be a network coding coefficient table may be included.

  Hereinafter, the method according to the present invention and the conventional random network coding method are compared by simulation. Assume that the number of network nodes in the network is 250, the file to be downloaded includes 50 to 200 information segments, and each information segment includes 32 to 256 information blocks. When viewing a video file using a P2P streaming service, each network node needs to buffer 20 information segments. The tracker allows access of at most 8 peers, each network node allows access of at most 4 peers, and each network node allows seeding of at most 4 peers. In the above case, FIG. 6 is a curve in which the control overhead varies with the number of information blocks included in each information segment when the method according to the embodiment of the present invention and the conventional random network coding method are employed. FIG. 7 is a curve in which the control overhead varies with the number of information segments included in the file to be downloaded when the method according to the embodiment of the present invention and the conventional random network encoding method are employed. In FIGS. 6 and 7, the square curve is a change curve of control overhead when the method according to the embodiment of the present invention is adopted, but the circle curve adopts the conventional random network coding. It is a change curve of the control overhead at the time. As can be seen from the above curve, the method according to the embodiment of the present invention significantly reduces the control overhead compared to the conventional random network coding method. For example, according to the random network coding method, the overhead of the control packet is around 10%, but according to the method according to the embodiment of the present invention, the overhead of the control packet is less than 0.1%.

  In addition, as described above, since any n columns of the network coding coefficient table generated in the embodiment of the present invention are all linearly independent, a peer can receive n data from any seed. As long as the data unit is received correctly, the original data can be obtained without fail. This greatly reduces the decoding failure probability.

  The above are only preferred embodiments of the present invention and do not limit the protection scope of the present invention. Various modifications, equivalent replacements, improvements and the like made within the spirit and principle of the present invention should all be included in the protection scope of the present invention.

Claims (16)

A data transmission method comprising:
Each of the peer and the seed generates a network coding coefficient table in which arbitrary n number of column vectors (where n represents the number of data units divided from transmission target data) are linearly independent from each other,
After knowing all seeds from the tracker, the peer sends a download request including the requested download target data ID and network coding coefficient ID to each seed.
Each seed obtains a corresponding column vector from the network coding coefficient table generated by itself according to the coding coefficient ID attached to the received download request, and makes it a network coding coefficient.
Each seed performs network encoding on the data unit included in the data indicated by the data ID attached to the download request by the acquired network encoding coefficient, and the encoded data unit is peered. To
Each peer receives network encoded data units from each seed, receives n data units, and performs decoding to obtain download target data.
A method comprising: The peer and seed each generate a network coding coefficient table,
Each of the peer and the seed generates a matrix whose radix is n or more, and forms the network coding coefficient table.
The method of claim 1, comprising:   The method of claim 2, wherein the matrix has a radix of 2n. The peer and seed each generate a network coding coefficient table,
The peer and the seed generate at least two matrices having different radixes and the radix is not less than n, and select one matrix according to the size of n to form a network coding coefficient table;
The method of claim 1, comprising: The peer and the seed generate at least two matrices having different radixes and the radix is not less than n, and select one matrix according to the size of n to form a network coding coefficient table. Is
The peer and seed generate four matrices with radix 64, 128, 256, and 512 respectively;
When the number of data units included in the download target data is 32 or less, a matrix having a radix of 64 is selected as a network coding coefficient table,
When the number of data units included in the download target data is greater than 32 and less than or equal to 64, a matrix having a radix of 128 is selected as a network coding coefficient table,
When the number of data units included in the download target data is greater than 64 and less than or equal to 128, a matrix having a radix of 256 is selected as a network coding coefficient table,
When the number of data units included in the download target data is greater than 128 and less than or equal to 256, a matrix having a radix of 512 is selected to form a network coding coefficient table.
The method according to claim 4, further comprising: The peer knows all seeds from the tracker
The peer requests the tracker for information on all seeds that can provide data by sending a seedlist request message to the tracker,
After the tracker receives the seed list request message, it returns a seed ID list including all seed IDs to the peer,
Peer knows all seeds that provide data from the list of seed IDs returned from the tracker.
The method of claim 1, comprising: The network coding coefficient ID includes a coding coefficient modulo value and a coding coefficient index;
Each seed obtains a corresponding column vector from the network coding coefficient table generated by itself according to the coding coefficient ID attached to the received download request, and makes it a network coding coefficient.
Each seed calculates a number in a network coding coefficient table of a column vector selected as a coding coefficient by the following formula i = xx × k + y:
Here, i is a column vector number in the network coding coefficient table, x is a coding coefficient modulo value, y is a coding coefficient index, and k is a non-negative integer.
The method according to claim 1. The coding coefficient modulo value attached to the download request sent from the peer to each seed is the same, but the coding coefficient index is not the same,
The method according to claim 7. The peer receives network encoded data units from each seed, respectively, receives n data units, and then performs decoding,
The peer obtains a corresponding column vector from the network coding coefficient table generated by itself by using the network coding coefficient ID attached to the download request transmitted to each seed, and uses it as the coding coefficient of each seed. Decoding for each of n data units from each seed, with the coding coefficient of each seed,
The method of claim 1, comprising: The network coding coefficient ID includes a coding coefficient modulo value and a coding coefficient index;
The peer obtains a corresponding column vector from the network coding coefficient table generated by itself by using the network coding coefficient ID attached to the download request transmitted to each seed, and sets it as the coding coefficient of each seed. That is
Each of the peers calculates a number in the network coding coefficient table of a column vector selected as a coding coefficient in each seed by the following formula i = xx × k + y:
Here, i is a column vector number in the network coding coefficient table, x and y are one seed coding coefficient modulo value and coding coefficient index, and k is a non-negative integer.
The method of claim 9.   11. The data according to claim 1, wherein the data is one file, and the data unit is at least one information segment obtained by dividing the file. Method. The data is one of a plurality of information segments obtained by dividing one file, and the data unit is at least one data block included in the data segment.
11. The method according to any one of claims 1 to 10, wherein: A network node,
Network coding coefficient table generating means for generating a network coding coefficient table in which any n columns (n represents the number of data units divided from transmission target data) are linearly independent;
Seed information acquisition means for acquiring all seeds providing data from the tracker;
Download request generating means for generating a download request including at least a download target data ID and a network coding coefficient ID required for each seed, and transmitting the download request to a corresponding seed;
For each seed, a code that obtains a corresponding column vector from the network coding coefficient table generated by itself using the network coding coefficient ID in the generated download request, and uses it as a network coding coefficient for each seed A coefficient generation means;
Data reception / decoding that receives network-encoded data units from each seed, receives n data units, and then performs decoding using the network encoding coefficient of each seed to obtain download target data Means,
A network node characterized by including: The network coding coefficient table generating means includes
A network coding coefficient matrix generation module for generating at least one matrix having a different radix and having a radix greater than or equal to n;
a network coding coefficient table selection module which selects one of the generated at least one matrix according to the size of n and sets it as a network coding coefficient table;
The network node according to claim 13, comprising: A network node,
Network coding coefficient table generating means for generating a network coding coefficient table in which any n columns (n represents the number of data units divided from transmission target data) are linearly independent;
Download request receiving means for receiving a download request from a peer;
Coding coefficient generation means for acquiring a corresponding column vector from the network coding coefficient table generated by itself using the network coding coefficient ID attached to the received download request, and making it a network coding coefficient;
A data unit encoded by performing network encoding on the data unit included in the data indicated by the data ID attached to the download request stored in itself by the acquired network encoding coefficient Network encoding means for transmitting to the peer;
A network node characterized by including: The network coding coefficient table generating means includes
A network coding coefficient matrix generation module for generating at least one matrix having a different radix and having a radix greater than or equal to n;
a network coding coefficient table selection module which selects one of the generated at least one matrix according to the size of n and sets it as a network coding coefficient table;
The network node according to claim 15, comprising:

Images