Multiplex communications – Fault recovery – Bypass an inoperative channel
Reexamination Certificate
2001-08-10
2004-06-01
Chin, Wellington (Department: 2664)
Multiplex communications
Fault recovery
Bypass an inoperative channel
C370S217000, C370S218000, C370S221000, C370S225000, C370S226000, C370S227000
Reexamination Certificate
active
06744727
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to techniques for improving network survivability and more particularly to techniques for determining a spare capacity allocation and techniques for optimizing a network restoration scheme.
BACKGROUND
Telecommunication networks occupy a critical role in today's society. The failure of a network, such as a telephone network, a medical database network, a banking computer network, a military network, an air traffic control network or the Internet, among others, could have catastrophic consequences.
Most networks are comprised of multiple nodes (such as computers, routers, servers, and switching devices, among others) interconnected by multiple links (such as fiber optic cables and wireless relay stations, among others). Information (such as network status information, user data, and component address information, among others) originates at a source node, flows over a set of sequentially connected links, and terminates at a destination node. A node may act as both a source node and a destination node. For example, a computer (source node) requests information from a router (destination node) over a fiber optic cable (link). The router (now acting as the source node) sends the requested information back over the fiber optic cable (link) to the computer (now acting as the destination node). A source node and its corresponding destination node are referred to as a “node pair”. It should be noted that the terms “data,” “traffic,” and “traffic demand” are intended to be synonymous with the term “information” hereinafter.
The route traveled by the information from the source node to the destination node is called a “path.” A path may include the source and destination nodes and one or more links. Furthermore, the path may contain intermediate nodes which pass the information to the next link or node. The path that is normally used for communication by a node pair is called the working path. Most networks establish the shortest path between the source node and the destination node as the working path. Thus, a route requiring one link to connect a node pair is preferred as the working path over a route requiring two links to connect the node pair.
A failure in any network component along a path, however, may prevent communication between the node pair. For example, a link that has failed within the working path will not allow information from the source node to reach the destination node. One or more component failures can easily cripple a network, thereby causing widespread communication failures. Network designers, to create a “survivable network”, establish backup paths which act as detours when a component in the working path fails. The ability of a network to continue operating after a failure is known as a network's “survivability” or “survivability level”.
Network designers must concentrate on providing cost-efficient spare capacity reservation at an acceptable survivability level. The “survivability level” gauges the percentage of network traffic that can be restored upon a failure. The ratio of the total spare capacity over the total working capacity, called the “network redundancy,” is used to measure the cost efficiency of spare capacity allocation. Network redundancy is highly dependent on the network topology, as well as the algorithms used to determine the amount and placement of the spare capacity. It should be noted that “determine”, as referred to in this disclosure, is intended to include calculating, inferring, and assuming, among others. The goal of survivable network design is to provide the maximum network survivability at the minimum network redundancy.
Many techniques have been developed and implemented to maximize network survivability. Traditional network survivability techniques have two components: survivable network design and network restoration. These components are complementary to each other and cooperate to achieve seamless service operation (i.e., the prevention of service disruptions) when a network component fails.
The first component of traditional network survivability techniques is survivable network design. Survivable network design refers to the incorporation of survivability strategies into the network design phase to mitigate the impact of a set of specific failure scenarios. A major component related to the creation of a survivable network is called spare capacity allocation (“SCA”). SCA refers to providing adequate resources within the network which enable traffic to be rerouted when a specific component fails (a link failure for example).
Designers face two major challenges related to SCA. The first challenge is determining how much spare capacity should be provisioned for the network. The second challenge is determining where that spare capacity should be located within the network. Several algorithms have been developed to assist designers in meeting these challenges. These algorithms are either classified as centralized or distributed algorithms. Centralized algorithms are implemented by a central controller, or processor, which has global information regarding the network. Centralized networks, although easy to implement, fail to adequately deal with the dynamic bandwidth provisioning and traffic fluctuations present in current networks such as ATM backbone networks and the Internet. Distributed algorithms, on the other hand, are implemented within each node in which network traffic travels. Distributed algorithms adequately address dynamic bandwidth provisioning and traffic fluctuations, but generally require more resources to implement and are not easily scaled to a changing network. Current algorithms require a large amount of computational time to achieve the desired result. Furthermore, the results obtained may not accurately approximate the optimal spare capacity requirement.
Therefore, there exists a need for a backup path routing scheme that is feasible, scalable, adaptive, much faster, and near global optimal in redundancy reduction.
The second component of traditional network survivability techniques is network restoration. Network restoration refers to rerouting traffic flow that has been affected by a network device failure. The affected traffic is detoured using either pre-planned spare capacity routing or dynamic fault-tolerant routing. In pre-planned spare capacity routing, the affected traffic is detoured to backup paths that have adequate spare capacity provisioned in the SCA design phase. Pre-planned spare capacity routing guarantees that service restoration occurs and minimizes the duration of the failure impact. Pre-planned spare capacity routing, however, requires allocating additional spare capacity, some of which may never be used. As such, the cost of implementing pre-planned spare capacity routing is relatively high.
Dynamic fault-tolerant routing, on the other hand, does not have spare capacity pre-allocated in anticipation of a specific failure. Instead, dynamic fault-tolerant routing establishes a backup path after a failure occurs using any available spare capacity. Although service restoration is not guaranteed and the duration and range of the failure impact is not minimized, dynamic fault-tolerant routing reduces the amount of spare capacity needed, thereby, reducing the implementation cost for the network.
With both pre-planned and dynamic routing, affected traffic is detoured using path restoration, link restoration, and fragment restoration. Path restoration refers to rerouting traffic within the end nodes (i.e., the source and destination nodes). Path restoration spreads the failure influence to a larger area within the network, but has a slow failure response speed. Link restoration refers to rerouting the traffic in the nodes adjacent to the failure (i.e., not necessarily within the source and destination nodes). Link restoration has a faster failure response speed, but has a significant impact on the area within the network that is close to the failure. Link restoration only patches the “hole” introduced by the failure. Final
Liu Yu
TIpper David
Chin Wellington
Schultz William C.
The University of Pittsburgh
Thorp Reed & Armstrong LLP
LandOfFree
Apparatus and method for spare capacity allocation does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Apparatus and method for spare capacity allocation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Apparatus and method for spare capacity allocation will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3308961