Method and system for matching network clients and servers under matching constraints

• US 20040003066A1
• Filed: 06/26/2002
• Published: 01/01/2004
• Est. Priority Date: 06/26/2002
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Harvey, Nicholas J., Lovasz, Laszlo
• Granted Patent: US 7,165,103 B2
• Time in Patent Office: Days
• US Class Current: 709/223
• CPC Class Codes: H04L 67/2871 Implementation details of single intermediate entities
• CPC Class Codes: H04L 67/306 User profiles
• CPC Class Codes: H04L 67/563 Data redirection of data network streams
• CPC Class Codes: H04L 67/564 Enhancement of application control based on intercepted application data
• CPC Class Codes: H04L 69/329 in the application layer [OSI layer 7]
• CPC Class Codes: H04L 9/40 Network security protocols

Abstract

A method of finding an optimal match between clients and servers under given matching constraints utilizes a bipartite diagram in which the clients are presented as vertices on one side, the servers as vertices on the other side, and each possible client-server pairing allowed under the matching constraints as an edge connecting the vertices representing the client and the server. After an initial round of assignments is performed, the assignments are optimized by an optimization operation that iteratively applies a reassignment process. The reassignment process searches for a chain of servers starting with a server having a highest number of clients and ends with another server with a client number less than that of the first server by at least two, with each server in the chain except the end server having a client reassignable to the next server in the chain. Those reassignable clients are then reassigned along the chain such that the first server'"'"'s client number is reduced by one and the end server'"'"'s client number is reduced by one. The reassignment process is repeated until an optimal match is reached.

Claims

1. A computer-readable medium having computer-executable instructions for performing steps for matching a plurality of clients with a plurality of servers under given matching constraints, the steps comprising:

presenting the clients and servers as vertices and allowable client-server pairs as edges connecting respective vertices in a bipartite diagram;

making an initial round of assignments to assign each client to one server;

identifying a server having a highest number of clients assigned thereto;

finding a chain of servers beginning with the server with the highest number of clients and ending with a server having a number of clients smaller than said highest number by at least two, each server in the chain except the server at the end of the chain having one client reassignable to the next server in the chain;

reassigning said reassignable clients along the chain such that the number of clients of the server at the beginning of the chain is reduced by one and the number of clients of the server at the end of the chain is increased by one; and

repeating the steps of identifying, finding, and reassigning until an optimal match between the clients and the servers is reached.

2. A computer-readable medium as in claim 1, wherein the step of finding includes searching for an alternating path in the bipartite diagram connecting the server having the highest number of clients to the server having a number of clients smaller than said highest number by at least two.

3. A computer-readable medium as in claim 2, wherein the step of making the initial round of assignments assigns each client to a server having a smallest number of assigned clients among servers to which said each client is assignable under the matching constraints.

4. A computer-readable medium as in claim 3, wherein the step of making the initial round of assignments further includes first sorting the clients according to a number of servers each client is assignable to under the matching constraints.

5. A computer-readable medium as in claim 2, wherein the searching for the alternating path is performed recursively using the bipartite diagram.

12. A computer network as in claim 11, wherein the matching module is programmed to perform the finding of a chain of servers by performing a recursive search for an alternating path in the bipartite diagram connecting the server with the highest number of clients to the server having a number of clients smaller than said highest number by at least two.

6. A method for matching a plurality of clients with a plurality of servers by means of computerized processing, comprising:

presenting the clients and servers as vertices and allowable client-server pairs as edges in a bipartite diagram;

making an initial round of assignments to assign each client to one server;

identifying a server having a highest number of clients assigned thereto;

finding a chain of servers beginning with the server with the highest number of clients and ending with a server having a number of clients smaller than said highest number by at least two, each server in the chain except the server at the end of the chain having one client reassignable to the next server in the chain;

reassigning said reassignable clients along the chain such that the number of clients of the server at the beginning of the chain is reduced by one and the number of clients at the end of the chain is increased by one; and

repeating the steps of identifying, finding, and reassigning until an optimal match between the clients and the servers is reached.

7. A method as in claim 6, wherein the step of finding includes searching for an alternating path in the bipartite diagram connecting the server having the highest number of clients to the server having a number of clients smaller than said highest number by at least two.

8. A method as in claim 7, wherein the step of making the initial round of assignments assigns each client to a server having a smallest number of assigned clients among servers to which each client is assignable under the matching constraints.

9. A method as in claim 8, wherein the step of making the initial round of assignments further includes first sorting the clients according to a number of servers each client is assignable to under the matching constraints.

10. A method as in claim 7, wherein the searching for the alternating path is performed recursively using the bipartite diagram.

11. A computer network comprising:

a plurality of servers;

a plurality of client, each client being assignable to a subset of the servers under given matching constraints;

a matching module programmed to compute an optimal match of the clients with the servers by presenting the clients and servers as vertices and client-server pairs allowable under the matching constraints as edges in a bipartite diagram, making an initial round of assignments to assign each client to one server under the matching constraints, finding a chain of servers beginning with a server having a highest number of clients assigned thereto and ending with a server having a number of clients smaller than said highest number by at least two, with each server in the chain except the server at the end of the chain having one client reassignable to the next server in the chain, reassigning said reassignable clients along the chain such that the number of clients of the server at the beginning of the chain is reduced by one and the number of clients at the end of the chain is increased by one, and repeating the steps of identifying, finding, and reassigning until an optimal match between the clients and the servers is reached.