1 – Introduction

OverSim [Baumgart, 2007] is an open source, powerful, and fast Peer-to-Peer (P2P) simulation platform based on the OMNet++ simulation environment. It is a component-based and layered simulation package built on top of the OMNet++ platform that utilizes object oriented features of C++. OverSim includes many well-known P2P protocols and applications that can be easily extend and modified. You can always build your protocols and applications when existing ones are inadequate. OverSim API is based on the Structured P2P API proposed by Dabek et al. [Dabek, 2003]. Below we discuss features, current applications, and high-level architecture of OverSim. You are encouraged to read the relevant publications (e.g., [Baumgart, 2007; Dabek, 2003]) to get a better understanding of protocols and applications that you may need to use or modify. Note that OverSim may not have all the features or may have introduced new features that were not discussed in the original publications.

1.1 Features

• Supports many structured and unstructured overlays
  • Structured overlays – Chord [Stoica, 2001], Kademlia [Maymounkov, 2002], Pastry [Rowstron, 2001], Bamboo, Koorde, Broose [Gai, 2004], QuON (overlay network based on quadtrees), Vast (overlay network based on voronoi diagrams), NTree [GauthierDickey, 2005], NICE [Banerjee, 2002] etc.
  • Unstructured overlays - Gia [Chawathe, 2003]
  • Hybrid designs
• Application layer services – Provides many real and dummy applications that demonstrate P2P applications
  • Distributed Hash Tables (DHT)
  • Internet Indirection Infrastructure (i3)
  • Multicast
  • Publish-Subscribe
  • Scribe [Castro, 2002]
  • SimMud
  • Peer-to-Peer Name Service (P2PNS) [Baumgart, 2008]
• Overlay routing - Allow different ways to forward a message from one overlay node to another (see Glossary for definitions)
  • Iterative - At each iteration, source node picks the next node to send the message based on nodes next hop nodes discovered by previous message. Routing scheme used in Kademlia [Maymounkov, 2002] is a good example.
  • Exhaustive-iterative
  • Semi-recursive - Use successive nodes to forward a message towards its destination, used in Chord & Pastry
  • Full-recursive
  • Source-routing-recursive
• Churn generators to simulate arrival, departure, and failure of peers (see Glossary for definitions)
  • LifetimeChurn
  • ParetoChurn
• Underlay support – Enable simulation of networks with simple underlay topologies to configurable network topologies with realistic bandwidths, packet delays, and packet losses. (see Glossary for definitions)
  • Simple underlay – Nodes are randomly placed on a 2D plane.
  • INET underlay – Nodes placed on a transit-stub topology.
  • Single host – Acts as an actual node that supports TCP and UDP.
• Graphical interface to demonstrate the overlay topology, message transmission, and node state. These can be helpful as a learning tool, in debugging, and in small-scale simulations.
• Large-scale simulation
  • Can simulate a 10,000 node network on a typical desktop. With more resources (memory and high speed CPU) it is possible to run even a 100,000 node networks over several simulation hours within reasonable time. I myself was able to run a 15,000 node network within 6 hours (6000 sec simulation time where each node sends a query every 15 seconds).
• Statistic collection and graphs
  • Simulator collects various statistics such as number of sent, received, or forwarded messages per node, successful/unsuccessful messages, and hop count. Several pythoh scripts are provided to ease post-processing of statistical data and generation of gnuplot output. You can always develop more complex scripts to analyze dumped data.

1.2 Applications

• Research tool – OverSim provides a convenient platform for simulating large-scale complex overlay protocols and applications. Though it can be overwhelming at first, you will realize its power when you develop a better understanding of the tool.
• Teaching tool – OverSim is a good teaching tool for overlay and P2P networking as it has the capability to visualize overlay connectivity, message passing, and simulation results. However, educators need to be proactive and need to provide some background/documentation to the tool otherwise students could find it overwhelming, particularly if students have not written large object oriented programs in C++. One of the objectives of this book is to address these concerns.

1.3 Architecture

OverSim is designed based on a layered architecture and its implementation tightly reflects the architecture of OMNet++. It is recommended that the reader gain good understanding of OMNet++, particularly if new overlay protocols or applications need to be developed. See Chapter 2 for a quick introduction on OMNet++. Even for a relatively small program you may have to modify code in multiple layers. Figure 1.1 show an abstract layered view of the architecture.

Fig. 1.1 - High-level OverSim architecture.

• Underlay – Is the physical network, e.g., Internet and ad-hoc networks. OverSim enables the simulation of network topologies with realistic bandwidths, packet delays, and packet losses. It support 3 underlay namely:
  • Simple underlay – A simple 2D topology where nodes are randomly placed on a plane. Inter-node distance is based on Euclidian distance between 2 nodes and latency is proportional to distance.
  • INET underlay – Enable simulation of complex topologies with multiple Autonomous Systems (ASs) and stubs (transit-stub), link bandwidth, delay, packet loss, etc.
  • Single host – Acts as an actual node that supports TCP and UDP. Used to communicate with other nodes as a typical P2P client.
• Overlay – Structured and unstructured protocols are implemented at this layer. Use overlay routers to forward messages for a given key.
• Tier 1 – Use to implement typical P2P services such as data indexing (e.g., Distributed Hash Tables (DHTs)), publisher-subscriber, caching, replication, etc.
• Tier 2 – Use to implement P2P application such as file sharing, name services, streaming, gaming, distributed data processing, etc.

More detailed view of the architecture given in Fig. 1.2.

Fig 1.2 - Detailed OverSim architecture (extracted from OverSim.org)

Many additional modules provided to enhance the functionality, visualize the topology and messages passing, and collect statistics. For example, Node List keeps track of current list of nodes in system, churn generators are used to simulate peer churn and failure, network coordinates are used for latency estimation, RPC handling provides simple messaging, trace manager is used to replay a given sequence of messages, etc. Later some of these modules will be discussed in detailed.

1.4 Outline

Chapter 2 presents how to install OverSim in Windows, Linux, and Mac. Several demos that explain how to run simple simulations is Presented in Chapter 3. Overview of OMNet++ is presented in Chapter 4. Chapter 5 introduce the Overlay layer and key functions. Key application layer (also refereed to as Tier 1) functions are presented in Chapter 6 and Tier 2 applications are presented in Chapter 7. How to write your own overlay and application is presented in Chapter 8. Chapter 9 discuss current implementations of various protocols in OverSim. Issues and possible optimizations related to simulating large-scale networks are discussed in Chapter 10.Various resources and a FAQ is presented in Chapter 11 and 12, respectively.

1.5 Summary

OverSim is a feature rich overlay/P2P simulation platform based on OMNet++. It comes with several well know overlay networks and P2P applications. You can always extend existing code or develop your own protocols and applications. Though it may initially appear intimidating, you will appreciate its features and flexibility as you develop a better understanding.

<< Previous – Welcome >> Next – Installing OverSim