Detecting network intrusions via sampling: a game theoretic approach
Detecting Network Intrusions via Sampling : A Game Theoretic Approach {muralik, lakshman}@bell-labs.com
a more detailed examination of the packet. To prevent packet
In this paper, we consider the problem of detecting an in-
mis-ordering or reduction of link throughput this examination
truding packet in a communication network. Detection is ac-
has to be done preferably at line rates. Packet sampling has
complished by sampling a portion of the packets transiting se-
been previously proposed for a variety of networking purposes. lected network links (or router interfaces). Since sampling en-
For instance, the SRED scheme in [6] uses packet sampling to
tails incurring network costs for real-time packet sampling and
estimate the number of active TCP flows in order to stabilize
packet examination hardware, we would like to develop a net-
network buffer occupancy for TCP traffic. Only packet headers
work packet sampling strategy to effectively detect network in-
need be examined for this scheme. The scheme proposed in [7],
trusions while not exceeding a given total sampling budget. We
also uses packet sampling and it is used for fair link-bandwidth
consider this problem in a game theoretic framework, where the
allocation. Sampling has also been proposed to infer network
intruder picks paths (or the network ingress point if only short-
traffic and routing characteristics [3]. Whereas, these applica-
est path routing is possible) to minimize chances of detection
tions require only sampling based on packet header compar-
and where the network operator chooses a sampling strategy to
isons, intrusion detection may entail a more thorough exami-
maximize the chances of detection. We formulate the game the-
nation of sampled packets. Also, unlike some of the sampling
oretic problem, and develop sampling schemes that are optimal
applications mentioned above, sampling for intrusion detection
requires near line-speed packet examination since copying sam-pled packets or packet-headers for off-line analysis is not suffi-cient to prevent intruding packets from getting through. Hence,
in the design of an intrusion detection scheme it is imperative
In this paper, we consider the problem of detecting intrusions
in a communication network. There is growing literature on
We study this intrusion detection via sampling problem in
providing security in communication networks. Two key areas
a game theoretic setting. Game theory has been used exten-
of interest in security are intrusion detection and intrusion pre-
sively to model different networking problems. This work in-
vention. In this paper, we deal with the problem of intrusion
cludes the work of Shenker for modeling service disciplines
detection. Intrusion in networks takes many forms including
[10], Akella et. al. for TCP performance [2], and Korilis,
denial of service attacks, viruses introduced into the networks,
Lazar and Orda [5] for modeling routing problems. To the
etc. Typically, in an intrusion problem, the intruder attempts to
best of our knowledge, this is the first attempt to model intru-
gain access to a particular file server or website in the network.
sion detection via sampling in communication networks using
In this paper, we consider a stylized intrusion problem. In this
a game-theoretic framework. This work is closely related to
problem, the intruder attempts to send a malicious packet to a
drug interdiction models. In particular the work of Washburn
given node in the network. The network attempts to detect this
and Wood [11] who considered drug interdiction in a game the-
intrusion. The detection mechanism is packet sampling and ex-
oretic framework. This work differs from the drug interdic-
tion models in two ways. First, in the drug interdiction models
The idea in sampling is that some portion of packets travers-
the objective is to deploy agents which is a discrete allocation
ing designated links (or router interfaces) are sampled and ex-
problem. In our case, the detection is by means of sampling.
amined in detail to determine whether the packet is an intruder
Therefore the game theoretic results are much more natural
packet. This packet examination may be simple (limited to spe-
than the discrete allocation models. Secondly, in our case, the
cific packet header fields as in packet filtering) or may involve
game theoretic problem naturally leads to a routing problem (to
maximize the service provider’s chances of detecting intruding
packets) which is absent in the drug interdiction problem. Thesolution to the game theoretic formulation is a maximum flowproblem and the routing problem can be formulated as a multi-commodity flow problem. We also consider various extensionsand variants to the basic models.
The problem set-up is outlined in three steps. First, we de-
scribe the network, then we define the adversaries in the game-theoretic framework, and finally we describe the objective of
the game that is played between the adversaries.
and hence detect the malicious packet. Sampling the packets
We consider a network G = (N, E) where N is the set of
flowing on a link involves setting up the appropriate sampling
nodes and E is the set of unidirectional links in the network.
filters and examining the packets. These can be fairly expen-
We assume that there are n nodes and m links in the network.
sive operations to perform in real time. Therefore, we assume
We assume that the capacity of link e ∈ E is denoted by c
that the service provider has a sampling bound of B packets
the amount of traffic flowing on link e is denoted by f
per second over the entire network. This sampling effort can be
two nodes u and v in the network, let Pv
distributed arbitrarily over the links in the network. One way
paths from u to v in G. Given an m-vector w, we use M
of implementing the sampling scheme is for each link to pick
to denote the maximum flow that can be sent from node u to
some fraction of the packets flowing through it and send it to a
node v using w as the link capacities. We use the parameter w
central intrusion detection node in the network which examines
the packet in more detail. The sampling bound can be viewed
uv () to indicate that dependence of
the maximum flow on the link capacities. Corresponding to this
as the maximum rate at which the intrusion detection node can
maximum flow between nodes u and v, there is a minimum cut
process packets in real time. If a link e that has a traffic of fe
comprising of a set of links in the network. This set of links in
flowing on it, is sampled at rate se then the probability of detect-
this minimum cut will be represented by Cv(
ing a malicious packet on this link is given by p
mulate the game theoretic problems in terms of p
that both the players have complete information about the topol-
The network intrusion detection game is played on the net-
ogy of the network and all the link flows in the network. The
work between two players: the Service Provider and the In-
service provider can have access to this information either from
truder. The objective of the intruder is to inject a malicious
link-state routing protocols with traffic engineering extensions
packet from some attack node a ∈ N with the intention of at-
that distribute flow information throughout a network area or
tacking a target node t ∈ N. We assume that an intrusion is
by explicit link polling from management systems. We assume
successful when the malicious packet reaches the desired tar-
that the adversary injecting intruding packets has this informa-
get t node without detection. In order to detect and prevent the
tion available as well since this makes the service provider’s
intrusion, the service provider is allowed to sample packets in
detection problem more difficult. Similarly, we also assume
the network. We assume that sampling takes place on the links
that the intruder is capable of picking paths in the network so
in the network. It is easy to modify the model to consider the
as to make the detection problem for the service provider more
case, where the sampling is done at the nodes in the network. If
difficult. However, in Section V-A, we also consider the case
during the course of sampling, the service provider samples the
where only shortest path routing is allowed in the network.
malicious packet then the intrusion is assumed to be detected
1) Strategies for the Two Players: In the case of the intruder,
and thwarted. The game is pictorially illustrated in Figure 1.
a pure strategy would be to pick a path from P ∈ Pta for the ma-licious packet to traverse from s to t. The intruder, in general,
C. The Objective and the Constraints of the Game
can use a mixed strategy. In the case of a mixed strategy, the in-
If there is no bound on the amount of sampling that can be
truder has a probability distribution q over the set of paths in Pta
done by the service provider, then the service provider can po-
tentially inspect every packet that flows through the network
represent the set of feasible probability allocations over the set
of paths between a and t. The intruder then picks path P ∈ Pta
detected as it goes from a to t. For a given path P ∈ Pta, the
with probability q(P ). The strategy for the service provider is
expected number of times that a packet is detected is given by
to determine a set of links on which sampling has to be done.
The probability that this path P is picked by the
The strategy for the service provider is to choose the sampling
intruder is given by q(P ). Therefore the expected number of
rate se on link e such that
times a packet is detected as it goes from the source to the des-
packet traverses link e with a sampling rate of se on a link with
tination for a fixed strategy from both adversaries is given by
flow fe results in the malicious packet being detected with prob-ability pe = se/fe. Let U = {p :
the set of detection probability vectors p that satisfy the sam-
pling budget constraint. (Note that p is an m- vector.) Instead
of viewing the service provider as picking the sampling rates
Interchanging the order of summation, we get
at the links, we view the service provider as picking a set of
detection probabilities at the links which belongs in the set U . Figures 2 and 3 depict the intruder’s and the service provider’s
Intruders Strategy: Pick a path from a to t
This can be equivalently written in a matrix form as qT M pwhere M is an m × |Pta| path-arc incidence matrix. Each rowin M represents a link in the network and each column of Mrepresents a path between nodes a and t. The entry correspond-
ing to row e and column P is set to one if e ∈ P and to zero
otherwise. A more natural payoff, is the probability of detec-
tion of the malicious packet as opposed to the expected num-ber of times the malicious packet is detected. In this case fora fixed path P ∈ Pta, the probability of the malicious packetbeing detected is given by 1 −
Defenders Strategy: Pick the sampling rates at the links
is non-linear in pe which makes the game theoretic problemintractable. However, the two payoffs that we outlined above
coincide if the optimal solution for the service provider is tosample at most one link on any path P ∈ Pta with q(P ) > 0. We call this strategy a minimal sampling strategy. We showlater that for all the problems we consider, the optimal solutionis a minimal sampling strategy.
that if his strategy is known to the service providerthen
tive of the intruder is to pick a distribution q() that minimizes
The objective of the service provider, using a similar argument
2) Payoff Matrix: Assume that the intruder and the service
provider each have chosen a strategy. This implies that the in-
truder has picked a probability distribution q over the set of
a and the service provider has picked a set of de-
tection probabilities p at the links. The payoff that we con-
This is a classical two person zero-sum game and the following
sider, is the expected number of times the malicious packet is
Theorem 1: There exists an optimal solution to the intrusion
Interpreting q(P ) as a flow on path P , the constraint
restricts the flow on a link e to be f
can be interpreted as the capacity of link e. The constraint
q(P ) = 1 enforces one unit of flow to be sent from
the source to the destination. Assume that fe is the capacity of
link e in the network. The objective then is to determine the
where θ is the value of the game.
smallest scaling factor λ, on the links in the network so that a
In the rest of this paper, we show how this minmax optimal
flow of one unit can be sent from the source to the destination.
solution can be computed for the intrusion detection game and
use that insight to route flows in the network. • Assume that link e has capacity fe and determine the max-
imum flow, Mat(f ) from the a to t using these capacities. • Set λ = Mat(f )−1. By scaling the capacities by λ, note
We now consider the solution of the minmax problem formu-
that a flow of one unit is sent from a to t.
lated in the last section. The idea is to get some insight into the
• The value of the game θ = BMat(f )−1.
structure of the problem which will enable us to extend the so-
Any maximum flow from a to t can be decomposed into a set
lution to more complex cases. Consider the intruders problem.
of flows on paths from a to t using standard flow decomposition
techniques. From network flow duality, note that corresponding
to the maximum flow value there is a minimum cut. The stable
operating point for the intruder and the service provider are the
For a fixed q ∈ V the inner maximization problem is the fol-
• Intruders Strategy: Solve the maximum flow Mat(f ),
from a to t using a capacity of fe on link e. Using stan-dard flow decomposition techniques, decompose the max-
imum flow into flow on paths P1, P2, . . . , Pl from a to
t. with flows of m1, m2, . . . , ml respectively. (Note that
li=1 mi = Mat(f ).)
licious packet along the path Pi with probability mi ∗• Service Providers Strategy: The service provider com-
putes the maximum flow from a to t using f
Associating a dual variable λ with the budget constraint, we
obtain the following dual optimization problem.
1, e2, . . . , er denote the arcs in the cor-
responding minimum cut with flows f1, f2, . . . , fr. From
ri=1 fi = Mat(f ). The service provider samples
link ei at rate BfiMat(f )−1.
We now illustrate the above results on the example shown in
Figure 4. The numbers next to the links are the flows on the
links. How these flows are generated is discussed in detail ina subsequent section. For now assume that the flows on the
Substituting this optimization problem in the intruders minmax
links are given. Assume that there is a sampling budget B of
formulation makes it the following minimization problem.
5 units. and a = 1 and t = 5 are the attack and target nodes
respectively. The links (1, 2), (4, 5) belonging to the minimuma − t cut are shown in thick lines. The minimum cut (and hence
the maximum flow) has a value of 11.5 units. The intruder’s
• Introduce the malicious packet along the path 1-2-5 with
• Introduce the malicious packet along the path 1-2-6-5 with
• Introduce the malicious packet along the path 1-3-4-5 with
The minmax strategy for the service provider is the follow-
• Sample link 1-2 at rate 5/11.5 giving a total sampling rate
of (5 × 7.5)/11.5 on that link. • Sample link 4-5 at rate 5/11.5 giving a total sampling rate
of (5 × 4.0)/11.5 on that link.
Note that θ = 5/11.5 is the value of the game.
The following observations can be made about the minmax
• The optimal strategy for the service provider is to sample
packets on the mincut with respect to the traffic flows. Thisimplies that along any path that the intruder would choose,
for commodity k will be represented by s(k), the destination
the malicious packet will be sampled at most on one link.
node by d(k) and the amount of demand (bandwidth) that has
Therefore this is a minimal sampling scheme.
to be routed for this source-destination pair is b(k). The service
• If B ≥ Mat(f ) then note that the malicious packet will al-
provider has to route these flows in the network respecting the
ways be detected. If B < Mat(f ) then there is a non-null
link capacity constraints. For the example shown in Figure 4,
probability that the malicious packet will not be detected.
each link is assumed to have a capacity of 10 units. The dif-ferent source-destination pairs and the corresponding demands
IV. ROUTING TO IMPROVE THE VALUE OF THE GAME
are shown in Table I. These demands have to be routed in the
In the last section, we showed that the value of the network
network such that the link capacity constraints are respected.
intrusion game is given by BMat(f )−1. All along, we assumed
There are several ways of routing these demands. One com-
that the flow f on the links is fixed. The flows on the links are
monly used method is to route the demands such that the max-
a result of routing the demands (aggregate traffic between node
imum link utilization in the network is minimized. (This can
pairs) in the network. In this section, we explore the case where
be solved as a maximum concurrent flow problem.) The link
the service provider adjusts the flows in the network in order to
flows shown in Figure 4 are a result of routing the demands in
maximize the value of the game. Corresponding to each pair
order to minimize the maximum utilization in the network. The
of nodes in the network, there could potentially be demands
that have to be routed from the first node in this pair to the
We now explore the case where the service provider routes
second node. Each node pair between which there is some de-
these flows such that the value of the network intrusion game
mand that has to be routed is termed a source-destination pair
is maximized. In other words, the service provider routes the
or a commodity. We assume that there are K source-destination
source-destination demands such that the maximum probabil-
demand pairs (commodities) in the network. The source node
ity of detection of the malicious packet is increased. We first
formulate this problem and then explore different heuristics
Instead of minimizing the left hand side of the inequality, we
to solve the problem. Recall that Pd(k)
minimize the upper bound represented by the right hand side of
paths between the source node s(k) and the destination node
the inequality. Since c is fixed, this is equivalent to maximizing
d(k) for commodity k. For notational simplicity, we refer to
x(P )) subject to the constraint that xX. We write this more formally as:
Note that Pk represents the set of valid paths
to route commodity k. Let X = {x(P ) :
≤ ce ∀e ∈ E}. Note that X
denotes an allocation of flow on paths in the network which
meets the demand for each commodity while satisfying the ca-pacity constraints on the links in the network. Given a fea-
sible routing vector, x ∈ X, the flow on link e is given by
x(P ). From Section III, the value of
the game is given by B/Mat(f ). The objective of the ser-
vice provider then is to route the source destination demands
such that the resulting value of Mat(f ) is as small as possible.
Therefore the objective of the service provider is to solve the
It is easy to view this as a multi-commodity flow problem with
K + 1 commodities. There are the original K commodities andan additional commodity between a and t. The size of the de-
mands for the first K commodities are known. We perform a
bisection search to determine the largest value of the commod-ity K + 1 that still results in a feasible routing for the first K
commodities. In order to develop an efficient algorithm it is
better to formulate the problem as a maximum concurrent flow
problem and perform the bisection search for this problem in-stead. We do not give the details of the solution procedure. In
Unfortunately this problem cannot be solved as a linear pro-
the case of the flow flushing algorithm, the link flows for the ex-
gramming problem. It is possible to reformulate this problem
ample in Figure 4 are shown in Figure 5 and the corresponding
as a non-convex optimization problem but it is not clear if there
is a solution technique to solve this problem. We therefore de-velop two different heuristics to get good solutions to this opti-
Let the m-vectors c and f represent the link capacity and
the flow on the link respectively. The flow on the links is a
result of routing the different source- destination demands in
Mat(f) + Mat(c − f) ≤ Mat(c).
This is true since the set of flows in the two terms on the lefthand side of the inequality is a feasible flow for the right hand
side of the inequality. Therefore Mat(f ) ≤ Mat(c) − Mat(c −f ). If f is the result of routing the source-destination demands
x(P )) ≤ M(c)−M(c−at(f ) on this network is 9.95 units.
The value of the game θ = 5/9.95. We now outline another
heuristic that can be used by the service provider to improve
Fig. 6. Cut Saturation Algorithm Network Set-up
the probability of detection of the malicious packet.
This algorithm relies on the fact that the maximum flow be-
tween a and t is upper bounded by the size of any a − t cut.
Let C represent the set of links in some a − t cut. Given any
link e ∈ E, let α(e) and β(e) represent the start and end nodes
of that link. The cut saturation algorithm picks some a − tcut and tries to direct flow away from this cut. Once the source-
destination demands are routed, this cut will be small and hence
will limit the maximum a − t flow. This is done as follows: In-troduce two new nodes s and t . Introduce an arc between node
s and all nodes α(e) for all e ∈ C. Similarly introduce links
between each node β(e) for each e ∈ C and the node t . The
objective now is to determine the highest flow that can be sentfrom s to t while maintaining the feasibility of routing thesource-destination demands. The modification of the network
saturation algorithm gives a better solution that the flow flush-
is shown in Figure 6. The only links shown in the network are
This problem can be solved almost identically to the Flow
Flushing Algorithm, except that the K + 1 commodity flows go
between nodes s and t . One way of choosing the cut that is
We consider several variants of the problem outlined above.
to be saturated is as follows: Assume that we currently have a
The first variant that we consider is the case where the intruder
routing of the source-destination demands resulting in a flow of
can introduce the malicious packet at one of a set of nodes A ⊂f (e) on link e. Determine a minimum a − t cut (using these
∈ A. The second variant that we consider
flows f as the capacities). Take this cut to be C and now at-
is the case where the objective of the intruder is to reach any one
tempt to saturate this cut. Continuing the example in Figure
of of a set of nodes T ⊂ N. We assume that A ∩ T = ∅. Both
4, assume that the cut that we saturate comprises of the links
these cases are easy to solve by introducing a super source node
(1, 2) and (4, 5). The links flows are shown in Figure 7 and the that is connected to all nodes in A and connecting all nodes incorresponding flows are shown in Table IV. T to a super sink node. The game is now played between the
The maximum flow Mat(f ) on this network is 8.0 units. The
super source node and the super sink node. Another variant is
value of the game θ = 5/8. Therefore, in this example, the cut
the case where the intruder can introduce the packet at any one
Note that L(d) represents the maximum flow that can be sent
from all the nodes in A to the destination node d. The value of
In this section we evaluated the algorithms developed on two
networks. The first network is shown in Figure 8. Each undi-
rected link in the figure represents two directed links each hav-
ing a capacity of 10 units. We performed the following experi-
of a set of nodes A but we assume that the intruder does not
have control of the routing in the network. Instead, we assume
that the routing in the network is shortest path routing like inOSPF or IS- IS. We term this a shortest path routing game.
We now consider the problem where the routing in the net-
work is along shortest paths. We assume that each link has alength and packets are routed from the source to the destination
along shortest paths according to this length metric. We assume
that ties are broken arbitrarily. Therefore given any two nodesin the network, there is a unique path from one node to the other.
Given a target node, all packets arriving at this node traverse theshortest path tree. Shortest path routing implies that there is a
unique tree rooted at the destination. A packet introduced at any
• Single attack node and single target node. (3 problems).
node in the network traverses the unique path from that node to
• Multiple attack node and single target node. (1 problem).
the destination along the links in the shortest path tree. We use
• Multiple attack node and multiple target node. (1 prob-
A to represent the set of nodes that the intruder can introduce a
malicious packet into the network. The objective of the intruder
For each of the cases, we ran three different algorithms.
is to determine which node of this set A to introduce the packet
1) Routing to minimize the highest utilized link with f1 rep-
into and the objective for the service provider is to determine
resenting the m-vector of link flows as a result of this
the sampling rate at the links subject to a sampling budget of
B. The main difference between this problem and the problem
2) Routing with flow flushing algorithm with f2 represent-
that we originally studied is the fact that it is easy to compute
ing the m-vector of link flows as a result of this routing
the maximum flow and hence the minimum cut on a tree. The
algorithm for solving this problem is the following:
3) Routing with cut saturation algorithm with f3 represent-
• Eliminate all leaf nodes in the routing tree that do not be-
ing the m-vector of link flows as a result of this routing
long to A. Let T represent this tree. Let P (i) represent the
predecessor of node i on T .
Let M (fi) for i = 1, 2, 3 represent the maximum flow that can
• Set L(i) = ∞ for all leaf nodes.
be sent from node a to t using fi as the link capacities. If B is
• While there are no leaf nodes do
the sampling budget, then the value of the game θ = B/M ().– Pick a leaf node i. Let e be the edge connecting i to
Table V shows the values of M () instead of θ. The smaller
P (i). Set L(P (i)) ← L(P (i)) + min{L(i), fe}.
that value of M , the better the chances of detection for a given
• Output L(t).
COMPARISON OF DIFFERENT ROUTING ALGORITHMS
From the table, note that the maximum flow value and hence
the value of the game can be changed significantly by changing
the routing in the network. In most of the examples the perfor-mance of the flow flusing algorithm and the cut saturation algo-
rithm are quite similar, and better than the simple minimization
Max. Utilization vs. Link Capacity for flow routing to minimize
A. Effect of Capacity on the Value of the Game
As the amount of spare capacity in a network increases, the
opportunity to reroute flows increases. This implies that theservice provider can improve the probability of detection byexploiting the spare capacity to reroute flows. We illustrate this
in the following set of experiments, using a second example
network, where the capacity of the links in the example network
are fixed at some constant value C. If the value of C increases,then the opportunity to reroute flows goes up. We consider theintrusion detection game between nodes a = 1 and t = 13. The
demands in the network are uniformly distributed between zeroand one. We first run the algorithm to route the flow such that
maximum utilization of any link is minimized. This maximumutilization value versus the link capacity C is shown in Figure9. As the maximum utilization becomes lower, the amount of
spare capacity to reroute flows increases in the network. This
implies that both the flow flushing algorithm as well as the cut
saturation algorithm will have more alternate paths. In Figure10, we show the performance of the flow flushing algorithm as
Fig. 10. Performance of flow flushing algorithm for different link capacities
the value of C increases. The straight line in the plot showsthe performance of the base case which is the routing algorithmthat minimizes the maximum utilization. The a − t maximum
packet sampling and examination in real-time can be expen-
flow is independent of the value of C. In the case of the flow
sive, the network operator must devise an effective sampling
flushing algorithm, the a − t maximum flow value decreases
scheme to detect intruding packets injected into the network
with increasing link capacity. It asymptotes at about 8.8. The
by an adversary. We considered the scenario where the adver-
same kind of performance was observed in the case of other
sary has considerable information about the network and can
attack-target pairs as well as the case for multiple attack sites.
either pick paths to minimize chances of detection or can pick asuitable network ingress-point if only shortest path routing is al-lowed. The detection via sampling problem was formulated in a
game-theoretic framework. The solution to this game-theoretic
We considered the problem of detecting intruding packets
problem is a max-flow problem from which the stable operat-
in a network by means of network packet sampling. Since
ing points are obtained. We also considered the network op-
erator’s problem of routing aggregate traffic between ingress-egress pairs as to to maximize the chances of detection withina given packet sampling budget. We proposed two heuristic al-gorithms for solving this problem. Finally, we evaluated theperformance of the developed algorithms on some sample net-works.
[1] R. K. Ahuja, T. L. Magnanti, J. B. Orlin, Network Flows: Theory, Algo-rithms, and Applications, Prentice Hall, 1993.
[2] Akella, A., Karp, R., Papadimitriou, C., Seshan, S., Shenker, S., “Selfish
Behavior and the Stability of the Internet: A Game Theoretic Analysis ofTCP”, Proceedings of SIGCOMM 2002, 2002.
[3] Duffield, N., Greenberg, A., Grossglauser, M., Rexford, J., “A Framework
for Passive Packet Measurement”. IETF Draft, work in progress, draft-duffield-framework-papame-01, February 2002.
onemann, J., “Faster and Simpler Algorithms for Multi-
commodity Flow and other Fractional Packing Problems”, Proceedingsof the 39th Annual Symposium on Foundations of Computer Science,pp.300-309, 1998.
[5] Korilis, Y., Lazar, A., Orda, A., “Architecting Noncooperative Networks”,
IEEE Journal on Selected Areas in Communications, pp. 1241-1251,September 1995.
[6] Ott, T. J., and Lakshman, T. V., and Wong, L. H., “SRED: Stabilized
RED”, Proceedings of Infocom 1999, pp. 1346-1355, 1999.
[7] Pan, R., Prabhakar, B., Psounis, K., “CHOKE, A Stateless Active Queue
Management Scheme for Approximating Fair Bandwidth Allocation”,Proceedings of Infocom 200, pp. 942-951, 2000.
[8] Owen, G., Game Theory, Academic Press, New York. [9] Shahrokhi, F., and Matula, D., “The Maximum Concurrent Flow Prob-
lem”, Journal of the ACM, 37, pp. 318-334, 1990.
[10] Shenker, S., “Making Greed Work in Networks: A Game-Theoretic Anal-
ysis of Switch Service Disciplines”, IEEE/ACM Transactions on Net-working, 1995.
[11] Washburn, A., and Wood, K., “Two-Person Zero-Sum Games for Net-
work Interdiction”, Operations Research, 43, pp. 243-251, 1995.