Network anaysis method for identifying global and local node servers and for determining a reconfigured network to provide improved traffic

We claim:

1. A network analysis method for use in relation to a network of the type comprising a plurality of sub-networks each with a plurality of nodes, the method comprising the steps of:

(1) monitoring the network to collect and store traffic data indicative of linkage between nodes as judged by traffic therebetween, "linkage" meaning a level of interconnectivity between nodes as determined by a quantity of traffic therebetween;

(2) analyzing said traffic data to identify nodes acting as global servers, a global server being a node which communicates with nodes on plural sub-networks but without communicating predominantly with nodes on one sub-network;

(3) accessing said stored traffic data and removing traffic data associated with nodes identified as acting as global servers, and identifying nodes acting as local servers by analyzing stored traffic data remaining after said removing, a local server being a node which is a predominant communicator with nodes on one particular sub-network.

2. A method according to claim 1, wherein step (3) involves examining the traffic data to identify any candidate global server amongst said nodes where a candidate global server is a node whose linkage to any of said sub-networks is less than a first predetermined portion of its total linkage to all nodes, and

where a said candidate global server is identified, identifying the candidate global server with the highest total linkage, removing its associated traffic from the traffic data, and returning to the start of step (3) to repeat the step using the traffic data so modified;

where no such candidate global server is identified, examining the traffic data to identify any candidate local server amongst said nodes where a candidate local server is a node for which for the sub-network with the highest linkage thereto, this linkage is equal to or greater than a second predetermined portion of the total linkage of that candidate local server, and

where a said candidate local server is identified, identifying the candidate local server with the highest linkage, recording this candidate as a local server, removing its associated traffic from the traffic data, and returning to the start of step (3) to repeat the step using the traffic data so modified;

where no said candidate local server is identified, exiting step (3).

3. A method according to claim 2, wherein said first predetermined portion and second predetermined portion are both about a half.

4. A method according to claim 1, wherein said traffic data is stored as traffic elements each providing an indication of traffic between a pair of said nodes, modification of the traffic data to remove traffic associated with a said server being effected by marking the relevant traffic elements as currently disabled.

5. A method according to claim 1, wherein the linkage of a node with other associated nodes is measured in terms of at least one of the following:

number of associated nodes;

number of frames involved in the traffic with the associated nodes;

number of bytes involved in the traffic with the associated nodes.

6. A method according to claim 1, wherein in step (1) of claim 1 the monitoring of the network is carried out in such a manner as to enable role information to be gathered indicative of whether a node is acting in a server or client role in relation to individual traffic items associated therewith, the identification of a node as a global or local server in step (3) being effected without reference to traffic for which the node is acting as a client as indicated by said role information.

7. A method according to claim 6, wherein said role information is derived on the basis of the well known port status of the node end points associated with traffic passed between a pair of nodes, one node of said pair being identified as acting in a server role and the other node in a client role where the end point for said one node is a well known port whilst the other end point is otherwise.

8. A method according to claim 1, wherein for at least one local server identified in step (3), determining an optimum sub-network for said local server, said determining involving assuming a change in location of the local server on each sub-network of said network, in turn, and evaluating for each such location of the local server, an optimal-location function that provides a measure of traffic between sub-networks that would be associated with the local server in a current assumed location, and identifying as said optimum sub-network, that sub-network for which evaluation of said optimal-location function indicates a minimum for said traffic between sub-networks.

9. A method according to claim 8, wherein said optimum-location function is a count of nodes that have communication linkage with said local server and are located on sub-networks other than one corresponding to the said current assumed location of the local server.

10. A method according to claim 8, wherein for a local server whose said optimum sub-network has been determined, determining whether any of the nodes to which said local server has communication linkage as a server on said optimum sub-network, should be moved to said optimum sub-network; said determining including testing for each node whether linkage between that node and the local server is about half or more of the total communication linkage of that node.

11. A method according to claim 1 wherein for the group of local servers identified in step (3), each local server is selected in turn in order of descending linkage and for each such server;

(i) creating a respective workgroup therefor unless the local server concerned has already been allocated to another workgroup created in respect of a local server higher in said order,

(ii) if said respective workgroup has been created in (i) for the local server concerned, allocating the server to that respective workgroup, and

(iii) for any node whose linkage to the local server is about at least half of the total linkage of said node, allocating said node to the same workgroup as the local server.

12. A method according to claim 11, wherein for at least one said sub-network, a determination is made whether it is worthwhile splitting the sub-network into two sub-networks, said determination further comprising the steps of:

(a) pruning each workgroup that has been created in respect of a local server located on a sub-network of interest, by removing from the workgroup any nodes that are inappropriate to include therein when considering the workgroup only in relation to the sub-network of interest;

(b) forming a respective further workgroup for each node of the sub-network of interest where that node is not already in a workgroup associated with the sub-network;

(c) merging the workgroups associated with the sub-network of interest until only two such workgroups remain; and

(d) deciding whether to split the sub-network by comparing an amount of traffic between the two workgroups remaining after step (c) with total traffic associated with each such workgroup.

13. A method according to claim 12, wherein step (a) involves removing from a workgroup being pruned, any node that is located on a different sub-network to the one of interest, and any node whose inclusion in the workgroup relies directly or indirectly on its association with a node located on a different sub-network to the one of interest.

14. A method according to claim 12, wherein step (c) involves an iterative process in which during each iteration, the workgroup with the smallest amount of associated traffic is merged with the workgroup with which it has the greatest linkage.

15. A method according to claim 8 wherein operations specified in claim 8 are carried out using the traffic data collected in step (1) of claim 1 but with all global server traffic removed.

16. A network analysis method for use in relation to a network of the type comprising a plurality of sub-networks each with a plurality of nodes, the method comprising the steps of:

(1) monitoring the network to collect and store traffic data between nodes as indicative of linkage between said nodes, "linkage" meaning a level of interconnectivity between nodes as determined by a quantity of traffic therebetween;

(2) processing the traffic data to identify nodes acting as local servers, a local server being a node which is a predominant communicator with nodes on one particular sub-network; and

(3) determining for at least one of the local servers identified in step (2), an optimum sub-network for the at least one local server, said determining assuming a change in location of the at least one local server on each sub-network in turn, and evaluating for each changed location of the at least one local server, an optimal-location function that provides a measure of traffic between sub-networks that would be associated with the at least one local server in an assumed current location, said determining further identifying as said optimum sub-network, that sub-network for which evaluation of said function indicates a minimum of traffic between sub-networks.

17. A network analysis method for use in relation to a network having a logical segment with a plurality of nodes, for the purpose of determining whether it is worthwhile splitting the logical segment into two such segments, the method comprising the steps of:

(1) monitoring the logical segment to collect and store traffic data indicative of the linkage between the nodes of the segment as judged by traffic therebetween;

(2) carrying out a first iterative process for analyzing the segment traffic data to classify said nodes into workgroups each with a local server and one or more client nodes, each iteration of this first iterative process involving allocating the node with the greatest traffic linkage to a respective new workgroup as a local server, further allocating as client nodes to the same workgroup those nodes whose linkage to the local server node is greater than a predetermined portion of the total linkage of the node concerned, and modifying the traffic data by removal of traffic associated with the new workgroup;

(3) carrying out a second iterative process for merging the workgroups identified in step (2) to leave two remaining workgroups, each iteration of this second iterative process involving identifying the workgroup with the smallest amount of associated traffic and merging it with the workgroup with which it has the greatest linkage; and

(4) deciding whether it is worthwhile splitting the logical segment by comparing the amount of traffic between the two workgroups left remaining after step (3) with the total traffic associated with each such workgroup.

18. A memory product for enabling a computer means to perform analysis of a network of the type comprising a plurality of sub-networks, each with a plurality of nodes, the memory product comprising:

means for enabling the computer means to monitor the network to collect and store traffic data indicative of linkage between nodes as judged by traffic therebetween, "linkage" meaning a level of interconnectivity between nodes as determined by a quantity of traffic therebetween;

means for enabling the computer means to analyze said traffic data to identify nodes acting as global servers, a global server being a node which communicates with nodes on plural sub-networks but without communicating predominantly with nodes on one sub-network;

means for causing said computer means to access said stored traffic data and to remove traffic data associated with nodes identified as acting as global servers; and

means for enabling the computer means to identify nodes acting as local servers by analyzing stored traffic data remaining after said removing, a local server being a node which is a predominant communicator with nodes on one particular sub-network.

19. A memory product for use with a computer means to enable said computer means to analyze a network comprising a plurality of sub-networks each with a plurality of nodes, the memory product comprising:

means for controlling the computer means to monitor the network to collect and store traffic data between nodes as indicative of linkage between said nodes, "linkage" meaning a level of interconnectivity between nodes as determined by a quantity of traffic therebetween;

means for controlling the computer means to process the traffic data to identify nodes acting as local servers, a local server being a node which is a predominant communicator with nodes on one particular sub-network; and

means for causing the computer means to determine, for at least one identified node acting as a local server, an optimum sub-network for the at least one identified node, said computer means controlled to assume a change in location of the at least one identified node on each sub-network, in turn, and to evaluate for each changed location, an optimal-location function that provides a measure of traffic between sub-networks that would be associated with the at least one identified node in an assumed current location, and to further identify as said optimum sub-network, that sub-network for which evaluation of said function indicates a minimum of traffic between sub-networks.

Description Submit all comments and votes

The present invention relates to a network analysis method for use in relation to a network of the type comprising a plurality of sub-networks each with a plurality of nodes.

The network analysis method of the invention has particular application to networks where the component sub-networks are logical segments interconnected by bridges operating at level 2 of the seven layer OSI Reference Model. However, the network analysis method can also be used in appropriate circumstances with other networks such as Internet networks with "IP" sub-networks interconnected by routers or gateways operating at level 3 of the OSI Reference Model.

As network monitoring systems become more and more sophisticated and comprehensive, the network operator has an increasing problem identifying significant data amongst the volumes of data on network operation provided by such monitoring systems. This is particularly so where the network concerned comprises several sub-networks with certain nodes acting as global servers across all sub-networks as in such cases it is difficult to get a true picture of what is really happening on each sub-network.

It is an object of the present invention to provide a network analysis method that facilitates an appreciation of operation of the network at a sub-network level.

SUMMARY OF THE INVENTION

To this end, in one aspect the present invention provides a network analysis method that serves to identify nodes acting as local servers, that is, nodes that predominantly deal with one particular sub-network. More particularly, in this aspect the present invention provides a network analysis method for use in relation to a network of the type comprising a plurality of sub-networks each with a plurality of nodes, the method comprising the steps of:

(1) monitoring the network to collect and store traffic data indicative of the linkage between nodes as judged by traffic therebetween; and

(2) processing the traffic data by preferentially removing traffic associated with nodes identified as acting as global servers, and using the remaining traffic to identify nodes acting as local servers.

The preferential removal of the global server traffic effectively unmasks the local servers enabling them to be identified.

Step (2) of the method preferably involves examining the traffic data to identify any candidate global server amongst said nodes where a candidate global server is a node whose linkage to any of said sub-networks is less than a first predetermined portion (generally 50%) of its total linkage to all nodes, and

where a said candidate global server is identified, identifying the candidate global server with the highest total linkage, removing its associated traffic from the traffic data, and returning to the start of step (2) to repeat the step using the traffic data so modified;

where no such candidate global server is identified, examining the traffic data to identify any candidate local server amongst said nodes where a candidate local server is a node for which for the sub-network with the highest linkage thereto, this linkage is equal to or greater than a second predetermined portion (again, generally 50%) of the total linkage of that candidate local server, and

where a said candidate local server is identified, identifying the candidate local server with the highest linkage (advantageously, highest total linkage, but alternatively, highest linkage to any one sub-network), recording this candidate as a local server, removing its associated traffic from the traffic data, and returning to the start of step (2) to repeat the step using the traffic data so modified;

where no said candidate local server is identified, exiting step (2).

The linkage of a node with other associated nodes will generally be measured in terms of at least one of the following: number of associated nodes; number of frames involved in the traffic with the associated nodes; number of bytes involved in the traffic with the associated nodes. For example, linkage may be measured in terms of number of associated nodes but with a traffic volume measurement (frames/bytes) being used to resolve situations where there is a tie between two linkage values being compared.

Although judgement as to whether a node is acting as a server can be based entirely on relative traffic linkages, preferably the monitoring of the network is carried out in such a manner as to enable role information to be gathered indicative of whether a node is acting in a server or client role in relation to individual traffic items associated therewith. In this case, the identification of a node as a global or local server in step (2) is effected without reference to traffic for which the node is acting as a client as indicated by said role information. The role information is, for example, derived on the basis of the "well known port" status of the node end points associated with traffic passed between a pair of nodes, one node of this pair being identified as acting in a server role and the other node in a client role where the end point for said one node is a well known port whilst the other end point is otherwise.

Once the local servers have been identified, then further analysis can be effected to determine how network performance may be improved. Thus, advantageously for at least one of the local servers identified in the main method step (2), a determination is made as to the optimum sub-network for this local server, this determination involving notionally locating the local server concerned on each sub-network in turn and evaluating for each such location of the local server, a predetermined optimal-location function that provides a measure of the traffic between sub-networks that would be associated with the local server in its current notional location, such determination further involving identifying as said optimum sub-network that sub-network for which evaluation of said function indicates a minimum for said traffic between sub-networks. For simplicity and speed, the optimum-location function is, preferably, a count of nodes that have linkage with the local server concerned and are located on sub-networks other than the one corresponding to the current notional location of the local server.

Upon the optimum sub-network for a local server being determined, a determination is advantageously also made as to whether, if this local server is located on its said optimum sub-network, any of the nodes to which is has linkage as a server, should also be moved to said optimum sub-network. This determination involves testing for each node whether the linkage between that node and the local server is substantially half or more of the total linkage of that node.

Another useful analysis that can be effected once the local servers have been identified is to associate the local servers and their client nodes into workgroups. To this end, each local server is taken in turn in order of descending linkage within the group of local servers and for each such server:

(i) a respective workgroup is created therefor unless the local server concerned has already been allocated to another workgroup created in respect of a said local server higher in said order,

(ii) if a said respective workgroup has been created in (i) for the local server concerned, then the server is allocated to that workgroup, and

(iii) any node whose linkage to the local server is substantially at least half of the total linkage of that node is allocated to the same workgroup as the local server.

It will be appreciated that a workgroup may contain more than one local server in the case where one such server is a well-linked client of another such server.

Using the workgroups established in this way, a determination can then be made as to whether it is worthwhile splitting a sub-network into two sub-networks, this determination involving:

(a) pruning the or each workgroup that has been created in respect of a local server located on the sub-network of interest, by removing from the workgroup any nodes that may no longer be appropriate to include therein when considering the workgroup only in relation to the sub-network of interest;

(b) forming a respective further workgroup for each node of the sub-network of interest where that node is not already in a workgroup associated with the sub-network;

(c) merging the workgroups associated with the sub-network of interest until only two such workgroups remain; and

(d) deciding whether it is worthwhile splitting the sub-network by comparing the amount of traffic between the two workgroups left remaining after step (c) with the total traffic associated with each such workgroup.

The analysis tasks carried out following identification of the local servers are, of course, preferably carried out using the traffic data collected in step (1) of the main method but with all global server traffic removed. However, even if the global server traffic is not all removed, the analysis tasks will generally still produce some useful information.

According to another aspect of the present invention, there is provided a network analysis method for use in relation to a network of the type comprising a plurality of sub-networks each with a plurality of nodes, the method comprising the steps of:

(1) monitoring the network to collect and store traffic data indicative of the linkage between nodes as judged by traffic therebetween;

(2) processing the traffic data to identity nodes acting as local servers; and

(3) determining for at least one of the local servers identified in step (2), the optimum sub-network for this local server, this determination involving notionally locating the local server concerned on each sub-network in turn and evaluating for each such location of the local server, a predetermined optimal-location function that provides a measure of the traffic between sub-networks that would be associated with the local server in its current notional location, said determination further including identifying as said optimum sub-network, that sub-network for which evaluation of said function indicates a minimum for said traffic between sub-networks.

According to a further aspect of the present invention, there is provided a network analysis method for use in relation to a network having a logical segment with a plurality of nodes, for the purpose of determining whether it is worthwhile splitting the logical segment into two such segments, the method comprising the steps of:

(1) monitoring the logical segment to collect and store traffic data indicative of the linkage between the nodes of the segment as judged by traffic therebetween;

(2) carrying out a first iterative process for analyzing the segment traffic data to classify said nodes into workgroups each with a local server and one or more client nodes, each iteration of this first iterative process involving allocating the node with the greatest traffic linkage to a respective new workgroup as a local server, further allocating as client nodes to the same workgroup those nodes whose linkage to the local server node is greater than a predetermined portion of the total linkage of the node concerned, and modifying the traffic data by removal of traffic associated with the new workgroup;

(3) carrying out a second iterative process for merging the workgroups identified in step (2) to leave two remaining workgroups, each iteration of this second iterative process involving identifying the workgroup with the smallest amount of associated traffic and merging it with the workgroup with which it has the greatest linkage; and

(4) deciding whether it is worthwhile splitting the logical segment by comparing the amount of traffic between the two workgroups left remaining after step (3) with the total traffic associated with each such workgroup.

BRIEF DESCRIPTION OF THE DRAWINGS

A network analysis method according to the invention will now be described, by way of non-limiting example, with reference to the accompanying diagrammatic drawings, in which:

FIG. 1 is a node cluster diagram depicting an example network with four sub-networks;

FIG. 2 is a diagram similar to FIG. 1 but showing example total traffic between nodes of the FIG. 1 network for a given monitoring period;

FIG. 3 is a diagram illustrating the main program items and data structures used in the network analysis method;

FIG. 4A shows a first form of traffic element data structure;

FIG. 4A shows a second form of traffic element data structure;

FIG. 5 is a flow chart of an Extract-Servers program shown in FIG. 3;

FIG. 6 is a diagram similar to FIG. 2 but showing only that component of the total traffic involving a node N1;

FIG. 7 is a diagram similar to FIG. 2 but showing only those components of the total traffic that remain after removal of traffic associated with global servers as identified by the FIG. 5 Extract-Servers program;

FIG. 8 is a diagram similar to FIG. 2 but showing only part of the network and only that component of the total traffic that is associated with a local server node N5 as identified by the FIG. 5 Extract-Server program;

FIG. 9 is a flow chart of a Move-Suggestions program shown in FIG. 3;

FIG. 10 is a flow chart of a Place-Server program item used by the FIG. 9 Move-Suggestions program;

FIG. 11 is a flow chart of a Place-Client program item used by the FIG. 9 Move-Suggestions program;

FIG. 12 is a diagram similar to FIG. 2 but showing only one sub-network and only those components of the total traffic that are local to the sub-network and are associated with local servers as identified by the FIG. 5 Extract-Server program;

FIG. 13 is a flow chart of a Split-Suggestions program shown in FIG. 3;

FIG. 14 is a flow chart of a Prune-Workgroups program item used by the FIG. 13 Split-Suggestions program;

FIG. 15 is a flow chart of a Merge-Workgroups program item used by the FIG. 13 Split-Suggestions program; and

FIG. 16 is a flow chart of a Split-Decision program item used by the FIG. 13 Split-Suggestions program.

BEST MODE OF CARRYING OUT THE INVENTION

FIG. 1 depicts an example network comprising four logical segments (sub-networks) X1, X2, X3 and X4 each with a plurality of nodes N, the nodes associated with a particular logical segment being clustered together. The logical segments are inter-connected by spanning devices in the form of bridges operating at level two of the seven-layer OSI Reference Model; each bridge makes its appearance on the FIG. 1 cluster diagram in the form of a corresponding node in each of the two logical segments it inter-connects. The pattern of interconnection of the logical segments by the bridges is not of importance for the purposes of the present description. The example network of FIG. 1 may be constituted by bridged Ethernets with each node being identified by an Ethernet address valid across all the logical segments of the network. The nodes N source and sink traffic to/from each other, this traffic being in the form of discrete message packets carrying both source and destination node addresses as well as the data to be transmitted.

The FIG. 1 network will be used as the basis for example traffic distribution diagrams used hereinafter to facilitate the description of the network analysis methods of the invention. For the purposes of the following description, it is assumed that the topology of the network in terms of which nodes are associated with which logical segments, is already known.

FIG. 2 illustrates the traffic across the FIG. 1 network over a given period of time, the passing of message packets between two nodes being represented by a line drawn therebetween with the thickness of the line providing a coarse indication of the quantity of traffic. In the present example, the traffic flows are derived by examination of the layer 2 source and destination addresses associated with each packet. Because the layer 2 addresses are valid across the whole network, examining the layer 2 addresses gives the true source and destination nodes of a packet regardless of the path taken across the network by the message packet.

Despite the lack of clarity in FIG. 2 resulting from the crowding together of traffic lines, it is possible to see that certain nodes communicate heavily with the other nodes of the network. For example, nodes N1 and N2 on logical segment X1 appear to communicate with virtually all other nodes of the network from which it might be reasonably inferred that these nodes have some overall role in monitoring or controlling the network.

Whilst diagrams of the FIG. 2 form give a network operator a general feel as to what is happening on the network, they do not permit a detailed scrutiny of the behaviour of the network and are easy to misconstrue.

The network analysis methods to be described hereinafter analyze traffic data similar to that used to create diagrams of the FIG. 2 form with a view to providing useful information on the character of the network and how its performance may be improved.

The general philosophy behind the network analysis methods to be described is that major improvements in the network's performance generally will not come from repositioning nodes that have a global pattern of communication (that is, their communication is not primarily with one logical segment) but from modifying the network in relation to nodes that communicate primarily with one logical segment (though not necessarily the segment upon which the node itself is located).

An important analysis task is therefore to separate out those nodes which communicate primarily on a global basis ("global servers") from those nodes who communicate primarily with one segment only and are major communicators in relation to that segment ("local servers"). It will be appreciated that whilst there may be many nodes which primarily communicate only with one segment, only some of these nodes will have a server-like role. Upon the local servers being identified, the network analysis methods described herein are then used to make suggestions as to whether any of these local servers should be moved to another logical segment and as to whether it would be worthwhile splitting a segment between two associated local servers.

FIG. 3 illustrates the main program items and the main data structures used in the implementation of the present invention described hereinafter. More particularly, three main program components are provided, these being an Extract-Servers program 10, a Move-Suggestions program 1, and a Split-Suggestions programs 12.

The Extract-Servers program 10 has available to it both traffic data and data on the logical arrangement of the network. The traffic data is in the form of a set of traffic elements 22 characterising node-to-node traffic on the network over a particular period. The data on the logical arrangement of the network is in the form of a list of segments 20 and a list of nodes 21, each list including association information between segments and nodes. The Extract-Servers program 10 analyses the traffic data presented in traffic elements 22 to produce a global servers list 23 and a local servers list 24.

The Move-Suggestions program 11 includes program items Place-Server 13 and Place-Client 14. The Move-Suggestions program 11 looks in turn at each local server identified by program 10 to decide whether it would be beneficial to move the local server to another segment and, if so, whether there would also be benefit in moving any of its client nodes (that is, nodes with which it communicates) to the same segment. On the basis of this analysis, program 11 produces a list of move suggestions (node-moves list 25). The program 11 also produces a list of work groups (workgroups list 26), each work group comprising a local server and its closely linked client nodes, if any.

The Split-Suggestions program 12 includes program elements Prune-Workgroup 15, Merge-Workgroup 16, and Split-Decision 17. The program 12 looks at each logical segment of the network in turn and groups all nodes into two work groups using as a basis the work groups listed in the workgroups list 26. The program 12 then makes a decision whether it would be worthwhile splitting the segment between two work groups and if it decides that there would be benefit in doing this, it enters a split suggestion in a segment-splits list 27.

As will become clear hereinafter, the level of sophistication of the programs 10, 11 and 12 (and, in particular, of program 10 in identifying global and local servers) depends on the depth of detail provided by the traffic data (elements 22). Thus, the traffic data may simply be based on level-2 packet information, that is, on the source and destination node addresses of message packets passed across the network with no attempt being made to look at higher level structuring contained in the data part of the packets. Alternatively, the traffic data may take account of such higher level structuring with a view to providing an indication as to whether packets passing to and from a particular node do so with the node acting in a server role or in a client role. In the absence of this more detailed form of tr