Directed Routing Explained in Flash 10.1 P2P

June 4th, 2010

Directed Routing enables you to send data to a specific client in the peer-to-peer group (NetGroup). It requires stable and correct topology to work well - still it’s very useful.

There has been already something written about directed routing. But I’d like to share with you much more.

First, let me explain you which methods does what. You have basically three main functions sendToNearest, sendToNeighbor and sendToAllNeighbors. See image below.

Image: Peer-to-Peer Directed Routing in Flash Player 10.1 [Bigger image]

Continue reading to understand how it all works.

There is a very important thing to understand first. Building P2P app for little groups with stable and correct topology is easy. Building P2P app for real world with NATs and firewalls gets quite more complicated - you will see why.

Neighbor=Your Directly Connected Peer

How is a mesh constructed? Neighbor Count != Group Member Count
In a small groups (~5-10 members) with a stable and correct topology, all users are neighbors and they are connected together, so neighborCount==memberCount. You will basically get this Ring topology of Full Mesh.

Ring topology is defined by:

p.nextIncreasingPeer.nextDecreasingPeer == p.nextDecreasingPeer.nextIncreasingPeer == p

All of them are also in optimal Ring topology. So if you call NetGroup.sendToNeighbor(message, NetGroupSendMode.NEXT_INCREASING); and forward on each hop/peer to next one, you will at some point receive the message back and then you are sure, that it went to all peers in O(n) time. So first question, which comes in your mind is that this could be suitable for distribution among all peers. Nope - forget this mechanism, it’s not the correct way.

It may be misleading, when developing your first P2P app as you can directly communicate with every peer as all peers are your neighbors and you can distribute data through Ring. But, when the mesh becomes bigger or some members get behind different NATs, then you will find your app behaving inappropriately. This can be partly solved by message forwarding (relaying by intermediaries). But as mentioned earlier, it might happen, that the message will never reach it’s correct destination, however in most cases it should.

sendToNearest

NetGroup.sendToNearest(message:Object,groupAddress:String) - sends a message to the *neighbor* with groupAddress nearest to the destination address.

You can get groupAddress by using convertPeerIDToGroupAddress(peerID:String).

It may not be the peer in the group that is closest, because you may not be directly connected to that peer (especially in a group with 1000 members – in that example, each peer is expected to have about 35 directly connected neighbors). you must use recursive routing to get the message to its final destination. So in that case other peers may see the message on its way to its destination (and in fact they must take an active role in moving the message on toward its destination).

Have a look at the image above (see bigger). Our aim is to send a message from San Francisco (#1) to Moscow (#2).

Sending Message

// peer2ID is of #2 (Moscow)
 
var message:Object = new Object();
message.destination = netGroup.convertPeerIDToGroupAddress(peer2ID);
message.value = "Hello I am message from #1";
 
netGroup.sendToNearest(msg, msg.dest);

Receiving Message
When you receive a Direct Routing message, it comes to NetStatusEvent with code “NetGroup.SendTo.Notify”:

netGroup.addEventListener(NetStatusEvent.NET_STATUS, netStatus);
 
function netStatus(event:NetStatusEvent):void{
	switch(e.info.code){
	case "NetGroup.SendTo.Notify":
		// e.info.message contains our message Object
		trace("Received Message: "+e.info.message.value);
		break;
	}
}

But this will work only if #2 is a neigbor of #1. For proper delivery, we need to use forwarding.

Forwarding Message
As you can see on the image - peers #1 and #2 are not neighbors, so if you send a message using sendToNearest(message, #2) it will end up at one of your neighbors closest to the final destination - in this case at the 1st HOP (New York). Then you have to take an active role in the forwarding. You can detect if we have reached final destination using e.info.fromLocal. If true, we have reached final destination, if false, you need to forward. See the example below.

netGroup.addEventListener(NetStatusEvent.NET_STATUS, netStatus);
 
function netStatus(event:NetStatusEvent):void{
	switch(e.info.code){
	case "NetGroup.SendTo.Notify":
 
		if(e.info.fromLocal == true){
			// We have reached final destination
			trace("Received Message: "+e.info.message.value);
		}else{
			// Forwarding
			netGroup.sendToNearest(e.info.message, e.info.message.destination);
		}
		break;
	}
}

sendToNeighbor

NetGroup.sendToNearest(message:Object,sendMode:String) is here for message distribution to your direct neighbors.

sendToAllNeighbors

Sends a message to all neighbors. As illustrated on the first image. It’s the group in the grey dashed bubble.

Each peer in a group has O(log n) peers. The actual number is approximately 2 log2(n) + 13. So in a group of 1000 members you’d expect to have 2 * log2(1000) + 13, or about 33-ish. Some peers will have a few more neighbors, some a few less. sendToAllNeighbors() sends just to the directly connected neighbors, not to all peers in the group.

sendToAllNeighbors() can be used sorta like NetGroup.post() but to only reach O(log n) peers instead of all peers. This might be useful for certain kinds of group queries where you just need one answer and lots of peers (but not necessarily every peer) might be able to answer. So you might try all neighbors first, and if you don’t get a response from your local neighborhood, you could post() to ask everybody. This could improve the scalability of a distributed application.

estimatedMemberCount

The estimated member count is only an estimate of the total size of the group, not an exact count. It could be way off. It’s based on local information, extrapolating the size of the whole ring by looking at how much of the ring is covered by the two neighbors each in the increasing and decreasing direction. Note that the estimated member count *could* be lower than the neighbor count – the estimate exposes the result of the estimate so you can apply other application heuristics if you want. typically though you would just use the maximum of (neighbor count + 1) and estimated member count.

NATs and firewalls

It is possible for the message to end up at someone else than you originally targeted when there are connectivity problems in the group (like when there are NATs and firewalls). When a NAT or firewall prevents some peers from making direct neighbor connections with some other peers, it’s likely that they won’t form a perfect ring. In a perfect ring, for each peer p: p.nextIncreasingPeer.nextDecreasingPeer == p.nextDecreasingPeer.nextIncreasingPeer == p. NATs and firewalls can break this, and then directed routing may behave inconsistently.

For data distribution: NetGroup.post() is 1) much more thorough in getting a message to everyone and 2) will get it done in O(log n) time instead off O(n) time like using sendToNeighbor ring forwarding.

Matthew Kaufman described very nicely the issues with NATs and Firewalls here: http://forums.adobe.com/message/1064983#1064983

The “inconsistent ring” problem can be illustrated with just three nodes:

- Peer A behind a symmetric NAT
- Peer B behind a different symmetric NAT
- Peer C behind a full-cone NAT

Types of NATs (see Wikipedia)

Peers A and B will not be able to communicate directly with each other (symmetric-symmetric is not possible); however, each of them will be able to talk directly to peer C.

From peer A’s perspective, it’s in a 2-node group (itself and C). its next-increasing and next-decreasing neighbor is C.

From peer B’s perspective, it’s in a 2-node group (itself and C). its next-increasing and next-decreasing neighbor is also C.

However, from C’s perspective, it’s in a 3-node group. its next-increasing neighbor might be B (depending on everyone’s group addresses), and its next-decreasing neighbor would therefore be A.

This group is connected *enough* for multicast, posting, and object replication to work. however, directed routing will yield inconsistent results because the correct ring structure necessary for message routing isn’t possible.

Thanks my colleagues from Adobe Michael Thornburgh, Brad Outlaw and Matthew Kaufman for numerous explanations, who spent hours answering my e-mails and helped me to understand this, and share with you. THANK YOU GUYS!

Where to go from here

Check other tutorials regarding P2P in Flash:

- File Sharing over P2P in Flash with Object Replication
- P2P GroupSpecifier Class Explained In Details Part 1
- Multicast Explained in Flash 10.1 P2P
- Directed Routing Explained in Flash 10.1 P2P
- Simple chat with P2P NetGroup in FP 10.1

Video tutorials:
- P2P Chat with NetGroup in Flash Player 10.1
- Multicast Streaming in Flash Player 10.1 Tutorial

Tags: 10.1, air, directed routing, firewall, flash, Flash Media Server, Flash Player, fms, NAT, netgroup, P2P, peer-to-peer, sendToAllNeighbors, sendToNearest, sendToNeighbor, stratus
Posted in Tutorial |