(12) United States Patent
`Diedrich et al.
`
`US006336143B1
`US 6,336,143 B1
`Jan. 1, 2002
`
`(10) Patent N0.:
`(45) Date of Patent:
`
`(54) METHOD AND APPARATUS FOR
`MULTIMEDIA DATA INTERCHANGE WITH
`PACING CAPABILITY IN A DISTRIBUTED
`DATA PROCESSING SYSTEM
`
`(75) Inventors: Richard Alan Diedrich; Harvey Gene
`Kiel, both of Rochester, MN (US)
`
`(73) Assignee: International Business Machines
`Corporation, Armonk, NY (US)
`
`( * ) Notice:
`
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 0 days.
`
`(21) Appl. No.: 08/127,932
`(22) Filed:
`Sep. 27, 1993
`
`(51) Int. Cl.7 ...................... .. G06F 13/38; G06F 15/177
`(52) US. Cl. ...................... .. 709/231; 709/219; 709/234
`(58) Field of Search ............................... .. 395/800, 200,
`395/600; 364/200; 370/94, 94.1; 709/231,
`219, 234
`
`(56)
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`6/1980 Eklund et 211.
`4,208,714 A
`9/1988 Blasbalg ................... .. 364/514
`4,771,391 A
`8/1991 BarZilali et a1. ......... .. 370/94.1
`5,040,176 A
`8/1993 Bryant et a1.
`395/800
`5,241,682 A
`5,303,238 A * 4/1994 Brodd et al. ............. .. 370/94.1
`
`FOREIGN PATENT DOCUMENTS
`
`EP
`JP
`JP
`JP
`
`0 550 197 A3
`62135037
`62154133
`04162155
`
`7/1993
`6/1987
`7/1987
`6/1992
`
`........... .. G06F/9/46
`
`OTHER PUBLICATIONS
`IBM Systems Journal, Jun. 1992 V31 n2 P161 (28) “Evo
`lution of an Open Communications Architecture”.*
`* cited by examiner
`Primary Examiner—Mark H. Rinehart
`Assistant Examiner—Jason Cardone
`(74) Attorney, Agent, or Firm—BraceWell & Patterson
`(57)
`ABSTRACT
`
`A method and apparatus for efficient multimedia data inter
`change Which utilizes multimedia pacing in a distributed
`data processing system. During a multimedia communica
`tions session, each of a plurality of receiving stations trans
`mits multimedia pacing requests to a sending station at
`negotiated set time intervals. The multimedia pacing request
`includes information on the availability of current storage
`for multimedia data at the receiving station, a minimum data
`time remaining in storage in the receiving station and other
`information pertaining to the interchange of the multimedia
`data. The sending station then allocates various priorities to
`the transmission of data to the plurality of receiving stations
`in an order indicative of the type of data, i.e. multimedia or
`non-multimedia, and the information in the multimedia
`pacing request pertaining to the minimum data time remain
`ing in storage at the receiving station. In addition, the
`sending station periodically determines the availability of
`the transmission queue. When the transmission queue is not
`readily available, the sending station transfers only high
`priority multimedia data to the transmission queue; hoWever
`When the transmission queue is available, the sending station
`transfers loWer priority multimedia data to the transmission
`queue as Well. The sending station can then supply a
`plurality of receiving stations With signi?cant multimedia
`data in advance When the communications interface is not
`overloaded.
`
`6 Claims, 8 Drawing Sheets
`
`Hullimediu
`Cummuniculinn
`Sessiun
`
`4s
`
`RIMOVO
`ilun 1mm
`Priulilylisls
`
`Hullimedin
`y
`I! Cnmmunicnlinn
`5
`:Sslun
`
`so
`
`Pvnuis
`w Facing
`Requesl
`
`Transmit
`n
`In
`SessiunRequasl
`
`Places:
`In: IN
`1
`Sessiunlllply
`
`54
`“Jamaal/HY
`mm
`
`"(a
`2
`lrqnsmisslonqunuq
`'Hundunilemonbigh
`
`/
`ilnblenn
`um
`
`7
`
`62
`
`Transfer
`
`Hem
`
`/
`llnblnon
`an:
`‘.wrzwnzznxm ""
`M“
`luv:
`Yes
`
`v
`
`.
`
`Page 1 of 16
`
`PETITIONERS' EXHIBIT 1012
`
`

`

`U.S. Patent
`
`1,
`2 0 0 2
`n. a J
`
`f 0
`
`US 6,336,143 B1
`
`om
`
`8 -.
`
`% éQsEz
`w 25:6
`
`$5
`
`1 $>5m
`
`uni vEQsEz
`
`Mon
`
`Page 2 of 16
`
`PETITIONERS' EXHIBIT 1012
`
`

`

`U.S. Patent
`
`Jan. 1, 2002
`
`Sheet 2 of 8
`
`US 6,336,143 B1
`
`36
`
`Muliimediu
`Communicoiion
`Session
`
`Y
`es
`
`(40
`
`5-46
`
`‘
`
`‘
`
`itlzamforzem
`Prlorliy Llsis
`
`.
`
`.
`
`.
`
`44
`Nuliimediu
`Yes ComSmunicoiion
`Complete?
`
`ession
`
`$50
`Process
`HM Pacing
`Requesi
`
`v<—
`
`48
`MM Pacing
`Requesi
`Received?
`
`Tronsmii
`SiariMM
`Session Re uesi
`q
`
`{42
`
`Process
`SiuriMM
`Session Reply
`
`____>'
`
`'
`
`I
`
`‘-
`
`{54
`Transfer
`H'ghl?glmoniy
`
`.
`
`.
`
`.
`
`ironsmlsslonqueu
`
`‘Space 52
`ovo|.|ub_le on
`Yesund uniiemonhigh
`\ prioriiy/
`Iisi?
`No
`
`.
`
`.
`
`.
`
`Transmission ueu
`
`SpuceJ55
`"58
`Transfer
`available on
`ued'u'liiipr'w'iy Ysond uniiemorilmede'.
`em
`6 \ prioriiy/
`Iisi?
`T0
`/Spoce 60
`available on
`Tronsmissionqueuq N0
`Y
`onduniiem onlow'
`es \ prioriiy/
`'iisi?
`V
`
`[.62
`f
`I
`'8"? 9!
`L
`OWHHOHH
`em
`
`Fig. 2
`
`Page 3 of 16
`
`PETITIONERS' EXHIBIT 1012
`
`

`

`U.S. Patent
`
`Jan. 1, 2002
`
`Sheet 3 0f 8
`
`US 6,336,143 B1
`
`@364
`
`[55
`
`Upduie
`High Prioriiy
`Hems
`
`UFduie
`Low rioriiy
`
`'
`
`Moms
`
`1-58
`
`70
`
`Hem
`on Prioriiy
`Lisi?
`
`Yes
`
`Goio
`Block 38
`FiygureZ
`
`/72
`
`74
`
`Fig. 3
`
`@16
`
`I78
`
`Trunsmii
`SiuriMM
`SessionRequesi
`
`Initialize
`Purumeiers
`
`8°
`
`@82
`Fig. 4
`
`Page 4 of 16
`
`PETITIONERS' EXHIBIT 1012
`
`

`

`U.S. Patent
`
`Jan. 1, 2002
`
`Sheet 4 of 8
`
`US 6,336,143 B1
`
`Locaie Hem
`10 be Updaied
`
`/- 96
`
`i
`Updaie
`Minimum Daia /98
`Time Remaining
`i
`Updaie
`Siorage
`Available
`
`jioo
`
`Low prioriiy i0 2
`iiem wiih
`No < minimum daia
`iime remaining
`less ihan a
`ihreshold '2
`
`YES
`
`Real locaie
`liem i0
`HighPri'oriiy “104
`Lisi
`
`'0 6
`
`pacing i0
`re 0 eiv i n
`s i ui ion .
`
`88
`g
`Process
`daia fo r no
`NH pacing
`
`Fig- 6
`
`Allocaie
`data to Low
`Priariiy Lisi
`
`92
`
`Fig. 5
`
`Page 5 of 16
`
`PETITIONERS' EXHIBIT 1012
`
`

`

`U.S. Patent
`
`Jan. 1, 2002
`
`Sheet 5 of 8
`
`US 6,336,143 B1
`
`f1 10
`
`Locafe ifem
`on high riorify
`lisi vii la wesf
`va I ue of min.
`dafa Time
`
`T
`
`Transfer
`item To
`Transmission
`queue
`
`i
`
`Updafe
`paramefers of
`lasf frame s enf
`and s f a rage
`available
`
`i
`
`Updafe
`paramefer of
`minimum dafa
`Time remaining
`
`fl '2
`
`ff '4
`
`xi T6
`
`('20
`Transfer
`ifem i0
`Lo 1!! Priorify
`
`11s
`Reallocafe
`High priorify
`ifem ?
`
`122
`
`Fig. 7
`
`Page 6 of 16
`
`PETITIONERS' EXHIBIT 1012
`
`

`

`U.S. Patent
`
`Jan. 1, 2002
`
`Sheet 6 0f 8
`
`US 6,336,143 B1
`
`i2 4
`
`1-126
`
`Locaie iiem
`on low rioriiy
`lisi Wii lowest
`value of min. daia
`iime‘ remaining
`
`I128
`
`Transfer
`iiem i0
`Transmission
`queue
`
`I130
`
`Upda’ie
`parameiers of
`lasi frame 5 eni
`and sin rage
`available
`
`Update
`parameier of
`minimum daia
`iime remaining
`
`1132
`
`13 4
`
`Fig. 8
`
`Page 7 of 16
`
`PETITIONERS' EXHIBIT 1012
`
`

`

`U.S. Patent
`
`Jan. 1, 2002
`
`Sheet 7 0f 8
`
`US 6,336,143 B1
`
`(154
`
`Pro cess no n
`mu l i | medlu duia
`
`Sicri
`HM Requesi
`Recelv ed
`?
`
`HM Data
`Rec e'jv ed
`
`Yes r15 5
`C 0
`Mil Dupin io
`B uffer
`
`$153
`
`i
`Upduie
`para meiers of
`sioru e OVOI lab I e
`u n minimum
`doiu iime
`remu i ning
`
`{160
`i
`Updoie
`synchronizoiion
`purumeier
`
`i
`
`Fig. 9
`
`(14o
`
`lniiio l i z e
`pa ru meiers
`
`i
`
`f142
`
`Creu i e Siuri
`MM 5 essio n
`Rep ly
`i
`Irons mii
`MN 5 essio n
`Reply
`i
`Creuie
`0 buffer in
`sio re MM duiu
`
`{144
`
`Y14s
`
`{14s
`
`}
`Creuie
`HM P0 cing
`Requesi
`[150
`i
`Trusmii
`MM Pu cing
`Requesi
`
`Page 8 of 16
`
`PETITIONERS' EXHIBIT 1012
`
`

`

`U.S. Patent
`
`Jan. 1, 2002
`
`Sheet 8 0f 8
`
`US 6,336,143 B1
`
`I62
`
`Pacing)?
`
`Mu
`
`No
`
`I64
`Yes
`
`No
`
`I68
`
`Tronemii
`NM Pacing
`Request .
`
`Creation
`of NM Po cing
`Requesi
`
`@
`
`Transmis sio n
`of NM Pacing
`Requesi
`
`1470
`
`3/172
`
`F 69; 10
`
`Page 9 of 16
`
`PETITIONERS' EXHIBIT 1012
`
`

`

`US 6,336,143 B1
`
`1
`METHOD AND APPARATUS FOR
`MULTIMEDIA DATA INTERCHANGE WITH
`PACING CAPABILITY IN A DISTRIBUTED
`DATA PROCESSING SYSTEM
`
`BACKGROUND OF THE INVENTION
`1. Technical Field
`The present invention relates in general to improved
`methods for interchanging data Within a distributed data
`processing system and in particular to improved methods for
`interchanging multimedia and non-multimedia data Within a
`distributed data processing system.
`2. Description of the Related Art
`The interchange of data Within a distributed data process
`ing system is a Well knoWn feature of modern state-of-the
`art computer systems. Text and graphics may be ef?ciently
`interchanged betWeen data processing facilities utiliZing
`Well knoWn modem devices or facsimile devices/cards.
`Recently, modern computer systems have begun to
`experiment in so-called “multimedia” data. That is, presen
`tations containing audio, video, text, graphics and image
`combined into a common presentation. One problem
`encountered in the interchange of such multimedia data in a
`distributed data processing system is the communications
`interface. The communications interface is frequently the
`performance constraint in computer systems Which support
`multimedia sources With multiple communications sessions.
`Several types of communications interfaces Which may be
`utiliZed in a distributed data processing system include:
`Local Area NetWorks (LAN), Wide Area NetWorks (WAN),
`and System Bus. Examples of each type of communications
`interface are listed beloW.
`Local Area NetWorks (LANs): Token Ring, Ethernet,
`FDDI, Wireless LAN, etc. betWeen the multimedia data
`sender and the receiving station.
`ISDN, etc. betWeen the
`Wide Area NetWorks
`multimedia data sender and the receiving station.
`System Bus: Multimedia systems store multimedia data
`on some type of storage, then When a receiving station
`requests multimedia data, the data is retrieved from the
`storage and sent across the system bus to some type of
`communications interface to the receiving station.
`Currently, a system Which transmits multimedia data to a
`receiving station across a communications interface sends
`the data at a preselected rate (bytes or frames per second)
`based on the type of multimedia data and compression
`algorithm. This approach, called isochronous transmission,
`Will allocate predictable multimedia data transmission rates
`for each multimedia session. The receiving station in such an
`approach assumes the multimedia data arrives at the same
`rate at Which it should be presented to the user at the
`receiving station.
`For example, if a receiving station and a remote sending
`station choose to communicate With each other across a
`communications interface, the receiving station and the
`remote sending station negotiate a set amount of bandWidth
`for that connection. A dedicated timeslot, such as every 30th
`of a second, is reserved for the transmission, and no other
`data may be transmitted in that timeslot. A problem arises
`With isochronous transmission of multimedia data. Isochro
`nous transmission requires speci?c hardWare Which
`increases the cost of the system. In addition, isochronous
`transmission may not function as Well for general purpose
`computing. It is therefore apparent a need exists for a
`method of interchanging multimedia data across any type of
`communications interface Without the need of special hard
`Ware.
`
`15
`
`25
`
`35
`
`45
`
`55
`
`65
`
`2
`Another problem encountered Within a communications
`interface is the possible overrun of data transmission to the
`receiving station. To prevent the overrun of data
`transmission, a technique called “pacing” controls the trans
`mission of data by a sending station. For example, printers
`receiving print jobs or a receiving station doWnloading ?le
`transfers from a sending station may utiliZe pacing to
`prevent overrun. Sophisticated pacing techniques exist for
`the transmission of non-multimedia data, such as adaptive
`pacing, Which alloWs a receiving station to change or adapt
`the pacing WindoW siZe based on its buffer resources and
`traffic patterns in the netWork. HoWever, in the transmission
`of multimedia data, no pacing exists.
`Fixed pacing consists of the sending station and the
`receiving station negotiating, before the interchange of the
`data, a ?xed WindoW siZe for the data Which remains
`constant during the duration of the interchange of multime
`dia data. A pacing response during the interchange signi?es
`the readiness of the receiving station to receive a WindoW
`siZe of multimedia data. The sending station receives the
`pacing response from the receiving station, immediately
`transfers a ?xed WindoW siZe of the information to the
`transmission queue of the sending station, Waits until receiv
`ing the next pacing response from the receiving station, and
`then transfers another ?xed WindoW siZe of information to
`the transmission queue.
`The transfer of information to the transmission queue of
`a sending station has a profound effect on the ef?ciency of
`the communications interface. The transmission queue of
`the sending station lists the items of multimedia or non
`multimedia data to be transmitted from the sending station
`to a plurality of receiving stations. The transmission queue
`transmits the listed items on a ?rst come, ?rst served basis.
`The transmission queue is a limited storage buffer and When
`storage is unavailable, a transfer of data to the transmission
`queue must Wait for more storage to become available. The
`availability of storage Within the transmission queue differs
`over time, resulting in peaks and valleys in the information
`How rate through the transmission queue. Long peaks in the
`information How rate can lead to overloading and instability
`of the communications interface. This problem, the control
`of the peaks and valleys in the information How rate, is
`especially acute When multimedia data interchange, along
`With non-multimedia data interchange, occurs across the
`communications interface since multimedia data consumes a
`large portion of the bandWidth.
`
`SUMMARY OF THE INVENTION
`
`It is therefore one object of the present invention to
`provide an improved method and apparatus for interchang
`ing data Within a distributed data processing system.
`It is another object of the present invention to provide an
`improved method and apparatus for interchanging multime
`dia and non-multimedia data Within a distributed data pro
`cessing system.
`It is yet another object of the present invention to provide
`an improved method and apparatus for multimedia and
`non-multimedia data interchange With multimedia pacing
`capability in a distributed data processing system.
`The foregoing objects are achieved as is noW described.
`The ef?ciency of the communications interface is improved
`by taking advantage of the large amount of storage available
`in a typical multimedia receiving station and by utiliZing an
`intelligent multimedia pacing capability. When a multimedia
`data communications session begins betWeen a sending
`station and one of a plurality of receiving stations Which
`
`Page 10 of 16
`
`PETITIONERS' EXHIBIT 1012
`
`

`

`US 6,336,143 B1
`
`3
`support multimedia pacing capability, the receiving station
`and the sending station negotiate on pacing parameters to be
`utilized during the multimedia data communications session.
`During the multimedia data communications session, the
`receiving station transmits multimedia pacing requests to the
`sending station at negotiated set time intervals. The multi
`media pacing request includes information on the availabil
`ity of current storage for multimedia data in the receiving
`station, the minimum data time remaining in storage in the
`receiving station, a parameter to synchroniZe the interchange
`of the multimedia data betWeen the receiving system and the
`sending system and other information pertaining to the
`interchange of the multimedia data. The sending station then
`allocates various priorities to the transmission of data to the
`plurality of receiving stations in an order indicative of the
`type of data, ie multimedia or non-multimedia, and the
`information in the multimedia pacing request pertaining to
`the minimum data time remaining in storage at the receiving
`station.
`When the receiving station has only a small amount of
`multimedia time remaining in storage, the sending station
`allocates a high priority to the transmission of more multi
`media data to that receiving station. When a receiving
`station has a suf?ciently large amount of multimedia time
`remaining in storage, the sending station allocates a loW
`priority to the transmission of more multimedia data to that
`receiving station. In addition, the sending station periodi
`cally determines the availability of the transmission queue
`for output data. When the transmission queue is not readily
`available, the sending station transfers only high priority
`data to the transmission queue. HoWever, When the trans
`mission queue is available, the sending station transfers
`loWer priority data to the transmission queue as Well. The
`sending station can then supply a plurality of receiving
`stations With signi?cant multimedia data in advance of
`actual requirements When the communications interface is
`not overloaded. Thus, the multimedia pacing method of the
`present invention ?attens the peaks and valleys of the
`information How rate through the transmission queue,
`increasing the total throughput of the communication inter
`face. In addition, any type of communications interface can
`support the multimedia pacing capability utiliZing asynchro
`nous transmission rather than isochronous transmission,
`Which requires special hardWare.
`The above as Well as additional objects, features, and
`advantages of the present invention Will become apparent in
`the folloWing detailed Written description.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`The novel features believed characteristic of the invention
`are set forth in the appended claims. The invention itself
`hoWever, as Well as a preferred mode of use, further objects
`and advantages thereof, Will best be understood by reference
`to the folloWing detailed description of an illustrative
`embodiment When read in conjunction With the accompa
`nying draWings, Wherein:
`FIG. 1 is a pictorial representation of a distributed data
`processing system Which may be utiliZed to implement the
`method and apparatus of the present invention;
`FIG. 2 is a high level logic ?oW chart Which illustrates the
`transmission of multimedia and non-multimedia data in an
`order indicative of the availability of the transmission queue
`and the priority of the data in accordance With the method
`and apparatus of the present invention;
`FIG. 3 is a high level logic ?oW chart Which depicts the
`periodic allocation of priorities to multimedia data by the
`
`4
`sending station at set time intervals in accordance With the
`method and apparatus of the present invention;
`FIG. 4 is a high level logic ?oW chart Which illustrates the
`transmission of a start multimedia session request from the
`sending system in accordance With the method and appara
`tus of the present invention;
`FIG. 5 is a high level logic ?oW chart Which depicts the
`processing by the sending station of a start multimedia
`session reply in accordance With the method and apparatus
`of the present invention;
`FIG. 6 is a high level logic ?oW chart Which illustrates the
`processing of a multimedia pacing request by the sending
`station in accordance With the method and apparatus of the
`present invention;
`FIG. 7 is a high level logic ?oW chart Which depicts the
`transfer of a high priority item to a transmission queue by the
`sending station in accordance With the method and apparatus
`of the present invention;
`FIG. 8 is a high level logic ?oW chart Which illustrates the
`transfer of a loW priority item to a transmission queue by the
`sending station in accordance With the method and apparatus
`of the present invention;
`FIG. 9 is a high level logic ?oW chart Which depicts the
`response to a start multimedia session request by one of a
`plurality of receiving stations in accordance With the method
`and apparatus of the present invention; and
`FIG. 10 is a high level logic ?oW chart Which illustrates
`the periodic transmission of multimedia pacing requests at
`set time intervals by one of a plurality of receiving stations
`in accordance With the method and apparatus of the present
`invention.
`
`10
`
`15
`
`25
`
`35
`
`DETAILED DESCRIPTION OF PREFERRED
`EMBODIMENT
`
`With reference noW to the ?gures and in particular With
`reference to FIG. 1, there is depicted a pictorial represen
`tation of a distributed data processing netWork 8 Which may
`be utiliZed in accordance With the method and system of the
`present invention. As may be seen, distributed data process
`ing netWork 8 may include a plurality of networks, such as
`Local Area netWork (LAN) 10 and 32, each of Which
`preferably includes a plurality of individual computers 12
`and 30, respectively. Of course, those skilled in the art Will
`appreciate that a plurality of Intelligent Work Stations (IWS)
`coupled to a host processor may be utiliZed for each such
`netWork.
`As is common in such data processing systems, each
`individual computer may be coupled to a storage device 14
`and/or a printer/output device 16. One or more such storage
`devices 14 may be utiliZed, in accordance With the method
`of the present invention, to store the various ?les containing
`multimedia or non-multimedia data Which may be periodi
`cally accessed, processed and interchanged by a user Within
`distributed data processing netWork 8 in accordance With the
`method of the present invention. In a manner Well knoWn in
`the prior art, each ?le containing multimedia or non
`multimedia data may be stored Within a storage device 14
`Which is associated With a Resource Manager or Library
`Service, Which is responsible for maintaining and updating
`all ?les associated thereWith.
`Still referring to FIG. 1, it may be seen that distributed
`data processing netWork 8 also includes multiple central
`computer systems, such as central computer system 18,
`Which may be preferably coupled to Local Area NetWork
`(LAN) 10 by means of communications link 22. In one
`
`45
`
`55
`
`65
`
`Page 11 of 16
`
`PETITIONERS' EXHIBIT 1012
`
`

`

`US 6,336,143 B1
`
`5
`embodiment of the present invention, central computer
`system 18 may be an IBM Application System/400,
`although other computer systems, such as an IBM/System/
`370 or PS/2 could also be utiliZed. In addition, central
`computer system 18 may not be necessary if one or more
`Local Area Networks (LANs) are suf?cient to connect all
`desired users.
`Central computer system 18 may also be coupled to a
`storage device 20 which may also serve as remote storage
`for Local Area Network
`10. Similarly, Local Area
`Network (LAN) 10 may be coupled via communications
`link 24 through a subsystem control unit/communications
`controller 26 and communications link 34 to gateway server
`28. Gateway server 28 is preferably an individual computer
`or Intelligent Work Station (IWS) which serves to link Local
`Area Network (LAN) 32 to Local Area Network (LAN) 10
`such that multimedia and non-multimedia data may be easily
`transmitted and received between individuals within either
`network containing multimedia data in accordance with the
`method of the present invention. Gateway server 28, in one
`preferred embodiment of the present invention, may be an
`IBM Application System/400.
`As discussed above with respect to Local Area Network
`(LAN) 32 and Local Area Network
`10, a plurality of
`?les may be stored within storage device 20 and controlled
`by central computer system 18, as Resource Manager or
`Library Service for the ?les thus stored. Of course, those
`skilled in the art will appreciate that central computer system
`18 may be located a great geographical distance from Local
`Area Network (LAN) 10 and similarly, Local Area Network
`(LAN) 10 may be located a substantial distance form Local
`Area Network (LAN) 32. That is, Local Area Network
`(LAN) 32 may be located in California, while Local Area
`Network (LAN) 10 may be located in Texas and central
`computer system 18 may be located in New York.
`As will be appreciated upon reference to the foregoing, it
`is often desirable for users within one portion of distributed
`data processing network 8 to be able to transmit multimedia
`and non-multimedia data to other users within distributed
`data processing network 8. The method and apparatus of this
`invention may be utiliZed to transmit multimedia data and
`non-multimedia data a between one portion of distributed
`data processing network 8 to other users within distributed
`data processing network 8 across any type of communica
`tions interface. The transmission may occur between two
`local area networks such as Local Area Network (LAN) 10
`and Local Area Network (LAN) 32 across Gateway Server
`28. The transmission may also occur across a communica
`tions interface between a Local Area Network (LAN) and a
`Wide Area Network (WAN), such as ISDN, or across a
`communications interface between two Wide Area Net
`works
`The method and apparatus of the present invention may
`also be utiliZed to transmit multimedia data and non
`multimedia data between individual stations such as 12 and
`30 within a Local Area Network (LAN) across a commu
`nications interface, such as central computer 18. In addition,
`multiple communication interfaces could be involved in the
`transmission of multimedia and non-multimedia data. The
`second (or third, or fourth, etc.) communications interface
`then acts as the receiving station to the sending station or the
`prior communications interface when multimedia data is
`transmitted in accordance with the present invention. Thus,
`the distributed data processing network 8 illustrates only one
`eXample of the many possible communications interfaces
`which may be utiliZed with the method and apparatus of the
`present invention.
`
`10
`
`15
`
`25
`
`35
`
`45
`
`55
`
`65
`
`6
`The transmission of multimedia data is generally accom
`plished in the prior art by isochronous transmission of the
`multimedia data. If pacing of data is utiliZed, a ?xed window
`siZe of information is transmitted by the sending station
`upon receipt of a pacing response, regardless of the load
`across the communications interface. It should be apparent
`that a need eXists for a method whereby multimedia data
`may be interchanged efficiently with a more intelligent
`pacing capability across any communications interface
`within a distributed data processing network such as dis
`tributed data processing network 8.
`Referring now to FIG. 2, a high level How chart is
`illustrated which depicts the transfer by a sending station of
`multimedia and non-multimedia data to a transmission
`queue in an order indicative of a priority associated with the
`data and the availability of the transmission queue, in
`accordance with the method and apparatus of the present
`invention. The process begins at block 36 and thereafter
`passes to block 38 which illustrates a determination of
`whether or not a multimedia communications session is to
`start. The determination to start a multimedia data commu
`nications session can be initiated by the sending station or by
`a message from one of a plurality of receiving stations. If a
`determination is made to start a multimedia communications
`session, block 40 depicts the transmitting of a start multi
`media session request to one of a plurality of receiving
`stations from the sending station. FIG. 4 illustrates in more
`detail the transmission of the start multimedia session
`request from the sending station. The present process then
`passes to block 42 which illustrates the processing of the
`start multimedia session reply sent from a receiving station,
`in response to the start multimedia session request. The
`processing of the start multimedia session reply is depicted
`in more detail in FIG. 5. The process then returns to block
`38 which depicts again a determination whether or not a
`multimedia communications session is to start.
`In the event a multimedia communication session is not to
`start, as determined within block 38, the process passes to
`block 44. Block 44 illustrates a determination whether or not
`a multimedia communications session is complete. If a
`multimedia communications session is complete, the pro
`cess passes to block 46 which depicts the removal of the data
`being interchanged within the completed multimedia com
`munications session from the list of priorities to be trans
`ferred to the transmission queue. The process then returns to
`block 38. Referring again to block 44, in the event a
`multimedia communications session is not complete, the
`process passes to block 48. Block 48 illustrates a determi
`nation of whether or not a multimedia pacing request has
`been received from one of a plurality of receiving stations.
`If a multimedia pacing request has been received, the
`process passes to block 50 which depicts the processing of
`the multimedia pacing request. The discussion accompany
`ing FIG. 6 describes the processing of the multimedia pacing
`request in greater detail. The process then returns to block
`38.
`Referring again to block 48, if a multimedia pacing
`request has not been received from a receiving station, the
`process passes to block 52. Block 52 illustrates the deter
`mination of whether or not space is available within the
`transmission queue and whether or not data is allocated as
`high priority multimedia data. Allocation of a data item as
`high priority can be accomplished by attaching a ?ag to the
`data item to designate it as such, or as in the preferred
`embodiment described herein, a data item is allocated as
`high priority by placing the data item, or its address, as an
`item on a high priority list. Similarly, a data item is allocated
`
`Page 12 of 16
`
`PETITIONERS' EXHIBIT 1012
`
`

`

`US 6,336,143 B1
`
`7
`as medium priority or loW priority by placing the data item,
`or its address, as an item on a medium priority list or a loW
`priority list, respectively.
`Still referring to block 52, if space is available on the
`transmission queue and an item is allocated to the high
`priority multimedia data list, the process passes to block 54.
`Block 54 depicts the transfer of the high priority multimedia
`data item to the transmission queue. Amore detailed descrip
`tion of the transfer of high priority multimedia data item is
`described With respect FIG. 7. The process then returns to
`block 38. Referring again to block 52, in the event space is
`not available on the transmission queue or an item is not
`allocated to the high priority multimedia data list, the
`process passes to block 56. Block 56 illustrates the deter
`mination Whether a data item is on the medium priority data
`list and Whether space is available on the transmission
`queue. Non-multimedia data is alWays allocated to the
`medium priority data list While multimedia data is never
`allocated to the medium priority data list in the depicted
`embodiment of the present invention. If a data item is on the
`medium priority data list and space is available on the
`transmission queue, the process passes to block 58 Which
`depicts the transfer of the medium priority data item to the
`transmission queue. The process then returns to block 38.
`Referring again to block 56, in the event a data item is not
`on the medium priority data list or space is not available on
`the transmission queue, the process passes to block 60.
`Block 60 illustrates the determination of Whether space is
`available on the transmission queue and Whether a data item
`is on the loW priority multimedia data list. If space is
`available on the transmission queue and a data item is on the
`loW priority multimedia data list, the process passes to block
`62, Which depicts the transfer of the loW priority data to the
`transmission queue. A more detailed discussion of the trans
`fer of the loW priority data to the transmission queue
`accompanies FIG. 8. Depending upon the implementation of
`the process, it may be appropriate to maintain a constant
`value for the availability of the transmission queue betWeen
`the determinations illustrated in block 52 and block 60. For
`example, the availability of the transmission queue may be
`a set variable established at block 52. A constant value for
`the availability of the transmission queue ensures loW pri
`ority data Will not be sent before high priority data if the real
`time availability of the transmission queue changes betWeen
`the determination illustrated in block 52 and block 60. After
`the transmission of loW priority data to the transmission
`queue, the process again returns to block 38.
`Referring again to block 60, if space is not available on
`the transmission queue or a data item is not on the loW
`priority multimedia data list, the process returns to block 38.
`Although only three priority lists, a high priority multimedia
`data list, a medium priority list, and a loW priority multi
`media data list, are illustrated in the high level logic flow
`chart of FIG. 2, a person With skill in the art Will appreciate
`t