Method and apparatus for traffic engineering in shortest path bridged networks

• US 9,503,360 B2
• Filed: 09/27/2010
• Issued: 11/22/2016
• Est. Priority Date: 09/27/2010
• Status: Active Grant

• Current Assignee: Ciena Corporation
• Original Assignee: Ciena Corporation
• Inventors: Bragg, Nigel Lawrence
• Primary Examiner(s): Maung, Zarni
• Application Number:
  US12/891,351
• Publication Number:
  US 20120076014A1
• Time in Patent Office: 2,248 Days
• Field of Search: 370/229, 370/237, 370/238, 370/238.1, 370351-359, 370/389, 370/392, 370/395.1, 370397-399, 370/400, 370/401, 709/238, 709/242
• US Class Current: 1/1
• 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/18 Loop-free operations
• CPC Class Codes: H04L 45/22 Alternate routing
• CPC Class Codes: H04L 45/66 Layer 2 routing, e.g. in Ethernet based MAN's
• CPC Class Codes: H04L 47/122 by diverting traffic away from congested entities

Abstract

A method and apparatus for diverting traffic in a communications network are disclosed. According to one aspect, the invention provides a communications network with a first node and a second node. Connecting these two nodes is a first set of intermediate nodes on a first path (the true shortest path) and a second set of intermediate nodes on a second alternate path. At a first node, a first processor determines whether a packet arriving at the first node must transit the second node. If so, the base virtual local area network (VLAN) identifier (VID) of the packet is replaced by a first VID, and the packet is transmitted along the second path through the second set of intermediate nodes to the second node. At the second node, a second processor determines whether a packet arriving at the second node must transit the first node. If so, the base VID of the packet is replaced by a second VID different from the first VID and different from the base VID, and the packet is transmitted along the second path through the second set of intermediate nodes to the first node.

Claims

1. A method of diverting packets of information in a communications network between a first node and a second node from a first shortest path to a second path, the second path different from the first shortest path, the method comprising:

associating a first virtual local area network (VLAN) identifier (VID) with the second path in a first direction from the first node toward the second node;

associating a second VID with the second path in a second direction from the second node toward the first node, the second VID being different from the first VID;

diverting packets from the first shortest path to a link being a first hop on the second path when the packets have a Media Access Control (MAC) destination address of a location reachable via the first shortest path between the first node and the second node by reducing a cost of the second path to be less than or equal to a cost of the first shortest path by setting the cost of the second path based on the cost of the first shortest path for a shortest path calculation at the first node;

assigning the first VID to all packets transiting a link being a first hop in the first direction on the second path, and assigning the second VID to all packets transiting a link being a first hop in the second direction on the second path, wherein a routing protocol of the first shortest path and a routing protocol of the second path are a same routing protocol; and

establishing a first forwarding table at the first node that directs packets having a first MAC address to transit the second path, wherein the first MAC address addresses a location reachable by the first shortest path in the absence of packet diversion.

2. The method of claim 1, further comprising establishing a second forwarding table at the second node that directs packets having a second MAC address to transit the second path, wherein the second MAC address addresses a location reachable by the first shortest path in the absence of packet diversion.

3. The method of claim 1, wherein establishing the first forwarding table comprises including the second path in the shortest path calculation, the shortest path calculation populating the first forwarding table, wherein the second path is to be taken only by packets transiting both the first and second nodes, and wherein all other packets are routed on shortest paths that exist in the absence of the second path.

4. The method of claim 1, wherein the cost of the second path is set to be fractionally less than the cost of the first shortest path, wherein the fraction is less than the cost of any link in the network.

5. The method of claim 1, wherein the cost of the second path is equal to the cost of the first shortest path, and wherein the second path is preferred to the first shortest path by policy when the costs of the paths are equal.

6. The method of claim 1, further comprising:

receiving a packet at the first node, the packet having a header, the header containing a MAC destination address and a base VID;

determining that the MAC destination address is reachable from the first node via the second node along the second path;

forwarding the packet towards the link being the first hop of the second path;

replacing the base VID with the first VID;

transmitting the packet along the second path toward the second node;

replacing the first VID with the base VID in the header before the packet transits the second node.

7. The method of claim 1, further comprising:

receiving a packet at the first node, the packet having a header, the header containing a MAC destination address and a base VID;

determining that the MAC destination address is reachable from the first node through an intermediate node on the second path without transiting the second node;

forwarding the packet towards the link being the first hop of the second path;

replacing the base VID contained in the header with the first VID;

transmitting the packet to the intermediate node;

leaving the route of the second path at the intermediate node on the basis of a forwarding table that is associated with the first VID; and

replacing, at the intermediate node, the first VID contained in the header with the base VID.

8. The method of claim 1, wherein the same routing protocol is a Provider Link State Bridging (PLSB) routing protocol.

9. A first node in a communications network, the first node configured to route traffic from an input port of the first node to one of a first output port or a second output port of the first node, the first node comprising:

a memory, the memory storing a forwarding table, the forwarding table directing packets having a first Media Access Control (MAC) address to transit a second path via the second output port, the directed packets being assigned a first virtual local area network (VLAN) identifier (VID), the directed packets received at the first node initially having a base VID, the first VID being different from the base VID; and

a processor in communication with the memory, the processor configured to;

inspect a first MAC destination address in a header of a first packet received at the first node;

determine that the inspected first MAC destination address is an address of a location reachable via the second port;

divert the first packet to the second port by reducing a cost of the second path to be less than or equal to a cost of the first shortest path by setting the cost of the second path based on the cost of the first shortest path for a shortest path calculation at the first node; and

replace the base VID of the packet with the first VID, wherein a routing protocol of a first shortest path and a routing protocol of the second path are a same routing protocol, and wherein the base VID is further associated with the first shortest path to a second node that is reachable via the first port in the absence of packet diversion.

10. The first node of claim 9, wherein the processor further:

inspects a second MAC destination address in a header of a second packet received at the first node;

determines that the inspected second MAC destination address is an address of a location reachable from an intermediate node via the second port without transiting a second node; and

replaces a base VID of the second packet with the first VID.

11. The first node of claim 9, wherein the processor is an application specific integrated circuit.

12. A communications network comprising:

a first node;

a second node; and

a first set of one or more intermediate nodes on a first path between the first and second nodes, the first path being a shortest path between the first and second nodes, and a second set of one or more intermediate nodes on a second path between the first and second nodes;

the first node having a first processor, the first processor configured to;

inspect a first Media Access Control (MAC) address in a header of a first packet;

determine that the first packet must transit the second node to reach a destination based on the inspected first MAC address;

divert the first packet to the second node by replacing a base virtual local area network (VLAN) identifier (VID) with a first VID in the header of the first packet and reduce a cost of the second path to be less than or equal to a cost of the first shortest path by setting the cost of the second path based on the cost of the first shortest path for a shortest path calculation at the first node; and

transmit the first packet to the second node along the second path through the second set of one or more intermediate nodes, wherein a routing protocol of the first path and a routing protocol of the second path are a same routing protocol, and wherein the base VID is further associated with the first shortest path to a second node that is reachable via the first port in the absence of packet diversion.

13. The communications network of claim 12, wherein:

the first processor further;

determining whether a second packet received at the first node must transit one of the second set of intermediate nodes without transiting the second node;

when the second packet must transit one of the second set of intermediate nodes without transiting the second node, replacing a base VID with the first VID in a header of the second packet; and

transmitting the second packet toward the one of the second set of intermediate nodes along the second path; and

further comprising, at the one of the second set of intermediate nodes, a second processor, the second processor;

determining that the second packet must leave the second path at the intermediate node; and

replacing the first VID with the base VID before transmitting the second packet to a next node, the next node not being on the second path.

14. The communications network of claim 12, wherein the first processor further:

determines whether a second packet received at the first node must transit one of the first set of intermediate nodes without transiting the second node; and

when the second packet must transit one of the first set of intermediate nodes without transiting the second node, transmitting the second packet toward the one of the first set of intermediate nodes along the first path without replacing a VID of the packet.

15. The communications network of claim 12, wherein the second node has a second processor, the second processor:

determining whether a second packet received at the second node must transit the first node to reach a destination;

when the second packet must transit the first node, replacing the base VID with a second VID in a header of the second packet; and

transmitting the second packet to the first node along the second path, the second VID not equal to the first VID or the base VID.

16. The communications network of claim 15, wherein:

the second processor further;

determining whether a third packet received at the second node must transit one of the second set of intermediate nodes without transiting the first node;

when the third packet must transit one of the second set of intermediate nodes without transiting the first node, replacing the base VID of the third packet with the second VID; and

transmitting the third packet towards the one of the second set of intermediate nodes along the second path;

wherein the one of the second set of intermediate nodes has a third processor, the third processor;

determining that the third packet must leave the second path at the intermediate node; and

replacing the second VID with the base VID before transmitting the third packet to a next node, the next node not being on the second path.

17. The communications network of claim 15, further comprising:

at a node attached to the first node on the second set of intermediate nodes, a third processor, the third processor replacing the second VID with the base VID in the header of the third packet before transmitting the third packet to the first node.

18. The communications network of claim 12, further comprising:

the second node having a second processor, the second processor;

replacing the first VID in the header of the first packet with the base VID before transmitting the first packet to the destination.

19. The communications network of claim 18, wherein each of the second set of intermediate nodes has a third processor, the third processor:

receiving the first packet;

inspecting the first packet to determine whether the first packet must transit through the second node; and

when the first packet must transit through the second node, transmitting the first packet along the second path to the second node without replacing the first VID of the packet.