Topology-centric resource management for large scale service clusters

• US 20060268742A1
• Filed: 05/31/2005
• Published: 11/30/2006
• Est. Priority Date: 05/31/2005
• Status: Active Grant

• Current Assignee: IAC Search & Media Incorporated (IAC/InterActiveCorp)
• Original Assignee: IAC Search & Media Incorporated (IAC/InterActiveCorp)
• Inventors: Yang, Tao, Zhou, Jingyu, Chu, Lingkun
• Granted Patent: US 7,894,372 B2
• Time in Patent Office: Days
• US Class Current: 370/254
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04L 43/0811 by checking connectivity
• CPC Class Codes: H04L 43/10 Active monitoring, e.g. heartbeat, ping or trace-route
• CPC Class Codes: H04L 45/46 Cluster building
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/12 Avoiding congestion; Recovering from congestion

Abstract

Topology-centric resource management for large scale service clusters is described herein. According to certain embodiments of the invention, techniques include 1) creating optimized topology with network switches to connect service modules based on application flows and bandwidth requirements, 2) providing centralized or decentralized monitoring schemes to maintain the topology view of a service cluster, and 3) using the topology information for optimizing load balancing and service information dissemination. Other methods and apparatuses are also described.

Claims

1. A computer implemented method, comprising:

dividing a plurality of nodes of a service cluster into a plurality of groups each having a plurality of members, each group having a dedicated node to communicate with other groups of the service cluster; and

in response to a message received from a member of a respective group, the dedicated node of the respective group distributing the message to other groups of the service cluster and a remainder of the members.

2. The method of claim 1, further comprising selecting the dedicated node of each group as a group leader that is responsible for communicating with other groups of the service cluster.

3. The method of claim 2, wherein the group leader of each group is responsible for communicating among the groups without having the remainder of the members to directly communicate with the other groups.

4. The method of claim 1, wherein the message received from a memory of the respective group includes an availability status of the member within the respective group.

5. The method of claim 4, wherein the message includes one of a joining and terminating the respective group message.

6. The method of claim 4, further comprising in response to a message received from another group of the service cluster, the dedicated node of the respective group forwarding the message to the members of the respective group.

7. The method of claim 6, wherein the message from another group includes an availability status of at least one member of another group.

8. The method of claim 1, further comprising:

in response to a packet received from a client over a wide area network (WAN), identifying a group for servicing the client based on a group identifier (ID) specified within the packet; and

distributing the packet to the identified group for services in response to the group ID.

9. The method of claim 8, wherein the packet is an IP packet and wherein the group ID is derived within a standard field of the IP packet.

10. The method of claim 9, wherein the group ID is determined based on a value within a TTL (time-to-live) field of an IP header of the packet.

11. The method of claim 1, further comprising creating a service graph having a hierarchical structure based on application service logics, wherein each of the nodes of each group is configured according to the service graph.

12. The method of claim 11, further comprising deriving a switch layout based on the service graph for optimized availability and networking performance, including

determining a separation factor for the service cluster,

separating the nodes of the service cluster into a plurality of sub-service graphs based on the determined separation factor,

assigning a switch for each node of each sub-service graph, and

coupling the plurality of sub-service graphs to form the service graph using one or more load balancing switches.

13. The method of claim 12, wherein the separation factor is no more than a maximum replication degree of the nodes in the service cluster.

14. The method of claim 12, wherein each node includes one or more replicas for redundancy purposes, wherein the method further comprises assigning the replicas of each node to an identifying switch.

15. The method of claim 12, further comprising:

for each sub-service graph, determining bandwidth stress between two adjacent switches; and

performing local optimization within each sub-service graph based on the determined bandwidth stress.

16. A service cluster, comprising:

a plurality of nodes coupled to each other and divided into a plurality of groups, each group having a dedicated node to communicate with a remainder of the groups,

wherein in response to a message received from a member of a respective group, a dedicated node of the respective group distributes the message to at least one of a remainder of the groups and a remainder of members within the respective group.

17. The service cluster of claim 16, wherein the dedicated node of each group is responsible for communicating among the groups without having the remainder of the members to directly communicate with the other groups.

18. The service cluster of claim 16, wherein the message received from a memory of the respective group includes an availability status of the member within the respective group.

19. The service cluster of claim 18, wherein in response to a message received from another group of the service cluster, the dedicated node of the respective group forwards the message to the members of the respective group.

20. The service cluster of claim 19, wherein the message from another group includes an availability status of at least one member of another group.

21. The service cluster of claim 16, further comprising a frontend node coupled to the plurality of nodes, wherein in response to a packet received from a client over a wide area network (WAN), the frontend node identifies a group for servicing the client based on a group identifier (ID) specified within the packet and distributes the packet to the identified group for services based on the group ID.

22. The service cluster of claim 21, wherein the packet is an IP packet and wherein the group ID is derived within a standard field of the IP packet.

23. The service cluster of claim 22, wherein the group ID is determined based on value within a TTL (time-to-live) field of an IP header of the packet.

24. An apparatus for a service cluster, comprising:

means for dividing a plurality of nodes of a service cluster into a plurality of groups each having a plurality of members, each group having a dedicated node to communicate with other groups of the service cluster; and

means for, in response to a message received from a member of a respective group, the dedicated node of the respective group distributing the message to other groups of the service cluster and a remainder of the members.

25. A computer implemented method performed within a service cluster having a plurality of nodes, the method comprising:

creating a service graph having a hierarchical structure with load balancing including

determining a separation factor for the service cluster,

separating the nodes of the service cluster into a plurality of sub-service graphs based on the determined separation factor,

assigning a switch for each node of each sub-service graph, and

coupling the plurality of sub-service graphs to form the service graph using one or more load balancing switches;

dividing a plurality of nodes of a service cluster into a plurality of groups according to the service graph each having a plurality of members, each group having a dedicated node to communicate with other groups of the service cluster;

in response to a message received from a member of a respective group, the dedicated node of the respective group distributing the message to other groups of the service cluster and a remainder of the members; and

in response to a message received from another group of the service cluster, the dedicated node of the respective group forwarding the message to the members of the respective group.

26. A computer implemented method, comprising:

maintaining a service graph for a service cluster having a plurality of nodes and each having one or more replicas, the service graph having a hierarchical infrastructure based on a network topology information associated with the plurality of nodes of the service cluster; and

in response to a service invocation from a first node, selecting, via the service graph, a second node within the service cluster according to a predetermined algorithm based on a load of the second node and a routing distance between the first and the second nodes.

27. The method of claim 26, wherein the second node is selected based on a load of at least one replica of the second node and a routine distance between the first node and the at least one replica of the second node.

28. The method of claim 26, further comprising:

determining a weight factor for each replicas of the second node; and

selecting a replica of the second node to service the first node, the selected replica having a minimum weight factor among the replicas of the second node.

29. The method of claim 26, wherein the predetermined algorithm is defined as follows:

f(y)=alpha*Load(y)+(1−

alpha)*routing distance(x->

y)

wherein f(y) represents a weight factor used to select node y, wherein the alpha is a constant ranging from approximately 0 to 1, wherein Load(y) represents a load node y, and wherein distance (x->

y) represents a routing distance between nodes x and y.

30. A computer implemented method, comprising:

creating a service graph having a hierarchical structure based on application service logics of a service cluster having a plurality of nodes; and

deriving a switch layout based on the service graph for optimized availability and networking performance of the plurality of nodes, including

determining a separation factor for the service cluster,

separating the nodes of the service cluster into a plurality of sub-service graphs based on the determined separation factor,

assigning a switch for each node of each sub-service graph, and

coupling the plurality of sub-service graphs to form the service graph using one or more load balancing switches.

31. The method of claim 30, wherein the separation factor is no more than a maximum replication degree of the nodes in the service cluster.

32. The method of claim 30, wherein each node includes one or more replicas for redundancy purposes, wherein the method further comprises assigning the replicas of each node to an identifying switch.

33. The method of claim 30, further comprising:

for each sub-service graph, determining bandwidth stress between two adjacent switches; and

performing local optimization within each sub-service graph based on the determined bandwidth stress.

34. A computer implemented method, comprising:

dividing a plurality of nodes of a service cluster into a plurality of groups each having a plurality of members, each group having a dedicated node to communicate with other groups of the service cluster with respect to availability information of members of the other groups;

in response to a first availability update received from a member of a respective group, the dedicated node of the respective group distributing the first availability update to other groups of the service cluster and a remainder of the members within the respective group; and

in response to a second availability update received from another group, the dedicated node of the respective group propagating the second availability update to the members of the respective group and storing the second availability update within the dedicated node to maintain a global view of the cluster regarding service availabilities.