Method and apparatus for detecting forwarding loops
View Patent ↗The invention includes a method and apparatus for detecting a forwarding loop at a network element. The method includes determining whether a received message was previously received by the first network element, and, if the received message was previously received, calculating a current routing digest and determining whether a header of the received message includes a previous routing digest. If the header of the received message includes the previous routing digest, a determination is made as to whether a forwarding loop exists. If the header of the received message does not include the previous routing digest, the current routing digest is inserted into the header of the received message and the message is forwarded toward the second network element. If the received message was not previously received, forwarding the received message toward a second network element.
1. A method for detecting a forwarding loop at a first network element, comprising:
determining whether a received message was previously received by the first network element;
when the received message was previously received by the first network element, calculating a current routing digest and determining whether a header of the received message includes a previous routing digest, further comprising:
when the header of the received message includes the previous routing digest, determining whether a forwarding loop exists; and
when the header of the received message does not include the previous routing digest, inserting the current routing digest into the header of the received message and forwarding the message toward the second network element; and
when the received message was not previously received by the first network element, forwarding the received message toward a second network element.
2. The method of claim 1 , wherein determining whether the received message was previously received by the first network element comprises:
determining if a header of the received message includes a header field inserted by the first network element when the received message was previously received by the first network element.
3. The method of claim 1 , wherein determining whether the forwarding loop exists comprises:
comparing the current routing digest and the previous routing digest and performing one of:
when the current routing digest and the previous routing digest match, detecting the forwarding loop; and
when the current routing digest and previous routing digest do not match, forwarding the message toward the second network element.
4. The method of claim 1 , wherein calculating the current routing digest comprises:
identifying, in the header of the received message, selected ones of a plurality of header fields associated with routing of the received message; and
calculating the current routing digest using the selected ones of the header fields associated with routing of the received message.
5. The method of claim 4 , wherein calculating the current routing digest using the selected ones of the header fields associated with routing of the received message comprises:
summing a result of a hash function over the selected ones of the header fields.
6. The method of claim 1 , wherein the current routing digest is inserted into the received message as a portion of the header of the received message.
7. The method of claim 1 , wherein the current routing digest is inserted into the received message as a portion of a header field of the header of the received message, wherein the current routing digest comprises a routing digest parameter name and a routing digest parameter value.
8. An apparatus for detecting a forwarding loop at a first network element, comprising:
a processor; and
a memory storing instructions, which when executed by the processor, causes the processor to:
determine whether a received message was previously received by the first network element;
when the received message was previously received by the first network element, calculate a current routing digest, determine whether a header of the received message includes a previous routing digest, and perform one of:
when the header of the received message includes the previous routing digest, determine whether a forwarding loop exists; and
when the header of the received message does not include the previous routing digest, insert the current routing digest into the header of the received message and forward the message toward the second network element; and
when the received message was not previously received by the first network element, forward the received message toward a second network element.
9. The apparatus of claim 8 , wherein the processor is configured to determine whether the received message was previously received by the first network element
by determining if a header of the received message includes a header field inserted by the first network element when the received message was previously received by the first network element.
10. The apparatus of claim 8 , wherein the processor is configured to determine whether the forwarding loop exists comprises by:
comparing the current routing digest and the previous routing digest, wherein:
when the current routing digest and the previous routing digest match, detecting the forwarding loop; and
when the current routing digest and previous routing digest do not match, forwarding the message toward the second network element.
11. The apparatus of claim 8 , wherein the processor is configured to calculate the current routing digest by:
identifying, in the header of the received message, selected ones of a plurality of header fields associated with routing of the received message; and
calculating the current routing digest using the selected ones of the header fields associated with routing of the received message.
12. The apparatus of claim 11 , wherein calculating the current routing digest using the selected ones of the header fields associated with routing of the received message comprises:
summing a result of a hash function over the selected ones of the header fields.
13. The apparatus of claim 8 , wherein the current routing digest is inserted into the received message as a portion of the header of the received message.
14. The apparatus of claim 8 , wherein the current routing digest is inserted into the received message as a portion of a header field of the header of the received message, wherein the current routing digest comprises a routing digest parameter name and a routing digest parameter value.
15. A non-transitory computer readable storage medium storing a software program, that, when executed by a computer, causes the computer to perform a method for detecting a forwarding loop at a first network element, the method comprising:
determining whether a received message was previously received by the first network element;
when the received message was previously received by the first network element, calculating a current routing digest and determining whether a header of the received message includes a previous routing digest, further comprising:
when the header of the received message includes the previous routing digest, determining whether a forwarding loop exists; and
when the header of the received message does not include the previous routing digest, inserting the current routing digest into the header of the received message and forwarding the message toward the second network element; and
when the received message was not previously received by the first network element, forwarding the received message toward a second network element.
16. The non-transitory computer readable storage medium of claim 15 , wherein determining whether the received message was previously received by the first network element comprises:
determining if a header of the received message includes a header field inserted by the first network element when the received message was previously received by the first network element.
17. The non-transitory computer readable storage medium of claim 15 , wherein determining whether the forwarding loop exists comprises:
comparing the current routing digest and the previous routing digest and performing one of:
when the current routing digest and the previous routing digest match, detecting the forwarding loop; and
when the current routing digest and previous routing digest do not match, forwarding the message toward the second network element.
18. The non-transitory computer readable storage medium of claim 15 , wherein calculating the current routing digest comprises:
identifying, in the header of the received message, selected ones of a plurality of header fields associated with routing of the received message; and
calculating the current routing digest using the selected ones of the header fields associated with routing of the received message.
19. The non-transitory computer readable storage medium of claim 18 , wherein calculating the current routing digest using the selected ones of the header fields associated with routing of the received message comprises:
summing a result of a hash function over the selected ones of the header fields.
20. The non-transitory computer readable storage medium of claim 15 , wherein the current routing digest is inserted into the received message as a portion of the header of the received message.