Method and apparatus for loop prevention in communication networks
View Patent ↗A method and apparatus route data packets in communication network. A current routing topology of the network is analyzed and a digest value representing the current routing topology is determined. The digest value is encapsulated within the data packet. The data packet is forwarded according to the current routing topology.
1. A method for routing a data packet in a communication network, the method comprising:
analyzing a current routing topology of the communication network;
determining a first digest value representing the current routing topology;
comparing the first digest value to a second digest value representing the routing topology at a previous time;
encapsulating the first digest value in the data packet; and
forwarding the data packet according to the current routing topology in response to the first digest value and the second digest value being the same.
2. The method of claim 1 , wherein the first digest value is based on a cost associated with traversing each link.
3. The method of claim 2 , wherein the first digest value is determined by applying a mathematical function to at least one of the node identifiers and the link identifiers and applying a modulo to the resulting value.
4. The method of claim 2 wherein the first digest value is mapped to a VLAN identifier field of an Ethernet header.
5. The method of claim 4 , wherein the first digest value is included in a VLAN identifier field of an Ethernet header.
6. The method of claim 2 , wherein the first digest value is determined by applying an XOR function to link-specific data.
7. A method for routing a data packets in a communication network, the method comprising:
receiving a data packet for re-transmission, the data packet including a first digest value summarizing a routing topology of the communication network at a time the data packet originated;
analyzing a current routing topology of the communication network;
determining a second digest value representing the current routing topology;
comparing the first digest value to the second digest value; and
responsive to determining that the first digest value and the second digest value are the same, forwarding the data packet.
8. The method of claim 7 , wherein the first digest value is computed based on an exchange of one of a BGP protocol message, an OSPF protocol message and an IS-IS protocol message.
9. The method of claim 7 , further comprising, responsive to determining that the first digest value and the second digest value are different, discarding the data packet.
10. The method of claim 9 , wherein the first digest value and the second digest value are determined considering at least one of node identifiers, link identifiers, and costs associated with traversing each link.
11. The method of claim 10 , wherein the first digest value and the second digest value are formed using a hash function.
12. The method of claim 10 , wherein the first digest value is encapsulated within the data packet.
13. The method of claim 10 , wherein the first digest value and the second digest value are determined by adding at least one of the node identifiers and the link identifiers and applying a modulo to the resulting sum.
14. The method of claim 9 , wherein the first digest value is mapped to a VLAN identifier field of an Ethernet header.
15. The method of claim 14 , wherein the first digest value is included in a VLAN identifier field of an Ethernet header.
16. The method of claim 9 , wherein the first digest value and the second digest value are determined by applying an XOR function to link-specific data.
17. An apparatus for routing data packets in a communication network, the apparatus comprising:
a controller, the controller operable to:
receive a first digest value representing a routing topology at a first time;
analyze a current routing topology of the communication network at a second time;
determine a second digest value representing the current routing topology at the second time
compare the first digest value to the second digest value; and
responsive to determining that the first digest value and the second digest value are different, discard the data packet; and
a communication interface communicatively coupled to the controller, the communication interface operable to forward the data packet according to the routing topology.
18. The apparatus of claim 17 , wherein responsive to determining that the first digest value and the second digest value are the same, the communication interface is further operable to forward the data packet.