United States Patent [191
`Spanke
`
`IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII
`USO05287347A
`[11]
`5,287,347
`Patent Number:
`[45] Date of Patent:
`Feb. 15, 1994
`
`[54] ARRANGEMENT FOR BOUNDING JI'ITER
`gs'égllm‘m'msm s I‘ HCHING
`
`5,179,549 1/1993 Joos et a]. ........................... .. 370/ 17
`FOREIGN PATENT DOCUMENTS
`
`[75] Inventor: Ron ,1 d A. spanke’ Wheaten, m-
`[73]‘ Assignee: AT&T Bell Laboratories, Murray
`Hill, NJ.
`
`_
`[21] A‘ppl' N°" 897300
`[22] Flled:
`Jun' 11’ 1992
`[51] Int. Cl.5 ........................................... .. H04L 12/54
`[52] US. Cl. ...' ................................... .. 370/60; 370/79;
`370/ 85.6
`[58] Field of Search .................. .. 370/17, 60.1, 79, 84,
`370/60, 85.6, 94.1, 94.2, 105.3; 375/118
`References Cited
`
`[56]
`
`U-S- PATENT DOCUMENTS
`3,428,946 2/1969 Batcher .......................... .. 340/1462
`4,516,238 5/1985 Huang et a1. .
`...... .. 370/60
`4'912»702 3/1990 vefbiest ----- --
`-- 370/34
`2,318???
`?nish """ "
`37307/
`5’083’269 V1992 S;:bat';]'<'é";t";i "" "
`‘395/125
`5:12l:383 6/1992 Golestani ....... .1":
`1370/60
`5,l32,966 7/1992 Hayano et a1.
`370/79
`5,150,358 9/1992 Punj et a1. ........................... .. 370/84
`
`H04L 12/56
`
`9104624 4/1991 World Int. Prop. 0.
`OTHER PUBLICATIONS
`H. Kuwahara at 211., “A Shared Buffer Memory Switch
`for an ATM Exchange”, IEEE Int’l. Conf on Comms,
`V01. 1 (Jun. 11-14, 1989), pp. 44.1-44.5.
`Primary Examiner-Benedict V. Safourek
`Assistant Examiner-Russell W. Blum
`Attorney, Agent, or Firm-Ross T. Watland
`
`ABSTRACI
`[57]
`An arrangement where a switching system receives
`parameter(s) concerning the traffic expected on a call
`from a ?rst user to a second user, the system determines
`a priority for the call based on the expected traf?c
`parameter(s). and information is transmitted to the sec
`end user during the call based on the determined prior
`ity and with less than a maximum jitter. The priority is
`selected from a predefined priority table based on ex
`pected traffic parameters. The priority table is usable
`for bmh °°n$tant bit rate and Statistical c3115
`
`14 Claims, 4 Drawing Sheets
`
`DATA
`
`{290
`IN
`vol
`
`USER CELL FORMAT
`
`{101%
`
`U1
`
`'-
`
`I
`
`11
`
`1 ,201
`RECOVER
`VASE)
`VCI
`I
`
`{202
`I—> CELL
`DROP UNIT
`
`1' 1 are.
`rm
`CELL
`COUNTER
`r211
`'-~ CVIEé’IIJ "“
`R
`{212
`I W
`-—- BUCKET H I—.
`ENFORCER
`{214
`PHYSICAL __
`'
`I "'“F DESTINATION
`TABLE
`
`I
`
`{215
`
`'-'*
`
`PRIORITY _-—'
`TAM
`
`I203
`ncsnnmou
`INFORMATION
`INSERTION
`UNIT
`
`l [204
`PRIORITY
`INFORMATTON
`INSERIION
`UNIT
`
`!
`
`I
`
`'
`
`NEWIZIS
`.
`_’ Va (“30 .—
`TABLE
`
`-
`
`I ,205 '
`VCI (VPI)
`Wm“
`L___
`
`102-1
`
`107~
`_
`‘3g FRI DEST
`W 0m
`CONTROLLER
`109
`WEN CELL FORMAT
`
`{291
`
`Ericsson Exhibit 1010
`Page 1
`
`

`

`U.S. Patent
`
`Feb. 15, 1994
`
`Sheet 1 of 4
`
`5,287,347
`
`_ ,103
`INTERCONNECTTON
`ARRANGEMENT 102-1 10: 1 111-1
`HLTER
`
`_
`
`1
`
`.
`
`‘
`,
`102-8 10H 111-8
`102-1
`2
`112-1
`H TER
`L
`
`‘
`‘
`102-8 1044 112-8
`102-1
`1
`118-1
`HLTER
`
`,105-1
`PRguRTlgllNG
`UT ->U1
`OUEUE
`
`,105-2
`PRIORITIZING
`OUTPUT —>U2
`OUEUE
`
`,105-3
`PRIORITIZING
`OUTPUT —>U3
`QUEUE
`,105-4
`PRIORTTIZING
`OUTPUT —>U4
`QUEUE
`
`102-1
`’
`'
`
`FIG. 1
`l°—°
`,101-1
`INPUT
`U1--PR0cEssINc
`UNIT
`1
`;101-2
`102-21
`INPUT
`U2—-PR0cEssIN0 T P
`UNII
`1
`;101-3
`INPUT
`U3—- PROCESSING
`UNIT
`1
`,101-4
`INPUT
`U4 - PROCESSING
`UNIT
`t
`[101-5
`INPUT
`U5 - PROCESSING
`UNrr
`1
`;101-6 ,'
`|NPUT
`102-6
`U8- PROCESSING
`’
`UNIT
`.
`1
`,101-7 '
`INPUT
`102-7
`U7 - PROCESSING
`*
`UNIT
`t
`,101-8 '
`|NPUT
`,102-8
`PROCESSING
`P
`UNrI
`
`I
`'102-3
`’
`
`1
`102-4
`?
`
`.
`
`'
`102-5
`’
`
`I
`
`l
`
`I
`
`'
`
`108 1
`2
`
`107
`I
`
`T
`T
`102-8
`_ 113-8
`102-1 1°’; ‘’ 114,-1
`H
`LTER
`
`I
`l
`102-8 1044, 114-8
`102-1
`2
`118-1
`FILTER
`
`1
`
`J'108-5
`PRgORITIZING
`UTPUT ->U5
`QUEUE
`
`I
`I
`102-8 1044; 115-8
`,102-1
`2
`1113-1
`
`1105—6
`PRIORITIZING
`OUTPUT —>U6
`QUEUE
`
`‘
`I
`102-8 1044 116-8
`1102-1
`1
`111-1
`
`FILTER
`
`FILTER
`
`,105-7
`PRIORITIZING
`OUTPUT —>U7
`QUEUE
`
`,
`‘
`l102-8 1W8 117-8
`102-1
`1
`118-1
`
`;105—8
`PRIORITIZING
`OUTPUT
`QUEUE
`
`FILTER
`
`,
`102-8
`
`—
`109 J
`i
`CONTROLLER
`
`I
`118-8
`
`108
`2
`
`Ericsson Exhibit 1010
`Page 2
`
`

`

`US. Patent
`
`Feb. 15, 1994
`
`Sheet 2 of 4
`
`5,287,347
`
`U1
`
`-
`
`DATA
`
`,290
`IN
`VCI
`
`USER CELL FORMAT_
`INPUI PRQQESSINQ QNIT
`
`{101A
`
`COUNTER
`
`_ VAUDITY <—
`' CHECKER
`;212
`LEAKY
`; BUCKET
`ENFORCER
`{214
`PHYSICAL :
`: DESTINATION
`TABLE
`
`'
`
`.
`
`'
`
`I
`
`I
`
`= P?gi'g ‘
`
`IIIIIII;
`
`VALUE
`
`' ,202
`I—- CELL
`I——- DROP uNIT
`
`I203
`DESTINATION
`, INFORMATION
`INSERTION
`UNIT
`
`I
`
`II J’
`PRIORITY
`INFORMATION
`INSERTION
`UNIT
`
`'
`
`.
`
`1216
`NEW
`> VCI (VPI) T
`
`I, ,205 '
`
`‘'0' (VP')
`
`-
`
`107~
`
`102-1
`2
`‘ )
`
`{291
`
`TO/FROM
`CONTROLLER
`109
`
`DATA
`
`VCI
`
`PRI DEST
`
`SYSTEM CELL FORMAT
`
`FIG. 2
`
`Ericsson Exhibit 1010
`Page 3
`
`

`

`US. Patent
`
`Feb. 15, 1994
`
`Sheet 3 of 4
`
`5,287,347
`
`111-1
`a
`
`?
`111-8
`
`_
`
`__
`
`,105-1
`
`W
`r314
`
`>u1
`
`I
`
`|
`
`SORT
`NETWORK
`
`.
`a
`:313-1
`(R)
`'313-R
`I
`
`,
`3
`312-1 1
`(R)
`312-R I
`a
`.
`
`1
`
`;315
`
`e
`.
`312-1 1
`(*3)
`31.7é-R -
`
`DELAY
`UNIT
`
`.
`2
`: 313-1
`('3)
`; 313-R
`
`FIG. 3
`
`Ericsson Exhibit 1010
`Page 4
`
`

`

`US. Patent
`
`Feb. 15, 1994
`
`Sheet 4 of 4
`
`5,287,347
`
`’
`
`I
`
`4a BYTE DATA
`PARAMETERS
`
`5 BYTE
`HEADER
`V
`
`‘
`
`ATM
`MEssAcE
`ATM
`vc|=1
`ADAPTION DATA REQUESTED ExPEcTED EXPECTED TYPHALL ADAPTION
`SIGNALLING
`A LAYER
`DESTINATION BuRsTTNEss
`BW
`SEEUP
`LAYER
`PROTOCOL
`PROTOCOL
`
`‘(a BYTES) A (3 BYTES) “(T BYTES)’
`
`15 DTDTT
`TELEPHONE
`NUMBER
`
`<64 kB/SEC
`=CBR
`1
`To
`2 To _
`100's 'BURSnNESS 2.4 GB/SEC
`
`CALL sETuP CELL = 53 BYTEs LONG (ATM)
`F I G. 4
`
`ATM
`ADAPTION
`LAYER
`PROTOCOL
`
`DATA
`
`ATM
`Apgggkm ADAPTION
`55mm ECHO
`NUMBER PARAMETERS (YES OR No)
`LAYER
`PROTOCOL
`
`vc|=1
`SIGNALLING
`
`SETUP RESPONSE CELL
`FIG. 5
`
`Ericsson Exhibit 1010
`Page 5
`
`

`

`1
`
`ARRANGEMENT FOR BOUNDING JI'ITER IN A
`PRIORITY-BASED SWITCHING SYSTEM
`
`TECHNICAL FIELD
`This invention relates to communications systems.
`
`5,287,347
`2
`applications resulting in excessive queuing delays and
`very large buffer buildouts on the receiving end.
`In view of the foregoing, a recognized need in the art
`exists for an arrangement usable in ATM or other
`packet switching systems which will bound jitter to an
`acceptable amount and which is applicable to both con
`stant bit rate and statistical traf?c.
`
`BACKGROUND OF THE INVENTION
`The term broadband covers a host of new products,
`technologies, services, and networks. One way to de?ne
`broadband networks is to categorize them as those net
`works that support services requiring bit rates well
`above one megabit per second. Business and residential
`subscribers will be connected to broadband networks
`via a common access, operating at 150 megabits per
`second or above, that can handle a range of different
`broadband service types. ATM (asynchronous transfer
`mode) has been chosen as the communication principle
`on which broadband networks will be based. A future
`broadband ISDN (integrated services digital network)
`will offer the ?exibility needed to handle diverse ser
`vices ranging from basic telephone service to high
`speed data transfer, videotelephony, and high quality
`television distribution. The key to this ?exibility is
`ATM which carries digital information in special cells.
`This allows the network to be used ef?ciently by appli
`cations and services with widely differing bandwidth
`requirements and call characteristics.
`Priority-based systems have been designed for
`switching ATM cells or performing other packet
`switching functions. In such systems, all cells (packets)
`for a given priority are transmitted to their destination
`before the ?rst cell of the next lower priority. Within a
`given priority, cells are transmitted on a ?rst come-?rst
`serve basis. All equal priority cells arriving at a given
`cell time are transmitted before the same priority cells
`arriving at the next cell time are started. This becomes
`the root cause of jitter because one high bandwidth call
`could have a cell arriving every other cell time; all of a
`sudden, ten or twenty cells from other calls and having
`the same priority as the one high bandwidth call arrive
`in one of the open cell times. All ten or twenty of these
`cells will be transmitted before the next cell of the high
`bandwidth call causing an absolute jitter of ten or
`twenty cell times. During this interval, cells for the high
`bandwidth call keep arriving every other cell time and
`are queued up. When the high bandwidth call does
`begin transmitting its cells again, they will be transmit
`ted every cell time, back-to-back, until the queue is
`empty. Not only is such jitter unacceptable in many
`50
`applications, substantial resources are required for buff
`ering and receiver buildout delay.
`In addition to being important in constant bit rate
`applications, jitter is also an important parameter for
`statistical (bursty) traf?c. Variable bit rate video re
`quires very low delay, has very high bandwidth and
`relatively low burstiness. Variable bit rate voice also
`requires moderately low delay, has relatively low band
`width and low burstiness. Both of these applications
`must have relatively low jitter to guarantee that cells do
`60
`not arrive “too late” and the buffer at the receiving end
`does not become empty. Even though this is statistical
`traf?c, it is jitter sensitive.
`Other applications, including ?le transfers and screen
`image dumps, do not typically require low delay. Such
`applications can have either low or high average band
`width; however, they are very bursty. Such applica
`tions could signi?cantly interrupt the delay sensitive
`
`SOLUTION
`This need is met and a technical advance is achieved
`in accordance with the invention in an exemplary ar
`. rangement where a switching system receives parame
`ter(s) concerning the traf?c expected on a call from a
`?rst user to a second user, the system advantageously
`determines a priority for the call based on the expected
`traf?c parameter(s), and information is transmitted to
`the second user during the call based on the determined
`priority and with less than a maximum jitter. The prior
`ity is selected from a predefined priority table based on
`the expected traf?c parameters. Signi?cantly, the same
`priority table is usable for both constant bit rate and
`statistical calls.
`A method in accordance with the invention is usable
`in a switching system serving a number of users. The
`system receives one or more parameters concerning the
`traf?c expected on a call from a ?rst user to a second
`user. The system transmits information to the second
`user during the call based on the expected traf?c param
`eters and with a maximum jitter.
`In an illustrative method, when the call is a constant
`bit rate call, the expected traf?c parameters include a
`bandwidth parameter, BW, and the priority is deter
`mined based on BW. The priority is selected from a
`priority table having a number, P, of priority bands and
`having a maximum bandwidth, BWm-gh, and a minimum
`bandwidth, BWLOW, speci?ed for each band. The ratio
`BWHigh/BWLWis a constant. The priority is selected by
`determining the band that includes BW. The maximum
`jitter is a worst case relative jitter. The constant bit rate
`call is made up of ?xed length cells and the worst case
`relative jitter, in intercell arrival periods, is given by the
`constant ratio, BWHfgh/BWLQW- (The terms “relative
`jitter” and “intercell arrival period” are described later
`herein.) If the priority table is used for constant bit rate
`calls only, it may include one additional priority band
`below the P priority bands and P and BWHigh/BWLW
`satisfy a relationship [BwHigh/BwMw]P= BWIF/BW
`Min, where BWIF and BWM,I are the maximum and
`minimum bandwidths between each of the users and the
`switching system.
`In a further illustrative method, the priority table is
`used for both constant bit rate calls and statistical calls.
`When the call is a statistical call, the expected traf?c
`parameters include an average bandwidth parameter,
`BW,;,;, and a burstiness index, BI, and the priority is
`determined by determining the band in the priority table
`that includes the ratio BwAvg/BI- The statistical call is
`made up of ?xed length cells and the worst case relative
`jitter, in intercell arrival periods, is given by the product
`of BI and the constant ratio, BWHigh/BWLOW- P and
`BWHigh/BWLDW satisfy a relationship [BWHigh/B
`WMw]P=BW11-'*BIMax/BWM,',,, where BW 1F and
`BWM;n are the'maximum and minimum bandwidths and
`BIMU is the maximum burstiness between each of the
`users and the switching system.
`
`40
`
`45
`
`SS
`
`65
`
`Ericsson Exhibit 1010
`Page 6
`
`

`

`DRAWING DESCRIPTION
`FIG. 1 is a diagram of an exemplary priority-based
`switching system which includes an arrangement for
`bounding jitter;
`FIG. 2 is a diagram of an input processing unit in
`cluded in the system of FIG. 1;
`FIG. 3 is a diagram of a prioritizing output queue
`included in the system of FIG. 1;
`FIG. 4 is a diagram of a call setup cell transmitted
`from users to the system of FIG. 1; and
`FIG. 5 is a diagram of a setup response cell transmit
`ted from the system of FIG. 1 to system users.
`
`10
`
`5,287,347
`4
`3
`virtual circuit identi?er (V CI) or virtual path identi?er
`In both illustrative methods, cells received from the
`(V PI) followed by data. A VPI comprises several VCls.
`?rst user during the call are dropped when the cells
`In ATM, cells are 53 bytes in length. Within input pro
`cause the expected traf?c parameters to be exceeded.
`cessing unit 101-1(FIG. 2), a cell is received by a unit
`201, the VCI(VPI) is recovered and transmitted to va
`lidity checker 211, leaky bucket enforcer 212, cell
`counter 213, physical destination table 214, priority
`table 215 and new VCI(VPI) table 216. Validity
`checker 211 determines whether the VCI(V PI) is valid
`based on information received from controller 109 via
`path 107; if the VCI(VPI) is not valid, it causes a cell
`drop unit 202 to drop the cell. Leaky bucket enforcer
`212 receives expected traf?c parameters, for example,
`expected bandwidth and expected burstiness index, and
`when enforcer 212 determines that a cell of a given
`virtual circuit results in the parameters being exceeded,
`it causes cell drop unit 202 to drop the cell. A cell
`counter 213 simply counts cells in each virtual circuit,
`and reports such counts to controller 109. A physical
`destination table 214 receives information from control
`ler 109 de?ning the destination associated with each
`virtual circuit, and, based on the VCI(V PI), causes a
`destination information insertion unit 203 to insert the
`destination information in each cell. A priority table 215
`receives a priority value from controller 109, and based
`on the VCI(VPI), causes a priority information inser
`tion unit 204 to insert the priority information in each
`cell. A new VCI(VPI) table 216 receives a new
`VCI(V PI) value and causes a VCI(VPI) overwrite unit
`205 to overwrite the incoming VCI ?eld of the user cell
`format 290 with an outgoing VCI in the system cell
`format 291. Format 291 also includes a destination ?eld
`as well as a priority ?eld.
`Cells transmitted by input processing unit 101-1
`(FIG. 1) are distributed via path 102-1 of interconnec
`tion arrangement 103 to all of the ?lters 104-1 through
`104-8. Cells destined for user U1 are transmitted by
`?lter 104-1 via paths 111-1 through 111-8 to prioritizing
`output queue 105-1. Queue 105-1 (FIG. 3) includes a
`sort network 314 which can be constructed in the man
`ner described, for example, by Batcher in U.S. Pat. No.
`3,428,946 issued Feb. 18, 1969, or as described by
`Huang et al., in U.S. Pat. No. 4,516,238 issued May 7,
`1985. Sort network 314 sorts received cells in accor
`dance with the priority ?eld, and transmits the highest
`priority cell to user U1. The remaining cells are trans
`mitted via paths 313-1 through 313-R(R, being a large
`number, e.g., greater than 1000) to delay unit 315,
`which provides a one cell time delay, and transmits the
`delayed cells back to sort network 314 via paths 312-1
`through 312-R. By operation of sort network 314, older
`cells within a given priority are transmitted to user Ul
`before newer cells.
`The manner of operation of queue 105-1 can be better
`understood by considering the example of Table l with
`four active virtual circuits VCI1 through VCI4 having
`priorities 1 through 4, respectively.
`
`DETAILED DESCRIPTION
`Switching System 100
`FIG. 1 is a diagram of an exemplary priority-based
`switching system 100 which includes an arrangement
`for bounding jitter in accordance with the present in
`vention. The switching function is performed within
`system 100 by ?lters 104-1 through 104-8 and prioritiz
`ing output queues 105-1 through 105-8. System 100
`serves seven users U1 through U7. Input processing
`units 101-1 through 101-8 process cells from users U1
`through U7 as well as cells from a controller 109 which
`controls the operation of system 100. The processing
`performed by processing units 101-1 through 101-8 is
`described further herein. Controller 109 communicates
`with users U1 through U7 by transmitting cells via path
`108 to processing unit 101-8 and on through system 100
`to the desired destination user. One of the functions of
`controller 109 is to determine a priority value for each
`virtual circuit set up between users based on parameters
`received from the users concerning the expected traffic.
`Such priority values are communicated from controller
`109 to processing units 101-1 through 101-8 via a path
`107 and are inserted in each cell of a virtual circuit for
`transmission within system 100. Cells from all of the
`input processing units 101-1 through 101-8 are distrib
`uted to each of the eight ?lters 104-1 through 104-8 via
`paths 102-1 through 102-8 of an interconnection ar
`rangement 103. Each of the ?lters 104-1 through 1048
`only transmits cells having a speci?c destination. For
`example, ?lter 104-1 only transmits cells having the user
`U1 as a destination. Since it is possible that as many as
`eight cells are received at the same cell time destined for
`U1, there are eight paths 111-1 through 111-8 between
`?lter 104-1 and queue 105-1. Filter 104-8 only transmits
`cells having controller 109 as a destination. There are
`eight paths 118-1 through 118-8 between ?lter 104-8 and
`queue 105-8. Queues 105-1 through 105-8 each transmit
`cells in priority order as described further herein.
`Cells are received from user U1 in format 290 shown
`in FIG. 2. Format 290(FIG. 2) includes an incoming
`
`35
`
`TABLE 1
`Bounded Jitter Example
`* = expected/
`VCI l VCI 2 VCI 3 VCI 4
`# : actual
`Queue Length
`50%
`33%
`5%
`2.5%
`Bl = 2 B] = 3 Bl = 1 Bl = 1 Fri Pri Pri Pri Output Pri Pri Pri Pri
`
`
`
`Time Pri 1 O .
`
`
`
`Fri 2
`
`
`
`Fri 3 .
`
`
`
`Fri 4 .
`
`
`
`l 0
`
`
`
`2 O
`
`
`
`3 0
`
`
`
`4 0
`
`
`
`Priority Idle
`
`1
`
`2
`
`l
`l
`.
`
`1
`2
`3
`4
`
`3
`.
`
`4
`.
`
`l
`l
`0
`O
`
`l
`2
`3
`2
`
`l
`l
`l
`l
`
`l
`l
`l
`l
`
`l
`l
`2
`2
`
`‘l
`l
`"‘
`
`l“
`
`2
`"“2
`
`3
`
`‘'
`
`Ericsson Exhibit 1010
`Page 7
`
`

`

`5,287,347
`
`5
`TABLE l-continued
`Mm
`' = expected/
`VCI 1 VCI 2 VCI 3 VCI 4
`# = actual
`Queue Length
`50%
`33%
`5%
`2.5%
`51:2 81:3 31:1 Bl=l Pri Pri Pri Prl Output Pri Pri Pri Pri
`Time Fri 1
`Fri 2
`Pri 3
`Pri 4
`1
`2
`3
`4
`Priority
`1
`2
`3
`4
`
`6
`
`l
`l
`.
`.
`1
`1
`.
`.
`1
`1
`.
`.
`1
`1
`.
`
`1
`l
`.
`.
`1
`1
`.
`
`1
`1
`.
`.
`1
`1
`
`1
`1
`
`.
`1
`1
`
`1
`1
`
`1
`1
`
`1
`1
`
`1
`1
`
`5
`6
`7
`8
`9
`10
`11
`12
`l3
`14
`15
`l6
`17
`1s
`19
`20
`21
`22
`23
`24
`25
`26
`27
`2s
`29
`30
`31
`32
`33
`34
`35
`36
`37
`3s
`39
`40
`41
`42
`43
`44
`45
`46
`47
`4s
`49
`50
`51
`52
`53
`54
`55
`56
`57
`5s
`59
`6O
`
`.
`.
`.
`.
`2
`2
`2
`.
`.
`.
`1
`.
`.
`2
`2
`2
`
`.
`.
`.
`2
`2
`2
`
`.
`.
`.
`2
`2
`2
`.
`
`.
`.
`2
`2
`2
`
`.
`2
`2
`2
`
`.
`3
`
`3
`
`4
`
`l
`l
`l
`l
`l
`l
`l
`l
`1
`1
`1
`o
`1
`1
`0 0
`1
`1
`0 0
`1
`1
`1
`0
`1
`0
`2
`0
`1
`0 2
`0
`l
`l
`l
`0
`1
`1
`1
`0
`1
`0
`1
`0
`0 0 0 1
`1
`0 0 0
`1
`0 0 0
`0 1
`o 0
`0
`1
`0 0
`1
`1
`1
`0
`l
`l
`l
`0
`0
`1
`1
`0
`0 0
`1
`0
`1
`0
`0
`0
`1
`0 0
`o
`0
`0
`0 0
`o
`1
`o
`0
`1
`1
`0
`o
`1
`2
`0 0
`0
`2
`0
`0
`0
`1
`0
`0
`1
`0
`0
`0
`1
`0
`0
`0
`0
`0
`0
`0
`0
`o
`0
`0
`1
`1
`0 0
`1
`2
`0
`0
`0
`3
`0
`0
`0
`2
`0
`0
`1
`1
`1
`1
`1
`1
`1
`1
`0
`1
`1
`1
`0
`0
`1
`1
`1
`0
`0
`1
`1
`1
`0
`1
`0
`2
`0
`1
`0
`2
`0
`1
`1
`1
`0
`1
`1
`1
`0
`1
`0
`1
`0
`1
`0
`0
`0
`1
`1
`0
`0
`0
`1
`0
`0
`0
`0
`1
`o 0
`0
`1
`0
`0
`1
`1
`0
`0
`1
`1
`o
`0
`0
`1
`0 0
`0
`o
`0
`0
`
`l
`l
`2
`3
`1
`1
`2
`2
`l
`1
`2
`4
`1
`1
`2
`2
`1
`l
`2
`3
`1
`1
`Idle
`2
`1
`1
`2
`2
`1
`1
`Idle
`Idle
`1
`1
`2
`2
`1
`1
`2
`3
`1
`1
`2
`2
`1
`1
`2
`4
`1
`1
`2
`2
`1
`1
`2
`Idle
`
`‘l
`l
`'
`
`'1
`1
`'
`
`'l
`1
`'
`
`'1
`1
`'
`
`'1
`l
`'
`
`'1
`1
`'
`
`'1
`1
`‘
`
`'1
`1
`'
`
`*1
`1
`'
`
`'1
`1
`'
`
`‘1
`1
`*
`
`'1
`1
`'
`
`'1
`1
`'
`
`'1
`1
`'
`
`'2
`
`3
`
`4
`
`'
`
`3
`
`'
`
`'
`
`3
`
`4
`
`~
`2
`2
`'
`
`2
`'
`
`'2
`2
`
`'
`2
`
`'
`
`'2
`
`'2
`2
`
`'
`
`*
`
`2
`'2
`
`'2
`
`'
`2
`2
`r
`
`2
`'
`
`'2
`2
`
`'
`2
`
`Note that virtual circuits VCl, VC2, VC3, and VC4
`have occupancies of 50%, 33%, 5%, and 2.5%, respec
`tively, and the expected cell arrivals (assuming constant 55 1 cells, respectively, the output priority is 2, and the cell
`transmitted is in virtual circuit VC2. Note that all cells
`bit rate traffic) corresponding to those occupancies are
`are transmitted within (2 times BI) expected intercell
`shown by asterisks on the right in Table 1. Virtual cir
`arrival periods from the expected arrival times. The
`cuits VCl, VC2, VC3, and VC4 have burstiness indices
`maximum jitter in this example is (2 times BI) expected
`of 2, 3, l, 1, respectively (burstiness index is discussed
`intercell arrival periods.
`later herein). Note that at cell time 1, cells are received
`An illustrative call setup cell received from a user,
`in virtual circuits 1, 2, 3, and 4, priorities 1, 2, 3, and 4
`e.g., user U1, is shown in FIG. 4. The ?ve-byte header
`have 1 cell each, the output priority is l, and the cell
`de?nes that VCI= l, which defines the cell as a signal
`transmitted is in virtual circuit VCl. At cell time 2, cells
`ling cell. VCII is prede?ned as a valid VCI in checker
`are received in virtual circuits 1 and 2, priorities 1, 2, 3,
`211(FlG. 2), as having controller 109 as the destination
`and 4 have 1, 2, l, and 1 cells, respectively, the output
`in table 214, and having a new VCI in table 216 for
`priority is again l, and the cell transmitted is again in
`insertion in the system cell format. That new VCI also
`virtual circuit VCl. At cell time 3, a cell is received in
`serves as a source identi?er. At the beginning and end of
`virtual circuit 2, priorities 1, 2, 3, and 4 have 0, 3, l, and
`
`65
`
`Ericsson Exhibit 1010
`Page 8
`
`

`

`5,287,347
`
`8
`Cell Jitter for CBR Traffic
`A CBR channel at a given frequency expects a cell to
`arrive periodically with a given inter-cell spacing. As an
`example, on a 2.488 Gb/s interface, a 100 Mb/s video
`call is set up. This call expects to receive a cell every 25
`cell times. This 25 cell period is de?ned as the expected
`intercell arrival period. Due to contention and queuing
`in the ATM (asynchronous transfer mode) fabric, the
`cell may not be output exactly when it is expected.
`“Absolute Jitter” is de?ned as the amount that the ac
`tual cell arrival time differs from the expected cell ar
`- rival time.
`A low bandwidth virtual channel with an expected
`interarrival time of 2000-3000 cell times would not be
`signi?cantly affected by an absolute jitter of 300-500
`cells, whereas a 300-500 cell absolute jitter would be
`devastating to a high bandwidth virtual channel that
`expected a cell every 2-3 cell times. A more representa
`tive term is the “Relative Jitter”. Relative Jitter is de
`?ned as follows:
`
`55
`
`7
`the 48-byte data portion of the call setup cell(FlG. 4)
`are ?elds enclosing the remaining data in an ATM adap
`tion layer protocol. The data includes a message type
`de?ned as call setup, and three parameters-the ex
`pected bandwitdth (seven bytes), the expected bursti
`ness (three bytes), and the requested destination tele
`phone number (eight bytes). The call setup cell is con
`veyed via interconnection arrangement 103, ?lter 104-8,
`and queue 105-8 to controller 109. Controller 109 uses
`the expected bandwidth and expected burstiness to
`assign a priority to the call by using a table of the type
`shown herein as Table 4. If the call is a constant bit rate
`(CBR) call (having B1 = l), the priority is determined by
`placing the expected bandwidth in one of the ranges of
`the table. If the call is statistical call (having BI > 1), the
`expected bandwidth is an average bandwidth, BWAVK,
`and the priority is determined by placing BwAyg/BI in
`one of the ranges of the table. Controller 109 also per
`forms a translation on the requested destination tele
`phone number to obtain a physical destination, e.g., user
`U5, and assigns a VCI for use by user U1 and a VCI for
`use by user US for the call. Controller 109 returns a
`setup response cell of the type shown in FIG. 5 via path
`108, processing unit 101-8, interconnection arrangement
`103, ?lter 104-1, and queue 105-1 to user U1. The setup
`response cell indicates whether the requested call has
`been approved, echoes the parameters, and de?nes the
`assigned VCI to be used subsequently by user U1 for the
`call. Controller 109 returns a similar setup response cell
`to user U5. Controller 109 transmits information via
`path 107 and input processing unit 101-1 to validity
`checker 211 (FIG. 2) de?ning the assigned VCI as
`valid, to enforcer 212 de?ning the bandwidth and bur
`stiness parameters for the assigned VCI, to table 214
`de?ning the physical destination associated with the
`assigned VCI, to table 215 de?ning the priority associ
`ated with the assigned VCI, and to table 216 de?ning
`the outgoing VCI to be used for incoming cells having
`the assigned VCI. If a return interconnection from user
`US to user U1 is also set up, controller 109 uses the
`bandwidth and burstiness parameters for the return path
`to calculate the priority for the return path. Controller
`109 transmits similar information via path 107 to pro
`cessing unit 101-5 (FIG. 1) to set up the return path.
`Bounding Cell Jitter Using Priority Levels
`The following description provides background in
`formation on the number of delay priority levels re
`quired for an exemplary ATM fabric. It discusses the
`phenomenon of cell jitter for CBR (constant bit rate)
`traf?c and shows how this maximum cell jitter can be
`bounded by allocating a priority level to a range of
`frequencies. Based on these results, the number of prior
`ity levels required for CBR traf?c is determined. Statis
`tical traffic can also be characterized by jitter. Even
`though statistical VCs (virtual circuits) can tolerate a
`higher amount of jitter, this jitter must still be absolutely
`bounded for many statistical applications to function
`correctly. Statistical traffic can also be divided into
`priority levels. A uni?ed priority arrangement is de
`scribed which overlaps the CBR and statistical priori
`ties such that both CBR and statistical VCs exist in the
`same priority spectrum. The total number of priority
`levels required for this combined CBR and statistical
`traffic is determined to maintain reasonable upper
`bounds on cell jitter.
`
`Worst Case Absolute Jitter
`Relative Jitter =
`Expected lntercell Arrival Period
`
`This worst case relative jitter represents the maximum
`difference in earliest arrival to latest arrival that can be
`expected, compared to the expected intercell arrival
`time. A Relative Jitter of l to 2 expected intercell ar
`rival times would be very good. A relative jitter of
`many intercell arrival periods would be very poor, and
`would require signi?cant buffering at the receiver to
`insure that the playback data does not run out.
`Many CBR services such as audio or video expect the
`next cell to arrive at the expected time so they can begin
`displaying the information. A “just-in-time” cell arrival»
`would minimize the overall delay through the switch.
`However, because of cell jitter, just-in-time cell arrivals
`cannot be guaranteed, and the application is forced to
`queue up several cells on the receiving end to insure
`that the playback of information does not run out of
`data while waiting for the next ATM cell to arrive. To
`the extent that overall jitter in the switch can be re
`duced, this will also reduce the amount of buffering and
`receiver buildout delay required for CBR services.
`In a priority based fabric, all cells for a given priority
`will be output before the ?rst cell of the next lower
`priority. Within a given priority, cells are output on a
`?rst come-?rst serve basis. That is, all equal priority
`cells arriving at a given cell time will be transmitted
`before the same priority cells arriving at the next cell
`time are started. This becomes the root cause of jitter
`because one VC could have a cell arriving every other
`cell time; all of a sudden, ten or twenty cells having the
`same priority as the one VC but from different VCs
`arrive in one of the open cell times. All ten or twenty of
`these cells will be transmitted before the next cell of the
`high bandwidth VC, causing an absolute jitter of ten or
`twenty cell times. During this interval, cells for the high
`bandwidth VC keep arriving every other cell time and
`are queued up. When the high bandwidth VC does
`begin transmitting its cells again, they will be transmit
`
`ted every cell time, back-to-back, until the queue empty.
`
`Calculation of Possible Cell Jitter
`An upper bound for the worst case absolute and rela
`tive jitter can be determined by a simple technique. Cne
`
`Ericsson Exhibit 1010
`Page 9
`
`

`

`5,287,347
`
`9
`determines the highest bandwidth channel and the low
`est bandwidth channel that are allowed within a given
`priority band. For this technique, the highest BW VC
`has an upper limit of i of the total interface rate. This
`value will generate the worst case jitter. One computes
`the expected intercell arrival period for this highest
`bandwidth channel. One then computes N, the maxi
`mum number of the low bandwidth channels that can be
`active on the interface, along with the one highest band
`width channel. This is given by the following formula:
`
`L B Winter/‘ace _ B WHighert Allowed
`B Wum Allowed
`
`15
`
`The worst case jitter would occur when a cell from all
`N low bandwidth sources arrived just before a cell from
`the 1 high bandwidth source. The cell from the high
`bandwidth VC would have waited its average intercell
`arrival period, and then just before it was output, N
`cells from the low bandwidth VCs must be output be
`fore the next cell from the high bandwidth VC. The
`25
`actual interarrival interval between cells from the high
`bandwidth VC is the expected interarrival period+N
`cells. The Absolute Jitter is this actual interarrival inter
`val minus the expected interarrival interval, which is
`always just equal to N cell times. Relative Jitter is then
`the Absolute Jitter divided by the expected interarrival
`interval.
`Consider the following example. A 150 Mb/s inter
`face has only a single priority level and has no limit on
`how small a VG bandwidth can be. For this technique,
`the highest bandwidth VC is limited to i of the interface
`rate or 75 MB/s. This gives an expected intercell arrival
`time of 2 cells. (i.e. a cell should arrive every other cell
`time.) Now since there is no limit on the smallest VC
`bandwidth, assume that this bandwidth is 1/ do bits/sec.
`(i.e. very, very small). The number of these low band
`width sources that can be supported on the remaining
`75 Mb/s is therefore co. The worst case jitter would
`occur when a cell from all co VCs was received just
`before the cell from the high bandwidth VC resulting in
`an Absolute Jitter equal to N or 00 celltimes. The Rela
`tive Jitter is this co divided by 2 which is still 00. This
`unrealistic example is included merely to show that a
`single priority system with no lower bound on the VC
`50
`bandwidth will generate up to an no amount of relative
`jitter. Clearly this is to be avoided.
`Consider a more realistic example, still with a single
`priority system, but now a minimum VC bandwidth of
`55
`64 Kb/s is set. The maximum bandwidth VC allowed is
`75 Mb/s with an intercell arrival interval of 2 cells. The
`number of low bandwidth sources is N=(l50 Mb-75
`Mb)/64 Kb=ll7l. The absolute jitter is N=1l71 cell
`times. The relative jitter is ll7l/2=585 interarrival
`times. Again, a jitter this large is to be clearly avoided.
`Consider an example with multiple priorities and
`having a very restricted band. The highest BW allo