Communication terminal and communication network

• US 20040258064A1
• Filed: 05/14/2004
• Published: 12/23/2004
• Est. Priority Date: 05/16/2003
• Status: Active Grant

• Current Assignee: OKI Electric Industry Company Limited
• Original Assignee: OKI Electric Industry Company Limited
• Inventors: Nakamura, Nobuyuki, Kado, Youiti
• Granted Patent: US 7,554,982 B2
• Time in Patent Office: Days
• US Class Current: 370/389
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/122 by minimising distances, e.g. by selecting a route with minimum of number of hops
• CPC Class Codes: H04L 45/24 Multipath

Abstract

Routing schemes are provided for a communication network. In one scheme, destination terminals and associated neighboring terminals are listed in a routing control cache at each communication terminal in the network, and packets are routed toward the destination terminal through the associated neighboring terminals. In another scheme, a single path from a source terminal to a destination terminal is automatically expanded into multiple paths. In yet another scheme, packets are routed as long as this does not increase the number of hops to the destination terminal. These schemes enable multiple paths to be established by a simple procedure not requiring complex distance calculations. In still another scheme, routing is restricted to the shortest path and paths up to a given number of hops longer than the shortest path, permitting paths to diverge in multiple directions from the source and destination terminals.

Claims

1. A communication terminal for use in a communication network formed by a plurality of communication terminals that communicate with each other, the plurality of communication terminals having respective identifiers (IDs), the communication terminal being one of the plurality of communication terminals, the communication terminal comprising:

a communication control unit controlling operations of the communication terminal, the operations including transmitting data to the plurality of communication terminals and receiving data from the plurality of communication terminals;

a source and destination analyzer for analyzing received data to obtain the IDs of a source terminal and a destination terminal of the received data;

an expiration time storage unit for storing an initial value of a relay time; and

a routing control cache for holding at least one destination terminal ID and an associated relay time, and decrementing the associated relay time as time elapses;

wherein the communication control unit

writes one of the IDs obtained by the source and destination analyzer into the routing control cache as a destination terminal ID and sets the associated relay time to the initial value,

deletes a destination terminal ID from the routing control cache when its associated relay time reaches zero, and

compares the ID of the destination terminal obtained by the source and destination analyzer with the at least one destination terminal ID stored in the routing control cache to decide whether to route the received data toward the destination terminal.

2. The communication terminal of claim 1, further comprising a neighboring terminal ID analyzer for analyzing the received data to obtain the ID of a neighboring terminal from which the data was directly received.

3. The communication terminal of claim 2, wherein the at least one destination terminal ID stored in the routing control cache is the ID of the source terminal obtained by the source and destination analyzer, the routing control cache also stores the ID obtained by the neighboring terminal ID analyzer as a relay terminal ID in association with the destination terminal ID, and the communication control unit

adds the ID of the source terminal obtained by the source and destination analyzer and the ID obtained by the neighboring terminal ID analyzer to the routing control cache as a new destination terminal ID and associated neighboring relay terminal ID if they are not already stored in the routing control cache as a destination terminal ID and associated neighboring relay terminal ID, also writing the initial value of the relay time in the routing control cache in association with the new destination terminal ID and neighboring relay terminal ID,

restores the associated relay time held in the routing control cache to the initial value if the source terminal of the received data and the ID of the neighboring terminal are already stored in the routing control cache as a destination terminal ID and associated neighboring relay terminal ID,

deletes a destination terminal ID and associated neighboring relay terminal ID from the routing control cache when the associated relay time reaches zero,

relays the received data to all neighboring terminals having IDs held in the routing control cache as relay terminal IDs in association with the ID of the destination terminal of the received data, and

abandons the received data if the ID of the destination terminal of the received data is not held in the routing control cache as a destination terminal ID.

4. The communication terminal of claim 2, further comprising a hopcount cache for storing IDs and associated hopcounts, wherein the source and destination analyzer also obtains the number of hops from the source terminal of the received data, and the communication control unit

writes the ID of the source terminal and the number of hops obtained by the source and destination analyzer in the hopcount cache as an ID and associated hopcount, if the ID of the source terminal is not already stored in the hopcount cache,

updates the hopcount associated with the ID of the source terminal obtained by the source and destination analyzer by writing the number of hops obtained by the source and destination analyzer in the hopcount cache, if the ID of the source terminal is already stored in the hopcount cache,

adds the ID of the source terminal obtained by the source and destination analyzer and the ID obtained by the neighboring terminal ID analyzer to the routing control cache as a new destination terminal ID and associated neighboring relay terminal ID if they are not already stored in the routing control cache as a destination terminal ID and associated neighboring relay terminal ID, also writing the initial value of the relay time in the routing control cache in association with the new destination terminal ID and neighboring relay terminal ID,

restores the associated relay time held in the routing control cache to the initial value if the source terminal of the received data is already stored in the routing control cache as a destination terminal ID, also adding the ID of the neighboring terminal obtained by the neighboring terminal ID analyzer to the routing control cache as a new neighboring relay terminal associated with the ID of the source terminal obtained by the source and destination analyzer,

deletes a destination terminal ID and associated neighboring relay terminal IDs from the routing control cache when the associated relay time reaches zero,

relays the received data to all neighboring terminals having IDs held in the routing control cache as relay terminal IDs in association with the ID of the destination terminal of the received data, provided the sum of the hopcount associated with the ID of the source terminal of the received data and the hopcount associated with the ID of the destination terminal of the received data in the hopcount cache does not exceed a value specified in the received data, and

abandons the received data if the ID of the destination terminal of the received data is not held in the routing control cache as a destination terminal ID or the sum of the hopcount associated with the ID of the source terminal of the received data and the hopcount associated with the ID of the destination terminal of the received data in the hopcount cache exceeds the value specified in the received data.

5. The communication terminal of claim 4, wherein the hopcount cache also stores a retention time in association with each stored ID, and decrements the retention time as time elapses, the retention time associated with the ID being restored to an initial value when the hopcount associated with the ID is updated, the stored ID and associated hopcount being deleted from the hopcount cache when the associated retention time reaches zero.

6. The communication terminal of claim 2, further comprising a neighboring terminal ID storage unit for holding the ID obtained by the neighboring terminal ID analyzer in association with a retention time, and decrementing the retention time from an initial value as time elapses, wherein:

the expiration time storage unit also holds an initial value of the retention time, and the communication control unit

adds the ID of the neighboring terminal obtained by the neighboring terminal ID analyzer to the neighboring terminal ID storage unit if it is not already stored in the neighboring terminal ID storage unit, also writing the initial value of the retention time in the neighboring terminal ID storage unit in association with ID of the neighboring terminal,

restores the associated retention time held in the neighboring terminal ID storage unit to the initial value if the ID of the neighboring terminal obtained by the neighboring terminal ID analyzer is already stored in the neighboring terminal ID storage unit, and

deletes the ID of the neighboring terminal from the neighboring terminal ID storage unit when the associated retention time reaches zero.

7. The communication terminal of claim 6, further comprising:

a routing analyzer for analyzing received data including a route request to obtain a pair of endpoint terminal IDs, and analyzing received data including a route command to obtain a pair of endpoint terminal IDs; and

a routing controller for generating route command data from the received data including a route request;

wherein the expiration time storage unit also holds an, initial value of a retention time, and the communication control unit

adds the ID of the neighboring terminal obtained by the neighboring terminal ID analyzer to the neighboring terminal ID storage unit if it is not already stored in the neighboring terminal ID storage unit, also writing the initial value of the retention time in the neighboring terminal ID storage unit in association with ID of the neighboring terminal,

restores the associated retention time held in the neighboring terminal ID storage unit to the initial value if the ID of the neighboring terminal obtained by the neighboring terminal ID analyzer is already stored in the neighboring terminal ID storage unit,

deletes the ID of the neighboring terminal from the neighboring terminal ID storage unit when the associated retention time reaches zero,

adds the IDs of the pair of endpoint terminals obtained by the routing analyzer to the routing control cache if they are not already stored in the routing control cache, also writing the initial value of the relay time in the routing control cache in association with IDs of the pair of endpoint terminals,

restores the associated relay time held in the routing control cache to the initial value if the IDs of the pair of endpoint terminals obtained by the routing analyzer are already stored in the routing control cache,

deletes the IDs of the pair of endpoint terminals from the routing control cache when the associated relay time reaches zero,

sends route command data to certain other communication terminals in the network as specified by the route request data

relays received data to all neighboring terminals with IDs held in the neighboring terminal ID storage unit if the source and destination terminal IDs of the received data obtained from the source and destination analyzer are stored in the routing control cache, and

abandons the received data if the source and destination terminal IDs of the received data obtained from the source and destination analyzer are not stored in the routing control cache.

8. The communication terminal of claim 6, further comprising a hopcount controller for analyzing the received data to obtain the number of hops from the source terminal of the received data and the number of hops to the destination terminal of the received data, wherein the communication control unit:

writes the source terminal ID of the received data in the hopcount cache as a destination terminal ID, if the source terminal ID of the received data is not already stored in the hopcount cache as a destination terminal ID, also writing the initial value of the relay time and the number of hops from the source terminal of the received data in the hopcount cache in association with the destination terminal ID;

restores the relay time associated with the source terminal ID of the received data to the initial value of the relay time, if the source terminal ID of the received data is already stored in the hopcount cache as a destination terminal ID, also writing the number of hops to the source terminal of the received data in the hopcount cache in association with the source terminal ID of the received data;

deletes the ID stored in the hopcount cache as a destination terminal ID when the associated relay time reaches zero;

relays the received data to all neighboring terminals with IDs stored in the neighboring terminal ID storage unit, decrementing the number of hops to the destination terminal by one, if the destination terminal ID of the received data obtained by the source and destination analyzer is stored in the hopcount cache and the number of hops to the destination terminal stored in the hopcount cache in association with the destination terminal ID is less than the number of hops to the destination terminal obtained from the received data by the hopcount controller, and

abandons the received data if the destination terminal ID of the received data is not stored in the hopcount cache, or the number of hops to the destination terminal stored in the hopcount cache in association with the destination terminal ID is greater than the number of hops to the destination terminal obtained from the received data by the hopcount controller.

9. The communication terminal of claim 8, wherein the communication control unit relays the received data if the number of hops to the destination terminal stored in the hopcount cache in association with the destination terminal ID is equal to the number of hops to the destination terminal obtained from the received data by the hopcount controller.

10. The communication terminal of claim 8, wherein the communication control unit abandons the received data if the number of hops to the destination terminal stored in the hopcount cache in association with the destination terminal ID is equal to the number of hops to the destination terminal obtained from the received data by the hopcount controller.

11. The communication terminal of claim 6, further comprising a motion sensor for detecting motion of the communication terminal, wherein:

when the motion sensor detects motion of the communication terminal, the communication control unit transmits data with a request to delete the ID of the communication terminal; and

if the communication control unit receives data with a request to delete the ID of another communication terminal in the network, the communication control unit deletes the ID of the other communication terminal from the neighboring terminal ID storage unit.

12. The communication terminal of claim 11, wherein the motion sensor comprises an oscillation detector for detecting motion from a pendulum inclination.

13. The communication terminal of claim 6, further comprising:

a motion detector for detecting a velocity and direction of motion of the communication terminal; and

a motion controller for managing the velocity and direction of motion of the communication terminal and the velocity and direction of motion of other communication terminals in the network as reported in data received from the other terminals, determining relative motion of a neighboring terminal with respect to motion of the communication terminal itself, and deciding whether the relative motion exceeds a predetermined value,

wherein

the communication control unit transmits data including the velocity and direction of motion of the communication terminal; and

if the relative motion of the neighboring terminal exceeds the predetermined value, the communication control unit deletes the ID of the neighboring terminal from the neighboring terminal ID storage unit.

14. The communication terminal of claim 13, wherein the motion detector detects velocity from a global positioning system.

15. A communication network comprising a plurality of communication terminals as described in claim 1.

16. A communication terminal for use in a communication network formed by a plurality of communication terminals that communicate with each other, the plurality of communication terminals having respective identifiers (IDs), the communication terminal being one of the plurality of communication terminals, the communication terminal comprising:

a communication unit for transmitting packets to other communication terminals in the communication network and receiving packets from the other communication terminals in the communication;

a hopcount cache for storing IDs of other communication terminals in the communication network and associated hopcounts indicating numbers of hops from the communication terminal to the other communication terminals in the communication network; and

a packet analyzer for analyzing each received packet to obtain the IDs of the source terminal and the destination terminal of the packet and a hopcount ceiling, obtaining the hopcounts associated with the IDs of the source terminal and the destination terminal from the hopcount cache and determining their sum, routing the received packet toward its destination terminal if the sum is equal to or less than the hopcount ceiling, and abandoning the received packet if the sum exceeds the hopcount ceiling.

17. The communication terminal of claim 16, wherein to transmit a packet to an arbitrary terminal in the communication network, the packet analyzer selects a hopcount ceiling equal to or greater than the hopcount associated with the ID of the arbitrary terminal in the hopcount cache, further comprising:

a packet generator for generating the packet to be transmitted to the arbitrary terminal, adding the hopcount ceiling to the packet, and transmitting the packet through the communication unit.

18. The communication terminal of claim 17, wherein the packet analyzer also detects stability of communication and increases the hopcount ceiling added to packets to be transmitted to the arbitrary terminal when communication is unstable.

19. The communication terminal of claim 18, wherein the packet analyzer also selects a priority control condition for restricting paths on which to route the packet transmitted to the arbitrary terminal, and the packet generator also adds the priority control condition to the packet transmitted to the arbitrary terminal.

20. The communication terminal of claim 19, wherein the packet analyzer also selects a bypass condition for unconditional routing of the packet transmitted to the arbitrary terminal, and the packet generator also adds the bypass condition to the packet transmitted to the arbitrary terminal.

21. The communication terminal of claim 17, wherein the packet generator also adds the hopcount associated with the ID of the arbitrary terminal to the packet to be transmitted to the arbitrary terminal to indicate a minimum number of hops to the arbitrary terminal.

22. The communication terminal of claim 16, wherein the packet analyzer also obtains a priority control condition from each received packet, and routes the received packet toward its destination terminal only if the priority condition is satisfied.

23. The communication terminal of claim 22, wherein the priority control condition is a condition on a remainder of the sum of the hopcounts associated with the IDs of the source terminal and the destination terminal of the received packet when divided by a positive integer.

24. The communication terminal of claim 22, wherein the packet analyzer also obtains a bypass condition from the received packet, and routes the received packet toward its destination terminal unconditionally if the bypass condition is satisfied.

25. The communication terminal of claim 24, wherein the bypass condition allows communication terminals within a certain number of hops of the source terminal or destination terminal of the received packet to route the packet unconditionally.

26. The communication terminal of claim 16, wherein the packet analyzer also obtains, from the received packet, a hopcount indicating a minimum number of hops from the source terminal to the destination terminal of the received packet, further comprising:

a suspension time selector for setting a suspension time according to a difference between the sum obtained by the packet analyzer and said minimum number of hops; and

a packet monitor for temporarily suspending routing of the received packet, determining whether the received packet is routed on a path through a different communication terminal in the communication network, abandoning the received packet if the received packet is routed on the other path within the suspension time, and otherwise relaying the received packet at the end of the suspension time.

27. The communication terminal of claim 26, wherein the packet monitor determines whether the received packet is routed on a path through a different communication terminal in the communication network by determining whether a packet identical to the received packet is received during the suspension time.

28. The communication terminal of claim 26, wherein the suspension time selector increases the suspension time as the difference between the sum obtained by the packet analyzer and said minimum number of hops increases.

29. A communication network comprising a plurality of communication terminals as described in claim 16.