Network Simulation via Hybrid System Modeling: A Time-Stepped Approach

Amogh Kavimandan^{†}, Wonsuck Lee^{‡}, Marina Thottan^{‡}, Anirudha Gokhale^{†}, and Ramesh Viswanathan^{‡} †Department of EECS, Vanderbilt University, Nashville, TN 37235 ‡Bell Laboratories, Lucent Technologies, Murray Hill, NJ 07920

Abstract— The ever increasing complexity of networks dramatically increases the challenges faced by service providers to analyze network behavior and (re)provision resources to support multiple complex distributed applications. Robust and accurate simulation tools are pivotal to this cause. The current state of the art in network modeling and simulation tools, namely, packet-based discrete event simulations and fluid models, are limited in that they are either applicable only to particular phases of the network’s dynamics or do not scale well to capture the behavior of immense or complex networks. The recently proposed hybrid system model for data communication networks shows promise in addressing these challenges. Based on the hybrid system modeling paradigm, this paper provides novel contributions to TCP network modeling and analysis/simulation of large scale networks. The salient distinguishing features of our approach include a new finite state machine model for a drop-tail queue, a new model for fast recovery/fast retransmit mode, a revised sending rate model, and an embedded time-out mode transition mechanism all of which employ a time-stepped solution method to solve the hybrid system network models. Our simulation results are consistent with well-known simulators, such as ns-2.

Index Terms— Data Communication Network, Network Simulation, TCP Traffic Modeling, Fluid Modeling, Hybrid Systems.

I. Introduction

C OMMUNICATION service providers use a variety

of tools including visualization, analysis and simulations to track the performance of their networks and (re)provision existing and new applications. For example, the Network Simulator ns-2 [?] is the most widely used packet-based simulation tool to understand network behavior. Simulators like ns-2 are based on discrete event simulation of per-packet behavior in the network. Although these simulators provide accurate analysis of network behavior, they have a number of shortcomings when applied to the networks of today and the future.

It is difficult to study heterogeneous and multilayered networks where they are made up of several layers starting with the physical layer on which are overlaid data link layers like ATM and MPLS followed by the internet protocols like TCP and IP. Existing techniques to analyze network behavior are typically restricted to individual layers. For example, simulators like ns-2 are particularly useful to analyze IP traffic. Thus, it is tedious and in many cases infeasible, with existing techniques, to determine the effect of disruptions at one layer on other layers of the network.

Another challenge includes networks of networks where the ever expanding size of the internet has given rise to a large collection of interconnected but independently administered networks that include both public and private networks. Analyzing the behavior of these networks requires accurately modeling the structure, policies and behavior of the networks while also scaling to the large size of the networks. Current state of the art in network analysis do not provide these capabilities.

As the scale of the network increases it becomes computationally infeasible to use sequential packetbased discrete event simulators to analyze the networks. Moreover, the storage requirements for the trace data generated by these simulations become cumbersome to manage and mine.

Addressing the challenges outlined above requires a new approach to analyzing network behavior where the computational requirements must be kept manageable.

Hybrid system models combine the strengths of continuous and discrete models. A system is modeled as a discrete event system at a coarse granularity where a discrete state transition occurs when certain guard conditions are met. Within each state, however, a system is modeled to evolve according to some continuous dynamics.

II. Survey of Work on Network Modeling &

Simulation

Simulation of data communication networks is instrumental to study the dynamics of the network under various conditions. Simulation studies are important and relevant to i) designing a new network, ii) evaluating the existing network, iii) performing stress test of a new communication protocol, and iv) testing network readiness to support a new service. Network modeling and simulation paradigms can be categorized into three mainstream approaches: packet-level models, flow-level models, and hybrid models.

Packet-level simulation has been the most widely accepted and used simulation methodology by the network simulation community. Packet-level simulators are based on event-logic driven simulation paradigm. For example, ns-2 [?], SSFNet [?] and JSim-INET [?], [?] fall into this category. Packet-level simulators keep track of all the individual packets in the network. Therefore, they offer highly accurate and detailed results; however, the computational complexity increases rapidly as the size of a network becomes large.

During the past decade fluid-level simulations have been studied extensively and continue to be researched actively. In the framework of a fluid models, a chunk of packets is modeled as a single continuous artifact, namely, a fluid. The dynamics of the network is then represented by a system of ordinary differential equations, which describe fluid rate changes inside the network. Most of the research efforts in this area [?], [?], [?], [?] have focused on modeling TCP protocols [?]. In this framework, the arrival and the loss of packets are often modeled as stochastic processes [?], [?]. The traffic source and queue dynamics constitute a system of equations which governs the TCP controlled data transfer over an IP network.

Recently, hybridization of the packet and the flow modeling approaches have been studied. Guo et. al. proposed the Time-stepped Hybrid Simulation (TSHS) [?] method to deal with the scalability issue faced by traditional packet-level discrete-event simulation methods. TSHS considers a chunk, grouped from the packets that are in the same time-step, as a unit entity. The packets in a chunk are assumed to be evenly spaced within the timestep. In order to identify any event, every node in the network is checked at every time-step. TSHS is capable of offering flexible choice in simulation fidelity based on the simulation abstraction level. With a slightly different objective, Gu et. al. studied the integration of a fluid model with a packet-level simulation to maintain both the performance advantage as well as providing details for selected packet traffic [?]. They proposed models that can account for the interaction between flow-based background TCP traffic and foreground packet-based traffic flows. Another approach called Time-Driven Fluid Simulation (TDFS) [?] models traffic nodes in a network as fluid servers which process workload continuously. In TDFS models, traffic sources may employ either continuous or discrete event models. Using TDFS framework, Yan et. al. studied a single class of traffic. They also proved that the discretization error does not depend on the network size but is determined by the length of the discretization interval used. TDFS can also be easily parallelized to improve computational performance. All the above mentioned hybrid approaches show promising avenues for network simulation but have not yet been used as an alternative to ns-2.

A newly proposed hybrid system modeling [?], which is different from the aforementioned hybridization approaches, describes continuous dynamic behavior of a network within an organized finite state machine (FSM) formalism. Bohacek et. al. proposed such a framework for data communication networks and studied various communication protocols using hybrid systems [?]. Bohacek et. al.’s work forms the groundwork for what we are reporting in this paper.

III. Hybrid Systems Modeling of TCP Networks

The hybrid system modeling approach for data communication network simulation is motivated by the drawbacks of the discrete-event driven packet level simulations and the flow-level simulations. Though the packet level simulators provide the most detailed network simulation, they often suffer from scalability issues. It is also difficult to analyze network performance related to network parameters, such as a certain combinations of link bandwidth in neighboring nodes and impact of queuing policies etc. The flow-level simulation models, on the other hand, statistically average quantities for better computational performance and are capable of providing information on network parameters and network performance relationship. However, the network dynamics for its entire duration is difficult to model naturally in the fluid modeling framework because discrete phase changes may be caused instantaneously by external events, such as a packet drop.

The hybrid system modeling approach [?] proposed by Bohacek et. al. effectively reduces the complexity of network simulations by using flow-level models in each state of the FSM description. Logic based events trigger transitions between states to capture the discrete nature of queue dynamics.

In this section, we describe the details of a hybrid system TCP network model we have developed. First, a mathematical model of network is presented. For a TCP network model, we focus on TCP New-Reno source, drop-tail queuing policy, and their interactions under FSM models. The models that differ from Bohacek et. al.’s work will be highlighted. Our solution method differs from Bohacek et. al.’s in that we use the timestepped solution method to solve the constructed hybrid system. This approach resembles the solution techniques used in TSHS [?].

A. Mathematical Model of a Network

Mathematically a network is a directed graph with positive real numbers assigned to each edge. Thus a communication network is a graph (N , L) where a set of vertices N denotes nodes and a set of edges L denotes a collection of links connecting two nodes. For instance, two nodes u ∈ N and v ∈ N are connected by a link l = l_{u,v} ∈ L. Three real positive numbers are assigned to each link l ∈ L, these are: bandwidth (link-rate), propagation delay, and maximum queue size. Let B^{l}, τ^{l}, and q_{max}^{l} denote the bandwidth, the propagation delay, and the maximum queue size of a link l, respectively. These three parameters characterize each link in a network. Before we discuss the relationships and the constraints imposed by these parameters, we first define what we mean by a flow.

Let F represent a set of flows. Each flow f ∈ F is associated with a source node u_{s} ∈ N and a destination node u_{d} ∈ N where f flows from u_{s} to u_{d}. We assume that flow f is generated and enters node u_{s} with an incoming rate a_{f} at a prescribed time t = t_{f}^{0}. Once the network is loaded with data flows, all or part of the links become path ways for data flows. A flow f on a link l can be quantified by a link-in-rate (a sending rate), s_{f}^{l}, and a link-out-rate (an arrival rate), a_{f}^{l}. Bohacek et. al. named s_{f}^{l} as l-link/f-flow transmission rate and a_{f}^{l} as l-link/f-flow arrival rate [?].

Note that we assume the source and the destination nodes are unchanged over time for a given flow f. However, intermediate nodes, that flow f passes through, may dynamically change in time but at a much slower scale compared to the data transmission rates. Hence network dynamics can be well defined on top of any flow path changes within network.

As discussed earlier our network model is characterized by the three parameters assigned on a link l. Bandwidth B^{l} imposes an upper bound on flow sending rate as follows:

∑_{f∈F} s_{f}^{l} ≤ B^{l},  ∀ l ∈ L .  (1)

Here s_{f}^{l} = s_{f}^{l}(t) is a dynamically evolving quantity.

A queue is a temporary storage for flows/packets and is utilized if the bandwidth of the out-bound link-rate is not enough to process the flow-rate from the in-bound link. Note that, in our model, a queue is associated with a link l ∈ L. q_{f}^{l} denotes the size of the flow f in the queue of a link l. Therefore, given the maximum capacity of the queue q_{max}^{l} of the link l, the following inequality should hold for all times.

∑_{f∈F} q_{f}^{l} ≤ q_{max}^{l},  ∀ l ∈ L .  (2)

Here q_{f}^{l} is also a function of time, i.e., q_{f}^{l} = q_{f}^{l}(t).

In general the transmission delay is composed of link propagation delay, processing delay, and queuing delay. Associated with each link l, we only consider a fixed propagation delay τ^{l} and a queuing delay q^{l}/B^{l} where q^{l} = ∑_{f∈F} q_{f}^{l}. For the sake of simplicity, we assume the processing delay is minimal compared to the other two terms.

Round-trip-time (RTT) is a measure of the current delay on a network or time elapsed to receive an acknowledgment packet (ACK) from the destination node. To compute RTT for a flow f, RT T_{f}, the queuing delay and the propagation delay of the original data packet plus the propagation delay of the ACK is considered. In other words, we ignore the queuing delay of the ACK from the destination node to the source node. If L_{f} is an ordered set of links that flow f takes on its way to the destination, RT T_{f} becomes

RT T_{f} = ∑_{f∈L_{f}}(2τ^{l} + \frac{q^{l}}{B^{l}}) .  (3)

Here RT T_{f} and q^{l} are functions of the time variable t and the coefficient 2 in front of τ^{l} accounts for propagation delay of the original packet and the ACK. We note that RT T_{f}(t) is the estimation of RTT at certain time t. In a real system a packet sent at time t may experience queuing delay different from q^{l}(t)/B^{l} at the link l since the packet will exit link l at a certain time past t.

TCP protocol [?] ensures fair management of network resources. Modeling TCP protocols has been our first goal since not only is a significant portion of internet traffic controlled by the TCP protocol but also it potentially possesses rich dynamics due to the concept of varying the sending rate in response to the network conditions. In the following subsection we focus on TCP-New Reno policy, other TPC variants can be modeled in similar manner with minor changes in some of the modes.

B. Source Dynamics

In the following subsection, we revisit Bohacek et. al.’s hybrid TCP source model [?]. A new model for fr/fr mode is introduced along with a more accurate sending rate formula. Transition to time-out mode is naturally embedded without further modeling effort. We start with the continuous time (CT) domain model of slow-start mode. Note that our primary unknown in CT domain of source dynamics is the congestion window size. The sending rate is a derived quantity from the congestion window size variable.

1) Slow-Start: The congestion window size w_{f} of a given flow f ∈ F is governed by the following ordinary differential equation:

w′_{f}(t) = \frac{log m_{ss}}{RT T_{f}(t)}w_{f}(t) ,  (4)

where ′ denotes the time derivative d/dt, m_{ss} is a multiplicative constant such that w_{f} is being multiplied by m_{ss} every RTT, and RT T_{f} is computed from Eqn. (??). w_{f} is initialized to 1 whenever the source enters slowstart mode. Hence, in slow-start CT domain we solve the initial value ODE problem. Derivation of Eqn. (??) is given in the Appendix section.

In TCP flow control w_{f} is used to limit the number of packets to be sent out from the sender. Because the sender is able to send more packets only when the ACKs arrive, effectively, only w_{f} number of packets are sent in RT T_{f} time window. With the assumption that the packets (or flow f) are sent over RT T_{f} period with evenly spaced pattern, the instantaneous sending rate s_{f} should be

s_{f}(t) = \frac{w_{f}(t)}{RT T_{f}(t)} .  (5)

Here we should note that the evenly spaced packets over RT T_{f} time period is a rather strong assumption. It may be a good model when traffic flow is up and running for some time so that ACKs become spread over time due to a certain random process. However, when traffic is at its early stage, like the very first slow-start mode, TCP tends to burst out traffic. In such cases the sending rate model, Eqn. (??) might be poor. We revisit this question in the discussion section.

Bohacek et. al. used an artificial coefficient β to adjust the sending rate formula as follows:

s_{f}(t) = \frac{βw_{f}(t)}{RT T_{f}(t)} ,  (6)

where β = 1.45 is obtained from the trace comparison against ns-2 simulation. However, we argue that it might be an artifact from the hybrid simulation paradigm employed in Bohacek et. al.’s paper [?]. In the discussion section we will show how a CT-FSM (i.e. hybrid) model may introduce this error by deducing the value of β based on certain assumptions.

Though the congestion window size evolves with Eqn (??) within the slow-start CT domain, w_{f} should not grow over the advertised maximum window size w_{f}^{adv}, which is assigned to the source host by the destination host at the initial hand-shake stage. Therefore we use Eqn. (??) with a slight modification. The model we use for instantaneous flow sending rate is

s_{f}(t) = \frac{max \{w_{f}(t), w_{f}^{adv}\}}{RT T_{f}(t)}.  (7)

2) Congestion Avoidance: Congestion avoidance mode increases congestion window size much more cautiously. During the congestion avoidance mode every ACK increases congestion window size by a small portion of the current window size,

w_{f}^{new} = w_{f}^{old} + \frac{L}{w_{f}^{old}} ,  (8)

where L is a real positive number (normally L = 1). Since w_{f} packets are sent every RTT, if the congestion avoidance mode is maintained during this time window, w_{f} packets will be returned. Therefore w_{f} is increased by 1 every RTT if L = 1. The ODE model that governs the congestion window size evolution in the congestion avoidance mode is

w′_{f}(t) = \frac{L}{RT T_{f}(t)} .  (9)

It is straight forward to deduce Eqn. (??), see the Appendix.

The model shows a linear increase of congestion window size in congestion avoidance mode as long as no drop is detected and w_{f} ≤ w_{f}^{max} is satisfied. Occurrence of dupACKs or no ACK ends the congestion avoidance mode and is followed by fr/fr or time-outs. 3) Fast Recovery/Fast Retransmit:

In TCP-New Reno policy fr/fr mode is initiated whenever the sender receives triple dupACKs. These dupACKs do not increase the congestion window size in real TCP flow control. Therefore, it is not accurate if the state remains at either slow-start or congestion avoidance mode since they are governed by their own dynamic discipline which evolves the congestion window size in time.

In order to model congestion window evolution correctly over the state transition, the source should enter fr/fr once a drop is detected. However the actual transition should be delayed by the right amount of time to account for elapsed time between the drop event and the arrival of dupACKs in the real system.

Since each dupACK increases w_{f} by 1, the speed of window size increments is the same as that in the slowstart mode, i.e., an exponential increase, unless there is a drop. Hence Eqn. (??) might well be applied as long as no drop occurs. However, in a real packet network a packet drop is usually followed by another drop because it takes a certain amount of time to send buffered packets out onto the out-bound link from a congested queue. In that event, a hybrid system may experience too many state transitions in a short time epoch and the model becomes inefficient.

To overcome this modeling difficulty within the hybrid system framework, we propose an algebraic model for fr/fr mode. Along with it we provide a formula for the duration of fr/fr mode.

Let w_{f}^{−} be the congestion window size of flow f just before the source enters fr/fr mode and t_{0}^{fr} be the time when the source mode becomes fr/fr. Suppose a_{f}^{D}(t) is the instantaneous arrival rate of flow f at destination node D at time t, ζ(t) is size of outstanding flow at time t and ack(t) is the acknowledged flow size since t = t_{0}^{fr}. Then we have following relations,

ack(t) = ∫_{t_{0}^{fr}}^{t} a_{f}^{D}(t′ − RT T_{f}/2) dt′ ,
ζ(t) = (w_{f}^{−} − w_{f}(t_{0}^{fr} − RT T_{f})) + η(t) − H(t) ,

(10)

for t ≥ t_{0}^{fr}. Here (w_{f}^{−} − w_{f}(t_{0}^{fr} − RT T_{f})) represents the initial outstanding flow size when the source enters fr/fr, η(t) denotes size of flow newly transmitted since the initiation of fr/fr mode. If there is no drop in [t − RT T_{f}(t), t], H(t) is equal to ack(t). Otherwise, if the source learns about the drop at t_{drop} ≤ t, H returns the value of ack(t′) provided no drop is detected in time period of [t′ − RT T_{f}(t′), t′] for t′ ≤ t_{drop}. Hence, function H does not count dupACKs in the events of drop during fr/fr mode. We remark that ζ approximates the outstanding flow size for the drop-tail queuing policy.

In fr/fr mode every ACK (either normal ACK or dupACK) increases the congestion window by 1 so the model for congestion window evolution is

w_{f}(t) = w_{f}^{−}/2 + ack(t) .  (11)

The instantaneous sending rate is different from Eqn. (??) since we do not allow the drop event to trigger state transition. Our flow sending rate model is

s_{f}(t) = \frac{max \{(w_{f}(t) − ζ(t)), w_{f}^{adv}\}}{RT T_{f}(t)}. (12)

Let n_{f}^{drop} be the cumulated flow size that are lost during the transmission. The increment of n_{f}^{drop} is then given by

n_{f}^{drop}(t) = ∫_{t_{0}^{fr}}^{t} d_{f}(t′) dt′ ,  (13)

where d_{f} is a drop rate which will be discussed in detail in the next section, Sec. ??. Since TCP New-Reno only retransmits one probably-lost packet at one RTT, the decrement of n_{f}^{drop} is 1 at every RTT unless all the flow sent were lost. In the event of total loss n_{f}^{drop} should not be decreased. More precisely, for every RT T_{f}, if ack(t) ≠ ack(t − RT T_{f}), n_{f}^{drop} should be decreased as follows:

n_{f}^{drop}(t) = n_{f}^{drop}(t − RT T_{f}) − 1 .  (14)

Here ack(t) ≠ ack(t − RT T_{f}) ensures that not all the flows were dropped during time interval of [t−RT T_{f}, t].

In our TCP New-Reno implementation, the source exits fr/fr mode if n_{f}^{drop} becomes 0. Other TCP variants should differ in fr/fr dynamic behavior and the duration of fr/fr. For example, TCP Reno policy exits as soon as the fast retransmit of the first lost packet is successful. If two packets were dropped, another fr/fr mode follows immediately after the recovery (fr/fr mode) of the first lost packet. Therefore, multiple packet losses might lead the source mode to time-out by multiple steps of halving the congestion window size.

4) Time-out: In our implementation, whenever a drop is detected, the source enters fr/fr. In fr/fr, if ACKs cease to return, the congestion window stays at a constant value and the number of outstanding packets is not decreased resulting in no new packets being sent for some time period.

Let t_{out} be a timer which is set to 0 when the source enters fr/fr. t_{out} keeps on increasing with the simulation clock. If t_{out} exceeds the given time-out period, say, RT O, then the source enters slow-start mode with w_{f} = 1 and ssthr = w_{f}^{−}/2. Note that if time-out occurs in the simulation, the fr/fr state entered exhibits no effect on congestion window dynamics because no new packets were sent and no ACKs were received by the sender.

C. Queue Dynamics

Suppose ω and ν are in-bound (west) and out-bound (east) links, respectively, in the traffic path of a flow f. Let F_{α} be a set of such flows sharing the links ω and ν. We have the following equation describing the queue changing rate

\frac{d}{dt}q_{f}^{ω} = a_{f}^{ω} − s_{f}^{ν} − d_{f}^{ω} ,  (15)

where q_{f}^{ω} is the size of flow f buffered at q^{ω}. a_{f}^{ω} is flow arrival rate from the link ω. s_{f}^{ν} denote flow sending rate into the link ν.

Suppose there is no packet loss during transmission over the links in a network, then incoming flow into a link ω must all exit from that link, that is, a_{f}^{ω}(t) = s_{f}^{ω}(t − τ_{ω}) where τ_{ω} is the link propagation delay. Here s_{f}^{ω}(t − τ_{ω}) is readily available at time t.

Let q_{max}^{ω} represent maximum queue size associated with the in-bound link ω. B^{ν} (B^{ω}) is a given fixed bandwidth of the link ν (ω).

Bohacek et. al. determined the values of s_{f}^{ν} and d_{f}^{ω} based on queue state. In their model, the FSM for a queue consists of three states, they are:

• Empty queue (q^{ω} = 0)

d_{f}^{ω} = 0, s_{f}^{ν} = \{ \begin{matrix}a_{f}^{ω} ∑_{f̄∈F_{α}} aω ; f̄ ≤ B^{ω} \\ a_{f}^{ω}B^{ω}/(∑_{f̄∈F_{α}} aω ; f̄) \end{matrix} (16)

• Queue neither empty nor full (0 < q^{ω} < q_{max}^{ω} or

q^{ω} = q_{max}^{ω} but ∑_{f̄∈F_{α}} aω ; f̄ ≤ B^{ω})

d_{f}^{ω} = 0, s_{f}^{ν} = \frac{q_{f}^{ω}}{∑_{f̄∈F_{α}} q_{f}^{ω}} B^{ν}  (17)

• Queue full and still filling (q^{ω} = q_{max}^{ω} and

∑_{f̄∈F_{α}} aω ; f̄ > B^{ω})

d_{f}^{ω} = \frac{a_{f}^{ω}(∑_{f̄∈F_{α}} aω ; f̄ − B_{ω})}{∑_{f̄∈F_{α}} aω ; f̄}, s_{f}^{ν} = \frac{q_{f}^{ω}}{∑_{f̄∈F_{α}} q_{f}^{ω}} B^{ν}

(18)

There are two assumptions made to obtain the above queue model. They are, i) packet arrival rate does not change rapidly and is assumed to be constant in a short time interval, namely, Arrival Uniformity ii) packets of different flows are uniformly distributed, Queue Uniformity.

The governing equation (??) of the queue size and the finite queue state description (??) - (??) is a mathematically well-defined hybrid system. However, the number of state transitions can be numerous specially if q^{ω} ≈ q_{max}^{ω} to detect zero-crossing for the state transition [?] in the hybrid system. Furthermore, a large system of ODE for q_{f}^{ω} for all f ∈ F_{α} needs to be solved.

In fact, to find q_{f}^{ω}(t) from the previously known queue size q_{f}^{ω}(t_{0}) for t_{0} < t, all that is required is the net increase of queue size. If we do not impose q_{f}^{ω} ≤ q_{max}^{ω}, we have

q_{f}^{ω}(t) = q_{f}^{ω}(t_{0}) + ∫_{t_{0}}^{t}(a_{f}^{ω}(t′) − s_{f}^{ν}(t′)) dt′  (19)

It is simply an integral form of Eqn. (??) without the drop term. Here s_{f}^{ν} is the sending rate into the link ν, i.e., the sending rate from the q^{ω}.

We now discuss our queue model. Unlike Bohacek et. al.’s model, the states are not determined by the queue size q_{f}^{ω}. Rather they depend on the bandwidth of the outbound link, B^{ν}, and the size of the arriving and departing packet. For the flow sending s_{f}^{ν}, we have,

s_{f}^{ν} = \{ \begin{matrix}\frac{q_{f}^{ω}}{∑_{f̄∈Fα} q_{f}^{ω}} , if ∑_{f̄∈F_{α}} q_{f}^{ω} ≥ B^{ω} \\ a_{f}^{ω} + q_{f}^{ω}, if ∑_{f̄∈F_{α}}(a_{f}^{ω} + q_{f}^{ω}) ≤ B^{ω} \\ q_{f}^{ω} + \frac{a_{f}^{ω}}{∑_{f̄∈Fα} a_{f}^{ω}} (B^{ω} − ∑_{f̄∈F_{α}} q_{f}^{ω}), o.w. \end{matrix}

(20)

Equations (??) and (??) completely describe the queue size and the flow sending rate changes in time. However, the sum of solutions ∑ q_{f}^{ω} may be greater than q_{max}^{ω} which should be understood as buffer overflow or flow drop.

The drop model should describe which flows suffer losses at the time a drop occurs. For example, one can drop a larger flow first or vice versa. A probability distribution p(f) may be used to select a flow to drop, for instance, p(f) can be

p(f) = \frac{a_{f}^{ω}}{∑_{f̄∈F_{α}} aω ; f̄} .  (21)

Another question is, if a flow is decided to be dropped, what is the right size of the flow that should be dropped. We propose the following model. Let D_{f}^{ω}(t) denote the size of dropped flow f, we model D_{f}^{ω}(t) as,

D_{f}^{ω}(t) = max \{0, ⌈\frac{a_{f}^{ω} (∑_{f̄∈F_{α}} qω ; f̄(t) − q_{max}^{ω})}{∑_{f̄∈F_{α}} aω ; f̄}⌉\}

(22)

Eqns. (??) - (??) are not entirely different from the Eqn. (??) and Eqns. (??) - (??). Eqns. (??) - (??) take an integral form and s_{f}^{ν} is based on packet arrival rate a_{f}^{ω} and queue size q_{f}^{ω} instead of the queue state. Note that Bohacek et. al.’s drop rate d_{f}^{ω} is determined by queue state only, however, in our model, the value of the drop size (??) is a deduced quantity.

D. Solution Techniques

In this section we describe the solution method and the algorithm used for our network simulation approach. We have created the simulator without relying on any existing simulation frameworks, such as, Stateflow/Simulink [?], Modelica [?], Ptolemy [?], [?] etc. There are certain disadvantages, mostly the amount of work required throughout the development cycle, however, we possess full control of the whole system including the solution method of the hybrid system, numerical scheme to be used in CT domain, and scope of component model. Furthermore, it is easy to identify any computational bottleneck and the sources of inaccuracy in the model specific to the implementation.

First, we take a closer look at the system we have constructed in the previous sections from CT-FSM point of view. In general FSM is not a timed model, however, its composition with CT domain requires detection of any events that may be triggered on the time axis. Each state in FSM is being refined during the continuous evolution of the sources and the queues in our model. At each time abscissa, which may be a priori chosen or dynamically updated, active states are evaluated. If the state transition condition is enabled, then the FSM makes corresponding transitions according to the condition and the system continues to evolve. The details of our solution technique are described next.

Assume that CT-FSM composition refers a master clock for their time. Consider one tick of that master clock to be the time step Δt of our hybrid system simulation. It is trivial that a smaller Δt introduces small error in state transition. In our simulation, we do not allow FSM state transitions during an epoch of length Δt. Now, CT domain simulation can be performed as accurately as possible, say, over an interval [nΔt, (n+1)Δt] where n = 0, 1, . . .. At each time point, nΔt, current states are evaluated, checked against transition enablers, and changes are made to the states, as necessary. The tasks described above can be summarized in the following algorithm.

Algorithm for the Hybrid Simulation

Input:

- A network (N , L),

- Bandwidth of all the links l ∈ L,

- Maximum queue size at all the queues,

- Set of source nodes S,

- Set of destination nodes D,

- Source wake up time and interval,

- Time-step h,

- End of simulation time T_{end}.

Construct L_{f} for each f ∈ F Set t = 0 while t ≤ T_{end} do

t = t + h Wake-up sources as scheduled Solve equations for all s ∈ S and q ∈ N for all s ∈ S do

switch mode(s): case (mode(s)=slow start):

if cwnd(s) ≥ ssthr then

mode(s) ⟶^{t+delay} c.a. else if flow f from s suffer drop then

mode(s) ⟶^{t+delay} fr/fr else

remain in slow start mode case (mode(s)=fr/fr): if n_{f}^{drop} = 0 then

mode(s) ⟶^{t} c.a.

else

remain in fr/fr case (mode(s)=c.a.):

if flow f from s suffer drop then

mode(s) ⟶^{t+delay} fr/fr else

remain in c.a. end for for all queue do

evaluate and set queue state for the next iteration end for

end while

Now we comment on a numerical scheme for Eqns. (??) - (??) which describes dynamics of the congestion window evolution. We have, in their general form,

w′ = g(t, w), w(0) = w_{0}

where w_{0} is given.

It is well known that Euler’s method [?] is not practical due to the requirements of small step size for reasonably accurate numerical solutions. Runge-Kutta methods do not require higher order derivative by evaluating g(t, w) at selected points on each interval of computation. Higher order methods can be obtained by paying extra for the evaluation of g. For example, Runge-Kutta method of order 2 employs the following recursive formula:

w_{n+1} = w_{n} + \frac{1}{2}(k_{1} + k_{2}),
where k_{1} = hg(t_{n}, w_{n}),
k_{2} = hg(t_{n} + h, w_{n} + k_{1}) .

Here t_{n} = nh and w_{n} = w(t_{n}). The local error of this method is of order h^{3} while Euler’s method is of order h^{2}. Henceforth, we can use larger step size or save computation time with higher order numerical scheme. As one might expect, in terms of computational efficiency, we found that the larger the hybrid simulation time step, the better it is with a higher order method.

Finally, we remark that the proposed solution approach is somewhat similar to the Time-stepped Hybrid Simulation (TSHS) [?] and shares the idea of packet smoothing, however, the concept of hybrid system of CT-FSM composition is fundamentally different from TSHS.

IV. Hybrid Model & Simulation Validation

A. Simulation Set Up & Environment

Our simulation studies are comprised of multiple experiments using the packet-based ns-2 simulator and the