Node in network including a plurality of nodes

In a network including a plurality of nodes, a node transmits data to another node, receives data from another node, and stores a communication history between a plurality of other nodes and the node itself. When an acknowledge response to data transmitted to a first node among the plurality of other nodes is not received, the node generates a duplicate data of the transmitted data. When a duplication report indicating detection of duplicate data transmitted to a second node among the plurality of other nodes has been received from one of the plurality of other nodes, the node refers to the communication history, and identifies the first node as a cause of generation of the duplicate data. Thereafter, the node generates a check request that include a communication history between the first node and the node itself and that requests the first node to check the communication history.

FIELD

The embodiments discussed herein are related to a node in a network including a plurality of nodes.

BACKGROUND

In a network having a plurality of options for a packet transfer route such as ad hoc networks, when a failure has occurred while a packet is being relayed on an optimum route that was originally selected, the packet is transferred to an alternative route.

In a communication network as illustrated inFIG. 1for example, when a data packet is to be transferred from a node101to a node105, there are three transfer routes, i.e., routes via nodes102,103, and104, respectively. First, the transfer route via the node102is selected, and when the packet transmission from the node101to the node102has failed, the transfer route via the node103is selected so that the data packet is transferred from the node101to the node103as an indirect transfer.

However, when the packet transmission from the node101to the node103has also failed, the transfer route via the node104is selected so that the data packet is transferred from the node101to the node104as an indirect transfer. When the packet transmission from the node101to the node104has succeeded, the data packet is transmitted from the node104to the node105and the data packet reaches the node105.

As described above, by providing an indirect transfer function to a communication network, the reachability with which data packets reach their transmission destinations can be increased even when the route data does not represent the actual condition of the communication network completely.

However, in some cases, indirect transfer functions worsen situations when there is congestion in networks. In a communication network as illustrated inFIG. 2, for example, when a data packet is to be transferred from the node201to the node206, there is a route via the node205and a route via the nodes203and204between nodes202and206.

When the transfer route via the node205is first selected so that the data packet is transmitted from the node202to the node205, an acknowledge response (Ack) packet211is transmitted in return from the node205to the node202. Thereafter, the data packet is transmitted from the node205to the node206so that the data packet reaches the node206.

When the returning of the Ack packet211is prevented by congestion, the Ack packet211does not reach the node202, and this causes an indirect transfer in which the same data packet is transferred as a duplicate packet212to the transfer route via the nodes203and204. Thereafter, the duplicate packet212is transmitted from the node204to the node206so that the duplicate packet212reaches the node206. No problems arise even when the node206receives the same data packet a plurality of times; however, repeated transmission of many duplicate packets worsens the congestion of the network.

In order to suppress duplication of data packets, methods of transmitting an Ack as described below are proposed.

(1) A Method in which the Transmission of an Ack is Multiplexed

In this method, when a data packet is transmitted from a transmitting node to a receiving node, an Ack packet is transmitted in return from the receiving node to the transmitting node a plurality of times. Thereby, the reachability of an Ack packet increases, suppressing duplication of data packets.

(2) A Method in which Transmission Confirmation of an Ack is Performed

In this method, when a data packet is transmitted from a transmitting node to a receiving node, a first Ack packet is transmitted in return from the receiving node to the transmitting node, and subsequently a second Ack packet, indicating the reception of the first Ack packet, is transmitted in return from the transmitting node to the receiving node. When the receiving node does not receive the second Ack packet, the first Ack packet is retransmitted from the receiving node to the transmitting node. Thereby, the reachability of first Ack packets increases, suppressing duplication of data packets.

(3) A Method in which the Transmission Power of an Ack is Adjusted

In this method, when a data packet is transmitted from a transmitting node to a receiving node, an Ack packet is transmitted in return with increased transmission power from the receiving node to the transmitting node. Thereby, the reachability of first Ack packets increases, suppressing duplication of data packets.

A method is known in which the link quality is evaluated by calculating the transmission success rate between nodes included in a communication network in order to detect congestion in the communication network. However, it is difficult to determine a success and failure of transmission on the basis of measurement in the receiving node alone unless the number of times of transmitting data packets and Ack packets and their transmission timings are known, because they are transmitted unperiodically. Accordingly, the transmission success rate is calculated on the basis of the fluctuation of arrival cycles of Hello packets, which are transmitted periodically.

A case is discussed as an example in which the intervals at which one node receives the first through ninth Hello packets are measured and the measurement results as illustrated inFIG. 3are obtained. In this example, the second and fifth reception intervals are 2T and 3T, respectively, which are longer than other reception intervals. In such a case, it can be estimated that missing Hello packets due to transmission failures have elongated the reception intervals, and accordingly the transmission success rate can be calculated on the basis of the measurement results of the reception intervals.

A technique is also known in which a wireless data communication system makes the transmission device record transmission time and the transmitted contents and also makes the reception device record the reception time and the received contents so that the recorded contents are analyzed in order to determine whether or not the transmission device and the reception device were operating normally when a failure occurred in communication.

A technique is also known in which, in a mobile communication network, a transmitting node transmits a measurement packet stream periodically and a receiving node transmits the measurement values of packet delay to the transmitting node so that the state information of each route is updated.

A technique is also known in which, in a mobile ad hoc network, link quality is measured on the basis of a packet error rate in order to determine a route on the basis of the measurement result.

SUMMARY

According to an aspect of the embodiments, a node in a network including a plurality of nodes includes a transmission unit, a reception unit, a memory, and a processor.

The transmission unit transmits data to another node. The reception unit receives data from another node. The memory stores a communication history between a plurality of other nodes and the node including the memory. The processor generates, when an acknowledgement response to data transmitted to a first node among the plurality of other nodes is not received from the first node, duplicate data of the transmitted data. The processor refers to the communication history, identifies the first node as a cause of generation of the duplicate data, and generates a check request that includes a communication history between the first node and the node including the memory and that requests the first node to check the communication history when a duplication report indicating detection of the duplicate data transmitted to a second node among the plurality of other nodes is received from one of the plurality of other nodes.

DESCRIPTION OF EMBODIMENTS

The above described methods of responding to a transmitting node when a receiving node has received data in conventional communication networks have the following problems.

It is possible to select the most appropriate method of transmitting an Ack from among (1) a method in which transmission of an Ack is multiplexed, (2) a method in which a transmission confirmation of an Ack is performed, and (3) a method in which the transmission power of an Ack is adjusted, and to select parameters such as the number of times of transmitting an Ack, the transmission power of an Ack, and the like, by taking into consideration the capacity reduction in the communication network and worsening of congestion caused by duplicate packets. In such a case, large-scale simulation is performed in order to set the most appropriate method of transmitting an Ack and the most appropriate parameters in the entire communication network.

In methods (1) and (2) of transmitting an Ack, an Ack packet is transmitted a plurality of number of times, and accordingly the traffic on a communication network is larger than a case where an Ack packet is transmitted in return only once. This may accelerate congestion, and it is considered that the normal operation capacity of the communication network is occupied unnecessarily, imposing loads on the communication network.

In method (1) or (3) of transmitting an Ack, when congestion has become worse due to some factor, the transmission success rate of an Ack packet is decreased, arousing a possibility that duplicate packets will be generated. Therefore, it is difficult to prevent duplicate packets completely although it is possible to reduce duplicate packets.

Also, in the method in which the transmission success rate is calculated by using hello packets, it is difficult to detect the fact that congestion has worsened the transmission success rate. The traffic of Hello packets is distributed to respective nodes almost evenly; however, the traffic of data packets concentrates around a particular node such as a gateway, leading to a tendency to have cases where the transmission success rate worsens only around such a particular node.

Further, Hello packets are transmitted on a consistent cycle without intermissions, each of them being transmitted independently as illustrated inFIG. 4, and accordingly a data volume401of hello packets are distributed along the time axis. By contrast, data packets are transmitted during limited periods, and because relaying of packets and transmission of Ack packets are performed continuously, a data volume402of data packets tends to concentrate on a particular period.

As described above, it is difficult to detect congestion in a communication network by calculating the transmission success rate on the basis of Hello packets, which have different characteristics from those of data packets.

This problem arises not only in ad hoc networks but also in other networks that have a plurality of nodes.

Hereinafter, embodiments will be explained in detail by referring to the drawings.

FIG. 5illustrates a configuration example of a communication system according to an embodiment. The communication system illustrated inFIG. 5includes nodes501through506in a communication network, and the nodes501through506perform communications with other nodes in a wireless or wired manner.

The nodes501and502may also be referred to as a duplicating node and a causing node, respectively. A duplicating node is a node that generates duplicate data of transmitted data when an acknowledge response to data transmitted to another node has not been received from that node.

The node501includes a transmission unit511, a reception unit512, a storage unit513, generation units514and516, an identification unit515, and a check unit517.

The transmission unit511transmits data to another node. The reception unit512receives data from another node. The storage unit513stores a communication history between the node501and a plurality of other nodes. The generation unit514generates duplicate data of transmitted data when an acknowledge response to data transmitted to the node502has not been received from the node502. The transmission unit511transmits the duplicate data to a node504.

The reception unit512receives a duplication report indicating that duplicate data has been detected from a node503. When the duplication report has been received, the identification unit515refers to the communication history, and identifies the node502as the cause of the duplicate data. The generation unit516generates a check request that includes a communication history between the nodes501and502and that requests the node502to check the communication history. The transmission unit511transmits the check request to the node502.

The node502includes a transmission unit521, a reception unit522, a storage unit523, generation units524and526, an identification unit525, and a check unit527.

The storage unit523stores a communication history between the node502and a plurality of other nodes. The transmission unit521transmits to the node501an acknowledge response to data received from the node501. The reception unit522receives from the node501a check request that includes the communication history between the nodes501and502and that requests to check communication history.

When the check request has been received, the check unit527collates the communication history included in the check request with the communication history between the nodes501and502that is stored in the storage unit523. When the node501has not received from the node502an acknowledge response to the data transmitted from the node501to the node502, the check unit527changes the method of responding to the node501.

The node503includes a transmission unit531, a reception unit532, a storage unit533, generation units534and536, an identification unit535, and a check unit537.

The storage unit533stores a communication history between the node503and a plurality of other nodes. The reception unit532receives first data from the node505. When the first data has been received, the identification unit535refers to the communication history so as to check whether one of the first data and second data received from the node506is duplicate data of the other of them. When one of them is duplicate data of the other, the identification unit535identifies the node501that generated the duplicate data. The transmission unit531transmits to the node501a duplication report indicating that duplicate data is detected.

In the communication system illustrated inFIG. 5, a duplicating node (node501) is identified when duplicate data is detected in the node503, and the duplicating node requests the causing node (node502) to check the communication history. Then, in the causing node, the communication history of the duplicating node is collated with the communication history of the causing node, and the method of responding from the causing node to the duplicating node is changed.

As described above, a duplicating node and a causing node are identified so that the response method is changed, reliably suppressing the generation of duplicate data. Also, response methods between all nodes are not changed by exchanging communication histories between all nodes in a communication network, and instead, a duplicating node transmits a communication history to a causing node so that only the method of responding from the causing node to the duplicating node is changed, suppressing loads imposed on the communication network for suppressing duplicate data.

FIG. 6illustrates an example of a communication network according to an embodiment. The communication network illustrated inFIG. 6includes nodes601through606, and has a plurality of options as a packet transfer route. The pieces of identification information (node IDs) of the nodes601through606are a, b, c, d, e, and f, respectively.

FIG. 7is a flowchart explaining an example of an operation in a normal mode of the communication network illustrated inFIG. 6. When a data packet is to be transferred from the node601to the node606, there is a transfer route via the node605and a transfer route via nodes603and604between the nodes602and606.

When the transfer route via the node605is first selected so that the data packet is transmitted from the node602to the node605, an Ack packet611is transmitted in return from the node605to the node602. Thereafter, the data packet is transmitted from the node605to the node606so that the data packet reaches the node606.

When the return of the Ack packet611has failed due to congestion (step701), the Ack packet611does not reach the node602, and this causes a situation where the same data packet is transferred as a duplicate packet612to a transfer route that goes via the nodes603and604as indirect transfer (step702). Thereafter, the duplicate packet612is transmitted from the node604to the node606so that the duplicate packet612reaches the node606.

The node606detects that the duplicate packet612is a duplication of the data packet that was received from the node605. Then, a duplication report packet613indicating that the duplicate packet612has been detected is transmitted to the node602(duplicating node), which generated the duplicate packet612(step703).

The node602refers to the communication history between the node602and an adjacent node so as to identify the node605(causing node), which caused the generation of the duplicate packet612, and counts the number of times that the duplication report packet613was received for each causing node (step704). When the counted value of a causing node has exceeded a threshold, the node602transitions to the monitoring mode (step705).

FIG. 8is a flowchart explaining an example of an operation in a monitoring mode of the communication network illustrated inFIG. 6. As illustrated inFIG. 9, the node602periodically transmits a check request packet901to the node605(step801). The check request packet901includes the communication history between the nodes602and605.

From the communication history included in the check request packet901, the node605extracts a record indicating that the node602received Ack packets from the node605. Also, from the communication history between the nodes602and605stored in the node605, the node605extracts a record indicating that the node605transmitted Ack packets to the node602. Thereafter, the two extracted records are collated (step802), and the transmission success rate of Ack packets is calculated (step803).

Next, when the obtained transmission success rate is lower than a threshold, the node605changes the method of responding to the node602in such a manner that the transmission success rate increases (step804). The nodes602and605repeat the operations of steps801through804, and the nodes transition to the normal mode (step805) when a prescribed period of time has elapsed since the operation of the monitoring mode started. It is also possible to transition to the normal mode when a prescribed period of time has elapsed after the transmission success rate of Ack packets has become equal to or higher than the threshold.

Although the communication network illustrated inFIG. 6has six nodes, a communication network according to an embodiment may have five nodes or fewer or seven nodes or more.

Next, explanations in more detail will be given for configurations and operations of each node according to an embodiment.

FIG. 10illustrates a configuration example of a node1001that corresponds to each node included in a wired or wireless communication network. The node1001illustrated inFIG. 10corresponds to each of the nodes501through506illustrated inFIG. 5and to each of the nodes601through606illustrated inFIG. 6.

The node1001includes a reception unit1011, a duplication report packet process unit1012, a check request packet process unit1013, an Ack packet process unit1014, a data packet process unit1015, a duplication report packet generation unit1016, and a transmission unit1017. The node1001further includes a storage unit1018, a mode process unit1019, a retransmission process unit1020, a check request packet generation unit1021, and a control unit1022.

The storage unit1018stores a link table1031, an Ack transmission evaluation table1032, a data management table1033, a communication history table1034, and a route table1035.

In the link table1031, for each link between the node1001and an adjacent node, the number of times of receiving a duplication report packet to identify the adjacent node as the causing node, a flag representing whether or not the node1001has transitioned to the monitoring mode, TTW1, TTW2, and the like are recorded. In the Ack transmission evaluation table1032, for each adjacent node or link that is the transmission destination of an Ack packet, the transmission success rate of Ack packets, the reception success rate of data packet, and the like are recorded.

The communication history table1034records a communication history of packets that were transmitted or received. The communication history table1034records, for each packet that was transmitted or received, the transmission time or the reception time, the node ID of the global source (GS) node, the frame ID (FID), the node ID of the local source (LS) node, and the node ID of the local destination (LD). The communication history table1034further records the packet type, the process type, and the like.

The data management table1033records a communication history of data packets among packets recorded in the communication history table1034. The data management table1033records, for each data packet that was transmitted or received, the transmission time or the reception time, the node ID of the GS, the FID, the TTW, the node ID of the LD, the route, and the like.

The route table1035records route information including an LD that the node1001can use as the packet transmission destination.

An FID is identification information of a packet, a GS corresponds to a node that sent out a packet for the first time, an LS corresponds to an adjacent node that sent out a reception packet, and an LD corresponds to a node adjacent to the transmission destination of a transmission packet. A packet type represents the type of a packet, such as a data packet, an Ack packet or the like, and a process type represents the type of process performed on a packet, such as transmission, reception, indirect transfer, and the like.

A TTW is set in the data management table1033when a data packet is transmitted, and represents the time obtained by adding the Ack waiting time to the time when the TTW was set. A TTW1 is set in the link table1031when the node1001has transitioned to the monitoring mode and when the transmission success rate of Ack packets has been determined to be lower than a threshold in the monitoring mode. The TTW1 represents a time obtained by adding the check interval to the time when the TTW1 was set. A TTW2 is set when the node1001has transitioned to the monitoring mode, and represents a time obtained by a monitoring mode continuation time to the time when the TTW2 was set.

The reception unit1011receives a packet from an adjacent node through a link. The duplication report packet process unit1012performs a process that is to be performed when a duplication report packet has been received, the check request packet process unit1013performs a process to be performed when a process check request packet has been received, and the Ack packet process unit1014performs a process to be performed when an Ack packet has been received.

The data packet process unit1015detects a duplicate packet from received data packets, and the duplication report packet generation unit1016generates, when a duplicate packet has been detected, a duplication report packet directed to the duplicating node. The transmission unit1017transmits a data packet, an Ack packet, and the like to an adjacent node through a link.

The mode process unit1019cancels the monitoring mode, and performs a process of making the mode transition to the normal mode, and when an Ack packet has not been received from a node adjacent to the data packet transmission destination, the retransmission process unit1020performs a process of retransmitting a data packet to a another adjacent node. The check request packet generation unit1021generates a check request packet in the monitoring mode. The control unit1022operates in accordance with a timer event, and requests the mode process unit1019, the retransmission process unit1020, or the check request packet generation unit1021to perform necessary processes.

The reception unit1011corresponds to the reception units512,522, and532inFIG. 5, and the duplication report packet process unit1012corresponds to the identification units515,525, and535. The check request packet process unit1013corresponds to the check units517,527, and537, and the data packet process unit1015corresponds to the identification units515,525, and535. The transmission unit1017corresponds to the transmission units511,521, and531, and the storage unit1018corresponds to the storage units513,523, and533. The retransmission process unit1020corresponds to the generation units514,524, and534, and the check request packet generation unit1021corresponds to the generation units516,526, and536.

FIG. 11is a flowchart explaining an example of a communication process performed by the node1001, andFIGS. 12 through 15are flowcharts explaining examples of the processes in steps1110,1108,1107, and1106inFIG. 11, respectively. The communication process inFIG. 11starts at constant time intervals as timer events.

First, the control unit1022obtains the current time from the timer, and compares the current time with the TTW recorded in each entry of the data management table1033(step1101). When there is an entry identical to the current time (YES in step1101), it is recognized that the Ack waiting time has elapsed without receiving an Ack packet from the transmission destination of the corresponding data packet. In such a case, the control unit1022requests the retransmission process unit1020to perform data packet retransmission (step1110).

When there are no entries that have a TTW identical to the current time (NO in step1101), the control unit1022compares the current time with the TTW1 recorded in each entry of the link table1031(step1102). When there is an entry having the TTW1 identical to the current time (YES in step1102), the current time is a time for requesting the causing node to check the communication history, and accordingly the control unit1022requests the check request packet generation unit1021to perform a check request packet transmission process (step1111). The check request packet generation unit1021generates a check request packet, and the transmission unit1017transmits a check request packet to the causing node.

When there are no entries having a TTW1 identical to the current time (NO in step1102), the control unit1022compares the current time with the TTW2 recorded in each entry of the link table1031(step1103). When there is an entry having a TTW2 identical to the current time (YES in step1103), the current time is a time for terminating the monitoring mode, and accordingly the control unit1022requests the mode process unit1019to cancel the monitoring mode (step1112). The mode process unit1019updates the link table1031so as to cancel the monitoring mode, and the node1001transitions to the normal mode.

When there are no entries having a TTW2 identical to the current time (NO in step1103), the control unit1022terminates the process. Next, the reception unit1011checks whether or not a packet has been received from either adjacent node (step1104). When a packet has not been received, the processes in and subsequent to step1101are repeated, and when a packet has been received, the control unit1022checks the type of that packet (step1105).

When the type of the packet is a check request packet, the control unit1022requests the check request packet process unit1013to perform a check request packet reception process (step1106). When the type of the packet is a duplication report packet, the control unit1022requests the duplication report packet process unit1012to perform a duplication report packet reception process (step1107).

When the type of the packet is a data packet, the control unit1022requests the data packet process unit1015to perform a data packet reception process (step1108). When the type of the packet is an Ack packet, the control unit1022requests the Ack packet process unit1014to update the data management table1033(step1109). Thereafter, the Ack packet process unit1014deletes the entry of the corresponding data packet from the data management table1033.

When the processes in steps1110through1112or1106through1109are terminated, the processes in and subsequent to step1101are repeated.

FIG. 12is a flowchart explaining an example of a data packet retransmission process performed by the retransmission process unit1020in step1110inFIG. 11.

The retransmission process unit1020refers to the data management table1033, and checks whether or not there is an LD that has not been used among a plurality of LDs recorded in an entry having a TTW identical to the current time (step1201).

FIG. 16illustrates an example of an entry in the data management table1033. In this example, information of the transmission time of a data packet, the node ID of the GS, the FID, the TTW, and the LD is depicted from among pieces of information included in an entry. The information of LD includes use flags and node IDs of LD1through LD3.

LD1through LD3correspond to a plurality of nodes that the node1001can use as LDs, their node IDs are h, p, and q, respectively, and their use flags are logics “1”, “0”, and “0”, respectively. When a use flag is “1”, this represents that the corresponding LD has been used, and when a use flag is “0”, this represents that the corresponding LD has not been used.

InFIG. 16, the use flag of LD1has been set to “1”, and accordingly it is recognized that a data packet has been transmitted to node h. When the current time has become 3600.9999, which is recorded as a TTW, it is checked whether or not there are LDs that have not been used from among LD1through LD3.

When there are LDs that have not been used (YES in step1201), the retransmission process unit1020selects one of those LDs, and updates the use flag of the selected LD to “1” (step1202). Next, the retransmission process unit1020resets, to the TTW of that entry, the time obtained by adding the Ack waiting time to the current time (step1203). Thereafter, the retransmission process unit1020generates a data packet having the same data as the transmitted data packet that corresponds to that entry, and requests the transmission unit1017to retransmit the data packet to the selected LD (step1204). The transmission unit1017transmits the requested data packet to the requested LD.

When, for example, LD2inFIG. 16has been selected, the use flag of LD2is changed to “1” as illustrated inFIG. 17, and a data packet is retransmitted to node p.

Thereafter, when, in step1101inFIG. 11, the current time is identical to the TTW that has been reset, LD3is selected as the retransmission destination. Then, as illustrated inFIG. 18, the use flag of LD3is changed to “1”, and a data packet is retransmitted to node q.

When there are no LDs that have been unused among a plurality of LDs recorded in an entry having a TTW identical to the current time (NO in step1201), the retransmission process unit1020deletes that entry from the data management table1033(step1205).

FIG. 13is a flowchart explaining an example of a data packet reception process performed by the data packet process unit1015in step1108inFIG. 11.

The data packet process unit1015refers to the data management table1033or the communication history table1034so as to check whether or not the same data packet as the received data packet is registered (step1301).

FIG. 19andFIG. 20respectively illustrate examples of entries in the communication history table1034stored in the node602(node b) and the node605(node e) inFIG. 6. Each node stores, in the communication history table1034, transmission or reception records of past n packets for which the process has been terminated. “n” represents an integer equal to or greater than one, and may be set beforehand or may be set in accordance with the current communication conditions.

The examples inFIGS. 19 and 20illustrate packet transmission time or packet reception time, node ID of GS, FID, node ID of LS, node ID of LD, packet type, and process type from among pieces of information included in an entry.

These communication histories illustrate that an Ack packet having “1” as the FID was transmitted from node e to node b in return for a data packet having “1” as the FID transmitted from node b to node e. However, an Ack packet transmitted in return for a data packet having “2” as the FID that was transmitted from node b to node e did not reach node e, and accordingly a data packet was transmitted from node b to node c as an indirect transfer.

Therefore, it is possible to recognize that the data packet having “2” as the FID transmitted from node b to node e and the data packet having “2” as the FID transmitted from node b to node c as an indirect transfer are the same packets.

As illustrated inFIG. 6, the data packet transmitted to node e is received by the node606(node f), and the data packet transmitted to node c as an indirect transfer (duplicate packet612) is also received by node f. In node f, the data packet that was received first between the two data packets is first registered in the communication history table1034. Accordingly, by comparing the GS and FID of the data packet received later with the GS and FID of the data packet registered in the communication history table1034, it is possible to check whether or not the same data packet as the data packet received currently is registered.

As described above, the communication history of data packets registered in the communication history table1034is registered in the data management table1033. Accordingly, even when the data management table1033is used instead of the communication history table1034, it is possible to check whether or not the same data packet as a received data packet is registered.

FIG. 21illustrates an example of entries in the data management table1033stored in node f. In this example, the transmission time or the reception time of data packet, node ID of GS, FID, and route are presented from among pieces of information included in an entry. A route is information in which node IDs of one or more nodes that the received data packet has passed through after being transmitted from the GS and before reaching the node f are arranged in the order of the passing through. For example, it can be recognized that the data packet having “2” as the FID reached node f after being transmitted from node a via nodes b and e.

When node f receives the duplicate packet612as illustrated inFIG. 22from node d in this situation, the data packet process unit1015refers to the data management table1033illustrated inFIG. 21, and checks whether or not the same data packet as the duplicate packet612is registered. In this example, because the data management table1033inFIG. 21has an entry having the same GS and FID as those inFIG. 22, it is determined that the same data packet is registered.

When the same data packet is not registered in the data management table1033or the communication history table1034(NO in step1301), the data packet process unit1015requests the transmission unit1017to transmit an Ack packet (step1302). The transmission unit1017returns an Ack packet to the LS of the received data packet.

Next, the data packet process unit1015selects a transmission destination LD, and registers the data packet in the data management table1033(step1303), and requests the transmission unit1017to transmit the data packet (step1304). The transmission unit1017transmits the data packet to the selected LD.

When the same data packet is registered (YES in step1301), the data packet process unit1015checks whether or not the received data packet has already passed through the node1001(step1305).

In the case of the duplicate packet612inFIG. 22, node f is recorded at the end of the route, meaning that the packet has not passed through node f before reaching the end of the route. In the case of the data packet inFIG. 23, node f is recorded as the third and last nodes on the route, meaning that the packet has already passed through node f. Accordingly, it is possible to check whether or not the packet has passed through the node1001by referring to the route of the received data packet.

When the data packet has already passed through the node1001(YES in step1305), the loop route via the node1001has been formed, and the data packet process unit1015deletes the LD that was used previously from the route table1035(step1307). Thereby, the sending of packets to a loop route is prohibited. Thereafter, the data packet process unit1015sends out a packet to a different route by executing the processes in and subsequent to step1302.

When the data packet has not passed through the node1001(NO in step1305), it is recognized that one of the data packet registered in the data management table1033and the received data packet is a duplicate packet of the other. Accordingly, the data packet process unit1015refers to the data management table1033so as to identify a duplicating node, which generated the duplicate packet, and requests the duplication report packet generation unit1016to generate a duplication report packet (step1306). The duplication report packet generation unit1016generates a duplication report packet, and the transmission unit1017transmits the duplication report packet to the duplicating node.

When the routes are compared between the data packet having “2” as the FID inFIG. 21and the duplicate packet612inFIG. 22, the result illustrated inFIG. 24is obtained. In such a case, checking a common portion between the two routes from node a as the GS to node f will lead to recognition that node b is the last node of the common portion and that the route is branched at this node b. Thereby, node b at the branching point for the two routes (branching node) is identified as a duplicating node.

FIG. 25illustrates an example of the duplication report packet613that is transmitted when duplicating node b has been identified. In this example, the duplication report packet613includes the node ID of the duplicating node, a cause candidate, a GS, and an FID.

A cause candidate is a node ID representing a candidate (candidate node) for a causing node which is a cause of generation of the duplicate packet612. In node f, it is not recognized which of the two same data packets is a duplicate packet, and accordingly it is not recognized which of the two routes illustrated inFIG. 24has a problem in its link. Accordingly, nodes e and c, which are the nodes next to duplicating node b, are both described in the duplication report packet613as candidates for a causing node.

For transmitting the duplication report packet613, a normal route for a data packet or the route through which the last data packet among a plurality of the same data packets was received is used.

FIG. 14is a flowchart explaining an example of a duplication report packet reception process performed by the duplication report packet process unit1012in step1107illustrated inFIG. 11.

The duplication report packet process unit1012identifies the causing node, which caused the duplicate packet, by referring to the communication history table1034(step1401).

When a duplication report packet includes a cause candidate, a plurality of entries corresponding to data transmission processes for a plurality of candidate nodes are extracted from the communication history table1034. The process type of an extracted data transmission process includes transmission and indirect transfer. The LD of the entry having the earliest transmission time among the extracted entries is identified as the causing node.

For example, in node b that received the duplication report packet613illustrated inFIG. 25, two entries of data transmission processes having candidate nodes e and c respectively as LDs are extracted from the communication history table1034illustrated inFIG. 19. In such a case, the process type of the entry having candidate node e as the LD is transmission, while the process type of the entry having candidate node c as the LD is indirect transfer. From among the two entries, node e, which is the LD of the entry having the earlier transmission time, is identified as the causing node.

Next, the duplication report packet process unit1012increments the number of times of reporting the entry corresponding to the causing node in the link table1031(step1402), and compares the number of times of the reporting with a threshold (step1403).

When the number of times of reporting has not exceeded the threshold (YES in step1403), the monitoring flag in the link table1031is changed to “1”, and the node1001transitions to the monitoring mode (step1404). When the number of times of reporting is equal to or smaller than the threshold (NO in step1403), the node1001does not transition to the monitoring mode.

FIG. 26illustrates an example of entries in the link table1031stored in node b. In this example, a link, the number of times of reporting, a monitoring flag, TTW1, and TTW2 are presented from among pieces of information included in an entry.

A link is identification information of a link between the node1001and an adjacent node. As the identification information of the link, the node ID of a corresponding adjacent node, for example, is used. The number of times of reporting is the number of times of receiving a duplication report packet and identifying the adjacent node thereof as a causing node and a monitoring flag represents whether or not the node1001has transitioned to the monitoring mode for monitoring that link. When the monitoring flag is “1”, the flag represents the monitoring mode while when the monitoring flag is “0”, the flag represents the normal mode.

Node b increments the number of times of reporting of link e by one each time it receives a duplication report packet including node e as a cause candidate and identifies node e as a causing node. In a situation where the threshold of the number of times of reporting is “1”, when the number of times of reporting that has been incremented has become two, the monitoring flag of link e is changed to “1”, and the node1001transitions to the monitoring mode for link e.

Upon the above transition, TTW1 is set to the time obtained by adding the check interval to the current time, and TTW2 is set to the time obtained by adding the monitoring mode continuation time to the current time. The check interval is set in such a manner that the higher the speed at which the transmission success rate of an Ack packet changes, the narrower the check interval. Thereby, it is possible to control a response method highly accurately by increasing the number of times of checking when there are great changes in the communication conditions.

Thereafter, when the current time is identical to set TTW1 in step1102inFIG. 11, the transmission unit1017transmits the check request packet901to causing node e as illustrated inFIG. 9. The check request packet901includes the communication history between duplicating node b and causing node e.

FIG. 27illustrates an example of a communication history included in the check request packet901. In this example, from among entries included in the communication history table1034inFIG. 19, an entry including node e as the LS or the LD is extracted and is included in the check request packet901.

The check request packet901includes transmission or reception records of past m packets. m is an integer equal to or greater than one, and may be set beforehand in accordance with the speed at which the propagation environment of the communication network changes or may be set in accordance with the current communication conditions.

As the check request packet901, an existing Hello packet may be used. In such a case, a communication history is added to a Hello packet. However, the transmission intervals of Hello packets are shorter than those of data packets, and therefore it is desirable that the check intervals be adjusted by adding a communication history to a Hello packet only once in a plurality of times.

FIG. 15is a flowchart illustrating an example of a check request packet reception process performed by the check request packet process unit1013in step1106illustrated inFIG. 11.

The check request packet process unit1013collates the communication history included in a received check request packet and the communication history table1034, and extracts, from the communication history included in the check request packet, the number of times of receiving Ack packets in the duplicating node, which is the requesting source (step1501). Next, the check request packet process unit1013extracts, from the communication history table1034, the number of times of transmitting Ack packets in the node1001in the same period (step1502).

Thereafter, the check request packet process unit1013calculates the transmission success rate of Ack packets from the extracted numbers of times of receiving and transmitting (step1503), and compares the obtained transmission success rate with a threshold (step1504). When the transmission success rate is lower than the threshold (NO in step1504), the check request packet process unit1013changes a response method used when a data packet is received from a duplicating node (step1505). When the transmission success rate is equal to or higher than the threshold (YES in step1504), the response method is not changed.

When the response method is changed in step1505, the response method after the change is reported to the duplicating node. The duplicating node that has received this report resets TTW1 in the link table1031to the time obtained by adding the check interval to the current time. For example, the link table1031illustrated inFIG. 26is updated in a manner illustrated inFIG. 28.

Thereafter, in the duplicating node, the link table1031is again referred to in step1102ofFIG. 11, and when the current time is identical to TTW1 that was reset, the check request packet transmission process in step1111is performed again.

In node e, which has received the check request packet901illustrated inFIG. 9, the communication history inFIG. 27included in the check request packet901is collated with the communication history table1034illustrated inFIG. 20. From the communication history illustrated inFIG. 27, it is recognized that the number of times of receiving an Ack packet is one, and from the communication history table1034illustrated inFIG. 20, it is recognized that the number of times of transmitting an Ack packet in node e is two.

Therefore, 0.5 is obtained as the transmission success rate of Ack packets by dividing the number of times of receiving Ack packets in node b by the number of times of transmitting Ack packets in node e. This transmission success rate of Ack packets represents the ratio of the number of Ack packets included in the communication history illustrated inFIG. 27to the number of Ack packets included in the communication history table1034illustrated inFIG. 20. As the threshold of the transmission success rate, a real number within a range, for example, from 0.5 through 1.0, is used.

At this moment, an entry as illustrated inFIG. 29is stored in the Ack transmission evaluation table1032. “Node” inFIG. 29represents the node ID of the duplicating node, which is the transmission destination of an Ack packet, and “Ack transmission success rate” represents the transmission success rate of an Ack packet transmitted from node e to node b. When the threshold of the transmission success rate is 0.7, the response method is changed because the Ack transmission success rate is lower than the threshold.

According to the above check request packet reception process, it is possible to accurately calculate the transmission success rate of Ack packets during congestion by checking the communication histories in both of the nodes adjacent to the monitoring target link.

Also, a communication history, which is relatively large in volume, is only transmitted on a link that is a monitoring target without being exchanged between all nodes, and accordingly monitoring loads that are imposed on the communication network can be minimized. When check request packets including communication histories are transmitted during a period when data packets are not transmitted or received, the loads on the communication network are reduced further.

In the check request packet reception process illustrated inFIG. 15, the response method is changed only in accordance with the transmission success rate of Ack packets; however, the response method may be changed also in accordance with other conditions. For example, the reception success rate of data packets may be used in addition to the transmission success rate of Ack packets.

In such a case, the check request packet process unit1013extracts, in step1501, the number of receiving Ack packets and the number of transmitting data packets in the duplicating node, from the communication history included in the check request packet. Also, in step S1502, the check request packet process unit1013extracts the number of times of transmitting Ack packets and the number of times of receiving data packets in the node1001from the communication history table1034.

In step1503, the check request packet process unit1013calculates the transmission success rate of Ack packets and the reception success rate of data packets, and in step1504, the check request packet process unit1013compares the transmission success rate of Ack packets with threshold T1 and the reception success rate of data packets with threshold T2.

When the transmission success rate of Ack packets is lower than T1 and the reception success rate of data packets is higher than T2, the check request packet process unit1013changes the response method. In such a case, because only the transmission success rate of Ack packets is low, it is considered that a duplicate packet was generated due to the response method.

When the transmission success rate of Ack packets is equal to or higher than T1 or the reception success rate of data packets is equal to or lower than T2, the response method is not changed. When the reception success rate of data packets is low, it is considered that the response method has no problems and other factors caused the generation of the duplicate packet.

For example, it is recognized that the number of transmitting data packets in node b is two from the communication history illustrated inFIG. 27and that the number of receiving data packets in node e is two from the communication history table1034illustrated inFIG. 20.

Accordingly, 1.0 is obtained as the reception success rate of data packets by dividing the number of receiving data packets in node e by the number of transmitting data packets in node b. This reception success rate of data packets represents the ratio of the number of data packets included in the communication history table1034illustrated inFIG. 20to the number of data packets included in the communication history illustrated inFIG. 27. As thresholds of T1 and T2, real numbers within a range, for example, from 0.5 through 1.0, are used.

At this moment, an entry as illustrated inFIG. 30is stored in the Ack transmission evaluation table1032. “Data reception success rate” inFIG. 30represents the reception success rate of data packets transmitted from node b to node e. When T1=T2=0.7 is satisfied, the Ack transmission success rate is lower than T1 and the data reception success rate is higher than T2, and accordingly the response method is changed.

As alternative response methods in the causing node, the methods as follows are possible.

(1) A Method in which Transmission of an Ack Packet is Multiplexed.

According to this method, an Ack packet is transmitted a plurality of number of times from causing node e to duplicating node b. Thereby, the reachability of the Ack packet increases, leading to suppression of duplication of a data packet.

For example, when the number of times of transmitting an Ack packet from node e to node b is changed to two, a first Ack packet3102is transmitted in return from node e to node b as illustrated inFIG. 31after a data packet3101is transmitted from node b to node e. Next, a second Ack packet3103is transmitted in return.

In such a case, the number of times of transmitting and the number of times of receiving are counted for each of the multiplexed Ack packets. Thereby, even when the reachability of an Ack packet has been increased by multiplexing, the transmission success rate of Ack packets can be evaluated independently from such multiplexing.

For example, when congestion continues, the transmission success rate of Ack packets is kept low, and accordingly multiplexing is continued. The monitoring mode may be cancelled when the congestion is resolved and the transmission success rate of Ack packets becomes equal to or higher than the threshold. After the cancellation of the monitoring mode, the response method returns to a response method in which the transmission of an Ack packet is not multiplexed.

(2) A Method in which Transmission of an Ack Packet is Confirmed

As illustrated inFIG. 32, according to this method, after a data packet3201has been transmitted from duplicating node b to causing node e, a first Ack packet3202is transmitted in return from node e to node b. Next, a second Ack packet3203indicating the reception of the first Ack packet3202is transmitted in return from node b to node e.

When node e does not receive the second Ack packet3203, the first Ack packet is transmitted repeatedly from node e to node b until the second Ack packet3203is received. Thereby, the reachability of the first Ack packet increases, leading to suppression of the duplication of the data packet.

The monitoring mode may be cancelled when the number of times of repeated transmission becomes smaller than a threshold by recording the number of times of repeated transmission of the first Ack packet. After the cancellation of the monitoring mode, the method returns to a response method in which the transmission of an Ack packet is not confirmed.

(3) A Method in which the Transmission Power of an Ack Packet is Adjusted

As illustrated inFIG. 33, according to this method, after a data packet3301is transmitted from duplicating node b to causing node e, an Ack packet3302is transmitted in return from node e to node b with increased transmission power. Thereby, the reachability of the Ack packet increases, leading to suppression of the duplication of the data packet.

Thereafter, the monitoring mode may be cancelled when the transmission success rate of Ack packets becomes equal to or higher than the threshold. After the cancellation of the monitoring mode, the transmission power of an Ack packet is decreased.

When above method (1), in which the transmission of an Ack packet is multiplexed, is employed as an alternative response method, the check request packet process unit1013multiplexes the transmission of an Ack packet by the following procedures, for example.

The check request packet process unit1013first determines the minimum integer k that satisfies the following expression, where ar is the transmission success rate of Ack packets calculated in step1503ofFIG. 15and r0 is the threshold of the transmission success rate.
(1−(1−ar)**k)>r0  (1)

“**k” on the left of expression (1) represents a k-th power operation. For example, when ar=0.5 and r0=0.7 are satisfied, k=2 is satisfied, and when ar=0.5 and r0=0.8 are satisfied, k=3 is satisfied.

The check request packet process unit1013changes the response method by using obtained k as the degree of multiplexing an Ack packet in such a manner that each time a data packet is received an Ack packet is transmitted in return k times. The degree of multiplexing k may be determined on the basis of factors other than expression (1).

According to this multiplexing method, an Ack packet is multiplexed only in a section and a period with actual deterioration of link quality caused by congestion. Accordingly, Ack packets are reduced in sections and periods that do not need multiplexing, in comparison with a method in which Ack packets are multiplexed regularly in the entire communication network, leading to reduction in loads on the communication network.

Even when above method (2), in which the transmission of Ack packets is confirmed, is employed, Ack packets are transmitted repeatedly only in a particular section and period. Accordingly, loads on a communication network can be reduced in comparison with a method in which the transmission of Ack packets is confirmed regularly in the entire communication network.

Even when above method (3), in which the transmission power of an Ack packet is adjusted, is employed, the transmission power of an Ack packet is increased only in a particular section and period. Accordingly, power consumed by a communication network can be reduced in comparison with a method in which the transmission power of Ack packets is increased regularly in the entire communication network.

By increasing the transmission success rate of Ack packets from a causing node to a duplicating node by identifying, in a real time way, the duplicating node which generated a duplicate packet, the generation of duplicate packets can be suppressed reliably. Accordingly, worsening of congestion in a communication network can be suppressed at an early stage, eliminating the need for simulation for setting an appropriate response method in the entire communication network.

Further, by changing the threshold of the number of times of reporting in step1403inFIG. 14, the process of the monitoring mode can be adjusted appropriately. For example, when the threshold is set to be greater, the frequency and sections of transitioning to the monitoring mode can be reduced, leading to reduction in the loads on the communication network.

Also, by setting the threshold to be smaller, it is possible to increase the frequency and sections of transitioning to the monitoring mode, leading to reliable suppression of the generation of duplicate packets. Particularly, when the threshold has been set to zero, a duplicating node that has received a duplication report packet transitions to the monitoring mode and the transmission success rate of Ack packets is evaluated each time a duplicate packet has been detected. Thereby, the generation of duplicate packets can be suppressed by changing the response method.

Note that in the communication processes illustrated inFIG. 11throughFIG. 15, it is not always necessary to execute all steps, and some of the steps may be omitted in accordance with the configuration or conditions of a communication network. For example, when a loop route is not likely to be formed, the processes in steps1305and1307illustrated inFIG. 13may be omitted. Also, when the node1001transitions to the monitoring mode immediately after identifying the causing node in step1401inFIG. 14, the processes in steps1402and1403may be omitted.

The nodes501through503illustrated inFIG. 5and the node1001illustrated inFIG. 10may be implemented by using, for example, an information processing apparatus (computer) as illustrated inFIG. 34. The information processing apparatus illustrated inFIG. 34includes a Central Processing Unit (CPU)3401, a memory3402, an external storage device3403, a medium driving device3404, and a network connection device3405. These components are connected to each other through a bus3406.

The memory3402is a semiconductor memory such as, for example, a Read Only Memory (ROM), a Random Access Memory (RAM), a flash memory, etc., and stores programs and data used for communication processes. For example, the CPU3401(processor) executes a program by using the memory3402so as to perform communication processes.

In the case of the node501illustrated inFIG. 5, the CPU3401operates as the generation units514and516, the identification unit515, and the check unit517. In the case of the node502, the CPU3401operates as the generation units524and526, the identification unit525, and the check unit527. In the case of the node503, the CPU3401operates as the generation units534,536, the identification unit535, and the check unit537.

In the case of the node1001illustrated inFIG. 10, the CPU3401operates as the duplication report packet process unit1012, the check request packet process unit1013, the Ack packet process unit1014, the data packet process unit1015, the duplication report packet generation unit1016, the mode process unit1019, the retransmission process unit1020, the check request packet generation unit1021, and the control unit1022.

The memory3402can be used as the storage units513,523, and533illustrated inFIG. 5, or as the storage unit1018illustrated inFIG. 10.

The external storage device3403is, for example, a magnetic disk device, an optical disk device, a magneto-optical disk device, a tape device, or the like. Examples of the external storage device3403also include a hard disk drive. The information processing apparatus can store programs and data in the external storage device3403so as to load them onto the memory3402to use them.

The medium driving device3404drives a portable recording medium3407so as to access information in it. The portable recording medium3407is, for example, a memory device, a flexible disk, an optical disk, a magneto-optical disk, or the like. Examples of the portable recording medium3407also include a Compact Disk Read Only Memory (CD-ROM), a Digital Versatile Disk (DVD), a Universal Serial Bus (USB) memory, and the like. An operator can store programs and data in the portable recording medium3407so as to load them onto the memory3402to use them.

As described above, examples of a computer-readable recording medium that stores programs and data used for communication processes include a physical (non-transitory) recording medium such as the memory3402, the external storage device3403, and the portable recording medium3407.

The network connection device3405is a communication interface that is connected to a wired or wireless communication network for performing data conversion that accompanies communication. The information processing apparatus can receive programs and data from an external device via the network connection device3405so as to load them onto the memory3402to use them. The network connection device3405can also be used as the transmission units511,521, and531, the reception units512,522, and532illustrated inFIG. 5, and as the reception unit1011or the transmission unit1017illustrated inFIG. 10.