Hardware percentile latency measurement

• US 9,806,995 B2
• Filed: 09/08/2014
• Issued: 10/31/2017
• Est. Priority Date: 11/05/2013
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Chu, Kit Chiu, Hill, Jeff, Edsall, Thomas J., Alizadeh Attar, Mohammadreza
• Primary Examiner(s): Hsu, Alpus H
• Assistant Examiner(s): Thai, Camquyen
• Application Number:
  US14/480,482
• Publication Number:
  US 20150124640A1
• Time in Patent Office: 1,149 Days
• Field of Search: 714748, 370235, 370329, 370352 M, 37039552, 370252, 370311, 370230, 370503, 370236, 370352, 704214
• CPC Class Codes: H04L 12/18 for broadcast or conference , e.g. multicast
• CPC Class Codes: H04L 12/4633 Interconnection of networks using encapsulation techniques, e.g. tunneling
• CPC Class Codes: H04L 12/4641 Virtual LANs, VLANs, e.g. virtual private networks [VPN] LAN interconnection over a bridge based backbone H04L12/462; encapsulation techniques H04L12/4633; routing of packets H04L45/00; packet switches H04L49/00; virtual private networks for security H04L63/0272
• CPC Class Codes: H04L 12/4645 Details on frame tagging routing of packets H04L45/00; support for virtual LAN H04L49/354
• CPC Class Codes: H04L 2212/00 Encapsulation of packets
• CPC Class Codes: H04L 41/0654 using network fault recovery ring fault isolation or reconfiguration in loop networks without recovery actions by a network management system H04L12/437
• CPC Class Codes: H04L 43/0811 by checking connectivity
• CPC Class Codes: H04L 43/0852 Delays
• CPC Class Codes: H04L 43/0894 Packet rate
• CPC Class Codes: H04L 43/16 Threshold monitoring
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/021 Ensuring consistency of routing table updates, e.g. by using epoch numbers
• CPC Class Codes: H04L 45/16 Multipoint routing
• CPC Class Codes: H04L 45/22 Alternate routing
• CPC Class Codes: H04L 45/24 Multipath
• CPC Class Codes: H04L 45/245 Link aggregation, e.g. trunking
• CPC Class Codes: H04L 45/28 using route fault recovery
• CPC Class Codes: H04L 45/48 Routing tree calculation
• CPC Class Codes: H04L 45/50 using label swapping, e.g. multi-protocol label switch [MPLS]
• CPC Class Codes: H04L 45/64 using an overlay routing layer
• CPC Class Codes: H04L 45/74 : Address processing for routing
• CPC Class Codes: H04L 45/745 : Address table lookup; Address filtering
• CPC Class Codes: H04L 45/7453 : using hashing
• CPC Class Codes: H04L 47/125 : by balancing the load, e.g. traffic engineering
• CPC Class Codes: H04L 49/70 : Virtual switches
• CPC Class Codes: H04L 51/214 : using selective forwarding
• CPC Class Codes: H04L 61/2503 : Translation of Internet protocol [IP] addresses
• CPC Class Codes: H04L 61/2592 : using tunnelling or encapsulation
• CPC Class Codes: H04L 67/10 : in which an application is distributed across nodes in the network software deployment G06F8/60; multiprogramming arrangements G06F9/46
• CPC Class Codes: H04L 69/22 : Parsing or analysis of headers

Abstract

The subject technology addresses the need in the art for directly measuring a maximum latency number with respect to a percentile of network traffic, which a network operator may utilize as an performance indication or metric. Given a traffic percentile, a tracking algorithm in accordance with embodiments described herein may be implemented in hardware and/or software to determine a maximum latency for this specific percentile of traffic.

Claims

1. A system, comprising:

at least one processor;

a network interface; and

memory including instructions that, when executed by the at least one processor, cause the system to;

receive a first set of packets at the network interface;

determine a number of packets, from the first set of packets, that are received with a latency value below a current threshold value;

determine whether a first ratio of packets below the current threshold value is less than a target ratio value, wherein the target ratio value is provided as a latency percentile;

in response to determining the first ratio is less than the target ratio value, increment the current threshold value by a product of a maximum latency value, a difference of the target ratio value and the first ratio, and a gain setting, wherein the gain setting indicates a magnitude for adjusting the current threshold value; and

in response to determining the first ratio is not less than the target ratio value, decrement the current threshold value by a product of a maximum latency value, a difference of the first ratio and the target ratio value, and a gain setting, wherein the gain setting indicates a magnitude for adjusting the current threshold value.

2. The system of claim 1, wherein the set of packets comprises an interval of packets, wherein the interval of packets represents an amount of packets received during a first period of time.

3. The system of claim 1, wherein the instructions further cause the at least one processor to:

determine whether a remaining period of time remains in a total amount of time for receiving packets.

4. The system of claim 3, wherein the instructions further cause the at least one processor to:

receive a second set of packets at the network interface.

5. The system of claim 1, wherein the set of packets are received at a respective port of the network interface, wherein the network interface includes a plurality of ports.

6. The system of claim 1, wherein the current threshold value comprises a predetermined value or a predicted median percentile latency value according to an expected latency throughout a network.

7. A computer-implemented method, comprising:

receiving a first set of packets at a network interface;

determining a number of packets, from the first set of packets, with a latency below a current threshold value;

determining whether a first ratio of packets below the current threshold value is less than a target ratio value, wherein the target ratio value is provided as a latency percentile;

in response to determining that the first ratio is less than the target ratio value, incrementing the current threshold value by a product of a maximum latency value, a difference between the target ratio value and the first ratio, and a gain setting, wherein the gain setting indicates a magnitude for adjusting the current threshold value; and

in response to determining that the first ratio is not less than the target ratio value, decrementing the current threshold value by a product of a maximum latency value, a difference between the first ratio and the target ratio value, and a gain setting, wherein the gain setting indicates a magnitude for adjusting the current threshold value.

8. The computer-implemented method of claim 7, wherein the set of packets comprises an interval of packets, wherein the interval of packets represents an amount of packets received during a first period of time.

9. The computer-implemented method of claim 7, further comprising:

determining whether a remaining period of time remains in a total amount of time for receiving packets.

10. The computer-implemented method of claim 9, further comprising:

receiving a second set of packets at the network interface.

11. The computer-implemented method of claim 7, wherein the set of packets are received at a respective port of the network interface, wherein the network interface includes a plurality of ports.

12. The computer-implemented method of claim 7, wherein the current threshold value comprises a predetermined value or a predicted median percentile latency value according to an expected latency throughout a network.

13. A non-transitory computer-readable medium including instructions stored therein that, when executed by at least one computing device, cause the at least one computing device to:

receive a first set of packets at a network interface;

determine a number of packets, from the first set of packets, that are received with a latency value below a current threshold value;

determine whether a first ratio of packets below the current threshold value is less than a target ratio value, wherein the target ratio value is provided as a latency percentile;

in response to determining that the first ratio is less than the target ratio value, increment the current threshold value by a product of a maximum latency value, a difference of the target ratio value and the first ratio, and a gain setting, wherein the gain setting indicates a magnitude for adjusting the current threshold value; and

in response to determining that the first ratio is not less than the target ratio value, decrementing the current threshold value by a product of a maximum latency value, a difference between the first ratio and the target ratio value, and a gain setting, wherein the gain setting indicates a magnitude for adjusting the current threshold value.

14. The non-transitory computer-readable medium of claim 13, wherein the set of packets comprises an interval of packets, wherein the interval of packets represents an amount of packets received during a first period of time.

15. The non-transitory computer-readable medium of claim 13, wherein the instructions further cause the at least one computing device to:

determine whether a remaining period of time remains in a total amount of time for receiving packets.

16. The non-transitory computer-readable medium of claim 13, wherein the instructions further cause the at least one computing device to:

receive a second set of packets at the network interface.

17. The non-transitory computer-readable medium of claim 13, wherein the set of packets are received at a respective port of the network interface, wherein the network interface includes a plurality of ports.