Performance Analysis on Destination Driven Multicast Routing Algorithm

Cheru Haile¹, Yimer Amedie¹, Yimenu Atinaf²

¹Department of Information Technology, Assosa University, Assosa, Ethiopia.
²Ethiotelecom IT Operation and Maintenance Supervisor, Assosa, Ethiopia.

DOI: 10.4236/jcc.2022.102004                

Abstract

The internet’s architecture today has a problem in routing information depending on what the receiver is interested in without knowing the sender and receiver addresses. As a result, the Publish-Subscribe paradigm was developed. In this network, we build and use in the design, implementation, and evaluation of Publish-Subscribe network via destination driven multicast routing algorithm for selecting the shortest path in the network. Basically, the networks have Router to perform routing mechanism, the publisher is the producer of information, and the subscriber is the consumer of information with their own deferent type of module for facilitating their function. Every connection in the network is bidirectional way of communication (an undirected graph) with random seed available in the network. Each Router has topology management module for creating a picture of the networks and computing the available path. It informs to the forwarder in order to send the information of network for intended receiver. Record table module used for recording of the network information comes from the subscriber or the publisher via link state advertisement then it informs to the topology manager. In this network, the receiver and sender don’t expect to be active at the same time, don’t know each other’s addresses, and don’t use any blocking mechanisms or client send requests and server replay responses. The Publish-Subscribe network is first developed and designed enough, after which it is implemented and evaluated using the destination driven multicast routing algorithm (DDMC) to pick the shortest path in the network and active match published information. The proposed work evaluated via total bit (produced 1,000,000 bit per second), and throughput was 83.33%.

Keywords

Publish-Subscribe, DDMC, Link State

1. Introduction

Publish-Subscribe means the client can be the producer of information or consumer of information in the system with the publisher and the subscriber information. That means each node does not expect to know each other as well as be active at the same time without blocking each other. Consumers can have multiple active subscriptions, and after a client has issued a subscription the notification service delivers all produced information that match the subscription then it can notify that is published by any producer until the client cancels the respective subscription [1].

Most researches deal with Publish-Subscribe on fixed network internet connection due to the IP multicast. But IP multicast and IP based SMS needs more infrastructure facility to perform the activity, so Publish-Subscribe is good for addressing this problem. For example [2] developed internet based distributed system through Publish-Subscribe to support large numbers of topics with a large number of subscribers per topic. It is developed on the top of pastry and multicast trees that are created by the reverse path forwarding approach [3].

A-TOPSS [4] is Content-Based system via approximate matching that allowed the expression of vagueness in the system. It consists two approximate ways namely the fuzzy set theory and probability theory, each triple consist attribute, operator, and value.

[5] introduced a type-based event notification middleware on the distributed system for the large scale internet, which uses rendezvous node known as special event broker, its functionality is the meeting point and know the publisher as well as a subscriber to deliver the message to the intended one.

According to [6] mobility handoff categorized into two; namely proactive handoff and reactive handoff. The first one deal with the extension of proxy to store the message of the publisher during the disconnection of the client and after reconnecting the message will be delivered to the client. If the client is connected to the new broker, it used state transfer protocol to forward the stored message from the old one to the new one and most of the middleware and Publish-Subscribe system is based on it. The proactive approach use dummy activated or deactivated on the proxy broker as well as neighbor. When the client disconnected, the broker created a dummy to buffer message and also notify all neighbor broker. The client connected to the new broker, the proxy noticed to the client and informs to the other broker to deactivate or removed the message store on the dummy.

Distinguished of two different of client mobility [7]; 1) proclaimed move: the client has informed its new broker destination before disconnected. The old broker responsible was to send migration subscription message to the next hop by a filtered neighbor broker, its duty was to create a temporal queue to store the subscription and added to filter table then send it. When it delivered to the required broker, it sends subscription migration acknowledged message back in order to delete the temporal queue in its filter table. 2) Silent move: the client disconnected without informing to the broker. After reconnected the client to the new broker, it created a persistent queue to store the subscriptions’ then sent handoff request message to the old broker with its identifier, client identifier, and old broker identifier. The old broker was sent subscription migration message to the new broker without created of the temporal queue in the next hop of the broker.

The topology management is a basic issue on different network area just like MANET (Mobile Ad-hoc Network) [8]. In mobile ad hoc network, all the nodes have the behaviors of mobility so it is difficult to get a stable route in the network and stable topology. There are two approaches structured and unstructured for multicast in MANET which is suitable for low and fast mobility respectively.

The above loosely couple property of Publish-Subscribe makes the system highly useful and practical for many real-world message distribution scenarios. Examples of such Publish-Subscribe systems could be a mailing list notification, RSS feeds, news updates, a stock market, and weather updates. According to [9] all Publish-Subscribe systems have basically three main things which are; Client (the publisher or subscriber) its main aim is either publish the message or consume the information, infrastructure, and link (the brokers and the interfaces connected with), and the service that the system provided.

Publishers and subscribers communicate only within a single broker that is directly connected with service, Publish-Subscribe systems basically have:

1) Publisher: is a producer of information for the consumer.

2) Subscriber: is a consumer of information that can get notification based on the subscription they are interested in.

3) Broker: it has basically three main functions in the system. Those are:

· Supplies all the subscriptions interest of subscribers

· Receives all the message from publishers and

· Send the published message to the correct subscribers via the correct path.

The result is that publishers and subscribers exchange information without directly knowing each other. Publish-Subscribe systems are then an anonymous, many-to-many, asynchronous communication paradigm, where multiple producers may propagate information to multiple consumers. Anonymity is an effective solution to easily get scalability at abstraction level. Participants do not have to know each other and when the size of the system grows, they still have to contact only the Notification Service. For more clarification see Figure 1 of Publish-Subscribe architecture that varies connectivity of broker from one to other based on the design issue.

Developing selective notification Middleware that use to implement content based subscription system which is used just like emergency service in smart cities. Developing mobile application using MQTT protocol with publish subscribe broker to efficient data dissemination methods with compressed data in smartphone via shared dictionary compression mechanism [9]. Design a system use named data network for selecting and subscribe method to match and fetch

Where S = Subscriber; P = Publisher; B1-7 = Brokers that are Publish-Subscribes router or Router.

Figure 1. Proposed architecture of publish-subscriber.

address on publish subscribe [10]. According to [11] use dynamic destination based routing algorithm with MERC to improve scalability on publish subscribe based on cluster and content based mechanism on the PADRES system. In wireless sensor network scalability and reliability is the basic issue but [12] use virtual broker for communication to improve scalability and reliability in large scale of publish subscribe.

This research is similar to intra-domain topology manager in Publish-Subscribe network [10] in the case of topology manager function. However, the rest of the modules function and connectivity’s of the modules in Publish-Subscribe paradigms are totally different. For example, in intra-topology manager, the connectivity helper module is used in the local area network to discover connectivity of the node in the network. In the case of our study work, use Link-state monitor which runs in each node to administer the link in the network and it used to inform Publish-Subscribe routers or nodes via link state advertisement.

According to [11] DDMC algorithm achieved good performance when compared with Dijkstra algorithm in large numbers of client participate in publish subscribe network. However, the active matching, amount of published, amount of subscriptions, and end-to-end delay in the network did not considered. So that this study have an ability to fill the above problem using of DDMC routing algorithm.

2. System Description

In the Publish-Subscribe system, information is produced by publishers and consumed by subscribers, while none of them has any knowledge of the each other’s existence. The data sent through the network, pass from a number of other network elements that determine the correct path they should follow. The system consists the clients (publishers and subscribers) and infrastructure in the cyclic distribute topology style with the messages are delivered in the form of FIFO (First in First out) order in topology manager module.

The basic problem of cyclic topology in the Publish-Subscribe network is creating a loop of message routing in the network. So that it can make the system busy and malfunction of the Publish-Subscribe by the reason of looping message in the system. In order to minimize the loop of message and find the optimal path in the network boost library in C++ is used.

Figure 2 below illustrated that the overall communication steps in the network. In other hand, Subscriber information can be routed through link state advertisement to the record table via subscription mechanism. In the other hand, publisher can produce information to the notification service. Now the record table responsibility is to record the publisher and subscriber information and inform to the topology manager if there is matching of information and disconnection of node is available in the network. Topology manager is used in order to compute the path and create the network picture in the system. Then it sends the information to the forwarder. The basic responsibility of the forwarder is receiving information from topology manager and send to the client based on the information received from topology manager. All information flow in the system has its own identification. The number in the flow chart indicates the step of flow information.

The study adopted Destination Driven Multicast routing algorithm in order to select the shortest path in the given of generic connectivity of Publish-Subscribe network. This algorithm [12] developed for a fundamental issue in multicast communication for transmitting message in the network to determine an efficient message route in the given of Publish-Subscribe network.

The algorithm idea puts as follow [12]; the network use undirected graph G = (V, E) where V is a set of host or route nodes and E is the set of communication links. Assume that the cost of the link is c(u, u) is nonnegative for each link $\left(u,u\right)\in V$ . Source and a set of destinations is $D\subset V$ such that $s\notin D$ , graph G whose root is s, which contains all nodes from D, and whose leaves consist of nodes from D. Note that s needs not be the only sender; since this algorithm produces a shared multicast tree, any member of $s\cup D$ will transmit using this same tree. Definition: Given a set $D\subset V$ , the indicator function Id: $\text{V}\mapsto \{0,1\}$ of D is defined as Id $\left(u\right)=0$ , if $u\in D$ , and 1 if $u\notin D$ .

Figure 2. Way of communication in the network.

3. Result and Discussion

To implement the study, different range of router and clients used randomly generated by the node running on the OMNeT++ simulation environment with INET framework. The simulation has basically the following parameters in order to fulfill Publish-Subscribe function.

1) Publication: A self-contained data unit that has been made available using publishes primitive. The main aim of the publisher is to produce or create information then it sends to the nearest Router or base station. Therefore, the publisher node has only a MAC (medium access control) and application layer which means there is no other network protocol and IP (internet protocol) directly used for publishing and transmits the packet to the record table in the network.

If the number of publisher increases in the network, it also increases the link state advertisement (LSA) in the network. This reason leads the function of topology manager becomes busy to computing and selecting a path, so it takes more time to publish a message on the proposed or nearest Publish-Subscribe Router. After topology manager received information and computing path finished then it becomes free until it receives new publication and subscription in the network.

2) Subscription: numbers of request send from subscribers in order to consume the produced information based on user interested in via subscription mechanism. This function is the subscriber node that has only MAC (medium access control) and application layer which means there is no other network protocol and IP (internet protocol) directly used just like publisher node.

If a number of subscriber increase in the network, it leads to increase link state advertisement in the network. All the communication in the network is based on the link information update via advertisement. In other word, the number of client’s participant in the network increase which leads to increase the link in the network, so that all the subscribers send their interest to the nearest Publish-Subscribe router via subscription. The record table sends the match information to the topology manager in order to compute and select the shortest path in the network. Finally it sends the information to the forwarder in order to sends the information to the interested receiver.

3) Active match of the publication with subscription: in the Publish-Subscribe paradigm a large number of information are produce and consume. Based on this information the record table has the ability to inform the topology manager if matching information is available in the network. So Figure 3 shows that the amount of link matching in the network.

4) End-to-end delay: The time delay for the packet from the publisher to the subscriber. The bit rate has a close connection with the end-to-end delay of the packets. The more congested the network is, not only the more packets get discarded, but the more time it takes for the non-discarded ones to reach their destination. Mathematically can express as below;

$\text{End-to-enddelay}={\text{Time}}_{\text{packetArrivedSubscriber}}-{\text{Time\_Packet\_Transmited}}_{\text{Publisher}}$ (1)

As Figure 4 in the below illustrated that total numbers of bits that generate in the network by producer and subscribers at the given of simulation time. However, all the bits cannot correctly receive by the subscriber because some of them do not match with the producer information and delay of bits available.

As Figure 5 illustrated the numbers of bit send by publishers and subscribers as well as subscribers receive bits which are correctly deliver to the subscriber based on their interested in.

Figure 6 illustrate that the end-to-end delay of destination driven algorithm with maximum, minimum, mean, and standard deviation with creating and finding of topology in the given of network introduced a delay in the Publish-Subscribe paradigm for sending and receiving of information among the numbers of clients and infrastructures increase in the network. Introducing a delay leads

Figure 3. Performance of DDMC algorithm.

Figure 4. Total bits in generated.

Figure 5. DDMC receive and sent bits per second.

Figure 6. End-to-end delay in each nodes.

to getting message latency of link state advertisement in the network starting from publisher to the subscriber. Observe that again, the average end-to-end delay increase greatly after the bit rate go over a certain limit. For example, how the number of the router would affect the number of traffic allowed to flow through the network. The sum and the average of the bytes sent by each publisher and the ones received by each subscriber are depicted for various numbers of nodes in the network.

5) Throughput: the amount of information that received correctly from one node to another node divide by the total time takes in the simulation. The measurement of throughput is bit per second, Mathematical can express

$\text{Throughput}=\frac{\text{number of deliver LSA}}{\text{total time}}$ (2)

As Figure 7 below illustrated that total throughput in the network. The number of delivered link state advertisement from the publisher to the subscriber with its total time it takes to reach in the subscriber. DDMC has an ability to replica ones publisher information from one publisher to interested subscriber exist in the network. So this behavior plays a great role to increase the throughput in the network.

Below Figure 8 show that the average throughput in the network with each of the Publish-Subscribe router available in the topology. Each router has its own number of participants. These participants increase in numbers can affect performance of each router. So this figure try to show each of router has average throughput in the network with increase number of participant in the network.

4. Conclusions

Nowadays, there are projects for designing new internet architecture for routing of information in the form of publishes-subscribes paradigms. From these projects, 1) PSRIP: its basic aim is to redesign the internet architecture to Publish-Subscribe

Figure 7. Throughput in the network.

Figure 8. Average throughput of each node in the network.

paradigm with routing internet protocol. 2) PURSUIT project: The main goal of the project is to redesign the current internet architecture that suitable for the internet on publishes subscribe paradigm. Information can exchange one with other by means of receiver oriented via Publish-Subscribe communication. In recent times, with the rise of mobile devices as well as progress in wireless communication, ad hoc networking is gaining importance with the increasing number of widespread applications.

Based on the above idea, this study has the topology management in the large Publish Subscribe networks and develops a different type of modules that relying on the form of Publish Subscribe model. In the network, there are clients that utilize whether a publisher or subscriber for information exchange with infrastructure that deals with connecting of one Router with other in the network with the matching of information based on the incoming link state advertisement. In this study, to find shortest path with low cost, we use DDMC algorithm in the topology management module.

The obtained results are introduced by a large number of clients participates in publishing and subscription in the network also it takes high time to perform the matching activity and computing the path in the network. Different improvements to the current topology management implementation can be introduced as discusses above, leading to more efficient topology creation. So based on our work, we recommended strongly DDMC can be used to farther used in self-organized nodes to find the image of the network as well as to select shortest path in the network.

Acknowledgements

Evidently, we have to thank our colleagues, Mr. Tesfaye Tadele, Mr. Kassahun Geresu, Mr. Haile Tesfay, and Mr. Solomon Aregawi, for the opportunity to collaborate and learn from them. Working with them has provided me the opportunity to broaden the spectrum of my research and assisted me in growing as my academic.

Author’s Contributions

Cheru Haile: Proposing the idea, collecting and analyzing necessary resources, developing the system and writing the manuscript.

Yimenu Atinaf: Design the network infrastructure and analysis the impact of the network in different angle.

Yimer Amedie: Collecting part of the resources, editing and reviewing the manuscript.

Conflicts of Interest

The authors declare no conflicts of interest regarding the publication of this paper.

References

[1]	Mühl, G. (2002) Large-Scale Content-Based Publish/Subscribe Systems. Unpubl. Dr. Diss. Darmstadt Univ. Technol, 1333-1366.
[2]	Rowstron, A., et al. (2001) SCRIBE: The Design of a Large-Scale Event Notification Infrastructure. Lecture Notes in Computer Science, Vol. 2233, Springer, Berlin, Heidelberg.
[3]	Banavar, G., et al. (1999) An Efficient Multicast Protocol for Content-Based Publish-Subscribe Systems. Proceedings of the 19th IEEE International Conference on Distributed Computing Systems, Austin, 5 June 1999.
[4]	Liu, H.F. and Jacobsen, H.-A. (2002) A-TOPSS—A Publish/Subscribe System Supporting Approximate Matching. Proceedings of the 28th International Conference on Very Large Databases, Hong Kong, 20-23 August 2002, 1107-1110.
[5]	Pietzuch, P.R. and Bacon, J. (2002) Hermes: A Distributed Event-Based Middleware Architecture. Proceedings of the 22nd International Conference on Distributed Computing Systems Workshops, Vienna.
[6]	Gaddah, A. and Kunz, T. (2008) Subscriber Mobility in Pub/Sub Systems: Pro-Active vs. Reactive Handoffs. Wireless and Mobile Computing, Networking and Communications, Avignon, 12-14 October 2008.
[7]	Wang, J.L., et al. (2007) MHH: A Novel Protocol for Mobility Management in Publish/Subscribe Systems. International Conference on Parallel Processing, Xi’an, 10-14 September 2007.
[8]	Mocito, J., et al. (2011) Topology Stability-Aware Multicast Protocol for MANETs. IEEE 36th Conference on Local Computer Networks, Bonn, 4-7 October 2011.
[9]	Chand, R. and Felber, P. (2004) XNET: A Reliable Content-Based Publish/Subscribe System. Proceedings of the 23rd IEEE International Symposium on Reliable Distributed Systems, Florianopolis, 18-20 October 2004.
[10]	Gajic, B., et al. (2011) Intra-Domain Topology Manager for Publish-Subscribe Networks. 18th International Conference on Telecommunications, Ayia Napa, 8-11 May 2011.
[11]	Haile, C., et al. (2020) Comparison of DDMC and Dijkstra Algorism on Topology Management in Large Publish-Subscribe Paradigm. International Journal of Networks and Communications, 10, 41-46.
[12]	Shaikh, A. and Shin, K. (1997) Destination-Driven Routing for Low-Cost Multicast. IEEE Journal on Selected Areas in Communications, 15, 373-381. https://doi.org/10.1109/49.564135