Multiplex communications – Fault recovery – Bypass an inoperative station
Reexamination Certificate
1998-06-03
2003-04-08
Chin, Wellington (Department: 2664)
Multiplex communications
Fault recovery
Bypass an inoperative station
C370S404000
Reexamination Certificate
active
06545977
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to signal routing techniques for use in optical networks and other types of networks, and more particularly to signal routing techniques for use in networks which are configured in the form of interconnected rings.
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. Ring network design usually involves the following basic steps: generation of candidate rings, ring selection, demand routing, and ring sizing and costing. 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 of a signal 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 Jun. 15, 1997. Unfortunately, conventional routing techniques for DRI are unable to provide optimal routing in many important applications.
Another problem with existing ring network routing techniques is that these techniques often must be implemented in a centralized manner. In a conventional ring network, the complete end-to-end path for a given demand is typically determined by a central provisioning operations system (OS). This type of centralized routing is required because the routing on a given pair of adjacent rings cannot be fully decoupled in a conventional ring network. In other words, a routing decision made with respect to one ring in the network may require changing the routing on another ring. As a result, conventional centralized routing techniques can severely limit the speed and scalability of the ring network. Unfortunately, existing distributed routing techniques are generally unable to provide minimum cost routing of point-to-point demands across a ring network using, for example, information available to local controllers of each individual ring.
SUMMARY OF THE INVENTION
The present invention solves the problems associated with conventional centralized routing of traffic demands over a SONET ring network or other type of ring network. In an illustrative embodiment, traffic demands are routed in a ring network by first determining an inter-ring path for a given demand from a source ring to a destination ring in the network, and then independently determining an intra-ring path for the demand on each of the rings in the inter-ring path. In accordance with the invention, intra-ring path provisioning may be fully decoupled from inter-ring path provisioning, such that the demand can be routed substantially more quickly and efficiently than has heretofore been possible using conventional fully-centralized routing. For example, both the routing direction and the interworking nodes for a dual ring interworking (DRI) connection can be determined independently for each of the rings of the inter-ring path. This provides an additional degree of freedom in routing decisions which considerably simplifies the routing process.
The invention may be implemented in the form of a hybrid centralized/distributed network architecture, in which a central operations system or other central controller determines the inter-ring path by applying a shortest path algorithm to a ring graph in which nodes represent rings in the network and links represent ring interconnections in the network. Ring controllers in the rings of the inter-ring path then each independently determine an intra-ring path for their corresponding rings. The ring controllers may also each provide information regarding current ring load to the central controller, such that the information can be used, for example, in determining optimal inter-ring paths for future demands. Once the central controller determines the inter-ring path, it transmits path information to the ring controllers of the rings in the inter-ring path. The information transmitted to a given ring may include, for example, an indication as to whether the given ring is a source ring, a destination ring or a transit ring, identifiers of its neighboring rings in the path, and an identifier and size of the demand.
Although the invention is particularly well suited for use with DRI, the invention can also improve routing performance in single ring interworking (SRI) applications, as well as applications involving combinations of DRI and SRI. Moreover, the invention is applicable to ring networks having arbitrary size, complexity and configuration.
REFERENCES:
patent: 5299207 (1994-03-01), Fujii
patent: 5394389 (1995-02-01), Kremer
patent: 5406549 (1995-04-01), Kremer
patent: 5546542 (1996-08-01), Cosares et al.
patent: 5742774 (1998-04-01), Al-Salameh et al.
patent: 5815489 (1998-09-01), Takatori et al.
patent: 6021113 (2000-02-01), Doshi et al.
patent: 6034798 (2000-03-01), Oberg
patent: 6073248 (2000-06-01), Doshi et al.
patent: 6111941 (2000-08-01), Schreyer
B. Doshi et al., “Dual Ring Interworking: High Penalty Cases and How to Avoid Them,” Proceedings of ITC 15, Jun., 1997.
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.
B. Doshi et al., “Overview of INDT—A New Tool for Next Generation Network Design,” Proceedings of IEEE Globecom, Nov. 1995.
Harshavardhana Paramasiviah
Ravikumar Srinivasan S.
Wang Yufei
Chin Wellington
Lucent Technologies - Inc.
Pham Brenda
Ryan & Mason & Lewis, LLP
LandOfFree
Methods and apparatus for routing signals in a ring 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 Methods and apparatus for routing signals in a ring network, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods and apparatus for routing signals in a ring network will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3055854