Fishwick P.A. (editor) Handbook of Dynamic System Modeling
Подождите немного. Документ загружается.
10-2 Handbook of Dynamic System Modeling
System
Model
Executable
Configuration
OutputInput
FIGURE 10.1 Relationships among modeling and simulation elements.
Time advance
method
Time-stepped Discrete-event Time parallel
FIGURE 10.2 Time advance mechanisms.
Processor mode
Sequential Parallel Distributed
FIGURE 10.3 Simulation modes based on computation platforms.
10.1.2 Elements of Execution
Although simulation models are qualitatively different relative to each other, they share common under-
lying execution concepts (Tocher, 63). Essentially, the modeled entities need to be mapped on to suitable
execution units, and the actions of the execution units have to be driven in simulation time order (Pidd, 92).
A key design element in model execution is the time advance mechanism (Nance,81; Chandy, 89; Zeigler,
00), as illustrated in Figure 10.2. In the traditional time-stepped simulation method, time is advanced in
fixed increments, and the system state is updated synchronously at each increment. Discrete-event sim-
ulation method, on the other hand, evolves different parts of system state at their own timescales, using
the concept of events. Each event signals the specific instant in simulation time at which a particular part
of the system is to be updated. Yet another method that is less commonly used is called the time parallel
simulation, in which simulation time is partitioned into multiple segments, and each segment is executed
independently from each other. Initial state of one segment is reconciled with the ending state of its pre-
vious segment and the process is iterated until convergence is reached. Time parallel simulation differs
from time-stepped and discrete-event simulation methods in that time parallel simulation partitions the
simulation across the simulation time dimension, whereas the latter two methods partition the simulation
across the problem’s spatial dimension.
The next important element is whether the execution is performed using one processor or using
multiple processors, as shown in Figure 10.3.
Sequential simulation uses one processorfor its execution. Parallelsimulation can assume shared memory
or high-speed interconnects among multiple processors. Distributed simulation is performed on loosely
Model Execution 10-3
Execution unit type
Event-oriented Process-oriented Activity-scanning
FIGURE 10.4 Classical simulation unit types, also called simulation worldviews.
Large-scale modeling
Monolithic approach Federated approach
FIGURE 10.5 Approaches to simulating large-scale models/scenarios.
connected nodes, such as a cluster of workstations connected by a local network, or a geographically sepa-
rated set of servers connected over a wide area network. Sequential execution is by far the most commonly
used approach, primarily due to its simplicity of implementation and the availability of a large number of
simulation tools that run on a single processor. Parallel execution using multiple processors is used when
the execution speed needs to be increased and the model needs large amount of memory that cannot fit in
a single processor’s memory. Distributed execution employs multiple processors connected by a network
and that do not share memory. The key distinction between parallel and distributed execution is that the
former uses shared memory among processors while the latter executes on distributed memory platforms.
Another related element is the type of modeling framework (Balci, 88; Fishwick, 95; Banks, 96) used
to map modeled entities to simulation units, as categorized in Figure 10.4. Process-oriented views are
those that provide a full stack (thread) of context for each modeled entity, which typically results in more
readable, maintainable, and shorter descriptions of the models (Banks, 96; Perumalla, 98). In contrast,
the alternative event-oriented views are those that provide a bare-bones event-handler interface, for poten-
tially better runtime performance than process-oriented views, but that are more complex to develop and
maintain. Another simulation approach is called activity scanning in which execution of “a set of guarded
actions” is enabled via continual scanning of predicated guards that prefix each action. Actions associated
with the guards that evaluate to true are executed during each scan.
Finally, large-scale scenarios are developed and simulated using two distinct approaches, shown in
Figure 10.5. In a monolithic approach, all models are developed and instantiated in a single simulator
(sequential or parallel), and the entire scenario is configured and executed in the same simulator. In
a federated approach, on the other hand, different models spanning multiple simulators are used to
assemble a single scenario, and the simulators are integrated at runtime to exchange data across models
(Nicol, 96) and synchronize their execution. While the monolithic approach is simpler and efficient to
implement and use if all models are present in a single simulator, the federated approach is useful when
no single simulator exists that contains all the desired functionality and, consequently, multiple simulators
are needed to realize a large integrated scenario.
10.1.3 Execution Platforms
The most common environment for model execution is a desktop computer, which serves well for typical
models that are small in size. A dual-processor or quad-processor workstation (called symmetric shared
memory multiprocessor [SMP]) can be used to improve processing speed by employing parallel simulation
techniques based on shared memory communication across processors. Cluster of workstations connected
by local area network represents the next level of computation platform to leverage dozens of uniprocessor
10-4 Handbook of Dynamic System Modeling
and SMP workstations. The highest levels of execution performance are afforded by supercomputing
platforms containing hundreds to thousands of processors connected by fast processor interconnects.
In addition to these traditional simulation platforms, new nontraditional platforms are emerging that
offer better performance to cost ratios. These include field programmable gate arrays (FPGA), application-
specific integrated circuits (ASIC), and general purpose graphical processing units (GPGPU).
10.1.4 Generating Executables from Models
Models in general can be developed in various environments. Some of the most common forms are
library-based, language-based, and integrated development environment (IDE)-based. In a library-based
approach,runtime support is provided in the form of a library module that is linked into simulation model.
Models are written using the interface provided by the library (e.g.,process and event class hierarchies). The
model, for example, invokes execution primitives to help coordinate time advances and message exchanges.
Examples of library-based approach include Georgia Tech Time Warp (GTW) (Das, 94) and A Discrete
Event Simulation (ADEVS) (Nutaro, 93) packages. In a language-based approach, the model is written in
a high-level modeling language, and a compiler automatically transforms models into executable entities.
The compiler also generates the runtime loop to invoke the generated executable entity code in appropriate
order. Examples of language-based approach include Modelica and PARSEC (general purpose) (Bagrodia,
98), and telecommunications description language (TeD) (Perumalla, 98), VHDL, and Verilog (domain-
specific). In an IDE-based approach, an IDE presents a graphical interface to compose models from model
repositories, and transparently performs all the required translations and assemblage to execute the model.
Examples of IDE-based systems include Simulink, Cadence, and OPNET. Another category might include
single-use efforts commonly used to build simulators. Even spreadsheets such as Microsoft Excel can be
used to quickly code certain simulations. These are not discussed here.
The generation of an executable model in a typical modeling system based on a hypothetical modeling
language L is shown in Figure 10.6. A language-based approach uses such a translation system to generate
the model executable. An IDE-based approach hides much of the internal operation from the user, but the
internal operation roughly follows the language-based approach. A library-based approach can be viewed
as the bottom half of the language-based process. In Figure 10.6, for example, the C++ code is generated
by the user instead of by a separate translator.
A simulation language shields the user from details of simulation units (Nance, 93; Schriber, 74), and
provides domain-specific constructs. For example, a modeling language for telecommunication networks
provides network-specific constructs such as network packets and protocols, and shields the modeler from
Models
written in
L
LP & event
class interface
LP & event
class library
L-to-C
translator
C code
C compiler Executable
FIGURE 10.6 Illustration of how a hypothetical simulation language L is converted to an executable based on an
intermediate conversion to C++.
Model Execution 10-5
simulation concepts such as logical processes and timestamped events. The modeler simply describes the
model in the language constructs and then uses the compiler to generate equivalent simulation executable
code. A system based on an IDE goes a bit further and hides much more of the model execution details
from the modeler by performing compilation, linkage, and execution under the covers of the IDE.
Regardless of the approach, the fundamental units of simulation execution remain the same. These are
the time advance method, the types of execution units, and whether the execution is sequential or parallel.
Once a model is defined, it needs to be executed to compute the state of the system over time.
10.1.5 Executable Timelines
In model execution, there are generally three distinct time axes. The first corresponds to the physical time,
which is the time in the physical system that is being modeled (e.g., 10–11 pm on January 1990). The
second corresponds to the simulation time, which is a representation of the physical time for the purposes
of simulation (e.g., number of seconds since 10 pm of January 1990, represented in floating point values
in the range [0 ... 3600] corresponding to the simulated time period of the physical time). Finally, the
last axis corresponds to wallclock time, which is the elapsed real time during execution of the simulation,
as measured by a hardware clock (e.g., number of milliseconds of computer time during execution). For
each, the notions of time axis and time instant can be defined such that the time axis is the totally ordered
set of time instants along the corresponding timeline.
10.1.6 Pacing the Execution
Almost always, there is a one-to-one mapping from physical time to simulation time. In contrast, there
may or may not exist a specific relationship between simulation time and wallclock time. The mode
of simulation execution determines this particular relationship. In an as-fast-as-possible execution, the
simulation time is advanced as fast as computing speed can allow, unrelated to wallclock time. In real-time
execution, on the other hand, advances in simulation time are performed in lockstep with wallclock time,
such that one unit of simulation time is advanced exactly in one same unit of wallclock time. A variation of
real-time execution is scaled real-time execution, in which simulation time period is some constant factor
times an equivalent wallclock time period.
10.2 Time-Stepped Execution
By far the most commonly used mode of execution in scientific simulations is the time-stepped method.
Time-stepped simulation is schematically illustrated in Figure 10.7. The horizontal bars represent timelines
of each modeled entity, while the solid vertical lines represent points in simulation time at which the entities
are updated.
The time-step value (simulation time period between successive updates to the state) is determined
by model-specific means to ensure stability of numerical computation along with sufficient accuracy of
results. The pseudocode for a generic sequential time-stepped algorithm is shown in Figure 10.8. It consists
FIGURE 10.7 Schematic of a time-stepped simulation.
10-6 Handbook of Dynamic System Modeling
of a simple simulation loop which typically terminates when a certain simulation time is reached. Within
the loop, each iteration consists of advancing the state of the entire set of modeled entities by a time step.
The variable t
now
maintains the current simulation time, which is updated by time step in step 1.1. All
elements are advanced using their advance() method to the new simulation time. From the loop, it can
be seen that time-stepped execution is one of the easiest time advance methods to implement. Although
this simple algorithm uses a constant time step during the entire execution, variants to this algorithm exist
that vary the time step dynamically as permitted by the model.
10.2.1 Example: Heat Equation
We will illustrate the time-stepped algorithm using an example application. The application is a simulation
of the diffusion process, such as heat transfer, which is a well-studied problem and has many applications.
We will use the following one-dimensional version of the diffusion equation:
∂Q
∂t
= α
x
∂
2
Q
∂x
2
+β (10.1)
For discretization of this continuous function, the spatial dimension is discretized by partitioning the
space as a grid in the x dimension. Time is discretized into a grid with equidistant points, with the spacing
fixed for all grid elements. Within each time step, the processing per grid element i in the 1-D grid can
be performed by one of several known methods. In the following simple explicit method, q
n+1
i
is the
computed value of q
i
at time step n +1.
q
n+1
i
= q
n
i
+α
x
q
n
i−1
−2q
n
i
+q
n
i+1
x
2
+β (10.2)
This model can be executed to answer any of the several questions, such as (1) what is the value of a given
q
i
at some time t
n
, and (2) what is the distribution of all values of q at a given time t
n
. In the time-stepped
algorithm, the advance() method updates q
n
i
to q
n+1
i
using the preceding equation. Of course, the new
values are stored in temporary variables while all the values are updated, to correctly access the previous
values for neighbors.
10.2.2 Parallelizing Time-Stepped Execution
We now turn to the question of how the time-stepped execution could be parallelized. This turns out to be
quite easy. The sequential simulation loop of Figure 10.8 is modified to that in Figure 10.9. Grid elements
are mapped to different processors, and the simulation loop is executed on every processor. Data exchange
among neighboring grid elements is achieved by sending out a copy of the updated state to neighbors
via interprocessor messages. Synchronization across processors is obtained by invoking a barrier call at
the end of each time step, as shown in step 1.1 of the parallel algorithm. The barrier is a “flush barrier”
which ensures that all messages destined to a processor are delivered before the barrier call returns. The
use of the flush barrier ensures that all updates to neighboring grid elements from a previous iteration
are incorporated before moving on to the next iteration. Note that the update messages are sent to other
processors for only those grid elements that have neighbors outside their own processor.
1. While not end of simulation
/*Advance current simulation time*/
1.1 t
now
+=timestep
/*Advance all entities to next timestep*/
1.2 For all (i): advance(i, t
now
)
FIGURE 10.8 Time-stepped algorithm for sequential execution.
Model Execution 10-7
1. While not end of simulation
/*Synchronize with rest of processors to start the current timestep*/
1.1 flush-barrier()
/*Advance current simulation time*/
1.2 t
now
+=timestep
/*Advance all entities’state to next timestep*/
1.3 For all (i on this processor): advance(i, t
now
)
/*Send copy of new state to all neighboring entities*/
1.4 For all (i on this processor having off-processor neighbors): send(state(i),
neighbor-processors(i))
FIGURE 10.9 Time-stepped algorithm for parallel execution.
10.3 Discrete-Event Execution
10.3.1 Execution Method
In discrete-event simulation, the system behavior is modeled in terms of actions at discrete points along
the time axis. The evolution of the state of the system is fully expressed in terms of these actions. Each
action, typically, is expressed as an instantaneous change in the system state, with causal dependencies
among the actions. Thus, after effecting an instantaneous action, the model may dynamically determine a
new set of future actions which are affected by this action. Each action is called an event. Since these events
occur at discrete points in simulated time, this type of a simulation is called a discrete-event simulation.
Figure 10.10 shows a schematic of time advances occurring in discrete-event simulation. It illustrates
the staggered time instants for updates to entities. The horizontal bands represent the timelines of entities
in the model, and each vertical bar represents an event processed at a particular simulation time on an
entity. Owing to the fact that update times are staggered, and also owing to the fact that future updates
are scheduled while processing current updates, the simulation loop becomes slightly more complex than
time-stepped simulation loop. The discrete-event simulation loop is shown in Figure 10.11. Thesimulation
starts at time zero in step 1, and the entities are initialized in step 2, as part of which the entities schedule
their initial set of events into the future. The main simulation loop starts in step 3. A priority queue data
structure is used to store all scheduled events, such that the minimum timestamped event is always readily
available to be dequeued. In each iteration of the loop, the minimum timestamped event is deleted from
the event list. The event data structure contains the timestamp of the event along with the identity of the
entity for whom the event is scheduled. The event is presented to the corresponding entity to process. As
part of processing, the entity updates its state to the time of the event, and schedules new events, if any,
to other entities (or to itself). The entity provides an event handler that processes events presented to the
entity. Typically, there can be multiple event handlers per entity to handle different event types coming to
the entity. In the algorithm in Figure 10.11, a generic handler called process() is assumed for the entity.
Multiple event handlers can be added to the entity that are invoked within the process() method of that
entity based on the type of event received.
10.3.2 Example: ATM Multiplexer
To illustrate the discrete-event execution method, we will use an example from the domain of telecommu-
nications networks using asynchronous transfer mode (ATM) protocol. Consider a simple model shown
in Figure 10.12 of a nonpreemptive ATM multiplexer (Fujimoto, 95) containing a buffer of size B (i.e.,
can hold at most B ATM cells). Suppose we are interested in measuring the cell loss probability (i.e., what
fraction of incoming cells are to be discarded due to lack of space in buffer) and delay distributions on the
10-8 Handbook of Dynamic System Modeling
FIGURE 10.10 Schematic of updates in discrete-event simulation.
1. t
now
=0
2. For all entities (i) EventList. Insert(initial-event(i,dt
i
))
3. While EventList is not empty and t
now
< end time
/*Find the event with the earliest timestamp*/
3.1 E(i
min
,t
min
) =EventList.DeleteMin()
/*Move global simulation time to the time of this event*/
3.2 t
now
=t
min
/*Let the entity process the event*/
3.3 Entity(i
min
).process(E) /*This can schedule more events into EventList*/
FIGURE 10.11 Sequential discrete-event simulation algorithm.
Source 1
Source 2
Source n
Output cell stream
B
FIGURE 10.12 Schematic of a model of an ATM multiplexer.
queue (i.e., the amount of delay that each incoming cell experiences before being sent on output channel).
This system can be modeled using multiple entities. The multiplexer itself is modeled as an entity, con-
taining a model of the buffer and the output channel. One entity is used to model each ATM cell source.
Cell source entities send events to the multiplexer entity to signal arrival of ATM cells from the source to
the multiplexer on the corresponding input channel.
The state of the multiplexer entity is simplified in terms of four variables, as shown in Figure 10.13(a). All
variables are initialized to zeros. The qlen variable is used to keep track of the current buffer occupancy;
sent and lost are variables to accumulate statistics of the total number of cells transferred to the
output link and the total number of cells dropped because of a full buffer respectively. The array delays
measures the number of cells experiencing a given amount of delay, which in combination with the sent
counter gives the cell delay distribution. Two event handlers are used to model actions of the multiplexer
upon cell arrivals and departures. A cell arrival event occurs at the multiplexer entity to mark the arrival
Model Execution 10-9
Integer qlen;
Integer sent;
Integer lost;
Integer delays [B];
(a)
if qlen < B
delays[qlen]++;
qlen++;
else
lost++;
(b)
if qlen > 0
qlen--;
sent++;
send(cell);
(c)
FIGURE 10.13 Simple model of an ATM multiplexer. (a) State. (b) Cell arrival event handler. (c) Cell departure
event handler.
of a cell from a source to the multiplexer. A cell departure event is scheduled by the multiplexer entity to
signal the transfer of a cell from the buffer to the output channel.
The code associated with the event handler in the multiplexer is shown in Figure 10.13(b) for processing
a cell arrival event. If there is room in the buffer to add the cell, the qlen variable is incremented to
mark that one more cell is added to the queue. The cell delay distribution is updated by noting that one
more cell experienced a delay of qlen units of time. If there is no room to hold the new cell (i.e., the
buffer is full), the cell is recorded as dropped by incrementing the lost counter. A cell departure event is
scheduled by the multiplexer to periodically emit a cell, if there are any cells present in the buffer. The cell
emission is marked by decrementing the qlen variable and incrementing the sent counter. The actual
cell emission is performed in Figure 10.13(c) by sending a cell event on its output channel, which typically
gets forwarded to the entity, if any, that is mapped to the output channel.
10.3.3 Parallelizing Discrete-Event Execution
How can discrete-event execution be parallelized? In other words, how can multiple processors be used
to execute the same simulation such that it produces the same set of results as a sequential execution,
albeit faster. A rich body of literature exists to address this question, and multiple approaches have been
proposed (Fujimoto, 90b). In parallel simulation, model entities are mapped to different processors, and
events among entities are exchanged via interprocessor communication (e.g., using shared memory or
local area network). The crux of parallel discrete-event simulation (PDES) is the need to perform efficient
synchronization such that the results from the parallel execution are the same as those from an equivalent
sequential execution. This means that all events have to be processed in such a way that global timestamp
order of processing is maintained for all events. This is achieved by processing all events local to each
processor in strict order of nondecreasing timestamps and ensuring that no incoming events from other
processors arrive in simulation past. Broadly, there are two main categories of PDES. A classification is
shown in Figure 10.14. The main methods are (1) conservative parallel simulation and (2) optimistic
parallel simulation.
In conservative parallel simulation (Chandy, 89), at every processor, processing of the minimum times-
tamped local event is blocked until a guarantee is obtained that no event with a smaller timestamp will
later arrive from other processors. This blocking can introduce idle time at the processor but will ensure
that the event processing always strictly follows the timestamp order. Conservative parallel simulation,
however, is constrained by an application-defined limitation called lookahead (explained later) which is
necessary to permit concurrency.
Optimistic parallel simulation (Fujimoto, 90a) is an approach by which the same timestamp ordered
processing is ensured across all processors, but it is achieved as an asymptotic guarantee. In other words,
the system might violate the timestamp ordered processing guarantee at certain times during execution,
but uses corrective measures to undo the guarantee violations. Processors optimistically execute ahead and
process locally minimum timestamped events without having to wait for absolute guarantees from other
processors. When the other processors indeed end up generating lower timestamped events, the violation
of the order is detected and the processor undoes the incorrect part of the optimistic computation, and
resumes from the correct state.
10-10 Handbook of Dynamic System Modeling
Parallel/
distributed
execution
Conservative Optimistic Mixed mode
Asynchronous Synchronous State-saving
Reverse
computation
Unified
framework
FIGURE 10.14 Classification of common parallel/distributed execution techniques.
10.3.3.1 Conservative Parallel Execution
A fundamental problem with conservative parallel simulation is concerned with the concept of lookahead.
In the absence of the concept of lookahead, suppose any simulator that is processing an event with
timestamp T can generate another event, whose timestamp is also equal to T, to another simulator.
Moreover, this new event could be destined to any or all simulators. In such a scenario, to ensure timestamp-
ordered processing, it is clear that there is little concurrency among federates. Only the event with the
globally minimum timestamp in the entire system can be processed at its simulator, while all the rest of
the simulators necessarily have to stay idle. Essentially, this degenerates to sequential execution, albeit with
multiple simulators. Clearly, this is undesirable in interest of runtime performance. It becomes desirable
to uncover concurrency among simulators to avoid such serialization. The concept of lookahead is defined
to resolve this problem (Deelman, 01).
Lookahead is defined as the minimum increment in simulation time between an event and any new
events generated during processing of that event. When this lookahead is greater than zero at all simulators,
the parallel execution can experience concurrency. If the lookahead is zero for any federate (i.e., a simulator
can generate events with zero delay), then the entire simulation suffers from serial execution (discounting
unrelated events with equal timestamps at different simulators).
In simulation models, it is possible to extractlookahead by examining the minimum time for interactions
to occur among entities. For example, signal transmission delays could be used to compute minimum
propagation delays across the ATM source and multiplexer entities. In other models, it might be difficult
to extract nonzero lookahead. Lookahead extraction is a topic of much research, and unfortunately remains
a challenge in its generality.
A typical conservative parallel simulation algorithm is shown in Figure 10.15. A quantity called lbts,
short for lower bound on incoming timestamps, is used to keep track of the smallest timestamp on
events that can potentially arrive from other processors. If lbts equals infinity, it is clear that this loop
simply degenerates to the sequential simulation loop in Figure 10.15. The complexity of the conservative
algorithm is in the computation of lbts, in step 4.3.1. Assuming there are no events in transit in the
interprocessor messaging network, it is easy to compute lbts, which is simply the minimum among all
values passed to the compute-lbts() function by all processors. Once this value is computed, it should be
corrected to take into account the events in transit, if any, among processors. This final value can now be
used as the lower bound guarantee on incoming event timestamps, and the rest of the loop is a simple
variant of the sequential loop.
An example scenario of conservative execution is shown in Figure 10.16. Let us assume each entity is
mapped to a different processor, and consider the operation of the processor simulating the multiplexer
entity. Suppose the multiplexer has just processed its events until time 8 (i.e., t
now
=8). It now finds two
events D@9 and A@10 in its event list. To determine if D@9 can be processed, it needs to compute the
value of lbts and wait until lbts is at least 9. Assume that the modeler has specified a transmission
Model Execution 10-11
1. t
now
=0
2. lbts =0
3. For all entities (i mapped to this processor) EventList.Insert(initial-event(i,dt
i
))
4. While EventList is not empty and t
now
< end time
/*Query for the local event with the earliest timestamp*/
4.1 E(i
min
,t
min
) =EventList.PeekMin()
/*See if this event can indeed be processed safely*/
4.2 if(t
min
<=lbts)
/*Move global simulation time to the time of this event*/
4.2.1 t
now
=t
min
/*Let the entity process the event*/
4.2.2 Entity(i
min
).process(E) /*This can schedule more events into EventList*/
4.3 else /*Need to compute new guarantee of safe processing time*/
/*Compute globally safe lower bound on timestamps of incoming events*/
4.3.1 lbts =compute-lbts(t
min
+lookahead)
FIGURE 10.15 Conservative parallel discrete-event simulation algorithm.
Source 1
C@8 C@20
Source 2
C@22
C@5
Multiplexer
A@13A@10 D@12D@9 D@15 A@25D@18
FIGURE 10.16 Example scenario of a two-source multiplexer model. Sources send cell arrival events A@t to the
multiplexer, with a constant delay (lookahead) of 5 time units. Multiplexer schedules departure events D@t to itself
every 3 time units.
delay (lookahead) of five time units from the sources to the multiplexer (the minimum time it takes for a
cell to move from a source to the multiplexer). It is clear that the minimum timestamp on any cell arrival
from source 1 or source 2 would be at least 13 (8+5). Thus, lbts at the multiplexer would be computed as
13. This enables the multiplexer to process all local events upto time 13, which allows it to safely process its
events A@10 and D@12. Once the time reaches 13, this process repeats, by which a new lbts computation
is initiated to determine a new (updated) guarantee on incoming timestamps.
10.3.3.2 Optimistic Parallel Execution
In optimistic parallel execution, local events are processed without having to wait for lbts guarantees,
unlike conservative execution. Clearly, as a result, the system can sometimes find itself performing event
processing in incorrect timestamp order. For example, in the scenario given in Figure 10.16, suppose