Method and apparatus for optimizing computer networks

• US 5,598,532 A
• Filed: 10/21/1993
• Issued: 01/28/1997
• Est. Priority Date: 10/21/1993
• Status: Expired due to Term

• Current Assignee: All Optical Networks, Inc.
• Original Assignee: All Optical Networks, Inc.
• Inventors: Liron, Moshe
• Primary Examiner(s): An, Meng-Ai T.
• Assistant Examiner(s): DAVIS JR, WALTER D
• Application Number:
  US08/141,180
• Time in Patent Office: 1,195 Days
• Field of Search: 395/800, 395/200, 370/94.1, 364/DIG. 1, 364/490
• US Class Current: 703/2
• CPC Class Codes: H04L 41/0826 for reduction of network costs H04L41/0833 takes precedence
• CPC Class Codes: H04L 41/0853 by actively collecting configuration information or by backing up configuration information
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04L 41/145 involving simulating, designing, planning or modelling of a network
• CPC Class Codes: H04L 41/16 using machine learning or artificial intelligence

Abstract

An optimization method collects data regarding network topology and traffic flow and creates a network model. The model is analyzed using optimization rules and network performance objectives to determine the optimal configuration of the network according to the network performance objectives. An optimization rule for positioning a shared central resource on the network identifies the communication paths between all clients of the resource and assigns a cost value to the traffic flowing between the clients and the resource. This is repeated for each potential resource position in the network. The position having the lowest traffic cost is the optimal position for the resource. An optimization rule for partitioning network segments determines all possible partitions at the hubs of a segment and scores the performance of each possible partition, according to network performance goals. The hub partition having the lowest score is the optimal hub for partitioning the network segment.

Claims

1. For a network including a plurality of interconnected network segments forming a network configuration, each network segment having at least one node, the network having at least one shared central resource interconnected in a network segment, a computer implemented method of optimizing the network configuration, comprising the computer executed steps of:

creating a network model of network traffic flow and network topology;

receiving an input specifying at least one network performance goal;

selecting at least one optimization rule as a function of the specified at least one network performance goal;

comprising,

optimizing the network configuration by determining an optimal network traffic flow using the selected at least one optimization rule by;

identifying at least one switching element on the network;

selecting a shared central resource;

identifying all clients on the network communicating with the shared central resource;

for each switching element, determining from the network model a network traffic flow between the shared central resource as positioned at the switching element and all clients communicating with the shared central resource;

determining a traffic cost for each network traffic flow according to the network performance goal; and

comparing said traffic costs to determine the switching element having a lowest traffic cost.

2. The method of claim 1 wherein the step of determining a traffic cost for each network traffic flow, further comprises the step of:

determining a hop cost for the network traffic flow.

3. The method claim 2 wherein the hop cost is a function of the network performance goal.

4. The method of claim 2 wherein the hop cost is a function of a delay between a client and the shared central resource.

5. The method of claim 2 wherein the hop cost is a function of the number of switching elements between a client and the shared central resource.

6. The method of claim 2 wherein the hop cost is determined from a hop cost table.

7. The method of claim 2 wherein the step of determining a hop cost for the network traffic flow, further comprises the steps of:

identifying a communication path between a client and the shared central resource; and

determining a hop cost for network traffic flow along the communication path.

8. The method of claim 7 wherein the step of identifying a communication path, further comprises the steps of:

identifying a communication path from a client to the shared central resource; and

identifying a communication path from the shared central resource to a client.

9. The method of claim 1 wherein the step of determining a traffic cost for each network traffic flow, further comprises the steps of:

determining for each client a total bidirectional hop cost for communication between the client and the shared central resource; and

summing the total bidirectional hop costs to produce a network traffic cost for a switching element.

10. For a network including a plurality of interconnected network segments forming a network configuration, each network segment having at least one node, the network having at least one shared central resource interconnected to a network segment, the network segment including a hub tree structure having at least one parent hub coupled to at least one child hub, a computer implemented method of optimizing the network configuration, comprising the computer executed steps of:

creating a network model of network traffic flow and network topology;

receiving an input specifying at least one network performance goal;

selecting at least one optimization rule as a function of the specified at least one network performance goal; and

,

optimizing the network configuration, using the selected at least one optimization rule to position a switching element at an optimal position between two coupled hubs by;

partitioning a network segment between a child hub and its parent hub, creating a partition including the child hub and a partition including the parent hub;

scoring each partition of the child hub according to the network traffic flow of the partitions of the child hub, and associating the scores of the partitions with the child hub as a score for the child hub;

repeating the steps of partitioning and scoring for each child hub of the network segment; and

selecting the child hub having a lowest score for positioning the switching element between the child hub and its parent hub.

11. The method of claim 10 wherein the step of scoring each child hub, further comprises the steps of:

determining an intrapartition network traffic flow for the child hub;

determining an interpartition network traffic flow for the child hub;

combining the interpartition and intrapartition network traffic flows; and

scoring the combined network traffic flows.

12. The method of claim 11 wherein the step of determining an interpartition network traffic flow, further comprises the steps of:

determining a first network traffic flow from a first partition to a second partition;

determining a second network traffic flow from the second partition to the first partition; and

summing the first and second network traffic flows.

13. The method of claim 11 wherein the step of scoring the combined network traffic flows further comprises the step of:

computing a scoring function f(A, B, C), where A is the network traffic flow within a first partition plus the network traffic flow from a second partition to the first partition, where B is the network traffic flow within a first partition plus the network traffic flow from the first partition to the second partition, and C is the interpartition network traffic flow.

14. The method of claim 11 wherein the step of scoring the combined network traffic flows further comprises the step of:

computing a function of an average byte delay during a data transmission between a source hub and a destination hub.

15. The method of claim 10 wherein step of scoring the network traffic flow minimizes a maximum network traffic flow of the partitions.

16. The method of claim 10 wherein the step of scoring the network traffic flow minimizes a mean network traffic flow of the partitions.

17. A computer implemented method for optimizing a position of a switching element in a network segment of a network having at least a parent hub coupled to at least one child hub comprising the steps of:

simulating a partitioning of the network segment between a child hub and its parent hub to produce two partitions coupled across a hub;

scoring the child hub according to a network traffic flow of the partitions of the child hub by;

determining an intrapartition network traffic flow for the child hub;

determining an interpartition network traffic flow for the child hub;

combining the interpartition and intrapartition network traffic flows;

scoring the combined network traffic flows;

repeating the steps of simulating and scoring for each child hub;

selecting the child hub having a lowest score; and

,

configuring the network by partitioning the network segment at the selected child hub and placing the switching element between the child hub and its parent hub.