United States Patent c191
`Zheng
`
`I lllll llllllll Ill lllll lllll lllll lllll lllll 111111111111111111111111111111111
`US005392280A
`[11] Patent Number:
`[45] Date of Patent:
`
`5,392,280
`Feb. 21, 1995
`
`[54] DATA TRANSMISSION SYSTEM AND
`SCHEDULING PROTOCOL FOR
`CONNECTION-ORIENTED PACKET OR
`CELL SWITCHING NETWORKS
`
`[75]
`
`Inventor: Oin Zheng, Belmont, Mass.
`
`[73] Assignee: Mitsubishi Electric Research
`Laboratories, Inc., Cambridge, Mass.
`
`[21] Appl. No.: 224,671
`
`[22] Filed:
`
`Apr. 7, 1994
`
`Int. Cl.6 ............................................. H04L 12/56
`[51]
`[52] U.S. Cl •..................................... 370/60; 370/94.2;
`370/95.1
`[58] Field of Search ....................... 370/60, 60.1, 94.1,
`370/61, 110.1, 108, 85.1, 85.15, 95.1-95.3, 79,
`81, 111, 118; 340/825.05, 825.5, 825.51
`
`[56]
`
`References Cited
`U.S. PATENT DOCUMENTS
`4,587,650 5/1986 Bell ................................... 370/85.15
`4,637,014 1/1987 Bell et al .......................... 370/85.15
`4,763,321 8/1988 Calvignac et al .................. 370/85.1
`4,914,650 4/1990 Sriram ................................... 370/60
`Primary Examiner-Douglas W. Olms
`Assistant Examiner-Ajit Patel
`Attorney, Agent, or Firm-Robert K. Tendler
`[57]
`ABSTRACT
`In connection-oriented packet or cell switching net(cid:173)
`works, a data transmission system and scheduling proto-
`
`col utilizes both synchronous transmission and asyn(cid:173)
`chronous transmission in an alternating pattern to pro(cid:173)
`vide each user with both a guaranteed transmission
`bandwidth or capacity to accommodate real-time com(cid:173)
`munications, and bandwidth sharing among users to
`increase network utilization, while simultaneously elim(cid:173)
`inating network congestion to avoid data losses. The
`synchronous time slots provide for the bandwidth guar(cid:173)
`antees, while the asynchronous time slots are used to
`transmit data when a part of a previous synchronous
`time slot is not used. The asynchronous time slots also
`permit asynchronous data transmission using unal(cid:173)
`located time within a given time frame. In one embodi(cid:173)
`ment, time frames for data transmission are provided in
`which each time frame is composed of synchronous
`transmission
`times interspersed with asynchronous
`transmission times. For a given time frame, alternating
`synchronous and asynchronous transmission times are
`specified by a controller which determines the pattern
`of this alternation. In a preferred embodiment, the pat(cid:173)
`tern is altered using novel timed-round-robin schedul(cid:173)
`ing which transmits cells of data of respective connec(cid:173)
`tions over an outgoing link depending upon the syn(cid:173)
`chronous transmission time allocated to each connec(cid:173)
`tion. To avoid data losses, asynchronous transmission is
`permitted only when a downstream switch indicates
`sufficient buffer space to accommodate asynchronous
`transmission from an upstream switch.
`
`8 Claims, 16 Drawing Sheets
`
`10
`
`CEll BUFFER FORAN OUTGOING LINK
`i._. GTTI -J 26
`~
`
`14
`~--
`
`• I L....;;!._.._8...L...-...;~=---...1
`/<~>:>
`•
`j
`1-- ~n -I,_,/_/.//
`~ r
`.. /
`/
`f
`I
`.
`. ·
`/~s8~~:~·--_-·_··_··_···_··_··_··_···_··r·-~-·~··6~0~,..-··~-f-/_;~~3_,2
`14
`~: EMPIY QUEUE
`...
`IJEIECTOR
`
`•
`
`I
`
`0
`
`ASYNCHRONOUS
`12
`40~ TRANSMISSION
`GTT2
`/GTTI ~~~~~~ ......... ~~~
`SYNC. J.. SYNC. 18 CELL BUFFER FOR AN INCOMING LINK
`16
`r-"---: i-'-----
`1421 ~ I
`44
`1
`································· .... ····euff£R··--
`•
`occuPATION
`•
`•
`•
`•
`•
`
`22
`
`' ' ' ' '
`' ' ' '
`
`' ' ' ' ' ' ' ' ' ' ' ' ' ' ' '
`
`20
`
`•
`•
`•
`20
`
`Pet., Exh. 1016, p. 1
`
`

`
`QO =
`
`~
`~ ...
`\0
`CH
`...
`UI
`
`....
`a,
`~ ....
`ga
`
`Cl\
`
`~
`....
`~ .:-
`~ ?-
`
`'"'d I
`~ • 00 •
`
`20
`
`•
`•
`•
`
`..
`
`'
`
`20
`
`------------.. I
`
`' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' '
`
`OCCUPATION
`
`BUFFER
`
`•
`•
`•
`
`50
`•
`•
`•
`
`I ~ l~I M I
`I
`~~ 1
`) I CELL BUFFER FOR AN INCOMING LINK
`16 ~nE. <~m. 8 r-------L---
`
`I ,...22
`
`12
`
`40~ TRANSMISSION
`ASYNCHRONOUS
`
`,'
`
`,,"'
`
`j..-GlTn __.j , ,/ ,./
`
`r--
`j..-G1T2~
`
`36
`
`.
`.
`
`•
`
`24
`
`~Gm~
`CELL BUFFER FOR AN OUTGOING LINK
`
`34
`
`10
`
`I
`
`I
`
`e
`•
`•
`
`~-----
`14
`
`Fig. 1
`
`CELL TRANSMISSION SCHEDULER
`
`ASYN. TRANSMISSION
`
`CONTROl.LER
`
`I
`
`L
`32
`
`:
`/
`/
`/
`
`'
`
`/
`
`,'
`
`c:60
`--------------------------------'
`
`7
`
`//>'',.
`
`,/
`
`,,''
`
`;"'"'
`
`,,''
`
`,,,,,,"'
`
`I
`
`,/
`
`~/I \
`14 I : \
`I 58
`I f
`I I~ t",.//
`/
`/
`:
`:
`I I 38 I
`
`Pet., Exh. 1016, p. 2
`
`

`
`c::>
`00
`~
`~
`~
`...
`OI
`
`QI
`1-l
`
`~
`
`e,
`r:JJ. [
`
`UI
`~
`1-l
`~ .r-
`~
`~
`
`1-Cj ;
`
`•
`
`~ • 00.
`
`.-1
`SYN. TIME FOR USER n ASYN. TIME
`
`Fig. 3
`
`ONE TIME FRAME
`
`• • •
`
`SYN. TIME FOR USER 2 ASYN. TIME
`
`ASYN. TIME
`AUGMENTED
`
`I~ 70
`
`/
`
`76
`
`------.-1
`
`62
`
`SYN. TIME FOR USER n ASYN. TIME
`
`• • •
`
`Fig. 2
`
`ONE TIME FRAME
`
`1~
`USED BY USER 1
`
`SYN. TIME
`
`64
`
`1~
`
`SYN. TIME FOR USER 1 ASYNTIME SYN. TIME FOR USER 2 ASYN. TIME
`
`74
`
`.-j
`FLEXIBLE
`
`68
`
`72
`
`.-j
`FLEXIBLE
`
`66
`
`70
`
`.-j
`FLEXIBLE
`
`64
`
`Pet., Exh. 1016, p. 3
`
`

`
`U.S. Patent
`
`Feb. 21, 1995
`
`Sheet 3of16
`
`5,392,280
`
`80
`
`i=l
`
`SYNCHRONOUS TRANSMISSION
`SEND ONE CELL FROM QUEUE i
`
`82
`
`84
`
`YES
`
`NO
`
`88
`
`F-BIT
`
`ASYNCHRONOUS TRANSMISSION
`SEND ONE CELL (OR IDLE)
`
`NO
`
`YES
`
`92
`
`i:=i+l MODn
`
`Fig. 4
`
`Pet., Exh. 1016, p. 4
`
`

`
`U.S. Patent
`
`Feb. 21, 1995
`
`Sheet 4 of 16
`
`5,392,280
`
`' °' •
`
`'° °'
`' I
`I
`I
`I
`C:-1
`N
`' ~
`co
`
`I
`I
`
`ClO
`
`I
`I
`N
`'
`co
`
`N -
`
`~
`
`°'
`
`0 -
`
`I
`I
`I
`N
`
`Ci) ,,
`
`I
`I
`I
`I
`I
`I
`'N
`:co
`I
`I
`I
`I
`I
`I
`
`N
`'
`co
`
`-
`
`u
`
`Lt')
`•
`C>
`LL
`
`·-
`
`I
`I
`I
`I
`
`I
`I
`I
`C-..
`.
`Ci)
`I
`M
`u
`
`\
`\
`I
`
`I
`I
`I
`I
`N
`Ci)
`I
`I
`I
`I
`N
`u
`
`Pet., Exh. 1016, p. 5
`
`

`
`U.S. Patent
`
`Feb. 21, 1995
`
`Sheet S of 16
`
`5,392,280
`
`'° °'
`' '
`
`I
`I
`I
`I
`C...
`N
`~ ~
`'
`I
`I
`I
`I
`
`N
`
`-
`
`I
`I
`I
`I
`I
`I
`
`I
`I
`I
`I
`I
`I
`
`C")
`
`~ l::!:
`:cc
`I
`I
`I
`I
`I
`I
`
`•
`
`I
`I
`
`::!:
`cc
`
`'°
`.
`·-
`Cl
`u..
`
`I
`I
`I
`I
`
`\
`\
`\
`\
`
`I
`I
`I
`N
`.......
`cc
`'
`I
`C")
`u
`
`\
`\
`\
`
`I
`I
`I
`I
`
`::!:
`cc
`I
`I
`I
`I
`N
`u
`
`I
`--~
`I
`I
`
`0
`
`I - I
`
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`
`::!:
`cc
`C")
`
`-
`
`u
`
`Pet., Exh. 1016, p. 6
`
`

`
`U.S. Patent
`
`Feb. 21, 1995
`
`Sheet 6of16
`
`5,392,280
`
`_.. _..
`w u
`w _..
`9
`z
`0 z w
`
`<(
`
`ell
`
`c....
`,_.
`
`-
`
`,_.
`0
`
`'\
`
`co
`,_.
`,_.
`
`0
`z
`
`_..
`_..
`w u
`
`<(
`0
`
`z w
`
`ell
`
`~
`
`·-
`C')
`u..
`
`Pet., Exh. 1016, p. 7
`
`

`
`U.S. Patent
`
`Feb. 21, 1995
`
`Sheet 7of16
`
`5,392,280
`
`co .
`Cl u::
`
`• • •
`
`u....--
`L&..N
`Oz Oz
`wo
`wo
`:::>-
`:::> i=
`wt;
`LUU
`::>w
`=>w
`oz Oz
`_,z
`-'Z
`-'O
`u::I 0
`~u uu
`
`LL. c: Oz wo
`:::>-wt;
`=>w Oz
`-'Z
`u::I 0 uu
`
`T c:
`
`c:
`~
`
`~
`~
`C:>
`
`•
`•
`•
`
`c:
`~
`
`N I=
`C:>
`
`T
`
`°' .
`Cl u::
`
`c:
`~
`
`T -~
`
`~
`C:>
`
`Pet., Exh. 1016, p. 8
`
`

`
`U.S. Patent
`
`Feb. 21, 1995
`
`Sheet 8of16
`
`5,392,280
`
`! '
`
`I
`I
`I
`I
`I
`I
`I
`I
`
`•
`
`I
`I
`I
`I
`I
`I
`I
`
`I
`I
`I
`I
`
`I
`I
`I
`N
`.......
`al
`I
`I
`C")
`
`u
`
`0
`......
`.
`·-
`Cl
`u..
`
`'
`
`\
`\
`
`'°
`:I:
`~
`3:
`en
`
`<(
`:I:
`~
`~
`
`'
`
`I
`I
`I
`I
`I
`I
`I
`I
`
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`1
`I
`I
`I
`I
`
`z
`0
`t;
`w
`C>
`z
`8
`
`'°
`:I:
`~
`~
`
`<(
`:I:
`~
`~
`
`•
`
`I
`I
`I
`I
`I
`I
`I
`
`I
`I
`I
`I
`
`I
`I
`I
`
`c....
`Ci3
`
`I
`I
`C")
`
`u
`
`.--
`.--
`·-
`Cl
`u..
`
`'
`
`\
`I
`
`I
`I
`!
`N
`d:i
`
`I
`I
`I
`I
`N
`d:i
`
`I
`I
`I
`I
`
`z
`0
`0 § N
`
`u
`
`..;.J
`..;.J
`<(
`:I:
`b
`~
`~
`
`C")
`
`;a
`-
`
`I
`I
`I
`I
`~
`'°
`I
`I
`~
`I
`cc:>
`I
`N
`u wZ u
`en-
`::::>~
`<(~
`Uen
`z :I:
`O!=
`ti; 3:
`wO oz
`z~ 8
`
`Pet., Exh. 1016, p. 9
`
`

`
`U.S. Patent
`
`Feb. 21, 1995
`
`Sheet 9of16
`
`5,392,280
`
`l
`
`<
`w
`c
`0
`z
`LI..
`0
`z
`0
`~
`:E
`c.n
`z
`~
`.....
`_,
`_,
`w
`u
`
`cc
`w
`c
`0 z
`
`< w c
`0 z
`
`c.n
`cc::::>
`wO
`cZ
`o~
`z:J:
`:EU
`<
`oz
`w c
`a:~
`0 z N
`<!) _,
`Zo
`LI..
`.
`~~
`0
`r-
`z
`u..O
`0 Cl
`-iU
`_,
`~ ·-
`~~
`:E u..
`:J:C
`c.n z
`~~
`~ .....
`z!a
`;:: <
`-w
`'ilc
`u..o
`zz
`<o
`
`~
`
`'
`
`Pet., Exh. 1016, p. 10
`
`

`
`QO =
`~ --~
`\0
`--~
`U1
`
`~ ... Q a. ...
`
`°'
`
`ga
`
`t-.) .:-...
`~ ?-
`
`UI
`~
`
`P! a
`
`~
`•
`00
`0
`
`Fig. 13
`
`0 ---~~~~~~~~~~~~~~--
`
`ASYNCHRONOUS CELL OCCUPATION
`
`C ~ I-----------------------------------------I C: COUNT OF ASYNCHRONOUS CELLS
`
`M-RRP-R ~-----------------. R: ROUND TRIP DELAY
`
`BUFFER TO DEAL WITH DELAY
`
`M-RRP i------------------11 RRP: ROUND-ROBIN PERIOD
`
`BUFFER FOR SYNCHRONOUS CELLS
`
`M: BUFFER FOR NODE A
`
`M
`
`Pet., Exh. 1016, p. 11
`
`

`
`U.S. Patent
`
`Feb. 21, 1995
`
`Sheet 11 of 16
`
`5,392,280
`
`I
`I
`I
`I
`I
`I
`I
`
`I
`
`I ,.
`I !(
`-------------T------------------------
`
`1
`I
`I
`I
`I
`
`-------------T------------------------
`
`1
`
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`
`Cl> ;p
`
`°'
`+
`'1J
`..9>
`
`'1J
`..9>
`
`q-
`..-
`.
`Cl ·-LL.
`
`N
`
`a.. w t;;
`
`u
`
`Pet., Exh. 1016, p. 12
`
`

`
`U.S. Patent
`
`Feb. 21, 1995
`
`Sheet 12 of 16
`
`5,392,280
`
`~ z ::;
`C) z
`
`~ 0
`
`• • •
`
`~
`0
`~ w
`~
`~-w~
`u.. t:O
`u.. (/) =>-
`c w
`
`t:O
`
`~
`<(
`J:
`(/)
`
`I-z
`:::::>
`-'I= oz
`e:~
`z
`0
`u
`
`Lt')
`
`.....
`.
`·-
`C>
`LL
`
`Pet., Exh. 1016, p. 13
`
`

`
`00 =
`
`N
`...
`N
`\C
`(Ji)
`...
`en
`
`Q\
`1-l
`
`e,
`~
`00 [
`
`UI
`~
`1-l
`J-l
`~
`
`~ ?-
`
`~ a a
`
`00 •
`0
`
`Fig. 16
`
`•
`
`• •
`
`LAST CELL ADDRESS (LCA)
`
`FIRST CELL ADDRESS (FCA)
`
`CONNECTION n __...
`
`•
`•
`
`• •
`• •
`
`TAG
`
`n
`CELL
`
`LAST CELL ADDRESS (LCA)
`
`FIRST CELL ADDRESS (FCA)
`
`CONNECTION 2 __...
`
`LAST CELL ADDRESS (LCA)
`
`FIRST CELL ADDRESS (FCA)
`
`CONNECTION 1 __...
`
`\ \_/\_/.. 0
`
`TAG
`
`TAG
`
`SHARED BUFFER MEMORY
`
`(SBM)
`
`1
`CELL
`
`0
`CELL
`
`CONNECTION LOOKUP TABLE (CLT)
`
`•
`•
`•
`
`Pet., Exh. 1016, p. 14
`
`

`
`QO =
`
`~
`~ ...
`\C
`CH
`...
`C.11
`
`Q\
`1-1.
`~
`.s:;..
`1-1.
`
`r ~
`
`~
`~ .r-
`~
`ITj
`
`1-1.
`
`~ a ('D a
`
`•
`tlJ.
`•
`Cj
`
`I ___________________________________________________________ :
`
`Fig. 17
`
`I
`I
`
`CONTROL UNIT
`
`(CNT)
`
`CONNECTION LOOKUP
`
`TABLE (CLT)
`
`I
`
`7
`
`REGISTERS (RARs)
`READING ADDRESS
`
`4
`
`CONTROL CIRCUIT
`
`(CC)
`
`__,
`
`13
`
`I
`
`2
`
`8
`
`~ IDLE ADDRESS POOL I
`
`UAP)
`
`6
`
`15
`
`r
`
`I
`I
`I
`
`OUTGOING LINKS
`
`• • .
`•
`
`SHARED BUFFER MEMORY
`
`(SBM)
`
`INCOMING LINKS
`
`•
`• •
`
`Pet., Exh. 1016, p. 15
`
`

`
`U.S. Patent
`
`Feb. 21, 1995
`
`Sheet 15 of 16
`
`5,392,280
`
`_,
`-' w u
`
`::I w u
`
`.
`C'> u:
`
`::I w u
`
`::I w u
`
`~ .....
`
`-' -' w u
`
`w
`::::>
`LU
`:::::>
`0
`
`_,
`-' w u
`
`~ .....
`
`-' -' w u
`....
`LU
`::::>
`LU a
`
`• • •
`
`• • •
`
`::I w u
`
`<!)
`~
`
`-' -' w u
`
`~
`LU
`::::>
`
`LU a
`
`Pet., Exh. 1016, p. 16
`
`

`
`U.S. Patent
`
`Feb. 21, 1995
`
`Sheet 16 of 16
`
`5,392,280
`
`~
`~ w
`
`~
`et:-
`w~ u..cc
`~!!?.
`cc
`0
`w °' <(
`:::c
`
`(/')
`
`_, _,
`w u
`
`(!)
`<(,....
`I-
`
`• • •
`
`(!)
`<(·-
`I-
`
`_, _,
`w u
`
`~ I-
`
`D
`.
`~
`Cl u:
`• • •
`\
`~~ I-
`v
`
`~ I-
`
`Pet., Exh. 1016, p. 17
`
`

`
`1
`
`5,392,280
`
`DATA TRANSMISSION SYSTEM AND
`SCHEDULING PROTOCOL FOR
`CONNECTION-ORIENTED PACKET OR CELL
`SWITCHING NETWORKS
`
`2
`able level of congestion. A common approach is to
`control traffic flow at entry points of a network with
`admission control and bandwidth enforcement. For
`A TM switches, admission control determines whether
`or not to accept a new connection at the connection
`setup time. Bandwidth enforcement monitors each indi(cid:173)
`FIELD OF THE INVENTION
`vidual connection to ensure that the actual traffic flow
`conforms to that specified at the time of connection
`This invention relates to digital communication net-
`works, and more particularly to a system for both guar-
`setup. With the use of a proper cell transmission sched-
`anteeing transmission capacities to users and maximiz- 10 uling policy at switches, preventive control can often
`ing network usage by providing a novel data transmis-
`provide users with a certain type of quality of service,
`sion scheduling and feedback flow control system.
`ranging from a guaranteed bandwidth to delay bounds.
`But a major problem with preventive control is that it is
`BACKGROUND OF THE INVENTION
`difficult to achieve high network utilization for variable
`Digital communication networks can be classified 15 bit-rate traffic, e.g., traffic of widely differing bit rates.
`into two types: synchronous and asynchronous net-
`A user is usually not allowed to send more messages
`works. In a synchronous network, communication ca-
`than specified, even when a network load condition
`pacity is statically allocated to users by dividing time
`allows this to happen. This makes A TM networks be-
`into fixed size frames and assigning a portion of each
`have like synchronous networks. Also, many traffic
`frame to an individual user. In an asynchronous net- 20 policing and scheduling schemes are costly to imple-
`work, information is organized into self-contained data ment.
`units called packets or cells. Each data unit is trans-
`Reactive control, on the other hand, admits traffic
`ferred over a network independently without being
`according to the current network load condition with a
`controlled by time frames.
`feedback mechanism. A network can accept traffic on a
`The advantage of a synchronous network is that each 25 best effort basis and there is no pre-set limit on the
`amount of traffic that each connection can carry. Thus
`user is allocated a given communication capacity such
`t?at a ce~ type of quality of service, e.g., transmis-
`it is possible to achieve high degree of dynamic band-
`s1on bandwtdth and delay bounds: ~an be. g~anteed. width sharing and a high network utilization making
`However, a synchronous network 1s meffic1ent m trans-
`.
`.
`'
`.
`· bl b"t
`t
`traffi
`·
`.
`ti"
`30 reactive control swtable for bursty data traffics like
`rtm.
`po
`g vana e 1 -ra e
`1c smce commumca on
`·
`h
`xhi .
`.
`btted m _co~p~ter networks. ~owever: with
`resources can not be shared among users. Today's digi-
`t ose. e
`reac~1ve control, it _is difficult to provide quality of
`tal telephone network is one example of a synchronous
`serv~ce guarantees smce the bandwtdth that each con-
`network which supports real-time voice conversation
`necti?~ can ~se depends on the act~ _network load
`relatively well but exhibits low efficiency when used for
`bursty computer data transmissions in which large 35 con~1t1on. Like_ asynchronous transllllSston_, a lack of
`amounts of data are transmitted in a burst.
`quality of service guarantee makes reactive control
`incapable of suppo~g real-tim_e appli~tions ~eqW?ng
`Asynchronous networks, on the other hand, can
`achieve high network utilization by statistically multi-
`guaran~e~d bandwtdth such as mteractive audio/video
`plexing variable bit-rate traffic on a transmission link,
`.
`.
`transmtss1~ns.
`but with a loss of quality of service guarantees for users. 40
`. In the view of the ~ore~omg, there ts a need to pro-
`While present computer networks offer an example of
`vide an approach which mtegrates synchronous trans-
`how an asynchronous network supports computer data
`mission with ~ynchronous tran~~sion in such a way
`that a network ts capable of prov1dmg guaranteed band-
`communication, asynchronous networks oftentimes
`cannot support real-time audio/video communications
`width transmission, while simultaneously providing
`45 both dynamic bandwidth sharing and lossless transmis-
`satisfactorily.
`Asynchronous Transfer Mode or A TM technology is
`sion.
`an emerging technology which tries to achieve the
`As to guaranteed bandwidth transmission, its purpose
`advantages of both synchronous and asynchronous
`is to allow a user to establish a connection with a guar-
`networks. Specifically, ATM networks organize a
`anteed bandwidth. Providing guaranteed bandwidth is
`user's information into 53-byte fixed-size cells which are 50 necessary to make a network capable of supporting
`services provided by synchronous networks, such as
`asynchronously transferred along a pre-established path
`without being subject to constraints of time frames.
`today's circuit-switched telecommunication networks.
`Since transmission bandwidth is dynamically shared by
`As to dynamic bandwidth sharing and lossless trans-
`mission, this permits a user to exceed its guaranteed
`all users, high network utilization can be achieved. But
`A TM networks inherit a common problem of asynchro- 55 bandwidth whenever resources are available. Specifi-
`nous transmission: namely the lack of quality of service
`cally, any bandwidth not allocated or bandwidth allo-
`guarantees. It is difficult to control the amount of traffic
`cated to one user but not used should be made available
`to all others, and it should also be guaranteed that no
`transferred over an A TM network such that quality of
`buffer overflows will occur due to this dynamic band-
`service can be guaranteed while maintaining a high
`level of network usage. Although many traffic control 60 width sharing. Achievement of this objective allows a
`schemes have been proposed to overcome this problem,
`network to make efficient use of transmission band-
`no one has succeeded in making A TM capable of pos-
`width which is essential to support variable bit-rate
`sessing advantages of both synchronous and asynchro-
`traffic of today's asynchronous data communication
`nous transmissions simultaneously.
`networks.
`Specifically, investigators have tried to solve the 65
`Integration of guaranteed bandwidth transmission
`traffic control problem with two approaches: preven-
`and dynamic bandwidth sharing brings immediate bene-
`tive control and reactive control. Preventive control
`fits to both network users and network providers if a
`tries to prevent a network from reaching an unaccept-
`proper billing scheme is used. One possible scheme is to
`
`Pet., Exh. 1016, p. 18
`
`

`
`5,392,280
`
`4
`nection. To avoid data losses, asynchronous transmis(cid:173)
`sion is permitted only when a downstream switch indi(cid:173)
`cates sufficient buffer space to accommodate asynchro(cid:173)
`nous transmission from an upstream switch.
`
`3
`calculate the cost of a connection partially based on the
`guaranteed bandwidth and partially based on the actual
`number of cells transmitted. In this way, a video confer(cid:173)
`encing user may be able to save network charges by
`turning off the video when the meeting gets boring. 5
`Since the connection is still there, he or she can monitor
`the meeting with audio and restart the video transmis(cid:173)
`sion immediately when some thing interesting happens.
`Network providers, on the other hand, can benefit from
`the increased network utilization.
`
`SUMMARY OF THE INVENTION
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`These and other features of the Subject Invention
`will be better understood in connection with the De(cid:173)
`tailed Description taken in conjunction with the Draw-
`10 ing of which:
`FIG. 1 is a schematic block diagram of the Subject
`System illustrating the timed-round-robin transmission
`of data in both a synchronous and an asynchronous
`As a result of the necessity of accommodating both
`mode determined by a cell transmission scheduler
`guaranteed bandwidth transmission and dynamic band-
`width sharing among users, in the Subject Invention 15 adapted to permit data transmission in asynchronous
`this objective is accomplished by an integration of syn-
`time slots based on unused synchronous transmission
`chronous and asynchronous transmissions which per-
`time;
`mits detection of unused portions of synchronous time
`FIGS. 2 and 3 are diagrams illustrating the format or
`and permits the network be reconfigured to fill these
`protocol for the synchronous/asynchronous transmis-
`unused portions of time with asynchronous data. The 20 sion of data over a transmission link, showing the ability
`to make use of unused synchronous time by augmenting
`subject system thus provides traffic control which is
`effective enou?h to p~ovide satisfactory ~etwork per-
`the adjacent asynchronous time slot so that it can be
`fo~ance, b11:t is ~so _sunple enough to be unplemented
`used to transmit data thereb
`to ermit d amic band-
`without addmg significant extra cost to the current
`. dth h
`·
`.
`'
`y
`· p
`yn
`kin
`ts
`25 wi
`s armg,
`d
`t
`FIG. 4 is a flowchart illustrating the cell transmission
`.
`.
`.
`ne wor g pro uc ·
`cl~~e: ~r~;~~ ::~~~~~:;u::ef!u1l~ S~~~:,~;
`s~heduler of FI?. 1 showin? ~he realization of the
`tuned-rou~d-robm cc:;ll trans_missioni
`which uses a novel timed-round-robin cell transmission
`. .
`FIG. 5 is a block d1~gram illustratmg th~ tr~smiss~on
`scheduling algorithm combined with a simple feedback
`flow control mechanism to integrate synchronous and 30 of ce~s from on~ switch to ~he=; next switch m w1:llch
`conflicts are avo1~ed by restnctmg the peak bandwidth
`asynchronous transmissions. The timed-round-robin
`that each 7onnection ~an use; .
`.
`.
`.
`.
`cell transmission scheduling provides each connection
`1'.IG. 6 is a blo~k d1agr~ illustrating a s1tuatlo~ m
`with a guaranteed transmission bandwidth and access to
`the full link transmission bandwidth when there is no
`which the dynamic bandwidth at the upstream switch
`contention from other connections. The feedback flow 35 can cause a conflict at the downstream switch which
`~esults in ~~ta l?ss due to buffer overload, also illustrat-
`control mechanism ensures that no cells will get lost by
`disabling asynchronous transmission at an upstream
`mg the u~~tion of feedback control c?upled .to the
`cell t~ansmiss1on sched~er o~ FIG. 1 which av01ds the
`node when there is not enough buffer space at a down
`stream node. An A TM switch design is also included
`confl1c~ ~ough the dISabling of the asynchronous
`which shows the feasibility of implementing the sub- 40 transmISs1?n;
`.
`.
`.
`FIG. 7 IS a flowchart illustratmg one embodunent for
`jected system with today's switch architectures without
`adding significant extra cost.
`accomplishing asynchronous cell transmission in the
`More specifically, in connection-oriented packet or
`system illustrated in FIG. 4, also describing the inter-
`ruption of asynchronous transmission based on the feed-
`cell switching networks, a data transmission system and
`scheduling protocol utilizes both synchronous transmis- 45 back from a downstream switch;
`sion and asynchronous transmission in an alternating
`FIG. 8 is a simplified schematic diagram of the timed-
`pattern to provide each user with both a guaranteed
`round-robin cell transmission scheduling technique of
`FIG. 1 illustrating sequential sampling of the data in a
`transmission bandwidth or capacity to accommodate
`real-time communications, and bandwidth sharing
`series connection;
`among users to increase network utilization, while si- 50
`FIG. 9 is a timing chart for synchronous and asyn-
`multaneously eliminating network congestion to avoid
`chronous transmission illustrating guaranteed transmis-
`data losses. The synchronous time slots provide for the
`sion times for different connections and variable length
`asynchronous time slots such that both guaranteed and
`bandwidth guarantees, while the asynchronous time
`slots are used to transmit data when a part of a previous
`reliable transmission of data can be achieved efficiently
`synchronous time slot is not used. The asynchronous 55 through dynamic utilization of transmission capacity or
`time slots also permit asynchronous data transmission
`bandwidth;
`using unallocated time within a given time frame. In one
`FIG. 10 is a block diagram of upstream and down-
`embodiment, time flames for data transmission are pro-
`stream switches illustrating bandwidth allocation for
`vided in which each time frame is composed of syn-
`the two connections of the upstream switch which can
`chronous transmission times interspersed with asyn- 60 be handled by the bandwidth of the associated outgoing
`transmission link of the downstream switch;
`chronous transmission times. For a given time frame,
`FIG. 11 is a block diagram of the switching network
`alternating synchronous and asynchronous transmission
`of FIG. 10 illustrating congestion in the downstream
`times are specified by a controller which determines the
`pattern of this alternation. In a preferred embodiment,
`switch when the bandwidth associated with one con-
`the pattern is altered using novel timed-round-robin 65 nection of the upstream switch plus the bandwidth of a
`connection at the downstream switch exceeds the band-
`scheduling which transmits cells of data of respective
`connections over an outgoing link depending upon the
`width of the associated outgoing transmission link of the
`synchronous transmission time allocated to each con-
`downstream switch;
`
`Pet., Exh. 1016, p. 19
`
`

`
`20
`
`30
`
`5,392,280
`
`s
`FIG. 12 is a block diagram illustrating the feedback to
`an upstream switch of the buffer status of a buffer in a
`downstream switch to inhibit asynchronous data trans(cid:173)
`mission until such time as there is sufficient buffer space
`in the downstream switch;
`FIG. 13 is a diagrammatic representation of buffer
`management protocol for the buffer for a downstream
`switch illustrating buffer space allocated to the associ(cid:173)
`ated upstream switch;
`FIG. 14 is a graph illustrating the setting of the F-bit 10
`in the algorithm which controls the transmission of
`asynchronous data, in which the F-bit is set in accor(cid:173)
`dance with the count of asynchronous cells in the buffer
`ofFIG.13;
`FIG. 15 is a block diagram illustrating shared buffer 15
`memory and a control unit along with multiplexing and
`demultiplexing circuits within a switch;
`FIG. 16 is a diagram illustrating a linked-list queueing
`structure to organize cell queues for connections pass-
`ing through a switch;
`FIG. 17 is an expanded block diagram of the control
`unit of FIG. 15 illustrating an idle address pool, a con(cid:173)
`nection lookup table coupled to a control circuit for
`specifying the address for incoming cells to be store in
`the shared buffer memory, for updating the reading 25
`address registers, and for implementing timed-round(cid:173)
`robin cell transmission scheduling;
`FIG. 18 is a diagram illustrating an enhanced linked(cid:173)
`list queueing structure to handle multicast cells, cells
`which are to be sent to multiple outgoing links; and,
`FIG. 19 is a diagram illustrating the implementation
`of the queueing structure of FIG. 18 in a shared buffer
`memory.
`
`6
`transmitted to switch 12 asynchronously. This is shown
`in format block 40 in which the data 34 from Connec(cid:173)
`tion 1 is transmitted first in the synchronous time slot
`associated with Connection 1. This is followed by the
`5 asynchronous transmission of data from Connection 2
`as illustrated at 42. Thereafter the remainder of the data
`in Connection 2 is transmitted as illustrated at 44 in
`synchronous time slot GTT2. As will be seen, the un-
`used time associated with GTTl is utilized so that extra
`data may be transmitted in an asynchronous fashion.
`The above results in efficient utilization of the trans(cid:173)
`mission bandwidth by detecting unused time in a syn(cid:173)
`chronous time slot and transmitting data in a variable
`length asynchronous time slot. In addition to efficient
`utilization, there is a guarantee that data will not be lost
`if there is sufficient buffer space at the downstream
`switch. This is not always the case and for this reason,
`a feedback path 50 is provided from switch 12 to switch
`10 utilizing the bidirectional links between switches 10
`and 12. The status of buffer occupation at switch 12 is
`provided by a so-called F-bit which is coupled to an
`asynchronous transmission controller 52 which inter(cid:173)
`rupts or inhibits the asynchronous transmission of data
`to switch 12 if there is insufficient buffer space at this
`downstream switch.
`The timed-round-robin scheduling is under the con(cid:173)
`trol of the scheduler 32 via a Connection 54 to transmit(cid:173)
`ter 56. It is obviously important to be able to sense an
`empty portion of a queue. For this purpose an empty
`queue detector 58 is used to detect when a queue is
`empty during transmission to permit switching to the
`asynchronous mode. The control of transmitter 56 de(cid:173)
`pends upon the output of synchronous time monitor 60
`which determines if the synchronous time is not used up
`DETAILED DESCRIPTION OF THE
`35 is determined by the detection of all empty queue.
`INVENTION
`Referring now to FIG. 2, it will be appreciated that
`Referring now to FIG. 1, an upstream switch 10 is
`one time frame or cycle 62 includes a number of syn-
`chronous time slots 64, 66, and 68, with the time slots
`coupled to a downstream switch 12. Switch 10 bas a
`number of incoming links 14 and a number of outgoing
`being variable in length depending on the guaranteed
`links 16, with one of the outgoing links 18 coupled to 40 transmission time for each connection. Likewise, asyn-
`switcb 12 as an incoming link. Switch 12 bas a number
`chronous time slots 70, 72, and 74 are variable length
`of outgoing links 20 to which data on link 18 may be
`depending upon scheduling. As can be seen in FIG. 3,
`selectively switched. Switch 12 incorporates a buffer 22
`asynchronous time slot 70 can be augmented as indi-
`whicb is utilized to store incoming data and to route it
`cated by arrow 76 to permit data transmission in that
`to one or more outgoing links.
`45 portion of time slot 64 for which no data for Connection
`Within switch 10 is a buffer 24 adapted to store in-
`1 exists.
`coming data from various incoming links through con-
`Referring now to FIG. 4, the algorithm utilized by
`nections to cell queues 26, 28, and 30 accomplished by
`scheduler 52 of FIG. 1 includes a block 80 indicating
`conventional switching. As illustrated, incoming links
`starting the cell transmission from the first connection.
`14 are connected by switch 10 to outgoing link 16 50 As shown by block 82, a cell of Connection i is transmit-
`tbrougb the utilization of a timed-round-robin scbedul-
`ted using the guaranteed transmission time of the con-
`nection. As illustrated at 84, a timer is utilized to detect
`ing system which sequentially accesses data from
`queues 26-30 in accordance with scheduling provided
`the expiration of synchronous transmission time for
`Connection i. If the synchronous time is not up, block
`by cell transmission scheduler 32.
`Buffer 24 is organized in a format of one queue per 55 86 checks to ascertain if there are other cells in the
`corresponding queue. If the queue is empty, asynchro-
`connection. As used herein, a connection is defined as a
`single path connecting two end users. As can be seen,
`nous transmission of data is authorized as illustrated at
`each queue is provided with a guaranteed transmission
`88. Note that asynchronous transmission is also autho-
`time, GTT, associated with a given connection. GTTl
`rized when the synchronous transmission time is up.
`indicates by shaded area 34 that only a part of the time 60 The expiration of asynchronous time is determined by
`needed to transmit the cells of this connection is used.
`timer 90, at which point the process is moved to the
`Thus there is an unused synchronous transmission time
`synchronous transmission of the next connection.
`for Connection 1. As can be seen by the shaded area 36,
`Referring now to FIG. 5, the problem with the con-
`Connection 2 requires additional time to transmit its
`gestion is illustrated in which Connection 1 and Con-
`data, with the time exceeding GTT2, the guaranteed 65 nection 2 to switch 10 have data each occupying one
`half of the link bandwidth. Data associated with Con-
`transmission time for this connection.
`nections 1 and 2 are time multiplexed to link 94 such
`Since a prior connection bas unused time, the addi-
`that Connection 1 data is outputted over outgoing link
`tional data 38 associated with Connection 2 may be
`
`Pet., Exh. 1016, p. 20
`
`

`
`8
`7
`in A TM networks. Timed-Round-Robin scheduling can
`96, whereas Connection 2 data is switched to outgoing
`realize similar bandwidth allocation ability as Stop-and(cid:173)
`link 98. As can be seen, a Connection 3 having data
`occupying a bandwidth equal to half of the link band(cid:173)
`Go, but it has the advantage of being easier to incorpo(cid:173)
`width is to be coupled to outgoing link 96. Here the link
`rate a feedback flow control scheme to achieve dy-
`capacity of outgoing link 96 is not exceeded, i.e., B/2
`5 namic bandwidth sharing and lossless transmission by
`from Connection 1 plus B/2 from Connection 3 equals
`using a concept of synchronous and asynchronous
`B.
`transmissions. Specifically, in the Subject Invention,
`time is divided into fixed-size frames called a Round-
`On the other hand, referring to FIG. 6, if Connection
`Robin Period, RRP. In one RRP, each connection is
`2 uses one fourth the link bandwidth, this would ordi-
`narily permit an increase in the bandwidth associated 10 given a certain amount of Guaranteed Transmission
`with Connection 1 to~ of the link bandwidth. However
`Time, GTT, with which cells are transmitted without
`at