Method and apparatus for transmission of node link status messages throughout a network with reduced communication protocol overhead traffic

• US 6,385,174 B1
• Filed: 11/06/2000
• Issued: 05/07/2002
• Est. Priority Date: 11/12/1999
• Status: Expired due to Fees

• Current Assignee: Stingray IP Solutions LLC (Acacia Research Corporation)
• Original Assignee: ITT Manufacturing Enterprises, Inc. (ITT, Inc.)
• Inventors: Li, Chris Cho-Pin
• Primary Examiner(s): Chin, Wellington
• Assistant Examiner(s): JONES, PRENELL P
• Application Number:
  US09/705,822
• Time in Patent Office: 547 Days
• Field of Search: 370/252-256, 370/448, 370/462, 370/408-411, 370/350-351, 370/237, 370/433, 370/355, 370/506, 370/375, 370/376, 370/420, 370/524, 370/220, 370/360, 703/17, 709/238-243, 455/426, 455/552, 455/414, 455/74.1, 455/504, 375/347, 379/269, 379/274
• US Class Current: 370/252
• CPC Class Codes: H04L 45/028 Dynamic adaptation of the update intervals, e.g. event-triggered updates
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/46 Cluster building
• CPC Class Codes: H04W 28/06 Optimizing the usage of the radio link, e.g. header compression, information sizing , discarding information system modifying transmission characteristic according to link quality by modifying frame length H04L1/0007; dynamic adaptation of the packet size for flow control or congestion control H04L47/365
• CPC Class Codes: H04W 4/06 Selective distribution of broadcast services, e.g. multimedia broadcast multicast service [MBMS]; Services to user groups; One-way selective calling services
• CPC Class Codes: H04W 4/12 Messaging; Mailboxes; Announcements
• CPC Class Codes: H04W 40/24 Connectivity information management, e.g. connectivity discovery or connectivity update
• CPC Class Codes: H04W 40/248 Connectivity information update
• CPC Class Codes: H04W 40/30 for proactive routing
• CPC Class Codes: H04W 40/32 for defining a routing cluster membership
• CPC Class Codes: H04W 8/26 Network addressing or numbering for mobility support
• CPC Class Codes: H04W 84/20 Master-slave selection or change arrangements
• CPC Class Codes: H04W 88/06 adapted for operation in multiple networks or having at least two operational modes, e.g. multi-mode terminals

Abstract

A wireless network includes a plurality of nodes arranged into clusters with each cluster having cluster member nodes and a designated cluster head node. The nodes communicate with each other via an intranet protocol, while the network may communicate with other external networks in accordance with an internetworking protocol (e.g., a Radio Open Shortest Path First (ROSPF) protocol). A database within each network node contains link information for that node, while ROSPF Link-State Advertisement (LSA) type packets or database update messages contain information to update the node databases. The ROSPF LSA type packets are transmitted to neighbors of each node to enable each database to maintain current information. In order to reduce overhead of transmitting numerous LSA type packets, the present invention transmits the ROSPF LSA type packet within an intranet protocol beacon type or node status packet that is periodically broadcasted within the network.

Claims

1. In a communications network, a communication unit to transmit and receive messages within said network comprising:

a transmitter to transmit an outgoing message to at least one other communication unit within said network;

a receiver to receive an incoming message from at least one other communication unit within said network; and

a processor to control said transmission and reception of said outgoing and incoming messages, wherein said processor includes;

a broadcast module to facilitate periodic transmission of a unit message to said at least one other communication unit, wherein said unit message includes information relating to a status of said communication unit; and

a message module to insert a broadcast message within said unit message to facilitate transmission of said broadcast message to said at least one other communication unit in conjunction with transmission of said unit message.

2. The unit of claim 1 wherein said transmitter transmits said outgoing message in the form of radio signals.

3. The unit of claim 1 wherein said receiver receives said incoming message in the form of radio signals.

4. The unit of claim 1 wherein said processor further includes a storage unit to store said broadcast message until a succeeding transmission time for said unit message.

5. The unit of claim 4 wherein said storage unit stores a plurality of broadcast messages, and said message module inserts at least one of said stored messages within said unit message.

6. The unit of claim 1 wherein said processor further includes:

an internal communications module to facilitate communications within said network in accordance with an intranet protocol; and

an external communications module to facilitate communications between said network and an external network in accordance with an internetworking protocol.

7. The unit of claim 6 wherein said internetworking protocol includes a Radio Open Shortest Path First protocol.

8. The unit of claim 6 wherein:

said unit message is associated with said intranet protocol and said broadcast module periodically transmits said unit message in accordance with said intranet protocol; and

said broadcast message is associated with said internetworking protocol and said message module inserts said internetworking protocol broadcast message into said intranet protocol unit message to facilitate transmission of said broadcast message in conjunction with said transmission of said intranet protocol unit message.

9. The unit of claim 6 wherein:

said communications network includes a plurality of clusters each having a plurality of said communication units, wherein one of said communication units of each said cluster is designated as a head unit with remaining communication units of that cluster being designated as member units;

head units of said clusters communicate with each other and with corresponding member units of that cluster to facilitate communications between and within said clusters;

said processor further includes a database to store information indicating particular network communication units in communication with said communication unit, wherein a database update message including information relating to a current status of network connections is distributed throughout said network in accordance with said internetworking protocol to synchronize said database of each said communication unit.

10. The unit of claim 9 wherein said processor further includes a transmission control module to facilitate transmission of said outgoing messages, wherein said transmission control module includes:

a head unit transmission module to facilitate transmission of said database update message as said broadcast message inserted within said unit message in response to said communication unit being designated as a head unit; and

a member transmission module to facilitate transmission of said database update message from said communication unit directly to a corresponding head unit in response to said communication unit being designated as a member unit.

11. The unit of claim 10 wherein said transmission control module further includes:

a head unit timer module to set head unit timers subsequent transmission of said database update message by said head unit transmission module and in response to said communication unit being designated as a head unit, wherein said head unit timers indicate a time for re-transmission of said database update message to corresponding member units and other head units;

a member timer module to set a member unit timer subsequent transmission of said database update message by said member transmission module and in response to said communication unit being designated as a member unit, wherein said member unit timer indicates a time for re-transmission of said database update message to a corresponding head unit; and

a re-transmission module to facilitate re-transmission of said database update message in response to expiration of a member or head unit timer, wherein said database update message is re-transmitted directly to communication units associated with said expired timer and that have not acknowledged receipt of said database update message.

12. The unit of claim 11 wherein said head unit transmission module facilitates transmission of said database update message at least two times and said head unit timer module sets said head unit timers subsequent transmission of said database update packet said at least two times.

13. The unit of claim 10 wherein said processor further includes:

a reception module to facilitate reception and processing of messages including said unit and database update messages, wherein said reception module includes;

an implied acknowledgment module for processing said received message as an acknowledgment message in response to said received message being an initial transmission of a database update packet previously received by said communication unit.

14. The unit of claim 13 wherein said reception module further includes:

a message discard module to discard a received message in response to determining that said received message is not received from a neighboring communication unit as indicated by said communication unit database; and

a message processing module to process a received database update message in response to determining that said received database update message has not been previously received by said communication unit, wherein said processing module includes;

a database update module to update said database with information contained within said received database update message;

a member acknowledgment module to facilitate transmission of an acknowledgment message as said broadcast message inserted within said unit message in response to receiving said database update message and said communication unit being designated as a member unit;

a head unit forwarding module to facilitate transmission of said processed database update message by said head unit transmission module in response to said communication unit being designated as a head unit; and

a member unit forwarding module to facilitate transmission of said processed database update message by said member transmission module in response to said communication unit being designated as a member unit.

15. The unit of claim 13 wherein said reception module further includes:

a re-transmission acknowledgment module to facilitate transmission of an acknowledgment message directly to a communication unit transmitting said received database update message in response to said received database update message being a re-transmission of a database update packet previously received by said communication unit.

16. In a communications network, a method of transmitting and receiving messages between communication units within said network comprising the steps of:

(a) periodically transmitting a unit message within said network from each communication unit, wherein said unit message includes information relating to a status of a corresponding communication unit transmitting that unit message; and

(b) inserting a broadcast message within a corresponding unit message of said each communication unit to transmit said broadcast message in conjunction with transmission of said corresponding unit message.

17. The method of claim 16 wherein step (a) further includes:

(a.1) transmitting said unit message from said each communication unit in the form of radio signals.

18. The method of claim 16 wherein step (b) further includes:

(b.1) storing said broadcast message in a storage device within said each communication unit until a succeeding transmission time for said corresponding unit message.

19. The method of claim 18 wherein step (b.1) further includes:

(b.1.1) storing a plurality of broadcast messages within said storage unit of said each communication unit and inserting at least one of said stored messages within said corresponding unit message.

20. The method of claim 16 wherein step (a) further includes:

(a.1) facilitating communications within said network in accordance with an intranet protocol; and

(a.2) facilitating communications between said network and an external network in accordance with an internetworking protocol.

21. The method of claim 20 wherein step (a.2) further includes:

(a.2.1) facilitating communications between said network and an external network in accordance with a Radio Open Shortest Path First protocol.

22. The method of claim 20 wherein said unit message is associated with said intranet protocol and said broadcast message is associated with said intemetworking protocol, and step (a.1) further includes:

(a.1.1) periodically transmitting said unit message from said each communication unit in accordance with said intranet protocol; and

step (b) further includes;

(b.1) inserting said intemetworking protocol broadcast message into said corresponding intranet protocol unit message to facilitate transmission of said broadcast message in conjunction with said transmission of said corresponding intranet protocol unit message.

23. The method of claim 20 wherein said communications network includes a plurality of clusters each having a plurality of said communication units, wherein one of said communication units of each said cluster is designated as a head unit with remaining communication units of that cluster being designated as member units, wherein head units of said clusters communicate with each other and with corresponding member units of that cluster to facilitate communications between and within said clusters, and wherein step (a.2) further includes:

(a.2.1) storing information within a database of said each communication unit indicating particular network communication units in communication with that communication unit; and

(a.2.2) distributing a database update message including information relating to a current status of network connections throughout said network in accordance with said intemetworking protocol to synchronize said database of said each communication unit.

24. The method of claim 23 wherein step (a.2.2) further includes:

(a.2.2.1) transmitting said database update message from each member unit receiving said database update message directly to a corresponding head unit; and

step (b) further includes;

(b.1) transmitting said database update message from each head unit receiving said database update message as said broadcast message inserted within said corresponding unit message.

25. The method of claim 24 wherein step (a.2.2) further includes:

(a.2.2.2) setting a member unit timer within each said member unit transmitting a corresponding database update message subsequent said transmission in step (a.2.2.1), wherein said member unit timer indicates a time for re-transmission of said corresponding database update message to a corresponding head unit; and

step (b) further includes;

(b.2) setting head unit timers within each said head unit transmitting a corresponding database update message subsequent said transmission in step (b.1), wherein said head unit timers indicate a time for re-transmission of said corresponding database update message to corresponding member units and other head units;

(b.3) re-transmitting said database update message from each said head unit having an expired head unit timer, wherein said database update message is re-transmitted from those head units directly to communication units associated with a corresponding expired timer that have not acknowledged receipt of said database update message; and

(b.4) re-transmitting said database update message from each said member unit having an expired member unit timer, wherein said database update message is re-transmitted from those member units directly to a corresponding head unit that has not acknowledged receipt of said database update message.

26. The method of claim 25 wherein step (b.1) further includes:

(b.1.1) transmitting said database update message at least two times from said each head unit receiving said database update message; and

step (b.2) further includes;

(b.2.1) setting said head unit timers within said each head unit transmitting said database update message subsequent transmission of said corresponding database update message said at least two times.

27. The method of claim 24 further including the step of:

(c) receiving and processing messages including said unit and database update messages within said each communication unit, wherein step (c) further includes;

(c.1) processing a received message as an acknowledgment message within each said communication unit in response to said received message being an initial transmission of a database update message previously received by that communication unit.

28. The method of claim 27 wherein step (c) further includes:

(c.2) discarding a received message within said each communication unit in response to determining that said received message is not received from a neighboring communication unit as indicated by said database of that communication unit; and

(c.3) processing a received database update message within said each communication unit in response to determining that said received database update message has not been previously received by that communication unit, wherein step (c.3) further includes;

(c.3.1) updating said database of said each communication unit with information contained within a corresponding received database update message;

(c.3.2) transmitting an acknowledgment message from each member unit as said broadcast message inserted within said unit message in response to that member unit receiving said database update message;

(c.3.3) facilitating transmission of said processed database update message from said each head unit as said broadcast message inserted within said unit message in response to that head unit receiving said database update message; and

(c.3.4) facilitating transmission of said processed database update message from said each member unit directly to a corresponding head unit in response to that member unit receiving said database update message.

29. The method of claim 27 wherein step (c) further includes:

(c.2) transmitting an acknowledgment message from said each communication unit directly to a communication unit transmitting said received database update message in response to that communication unit receiving said database update message as a re-transmission of a database update message previously received by that communication unit.

30. A communication network comprising:

a plurality of clusters each having a plurality of communication units, wherein one of said communication units of each said cluster is designated as a head unit with remaining communication units of that cluster being designated as member units, wherein head units of said clusters communicate with each other and with corresponding member units of that cluster to facilitate communications between and within said clusters;

wherein each said head unit includes;

a head unit transmission module to periodically transmit a unit message within said network, wherein said unit message includes information relating to a status of that head unit; and

a message broadcast module to insert a broadcast message within said unit message to facilitate transmission of said broadcast message within said network in conjunction with transmission of said unit message;

wherein each said member unit includes;

a member unit transmission module to transmit said broadcast message directly to a corresponding head unit to facilitate transmission of said broadcast message throughout said network via said corresponding head unit.

31. The network of claim 30 wherein said each head unit and member unit transmits messages in the form of radio signals.

32. The network of claim 30 wherein said each head unit and member unit further includes a database to store information indicating particular communication units in communication with that unit, wherein said head and member units transmit a database update message including information relating to a current status of network connections as said broadcast message to synchronize each said database.

33. The network of claim 32 wherein said each head unit and member unit further includes:

a reception module to facilitate reception and processing of messages including said unit and database update messages, wherein said reception module includes;

an implied acknowledgment module for processing a received database update message as an acknowledgment message in response to said received database update message being an initial transmission of a database update message previously received by that unit.

34. In a communication network including a plurality of clusters each having a plurality of communication units, wherein one of said communication units of each said cluster is designated as a head unit with remaining communication units of that cluster being designated as member units, wherein head units of said clusters communicate with each other and with corresponding member units of that cluster to facilitate communications between and within said clusters, a method of transmitting messages within said network comprising the steps of:

(a) periodically transmitting a unit message within said network from each said head unit, wherein said unit message includes information relating to a status of that head unit;

(b) inserting a broadcast message within said unit message by said each head unit receiving said broadcast message to facilitate transmission of said broadcast message within said network in conjunction with transmission of said unit message; and

(c) transmitting said broadcast message from each said member unit receiving that message directly to a corresponding head unit to facilitate transmission of said broadcast message throughout said network via said corresponding head unit.

35. The method of claim 34 wherein said each head unit and member unit transmits messages in the form of radio signals.

36. The method of claim 34 wherein said each head unit and member unit includes a database to store information indicating particular communication units in communication with that unit, wherein step (b) further includes:

(b.1) inserting a database update message including information relating to a current status of network connections within said unit message by said each head unit receiving said database update message to facilitate transmission of said database update message within said network to synchronize said each database; and

step (c) further includes;

(c.1) transmitting said database update message from each said member unit receiving that message directly to a corresponding head unit to facilitate transmission of said database update message throughout said network via said corresponding head unit.

37. The method of claim 36 further including the step of:

(d) receiving and processing messages including said unit and database update messages by said each head unit and member unit, wherein step (d) further includes;

(d.1) processing a received database update message as an acknowledgment message by each said head unit and member unit receiving said database update message in response to said received database update message being an initial transmission of a database update message previously received by that unit.