Apparatus and method for selecting improved routing paths in an autonomous system of computer networks

• US 5,754,790 A
• Filed: 05/01/1996
• Issued: 05/19/1998
• Est. Priority Date: 05/01/1996
• Status: Expired due to Term

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: 3Com Corporation (HP Inc.)
• Inventors: France, Robert Millard, Husak, David J.
• Primary Examiner(s): Eng, David Y.
• Application Number:
  US08/641,506
• Time in Patent Office: 748 Days
• Field of Search: 395/200.15, 395/200.16, 395/200.17, 395/200.18, 395/200.2
• US Class Current: 709/238
• CPC Class Codes: H04L 2012/5615 Network termination, e.g. NT1, NT2, PBX
• CPC Class Codes: H04L 2012/5619 Network Node Interface, e.g. tandem connections, transit switching
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/033 by updating distance vector protocols
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04Q 11/0478 Provisions for broadband connections

Abstract

An apparatus and method for selecting improved routing paths in an autonomous system having at least two computer networks while retaining the benefits of Routing Information Protocol (RIP) are disclosed. Such an apparatus and method are realized by having network bridges identify and, in certain circumstances, modify RIP update messages according to information retrieved from a routing database, or table, of an associated network router. More particularly, the network bridges modify RIP messages so that they will more accurately reflect the position of the network router that broadcast the RIP message, relative to the position of the associated network router, with respect any given destination network.

Claims

1. A method for modifying update messages in a computer network system having at least two computer networks, said method comprising the steps of:

receiving an update message from an origination routing network element at an update message forwarding network element, said update message comprising a destination network address and a first integer value representing a distance between said origination routing network element and said destination network address, said update message forwarding network element having access to routing information of an associated routing network element, said routing information comprising said destination network address and a second integer value representing a distance between said associated routing network element and said destination network address, said first integer value distance being measured by a first number of routing network elements located along a first route from said origination routing network element to said destination network address, said second integer value distance being measured by a second number of routing network elements located along a second route from said associated routing network element to said destination network address;

comparing said first integer value distance with said second integer value distance; and

if said first number of routing network elements is equal to said second number of routing network elements, modifying said update message by increasing the integer value of said first integer value distance to an integer value that is greater than said second number of routing network elements.

2. The method as defined in claim 1, further comprising the steps of:

determining if said update message comprises any further destination network addresses and any further integer value distances between said origination routing network element and said further destination network addresses;

if said update message comprises any further destination network addresses and any further integer value distances between said origination routing network element and said further destination network addresses, comparing said further integer value distances with corresponding integer value distances between said associated routing network element and said further destination network addresses, wherein said further integer value distances are measured by first numbers of routing network elements located along first routes from said origination routing network element to said further destination network addresses, and wherein said corresponding integer value distances are measured by corresponding second numbers of routing network elements located along second routes from said associated routing network element to said further destination network addresses; and

if said first numbers of routing network elements are equal to said corresponding second numbers of routing network elements, modifying said update message by increasing the integer values of said further integer value distances to an integer value that is greater than said corresponding second numbers of routing network elements.

3. The method as defined in claim 2, further comprising the step of:

if said update message does not comprise any further destination network addresses and any further integer value distances between said origination routing network element and said further destination network addresses, forwarding said update message to other network elements.

4. A method for modifying update messages in a computer network system having at least two computer networks, said method comprising the steps of:

receiving an update message from an origination routing network element at an update message forwarding network element, said update message comprising a destination network address and a first integer value representing a distance between said origination routing network element and said destination network address, said update message forwarding network element having access to routing information of an associated routing network element, said routing information comprising said destination network address and a second integer value representing a distance between said associated routing network element and said destination network address, said first integer value distance and said second integer value distance being measured by a first number of routing network elements and a second number of routing network elements situated between said origination routing network element and said associated routing network element, respectively, and said destination network address;

comparing said first integer value distance with said second integer value distance; and

if said first number of routing network elements, modifying said update message by increasing the integer value of said first integer value distance to an integer value that is greater than said second number of routing network elements.

5. The method as defined in claim 4, further comprising the steps of:

determining if said update message comprises any further destination network addresses and any further integer value distances between said origination routing network element and said further destination network addresses;

if said update message comprises any further destination network addresses and any further integer value distances between said origination routing network element and said further destination network addresses, comparing said further integer value distances with corresponding integer value distances between said associated routing network element and said further destination network addresses, wherein said further integer value distances are measured by first numbers of routing network elements situated between said origination routing network element and said further destination network addresses, and wherein said corresponding integer value distances are measured by corresponding second numbers of routing network elements situated between said associated routing network element and said further destination network addresses; and

if said first numbers of routing network elements are equal to said corresponding second numbers of routing network elements, modifying said update message by increasing the integer values of said further integer value distances to integer values that are greater than said corresponding second numbers of routing network elements.

6. The method as defined in claim 5, further comprising the step of:

if said update message does not comprise any further destination network addresses and any further integer value distances between said origination routing network element and said further destination network addresses, forwarding said update message to other network elements.

7. A method for modifying update messages in a computer network system having at least two computer networks, said method comprising the steps of:

receiving an update message from an origination routing network element at an update message forwarding network element, said update message comprising a destination network address and a first integer value representing a distance between said origination routing network element and said destination network address, said update message forwarding network element having access to routing information of an associated routing network element, said routing information comprising said destination network address and a second integer value representing a distance between said associated routing network element and said destination network address, said first integer value distance and said second integer value distance being measured by numbers of routing network elements situated between said origination routing network element and said associated routing network element, respectively, and said destination network address;

comparing said first integer value distance with said second integer value distance; and

if said first integer value distance is equal to said second integer value distance, modifying said update message by increasing the integer value of said first integer value distance to an integer value that is greater than the integer value of said second integer value distance.

8. The method as defined in claim 7, further comprising the steps of:

determining if said update message comprises any further destination network addresses and any further integer value distances between said origination routing network element and said further destination network addresses;

if said update message comprises any further destination network addresses and any further integer value distances between said origination routing network element and said further destination network addresses, comparing said further integer value distances with corresponding integer value distances between said associated routing network element and said further destination network addresses, wherein said further integer value distances and said corresponding integer value distances are measured by numbers of routing network elements situated between said origination routing network element and said associated routing network element, respectively, and said further destination network addresses; and

if said further integer value distances are equal to said corresponding integer value distances, modifying said update message by increasing the integer values of said further integer value distances to integer values that are greater than the integer values of said corresponding integer value distances.

9. The method as defined in claim 8, further comprising the step of:

if said update message does not comprise any further destination network addresses and any further integer value distances between said origination routing network element and said further destination network addresses, forwarding said update message to other network elements.

10. An apparatus for modifying update messages in a computer network system having at least two computer networks, said apparatus comprising:

a first circuit for receiving an update message from an origination routing network element, said update message comprising a destination network address and a first integer value representing a distance between said origination routing network element and said destination network address, said first circuit having access to routing information of an associated routing network element, said routing information comprising said destination network address and a second integer value representing a distance between said associated routing network element and said destination network address, said first integer value distance being measured by a first number of routing network elements located along a first route from said origination routing network element to said destination network address, said second integer value distance being measured by a second number of routing network elements located along a second route from said associated routing network element to said destination network address;

a second circuit for comparing said first integer value distance with said second integer value distance; and

a third circuit for modifying said update message by increasing the integer value of said first integer value distance to an integer value that is greater than said second number of routing network elements if said first number of routing network elements is equal to said second number of routing network elements.

11. The apparatus as defined in claim 10, further comprising a fourth circuit for determining if said update message comprises any further destination network addresses and any further integer value distances between said origination routing network element and said further destination network addresses.

12. The apparatus as defined in claim 11, further comprising a fifth circuit for forwarding said update message to other network elements if said update message does not comprise any further destination network addresses and any further integer value distances between said origination routing network element and said further destination network addresses.

13. An apparatus for modifying update messages in a computer network system having at least two computer networks, said apparatus comprising:

a first circuit for receiving an update message from an origination routing network element, said update message comprising a destination network address and a first integer value representing a distance between said origination routing network element and said destination network address, said first circuit having access to routing information of an associated routing network element, said routing information comprising said destination network address and a second integer value representing a distance between said associated routing network element and said destination network address, said first integer value distance and said second integer value distance being measured by a first number of routing network elements and a second number of routing network elements situated between said origination routing network element and said associated routing network element, respectively, and said destination network address;

a second circuit for comparing said first integer value distance with said second integer value distance; and

a third circuit for modifying said update message by increasing the integer value of said first integer value distance to an integer value that is greater than said second number of routing network elements if said first number of routing network elements is equal to said second number of routing network elements.

14. The apparatus as defined in claim 13, further comprising a fourth circuit for determining if said update message comprises any further destination network addresses and any further integer value distances between said origination routing network element and said further destination network addresses.

15. The apparatus as defined in claim 14, further comprising a fifth circuit for forwarding said update message to other network elements if said update message does not comprise any further destination network addresses and any further integer value distances between said origination routing network element and said further destination network addresses.

16. An apparatus for modifying update messages in a computer network system having at least two computer networks, said apparatus comprising:

a first circuit for receiving an update message from an origination routing network element, said update message comprising a destination network address and a first integer value representing a distance between said origination routing network element and said destination network address, said first circuit having access to routing information of an associated routing network element, said routing information comprising said destination network address and a second integer value representing a distance between said associated routing network element and said destination network address, said first integer value distance and said second integer value distance being measured by numbers of routing network elements situated between said origination routing network element and said associated routing network element, respectively, and said destination network address;

a second circuit for comparing said first integer value distance with said second integer value distance; and

a third circuit for modifying said update message by increasing the integer value of said first integer value distance to an integer value that is greater than the integer value of said second integer value distance.

17. The apparatus as defined in claim 16, further comprising a fourth circuit for determining if said update message comprises any further destination network addresses and any further integer value distances between said origination routing network element and said further destination network addresses.

18. The apparatus as defined in claim 17, further comprising a fifth circuit for forwarding said update message to other network elements if said update message does not comprise any further destination network addresses and any further integer value distances between said origination routing network element and said further destination network addresses.

19. A method for modifying update messages in a computer network system having at least two computer networks, said method comprising the step of modifying an update message from an origination routing network element at an update message forwarding network element, said update message comprising a destination network address and a first integer value representing a distance between said origination routing network element and said destination network address, said update message forwarding network element having access to routing information of an associated routing network element, said routing information comprising said destination network address and a second integer value representing a distance between said associated routing network element and said destination network address, said step of modifying comprising increasing the integer value of said first integer value distance over the integer value of said second integer value distance so as to more accurately reflect the position of said origination routing network element, relative to the position of said associated routing network element, with respect to said destination network address.

20. An apparatus for modifying update messages in a computer network system having at least two computer networks, said apparatus comprising a circuit for modifying an update message from an origination routing network element at an update message forwarding network element, said update message comprising a destination network address and a first integer value representing a distance between said origination routing network element and said destination network address, said update message forwarding network element having access to routing information of an associated routing network element, said routing information comprising said destination network address and a second integer value representing a distance between said associated routing network element and said destination network address, said circuit modifying said update message by increasing the integer value of said first integer value distance over the integer value of said second integer value distance so as to more accurately reflect the position of said origination routing network element, relative to the position of said associated routing network element, with respect to said destination network address.

21. A method for modifying update messages in a computer network system having:

an update message forwarding network element;

an origination routing network element for transmitting an update message to said update message forwarding network element;

a routing network element associated with said update message forwarding network element;

wherein said update message comprises a destination network address and a first integer value representing a distance between said origination routing network element and said destination network address, said update message forwarding network element having access to routing information of said associated routing network element, said routing information comprising said destination network address and a second integer value representing a distance between said associated routing network element and said destination network address, said method comprising the step of;

modifying the integer value of said first integer value distance based upon a comparison of said first integer value distance with said second integer value distance.

22. The method of claim 21, wherein said first integer value distance and said second integer value distance are measured by a first number of routing network elements and a second number of routing network elements situated between said origination routing network element and said associated routing network element, respectively, and said destination network address.

23. The method of claim 22, wherein said modifying step includes the step of increasing said first integer value distance if the integer value of said first integer value distance is equal to the integer value of said second integer value distance.