Method and apparatus to provide a routing protocol for wireless devices

• US 6,704,301 B2
• Filed: 12/29/2000
• Issued: 03/09/2004
• Est. Priority Date: 12/29/2000
• Status: Expired due to Term

• Current Assignee: Hitachi Energy Switzerland AG (Hitachi, Ltd.)
• Original Assignee: Tropos Networks Incorporated (ABB Limited)
• Inventors: Srikrishna, Devabhaktuni, Chari, Amalavoyal Narasimha
• Primary Examiner(s): APPIAH, CHARLES NANA
• Application Number:
  US09/751,262
• Publication Number:
  US 20020107023A1
• Time in Patent Office: 1,166 Days
• Field of Search: 370/254, 370/255, 370/238, 370/351, 370/400, 370/338, 370/256, 370/331, 455/463, 455/454, 455/445, 455/452, 455/453, 709/227
• US Class Current: 370/351
• CPC Class Codes: H04L 45/20 Hop count for routing purposes, e.g. TTL
• CPC Class Codes: H04W 40/02 Communication route or path selection, e.g. power-based or shortest path routing
• CPC Class Codes: H04W 40/10 based on available power or energy
• CPC Class Codes: H04W 40/12 based on transmission quality or channel quality
• CPC Class Codes: H04W 40/246 Connectivity information discovery
• CPC Class Codes: H04W 40/26 for hybrid routing by combining proactive and reactive routing
• CPC Class Codes: H04W 40/32 for defining a routing cluster membership
• CPC Class Codes: H04W 88/04 adapted for relaying to or from another terminal or user

Abstract

A method and apparatus for generating connectivity is described. The method includes a server broadcasting a beacon including the server'"'"'s address. The method further includes each client that receives the beacon rebroadcasting the beacon. The result is that each client receiving the beacon knows a way to reach the server.

Claims

1. A method of wireless connectivity comprising:

broadcasting a beacon by a server;

receiving and storing every beacon received by a client, the client further retaining information indicative of a path to the server;

designating one path identified by one beacon as the optimal path;

setting a default gateway as identified in the optimal path; and

rebroadcasting only the beacon representing the optimal path.

2. The method of claim 1, wherein the beacon broadcast by the server includes a hop-count set to zero, the method further comprising:

each client that receives the beacon rebroadcasting the beacon with the hop-count incremented by one;

such that each client receiving the beacon knows a way to reach the server and the number of hops in this path.

3. The method of claim 1, wherein the beacon broadcast by the server includes server address, such that each client receiving the beacon knows the address of the server.

4. The method of claim 1 further comprising:

each client that receives the beacon rebroadcasting the beacon with an address of the client added to the beacon;

such that each client receiving the beacon has a complete path to the server.

5. The method of claim 1, wherein the beacon includes a sequence number representing a current routing cycle.

6. The method of claim 1, further comprising:

determining if there is a previous default gateway identified; and

deleting the previous default gateway from memory.

7. The method of claim 1, further comprising, for each client:

collecting all beacons; and

selecting a single beacon to rebroadcast.

8. The method of claim 7, wherein selecting a beacon comprises:

identifying a number of hops between the server and the client for each beacon; and

selecting the beacon with the lowest number of hops.

9. The method of claim 1, further comprising:

sending a reverse beacon to the server; and

constructing a client tree in the server, wherein the server has a path to all clients.

10. A method of wireless connectivity comprising:

broadcasting a beacon by a server, the beacon including a sequence number representing a current routing cycle;

receiving and storing the beacon at the client, the client further retaining information indicative of a path to the server;

rebroadcasting the beacon by the client;

upon a client receiving a beacon, determining if a beacon has already been received for this routing cycle; and

if no beacon has already been received for the routing cycle, storing a routing path to the server from the beacon.

11. The method of claim 10, further comprising, if the beacon has already been received for the routing cycle:

determining if this beacon has a higher sequence number than a prior beacon for this routing cycle, and if so,

storing the current beacon in memory.

12. A method of wireless connectivity comprising:

broadcasting a beacon by a server, the beacon including a sequence number representing a current routing cycle;

receiving and storing the beacon at the client, the client further retaining information indicative of a path to the server;

rebroadcasting the beacon by the client;

wherein the beacon includes a sequence number representing a current routing cycle;

upon a client receiving a beacon, determining if a currently received beacon represents an optimal path for this routing cycle; and

if the current beacon represents the optimal path, identifying a default gateway in the current beacon, and storing the default gateway.

13. The method of claim 12, further comprising:

determining if there is a previous default gateway identified; and

deleting the previous default gateway from memory.

14. The method of claim 12, further comprising, for each client:

collecting all beacons; and

selecting a single beacon to rebroadcast.

15. The method of claim 14, wherein selecting a beacon comprises:

identifying a number of hops between the server and the client for each beacon; and

selecting the beacon with the lowest number of hops.

16. The method of claim 12, further comprising:

sending a reverse beacon to the server; and

constructing a client tree in the server, wherein the server has a path to all clients.

20. The method of claim 12, wherein the highest quality is based on most back end bandwidth capacity at the server.

21. The method of claim 12, wherein the highest quality is based on a lowest level of traffic being handled by the server.

17. A method of wireless connectivity comprising:

broadcasting a beacon by a server; and

receiving and storing the beacon at the client, the client further retaining information indicative of a path to the server;

rebroadcasting the beacon by the client;

further comprising, for each client;

collecting all beacons; and

selecting a single beacon to rebroadcast;

wherein selecting a beacon comprises;

identifying a traffic monitoring code (TMC) for each of the beacons; and

selecting the beacon with the lowest TMC.

18. A method of wireless connectivity comprising:

broadcasting a beacon by a server; and

receiving and storing the beacon at the client, the client further retaining information indicative of a path to the server;

rebroadcasting the beacon by the client;

further comprising, for each client;

collecting all beacons; and

selecting a single beacon to rebroadcast;

wherein selecting a beacon comprises;

identifying a beacon with a highest quality; and

selecting the beacon with the highest quality.

19. The method of claim 18, wherein the highest quality is a best signal-to-noise ratio.

22. A method of generating a routing path for a system including a server and a plurality of clients, the method comprising each client:

receiving a beacon from the server;

rebroadcasting one beacon received from an upstream node; and

broadcasting a reverse beacon upstream, the reverse beacon being addressed to the known upstream node, the reverse beacon used by the server and each client to set up a routing table;

wherein

receiving a reverse beacon broadcast by a client'"'"'s default gateway triggers the client to start a timer to send the reverse beacon.

23. A method of generating a routing path for a system including a server and a plurality of clients, the method comprising each client:

receiving a beacon from the server;

rebroadcasting one beacon received from an upstream node; and

broadcasting a reverse beacon upstream, the reverse beacon being addressed to the known upstream node, the reverse beacon used by the server and each client to set up a routing table;

further comprising, if a client receives multiple beacons;

evaluating a link quality of each of the beacons received; and

selecting the default gateway based on the beacon with the best link quality and rebroadcasting that beacon.

24. The method of claim 23, wherein the link quality comprises reliability of the beacon.

25. The method of claim 23, wherein the link quality includes information about the back end bandwidth capacity of the server.

26. The method of claim 23, wherein the link quality includes information about the traffic being handled by the server.

27. The method of claim 23, wherein a connection between the server and the client is a wireless connection.

28. The method of claim 23, wherein a connection between the server and the client is chosen from among the following types of connections:

a wireless connection, a wired connection, and a switched connection.

29. A method of generating a routing path for a system including a server and a plurality of clients, the method comprising each client:

receiving a beacon from the server;

rebroadcasting one beacon received from an upstream node; and

broadcasting a reverse beacon upstream, the reverse beacon being addressed to the known upstream node, the reverse beacon used by the server and each client to set up a routing table;

further comprising the client;

receiving a plurality of beacons from a plurality of servers; and

selecting one of the plurality of beacons, and setting the server associated with the selected beacon as its preferred server;

thereby self-selecting to belong in a cluster associated with the preferred server.

30. The method of claim 29, further comprising the client:

moving outside the cluster;

upon receiving a beacon from a new cluster, the client setting the server associated with the new beacon and the new cluster as its preferred server.

31. The method of claim 30, further comprising:

expiring a routing table including a previous preferred server and previous default gateway.