My favorites | Sign in
Project Home Wiki Issues Source
READ-ONLY: This project has been archived. For more information see this post.
Search
for
Design  
This article describes the design details of our topology construction routines.
Updated Apr 5, 2013 by Arkin...@gmail.com

T-Man Live-Streaming TCS Design

I. Table of Acronyms

Acronym Meaning
TCS Topology Construction System
TVS T-Man View Size
CVS Cyclon View Size
SL Shuffle Length
PC Peer Count
OD Out-Degree
ID In-Degree
BW Bandwidth

II. Table of Terms

Term Meaning
Epidemic Algorithm An networking algorithm that allows peers to spread themselves to their neighbors and ultimately (given sufficient cycles) to the entire network
Child A type of relationship where a node has an in-bound connection to another
Parent A type of relationship where a node has an out-bound connection to another
Orphan A node with no parents
Source node A special type of node that has no predecessors (usually the streamer)
Hop count The path-length (or number of hops) from a node to the source node

1. Introduction

This article describes the design details of our topology construction routines. We'll begin by giving an overview of our motivations, detailing our assumptions and then describing the target topology that our TCS is aiming to construct.

1.1 Background

The purpose of our system is to construct a topology that minimizes the average path length of all nodes from a single source node. This source node is considered the originator of the stream, and therefore decreasing the average path length would logically yield lower latencies and thus much less observable lag. This can be achieved by maximizing the bandwidth utilization of the involved nodes. Meaning that the higher OD nodes are connected closer to the source node to allow for lesser average path lengths.

These kind of topologies have long been constructed in P2P environments using a dedicated central server that allows nodes to connect in the "right" way. However, dedicated servers aren't always an option and so the need arises for producing a solution that's capable of allowing nodes to construct such topologies in a distributed fashion. Our system will aim to achieve this using a T-man, Cyclon and a combination of specialized routines.

1.2 Assumptions

This sub-section contains a list of formal assumptions about the problem at hand. The assumptions are as follows:

  • Source nodes can't have any in-bound connections
  • Only one source node exists in the overlay
  • All non-source nodes share a constant static in-degree
  • Nodes are assigned out-degrees that satisfy a predefined random distribution
  • Our ultimate goal is to decrease the nodes' average path length from the source
  • This is done by maximizing bandwidth utilization of peers with higher out-degrees
  • To maximize bandwidth utilization, we'll sort nodes by their out-degrees. The higher the out-degree of a node the lower is its hop-count from the source node and vice versa.
  • Nodes are allowed to connect to other nodes in the same row
  • The graph must be acyclic:
    • Nodes from a lower row must not have any outbound connections to those in higher rows
    • Nodes must not have inbound and outbound connections to the same node (i.e. a node can't be both a parent and a child to the same node)
  • The graph should converge to & satisfy the aforementioned assumptions without using a central entity
  • This convergence should be based on the T-Man topology construction protocol

1.3 Target Topology

Given nodes with the following out-degree counts:

Out-Degree Frequency
3 1
2 2
1 3

And a static in-degree of 2, the following topology would fulfill the optimal solution (according to our predefined assumptions in section 1.2):

2. Architecture

Our system is composed of 3 main layers:

  1. Cyclon: This is an epidemic protocol that is used for propagating and collecting random nodes - The objective is to keep peer views completely random
2. T-Man: This protocol works on top of cyclon. It takes the cyclon view and sort its nodes (according to a ranking function) and then assembles them in a separate view. As time passes, peer views are accumulating the highest ranking nodes, and trimming the least. Our ranking function will be described in detail in section 3.3.2.
3. Children/Parent Clusters: Once a peer acquires children and/or is acquired by a parent, they keep updating their state to their successors and predecessors. This is to insure that its state is kept up-to-date.

3. Design

3.1. Data Structures

In this section we'll discuss the various utilized data structures and their corresponding uses in our topology construction protocols.

3.1.1. Peer Descriptor

Peer Address Age Out-Degree In-Degree Parents Hop-count

The Peer Descriptor is the build-block for all our data structures. It's a representation of the peer. It contains the following elements:

  • Peer Address (static): ID/IP address of the peer in the network. Used to uniquely define it and to allow connections.
  • Age (dynamic): Defines how many cycles passed on this descriptor before its last update.
  • Out-Degree/Bandwidth (static): This describes the maximum number of out-going connections that the peer in question can maintain.
  • In-Degree (static): This describes the maximum number of in-bound connections that the peer can have. It's usually fixed for all peers joining the network.
  • Parents (dynamic): List of peer's current parents
  • Hop-count (dynamic): Number of hops from the source node

3.1.2. View

Peer Descriptor 1 Peer Descriptor 2 ... Peer Descriptor n

A view consists of a series of Peer Descriptors that describe peers in a network. Views are held by peers and are periodically shifted between neighboring nodes, to allow the network to converge to the desired topology.

3.1.3. Peer Data

My Descriptor Cyclon View T-Man View Parents Children

These are the data items carried by each individual peer. It consists of the following elements:

  • My Descriptor: A Descriptor of itself.
  • Cyclon View: A list of descriptors to nodes used to construct a random topology using Cyclon.
  • T-Man view: A list of descriptors to nodes used to construct the designated T-Man topology.
  • Parents: A list of the descriptors of my current parents.
  • Children: A list of the descriptors of my current children.

3.2. Cyclon

Our implementation of Cyclon is based on this paper: "CYCLON:Inexpensive Membership Management for Unstructured P2P Overlays".

Cyclon forms an overlay and keeps it connected by means of an epidemic algorithm. This works by having peers know a small changing set of peers (called neighbors). They then periodically contact any one of those peers to exchange neighbors.

More formally, each peer maintains a neighbor list in a small, fixed-sized cache of c entries (with typical value 20, 50, or 100). A cache entry contains the peer address of another peer in the overlay. Each peer P repeatedly initiates a neighbor exchange operation, known as shuffle, by executing the following seven steps:

1. Increase by one the age of all neighbors.
2. Select neighbor Q with the highest age among all neighbors, and l-1 other random neighbors.
3. Replace Q’s entry with a new entry of age 0 and with P’s address.
4. Send the updated subset to peer Q.
5. Receive from Q a subset of no more that i of its own entries.
6. Discard entries pointing at P and entries already contained in P’s cache.
7. Update P’s cache to include all remaining entries, by firstly using empty cache slots (if any), and secondly replacing entries among the ones sent to Q.

The constant exchange of views maintains the randomness of the overlay, which is a necessary property. Even more so, Cyclon provides a more enhanced implementation to the basic shuffling protocol by taking the age parameter into consideration (as outlined above). This insures that nodes are going to be uniformly represented in views, which enhances the overall overlay randomness.

3.3. T-Man

3.3.1. Protocol

On-top of Cyclon, a T-Man topology construction protocol operates as defined in "T-Man : Gossip-based Overlay Topology Management". Peers basically take the nodes in their cyclon-view, sort them using a ranking function (which will be defined the next subsection) and then integrate them into their T-Man views. This means that peers are constantly accumulating high-ranked nodes and getting rid of low-ranked ones. Of course, this protocol works in parallel to Cyclon, as we always need a stream of random nodes to prevent the network from converging to an undesired overlay.

Like Cyclon, the protocol works using a similar algorithm as defined below:

  1. Active Thread
do at a random time once in each consecutive inetrval of T time units:
p <-- selectPeer()
myDescriptor <-- (myAddress, myProfile)
buffer <-- merge(view, {myDescriptor})
buffer <-- merge(buffer,rnd,view)
send buffer to p
receive buffer(p) from p
buffer <-- merge(buffer(p), view)
view <-- selectView(buffer)
2- Passive Thread
receive buffer(q) from q
myDescriptor <-- (myAddress, myProfile)
buffer <-- merge(view, {myDescriptor})
buffer <-- merge)(buffer, rnd, view)
send buffer to q
buffer <-- merge(buffer(q), view)
view <-- selectView(buffer)

Functions:

  • merge(A, B): Returns the union of A & B, whilst keeping the lower aged in any intersecting nodes.
  • selectPeer: Sorts the nodes in the target view according to the ranking function and returns the highest ranked peer
  • selectView: Sorts the nodes in the target view and return the highest ranked tvs nodes (where tvs is the predefined T-man view size)

3.3.2. Ranking Function

Here we'll describe in detail how the ranking system (utilized by the T-Man protocol) operates.

Rank(Node A, Node B):

     if(A has a higher bandwidth than B) do:
         return Favor(A, B)
     if(A has the same bandwidth as B) do:
         if(A is already my child) do:
             return A
         else
             return B
     if(A has a lower bandwidth than B) do:
         return Favor(B, A)
Favor(Node X, Node Y):
    if(Xs hop count will decrease if I acquire it) do:
         return X
    if(Ys hop count will decrease if I acquire it) do:
         return Y
    if(my BW is greater than Xs highest parent BW) do:
         return X
    if(my BW is greater than Ys highest parent BW) do:
         return Y
    if(Xs parent.size less than its in-degree) do:
         return X
    if(Ys parent.size less than its in-degree) do:
         return Y
    return X

We first give a precedence to nodes that have a higher bandwidth (or out-degree). However, that's not our only ranking measure. We also rate nodes based on:

1. Hop-count: Nodes with a hop-count that is greater than my hop-count + 1 are favored, because I'll be able to decrease their path length from the source node. If the node is orphaned (i.e. has no parents) then the hop-count is set to infinity.

2. Highest Parent Bandwidth: This parameter represents the highest bandwidth of all the parents of the node in question. If my bandwidth is higher than this parameter, then this node is favored, as I'm likely to be placed closer to the source node than its parents. If the node is orphaned then this value is set to 0.

3. Number of parents: This represents the number of parents that have acquired the specified node. Nodes with in-degrees higher than their current parent count are favored, since they can allow for more in-bound connections.

3.4. Child/Parent Clusters

This is our upper most layer that is built using our T-Man topology construction protocol.

3.4.1. Acquisition Process

During the active & passive threads (shown on section 3.3.1) of the T-Man protocol, the views are updated and sorted after adding the node's current children to the view. The top OD nodes (where OD represents the node's Out-Degree) are then put into a candidate list. If any of these nodes is not a current child, the peer sends a child acquisition request and awaits a response. The child's choice criteria is determined using a similar logic to our pre-defined ranking function (for more information refer to section 5.2 of our implementation wiki entry).

If the peer receives an acceptance response, it will add the child into its children list. The child, on the other side, will add the node to its parents list.

3.4.2. Update Process

Once a child or parent is acquired using the above process, they will have to update the acquiring node with any changes in their state (at all times). This includes changes in their hop-counts.

Such updates are necessary in order to allow peers to make informed decisions about acquiring/being acquired by different nodes because they have up-to-date info about their parents' and children's current states.

The update messages and handlers will be outlined in more detail in the implementations page.

Powered by Google Project Hosting