# US 2021/0344749 A1 · Methods and Apparatuses for Balancing Utilization of Computer Resources > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 2021/0344749 A1 - Document ID: US20210344749A1 - Status: Published application - Kind: A1 - Application number: 17/283,182 - Filed: 2018-10-08 - Published: 2021-11-04 - Earliest claimed: 2018-10-08 - Assignees: Telefonaktiebolaget LM Ericsson (publ) - Applicants: Telefonaktiebolaget LM Ericsson (publ) - Inventors: Pär Karlsson; Lars Haraldsson - Web page: https://patentgrep.com/patent/US20210344749A1 ## CPC - H04L 67/1034: Reaction to server failures by a load balancer - G06F 9/5088: {involving task migration} - G06F 16/278: {Data partitioning, e.g. horizontal or vertical partitioning} - H04L 67/10: in which an application is distributed across nodes in the network (software deployment G06F8/60; multiprogramming arrangements G06F9/46) - H04L 67/1008: based on parameters of servers, e.g. available memory or workload (monitoring of computer activity G06F11/30) - H04L 67/1012: based on compliance of requirements or conditions with available server resources - H04L 67/1029: using data related to the state of servers by a load balancer - H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M) - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract Methods and apparatus for balancing resource utilization as described herein enable the use of distributed allocation architectures with minimal coordination signaling. Among the multiple advantages gained are reduced overhead signaling, greater implementation flexibility, and improved adaptability to changes in the system state. Here, “system state” refers to the subset (16) of servers (12) that are currently available among a set (14) of servers (12) targeted for use in load balancing. Of course, the contemplated methods and apparatus do not foreclose centralization of at least some of the load-balancing operations and associated data management. ## Claims ### Claim at position 1 1-25. (canceled) ### Claim 26 A method of balancing resource utilization among a set of servers, the method comprising: determining a system state for the set of servers, wherein some of the servers in the set may be unavailable, the system state being defined by the subset of servers that are currently available from among the set of servers, and wherein the number of possible system states is the number of unique subsets of servers from among the set of servers; assigning individual shards to respective ones among the subset of available servers according to a shard-to-server allocation scheme that, at least for mapped ones of the possible system states, prescribes an allocation of the shards among the subset of servers belonging to each mapped system state and minimizes the number of shard reassignments needed when the system state changes, wherein each shard is one among a set of shards and comprises a logical container for objects, and wherein each object comprises a job object or a storage object that requires respective resources on the server to which the object is assigned; allocating new objects incoming to the set of servers for processing to respective ones of the shards according to an object-to-shard allocation scheme that balances resource requirements across the shards; and responsive to the system state changing from a first one of the mapped system states to a second one of the mapped system states, reassigning individual ones of the shards from one server to another, as needed, in view of the differences between the shard-to-server assignments prescribed by the shard-to-server allocation scheme for the first and second mapped system states. ### Claim 27 (depends on 26) The method of claim 26, further comprising uniquely identifying each shard in the set of shards by a corresponding shard identifier and uniquely identifying each server in the set of servers by a corresponding server identifier, and wherein the shard-to-server allocation scheme imposes a fixed mapping of shard identifiers to server identifiers, for each mapped system state. ### Claim 28 (depends on 26) The method of claim 26, wherein not all servers in the set of servers have equal capacities and wherein the object-to-shard allocation scheme allocates new objects incoming to the set of servers for processing by allocating each new object in dependence on the respective capacities of the servers in the set of servers. ### Claim 29 (depends on 26) The method of claim 26, further maintaining coordination information in each available server, the coordination information comprising an indication of the system state, such that each available server knows which other servers in the set of servers are available, and the coordination information further comprising the shard-to-server allocation scheme, such that each available server knows which shards belong to which servers in the subset of available servers. ### Claim 30 (depends on 26) The method of claim 26, wherein the set of servers comprises a service provisioning and activation platform configured to provision and activate telecommunication services in a telecommunications network, for respective subscribers of the telecommunications network, and wherein each object comprises a managed object that defines the provisioning needed for a given customer service order requesting provisioning and activation of one or more telecommunication services for a given subscriber. ### Claim 31 (depends on 30) The method of claim 30, wherein the given customer service order comprises a provisioning order for a Subscriber Identification Module (SIM) used for authorizing access to the telecommunications network by corresponding subscriber equipment, and wherein the corresponding managed object represents a set of provisioning tasks for the SIM. ### Claim 32 (depends on 26) The method of claim 26, further comprising maintaining an object state database indicating current states of the objects that have been allocated to each shard and using the object state database to restore or resume processing associated with each object in a given shard, when the given shard is reassigned from one server to another server. ### Claim 33 A computer processing apparatus operative to balance resource utilization among a set of servers, the computer processing apparatus comprising: interface circuitry; and processing circuitry configured to communicate via the interface circuitry and, based on such communications: determine a system state for the set of servers, wherein some of the servers in the set may be unavailable, the system state being defined by the subset of servers that are currently available from among the set of servers, and wherein the number of possible system states is the number of unique subsets of servers from among the set of servers; assign individual shards to respective ones among the subset of available servers according to a shard-to-server allocation scheme that, at least for mapped ones of the possible system states, prescribes a defined allocation of the shards among the subset of servers belonging to each mapped system state and minimizes the number of shard reassignments needed when the system state changes, wherein each shard is one among a set of shards and comprises a logical container for objects, and wherein each object comprises a job object or a storage object that requires respective resources on the server to which the object is assigned; allocate new objects incoming to the set of servers for processing to respective ones of the shards according to an object-to-shard allocation scheme that balances resource requirements across the shards; and responsive to the system state changing from a first one of the mapped system states to a second one of the mapped system states, reassign individual ones of the shards from one server to another, as needed, in view of the differences between the shard-to-server assignments prescribed by the shard-to-server allocation scheme for the first and second mapped system states. ### Claim 34 (depends on 33) The computer processing apparatus of claim 33, wherein the processing circuitry is configured to uniquely identify each shard in the set of shards by a corresponding shard identifier and uniquely identify each server in the set of servers by a corresponding server identifier, and wherein the shard-to-server allocation scheme imposes a fixed mapping of shard identifiers to server identifiers, for each mapped system state. ### Claim 35 (depends on 33) The computer processing apparatus of claim 33, wherein all objects have comparable resource requirements and wherein the object-to-shard allocation scheme allocates new objects incoming to the set of servers for processing by one of: randomly assigning each new object to one of the shards in the set of shards; assigning each new object to one of the shards in the set of shards according to a round-robin scheme; or assigning each new object to one of the shards in the set of shards according to hash-based scheme. ### Claim 36 (depends on 33) The computer processing apparatus of claim 33, wherein not all objects have comparable resource requirements and wherein the object-to-shard allocation scheme allocates new objects incoming to the set of servers for processing by allocating each new object in dependence on the resource requirements of the new object. ### Claim 37 (depends on 33) The computer processing apparatus of claim 33, wherein not all servers in the set of servers have equal capacities and wherein the object-to-shard allocation scheme allocates new objects incoming to the set of servers for processing by allocating each new object in dependence on the respective capacities of the servers in the set of servers. ### Claim 38 (depends on 33) The computer processing apparatus of claim 33, wherein the processing circuitry is configured to maintain coordination information in each available server, the coordination information comprising an indication of the system state, such that each available server knows which other servers in the set of servers are available, and the coordination information further comprising the shard-to-server allocation scheme, such that each available server knows which shards belong to which servers in the subset of available servers. ### Claim 39 (depends on 33) The computer processing apparatus of claim 33, wherein the processing circuitry is configured to implement the shard-to-server allocation scheme as a lookup table. ### Claim 40 (depends on 39) The computer processing apparatus of claim 39, wherein the lookup table includes a row for each shard in the set of shards, each row containing a permuted copy of a weight vector comprising an ordered set of weights expressing relative preferences for assigning the shard to respective ones of the servers in the set of servers, the order of the weights being permutated across the rows so that each row in the lookup table is unique. ### Claim 41 (depends on 40) The computer processing apparatus of claim 40, wherein the processing circuitry is configured to assign individual shards to respective ones among the subset of available servers according to the shard-to-server allocation scheme by assigning each shard to the available server having the highest relative preference, as indicated by the weight vector contained in the table row that corresponds to the shard. ### Claim 42 (depends on 33) The computer processing apparatus of claim 33, wherein the set of servers comprises a service provisioning and activation platform configured to provision and activate telecommunication services in a telecommunications network, for respective subscribers of the telecommunications network, and wherein each object comprises a managed object that defines the provisioning needed for a given customer service order requesting provisioning and activation of one or more telecommunication services for a given subscriber. ### Claim 43 (depends on 42) The computer processing apparatus of claim 42, wherein the given customer service order comprises a provisioning order for a Subscriber Identification Module (SIM) used for authorizing access to the telecommunications network by corresponding subscriber equipment, and wherein the corresponding managed object represents a set of provisioning tasks for the SIM. ### Claim 44 (depends on 33) The computer processing apparatus of claim 33, wherein the processing circuitry is configured to maintain an object state database indicating current states of the objects that have been allocated to each shard and use the object state database to restore or resume processing associated with each object in a given shard, when the given shard is reassigned from one server to another server. ### Claim 45 A computer-readable medium storing a computer program comprising program instructions that, when executed by processing circuitry of a computer processing apparatus, configures the computer processing apparatus to balance resource utilization among a set of servers, the computer program comprising program instructions causing the computer processing apparatus to: determine a system state for the set of servers, wherein some of the servers in the set may be unavailable, the system state being defined by the subset of servers that are currently available from among the set of servers, and wherein the number of possible system states is the number of unique subsets of servers from among the set of servers; assign individual shards to respective ones among the subset of available servers according to a shard-to-server allocation scheme that, at least for mapped ones of the possible system states, prescribes a defined allocation of the shards among the subset of servers belonging to each mapped system state and minimizes the number of shard reassignments needed when the system state changes, wherein each shard is one among a set of shards and comprises a logical container for objects, and wherein each object comprises a job object or a storage object that requires respective resources on the server to which the object is assigned; allocate new objects incoming to the set of servers for processing to respective ones of the shards according to an object-to-shard allocation scheme that balances resource requirements across the shards; and responsive to the system state changing from a first one of the mapped system states to a second one of the mapped system states, reassigning individual ones of the shards from one server to another, as needed, in view of the differences between the shard-to-server assignments prescribed by the shard-to-server allocation scheme for the first and second mapped system states.