[Docs] [txt|pdf] [Tracker] [Email] [Nits]

Versions: 00

Differentiated Services Working Group                     G. Mercankosk
Internet Draft                                               Australian
Expires January 2001                                 Telecommunications
                                                                    CRC
Document: draft-mercankosk-diffserv-pdb-vw-00.txt             July 2000
Category: Informational


     The Virtual Wire Per Domain behavior _ Analysis and Extensions
                draft-mercankosk-diffserv-pdb-vw-00.txt


Status of this Memo

   This document is an Internet-Draft and is in full conformance with
   all provisions of Section 10 of RFC2026 [1]. Internet-Drafts are
   working documents of the Internet Engineering Task Force (IETF), its
   areas, and its working groups. Note that other groups may also
   distribute working documents as Internet-Drafts.

   Internet-Drafts are draft documents valid for a maximum of six
   months and may be updated, replaced, or obsoleted by other documents
   at any time. It is inappropriate to use Internet-Drafts as reference
   material or to cite them other than as "work in progress."

   The list of current Internet-Drafts can be accessed at
   http://www.ietf.org/ietf/1id-abstracts.txt
   The list of Internet-Draft Shadow Directories can be accessed at
   http://www.ietf.org/shadow.html.

   Distribution of this memo is unlimited.

Abstract

   This document provides an analysis of the Virtual Wire Per Domain
   Behavior with limited extensions.

   The draft formalizes a model for the PDB by explicitly identifying
   key timing and decision variables and associated design parameters.
   It derives the necessary and sufficient conditions for creating and
   establishing a Virtual Wire flow. It provides methods for
   quantifying design parameters and setting decision parameters and
   discusses their extensions to incorporate variations in traffic
   characteristics.

   A pdf version of this document is available at
   http://www.ee.uwa.edu.au/~guven/vwpdb.pdf








Mercankosk             Informational - Jan 2001                      1
                 Virtual Wire - Analysis & Extensions        July 2000

1. Introduction

   The document [3] describes a Differentiated Services (diffserv or
   DS) Per Hop Behavior (PHB) called Expedited Forwarding (EF) intended
   for use in building a scalable edge-to-edge service that appears to
   the end points like an un-shared, point-to-point connection or
   `Virtual Wire.' For scalability, a DS-domain supplying this service
   must be completely unaware of the individual end points using it,
   except for routing purposes, and sees only the aggregate EF marked
   traffic entering and traversing the domain.

   The document [4] provides a set of specifications necessary on the
   aggregate traffic (in DS terminology, a Per Domain Behavior or PDB)
   in order to meet these requirements and thus defines a new PDB, the
   `Virtual Wire' PDB of some fixed capacity. It does not require `per-
   flow' state to exist anywhere other than the ingress and egress
   routers. Despite the lack of per-flow state, if the aggregate input
   rates are appropriately policed and the EF service rates on interior
   links are appropriately configured, the edge-to-edge service
   supplied by the DS-domain will be indistinguishable from that
   supplied by a dedicated wire between the end points.

   This document provides an analysis of `Virtual Wire' PDB with
   limited extensions. "The same as a dedicated wire," means that as
   long as packets are sourced at a rate less than or equal to the
   virtual wire's configured rate, they will be delivered with a high
   degree of assurance and with no distortion (apart from line clock
   jitter) of the inter-packet timing imposed by the source. However,
   any packet sourced at a rate greater than the virtual wire's
   configured rate will either be unconditionally discarded or spaced
   to conform with the configured rate. In the latter case, the packets
   will be delivered with inter-packet timing imposed by the spacer.

   This draft formalizes a model for the `Virtual Wire' PDB by
   explicitly identifying key timing and decision variables and
   associated design parameters. It derives the necessary and
   sufficient conditions for creating and establishing a `Virtual Wire'
   flow. It provides methods for quantifying design parameters and
   setting decision parameters and discusses their extensions to
   incorporate variations in traffic characteristics.

   In this document, we distinguish between the transfer delay over a
   DS-domain and edge-to-edge service delay. We provide a
   characterization of the transfer delay bound based on established
   results. We argue that the issue of non-EF traffic starvation does
   not exist even when priority queueing is deployed. We point out that
   the presence of non-EF micro flows does not necessitate additional
   bandwidth resources. We determine a conservative expected time to
   the first failure of a `Virtual Wire.' We discuss the impact of
   heterogeneous packet lengths on the transfer delay bound.

   This document provides a synthesis of various methods in delivering
   a particular but versatile solution. The issue of scalability, the


Mercankosk             Informational - Jan 2001                      2
                 Virtual Wire - Analysis & Extensions        July 2000

   edge-to-edge service characteristics and a simple management of DS-
   domain provide the basis for the presented solution.

   The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
   "SHOULD", "SHOULD NOT", "RECOMMENDED",  "MAY", and "OPTIONAL" in
   this document are to be interpreted as described in RFC-2119 [2].


2. Description of Virtual Wire PDB with extensions

   Figure 1: An illustration of virtual wire transfer over a DS-domain

   An illustration of the model of a Virtual Wire transfer over a DS-
   domain is given in Figure 1. At the ingress end of the micro flow,
   the model contains an ingress link (S to I) and a DS-domain ingress
   border router (at I). Over the DS-domain (I to E), the packets from
   the micro flow are subject to random delays, according to EF-PHB
   service. At the egress end of the flow, the remaining components of
   the model are a DS-domain egress border router (at E) and an egress
   link (E to D). The ingress link and the egress link are assumed to
   run at the same constant rate as the virtual wire rate R with
   negligible line clock jitter.

   2.1  Ingress edge of DS-domain

   A periodic flow of packets of size S is sourced at a rate R on the
   ingress link. Accordingly, one packet is presented at the DS-domain
   ingress border router in every T=S/R time units. The number of
   complete packets that are in transit in the DS-domain at time t is
   denoted by N_DS(t). Without loss of generality, we choose the time
   origin such that the last bit of the first packet presented at the
   ingress border router is at time T. Let t_k represent the time at
   which the last bit of the kth packet is presented to the DS-domain
   at the ingress border router, then

   (1) t_k = kT.

   2.2  Over the DS-domain

   Once a packet that belongs to a micro flow is presented at the
   ingress border router, it hops from one EF router to another along
   its path over the DS-domain before reaching the egress border
   router. There are two main components for the delay experienced by a
   packet over the DS-domain, namely the propagation delay and the
   queueing delay. The propagation delay refers to the time it would
   take for a packet to traverse through the DS-domain if the packet
   experienced no queueing delay along its path. Accordingly, the
   propagation delay, d_p, is fixed and includes the time necessary to
   process a packet at routers. Let d_k denote the total queueing delay
   experienced by the kth packet along its path. It is assumed that the
   queueing delay experienced by each packet of a micro flow over the
   DS-domain is statistically bounded by a known value, D, that is

   (2) 0 <= d_k < D

Mercankosk             Informational - Jan 2001                      3
                 Virtual Wire - Analysis & Extensions        July 2000


   The value, D, can be obtained by some (1-alpha) quantile of the
   total queueing delay. Note that the value D refers to the difference
   between the best and the worst case expectation of the packet
   transfer delay. The best case is equal to d_p and the worst case is
   equal to d_p + D, a value likely to be exceeded with a probability
   less than alpha. Therefore, the value D is a measure of variation of
   the delay distribution and may be referred to as expected maximum
   jitter.

   At a given EF-router, let C generically denote the capacity of the
   output link associated with the micro flow. The transmission time
   delta of a size S packet onto the output link is given by S/C time
   units. Finally, let f denote the fraction of the output link
   capacity C as the target operating point for the aggregate EF flow
   at a given node.

   Also let tau_k denote the time at which the last bit of the kth
   packet reaches the egress border router. So we have

   (3) tau_k = t_k + d_k + d_p

   2.3  Egress edge of DS-domain

   The packets that arrive at the egress border router are placed in a
   micro flow specific buffer of size B_E. The number of complete
   packets in the egress buffer at time t is denoted by N_E(t). Similar
   to the ingress link, one packet is transmitted onto the egress link
   in every T time units. It is clear that the timing structure of the
   sequence {tau_k} is not necessarily the same as that of the sequence
   {t_k}. A commonly used strategy for recovering the initial timing
   structure is to delay the transmission of the first packet onto the
   egress link by a fixed amount of time, say D_xi, and set the size of
   the egress buffer B_E such that the continuity of the data flow is
   maintained when packets are transmitted onto the egress link using
   the very same timing structure {t_k}. We note that a micro flow
   specific buffer at the egress border router is required even for the
   original Virtual Wire [4]. Let xi_k denote the time at which the
   first bit of the kth packet is transmitted onto the egress link.
   Accordingly, we have

   (4) xi_k = T + d_1 + d_p + D_xi + (k-1)T


3. Establishing a virtual wire

   In Appendix B, we list a number of micro flow properties over a
   virtual wire and express key micro flow quantities in terms of the
   virtual wire rate R and the equalization delay D_xi. We observe that
   the end-to-end delay experienced by each packet of the micro flow is
   constant as it would be over a dedicated wire and given by

   (5) xi_k - t_k = d_1 + d_p + D_xi


Mercankosk             Informational - Jan 2001                      4
                 Virtual Wire - Analysis & Extensions        July 2000

   We note that the end-to-end delay depends on the queueing delay d_1
   experienced by the first packet, the propagation delay d_p over the
   virtual wire, and the equalization delay D_xi at the egress border
   router. We will later observe that, in establishing a virtual wire,
   no explicit knowledge of d_1 and d_p is required.

   In expressing the key micro flow quantities, we assume that buffers
   over the DS-domain and at the egress border are sufficiently large
   that they do not overflow. We also assume that the equalization
   delay is made sufficiently large so that when the transmission of a
   packet onto the egress link is completed, there is always another
   packet in the egress buffer ready for transmission.

   Continuity of micro flow requires that every packet presented to the
   DS-domain at the ingress router at fixed intervals has to be
   transmitted onto the egress link after a fixed delay but again at
   the same fixed intervals, without being subject to packet loss or
   interruption during the life time of the flow. Packet loss occurs if
   a packet has to be discarded due to lack of storing capacity upon
   arrival at the egress border router. On the other hand, the flow is
   interrupted if a transmission cannot be started due to
   unavailability of a packet at the egress border buffer.

   In Appendix C, we show that having a bounded queueing delay over the
   DS-domain, as indicated by (2), is sufficient to have maximum and
   minimum limits on the egress border buffer fill N_E(t). Accordingly,
   the egress buffer fill N_E(t) is bounded above by
   ceiling((D+D_xi)/T) and below by floor((D_xi-D)/T) (definitions for
   floor(x) and ceiling(x) are given in Appendix A). We then use these
   limits to derive the necessary and sufficient conditions to maintain
   the continuity of flow. In relation to avoiding egress link
   starvation, we consider the situation where the first packet of the
   flow experiences no queueing delay and some other packet experiences
   a queueing delay arbitrarily close to the maximum D to obtain

   (6) floor((D_xi-D)/T) >= 0

   In relation to avoiding egress border buffer overflow however, we
   consider the situation where the first packet experiences a queueing
   delay arbitrarily close to the maximum D and some other packet
   experiences no queueing delay to obtain

   (7) ceiling((D+D_xi)/T) <= B_E

   As indicated earlier, in determining the maximum queueing delay D,
   the rarity of events has been taken into account. Accordingly, some
   level of loss is allowed in case events considered rare do occur.
   The conditions given in (6) and (7) ensure that there would be no
   further losses.

   The smallest value for D_xi that satisfies (6) is D. Setting the
   initial delay as

   (8) D_xi = D

Mercankosk             Informational - Jan 2001                      5
                 Virtual Wire - Analysis & Extensions        July 2000


   also minimizes the end-to-end delay over the DS-domain. The
   resulting end-to-end delay is

   (9) xi_k - t_k = xi_1 - T = d_1 + d_p + D

   Now substituting (8) into (7), we have

   (10) ceiling(2D/T) <= B_E

   Consequently, the left hand side of the inequality in (10)
   determines the minimum buffer size for egress border buffer as

   (11) B_E = ceiling(2D/T)


4. Characterization of the delay bound

   In Appendix D, we outline a general queueing model that forms the
   basis for quantifying the transfer delay bound. We observe that, for
   all practical purposes, the transfer delay bound is only a function
   of aggregate traffic intensity and independent of individual micro
   flow rates. We point out that strict ingress policing and resource
   reservation ensure the delivery of rate guarantees to individual
   micro flows. We also emphasize the non-ergodic nature of the problem
   which is critical in determining the measure of interest.

   In this section, we first look at the delay due to phase
   coincidences with other micro flows. We next consider heterogeneous
   micro flow rates in relation to the delay due to packets from the
   same micro flow. We then summarize the methods of determining the
   delay bound across the DS-domain. We finally consider servers taking
   vacations upon becoming idle to examine the delay due to non-EF
   micro flows.

   4.1  Delay due to phase coincidences with other micro flows

   The queueing model outlined in Appendix D is based on the
   superposition of periodic micro flows. Given the strict ingress
   policing to ensure a micro flow behavior given by (1), a nD/D/1
   queue naturally arises provided that all contributing micro flows
   have just joined in. Due to phase coincidences at a given router, a
   micro flow cannot maintain the behavior given by (1) into the
   successive routers along its path. However, we note that the work
   associated with the micro flow remains unchanged. The deviation from
   the nominal behavior, after a number of multiplexing stages, results
   in the delay experienced by each packet of a micro flow being
   additionally affected by the previous packets of that flow [10].
   Such an impact can be taken into account by considering an
   additional flow into the queueing system.

   As a limiting case, we observe that the delay distribution through
   an (M+D)/D/1 queueing system always provides an upper bound for the
   delay distribution through any nD/D/1 queue of the same aggregate

Mercankosk             Informational - Jan 2001                      6
                 Virtual Wire - Analysis & Extensions        July 2000

   intensity. We note, however, that the use of a conservative upper
   bound does not alter the non-ergodic nature of the problem.

   4.2  Delay due to packets from the same micro flow

   In Appendix D, when the aggregate consists of micro flows of the
   same rate, we note that a packet cannot be further delayed due to
   packets from the micro flow that it belongs to. Yet, when the
   aggregate consists of micro flows of different rates, this is not
   necessarily correct. In particular, a packet from a high rate flow
   may find itself queued behind packets from the same micro flow even
   when all micro flows are perfectly periodic.

   Referring to the numerical examples given in Appendix D, the
   following observation can be made: The delay distribution for an
   arbitrary aggregate traffic mix is always upper bounded by that of
   an aggregate which consists of micro flows of the smallest rate only
   and totalling to the same intensity. This means that for a given
   fraction f, the number of possible minimum rate micro flows
   determines an upper bound distribution function for any aggregate
   traffic mix.

   Note that, through conservative upper bounding, we have the same
   delay bound for all micro flows in an aggregate irrespective of
   individual rates which in turn greatly simplifies the management of
   a DS-domain. Take, for example, the case where the transmission is
   over an OC-3 link (C=148.61 Mbps, sonet user rate) with aggregate EF
   traffic intensity 0.90C on the link, then the delay bound per hop is
   of the order of 1.02 ms (delta=10.77 micro seconds, S=200 bytes, M -
   > infinity, D=95delta, alpha=10^-9).

   4.3  Delay across a DS-domain

   If a DS-domain is designed such that the lowest capacity domain link
   constrains the total number of micro flows that can be transferred
   over the DS-domain [4] then the Appendix F establishes that the
   bound on the delay can be determined from one count of an equivalent
   stand alone nD/D/1 queue or (M+D)/D/1 queue.

   Alternatively, consider the case where each micro flow follows a
   fixed routing path from ingress to egress over a fixed number of
   hops, say H. We note that a micro flow may traverse portions of DS-
   domain together with other micro flows. However, a conservative
   delay bound across the domain can be determined by assuming that the
   micro flow meets a new set of micro flows at each hop. The delay
   across the DS-domain can then be considered as the sum of H
   independent random delay components. Consequently, the bound on the
   delay can be determined from H counts of nD/D/1 queue or (M+D)/D/1
   queue. The study given in [11] provides an accurate closed-form
   formula to calculate the transfer delay bound under similar
   assumptions.

   Since the use of conservative assumptions result in small delay
   bounds (e.g. 1.02 ms), over provisioning of bandwidth resources is

Mercankosk             Informational - Jan 2001                      7
                 Virtual Wire - Analysis & Extensions        July 2000

   not required. Rather, moderate amounts of additional storage
   resources have been traded for lowering the probability of data flow
   discontinuity. Also, the simplicity in management of a DS-domain has
   been an underlying guideline.

   4.4  Delay due to non-EF micro flows

   In the case of non-preemptive priority queueing, it is possible that
   an EF micro flow packet arriving to an empty EF queue may find the
   server busy transmitting a non-EF packet and has to wait for the end
   of transmission. The worst case occurs when there is always a non-EF
   packet waiting to be transmitted. The situation is then equivalent
   to a queueing system where a server can take vacations if no
   customer is waiting upon completion of a service. Appendix E
   provides relevant references for quantifying the additional delay an
   EF-packet experiences due to non-EF micro flows.

   Figure 2: Residual rest periods due to non-EF flows

   Given the properties of queueing models with rest periods stated in
   Appendix E, the problem of determining the delay due to non-EF micro
   flows reduces to that of calculating the distribution of residual
   rest periods. Let S_N-EF denotes the size of a non-EF packet. Then
   the transmission time delta_N-EF onto the output link is given by
   S_N-EF/C. There are three cases to consider as illustrated in Figure
   2. If the size of a non-EF packet is also equal to S, i.e. delta_N-
   EF =  delta, then the study in [5] readily provides the solution. If
   the size of a non-EF packet is, and normally would be, larger than S
   but requires less than T time units for transmission, i.e. T >=
   delta_N-EF > delta, we can use the property shown in [8] with
   uniformly distributed residual rest period to quantify the delay due
   to non-EF micro flows. Finally, if the time required to transmit a
   non-EF packet is larger than T time units, i.e. delta_N-EF > T, then
   the residual rest period is equal to delta_N-EF - T which is a
   constant plus a uniformly distributed random variable over (0,T]. If
   the packet lengths from non-EF micro flows are not fixed but drawn
   from a known distribution then the residual rest period distribution
   has to be determined accordingly.


5. Other issues

   We finally look at other issues such as the issue of non-EF traffic
   starvation, the expected time to the first failure and heterogeneous
   packet lengths. Unless otherwise stated, we assume non-preemptive
   priority queueing with equal size EF micro flow packets.

   5.1  The choice of scheduling mechanism

   Recall that f denotes the fraction of the output link capacity C
   that is allocated to the aggregate EF flow at a given node. The
   maximum amount of EF work presented to the node is then worth fT
   time units in any interval of T time units. Equivalently, the output
   link either remains idle or is used to serve non-EF work for T-fT

Mercankosk             Informational - Jan 2001                      8
                 Virtual Wire - Analysis & Extensions        July 2000

   time units. We note that these proportions remain valid under any
   scheduling mechanism. However, the delay experienced by the members
   of the aggregate flow depends on the mechanism under consideration.
   Clearly, the use of priority queueing minimizes the delay for EF
   traffic and there is no issue of starvation for non-EF traffic
   provided that T-fT>0.

   We note, with non-preemptive priority queueing, that the possibility
   of an additional delay due to non-EF micro flows does not
   necessitate an additional bandwidth for EF aggregate provided that
   the aggregate input rate does not exceed the minimum departure rate
   which happens to be the output link capacity. This observation is
   based on the fact that the EF traffic never waits while a non-EF
   queue is serviced except under the circumstances described earlier.
   This situation is distinctly different under weighted round robin
   scheduling where the EF queue is forced to relinquish control every
   now and then as its scheduling parameters require.

   We acknowledge that the particular way EF PHB is defined may result
   in EF bandwidth allocation restrictions. We note, however, that it
   is not a technical requirement, either.

   It is correct that one could clear the EF traffic backlog by using a
   scheduling mechanism such as weighted round robin that guarantees a
   minimum departure rate of (f+deltaf)C with deltaf>0. Such a
   departure rate, instead of C, can then be used in the analysis above
   to determine the corresponding delay bounds. As a matter of fact,
   the minimum departure rate is actually the maximum rate that a
   scheduler can guarantee to clear the EF traffic backlog. Depending
   on the dynamic state of the node, the scheduler may clear the EF
   traffic backlog at a higher rate. However, for the purposes of
   creating a Virtual Wire PDB, the situation is not considered well
   defined [4].

   5.2  Expected time to the first failure

   We noted earlier that the delay bound, D, is obtained by the (1-
   alpha) quantile of the queuing delay for some alpha, say alpha=10^-
   9. Accordingly, if a VW micro flow lasts long enough then there is a
   distinct possibility that the data flow continuity could break down.
   We now establish a crude but conservative expected time to the first
   failure. A similar approximation has been given in [5]. Recall that
   an activity change means that either one micro flow drops out or
   another one joins in. Although activity changes occur due to one
   micro flow at a time, we assume an entirely new and independent
   arrival pattern at each activity change. We further assume that
   there will be an activity change for each packet of a tagged micro
   flow which is not normally the case. The probability that a packet
   from the tagged micro flow experiences very small or no queueing
   delay is a function of target operating loading (indicated by
   fraction f of each link along the path), and it is generally very
   high. Therefore, if the first packet of the tagged micro flow
   experiences a queueing delay greater than D, a break


Mercankosk             Informational - Jan 2001                      9
                 Virtual Wire - Analysis & Extensions        July 2000

   down in data flow continuity would immediately follow due to the
   reasoning that led to the condition in (6). However, this will
   happen only once per 1/alpha micro flow starts. For the more likely
   case of the first packet experiencing no queueing delay, the time
   until the first break down (expressed in number of activity changes)
   due to the reasoning that led to the condition in (7), is
   geometrically distributed with mean 1/alpha. For a micro flow that
   generates one packet every 20 ms, and given alpha=10^-9, the
   expected time to the first failure is conservatively 230 days which
   can be considered reasonably long for all practical purposes. These
   numbers further put the choice for parameter alpha into a context.

   5.3  Heterogeneous packet lengths

   Finally, we look at the issue of heterogeneous packet lengths. We
   first consider the case where fixed size packets are in use within
   the same flow, but the size of packets may differ from one micro
   flow to another. We then lift any restrictions on the packet
   lengths.

   We note that, given the virtual wire rate R, large packets mean
   longer periods and short packets mean shorter periods. However, the
   amount of work presented to an output link, in its nature, does not
   differ from the case when we have fixed size packets. Because of the
   strict ingress policing, the size of a packet can be considered as a
   quantum of service request over a short time scale. At one extreme,
   consider a micro flow with a smaller packet size competing with
   micro flows that use larger packets. Given the uniformly distributed
   packet arrival epochs in the analysis above, it should be clear that
   the distribution of the number of packets that form the unfinished
   work does not change. However, we note that, given the number of
   packets in the queue, the unfinished work and hence the queueing
   delay is larger due to larger packet lengths. Under the
   circumstances, we can relate the difference in queueing delays to
   the service quanta represented by different packet sizes. Although
   the arguments given in this paragraph requires further study, the
   impact of heterogeneous packet sizes should not be significant
   provided that packet sizes, in use for EF micro flows, do not vary
   wildly.

   With variable length packets allowed within the same micro flow, its
   impact on the queueing delay can be determined when we observe that
   the unfinished work is now a random sum of random variables that
   represent packet lengths.

   Variable length packets within a given micro flow has also an impact
   on the packet transmission times for the micro flow. With fixed size
   packets, there is no variation due to packet transmissions and as
   such the transmission delay is considered as a component of the
   fixed propagation delay d_p. With variable packet lengths, the
   variation in packet transmission times is bounded by the difference
   between the transmission time of a maximum length packet and that of
   a minimum length packet. We note that the variation in transmission


Mercankosk             Informational - Jan 2001                     10
                 Virtual Wire - Analysis & Extensions        July 2000

   time can be incorporated into the earlier analysis as a modification
   on the propagation delay without any effect on the queueing delay.


6. Assumptions

   In this document, we have derived the necessary and sufficient
   conditions for realizing a `Virtual Wire' PDB under the assumption
   that a periodic flow of packets of fixed size is presented to the
   DS-domain. It is further assumed that each flow is fully and
   isochronously used. However, the use of `Virtual Wire' PDB is not
   limited to periodic flows of fixed size packets. As a matter of
   fact, pointers for incorporating any variations in traffic
   characteristics are given. Possible extensions include multi-
   priority EF queueing and periodic flows with on-off periods. These
   extensions and possibly some others are left for future discussions.


References

     [1] Bradner, S., "The Internet Standards Process -- Revision 3",
   BCP 9, RFC 2026, October 1996.
     [2] Bradner, S., "Key words for use in RFCs to Indicate
   Requirement Levels", BCP 14, RFC 2119, March 1997
     [3] V. Jacobson, K. Nichols, K. Poduri, "An Expedited forwarding
   PHB,"  ftp://ftp.isi.edu/in-notes/rfc2598.txt.
     [4] V. Jacobson, K. Nichols, K. Poduri, "The `Virtual Wire'
   Behavior Aggregate," draft-ietf-diffserv-ba-vw-00.txt, March 2000.
     [5] P.A. Humblet, A. Bhargava, M.G. Hluchyj, "Ballot Theorems
   Applied to the Transient Analysis of nD/D/1 Queues," IEEE/ACM
   Transactions on Networking, Vol 1, No 1, pp 81-95, February 1993.
     [6] J.W. Roberts, J.T. Virtamo, "The Superposition of Periodic
   Cell Arrival Streams in an ATM Multiplexer," IEEE Transactions on
   Communications, Vol 39, No 2, pp 298-303, February 1991.
     [7] M. Scholl, L. Kleinrock, "On the M/G/1 with Rest Periods and
   certain Service Independent Queueing Disciplines," Operations
   Research, Vol 31, pp 705-719, 1983.
     [8] G. Mercankosk, "Mathematical Preliminaries of Rate Enforced
   ATM Access," Australian Telecommunications Research Institute, NRL-
   TM-071, July 1995.
     [9] R.L. Graham, D.E. Knuth, O. Patashnik, "Concrete Mathematics,"
   Addison Wesley Publishing Company, 1994.
    [10] Commission of the European Communities, "COST 224, Performance
   evaluation and design of multiservice networks," Edited by J.W.
   Roberts, October 1991.
    [11] D. De Vleeschauwer, G.H. Petit, B. Steyaert, S. Wittevrongel,
   H. Bruneel, "An accurate Closed-Form Formula to calculate the
   Dejittering Delay in Packetized Voice Transport," Proceedings of the
   IFIP-TC6, International Conference on Networking 2000, pp 374-385,
   Paris, May 2000.





Mercankosk             Informational - Jan 2001                     11
                 Virtual Wire - Analysis & Extensions        July 2000

Acknowledgments

   This document is based on and inspired by an earlier joint work with
   Professor Cantoni. Numerous discussions on related topics with
   Professor Budrikis have found their way into the arguments presented
   in this document. Dr. Siliquini has provided a constant
   encouragement, and has shared the excitement for the preparation of
   this document. I would also like to acknowledge the context provided
   by Van Jacobson and his team.


Author's Address

   Guven Mercankosk
   Australian Telecommunications CRC
   University of Western Australia
   TEN Research Group (EE)
   Nedlands WA 6907
   Australia
   Phone: +61 8 9380 7260
   Email: guven@ee.uwa.edu.au


Full Copyright Statement

   "Copyright (C) The Internet Society (2000). All Rights Reserved.
   This document and translations of it may be copied and furnished to
   others, and derivative works that comment on or otherwise explain it
   or assist in its implmentation may be prepared, copied, published
   and distributed, in whole or in part, without restriction of any
   kind, provided that the above copyright notice and this paragraph
   are included on all such copies and derivative works. However, this
   document itself may not be modified in any way, such as by removing
   the copyright notice or references to the Internet Society or other
   Internet organizations, except as needed for the purpose of
   developing Internet standards in which case the procedures for
   copyrights defined in the Internet Standards process must be
   followed, or as required to translate it into

















Mercankosk             Informational - Jan 2001                     12
                 Virtual Wire - Analysis & Extensions        July 2000

A. Some number theoretic results

   We first note that, for all real x,  floor(x) denotes the largest
   integer less than or equal to x and ceiling(x) denotes the smallest
   integer greater than or equal to x. Also note that R and Z denote
   the set of real and integer numbers, respectively.

   The following rules can be found in [9].

   (12) for all x in R, -floor(x) = ceiling(-x)

   (13) for all x in R, n in Z, n = ceiling(x) if and only if x <= n <
   x+1

   (14) for all x in R, n in Z, n < x if and only if n < ceiling(x)

   (15) for all x in R, n in Z, n > x if and only if n > floor(x)






































Mercankosk             Informational - Jan 2001                     13
                 Virtual Wire - Analysis & Extensions        July 2000

B. Micro flow relations

   In this appendix, we express key system quantities in terms of the
   virtual wire rate R and the equalization delay D_xi. We assume that
   buffers over the DS-domain and at the egress border are sufficiently
   large that they do not overflow. We also assume that the initial
   delay is made sufficiently large so that when the transmission of a
   packet onto the egress link is completed, there is always another
   packet in the egress buffer ready for transmission. Subsequently in
   the Appendix C, we determine the bounds on the buffer sizes and the
   initial delay.

   B.1  Packets presented and delivered

   The number of packets presented to the DS-domain at the ingress
   border in the interval (0,t] is given by the expression

   (16) floor(t/T)

   and illustrated in Figure 3.

   Figure 3: Packet presentation instants at the ingress

   Similarly, the number of packets transmitted onto the egress link in
   the interval (d_1+d_p+D_xi,t] is given by the expression

   (17) floor((t-(d_1+d_p+D_xi))/T)

   and illustrated in Figure 4.

   Figure 4: Packet departure instants at egress

   B.2  Egress router buffer fill

   The arrival instants at the egress border buffer partition the time
   axis into contiguous intervals of variable length. That is, for a
   given time t, there exists an integer n such that

   (18) tau_n <= t < tau_(n+1)

   where tau_n is defined as in (3) and illustrated in Figure 5.

   Figure 5: Arrivals at egress border buffer

   The fill level of the egress border buffer at time t is equal to a
   difference between the total number of packets that have arrived at
   the egress buffer and the number of packets transmitted onto the
   egress link. Equivalently,

   (19) N_E(t) = n - floor((t-(d_1+d_p+D_xi))/T)

   which follows from (17) and (18).



Mercankosk             Informational - Jan 2001                     14
                 Virtual Wire - Analysis & Extensions        July 2000

   The fill level N_E(t) is a non-increasing function of t between the
   two successive arrivals at the egress border buffer or over the
   interval [tau_n,tau_(n+1)) as illustrated in Figure 6.

   Figure 6: Fill level between successive arrivals

   B.3  Packets in transit

   Packets in transit are the packets that have been presented to the
   DS-domain at the ingress router but have not yet reached the egress
   border buffer. So, the number of packets in transit at a given time
   t is given by

   (20) N_DS(t) = floor(t/T) - n

   which follows from (16) and (18).

   B.4  End-to-end delay

   The initial fill for a particular flow is the number of packets
   presented to the DS-domain just ahead of the transmission of the
   first packet onto the egress link minus the first packet. Noting
   that N_DS(xi_1) is the number of packets in transit at time xi_1 and
   N_E(xi_1) is the egress border buffer fill at the same time xi_1, we
   have

   (21) N_DS(xi_1) + N_E(xi_1) = floor(xi_1/T) - 1 =
   floor((d_1+d_p+D_xi)/T).

   Next, we derive an expression for the end-to-end delay over the VW.
   The end-to-end delay experienced by the kth packet is the time from
   when the last bit of the kth packet is presented to the DS-domain to
   when the first bit is transmitted onto the egress link. It can be
   found by rearranging (4) and substituting t_k for kT as

   (22) xi_k - t_k = xi_1 - T = d_1 + d_p + D_xi

   which shows that the end-to-end delay is constant as it would be
   over a dedicated wire. Adding and subtracting floor(xi_1/T)T and
   rearranging terms lead to

   (23) xi_k - t_k = (xi_1 - floor(xi_1/T)T) + (N_DS(xi_1) +
   N_E(xi_1))T

   where we also make use of (4) for k=1 and (21). Since the packet
   presentation to the DS-domain and packet transmission onto the
   egress link are periodic with period T, the first term on the right
   hand side of the (23) can be considered as the phase difference
   phi_R of the egress link relative to the ingress link which is

   (24) 0 <= phi_R = xi_1 - floor(xi_1/T)T < T.

   B.5  An invariance property


Mercankosk             Informational - Jan 2001                     15
                 Virtual Wire - Analysis & Extensions        July 2000

   Adding equations (19) and (20) leads to

   (25) N_DS(t) + N_E(t)
          = floor(t/T) - floor((t-(d_1+d_p+D_xi))/T)
          = (floor(xi_1/T) - 1) + (floor(t/T) - floor((t-phi_R)/T))
          = N_DS(xi_1) + N_E(xi_1) + (floor(t/T) - floor((t-phi_R)/T))

   where we make use of (21) and (24). (25) indicates that the total
   number of packets for a periodic flow over a virtual wire remains
   constant to within one packet, once the egress link is initialized
   and the transmission starts. This is expected as packets flow in at
   the same rate that they flow out. This represents an invariance
   property of the total fill, including the packets in transit.

   Figure 7: Invariance property of the total fill

   As illustrated in Figure 7, the last term on the right hand side of
   (25) takes only the values 0 and 1. If we observe the term over the
   time, the term switches from 0 to 1 just after a packet is presented
   at the ingress. It stays at that value until the next packet is
   transmitted onto the egress link. Then it switches back to 0.


































Mercankosk             Informational - Jan 2001                     16
                 Virtual Wire - Analysis & Extensions        July 2000

C. Continuity of flow

   In Appendix B, we assume sufficiently large buffers and initial
   total fill so that the data flow continuity could be maintained. In
   this section, we derive the necessary and sufficient conditions for
   data flow continuity.

   Continuity of data flow requires that every packet presented to the
   DS-domain at the ingress router at fixed intervals has to be
   transmitted onto the egress link after a fixed delay but again at
   the same fixed intervals, without being subject to packet loss or
   interruption during the life time of the flow. Packet loss occurs if
   a packet has to be discarded due to lack of storing capacity upon
   arrival at the egress border router. On the other hand, the flow is
   interrupted if a transmission cannot be started due to
   unavailability of a packet at the egress border buffer. In the
   latter case, the buffer is said to be underflowing.

   In what follows, we show that having a bounded queueing delay over
   the DS-domain is sufficient to have limits on the maximum fill level
   that the egress buffer could reach and the minimum fill level that
   it could fall. These limits can then be used to derive the necessary
   and sufficient conditions to avoid both overflows and underflows of
   the egress buffer, i.e. to maintain the continuity of flow.

   C.1  Egress buffer overflow

   As the fill level N_E(t) is a non-increasing function of t over the
   interval [tau_n,tau_(n+1)), it has its peak level at the start of
   the interval, when the nth packet arrives. Substituting tau_n for t
   in (19), we have

   (26) N_E(t) <= n - floor((t_n+d_n+d_p-(d_1+d_p+D_xi))/T)

   where we make use of (3). Again from the identity given in (1), we
   see that t_n/T is an integer. This leads to

   (27) N_E(t) <= - floor((d_n-d_1-D_xi)/T)
               <= ceiling((d_1+D_xi-d_n)/T)
               <  (d_1+D_xi-d_n)/T + 1

   where we make use of (12) and (13). An upper bound for N_E(t) can be
   found by considering a packet which experiences no queueing delay
   over the DS-domain and the case where the first packet experiences a
   queueing delay arbitrarily close to the maximum. That is,

   (28) N_E(t) <  (D+D_xi)/T + 1
               <= ceiling((D+D_xi)/T)

   where we make use of (14). Therefore, the maximum value N_E,max that
   the fill level N_E(t) of the egress buffer can reach satisfies the
   relation

   (29) N_E(t) <= N_E,max = ceiling((D+D_xi)/T).

Mercankosk             Informational - Jan 2001                     17
                 Virtual Wire - Analysis & Extensions        July 2000


   So if we choose the size of the egress buffer B_E greater than or
   equal to N_E,max, then the egress buffer never overflows. Otherwise
   whenever the fill level N_E(t) reaches N_E,max, that is

   (30) N_E(t_max) = N_E,max > B_E

   the egress buffer overflows. This leads us to our first dimensioning
   rule

   (31) ceiling((D+D_xi)/T) <= B_E

   which is necessary and sufficient to avoid egress buffer overflow.

   C.2  Egress link starvation

   Since the fill level N_E(t) is a non-increasing function of t over
   the interval [tau_n,tau_(n+1)), it falls to its minimum level after
   the last, say the kth, packet is transmitted onto the egress link
   but before the (n+1)st packet arrives. Substituting tau_(n+1) for t
   in (19), we obtain

   (32) N_E(t) >= n - floor((t_(n+1)+d_(n+1)+d_p-(d_1+d_p+D_xi))/T)

   where we again make use of (3). Using the fact that t_(n+1)/T is an
   integer and the identity (1), we are led to

   (33) N_E(t) >= -1 - floor((d_(n+1)-d_1-D_xi)/T)
               >= ceiling((d_1+D_xi-d_(n+1))/T) - 1
               >= (d_1+D_xi-d_(n+1))/T - 1

   where we again make use of (12) and (13). Over all packet transfers,
   a lower bound for N_E(t) can be found this time by considering a
   packet which experiences a queueing delay arbitrarily close to the
   maximum and the case where the first packet experiences no queueing
   delay over the DS-domain. That is,

   (34) N_E(t) >  (D_xi-D)/T - 1
               >= floor((D_xi-D)/T)

   where we make use of (15). Therefore, the minimum value N_E,min that
   the fill level N_E(t) of the egress buffer can fall satisfies the
   relation

   (35) N_E(t) >= N_E,min = floor((D_xi-D)/T).

   Note that the minimum value N_E,min is determined at a time instant
   such that there will be at least one packet arrival ahead of the
   next scheduled transmission onto the egress link. So if we delay the
   transmission of the first packet onto the egress link longer than
   the maximum queueing delay possible over the DS-domain, then the
   fill level of the egress buffer never falls below zero. Otherwise,
   whenever circumstances occur for the fill level N_E(t) to fall down
   to N_E,min, that is

Mercankosk             Informational - Jan 2001                     18
                 Virtual Wire - Analysis & Extensions        July 2000


   (36) N_E(t_min) = N_E,min < 0

   the transmission is interrupted. This leads us to our second
   dimensioning rule

   (37) floor((D_xi-D)/T) >= 0

   which is necessary and sufficient to avoid egress link starvation.














































Mercankosk             Informational - Jan 2001                     19
                 Virtual Wire - Analysis & Extensions        July 2000

D. Superposition of periodic flows

   In this appendix, we outline a queueing model that forms the basis
   for quantifying the transfer delay bound over a DS-domain. We first
   describe the queueing model in terms of periodic micro flows to
   establish the relevance. We then summarize the studies in the
   literature to quantify the delay due to phase coincidences among
   micro flows and the delay due to packets within the same micro flow.
   We finally provide a set of numerical examples.

   D.1  Queueing model

   Consider M independent and identical EF-micro flows arriving at a
   DS-domain router such that all M are bound for the same output link.
   With the use of priority queueing, the output link capacity provides
   a well-defined minimum departure rate for EF-traffic. Let C denote
   the output link capacity. The transmission time delta of a size S
   packet onto the output link is given by S/C time units. Assuming
   that the micro flow behavior is strictly determined by (1), each
   micro flow presents one packet in every T time units to the DS-
   domain router. Accordingly, the aggregate is a superposition of
   periodic flows. Limiting the number M of micro flows such that M
   delta < T, we ensure that the aggregate input rate is less than the
   minimum departure rate. Consequently, at the output link of the DS-
   domain router, there is no issue of rate guarantees to individual
   micro flows. That is, whatever is presented to the DS-domain router,
   as specified by (1), will be transmitted onto the output link of the
   router in finite time with probability one, irrespective of the
   scheduling mechanism being deployed provided that the mechanism is
   work conserving.

   Figure 8: An illustration of an arrival pattern

   The aggregate behavior is completely specified by a set of arrival
   epochs in any interval of length T. Each set consists of one arrival
   per micro flow. An illustration of a possible arrival pattern is
   given in Figure 8. The worst case phasing occurs when all M arrival
   epochs coincide. However, it should be clear that the likelihood of
   such occurrence is very small. Nonetheless, phase coincidences give
   rise to an inevitable multiplexing delay. Assuming a deterministic
   scheduler, we note that during an interval of no activity change,
   there is no change in the delay for individual micro flows. An
   activity change means that either one micro flow drops out or
   another one joins in.

   In determining the likelihood of exceeding a specified delay bound,
   we can safely ignore the repetitive arrival patterns (which is the
   case over an interval of no activity change) and only consider
   distinct arrival patterns. In other words, we look at the percentage
   of arrival patterns that result in a delay exceeding a specified
   bound. Given the non-ergodic character of the behavior aggregate, we
   note that the measure of interest is the likelihood of exceeding a
   specified delay bound (ensemble average) rather than the percentage
   of time a specified delay bound is exceeded (time average).

Mercankosk             Informational - Jan 2001                     20
                 Virtual Wire - Analysis & Extensions        July 2000


   D.2  Delay due to phase coincidences with other micro flows

   At a multiplexing stage, the delay due to phase coincidences has
   been studied in [5] and [6]. The method involves tagging a micro
   flow and considering an arbitrary arrival pattern of other micro
   flows for determining the probability of delay exceeding a specified
   value for the tagged micro flow. Given that each micro flow is
   strictly shaped to rate R, each packet arrives at a time when it is
   supposed to arrive. Consequently, FCFS scheduling becomes a natural
   choice for arbitration of EF micro flows. We note that any other
   sophisticated arbitration method would require per micro flow state
   information.

   Without loss of generality, a packet from the tagged micro flow is
   assumed to arrive at time t. The waiting time of the packet is then
   given by the unfinished work in the queue (referred to as nD/D/1
   queue) at time t, due to M-1 packet arrivals, one per every other
   micro flow, which are distributed uniformly and independently over
   the interval [t-T,t) provided that M delta < T. In [5], the
   associated distribution is given as

   (38) Pr{ delay > D } = SUM D(j) over [j,ceiling(D/delta),M-1]

          where  D(j) = A(j) C(M-1,j) B(j)^j (1-B(j))^(M-1-j)
                 A(j) = (T+D-(M-1)delta)/(T+D-j delta)
                 C(M-1,j) denotes M-1 choose j
                 B(j) = (j delta - D) / T.

   The result given in (38) can be normalized, in a straight forward
   manner, to the transmission time delta. Consequently, the result is
   not specific to any network architecture. Furthermore, since the
   choice of tagged micro flow is arbitrary, the delay distribution
   applies to all micro flows. The issue of heterogeneous packet sizes
   is addressed elsewhere. It is also a common practice in the
   literature to normalize the delay to the period T which we have
   avoided. The normalization naturally takes place in deriving
   necessary and sufficient conditions given by (6) and (7).

   D.3  Delay due to packets from the same micro flow

   The study given in [6] provides a method of determining the delay
   distribution for an individual micro flow where the aggregate
   consists of micro flows with heterogeneous rates. Let M_i denote the
   number of type-i micro flows with period T_i. Then, we ensure that
   the aggregate input rate does not exceed the minimum departure rate
   by satisfying the condition SUM (M_i delta) / T_i < 1 where the
   summation is taken over the set of possible micro flow types. In
   determining the unfinished work in the queue at time t, the method
   makes the observation, as illustrated in Figure 9, that the number
   of packet arrivals from a given type of micro flow in an interval
   [t-s,t) of length s consists of a deterministic part and a random
   part. Note that in the former case, we only have the random part and
   that the intervals of size greater than T need not be considered.

Mercankosk             Informational - Jan 2001                     21
                 Virtual Wire - Analysis & Extensions        July 2000


   Figure 9: The number of packet arrivals in [t-s,t)

   The study [6] develops tight upper bounds for delay distribution
   functions as the exact distributions are, in general, difficult, if
   not impossible, to determine. Fortunately though, the study [6] also
   concludes that the delay distribution for an arbitrary traffic mix
   is always upper bounded by that of an aggregate which consists of
   micro flows of the smallest rate only and totalling to the same
   intensity.

   In the case of homogeneous micro flows in a single multiplexing
   stage, it is always correct that the delay bound for an individual
   micro flow never exceeds its period T and in general is much smaller
   than the period by a couple of orders of magnitude. As a result, a
   packet cannot be further delayed due to packets from the micro flow
   that it belongs to. We note however that when the aggregate consists
   of micro flows with different rates, this is not necessarily
   correct. In particular, a packet from a high rate micro flow may
   find itself queued behind packets from the same micro flow. Despite
   this fact, the method that we refer above already incorporates the
   situation in its derivations.

   D.4  Numerical results

   Figure 10: Delay distribution for nD/D/1 queues, aggregate intensity
   0.90C

   First, we consider multiplexing homogenous micro flows at an
   aggregate intensity of 0.90C. The number M of micro flows varies
   between 50 to 900. The corresponding delay distributions, obtained
   by using (38), are plotted in Figure 10. Clearly, as the number M
   increases higher delays are observed. But even for 900 micro flows,
   the probability of delay exceeding 62 delta time units is 10^-9.
   This value of delay is smaller than the worst case, which is 899
   delta time units, by an order of magnitude. We note that the
   corresponding distribution for an (M+D)/D/1 system represents the
   limiting case as M->infinity.

   Next, we keep the aggregate traffic intensity at 0.90C but consider
   different aggregate traffic compositions. The upper bounds for delay
   distribution functions, obtained by using the formulation given in
   [6], are plotted in Figure 11 where each composition is labelled by
   a triple (M_1,M_2,M_3) and M_i indicates the number of type-i micro
   flows. In the first composition, we have few high rate flows. Then
   we replace some high rate flows with many low rate flows. This
   results in an increase in the delay experienced, but again to some
   moderate values. For example, in the third composition where we have
   461 micro flows, the probability of delay exceeding 40 delta time
   units is 10^-9. The delay bound is again 10 times less than the
   worst case figure.

   Figure 11: Upper bound distribution functions,
   T_1=1000delta,T_2=33.33delta,T_3=6.67delta

Mercankosk             Informational - Jan 2001                     22
                 Virtual Wire - Analysis & Extensions        July 2000


   Comparing these two sets of experiments, the following observations
   can be made. First, the upper bound for a distribution function
   yields the same result as (38) does, if there is only one type of
   micro flow. Second, any aggregate traffic composition would result
   in a better delay performance than the case where enough number of
   lowest rate micro flows making up the same aggregate intensity. This
   means that for a given fraction f, the number of possible minimum
   rate micro flows determines the limiting distribution for any
   aggregate traffic mix.













































Mercankosk             Informational - Jan 2001                     23
                 Virtual Wire - Analysis & Extensions        July 2000

E. Queueing models with rest periods

   Queueing models with rest periods are used in the analysis of
   slotted queueing systems. This appendix provides relevant references
   for studying the delay due to non-EF traffic.

   In [7], the study shows that, for a slotted M/G/1 system, the
   waiting time is the sum of two independent random variables
   representing the waiting time when there are no rest periods and an
   additional delay distributed as the residual life of the rest
   period.

   In [5], the study provides not only the delay distribution as given
   in (38) when there is no slotting but also the delay distribution
   when the transmission is restricted to start at a slot boundary
   where each slot is of fixed length equal to delta. Since packet
   arrival epochs are assumed to be uniformly distributed over an
   interval of length T, the residual slot period until the start of
   the next transmission opportunity (following the arrival of a packet
   from the tagged micro flow) is uniformly distributed over (0,delta].

   In [8], based on the results given in [5], we show that a slotted
   nD/D/1 queue exhibits the same property, given in [7], as a slotted
   M/G/1 system does.































Mercankosk             Informational - Jan 2001                     24
                 Virtual Wire - Analysis & Extensions        July 2000

F. A network of routers in tandem

   In this appendix, we consider two simulation scenarios. In the first
   scenario, we have a network of routers in tandem where micro flows
   with a common destination are incrementally introduced at each hop.
   In the second scenario, the same set of micro flows compete for
   access onto the same output link of a stand-alone router. The latter
   is equivalent to having infinite capacity links between the
   intermediate routers in tandem except at the last hop.

   An illustration of a network of routers in tandem is given in Figure
   12. The network is comprised of a specified number of routers. The
   background flows in groups are attached to specified routers and
   join the aggregate flow. We focus on a single tagged or test flow
   and study its delay characteristics through the network. The test
   flow can be attached to any router and runs from the router it is
   attached (the ingress router) to the egress router.

   Figure 12: A network with 4 hops, all flows through the same egress
   router

   Figure 13: A stand-alone router

   With the use of infinite capacity links between the routers, the
   network of routers in tandem can be represented with a stand-alone
   router as illustrated in Figure 13. To facilitate the comparison,
   the flow arrival patterns used for the routers in tandem are exactly
   regenerated and presented to the stand-alone router.

   F.1  Traffic model

   In quantifying the delay due to phase coincidences, we maintain a
   periodic test flow. Once the activity of the test flow starts, it
   presents packets to the network continuously at the specified rate
   until the end of simulation run.

   In determining ensemble averages, we use a specified number of
   background micro flows with identical period. After an uniformly
   distributed transient delay, each background flow determines a
   random phase within its period to start its activity. After
   periodically generating a specified number packets at a given phase,
   the background flow stops for a geometrically distributed number of
   periods. At the end of the silence interval, it repeats its activity
   with a different phase.

   The use of Markovian background traffic can be considered as a
   limiting case. As a matter of fact, considering a background traffic
   comprised of M independent periodic flows each with period T, it is
   true that the number of arrivals over an interval (t-s,t] is
   distributed according to the binomial distribution where s<T.
   Consequently, in the limit as M->infinity while keeping the
   aggregate intensity fixed at fC=N delta/T, we obtain Poisson arrival
   process with parameter fC. In other words, the Markovian noise is


Mercankosk             Informational - Jan 2001                     25
                 Virtual Wire - Analysis & Extensions        July 2000

   comprised of infinitely many periodic flows each with period
   infinity while the aggregate intensity is fC.

   Accordingly, the background traffic either is comprised of a
   specified number of periodic flows with randomly changing phases or
   is generated by a Markovian process of equivalent intensity.
   Although it is assumed that priority queueing is deployed at each
   router, the non-EF traffic is not considered. The ingress-to-egress
   total queuing delay experienced by each test packet is recorded to
   obtain a delay histogram.

   F.2  Numerical results

   In the first set of experiments, we use a test flow that
   periodically generates one packet in every 100 delta time units,
   i.e. with intensity 0.01C. In the background, we use 100 micro flows
   and 10 hops, i.e. 10 micro flows per hop. Each flow generates 20
   packets with period 100 delta time units at a random phase. After
   each phase activity, a flow remains silent for geometrically
   distributed number of 100 delta time units with a mean value of
   1.053. Accordingly, the intensity of background flows joining the
   aggregate at each hop is 0.095C. In the second set of experiments,
   the set of periodic flows at each router is replaced with a Poisson
   source of the same intensity.

   In both set of experiments, the location of the test flow is varied
   from nearest to the egress router to furthest. The associated delay
   distributions are plotted in Figure 14. Despite the fact that the
   aggregate intensity remains fixed, we observe that a test flow
   closer to the egress router experiences a better delay performance.
   We also note that, in the case of periodic background flows, after 5
   hops the difference becomes unnoticeable. In the case of Markovian
   flows, the difference is marginal altogether.

   Figure 14: Delay distribution versus test flow position, aggregate
   intensity

   In Figure 15, the tail distribution of the delay experienced by the
   packets of test flow when located at both extremes are plotted
   against that of the packets of test flow when the aggregate flow is
   fed into a stand-alone router. The delay experienced through the
   routers in tandem is depicted by dashed lines whereas that of
   through the stand-alone router is depicted by solid lines.

   Figure 15: Delay distribution, tandem versus stand-alone, aggregate
   intensity

   As the curves indicate, when the test flow is located furthest from
   the egress router, the performance is inferior to that of stand-
   alone router. However, in practical terms, it is insignificant. The
   difference can be attributed to arrival pattern transformations. A
   pattern transformation results due to the possibility of packets
   from micro flows joining the aggregate at a nearer router overtaking
   packets from the test flow until the latter packets reach the router

Mercankosk             Informational - Jan 2001                     26
                 Virtual Wire - Analysis & Extensions        July 2000

   in question. The simulation results show that the effect of such
   transformations are minimal.

   When the test flow is located nearest to the egress router, it is in
   the most advantageous position. As indicated earlier, the stand-
   alone router represents the situation of having infinite capacity
   links between the intermediate routers in tandem except at the last
   hop. A consequence of such a situation is that packets arriving at
   the intermediate routers appear at the last hop in no time. In the
   case of finite but relatively higher rate links, each packet appears
   at the last hop shortly following its arrival. Under the
   circumstances, the test flow located nearest loses its advantage but
   not beyond the delay due to originating phase coincidences.










































Mercankosk             Informational - Jan 2001                     27


Html markup produced by rfcmarkup 1.129d, available from https://tools.ietf.org/tools/rfcmarkup/