Note: Descriptions are shown in the official language in which they were submitted.
CA 02667163 2009-05-28
Packet Throttling System and Method of Throttling Packet Reception
FIELD OF THE INVENTION
[0001 ] The present invention relates to a packet throttling system and a
method of
throttling packet reception, and more specifically, to a packet throttling
system and a
method of throttling packet reception at an interrupt level.
BACKGROUND OF THE INVENTION
[0002] Computer networks experience rapid and continuous increases in traffic
volumes as new types of bandwidth-hungry applications, such as Peer-2-Peer
file
sharing and video streaming tools, become more popular. This increasing
traffic
volume creates problems for all aspects of a network, but most significantly
at the
head-end of a network where the traffic passes through a gateway or routing
device.
That head-end device must be able to offer its provisioning and traffic
forwarding
functionality under the most extreme conditions with which it is presented.
This often
requires either frequent upgrades of the head-end device, or the addition of
traffic-
control mechanisms throughout the network. However, frequent upgrades and
control mechanism addition are often not practical or cost effective in many
situations.
[0003] Network traffic is transmitted as small discrete units of data called
packets.
Packets can arrive at a network device at very fast rates, such as hundreds or
thousands of packets per second. A server having a central processing unit
(CPU) is
provided with network interface card (NIC) connected to a network to receive
packets
from and transmit to the network. When a packet arrives at a server's NIC from
a
network to which that NIC is connected, that NIC notifies the server's CPU of
the
arrival of a packet. This notification is accomplished with the generation of
a CPU
interrupt by the NIC. An interrupt very briefly pauses the processing that the
CPU is
currently doing, and focuses the CPU's attention on the interrupt. The
operating
system which is running on the CPU has a defined small and fast set of
instructions,
known as an interrupt handler, to be processed as a result of the interrupt. A
-1-
CA 02667163 2009-05-28
network interrupt handler for a received packet is responsible for, at a
minimum,
copying the packet from the NIC's internal packet buffer into the server's
central
memory, and preparing the operating system for further processing of the
packet.
[0004] An interrupt can take the CPU's attention away from almost any task
which
the CPU is executing, at almost any time. Since thousands of network
interrupts can
occur each second, a network interrupt handler must execute very quickly, in
order to
leave the server responsive to other tasks, such as application processing,
and to
enable the server to process all of the many types of interrupts which occur.
[0005] Interrupt lines from devices that send CPU interrupts to the CPU can be
temporarily disabled by the operating system or by device drivers. This is
usually
performed only by device drivers for purposes necessary for the fundamental
reception and transmission of data. A disabled interrupt line generates no
interrupts.
[0006] Some operating systems, such as Linux, implement a scheme which
extracts
much of the work from interrupt handlers and places it into special operating
system
tasks known as soft interrupt handlers. This allows an interrupt handler to
perform
much less work in much less time, thereby decreasing the expense of an
interrupt. A
soft interrupt handler is executed by the operating system when the operating
system
decides that it has time to do so, which makes a soft interrupt handler less
intrusive
than a regular interrupt handler. This division of labour between interrupts
and soft
interrupts has lead to the designation of interrupts as hard interrupts. A
hard
interrupt (hardirq) is initiated by a hardware device, such as a network
interface card
or a hard disk controller. A soft interrupt (softirq) is set up within a hard
interrupt
handler, and then scheduled by the operating system for execution at a later
time.
The use of soft interrupt handlers allows a hard interrupt handler to postpone
the
expensive and time-consuming parts of a packet's reception processing, such as
the
interpretation of the packet's headers.
[0007] Some servers possess multiple NICs. Usually each NIC generates hard
interrupts on a different interrupt line, although NICs can occasionally share
interrupt
-2-
CA 02667163 2009-05-28
lines. All of the NICs' hard interrupt handlers generate the same type of
packet
reception soft interrupt, and thus, for soft interrupt scheduling purposes,
the
operating system does not care which NIC caused the soft interrupt.
[0008] Since hard interrupt handlers execute much faster, and with an
inherently
higher priority than soft interrupt handlers, an operating system can find
itself with a
large backlog of soft interrupts to process. Soft interrupt handlers are
executed by
the operating system with a higher priority than other operating system tasks,
and
accordingly, when there is a backlog of soft interrupts, the operating system
has less
time to allocate to other tasks. This situation can make the server almost
unresponsive in various ways: for example, simple applications such as word
processing may be sluggish, complex applications such as web servers may be
unable to service requests in a timely manner, leading to communication
timeouts,
and basic network connectivity to and from the server may be impaired, because
of
the backlog of soft interrupt handlers.
[0009] Some servers possess multiple physical and/or logical CPUs. A hard
interrupt
is processed by one of the CPUs. Each soft interrupt is also processed by a
single
CPU. There is no guarantee that the same CPU always processes the same type of
hard interrupt or soft interrupt. It is therefore not impossible for more than
one CPU
to be overloaded with soft interrupts.
[0010] In practice, when a server is unable to process received network
traffic in a
timely manner, the traffic backlog often increases in a superlinear manner, as
clients
and protocols resend their requests over and over. This makes a backlog of
packet
reception soft interrupt handlers even more serious.
[0011] It is therefore desirable to provide an operating system with a
mechanism
which can alleviate a backlog of packet reception soft interrupt handlers,
leaving the
server responsive even under very high network traffic load conditions.
-3-
CA 02667163 2009-05-28
SUMMARY OF THE INVENTION
[0012] It is an object of the invention to provide an improved a packet
throttling
system and a method of throttling packet reception that obviates or mitigates
at least
one of the disadvantages of existing systems.
[0013] The invention uses a throttling mechanism for throttling packet
reception
interrupt handlers based on CPU interrupt loads.
[0014] In accordance with an aspect of the present invention, there is
provided a
packet throttling system for a network head-end device having one or more
central
processing units (CPUs) and an operating system running thereon for processing
network head-end device tasks. The operating system has interrupt handling
code
to implement one or more interrupt handlers in one or more of the CPUs for
processing interrupts. The packet throttling system comprises a CPU interrupt
load
examiner, a throttling period calculator and an interrupt handler terminator.
The CPU
interrupt load examiner is provided for determining a current CPU interrupt
load for
each of the CPUs, the current CPU interrupt load being a proportion of a CPU's
time
that is being spent servicing any interrupt handlers. The throttling period
calculator is
provided for calculating a throttling period for each of the CPUs based on the
current
CPU interrupt load, the throttling period being a period between permitted
packet
receptions for the CPU. The interrupt handler terminator is provided for
terminating a
packet reception interrupt handler handling a packet reception interrupt in a
receiving
CPU if the throttling period of the receiving CPU has not elapsed since the
receiving
CPU handled a last permitted received packet.
[0015] In accordance with another aspect of the invention, there is provided a
method of throttling packet reception for a network head-end device having one
or
more central processing units (CPUs) and an operating system running thereon
for
processing network head-end device tasks. The operating system has interrupt
handling code to implement one or more interrupt handlers in one or more of
the
CPUs for processing interrupts. The method comprises the steps of determining
a
-4-
CA 02667163 2009-05-28
current CPU interrupt load for each of the CPUs, the current CPU interrupt
load
being a proportion of a CPU's time that is being spent servicing any interrupt
handlers, calculating a throttling period for each of the CPUs based on the
current
CPU interrupt load, the throttling period being a period between permitted
packet
receptions for the CPU, and terminating a packet reception interrupt handler
handling
a packet reception interrupt in a receiving CPU if the throttling period of
the receiving
CPU has not elapsed since the receiving CPU handled a last permitted received
packet.
[0016] In accordance with another aspect of the invention, there is provided a
computer readable medium storing computer readable code for execution in a
computer, the code having instructions for implementing a method of throttling
packet reception for a network head-end device having one or more central
processing units (CPUs) and an operating system running thereon for processing
network head-end device tasks, the operating system having interrupt handling
code
to implement one or more interrupt handlers in one or more of the CPUs for
processing interrupts. The method comprises the steps of determining a current
CPU interrupt load for each of the CPUs, the current CPU interrupt load being
a
proportion of a CPU's time that is being spent servicing any interrupt
handlers,
calculating a throttling period for each of the CPUs based on the current CPU
interrupt load, the throttling period being a period between permitted packet
receptions for the CPU, and terminating a packet reception interrupt handler
handling
a packet reception interrupt in a receiving CPU if the throttling period of
the receiving
CPU has not elapsed since the receiving CPU handled a last permitted received
packet.
[0017] This summary of the invention does not necessarily describe all
features of
the invention.
-5-
CA 02667163 2009-05-28
BRIEF DESCRIPTION OF THE DRAWINGS
[0018] These and other features of the invention will become more apparent
from the
following description in which reference is made to the appended drawings
wherein:
Figure 1 is a block diagram showing a packet throttling system in accordance
with an
embodiment of the present invention;
Figure 2 is a flowchart showing a method of throttling packet reception in
accordance
with an embodiment of the present invention;
Figure 3 is a block diagram showing a packet throttling system in accordance
with
another embodiment of the present invention;
Figure 4 is a block diagram showing an embodiment of the packet throttling
system;
Figure 5 is a flowchart showing an example of calculation by the packet
throttling
system;
Figure 6 is a block diagram showing an embodiment of a throttling period
calculator
of the packet throttling system;
Figure 7 is a block diagram showing an embodiment of a packet reception hard
interrupt throttling unit of the packet throttling system;
Figure 8 is an example of a pseudo code of the throttling operation of the
packet
throttling system; and
Figure 9 is a flowchart showing a method of throttling packet reception in
accordance
with another embodiment of the present invention.
DETAILED DESCRIPTION OF PREFERRED EMBODIMENTS
[0019] Referring to Figure 1, a packet throttling system 100 in accordance
with an
embodiment of the present invention is described. The packet throttling system
100
is provided in a network head-end device 10 of a local area network (LAN) 60.
The
network head-end device 10 may be a server, gateway or router that routes
traffic to
or from network devices on the LAN 60 from or to an outside network, e.g., a
wide
area network (WAN) 80, which may be the Internet.
-6-
CA 02667163 2009-05-28
[0020] The network head-end device 10 has one or more CPUs 12 for processing
network head-end device tasks. The head-end device 10 has an operating system
running on the CPUs 12. The operating system has interrupt handling code to
implement one or more interrupt handlers 14 in one or more of the CPUs 12 for
handling interrupts.
[0021 ] The packet throttling system 100 throttles packets received by the
head-end
device 10. It is an operating system level defense against excessive amounts
of
received network traffic, in terms of numbers of packets, rather than sizes of
packets.
The packet throttling system 100 has a CPU interrupt load examiner 110, a
throttling
period calculator 120 and an interrupt handler terminator 130.
[0022] The CPU interrupt load calculator 110 determines a current CPU
interrupt
load for each of the CPUs 12. A current CPU interrupt load is calculated as a
proportion of a CPU's time that is being spent servicing any interrupt
handlers 14. To
determine current CPU interrupt loads, the CPU interrupt load calculator 110
may
use the statistics of CPU usages maintained by the operating system.
[0023] The throttling period calculator 120 calculates a throttling period for
each of
the CPUs 12 based on the current CPU interrupt load. A throttling period is a
period
between permitted packet receptions for a specific CPU 12. A packet received
within
the throttling period is subject to the packet throttling by the packet
throttling system
100. The length of the throttling period of a specific CPU 12 varies depending
on the
current CPU interrupt load of the specific CPU 12.
[0024] The CPU interrupt load calculator 110 and the throttling period
calculator 120
may recalculate current CPU interrupt loads and throttling periods
intermittently at a
predetermined throttling examination interval.
[0025] The interrupt handler terminator 130 drops the received packet and
terminates
a packet reception interrupt handler handling a packet reception interrupt
when the
-7-
CA 02667163 2009-05-28
packet reception interrupt is received within the throttling period of the CPU
that is
processing the packet reception interrupt handler.
[0026] Figure 2 shows an example of the operation of the packet throttling
system
100. In the packet throttling system 100, the CPU interrupt load calculator
110
determines a current CPU interrupt load for each CPU 12 (150), and the
throttling
period calculator 120 calculates a throttling period for each CPU 12 based on
the
current CPU interrupt load (152). The current CPU interrupt loads and
throttling
periods for the CPUs 12 are recalculated intermittently (154). As the first
calculation
and recalculation are carried out in the same manner, the terms calculation
and
recalculation may be used interchangeably hereinafter.
[0027] When a packet is received by the network head-end device 10, a packet
reception interrupt is generated and received by one of the CPUs 12 (160).
This
initiates a packet reception interrupt handler 14a in the receiving CPU 12a to
handle
the packet reception interrupt (162). The initiation of the packet reception
interrupt
handler 14a may initiate the recalculation of the current CPU interrupt loads
and
throttling periods (164).
[0028] When the packet reception interrupt handler 14a is initiated, the
interrupt
handler terminator 130 determines the throttling period of the receiving CPU
12a
(170), and determines if the throttling period of the receiving CPU 12a has or
has not
elapsed since the receiving CPU 12a handled a last permitted received packet
(172).
If the throttling period has elapsed, it means that the packet reception is
permitted,
and thus, the interrupt handler terminator 130 allows the interrupt handler
14a to
continue processing the packet reception interrupt and the received packet to
be
processed further by the head-end device 10 (174). If the throttling period
has not
elapsed (172), it means that the packet reception is not permitted, and thus,
the
interrupt handler terminator 130 drops the received packet and terminates the
packet
reception interrupt handler 14a (176). Thus, the excess packet reception is
throttled.
-8-
CA 02667163 2009-05-28
[0029] Some Operating Systems implement hard interrupt handlers and soft
interrupt
handlers, and some Operating Systems implement hard interrupt handlers only.
For
Operating Systems that implement soft interrupt handlers, in the packet
throttling
system 100, the CPU interrupt load calculator 110 determines a current CPU
soft
interrupt load, which is a proportion of a CPU's time that is being spent
servicing any
soft interrupt handlers. The throttling period calculator 120 calculates a
throttling
period based on the current CPU soft interrupt load. The interrupt handler
terminator
130 terminates a packet reception soft interrupt handler handling a packet
reception
interrupt of a received packet.
[0030] Also, the packet throttling system 100 may have a hard interrupt
throttler 140,
as shown in Figure 3. A packet reception interrupt is received on a hard
interrupt
line. The hard interrupt throttler 140 temporarily disables the hard interrupt
line
based upon the recent CPU soft interrupt load.
[0031] Figure 3 shows a packet throttling system 300 in accordance with
another
embodiment of the present invention. The packet throttling system 300 is
suitably
used in a Visitor Based Network (VBN) server 200, which is a network head-end
device providing network provisioning and traffic forwarding services for a
VBN
network or LAN 260. The VBN server 200 allows temporary access to an outside
network or WAN 280 for roaming clients or user devices 262 that are
temporarily
connected to the LAN 260. The VBN server 200 has one or more CPUs 210 on
which an operating system is running, and network interface cards (NICs) 220
for
communication with the LAN 260 and the WAN 280. In this embodiment, CPUs 210
are capable of implementing soft interrupt handlers from hard interrupt
handlers.
[0032] While the packet throttling system 300 is further described hereinafter
based
on the use in the LAN 260 in this embodiment, the packet throttling system 300
may
also be suitably used in different types of servers, such as web servers and
Domain
Name System (DNS) severs.
-9-
CA 02667163 2009-05-28
[0033] VBN networks also face the issues surrounding the increasing traffic
volumes.
The frequent upgrade of a VBN network is rarely practical or cost-effective.
It is
therefore beneficial for the VBN server 200 to possess the ability to mitigate
the
detrimental effects of very high rates of traffic, while still offering VBN
server
functionality. The packet throttling system 300 provides the VBN server 200
with
such a traffic mitigation ability.
[0034] There are well-known means of controlling network bandwidth usage on a
gateway or router such as a VBN server. These tools include quality-of-service
(QoS) enforcement, and packet filter that enforces packet rate limiting. QoS
applies
bandwidth allocation rules to specific IP addresses. It usually operates on
amounts
of data rather than numbers of packets, so that the size of individual packets
is
considered. QoS can also consider numbers of packets. A packet filter may
maintain packet counters originating from and/or destined to each relevant IP
address, and drop packets if certain thresholds have been exceeded. These
tools
serve to protect applications, which run on the gateway or router, from
excessive
amounts of traffic. However, these tools do not protect the operating system
itself. If
the operating system becomes swamped by the processing of excessive rates of
incoming traffic, then these higher-level traffic control tools are of little
use. Also,
these tools are often full-featured and very reliable ways to control the rate
of
packets flowing through the server. However, these tools are applied after the
packets have been fully received by the operating system. If the operating
system is
backlogged by soft interrupt handlers, then the QoS and packet filter may not
be
allocated enough processing time by the CPU(s) to enforce their policies.
[0035] The packet throttling system 300 works by dropping received packets
before
they reach any of the networking subsystems of the operating system, apart
from the
received packet soft interrupt handler. This frees up CPU time at the expense
of
network reliability for traffic of very high rates, e.g., for streams of
traffic possessing
relatively high packet frequencies. However, it can increase network
reliability for
normal traffic, e.g., for streams of traffic possessing relatively low packet
frequencies.
-10-
CA 02667163 2009-05-28
[0036] In this embodiment, the packet throttling system 300 is incorporated
entirely
within the kernel of the operating system of the VBN server 200. Configuration
of the
packet throttling system 300 is performed using a standard kernel
configuration
mechanism, for example, using the sysctl interface of the Linux kernel, which
uses
numerical values entered by a system administrator into special files which
are
automatically parsed and applied by the kernel. In a different embodiment, the
packet throttling system 300 may be configured using a graphical throttling
configuration tool added to the VBN server 200.
[0037] The VBN server 200 has a registration driver 230 that manages a
collection of
IP addresses which can be allocated to network entities on the LAN 260 behind
the
VBN server 200. The entities are devices connected to the LAN 260, and which
possess IP addresses and which send traffic to and receive traffic from the
VBN
server 200. For example, these entities send packets to a NIC 220 located
within the
VBN server 200. The VBN server 200 classifies these entities in a specific
manner
of the VBN server 200. The classifications of interest to the packet
throttling system
300 are Registered, Device, Router, and Foreign. A fifth classification is
implied,
representing the population which is not contained within the other four
classifications, and is referred to as the Regular classification. The
classifications
are mutually exclusive, although individual IP addresses may be reclassified
at any
time by the normal functioning of the VBN server 200.
- A Registered entity is permitted access to the VBN server 200's WAN 280,
through
the VBN server 200.
- A Device entity is a network access concentrator, which may relay some types
of
traffic from its own Internet Protocol (IP) address on behalf of other
entities. An
example is a DHCP Relaying switch.
- A Router entity is a network access concentrator which relays all traffic,
via its own
IP address, from entities behind it.
- A Foreign entity is defined as an entity which is not managed by the
registration
driver 230. This may include entities on the WAN 280 as well as on the LAN
260.
-11-
CA 02667163 2009-05-28
- A Regular entity is not a known network access concentrator, and is not a
router,
but is managed by the registration driver 230, such as an unregistered client.
A
Regular entity is denied access to the server's WAN 280,
[0038] The packet throttling system 300 applies different degrees of entity-by-
entity
throttling to the different classes of network entities which may be
transmitting traffic
to the VBN server 200.
[0039] Figure 4 shows an embodiment of the packet throttling system 300. In
this
embodiment, the packet throttling system 300 has a registration driver
interface 310,
soft interrupt hander interface 320, data manager 330, CPU soft interrupt load
monitor 340, throttling period calculator 350, soft interrupt handler
terminator 360,
timekeeper soft interrupt examiner 370, hard interrupt line disabler 380 and
configuration manager 390. In a different embodiment, the packet throttling
system
300 may have fewer or more elements.
[0040] The packet reception soft interrupt throttling unit 400 interacts with
the
registration driver 230 through the registration driver interface 310. Through
the
registration driver interface 310, the registration driver 230 informs the
packet
throttling system 300 of the number of assignable IP addresses that the
registration
driver 230 is managing, and also of the numbers of Registered, Unregistered,
Device, and Router entities which are currently assigned IP addresses by the
registration driver 230. The VBN server 200 allocates or assigns IP addresses
even
to statically addressed clients, and thus, the concept of IP address
assignment by
the VBN server 200 does not necessarily imply the DHCP protocol. The
registration
driver 230 informs the packet throttling system 300 of the number of IP
addresses
that it is managing when the registration driver 230 is initialized. If the
registration
driver 230 is re-initialized, then the packet throttling system 300 is re-
initialized as
well. The registration driver 230 informs the packet throttling system 300 of
device
classifications and reclassifications on the fly, for example, when users are
-12-
CA 02667163 2009-05-28
registered or unregistered by the registration driver 230, or when the
registration
driver 230 reclassifies an entity as a device or a router.
[0041]The data manager 330 manages a throttling data store 332 to maintain
throttling related data for each CPU 210, including a short history of CPU
records for
each CPU, as further described below.
[0042] The CPU soft interrupt load monitor 340, the throttling period
calculator 350
and the soft interrupt handler terminator 360 are used to throttle packets by
terminating packet reception soft interrupt handlers 212, and they may be
collectively
called a packet reception soft interrupt throttling unit 400 hereinafter. The
packet
reception soft interrupt throttling unit 400 alleviates packet reception soft
interrupt
backlogs so that any available QoS and packet filters can work properly. The
packet
reception soft interrupt throttling unit 400 also serves to make CPU time
available for
applications running on the VBN server 200. The packet reception soft
interrupt
throttling unit 400 of the packet throttling system 300 provides an operating
system
level defense against excessive amounts of received network traffic, in terms
of
numbers of packets.
[0043] The CPU soft interrupt load monitor 340 determines a current CPU soft
interrupt load for each CPU 210. The current CPU soft interrupt load is
represented
by a proportion of a CPU's time that is being spent servicing any soft
interrupt
handlers. The kernel of the operating system of the VBN server 200 typically
maintains statistics on how much time each of the server's CPUs spends on
various
types of tasks, such as hard interrupt processing, soft interrupt processing,
and
application processing. The CPU soft interrupt load monitor 340 accesses these
statistics through existing facilities, in order to calculate the percentage
of time during
the preceding throttling examination interval which each CPU has spent
servicing
soft interrupt handlers. There is no distinction made, either within the
kernel's
original CPU usage statistics, or within the packet throttling system's
statistics,
between packet reception soft interrupt handling and other types of soft
interrupt
-13-
CA 02667163 2009-05-28
handling. A fundamental assumption is made by the packet throttling system 300
that a properly functioning VBN server 200 experiences sustained high soft
interrupt
loads only during times of excessive packet reception. This assumption is not
guaranteed to be correct, but for the practical purposes it can be considered
a valid
assumption.
[0044] The throttling period calculator 350 calculates a throttling period,
for each of
the classifications of the IP addresses for each of the CPUs, based on the IP
address information that the registration driver interface 310 received from
the
registration driver 230 and the current CPU interrupt load calculated by the
CPU soft
interrupt load monitor 340. A throttling period is a period between permitted
packet
receptions for a specific IP address class for a specific CPU. Thus, a
throttling
period represents an allowed packet rate for a specific IP address class for a
specific
CPU.
[0045] Because soft and hard interrupt handlers can execute on various CPUs
210,
the packet reception soft interrupt throttling unit 400 maintains in the
throttling data
store 332 a separate set of statistics and throttling periods for each CPU
210. Thus,
CPU-specific packet reception throttling can be performed.
[0046] The packet throttling system 300 enforces packet reception throttling
over
throttling examination intervals. At the start of each throttling examination
interval,
the CPU soft interrupt load monitor 340 and throttling period calculator 350
recalculates its statistics and throttling periods (or allowed packet rates),
and applies
those throttling periods (or allowed packet rates) until the end of the
throttling
examination interval. The length of the throttling examination interval is a
configuration option, and can be changed at any time. Throttling examination
intervals are delimited only by recalculations of the statistics and rates.
There is no
period of throttling cessation in between throttling examination intervals.
[0047] The recalculations by the CPU soft interrupt load monitor 340 and
throttling
period calculator 350 may be initiated in two ways: by an intermittently
executing
-14-
CA 02667163 2009-05-28
kernel task which runs every N seconds, where N is the current length of a
throttling
examination interval, and by the packet reception soft interrupt handler. Both
the
intermittent task and the soft interrupt handler check to see if more than N
seconds
have elapsed since the previous recalculation, before initiating a new
recalculation.
The recalculation initiation from within the soft interrupt handler enables
the CPU soft
interrupt load monitor 340 and throttling period calculator 350 to perform the
recalculation even under very high load conditions when intermittent kernel
tasks
may not occur in a timely manner. The recalculation initiation from within the
intermittent kernel task ensures that the recalculation occurs even when no
packets
are being received.
[0048] Figure 5 shows an example of the recalculation. The recalculation is
carried
out, for each CPU, by examining CPU load and determining a current soft
interrupt
load percentage (600), recalculating a packet reception multiplier (PRM)
period
based upon the current soft interrupt load percentage (602), and recalculating
throttling periods for the different classes of network entity recognized by
the VBN
server 200 (604). The recalculation may also include recalculation of hard
interrupt
throttling parameters based upon the recent soft interrupt load percentages
(606)
when the hard interrupt throttler 380 is used, as further described below.
[0049] During the CPU load examination and determination of current soft
interrupt
load percentages (600), the CPU soft interrupt load monitor 340 determines the
percentage of time which each CPU 210 in the server has spent processing soft
interrupt handlers during the preceding throttling examination interval, as
described
above.
[0050] Figure 6 shows an embodiment of the throttling period calculator 350
that
suitably carries out the recalculation of the throttling periods. In this
embodiment, the
throttling period calculator 350 has a PRM calculator 352, a base applied
period
calculator 354 and a class applied period calculator 356.
-15-
CA 02667163 2009-05-28
[0051 ]The PRM calculator 352 carries out the calculation of a packet
reception
multiplier (PRM) period for each CPU 210 (602). The PRM calculator 352
maintains
in the throttling data store 332 a packet reception multiplier (PRM) which is
an ordinal
value that is adjusted up and down to alter permitted packet reception
frequencies.
This PRM provides a base for further calculations, which then produce rates or
throttling periods that are applied to received traffic. These further
calculations are
described below. Increasing the PRM increases the periods between permitted
packet receptions for each IP address, and thus decreases the rate of
permitted
packet receptions. Decreasing the PRM has the opposite effect. Since the PRM
determines the values of the applied periods, alteration of the PRM is a
legitimate
means of adjusting the all of the throttling periods in a consistent manner.
[0052] A larger period between allowed packet receptions lowers the amount of
time
the CPU spends processing packets. A smaller period increases the amount of
CPU
time. The modifications to the kernel's packet reception soft interrupt
handler
reference the allowable packet reception periods in order to determine if a
packet
should be dropped.
[0053] For each CPU, the PRM calculator 352 considers the current soft
interrupt
load percentage, the configured maximum soft interrupt load percentage, and
the
configured soft interrupt load tolerance, which is a percentage above or below
the
configured maximum which is considered acceptable. If the current soft
interrupt
load percentage is too high, then the PRM calculator 352 increases the PRM. If
the
current soft interrupt load percentage is below the maximum allowed
percentage,
then the PRM calculator 352 decreases the PRM as unnecessary throttling is
undesirable. If the current soft interrupt load percentage is within an
acceptable
range of the maximum allowed soft interrupt load percentage, then the PRM is
not
altered.
[0054] Immediately after initialization of the packet throttling system 300,
the PRM
calculator 352 sets the PRM to an absolute minimum, in order to not
unnecessarily
-16-
CA 02667163 2009-05-28
interfere with traffic. In very simple terms, the PRM is increased only if the
current
soft interrupt load percentage exceeds the configured maximum soft interrupt
load
percentage. The PRM is increased, as further described below, up to an
absolute
maximum, until the current soft interrupt load percentage is within range of
the
configured maximum soft interrupt load percentage, plus or minus the tolerance
percentage. If the current soft interrupt load percentage is below the
configured
maximum soft interrupt load percentage, then the PRM is decreased.
[0055] The configured maximum soft interrupt load percentage is not a desired
or
target percentage, but it is simply a threshold past which packet reception
throttling
must occur, and which the packet throttling system 300 does not want the
current
soft interrupt load percentage to exceed.
[0056] The PRM adjustments may not be simple increments and decrements. The
PRM calculator 352 may apply an adaptive and customized binary convergence
algorithm. The algorithm uses a search which is a modified binary search. A
standard binary search is a well known mathematical technique for searching
sets of
ordered data. The search starts at the midpoint M of the ordered set of N
values,
and, if the value at position M is greater then the target value, the search
proceeds to
position M/2. If the value at M is less than the target value, then the search
proceeds
to position ( M+N )/2. The search continues by continuing to halve the size of
the
steps, in the appropriate directions. A binary search may change directions
several
times as it converges upon the target value.
[0057] The modified binary search used by the adaptive and customized binary
convergence algorithm is as follows. The PRM starts as an absolute minimum. If
the current soft interrupt load percentage requires the PRM to be increased,
i.e., the
current load is greater than the maximum allowed load, then the PRM calculator
352
increases the PRM in steps which double in size with each recalculation, until
the
PRM has been increased too much: the previous soft interrupt load percentage
was
greater than allowed, but the current soft interrupt load percentage is less
than the
-17-
CA 02667163 2009-05-28
maximum allowed soft interrupt load percentage range. This occurrence, of
having
the soft interrupt load percentage jump from above to below (or below to
above) the
maximum range, is analogous to a binary search having jumped past the target
value
in an ordered list. In the spirit of a binary search, the PRM is then
decreased by half
of the size of the latest increase, in an attempt to adjust the soft interrupt
load so that
the soft interrupt load percentage increases to be within range of the
configured
maximum soft interrupt load percentage. The PRM is then increased or
decreased,
as required, in successively halved steps, in an attempt to converge the
current soft
interrupt load percentage upon the configured maximum soft interrupt load
percentage.
[0058] As an unrealistic but useful example, given a configured maximum soft
interrupt load percentage of 50, and a maximum soft interrupt load tolerance
of 10%,
which implies 40% -> 60% is an acceptable maximum:
Current Softirq Load PRM PRM Delta
100 10 0
100 20 +10 (absolute minimum stepsize)
100 40 +20 (doubled stepsize)
25 80 +40 (too far, go back (binary convergence))
70 60 -20 (too far, go back)
55 70 +10 (within range of max load)
[0059] Once the PRM has brought the current soft interrupt load percentage
within
range of the configured maximum soft interrupt load percentage, the PRM
stepsize is
reduced to the absolute minimum. This is done to ensure that the next
adjustment of
the PRM is very small, because even relatively constant traffic rates
experience
variations, and because even under a constant traffic load, the CPU's current
soft
interrupt load percentage varies slightly, because the CPU has so many other
responsibilities. It is therefore desirable for the next adjustments of the
PRM to be
small, because the current soft interrupt load percentage probably has altered
only to
a small degree. If the current soft interrupt load percentage does change
-18-
CA 02667163 2009-05-28
significantly after having been throttled into the maximum allowed range, then
the
binary convergence soon switches to doubling stepsizes in order to reach a
suitable
PRM, as further described below.
[0060] Convergence in this context means that the PRM's stepsizes are being
halved, and may change direction. A convergence, in this context, is initiated
when
an adjustment to the PRM results in the current soft interrupt load percentage
moving from above the allowed maximum to below the allowed maximum, or from
below the allowed maximum to above the allowed maximum. A convergence ends
when either (a) the current soft interrupt load percentage is brought within
range of
the maximum or (b) the convergence patience, as further described below, for
the
number of consecutive halved steps in the same direction is exceeded. When (b)
occurs, then the PRM stepsizes begin to double, until a new convergence is
initiated.
(b) enforces a temporal and mathematical limit on the lifespan of a
convergence.
This is beneficial because it is desirable for the PRM to reach an optimal
value as
quickly as possible, and outside of a convergence the PRM is modified at
greater
rates than it is within a convergence. (b) also enables the PRM adjustments to
accommodate fluctuations in the current soft interrupt load percentage: a
convergence works only if the current soft interrupt load percentage remains
relatively steady. If the current soft interrupt load percentage changes
greatly during
a convergence, then the convergence terminates due to (b), and the PRM is
'pursuing' an appropriate value in doubling stepsizes.
[0061 ]The PRM can be modified during a convergence, and outside of a
convergence. Within a convergence, the PRM is modified by successively halved
stepsizes, and possibly in different directions (up or down). Outside of a
convergence, the PRM is always modified by successively doubling stepsizes,
and in
the same direction, until a convergence is initiated.
[0062] The PRM calculator 352 does not allow the PRM to exceed absolute
extremes. This enforces a practical limit on the maximum degree of packet
throttling
-19-
CA 02667163 2009-05-28
which the packet throttling system 300 may apply. For example, it makes little
sense
to allow only one packet per second from a network entity, regardless of how
high
the server's CPU load is. The PRM's absolute maximum limit enforces a
realistic
limit on the lowest packet rates which may be enforced by the packet
throttling
system 300.
[0063] The PRM adjustment algorithm does not attempt to unnecessarily maintain
the CPU's current soft interrupt load percentage within range of the
configured soft
interrupt maximum load percentage. If the current soft interrupt load
percentage is
less than the configured maximum soft interrupt load percentage, and the PRM
is not
being adjusted within a convergence, then the PRM algorithm always decreases
the
PRM. This ensures that a mostly idle CPU does not enforce throttling on its
received
traffic.
[0064] With regard to the convergence patience, once the PRM has begun
attempting to converge upon a suitable value using the binary convergence
technique, the PRM is not continued to be blindly adjusted using continuously
halving
stepsizes, because the CPU's current soft interrupt load percentage is
constantly
changing (a moving target). The PRM adjustment algorithm is configured with a
convergence patience P, which ensures that, if after P halved steps in the
same
direction the current soft interrupt load has not been forced (by the altered
PRM)
either below or above the configured allowed maximum soft interrupt load
percentage range (remember that such an occurrence is analogous to a binary
search's jump past the target value), then the PRM adjustment algorithm begins
to
double its stepsizes, instead of halving them. Once the PRM has been altered
sufficiently so that the current soft interrupt load has been forced below or
above the
allowed maximum, then the PRM adjustment algorithm begins halving the PRM
stepsizes again in order to converge upon an acceptable PRM value.
[0065] Once a PRM has been calculated, it is used as a basis for further
calculations
which produce several periods which are applied to received packets. The base
-20-
CA 02667163 2009-05-28
applied period calculator 354 and class applied period calculator 356 carries
out the
recalculation of throttling periods (604). The base applied period calculator
354 and
class applied period calculator 356 consider the classes of IP addresses which
are
managed by the registration driver 230.
[0066] The base applied period calculator 354 uses an algebraic equation to
convert
the PRM into a base applied period, as further described below.
[0067] The class applied period calculator 356 uses this base applied period
to
calculate different applied periods for each of the IP address classes:
Regular,
Registered, Device, Router, and Foreign. Each class is associated with a
configurable period weighting. These weightings determine the ratios between
the
classes' applied periods. For example, if the Registered class has a weighting
of 2
and the Regular class has a weighting of 1, then the Registered class's
packets are
subject to a throttling period which is approximately half of the throttling
period that is
applied to the Regular class's packets. Thus, each member of the Registered
class
has its packets processed by the VBN server at about twice the rate as any
member
of the Regular class.
[0068] The class weightings enable the packet throttling system 300 to apply
different
degrees of throttling to different types of network entity. For example, the
packet
throttling system 300 may consider it beneficial to allow Registered users
less
restricted traffic flow than unregistered users, which are contained within
the Regular
class. The rationale behind the IP address classifications is now described
for each
class.
[0069] Regular (unregistered) entities need only access the VBN server's
registration
web pages and basic provisioning services, and therefore can function under
relatively high degrees of traffic throttling. Additionally, unregistered
network entities
often automatically transmit disproportionately large volumes of traffic to
the VBN
server, because the unregistered entities' various automatic networking client
applications are unable to contact their remote servers, and continually re-
attempt to
-21-
CA 02667163 2009-05-28
contact those servers. Such large amounts of unregistered traffic have
traditionally
represented a scalability problem for VBN servers on large networks, because
the
VBN server need to process all unregistered traffic at both a kernel and
application
level, instead of simply routing the traffic to the WAN. The packet throttling
system
300 provides the VBN server with a highly effective last line of defense
against such
unregistered traffic. The Regular class weighting is always 1, and is usually
lower
than that of all other classes, because unregistered entities do not need WAN
access, and because unregistered traffic is frequently a problem for the VBN
server.
[0070] Registered entities need to access the WAN through the VBN server in a
timely manner. The Registered class therefore usually receives a relatively
high
weighting.
[0071] Device entities are meant to be unregistered entities which may relay
some
types of traffic on behalf of other entities. The Device class weighting can
be made
greater than that of the Regular class weighting, in order to accommodate the
greater volumes of traffic which may be expected from each member of the
Device
class.
[0072] Router entities are meant to be unregistered entities which relay all
traffic on
behalf of the entities behind them. The Router class weighting can therefore
be
made large enough to allow for the disproportionate amount of traffic that
each router
may transmit to the VBN server 200.
[0073] Foreign entities are all entities on the LAN 260 and WAN 280 which are
not
managed by the registration driver 230. All foreign entities are considered by
the
packet throttling system 300 to be a single entity: the Foreign applied period
is
applied to all foreign IP addresses, not to each foreign IP address.
[0074] The soft interrupt handler terminator 360 applies throttling to
received packets
based on the classification of the received packets using the IP addresses. A
packet's source and/or destination IP addresses are examined in order to
determine
-22-
CA 02667163 2009-05-28
to which of the five VBN classes the packet belongs. The packet throttling
system
300 is aware of the properties of each of the IP addresses that are managed by
the
registration driver 230, because the registration driver 230 informs the
packet
throttling system 300 of such properties. The packet's source IP address takes
precedence: if the source IP address is known to be that of a Registered,
Regular,
Device, or Router entity, then that packet is considered to belong to the
corresponding class. Otherwise, if the destination IP address is known to be
that of
a Registered, Regular, Device, or Router entity, then that packet is
considered to
belong to the corresponding class. Otherwise, the packet is considered to
belong to
the Foreign class.
[0075] An example of base period calculations is now described. Because of the
information received from the registration driver 230 as described above, the
packet
throttling system 300 knows how many IP addresses are managed by the
registration
driver 230. The packet throttling system 300 also considers all foreign IP
addresses,
which are not managed by the registration driver 230, to be represented
collectively,
for throttling purposes, as a single additional IP address class Foreign. The
base
applied period calculator 354 begins with the equation:
( ( num IPs managed by RD ) + 1 ) * PRM = C
The +1 represents all foreign IP addresses, collectively
[0076] The total number of IP addresses which are managed by the registration
driver 230 are then partitioned into VBN classes:
[ ( num regular IPs ) + ( num registered IPs ) + ( num device
IPs ) + ( num router IPs ) + 1 ] * PRM = C
[0077] The base applied period calculator 354 then replaces the PRM with an
unknown base period P, while maintaining the remainder of the equation. This
ensures that the base period P is proportional to the PRM, and thus the PRM is
the
primary influence on the calculated periods.
-23-
CA 02667163 2009-05-28
num regular IPs ) + ( num registered IPs ) + ( num device
IPs ) + ( num router IPs ) + 1 ] * P = C
[0078] The base applied period calculator 354 then introduces the relative
class
weightings into the equation:
[ num_regular_ips * ( P / 1 ) ] +
[ num router_ips * ( P / router_weight ) ] +
[ num device _ips * ( P/ device_weight ) ] +
[ num_ registered ips * ( P / registered-weight ) ] +
[ 1 * ( P / foreign weight ) ] = C
[0079] The base applied period calculator 354 then solves for the base period
P:
P = C /
[ num_regular_ips +
( num_router_ips / router weight ) +
( num device_ips / device weight ) +
( num registered ips / registered-weight ) +
( 1 /foreign weight ]
[0080] The class applied period calculator 356 then calculates the applied
periods for
each VBN class:
regular applied period = P / 1
registered applied period = P / (registered weight)
device applied period = P / (device weight)
router applied period = P / (router weight)
foreign applied period = P / (foreign weight)
[0081 ] A smaller period between permitted packets allows a greater rate of
permitted
packets, so a larger class weighting creates a greater class maximum packet
rate.
These applied periods are all proportional to the PRM, and thus preserve the
current
soft interrupt load percentage management effect of the PRM. The applied
periods
are throttling periods for different IP address classes for different CPUs.
The
-24-
CA 02667163 2009-05-28
throttling periods are maintained in units of nanoseconds, in order to
facilitate the
accurate enforcement of short throttling periods.
[0082] The soft interrupt handler terminator 360 applies the throttling
periods within
the packet reception soft interrupt handler, as further described in detail
below. The
soft interrupt handler terminator 360 determines which IP address throttling
record in
the throttling data store 332, including a throttling period for the iP
address class, is
associated with a received packet, checks the timestamp of the last permitted
received packet which is stored in that record, and drops the packet and
terminates
the soft interrupt handler if the throttling period has not elapsed since that
timestamp.
If at least the throttling period has elapsed since the timestamp, then the
packet is
permitted to be processed by the remainder of the soft interrupt handler, and
the
throttling record's timestamp is updated with the current time.
[0083] The scheme of the packet reception soft interrupt throttling unit 400
is
protocol-independent and application independent. It considers only packet
source
and/or destination IP addresses, and it does not consider packet ports or
packet
payloads. The packet losses are therefore distributed without prejudice across
all IP
protocols and applications. This throttling fairness is now described further.
[0084] The throttling operates upon a per-IP address basis: each IP address
that is
managed by the VBN server 200 is provided with its own packet reception
frequency
counter. All other IP addresses are provided with a single collective packet
reception
frequency counter.
[0085] A packet which is sent from a managed IP address A is considered, for
throttling purposes, to be equivalent to a packet which is sent to managed IP
address
A, provided that the packet which is sent to managed IP address A is not sent
from
another managed IP address B. In other words, if a packet is sent from one
managed IP address to another managed IP address, then the source IP address
of
that packet is of interest to the throttling system 300. If a packet is sent
from a
managed IP address to a Foreign IP address, then the source IP address of that
-25-
CA 02667163 2009-05-28
packet is of interest to the throttling system 300. If a packet is sent from a
Foreign IP
address to a managed IP address, then the destination IP address of that
packet is
of interest to the throttling system 300. If a packet is sent from a Foreign
IP address
to another Foreign IP address, then that packet is considered to be a member
of the
special Foreign class, all members of which are considered by the throttling
system
300 to be a single logical entity. Thus, if an entity behind the VBN server
200 is the
source and/or the recipient of a high rate of packets, the packet throttling
system 300
mitigates the CPU packet reception expense resulting from both the incoming
and
outgoing streams of packets.
[0086] Not all members of each VBN class are necessarily sending traffic to
the VBN
server 200 at the same time, or at the same rate. It may at first glance seem
unfair
to apply the same period to all members of a class, when some members of that
class are transmitting far more traffic than other members of that class. It
may also
seem unfair to calculate all classes' periods using a single base period, when
some
classes may be sending far more traffic to the VBN server 200 than other
classes.
[0087] As described above, the period which is applied to a class is actually
applied
independently to each member of that class, not cumulatively to all members of
that
class. For example, given a class period of 100ns, for each member of that
class the
VBN server 200 fully processes one received packet every 100ns. If there are
100
members in the class, then the total packet processing rate for that class
could be as
great as 100 packets every 100ns.
[0088] The goal of the packet throttling system 300 is only to ensure that the
VBN
server 200's CPUs remain able to process traffic from each managed IP address
(and all foreign addresses, collectively) even when the cumulative frequency
of
packet reception is sufficiently large that the server's CPUs would normally
be
backlogged with packet reception soft interrupt handler tasks.
[0089] By reducing the maximum received packet processing rate for each
managed
IP address (and all foreign addresses, collectively) to a rate (subject to
class
-26-
CA 02667163 2009-05-28
weightings) which ensures that the currently received rate of received packet
processing does not force the CPUs' soft interrupt load percentages to remain
above
a configured threshold, the packet throttling system 300 can ensure that the
CPUs
remain available to perform other important tasks, and also handle sudden
increases
in packet reception rates.
[0090] If only a small number of the managed IP addresses are sending packets
to
the server, then the packet throttling system 300 calculates maximum packet
rates
for all IP addresses based only upon the activity of those few transmitting IP
addresses. This provides a suitable overall degree of throttling for the
current
situation, and also enforces an upper bound upon the traffic rates of the
nontransmitting IP addresses during the next throttling examination interval.
Should
any of the hitherto nontransmitting IP addresses suddenly begin transmitting
at large
rates during the next throttling examination interval, then the effect of
those new
transmissions on the CPU loads is limited by the throttling periods which are
in effect
during that throttling examination interval. The recalculation of the
throttling periods
at the end of the next throttling examination interval, which is usually only
several
seconds away, then reflects the suddenly increased total frequency of packet
reception. The effect on CPU loads would be a sudden and brief spike, which
would
soon be reduced by the next few recalculations of the throttling periods.
[0091 ] It can be seen that the packet throttling system 300 applies ideally
when a
large proportion of the IP addresses are sending similar rates of packets.
However,
the packet throttling system 300 is also highly effective at managing uneven
distributions, and also rapidly fluctuating distributions, of traffic rates,
without
imposing unnecessary degrees of throttling, because the throttling periods or
packet
reception rates are regularly and frequently being recalculated. The packet
throttling
system 300 allows sudden increases in received traffic rates to create sudden
and
brief increases in CPU loads, rather than imposing stricter throttling rules
which
would prevent such CPU load spikes by enforcing harsher degrees of throttling
which
would be excessive in most situations. The packet throttling system 300 is
thus very
-27-
CA 02667163 2009-05-28
well-suited to the diverse and dynamic packet reception throttling needs of a
modern
VBN server 200.
[0092] The packet throttling system 300 leaves it up to the higher-level
traffic control
tools such as QoS and packet filtering to enforce more sophisticated traffic
control
polices upon individual users and groups of users.
[0093] There are so many factors in addition to the packet reception rate
which affect
a CPU soft interrupt load percentage that the above period calculations
carried out
by the packet throttling system 300 are educated approximations of the
required
throttling adjustments. The regular period recalculations by the packet
throttling
system 300 serve to accommodate changing CPU conditions, and thus provide a
continual adjustment of the approximations.
[0094] As shown in Figure 4, in addition to the packet reception soft
interrupt
throttling unit 400, the packet throttling system 300 may also have a packet
reception
hard interrupt throttling unit 500 comprising the timekeeper soft interrupt
examiner
370 and the hard interrupt line disabler 380 to throttle packet reception hard
interrupts. When a packet arrives at one of the NICs 220 of the VBN server
200, the
NIC 220 generates a packet reception interrupt to one of the CPUs 210 on an
interrupt line. The arrival of the packet reception interrupt on the interrupt
line
initiates a packet reception hard interrupt handler in the receiving CPU 210.
Soft
interrupts are generated by such hard interrupts. The packet reception hard
interrupt
throttling unit 500 determines if packet reception hard interrupts need to be
throttled,
and enforces throttling for hard interrupt lines of the NICs 220 when it is
determined
necessary.
[0095] Figure 8 shows an embodiment of the packet reception hard interrupt
throttling unit 500. In this embodiment, the packet reception hard interrupt
throttling
unit 500 has a timekeeper soft interrupt examiner 370 and a hard interrupt
line
disabler 380. The hard interrupt line disabler 380 may have a hard interrupt
throttling
degree handler 382.
-28-
CA 02667163 2009-05-28
[0096] The timekeeper soft interrupt examiner 370 monitors timekeeper soft
interrupts. In this embodiment, the kernel possesses a timekeeper soft
interrupt
handler. The kernel executes this timekeeper soft interrupt hundreds of times
per
second on each CPU in order to facilitate operating system level
synchronization and
scheduling activities, and CPU context switches from one task to another. The
timekeeper soft interrupt serves as an operating system level clock tick, but
is not the
same as a hardware clock tick. The timekeeper soft interrupt does not depend
upon
the network card hard interrupts soft interrupts. The timekeeper soft
interrupt
examiner 370 may be an interface to add functionality to this kernel's
timekeeper soft
interrupt handier to permit the hard interrupt line throttling unit 500 to re-
enable any
hard interrupt lines which the hard interrupt line disabler 380 may have
disabled
since the previous execution of the timekeeper soft interrupt handler. This
ensures
that no hard interrupt line is disabled for a duration of more than one
operating
system clock tick.
[0097] The timekeeper soft interrupt examiner 370 also increments a counter
within
the appropriate CPU record of the packet throttling system 300. This results
in a
count of the number of timekeeper soft interrupt executions which have
occurred on
each CPU during a throttling examination interval.
[0098] In order to determine if hard interrupts need to be throttled, the
timekeeper
soft interrupt examiner 370 examines, for each CPU, the timekeeper soft
interrupt
counters in each of that CPU's data records maintained in the throttling data
store
332.
[0099] Since a known and predetermined number of timekeeper soft interrupts
should occur within any interval, under normal conditions, it is possible for
the
timekeeper soft interrupt examiner 370 to determine if the CPU has missed any
timekeeper interrupts in any of the recent intervals. Timekeeper interrupts
can be
missed if the CPU is exceptionally busy, such as when the CPU is overloaded
with
packet reception soft interrupts. Thus, missed timekeeper interrupts are a
sign that
-29-
CA 02667163 2009-05-28
the CPU is detrimentally, rather than inconveniently, overloaded. A side-
effect of
missed timekeeper soft interrupts is the kernel's failure to accurately record
CPU
usage statistics because those statistics are collected during the timekeeper
soft
interrupts. The CPU usage statistics are referenced by the timekeeper soft
interrupt
examiner 370 in determining soft interrupt load percentages. Therefore, when
the
CPU cannot execute all of its timekeeper interrupts, the throttling period
calculator
350 cannot accurately calculate throttling periods.
[00100] The packet throttling system 300 thus has good reason to be able to
throttle hard NIC interrupts. The timekeeper soft interrupt examiner 370
considers
hard NIC interrupt throttling to be necessary if, for any of the CPUs, that
CPU missed
timekeeper interrupts in each of the recorded throttling examination intervals
which
are stored in the CPU data record history in the throttling data store 332.
[00101] The hard interrupt throttling by the packet reception hard interrupt
throttling unit 500 is performed in conjunction with the soft interrupt
throttling by the
packet reception soft interrupt throttling unit 400, as a supplement to the
soft
interrupt throttling. It is not an alternative to the soft interrupt
throttling. The hard
interrupt throttling may never be applied, if circumstances do not require it.
[00102] The packet reception hard interrupt throttling unit 500 throttles NIC
hard
interrupts by temporarily disabling the NIC interrupt lines by the hard
interrupt line
disabler 380. It is not desirable to disable NIC interrupt lines for lengthy
periods of
time, because NIC interrupt lines are used for both packet transmission and
reception, and because disabling NIC interrupt lines drops all packets which
would
have been received or transmitted on that interrupt line during the disabled
period,
not only those packets which would have been selectively dropped by the soft
interrupt throttling unit 400.
[00103] The hard interrupt line disabler 380 implements a proprietary hard
interrupt disabling scheme which disables an interrupt line for no more than
one OS
clock tick at a time, but may disable the interrupt line with various
frequencies. Thus,
-30-
CA 02667163 2009-05-28
the length of each hard interrupt disabling is always brief, but a hard
interrupt may be
disabled more or less often, as required. Since lengthy disablings of hard
interrupts
are easily noticed by protocols and applications, this scheme provides an
optimal
balance between packet denial and server responsiveness.
[00104] The hard interrupt line disabler 380 may utilize facilities of the
kernel's
hard interrupt management code that provides facilities to enable and disable
specific interrupt lines. The hard interrupt line disabler 380 utilizes these
facilities to
enable and disable NIC interrupt lines of the server 200. The hard interrupt
line
disabler 380 disables interrupt lines, when necessary, from within the packet
reception soft interrupt handler. During the execution of the next timekeeper
soft
interrupt, the hard interrupt line disabler 380, from within the next
timekeeper soft
interrupt handler, enables any and all of the interrupt lines which it has
disabled.
Thus, a hard interrupt is disabled for a duration of no more than one
operating
system clock tick, unless the next clock tick is delayed because of CPU
overloading,
in which case the extended disabling of the NIC hard interrupt line is
probably
beneficial.
[00105] The hard interrupt line disabler 380 may have a hard interrupt
throttling
degree handler 382 to change throttling degrees of hard interrupt throttling.
The
degree of hard interrupt throttling is defined as the frequency of hard
interrupt
disablings. Each time the degree of hard interrupt throttling is increased,
the NIC
interrupt lines are disabled more frequently. Each time the degree of hard
interrupt
throttling is decreased, the NIC interrupt lines are disabled less frequently.
Whenever the timekeeper soft interrupt examiner 370 calculates and determines
that
hard interrupt throttling is required, the hard interrupt throttling degree
handler 382
increases the current degree of hard interrupt throttling, which results in a
cumulative
or telescoping throttling. Whenever the timekeeper soft interrupt examiner 370
calculates that hard interrupt throttling is not required, the hard interrupt
throttling
degree handler 382 decreases the current degree of hard interrupt throttling.
The
-31-
CA 02667163 2009-05-28
current degree of hard interrupt throttling is stored within the hard
interrupt
parameters data structures in the throttling data store 332.
[00106] The VBN server 200 typically contains at least two NICs: one for the
LAN 260 and the other for the WAN 280. Usually, these NICs utilize different
hard
interrupt lines, although it is possible for them to share a single hard
interrupt line.
[00107] The hard interrupt line disabler 380 may have a throttling proportion
calculator 384 to calculate throttling proportions among NICs. Over any given
throttling examination interval, one of the NICs most likely receives more
traffic than
the other or others. In practice, when the VBN server 200 is experiencing high
packet reception rates, one of the NICs is receiving most of the traffic.
Therefore,
when the packet reception hard interrupt throttling unit 500 imposes hard
interrupt
throttling, the throttling proportion calculator 384 calculates throttling
proportions so
that the throttling is applied in proportions similar to the proportions of
hard interrupt
activity generated by each of the NICs.
[00108] An example is described for a server having two NICs. Once the
timekeeper soft interrupt examiner 370 determines that hard interrupt
throttling, or a
greater degree of hard interrupt throttling, is required by identifying a CPU
which
repeatedly missed timekeeper interrupts, the throttling proportion calculator
384
examines the latest throttling data record for the offending CPU, and
calculates the
two NICs' recent relative proportions of hard interrupt activity, e.g. the LAN
260
having 800 interrupts in the past interval, the WAN 280 having 200 interrupts
in the
past interval, gives us an 8:2 ratio. The throttling proportion calculator 384
increases
the degree of hard interrupt throttling in the same proportions so that, e.g.,
the LAN
NIC will have its hard interrupt throttling increased by 8 additional
disablings per
second, and the WAN NIC will have its hard interrupt throttling increased by 2
additional disablings per second.
[00109] A configuration option, hard interrupt throttling granularity, may be
applied to the throttling proportions, in order to provide faster or smaller
increases in
-32-
CA 02667163 2009-05-28
degrees of hard interrupt throttling. For example, if the hard interrupt
throttling
granularity is 2, then the LAN NIC's hard interrupt throttling is increased by
2 * 8
disablings per second, and the WAN NIC's hard interrupt throttling is
increased by 2
* 2 disablings per second, up to an absolute maximum number of disablings per
second.
[00110] When the timekeeper soft interrupt examiner 370 determines that
further hard interrupt throttling is not required, the hard interrupt
throttling degree
handler 382 decreases the current degree of hard interrupt throttling, but not
in
proportional steps. Instead, a configurable hard interrupt throttling degree
decrement
is applied, subjected to the hard interrupt throttling granularity. The NICs'
hard
interrupt throttlings are thus decreased at the same rate. For example, if the
hard
interrupt throttling degree decrement is 5, the hard interrupt throttling
granularity is 2,
then each time the timekeeper soft interrupt examiner 370 determines that
further
hard interrupt throttling is not required, each NIC's hard interrupt line is
disabled 2 * 5
fewer times per second.
[00111] As described above, the data manager 330 manages the data
structures in the throttling data store 332 that the packet throttling system
300
maintains. Of primary importance are the CPU data records, and the user
records.
[00112] The CPU data records store, for each CPU, soft interrupt load
statistics
and packet reception statistics. The throttling mechanism maintains several
recent
sets of CPU data records, so that it can compare recent CPU data sets with the
current CPU data sets in order to determine usage trends.
[00113] The user records store, for each IP address which is managed by the
VBN server 200, and, in one special record for all other IP addresses, the
allowed
packet reception timestamps, so that the throttling mechanism can apply the
allowed
packet reception rates to each IP address.
-33-
CA 02667163 2009-05-28
[00114] The throttling data store 332 also maintains a hard interrupt
throttling
parameter array, and a hard interrupt throttling state array, for use by the
hard
interrupt throttling component of the throttling mechanism. These arrays
contain one
element for each NIC on the server.
[00115] The kernel provides a section of code which serves as the first step
in
the processing of a received packet during a soft interrupt, regardless of
which NIC
the packet arrived on, and regardless of the characteristics of the packet
itself. The
soft interrupt hander interface 320 may provide an interface to modify this
initial step
in the kernel's packet reception soft interrupt handler to communicate with
the packet
throttling system 300 before performing any of its regular work. The high-
level
throttling logic is applied within this soft interrupt handler.
[00116] Figure 8 shows an example of the pseudo code of the packet reception
soft interrupt throttling unit 400. First, the packet reception soft interrupt
throttling
unit 400 checks to see if throttling can and should be performed. It then
checks with
the throttling mechanism to see if a throttling statistic refresh / period
recalculation is
required, and instructs the throttling mechanism to refresh if necessary.
Placing the
refresh check and initiation within the soft interrupt handler instead of only
within an
intermittently executed kernel task ensures that even under very high packet
reception loads (when kernel tasks may not be executed in a timely manner),
the
throttling statistics are refreshed when required.
[00117] The packet reception soft interrupt throttling unit 400 then
determines if
this packet needs to be dropped, by examining its source and/or destination IP
address, according to the periods which have been calculated by the throttling
mechanism.
[00118] Finally, the packet reception soft interrupt throttling unit 400
allows the
throttling mechanism to perform its hard network interrupt throttling, if the
throttling
mechanism considers it necessary.
-34-
CA 02667163 2009-05-28
[00119] The configuration manager 390 manages parameters that configure the
packet throttling system 300. The parameters include the following:
- enabled: This parameter is a toggle which activates or deactivates the
packet
throttling system 300.
- refresh throttling examination interval: This parameter determines the
duration of
the throttling examination intervals. Statistics are collected, periods are
calculated at
the beginning of each throttling examination interval and are applied until
the end of
that throttling examination interval.
- Router weight: This parameter determines the relative weight which the soft
interrupt period calculations apply to the Router class of VBN clients.
- Device weight: This parameter determines the relative weight which the soft
interrupt period calculations apply to the Device class of VBN clients.
- Registered Weight: This parameter determines the relative weight which the
soft
interrupt period calculations apply to the Registered class of VBN clients.
- Foreign Weight: This parameter determines the relative weight which the soft
interrupt period calculations apply to the all IP addresses which are not
managed by
the registration driver 230, collectively.
- Soft interrupt load tolerance: This parameter determines a percentage of
leeway
which the packet throttling system 300 applies to a CPU's maximum allowable
soft
interrupt load percentage. Given maximum M, the soft interrupt load tolerance
T
defines a range from (M - T)% to (M + T)%.
- convergence patience: This parameter defines the number of consecutive
halving
steps in the same direction that the binary convergence algorithm will allow
before
beginning to double the stepsize.
- hard interrupt granularity: This parameter defines a multiplier which is
applied to
the hard interrupt throttling degree increases and decreases, in order to
amplify the
changes made to hard interrupt throttling degrees.
- hard interrupt decrement: This parameter defines the number of hard
interrupt
disablings per second by which hard interrupt throttling degrees are
decremented.
-35-
CA 02667163 2009-05-28
- CPU load reassignment threshold: This parameter defines how frequently, in
number of throttling examination intervals, that the maximum soft interrupt
load
percentages should be reassigned to appropriate CPUs, as described below.
- maximum soft interrupt load percentages: One maximum soft interrupt load
percentage is defined for each CPU. On systems with multiple CPUs, it is not
always
possible to predict which CPU(s) will receive the brunt of the network soft
interrupt
processing. The packet throttling system 300 provides an automatic shuffling
of the
configured maximum soft interrupt load percentage parameters at the start of
some
throttling examination intervals: the packet throttling system 300 will
automatically
reassign the highest configured percentage to the CPU which is currently
experiencing the highest soft interrupt load, and the remaining configured
maximum
percentages will be applied to the other CPUs in same manner. For example, if
the
VBN server possesses 4 CPUs, then the maximum soft interrupt load percentages
may be configured as 75 75 50 20. At the start of Nth throttling examination
interval,
where N is the configured CPU load reassignment threshold, the throttling
mechanism will automatically ensure that the CPU which possesses the highest
current soft interrupt load percentage will be assigned the 75% maximum soft
interrupt load percentage, and so on. This scheme ensures that the least
amount of
traffic throttling will be performed on the server as a whole.
[00120] Figure 9 shows an example of the operation of the packet throttling
system 300. In the packet throttling system 300, the registration driver
interface 310
receives IP address information from the registration driver 210 (700). The
CPU soft
interrupt load calculator 340 determines a current CPU soft interrupt load for
each
CPU (750), and the throttling period calculator 350 calculates a throttling
period for
each IP address class for each CPU based on the current CPU soft interrupt
load
and the IP address information (752). Also, the hard interrupt throttling unit
500
calculates hard interrupt throttling parameters (756). The current CPU
interrupt
loads and throttling periods are recalculated intermittently (754).
-36-
CA 02667163 2009-05-28
[00121] When a packet is received by a NIC 220 of the VBN server 200, the
NIC 220 sends a packet reception interrupt to one of the CPUs (760). This
initiates a
packet reception hard interrupt handler which initiates a packet reception
soft
interrupt handler 212 in one of the CPUs (762). The initiation of the soft
packet
reception interrupt handler 212 initiates the recalculation of the current CPU
soft
interrupt loads and throttling periods (764) if the recalculations were not
carried out in
a predetermined period..
[00122] When the packet reception soft interrupt handler 212 is initiated,
before
the packet reception soft interrupt is further processed, the soft interrupt
handler
terminator 360 determines the throttling period of the CPU for the received
packet
based on the IP address of the received packet (770), and determines if the
throttling
period has or has not elapsed since the CPU handled a last permitted received
packet (772) for this packet's source or destination IP address. If the
throttling period
has elapsed, the soft interrupt handler terminator 130 allows the soft
interrupt
handler 212 to continue processing the packet reception interrupt and the
received
packet to be processed further by the server 200 (774). If the throttling
period has
not elapsed (772), the interrupt handler terminator 360 drops the received
packet
and terminates the packet reception soft interrupt handler 212 (776).
[00123] In commonplace server architectures, there is only one set of hard
interrupt lines, regardless of the number of CPUs. For example, if the server
possesses two NICs and eight CPUs, then there are only, at most, two NIC hard
interrupt lines for the throttling system 300 to consider. The throttling
system 300
maintains separate collections of throttling data for each CPU. For each CPU,
it
maintains multiple sets of this data, representing a short history of
throttling data.
The multiple sets of the data for M CPUs may be expressed as follows:
CPUO: Data Set 1 - Data Set 2 - Data Set 3 - ... Data Set N
CPU1: Data Set 1 - Data Set 2 - Data Set 3 - ... Data Set N
CPUM: Data Set 1 - Data Set 2 - Data Set 3 - ... Data Set N
-37-
CA 02667163 2009-05-28
[00124] The packet reception hard interrupt throttling unit 500 collects each
set
of this data at the end of a throttling interval (780). If the timekeeper soft
interrupt
examiner 370 detects missing timekeeper soft interrupts for any CPU in each of
that
CPU's recorded sets of throttling data (782), then the hard interrupt line
disabler 380
performs hard interrupt throttling (784). This hard interrupt throttling is
applied to all
of the NIC interrupt lines (e.g., the two hard interrupt lines, in this
example), and has
the effect of disabling all NIC hard interrupts for all of the CPUs within the
server 200.
The hard interrupt line disabler 380 enables the disabled hard interrupt lines
during
the execution of the next timekeeper soft interrupt (786).
[00125] As described above, the packet throttling system 300 can apply
adaptive adjustment of received packet permission periods or throttling
periods, at a
soft interrupt level, to VBN classes of IP addresses. The packet throttling
system
300 can dynamically target a configurable soft interrupt load percentage.
[00126] The present invention may be embodied as a system, method,
computer program product, or a computer readable medium having computer
readable instructions for execution in a computer system.
[00127] The packet throttling system may be implemented by any hardware,
software or a combination of hardware and software having the above described
functions. The software code, instructions and/or statements, either in its
entirety or
a part thereof, may be stored in a computer readable memory. Further, a
computer
data signal representing the software code, instructions and/or statements may
be
embedded in a carrier wave may be transmitted via a communication network.
Such
a computer readable memory and a computer data signal and/or its carrier are
also
within the scope of the present invention, as well as the hardware, software
and the
combination thereof.
[00128] While particular embodiments of the present invention have been
shown and described, changes and modifications may be made to such
embodiments without departing from the scope of the invention. For example,
the
-38-
CA 02667163 2009-05-28
elements of the packet throttling system are described separately referring to
block
diagrams, however, two or more elements may be provided as a single element,
or
one or more elements may be shared with other components in one or more
computer systems. Also, other embodiments of the invention may have fewer or
more elements than those shown in the block diagrams. Similarly, the methods
or
operations of the packet throttling are described referring to flowcharts, in
which one
or more boxes may be combined or spread, omitted or added in different
embodiments.
-39-
