 |
Claims  |
|
|
What is claimed is:
1. A data processing method for improving the performance of a window
protocol based data communications network including a sending node which
sends a first window's worth of data packets during a first cycle on a
first communications link in the network to an intermediate node having a
queue, the queue outputting data packets at a departure rate on a second
communications link in the network to a destination node and the
intermediate node further outputting queue size information during the
first cycle to the sending node, the destination node sending a marker to
the sending node indicating the receipt of data packets from the first
window's worth of data packets, the sending node sensing a second window's
worth of data packets during a second cycle in response to having received
the marker, the second window's worth of data packets having a size
controlled by the queue size information, the method comprising the steps
of:
inputting to a data processor a physical and logical network path
description of said data communications network, including a size value of
said first window's worth of data packets and a departure rate value for
said departure rate;
computing in said data processor a first queue size information during the
first cycle, from said size value of the first window's worth of data
packets and said departure rate of the queue;
comparing in the data processor the first queue size information with a
threshold queue size value;
computing in the data processor the size of the second window's worth of
data packets, from the size of the first window's worth and the result of
said comparing step;
computing a first cycle time duration of the first cycle necessary to
transmit a data packet in the first window's worth of data packets from
the sending node to the destination node and to transmit the marker from
the destination node to the sending node;
storing the size of the first window's worth of data packets and the first
cycle time in a table in the data processor;
computing in the data processor a second queue size information during the
second cycle, from the size of the second window's worth of data packets
and the departure rate of the queue;
comparing in the data processor the second queue size information with the
threshold queue size value;
computing in the data processor the size of the next window's worth of data
packets, from the size of the second window's worth and the result of said
comparing step for said second cycle;
computing a second cycle time duration of the second cycle necessary to
transmit a data packet in the second window's worth of data packets from
the sending node to the destination node and to transmit the marker from
the destination node to the sending node;
storing the size of the second window's worth of data packets and the
second cycle time in said table in the data processor;
determining in said data processor from said table a period for a
repetitive pattern of said cycle times and said window sizes;
computing in said data processor throughput value for said network from
said cycle times in said period;
outputting a recommendation from said data processor for changes to network
parameters and physical characteristics of said data communications
network; and
implementing said changes to network parameters and physical
characteristics in said data communications network.
2. A data processing method for improving the performance of a window
protocol based data communications network including a sending node which
sends a first window's worth of data packets during a first cycle on a
first communications link in the network to an intermediate node having a
queue, the queue outputting data packets at a departure rate on a second
communications link in the network to a destination node and the
intermediate node further outputting queue size information during the
first cycle to the sending node, the destination node sending a marker to
the sending node indicating the receipt of data packets from the first
window's worth of data packets, the sending node sending a second window's
worth of data packets during a second cycle in response to having received
the marker, the second window's worth of data packets having a size
controlled by the queue size information, the method simulating the
comprising the steps of:
inputting to a data processor a physical and logical network path
description of said data communications network, including a size value of
said first window's worth of data packets and a departure rate value for
said departure rate;
computing in said data processor a first queue size information during the
first cycle, from said size value of the first window's worth of data
packets and said departure rate of the queue;
comparing in the data processor the first queue size information with a
threshold queue size value;
computing in the data processor the size of the second window's worth of
data packets, from the size of the first window's worth and the result of
said comparing step;
computing a first cycle time duration of the first cycle necessary to
transmit a data packet in the first window's worth of data packets from
the sending node to the destination node and to transmit the marker from
the destination node to the sending node;
storing the size of the first window's worth of data packets and the first
cycle time in a table in the data processor;
computing in the data processor a second queue size information during the
second cycle, from the size of the second window's worth of data packets
and the departure rate of the queue;
comparing in the data processor the second queue size information with the
threshold queue size value;
computing in the data processor the size of the next window's worth of data
packets, from the size of the second window's worth and the result of said
comparing step for said second cycle;
computing a second cycle time duration of the second cycle necessary to
transmit a data packet in the second window's worth of data packets from
the sending node to the destination node and to transmit the marker from
the destination node to the sending node;
storing the size of the second window's worth of data packets and the
second cycle time in said table in the data processor;
determining in said data processor from said table a period for a
repetitive pattern of said cycle times and said window sizes;
computing in said data processor throughput value for said network from
said cycle times in said period;
outputting a recommendation from said data processor for changes to network
parameters and physical characteristics of said data communications
network; and
implementing said changes to network parameters and physical
characteristics in said data communications network.
3. A data processing method for improving the performance of a window
protocol based data communications network including a sending node which
sends a first window's worth of data packets during a first cycle on a
first communications link in the network to an intermediate node having a
queue, the queue outputting data packets at a departure rate on a second
communications link in the network to a destination node and the
intermediate node further outputting queue size information during the
first cycle to the sending node, the destination node sending a marker to
the sending node indicating the receipt of data packets from the first
window's worth of data packets, the sending node sending a second window's
worth of data packets during a second cycle in response to having received
the marker, the second window's worth of data packets having a size
controlled by the queue size information, the method comprising the steps
of:
inputting to a data processor a physical and logical network path
description of said data communications network, including a size value of
said first window's worth of data packets and a departure rate value for
said departure rate;
computing in said data processor a first queue size information during the
first cycle, from said size value of the first window's worth of data
packets and said departure rate of the queue;
comparing in the data processor the first queue size information with a
threshold queue size value;
computing in the data processor the size of the second window's worth of
data packets, from the size of the first window's worth and the result of
said comparing step;
computing a first cycle time duration of the first cycle necessary to
transmit a data packet in the first window's worth of data packets from
the sending node to the destination node and to transmit the marker from
the destination node to the sending node;
storing the first queue size and the first window size in a table in the
data processor;
computing in the data processor a second queue size information during the
second cycle, from the size of the second window's worth of data packets
and the departure rate of the queue;
comparing in the data processor the second queue size information during
the second cycle, from the size of the second window's worth of data
packets and the departure rate of the queue;
comparing in the data processor the second queue size information with the
threshold queue size value;
computing in the data processor the size of the next window's worth of data
packets, from the size of the second window's worth and the result of said
comparing step for said second cycle;
whereby said second throughput value more closely approximates a desired
throughput value.
4. The method of claim 3 which further comprises the steps of:
following the steps of computing the throughput value of the network from
said cycle times in said period, selecting a second threshold queue size
value;
repeating said steps of computing in a data processor a first queue size
information during the first cycle and then;
comparing in the data processor the first queue size information with said
second threshold queue value;
using said second threshold queue size value in the subsequent steps:
computing a second throughput value for said network from said cycle times
in said period, having a use of said second threshold queue size value;
whereby said second throughput value more closely approximates said desired
throughput value.
5. The method of claim 3, wherein said step of determining said repetitive
pattern includes determining a repetitive pattern for window sizes, queue
sizes, cycle times, arrival patterns and output patterns. |
|
 |
|
 |
Claims |
|
|
|
Description |
|
|
BACKGROUND OF THE INVENTION
1. Technical Field
The invention disclosed broadly relates to data processing systems and
methods and more particularly relates to a data processing method for the
efficient simulation of a data communications network operating with a
window-based protocol.
2. Background Information
Window protocols have been successfully used for multiple purposes in
computer networks. Often, they are found at several network architecture
layers. They provide a means for flow control and are at the heart of any
network congestion control mechanism. Typical window protocols are found
in IBM's System Network Architecture which is explained, for example, in
the book by Anura Guruge, SNA--Theory in Practice, Pergamon Infotech Ltd.,
1984. Another window protocol system can be found in DECnet which is
described, for example, in the article by Raj K. Jain, "A Timeout Based
Congestion Control Scheme for Window Flow Controlled Networks," IEEE
Journal on Selected Areas in Communications, Vol. SAC-4, No. 7, October
1986. Window protocols allow control of the amount of data in transit
between two users of the protocol. As a flow control mechanism they
prevent a fast sender from overwhelming a slow receiver. The prior art
approach to the analysis of window protocols has been limited to queuing
theory or by simulation. Formal queuing theory is used in the analysis of
computer network behavior. An example of this is described by Leonard
Kleinrock, "Queuing Systems," Vol. 2, Computer Applications, New York:
Wiley - Interscience, 1976.
Since queuing theory analysis has problems characterizing the dynamic
behavior of a network, simulation methods have been applied. Typically,
simulations are performed to validate analytic models or investigate the
operational details of a specific mechanism. However, considerable effort
is involved in building and running any simulator. The use of a benchmark
that specifies system topology, hardware behavior and trial workloads
requires development. Frequently, shortcuts are taken at the expense of
accuracy. Validation of a simulation model and the proper choice of a
benchmark to evaluate window protocol behavior appear to be open problems.
OBJECTS OF THE INVENTION
It is therefore an object of the invention to provide a method to more
efficiently simulate a window-based protocol for a data communications
network.
It is another object of the invention to provide an improved method for
optimizing a data communications network employing a window-based
protocol.
SUMMARY OF THE INVENTION
These and other objects, features and advantages are accomplished by the
method disclosed herein. The invention is a method for the efficient
simulation of the dynamic behavior of a data communications network
running under a window-based protocol. The typical data communications
network includes a sending node which sends a first window's worth of data
packets during a first cycle on a first communications link in the network
to an intermediate node having a queue. The queue outputs data packets at
a departure rate on a second communications link in the network to a
destination node and the intermediate node further outs queue size
information during the first cycle to the sending node. The destination
node sends a marker to the sending node indicating the receipt of data
packets from the first window's worth of data packets. The sending node
then sends a second window's worth of data packets during a second cycle
in response to having received the marker, the second window's worth of
data packets having a size controlled by the queue size information.
The inventive method efficiently simulates the dynamic behavior of the
communications network. The method includes the step of computing in a
data processor a first queue size information during the first cycle, from
the size of the first window's worth of data packets and the departure
rate of the queue. Then the method compares in the data processor the
first queue size information with a threshold queue size value. It then
computes in the data processor the size of the second window's worth of
data packets, from the size of the first window's worth and the result of
the comparing step. Then the method computes a first cycle time duration
of the first cycle necessary to transmit a data packet in the first
window's worth of data packets from the sending node to the destination
node and to transmit the marker from the destination node to the sending
node. At the end of the first stage, the method stores the size of the
first window's worth of data packets and the first cycle time in a table
in the data processor.
In the second stage, the method computes in the data processor a second
queue size information during the second cycle, from the size of the
second window's worth of data packets and the departure rate of the queue.
Then it compares in the data processor the second queue size information
with the threshold queue size value. The method then computes in the data
processor the size of the next window's worth of data packets, from the
size of the second window's worth and the result of the comparing step for
the second cycle. Then the method computes a second cycle time duration of
the second cycle necessary to transmit a data packet in the second
window's worth of data packets from the sending node to the destination
node and to transmit the marker from the destination node to the sending
node. Then the method stores the size of the second window's worth of data
packets and the second cycle time in the table in the data processor.
Finally, the method determines in the data processor from the table a
period for a repetitive pattern of the cycle times and the window sizes,
and from this, the method computes a throughput value for the network from
the cycle times in the period.
BRIEF DESCRIPTION OF THE DRAWINGS
FIGS. 1A-1M show a sequence of schematic diagrams of a data communications
network operating under a window-based protocol, as it achieves a periodic
repetition of the dynamic behavior for the system.
FIG. 2 is a table which summarizes the consecutive states of the data
communications network of FIGS. 1A-1M.
FIG. 3 is a flow diagram of the invention.
DESCRIPTION OF THE BEST MODE FOR CARRYING OUT THE INVENTION
A window-based protocol for a data communications network is modeled by the
disclosed method. The method attributes physical and logical parameters to
the components in the communications network. This includes an initial
window size for the input terminal in the communications network. The
initial window size will dynamically change over time as information
packets are propagated through the network and control signals are fed
back in accordance with the window protocol. A first cycle for exercising
the model consists of transmitting from the input station, the first
window of data. The second cycle consists of inputting the next window of
data. Consecutive cycles consist of inputting consecutive windows of data.
At the end of each cycle a state characterization is inferred for the
network. The network consists of a series connected array of queues. Each
queue has been specified by the user as having a given threshold size and
a given maximum rate of data transmission. As the network passes data
through consecutive cycles, several of the queues begin filling with data
that could not be passed during the current cycle. When a given queue in
the network reaches a threshold level of accumulated data, it will feed
back a control signal to the beginning or input node, signaling that the
window size for inputting data during a next cycle should be reduced. The
number of bytes accumulated in each of the queues in the network
represents the state of the network during a particular cycle. In
accordance with the invention, the states of the consecutive cycles are
monitored and an attempt is made to recognize a repetitive pattern for
those consecutive states. When a repetitive pattern for the occurrence of
the states in the network is identified, the data throughput for a period
of state repetition is characterized and extrapolated to find the total
amount of time necessary to transfer the remaining bytes of data necessary
to achieve a predetermined total byte transmission. It is the
characterization of the period for the repetitive pattern of cyclic states
and the extrapolation based upon the identification of the repetitive
pattern of states for the window-based protocol network, which is the
heart of the invention.
Each window's worth of data which is input at the input node includes a
marker. When that marker reaches the destination node at the end of the
serial network, that marker is fed back to the input node. When that
feedback is received by the input node, a decision is made as to whether
the window size is to be changed for the next window's worth of data to be
input. The window size will be increased unless a signal is received from
any of the nodes in the network indicating that its queue has reached a
threshold of accumulated messages. When a queue threshold signal is
received at the input node, a decision is made as to whether that is
adequate to not increase the window size or alternately to decrease the
window size for the next window's worth of data to be input. Over the
course of consecutive cycles, the state of accumulated messages in each of
the queues oscillates and the window size at the input node oscillates.
After sufficient time has elapsed, a periodic pattern of filled queues and
window sizes will occur and this is the repetitive pattern of states which
is to be identified, in accordance with the invention.
FIGS. 1A-1M illustrate a data communications network operating under a
window-based protocol, illustrating the sequential cycles in its
operation. The data communications network was represented by an origin
node 20, an intermediate node 22, and a destination node 24. A data source
26 supplies a sufficient quantity of data packets to the origin node 20.
The origin node 20 includes the window generator 28 which receives data
packets from the data source 26 and which outputs a window's worth of data
packets to the queue 30. The queue 30 has a characteristic departure rate
for outputting data packets over communications link 32 to the
intermediate node 22. The intermediate node 22 includes the queue 34 which
receives the data packets from the link 32. The queue 34 has another
departure rate which characterizes it, which is the rate at which packets
are output from the queue 34 onto the communications link 36 to the
destination node 24.
When the destination node 24 receives a data packet from a window's worth
of data packets, it outputs a marker response over line 38 to the window
28 in the origin node 20. In response to the receipt of the marker
response on line 38, the window 28 will output a second window's worth of
data packets to the queue 30.
The queue 30 has a threshold value assigned to it for the maximum number of
packets which can be stored in the queue, above which a threshold
congestion signal V1 is output to the window 28. Similarly, the queue 34
has a second threshold value assigned to it for the maximum number of data
packets which can accumulate in the queue 34, above which a threshold
congestion signal V2 will be output from queue 34 to the window 28. The
input 44 to the window 28 supplies the threshold congestion signals V1 and
V2 from the queues 30 and 34, respectively, to the window 28.
When the window 28 receives a threshold congestion signal on the line 44,
the next window's worth of data packets will have a reduced size from the
current window's worth of data packets, in order to reduce the number of
data packets which are output during the next cycle to the queue 30.
A cycle is defined as the duration of time between the receipt of a first
marker response on line 38 and the receipt of a second marker response on
line 38 at the window 28.
Each cycle of the data communications network can be characterized by a
state with the parameters of that state including the cycle time duration
from the receipt of a first marker response 38 to the receipt of a second
marker response 38 at the window 28. Other parameters defining a state can
include the window size during a cycle, the maximum number of packets
stored at any instant in the first queue 30 or in the second queue 34.
As the cycles of operation progress for the data communications network,
the states for each respective cycle will form a pattern which will
ultimately become repetitive. The repetition period for the pattern of
states is significant since for the transmission of large blocks of data
over an extended interval of time, a plurality of consecutive periods of
repetitive patterns will occur.
In accordance with the invention, by characterizing a single period of a
repetitive pattern of states for the dynamic behavior of the data
communications network operating under the window-based protocol, the
overall throughput and other performance characteristics for the data
processing system can be determined. From an analysis of the resulting
computed throughput for the data processing system, changes can be made to
various operating parameters such as the departure rate for the queues,
the incremental change in window sizes as congestion thresholds are
reached, and other system parameters, one can optimize the throughput or
other performance characteristics for a data communications network.
FIGS. 1A-1M show a sequence of schematic diagrams of a data communications
network operating under a window-based protocol, as it achieves a periodic
repetition of the dynamic behavior for the system. FIG. 1A shows cycle 1
which is characterized by the state of variables for the window size W,
the maximum size obtained by the queue 30, which is Q1 and the maximum
size achieved by the second queue 34, which is Q2. In FIG. 1A, cycle 1 has
the state of W=2, Q1=0 and Q2=0.
In FIG. 1B, cycle 2 for the network starts when the marker associated with
the window's worth of packets transmitted during cycle 1 of FIG. 1A, is
received back on line 38 at the origin node 20. Since the threshold's
value V1 for the first queue 30 was not achieved, V1 is equal to zero and
since the threshold value for the second queue 34, was not achieved, V2 is
equal to zero. The threshold conditions V1 and V2 are fed back on line 44
to the window generator 28 of the origin node 20, along with the marker
response on line 38. Since V1 equals 0 and V2 equals 0 for cycle 1, the
window size for the window generator is incremented, in this example by
one data packet size. Thus it is seen that in FIG. 1B for cycle 2, the
value of W is 3. In cycle 2, packets from both the first window's worth of
data and the second window's worth of data bring the maximum queue size of
the first queue 30 up to one packet and also brings the maximum queue size
of the second window 35 up to one packet. Thus, the state for cycle 2 is
W=3, Q1=1 and Q2=1.
When the marker is received at the window generator 28 of the line 38 for
the second cycle, this initiates cycle 3 in FIG. 1C. Since the threshold
was not achieved for the first queue 30 in the second cycle, V1 equals 0
and since the threshold is not achieved for the second queue 34, V2 equals
0 in the second cycle. Thus, the window generator in cycle 3 adjusts the
window size to four packets and W equals 4. During the third cycle in FIG.
1C, the maximum accumulation of packets in the first queue 30 is two
packets, so Q1 equals 2 and the maximum accumulation of packets in the
second queue 34 is two packets, so Q2 equals 2. Since the threshold value
for both the queue 30 and queue 34 has been set equal to 6, neither queue
30 nor queue 34 achieve the threshold. Therefore, during cycle 3, the V1
equals 0 and V2 equals 0. The state for cycle 3 is W=4, Q1=2 and Q2=2.
In FIG. 1B, cycle 4 has the window generator receiving the marker on line
38 and receiving values of V1 equals 0 and V2 equals 2 on line 44 and
therefore the window generator 28 will increment the window size by one so
that W equals 5. During the interval of cycle 4, three packets accumulate
in the first queue 30 and therefore Q1 equals 3 and four packets
accumulate in the second queue 34 and thus Q2 equals 4. The state for
cycle 4 is W=5, Q1=3 and Q2=4.
FIG. 1E shows cycle 5 in which a marker is received on line 38 initiating
cycle 5 and values of V1 equals 0 and V2 equals 0 are received from queue
30 and queue 34 during the previous cycle 4 on line 44. Thus, the window
generator 28 during cycle 5 increments the window size by one, resulting
in W equals 6 for cycle 5. During the interval of cycle 5, four packets
accumulate in the first queue 30 making Q1 equals 4 and six packets
accumulate in the second queue 34 making Q2 equal 6. During cycle 5, since
only four packets have accumulated in the first queue 30, V1 equals 0.
However, during cycle 5, since six packets have accumulated in the second
queue 34, this being the threshold value for second queue, V2 is equal to
1. The state for cycle 5 is W=6, Q1=4 and Q2=6.
At the beginning of cycle 6, the marker is received over the line 38 at the
window generator 28 and the value V1 equals 0 and the value V2 equals 1
are received over line 44. Since the value V2 equals 1, the threshold has
been reached for one of its queues in the communications link between the
origin 20 and the destination 24. In accordance with the window-based
protocol, the window generator 28 will not increment the size of the
window for cycle 6, but will decrement the current window size from the
value of W equals 6 to a new value of W equals 5 for cycle 6. During cycle
6, three packets accumulate in the first queue 30 since Q1 equals 3 and
six packets have accumulated in the second queue 34 so Q2 equals 6. Since
the threshold has not been reached for the first queue 30, V1 equals 0.
However, since the threshold has been reached for the second queue 34, V2
equals 1. The state for cycle 6 is W=5, Q1=3 and Q2=6.
In FIG. 1G, cycle 7 begins with the receipt of the marker on line 38 at the
window generator 28. The value V1 equals 0 and the value V2 equals 1, are
received from the state of the preceding cycle 6 and are applied on line
44 to the window generator 28. This will cause the window generator 28
during cycle 7 to decrement the size of the window from the existing cycle
5 which occurred in cycle 6 to a new size W equals 4 which will obtain
during cycle 7. During cycle 7, two packets accumulate in the first queue
30 so Q1 equals 2 and four packets accumulate in the second queue 34 and
thus Q2 will equal 4. Since the threshold is not exceeded for a first
queue 30 or the second queue 34 during cycle 7, both V1 and V2 will equal
0. The state for cycle 7 is thus W=4, Q1=2 and Q2=4.
Cycle 8 begins with the receipt of the marker on line 38 at the window
generator 28. The values of V1 equals 0 and V2 equals 0 which obtained
during cycle 7 are applied on line 44 to the window generator 28 at the
beginning of cycle 8. Since both V1 and V2 equal 0, the window-based
protocol will increment the current window size W equals 4 to a new window
size W equals 5 for cycle 8. During cycle 8, three packets accumulate in
the first queue 30 and therefore Q1 equals 3 and four packets accumulate
in the second queue 34 and therefore Q2 equals 4. Since the threshold is
not exceeded for either the first or the second queues, V1 and V2 are both
0 during cycle 8. The state for cycle 8 is W=5, Q1=3 and Q2=4.
In FIG. 1I, cycle 9 begins with the receipt of the marker on line 38 at the
window generator 28. The values for V1 and V2 which were generated during
cycle 8 are applied over line 44 to the window generator 28 and both
values are 0. Therefore, the window-based protocol increments the window
size from the value W equals 5 which obtained in cycle 8, to a new value W
equals 6 which will apply during cycle 9. During cycle 9, four packets
accumulate in the first queue 30 and therefore Q1 equals 4. However, six
packets accumulate in the second queue 34 making Q2 equal 6, which exceeds
the threshold for the second queue. Thus, V1 will equal 0 and V2 will
equal 1 during cycle 9. The state for cycle 9 is W=6, Q1=4 and Q2=6.
In FIG. 1J, cycle 10 begins with the receipt of the marker on line 38 of
the window generator 28. Since the value of V1 equals 0 and V2 equals 1
during the preceding cycle 9, these values applied on line 44 to the
window generator 28 at the beginning of cycle 10 will cause the window
generator to decrement the window size by one packet from the value of W
equals six which obtained during cycle 9, to a new value of W equals 5
which will obtain during cycle 10. During cycle 10, three packets will
accumulate in the first queue 30 and therefore Q1 equals 3 and six packets
will have accumulated in the second queue 34 and therefore Q2 equals six,
which exceeds the threshold value. Thus, V1 equals 0 and V2 equals 1
during cycle 10. The state for cycle 10 is W=5, Q1=3 and Q2=6.
In FIG. 1K, cycle 11 begins with the receipt of the marker on line 38 of
the window generator 28. The value of V1 equals 0 and V2 equals 1 which
obtained during cycle 10, are applied over line 44 to the window generator
28 at the beginning of cycle 11. This causes the window-based protocol to
reduce the window size from the preceding value W equals 5 which obtained
during cycle 10, to a new value of W equals 4 which will obtain during
cycle 11. During cycle 11, the two packets will accumulate in queue 30,
making Q1 equal 2 and four packets will accumulate in queue 34, making Q2
equal 4. Since neither queue exceeds its threshold value of 6, V1 equals 0
and V2 equals 0 during cycle 11. The state for cycle 11 is W=4, Q1=2 and
Q2=4.
In FIG. 1L, cycle 12 begins with the receipt of the marker on line 38 at
the window generator 28. The values of V1 equals 0 and V2 equals 0 which
were generated during cycle 11, are applied to the window generator 28 of
the line 44 at the beginning of cycle 12. Since both V1 equals 0 and V2
equals 0, the window-based protocol will increment the size of the window
from the value W equals 4 which obtained during cycle 11, to a value of W
equals 5 which will obtain during cycle 12. During cycle 12, three packets
accumulate in the queue 30 making Q1 equal to 3 and four packets
accumulate in the second queue 34 making Q2 equal 4. Since neither queue
has reached its threshold, V1 equals 0 and V2 equals 0 during cycle 12.
The state for cycle 12 is W=5, Q1=3 and Q2=4.
FIG. 1M shows cycle 13 which begins with the receipt of the marker on line
38 at the window generator 28. The values of V1 equals 0 and V2 equals 0
which were generated in cycle 12, are applied on line 44 to the window
generator 28 at the beginning of cycle 13. Since V1 equals 0 and V2 equals
0, the window-based protocol will increment the size of the window from
the value W equals 5 which obtained during cycle 12, to a value W equals 6
which will obtain during cycle 13. During cycle 13, four packets
accumulate in the first queue 30 making Q1 equal to 4 and six packets
accumulate in the second queue 34 making Q2 equal to 6, which exceeds its
threshold value. Therefore, V1 equals 0 and V2 equals 1 during cycle 13.
The state for cycle 13 is W=6, Q1=4 and Q2=6.
The states for the cycles 1-13 are recorded in the cycle state table shown
in FIG. 2. It can be seen that a pattern of periodic repetition of the
states occurs every four cycles, starting with cycle 4, the pattern
repeating again at cycle 8 and at cycle 12. In accordance with the
invention, by characterizing a single period of a repetitive pattern of
states for the dynamic behavior of a data communications network, the
behavior of subsequent cycles can be inferred. By determining from the
cyclic state table a period for repetitive pattern cycle times and window
sizes, the throughput and other performance characteristics for the
network can be predictive. In the example shown in FIGS. 1A-1M and FIG. 2,
beginning with cycle 12, the method of the invention will extrapolate for
another 57 periods of four cycles each to determine the overall duration
necessary to transmit a total of 10,000 packets. After having computed
this duration for 10,000 packets, the throughput for the network can be
determined as the ratio of packets per unit time. In addition, response
times and other performance characteristics for the transmission of 10,000
packets can be quickly determined.
The invention is a method for the efficient prediction of the dynamic
behavior of a data communications network running under a window-based
protocol. The typical data communications network includes a sending node
which sends a first window's worth of data packets during a first cycle on
a first communications link in the network to an intermediate node having
a queue. The queue outputs data packets at a departure rate on a second
communications link in the network to a destination node, and the
intermediate node further outputs queue size information during the first
cycle to the sending node. The destination node sends a marker to the
sending node indicating the receipt of data packets from the first
window's worth of data packets. The sending node then sends a second
window's worth of data packets during a second cycle in response to having
received the marker, the second window's worth of data packets having a
size controlled by the queue size information.
The inventive method efficiently predicts the dynamic behavior of the
communications network. The method includes the step of computing in a
data processor a first queue size information during the first cycle, from
the size of the first window's worth of data packets and the departure
rate of the queue. Then the method compares in the data processor the
first queue size information with a threshold queue size value. It then
computes in the data processor the size of the second window's worth of
data packets, from the size of the first window's worth and the result of
the comparing step. Then the method computes a first cycle time duration
of the first cycle necessary to transmit a data packet in the first
window's worth of data packets from the sending node to the destination
node and to transmit the marker from the destination node to the sending
node. At the end of the first stage, the method stores the size of the
first window's worth of data packets and the first cycle time in a table
in the data processor.
In the second stage, the method computes in the data processor a second
queue size information during the second cycle, from the size of the
second window's worth of data packets and the departure rate of the queue.
Then it compares in the data processor the second queue size information
with the threshold queue size value. The method then computes in the data
processor the size of the next window's worth of data packets, from the
size of the second window's worth and the result of the comparing step for
the second cycle. Then the method computes a second cycle time duration of
the second cycle necessary to transmit a data packet in the second
window's worth of data packets from the sending node to the destination
node and to transmit the marker from the destination node to the sending
node. Then the method stores the size of the second window's worth of data
packets and the second cycle time in the table in the data processor.
Finally, the method determines in the data processor from the table a
period for a repetitive pattern of the cycle times and the window sizes,
and from this, the method computes a throughput value and other
performance characteristics for the network from the cycle times in the
period.
In this manner, the performance of the data communications network
operating under a window-based protocol can be efficiently predicted and
modifications can then be quickly made to the parameters controlling
network behavior, to optimize the performance of the network.
FIG. 3 is a flow diagram of the invention. The flow diagram for the method
is shown in FIG. 3 and starts with step 100 in which a physical and
logical network path description is input. This information includes the
initial window size for the window generator 28, the threshold size for
the first queue 30 and for the second queue 34, and the departure rate for
packets output from the first queue 30 and the second queue 34.
The method then continues with step 102 in which the input information is
converted to delay values from deterministic equations. The flow diagram
of FIG. 3 describes in outline form, the pseudo code program instructions
shown in Table 1 which implement the method of the invention.
The flow diagram of FIG. 3 then proceeds to step 104 which calculates the
cycle time from the current cycle. Then the subroutine is called in step
106 to calculate queue delays. Then step 104 proceeds to step 108 to
calculate the queue size for each queue as the marker leaves that queue.
The subroutine 110 is then called to calculate the maximum upstream delay.
Reference should be made to the pseudo code program instructions in Table
1 for a further explanation of these steps.
Step 112 proceeds to step 114 which calculates response times for the
current cycle. Then the method proceeds to step 116 to remember the cycle
values for the next cycle. The method proceeds to step 118 where the
current cycle throughput is calculated. Then the method proceeds to 120 to
calculate the queue sizes with data from the previous cycles that will
impact the marker of the next cycle. Then the method proceeds to step 122
in which the window protocol entrance queue is calculated. This is the
adjustment of the window size in preparation for the next cycle, based
upon whether any of the queues have achieved their threshold value in the
current cycle.
Step 122 then proceeds to step 124 which makes an entry into the cycle
state table and which checks to see if a periodic pattern of cycle states
has been found. If no periodic pattern of cycle states has been found,
then step 124 proceeds to step 126 where the window size is adjusted in
preparation for the next cycle, in accordance with the window-based
protocol and the values of V1 and V2. Step 126 then proceeds to step 128
which increments the cycle counter and then the method returns to the
beginning of step 104 to begin the calculation for the next cycle.
If step 124 finds a periodic pattern for the repetition of states for the
cycles, then step 124 proceeds to step 130 to extrapolate for the
remaining number of periods necessary to transmit a total of 10,000 | | |
