|
Design
This article describes the design details of our topology construction routines.
T-Man Live-Streaming TCS Design
I. Table of Acronyms
II. Table of Terms
1. IntroductionThis 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 BackgroundThe 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 AssumptionsThis sub-section contains a list of formal assumptions about the problem at hand. The assumptions are as follows:
1.3 Target TopologyGiven nodes with the following out-degree counts:
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. ArchitectureOur system is composed of 3 main layers:
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. Design3.1. Data StructuresIn this section we'll discuss the various utilized data structures and their corresponding uses in our topology construction protocols. 3.1.1. Peer Descriptor
The Peer Descriptor is the build-block for all our data structures. It's a representation of the peer. It contains the following elements:
3.1.2. View
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
These are the data items carried by each individual peer. It consists of the following elements:
3.2. CyclonOur 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-Man3.3.1. ProtocolOn-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:
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:
3.3.2. Ranking FunctionHere 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 XWe 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 ClustersThis is our upper most layer that is built using our T-Man topology construction protocol. 3.4.1. Acquisition ProcessDuring 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 ProcessOnce 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. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||