Method for providing an efficient and adaptive management of message routing in a multi-platform and apparatus communication system

• US 5,117,422 A
• Filed: 07/09/1990
• Issued: 05/26/1992
• Est. Priority Date: 07/09/1990
• Status: Expired due to Term

• Current Assignee: ITT Corporation (ITT, Inc.)
• Original Assignee: ITT Corporation (ITT, Inc.)
• Inventors: Doskow, Arthur, Hauptschein, Arthur, Kennedy, John B.
• Primary Examiner(s): Olms, Douglas W.
• Assistant Examiner(s): SAMUEL, TEMESGHEN
• Application Number:
  US07/551,177
• Time in Patent Office: 687 Days
• Field of Search: 370/94.1, 370/60, 370/62, 370/95.3, 370/93, 370/77, 370/95.1, 340/825
• US Class Current: 370/255
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/16 Multipoint routing
• CPC Class Codes: H04L 45/44 Distributed routing

Abstract

The method for providing an efficient and adaptive management of message routing in a multi-platform, communication system having dynamically changing platform populations and dynamically changing connectivities between platforms where each of the platforms are capable of performing the steps of recognizing at least certain ones of the platforms in the system, deriving from at least one of the recognized platforms the quality of interconnectivities of the recognized platforms and certain others of the platforms in the system; and employing the derived quality of interconnectivities to make connectivity-based routing decisions using a selective one of a point-to-point routing algorithm, a point-to-multipoint routing algorithm and a broadcast routing algorithm.

Claims

1. A method for providing an efficient and adaptive management of message routing in a multi-platform, multi-network communications system having dynamically changing platform populations and dynamically changing connectivities between platforms where each of said platforms are capable of performing the steps of:

recognizing at least certain ones of said platforms in said system;

deriving from at least one of said recognized platforms the quality of interconnectivities of said recognized platforms and certain others of said platforms in said system, said quality of interconnectivities transmission media disruptions, recognized transmit and receive power and antenna gain whereby said quality can be determined only after recognition of said platforms; and

employing said derived quality of interconnectivities to make connectivity-based routing decisions using either a point-to-point routing algorithm, a point-to-multipoint routing algorithm, or a broadcast routing algorithm as appropriate.

2. A method according to claim 1, wherein said step of recognizing includes

the step of providing a plurality of different accesses to remote recognized platforms from said platform performing the step of recognizing during which said platforms can initiate transmissions, each of said plurality of different accesses being capable of being used by many of said platforms in said system so long as said platforms are not direct neighbors and said platforms do not share a common intermediary platform.

3. A method according to claim 1, wherein

said point-to-point routing algorithm is Dijkstra'"'"'s algorithm.

4. A method according to claim 1 wherein

said step of deriving includes the step of

continuously monitoring the current state of said quality of interconnectivities;

and

said step of employing includes the step of

updating said routing decisions when said quality of interconnectivities changes.

6. A method according to claim 3, wherein

said certain ones of said platforms are within a first line-of-sight range of that one of said platforms initiating communication where said platform initiating communication is on a direct line with said certain ones, and

said certain others of said platforms are outside of said first line-of-sight range but within a second line-of-sight range relative to at least one of said certain ones of said platforms other than that one of said platforms initiating communication where said platform initiating communication is not in a direct line with said certain ones.

7. A method according to claim 3, wherein

said Dijkstra'"'"'s algorithm provides a route from an originating platform to a destination platform one platform at a time starting with said originating platform and adding one platform at a time until said destination platform is reached always selecting the next platform on the route to destination.

8. A method according to claim 1, wherein

said point-to-point routing algorithm is a truncated Dijkstra algorithm.

9. A method according to claim 1 wherein

said step of deriving includes the step of

continuously monitoring the current state of said quality of interconnectivities;

and

said step of employing includes the step of

updating said routing decisions when said quality of interconnectivities changes.

10. A method according to claim 8 wherein

said step of employing includes the steps of

establishing and maintaining knowledge of said connectivities in said system;

and

using said knowledge effectively to satisfy communication message deliverability requirements for both data and voice traffic in a timely fashion.

11. A method according to claim 8, wherein

said certain ones of said platforms are within a first line-of-sight range of that one of said platforms initiating communication, and

said certain others of said platforms are outside of said first line-of-sight range but within a second line-of-sight range relative to at least one of said certain ones of said platforms other than that one of said platforms initiating communication.

12. A method according to claim 8, wherein

said truncated Dijkstra algorithm provides a route from an originating platform to a destination platform one platform at a time starting from said originating platform and progressing toward said destination platform in hops of predetermined length until said destination platform is reached always selecting the next platform on the route to the destination.

13. A method according to claim 1, wherein

said routing decisions employ a point-to-multipoint routing algorithm.

14. A method according to claim 1 wherein

said step of deriving includes the steps of

continuously monitoring the current state of said quality of interconnectivities;

and

said step of employing includes the step of

updating said routing decisions when said quality of interconnectivities changes.

16. A method according to claim 13, wherein

said certain ones of said platforms are within a first line-of-sight range of that one of said platforms initiating communication, and

said certain others of said platforms are outside of said first line-of-sight range but within a second line-of-sight range relative to at least one of said certain ones of said platform other than that one of said platforms initiating communication.

17. A method according to claim 13, wherein said point-to-multipoint algorithm includes the steps of

an originating platform selecting the smallest set of prospective first remote platforms needed to begin routing its message to all destination platforms, with said remote platforms to operate as relay platforms for routing said message to said destination platforms,

each of said selected first relay platforms determining which of said destination platforms motivated its selection as a relay, and

each of said selected first relay platforms, after determining said destination platform for which it is responsible, repeating said originating platform process to select successor relay platforms as required.

18. A method according to claim 17, wherein

a selected relay platform assumes responsibility for a particular destination platform if and only if said selected relay platform lies in a minimum distance path from said originating platform to said destination platform.

19. A method according to claim 1, wherein

said routing decisions employ said broadcast routing algorithm.

20. A method according to claim 1 wherein

said step of deriving includes the steps of

continuously monitoring the current state of said quality of interconnectivities;

and

said step of employing includes the step of

updating said routing decisions when said quality of interconnectivities changes.

21. A method according to claim 1, wherein

said step of employing includes the steps of

establishing and maintaining knowledge of said connectivities in said system;

and

using said knowledge effectively to satisfy communication message deliverability requirements for both data and voice traffic in a timely fashion.

22. A method according to claim 19, wherein

said certain ones of said platforms are within a first line-of-sight range of that one of said platforms initiating communication, and

said certain others of said platforms are outside of said first line-of-sight range but within a second line-of-sight range relative to at least one of said certain ones of said platforms other than that one of said platforms initiating communication.

5. A method according to claim wherein

said step of employing includes the steps of

establishing and maintaining knowledge of said connectivities in said system;

and

using said knowledge effectively to satisfy communication message deliverability requirements for both data and voice traffic in a timely fashion.

15. A method according to claim wherein

said step of employing includes the steps of

establishing and maintaining knowledge of said connectivities in said system;

and

using said knowledge effectively to satisfy communication message deliverability requirements for both data and voice traffic in a timely fashion.