if? N ,x
`
`SAN 2 is 1998
`
`7:3ng
`
`K 3
`
`T
`
`@ueee JOURNAL ON
`
`.
`
`_p
`
`greew
`
`SELECTED AREAS IN
`COM MU NICATIOBLS
`
`A PUBLICA110N OF THE IEEE COMMUNICATIONS SOCIETY
`
`'_.-':
`-—~
`
`t=
`
`JANUARY 1996
`
`VOLUME 14
`
`NUMBER 1
`
`ISACEM
`
`(ISSN 0733—8716)
`
`
`
`
`
`
`Guest Editorial
`
`......................................................... N. D. Georganas, R. Steinmetz, and T. Nakagawa
`
`1 P
`
`APERS
`
`Overview and Reference Models
`
`G. Blakowski and R. Steinmetz
`A Media Synchronization Survey: Reference Model, Specification, and Case Studies
`A Temporal Reference Framework for Multimedia Synchronization ............... M. J. Pe’rez-Luque and T. D. C. Little
`Continuity and Synchronization in MPEG ...................................... P. V. Rangan, S. S. Kumar, and S. Rajan
`
`5
`36
`52
`
`User Perception
`
`Human Perception of Jitter and Media Synchronization ....................................................... R. Steinmetz
`
`61
`
`Modeling
`
`A New Multimedia Synchronization Model ...................................................................... M. Haindl
`’ Modeling Logical and Temporal Synchronization in Hypermedia Systems ................................................
`......................................................... P. Se’nac, M. Diaz, A. Leger, and P. de Saqui-Sannes
`
`Synchronization Representation and Traffic Source Modeling in Orchestrated Presentation ...............................
`.......................................................... S. V. Raghavan, B. Prabhakaran, and S. K. Tripathi
`Doing FLIPS: FLexible Interactive Presentation Synchronization ............ J. Schnepf, J. A. Konstan, and D. H.-C. Du
`Using Timed CSP for Specification Verification and Simulation of Multimedia Synchronization .........................
`.............................................................. A. F. Ates, M. Bilgic, S. Saito, and B. Sarikaya
`AnEFSM—Based Multimedia Synchronization Model and the Authoring System ........... C. -M. Huang and C. —M. L0
`
`Mechanisms
`
`Distributed Source-Destination Synchronization Using Inband Clock Distribution .................. C.-S. Li and Y. Ofek
`Multimedia Group Synchronization Protocols for Integrated Services Networks ............... I. F. Akyildiz and W. Yen
`Clock Hierarchies: An Abstraction for Grouping and Controlling Media Streams ........... K. Rothermel and T. Helbig
`AGeneral—Purpose Multimedia Synchronization Mechanism Based on Causal Relations .................................
`..................................... J.—P. Courtiat, L. Fernando Rust da Costa Carmo, and R. Cruz de Oliveira
`
`73
`
`84
`
`104
`114
`
`126
`138
`
`153
`162
`174
`
`185
`
`‘
`
`Fault Recovery
`
`
`
`Exception Handling and Fault-Tolerance in Multimedia Synchronization .......................................... K. Naik 196
`
`
`
`Pae1
`
`(Continued on Back Cover)
`Ericsson Exhibit 1007
`
`Ericsson Exhibit 1007
`Page 1
`
`

`

`
`
`
`
`IEEE COMMUNICATIONS SOCIETY
`
`telecommunications including telephone.
`The field of interest of the IEEE Communications Society consists of all
`television, by
`facsimile, and point-to-point
`telegraphy,
`electromagnetic propagation including radio: wire; aerial, underground, coaxial, and submarine cables; waveguides, com
`munication satellites, and lasers; in marine, aeronautical,
`space. and fixed station servies; repeaters, radio relaying, signal storage, and regeneration; telecormnunication error dete
`ction and correction; multiplexing and carrier techniques;
`communication switching systems; data communications; and communication theory.
`In addition to the above, this JOURNAL or the IEEE TRANSACATIONS ON COMMUNICATION
`
`payment of the annual Society membership fee of $23.00. Members may received this JOURNAL upon payment of an additional $25.00 ($48.00 total). the IEEE TRANSACATIONS
`ON COMMUNICATIONS upon payment of an additonal $27.00 ($50.00 total), or both publications upon payment of an additional $52.00 ($75.00 total). For information on joining,
`write to the IEEE at the address below. Member copies of Transactions/Journals are for personal use only.
`
`IEEE COMMUNICATIONS SOCIETY
`JOURNAL Editorial Board 1996
`
`T. J. PLEVYAK, Director ()fPulJ/ications
`Bell Atlantic
`
`A. M. BUSH
`NSF
`4201 Wilson Boulevard
`Room 1175
`Arlington, VA 22230
`
`N. K. CHEUNG
`Bellcore, Rm. NVC 32—219
`331 Newman Springs Rd.
`Red Bank, NJ 07701
`
`J. F. HAYES
`Dept. Elec. Eng.
`Concordia Univ.
`1455 De Maissonneuve
`Montreal, Quebec
`Canada H3G 1M8
`
`W. H. TRANTER, Editor-in-Chief
`Dept. Elec. Eng.
`Univ. Missouri—R0113
`Rolla, MO 65401—0249
`tranter@ee.umr.edu
`Senior Editors
`T.S. RAPPAPORT
`The Bradley Dept. Elec. Eng.
`615 Whittemore Hall
`Virginia Polytech. Inst. & State Univ.
`Blacksburg. VA 24061—011 l
`
`M. KAWASHIMA
`Fujitsu Inst. Comp. Sci.
`1—17—25 Shinkamata
`Ota—Ku
`Tokyo 144—00, Japan
`
`SUE L. MCDONALD, Executive Editor
`Bellcore. Rm. 2P—291
`445 South Street
`Morristown, NJ 07960—1910
`sue@thumper.bellcore.com
`
`N. MAXEMCHUK
`AT&T Bell Labs.
`600 Mountain Ave.
`Murray Hill, NJ 07974
`
`W.D. SINCOSKIE
`Bellcore, Rm. 2Q—286
`445 South Street
`Morristown, NJ 07960—1910
`
`R. YATSUBOSHI
`Fujitsu Labs.
`1015 Kamikodanaka Nakahara—ku
`Kawasaki 211, Japan
`
`L. B. MILsTEIN
`Dept. Elect. and Comput. Eng.
`Mail Code 0407
`Univ. of California, SD
`La Jolla. CA 92093
`
`W. BUx
`IBM Res. xLab. Zurich
`Saumerstrasse 4
`8803 Ruschlikon ZH
`Switzerland
`
`D. P. TAYLOR
`Dept. E & E Engineering
`Univ. of Canterbury
`Private Bag 4800
`Christchurch, New Zealand
`
`THE INSTITUTE OF ELECTRICAL AND ELECTRONICS ENGINEERS, INC.
`Officers
`WALLACE S. READ President
`JOEL B. SNYDER, Vice President, Professional Activities
`CHARLES K. ALEXANDER. President-Elect
`W. KENNETH DAWSON, Vice President, Publication Activities
`TSUNEO NAKAHARA. Secretary
`RAYMOND D. FINDLEY, Vice President, Regional Activities
`DONALD C. LOUGHRY, Vice President, Standards Activities
`HOWARD L. WOLFMAN, Treasurer
`BRUCE A. EISENSTEIN, Vice President, Technical Activities
`JERRY R. YEARGAN, Vice President, Educational Activities
`THEODORE W. HISSEY, JR.. Executive Director
`CELIA L. DESMOND, Director, Division IIIVCommunications Technology Division
`Executive Staff
`DANIEL J. SENESE, General Manager
`RICHARD D. SCHWARTZ. Stafi“ Executive, Business Administration
`ANTHONY J. FERRARO, Stafi‘ Executive, Publications
`
`ANDREW G. SALEM, Managing Director, Standards Activities
`IRVING ENGELSON. Managing Director, Corporate Activities
`W. THOMAS SUTTLE, Managing Director, Professional Activities
`PETER A LEWIS, Managing Director, Educational Activities
`ROBERT T. WANGEMANN, Managing Director, Technical Activities
`CECELIA JANKOWSKI, Managing Director, Regional Activities
`Transactions/Journals Department
`Staff Director: PATRICIA WALKER
`Transactions Manager: GAIL S. FERENC
`Electronic Publishing Manager: JERI L. UZZO
`Editorial Manager: VALERIE CAMMARATA
`Managing Editor: GERALDINE E. KROLIN
`Senior Editor: SCOTT DISANNO
`Associate Editor: LAURA L. TUCKER
`Assistant Editor: LYLE SMITH
`
`IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS is published nine times a year in January, February. April, May, June, August, September. October, and December
`by the Institute of Electrical and Electronics Engineers. Inc. Responsibility for the contents rests upon the authors and not upon the IEEE, the Society/Council, or its members.
`IEEE Corporate Office: 345 East 47 Street, New York. NY 10017-2394. IEEE Operations Center: 445 Hoes Lane, PO. Box 1331. Piscataway, NJ 08855-1331. NJ Telephone:
`908-981-0060. Price/Publication Information: Individual copies: IEEE Members $10.00 (first copy only), nonmembers $20.00 per copy. (Note: Add $4.00 postage and handling
`charge to any order from $1.00 to $50.00. including prepaid orders.) Member and nonmember subscription prices available upon request. Available in microfiche and microfilm.
`Copyright and Reprint Permissions: Abstracting is permitted with credit to the source. Libraries are permitted to photocopy for private use of patrons, provided the per-copy fee
`indicated in the code at the bottom of the first page is paid through the Copyright Clearance Center, 222 Rosewood Drive. Danvers, MA 01923. For all other copying, reprint,
`or republication permission, write to Copyrights and Permissions Department, IEEE Publications Administration. 445 Hoes Lane, PO. Box 1331, Piscataway, NJ 08855-1331.
`Copyright © 1996 by The Institute of Electrical and Electronics Engineers. Inc. All rights reserved. Second»class postage paid at New York. NY and at additional mailing offices.
`Postmaster: Send address changes to lEEE JOURNAL ON SELECTED AREAS 1N COMMUNICATIONS, IEEE. 445 Hoes Lane. PO. Box 1331, Piscataway, NJ 088554331. GST
`Registration No. 125634188. Printed in USA.
`
`Ericsson Exhibit 1007
`
`.“.3._.4
`
`.,-;:_—fiw_‘a—E._._
`
`m
`
`HH.>—I.Hnnr~t—>~
`
`til
`
`61‘
`
`Gt
`
`
`, Pace
`_
`
`Ericsson Exhibit 1007
`Page 2
`
`

`

`
`
`(Continued from Front Cover)
`
`Implementation
`
`
`
`.jJ A Multimedia Synchronization Model and Its Implementation in Transport Protocols ....................................
`‘
`............................................................................... C.-C. Yang and J.-H. Huang
`
`dJ Client—Server Synchronization and Buffering for Variable Rate Multimedia Retrievals ...................................
`
`................................................................... J. Y. Hui, E. Karasan, J. Li, and J. Zhang
`MultiSync: A Synchronization Model for Multimedia Systems ................................. H.-Y. Chen and J.-L. W
`A Programming Model and System Infrastructure for Real-Time Synchronization in Distributed Multimedia Systems ..
`
`........................ G. S. Blair, G. Coulson, M. Papathomas, P. Robin, J.-B. Stefani, F. Horn, and L. Hazard
`Synchronization of Multimedia Data for a Multimedia News-on—Demand Application ....................................
`
`.......................................................... L. Lamont, L. Li, R. Brimonz, and N. D. Georgan‘ash
`
`
`Personal Communications—Services, Architecture and Performance Issues ................................................
`Networking and Performance Issues of Personal Mobile Communications ..............................................
`
`Real-Time Video Services in Multimedia Networks ........................................................................t
`
`Advances in ATM Switching Systems for B-ISDN ......................................................................... ,x»,
`. u
`Computer—Aided Modeling, Analysis and Design of Communications ......................... ,........................... ~
`
`
`CALL FOR PAPERS
`
`,4
`
`
`
`IEEE COPYRIGHT FORM .....................................................................................
`
`Upcoming Issues of the
`IEEE JOURNAL ON
`
`SELECTED AREAS IN COMMUNICATIONS
`
`
`
`I
`Topic
`Circuit Switching for Broadband ISDN and Beyond
`
`Wireless Local Communications
`Optical Networks
`
`Integrated Video-Based Services for the Home
`
`Distributed Multimedia Systems and Technology
`
`Code Division Multiple Access Networks III and IV
`Wireless ATM
`Cumputational and Artificial Intelligence in High Speed Networks
`Network Support for Multipoint Communication
`Advances in ATM Switching Systems for B-ISDN
`
`Real-Time Video Services in Multimedia Networks
`
`Computer—Aided Modeling, Analysis, and Design of Communication Links
`
`Personal Communications—Services, Architecture, and Performance Issues
`
`Networking and Performance Issues of Personal Mobile Communications
`*Issue of J—SAC in which the Call for Papers first appears.
`
`l
`
`
`
`Date of Call"?L
`June 1994
`..
`‘
`
`‘
`
`June 1994
`December
`
`December
`
`December
`
`
`
`
`
`
`January 19
`May 1995‘
`
`August 19'“
`
`August 1995'
`Decemb
`l
`
`December:
`
`Decernb’esrj
`Decemba’”
`
`December I
`
`
`
`
`Ericsson Exhi
`
`
`
`
`Ericsson Exhibit 1007
`Page 3
`
`

`

`‘
`
`,
`
`‘
`
`l
`I
`
`,
`
`'
`
`'rl
`
`EKEEMAN (’96)
`.
`
`Director of Chapters
`
`and Elections
`, JR.
`
`..
`
`I
`
`'
`
` '
`
`
`‘
`INFORMATION FOR AUTHORS
`II
`Each issue of the IEEE JOURNAL ON SELECTED AREAS [N COMMUNICATIONS (J-SAC) is devoted to a specific technical area within the scope of the IEEE Communications Society.
`ll
`1‘ Papers submitted to the IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS (J-SAC) must be targeted to a specific J-SAC issue for which a call—for-papers has been publisl'led.
`These calls—for—papers are published in J—SAC and in other appropriate publications of the IEEE Communications Society. In general, material which has been previously copyrighted,
`published, or accepted for publication will not be considered for publication in the IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS. Exceptions to this rule include items
`that have had limited distribution have been printed in Abstract form only. or have appeared in Convention Records or Digests. All papers are considered on the basis of their
`individual merit alone, and the fact that a paper may have been accepted for presentation at a conference does not ensure its acceptance for publication in the IEEE JOURNAL 0N
`SELECTED AREAS IN COMMUNICATIONS. In many cases. a conference paper must be substantially deepened and revised to meet the technical and presentational standards maintained
`by the JOURNAL. A manuscript identical to or largely based upon a conference paper must be so identified.
`Journal papers should adhere to the following criteria: be no more than 20 double or 1 1/2 spaced typewritten pages (using one side of the sheet only and excluding
`figures); contain an informative 75—200 word abstract outlining the scope of the paper; and be in 12—point type with l—inch margins all around. Introductory discussion
`should he kept to a minimum, and material published elsewhere should be referenced rather than reproduced or paraphrased. Authors should strive for maximum clarity
`‘ of expression, bearing in mind that the purpose of publication is dissemination of technical knowledge, and that an excessively complex or poorly written presentation
`an only obscure the significance of the work described. Care should be taken in the organization of the paper. such that a logical and consistent progression of thought
`, 5:5 evident. It is strongly suggested that theorems, derivations, calculations, and other elements of a paper which are not essential to the continuity of the text be placed in
`appendixes. Authors with language difficulties should, whenever possible, obtain the assistance of a colleague fluent in English or one of the International Committee
`, Emir-men before submitting a manuscript for publication.
`All authors must enclose signed IEEE copyright forms when their paper is submitted for publication. All papers should have company clearance before submission and are
`tuned to contain no proprietary material unprotected by patent or patent application. Responsibility for technical content and for protection of proprietary material rests solely
`“1
`with the author and the author's organization, and is in no way the responsibility Of the IEEE or its editorial staff. The format of manuscript submitted to the IEEE JOURNAL ON
`my
`- AREAS IN COMMUNICATIONS must follow IEEE editorial and typographical standards, as described in “Information for [EEE Authors," available on request from the IEEE
`ticus/Joumals Department. 445 Hoes Lane, Piscataway, NJ 0885541331. In particular. illustrations must be provided which are suitable for reproduction within one column
`. moat redrawing or retouching.
`
`Five copies each of the abstract, the manuscript, and the illustrations (but not the original illustrations themselves) should be submitted for consideration to the Guest Editor
`“the issue to which the paper is targeted. All submissions are reviewed by competent referees who will recommend acceptance, modification. or unacceptability of the material
`'
`JOURNAL publication. Supplementary materials, such as biographies and original illustrations, will be requested when needed for publication. Authors of accepted manuscripts
`
`be asked to provide the final version of their manuscript on a floppy disk along with a hard copy. Further information will be provided closer to the publication date. After a
`uusctipt has been accepted for publication. the author's company or institution will be requested to pay a charge of $110 per printed page to cover part of the cost Of publication.
`charges for this JOURNAL are not obligatory, nor is their payment a prerequisite for publication. The author will receive 100 free reprints if the page charge is honored, Detailed
`
`non will accompany the page proof.
`IEEE Communications Society
`
`1996 Board of Governors
`Officers
`DECINA, President
`P. E. GREEN, Jr., Past President
`
`‘co di Milano/Cefriel
`IBM Research
`WEINSTEIN, VP-Technicol Affairs
`G. A. LEDBETTER. Secretary/Executive
`Director
`
`IEEE ComSoc
`Members at Large
`T. J. PLEVYAK (‘97)
`Bell Atlantic
`B. PRASADA (’95)
`Bell Northern Res.
`H. RUDIN. Jr. ('95)
`IBM Research
`Directors
`R, P. SKILLEN, Director ofMeetings and
`Conferences
`Northern Telecom Ltd.
`Meetings and Conferences Department
`INFOCOM Conf Board
`H. A. FREEMAN
`Lanworks Inc.
`Americas Con]: Board
`V. BHARGAVA
`Univ. of Victoria
`Asia/Pacific Conf. Board
`L. LEE
`Nat. Taiwan Univ.
`Tutorials Conf. Board
`H. SOBOL
`Univ. Texas
`Applications & Syst. Eng. Dev.
`Board
`I. EBERT
`Bell-Northern Res,
`Fundamental Res. Dev. Board
`I... B. MILSTEIN
`Univ. Calif—San Diego
`Product & Syst. Develop.
`R. P. SKILLEN
`Northem Telecom Ltd.
`
`S. B. WEINSTEIN, President-Elect
`NEC USA. Inc.
`J. R. B. DE MARCA. VP-Internalionol
`Cetuc-Puc/Rico
`
`L. LEE (’96)
`National Taiwan Univ.
`J. L. LOCICERO (’96)
`Illinois inst. Technol.
`L. B. MILSTEIN ('95)
`Univ. CA at San Diego
`
`C. L. DESMOND, VP—Member Affairs
`Stentor Res. Ctr., Inc.
`G. A. LEDBE’ITER, Acting Treasurer
`IEEE ComSoc
`
`R. K. SNELLING (’96)
`Georgia Inst. Technol.
`F. TOSCO (’97)
`CSELT
`D. N. ZUCKERMAN (’97)
`AT&T Bell Labs
`
`J. N. DAlGLE. Director of Education
`Univ. of Mississippi
`
`T. J. PLEVYAK, Director of Publications
`Bell Atlantic
`
`Director
`R. P. SKILLEN
`Northern Telecom Ltd.
`GLOBECOM/ICC Conf. Board
`R. C. ANDERSON
`Southwestern Bell Telephone
`MILCOM Conf Board
`E. BRADY
`TRW Space Commun.
`OFC Conf Board
`P. E. GREEN, JR.
`IBM Research
`Europe/Middle East/Africa Conf
`Board
`F. TOSCO
`CSELT
`Directed Growth Conf. Board
`R. HORN
`Northern Telecom
`
`Publications Board
`A. JAJSZCZYK. The Global
`T. J. PLEVYAK, Director of
`Publications
`Commun. Newsletter
`Bell Atlantic
`T. G. ROBERTAZZI, ComSoc
`J. L. LOCICERO, Transactions
`Editorfor IEEE Press
`Editorein~Chief
`SUNY at Stonybrook
`Illinois Inst. Technol.
`J. DERBY. ComSoc Editorfor
`W. H. TRANTER. Journal
`Multimedia Magazine
`Editor-in-Chief
`IBM Corp.
`Univ. Missouri-Rollin
`N. K. CHEUNG, ComSoc Editorfor
`H. T. MOUFTAH, Communications
`Journal of Lighrwove Technology
`Bellcore
`Magazine Editor‘inAChief
`Queen’s Univ.
`D. FELDMEIER, Network
`Magazine Editor—in-Chief
`S. LAM, IEEE/ACM Transactions
`on Networking Editor—ineCliief
`Univ. Texas, Austin
`H. AHMAD]. IEEE Personal
`Commun. Editor—in-Chief
`IBM Research
`
`
`
`
`
`,
`
`Bellcore
`liv. & Access Syst.
`
`
`
`. dz Manage.
`
`g‘STE'l'T Group
`
`In Software
`
`ENE Systems Inc.
`Switching
`
`
`George Mason Univ.
`in Systems Integration
`
`
`
`Technical Activities Council
`Computer Communications
`M. J. KAROL. AT&T Bell Labs.
`Data Communications
`K. JOSEPH, Gen. Datacomm Ltd.
`Enterprise Networking
`D. N. ZUCKERMAN.
`AT&T Bell Labs.
`Gigabit Networking
`I. RICHER. MITRE Corp.
`Interconnection in High-Speed
`Digital Systems
`M, GOODMAN. Bellcore
`Internet
`L. ZHANG
`Xerox Palo Alto
`Multimedia Communications
`J. DERBY, IBM Corp.
`Optical Communications
`K. OGAWA. AT&T Bell Labs.
`
`Representatives
`Int. Telecommun. Union
`PACE
`J. S. RYAN
`(to be determined)
`Intelligent Transport. Syst.
`Solid—State Circ. Council
`A. TZES
`S. TEWKSBURY
`Neural Networks Council
`G. FETTWEIS
`K, BAKHRU
`Standards Board
`A. EPHREMIDES
`I. N. KNIGHT
`OFC Steering Committee
`Steering Committee for J.
`P. E. GREEN. Jr.
`Lighrwove Technol.
`H. L. LEMBERG
`K. LIU
`P_ R. TRISCHIITA
`
`Personal Communications
`S. RAPPAPORT, State Univ. NY
`Quality Assurance Management
`R. BOLDOSSER, Shilay Assoc,
`Radio Communications
`H. BOE, US West Commun.
`Satellite & Space Commun.
`S. KATO. NTT Radio Commun.
`Syst. Labs.
`Signal Processing and
`Communication Electronics
`5. KARTALOPOULOS, AT&T Bell
`Labs.
`Signal Processing for Storage
`M. MELAS, IBM
`Transmission & Access Systems
`S. S. GORSHE. NEC America
`
`Ericsson Exhibit 1007
`
`Page 4
`
`Ericsson Exhibit 1007
`Page 4
`
`

`

`212
`
`IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS, VOL. 14, NO 1, JANUARY 1996
`
`A Multimedia Sync onization
`Its Implementation in Transport
`
`el
`
`IS
`
`Chun-Chum Yang and Jau-Hsiung Huang, Associate Member, IEEE
`
`implementation of a synchronization mechanism
`Abstract-An
`in transport protocol to support multimedia applications over
`a packet or cell switched network is proposed. In designing
`such a mechanism for practical use, ease of implementation and
`capability of handling random delay of packets are two key
`issues for success. Since the random delay of packet or cell
`switched networks makes synchronization among media more
`complicated after the transmission across the network, a model
`which considers the random transmission delay is hence required
`to specify the temporal relationship among media. Therefore,
`a real-time synchronization model is presented to satisfy this
`requirement in the paper. Based on the proposed synchronization
`model, a transport protocol, namely multimedia synchronization
`transport protocol, is designed and implemented. The perfor-
`mance measurement of such a protocol is also presented.
`
`I. INTRODUCTION
`ITH THE increasing power of modern computers and
`high-speed network technologies, the integration of
`multiple media into a single network application becomes
`possible; such as video conferencing, shared workspace and
`groupware systems [ 11-[SI. For multimedia applications, syn-
`chronization is a very important issue which means the inter-
`media temporal relationship has to be satisfied across the
`network. To tackle such a problem, we have to first examine
`the characteristics of packethell switched network and the
`characteristics of media.
`Two major problems of packet or cell switched network
`supporting real-time multimedia applications are random delay
`and lost packets, due in large part to buffer overflow. Hence,
`the temporal relationship among media may be destroyed at
`the receiver even if they were sent in synchronization by the
`sender. Worse yet, since each medium is usually transmitted
`through a separate connection and the quality of service of
`connections may be different; the delay characteristics of
`different media may be different. Thus, a synchronization
`mechanism should be implemented at the receiver to regain
`the synchronization among media.
`Much work [9]-[13] has been done in describing the syn-
`chronization model for multimedia applications. Among those,
`Petri-net based models provide a good method to specify
`temporal relationships. ,A modified Petri-net model, object
`
`Manuscript received August 7, 1994; revised April 5, 1995.
`The authors are with the Communications and Multimedia Laboratory,
`Depatment of Computer Science and Information Engineering, National
`Taiwan University, Taipei, R.O.C., Taiwan (e-mail: jau@csie, nut.edu.tw).
`Publisher Item Identifier S 0733-87 16(96)00228-4.
`
`P
`
`t4
`
`V : video, Tx : text, A : audio
`
`Fig. 1. An example of Petri net based synchronization model.
`
`composition Petri net (OCPN) model [lo], [ll], has been
`proved to have the ability to specify any arbitrary temporal
`relationship among media and it may be applied to both
`stored-data applications and live applications. The extended
`OCPN (XOCPN) [12] can additionally specify the commu-
`nication functions. In [13], user actions are also considered.
`However, when taking the real-time issue of multimedia and
`the random delay of packethell networks into consideration,
`OCPN/XOCPN and other Petri net based models are not
`sufficient to deal with the late transmission of packets. Here,
`we define late transmission of a packet to be that the packet
`fails to reach its destination in time (i.e., exceeding its real-
`time constraint) and should be dropped. We explain the
`insufficiency of OCPN by the example shown in Fig. 1 in
`the following.
`We may treat the example in Fig. 1 as an MTV-like applica-
`tion in which there is music (audio) and corresponding video
`frames and text (subtitle) on the screen. In Fig. 1, we only
`show two cycles of a cyclic model of the application and the
`interpretation of transition tl to t 3 follows. Simultaneously, the
`application plays audio A I , displays two video frames VI, V,
`orderly, and displays text Txl. Fig. 1 shows that transition
`t 3 will be fired only after V2, A1 and Txl finish playing.
`Similarly, transition t 5 will be fired only after Vq, A2, and
`Txa finish playing.
`In the following, we examine the characteristics of audio,
`video, and text data. For audio data, it is very jitter sensitive
`and cannot tolerate random delay between audio segments;
`hence, by holding A2 too long after finishing AI will result in
`unrecognizable audio quality. For video frames, by dropping
`a small portion of video frames or by having a small random
`delay between video frames may only have a minor impact on
`human eyes and may be acceptable. For text data, it has the
`least jitter sensitivity compared to audio and video. Based on
`such an observation, we notice that audio data is much more
`jitter sensitive than video and text data.
`
`0733-8716/96$05.00 0 1996 IEEE
`
`Authorized licensed use limited to: National Taiwan University. Downloaded on March 24, 2009 at 01:53 from IEEE Xplore. Restrictions apply.
`
`Ericsson Exhibit 1007
`Page 5
`
`

`

`YANG AND HUANG A MULTIMEDIA SYNCHRONIZATION MODEL AND ITS IMPLEMENTATION IN TRANSPORT PROTOCOLS
`
`213
`
`In Fig. 1 based on OCPN model, if A1 and Txl have
`finished playing but Vz is late due to network congestion,
`transition t 3 can not be fired until Vz arrives and finishes
`playing. For this late transmission of V2, A2 car1 not be played
`even if its data has arrived. However, this is improper since
`audio is very jitter sensitive as explained earlier. Therefore, a
`natural thought in handling this situation is to fire transition
`t 3 right after finishing A1 to activate A2 in order to maintain
`the audio quality. Clearly, the unfinished video frames in Vz
`will be dropped.
`However, any of the earlier proposed Pelri net models
`does not allow firing transition t 3 before finishing V,. More
`precisely, they only describe the synchronization relationship
`under perfect network condition or require a known network
`delay bound for video-on-demand type of applications. In wide
`area packetkell networks, it is impractical to make such an
`assumption since the upper bound of network delay is too
`large to support live applications such as video conference.
`Hence, a new model will be proposed in this paper and is
`named as Real-Time Synchronization Model (6:TSM). As will
`be explained in Section 11, the definition and firing rules of
`RTSM are different from the Petri-net based models.
`There is another question raised after defining the RTSM
`model. That is, where do we place the synchrclnization mech-
`anism in the network architecture? We have two1 choices for the
`answer: 1) in the application, or 2) in the transport protocol.
`To place the synchronization mechanism in the application
`means that the application has to handle all the synchroniza-
`tion control for itself, which will introduce more overhead
`to the application. However, more complex synchronization
`relationships can be supported if the synchronization mecha-
`nism is implemented in the application. Multimedia titles and
`documents with complex synchronization relationships and no
`repeated cycles (as in Fig. 1) may be applications of this
`category.
`On the other hand, we can place the synchroinization mecha-
`nism in the transport protocol. A transport protocol supporting
`synchronization mechanism is trying to simulate an end-to-
`end connection as a circuit, where the receiving application
`receives data with the same temporal relationship as they
`were sent by the sender. Hence, the application at the receiver
`simply has to receive and play data since the synchronization
`is provided by the transport protocol. Thus, the design of
`applications is simplified. Applications such as video con-
`ference where a simpler synchronization relationship with
`repeated cycles may belong to this category. In this paper,
`we apply the proposed RTSM model in tlhe design of a
`new transport protocol, namely Multimedia Synchronization
`Transport Protocol (MSTP) for synchronization purpose.
`As to the part of the transport protocols, much work
`[ 141-[24] has been done in discussing high-speed transport
`protocols. The goals of these protocols are fixused on high-
`throughput or low-latency. The issue of real-time synchroniza-
`tion in multimedia applications is rarely addressed [25]-[29].
`In [25], Huitema and Dabbous discussed the synchronization
`relationship between different types of data. However, that
`model did not address the real-time characteristics of media,
`and it could not achieve more complex sync'hronization rela-
`
`tionship since it had only two types of data (RT, DT). In this
`paper, MSTP is presented to support more general services.
`The remainder of this paper is organized as follows. In
`Section 11, the RTSM and the concept of key medium and
`time medium are presented. The goal of key medium and time
`medium is to handle situations when data must be dropped
`due to late transmissions. Section I11 describes the architecture,
`the packet format, and the synchronization control mechanism
`of MSTP. The implementation and performance evaluation
`of MSTP are discussed in Section IV. Finally, Section V
`concludes this paper.
`
`11. REAL-TIME SYNCHRONIZATION MODEL (RTSM)
`Before introducing the definition of RTSM, we explain some
`terminologies used in the model. The elements in RTSM
`include place, token, and transition, as in the OCPN model
`[lo]. The places are used to represent the medium unit
`(such as audio segments, video frames, or text strings) and
`their corresponding actions (such as playing audio, displaying
`video, or text on the screen). There could be one or zero
`token within a place to represent the state of the place. A
`place without token means the place is currently inactive.
`A place with a token is active and could be in one of the
`two states: token is blocked or unblocked. When a token is
`just added into a place, the corresponding action of the place
`can be executed, and before finishing the action, the token is
`blocked. The token in the place is unblocked after the action is
`finished. Transitions are used to represent the synchronization
`relationship between places. However, the places in RTSM are
`divided into two types further, and a new firing rule for RTSM
`is also proposed for the real-time issue. We explain the new
`idea in the following.
`Considering the example in Fig. 1, in order to avoid the
`unexpected blocking due to late transmission, we need a
`mechanism to enforce some blocked transitions to be fired
`under the situation of late transmissions. In RTSM, there are
`two kinds of places as regular places and enforced places. To
`differentiate an enforced place from a regular place, a double
`circle is drawn for enforced place as shown in Fig. 2 where
`transition t 3 is fed by two regular places, Vz and Txl, and
`one enforced place, Al.
`The firing rule about enforced places is that once an
`enforced place gets unblocked, the transition following it will
`be immediately fired regardless of the states of other places
`feeding this transition. Therefore, if A1 becomes unblocked
`in Fig. 2, transition t 3 will be immediately fired regardless
`of the states of Vz and Tzl. At the same time, tokens in
`the places before transition t 3 , such as Vl,V2 or Tzl, must
`be cleared since these places are obsolete due to the firing
`of t 3 . We call this action of clearing all obsolete tokens
`backtracking, since the action is backtracked from the fired
`transition in RTSM. In this way, the synchronization anomaly
`due to late transmission is solved. The following are the
`complete definition, firing rules and backtracking rules of
`RTSM. Notice that with the inclusion of enforced places and
`enforced firing, this synchronization model is different from
`Petri net in nature. However, there are still some similarities
`
`Authorized licensed use limited to: National Taiwan University. Downloaded on March 24, 2009 at 01:53 from IEEE Xplore. Restrictions apply.
`
`Ericsson Exhibit 1007
`Page 6
`
`

`

`214
`
`IEEE JOURNAL ON SELECTED AREAS W COMMUNICATIONS, VOL. 14, NO. 1, JANUARY 1996
`
`n
`
`t4
`
`The stop point
`of backtracking
`
`A backtracking
`
`Fig. 2. An RTSM model for the example in Fig. 1.
`
`saithg transitii
`
`\=/ ei
`
`place