Reducing overhead when using loopback cells for fault detection in bi-directional virtual circuits

[0001] 1. Field of the Invention

[0002] The present invention relates to telecommunication networks, and more specifically to a method and apparatus for reducing overhead when using loopback cells for fault detection of bi-directional virtual circuits.

[0003] 2. Related Art

[0004] Bi-directional virtual circuits are often provided to enable data transfers between two systems in a network. A bi-directional virtual circuit refers to a virtual circuit in which data traverses the same set of intermediate devices (forming the path) in both the directions. As an example, a virtual circuit provides communication between two end systems (e.g., edge routers or other devices interfacing directly with an ATM switch) in asynchronous transfer mode (ATM) networks, and the same intermediate switches provide the path between the two end systems in both directions.

[0005] Loopback cells are often used to detect faults in the path of virtual circuits. In a typical scenario, each end system (“source end system”) sends a loopback cell (“loopback command”) directed to the other end system (i.e., at the other end of the virtual circuit), and the other end system sends back the cell (“loopback acknowledgment”) with potentially some acknowledgment information incorporated within the cell. The source end system determines the status of the path (including intermediate devices and connecting transmission lines) depending on whether the loopback response is received or not.

[0006] OAM (operation, administration and maintenance) cells (both commands and acknowledgment/responses) used in the context of ATM networks are examples of the loopback cells. Only some of the details of OAM are described here for conciseness. For further details on OAM, the reader is referred to ITU-T Recommendation I.610 entitled, “Series I: Integrated Services Digital Network—Maintenance principles B-ISDN operation and maintenance principles and functions”, which is incorporated in its entirety herewith. At least in OAM related implementations, both end systems (at either end of a virtual circuit) independently check the status of the PVC.

[0007] One problem with such implementations is that the overhead on the components in the network due to resulting traffic (i.e., command and acknowledgment loopback cells) may be unacceptably high. The overhead may include use of bandwidth (which may otherwise be available for other applications) on the communication links and also buffering/processing overhead on all the devices in the virtual circuit path. Such overhead is particularly high on end systems which may need to process the cells more than other devices. The overhead may be unacceptable at least in that the corresponding end system implementations may not scale to large networks (employing a lot of end systems).

[0008] Accordingly, what is needed is a method and apparatus which reduces fault management related traffic (cells) when using loopback cells for fault detection of bi-directional virtual circuits.

[0009] An end system (“first end system”) at one end of a bi-directional virtual circuit sends loopback response cells in response to loopback command cells received from another end system. The another end system determines the status of the virtual circuit based on the loopback response cells. The first end system concludes that the virtual circuit is operational if the another end system determines that the virtual circuit is operational.

[0010] As the first end system need not send loopback command cells to determine the status of the virtual circuit, the overhead on the backbone network (on which the virtual circuit is provisioned) and any devices in the path of the virtual circuit is reduced.

[0011] In an embodiment, the first end system may conclude that the virtual circuit is operational by examining the frequency (receive frequency) at which the loopback command cells are received. If the receive frequency does not change substantially over time, the first end system concludes that the other end system has determined that the virtual circuit is operational.

[0012] Accordingly to an aspect of the present invention, an end system with lower sending frequency stops sending the loopback command cells when both end systems implement the features of the present invention. When the two end systems send with the same sending frequency, both systems may wait a respective random amount of time before stopping to send the loopback command cells. Only the system waiting more time continues sending the loopback command cells.

[0013] Further features and advantages of the invention, as well as the structure and operation of various embodiments of the invention, are described in detail below with reference to the accompanying drawings. In the drawings, like reference numbers generally indicate identical, functionally similar, and/or structurally similar elements. The drawing in which an element first appears is indicated by the leftmost digit(s) in the corresponding reference number.

[0019] 1. Overview and Discussion of the Invention

[0020] An end system (“first end system”) in accordance with the present invention concludes that a bi-directional virtual circuit is operational if the end system at the other end has determined that the virtual circuit is operational based of loopback command and acknowledgment cells. As the other end system would have ensured operability of the virtual circuit in both the directions due to the loopback cells, the first end system may reasonably rely on the determination of the other end system.

[0021] Accordingly, the first end system may not send loopback command cells so long as the other end system continues with the determination that the virtual circuit is operational. As a result, up to 50% of the fault management related packets may be reduced on a network.

[0022] The invention is described below with reference to an example environment for illustration. It should be understood that numerous specific details, relationships, and methods are set forth to provide a full understanding of the invention. One skilled in the relevant art, however, will readily recognize that the invention can be practiced without one or more of the specific details, or with other methods, etc. In other instances, well-known structures or operations are not shown in detail to avoid obscuring the invention. Furthermore the invention can be implemented in other environments.

2. Example Environment

[0023] FIG. 1 is a block diagram illustrating an example environment in which the present invention can be implemented. The environment is shown containing user systems 110-A, 110-B, 170-A and 170-B, edge routers 120, 160 and 180, and switches 130 and 140 in ATM backbone 150. The environment is shown containing a few representative components only for illustration. In reality, each environment typically contains many more components. Each component is described below in further detail.

[0024] User systems 110-A, 110-B communicate with user systems 170-A and 170-B using ATM backbone 150. Each user system (e.g., 110-A) interfaces with the connected (e.g., user system 110-A is shown connected to edge router 120) edge router(s) using a protocol such as Internet Protocol (IP). Each user system may correspond to a computer system or workstation, and can be implemented in a known way.

[0025] ATM backbone 150 is shown containing switches 130 and 140. Switches 130 and 140 operate consistent with the ATM protocol, and may be implemented in a known way. In general, switches enable edge routers 120, 160 and 180 to communicate with each other using ATM protocol.

[0026] Edge router 120 interfaces with user systems 110-A and 110-B using IP protocol, and with switch 130 using ATM. Edge router 120 may use a PVC (bidirectional in nature) to communicate with each of the other edge routers 160 and 180. The edge routers at either end of a PVC are referred to as end systems in the present application. OAM loopback cells may be used for fault management of the PVCs. The present invention enables the OAM messages to be reduced as described below.

[0027] For illustration, it is assumed that a PVC is set up between edge routers 120 and 160. Instead of sending OAM command cells at regular intervals (e.g., every 10 seconds), edge router 120 may conclude that the PVC is operational based on the determination by edge router 160 that the PVC is operational.

[0028] Edge router 120 may determine that edge router 160 has determined that the PVC is operational by examining a frequency at which the OAM command cells are received. As is well known, edge routers are typically implemented to transmit loopback command cells at a default interval, but increase the frequency of the transmissions if the loopback acknowledgment cells are not consistently received (or there is question on operability otherwise).

[0029] Thus, if edge router 160 consistently receives loopback acknowledgment cells from edge router 120, edge router 160 may determine that the PVC is operational. Accordingly, edge router 160 sends loopback command cells at the same default rate. So long as loopback command cells are received at the same rate, edge router 120 may conclude that the PVC is operational and not send loopback command cells. Thus, the OAM cells may be reduced by up to 50% in accordance with the present invention. The description is continued with reference to a flow chart of FIG. 2.

3. Method

[0030] FIG. 2 is a flow chart depicting a method in accordance with the present invention. The method is described with reference to reduction of fault detection cells on a PVC set up between edge router 120 and edge router 160 of FIG. 1 for illustration. However, the present invention may be performed in other end systems and environments also. The method starts in step 201, in which control immediately passes to step 210.

[0031] In step 210, edge router 120 receives several loopback command cells on a PVC from, for example edge router 160. The cells may be received in a known way. In step 220, edge router 120 determines the average frequency at which the loopback command cells are received. The average may be computed based on several successive cells to account for transient situations such as traffic congestion in the path, etc.

[0032] In step 230, edge router 120 determines a present frequency at which the loopback command cells are being received. In one embodiment, a time stamp is associated with each received command cell. If a subsequent cell is not received within a time duration determined by the present frequency, then control passes to step 260 (via step 240). A timer may be used for such an implementation.

[0033] In step 240, edge router 120 determines whether the present frequency at least approximately equals (shown as symbol ‘˜=’ in FIG. 2) the average frequency determined in step 210. If such equality exists, edge router 120 may conclude that the PVC is operational and control passes to step 250; otherwise control passes to step 260. In a timer based approach noted in step 230, expiration of timer implies that the present frequency exceeds the average frequency, and thus control passes to step 260.

[0034] In step 260, edge router 120 continues to send loopback command cells to independently determine the status of the path to edge router 160. In step 270, edge router 120 determines whether the corresponding loopback response cells are received from the other end system. Control passes to step 290 if the loopback cells are received, or else control passes to step 280.

[0035] In step 280, edge router 120 indicates internally the virtual circuit is not operational. From step 280, control passes to step 260. In step 290, edge router 120 indicates that the virtual circuit is operational. Control then passes to step 210. By not sending the loopback command cells to edge router 160, a reduction of up to 50% of OAM related command cells on ATM backbone 150 may be achieved.

[0036] The details of an embodiment of edge router 120 as relevant to the present invention is described below.

4. Edge Router

[0037] FIG. 3 is a block diagram illustrating the internals of an embodiment of edge router 120 as relevant to several aspects of the present invention. Edge router 120 is shown containing ethernet interface 310, forwarding block 320, encapsulator 330, ATM interface 350, parser 360 and OAM processor 370. Each block is described below in further detail.

[0038] Ethernet interface 310 provides the electrical and protocol interfaces necessary to send and receive IP packets. Ethernet interface 310 forwards each received packet to forwarding block 320. Forwarding block 320 examines the header of each packet and determines the direction in which to forward the packet based on the entries in forwarding table 325. Forwarding block 320 and ethernet interface 310 may be implemented in a known way.

[0039] Forwarding table 325 indicates the manner (outbound interface) in which each IP packet is to be forwarded, and may be populated using one of several known routing protocols (and/or manual configuration). For purpose of illustration, it will be assumed that a packet is to be forwarded on ATM backbone 150, and accordingly the packet is forwarded to encapsulator 330.

[0040] Encapsulator 330 encapsulates each IP packet in the form of potentially multiple cells. The specific VC on which to forward the packet may be determined based on the entries in VC table 335. Encapsulator 330 may also be implemented in a known way.

[0041] VC table 335 may contain data representing the various VCs (virtual circuits) terminating on edge router 120. VC table 335 may further indicate the status of each VC (e.g., PVC to edge router 160). Data cells (i.e., non-management related data) may be transmitted on a VC only if the VC is indicated to be operational. OAM processor 370 may set the status information as described below.

[0042] ATM interface 350 provides the physical, electrical and protocol interfaces necessary to send and receive ATM cells. ATM interface 350 forwards each cell to parser 360. Parser 360 examines the cell to determine the manner in which to process the cell. For illustration, it will be assumed that the cell is a OAM loopback cell used for fault management of the PVC on which the cell is received. Accordingly, the cell is forwarded to OAM processor 370. ATM interface 350 and parser 360 may be implemented in a known way.

[0043] OAM processor 370 determines whether each PVC is operational in accordance with an aspect of the present invention. The status of some of the PVCs may be determined by monitoring the frequency of the loopback command cells on the corresponding PVCs as described above. To determine the average and present frequencies, multiple time stamps (e.g., prior 5) representing the time points at which successive prior cells are received may be stored in OAM table 375. The averages may be computed based on the time stamps in a known way.

[0044] At least when the status of the PVC is not yet determined or cannot be determined based on command cells received from other end systems, OAM processor 370 sends loopback command cells to the end system (“other end system”) at the other end of the PVC. The other end system sends loopback response cells which would confirm that the PVC is operational in both directions. To correlate command cells with the later received response cells, a unique tag may be generated associated with each command cell and included in the cell. The tags also may be stored in OAM table 375.

[0045] Thus, when a OAM response cell is received, the tag in the cell may be compared with the tags in OAM table 375 to ensure that all the sent cells are received. If at least a substantial number of response cells are not received, OAM processor 370 may increase the frequency at which the command cells are sent.

[0046] Once the PVC is determined to be operational, the corresponding entry in VC table 335 is updated to reflect that the PVC is operational. While some of the basic underlying principles are described above, it is generally necessary for end systems to inter-operate with other end system with same or different implementations. Operation with some of such other implementations is described below.

5. Inter-Operability

[0047] In an embodiment, edge router 120 is implemented to stop sending loopback command cells only if the average interval at which edge router 120 transmits is more than the average interval at which the other end system (e.g., edge router 160) transmits the command cells. In other words, when both end systems implement the features of the present invention, the end system with the lower interval (i.e., higher transmit frequency) for transmitting command cells continues transmission.

[0048] In case an end system with a lower interval (for sending command cells) does not implement the invention, edge router 120 may be implemented to stop transmitting the command cells after waiting for a short duration. Thus, both the end systems continue transmission for a while and then the end system with the higher interval (lower frequency) stops sending the command packets.

[0049] In case both end systems have a substantially equal interval for transmitting the command cells, a random number may be used to determine which end system stops sending the loopback command cells. Thus, both end systems may generate a respective random number, and continue transmission of command cells for a duration proportionate to the corresponding generated random number. At the end of the duration, further transmission may continue only if the command cells are not received from the other end system. If both end systems stop transmission, then both may re-start transmission and use the random number until only one of the two end systems stops transmitting.

[0050] It should be understood that each feature of the present invention can be implemented in a combination of one or more of hardware, software and firmware. In general, when throughput performance is of primary consideration, the implementation is performed more in hardware (e.g., in the form of an application specific integrated circuit). When cost is of primary consideration, the implementation is performed more in software (e.g., using a processor executing instructions provided in software/firmware). Cost and performance can be balanced by implementing edge router 120 with a desired mix of hardware, software and/or firmware. An embodiment implemented substantially in software is described below.

6. Software Implementation

[0051] FIG. 4 is a block diagram illustrating the details of edge router 120 in one embodiment. Edge router 120 is shown containing processing unit 410, random access memory (RAM) 420, storage 430, output interface 460, packet memory 470, network interface 480 and input interface 490. Each component is described in further detail below.

[0052] Output interface 460 provides output signals (e.g., display signals to a display unit, not shown) which can form the basis for a suitable user interface for an administrator to interact with edge router 120. Input interface 490 (e.g., interface with a key-board and/or mouse, not shown) enables an administrator to provide any necessary inputs to edge router 120. Output interface 460 and input interface 490 can be used, for example, to enable a network administrator to configure various virtual circuits and specify the intervals at which the OAM command cells are to be transmitted.

[0053] Network interface 480 enables edge router 120 to send and receive data on communication networks using asynchronous transfer mode (ATM) and internet protocol (IP). Network interface 480 may correspond to ethernet interface 310 and ATM interface 390 of FIG. 3. Network interface 480, output interface 460 and input interface 490 can be implemented in a known way.

[0054] RAM 420, storage 430, and packet memory 470 may together be referred to as a memory. RAM 420 receives instructions and data on path 450 from storage 430, and provides the instructions to processing unit 410 for execution. In addition, RAM 420 may be used to implement one or more of forwarding table 325, VC table 335, and OAM table 375. Packet memory 470 stores (queues) cells/packets waiting to be forwarded (or otherwise processed) on different ports.

[0055] Secondary memory 430 may contain units such as hard drive 435 and removable storage drive 437. Secondary storage 430 may store the software instructions and data, which enable edge router 120 to provide several features in accordance with the present invention.

[0056] Some or all of the data and instructions may be provided on removable storage unit 440, and the data and instructions may be read and provided by removable storage drive 437 to processing unit 410. Floppy drive, magnetic tape drive, CD-ROM drive, DVD Drive, Flash memory, removable memory chip (PCMCIA Card, EPROM) are examples of such removable storage drive 437.

[0057] Processing unit 410 may contain one or more processors. Some of the processors can be general purpose processors which execute instructions provided from RAM 420. Some can be special purpose processors adapted for specific tasks (e.g., for memory/queue management). The special purpose processors may also be provided instructions from RAM 420. In general processing unit 410 reads sequences of instructions from various types of memory medium (including RAM 420, storage 430 and removable storage unit 440), and executes the instructions to provide various features of the present invention.

[0058] Embodiments according to FIG. 4 can be used to reduce the loopback cells used for fault detection in virtual circuits as described above. While the embodiments above have been described with reference to ATM substantially, it should be understood that various aspects of the present invention can be implemented in other environments (e.g., frame relay). Implementations in such other environments are also contemplated to be within the scope and spirit of several aspects of the present invention.

[0059] While various embodiments of the present invention have been described above, it should be understood that they have been presented by way of example only, and not limitation. Thus, the breadth and scope of the present invention should not be limited by any of the above-described exemplary embodiments, but should be defined only in accordance with the following claims and their equivalents.