Add to Favorites    Make Home Page 2061 Online  
 Language Categories  
 Our Services  

Home » C++ Home » Algorithms Home » Message Transfer In Cluster Computing


Search Projects & Source Codes:

Title Message Transfer In Cluster Computing
Author Nautin
Author Email noutin [at]
Description In this article improved version of new networking protocol for distributed or parallel computations is presented. In common, it is
suitable just for fast, reliable and featureful interchange of small messages. Protocol's implementation and demo project are provided.
Category C++ » Algorithms
Hits 323733
Code Select and Copy the Code
Commands Transfer Protocol (CTP) - New Networking Protocol for Distributed or Parallel Computations By dum In this article improved version of new networking protocol for distributed or parallel computations is presented. In common, it is suitable just for fast, reliable and featureful interchange of small messages. Protocol's implementation and demo project are provided. Introduction Computational cluster is a specific system that asserts special requirements for network functionality. Main properties of the networking mechanism for good quality cluster are: 1. Fast data interchange. 2. Reliable data interchange. 3. Broadcasting support. As usual, all workstations inside the subnet took part in the computational experiment, so broadcasting makes controlling easier. 4. Huge data blocks interchange support (interchange of such blocks takes place not so often, that means that it need not be extra fast). 5. Peer-to-peer networking. Any nodes can be data source and data destination, so they all are clients and servers simultaneously. In fact, majority of parallel computation software toolkits are represented as libraries, which use standard general-purpose networking protocols (TCP/IP [1], in most cases). There are a lot of disadvantages of using this protocol: Low speed of data interchange. The "reliability" and "universality" of TCP has a lot of overhead charges. TCP does not support broadcasting. UDP does, but it is not reliable and size of UDP datagram is limited by 65467 bytes [1]. Ideology of logical channel creation before data interchange is redundant for cluster computations. Firstly because, as usual, cluster is a well tuned, good working net. Secondly because, some strategies of cluster computing lead to disordered interchange between workstations. TCP is a stream-based protocol, but for determined task bounded blocks, interchange is preferable, because it allows to say definitely, when all necessary data have arrived. Of course, specialized networking protocol can be adapted to special requirements, which arise for cluster computations. So, CTP is a protocol that is to satisfy needs of arbitrary distributed parallel computations platform. Ideology The majority of existing toolkits for parallel computations use, so named, "messages" as basic abstractions. The basic abstraction used in CTP is "command". Command is an order from somebody to someone to do something (in most cases, workstations in clusters are communicating exactly in this way) or the response for such order. From last sentence, it is possible to conclude that command is characterized by following parameters: "somebody" - sender. "someone" - recipient. "something" - command's description. So, it is needed to define sender and recipient somehow. For this purpose, IP addresses will be used (the reason is that IP is used extremely widely). Commands will be identified by integer numbers. In terms of discussed protocol words, "command" and "message" are synonyms, because "command" is "message" (but not always vice verse). CTP needs to satisfy cluster networking protocol properties. The way in that this will be achieved follows (in the same order as in introduction): 1. For incrementing the speed of interchange, UDP will be used as the basis of the protocol (if IP was chosen for sender's and recipient's networking, it is obvious to use one of TCP/IP or UDP/IP ideology). 2. Reliability of data interchange is to be implemented. Each sent packet will be stored until receiver has not returned the confirmation of the receiving. For implementation of this mechanism, packets are to be provided with identifiers. Identification will be performed by assigning integer numbers on the sender-side. These IDs cannot be unique in general, but are to be unique for each sender. 3. Broadcasting support is one more argument to use UDP as the basic protocol. 4. Huge data interchange support is to be implemented. If a message that is greater than some limit (65400 bytes by default) is going to be sent then it is to be divided into smaller parts. These parts will be enumerated and sent to the recipient separately. On the recipient's side, these parts will be united to arrange the initial command. Recipient application will get information about it's arrival only after all its parts were received. Such commands will be named as "large messages", but on practice majority of commands are carried by normal messages (need single packet). 5. For peer-to-peer interchange CTP's implementations are to include both, client and server functionality, united in solid unity. CTP/IP's relationship with the OSI-model [2] and UDP/IP ideology is shown on pic. 1. Pic. 1. Relationship between OSI-model, UDP/IP-model and CTP/IP-model Implementation from the Theoretical Point of View Each CTP-packet is represented, as usual, as header plus body (data). The structure of header is shown in table 1 (in order of appearance). Name Size (in bits) Comment Packet size 16 Unsigned integer - size of the packet (including header) Command's number 16 Unsigned integer - command's number (from zero to 32767, highest bit is not set). If highest bit is set then packet represents a confirmation of the receiving of the message with the specified command. Packet's number inside the large message 32 Unsigned integer. For large messages - packets number, from zero to amount of packets (given by next field of the header) minus unity. For normal messages - zero. Amount of packets for the message 32 Unsigned integer. For large messages - amount of packets, needed for it's sending. For normal messages - zero or unity. ID 32 Unsigned integer. Identifier of message. Must be unique for each sender Message size 64 (only 48 are used) Unsigned integer - size of the whole message (without any headers). So, size of biggest command is 232*65400 (maximal amount of packets multiplied by maximal size of packet), that equals 280890861158400 bytes or more than 255 terabytes. That is near to unlimited size of the message. It is obvious that 48 bits are enough to store size value, but 64 bits were apportioned for alignment. Options 8 Set of bits. Each bit determines an option is set or not. Options will be discussed later. Table 1. CTP packets header Total size of the header is 25 bytes. Important note is that ID is an identifier of message, not of packet. Single packet can be fully identified by its sender, ID and number. Messages need only sender and ID for their identification. The uniqueness of ID for each sender is provided in the following way: initial value of ID of next message that will be sent is unity. After sending of each message, it is to be incremented. It is necessary to save it after any changing, to some local node's storage (in current implementation for Windows, it is stored in the registry to "LastID" value in running application's key "CTP") to protect systems from errors after restarting and after failure. The flowchart, that shows the sequence of operations for packet interchange is shown on pic. 2. 2. For sending the command, packets are to be arranged. Some memory is to be allocated and filled with packets headers and data. It will not be freed and unallocated just after sending, but stored to the sent commands storage (pointer to sent buffer and corresponding parameters). Record can be removed from sent commands storage only after all it's packets arrival have been confirmed. This ideology can be implemented not for "each command", but for "each packet" (like in CTP v. 1.0), but first variant is preferable. In this case, so named, "smart buffers" can keep from redundant memory allocations, by reserving memory, needed for headers, while packets data arrangement. One of the key parameters of CTP's implementation is, so named, timeout. If confirmation of packets arrival will not be received during timeout then packet will be resent. If it will not be confirmed during 5 timeouts, multiplied by amount of packets, used for this command, then error message "Command is not confirmed too long" will be generated. If timeout is set to zero then this feature will be switched off. First thing recipient does when it receives a packet is checking if same packet was already received (packet with same ID and number from the same sender). For this purpose, receiver looks through the received packets storage (list of structures that stores IP-addresses of senders, and lists of IDs and numbers of received packets). If such a packet was already received that means that sender failed to get the confirmation, so confirmation has to be sent again and this packet's receiving could be skipped. Confirmation exactly "has to be sent again", not "resent". Confirmations are not stored in the sent packets storage, but are generated when needed. If such a packet have not been received earlier, then information about it's arrival needs to be stored in the received packet's storage. This storage is to be limited, and if this limit will be reached, then the oldest record is to be removed from the storage. If got packet represents the normal message, then server informs the recipient about data arrival. If it is part of a large message, then server stores it to the large messages storage (list of large packet descriptors: sender, amount of received parts, total amount of parts and buffer for arranging the whole message). Each part of the message, except the last one, are of maximal datagram size, so parts can easily find their places in the buffer, knowing their numbers and the total amount of parts. After putting next part to the buffer, the amount of received parts is to be increased. When the number of received parts reaches the total amount of parts, the message is considered to be compiled and recipient can be informed about data arrival. The received packets storage keeps from putting the same part of the large message to buffer twice. That means that protocol is stable and errorless when the limit of received packets storage is greater than the amount of parts for the longest message. But on practice, there is no need to set this limit to 232, because first parts become not topical, after being confirmed, so value of limit several thousands, usually, will be enough. After the packet has found it's place, confirmation has to be sent, and then recipient begins to wait for the next packet. When sender receives any confirmation, it is to delete corresponding record from the sent packets storage. The received packets storage is freed only when CTP server is to terminate. The large messages storage is also freed when CTP server is to terminate. Single record is to be deleted from it after the whole message has been compiled. This means, that mechanism, like an alive creature, aspire to minimize it's potential energy, to free all storages as soon, as possible. Questions that can rise after explanations above are: what confirmation actually is, and how recipient application is informed about arrival of the message or error occurred while networking? Answer for the first question: confirmation is a packet with empty body (header only), which has only three differences between headers of the packet having been confirmed and the confirmation. In confirmations header: packet's size is set to header's size; in command's number highest bit is set; message size is set to zero. Answer for the second question: whole received message or error description is, so named, "delivery". Speaking in terms of object-oriented programming: objects, that implement recipient application, can subscribe to get deliveries for given command. In this case corresponding object will receive information about command's arrival, and about errors, which are related to this command. Also, there is to be default receiver that gets information about command, which has no subscribers, and about errors, which have no related commands. In conclusion, it is time to discuss available options of packets (last field of packet's header). There are three possible options: 1. ErrorOnce - if set, then information about sending this packet will be removed after receiver was informed that its arrival was not confirmed. So, this error will be sent only once. 2. NoResend - if set, then this packet will not be resent even if it was not confirmed. 3. UniqueCommand - if set, then confirmation of this packet's command will confirm all packets with the same command's number that were sent to given recipient. It is not allowed to use this option for large messages to protect it from integrity corruption. These options can be used in any combination: separately, all together and so on. For example, options set ErrorOnce + NoResend + UniqueCommand can be useful for commands like: "answer me if you are alive" (ping). For commands, that are sent often, which are small and which does not bring information, but response or confirmation does (recipient is working). Implementation for Windows CTP was implemented for operating system Windows to become basis of networking mechanism used in (Cellular Automata Modeling Environment & Library) project. Of course, it also could be used for arbitrary applications. Protocol's implementation is represented by a set of classes. The class that contains main functionality of CTP is CCTPNet. Description of all classes, which are involved in CTP's implementation follows. IPAddr Class Objects of IPAddr class represent IP-address of workstation. This class does not need any explanations except the source: union IPAddr { // Constructors IPAddr() {SetLocalhost();}; IPAddr(unsigned char b1,unsigned char b2, unsigned char b3,unsigned char b4) {Bytes.b1=b1;Bytes.b2=b2;Bytes.b3=b3;Bytes.b4=b4;}; IPAddr(unsigned long l) {Solid=l;}; // Returns true is this ip-address refers to localhost inline bool IsLocalhost() {return Bytes.b1==127&&Bytes.b2==0 &&Bytes.b3==0&&Bytes.b4==1;}; // Returns via s and return value dotted string //representation of ip-address inline STRING GetString(STRING s) {sprintf(s,"%d.%d.%d.%d",Bytes.b1,Bytes.b2, Bytes.b3,Bytes.b4); return s;}; // Set stored ip address to value, represented with string s (in // dot-separated format). Returns true if // succeeded and false otherwise bool FromString(STRING s); // Set stored ip address to localhost inline void SetLocalhost() {Bytes.b1=127;Bytes.b2=0; Bytes.b3=0;Bytes.b4=1;}; // Operators bool operator ==(unsigned long ip) {return Solid==ip;} bool operator ==(IPAddr ip) {return Solid==ip.Solid;} bool operator !=(IPAddr ip) {return Solid!=ip.Solid;} IPAddr& operator =(const IPAddr ip) {Solid=ip.Solid; return *this;} // Actual data struct IPBytes { unsigned char b1,b2,b3,b4; } Bytes; unsigned long Solid; }; Objects of IPAddr class represent "smart buffers", that save CTP's implementation from redundant memory allocations. It reserves place for packet's header once per definite size of data (maximum amount of data in single packet) on the fly. So user just put data to smart buffer. Then CTP's sending function adds headers and packets are ready to go. This class's definition CCTPNet Class Class implements main CTP's functions (client and server simultaneously). Following definition describes the members Implementation of protocol functionality is multithreaded. There are three types of threads: Server thread realizes confirmation support, error message generation and other necessary CTP specific networking functions. If data arrived or error information appeared, thread adds it to the deliveries list. On idle loop, thread can fall asleep for one tenth of timeout (or for 100 milliseconds if timeout is zero). Once per tenth of timeout, this thread checks existence of packets that need resending, and resends them if necessary. Delivery manager thread creates additional deliverer threads if all existing deliverers are busy and deliveries list is not empty. Of course, maximum amount of deliverers is limited by CCTPNet's parameter. Protocol's mechanism aspires to reduce loading. On idle loop, thread can fall asleep for 100 milliseconds. Deliverer threads check deliveries list and if it is not empty then deliver first delivery to corresponding subscriber or to the default recipient. If thread does nothing for a minute then it will be terminated. On idle loop, thread can fall asleep for (log10(number_of_idle_loops)+1)*50 milliseconds. Each command is order (or response). It can order to do something difficult and enduring. So implementation of deliverers in separate threads allows to compute something "by order". Nevertheless, it is strongly not recommended to use AfxMessageBox and modal dialogs in command receiving handlers, because it will keep deliverer busy uselessly. How to use all this? First of all, add files CTPNet.h, CTPNet.cpp, Network.h, Network.cpp to projects that are to use CTP. Then put following directives to StdAfx.h: // Include MFC multithreading support #include <afxmt.h> // Include STL #pragma warning(push) // Disable STL-critical warnings #pragma warning(disable: 4245) #pragma warning(disable: 4100) #pragma warning(disable: 4663) #pragma warning(disable: 4018) #pragma warning(disable: 4786) #pragma warning(disable: 4097) #include <list> #include <vector> #include <algorithm> using namespace std; // Enable STL-critical warnings #pragma warning(pop) // CRT library includes #include <sys/timeb.h> #include <time.h> #include <math.h> // Include Windows Sockets #include <Winsock2.h> #include <Ws2tcpip.h> These includes, except the last one, are put to provided file NetIncludes.h. It is necessary also to link WinSocket library ws2_32.lib to your project (choose "Project" | "Settings" | "Link" then type "ws2_32.lib" in "Object/library modules" edit field). Then, start Winsock up. For this purpose, for example, put following code in project's main window's initialization function: WSADATA wsaData; WSAStartup(MAKEWORD(2,2),&wsaData); After this, place following code to start CTP server up: m_pCTP = new CCTPNet("CTP",m_pCTPReceiver,1515,1000); // Server created suspended so it needs to be started manually m_pCTP->SetSuspended(false); Last code is correct in the assumption that m_pCTPReceiver is NetReceiver's descendant. Demo Application Demo application that is provided with this article shows usage of described CTP implementation. It also includes implementations of TCP and UDP in the same framework, so all these protocols can be used together and, obviously, can be compared (pic. 3). Pic. 3. Time of interchange via CTP, TCP and UDP (where possible) in microseconds versus size of message. Results of protocols research using provided demo project. Similar result of CTP and UDP shows that CTP's implementation doesn't use critical amount of resources. It's overhead expenses are small enough to be ignored. CTP is up to 70% faster than TCP while working with normal messages and messages that could be brought by several packets. That is great result, because the overwhelming majority of interactions in cluster are performed using normal messages. Order to start computations, query of some values and response for such queries are small. But TCP is better using large messages. Nevertheless huge data blocks appear in cluster computations rarely, for example, on the stage of task separation (and even here, not always). Important note is that CTP is not critically slow for large blocks, so it can be used as networking mechanism in cluster, paying attention to previous paragraph. Besides, test had been performed on two nodes, because it is more interesting here: pure protocols throughput. Results of comparing for rapid interchange between dozen of nodes are to be more pleasant for CTP, because it's activities will stay the same, but TCP will loose a lot on channels creating and recreating. For CTP does not matter, for whom to send. Reason, why it is impossible to overcome TCP, because it is on kernel level, but CTP is implemented by application. From one side - this is disadvantage of the last one, but from another, it is absolutely independent and complete.

Related Source Codes

Script Name Author
Moving ball screen saver karlmarx
The Classic Game of Snake & Ladder Lakshmi Narayana .A
Railway seat reservation question which comes in sapient VyomWorld
To calculate percentile Ravi Mathur
Send to folder ANIMESH SAHU
Analog clock and calendar Nazia & Rida
Data structure (stack Implimentation) Swapnil B Adsure
Memory Game AnirudhSanyal
Easy Calc Anirudh Sanyal
GK Quiz Anirudh Sanyal
Hangman Game Manish Jain
Snakeman Manish Jain
Full month Calendar Nigi
Cursor shapes nigi


Google Groups Subscribe to SourceCodesWorld - Techies Talk

Free eBook - Interview Questions: Get over 1,000 Interview Questions in an eBook for free when you join JobsAssist. Just click on the button below to join JobsAssist and you will immediately receive the Free eBook with thousands of Interview Questions in an ebook when you join.

New! Click here to Add your Code!

ASP Home | C Home | C++ Home | COBOL Home | Java Home | Pascal Home
Source Codes Home Page


Google Search


Source Codes is a part of Vyom Network.

Vyom Network : Web Hosting | Dedicated Server | Free SMS, GRE, GMAT, MBA | Online Exams | Freshers Jobs | Software Downloads | Interview Questions | Jobs, Discussions | Placement Papers | Free eBooks | Free eBooks | Free Business Info | Interview Questions | Free Tutorials | Arabic, French, German | IAS Preparation | Jokes, Songs, Fun | Free Classifieds | Free Recipes | Free Downloads | Bangalore Info | Tech Solutions | Project Outsourcing, Web Hosting | GATE Preparation | MBA Preparation | SAP Info | Software Testing | Google Logo Maker | Freshers Jobs

Sitemap | Privacy Policy | Terms and Conditions | Important Websites
Copyright ©2003-2022, All Rights Reserved.
Page URL:

Download Yahoo Messenger | Placement Papers | Free SMS | C Interview Questions | C++ Interview Questions | Quick2Host Review