Communication terminal and communication network

• US 8,199,664 B2
• Filed: 05/26/2009
• Issued: 06/12/2012
• 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): Wu, Jianye
• Assistant Examiner(s): Davenport, Mon Cheri
• Application Number:
  US12/471,955
• Publication Number:
  US 20090245247A1
• Time in Patent Office: 1,113 Days
• Field of Search: 370/230, 370/252, 370/254, 370/328, 370/338, 370/351, 370/389, 370/392, 370/465
• US Class Current: 370/252
• 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 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;

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, 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; and

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.

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

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

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

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

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

6. 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,

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.

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

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

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

14. A communication network comprising a plurality of communication terminals as described in claim 6.

10. 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 receivinq 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, the packet analyzer also obtaining, from the received packet, a hopcount indicating a minimum number of hops from the source terminal to the destination terminal of the received packet;

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.

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

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

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