********************************************** Coffee Talk A Peer-to-Peer Chat Protocol Utilizing TCP/IP and UDP/IP (C) Jan Michael Ibanez 2003 CONTENTS -------- Introduction Terms Protocol Phases P2P Peer Management Subprotocol Peer Sequence Numbers Peer Discovery Network Reconfiguration Network Registry Peers Peer Death P2P Messaging and Relaying Subprotocol Conversations and Dialogues Related Material Introduction ------------ There are several existing chat and instant messaging (IM) protocols existing in the market today. However, most of these protocols exist with the need for a central server to route and manage these chat networks. A good example is the IRC network. When a client wants to participate in an IRC chat session, he must first connect to one of several thousand IRC servers around the world, specific to a particular IRC network. For example, to connect to the Undernet Network (http://www.undernet.net), the client must connect eu.undernet.net to connect to a random Undernet server in Europe. Each server is connected to each other, relaying messages from clients connected to it to other servers, as well as relaying messages from other servers to its clients. The backbone therefore of such a network is the many servers that relay messages to and from clients and other servers. A problem with such a model is that the network suffers from a single point of failure -- the server. In the case of IRC, such is quite evident when the network suffers from what is known as a net split. A net split occurs when the link between two or more IRC servers is severed (either because of hardware or software failure), causing a block in the relaying of messages. Messages from one side of the split cannot reach the other because of the severed link, and vice versa. In recent years, there has been a shift in network models to what is now known as peer-to-peer computing. An example of a peer-to-peer (or P2P as it is abbreviated) network is the Gnutella network. The Gnutella protocol is an open protocol that allows users to share files. There is no central source of connection-- a Gnutella client does not need to connect to a central server. In this model, the network becomes more robust, as each node (called a peer in P2P parlance) is in a sense both a server and a client in the network. A Gnutella network is therefore more ad hoc than a network based on a server-client architecture. Coffee Talk is a p2p protocol that allows users to exchange messages over a TCP/IP-based network. Version 0.1 of the protocol uses a UDP broadcast to look for and discover peers. It uses a TCP connection to connect to peers to send messages. Terms ----- P2P Network : The collection of peer-to-peer chat peers within a particular subnet or network. P2P Peer Management Subprotocol (PMsP) : The subprotocol responsible for monitoring and maintaining the P2P Network. It uses UDP port 32102. This is the subprotocol used in phase A and phase C of the protocol. P2P Messaging and Relaying Subprotocol (MRsP) : The subprotocol responsible for sending messages to a particular peer. It uses TCP port 32103. Peer : A single entity within the peer-to-peer chat network; represents a point of entry into the system. Each peer is an independent unit within the P2P network. Peer discovery : A process by which a peer wishing to join the network looks for other peers currently in the network. This is phase A of the protocol. Dying peer : A peer which is about to leave the network. A dying peer must follow phase C of the protocol. Lost peer : A peer which has inadvertently left the network without undergoing phase C of the protocol. Part of the p2p network management subprotocol deals with lost peers. Network Registry Peer : A peer that monitors the network addresses of other peers and responds to peer lookup requests. Network registry peers are responsible for responding to joining peers' requests, as well as keeping track of active peers. See "Network Registry Peers" for more info. Messaging Session : A messaging session is started when one peer initiates a connection with another peer during the peer messaging phase. The session is a unicast event, and may either be a conversation or a dialogue. Dialogue : A messaging session with only two peers involved. This is the simplest messaging session. Conversation : A messaging session with several peers involved, with one of the peers acting as conversation locus. The peer initiating the conversation acts as the conversation locus; all other peers initially connect to it. Messages from peers are relayed by the locus. The initiation of a conversation is broadcast via PMsP to all peers, unless it is flagged "secret". Protocol Phases --------------- The protocol has three phases of operation: a) Peer discovery/lookup phase b) Peer messaging phase c) Peer termination and exit phase / Network reconfiguration a) Peer discovery/lookup phase A peer performs peer discovery to look for and connect to active peers in the particular subnet it is in. Each peer that responds to lookup can be connected to during peer messaging. The peer performing peer discovery must store reply information for use later in the protocol. Peers responding to peer discovery must update their peer information to include the joining peer. If a network registry peer exists, only the network registry peer should reply to peer discovery requests. b) Peer messaging phase Once a peer has joined the network, it can participate in messaging. Messaging is a unicast event between two peers, either through a conversation or through a dialogue. Peer messaging is managed by the MRsP. c) Peer termination and exit phase / Network reconfiguration A peer wanting to terminate must notify the network via the PMsP. Peers which have not notified the network of their termination (either because of a software or hardware failure, or because they were forcibly removed from the network) will be "expired" via the PMsP. If a network registry peer exists, it is responsible for verifying whether a peer is still alive; otherwise, see "Peer Death". The three phases outlined above are essentially sequential in order. Phase B (peer messaging) is performed during the lifetime of the peer. P2P Peer Management Subprotocol ---------------------------------- The P2P Peer Management Subprotocol (PMsP) is responsible for maintaining the peer-to-peer chat network. Each peer in the network is responsible for maintaining a list of mappings between network-unique IDs and network addresses, unless there is a Network Registry Peer, in which case each peer should rely on the Network Registry Peer to update its list. PMsP is a datagram-oriented connectionless protocol that uses UDP for transport. Since UDP is inherently unreliable, each PMsP message is an "act on reception" message; i.e., the status quo is maintained if no PMsP message is received. A PMsP message is always 64 bytes in length, with the following format: Offset Contents 0 Message Header n (n = Header length) Message Body n+m (m = Body length) 0xFF; Check byte The Message Header format is as follows: Offset Contents 0 Message ID 1 Subprotocol version 2 Coffee talk version 3 Length of Network ID 4 Network ID 4+[3] Message body The following are the legal PMsP messages and their parameters: JOIN - Peer requests to join the network (0x01) Offset Contents 0 Flags-- A bitset which signify the capabilities of this peer. Currently, only bits 3 and 2 are used; bit 1 is reserved. Bit Capability 1 (Reserved) 2 Diagnostics-only peer 3 Network registry peer 4 (unused) 5 (unused) 6 (unused) 7 (unused) 8 (unused) LEAVE - Peer requests to leave the network (0x03) - no body - PEER - Currently participating peer's response to a JOIN (0x02) Offset Contents 0 (integer) Peer sequence number. Used to determine next-in-line for network registry peers and beacon peers. UID_CONFLICT - A peer already is using that network UID (0x04) Offset Contents 0 Flags (see JOIN) 1 (integer) Peer sequence number. REGISTRY_PEER_QUERY - Broadcast response by a joining network registry peer. This tells the network that a registry peer wishes to preside over the network. (0x05) Offset Contents 0 (integer) Peer sequence number. REGISTRY_PEER_TAKEOVER - Broadcast by a network registry peer wishing to replace a leaving or lost network registry peer. Optional.(Note: If several peers broadcast this message, the peer with the lowest peer sequence number becomes the new network registry peer) (0x06) Offset Contents 0 (integer) Peer sequence number. REGISTRY_PEERLIST - Currently participating network registry peer's response to a JOIN (0x07) Offset Contents 0 Flags. 1 Number of REGISTRY_PEERITEM messages to expect (up to 255) 2 Peer list UID REGISTRY_PEERITEM - Item in a registry peer's list (0x08) Offset Contents 0 Flags (for other peer) 1 32-bit IPv4 address of other peer 5 Other peer's Network ID length (n) 6 Other peer's Network ID 6+n (integer) Other peer's peer sequence number REGISTRY_UPDATE - Request by a peer to a network registry peer for updates. (0x09) - no body - (Note: only valid for network registry peers. Reply is in the form of REGISTRY_PEERLIST/REGISTRY_PEERITEM messages) KEEP - Broadcast by either a network registry peer or by the current "beacon" peer to look for lost peers [ PeerSeq TimeToNext ] TimeToNext: Number of seconds to next KEEP message ALIV - Unicast response by a peer to a broadcast KEEP [ NetworkUID ] LOST - Notifies peers of the identity of a lost peer [ ProtoVer NetworkUID Flags PeerSeq IPAddress ] PING - Unicast message representing a protocol ping [ ProtoVer NetworkUID Flags PingUID ] PingUID: Unique ID to distinguish this ping from other pings. PONG - Reply to a protocol PING [ ProtoVer NetworkUID Flags PingUID ] RES_ - Broadcast message to notify peers of available resources [ ProtoVer NetworkUID ResourceCount (ResourceType ResourceID) ] ResourceCount: Number of resources being advertised. ResourceType: The type of resource being advertised. ResourceID: The name/ID of the resource with the specified type. Broadcast messages JOIN, LEAV, REG1, REG!, KEEP, LOST, UID! Unicast messages PEER, PLST, PREG, ALIV, PING, PONG, UREG -- FIXME FIXME FIXME FIXME FIXME FIXME FIXME FIXME FIXME FIXME FIXME -- BEACON PEERS. To ensure that lost peers are found and are expired from each peers' list, a "beacon" peer is assigned to broadcast a KEEP message after a certain interval. Each peer must then reply with an ALIV message to inform the beacon peer that it is still participating in the network. The beacon peer then checks all replies against its list of peers; peers which have not replied to the KEEP message are then broadcast in individual LOST entries. Peers must then update their lists accordingly. NOTE: LOST messages only flag that the peer is "unreachable". A peer marked LOST after three KEEP checks should be expired and removed from the list of participating peers. Beacon peer assignation is made at random. ** note - i have no idea how the *first* beacon peer gets assigned at this point in time. probably the first peer to join the network? -- FIXME FIXME FIXME FIXME FIXME FIXME FIXME FIXME FIXME FIXME FIXME -- Peer Sequence Numbers --------------------- Each participating peer in the network generates a peer sequence number from the sequence numbers of other peers in the network. The sequence number is unique to a single peer at a single instance of the network; a rejoining peer has a different sequence number. Peer sequence numbers are generated from the current time of the computer's clock. The time is converted to a offset of the number of seconds from midnight, and is one of the roots in a formula, the other being the 32-bit IPv4 address of the host. The last peer sequence number is input into the formula with these two roots, and the result of the formula is used as the peer's sequence number. The sequence number therefore becomes pseudo-random, but with predictable results; i.e. a peer connecting at exactly the same time of day with the same IP address may have the same sequence number. Note that the sequence number depends on the host computer's clock, and not a unified or synchronized clock within the network; the host computer's clock may be synchronized with other clocks in the network, but this is not a requirement. The IP address is used to ensure that two peers connecting at precisely the same moment will have different peer sequence numbers. Peer Discovery -------------- To participate in the network, a peer must first "discover" or lookup currently participating peers. To do this, the peer must perform Peer Discovery via the PMsP. First, the peer broadcasts a JOIN message on the local network, calculating the broadcast address from the local address. The peer then waits for replies to its JOIN message in the form of PEER messages. If no messages arrive after the timeout period, the peer then assumes it is the only one on the network. A peer already in the network or about to join the network must listen for PMsP broadcasts. Whether or not a peer has joined the network, it must reply to JOIN messages by replying with a PEER message to the peer who had sent the JOIN. This ensures that peers who have come up and initiated phase A at the same time all join the network. If a peer receives a JOIN message having the same network UID, with the message not having originated from it, the peer broadcasts a UID! message to all peers to notify that a network UID clash has occured. Peers about to join the network must resend their respective JOIN messages with a different network UID; already participating peers receiving the UID! message must remove the entry(ies) in their peer lists referring to the peer(s) who have attempted to JOIN with a clashing network UID. If the network has a network registry peer already active and presiding over the network, the joining peer receives PLST / PREG messages instead of PEER messages; peers must respect the presence and presidence of the network registry peer and should ignore the JOIN broadcast message. Network Reconfiguration ----------------------- FIXME: Write this part Network Registry Peers ---------------------- When a peer joins the network with its 'r' flag set, and there are no other network registry peers, it becomes the primary network registry peer. A network registry peer acts as a central repository of network information, including the list of mappings between network UIDs and IP addresses. When a network registry peer leaves the network, other peers capable of becoming a network registry peer should at their choice broadcast a REG! message to notify their intention of succeeding the leaving network registry peer. If several peers broadcast a REG! message, the peer with the lowest peer sequence number becomes the new network registry peer, and must broadcast a REG1 message to all peers to notify them that it is the new registry peer. The network registry peer is responsible for keeping track of the status of all peers in the network. If it is currently presiding over the network, it must be the one responsible for broadcasting KEEP and LOST messages. If the network registry peer does not send its KEEP message within the timeout specified by its previous KEEP message, the peer is assumed to have been lost. If no other network registry peer announces its intention to preside, the network assumes that no other network registry peer exists and will then fallback to the use of beacon peers. If a peer in the network wishes to update its list of peers, it should issue a UREG message to the current network registry peer, either by broadcast or (preferably) by unicast to the network registry peer. The network registry peer should then respond with PLST / PREG messages. If two network registry peers come up at the same time and the network currently has no network registry peers presiding over it, the two peers will both send a REG1 to the network. As with REG! messages, the peer with the lowest sequence number becomes the new network registry peer. Peer Death ---------- A peer wishing to leave the network should notify other peers by broadcasting a LEAV PMsP message. Peers receiving the LEAV message should expire the entry referring to the orgin peer in their list of peer-to-IP mappings. However, in the case where software or hardware failure, or loss of network connectivity kills a particular peer without notifying the network, the network must have a way to discover this loss. For this reason, a peer is assigned to be a "beacon" peer in turn, with the responsibility of checking the status of the peers in the network. If a network registry peer exists and is currently presiding over the network, that registry peer acts as the beacon peer. It may occur that a network peer is found to be "lost" by the beacon peer broadcast (either because its reply to the KEEP message was lost, or the KEEP message was not received). In such a case, the peer is desynchronized from the network. Peers must have the logic to detect that they are desynchronized from the network, and so must resend a JOIN message if necessary. P2P Messaging and Relaying Subprotocol -------------------------------------- FIXME: Write this part Conversations and Dialogues --------------------------- FIXME: Write this part. Related Material ---------------- BabbleNet IBM Alpha Works (from http://www.alphaworks.ibm.com/tech/babblenet) "BabbleNet is a completely decentralized, peer-to-peer (P2P), real-time chat program that allows users to create an ad hoc chat network without connecting to or installing a central server. Basically, it is a cross between Gnutella and IRC. BabbleNet was developed in a modular way so that the chat functionality sits upon a generic P2P framework." JXTA Java (from http://www.fawcette.com/javapro/2001_12/magazine/features/bkurniawan/) "The JXTA protocols are a set of six protocols that have been designed for peer-to-peer (P2P) network computing. The six protocols are the Peer Discovery Protocol, the Peer Resolver Protocol, the Peer Information Protocol, the Peer Membership Protocol, the Pipe Binding Protocol, and the Peer Endpoint Protocol. Using these protocols, you can send messages across multiple network hops to any other peer in the network. These protocols are the backbone of any Java peer-to-peer application..." Tragic http://users.bestweb.net/~fordii/tragic/tragic.txt Additional Notes ---------------- Bandwidth: There has to be a way to conserve bandwidth, especially when it comes to the peer management protocol. I mean, the KEEP message broadcast is too costly, IMHO. Probably connect each peer to another peer ala buddy system (as discussed with Paolo)? Problem is if both peer and buddies all die, no one is informed. With current setup, all peers know when the KEEP broadcast should occur, and can react when it doesn't come. However, with the current setup, there is too much state information within the system; i.e. state information is always refreshed just to keep track of peers, instead of updating only when there is a change in states. And the LEAV message becomes redundant because of that. Why not a keep-alive ping to the network registry peer? I mean, the peer monitors everyone, right? So everyone has a direct connection to the peer, and when it goes under, the network registry peer resolution protocol (see Network Registry Peer) takes into effect, and so it goes. Hmm. Then it becomes a shared-server model? Lost hosts: Current setup for discovering lost hosts is weird. I can probably make it "optional" in the sense that the network *should* run without it. Hopefully. And what's with peer desynchronization? That doesn't make sense. How should a peer discover that it's desynchronized? By expectation? What about the unreliability of UDP? Current definition of PMsP needs the underlying transport to be at least somewhat reliable. The actions/messages sent are "need to act" kind of messages-- i.e. if they aren't acted on/received, the whole network suffers.