Compact Self-Healing and Routing Over Low Memory Nodes (COSHER)

Lead Research Organisation: Loughborough University
Department Name: Computer Science

Abstract

Computer Networks have permeated every sphere of our lives. For example, the Internet has almost instantaneously taken over global communications and networks now pervade every part of our professional, personal and social life. A major part of this revolution is computing devices coming together in an ad-hoc manner in the form of Peer-to-Peer (P2P) overlay networks. A good example is the digital currency Bitcoin built upon P2P technology. The next step in this revolution is the Internet of Things (IOT) which will involve everyday objects of our use fitted with small low memory sensors communicating with each other forming adhoc Peer-to-Peer networks. Such networks will also be highly dynamic with frequent additions, removals or failures of nodes.
In this scenario, my project will initiate research into the development of fault-tolerant routing for such large scale networks of devices with low memory. We plan to achieve this by developing mathematically rigorous novel compact self-healing routing distributed algorithms leveraging the intense research done in previous years in compact routing and in self-healing algorithms.

Self-healing is a paradigm for reconfigurable networks that restores the global state of a network by only local changes following an adversarial attack, and allows us to deal with node removals or additions. Routing is the essential requirement in any network of being able to transport packets of data from sender node(s) to receiver node(s) often using packet headers and routing tables on intermediate nodes. Compact routing attempts to make routing scalable for large networks by minimising the space requirements at the cost of some additional delay in delivery (this is called 'stretch'). In this proposal, I plan to design a series of self-healing compact routing algorithms for nodes with low memory. These algorithms shall be mathematically analysed and bench-tested for accuracy and efficiency (in terms of time, space and message complexities).

I will actively disseminate our algorithms and generate increased scientific interest in Queen's, the larger academic community and the general public towards this line of work. Success in development of such algorithms will have significant impact down the line in development of such technologies and contribute towards preparing the UK for technologies such as IOT.

Planned Impact

The project has significant potential impact in the short, medium and long term. This project uses mathematical and theoretical tools to address a challenging problem for present and future days network: that of sending messages in a network despite failures of members/components of that network. The project is relavant to many of EPSRC's research areas and themes such as the ICT Networks and Distributed Systems (ICT/Global Uncertainities/Digital Economy), Working together and Maths of Computing.

Impact will be achieved by activities such as training, publications, participation in meetings/conferences/fairs/forums, student projects, demonstrations, websites, social platforms and engagement with policy planners and advisors. The impact can be classified into the following categories with the given timeframes:

i) Impact on individuals (< 5 years):
- PI: The project shall help the PI cement his research credentials and achieve a more secure (post-probation) position in the UK academia.
-PDRA: Shall be most directly impacted. PDRA shall receive significant scientific, professional and managerial training during the course of the project from the research, interaction with the PI and specialised training from QUB and the Royal Society (Communications course).
- QUB and UK students: These shall benefit from resultant UG/PG projects and dissemination activities at local/national level (Open days/national seminars).
- UK/International academics: The project shall advance the state of art and disseminate in international conferences.

ii) Organisations (2 - 10 years):

- Industry: The project will propose solutions at a higher/theoretical level (for a seminal problem) which takes time to be adapted/adopted/implemented for industrial use. At the same time, the resultant fan out ensures a much higher impact than a single tailor made solution. The project impacts areas such as large scale networks and Internet of Things which will see wide adoption by industry ranging from Computing (Google, facebook etc) to electricity and power to automobiles. Solutions based on our results may potentially be adopted by any or all of them.

- Government (planning): The project shall maintain already established contact with government agencies such as RaISe (Northern Ireland) and POST (Westminster); agencies which are assisting in research planning and adoption of future technologies. This shall assist in maximising the impact across organisations and general public.

iii) General public (> 5 years): Technologies already in use and those to be adopted in near future (such as IOT) will be potentially impacted; this will benefit everyday life. Possible adaptation of concepts into text book and curricula will have lasting impact. Dissemination and outreach activities (such as open days/demonstrations etc) shall influence the next generation of students.

The 'pathways to Impact' document has more details.

Publications


10 25 50