Method and structure for autoconfiguration of network destinations

• US 7,580,370 B2
• Filed: 06/21/2002
• Issued: 08/25/2009
• Est. Priority Date: 06/21/2002
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Boivie, Richard H., Feldman, Nancy K.
• Primary Examiner(s): Mattis; Jason E
• Application Number:
  US10/176,045
• Publication Number:
  US 20030235155A1
• Time in Patent Office: 2,622 Days
• Field of Search: 370/254, 370/255, 370/401
• US Class Current: 370/255
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/26 Route discovery packet
• CPC Class Codes: H04L 45/46 Cluster building
• CPC Class Codes: H04L 45/64 using an overlay routing layer

Abstract

A method (and structure) for determining an optimal routing of data packets to subnet addresses in a network including a plurality of routers interrelated by a defined neighborhood relationship, includes, responsive to learning of a presence of a subnet, determining a distance between the subnet and each router.

Claims

1. A method of determining an optimal subnet data-packet-routing in an overlay network comprising a plurality of routers interrelated by a defined neighborhood relationship, by automatically determining an optimal router from said plurality of routers to serve as a local router that will communicate directly to said subnet, said method comprising:

responsive to learning of a presence of a subnet not previously recognized by said overlay network, determining a distance between said subnet and each router in said plurality of routers; and

determining a router having a smallest distance to said subnet to serve as the local router for said subnet for purpose of said overlay network.

2. The method of claim 1, further comprising:

determining, for each said router in said overlay network, an optimal routing procedure to use when said router receives a data packet addressed to said subnet, said optimal routing procedure defining whether each said router should forward said data packet directly to said subnet or to a neighboring router.

3. The method of claim 2, further comprising:

for each router in said overlay network having more than one neighboring router, determining a specific one of said neighboring routers to forward said data packets addressed to said subnet, if said optimal routing procedure for data packets to said subnet comprises forwarding said data packets to a neighboring router.

4. The method of claim 1, further comprising:

in a first router of said overlay network, responsive to learning of a presence of said subnet, communicating with said subnet to allow said first router to measure a distance D₀ between said first router and said subnet; and

transmitting distance D₀ to each router R_i (where i is an integer equal to or greater than one) defined as being a neighbor of said first router.

5. The method of claim 4, further comprising:

in each neighbor router R_i, communicating with said subnet to allow each router R_i to measure a respective distance D_i to said subnet.

6. The method of claim 5, wherein an optimal routing procedure for said first router comprises:

sending said data packets from said first router directly to said subnet, if said distance D₀ is smallest of all said distances D_i; and

sending said data packets from said first router to whichever neighboring router D_i has the smallest distance D_i, if said distance D₀ is not smallest of all said distances D_i .

7. The method of claim 6, further comprising:

designating said first router to be a local router for said subnet if said distance D₀ is smallest of all said distances D_i.

8. The method of claim 6, wherein each said neighboring router R_i transmits its said respective distance D_i to said first router and a determination of an optimal routing for said first router to said subnet occurs in said first router.

9. The method of claim 4, wherein said distance D₀ is determined by pinging to said subnet to determine a time interval.

10. The method of claim 4, further comprising:

periodically repeating said communicating to determine whether said optimal routing should be revised.

11. The method of claim 1, wherein each said router of said overlay network, responsive to learning of said subnet in any manner, determines a distance between itself and said subnet, and each said router determines its own optimal routing to said subnet as based on comparing its distance from said subnet with distances of any neighboring routers from said subnet.

12. A computer for determining an optimal routing of data packets to subnets in an overlay network by automatically determining whether it should itself serve as a local router to communicate directly to a subnet, said overlay network comprising a plurality of routers organized by a relationship defining how said plurality of routers are related as neighboring routers, said computer comprising:

an awareness module for learning of a presence of a subnet not previously recognized by said overlay network;

a receiver to receive data packets addressed to said subnet and transmissions from any neighboring router of said overlay network;

a transmitter for communicating with said subnet and with any neighboring router of said overlay network;

a timing detector for determining from said communication a time interval corresponding to a distance to said subnet; and

a calculator for using said time interval to determine an optimal routing procedure to use whenever receiving a data packet addressed to said subnet, said optimal routing procedure defining whether to transmit said data packet directly to said subnet or to transmit said data packet to a neighboring router of said overlay network, an optimal routing determined by comparing said distance to said subnet with a distance to said subnet as reported by each neighboring router.

13. The computer of claim 12, further comprising:

a timer such that said communication with said subnet is periodically repeated to determine a current distance to said subnet.