Patent Publication Number: US-8526336-B2

Title: Conference resource allocation and dynamic reallocation

Description:
FIELD OF THE INVENTION 
     The present invention relates generally to the field of packet-based communication networks; more specifically, to apparatus and methods for conducting conferencing over a communications network. 
     BACKGROUND OF THE INVENTION 
     Conferencing systems, in which participants communicate in a conference call or meeting over existing voice and data networks, have grown increasingly complex in recent years in order to increase the number of people able to efficiently participate in a conference call. In any conferencing system, the usage of network resources is a function of the number of participants. In a traditional system, each time an end-user or object initiates a conference session to facilitate a particular call or meeting, a processor, such as a digital signal processor (DSP) associated with a multipoint control unit (MCU), sets up of media streams from the endpoints to a conference server or bridge, where the streams may be mixed and then sent back to the endpoints as individual streams. The limited resource capacity of network devices (mixers, routers, media switches, processors, etc.) coupled with the high demand for conferencing resources, means that it is essential to efficiently allocate and schedule conference call resources on a communications network. 
     Conference resource scheduling systems typically rely upon various usage metrics to determine the appropriate conference resource to allocate for a given conference. For example, resource usage metrics are often used to allocate a conference bridge—either in advance of a scheduled conference or on an on-demand basis for an ad hoc conference session. A common metric used to determine whether a bridge is to be allocated involves resource usage statistics in conjunction with some sort of round-robin or least-recently used (LRU) algorithm. 
     One of the problems with relying upon resource usage statistics when allocating conference call resources (such as a bridge) is that such statistics usually do not accurately predict the location in the network where a given user will call or join from to access or initiate a conference session. The physical location of the user in the network is important to efficient resource allocation because it can affect performance considerations such as signal latency, timing and synchronization. Optimizing performance criteria such as signal latency, timing and synchronization are important when attempting to achieve an optimal conference user experience (e.g., good audio quality). For example, if everyone participating in a conference call will be dialing into the call from a certain building, the optimal location of the bridge is at or near that building. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       The present invention will be understood more fully from the detailed description that follows and from the accompanying drawings, which however, should not be taken to limit the invention to the specific embodiments shown, but are for explanation and understanding only. 
         FIG. 1  illustrates an example communications network. 
         FIG. 2  illustrates an example method for conference resource allocation and dynamic reallocation. 
         FIGS. 3A &amp; 3B  illustrate another example method for conference resource allocation and dynamic reallocation. 
         FIG. 4  illustrates another example method for conference resource allocation and dynamic reallocation. 
     
    
    
     DETAILED DESCRIPTION OF EXAMPLE EMBODIMENTS 
     In the following description specific details are set forth, such as device types, system configurations, protocols, applications, methods, etc., in order to provide a thorough understanding of the present invention. However, persons having ordinary skill in the relevant arts will appreciate that these specific details may not be needed to practice the present invention. 
     According to one embodiment of the present invention, a mechanism is provided for improving an initial conference call resource selection or allocation by utilizing history and presence information about the users, i.e., the participants invited to the conference session. The user history information may include, for example, data such as the physical location where a particular user dialed into a conference for the last several meetings he attended. If, for instance, a user most frequently dials into a conference session from his home, that location may be used along with various resource usage metrics to select a conference bridge optimized in terms of latency, phase shift, or other quality of service (QoS) consideration. 
     Various decision algorithms, such as a weighted average probability calculation, may be applied to accumulated history and presence information about each participant in order to determine the highest probability location of each participant dialing into the conference session. By making a reasonably accurate predictive guess about a probable location where users will join a conference session from, an optimal resource selection may be made most of the time. A resource may be considered to be an optimal resource selection from, say, a latency point of view, if it provides the lowest average latency for all users in the conference session. Other metrics for average latency, such as lowest-mean-square (LMS), could also be used in accordance with different embodiments of the present invention. (Practitioners in the art appreciate that LMS-type algorithms provide a degree of fairness by avoiding large deviations from the mean latency.) Additionally, the mechanism described herein facilitates an increase in utilization of conference resources by eliminating the redundant processing of inactive media streams originating from each of the remaining endpoints. 
     In one embodiment, two kinds of user history information are relevant: conference history and presence history, both of which may be utilized when making a predictive determination of where a user will likely call from. In certain implementations, the predictor mechanism may incorporate a degree of hysteresis, or what is commonly known as a “fast-attack algorithm”, to either minimize or accentuate the impact of slight changes in presence information. 
       FIG. 1  is an example communications system  10  with endpoint devices that include VoIP phones  16  and personal computers (PCs)  14 . Each of the PCs is configured with an associated video camera; that is, each PC  14  has an associated video camera  13  to facilitate participation in a video conference session. In general, an endpoint represents an end user, client, or person who wishes to initiate or participate in an audio/video conference session and via communications system  10 . Other endpoint devices not specifically shown in  FIG. 2  that may be used to initiate or participate in a conference session include a personal digital assistant (PDA), a laptop or notebook computer, a non-IP telephone device, a video appliance, a streaming client, a television device, or any other device, component, element, or object capable of initiating or participating in voice, video, or data exchanges with communications system  10 . In operation, each of the endpoint devices shown in  FIG. 1  may join an audio/video conference session by calling into a conferencing application running on a conferencing server, e.g., conferencing resource allocator  18 . 
       FIG. 1  illustrates PCs  14  and VoIP phones  16  connected via an network  11 , which includes a plurality of conferencing call resources (e.g., conference bridges)  12  distributed at different physically locations within network  11 . Other types of call resources include media switches; mixers (e.g., a digital signal processor (DSP) or a firmware/software-based system to mix and/or switch audio/video signals received at its input ports), call gateway devices, etc. A scheduler  17  and conference resource allocator  18  are also shown connected with IP network  11 . Additionally, conference resource allocator  18  is shown connected with a database  19 . 
     It is appreciated that the media path for the conference participants (via the various endpoints shown) may include audio/video transmissions, e.g., Real-Time Transport Protocol (RTP) packets sent across a variety of different networks (e.g., Internet, intranet, PSTN, etc.), protocols (e.g., IP, Asynchronous Transfer Mode (ATM), Point-to-Point Protocol (PPP), H.323, session initiation protocol (SIP), media gateway control protocol (MGCP), etc.), with connections that span across multiple services, systems, and devices (e.g., private branch exchange (PBX) systems, VoIP gateways, etc.). 
     Scheduler  17  comprises a scheduling application, server, or any other IP communication system product, such as Cisco&#39;s MeetingPlace™ conferencing application, that allows users to schedule meeting conferences in advance or, alternatively, to set up conferences immediately by dialing out to participant parties. Cisco MeetingPlace™ is typically deployed on a corporate network behind the firewall, and facilitates scheduling of business conferences from a touch-tone or voice over IP (VOIP) telephone, or a computer, using various software clients, such as Microsoft® Outlook, or a web browser. Scheduler  17  may also comprises any of a variety of scheduling systems, such as the Calendar Facility of Microsoft® Outlook, that provide a user with the ability to propose a meeting time to one or more other users. For instance, in the Calendar Facility, the system typically checks the schedule of potential participants and sends a message to each one asking them to attend. 
     Continuing with the example of  FIG. 1 , conference resource allocator  18  comprises an application or conferencing/meeting server for establishing a scheduled conference session and for handling the control plane functions associated with the conference session. In operation, a user sets up a conference session by inviting a group of conference participants using scheduler  17 . Scheduler  17  transfers this information to conference resource allocator  18 , which then establishes the conference session by allocating and engaging the necessary media components/resources of communications system  10  to satisfy the media requirements of all of endpoint devices invited to attend the conference session. Conference resource allocator  18  may execute various algorithms (i.e., code) in order to make an a priori selection of conference call resources, and for dynamically changing the current allocation in response to changing network conditions, or other events that occur during the conference session, as described in more detail below. 
     Practitioners in the arts will understand that there exist multiple alternative ways of aggregating/disaggregating the conferencing and mixing (bridging) resources within the communication network “cloud”  11 . In other words, the details of system  10  can vary greatly depending upon application, available resources, network usage, and other particular configuration considerations. In addition, it is appreciated that the scheduler  17  and conference resource allocator  18  may be integrated or incorporated into a single application or server that runs executable code to implement the conferencing or meeting functions described herein. 
     Alternative embodiments may be implemented in software or hardware (firmware) installed in an IP communication system, PBX, telephony, telephone, and other telecommunications systems. Similarly, the signaling path may be across any network resource that may be utilized for transmission of commands, messages, and signals for establishing, moderating, managing and controlling the conference session. 
       FIG. 2  illustrates an example method for conference resource allocation and dynamic reallocation. The process starts when the conference server receives a request to establish a conference session at a particular time—either immediately or at some future date/time. In response, the conferencing server fetches history and/or presence information about the users invited to participate or expected to attend the conference session (block  21 ). Those who are expected to attend, for example, may include users who have affirmatively replied to an invitation message. 
     The history and/or presence information may be obtained, for example, by accessing a database such as database  19  shown in  FIG. 1  that stores and updates user information and other network usage statistics in an archival manner. The conferencing server/scheduler may execute an algorithm aimed at making a weighted determination or guess as to the probable current physical locations where each of the users may be expected to join from (block  22 ). Based on that determination, the system then converges on an optimal location for a given resource type, e.g., a centrally-located mixer to all the participants with fair round-trip delays. The parameters to the algorithm may include presence information of the participants and their presence history. 
     In certain embodiments, a calendaring system may be integrated with the resource scheduler/allocator. Alternatively, user information such as presence information may be extracted from other applications, e.g., an email client such as Microsoft Outlook. In Microsoft Outlook, for example, calendar information may be derived via Collaboration Data Objects. Once the list of participants is available, each participant could be queried about their presence/location. History information about the location characteristics of the invited participants may then be stored in a database associated with the conferencing scheduler/allocator. The database can also keep track of participants (user-ids) who frequently attend recurring meetings. 
     Based on the list of probable user locations, the conferencing server proceeds to find a set of available conference bridges, and other conference call resources, which provide optimal performance in terms of QoS (block  23 ). 
     By way of example, in cases where signal latency is a primary QoS consideration, latency may be determined by transmitting packet “pings” between each of the endpoints and a particular conference bridge. Alternatively, latency and/or other performance criteria may be determined from historical Real-Time Control Protocol (RTCP) information or other historical/statistical data. Note that there may be times when all of the expected users or conference participants will not be completely known, in which case the selection of the conferencing resources may not be fully optimized at the start of the conference session. However, as described in conjunction with  FIG. 4  below, in one embodiment a mechanism is provided for dynamically reallocating conference resources in response to changing network conditions or other triggering events. In other words, if an initial selection is sub-optimal due to the fact that some of the conference participants were not known before the start of the conference session, the conferencing server is operable to reallocate resources during the session based on current network conditions and the actual participants attending the meeting. 
     Continuing with the example of  FIG. 2 , once a set of conference bridges have been found that provide optimal performance (e.g., in terms of latency), one or more conference bridges are identified from among that set and allocated for the conference session using certain resource usage metrics (e.g., applying a round-robin, LRU, or some other algorithm). 
       FIGS. 3A &amp; 3B  are physical network topology diagrams that illustrate another example method for conference resource allocation and dynamic reallocation. In each of  FIGS. 3A &amp; 3B , three endpoint devices—associated with users “A”, “B” and “C”—are shown are located at certain physical distances from call resources  32  &amp;  33 . Each of call resources  32  &amp;  33  may comprise an audio mixer. In  FIG. 3A , for example, user “A” may have a roundtrip signal transmission time of 100 milliseconds to call resource  32 . User “B&#39;s” roundtrip time may be 20 ms, while user “C” may have a roundtrip time of 40 ms. In the case of non-cascaded resources, an allocation routine executed on a conferencing resource allocator may determine the average roundtrip signal transmission time between various available call resources (e.g., call recess  32  of  FIG. 3A , or call recess  33  of  FIG. 3B ) and each of the endpoint devices. Based on this determination, a particular call resource may be allocated that optimizes the average roundtrip signal transmission time between the resource and each of the user endpoint devices. In other words, the allocation routine may select an audio mixer such that it is equidistant (or nearly so) to all the participants in order to give all the participants an equal chance to grab a slot in the next available talk-burst. 
       FIG. 3B  shows such an optimal call resource allocation in which each of the users is equidistant from call resource  33 . This allocation ensures that the resource selected has the best a priori chance of providing a latency that is fair to all (or most) of the participants. Practitioners in the art understand that latency fairness is an important consideration since having a subset of users with high latency compared to the rest of the participants basically prevents them from being equal participants in the conference session. For instance, in the case of an allocation that results in an unbalanced latency situation, some endpoints may exhibit a phase-lag and be unable to grab a slot in the speaker selection at the end of a talk-burst. In other words, in many applications latency should be approximately equalized for all the participants, so that everyone participating in the conference session has the same physical distance to the mixer resource, and therefore enabling them to equally participate in the discussions. 
       FIG. 4  illustrates another example method for conference resource allocation and dynamic reallocation in which network conditions change (e.g., a new call resource becomes available) during a conference session. In such a case, the conference resource allocator operates to dynamically move the conference session to a new resource to achieve a more optimal resource allocation, thereby achieving improved performance. The process of  FIG. 4  begins at block  41 , where an initial conference resource allocation has already been made in accordance with the method described in the embodiment of  FIG. 2 . Once the conference session begins (block  42 ), any one of any number of triggering events may occur (block  43 ) that cause the system to reallocate resources for the conference session. In the absence of a triggering event, the conference session simply continues with the initial resource allocation (block of  44 ). 
     Examples of changing network conditions or events that may trigger a new allocation include: latency changes or any other quality of service issues that diminish or decrease conferencing system performance below a certain detectable threshold level; availability of new or different resources which may provide a more optimal conferencing solution; a user-based or moderator-based triggering mechanism wherein a user or moderator initiates a new allocation based on noticeable quality of service problems with the initial or current allocation; and detection of a subset of conference participants who are the most active speakers, i.e., doing most or all of the speaking, during a conference session. Any of these triggering events may be invoked automatically as part of an algorithm running on a conferencing server or conference resource allocator. 
     It is appreciated that certain embodiments may implement a feature wherein reallocation may be disabled or prohibited from occurring in situations where the conference session is nearly over. In other words, the triggering mechanism may be automatically turned off when there is, say, less than ten or fifteen minutes remaining in the conference session. In such cases it may not be worthwhile to move a conference from one resource to another resource. 
     Regardless of the particular triggering event or mechanism utilized to initiate a change in the initial allocation, reallocation of network resources is based upon the current network conditions—including currently available network/call resources—at the time the triggering event occurred (block  45 ). After a reallocation has been performed, the conferencing system waits until another triggering event occurs (block  46 ). If another triggering event does occur, resources are again reallocated based on the current network conditions (block  45 ). The process of a triggering event that causes a reallocation, followed by a new triggering event that causes another reallocation, may continue repeatedly during the conferencing session. Alternatively, in the absence of a triggering event or no new network conditions the conferencing session continues with the present allocation (block  47 ). 
     Practitioners in the art will appreciate that a variety of different implementations of the above-described methods and mechanisms are possible within the scope and spirit of the present invention. For example, in a particular implementation the conferencing server or resource allocator may periodically measure latency during the active conference session. The moment that the measured latency is significantly worse than a predicted latency or acceptable threshold level, the allocator begins searching for a better resource (e.g., bridge) available on the communications network. Note that latency may not be the only measure of audio quality that is monitored. Packet drops and other performance thresholds are other criteria or considerations that could also be used for triggering a reallocation. If a better resource is found, the conference session is moved to a new resource, provided that there is sufficient time remaining in the scheduled conference session. 
     It should be understood that there are numerous prior art methods of moving a conference session from one resource to another. 
     In a variation of the above embodiment, the conferencing server may periodically monitor all conference resources that are available to determine predicted latencies. For instance, if a conference bridge is found that is significantly better than an existing conference, and that conference bridge is currently available, the conference may be automatically moved to improve performance. 
     In still another implementation of the present invention, the conference moderator has the option of triggering a conference move. This can happen, for example, when the conference participants experience poor audio quality. Basically, when the moderator triggers a reallocation, the conference session is moved to one or more different call resources which may involve different communication channels/paths through the network. This process may be repeated by the moderator until an acceptable audio quality level is achieved. 
     In yet another embodiment of the present invention, the conferencing server/scheduler optimizes for more active participants rather than all participants. Speakers who are more active are assigned higher weights in an algorithm aimed at minimizing the average latency for the most active speakers. This approach is especially useful for large meetings or training sessions where the majority of the conversation involves a small group or subset of the meeting participants. 
     It should be understood that elements of the present invention may also be provided as a computer program product which may include a machine-readable medium having stored thereon instructions which may be used to program a computer (e.g., a processor or other electronic device) to perform a sequence of operations. Alternatively, the operations may be performed by a combination of hardware and software. The machine-readable medium may include, but is not limited to, floppy diskettes, optical disks, CD-ROMs, and magneto-optical disks, ROMs, RAMs, EPROMs, EEPROMs, magnet or optical cards, or other type of machine-readable medium suitable for storing electronic instructions. 
     Additionally, although the present invention has been described in conjunction with specific embodiments, numerous modifications and alterations are well within the scope of the present invention. Accordingly, the specification and drawings are to be regarded in an illustrative rather than a restrictive sense.