Passive network latency monitoring

A method measures a resident delay for each port in a node in a network and a peer delay between each pair of neighbor nodes in the network. From these resident delays and peer delays, latency between each pair of neighbor nodes in the network is determined. The method includes weighting a route for a data packet going through the nodes in the network using the determined latencies. Each node includes a switch having switchable connections and is configured by a controller to send probe packets from an output port to a port in a neighbor node. The packet may include a time stamp and an identifier.

TECHNICAL FIELD

The present disclosure relates generally to network measurements. More particularly, embodiments described herein relate to passive network latency measurements.

BACKGROUND

A measure of network latency is desirable for internet service providers to comply with service level agreements (SLA) with a client, and to market their products. In network latency measurements, active strategies are typically used. In an active latency measurement, a number of probe packets are sent across multiple paths between nodes A and B in a network, such as Level 2, Multi-Path (L2MP) network. The time it takes for each packet to traverse from node A to node B is measured. A statistical analysis of the data obtained is used to establish a diagnostic of the network latency. However, the number of equal cost multi-paths (ECMPs) between two given nodes A and B in the network grows exponentially with the number of nodes in the network. Thus, in active network latency measurements the number of probe packets that are required to be sent between nodes A and B grows exponentially with the size of the network. Such exponential growth creates a heavy burden for active latency measurement processes. Also, using an exponentially growing number of probe packets burdens network hardware, since other tasks may need to be processed simultaneously with the latency measurement.

In the figures, elements having the same reference number perform the same or similar functions.

DESCRIPTION OF EXAMPLE EMBODIMENTS

Overview

In this detailed description, the term “node” may refer to, for example, a switch device that relays data packets in a data communication network. Such a switch device may include multiple ports for receiving data packets into the switch device (“ingress”) and for transmitting data packets out of the switch device (“egress”), a processor, and a memory accessible by the processor. Within the switch device, switchable connections are provided such that a data packet received in an ingress port may be sent out from any one of multiple egress ports.

According to embodiments disclosed herein, a method includes measuring an approximate resident delay for a port at a node in a network; measuring peer delays between a pair of nodes in the network; and calculating network latencies for data packets sent between nodes in the network based on the resident delays and the peer delays.

According to embodiments disclosed herein, the memory stores data related to a resident delay time for each port in the switch; and data related to peer delays, each of which is a transit time for a packet to travel from a designated egress port of the switch device to an ingress port of a neighbor node.

According to embodiments disclosed herein a switch may be configured by a controller to send a probe packet from an output port of the switch to a second switch at a neighbor node. The probe packet may include a time stamp and an identifier.

According to embodiments disclosed herein a node may include means for receiving a data packet from a first neighbor node in a network; means for sending a data packet to a second neighbor node in the network; means for calculating a resident time for the data packet in the node; means for determining a peer delay for the data packet to travel to the second neighbor node; and means for storing the resident time for each port in the node, and for storing the peer delay for each neighbor node.

Active strategies for network latency measurements are sometimes selected because they provide an accurate current state of a network. Active latency measurements may be a reliable and cost-effective way to obtain information about network performance, especially when the number of nodes is somewhat limited or is changing only at a moderate rate.

In some embodiments consistent with the present disclosure, a network may be changing rapidly. In such a network, active latency measurements may become problematic as to network usage and device load. For such networks, a passive network latency measurement strategy as disclosed herein may be desirable in fast changing networks. Passive latency measurements as described herein may reduce considerably the number of probe packets that are required to be sent between nodes in the network. Thus, passive strategies consistent with embodiments herein reduce overhead and thus enable a higher network utilization. At the same time, passive latency measurements as disclosed herein facilitate establishing SLAs in complex networks.

A method as disclosed herein may include determining a resident delay for each port at each node in a network; determining a peer delay between each pair of connected ports between neighbor nodes in the network; determining a latency between each pair of ports in neighbor nodes in the network; and creating a graph in which every pair of ports in neighbor nodes of the network is represented by an edge that is assigned a weight proportional to the latency determined for that pair of ports of the neighbor nodes.

In further embodiments disclosed herein the memory of a switch device may store data related to the resident delay for each port and a peer delay to each neighbor node measured by a packet that is sent to the neighbor nodes.

Example Embodiments

FIG. 1illustrates a graphical view of network100having connectivity between node1and node6along network paths110,120, and130, according to some embodiments. Network100inFIG. 1includes nodes1,2,3,4,5,6,7,8, and9. Each node in network100may include network components such as switches, routers, and other devices. According toFIG. 1, a communication link existing between a node i and a neighbor node j is labeled link i-j, where i=1-9, j=1-9, and j≠i. Embodiments consistent with the present disclosure may include a connectivity matrix representation of network100. Further according to embodiments disclosed herein, a probe packet traveling from node i to node j may have associated a peer delay t(i-j), which is the delay for a probe packet to traverse link i-j, measured from the corresponding output or egress port of node i to the corresponding input or ingress port of node j.

FIG. 1shows three possible routes110,120, and130, between nodes1and6, in network100. Route110includes link1-2, and link2-6. A probe packet following route110will incur a peer delay time t(1-2) and a peer delay time t(2-6). Route120includes link1-5and link5-6. A probe packet following route120will incur a peer delay time t(1-5) and a peer delay time t(5-6). Route130includes link1-8and link8-6. A probe packet following route130will incur a peer delay time t(1-8) and a peer delay time t(8-6).

Accordingly, the time it takes for a probe packet to transit from node1to node6depends on the route taken by the packet. In embodiments consistent with the present disclosure, a node i in network100may store peer delays t(i-j) for each neighbor node j. For example, node T can represent a switch device with a memory circuit which stores peer delays t(i-j) for each neighbor node j.

FIG. 2illustrates a partial view of node200in a network, according to some embodiments. As shown inFIG. 2, node200includes switch201and controller205, according to some embodiments. Controller205may include, for example, processor circuit210, memory circuit220, and clock circuit230. Clock circuit230may provide clock signals to control timing in node200. Switch201in node200may include ports211through218. The number of ports in switch201is not limiting, and ports211-218shown herein are illustrative only. According to embodiments of the present disclosure, some of the ports in node200may be input (ingress) ports and some of the ports may be output (egress) ports. Further according to embodiments disclosed herein, ports211-218in node200may be internally coupled to each other, such that each port is coupled to every one of the other ports. For example, port211is connected to every one of ports212-218. The connections between two ports in switch201may be controlled under controller205by one or more switches for dynamic reconfiguration. Thus, in one configuration port,211may be connected to port213, and in a different configuration port211may be connected to port215.

FIG. 2also shows processor circuit210and memory circuit220, associated with controller205in node200. A resident delay R(p1, p2) exists between any two ports p1and p2in switch201. R(p1, p2) represents the delay for a packet traversing from port p1to port p2. For example, resident delay R(211,215) exists between port211and port215. R(211,215) is the time it takes for a data packet to traverse internally from port211to port215in switch201. For port215in switch201, a set of resident delays S(215) can be defined as:
S(215)={R(211,215),R(212,215),R(213,215),R(214,215),R(216,215),R(217,215),R(218,215)}.

More generally, for a port pk in a network switch, the set of resident delays S(pk) can be defined as:
S(pk)={R(x1,pk),R(x2,pk), . . .R(xN,pk)}.

Where {x1, x2, . . . xN} is the set of all ports in the network switch other than pk. Given the definition of set S(pk) of resident delays above, an approximate resident delay D(pk) may be defined for some embodiments, for example, as:
D(pk)=Avg(S(pk)).

That is, approximate resident delay D(pk) is the average of all of the resident delays in the set S(pk). In some embodiments, for any port pk in a given switch, approximate resident delay D(pk) will have a small standard deviation. In some embodiments, approximate resident delay D(pk), may be defined as a measured value based on measuring network latency for traffic egress from port pk. That measured approximate resident delay D(pk) may be a function of several measured values, without regard to the specific ingress ports from which the measurement are initiated.

According to some embodiments consistent with the present disclosure, software stored in memory circuit220inserts probe packets at different ports destined for port pk, at different times (e.g., regular time intervals) to measure the delay of each of the probe packets from ingress to egress to update set S(pk), and thus the value of approximate resident delay D(pk).

The above definitions of approximate resident delay D(pk) associated with traffic ‘leaving’ switch201through port pk are merely illustrative and are not limiting. Alternatively, embodiments consistent with the present disclosure may provide an approximate resident delay D(pk′) associated with traffic ‘entering’ switch201through port pk′. In this case, the approximate resident delay may be calculated from a set S(pk′) including resident delays R(pk′, pk) between input (ingress) port pk′ and any one of multiple other output (egress) ports pk in switch201.

FIG. 3illustrates a network including one or more communication links (e.g., communication link300) between neighbor nodes350and355. Communication link300may include peer delay t(350-355) between port351of node350and port356of node355. In general, the delay between a pair of ports of nodes350and355may depend on the direction of packet traversal. For example, a packet traversing through node350to node355incurs the an actual resident delay in node350at egress port351and peer delay time t(350-355). Conversely, a packet traversing through node355to node350incurs an actual resident delay in node355at egress port356, and peer delay time t(355-350).

Large amounts of network resources (e.g., bandwidth, processor cycles, memory, etc.) would be expended in measuring and recording actual resident delays between all ingress and egress ports in a network in real time or near real time. In some embodiments, a measurement of network latency substitutes an approximate resident delay for the actual resident delay. For example, D(351) (as defined above) can be substituted for the actual resident delay associated with traversing through node350(from any ingress port) out through egress port351. D(356) (as defined above) can be substituted for the actual resident delay associated with traversing through node355(from any ingress port) out through egress port356. In some embodiments, approximate resident delay D(351) in node350may be different from approximate resident delay D(356) in node355. The directionality of communication link300may be expressly represented, for example, by weighted graph370. Weighted graph370illustrates time T1that represents the latency for a packet transiting from node350to node355, and time T2that represents the latency for packet transiting from node355to node350. T1and T2may be defined as follows:
T1=t(355−350)+D(351)  (2.1)
T2=t(355−350)+D(356)  (2.2)

Where D(351) is the approximate resident delay for port351in node350, and D(356) is the approximate resident delay for port356in node355.

According to some embodiments, software in a controller included in node350may send probe packets from egress port351to an ingress port in node355to measure peer delay t(355-350). Peer delay t(350-355) may be measured at node350by sending a probe packet to node355. In response, node355returns measured peer delay t(350-355) to node350. In some embodiments, software in node350may inject packets from one of its own ingress ports designating one or more of its own egress ports to measure resident delays at these egress ports. Node355may send to node350, as part of the probe packet, approximate resident delay D(356). The controller in node350may find the latencies T1and T2using Eqs. (2.1) and (2.2) based on clock230. According to some embodiments, peer delays are measured using IEEE 1588 ‘peer-to-peer’ transparent clocking. The peer delay is obtained at node350by comparing the time stamp included by node355in the probe packet at the time of sending to a clock value in a clock circuit included in node355. Thus, in this manner software stored in memory circuit220may also update values of peer delay times between node350and other nodes. The probe packets sent from node350may be processed through any of the ports in the switch fabric included in node350. As described herein, node350may be implemented by node200ofFIG. 2, which includes switch201with ports211through218. That is, ports351, and356may each be implemented by any of ports211-218, described in detail above in relation toFIG. 2.

FIG. 4illustrates a partial view of communication links450-1and451-2among node450, node451, and node452in a network portion400, according to some embodiments. Also illustrated inFIG. 4are a peer delay t460-1, peer delay t461-2, resident delay t460, resident delay t461, and resident delay t462. According to embodiments consistent with the present disclosure, resident delay460is associated with an output port in node450that is linked to node451. Likewise, resident delay461may be associated with an output port in node451that is linked to node452, and resident delay462may be associated with an output port in node452. Thus, a delay measurement T4for a packet traversing from an egress port in node450to an ingress port in node452in network portion400includes peer delays t460-1and t461-2, and resident delay461, as follows:
T4=t460−1+t461−2+t461  (3.1)

In some embodiments consistent with the present disclosure, network portion400may have node450as a source node linked to a first host through an ingress port and node452may be a destination node linked to a second host through an egress port. In this case, host to host latency T4′ includes, in addition to peer delays t460-1and t461-2, resident delays460,461, and462, as follows:
T4′=t460−1+t461−2+t460+t461+t462  (3.2)

According to some embodiments, resident delays t460, t461, and t462may be approximated using the averaging procedure described above in relation toFIG. 2. In some embodiments, resident delays t460, t461, and t462, and transit delays t460-1and t461-2are maintained as a history of average values for switch ports. These historical link and residence latency values along with historical topology information can be used to figure network-wide latency between ingress point A (e.g., node1, cf.FIG. 1) and egress point B (e.g., node6, cf.FIG. 1).

FIG. 5illustrates a partial view of a network500according to some embodiments. Network500may have the architecture shown inFIG. 5, including sub-networks510,520, and530. In some embodiments, network500may be an Intermediate System to Intermediate System (ISIS) network, consistent with the present disclosure. In such a network, each sub-network may include level 1 nodes, which are nodes essentially interconnected within each sub-network. ISIS networks may also include level 2 nodes, which are connected with level 2 nodes from other sub-networks. Further embodiments of an ISIS network may include hybrid nodes, combining level 1 and level 2 capabilities. For example, sub-network510inFIG. 5may include a plurality of level 1 nodes such as nodes511-1,511-2, and511-3. Also, sub-network510may include a hybrid node512, which connects to level 1 nodes511-1and511-2, with hybrid node522from sub-network520, and with level 2 node533in sub-network530. Node533in sub-network530may be a level 2 node because it only connects to hybrid nodes512and522. Node521-1in sub-network520is a level 1 node.

According to embodiments disclosed herein, passive latency measurements may be calculated separately for each of the sub-networks510,520, and530, and then propagated through the entire network. For example, each sub-network510,520, and530may be modeled as a single node and used in a passive latency measurement configuration consistent with the present disclosure. Thus, the modeling is essentially self-replicating, such that complex architectures may be resolved in an iterative manner, using the basic latency measurement disclosed herein.

FIG. 6shows a flowchart for a method600for measuring latency in a network, according to some embodiments, such as using processes described herein. At step610, each node in the network measures its resident delays and creates a per port average. Thus, some embodiments avoid keeping track of every ingress-egress port combination inside the node. At step620, the peer delay between each pair of nodes in the network is measured. At step630, the latency between each pair of neighbor nodes in the network is measured. For example, at step630, the resident delay measured in step610and the peer delay measured in step620may be added for each pair of nodes in the network. At step640, each route through a number of nodes may be weighted using the latency values measured in step630. According to some embodiments, method600enables a network graph to be created with links joining neighbor nodes. In such a graph, each link is provided a weight proportional to the latency between the neighbor nodes. A graph as such may be useful in determining the shortest data transit routes for a data packet traversing from a source node to a destination node in the network.

FIG. 7Ashows a flowchart for a method700A for determining latency in a network, according to some embodiments. At step710, a network graph is created. In some embodiments, step710may be performed following steps610-640of method600described in detail above in conjunction withFIG. 6. Thus, the links joining neighbor nodes in the network graph created in step710may have a weight proportional to the latency between the neighbor nodes. At step720, all possible paths between node A and node B are identified from the network graph created in step710. For example, paths110,120, and130may be identified in step720for node1and node6(cf.FIG. 1). The selections of ingress point A (e.g., node1, cf.FIG. 1) and egress point B (e.g., node6, inFIG. 1) may be arbitrary or may depend on the particular interest of the user executing method700A. For example, in some embodiments the user executing method700A may be a network provider establishing an SLA between a server in node A, and a server in node B.

At step730, the shortest path, Lab_min, is selected from the set of all paths between nodes A and B which are identified in step720. According to some embodiments, step730may be performed using Dijkstra's algorithm, for example. A summary of Dijkstra's algorithm is disclosed in the paper by E.W. Dijkstra, “A Note on Two Problems in Connexion with Graphs,” Numerische Mathematik 1, 269-271 (1959). At step740, the longest path Lab_max is selected from the set of all paths between nodes A and B found in step720. Thus, the values Lab_min and Lab_max provide a measure of the minimum and maximum latency values expected between nodes A and B in the network. Note that according to embodiments consistent with the present disclosure, the values Lab_min and Lab_max may be varying in time, depending on specific network conditions. Furthermore, more sophisticated information may be retrieved after a set of all possible paths between nodes A and B is found in step720. For example, an average latency value may be determined, with a standard deviation.

FIG. 7Bshows a flowchart for a method700B for determining latency in a network, according to some embodiments. In method700B, steps710and720may be implemented in the same manner as correspondingly numbered steps of method700A described in conjunction withFIG. 7Aabove. At step750, method700B selects a value representing a selected number of hops. A hop is that segment of a path taken by a packet between one node and a neighbor node. According to some embodiments, a network performance parameter, such as cost, may be associated with each hop. For example, such a parameter may be the susceptibility to errors for a packet traversing between two nodes. In some embodiments, step750is used in the L2MP networks, which perform calculations on paths having equal number of hops.

At step760, all the possible paths between an ingress point A and an egress point B in the network are identified. According to some embodiments, step760may be implemented by step720in method700A, except that step760in method700B may include the limitation that the paths joining point A to point B have a given number of hops, as determined in step750. At step770, the shortest path within the set of paths found in step760is identified. Thus, in embodiments consistent with the present disclosure, the shortest path in a graph is calculated over paths including the same number of edges. At step780, the longest path within the set of paths found in step760is identified. At step790, a minimum latency; for example, by using the shortest path found in step770is identified. At step795, a maximum latency; for example, by using the longest path found in step780is determined.

According to some embodiments consistent with the present disclosure, steps described in methods600,700A, and700B may be performed by a computer in a Network Management System (NMS) having access to resident delays and peer delays for each node in a network. For example, in some embodiments a Data Center Network Management (DCNM) system may collect resident delays and peer delays for each node in a network in order to perform at least one of the steps in methods600,700A, and700B, as disclosed herein. According to some embodiments, steps included in methods600,700A, and700B may be performed by controllers and processors included in at least one of the nodes in a network. For example, steps in methods600,700A and700B may be performed by controllers such as controller205(cf.FIG. 2) in a level 2 node for an ISIS network, such as node512in sub-network510(cf.FIG. 5).

Therefore, it should be understood that the invention can be practiced with modification and alteration within the spirit and scope of the appended claims. The description is not intended to be exhaustive or to limit the invention to the precise form disclosed. It should be understood that the invention can be practiced with modification and alteration and that the invention be limited only by the claims and the equivalents thereof.