Neighbor monitoring in a hyperscaled environment

Abstract

A network of N nodes performs a monitoring method, where the method is performed by each node. The N nodes are partitioned into domains according to a sorted order. The domains include a local domain in which the node is located and one or more remote domains. Each remote domain has a domain head designated to monitor member nodes in the remote domain. The node sends probes at a given frequency to actively monitored nodes that include all other member nodes in the local domain and domain heads in the remote domains. The node then determines whether each of the actively monitored nodes is up based on replies received from the actively monitored nodes in response to the probes.

What is claimed is: 
     
       1. A method for monitoring a network of N nodes, the method comprising:
 partitioning, by a first node, a subset of nodes from the N nodes into a domain according to a sorted order, the domain overlapping with one or more of (N−1) domains partitioned by the rest of the N nodes, wherein the domain includes a local domain in which the first node is located and the domain is associated with one or more remote domains, the one or more remote domains being respective local domains of one or more remote nodes, the one or more remote nodes monitoring a state of all the nodes in the network with the first node; 
 sending probes at a given frequency to actively monitored nodes that include all other member nodes in the local domain and the one or more remote nodes in the one or more remote domains; and 
 determining whether each of the actively monitored nodes is up based on replies received from the actively monitored nodes in response to the probes. 
 
     
     
       2. The method of  claim 1 , wherein partitioning the number of nodes further comprises:
 setting up the local domain to include a sequence of M nodes in the sorted order with the first node being the first of the sequence, wherein M is a size of the local domain. 
 
     
     
       3. The method of  claim 1 , wherein partitioning the subset of nodes further comprises:
 designating one node in the local domain as a domain head for one of the one or more remote domains; and 
 setting up said remote domain based on a local domain reported by the domain head. 
 
     
     
       4. The method of  claim 1 , further comprising:
 storing, in a memory of the first node, a domain record identifying the member nodes in the local domain. 
 
     
     
       5. The method of  claim 1 , further comprising:
 storing, in a memory of the first node, an enhanced domain record identifying the member nodes in the local domain, and, for each member node, recording an up or down state and a generation identifier that is incremented each time the member node's local domain changes. 
 
     
     
       6. The method of  claim 1 , further comprising:
 broadcasting a domain event to all of the nodes in the network upon detecting a change in the local domain, wherein the domain event is one of a node addition event, a node removal event, a node up event and a node down event. 
 
     
     
       7. The method of  claim 6 , further comprising:
 broadcasting a domain record when the domain event is the node addition event or the node removal event, wherein the domain record identifies the member nodes in the local domain; and 
 broadcasting an identifier of a downed node when the domain event is the node down event or the node up event. 
 
     
     
       8. The method of  claim 1 , further comprising:
 receiving, from a second node in the network, a domain event indicating that a third node in the network is down; and 
 sending one or more confirmation probes to the third node in response to the domain event until one of following conditions is satisfied, the conditions including: the third node responds, a pre-determined number of confirmation probes have been left unresponded by the third node, and another domain event is received from a fourth node in the network indicating that the third node is down. 
 
     
     
       9. The method of  claim 1 , further comprising:
 detecting from a reported domain record from one of the one or more remote nodes that said remote node and the first node have different network views; and 
 truncating the reported domain record immediately before a first mismatched node, at which the reported domain record does not match the first node's network view. 
 
     
     
       10. The method of  claim 1 , further comprising:
 detecting an addition or a removal of a given node in the network; and 
 re-calculating a size of the local domain according to an updated value of N; and 
 updating membership of the domains and re-designating the domain heads. 
 
     
     
       11. A first node in a network of N nodes, the first node adapted to monitor the N nodes collaboratively with the N nodes, the first node comprising:
 a circuitry adapted to cause the first node to:
 partition a subset of nodes from the N nodes into a domain according to a sorted order, the domain overlapping with one or more (N−1) domains partitioned by the rest of the N nodes, wherein the domain includes a local domain in which the first node is located and the domain is associated with one or more remote domains, the one or more remote domains being respective local domains of one or more remote nodes, wherein the one or more remote nodes monitor a state of all the nodes in the network with the first node; 
 send probes at a given frequency to actively monitored nodes that include all other member nodes in the local domain and the one or more remote nodes in the one or more remote domains; and 
 determine whether each of the actively monitored nodes is up based on replies received from the actively monitored nodes in response to the probes. 
 
 
     
     
       12. The first node of  claim 11 , wherein the circuitry is further adapted to cause the first node to:
 sort the N nodes using a same sorting algorithm as all other nodes in the network, on a same set of numerical representations of the N nodes, wherein a numerical representation of any node in the network is one of: a numerical identifier, a hash value of the numerical identifier, and a mapped value of the numerical identifier. 
 
     
     
       13. The first node of  claim 11 , wherein the circuitry is further adapted to cause the first node to: calculate a size of the local domain, M, as equal to the ceiling of 
       
         
           
             
               
                 ( 
                 
                   N 
                   2 
                 
                 ) 
               
               . 
             
           
         
       
     
     
       14. The first node of  claim 13 , wherein the circuitry is further adapted to cause the first node to:
 set up the local domain to include a sequence of M nodes in the sorted order with the first node being the first of the sequence. 
 
     
     
       15. The first node of  claim 11 , wherein the circuitry is further adapted to cause the first node to:
 designate one node in the local domain as a domain head for one of the one or more remote domains; and 
 set up said remote domain based on a local domain reported by the domain head. 
 
     
     
       16. The first node of  claim 11 , wherein the circuitry is further adapted to cause the node to:
 store, in a memory of the first node, a domain record identifying the member nodes in the local domain. 
 
     
     
       17. The first node of  claim 16 , wherein the circuitry is further adapted to cause the first node to:
 send the domain record to a node that is newly added to the network upon establishing a link to the newly added node. 
 
     
     
       18. The first node of  claim 11 , wherein the circuitry is further adapted to cause the first node to:
 store, in a memory of the first node, an enhanced domain record that identifies the member nodes in the local domain, and, for each member node, records an up or down state and a generation identifier that is incremented each time the member node's local domain changes. 
 
     
     
       19. The first node of  claim 18 , wherein the circuitry is further adapted to cause the node to:
 send the enhanced domain record with each probe and each reply to a received probe. 
 
     
     
       20. The first node of ef  claim 11 , wherein the circuitry is further adapted to cause the first node to:
 broadcast a domain event to all of the nodes in the network upon detecting a change in the local domain, wherein the domain event is one of a node addition event, a node removal event, a node up event and a node down event. 
 
     
     
       21. The first node of  claim 20 , wherein the circuitry is further adapted to cause the first node to:
 broadcast a domain record when the domain event is the node addition event or the node removal event, wherein the domain record identifies the member nodes in the local domain; and 
 broadcast an identifier of a downed node when the domain event is the node down event or the node up event. 
 
     
     
       22. The first node of  claim 11 , wherein the circuitry is further adapted to cause the first node to:
 receive, from a second node in the network, a domain event indicating that a third node in the network is down; and 
 send one or more confirmation probes to the third node in response to the domain event until one of following conditions is satisfied, the conditions including: the third node responds, a pre-determined number of confirmation probes have been left unresponded by the third node, and another domain event is received from a fourth node in the network indicating that the third node is down. 
 
     
     
       23. The first node of  claim 11 , wherein the circuitry is further adapted to cause the node to:
 send confirmation probes in round robin to all nodes in each remote domain excluding the domain head at a second frequency per node, wherein the second frequency is lower than the given frequency. 
 
     
     
       24. The first node of  claim 11 , wherein the circuitry is further adapted to cause the first node to:
 detect from a reported domain record from one of the one or more remote nodes that said remote node and the first node have different network views; and 
 truncate the reported domain record immediately before a first mismatched node, at which the reported domain record does not match the node's network view. 
 
     
     
       25. The first node of  claim 11 , wherein the domain partitioned by the first node and the (N−1) domains partitioned by the rest of the N nodes form a K-level hierarchy of the N nodes, and wherein each Kth-level domain is composed of a set of (K−1)th-level domains, K being an integer that is at least 2. 
     
     
       26. The node of  claim 25 , wherein the circuitry is further adapted to cause the first node to:
 calculate a size of the local domain, M, as equal to ceil 
 
       
         
           
             
               
                 ( 
                 
                   N 
                   K 
                 
                 ) 
               
               . 
             
           
         
       
     
     
       27. The first node of  claim 11 , wherein the circuitry is further adapted to cause the first node to:
 detect an addition or a removal of a given node in the network; and 
 re-calculate a size of the local domain according to an updated value of N; and 
 update membership of the domains and re-designate the domain heads.