Communication terminal and communication network

• US 7,664,032 B2
• Filed: 11/05/2004
• Issued: 02/16/2010
• Est. Priority Date: 11/10/2003
• Status: Active Grant

• Current Assignee: OKI Electric Industry Company Limited
• Original Assignee: OKI Electric Industry Company Limited
• Inventors: Kado, Youiti, Nakamura, Nobuyuki
• Primary Examiner(s): HSU, ALPUS
• Application Number:
  US10/981,630
• Publication Number:
  US 20050099983A1
• Time in Patent Office: 1,929 Days
• Field of Search: 370/235, 370/349, 370/351, 370/395.3, 455/9, 455/445
• US Class Current: 370/235
• CPC Class Codes: H04L 45/20 Hop count for routing purposes, e.g. TTL
• CPC Class Codes: H04L 45/24 Multipath
• CPC Class Codes: H04W 40/00 Communication routing or communication path finding
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks

Abstract

Each node or terminal in a communication network is capable of generating routing information for routing packets from an arbitrary source terminal to an arbitrary destination terminal on both a single-path route and a multipath route. The routing information is placed in packets transmitted to neighboring communication terminals, and analyzed in packets received from neighboring terminals. The single-path route is spatially or temporally separated from the multipath route so that the single-path route does not receive interference from the multipath route. Temporal separation may be effected by suspending the transmission of packets temporarily at each communication terminal on the multipath route. Spatial separation may be effected by using the routing information to designate different zones in the network, the single-path route being disposed in one zone, the multipath route in another zone.

Claims

1. A communication terminal for use in a communication network, comprising:

means for generating routing information for routing packets from a source terminal to a destination terminal on both a single-path route in the communication network and a multipath route in the communication network, the source terminal and the destination terminal being an arbitrary pair of the communication terminals in the communication network;

means for placing said routing information in packets and transmitting said packets to neighboring communication terminals in the communication network; and

means for analyzing the routing information in packets received from said neighboring terminals in the communication network;

means for determining a suspension time; and

means for suspending transmission of a received packet for said suspension time, abandoning the suspended packet if an identical packet is received during the suspension time, the identical packet also being abandoned, and transmitting the received packet at the end of the suspension time if no identical packet is received from another communication terminal in the communication network during the suspension time,

wherein the single-path route is separated from the multipath route so that signals transmitted on the multipath route do not interfere with signals transmitted on the single-path route.

2. The communication terminal of claim 1, wherein the means for determining the suspension time determines the suspension time by monitoring signal conditions at other communication terminals in the communication network.

3. The communication terminal of claim 1, wherein the means for determining the suspension time determines the suspension time by monitoring packet transmission activity by the neighboring communication terminals on the single-path route.

4. The communication terminal of claim 1, wherein the means for determining the suspension time determines the suspension time by monitoring both signal conditions at other communication terminals in the communication network and packet transmission activity by the neighboring communication terminals on the single-path route.

5. The communication terminal of claim 1, wherein the means for determining the suspension time determines the suspension time randomly.

6. The communication terminal of claim 1, wherein the means for determining the suspension time determines the suspension time from a number of packet flows currently being relayed by the communication terminal.

7. The communication terminal of claim 6, wherein the means for suspending suspends packet transmission if the communication terminal is currently relaying more than a predetermined number of packet flows, even if the communication terminal is disposed on the single-path route.

8. The communication terminal of claim 1, wherein:

the means for analyzing obtains, as part of the routing information in a received packet, information identifying one terminal on the single-path route and one or more terminals on the multipath route that are to transmit the received packet next;

if the communication terminal is said one terminal on the single-path route, the means for placing updates said part of the routing information in the received packet and transmits the received packet immediately; and

if the communication terminal is among said one or more terminals on the multipath route, the means for suspending suspends the packet, and the means for placing updates said part of the routing information in the received packet and transmits the received packet if the received packet is not abandoned during the suspension time.

9. The communication terminal of claim 1, further comprising means for storing a table of entries listing communication terminal identifiers and packet identifiers, the communication terminal identifiers listed in each entry having fields for storing a destination terminal identifier, one primary terminal identifier of a next communication terminal on the single-path route to the destination terminal identified by the destination terminal identifier, and one or more secondary terminal identifiers identifying one or more next communication terminals on the multipath route to the destination terminal identified by the destination terminal identifier, wherein:

when the communication terminal receives a packet including a source terminal identifier identifying a communication terminal from which the packet originated, a neighboring terminal identifier identifying a communication terminal from which the packet was received, and a packet identifier identifying the packet, if the source terminal identifier and the packet identifier in the received packet match the destination terminal identifier and the packet identifier of an entry in said table, the means for analyzing adds the neighboring terminal identifier to said entry as a secondary communication terminal identifier, if the source terminal identifier in the received packet matches the destination terminal identifier of an entry in said table and the packet identifier in the received packet does not match the packet identifier in said entry the means for analyzing replaces the primary terminal identifier in the entry with the neighboring terminal identifier, replaces the packet identifier of the entry with the packet identifier of the received packet, and if the neighboring terminal entry is present in the secondary terminal identifier field of the entry, deletes the neighboring terminal entry from the secondary terminal identifier field of the entry, whereas if the source terminal identifier in the received packet does not match any destination terminal identifier in the table, the means for analyzing adds a new entry to the table, the new entry having the source terminal identifier of the received packet in its destination terminal identifier field, the neighboring terminal identifier of the received packet in its primary terminal identifier field, and the packet identifier of the received packet in its packet identifier field, and having no communication terminal identifier in its secondary terminal identifier field;

when the communication terminal receives a packet including a destination terminal identifier matching the destination terminal identifier of an entry in said table, if the packet also includes a primary terminal identifier identifying the communication terminal receiving the packet, the means for placing immediately transmits the packet, replacing the primary terminal identifier in the packet with the primary terminal identifier of said entry in the table, and replacing any secondary terminal identifiers in the packet, if present, with the secondary terminal identifiers of said entry in the table;

when the communication terminal receives a packet including a destination terminal identifier matching the destination terminal identifier of an entry in said table, if the packet also includes a secondary terminal identifier identifying the communication terminal receiving the packet, the means for suspending suspends transmission of the packet, and if the means for suspending does not abandon the packet during the suspension time, the means for placing transmits the packet upon expiration of the suspension time, replacing the primary terminal identifier in the packet with the primary terminal identifier of said entry in the table, and replacing any secondary terminal identifiers in the packet, if present, with the secondary terminal identifiers of said entry in the table; and

when the communication terminal receives a packet including a destination terminal identifier not matching the destination terminal identifier of any entry in said table, the received packet is abandoned.

10. A particular communication terminal for use in a communication network that includes a plurality of communication terminals, each of the communication terminals having:

means for generating routing information for routing packets from a source terminal to a destination terminal on both a single-path route in the communication network and a multipath route in the communication network, the source terminal and the destination terminal being an arbitrary pair of the communication terminals in the communication network;

means for placing said routing information in packets and transmitting said packets to neighboring communication terminals in the communication network; and

means for analyzing the routing information in packets received from said neighboring terminals in the communication network,

wherein the single-path route is separated from the multipath route so that signals transmitted on the multipath route do not interfere with signals transmitted on the single-path route,

wherein the multipath route is spatially separated from the single-path route by using the routing information to designate a first zone and a second zone in the communication network, the single-path route being disposed in the first zone, the multipath route being disposed in the second zone, and

wherein the particular communication terminal further comprises means for selecting at least;

a first operating mode in which the means for placing transmits a received packet addressed to the destination terminal only if the communication terminal is in the first zone;

a second operating mode in which the means for placing transmits the received packet only if the communication terminal is in the second zone; and

a third operating mode in which the means for placing transmits the received packet if the communication terminal is in either the first zone or the second zone.

11. A communication networks, comprising a plurality of communication terminals, each of the communication terminals having:

means for generating routing information for routing packets from a source terminal to a destination terminal on both a single-path route in the communication network and a multipath route in the communication network, the source terminal and the destination terminal being an arbitrary pair of the communication terminals in the communication network;

means for placing said routing information in packets and transmitting said packets to neighboring communication terminals in the communication network; and

means for analyzing the routing information in packets received from said neighboring terminals in the communication network,

wherein the single-path route is separated from the multipath route so that signals transmitted on the multipath route do not interfere with signals transmitted on the single-path route,

wherein the multipath route is spatially separated from the single-path route by using the routing information to designate a first zone and a second zone in the communication network, the single-path route being disposed in the first zone, the multipath route being disposed in the second zone, and

wherein at least one communication terminal on the single-path route is designated as a median terminal, the first zone including all communication terminals within the communication network that are within a first number of hops of the median terminal, the second zone including all communication terminals in the communication network that are within a second number of hops from the median terminal and are outside the first zone, the second number being larger than the first number.

12. A particular communication terminal for use in a communication network that includes a plurality of communication terminals, each of the communication terminals having:

means for generating routing information for routing packets from a source terminal to a destination terminal on both a single-path route in the communication network and a multipath route in the communication network, the source terminal and the destination terminal being an arbitrary pair of the communication terminals in the communication network;

means for placing said routing information in packets and transmitting said packets to neighboring communication terminals in the communication network; and

means for analyzing the routing information in packets received from said neighboring terminals in the communication network,

wherein the single-path route is separated from the multipath route so that signals transmitted on the multipath route do not interfere with signals transmitted on the single-path route,

wherein the multipath route is spatially separated from the single-path route by using the routing information to designate a first zone and a second zone in the communication network, the single-path route being disposed in the first zone, the multipath route being disposed in the second zone, and

wherein the particular communication terminal further comprises a first table and a second table, and wherein;

when the communication terminal receives, from an arbitrary neighboring terminal in the communication network, a packet originating at an arbitrary distant terminal in the communication network, the means for analyzing obtains identifiers of the neighboring terminal and distant terminal from the packet and stores the identifiers of the neighboring terminal and the distant terminal in the first table, designating the neighboring terminal as the next terminal on a single-path route to the distant terminal if the neighboring terminal is the first terminal from which the communication terminal receives the packet;

if the communication terminal is said source terminal, the means for generating generates hopcount information from the first number of hops and the second number of hops and generates a pair of endpoint terminal identifiers identifying the source terminal and the destination terminal, and the means for placing transmits the hopcount information and the pair of endpoint terminal identifiers in an assignment packet addressed to the median terminal; and

if the communication terminal is the median terminal, the means for placing places the hopcount information, time-to-live information, and the pair of endpoint terminal identifiers in a zone control packet and transmits the zone control packet;

if the communication terminal receives the zone control packet, the means for analyzing determines, from the hopcount information and the time-to-live information, whether the communication terminal is in the second zone, and stores the pair of endpoint terminal identifiers in the second table if the communication terminal is in the second zone, and if the time-to-live hopcount is not zero, the means for placing updates the time-to-live information and transmits the packet with the updated time-to-live information;

if the communication terminal is said source terminal, when the communication terminal transmits a packet addressed to the destination terminal, the means for placing places identifiers of the source terminal and the destination terminal and the identifier of a nearest neighboring terminal, on the single-path route to the destination terminal, in the packet as said routing information;

when the communication terminal receives a packet addressed from the source terminal to the destination terminal, the means for analyzing uses the first table and the second table to determine whether the communication terminal is the next terminal on the single-path route to the destination terminal or the communication terminal is in the second zone, and if the communication terminal is the next terminal on the single-path route to the destination terminal or is in the second zone, the means for placing updates the routing information in the packet and transmits the packet.

13. A communication network, comprising a plurality of communication terminals, each of the communication terminals having:

means for generating routing information for routing packets from a source terminal to a destination terminal on both a single-path route in the communication network and a multipath route in the communication network, the source terminal and the destination terminal being an arbitrary pair of the communication terminals in the communication network;

means for placing said routing information in packets and transmitting said packets to neighboring communication terminals in the communication network; and

means for analyzing the routing information in packets received from said neighboring terminals in the communication network,

wherein the single-path route is separated from the multipath route so that signals transmitted on the multipath route do not interfere with signals transmitted on the single-path route,

wherein the multipath route is spatially separated from the single-path route by using the routing information to designate a first zone and a second zone in the communication network, the single-path route being disposed in the first zone, the multipath route being disposed in the second zone, and

wherein the second zone is subdivided into;

an inner subzone in which received packets addressed to the destination terminal are transmitted immediately; and

an outer subzone in which the received packets addressed to the destination terminal are suspended temporarily at each communication terminal on the multipath route.

14. The communication network of claim 13, wherein the outer subzone is further subdivided into subzones with respective suspension times that increase with increasing distance from the first zone.