Routing algorithm for distributed telecommunication networks

• US 7,123,908 B2
• Filed: 11/21/2001
• Issued: 10/17/2006
• Est. Priority Date: 11/28/2000
• Status: Expired due to Fees

• Current Assignee: Stephen Anthony Gerard Chandler
• Original Assignee: Stephen Anthony Gerard Chandler
• Inventors: Chandler, Stephen Anthony Gerard
• Primary Examiner(s): Ramakrishnaiah, Melur
• Application Number:
  US10/416,960
• Publication Number:
  US 20040029528A1
• Time in Patent Office: 1,791 Days
• Field of Search: 455/428, 455/12.1, 455/452.2, 455/513, 455/67.11, 455/69, 455/500, 455/554.1, 455/445, 370/238, 370/400, 370/237, 370/252, 370/255, 370/392
• US Class Current: 455/428
• 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: H04Q 2213/13056 Routines, finite state machines
• CPC Class Codes: H04Q 2213/13106 Microprocessor, CPU
• CPC Class Codes: H04Q 2213/13141 Hunting for free outlet, circuit or channel
• CPC Class Codes: H04Q 2213/13191 Repeater
• CPC Class Codes: H04Q 2213/13196 Connection circuit/link/trunk/junction, bridge, router, gateway
• CPC Class Codes: H04Q 2213/13204 Protocols
• CPC Class Codes: H04Q 2213/13342 Arrangement of switches in the network
• CPC Class Codes: H04Q 2213/13352 Self-routing networks, real-time routing
• CPC Class Codes: H04Q 2213/13353 Routing table, map memory
• CPC Class Codes: H04Q 2213/13388 Saturation signaling systems
• CPC Class Codes: H04Q 3/66 Traffic distributors
• CPC Class Codes: H04W 40/02 Communication route or path selection, e.g. power-based or shortest path routing
• CPC Class Codes: H04W 40/246 Connectivity information discovery
• CPC Class Codes: H04W 40/30 for proactive routing
• CPC Class Codes: H04W 88/04 adapted for relaying to or from another terminal or user

Abstract

In a telecommunication network a plurality of transmitting and receiving stations are provided at randomly distributed locations. Routing elements are provided for routing of calls between stations in the network utilizing other stations in the network for relaying of such calls where necessary. Each station incorporates a call routing control unit acting to select a further station to which a call is to be transmitted for the purpose of relaying the call and comprising a memory for compiling, for a plurality of possible destination stations and from information received from further stations within the network within range of the transmitting station, information on possible further stations which may be suitable for relaying calls to the destination stations.

Claims

1. A transmitting and receiving station for a telecommunication network in which a plurality of such stations are to be provided at randomly distributed locations and in which routing means are provided for routing of call setup information between stations in the network utilising other stations in the network acting as relay stations for relaying of such call setup information where necessary, which station incorporates call routing control means acting to select a relay station to which call setup information is to be transmitted for the purpose of relaying call setup information to a required destination station and comprising:

(a) memory means for storing, for a plurality of possible destination stations and from network status signals received from further stations within the network, the cumulative cost associated with the notional use of possible relay stations for relaying call setup information to the destination stations;

(b) compiling means for compiling in the memory means the cumulative cost associated with the notional use of possible relay stations for relaying call setup information to the destination stations, the compiling means being adapted to update the cumulative cost associated with the relay stations in the memory means in dependence on network status signals originating from the destination stations and relayed by relay stations to other stations in the network;

(c) overhearing means for receiving a network status signal transmitted by a further station in the network within range, whether or not the station is the intended recipient of call setup information transmitted by said further station, said network status signal being indicative of the cost of routing information to a source station from which the call setup information originates, being the sum of the cost information received from the previous relay station (where said further station is not the source station) and some incremental cost, together with the identities of said further station and the source station;

(d) transmission means for transmitting call setup information to at least one recipient station in the network within range and for additionally transmitting a network status signal;

(e) reception means for receiving call setup information from the transmission means of at least one further station in the network within range; and

(f) station selection means for selecting a relay station for relaying call setup information to a destination station on the basis of receipt of a signal providing acknowledgement of the acceptance of the request from a station judged by the memory means to be suitable for relaying call setup information to the destination station.

2. A station according to claim 1, wherein the call routing control means incorporates precedence means for establishing a precedence amongst the further stations judged, at least in part by the memory means from the cost information received from the further stations relaying to the destination station, to be suitable for relaying the call setup information to the destination station, the station selection means being adapted to preferentially select as the station for relaying the call setup information the station of the highest precedence which is available for relaying the call setup information.

3. A station according to claim 2, wherein the precedence means is adapted to establish precedence at least partly on the basis of minimising a cost, such as the number of stations involved in relaying the call setup information to the destination station,

the station, the station selection means being adapted to preferentially select as the station for relaying the call setup information the station at the least distance from the destination station.

4. A station according to claim 2, wherein the cost is determined at least partly on the basis of the signal traffic congestion at the station in question.

5. A station according to claim 2, wherein the cost is determined at least partly on the basis of the likely delay through the station.

6. A station according to claim 1, wherein the call routing control means incorporates direct routing means arranged to cause a routing signal to be transmitted to at least one further station within range in the event that none of the stations judged suitable by the memory means is available for relaying the call setup information to the destination station, enabling a routing signal to be transmitted back to the station, the station selection means being adapted to the preferentially select as the station for relaying the call setup information the station at the least distance from the destination station.

7. A station according to claim 1, wherein the call routing control means incorporates flood routing means arranged to cause a routing signal identifying the transmitting station to be transmitted to further stations within range in the event that none of the stations judged suitable by the memory means is available for relaying the call setup information to the destination station, receipt of the routing signals by the further stations in turn causing those stations to transmit further routing signals identifying the further stations which in turn may cause still further stations to transmit routing signals in an iterative process which eventually results in receipt of a routing signal by the destination station, enabling an acknowledgement signal to be transmitted back to the transmitting station giving the identities of a series of stations suitable for relaying the call setup information between the transmitting station and the destination station.

8. A station according to claim 1, wherein the memory means incorporates a table NNT containing information relating to the current activity states of further stations within range of the transmitting station and optionally also other parameters such as the operating frequencies and signal strengths of the further stations.

9. A station according to claim 1, which is adapted for routing data packets within a data network.

10. A data network incorporating stations according to claim 9 for routing data packets within the network.