Method and apparatus for routing communications among computer networks

• US 5,088,032 A
• Filed: 01/29/1988
• Issued: 02/11/1992
• Est. Priority Date: 01/29/1988
• Status: Expired due to Term

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Systems, Inc.
• Inventors: Bosack, Leonard
• Primary Examiner(s): Shaw, Gareth D.
• Assistant Examiner(s): Kriess, Kevin A.
• Application Number:
  US07/149,820
• Time in Patent Office: 1,474 Days
• Field of Search: 364/200 MS File, 364/900 MS File, 370/94, 370/94.1, 370/94.3, 370/60.1
• US Class Current: 709/242
• CPC Class Codes: H04Q 2213/13141 Hunting for free outlet, circuit or channel
• CPC Class Codes: H04Q 2213/13148 Maximum profit routing
• CPC Class Codes: H04Q 2213/13196 Connection circuit/link/trunk/junction, bridge, router, gateway
• CPC Class Codes: H04Q 2213/13204 Protocols
• CPC Class Codes: H04Q 3/665 Circuit arrangements therefor

Abstract

An improved method and apparatus for routing data transmissions among computer networks. The computer networks are interconnected with a series of gateway circuits. Each gateway identifies all destination computers to which it is connected and identifies the path or paths to each destination computer. For each identified path, the gateway stores the topological delay time for a transmission, the path bandwidth for the narrowest bandwidth segment of a path and a number corresponding to the reliability of the path. When a transmission is received, the gateway examines the various paths in accordance with a predetermined algorithm which also considers the channel occupancy of each path to determine a best path for transmision. The data transmission is then directed over the best path. If more than one path exists, the data may be directed in multiplex fashion over two or more paths with the amount of data on each path being related to the quality of the path. The routing information to destination networks is broadcast periodically by each gateway circuit to its neighboring gateway circuits.

Claims

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

identifying routing paths from said gateway to said destination computer;

characterizing each of said paths by a vector of metric values, each of said metric values corresponding to a characteristic of a path;

transmitting said vector of metric values to a node in said network;

computing a single composite metric from a first predetermined algorithm based on said vector of metric values;

determining a best path from a second predetermined algorithm based on said composite metric; and

directing said data transmission over said best path.

2. The method of claim 1 wherein said metric values include:

a) a topological delay time for a transmission over a path;

b) a path bandwidth equal to the narrowest bandwidth of one or more segments making up said path;

c) a reliability number corresponding to the reliability of the path; and

d) a channel occupancy obtained by measuring traffic along the path.

3. The method of claim 2 wherein said composite metric is determined by the algorithm (K₁ /B_e +K₂ D_c) * r where K₁ and K₂ are constants, B_e is a path effective bandwidth equal to said path bandwidth multiplied by (1-said channel occupancy), D_c is said topological delay and r is said reliability.

4. The method of claim 2 wherein said second algorithm is further based on a hop count that is incremented at each gateway along a path.

5. The method of claim 1 further comprising the steps of transmitting data, including said composite metric, for each identified data path to at least two gateways coupled to said gateway as an update message and storing data from update messages received.

6. The method of claim 3 further comprising the steps of:

a) examining a protocol header of a data transmission to determine what characteristics of said data transmission are described;

b) varying the values of said constants K₁ and K₂ in accordance with said described data transmission characteristics; and

c) maintaining separate sets of path information within said gateway for each combination of said described transmission characteristics.

7. The method of claim 6 further comprising the steps of merging said separate sets of path information into a single routing update transmission and eliminating duplicate information.

8. The method of claim 1 further comprising the step of modifying said first algorithm according to described data transmission characteristics associated with a data transmission.

9. The method of claim 1 further comprising the step of routing portions of said data transmission over multiple paths in alternation.

10. The method of claim 9 further comprising the step of computing the share of data to send over each of said multiple paths as inversely proportional to the composite metric of said path.

11. The method of claim 9 further comprising the step of maintaining a list of paths for each destination, with paths being maintained on the list when their composite metric is less than M×

V, where M is the minimum composite metric for the destination, and V is a predetermined variance.

12. The method of claim 9 further comprising the step of not sending data transmissions on a path where the composite metric for the destination is larger at a next gateway on said path than at a current gateway.

13. The method of claim 5 further comprising the step of deactivating a path when an update message indicates an increase in the metric of a predetermined kind.

14. The method of claim 5 further comprising the step of deactivating a path when an update message indicates an increase in hop count by more than 2.

15. The method of claim 5 further comprising the step of ceasing to accept update information about a destination for a predetermined time when the best composite metric for the destination has deteriorated by more than a predetermined amount.

16. The method of claim 5 further comprising the step of not sending information about a destination out the same interface from which said information was originally obtained.

17. 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.

18. 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.

19. The gateway of claim 18 wherein said metric values include:

a) a topological delay time for a transmission over a path;

b) a path bandwidth equal to the narrowest bandwidth of one or more segments making up said path;

c) a reliability number corresponding to the reliability of the path; and

d) a channel occupancy obtained by measuring traffic along the path.

20. The gateway of claim 19 wherein said composite metric is determined by the algorithm (K₁ /B_e +K₂ D_c) * r where K₁ and K₂ are constants, B_e is a path effective bandwidth equal to said path bandwidth multiplied by (1-said channel occupancy), D_c is said topological delay and r is said reliability.

21. The gateway of claim 19 wherein said second algorithm is further based on a hop count that is incremented at each gateway along a path.

22. The gateway of claim 18 further comprising means for transmitting the stored data, including said composite metric, for each identified data path to at least one gateway coupled to said gateway as an update message and means for storing data from update messages received.

23. The gateway of claim 20 further comprising:

a) means for examining a protocol header of a data transmission to determine what characteristics of said data transmission are described;

b) means for varying the values of said constants K₁ and K₂ in accordance with said described data transmission characteristics; and

c) means for maintaining separate sets of path information within said gateway for each combination of said described transmission characteristics.

24. The gateway of claim 18 further comprising means for modifying said first algorithm according to described data transmission characteristics associated with a data transmission.

25. The gateway of claim 23 further comprising means for merging said separate sets of path information into a single routing update transmission and means for eliminating duplicate information.

26. The gateway of claim 18 further comprising means for routing portions of said data transmission over multiple paths in alternation.

27. The gateway of claim 26 further comprising means for computing the share of data to send over each of said multiple paths as inversely proportional to the composite metric of said path.

28. The gateway of claim 26 further comprising means for maintaining a list of paths for each destination, with paths being maintained on the list when their composite metric is less than M×

V, where M is the minimum composite metric for the destination, and V is a predetermined variance.

29. The gateway of claim 26 further comprising means for not sending data transmissions on a path where the composite metric for the destination is larger at a next gateway on said path than at a current gateway.

30. The gateway of claim 22 further comprising means for deactivating a path when an update message indicates an increase in the metric of a predetermined kind.

31. The gateway of claim 22 further comprising means for deactivating a path when an update message indicates an increase in hop count by more than 2.

32. The gateway of claim 22 further comprising means for ceasing to accept update information about a destination for a predetermined time when the best composite metric for the destination has deteriorated by more than a predetermined amount.

33. The gateway of claim 22 further comprising means for not sending information about a destination out the same interface from which said information was originally obtained.

34. 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.

35. 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.

36. A method as in claim 35, wherein said plurality of routing data items comprises at least one of the group:

delay time, bandwidth, reliability, channel occupancy, and security.

37. A method as in claim 35, wherein said step of selecting comprises

computing a composite routing characteristic from said plurality of routing data items;

and

selecting at least one preferred path based on said composite routing characteristic.

38. A method as in claim 35, wherein said step of associating comprises

identifying at least one subpath of each said path;

associating each said subpath with a plurality of subpath routing data items, each of said subpath routing data items being representative of a routing characteristic of said subpath; and

computing said plurality of routing data items based on said plurality of subpath routing data items for each said subpath.

39. A method as in claim 38, wherein each said subpath comprises a hop.

40. A method as in claim 38, wherein said step of computing comprises computing a composite routing data item for each said subpath routing data item.

41. A method as in claim 38, wherein said step of computing comprises

for each said subpath routing data item, applying a function to said plurality of subpath routing data items for each said subpath.

42. A method as in claim 41, wherein said function comprises one of the group:

addition, minimum, and product, of a plurality of subpath routing data items.

43. A method as in claim 41, wherein said function comprises addition when said subpath routing data item is delay time, minimum when said subpath routing data item is bandwidth, and product when said subpath routing data item is reliability.

44. 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.

45. 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.

46. 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.

47. A method as in claim 46, wherein said step of determining comprises examining at least a part of said message.

48. A method as in claim 46, wherein said step of associating comprises computing a composite routing data item based on said at least one routing characteristic and based on said transmission type.

49. A method as in claim 46, wherein said step of associating comprises

associating a variable value with each routing characteristic of said path;

associating at least one coefficient value with said transmission type;

computing a composite routing characteristic based on a polynomial having said at least one coefficient value and at least one said variable value as material factors.

50. 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.

51. 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.

52. 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.

53. 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.

54. 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×

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.

55. 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.

56. 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.

57. A method as in claim 56, wherein said routing data item is a composite of at least two network data items.

58. A method as in claim 56, wherein said routing data item is a hop count and said tolerance is 2.

59. A method as in claim 56, comprising ceasing to accept update information about a destination for a predetermined time when the best composite metric for the destination has deteriorated by more than a predetermined amount.

60. A method as in claim 56, comprising transmitting an outgoing update message to at least one receiving node coupled to said node, wherein said receiving node is coupled to said node by means of an interface other than an interface from which said information was originally obtained.

61. 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.

62. 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.

63. 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.

64. 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.