Multiplex communications – Data flow congestion prevention or control – Flow control of data transmission through a network
Reexamination Certificate
2000-04-19
2004-09-21
Patel, Ajit (Department: 2664)
Multiplex communications
Data flow congestion prevention or control
Flow control of data transmission through a network
C370S468000
Reexamination Certificate
active
06795401
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a bandwidth measuring method and apparatus for a packet switching network in which a plurality of test packets are fed to a packet switching network so that the bandwidth is measured, and more specifically relates to a bandwidth measuring method and apparatus for a packet switching network in which even a bandwidth (capacity) of a link that is distant from a tester that transmits test packets can be measured.
2. Description of the Related Art
FIG. 4
is a diagram showing a conventional bandwidth measuring method for a packet switching network. A receiver
40
is connected to a tester
10
via two transit nodes
20
A,
20
B.
In
FIG. 4
, the line width of each link
30
A,
30
B,
30
C connecting among the tester
10
, each transit nodes
20
A,
20
B and the receiver
40
represent the bandwidth of each one, respectively, and here, the bandwidth of the link
30
B between the transit nodes
20
A,
20
B is narrower than those of other links
30
A,
30
C, thereby forming a so-called bottleneck.
A tester
10
as a bandwidth measuring apparatus feeds two (or more) test packets TPa, TPb, which have the same packet length L to a link
30
A. When receiving each test packet, a transit node
20
A transfers one after another each test packet TPa, TPb to a link
30
B of its latter part, each time a reception is completed. The transit node
20
A starts receiving the test packet TPa at the time t
1
, and competes the reception at the time (t
1
+&Dgr;t
1
) that is &Dgr;t
1
after t
1
. Receiving the test packet TPb starts immediately after the completion of the reception of the test packet TPa, and the transit node
20
A completes the reception at the time (t
1
+2·&Dgr;t
1
) that is &Dgr;t
1
after the completion of the reception of the test packet TPa.
When the transit node
20
A is a receiver, the difference (=&Dgr;t
1
) between the reception completion time of the test packet TPb (t
1
+2·&Dgr;t
1
) and the reception completion time of the test packet TPa (t
1
+&Dgr;t
1
) is calculated. This difference &Dgr;t
1
corresponds to a transfer time of the test packet TPb by the link
30
A as far as the reception completion timing of the test packet TPa at the transit node
20
A (receiver) and the reception starting timing of the test packet TPb correspond to each other. The bandwidth of the link
30
A can be determined at the transit node
20
A (receiver) based on the difference &Dgr;t
1
and the packet length L of the test packet TPb.
In
FIG. 4
, a transit node
20
B receives the test packet TPa via the link
30
B at the time t
2
, and when the transit node
20
B completes the reception &Dgr;t
2
after, it immediately transfers the test packet TPa received to a link
30
C. Similarly, the transit node
20
B completes the reception of the test packet TPb at the time (t
2
+2·&Dgr;t
2
) and immediately transfers it to the link
30
C. Since the bandwidth of the link
30
B is narrower than that of the link
20
A, the period &Dgr;t
2
that the transit node
20
B requires to receive each test packet TPa, TPb becomes longer than the &Dgr;t
1
.
If the bandwidth of the link
30
C that is the latter part is sufficiently wide as similar to the link
30
A, as the transit node
20
B starts transferring the test packet TPa at the time t
3
, the transfer can be completed after &Dgr;t
3
(<&Dgr;t
2
) that is similar to the &Dgr;t
1
. However, since &Dgr;t
3
is shorter than the &Dgr;t
2
, at the transit node
20
B at the time (t
3
+&Dgr;t
3
), when the transfer of the TPa is completed, the reception of the test packet TPb is not completed. Thus, the transit node
20
B cannot start transferring the test packet TPb immediately after the transferring of the test packet TPa is completed.
The transit node
20
B, immediately after completing the reception of the test packet TPb at the time (t
2
+2·&Dgr;t
2
), transfers it to a receiver
40
. However, after the completion of the reception of the first test packet TPa at the time t
4
, an empty time (between packets gap) &Dgr;t gap is generated at the receiver
40
until the reception of the next test packet TPb is started. When the reception of the test packet TPb is completed &Dgr;t
4
after the start of the reception, the times when the receiver
40
completes the receptions of each test packet TPa, TPb become t
4
, (t
4
+&Dgr;t gap+&Dgr;t
4
), respectively. Since the difference (&Dgr;t gap+&Dgr;t
4
) extra includes the between packets gap &Dgr;t gap, a true transmitting time of the test packet TPb is not represented. Therefore, the receiver
40
cannot determine the bandwidth of the link
30
C based on the difference (&Dgr;t gap+&Dgr;t
4
) and the packet length L of the test packet TPb.
SUMMARY OF THE INVENTION
The object of the present invention is to provide a bandwidth measuring method and apparatus for a packet switching network in which a bandwidth of a link that is distant from a tester that transmits test packets, specifically a bandwidth distant beyond a bottleneck, can be measured.
A feature of the present invention is to that, a bandwidth measuring method for a packet switching network in which a bandwidth of a packet switching network comprising a plurality of nodes for packet switching connected mutually is measured, said method comprising a procedure in which a plurality of test packets which at least include two test packets having different packet length are fed to the packet switching network so that in said two test packet, the test packet having a long packet length and the test packet having a short packet length are successive in this order, and a procedure in which a receiver receiving each test packet determines an immediately former bandwidth based on the difference in the reception completion timing thereof.
According to the aforementioned characteristics, in two test packets that were successively fed, since the packet length (L
1
) of the first test packet (TPI) is longer than the packet length (L
2
) of the next test packet (TP
2
). Therefore, the transit node to whose latter part a target link is connected can complete the receiving of the next test packet (TP
2
) from the link of the former part until feeding of the first received test packet (TP
1
) to the target link is completed, even when the bandwidth of the link that is connected to the former part of the transit node is narrower than that of the target link.
Therefore, to the target link of the latter part, the next test packet (TP
2
) can be fed at the same time when feeding of the first test packet (TP
1
) is completed, thereby enabling prevention of generation of a between packets gap of each test packet on the target link of the latter part. As a result of this, since the difference of the times when the receiver of the latter part completes receiving of each test packet represents the times that the target link requires to transfer the test packet (TP
2
), the receiver can determine the bandwidth of the target link based on the difference of the receiving completion times and the packet length of the test packet (TP
2
).
REFERENCES:
patent: 5477531 (1995-12-01), McKee et al.
patent: 5519689 (1996-05-01), Kim
patent: 5802106 (1998-09-01), Packer
patent: 6002671 (1999-12-01), Kahkoska et al.
patent: 6363056 (2002-03-01), Beigi et al.
patent: 6424624 (2002-07-01), Galand et al.
patent: 0 522 211 (1993-01-01), None
Lai, K. et al.; “Measuring Bandwidth”; Proceeding IEEE Inforcom. The Conference on Computer Communications, US, New York; Mar. 21, 1999; pp. 235-245.
Vern Paxson; “Measurements and Analysis of End-to-End Internet Dynamics”; PhD Dissertation; Apr. 1997.
Srinivasan Deshav; “A Control-Theoretic Approach to Flow Control”; Computer Communications Review; US; Association for computing Machinery, vol. 21, No. 4, Sep. 1, 1991.
Kevin Lai and Mary Baker, 1999 IEEE, Department of Computer Science, Stanford University—“Measuring Bandwidth”, p. 235-245.
Ha Yvonne Quy
KDD Corporation
Patel Ajit
Westerman Hattori Daniels & Adrian LLP
LandOfFree
Band width measuring method and apparatus for a packet... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Band width measuring method and apparatus for a packet..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Band width measuring method and apparatus for a packet... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3207849