System for establishing route by selecting minimum of time-independent link parameters of incremental values

• US 5,031,093 A
• Filed: 03/27/1990
• Issued: 07/09/1991
• Est. Priority Date: 12/22/1986
• Status: Expired due to Term

• Current Assignee: NEC Corporation
• Original Assignee: NEC Corporation
• Inventors: Hasegawa, Satoshi
• Primary Examiner(s): Lee, Thomas C.
• Application Number:
  US07/500,114
• Time in Patent Office: 469 Days
• Field of Search: 360/200 MS File, 360/900 MS File, 360/51, 370/16, 370/17, 370/60, 370/85.7, 370/94.2, 340/825.52
• US Class Current: 709/241
• CPC Class Codes: H04L 69/00 Network arrangements, protocols or services independent of the application payload and not provided for in the other groups of this subclass networks security protocols H04L9/40; wireless communication networks H04W

Abstract

A routing matrix for fixed routing is derived for a communications network having a plurality of nodes interconnected by links each having a link parameter. A second node which can be reached from a first node by a single hop is determined, and a third node which can be reached from the second node by (m-1) hops is determined, where m is an integer equal to or greater than unity. A route between the first and third nodes via the second node is selected if this route is the only route available therebetween. A route which minimizes a total of link parameters between the first and third nodes is selected if two or more routes are available between the first and third nodes. The identification of the second node of the selected route is stored in a location of a routing directory which can be addressed in response to the identifications of the first and third nodes. The above steps are repeated by shifting the first node to the next and incrementing the value m by one.

Claims

1. In a communication network of multiple nodes interconnected by links, a method for establishing a route between a source node and a destination node via an intermediate node, said nodes having respective identifications and each of said links having a link parameter of time-independent value, comprising the steps of:

a) determining a second node as corresponding to said intermediate node which is reached from a first node by a single hop, said first node corresponding to said source node;

b) determining a third node as corresponding to said destination node which is reached from said second node by (m-1) hops, where m is an integer equal to or greater than unity;

c) selecting links on a route between said first and third nodes via said second node if, said route of the selected links is the only route available between said first and third nodes;

d) if said route of the selected links is not the only route available between said first and third nodes, storing initial values of the link parameters of possible routes between said first and third nodes in matrix locations of a link parameter memory, said link parameters representing an amount of traffic carried by a link;

e) incrementing said initial values of said selected links by a predetermined amount to update said link parameter memory;

(f) summing said link parameters of said possible routes;

g) selecting links on one of said possible routes which give a minimum sum of the link parameters;

h) storing an identification of a second node of the links selected according to step (c) or (g) in a routing memory addressable as a function of identifications of said first and third nodes;

i) repeating steps (a) to (h) by shifting a first node to the next and incrementing the value m by one to thereby store a plurality of identifications of said second node in said routing memory; and

j) recalling one of said stored identifications from said routing memory as a function of identifications of said source and destination nodes and establishing a route between said source node and said destination nodes through an intermediate node having said recalled identification.

2. A communications system having a plurality of nodes interconnected by links each having a link parameter of time-independent value, comprising:

a routing matrix memory storing an array of node identifications in locations addressable as a function of address information supplied thereto; and

means for recalling one of said node identifications from said routing matrix memory as a function of identifications of a source node and a destination node and establishing a route therebetween through an intermediate node having said recalled node identification,

said array of node identifications being stored in said routing matrix memory by a process including the steps of;

a) determining a second node as corresponding to said intermediate node which is reached from a first node by a single hop, said first node corresponding to said source node;

b) a determining a third node as corresponding to said destination node which is reached from said second node by (m-1) hops, where m is an integer equal to or greater than unity;

c) selecting links on a route between said first and third nodes via said second node if said route of said selected links is the only route available between said first and third nodes;

d) if said route of said selected links is not the only route available between said first and third nodes, storing initial values of the link parameters in locations of a link parameter matrix memory, said link parameters representing an amount of traffic carried by a link;

e) incrementing said initial values of said selected links by a predetermined amount to update said link parameter matrix memory;

f) summing link parameters of possible routes;

g) selecting links on one of said possible routes which give a minimum sum of the link parameters;

h) storing an identification of a second node of the links selected according to step (c) or (g) in a location of said routing matrix memory addressable as a function of identifications of said first and third nodes; and

i) repeating steps (a) to (h) by shifting a first node to the next and incrementing the value m by one.

3. A method for establishing a route between a source node and a destination node via an intermediate node in a communications network, said nodes having respective identifications and being interconnected by links each having a link parameter of time-independent value, comprising the steps of:

a) determining an intermediate node which is reached from a source node by a single hop;

b) determining a destination node which is reached from said intermediate node by (m-1) hops, where m is an integer equal to or greater than unity;

c) selecting links on a route between said source node and said destination node via said intermediate node if said route is the only route available between said source node and said destination node;

d) if said route of said selected links is not the only route available between said source and destination nodes, setting initial values of the link parameters of possible routes between said source node and said destination node, said link parameters representing an amount of traffic carried by a link;

e) incrementing said initial values of said selected links by a predetermined amount;

f) summing said link parameters of said possible routes;

g) selecting links on one of said possible routes which give a minimum sum of the link parameters; and

h) establishing a route between said source node and said destination node via an intermediate node via the links selected by step (c) or (g).