Selecting a routing direction in a communications network using a cost metric

• US 6,680,912 B1
• Filed: 03/03/2000
• Issued: 01/20/2004
• Est. Priority Date: 03/03/2000
• Status: Expired due to Term

• Current Assignee: ADTRAN Incorporated (ADTRAN Holdings, Inc.)
• Original Assignee: Luminous Networks, Inc (ADTRAN Holdings, Inc.)
• Inventors: Fan, Jason C., Bannai, Vinay K., Jogalekar, Prasad P., Barry, Charles F., Kalman, Robert F.
• Primary Examiner(s): Chin, Wellington
• Assistant Examiner(s): Fox, Jamal A.
• Application Number:
  US09/519,024
• Time in Patent Office: 1,418 Days
• Field of Search: 370/235, 370/238, 370/238.1, 370/404, 370/237, 370/351, 370/222, 370/223, 370/224, 370/225, 370/242, 370/245
• US Class Current: 370/238
• CPC Class Codes: H04J 2203/0042 Ring
• CPC Class Codes: H04J 2203/0053 Routing
• CPC Class Codes: H04J 2203/006 Fault tolerance and recovery
• CPC Class Codes: H04J 3/085 for ring networks, e.g. SDH/SONET rings, self-healing rings, meashed SDH/SONET networks
• CPC Class Codes: H04L 12/43 with synchronous transmission, e.g. time division multiplex [TDM], slotted rings
• CPC Class Codes: H04L 45/123 Evaluation of link metrics techniques for monitoring network metrics H04L43/08
• CPC Class Codes: H04L 45/22 Alternate routing
• CPC Class Codes: H04L 45/28 using route fault recovery
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/122 by diverting traffic away from congested entities
• CPC Class Codes: H04L 47/2441 relying on flow classification, e.g. using integrated services [IntServ]
• CPC Class Codes: H04L 47/283 in response to processing delays, e.g. caused by jitter or round trip time [RTT]
• CPC Class Codes: H04L 47/32 by discarding or delaying data units, e.g. packets or frames
• CPC Class Codes: H04L 47/41 by acting on aggregated flows or links
• CPC Class Codes: H04L 47/746 Reaction triggered by a failure
• CPC Class Codes: H04L 47/762 triggered by the network
• CPC Class Codes: Y02D 30/50 in wire-line communication networks, e.g. low power modes or reduced link rate

Abstract

The disclosed network includes two rings, wherein a first ring transmits data in a clockwise direction, and the other ring transmits data in a counterclockwise direction. The traffic is removed from the ring by the destination node. During normal operations (i.e., all spans operational), data between nodes flows on the ring that would provide the minimum number of hops to the destination node. Thus, both rings are fully utilized during normal operations. The nodes periodically test the bit error rate of the links (or the error rate is constantly calculated) to detect a fault in one of the links. The detection of such a fault sends a broadcast signal to all nodes to reconfigure a routing table within the node so as to identify the optimum routing of source traffic to the destination node after the fault. Since the available links will now see more data traffic due to the failed link, traffic designated as “unprotected” traffic is given lower priority and may be dropped or delayed in favor of the “protected” traffic. Specific techniques are described for identifying a failed link, communicating the failed link to the other nodes, differentiating between protected and unprotected classes of traffic, and updating the routing tables.

Claims

1. A method performed by a communications network, said network comprising a plurality of routing switches interconnected by communication links, at least some of said routing switches being connected in a ring, said method comprising:

(a) detecting a faulty link by one of the plurality of routing switches, wherein the plurality of routing switches are interconnected in a ring;

(b) transmitting information from the one routing switch to the remaining of the plurality of routing switches to identify the faulty link;

(c) determining reroute paths for the traffic by the plurality of routing switches, such that the rerouted traffic does not traverse the faulty link, wherein each of the plurality of routing switches independently determines the reroute paths, wherein the determining step comprises;

dynamically selecting routes of traffic along said ring based on a status of links interconnecting said routing switches, the selection of routes to be taken by traffic being determined as follows;

for each destination routing switch j, assigning a cost to each output direction from a first routing switch on the ring;

determining a preferred direction for traffic from said first routing switch to routing switch j based on said direction with a lowest cost;

reassigning costs to each routing switch j for each output direction from said first routing switch as conditions of the links change over time; and

determining reroute paths for traffic from said first routing switch to said routing switch j based on an aggregate cost of links between said first routing switch and said routing switch j in a first direction around said ring and an aggregate cost of links from said first routing switch to routing switch j in an opposite direction around said ring; and

(d) revising a routing table at each of the plurality of routing switches according to the reroute paths.

2. The method of claim 1 wherein said step of rerouting traffic comprises selecting a route with the lowest aggregate cost.

3. The method of claim 1 wherein said costs are based upon a packet loss rate.

4. The method of claim 1 wherein said costs are based upon an average packet queuing delay at the routing switch receiving packets from the link.

5. The method of claim 1 wherein said costs are based upon the variation of packet queuing delay at the routing switch receiving packets from the link.

6. The method of claim 1 wherein said costs are different for different classes of traffic.

7. The method of claim 6 wherein said different classes of traffic comprises protected traffic and unprotected traffic, wherein protected traffic has a higher priority than unprotected traffic.