Multiplex communications – Fault recovery – Bypass an inoperative channel
Reexamination Certificate
1999-08-30
2004-07-06
Yao, Kwang Bin (Department: 2667)
Multiplex communications
Fault recovery
Bypass an inoperative channel
Reexamination Certificate
active
06760302
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to automatic protection switching systems and methods in networks which incorporate any type of switching and transmission technology.
BACKGROUND OF THE INVENTION
Today's communication systems for delivering data from a source to a destination are typically high-speed, high capacity systems that handle many different types of user services. One example of such a system is an optical fiber network used for telephone traffic or for other data exchange. These advanced networks can transport vast amounts of information at any given time. The networks are conventionally made of links connected to nodes which route information over the network to a desired destination. Since link failures are common for such networks, a fault recovery system is needed to ensure that the data is properly routed to its destination in the event of a fault in a link. While node failures are less frequent, protection against them is also desirable.
Various recovery schemes in the event of a failed link in a network have been proposed but all previous schemes have significant shortcomings. One possible scheme for link failure recovery is a dynamic path rearrangeable mesh architecture. This recovery architecture reroutes transmission paths around a failure point in real time. Spare capacity in the network is used to restore communication on a transmission path when a failure occurs. A control system optimizes the use of available spare capacity by having a node at one end of the failed link broadcast a restoration message to all the other nodes in the network. A node with spare capacity then acknowledges the message and establishes an alternate link from the source to destination. This dynamic method is very time consuming and computationally expensive. The dynamic method has high costs, slow restoration speed, difficult control requirements and the need to constantly plan upgrades to restoration capacity when traffic growth occurs. Additionally, this scheme does not correct for node failures.
Another proposed recovery scheme is a dedicated facility restoration which has dedicated protection links to carry the data if a failure occurs in a link over the main data path. In a “One plus One” protection scheme, the traffic from the source is transmitted simultaneously over both the “main” data path (consisting of links and nodes) and the “backup” data path consisting of a different set of links and nodes. The decision to switch between main and backup data paths is made at the receiving station. In this scheme, fifty percent of the network equipment will always be in standby mode, either operating as a main or backup data path. The main disadvantage of this recovery scheme is that it depends on the connection state of the network. Every time a connection is made from a source to a destination over a link and node data path, a second separate backup link and node data path has to be found to support the main path.
Another proposed dedicated recovery scheme is called the “One for One” protection scheme. This scheme has traffic carried over one path designated the “main” data path with a dormant bearer being the “standby” data path. The main designated data path carries the data until a fault occurs. If a failure occurs, the traffic is switched to the standby data path and remains in that configuration until another failure occurs. Thus fifty percent of the network equipment is always in standby mode. This method is not autonomous but requires end-to-end messages to be transmitted to signal a failure to the source in order to switch data paths. These extra signals add significantly to the cost of operating the network. This recovery scheme also depends on the connection state of the network and every time a connection is made from a source to destination, a second link and node standby path separate from the main path has to be found.
Yet another possible dedicated recovery scheme is a self healing ring. The self healing ring can be either uni-directional or bi-directional. A uni-directional ring has two paths arranged in a ring, composed of a succession of alternating links and nodes, with each link containing two communication lines carrying traffic in opposite directions. Each path carries the same information except that the direction of data propagation is reversed in the second ring. If a link is cut or failed, the network simply relies on the information propagating in the other ring operating in the opposite direction. The receiver of the data can select either path to obtain the data. Every node in the network is connected in the ring. The self healing ring can also be a bi-directional ring with four paths, two main or “working” rings operating in opposite directions and two protection rings, also operating in opposite directions. Each link now has two working lines carrying traffic in opposite directions and two protection lines carrying traffic in opposite directions. Under normal operation (no failures) each working ring carries a portion of the traffic. If a link fails (i.e., all four lines fail), protection switching is used to perform a loop-back function, rerouting the traffic that normally would have used the failed link, around the ring in the opposite direction. This architecture requires a protection line for each working line as in the “one for one” architecture. The main disadvantage of the self-healing ring is that the network topology is limited to a ring including all the nodes. In a ring, there is no capacity for expansion of network traffic since the limited capacity must be shared with all the nodes in the ring. Additionally, a ring can only be protected from a single node or single link failure in the network.
SUMMARY OF THE INVENTION
The present invention is an automatic protection switching system for a network which includes a plurality of network nodes and a plurality of links, each link connecting a pair of nodes. Each link is composed of a pair of working data conduits (communication lines) carrying traffic in opposite directions. In some cases a link may contain more than one pair of working and/or protection conduits. The network nodes contain center switches whose function it is to connect sets of working lines into paths carrying traffic between end user source and destination equipment. They also contain protection switches, whose function is to connect set of protection lines into pre-assigned “protection paths” designed to reroute traffic around a failed link or center switch if a fault is detected. The automatic protection system protects against both link failures and node failures.
The automatic protection system of the present invention is configured by first modeling the network as a graph whose vertices correspond to the net nodes and whose edges correspond to the protection conduits. The pre-assigned protection paths are associated with “protection cycles”. Each cycle protects a part of the network, and an appropriate set of protection cycles can be calculated for any network once its topology is known, so that all links and network nodes are protected. When a failure is detected, the protection switches associated with the failed link or center switch are activated, switching the data that would normally use the failed element, onto a path derived from the cycle protecting that element.
REFERENCES:
patent: 4696001 (1987-09-01), Gagliardi
patent: 5003531 (1991-03-01), Farinholt
patent: 5081452 (1992-01-01), Cozic
patent: 5282200 (1994-01-01), Dempsey
patent: 5442623 (1995-08-01), Wu
patent: 5444694 (1995-08-01), Millet et al.
patent: 5751696 (1998-05-01), Bechtel
patent: 5757774 (1998-05-01), Oka
patent: 5793745 (1998-08-01), Manchester
patent: 5949755 (1999-09-01), Uphadya
Allan Gibbons (1985) “Algorithmic Graph Theory”, Cambridge University Press: pp. 85-93.
T.C. Hu (1982) “Combinatorial Algorithms”, Chapter 4, pp. 138-161, Addison Wesley Publishin Company.
Ellinas George Nicos
Stern Thomas E.
Baker & Botts LLP
The Trustees of Columbia University in the City of New York
Yao Kwang Bin
LandOfFree
Automatic protection switching system in a network does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Automatic protection switching system in a network, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Automatic protection switching system in a network will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3213714