Data working relay method and device, network system device, data working relay processing program and recording medium with its processing program recorded

[0001] The present invention relates to a data processing relay method, an apparatus and a network system apparatus, a data processing relay processing program, and a recording medium on which the processing program is recorded. In the process of relaying data, a data processing relay method for adding additional data such as advertisement data to the content data or converting the data format of the content data, and a data processing relay device directly used for the implementation thereof. And the data processing relay network system apparatus, the data processing relay processing program for carrying out the data processing relay method, and the recording medium on which the data processing relay processing program is recorded.

Conventionally, when stream data with an advertisement is delivered from a server to a client via a multicast tree-type network, the required advertisement data is added to the stream data to be delivered on the server. A method of preparing a pre-added data and distributing it to each client was generally adopted.

[0003] When the above method is adopted, by adding the advertisement data suitable for the taste of each client (user) to the stream data, a more effective advertisement is presented to each client. On the other hand, it is possible to prepare a large amount of stream data with advertisements according to the type of preference of each existing client, which increases the load on the server and reduces its scalability. Problems such as were pointed out.

[0004] In recent years, various methods have been proposed in order to deal with such a problem. For example, in Japanese Patent Application Laid-Open No. 2000-29712, when a game program is downloaded from a server, it is installed in a game center or the like in each place. A method of selectively adding an advertisement is disclosed in the terminal station.

[0005] Further, in Japanese Patent Application Laid-Open No. 11-134353 by the applicant of the present application, an advertisement addition server installed in the network acquires stream data from the server in response to a data acquisition request from the client, and the stream data is obtained. Disclosed is a method of returning the data obtained by statistically adding the advertisement data suitable for the client's taste to the client who requested the acquisition.

[0006] [Problem to be Solved by the Invention] However, in the above-described method of selectively adding an advertisement in a terminal station, when the load of the advertisement addition process is to be distributed, each terminal station existing there is to distribute the load. There was a problem that it had to be done every time, and it could not be dealt with when the number of clients increased or decreased dynamically.

[0007] Further, in the method of obtaining the required stream data with advertisement using the advertisement addition server, the client needs to make a data acquisition request to the proxy server instead of the server, so that the load is concentrated on the advertisement addition server. There was a problem.

[0008] Here, the main object to be solved by the present invention is as follows.

[0009] That is, the first object of the present invention is a data processing relay method and device and a network system device capable of efficiently adding additional data such as an advertisement suitable for each client's taste to the content data, and an apparatus and a network system apparatus. It is intended to provide a data processing relay processing program and a recording medium on which the processing program is recorded.

[0010] A second object of the present invention is a data processing relay method, an apparatus, and a network system apparatus capable of converting the data format of the content data into a format receivable by each client in the process of distributing the content data. , And a data processing relay processing program and a recording medium on which the processing program is recorded.

[0011] A third object of the present invention is a data processing relay capable of delivering required content data in consideration of the load state of each relay node itself and the load state of the communication link of each relay node. It is intended to provide a method, an apparatus, a network system apparatus, a data processing relay processing program, and a recording medium on which the processing program is recorded.

[0012] Other objects of the present invention will be self-evident from the description, drawings, and in particular, the description of each claim in the claims.

[Means for Solving the Problems] In the method of the present invention, in order to solve the above problems, content data is transferred from adjacent nodes on the root side of each of a plurality of relay nodes constituting the network. At times, various classifications of additional data to be transferred to each leaf side adjacent node are selected, and if additional data is not added to the transferred content data, it is registered corresponding to the selected various classifications. If the additional data is transferred to each leaf-side adjacent node, and the additional data has already been added to the transferred content data, and the additional data is different from that of the selected various categories, The additional data is replaced with the additional data registered corresponding to the various classifications and transferred to each leaf side adjacent node, and the additional data is already added to the transferred content data and the additional data is added. When the data is the same as that of the selected various classifications, a characteristic configuration method is adopted in which the content data is transferred to each leaf-side adjacent node as it is.

On the other hand, in the apparatus of the present invention, in order to solve the same problem, the receiving means for receiving the content data transferred from the root side adjacent node and the data addition form of the content data received by the receiving means are used. Correspondingly, various classifications of additional data to be transferred to each leaf side adjacent node are selected by referring to the additional instruction table, and additional data stored in the additional data storage means corresponding to the selected various classifications are selected. The data addition / replacement means for reading and adding / replacing the additional data related to the reading to the content data, and the content data to which the additional data has been added / replaced by the data addition / replacement means are connected to each leaf side adjacent node. A characteristic configuration means of providing a transmission means for transmitting toward the data is taken.

[0015] Further, in the network system apparatus of the present invention, in order to solve the same problem, the above-mentioned book is applied to a plurality of relay nodes constituting a network for distributing content data from a single server to one or more clients. We will take a characteristic configuration means of allocating each of the invention devices to form a network.

[0016] On the other hand, in the program of the present invention, in order to solve the same problem, when the content data is transferred from the root side adjacent node in each of the plurality of relay nodes constituting the network, each leaf side adjacent. A processing step for selecting various classifications of pre-classified additional data for each node, and additional data corresponding to the selected various classifications when the additional data is not added to the transferred content data. When the processing step of transferring to the adjacent node on the leaf side and the additional data have already been added to the transferred content data and the additional data is different from that of the selected various categories, the additional data is added. , The processing step of replacing the additional data corresponding to the various classifications and transferring to each leaf side adjacent node, and the additional data has already been added to the transferred content data, and the additional data has been selected. In the same case as those of various classifications, a characteristic configuration procedure is taken in which the processing step of transferring the content data as it is to each leaf-side adjacent node is sequentially performed.

[0017] Further, in the recording medium of the present invention, in order to solve the same problem, in order to add predetermined additional data to the content data in the process of relaying the content data by a plurality of relay nodes constituting the computer, respectively. The characteristic constitutional procedure of actually recording the processing procedure by the above-mentioned program of the present invention is taken.

[0018] Further, more specifically, in order to solve the problem, the present invention achieves the above object by adopting the novel characteristic constitutional methods, means, procedures or procedures listed below. Will be done.

[0019] That is, the first feature of the method of the present invention is a multicast tree including a server that distributes content data, a client that receives the content data, and a relay node that connects the server and the existing client. It is a data processing relay method for adding predetermined additional data to the content data in the downstream relay process of the content data by the relay node, which is applied to the network of the form, and is applied to each of the relay nodes. , The additional data to be delivered to the client corresponding to the downstream is registered in advance according to various classifications required by the client according to the preference, and the preference and the addition of the additional data of the client. Based on the preference cost information showing the correlation with the additional cost of the data, the additional instruction table in which the various classifications of the additional data to be transferred to the existing leaf-side adjacent node are classified and defined for each leaf-side adjacent node is prepared in advance. In the relay node, when the content data is transferred from the root side adjacent node, various classifications of the additional data to be transferred to the leaf side adjacent node are selected based on the additional instruction table. If the additional data is not added to the transferred content data, the additional data registered corresponding to the selected various classifications is transferred to the leaf-side adjacent node and transferred. If the additional data has already been added to the content data that has been created and the additional data is different from that of the selected various classifications, the additional data corresponds to the various classifications. The additional data is replaced with the registered additional data and transferred to the leaf-side adjacent node, and the additional data has already been added to the transferred content data, and the additional data is selected for the various classifications. In the case of the same as that of the above, the configuration of the data processing relay method characterized in that the content data is transferred to the leaf side adjacent node as it is is adopted.

[0020] The second feature of the method of the present invention is that the selection of various classifications of the additional data in the relay node in the first feature of the method of the present invention is performed based on the preference cost information. The configuration of the data processing relay method according to claim 1, wherein the data processing is performed based on information indicating a load state on the downstream side of the relay node itself.

[0021] The third feature of the method of the present invention is that the selection of various classifications of the additional data in the relay node in the first or second feature of the method of the present invention is performed based on the preference cost information. In addition, the configuration of the data processing relay method according to claim 1 or 2, wherein the data processing relay method is performed based on information indicating a load state on the downstream side of a communication link between the relay nodes.

[0022] The fourth feature of the method of the present invention is that the setting of the additional instruction table in the relay node in the first, second or third feature of the method of the present invention is transferred from the relay node located downstream thereof. A series of processes in which a predetermined operation is intensively performed as a vector on the incoming preference cost information and the new preference cost information obtained by the operation is transferred to a relay node located upstream of the operation is performed from the client as a base point. However, the configuration of the data processing relay method according to claim 1, 2 or 3, wherein the data processing is performed step by step from the downstream side to the upstream side of the network.

[0023] A fifth feature of the method of the present invention is a multicast tree-type network including a server that distributes content data, a client that receives the content data, and a relay node that connects the server and an existing client. It is a data processing relay method for converting the data format of the content data in the downstream relay process of the content data by the relay node, and is distributed from the server to each of the relay nodes. The data format conversion means for converting the data format of the content data into a format receivable by the client is determined in advance according to various classifications of the data format conversion means required by the client according to the preference. The data format to be adopted in the existing leaf-side adjacent node based on the preference cost information that is registered and represents the correlation between the preference of the client in the data format and the data format conversion cost of the content data. A conversion instruction table in which various classifications of the conversion means are classified and defined for each leaf-side adjacent node is set in advance, and when the relay node receives the transfer of the content data from the root-side adjacent node, the leaf-side Various classifications of the data format conversion means to be adopted in the adjacent node are selected based on the conversion instruction table, and the data format conversion means for obtaining the data format of the transferred content data is selected. If it is different from that of various classifications, the content data is converted by the other data format conversion means registered corresponding to the various classifications, transferred to the leaf side adjacent node, and transferred. When the data format conversion means for obtaining the data format of the content data is the same as that of the selected various classifications, the content data is transferred as it is to the leaf side adjacent node. The configuration of the data processing relay method is adopted.

[0024] The sixth feature of the method of the present invention is that the selection of various classifications of the data format conversion means in the relay node in the fifth feature of the method of the present invention is performed based on the preference cost information. The configuration of the data processing relay method according to claim 5, wherein the data processing / relay method is performed based on the information indicating the downstream load state of the relay node itself.

[0025] The seventh feature of the method of the present invention is that the selection of various classifications of the data format conversion means in the relay node in the fifth or sixth feature of the method of the present invention is performed based on the preference cost information. In addition, the configuration of the data processing relay method according to claim 5 or 6, wherein the data processing relay method is performed based on information indicating a load state on the downstream side of the communication link between the relay nodes.

[0026] The eighth feature of the method of the present invention is that the setting of the conversion instruction table in the relay node in the fifth, sixth or seventh feature of the method of the present invention is transferred from the relay node located downstream thereof. A series of processes in which a predetermined operation is intensively performed as a vector on the incoming preference cost information and the new preference cost information obtained by the operation is transferred to a relay node located upstream of the operation is performed from the client as a base point. However, the configuration of the data processing relay method according to claim 5, 6 or 7, wherein the data processing is performed step by step from the downstream side to the upstream side of the network.

[0027] On the other hand, the first feature of the apparatus of the present invention is to configure each relay node applied to a multicast tree-type network for distributing content data from the server to the client, and relay the content data downstream of the relay node. In the process, it is a data processing relay device for adding predetermined additional data to the content data, and the additional data to be distributed to an existing client is classified into various types requested by the client according to the preference. Based on the additional data storage means that is stored in advance and the preference cost information that represents the correlation between the preference of the additional data of the client and the additional cost of the additional data, to the existing leaf-side adjacent node. An additional instruction table in which various classifications of the additional data to be transferred are classified and defined in advance for each leaf-side adjacent node, a receiving means for receiving the content data transferred from the root-side adjacent node, and this reception. According to the data addition form of the content data received by the means, various classifications of the additional data to be transferred to the leaf side adjacent node are selected with reference to the addition instruction table, and the selected various classifications are selected. Data addition / replacement means for reading the additional data stored in the additional data storage means and adding / replacing the additional data related to the reading to the content data, and the data addition / replacement means. The present invention is to adopt a configuration of a data processing relay device, which comprises a transmission means for transmitting the content data to which the additional data has been added or replaced to the leaf side adjacent node.

[0028] A second feature of the apparatus of the present invention is that the receiving means in the first feature of the apparatus of the present invention has a function of receiving preference cost information transferred from an adjacent node on the leaf side, and the addition is provided. The instruction table includes a preference cost information extracting means for extracting the preference cost information received by the receiving means, a preference cost information table for holding the preference cost information extracted by the preference cost information extracting means, and the preference. The content can be updated based on the preference cost information aggregation means for obtaining new preference cost information by intensively performing a predetermined operation on the preference cost information held in the cost information table as a vector. The data processing according to claim 9, wherein the transmission means has a function of transmitting the new preference cost information obtained by the preference cost information aggregation means toward the route-side adjacent node. The configuration of the relay device is adopted.

[0029] The third feature of the apparatus of the present invention is to configure each relay node applied to a multicast tree-type network for distributing content data from the server to the client, and in the process of relaying the content data downstream of the relay node. , A data processing relay device for converting the data format of the content data, and data format conversion for converting the data format of the content data to be delivered to an existing client into a format receivable by the client. A data format conversion means storage means that stores the means in advance according to various classifications of the data format conversion means required by the client according to the preference, and the preference of the client in the data format and the content data. Based on the preference cost information showing the correlation with the data format conversion cost, various classifications of the data format conversion means to be adopted in the existing leaf side adjacent node are defined in advance for each leaf side adjacent node. The conversion instruction table, the receiving means for receiving the content data transferred from the root side adjacent node, and the data format of the content data received by the receiving means should be adopted in the leaf side adjacent node. Various classifications of the data format conversion means are selected with reference to the conversion instruction table, and the data format conversion means stored in the data format conversion means storage means corresponding to the selected various classifications is selected. The leaf side of the data format conversion means for reading and converting the data format of the content data by the data format conversion means related to the reading, and the content data whose data format has been converted by the data format conversion means. The present invention is to adopt a configuration of a data processing relay device, which comprises a transmission means for transmitting to an adjacent node.

[0030] A fourth feature of the apparatus of the present invention is that the receiving means in the third feature of the apparatus of the present invention has a function of receiving preference cost information transferred from an adjacent node on the leaf side, and the conversion. The instruction table includes a preference cost information extracting means for extracting the preference cost information received by the receiving means, a preference cost information table for holding the preference cost information extracted by the preference cost information extracting means, and the preference. The content can be updated based on the preference cost information aggregation means for obtaining new preference cost information by intensively performing a predetermined operation on the preference cost information held in the cost information table as a vector. The data processing according to claim 11, wherein the transmission means has a function of transmitting the new preference cost information obtained by the preference cost information aggregation means toward the route-side adjacent node. The configuration of the relay device is adopted.

[0031] The first feature of the network system device of the present invention is in the process of relaying the content data downstream to the relay nodes constituting the multicast tree-shaped network for distributing the content data from the server to the client. , The configuration of the data processing relay network system device is characterized in that the data processing relay device according to claim 9 for adding predetermined additional data to the content data is assigned to each of the data processing relay devices to form a network. is there.

[0032] The second feature of the network system apparatus of the present invention is that in the process of relaying the content data downstream to the relay node constituting the multicast tree-type network for distributing the content data from the server to the client. A configuration of a data processing relay network system device is adopted, wherein the data processing relay device according to claim 10 for adding predetermined additional data to the content data is assigned to each of the data processing relay devices to form a network configuration.

[0033] A third feature of the network system device of the present invention is that the relay node constituting the multicast tree-type network for distributing the content data from the server to the client is subject to the downstream relay process of the content data. The configuration of a data processing relay network system device is adopted, wherein the data processing relay device according to claim 11 for converting the data format of the content data is assigned to each of the data processing relay devices to form a network configuration.

[0034] A fourth feature of the network system apparatus of the present invention is that the relay node constituting the multicast tree-type network for distributing the content data from the server to the client is concerned in the downstream relay process of the content data. The configuration of a data processing relay network system device is adopted, characterized in that the data processing relay device according to claim 12 for converting the data format of the content data is assigned to each of the data processing relay devices to form a network configuration.

[0035] On the other hand, the first feature of the program of the present invention is a multicast tree type including a server that distributes content data, a client that receives the content data, and a relay node that connects the server and an existing client. This is a data processing relay processing program for adding predetermined additional data to the content data in the downstream relay process of the content data by the relay nodes each constituting the computer, which is applied to the network of the above. Based on the preference cost information showing the correlation between the preference of the additional data of the client and the additional cost of the additional data when the content data is transferred from the adjacent node on the root side of each of the nodes. , A process step of selecting various classifications of the additional data defined in advance for each existing leaf-side adjacent node, and selection when the additional data is not added to the transferred content data. The processing step of transferring the additional data registered in advance corresponding to the various classifications to the leaf-side adjacent node, and the addition of the additional data already added to the transferred content data. When the data is different from that of the selected various classifications, the processing step of replacing the additional data with the additional data registered in advance corresponding to the various classifications and transferring the additional data to the leaf side adjacent node. When the additional data has already been added to the transferred content data and the additional data is the same as that of the selected various categories, the content data is transferred to the leaf-side adjacent node. It is a configuration of a data processing relay processing program characterized by having a processing step of transferring as it is.

[0036] The second feature of the program of the present invention is a multicast tree-type network including a server that distributes content data, a client that receives the content data, and a relay node that connects the server and an existing client. This is a data processing relay processing program for converting the data format of the content data in the downstream relay process of the content data by the relay nodes constituting the computer, respectively, in each of the relay nodes. When the content data is transferred from the root-side adjacent node, the content is based on the preference cost information showing the correlation between the client's preference in the data format and the data format conversion cost of the content data. In order to convert the data format of the data into a format that can be received by the client, a processing step of selecting various classifications of the data format conversion means defined in advance for each existing leaf-side adjacent node, and the transferred data format are described. When the data format conversion means for obtaining the data format of the content data is different from that of the selected various classifications, the content data is registered in advance corresponding to the various classifications. The processing step of converting by the data format conversion means and transferring to the leaf side adjacent node, and the data format conversion means for obtaining the data format of the transferred content data are those of the various classifications selected. In the same case, there is a configuration of a data processing relay processing program characterized by having a processing step of transferring the content data to the leaf side adjacent node as it is.

[0037] Further, the first feature of the recording medium of the present invention includes a server that distributes content data, a client that receives the content data, and a relay node that connects the server and an existing client. The data according to claim 17, wherein a predetermined additional data is added to the content data in the downstream relay process of the content data by the relay nodes each constituting the computer, which is applied to the multicast tree type network. The data processing relay processing program is characterized in that the processing procedure is actually recorded by the processing relay processing program, and the configuration of the recording medium on which the data processing relay processing program is recorded is adopted.

[0038] A second feature of the recording medium of the present invention is a multicast including a server for distributing content data, a client for receiving the content data, and a relay node for connecting the server and an existing client. The data processing relay processing program according to claim 18 for converting the data format of the content data in the downstream relay process of the content data by the relay nodes each constituting a computer, which is applied to a tree-shaped network. The configuration of a recording medium that records a data processing relay processing program, which is characterized by actually recording the processing procedure, is adopted.

[Embodiment of the Invention] Hereinafter, with reference to the attached drawings, the embodiment of the present invention will be described in the stream data in the process of relaying the stream data by a plurality of relay nodes as an outline thereof. On the other hand, the explanation will be made on the assumption that the advertisement data is added as predetermined additional data, and subsequently, the first and second device examples, the network system device example and the method example based on the outline explanation, and the method example thereof will be described. An example of a program and an example of a recording medium for carrying out the above will be described in order, and further, as a modification of these, two examples assuming a case of converting the data format of the stream data will be described in detail. .. Hereinafter, "various classifications" will be referred to as "categories".

[Overview] In the present embodiment, it is assumed that stream data is mainly delivered from a server to a plurality of clients by multicast. However, by assuming a special case where there is only one client, the present invention can also be applied to one-to-one communication (unicast).

[0041] Here, the client (user) shall select one or a plurality of categories from the n types of advertisement categories prepared. However, the user does not have to explicitly select the advertisement category at this time. For example, information on the user's preference may be automatically extracted from the network access history of the client.

[0042] Further, each relay node has a function of adding or replacing advertising data to stream data for each leaf-side adjacent node (hereinafter, also referred to as "child node" or simply "child") in a multicast tree-type network. Shall be provided.

[0043] In the multicast network composed of the relay nodes as described above, under the condition that the advertisement preferred by the client is added to each relay node by the time the stream data transmitted from the server arrives at the client. The means, methods, procedures and procedures for minimizing the cost of adding / replacing advertising data throughout the network are shown below.

(Example of First Device and Example of Network System Device) First, FIG. 1 shows an internal configuration of a relay node (data processing relay device referred to in the present invention) according to the first device example of the present invention. It is a block diagram.

As shown in the figure, the relay node N1 according to the present device example is a multicast tree for distributing stream data from a single server (not shown) to one or more clients (not shown). It is applied to a network of forms (not shown), and in order to add advertisement data to the stream data in the process of relaying the required stream data, basically, the advertisement data storage means 11 and the additional advertisement instruction table 12 The receiving means 13, the advertisement adding / replacing means 14, and the transmitting means 15 are provided.

[0046] Of these, the advertisement data storage means 11 stores the advertisement data to be delivered to each existing client in advance across a plurality of required categories, and the additional advertisement instruction table 12 shows. , One or more existing leaf-side adjacencies based on a preference vector (a form of "preference cost information" referred to in the present invention; details will be described later) showing the correlation between the preference of each client and the additional cost of advertising data. The categories of advertising data to be transferred to the nodes (not shown) are classified and defined in advance for each leaf-side adjacent node.

Further, the receiving means 13 receives the stream data transferred from the root side adjacent node (not shown) and also receives one or more preference vectors transferred from one or more leaf side adjacent nodes. Is what you do. The receiving means 13 also functions to receive the advertising data to be registered in advance in the advertising data storage means 11 from the network.

[0048] Further, the advertisement addition / replacement means 14 sets the category of advertisement data to be transferred to each leaf-side adjacent node according to the data addition form of the stream data received by the reception means 13, and displays the additional advertisement instruction table 12. In addition to referencing and selecting, the advertisement data stored in the advertisement data storage means 11 corresponding to the selected category is read, and the advertisement data related to the reading is added or replaced with the stream data.

[0049] Then, the transmission means 15 transmits the stream data to which the advertisement data has been added or replaced by the advertisement addition / replacement means 14 to the adjacent nodes on the leaf side.

[0050] The content of the additional advertisement instruction table 12 can be updated by the illustrated preference extraction means 16, the preference information table 17, and the preference aggregation means 18.

That is, the additional advertisement instruction table 12 is extracted by the preference extracting means 16 that extracts (removes unnecessary packet headers and the like) one or more preference vectors received by the receiving means 13 and the preference extracting means 16. The preference information table 17 that holds one or more preference vectors and the preference aggregation means 18 that obtains a new preference vector by intensively performing a predetermined operation on the one or more preference vectors held in the preference information table 17. It is possible to update the contents based on.

[0052] In order to configure the "data processing relay network system device" referred to in the present invention by the relay node N1 configured as described above, stream data is distributed from a single server to one or more clients. A multicast tree-type network for this purpose may be configured, and the above relay nodes N1 may be assigned to each of a plurality of relay nodes in the network (the form of the network is not particularly shown, but a method described later). Obviously in the example).

(Example of First Method) Subsequently, an example of the first method implemented by the relay node N1 and the network system apparatus configured as described above will be described.

[0054] First, in this method example, the following cost model is assumed. That is, the cost at which the relay node N1 simply forwards the packet from the root side adjacent node (hereinafter, also referred to as "parent node" or simply "parent") to each leaf side adjacent node is "0", and the advertisement. It is assumed that the cost of adding / replacing data is "1".

[0055] For example, when a relay node N1 on the network has c children, it is simply transferred to x children, and advertisement data is added to the remaining cx children. Assuming that the replacement process is executed and sent, the cost of the corresponding relay node N1 is cx. Reducing the cost of the entire network under this cost model means reducing the number of times advertising data is added or replaced.

[0056] Here, first, a method for minimizing the cost of the entire network under the above cost model will be described below. This method is realized by two phases, a "request phase" and a "delivery phase".

[0057] Here, in the request phase, the category of the advertisement preferred by the client (hereinafter, also referred to as "advertisement category" or simply "category") is transmitted to the network, and based on this, a plurality of relay nodes (N1). , N1, ...) to determine the relay node N1 that actually adds / replaces the advertising data.

[0058] On the other hand, in the delivery phase, appropriate advertisement data is actually added / replaced at the appropriate relay node N1 based on the decision made by the request phase. The detailed operation of these request phase and delivery phase will be described below.

[0059] First, in the request phase, each relay node and client periodically transmit the preference vector defined below to the parent node in the multicast tree. That is, when the number of advertisement categories is n, the preference vector is an n-dimensional vector (n-bit vector) whose element is "1" or "0", and the i-th bit of the preference vector is "1". If there is, it indicates that the i-th advertising category is preferred.

[0060] Here, when the client desires the i-th advertisement category, the client transmits a preference vector in which the i-th bit in the n-bit vector is "1" to the parent node. For example, the preference vector (0,1,0) indicates that the second category out of the three advertising categories is desired.

[0061] The client may also desire a plurality of advertising categories at the same time, for example, the preference vector (1,1,0) desires the first and second categories from the three advertising categories. Represents that. Therefore, if any advertising category is acceptable, the preference vector is (1,1,1).

[0062] Hereinafter, the processing of the request phase based on the above-mentioned preference vector will be described with reference to the drawings.

[0063] FIGS. 2 (a) and 2 (b) are diagrams showing an outline of a request phase in the stream data processing relay method according to the first method example of the present invention.

[0064] First, as shown in FIG. 6A, the relay node N1 takes a majority vote of the preference vector transmitted from the child, and only the element (bit) of the preference vector corresponding to the most requested advertisement category is selected. Set to "1" and send the preference vector to the parent node. At this time, if there are a plurality of most requested advertisement categories, all the elements of the preference vector corresponding to those advertisement categories are set to "1" (other elements are "0"), and the preference vector is transmitted to the parent node. ..

[0065] For example, when there are two children and the preference vector transmitted from each child is (1,0,0), (1,0,1) as shown in the figure, the sum of these is calculated. Then, it becomes (2,0,1), so the preference vector (1,0,0) with only the first bit set to "1" is sent to the parent node. That is, the sum of the preference vectors sent from all the children is taken, only the bit that takes the maximum value is set to "1", the others are set to "0", and this is sent to the parent node.

Further, as shown in FIG. 6B, the relay node N1 sets each child of a table indicating the category of the advertisement data to be added / replaced in the delivery phase, that is, the above-mentioned additional advertisement instruction table 12. It is generated and stored according to the above-mentioned preference vector sent from.

[0067] In this additional advertisement instruction table 12, the column of "In" represents the category of the advertisement data added to the stream data from the parent node, and the columns of "Out1", "Out2", ... Indicates the category of advertising data to be added to the stream data output to the children of, 1st, 2nd, .... Further, "φ" represents a state in which advertising data is not added, and "A", "B", and "C" represent the first, second, and third advertising categories, respectively.

[0068] Here, in the additional advertisement instruction table 12, the child who has transmitted the preference vector (1,0,0) is added / replaced with the advertisement of category A, and the preference vector (1,0,1) is added. ) Is instructed to the above-mentioned advertisement addition / replacement means 14 to add / replace the advertisement of category A or C to the child. However, in the latter case, the additional advertisement instruction table 12 is configured so that only transfer is required as much as possible according to the category of the advertisement data added to the stream data from the parent node.

[0069] For example, when the advertisement data of category C is added to the stream data from the parent node, category C is selected for the child who has sent the preference vector (1,0,1). By doing so, it is possible to only transfer the stream data (when category A is selected, replacement (category C category A) is required and the cost increases, so this is avoided). ..

Next, the processing of the delivery phase based on the above-mentioned preference vector will be described with reference to the drawings.

FIG. 3 is a diagram showing a specific operation example of the delivery phase in the data processing relay method according to the first method example of the present invention.

In the figure, the nodes represented by "A" and "B" represent clients, the nodes represented by "S" represent servers, and the other nodes are relay nodes N1 (hereinafter, reference numeral "1"). , "2", "3", "4" are used as alternatives). In addition, there are two types of advertisement categories, "A" and "B", and the above-mentioned symbols indicating clients ("A" and "B") represent the advertisement categories preferred by the corresponding client (however, "A"). And "B" are the first and second advertising categories, respectively).

[0073] Further, among the symbols in each additional advertisement instruction table 12, "*" means that it fits into an arbitrary advertisement category (including a state in which advertisement data is not added) ("In", "Out1", "Out2", "φ" are the same as those in Fig. 2, but the child numbers are 1,2,3, ... in order from the left child in the figure. Assuming they are numbered).

As shown in the figure, first, the client who prefers the advertisement category A sends the preference vector (1,0) to the parent node, and the client who prefers the advertisement category B sends the preference vector (0,1). To the parent node.

At this time, since the relay node 3 receives the preference vector (1,0) from the child, the advertisement data added to the stream data sent from the parent node (relay node 2) in the delivery phase. The additional advertisement instruction table 12 is generated so that the advertisement data belonging to the advertisement category A is added or replaced regardless of the category, and the preference vector (1,0) received from the child node is transmitted to the parent node as it is. To do.

On the other hand, in the relay node 4, since the preference vectors (0,1) and (1,0) are sent from the two children, the category of the advertisement data added to the stream data from the relay node 2. Regardless of this, the additional advertisement instruction table 12 is provided so that the left child of the figure is added or replaced with the advertisement data belonging to the advertisement category B, and the right child is added or replaced with the advertisement data belonging to the advertisement category A. It is configured and a new preference vector (1,1) generated according to the above-mentioned rule is transmitted to the relay node 2.

As a result of the above, the preference vectors (1,0) and (1,1) are sent from the two children to the relay node 2, and the relay node 2 is the left child (relay node 3). ), The addition or replacement of the advertisement data belonging to the advertisement category A is also performed by the right child (relay) regardless of the category of the advertisement data added to the stream data from the parent node (relay node 1). For node 4), the additional advertisement instruction table 12 is configured so that the advertisement data belonging to either the advertisement category A or B (the advertisement data belonging to the category with the lower cost) is added or replaced. To do.

That is, in the case of the illustrated example, even if the advertisement data of the advertisement category A is added to the stream data from the relay node 1 or the advertisement data of the advertisement category B is added, the stream data is It will be transferred to the relay node 4 as it is. However, when no advertisement data is added to the stream data, the relay node 2 arbitrarily selects either the advertisement category A or B and adds the advertisement data of the selected category to the stream. Then, it is transmitted to the relay node 4 (the operation of the relay node 1 is the same as that of the relay node 3 described above).

[0079] Then, based on the additional advertisement instruction table generated and configured in this way, the advertisement data is added / replaced in the delivery phase.

Since each relay node 1,2,3,4 does not always receive the preference vector sent from the child at the same time, the preference vector transmitted from the child is actually used as the preference information described above. It is memorized in Table 17, and when the preference vectors from all the children are prepared, a majority vote is taken to obtain a new preference vector. In addition, in order to respond to changes in the preference vector and the participation and withdrawal of clients in the multicast tree, the operation of taking the required majority vote is performed, for example, when the preference vector from the child is changed, or , It is preferable to perform this at predetermined time intervals set in advance.

Next, FIG. 4 is a diagram showing a specific operation example of the delivery phase in the data processing relay method according to the first method example of the present invention (corresponding to the request phase shown in FIG. 3).

As shown in the figure, each relay node 1,2,3,4 adds actual advertisement data based on the advertisement data added to the stream data sent from the parent node. Determine the replacement process. Therefore, even if the stream data to which the advertisement data belonging to the category inconsistent with the preference vector sent to the parent node is added is sent from the parent node due to the timing shift of the table update due to the request phase, the "client's" The function of "adding advertisements as you like" does not break down.

Therefore, the request phase and the delivery phase can operate independently, and if the time interval in which each additional advertisement instruction table 12 is updated by the request phase is sufficiently long, the above cost model can also be used. With and, the lowest cost delivery is realized.

[0084] Next, FIG. 5 is a diagram showing an example of cost when the required advertisement data addition / replacement process is executed by a normal method.

[0085] As shown in the figure, first, it is assumed that each client constituting the leaf of the multicast tree prefers any of "A", "B", and "C" as an advertisement category. In addition, the thick solid line, dotted line, and broken line in the figure represent communication links through which stream data to which advertising data of advertising categories A, B, and C are added flows, and the numbers assigned in the vicinity of each relay node are shown. Represents the cost at each of these relay nodes.

[0086] Here, based on the fact that there are the most clients who prefer the advertisement category A, the advertisement data of the category A is added to the stream data at the relay node directly under the server, and the clients are adjacent to each other. At the relay node, the advertisement data shall be replaced according to the tastes of each of those clients.

[0087] When the advertisement data is replaced as described above, it is understood that the cost of the entire multicast network is "11" when the sum of the costs at each relay node is taken.

On the other hand, FIG. 6 is a diagram showing a second cost example when the addition / replacement process of the advertisement data is executed by the data processing relay method according to the first method example of the present invention.

As shown in the figure, when the advertisement data is replaced by the example of this method, the cost of the entire multicast network is "8", which is lower than the above-mentioned normal case, and the required advertisement data is required. It is possible to execute the addition / replacement process of.

(Example of Second Device and Example of Network System Device) Subsequently, FIG. 7 shows the internal configuration of the relay node (data processing relay device referred to in the present invention) according to the second device example of the present invention. It is a block diagram which shows.

As shown in the figure, the relay node N2 according to the present device example is directed from a single server (not shown) to one or more clients (not shown) as in the first device example. It is applied to a multicast tree type network (not shown) for delivering stream data, and basically, in order to add advertisement data to the stream data in the process of relaying the required stream data, the advertisement data storage is basically performed. The means 21, the additional advertisement instruction table 22, the receiving means 23, the advertisement adding / replacing means 24, and the transmitting means 25 are included.

The configurations of the advertisement data storage means 21, the additional advertisement instruction table 22, the receiving means 23, the advertisement adding / replacing means 24, and the transmitting means 25 are the same as those in the first device example. The description is omitted.

[0093] Further, the content of the additional advertisement instruction table 22 can be updated by the illustrated cost extraction means 26, the cost information table 27, and the cost totaling means 28.

That is, the additional advertisement instruction table 22 is a cost extraction means 26 for extracting one or more cost vectors (a form of "preference cost information" referred to in the present invention; details will be described later) received by the receiving means 23. , A new cost information table 27 holding one or more cost vectors extracted by the cost extraction means 26 and one or more cost vectors held in the cost information table 27 are subjected to a predetermined operation intensively. The content is updated based on the preference aggregation means 18 for obtaining a cost vector.

[0095] In order to configure the "data processing relay network system device" referred to in the present invention by the relay node N2 configured as described above, stream data is distributed from a single server to one or more clients. A multicast tree-type network for this purpose may be configured, and the above relay nodes N2 may be assigned to each of a plurality of relay nodes in the network (the form of the network is not particularly shown, but a method described later). Obviously in the example).

(Example of Second Method) Next, an example of the second method implemented by the relay node N2 and the network system apparatus configured as described above will be described assuming a more general cost model. ..

[0097] FIG. 8 is a diagram showing an outline of a cost model in the data processing relay method according to the second method example of the present invention.

As shown in the figure, in this method example, when a certain relay node N2 (hereinafter referred to as an alternative display by the symbol k) has c children, a stream transmitted from the parent node. Suppose that when the advertisement data of the i-th category is added to the data, the advertisement data is replaced with the advertisement data of the a (j) -th category for the j-th child.

At this time, the cost of adding / replacing the advertisement data at the relay node k is as shown in the figure f._kIt shall be given by (i, a (1), a (2), ..., a (c)). However, even if the advertisement data is not added, it is assumed that it is one advertisement category, and in the following explanation, only the replacement of the advertisement data will be considered. In addition, the advertising data belonging to the same advertising category shall be equivalent from the viewpoint of the replacement cost. If this is not the case, the categories may be further subdivided to satisfy the above conditions.

[0100] For example, the advertising categories "A", "B", and "C" are "A", respectively.₁And "A₂, "B₁And "B₂, "C₁And "C₂Even if it is subdivided into "", if the categorization that is meaningful to the client is "A", "B", "C", it will be called "A", "B", "C" on the user interface. If you want to categorize, for example, if you prefer advertising category A, you are actually in advertising category A.₁Or A₂Can be interpreted and processed as desired.

[0101] With respect to the above cost model, a method of replacing the advertisement data so as to minimize the cost of the entire network will be described below. In addition, this method is also realized by two phases of "request phase" and "delivery phase" as in the case of the first method example.

[0102] First, in the request phase, the client has a cost of "0" when the advertisement data of his / her preference is added to the stream data, and when other advertisement data is added, the client has a cost of "0". Sends information that the cost is infinite "" to the parent node. If this information is represented by an n-dimensional vector (cost vector) for the number of advertising categories n, for example, the cost vector from a child who prefers advertising data in the fourth category is (, , ). , 0, , , ..., ).

[0103] Here, each relay node k, k, ... is a function f representing the cost vector transmitted from the child and the cost for replacing the advertisement data._kBased on (i, a (1), a (2), ..., a (c)), the relay node k when the advertisement data of category i is added to the stream data received from the parent. The minimum cost value of the subtree to be the root is obtained for each i, and this is represented by a cost vector and sent to the parent node.

That is, the stream data received by the relay node k from the parent node P (k) is added with the advertisement data of the category i, and the subtree rooted at the relay node k is referred to as T (k). If so, the minimum cost of T (k) that can be achieved at this time is v^k_iIf so, the relay node k has an n-dimensional cost vector V with respect to P (k)._k= (v^k₁, v^k₂, ..., v^k_n) Is sent.

[0105] The above cost vectors are the cost vector sent from the child node and the above function f._kCalculated from (i, a (1), a (2), ..., a (c)) (detailed calculation method will be described later), for example, V_kIf is (10,23,41), there are three ad categories, and the stream data from P (k) is populated with ad data belonging to the first, second, or third category. If so, the minimum cost of T (k) that can be achieved is "10", "23", and "41", respectively. Then, the calculation / transmission process of the cost vector as described above is executed in order from the leaf to the route.

[0106] In each relay node k, v for each i (i = 1,2, ..., n).^k_iThe category of advertising data that should be replaced with respect to the stream data sent to each child in order to achieve that v^k_iSince it can be obtained in the calculation process of, this is recorded as the additional advertisement instruction table 22, and the additional advertisement instruction table 22 is used to replace the advertisement data in the delivery phase as in the first method example. To do.

Next, the method of calculating the cost vector will be described as follows. That is, first, any relay node k having c children sends the advertisement data added to the stream data to the j (j = 1,2, ..., n) th child a ( j) Suppose that you want to replace with the advertisement data of the third category.

[0108] At this time, assuming that the stream data to which the i-th advertisement data is added arrives from the parent node P (k), the cost related to the replacement of the advertisement data in the relay node k is the above-mentioned function f._kIt is represented by (i, a (1), a (2), ..., a (c)).

[0109] Now, for the relay node k, the n-dimensional cost vector sent from the jth child is U._j= (u^j₁, u^j₂, ..., u^j_n), And the jth child is the relay node C_kIf it is (j), T (C) when stream data with the a (j) th advertisement data added from k is sent._kThe minimum cost of (j)) is u^j_{a (j)}Is.

Therefore, the minimum cost of T (k) in this case is f._k(i, a (1), a (2), ..., a (c)) + u¹_{a (1)}+ ... + u^c_{a (c)}Will be. Therefore, V_k= (v^k₁, v^k₂, ..., v^k_n) Element v_iIs f in all combinations of a (1), a (2), ..., a (c)_k(i, a (1), a (2), ..., a (c)) + u¹_{a (1)}+ ... + u^c_{a (c)}It may be the minimum value of.

[0111] Then, the above calculation is performed for each i, and V_k= (v^k₁, v^k₂, ..., v^k_n) And each v^k_iThe combination of a (1), a (2), ..., a (c) that achieves the above is recorded in the additional advertisement instruction table 22 at each relay node k.

Next, FIG. 9 is a diagram showing a specific operation example of the request phase in the data processing relay method according to the second method example of the present invention, and FIGS. 10 (a) to 10 (c) are the same. It is a figure which shows the specific example of the cost function in a data processing relay method.

First, as shown in FIG. 9, in a state where three relay nodes are interposed between the server and the client, the cost function for each relay node k (1,2,3) is f._k(i, a (1), a (2), ..., a (c)) = g_k(i, a (1)) + g_k(i, a (2)) + ... + g_kTake the case where it can be decomposed as (i, a (c)) as an example.

[0114] That is, when focusing on a certain relay node k, it means that the costs required for the processing of replacing the advertisement data for each child are completely independent and the cost functions are equal to each other.

[0115] Here, the cost function g in each relay node._kTo give an example of, it will be shown in each left column of FIGS. 10 (a) to 10 (c). In the figure, the cost function g_kEach row represents the ad category before replacement, each column represents the ad category after replacement, and for "φ", "A", and "B", the first, second, and third ad categories, respectively. It is treated as. However, the state in which no advertisement data is added is also regarded as one advertisement category.

[0116] For example, in the relay node 1 shown in FIG. 9, the cost g required to add the advertisement data A from the state where no advertisement data is added.₁(φ, A) is "10" (The cost vector and additional advertisement instruction table 22 shown in the figure are those sent and generated in the request phase based on the cost function shown in the left column of FIG. Is).

Next, FIGS. 11 (a) and 11 (b) are diagrams showing a part of a specific operation example of the request phase in the data processing relay method according to the second method example of the present invention, and FIG. 12 (b). a) to (c) are diagrams showing a calculation example of the cost function in the data processing relay method, and FIG. 13 is a diagram showing another part of a specific operation example of the request phase in the data processing relay method.

First, as shown in FIG. 11, the relay node 2 receives the cost vector U from its child relay node 3.₁When = (20,1,20) is received, the cost vector to be sent to the relay node 1 and the calculation method of the additional advertisement instruction table 22 to be generated to the relay node 2 are as shown in FIG. Become.

[0119] [Outside 1]<img file="JP3788754B2_D0001.tif" />[0120] The minimum value in the i-th row of the above equation 1 represents the minimum cost of T (2) that can be achieved when the advertisement data of the i-th category is added to the stream data from the parent node. There is. In either case, it is understood that sending the child in place of the category A advertising data is the choice to achieve the minimum cost (see FIG. 12 (b)).

[0121] Then, as shown in FIG. 12 (c), the cost vector to be sent to the relay node 3 and the additional advertisement instruction table 22 to be generated in the relay node 2 can be obtained. As shown in FIG. 13, after the request phase processing in the relay node 2 is completed, the same processing is performed in the order of the relay nodes 3, 2, 1 to generate the additional advertisement instruction table 22 in all the relay nodes. Based on this, in the delivery phase described below, the addition / replacement process of the advertisement data is performed.

Next, FIG. 14 is a diagram showing a specific operation example of the delivery phase in the data processing relay method according to the second method example of the present invention.

As shown in the figure, the stream data sent from the server is processed according to the additional advertisement instruction table 22 of each relay node 1, 2, and 3. That is, the relay node 1 transfers the stream data without adding the advertisement data, the relay node 2 transfers the stream data with the advertisement data of category A added to the stream data, and the relay node 3 already transfers the advertisement of category A. Since the data is added to the stream data, only the transfer is done.

The above method minimizes the cost of the entire network. In the example of FIG. 9, the addition processing of the advertisement data is performed only by the relay node 2, as shown in FIG.₂But G₁And G₃This is because it has an element whose value is smaller than that of. For example, it is understood that the load can be distributed by reflecting the load state of the relay node in this cost value.

Next, FIG. 15 is a diagram showing a specific operation example of another request phase in the data processing relay method according to the second method example of the present invention, and FIGS. 16 (a) to 16 (d) are shown. , It is a figure which shows the calculation example of another cost function in the same data processing relay method.

[0126] First, as shown in FIG. 15, when stream data is delivered to a plurality of clients by multicast, there are nodes having a plurality of children, such as relay node 2 and relay node 4. As in the example shown in Figure 9, f_k(i, a (1), a (2), ..., a (c)) = g_k(i, a (1)) + g_k(i, a (2)) + ... + g_kAssuming that it can be decomposed as (i, a (c)), the cost vector U from the j (j = 1,2, ..., c) th child_j= (u^j₁, u^j₂, ..., u^j_n), F_k(i, a (1), a (2), ..., a (c)) + u¹_{a (1)}+ u²_{a (2)}+ ... + u^c_{a (c)}= (g_k(i, a (1)) + u¹_{a (1)}) + (G_k(i, a (2)) + u²_{a (2)}) + ... + (g_k(i, a (c)) + u^c_{a (c)}).

[0127] Therefore, g for each j_k(i, a (j)) + u^j_{a (j)}By finding the minimum value of and taking the sum of them, f_k(i, a (1), a (2), ..., a (c)) + u¹_{a (1)}+ u²_{a (2)}+ ... + u^c_{a (c)}The minimum value of can be obtained (the cost vector and additional advertisement instruction table 22 shown in the figure are g._kWas sent and generated in the request phase when is given in the form shown in each left column of FIGS. 16 (a) to 16 (d)). Since the relay node 1 and the relay node 3 have one child, the calculation method of the cost vector and the additional advertisement instruction table 22 is the same as the example shown in FIG.

Next, FIGS. 17 (a) and 17 (b) are diagrams showing a part related to the relay node 2 in FIG. 15, and FIGS. 18 (a) to 18 (d) are the relay nodes 2 in FIG. FIG. 19 is a diagram showing a calculation example, and FIG. 19 is a diagram showing how the relay node 2 of FIG. 15 sends a cost vector.

[0129] First, as shown in FIG. 17, for the relay node 2, the cost vector U from the relay node 3₁= (20,1,20), but also cost vector U from relay node 4₂= (4,3,3) are assumed to have arrived respectively.

At this time, the cost vector U₁And U₂And g₂Matrix G representing₂Therefore, by performing the same calculation as the example shown in FIG. 10, the calculation results as shown in FIGS. 18 (a) and 18 (b) can be obtained, and further, by taking the sum of the minimum values for each child. , As shown in Fig. 18 (c), the cost vector V to be sent to the relay node 1.₂= (16,6,15) can now be obtained, and as shown in Fig. 19, the category of advertising data that should be replaced in order to obtain the minimum value at the same time as the request phase processing at the relay node 2 is completed , Each child node is set in the additional advertisement instruction table 22 in the relay node, and based on this, the required advertisement data addition / replacement process is performed in the delivery phase described below.

[0131] Next, FIG. 20 is a diagram showing a specific operation example of another delivery phase in the data processing relay method according to the second method example of the present invention.

As shown in the figure, the stream data sent from the server is processed according to the additional advertisement instruction table 22 of each relay node 1, 2, 3, and 4. That is, in the relay node 1, the advertisement data of category A is added to the stream data, and in the relay node 2, the advertisement data of category A is already added to the stream data, so that only the transfer is performed, and the relay node 3 performs only the transfer. For the same reason, only the transfer is performed, and in the relay node 4, only the left child in the figure is replaced with the category B advertisement data, and only the right child is transferred.

[0133] That is, the relay node 1 and the relay node 4 perform the required replacement processing of the advertisement data, and the relay node 2 and the relay node 3 merely perform the transfer. This is the matrix G, as shown in FIG.₁And G₄The value of the element of is the matrix G₂And G₃It reflects that it is relatively smaller than the value of the element of. Therefore, as in the case of the example of FIG. 9, g_kIt is understood that the load distribution of the entire network can be realized by reflecting the load status of each relay node 1, 2, 3, and 4.

[0134] When it is expected that the traffic amount will increase significantly by adding the advertisement data to the stream data, the communication link having a narrow usable band among the communication links constituting the multicast tree will be stream data. When is passed, it is more effective not to add advertising data to it.

To achieve this, for example, if the communication link on the tree connecting the relay node k and the jth child is congested, the cost function f when a (j) φ_kBy setting the values of (i, a (1), a (2), ..., a (c)) to a large value, advertising data is not added as much as possible when stream data passes through this communication link. It is possible to put it in a state.

[0136] On the other hand, by adding the number of viewers, the type of the stream data, or the information of the scene that changes from moment to moment to the stream data from the server separately from the advertisement data, at each relay node, It is also possible to select predetermined advertisement data according to information such as the number of viewers from the advertisement data belonging to the category preferred by the client, and add / replace it.

[0137] FIG. 21 is a diagram showing a number of viewers-advertising category search table applicable to the data processing relay method according to the second method example of the present invention.

[0138] As shown in the figure, in the number of viewers-advertising category search table 29, the row represents the number of viewers and the column represents the ad category, "A1", "A2", "A3". However, "B1", "B2", "B3" are the advertisement data belonging to the advertisement category A, and "C1", "C2", "C3" are the advertisement data belonging to the advertisement category B. Each of the advertising data to which it belongs is represented.

[0139] By placing the above-mentioned number of viewers-advertisement category search table 29 in each relay node N2 in addition to the additional advertisement instruction table 22, advertisement data to be added / replaced according to the number of viewers can be added. Can be changed.

[0140] For example, when it is instructed to add (replace) the advertisement data of category B by the additional advertisement instruction table 22 created in the request phase, the number of viewers information added to the stream data from the server. If is "5000", the advertisement data "B2" should be added (replaced). By adopting such a method, it is possible to carry out advertisements that reflect the intentions of both the advertiser and the stream data provider and the user.

(Program Example and Recording Media Example) Subsequently, a program example and a recording medium example applicable to the implementation of the first and second method examples described above will be described.

[0142] As is clear from the above description, the relay nodes N1 and N2 are composed of computers that send and receive stream data composed of packets. Therefore, the first and second method examples described above can be programmed with this as an execution procedure.

[0143] In this case, as the required program, for example, (a) the correlation between the preference of each client and the additional cost of the advertisement data when the stream data is transferred from the root-side adjacent node of the relay node. Based on the preference vector or cost vector representing, a processing step of selecting a category of advertisement data pre-classified and defined as additional advertisement instruction tables 12 and 22 for each existing leaf-side adjacent node, and (b). When the advertisement data is not added to the transferred stream data, the advertisement data registered in advance in the advertisement data storage means 11 and 21 corresponding to the selected category is transferred to each leaf side adjacent node. If the processing step and (c) the transferred stream data have already been added with advertisement data and the advertisement data is different from that of the selected category, the advertisement data is assigned to the category. Then, the processing step of replacing the advertisement data registered in advance in the advertisement data storage means 11 and 21 and transferring the data to each leaf side adjacent node, and (d) the advertisement data is already added to the transferred stream data. If the additional data is the same as that of the selected category, the stream data may be provided with a processing step of transferring the stream data to each leaf-side adjacent node as it is.

[0144] Further, a series of procedures including each processing step constituting the above program is written in an arbitrary recording medium, and these are relay nodes N1 and N2 (all relay nodes constituting the network) prior to execution. ), Data processing relay processing related to the required advertisement data addition function will be realized.

[0145] As described above, for the first and second device examples, the network system device example and the method example, and the data processing relay processing program and the recording medium, as the required additional data to be added to the stream data, the advertisement data is taken as an example. As described above, this is merely an example of application of the present invention, and the present invention is similarly applicable to any other additional data.

(1st Modified Example) Subsequently, as a modified example of the first and second apparatus examples, the network system apparatus example and the method example described above, and the data processing relay processing program and the recording medium, stream data An example of converting the data format of is described. In this first modification, it is assumed that the data format of the stream data can be converted (has reversibility) with each other for all existing types.

[0147] First, when data format conversion of stream data is performed, a data format conversion means storage means, which replaces the advertisement data storage means (11, 21) shown in the first and second device examples, respectively, is added as a relay node. A conversion instruction table that replaces the advertisement instruction table (12,22) and a data format conversion means that replaces the advertisement addition / replacement means (14,24) are newly configured, and a reception means similar to that in each device example. A transmission means, a preference or cost extraction means, a preference or cost information table, and a preference or cost aggregation means are set.

[0148] Of the above, the data format conversion means storage means is required to have a data format conversion means for converting the data format of the stream data to be delivered to each existing client into a format receivable by each client. It is stored in advance across multiple categories, and the conversion instruction table exists based on the preference vector or cost vector that shows the correlation between the preference of each client and the data format conversion cost of the stream data. The categories of data format conversion means to be adopted in one or more leaf-side adjacent nodes are classified and defined in advance for each leaf-side adjacent node.

[0149] Further, the data format conversion means selects the category of the data format conversion means to be adopted in each leaf side adjacent node according to the data format of the stream data received by the receiving means by referring to the conversion instruction table. At the same time, the data format conversion means stored in the data format conversion means storage means is read according to the selected category, and the data format of the stream data is converted by the data format conversion means related to the reading.

[0150] In order to configure the data processing relay network system device by the relay nodes configured as described above, a multicast tree type for distributing stream data from a single server to one or more clients. A network may be configured, and the above relay nodes may be assigned to a plurality of relay nodes in the network.

[0151] In implementing the method, the relay nodes interpret the advertising data categories A, B, and φ described in the first and second method examples as languages that can be translated into each other, respectively. It can be explained as having a translation function. As a result, the server sends out the stream data described in the language φ, and by translating it at the relay node on the route to reach the client, the stream data described in the language requested by the client is delivered. It can be used for services.

[0152] For example, assuming translation to video data or the like as an example of stream data, the translation can be interpreted as an encoding conversion or a media conversion. However, since this kind of data conversion can be performed only in one direction in many cases, the above characteristics of data conversion should be taken into consideration when applying the method in this modification.

FIG. 22 is a diagram showing a specific operation of a request phase in the data processing relay method applied to the first modification of the present invention, and FIG. 23 is a diagram showing a specific delivery phase in the data processing relay method. It is a figure which shows the operation.

First, as shown in FIG. 22, the server sends out the required stream data by the encoding method C, and the three clients receive the stream data by the encoding method A or B different from the encoding method C. However, among the above encoding methods, it is possible to convert from method B to method A, but it is not possible to convert from method A to method B (this is expressed as "B A"). ). In addition, in the explanation of this figure, the same cost model as that explained in FIG. 3 is used as the cost model for simplification, but it can be extended to the general cost model explained in FIG. is there.

[0155] Here, when "A", "B", and "C" are the first, second, and third encoding methods, respectively, the relay node 4 has a preference vector (0,,) from two children. It receives 1,0), (1,0,0), but since it is B A, it is not possible to request the encoding method A from the relay node 2, so the preference vector (0,1,0) ) Is sent.

[0156] On the other hand, the relay node 2 receives the preference vectors (1,0,0), (0,1,0) from the two children, but since it is B A, the relay node 2 has a preference vector (1,0,0), (0,1,0). Then, the preference vector (0,1,0) is transmitted.

As a result of the above, in the request phase, a conversion instruction table as shown in the figure is set in each relay node 1, 2, 3, 4, and in the delivery phase, the conversion of the encoding method as shown in FIG. 23 is performed. Is realized. However, it is assumed that the data format sent by the server can be converted to B (otherwise, such a service itself does not hold).

[0158] When a program is configured in this modification, for example, when stream data is transferred to the program from a node adjacent to the root side of the (a ́) relay node, the preference and stream data of each client are received. For each one or more leaf-side adjacent nodes that exist to convert the data format of the stream data to a format that each client can receive, based on the preference vector or cost vector that represents the correlation with the data format conversion cost of The processing step of selecting the category of the pre-classified and defined data format conversion means as the conversion instruction table and (b ́) the data format conversion means for obtaining the data format of the transferred stream data are selected categories. When the stream data is different from that of the data, the stream data is converted by the data format conversion means registered in advance in the data format conversion means storage means corresponding to the category and transferred to each leaf side adjacent node. , (C ́) When the data format conversion means for obtaining the data format of the transferred stream data is the same as that of the selected category, the processing step of transferring the stream data as it is to each leaf side adjacent node is provided. Just let me do it.

[0159] Further, a series of procedures including each processing step constituting the above program is written in an arbitrary recording medium, and this is introduced to a relay node (all relay nodes constituting the network) prior to execution. Then, the data processing relay processing related to the required data conversion function can be realized.

(Second variant) Next, as a second variant, the data formats of stream data are not necessarily convertible to each other for all existing types (some have irreversibility). An example of the case will be described based on the above-mentioned first and second method examples. In the following description, it is assumed that at least one data format that can be converted into any data format requested by the client exists among all existing data formats (if this assumption is ignored, it is assumed). It is not possible to have all clients in one multicast tree).

[0161] First, FIG. 24 shows a conversion constraint that defines a constraint on conversion between data formats in the stream data described in the first method example in the data processing relay method applied to the second modification of the present invention. It is a figure which shows the graph (directed graph).

[0162] In the illustrated conversion constraint graph 30, the numbers shown at each node represent the types of all existing data formats (all four types), and conversion from data format i to data format j is possible. Then there is a directed branch (i, j) from node i to node j. However, when actually converting the data format i to the data format j, even if it is necessary to go through one or more other data formats in the middle, "the conversion from the data format i to the data format j is possible". Is defined as.

[0163] This means that in the cost model described in the first method example, arbitrary data format conversion is performed at a cost of "1", so it does not mean whether or not the corresponding data format can be directly converted. This is because it does not have. Therefore, if there is a directed path from the node i to the node j, there is always a directed branch (i, j).

[0164] The conversion constraint graph 30 described above is held in advance by the preference aggregation means 18 of the relay node N1 shown in the first device example to which the first method example is applied, or through the receiving means 13. It may be added as data to the preference vector transferred from one or more leaf-side adjacent nodes.

Next, FIG. 25 shows a preference vector sent by each relay node or client when the conversion constraint graph 30 shown in FIG. 24 is given, and stream data delivered corresponding to this preference vector. It is a figure which shows the relationship of.

[0166] The preference vector is defined in the same manner as in the first method example. That is, assuming that the total number of data formats is n, the preference vector is an n-dimensional vector (n-bit vector) in which the element is "1" or "0", and the i-th bit in the n-bit is "1". If there is, it means that the i-th data format is requested.

[0167] Here, if the method of aggregating the preference vector is described using the relay node 1 shown in the figure as an example, the relay node 2 requires the second or fourth data format from the definition of the preference vector. Understood. In order to send stream data from relay node 1 to relay node 2 in these data formats, the stream data must be in the second, third, or fourth data format according to the provisions of conversion constraint graph 30. is there.

[0168] In this way, S is a set of data formats of stream data from the parent node that can be converted into the data formats requested by the relay node (or client) j._jExpressed as S₂= {2,3,4}, S₃= {2,3,4}, S₅= {1,2,3} (j = 4 is a missing number).

At this time, in order to satisfy the requests from all the child nodes, the data format of the stream data from the parent node is S.₂ S₃ S₅= Must be {2,3}. Therefore, here, the second or third data format is requested from the parent node.

Further, since the sum of the preference vectors from all the child nodes is (1,2,1,2), the relay node is better when the stream data from the parent node is in the second data format. The conversion cost at 1 is low. Therefore, the relay node 1 sends (0,1,0,0) to the parent node (server 10 in the figure).

On the other hand, the preference vectors (0,1,0,1) and (0,0,1,1) generated by the relay nodes 2 and 3 are S.₆= {1,2,3,4}, S₇= {2,3,4}, S₈= {1,2,3,4}, and S₉It can be derived based on = {2,3,4}. S above_jThe intersection over each child of is not an empty set because it can be converted to any data format, but there is at least one data format.

[0172] The method of aggregating preference vectors at each relay node can be summarized as follows. 1. Preference vector from each child j and conversion constraint graph 30 to S_jTo calculate. 2. Sum of preference vectors from each child j (s₁, s₂, ..., s_n) Is calculated. 3.S_jLet i be the element of s_iLet I be the set of i that has the maximum value in the set of. 4. The preference vector to be sent to the parent node is (b)₁, b₂, ..., b_n). However, if i'is an element of I, b_i_’= 1 otherwise, b_i_’Set to = 0.

[0173] As in the first method example, the conversion instruction table is generated in each relay node so that the stream data is converted into a data format that satisfies the preference vector from each child. However, if stream data arrives from the parent node in a data format other than the requested data format due to the timing of updating the preference vector, etc., it will be converted if it can be converted to the data format requested by the child. If conversion is not possible, the data packet itself may be discarded.

[0174] This is not a big problem in a stable network where the order of packets is not changed. This is because, while each client or relay node continues to transmit the same preference vector on a regular basis, stream data does not arrive from the parent node in a data format other than the requested data for the following reasons. ..

That is, since the parent node calculates the preference vector so that the request of the child node is always satisfied, even if the child of the parent node other than the client or the relay node changes the preference vector, the parent node can change the preference vector. This is because the stream data requested by the newly generated preference vector can also be converted into the data format requested by the client or the relay node.

By the way, as a special case of conversion constraint, i₁&lt;i₂Then i₂I from the second data format₁There may be a constraint that conversion to the second data format is possible, but not the other way around. In this case, the calculation of the preference vector can be simplified as follows.

That is, the preference vector from the relay node (or client) j (b).^j₁, b^j₂, ..., b^j_n), B^j_iIf the minimum value of the subscript i satisfying = 1 is min (j) and the maximum value of min (j) over all child js is T, then S for all child js._jThe intersection of is the set {i | i T}.

[0178] For example, in the case of the relay node 1 shown in FIG. 26 (example in the case where the conversion constraint is special), min (2) = 2, min (3) = 3, min (5) = 1 (j). = 4 is a missing number), T = 3, and S₂ S₃ S₅= {3,4}. At this time, since the sum of the preference vectors from the three children is (1,2,1,2), the relay node 1 has (0,0,0,) with respect to the parent node (server 10 in the figure). Send 1).

[0179] The method of dealing with the conversion constraint based on the cost model described in the first method example has been described above, whereas in the cost model described in the second method example, the function f has been described._kBy setting the values of (i, a (1), a (2), ..., a (c)) as follows, the required conversion constraints can be met.

That is, when a data format that cannot be converted from the data format i is included in a (1), a (2), ..., a (c), f._kBy setting (i, a (1), a (2), ..., a (c)) = (infinity), such (i, a (1), a (2), ..., a (c)) combinations can be excluded. Also, f_kThe values of (i, a (1), a (2), ..., a (c)) can reflect the difference in conversion cost between data formats.

[0181] FIG. 27 is a conversion constraint graph (FIG. 27) that defines restrictions on conversion between data formats in stream data described in the second method example in the data processing relay method applied to the second modification of the present invention. It is a figure which shows the directed graph). The label of each directed branch represents the corresponding data conversion cost.

[0182] Here, when the conversion constraint graph 31 shown in the figure is given, f is the same as in the second method example._k(i, a (1), a (2), ..., a (c)) = g_k(i, a (1)) + g_k(i, a (2)) + ... + g_kConsider the case where it can be decomposed as (i, a (c)), and then g_kIf (i, a (j)) is defined as the label of the directed branch (i, a (j)), then f_k(2,1,1,3) = g_k(2,1) + g_k(2,1) + g_kIt is calculated as (2,3) = 3 + 3 + 2 = 8.

[0183] In this way, by reflecting the conversion cost between each data format in the value of (i, a (1), a (2), ..., a (c)), the multicast cast tree as a whole , It is possible to realize more precise conversion cost minimization.

[0184] According to the above modified example, f as described in the second method example._kIt is also possible to reflect the load status of the node and the available bandwidth of the communication link in the values of (i, a (1), a (2), ..., a (c)).

That is, in order to reflect the load state of the node, the function f is used in the relay node with a heavy load._kBy setting the value of (i, a (1), a (2), ..., a (c)) to be larger than the value of the function of the other relay node, as described in the second method example. In addition, the conversion process in the relay node with a heavy load can be avoided as much as possible.

[0186] Further, in order to reflect the usable bandwidth of the communication link, when the communication link with the parent node is congested, the conversion cost from the data format having a large required bandwidth to another data format is increased. By setting to, it is possible to reduce the possibility that stream data in a data format having a large required band passes through the congested communication link.

[0187] The embodiments of the present invention have been described above with reference to first and second device examples, network system device examples and method examples, and a data processing relay processing program and a recording medium. It is not necessarily limited to the means, methods, procedures and procedures described above, but can be appropriately modified and implemented within the scope of achieving the object of the present invention and having the effects described below.

[0188] For example, in the above description, stream data is given as an example of content data, but this is merely an application example of the present invention, and the present invention relates to any other content data. Is applicable as well.

[Effects of the Invention] As described in detail above, according to the present invention, it becomes possible to efficiently add additional data such as advertisements that match the tastes of each client to the content data. In the process of distributing the content data, it is possible to convert the data format of the content data into a format that can be received by each client. In addition, the required content data is distributed according to the load status of each relay node itself and the relevant. This can be done in consideration of the load status of the communication link of each relay node.

BRIEF DESCRIPTION OF THE DRAWINGS [Fig. 1] Fig. 1 is a block diagram showing an internal configuration of a relay node (data processing relay device) according to a first device example of the present invention.

FIG. 2 is a diagram showing an outline of a request phase in a data processing relay method according to a first method example of the present invention.

FIG. 3 is a diagram showing a specific operation example of a request phase in the data processing relay method according to the first method example of the present invention.

FIG. 4 is a diagram showing a specific operation example of a delivery phase in the data processing relay method according to the first method example of the present invention.

FIG. 5 is a diagram showing an example of cost when a required advertisement data addition / replacement process is executed by a normal method.

FIG. 6 is a diagram showing a cost example when an advertisement data addition / replacement process is executed by the data processing relay method according to the first method example of the present invention.

FIG. 7 is a block diagram showing an internal configuration of a relay node (data processing relay device) according to a second device example of the present invention.

FIG. 8 is a diagram showing an outline of a cost model in a data processing relay method according to a second method example of the present invention.

FIG. 9 is a diagram showing a specific operation example of a request phase in the data processing relay method according to the second method example of the present invention.

FIG. 10 is a diagram showing a specific example of a cost function in the data processing relay method according to the second method example of the present invention.

FIG. 11 is a diagram showing a part of a specific operation example of a request phase in the data processing relay method according to the second method example of the present invention.

FIG. 12 is a diagram showing a calculation example of a cost function in the data processing relay method according to the second method example of the present invention.

FIG. 13 is a diagram showing another part of a specific operation example of the request phase in the data processing relay method according to the second method example of the present invention.

FIG. 14 is a diagram showing a specific operation example of a delivery phase in the data processing relay method according to the second method example of the present invention.

FIG. 15 is a diagram showing a specific operation example of another request phase in the data processing relay method according to the second method example of the present invention.

FIG. 16 is a diagram showing a calculation example of another cost function in the data processing relay method according to the second method example of the present invention.

FIG. 17 is a diagram showing a portion related to the relay node 2 in FIG.

FIG. 18 is a diagram showing a calculation example of the relay node 2 in FIG.

FIG. 19 is a diagram showing a state in which the relay node 2 of FIG. 15 sends a cost vector.

FIG. 20 is a diagram showing a specific operation example of another delivery phase in the data processing relay method according to the second method example of the present invention.

FIG. 21 is a diagram showing a number of viewers-advertising category search table applicable to the data processing relay method according to the second method example of the present invention.

FIG. 22 is a diagram showing a specific operation of a request phase in a data processing relay method applied to a first modification of the present invention.

FIG. 23 is a diagram showing a specific operation of a delivery phase in a data processing relay method applied to the first modification of the present invention.

FIG. 24 is a conversion constraint graph (directed graph) that defines restrictions on conversion between data formats of stream data described in the first method example in the data processing relay method applied to the second modification of the present invention. It is a figure which shows.

FIG. 25 is a diagram showing an example of the relationship between the preference vector transmitted by each relay node or client when the conversion constraint graph shown in FIG. 24 is given, and the stream data delivered corresponding to the preference vector. Is.

FIG. 26 shows special cases of conversion constraints, i.e. i.₁&lt;i₂Then i₂I from the second data format₁The preference vector sent by each relay node or client when there is a constraint that conversion to the second data format is possible, but not the other way around, and the preference vector is delivered. It is a figure which shows an example of the relationship with stream data.

FIG. 27 is a conversion constraint graph (directed graph) that defines restrictions on conversion between data formats of stream data described in the second method example in the data processing relay method applied to the second modification of the present invention. It is a figure which shows.

[Explanation of code] N1, N2, k, 1 ~ 4 ... Relay node 5 ~ 9 ... Client 10 ... Server 11,21 ... Advertising data storage means 12,22 ... Additional advertising instruction Table 13,23 ... Receiving means 14,24 ... Advertising addition / replacement means 15,25 ... Sending means 16 ... Preference extraction means 17 ... Preference information table 18 ... Preference aggregation means 26 ... cost extraction means 27 ... cost information table 28 ... cost aggregation means 29 ... number of viewers-advertising category search table 30,31 ... conversion constraint graph (directed graph)