 |
Description  |
|
|
BACKGROUND OF THE INVENTION
1. Field of Invention
The present invention relates generally to the management of computer
networks and more particularly, to methods and apparatuses for improving
network performance through the configuration of network resources.
2. Description of Related Art
A computer network is a collection of autonomous computers interconnected
via a communications system. The network permits the computers to share
central hardware or software resources such as a particular computer, a
set of particular software applications or data files such as a database,
or a set of peripheral devices, including disk drives, printers, CD-ROM
drives, modems, and the like. A shared central computer providing data
files or applications is known as a "server"; the computers or network
devices (printers, disk drives, modems, etc.) communicating with the
server are known as "nodes". Where a node is computer running multiple
application programs, the individual application programs are "clients" of
the server. This is because each application program can communicate with
the server using a different network level protocol, as further described
below.
Networks are often comprised of "subnets" connected together. Typically,
subnets are collections of Local area network (LAN) segments residing
within a single physical structure, such as an office building. Within a
LAN segment, a number of nodes are connected to a hub, and the hub is
connected to other hubs to form the segment. Communication between LAN
segments is accomplished with switching elements such as routers, bridges,
LAN switches, and gateways. A wide area network (WAN) interconnects
remotely located subnets.
The "topology" of a network is the physical and logical organization of
devices on the network. The topology of the network can be generally
described as rings (closed looped arrangements of nodes), buses (linear
arrangements of nodes), stars (nodes radially connected), or a general
mesh structure having no particular geometry.
The communication between devices on a network is governed by a collection
of network protocols. Each protocol is a set of rules for communication
that defines the pattern or format of data transmitted on the network, and
the procedure for such transfers. Low level, or access, protocols allow
network devices to connect to each other and communicate with higher level
protocols. High level protocols allow the interconnection of heterogeneous
subnets comprised of differing device platforms (personal computers,
mainframes, or minicomputers), and access protocols.
Given the variety of topologies, protocols, and devices that can comprise a
network, there are two fundamental problems in configuring networks.
First, for existing networks, there is a need to optimize the
configuration of network devices and topologies using actual measured
performance data. Optimization is required to position shared central
resources, such as server, according to its usage by the network's nodes.
More particularly, the optimization question considers where in the
network to position the shared central resource given:
1. The identity of the shared central resource and its clients;
2. How each client is attached to the network;
3. The amount of traffic flowing between each client and the shared central
resource;
4. The network topological structure;
5. The network protocols used by the clients in communicating with the
shared central resource; and
6. A set of network performance objectives to use in seeking the optimal
shared central resource position, for example, minimum average
communication delay or minimum hops between the clients and the shared
central resource.
Similarly, optimization is needed to identify the best configuration of
segments in a given area of a network in light of network traffic flow.
More specifically, it is often necessary to configure the positioning of
hubs within a LAN segment to improve traffic flow. The traffic flow within
a network segment is generally related to the type of work done by users
of the network, where users accessing common resources or files form
logical, though often not physical, work groups. Accordingly, it is
desirable to optimize the configuration of network segments to better
balance the traffic flow requirements between such logical groups.
Further, segment optimization becomes particularly significant because of
the high labor cost associated with re-wiring an already existing wiring
plan. In metropolitan areas such as New York city the labor cost component
accounts for well over 50% of the total LAN investment. In partitioning a
network segment, it is thus desirable to preserve the existing hubs, hub
locations, hub to hub wiring plans, and node to hub wiring (to avoid for
example the need for running new wires from a station on the 50-th floor
to a hub on the 1-st floor). This is because rewiring may require shutting
all use of network segment for many hours or even days (in a high rise
office building). In addition, because network managers generally have
various network performance objectives, in these circumstances there also
is a need to optimize the network to meet these performance objectives.
Currently, network managers are limited to tools that can measure and
collect performance data, such as internodal traffic, communication cycle
times, error rates, segment utilization, and the like. These tools can
analyze the data to determine network performance according to a number of
performance parameters. In addition, other tools address the
interconnection of network routers to minimize link usage costs. In either
case, it remains up to the network manager, using personal knowledge and
experience, to decide how to configure the network in light of the
performance data to meet general performance objectives such as least
delay. This process is generally one of trial and error, and typically
leads to wrong solutions, resulting in economic and performance losses.
The second problem is the optimization of network design prior to actual
implementation. This requires the ability to model a given network
topology, including its protocols, and devices, and to simulate the actual
operation of the network at all its levels. Once the network is accurately
simulated, performance data can be gathered and the proposed network
optimized to meet performance objectives specified by a network manager.
Current simulation tools provide only limited capability to model all the
details of an actual network. These network models do not capture the
internodal activity in sufficient granularity to simulate realistic
network behavior. In addition, simulation tools require extensive
computation time, limiting their effectiveness for real time simulation,
optimization analysis and network design. Accordingly, what is needed is a
simulation tool which accurately models network interaction and allows
near real time simulation.
SUMMARY OF THE INVENTION
The invention provides methods and apparatuses for modeling and optimizing
networks according to network performance objectives. The methods produce
a network model describing the network topology, traffic patterns and
protocols. This model is created by either collecting and consolidating
actual topology and traffic data from the network, or by a network
simulator when creating or modifying a network design, or by a combination
of the two processes. Goals for network performance objectives are
defined, and the network is then optimized to meet these goals.
Optimization can be of LAN segments or of the position of a shared central
resource.
Optimization for the purpose of finding the optimal position in the network
of a shared central resource employs a "center of gravity" approach which
analyzes the effectiveness of positioning the shared central resource at
various locations in the network. The optimal position of the shared
central resource is "the center of gravity" with respect to the clients
because each client "pulls" the shared central resource in its direction
at a "force" proportional to the amount of traffic between it and the
shared central resource. The optimal position of the shared central
resource is the "balance" point given "pulling" forces from a multiplicity
of clients in different directions and pull strength.
A data packet flowing between a client and a shared central resource makes
use of communication resources, such as a LAN, router, or bridge, along
the path traversed by the packet. The actual path taken is governed by the
network protocol transporting the packet as well as on the particular
network topology. In traversing a source-destination path a data packet
"hops" a particular communication resource, incurring a "hop-cost". The
term "hop-cost" is used in a genetic sense and may represent dollar cost,
delay cost, number of hops, etc., or a function which simultaneously
depends on several variables. The optimization method serially "attaches"
the shared central resource to each possible "candidate" network segment,
router or other switching element and determines the total hop cost
incurred in communicating with its clients. The position yielding the
minimal hop cost is selected as the optimal position for the shared
central resource.
The optimization of LAN segments is performed by "hub tree" optimization,
which is applicable to a segment composed of hubs interconnected to a hub
tree. The process repeatedly partitions the LAN segment at each of its
hubs into two smaller segments, and determines the overall traffic flow
patterns within and between the partitions, and scores the partitions
relatives to network performance objectives. The hub yielding the
partitions with the best score is the optimal hub at which the LAN segment
should be partitioned.
BRIEF DESCRIPTION OF THE DRAWINGS
FIG. 1 is pictorial illustration of the apparatus of the present invention
showing a network 11 comprised of LAN segments 13, nodes 16, switching
elements 19, segment collectors 17, consolidator 25, simulator 37, and
optimizer 29.
FIG. 2 is a block diagram illustrating the method of the present invention,
showing the steps of collecting 101 network configuration data from
segment collectors 17, consolidating 103 the network configuration data,
to produce a network model 27, and optimizing 107 the network
configuration.
FIG. 3 is a block diagram illustrating the process of optimizing network 11
using the center of gravity optimization process 200.
FIG. 4 is a pictorial illustration of a LAN segment 13 having hubs 402, and
partitions 408.
FIG. 5 is a block diagram illustrating the process optimizing network 11
using the hub-tree optimization process 500.
FIG. 6 is a pictorial illustration of bi-directional node to node traffic
flow collected on a real hub LAN.
FIG. 7 is a block diagram illustrating the process of scoring the
partitions during hub tree optimization process 500.
DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT
Referring now to FIGS. 1 and 2, FIG. 1 shows a pictorial illustration the
network elements used in the preferred embodiments of the apparatus and
methods of the present invention, and FIG. 2 shows the method 100 of
optimizing networks. Network 11 includes a number of LAN segments 13, each
of which contains a plurality of nodes 16, a switching element 19, and a
segment collector 17. Nodes 16 are individual computers connected to LAN
segment 13. Each node 16 can contain a number of application programs,
clients 15 (not shown), which communicate with a shared central resource
39. Switching elements 19, which can be routers, bridges, or the like,
connect the individual LAN segments 13 along links 41, and allow
communication between LAN segments 13 having different topologies and
network protocols. Segment collector 17 monitors the LAN segment 13 to
which it is attached and collects network traffic and topology data.
Referring to FIG. 2, optimization method 100 collects 101 data describing
network 11, including its topology and traffic flow patterns. Data
collection is accomplished in the preferred embodiment using segment
collectors 17 on the LAN segments 13 of interest; information about other
LAN segments 13 can be ignored if desired. These segment collectors 17
collect data local to their attached LAN segment 13. Some conventional
networks 11 use segment collectors 17 (e.g. SNMP, RMON, network analyzers,
etc.) which may relay the collected information to a network management
console 23.
Next, optimization method 100 builds 103 an overall network model 27 from
local data collected by segment collectors 17, using consolidator 25. In
the preferred embodiment, the input to consolidator 25 comes either
directly from segment collectors 17 or indirectly from segment collectors
17 via network management console 23. In either case consolidator 25
produces a network model 27 of the portions of network 11 for which data
was collected, including its network topology, the clients 15, switching
devices 19, links 41, LAN segments 13, the network protocols employed, and
the traffic flows. Alternatively, network model 27 can be based on data
acquired from both segment collectors 27 and network management console
23. In the preferred embodiment, consolidator 25 is implemented as a
processor executing software routines stored in memory.
Where the objective is to design a new network, for which actual measured
network data does yet not exist, a simulator 37 is used to generate
network model 27, by describing the network elements, topology, and
protocols. Simulator 37 simulates 99 (FIG. 2) the network model 27 for
input to optimizer 29. Simulator 37 can also accept a network model 27
generated by consolidator 25, from real network data. This lets a network
manager start with an existing network 11 and then model "what-if" changes
45 by simulating 99 the network model 27 of the modified network, and
submitting that model to optimizer 29 for optimization 107. The "what-if"
capabilities of simulator 37 let a network manager move network devices
around, add applications, change one object type with another (e.g. from
an ethernet LAN to an FDDI LAN, or from one router type to another), and
the like. In the preferred embodiment, simulator 37 is implemented as a
processor executing software routines stored in memory. The operation of
simulator 37 will be described below.
Optimizer 29 accepts network model 27 and a set of network performance
objectives defined in goals 31. Optimizer 29 is "unaware" of the source of
network model 27, whether from simulator 37 or from consolidator 25, or
both. Referring to FIG. 2, the user, typically a network manager,
specifies 105 optimization goals 31. Optimization goals 31 can specify
performance objectives with respect to either a shared central resource
39, or within a LAN segment 13. Goals 31 for shared central resource can
be to minimize the average communication between a shared central resource
39 and all of its clients 15, to minimize the average number of switching
elements 19 or links 41 traversed by data packets flowing between the
shared central resource 39 and its clients 15, or to minimize the dollar
cost incurred in communicating with the shared central resource 39.
Optimizer 29 then optimizes 109 the network configuration, and produces
configuration recommendations 33 describing how to re-configure network 11
in order to achieve the network performance objective defined by goals 31.
Optimizer 29 uses a set of optimization rules stored in memory 43 for
optimizing 107 network 11 depending on goals 31. Where goals 31 specify
the performance objectives for a shared central resource 39, optimizer 29
uses a center of gravity optimization process 200. Where goals 31 specify
the performance objectives for a LAN segment 13, optimizer 29 uses a
hub-tree optimization process 500. In the preferred embodiment, optimizer
29 is implemented as a processor executing optimizations processes 200 and
500 stored in memory 43.
Referring now to FIG. 3 there is shown a block flow diagram of the center
of gravity optimization process 200 for optimizing 107 the position of
shared central resource 39. Using network model 27 optimization process
200 identifies 201 all the available switching elements 19 to which shared
central resource 39 may be attached. These switching elements 19 typically
include LANs segments 13, routers, bridges, routing servers, LAN switches,
and the like. The address or other unique identifier of each switching
element 19 is stored in list SWITCH. The i-th switching element 19 in list
SWITCH is SWITCH[i] where i=1, 2, . . . , S, S equal to the number of
switching elements 19.
Next, from network model 27, all network links 41 interconnecting switching
elements 19 of SWITCH are identified 203. Links 41 are uniquely identified
and stored in list LINK. The l-th link in LINK is LINK[l] where l=1, 2, .
. . , L, L equal to the number of links 41.
Next, optimization process 200 selects 205 a shared central resource 39
whose position is to be optimized 107 in network 11 with respect to its
clients 15 and goals 31. This shared central resource 39 is designated R,
and can represent a node 16 where shared central resource 39 is physically
connected to some SWITCH[i]. Alternatively, R can represent some logical
shared central resource 39, such as a database application running in a
node 16, possibly sharing the node with other application programs. In
this case R is "hosted" by node 16 which is in turn physically attached to
some SWITCH[i].
Optimization process 200 then identifies 207 all clients 15 communicating
with R. Clients 15 are distributed throughout network 11 in nodes 16 on
various LAN segments 13. Clients 15 are uniquely identified and are stored
in list CLIENT. The j-th client in list CLIENT is CLIENT[j] where j=1, 2,
. . . , C, C being the number of clients 15 on network 11 communicating
with shared central resource 39.
Optimization process 200 determines 209 the amount of network traffic known
to flow between the given clients 15 and R over a given time t. These
traffic flow amounts are stored in TRAFFIC. TRAFFIC has C elements, C
being the number of clients 15 in CLIENTS. The j-th entry in TRAFFIC
comprises TRAFFIC[j, client.sub.-- r] for the unidirectional traffic flow
(for example in bytes) from CLIENT[j] to R, and TRAFFIC[j, r.sub.--
client] for the traffic from R to CLIENT[j]. TRAFFIC is formed from
network model 27 using actual measurements, or through estimation, for
example, using simulation by simulator 37.
The optimization goals 31 specified by the user are stored in list GOALS.
Optimization process 200 then loops through a series of "cost" analyses
that determine the TOTAL.sub.-- R.sub.-- COST of positioning R, the shared
central resource 39, at each of the switching elements 19 in SWITCH.
Optimization process 200 determines the SWITCH[i] for which TOTAL.sub.--
R.sub.-- COST[i] is a minimum.
Each switching element 19 in SWITCH or LIST is a "hop." TOTAL.sub.--
R.sub.-- COST[i] is a function of the number of hops a data packet must
travel when traversing network 11 between a client 15 and the shared
central resource 39 when the shared central resource 39 is attached to
SWITCH[i], and the cost of traversing each hop. The cost of a hop is
described as follows.
Given a particular hop h and an optimization goal 31 termed "goal",
function hop.sub.-- cost(goal, h) assigns a cost metric to h relative to
the given optimization goal 31. The cost metric is stated as a normalized
quantity, for example delay time per byte, per bit or per packet. If
optimization goal 31 is to minimize delay then hop.sub.-- cost(goal, h)
would return the known or estimated delay incurred while going through hop
h. Alternatively, if optimization goal 31 is to minimize hops, then
hop.sub.-- cost(goal, h) returns a fixed value of 1 for any hop h. The hop
cost function can be a multivariate function representing a combination of
optimization goals 31, for example, a weighting of 70% minimized hops and
30% minimized delay.
In an alternative embodiment, hop costs are assigned by constructing a hop
cost table. The network manager associates a hop cost metric for each hop.
For example to position the shared central resource 39 so that link
bandwidth is minimized, the hop cost table sets the link 41 hop cost to
value of 3 and that of switching elements 19 to value 1. The hop costs
computed by hop.sub.-- cost(goal, h) are not necessarily the same as or
even related to the hop costs used by the network routing protocol (e.g.
RP or IGRP) used for computing a path between a client 15 and the shared
central resource 39 since the route selection is governed by protocol
standards. Using a hop cost table, optimization process 200 associates its
own cost metric with each path produced by the network routing protocol.
In either embodiment TOTAL.sub.-- R.sub.-- COST[i] is a function of the
total hop cost of position R at each SWITCH[i].
Continuing then, optimization process 200 begins an iterative loop for each
switching element 19 in SWITCH, that is each SWITCH[i], i equals 1 to S,
setting 211 the TOTAL.sub.-- R.sub.-- COST[i] to zero.
A second iterative loop is begun for each client 15 in CLIENT to determine
the path cost associated with traffic flow between each CLIENT[j], j
equals 1 to C, and R, now assumed to be attached to SWITCH[i].
This cost is determined by identifying 213 the communication path from the
client 15 to the switching element 19 to which R, the shared central
resource 39, is attached. Specifically, PATH[j, i] is the communication
path from CLIENT[j] to SWITCH[i] to which R is attached. The path taken
from CLIENT[i] to SWITCH[j] in network 11 depends on the particular ISO
level 3 network layer protocol (e.g. IP, IPX, XNS, AppleTalk) "spoken"
between a client 15 and the shared central resource 39. This is because
certain switching elements 19, such as routers, operate by looking "into"
a particular data packet to determine its protocol. Router ports can be
configured to be protocol "sensitive"--letting one protocol type through
(e.g. IP) but not another (e.g. XNS). Consequently, the particular network
level protocol employed in communicating between a client 15 and R, the
shared central resource 39, must be known in order to determine the
communication path between them.
A particular path PATH[i, i] traversed from CLIENT[j] to SWITCH[i] includes
a sequence of hops, as described above. The path is determined from either
actual measurements by the segment collectors 17 or can be determined
using the network routing protocol and the particular protocol filtering
settings of the ports of ISO Level 3 switching elements 19. While in many
cases PATH[j, i] will be the same as PATH[i, j] the preferred embodiment
does not rely on such an assumption. For example, one direction of a full
duplex link, such as link 41, may carry a load of 90% and exhibit high
delay while the other direction may at the same time carry a lower load of
only 10% and thus exhibit lower delay. Therefore, in general PATH[j, i]
and PATH[i, j] are not the same. While the actual path taken is governed
exclusively by the routing protocol employed in network 11 (such as IP or
IPX), the preferred embodiment outlined here has no control over the path
selection. Optimization process 200 is however capable of determining the
path that would be selected by the network routing protocol from any point
in network 11, such as a client 15, to any other point in network 11, such
as the position of R.
Having determined the path PATH[j, i] between client 15 under consideration
and the current proposed switching element 19, the function hop.sub.--
cost(goal, h) determines 215 for each hop h along the path PATH[j, i] the
UNIDIRECTIONAL.sub.-- COST[j, i] of traffic from CLIENT[j] to R attached
to SWITCH[i]. UNIDIRECTIONAL.sub.-- COST[i, j] is the cost of transporting
a given amount of traffic from SWITCH[i] to CLIENT[j] over path PATH[i,
j]. It is the sum of all hop costs, as determined by the hop.sub.-- cost
function, traversed along path PATH[i, j] and the amount of traffic
TRAFFIC[j] transported along that path.
As stated above, optimization process 200 does not assume or require that
the path of traffic from the shared central resource 39 to client 15 be
the same as the path from the latter to the former. Accordingly,
optimization process 200 next identifies 217 the communication path from
the switching element 19 to which the shared central resource 39 is
attached to the client 15. This is PATH[i, j] from R attached to SWITCH[i]
to CLIENT[j].
Next, using function hop.sub.-- cost(goal, h), optimization process 200
determines 219 for each hop h along the path PATH[i, j] the
UNIDIRECTIONAL.sub.-- COST[i, j] of traffic from R attached to SWITCH[i]
to CLIENT[j].
Having determined the unidirectional costs of transporting a data packet
over network 11 back and forth between a client 15 and a switching element
19, optimization process 200 then determines 221 the bi-directional cost.
BIDIRECTIONAL.sub.-- COST[i, j] represents the total traffic flow cost
between i and j in both directions. If R is attached to SWITCH[i] then
BIDIRECTIONAL.sub.-- COST[i, j] reflects the total bi-directional traffic
cost between R and CLIENT[j]. BIDIRECTIONAL.sub.-- COST[i, j] equals:
UNIDIRECTIONAL.sub.-- COST[i, j]+UNIDIRECTIONAL.sub.-- COST[j, i]Eq. (1)
Clearly BIDIRECTIONAL.sub.-- COST[i, j]=BIDIRECTIONAL COST[j, i].
Once the bi-directional cost from the client 15 is determined, it is summed
223 to the TOTAL.sub.-- R.sub.-- COST for the current switching element
19. This is expressed as:
TOTAL.sub.-- R.sub.-- COST[i]=TOTAL.sub.-- R.sub.--
COST[i]+BIDIRECTIONAL.sub.-- COST[i, j] Eq. (2)
TOTAL.sub.-- R.sub.-- COST[i] thus represents the total cost of positioning
shared central resource 39 on the switching elements of SWITCH[i] with
respect to all its clients 15. Optimization process 200 then loops back in
the second iterative loop for each client 15, that is each CLIENT[j]. Once
all clients 15 for shared central resource 39 are examined, optimization
process loops 200 back to the first iterative loop, and repeats the cost
function analysis for the next proposed switching element 19, SWITCH[i].
When all switching elements 19 have been examined as possible attachment
points for shared resource 39, the TOTAL.sub.-- R.sub.-- COST[i] for each
switching element 19 will be known. Optimization process 200 then produces
225 configuration recommendation 33 in the form of a sorted table
comprised of entry pairs <i, TOTAL.sub.-- R.sub.-- COST[i]> sorted by
increasing values of TOTAL.sub.-- R.sub.-- COST[i], again i indicating
each switching element 19 in SWITCH. The closer a particular entry is to
the beginning of the table in configuration recommendation 33, the lower
its TOTAL.sub.-- R.sub.-- COST measure, and the higher its "merit". The
first entry in configuration recommendation 33 is the optimal switching
element 19 to which shared central resource 39 should be attached.
Referring now to FIG. 4, there is shown a pictorial illustration of a LAN
segment 13 having partitions 408. Typically, LAN segments 13 are
physically organized as a collection of hubs 402 interconnected among
themselves so as to form a tree structure. A node 16 is attached to a LAN
segment 13 via a port 403 on a hub. In each LAN segment 13 there is a root
hub 404 which forms the top the hub tree in that LAN segment 13. The hubs
402 forming a LAN segment 13 are typically scattered throughout a local
area such as on different floors of an office building or throughout a
university or industrial campus. The maximum allowed wiring length between
hubs 402 depends on the particular LAN technology employed and typically
varies from a few hundred yards to well over a few miles. Regardless of
the particular tree structure or area spanned, all clients attached to a
LAN segment 13 are part of the same LAN. For example, if a LAN segment 13
is an ethernet LAN then all the LAN nodes 16 are part of the same
"collision domain", or if the LAN segment 13 is a token ring all its nodes
16 share the same token.
When the traffic load on LAN segment 13 increases, the time delay for
completion of a transmission also increases, usually in some exponentially
related manner. One method of increasing performance is to replace the LAN
segment 13 with one having higher throughput. This solution tends to be
very expensive since all the hubs 402 and all the interface cards on nodes
16 need to be changed. In many cases it would be much more economical to
partition LAN segment 13 into two independent LAN segments 13 so as to
lower the traffic load on each of the two new LAN segments 13. The two
segments would then be interconnected via an existing or a new switching
element 19.
The traffic patterns among users in a network tend to follow the actual
business work flow: users working in the same department (e.g. accounting)
or on the same project tend to communicate among themselves more often
then to users outside of their work group (accountants would rarely
communicate with users in the R&D department). Such user groups also tend
to be physically co-located (e.g., share the same floor) and therefore
attach to the same LAN segments 13 and hubs 402. Accordingly, hub-tree
optimization process 500 identifies the "natural" user groups and
partitions the LAN segment 13 so as to minimize the "interference" among
unrelated user groups. The LAN segment 13 is partitioned with a switching
element 19 placed between the partitions; this preserves the existing
wiring plan of the LAN segments and significantly reduces the cost of
increasing the performance of the LAN segment 13.
Referring now to FIG. 5, there is shown hub-tree optimization process 500
for determining the optimal hub 402, namely, to identify hub(opt)
producing the optimal partition of LAN segment 13 relative to a goal 31.
Hub tree optimization process 500 examines N-1 possible ways to partition
LAN segment 13, associating a "score" with each such partition, where N is
the number of hubs 402 in LAN segment 13. It is unnecessary to partition
LAN segment 13 at its original root hub 404 since it will produce the
original tree formation of LAN segment 13. Hence, only N-1 different ways
to partition LAN segment 13 are examined, not N. The particular
partitioning resulting the lowest score is the optimal partition. When the
optimal hub(opt) is determined, LAN segment 13 will be split into two
partitions 408, one partition including of hub(opt) and all the hubs in
its subtree, and a second partition which is a tree rooted at the root hub
404 and including of the original LAN segment 13 tree less the partition
at hub(opt). In this case hub(p) becomes the root of the first partition.
Hub-tree optimization process 500 employs the following definitions:
PA(p) is the hub tree structure of LAN segment 13 consisting of hub(p) and
all hubs 402 in its subtree. An example of PA(p) is seen on FIG. 4, with
Hub(2) as hub(p), and Hub(3) and Hub(4) as its subtree. PB(p) is the
balance of LAN segment 13 excluding PA(p). In FIG. 4, it is represented by
partition 408 containing Hub(1) and Hub(5).
M is the total number of nodes 16 attached to LAN segment 13.
N is the total number of hubs 402 forming LAN segment 13. A hub 402 is
identified by a numerical identifier, 1, 2, . . . , N. The i-th hub 402 is
denoted as "hub(i)". Hub(i) represents the identity of each source hub 402
originating traffic on LAN segment 13, where i=1, 2, . . . , N. Hub(j)
represents the identity of each hub 402 receiving traffic on LAN segment
13, where j=1, 2, . . . , N. Hub(p) represents the identity of each
destination hub 402 used to partition LAN segment 13, where p=1, 2, . . .
, N, where the identity of root hub 404 is excluded.
List MMT is a | | |
