Communication terminal and communication network

• US 7,554,982 B2
• Filed: 05/14/2004
• Issued: 06/30/2009
• Est. Priority Date: 05/16/2003
• Status: Expired due to Fees

• Current Assignee: OKI Electric Industry Company Limited
• Original Assignee: OKI Electric Industry Company Limited
• Inventors: Nakamura, Nobuyuki, Kado, Youiti
• Primary Examiner(s): Rao; Seema S
• Assistant Examiner(s): Davenport; Mon Cheri S
• Application Number:
  US10/845,199
• Publication Number:
  US 20040258064A1
• Time in Patent Office: 1,873 Days
• Field of Search: 370/338, 370/351, 370/389, 370/390, 370/392, 370/395.31, 370/395.32, 370/395.4, 370/400, 370/401, 370/428, 370/429
• US Class Current: 370/392
• 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;

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;

an expiration time storage unit for storing an initial value of a relay time, the initial value being greater than zero; and

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

wherein 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,

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,

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.

2. The communication terminal of claim 1, 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

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,

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.

3. The communication terminal of claim 2, 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.

4. The communication terminal of claim 1, 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.

5. The communication terminal of claim 4, 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.

6. The communication terminal of claim 4, 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 a 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.

7. The communication terminal of claim 6, 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.

8. The communication terminal of claim 6, 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.

9. The communication terminal of claim 4, 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.

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

11. The communication terminal of claim 4, 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.

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

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