• 专利附录
  • 专利说明
  • 权利要求
  • 类似技术
  • 同族专利
  • 引用文献
  • 法律状态
  • 优先权
    • 专利摘要:
    STORAGE MEDIA CONTAINING CLOUD EDGE TOPOLOGY. The invention relates to cloud edge topologies (104). Some aspects concern cloud edge applications (104) and resource utilization in various cloud edge topologies (104). Another aspect of the present cloud edge topologies (104) may concern the specification of cloud edge applications (104) that use a temporal language. An additional aspect may involve an architecture that runs data stream management systems (DSMSs) machines over the cloud (104) and cloud edge computers (104) to execute query parts.
    公开号:BR112014016099B1
    申请号:R112014016099-6
    申请日:2012-12-19
    公开日:2021-04-20
    发明作者:Badrish Chandramouli；Suman K. Nath；Wenchao Zhou
    申请人:Microsoft Technology Licensing, Llc；
    IPC主号:
    专利说明:

    FUNDAMENTALS
    [001] The widespread adoption of 'smart' handheld computing devices, such as smartphones, by consumers and the availability of vast amounts of cloud-based computing resources have led to what is known as the "cloud edge topology". Smart handheld computing devices are termed 'smart' in that processor and memory advancements allow these devices to have substantial computing resources available to the user. Smart handheld computing devices can generate real-time data such as GPS location, battery drain, speed etc. These smart handheld computing devices can also be thought of as cloud edge devices in which communication between an individual device and cloud-based resources can be imagined as an edge.
    [002] Given the substantial computing resources available on the smart handheld computing device, the user can select various applications to run on his device. Many of these applications can be termed as cloud edge applications where one application instance runs on the smart handheld computing device and another application instance runs on the cloud-based computing resources. There is a broad class of cloud edge applications that correlate data across multiple smart handheld computing devices and the cloud to achieve application functionality. One example is a friend-finding application that works to notify a user if any friend is nearby. This app functionality relies on the correlation of real-time locations and slowly changing data such as social media. Although large amounts of computing resources are available on top of smart handheld computing devices and cloud-based resources, resource utilization, such as communication resources, can be significant when large numbers of smart handheld computing devices are running cloud edge applications. SUMMARY
    [003] The description refers to cloud edge topologies. Some aspects relate to cloud edge applications and resource utilization across multiple cloud edge topologies. An example might evaluate a real-time stream query that uses data from multiple different edge computing devices. Multiple different edge computing devices can be configured to communicate with cloud-based resources but not to communicate directly with each other. Individual edge computing devices include an instantiation of an application conveyed in a declarative temporal language. This example can compare resource usage between a first and a second scenario. The first scenario involves loading query data from multiple different computing devices to cloud-based resources for processing. The second scenario involves loading the query data from all but one node from the multiple different computing devices to the cloud-based resources and offloading the query data to that node from the multiple different edge computing devices for processing.
    [004] Another aspect of the present cloud edge topologies may refer to the specification of cloud edge applications that use a temporal language. An additional aspect might involve an architecture that runs data stream management systems (DSMSs) machines over the cloud and cloud edge computers to run query parts.
    [005] The examples listed above are intended to provide a quick reference to assist the reader and are not intended to define the scope of the concepts described here. BRIEF DESCRIPTION OF THE DRAWINGS
    [006] The accompanying drawings illustrate implementations of the concepts conducted in this application. The features of the illustrated implementations can be more readily understood by reference to the following description taken in conjunction with the accompanying drawings. Like reference numerals in the various drawings are used wherever practicable to indicate like elements. Furthermore, the leftmost number of each reference number leads to the figure and the associated discussion where the reference number is first introduced.
    [007] Figure 1 shows an example of a system to which the present cloud edge application resource utilization concepts can be applied according to some implementations.
    [008] Figure 2 shows an example of a system architecture to which the present cloud edge application resource utilization concepts can be applied according to some implementations.
    [009] Figures 3 to 9 show examples of graphs to which the present cloud edge application resource utilization concepts can be applied according to some implementations.
    [0010] Figure 10 shows a flowchart of an example of techniques for using the cloud edge application resource according to some implementations of the present concepts. DETAILED DESCRIPTION
    [0011] The present concepts refer to cloud-based systems and resource-aware, dynamic processing by applications running on cloud-based systems and connected devices.
    [0012] For the purposes of explanation consider introductory Figure 1, which shows an example of a system 100 which can implement the present concepts. System 100 includes three cloud edge computing devices (hereinafter, "computing devices") 102(1), 102(2), and 102(N) (where N means any number of computing devices could be used). Computing devices 102(1)-102(N) can communicate with cloud 104 via a network 106 as indicated by lines 108(1)-108(3), respectively. In this example, individual computing devices can communicate with each other through cloud 104, but not directly with other computing devices. Cloud 104 can provide vast amounts of computing resources 110, although the exact physical location of these computing resources may not be readily apparent. Cloud computing continues to gain in popularity due to the relatively inexpensive and extensive computing resources it offers.
    [0013] The 102(1)-102(N) computing devices can be any type of computing devices. Commonly these computing devices are portable computing devices such as smartphones and tablet computers. The term "computer" or "computing device" as used herein can mean any type of device that has some amount of processing power. Although specific examples of such devices are illustrated for purposes of explanation, other examples of such devices may include traditional computing devices such as personal computers, cell phones, smartphones, personal digital assistants, or any of a myriad of device types. always evolving or still to be developed. Also, rather than being standalone, a computer can be incorporated into another device. For example, a dashboard computer can be included in a car or other vehicle.
    [0014] Seen from one perspective, computing devices 102(1)102(N) can be thought of as 'edge devices' in a topology supported by cloud 104 and network 106. Many of these edge devices are equipped with sensors that produce frequent or continuous streams of real-time data such as a user's GPS location, speed, current activity, device battery usage, etc. In addition, there may be an increasing amount of reference data that they change slowly, such as social network graphs and gas prices being made available in the cloud, for example, through data markets. This proliferation of computing and data devices has fueled growing interest in an emerging class of real-time cloud edge applications (or, cloud edge applications for short). These cloud edge applications can provide services such as notifications or recommendations based on real-time streams collected from a large number of cloud and edge computing devices.
    [0015] In some scenarios, computing devices 102(1)-102(N) communicate their data to cloud 104 for processing by one or more service providers running on cloud computing resources 110. For example, assume for purposes of explanation that such a service is a friend-finding service that notifies a user whenever any of their friends are near their current location. In some implementations, the meet-a-friend service can be performed by a meet-a-friend application running on cloud computing resources 110 and corresponding meet-a-friend applications running on individual computing devices 102(1)-102( N).
    [0016] Enabling the meet friends application allows a correlation of real-time locations of users' smartphones (eg, computing devices 102(1)-102(N)) as well as slowly changing reference data such as a social network (which defines the friend relationship). For ease of explanation consider only computing devices 102(1) and 102(2) and assume that computing device 102(1) belongs to User1 and that computing device 102(2) belongs to User2. Also, assume that User1 and User2 were considered as 'friends'. Each computing device from time to time uploads data to the cloud as indicated by arrows 112(1) and 112(2). The uploaded data can be processed by the service provider operating on cloud computing resources 110. The service provider can determine the results for each computing device and communicate these results back to the respective computing devices 102(1) and 102(2). In some cases, such a process can generate high numbers of upload and download communications over the network 106 between the cloud 104 and the computing devices 102(1) and 102(2). The present concepts may allow an alternative option. This alternative option can be thought of as a dynamic resource-aware option. In the dynamic resource aware option, one of computing devices 102(1) and 102(2) can determine that system resource utilization, such as those network communications, can be reduced by the individual computing device obtaining data from the another cloud computing device and handling the processing locally on the individual computing device. (Network communications can be considered by number and/or network bandwidth usage). In such a case, the individual computing device does not load. The other (remaining) computing devices load as normal, and the individual computing device unloads. This dynamic resource-aware option can be thought of as dynamic in that resource utilization calculations can change as the scenario changes. One such example is described below in relation to a rate at which a computing device is generating location data. Resource utilization calculations can produce a different result when the location data rate changes. Thus, rather than being a one-time determination, the determination can be repeated in an iterative fashion as conditions or parameters change.
    [0017] To illustrate this reduced resource utilization, suppose that computing device 102(1) belongs to User1 and that computing device 102(2) belongs to User2. Also assume User1 is working from his office (eg relatively stationary) and User2 is driving in a nearby neighborhood. In the fixed configuration described above, an existing meeting-friends application will require User2 (computing device 102(2) to load (112(2))) its location frequently (say, once every 10 seconds) so that the cloud knows your current location to correlate with User1's location. User1 (computing device 102(1)), however, may load (112(1)) its location infrequently (say, once an hour) since he/she is not moving much. In this example, the total communication overhead of User1 and User2 will be 361 messages per hour (ignoring the final notification messages) over the 106 network. This network usage can be costly, especially when a user has many friends or runs many such applications . This can severely limit the application's usefulness as it is forced to limit how often it correlates user data, which translates into high notification latency. Furthermore, users can simply shut down the application due to its high resource usage. However, this inefficiency can be easily resolved in the above example with the dynamic resource-aware option. Rather than using a cloud mapping methodology, User1's location may be sent to User2's computing device 102(2) (via cloud 104 as indicated by arrows 114 and 116, respectively). The correlation can then be performed by User2's computing device. In this case, User2 doesn't need to send his location anywhere and the total cost would become only 2 messages per hour (one from User1 to the cloud, and one from the cloud to User2). Note that at a subsequent point in time, such as User1 is returning home, the dynamic resource-aware option may determine a different proposition, such as processing in the cloud 104.
    [0018] In short, the dynamic resource-aware option can determine which (if any) computation to push, and to which edge computing device to push it. The determination can be thought of as an optimization problem that depends on several factors such as network topology, data flow rates, data upload and download costs, pairs of flows to correlate, etc. Furthermore, as these parameters can change over time (eg User1's rate may change when he/she starts traveling after office hours), the determination can be dynamically updated. A dynamic resource-aware option implementation is referred to as RACE and is described in detail below.
    [0019] Briefly, RACE (which stands for Real-Time Applications on Cloud Edge), is a framework and system for specifying and efficiently running cloud edge applications. RACE can use database techniques to address two main issues. First, RACE solves the real-time cloud edge application specification. Second, RACE solves the system resource utilization associated with running applications and cloud edge in real time. The utilization of system resources can be improved and/or optimized (hereafter, for the sake of brevity, the term "optimized" means "improved and/or optimized"). SPECIFICATION OF CLOUD EDGE APPLICATIONS
    [0020] RACE solves the real-time cloud edge application specification by abstracting the cloud edge application core logic as platform-agnostic continuous queries (CQs) over a set of stream data sources.
    [0021] Cloud edge applications are often written in standard imperative languages such as Objective C, Java or C#. Application developers are required to manually implement mechanisms that handle cross-device communications, publishing and subscribing to data streams, and time-related semantics in application logic such as temporal joins and window computations. This process is time consuming and error prone. RACE can add platform support for common functionality shared by most cloud edge applications. Application designers can then focus on core application logic rather than implementation details.
    [0022] The present implementations leverage the fact that although different cloud edge applications have several application-specific characteristics (for example, visualization and support for privacy), they may share some common points. For example, both the data and core application logic for cloud edge applications are often temporal in nature. In other words, cloud edge applications can be seen as continuous queries that continuously correlate real-time and slowly changing (but still temporal) reference data in a massively distributed system.
    [0023] For example, the friend-finder app can be thought of as a temporal junction between the real-time GPS locations of edge devices and a slowly changing social network stream. A location-aware coupon application correlates current user location information with user profiles (computed over a historical time window) and current advertisements. Thus, in some implementations, the specification language for cloud edge applications must contain native support for temporal semantics. Such support allows for clean expression of time-oriented operations such as temporal joins and windowed aggregations. Alternatively or in addition, the language may have other properties. For example, one such property is the declarative nature of the specification language. This can allow application designers to specify applications in a declarative and agnostic mode of network topology, where they can focus on "what" applications are, rather than "how" they are implemented. Implementation details can be transparent to application designers, and instead be handled automatically by the underlying platform. Another property may refer to brevity. Application specification can be succinct, allowing for productive prototyping, development, and debugging by application designers. Conciseness is naturally in line with adopting declarative specifications. Flexibility can be another property. The specification language can be flexible so that application designers can easily customize the application according to different sources and input/output configurations.
    [0024] The specification language design space will now be described in light of these properties. Declarative languages such as SQL and Datalog (and their variants, eg Network Datalog) can allow for a succinct and flexible specification of continuous queries in distributed environments. However, these languages do not have native support for temporal semantics, which can be crucial for most cloud edge applications. On the other hand, data flow management systems (DSMSs) use declarative temporal languages that satisfy the desired properties. Examples include LINQ™ for Streamlnsight™, and StreamSQL™ for Oracle® CEP, and StreamBase™. The description below uses LINQ to Streamlnsight as the specification language, but is applicable to other configurations. LINQ allows the declarative specification of temporal queries, and is based on well-defined algebra and semantics that fit well with the temporal nature of cloud edge applications.
    [0025] The discussion that follows provides an example of a cloud edge application specification. Remember that the friend-finder query finds all user pairs (User1, User2) that satisfy the conditions: 1) User2 is a friend of User1; and 2) the two users are geographically close to each other at a given time. At this point, for purposes of explanation, assume that the friend relationship is asymmetric, that is, User2 being a friend of User1 does not necessarily imply otherwise, given a point in time. There are two entries for the friend-finder app, namely the GPS location streams reported by edge devices, and the social network data. GPS locations are actively collected at runtime, while social network data is relatively slow to change and is generally available in the cloud. Friend-finder can be written as a two-stage temporal join query as illustrated below.

    [0026] The first query (query0) joins the GPS location stream (location) with the social network reference stream (socialNetwork), and the resulting output stream is joined with the GPS locations (in query1), to check the distance between each pair of friends. The final output is a stream of pairs (User1, User2) where the two users are friends and are geographically close to each other.
    [0027] The above query specification defines the high-level query logic as temporal joins, and references the socialNetwork flow and location flow schemas. This is written on top of the social network stream and a conceptually unified GPS location stream input, and is thus agnostic of network topology. As another example, assume that a desired function is to find friends who visited a specific location (say a restaurant) within the last week. To specify this, present concepts may allow replacing the location entry in query1 with location.AlterEventDuration(TimeSpan.FromDays(7)). This extends the "lifetime" of location events to 7 days, allowing the merge to consider friend events within the last week.
    [0028] In short, RACE can use a declarative specification of a cloud application. RACE can run logic on distributed system made up of edge devices and the cloud. RACE can use an unmodified DSMS as a black box to locally run queries on individual edge devices and the cloud. Some RACE implementations may operate on the assumption that DSMS provides a management application program interface (API) for users to submit queries (which define the continuous queries to be executed), event types (which specify the flow scheme input data), and input and output adapters (which define how data streams reach the DSMS from the outside world and vice versa). In addition, the API also allows users to start and stop queries about DSMS.
    [0029] Stated otherwise, some implementations may move different data streams (or parts of streams) to the cloud and/or to other edge computing devices through the cloud. Some other data streams may be held locally on the device and not uploaded to the cloud. Furthermore, these various streams (moved and local) can serve as inputs to application query threads that run in various locations (such as a subset of devices or even in the cloud). The output streams of such queries themselves can either be held locally for further computations or uploaded to the cloud (and then possibly transferred to other devices). In general, end-user-specified computation can be performed in a distributed mode. RACE ARCHITECTURE
    [0030] Figure 2 shows a general system or system architecture 200 of a RACE implementation. System architecture 200 carries computing devices 102(1)-102(N), cloud 104, and network 106 of Figure 1. System architecture 200 introduces a RACE 202 management server and a RACE processor 204. The RACE processor includes a graph builder 206, an optimizer 208, and a query builder 210. The system architecture 200 also includes statistical data 214, reference data 216, a control plane 218, and a control plane. data 220. Computing devices 102(1)-102(N) include an instance of DSMS 222(1)-222(3), respectively. An instance of DSMS 222(4) also occurs in cloud 104.
    [0031] System architecture 200 is explained in relation to an experience provided for an application developer 224. The application developer can interact with the RACE 202 management service by writing an application in a declarative and temporal language, such as LINQ 226. Assume for purposes of explanation that the application is a friend-finder application 228. The functionality of friend-finder applications was introduced above with respect to Figure 1. The friend-finder application 228 can manifest on individual computing devices 102( 1)-102(N) as friend-finder application instantiations 228(1)-228(3), respectively, and over cloud 104 as friend-finder application instantiations 228(4). Still, although only illustrated in relation to computing device 102(1) for the sake of brevity, the individual computing devices may include various hardware 230. In this example, the illustrated hardware is a processor 232, a storage 234, and another 236. The elements mentioned above are described in more detail below.
    [0032] Processor 232 can execute the data in the form of computer readable instructions to provide functionality, such as friend-finder functionality. Data, such as computer readable instructions, can be stored in storage 234. The storage can be either internal or external to the computing device. Storage 234 can include any one or more of volatile or non-volatile memory, hard disks, and/or optical storage devices (e.g., CDs, DVDs, etc.), among others.
    Computer 102(1) may also be configured to receive and/or generate data in the form of computer readable instructions from storage 234. Computer 102(1) may also receive data in the form of computer readable instructions about the network 106 which are then stored on the computer for execution by its processor.
    [0034] In an alternative configuration, the computer 102(1) can be implemented as a system-on-a-chip (SOC) type design. In such a case, the functionality provided by the computer may be integrated into a single SOC or multiple coupled SOCs. In some configurations, computing devices can include shared resources and dedicated resources. An interface(s) facilitates communication between shared resources and dedicated resources. As the name implies, dedicated resources can be thought of as including individual portions that are dedicated to achieving specific functionality. Shared resources can be storage, processing units etc. that can be used by multiple functionalities.
    [0035] Generally, any of the functions described here can be implemented using software, firmware, hardware (eg, fixed logic circuit), manual processing, or a combination of these implementations. The terms "tool", "component", or "module" as used herein generally means software, firmware, hardware, entire devices or networks, or a combination thereof. In the case of a software implementation, for example, these can represent program code that performs specified tasks when run on a processor (eg CPU or CPUs). Program code may be stored on one or more computer-readable memory devices, such as computer-readable storage media. The component's characteristics and techniques are platform-independent, meaning they can be implemented on a variety of commercial computing platforms that have a variety of processing configurations.
    [0036] As used herein, the term "computer readable media" can include transient and non-transient instructions. In contrast, the term "computer readable storage media" excludes transient instances. Computer readable storage media may include "computer readable storage devices". Examples of computer-readable storage devices include volatile storage media, such as RAM, and non-volatile storage media, such as hard disks, optical disks, and flash memory, among others.
    [0037] Other hardware 236 may include displays, input/output devices, sensors etc. which may be implemented in various computing devices.
    [0038] The RACE 202 management service can run on cloud 104 and expose a management service that is fully compliant with the DSMS management API. Thus, individual computing devices 102(1)-102(N) can submit their declarative cloud edge application logic to the RACE management service 202 as regular temporal declarative queries supported by the respective DSMS 222(1)-222 (N). Note that from an edge device perspective (eg 102(1)-102(N) devices), these simply appear to communicate with a normal DSMS machine.
    [0039] Viewed from another perspective, the RACE management service 202 can be thought of as being configured to interact with an application running in the cloud and on individual edge computing devices communicating with the cloud. The RACE management service 202 can be configured to simulate a DSMS machine to receive the temporal declarative queries from the individual edge computing devices.
    [0040] Briefly, the RACE processor 204 can be thought of as intercepting and analyzing the incoming query, adapters, and types of the individual computing devices 102(1)-102(N) that run the friend-finder application 228. RACE processor 204 then compiles these entries into an object representation of the original query. The object representation is passed to graph builder module 206 which converts the original query to a larger query graph. For example, the larger query graph might include input streams by edge and operators. The query graph is passed to optimizer module 208 to decide the optimal operator placement. Finally the query builder module 210 can generate object representations of types, adapters, and (sub) queries to be executed on individual computing device 102(1)-102(N) or on cloud 104. These objects are sent to the individual DSMSs (via their management APIs) of the respective computing devices to execute the application logic in a distributed mode. Note that while in this configuration, the RACE management service 202 and the RACE processor 204 are implemented in the cloud 104, in other implementations, alternatively or additionally, the RACE management service and/or the RACE processor could be implemented in one or more of the 102(1)-102(N) computing devices. The RACE management service and/or RACE processor implemented on the computing devices could be standalone or operate in a cooperative mode with the corresponding RACE management service and/or RACE processor instantiations in the cloud.
    [0041] The graph builder 206 can be thought of as taking the object representation of a query as an input, along with statistics about flow rates and metadata information about each input. The graph builder can first use the query object representation to generate a query pattern, which represents a template or skeleton for generating the expanded query graph. For example, Figure 3 illustrates the query pattern 302 issued by graph builder 206 for the friend-finder query described above with respect to paragraph 25.
    [0042] Some of the input streams in query pattern 302 refer to per-device data streams such as GPS location sources. Graph builder 206 can create multiple instances of the query pattern by dividing such streams into multiple inputs, one per edge. Slowly changing reference data entries, such as social networking, can be materialized to limit the size of the generated query graph. For example, Figure 4 shows a social network 400 of four users P, Q, R, and S. Figure 5 shows the corresponding instantiated query patterns 502(1), 502(2), and 502(3) for the friendfinder query. Note that in order to allow for information sharing and to avoid duplicate borders in the instantiated query patterns, the instantiated source and operators together are carefully named, as shown in Figure 5. The final step is to sew the instantiated query patterns 502(1 )-502(3) in a complete query graph.
    [0043] Figure 6 shows a final 602 query graph derived from the instantiated query patterns shown in Figure 5. Note that when combining the instantiated query patterns, vertices (in the instantiated patterns) with the same name are mapped to the same vertex in the final query graph. For example, the Join<GPS-P, SNP > vertex is shared by the instantiated patterns for edges (P; R) and (P; S).
    [0044] Returning to Figure 2, the optimizer module 208 accepts the final query graph 602 as input, and decides where to run each operator (eg, query part) in the query graph so that the total communication cost or application collective is minimized (or at least reduced). With thousands or even millions of users participating in the cloud edge system, the final query graph could be huge - containing millions of operators. For such a large query graph, optimal operator placement is not trivial. The RACE Optimizer module can use several techniques to determine the optimal operator placement. One such technique is described below under the heading "Optimal Operator Placement". RACE can perform a periodic re-optimization to adjust placement to changes in the query graph and/or statistics.
    [0045] After decisions for improved/optimal operator placement are made, the RACE processor 204 has a set of root query graphs (each consisting of a directed acyclic graph (DAG) of temporal operators. match some location (edge or cloud). Query builder module 210 can generate object representations of query components (including event types, adapters, and queries) for each graph. Query builder module can then submit the object representations to the corresponding DSMS via control plane 218. Note that two additional adapters can be installed in each DSMS instance - one to send event data to data plan 220, and one to receive event data from data plan.
    [0046] The RACE 218 control plane is used to place the generated query fragments and metadata on the cloud instance and the DSMS edge instances using the DSMS management API. One complication is that edge devices (eg telephones) are usually not directly reachable or addressable from the RACE 202 management service. Instead, the RACE management service can maintain a server for which the edge devices create and maintain persistent connections in order to receive management commands that are transferred to DSMS instances over the edges. During query execution, events flow between the edge devices and the cloud. The RACE management service 202 can utilize a separate data plane 220 which is exposed as a server in the cloud 104, and to which edge computing devices 102(1)-102(N) can connect via the data plane. control 218. The generated queries about the edge computing devices and the cloud subscribe and publish named streams that are registered with the data plan 220. The data plan routes the events from the cloud 104 to the edge computing devices 102( 1)-102(N) and vice versa.
    [0047] With thousands and even millions of users participating in the cloud edge system, the final query graph could be huge - containing millions of operators. As data sources are distributed (eg, GPS data streams from multiple users originate from their edge devices), the placement of each operator has its impact on query evaluation overhead. There are exponentially many different combinations of operator placement. A naive proposal that searches the entire design space may not be feasible. Also, considering the sharing of intermediate results makes the problem even more difficult.
    [0048] The following discussion refers to an example of an efficient algorithm for optimal operator placement, leveraging the special "star" topology of cloud edge systems. For some implementations, the accuracy of the algorithm can be proven given the two assumptions mentioned below. Also, the overhead of finding the optimal placement can be very low.
    [0049] Assumption 1. The final output of queries is relatively much smaller than the input stream data, and therefore its cost can be ignored.
    [0050] This assumption is reasonable given the general nature of cloud edge applications. Also, based on privacy considerations, some implementations may restrict the allowable locations of operators. For example, stream data might include sensitive personal information (for example, the geolocation traces of a mobile phone). An edge client may not want to expose raw information unless it is properly processed (excluding sensitive data from the final results of a join operation), or if it is only dispatched to nodes that have been authorized.
    [0051] Assumption 2. For any A 1 1B join (where A and B are the input streams of the join), the join operation is performed either in the cloud or at the nodes where A or B originated.
    [0052] Note that this assumption does not simplify the placement problem; there is still an exponential number of possible operator placements. Before presenting the reasoning and the proposed algorithm, several graphic-based denotations are described.
    [0053] Definition (Demand) May be denoted as a pair (v1, v2), that a v2 stream data source "demands" (ie needs to correlate with) the data generated by another v1 source.
    [0054] Definition (Demand Graph) Given a cloud edge application, the demand graph G = (V, E) is defined as follows: the vertex set V = { v/v is a stream data source }, and E = {(VI, v2)(vi, V2) is a pair of demands}. Each edge e = (i,) and E is associated with a rate rij, which indicates the rate of the flow of vj that is demanded by vj. Algorithm 1. Query Graph Generate Demand Graph

    [0055] Figure 7 shows the corresponding demand graph 702 for the friend-finder query, given the social network shown in Figure 4. The edges in the demand graph 702 illustrate the demand relationships. For example, the edge GPS-P, SNp) indicates that the GPS reading of P (GPS-P) must be correlated with the social network (SNp). In a demand graph, operators together are treated as virtual data sources in the demand graph (as they are producing results together as flows). Indeed, there is a one-to-one mapping between demand graphs and query graphs. Given a query graph GQ = (VQ, EQ), Algorithm i generates the corresponding demand graph GD = (VD, ED). The query graph can be redesigned by the demand graph following a similar algorithm
    [0056] Attribution: Download versus Upload. In general, deciding an optimal operator placement for distributed query evaluation is known to be a difficult problem. The essence of the proposed algorithm is rooted in leveraging a special network property of the cloud edge architecture. In this case, edge computing devices cannot communicate with each other directly. Instead, to exchange information, edge computing devices need to upload or download data via cloud-side servers.
    [0057] Definition (Upload and Download). Given a demand graph G = (V, E), for an edge (I, j) and E, this implementation characterizes vj as "uploading" over (I, j), if, regardless of where vj is placed (or in an edge computing device or on the cloud server), it always makes an effort to have the corresponding stream (demanded by vj) available on the cloud server; otherwise vi is characterized as "downloading" in (i, j).
    [0058] Intuitively, since a vertex decides to load over an edge (which represents a required data correlation), there is no reason for it to offload any data for this correlation from the cloud-side server, because the correlation may simply be run on the cloud side (as data has already been made available on the cloud side). Consider the following motto.
    [0059] Lemma 1. Given a demand graph G = (V, E), in its optimal operator placement, t/(i,j) and E, (i,j) must be in one of two statuses: or vi is loading (but not unloading) or unloading (but not loading) in (i ,j).
    [0060] Proof; Suppose a vertex Vi and V decides to both load and unload at (i,). The operator together for the corresponding correlation can be placed in three locations (according to Assumption 2), namely vi, vj, and the cloud. In this case the operator together cannot be placed in vi in the optimal placement: since vi is already loading its flow. The joint operation could be performed in the cloud, in which case it saves the communication cost to download the data from vj to vi. Therefore, vi is not downloading in (i,) (since no operator together is placed in vi)
    [0061] Lemma 1 supports the conclusion that, given a demand graph G = (V,E), there is a mapping of its optimal placement to a set of upload vs. decisions. downloads made over each vertex in G. Such a set of decisions is defined as an assignment.
    [0062] Definition (Assignment). Given a demand graph G = (V,E), an assignment A : E ^ {D, U} is defined as follows: A, = U if vertex Vj decides to carry its flow data over the edge (i, j), otherwise Ai,j = D.
    [0063] The optimal placement and its corresponding assignment can be denoted as Popt and Aopt. Figure 8 shows the optimal placement (Popt) for the demand graph 702 of Figure 7. Figure 9 shows the corresponding assignment (Aopt). In optimal operator placement, the join between GPS-P and SNP is performed at node P, which means that the SNP partitioned social network graph must be dispatched to node P, ie, SNP is "loaded" to the cloud , and GPS-P is not. This is consistent with the assignment given in Figure 9.
    [0064] It is natural to ask questions 1) if there is a reverse mapping of Aopt to Popt, and 2) if there is an efficient algorithm to find the Aopt, given a demand graph. The discussion below initially addresses the first question, and then gradually develops the answer to the second question.
    [0065] Not all assignments can be mapped to a viable assessment plan. There is a fundamental restriction: a join requires collocation of all its entries. Therefore, for any junction that takes inputs from different sources (edge devices) at most one device is unloading.
    [0066] Definition (Feasibility and Conflict). Given a demand graph G = (V, E), an assignment A is viable if it satisfies the following condition: /e = (i,) and E, A, ^ D v Aj,i * D. A breaking edge this condition is called a conflict edge.
    [0067] For example, Figure 9 illustrates a viable assignment given the demand graph shown in Figure 7, as for any correlation, at most one data source is deciding to offload. If ASNP,GPS-P is changed to unload, it will invalidate the assignment, as the edge (SN, GPS-C) is a conflicting edge.
    Lemma 2. Given a viable assignment A, A can be mapped to a corresponding operator placement.
    [0068] Proof. Proof by construction. Operator placement is decided in a bottom-up mode (shown as Algorithm 2). Like the base case, the locations of leaf vertices in a query graph are known (trivially the flow sources). For an internal vertex (that is, a virtual vertex that represents an operator together), according to assumption 2, it can either be placed on the cloud-side server, or co-located with one of its inputs. If all input sources decide to load, then the operator together must be placed in the cloud; otherwise, there is one and only one input source (given the A assignment being feasible, deciding to download, then the operator together must be placed with that input source.
    [0069] Theorem 4.5 The optimal operator placement problem can be reduced to finding a viable assignment with an optimal cost (directly derived from Lemma 1 and Lemma 2). Single Level Board Inquiries
    [0070] This discussion starts with a simple scenario, where applications are specified as single-level join queries. The discussion will be extended to multi-level board consultations in the discussion that follows. Same Demand Rate
    [0071] The discussion first considers a special case of single-level joint queries, in which, for any vertex i in a demand graph, the flow rates for all outgoing edges are the same, namely, V( i,j) and E; ri.j = ri. Basically, an operator together requires the total flow data from each input stream to perform the operation together. This corresponds to queries where no filtering (such as projection or selection) is performed before the join.
    [0072] Rather than directly considering the cost of an assignment, some implementations can compute the gain of changing loading and unloading (which could be positive or negative compared to a viable base assignment - a naive solution that all vertices choose to carry. your flow data. By changing a vertex i from load to unload, the gain can be computed as follows: gain,

    [0073] Definition (Global Optimal Degree). Given a demand graph G = (V, E), for the global optimal assignment it is a viable assignment A that maximizes the total gains.
    [0074] The following technique for finding an Aopt assignment that makes the global optimal degree considers a greedy proposal where each vertex in the demand graph locally makes the assignment decision based on its own benefit.
    [0075] Definition (Local Optimum Degree). Given a demand graph G = (V, E), for each vertex v and V, the optimal local assignment for v is a local decision about Av that maximizes the local gain. Specifically, Av = D if and only if gainv > 0.
    [0076] It can be proven that the local optimum degree is actually consistent with the global optimum degree, which has two implications: First, the overhead to compute the local optimum degree is low, which is linear to the number of vertex degrees in the demand graph. Second, it means that the assignment problem can be partitioned and solved in parallel. This is especially important in cases where the demand graph is huge, as this technique can leverage vast cloud computing resources to efficiently solve it.
    [0077] Theorem 1. Given a demand graph at G = (V, E), the assignment A = {Av Av = assignment [optimal location in v, v and V} is feasible.
    [0078] Proof. Proof by contradiction. Suppose there is a conflict edge e = (i,j), which means that Ai = D and Aj = D. Ai = D provides that gain, = ri - ∑(i,j)eE rj > 0. ri >j Similarly, rj > ri can be derived from Aj = D. Contradiction.
    [0079] Theorem 2. Local optimal degree is consistent with the global optimum degree, namely, the global optimum degree can be derived by individually applying the local optimum degree.
    [0080] Proof. 1) Theorem 1 shows that the attribution derived by individually applying the local optimal degree is feasible. 2) Each local optimum degree is computing the maximum gain for an isolated physical connection, and the global optimum degree is simply the sum of the gains over the physical connections. Different Demand Rates
    [0081] The discussion is now extended to consider the scenario where, for a given vertex i, the flow rates demanded by each of the other vertices may be different. For example, in the case of the friend-finder app, the event rate for a specific user may be different for each of your friends. Here, it is assumed that the stream with a lower rate can be constructed using one with a higher rate, which corresponds to queries that apply sampling filters. In other words, a filter that needs to sample x events/second can be provided by another filter that samples y events/s, for any y >x. In such a scenario, load versus unload decisions need to be made for each edge (rather than each vertex) in the demand graph.
    Assuming that the rates ri,vj are sorted at vertex i, so that ri,v1 < ri,v2 < ... < ri,vp it is not difficult to see that an optimal assignment for the p sorted edges must have the pattern [U, ..., U, D, ..., D].
    [0083] Definition (Great local degree). Consider the gain of an assignment vj < k, Ai,v = U, Vj > k, Ai,v = D: gaini,vk = n,vp - n,vk - ∑k+i<s<pRs,i. Some implementations can select k = argmaxi<j<pgaini,vk, and configure the assignment in the pattern described above.
    [0084] Lemma 4.8. After applying the local optimum degree to vertex i, which

    [0085] Proof. Proof by contradiction. Suppose ri,vj>rvj,i. According to the definition of local optimum degree:

    [0086] Note that j > k, since Ai,vj = D. Also gaini,vj - gainiv,k = riv,k + ∑k+i<s<j-1rvs,i + (rvj'- ri,vj ) > 0. This creates a contradiction since gaini,vk is great).
    [0087] Theorem 3. The feasibility theorem (Theorem 1) is still true.
    [0088] Proof. Proof by contradiction. Suppose there is a conflict edge is (v1, v2). Applying Lemma 3, it supplies rv1,v2 > rv2,v1 of Av1,v2 = D, and rv2,v1, > rv1,v2 of Av2,v1 = D, which produces a contradiction. Multi-Level Joint Queries
    [0089] When considering the queries together with multiple levels, there may be difficulties that prevent naively to apply the algorithm developed for the queries together with a single level. For example, for single-level joint queries, the cost of the output streams for the operators together is not considered (since the final output is assumed to be insignificant compared to the input streams). However, this is not the case for queries together at multiple levels. For example, when naively applying the algorithm presented in the previous section, an edge device can individually decide to offload other streams and perform the computation locally. However, if the edge device is aware of the fact that outflow is then required for a higher level operator together (whose optimal placement is on the cloud side), it may make a different decision. The discussion below addresses how this challenge is solved by extending the algorithm to single-level joints.
    [0090] Assumption 3. A data stream from a given edge appears in no more than one child subtree of any operator in the query graph.
    [0091] This is a reasonable assumption, as one can simply combine flows from the same edge device into a single flow, or locally perform the necessary computation in which these flows are involved. Note that this assumption does not exclude source sharing or intermediate results, and specifically, it is always true in the case where the query pattern is a deep left tree over different data sources. Operator Placement In A Top-Down Mode
    [0092] The operators together internal to the query graph can be seen as virtual flow sources, except that their locations need to be decided. Intuitively, given a query graph, present techniques can make load versus unload decisions for operators in top-down mode. For example, the decision can be made for a given vertex vi that corresponds to an operator together, as long as the location where its output is to be dispatched (based on the placement decision made by its parent operator) is known. The algorithm for single-level merge queries can be directly extended further by including the cost of dispatching the output stream to the destination.
    [0093] Note that the only destination considered is the cloud side. For example, even if the destination is another edge device (since the outflow is required by another v2 vertex located on the edge device), the technique does not need to consider the offload part of the dispatch cost (ie, the cost of sending the cloud-side output stream to that edge device), as this offload cost is already considered in the gain calculation for v2. Note that Assumptions 1 and 3 ensure that when considering vertex v1, the actual placement decision can be disregarded for your destination, as it will definitely be placed either on the cloud or on some other edge than v1 (or its subtree) does not overlap. This key observation makes the extension of the algorithm possible, and it can be easily shown that the extended algorithm still guarantees a viable and optimal assignment. Loading Versus Unloading In A Top-Down Mode
    [0094] Note that the previous proposal (for single-level joint queries) derives placing operators in bottom-up mode after loading versus unloading decisions are made. Algorithm 3 can be refined to decide the loading versus unloading assignment based on the assignment of the parent operators rather than their placement (since placement is not feasible).
    [0095] Since the decision of the parent vertex v1 is known, some implementations may consider that the decision must be made for a child vertex v2. Again, v2 has two choices - either upload or download.
    [0096] In one scenario, if the decision of the v1 parent vertex is offload, this means that there is no need to make the effort to have the output available on the cloud server. Therefore, when finding the local optimal degree for v2, the outflow cost is not considered in the computation of the gains.
    [0097] In another scenario, if the v1 parent vertex decision is to load, it means that the v2 output stream must be made available on the cloud server. Therefore, when finding the optimal local degree for v2, the outflow cost must be considered.
    [0098] Algorithm 3 takes the demand graph G = (V, E) as the input, and computes the optimal operator placement. The algorithm applies to a generic scenario where it assumes a joint query of multiple levels, and demand rates per edge (ie, rates associated with demand edges starting from a given vertex may be different). According to Theorems 1 and 2, it is not difficult to see that the derived assignment is feasible and optimal. Algorithm 3. Compute Optimal Attribution

    Asymmetric Loading/Unloading Costs
    [0099] Until now, the above techniques have operated on the assumption that the loading cost and the unloading cost are the same. However, in reality, this may not be the case. For example, prices per unit of bandwidth usage for uploading and downloading may be different (for example, a cloud service provider may introduce asymmetric costs to encourage users to feed data into the cloud). As another example, an edge device could exhibit different battery consumptions for charging and discharging.
    [00100] The discussion that follows considers asymmetric loading/unloading costs. The cost per unit for loading and unloading is denoted as Cu and Cd. For the scenarios where Cu< Cd, the results for Cu = Cd presented in the previous sections still hold. Basically, the reasoning of the key feasibility theorem (Theorem 1) is true.
    [00101] On the other hand, deciding the optimal operator placement is a more difficult problem for the cases where Cu> Cd. For a special case where Cd = 0, it can be shown that the optimal operator placement problem is shown to be difficult by reduction of the classic minimum weighted vertex coverage (WMVC) problem. Essentially, the feasibility theorem breaks in these cases, so having the edge devices individually applying the local optimum degree can result in conflicts. In such cases, a viable assignment can still be obtained by resolving conflicts by adjusting some vertices in the demand graph for loading at higher rates. Therefore, the problem reduces to the WMVC problem in the residual graph, which lacks an efficient general solution. The following discussion refers to a condition. If the condition is satisfied, the optimal operator placement problem can be efficiently solved.
    [00102] Definition. Given a demand graph G = (V, E), the slope of a vertex v G V, Sv is defined as the ratio of the maximum and minimum rate associated with the edges leaving v. Namely, Sv = max(v,i)gEi)rv,i/min(v,j)gE)rv,j.
    [00103] Definition. Given a demand graph G = (V, E), the slope of G is defined as the maximum slope between the nodes in G. Namely, S = maxvgVSv.
    Table 1: Shows a summary of the operator placement algorithm. The overall optimum degree is achieved in all cases.
    [00104] Lemma 4. Given the slope S of a graph G, if Cd< Cu< (1 + 1/S) . Cd, after applying the local optimum degree over all vertices, the residual graph G' consisting of the conflict edges is acyclic (ie separate trees).
    [00105] Proof. Proof by contradiction. Suppose there is a cycle (Vi, V2), (V2, V3),..., (V(p-1), Vp), (Vp, VI) in the residual graph G'. For presentation purposes, denote that vo = Vp and v(p+i) = vi. Since each edge in the cycle is a conflicting edge, V1 < i < p, there is a loose link that

    [00106] Therefore, this implementation may derive the following contradiction:

    [00107] Theorem 4. If Cd< Cu< (i+ i/S) . Cd, the optimal operator placement can be found at time P.
    [00i08] Proof. It can be concluded by applying Lemma 4 that G' is acyclic. This discussion shows that, for each tree in the residual plot G', its weighted minimum vertex coverage can be found in linear time using a dynamic program algorithm.
    [00i09] Starting from the leaf vertices, for each vertex v, consider the vertex cover cost for the subtree (in root by v), having (or not having) v, in the cover set. For any inner vertex v, if v is not within the coverset, then all children of v must be in the coverset . Therefore, Cost-v = ∑kchild(v) Cost+v. On the other hand, if v is in the cover set, then each subtree can independently choose its vertex cover: Cost+v = cv + miniechild(v) (Cost-v, Cost+v).
    [00110] Note that for a special case where the flow rates required by different friends are the same, the optimal placement can be found at time P, if Cd< Cu< 2 . Cd (which is true in the most practical scenarios). Empirically, even if Cu >2 . Cd, the conflicting edges still form isolated trees. SUMMARY
    [00111] Table 1 summarizes the theoretical results and time complexity of the proposed operator placement algorithm, given various combinations of query complexities, selection conditions, and load/unload cost ratios.
    [00112] The operator placement algorithm computes the globally optimal solution by individually considering the local optimal degree for each vertex in the demand graph. This discussion proves that the local optimum degree is consistent with the global optimum degree (if Cu < Cd). An efficient greedy algorithm is proposed to compute the local optimum degree. With this efficient greedy algorithm each node individually chooses the solution that maximizes local gain.
    [00113] The algorithm handles both more complex single-level and multi-level queries. In the case of multi-level joint queries, the built-in operators in a query graph are treated as virtual vertices.
    [00114] The local optimum degree can be computed for each individual vertex in a top-down mode. Furthermore, in the common case where the residual graph is acyclic (for Cu>Cd), there is an efficient dynamic programming (DP) algorithm to find the optimal assignment for the demand graph. Therefore, an optimal operator placement for the query graph can be determined. The extension of these concepts to general query charts with black box operators is also explained.
    [00115] Given the nature of cloud edge applications (which are usually correlations through real-time data), the above discussion has mainly focused on queries together (with sampling filters). The discussion that follows concerns how the proposed algorithm can be applied to support general query graphs in a cloud edge topology. The discussion further explains how runtime dynamism such as query graph changes and event rates can be handled. Handling General Query Graphs
    [00116] A G query graph is defined as a directed acyclic graph (DAG) over a set of black box operators (denoted as O), where the leaves in G are called sources, and the roots are called dips. Each operator in O can take zero (for sources) or more inputs, and its output can be used as an input for other operators. A selection and projection are examples of one-entry operators, while a join operation is an example of two-input operators (or a multiple-input operator for leafy joints). The high-level intuitions of the operator placement algorithm still hold that each operator can individually decide (in a top-down order) whether it should load (or unload) its output to optimize its local cost. In this case, the attribution feasibility is still guaranteed as before. Furthermore, given that operators are considered as black boxes, there is no longer an opportunity to exploit sharing through the input of different operators. In this case, the consistency between the local optimal and the global optimal still holds, following reasoning similar to Theorem 2. Therefore, the problem can again be reduced by finding the optimal loading/unloading assignments, and the proposed efficient local optimal degree algorithms can be used. Manipulating Dynamism
    [00117] Some instances of the algorithm assume query graph availability, and rate statistics for all flows. The optimal placement is computed based on this information collected in the optimization stage. However, the query graph can change over time, for example, due to the addition and removal of borders in the social network. Similarly, event rates can also change over time. Thus, it may be necessary to adapt to these changes during runtime. Since the proposed optimization algorithm is very efficient, periodic reoptimization is a viable solution. However, re-optimization can encounter placement overhead (eg, sending control plane messages such as query definitions). If implementations re-optimize too often, re-optimization overhead can obscure the benefits of optimization.
    [00118] To solve this dilemma, one solution is to use an online algorithm based on cost. For example, such an algorithm can estimate and maintain the accumulated loss due to not performing reoptimization, and choose to perform reoptimization if the accumulated loss exceeds the reoptimization overhead. A potentially beneficial property of this proposal is that it is tricompetitive - the total cost is guaranteed to be limited by 3 times the optimum (even with a priori knowledge of the changes).
    [00119] The above discussion provides great details of specific RACE implementations. RACE can support a wide class of real-time cloud edge applications. RACE solved two main technical challenges: (1) the specification of such applications; and (2) its optimized execution in the cloud edge topology. for (1), the discussion shows that using a declarative temporal query language (such as LINQ to Streamlnsight) to express these applications is very powerful and intuitive. For (2) the use of DSMS machines is proposed to share processing and execute different portions of application logic on edge devices and in the cloud. Here, the new algorithms are highly efficient but are likely to minimize the overall network cost, while handling asymmetric networks, general query graphs, and intermediate result sharing. The above RACE implementations are configured to work with Microsoft® Streamlnsight®, a commercially available DSMS. Other implementations can be configured to use other DSMS options.
    [00120] Experiments on real data sets have indicated that the RACE optimizer is orders of magnitude more efficient than prior art optimal placement techniques. Still, the placements achieved by the present implementations incurred several lower cost factors than simpler layouts for a friend-finder app on top of a realistic social network graph with 8:6 million edges. RACE is easily parallelizable with the cloud. It also scales well using just a single machine in real placements with up to 500 edge clients. Details of some implementations are described above at a fine level of granularity. The discussion below provides a broader discussion that may refer to the aforementioned implementations and/or other implementations. EXAMPLES OF ADDITIONAL METHODS
    [00121] Figure 10 illustrates a flowchart of a technique or method 1000 that is consistent with at least some implementations of the present concepts.
    [00122] At block 1002, the method can obtain a declarative flow query in a cloud edge topology that includes multiple edge devices and cloud-based resources.
    [00123] In block 1004, the method can convert the declarative flow query into a query graph that reflects the multiple edge devices.
    [00124] In block 1006, the method can determine whether to run the query graph operators on individual edge devices or on cloud-based resources when using resources for the cloud edge topology.
    [00125] The order in which the aforementioned methods are described is not intended to be considered a limitation, and any number of the described blocks may be combined in any order to implement the method, or an alternative method. Furthermore, the method can be implemented on any suitable hardware, software, firmware, or combination thereof, so that a computing device can implement the method. In one case, the method is stored on a computer-readable storage medium as a set of instructions so that execution by a computing device causes the computing device to execute the method. CONCLUSION
    [00126] Although techniques, methods, devices, systems etc., referring to cloud edge resources and their allocation are described in a specific language for structural characteristics and/or methodological acts, it is understood that the subject defined in the attached claims does not it is necessarily limited to the specific features or acts described. Rather, specific features and acts are described as exemplary ways to implement the methods, devices, systems, etc. claimed.
    权利要求:
    Claims (11)
    [0001]
    1. Method for cloud edge topologies (1000), comprising the steps of: obtaining (1002) a declarative flow query in a cloud edge topology that includes multiple edge devices (102) and cloud-based resources (110 ); convert (1004) the declarative flow query into a query graph that reflects multiple edge devices (102) by generating a query pattern from an object representation of the query and generating the query graph using the query pattern as a model; and, characterized in that it further comprises: determining (1006) whether query graph operators should run on individual edge devices (102) or cloud-based resources (110) based on resource usage for the topology of cloud edge.
    [0002]
    2. Method (1000) according to claim 1, characterized in that the high-end computing devices (102) comprise intelligent computing devices (102) that are configured to communicate directly with cloud-based resources ( 110) across a network (106) and wherein the network (106) is misconfigured in order to allow individual smart computing devices (102) to communicate directly with each other, instead the individual smart computing devices (102) communicate with each other indirectly through cloud-based resources (110).
    [0003]
    3. Method (1000), according to claim 1 or 2, characterized in that the determination (1006) comprises determining a global optimum in relation to cloud-based resources (110) related to the use of bandwidth resources network.
    [0004]
    4. Method (1000), according to claim 3, characterized in that determining a global optimum comprises allowing nodes in the query graph to make greedy local decisions and in which local decisions, when viewed cumulatively, produce the great overall.
    [0005]
    5. System (200) for cloud edge topologies comprising a processor configured to: obtain (1002) a declarative flow query in a cloud edge topology that includes multiple edge devices (102) and cloud-based resources ( 110); convert (1004) the declarative flow query into a query graph that reflects multiple edge devices (102) by generating a query pattern from an object representation of the query and generating the query graph using the query pattern as a model; and, characterized by the fact that the processor is further configured to: determine (1006) whether query graph operators should run on individual edge devices (102) or cloud-based resources (110) based on the use of resources for cloud edge topology.
    [0006]
    6. System according to claim 5, characterized in that it comprises a cloud-based management service (202) configured to interact with an application running in the cloud (104) and on individual edge computing devices (102 ) in communication with the cloud (104), the cloud based management service (202) configured to mimic a data stream management system mechanism, DSMS, to obtain the temporal declarative stream queries from the edge computing devices individual (102); and, where the processor is configured to obtain the declarative stream query by intercepting the temporal declarative queries, and the processor is configured to convert the declarative stream query by parsing and compiling individual temporal declarative queries into an object representation.
    [0007]
    7. System (200) according to claim 6, characterized in that the processor (204) comprises a graph builder (206), and in which the graph builder is configured to convert the declarative flow query generating a query pattern (302) from the object representation.
    [0008]
    8. System (200) according to claim 7, characterized in that, in an instance where the query pattern (302) includes input streams that refer to data streams from each edge computing device (102), the graph builder (206) converts the declarative stream query by creating a query graph that includes multiple instances of the query pattern (302), dividing the data streams into multiple instances of the query pattern (302) with an input stream per edge of the query graph.
    [0009]
    9. System (200) according to claim 8, characterized in that the processor (204) comprises an optimizer (208) configured to determine where to execute individual operators of the query graph to reduce the total costs of communication between the edge computing devices (102) and cloud-based resources (110).
    [0010]
    10. System (200) according to claim 9, characterized in that the optimizer (208) is configured to determine where to execute the individual operators of the query graph to minimize the total costs of communication between the computing devices of edge (102) and cloud-based resources (110).
    [0011]
    11. System (200), according to any one of claims 6 to 10, characterized in that the processor (204) comprises a query builder (210) configured to generate representations of type objects, adapters and subqueries to be run on each edge computing device (102) or in the cloud (104).
    类似技术:
    公开号 | 公开日 | 专利标题
    BR112014016099B1|2021-04-20|method for cloud edge topologies and system for cloud edge topologies
    JP6055487B2|2016-12-27|Iterative simulation of requirement metrics for hypothesis and schema-free configuration management
    US20190318268A1|2019-10-17|Distributed machine learning at edge nodes
    US10366112B2|2019-07-30|Compiling extract, transform, and load job test data cases
    US11030002B2|2021-06-08|Optimizing simultaneous startup or modification of inter-dependent machines with specified priorities
    US10521738B2|2019-12-31|Automated collaboration workflow generation in thing-sourcing environments
    Kavoussanakis et al.2013|Bonfire: The clouds and services testbed
    CN111406255A|2020-07-10|Coordination engine blueprint aspects of hybrid cloud composition
    US20200125926A1|2020-04-23|Dynamic Batch Sizing for Inferencing of Deep Neural Networks in Resource-Constrained Environments
    US10620837B2|2020-04-14|Tuning memory across database clusters for distributed query stability
    US11163561B2|2021-11-02|Mapping components of a non-distributed environment to a distributed environment
    Menard et al.2021|Mocasin—Rapid Prototyping of Rapid Prototyping Tools: A Framework for Exploring New Approaches in Mapping Software to Heterogeneous Multi-cores
    WO2019227011A1|2019-11-28|Device for orchestrating distributed application deployment with end-to-end performance guarantee
    CN111406256A|2020-07-10|Coordination engine blueprint aspects of hybrid cloud composition
    CN111406383A|2020-07-10|Coordination engine blueprint aspects of hybrid cloud composition
    CA3099664C|2022-03-01|Cloud-edge topologies
    US20210287108A1|2021-09-16|Estimating performance and required resources from shift-left analysis
    Llorens-Carrodeguas et al.2021|An energy-friendly scheduler for edge computing systems
    US10417055B2|2019-09-17|Runtime movement of microprocess components
    Delicato et al.2017|The Activity of Resource Modelling
    同族专利:
    公开号 | 公开日
    JP6172721B2|2017-08-02|
    MX346690B|2017-03-29|
    IN2014CN04218A|2015-07-17|
    CA2859500A1|2013-07-04|
    US20150296000A1|2015-10-15|
    US9876851B2|2018-01-23|
    WO2013101563A1|2013-07-04|
    US9098344B2|2015-08-04|
    JP2015505404A|2015-02-19|
    AU2012362829A1|2014-07-17|
    EP2798512A1|2014-11-05|
    KR102008242B1|2019-08-07|
    EP2798512A4|2015-09-23|
    BR112014016099A8|2017-07-04|
    KR20140111266A|2014-09-18|
    CN103108031A|2013-05-15|
    CA2859500C|2021-01-12|
    CN103108031B|2016-08-17|
    RU2014126065A|2016-01-27|
    RU2628208C2|2017-08-15|
    US20130166712A1|2013-06-27|
    AU2012362829B2|2017-08-31|
    CA3099664A1|2013-07-04|
    BR112014016099A2|2017-06-13|
    MX2014008007A|2014-08-21|
    引用文献:
    公开号 | 申请日 | 公开日 | 申请人 | 专利标题
    US6671276B1|1997-11-18|2003-12-30|Nec Corporation|Switch based network architecture for IP multicast and integrated services|
    US6332163B1|1999-09-01|2001-12-18|Accenture, Llp|Method for providing communication services over a computer network system|
    US6578054B1|1999-10-04|2003-06-10|Microsoft Corporation|Method and system for supporting off-line mode of operation and synchronization using resource state information|
    US8463839B2|2000-03-28|2013-06-11|Cybernet Systems Corporation|Distributed computing environment|
    US6959320B2|2000-11-06|2005-10-25|Endeavors Technology, Inc.|Client-side performance optimization system for streamed applications|
    US7680916B2|2007-04-24|2010-03-16|Hyperformix, Inc.|System for improving the performance of a computer software application in a server network|
    JP5119844B2|2007-10-09|2013-01-16|沖電気工業株式会社|File transfer system, file transfer method, file transfer program, and index server|
    US8099720B2|2007-10-26|2012-01-17|Microsoft Corporation|Translating declarative models|
    US8051069B2|2008-01-02|2011-11-01|At&T Intellectual Property I, Lp|Efficient predicate prefilter for high speed data analysis|
    US8797178B2|2008-03-10|2014-08-05|Microsoft Corporation|Efficient stream sharing for multi-user sensor data collection|
    WO2009146087A1|2008-04-01|2009-12-03|Yahoo! Inc.|Open framework for integrating, associating and interacting with content objects|
    US8291006B2|2008-05-30|2012-10-16|International Business Machines Corporation|Method for generating a distributed stream processing application|
    US20100333116A1|2009-06-30|2010-12-30|Anand Prahlad|Cloud gateway system for managing data storage to cloud storage sites|
    CA3041557A1|2009-07-16|2011-01-20|Bluefin Labs, Inc.|Estimating and displaying social interest in time-based media|
    US20110072489A1|2009-09-23|2011-03-24|Gilad Parann-Nissany|Methods, devices, and media for securely utilizing a non-secured, distributed, virtualized network resource with applications to cloud-computing security and management|
    US20110126168A1|2009-11-25|2011-05-26|Crowdsource Technologies Ltd.|Cloud plarform for managing software as a service resources|
    US9106591B2|2009-12-24|2015-08-11|Delphix Corporation|Adaptive resource management using survival minimum resources for low priority consumers|
    US8806014B2|2010-03-19|2014-08-12|Novell, Inc.|Techniques for intelligent service deployment|
    US9898342B2|2010-05-14|2018-02-20|Micro Focus Software Inc.|Techniques for dynamic cloud-based edge service computing|
    CN101977242A|2010-11-16|2011-02-16|西安电子科技大学|Layered distributed cloud computing architecture and service delivery method|
    RU2435236C1|2010-12-13|2011-11-27|Государственное образовательное учреждение высшего профессионального образования "Санкт-Петербургский государственный электротехнический университет "ЛЭТИ" им. В.И. Ульянова |System and method of recording data into cloud storage|
    US9098344B2|2011-12-27|2015-08-04|Microsoft Technology Licensing, Llc|Cloud-edge topologies|US20120030343A1|2010-07-29|2012-02-02|Apple Inc.|Dynamic migration within a network storage system|
    CN103890706B|2011-10-31|2019-06-14|惠普发展公司，有限责任合伙企业|Rendering for rendering content is permitted|
    US9098344B2|2011-12-27|2015-08-04|Microsoft Technology Licensing, Llc|Cloud-edge topologies|
    US9462080B2|2012-04-27|2016-10-04|Hewlett-Packard Development Company, L.P.|Management service to manage a file|
    US20130290511A1|2012-04-27|2013-10-31|Susan Chuzhi Tu|Managing a sustainable cloud computing service|
    US9002822B2|2012-06-21|2015-04-07|Sap Se|Cost monitoring and cost-driven optimization of complex event processing system|
    EP2864903A1|2012-06-26|2015-04-29|Telefonaktiebolaget LM Ericsson |Dynamic input streams handling in dsms|
    US8856386B2|2012-08-21|2014-10-07|Cisco Technology, Inc.|Cloud resource placement using placement pivot in physical topology|
    CN103827825B|2012-09-07|2017-02-22|运软网络科技有限公司|Virtual resource object component|
    US8745261B1|2012-10-02|2014-06-03|Nextbit Systems Inc.|Optimized video streaming using cloud computing platform|
    US9106721B2|2012-10-02|2015-08-11|Nextbit Systems|Application state synchronization across multiple devices|
    GB2507338A|2012-10-26|2014-04-30|Ibm|Determining system topology graph changes in a distributed computing system|
    EP2731362A1|2012-11-08|2014-05-14|Alcatel Lucent|Configuration of electronic device|
    US9654538B1|2013-03-11|2017-05-16|DataTorrent, Inc.|Dynamic partitioning of instances in distributed streaming platform for real-time applications|
    US9769675B2|2013-03-15|2017-09-19|Hewlett Packard Enterprise Development Lp|Cloud-based connectivity|
    US8805972B1|2013-06-26|2014-08-12|Kaspersky Lab Zao|Multi-platform operational objective configurator for computing devices|
    EP3069275A4|2013-11-11|2017-04-26|Amazon Technologies, Inc.|Data stream ingestion and persistence techniques|
    US9720989B2|2013-11-11|2017-08-01|Amazon Technologies, Inc.|Dynamic partitioning techniques for data streams|
    US9553822B2|2013-11-12|2017-01-24|Microsoft Technology Licensing, Llc|Constructing virtual motherboards and virtual storage devices|
    US20160197837A1|2015-01-05|2016-07-07|L&M Ip|Method for Conveying Media to a Cloud Computing Environment|
    US9632846B2|2015-04-02|2017-04-25|Microsoft Technology Licensing, Llc|Complex event processor for historic/live/replayed data|
    US10217053B2|2015-06-23|2019-02-26|International Business Machines Corporation|Provisioning service requests in a computer system|
    US10063428B1|2015-06-30|2018-08-28|Apstra, Inc.|Selectable declarative requirement levels|
    US20170154080A1|2015-12-01|2017-06-01|Microsoft Technology Licensing, Llc|Phasing of multi-output query operators|
    US10313206B1|2015-12-23|2019-06-04|Apstra, Inc.|Verifying service status|
    US10523762B2|2016-06-30|2019-12-31|Red Hat, Inc.|Persistent real-time communication channels with cloud computing systems|
    EP3504698B1|2016-08-23|2021-05-26|Teleste Oyj|A method for providing information to information representation units|
    US20180150511A1|2016-11-29|2018-05-31|International Business Machines Corporation|Processing a data query|
    JP6891484B2|2016-12-22|2021-06-18|富士フイルムビジネスイノベーション株式会社|Equipment control system, image forming device, control device, and program|
    US10958716B2|2017-10-02|2021-03-23|Fujitsu Limited|Distributed process management system, distributed process management method for suppressing number of messages between computers, and information processing apparatus|
    US11050781B2|2017-10-11|2021-06-29|Microsoft Technology Licensing, Llc|Secure application monitoring|
    EP3698586A1|2017-10-25|2020-08-26|Huawei Technologies Co., Ltd.|Devices and methods for transforming user plane signaling from a remote sidelink control server into control plane signaling|
    US10432462B2|2018-03-05|2019-10-01|International Business Machines Corporation|Automatic selection of cut-point connections for dynamically-cut stream processing systems|
    CN109788074A|2018-03-19|2019-05-21|南京邮电大学|A kind of Edge intelligence service system|
    US20200267053A1|2019-02-15|2020-08-20|Samsung Electronics Co., Ltd.|Systems and methods for latency-aware edge computing|
    CN110022234B|2019-04-16|2022-02-22|中国人民解放军国防科技大学|Method for realizing unstructured data sharing mechanism facing edge calculation|
    JP2020198068A|2019-05-28|2020-12-10|株式会社日立製作所|Information processing system and control method of information processing system|
    US11075812B2|2019-06-20|2021-07-27|Kaloom Inc.|Server and methods for synchronizing networking information with client devices|
    US10771569B1|2019-12-13|2020-09-08|Industrial Technology Research Institute|Network communication control method of multiple edge clouds and edge computing system|
    CN111182076A|2020-01-02|2020-05-19|合肥工业大学|Cloud-edge cooperative smart power grid monitoring system and resource allocation and scheduling method thereof|
    KR20210136761A|2020-05-08|2021-11-17|삼성전자주식회사|Method and apparatus for manging information related to edge computing service|
    WO2021260970A1|2020-06-26|2021-12-30|ソニーグループ株式会社|Network control method and data processing system|
    法律状态:
    2017-12-12| B25A| Requested transfer of rights approved|Owner name: MICROSOFT TECHNOLOGY LICENSING, LLC (US) |
    2018-12-04| B06F| Objections, documents and/or translations needed after an examination request according [chapter 6.6 patent gazette]|
    2019-12-03| B06U| Preliminary requirement: requests with searches performed by other patent offices: procedure suspended [chapter 6.21 patent gazette]|
    2020-09-08| B07A| Application suspended after technical examination (opinion) [chapter 7.1 patent gazette]|
    2021-02-09| B09A| Decision: intention to grant [chapter 9.1 patent gazette]|
    2021-04-20| B16A| Patent or certificate of addition of invention granted [chapter 16.1 patent gazette]|Free format text: PRAZO DE VALIDADE: 20 (VINTE) ANOS CONTADOS A PARTIR DE 19/12/2012, OBSERVADAS AS CONDICOES LEGAIS. |
    优先权:
    申请号 | 申请日 | 专利标题
    US13/337,291|US9098344B2|2011-12-27|2011-12-27|Cloud-edge topologies|
    US13/337,291|2011-12-27|
    PCT/US2012/070427|WO2013101563A1|2011-12-27|2012-12-19|Cloud-edge topologies|
    [返回顶部]