FIELD OF INVENTION

[001] The present invention relates to cellular data traffic and more particularly to prediction of cellular data traffic by using Online Social Networking (OSN) traffic as a predictor variable.

BACKGROUND OF INVENTION

[002] Broadband cellular networks are emerging to be the most common means for mobile data access globally. The popularity of broadband cellular networks is driven by the usage of user-friendly smart phones, net books, tablets and other devices with a variety of innovative mobile applications. It is expected that the volume of data through cellular data networks will increase rapidly in the near future.

[003] Of late OSNs have been a fast growing business in the internet. As OSNs get increasingly popular, leading websites boast of an ever increasing extensive user base of subscribers. These OSNs websites drive a significant amount of traffic to the rest of the World Wide Web. The increased penetration of smart-phones and tight integration of social-sharing features into various mobile applications and services suggest that much of this socially driven data traffic originate from smart phones.

[004] As an increasing number of messages and content are being shared in OSNs, these messages are tagged with geo-location of their origin, in addition to other relevant information such as time-of-creation, sender and the recipient(s). Significantly, the OSN traffic has increased more than 250% in 2011.

[005] Obtaining certain facets of public data from various OSNs is relatively easy. The data thus obtained provides insights into the cellular data traffic patterns. One of the patterns that cellular data traffic exhibits is the spike which relates to extreme high values of data traffic. Spikes are capable of disrupting normal network operations and are hard to model and predict in general time-series data. In several cells of the network, especially in urban areas and official districts, the prominent driver of cellular data traffic is OSNs. Often in such cells, a spike in Cellular data traffic is preceded by a burst in OSN traffic These are the cells where providing a smooth service by the network operator is considered crucial.

[006] Conventional approaches try to avoid spikes by over-provisioning during network planning or modeling the time-series data with simplifying statistical assumptions. Over-provisioning is generally considered wasteful and statistical approaches to model extreme values in time-series data is hindered by factors such as low prior evidence of extreme vales and the heavy tailed nature of extreme value distribution.

[007] In light of the above mentioned reasons, it is necessary to model spikes in cellular data traffic as a function of bursts in OSN traffic and to incorporate the physical process behind data generation for modeling purposes.

SUMMARY
[008] Embodiments herein disclose a method for predicting spikes in data traffic in a cellular network, said method comprising of selecting a plurality of cells from said network which contribute to spikes in data traffic; selecting a plurality of users associated with said selected plurality of cells; modeling mobility for each of said selected plurality of users; modeling home timelines of online social networks belonging to each of said selected plurality of users; determining data traffic generated if each of said selected plurality of users click on at least link present in said home timeline; modeling clicking behaviour of said selected plurality of users; estimating data traffic at a particular time instant based on said modeled mobility, said modeled home timelines, said determined data traffic and said modeled clicking behaviour for each of said selected plurality of cells; and predicting a spike in data traffic, on said estimated data traffic being higher than a threshold.

[009] Also, disclosed herein is a system for predicting spikes in data traffic in a cellular network, said system configured for selecting a plurality of cells from said network which contribute to spikes in data traffic; selecting a plurality of users associated with said selected plurality of cells; modeling mobility for each of said selected plurality of users; modeling home timelines of online social networks belonging to each of said selected plurality of users; determining data traffic generated if each of said selected plurality of users click on at least link present in said home timeline; modeling clicking behaviour of said selected plurality of users; estimating data traffic at a particular time instant based on said modeled mobility, said modeled home timelines, said determined data traffic and said modeled clicking behaviour for each of said selected plurality of cells; and predicting a spike in data traffic, on said estimated data traffic being higher than a threshold.

BRIEF DESCRIPTION OF FIGURES

[0010] This invention is illustrated in the accompanying drawings, throughout which like reference letters indicate corresponding parts in the various figures. The embodiments herein will be better understood from the following description with reference to the drawings, in which:

[0011] FIG. 1 is a block diagram depicting the architecture of a cellular data traffic prediction system, according to embodiments as disclosed herein;

[0012] FIG. 2 is a flow diagram depicting the procedure to select the cells and users in a cellular data traffic prediction system, according to the embodiments as disclosed herein; and

[0013] FIG. 3 is a block depicting the modules involved in predicting spikes in a cellular data traffic system, according to the embodiments disclosed herein.

DETAILED DESCRIPTION OF INVENTION

[0014] The embodiments herein and the various features and advantageous details thereof are explained more fully with reference to the non-limiting embodiments that are illustrated in the accompanying drawings and detailed in the following description. Descriptions of well-known components and processing techniques are omitted so as to not unnecessarily obscure the embodiments herein. The examples used herein are intended merely to facilitate an understanding of ways in which the embodiments herein can be practiced and to further enable those of skill in the art to practice the embodiments herein. Accordingly, the examples should not be construed as limiting the scope of the embodiments herein.

[0015] The embodiments herein achieve a method and system to predict extreme values of cellular data traffic. A bootstrapping and user modeling procedure is implemented to predict the spikes.

[0016] Referring now to the drawings, and more particularly to FIGS. 1 through 3, where similar reference characters denote corresponding features consistently throughout the figures, there are shown preferred embodiments.

[0017] FIG. 1 is a block diagram depicting the architecture of a cellular data traffic prediction system, according to embodiments as disclosed herein. As depicted in FIG. 1, the cellular data prediction system is modeled based on the World Wide Web 100 which serves as a platform for the OSNs. An URL analyzer 101 is implemented to calculate factors such as page size, composition, download time, and other web page characteristics. The URL module 102 is responsible for accumulating information in an automated way about the URL in question (e.g. the content type and size)

[0018] Further, the search client module 103 searches for the information required. In an example, if a user is a subscriber of twitter, then the search client module 103 gathers tweets that assist in analysis of cellular data traffic. The user can thus follow his favorite topics or keep track of other users' comments. The stream client module 104 is also responsible for gathering tweets that assist in analysis of cellular data traffic. The search client module 103 and the stream client module 104 harvest set of users related to a region by continuously querying the corresponding OSN APIs. The stream client module 104 may support basic and advanced playback features and several other monetization features. The notification fetcher module 105 helps add latest alerts (for twitter consider tweets) to the user's post or the selected post on the OSNs or give different alerts to different posts. The profile fetcher 106 fetches users' profiles from the OSNs in order to aid the analysis of cellular data traffic.

[0019] The architecture system further comprises of a map reduce software framework module 110, distributed file system 111 and a distributed database module 112. In an embodiment an open source software framework such as Apache Hadoop may serve as the map reduce software framework module110.The map reduce software framework module 110 allows for the distributed processing of large data sets across clusters of computers and is designed to scale up offering local computation and storage. The map reduce software framework module 110 is essentially a map reduce that is typically used to do distributed computing on clusters of computers. The distributed file system 111 provides high throughput access to application data and is suitable for applications that have large data sets. In an embodiment, Hadoop Distributed File System (HDFS) may serve as the distributed file system 111.

[0020] The distributed database module 112 maintains configuration information, naming, providing distributed synchronization, and provides group services. In an embodiment, the distributed database module 112 may be a database such as a HDFS or a coordination service such as Zookeeper.

[0021] Consider a process that generates socially driven traffic. For example, when a user clicks on a link embedded inside a tweet, the social networking website twitter redirects the user to the appropriate domain serving the link. The link maybe an online shopping site, a video hosting site, an online news channel or any such kind. From considerable research, it has been indicated that social networking websites (twitter and Facebook) redirect a considerable amount of traffic to these websites. It has also been observed that in many cells in socially driven busy metropolitan areas, the socially driven cellular data traffic and the overall data traffic exhibit strong correlation.

[0022] Consider a case, how a typical twitter user would generate cellular data traffic. Initially, the user may update his/her status. The frequency of status updates is usually high, but it translates to a small volume of data due to the brief nature of updates. The user may also check his/her the messages or notifications received and click on the links present. Once the user clicks on the link, considerable data traffic may be generated. The data traffic thus generated maybe a cause such as a user clicking on a video link and watching it for three minutes or checking 40 odd photos in an album or any such kind.

[0023] On an individual level, users exhibit certain patterns in their clicks. A user may rather click on links when he/she is commuting, or during a lunch break, that is when the user is relatively free from work. On an aggregate level, many of these user patterns are preserved since the time of commutes and breaks are almost synchronized. Depending on the demographics of the cell, the group behavior may lead to profound patterns in socially driven data traffic. One of the patterns is viral propagation where the links spread over social ties. Viral propagation ensures that certain links are clicked soon after they appear in a user's notification and once the user propagate the notification further, it may lead to several clicks on the same link in short duration of time resulting in spikes.

[0024] In order to model the spikes, it is necessary to know a few variables for every user. The variables may be the content of their notifications, the clicking behavior and mobility. Clicking behavior refers to the probability of users clicking on certain links embedded in OSNs while using the internet. Mobility or mobility models represents the movement of mobile users, and how their location, velocity and acceleration change over time.

[0025] FIG. 2 is a flow diagram depicting the procedure to select the cells and users in a cellular data traffic prediction system, according to the embodiments as disclosed herein. As depicted in FIG.2, initially a bootstrap procedure is applied. The bootstrap procedure is implemented to select (201) the cells. Firstly, it is required to tessellate the region being served by a group of base stations into cells. Tessellation is the process of creating a two-dimensional plane using the repetition of a geometric shape with no overlaps and no gaps. Voronoi decomposition is chosen as the method for tessellation. These objects are usually called the sites or the generators and to each such object a corresponding Voronoi cell is associated which is namely the set of all points in the given space whose distance to the given object is not greater than their distance to the other objects.

[0026] In an embodiment all points inside a Voronoi cell are (geographically) closer to the cell's base station than any other base stations. The tessellation may also be supplied by the network operator.

[0027] Further, for each cell, the correlation between the socially driven data traffic and overall data traffic is calculated. The cells are chosen where the correlation is high. This process requires some further data from the cellular network specifically from the data traffic split between socially driven data traffic and overall data traffic. Further the peaks in data traffic are correlated.

[0028] The bootstrapping procedure is applied to select (202) the users. The users of social networks may indicate their locations in at least two ways that is either by mentioning their home locations in their SNSs profile or by geo-coding their social messages. The users selected are those who traverse regions spanned by the cells of interest. At the end of this user selection process, a list of users who would be statistically sufficient to predict spikes can be obtained.

[0029] Further, the user modeling procedure is applied to model (203) the mobility. For each user of interest, sufficient number of location traces is gathered from SNSs in order to build the mobility model. Once the location traces are obtained, mobility models for each user of interest will be obtained. The step 203 is periodically repeated to refine the models as and when new location data is available.

[0030] User modeling is further applied to model (204) the home-timeline. Due to privacy restrictions, obtaining home-timelines of users from SNSs is approximated by collating the social messages shared by the user's social circle.. The step 204 is repeated for each user of interest. For each URL present in the home-timelines collected, the click is simulated. In addition, the amount of data traffic generated if it had been clicked by the user is calculated.

[0031] The user model is applied to model (205) the clicking behavior. For each user, it is modeled as to whether and when the user is going to click on any URL present in their home-timeline. Further for each instance of time t in future (e.g. t = 1 hour from present time), the user models are aggregated which are estimated in step 203, 204, and 205 over all users of interest (estimated in step 202), for each cell of interest (estimated in step 201). Therefore it is possible to evaluate the quantity of socially driven data which may be generated in cells of interest at time t.

[0032] The aggregation of user models is repeated for several time instances and checked whether any of the predicted data traffic is higher than a threshold value. If the predicted data traffic is higher than a threshold value, then a spike is predicted (206). Based on user modeling for the mobility, home-timeline, and clicking behavior the spikes in OSN traffic may be predicted. Further, the correlation between OSN and cellular data traffic is used to predict spikes in cellular data traffic.

[0033]. The various actions in method 200 may be performed in the order presented, in a different order or simultaneously. Further, in some embodiments, some actions listed in FIG. 2 may be omitted.

[0034] FIG. 3 is a block depicting the modules involved in predicting spikes in a cellular data traffic system, according to the embodiments disclosed herein. The data that is observed in modeling is the clicks on links embedded inside social messages on OSNs., these pieces of data are generally unavailable publicly from SNSs. The data in the packet log maintained by the packet inspector is also unavailable due to legal complications

[0035] The two traits of an individual's clicking behavior are :
1. The clicks occur soon after the link arrives.
2. The probability of a click depends on the trustworthiness of the person forwarding it.

[0036] The clicking behavior module 301 incorporates the two traits. Consider a model where after a random (exponentially distributed) time of appearance of a link in a user's home-time line, the user tosses a biased coin and decides whether to click on the link based on the outcome. In an embodiment, the bias of the coin may be modeled to depend on the user from whom the link originated. Further, the type of the domain the link points to and the time-of-day can be taken into consideration while deciding the bias. For example, a user is more likely to click on a video link while at lunch break, whereas, a link to news article or photo sharing site can be clicked from work.

[0037] The clicking behavior module 301 searches data about "re-tweets" (or "Likes"). The re-tweets may measure the social popularity of contents and can indicate the probability of a click. If more data is available, the model is fine tuned to fit the additional data.. The volume of data a user is likely to generate at different times of the day can be modeled if the volume of data the link is likely to generate is known and vice versa. This results in a time series Vu, per-user.

[0038] The user mobility module 302 is used to model the mobility of users in cellular networks. The places users checks in to fall under two categories. The first category comprises of small number (typically 2) of clusters which correspond roughly to the user's home, and work locations or places connecting them corresponding to their commutes. The second category comprises of places where the user's friend checked in at a sufficient close in time.

[0039] Based on the categories, the user mobility module 302 works in multiple stages. Firstly, before checking in, the user tosses a (biased) coin to determine what type of check-in it is going to be whether it is "social" or "periodic". If the outcome is periodic, then the user picks either the "home" or the "work" state depending on time-of-day, and once the state is chosen, the user chooses the location from a Gaussian exclusive to the state. If the outcome is social, the user is supposed to choose from locations where his/her friend in the social circle checked in to in the same day. The probability of choosing a specific location from this lot depends on the time from the user's friend visit to that place and the geographical distance from his/ her current location. Further, the user mobility module 302 can be fit to the location data available from geo-coded social-messages obtained from OSNs. The location data may be fitted to the user mobility module 302. Any data from base station locations is considered additional and optional. In case more data (e.g. cell tower locations for these users) is available, the user mobility module 302 is tuned to fit the additional data.

[0040] The efficiency of the user mobility module 302 depends on how much location data is obtained per user. Since the current usage of OSNs and smart phones (or the like) is increasing periodically, the location trails for a significant fraction of users who contribute a lot of socially-driven data traffic and are instrumental in generating spikes in OSN traffic are obtained. The user mobility module 302 enables to access the time series of locations of the user.

[0041] The user home timeline module 303 infers the home-timelines of users by collating the social messages originating from their social circles.

[0042] In an example, consider the social networking site twitter. Twitter does not provide an Application Programming Interface (API) to obtain a set of users who are related to a region. The two location related APIs twitter provides are:

1.Search APT. A tweet is related to a region when either the tweet comes with a geo-location that falls inside the region in question, or, it is tweeted by someone who has indicated a place inside the region as his/ her home location in his/her public profile.
2. Streaming API: A sample of tweets bearing geo-locations from within that particular region is presented to the API client.

[0043] The set of users related to a region are harvested by repeatedly querying the Search API and Stream API. A client for search API needs to query frequently (e.g. 8 queries per minute over HTTP REST) and each response should amount to roughly 2 MB of data (furnishing 1 million tweets every day, translating to a throughput of 2 GB per day). In order to scale to the required frequency, queries are processed from many threads and client processes are executed in multiple virtual machines in parallel. To cope up with the storage requirement, a distributed highly available column oriented database is used.

[0044] A client for streaming API needs to be able to process a tweet fast. Whenever a tweet is aired from that region, the client receives a notification. Further, a thread is spawned and the tweet is stored into the data-store. Irrespective of the size of the region, tweets are received at the same frequency. In order to expedite the process, the region is broken down into smaller sub regions and executed clients clinging to one particular sub-region in multiple virtual machines, in parallel. There is one client per sub region and each client is run parallel .The tweets in the data-store are analyzed to find users from the region of interest, and also to gather their detailed location trails. Any user present in our database either specifies a location inside the region in their profile, or they tweet at least once from inside the region. For a subset of these users, this process yields more than one location traces.

[0045] The collection of re-tweets and other location traces can be bundled into the task of collecting the tweets harvested by the users. Twitter provides an API for collecting 3000 recent tweets by users. In order to keep the database updated, users need to be revisited often. To scale up to the requirement, multi-threaded crawlers are implemented and run on several virtual machines in parallel. Further, to establish a priority among users, the users prioritized are from locations of importance.

[0046] In order to approximate the home-timeline, the tweets of the user's folio wees are collated. Since the expansion can be huge, it is necessary to establish a priority among the followees. Thus, it is necessary to fetch followees that either have a sufficient number of followers or frequent tweeters.

[0047] In order to analyze the URL, it is necessary to determine the domain of the URL and also determine the number of bytes that will be generated when a user clicks it on a mobile device. HTTP re-directions are used to lengthen short URLS. Further, to determine the size of the URL a headless web browser is used. The headless web browser provides a programmable access to the content of the page (for example one can programmatically click on links present). The large number of URLs requires to be processed and the repeated occurrence requires caching the results of every individual analysis.

[0048] Further, some additional metrics such as global popularity of the URL and certain characteristics of the cascade involving the URL are monitored. In order to keep the raw data and various statistics calculated, several tables are maintained in the stat table 108 (depicted in FIG.l). For example, one table comprises all the information about users (their profile information, their incoming and outgoing tweets and their social-ties) which are stored as columns in the stat table 108. Several processes read and write to the stat table 108 with each process writing to their own (disjoint) set of columns. Similarly tables are maintained for storing the URL information and the various statistics calculated.

[0049] A prediction module is implemented as a map-reduce job. For each cell of interest, and a time-instance in future, the prediction module simulates each user model to see how much socially-driven data they would generate from this cell. The total socially-driven data traffic is a summation of these individuals (estimated) data traffics, and according to the value of this sum, a spike is predicted.

[0050] In a preferred embodiment, the probe in the cellular data network may furnish aggregate cell level statistics such as overall data volume, socially driven data volume, or it may furnish finer grained packet level information which is the I/P port of source, destination, referrer and so on. Further, for each user the system may record the current cell tower locations.

[0051 ] Though the above embodiment is explained with help of the social networking website mobile Twitter, it will be apparent to a person having ordinary skills in the art that the present embodiment can be explained/ practiced with the help of any other electronic device, all in accordance with the present invention.

[0052] The embodiments disclosed herein can be implemented through at least one software program running on at least one hardware device and performing network management functions to control the elements. The elements shown in Figs. 1 and 3 include blocks which can be at least one of a hardware device, or a combination of hardware device and software module.

[0053] The foregoing description of the specific embodiments will so fully reveal the general nature of the embodiments herein that others can, by applying current knowledge, readily modify and/or adapt for various applications such specific embodiments without departing from the generic concept, and, therefore, such adaptations and modifications should and are intended to be comprehended within the meaning and range of equivalents of the disclosed embodiments. It is to be understood that the phraseology or terminology employed herein is for the purpose of description and not of limitation. Therefore, while the embodiments herein have been described in terms of preferred embodiments, those skilled in the art will recognize that the embodiments herein can be practiced with modification within the spirit and scope of the embodiments as described herein.

CLAIMS

We claim:

1. A method for predicting spikes in data traffic in a cellular network, said method comprising of selecting a plurality of cells from said network which contribute to spikes in data traffic; selecting a plurality of users associated with said selected plurality of cells; modeling mobility for each of said selected plurality of users; modeling home timelines of online social networks belonging to each of said selected plurality of users; determining data traffic generated if each of said selected plurality of users click on at least link present in said home timeline; modeling clicking behaviour of said selected plurality of users; estimating data traffic at a particular time instant based on said modeled mobility, said modeled home timelines, said determined data traffic and said modeled clicking behaviour for each of said selected plurality of cells; and predicting a spike in data traffic, on said estimated data traffic being higher than a threshold.

2. The method, as claimed in claim 1, wherein selecting a plurality of cells from said network comprises of determining an initial plurality of cells by tessellating a region served by said network into a plurality of cells; calculating a correlation between social networks based data traffic and data traffic for each of said initial plurality of cells; selecting said plurality of cells from said initial plurality of cells, wherein said selected plurality of cells are cells with a high correlation.

3. The method, as claimed in claim 1, wherein said selected plurality of users traverse regions spanned by said selected plurality of cells.

4. The method, as claimed in claim 1, wherein modeling mobility of said selected plurality of users comprises of using location traces of said selected plurality of users.

5. The method, as claimed in claim 1, wherein modeling home timelines comprises of collating messages shared by social circle of each of said selected plurality of users; and tracking progress of cascades in said online social networks.

6. A system for predicting spikes in data traffic in a cellular network, said system configured for selecting a plurality of cells from said network which contribute to spikes in data traffic; selecting a plurality of users associated with said selected plurality of cells; modeling mobility for each of said selected plurality of users; modeling home timelines of online social networks belonging to each of said selected plurality of users; determining data traffic generated if each of said selected plurality of users click on at least link present in said home timeline; modeling clicking behaviour of said selected plurality of users; estimating data traffic at a particular time instant based on said modeled mobility, said modeled home timelines, said determined data traffic and said modeled clicking behaviour for each of said selected plurality of cells; and predicting a spike in data traffic, on said estimated data traffic being higher than a threshold.

7. The system, as claimed in claim 6, wherein said system is configured for selecting a plurality of cells from said network by determining an initial plurality of cells by tessellating a region served by said network into a plurality of cells; calculating a correlation between social network based data traffic and data traffic for each of said initial plurality of cells; selecting said plurality of cells from said initial plurality of cells, wherein said selected plurality of cells are cells with a high correlation.

8. The system, as claimed in claim 6, wherein said system is configured for selecting said selected plurality of users by checking for users of said network who traverse regions spanned by said selected plurality of cells.

9. The system, as claimed in claim 6, wherein said system is configured for modeling mobility of said selected plurality of users by using location traces of said selected plurality of users.

10. The system, as claimed in claim 6, wherein said system is configured for modeling home timelines by collating messages shared by social circle of each of said selected plurality of users; and tracking progress of cascades in said online social networks.