Intelligent switching of client packets among a group of servers

Abstract

The content-aware application switch and methods thereof intelligently switch client packets to one server among a group of servers in a server farm. The switch uses Layer 7 or application content parsed from a packet to help select the server and to schedule the transmitting of the packet to the server. This enables refined load-balancing and Quality of-Service control tailored to the application being switched. In an exemplary embodiment of the invention, a method includes maintaining a server load metric for each server in a group of servers; parsing application content from a packet; selecting a destination server from the group of servers, wherein selecting the destination server is dependent on the server load metric for each server, assigning a priority to the packet, the priority being dependent on the application content; and dropping the packet if the priority comprises at least one of a predetermined type.

Claims

1. A method comprising: parsing application content from a packet; selecting a destination server from a group of servers, wherein selecting the destination server is dependent on a load metric for each server; assigning a priority to the packet, the priority dependent on the application content; transmitting the packet to the destination server according to a transmitting schedule; and dropping the packet if the priority comprises a predetermined type.

2. The method of claim 1, wherein the transmitting schedule is dependent on the priority.

3. The method of claim 1, further comprising referencing an access control list to enforce security, the access control list being dependent at least in part upon the application content.

4. The method of claim 3, wherein referencing an access control list further comprises dropping the packet if the application content comprises a first predetermined type.

5. The method of claim 4, wherein referencing an access control list further comprises redirecting the packet to a predetermined location if the application content comprises a second predetermined type.

6. The method of claim 1, wherein the priority comprises at least one of a first priority and a second priority, the second priority being lower than the first priority, wherein the destination server has a workload above a first predetermined level, and the transmitting schedule is constructed such that, if the packet comprises the first priority then the packet is transmitted to the destination server without delay and if the packet comprises the second priority then the packet is held back from being transmitted to the destination server.

7. The method of claim 1, further comprising at least one of: determining at least one eligible server from among the group of servers, wherein determining at least one eligible server is dependent on the application content; and selecting the destination server from among the at least one eligible servers.

8. The method of claim 1, further comprising determining an estimated application load for the destination server, the estimated application load being dependent at least in part upon the application content; wherein selecting a destination server is dependent at least in part upon the estimated application load.

9. The method of claim 1, wherein the transmitting schedule is dependent at least in part upon the server load metric for each server.

10. The method of claim 1, wherein the application content comprises a Hypertext Transfer Protocol header.

11. A non-transitory computer readable medium, the computer readable medium including instructions, which when executed perform steps comprising: parsing application content from a packet; selecting a destination server from a group of servers, wherein selecting the destination server is dependent on a load metric for each server; assigning a priority to the packet, the priority dependent on the application content; transmitting the packet to the destination server according to a transmitting schedule; and dropping the packet if the priority comprises a predetermined type.

12. The non-transitory computer readable medium of claim 11, wherein the transmitting schedule is dependent on the priority.

13. The non-transitory computer readable medium of claim 11, wherein the steps further comprise referencing an access control list to enforce security, the access control list being dependent at least in part upon the application content.

14. The non-transitory computer readable medium of claim 13, wherein referencing an access control list further comprises dropping the packet if the application content comprises a first predetermined type.

15. The non-transitory computer readable medium of claim 14, wherein referencing an access control list further comprises redirecting the packet to a predetermined location if the application content comprises a second predetermined type.

16. The non-transitory computer readable medium of claim 11, wherein the priority comprises at least one of a first priority and a second priority, the second priority being lower than the first priority, wherein the destination server has a workload above a first predetermined level, and the transmitting schedule is constructed such that, if the packet comprises the first priority then the packet is transmitted to the destination server without delay and if the packet comprises the second priority then the packet is held back from being transmitted to the destination server.

17. A method comprising: parsing application content from a packet; determining at least one eligible server from a group of servers, wherein determining at least one eligible server is dependent at least in part upon the application content; selecting a destination server from the at least one eligible server; determining an estimated application load for the destination server, the estimated application load dependent at least in part upon the application content; assigning a priority to the packet, the priority being dependent at least in part upon the application content; transmitting the packet to the destination server according to a transmitting schedule; and dropping the packet if the priority comprises a predetermined type.

18. The method of claim 17, wherein the step for selecting the destination server is dependent at least in part upon the server load metric for each server in the group of servers and the estimated application load.

19. The method of claim 17, wherein the transmitting schedule is dependent on the priority.

20. The method of claim 17, wherein the priority further comprises at least one of a first priority and a second priority, the second priority being lower than the first priority, wherein the destination server has a workload above a first predetermined level of the at least one of a predetermined level, and the transmitting schedule is constructed such that, if the packet comprises the first priority then the packet is transmitted to the destination server without delay and if the packet comprises the second priority then the packet is held back from being transmitted to the destination server.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) FIG. 1 illustrates a data center hosting the web application by means of a server farm.

(2) FIG. 2 is a table illustrating the protocol layers of the OSI model, the corresponding TCP/IP protocol stacks, and the types of conventional switching and routing operable at each layer.

(3) FIG. 3 illustrates the various headers of an IP packet.

(4) FIG. 4 illustrates conventional TCP port assignments for some of the more standard services.

(5) FIG. 5 is a functional block diagram illustrating schematically a content-aware application switch operating in an intelligent data center, according to a preferred embodiment of the present invention.

(6) FIG. 6 is a table illustrating the various TCP/IP protocol stacks and OSI layers and associated messages or information the application switch employs to perform switching.

(7) FIG. 7 is a flow diagram illustrating a method of switching prioritized packets to one of a group of servers.

(8) FIG. 8 shows the components of the application switch of FIG. 5 in more detail.

(9) FIG. 9 is a schematic illustration of the information carried in a packet tag.

(10) FIG. 10A illustrates a content dictionary containing a set of predefined patterns indexed by content class.

(11) FIG. 10B illustrates a policy table containing a set of predefined policies indexed by content class.

(12) FIG. 10C illustrates a server property table.

(13) FIG. 10D illustrates a server state table.

(14) FIG. 11 is a flow chart illustrating a load-balancing scheme based on weighed least connection.

(15) FIG. 12 illustrates schematically the QoS controller of FIG. 8 in more detail.

(16) FIG. 13 is a table showing how the ActiveFlags are set as a function of server load.

(17) FIG. 14 is a flow diagram illustrating a preferred schedule of packet prioritization for a given server port.

(18) FIG. 15 illustrates schematically a Dynamic Server Weight that converges to the Default Server Weight as the Current Load of the newly put online server approaches the average Current Loads of the servers in a group participating in load balancing.

(19) FIG. 16A is a flow chart illustrating the process of adjusting the server weight of the new server being added to the group of servers under load balancing.

(20) FIG. 16B is a flow chart illustrating the process of performing load balancing with the new server included in the group of servers under load balancing.

(21) FIG. 17 illustrates the handshaking at the beginning of a TCP session between a client, an intermediate switch and a server under the TCP splicing scheme.

(22) FIG. 18 illustrates the streamlined TCP process of the present invention.

(23) FIG. 19 is a flow chart illustrating the method of content-aware switching without delay binding.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS

(24) Content-Aware Application Switch

(25) According to one aspect of the present invention, a content-aware application switch enables switching a client packet to a server among a group of servers, where the selected server and the priority of the packet are dependent on the content carried in the packet.

(26) FIG. 5 is a functional block diagram illustrating schematically a content-aware application switch operating in an intelligent data center, according to a preferred embodiment of the present invention. An intelligent data center 10 is implemented by the deployment of a content-aware application switch 20 to switch between servers in a server farm 30. The server farm 30 comprises a group of web servers 32 for hosting replicas of a web application to be deployed on the Internet 50. The server farm optionally includes other servers, such as database servers 34 and media servers 36 for providing resources that may augment or be required by the particular web application being deployed. Browsers on the Internet, such as a browser 60 running on a client computer, can access the web application hosted in the data center 10 via a WAN (wide-area network) router 40.

(27) A browser accesses a web application by the URL pointing to the website hosting the web application. In the simple case when a web server is accessible directly from the Internet, the URL for the website will be the IP address of the server. In the case of the data center, where the web servers are behind the application switch 20 and not directly accessible, the URL for the website is a virtual IP address that actually points to the application switch. Each server in the server farm 30 has its own IP address, which is a local IP address accessible only within the data center. The virtual IP address enables the client packet to be delivered to the switch. The switch selects a server and delivers the packet to the selected server by addressing the server's local IP address. This switching process involves modifying the destination IP address in each packet header from that of the switch to that of the selected server. Likewise, the hardware MAC address in the packet header is modified.

(28) The application switch 20 basically receives packets from clients on the Internet, examines the content of the packets, and based on the content, prioritizes the packets and selects appropriate servers to send the packets to. The application switch 20 comprises an IP bus 100 that enables IP communications with the Internet 50 and the server farms 30. A buffer controller 120 temporarily stores packets passing through the application switch.

(29) A packet classifier 140 snoops receive packets from the IP bus 100 so as to examine the content in each packet and classify the identified content pattern as one of predefined content pattern classes.

(30) A transmit controller 160 uses the assigned content class to look up a set of tables 180 to determine transmit instructions for each packet. Ultimately, the transmit instructions determine which server the packet is to be directed to, and in what order. The transmit controller includes a load balancer 162 and a QoS controller 164. The load balancer 162 selects a server that can best serve the request associated with the packet based on the content class, server farm configuration and the current loads of the servers. The QoS controller 164 prioritizes each packet based on the content class and the predefined policy for each class.

(31) Once the transmit instructions have been determined for each packet, the transmit controller cooperates with the buffer controller 120 to release the temporarily stored packets to the selected server according to their determined priority.

(32) Thus, it can be seen that packets are routed from the client 60 to the application switch 20 using Layer 3 information. From the switch to a selected server, Layer 4-7 information is used to select a server and set priority, and Layers 2-4 information is used to deliver the packet to the selected server.

(33) FIG. 6 is a table illustrating the various TCP/IP protocol stacks and OSI layers and associated messages or information the application switch employs to perform switching. As mentioned in the background section, a conventional web switch operates within a data center to switch packets to one of a group of servers based on load-balancing considerations. A server is selected based on how busy each server is and what type of request is carried by a packet. The type of request carried by a packet can be determined by examining Layers 4-7 message.

(34) The content-aware application switch 20 shown in FIG. 5, operates in a similar environment as a web switch. It switches packets based on information or messages associated with Layer 7 as well as those of lower layers. However, unlike a web switch, not only is it aware of Layers 2-7 messages, it also uses this information to prioritize the packets as well as to select the most appropriate server. In other words, the application switch performs QoS control and load balancing based on application-related information.

(35) The application-related or Layer 7 message carried in a packet includes HTTP header and other HTTP payload such as data or other personalized information. The information can be used to make switching decisions based on QoS considerations. For example, at an online merchandising website, the customer who is actually trying to buy an item can be distinguished from another who is merely browsing a catalog by the web page they are currently requesting. This information can be determined from the URL contained in the HTTP header, since it actually points to the current webpage. Similarly, the packets from a preferred customer may be identified by the cookie contained in the HTTP header. Based on a set predefined policies, the packets can be prioritized, with the higher priority ones getting better quality of service (QoS).

(36) FIG. 7 is a flow diagram illustrating a method of switching prioritized packets to one of a group of servers.

(37) Buffering:

(38) Step 200: Store an input packet in a buffer. The input packet is typically associated with a client request.

(39) Content Classification:

(40) Step 210: Parse out the Layer 7 content from the packet. Lower layer information is also parsed out to obtain various addresses, but Layer 7 content provides information about the application associated with the input packet.

(41) Step 212: Assign a content class to the packet based on its parsed content by reference to a predefined set of content class definitions.

(42) Load-Balancing:

(43) Step 220: Select a destination server for the packet from among a group of servers, where the server selection is a predefined function of the individual server properties, including server loads, among the group of servers.

(44) Alternatively,

(45) Step 220: In another embodiment, select a destination server for the packet from among a group of servers, where the server selection is a predefined function of the individual server properties among the group of servers and the content class of the packet. The dependency on content class allows more refined load balancing. For example, the content class assigned to the packet allows identification of the group of eligible servers for serving the application, and also the estimated load the application placed on the selected server.

(46) QoS Control:

(47) Step 230: Queue the packet according to a priority that is given by a predefined function of content class.

(48) Switching:

(49) Step 240: Release the packet from the buffer to the designation server according to a schedule that depends on the assigned priority and the properties and workload of the destination server.

(50) In the preferred embodiment, all packets belonging to the same TCP session are assigned similar transmission characteristics and are therefore treated as a group. Classification by the packet classifier 140 need only be performed on a sample packet of the group. The transmit controller 160 then assigns the same classification to the rest of the packets in the same TCP session. In this way, it has been estimated that the packet classifier need only process five percent of all packet traffic. A TCP session can be identified by the unique combination of Source IP Address (Layer 3 header) and Source Port Number (Layer 4 header).

(51) FIG. 8 shows the components of the application switch of FIG. 5 in more detail. The application switch 20 uses the IP bus 100 to communicate with the Internet 50 on one side and the server farm 30 on the other side (see FIG. 5). In one preferred embodiment, the IP bus interfaces on the Internet side (ingress port) with a wideband network interface, such as a 1 Gbps Ethernet port (not shown). On the server farm side (egress port), the IP bus interfaces with N (e.g., N=8) 10/100 Mbps Ethernet ports 310, allowing connections to N servers 32. This provides a throughput of 1.28 Gbps full duplex across the application switch. In general N should be a number such that the throughput on the ingress port is commensurate with that of the egress port.

(52) Buffer Controller

(53) Packets entering the application switch 20 are temporarily stored in the buffer controller 120. The buffer controller comprises a receiver 320, a packet buffer 322 and a transmitter 324. On the ingress side, client packets arriving from the Internet are picked up by the receiver 320 from the IP bus. The receiver stores the packets in the packet buffer 322 and also creates a packet tag for each stored packet. The packet tag is a token for the stored packet and is used by the transmit controller to assign transmit instructions to the stored packet.

(54) FIG. 9 is a schematic illustration of the information carried in a packet tag. It comprises a Packet ID field, a Buffer Address field, a Priority field, a Previous Packet ID field, a Next Packet ID field, and a Selected Server field. Packet ID serves as an index to the stored packet. Buffer Address gives the memory location of the stored packet. Priority is determined from a classification of the packet content and is used to set the sending order of the packet to the selected server. The sending order is encoded in the linked list fields, Previous Packet ID and Next Packet ID. Selected Server is the address (i.e. port number) of the selected server. The linked list fields and Selected Server field contain transmit instructions that are assigned by the transmit controller.

(55) Tables

(56) Returning to FIG. 8, it will be understood that various components of the application switch communicate with each other by well known means of internal buses, processors, memories and other glue logic, and are not explicitly shown. Shown explicitly are those communication paths that help to illustrate functional relationships. In particular, where information is stored and processed by a number of components, it is preferably stored in the set of tables 180.

(57) The tables include a TCP session table 182, an ACL (access control list) table 184, one or more server table 186, a class policy table 188 and others. These tables are accessible by the various components of the application switch and will be described more fully in connection these components later. In the preferred embodiment, the tables are stored in non-volatile memory and loaded into random access memory (RAM) during operation.

(58) The TCP session table 182 keeps track of TCP sessions. When a packet is received into the application switched, it is checked against the TCP session table to see if it belongs to an existing TCP session. If the packet is part of an existing TCP session, it will be assigned transmission instructions similar to other packets of the same TCP session. If the packet does not match any existing TCP session, a new TCP session will be registered in the TCP session table 182.

(59) The ACL table 184 is a listing of access control instructions versus content class. Essentially, it allows a user or an administrator to control access based on parsed Layer 2-7 information. In one embodiment, it is incorporated into the class policy table.

(60) The class policy table 188 allows a user or an administrator to set policies or business rules to different content classes. In the preferred embodiment, a priority is assigned to each content class.

(61) Packet Classifier

(62) As a receive packet is taken up by the receiver 320, a copy of it is snooped by the packet classifier 140. The packet classifier comprises a content parser 340 that parses out content from the various header fields and data portion (Layers 2 to 7) of the a packet. A content class classifier 342 recognizes the parsed content as one of a set of predefined patterns and classifies each pattern by reference to a content class dictionary 344.

(63) FIG. 10A illustrates a content class dictionary containing a set of predefined patterns indexed by content class. The content class dictionary 344 is a table stored in memory that can be updated by a user or administrator. In one embodiment, it is included in tables 180.

(64) Returning to FIG. 8, the content class classifier 140 assigns to the packet a content class, which is then communicated to the receiver 320 and the transmit controller 160.

(65) Basically, Layer 2-4 information parsed by the packet classifier is used by the receiver 320 to make a preliminary determination of what to do with each packet. For example, the classification on (Layer 2-4) headers is useful for screening out uninterested web traffic. This includes:

(66) a. Checking destination MAC address for Layer 2 switching;

(67) b. Setting an Access Control List (ACL) by looking at TCP/IP headers, and returning a flag for reject or allowed packet traffic;

(68) c. Identifying uninterested web traffic by looking at TCP/IP headers, such as user specified VIP and/or web service port numbers, and returning a flag to indicate uninteresting web traffic and forwarding output MAC port number;

(69) d. Identifying management traffic by looking at TCP/IP headers, such as the appearance of the actual IP address of the application switch and/or network management port numbers, and returning a flag to indicate management traffic and forwarding output MAC port number.

(70) In a preferred embodiment, Layer 7 information is also examined for making a preliminary determination of what to do with each packet. In particular, the ACL is also controlled by application layer information where packets carrying certain class of content are accepted, rejected or redirected to a predetermined location.

(71) If the receiver 320 determines from the Layers 3-4 information that the packet is not related to web traffic, the transmit controller 160 will not need the application layer (Layer 7) information from the packet classifier 140. It will be notified by the receiver to process the transmit instructions of the packet accordingly. Otherwise, the transmit controller will take the application layer information into account.

(72) The classification on application layer (Layer 7) content makes it possible to assign, in combination with the policy table 188, more refined transmit instructions for a packet. In general, the inbound packets are classified based on at least three categories of information. The first one is related to the nature of the application. Different applications will be treated differently based on their business values. Different application can be identified by the associated URL path information. The second is related to client's history. Based on the historical behavior of a client, the client can be assigned a priority. A specified cookie field can be used to accumulate client history information, and be examined to classify the inbound packets. The third category is related to client's browsing status. The business value associated with clients in different browsing stages will be different. A client in a buying mode who has put items into the shopping cart and/or provided his/her credit card information has higher business value than the clients in random surfing mode. The different browsing stages can be determined by examining the URL paths (i.e., the web pages being pointed to) and/or from specified cookie fields established to identify clients in different browsing stages.

(73) The application layer classification therefore includes checking URL and Cookie values, and return URL and Cookie Pattern index based on these values. From the URL, the HTTP request method (GET, HEAD, POST, etc.) is also examined. Policy can be set to disable certain methods, like PUT or DELETE. Examples of other possible URL patterns that may be checked, include: TABLE-US-00001 GET/subdir/filname.html (or HEAD, POST, PUT, etc.) GET /subdir/* .gif GET/(all.cgi, .bin, and .exe files) GET /*.asp?userid=1234 (or all userid between 100 and 500) Host: www.companyname.com Referer: http:/www.companyname0.com/subdir/filename.html

(74) Examples of possible Cookie patterns that may be checked, includes: TABLE-US-00002 Cookie: ***; userid=1234; (or all userid between 100 and 500) Cookie: ***; shoppingcartexists=yes; ***; shipping=fedex.

(75) In a preferred embodiment, the packet classifier 140 is implemented with the aid of a PAX.port 1100 Classification Processor manufactured by Solidum Systems Corp., Scotts Valley, Calif., U.S.A. Classification is only performed on packets from the Internet side, i.e., ingress traffic, which will inspect all the packets at the speed of 500 Mbs (312K packet per second (pps), assuming 200 bytes of average packet size) and parsing of all Layer 2 to 7 fields.

(76) Transmit Controller

(77) The transmit controller's job is to use information parsed from a packet to assign transmit instructions for the packet in order to stage the packet for transmission. In the preferred embodiment, the transmit controller performs an initial application-layer security screening by checking against the ACL table 184. Dependent on the determined content class of the packet, the ACL table may prescribe that the packet is to be dropped, or redirect to a predetermined location, or other actions. On the other hand, if the ACL table grant access for the packet to be switched to a destination server among the server farm, the transmit controller will invoke the load balancer 162 and the QoS controller 164 to provide transmit instructions for the packet.

(78) In the preferred embodiment, the transmit instructions include specifying which destination server the packet is to send to and with what priority. The destination server is determined by the load-balancer 162 component of the transmit controller and the priority is determined by the QoS controller 164 component. These determinations are made by reference to both the content class for the packet and tables containing server and priority information.

(79) FIG. 10B illustrates a class policy table containing a set of predefined policies indexed by content class. The policy table 188 is a table stored in memory that can be updated by a user or administrator. It basically codifies the relative importance of a packet with a given content class, based on business and other considerations. This is implemented by a priority assigned to each class. In a preferred embodiment, the priority falls into one of three types: HIGH, MEDIUM, and LOW. In another embodiment, the priority type also includes REJECT, which means the packet is to be dropped. This will provide an alternative implementation of application-layer security control. For expediency, the table also contains a Server Group field and a Class Weight field. The Server Group field yields, for each class, a list of eligible servers eligible to service the class. The Class Weight field provides a relative estimate of the load presented to a server by applications associated with this class. In the example shown in FIG. 10B, the class policy table defines Priority, Server group, and Class Weight as individual functions of content class.

(80) FIG. 10C illustrates a server property table. The server property table is part of the server table 186 shown schematically in FIG. 8. It lists all servers in the server farm and their properties and settings. The server properties include: the server's IP & MAC addresses; the maximum number of connections that the application switch can establish with the server; the default server weight, which is an integer number indicates the relative power of the server, a LOW margin; and a HIGH margin. The default server weight provides a weighted measure of the server intrinsic capacity. The LOW and HIGH margins will be described in connection with QoS control later.

(81) FIG. 10D illustrates a server state table. The server state table is a dynamic part of the server table 186 shown schematically in FIG. 8. The server state table stores server load metrics that include: CurrentConnections; CurrentLoad; DynamicServerWeight and a count, k. The CurrentConnections indicates the current number of connections the application switch has established with the server. The CurrentLoad is a weighted summation of all current connections, i.e. a summation where each connection is weighted by the default server weight and also the class load (see FIG. 10B) associated with each connection. The DynamicServerWeight and the count, k will be described in more detail later in connection with a slow-start server-selection method for a newly added server.

(82) To determine a destination server for a packet, the load balancer 162 (FIG. 8) uses the content class obtained from the packet classifier 140 to look up the policy table 188 for a server group and a class load. The load balancer then selects one server from the server group based on load-balancing considerations. The load balancer references the various server tables 186 and takes into consideration the properties and the server load metrics of each server in the server group in order to select a server best able to fulfill the request associated with the packet in question.

(83) At least four types of load-balancing schemes are applicable. The first three types are simpler, without considering the number of existing connections on each server. For example, the first type is Round Robin, which chooses a server among a group in turns. The second is Weighted Round Robin, which is similar to Round Robin, but each server is weighted by its DefaultServerWeight (FIG. 10C). The third is Weighted Distribution, which is similar to Weighted Round Robin in that the servers are weighted, but it chooses a server by random selection rather than going around the group in turns.

(84) The fourth type of load-balancing scheme is Weighted Least Connection, which is the preferred scheme. It involves more computations but provides a more refined balance. Basically, it selects a server with the minimum number of weighted connections (i.e. CurrentLoad). A weighted connection takes into consideration that different class of requests presents different load on a server as represented by the ClassWeight value given in the policy table of FIG. 10B. It also takes into consideration that each server also has a weight (represented by DefaultServerWeight in FIG. 10C) which allows some server to have more connections than others.

(85) FIG. 11 is a flow chart illustrating a load-balancing scheme based on weighed least connection.

(86) Step 370: Read the list of servers in ServerGroup. ServerGroup is the group of servers predetermined to be eligible for serving packets of a given content class (see. FIG. 10B).

(87) Step 372: Delete all servers with CurrentConnections+1>=MaxConnections. All servers in the group that are already connected to the maximum need not be considered.

(88) Step 374: For the remaining servers in the ServerGroup, select the server with the smallest CurrentLoad.

(89) Step 376: End.

(90) Conventional load balancing mechanisms take into account only server utilization factor. If all servers are busy, no one can get in since it gives no preferential treatment to traffic with higher business value. The present application switch 20 is capable of prioritizing all inbound packets (i.e., packets on ingress traffic) according to predefined business values.

(91) In the preferred embodiment, the QoS controller 164 (FIG. 8) sorts all inbound packets into three priority types, High, Medium, and Low, and place packets of different types into queues of different priority levels, based on the business values assigned to the traffic. Packets in different type queues will be managed differently. When all servers are busy, the application switch will give preferential treatment to the High priority inbound packets, and delay and/or discard Medium and Low priority inbound packets. Using this mechanism, the application switch can allocate more server resource to traffic with higher business values.

(92) FIG. 12 illustrates schematically the QoS controller of FIG. 8 in more detail. As packets are received by the Application switch 20, their corresponding packet tags are being handled by the transmit controller 160 (see FIG. 8). The QoS controller 164 effectively sorts the packet tags into a series of queues. There is one set queues for each of the N servers. Each set of queues, such as that for Port 1 connecting to server 1 (see FIG. 8), comprises a High priority queue 410, a Medium priority queue 420, and a Low priority queue 430. The queues are First-In-First-Out (FIFO) queues. As the packet tags are received, the QoS controller puts each tags into one of the queues according to its assigned transmit instructions, i.e. selected server and priority. Thus, if a packet tag has the transmit instructions of server 1 and Medium priority, it will be queued in the Medium priority queue 420 associated with Port 1.

(93) The transmit scheduler 360 effectively generates a transmit queue by picking off the packet tags from the various queues according a predefined schedule and sends the prioritized transmit packet tags to the transmitter 324 of the Buffer controller 120 (see FIG. 8). The predefined schedule is based on the following requirements. Packets should be generally be ordered according to their assigned priority, but also in regard to how busy is the destination server. The second considerations allows management of server headroom, so that at any time a server would not be totally swamped by lower priority requests in the absence of High priority requests.

(94) The transmit scheduler schedules removal of the packet tags from each queue with the aid of two flags. The EmptyFlag indicates whether the queue is empty (=1) or nonempty (=0). When a queue is non-empty, it is ready for packet removal, subject to the condition of the ActiveFlag. The ActiveFlag is used to implement server headroom and indicates whether the queue is active (=1) or not active (=0) for packet tag removal. When a queue is inactive, it is in a sleep state, and can be used to hold back lower priority packets. In general, there will be a set of these two flags for each queue. The ActiveFlags such as HActiveFlag 414, MActiveFlag 424 and LActiveFlag 434 are updated dynamically at predetermined intervals based on the load of the associated server. Thus, for the High priority queue 410, the corresponding flags are HEmptyFlag 412 and HActiveFlag 414. For the Medium priority queue 420, the corresponding flags are MEmptyFlag 422 and MActiveFlag 424. For the Low priority queue 430, the corresponding flags are LEmptyFlag 432 and LActiveFlag 434.

(95) FIG. 13 is a table showing how the ActiveFlags are set as a function of server load (i.e. how busy the server is). Each server has load metrics to measure what it considers busy (see FIG. 10C). Max Load is a load level where the server is about to saturate. LOW Margin is a load level where the server is not busy and therefore has much headroom. HIGH Margin is a level where the server is quite busy and therefore has a little headroom left. It can be seen that, among the three priority queues, packet tags in the High priority queue will be served first without regard to server workload condition. Thus, HActiveFlag is active for packet removal (1) for all server load conditions. The packet tags in the Medium priority queue are active for removal only when the server load is below the HIGH margin mark. If the server load is above the HIGH margin mark, the removal of the Medium priority packet tags is slowed by putting the queue to sleep in alternate intervals. In the case of Low priority packet tags in the Low priority queue, they are active for removal only when the server load is below the LOW margin mark. When the server load is in the region between the LOW and HIGH margin marks, the removal of the Low priority packet tags are slowed by putting the queue to sleep in alternate intervals. When the sever load is above the HIGH margin mark. The Low priority queue is put to sleep.

(96) In addition to the sleeping times for Medium and Low priority queues, there are also maximum queue size thresholds for both Medium and Low priority queues. When the Medium (Low) priority queue reaches the maximum queue size, the oldest packet tags in the Medium (Low) priority queue will be discarded. Since High priority packet tags will be served first and there is likely no large queue size built up for these packet tags, there will be no maximum queue size restriction for them.

(97) FIG. 14 is a flow diagram illustrating a preferred schedule of packet prioritization for a given server port.

(98) High Priority Queue

(99) Step 450: While there is a packet tag in the High priority queue and the queue is active, transfer the packet tag to the transmitter. Otherwise go to Step 460.

(100) Medium Priority Queue

(101) Step 460: Do Steps 462 while the High priority queue is empty, otherwise go to Step 450.

(102) Step 462: While there is a packet tag in the Medium priority queue and the queue is active, transfer the packet tag to the transmitter. Otherwise go to Step 470.

(103) Low Priority Queue

(104) Step 470: Do Step 472 while the High priority queue is empty, otherwise go to Step 450.

(105) Step 472: Do Step 474 while the Medium priority queue is empty, otherwise go to Step 462.

(106) Step 474: While there is a packet tag in the Low priority queue and the queue is active, transfer the packet tag to the transmitter, otherwise go to Step 480.

(107) Step 480: End.

(108) For N server ports, when more than one port has a non-empty High priority queue, the transmit scheduler transfers the packet tags from the plurality of non-empty High priority queues in an equitable manner, such as using a Round Robin schedule. The Medium and Low priority queues are treated similarly.

(109) Referring again to FIG. 8, the transmit scheduler 160 effectively transfers the packet tags to the transmitter 324 as a transmit queue in the order prescribed by the schedule described above. In the meantime, an address modifier 366 in the transmit controller modifies the packets in the packet buffer 322 corresponding to the packet tags. It modifies the Layer 2-4 destination addresses to that of the designation server. In this way, when the transmitter 324 releases the packets in the packet buffer onto the IP bus 100, according the packet tags in the transmit queue, the packets will have the correct addresses to proceed to their respectively selected server.

(110) Traffic from a server back to the client is usually deterministic and the application switch merely performs the function of changing the IP and MAC addresses of a packet from that of the switch to that of the client. This is implemented by TCP splicing or Network Address Translation (NAT).

(111) The application switch is preferably implemented by a collection of tightly coupled application-specific integrated circuits (ASICs). In the preferred embodiment, a network processor, embodied by multiple programmable microengines and a core processor, is used to implement and manage the various components. An example of such a network processor is Intel IXP 1200 Network Processor manufactured by Intel Corporation, Santa Clara, Calif., U.S.A.

(112) Slow-Start New Server Selection

(113) According to another aspect of the invention, a slow-start server selection method is advantageous employed to alleviate the problem of a server newly put online from being swamped due to existing load balancing schemes.

(114) The four established load balancing algorithms identified earlier do not address the problem when a new server is brought up online among a group of servers participating in load balancing. The newly added server, by virtue of an initial low workload, can be flooded with new requests, which will quickly degrade the service quality perceived by the users. This is because these algorithms take into account only server utilization factor, (e.g., selecting a server with the least workload) resulting in the selection tipping heavily towards the newly added server.

(115) As described earlier, the preferred load-balancing scheme is Weighted Least Connection, which selects a server with the minimum CurrentLoad, where CurrentLoad=number of weighted connections=Summing over {DefaultServerWeight*ClassLoad(i)}, where i=1 to CurrentConnections. (See FIGS. 10B, 10C, 10D).

(116) In the slow-start load-balancing method, the server load metric for a newly added server has a configurable server-weight factor. In the calculation for CurrentLoad, the DefaultServerWeight is replaced by a DynamicServerWeight (see FIGS. 10C and 10D). The DynamicServerWeight is initially made larger but eventually converges to the value of the DefaultServerWeight. Generally, the DynamicServerWeight is such that it reduces the disparity in the normalized CurrentLoads (i.e., CurrentLoad normalized by ServerWeight) of the new server and a typical server among the group. In this way, the chance of the new server always having the smallest normalized CurrentLoad and therefore always being selected is reduced. As the new server establishes more connections with the application switch, the DynamicServerWeight is gradually reduced until it becomes the same as the Default Server Weight. At this point, the new server's normalized CurrentLoad will have increased to a level similar to the rest of the server group.

(117) FIG. 15 illustrates schematically a DynamicServerWeight that converges to the DefaultServerWeight as the normalized CurrentLoad of the newly put online server approaches the average normalized CurrentLoad of the other servers in a group participating in load balancing. In a preferred embodiment, DynamicServerWeight=.sup.2kDefaultServerWeight, where k is an integer initially set to equal SlowStartCount, which is a configurable number. In this way, DynamicServerWeight converges to DefaultServerWeight as k is counted down to zero during a period that the normalized CurrentLoad of the new server increases to approach a level similar to that of the rest of the servers in the group participating in load balancing. For example, initially k=5, and each time the disparity is reduced by a factor of two, k is reduced by one.

(118) FIGS. 16A and 16B are flow charts illustrating load-balancing with a newly incorporated server, according to one preferred embodiment of the invention.

(119) In a preferred implementation, there are three processes. The first is the initialization process of setting an initial value for the ServerWeight of the new server. The second is switching a packet subject to load balancing with the group of servers, including the new server. The third is to adjust the ServerWeight of the new server to converge to DefaultServerWeight over a predefined period during load balancing.

(120) FIG. 16A is a flow chart illustrating the process of adjusting the server weight of the new server being added to the group of servers under load balancing.

(121) Step 510: Initialize k=SlowStartCount.

(122) Step 512: Set ServerWeight=DynamicServerWeight=2.sup.kDefaultServerWeight, go to Step 540.

(123) Step 540: At predefined intervals while load balancing is ongoing (see Steps 530 and 532), test if k=>0?, if so, go to Step 542, else go to Step 550.

(124) Step 542: Set k1, decrementing the server-weight factor by half, then go to Step 512.

(125) Step 550: End.

(126) This is the point where k is zero, and the new server has a ServerWeight DefaultServerWeight. Its CurrentLoad normalized by its DefaultServerWeight is similar to that of the other servers in the group.

(127) FIG. 16B is a flow chart illustrating the process of performing load balancing with the new server included in the group of servers under load balancing. Load balancing can begin as soon as the ServerWeights for all the servers, including the newly added one, is set, as in Steps 512 and 520.

(128) Step 530: Compute CurrentLoad of the server using ServerWeight.

(129) Step 532: Select a server based on CurrentLoads among the Server Group. Content-Aware Switching Without Delayed Binding

(130) According to another aspect of the invention, a method is provided to perform content-aware switching without incurring delay and excessive processing while initially waiting for content to become available in order to make switching decisions.

(131) The servers in a data center/call center can be the performance bottleneck for web applications in many cases. All existing load-balancing algorithms mostly use Layers 3 and/or 4 information to select a server.

(132) As described earlier, different web applications may have different required server load implications. This information is derivable by identifying from the application layer (Layer 7) the class of application and associating it with a ClassWeight (see FIG. 10B). Load balancing is more refined when Class Weight is taken into consideration.

(133) However, application layer information typically arrives after the initial TCP handshaking process. The first few packets used for handshaking purposes carry no application layer information. Thus, if load balancing is also dependent on Layer 7 information, the switch will have to wait until after the handshaking is completed to obtain it in order to select a server (delayed binding). The former treats all applications on the same server group equally and does not take into account the difference in load demand by different applications. The latter uses TCP splicing and is process intensive.

(134) FIG. 17 illustrates the handshaking at the beginning of a TCP session between a client, an intermediate switch and a server under the TCP splicing scheme. First the client initiates a TCP session with the switch. The first three packets exchanged are for handshaking between client and switch. The application layer packets come after the handshaking packets. The switch then uses the application layer information to make switching decisions. Thereafter, the switch initiates another TCP session with the selected server. This tandem process of TCP splicing is inefficient and process intensive but is necessary if application layer information must first be obtained by the switch in order to select a server to switch to.

(135) The present invention prescribes using application layer (Layer 7) information to perform load balancing as soon as the first handshaking packet from a new TCP session arrives. This is accomplished by using the application layer information from a previous TCP session as a best estimate for the new session. This scheme works if there is only one server group in the server farm, as is typical, and therefore Layer 7 information is not necessary to select a server group. Thus, load balancing is performed on the basis of workloads of servers based on data from a previous TCP session. Since a server can be selected on the fly, the handshaking packets can be sent directly to the server without performing the tandem process of TCP splicing.

(136) FIG. 18 illustrates the streamlined TCP process of the present invention. When the switch receives a handshaking packet, a server is selected based on the servers' load metrics, which are dependent on Layer 7 information of a previous session. The packet is redirected on the fly to the server. Similar, the returned packet from the server is redirected at the switch on the fly to the client. As soon as a packet carrying Layer 7 information arrives, the switch uses it to update the server load metric so that it can provide the most current estimate for the next TCP session.

(137) As for QoS control, the few handshaking packets at the beginning of a new TCP session are assigned a default High priority so that the handshaking process can be completed without delay and the Layer 7 information be available as soon as possible. When the Layer 7 information becomes available, it will be used to prioritize the current packets in the manner described earlier.

(138) FIG. 19 is a flow chart illustrating the method of content-aware switching without delay binding.

(139) Step 600: If the packet is a first handshaking packet, go to Step 610, else go to Step 620.

(140) Step 610: Retrieve existing server load metrics for the group of servers under loads balancing. These existing server load metrics have been updated based on application layer information of a previous TCP session.

(141) Step 612: Select a server from the group of servers based on the existing server load metrics.

(142) Step 614: Set the packet to a default priority. Go to Step 630.

(143) Step 620: If the packet a handshaking packet, go to Step 622, else go to Step 630.

(144) Step 622: If application layer information for current TCP session has already been obtained, go to Step 624, else go to Step 630.

(145) Step 624: Use the application layer information from the packet to set priority for the packet.

(146) Step 626: Use the application layer information from the packet to update the server load metrics. The server load metric will be used in the next TCP session to select a server. Go to Step 630.

(147) Step 630: Direct the packet to the selected server according to a predefined schedule dependent on the assigned priority.

(148) Step 640: End

(149) Thus it is possible, by the present invention, to implement application-aware load balancing and QoS control without having to use delayed binding. The server load metrics used in the load-balancing algorithm are updated based on application layer information after a server is selected. This way, the server selection process does not need to wait (hence requiring delayed binding) for application layer information to arrive in order to select a server for the current request. However, after the application layer information is available, the server load metric is updated based on the application and hence reflected on the next server selection process.

(150) While the embodiments of this invention that have been described are the preferred implementations, those skilled in the art will understand that variations thereof may also be possible. Therefore, the invention is entitled to protection within the full scope of the appended claims.