Monitoring an interconnection network

The following description is directed to monitoring an interconnection network. In one embodiment, a method of monitoring an internal link of an interconnection network can comprise creating a network packet. The network packet can comprise a data-link-layer destination address corresponding to a management interface of a first router of the interconnection network, and a network-layer destination address corresponding to a host computer. The network-layer destination address can be within a subnet associated with a management interface of a second different router of the interconnection network. The internal link can connect the first router and the second router. The method can further comprise transmitting the network packet from the host computer, and determining one or more performance metrics of the internal link based, at least in part, on whether the network packet is received at the host computer.

BACKGROUND

Computer networks generally comprise various interconnected computing devices that can communicate with each other to exchange data. When small numbers of devices are interconnected, the devices can be directly connected to each other. For example, one device can be directly connected to another device via a network link. However, direct connections between large numbers of devices is not scalable. Thus, the connections between a large number of devices will typically be via indirect connections. For example, one device can be connected to another device via an interconnection network comprising one or more routers. Large routers for connecting many devices together can be expensive. However, large routers can be constructed from lower cost commodity equipment interconnected with a high-radix architecture.

For example, a high-radix interconnection network can comprise multiple routers interconnected by a high-radix architecture. Exemplary high-radix architectures include Clos, folded-Clos, fat-tree, butterfly, flattened-butterfly, full-mesh, and dragonfly networks. The high-radix network can comprise a large number of “externally facing ports” for connecting to and between devices outside of the high-radix architecture. For example, each device connected to an externally facing port can connect to any other device on an externally facing port of the high-radix network. The high-radix network can comprise multiple different stages or tiers of routers. One or more tiers of routers can include externally facing ports and one or more tiers of routers can be connected only to devices internal to the high-radix architecture.

An operator of the high-radix network may desire to provide high availability and throughput through the high-radix network. Thus, the operator may monitor the high-radix network for indications of dropped or lost packets, service degradation, component failures, or congestion within the network. However, as the number of nodes and links of the high-radix network increases, it can be more difficult to detect and isolate degraded components within the high-radix network.

DETAILED DESCRIPTION

Internet Protocol (IP) network traffic can be routed using commodity IP routers that are connected by an interconnection network. For example, multiple IP routers can be connected together using a high-radix or a Clos-like network architecture. For example, 64, 96, or 128 routers can be connected together in a mesh or fabric via 10 gigabit/second (10 G) network links. Compared to a single large chassis router, the commodity routers connected with a high-radix network can potentially provide cost, resilience, bandwidth, and load-balancing benefits. However, monitoring the error-free operation of the large number of links in a highly meshed network architecture can be complicated.

In one solution, one or more possible paths across the network can be monitored by sending “pings” between agents dotted around the edge of the network. A ping operates by having a requesting host computer send an Internet Control Message Protocol (ICMP) echo request packet to a target host computer and waiting for the target to reply with an ICMP response returned to the requestor. If packet loss is detected, a triangulation process can be used to try and determine which network link or device is responsible for the packet loss. In this solution, multiple host computers are used for the monitoring and a large number of host computers may be needed to get full coverage of all of the internal links of the mesh. However, even with the use of many pings, it may not be possible to isolate and test specific network links within the network or to guarantee that all desired network links have been tested.

In the methods disclosed herein, a single monitoring agent can be used to monitor the internal links of the interconnection network. For example, the monitoring agent can connect to a management interface on each network device, e.g., router, in the interconnection network and inject health probes to test the integrity of those links internal to the interconnection network and connected to that network device. The monitoring agent does not use regular IP routing for health probe injection. Instead, the monitoring agent can “forge” layer 2 headers of outgoing frames to forcibly inject the health probes that are actually addressed back to itself. The probes take a short predetermined path through the network before returning to the monitoring agent. The monitoring agent can then make a unilateral, simple, and decisive determination of the health of the internal links and routers within the interconnection network.

Turning to the Figures,FIG. 1is a system diagram showing an embodiment of a system100for monitoring an interconnection network110. The system100can comprise a host computer120including an agent122. For example, the agent122can be a software routine executing on the host computer120, such as a daemon running as a background process. The agent122can create health probes to inject into the interconnection network110and monitor for the return of the health probes. As described in more detail below, the health probes can include data for use in diagnosing the health of the interconnection network110. The health probe can be encapsulated in a frame or network packet for transmission to other computing devices. For example, the agent122can create a packet addressed to traverse a predetermined link of the interconnection network110and return to the host computer120.

The health probe can be transmitted to the interconnection network110via a layer 2 fan-out switch130. Generally, a switch includes multiple ports or interfaces and the switch can forward a frame from one port to a different port of the switch. As used herein, “layer 2” refers to the “data link” layer of the Open Systems Interconnection (OSI) model that partitions and standardizes the internal functions of a communication system into abstraction layers. Non-limiting examples of layer 2 protocols are Ethernet, Asynchronous Transfer Mode (ATM), Point-to-Point Protocol (PPP), High-level Data Link Control (HDLC), Fiber Distributed Data Interface (FDDI), and Token Ring. Thus, the layer 2 switch130can forward frames encoded in a layer 2 protocol, such as Ethernet, from one port to another port of the layer 2 switch130. In this manner, the agent122can communicate with the interconnection network110via a layer 2 network.

The layer 2 network can include multiple virtual local area networks (VLANs) and a different VLAN can be associated with each router of the interconnection network110. For example, the layer 2 network can include 96 VLANs if there are 96 routers in the interconnection network110. The host computer120can be connected to a trunk port of the layer 2 switch130by a VLAN trunk140. The VLAN trunk140is a network link that can carry frames from multiple VLANs. The layer 2 switch130can include multiple access ports, where each access port is connected to a different router of the interconnection network110. An access port can carry frames for a single VLAN. Each endpoint of a VLAN can have a layer 3 address and a layer 2 address. Thus, the host computer120can have multiple different addresses corresponding to respective VLANs of the trunk link. For example, the host computer120can have 96 layer 3 addresses and 96 layer 2 addresses when there are 96 VLANs in the layer 2 network. Layer 2 or Media Access Control (MAC) addresses are generally unique for each hardware port. Using this configuration, the agent122can send a frame to a router of the interconnection network110by transmitting the frame over the VLAN associated with the router. Further, by using multiple VLANs, the host computer120can use a single network interface controller (NIC) connected by one network link to the layer 2 switch130, but still have multiple logical interfaces for communicating with the interconnection network110.

The interconnection network110can be a layer 3 network. As used herein, “layer 3” refers to the “network” layer of the OSI model. Non-limiting examples of layer 3 protocols are IP (including IPv4 and IPv6), ICMP, Address Resolution Protocol (ARP), Internetwork Packet Exchange (IPX), and Datagram Delivery Protocol (DDP). The interconnection network110can include multiple routers, such as routers150and160, interconnected by an interconnection architecture. For example, the interconnection architecture can be a high-radix network architecture, such as described with reference toFIG. 3. For example, the interconnection network110can be a folded-Clos network with 64 tier-1 routers and 32 tier-2 routers, where the tier-1 routers have ports connected to customers via an external network (such as the Internet), and every tier-1 router is connected to every tier-2 router. Connections between routers can be by a single network link or by multiple network links. Generally, a router includes multiple interfaces or ports and the router can forward a packet from one port to a different port. The forwarding decision can be based on a layer 3 destination address, for example. Layer 3 addresses are generally based on the topology of the network. Routers150and160can each include a management port (MP) for connecting to the layer 2 network. For example, each management port can connect to a different access port of the layer 2 switch130.

It should be understood that the terms “switch” and “router” can be used interchangeably for network devices having multiple ports. For purposes of clarity and explanation, this document standardizes on the term “switch” to mean a multi-port network bridge that processes and forwards data at the data link layer (layer 2) of the OSI model, and the term “router” to mean a multi-port network device that processes and forwards data at the network layer (layer 3) of the OSI model. It should also be understood that a layer 2 fan-out switch can be a single device or multiple interconnected devices.

As the following example demonstrates, the system100can be used to monitor one or more network links of the interconnection network110. A link under test is determined by creating a health probe, e.g., a network packet, with a layer 2 destination address of a router on the transmitting end of the link under test, and a layer 3 destination address within a subnet of a router on the receiving end of the link under test. Multiple links can be tested, by creating multiple packets with addresses selected to route the packet across the respective links. The health probe is both sent from and received at the host computer120, taking a round-trip path from the host computer120, through a predetermined link, and back to the host computer120. Thus, the link under test should be connected to routers that have a direct or indirect path to the host computer120. When all of the routers of the interconnection network110are connected to the host computer120, then all of the internal links between the routers can be tested by the agent122.

For example, the links connecting the routers of the interconnection network110can be tested by the agent122. The agent122can create a health probe for testing a link of the interconnection network110. The health probe can be a unilateral, unidirectional probe that is directed towards the agent122. In other words, the health probe can be sourced by and returned to the agent122. Thus, a single agent122can both generate the probe and monitor for the probe's return. The host computer's120regular networking stack would typically prevent the health probe from being transmitted from the host computer120because the destination address resides on the originating host, e.g., the host computer120. However, the agent122can “forge” a layer 2 destination address to forcibly inject the health probe into the layer 2 network without using the host's regular networking stack. For example, the health probe transmitted by the host computer120can include a layer 2 destination address that corresponds to the management port of a router that is connected to the link under test. The health probe can include a layer 3 destination address corresponding to the host computer120so that when the interconnection network110is operating as expected, the network will return the packet to the originating host computer120after a short number of network hops (typically three).

The health probe can be transmitted on a VLAN corresponding to the management port of the router that is connected to the link under test. The host computer120can include a layer 3 IP address corresponding to each VLAN connected to the host computer120. For example, the host computer120can have an IP address 10.1.1.0 associated with VLAN 1 and an IP address 10.2.2.0 associated with VLAN 2; the management port of router150can have an IP address 10.1.1.1 associated with VLAN 1; and the management port of router160can have an IP address 10.2.2.1 associated with VLAN 2. The health probe can be forcibly sent out by the agent122on VLAN 1, with a layer 2 destination MAC address of the management interface of router150. Thus, the transmitted health probe can include a source IP address of 10.1.1.0 and a destination IP address of 10.2.2.0. The transmitted health probe can be transmitted from the host computer120to the layer 2 switch130via the VLAN trunk140, and the layer 2 switch130can forward the health probe to the management port of router150based on the layer 2 destination MAC address of the health probe.

When the health probe arrives at the router150, “normal” routing can be used to forward the probe towards the router160across the link under test. In other words, the routing information in the health probe causes the health probe to traverse a predetermined path through the interconnection network110when the link under test is functioning properly. The router150can examine the destination IP address of the health probe and determine that the next hop in the route is through the router160. As a specific example, the router150can determine that the destination IP address of 10.2.2.0 is on the same subnet as the management port of the router160and the health probe can be forwarded across the link under test to the router160.

As part of the normal routing, the health probe can be modified as it passes through components of the system100. For example, a time-to-live (TTL) field in a layer 3 header of the health probe can be decremented as the health probe passes through each layer 3 component, such as routers150and160and host computer120. As another example, a layer 2 header can be stripped from the received frame and regenerated for transmission at each layer 3 component.

When the health probe arrives at the router160, normal routing can be used to forward the probe out of the management port of the router160over VLAN 2 to the originating host computer120. Specifically, the router160can examine the destination IP address of the health probe and determine that the destination IP address of 10.2.2.0 is on the same subnet as the management port of the router160. The health probe can be forwarded through the layer 2 switch130to the originating host computer120.

The agent122can monitor for the receipt or non-receipt of the health probe at the host computer120and determine one or more performance metrics of the link under test based, at least in part, on whether the network packet is received at the host computer. For example, the agent122can determine that the link under test is down when the health probe is not received at the host computer120within a predetermined time interval after the health probe is transmitted. The predetermined time interval can be set based on the expected number of hops through the network and a desired latency through each component of the network. As another example, the agent122can determine that the link under test is down when the received health probe comprises a TTL field having a value less than a predetermined value. For example, the health probe will typically traverse a router on the transmitting end of the link under test, a router on the receiving end of the link under test, and the host computer120. Thus, the TTL field will typically be decremented by three. However, the health probe may take an alternate, longer path through the interconnection network110due to a problem with a network link or component of the interconnection network110. In this case, the TTL field will be decremented by more than expected, so a TTL field that is less than expected can indicate a problem with the interconnection network110.

The agent122can correlate data from multiple health probes to determine one or more performance metrics of the link under test. For example, the latency or delay of a health probe through the system100can be measured by the agent122. The latency of a health probe can be measured by taking a difference of the time when the health probe is received at the agent122and a time when the health probe is transmitted from the agent122. The latency can be stored and compared to latencies of other health probes sent across the same link under test. A jitter or packet delay variation can be calculated based on the latencies of multiple health probes. For example, jitter can be calculated as a deviation from the mean or average latency over a single link. As another example, jitter can be calculated as a deviation from the mean or average latency over multiple links. The agent122can determine that the internal link is congested when the jitter exceeds a predetermined threshold. As another example, a count or percentage of lost health probes over a period of time through the link under test can be indicative of a link that is partially functional. For example, if one out of 200 health probes are dropped or corrupted by a link then the link may be partially functional and in need of maintenance. A partially functional link may indicate that a connector of the link is not seated properly or a laser associated with the link is attenuating over time, etc.

The agent122can correlate data from multiple health probes to determine one or more performance metrics of components associated with the link under test. For example, the performance metrics of multiple links associated with a router can be analyzed to determine a performance metric of the router. For example, if all of the links of a particular router are down or experiencing a high latency, then the particular router can be the source of the problem. Similarly, if only forty percent of the health probes traversing the router are returned, the router can be the source of the problem. Problems of this nature may be indicative of the router having a faulty or “hung” central processor unit, corrupt memory, or a faulty or hung application-specific integrated circuit (ASIC). Thus, it may be desirable to reboot the router or to take the router off-line for maintenance.

FIG. 2shows an example of a health probe200used in a system for monitoring an interconnection network, such as the interconnection network110. The health probe200can comprise a network packet including information corresponding to multiple layers of the OSI model. For example, the health probe200can comprise a layer 2 frame210including a layer 2 header220and a layer 2 payload230. Generally, a header is a data structure that is used by peers to communicate with each other. The format of the header is determined based on the specific networking protocol associated with the header. Thus, an Ethernet header can be different from a HDLC header, for example. However, there can be common fields between different layer 2 protocols. For example, the layer 2 header220can comprise a source address222and a destination address224. The source address222can be a layer 2 address (such as a MAC address) corresponding to a node in the layer 2 network that originated the frame. The destination address224can be a layer 2 address corresponding to a receiving node in the layer 2 network. Thus, the source address222of the transmitted health probe200can correspond to an address of the host computer120, and the destination address224can correspond to the router of the interconnection network110that is connected to the transmitting end of the link under test. The source address222of the returning health probe200can correspond to the router of the interconnection network110that is connected to the receiving end of the link under test, and the destination address224can correspond to an address of the host computer120. The layer 2 header220can comprise a VLAN tag226for identifying the VLAN associated with the frame. As described above with reference toFIG. 1, the health probe200can be sent over a first VLAN and returned over a second VLAN.

The layer 2 frame210can encapsulate health probe data and higher level routing information. For example, the layer 2 frame210can encapsulate a layer 3 packet240. Specifically, the layer 2 payload230can include the layer 3 packet240. The layer 3 packet240can include a layer 3 header250and a layer 3 payload260. The layer 3 header250can include a source address252, a destination address254, and a TTL field256. The source address252can be a layer 3 address (such as an IP address) corresponding to a node that originated the packet. The destination address254can be a layer 3 address corresponding to a receiving node of the packet. Since the source and destination of the health probe200can be the host computer120, the source address252of the transmitted health probe200can correspond to a first address of the host computer120, and the destination address254can correspond to a second address of the host computer120. For example, the source address252can correspond to an IP address associated with a first VLAN and the destination address254can correspond to an IP address associated with a second VLAN.

Generally, the TTL field256can be used to prevent a packet from persisting in the network for an undesirable amount of time, such as if the packet is looping in the network. The TTL field256can be written with an initial value greater than zero, and each layer 3 node can decrement the TTL field256by one as the packet passes through the node. When the TTL field256is decremented to zero, the packet can be discarded. The TTL field256of the transmitted health probe200can be programmed with an initial value greater than the expected hop count through the interconnection network. The TTL field256of the returning health probe200can be analyzed, as described above, to determine if the link under test is fully or intermittently down.

The layer 3 frame240can encapsulate health probe data and higher level routing information. For example, the layer 3 frame240can encapsulate a layer 4 packet270. Specifically, the layer 3 payload260can include the layer 4 packet270. The layer 4 packet270can include a layer 4 header280and a layer 4 payload290. The layer 4 header280can include a User Datagram Protocol (UDP) destination port282and a UDP source port284. The UDP destination port282and the UDP source port284can be configured to provide “entropy” across a link aggregation group (LAG). For example, providing entropy can include randomizing or programmatically setting the UDP destination port282and a UDP source port284such that multiple health probes hash to and traverse all the members (e.g., links) of the LAG. A LAG can include multiple network links connected between the same two routers. By bundling, or aggregating the links from one router to a second router, the bandwidth between the routers can potentially be increased proportionally to the number of links bundled. For example, bundling four 10 G links between routers can potentially increase the bandwidth from 10 gigabit/second to 40 gigabit/second. The router will typically be configured to create a fair distribution of traffic between the links based on the source address252, the destination address254, and the layer 4 header280. For example, the router can use a round-robin or hashing algorithm based on the source address252, the destination address254, and the layer 4 header280to determine which one of the aggregated links will transmit the packet. In one embodiment, the transmitted health probe200can include a randomized UDP destination port282and UDP source port284to potentially create an equitable distribution across aggregated links. In an alternate embodiment, the transmitted health probe200can target a specific link of the LAG by configuring the UDP destination port282and the UDP source port284based on the hash function of the router.

The layer 4 payload290can include a timestamp292and an identifier294. The identifier294can be used to uniquely identify the health probe200over a pre-determined period of time or number of packets. For example, the identifier294can be used to uniquely identify the health probe200over fifteen seconds. The identifier294can include a field for identifying the host computer120and the agent122that originated the health probe200. Thus, if other hosts or agents are creating health probes, the identifier294can guard against accidental cross-talk between health probes generated on other hosts and/or agents.

The timestamp292can correspond to the time when the health probe200is injected into the system100. The latency of the health probe200can be determined by taking a difference between the timestamp of when the health probe200arrives at the host computer120and the timestamp292. In an alternative embodiment, the time when the health probe200is injected into the system100can be recorded in a table indexed by the identifier294.

While the layer 4 packet270depicted in the example health probe200is a UDP packet, other layer 4 network protocol packet types can be used. For example, a TCP packet can be used as the layer 4 packet270(e.g., including TCP source and destination ports which can be used for LAG testing). As another example, a custom layer 4 packet can be used as the layer 4 packet270. When a custom layer 4 packet is used, the routers of the interconnection network may be custom programmed to allow for LAG testing.

FIG. 3illustrates an embodiment of a two-tier folded Clos interconnection network300. Generally, the interconnection network300can be a high-radix interconnection network, such as a Clos, folded-Clos, fat-tree, butterfly, flattened-butterfly, full-mesh, or dragonfly network, for example. The interconnection network300can include multiple tiers of routers, such as a first tier310and a second tier320of routers. The first tier310can include routers311-314and the second tier320can include routers321-323, for example. Alternative embodiments can include two or more tiers and/or can include more or fewer routers in each tier. As one example, a two-tier folded Clos network can include 64 routers in the first tier and 32 routers in the second tier. One or more routers of the first tier310can include externally facing ports for communicating with devices outside of the interconnection network300. Each of the routers of the first tier310can be connected to one or more routers of the second tier320. For example, respective routers311-314of the first tier310are connected to each router321-323of the second tier320via internal links, where an internal link is a network link that connects devices only within the interconnection network300. Routers within a tier may not be connected to each other. For example, none of the routers311-314of the first tier310connect to each other and none of the routers321-323of the second tier320connect to each other. Each of the routers of the second tier320can be connected to one or more routers of the interconnection network300via internal links.

The host computer120can be connected to one or more routers of the interconnection network300. In one embodiment, the host computer120can be connected to one or more routers of the interconnection network300via one or more fan-out switches configured to carry network traffic of multiple VLANs, such as described with reference toFIG. 1. Thus, the host computer120can be connected by one physical network link and multiple logical interfaces to the routers of the interconnection network300. In an alternative embodiment, the host computer120can be connected to one or more routers of the interconnection network300via a separate NIC for each router. It may be desirable to use a fan-out switch so that fewer NICs can be used to connect the host computer120to the routers of the interconnection network300. Connecting the host computer120to the routers of the interconnection network300can enable internal links of the interconnection network300to be monitored even when customer traffic is routed away from the internal links. For example, a router can be configured so that traffic from an externally facing port (e.g., customer traffic) of the interconnection network300does not traverse any internal links connected to the router, such as when the router is believed to be unhealthy or degraded. For example, an internal link can be considered degraded when packet loss is detected (e.g., when a percentage of health probes sent along the internal link do not arrive). If a router is believed to be unhealthy, the routing attributes (e.g., the OSPF metrics) associated with the router can be weighted to push customer traffic away from the unhealthy router. However, by addressing the health probe to a connected interface on the unhealthy router, the health probe can still be routed to the unhealthy router. The unhealthy router can be replaced with a different router and the internal links of the new router can be monitored with the health probes prior to restoring customer traffic to the router (by returning the routing attributes to normal). In comparison, a health monitoring service with agents connected to the externally facing ports would have its health probes routed away from the unhealthy router along with the customer traffic.

The agent122can discover the nodes of the interconnection network300. It can be desirable for the interconnection network300to have a regular architecture with a well-known structure in order to reduce the amount of discovery of the interconnection network300. By using a regular architecture, the agent122is not required to perform repeated network discovery with “traceroute” or polling of an Interior Gateway Protocol (IGP) database. Rather, the agent122can be configured with information detailing which routers are in which tier (e.g., tier1, tier2, . . . tier n) and which variant of high-radix architecture is used (such as Clos, folded-Clos, fat-tree, butterfly, flattened butterfly, full-mesh, or dragonfly) for the interconnection network300. Alternatively, the agent122can be programmed with the structure of the interconnection network300(e.g., such that discovery is not needed).

The number of routers at each tier can be discovered by using a regular address structure for the addresses of the management ports of the routers. Thus, the same address structure can be re-used for each similar interconnection network that is being managed. For example, the devices of the first tier310can be addressed using /31 subnets out of a reserved /22 address space and the devices of the first tier310can be reachable from the NIC of the host computer120on VLANs 1 through 512. It should be understood that a “/31” subnet is Classless Inter-Domain Routing (CIDR) notation referring to an IP address with a routing prefix of 31 address bits, leaving one address bit available to identify two different hosts (such as the host computer120and a management port of a device of the first tier310). The devices of the second tier320can be addressed using /31 subnets out of a reserved /23 address space and the devices of the second tier320can be reachable from the NIC of the host computer120on VLANs 513 through to 768. Devices of a third tier (not shown) can be addressed using /31 subnets out of a reserved /24 address space and the devices of the third tier can be reachable from the NIC of the host computer120on VLANs 769 through to 896. The host computer120can be pre-configured with all 896 VLANs and /31 subnets. The agent122can ping the remote end of each /31 subnet to learn how many devices are in the first tier310, second tier320, and third tier of the architecture. The agent122can learn the MAC address of the remote ends of the /31s to enable the health probe injection.

Based on the architecture type and the number of devices at each tier, the agent122can determine which devices of the first tier310are connected to which devices of the second tier320, and which devices of the second tier320are connected to which devices of the third tier, and so on, without any further network discovery. Based on the connectivity of the devices of the interconnection network300, the agent122can determine all of the internal links of the interconnection network300and health probes can be sent across all of the internal links to test the interconnection network300. Alternatively, an explicit list of all of the internal links to test can be maintained, and health probes can be sent only to the internal links on the list. Thus, when a problematic link is found, the link can be removed from the list to prevent the agent122from sending redundant alarms about the problematic link. In some embodiments, an explicit list of the internal links to test is maintained. For example, the list can indicate some or all of the internal links that are present in the interconnection network (e.g., only some of all the possible internal links may be cabled) and/or some or all of the internal links that are currently configured in the interconnection network (e.g., some links may be taken out of service).

In an alternative embodiment, the interconnection network300can be monitored by two or more host computers to potentially improve the resiliency of the monitoring. When a second host computer is used for the monitoring, the VLAN numbering can be the same as for the host computer120, but the IP addressing for the second host computer can come out of another set of reserved /22, /23, /24 address spaces and the network devices can be configured to include secondary addresses on the management interfaces of the network devices. Alternatively, the /31 subnets (2 addresses) can be increased to /29 subnets and each of the host monitors can be assigned to different addresses within the /29 subnet; the reserved /22, /23, /24 address spaces above can also be increased to /20, /21, /22 address spaces to accommodate the larger /29 subnet. When multiple monitoring hosts are present, a quorum system can be implemented, where the monitoring hosts responsible for the interconnection network300vote on whether a link is problematic prior to calling in an issue to a central monitoring agent.

FIG. 4shows a flow diagram of an example method400for monitoring an interconnection network, such as the interconnection network300ofFIG. 3. At410, a health probe packet can be created. Generally, the packet can be addressed to traverse a predetermined link of the interconnection network and return to the host computer that sends the packet. As an example, the predetermined link can be network link330of the interconnection network300. The packet can comprise a data-link-layer destination address corresponding to an interface of a first router of the interconnection network, and a network-layer destination address corresponding to a host computer. The first router can be the router connected to the transmitting end of the predetermined link. For example, the data-link-layer destination address corresponding to the interface of the first router can be the MAC address of a management interface of router311. The network-layer destination address corresponding to the host computer can be an IP address corresponding to an interface of the host computer120that is within the subnet associated with the management interface of a second router. The second router can be the router on the receiving end of the predetermined link. For example, the network-layer destination address corresponding to the host computer can be an IP address assigned to the host computer that is on the same subnet as a management interface of router321. The health probe packet can include other information such as a time-stamp, a unique identifier, a TTL field, a network layer source address, a VLAN tag, and/or an UDP source and destination ports, for example.

At420, the packet can be transmitted from the host computer. For example, the packet can be transmitted from the host computer120over a first VLAN to the management interface of router311. A timer can be started or a time value can be stored in association with an identifier for the packet when the packet is transmitted. When the interconnection network300is working properly, the router311can transmit the packet to the next hop in the network path of the packet based on the network-layer destination address of the health probe packet. Thus, router311can transmit the packet across the predetermined link, e.g., link330, to the router321. However, the packet can get dropped or corrupted if the interconnection network300is not working properly, such as if there is a problem with routers311or321or link330. The packet can get delayed if there is congestion on routers311or321or link330. The packet can be transmitted from the management interface of router321over a second VLAN to the host computer120, where the network-layer destination address is associated with the second VLAN.

At430, one or more performance metrics of the internal link can be determined based, at least in part, on whether the packet is received at the host computer. It can be determined that the internal link is down if the packet is not received within a predetermined time interval. If a packet is received, the contents of the received packet can be analyzed to verify that the packet was sent by the host computer120and that the packet is not corrupt. For example, the identifier and the network layer source address of the packet can be examined to determine that the host computer120sent the packet. The TTL field can be compared to a predetermined value of the TTL field. It can be determined that the internal link is down if the TTL is less than the predetermined value. A latency of the packet can be determined by taking the difference between the timestamps when the packet was received and when the packet was transmitted. The latency of the packet can be compared to the latency of other packets using statistical techniques. Using statistical techniques, the internal link can be monitored over time and/or devices associated with multiple links can be monitored. For example, a jitter of the internal link can be determined, and it can be determined that the link is congested based, at least in part, on the jitter exceeding a predetermined threshold. The jitter can be determined by comparing the latency of the packet to a mean or average of the latencies of other packets transmitted either over the same internal link or over multiple links. The performance metrics of the internal link can be correlated to performance metrics of a different internal link to determine performance metrics of a router of the interconnection network. For example, if multiple internal links connected to a network device appear problematic, then the source of the problem can be the network device.

FIG. 5shows a flow diagram of an example method500for monitoring an interconnection network. At510, an internal link of a high-radix network can be selected to test. The internal link can connect a first router and a second router. For example, the internal link can be the link330, connecting router311and321.

At520, a health probe packet can be created. The packet can comprise a MAC destination address corresponding to an interface of the first router, and an IP destination address corresponding to a second interface of a host computer. For example, the MAC destination address can be the MAC address corresponding to the management interface of the router311, and the IP destination address can be the IP address corresponding to an interface of the host computer120, such as the interface connected to the subnet associated with the management port of the router321.

At530, the packet can be transmitted from a first interface of the host computer. For example, the packet can be transmitted from an interface connected to the subnet associated with the management port of the router311.

At540, one or more performance metrics of the internal link can be determined based, at least in part, on whether the packet is received at the second interface of the host computer. For example, one or more performance metrics of the internal link330can be determined based, at least in part, on whether the packet is received at the second interface of the host computer120.

At550, it can be determined if there are more internal links to test, and if there are more internal links to test, the method500can continue at510. For example, the host computer120can be connected to every router of the high-radix interconnection network and the host computer120can be configured to test each individual internal link of the high-radix network. In other words, the agent122can test all internal links by looping over all possible links connecting the routers of the high-radix network. As another example, all of the internal links associated with a network device of the high-radix network can be tested to determine if the network device is behaving properly. As yet another example, a single internal link can be tested multiple times in succession to determine if the internal link has an intermittent or “gray” failure manifested by occasional packet loss or corruption.

FIG. 6is a computing system diagram of a network-based compute service provider600that illustrates one environment in which embodiments described herein can be used. By way of background, the compute service provider600(i.e., the cloud provider) is capable of delivery of computing and storage capacity as a service to a community of end recipients. In an example embodiment, the compute service provider600can be established for an organization by or on behalf of the organization. That is, the compute service provider600may offer a “private cloud environment.” In another embodiment, the compute service provider600supports a multi-tenant environment, wherein a plurality of customers operate independently (i.e., a public cloud environment). Generally speaking, the compute service provider600can provide the following models: Infrastructure as a Service (“IaaS”), Platform as a Service (“PaaS”), and/or Software as a Service (“SaaS”). Other models can be provided. For the IaaS model, the compute service provider600can offer computers as physical or virtual machines and other resources. The virtual machines can be run as guests by a hypervisor, as described further below. The PaaS model delivers a computing platform that can include an operating system, programming language execution environment, database, and web server. Application developers can develop and run their software solutions on the compute service provider platform without the cost of buying and managing the underlying hardware and software. The SaaS model allows installation and operation of application software in the compute service provider. In some embodiments, end users access the compute service provider600using networked client devices, such as desktop computers, laptops, tablets, smartphones, etc. running web browsers or other lightweight client applications. Those skilled in the art will recognize that the compute service provider600can be described as a “cloud” environment.

The particular illustrated compute service provider600includes a plurality of server computers602A-602D. While only four server computers are shown, any number can be used, and large centers can include thousands of server computers. The server computers602A-602D can provide computing resources for executing software instances606A-606D. In one embodiment, the instances606A-606D are virtual machines. As known in the art, a virtual machine is an instance of a software implementation of a machine (i.e. a computer) that executes applications like a physical machine. In the example of virtual machine, each of the servers602A-602D can be configured to execute a hypervisor608or another type of program configured to enable the execution of multiple instances606on a single server. Additionally, each of the instances606can be configured to execute one or more applications.

It should be appreciated that although the embodiments disclosed herein are described primarily in the context of virtual machines, other types of instances can be utilized with the concepts and technologies disclosed herein. For instance, the technologies disclosed herein can be utilized with storage resources, data communications resources, and with other types of computing resources. The embodiments disclosed herein might also execute all or a portion of an application directly on a computer system without utilizing virtual machine instances.

One or more server computers604can be reserved for executing software components for managing the operation of the server computers602and the instances606. For example, the server computer(s)604can execute a management component610. A customer can access the management component610to configure various aspects of the operation of the instances606purchased by the customer. For example, the customer can purchase, rent or lease instances and make changes to the configuration of the instances. The customer can also specify settings regarding how the purchased instances are to be scaled in response to demand. The management component can further include a policy document to implement customer policies. An auto scaling component612can scale the instances606based upon rules defined by the customer. In one embodiment, the auto scaling component612allows a customer to specify scale-up rules for use in determining when new instances should be instantiated and scale-down rules for use in determining when existing instances should be terminated. The auto scaling component612can consist of a number of subcomponents executing on different server computers602or other computing devices. The auto scaling component612can monitor available computing resources over an internal management network and modify resources available based on need.

A deployment component614can be used to assist customers in the deployment of new instances606of computing resources. The deployment component can have access to account information associated with the instances, such as who is the owner of the account, credit card information, country of the owner, etc. The deployment component614can receive a configuration from a customer that includes data describing how new instances606should be configured. For example, the configuration can specify one or more applications to be installed in new instances606, provide scripts and/or other types of code to be executed for configuring new instances606, provide cache logic specifying how an application cache should be prepared, and other types of information. The deployment component614can utilize the customer-provided configuration and cache logic to configure, prime, and launch new instances606. The configuration, cache logic, and other information may be specified by a customer using the management component610or by providing this information directly to the deployment component614. The instance manager can be considered part of the deployment component.

Customer account information615can include any desired information associated with a customer of the multi-tenant environment. For example, the customer account information can include a unique identifier for a customer, a customer address, billing information, licensing information, customization parameters for launching instances, scheduling information, auto-scaling parameters, previous IP addresses used to access the account, etc.

An interconnection network630, as disclosed herein, can be utilized to interconnect the server computers602A-602D and the server computer(s)604. The interconnection network630can be a high-radix interconnection network, such as a Clos, folded-Clos, fat-tree, butterfly, flattened-butterfly, full-mesh, or dragonfly network, for example. The server computers602A-602D and the server computer(s)604can be connected to externally facing ports of the interconnection network630. A Wide Area Network (WAN)640can be connected to externally facing ports of the interconnection network630so that end users can access the compute service provider600. It should be appreciated that the network topology illustrated inFIG. 6has been simplified and that many more networks and networking devices can be utilized to interconnect the various computing systems of the service provider600.

The host computer120can be connected to the interconnection network630via a dedicated layer 2 network. For example, a dedicated layer 2 switch (or combination of switches) (not shown inFIG. 6) can be used to connect the host computer120to a management interface of each router of the interconnection network630. The layer 2 switch can include a VLAN trunk for connecting to a NIC of the host computer120and multiple access ports, each access port associated with only one VLAN for connecting to a single router of the interconnection network630. Each VLAN can be associated with a private IP subnet that is not accessible from outside of the interconnection network630. Thus, the health probe traffic can stay interior to the interconnection network630. By using a dedicated layer 2 network for the health probes, the same address space can potentially be used for other interconnection networks of the compute service provider600, which can potentially simplify the configuration of the agent122.

The host computer120can include a second NIC (not shown) for connecting to the server computer(s)604and/or the server computers602A-602D. The interface associated with the second NIC can be used to communicate with the host computer120to manage the host computer120and to retrieve health data about the interconnection network630. For example, the agent122can operate as a web service that is accessible to the server computer(s)604and/or the server computers602A-602D. Web services are commonly used in cloud computing. A web service is a software function provided at a network address over the web or the cloud. Clients initiate web service requests to servers and servers process the requests and return appropriate responses. The client web service requests are typically initiated using, for example, an API request. For purposes of simplicity, web service requests will be generally described below as API requests, but it is understood that other web service requests can be made. An API request is a programmatic interface to a defined request-response message system, typically expressed in JSON or XML, which is exposed via the web—most commonly by means of an HTTP-based web server. Thus, in certain implementations, an API can be defined as a set of Hypertext Transfer Protocol (HTTP) request messages, along with a definition of the structure of response messages, which can be in an Extensible Markup Language (XML) or JavaScript Object Notation (JSON) format. The API can specify a set of functions or routines that perform an action, which includes accomplishing a specific task or allowing interaction with a software component. When a web service receives the API request from a client device, the web service can generate a response to the request and send the response to the endpoint identified in the request.

FIG. 7depicts a generalized example of a suitable computing environment700in which the described innovations may be implemented. The computing environment700is not intended to suggest any limitation as to scope of use or functionality, as the innovations may be implemented in diverse general-purpose or special-purpose computing systems. For example, the computing environment700can be any of a variety of computing devices (e.g., desktop computer, laptop computer, server computer, tablet computer, etc.)

With reference toFIG. 7, the computing environment700includes one or more processing units710,715and memory720,725. InFIG. 7, this basic configuration730is included within a dashed line. The processing units710,715execute computer-executable instructions. A processing unit can be a general-purpose central processing unit (CPU), processor in an application-specific integrated circuit (ASIC) or any other type of processor. In a multi-processing system, multiple processing units execute computer-executable instructions to increase processing power. For example,FIG. 7shows a central processing unit710as well as a graphics processing unit or co-processing unit715. The tangible memory720,725may be volatile memory (e.g., registers, cache, RAM), non-volatile memory (e.g., ROM, EEPROM, flash memory, etc.), or some combination of the two, accessible by the processing unit(s). The memory720,725stores software780implementing one or more innovations described herein, in the form of computer-executable instructions suitable for execution by the processing unit(s).

A computing system may have additional features. For example, the computing environment700includes storage740, one or more input devices750, one or more output devices760, and one or more communication connections770. An interconnection mechanism (not shown) such as a bus, controller, or network interconnects the components of the computing environment700. Typically, operating system software (not shown) provides an operating environment for other software executing in the computing environment700, and coordinates activities of the components of the computing environment700.

The tangible storage740may be removable or non-removable, and includes magnetic disks, magnetic tapes or cassettes, CD-ROMs, DVDs, or any other medium which can be used to store information in a non-transitory way and which can be accessed within the computing environment700. The storage740stores instructions for the software780implementing one or more innovations described herein.

The input device(s)750may be a touch input device such as a keyboard, mouse, pen, or trackball, a voice input device, a scanning device, or another device that provides input to the computing environment700. The output device(s)760may be a display, printer, speaker, CD-writer, or another device that provides output from the computing environment700.