Patent Publication Number: US-9420513-B1

Title: Clustering approach to estimating a network metric for nodes

Description:
BACKGROUND 
     Large networks, such as the Internet, provide the infrastructure for many peer-to-peer systems and are now being used to provide a variety of services to users. Some recent Internet applications require high bandwidth. Live, high-quality, streaming video, video conferencing, and graphic-intensive multiplayer games are examples of high-bandwidth applications. 
     A fundamental challenge in effectively utilizing high-bandwidth network services is to provide these services and other data transmission without affecting the quality of the services. Quality of Service (QoS) routing is a major factor in providing these services. However, selecting routes that provide the performance required by the service is difficult. 
     Accurately measuring metrics for computing network routes can be difficult. This is especially true when determining bandwidth. Measuring bandwidth is a computational and resource intensive process. It is difficult to conduct bandwidth measurements for large networks, such as the Internet, having a large number of paths. Measuring simultaneously on multiple paths may cause interference to measurement tools and may generate cross traffic, thus making it difficult to get accurate measurements in real-time. Furthermore, bandwidth changes quite rapidly and the measurements need to be updated frequently. In a large network, continuously measuring bandwidth would be infeasible because of the large measurement overhead. 
     SUMMARY 
     A clustering-based method of estimating a network metric between a first node and a second node includes determining source clusters of nodes and destination clusters of nodes for each node. Cluster heads are selected for each cluster. Measurements of the network metric between each node and each cluster head for the source clusters and destination clusters are performed, and the network metric for a pair of nodes is estimated based on the measurements for the pair of nodes. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       Various features of the embodiments can be more fully appreciated, as the same become better understood with reference to the following detailed description of the embodiments when considered in connection with the accompanying figures, in which: 
         FIG. 1  illustrates a network including nodes, according to an embodiment; 
         FIG. 2  illustrates a traceroute tree, according to an embodiment; 
         FIG. 3  illustrates a flow chart of a method for estimating a network metric, according to an embodiment; and 
         FIG. 4  illustrates a computer system, according to an embodiment. 
     
    
    
     DETAILED DESCRIPTION OF THE EMBODIMENTS 
     For simplicity and illustrative purposes, the principles of the embodiments are described by referring mainly to examples thereof. In the following description, numerous specific details are set forth in order to provide a thorough understanding of the embodiments. It will be apparent however, to one of ordinary skill in the art, that the embodiments may be practiced without limitation to these specific details. In some instances, well known methods and structures have not been described in detail so as not to unnecessarily obscure the embodiments. 
     According to embodiments described herein, efficient and scalable estimation of available bandwidth for an end-to-end path is provided. In one embodiment, a clustering-based approach is used to estimate available bandwidth, where only a few measurements from each node are needed to estimate available bandwidth for any pair of nodes in the network. The clustering-based approach includes, for each node, dividing all other nodes in the network into two different sets of clusters. The two sets of clusters are source clusters and destination clusters. There are k1 number of clusters in source clusters set and k2 number of clusters in destination clusters set. A cluster head is selected for each cluster, which is a representative node from each cluster. Each node may store an identifier or address for each cluster head for each source and destination cluster, or this information may be stored in a central location. 
     Based on the stored information for each node, available bandwidth may be estimated for any pair of nodes in the network. For example, available bandwidth is measured to or from each of the pair nodes to cluster heads for relevant source and destination clusters for each of the pair of nodes. Then, available bandwidth is estimated based on the measurements. Using this technique to estimate available bandwidth, only a few available bandwidth measurements from the end hosts, which are the pair of nodes for which available bandwidth is being estimated, are needed. Also, in addition to available bandwidth, other network metrics may be estimated using this technique, including capacity and loss rate. 
     The clustering-based approach of the embodiments described herein may be used to estimate available bandwidth between a set of end hosts that are known in advance, which are the pair of nodes for which available bandwidth is being estimated. This scenario arises in many distributed applications with a set of servers that can leverage the bandwidth information between all pairs of nodes to optimize certain functionalities. For example, in a content distribution network where content needs to be distributed to different servers, we can utilize the bandwidth information to choose the synchronization paths that reduce the total transfer time. Also, the knowledge of available bandwidth between end-hosts may be used for optimizing the performance in several applications such as media-streaming systems, content distribution networks, interactive audio-video systems, and online-gaming systems. For example, in a media streaming system, the available bandwidths from a client to a set of media servers that hold the same content can be used to select a suitable server for providing the content to the client at the bandwidth needed for the high-quality media streaming. Similarly, the available bandwidth from a server to a client can be used in online gaming systems to select the quality of the gaming graphics. 
     After the available bandwidth between a pair of nodes is estimated, the available bandwidths may be stored, displayed or conveyed to a user or another node in the network. The available bandwidths may be used to select a path for transmitting data to a destination. In one example, the available bandwidth is used to select a path that meets the requirements for providing a service. For example, a service provided to a user over a network, such as the Internet, may require a minimum available bandwidth. A path is selected in the network that has an available bandwidth greater than or equal to the required minimum available bandwidth. Other network metrics, such as latency, throughput, loss rate, etc., in addition to available bandwidth, may be considered when selecting a path. 
     As used herein capacity is the maximum transmission rate of a data transmission on a link or an end-to-end path, assuming the data transmission has full access to the link or path without any other network traffic on the link or path. 
     Available bandwidth is the transmission rate of a data transmission on a link or path with other network traffic on the link or path. The network traffic typically varies over time, so the available bandwidth varies over time and is generally less stable than capacity. 
     An end-to-end path in a network between a source node and a destination node, also referred to as a path or network path, may be comprised of one or more links. The available bandwidth or capacity of a path comprised of multiple links may be characterized by the link in the path having the lowest capacity or lowest available bandwidth. This link may be referred to as the bottleneck link. 
       FIG. 1  illustrates a network  100  including nodes. An example of the network  100  includes a large-scale network, such as the Internet. However, the embodiments may be implemented in smaller networks. 
     A node is any device that may send and/or receive messages via the network and that is typically operable to perform some type of data processing. Examples of nodes include routers, servers, and end-user devices, such as personal digital assistants (PDAs), personal computers, laptops, and cellular phones. The nodes  110  may be operable to route data in the network  100  along network paths. The nodes may include intermediate routers, which are routers in a path between end hosts. 
     According to an embodiment, available bandwidth is estimated for end hosts in the network  100 , which are a pair of the nodes  110 . Typically, this includes servers and clients, which may be receiving content or services, such as streaming media, on-line gaming, etc., from the servers, but other types of nodes may be end hosts. 
     For each of the nodes  110  that may be used as end hosts, all other nodes are divided into source and destination clusters. Thus, each of the nodes  110  has a set of source clusters and destination clusters comprised of all the other nodes in the network  100 . A k1 number of source clusters and a k2 number of destination clusters may be determined, where k1 and k2 are predetermined numbers and could be independently chosen by each node depending on some metric, such as its current load, etc. For the sake of simplicity, we assume that k1=k2=k in the embodiments described below. A clustering function, described in detail below, is used to determine the source and destination clusters for each node  110 . 
       FIG. 1  shows a pair of nodes including source nodes  110   a  and destination node  110   b . A destination cluster  121  is shown for the source node  110   a . However, the source node  110   a  may have k destination clusters and k source clusters where k is greater than 1, even though those clusters are not shown. A source cluster source  120  is shown for the destination node  110   b . However, the destination node  110   b  may have k source clusters and k destination clusters where k is greater than 1, even though those clusters are not shown. 
     A cluster head is selected for each cluster of the source clusters and destination clusters for each node. For example, a node  110   y  is the cluster head for the source cluster  120 , and a node  110   z  is a cluster head for the destination cluster  121 . For each node, a network metric is measured from the node to each of the cluster heads for the node&#39;s destination clusters and a network metric is measured to the node from each of the cluster heads for the node&#39;s source clusters. For example, the source node  110   a  measures available bandwidth from itself to the cluster head  110   z , and stores the measured available bandwidth for the cluster, which is the destination cluster  121 .  FIG. 1  shows an example of a path between the source node  110   a  and the cluster head  110   z  including nodes  110   r - u  and links  131   a - d  and  131   g . The available bandwidth may be measured along this path using conventional techniques. Furthermore, well known measurement techniques for measuring available bandwidth, loss rate, capacity or other network metrics may be used. 
     Available bandwidth is also measured between the source node  110   a  and all the other cluster heads for all the other k destination clusters and all the k source clusters for the source node  110   a . These measurements are stored, for example, locally in the node  110   a  and/or in a central location, such as the bandwidth estimation server  150 . 
     Available bandwidth is also measured between the destination node  110   b  and all the cluster heads for all the k destination clusters and all the k source clusters for the destination node  110   b . These measurements are stored, for example, locally in the node  110   b  and/or in a central location, such as the bandwidth estimation server  150 . An example of a path between the destination node  110   b  and the cluster head  110   y  for the source cluster  120  for the destination node  110   b  is shown. The path includes nodes  110   u ,  110   t ,  110   s  and  110   r , and links  131   e ,  131   d ,  131   c ,  131   b , and  131   f.    
     Available bandwidth may be estimated between the source node  110   a  and the destination node  110   b  based on the stored measurements. For example, a path between the source node  110   a  and  110   b  is shown, including nodes  110   r - u  and links  131   a - e . Available bandwidth on this path is estimated based on the available bandwidth measurements between the source node  110   a  and the k cluster heads for each of the k source and destination clusters for the node  110   a  and based on the available bandwidth measurements between the destination node  110   b  and the k cluster heads for each of the k source and destination clusters for the node  110   b . In particular, according to an embodiment, a cluster is identified for each of the nodes  110   a  and  110   b  that the other node is a member of, and the available bandwidth measurements for those clusters are used to estimate available bandwidth for the node pair. 
     For example, a destination cluster for the source node  110   a  is identified of which the destination node  110   b  is a member, i.e., the destination cluster  121 . The available bandwidth measurement from the source node  110   a  to the cluster head  110   z  for the destination cluster  121  is determined. Also, a source cluster for the destination node  110   b  is identified of which the source node is a member, i.e., the source cluster  120 . The available bandwidth measurement to the destination node  110   b  from the cluster head  110   y  for the source cluster  120  is determined. The minimum of these measurements may be used as the estimation of available bandwidth for the path between the pair of nodes  110   a  and  110   b.    
     The network metric measurements, which in this example are available bandwidth measurements, for all the nodes  110  may be measured periodically and stored in the bandwidth estimation server  150 . Then, the server  150  may be queried to estimate available bandwidth for any pair of nodes based on the stored measurements. Instead of a single server  150 , a distributed storage and estimation system comprised of multiple servers in the network  100  may be used to store and estimate network metrics for a large-scale network. Other distributed solutions may also be used. In another embodiment, the nodes may be queried for their measured available bandwidths to cluster heads and the requesting node may estimate the available bandwidth. For example, a node in the system  100  needs to determine the available bandwidth between the source node  110  and the destination node  110   b . The node queries the node  110   a  for the measured available bandwidth to the cluster head  110   z , and the node queries the node  110   b  for the measured available bandwidth to the cluster head  110   y . Then, the node estimates the available bandwidth between the source node  110   a  and the destination node  110   b . In yet another embodiment, one of the nodes taking a measurement may query the other node for its measurement to estimate available bandwidth. For example, the source node  110   a  may query the destination node  110   b  for the measured bandwidth to the cluster head  110   y , and then the source node calculates an estimation of available bandwidth between the two nodes based on the measured metric. 
     As described above, for a given node in the network  100 , all other nodes are divided into source clusters and destination clusters for that node. In one embodiment, for a given node, each of the other nodes in the system may belong to only one source cluster and one destination cluster. 
     According to an embodiment, nodes that share a similar property with respect to network metric measurements from or to the given node are selected for the same cluster. For source clusters, we divide nodes based on their properties while measuring to the given node and for destination clusters, we divide nodes based on their properties as measured from the given node. For example, path similarity, in terms of the same hops or links, may be leveraged as a property to perform the clustering. For the source node  110   a , all paths from all the other nodes or a subset of all the other nodes in the network  100  are considered. These paths are referred to as source paths. Since end-hosts are typically connected to the Internet via few service providers, mostly one, most source paths will share some hops with other source paths. This property is leveraged to divide nodes into clusters such that nodes in a cluster share last few hops on their source paths to the source node  110   a . Those nodes may be clustered into a single source cluster of k source clusters formed for the source node  110   a . k may be a small number such as 1-4, but k may be larger. Similarly, k destination clusters are formed by considering all paths, i.e., destination paths, from the source node  110   a  to all the other nodes. All the other nodes are clustered such that the nodes in a cluster share first few hops from the node  110   a . For example, the destination cluster  121  for the source node  110   a  is shown. The nodes in the destination cluster  121  all share at least the first few hops in their destination paths from the node  110   a.    
     According to an embodiment, a clustering function uses path similarity and network topology information to form clusters. To determine the network topology, each node may perform traceroutes to all other nodes in the network  100  to determine all the intermediate nodes in all the paths. Traceroutes use a few small-sized packets to determine intermediate nodes and links in paths. Also, the topology of the network  100  may change slowly and is not as dynamic as available bandwidth. So, traceroutes may be periodically performed at a much slower rate than available bandwidth measurements to update the network topology information. The traceroute information may be transmitted to the server  150  to determine the network topology. 
     A tree-clustering function may be used to form the clusters. For example, the server  150  constructs a traceroute tree representative of the network topology for each of the nodes  110  from the traceroutes performed for each node. In another embodiment, instead of the server  150  constructing the traceroute tree, each node constructs its own tree and determines the clusters. 
     After constructing the tree for each node, the tree is traversed to create k source clusters or k destinations clusters. To create destination clusters, a number of children from the root of the tree is determined. Also, a number of leaves in each of the subtrees of the children are determined. Then, k is divided among each of the children based on the number of leaves in the subtree of the children. If a number of leaves is greater for one subtree, then that subtree gets more clusters. The number of clusters assigned to each child of the root may be proportional to the number of leaves in the subtrees for each child when dividing k among the children. To ensure that the divided numbers are integers, the numbers are rounded to the nearest integer while ensuring that the total is k. If the calculated portion of k to be assigned to a subtree is less than one, then that subtree may be given one cluster. If the portion of k for a subtree is greater than one, then these steps are repeated at the subtree&#39;s root with the nearest integer of the fraction as the new k. 
       FIG. 2  shows an example of a tree for the source node  110   a . The tree root, which is the source node  110   a , has two children  201  and  202 . Note that the subtree  210  for the child  201  has more leaves then the subtree  211  for the child  202 . If k=3, then dividing k among the children based on the number of leaves in each subtree may result in the child  201  having k=2 destination clusters and the child  202  having k=1 destination cluster. That is the nodes in the subtree  210  are divided into 2 clusters, and the nodes in the subtree  211  become members of a single cluster. Because the portion of k for the subtree  210  is greater than one, i.e.,  2 , the clustering steps described above are repeated at the subtree&#39;s root, which is 201, with the nearest integer of the portion of k as the new k. In this example, each subtree of the node  201  may be assigned to 1 cluster. This same procedure is repeated to determine source clusters for the node  110   a . The tree for determining the source clusters may be created from traceroute packets transmitted to the node  110   a  from all other nodes in the network. Also, source clusters and destination clusters may be formed for each node  110 . 
     After the source and destination clusters are formed for each node, cluster heads are selected. The cluster heads may be selected as a representative of all the nodes in the cluster in terms of the network metric being estimated. Cluster heads may be selected based on one or more properties, such as a least loaded node, a node with large incoming or outgoing network capacity, or a node with large incoming or outgoing available bandwidth. The accuracy of the estimation of the network metric is affected by the cluster head selection policy. Thus, a cluster head having properties maximizing the accuracy of the network metric estimation is selected. 
     In one embodiment, a node in a cluster having a maximal capacity is selected as the cluster head. The capacity is the end-to-end capacity of the path between the cluster head and the source or destination node. 
     For available bandwidth estimation using the minimum logic, a cluster heads is selected such that the bottlenecks of a path between a source or destination node and the cluster head does not lie close to the cluster head. For a source cluster of a destination node, a cluster head is selected such that the capacity from the cluster head to the destination node is greater than the capacity from any other node in the cluster to the destination node. Similarly, for a destination cluster of a source node, a cluster head is selected such that the capacity from the source node to the cluster head is greater than the capacity from the source node to any other nodes in the cluster. This step requires information about the capacity between nodes. Note that the capacities are not highly dynamic metrics and hence it is feasible to monitor all pair capacities and use it for this purpose. 
       FIG. 3  illustrates a method for estimating a network metric using a clustering approach, according to an embodiment. Examples of the network metric include but are not limited to available bandwidth, capacity, and loss rate.  FIG. 3  is described with respect to  FIGS. 1 and 2  by way of example and not limitation. 
     At step  301 , source clusters and destination clusters are determined for each node of a plurality of nodes in the network  100  shown in  FIG. 1 . For each node, clustering may be based on path similarities for paths between the node and other nodes in the network  100 . In the embodiment described with respect to  FIG. 2 , a network topology is determined, such as a traceroute tree for each node, and clustering is performed based on the tree. The clustering is performed to determine k source clusters and k destination clusters for each node. 
     At step  302 , a cluster head is determined for each cluster for each node. The cluster head may be selected such that the cluster head is representative of all the nodes in the cluster in terms of a network property. In one embodiment, capacity is used to select the cluster head. The cluster head may be selected such that a bottleneck link is not close to the cluster head. 
     At step  303 , each node measures the network metric between itself and the cluster heads for each of the source clusters and destination clusters for the node. If the network metric is available bandwidth, then available bandwidth is measured between the node and the cluster heads for the clusters for the node. 
     At step  304 , the measured network metrics for each node are stored, for example, in the bandwidth estimation server  150 . Each node may transmit the measured network metrics to the bandwidth estimation server  150  for storage. Measurements may be performed and stored periodically. 
     At step  305 , a pair of nodes, including a source node and a destination node, are selected for estimating the network metric. For example, available bandwidth needs to be determined for a path between the source node  110   a  and the destination node  110   b . These nodes are the pair of selected nodes. 
     At step  306 , a destination cluster for the source node is identified that has the destination node as a member. For example, a destination cluster for the source node  110   a  is identified of which the destination node  110   b  is a member, i.e., the destination cluster  121 . The available bandwidth measurement from the source node  110   a  to the cluster head  110   z  for the destination cluster  121  is determined from the stored measurements. 
     At step  307 , a source cluster for the destination node is identified that has the source node as a member. For example, a source cluster for the destination node  110   b  is identified of which the source node is a member, i.e., the source cluster  120 . The available bandwidth measurement from the destination node  110   b  to the cluster head  110   y  for the source cluster  120  is determined from the stored measurements. 
     At step  308 , the network metric is estimated for the pair of nodes based on the stored measurements for the cluster heads of the identified clusters. In one embodiment, the minimum of the available bandwidth measurement from the source node  110   a  to the cluster head  110   z  for the destination cluster  121  and the available bandwidth measurement from the destination node  110   b  to the cluster head  110   y  for the source cluster  120  is the estimation of the available bandwidth for the pair of nodes. 
     One or more of the steps described above may be performed by the bandwidth estimation server  150  and/or each of the nodes to estimate the network metric. 
       FIG. 4  illustrates an exemplary block diagram of a computer system  400  that may be used as a node in the network  100  or as the bandwidth estimation server  150 . The computer system  400  includes one or more processors, such as processor  402 , providing an execution platform for executing software. 
     Commands and data from the processor  402  are communicated over a communication bus  405 . The computer system  400  also includes a main memory  404 , such as a Random Access Memory (RAM), where software may be resident during runtime, and a secondary memory  406 . The secondary memory  406  includes, for example, a hard disk drive and/or a removable storage drive, representing a floppy diskette drive, a magnetic tape drive, a compact disk drive, etc., or a nonvolatile memory where a copy of the software may be stored. The secondary memory  406  may also include ROM (read only memory), EPROM (erasable, programmable ROM), EEPROM (electrically erasable, programmable ROM). In addition to software for routing and other steps described herein, routing tables, network metrics, and other data may be stored in the main memory  404  and/or the secondary memory  406 . The memories  404  and/or  406  may store the network metric measurements, node IDs for cluster heads and clusters, etc. 
     A user interfaces with the computer system  400  with one or more I/O devices  408 , such as a keyboard, a mouse, a stylus, display, and the like. A network interface  410  is provided for communicating with other nodes in the network  100 . 
     One or more of the steps of the method  300  and other steps described herein may be implemented as software embedded on a computer readable medium, such as the memory  404  and/or  406 , and executed on the computer system  400 , for example, by the processor  402 . The steps may be embodied by a computer program, which may exist in a variety of forms both active and inactive. For example, they may exist as software program(s) comprised of program instructions in source code, object code, executable code or other formats for performing some of the steps. Any of the above may be embodied on a computer readable medium, which include storage devices and signals, in compressed or uncompressed form. Examples of suitable computer readable storage devices include conventional computer system RAM (random access memory), ROM (read only memory), EPROM (erasable, programmable ROM), EEPROM (electrically erasable, programmable ROM), and magnetic or optical disks or tapes. Examples of computer readable signals, whether modulated using a carrier or not, are signals that a computer system hosting or running the computer program may be configured to access, including signals downloaded through the Internet or other networks. Concrete examples of the foregoing include distribution of the programs on a CD ROM or via Internet download. In a sense, the Internet itself, as an abstract entity, is a computer readable medium. The same is true of computer networks in general. It is therefore to be understood that those functions enumerated below may be performed by any electronic device capable of executing the above-described functions. 
     While the embodiments have been described with reference to examples, those skilled in the art will be able to make various modifications to the described embodiments without departing from the scope of the claimed embodiments.