 |
Claims  |
|
|
What is claimed is:
1. A method of ascertaining topology features of a network using a
processing system, the network comprising a plurality of sub-networks,
spanning devices interconnecting the sub-networks, and stations
operatively interconnecting the sub-networks, wherein at least some of
said interconnections are not provided as inputs to said processing
system, said network carrying message packets having source information
indicative of a source from which said message packets had originated and
destination information indicative of a destination to which said message
packets are destined, said message packets being carried on and between
said sub-networks and defining traffic carried on and between said
sub-networks, said stations being operative to do at least one of i)
transmit traffic to at least one sub-network, and ii) receive traffic from
at least one sub-network, the method comprising the steps of:
monitoring the traffic on at least a number of said plurality of
sub-networks to derive data relating to at least an amount of traffic
carried on and between said number of sub-networks so monitored and source
of the traffic carried on and between said sub-networks so monitored; and
processing the data to determine topology features of the network that have
not been provided as inputs to said processing system, said topology
features including the interconnection of each station to at least one
sub-network and the interconnection of sub-networks to each other and to
each of the spanning devices.
2. The method according to claim 1, further comprising the steps of:
ascertaining to which sub-network a selected station is connected, wherein
the source information serves to identify those stations from which the
message packets originate, the monitoring step determining the amount of
traffic originating from the selected station that is carried on each
sub-network, the processing step determining the sub-network carrying a
largest amount of traffic from the selected station, said sub-network
defining the sub-network to which the selected station is connected
thereto.
3. The method according to claim 2, further comprising the steps of:
ascertaining to which sub-networks the stations are connected, wherein the
source information serves to identify those stations from which the
message packets originate;
and repeating the step of claim 2 for each station with the monitoring step
being carried out for substantially all stations concurrently.
4. The method according to claim 1, further comprising the steps of:
(a) providing association information enabling the source information to be
used to identify whether the message packet having the source information
originated from at least one station connected to a first sub-network (Y);
and
(b) said monitoring step being operative to monitor the traffic on a second
sub-network (X) and on each sub-network of a group (R) of sub-networks
comprising substantially all sub-networks other than the first and second
sub-networks, thereby deriving data relating to the amount of traffic from
at least one station connected to the first sub-network (Y) that is
carried on the second sub-network (X) defining traffic (T.sub.1).sub.x and
carried on the sub-networks of group (R) taken together defining traffic
(T.sub.1).sub.R, using the association information;
said processing step being operative to use the data to compare the amounts
of traffic (T.sub.1).sub.x and (T.sub.1).sub.R, the processing step
determining whether one of the spanning devices is connected between the
first sub-network (Y) and second sub-network (X) when the larger of the
amounts of (T.sub.1).sub.x and (T.sub.1).sub.R is (T.sub.1).sub.x.
5. The method according to claim 1, further comprising the steps of:
(a) providing association information enabling:
(i) the source information to be used to identify whether the message
packet having the source information originated from at least one station
connected to a first sub-network (Y); and
(ii) the destination information to be used to identify whether the message
packet has a destination for at least one station connected to one of the
sub-networks other than a second sub-network (X); and
(b) said monitoring step being operative to monitor the traffic on the
second sub-network (X) and on each sub-network of a group (R) of
sub-networks comprising substantially all sub-networks other than the
first and second sub-networks, thereby deriving data relating to the
amount of traffic from at least one station connected to the first
sub-network (Y) and having a destination other than stations connected to
the second sub-network (X) that is carried on the second sub-network (X)
defining traffic (T.sub.2).sub.x and carried on the sub-networks of the
group (R) taken together defining traffic (T.sub.2).sub.R, using the
association information;
said processing step being operative to use the data to compare the amounts
of traffic (T.sub.2).sub.x and (T.sub.2).sub.R , the processing step
determining whether one of the spanning devices is connected between the
first sub-network (Y) and the second sub-network (X) when the larger of
(T.sub.2).sub.x and (T.sub.2).sub.R is (T.sub.2).sub.x .
6. The method according to claim 1, wherein the spanning devices used in
the network do not act perfectly to block message packets with a
destination to one station connected to a different sub-network from
passing through at least one of said spanning devices to the different
sub-network, the method further comprising the step of:
(a) providing association information enabling:
(i) the source information to be used to identify whether the message
packet having the source information originated from one of the stations
connected to a first sub-network (Y); and
(ii) the destination information to be used to identify whether the message
packet having the destination information has a destination for one of the
stations connected to the first sub-network (Y); and
(b) said monitoring step being operative to monitor the traffic on a second
sub-network (X) and on each sub-network of a group (R) of sub-networks
comprising substantially all sub-networks other than the first and second
sub-networks, thereby deriving information indicative of the amount of
traffic from one station connected to said first sub-network (Y) and
having a destination to one station connected to the first sub-network
(Y), that is carried on the second sub-network (X) defining traffic
(T.sub.3).sub.x and carried on the sub-networks of group (R) taken
together defining traffic (T.sub.3).sub.R, using the association
information;
said processing step being operative to use the data to compare the amounts
of traffic (T.sub.3).sub.x and (T.sub.3).sub.R, the processing step
determining whether one of the spanning devices is connected between the
first sub-network (Y) and the second sub-network (X) when the larger of
(T.sub.3).sub.x and (T.sub.3).sub.R is (T.sub.3).sub.x.
7. The method according to claims 4, 5 or 6, wherein said processing step
derives the amount of traffic sourcing from the first sub-network (Y) that
is carried on the sub-networks of the group (R) by adding together the
traffic amount for each sub-network of the group (R) without regard to any
duplication that results from the same message packet being monitored on
more than one sub-network of the group.
8. The method according to claim 4, wherein said association information
further enables the destination information to be used to identify the
sub-network having the station to which the packet is destined connected
thereto, said processing step deriving the amount of traffic sourcing from
at least one station connected to the first sub-network (Y) that is
carried on the sub-networks of the group (R) taken together, by performing
the following steps:
(a) determining an amount of sub-network traffic is from at least one
station connected to said first sub-network (Y), that is also destined for
at least one station connected to the first sub-network (Y) and for at
least one station connected to said second sub-network (X), for each of
the sub-networks of group (R), and
(b) adding together the amounts of sub-network traffic so determined in
step (a) of this claim 8 for substantially all the sub-networks of group
(R).
9. The method according to claims 5 or 6, wherein the processing step
derives a relevant amount of traffic sourcing from at least one station
connected to the first sub-network (Y) that is carried by the sub-networks
of group (R) taken together by performing the following steps:
(a) determining for each sub-network of group (R), which sub-network
traffic is from at least one station connected to the first sub-network
(Y), that is also destined for at least one station connected to the first
sub-network (Y) and for at least one station connected to the second
sub-network (X), and
(b) adding together the relevant sub-network traffic components so
determined for substantially all the sub-networks of group (R).
10. The method according to claims 4, 5 or 6, wherein said association
information further enables the source information to be used to identify
from which station in the first sub-network (Y) the message packet
including said source has originated, the monitoring and processing steps
for determining whether one of the spanning devices is present between
said first and second sub-networks (Y,X) being carried out in respect of
traffic from each station connected to the first sub-network (Y) taken
separately.
11. The method according to claims 4, 5, or 6, further comprising the step
of:
ascertaining whether two sub-networks of a network are directly connected
by a bi-directional spanning device, wherein steps (a) and (b) of each of
the respective claims 4, 5 or 6 are repeated for traffic from at least one
station connected to each of the two sub-networks.
12. The method of claims 4, 5, or 6 wherein steps (a) and (b) of each of
the respective claims 4, 5 or 6 are carried out for a pairing of a set of
sub-networks for substantially all sub-networks of the network or the
portion thereof under consideration, thereby determining which of the
sub-networks are interconnected by spanning devices.
13. The method according to claim 1, wherein said monitoring step involves
the generation of traffic matrices for each sub-network.
14. The method according to claim 1, wherein said monitoring step involves
sampling the traffic carried on the sub-networks, said processing step
effecting its determination by using hypothesis testing.
15. The method of claim 1, wherein said step of monitoring the traffic to
derive data relating to the amount and source of the traffic does not
suspend i) the transmission of message packets to any station, and ii) the
reception of message packets from any station.
16. The method of claim 1, wherein said step of monitoring the traffic to
derive data relating to the amount and source of the traffic does not
involve special message packets dedicated to providing information related
to the topology features of the network such that the special message
packets are carried solely between spanning devices. |
|
 |
|
 |
Claims |
|
|
|
Description |
|
|
FIELD OF THE INVENTION
The present invention relates to a method of ascertaining topology features
of a network of the type comprising a plurality of sub-networks, spanning
devices interconnecting the sub-networks, and stations operative to source
and/or sink traffic to/from the sub-networks, the traffic being in the
form of discrete message packets each including source and destination
information.
BACKGROUND OF THE INVENTION
Networks of the aforesaid type are well known, their spanning devices
serving to isolate local traffic (that is, traffic sourcing from, and
destined for, stations on the same sub-network) to the sub-network
concerned, at least to some degree. Examples of such networks are:
(a) bridged Ethernets where stations, identified by Ethernet addresses, are
connected to sub-networks (also termed logical segments) which are
interconnected by spanning devices in the form of bridges operating at
level 2 of the seven-layer OSI Reference Model; and
(b) Internet networks where stations identified by "ip" addresses are
connected to "ip" sub-networks which are interconnected by spanning
devices in the form of routers or gateways operating at level 3 of the
seven-layer OSI Reference Model.
Knowledge of topological features of such networks (for example, the
connection arrangement of stations to sub-networks and the interconnection
of sub-networks by spanning devices) is of importance in monitoring and
optimizing the performance of the network and in planning for its
expansion to cope with increased demand. However, such knowledge is
frequently difficult to ascertain, particularly with large networks. For
example, keeping up-to-date plans of the network by recording every change
made, is not only time-consuming but is, in reality, a virtually
impossible task to carry through with complete accuracy; in addition, such
plans can only indicate the intended connection state of the network and
cannot take account of the failure of network elements such as the simple
disconnection of a station from its sub-network. Physical inspection of a
network to ascertain its topology is also very difficult since much of the
network may be hidden beneath flooring or located at remote sites.
In the case of a network made up of a single sub-network, it is possible to
ascertain which stations are connected to the subnetwork simply by
monitoring the traffic on the sub-network; all stations sourcing traffic
are obviously connected to the sub-network as there is no other source of
traffic outside the sub-network. However, where the network comprises
several sub-networks interconnected by spanning devices, it is no longer
possible to make such simple deductions as traffic appearing on any one
particular sub-network might have originated on another sub-network.
SUMMARY OF THE INVENTION
It is an object of the present invention to provide a relatively simple
method for ascertaining topology features of a network that includes a
plurality of sub-networks.
The present invention provides a method of ascertaining topology features
of a network of the aforesaid type. The traffic on some of the
sub-networks is monitored to derive data related to the amounts and
origins of the traffic. The data is then processed to determine the
topology features of the network.
The monitoring step utilizes a monitoring device on each sub-network
concerned. Such a device may be a stand-alone device or part of a spanning
device or station connected to the sub-network. Each monitoring device is
preferably operative to collect both source and destination information in
respect of traffic on the sub-network and this information is then used to
generate a partial traffic matrix, that is, a correlation between source
stations and destination stations for the traffic seen on the sub-network
concerned. Preferably, therefore, the data passed by the monitoring step
to the processing step will be in the form of partial traffic matrices for
all the relevant sub-networks. However, it should be understood that the
processing step, depending on what topological features are to be
ascertained, may not require all the data contained in such partial
traffic matrices and the present invention should therefore not be taken
as limited to the provision of the necessary data to the processing step
in the form of partial traffic matrices.
The source information in each message packet will generally only provide
an indication of the originating station, although in certain networks,
sub-network identification is also carried in the source information. In
the former case, the method of the present invention can be used to
ascertain to which sub-network a selected station is connected. This is
achieved by having the monitoring step determine the amount of traffic
originating from the selected station that is carried by each said
sub-network. The processing step then determines the sub-network carrying
the most traffic from the selected station. This sub-network is taken as
the one to which said selected station is connected. This process can then
be repeated for each station to build up a complete picture of the
connection of stations to sub-networks.
The method of the present invention can also be used to ascertain whether a
first sub-network is directly connected by a spanning device to a second
sub-network; this is done by comparing, for some or all of the components
of traffic originating on the first sub-network, the amounts of that
traffic seen on the second sub-network with the amounts of that traffic
seen on all the other sub-networks (that is, other than the first and
second sub-networks). In particular, three different methods for testing
for a spanning device will be described in detail herein.
In a preferred implementation of the invention, traffic information on each
sub-network is collected locally by a sampling monitoring device which
transmits sampled data back to a central processing station. The
processing station derives partial traffic matrices for all the monitored
sub-networks and then processes the data contained in the traffic matrices
in accordance with the methods of the invention. In carrying out this
processing, the processing station effects comparisons between traffic
flows by using hypothesis testing in view of the sampled nature of the
data provided to it.
A suitable sampling monitoring device for use in implementing the method of
the present invention is described and claimed in our co-pending European
Patent Application No. 90310699.5 filed 28th Sep. 1990.
The partial traffic matrices used by the processing station for deriving
topology features of the network can, of course, be obtained in other ways
such as, for example, by monitoring devices which derive and store these
partial traffic matrices themselves, the partial traffic matrices then
being collected and passed to the processing station.
BRIEF DESCRIPTION OF THE DRAWINGS
A method, according to the invention, of ascertaining topology features of
a network will now be described by way of non-limiting example with
reference to the accompanying diagrammatic drawings, in which:
FIG. 1 is a block diagram of one network in which a processing station and
a number of sampling monitoring devices have been connected to form a
network monitoring system capable of implementing the method of the
present invention;
FIG. 2 is a diagram illustrating the general form of a data packet
transmitted over the FIG. 1 network;
FIG. 3 is a block diagram of a sampling monitoring device of FIG. 1;
FIG. 4 is a flow chart illustrating the main interrupt service routine run
by a controlling microprocessor of the FIG. 3 device;
FIG. 5 is a diagram illustrating the main data structures utilized by the
processing station of FIG. 1 in processing data from the sampling
monitoring devices;
FIG. 6 shows an example of a partial traffic matrix for a sub-network of
the FIG. 1 network;
FIG. 7 is a flow chart illustrating a main program run by the processing
station;
FIG. 8 is a flow chart illustrating an interrupt service routine which is
run by the processing station, upon receipt of data from a sampling
monitoring device, in order to build up partial traffic matrices;
FIG. 9 is a flow chart illustrating a "station-allocation" routine called
by the FIG. 7 program to determine the association between stations and
sub-networks of the FIG. 1 network;
FIG. 10A is a diagram illustrating possible traffic flows in the network
between two sub-networks Y and X when they are connected by a bridge;
FIG. 10B is a diagram similar to FIG. 10A but for the case when no bridge
inter-connects sub-networks Y and X;
FIG. 11 is a diagram illustrating possible leakage traffic flows from
sub-network Y when no bridge inter-connects sub-networks Y and X;
FIG. 12 is a flow chart illustrating a "tests for bridges" routine called
by the FIG. 7 program to determine which pairs of sub-networks are
inter-connected by bridges;
FIG. 13 is a flow chart illustrating a "first test for a bridge"
sub-routine called by the FIG. 12 routine; and
FIG. 14 is a flow chart illustrating the derivation of a site traffic
matrix.
DETAILED DESCRIPTION OF THE INVENTION
FIG. 1 illustrates a typical local area network in which a plurality of
stations 11, 12, and 13 are interconnected via cable segments 10A, 10B,
and 10C. The network is divided into three sub-networks by bridges
(spanning devices) 14 that connect respective ones of the cable segments
10B, 10C to the cable segment 10A. As is well known in the art, the
bridges serve to filter traffic passing between the network segments, such
that messages originating from a particular segment and destined for a
station on the same segment (local traffic) are not passed through the
bridge or bridges 14 to the other segments whereas messages originating in
one segment and intended for another one (non-local traffic) are allowed
across the bridge. The operation for such bridges is generally imperfect
and some local traffic will usually `leak` through the bridges.
In the illustrated local area network, messages between the stations 11, 12
and 13 are transmitted in the form of packets that are broadcast over the
network. Typically a packet will have the form illustrated in FIG. 2 with
a packet header 15 containing a source address (the address of the station
sending the packet) and a destination address (the address of the station
intended to receive the packet), and an information field 16 containing
the data to be passed to the receiving station and normally including
error checking codes. Depending on the particular packet format being
used, other fields may also be present; thus, for example, there may be a
CRC (cycle redundancy check) field covering both the packet header and
information field.
The FIG. 1 network may, for example, be an Ethernet network well known to
persons skilled in the art.
The network of FIG. 1 is arranged to be monitored by a network monitoring
system comprising a plurality of monitoring devices (stations 12) and a
central processing station 13. Each of the monitoring devices is
associated with a respective one of the sub-networks of the network. As
will become clear below, each monitoring device is operative to randomly
sample the packets on its associated sub-network and transmit data on the
sampled packets back to the processing station 13 for processing and
analysis.
The form of each monitoring device is illustrated in FIG. 3. The device
comprises a network interface 20, a microprocessor 21, and ROM
(non-volatile, pre-programmed memory) and RAM (re-writable memory) units
22 and 23 respectively. These units 20 to 23 are all interconnected via
address, data and control buses 27, 28 and 29 respectively. The network
interface 20 is operative to carry out all the low level functions
necessary to interface the monitoring device of FIG. 3 to the network
cable 10 and to pass received packets to a receive queue, in the form of a
FIFO (First In First Out) buffer 25 in RAM 23. The network interface is
further operative to transmit packets held in a transmit queue, formed by
a FIFO buffer 26, in RAM 23. The network interface 20 thus constitutes
packet receive means and packet transmit means for the monitoring device.
In the present example, the network interface 20 is arranged to receive
all packets regardless of their destination address contained in the
packet header. Furthermore, the network interface 20 is operative to pass
only the header portion 30 of each received packet to the receive FIFO
buffer 25.
The network interface 20 is arranged to operate in co-ordination with the
microprocessor controller 21 and, in particular, informs the
microprocessor 21 each time a packet header is inserted into the receive
FIFO buffer 25, by means of a suitable interrupt control signal.
The network interface 20 also contains various counters 24 which hold a
number of counts including the total number of packets received, the
number of packets received which according to their CRC field are in
error, the number of packets received below the minimum accepted length
(RUNT packets), and the number of packets received above the maximum
accepted length (JABBER).
Implementations of the network interface 20 for particular network
protocols are well known in the art. Thus, for example, for an Ethernet
network, the network interface 20 may be constituted by Intel Corporation
chips 82502, 82501, and 82586; in this case an appropriate microprocessor
constituting the microprocessor 21 is the Intel processor 80186.
The ROM 22 holds the programs run by the microprocessor 21 and also a table
of random count values predetermined according to an exponential
distribution.
The processor 21 is operative to run a background program in which it does
nothing (i.e., an idling program). The main working program for the
processor 21 is an interrupt service routine which is called each time the
network interface 20 generates a processor interrupt to tell the processor
that it has stored a new packet header in the receive FIFO 25. The
interrupt service routine, which will be described in more detail below,
operates to randomly select a received packet header and form it into a
collected-data packet together with the current count values of the
counters 24. The random selection of received packet headers is effected
by utilizing the predetermined random counts stored in ROM 22. The
collected-data packet so formed is put into the transmit queue FIFO 26
and, in due course, is transmitted by the network interface 20 back to the
processing station 13. The header of each collected-data packet contains
as its source address the address of the monitoring device concerned while
the destination address is that of the processing station (alternatively,
a multi-cast address can be used to which the processing station is set to
listen).
A more detailed description of the operation of the monitoring device will
now be given with reference to FIG. 4 which is a flow chart of the
interrupt service routine run by the microprocessor 21. The microprocessor
21 will be taken to be in a state in which it is running its background
(idling) program and in which it has one of the random count values held
in an internal register (i.e., access to the first count value upon
switch-on of the monitoring device would be part of an initialization
routine). It will also be assumed that the receive and transmit FIFO
buffers 25 and 26 are empty.
On receiving a packet over the network cable 10, the network interface 20
passes the packet header to the receive FIFO buffer 25, updates its
counters 24 and generates an interrupt signal for the microprocessor 21.
On receipt of this interrupt, the microprocessor 21 executes the interrupt
service routine illustrated in FIG. 4. The first step 40 of this routine
carries out the normal house-keeping tasks associated with such routines
including saving the volatile environment parameters of the background
program and masking further interrupts.
Next, the microprocessor decrements the random count value held in its
internal register (step 41) and then checks the remaining value to see if
this has been reduced to zero (step 42).
If the count value is still greater than zero, the microprocessor 21
discards the head entry in the receive FIFO buffer 25 (step 43).
Thereafter, the microprocessor must check the receive FIFO buffer 25 to see
if any further packet headers have been entered into the buffer by the
network interface 20 during the preceding steps of the interrupt service
routine (step 44). Generally this will not be the case and the
microprocessor will then exit its interrupt service routine and restore
its background environment and unmask its interrupts (step 45). However,
in the event that the receive FIFO buffer 25 contains a further packet
header, the interrupt service routine will pass from step 44 back to step
41.
If during the test (step 42) carried out on the count value held in its
internal register, the microprocessor 21 finds that this count value has
been reduced to zero, the interrupt service routine will proceed to
generate a collected-data packet 31 in respect of the packet header at the
top of the receive FIFO buffer 25 (step 46). This collected-data packet 31
is assembled in the transmit FIFO buffer 26 from the received packet
header 30, the count values from the counter 24, the address of the
monitoring device (source address for the collected-data packet) and the
address of the processing station (destination address for the
collected-data packet header). After the collected-data packet has been
assembled, the microprocessor 21 flags the network interface 20 to
indicate that there is a packet ready for transmission. (The network
interface 20 will transmit the packet as and when it is able and cancel
the flag set by the microprocessor 21 once this has been done).
After completion of step 46 of the interrupt service routine, the
microprocessor fetches a new random count from ROM 22 and stores this new
random count in its internal register (step 47). The microprocessor then
proceeds to step 44 and running of the interrupt service routine proceeds
as previously described.
The size of the receive and transmit FIFO buffers 25 and 26 can be quite
small, for example, sufficient to hold only two or three entries. This is
possible with respect to the receive buffer 25 because in general the
interval between packets received by the network interface 20 will be
sufficient for the microprocessor 21 to run its interrupt service routine
and clear the top entry from the receive buffer. In any event, the
occasional overflowing of the receive buffer 25 is not of major
consequence since a missing packet will generally have minimal effect on
the statistical measurements being conducted by the network monitoring
system. This equally applies to the transmit buffer 26 where an overflow
is even less likely to occur as its entries are only in respect of the
randomly selected ones of the received packets.
The above-described implementation of the monitoring device does mean that
the count values included in a collected-data packet from the counter 24
may not be the count values current at the time that the relevant packet
was actually received by the network interface (this is because of the
possible delay in actually processing the packet header). However, again,
any discrepancy in this respect will be minor and will have minimal effect
on the validity of the statistically determined results produced by the
network monitoring system. Of course, it would be possible to design
circuitry which associated the count values present in counters 24 with
the header of each received packet. However, the added circuit complexity
needed to do this is generally not justified.
The data structures used to implement the receive and transmit FIFO buffers
25 and 26 in RAM 23 will be apparent to a person skilled in the art and
will therefore not be described herein. Furthermore, it will be
appreciated that although in the FIG. 3 embodiment the random selection of
incoming packets has been effected by storing predetermined random numbers
in ROM 22, these random numbers could alternatively be generated as and
when required by the processor 21 (although this is not preferred as it
places extra processor requirements on the microprocessor). Typically, the
random numbers are such as to give an average skip between selected
packets of ninety nine; other values may be more appropriate depending on
traffic density, sampling period and acceptable statistical error level.
The random selection of packets could be effected on a time basis rather
than on the number of packets received.
The collected-data packets sent out by the monitoring devices 12 over the
network are all received by the processing station 13 which stores these
packets and carries out subsequent processing and analysis.
The processing station 13 is, for example, constituted by a standard
workstation interfacing with the network through a network interface (not
shown) similar to the interface 20 of the FIG. 3 monitoring device 12.
Such a workstation will be provided in standard manner with RAM memory for
storing working data and program segments, ROM memory for permanent
storage of programs, a processor for processing data held in the RAM
memory in accordance with the programs, and various input/output devices;
none of these elements are illustrated or described herein as they are all
standard and well known to persons skilled in the art.
The processing station 13 carries out three main tasks, namely:
(1) generation of traffic matrices for each sub-network on the basis of the
collected-data packets received;
(2) the association of stations 11 with the various sub-networks using the
sub-network traffic matrices; and
(3) testing for the presence of bridge between all pairs of sub-networks by
using the sub-network traffic matrices.
The main data structures employed by the processing station 13 in carrying
out these tasks are illustrated in FIG. 5, the data structures being
created and maintained in the RAM memory of the station 13. The main data
structures are:
Input-queue 50 this is a queue of collected-data packets required by the
network interface of the station, each packet being temporarily held in
the queue pending processing;
Sub-Network List 51 this is a list of all the known sub-networks of the
network with each sub-network having a respective entry comprising a field
storing the sub-network identity SN-ID, a first pointer TM-POINTER, and a
second pointer S-POINTER;
Station List 52 this is a list of all the known stations 11 of the network
with each station having a respective entry comprising a field storing the
station identity S-ID, and a pointer NEXT-S POINTER. The first station to
be associated with any particular sub-network is associated with that
sub-network by setting the S-POINTER of the corresponding sub-network
entry in the sub-network list 51, to point to the appropriate station
entry in the station list 52. The association of further stations with the
same sub-network is achieved by using the NEXT-S POINTER of the last
preceding station associated with the sub-network to point to the entry of
the next station to be associated with the sub-network, thereby building
up a linked list of stations.
Sub-Network Traffic Matrix 53 This is an array formed for each sub-network
to hold the partial traffic matrix data for the sub-network. The traffic
matrix array relevant to a sub-network is pointed to by the pointer
TM-POINTER of the corresponding entry in the sub-network list 51. FIG. 6
illustrates a typical partial traffic matrix giving for each source
station/destination station pair, the number of packets carried by the
sub-network concerned in a given interval of time (the different stations
11 are here designated 11A, 11B, 11C . . . 11N).
Bridge List 54 This is a list of all the known bridges of the network with
each bridge having a respective entry comprising a field storing the
bridge identity B-ID, and a pair of fields for storing the identities
(SN-ID) of the sub-networks connected by the bridge.
Having outlined the main data structures used by the processing station 13,
a description will now be given as to how the station carries out its
tasks using these structures.
The main program run by the processing station 13 is illustrated in FIG. 7.
Upon start up of the program, a predetermined time period (e.g., 1 hour),
is timed (steps 60,61) during which the main program is idle but
collected-data packets are received by the processing station and
processed by an interrupt service routine to construct traffic matrices
for the sub-networks of the network. After time-out of the predetermined
time interval, the main program carries out statistical processing of the
traffic matrices (step 62) before proceeding to ascertain topological
features of the network, first of all by associating stations with
sub-networks using a "station allocation" routine (step 63), and then by
ascertaining where bridges are present in the network using the "tests for
bridges" routine (step 64); finally, the main program terminates.
FIG. 8 illustrates the interrupt service routine used to derive sub-network
traffic matrices from the received collected-data packets. The interrupt
service routine is called in response to the generation of an interrupt by
the network interface of the station 13 following the receipt thereby of a
collected-data packet and the storage of that packet in the input queue
data structure 50. Upon start-up of the interrupt service routine, the
normal housekeeping tasks of storing the volatile environment of the main
program and masking interrupts is effected (step 65). Next, the header of
the collected-data packet at the top of the input queue is examined (step
66). The source address contained in the header identifies the monitoring
device that generated the collected-data packet; indeed, on the assumption
that one monitoring device is associated with each sub-network of the
network, the address of the monitoring device also serves to identify the
associated sub-network. The monitoring device addresses are therefore used
either directly or indirectly as the sub-network identities SN-ID. By
examining the source address contained in the header of the collected-data
packet under examination, it is therefore possible to tell, by checking
against the sub-network list 51, whether the collected-data packet comes
from a known sub-network or whether the packet indicates the presence of a
previously unknown sub-network (step 67). If a new sub-network is
identified, then a new entry is made in the sub-network list 51 and a new
sub network traffic matrix array 53 is created (step 68); the TM-POINTER
of the sub-network entry is set to point to the new traffic matrix array
while the S-POINTER is set to null.
Thereafter, the interrupt service routine goes on to examine the contents
of the data field of the collected-data package under consideration (step
69). A check is made of the source station and destination station
addresses held in the data field to ascertain if either of these addresses
indicates the presence of a previously unknown station, that is, a station
not contained in the station list 52 (step 70). If a new station is
identified, then the station list 52 is updated (with its NEXT-S POINTER
set to null) and the existing sub-network traffic matrices 53 are extended
to include the new station (step 71).
Once the foregoing preliminary steps have been effected, the interrupt
service routine updates the traffic matrix 53 for the relevant sub-network
(as identified by the source address in the header of the collected-data
packet) by incrementing the entry for the source station/destination
station pair concerned (as indicated by the addresses held in the data
field of the collected-data packet)--see step 72.
Because of the sampled nature of the information provided by the monitoring
devices 12, the sub-network traffic matrices built directly using the raw
data from the monitoring devices 12, is preferably subject to statistical
processing. This processing is effected in step 62 of the main program at
the time-out of the sampling period. However, in order to carry out this
processing, it is necessary to record the total number of packets carried
by each sub-network during the sampling period. As explained above, the
total current packet count for a sub-network is included in the
information field of each co | | |
