Method and apparatus for controlling communication links between network nodes to reduce communication protocol overhead traffic

• US 6,349,091 B1
• Filed: 11/07/2000
• Issued: 02/19/2002
• Est. Priority Date: 11/12/1999
• Status: Expired due to Term

• 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): NGO, RICKY QUOC
• Application Number:
  US09/706,845
• Time in Patent Office: 469 Days
• Field of Search: 370/230, 370/231, 370/232, 370/235, 370/236, 370/237, 370/238, 370/352, 370/389, 370/395, 370/400, 370/252, 370/351, 370/328, 370/340, 370/338, 370/410
• US Class Current: 370/238
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/122 by minimising distances, e.g. by selecting a route with minimum of number of hops
• CPC Class Codes: H04L 45/20 Hop count for routing purposes, e.g. TTL
• 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

Abstract

Link-State Advertisement (LSA) and other routing control packets are transmitted within a wireless communication system or network via selective enablement of control links for transference of the packets between network nodes. Specifically, an exemplary 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. A database within each network head node contains link information for that node. The LSA packets contain information to update the head node databases, while other routing control packets generally contain various routing information for network nodes to facilitate message transmissions. The routing control packets are transmitted to each head node to control routing functions and enable each database to maintain current information. In order to reduce overhead traffic due to transmission of numerous LSA and other routing control packets, the present invention selectively controls enablement of control links (e.g., links that transport routing control information) to transmit the LSA and other routing control packets to head nodes within the network. In other words, the present invention selectively reduces the quantity of control links between head nodes to transmit the LSA and other routing control packets with reduced protocol overhead traffic, thereby permitting the network to utilize link-state based protocols effectively (e.g., with minimal impact on network throughput) while expanding to larger scales.

Claims

1. In a communications network, a communication unit including a communication link with each neighboring communication unit within said network to facilitate network communications, wherein each said communication link facilitates transfer of data and is selectively controllable to further facilitate transfer of control messages, said communication unit comprising:

a transmitter to transmit an outgoing message to each said neighboring unit via a corresponding communication link;

a receiver to receive an incoming message from each said neighboring unit via a corresponding communication link; and

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

a communications module to examine network connectivity and determine particular communication links associated with said communication unit sufficient to enable transmission of a control message over said network to each said neighboring unit within a predetermined quantity of hops;

a link control module to control said communication links associated with said communication unit in accordance with said determination, wherein each communication link is controlled to facilitate transmission of data and said particular communication links are controlled to further facilitate transmission of said control message to corresponding neighboring units; and

a transmission module to facilitate transmission of said control message throughout said network by transmitting said control message via said particular communication links to corresponding neighboring units.

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 further including a storage unit to store information indicating said network connectivity, and said communications module includes:

an evaluation module to analyze said network connectivity information to determine said particular communication links.

5. The unit of claim 1 wherein said control message includes routing control information.

6. The unit of claim 4 wherein said control message includes information relating to changes in network connectivity to synchronize storage units of said network communication units.

18. The unit of claim 1 wherein said communications network includes a plurality of clusters each having said communication unit as a head unit and a plurality of communication units being designated as member units, wherein head units of said clusters communicate with each other via said communication links to facilitate communications throughout said network.

7. In a communications network, a communication unit including a communication link with each neighboring communication unit within said network to facilitate network communications, wherein each said communication link includes a data link for transferring data and a control link for transferring control messages, said communication unit comprising:

a transmitter to transmit an outgoing message to each said neighboring unit via a corresponding communication link;

a receiver to receive an incoming message from each said neighboring unit via a corresponding communication link; and

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

a communications module to examine network connectivity and determine particular communication links associated with said communication unit sufficient to establish communications via said network with each said neighboring unit within a predetermined quantity of hops;

a link control module to control said communication links in accordance with said determination, wherein said particular communication links are controlled to transmit a control message to corresponding neighboring units, and wherein said link control module includes;

a data link module to enable said data link of each said communication link associated with said communication unit; and

a control link module to control said control links of said communication links to facilitate transmission of said control message over said particular communication links to corresponding neighboring units and throughout said network; and

a transmission module to facilitate transmission of said control message throughout said network by transmitting said control message via said particular communication links to corresponding neighboring units.

8. The unit of claim 7 wherein said link control module further includes:

a neighbor determination module to determine the presence of a new neighboring unit; and

a link initiation module to provide a communication link between said communication unit and said new neighboring unit and to enable said data and control links of said provided communication link in response to determining the presence of said new neighboring unit.

9. The unit of claim 7 wherein said link control module further includes:

a control link enablement module to enable a disabled control link in response to said communication unit receiving said control message via that disabled control link.

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

a control link status module to determine, prior to transmission of said control message, viability of said communication links for establishing communications with each said neighboring unit via said network within said predetermined quantity of hops in response to expiration of a predetermined time interval.

11. The unit of claim 10 wherein said control link status module includes:

a control link selection module to select successive disabled control links and enable a selected disabled control link in response to determining that said communication links are not viable and communications between said communication unit and each neighboring unit can be established within said predetermined quantity of hops with said selected link enabled; and

a control link enablement module to enable successive disabled control links until communications between said communication unit and each neighboring unit are established within said predetermined quantity of hops in response to no disabled control link being enabled by said control link selection module.

12. The unit of claim 7 wherein said processor further includes:

a control link status module to examine said communication links and determine said particular communication links in response to enablement of a control link or receipt of a message indicating changes in network connectivity.

13. The unit of claim 12 wherein said control link status module includes:

a control link disablement module to select each enabled control link successively and disable that enabled control link in response to determining that communications between said communication unit and each neighboring unit can be established within said predetermined quantity of hops with that selected control link disabled.

14. The unit of claim 13 wherein said control link disablement module includes:

a control link selection module to successively select each enabled control link;

a link evaluation module to determine viability of establishing communications between said communication unit and each neighboring unit within said predetermined quantity of hops with a selected control link disabled;

a request module to facilitate transmission of a request message to a neighboring unit associated with said selected control link to request disablement of said selected control link; and

a disablement module to disable said selected control link in response to receiving a reply message from said associated neighboring unit permitting disablement of said selected link.

15. The unit of claim 14 wherein said control link disablement module further includes:

a record module to record a disablement attempt in response to expiration of a reply timer prior to receiving said reply message from said associated neighboring unit.

16. The unit of claim 14 wherein said processor further includes:

a reception module to facilitate reception and processing of messages including said request message, wherein said reception module includes;

a disablement request module to receive said request message from a neighboring unit and disable a control link indicated in said request message in response to determining that communications between said communication unit and each neighboring unit can be established within said predetermined quantity of hops with said indicated control link disabled.

17. The unit of claim 16 wherein said disablement request module includes:

a request reception module to receive said request message from said neighboring unit;

a disabled link evaluation module to determine viability of establishing communications between said communication unit and each neighboring unit within said predetermined quantity of hops with said indicated control link disabled; and

a link disablement module to facilitate transmission of said reply message to said neighboring unit indicating that said indicated control link may be disabled and to disable said indicated control link in response to said determination of viable communications with each neighboring unit.

19. In a communications network employing a communication link between each neighboring communication unit within said network, wherein each said communication link facilitates transfer of data and is selectively controllable to further facilitate transfer of control messages, a method of transmitting and receiving messages by a communication unit within said network comprising the steps of:

(a) examining network connectivity and determining particular communication links associated with said communication unit sufficient to enable transmission of a control message over said network to each corresponding neighboring unit within a predetermined quantity of hops;

(b) controlling said communication links associated with said communication unit in accordance with said determination, wherein each associated communication link is controlled to facilitate transmission of data and said particular communication links are controlled to further facilitate transmission of said control message to corresponding neighboring units; and

(c) facilitating transmission of said control message throughout said network by transmitting said control message via said particular communication links to corresponding neighboring units.

20. The method of claim 19 wherein step (c) further includes:

(c.1) transmitting said control message in the form of radio signals.

21. The method of claim 19 wherein said communication unit includes a storage unit to store information indicating said network connectivity, and step (a) further includes:

(a.1) analyzing said network connectivity information to determine said particular communication links.

22. The method of claim 19 wherein said control message includes routing control information.

23. The method of claim 21 wherein said control message includes information relating to changes in network connectivity, and step (c) further includes:

(c.1) transmitting said control message throughout said network to synchronize storage units of said network communication units.

36. The method of claim 19 wherein said communications network includes a plurality of clusters each having said communication unit as a head unit and a plurality of communication units being designated as member units, wherein head units of said clusters communicate with each other via said communication links to facilitate communications throughout said network.

24. In a communications network employing a communication link between each neighboring communication unit within said network, wherein each said communication link includes a data link for transferring data and a control link for transferring control messages, a method of transmitting and receiving messages by a communication unit within said network comprising the steps of:

(a) examining network connectivity and determining particular communication links associated with said communication unit sufficient to establish communications via said network with each corresponding neighboring unit within a predetermined quantity of hops;

(b) controlling said communication links associated with said communication unit in accordance with said determination, wherein said particular communication links are controlled to transmit a control message to corresponding neighboring units, and wherein step (b) further includes;

(b.1) enabling said data link of each said communication link associated with said communication unit; and

(b.2) controlling said control links of said associated communication links to facilitate transmission of said control message over said particular communication links to corresponding neighboring units and throughout said network; and

(c) facilitating transmission of said control message throughout said network by transmitting said control message via said particular communication links to corresponding neighboring units.

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

(b.3) determining the presence of a new neighboring unit; and

(b.4) providing a communication link between said communication unit and said new neighboring unit and enabling said data and control links of said provided communication link in response to determining the presence of said new neighboring unit.

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

(b.3) enabling a disabled control link in response to said communication unit receiving said control message via that disabled control link.

27. The method of claim 24 wherein step (b) further includes:

(b.3) determining, prior to transmission of said control message, viability of said communication links for establishing communications with each said neighboring unit via said network within said predetermined quantity of hops in response to expiration of a predetermined time interval.

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

(b.3.1) selecting successive disabled control links and enabling a selected disabled control link in response to determining that said communication links are not viable and communications between said communication unit and each neighboring unit can be established within said predetermined quantity of hops with said selected link enabled; and

(b.3.2) enabling successive disabled control links until communications between said communication unit and each neighboring unit are established within said predetermined quantity of hops in response to no disabled control link being enabled in step (b.3.1).

29. The method of claim 24 wherein step (b) further includes:

(b.3) examining said communication links and determining said particular communication links in response to enablement of a control link or receipt of a message indicating changes in network connectivity.

30. The method of claim 29 wherein step (b.3) further includes:

(b.3.1) selecting each enabled control link successively and disabling that enabled control link in response to determining that communications between said communication unit and each neighboring unit can be established within said predetermined quantity of hops with that selected control link disabled.

31. The method of claim 30 wherein step (b.3.1) further includes:

(b.3.1.1) successively selecting each enabled control link;

(b.3.1.2) determining viability of establishing communications between said communication unit and each neighboring unit within said predetermined quantity of hops with a selected control link disabled;

(b.3.1.3) facilitating transmission of a request message to a neighboring unit associated with said selected control link to request disablement of said selected control link; and

(b.3.1.4) disabling said selected control link in response to receiving a reply message from said associated neighboring unit permitting disablement of said selected link.

32. The method of claim 31 wherein step (b.3.1) further includes:

(b.3.1.5) recording a disablement attempt in response to expiration of a reply timer prior to receiving said reply message from said associated neighboring unit.

33. The method of claim 31 further including:

(d) processing messages received from said neighboring units.

34. The method of claim 33 wherein said received messages include said request message, and step (d) further includes:

(d.1) receiving said request message from a neighboring unit and disabling a control link indicated in said request message in response to determining that communications between said communication unit and each neighboring unit can be established within said predetermined quantity of hops with said indicated control link disabled.

35. The method of claim 34 wherein step (d.1) further includes:

(d.1.1) receiving said request message from said neighboring unit;

(d.1.2) determining viability of establishing communications between said communication unit and each neighboring unit within said predetermined quantity of hops with said indicated control link disabled; and

(d.1.3) transmitting said reply message to said neighboring unit indicating that said indicated control link may be disabled and to disable said indicated control link in response to viable communications with each neighboring unit.

37. A communications network comprising:

a plurality of nodes each having a communication link between that node and each of its neighboring nodes to facilitate network communications, wherein each said communication link facilitates transfer of data and is selectively controllable to further facilitate transfer of control messages;

wherein each said node includes;

an evaluation module to determine particular communication links associated with that node and sufficient to enable transmission of a control message over said network to corresponding neighboring nodes within a predetermined hop limit based on network connectivity; and

a link control module to selectively control said associated communication links in accordance with said determination to enable said particular communication links to facilitate transmission of a control message from that node to each of its neighboring nodes to propagate said control message through said network by succeeding nodes receiving that message, wherein each associated communication link is controlled to facilitate transfer of data and said particular communication links are controlled to further facilitate transmission of said control message.

38. The network of claim 37 wherein each said node transmits said control message in the form of radio signals.

39. The network of claim 37 wherein each said node includes a storage unit to store information relating to network connectivity and said control message includes information relating to changes in network connectivity to synchronize storage units of said network nodes.

41. The network of claim 37 further including a plurality of clusters each having said node as a head unit and a plurality of communication units being designated as member units, wherein head units of said clusters communicate with each other via said communication links to facilitate communications throughout said network.

40. A communications network comprising:

a plurality of nodes each including a communication link between that node and each of its neighboring nodes to facilitate network communications, wherein each said communication link includes a data link for transferring data and a control link for transferring control messages;

wherein each said node includes;

an evaluation module to determine particular communication links associated with that node and sufficient to establish communications via said network to corresponding neighboring nodes within a predetermined hop limit based on network connectivity; and

a link control module to selectively control said associated communication links in accordance with said determination to enable said particular communication links to facilitate transmission of said control message from that node to each of its neighboring nodes to propagate said control message through said network by succeeding nodes receiving that message, wherein said link control module includes;

a data link module to enable said data link of each said associated communication link; and

a control link module to control said control links of said associated communication links to facilitate transmission of said control message over said particular communication links to corresponding neighboring nodes and throughout said network.

42. In a communications network including a plurality of nodes each having a communication link between that node and each of its neighboring nodes, wherein each said communication link facilitates transfer of data and is selectively controllable to further facilitate transfer of control messages, a method of transmitting messages within said network comprising the steps of:

(a) determining particular communication links for each node sufficient to transmit a control message from that node over said network to corresponding neighboring nodes within a predetermined hop limit based on network connectivity; and

(b) selectively controlling said communication links of each node in accordance with said determination to enable said particular communication links to facilitate transmission of said control message from that node to each of its neighboring nodes to propagate said control message through said network by succeeding nodes receiving that message, wherein each communication link is controlled to facilitate transfer of data and said particular communication links are controlled to further facilitate transmission of said control message.

43. The method of claim 42 wherein each said node transmits said control message in the form of radio signals.

44. The method of claim 42 wherein each said node includes a storage unit to store information relating to network connectivity and said control message includes information relating to changes in network connectivity to synchronize storage units of said network nodes.

46. The method of claim 42 wherein said network further includes a plurality of clusters each having said node as a head unit and a plurality of communication units being designated as member units, wherein head units of said clusters communicate with each other via said communication links to facilitate communications throughout said network.

45. In a communications network including a plurality of nodes each having a communication link between that node and each fits neighboring nodes, wherein each said communication link includes a data link for transferring data and a control link for transferring control messages, a method of transmitting messages within said network comprising the steps of:

(a) determining particular communication links for each node sufficient to establish communications via said network from that node to corresponding neighboring nodes within a predetermined hop limit based on network connectivity; and

(b) selectively controlling said communication links of each node in accordance with said determination to enable said particular communication links to facilitate transmission of a control message from that node to each of its neighboring nodes to propagate said control message through said network by succeeding nodes receiving that message, wherein step (b) further includes;

(b.1) enabling said data link of each said communication link; and

(b.2) controlling said control links of said communication links of each node to facilitate transmission of said control message over said particular communication links of that node to corresponding neighboring nodes and throughout said network.