Multiplex communications – Fault recovery – Bypass an inoperative station
Reexamination Certificate
1998-05-04
2002-10-08
Nguyen, Chau (Department: 2663)
Multiplex communications
Fault recovery
Bypass an inoperative station
C370S256000, C370S406000, C370S408000
Reexamination Certificate
active
06463033
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to techniques for configuring optical networks and other types of communication networks, and more particularly to network configuration techniques which permit fast restoration of signal paths after a failure in a link or node of the network.
BACKGROUND OF THE INVENTION
Ring networks, such as networks based on synchronous optical network (SONET) rings, are becoming increasingly popular due to their fast restoration capability in the presence of node or link failures. A ring network may be viewed as any network which includes a set of interconnected rings of nodes. For a given network including a set of rings and a set of node-to-node traffic demands, the routing aspect of ring network design generally involves routing each demand across the ring network from its source node to its destination node such that the overall network cost, as a function of the ring capacities required by the routing, is minimized.
There are two types of ring interconnections that are used in ring networks: Single Ring Interworking (SRI) and Dual Ring Interworking (DRI). SRI is a simple interworking technique which uses only one hub node serving as a gateway to move traffic from one ring to another. The hub node has to be a common node shared by the two rings. SRI for a given demand is uniquely defined by two rings and a hub node for that demand. There may be multiple common nodes between two rings, and any one of the common nodes can be used in SRI. Although SRI has the advantage of simplicity, it provides no protection against hub node failure.
DRI is designed to overcome this reliability weakness at the price of higher complexity. In DRI, two hub nodes are selected from each ring and paired with the hub nodes on another ring. Cross-ring traffic is moved by sending two copies from one ring to the other via two hub pairs, with one copy sent on each hub pair. DRI is described in greater detail in, for example, B. Doshi et al, “Dual Ring Interworking: High Penalty Cases and How to Avoid Them,” Proceedings of ITC 15, June, 1997. Examples of ring-based architectures which utilize DRI include bidirectional line-switched rings (BLSRI and path switched rings.
Although ring-based architectures based on DRI can provide very fast restoration, e.g., on the order of milliseconds, the increased restoration speed is achieved at the expense of added cost and increased operational complexity. Both the added cost and the increase in operational complexity can be traced to the above-described DRI feature. It is therefore apparent that a need exists for an improved network architecture which can provide the fast restoration capability commonly associated with DRI, but with a substantially reduced cost and complexity.
SUMMARY OF THE INVENTION
The invention provides techniques for routing capacity demands in a ring-based network while avoiding the cost and complexity typically associated with DRI. In an illustrative embodiment, a network includes at least one ring having a pair of hub nodes and a number of additional nodes. A pair of minimum-weight routing trees is generated for the ring, with each of the routing trees specifying paths between nodes of the ring, and having as its root a corresponding one of the hub nodes of the ring. The routing trees are utilized to route capacity demands from nodes of the ring to other portions of the network, such as other rings. The routing trees for a given ring of the network are configured such that the two hub nodes of the ring are adjacent in each of the routing trees of that ring. In addition, the routing trees for the given ring are directed edge disjoint, such that if a link corresponding to one edge of a tree fails, an affected demand is routed to the other hub node of the ring using the other routing tree of the ring. A capacity demand originating at one of the additional nodes of the ring is therefore routed through a first routing tree of the ring to a first hub node of the ring, while a restoration path for the given demand is provided through a second routing tree of the ring to a second hub node of the ring.
In accordance with another aspect of the invention, a network may be configured to include pairs of “super” hub nodes, with pairs of the hub nodes for rings in the network each being assigned to pairs of the super hub nodes. A pair of routing trees generated for a given pair of the super hub nodes is then utilized to route demands for capacity from one of the hub nodes to the super hub nodes. The routing trees for a given pair of super hub nodes have characteristics similar to those identified above for routing trees of ring hub nodes.
A dual hubbed tree network architecture in accordance with the invention not only provides the advantage of predefined failure-independent restoration paths, but also allows more efficient capacity sharing while eliminating the added cost and complexity associated with conventional DRI. These and other features and advantages of the present invention will become more apparent from the accompanying drawings and the following detailed description.
REFERENCES:
patent: 4947390 (1990-08-01), Sheehy
patent: 5533016 (1996-07-01), Cook et al.
patent: 5923646 (1999-07-01), Mandhyan
patent: 6047331 (2000-04-01), Medard et al.
patent: 6061335 (2000-05-01), De Vito et al.
B. Doshi et al, “Dual Ring Interworking: High Penalty Cases and How to Avoid Them,” Proceedings of ITC 15, Jun., 1997.
Communications Network Analysis, Section 2-5, “The Esau-Williams Algorithm,” pp. 14-20.
C. Buyukkoc, “Load Balancing on SONET Rings,” Proceedings of ICT '96, Istanbul, pp. 763-766, 1996.
S. Cosares and I. Saniee, An Optimization Problem Related to Balancing Loads on SONET Rings, Telecommunication Systems, vol. 3, pp. 165-181, 1994.
Lee Andrew
Lucent Technologies - Inc.
Nguyen Chau
Ryan & Mason & Lewis, LLP
LandOfFree
Dual hubbed tree architecture for a communication 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 Dual hubbed tree architecture for a communication network, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Dual hubbed tree architecture for a communication network will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2923166