Abstract:
Enhancing performance in a multicasting system. Flow rates in a multicasting system are monitored as system characteristics change. The multicasting system is operated based on a first mapping between data flows and multicasting groups. Data is disseminated by way of the mapping to subscribers to one or more of the data flows. The flow rate thresholds of satisfied flows are decreased to minimize the difference between the flow rate thresholds and respective target transmission rates of the satisfied flows, as the system&#39;s feasible data transmission workload is maintained with respect to subscriber reception rate capacities. The flow rate thresholds of unsatisfied flows are increased to minimize the difference between the flow rate threshold and respective target transmission rates for the unsatisfied flows and to limit occurrences of data transmission delays or losses, as the system&#39;s feasible data transmission workload is maintained with respect to subscriber reception rate capacities.

Description:
BACKGROUND 
       [0001]    The disclosed subject matter relates generally to optimizing data dissemination in a communication environment, and, more particularly, to a system and method for dynamically controlling the data dissemination flow rates and mappings in a multicasting system. 
         [0002]    Multicasting environments provide means to disseminate content related to a great variety of topics to multitudes of subscribers. The content of each topic is delivered over an information flow, where each flow is associated with one or more multicast groups. Multicast groups may be deployed over systems with finite resources. Thus, the number of flows may be considerably larger than the number of groups with multiple flows transmitted over a single group. To manage the relationships between flows and groups, a mapping scheme is used. 
         [0003]    Referring to  FIG. 1 , as an example, flows F 1 , F 2 , . . . , FK are mapped to multicast groups G 1 , G 2 , . . . , GM in order to be transmitted to multiple users U 1 , U 2 , . . . , UN, according to the users&#39; interest and subscriptions to different flows. In a large-scale multicast system, the rate of flows will likely vary during deployment. Since each user has a limited reception rate capacity, the rate of each flow may be adjusted and controlled so that users&#39; capacity constraints are not violated both during a fixed mapping of flows to groups and following a change in flow to group mapping. 
         [0004]    Setting the rate limits of different flows typically depends on dynamic factors such as the current mapping, users&#39; reception rate capacities, flow priorities and flow rate profiles. Some of these factors are affected by remapping which occurs for example due to change in interests and change of flows rates. Since a multicast system continually evolves due to changes in user subscription and system resources, the flow mappings and flow rates continuously require adjustment. As the adjustments take place, it is important for the system to remain optimized. 
       BRIEF SUMMARY 
       [0005]    For purposes of summarizing, certain aspects, advantages, and novel features have been described herein. It is to be understood that not all such advantages may be achieved in accordance with any one particular embodiment. Thus, the disclosed subject matter may be embodied or carried out in a manner that achieves or optimizes one advantage or group of advantages without achieving all advantages as may be taught or suggested herein. 
         [0006]    Embodiments of the present invention disclose a method, computer program product, and system for enhancing performance in a multicasting system. Flow rates in a multicasting system are monitored as system characteristics change over time, wherein the multicasting system is operated based on a first mapping between a plurality of data flows and multicasting groups, wherein data is disseminated by way of the mapping to subscribers to one or more of the data flows. The flow rate thresholds of satisfied flows are decreased so as to minimize the difference between the flow rate thresholds and respective target transmission rates of the satisfied flows, as the system&#39;s feasible data transmission workload is maintained with respect to subscriber reception rate capacities. The flow rate thresholds of unsatisfied flows are increased so as to minimize the difference between the flow rate threshold and respective target transmission rates for the unsatisfied flows and to limit occurrences of data transmission delays or losses, as the system&#39;s feasible data transmission workload is maintained with respect to subscriber reception rate capacities. 
         [0007]    One or more of the above-disclosed embodiments in addition to certain alternatives are provided in further detail below with reference to the attached figures. The disclosed subject matter is not, however, limited to any particular embodiment disclosed. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0008]    The disclosed embodiments may be better understood by referring to the figures in the attached drawings, as provided below. 
           [0009]      FIG. 1  illustrates an exemplary multicasting environment in accordance with one or more embodiments, wherein a plurality of topic flows are mapped to a plurality of groups and subscribers. 
           [0010]      FIG. 2  is a flow diagram of a flow control unit, in accordance with one embodiment. 
           [0011]      FIG. 3  is an exemplary flow chart of a phase of an optimization process in a multicasting environment, in accordance with one embodiment. 
           [0012]      FIG. 4  is an exemplary flow chart of another phase of an optimization process in a multicasting environment, in accordance with one embodiment. 
           [0013]      FIGS. 5 and 6  illustrate a block diagram for a dynamic run of the different phases of the optimization process shown in  FIGS. 3 and 4 , in accordance with one embodiment. 
           [0014]      FIGS. 7A and 7B  are block diagrams of hardware and software environments in which the disclosed systems and methods may operate, in accordance with one or more embodiments. 
       
    
    
       [0015]    Features, elements, and aspects that are referenced by the same numerals in different figures represent the same, equivalent, or similar features, elements, or aspects, in accordance with one or more embodiments. 
       DETAILED DESCRIPTION 
       [0016]    In the following, numerous specific details are set forth to provide a thorough description of various embodiments. Certain embodiments may be practiced without these specific details or with some variations in detail. In some instances, certain features are described in less detail so as not to obscure other aspects. The level of detail associated with each of the elements or features should not be construed to qualify the novelty or importance of one feature over the others. 
         [0017]    Referring to  FIG. 1 , in a multicasting environment, the flow rate refers to the average rate of the flow (e.g., F 1 ) over a course of time. As such, a higher flow rate indicates that more content is being delivered per unit of time and that more bandwidth is being used by the flow. Referring to  FIG. 2 , flow rate control may be achieved by way of a monitoring mechanism (e.g., a flow control unit  200 ) that, for a flow, provides the rate of the outgoing traffic based on certain factors including the incoming traffic sustained rate, and burst size. 
         [0018]    Depending on implementation, the flow control unit  200  may monitor, limit and adjust the rate at which data is published for each flow in the system, such that a feasible workload is maintained for the system. Flow control unit  200  may be configured to calculate the average rate of the flow as well as the rate variance based on the history of the flow behavior as recorded by the flow&#39;s publisher, for example. A target rate for a flow may thus be calculated based on the average rate of the flow plus a variability margin deduced from its rate variance. Flow control unit  200  may also control and set the rate limit at which data may be published for each flow, such that the multicast system maintains a feasible workload. 
         [0019]    Feasibility in a multicast system refers to the ability to maintain a dissemination workload, where reception capacity constraints for the subscribers are not violated and a subscriber receives a flow without substantial delay or loss. To avoid delay or loss, traffic statistics may be collected to determine whether sufficient bandwidth is allocated to a flow. Flows with peak rates higher than their maximum allowed rate (i.e., threshold flow rate) are identified by, for example, the flow control unit  200  tracking the length of the respective transmission buffering queues. If the corresponding queues are substantially long, flow rate or bandwidth adjustment may be needed. 
         [0020]    If the bandwidth allocated to a flow is sufficient to allow the data to be transmitted to the targeted multicasting groups (and ultimately the subscribers) without any substantial delay or data loss, then the flow is deemed to be satisfied. If the data transmission is delayed or data loss occurs as the result of extensive buffering (i.e., because sufficient transmission bandwidth is not available or allocated to a flow), then the flow is deemed unsatisfied. Certain flows that require rates lower than their flow rate threshold, but experience some buffering may be referred to as semi satisfied and ordered according to the length of their buffered data, for example. 
         [0021]    During a multicasting operation, each flow in the system may be monitored and designated as having a threshold flow rate that indicates the maximum allowed transmission rate for that flow depending on system constraints and users&#39; reception rate capacities. The maximum allowed transmission rate or threshold flow rate thus refer to the upper rate limit for a flow. In the following a mapping solution is provided that helps find a mapping that is feasible for the multicast system workload with respect to the flows rate thresholds taking into account to the subscribers&#39; reception rate capacities. 
         [0022]    In accordance with one implementation, to avoid data loss or unacceptable levels of delay in multicasting, a resource reallocation process and, where needed, threshold flow rate adjustment and/or a flow remapping approach may be implemented, as provided in further detail below. In one aspect, optionally, no remapping of the multicasting groups is performed, unless the resource reallocation approach or threshold flow rate adjustment do not sufficiently ameliorate the respective flow rate deficiencies in the multicasting system. 
         [0023]    Referring to  FIGS. 2 and 3 , in one embodiment, a flow control unit  200  may be utilized to monitor the flow rates for different flows in a multicasting system (S 310 ). For satisfied flows that are determined to have a lower flow rate (e.g.., based on historic or empirical data analysis) than the threshold flow rate previously assigned to them, attempts may be made to decrease their respective threshold flow rates (S 320 ). Decreasing the threshold flow rate for the satisfied flows may help provide additional transmission bandwidth in the system as a whole, because effectively the previously assigned bandwidth that was not being fully utilized will become available for use by other flows. 
         [0024]    If the above-noted decrease in the assigned threshold flow rate for the satisfied flows provides additional bandwidth in the system, or regardless if additional bandwidth is available in the system, in one embodiment, attempts may be made to increase the threshold flow rate assigned to unsatisfied (or semi satisfied) flows (S 330 ), if it is determined that there is no collateral violation of the other constraints in the multicasting system. As such, unsatisfied or semi-satisfied flows would benefit from a higher flow rate than what has been previously assigned to or allowed for such unsatisfied flows. 
         [0025]    Constraints that may be inadvertently affected, as a result of increasing the threshold flow rate for one or more unsatisfied flows, relate to the reception rate constraints for the subscribers to a flow. The threshold flow rate increase may, for example, overwhelm a subscriber to a point that the subscriber is unable to process the increased level of data flow directed to a multicast group to which it subscribes. The inability to process the increased data flow level may be due to the subscriber&#39;s limited capacity to buffer and filter unwanted flows provided via the multicast group. If a subscriber is unable to process the increased data flow properly, then a constraint violation is deemed to have occurred. 
         [0026]    Depending on implementation, the flow rate adjustments (i.e., either the increase or the decrease in the flow rate threshold) may be performed gradually by way incremental increases or decreases in the corresponding flow rates. At each increment, the effects of the adjustment on the subscribers and multicast groups may be evaluated or re-evaluated, until optimization is achieved.  FIG. 3  does not illustrate incremental adjustments. However, in one embodiment, if unsatisfied flows remain, the system may revert back to S 320  or S 330  until no further adjustments are possible, or it is determined that additional adjustments are not beneficial any further or result in violation of system constraints. 
         [0027]    In certain embodiments, if the flow rate adjustments in the first phase illustrated in  FIG. 3  do not adequately resolve the transmission loss or delay (i.e., if unsatisfied flows remain (S 340 )), then a second approach may be considered. Referring to  FIG. 4 , in a second phase, a proposed mapping (i.e., a “virtual remapping”) of the groups in the multicast environment is contemplated (S 410 ). The virtual remapping is calculated prior to enforcing the proposed mapping to target multicasting groups such that the effects of a newly calculated remapping may be virtually determined, prior to committing the new mapping. 
         [0028]    If the virtual remapping results indicate that a new mapping may lead to the increase of threshold flow rate for some flows (S 420 ) without violating subscriber&#39;s reception rate constraints, then it is determined whether further virtual remapping is needed to satisfy the needs of some remaining unsatisfied flows (S 430 ). If so, another virtual remapping may be calculated (S 410 ), and the virtual remapping process may continue until one or more flows are deemed satisfied, or until it is determined that additional virtual remapping will have no further positive effect on the remaining unsatisfied flows. 
         [0029]    Thereafter, the virtual remapping results may be analyzed to determine how to best transition the multicasting system into one or more calculated virtual mappings in one or more steps, and desirably in a minimum number of steps (S 440 ). The transition may thus be performed in one or more steps, with each step being analyzed to determine if any system constraints are violated. Remaps may be performed sequentially, according to the order of calculation resulting in the updating of threshold flow rates for one or more flows according to the calculated virtual mappings (S 450 ). 
         [0030]    It is noteworthy that, in one embodiment, the rates are increased virtually at each virtual mapping and thus the actual rate increases are performed after the last virtual mapping is computed and the transition to the last virtual mapping is performed. The transition to the last virtual mapping is the real transition taking place at the end of the process, as until that time the calculated re-mappings are virtual in nature and were not actually performed Note that, depending on implementation, before the transition, the rate increases are not supported by the current mapping in the event of occurrence of violations. 
         [0031]    It is further noteworthy that the move from a current mapping to a final virtual mapping may not simply take place in a single transition, since it is not clear what would happen during each individual transition (i.e., when violations could occur). However, a sequential or incremental transition based on the calculated virtual mappings would be feasible (as transition was taken into account during calculations). Thus, in one embodiment, it is desirable to find the minimum sequence of transitions that are needed for a proper transitioning to the final virtual mapping. 
         [0032]    It is noteworthy that in the second phase, if none of the contemplated virtual maps allow for more rate increases without violating systems constraints, then it may be determined that it is not worthwhile to perform the re-mapping and further processing under the second phase may be aborted. It is further noteworthy that the application of the methods and processes, disclosed in the first and second phases, may be in a different order than that disclosed herein. For example, referring to  FIGS. 5 and 6 , the process disclosed in the first phase may be applied to data flows that are deemed unsatisfied, and then the same or similar process may be applied to data flows that are deemed semi satisfied. 
         [0033]    In the above disclosure, an exemplary optimization scheme in accordance with one or more embodiments is provided. In one exemplary embodiment, a multicasting model and a remapping algorithm in addition to one or more methods for calculating the associated costs may be implemented. It is noteworthy that the detailed features disclosed are by way of example and should not be construed as limiting the scope of the claimed subject matter to the particular details. Such details are provided to help better understand the underlying features and elements. 
         [0034]    References in this specification to “an embodiment”, “one embodiment”, “one or more embodiments” or the like, mean that the particular element, feature, structure or characteristic being described is included in at least one embodiment of the disclosed subject matter. Occurrences of such phrases in this specification should not be particularly construed as referring to the same embodiment, nor should such phrases be interpreted as referring to embodiments that are mutually exclusive with respect to the discussed features or elements. 
         [0035]    In different embodiments, the claimed subject matter may be implemented as a combination of both hardware and software elements, or alternatively either entirely in the form of hardware or entirely in the form of software. Further, computing systems and program software disclosed herein may comprise a controlled computing environment that may be presented in terms of hardware components or logic code executed to perform methods and processes that achieve the results contemplated herein. Said methods and processes, when performed by a general purpose computing system or machine, convert the general purpose machine to a specific purpose machine. 
         [0036]    Referring to  FIGS. 7A and 7B , a computing system environment in accordance with an exemplary embodiment may be composed of a hardware environment  1110  and a software environment  1120 . The hardware environment  1110  may comprise logic units, circuits or other machinery and equipments that provide an execution environment for the components of software environment  1120 . In turn, the software environment  1120  may provide the execution instructions, including the underlying operational settings and configurations, for the various components of hardware environment  1110 . 
         [0037]    Referring to  FIG. 7A , the application software and logic code disclosed herein may be implemented in the form of machine readable code executed over one or more computing systems represented by the exemplary hardware environment  1110 . As illustrated, hardware environment  110  may comprise a processor  1101  coupled to one or more storage elements by way of a system bus  1100 . The storage elements, for example, may comprise local memory  1102 , storage media  1106 , cache memory  1104  or other machine-usable or computer readable media. Within the context of this disclosure, a machine usable or computer readable storage medium may include any recordable article that may be utilized to contain, store, communicate, propagate or transport program code. 
         [0038]    A computer readable storage medium may be an electronic, magnetic, optical, electromagnetic, infrared, or semiconductor medium, system, apparatus or device. The computer readable storage medium may also be implemented in a propagation medium, without limitation, to the extent that such implementation is deemed statutory subject matter. Examples of a computer readable storage medium may include a semiconductor or solid-state memory, magnetic tape, a removable computer diskette, a random access memory (RAM), a read-only memory (ROM), a rigid magnetic disk, an optical disk, or a carrier wave, where appropriate. Current examples of optical disks include compact disk, read only memory (CD-ROM), compact disk read/write (CD-R/W), digital video disk (DVD), high definition video disk (HD-DVD) or Blue-ray™ disk. 
         [0039]    In one embodiment, processor  1101  loads executable code from storage media  1106  to local memory  1102 . Cache memory  1104  optimizes processing time by providing temporary storage that helps reduce the number of times code is loaded for execution. One or more user interface devices  1105  (e.g., keyboard, pointing device, etc.) and a display screen  1107  may be coupled to the other elements in the hardware environment  1110  either directly or through an intervening I/O controller  1103 , for example. A communication interface unit  1108 , such as a network adapter, may be provided to enable the hardware environment  1110  to communicate with local or remotely located computing systems, printers and storage devices via intervening private or public networks (e.g., the Internet). Wired or wireless modems and Ethernet cards are a few of the exemplary types of network adapters. 
         [0040]    It is noteworthy that hardware environment  1110 , in certain implementations, may not include some or all the above components, or may comprise additional components to provide supplemental functionality or utility. Depending on the contemplated use and configuration, hardware environment  1110  may be a machine such as a desktop or a laptop computer, or other computing device optionally embodied in an embedded system such as a set-top box, a personal digital assistant (PDA), a personal media player, a mobile communication unit (e.g., a wireless phone), or other similar hardware platforms that have information processing or data storage capabilities. 
         [0041]    In some embodiments, communication interface  1108  acts as a data communication port to provide means of communication with one or more computing systems by sending and receiving digital, electrical, electromagnetic or optical signals that carry analog or digital data streams representing various types of information, including program code. The communication may be established by way of a local or a remote network, or alternatively by way of transmission over the air or other medium, including without limitation propagation over a carrier wave. 
         [0042]    As provided here, the disclosed software elements that are executed on the illustrated hardware elements are defined according to logical or functional relationships that are exemplary in nature. It should be noted, however, that the respective methods that are implemented by way of said exemplary software elements may be also encoded in said hardware elements by way of configured and programmed processors, application specific integrated circuits (ASICs), field programmable gate arrays (FPGAs) and digital signal processors (DSPs), for example. 
         [0043]    Referring to  FIG. 7B , software environment  1120  may be generally divided into two classes comprising system software  1121  and application software  1122  as executed on one or more hardware environments  1110 . In one embodiment, the methods and processes disclosed here may be implemented as system software  1121 , application software  1122 , or a combination thereof. System software  1121  may comprise control programs, such as an operating system (OS) or an information management system, that instruct one or more processors  1101  (e.g., microcontrollers) in the hardware environment  1110  on how to function and process information. Application software  1122  may comprise but is not limited to program code, data structures, firmware, resident software, microcode or any other form of information or routine that may be read, analyzed or executed by a processor  1101 . 
         [0044]    In other words, application software  1122  may be implemented as program code embedded in a computer program product in form of a machine-usable or computer readable storage medium that provides program code for use by, or in connection with, a machine, a computer or any instruction execution system. Moreover, application software  1122  may comprise one or more computer programs that are executed on top of system software  1121  after being loaded from storage media  1106  into local memory  1102 . In a client-server architecture, application software  1122  may comprise client software and server software. For example, in one embodiment, client software may be executed on a client computing system that is distinct and separable from a server computing system on which server software is executed. 
         [0045]    Software environment  1120  may also comprise browser software  1126  for accessing data available over local or remote computing networks. Further, software environment  1120  may comprise a user interface  1124  (e.g., a graphical user interface (GUI)) for receiving user commands and data. It is worthy to repeat that the hardware and software architectures and environments described above are for purposes of example. As such, one or more embodiments may be implemented over any type of system architecture, functional or logical platform or processing environment. 
         [0046]    It should also be understood that the logic code, programs, modules, processes, methods and the order in which the respective processes of each method are performed are purely exemplary. Depending on implementation, the processes or any underlying sub-processes and methods may be performed in any order or concurrently, unless indicated otherwise in the present disclosure. Further, unless stated otherwise with specificity, the definition of logic code within the context of this disclosure is not related or limited to any particular programming language, and may comprise one or more modules that may be executed on one or more processors in distributed, non-distributed, single or multiprocessing environments. 
         [0047]    As will be appreciated by one skilled in the art, a software embodiment may include firmware, resident software, micro-code, etc. Certain components including software or hardware or combining software and hardware aspects may generally be referred to herein as a “circuit,” “module” or “system.” Furthermore, the subject matter disclosed may be implemented as a computer program product embodied in one or more computer readable storage medium(s) having computer readable program code embodied thereon. Any combination of one or more computer readable storage medium(s) may be utilized. The computer readable storage medium may be a computer readable signal medium or a computer readable storage medium. A computer readable storage medium may be, for example, but not limited to, an electronic, magnetic, optical, electromagnetic, infrared, or semiconductor system, apparatus, or device, or any suitable combination of the foregoing. 
         [0048]    In the context of this document, a computer readable storage medium may be any tangible medium that can contain, or store a program for use by or in connection with an instruction execution system, apparatus, or device. A computer readable signal medium may include a propagated data signal with computer readable program code embodied therein, for example, in baseband or as part of a carrier wave. Such a propagated signal may take any of a variety of forms, including, but not limited to, electro-magnetic, optical, or any suitable combination thereof. A computer readable signal medium may be any computer readable medium that is not a computer readable storage medium and that can communicate, propagate, or transport a program for use by or in connection with an instruction execution system, apparatus, or device. 
         [0049]    Program code embodied on a computer readable storage medium may be transmitted using any appropriate medium, including but not limited to wireless, wireline, optical fiber cable, RF, etc., or any suitable combination of the foregoing. Computer program code for carrying out the disclosed operations may be written in any combination of one or more programming languages, including an object oriented programming language such as Java, Smalltalk, C++ or the like and conventional procedural programming languages, such as the “C” programming language or similar programming languages. 
         [0050]    The program code may execute entirely on the user&#39;s computer, partly on the user&#39;s computer, as a stand-alone software package, partly on the user&#39;s computer and partly on a remote computer or entirely on the remote computer or server. In the latter scenario, the remote computer may be connected to the user&#39;s computer through any type of network, including a local area network (LAN) or a wide area network (WAN), or the connection may be made to an external computer (for example, through the Internet using an Internet Service Provider). 
         [0051]    Certain embodiments are disclosed with reference to flowchart illustrations or block diagrams of methods, apparatus (systems) and computer program products according to embodiments. It will be understood that each block of the flowchart illustrations or block diagrams, and combinations of blocks in the flowchart illustrations and/or block diagrams, can be implemented by computer program instructions. These computer program instructions may be provided to a processor of a general purpose computer, a special purpose machinery, or other programmable data processing apparatus to produce a machine, such that the instructions, which execute via the processor of the computer or other programmable data processing apparatus, create means for implementing the functions or acts specified in the flowchart or block diagram block or blocks. 
         [0052]    These computer program instructions may also be stored in a computer readable storage medium that can direct a computer, other programmable data processing apparatus, or other devices to function in a particular manner, such that the instructions stored in the computer readable storage medium produce an article of manufacture including instructions which implement the function or act specified in the flowchart or block diagram block or blocks. 
         [0053]    The computer program instructions may also be loaded onto a computer, other programmable data processing apparatus, or other devices to cause a series of operational steps to be performed on the computer, other programmable apparatus or other devices to produce a computer or machine implemented process such that the instructions which execute on the computer or other programmable apparatus provide processes for implementing the functions or acts specified in the flowchart or block diagram block or blocks. 
         [0054]    The flowchart and block diagrams in the figures illustrate the architecture, functionality, and operation of possible implementations of systems, methods and computer program products according to various embodiments. In this regard, each block in the flowchart or block diagrams may represent a module, segment, or portion of code, which comprises one or more executable instructions for implementing the specified logical functions. It should also be noted that, in some alternative implementations, the functions noted in the block may occur in any order or out of the order noted in the figures. 
         [0055]    For example, two blocks shown in succession may, in fact, be executed substantially concurrently, or the blocks may sometimes be executed in the reverse order, depending upon the functionality involved. It will also be noted that each block of the block diagrams or flowchart illustration, and combinations of blocks in the block diagrams or flowchart illustration, may be implemented by special purpose hardware-based systems that perform the specified functions or acts, or combinations of special purpose hardware and computer instructions. 
         [0056]    The claimed subject matter has been provided here with reference to one or more features or embodiments. Those skilled in the art will recognize and appreciate that, despite of the detailed nature of the exemplary embodiments provided here, changes and modifications may be applied to said embodiments without limiting or departing from the generally intended scope. These and various other adaptations and combinations of the embodiments provided here are within the scope of the disclosed subject matter as defined by the claims and their full set of equivalents.