:: Hani Jamjoom (هاني جمجوم) :: Research

Overview | Adaptation to Overload | QGuard | Publications on APFs

Overload in network servers is usually caused by an uncontrolled influx of requests from network clients. Since these requests for service are received as network packets, server load can be managed by controlling the influx of certain network packets, e.g., connection requests. Adaptive Packet Filters (APFs) is a general architecture designed for integrating signaling information with dynamic control in Internet servers. APFs provide overload protection and QoS differentiation for today's Internet servers. They require neither OS changes nor difficult offline capacity analysis. Furthermore, APFs are easily integrated into networking protocols, firewalls, or Layer-3+ load-balancers that connect servers to the Internet. APFs reduce the need for heavily over-designed servers since the request flow to the server will be matched to its capacity.

APFs can be seen as an enhancement of the classic network-based QoS-management approaches by allowing arbitrary load-inputs to affect traffic policing. Alternatively, one may view APFs as an extension to firewalling (e.g., ipchains) since they, too, can be configured to enforce arbitrary packet-filtering policies. What distinguishes APFs from traditional firewalls is that they respond to configurable load inputs by dynamically enforcing more or less restrictive packet filters. An APF allows alternative packet filters to be loaded into a filter controller and accepts feedback from load monitors. Depending on the configured filters and load indicators, an APF automatically enforces filters that avoid overload. APFs do not prescribe the use of any specific monitoring mechanism and can be integrated with various sources of monitoring information, e .g., SNMP, Tivoli, etc. (see above figure).

Basic Technology

Network-based QoS control and differentiation requires basic packet classification where each packet, once classified, will be treated according to a policy associated with its traffic class. Traffic classes are defined by information contained in the packets' IP headers:

Server-side applications via IP destination information.
Client populations via IP source address prefixes.
Packet types, such as, TCP, TCP-SYN, UDP, IPX, and ICMP.
DiffServ code points.
A combination of the above.

The APF notion of traffic classes is used in firewall configuration. A rule combines traffic class and policy. The policy specifies whether packets of the traffic class should be accepted, dropped, shaped, or policed to a particular rate. If multiple rules apply to an incoming packet, the most restrictive policy will be applied to the packet. This definition of rules is consistent with that of most modern firewall implementations.

Each individual rule defines QoS requirements for exactly one traffic class. Thus, QoS differentiation between competing traffic classes can only be achieved by installing rule combinations. Rule combinations are expressed in filters. For example, a filter of two rules could be set up to admit twice the packet rate from IP address X as from IP address Y. To guarantee QoS differentiation, the rules of a filter are considered a unit, i .e., all or none of its rules are enforced.

To make filters applicable to environments of unknown or variable server processing capacities, it is necessary to implement filter adaptation. Fixed filters with inadequate shaping rates could easily cause underutilization of network servers. For example, if one restricts incoming traffic to a moderately-loaded Internet server, one risks dropping requests which the server could have handled easily. However, installing only permissive filters to accommodate the common (lightly-loaded) case would be a false conclusion. Permissive filters will fail to defend the server from load surges.

Filter adaptation is achieved in filtering dimensions (FDims). Each FDim is a linear list of filters, f1, f2, ..., fn, only one of which is enforced at any given time. A switch from one filter to another is an atomic operation, meaning that the old filter is uninstalled and the new filter is installed without processing any network packets in between. The figure above shows an expanded view of a FDim. The filter selection process is driven by a FDim-specific load index, which is fed by external load-monitoring software.

To provide effective overload protection, each FDim configuration must satisfy the following constraints:

filters are ordered by increasing restrictiveness,
the least restrictive filter does not police incoming traffic, and
the most restrictive filter drops all incoming traffic.

Multiple FDims may be installed simultaneously, each tied to its own load variable. This pays tribute to the fact that different types of overload may be caused by different network services, which
must be policed separately. Support for multiple FDims is particularly useful when an APF-enabled
device controls access to different services, each of which is located on its own separate backend server.

APFs are conceptually similar to CBQ. There are, however, three key differences between the two. First, APFs are inbound controls. Therefore, they remain effective QoS controls even if they are only installed on the network servers. Second, APFs are not tied to any particular link scheduling or packet scheduling architecture. Finally, APFs may police incoming packets based on load measurements other than just link utilization. CBQ cannot adapt incoming packet rates to match the network servers' capacities.

Adaptation to Overload

In the APF framework, QoS differentiation and overload defense depend on the controller's ability to determine the best filter for incoming traffic. The following control mechanism automatically determines the least restrictive filter in each FDim that prevents their respective monitoring variables from reporting overload. This optimizes overall server throughput subject to the ``no-overload'' constraint.

Load indices are integral numbers between 0 and 100, with 0 representing no load and 100 representing highest load.
APF associates user-defined thresholds with each load index as to what constitutes an overload and an underload.
When an overload is detected on some load index, v_i, the next most restrictive filter for its corresponding FDim, F_i, is applied. If this change triggers the application of the most restrictive filter for that FDim, the FDim is flagged as severely overloaded potentially requiring network administrator intervention.
When an underload is detected on load variable, v_i, the next less restrictive filter for its corresponding FDim, F_i, is applied.
APFs are configured with a configurable inter-switching delay, s_i, for each FDim, F_i to stabilize its adaptation behavior.
APFs keep track of how long each filter is applied against incoming load. This is an indication of a filter's effectiveness, and therefore, important for FDim reconfiguration.

FDims eventually begin to oscillate between the application of a few adjacent filters because the policies of one filter are too restrictive, and too permissive in the other. This behavior is a natural consequence of the controller's design and is non-problematic unless the controller oscillates between vastly different filters. In this case, the FDim is configured too coarse-grained and needs to be refined. We tackle this problem using an automated FDims generation and reconfiguration tool called FDim Manager. The FDim Manager analyzes incoming traffic statistics and the oscillations of the kernel-based control loop to devise more effective packet filters. Moreover, it takes policy input from the system administrator into account when creating packet filters that are to be used by the kernel-based controller.

Traffic Enforcement

As shown in the [SIGCOMM'03,ToN'04], the traffic enforcement mechanism can have a significant impact on the behavior of arriving requests due to the persistent nature of incoming requests. In particular, the re-synchronization of dropped requests can (and in our experience often does) reduce the stability of the underlying control mechanisms. For instance, referring to Figure 5 in [ToN'04], one can see that a temporary burst may induce an oscillatory behavior in request arrival, which in turn may cause an oscillation in the traffic adaptation mechanism. That is, during peak arrival, the adaptation mechanism may move to a more restrictive policy (or filter) to avoid overload, and vice versa.

It is, thus, necessary for our adaptation mechanism to appropriately account for this possible behavior. This considerably complicates the design of the adaptation controller as it must now account for the possible correlation between the applied control (i.e., traffic filter) and future request arrivals. This is further complicated by the fact that incoming requests are inherently bursty. Without a steady arrival distribution (which is seldom the case), it is unclear (from a traditional control optimization perspective) how the stability of the underlying controller can be verified. (We note here that similar to any control mechanism, stability is an important, if not the pivotal, issue in the design of effective and predictable controllers.)

Instead of complicating the design of the controller, we choose to take advantage of the results in [SIGCOMM'03] where we have shown that Persistent Dropping (PD) can virtually eliminate the effects of clients' persistence from incoming traffic. Since PD is already designed as a low-level filtering mechanism, it fits well with the overall architecture of APF. Specifically, we use PD to decouple the applied control from future arrival (this is from the perspective of the adaptation mechanism). Therefore, each time a new filter is installed, it is effectively changing the drop probability of the persistent dropping filter that is assigned to each traffic class without erasing the state of the previous filter.

It is important to note that the filtering mechanism in APF is not limited to PD. APF can be configured with different mechanisms that can be designed to handle different types of traffic. This flexibility is important to better handle the changing nature of Internet services. However, for the remainder of the chapter, we assume that traffic filtering is engineered around the persistent dropping mechanism.

Prototype Implementation

The APF prototype is implemented as an extension module, called QGuard, for the Linux 2.2.14 kernel's firewalling layer ipchains . ipchains provides efficient packet header matching functionality and simple packet rejection policies. We implemented additional support for traffic shaping. We note that Linux 2.4.x firewalling support, netfilters , already implements this policy. Our prototype implements the well-known token bucket rate-control scheme by associating each traffic class with a counter of remaining tokens, a bucket volume, a timestamp for the last token replenishment time, and a per-second token rate. These variables are part of the firewalling rule data structure.

As soon as a FDim is created inside the kernel, user-space scripts may start reporting load for it. This, too, is done via a special system call. Less invasive configuration mechanisms like a configuration file, the so -called /proc file system, or SNMP MIBs could have been used instead. However, this detail does not discount our prototype as a proof-of-concept.

To avoid any conflicts between adaptive filters and firewalling rules that warrant network security, dynamic QGuard filters are always the last to be enforced. Thus, a QGuard-enabled system will never admit any packets that are to be rejected for security reasons. Our particular implementation achieves this goal by linking the QGuard firewalling chain as the last rule chain into ipchain's input chain list.

The QGuard implementation relies on a distributed user-space monitor to obtain its load information (see D.MON in figure above). It consists of monitors on the backend servers and a collector component, which resides on the AFP-enabled device. Whenever the load on the backend servers changes, the collector receives load updates, which it feeds through to the QGuard kernel module. A configuration file specifies the association between load indices and FDims. This flexible monitoring architecture allows for simple reconfiguration of the basic adaptation mechanism. The above figure gives several examples of how FDims can be configured to achieve different performance goals. Hence, we were able to explore a variety of different load indicators (e.g. paging rate, disk access rate, idle time, bandwidth consumption, packet arrival rate, and TCP timeouts rate), their relationship to overload, and their usability in QGuard-based overload defense.

Release Notes:

Currently, there is no official release of the QGuard code. We expect to have one sometime in the future.

Publications on APFs

J. Reumann and H. Jamjoom, "Adaptive Packet Filters" In the Proc. of IEEE GLOBECOM, San Antonio, Texas, November, 2001.
H. Jamjoom and J. Reumann. "QGuard: Protecting internet servers from overload." University of Michigan Tech. Rep., CSE-TR-427-00, 2000
J. Reumann, H. Jamjoom, and K. Shin. "Dynamic Filter Selection to Protect Internet Servers From Overload." U.S. provisional application Serial No. 60/241,773, filed October 19, 2000.