Low overhead continuous monitoring of network performance

• US 6,363,056 B1
• Filed: 07/15/1998
• Issued: 03/26/2002
• Est. Priority Date: 07/15/1998
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Beigi, Mandis Sadr Mohammad, Jennings, Raymond Byars, Verma, Dinesh Chandra
• Primary Examiner(s): NGO, RICKY QUOC
• Application Number:
  US09/115,438
• Time in Patent Office: 1,350 Days
• Field of Search: 370/241, 370/242, 370/243, 370/244, 370/245, 370/252, 370/253, 370/401, 370/400, 709/224, 709/235, 709/223
• US Class Current: 370/252
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04L 41/5003 Managing SLA; Interaction between SLA and QoS
• CPC Class Codes: H04L 43/0852 Delays
• CPC Class Codes: H04L 43/0864 Round trip delays
• CPC Class Codes: H04L 43/0876 Network utilisation, e.g. volume of load or congestion level
• CPC Class Codes: H04L 43/10 Active monitoring, e.g. heartbeat, ping or trace-route
• CPC Class Codes: H04L 43/106 using time related information in packets, e.g. by adding timestamps
• CPC Class Codes: H04L 43/12 Network monitoring probes
• CPC Class Codes: H04L 43/18 Protocol analysers
• CPC Class Codes: H04L 43/50 Testing arrangements
• CPC Class Codes: H04L 43/55 Testing of service level quality, e.g. simulating service usage

Abstract

A method, apparatus, article of manufacture and computer product for low-overhead continuous monitoring of network performance in an intranet or Internet topology. Probe packets are sent from ingress access routers where they are received and processed by egress access routers. Probe packets are generated by copying every Nth packet being sent by an ingress access router. In the event an access router does not receive the probe packet, the probe packet is discarded through normal network delivery mechanisms. Network delay is determined by subtracting the time that a probe packet was received with the time stamp enclosed in the probe packet. Round trip time is established by reflecting the probe packet back to the originating access router and computing the round trip time. Bandwidth monitoring is achieved by using the number of probe packets received to estimate the expected amount of network traffic to be received. Fault monitoring is accomplished by comparing the number of probe packets received with the number of actual packets received. When the low overhead mechanisms indicate that network delays or faults exist, a heavy weight monitoring protocol is started between two access routers in question.

Claims

1. A method for determining network characteristics between a first and a second access point in a network, the method comprising:

configuring the first access point as an ingress access point to generate a plurality of probe packets;

generating each of the probe packets based on contents of a data packet and on preset criteria;

configuring the second access point as an egress access point to detect the probe packets; and

correlating each of the probe packets received at the egress access point with one of the probe packets sent by the ingress access point to determine the network characteristics between the two access points.

2. A method as recited in claim 1, wherein the preset criteria is such that a probe packet is generated after a specific number of data packets have passed through the first ingress access point.

3. A method as recited in claim 1, wherein the preset criteria is such that a probe packet is generated after a specific time interval has elapsed at the first ingress access point.

4. A method as recited in claim 1, wherein the preset criteria is such that the probe packets are generated after a specific number of bytes have passed through the first ingress access point.

5. A method as recited in claim 1, wherein the network characteristics include network bandwidth, and the step of correlating includes the step of comparing a count of probe packets sent by the ingress access point to a count of probe packets received by the egress access point.

6. A method as recited in claim 1, wherein the egress access router removes the probe packets from normal data traffic when each of the probe packets is detected.

7. A method as recited in claim 1, wherein the probe packets are structured so that they are discarded through normal network mechanisms if an egress edge device is not found at the specified destination address of the probe packet.

8. A method as recited in claim 1, wherein the step of generating includes the step of copying;

the destination field in a packet header of the probe packet from the destination field in a data packet passing through the ingress access point; and

setting fields in the probe packet header or payload to specific values which enable the egress access point to detect the probe packet.

9. A method as recited in claim 8, wherein the protocol number in the pocket header is changed to a special reserved protocol number.

10. A method as recited in claim 8, wherein the network is an IP network and an UDP payload is put into the probe packet with a reserved pattern and attaching a data segment as the UDP payload which includes a probe number and local time-stamp.

11. A method recited in claim 1, wherein the network characteristics include network delay and the step of correlating includes, comparing the time difference between the time when the probe-packet is generated at the ingress access point and the time the probe packet is received at the egress access point to give the network delay.

12. A method as recited in claim 10, further comprising the step of the ingress access point placing a time-stamp in the UDP payload of the probe packet.

13. A method as recited in claim 1, further comprising the step of the egress access point determining an expected number of probe packets to be obtained from a particular ingress access point on a basis of probe packets being received from the particular ingress access point.

14. A method as recited in claim 1, wherein the network characteristics include a round-trip delay between two endpoints and the step of generating includes marking the probe packet with a time of generation, the method further comprising;

the egress access point reflecting a probe packet back to the ingress access point; and

the ingress access point comparing the time of generation to a time when the probe was received back.

15. A method as recited in claims 13, further comprising the step of determining network faults by comparing the expected number of probe packets at a particular egress access point to a number of probe packets actually received at the particular egress access point.

16. A method as recited in claim 1, wherein the network is an IP network.

17. A method as recited in claim 1, wherein the ingress point is located at a campus firewall.

18. A method as recited in claim 1, wherein the ingress and egress points are each located in separate routers.

69. A method as recited in claim 8, wherein the step of generating also includes the step of setting the source address in a probe packet header to the source address of the first access point.

19. An apparatus to monitor network performance characteristic between a first and a second access point in the network, said apparatus comprising:

a trigger mechanism at the first access point for determining a time to generate a probe packet;

a probe generation mechanism at the first access point for generating a probe packet based on contents of a data packet and probe generating criteria;

a probe detection mechanism at the second access point for detecting the probe packet; and

an analysis mechanism to compare the probe packet detected at the second access point to the probe packet generated at the first access point.

20. An apparatus as described in claim 19, wherein the trigger mechanism and probe generation mechanism are located in a path of forwarding packets.

21. An apparatus as described in claim 19, wherein the probe detection mechanism is located in the path of forwarding packets.

22. An apparatus as described in claim 21, wherein the probe detection mechanism performs the additional function of removing probe packets from a data stream.

23. An apparatus as described in claim 19, wherein the trigger mechanism and probe generation mechanism are located outside of the data forwarding path of the packets, and monitor the flow of packets through the first access point.

24. An apparatus as described in claim 19, wherein the probe detection mechanism is located outside of the data forwarding path of packets, and operates by monitoring the flow of packets through the second access point.

25. A method comprising:

providing bandwidth measurement between an ingress and an egress access router in a network by;

counting a plurality of packets at the ingress access-router;

generating a probe packet based on content of a data packet whenever a packet count reaches a specified value N; and

counting the probe packets received at the egress access-router.

26. A method as recited in claim 25, further comprising the step of discarding the probe packets through normal network mechanisms if an egress edge device is not found at a specified destination address of the probe packet.

27. A method as recited in claim 25, wherein the step of generating includes probe packets copying every Nth packet and changing the source address of the Nth packet to that of an originating access router;

changing the protocol number to a reserved protocol number;

attaching a UDP header with a reserved pattern; and

attaching a data segment as the UDP payload which includes a probe number and a local time-stamp.

28. The method of claim 27, further comprising the step of the egress access-router identifying probe packets by the reserved protocol number and the UDP header pattern.

29. A method as recited in claim 25, wherein a delay between two endpoints can be determined through use of a common clock and probe packets.

30. The method as recited in claim 25, further comprising the step of counting a first number of probe packets received, and comparing the first number to a second number of packets that should have been received.

31. The method of claim 25, further comprising the step of determining a delay between two endpoints in the network by reflecting a probe packet back to a source router, and determining the round-trip time between the access routers.

32. The method of claim 25, further comprising the step of determining network faults by keeping a count of a number of probe packets received over a time interval.

33. A method for providing bandwidth accounting between a first and a second ISP access point in a network, the method comprising:

configuring at least one ingress access point to have a first packet count of ‘

N-in’

;

said at least one ingress access point keeping track of a second packet count ‘

N-out’

of packets sent into the network; and

generating a probe packet whenever ‘

N-out’

=‘

N-in’

, wherein said probe packets being given a destination address of an Nth packet sent into the network, and being given a source address of an ingress router associated with the at least one ingress point.

34. A method as recited in claim 33, further comprising:

identifying and removing the probe packet from a network data stream and an egress router associated with the at least one ingress point;

sending the probe packet to a local processor;

analyzing the probe packet at the local processor; and

incrementing a packet count of packets received from the ingress access router.

35. The method of claim 34, further comprising the step of converting the packet count into an estimate of packets sent by the ingress access router.

36. The method as recited in claim 33, further comprising the step of discarding the probe packets that do not encounter an egress access router.

37. The method as recited in claim 33, further comprising the step of adjusting the probe packet according to a change in network statistics.

38. A method for forming a plurality of probes packets in a network, said method comprising:

marking of protocol field in a header of each probe packet with a reserved protocol number;

filling a source port field in a UDP header for each probe packet with the reserved pattern; and

filling a destination probe field with the probe number.

39. A method as recited in claim 38, further comprising the step of using the reserved protocol number at an egress access router to identify each probe packet.

40. The method as recited in claim 39, further comprising the step of extracting each probe packet based on an identification obtained in the step of using.

41. A method comprising:

monitoring performance of a shared network by;

forming a probe packet for each group of packets based on content of a data packet received by a router on the network;

counting the probe packets; and

estimating the network bandwidth based on the packet probe count compared to a preset criteria.

42. A method for measuring network characteristics between a first and a second router in a network, the method comprising:

configuring at least one ingress access point on the first router to generate a plurality of probe packets;

generating each of the probe packets based on the contents of a next data packet passing through the ingress access point;

configuring at least one egress access point on the second router to detect the probe packet; and

correlating each of the probe packets received at the egress access point with each of the probe packets sent by the ingress access point to determine the network characteristics between the ingress and egress access points.

43. A method as recited in claim 42, wherein the probe packets are generated after a preset number of data packets have passed through the ingress access point.

44. A method as recited in claim 42, wherein the network characteristics being measured include network bandwidth, and the step of correlating includes comparing a count of probe packets sent by the first router to the count of probe packets received by the second router.

45. A method as recited in claim 42, wherein the egress access router removes each of the probe packets from normal data traffic after each of the probe packets is detected.

46. A method as recited in claim 42, wherein the probe packets are structured so that they are discarded through normal network mechanisms.

47. A method as recited in claim 42, wherein the step of generating includes forming each of the probe packets as follows:

copying a destination field in a particular data packet passing through the ingress access point to a probe destination field in the header of the probe packet;

forming a probe source address in the header of the probe packet to be a router source address of an originating access router; and

setting fields in the header or payload of the probe packet to be a specific value which enables the egress access point to detect the probe packet.

48. A method as recited in claim 47, wherein the protocol number in the header is changed to a special reserved protocol number.

49. A method as recited in claim 47, wherein an UDP payload is put in the probe packet with a reserved pattern and attaching a data segment as the UDP payload which includes such information as the probe number and local time-stamp.

50. An article of manufacture comprising a computer usable medium having computer readable program code means embodied therein for determining network characteristics between a first and a second access point in a network, the computer readable program code means in said article of manufacture comprising computer readable program code means for causing a computer to effect:

configuring the first access point as an ingress access point to generate a plurality of probe packets;

generating each of the probe packets based on contents of a data packet and preset criteria;

configuring the second access point as an egress access point to detect the probe packets; and

correlating each of the probe packets received at the egress access point with one of the probe packets sent by the ingress access point to determine the network characteristics between the two access points.

51. An article of manufacture as recited in claim 50, wherein the network characteristics include a round-trip delay between two endpoints and the step of generating includes marking the probe packet with a time of generation, and the computer readable program code means in said article of manufacture further comprising computer readable program code means for causing a computer to effect:

the egress access point reflecting a probe packet back to the ingress access point; and

the ingress access point comparing the time of generation to a time when the probe was received back.

52. An article of manufacture as recited in claim 50, the computer readable program code means in said article of manufacture further comprising computer readable program code means for causing a computer to effect the step of the egress access point determining an expected number of probe packets to be obtained from a particular ingress access point on a basis of probe packets being received from the particular ingress access point.

53. A computer program product comprising a computer usable medium having computer readable program code means embodied therein for providing bandwidth measurement between an ingress and an egress access router in a network, the computer readable program code means in said computer program product comprising computer readable program code means for causing a computer to effect:

counting a plurality of packets at the ingress access-router;

generating a probe packet whenever a packet count reaches a specified value N; and

counting the probe packets received at the egress access-router.

54. A computer program product as recited in claim 53, the computer readable program code means in said computer program product further comprising computer readable program code means for causing a computer to effect discarding the probe packets through normal network mechanisms if an egress edge device is not found at a specified destination address of the probe packet.

55. A computer program product as recited in claim 53, wherein the step of generating includes probe packets being generated by copying every Nth packet and changing the source address of the Nth packet to that of an originating access router;

changing the protocol number to a reserved protocol number;

attaching a UDP header with a reserved pattern; and

attaching a data segment as the UDP payload which includes a probe number and a local time-stamp.

56. A program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform method steps for providing bandwidth accounting between a first and a second ISP access point in a network, said method steps comprising:

configuring at least one ingress access point to have a first packet count of ‘

N-in’

;

said at least one ingress access point keeping track of a second packet count ‘

N-out’

of packets sent into the network; and

generating a probe packet when ‘

N-out’

=‘

N-in’

, wherein said probe packets being given a destination address of an Nth packet sent into the network, and being given a source address of an ingress router associated with the at least one ingress point.

57. A program storage device readable by machine as recited in claim 56, said method steps further comprising:

identifying and removing the probe packet from a network data stream and an egress router associated with the at least one ingress point;

sending the probe packet to a local processor;

analyzing the probe packet at the local processor; and

incrementing a packet count of packets received from the ingress access router.

58. A program storage device readable by machine as recited in claim 57, said method steps further comprising the step of converting the packet count into an estimate of packets sent by the ingress access router.

59. An article of manufacture comprising a computer usable medium having computer readable program code means embodied therein for measuring network characteristics between a first and a second router in a network, the computer readable program code means in said article of manufacture comprising computer readable program code means for causing a computer to effect:

configuring at least one ingress access point on the first router to generate a plurality of probe packets;

generating each of the probe packets based on the contents of a next data packet passing through the ingress access point;

configuring at least one egress access point on the second router to detect the probe packet; and

correlating each of the probe packets received at the egress access point with each of the probe packets sent by the ingress access point to determine the network characteristics between the ingress and egress access points.

60. An article of manufacture as recited in claim 59, wherein the step of generating includes forming each of the probe packets by effecting the steps of:

copying a destination field in a particular data packet passing through the ingress access point to a probe destination field in the header of the probe packet;

forming a probe source address in the header of the probe packet to be a router source address of an originating access router; and

setting fields in the header or payload of the probe packet to be a specific value which enables the egress access point to detect the probe packet.

61. An article of manufacture as recited in claim 59, wherein the network characteristics being measured include network bandwidth, and the step of correlating includes comparing a count of probe packets sent by the first router to the count of probe packets received by the second router.

62. An article of manufacture as recited in claim 59, wherein the network characteristics being measured include network bandwidth, and the step of correlating includes comparing a count of probe packets sent by the first router to the count of probe packets received by the second router.

63. An article of manufacture as recited in claim 59, wherein the egress access router removes each of the probe packets from normal data traffic after each of the probe packets is detected.

64. An article of manufacture as recited in claim 59, wherein the probe packets are structured so that they are discarded through normal mechanisms.

65. A computer program product comprising a computer usable medium having computer readable program code means embodied therein for forming a plurality of probes packets in an network, the computer readable program code means in said computer program product comprising computer readable program code means for causing a computer to effect:

marking a protocol field in an header of each probe packet with a reserved protocol number;

filling a source port field in a UDP header for each probe packet with the reserved pattern; and

filling a destination probe field with the probe number.

66. A computer program product as recited in claim 65, the computer readable program code means in said computer program product further comprising the step of using the reserved protocol number at an egress access router to identify each probe packet.

67. A computer program product as recited in claim 66, the computer readable program code means in said computer program product further comprising the step of extracting each probe packet based on an identification obtained in the step of using.

68. A computer program product comprising a computer usable medium having computer readable program code means embodied therein for monitoring performance of a shared network, the computer readable program code means in said computer program product comprising computer readable program code means for causing a computer to effect:

forming a probe packet for each group of packets received by a router on the network;

counting the probe packets; and

estimating the network bandwidth based on the packet probe count compared to a preset criteria.

70. A method comprising:

determining network characteristics between a first and a second access point in a network, by;

configuring the first access point as an ingress access point to generate a plurality of probe packets;

generating each of the probe packets based on contents of a data packet and on preset criteria;

configuring the second access point as an egress access point to detect the probe packets; and

correlating each of the probe packets received at the egress access point with one of the probe packets sent by the ingress access point to determine the network characteristics between the two access points.