# US 8,151,019 B1 · Adaptive network traffic shaper

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 8,151,019 B1
- Document ID: US8151019B1
- Status: Granted
- Kind: B1
- Application number: 12/107,428
- Filed: 2008-04-22
- Granted: 2012-04-03
- Earliest claimed: 2008-04-22
- Assignees: Lockheed Martin Corporation
- Inventors: Tuong Le; Brian F. Rossa
- Web page: https://patentgrep.com/patent/US8151019B1

## CPC

- G06F 5/065: {Partitioned buffers, e.g. allowing multiple independent queues, bidirectional FIFO's}
- H04L 47/2441: relying on flow classification, e.g. using integrated services [IntServ]
- H04L 47/20: Traffic policing
- H04L 47/22: Traffic shaping
- H04L 47/2408: for supporting different services, e.g. a differentiated services [DiffServ] type of service
- H04L 47/28: in relation to timing considerations
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

A network traffic shaper adjusts the rate of data flowing from a packet source to a packet sink responsive to priority assigned to the packets pursuant to their ability to match a series of filters. Each packet is applied to a queue depending on its classification. The packets are read from each queue in accordance with a queue reading policy. Singular spectrum analysis of the traffic load produces a set of vectors that capture the spectral bases of the traffic state. These vectors are associated with the bandwidth demanded by the traffic, a relationship that is recorded in a queue/time/eigenvector/bandwidth/control table. Samples of the current network load are compared with previously recorded vector bases to reveal how similar the current traffic state is to previous traffic states, which in turn predicts the traffic's bandwidth needs for the immediate future. The queue reading regime is updated in response to this prediction.

## Claims

### Claim 1

A method for transmitting packets of data from a source network to a destination network, said method comprising the steps of:
classifying each packet accordingly to its ability to match a series of filters, and marking each packet with the classification;
applying each packet to a queue of a set of queues in dependence upon the packet's classification;
reading said packets from each queue in accordance with a predetermined queue reading policy;
observing a volume of traffic arriving at each queue during N−2n previous time intervals to thereby define traffic load history for each queue, where n is a system parameter and N is a current time step;
from said traffic load history, constructing a matrix Xj[N] for each queue j={0, . . . , M} that captures a state of the traffic entering that queue;
performing an eigen analysis of the matrix Rj[N]=(Xj[N])T(XJ[N]) to produce a set of vectors Uj[N] that capture a spectral basis of the traffic state;
comparing a current traffic state to the traffic state at time k by projection Xj[N] onto the spectral bases Uj[k] according to the relation
D
⁡
(
X
,
U
)
=
∑
i
=
1
n
⁢
(
X
i
)
T
⁢
(
X
i
)
-
(
X
i
)
T
⁢
(
U
)
⁢
(
U
)
T
⁢
(
X
i
)
where
X and U are square matrices of size n-by-n;
Xi are the columns of X;
making a bandwidth bj[k] a new queue reading policy for queue j if a previously recorded Uj[k] can be found to satisfy the inequality Dj[N,k]≦D* where Dj[N,k]=D(Xj[N][Uj[k]);
otherwise
recording a current spectral basis Uj[N] and current bandwidth requirement bj[N].

### Claim 2

A method for prioritizing network traffic to control quality-of-service where each of a plurality of packets carries information relating to its priority relative to other messages, said method comprising the steps of:
observing at least packet sizes and data each of the packets contain;
determining each of the packet's priority based on the data it contains;
routing each of the packets to one of a plurality of queues allocated to a relevant priority;
temporarily storing said packet sizes and their destination queue numbers;
determining and storing a volume of data arriving at each of the queues over a time window using the temporarily stored packet sizes and destination queue numbers;
determining a load spectrum of incoming network traffic by singular spectrum analysis using the determined volume of data from each of the queues;
associating the load spectrum with a rate of data arriving at each of the queues over a time window; and
applying the packets of said network traffic to a traffic shaper, which allocates a portion of an available transmission bandwidth to each of the queues according to a stored policy.

### Claim 3 (depends on 2)

A method according to claim 2, further comprising the step of storing the load spectrum and associated data rate.

### Claim 4 (depends on 2)

A method according to claim 2, further comprising the step of:
periodically adjusting the stored policy according to changes in the load spectrum.

### Claim 5 (depends on 2)

A method according to claim 2, further comprising the steps of:
periodically adjusting the stored policy according to changes in the load spectrum; and
storing the load spectrum and associated data rate.

### Claim 6

A method for transmitting packets of information from a source network, said method comprising the steps of:
classifying a priority of each of the packets based on data it contains;
marking each of the packets with the classification;
applying each of the packets to one of a plurality of queues depending upon its marked priority;
reading each of the queues according to a queue reading policy;
while said packets are traversing said queues, calculating a traffic spectral basis and associated network bandwidth to generate a queue/time/eigenvector/bandwidth/control table;
finding a similarity of a current traffic state to a traffic state at time k by calculating a distance from the spectral basis at time k;
searching the queue/time/eigenvector/bandwidth/control table for a previously observed traffic state that is similar to the current traffic state to determine an expected network bandwidth demand; and
updating the queue reading policy to meet the expected network bandwidth demand.

### Claim 7

A system for prioritizing network traffic including a plurality of packets, where each of the packets of said network traffic carries information relating to its priority relative to other messages, said system comprising:
a processor executing instructions to perform the steps of:
observing at least packet sizes and data each of the packets contain;
determining each of the packet's priority based on the data it contains;
routing each of the packets to one of a plurality of queues allocated to a relevant priority;
temporarily storing said packet sizes and their destination queue numbers using the temporarily stored packet sizes and destination queue numbers;
determining and storing a volume of data arriving at each of the queues over a time window using the determined volume of data from each of the queues;
determining a load spectrum of incoming network traffic by singular spectrum analysis;
associating the load spectrum with a rate of data arriving at each of the queues over a time window; and
applying the packets of said network traffic to a traffic shaper, which allocates a portion of an available transmission bandwidth to each of the queues according to a stored policy.

### Claim 8 (depends on 7)

A system according to claim 7, wherein the processor executes instructions to perform the further step of storing the load spectrum and associated data rate.

### Claim 9 (depends on 7)

A system according to the claim 7, wherein the processor executes instructions to perform the further step of periodically adjusting the stored policy according to changes in the load spectrum.

### Claim 10 (depends on 7)

A system according to claim 7, wherein the processor executes instructions to perform the further step of periodically adjusting the stored policy according to changes in the load spectrum; and storing the load spectrum and associated data rate.

### Claim 11 (depends on 7)

A system according to claim 7, further comprising a sensor for reading packet size and queue information and for sending said information to a queue/size table.

### Claim 12 (depends on 11)

A system according to claim 11, further comprising a multiplexor for receiving each of the packets from said sensor and for routing each packet to a queue in accordance with a marked priority.

### Claim 13 (depends on 7)

A system according to claim 7, wherein the processor executes instructions to perform the further step of comparing a current state of traffic entering each of the queues to traffic states that have been previously observed, and adjusting the stored policy in accordance with said previous observations.

### Claim 14 (depends on 13)

A system according to claim 13, wherein said step of adjusting the stored policy is responsive to changes in the load spectrum.

### Claim 15 (depends on 13)

A system according to claim 13, wherein said step of adjusting the stored policy is responsive to meet an expected bandwidth demand for an associated queue.

### Claim 16 (depends on 2)

A method according to claim 2, comprising the further step of comparing a current state of traffic entering each of the queues to traffic states that have been previously observed, and adjusting the stored policy in accordance with said previous observations.

### Claim 17 (depends on 16)

A method according to claim 16, wherein said step of adjusting the stored policy is responsive to changes in the load spectrum.

### Claim 18 (depends on 16)

A method according to claim 16, wherein said step of adjusting the stored policy is responsive to meet and expected bandwidth demand for an associated queue.