Igor Overlay Network
From Self-Organizing Systems Group
Contents |
The IGOR Ecosystem
IGOR is a structured peer-to-peer overlay network. It provides a generic key based routing (KBR) service that can support all kinds of peer-to-peer applications. The name IGOR is an eponym after a character from Terry Pratchett's Discworld novels.
Similar to Chord, IGOR's overlay network is based on a ring structure. Unlike Chord, IGOR uses a symmetric ring with bidirectional overlay connections for increased efficiency. That means, that each IGOR instance keeps contact to its left and right neighbor in the ring. Moreover, IGOR relies on network proximity, i.e. apart from the said ring invariant, IGOR peers connect to those other peers that provide the best service at a time.
Following the traditional Unix style, the IGOR overlay implementation runs as a daemon. It has a modular design and can be extended by various plug-in extensions, which can, for example, be used to control the overlay's topology. The 'libigor' library provides the daemon's KBR interface to the applications. It comes with a complete API documentation, including a simple example application. Daemon and applications are connected via local socket communication. The daemon could also run in a DMZ, if you are, for example, bound to paranoid company policies.
Applications that are layered on top of IGOR can use the IGOR overlay to provide the required P2P functionality. The the most widely used functionality, a distributed hash table, is readily available with our extensible libdht library.
There are several applications that are based on IGOR and libdht: a distributed file system, a distributed video disk recorder, and a jabber style P2P connection manager for telepathy.
In the following we will briefly discuss the features and design concepts of the IGOR overlay daemon.
Routing
P2P overlays come in two different flavors: structured and unstructured overlays. Occasionally, there are proposals of hybrid solutions. Unstructured overlays cause little maintenance overhead, because they each peer can connect to any set of peers that it likes. Structured overlays efficiently locate individual data items. They guarantee success, provided the item is available somewhere in the overlay.
If combined with proximity-awareness techniques, structured overlays can achieve a good routing efficiency, too. As a downside, maintaining the required structural constraints of the overlay requires a potentially high overhead. One key aspect of our research behind IGOR is to improve the proximity-awareness and to reduce the maintenance overhead of structured overlays.
IGOR focuses solely on structured overlays, i.e. systems that support key based routing. We based our work mainly on the Chord and Kademlia structures. Other structures have similar characteristics.
IGOR can be thought of as two-way Chord. It inherits Chord's simple structural constraint of arranging the peers in a virtual ring. Thus, a peer only needs to know its left and right neighbor to be able to route all messages correctly. Furthermore, IGOR inherits Kademlia's symmetric paths. Overlay connections (aka fingers) can be used in both directions. While the original Chord proposal forces clockwise routing in the ring, IGOR request and response messages can travel on the same path. Thereby, the peers can quickly learn about good connections.
To enhance the routing performance of IGOR, it is equipped with proximity-awareness techniques. IGOR implements both, proximity route selection (PRS) and proximity neighbor selection (PNS). The proximity of an already connected neighboring peer is determined by round trip time (RTT) measurements. The RTT measurement is not part of the overlay. IGOR reads the RTTs directly from the underlying TCP/IP network stack. The proximity of yet-to-be neighbors is derived from network coordinates. IGOR uses the Vivaldi algorithm to obtain its network coordinates.
Plug-ins
We designed our IGOR daemon in a modular manner using plug-ins. There are four different basic types of plug-ins. Each of them is responsible for a different functionality.
Connection policy plug-in
Plug-ins of this type evaluate potential new fingers (i.e. overlay connections). The plug-in applies to both, incoming connection requests from other peers and the creation of outgoing connections based on other peers' recommendations to connect to some other peer.
Message plug-in
Plug-ins can define their own messages types. Our network coordinate algorithm, e.g., needs to exchange the peers' coordinates. Hence, every plug-in that defines own message-types must implement an according message plug-in that determines how the messages are forwarded and handled.
Task plug-in
Task-plug-ins are required for periodic actions, for example, the regular probing of the neighbors in the virtual ring.
Snoop and piggy-back plug-in
Plug-ins can snoop on the (payload) traffic. They can also piggy-back their own information onto other messages. The network coordinate system, e.g., regularly sends its coordinate estimations to the currently active peers.
NAT Traversal
In practice, firewalls and network address translators (NATs) obstruct the access to the peers. Firewalls implement an administrative decision, which we want to obey. So, we refrain from stealth technologies, which e.g. use HTTP or SSH ports for P2P overlay connections. NATs, on the other hand, should be considered as technical solutions to deal with address space limitations. Thus, we employ all the readily available solutions for NAT traversal.
We currently support
- Connection Reversal
- Connection Relaying
- UPnP using libminiupnp
For further information see Jonathan Will's bachelor thesis (in German).
Services
A generic KBR system should isolate the different applications, i.e. only peers that run a given application should be bothered by the respective overlay traffic. E.g. a mobile phone that joins a light-weight chat application should not have to relay heavy traffic from a video on demand system. On the other hand, general information that is useful for every node, for example, for peer recommendations, should be spread widely. This sharing of general information especially helps applications that only have a small user base. Being part of a large network helps them to bootstrap and stabilize in face of node churn.
IGOR addresses this issue with the concept of services. Each application is part of its own virtual service overlay. All the services that a peer has subscribed to share their local state. Thereby, we efficiently ensure the correctness of the routing algorithm, optimize the overlay network, and isolate the different applications.
IGOR routes messages based on a destination key and a service identifier. It is up to the respective service how these messages are handled.
Building and Running
IGOR uses autoconf && automake to compile. A notable compile option for extra verbose debug output is
configure --enable-debug=yes
which will produce much bigger debug logs, enabling to trace errors. For running IGOR see its README
make doxy
will provide documentation
Simulation
IGOR has built in capabilities of running both native and in the Omnet++ simulator and its INET extension. To build an IGOR, with Omnet support, use
configure --enable-omnet=yes --with-omnet=<path-to-the-omnet-dir> --with-inet=<path-to-the-inet-dir>
