{'fraction_non_alphanumeric': 0.030964090447014862, 'fraction_numerical': 0.007308294639668105, 'mean_word_length': 4.632621479418137, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 10, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Topic Allocation Method on Edge Servers for Latency-sensitive Notification Service

The importance of real-time notification has been growing for social services and Intelligent Transporting System (ITS). As an advanced version of Pub/Sub systems, publish-process-subscribe systems, where published messages are spooled and processed on edge servers, have been proposed to achieve data-driven intelligent notifications. In this paper, we present a system that allows a topic to be managed on multiple edge servers so that messages are processed near the publishers, even when publishers are spread over a wide area. Duplicating messages on geographically distributed servers could enable immediate notification to neighboring subscribers. However, the duplicated message spool may cause exhaustion of resources. We prepare a formal model of our publish-process-subscribe system and formulate the topic allocation as an optimization problem under the resource constraints of edge servers. As the optimization problem is NP-hard, we propose heuristics leveraging the locality and the pub/sub relationships observed between clients to use the edge server resources efficiently. Our performance evaluation shows that our method reduces the delay to deliver notifications and the effectiveness of the strategy exploiting the relationships between clients.


INTRODUCTION
In recent years, the importance of real-time notification combined with the use of data has been growing for applications such as IoT applications and Intelligent Transporting System (ITS). 1 For example, real-time decision-making services proposed in ITS are expected to react immediately to changes in traffic conditions, analyze the current conditions, and provide optimal behavior for vehicles. 2 Multi-access Edge Computing (MEC) and Pub/Sub messaging models have been exploited to generate notifications immediately, reflecting the changing spatio-temporal conditions. MEC, proposed by the European Telecommunications Standards Institute (ETSI), enables ultra-low latency and high bandwidth by geographically distributing computation and storage resources to edge servers. 3 MEC has already been applied to IoT, AR / VR, and traffic management. 1 On the other hand, Pub/Sub model can be adapted to the design of large-scale distributed systems such as MEC. 4 In particular, topic-based and content-based Pub/Sub model has been used in social interaction message notifications and event notifications among vehicles. 5,6 A more sophisticated version of Pub/Sub called publish-process-subscribe enables data-driven notifications by spooling and analyzing messages. 7 Many studies assume that one topic is managed by one server. We present a topic-based publish-process-subscribe system that allows one topic to be managed by multiple edge servers. By managing one topic at multiple edge servers, publishers can send messages to the nearby edge server which manages the message's particular topic. The server generates the notifications for the messages and delivers them to subscribers. With such a system, duplicating messages on geographically distributed servers could enable immediate notifications from publishers to neighboring subscribers.
However, due to the limited resources on edge servers, duplicating messages on numerous edge servers could cause exhaustion of storage capacity. An efficient way of using computational resources consumed by Pub/Sub brokers, which perform analysis of the streaming messages in the publish-process-subscribe paradigm, has been presented. 8 In contrast, we mainly focus on utilizing storage capacity on edge servers efficiently while enabling one topic to be managed on multiple edge servers so that the published messages are processed at nearby edge servers and the generated notifications are immediately delivered to neighboring subscribers. Note that while our scheme increases the total storage capacity needed for duplicated message spools, it does not increase the total computational cost for message processing executed in a distributed manner.
We have proposed the prototype design of our publish-process-subscribe system and conducted a preliminary experiment to show the tradeoff between network latency and the required storage capacity. 9 In this previous work, we measured the path length from publishers to subscribers and the storage capacity used on each edge server depending on the number of edge servers managing one topic. We ignored the delay caused by concentrating clients on specific servers.
In this paper, we propose a model that links the path from publishers to subscribers and estimates the consumed storage capacity and computational resources on each edge server. Based on this model, we propose a method to allocate topics on edge servers in order to achieve real-time notifications in a publish-process-subscribe system under limited resources. Currently, our scheme does not assume clients that change their location or message pattern dynamically. This paper makes the following key contributions: • We propose a delay model of the notification delivery from a publisher to subscribers and formulate the topic allocation method as an optimization problem of the delay under the resource constraints on edge servers.
• As the formulated optimization problem is NP-hard, we propose a heuristic named RELOC, which allocates topics on edge servers so that notifications can be processed at neighboring edge servers immediately. We exploit locality and topicderived relationships observed among publishers and subscribers to use storage capacity efficiently while maintaining proximity between clients and a message processor.
This paper is an extended version of previous work published in APNOMS 2020. 10 We explain the related work and the motivational case in more details, enhance the model used to represent computational resources on edge servers, and improve the RELOC algorithm and its evaluation. The remainder of this article is organized as follows: Section 2 explains related works to clarify the position of our research. The overview of our system is presented in Section 3 and Section 4 illustrates the motivation case. In Section 5, we formulate the notification delivery delay for the presented publish-process-subscribe system. In Section 6, we elaborate on our topic allocation method RELOC. Simulation results are shown to evaluate the performance of our topic method in Section 7.

RELATED WORK
Topic-based Pub/Sub systems categorize messages using topics. The messages are not directly sent from senders (called publishers) to receivers (subscribers). Instead, a broker prepared for each topic receives messages published to this topic and delivers them to the subscribers of this topic. Many Pub/Sub systems assume there is a unique broker per topic and do not support distributed broker situations. In cloud computing, scalable Pub/Sub systems are used to connect multiple servers with low latency. 11,12,13 Apache Kafka 11 , which is developed by LinkedIn, can allocate multiple brokers for each topic and supports consumer groups. Each record published to a topic is delivered to one consumer in a group. This system focuses on scalability and fault-tolerance of the distributed system but pays little attention to the geographical locality.
Publish-process-subscribe systems are an evolution of Pub/Sub mechanisms where published messages are processed before disseminating them to subscribers. Publish-process-subscribe model based real-time communication is investigated in several recent studies. 7 The message processing causes critical problems in achieving real-time notifications due to the processing load. Khare et al. present techniques to realize a scalable broker architecture that balances data publication and processing load for publish-process-subscribe systems operating at the edges, and ensures Quality-of-Service (QoS) on a per-topic basis. 8

FIGURE 1
Overview of our publish-process-subscribe system Nevertheless, many researchers focusing on efficient edge server resource use assume that one topic is managed by one edge server. Occasionally, such one-topic-to-one-edge-server architecture does not guarantee the required QoS. For example, it could take longer to deliver messages from publishers to subscribers in applications where publishers and subscribers are spread over a wide area. 14 Besides, computational load and traffic load could be concentrated when numerous publishers and subscribers are allocated to one topic. Managing a topic on multiple edge servers and brokers has the potential to achieve immediate message delivery from publisher to subscriber via their nearby edge server, as shown in Section 4. This one-topic-to-many-edge-server architecture could distribute computational load and traffic load. However, preparing message processors on multiple servers could cause storage capacity over-consumption.
Considering the limited resources of edge servers, many researches focus on proactively fetching content on edge servers to improve latency for clients to obtain content. The criteria to determine where and which content should be cached include: (1) content request probability 15,16 , where the most popular content is cached on edge servers; or (2) client mobility 17,18 , where content is cached on an edge server near the client who will request the content. In contrast, in publish-process-subscribe systems, the messages or data objects to be stored on edge servers is determined by topics and publishers/subscribers relationships. In this research, we propose an efficient use of the limited storage capacity and other resources of edge servers with adequate allocation of topics to edge servers. To the best of our knowledge, topic-allocation-based messages management on edge servers in publish-process-subscribe paradigm has not been presented before.
Some distributed storage services are proposed to offer storage service for distributed edge servers. FogStore 19,20 is a distributed data store for Fog/edge computing. It uses a distributed data store for cloud data centers as a base system, and introduces location-conscious replica placement strategy using a context (location) based index. It places some replicas on neighboring hosts to enable efficient quorum based queries, and also allocates remote replicas to provide tolerance from geographicallycorrelated failures. These works only considers the location context of data and do not support publish/subscribe relationships between remote clients. ElfStore 21 is an edge-local federated store over unreliable MEC hosts. The storage namespace has a flat set of streams, and MEC hosts can add data blocks to the streams. It features a federated indexing model using Bloom filters and differential replication scheme across edge servers, but it does not consider data processing or notifications to subscribers. Nagato et al. propose a distributed data framework in a pub/sub paradigm. 22 It allows application developers to define proactive caching rules based on pub/sub relationships, but it does not take into account resource capacity or data processing.

SYSTEM OVERVIEW
We consider a publish-process-subscribe system, where each edge server generates and transmits data-driven notifications near publishers so that immediate notifications are delivered to the nearby subscribers. FIGURE 1 presents an overview of our system, where each publisher is assigned to a single edge server which manages all the topics the publisher registers. For example, Client C publishes messages to Topic P and Q, and Edge B -the assigned server of Client B -manages both of these topics. We call the server assigned to each client the "home server." A message processor is FIGURE 2 Notification delivery flow prepared for each topic that an edge server manages. It functions as a message spooler and an analyzer of the spooled messages for a topic.
On this topic management mechanism, the system generates notifications and delivers them to subscribers as shown in FIGURE 2. When an edge server receives a message from a publisher, it spools messages in the message processor prepared for the topic. Next, the message processor analyzes the spooled messages and generates a notification. Finally, the generated notification is delivered to the subscribers. Note that, message processing is conducted only by the edge server which receives the message from the publisher. The generated notifications are either directly sent to the subscribers, or delivered via the subscribers' home server.
The home server also functions as a broker which receives messages from publishers and delivers the notifications produced by the message processors to the clients. In FIGURE 1, Edge B manages topics P and Q, that is, Edge B receives messages for topics P and Q and generate notifications for both of these topics. The notifications are then transferred to clients A and C via their home servers. In this case, Edge C has a single client which only subscribes to messages. As a consequence, it does not have any message processors.

MOTIVATIONAL CASE
In this section, we explain the motivational case of our system and discuss the advantage of the proposed system. Let us consider an application in which data is collected from pedestrians, automobiles and IoT sensors. Our system tries to generate beneficial information such as alerts using the collected data.
The FIGURE 3a shows a situation where messages containing the positions of pedestrians and automobiles are collected to a single server. Based on the collected data, our publish-process-subscribe system generate a notification. In the situation presented in FIGURE 3b, the pedestrian circled in red is suddenly leaving the building, and is in danger of being hit by the car circled in red. In such a situation, our system would generate an alert notification based on the positions of the car and the pedestrian, and deliver it to both the car and the pedestrian. After the automobile and the pedestrian receive the notification, they can both take appropriate actions to avoid an accident.
Next, let us consider a situation where multiple edge servers are deployed in the field. In FIGURE 4, an edge server is placed at each intersection, for a total of three in this area. More generally, the area is separated into three sub-areas and one topic is assigned for each sub-area. In the case of FIGURE 4a, the message and notification delivery from publishers to subscribers in the same sub-area will be faster compared to the centralized case presented in FIGURE 3. However, the system cannot generate alert notifications using messages in different sub-areas. For instance, if automobiles runs with high speed, it is better to share  To resolve this, we propose another topic allocation shown in FIGURE 4b, where one topic is assigned to all three of the edge servers in the area. The automobiles and pedestrians publish messages to the closest edge servers, while the broker which receives the messages copies them to the other edge servers. Such an allocation will triple the storage space required. However, messages and notifications delivery between publishers and subscribers in the same sub-area will be faster than the case presented in FIGURE 3 and as fast as the case presented in FIGURE 4a. Note that a server which receives a message from a publisher can utilize the spooled messages from other sub-areas to generate notifications. Notifications delay between clients in different subareas does not improve, but it makes sense to give notifications of imminent danger between clients in closer positions higher priority.
Our objective in the following sections is to investigate topic allocation to achieve minimum delay for the message and notification delivery from a publisher to subscribers, taking into account constraints such as the available storage capacity on edge servers, and the number of connections between edge servers and clients. The topic allocations shown in FIGURE 4b could achieve lower latency for notification delivery, but it is too naive to use edge server resources efficiently. Note that this example includes many mobile clients, even though our scheme does not currently care for the mobility of clients because of some reason described in Section 5.3. We will tackle these challenges in future work.
When the calculated minimum delay is lower than the application requirements, the application can operate their service as expected. Otherwise, they can obtain more storage capacity or network resource and reconfirm that their requirement is met with the best topic allocation.

SYSTEM MODEL AND PROBLEM FORMULATION
In this section, we introduce a formal model of our publish-process-subscribe system. Given an assignment of a home server to each client, the model estimates the delay in delivery of a message from the publisher via the nearby message processors to subscribers. The optimal allocation of topics under the resource constraints of edge servers is formalized as an optimization problem of the total sum of the delay.
To treat the situation where topics assigned to an edge server needs more storage capacity or computation resource than the edge server has, we introduce a delegation mechanism of message processing to the cloud server. When the assigned server of a client does not have a message processor for a topic, the published messages are forwarded to the cloud server, incurring a delay in visiting the cloud server.
In the following sections, we show the influence of topic allocation on the delivery delay within our publish-process-subscribe system model followed by a formal definition of our optimization problem.
Messages are managed on a topic basis. Let  = { 1 , 2 , ⋯ , } denote the set of all topics that have been created for the system, and  ⊆ denote the set of topics that are managed by the server . Finally, let  ⊆  denote the set of clients who are publishers or subscribers of topic and let  P , ⊆  denote the set of publishers of topic whose home server is . A topic has its own message processor that uses a message spooler of size . The size of the message spoolers for each topic is predefined to hold enough entries needed for analysis to generate notifications. If a message spooler reaches its capacity limit, it discards the oldest messages to store new ones. We introduce two resource constraints of edge servers, namely storage capacity limit and computational resource limit. Let , and denote the storage capacity limit, and the computational resource limit on server respectively. Each server cannot hold message spoolers greater than , while each edge server cannot have computational load over . Let us consider an example. The total number of spooled messages for all topics assigned to server can be expressed as ∑

∈
. The computational load to process all the topics assigned to server is denoted as . We assume that the computational load is proportional to the number of analyzed messages stored in the message spooler and the number of clients who publish messages to the topic. is calculated by

FIGURE 6
Route and process to deliver a notification to a subscriber When an edge server does not have enough capacity to spool messages for topics in or sufficient computational resource to analyze messages for topics in , the edge server cannot host the message processors of some topics anymore. Instead, it delegates the message processing to the cloud server. This situation happens when ∑ ∈ > or > . In On the other hand, 1 = 1 | P 1,1 | = 16 and 2 = 1 | P 2,1 |+ 2 | P 2,1 | = 14. As edge server 2 reaches its storage capacity 2 , 2 delegates the message processing of some topics to the cloud server.
We roughly estimate the delegation ratio of a server using the ratio of storage capacity and computation resource held by the server and the storage and computation required to process the messages locally.
This estimation may be inaccurate when considering resource fragmentation and/or the variations in frequency of message publication depending on the topics. We adopt this rough estimation because the main purpose of this model is to find the optimal topic allocation. Our model focuses on accurately estimating the delays depending on topic allocation in situations where delegation seldom occurs.

Route for notification delivery
In this section, we formalize the delay between a message being sent and the notification being delivered, which we denote , considering the constraints of and . Let C denote the network delay between any of the edge servers and the cloud server. We use the same value for all the edge servers. The delay in the path between a client and its home server is denoted by H , . The delay in the path between servers and ′ is denoted by S , ′ . These values are determined by the network distance between the locations of both servers. In the performance evaluation in section 7, we use the Euclidian distance instead of the network distance. We assume C is much larger than H , or S , ′ . FIGURE 6 shows the route and process from publication of a message by a publisher , until the subscriber ′ receives the corresponding notification. (a) corresponds to the case where the message for the target topic is not delegated. The home server of publisher is , and the home server of subscriber ′ is ′ . (b) illustrates the case where the message processing is delegated to a cloud server. In case of (a), equals to H , + S , ′ + H ′ , ′ . In case of (b), equals to H , + 2 C + H ′ , ′ .

Problem formulation
The strategy of the optimization problem is denoted by a binary matrix = { , | ∈ , ∈ }. If 's home server is , , = 1, otherwise , = 0. Our objective is to find the optimal that minimizes the sum of the delay. Keeping the ratio high and the value H , small is incompatible. When the publishers of the same topic are assigned to many edge servers, H , will be small. However, the duplication of message processors increase the value of ∑ ∈ and in Equation 2. We have to take care not to concentrate topic allocations on any edge server to avoid capacity overflows. Due to this trade-off, we try to find an optimal strategy under the given capacity constraints by formulating the problem mathematically. Given message publications, we obtain an optimization problem which consists in adapting the topic assignment to edge servers to minimize the delay between message publication and notification delivery.  denotes a set that only includes the publisher of the -th message publication | | = 1 and the  denotes the set of subscribes of -th publication (| | ≥ 1). We define the following optimization problem: In Equation 6, only when = 1 (which means the edge server has enough capacity and computational resource to hold all the message processors of the topics it manages) does 1 − becomes 0, otherwise 2 C is added under the probability 1 − . Similarly, S , ′ is added under the probability . The optimization problem is NP-Hard because it is a kind of set partitioning problem. 23 Therefore, we develop heuristics based on an analysis of the formulated optimization problem.
Our system assumes that we know pub/sub communication patterns before solving the optimal assignments of home servers. This assumption may be satisfied if the targets are unrelocatable IoT sensor devices that periodically send signals. On the other hand, if you want to apply this scheme to mobile agents, you may need to solve optimization problems periodically based on recent communication patterns. Moreover, we have to take care of relocating message processors as publishers move. We will tackle these challenges in future work.

RELOC ALGORITHM
We develop a heuristic named RELOC (RElation and LOcality conscious Cooperative client assignment), which determines a topic-allocation strategy which reduces the delay between message submission and notification delivery , resolving the trade-off between and H , . RELOC exploits notable features of publishers and subscribers, namely locality and topic-derived relationships.
Initially, RELOC divides the field into clusters based on the position of edge servers using the -means clustering algorithm. A client is only assigned to a server which belongs to the closest cluster so that the delay between the client and its home server H , is reduced. The number of clusters is given in advance according to the strength of locality in client distribution. For example, in an application where publishers and subscribers are close together, we set larger to more finely divide the field. Adequate values are investigated in Section 7.
Secondly, RELOC assigns publishers who have strong relationships to the same edge server. This helps reducing storage capacity consumption by using the same message processor to handle the topic to which these multiple publishers submit messages to. Initially, we prepare a list of publishers and subscribers for each topic (i.e.  1 ,  2 , ⋯ ,  ) from the given pub/sub communication pattern. Next, RELOC makes the matrix = { , ′ | , ′ ∈ }, where , ′ represents the number of times that both clients and ′ are publishers/subscribers to the same topic (i.e. ∈  ∩ ′ ∈  ). , ′ is the number of topics such that ∈  ∩ ′ ∈  . After that, RELOC obtains the set of clients who have the strongest relationship with each other by adapting a matrix factorization technique 24 to . Note that publishers located in different clusters are not assigned to the same server even if they have a strong relationship. Thus, RELOC can keep the distance between publishers and their home servers small within a cluster, while reducing the storage capacity consumption on the edge servers by assigning publishers who have strong relationships to the same edge server.
Finally, RELOC assign home servers to clients in order, taking into account the current resource usage of each edge server which is represented by . If a resource on the client 's home server is exhausted (i.e. < 1) as a result of placing a new message processor for topic on that server, a new home server ′ is assigned to client . The topics that the client

FIGURE 7
Arranged dataset of user_sns.txt publishes to are copied to this new home server. RELOC then reassigns all the publishers to this topic from edge server to this new edge server ′ . If there are no longer any clients who publish to a topic managed by server (i.e.  P , = ), RELOC removes this topic from this server.
The overall operation of RELOC is presented in Algorithm 1. The RELOC assigns home server to all clients ∈ , where  =  1 ∪  2 ∪ ⋯ ∪  .

locality conscious:
In Line 17, the field with multiple edge servers is divided into clusters using the -means clustering algorithm.

relation conscious:
In Line 19, the set of clients who have the strongest relationship are obtained. In Line 22, ′ clients who have the strongest relationship with are stored in  ′ . A home server is temporarily selected from servers which belong to the same cluster as and satisfies = 1. If extracted clients include a client who belongs to the same cluster as , is updated to index of the extracted user's home server. In Line 32, RELOC update and update server states  ,  P , as well as . 3. cooperation: If a resource on the home server of client is exhausted (i.e. < 1) after updating , a new home server is assigned to client in Line 38. Topics that the client publishes (i.e. ′ ) are copied to the new home server in Line 4. In Line 11, if all ∈  P , have been assigned to a new home server (i.e.  P , = ), then RELOC removes the topic and update ′ and ′ .

SIMULATION
In this section, we observe topic allocation conducted by RELOC algorithm, and evaluate the notification delivery delay given by the home server assignment conducted by RELOC.
We obtain a list of topics and publishers/subscribers for each topic from a real-world social network dataset (user_sns.txt) provided by Tencent Inc. 25 We group Followee-userid by Follower-userid and make the arranged dataset, where each line includes a follower and her/his followees as shown in FIGURE 7. We extract lines from the arranged dataset and assign a topic to each line. Besides, we regard a follower and her/his followees in each line as publishers and subscribers of the assigned topic as shown in FIGURE 8. In From the obtained list of topics and publishers/subscribers for each topic, the set of topics  can be expressed as  = { 1 , 2 , ⋯ , }, while the set of clients  can be expressed as  = 1 ∪ 2 ∪ ⋯ ∪ . We distribute the clients ∈  to a 25 km square field, where publishers/subscriber of the same topic (i.e. ∈ ) follows a Gaussian distribution with a standard deviation of km centered on a randomly chosen point in the field. Also, edge servers are placed in this field. FIGURE 9 shows examples of client distribution, where points represents clients. Two clients connected by an edge are publishers/subscribers of the same topic. The left figure shows the case that ∩  ′ ≠ for some , ′ ∈  , while the right figure shows the case that  ∩  ′ = for all , ′ ∈  .

Algorithm 1 RELOC:home server assignment to clients
Require: The set of all topics  ; the size of message spooler of each topic ; storage capacity limit ; computational load limit ; The sets of clients who publish or subscribe to topic 1 , 2 , ⋯; (i.e.  1 ,  2 , ⋯,  ); the number of clusters ; the number of extracted clients who have the strong relationship ′ Ensure: home server assignment strategy 1: function COOPERATION( , ′ , , ′ ) 2: for in ′ do 3: if not in then 4: Add to  5: end if 6: Add to  P , and update using the updated  ,  P , 7: Remove from  P , ′ and update ′ using the updated  P , ′ 8: end for 9: for in ′ do 10: if | , ′ | = 0 then 11: Remove from ′ and update ′ using the updated  ′

12:
end if 13: end for 14: end function 15: 16: Initialize by = 0 17: Divide field to clusters. 18: Makes a matrix based on  1 ,  2 , ⋯,  19: Adapt matrix factorization to and obtain the set of clients who have the strongest relationship with each other 20: for in  do 21: for in  do 22:  ′ ← ′ clients who have the strongest relation with 23: : the home server of ← the server that satisfies = 1 and belongs to the same cluster as (initial value) 24: for ′ in  ′ do 25: if ′ (home server of ′ ) and client belongs to the same cluster then 26:

Preliminary evaluation
As a preliminary evaluation, we observe a home server assignment determined by RELOC in a simple case. RELOC determines home servers of clients by Algorithm 1 based on , { 1 ,  2 , ⋯,  }, the size of message spooler of each topic , storage capacity limit , computational load limit , the number of clusters and the number of extracted clients who have the strong relationship ′ .
For sake of simplicity, let 1 = 2 = ⋯ = = and 1 = 2 = ⋯ = = , in the following sections. Besides, all ∈ can take a role of publishers and subscribers. This means that all clients publishes messages to their home server while receiving notification from their home server. On top of that, let us represent by = | |, which means that the message processor of topic can spool messages published by a client on average. For example, if | | = 7 and = 2, the message processor of topic can hold 2| | = 14 messages. FIGURE 10 shows the result of home server assignment to clients by each step of RELOC, namely locality conscious, relation conscious, and cooperation. The values of constants given in this simulation is shown in TABLE 1.

Performance Evaluation
We compare the performance of RELOC with 3 assignment methods, namely Random Assignment (RA), the Nearest Server assignment (NS), and One-Topic-One-Server-assignment (OTOS). RA assigns home servers to clients randomly, while NS assigns the closest server to client. OTOS allocates one topic to one server, whereas RELOC allocates one topic to multiple  servers. Note that OTOS does not work when a client is a publisher/subscriber of multiple topic such as a case shown in the right figure of FIGURE 9. Therefore, we apply cooperation mechanism to OTOS to prevent concentration of resource consumption.  Next, we conduct | | times notification deliveries for each topic ∈  , where the set of publishers is and the set of as other clients in for each ∈ . Thus, message publication and notification delivery to subscribers is conducted = ∑ ∈ | | times in total.
1 is the delay caused by distance, while 2 is the delay caused by resource consumption. In this simulation, we represent H , by where is delay per a kilometer , is the geographical distance between a client and her/his home server . In this simulation we set by = 0.1 ms. FIGURE 14 shows storage capacity usage, computational load, and distance between clients and their home server as well as average delivery delay , 1 and 2 against locality of clients . All graph represents the average, and the band shown in the above three graph illustrates the 95% confidential interval. From FIGURE 14, we can observe that RELOC has the smallest delay to deliver notifications to clients if ≥ 5. NS gives the smallest distance H , , but NS gives delay 2 as the value of increases. When there is sufficient capacity, NS method may be the best method. OTOS gives the smallest storage capacity consumption, but it gives more delay 1 than RELOC constantly. The black line in the graphs that show used capacity and computational load is and respectively. When applying RELOC, the storage capacity is not over even when locality increases. This implies that the total storage consumption is reduced by relation conscious step and storage capacity consumption is adjusted among edge servers by transferring message processors to servers which are not heavily used by cooperation step. FIGURE 15 shows storage capacity usage, computational load, and distance between clients and their home server as well as average delivery delay , 1 and 2 against the average size of message spooler for each topic | |. From FIGURE 15, we can observe that RELOC has the smallest delay to deliver notifications to clients. Even when used capacity and computational load is over the constraint and after relation conscious step, the increase of average delivery delay is small by virtue of cooperation step.

FIGURE 14
Comparing storage capacity usage, computational load, and distance between clients and their home server as well as average delivery delay , 1 and 2 of RA, NS, OTOS, and RELOC against locality of clients ( = 2, = 4).

FIGURE 15
Comparing storage capacity usage, computational load, and distance between clients and their home server as well as average delivery delay , 1 and 2 of RA, NS, OTOS, and RELOC against average size of spoolers ( = 5, = 4) Finally, we investigate the adequate number of clusters . FIGURE 16 shows storage capacity usage, computational load, and distance between clients and their home server as well as average delivery delay , 1 and 2 against the number of clusters . From FIGURE 16, when locality = 10, 15, 20, though the average delivery delay fluctuates depending on the number of clusters , the average delivery delay does not vary so much. On the other hand, when locality is small, that is = 1, 5, the delay is minimized by increasing the value of .

CONCLUSION
In this paper, we presented a publish-process-subscribe system that allows messages published to a topic to be immediately processed by distributed message processors on edge servers. We formulated the delay caused by excessive edge server resource

FIGURE 16
Comparing storage capacity usage, computational load, and distance between clients and their home server as well as average delivery delay , 1 and 2 of RELOC against the number of clusters ( = 2, method: RELOC) to find the optimized allocation of topics on edge servers. Numerical experiments show that our heuristics constructed with an analysis of the formulated optimization problem give an efficient use of edge server resources and reduce the message and notification delivery delay.
Future work involves comparing results by the optimal solution and heuristic solution, considering how to determine adequately in Algorithm 1 exploiting several features of application users such as locality and mobility, and investigating time complexity and execution frequency to confirm that RELOC can be deployed to real environments.