Apparatus for selecting a route in a packet-switched communications network

• US 5,956,339 A
• Filed: 04/10/1997
• Issued: 09/21/1999
• Est. Priority Date: 10/17/1996
• Status: Expired due to Fees

• Current Assignee: Fujitsu Limited
• Original Assignee: Fujitsu Limited
• Inventors: Harada, Takayuki, Araya, Shinichi
• Primary Examiner(s): Kizou, Hassan
• Assistant Examiner(s): TOWNSEND, CLEMENT G
• Application Number:
  US08/837,235
• Time in Patent Office: 894 Days
• Field of Search: 370/351, 370/238, 370/400, 370/408, 370/409, 370/389, 370/396, 370/397, 395/200.68, 395/200.71
• US Class Current: 370/400
• CPC Class Codes: H04L 2012/562 Routing
• 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/22 Alternate routing
• CPC Class Codes: H04L 45/38 Flow based routing
• CPC Class Codes: H04Q 11/0478 Provisions for broadband connections

Abstract

An apparatus for selecting a route in a packet-switched network where a plurality of candidate routes are available between a sending node and a receiving node. Total capacity calculation unit disposed in the sending node calculates the total channel capacity of each candidate route by summing up channel capacities of the inter-node links between the sending node and the receiving node. First selection unit chooses the candidate route(s) that exhibit the largest value of the total channel capacity. Uniformity calculation unit is activated when the first selection unit selected a plurality of candidate routes. The uniformity calculation unit calculates uniformity of each candidate route by evaluating the channel capacities of the inter-node links. The second selection unit chooses one of the candidate routes based on the calculated uniformity. This route will be used in packet transmission from the sending node to the receiving node.

Claims

1. An apparatus for selecting a route in a packet-switched communications network where a plurality of candidate routes are available between a sending node and a receiving node, each candidate route being formed by a plurality of inter-node links that are joined together by relaying nodes, the inter-node links having predetermined channel capacities, the apparatus comprising:

total capacity calculation means for calculating total channel capacity of each candidate route by summing up the channel capacities of the inter-node links between the sending node and the receiving node;

first selection means for obtaining at least one first-selected route by choosing at least one candidate route that exhibits the largest value of the total channel capacity calculated by said total capacity calculation means;

uniformity calculation means, activated when said first selection means selected a plurality of first-selected routes, for calculating uniformity of each of the first-selected routes by evaluating the channel capacities of the inter-node links thereof; and

second selection means, coupled to said uniformity calculation means, for choosing one of the first-selected routes based on the uniformity calculated by said uniformity calculation means.

2. The apparatus according to claim 1, wherein said uniformity calculation means comprises

average value calculation means for calculating an average value of the channel capacities of the inter-node links constituting each of the first-selected route, and

uniformity determination means for determining the uniformity of each first-selected route by

calculating a reciprocal value of a difference between the channel capacity of each inter-node link and the average value that is calculated by said average value calculation means, and

extracting the largest reciprocal value from among the reciprocal values calculated for all the inter-node links as part of each first-selected route.

3. An apparatus for selecting a route in a packet-switched communications network where a plurality of candidate routes are available between a sending node and a receiving node, each candidate route being formed by a plurality of inter-node links that are joined together by relaying nodes, the inter-node links having predetermined channel capacities, the apparatus comprising:

total capacity calculation means for calculating total channel capacity of each candidate route by summing up the channel capacities of the inter-node links between the sending node and the receiving node;

first selection means for obtaining at least one first-selected route by choosing at least one candidate route that exhibits the largest value of the total channel capacity calculated by said total capacity calculation means;

decision means, activated when said first selection means selected a plurality of first-selected routes, for investigating each relaying node involved in each first-selected route to clarify whether the relaying node under the investigation has any branching link that branches toward another node that does not belongs to the first-selected route under the investigation; and

second selection means, coupled to said decision means, for choosing one of the first-selected routes based on results of the investigation performed by said decision means.

4. The apparatus according to claim 3 further comprising:

summation means, activated when said decision means clarified that all the first-selected routes have at least one branching link to another node, for obtaining a total branching capacity for each of the first-selected routes by summing up the channel capacities of all the branching links originating from the relaying nodes thereof, and

third selection means coupled to said summation means for choosing one of the first-selected routes which exhibits the smallest total branching capacity.

5. An apparatus for selecting a route in a packet-switched communications network where a plurality of candidate routes are available between a sending node and a receiving node, each candidate route being formed by a plurality of inter-node links that are joined together by relaying nodes, the inter-node links having predetermined channel capacities, the apparatus comprising:

usable capacity calculation means for calculating a usable channel capacity of each inter-node link of each candidate route, the usable channel capacity being a portion of the channel capacity that can be used for packet transmission from the sending node to the receiving node via the candidate route under investigation;

total capacity calculation means for calculating total channel capacity of each candidate route by summing up the usable channel capacity calculated by said usable capacity calculation means; and

selection means for choosing one candidate route that exhibits the largest value of the total channel capacity calculated by said total capacity calculation means.

6. The apparatus according to claim 5, wherein said usable capacity calculation means comprises

first usable capacity calculation means for calculating the usable channel capacity, while considering affection of packet traffic to/from other nodes when the relaying nodes on the candidate route have at least one branching link that branches toward another node that does not belongs to the candidate route concerned, and

second usable capacity calculation means for calculating the usable channel capacity, while assuming that the whole channel capacity of each inter-node link on the candidate route can be used for packet transmission from the sending node to the receiving node, when the relaying nodes on the candidate route have no branching links.

7. An apparatus for selecting a route in a packet-switched communications network where a plurality of sending nodes are linked to a particular relaying node and a plurality of candidate routes are available between the particular relaying node and a receiving node, each candidate route being formed by a plurality of inter-node links that are joined together by other relaying nodes, the inter-node links having predetermined channel capacities, the apparatus comprising:

total capacity calculation means for calculating total channel capacity of each candidate route by summing up the channel capacities of the inter-node links between the sending node and the receiving node;

selection means for choosing at least one candidate route that exhibits the largest value of the total channel capacity calculated by said total capacity calculation means; and

signal assignment means, activated when said selection means chose a plurality of candidate routes, for assigning signals sent to/from the plurality of sending nodes equally to the plurality of candidate routes selected by said selection means.

8. An apparatus for selecting a route in a packet-switched communications network where a plurality of candidate routes are available between a sending node and a receiving node, each candidate route being formed by a plurality of inter-node links that are joined together by other relaying nodes, the inter-node links having predetermined channel capacities, the sending node handling transmission signals to/from a plurality of user terminals, the apparatus comprising:

total capacity calculation means for calculating total channel capacity of each candidate route by summing up the channel capacities of the inter-node links between the sending node and the receiving node;

selection means for choosing at least one candidate route that exhibits the largest value of the total channel capacity calculated by said total capacity calculation means; and

signal assignment means, activated when said selection means chose a plurality of candidate routes, for assigning the transmission signals sent to/from the plurality of user terminals equally to the plurality of candidate routes selected by said selection means.

9. An apparatus for selecting a route in a packet-switched communications network where a plurality of candidate routes are available between a sending node and a receiving node, each candidate route being formed by a plurality of inter-node links that are joined together by relaying nodes, the inter-node links having predetermined channel capacities, the apparatus comprising:

total capacity calculation means for calculating total channel capacity of each candidate route by summing up the channel capacities of the inter-node link between the sending node and the receiving node;

first selection means for obtaining at least one first-selected route by choosing at least one candidate route that exhibits the largest value of the total channel capacity calculated by said total capacity calculation means;

decision means, activated when said first selection means selected a plurality of first-selected routes, for examining whether each first-selected route has a spare channel for backup purposes or not; and

second selection means, activated when said decision means found that there is only one first-selected routes having a spare channel, for choosing said only one first-selected routes.

10. The apparatus according to claim 9, further comprising:

backup ratio calculation means, activated when said decision means found that two or more routes out of the first-selected routes have a spare channel, for calculating a backup ratio that indicates how much percent of the channel capacity are backed up by the spare route, and

third selection means for choosing one of the first-selected routes that exhibits the largest value of the backup ratio calculated by said backup ratio calculation means.

11. The apparatus according to claim 10, said backup ratio calculation means comprises

working-channel capacity summation means for calculating total working-channel capacity by summing up the channel capacities of the inter-node links of each working channel as part of each first-selected route having the spare channel,

spare-channel capacity summation means for calculating total spare-channel capacity by summing up the channel capacities of the inter-node links of each spare channel as part of each first-selected route having the spare channel, and

division means for obtaining the backup ratio by dividing the total spare-channel capacity by the total working-channel capacity.

12. An apparatus for selecting a route in a packet-switched communications network where a plurality of candidate routes are available between a sending node and a receiving node, each candidate route being formed by a plurality of inter-node links that are joined together by relaying nodes, the inter-node link having predetermined channel capacities, the apparatus comprising:

total capacity calculation means for calculating total channel capacity of each candidate route by summing up the channel capacities of the inter-node links between the sending node and the receiving node;

first selection means for obtaining at least one first-selected route by choosing at least one candidate route that exhibits the largest value of the total channel capacity calculated by said total capacity calculation means;

uniformity calculation means, activated when said first selection means selected a plurality of first-selected routes, for calculating uniformity of each of the first-selected routes by evaluating the channel capacities of the inter-node links thereof;

second selection means, coupled to said uniformity calculation means, for obtaining at least one second-selected route by choosing at least one of the first-selected routes based on the uniformity calculated by said uniformity calculation means;

first decision means, activated when said second selection means selected a plurality of second-selected routes, for investigating each relaying node involved in each second-selected route to clarify whether the relaying node under the investigation has any branching link that branches toward another node that does not belongs to the second-selected route under the investigation;

summation means, activated when said first decision means clarified that all the second-selected routes have at least one branching link to another node, for obtaining a total branching capacity for each of the second-selected routes by summing up the channel capacities of all the branching links originating from the relaying nodes thereof;

third selection means coupled to said summation means for obtaining at least one third-selected route by choosing at least one of the second-selected routes which exhibits the smallest total branching capacity;

second decision means, activated when said third selection means selected a plurality of third-selected routes, for examining whether or not each third-selected route is equipped with a spare channel for backup purposes;

backup ratio calculation means, activated when said second decision means found that two or more routes out of the third-selected routes have a spare channel, for calculating a backup ratio that indicates how much percent of the channel capacity are backed up by the spare route; and

fourth selection means for choosing one of the third-selected routes that exhibits the largest value of the backup ratio calculated by said backup ratio calculation means.

13. An apparatus for selecting a route in a packet-switched communications network where a plurality of candidate routes are available between a sending node and a receiving node, each candidate route being formed by a plurality of inter-node links that are joined together by relaying nodes, the inter-node link having predetermined channel capacities, the apparatus comprising:

first total capacity calculation means for calculating total channel capacity of each candidate route by summing up the channel capacities of the inter-node links between the sending node and the receiving node;

first selection means for obtaining at least one first-selected route by choosing at least one candidate route that exhibits the largest value of the total channel capacity calculated by said first total capacity calculation means;

uniformity calculation means, activated when said first selection means selected a plurality of first-selected routes, for calculating uniformity of each of the first-selected routes by evaluating the channel capacities of the inter-node links thereof;

second selection means, coupled to said uniformity calculation means, for obtaining at least one second-selected route by choosing at least one of the first-selected routes based on the uniformity calculated by said uniformity calculation means;

usable capacity calculation means, activated when said second selection means selected a plurality of second-selected routes, for calculating a usable channel capacity of each inter-node link of each second-selected route, the usable channel capacity being a portion of the channel capacity that can be used for packet transmission from the sending node to the receiving node via the second-selected route concerned;

second total capacity calculation means for calculating total usable channel capacity of each second-selected route by summing up the usable channel capacity calculated by said usable capacity calculation means;

third selection means for obtaining at least one third-selected route by choosing at least one of the second-selected routes that exhibits the largest value of the total usable channel capacity calculated by said second total capacity calculation means;

decision means, activated when said third selection means selected a plurality of third-selected routes, for examining whether or not each third-selected route is equipped with a spare channel for backup purposes;

backup ratio calculation means, activated when said decision means found that two or more routes out of the third-selected routes have a spare channel, for calculating a backup ratio which indicates how much percent of the channel capacity are backed up by the spare route; and

fourth selection means for choosing one of the third-selected routes that exhibits the largest value of the backup ratio calculated by said backup ratio calculation means.

14. An apparatus for selecting a route in a packet-switched communications network where a plurality of candidate routes are available between a sending node and a receiving node, each candidate route being formed by a plurality of inter-node links that are joined together by relaying nodes, the inter-node links having predetermined channel capacities, the apparatus comprising:

usable capacity calculation means for calculating a usable channel capacity of each inter-node link of each candidate route, the usable channel capacity being a portion of the channel capacity that can be used for packet transmission from the sending node to the receiving node via the candidate route under investigation;

total capacity calculation means for calculating total channel capacity of each candidate route by summing up the usable channel capacity calculated by said usable capacity calculation means;

first selection means for obtaining at least one first-selected route by choosing at least one candidate route that exhibits the largest value of the total channel capacity calculated by said total capacity calculation means;

uniformity calculation means, activated when said first selection means selected a plurality of first-selected routes, for calculating uniformity of each of the first-selected routes by evaluating the channel capacities of the inter-node links thereof;

second selection means, coupled to said uniformity calculation means, for obtaining at least one second-selected route by choosing at least one of the first-selected routes based on the uniformity calculated by said uniformity calculation means;

decision means, activated when said second selection means selected a plurality of second-selected routes, for examining whether or not each second-selected route is equipped with a spare channel for backup purposes;

backup ratio calculation means, activated when said decision means found that two or more routes out of the second-selected routes each have a spare channel, for calculating a backup ratio which indicates how much percent of the channel capacity are backed up by the spare route; and

third selection means for choosing one of the second-selected routes that exhibits the largest value of the backup ratio calculated by said backup ratio calculation means.