JP6135078B2 - Information processing method and information processing apparatus for arrival confirmation message - Google Patents

Description

  The present technology relates to a network communication technology in which a communication path between communication nodes is uncertain.

  A network in which data is transmitted and received between mobile terminals and fixed terminals (hereinafter referred to as communication nodes or simply nodes), and data received by each node is stored, transported (only mobile terminals), and transferred Has been devised. In this way, a network that does not always have a communication path between a source node and a destination node, that is, a network that can transfer data even in a communication environment in which the communication path is indeterminate, is a delay tolerant network ( It is called Delay Tolerant Network (DTN) or Disruption-Tolerant Network (DTN).

  In DTN, it takes a long time to transfer end-to-end data from a source node to a destination node, and it may include a poor communication environment such as frequent packet loss and communication line disconnection. Even in such a communication environment, efficient data transfer is required.

  In DTN, a mobile node that can move or a fixed node that cannot move moves data from the source node to the destination node by repeating data transfer. Specifically, when a node that receives data is not near a transfer destination node, the node temporarily stores the received data in its own storage area. Thereafter, the data is transferred when another node comes close by the movement of the own node or another node. In this way, data transfer is possible even in a communication environment in which an end-to-end communication path does not always exist.

  A node on the DTN temporarily stores data received from another node as a cache in its own storage area (hard disk drive, memory, etc.) in order to transfer data. However, the capacity of the storage area of the node is limited, and it is preferable to erase the cache of data that has reached the destination node in order to store and transfer data newly generated from the transmission source node. Therefore, it is preferable that the destination node of data transmits an arrival confirmation message, that is, an ACK message on the DTN in order to notify the arrival of data to the transmission source node and the forwarding node. On the other hand, if an ACK message is transmitted every time data reaches the destination node, a large amount of ACK messages are propagated on the DTN. This is not preferable in terms of communication efficiency.

  As shown in FIG. 1, in a normal communication environment such as the Internet, when transmitting data from the left end server to the right end server, the left end server transmits a packet including the data with a sequence number. . In such a network, it is unlikely that packets will be lost or greatly delayed in the middle, so the rightmost server will receive an ACK containing the largest sequence number among the sequence numbers assigned to consecutively received packets. Send the packet to the leftmost server. For example, if the maximum sequence number is “4”, an ACK packet including “4” is transmitted. When receiving the ACK packet, the leftmost server discards the packet data for the sequence number equal to or less than the sequence number included in the ACK packet. In the case of an ACK packet including the sequence number “4”, the data related to the sequence numbers 0 to 4 is discarded.

  In DTN, there are cases where packets are lost or greatly delayed in the middle of the process, so such a technique may not be able to continuously receive packets. For example, a packet with a sequence number such as sequence numbers “0”, “2”, and “4” may be received. Since the sequence numbers of the received packets are not consecutive, the maximum sequence number is “0”, and ACK packets cannot be aggregated.

JP 2011-4333 A JP 2011-172196 A

“DTN: Network to make friends with delay”, Communications Society Magazine No.16 [Spring] 2011 “Current Status and Prospects of DTN Technology”, Communications Society Magazine No.16 [Spring] 2011 Wing Ho Yuen, et. Al, "IMPROVING SEARCH EFFICIENCY USING BLOOM FILTER IN PARTIALLY CONNECTED AD HOC NETWORKS, A NODE-CENTRIC ANALYSIS", Global Telecommunications Conference, 2006. GLOBECOM '06. IEEE

  Therefore, an object of the present technology is to provide a technology for efficiently transmitting an arrival confirmation message in a network in which a communication path between communication nodes is indefinite.

  An arrival confirmation message transmission method according to the first aspect of the present technology includes (A) a method for confirming whether a set of identifiers of data received from a certain source node is included in the set. A process of mapping to a bit string; and (B) a process of transmitting an arrival confirmation message including data defining the range of identifiers included in the set and the bit string to a certain source node.

  In the data deletion method according to the second aspect of the present technology, (C) data defining a set range of identifiers of data received from a certain transmission source node, and whether or not the identifiers are included in the set. From the data included in the arrival confirmation message, the process of receiving the arrival confirmation message including the bit string for confirmation, and (D) the data storage unit that stores the data about the source node and the identifier of the data. A process of extracting an identifier included in a specified range; (E) a process of determining whether the extracted identifier is included in the set based on the bit string; and (F) an included in the set. And the process of deleting the data about the identifier determined to have been deleted from the data storage unit.

  An arrival confirmation message can be efficiently transmitted in a network in which a communication path between communication nodes is uncertain.

FIG. 1 is a diagram for explaining transmission of an ACK message in a normal network. FIG. 2 is a diagram schematically showing a state of data packet transmission in DTN. FIG. 3 is a diagram schematically showing a state of transmission of an ACK packet in DTN. FIG. 4 is a diagram illustrating an overview of the embodiment of the present technology. FIG. 5 is a functional block diagram of a node that functions as a transmission source node. FIG. 6 is a functional block diagram of a node that functions as a forwarding node. FIG. 7 is a functional block diagram of a node that functions as a destination node. FIG. 8 is a diagram illustrating a processing flow of processing executed by the receiving unit of the destination node. FIG. 9 is a diagram illustrating an example of data stored in the data storage unit of the destination node. FIG. 10 is a diagram illustrating a processing flow of processing executed in the destination node. FIG. 11 is a diagram illustrating a processing flow of the first preprocessing. FIG. 12 is a diagram illustrating a processing flow of the second preprocessing. FIG. 13 is a diagram for explaining the Bloom filter. FIG. 14 is a diagram for explaining the Bloom filter. FIG. 15 is a diagram illustrating a processing flow of an erroneous detection verification process. FIG. 16 is a diagram for explaining the false detection verification process. FIG. 17 is a diagram illustrating a configuration example of an ACK packet. FIG. 18 is a diagram illustrating an example of data stored in the forwarding node and the transmission source node. FIG. 19 is a diagram illustrating a processing flow of processing when an ACK packet is received at a forwarding node and a transmission source node. FIG. 20 is a diagram illustrating a processing flow of processing when an ACK packet is received at a forwarding node and a transmission source node. FIG. 21 is a functional block diagram of an information processing apparatus that is a node.

  FIG. 2 is a diagram illustrating a state of transmission of a data packet (or data message) in DTN. In the example of FIG. 2, data is transmitted from the fixed transmission source node 1001 shown at the left end to the fixed destination node 1007 shown at the right end. In this example, when the movable transfer node 1002 approaches the transmission source node 1001, the transmission source node 1001 transmits a data packet to the transfer node 1002, and the transfer node 1002 receives the data packet and caches it. To accumulate. If there is no other forwarding node in the vicinity of the forwarding node 1002, the data packet is not forwarded. For example, when the forwarding node 1002 moves and a fixed forwarding node 1003 or a movable forwarding node 1005 is in the vicinity, The forwarding node 1002 forwards the data packet stored in the cache. The forwarding node 1003 caches the received data packet, and when the movable forwarding node 1004 approaches, forwards the data packet in the cache to the forwarding node 1004. When the forwarding node 1005 receives a data packet from the forwarding node 1002, the forwarding node 1005 caches and moves the data packet. When the forwarding node 1005 comes close to the extent that it can communicate with the destination node 1007, the forwarding node 1005 transmits the cached data packet to the destination node 1007. In this way, the data packet is transferred from the source node 1001 to the destination node 1007.

  FIG. 3 is a diagram illustrating a state of transmission of an ACK packet (or ACK message) in DTN. Basically, an ACK packet is transmitted to the source node 1001 in the reverse direction of FIG. 2, but the same node is not necessarily used. The destination node 1007 transmits an ACK packet, which will be described in detail below, to the movable forwarding node 1005 existing in the neighborhood at that time. The forwarding node 1005 executes processing for deleting data from the cache based on the data included in the ACK packet as described below. Further, the forwarding node 1005 moves to come near the fixed forwarding node 1003 or the movable forwarding node 1103. Then, forwarding node 1005 transmits an ACK packet to forwarding nodes 1003 and 1103.

  When receiving the ACK packet, the forwarding node 1003 executes a process of deleting data from the cache based on the data included in the ACK packet as described below. When the movable transfer node 1102 approaches, the transfer node 1003 transfers the ACK packet to the transfer node 1102. Further, the forwarding node 1103 starts moving after receiving the ACK packet. When the forwarding node 1103 approaches the transmission source node 1001 and becomes communicable, the forwarding node 1103 forwards the ACK packet. Then, the transmission source node 1001 also executes a process of deleting data from the cache based on the data included in the ACK packet as described below.

  By performing such processing between various nodes, data communication is performed on the DTN. In the embodiment, for simplification of description, the source node, the forwarding node, and the destination node are distinguished from each other. However, any node functions as the source node, the forwarding node, or the destination node.

  In the present embodiment, as schematically shown in FIG. 4, the data packets with sequential identification numbers “0” to “9” are transmitted from the leftmost source node to the rightmost destination node. This is effective when the destination node can receive only the data packets having the identification numbers “0”, “2”, and “4”. That is, in this case, an ACK indicating that a data packet having identification numbers “0”, “2”, and “4” has been received and a bit string for confirming which identification packet has been received is added. The destination node transmits the packet to the source node. This makes it possible to confirm which data packet can be discarded at the transfer node and the transmission source node on the transfer path of the ACK packet.

  Hereinafter, a configuration of a node included in the DTN and a process executed by the node will be described in the present embodiment.

  FIG. 5 shows a functional block diagram of the node 100 functioning as a transmission source node. The transmission source node 100 includes a communication interface 101, a transmission unit 102, a reception unit 103, a data generation unit 104, an ID generation unit 105, a data deletion processing unit 106, and a data storage unit 107.

  The communication interface 101 is a module that performs wireless communication processing, for example. The data generation unit 104 generates data to be transmitted to other nodes. The generated data is, for example, output data of a sensor such as a position sensor, processing log data, or the like.

  The transmission unit 102 generates a packet from the data to be transmitted to other nodes generated by the data generation unit 104 and transmits the packet via the communication interface 101. For example, in cooperation with the transmission unit 102, the ID generation unit 105 sequentially generates a sequential identification number that is an identifier (ID) of a packet to be transmitted for each destination node identifier, and outputs the sequential identification number to the transmission unit 102. The transmission unit 102 stores the transmitted data in the data storage unit 107 in association with the identifier and identification number of the destination node. Note that the data generation unit 104 may generate an identification number for each identifier of the destination node in cooperation with the ID generation unit 105 and store it in the data storage unit 107 together with the data.

  The receiving unit 103 receives a packet from another node via the communication interface 101, stores the packet in the data storage unit 107, and executes processing to the data deletion processing unit 106 when an ACK packet is received as described below. Let The data deletion processing unit 106 uses the data included in the ACK packet received by the reception unit 103 to identify and delete data that can be deleted from the data stored in the data storage unit 107.

  FIG. 6 shows a functional block diagram of the node 200 that functions as a forwarding node. The transfer node 200 includes a communication interface 201, a transmission unit 202, a reception unit 203, a transfer processing unit 204, a data deletion processing unit 205, and a data storage unit 206.

  The communication interface 201 is a module that performs wireless communication processing, for example. The transmission unit 202 transmits the data packet stored in the data storage unit 206 to another node in response to an instruction from the transfer processing unit 204. When receiving the data packet and the ACK packet from another node, the receiving unit 203 stores the data packet and the ACK packet in the data storage unit 206. The data packet is managed in the data storage unit 206 in association with the identifier and identification number of the destination node. The ACK packet is deleted if transferred.

  When the transfer processing unit 204 detects that another node is close via the communication interface 201, the transfer processing unit 204 causes the transmission unit 202 to transmit the data packet and the ACK packet stored in the data storage unit 206. The data deletion processing unit 205 uses the data included in the ACK packet received by the reception unit 203 to identify and delete data that can be deleted from the data stored in the data storage unit 206. The data deletion processing unit 106 in the transmission source node 100 and the data deletion processing unit 205 in the forwarding node 200 perform similar processing.

  FIG. 7 is a functional block diagram of the node 300 that functions as a destination node. The destination node 300 includes a communication interface 301, a transmission unit 302, a reception unit 303, a bit string generation unit 304, a verification processing unit 305, and a data storage unit 306.

  The communication interface 301 is a module that performs wireless communication processing, for example. The transmission unit 302 transmits an ACK packet or the like via the communication interface 301. The receiving unit 303 receives the data packet via the communication interface 301 and stores it in the data storage unit 306.

  The bit string generation unit 304 generates a bit string for confirming whether or not the identification number of the received data packet is used when generating the bit string for each transmission source node. In addition, the verification processing unit 305 executes verification processing of the bit string generated by the bit string generation unit 304.

  Next, processing in the destination node 300 will be described with reference to FIGS. The receiving unit 303 of the destination node 300 waits for reception of the data packet (FIG. 8: Step S1), and when receiving the data packet, stores the data portion of the data packet in the data storage unit 306 (Step S2). In addition, the reception unit 303 identifies the identifier of the transmission source node of the data packet from the data packet (step S3).

  Then, the reception unit 303 increments the counter of the number of unprocessed packets of the transmission source node by 1 (step S5), extracts the data identifier included in the data packet, and stores it in the data storage unit 306 (step S6). ). For example, data as shown in FIG. 9 is stored in the data storage unit 306 for each transmission source node. In the example of FIG. 9, a counter value of the number of unprocessed packets and an unprocessed identification number group are stored.

  Such a process is repeated until the process ends due to, for example, an end instruction from the user (step S7).

  In contrast, processing executed by the bit string generation unit 304, the verification processing unit 305, and the transmission unit 302 will be described with reference to FIGS.

  The bit string generation unit 304 selects one transmission source node, for example, in a round robin manner from among the transmission source nodes whose data is stored in the data storage unit 306 (FIG. 10: step S11). Then, the bit string generation unit 304 determines whether or not the counter value of the number of unprocessed packets stored in the data storage unit 306 for the selected transmission source node is greater than or equal to the threshold (step S13). This is because the number of data packets equal to or greater than the threshold is received, aggregated and transmitted as an ACK packet.

  If the counter value of the number of unprocessed packets is not equal to or greater than the threshold for the selected transmission source node, the process returns to step S11. On the other hand, if the counter value of the number of unprocessed packets for the selected transmission source node is greater than or equal to the threshold value, the bit string generation unit 304 performs preprocessing (step S15). The preprocessing will be described with reference to FIGS. In the present embodiment, the preprocessing is executed in order to improve the processing efficiency of a false detection verification process that is executed later.

  First, the bit string generation unit 304 sets the identification numbers of unprocessed packets stored in the data storage unit 306 in the set S (FIG. 11: step S31). Then, the bit string generation unit 304 calculates the ratio of the number of identification numbers included in the set S to the range of identification numbers included in the set S (step S33). If the set S includes the identification numbers {1, 3, 5, 9, 11}, the range of the identification numbers is 10 (= 11-1), and the number of the identification numbers included in the set S is 5. Therefore, the ratio is 50% (= 5/10).

  Then, the bit string generation unit 304 determines whether the calculated ratio exceeds the threshold value (step S35). The threshold value is a predetermined numerical value of 50% or more, for example. In the erroneous detection verification process executed later, whether or not erroneous detection is performed for (100% -calculated ratio) number of identification numbers is verified, so that the identification numbers included in the range of identification numbers included in the set S This is because the majority of these are subject to false detection verification processing.

  When the calculated ratio does not exceed the threshold value, the bit string generation unit 304 excludes the identification number maximum value from the set S (step S37). Then, the process returns to step S33.

  On the other hand, when the calculated ratio exceeds the threshold value, the bit string generation unit 304 sets the identification number included in the set S to the identification number of the bit string generation target (step S39). Then, the process returns to the caller process.

  This pre-processing may be changed to the processing shown in FIG. 12, for example. The bit string generation unit 304 sets the identification number of the unprocessed packet stored in the data storage unit 306 to the set (step S41). Then, the bit string generation unit 304 selects one unprocessed set (step S43).

  After that, the bit string generation unit 304 calculates the number of identification numbers included in the selected set with respect to the range of identification numbers included in the selected set (step S45). The calculation contents are the same as in step S33.

  Then, the bit string generation unit 304 determines whether the calculated ratio exceeds the threshold (step S47). When the calculated ratio does not exceed the threshold value, the bit string generation unit 304 divides the selected set at a portion where the interval between the identification numbers included in the selected set is maximized (step S49). . Then, the process returns to step S43. In addition, you may make it remove | exclude from the process object about the set with too few the identification numbers included among the sets produced | generated by the division | segmentation.

  On the other hand, when the calculated ratio exceeds the threshold, the bit string generation unit 304 sets an identification number included in the selected set as a bit string generation target (step S51). Then, the bit string generation unit 304 determines whether there is an unprocessed set (step S53). If there is an unprocessed set, the process returns to step S43. On the other hand, if there is no unprocessed set, the process returns to the caller process.

  According to this pre-processing, there are a plurality of sets of identification numbers to be subjected to bit string generation, and therefore the following processing is executed for each set.

  Returning to the description of the processing in FIG. 10, the bit string generation unit 304 generates a bit string for confirming whether an arbitrary identification number is included in the set of bit string generation targets (step S <b> 17). In the present embodiment, a stochastic data structure, specifically, a Bloom filter is employed as the bit string.

  Bloom filters are well known, but will be briefly described with reference to FIGS. In order to generate a Bloom filter, as shown in FIG. 13, k hash functions are prepared, and an identification number is input to each to obtain a hash value. In the example of FIG. 13, the hash value “8” is generated from the hash function 1, the hash value “1” is generated from the hash function 2, and the hash value “11” is generated from the hash function k. To do. Then, in the m-bit array, the bit at the position of the hash value is set to “1”. In the example of FIG. 13, the “8” bit, the “1” bit, and the “11” bit are set to “1”. The bit string generated in this way is a Bloom filter. The k hash functions are common in DTN.

  Further, as shown in FIG. 14, other identification numbers included in the set of bit string generation targets are also input to k hash functions, respectively, to obtain hash values. In the example of FIG. 14, it is assumed that the hash value “0” is generated from the hash function 1, the hash value “1” is generated from the hash function 2, and the hash value “8” is generated from the hash function k. Then, the bit of the hash value position is set to “1” in the m-bit array of the Bloom filter generated in FIG. In the example of FIG. 14, “1” is set to the “0” bit, the “1” bit, and the “8” bit. However, since the “1” and “8” bits are already set to “1”, there is no change. In this way, bit operations for a plurality of identification numbers are performed repeatedly on the same m-bit array.

  Returning to the description of the processing in FIG. 10, the bit string generated by the bit string generation unit 304 in this way is output to the verification processing unit 305, and the verification processing unit 305 executes a false detection verification process (step S19). The erroneous detection verification process will be described with reference to FIGS. 15 and 16.

  The verification processing unit 305 identifies one unprocessed identification number among the specific identification numbers that are included in the range of identification numbers used for bit string generation and not used for bit string generation (FIG. 15: step S61). When the identification number {1, 3, 5, 9, 11} is used for bit string generation, {2, 4, 6, 7, 8, 10} is the specific identification number in the range of identification numbers 1 to 11. Become.

  And the verification process part 305 determines the presence or absence of the false detection of a Bloom filter (step S63). Bloom filters are known to cause false detection due to their nature. If this false detection is allowed, data packets to be retransmitted are deleted at the transfer node and the transmission source node on the communication path. End up. Therefore, it is verified here whether or not erroneous detection occurs.

  For example, as shown in FIG. 16, the specific identification number is input to the same k hash functions as when the Bloom filter is generated, and the hash value is acquired. If the values of the bit positions indicated by the hash values are all “1”, the specific identification number is included in the set at the time of generating the Bloom filter, so it is determined that it is a false detection. In the example of FIG. 16, the hash value of the hash function 1 is “3”, the hash value of the hash function 2 is “10”, the hash value of the hash function k is “4”, Since the bit values are all “1”, it is determined that there is a false detection. On the other hand, if even one bit position value indicated by the hash value is “0”, it is determined that there is no false detection.

  When it is determined that there is an erroneous detection as a result of step S63 (step S65: Yes route), an erroneous detection is output to the bit string generation unit 304 (step S67). Then, the process returns to the caller process. On the other hand, if no false detection is detected as a result of step S63 (step S65: No route), the verification processing unit 305 determines whether an unprocessed identification number exists in the specific identification number (step S69). If there is an unprocessed identification number, the process returns to step S61. On the other hand, if there is no unprocessed identification number, it means that there is no false detection for the generated Bloom filter, so the verification processing unit 305 outputs no false detection to the bit string generation unit 304 (step S71). ). Then, the process ends.

  By executing such processing, it is determined whether or not the generated bit string, that is, the Bloom filter can be used as it is.

  Returning to the description of the processing of FIG. 10, the bit string generation unit 304 determines whether or not there is a false detection based on the output from the verification processing unit 305 (step S <b> 21). If there is a false detection, the bit string generation unit 304 adjusts the identification number of the bit string generation target (step S29).

  Various methods can be used for adjusting the identification number. However, since it is unclear directly which identification number is removed from the bit string generation target, it is unknown (A) a method of deleting the largest identification number among the identification numbers of the bit string generation target, and (B) bit string generation. A method of deleting an identification number whose range of identification numbers of a bit string generation target is narrowed when excluded from among a minimum identification number and a maximum identification number of target identification numbers; For example, a method of calculating the interval and deleting the rear identification number from the widest portion may be employed.

  Thereafter, the process returns to step S17 to generate a bit string again, and then performs a false detection verification process.

  On the other hand, if there is no false detection, the bit string generation unit 304 defines the range of the generated bit string and the identification number of the bit string generation target (for example, a combination of a head identification number and a tail identification number. An ACK packet including a combination of a number and an offset value up to the end identification number) is generated and transmitted to the transmission unit 302 (step S23).

  For example, a data configuration example of an ACK packet as shown in FIG. 17 is shown. In the example of FIG. 17, arrival confirmation (ACK) is specified as the packet type, and includes an identifier of a transmission source node, a head identification number, a tail identification number, and a Bloom filter that is a bit string.

  Then, the bit string generation unit 304 determines whether or not to end the process due to an instruction to end the process (step S25). If the processing is not finished, the bit string generation unit 304 decrements the counter value of the number of unprocessed packets by the number of identifiers used for bit string generation in the data storage unit 306 for the transmission source node for processing, The identification number of the bit string generation target is deleted (step S27). Then, the process returns to step S11.

  By executing the processing as described above, it is possible to generate and transmit one ACK packet in which ACK packets of a large number of data packets are aggregated while guaranteeing that there is no erroneous detection of the identification number. That is, communication efficiency is improved.

  Next, processing when an ACK packet is received at the forwarding node and the transmission source node will be described with reference to FIGS. In the transmission source node and the forwarding node, it is assumed that data as shown in FIG. 18 is stored in the data storage unit. In the example of FIG. 18, it is assumed that not only the data of the data packet but also an unprocessed identification number group is held for each transmission source node (for the transmission source node only for the own node). Here, the forwarding node 200 will be described as an example, but the data deletion processing unit 106 executes the same processing for the transmission source node 100 as well.

  First, the data deletion processing unit 205 of the forwarding node 200 stands by until an ACK packet is received from the receiving unit 203 (FIG. 19: Step S81). When receiving the ACK packet, the data deletion processing unit 205 extracts the identifier of the data transmission source node, the head and tail identification numbers, and the bit string from the ACK packet (step S83).

  Further, the data deletion processing unit 205 extracts the identification number of the unprocessed packet stored in the data storage unit 206 for the extracted identifier of the transmission source node (step S85). Data as shown in FIG. 18 is read.

  Thereafter, the data deletion processing unit 205 selects one unprocessed identification number from the extracted identification numbers (step S87). Then, the data deletion processing unit 205 performs inclusion determination of the selected identification number based on the bit string included in the ACK packet (step S89). In the case of the Bloom filter, if all the bit position values indicated by the hash values of the k hash functions are “1”, it can be confirmed that they are included in the set of identification numbers at the time of generating the Bloom filter. Therefore, also in this step, the selected identification number is input to the k hash functions to obtain the hash value, the value of the bit position indicated by the hash value is confirmed, and all the bit values are “1”. If there is, it is determined as inclusion. Then, the processing shifts to the processing in FIG.

  Shifting to the description of the processing in FIG. 20, the data deletion processing unit 205 determines whether or not it is determined that the selected identification number is included (step S91). If it is determined that it is not included, the process proceeds to step S95. On the other hand, if it is determined that the data is included, the data deletion processing unit 205 deletes the data of the packet having the selected identification number in the data storage unit 206 (step S93). The cache capacity can be effectively utilized as much as the arrival confirmation is completed.

  Then, the data deletion processing unit 205 determines whether there is an unprocessed identification number (step S95). If there is an unprocessed identification number, the process returns to step S87 via the terminal B. On the other hand, if there is no unprocessed identification number, the above-described processing is repeated until the processing end is explicitly instructed (step S87). That is, if the process is not finished, the process returns to step S81 via the terminal C.

  By performing the processing as described above, it is possible to discard the held data packet after confirming that the data packet has arrived at the destination node. As a result, the cache can be used effectively.

  In the embodiment described above, an example in which a Bloom filter is used as a bit string has been described. By using the Bloom filter, a large number of data packets can be aggregated. However, due to the nature of the Bloom filter, erroneous detection prevention processing is performed. For example, when data packets corresponding to the bit length of a bit string that can be included in an ACK packet are aggregated, the Bloom filter may not be used.

  For example, if the bit length is m bits, a maximum of m data packets can be aggregated. For example, if the head identification number is “11”, the tail identification number is “23”, and the identification number of the bit string generation target is {11, 13, 15, 17, 19, 21, 23}, the head for each identification number. A bit string “1010101010101” in which the bit position corresponding to the offset position from the identification number is set to “1” may be adopted. That is, the bit string generation process is performed with a predetermined length for confirming whether or not the bit string generation target identification number is included in the bit string generation target set by the bit value of the bit position corresponding to the offset position from the head identification number. To a bit string of. Even when the Bloom filter is used, it can be said that the bit string generation target identification number is mapped to the bit string corresponding to the Bloom filter.

  In this case, the erroneous detection verification process and the process of adjusting the identification number of the bit string generation target need not be performed. In addition, regarding the forwarding node and the transmission source node, the inclusion determination can be performed only by checking whether the bit position in the bit string is “1”, so that the processing becomes simple.

  Although the embodiment of the present technology has been described above, the present technology is not limited to this. For example, the functional block diagram may not match the program module configuration. The data structure example is merely an example, and other data structures that hold the same contents may be adopted.

  Furthermore, as for the processing flow, as long as the processing result does not change, the order of the processing steps may be changed, or the processing may be executed in parallel.

  The transmission source node 100, forwarding node 200, and destination node 300 described above are computer devices, and as shown in FIG. 21, a memory 2501, a CPU (Central Processing Unit) 2503, and a hard disk drive (HDD: HDD). Hard Disk Drive) 2505, a display control unit 2507 connected to the display device 2509, a drive device 2513 for the removable disk 2511, an input device 2515, and a communication control unit 2517 for connecting to the network are connected via a bus 2519. Yes. An operating system (OS) and an application program for executing the processing in this embodiment are stored in the HDD 2505, and are read from the HDD 2505 to the memory 2501 when executed by the CPU 2503. The CPU 2503 controls the display control unit 2507, the communication control unit 2517, and the drive device 2513 according to the processing content of the application program, and performs a predetermined operation. Further, data in the middle of processing is mainly stored in the memory 2501, but may be stored in the HDD 2505. In an embodiment of the present technology, an application program for performing the above-described processing is stored in a computer-readable removable disk 2511 and distributed, and installed from the drive device 2513 to the HDD 2505. In some cases, the HDD 2505 may be installed via a network such as the Internet and the communication control unit 2517. Such a computer apparatus realizes various functions as described above by organically cooperating hardware such as the CPU 2503 and the memory 2501 described above and programs such as the OS and application programs. .

  The above-described embodiment can be summarized as follows.

  In the arrival confirmation message transmission method according to the first aspect of the present embodiment, (A) a set of identifiers of data received from a certain transmission source node is confirmed whether or not the identifiers are included in the set. And (B) a process of transmitting an arrival confirmation message including data defining the range of identifiers included in the set and the bit string to a certain source node.

  In this way, arrival confirmation messages can be aggregated, and communication efficiency can be improved. The message may be a message or packet at any hierarchical level.

  Further, the bit string described above may be a stochastic data structure. Whether or not the above-described mapping process includes (a1) an identifier included in the identifier range but not included in the set based on the bit string. (A2) If an identifier included in the identifier range but not included in the set is to be included in the set, the identifier included in the set is And processing for regenerating the bit string after the reduction. More data messages or data packets can be aggregated.

  In addition, the mapping process described above includes (a3) the verification process and the re-generation process, and identifiers that are included in the identifier range but not included in the set in the verification process. You may make it further include the process repeated until it is determined that it is not included in the set.

  The mapping process described above is included in the set such that the ratio of the number of identifiers included in the set to the number of identifiers included in the range of identifiers included in the set is equal to or greater than a certain value. You may make it include the process which specifies an identifier. For example, this is for increasing the communication efficiency by setting the degree of aggregation to a certain level or more and improving the efficiency of the verification process.

  Further, the above-described specifying process is a process in which the last identifier among the identifiers included in the identifier range is deleted, or a portion where the maximum interval occurs among the identifier intervals included in the identifier range. The process of dividing the set may be included.

  Further, the re-generation process described above is a process for deleting the last identifier among the identifiers included in the identifier range, and a new one when the first identifier is deleted among the identifiers included in the identifier range. An identifier that generates a narrow range between the first range of identifiers included in the set and the second range of identifiers included in the new set when the last identifier is deleted among the identifiers included in the range of the identifiers Or a process of deleting identifiers after the widest interval among identifier intervals included in the identifier range.

  In the data deletion method according to the second aspect of the present technology, (C) data defining a set range of identifiers of data received from a certain transmission source node, and whether or not the identifiers are included in the set. From the data included in the arrival confirmation message, the process of receiving the arrival confirmation message including the bit string for confirmation, and (D) the data storage unit that stores the data about the source node and the identifier of the data. A process of extracting an identifier included in a specified range; (E) a process of determining whether the extracted identifier is included in the set based on the bit string; and (F) an included in the set. And the process of deleting the data about the identifier determined to have been deleted from the data storage unit.

  In this way, the capacity of the data storage unit can be used effectively.

  A program for causing a computer to perform the above-described processing can be created. The program is, for example, a computer-readable storage medium or storage device such as a flexible disk, a CD-ROM, a magneto-optical disk, a semiconductor memory, or a hard disk. Stored in The intermediate processing result is temporarily stored in a storage device such as a main memory.

  The following supplementary notes are further disclosed with respect to the embodiments including the above examples.

(Appendix 1)
A set of identifiers of data received from a source node is mapped to a bit string for confirming whether the identifier is included in the set;
A program for causing a computer to execute processing for transmitting an arrival confirmation message including data defining a range of identifiers included in the set and the bit string to the certain transmission source node.

(Appendix 2)
The bit sequence is a stochastic data structure;
The process of mapping is
A process for verifying whether an identifier that is included in the identifier range but not included in the set is to be included in the set based on the bit string;
If an identifier included in the identifier range but not included in the set is to be included in the set, the identifier included in the set is reduced and the bit string is generated. Process to fix,
The program according to appendix 1, including

(Appendix 3)
The process of mapping is
The verification process and the re-generation process until it is determined that an identifier included in the identifier range but not included in the set is included in the set in the verification process. The program according to appendix 2, further including a repetition process.

(Appendix 4)
The process of mapping is
Additional remarks 1 to 3 including a process of identifying an identifier included in the set such that a ratio of the number of identifiers included in the set to a number of identifiers included in a range of identifiers included in the set is a predetermined value or more. The program according to any one of the above.

(Appendix 5)
The identifying process is
Supplementary note 4 including a process of deleting the last identifier among the identifiers included in the identifier range, or a process of dividing the set at a portion where the maximum interval occurs among the intervals of the identifiers included in the identifier range The listed program.

(Appendix 6)
The regenerating process is
A process of deleting the last identifier among the identifiers included in the identifier range, a first range of identifiers included in a new set when the first identifier is deleted among the identifiers included in the identifier range; and A process of deleting an identifier that causes a narrow range from the second range of identifiers included in the new set when the last identifier is deleted among the identifiers included in the range of identifiers, or in the range of the identifiers The program according to appendix 2, including a process of deleting identifiers after the widest interval among the included identifier intervals.

(Appendix 7)
Receiving an arrival confirmation message including data defining a range of a set of identifiers of data received from a source node, and a bit string for confirming whether or not the identifier is included in the set;
From the data storage unit that stores the data about the certain source node and the identifier of the data, the identifier included in the range specified from the data included in the arrival confirmation message,
Based on the bit string, determine whether the extracted identifier is included in the set;
A program for causing a computer to execute processing for deleting an identifier determined to be included in the set and data about the identifier from the data storage unit.

(Appendix 8)
A set of identifiers of data received from a source node is mapped to a bit string for confirming whether the identifier is included in the set;
An arrival confirmation message transmission method in which a computer executes a process of transmitting an arrival confirmation message including data defining a range of identifiers included in the set and the bit string to the certain source node.

(Appendix 9)
Receiving an arrival confirmation message including data defining a range of a set of identifiers of data received from a source node, and a bit string for confirming whether or not the identifier is included in the set;
From the data storage unit that stores the data about the certain source node and the identifier of the data, the identifier included in the range specified from the data included in the arrival confirmation message,
Based on the bit string, determine whether the extracted identifier is included in the set;
A data deletion method in which a computer executes a process of deleting an identifier determined to be included in the set and data about the identifier from the data storage unit.

(Appendix 10)
A bit string generation unit that maps a set of identifiers of data received from a source node to a bit string for confirming whether or not the identifiers are included in the set;
A transmission unit for transmitting an arrival confirmation message including data defining the range of identifiers included in the set and the bit string to the certain source node;
An information processing apparatus.

(Appendix 11)
A receiver for receiving an arrival confirmation message including data defining a range of a set of identifiers of data received from a source node and a bit string for confirming whether or not the identifier is included in the set; ,
An identifier included in a range specified from the data included in the arrival confirmation message is extracted from a data storage unit that stores data about the certain source node and an identifier of the data, and is extracted based on the bit string Determining whether or not the identifier is included in the set, and deleting the identifier determined to be included in the set and the data about the identifier from the data storage unit;
An information processing apparatus.

100 transmission source node 101 communication interface 102 transmission unit 103 reception unit 104 data generation unit 105 ID generation unit 106 data deletion processing unit 107 data storage unit 200 transfer node 201 communication interface 202 transmission unit 203 reception unit 204 transfer processing unit 205 data deletion process Unit 206 data storage unit 300 destination node 301 communication interface 302 transmission unit 303 reception unit 304 bit string generation unit 305 verification processing unit 306 data storage unit

Claims (11)

A set of identifiers of data received from a source node is mapped to a bit string for confirming whether the identifier is included in the set;
A program for causing a computer to execute a process of transmitting an arrival confirmation message including data specifying a range of identifiers included in the set and the bit string to the certain source node,
The bit sequence is a stochastic data structure;
The process of mapping is
A process for verifying whether an identifier that is included in the identifier range but not included in the set is to be included in the set based on the bit string;
If an identifier included in the identifier range but not included in the set is to be included in the set, the identifier included in the set is reduced and the bit string is generated. Process to fix,
Including programs. The process of mapping is
The verification process and the re-generation process until it is determined that an identifier included in the identifier range but not included in the set is included in the set in the verification process. The program according to claim 1, further comprising: repetitive processing. A set of identifiers of data received from a source node is mapped to a bit string for confirming whether the identifier is included in the set;
A program for causing a computer to execute a process of transmitting an arrival confirmation message including data specifying a range of identifiers included in the set and the bit string to the certain source node,
The bit sequence is a stochastic data structure;
The process of mapping is
A process of specifying an identifier included in the set such that a ratio of the number of identifiers included in the set to a number of identifiers included in a range of identifiers included in the set is a certain value or more ;
A program for verifying whether or not an identifier included in the identifier range but not included in the set is to be included in the set based on the bit string . The identifying process is
Process of removing the last identifier of the identifier included in the aggregate, or claim 3, wherein the program including a process of dividing the set in a portion where the maximum interval occurs within interval identifier included in the set . A set of identifiers of data received from a source node is mapped to a bit string for confirming whether the identifier is included in the set;
A program for causing a computer to execute a process of transmitting an arrival confirmation message including data specifying a range of identifiers included in the set and the bit string to the certain source node,
The bit sequence is a stochastic data structure;
The process of mapping is
A process for verifying whether an identifier that is included in the identifier range but not included in the set is to be included in the set based on the bit string;
If an identifier included in the identifier range but not included in the set is to be included in the set, the identifier included in the set is reduced and the bit string is generated. Process to fix,
Including
The regenerating process is
Included in the last process of deleting the identifier, the set with the first range of identifiers contained in the new set in the case where removing the leading identifier of the identifier included in the set of identifiers included in the set A process of deleting an identifier that causes a narrow range from the second range of identifiers included in the new set when the last identifier is deleted, or the most of the intervals of identifiers included in the set A program that includes processing to delete identifiers after a wide interval. A set of identifiers of data received from a source node is mapped to a bit string for confirming whether the identifier is included in the set;
An arrival confirmation message transmitting method in which a computer executes a process of transmitting an arrival confirmation message including data defining the range of identifiers included in the set and the bit string to the certain source node,
The bit sequence is a stochastic data structure;
The process of mapping is
A process for verifying whether an identifier that is included in the identifier range but not included in the set is to be included in the set based on the bit string;
If an identifier included in the identifier range but not included in the set is to be included in the set, the identifier included in the set is reduced and the bit string is generated. Process to fix,
Including an arrival confirmation message sending method. A set of identifiers of data received from a source node is mapped to a bit string for confirming whether the identifier is included in the set;
An arrival confirmation message transmitting method in which a computer executes a process of transmitting an arrival confirmation message including data defining the range of identifiers included in the set and the bit string to the certain source node,
The bit sequence is a stochastic data structure;
The process of mapping is
A process of specifying an identifier included in the set such that a ratio of the number of identifiers included in the set to a number of identifiers included in a range of identifiers included in the set is a certain value or more ;
An arrival confirmation message transmission method comprising: verifying whether an identifier included in the identifier range but not included in the set is to be included in the set based on the bit string . A set of identifiers of data received from a source node is mapped to a bit string for confirming whether the identifier is included in the set;
An arrival confirmation message transmitting method in which a computer executes a process of transmitting an arrival confirmation message including data defining the range of identifiers included in the set and the bit string to the certain source node,
The bit sequence is a stochastic data structure;
The process of mapping is
A process for verifying whether an identifier that is included in the identifier range but not included in the set is to be included in the set based on the bit string;
If an identifier included in the identifier range but not included in the set is to be included in the set, the identifier included in the set is reduced and the bit string is generated. Process to fix,
Including
The regenerating process is
Included at the end of process of deleting the identifiers, said it sets a first range of identifiers contained in the new set in the case where removing the leading identifier of the identifier included in the set of identifiers included in the set A process of deleting an identifier that causes a narrow range from the second range of identifiers included in the new set when the last identifier is deleted, or the most of the intervals of identifiers included in the set An arrival confirmation message transmission method that includes processing to delete identifiers after a wide interval. A bit string generation unit that maps a set of identifiers of data received from a source node to a bit string for confirming whether or not the identifiers are included in the set;
A transmission unit for transmitting an arrival confirmation message including data defining the range of identifiers included in the set and the bit string to the certain source node;
An information processing apparatus having
The bit sequence is a stochastic data structure;
The bit string generation unit
Based on the bit string, verify whether or not an identifier that is included in the identifier range but not included in the set is to be included in the set;
If an identifier included in the identifier range but not included in the set is to be included in the set, the identifier included in the set is reduced and the bit string is generated. Fix Information processing device. A bit string generation unit that maps a set of identifiers of data received from a source node to a bit string for confirming whether or not the identifiers are included in the set;
A transmission unit for transmitting an arrival confirmation message including data defining the range of identifiers included in the set and the bit string to the certain source node;
An information processing apparatus having
The bit sequence is a stochastic data structure;
The bit string generation unit
Identifying an identifier included in the set such that a ratio of the number of identifiers included in the set to a number of identifiers included in a range of identifiers included in the set is equal to or greater than a certain value ;
An information processing apparatus that verifies whether an identifier that is included in the identifier range but not included in the set is included in the set based on the bit string . A bit string generation unit that maps a set of identifiers of data received from a source node to a bit string for confirming whether or not the identifiers are included in the set;
A transmission unit for transmitting an arrival confirmation message including data defining the range of identifiers included in the set and the bit string to the certain source node;
An information processing apparatus having
The bit sequence is a stochastic data structure;
The bit string generation unit
A process for verifying whether an identifier that is included in the identifier range but not included in the set is to be included in the set based on the bit string;
If an identifier included in the identifier range but not included in the set is to be included in the set, the identifier included in the set is reduced and the bit string is generated. Perform the correction process,
In the re-generation process, the bit string generation unit,
Included in the last process of deleting the identifier, the set with the first range of identifiers contained in the new set in the case where removing the leading identifier of the identifier included in the set of identifiers included in the set A process of deleting an identifier that causes a narrow range from the second range of identifiers included in the new set when the last identifier is deleted, or the most of the intervals of identifiers included in the set An information processing apparatus that executes processing for deleting identifiers after a wide interval.

Images