Method for providing for automatic topology discovery in an ATM network or the like

Description Submit all comments and votes

BACKGROUND OF THE INVENTION

1. Field of the Invention

The present invention relates to the field of computer networking, specifically to the field of asynchronous transfer mode (ATM) communications. More specifically, the present invention relates to methods and apparatus for providing topology discovery in an ATM network over a virtual service path (VSP).

2. Description of the Related Art

The present invention relates to the field of ATM and similar networking systems. Such systems are characterized by use of high-speed switches which act to switch message cells of a fixed size and format through the network. Below is provided a general description of ATM networks

ATM Networks

The described embodiment is implemented in an asynchronous transfer mode (ATM) network. Such networks are well-known in the an and, in fact, are described in various references. One such reference is Handel, R. and Huber, M. N., Integrated Broadband Networks, an Introduction to ATM-based Networks, published by Addison-Wesley Publishing Company, 1991 and hereinafter referred to as the Handel et al. reference. Another such reference is de Prycher, M., Asynchronous Transfer Mode solution for broadband ISDN, published by Ellis Horwood Limited, West Sussex, England, 1991.

Importantly, in ATM networks information is communicated in fixed-size cells which comprise a well-defined and size-limited header area and user information area. The switch fabric of an ATM switch is designed to act upon information in the header area in order to provide for muting of cells in the network. The switch fabric is normally implemented in hardware, for example using large-scale integrated circuits, in order to provide for high-speed switching of cells in the network.

Standards have been adopted for ATM networks, for example, by the International Telegraph and Telephone Consultative Committee (CCITT). The CCITT standards require a header area comprising a fixed set of fields and being of a fixed size and a payload area, also referred to as a user information area, and also of a fixed size but allowing user-defined information fields. The CCITT standards define the header to be of a very limited size to keep at a minimum overhead associated with each cell.

ATM Cell Format

In an ATM network, all information to be transferred is packed into fixed-size slots which are commonly referred to as cells. Of course, such fixed-size slots may be referred to with other terminology, for example, packets. In one standard ATM format (CCITT Recommendation I.150, "B-ISDN ATM Functional Characteristics", Geneva, 1991), the format is generally shown in FIG. 1(a) and includes a 5-byte (also called octet) header field 101 and a 48-byte information field 102. The information field is defined by the standard to be available to the user and the header field is defined by the standard to carry information pertaining to ATM functionality, in particular, information for identification of the cells by means of a label. See, Handel et al., at pages 14-17.

The standardized format for the header field 101 is better shown in FIGS. 1(b) and 1(c) and is described in greater detail with reference to Handel et al., at pages 84-91. The header field 101 will be discussed in greater detail below; however, it is worthwhile mentioning here that the header field 101 comprises two fields: (1) a virtual channel identifier (VCI) and (2) a virtual path identifier (VPI). The VPI field is defined as an eight-bit field in one format (see FIG. 1(b)) and as a twelve-bit field in another format (see FIG. 1(c)) and is defined to be used for routing of the cell. The VCI field is also used for routing in the defined format and is defined as a sixteen-bit field.

The de Prycher reference further describes the format of the ATM cell, for example at pages 55-124 and, especially at pages 106-108.

ATM Switching

Two primary tasks are accomplished by an ATM switch: (1) translation of VPI/VCI information and (2) transport of cells from the input port to the correct output port. The functions of an ATM switch are more fully described in Handel et al. at pages 113-136.

A switch is typically constructed of a plurality of switching elements which act together to transport a cell from the input of the switch to the correct output. Various types of switching elements are well-known such as matrix switching elements, central memory switching elements, bus-type switching elements, and ring-type switching elements. Each of these are discussed in greater detail in the Handel et al, reference and each carries out the above-mentioned two primary tasks.

Translation of the VPI/VCI information is important because in a standard ATM network the contents of these fields only has local meaning (i.e., the same data would be interpreted differently by each switch). Thus, the VPI/VCI information is translated by each switch and changed prior to the cell being output from the switch. This translation is accomplished through use of translation tables which are loaded into the switch fabric, generally under control of a switch controller.

ATM Service Providers

An ATM network typically includes at least one service provider whose function it is to provide various services to devices in the network. These services may include, for example, support of a meta-signalling channel specified by the CCITT standard (channel having a VPI:VCI value of 0:1) and supervisory and configuration management functions for internal operations of the devices and for reporting of status of the devices to the service provider.

The various devices (e.g., switches and clients) are interconnected in the network through external ports on the various switches. In the network, these external ports are the lowest addressable unit addressable by the service provider. Importantly, each of the various devices in the network must communicate with the service provider during operation of the network. The communication between the devices and the service provider may be viewed as system overhead and, although necessary, such overhead should be minimized. One area in which an overhead penalty may be paid is in set-up and tear down of communications links between the various devices and the service providers. Typically, it is required to set up at least one communication link per active port. Another area of significant resource overhead is the allocation of VPI/VCI translation table entries and bandwidth utilization on the physical links. For example, each time a communication link is set-up or torn down, translation tables in each switch involved in the communication link must be allocated and updated. Updating of the translation tables and other types of allocation overhead, of course, requires system resources which could be better spent on providing user communication in the network.

Topology Discovery

Topology discovery and, in fact, automatic topology discovery is known in the field of computer networking. For example, U.S. patent Ser. No. 07/526,567 titled "Apparatus and Method for Monitoring the Status of a Local Area Network" filed May 21, 1990, hereinafter the '567 application, which application is assigned to the assignee of the present invention, describes an inventive automatic topology discovery system.

Topology discovery relates generally to the area of obtaining information on devices (e.g., switches, hubs, repeaters, bridges, etc.) in a network and reporting the information in some form such as by display of a graphical representation of the network on a display device.

The following United States Patents are also understood to relate to the area of topology discovery:

______________________________________ U.S. Issue Pat. No. Date Title ______________________________________ 4,545,013 10/1/85 Enhanced Communications Network Testing and Control System 4,644,532 2/17/87 Automatic Update of Topology in a Hybrid Network 4,827,411 5/2/89 Method of Maintaining a Topology Database 5,049,873 9/17/91 Communications Network State and Topology Manager 5,101,348 3/31/92 Method of Reducing the Amount of Information included in Topology Database Update Messages In a Data Communications Network ______________________________________

Importantly, although each of these references relate to the area of topology discovery, the references do not approach the difficult issues raised by ATM networks when attempting to provide for topology discovery.

Certain prior an topology discovery methods utilize a process of flooding of topology information within the network. In such systems, each device transmits on each of its links link state information to each of its neighbors and each of its neighbors, in turn, transmit the message to each of its own neighbors. In this manner, eventually, the entire network topology can be computed at each device in the network. It will be readily seen that in such systems, the use of a flooding technique can lead to infinite loops, in the absence of some control. Further, even with such control, a large number of messages are generated.

In addition, certain prior an topology discovery methods require some intervention, knowledge or processing power on the part of the "neighbor" switches when topology information is advertised. Of course, this has obvious performance implications.

It is also noted that in certain prior art topology discovery methods, topology information is transmitted in the form of messages to, for exa