Method and apparatus for routing communications among computer networks

A method performed by a computer for dynamically routing a data transmission from a source computer to a destination computer with a gateway, comprising the steps of:

• a) identifying routing paths from said gateway to said destination computer;
• b) characterizing each of said paths by at least one metric value corresponding to a characteristic of the path;
• c) transmitting said metric value for each identified path to at least one gateway coupled to said gateway as an update message;
• d) storing data from update messages received;
• d) deactivating a path when an update message indicates an increase of more than 2 in a hop count that is incremented at each gateway along a path;
• f) ceasing to accept update information about a destination for a predetermined period of time when the metric value for the best path to said destination has deteriorated by more than a predetermined amount;
• g) not sending information about a destination out the same interface from which said information was originally obtained;
• h) determining a best path from said metric values;
• and
• i) directing data transmissions over said best path.

A gateway for routing a data transmission in a network from a source computer to a destination computer, comprising:

• means for identifying routing paths from said gateway to said destination computer;
• means for characterizing each of said paths by a vector of metric values, each of said metric values corresponding to a characteristic of a path;
• means for transmitting said vector of metric values to a node in said network;
• means for computing a single composite metric from a first predetermined algorithm based on said vector of metric values;
• means for determining a best path from a second predetermined algorithm based on said composite metric;
• and
• means for directing said data transmission over said best path.

A gateway for routing a data transmission from a source computer to a destination computer, comprising:

• a) means for identifying routing paths from said gateway to said destination computer;
• b) means for characterizing each of said paths by at least one metric value corresponding to a characteristic of the path;
• c) means for transmitting said metric value for each identified path to at least one gateway coupled to said gateway as an update message;
• d) means for storing data from update messages received;
• d) means for deactivating a path when an update message indicates an increase of more than 2 in a hop count that is incremented at each gateway along a path;
• f) means for ceasing to accept update information about a destination for a predetermined period of time when the metric value for the best path to said destination has deteriorated by more than a predetermined amount;
• g) means for not sending information about a destination out the same interface from which said information was originally obtained;
• h) means for determining a best path from said metric values;
• and
• i) means for directing data transmission over said best path.

A method performed by a processor of dynamically routing data from a source to a destination in a network having an intermediate node, said method comprising

• identifying at least one routing path from said node to said destination;
• associating each said path with a plurality of routing data items, each of said routing data items being representative of a routing characteristic of said path;
• transmitting said plurality of routing data items to a node in said network;
• and
• selecting at least one preferred path based on said plurality of routing data items.

An intermediate node in a network for routing data from a source to a destination, comprising

• means for identifying at least one routing path from said node to said destination;
• means for associating each said path with a plurality of routing data items, each of said routing data items being representative of a routing characteristic of said path;
• means for transmitting said plurality of routing data items to a node in said network;
• and
• means for selecting at least one preferred path based on said plurality of routing data items.

A network for routing data from a source to a destination, said network comprising at least one intermediate node having

• means for identifying at least one routing path from said node to said destination;
• means for associating each said path with a plurality of routing data items, each of said routing data items being representative of a routing characteristic of said path;
• means for transmitting said plurality of routing data items to a node in said network;
• and
• means for selecting at least one preferred path based on said plurality of routing data items.

A method performed by a processor of dynamically routing a message from a source to a destination in a network having an intermediate node, said method comprising

• determining a transmission type of said message;
• identifying at least one routing path from said node to said destination;
• associating each said path with a routing data item which is representative of at least one routing characteristic of said path, wherein the choice of said routing data item is based on said transmission type;
• and
• selecting at least one preferred path based on said plurality of routing data items.

An intermediate node in a network for routing a message from a source to a destination, comprising

• means for determining a transmission type of said message;
• means for identifying at least one routing path from said node to said destination;
• means for associating each said path with a routing data item which is representative of at least one routing characteristic of said path, wherein the choice of said routing data item is based on said transmission type;
• and
• means for selecting at least one preferred path based on said plurality of routing data items.

A network for routing a message from a source to a destination, said network comprising at least one intermediate node having

• means for determining a transmission type of said message;
• means for identifying at least one routing path from said node to said destination;
• means for associating each said path with a routing data item which is representative of at least one routing characteristic of said path, wherein the choice of said routing data item is based on said transmission type;
• and
• means for selecting at least one preferred path based on said plurality of routing data items.

A method performed by a processor of dynamically routing a message from a source to a destination in a network having an intermediate node, said method comprising

• determining a transmission type of said message;
• identifying at least one routing path from said node to said destination;
• associating each said path with a plurality of routing data items, each of said routing data items being representative of a routing characteristic of said path, wherein the choice of at least one of said plurality of routing data items is based on said transmission type;
• and
• selecting at least one preferred path based on said plurality of routing data items.

A method performed by a processor of routing data from a source to a destination in a network having an intermediate node and a plurality of routing paths from said node to said destination, said method comprising;

• characterizing each routing path with at least one routing characteristic;
• selecting as a first routing path, the routing path characterized with a most preferred routing characteristic in accordance with a predetermined condition;
• selecting as a set of second routing paths, the routing paths each characterized with a routing characteristic within a predetermined tolerance of the routing characteristic the first routing path;
• identifying said first routing path and said set of second routing paths as a plurality of preferred routing paths;
• and
• routing at least part of said data along each of said plurality of preferred routing paths.

A method performed by a processor of routing data from a source to a destination in a network having an intermediate node and a plurality of routing paths from said node to said destination, said method comprising:

• characterizing each routing path with at least one routing characteristic;
• selecting as a first routing path, the routing path characterized with a minimum routing characteristic M;
• selecting as a set of second routing paths, the routing paths each characterized with routing characteristics less than M.times.V, wherein V is a predetermined tolerance factor;
• identifying said first routing path and said set of second routing paths as in plurality of preferred routing paths;
• and
• routing at least part of said data along each of said plurality of preferred routing paths.

A method performed by a processor of dynamically routing a message from a source to a destination in a network having an intermediate node, said method comprising

• determining a transmission type of said message and a plurality of message data items of said message;
• identifying at least one routing path from said node to said destination;
• associating each said path with a routing data item which is representative of at least one routing characteristic of said path, wherein the choice of said routing data item is based on said transmission type;
• identifying a plurality of preferred routing paths from said node to said destination based on said routing data item;
• and
• routing at least some of said message data items along each of said plurality of preferred routing paths.

A method performed by a processor of dynamically routing a data message from a source to a destination in a network having an intermediate node, said method comprising

• receiving an incoming update message from at least one transmitting node coupled to said node, said incoming update message comprising at least one network data item;
• identifying at least one routing path from said node to said destination;
• associating each said path with a routing data item based on said network data item;
• deactivating a said path from selection whenever a predetermined routing data item differs from a previous value of said routing data item by more than a predetermined tolerance;
• and
• selecting at least one preferred path based on said routing data item.

An intermediate node in a network for routing a data message from a source to a destination, comprising

• means for receiving an incoming update message from at least one transmitting node coupled to said node, said incoming update message comprising at least one network data item;
• means for identifying at least one routing path from said node to said destination;
• means for associating each said path with a routing data item based on said network data item;
• means for deactivating a said path from selection whenever a predetermined routing data item differs from a previous value of said routing data item by more than a predetermined tolerance;
• and
• means for selecting at least one preferred path based on said routing data item.

A network for routing a data message from a source to a destination, said network comprising at least one intermediate node having

• means for receiving an incoming update message from at least one transmitting node coupled to said node, said incoming update message comprising at least one network data item;
• means for identifying at least one routing path from said node to said destination;
• means for associating each said path with a routing data item based on said network data item;
• means for deactivating a said path from selection whenever a predetermined routing data item differs from a previous value of said routing data item by more than a predetermined tolerance;
• and
• means for selecting at least one preferred path based on said routing data item.

A method performed by a processor of dynamically routing data from a source to a destination in a network having an intermediate node, said method comprising

• receiving an incoming update message from at least one transmitting node coupled to said node, said incoming update message comprising at least one network data item;
• associating each said path with a routing data item based on said network data item;
• identifying a plurality of preferred routing paths from said node to said destination based on said routing data item;
• deactivating a said path from selection whenever a predetermined routing data item differs from a previous value of said routing data item by more than a predetermined tolerance;
• and
• routing at least part of said data along each of said plurality of preferred routing paths.

A method performed by a processor of dynamically routing a data message from a source to a destination in a network having an intermediate node, said method comprising

• receiving an incoming update message from at least one transmitting node coupled to said node, said incoming update message comprising at least one network data item;
• determining a transmission type of said data message and a plurality of message data items of said data message;
• identifying at least one routing path from said node to said destination;
• associating each said path with a plurality of routing data items, each of said routing data items being representative of a routing characteristic of said path, wherein the choice of at least one of said plurality of routing data items is based on said transmission type, and wherein at least one said routing data item is based on said network data item;
• deactivating a said path from selection whenever a predetermined routing data item differs from a previous value of said routing data item by more than a predetermined tolerance;
• identifying a plurality of preferred routing paths from said node to said destination based on said plurality of routing data items;
• and
• routing at least some of said message data items along each of said plurality of preferred routing paths.