Distributed processing of route selection across networks and subnetworks

• US 5,398,012 A
• Filed: 11/24/1992
• Issued: 03/14/1995
• Est. Priority Date: 11/24/1992
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Vu, Ken V., Dykeman, Douglas H., Sandick, Haldon J., Derby, Jeffrey H., Drake, John E. Jr., Doeringer, Willibald A.
• Primary Examiner(s): Horabik, Michael
• Application Number:
  US07/980,854
• Time in Patent Office: 840 Days
• Field of Search: 340/825.03, 340/826, 340/827, 370/54, 379/220, 379/221
• US Class Current: 370/238
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/44 Distributed routing

Abstract

The process for determining the best communication route from a source end station to a destination end station is distributed over both source and destination network nodes. Network nodes, at the interface between a wide area network (WAN) and each subnetwork, contain access agents to control the communication flow between the wide area network and an end station in the subnetwork. The task of selecting the best route between two end stations is distributed between the access agents at the WAN interface in the first subnetwork, and the access agents at the WAN interface in the second subnetwork. Each access agent at one WAN interface obtains the best route from itself to the end station in its subnetwork. Each access agent at the other WAN interface finds the best route from each access agent at the first WAN interface through itself to the end station in its subnetwork. One designated access agent collects all the best route information. This best route information is concatenated, and the route with the least weight is selected as the best route between end stations.

Claims

1. A selection apparatus for use in a communication network having a Wide Area Network (WAN) and a plurality of subnetworks, an interface between the WAN and each subnetwork, and having one or more access agents at each interface, said selection apparatus for selecting the best route between a first end station in a first subnetwork and a second end station in a second subnetwork, said selection apparatus comprising:

a plurality of first access agent means in the first subnetwork for routing communication flow between a first end station and the wide area network, and for finding first, best-route information from each first access agent means to the first end station;

a plurality of second access agent means in a second subnetwork for routing communication flow between the second end station and the wide area network, and for finding second, best-route information from each second access agent means to the second end station, and for finding WAN, best-route information between each of said first access agent means and each of said second access agent means; and

selecting access agent means responsive to each of said first and second access agent means for selecting the best route from the first end station to the second end station based on the first, best-route information from said first access agent means, the WAN, best-route information from the second access agent means, and the second, best-route information from said second access agents means.

2. The apparatus of claim 1 and additionally comprising:

first means for distributing to each first access agent means the task of finding the first best-route from the first end station through the first subnetwork; and

second means for distributing to each second access agent means the task of finding the best WAN route between each of said first and second access agent means, and the best route from the second end station through the second subnetwork.

3. The apparatus of claim 2 wherein said first distributing means comprises:

means in the first end station for broadcasting to each first access means a request for communication with the second end station.

4. The apparatus of claim 3 wherein said second distributing means comprises:

means in said selecting access agent means for broadcasting to each second access means a request for best route information to the second end station.

5. The apparatus of claim 2 wherein said first and second distributing means comprises:

said selecting access agent means querying each of said first and second access agent means for best route information.

6. The apparatus of claim 1 wherein each of said second access agent means comprises:

means for finding the second, best-route information from each second access agent means to the second end station;

means for finding the WAN, best-route information between each of said first access agent means and each of said second access agent means; and

means for concatenating the second, best-route information with the WAN, best-route information to obtain combined WAN and second, best-route information from each of said first access agent means through each of said second access agent means to said second end station.

7. The apparatus of claim 6 wherein said selecting access agent means comprises:

means responsive to each of said first access agent means for receiving the first best-route information from the first end station to each of said first access means;

means responsive to each of said second access agent means for receiving the combined best-route information from the second end station to each of said first access agent means; and

means for concatenating the first best-route information with the combined best-route information to obtain best-route information from said first end station to said second end station.

8. A method for selecting a best communication route from a source end station to a destination end station through a communication network having a Wide Area Network (WAN) and subnetworks attached to the wide Area Network, an interface between the WAN and each subnetwork, and each subnetwork containing one or more end stations, said communication network having one or more access agents at the interface between the WAN and each subnetwork, said method comprising the steps of:

finding a best source route from each source access agent to the source end station;

finding a best destination route from each destination access agent to the destination end station;

finding a best WAN route from each source access agent to each destination access agent;

first, concatenating the best WAN route with either the best source route, or the best destination route for each access agent thereby producing a best combined route from each of the access agents at the source, or destination end, to the end station at the other end; and

second, concatenating the best combined route with either the best source route or the best destination route based on the route not having been concatenated by said first concatenating step whereby the best route from the source end station to the destination end station is selected.

9. The method of claim 8 wherein said first and second concatenating steps comprise, respectively:

first, concatenating the best WAN route with the best destination route for each access agent, thereby producing the best combined route from each of the source access agents through each destination access agent to the destination end station; and

second, concatenating the best combined route with the best source route to select the best route from the source end station to the destination end station.

10. The method of claim 9 wherein one of said source access agents is designated as paired with the source end station and thereby becomes a designated source access agent, and wherein said best source route finding step comprises the steps of:

querying by the designated source access agent to the other source access agents for the best route from each source access agent to the source end station;

obtaining thereafter at each source access agent the best route from the source access agent to the source end station; and

notifying the designated source access agent of the best route from each source access agent to the source end station.

11. The method of claim 10 wherein said best destination route finding step comprises the steps of:

sending a find message from the designated source access agent to each of the destination access agents; and

obtaining, in response to the find message, the best route from each destination access agent to the destination end station.

12. The method of claim 11 wherein said first concatenating step comprises:

concatenating at each of the destination access agents the best WAN route from each source access agent to the destination access agent and the best destination route from the access agent to the destination end station, thereby producing the best combined route from each of the source access agents through each destination access agent to the destination end station; and

sending a found message from each of the destination access agents to the designated source access agent, said found message containing the best route from each source access agent to the destination end station through the destination access agent sending the found message.

13. The method of claim 9 wherein one of said source access agents is designated as paired with the source end station and thereby becomes a designated source agent, and wherein said best source route finding step comprises the steps of:

broadcasting a communication request from the source end station to each of the source access agents;

obtaining, in response to the communication request, the best route from each source access agent to the source end station; and

notifying the designated source access agent of the best route from each source access agent to the source end station.

14. The method of claim 13 wherein said best destination route finding step comprises the steps of:

broadcasting a find message from the designated source access agent to each of the destination access agents;

broadcasting, in response to the find message, the communication request from each destination access agent to the destination end station;

sending a communication request response from the destination end station to each destination access agent; and

obtaining from the communication request responses the best destination route from the destination end station to each destination access agent.

15. The method of claim 14 wherein said first concatenating step comprises:

concatenating, at each of the destination access agents, the best WAN route from each source access agent to the destination access agent and the best destination route from the destination access agent to the destination end station, thereby producing the best combined route from each of the source access agents through each destination access agent to the destination end station; and

sending a found message from each destination access agent to the designated source access agent, said found message containing the best route from each source access agent to the destination end station through the destination access agent sending the found message.