Apparatus and method for displaying data communication network configuration after searching the network

Description Submit all comments and votes

COPYRIGHT NOTICE

A portion of the disclosure of this patent document contains material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction of the patent document or the patent disclosure, as it appears in the Patent and Trademark Office patent file or records, but otherwise reserves all copyright rights whatsoever.

BACKGROUND

1. Field of the Invention

This invention relates generally to the field of network diagnostic and management systems for communications network and a method and apparatus for displaying the results of database queries. More particularly the present invention relates to a method and device for determining the interconnection topology of a possible dynamic data communication network and for conducting communication between a network controller and the devices being controlled. The invention uses an unique method of querying a database which permits a graphical representation of the query results.

2. Background of the Invention

Relational database software is commercially available and suitable for various database functions where elements of the database are related to one another in some way. For example, such databases may be used to store information about a company's employees. Such information may include structural relationships concerning a person's position within a company's organization such as the person's department name or number, his supervisor, his subordinates, etc. Traditional relational database managers are able to readily produce, for example, a list of all of the people who report to a particular supervisor. Unfortunately, this method of displaying relational information is often not optimal for use by the database user. For example, although such information may provide a complete structural definition of a company's organizational structure, a graphical representation such as the typical organization chart is much more easily digested by the human user.

In an environment more closely akin to the preferred embodiment, it becomes even more evident that the typical database output format is inferior. Consider, for example, a major airline's telecommunication system for data communication used for processing reservations. The network's topology may be stored in a relational database containing entries which are related to one another by their interconnection. However, present relational database management software provides no mechanism for displaying that interconnection in a manner which is easily understood. Such software typically is only able to provide a sorted listing selected entries of the database.

Such a data communications network consists of nodes and links. The nodes are of different types and can offer different services. A node has a set of ports, and a set of time varying mappings are defined between these ports. Nodes are connected to form the network via links. Links connect the external ports of the nodes. The network derives its time varying character by virtue of the switching that takes place in the nodes. The network carries user data in logical pipes called channels. The channels are dynamic and the physical paths followed by the channel can change with time. The channel data flows change as a result of this switching. A multiplicity of channels may be carried by a link.

Each node receives the data on its ports and forwards it on some other port(s) depending on the switching state of the node. Data from a multiplicity of ports may be sent on a single port and vice versa.

For several reasons including network management it is required that network topology and channel flow changes can be represented, displayed, and effected in an efficient manner. In particular it is required from the network management perspective to effect configuration and switching changes, run diagnostic tests on the nodes and links and to receive unsolicited information regarding the spontaneous activity in the network. Several management entitles can simultaneously control the network. In such complex networks, it is also desirable to be able to display selected portions or views of the network in a graphical manner which is better digested by the user.

U.S. Pat. No. 4,613,946 to Forman describes a method and apparatus for generating hierarchical displays. But, only the entire tree, or the entire portion of a tree beginning at a selected root node may be selected for display.

Hitherto, in literature several search techniques have been proposed. Examples include Winston, P.H."Examples Involving Search", LISP, pp. 137-154, Addison-Wesley Publishing Co., 1984; Winston, P.H., "Exploring Alternatives", Artificial Intelligence, pp. 87-136, Addison-Wesley Publishing Co., 1984; and Aho A.V. et at., "Directed Graphs", Data Structures and Algorithms, pp. 198-229 Addison Wesley Publishing Co., 1982. However, these techniques use a model of the node where input on any port can go out on any other port. No attempt is made to model the internal characteristics of the node. Furthermore the time varying aspect of the internal switchings is not modelled.

There are elegant algorithms for directed tree searches, but in absence of internal node modelling, flood routing such as described in U.S. Pat. No. 4,399,531 to Grande et al. seems to be the norm for searching in undirected graphs.

Since different networks have different characteristics, an efficient and generic method is needed to handle all the various network types uniformly in order to:

determine the configuration topology based on services and channels;

determine routing between two nodes;

search the management entity controlling the node (management entity can change dynamically);

determine channels carried by the node; and

search for different services and node types.

A model for connectivity of these objects is needed and a search algorithm is also needed for obtaining routes and views of the connectivity of the network. The search algorithm should be capable of tracing logical connection pathways referred to here as channels in an efficient manner by pruning the undesired pathways.

The present invention satisfies these needs by utilizing a mechanism for modelling the internal switchings of a node as well as routing mechanisms to perform efficient searches in face of time varying dynamic behavior of the network, which is a characteristic of most data communication networks.

The present invention also provides a mechanism to display graphically a representation of a relational database and provides a mechanism for searching a complex computer network for a particular device within the network so that control over that device may be effected by a network controller. The search is conducted in an efficient manner which relies upon a network model which may simulate any element in a communication network.

SUMMARY OF THE INVENTION

It is an object of the present invention to provide an improved system for performing network diagnostics and maintenance in a complex data communication network.

It is an advantage of the present invention that a selective graphical representation of the contents of a relational database can be obtained.

It is an advantage of the present invention that portions of a data communications network may be viewed in a graphical representation.

It is another advantage of the present invention that by keeping track of aggregations which have been traversed in the search, the necessity of exploring all paths as in flooding can be avoided by exploring only deaggregations that have previously undergone aggregations.

Another advantage is obtained by identifying the global search context and separating it allowing the search token to carry only needed unique information and referencing the global context merely by pointing to it. This reduces the size of the search tokens which are replicated as the search proceeds.

It is a further advantage of the present invention to provide an efficient mechanism for determining a network's topology and for finding a particular device within a network.

These and other objects and advantages of the invention will become apparent to those skilled in the art upon consideration of the following description of the invention.

In one embodiment of the present invention, a method for providing a response to a query of a relational database, includes the steps of searching the database for entries which satisfy a search criterion; ascertaining a structural interrelationship between the entries which satisfy the search criterion; and generating a representation of the interrelationship between the entries which satisfy the search criterion, the representation being capable of conversion to a graphical representation of the structural interrelationship.

An apparatus, according to one embodiment of the present invention, for displaying a selected portion of information from a database includes a searching mechanism for searching the database for entries which satisfy a search criterion. An ascertaining mechanism ascertains a structural interrelationship between the entries which satisfy the search criterion. A generating mechanism generates a graphical representation of the interrelationship between the entries which satisfy the search criterion.

In another embodiment of the invention, a method of displaying a graphical representation of a selected portion of a network includes the steps of establishing a search criterion for selecting the portion of the network; conducting a search of the network for objects which meet the search criterion; storing selected information relating to the interconnection of objects within the network which meet the search criterion; and displaying a graphical representation of the interconnection of the objects.

Another method according to the present invention of searching a computer network for nodes satisfying a predetermined search criterion includes the steps of generating a token including a search criterion; placing the token on a first port of a node; determining whether or not the node has characteristics which satisfy the search criterion; transforming the token to a second port in accordance with a stored internal switch mapping which describes how the node's ports are mapped to one another; moving the token to an externally connected node using a stored external connection mapping which describes how the node is interconnected with other nodes; and recording a list of the nodes traversed as by the above steps which satisfy the search criterion.

In an embodiment of a routing manager for a diagnostics and control system for a communications network comprising interconnected nodes according to the present invention, the routing manager includes a relational database management system including a database containing information relating the nodes of the network to one another. Searching means are provided for conducting a search of the database for nodes satisfying a search criterion. A display displays an abstraction of a selected portion of the network based upon which of the nodes satisfy the search criterion.

The features of the invention believed to be novel are set forth with particularity in the appended claims. The invention itself however, both as to organization and method of operation, together with further objects and advantages thereof, may be best understood by reference to the following description taken in conjunction with the accompanying drawing.

BRIEF DESCRIPTION OF THE DRAWING

FIG. 1 is a diagram of a small portion of a communications network using the present invention.

FIG. 2 illustrates a device which may be controlled by two device controllers.

FIG. 3 illustrates channel flow determination.

FIG. 4A shows an example data communication network.

FIG. 4B shows a first OSI abstraction of the network of FIG. 4A.

FIG. 4C shows a second OSI abstraction of the network of FIG. 4A.

FIG. 4D shows a third OSI abstraction of the network of FIG. 4A.

FIG. 4E shows a fourth OSI abstraction of the network of FIG. 4A.

FIG. 5A shows an aggregation device model.

FIG. 5B shows a translation device model.

FIG. 5C shows a mesh or star device model.

FIG. 5D shows a deaggregation device model.

FIG. 5E shows a termination device model.

FIG. 5F shows an example of two aggregations and one translation used to build a more complex model.

FIG. 6A shows a model of a multiport modem.

FIG. 6B shows a model of a multiplexer.

FIG. 6C shows a model of a matrix switch.

FIG. 7 shows a generalized object representation of the network of a network.

FIG. 8 shows the object data structure of the present invention.

FIG. 9 shows the search token data structure of the present invention.

FIG. 10A represents an initial token generation.

FIG. 10B represents a first modification of the token.

FIG. 10C represents a second modification of the token.

FIG. 11 is a diagram of the routing manager interface to other processes of the present network controller.

FIG. 12 is a flow chart describing the initial token generation in the present invention.

FIG. 13 is a flow chart describing the initiation of a search in the present invention.

FIG. 14 is a flow chart of the internal mapping list handler of the present invention.

FIG. 15 is a flow chart of the recursive "EXPLORE" routine of the present invention which works on a single token.

FIG. 16A is the first sheet of a flow chart of the internal switching process of the present invention.

FIG. 16B is the second sheet of a flow chart of the internal switching process of the present invention.

FIG. 16C is the third sheet of a flow chart of the internal switching process of the present invention.

FIG. 17 is a flow chart of the external switching process of the present invention.

FIG. 18 illustrates the memory hashing scheme of the preferred embodiment.

FIG. 19A illustrates the search list representation of the network.

FIG. 19B illustrates the graphical representation of the network corresponding to the search list representation.

FIG. 20 is a flow chart for the process of converting the search list information into a graphical representation.

FIG. 21A shows a first abstraction of the network of FIG. 4.

FIG. 21B shows a second abstraction of the network of FIG. 4.

FIG. 21C shows a third abstraction of the network of FIG. 4.

FIG. 21D illustrates a fourth abstraction of the network of FIG. 4.

FIG. 22 is a hardware block diagram of the host utilized for the present invention.

DETAILED DESCRIPTION OF THE INVENTION

For purposes of this document, the terms `nodes` and `devices` are used synonymously. The term `Relational Database Manager` or `Relational Database Management System` or `RDBMS` refer synonymously to a system which stores elements of information which contain relationships to other elements of information. Typically, such information is stored as a table but this is not to be limiting since other mechanisms may be utilized.

Turning now to FIG. 1, an example communication network is shown from the perspective of the network management and diagnostic system. In this network, a network manager 10 is coupled to a communication processor 12 which is in turn coupled to a pair of device controllers 14 and 16. Device controller 14 is coupled to a modem 18 to communicate diagnostic data and modem 18 is communicating with a modem 20. Modem 20 is coupled to a DTE (Data Terminal Equipment) at one port and to other network components (not shown) at a second port). A Front End Processor (FEP) 24 is coupled to modem 18 for main channel data as well as several ports of a multiplexer (MUX, actually a multiplexer/demultiplexer) 26. The second device controller 16 is also coupled to one of the multiplexer ports of multiplexer 26. The aggregate output of multiplexer 26 is coupled to a second multiplexer 28. One of the ports of multiplexer 28 is coupled to a modem 30 which may be coupled to a second front end processor 32. Modem 30 communicates with a modem 34 which has one port connected to a DTE 36 and another port connected to other network components. Other ports of multiplexer 28 are coupled to DTE devices 40, 42, 44, 46, 48 and 50. Of course, this example network is intended only as an illustration of a portion of a typical communications network which may include hundreds or thousands of modems, multiplexers, etc.

Such communication networks are assembled from of modems, multiplexers, concentrators, and switches. The network topology connecting these devices is based on user implementation and could vary considerably. The network management system controls these devices by means of diagnostic channels which are usually multiplexed in some manner with the user data. This can be accomplished by using a low speed FSK side channel which is frequency division multiplexed with the main channel data or by allocating slots for diagnostic data in a multiplexer's data frame or other similar techniques. The diagnostic channels originate from Device Controllers (DC). The devices carry user data in addition to diagnostic data. The user data channels originate from the Front End Processors (FEP's). A typical network as shown in FIG. 1 includes such components. The network topology is stored in a database according to the present invention and updated as necessary to reflect connectivity changes such as additions or reconfigurations of the network.

Communication between the Network Manager (NM) and the device is a hierarchical process. The Network Manager 10 communicates with Device Controllers (DC) 14 and 16 which in turn control the devices. The NM `knows` the connectivity to the device (which devices are connected to which) from its database, but the identity of the DC is not known. This is because the assignment of the DC to a device changes dynamically based on the switching function of the device itself and intervening devices. So, it is required to determine this by querying the database. This query is conducted selectively, i.e., only with respect to the diagnostic channel.

In a network such as that of FIG. 1, it is not unusual for one device to be controlled by several device controllers as illustrated in FIG. 2. In this figure, a modem 60 is controlled by either device controller 62 or 64 depending upon the position of matrix switch 66.

Parallel activity may be permitted in network over the same channel, and therefore in order to allocate resources with the intent of avoiding collisions, topological orientation of the device with respect to other devices on the diagnostic channel is needed. This is accomplished by conducting searches on the diagnostic channel to find the upstream, downstream and codevices (devices that are on the same diagnostic tier).

A port on a device can carry a multiplicity of channels by virtue of aggregations at the device itself, or aggregations in the preceding devices. It is desirable to find the individual channels that are carried by the port at a given time. In order to accomplish this goal, searches are conducted until the aggregations have been deaggregated and the channel termination points (such as TNPs, DTEs and FEPs) have been reached in the search.

Turning now to FIG. 3, an example illustrating channel flow determination is shown in a portion of an example network including a front end processor 70 coupled to six ports of a multiplexer 72 with a device controller 74 connected to a seventh port of multiplexer 72. The aggregate channel from the multiplexer 72 is communicated by a modem 76 with a modem 78 to a multiplexer 80. For example, determine the channel flow on port 6 of mux 80, port 6 is traversed internally through the mux 80 to port 8 of the mux which in turn travels through the modems 78 and 76 to mux 72 port 8. Port 8 is then internally traversed to port 6 and then to port 6 of the FEP 70. This gives us the required solution for this example.

In order to find a route between two devices a search is conducted from the given device on the specified port until the target device is found. In conducting the search, it is not necessary to resort to flood routing which can be combinatorially explosive and consumes a great deal of overhead. Rather, the present invention takes advantage of the port mapping information in the internal switchings of the node to limit the scope of the search.

Sometimes it may be desired to find a particular type of device closest to a given device. The search is then conducted as usual but is terminated as soon as the given device type is found. For example in FIG. 3 one may want to determine the multiplexer closest to multiplexer 80. In this case the search will go through the modems 76 and 78 and find that it is multiplexer 72.

Of course, the actual searches are performed on the network model stored in the network manager in the form of the memory map of the network and/or the database information stored on disk, but this is not to be limiting since the search could also be performed on the actual network if desired in other embodiments.

The network topology is stored in the network manager's database. The changes in the network topology resulting from switching, and connection changes must be reflected in the database to perform the routing correctly. These changes are localized to the devices in which they occurred and do not produce ripple effects. This is achieved by storing only the local and minimal information with each device.

Turning now to FIG. 4, an analogy of the network abstraction to the OSI model is shown. In this example, FIG. 4a shows that an FEP 84 is coupled to a multiplexer 86 which communicates via modems 88 and 90 with multiplexer 92 which is coupled to a plurality of DTE devices 94, 96, 98 and 99. This communication hierarchy is analogous to the layered communication model known as the OSI (Open System Interconnection) model as illustrated in FIG. 4b, 4c, 4d and 4e wherein communication between FEP 84 and a DTE are carried out through mux 86 and mux 92 with the lower level communication of data bits carried out by modems 88 and 90.

As mentioned above, it is often desirable or necessary to obtain different views of the network based on the characteristics of the devices. The network can be abstracted at several different levels according to the present invention. This is analogous to the layered OSI model as shown in FIG. 4. On the highest level one can view the network to be a connection between FEP's and DTE's treating all the intervening devices transparent. On a lower level, muxes can be viewed but modems carrying the mux aggregate links may be deemed transparent. At the lowest level all the devices may be visible. Other abstractions are also possible.

Any of the devices forming a network such as that forming the network of FIG. 1 may be modeled according to the present invention as one of the model devices of FIG. 5. The aggregation mapping object 100 of FIG. 5a is used to model a device in which a plurality of ports map to a single port or vice versa such as a multiplexer or demultiplexer (usually collectively referred to herein as a multiplexer). A translation object 102 as shown in FIG. 5b is used where a single port maps to another single port such as a single port modem, a digital service unit, an encrypter, etc. The mesh object 104 of FIG. 5c is used to represent devices wherein any port may be mapped to any other port such as a packet switching node. FIG. 5d represents a deaggregation object which is simply the opposite of an aggregation. FIG. 5e represents a termination object which represents an end point such as a DTE. Terminations are also referred to herein as a leaf. These objects may be used singly or in combination to represent any device in a communication network. Several instances of mappings may be used in layers or other combinations to represent more complex devices. For example, FIG. 5f shows a more complex internal mapping represented by a combination of the basic mappings involving two aggregations and one translation.

Devices are represented in an abstract form as a "generalized object". The generalized object model is used here to build a network model. The object model generalizes the concept of a device to include all device types and operations. The generalized object model provides an uniform view of all devices regardless of their type and function.

The generalized object is comprised of a set of ports further classified in two sets: external ports, and internal ports. The external ports are the means by which an object connects to other objects in the network. Internal ports are means to characterize the switching nature of the object.

Internal switching mapping is the description of switching performed by the object. In other words it is the mapping of an object's set of external and internal ports onto itself. Several basic types of switching functions have been identified and shown in FIG. 5. An object may use one or all of these switching functions as well as many instances of them in mapping its ports.

The aggregation type of switching mapping maps a multiplicity of an objects internal and/or external port to a single external or internal port. The deaggregation type performs the opposite function. (A broadcast function may also be defined as a deaggregation type function which does not have a corresponding aggregation.) The translation type of switching mapping, maps an individual external or internal port to an individual external or internal port. The mesh or star type of switching mapping models a type of connection wherein every port in the star connection maps to every other port in the same star connection set.

Examples of these objects representing network components are shown in FIG. 6. FIG. 6a shows a multiport modem 110 with 4 DTE ports and a diagnostic controller port modeled as an aggregation object. FIG. 6b shows a multiplexer 112 having 4 DTE ports and a diagnostic port modeled as an aggregation object. FIG. 6c shows a matrix switch 114 modeled as a translation object. The generalized objects are connected to depict an abstract form of the network. These connections (links) are represented by external connection structures. External connection structure is the description of the connections of an object to other objects via the external ports. In other words it is the mapping of an object's external ports to the external ports of a multiplicity of other objects.

Turning now to FIG. 7, a network is modeled as described above using the object representation. A front end processor 120 has four ports coupled to a multi-port modem 122 which also has a port coupled to device controller 124. All ports of the FEP 120 are internally terminated (leaf). Modem 122 is modeled as an aggregation as is its corresponding multi-port modem 126 with which it communicates. FEP 120 also has a plurality of ports coupled to a multiplexer 128 also modeled as an aggregation object which is also coupled to a device controller 130. The aggregated port of 128 is coupled to a modem 132 which is modeled as an aggregation object. Modem 132 is coupled to a modem 134 which is modeled as an aggregation object. Modem 134 is coupled to a multiplexer 136 which is modeled as an aggregation object. A port of multiplexer 136 is coupled to a modem 138 which is also coupled to FEP 140. Modem 138 is modeled as an aggregation object. Modem 138 communicates with modem 144 which is also modeled as an aggregation object.

Mesh objects may be used to model objects when there is no knowledge of the internal mapping.

FIG. 7 shows another example network represented in the form of generalized objects and external connection structures. All the problems identified above, need a search mechanism. This mechanism uses a single algorithm, which operates on different parameters to solve the different problems identified. A few definitions are listed below:

Search--A search is defined to be the traversal of the objects in the network graph according to some criteria. The representation mechanism in the search algorithm is a search token. A search is thus a restricted flow of tokens in the network or network model.

Search Token--A search token specifies the object, port, and the extent that is to be searched and it points to a search context (defined below). The token also carries with it the history of every aggregation until the time every aggregation is balanced by a corresponding deaggregation in the search path. The search token specifies the pathways and objects that are to be traversed. The search is completely specified by a list of search tokens.

Search Context (Search Criterion)-- There is also some global context in which the search is to be undertaken. This context specifies which of the objects that are encountered in the process of searching are to be remembered, when the search is to be stopped, direction and view in which the search is undertaken. In general, this can relate to any of the attributes of the nodes or there connectivity and may be similar or identical to the types of criteria generally searchable in a relational database.

Transcription-- The process by which a token notes which nodes have been visited which satisfy the search criterion.

The search in the above framework can be thought of as a restricted flow of search tokens in the network graph. An object receives a search token on one of its external ports and operates upon it with the translation, aggregation, deaggregation and star operations possibly many times until the token(s) appear on its external port(s). It then forwards the resulting search token(s) to the multiplicity of the objects connected to this object by its external ports.

As the search tokens flow through the graph, the token list is updated with the resulting tokens. As the tokens flow in the network graph the visited objects which meet the search context are remembered (transcripted) in another list called search list, if it is required by this token's search context. A token is removed from the token list if the object that it refers to does not present any connections or if the end condition for this token has been met.

A search is said to be completed when either the token list has become empty in which case there is nothing more to be searched or the end condition for the search specified by the search context has been met in which case remaining tokens need not be pursued.

The order in which search token are explored would identify the order of search: depth first, or breadth first etc. In the present embodiment, breadth first is used but this is not to be limiting.

In the given example, devices are identified by addresses. For this solution, a relational database has been assumed, but other types of databases can also be used. Two relations are defined, one for external connections, and one for internal switching. External connection relation has the following form:

[Device ID, Device Port, Connected Device ID, Connected Device Port].

Device ID: is the address of the device being defined.

Device Port: refers to a particular external port # in this device.

Connected Device ID (CID): refers to the address of the device connected to port defined by `Device Port`.

Connected Device Port (CDP): is the port number of the CID, connected to the Device Port.

Table 1 shows as an example the external connection table entries for device 122 of FIG. 7.

The internal switching table has the following form:

[device ID, Source Port ID, Sink Port ID, Mapping & Port Characteristics]

Device ID: is the address of the device being defined.

Source Port: Port # of the port being aggregated.

Sink Port: Port # of the aggregate port.

Mapping and Port Characteristics (MAPC): This identifies the type of mapping (translation, aggregation, and mesh) as well as the port characteristics (such as diagnostic, external, internal, etc.).

It should be noted that the Source and Sink port definitions apply both to internal as well as external ports. Also, the concept of Sink and Source ports refer only to operations that perform aggregation and deaggregation. In translation and mesh operations the Source and Sink ports have no significance and are interchangeable.

Table 2 shows for example the internal switching entries for device 122 of FIG. 7.

TABLE 1 ______________________________________ EXTERNAL CONNECTION ENTRIES FOR DEVICE 122 DEVICE ID PORT CNCT CNC PORT ______________________________________ 122 6 124 1 122 1 120 1 122 2 120 2 122 3 120 3 122 4 120 4 122 5 126 5 ______________________________________

TABLE 2 ______________________________________ INTERNAL SWITCHING ENTRIES FOR DEVICE 122 DEVICE ID SRC-PORT SNK-PORTMAPPING TYPE ______________________________________ 122 6 5 diag, agg 122 1 5 main, agg 122 2 5 main, agg 122 3 5 main, agg 122 4 5 main, agg ______________________________________

Data Structures for object representation consists of two parts, viz., a fixed part and a variable part. The fixed part has information about the object such as its address, characteristics, and length information for the variable part. The variable part contains the external connections and internal switchings as well a as a list of diagnostic source ports. FIG. 8 shows the object data structure. It should be emphasized that the connectivity information that is stored for each device is localized.

By tracing the connection from a device to its neighbors and repeating this process recursively on the neighbors, the network connectivity is obtained. The Search method, and the principle of search tokens has been defined to achieve the connectivity information.

The data structures for the search token, and related data structures are shown FIG. 9. Object ID and port number locate a token definitively in the network. As the search continues and tokens flow, these two fields are updated. The level count is initially set to the number of levels to which search is to be undertaken. At each transcripted object traversed, it is decremented by one.

To help keep track of the search process, an aggregation stack associated with each token is maintained in memory. This aggregate stack is a memory of aggregations that have been passed through so far without deaggregation. The search context (a global structure) abstracts the token independent search criteria (end condition, remember criterion, etc.) and global search information (direction, view, etc.).

By way of example of the search process, to find the DC of device (modem) 138 of FIG. 7, the search process begins by locating the diagnostic source port by referring to the Mapping and Port Characteristics field in the Internal Switching Port table of device 138. An initial token is generated on this port. The token is as in FIG. 10a. Now the external connection table of device 138 is searched, and the device (and its external port) connected to the port referred to by the token is determined. Next the initial token is transformed with its device ID changed to the connected device id, and its port number is changed to the