Four color Ants optimize broker resilience


Posted on December 13, 2010  /  1 Comments

publishers, subscribers, and brokers (image taken from Bigham's ICCIA slides)

Those who know graphs theory are familiar with the “four color theorem“; an example being the world map (relaxed as a planar graph) can be colored with a minimum of four colors such that two countries sharing a border do not share the same color. Researchers at Queen Mary University of London use this theorem to color code cellular network base stations. The base stations are in abstract sense regarded as message Brokers (also termed as “Publisher Subscriber Message Oriented Middleware” – PSMOM) that channel the published message (SMS, Email, Voice packet, data packets, etc) to the Subscriber (or message recipient). Sometimes a subscriber and a publisher can be directly linked through a single broker or they may be linked through several intermediary brokers.

The role of the Sahana Alerting Broker, essentially, is similar to that of a cellular base station; where decision-maker or decision-system published risk information is disseminated to the subscribers of the response systems in the form of public warnings or restricted and private alerts (also known as closed user group alerts typically applicable to first responders). There are two downstream message distribution methods: Direct and Cascade; where direct alerting is a broker-to-person and the cascade method delivers the alerts to another broker (system); i.e. broker-to-broker. In addition, these broker, publisher, and subscriber network models would inherit one or a hybrid of the typical network topologies.

Sahana Alerting Broker subsystems (image taken from book "Biosurveillance methods and case studies", chapter 14)

Sahana Alerting Software for Real-Time Biosurveillance in India and Sri Lanka (soon available in IEEE Xplore) was the topic of my paper and presentation at the 1st International Conference on Computer and Information Applications 2010, held at the Tianjin Polytechnic University in China (Dec 03 – 05, 2010) – Click to view presentation: power point and video. It was nice to have spent some time with the keynote speaker Prof. John Bigham, Technical Advisor, School of Electronic Engineering and Computer Science, Queen Mary University of London, chatting about brokers at this event. Besides Porf. Gordon Gow, with whom I have been working on the Common Alerting Protocol (CAP) enabled Sahana Alerting Broker for the past several years, Prof. Bigham is the first person I came across who was thinking of Brokers in the same way; even though his work was more on the physical layer opposed to Sahana Alerting Broker being in the application/content layer. We both agree that there was very little research and literature available in the context of measuring Brokers for their robust-reliability, throughput associated performance, or other characteristics. This was a dilemma in working towards classifying early warning systems with the need to find ways to place a universal measure on brokers. Message brokers play an intermediary role between the decision subsystems and the response subsystems in the early warning chain of subsystems.

now back to the four color ant story … An ever present problem that pester those communications engineers is optimizing the quality of service; thus reducing characteristics like latencies (round trip time), jitter, etc (see LIRNEasia work on Broadband QoS). Another important aspect is the end-to-end resilience that comes along with crises where network nodes are broken and the are pipes blocked. You may have heard of emergency services (police, ambulance, fire-brigade, military, etc) using ad-hoc networks with multiple hops. During a crisis, the emergency services need to work within the constraints and require that the brokers (or routing agents) are smart enough to carry their traffic without disrupting their communication. The revenue generated through these priority occupants – emergency services – would be more than your’s or my personal phone call; hence, our call would get dropped in such a setting. Researchers at Queen Mary University of London choose to use a revenue penalty formula as the objective function to optimize the network routing protocols to ensure end-to-end resilience.

How does it work? Once the the base stations (or brokers) are colored then the Ant Colony Optimization (ACO) algorithm is applied to each clique of base stations with equal color to find the optimal paths within those cliques. The iterative ACO process is a technique typically used in such adaptive problems or combinatorial problem. In the broker resilience problem the best paths are those that have a lesser pheromone trail; i.e. pipes that are less congested (or blocked). The adaptive methods use semi smart antennas that cooperate in tilting or yawing to maximize the radio coverage and signal strength.

Computer scientist first developed the ACO algorithm as a solution to the typical Traveling Salesmen Problem (TSP). While the Ant algorithm is know to be slower than competing similar shortest path algorithms, but with less computational complexity, is good for tackling certain problems; such as finding the set of optimal paths for any combination of subscribers and publishers in a cellular network. These optimal strategies do not require the calculations to be executed frequently, perhaps once a day or less frequent as once a week.

The problems associated with Sahana Alerting Broker has not evolved to this level of path breaking combinatorial complexity. However, the complexities are more in CAP with the need to address multi natural language translation for quick relaying of alerts for rapid onset hazards that are constrained by very little time spans. Others challenges are more on the social and policy aspects of getting users to realize the importance and adapt such systems in developing countries. The Sahana Alerting Broker in the RTBP pilot had shown promising results to the extent the Public Health Inspectors in Sri Lanka have been frequently utilizing the system to share detected adverse public health events with targeted health officials and health workers. They also improvise the software to communicate other investigation information, otherwise would require a long bus ride for several ours to the health department to receive that information on paper, now is relayed electronically at near light speed on to their mobile phones!

1 Comment


  1. The Common Alerting Protocol work in Sri Lanka mentioned in WMO CAP video – http://www.youtube.com/watch?v=n0iKp60jjtY … we have been contributing our research to the World Meteorological Organization. Also see this video for various solutions on CAP – http://www.youtube.com/watch?v=5ELl-WiWqhk&feature=related ; But what they are taking to the military and home land security we are taking to last-mile communities.