United States Patent [19]
`Sreenan
`
`[54] RESOURCE MANAGEMENT SYSTEM FOR A
`BROADBAND MULTIPOINT BRIDGE
`
`[75] Inventor: Cormac J. Sreenan, Green Village.
`NJ.
`
`[73] Assignee: Lucent Technologies Inc., Murray Hill.
`NJ.
`
`[21] Appl. No.: 851,056
`[22] Filed:
`May 5, 1997
`
`Related US. Application Data
`
`[63] Continuation of Ser. No. 560,446, Nov. 17, 1995, aban
`cloned.
`
`[51] Int. (31.6 ................................................. .. G06F 15/176
`[52] US. Cl. ................................ .. 395/200.56; 395/200.7;
`395/200.59; 370/17; 370/54; 370/8513
`[58] Field of Search .......................... .. 395/200.56, 200.7,
`395/20059; 370/8513, 17, 54
`
`[56]
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`4,905,282 2/1990 McGlynn et a1. ...................... .. 380/48
`5,086,426 2/1992 Tsukakoshi et a1. .
`370/8513
`5,131,016
`7/1992 Broughton et a1. ..
`.... .. 375/240
`5,309,437
`5/1994 Perlman et a1.
`370/8513
`5,341,477
`8/1994 Pitkins et al.
`395/20009
`5,426,637
`6/1995 Derby et a1, .
`370/8513
`5,461,611 10/1995 Drake, Jr. et al.
`370/54
`
`5,485,455
`
`1/1996 Dobbins et al. . . . . .
`
`. . . . . . .. 370/60
`
`5,509,123
`5,526,344
`5,530,695
`
`395120015
`4/1996 Dobbins et a1.
`370/16
`6/1996 Diaz et a1. ..... ..
`6/1996 Dighe et a1. ............................ .. 370/17
`
`OTHER PUBLICATIONS
`
`“Video conferencing, ?le storage, and management in mul
`timedia computer systems”, Rangan, P.V., Computer Net
`works and ISDN Systems 25, (1993) pp. 901-919.
`
`USO05742772A
`[11] Patent Number:
`[45] Date of Patent:
`
`5,742,772
`Apr. 21, 1998
`
`“Panel-Discussion Multimedia Conferencing over ATM
`Network”. Wakahara, T., and Unemoto, K., IEEE Com. Soc.
`Int. Conf. 0n Multimedia Communications, May 1994.
`“Multipoint Multimedia Conferencing”, Clark, W.J.. IEEE
`Communications Magazine, May 1992, pp. 44-50.
`“Issues of Reserving Resources in Advance”, Wolf, L.C., et
`211.. 5th Int. Workshop on Network and 0p. Sys. Support For
`Digital Audio & Video, Apr. 1995.
`“A Standards-Based Multimedia Conferencing Bridge”,
`Horn, D.N., et al., AT&T Technical Journal, Jan/Feb. 1993.
`pp. 41-49.
`“A Versatile Audio Bridge for Multimedia Conferencing”,
`Horn. D.N. and Shanna, A., Proc. of IEEE ICC ’94, pp.
`1754-1762.
`“Montage: Continuous Presence Teleconferencing Utilizing
`Compressed Domain Video Bridging”, Gaglianello, RD.
`and Cash, G.L., Proc. of IEEE [CC ’95, pp. 573-581.
`
`Primary Examiner-Robert B. Harrell
`Assistant Examiner—Saleh Najjar
`
`[57]
`
`ABSTRACT
`
`An electronic bridge resource management system, having a
`programmatically-implemented processing system. A bridge
`service interfaces with a plurality of clients and receives a
`quality of service (QOS) speci?cation from each of the
`clients. A resource manager receives a QOS speci?cation
`from the bridge service, distributes at least one QOS con
`straint associated with the QOS speci?cation across ?ow
`processing modules of a channel, determines resource
`requirements for each of the flow processing modules, and
`then determines whether bridge resources can be allocated to
`meet the QOS speci?cation. The clients may alter their QOS
`speci?cations and retry if the resource manager denies them
`admission because of a lack of available bridge resources.
`
`20 Claims, 5 Drawing Sheets
`
`
`
`24\ GROUP, CLIENT AND CHANNEL: comm AND ACCESS ll
`
`CONTROL y
`
`l
`
`FEEDBACK
`
`25\ SYNCHRONIZATION, COMBINATION, TRANSFORMATION
`
`,gg‘g‘gli],
`
`28\B1s[m SIGNALLING, AAL/ATM PROCESSING, DATA TRANSMlT/RECEIVE Egg‘
`
`1
`
`DATA m
`
`om our
`
`CISCO Exhibit 1007, pg. 1
`
`

`
`US. Patent
`
`Apr. 21, 1998
`
`Sheet 1 0f 5
`
`5,742,772
`
`FIG. 1
`
`MULTIMEDIA [12
`TERMINAL
`
`MULTIMEDIA [12
`TERMINAL
`
`MULTIMEDIA f1 2
`TERMINAL
`
`MULTIMEDIA _/—t2
`TERMINAL
`
`FIG. 2
`
`vIDED fIB
`PROCESSING
`IL
`“
`
`14
`
`BROADBAND ATM NETWORK
`
`u
`U
`AUDIo [20
`PROCESSING
`
`m
`/
`
`PROCESSING
`\
`
`22
`
`SERVICE
`HOST
`
`16
`
`CISCO Exhibit 1007, pg. 2
`
`

`
`US. Patent
`
`Apr. 21, ‘1998
`
`Sheet 2 of 5
`
`5,742,772
`
`FIG. 3
`
`24% GROUP, CLIENT AND CHANNEL: CONTROL AND ACCESS
`CONTROL T
`FEEDBACK
`
`II
`
`SBERéBECEE
`
`26\-
`
`SYNCHRONIZATION. COMBINATION, TRANSFORMATION
`
`PFESéENSNSEhG
`
`II
`
`28x BISDN SIGNALLING, AAL/ATN PROCESSING, DATA TRANSMIT/ RECEIVE
`
`NlfgévgsK
`
`DATA ' IN
`
`DATA OUT
`
`CISCO Exhibit 1007, pg. 3
`
`

`
`Apr. 21, 1998
`
`Sheet 3 of 5
`
`5,742,772
`
`FIG. 4
`
`CLIENT A
`
`AUDIO
`
`7
`
`CLIENT B
`
`AUDIO
`
`FIG. 5
`
`I
`
`44
`
`1
`
`2 4
`
`6
`
`1 AND 2
`
`1
`
`1
`
`2
`
`CONVERT
`
`SYNCHRONIZE
`
`CISCO Exhibit 1007, pg. 4
`
`

`
`US. Patent
`
`Apr. 21, 1998
`
`Sheet 4 of 5
`
`5,742,772
`
`FIG. 6
`
`@60
`70@ RESERVATION MANAGER
`66
`
`64
`
`SYNCHRONIZATION
`CONTROLLER
`
`COMBINATION
`CONTROLLER
`
`62
`
`TRANSFORMATION
`CONTROLLER
`
`72
`
`68
`
`'
`
`/
`RESOURCE SCHEDULERS
`
`MEMORY
`/
`52
`
`'
`
`OSPs
`l
`54
`
`CPUs
`K
`56
`
`NETWORKS
`I
`58
`
`CISCO Exhibit 1007, pg. 5
`
`

`
`U.S. Patent
`
`Apr. 21, 1998
`
`Sheet 5 of 5
`
`5,742,772
`
`FIG. 7
`
`BRIDGE
`SERVICE
`
`OOS
`MANAGER
`
`RESERVATION COMBINATION
`CONTROLLER
`MANAGER
`
`~ (5)
`‘'''‘"_-—-> I5)
`
`(8)
`
`(7)
`
`~
`
`(9) A
`
`_
`
`-
`
`T
`
`-
`
`CLIENTA CLIENTB CLIENTC
`(1)
`
`CREATE
`CLIENT
`
`(2)
`
`CREATE
`GROUP
`
`(3)
`
`CREATE
`CHANNEL
`
`(4)
`JOIN
`CHANNEL
`
`TO
`CREATE (
`)
`CLIENT
`JOIN
`GROUP
`
`CHAONNEL ‘
`
`(11)
`
`CREATE
`CLIENT _
`
`JOIN
`GROUP ‘
`JOIN
`CHANNEL
`
`CISCO Exhibit 1007, pg. 6
`
`

`
`5,742,772
`
`1
`RESOURCE MANAGEMENT SYSTEM FOR A
`BROADBAND MULTIPOINT BRIDGE
`
`This is a continuation of application Ser. No. 08/ 560,446,
`?led on Nov. 17. 1995, now abandoned.
`
`FIELD OF THE INVENTION
`The present invention relates to a system for efficiently
`allocating broadband bridge resources. In particular, the
`system allows client applications to negotiate quality of
`service contracts with a bridge resource manager.
`
`10
`
`2
`SUMMARY OF THE INVENTION
`
`A bridge provides a set of services to enable efficient
`operation of multipoint applications. In a broadband context,
`the task of designing a multipoint bridge is complicated by
`several factors, including diiferent media types, asynchro
`nous (packet) communications, and heterogeneous termi
`nals. The present invention is directed to resource manage
`ment within a broadband multipoint bridge.
`According to one aspect of the invention. an electronic
`bridge resource management system comprises a
`programmatically-implemented processing system having
`bridge service and resource manager software. The bridge
`service interfaces with a plurality of clients'and receives a
`quality of service (QOS) speci?cation from each of the
`clients. The resource manager receives the QOS speci?ca
`tion from the bridge service and distributes at least one QOS
`constraint associated with said QOS speci?cation across the
`?ow processing modules of a channel. The resource man
`ager then determines the resource requirements for each of
`the ?ow processing modules, and determines whether bridge
`resources can be allocated to meet the QOS speci?cation. As
`part of the QOS contract negotiation process, the clients may
`alter their QOS speci?cations and retry if the resource
`manager denies them admission because of a lack of avail
`able resources.
`According to a second aspect of the invention, a method
`is provided for implementing a bridge degradation policy
`where a client passes service degradation policy information
`to the bridge. The degradation policy information relates to
`a prioritization amongst either clients. channels. or groups.
`The bridge then stores data corresponding to the degradation
`policy information in the appropriate client, channel or
`group data structure. The bridge implements the speci?ed
`degradation policy should a bridge resource overload occur.
`
`DESCRIPTION OF THE DRAWINGS
`
`The invention will be described in greater detail below
`with reference to the attached drawings, of which:
`FIG. 1 is a diagram showing a typical bridge system
`con?guration.
`FIG. 2 is a diagram showing an example of a distributed
`bridge.
`FIG. 3 is a functional block diagram illustrating the
`overall bridge architecture.
`FIG. 4 is a diagram illustrating the basic FPMs and ?ows
`for a single (audio) channel, two client conference.
`FIG. 5 is a diagram showing several examples of multi
`port FPMs.
`FIG. 6 is a diagram illustrating the components of the
`bridge software architecture for QOS management.
`FIG. 7 is a chart illustrating interactions between clients
`and bridge for forming a three client audio conference.
`
`DESCRIPTION OF THE PREFERRED
`EMBODINIENT
`In the following description of the preferred embodiment,
`a “group” refers to a collection of clients that participate in
`a multi-user application. For each group that the bridge is
`asked to create. it maintains a data structure.
`A client is a software program that runs at a multimedia
`terminal and interacts with the bridge service to allow a user
`to take part in a group. In order to participate in a particular
`multi-user application. a user is expected to select and run
`the corresponding client program. For example. a user could
`
`BACKGROUND OF THE INVENTION
`As the deployment of high-speed networking accelerates
`to reach homes and o?ices. the popularity of multi-user
`applications is expected to increase dramatically. Examples
`of these applications include conferencing. game playing.
`collaborative working and distance learning. Multi-user
`applications usually involve diiferent information types,
`such as control data. video, images and audio, which are
`exchanged between the various user terminals, i.e.. they are
`multipoint. Designing a system to support these multi-media
`multipoint applications presents two key challenges: a scal
`able technique for managing potentially complex
`interactions. and the use of resources in an e?icient and
`economical fashion. In the Narrowband-ISDN context, these
`issues are addressed for multi-user conference calls by using
`a bridge. also known as a multipoint control unit (MCU). A
`bridge is a logically centralized service that performs data
`combination and conference management. e.g., adding!
`dropping users. It accepts audio from each of the users,
`mixes the signals and transmits the resulting signal in return,
`thereby enabling multipoint communication over point-to
`point links.
`In a packet based network like Broadband-ISDN, it is of
`course possible to provide these bridge functions in a
`distributed manner at sophisticated terminals, e.g., personal
`computers (PCs) and workstations. However, there are
`cogent arguments for the use of a bridge in this scenario also.
`Simple terminals will continue to be attached to the network
`and may not be capable of supporting these functions.
`Directly attached ATM devices. as well as telephones, fall in
`this category. By providing a logically centralized focus of
`control. many of the management issues are simpli?ed,
`notably with respect to maintaining accurate state informa
`tion and providing secure access. Regarding the use of
`bandwidth, a bridge-based solution can be highly e?icient,
`avoiding any unnecessary data transmission. For example,
`one doesn’t need to receive individual (bandwidth intensive)
`audio and video channels from each user.
`Designing a broadband bridge is considerably more com
`plex than for the narrowband network and raises several
`issues which must be addressed in order to make this
`approach viable. The focus of the present invention is on
`how to efficiently manage bridge resources, an issue which
`is motivated by the following four considerations. Firstly,
`the range of applications is much wider, demanding a greater
`?exibility in terms of bridge functions and the resources they
`demand. Secondly, the capabilities of terminals will vary. as
`will the types of compression and data channel processing
`that they support. Thirdly. use of a packet network in
`combination with variable bit rate tra?ic such as compressed
`video. introduces issues of bridge resource management
`akin to those for the network itself. Fourthly. operation of the
`bridge can have serious consequences for the end to end
`Quality of Service (QOS) received by audio and video
`channels. notably in regard to delay and packet loss.
`
`15
`
`25
`
`35
`
`45
`
`55
`
`65
`
`CISCO Exhibit 1007, pg. 7
`
`

`
`5 .742,772
`
`10
`
`20
`
`25
`
`35
`
`3
`participate in a multi-player game and a multi-user confer
`ence by running both the game and conference clients.
`Client information is recorded in a bridge-maintained data
`structure.
`Associated with a group are one or more channels. where
`each channel allows communication of a speci?c informa
`tion type between the clients in the group. Examples of
`information types are audio. video and Whiteboard data. A
`channel is represented by a bridge-maintained data structure
`and realized using a set of dedicated ?ow processing mod
`ules (FPM s) and connecting ?ows (described in detail later).
`For an audio conference with three clients. for example. the
`channel consists of a pair of flows for I/O to each client and
`an audio mixing FPM at the bridge.
`Each user participates in a group by interacting with a
`bridge using his/her terminal, typically via a graphical user
`interface (GUI). Terminals may take many forms. including
`PCs and set-top boxes, and are equipped with broadband
`network access and some I/O devices. such as a display,
`speaker. microphone and/or a camera. Application software.
`running on the terminal or its agent (e.g.. a PC controlling
`access to a telephone) uses a signalling protocol such as
`remote procedure call (RPC) to interact with the bridge
`service.
`The bridge service is software running on the bridge to
`implement the application programmer’s interface (API) to
`the services provided by the bridge. A bridge is designed to
`allow simultaneous access by multiple groups. The broad
`band network is used to transport control information (i.e..
`signalling) and data tra?ic over virtual circuits between the
`bridge and terminals. Data tra?ic includes continuous media
`(CM) such as audio and video. which may be used depend
`ing on particular application requirements, user preferences
`and terminal capabilities.
`FIG. 1 shows a typical system con?guration where a
`bridge 10 and various multimedia terminals 12 are intercon
`nected by a broadband ATM network 14. A bridge is a
`computer system designed to handle large internal and
`external data bandwidth. such as available on modern class
`server machines (e.g., Silicon Graphics Inc. Challenge
`servers). A network service provider may implement a
`bridge server as a switch adjunct in an intelligent network.
`The bridge 10 may be physically realized using a collection
`of networked hosts. offering perhaps, media-speci?c facili
`ties such as video processing. Such a distributed bridge
`arrangement is illustrated in FIG. 2 Where a bridge service
`host 16. a video processing host 18. an audio processing host
`20. and a data processing host 22 are interconnected by the
`broadband network 14 itself. Moreover. the concepts of the
`present invention could also be supported by multiple coop
`erating bridges.
`The bridge service API allows user applications (clients)
`to access the facilities of a bridge 10. When a request is
`received by the bridge service it is processed and a reply is
`returned to the client. indicating success or failure. As part
`of processing each request the bridge service may initialize
`or modify state information which it maintains to record
`information about groups and clients. The interface to the
`bridge 10 is de?ned by the API and associated state infor
`mation. The interface might also support multi-level groups
`(e.g.. to allow sub-conferences).
`As already de?ned. a group refers to a collection of clients
`that participate in a multi-user application involving a bridge
`10. For each group..the bridge service maintains a data
`structure as part of its state information. It also maintains
`per-client information. with a distinct client data structure
`
`4
`for each group in which a user participates. These data
`structures maintained by the bridge. and their constituent
`?elds, are as follows:
`Group Data Structure
`1. group identi?er
`2. list of current clients (i.e.. the participants)
`3. group owner (the creator by default)
`4. current status (e.g.. starting, ongoing. paused. future
`reservation)
`5. schedule (start time/date. duration)
`6. floor control policy (e.g., open. selected client
`coordinates. bridge coordinates requests sequentially)
`7. access control policy (e.g.. open. restricted client list)
`8. setup mode (active-bridge initiated. passive)
`9. billing (e.g.. owner. equal client shares. usage-based)
`10. media channels (number and type. e.g., video. audio.
`whiteboard)
`Client Data Structure
`1. client identi?er
`. user details (name. address)
`. client address
`. authentication key (cryptographic key)
`. current group (can be null)
`. current status (active/inactive)
`. event reporting (on/off. event mask)
`. acceptable data formats (compression. coding)
`. available media devices (types. capabilities)
`10. list of current channels
`11. media channel mask
`12. presentation options (e.g.. window quadrants. audio
`based selection)
`Several pararneterized calls are provided as part of the
`API. including those to: (1) create and destroy a group; (2)
`create and destroy a client; (3) allow a client to join or leave
`a group; and (4) set or get attributes of a group or client.
`As illustrated in FIG. 3, the bridge architecture comprises
`three basic elements: the bridge service 24. channel pro
`cessing 26, and network access 28. The bridge service 24
`implements the API and grants bridge access to clients,
`groups and channels. Some of the channels being used in a
`group may require processing by the bridge 10 (the channel
`processing function 26 in the present invention is performed
`by the FPMs). In particular. CM may be operated on to
`perform synchronization. combination and/or transforma
`tion. Synchronization is essential so that temporal relation
`ships between CM can be maintained. Combination refers to
`functions which can be applied to a set of CM. e.g..
`individual gain controls for audio. and image scaling for
`video. The need for transformation arises due to the use of
`heterogeneous data formats and device capabilities. For
`example, one multimedia terminal might have an MPEG
`compression board while the other participant has only
`JPEG support. The bridge must also access the broadband
`network 14 in order to receive and transmit control and data
`(including CM). and execute the appropriate communica
`tions protocols. For example. the network access function 28
`of the bridge supports BISDN signalling. AAL/ATM
`processing. and data transmit/receive.
`An important requirement in operating a bridge 10 is
`performance. In other words. how to give clients access to
`a group with a level of performance that is acceptable and
`predictable. This in turn demands an appropriately designed
`resource management system. In the narrowband case this is
`
`40
`
`45
`
`50
`
`55
`
`65
`
`CISCO Exhibit 1007, pg. 8
`
`

`
`5,742,772
`
`15
`
`5
`drastically simpli?ed by the fact that the maximum band
`width is low, even for CM, and the current usage easily
`determined by the number of active physical network con
`nections. In addition, the set of processing functions is
`usually quite limited and statically de?ned, allowing imple
`mentation using a bank of DSPs. For a broadband bridge,
`however, the set of processing functions will be larger and
`will need to be capable of being dynamically updated, e.g.,
`to accommodate a new video compression format. This
`places an increased emphasis on software implementations.
`Furthermore, the maximum bandwidth will be signi?cant
`and, more importantly, may vary even for a given CM
`channel, making it more di?icult to determine current usage
`requirements. The present invention therefore provides an
`efficient technique for managing access to bridge resources.
`In essence, a bridge 10 is a server in a large distributed
`computing system. The conventional way of dealing with
`resource management in such systems is to rely on an
`operating system to control resource access by a collection
`of user-level entities, often called processes or domains. This
`allows the processes to operate independently but share a
`common platform. For a broadband bridge, this could take
`the form of a bridge service that instantiates a process to deal
`with each new group. That process'would then deal with its
`client’s requests, and perform channel processing and dis
`tribution. Each process would make requests to the operat
`ing system in order to access resources, such as CPUs,
`DSPs, memory and network I/O. While this is a reasonable
`model, it makes it di?icult to allocate resources in a manner
`which is both e?icient and can ensure predictable schedul
`ing. For a broadband bridge, a ?ner degree of resource
`management is desirable. This is important in order to
`support the Quality of Service (QOS) requirements of CM
`channels, which typically have stated delay, jitter and loss
`tolerances.
`In general terms, a QOS contract is an agreement with a
`resource provider for use of that resource to satisfy a speci?c
`performance requirement. QOS de?nes the expected perfor
`mance for data transport on a ?ow. It is speci?ed as a set of
`parameters describing the type of QOS contract, traffic and
`performance. Broadband networks are designed to support
`QOS contracts on an end to end basis. In the system of the
`present invention, these contracts are extended to encompass
`bridge operation.
`-
`An architecture for QOS has a set of basic functions:
`speci?cation, negotiation, translation, admission control,
`policing and scheduling. User speci?cations describe tra?ic
`characteristics (e. g., mean/peak bandwidth, burstiness), per
`formance requirements (e.g., delay, jitter, losses), and type
`of QOS contract (e.g., guaranteed, statistical). In order to try
`to ensure that these QOS requirements can be attained. a
`user must negotiate with a QOS manager. This entails
`passing the speci?cation information and waiting to see if
`access will be granted or denied The speci?cation is trans
`lated by the QOS manager to a set of resource demands, e.g.,
`amount of memory and CPU cycles, and used in combina
`tion with knowledge of already existing applications to
`perform an admission control test. The result determines
`whether a QOS contract can be established for use of the
`system as requested. If a contract is granted, a policing
`mechanism aims to ensure that the stated source tra?ic limits
`are upheld. while the scheduling mechanism aims to try and
`meet performance requirements.
`In order to allow QOS-driven resource management for a
`broadband bridge 10, the system of the present invention
`allows clients to establish contracts for bridge access in a
`similar manner as they do for network access. Furthermore.
`
`rather than simply allocating resources based on number of
`groups, clients or channels, higher e?iciency is achieved by
`associating resources with channel processing activities.
`Such resource allocation is enabled by introducing the
`concepts of “?ows” and “?ow processing modules”.
`Recall that a group may involve several channels, some of
`which may carry CM. Each client will contribute to, and
`receive, some or all of the channels in its group. Thus, for a
`given channel, the bridge 10 will be receiving data from
`clients, operating on it. and returning the resulting data. An
`example is a group which has a single channel over which
`each client transmits its audio and receives the combined
`signal in return.
`A “?ow” is the connection for carrying data from/to a
`client and the connection for carrying data internally
`between the channel processing stages 26 of the bridge 10.
`Each channel comprises a set of ?ows. A ?ow is always
`associated with a particular channel within a group. but not
`necessarily a single client of that group. Essentially. a ?ow
`is a unidirectional pipe for data transport between ports that
`is implemented using a network virtual circuit (VC) or
`internally to the bridge 10, by using bridge memory buffers.
`The various functions 26 that can be applied to a channel
`are realized using ?ow processing modules (FPMs), which
`could be implemented as functions in a programming lan
`guage library. Each one of these implement a single well
`de?ned function and execute at run time as independently
`schedulable threads. A thread is a software program that
`exists to execute an FPM instance or process a flow within
`a client. Thus, once a given FPM is selected, an instance of
`that FPM is created and assigned to a thread for execution.
`Each FPM is designed to receive data for a particular
`channel on one or more input ?ows, process it to perform a
`self-contained function, and then transmit the resulting data
`on its output ?ow(s). A simple example of a FPM is one
`which is responsible for receiving ?ow data from an incom
`ing network VC. More sophisticated examples include
`FPMs for combining audio and performing video format
`conversions. As part of its de?nition, a FPM may accept
`parameters which tailor its behavior. For example, a JPEG
`video compression FPM would accept a quantization factor.
`Each PPM performs software initialization and core pro
`cessing. Once an instance of an FPM is created, it performs
`initialization which involves interpreting control
`parameters, setting up data structures, etc. The FPM instance
`then enters a loop where its core processing takes place. In
`particular, this is a loop in which the FPM reads data from
`its input ?ow(s), processes it and writes the results to its
`output ?ow(s). Core processing may be implemented in
`diiferent ways independent of the FPM’s functional de?ni
`tion. For example, an audio combination FPM may be
`executed on a CPU or using a DSP. Traditionally DSPs have
`been used to support audio and image manipulation, but with
`faster processor speeds and suitably designed compression
`techniques it is possible to implement many such features in
`software (e.g., a video mixer) thereby facilitating the incre
`mental addition of new bridge functions.
`-
`Software allocates bridge resources to each FPM instance
`admitted for execution. Such allocations are an important
`aspect of the present system. It is by controlling how each
`thread accesses the bridge resources that QOS contracts can
`be honored.
`FIG. 4 shows the use of FPMs to implement a two client
`conference with just a single (audio) channel. where client
`A 30 and client B 32 communicate via the bridge 10. Two
`FPMs 34. 36 are used for receiving audio information and
`two FPMs 38. 40 are used for transmitting audio informa
`
`25
`
`35
`
`40
`
`45
`
`55
`
`65
`
`CISCO Exhibit 1007, pg. 9
`
`

`
`5 ,742,772
`
`7
`tion. Flows 42 carry data to/from the bridge and interconnect
`the FPMs for a given channel. Data is processed in a
`pipeline, arriving ?'om the network and traveling on ?ows
`through a sequence of FPMs.
`FPMs are allowed to have more than one input and output
`port. A port is an end-point for communication over a ?ow.
`It is associated with a particular thread, running on either the
`bridge or a multimedia terminal. FIG. 5 shows four
`examples of multiport FPMs: a Convert FPM 44 having a
`single input and output port; a Synchronize FPM 46 having
`two input ports and two output ports; a combine FPM 48
`having two input ports and a single output port; and a select
`FPM 50 having two input ports and a single output port.
`Each FPM also has control and feedback ports for interact
`ing with the bridge service (not shown).
`The FPM/?ow model requires extensions to the bridge
`service API and state information as previously presented.
`Data structures for a channel, ?ow and FPM/Thread are as
`follows:
`Channel Data Structure
`1. channel identi?er
`2. channel type (e.g., audio. video, data, animation, etc.)
`3. owner (e.g.. group identi?er)
`4. list of ?ows (flow identi?ers)
`5. list of FPMs (module identi?ers)
`Flow Data Structure
`1. ?ow identi?er
`. owner (default is group)
`. source (hostlthread/port)
`. sink (host/thread/port)
`. network VC information (e.g., AFM address, unicast or
`multicast VC)
`. QOS (contract type, tra?ic and performance)
`’ FPM/Thread Data Structure
`
`15
`
`20
`
`25
`
`30
`
`. module identi?er
`. owner (default is group)
`. control/event ports
`. list of input ports
`. list of output ports
`. operating parameters
`. resource handles (a “ticket” allowing access to allo
`cated bridge resources)
`Access to the above items is achieved by extending the
`API with the following parameterized calls: (1) create and
`destroy a channel; (2) join and leave a channel; and (3) set
`and get channel attributes.
`The FPM/?ow model aims to simplify the process of
`translating a client’s requirements for service quality and
`bridge functions in terms of actual resource needs. As
`mentioned. resources are allocated so that a thread can
`execute an instance of an FPM. In the bridge, these resources
`(represented in FIG. 6) are memory 52, DSPs 54. CPUs 56,
`internal and external bus/network access 58. Other resources
`used to transport or process data may also be allocated. e.g.,
`switches.
`'
`FIG. 6 shows the components of the software architecture
`needed for resource management within a bridge. Access to
`the bridge is by way of the Bridge Service 60. which passes
`requests on to the resource management system. ‘There are
`three levels of resource management. the lowest being the
`individual resource schedulers 62. which allow access to
`resources by those FPMs admitted for execution. A resource
`scheduler selects from amongst waiting FPMs according to
`a scheduling policy. In order to allow performance con
`
`8
`straints to be satis?ed, a scheduling algorithm of the type
`used in fast packet switches is employed, i.e.. support for
`priority and time deadlines. At the middle level are three
`controllers, de?ned for synchronization 64. combination 66.
`and transformation 68 FPMs, one for each of the three types
`of processing that the bridge implements. These keep track
`of the available FPMs and can estimate their resource
`requirements for a given parameter and tra?ic set. At the top
`level is the QOS Manager 70. This can be viewed as a
`higher-level scheduler which performs admission control
`and coordinates resource access. A resource handle is an
`identi?er issued by the QOS Manager 70 for use by an FPM
`to gain access to a particular resource. This is achieved by
`presenting the handle to the appropriate resource scheduler
`62. At the same level as the QOS Manager 70 is the
`Reservation Manager 72, which allows longer term man
`agement by handling advance reservation of bridge
`resources.
`In order to explain the detailed interactions of the three
`levels of resource management. an example will be used. A
`three client audio-only conference and the various interac
`tions necessary to realize it is shown in FIG. 7. The owner
`makes arequest (1) to the Bridge Service 60 to create a client
`which we call Client A. and subsequently to create a group
`(2) that will have a total of three clients, a single audio
`channel, and which is to start immediately. The bridge
`service 60 allocates and initializes client and group data
`structures. returning an indication of success to Client A.
`Client A then requests (3) that the channel be created. and
`that a FPM for audio combination should be associated with
`it. If successful, the channel data structure and a FPM data
`structure (for the audio combination FPM) are created by the
`bridge service. Client A then requests (4) to join that
`channel, supplying the QOS parameters (i.e., the QOS
`speci?cation) it expects for the ?ow to be received from the
`bridge.
`It is at this point that the Bridge Service 60 calls (5) on the
`QOS Manager 70 to decide whether the client should be
`admitted for execution. Admission control involves three
`basic steps: constraint distribution. resource translation, and
`admission decision. Constraint distribution involves a soft
`ware algorithm for decomposing the overall QOS con
`straints (as given in the speci?cation) in terms of operating
`constraints for the individual threads which are executing
`FPMs for that channel. Various approaches can be used for
`implementing constraint distribution. One approach is to
`simply distribute the constraints equally. A more sophisti
`cated approach corresponds to a two phase protocol used for
`virtual circuit establishment in some wide area ATM net
`works. In the ?rst phase the network QOS speci?cation is
`passed sequentially through each switch between the source
`and sink aiming to satisfy the overall constr