Topology and quality of service management apparatus and methods for communication networks

• US 7,995,489 B2
• Filed: 06/14/2004
• Issued: 08/09/2011
• Est. Priority Date: 06/14/2004
• Status: Expired due to Fees

• Current Assignee: The Boeing Co.
• Original Assignee: The Boeing Co.
• Inventors: Ayyagari, Arun
• Primary Examiner(s): Kumar; Pankaj
• Assistant Examiner(s): SMITH, MARCUS
• Application Number:
  US10/868,565
• Publication Number:
  US 20050276231A1
• Time in Patent Office: 2,612 Days
• Field of Search: None
• US Class Current: 370/252
• CPC Class Codes: H04W 40/24 Connectivity information management, e.g. connectivity discovery or connectivity update
• CPC Class Codes: H04W 72/12 Wireless traffic scheduling
• CPC Class Codes: H04W 8/005 Discovery of network devices, e.g. terminals
• CPC Class Codes: H04W 8/24 Transfer of terminal data
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks

Abstract

A method of structuring an ad hoc network is described. A node discovers and pairs with another node to form a network link. Each node maintains a network topology based on node/link states received from other nodes. One node communicates an outbound link state to other nodes which schedule transmission based on the communicated state. A node includes a network control module that controls network routing, a node control module that controls packet routing within the node, and a switching platform control module that provides an outbound link state to the other control modules of the node.

Claims

1. A method of managing a plurality of nodes, the method comprising:

each node maintaining a pairing list of discovered nodes, if any, discovered by the maintaining node and with which the maintaining node may potentially pair, the pairing list maintained based on pairing criteria applicable by the maintaining node to nodes not paired with the maintaining node;

at least a first of the nodes announcing its presence to discover nodes with which to potentially pair;

at least a second of the nodes, in response to the announcing, sending its node/link state to at least the first node;

based on whether the node/link state sent by the second node is in accordance with the pairing criteria of the first node, the first node selectively listing the second node in the pairing list of the first node;

based on whether the second node is listed in the pairing list of the first node, the first node selectively pairing with the second node and establishing connectivity with the second node via one or more links between the first and second nodes;

at least the maintaining and selectively pairing performed reiteratively, during operation of a network that includes at least one of the first and second nodes, as part of a background process in which each of the nodes of the network (a) receives current node/link states of all other nodes in the network and (b) manages a link topology relative to the network based on the pairing list of the node and on the current node/link states;

the first node capable of communicating with the second node over a link outbound from the first node to the second node via a first transport medium and inbound to the first node from the second node via a transport medium different from the first transport medium.

2. The method of claim 1, wherein the first and second transport media include free-space optical (FSO) and radiofrequency (RF).

3. The method of claim 1, wherein a third node of the network updates a routing table in accordance with the link topology maintained by the third node.

4. The method of claim 1, further comprising a node of the network using an order wire channel to communicate with a node not linked into the network.

5. The method of claim 1, further comprising the first and second nodes pairing and linking based on at least one node/link state criterion of the first node not met by a node from which an outbound link is outbound to the first node.

6. The method of claim 1, further comprising a node control module of the first node controlling hybrid routing within the first node based on a node/link state communicated from a third node.

7. A method of structuring an ad hoc network, the method comprising:

each of a plurality of nodes maintaining a pairing list of potential nodes, if any, with which to pair, the pairing list based on pairing criteria of the node maintaining the pairing list, the pairing criteria including a node/link state of a potential node with which to pair, the node/link state including a location and trajectory of the potential node;

a first of the nodes announcing its presence to discover nodes with which to potentially pair;

a second of the nodes, in response to the announcing, sending its node/link state to at least the first node;

based on whether the node/link state sent by the second node meets the pairing criteria of the first node, the first node selectively listing the second node in the pairing list of the first node;

based on whether the second node is listed in the pairing list of the first node, the first node pairing with the second node and the first and second nodes establishing one or more links between the first and second nodes such that the first node is capable of communicating with the second node over a link outbound from the first node to the second node via a first transport medium and inbound to the first node from the second node via a transport medium different from the first transport medium;

at least the maintaining and pairing performed reiteratively as part of a background process during operation of the ad hoc network;

the background process comprising;

each node of the network receiving updates of node/link states of each of the other nodes of the network and each node of the network using the updates to maintain a link topology that includes all nodes of the network; and

based on one of the updates, a third node selectively pairing with a fourth node listed in the pairing list of the third node to establish connectivity with the fourth node.

8. The method of claim 7 wherein the third node pairs with the fourth node based on a changed node/link state of a fifth node.

9. The method of claim 7, wherein the pairing is performed via an order wire channel outside the network.

10. The method of claim 7, wherein a node/link state comprises a number of links, a current pairing state, a link bandwidth, and a link utilization.

11. The method of claim 7, wherein the different transport media include radiofrequency (RF) and free-space optical (FSO).

12. A network comprising:

a plurality of nodes, each node configured to control routing of packets through the node based on a network link topology including each of the nodes, the link topology maintained on each node using node/link state information received by the node reiteratively in a background process (a) from one or more nodes outside the network sending their node/link states in response to announcing nodes for possible selection by one of the announcing nodes for inclusion, based on pairing criteria of the one of the announcing nodes, in a pairing list maintained by the one of the announcing nodes for possible establishment of links that add one or more nodes to the network, and (b) from nodes of the network multicasting updates of their node/link states to the other nodes of the network;

each node including;

a network control module configured to use the network link topology maintained by the node to determine one or more route tables for network-level routing;

a node control module that receives the one or more route tables from the network control module and uses the one or more route tables to control packet routing within the node between terminals of the node; and

a switching platform control module that, based on the one or more route tables, controls switching of packets to and from the node and provides the node/link state information pertaining to the node to each of the other nodes via the node control module and network control module;

a first of the nodes capable of communicating with a second node over a link outbound from the first node to the second node via a first transport medium and inbound to the first node from the second node via a transport medium different from the first transport medium.

13. The network of claim 12 wherein a network control module of one of the nodes determines packet routing based on state information pertaining to an outbound link of another node.

14. The network of claim 12 wherein a network control module of one of the nodes determines packet routing over a link topology changed based on at least one of a change in a node/link state, a node location, a node trajectory, and an atmospheric condition.

15. The network of claim 12 wherein the terminals of one of the nodes include hybrid terminals for different transport media, and the node control module of the one of the nodes controls packet routing between the hybrid terminals.

16. The network of claim 15 wherein the node control module of the one of the nodes controls the packet routing between the hybrid terminals based on at least one of a link state, a packet destination and a quality of service (QoS) requirement.

17. The network of claim 12 wherein a network control module of one of the nodes passes a route table, via the node control module of the node, to the switching platform control module of the node.

18. The network of claim 12 wherein one of the nodes comprises QoS module for specifying quality of service (QoS), and wherein the network control module of the one of the nodes updates the QoS module when a node/link state of another node changes.

19. The network of claim 12 wherein the network control module updates interconnectivity of the nodes and updates a network route table.

20. The network of claim 19 wherein the network control module performs the updating based on a history of outbound link bandwidth.

21. The network of claim 12 wherein the switching platform control module switches a link transmission rate based on at least one of a signal-to-noise ratio (SNR) characteristic and a bit error rate (BER) of the link.

22. A non-transitory machine-readable medium for use with a processor having a memory, the machine-readable medium comprising:

instructions executable by a processor to configure a first node to maintain, in accordance with pairing criteria of the first node, a pairing list of potential pairing nodes;

instructions executable by a processor to configure the first node to (a) announce, reiteratively in a background process, the presence of the first node, (b) to evaluate, relative to the pairing criteria of the first node, node/link state information received from other nodes in response to the announcing by the first node, and (c) to selectively list one or more of the other nodes on the pairing list of the first node;

instructions executable by a processor to configure the first node to select one or more nodes in the pairing list for pairing with the first node to form links in a network;

instructions executable by a processor to configure a network control module of the first node to determine one or more route tables for packet routing across the network based on a link topology of the network maintained on and including each node of the network, the link topology maintained using node/link state information received by the nodes reiteratively in the background process from (a) one or more nodes outside the network sending their node/link states in response to announcing nodes for potential pairing with the announcing nodes and/or (b) paired nodes sending multicast updates of their node/link states;

instructions executable by a processor to configure a node control module of the first node to receive and use the one or more route tables from the network control module to control packet routing within the first node between terminals of the first node; and

instructions executable by a processor to configure a switching platform control module of the first node to;

control switching of packets to and from the first node; and

provide node/link state information pertaining to an outbound link of the first node via the node control module and the network control module to another node of the network;

where to form a link includes to form a link outbound from the first node to a second node via a first transport medium and inbound to the first node from the second node via a transport medium different from the first transport medium.

23. A node-performed method of controlling communication among nodes, the method comprising:

at least some nodes announcing their presence to discover nodes with which they might potentially pair;

at least some nodes, in response to the announcing, sending their node/link states to one or more of the announcing nodes;

based on the sent node/link states, at least one of the announcing nodes selectively listing one or more of the sending nodes on a pairing list of potential nodes with which to pair;

at least one node pairing with one or more nodes on the pairing list of the pairing node to establish connectivity between paired nodes;

the announcing, sending, and pairing performed reiteratively as part of a background process during operation of the network wherein each paired node is provided with background updates of node/link states of each of the other paired nodes; and

a first node communicating with a second node paired with the first node, the communicating performed over a link outbound from the first node to the second node via a first transport medium and inbound to the first node from the second node via a second transport medium different from the first transport medium.

24. The method of claim 23, further comprising the second node, in response to an altered transmission rate of the first link, pairing with a fourth node on the pairing list of the second node.

25. The method of claim 23, wherein the first and second transport media include free-space optical (FSO) and radiofrequency (RF).

26. The method of claim 23, further comprising the first node transmitting via the link at a bit error rate based on a signal-to-noise characteristic of an outbound link from a third node.

27. The method of claim 24, wherein altering a transmission rate comprises stopping transmission.