Abstract:
Ad segments on a Web page are filled with ads that are served by a service provider operating between a user computer and publisher on one end and multiple ad serving entities on the other. The service provider implements a bidding process for the ad segment. Impression caps may be imposed over geographically separate data centers. An individual server in a data center may dynamically request information from a central store to update a local impression cap quota.

Description:
TECHNICAL FIELD OF THE INVENTION 
       [0001]    The present invention relates generally to computer software and Internet advertising. More specifically, the invention relates to software for serving advertisements over the Internet for display on Web sites. 
       BACKGROUND OF THE INVENTION 
       [0002]    The online advertising industry is growing increasingly sophisticated. As the number of display ads grows, driven mainly by more intelligent programmatic ad buying capabilities, the amount of control that publishers (entities who have an inventory of advertising space to sell) want with respect to selling this ad space inventory grew. And with it the value of the publisher&#39;s inventory rose as well. There is an increasing desire among publishers to carve out specific inventory buckets for their ad space inventory. On the advertiser side, advertisers are now increasingly particular about how much they will pay to place their ads on Web pages. Presently, prices for paying for ad space is based on fairly generic level controls, such as Web site traffic, location on Web page, visibility on page, and the like. The specific audience, that is, who would see the ad, does not play a role in determining the value of an ad space or segment. 
         [0003]    Referring to  FIG. 1 , an online advertising system may include an ad server that acts as an intermediary between publishers and advertisers. This may include providing real time bidding for ad segments served to individual users viewing web pages of publishers. 
         [0004]    One aspect of the online advertising industry is that ads may be served to users across large geographic areas. For example, an individual publisher may have a website that is viewed by people within large geographic areas, including different countries around the world. As a result, the online ads will typically be served from geographically distributed servers. Thus, in the example of  FIG. 1 , local servers (not shown) would be provided in individual geographic regions to provide acceptable response times to consumers. 
         [0005]    Providing a geographically distributed online advertising service generates a problem in controlling the number of impressions served. In many applications it is desirable to have a cap on the number of impressions for a particular campaign, creative, real time bidding, or ad network. This is also known as an impression cap. However, coordinating impression caps in a distributed online advertising environment is difficult. 
         [0006]    Therefore, it would be desirable to provide tools for improved control of serving impressions in an online advertising campaign. 
       SUMMARY OF THE INVENTION 
       [0007]    In one aspect of the preset invention, a method of serving ads to ad segments on Web pages is described. Impression caps may be imposed on geographically distributed data centers. In an individual data center a server may dynamically request information to update a local impression cap at the server. The rules for determining an impression cap for a server may include selecting the impression cap to be a small fraction of a total impression cap for a data center to minimize under/over serving. Additionally, the impression cap may be selected to be sufficiently large to keep latency within acceptable limits. Additionally, other rules may be imposed on the impression cap at the local server. After a server exhausts an impression cap quota it dynamically requests information from a central store to update its impression cap quota. Additional monitoring of actual impressions served may be used to aid in determining the number of remaining impressions to be served by the servers of a data center. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0008]    The invention and the advantages thereof may best be understood by reference to the following description taken in conjunction with the accompanying drawings in which: 
           [0009]      FIG. 1  is a block diagram showing the entities and relationships for controlling advertising in accordance with the prior art; 
           [0010]      FIG. 2  is a block diagram illustrating geographically distributed impression capping in accordance with an embodiment of the present invention; 
           [0011]      FIG. 3  illustrates impression capping at a data center in accordance with an embodiment of the present invention; and 
           [0012]      FIGS. 4A and 4B  are flow charts illustrating embodiments of methods of the present invention. 
       
    
    
       [0013]    In the drawings, like reference numerals are sometimes used to designate like structural elements. It should also be appreciated that the depictions in the figures are diagrammatic and not to scale. 
       DETAILED DESCRIPTION OF THE INVENTION 
       [0014]    Methods, systems, and computer readable media for impression capping in an online advertising distributed environment are described.  FIG. 2  is a high level block diagram of an embodiment of the present invention. In one embodiment impression caps are distributed at the data center level. The distributed system has multiple data centers  205  in different geographic areas (e.g., different time zones as one example). Each data center  205  has one or more data clusters where an individual cluster includes a group of servers. An individual cluster may serve a single type of inventory or multiple types of inventory. Examples of inventory include ad segments for mobile devices, web, video, or combinations. An impression cap may have daily, hour, lifetime, and geographic level limits. The effective Cost Per Mil (e-CPM) may also vary. As an illustrative example, assume two inventories, inventory ‘a’ and inventory ‘b’. Inventory ‘a’ has an e-CPM of $2 and inventory ‘b’ has an e-CPM of $1. A total targeted impressions may be 150,000 with 100,000 impressions from inventory a and 50,000 impressions from inventory ‘b’. Additional administration  210  may be provided to provide an impression cap for all of the data centers. 
         [0015]      FIG. 3  illustrates in more detail an individual data center  300  with two or more ad servers  305  to serve impressions to the browser  390  of client computers within a geographical region. Each individual server  305  fetches an impression cap (icap) quota from a central icap store  340 . Each server  305  serves impressions to web browsers and this information on served impression is recorded in a database  350 . A chronological (cron) analysis module  360  is a unit that analyzes the served impression details. This chronological information is used to determine what the remaining portion of the icap at the central icap store  340  is and this information may be used to refine impression cap updates given to individual servers  305 . An individual server  305  may include a rules module  307  to define the rules for the icap quota updates. In one embodiment the cron analysis module  360  gets the impression served details and determines the impressions to be served and set in the central icap store  340 . When an ad-server  307  gets an icap quota from the central icap store  340 , the icap quota is deducted from the central icap count. 
         [0016]    In one embodiment a get impression served details  355  command is used for the cron analysis modules  360  to fetch information on impressions served. The central icap store  340  may use a get details and set icap command  365  to get the chronological information, which may include information on the number of impressions to be served and the impressions actually served. 
         [0017]    Each individual server  305  of the data center  300  fetches an icap quota from the central icap store  340  keeps the fetched quota locally at the server. Once that icap quota has been exhausted at the individual server, the server will then fetch an updated icap quota from the central icap store and continue to serve impressions. The process of each server fetching an updated icap quota each time a previous icap quota is exhausted continues until the remaining icap quota in the central icap store  340  is exhausted. 
         [0018]      FIG. 4A  illustrates an exemplary method in accordance with an embodiment of the present invention. An impression cap is distributed to each data center in block  405 . In an individual data center, there is monitoring of chronological data on impressions served and determining of remaining impression cap for a central store in block  410 . Each individual server of the data center dynamically requests in block  415  an impression cap quota update from the central store after it has exhausted its previous impression cap. 
         [0019]      FIG. 4B  illustrates an exemplary method for a server to dynamically request updates. An individual server begins with a default icap quota in block  420 . This default could, for example, be a small starting quota, such as 1 impression. This initial default icap quota is exhausted after the corresponding number of impressions is served. The server then dynamically acquires and updates the icap quota from the central store in block  425 . This updated icap quota may be a fixed number. However, more generally it may be adjusted based on the remaining icap at the central store. For example, one or more rules may be applied as the remaining icap decreases to reduce the icap quota. The individual server may then exhaust the updated icap quota and request a new (next) icap quota from the central store in block  430 . 
         [0020]    As an illustrative example, assume that there is an impression cap (icap) of 100,000 for a given data center. Suppose there are servers A, B, and C of different clusters. Suppose server A fetches an icap quota of 100 and keeps it at the server locally. 
         [0021]    Once the 100 impressions are served by that server, it will again fetch an updated quota (e.g., 100) from the central store. Several different aspects are illustrated by this example. In this example the impression cap quota is small compared with the total icap for the data center. Thus, there is a low chance of over-serving or under-serving. However, the icap quota is also large enough so that the icap quota is not always updated from the central store. That is, the icap quota is selected to be large enough to keep latency within acceptable limits. Additionally, the use of the central store eliminates the need to maintain cluster information to control the impression cap. Moreover, because the data center is monitoring the actual impressions served, the remaining inventory can be determined and used to refine the icap quota updates based on the remaining inventory. 
       Exemplary Server Algorithm 
       [0022]    As previously discussed an individual server  305  may include a rules module  307  to update the icap quota. An exemplary server algorithm to update the icap quota will now be described in accordance with an embodiment of the present invention. In one embodiment, on each server call request, the following steps are implemented by the server: 
         [0023]    1. Get related winnable inventory having impression cap enabled. 
         [0024]    2. If icap data is not available locally for an inventory take a default icap, where an exemplary default icap may be set to be a small number such as 1. Setting the default icap to be a small value avoids a first time huge update request to the central data store. Moreover, setting the default icap to be a small number, such as 1, can be accommodated while an estimation is performed at the centralized data store of the remaining icap for the data center. 
         [0025]    3. Determine if the icap data is available locally but &lt;=0, and if the icap is available at the central store. For this case, fetch icap quota as per icap available at central store, decrement same at central store and store it locally for further use. 
         [0026]    4. If the inventory having icap wins, then decrement the icap count for the same inventory by 1 locally, then again go through step 3 to update icap if required. 
         [0027]    In one embodiment a rule is provided for the local Icap data to expire based on a condition, such after a pre-selected time or other condition. 
         [0028]    As an illustrative example suppose for an ad request that c1, c2, c3, c4 are different types of active inventory each having icap enabled. Then in one embodiment the following steps will be followed by the server: 
         [0029]    1. The server checks the icap value locally for the different types of inventory c1, c2, c3, c4. In this example, for a first time call the icap data will not be available locally so the server will take the default icap (e.g., a small value, such as 1) and will do further processing. 
         [0030]    2. Now suppose that the inventory c2 is finally owned and served. The icap count is then decremented locally by 1. In this example, the default icap is assumed to also be 1. As the icap count is now &lt;=0, an updated icap quota (e.g., say 100) will be fetched from central store and set locally for further use. 
         [0031]    3. Thus, after step 2 we have icap for c1=1, c2=100, c3=1, c4=1. 
         [0032]    4. The Server again get a call and one of the inventories c1, c2, c3, and c4 is selected. 
         [0033]    5. Whichever campaign wins will decrement the icap locally by 1. 
       Dynamic Quota Mechanism 
       [0034]    In one embodiment the icap quota fetched by server will be dynamic and will be decided as per the remaining icap at central store. Initially the server will be unaware of the icap at the central store so it will fetch a minimal quota at first. Once it knows the icap at the central store it will decide its quota accordingly as below: 
         [0035]    An icap_quota_factor is one of the deciding factors to calculate a dynamic quota. In one implementation a default value for the icap_quota_factor is 5. 
         [0036]    An icap_minimum_quota is a minimum icap quota. 
         [0037]    An icap_max_quota is a maximum icap quota. 
         [0038]    A factor value is based on the data center server count and the icap quota server as follows: 
         [0039]    factor=dc_server_count*icap_quota_factor 
         [0040]    Then using these expressing the updated (next) icap quota is given by the following expression to adjust the next icap quota based on the remaining icap at the central store, the icap minimum quota, and the factor value: 
         [0041]    next_quota=icap_minimum_quota 
         [0042]    if(remaing_icap_at_central_store&gt;icap_minimum_quota*factor){ 
         [0043]    next_quota=remaing_icap_at_central store/factor; 
         [0044]    if(icap_max_quota&lt;next_quota){ 
         [0045]    next_quota=icap_max_quota; 
         [0046]    } 
         [0047]    } 
       Icap Estimation Algorithm 
       [0048]    In one embodiment, and estimate is formed for the icap at some initial time period for the central store, such as at the beginning of the day (the 0th hour with respect to the beginning of a new time period). This estimate may be weighted based on how many impressions were served in the previous time period by the data server. However, if no impressions were served in the previous time period by the data center, then the estimate can be based on the percentage of servers in the data center, or by other techniques. A default number can also be set to each server. 
         [0049]    For example, in one embodiment each day the chron analysis module  360  will run in each data center. This provides the number of impressions served by the data center in the previous time period. This is performed to decide the maximum number of impressions to be served for the day, which is updated in the central store. This update is performed for all active inventories. 
         [0050]    In one implementation, the update will depend on the total number of impressions to be served today multiplied by the percentage of impressions served yesterday by the data center then the following algorithm may be used: 
         [0051]    Impression_to_be_served_by_dc=total_impression_to_serve_today*% of impression_served_yesterday_by_dc 
         [0052]    However, suppose that in the previous time period that no impressions were served by that data center. In this situation a different algorithm may be used: 
         [0053]    If impression_served_yesterday_by_dc is zero for a DC then 
         [0054]    Impression_to_be_served_by_dc=total_impression_to_serve_today*% of server in that DC. 
         [0055]    By default, an icap of 1 is given to all server this is accommodated in estimation by below step: 
         [0056]    Impression_to_be_served_by_dc=Impression_to_be_served_by_dc-total_server_in_dc 
         [0057]    Impression_to_be_served_by_dc will be set in central store. 
       Estimate and Serve Undelivered Impression 
       [0058]    As previously discussed, in one embodiment the cron analysis module  360  monitors the impressions that are actually served on a user browser. An impression is counted served only if it is served on a user&#39;s browser. This improves accuracy. For example suppose that an auction happens at the publisher end. Suppose some of the impressions are lost. This may arise from problems in the network through which the impression is served to the end user or for other technical reasons. In this situation, the lost impressions need to be re-delivered. 
         [0059]    A redelivery algorithm may be implemented on a period basis. In one implementation an algorithm to redeliver lost impressions is followed every 15 minutes, although it will be understood that the algorithm could be repeated with other periodicities. An exemplary redelivery algorithm is as follows: 
         [0060]    a. Find out all active inventories whose icap is finished at central store in a DC. 
         [0061]    b. If the icap is finished 15 min before current time at central store for given DC then: 
         [0062]    Remaining_Impression_to_serve_by_DC=total_impression_to_serve_today_by_DC-impression_already_served 
         [0063]    If Remaining_Impression_to_serve_by_DC&gt;lowest_quota*machine_count_in_dc 
         [0064]    Remaining_Impression_to_serve_by_DC=Remaining_Impression_to_serve_by_DC-(lowest_quota*machine_count_in_dc) 
         [0065]    else if Remaining_Impression_to_serve_by_DC&lt;lowest_quota*machine_count_in_dc 
         [0066]    Remaining_Impression_to_serve_by_DC=0 
         [0067]    c. Set Remaining_Impression_to_serve_by_DC in central store. 
         [0068]    In addition, embodiments of the present invention further relate to computer storage products with a computer-readable medium that have computer code thereon for performing various computer-implemented operations. The media and computer code may be those specially designed and constructed for the purposes of the present invention, or they may be of the kind well known and available to those having skill in the computer software arts. Examples of computer-readable media include, but are not limited to: magnetic media such as hard disks, floppy disks, and magnetic tape; optical media such as CD-ROMs and holographic devices; magneto-optical media such as floptical disks; and hardware devices that are specially configured to store and execute program code, such as application-specific integrated circuits (ASICs), programmable logic devices (PLDs) and ROM and RAM devices. Examples of computer code include machine code, such as produced by a compiler, and files containing higher-level code that are executed by a computer using an interpreter. 
         [0069]    Although illustrative embodiments and applications of this invention are shown and described herein, many variations and modifications are possible which remain within the concept, scope, and spirit of the invention, and these variations would become clear to those of ordinary skill in the art after perusal of this application. Accordingly, the embodiments described are to be considered as illustrative and not restrictive, and the invention is not to be limited to the details given herein, but may be modified within the scope and equivalents of the appended claims.