ARIGATONI

 Programmable Overlay Network

for Generic Resource Discovery

INRIA Sophia Antipolis, LogNet Team

• AEOLUS -- FP6 ST FET Global Computing: Algorithmic Principles for Building Efficient Overlay Computers (WIKI, CORDIS).
• The recent explosive growth of the Internet gives rise to the possibility of a global computer of grand-scale consisting of Internet-connected computing entities (possibly mobile, with varying computational capabilities, connected among them with different communication media), globally available and able to provide to its users a rich menu of high-level integrated services that make use of its aggregated computational power, storage space, and information resources. Achieving this efficiently and transparently is a major challenge that can be overcome by introducing an intermediate layer, the overlay computer. The goal of this project is to investigate the principles and develop the algorithmic methods for building such an overlay computer that enables this efficient and transparent access to the resources of an Internet-based global computer.
• According to the AEOLUS Manifesto (GET-IT!), Arigatoni fits into
  
• AEOLUS SP2: Resource Management - WP 2.1: Resource Discovery  GET-IT!
  
• AEOLUS SP3: Sharing Information and Computations - WP 3.4: Workflow and Services

• Capsule. The research program focus on the study of foundations of programmable overlay networks. Such overlays are built over a large number of distributed computational individuals, virtually organized in colonies gouverned by a leader (called broker), democratically elected or imposed by system administrators (deux-ex-machina). Every computational entities ask to the broker to log in the colony by declaring their resources that the computee is ready to offer with variable guarantee. Once logged, the individual can ask to the broker for other resources.  Colonies can recursively be considered as evolved individuals that can sign in a outermost colony gouverned by another super-leader.  Communications and routing intra-colonies goes through a  broker-2-broker PKI-based negociation.  Every broker route intra and  inter \emph{requests} by first filtering in its resource routing table and then forwarding the request first inside its colony, and then forward the request toward the proper super-leader (thus applying an endogenous-first-estrogen-last strategy). Theoretically speacking, queries are formulæ of first-order logics equipped with a small imperative program used to orchestrate and  synchronize atomic formulæ.  When the client individual  receive all (or part of) the requested resources, then it is served  directly by the others server(s) individuals, without a further mediation of the leader, in a pure peer-to-peer fashion. The  proposed overlay promotes an intermittent participation in the colony, since peers can appear, disappear, and organize themselves dynamically. This implies that the routing process may lead to failures, because some individuals have logged out, or are  temporarily unavailable, or they have been manu militari logged out by the broker because of their poor performance or  greediness.
  
• A two pages "resume" GET-IT!
  
• A general talk on Arigatoni and resource discovery protocol GET-IT!
• A specialized talk on the virtual intermittence protocol GET-IT!

• COLORS -- Action INRIA Sophia: Arigatoni on Wheels (with Politecnico di Torino, ETH Zurich)

• The goal of the project is the definition of an info-mobility system capable of proposing new development paradigms that focus on the maximization of communication efficiency and information exchange in Vehicle-to-Vehicle (V2V) and Vehicle-to-Infrastructure (V2I) communication. Such goals can be pursued without devising new communication technologies, but, rather, by aiming at a drastic technological upgrading of existing infrastructures and at devising a lightweight overlay network called Arigatoni, designed at INRIA Sophia Antipolis in Mascotte Project Team and mathematically investigated in Maestro Project Team. The “Arigatoni-On-Wheels” project will therefore specify and investigate models, algorithms and protocols that can promote an efficient interactivity among all the elements of traffic systems (vehicles, roadside infrastructures and service centres).

• Luigi Liquori
• Michel Cosnard
  

• Raphael Chand
  

1. D. Borsetti, C. Casetti, C. F. Chiasserini and L. Liquori. Content Discovery in Heterogeneous Mobile Networks. In Heterogeneous Wireless Access Networks: Architectures and Protocols, Springer-Verlag, book chapter, invited, 2008. GET-IT!
2. L. Liquori, D. Borsetti, C. Casetti, and C. F. Chiasserini. An Overlay Architecture for Vehicular Networks. In Proc. of IFIP Networking-08. International Conferences on Networking, Lecture Notes in Computer Science, 4982, pages 60--71, Springer-Verlag, 2008. GET-IT!
3. L. Liquori, M. Cosnard. Logical Networks: Towards Foundations of Programmable Overlay Networks and Overlay Computing Systems: In Proc. of TGC-07. International Symposium on Trustworthy Global Computing, Lecture Notes in Computer Science, 4912, Springer-Verlag, 2008. GET-IT!
   • This paper is our manifesto! Probably it is one of the first you may have a look.
4. R. Chand, M. Cosnard, L. Liquori. The Arigatoni Overlay Network: An Improved Resource Discovery Protocol. Future Generation Computer Systems, 24(1), pp 31--38, Elsevier, 2008. GET-IT!
5. M. Cosnard, L. Liquori. Weaving Arigatoni with a graph topology: In Prof. of ADVCOMP-07. International Conference on Advanced Engineering Computing and Applications in Sciences, IEEE Computer Society, to appear, 2007. GET-IT!
   • This paper presents the first paper using a graph topology.
     
6. R. Chand, M. Cosnard, L. Liquori. Improving Resource Discovery in the Arigatoni Overlay Network. In Proc. of ARCS'07: 20th International Conference on Architecture of Computing Systems System Aspects in Pervasive and Organic Computing, Lecture Notes in Computer Science, 14 pages, to appear, Springer-Verlag, 2007. GET-IT!
• This paper presents the resource discovery protocol RDP V2.
  
7. R. Chand, M. Cosnard, L. Liquori. Resource Discovery in the Arigatoni Overlay Network. In Proc. of I2CS'06, International Workshop on Innovative Internet Community Systems, Neuchatel, Switzerland. Lecture Notes in Computer Science, 13 pages, to appear, Springer Verlag, 2007. GET-IT!
• This paper presents the resource discovery protocol V1.
  
8. M. Cosnard, L. Liquori, R. Chand. Virtual Organizations in Arigatoni. In Proc. of DCM'06, 3rd International Workshop on Developments in Computational Models, Venice, Italy. Electronic Notes in Theoretical Computer Science, 22 pages, to appear, Elsevier, 2007. 22 pages = journal version. GET-IT!
• This paper present the virtual intermittent protocol VIP V1.
  
9. D. Benza, M. Cosnard, L. Liquori, M. Vesin. Arigatoni: A Simple Programmable Overlay Network. In Proc. of JVA'06, John Vincent Atanasoff International Symposium on Modern Computing, Sofia, Bulgaria, pages 82--91, IEEE Computer Society, 2006. GET-IT!
• This paper is the "father" of all the above.  
  

• GET-IT-LINUX! or GET-IT-OSX!
  
• Capsule. The resource discovery algorithm  was implemented in C++ and compiled using GNU C++ version 2.95.3. Experiments were conducted on a 3.0 Ghz Intel Pentium machine with 2GB of main memory running Linux 2.4.28.
• Screenshot

 

• For a randomly generated topology GET-IT! we had some simulations experiments C1 C2 C3 C4 C5

 

• The JOpera source file GET-IT! (try JOPERA!)
• A nice animation of the example is now available GET-IT-3MB! or GET-IT-6MB!

• GET-IT!
  
• Abstract. Arigatoni is a structured multi-layer overlay computer providing various services with variable guarantees, and promoting an intermittent participation to the virtual organization where peers can appear, disappear and organize themselves dynamically. Arigatoni mainly concerns itself with how resources are declared and discovered in the overlay, allowing global computers to make a secure (using standard PKI mechanisms) use of global aggregated computational power, storage, information resources, etc. Arigatoni provides fully decentralized, asynchronous and scalable resource discovery, and provides mechanisms for dealing with dynamic virtual organizations. Simulations show that resource discovery in Arigatoni is efficient and scalable. The explosive growth of the Internet gives rise to the possibility of designing large overlay networks (a.k.a. virtual organizations) consisting of Internet connected global computers (GC), able to provide a rich functionality of services that makes use of its aggregated computational power, storage, information resources, etc. The virtual organization is hierarchically structured in colonies, governed by global brokers (GB). A GB (un)registers GCs, receives service queries from clients GCs, contacts potential servants GCs, trusts clients and servers and allows the clients GC and the servants GCs to communicate. Registrations and requests are performed via a simple query language à la SQL and a simple orchestration language à la JOPERA. Communication intra-colony is initiated via only one GB, while communication inter-colony is initiated through a chain of GB-2-GB message exchanges. Once the resource offered by a global computer has been found in the overlay network, the real resource exchange is performed out of the overlay itself, in a peer-to-peer fashion. The main challenges in Arigatoni lie in the management of an overlay network with a dynamic topology, the routing of queries and the discovery of resources in the overlay. In particular, resource discovery is a non trivial problem for large distributed systems featuring a discontinuous amount of mobile resources offered by global computers and an intermittent participation in the overlay. Thus, Arigatoni features two protocols: the virtual intermittence protocols, VIP, and the resource discovery protocol RDP. The VIP protocol deals with the dynamic topology of the overlay, by allowing individuals to login/logout to/from a colony. This implies that the process of routing may lead to some failures, because some individuals have logged out, or are temporarily unavailable, or because they have been "manu military" logged out by the broker because of their poor performance or avidity.