Communication network having a plurality of bridging nodes which transmits a polling message with backward learning technique to determine communication pathway

• US 7,899,951 B2
• Filed: 08/18/2008
• Issued: 03/01/2011
• Est. Priority Date: 05/13/1991
• Status: Expired due to Fees

• Current Assignee: Avago Technologies International Sales Pte Limited (Broadcom, Inc.)
• Original Assignee: Broadcom Corporation (Broadcom, Inc.)
• Inventors: Meier, Robert C., Mahany, Ronald L., Luse, Ronald E.
• Primary Examiner(s): PEYTON, TAMMARA R
• Application Number:
  US12/193,168
• Publication Number:
  US 20090046602A1
• Time in Patent Office: 925 Days
• Field of Search: 710/18, 710/46, 709/227, 709/304, 713320-324, 455/342, 455/517, 455/524, 375/132, 375/202, 375/220, 370/329, 370/351
• US Class Current: 710/18
• CPC Class Codes: G06F 15/0225 User interface arrangements, e.g. keyboard, display; Interfaces to other computer systems
• CPC Class Codes: G06K 7/1098 the scanning arrangement having a modular construction
• CPC Class Codes: G08C 17/02 using a radio link
• CPC Class Codes: G08C 2201/20 Binding and programming of remote control devices
• CPC Class Codes: H01Q 1/007 specially adapted for indoor communication
• CPC Class Codes: H01Q 1/241 used in mobile communications, e.g. GSM H01Q1/247, H01Q1/248 take precedence
• CPC Class Codes: H01Q 21/24 Combinations of antenna units polarised in different directions for transmitting or receiving circularly and elliptically polarised waves or waves linearly polarised in any direction circularly polarised patch antennas H01Q9/0428; circularly polarised horns H01Q13/0241; cross-polarised horns H01Q13/0258; polarisation converters H01Q15/242; cross-polarised rear feeds H01Q19/136; crossed polarisation dual antenna H01Q25/001
• CPC Class Codes: H04B 1/1615 Switching on; Switching off, e.g. remotely battery saving circuits associated with selective call operation H04W52/00; details of power consumption reduction in a PLL, H03L7/0802, H03L7/14, H03L2207/08, H03L2207/18; muting amplifiers by gain control see H03G3/34
• CPC Class Codes: H04B 1/3833 Hand-held transceivers
• CPC Class Codes: H04B 1/69 Spread spectrum techniques
• CPC Class Codes: H04B 17/0085 using test signal generators
• CPC Class Codes: H04B 17/318 Received signal strength
• CPC Class Codes: H04L 1/0003 by switching between different modulation schemes
• CPC Class Codes: H04L 1/0007 by modifying the frame length
• CPC Class Codes: H04L 1/0014 by adapting the source coding
• CPC Class Codes: H04L 1/0025 Transmission of mode-switching indication
• CPC Class Codes: H04L 1/0032 Without explicit signalling
• CPC Class Codes: H04L 1/0071 Use of interleaving interleaving per se H03M13/27
• CPC Class Codes: H04L 1/08 by repeating transmission, e.g. Verdan system H04L1/1858 and H04L1/189 take precedence
• CPC Class Codes: H04L 12/12 Arrangements for remote connection or disconnection of substations or of equipment thereof
• CPC Class Codes: H04L 12/4625 : Single bridge functionality, e.g. connection of two networks over a single bridge
• CPC Class Codes: H04L 2001/0097 : Relays
• CPC Class Codes: H04L 45/026 : Details of "hello" or keep-alive messages
• CPC Class Codes: H04L 45/26 : Route discovery packet
• CPC Class Codes: H04L 45/36 : Backward learning
• CPC Class Codes: H04L 45/44 : Distributed routing
• CPC Class Codes: H04L 45/48 : Routing tree calculation
• CPC Class Codes: H04L 45/488 : using root node determination
• CPC Class Codes: H04L 69/14 : Multichannel or multilink protocols
• CPC Class Codes: H04L 69/18 : Multiprotocol handlers, e.g. single devices capable of handling multiple protocols
• CPC Class Codes: H04L 69/32 : Architecture of open systems interconnection [OSI] 7-layer type protocol stacks, e.g. the interfaces between the data link level and the physical level
• CPC Class Codes: H04L 69/324 : in the data link layer [OSI layer 2], e.g. HDLC
• CPC Class Codes: H04L 69/325 : in the network layer [OSI layer 3], e.g. X.25 H04L69/16 takes precedence
• CPC Class Codes: H04L 69/326 : in the transport layer [OSI layer 4] H04L69/16 takes precedence
• CPC Class Codes: H04L 9/40 : Network security protocols
• CPC Class Codes: H04W 40/246 : Connectivity information discovery
• CPC Class Codes: H04W 40/248 : Connectivity information update
• CPC Class Codes: H04W 52/0225 : using monitoring of external events, e.g. the presence of a signal
• CPC Class Codes: H04W 52/029 : reducing the clock frequency of the controller
• CPC Class Codes: H04W 52/343 : taking into account loading or congestion level
• CPC Class Codes: H04W 84/18 : Self-organising networks, e.g. ad-hoc networks or sensor networks
• CPC Class Codes: Y02D 30/70 : in wireless communication networks

Abstract

An apparatus and a method for routing data in a radio data communication system having one or more host computers, one or more intermediate base stations, and one or more RF terminals organizes the intermediate base stations into an optimal spanning-tree network to control the routing of data to and from the RF terminals and the host computer efficiently and dynamically. Communication between the host computer and the RF terminals is achieved by using the network of intermediate base stations to transmit the data.

Claims

1. A terminal node for use in a multi-hop data communication network having RF capability and a plurality of bridging nodes that operate to dynamically create and revise communication pathways between nodes in the network, where the terminal node operates to, at least:

receive a first message from a bridging node of the plurality of bridging nodes; and

responsive at least in part to the received first message, communicate a second message to the bridging node, where the second message comprises characteristics that are used by the bridging node, through a backward learning technique, to independently create and/or maintain locally stored information that specifies how communication traffic should flow through the bridging node.

2. The terminal node of claim 1, where the first message comprises information that is based, at least in part, on communication link conditions.

3. The terminal node of claim 1, where the first message comprises a HELLO message.

4. The terminal node of claim 1, where the first message comprises a polling message.

5. The terminal node of claim 1, where the first message is a first particular type of message, and wherein the terminal node operates to periodically receive messages of the first particular type at substantially constant periodic intervals.

6. The terminal node of claim 5, wherein each of at least a portion of the substantially constant periodic intervals comprises a random component that is calculated prior to transmission of a respective message of the first particular type.

7. The terminal node of claim 5, wherein each of at least a portion of the substantially constant periodic intervals comprises a random component that is calculated by both the bridging node and the terminal node prior to transmission of a respective message of the first particular type.

8. The terminal node of claim 1, where the first message comprises a beacon message.

9. The terminal node of claim 1, where the first message is a first particular type of message and comprises timing information, and wherein the terminal node operates to synchronize reception of a future message of the first particular type based, at least in part, on said timing information.

10. The terminal node of claim 1, wherein the terminal node operates to:

determine communication link conditions; and

generate the second message based, at least in part, on the determined communication link conditions.

11. The terminal node of claim 10, wherein the terminal node operates to determine information to include in the second message based, at least in part, on the determined communication link conditions.

12. The terminal node of claim 10, wherein the terminal node operates to address the second message to the bridging node based, at least in part, on the determined communication link conditions.

13. The terminal node of claim 1, where the second message comprises characteristics that cause the bridging node to enter and/or maintain information of the terminal node in a routing table.

14. The terminal node of claim 1, where the second message comprises characteristics that cause the bridging node to communicate a third message to a third node of the communication network.

15. The terminal node of claim 14, where the third node is a second bridging node of the communication network.

16. The terminal node of claim 15, where the third message comprises characteristics that cause the second bridging node to enter and/or maintain locally stored information that specifies how communication traffic should flow through the second bridging node.

17. The terminal node of claim 1, where the second message comprises an attach request.

18. The terminal node of claim 1, where the second message comprises a data packet.

19. The terminal node of claim 1, where the first message is a first type of message, and wherein the terminal node operates to:

receive another of the first type of message from a second bridging node; and

responsive, at least in part, to the received first message and the received another of the first type of message, communicate the second message to the bridging node.

20. The terminal node of claim 19, wherein the terminal node operates to, responsive at least in part to the received first message and the received another of the first type of message, communicate a third message to the second bridging node, where the third message comprises characteristics that cause the second bridging node, through a backward learning technique, to independently create and/or maintain locally stored information that specifies how communication traffic should flow through the second bridging node.

21. A terminal node for use in a multi-hop wireless data communication network comprising a plurality of bridging nodes, where the terminal node operates to, at least:

receive a first message broadcast from a bridging node of the wireless communication network; and

responsive at least in part to the received first message, communicate a second message to the bridging node, where the second message comprises characteristics that are used by the bridging node, through a backward learning technique, to independently create and/or maintain locally stored information that specifies how communication traffic should flow through the bridging node.

22. The terminal node of claim 21, where the first message comprises information that is based, at least in part, on communication link conditions.

23. The terminal node of claim 21, where the first message comprises a HELLO message.

24. The terminal node of claim 21, where the first message comprises a polling message.

25. The terminal node of claim 21, where the first message is a first particular type of message, and wherein the terminal node operates to periodically receive messages of the first particular type at substantially constant periodic intervals.

26. The terminal node of claim 25, wherein each of at least a portion of the substantially constant periodic intervals comprises a random component that is calculated prior to transmission of a respective message of the first particular type.

27. The terminal node of claim 25, wherein each of at least a portion of the substantially constant periodic intervals comprises a random component that is calculated by both the bridging node and the terminal node prior to transmission of a respective message of the first particular type.

28. The terminal node of claim 21, where the first message comprises a beacon message.

29. The terminal node of claim 21, where the first message is a first particular type of message and comprises timing information, and wherein the terminal node operates to synchronize reception of a future message of the first particular type based, at least in part, on said timing information.

30. The terminal node of claim 21, wherein the terminal node operates to:

determine communication link conditions; and

generate the second message based, at least in part, on the determined communication link conditions.

31. The terminal node of claim 30, wherein the terminal node operates to determine information to include in the second message based, at least in part, on the determined communication link conditions.

32. The terminal node of claim 30, wherein the terminal node operates to address the second message to the bridging node based, at least in part, on the determined communication link conditions.

33. The terminal node of claim 21, where the second message comprises characteristics that cause the bridging node to enter and/or maintain information of the terminal node in a routing table.

34. The terminal node of claim 21, where the second message comprises characteristics that cause the bridging node to communicate a third message to a third node of the communication network.

35. The terminal node of claim 34, where the third node is a second bridging node of the communication network.

36. The terminal node of claim 35, where the third message comprises characteristics that cause the second bridging node to enter and/or maintain locally stored information that specifies how communication traffic should flow through the second bridging node.

37. The terminal node of claim 21, where the second message comprises an attach request.

38. The terminal node of claim 21, where the second message comprises a data packet.

39. The terminal node of claim 21, where the first message is a first type of message, and wherein the terminal node operates to:

receive another of the first type of message from a second bridging node; and

responsive, at least in part, to the received first message and the received another of the first type of message, communicate the second message to the bridging node.

40. The terminal node of claim 39, wherein the terminal node operates to, responsive at least in part to the received first message and the received another of the first type of message, communicate a third message to the second bridging node, where the third message comprises characteristics that cause the second bridging node, through a backward learning technique, to independently create and/or maintain locally stored information that specifies how communication traffic should flow through the second bridging node.

41. A terminal node for use in a wireless communication network, where the terminal node operates to, at least:

receive a first message from a bridging node of a wireless communication network; and

responsive at least in part to the received first message, generate a second message for the bridging node, where the second message comprises characteristics that are used by the bridging node to independently create and/or maintain locally stored information that specifies how communication traffic should flow through the bridging node.

42. The terminal node of claim 41, where the first message comprises information that is based, at least in part, on communication link conditions.

43. The terminal node of claim 41, where the first message comprises a HELLO message.

44. The terminal node of claim 41, where the first message comprises a polling message.

45. The terminal node of claim 41, where the first message is a first particular type of message, and wherein the terminal node operates to periodically receive messages of the first particular type at substantially constant periodic intervals.

46. The terminal node of claim 45, wherein each of at least a portion of the substantially constant periodic intervals comprises a random component that is calculated prior to transmission of a respective message of the first particular type.

47. The terminal node of claim 45, wherein each of at least a portion of the substantially constant periodic intervals comprises a random component that is calculated by both the bridging node and the terminal node prior to transmission of a respective message of the first particular type.

48. The terminal node of claim 41, where the first message comprises a beacon message.

49. The terminal node of claim 41, where the first message is a first particular type of message and comprises timing information, and wherein the terminal node operates to synchronize reception of a future message of the first particular type based, at least in part, on said timing information.

50. The terminal node of claim 41, wherein the terminal node operates to:

determine communication link conditions; and

generate the second message based, at least in part, on the determined communication link conditions.

51. The terminal node of claim 50, wherein the terminal node operates to determine information to include in the second message based, at least in part, on the determined communication link conditions.

52. The terminal node of claim 50, wherein the terminal node operates to address the second message to the bridging node based, at least in part, on the determined communication link conditions.

53. The terminal node of claim 41, where the second message comprises characteristics that cause the bridging node to enter and/or maintain information of the terminal node in a routing table.

54. The terminal node of claim 41, where the second message comprises characteristics that cause the bridging node to communicate a third message to a third node of the communication network.

55. The terminal node of claim 54, where the third node is a second bridging node of the communication network.

56. The terminal node of claim 55, where the third message comprises characteristics that cause the second bridging node to enter and/or maintain locally stored information that specifies how communication traffic should flow through the second bridging node.

57. The terminal node of claim 41, where the second message comprises an attach request.

58. The terminal node of claim 41, where the second message comprises a data packet.

59. The terminal node of claim 41, where the first message is a first type of message, and wherein the terminal node operates to:

receive another of the first type of message from a second bridging node; and

responsive, at least in part, to the received first message and the received another of the first type of message, communicate the second message to the bridging node.

60. The terminal node of claim 59, wherein the terminal node operates to, responsive at least in part to the received first message and the received another of the first type of message, communicate a third message to the second bridging node, where the third message comprises characteristics that cause the second bridging node, through a backward learning technique, to independently create and/or maintain locally stored information that specifies how communication traffic should flow through the second bridging node.