Multiplex communications – Diagnostic testing – Determination of communication parameters
Reexamination Certificate
1998-07-06
2001-05-08
Vu, Huy D. (Department: 2663)
Multiplex communications
Diagnostic testing
Determination of communication parameters
C370S252000, C370S400000, C370S254000
Reexamination Certificate
active
06229791
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to partitioning of a partially switched local area network (LAN) and more particularly to using a Tabu Search methodology to find optimal switch configurations.
BACKGROUND OF THE INVENTION
Local area networks (hereinafter “LANs”), as typified by Ethernet networks in accordance with IEEE Standard 802.3, share a fixed amount of bandwidth between multiple host workstations. When the demands of the hosts reach or exceed the capacity of the LAN, throughput decreases and packet delay increases. In order to improve performance, the LAN can be partitioned into a partially switched network using IEEE 802.1d compliant LAN switches. By utilizing such switches, the host workstations can be distributed among multiple switch-connected LAN segments of varying size, so as to minimize and balance the segments. However, determining how to partition, or segment, a LAN and estimating the performance improvements to be realized by a given partitioning scheme are challenging problems.
Different partitioning approaches have utilized various network characteristics in determining how to partition. For example, in the research paper entitled “Topological Design of Local-Area Networks Using Genetic Algorithms” by R. Elbaum and M. Sidi,
Proceedings of IEEE INFOCOM
'95, pp. 64-71 (1995), Genetic and Simulated Annealing algorithms are employed for solving network partitioning problems. The Elbaum approach segments the network into clusters using bridges and represents the traffic on the LAN segments and bridges to determine the total network delay based on the traffic in the different parts of the network. The Elbaum approach does not, however, allow for biasing or balancing of delay. Moreover, because it uses bridges to segment the network, it allows multiple bridges to attach to a segment, and only two segments to attach to a bridge.
Another approach, found in “Analyser, A Genetic Algorithm Based Network Divider” by C. Farrell, et al, http://www.cs.curtin.edu.au/~netman/analyser.html (1994), uses Simulated Annealing for separating the workstations in an existing network into two segments using a so-called “generic network connecting device.” The approach concentrates on maximizing and balancing intra-segment traffic, but does not consider multiple segments or characteristics of the segments, such as capacity, nor does it consider characteristics of the partitioning device, such as switch delay.
Yet another approach, outlined by M. Songerwala in “Efficient Solutions to the Network Division Problem”, http://www.cs.curtin.edu.au/~netman/analyser.html (1995), and which employs the Genetic algorithm, also fails to consider multiple segments, characteristics of the segment, such as capacity, and characteristics of the partitioning device, such as switch delay.
A more detailed discussion of the prior art, and of the algorithms used therein, can be found in the Master's Thesis of Mark R. Nusekabel, dated July 7, 1997, entitled “Switched Network Partitioning Using Tabu Search,”
University of South Florida
, the teachings of which are herein incorporated by reference.
What is needed, therefore, and what is an objective of the present invention, is to provide a system and method for determining optimal partitioning in a partially-switched LAN, which function takes into consideration both inter-segment and intra- segment traffic and characteristics, including attempting to minimize as well as balance the mean delay for the LAN segments, switch characteristics, including switch delay, and the number of workstations per segment.
SUMMARY OF THE INVENTION
The present invention achieves the foregoing and other objectives by approaching the LAN as a tree structure for partitioning. Each of the components (i.e., switches, LAN segments, and workstations) is treated as a node for placement in a tree structure topology, with one switch at the top of the tree. Each switch may have other switches or LAN segments connected to it, with each LAN segment having a plurality of workstations attached to it. The workstations are the leaf nodes of the tree and cannot have anything connected to them. The inventive method for determining optimal partitioning is to calculate the mean switch delay, the mean segment delay, and the standard deviation as a function of the total number of workstations in the network, and to sum the values together. Finally, the invention applies a Tabu Search to the potential tree-structured solutions to the problem in order to rapidly and accurately determine the optimal network configuration.
REFERENCES:
patent: 5598532 (1997-01-01), Liron
patent: 6026095 (2000-02-01), Sherer et al.
patent: 6049720 (2000-04-01), Rude
Christensen Kenneth Jussi
Nusekabel Mark R.
Strayer Heidi
Crockatt JoAnn K.
Dougherty Anne Vachon
International Business Machines - Corporation
Nguyen Danny
Vu Huy D.
LandOfFree
Method and system for providing partitioning of partially... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and system for providing partitioning of partially..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for providing partitioning of partially... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2476619