Technique for detecting leaky points within a network protocol domain

• US 6,718,382 B1
• Filed: 02/11/1999
• Issued: 04/06/2004
• Est. Priority Date: 02/11/1999
• Status: Expired due to Term

• Current Assignee: Ciena Corporation
• Original Assignee: Nortel Networks Limited (Nortel Networks Corporation)
• Inventors: Li, Yunzhou, Ng, Billy C.
• Primary Examiner(s): Thompson, Marc D.
• Assistant Examiner(s): VU, THONG H
• Application Number:
  US09/248,803
• Time in Patent Office: 1,881 Days
• Field of Search: 709/224, 709/204, 709/245, 709/232, 709/220, 709/203, 709/104, 709/252, 370/233, 370/230, 370/282, 370/13, 370/252, 370/235, 370/236, 370/231, 370/256, 370/286, 370/458, 371/49, 713/201, 713/153, 714/48, 455/555, 455/419, 455/502
• US Class Current: 709/224
• CPC Class Codes: H04L 43/50 Testing arrangements
• CPC Class Codes: H04L 63/1408 by monitoring network traffic monitoring network traffic per se H04L43/00

Abstract

A mechanism for allowing a prober to detect and identify leaky points within a network protocol domain utilizes a Probe Boundary Leak (PBL) protocol to propagate a probe message throughout the network protocol domain. Each PBL router that receives the probe message checks for leaky points in the network protocol domain. Any PBL router that detects a leaky point in the network protocol domain sends a negative response message to the prober including a network address for each leaky point detected by the PBL router. A PBL border router within the network protocol domain being probed sends a positive response message to the prober including a network address for each exit interface supported by the PBL border router. The prober thereby receives a list of “leaky” network interfaces and a list of “non-leaky” exit interfaces for the network protocol domain.

Claims

1. A method for probing leaky points in a network protocol domain of a communication network, the method comprising the steps of:

transmitting a probe message by a prober device, the probe message including a protocol field indicating a protocol of the network protocol domain;

propagating a probe message to a number of probed devices within the communication network;

checking for a leaky point in the network protocol domain by each of said number of probed devices that receives the probe message, including determining whether the probed device executes the protocol indicated in the protocol field of the probe message;

determining, by each probed device, whether to transmit a response message to the prober device, wherein said response message is one of;

negative response message indicating that the probed device detected a leaky point in the network protocol domain; and

a positive response message indicating that the probed device failed to detect a leaky point in the network protocol domain; and

determining, by the prober device, whether the network protocol domain is leaky based upon a pattern of response messages received by the prober device.

2. The method of claim 1, wherein each probed device that detects a leaky point in the network protocol domain transmits a negative response message to the prober device indicating that a leaky point was detected and wherein the step of determining whether the network protocol domain is leaky comprises:

determining that the network protocol domain is leaky if the prober device receives at least one negative response message; and

determining that the network protocol domain is not leaky if the prober device fails to receive at least one negative response message.

3. The method of claim 2, wherein each border device within the network protocol domain that fails to detect a leaky point in the network protocol domain transmits a positive response message to the prober device indicating that no leaky point was detected.

4. The method of claim 1, wherein each probed device that fails to detect a leaky point in the network protocol domain transmits a positive response message to the prober device indicating that no leaky point was detected, and wherein the step of determining whether the network protocol domain is leaky comprises:

determining that the network protocol domain is not leaky if the prober device receives a positive response message from each of a predetermined group of probed devices; and

determining that the network protocol domain is leaky if the prober device fails to receive a positive response message from at least one of the predetermined group of probed devices.

5. In a prober device, a method for probing leaky points within a network protocol domain of a communication network, the method comprising the steps of:

transmitting a probe message to a number of neighboring devices in the communication network, to determine whether each of the number of neighboring devices executes a protocol of the network protocol domain;

monitoring for a probe acknowledgement message from each of said neighboring devices; and

determining that a neighboring device is a leaky point within the network protocol domain if the prober device fails to receive a probe acknowledgement message from the neighboring device within a predetermined period of time.

6. The method of claim 5, further comprising the steps of:

monitoring for response messages from various probed devices in the communication network that receive the probe message; and

determining whether there is at least one leaky point within the network protocol domain, other than a neighboring device for which the prober device failed to receive the probe acknowledgement message within the predetermined period of time, based upon a pattern of response messages received.

7. The method of claim 6, wherein each probed device that detects a leaky point in the network protocol domain transmits a negative response message to the prober device indicating that a leaky point was detected, and wherein the step of determining whether there is at least one leaky point within the network protocol domain, other than a neighboring device for which the prober device failed to receive the probe acknowledgement message within the predetermined period of time, comprises:

determining that there is at least one leaky point within the network protocol domain, other than a neighboring device for which the prober device failed to receive the probe acknowledgement message within the predetermined period of time, if the prober device receives at least one negative response message; and

determining that there is no leaky point within the network protocol domain, other than a neighboring device for which the prober device failed to receive the probe acknowledgement message within the predetermined period of time, if the prober device fails to receive at least one negative response message.

8. The method of claim 6, wherein each probed device that fails to detect a leaky point in the network protocol domain transmits a positive response message to the prober device indicating that no leaky point was detected, and wherein the step of determining whether there is at least one leaky point within the network protocol domain, other than a neighboring device for which the prober device failed to receive the probe acknowledgement message within the predetermined period of time, comprises:

determining that there is no leaky point within the network protocol domain, other than a neighboring device for which the prober device failed to receive the probe acknowledgement message within the predetermined period of time, if the prober device receives a positive response message from each of a predetermined group of probed devices; and

determining that there is at least one leaky point within the network protocol domain, other than a neighboring device for which the prober device failed to receive the probe acknowledgement message within the predetermined period of time, if the prober device fails to receive a positive response message from at least one of the predetermined group of probed devices.

9. A prober device for probing leaky points within a network protocol domain of a communication network, the prober device comprising:

network interface logic operably coupled to the communication network, and

probing logic operably coupled to the network interface logic, wherein the probing logic comprises;

probe messaging transmitting logic operably coupled to the network interface logic for transmitting a probe message to a number of neighboring devices in the communication network to determine whether each of the number of neighboring devices executes a protocol of the network protocol domain;

probe acknowledgement receiving logic responsive to the probe message transmitting logic and operably coupled to the network interface logic for monitoring for a probe acknowledgement message from each of said neighboring devices; and

leak detection logic responsive to the probe acknowledgement receiving logic and operably coupled to determine that a neighboring device is a leaky point within the network protocol domain if the protocol acknowledgement receiving logic fails to receive a probe acknowledgement message from the neighboring device within a predetermined period of time.

10. The prober device of claim 9, wherein the probing logic further comprises probe response receiving logic operably coupled to the network interface logic for receiving response messages from various probed devices in the communication network that receive the probe message, and wherein the leak detection logic is further responsive to the probe response receiving logic and operably coupled to determine whether there is at least one leaky point within the network protocol domain, other than a neighboring device for which the prober device failed to receive the probe acknowledgement message within the predetermined period of time, based upon a pattern of response messages received.

11. The prober device of claim 10, wherein each probed device that detects a leaky point in the network protocol domain transmits a negative response message to the prober device indicating that the leaky point was detected, and wherein the leak detection logic is operably coupled to determine that there is at least one leaky point within the network protocol domain, other than a neighboring device for which the prober device failed to receive the probe acknowledgement message within the predetermined period of time, if the probe response receiving logic receives at least one negative response message.

12. The prober device of claim 10, wherein each probed device that fails to detect a leaky point in the network protocol domain transmits a positive response message to the prober device indicating that no leaky point was detected, and wherein the leak detection logic is operably coupled to determine that there is at least one leaky point within the network protocol domain, other than a neighboring device for which the prober device failed to receive the probe acknowledgement message within the predetermined period of time, if the probe response receiving logic fails to receive a positive response message from at least one of a predetermined group of probed devices.

13. A program product comprising a computer readable medium having embodied therein a computer readable program for probing leaky points within a network protocol domain by a prober device in a communication network, the computer readable program comprising:

probe message transmitting logic programmed to transmit a probe message to a number of neighboring devices in the communication network to determine if each of the number of neighboring devices execute a protocol of the network protocol domain;

probe acknowledgement receiving logic programmed to monitor for a probe acknowledgement message from each of said neighboring devices; and

leak detection logic programmed to determine that a neighboring device is a leaky point within the network protocol domain if the protocol acknowledgement receiving logic fails to receive a probe acknowledgement message from the neighboring device within a predetermined period of time.

14. The program product of claim 13, further comprising probe response receiving logic programmed to receive response messages from various probed devices in the communication network that receive the probe message, and wherein the leak detection logic is further programmed to determine whether there is at least one leaky point within the network protocol domain, other than a neighboring device for which the prober device failed to receive the probe acknowledgement message within the predetermined period of time, based upon a pattern of response messages received.

15. The program product of claim 14, wherein each probed device that detects a leaky point in the network protocol domain transmits a negative response message to the prober device indicating that a leaky point was detected, and wherein the leak detection logic is programmed to determine that there is at least one leaky point within the network protocol domain, other than a neighboring device for which the prober device failed to receive the probe acknowledgement message within the predetermined period of time, if the probe response receiving logic receives at least one negative response message.

16. The proven product of claim 14, wherein each probed device that fails to detect a leaky point in the network protocol domain transmits a positive response message to the prober device indicating that no leaky point was detected, and wherein the leak detection logic is programmed to determine that there is at least one leaky point with in the network protocol domain, other than a neighboring device for which the prober device failed to receive the probe acknowledgement message within the predetermined period of time, if the probe response receiving logic fails to receive a positive response message from at least one of a predetermined group of probed devices.

17. A method for probing leaky points within a network protocol domain by a probed device in a communication network, the method comprising the steps of:

receiving, from a neighboring device, a probe message originated by a prober device in the communication network, the probe message for determining whether the probed devices executes a protocol of the network protocol domain;

transmitting a probe acknowledgement message to the neighboring device;

checking for a leaky point in the network protocol domain; and

determining whether to transmit a response message to the prober device based upon whether the probed device detected a leaky point in the network protocol domain, wherein said response message is one of;

a negative response message indicating that the probed device detected a leaky point in the network protocol domain; and

a positive response message indicating that the probed device failed to detect a leaky point in the network protocol domain.

18. The method of claim 17, wherein the probed device transmits a negative response message to the prober device if the probed device detects at least one leaky point in the network protocol domain.

19. The method of claim 18, wherein the probed device transmits a positive response message to the prober device if the probed device is a border router within the network protocol domain.

20. The method of claim 17, wherein the probed device transmits a positive response message to the prober device if the probed device fails to detect a leaky point in the network protocol domain.

21. The method of claim 17, wherein the probe message includes a protocol identifier identifying a networking protocol being probed, and wherein the probed device is a leaky point in the network protocol domain if the probed device does not support the networking protocol identified by the protocol identifier.

22. The method of claim 17, wherein the probe message includes a protocol identifier identifying a networking protocol being probed and a protocol verification indicator indicating whether or not the probed device is required to support the networking protocol identified by the protocol identifier, and wherein the probed device is a leaky point in the network protocol domain if the probed device does not support the networking protocol identified by the protocol identifier and the protocol verification indicator indicates that the probed device is required to support the networking protocol identified by the protocol identifier.

23. The method of claim 17, wherein the probe message includes a protocol identifier identifying a networking protocol being probed and a domain identifier identifying the network protocol domain being probed, and wherein the probed device is a leaky point in the network protocol domain if the probed device is a border device that supports the networking protocol identified by the protocol identifier and is not within the network protocol domain identified by the domain identifier.

24. The method of claim 17, wherein the probe message includes a time-to-live indicator indicating a maximum number of hops over which the probe message is permitted to traverse, and wherein the probed device is a leaky point in the network protocol domain if the probe message has traversed the maximum number of hops permitted based upon the time-to-live indicator in the probe message.

25. The method of claim 17, wherein the step of checking for a leaky point in the network protocol domain comprises forwarding the probe message by the probed device to a number of neighboring devices, and wherein a neighboring device is a leaky point in the network protocol domain if the probed device does not receive a probe acknowledgement message from the neighboring device within a predetermined period of time.

26. The method of claim 25, wherein the probe message includes a time-to-live indicator indicating a maximum number of hops over which the probe message is petted with traverse, and wherein the step of forwarding the probe message to the number of neighboring devices comprises decreasing the time-to-live indicator in the probe message by one (1).

27. The method of claim 17, wherein the negative response message includes a result code identifying the leaky point detected by the probed device, and optionally includes a network address identifying the leaky point detected by the probed device.

28. The method of claim 17, wherein the positive response message optionally includes a list of network addresses identifying each non-leaky network interface detected by the probed device.

29. A probed device for probing leaky points within a network protocol domain of a communication network, the probed device comprising:

network interface logic operably coupled to the communication network; and

probing logic operably coupled to the network interface logic, wherein the probing logic determines whether neighboring devices execute a protocol of the network protocol domain, wherein the probing logic comprises;

probe message receiving logic operably coupled to the network interface logic for receiving from a neighboring device a probe message originated by a prober device in the communication network;

probe acknowledgement transmitting logic responsive to the probe message receiving logic and operably coupled to transmit a probe acknowledgement message to the neighboring device;

leak detection logic responsive to the probe message receiving logic and operably coupled to check for a leaky point in the network protocol domain; and

probe response transmitting logic responsive to the leak detection logic and operably coupled to determine whether to transmit a response message to the prober device based upon whether the leak detection logic detected a leaky point in the network protocol domain, wherein said response message is one of;

a negative response message indicating that the lead detection logic detected a leaky point in the network protocol domain; and

a positive response message indicating that the leak detection logic failed to detect a leaky point in the network protocol domain.

30. The probed device of claim 29, wherein the probe response transmitting logic is operably coupled to transmit a negative response message to the prober device if the leak detection logic detects at least one leaky point in the network protocol domain.

31. The probed device of claim 30, wherein the probe response transmitting logic is operably coupled to transmit a positive response message to the prober device if the probed is device is a border router within the network protocol domain.

32. The probed device of claim 29, wherein the probe response transmitting logic is operably coupled to transmit a positive response message to the probe device if the leak detection logic fails to detect a leaky point in the network protocol domain.

33. The probed device of claim 29, wherein the probe message includes a protocol identifier identifying a networking protocol being probed, and wherein leak detection logic is operably coupled to determine that the probed device is a leaky point in the network protocol domain if the probed device does not support the networking protocol identified by the protocol identifier.

34. The probed device of claim 29, wherein the probe message includes a protocol identifier identifying a networking protocol being probed and a protocol verification indicator indicating whether or not the probed device is required to support the networking protocol identified by the protocol identifier, and wherein the leak detection logic is operably coupled to determine that the probed device is a leaky point in the network protocol domain if the probed device does not support the networking protocol identified by the protocol identifier and the protocol verification indicator indicates that the probed device is required to support the networking protocol identified by the protocol identifier.

35. The probed device of claim 29, wherein the probe message includes a protocol identifier identifying a network protocol being probed and a domain identifier identifying the network protocol domain being probed, and wherein the leak detection logic is operably coupled to determine that the probed device is a leaky point in the network protocol domain if the probed device is a border device that supports the networking protocol identified by the protocol identifier and is not within the network protocol domain identified by the domain identifier.

36. The probed device of claim 29, wherein the probe message includes a time-to-live indicator indicating a maximum number of hops over which the probe message is permitted to traverse, and wherein the leak detection logic is operably coupled to determine that the probed device is a leaky point in the network protocol domain if the probe message has traversed the maximum number of hops permitted based upon the time-to-live indicator in the probe message.

37. The probed device of claim 29, wherein the leak detection logic is operably coupled to forward the probe message to a number of neighboring devices, and wherein the leak detection logic is operably coupled to determine that a neighboring device is a leaky point in the network protocol domain if the leak detection logic does not receive a probe acknowledgement message from the neighboring device within a predetermined period of time.

38. The probed device of claim 37, wherein the probe message includes a time-to-live indicator indicating a maximum number of hops over which the probe message is permitted to traverse, and wherein the leak detection logic is operably coupled to decrement the time-to-live indicator in the probe message by one (1) before forwarding the probe message to the neighboring devices.

39. The probed device of claim 29, wherein the negative response message includes a result code identifying the leaky point detected by the leak detection logic, and optionally includes a network address identifying the leaky point detected by the leak detection logic.

40. The probed device of claim 29, wherein the positive response message optionally includes a list of network addresses identifying each non-leaky network interface detected by the leak detection logic.

41. A program product comprising a computer readable medium having embodied therein a computer readable program for probing leaky points within a network protocol domain by a probed device in a communication network, the computer readable program comprising:

probe messaging receiving logic programmed to receive from a neighboring device a probe message oriented by a prober device in the communication network, the probe message for determining whether the probed device executes a protocol of the network protocol domain;

probe acknowledgement transmitting logic programmed to transmit a probe acknowledgement message to the neighboring device;

leak detection logic programmed to check for a leaky point in the network protocol domain; and

probe response transmitting logic programmed to determine whether to transmit a response message to the prober device based upon whether the leak detection logic detected a leaky point in the network protocol domain, wherein said response message is one of;

a negative response message indicating that the leak detection logic detected a leaky point in the network protocol domain; and

a positive response message indicating that the leak detection logic failed to detect a leaky point in the network protocol domain.

42. The program product of claim 41, wherein the probe response transmitting logic is programmed to transmit a negative response to the prober device if the leak detection logic detects at least one leaky point in the network protocol domain.

43. The program product of claim 42, wherein the probe response transmitting logic is programed to transmit a positive response message to the prober device if the probed device is a border router within the network protocol domain.

44. The program product of claim 41, wherein the probe response transmitting logic is programmed to transmit a positive response message to the prober device if the leak detection logic fails to detect a leaky point in the network protocol domain.

45. The program product of claim 41, wherein the probe message includes a protocol identifier identifying a network protocol being probed, and wherein leak detection logic is programmed to determine that the probed device is a leaky point in the network protocol domain if the probed device does not support the networking protocol identified by the protocol identifier.

46. The program product of claim 41, wherein the probe message includes a protocol identifier identifying a networking protocol being probed and a protocol verification indicator indicating whether or not the probed device is required to support the networking protocol identified by the protocol identifier, and wherein the leak detection logic is programed to determine that the probed device is a leaky point in the network protocol domain if the probed device does not support the networking protocol identified by the protocol identifier and the protocol verification indicator indicates that he probed device is required to support the networking protocol identified by the protocol identifier.

47. The program product of claim 41, wherein the probe message includes a protocol identifier identifying a network protocol being probed and a domain identifier identifying the network protocol domain being probed, and wherein the leak detection logic is programmed to determine that the probe device is a leaky point in the network protocol domain if the probed device is a border device that supports the network protocol identified by the protocol identifier and is not within the network protocol domain identified by the domain identifier.

48. The program product of claim 41, wherein the probe message includes a time-to-live indicator indicating a maximum number of hops over which the probe message is permitted to traverse, and wherein the leak detection logic is programed to determine that the probed device is a leaky point in the network protocol domain if the probe message has traversed the maximum number of hops permitted based upon the time-to-live indicator in the probe message.

49. The program product of claim 41, wherein the leak detection logic is programmed to forward the probe message to a number of neighboring devices, and wherein the leak detection logic is programmed to determine that a neighboring device is a leaky point in the network protocol domain if the leak detection logic does not receive a probe acknowledgement message from the neighboring device within the predetermined period of time.

50. The program product of claim 49, wherein the probe message includes a time-to-live indicator indicating a maximum number of hops over which the probe message is permitted to traverse, and wherein the leak detection logic is programmed to decrement the time-to-live indicator in the probe message by one (1) before forwarding the probe message to the neighboring devices.

51. The program product of claim 41, wherein the negative response message includes a result code identifying the leaky point detected by the leak detection logic, and optionally includes a network address identifying the leaky point detected by the leak detection logic.

52. The program product of claim 41, wherein the positive response message optionally includes a list of network addresses identifying each non-leaky network interface detected by the leak detection logic.

53. A communication system comprising a prober device in communication with a number of probed devices by way of a probing protocol, wherein:

the prober device transmits a probe message over the communication system, the probe message for determining which of the number of probed devices executes a protocol;

each probed device that receives the probe message from a neighboring device transmits a probe acknowledgement message to the neighboring device and checks for a leaky point in the network protocol domain; and

each probed device determines whether to transmit a response message to the prober device based upon whether the probed device detected a leaky point in the network protocol domain, wherein the response message is one of;

a negative response message indicating that the probed device detected a leaky point in the network protocol domain; and

a positive response message indicating that the probed device failed to detect a leaky point in the network protocol domain.

54. The system of claim 53, wherein each probed device that detects a leaky point in the network protocol domain transmits a negative response message to the prober device indicating that a leaky point was detected.

55. The system of claim 54, wherein each border device within the network protocol domain that fails to detect a leaky point in the network protocol domain transmits a positive response message to the prober device indicating that no leaky point was detected.

56. The system of claim 53, wherein each probed device that fails to detect a leaky point in the network protocol domain transmits a positive response message to the prober device indicating that no leaky point was detected.