F
`
`INTERNATIONAL SWITCHING SYMPOSIUM
`1992
`
`"Diversification and Integration of
`Networks and Switching Technologies
`Towards the 21st Century"
`
`Yokohama, Japan
`October 25-30; 1992
`
`Proceedings
`Vol. 2
`
`FEB 0 8 1993
`
`Volume 1 Session A1 - C2, P
`A3 - C4
`Volume 2 Session A5 - C10
`
`:
`
`"
`
`GUEST TEK EXHIBIT 1021
`Guest Tek v. Nomadix, IPR2019-00211
`
`

`

`XIV
`International
`Switching
`Symposium
`Yokohama, .Japan
`October 25-30, 1992
`
`THE SPACING POLICER, AN ALGORITHM FOR EFFICIENT PEAK BIT RATE
`
`CONTROL IN ATM NETWORKS
`
`Eugen Wallmeier and Tom Worster
`
`Siemens AG, OEN ZL S, P.O. Box 700073, W-8000 Munich 70, Germany
`
`ABSTRACT
`
`A policing function enforcing the peak cell rate in an
`ATM network which does not prevent clusters of cells from
`entering the network cannot protect the network from
`congestion under all conditions. Proper protection can be
`achieved by using "cell spacing" where the policing
`function spaces out cells that arrive too close together, thus
`ensuring that the interdeparture times of consecutive cells
`are never in conflict with the negotiated peak cell rate. The
`paper presents a new algorithm for combined policing and
`cell spacing. The high performance of the algorithm results
`from two key principles: 1 - Shared memory is used for the
`waiting cells of all VC's, keeping memory requirements
`down; 2 - arriving cells are linked to an appropriate queue
`without using a search algorithm,
`thus
`the . dynamic
`processing requirements are similar to those of simpler non(cid:173)
`spacing algorithms. Concerning the inevitable delays due to
`spacing, the algorithm shows a tendency to prefer users
`who comply to their negotiated peak bit rate over non
`complying users.
`
`1. INTRODUCTION
`
`An ATM network's decision whether to accept an
`incoming connection depends on traffic parameters (e.g. the
`peak or mean cell rate - or equivalently - bit rate) which are
`negotiated between user and network at call set up time. A
`policing function (also known as usage parameter control
`(UPC) function) has to monitor the compliance of the user
`to
`the negotiated parameter values
`throughout
`the
`connection's holding time. This contribution addresses the
`problem of peak cell rate policing.
`
`In most of the policing functions proposed so far in the
`literature, excess cells are discarded but the rest of the cell
`stream passes the policing function unaltered. In [1] such
`policing
`functions
`are named pick-up
`algorithms.
`Meanwhile it is recognized (see e.g. [2-4]) that pick-up
`algorithms cannot protect the network efficiently under all
`conditions because they do not prevent clusters of cells
`from entering the network in the pres.ence of delay jitter.
`The impact of jitter on peak cell rate policing is discussed
`in more detail in Chapter 2.
`
`The problems caused by ch.1sters of cells belonging to
`one connection can be avoided . if the. policing function
`controlling the peak cell rate not only discards excess cells
`but also smooths out mome11~ary : peaks in the incoming
`traffic with the aid of a partkula.r.' ki,nd of traffic shaping
`known as "cell spacing". Cell spa¢itig '(cf. [1]) denotes the
`,;" ,,
`
`© IEICE 1992
`
`the
`that
`such
`technique of delaying certain cells
`interdepature
`times
`from
`the policing unit between
`consecutive cells of one connection are never below a
`minimal value which is allowed according to the negotiated
`·peak cell rate. Chapter 3 describes the logical functionality a
`cell spacing function has to provide. The problem of cell
`spacing on a VC basis at the User Network Interface is rather
`complex because a large number of VCs using the same
`access line have to be spaced individually but all at the same
`time.
`
`One way to implement a cell spacing function is
`described in [5]. Here we present an alternative algorithm
`(denoted as Spacing Policer) which allows combined cell
`spacing and policing for an access line used by any large
`number of ATM virtual connections. The algorithm which is
`described in Chapter 4 shows that cell spacing on a VC basis
`is feasible in practice with a moderate increase iri the
`complexity of the UPC function compared with a simple
`Leaky Bucket. The dynamic processing requirements for the
`presented Spacing Policer are moderate since arriving cells,
`which have to be delayed, are linked to an appropriate queue
`without using a search algorithm. In every cell cycle a sma.11
`deterministic amount of work has to be done. This facilitates
`an implementation for lines with very high speed (e.g. at the
`Network Node Interface).
`
`The required memory for the spacing policer, which is
`shared among all VCs, depends on the jitter which may arise
`between the terminal equipment and the policing function.
`Given a bound for the jitter, the cell memory can be
`dimensioned such that no cell loss due to lack of memory can
`occur. In Section 5 it is shown that a memory for 75 ATM
`cells will be sufficient even if an access lines connected to a
`large ATM P ABX is policed.
`
`The algorithm shows a tendency to prefer users who
`comply with their negotiated peak cell rate over users who
`exceed the negotiated peak cell rate during short bursts. On
`the average cells of well behaving sources will be less af(cid:173)
`fected by the inevitable multiplexing delay due to spacing
`than cells of sources which send short bursts violating the
`allowed peak cell rate. First results concerning the perfor(cid:173)
`mance of the Spacing Policer are described in Section 6.
`
`The high and low priority cell streams within one virtual
`connection have to be policed individually. In Section 7 two
`UPC schemes which can be used for this purpose are
`described. It is shown how the Spacing Policer can be used
`in these schemes.
`
`ISS '92, October 1992, Vol. 2
`
`AS.5
`
`

`

`THE SPACING POLICER, AN ALGORITHM FOR EFFICIENT PEAK BIT RATE CONTROL IN ATM NETWORKS
`
`23
`
`2. THE IMPACT OF JITTER ON PEAK CELL
`RATE POLICING
`
`In general, the peak cell rate observed by the UPC
`function will be different from the peak cell rate directly at
`the source 1) which is agreed in the contract between user
`and network. The difference results from jitter which may be
`introduced by the use of the GFC protocol, the slotted nature
`of the physical layer of an ATM system and multiplexing ar(cid:173)
`rangements located between source and UPC function. The
`UPC function has to tolerate this jitter, otherwise it might
`discard cells of well behaving sources. However it is princi(cid:173)
`pally impossible for the policing device to decide whether
`short bursts that violate the specified peak cell rate are cau(cid:173)
`sed by badly behaving sources or by delay jitter. If the poli(cid:173)
`cing function lets bursts of both kinds pass transparently
`through, this weakness may be exploited by "tricky users"
`who send short bursts at a cell rate exceeding the negotiated
`peak value (e.g. because they want to send small messages,
`such as X.25 packets, consisting of some ATM cells at the
`full cell rate of the User Network Interface). Errant terminal
`behaviour or intended misbehaviour could also cause bursts
`violating the specified peak cell rate. The public network
`cannot simply trust that none of the traffic sources are mali(cid:173)
`cious or tricky users and that sources always conform to
`their negotiated peak cell rates. The results in [2-4] show that
`already a relatively small amount of bursty traffic allowed by
`pick-up policing algorithms (e.g. the Leaky Bucket or the
`Sliding Window) may
`introduce severe degradation in
`network performance.
`
`3. A CONCEPTUAL MODEL FOR A COMBINED
`POLICING AND SPACING FUNCTION
`
`If an access line being policed is used only by one vir(cid:173)
`tual connection then the incoming traffic can be spaced with
`the aid of a buffer, which is organized as a FIFO (first-in(cid:173)
`first-out) queue and is served at the policed cell rate. Using
`such a "Leaky Bucket Queue" for a connection with a peak
`cell rate 10% of the pipe capacity, a cell could enter the net(cid:173)
`work at most every ten cell cycles. Generally, however, an
`access line may be used by a number of virtual connections
`(VCs) simultaneously (potentially up to 4000 VCs). In this
`case the problem of cell spacing at the network interface is
`more complex because all VCs have to be spaced indivi(cid:173)
`dually but all at the same time. In this case a spacing device
`has to provide the logical functionality of the conceptual
`
`Demultiplex
`
`n FIFO queues
`with deterministic
`service time
`
`Multiplex
`
`n VC5 on one line
`
`n VC5 on n lines
`
`n VC5 on one line
`
`Fig. 1 Conceptual model for a combined Leaky
`Bucket policing and cell spacing device. (Note that
`the device would not be implemented as shown here.)
`
`1) CCITI (see [6]) specifies a virtual cognectjon's peak cell rate as
`the inverse of the minimum inter arrival .time of two requests fo send an
`A 1M cell. The definition refers to a refeienc1; point at the service access
`pointoftheA1Mlayer.
`·' · :.::··" ·.
`
`model of the system shown in Fig. 1 which shows the VCs
`being demultiplexed on different lines such that VC indivi(cid:173)
`dual Leaky Bucket Queues can be applied before the VCs
`are multiplexed again.
`·
`
`From the implementation point of view a system using
`VC specific queues is not practical. This contribution pre(cid:173)
`sents a combined Leaky Bucket policing and cell spacing
`device (called Spacing. Policer), which emulates the logical
`behaviour of the system in Fig. 1 without using VC specific
`queueing.
`
`4. THE DESIGN OF THE SPACING POLICER
`
`In this Chapter we describe the Spacing Policer which
`monitors the total flow of virtual connections without consi(cid:173)
`dering the cell loss priority bit (CLP) in the ATM cell hea(cid:173)
`der. In Section 7 it is described how the Spacing Policer can
`be used in a UPC scheme taking into account the CLP bit.
`
`Fig. 2 shows a block diagram of the Spacing Policer.
`The input and output lines (providing a slotted system for
`carrying ATM cells of a possibly large number of VCs) have
`the same cell rate. One cell can be received per time slot
`(also denoted as cell cycle). Simultaneously another cell can
`leave the device. The Spacing Policer consists of two main
`components, the Leaky Bucket Manager and the Cell Buffer
`Manager. An incoming cell is forwarded to the Cell Buffer
`Manager, which is informed by the Leaky Bucket Manager
`(with the aid of a value D) how long the arriving cell has to
`be buffered before transmission or whether it should be dis(cid:173)
`carded.
`
`Input Line DJ ATMCell ~
`
`output Line
`
`VPINCI
`
`Leaky
`Bucket
`Manager Required Delay D
`
`Cell
`Buffer
`Manager
`
`'
`
`Fig. 2 Block diagram of the Spacing Policer
`
`4.1 The Leaky Bucket Manager
`
`When the header of an arriving cell has been received,
`the VPINCI (virtual path/channel identifier) is given to the
`Leaky Bucket Manager which holds for every existing VC
`the variables and parameters of a common Leaky Bucket (in
`the following also denoted as "Leaky Bucket Counter")
`which simulates the behaviour of a VC individual Leaky
`Bucket Queue (i.e. a FIFO Queue with deterministic service
`time) as shown in the conceptual model.
`
`The value S of the Leaky Bucket Counter can he
`interpreted as the current content of the Leaky Bucket queue,
`which has three parameters: the fill value F (at cell arrival
`the queue length grows by F), the capacity C of the queue
`and the leak rate L.
`
`The counter S of the Leaky Bucket.is initialised to 0. At
`each of the VC's cell arrivals the counter S is first decremen(cid:173)
`ted by i • L (but not beyond 0), where i denotes the elapsed
`time since the last cell arrival (in cell cycles). If the resulting
`vafue S does not exceed C-F, the value D is calculated by
`
`A5.5
`
`ISS '92, October 1992, Vol.2
`
`

`

`24
`
`THE SPACING POLICER, AN ALGORITHM FOR EFFICIENT PEAK BIT RATE CONTROL IN ATM NETWORKS
`
`D = lS/LJ (lxJ is the integer part of x) and afterwards S is
`incremented by F. D represents the number of cell cycles the
`arriving cell would wait in a Leaky Bucket Queue served at a
`rate of rc=L/F cells per cycle. If S exceeds C-F after.it has
`been decremented, then S is not incremented and D is set to
`a special value' (e.g. -1) indicatjng that the cell should be
`discarded by the Cell Buffer Manager. In order to facilitate
`the imp'lementation of the Leaky Bucket Manager the leak
`rate L should be chosen as L= 2m for some integer m.
`
`4.2 The Cell Buffer Manager
`
`There are various ways to implement the Cell Buffer
`Manager. One variant is described in [7]. Here we describe
`an alternative solution.
`
`Fig. 3 shows the logical components of the Cell Buffer
`Manager: the Cell Memory (CM), an array denoted as
`Calendar (CA) and four additional variables specifying
`special positions in CM.
`
`The Cell Memory is a pool of storage elements, each
`element capable of storing an ATM cell together with a
`pointer to another element in the Cell Memory. These poin(cid:173)
`ters a11ow the elements of CM to be chained together in
`linked lists.
`
`Free List
`
`Time Slot Queues
`
`Output List
`
`Cell Memory
`
`T
`FLT Free List Tail
`FLH Free List Head
`CEH Calendar Entry Head
`
`OL T Output List Tail
`OLH Output List Head
`'CET Calendar Entry Tail
`
`Fig. 3 Structure of the Cell Buffer Manager
`
`All vacant cell spaces are chained together in the Free
`List. An arriving cell is written into the cell space at the head
`of the Free List, identified by a variable denoted as Free List
`Head.
`·
`
`Cell spaces containing ATM-cells which have been
`delayed for the time D calculated by the Leaky Bucket
`Manager and wait for transmission are chained together in
`the Output List. The Output List corresponds to the queue in
`the output multiplexer of the conceptual model of Fig. 1.
`
`The various VCs' cells that have to be delayed in the
`Spacing Policer are queued ·with the !lid of the Calendar
`(length NcA) which has an entry '(consisting of two parts, the
`Calendar Entry Head and the Calendar Entry Tail) for every
`cell cycle in the (near) futur'e, A~ariableT ·contains an index
`that 'identifies a special positioti in.~QA;.T is incremented by
`one (modulo NcA) at the begfn~irtg,of every cell cycle and
`
`thus provides the present cell cycle number (or time) modulo
`NcA'
`
`When a cell arrives the cell cycle X when it should
`leave is determined (namely X = (T+D) mod NcA) and the
`corresponding entry of the Calendar is marked. If there is
`only one cell which should leave in cell cycle X, then both
`parts of the corresponding calendar entry are marked with a
`pointer to the cell. If more than one cell want to exit the de(cid:173)
`vice in cell cycle X then these cells are linked together in a
`list (called time slot queue) in such a way that the cell which
`arrived most recently is at the head of the list and identified
`by the value of the Calendar Entry Head. The cell which has
`been waiting for the longest time in the time slot queue is
`identified by the Calendar Entry Tail.
`
`When the time proceeds and T reaches a marked entry
`of the Calendar, the corresponding time slot queue is
`transferred to the end of the Output List and the calendar
`entry is cleared. The time slot queue is linked to the Output
`List in such a way that the cell at the tail of the time slot
`queue forms the new tail of the Output List.
`
`In each cell cycle one cell of the Output List can be
`transmitted. The cells are transmitted in the order they ap(cid:173)
`pear in this list (starting from the head of the output list).
`After the cell at the head of the output list has been selected
`for transmission the CM element is linked to the tail of the
`Free List.
`
`All cells that have to wait in the Output List leave later
`then originally specified. The strategy used for linking
`arriving cells to a Time Slot Queue implies that cells which
`should leave at the same time are transmitted in the reverse
`order of their arrival. (In Fig. 3 the cells a, b, ... e would be
`read out in alphabetical order.) Thus a delay advantage is
`given to cells that have to be delayed only little or not ·at all
`and thus have a very small D value. On the average, cells of
`well behavin,g sources are less affected by the delay in the
`Output List than cells of bursty sources which send short
`bursts violating the allowed peak rate.
`
`5. DIMENSIONING OF THE SPACING POLICER
`
`5.1 Dimensioning of the Leaky Bucket Manager
`
`The Leaky Bucket parameters have to be chosen so that
`cells of a well behaving source are discarded only with a
`very low probability (e.g. 10-10). The probability that the
`Leaky Bucket Queue overflows is determined by the ratio
`C/F which is roughly spoken the capacity of the Leaky
`Bucket Queue measured in cells. It can be shown (in a
`similar way as that of inequality (5) in [8] that a cell of a
`source sending at the policed cell rate re= L/F cells per cycle
`is discarded with a probability not higher than a given value
`a (e.g. a=l0-10), when C and Fare chosen such that
`
`(1)
`
`where ti denotes the (1-a)-Quantile of the variable part .of the
`delay (in ce!I cycles) experienced between terminal equip(cid:173)
`ment and policing device. Dimensioning examples for the
`Leaky Bucket algorithm using (1) are given in table 2 of [9].
`
`5.2 Memory Requirements
`
`Memory Requirements for the Cell Buffer Manager
`depend on the parameters held by
`the Leaky Bucket
`·Manager. From the Leaky Bucket Counter description in
`
`ISS '92, October 1992, Vol.2
`
`AS.5
`
`

`

`THE SPACING POLICER, AN ALGORITHM FOR EFFICIENT PEAK BIT RATE CONTROL IN ATM NETWORKS
`
`25
`
`Section 4.1 we see that the requested delay D, which is
`calculated by the Leaky Bucket Manager after cell arrival, is
`always smaller thari or equal to Dmax which is the maximum
`value of
`l(C-F)/LJ over all the VCs. Cells which would
`require a higher delay are discarded as excess cells. In the
`Appendix it is shown that no cell loss due to lack of places in
`Cell Memory will occur even af 100% load if the Cell
`Memory has
`
`(2)
`
`elements. If the parameters of a Leaky Bucket Counter are
`correctly chosen (i.e. so that, for all Leaky Bucket Counters,
`the ratio C(F is only a little larger than the lower bound
`1 +ore given in inequality (1)) then C(F "" 1 +ore and
`
`Dmax ~ (C-F)/L ~
`
`F
`
`L
`
`= 6.
`
`At the UNI the (1-10-10)-quantile o of the queueing
`delay (and thus also DmaJ will be below or around 75 cell
`cycles, assuming that the cells arriving at the UNI have
`passed at most four queueing stages (e.g. in a large P ABX)
`where each queue has about 80% output utilisation. From
`this value, which was calculated by autoconvoluting the
`delay distribution of an M/D/1 queue, we get a necessary cell
`memory size of
`NcM = Dmax+l ""75 ATM cells.
`
`A Calendar of size
`
`(3)
`
`guarantees that the cell sequence integrity of a connection is
`preserved. The proof of cell sequence integrity is similar to
`the proof given in Appendix B of [7].
`
`6. EFFECT OF THE SPACING POLICER ON A
`CELL STREAM
`
`The effect of the Spacing Policer on a connection's cell
`stream should be considered as having three separate
`components, namely:
`
`• cell loss due to leaky bucket policing,
`
`• cell delay in the time slot queues (i.e cell delay in the
`Leaky Bucket Queues of the conceptual model), and
`
`• cell delay in the Output List (i.e. cell delay in the output
`multiplexer of the conceptual model).
`
`The following remarks refer to_ these three components:
`
`Leaky Bucket cell loss can be controlled to an arbitrary
`degree, using inequality (1) above, and therefore needs no
`further investigation here.
`
`The cell delay experienced by a cell stream due to the
`spacing effect of the Leaky Bucket Queues is relatively well
`understood since it is exactly that of the deterministic service
`time queue (see e.g. [10]). Qualitatively speaking this delay
`is influenced by two factors: the ratio r/re of actual source
`cell rate to· the policing cell rate and the amount of jitter
`accumulated up to the spacing device~. Th~ influence of r/r c ,
`which is the load on the qu~tle, .is: that the smaller it is the
`lower the delay will be. In a CB,R:ce9,nn¢ction spaced with
`r = r0 all cells will be delayed in th'p:·l;i;_aky Bucket Queue so
`
`that they exit with the same total delay as that cell of the
`connection which has experienced the highest delay so far. It
`is therefore always necessary to have a tolerance on the
`policing cell rate over the negotiated cell rate of a few
`percent to ensure that the Leaky Bucket Queue always
`empties reasonably quickly.
`
`While the Leaky Bucket queue does not completely
`empty the traffic at its output is periodic. Whenever the
`Leaky Bucket Queue empties then the phase of the periodic
`stream, once it resumes, will have changed. Thus if a source
`transmits with a mean cell rate close to the policed cell rate
`then the traffic after the Leaky Bucket Queue will be a
`periodic stream with occasional phase shifts, whatever the
`arrival process before the queue may be. Therefore we
`postulate that the delay in the Output List (the output
`multiplexer delay in Fig. 1) is similar to the delay of a
`2;Di/D/l queue. However, the more gaps there are in the
`incoming periodic streams, the smaller the delay will be.
`Experiments were carried out to verify this hypothesis.
`
`'al 10 -
`~ =
`" E
`-
`;::
`-
`"' c
`-
`~
`~
`
`1_
`
`= -f-
`
`a
`
`f-
`
`I 1111111
`10
`
`I 1111111
`100
`Number of VCs -
`
`I 1111111
`1()00
`
`10-5 Quantile
`Sta~d~rd
`Mean
`.
`Deviation of of
`Waiting Time Waiting Time Waiting Time
`
`nD/D/1 - -
`
`Spacing
`Polle er
`Simulation
`
`a
`
`Fig. 4 Cell delay in the Output List. Load 0.8 on the
`inlet line of the Spacing Policer produced by a multi(cid:173)
`plex of identical Bernoulli sources.
`
`A simulation of the Spacing Policer was fed with a
`multiplex of n statistically identical Bernoulli sources (with
`values of n between 2 and 100) producing a total load of
`80%. For every n the policing cell rate re was adapted to the
`source cell rate such that rcfr s 1.02. The distribution of the
`delay in the Output List was recorded. As figure 4 shows, the
`delays experienced are very similar to (slightly better than)
`the delays of the nD/D/1 queueing model [11 ]. These results
`refer to averages takeri over all VCs being spaced. In the
`presence of bursty sources which send short bursts violating
`the allowed peak rate well behaving sources may experience
`even smaller delays at the cost of the misbehaving sources
`due to the strategy used to link the time slot queues to the
`Output List. (This strategy was described in Section 4).
`
`AS.5
`
`!SS '92, October 1992, Vol. 2
`
`•
`
`

`

`26
`
`THE SPACING POLICER. AN ALGORITHM FOR EFFICIENT PEAK BIT RATE CONTROL IN ATM NETWORKS
`
`7. POLICING OF CONNECTIONS INVOLVING
`TWO LEVELS OF PRIORITY
`
`APPENDIX
`
`At CCITI (cf. [6]) two UPC schemes are under
`discussion for virtual connections that involve two levels of
`priority as indicated by the cell lpss priority (CLP) bit in the
`cell header.
`
`• Scheme 1: Separate policing of the high priority cell
`stream (CLP=O) and the combined cell stream (CLP=O or
`CLP=l) containing high and low priority cells.
`
`• Scheme 2: Separate policing of the CLP=O stream and the
`CLP=l stream.
`
`In scheme 1 the combined cell stream (CLP=O or
`CLP=l) can be monitored by a Spacing Policer. In addition a
`simple Leaky Bucket counter can be used to monitor the
`CLP=O stream. Scheme 1 has the disadvantage that cells are
`discarded regardless of their priority if the combined cell
`stream does not conform to the contract.
`
`Figure 5 shows how policing and cell spacing can be
`combined in Scheme 2. In this scheme the high priority
`traffic flow and the low priority traffic flow are first policed
`separately at Pl and P2, respectively. Simple pick up
`policing devices e.g. Leaky Bucket counters can be used for
`peak cell rate policing. Excess cells with CLP=O are
`discarded or (alternative option) tagged, i.e. the CLJ? bit is
`changed from 1 to 0. Excess cells with CLP=l are always
`discarded. After policing,
`the combined cell stream is
`spaced. In this scheme the Spacing Policer is mainly used for
`spacing - normally there will be no cell discarding in the
`Spacing Policer. The cell rate allowed by the Spacing Policer
`may be chosen independently from the policed cell rates at
`Pl and P2. Thus the maximal cell rate allowed by the
`spacing function can be chosen slightly higher than the
`policed cell rate in order to keep the delay due to cell
`spacing small.
`
`~
`
`I
`
`SP
`Pl
`
`Spacing Policar
`
`Policing of high priority flow = Cell discard
`
`P2
`
`Policing of low priority flow
`
`Fig. 5 UPC scheme for separate control of high and
`low priority cell streams
`
`8. CONCLUSIONS
`
`is generally
`for a Spacing Function
`The need
`understood and we have presented an efficient algorithm for
`a combined policing and spacing function. The performance
`of the algorithm is that of the Spacing Policer of Fig. 1 with
`the output multiplexer producing less delay and jitter than
`one queueing stage in the network.
`
`ACKNOWLEDGEMENT
`
`This work was supp&te9 'by:· the. Commission of the
`European Communities u:nc!e,r:'._'RA.:CE project R1012
`"Broadband Local Node Techho\pgy·'.'
`
`Let us assume that the algorithm is implemented such
`that a cell which
`·
`i) gets to the head of the Output List in cell cycle n is
`transmitted in cell cycle n+ 1,
`ii) which enters in cell cycle n and is delayed for D (;;;,O) cell
`cycles enters the Output List in cell cycle n+D.
`
`We shall show that under these assumptions there is no
`cell loss due to lack of Cell Memory if NcM;;;, Dmax+ 1.
`
`To prove this it is sufficient to show the following
`assertion: Consider an arbitrary cell cycle n (i.e. a cell cycle
`where T = n mod NcA>· If the contents of the Cell Memory
`increases during the cell cycle n+ 1 (that means a cell is
`added to the Cell Memory but no cell is transmitted) then the
`number of cells stored in the Cell Memory at the end of cell
`cycle n is smaller than or equal to Dmax·
`
`Proof: During cell cycle n+ 1 no cell is transmitted, i.e.
`at the end of cell cycle n the output list is empty and all cells
`which are buffered in the Cell Memory at this time are
`. linked to a time slot queue. Since cells wait for at most Dmax
`cell cycles in a time slot queue all these cells must have
`entered the Spacing Policer after cell cycle n-Dmax• i.e. in
`the interval [n+l-Dmax• n]. In this interval, however, at most
`n - (n+l-Dmax)+l = Dmax cells can have entered the system.
`This implies that at most Dmax cells are buffered in the Cell
`Memory at the end of cell cycle n, which was to be proved.
`
`REFERENCES
`
`[l] P. Boyer, "A congestion control for the ATM," Proc.
`7th ITC Seminar, New Jersey, paper 4.3, Oct. 1990.
`[2] H. HeiB, "The Impact of Jitter on Peak CelL Rate
`Policing," Proc. 2nd RACE Workshop on Traffic and
`Performance Aspects in IBCN, Aveiro, Portugal, Jan.
`1992.
`[3] F. Guillemin, P. Boyer, A. Dupuis, and L. Romoeuf,
`"Peak rate enforcement
`in ATM networks," Proc.
`INFOCOM '92, pp. 753-758, May 1992.
`.
`[4] F. Guillemin, A. Dupuis, "A Basic Requirement for the
`Policing Function
`in ATM Networks," Computer
`Networks and ISDN Systems, vol.24, pp. 311-320 May
`1992.
`'
`[5] P. Boyer, Y. Rouaud, M. Servel, "Methode et systeme
`de lissage et de controle de debits de communications
`temporelles asynchrones," Demande de Brevet Euro(cid:173)
`peen, European Patent Office, 24.07.91, Bulletin 91/30.
`[6] CCITT Draft Recommendation 1.371, SG XVIII, Report
`R 91, Annex 3, Feb 1992.
`[7] E. Wallmeier, T. Worster, "A Cell Spacing and Policing
`device for Multiple virtual Connections on one ATM
`Pipe," Rl022 Technical Committee Workshop on ATM
`Network Planning and Evolution, London, April 1991.
`[8] G. Niestegge, "The 'Leaky Bucket' policing method in
`the ATM network," Int. J. of Digital & Analog
`Commun. Systems, Vol 3, pp 187-197, 1990.
`[9] G. · Gallassi, H. Hofstetter, T. Worster, "Telettaffic
`Studies on ATM in the Broadband Local Network
`Technology RACE Project,"
`in Teletraffic
`and
`Datatraffic in a Period of Change, ITC 13, A. Jensen
`and V.B. Iversen (eds), pp. 41-46, June 1991.
`[10] E. Rathgeb, "Modeling ·and Performance Comparison of
`Policing Mechanisms for ATM networks," JSAC vol. 9,
`pp. 325-334, April 1991.
`.
`.
`[11] J. W. Roberts, J. T. Virtamo, "The superposition of
`periodic cell arrival streams in an ATM multiplexer,"
`IEEE Trans. Commun., vol. 32, pp. 298-303, Feb. 1991.
`
`ISS '92. October 1992. Vol. 2
`
`AS.5
`
`! I
`I
`I
`I l
`j
`
`I !
`
`