Communication device and communication system
According to one embodiment, a communication device 1 operating as a publisher calculates parity of a certain size which is capable of being commonly used for each of different data units from data to be sent each time receiving a lost notification from one or more communication device 1 operating as subscribers, the lost notification indicating that one or more data units are lost, and sends the calculated parity to the one or more communication devices 1 operating as the subscribers.
1. A communication device comprising:
a communication interface that sends/receives data to/from another communication device;
a unit creator that creates a plurality of data units, each of the plurality of data units including user data of a certain size;
a sender that sends the plurality of data units to the other communication device through the communication interface; and
a parity calculator that calculates parity which is capable of being commonly used for a plurality data units out of the plurality of data units, wherein
the sender sends the plurality of data units to the other communication device through the communication interface,
the parity calculator calculates the parity of the certain size based on the data to be sent every time receiving a lost notification from the other communication device, the lost notification indicating that one or more data units out of the plurality of data units are lost,
the unit creator creates a parity unit including the parity calculated by the parity calculator, and
the sender sends the parity unit to the other communication device through the communication interface.
2. The communication device according to claim 1 , wherein the parity calculator calculates h-th parity by using following equation
P h,i =f i ( x )%( x−a l+h-1 )= f i ( a l+h-1 )
wherein i is an integer taking a value from one up to the number of unit data forming the user data included in respective data units, % is modulo operation, h is an integer not smaller than one, x is one element of a Galois field of {0, a 0 , a 1 , a 2 , . . . , a m-2 } in which a is an element, wherein m=2 l and a m-1 =1.
3. The communication device according to claim 1 , further comprising: an error-detecting code creator that calculates error-detecting codes of the plurality of data units and an error-detecting code of the parity, wherein
the unit creator creates the plurality of data units by concatenating the user data with the error-detecting codes calculated by the error-detecting code creator for the user data and creates the parity unit by concatenating the parity with the error-detecting code calculated by the error-detecting code creator for the parity.
4. The communication device according to claim 1 , wherein, the parity calculator waits for reception of the lost notification from the other communication device for certain waiting time when a certain number of the data units or the parity unit are sent to the other communication device through the communication interface, and calculates the parity by using the certain number of user data out of the data to be sent when receiving the lost notification within the certain waiting time.
5. The communication device according to claim 4 , wherein the certain number is (( 2 n −1)+1)/2=2 (n-1) (n is an integer not smaller than one; 2 n −1 is a Mersenne prime).
6. The communication device according to claim 1 , wherein
the sender converts the plurality of data units and the parity unit to a message format, and
the communication interface multicast-delivers the data units and the parity unit converted to the message format to the other communication device.
7. A communication device comprising:
a communication interface that sends/receives data to/from another device;
a lost unit detector that detects loss of every one of a plurality of data units received from the other communication device through the communication interface, each of the plurality of data units including user data of a certain size;
a lost notification creator that creates, when the lost unit detector detects the loss of one or more data units out of the plurality of data units, a lost notification indicating that one or more data units are lost;
a sender that sends the lost notification created by the lost notification creator to the other communication device through the communication interface; and
a lost unit recovery executor that recovers the one or more lost data units detected by the lost unit detector by using parity included in a parity unit which the other communication device has sent in response to the lost notification.
8. The communication device according to claim 7 , wherein the lost unit detector detects the loss of every one of the plurality of data units by using error-detecting codes included in the plurality of data units and sequence numbers, each of the sequence numbers being assigned to each of the plurality of data units.
9. The communication device according to claim 7 , wherein
the parity unit includes an error-detecting code, and
the lost unit detector detects whether the parity unit is lost by using the error-detecting code included in the parity unit.
10. The communication device according to claim 7 , wherein,
when receiving a certain number of the data units, the lost notification creator creates the lost notification when there is the one or more lost data units in the certain number of data units, and
the lost unit recovery executor recovers the one or more lost data units by using the certain number of data units and the parity.
11. The communication device according to claim 10 , wherein
the lost notification creator creates the lost notification until parities as many as the one or more lost data units detected by the lost unit detector are received, and
the lost unit recovery executor recovers the one or more lost data units by using the certain number of data units and the parities when the parities as many as the one or more lost data units are secured.
12. The communication device according to claim 11 , wherein the lost notification creator creates the lost notification until the parities as many as the one or more lost data units detected by the lost unit detector, the parities linearly independent from one another are secured.
13. The communication device according to claim 12 , wherein the parities linearly independent from one another include h continuous parities out of the parities calculated by using following equation
P h,i =f i ( x )/%( x−a l+h-1 )= f i ( a l+h-1 )
wherein i is an integer taking a value from one up to the number of unit data forming the user data included in respective data units, % is modulo operation, h is an integer not smaller than one, x is one element of a Galois field of {0, a 0 , a 1 , a 2 , . . . , a m-2 } in which a is an element, wherein m=2 l and a m-1 =1.
14. The communication device according to claim 12 , wherein the certain number is ((2 n −1)+1)/2=2 (n-1) (n is an integer not smaller than one; 2 n −1 is a Mersenne prime).
15. The communication device according to claim 7 , wherein the communication interface receives the plurality of data units and the parity unit multicast-delivered from the other communication device in a message format.
16. The communication device according to claim 15 , further comprising:
a priority manager that sets priority of the device itself in a destination multicast group being a destination of the multicast-delivery; and
a waiting time setter that sets waiting time according to the priority of the device itself set by the priority manager, wherein
the lost notification creator creates the lost notification after the waiting time elapses when the lost unit detector detects the loss of the one or more data units out of the plurality of data units and creates the lost notification after the waiting time elapses from the reception of the parity unit when the parity unit is received from the other communication device before the waiting time elapses and when it is required to receive a next parity unit from the other communication device.
17. The communication device according to claim 15 , further comprising: a waiting time setter that sets waiting time according to the number of the one or more lost data units detected by the lost unit detector, wherein
the lost notification creator creates the lost notification after the waiting time elapses when the lost unit detector detects the loss of the one or more data units out of the plurality of data units and creates the lost notification after the waiting time elapses from the reception of the parity unit when the parity unit is received from the other communication device before the waiting time elapses and when it is required to receive a next parity unit from the other communication device.
18. The communication device according to claim 15 that voluntarily exits from the destination multicast group when the number of the one or more lost data units detected by the lost unit detector is not smaller than a certain number determined in advance.
19. A communication system comprising a publisher and a subscriber,
the publisher including
a first communication interface that sends/receives data to/from a subscriber,
a unit creator that creates a plurality of data units, each of the plurality of data units including user data of a certain size,
a first sender that sends the plurality of data units to the subscriber through the first communication interface, and
a parity calculator that calculates parity which is capable of being commonly used for different data units out of the plurality of data units,
the first sender sending the plurality of data units to the subscriber through the first communication interface,
the parity calculator calculating the parity of the certain size based on the data to be sent every time receiving a lost notification from the subscriber, the lost notification indicating that one or more data units out of the plurality of data units are lost,
the unit creator creating a parity unit including the parity calculated by the parity calculator, and
the first sender sending the parity unit to the subscriber through the first communication interface, and
the subscriber including
a second communication interface that sends/receives the data to/from the publisher,
a lost unit detector that detects loss of every one of the plurality of data units received from the publisher through the second communication interface,
a lost notification creator that creates the lost notification indicating that the one or more data units are lost when the lost unit detector detects the loss of the one or more data units out of the plurality of data units,
a second sender that sends the lost notification created by the lost notification creator to the publisher through the second communication interface, and
a lost unit recovery executor that recovers the one or more lost data units detected by the lost unit detector by using the parity included in the parity unit received from the publisher according to the lost notification.