Multiple path routing mechanism for packet communications network

• US 4,905,233 A
• Filed: 11/23/1987
• Issued: 02/27/1990
• Est. Priority Date: 11/23/1987
• Status: Expired due to Fees

• Current Assignee: Harris Corporation (L3Harris Technologies, Inc.)
• Original Assignee: Harris Corporation (L3Harris Technologies, Inc.)
• Inventors: Cain, Joseph B., Adams, Stanley L., Noakes, Michael D.
• Primary Examiner(s): Olms, Douglas W.
• Assistant Examiner(s): Jung, Min
• Application Number:
  US07/124,282
• Time in Patent Office: 827 Days
• Field of Search: 370/94, 370/60, 370/13, 370/14, 370/17, 370/54, 370/104, 178/3
• US Class Current: 370/237
• 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/24 Multipath
• CPC Class Codes: H04Q 3/665 Circuit arrangements therefor

Abstract

A mechanism for establishing at least one transmission route between a source node and a destination node in a multinode communications network comprises monitoring transmission characteristics of each of the transmission paths among the respective nodes of the network so as to derive a plurality of path metrics representative of the ability of the respective transmission paths of the network to transmit communication signals. Then, feasible transmission routes to be used for the transmission of communication signals from the source node to the destination node are selected as those routes which extend from the source node to the destination node and each of which is comprised of one or more transmission paths among the nodes of the network and the sum of path metrics of transmission paths from neighboring nodes to the destination node is less than the path metric of a transmission path the end nodes of which correspond to the source and destination nodes. Communication signals are then transmitted from the source node to the destination node over the selected feasible transmission routes.

Claims

1. For use in a multinode communications network having a plurality of communication nodes each of which is capable of transmitting communication signals to and receiving communication signals from other nodes of the network, so that at least one transmission route from a source node to a destination node may be established among plural nodes of the network, a method of establishing at least one transmission route between a source node at which communication signals originate and a destination node for which communication signals originating at said source node are to be transmitted comprising the steps of:

(a) monitoring transmission characteristics of each of the transmission paths among the nodes of the network so as to derive therefrom a plurality of path metrics representative of the ability of the transmission paths of the network to transmit communication signals thereover;

(b) selecting, as feasible transmission routes to be used for the transmission of communication signals from said source node to said destination node, those routes which extend from said source node through neighbor nodes thereof to said destination node and each of which is comprised of one or more transmission paths among the nodes of the network the sum of path metrics of transmission paths from said neighbor nodes to said destination node is less than the path metric of a transmission path the end nodes of which correspond to said source and destination nodes; and

(c) transmitting communication signals from said source node to said destination node over the feasible transmission routes selected in step (b).

2. A method according to claim 1, wherein step (c) comprises allocating the use of each of said selected feasible transmission routes for the transmission of communication signals thereover in accordance with a prescribed relationship between the path metric sum for said each of said selected feasible transmission routes and the path metrics of the other selected feasible routes.

3. A method according to claim 2, wherein step (c) comprises allocating the use of each of said selected feasible transmission routes for the transmission of communication signals thereover in accordance with the ratio of the inverse of the path for said each of said selected feasible trnsmission routes metric sum to the total of the inverse of the path metric sums of each of said feasible routes.

4. For use in a multinode communications network having a plurality of communication nodes each of which is capable of transmitting communication signals to and receiving communication signals from other nodes of the network, so that at least one transmission route from a source node to a destination node may be established among plural nodes of the network, a method of establishing at least one transmission route between a source node at which communication signals originate and a destination node for which communication signals originating at said source node are to be transmitted comprising the steps of:

(a) monitoring transmission characteristics of each of the transmission paths among the nodes of the network so as to derive therefrom a plurality of data representative of the ability of the transmission paths of the network to transmit communication signals thereover;

(b) selecting, as feasible transmission routes to be used for the transmission of communication signals from said source node to said destination node, those routes which extend over transmission paths from said source node to said destination node and contain those neighbor nodes of said source which are located closer to said destination node than said source node; and

(c) transmitting communication signals from said source node to said destination node over the feasible transmission routes selected in step (b).

5. A method according to claim 4, wherein step (c) comprises allocating the use of each of said selected feasible transmission routes for the transmission of communication signals thereover in accordance with a prescribed relationship between the sum of the transmission capability data derived for the paths of said each of said selected feasible transmission routes and for the paths of the other selected feasible routes.

6. A method according to claim 5, wherein step (c) comprises allocating the use of each of said selected feasible transmission routes for the transmission of communication signals thereover in accordance with the ratio of the sum of the transmission capability data for the paths of said each of feasible transmission routes to the total of the data sums of each of said feasible routes.

7. A method according to claim 4, further including the step of:

(d) in response to the occurrence of a failure of at least a portion of a transmission route between nodes of the network, reperforming step (b) in accordance with transmission capability data monitored in step (a) for feasible routes exclusive of the route in which said failure has occurred; and

(e) transmitting communication signals from said source node to said destination node over the feasible transmission routes selected in step (d).

8. A method according to claim 7, wherein step (c) comprises allocating the use of each of said selected feasible transmission routes for the transmission of communication signals thereover in accordance with a prescribed relationship between the sum of the transmission capability data derived for the paths of said each of said selected feasible transmission routes and for the paths of the other selected feasible routes.

9. A method according to claim 8, wherein step (c) comprises allocating the use of each of said selected feasible transmission routes for the transmission of communication signals thereover in accordance with the ratio of the sum of the transmission capability data for the paths of said each of said feasible transmission routes to the total of the transmission capability data sums of each of said feasible routes.

10. For use in a multinode communications network having a plurality of communication nodes each of which is capable of transmitting communication signals to and receiving communication signals from other nodes of the network, so that at least one transmission route from a source node to a destination node may be established among plural nodes of the network, a method of establishing at least one transmission route between a source node at which communication signals originate and a destination node for which communication signals originating at said source node are to be transmitted comprising the step of:

(a) monitoring transmission characteristics of each of the transmission paths among the nodes of the network so as to derive therefrom a plurality of data representative of the ability of the transmission paths of the network to transmit communication signals thereover;

(b) selecting, as a virtual circuit to be used for the transmission of communication signals from said source node to said destination node, one of those routes which extend over transmission paths from said source node to said destination node and contain those neighbor nodes of said source which are located closer to said destination node than said source node; and

(c) transmitting communication signals from said source node to said destination node over the virtual circuit selected in step (b).

11. A method according to claim 10, wherein step (b) further includes the step of selecting, as feasible transmission routes to be used for the transmission of communication signals from said source node to said destination node, others of those routes which extend over transmission paths from said source node to said destination node and contain only nodes which are neighbor nodes of said source node and are located closer to said destination node than said source node, and step (c) comprises transmitting communication signals from said source node to said destination node over said feasible transmission routes selected in step (b).

12. A method according to claim 11, wherein step (c) comprises allocating the use of each of said virtual circuit and said selected feasible transmission routes for the transmission of communication signals so as to effectively balance the flow of communication traffic thereover.

13. In a multinode communications network having a plurality of communication nodes each of which is capable of transmitting communication signals to and receiving communication signals from other nodes of the network, so that at least one transmission route from a source node to a destination node may be established among plural nodes of the network, an arrangement for establishing at least one transmission route between a source node at which communication signals originate and a destination node for which communication signals originating at said source node are to be transmitted comprising:

means for monitoring transmission characteristics of each of the transmission paths among the nodes of the network so as to derive therefrom a plurality of data representative of the ability of the transmission paths of the network to transmit commtnication signals thereover; and

means for transmitting communication signals from said source node to said destination node over those transmission routes which extend over transmission paths from said source node to said destination node and contain those neighbor nodes of said source which are located closer to said destination node than said source node.

14. An arrangement according to claim 13, further including means for allocating the use of each of said transmission routes for the transmission of communication signals thereover in accordance with a prescribed relationship between the sum of the transmission capability data derived for the paths of said each route and the paths of the other routes.

15. An arrangement according to claim 13, wherein said allocating means comprises means for allocating the use of each of said transmission routes for the transmission of communication signals thereover in accordance with the ratio of the sum of the transmission capability data for the paths of said each of said feasible transmission routes to the total of the data sums of each of said routes.

16. An arrangement according to claim 15, further including means, responsive to the occurrence of a failure of at least a portion of a transmission route between nodes of the network, for transmitting communication signals from said source node to said destination node over those transmission routes which extend over transmission paths from said source node to said destination node and contain only nodes which are neighbor nodes of said source and are located closer to said destination node than said source node and are exclusive of the route in which said failure has occurred.

17. An arrangement according to claim 13, further including means for allocating the use of each of said transmission routes for the transmission of communication signals thereover in accordance with a prescribed relationship between the sum of the transmission capability data derived for the paths of said each route and those of the other routes.

18. For use in a multinode communications network having a plurality of communication nodes each of which is capable of transmitting communication signals to and receiving communication signals from other nodes of the network, so that at least one transmission route from a source node to a destination node may be established among plural nodes of the network, an arrangement for establishing at least one transmission route between a source node at which communication signals originate and a destination node for which communication signals originating at said source node are to be transmitted comprising;

means for monitoring transmission characteristics of each of the transmission paths among the nodes of the network so as to derive therefrom a plurality of data representative of the ability of the transmission paths of the network to transmit communication signals thereover;

means for selecting, as a virtual circuit to be used for the transmission of communication signals from said source node to said destination node, one of those routes which extend over transmission paths from said source node to said destination node and contain those neighbor nodes of said source which are located closer to said destination node than said source node; and

means for transmitting communication signals from said source node to said destination node over the selected virtual circuit.

19. An arrangement according to claim 18, wherein said selecting means includes means for selecting, as feasible transmission routes to be used for the transmission of communication signals from said source node to said destination node, others of those routes which extend over transmission paths from said source node to said destination node and contain only nodes which are neighbor nodes of said source node and are located closer to said destination node than said source node, and said transmission means comprises means for transmitting communication signals from said source node to said destination node over said selected feasible transmission routes.

20. An arrangement according to claim 19, further including mans for allocating the use of each of said virtual circuit and said selected feasible transmission routes for the transmission of communication signals by said transmitting means, so as to effectively balance the flow of communication traffic thereover.