Realtime Event Classification for a Data Communications Network

1. Technical Field

The invention disclosed broadly relates to the extraction of information from large bodies of data for high speed communication facilities, and more particularly relates to realtime event classification for a data communications network.

2. Related Patent Applications

This invention is related to the copending patent application Ser. No. 08/024,575, filed Mar. 1, 1993, now U.S. Pat. No. 5,365,514 entitled "Event Driven Interface for a System for Monitoring and Controlling a Data Communications Network," by P. C. Hershey, et al., (now U.S. Pat. No. 5,365,514 issued Nov. 15, 1994) assigned to the IBM Corporation and incorporated herein by reference.

This patent application is related to the U.S. patent application Ser. No. 08/024,572, filed Mar. 1, 1993, U.S. Pat. No. 5,375,070, entitled "Information Collection Architecture and Method for a Data Communications Network," by J. G. Waclawsky, et al., now U.S. Pat. No. 5,375,070 issued Dec. 20, 1994 assigned to the IBM Corporation and incorporated herein by reference.

This patent application is also related to the U.S. patent application Ser. No. 08/024,563, filed Mar. 1, 1993, abandoned, entitled "Event Driven Interface for a System for Monitoring and Controlling a Data Communications Network," by P. C. Hershey, et al., assigned to the IBM Corporation and incorporated herein by reference.

This patent application is also related to the U.S. patent application Ser. No. 08/024,542, filed Mar. 1, 1993, entitled "System and Method for Configuring an Event Driven Interface and Analyzing Its Output for Monitoring and Controlling a Data Communications Network," by J. G. Waclawsky, et al., assigned to the IBM Corporation and incorporated herein by reference.

This patent application is also related to the copending U.S. patent application Ser. No. 08/138,045, filed Oct. 15, 1993, entitled "System and Method for Adaptive, Active Monitoring of a Serial Data Stream Having a Characteristic Pattern," by P. C. Hershey, et al., assigned to the IBM Corporation and incorporated herein by reference.

3. Background Information

The above cited Hershey, et al. patent application describes the Event Driven Interface which is a programmed device to perform pattern recognition operations on the serial data streams in a data communications network. The Event Driven Interface categorizes various patterns identified in the serial bit stream and increments designated counters at the output at the Event Driven Interface, in accordance with a preprogrammed set of control vectors.

It would be useful to perform simultaneous network analyses and monitoring operations by capturing selection significant segments of the serial bit streams off the data communications network, thereby enabling the categorization of the counting of events based upon prespecified categories.

It is therefore an object of the invention to perform realtime event classification on a data communications network, in an improved manner.

It is another object of the invention to identify a plurality of categories of bit patterns from the serial bit stream of a data communications network, simultaneously.

These and other objects, features and advantages are accomplished by the invention disclosed herein. The invention is an extension to the Event Driven Interface concept, by augmenting the Event Driven Interface to include an additional component which identifies bit pattern segments which are significant for the selection of categories of information in the serial bit stream. In accordance with the invention, the Event Driven Interface extension will process the serial bit stream in parallel with the processing of the serial bit stream by the basic Event Driven Interface, in order to identify selection significant bit patterns. Selection significant bit patterns can include for example the identity of the source of messages on the data communications network. For each different transmitting node on the data communications network, a separate array of event vector counters can be provided. As each specific source node is identified for a given data frame, for example, a separate counter can be provided to receive the count outputs of the base Event Driven Interface. This example application would be useful for establishing billing information, for monitoring node activity, or for problem determination related to the source node in the network.

By having a plurality of event vector counters, one for each preprogrammed category whose pattern is to be identified by the EDI extension, global billing can be performed for all of the source nodes in the network. In addition, an overall network design analysis can be performed for all of the source nodes in the network. In addition, capacity planning can be performed for all of the source nodes in the network. In addition, network tuning and optimization activities can be performed using the plurality of event vector counters, in accordance with the invention.

Other types of categories into which the plurality of event vector counters can be associated includes all of the destination addresses in the data communications network, or all of the packet sizes in the data communications network, or the respective account numbers in the data packets.

Another feature of the invention is the inclusion of an activity bit which would be associated with each respective event vector counter in the plurality of counters receiving outputs from the base Event Driven Interface. The activity bit would be turned on whenever a particular counter was accessed. If the artificial intelligence analysis system making use of the event vectors, interrogates the plurality of counters on a periodic or infrequent basis, then only those event vector counters which had activity, as indicated by the activity bit being on, need be copied to the analysis program. This feature minimizes the Event Driven Interface event vector information which needs to be returned to the expert system analyzer.

Another feature of the invention is a least recently used feature for the event vector counters. If there are a limited number of event vector counters, then one way to implement a least recently used feature is to assign each counter to the top of a stack at the moment it is used or incremented. Then as a given counter ages with time, its relative priority diminishes as it proceeds down to the bottom of the stack and if the counter has no activity by the time all of the rest of the counters have been used, then that counter loses its identity.

A corollary to this feature would be the most frequently used feature where each respective event vector counter has associated with it a count of the total number of accesses that it has had during a session. The event vector counter having the most current accesses is placed at the top of a stack. There is only room for the top N counters and therefore those categories which are not as frequently counted will not have a corresponding counter available in the plurality of counters. Of course, with both the least recently used feature and with the most frequently used feature, there will be a periodic dumping of the contents of the counters to the expert system analyzer and a resetting of each respective counter so that all categories of activities in the data communications system will have an opportunity to register their counts in the plurality of event vector counters.

Another feature of this invention includes the capability to detect and classify multiple characteristic data patterns that can occur simultaneously on a communications network. These characteristic data patterns represent events of interest for network management. These events may be station specific or network specific. Examples of such events include parameters required for performance analysis, fault tolerance, and security. This invention classifies the detected events simultaneously as they occur on the wire. Therefore, realtime event classification is possible.

These and other objects, features and advantages will be more fully appreciated by reference to the accompanying figures.

FIG. 1 is a schematic diagram of the Event Driven Interface and the Event Driven Interface extension, with a plurality of event vector counters, in accordance with the invention.

FIG. 2 illustrates a more detailed diagram of the base Event Driven Interface and the extension Event Driven Interface, for an example of categorizing billing information for a plurality of source nodes in the data communications network.

FIG. 3 illustrates a hardware architecture for simultaneous event classification.

The problem is how to simultaneously compile several event vectors corresponding to several types of events or categories of events using the Event Driven Interface.

Attached is a FIG. 1 which shows a modification to the Event Driven Interface (EDI) structure, which is described in the companion the above cited patent application Ser. No. 08/024,575. The counters 10 for the EDI 12 are expanded in this invention, to have several levels of counters. Each level of counters will correspond to one event category, such as communication between a specified pair of nodes, or traffic classified as sizes, or traffic originating from a particular node, or traffic destined to a particular node, etc. Each of those categories of traffic on the network can have corresponding event vectors compiled for them in separate levels of counters as is shown in the figure.

In order to accomplish this, additional branches of the tree in EDI are provided which correspond to each respective category of events. The output of the EDI extension portion 12' is an address which enables the writing to a particular level in a multiple level of counters for each respective category of events to be recorded. In this manner, a variety of event categories can have corresponding event vectors compiled simultaneously for a network.

One feature of the system shown in the attached figure is the changed bit column which allows only those levels of counters which have had a change in their contents since the last transmission to the expert system, to be forwarded during the current monitoring interval.

Another feature of the system shown in the attached figure is the formulation of the address at the output of the extended EDI 12', which can be by a hashing algorithm FSM loaded into the EDI to work off patterns in the bit stream or by another form of bit pattern generation which will provide a more efficient addressing technique for addressing a relatively sparse matrix of data in the layers of counters 10, addressing algorithms to particular counter levels.

Still another feature of this system in the attached figure is the provision of a least recently used indication for respective layers of counters, so that after an extended period of monitoring, only those counters which have had the highest corresponding measured activity, will be recognized and forwarded to the expert system.

FIG. 2 illustrates an example of the base Event Driven Interface and the extension Event Driven Interface used in categorizing billing information by the number of frames sent (number F) and the number of bytes sent in each frame (bytes) by devices in a four node network. In this example, device addresses for the source nodes are mapped by the extension Event Driven Interface into four category locations 0, 1, 2 and 3 in the random access memory.

Still another feature of this system is simultaneous event classification. Simultaneous event classification (SEC) refers to the collection of two of more events during the same measurement time interval for individual network station addresses. A measurement time interval (MTI) is defined as the period of time over which data is collected. Examples include collecting separate performance data for each node within a given communication network (i.e., frame count F{1} originated from node 1 and frame count F{2} originated from node 2). The event F.sub.-- {i}, in this case, would correspond node address i that is identified by the source or destination address field of the frame format of the protocol. This example applies to communications protocols such as FDDI [1], FDDI-2 [2], token ring [3], DQDB [4], token bus [5], and CSMA/CD [6].

Consider the example of a 16 Mbps IEEE 802.5 token ring network. A single token ring network can have at most 250 attached stations. The ICA device as previously disclosed can collect data for a network with 250 attached stations and can compute a performance measure for the overall network. However, this ICA device does not distinguish between individual stations. Herein we extend the ICA methodology to classify events by their source or destination address. Thereby, the ICA can collect performance data for each individual station in addition to collecting data for the network as a whole. Important applications for such an extension include billing, fault isolation, and security.

A hardware architecture for SEC appears in FIG. 3. This architecture differs from that previously disclosed. The protocol, pattern recognition FSMs, and the first bank of counters operate exactly as described in above cited patent application Ser. No. 08/024,563 and the copending U.S. patent application entitled "Realtime Addressing for High Speed Serial Bit Stream" by P. C. Hershey, et al., Ser. No. 08/188,167, filed Jan. 26, 1994 on the same day as this application. We enhance this architecture by adding an address finite state machine (FSM) 30, an arithmetic logic unit (ALU) 32, a Pattern Store memory 34, and a second bank of counters. The address FSM recognizes source and/or destination addresses using the same RAM lookup table procedure described in the two above cited copending patent applications for pattern recognition. When a particular address is recognized, the address FSM produces an output symbol that serves as an enable to a specific bank (or region) of Pattern Store memory. This memory region is specifically dedicated to storing performance parameters detected for only that address. The Pattern Store memory map is dynamically reprogrammable. When the next address becomes active, the address FSM enables a different region in Pattern Store memory so that performance parameters specific to that address can be stored there. If the original address is detected again, the Pattern Store memory outputs the stored parameter counts for that address to the ALU. When a different address is recognized by the address FSM, the contents of the active counter bank is dumped to the ALU where the counts for the performance parameters are added to those previously accumulated. After the addition, the contents of the ALU are again stored in the Pattern Store until the address is recognized again. At the end of the time interval, the contents of the Pattern Store memory are dumped to the performance FSM for analysis. We provide two banks of counters in order to maintain realtime counting. Otherwise, during the time when the counters are dumping to the ALU, we would have to stop counting new parameters. We alternate between counter banks when addresses change. The address FSM detects this changes and controls the switching between counter banks.

For a single token ring network, a maximum of 250 stations can be active. Therefore, this architecture would require 250 memory partitions. Present technology includes 10 ns access time static RAMs organized as 256K by 16. Therefore, we would have 1K locations per address to store parameters values. This is more than adequate to store parameter counts for any of the performance measures identified herein.

The actual procedure to handle the changing set of addresses could be a hashing algorithm described in A. V. Aho, J. E. Hopcroft, J. D. Ullman, "Principles and Practice of the Design and Analysis of Computer Algorithms," Addison-Wesley, Reading, Mass. 1974. Aho et al. provides such a hashing scheme. This algorithm permits the mapping of elements from a universal set (e.g. the set of station addresses) to Pattern Store memory blocks 0 through M-1, where M=256 for our example. Aho shows that the computational complexity to insert n new addresses is order n (e.g., O(n)). Because the number of station addresses is unknown for a given data collection time interval, we must construct a number of different hash tables T.sub.-- {0}, T.sub.-- {1}, T.sub.-- {2}, . . . , and initially pick one of suitable size. If the number of station addresses exceeds M, we reconfigure the Pattern Store memory with a new hash table of depth 2M and rehash the elements of the original hash table to the new hash table. Alternative hashing algorithms specifically for address lookup in computer networks are presented by R. Jain, "A Comparison of Hashing Schemes for Address Lookup in Computer Networks," IEEE Trans. Commun, Vol. 40, No. 10, October 1992, pp. 1570-1573.

This new architecture can be extended to multiple networks by using the ICA at a bridge, router, or hub. For these cases the number of addresses will increase; however, the number of recognizable performance parameters is less do to limited visibility to the data stream for these devices as compared with a station on the network.

Although a specific embodiment of the invention has been disclosed, it will be understood by those having skill in the art that changes can be made to that specific embodiment without departing from the spirit and the scope of the invention.