METHOD AND APPARATUS FOR PROVIDING FAST REROUTE OF A PACKET THAT MAY BE FORWARDED ON ONE OF A PLURALITY OF EQUAL COST MULTIPATH ROUTES THROUGH A NETWORK

• US 20100290458A1
• Filed: 05/03/2010
• Published: 11/18/2010
• Est. Priority Date: 05/13/2009
• Status: Active Grant

• Current Assignee: Avaya Incorporated
• Original Assignee: Avaya Incorporated
• Inventors: Assarpour, Hamid
• Granted Patent: US 8,351,429 B2
• Time in Patent Office: Days
• US Class Current: 370/389
• CPC Class Codes: H04L 12/437 Ring fault isolation or reconfiguration for SDH/SONET ring networks H04J3/085
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/245 Link aggregation, e.g. trunking
• CPC Class Codes: H04L 45/28 using route fault recovery
• CPC Class Codes: H04L 49/557 Error correction, e.g. fault recovery or fault tolerance
• CPC Class Codes: Y02D 30/50 in wire-line communication networks, e.g. low power modes or reduced link rate

Abstract

A method, apparatus and computer program product for providing fast reroute of a packet that may be forwarded on one of a plurality of Equal Cost Multi Path (ECMP) routes through a network is presented. A packet is received by a Forwarding Data Unit (FDU) in a data plane of a network element. The unicast packet is routed at L3, and ECMP is enabled for a next hop for the unicast packet. An ECMP route is selected for forwarding the packet to a destination port. A lookup is performed in a port state table maintained by the FDU to determine an available local port for said ECMP route that is in an UP state for the destination, and if no local port is UP, then a lookup is performed in the port state table to determine an available remote port that is in an UP state for the selected ECMP route.

Claims

1. A computer-implemented method in which a network element performs operations providing fast reroute of a packet that may be forwarded on one of a plurality of Equal Cost Multi Path (ECMP) routes through a network, the method comprising the steps of:

receiving a packet by a Forwarding Data Unit (FDU) in a data plane of a network element, wherein said unicast packet is routed at L3, and wherein ECMP is enabled for a next hop for said unicast packet;

selecting an ECMP route for forwarding the packet to a destination port;

performing a lookup in a port state table maintained by the FDU to determine an available local port for said ECMP route that is in an UP state for the destination, and if no local port is UP, then performing a lookup in the port state table to determine an available remote port that is in an UP state for the selected ECMP route; and

if no available port is determined for the selected ECMP route, selecting another ECMP route if another ECMP route is available and repeating said performing the lookup in the port state table until a port is found for the packet.

2. The method of claim 1 further comprising forwarding said packet to said available port using said ECMP route.

3. The method of claim 1 further comprising determining there are no more ECMP routes available then dropping said packet.

4. The method of claim 1 wherein said selecting an ECMP route for forwarding the packet to a destination port comprises determining whether said destination port is a stand-alone port or a MLT group.

5. The method of claim 4 wherein when said destination port is a MLT group, then generating a hash value from selected fields of said packet to determine a MLT port member.

6. The method of claim 5 further comprising using said MLT group ID and said hash value to determine a port member that is in the UP state.

7. The method of claim 6 further comprising determining whether all port members in a local table are down, and when said all port members are down, then determining an MLT port from a remote table.

8. The method of claim 7 further comprising determining an IST that is in the UP state for a port member selected from said remote table.

9. The method of claim 8 further comprising forwarding said packet to said remote port over said IST.

10. A network element comprising:

a memory;

a processor;

a communications interface;

an interconnection mechanism coupling the memory, the processor and the communications interface; and

wherein the memory is encoded with an application providing fast reroute of a packet that may be forwarded on one of a plurality of Equal Cost Multi Path (ECMP) routes through a network, that when performed on the processor, provides a process for processing information, the process causing the network element to perform the operations of;

receiving a packet by a Forwarding Data Unit (FDU) in a data plane of a network element, wherein said unicast packet is routed at L3, and wherein ECMP is enabled for a next hop for said unicast packet;

selecting an ECMP route for forwarding the packet to a destination port;

performing a lookup in a port state table maintained by the FDU to determine an available local port for said ECMP route that is in an UP state for the destination, and if no local port is UP, then performing a lookup in the port state table to determine an available remote port that is in an UP state for the selected ECMP route; and

if no available port is determined for the selected ECMP route, selecting another ECMP route if another ECMP route is available and repeating said performing the lookup in the port state table until a port is found for the packet.

11. The network element of claim 10 further comprising the network element performing the operation of forwarding said packet to said available port using said ECMP route.

12. The network element of claim 10 further comprising the network element performing the operation of determining there are no more ECMP routes available then dropping said packet.

13. The network element of claim 10 wherein said selecting an ECMP route for forwarding the packet to a destination port comprises determining whether said destination port is a stand-alone port or a MLT group.

14. The network element of claim 13 further comprising instructions wherein when said destination port is a MLT group, then said network element generates a hash value from selected fields of said packet to determine a MLT port member.

15. The network element of claim 14 further comprising the network element performing the operation of using said MLT group ID and said hash value to determine a port member that is in the UP state.

16. The network element of claim 15 further comprising the network element performing the operation of determining whether all port members in a local table are down, and when said all port members are down, then determining an MLT port from a remote table.

17. The network element of claim 16 further comprising the network element performing the operation of determining an IST that is in the UP state for a port member selected from said remote table.

18. The network element of claim 17 further comprising the network element performing the operation of forwarding said packet to said remote port over said IST.

19. A computer readable storage medium having computer readable code thereon for providing fast reroute of a packet that may be forwarded on one of a plurality of Equal Cost Multi Path (ECMP) routes through a network, the medium including instructions in which a network element performs operations comprising:

receiving a packet by a Forwarding Data Unit (FDU) in a data plane of a network element, wherein said unicast packet is routed at L3, and wherein ECMP is enabled for a next hop for said unicast packet;

selecting an ECMP route for forwarding the packet to a destination port;

performing a lookup in a port state table maintained by the FDU to determine an available local port for said ECMP route that is in an UP state for the destination, and if no local port is UP, then performing a lookup in the port state table to determine an available remote port that is in an UP state for the selected ECMP route; and

if no available port is determined for the selected ECMP route, selecting another ECMP route if another ECMP route is available and repeating said performing the lookup in the port state table until a port is found for the packet.

20. The computer readable storage medium of claim 19 further comprising instructions for forwarding said packet to said available port using said ECMP route.