# US 2009/0245103 A1 · Congestion detection method, congestion detection apparatus, and recording medium storing congestion detection program recorded thereon

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

- Number: US 2009/0245103 A1
- Document ID: US20090245103A1
- Status: Published application
- Kind: A1
- Application number: 12/410,099
- Filed: 2009-03-24
- Published: 2009-10-01
- Earliest claimed: 2008-03-25
- Assignees: Fujitsu Limited
- Inventors: Hideaki Miyazaki
- Web page: https://patentgrep.com/patent/US20090245103A1

## CPC

- H04L 41/0677: Localisation of faults
- H04L 43/0829: Packet loss
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

According to an aspect of the embodiments, a congestion detection method causes a computer to function as a congestion detection apparatus connectable to a network. Packets on the network are obtained and a packet loss is detected. A packet group made up of a series of packets based on the obtained packets is extracted. A packet loss in the packet group is detected and a position in the packet group where the packet loss occurred is detected. Whether congestion is occurring is judged based on the position of the packet loss in the packet group.

## Claims

### Claim 1

A congestion detection method for causing a computer to function as a congestion detection apparatus connectable to a network, the congestion detection method comprising:
obtaining packets on the network;
extracting a packet group made up of a series of packets based on the obtained packets;
detecting a packet loss in the packet group and locating a position in the packet group where the packet loss is occurring; and
judging whether congestion is occurring based on the position of the packet loss in the packet group.

### Claim 2 (depends on 1)

The congestion detection method according to claim 1, wherein
the judging judges that congestion is occurring if the position of the packet loss is a position temporally posterior to a given position in the packet group, and
the given position is any position in the packet group from a center of the given position to a latter half portion in terms of packet obtaining time in the obtaining of the packets on the network.

### Claim 3 (depends on 2)

The congestion detection method according to claim 2, wherein the judging judges that congestion is occurring if a number of packet losses at positions temporally posterior to the given position in the packet group is greater than a number of packet losses at positions temporally anterior to the given position.

### Claim 4 (depends on 2)

The congestion detection method according to claim 2, wherein
the judging statistically estimates a confidence interval of a population mean of loss rates using a packet loss rate and a number of packets in an anterior portion temporally anterior to the given position in the packet group, sets an upper limit value of the estimated confidence interval as a threshold A, and judges that congestion is occurring if the packet loss rate in a posterior portion temporally posterior to the given position in the packet group is greater than the threshold value A.

### Claim 5 (depends on 4)

The congestion detection method according to claim 4, wherein the judging obtains the threshold value A according to either Formula (2) or (3):
Threshold value A=Lf+1.96√{square root over (Lf(L−Lf)/N)} (Lf≠0) (2)
Threshold value A=1−(0.95)1/N(Lf=0) (3)
where Lf is the packet loss rate in the anterior portion and N is the number of packets in the anterior portion.

### Claim 6 (depends on 1)

The congestion detection method according to claim 1, wherein when N represents a packet position number that indicates an order of a packet within the packet group as counted from a first packet in the packet group, and the judging judges that congestion is occurring if an average value M of packet position numbers N at the position of the packet loss is greater than a threshold value W which is a first value of “i” that satisfies Formula (4) when varying “i” as i=x, x-1 . . . , in sequence,
∑
t
=
i
x

F

(
x
,
y
,
t
×
y
)
C
y
x
>
Z
(
4
)
where
“F (a, b, c)” shows the frequency of pattern that a sum of b figures selected from 1 to a becomes a figure of c,
“x” is a number of packets in the packet group,
“y” is a number of packet losses in the packet group, and
“Z” is a given lower limit for judging that congestion is occurring.

### Claim 7 (depends on 1)

The congestion detection method according to claim 1, wherein upon detecting that original data has been divided into a plurality of packets, the extracting extracts the plurality of packets as the packet group.

### Claim 8 (depends on 1)

The congestion detection method according to claim 1, wherein the extracting compares packet intervals which are time intervals at which each of the packets is obtained with a given value, and extracts the packet group based on results of comparison.

### Claim 9 (depends on 8)

The congestion detection method according to claim 8, wherein the given value is a value that is decided based on an average value of the packet intervals.

### Claim 10 (depends on 9)

The congestion detection method according to claim 9, wherein the given value is a value that is decided based on the average value of the packet intervals and a standard deviation of the packet intervals.

### Claim 11 (depends on 1)

The congestion detection method according to claim 1, wherein the extracting stores a rule of change for change in a number of packets in the packet group, determines the number of packets in a packet group in which a packet loss has occurred based on a number of packets in a packet group in which no packet loss has occurred and the rule of change, and extracts a packet group in which a packet loss has occurred based on the determined number of packets.

### Claim 12 (depends on 1)

The congestion detection method according to claim 1, wherein
the judging locates a network position where congestion is occurring on the network by compiling results of congestion judgment for each of addresses of terminals that transmitted the packets and analyzing presence/absence of congestion for each layer of the addresses.

### Claim 13

A congestion detection apparatus that is connectable to a network, comprising:
a packet acquiring part obtaining a plurality of packets on the network;
a packet group extracting part extracting a packet group made up of a series of packets based on the obtained packets;
a packet loss detecting part detecting a packet loss in the packet group and locating a position in the packet group where the packet loss has occurred; and
a congestion judging part judging whether congestion is occurring based on the position of the packet loss in the packet group.

### Claim 14

A computer-readable recording medium storing a computer program for causing a computer to function as a congestion detection apparatus that is connectable to a network, the computer program causes the computer to execute:
obtaining packets on the network;
extracting a packet group made up of a series of packets based on the obtained packets;
detecting a packet loss in the packet group and locating a position in the packet group where the packet loss has occurred; and
judging whether congestion is occurring based on the position of the packet loss in the packet group.

### Claim 15

An apparatus on a data network, comprising:
a computer processor to execute
detecting a lost data packet in a data packet group transmitted on the network;
locating a positional order of the lost data packet in the data packet group; and
judging whether congestion is occurring in the network based on the position of the lost data packet in the data packet group.

### Claim 16 (depends on 14)

The apparatus according to claim 14, wherein the detecting of the lost data packet comprises detecting the lost packet before extracting the data packet group, after the extracting of the data packet group, a combination thereof.
