Lei Xu
email: leixu@zju.edu.cn

Wenzhi Chen
email: chenwz@zju.edu.cn

Zonghui Wang

Huafei Ni

Jiajie Wu

Smart Ring: A Model of Node Failure Detection in High Available Cloud Data Center

Keywords: Cloud Data Center, High Availability, Node Failure Detection

Nowadays most of cloud data centers deploy high available system in order to provide continuous services, so it's very important for a high available cluster to detect the node failure (physical machine failure) accurately and timely in a low bandwidth occupation way. However, compared to the traditional cluster environment, the scale of cloud data center increases rapidly with the use of virtualization, so traditional node failure detection models have already faced several new problems. In this paper, we present a three roles and two layers node failure detection model, named as Smart Ring, which fits cloud data center well and strikes a balance between accuracy, instantaneity and bandwidth occupation. It can simultaneously detect the status of physical machines and virtual machines and deal well with multiple nodes failure and network partition. Our experiment results show that Smart Ring has a better performance than most existing models.

Introduction

In the past few years, many kinds of cloud services spew out. These services must serve continuously for 24 hours a day and 365 days a year with minimal maintenance. In addition, in many important fields,such as Finance, Traffic, Telecom and Military, once the system crashes, even if a short stop running, it may bring unimaginable consequences. So cloud data center should deploy high available (HA) system to provide the most stable network service and check out the node failure in time.

In our research we have found several kinds of failure detection models that have been applied in HA system. However, these models designed for traditional clusters can't fit well with data center. Because the number of machines has exploded rapidly in data center, especially the number of virtual machines (VM), most existed models have obvious bottlenecks when they are applied in cloud data center. They either consume more time to detect node failure, or occupy more bandwidth or easy to make misjudgments. What's worse, some of these traditional models don't support virtualization architecture that means they can't monitor the status of VM efficiently.

Considering the problems mentioned above, a novel model is proposed in this paper. We firstly introduce several classical node failure detection models in section 2. In section 3, we detail the design of Smart-Ring. Section 4 shows the extended functions of Smart-Ring. In section 5, we implement a prototype system to evaluate the performance of Smart Ring. A summary and plan of our future work are described in section 6.

Related Work

HA architecture has been extensively explored by cluster researchers in past years. This has led to the development of various node failure detection models. We have found many existing models used in HA system. These models can be summarized as five categories: Unidirectional ring is the simplest model. G Rudolph [START_REF] Rudolph | Parallel clustering on a unidirectional ring[END_REF] published a paper talked about parallel clustering on a unidirectional ring in 1993 and a patent of Symantec [START_REF] Pasqua | Cluster communication in heartbeat messages[END_REF] is also based on unidirectional ring. This model is very easy to make a misjudgment, because its judge logic is too simple.

Bidirectional ring is an upgrade of the unidirectional ring. Wang [START_REF] Wang | Stability and hopf bifurcation analysis in bidirectional ring network model[END_REF] and Savari [START_REF] Savari | The multimessage unicast capacity region for bidirectional ring networks[END_REF] et al. have discussed the bidirectional ring network model in their papers. This model can reduce misjudgment rate, because a node is judged invalid only when the precursor and successor both don't get heartbeat. However, it occupies double bandwidth as the unidirectional ring.

Centralized network is a kind of stellate reticulum model. The principle of Linux-HA project [START_REF] Robertson | Linux-ha heartbeat system design[END_REF] is similar with centralized model, Khan et al. [START_REF] Khan | Centralized framework with ring broadcasting for real time traffic in vehicular ad hoc networks[END_REF] and Hamlyn [START_REF] Hamlyn | Computer network distributed monitoring and centralized forecasting of utility distribution system operations[END_REF] have researched this centralized framework in distribution system. Nevertheless, if the central one is down, the system can't keep running which means it is the bottleneck of system.

Mesh network is a kind of full connection model. Only when all other nodes can't get heartbeat from a node the system judges this node is definitely down. This model has the highest accuracy while occupies the highest bandwidth. A famous HA project named Linux Failsafe [START_REF]SGI: Linux failsafe[END_REF] developed by SGI & SUSE is based on this model.

Token ring is a classic network model. Nilausen [START_REF] Nilausen | Token ring network management: Performance management[END_REF], Hutchison [START_REF] Hutchison | Simple token ring local area network[END_REF] and Goapl [START_REF] Gopal | Novel fault tolerant token ring network[END_REF] have done a lot of work around token ring model. This model can enhance reliability, so the grid fault-tolerant middleware GRM [START_REF] Siddesh | Grm: a reliable and fault tolerant data replication middleware for grid environment[END_REF] and group communication project Corosync [START_REF] Dake | The corosync cluster engine[END_REF] both use token ring network model. However, in this model,the cycle of fault detection is too long. It isn't suitable for applied in large scale virtual cluster yet.

Briefly, we can see that all these aforementioned models have their own features. But when focus on HA data center environment, they seem not to be suitable. Because they couldn't support virtualization architecture well and can't strike a balance among accuracy, instantaneity and bandwidth occupation. So based on long time of survey and study, we design a novel model which is fit for large scale HA data center.

A Novel Node Failure Detection Model -Smart Ring

Smart Ring has two monitoring layers as depicted in Fig. 2. At the physical machine (PM) layer, each node is monitored by precursor while VMs are monitored by their host PM at the virtual machine layer.

Smart Ring also has three node roles: leader, backup and common. When leader node is invalid, backup node will be elected to be new leader. When backup node is invalid, its first successor common node will change into backup. This process is irreversible. A short introduction about the features of these three roles should be made:

-Common node corresponds to an actual PM running with many VMs. Each common node has an IP list with three records corresponded to leader IP, backup IP and the first successor IP. With the first successor IP a common node can keep heartbeat with it, with leader IP a common node can inform a suspect failure to leader and backup IP will be the new leader IP after leader failure. This IP list is important for Smart Ring to maintain system operation. -Leader node is also a common node when there are no failures, that means in most of time it works as a common server. This design can make Smart Ring

Physical Machine Failure Detection

As mentioned above, nodes in Smart Ring have three different roles and the detection process of each role is different, we will describe respectively. Common node failure detection process. Now we assume node 3 is invalid, as shown in Fig. 3(a), node 4 wouldn't get heartbeat from 3 in appointed timeout. Then 4 will report this suspected fault to the leader node 0, 0 knows 4's precursor is 3 by checking the global view. 0 sends check info to 3 by Check Info Channel. If in the appointed timeout 0 can't get response from 3, in that way we think 3 is invalid, otherwise 3 is active. If 3 is indeed invalid, 0 will inform 4 to set its precursor as 3's precursor that is node 2, and 0 modifies global view and synchronizes with backup node 1. If node 3 is active, it indicates that there is only a link failure between 3 and 4, this link failure doesn't influence the normal work of node 3 and 4, so 0 will record this link failure in system log file, 4 will monitor 3 again after system administrator fixes this link failure. Backup node failure detection process. This process shown in Fig. 3(b) is similar with common node failure detection process. The only different is that if 1 is invalid, the leader node 0 will set node 2 which is the first successor of 1 as a new backup node and 0 sets its successor as 2. After that, 0 will update its successor info in its IP list, in the same way, 2 will update its precursor info too. Then 0 modifies global view and synchronizes it with the new backup node 2.

Leader node failure detection process. If leader is down, 1 wouldn't get the heartbeat from 0. Then 1 will inform all common nodes to check leader's status and then report the result to node 1. 1 will judge whether leader is active or not by all results. If most nodes (> N um All /2, N um All is the number of all nodes ) judge leader is invalid, 1 will change itself into new leader and set its successor as new backup and then inform all nodes to modify their leader IP and backup IP info recorded in their own IP lists. Otherwise the leader is normal, and it is just a kind of link failure. Just like common node failure detection process we describe above, system writes down this failure in log file and 1 will monitor 0 again after administrator fixes this failure. This process is described in Fig. 3(c).

Virtual Machine Failure Detection

The process of virtual machine failure detection is relatively simple. As VMM (Virtual Machine Monitor) can get current status of virtual machines by commands, for example, use "xm list" command in Xen VMM. We should just set a suitable interval, and a daemon process executes this command periodically to get the status of virtual machines repeatedly. If host machine finds a VM fault, it will remove this VM info from the VM list stored in it and then report to leader. After leader gets this VM fault report, it immediately modifies global view and synchronizes with backup without checking again. The command we used is shown as follows:

xm list|sed -n '3,$'p|awk '{print $1;print $5}'> xmstatus.info

Extended Functions of Smart Ring

Node failure detection is just a major and primary function of Smart Ring. Beyond that, it also has some extended functions which can deal with the problems in traditional HA system, such as multiple nodes fault and network partition.

Multiple Nodes Failure

In order to ensure that when multiple nodes fail simultaneously HA system still can work normally, we should just set more backup nodes. In a general way, if system meets the condition N um Backup ≥ N um F ault Where N um Backup is the number of backup nodes in supporting multiple nodes failure Smart Ring and N um F ault is the maximum number of faulted machines that we want our system to support. This can ensure the normal work of system, because there are enough backup nodes could become leader when leader and several backup nodes fail simultaneously.

There is a new problem after Smart Ring sets multiple backup nodes that is how to keep global view consistency between leader and all backup nodes. For solving this problem, we can import a GCS (Group Communication System) in Smart ring. GCS is a private channel between leader node and all backup nodes, and it can ensure that all group members can receive messages orderly and reliably. Our research group has respectively deployed Apache ZooKeeper and Spread in our Smart Ring to keep global view consistency which are both excellent GCS toolkit.

Network Partition

Network partition [START_REF]Symantec: Network partition[END_REF] is the condition that exists after all network connections between any two groups of systems fail simultaneously. When this happens, systems on both sides of the partition can restart applications from the other side resulting in duplicate services, or split-brain. A split brain occurs when two independent systems configured in a cluster assume they have exclusive access to a given resource (usually a file system or volume). The most serious problem caused by a network partition is that it affects the data on shared disks. For solving this problem, Smart Ring takes such a strategy: a) For a subgroup with leader node, it is a valid subgroup and keeps running only when it meets the condition N um N ow ≥ N um Most /2 . Meanwhile, the other subgroups are invalid. N um N ow is the number of this subgroup and N um Most is the number of nodes in the ring before network partition. N um Most is not a constant, its initial value is equal with the number of PMs and it will update after a network partition.

b) For a subgroup with backup node, first of all, backup changes into new leader. Then it counts up the number of nodes in this subgroup. If it meets the condition N um N ow > N um Most /2, it is a valid subgroup and forms a new ring. So the other subgroups are invalid and they must quit Smart Ring. c) For a subgroup with both leader and backup, it is treated as a valid subgroup no matter how many nodes in this subgroup. It will keep running while the other subgroups must quit HA system. d) For a subgroup without both leader and backup, it is treated as a invalid subgroup no matter how many nodes in this subgroup.

Through this strategy, we can ensure that there is only an optimum subgroup valid and this subgroup can form a new Smart Ring to keep HA system continuously running.

Performance Evaluation

For evaluating the performance of Smart Ring, we have implemented a prototype system to observe the time consuming of node failure detection and the bandwidth occupation. Our experiments ran on this environment shown as follows:

Node Failure Detection Evaluation

For the first experiment, we perform three groups of tests for 10 times each group. Firstly, we respectively calculate the average time consuming of one node failure detection among those five models we talked in section 2 and Smart Ring as a comparison. Then we calculate the average time consuming of two nodes failure detection in Smart Ring. At last, we calculate the average time consuming of three nodes failure detection which is the maximum number our experiment environment supports. As shown in Fig. 4(a), compared to other models, Smart Ring takes less time than the average level. Especially it spends the least time in VM failure detection which is the most possible failure in cloud data center. And we can see in the Smart Ring, VM failure takes the least time, leader failure takes the most and common failure takes the same time as backup approximatively. In Fig. 4 we can see it takes the same time approximatively as the situation of one node failure. We examine the capacity of three nodes failure detection in Fig. 4(c) as well. What to notice is that the time consuming of three continuous common nodes failure detection is different with those discontinuous and three VMs on the same host is different with those on the different hosts as well.

Bandwidth Occupation Evaluation

Smart Ring takes a tiny bandwidth occupation when HA system runs normally, because only heartbeat messages transferred between adjacent nodes occupy the bandwidth and VM failure detection executed inter physical machine doesn't occupy bandwidth neither. If there is a failure happens, bandwidth occupation will increase until a new ring forms. As we know the leader node which has the largest data flow is the performance bottleneck. So in our second testing, we compare the bandwidth occupation of leader node when a failure happens in Smart Ring with the other five models. Fig. 5(a) shows the bandwidth occupation evaluation result among Smart Ring and other five models. Smart Ring is just a little higher than unidirectional ring model but a great fewer than others. From Fig. 5(b) we can know that Smart Ring just occupies about 22KB/s when HA system runs normally. But when a fault happens at the 5 th second it will increase until a new ring forms. For a VM fault or a common node fault the bandwidth occupation is about 55KB/s, while for a backup node fault or a leader node fault it is about 97KB/s. Because synchronizing the whole of global view occupies a little bandwidth. In addition, we can see the time from bandwidth occupation increases to it restores coincides with our first test results.

Conclusion and Future Work

In this paper, we have presented a three roles and two layers node failure detection model. To the best of our knowledge, this work is a kind of novel design and implementation of node failure detection that could be applied in a big scale cluster with plenty of VMs like a cloud data center. We have detailed how to detect a node failure quickly and exactly with a lower cost, support multiple nodes fail simultaneously, solve network partition problem. Moreover, we have evaluated Smart Ring within a 64*100 machines scale cluster.The result shows that Smart Ring has a higher accuracy compared to unidirectional and Bidirectional ring, a lower bandwidth occupation compared to centralized ring and mesh network, and a lower time consuming of node failure detection compared to token ring.

Nevertheless, our design has some limitations that we plan to address in the future. We now can't support discontinuous backup nodes and detect the status of VMs in a simple way through the VMM commands. Finally, it's just a beginning of Smart Ring of design, implementation and performance evaluation. Various other measurements and optimization strategies will need to be explored in the future.

Fig. 1 .

 1 Fig. 1. Traditional node failure detection models

Fig. 2 .

 2 Fig. 2. Smart Ring model

Fig. 3 .

 3 Fig. 3. Node Failure Detection Process. (a)Common node failure detection process. (b)Backup node failure detection process. (c)Leader node failure detection process.

  (b), we examine the capacity of Smart Ring in two nodes failure detection where 2C means two Common nodes failure, 2B means two Backup nodes failure, C & L means a Common node and a Leader node failure and on. From the results,

Fig. 4 .

 4 Fig. 4. Node Failure Detection Testing

Fig. 5 .

 5 Fig. 5. Bandwidth Occupation Evaluation

Table 1 .

 1 Experiment environment

	PM Numbers	VM Numbers	CPU Frequency (GHz)	CPU Cores	Memory (GB)	Network (Mb/s)	Leader Numbers	Backup Numbers	Common Numbers
	64	6400	3.3	4	4	100	1	3	60

This research is funded by National Natural Science Foundation of China under grant NO. 60970125.


Shahnawaz Talpur
email: talpur@bit.edu.cn

Feng Shi

Yizhuo Wang

Communication Locality Analysis of Triplet-Based Hierarchical Interconnection Network in Chip Multiprocessor

Keywords: Chip multiprocessor, communication locality, interconnection network, mesh

de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

In computing, performance can be achieved by reducing data access latency, which is dependent on interconnect network on-chip. The issue of the highest performance on significant applications is the main effort of the microprocessor architecture, which also meets the limitation in the design time, power consumption and the area [START_REF] Codrescu | Architecture of the Atlas chip-multiprocessor: dynamically parallelizing irregular applications[END_REF]. CMP is much more promising because it is partitioned into individual processing cores and has simple design scalability with great performance/power ratios and the potential to provide higher peak throughput [START_REF] Rakesh | Tullse: Interconnections in Multi-Core Architectures: Understanding Mechanisms, Overheads and Scaling[END_REF].

In parallel with interconnection network, Cache organization has also the main impact on data latency which can affect the performance of multicore. Association of memory hierarchy, the operational work load and interconnection on-chip are the factors on which data access latency is built-up. Rapid path or routes are assembled for reducing latency in several Network-on-chip designs, utilizing communication locality [3]. Latency on data stored in cache on-chip can be suffered by interconnection network, while the distance in blocks of data stored on cache can be affected by cache association. This affects the overall communication model against NoC.

Multicore has one decisive issue, the locality, which is alienated in temporal and spatial. When two or more cores access shared data in short time, it is known as temporal locality, whereas; in flat time, one core's data is accessed constantly by other core(s), known as spatial locality. Data latency will be even more critical issue as the number of cores increases in the system.

Packet interconnection network is an extensive approach in recent research, for controlling on chip communication. Wires deliver the suitable electrical constraint in structured network, which allows high recital circuits to raise bandwidth and dipping latency [START_REF] William | Route Packets, Not Wires: On-Chip Interconnection Networks[END_REF] [START_REF] Ching | Integrated Modeling and Generation of a Configurable network-on-chip[END_REF]. Researchers conclude that the power efficiency should be balanced with wire utilization through topologies.

The mature topologies, explored by parallel computing, such as complete connection, torus and cube are all too complex to implement on a single chip. Recently, 2-D mesh is much focused for implementation as interconnection network in CMP [START_REF] Kumar | A network on chip architecture and design methodology[END_REF]. Although it is not expected that it will benefit at all.

The rest of the paper is prepared as follows: Section 2 presents TBHIN topology and node addressing. The static analysis and dynamic analysis are given in Section 3. We compare TBHIN with 2-D mesh on the condition of existence of communication locality. Section 4 consists of related work and Section 5 concludes this paper.

Triplet-Based Hierarchical Interconnection Network

Fig 1 illustrates the basic TBHIN topology and it can be seen that its structure is similar to Sierpinski Gasket, which is a fractal object. Iterartor Function System (IFS) produces Sierpinski Gasket according the theory of fractal geometry [START_REF] Feng | A Triplet Based Computer Architecture Supporting Parallel Object Computing[END_REF]. Single node in a scalable and hierarchical interconnection network described as a lowest level 0 TBHIN. On next step level 1 three cores shaping one triangle. The level 2 consists of three triangular shape communication links [START_REF] Baojun | A New Routing Algorithm in Triple-based Hierarchical Interconnection Network[END_REF], as shown in Fig. Using Iterated Function System (IFS), higher levels of TBHIN can be generated from level 1. Assume that IFS for this design is IFS {F1, F2, F3}. Level 1 TBHIN N(1) is the outcome after one iteration of IFS and N (k) represents level k, after kth iteration that is the result of IFS. Then the procedure of TBHIN structure can be represented by

  3 1 1 i kk i F NN    (1)
Based on level 1 each core builds an upper level TBHIN. For the convenience three sub-networks of N(k) are described here as Triplet 1 ,Triplet 2 and Triplet 3 [START_REF] Bin | Triplet-based architecture and its process migration mechanism[END_REF]. However; in order to understand the organization and binary representation of basic addressing scheme of TBHIN, we show only the 2 levels of TBHIN in the following Table 1. The ratio of the result of sum of minimal path lengths between two nodes to the total number of paths in the networks is known as mean minimal distance (MMD) of network [START_REF] Dong | Exact Computation Of The Mean Minimal Path Length Of N-MESH AND N-TORUS[END_REF]. The estimated MMD of TBHIN can be calculated as [START_REF] Weixing | Study on an interconnection network for complex embedded systems[END_REF]:

    1 16 6 1 1 5 1 1 3 3 3 3 3 3 3 16 6 1 11 3 5 3 3 k kk k avg k k k k k kk D P                   (2)
Where D k is sum of all shortest distance and, k is level of TBHIN.

Performance analysis of network

This section analyzes the performance of TBHIN. Through this analysis, it is showing the advantages of this interconnection network in comparison to 2-D Mesh, most commonly used network on chip. TBHIN uses less number of links than 2-D mesh, but it provides larger MMD. Section 4.1 presents a performance analysis assuming that there is no contention. Section 4.2 presents contention analysis and the simulation experiments that are on the queuing analysis.

Analysis with No Contention

Here, we consign all assumptions and performance comparison standards proposed in [START_REF] Dandamudi | Hierarchical Interconnection Networks for Multicomputer Systems[END_REF]. In this paper, we consider  as the probability at both the source and destina- tion nodes of a message in the same sub-network, whereas; in [START_REF] Dandamudi | Hierarchical Interconnection Networks for Multicomputer Systems[END_REF]  is the probabil- ity at both the source and destination nodes of a message in the same cluster. Therefore     represents the probability of different sub-networks communication.

Communication locality is stronger if the value of  is larger. Denoting m q the probability of both source and destination nodes of a message being in N (m) and ' m q is the probability of a message being in N (M), but not in the same sub-network N (m-1). For N (k), we have:

      1 2 2 1 2 1 1 2 1 1 11 11
11 1 k k k k k k k q q q q q q q q q q                              (3)               2 1 2 3 2 2 1 2 1 1 1 1 1 1 1 1 1 1 k k k k k k q q q q q q q q                         (4)
For larger value of , the probability of inter-sub-networks communication will be smaller. As in [START_REF] Dandamudi | Hierarchical Interconnection Networks for Multicomputer Systems[END_REF], the cost and complexity of network N(k) is represented with ), which gives a cost-benefit part of static performance and should be minimized. For N(k), the total number of links can be presented as:

1 1 3 33 kk L LL       (5)
From Eq. ( 11) we can know that:

  3 3 1 / 2 k k L    (6)
Denote ' k P as the source and destination nodes, which reside within the same network of N(k), but not within the same network of Triplet.

        ' ' ' ' ' ' 1 1 2 2 3 3 2 2 1 ' ' ' ' 1 2 3 1 1 1 1 1 k k k
kk kk P Pq P q P q P q

P P P P P                          (7)
According to [START_REF] Weixing | Study on an interconnection network for complex embedded systems[END_REF] suppose i v and j v are two nodes and they belongs to two different Triplets.

              1 1 1 1 1 1 11 3 3 3 3 3 3 11 12 21 1 1 1 1 1 1 ' 1 1 1 1 33 1 1 1 1 12 21 11 11 1 1 1 1 11 , , 3 3 1 , 3 3 3 3 3 , 3 3 1 3 , 33 2 3 3 3 1 33 k k k k k k kk kk i j i j i j i j i j k k k k k k k k k ij ij kk k k k k kk d v v d v v d v v P d v v d v v Q                                                       (8)
From Eq. ( 8) and already calculated sum of shortest distance from any node with Triplet N(K) [START_REF] Weixing | Study on an interconnection network for complex embedded systems[END_REF]

1 1 1 1 ' 1 11 2 3 3 3 1 21 3 3 3 k k k k k k kk Q P               (9)
And because

Thus from Eq. ( 7), Eq. ( 9) and Eq. ( 10) we can know:

      1 8 1 2 1 1 3 2 1 k k k P               (11)

Fig. 2. The group scheme for 2-D mesh

To compare with TBHIN, every four nodes of 2-D mesh are grouped together as a sub-network, as shown in Fig. 2. After that four groups constitute a bigger group.

Analogically, the 2-D mesh with 4 k N  nodes can be considered as a k hierarchy network. The number of links and MMD of 2-D mesh are listed below:

    2 2 4 2 kk k L N N       (12)   , 21 22 2 33 3 k avg k N PN N      (13)
Like TBHIN, suppose the probability of communication locality is  , yielding:

        1 2 2 1 ' ' ' ' 1 2 3 1 16 1 44 1 1 1 1 kk k k k P P P P P P P                            (14)
' k P is given by:

k k k k k kk k k k k k PP P                (15)
Eq. ( 14) and Eq. ( 15) then give:

      28 1 7 2 1 2 1 k k k P            (16)

Analysis with Contention

The analysis with contention becomes more complex, since we have to consider the competition for communication resources among messages. In order to simulate the transition of messages over network, we assume that every link is full-duplex in the network. Each full-duplex link in our study is conceptually sub divided in two halfduplex links, each of which is modeled as a queuing center [START_REF] Dandamudi | Hierarchical Interconnection Networks for Multicomputer Systems[END_REF]. Between the source and destination nodes, all messages are routed over the shortest path. We also suppose that all the messages have the same size and the capacity of link buffers is unlimited.

The simulation process is composed of consecutive steps; following tasks should be finished within each step: 1. Each node generates λ pieces of messages, whose source and destination nodes are randomly obtained according to the distribution of probability. The shortest path from source node to destination nodes is calculated using the algorithm proposed in section IV. Meanwhile, the message is sent to the waiting queue of the first link. Additionally, the shortest path is attached to the corresponding message. 2. Each link picks up μ pieces of messages from the waiting queue, and sends the message to the next link according to the attached routing information. When message reaches the destination node, calculate the total delay and delete the message.

3. Calculate the average delay by dividing the total number of messages into total delay of all messages.

RELATED WORK

Interconnection network on-chip emphasized more intensely as a prominent factor in Communication locality. In [3], interconnection for cache scheme and design circuit is classified periodically for the improvement in communication latency. Study essential diverse approach focuses on hindrance in locality and partitioning internal memory between cores in CMP shared memory system for reducing locality obstruction [START_REF] Kyu | Balancing DRAM Locality and Parallelism in Shared Memory CMP Systems[END_REF]. When data is shared among processors, allowing diverse application, optimal data locality scheme has been expressed with inimitable characteristic [START_REF] Kandemir | Data locality enhancement for CMPs[END_REF]. Parallel program and locality is achieved by enabling direct manipulation of tiles expressed in [START_REF] Bikshandi | Programming for parallelism and locality with hierarchically tiled arrays[END_REF]. Optimal behavior of cache memory is stated and using sampling techniques elucidate the predictable scheme for CMEs solution in [START_REF] Xavier | A fast and accurate framework to analyze and optimize cache memory behavior[END_REF]. In literature survey of [START_REF] Abhinav | Benefits of Topology Aware Mapping For Mesh Interconnects[END_REF][18], latency improvement is explored in hop count, topology mapping, different mesh dimensions and interconnects graph etc. Data in groups is accessed collectively with reference to the association in memory as expressed in [START_REF] Zhang | A hierarchical model of data locality[END_REF]. Despite the fact that, many of the researcher's proposed simple 2D packet-switched mesh interconnects for the cache. The novelty of our analysis demonstrates that Triplet based hierarchical internetwork can be replaced as improved one. Due to different attributes of each methodology for data accessing, cache/memory hierarchy can't fully benefit from 2D interconnections.

Conclusion

In this paper, we investigate communication locality between Triplet-Based Hierarchical Interconnection Network and 2-D mesh. It has been found that TBHIN is easily scalable and has better cost benefit ratio than 2-D mesh in case of higher communication locality. It is also observed that TBHIN dynamically performs much better than 2-D Mesh because of having lower average delay. Due to the facility of hardware implementation, it can be used as the interconnection network of CMP.

1

 1 Fig 1 illustrates the basic TBHIN topology and it can be seen that its structure is similar to Sierpinski Gasket, which is a fractal object. Iterartor Function System (IFS) produces Sierpinski Gasket according the theory of fractal geometry[START_REF] Feng | A Triplet Based Computer Architecture Supporting Parallel Object Computing[END_REF].Single node in a scalable and hierarchical interconnection network described as a lowest level 0 TBHIN. On next step level 1 three cores shaping one triangle. The level 2 consists of three triangular shape communication links[START_REF] Baojun | A New Routing Algorithm in Triple-based Hierarchical Interconnection Network[END_REF], as shown in Fig.1

Fig. 1 .

 1 Fig. 1. Triplet-Based Hierarchical Interconnection Network Level 2(TBHIN)

  is used to present the efficiency of the network N(k). Therefore, a use- ful measure is the product of k

Fig. 3 .

 3 Fig. 3. The comparison of LP with α=0.7 and N=256 Fig. 3(A) gives LP comparison of TBHIN and 2-D Mesh, when is 0.7 as function of the all nodes in the network; it could be observed that TBHIN has lower LP than 2-D Mesh. In Fig. 3(B), N is fixed at 256 and the value of  is increased, to increase the probability of communication locality. The graph of Fig. 3(B) indicates that TBHIN has lower LP value when  is larger than 0.3, which proves better cost benefit ration than 2-D mesh on the condition of

Fig. 4 (

 4 Fig.4(A) gives the average delay of messages along with the simulation steps. As we can see, the higher the communication locality, the shorter will be average delay. What's more, the network will be stable much more quickly. In reverse, the average delay becomes longer. And what is worse, the network may paralysis due to the heavy workload. In fig.4(B), the average delay of TBHIN is around 25% lower than 2-D mesh when 0.6, 81, 1, 2 N        . Therefore, Triplet-Based Hierarchical Interconnection Network dynamically performs much better than 2-D mesh.

Fig. 4 .

 4 Fig. 4. The comparison of message delay

Table 1 .

 1 TBHIN Adressesing

		Triplet 1(01)			Triplet 2(10)			Triplet 3(11)
	Core 1 Core 2 Core 3 Core 4 Core 5 Core 6 Core 7 Core 8 Core 9
	0101	0110	0111	1001	1010	1011	1101	1110	1111


You-Sik Hong
email: yshong@sangji.ac.kr

Hongkyun Kim

Cheonshik Kim

Geuk Lee

New Electronic Acupuncture System using Intelligence

Keywords: Pulse wave, Fuzzy Rules, Acupuncture

n recent years, scientific studies of traditional oriental medicine are accelrating. Furthermore, researches of medical examinations and treatments through collaboration of oriental medicine and western medicine is in progress. This paper will seek for spots on the body suitable for acupuncture using special features that skin impedance values are different. The computer simulation results have shown that Electro-Acupuncture administered by using the medical diagnosis system developed in this study is more effective than the conventional method.

Introduction

In oriental medicine, the term 'pulse' has several meanings. The pulse is considered an important factor in herbal remedies, since observation of a person's pulse rate may reflect their health and illness [START_REF] Lee | Study on the characteristics of blood vessel pulse area using ultrasonic[END_REF][START_REF] Lee | Designing a stabilized process of pulse analyzing method using sigma 6[END_REF][START_REF] Lee | Diagnostic atlas 2 analyzing pulse[END_REF]. The observation of heart palpitations is critical as the cessation of a person's heart palpitations classify them as dead. Therefore, the condition of the instant heart change is observed in both western medication and eastern medication, and we can diagnose it by feeling the pulse. Since ancient times, oriental doctors have considered pulse rate as an important data in diagnosis. Accordingly, a doctor who was competent in checking the pulse of their patient was considered a creditable doctor. However, the current blood pressure pulse analyzer may be considered flawed, since it is uncertain whether the blood pressure pulse analyzing sensor is located precisely on the radial artery. Furthermore, the analogue type blood pressure pulse analyzer has the issue of objectifying the blood pressure pulse. Although some people may have the same forearm length, the thickness of their blood vessel may differ, and therefore there is no set of data that is considered reliable enough to judge the accuracy of blood pressure pulse rates. [START_REF] Gunal | Subspace based feature selection for pattern recognition[END_REF][5][START_REF] Garg | A Fuzzy Petri-nets for Knowledge Represent-ation and Reasoning[END_REF][START_REF] Genrich | System Modelling with High-level Petri Nets[END_REF] In this paper, in order to calculate the best optimal time of Electronic-Acupuncture, it will consider the patient's physical conditions, age conditions and disease conditions [START_REF] Leung | Fuzzy Concepts in Expert Systems[END_REF][START_REF] Looney | Logical Controls via Boolean Rule Matrix Transformation[END_REF][START_REF] Looney | Fuzzy Petri Nets for Rule-based Decision Making[END_REF][START_REF] O'rourke | The Arterial Pulse[END_REF][START_REF] Gong | Quantitative investigation on normal pathological tongue shape and correlation analysis between hypertension and syndrome[END_REF]. As the computer simulation resulted, Electronic-Acupuncture using the intelligence had proven to be more efficient than the existing method. The composition of this paper is as follows: section 2 discusses the multipad with a built-in Electronic-Acupuncture ; section 3 discusses the fuzzy rules based on pulse wave analysis. Section 4 reports the results of Electronic-Accupuncture simulation and section 5 concludes this paper.

E-Acupuncture pad with built-in multi-active

What is a multi-pad with a built-active JEUNJACHIM (Electronic-Acupuncture) depending on a patient's current body status? Based on this information, the patient meets the voltage and current self-oscillation. The frequency with the ability to automatically advanced procedure is called JEUNJACHIM. In order to perform these functions simultaneously with the sensing of JEUNJACHIM, one is required to possess the ability to perform surgery, derive accurate analysis from fuzzy logic and process statistical data. Electrical resistance of the body including long-term resistance, internal resistance and the surface can be divided into exposed skin. Resistance of the body when the DC voltage is based on the pure resistive component can be considered only based on the basis, when the impedance of the AC voltage should be considered. That body electrical conductors if you think skin, blood, muscles and other body each part of the voltage and current for the resistive component and capacity components are separated by impedance and its size, the electrical conduction path, the contact voltage, the contact area, and energizing time, is applied differently depending on the frequency may occur. Figure1 illustrates the basic theory of Electronic-Acupuncture. In addition, these changes in a person's age, gender, humidity, temperature, weight and fat accumulation is based on the changes. The requirements when considering the electrical resistance of human skin in general is based on the amount of approximately 2500Ω. However, the same voltage and current is applied even if the amount of contact area and pain change in resistance over time are different. In the electrical resistance of human body tissues, regardless of the DC and AC power is almost constantly appear if time longer JUAL heat due to temperature rise of tissue resistance is slightly reduced. When the electricity in the human body typically conduct a minimum of power to feel the flow of the AC voltage is 1mA ~ 2mA for men. In contrast, direct the flow of power is smaller than the stimulus at least five double-road sensing current flow caused by the voltage applied, even though I do not feel the flow of electricity. Thus, in the treatment of JEUNJACHIM, electricity is AC rather than DC voltage with the voltage of the aneurysm and the frequency and voltage, over current change as a real hand acupuncture procedures, a small battery that has the same effect as a treatment is likely to be seen.In the experiment, according to AC current that can safely come off as self a man 16mA (60Hz) women 10.5mA (60Hz) is about the human body can withstand DC current is approximately 74mA men for women is approximately 50mA .But it also including a person's body size and weight may appear slightly different depending on the requirements. In this paper, the voltage between 15V ~ 50V AC voltage to the change of 5Hz ~ 1.2Khz and current 500uA ~ 1500uA given in the current experiments were carried out. Figure 2 illustrates the electronic acupuncture circuit

Fuzzy rules considering the patient's condition

The general algorithm comes to a conclusion of B on the assumption of 'A → B and equals A'. In this case the latter A should be completely consistent with the former A (of conditional clause). This kind of inference is called Modus Ponens and the Fuzzy algorithm is trying to expand as follows which will be called GMP (Generalized Modus Ponens); Assumption 1: If x equals A,y will be B. Assumption 2: x equals A'. Conclusion : y equals B'. When you use the Fuzzy Rules, the knowledge to judge a patient's health by using the pulse wave will be expressed in Fuzzy R and you will be able to carry out modeling like the following to observe Output (or Symptom) B to clarify Input (or Cause) A. If you are not careful for actual pulse feeling, often you may be confused that floating pulse, sliding pulse, and big pulse are powerful while submerging pulse and small pulse aren't. However, some floating pulse, big pulse, and sliding pulse are weak and some submerging pulse and small pulse are strong.

If 4 patients, a, b, c, and d are in their terminal stage, the left figure will be ranging from 0.8 to 1.0 and if in the middle stage, from 0.4 to 0.7 and if in the initial stage, from 0.1 to 0.3. The figure in the middle indicates the patient's physical condition. For example, if a patient is 150 cm high and weighs less than 45 kg, the figure will range from 0.1 to 0.3, if he is 151 -170 high and weights 46 -70kg, from 0.4 to 0.7, and if he is 171 -200 cm high and weighs 71 -130kg, from 0.8 to 1.0. This illustrates the Fuzzy conversion factor to adjust the correlation coefficient in consideration of the weight, age, gender, and physical condition when you analyze patient health condition. The evidences of this kind of hypothesis are atopic disease, acne, and age spot. This skin related troubles happen because the diseased spots have high resistance of electricity. High resistance to electricity means inappropriate oxygen provision therefore the skin disorder occurs in various ways such as atopic disease or age spot. Existing blood pressure pulse analyzing system doesn't consider patient's sex, age, and condition therefore there is an inadequacy of choosing the right amount of pressure to press the needle into patient's skin. It also has a problem of inaccuracy in finding the right acupuncture points. Therefore if a needle is used on an aged patient or a young patient with weak skin it might leave bruises or wounds. In this paper, it tried to solve these problems using intelligent fuzzy rules.

e=R-Y Ce=e2-e1

Where, Y: optimum pulse feeling judgment R: Criteria Input e: Error Ce: Error Displacement e2: Current Error A global priority reflects the importance of an element with respect to the focus of the problem. The derivation of local priorities is carried out through the use of a comparison scale and a pair wise comparison matrix. A comparison matrix for deriving the priority vector is associated with 3 elements in a specific level with respect to a single element in a level immediately about it. Such a matrix is denoted by A.

In this matrix every element is the result of a pair wise comparison denoting the dominance of element i relative to element j. A comparison is also being made of the j th element with the i th element. The fuzzification membership functions in a fuzzy rule base are triangular typed ones defined by equation ( 1

           otherwise U u b u a a x a b y , 0 , ), ( 2 (1)
This interval includes all possible values for the variable in universe of discourse( U ). All fuzzy sets in a fuzzy rule base have the same support interval ] , [ b a . The equation can be represented all types of fuzzy membership functions both fuzzy and non-fuzzy membership functions. The oriental medicine is adopting 4 diagnosis methods such as seeing, hearing, inquiring, and touching but among those is there tongue feeling system in which a doctor will see a patient's tongue for diagnosis. This method has been used to observe the tongue condition or fur deposited on it to diagnose any disease and its kind from the ancient times. Observation of the tongue is mainly used to understand functioning of the heart and spleen. If the tongue fur is white, the corresponding disease is in its initial stage or light, indicating False Symptom, Cold Symptom, and Humid Symptom. If it is yellow, it indicates heat is accumulated in internal organs, most commonly acute fevers.

Fig. 4 illustrates the automatic detection of RGB images which is most similar to the patient's health judgment condition among those tongue feeling images to make the oriental medicine scientific. Moreover, this thesis has developed an algorithm for more accurate judgment of the quantity of tongue furs and the sublingual veins by using the ultraviolet ray and infrared methods. Fig. 4 illustrates the Pulse wave decision system using fuzzy rules which depending on the patient's physical condition. In this paper, it is tried to classify the difference in physical characteristics such as thickness of skin and blood vessel, skin impedance, glandular nature of skin in order to come up with an accurate pulse analysis.

Simulation

In this paper, in order to solve this kind of problem, it uses compositional inference while using the fuzzy rule. Fuzzy compositional rule of inference is applied to come up with a calibrating constant in order to derive an accurate result (considering the patient's physical condition) in analyzing the blood pressure pulse. In existing method, an oriental doctor infers one pulse wave out of 28 pulse wave and diagnoses the patient. Fuzzy compositional rule of inference is a rule made in order to come up with an inference by using fuzzy production rule which includes fuzzy variables. The form of fuzzy compositional rule of inference is as in the following. Belief of fuzzy composite function: If fuzzy compositional rule of inference is applied in fuzzy production rule then belief of fuzzy evaluation function can't be used. So in order to calculate the belief of fuzzy function, the belief of fuzzy composite function is used. βc = βcomp(β(βf, βr)) = min (max (β (βfp, βrpq)))

In here, p=1, 2, ⋯ , m, q = 1, 2, ⋯ , n. m, n are the number of each fuzzy thesis in premise and conclusion. Belief of fuzzy union function in type 1 and 2 of fuzzy production rule which are the minimized version of type 5 and 6 can come up with the same node or conclusion using different inference. In this kind of node, same conclusion has two or more different belief of function. In this type of situation, in order to recalculate the belief of fuzzy function, fuzzy union function is used. Then, the electric route creation part outputs the electric pattern by the patient condition and A/D and D/A is executed to process the pattern after delivered from the sensor. In this paper, the blood pressure is converted into a form for facilitating judgement via 1st and 2nd derivative and the electrode to measure the conductivity filters each delivered signal to create the input data required by the Fuzzy logic.

Conclusion

This paper calculates the optimal time for Electronic-Acupuncture using fuzzy rules. In order to calculate the exact acupuncture time, it considers physical condition, illness conditions and age conditions. However, this classification scheme depending on the patient's illness conditions vary greatly. To improve these problems, it adjusts the acupuncture time depending on the patient physical conditions. Since the oriental medicine can check human's health and disease condition by observing the pulse beating condition, the herbal treatment considers the pulse very importantly. The oriental doctor has regarded the pulse as an important data in diagnosis from the past. However, the existing pulse stethoscope was not good enough to confirm if the pulse wave detection sensor was positioned exactly on the aorta radial. Furthermore, it was difficult to feel for accurate pulse of a person with a thick forearm and different body type to the person with a thin forearm. The health judgment by using existing pulse feeling has generated ambiguous problems with accurate judgment due to an oriental doctor's subjective data analysis. In this paper, we applied the Fuzzy algorithm to analyze such a problem and draw an inference from objective data in view of pretreatment and applied the electrical characteristics of pain parts which respond to acupuncture antidune in view of post-treatment to propose the scientific pulse feeling system algorithm and simulation experiment.

Fig. 1 .

 1 Fig. 1. multipad with a built in electronic acupuncture

Fig. 2 .

 2 Fig. 2. Electronic acupuncture circuit.

Fig. 3 .

 3 Fig. 3. Patient Health Condition using Fuzzy Rules

  rule base composes of MISO (Multi Input Single Output) typed rule base. Each fuzzy membership function in a fuzzy rule base has a membership value area ] normalized in this area.

Fig. 4 .

 4 Fig. 4. Pulse wave decision system using fuzzy rules.

Fig. 5 .

 5 Fig. 5. Intelligence DSP Board Firmware Fig. 5 shows the sequence of DSP Board Firmware. The sequence can be classified into 4 major categories. They are Main Part for main process, Sensor Signal Input & Processor, Data Indexing Processer to create accurate information data on the basis of the sensed data and Fuzzy Logic Driver to create the result data. After power supply, all the register functions of DSP and related memories and variables are initialized.Then, the electric route creation part outputs the electric pattern by the patient condition and A/D and D/A is executed to process the pattern after delivered from the sensor. In this paper, the blood pressure is converted into a form for facilitating judgement via 1st and 2nd derivative and the electrode to measure the conductivity filters each delivered signal to create the input data required by the Fuzzy logic.

Acknowledgments

This work was supported by the Security Engineering Research Center, granted by the Korea Ministry of Knowledge Economy.


Hsing-Chung Chen

Jai-Zong Sun

Shian-Shyong Tseng
email: sstseng@asia.edu.tw

Chien-Erh Weng
email: ceweng@mail.nkmu.edu.tw

A New Approach for Detecting SMTPFA Based on Entropy Measurement

Keywords: SMTP, Entropy, Attack detecting, SMTP flooding attack

In this paper, we propose a new approach of detecting a kind of Simple Mail Transfer Protocol Flooding Attack (SMTPFA for short) based on entropy measurement. We will calculate the entropy values from the received packets flow. Further checking its entropy value compared with the values of abnormal entropy, we then use it to detect this server whether is suffered some attacks from hacker. The scheme can easily detect SMTPFA, and monitor the real-time status of SMTP server.

Introduction

In recent years, with the rapid development of the networks, people communicate of long range gradually shift from use the traditional post letter becoming to use e-mail delivery. Today, e-mail has become one of necessary communication tools for Internet users. In 1982, the early stage of e-mail development, the SMTP (Simple Mail Transfer Protocol) is formulated in RFC 821 [START_REF] Postel | A SIMPLE MAIL TRANSFER PROTOCOL[END_REF]. Owing to RFC 1939 [START_REF] Myers | Post Office Protocol -Version 3[END_REF], RFC 2821 [START_REF] Klensin | SIMPLE MAIL TRANSPORT PROTOCOL[END_REF] and RFC 3461 [START_REF] Moore | Simple Mail Transfer Protocol (SMTP) Service Extension for Delivery Status Notifications (DSNs)[END_REF] are formulated in the RFC standard, the e-mail protocol has been gradually completed.

A simple e-mail server (SMTP server, for short hereinafter) has a lot of users, so it became an important attacked target in the network. The ways of attacks includes SMTP Flooding Attack (SMTPFA), spam attacks and the malicious attachment etc. in e-mail [START_REF] O'donnell | The Evolutionary Microcosm of Stock Spam[END_REF][START_REF] Bass | A simple framework for filtering queued SMTP e-mail[END_REF][START_REF] Bass | E-Mail Bombs and Countermeasure: Cyber Attack on Availability and Brand Integrity[END_REF][START_REF] Wang | On the effectiveness of secure overlay forwarding systems under intelligent distributed DoS attacks[END_REF]. The SMTPFA will increase the loading of the server. In this paper, we propose a new approach for detecting SMTPFA based on entropy operation. Then, we use the entropy operation to analyse the received packets, in order to distinguish normal packets and abnormal packets from SMTP message flow, and then calculate the corresponding information parameters. Therefore, the information parameter will be used to describe the status of the serving server. According to the value of this status, the server will determine whether it is suffered by SMTPFA.

The remainder of this paper is organized as follows. Section 2 describes the SMTP and entropy operation related work. In the Section 3, we propose a new approach for detecting SMTPFA based on entropy operation, and describe how to calculate the parameters of server status. Finally, we draw conclusions in Section 4.

Related Work

In our proposed approach, we use the entropy measurement to detect the behaviour of the SMTPFA. Therefore, in Section 2, we will describe the normal message flows of SMTP standard [START_REF] Postel | A SIMPLE MAIL TRANSFER PROTOCOL[END_REF][START_REF] Moore | Simple Mail Transfer Protocol (SMTP) Service Extension for Delivery Status Notifications (DSNs)[END_REF], and the entropy operations [START_REF] Bass | A simple framework for filtering queued SMTP e-mail[END_REF][START_REF] Shannon | A mathematical theory of communication[END_REF].

SMTP

First, SMTP had been defined in the RFC 821 [START_REF] Postel | A SIMPLE MAIL TRANSFER PROTOCOL[END_REF]. It is an independent subsystem in special communication system. In this communication system, it only needs a reliable channel to transmit the related sequence message flows. SMTP has an important simple delivering e-mail protocol which it can forward an e-mail between two different networks. The architecture of SMTP is shown in Fig. 1. In the SMTP architecture, it consists of a Sender, a sender-SMTP, a receiver-SMTP and a Receiver. When a Sender (user or file server) will connect to another receiver, it will send a request message of Establishes Connection to the sender-SMTP. Then, the sender-SMTP will establish a two-way transmission channel in order to connect the Receiver. The receiver-SMTP will be as a destination point or a relay point. Thus, the sender-SMTP will send the related SMTP commands to the receiver-SMTP. Finally, the receiver-SMTP will follow these commands to send back a SMTP response message to sender-SMTP. According to the above steps, if the command-respond pair has been completed during one normal time-period, it means that a round of SMTP session has been completed. The established SMTP message flows are divided into seven stages [START_REF] Postel | A SIMPLE MAIL TRANSFER PROTOCOL[END_REF][START_REF] Moore | Simple Mail Transfer Protocol (SMTP) Service Extension for Delivery Status Notifications (DSNs)[END_REF] as below: Establishes Connection, HELO, MAIL FROM, RCPT TO, DATA, DATA TRANSFER, and QUIT. The SMTP message flows are shown in Fig. 2. At first, in Establishes Connection, Client (e-mail sender) will send a request of Establishes Connection to SMTP server, and prepare to forward an e-mail. After SMTP server getting the requesting connection, it will send a message '220' which means the SMTP server has prepared completely. When client gets the message "220" from SMTP server, it will send a command as "HELO < sender domain>" to SMTP server. After SMTP server gets the command as "HELO", a buffer will be initialized, and sent back the message "250 < receiver domain>" which means the command of Client is correct. Then, Client will write the source address into "MAIL FROM: < reverse-path>" command. The main purpose of this step is that when some errors have occurred during e-mail delivered path, it will return error messages of the e-mail to Client via reverse-path. If the e-mail address is inerrancy, the SMTP server will response the message "250", else it will response the message "550" which means the e-mail address doesn't exist. After Client gets the message "250", it will send back the "RCPT TO :< forward-path>" command. When the above steps have been completed, the client will use the "DATA" command to notify the SMTP server. Then, the data will be sent via the file server. When SMTP server gets command, it will response the message "354" to notify Client "You can start to upload the e-mail, and add "<CRLF>.<CRLF>" at the end of this e-mail. After getting "<CRLF>.<CRLF>", the SMTP server then responses the message "250" that means the e-mail has finished successfully the work. Finally, if Client doesn't want to uses e-mail functions, she/he will send back the "QUIT" command to notify the SMTP server. Then, the SMTP server further response the message "221" which means as "shut down the connected service".

Entropy Operation

In the Information Theory, Entropy is an approach used to measure the uncertainty or randomness in random variable [START_REF]Information Entropy[END_REF][START_REF] Russell | Artificial Intelligence-A Modern Approach 3/E[END_REF]. Entropy measurement approach is proposed by Shannon [START_REF] Shannon | A mathematical theory of communication[END_REF] and Weaver [START_REF] Weaver | The Mathematical Theory of Communication[END_REF]. In the entropy operation, a random entropy value

  n x x x x X ,..., , , 3 2 1



, the entropy calculation formula [START_REF]Information Entropy[END_REF][START_REF] Russell | Artificial Intelligence-A Modern Approach 3/E[END_REF] as below:

        n i i i x P x P X H 1 log ) ( (1)
where

  m m x P i i  ,    n i i m m 1 , i
m is the observation frequency or numbers of the i x from X. It can represent [START_REF]Information Entropy[END_REF][START_REF] Russell | Artificial Intelligence-A Modern Approach 3/E[END_REF] as:

                n i i i m m P m m X H 1 log ) ( (2)
For example, if we throw a coin according to the formula (1) and ( 2), the positive and negative entropy values will be shown as follows:

) ( 1 1 5 . 0 log 5 . 0 1 5 . 0 log 5 . 0 ) ( 2 2 negative H positive H           
Throwing a coin will face the probability of 99%, the positive entropy value is as

. 014 . 0 1 99 . 0 log 99 . 0 ) ( 2          positive H
And the negative entropy value is as

. 066 . 0 1 01 . 0 log 01 . 0 ) ( 2          negative H
From the example above, we know that the coin is thrown according to the positive and negative probability to determine the entropy. The entropy value is inversely proportional to the probability value. With this feature, the value of results we calculate has dependability.

A New Approach for Detecting SMTPFA

When SMTP server is under the SMTPFA, it will have a large number of request packets into SMTP server. In SMTPFA, the request packets will sent to SMTP server from clients, and the connection will be established with the SMTP server. But clients will not be sent the command packets again. At the same time, there have request packets from another client into SMTP server. Therefore, the server resources will be reduced ceaselessly, further increasing the loading of the server. In this session, we propose a new approach for detecting SMTPFA based on entropy operation. This approach can quickly to detect SMTPFA. In order to detect SMTPFA, we mark a server command packet and a client message packet become to a pairs. A normal packets pair (hereinafter referred to as the NPP) include one command packet and one message packet; an abnormal packets pair (hereinafter referred to as the APP) just include one message packet and no command packet. Then, we calculate the normal and abnormal packets entropy value in the SMTP message flow. By using this entropy to determine whether the server was affected by SMTPFA.

In general, when SMTPFA has starting, the device other than the server may not work. However, in our proposed method, we assume that the SMTP server crashing by SMTPFA. This represents the SMTPFA will attack the server directly, and does not affect the router and bandwidth. We will describe the process of SMTP message flow matching as below. Then, we will explain how to use the entropy operations to calculate the SMTP server status value. Finally, we describe a server status change of entropy situation when a server is under SMTPFA. Some notations used in the paper are given in Table 1.

S

The status value of SMTP Server

SMTP Message Flow

Definition 1. A completion SMTP message flow contains six rounds, which not include the steps of Establishes Connection and Service closing transmission channel. The round 0 is represented to the packet pair of establishment connection, and the round 7 is represented the packet pair of closing transmission channel. There is only one packet in the round 0 and round 7. After the SMTP connection being established, the message flow will be divided into a pair of two packets matching. The packet pair is

  i port i port D S , , where         i port S i port D i port D i port S i port i port D D S S D S _ _ _ _ , , , , 
. It is recorded by the SMTP server.

According to Definition 1, In SMTP message flow; there have two packets in one pair. Every packets pair includes a source and destination port number, and it is used to identify the sender and the receiver. For example, in the round 1, SMTP server will : send a message "220 Service already" to client. The packet pair is called

  _ _ , i i S port D port S S
, it means the packet that send to Client form SMTP server. When the destination of client gets the packet, it will send a HELO packet to SMTP server, it

is called   i port S i port D D D _ _ ,
. This packet means that send to SMTP server form Client. Therefore, this transmission process is called a successful packet pair

  i i port port D S ,
. If there has a packet is transmission fail or over the SMTP server waiting time from client, it's called a fail packet pair  

loss port D S i ,
, and record into the SMTP server. SMTP packets pair message flow as shown Fig. 3.

3.2

A approach for detecting SMTPFA using entropy Definition 2. In the SMTP, it has a NPP at least, to represent the SMTP server and the client has completed at least the starting of SMTP connection steps.

In the approach of detecting the SMTPFA, SMTP message flows are divided into two one-group pairing according to the description of Section 3.1. Then, we use the entropy operation to calculate the SMTP packets pair entropy values for the normal message flows and abnormal message flows. The entropy formulas are listed as follows. : ( ) log ,

n n P P Entropy H x P P          (3) 2 2
: ( ) log ,

a a P P Entropy H x P P          (4)
where P=P n +P a. By formula (3), we calculate the normal packets pair entropy

) ( 1 x H at w T .
If the normal number of packets pair is more, its mean the normal packets pair entropy n P will less. Otherwise, the number of normal packets pair is less, its mean the normal packets pair entropy n P will more. In formula (4), we calculate the normal packets pair entropy

) ( 2 x H at w
T . If the number of abnormal packets pair is more, its mean the abnormal packets pair entropy a P will less. Otherwise the number of abnormal packets pair is less;

it means the abnormal packets pair entropy n P will more. According to Definition 2, if all of the packets pair is abnormal in SMTP message flow, it means all of the packets are lost, and the SMTP server and Client connections will not start. Therefore, in the SMTP message flow must be at least a normal packets pair to represent server and client is established a connection, and complete the SMTP steps of establish connection. Finally, according to formula (1) and formula (2), we get the intersection point of the entropy of the normal packets pair entropy and abnormal packets pair, as shown in Fig. 4. When the server status values are more near to the intersection point, it indicating the server's security will be lower. The following we use the algorithm to describe the server status value. , and return 0 mean the status on behalf of the server in the security value of the critical point. When the NPP entropy value adds the APP entropy value will less than 0,     0   a n P H P H , its mean the SMTP server is under the danger status. If the server in this case, it will be attacked by SMTPFA or the SMTP server will overload. When the NPP entropy value adds the APP entropy value will greater than 0,

    0   a n P H P H
, its mean the SMTP server is safe status. Finally, return the server status value S , and according to the value determine whether the SMTP server was affected by SMTPFA.

An example for detecting of SMTPFA

In the time slide window   is APP entropy. We prove that the description of Section 3.2 is correct: the smaller the entropy value, the number of normal packets pair will be greater; the smaller the value, the fewer the number representing the abnormal packets. Then, we will add

Conclusions

In this paper, we propose a new approach for detecting SMTPFA based on entropy measurement. By using this method, we can quickly analyse the current status of the SMTP server, and determine whether the server is attacked by SMTPFA or not. This approach can not only be applied to different SMTP servers, but also monitor the real-time status of SMTP server. Finally, according to the status value of STMP server by using the entropy measurement we proposed, it can detect SMTPFA easily and quickly.

Fig. 1 .Fig. 2 .

 12 Fig. 1. The SMTP architecture

  mail input; end with <CRLF>.<CRLF> DATA TRANSFER end with 250 OK QUIT 221 < receiver domain> Service closing transmission channel 220< receiver domain>Simple Mail Transfer Service Ready

Fig. 3 .

 3 Fig. 3. SMTP packet pair message flows.

Fig. 4 .

 4 Fig. 4. The intersection point of entropy.

Fig. 5 .

 5 Fig. 5. The status of SMTP server,

Table 1 .

 1 Notations

	Notations			Definitions	Notations	Definitions
	Port i	The i-th port number	loss D	The fail packets are sent from client to SMTP server.
			The i-th message flow	T	w	The w-th unit of time slide
			packet pair, for the port	window, w=1, 2, 3, …, n,
			number	i port , which is send
			from SMTP server. It
			includes two packets:
			S S _	i port	and	D S _	i port	.
	D S _	i port	The i-th packet is delivered from client to SMTP server, which is one of the packet pair i port S .	P	The total SMTP message flow pair numbers, where a n P P P   .
	S S _	i port	The i-th packet is delivered from SMTP server to client, which is one of the packet pair i port S .	n P	The number of normal SMTP message flow pair, where   j n n n n n P P P P P , ... , , , 3 2  , 1 j=1, 2, 3, …, n

i port S

Acknowledgements

This work was supported in part by Asia University, Taiwan, under Grant 100-asia-34, also by the National Science Council, Taiwan, Republic of China, under Grant NSC99-2221-E-468-011.


Jongbeom Lim
email: jblim@korea.ac.kr

Kwang-Sik Chung

Heon-Chang Yu

A Termination Detection Technique Using Gossip in Cloud Computing Environments

Keywords: Termination Detection, Gossip Algorithm, Cloud Computing

Termination detection is a fundamental problem in distributed systems. In previous research, some structures are used (e.g., spanning tree or computational tree) to detect termination. In this work, we present an unstructured termination detection algorithm, which uses a gossip based algorithm to cope with scalability and fault-tolerance issues. This approach allows the algorithm not to maintain structures during runtime due to node joining and leaving. These dynamic behaviors are prevalent in cloud computing environments and little attention has been paid by existing approaches. To measure the complexity of our proposed algorithm, a new metric, self-centered message complexity is used. Our evaluation over scalable settings shows that the unstructured approach can have a significant merit on performance over existing algorithms.

Introduction

In the termination detection problem, a set of nodes in the system collectively execute a distributed computation. Determining whether a distributed computation has terminated is a non-trivial task because no node has complete knowledge of the global state, and there is no notion of global time or global memory. Each node only knows its own local state and local time, and communication among nodes can be done only by message passing.

Termination detection problem has been extensively studied for static distributed systems where all of the nodes are stationary in terms of node joining and leaving from the beginning to the end (e.g., [START_REF] Dijkstra | Termination detection for diffusing computations[END_REF][START_REF] Mattern | Algorithms for distributed termination detection[END_REF][START_REF] Huang | Termination detection by using distributed snapshots[END_REF][START_REF] Mahapatra | An efficient delay-optimal distributed termination detection algorithm[END_REF][START_REF] Mittal | A family of optimal termination detection algorithms[END_REF][START_REF] Livesey | The Doomsday distributed termination detection protocol[END_REF]). One of systems that termination detection algorithms can be used in is the cloud computing system in which constituent nodes can easily join and leave with dynamic behavior due to loosely-coupled environments. However, although much research for the termination detection problem in recent years mainly focuses on reducing message complexity, little attention has been paid to the aforementioned dynamic behavior. Most of the studies assumed that the system does not change anymore without considering node failures and joining which are vital aspects in cloud computing environments that should not be dismissed.

Recently, gossip-based algorithms have received much attention due to its inherent scalable and fault-tolerant properties which offer additional benefits in distributed systems [START_REF] Ganesh | Peer-to-peer membership management for gossip-based protocols[END_REF]. Correctness of a gossip-based protocol is presented in [START_REF] Allavena | Correctness of a gossip based membership protocol[END_REF][START_REF] Gurevich | Correctness of gossip-based membership under message loss[END_REF]. In gossipbased algorithms, each node maintains some number of neighbors called a partial view. With this partial view, at each cycle (round), every node in the system selects f (fanout) number of nodes at random and then communicates using one of the following ways: 1) Push, 2) Pull, and 3) Push-pull mode. Gossip-based algorithms guarantee message delivery to all nodes with high probability and their variation can be found in [START_REF] Ganesh | HiScamp: self-organizing hierarchical membership protocol[END_REF][START_REF] Voulgaris | CYCLON: Inexpensive Membership Management for Unstructured P2P Overlays[END_REF][START_REF] Matos | CLON: Overlay Networks and Gossip Protocols for Cloud Environments[END_REF][START_REF] Jelasity | T-Man: Gossip-based fast overlay topology construction[END_REF][START_REF] Lim | Group-based gossip multicast protocol for efficient and fault tolerant message dissemination in clouds[END_REF]. Applications of gossip-based algorithms include message dissemination, failure detection services, data aggregation etc.

In this paper, we present an unstructured termination detection algorithm based on the gossip-based algorithm. The use of the gossip-based algorithm for the termination detection problem is a desired approach to deal with scalability and dynamic behavior in cloud computing systems. Having partial view in the gossip-based algorithm is the essential key to achieve the scalability issue. In other words, each node does not have to maintain all the nodes in the system, but the small number of nodes. Furthermore, in structured termination detection algorithms (using spanning tree or computational tree), reconstruction of the structure of algorithms is needed when node joining and leaving. Otherwise, detecting the termination of a distributed computation is virtually impossible since node connection is broken.

The rest of the paper is organized as follows. We present the system model and formally describe the termination detection problem in Section 2. Section 3 provides our gossip-based termination detection algorithm. Simulation results for the algorithm and their interpretation are given in Section 4; this section also analyzes the message complexity. Finally, Section 5 gives our conclusions.

2

Model and Problem Specifications

System Model

We assume that the cloud computing infrastructure consists of numerous nodes of resources, and individual nodes process arbitrary programs to achieve a common goal.

Because of the absence of shared memory, each process or node should communicate with other nodes only by message passing through a set of channels. In addition, we assume that all channels are reliable and FIFO (first-in, first-out), meaning all messages within a channel are received in the order they are sent to. And the message delay is bounded. There is no global clock. However, it is assumed that each node synchronizes its time by gossiping with other nodes. This approach has been justified by [START_REF] Iwanicki | Gossip-based clock synchronization for large decentralized systems[END_REF]. Furthermore, the communication model is asynchronous. In other words, a sender does not have to wait for acknowledgements of receivers (non-blocking).

2.2

Specifications of the Problem

Termination detection is a fundamental problem in distributed systems; it is not an exception in cloud computing systems. The importance of determining termination derives from the observation that some nodes may execute several sub-problems, and in some cases, there are precedence dependencies among them. Because there is no shared memory, message passing is the only way to deal with the termination detection problem satisfying following properties:

 Safety: If the termination detection algorithm announces termination, then the underlying computation has indeed terminated.  Liveness: If termination holds in the underlying computation, then eventually the termination detection algorithm announces termination and henceforth termination is not revoked.  Non-Interference: The termination detection algorithm must not influence the underlying computation.

The definition of termination detection is as follows: Let P i (t) denote the state (active or passive) of process P i at time t and C i , j (t) denote the number of messages in transit in the channel at time t from process P i to process P j . A distributed computation is said to be terminated at time t if and only if:

(∀i :: P i (t) = passive)∧(∀i,j :: C i , j (t) = null)

Performance Metrics

Traditionally, the following metric has been used to measure the performance of termination detection algorithms:

 Message complexity: The number of messages required to detect the termination.

In addition to the message complexity, we propose a new metric called selfcentered message complexity. Self-centered message complexity counts the number of message requited to detect the termination from the requester point of view rather than from the whole nodes in the system. We conjecture that this is more flexible and simpler metric to measure the structured and unstructured termination detection algorithms because some algorithms are not always intuitive and observable at the highlevel domain. Self-centered message can be defined as follows:

 Self-centered message complexity: The number of messages required to detect the termination from the requester point of view.

Termination Detection Technique

In this section, we first review the basic gossip-based protocol based on [START_REF] Jelasity | The peer sampling service: experimental evaluation of unstructured gossip-based implementations[END_REF] to describe our gossip-based termination detection algorithm. The termination detection algorithm proposed in this section can be viewed as an extension of the gossip-based algorithm to support the termination detection functionality.

Termination Detection Technique Using the Gossip Algorithm

In the gossip-based algorithm, there are two different kinds of threads in each node: active and passive. At each cycle (round), an active thread selects a neighbor at random and sends a message. The active thread then waits for the message from the receiver. Upon receiving the message from the neighbor, the active thread updates local information with the received message and its own information. A passive thread waits for messages sent by active threads and replies to the senders. Afterwards, the passive thread updates its local information with the received message from the sender accordingly.

The function getNeighbor() returns a random neighbor identifier from its partial view, not from the entire set of nodes in our algorithm. It is noted that according to the system parameter f (fanout), getNeighbor() returns f number of neighbor identifiers. Additionally, before the gossiping is initiated, the partial view of nodes is constructed by the middleware called peer sampling service [START_REF] Jelasity | The peer sampling service: experimental evaluation of unstructured gossip-based implementations[END_REF], which returns a uniform random sample from the entire set of nodes in the system.

A simple way to solve the termination detection problem is to use distributed snapshots (e.g., [START_REF] Huang | Termination detection by using distributed snapshots[END_REF]). If a consistent snapshot of a distributed computation is taken after the distributed computation has terminated, the snapshot will capture the termination of the computation. However, the algorithm that uses distributed snapshots broadcasts to all other nodes when a process goes passive; this involves a large number of request messages. Furthermore, detecting whether all the other processes are taken a snapshot is not a trivial job even though all the other processes are passive and taken a snapshot.

Hence, we take the distributed approach with the gossip-based algorithm. To let a process decide whether all of nodes are passive and distributed computation is terminated, we use the piggybacking mechanism by which a node adds additional information of neighbors to the message during gossiping. By using the piggybacking mechanism, any node wishing to detect termination can eventually detect whether distributed computation is terminated or not.

In the previous researches using the distributed approach, however, they assumed that the number of nodes is static. Few studies have focused on the dynamic behavior such as adding and removing nodes while request operations are ongoing, which is that we want to deal with. In the dynamic scenario, it is assumed that each node can learn about newly added and removed nodes by the middleware before each cycle begins. (c) if (a) is false, then termination is not detected.

Unstructured Termination Detection Algorithm

Fig. 1. The proposed unstructured termination detection algorithm

The unstructured termination detection algorithm using a gossip-based approach is summarized in Figure 1. We explain only our extensions to the gossip algorithm. We assume that each process has a unique identifier and can be indexed by from 1 to n, where n is the number of processes (nodes) in the system. Henceforth, the terms a node and a process are used interchangeably.

Each process P i maintains the following data structures:

 State i [1 :
n] : An array of states for P i . This data structure consists of two elements for each array: state and timestamp. State value can be active or passive and timestamp value is logical time at which state value is updated.

We describe our extensions as follows:

1. If process P i selects process P j during gossiping following states are performed: (a) When P i sends a basic message to P j , State array is updated as follows:

(i) jth elements (i.e., state and timestamp) of array of both processes are updated with active and LC current . (b) When P j sends a basic message to P i , State array is updated as follows:

(i) ith elements (i.e., state and timestamp) of array of both processes are updated with active and LC current . (c) Each element of State[k] of both processes, where ∀k ∈ {1 … n}, is updated with the one whose timestamp value is larger.

Experimental Evaluation

In this section, we present simulation results for the gossip-based termination detection algorithm using the PeerSim simulator [START_REF] Montresor | PeerSim: A scalable P2P simulator[END_REF], which supports extreme scalability and dynamicity of nodes, and is implemented in Java. To compare our algorithms' performance, we implemented the simple broadcast algorithm that is similar to [START_REF] Huang | Termination detection by using distributed snapshots[END_REF], which involve n-1 request messages and n-1 acknowledge messages. During entire experiments, a fanout parameter f is set to 1.

We first evaluated effects of the size of PartialView and the number of nodes. In Figure 2, we can see the results for the requisite number of cycles to detect termination with varying the size of PartialView from 5 to 30 by increments of 5 for 10 4 nodes, and the number of nodes from 10 2 to 10 4.5 with a PartialView size of 20. It is noted that in this experiment, we let each node update its state when a request message is received.

The Size of PartialView We have confirmed that effects of the size of PartialView is insignificant when the size is larger than 15 when the number of nodes is 10 4 . Notice that in Figure 2(b), the requisite number of cycles grows linearly as the total number of nodes increases exponentially.

Figure 3 shows the results of message complexity. It is noted that in this experiment, the number of nodes is set to 10 4 , and the size of PartialView is set to 20. When we compare self-centered message complexity of the proposed algorithm and the broadcast algorithm, our algorithm performed better than the broadcast algorithm about a 111100% improvement.

During experiments we also have confirmed that if each node changes its state to passive when local computation is finished, rather than when a request message received, the requisite number of cycles to detect termination using our unstructured algorithm is 2. In this regard, when we compare the two algorithms, message complexity is close to each other. In other words, the proposed algorithm generates 2n messages, while the broadcast algorithm generates 2(n-1) messages. This signifies that our unstructured termination detection algorithm and the broadcast algorithm have no big difference in message complexity, but in our algorithm, messages are diffused among nodes without a bottleneck.

Conclusion

In this work, we have presented the termination detection algorithm using a gossipbased approach to cope with scalability and fault tolerance issues. A cloud environment where the behavior of their constituting nodes is active and dynamic (i.e., joining and leaving at any time) is an example that our algorithm will be applied to. Furthermore, our gossip-based termination detection algorithm could be embedded seamlessly into other existing gossip-based algorithms. In other words, if a gossip-based algorithm is implemented for the failure-detection service, then the termination detection algorithm proposed in our work can be embedded in the existing gossip-based algorithm.

  (a) State i [i].state = passive; (b) State i [i].timestamp = LC current ;  Deciding for termination: 1. Checking states array: (a) Check if State i [k].state == passive, ∀k ∈ {1 … n} (b) if (a) is true, then termination is detected.

Fig. 2 .

 2 Fig. 2. The requisite numbers of cycles to detect termination. The number of nodes is set to 10 4 in (a). The size of PartialView is set to 20 in (b).

Fig. 3 .

 3 Fig. 3. The comparisons of self-centered message complexity (a) and message complexity (b)between the proposed algorithm and the broadcast algorithm.



  Initial local state for process P i array of states : State i [j] = passive, j  {1 … n}  During gossiping: Process P i executes the followings during gossiping with target P j (where j ≠ i):

	1. When P i sends a basic message to P j :
	(a) State i [j].state = State j [j].state = active;
	(b) State i [j].timestamp = State j [j].timestamp = LC current ;
	2. When P j sends a basic message to P i :
	(a) State i [i] = State j [i] = active;
	(b) State i [i].timestamp = State j [i].timestamp = LC current ;
	3. Updating states array:
	(a) Update each element of State i [k] and State j [k], where ∀k ∈ {1 … n}, ac-cording to timestamp
	 When local computation is completed:
	1. Updating local state:

  2. When local computation is completed, State values are updated as follows: (a) State i [i].state and State i [i].timestamp are updated with passive and LC current , respectively. 3. In order to decide whether local computation of whole processes is completed, following states are performed: (a) State array is checked: (i) If State i [k].state == passive, where ∀k ∈ {1 … n}, then it concludes that termination is detected. (ii) Otherwise, it concludes that termination is not detected and local computation of some processes is ongoing.


Shiang-Lan Kuo
email: lilykuojiki@gmail.com

Cross-cultural training programs and expatriate adjustment effectiveness

Keywords: Cross-Cultural Competence, Cross-Cultural Training, Expatriate Adjustment, Multinational Corporations

The purpose of the study reported here was to explore cross-cultural training programs and expatriate adjustment effectiveness that increase effective cross-cultural interaction. Effective cross-cultural training increases trainees' knowledge, encourages them to see the personal and organizational benefits of cultural diversity and cross-cultural competence, and increases their skill and capacity to work with cultural diversity. Cross-cultural training is an effective strategy in the achievement of organizational performance targets and multicultural policy objectives. Addressing the identified limitations of current practice in CCT will increase its contribution to the development and enhancement of organizational and individual cultural competence. Moreover, developing crosscultural training programs could add value to the firm and its people.

Introduction

Multinational corporations (MNCs) are having difficulty retaining expatriates for their global operations. It is estimated that 10-80% of expatriates sent on foreign assignments return home prematurely. One of the reasons for expatriates' failure has been cited as the inability of these managers and/or their spouses to adapt to the hostcountry's culture. As a result, cross-culture training programs provided to employees and their families by MNCs have become crucially important for successful international operations [START_REF] Okpara | Cross-cultural training and expatriate adjustment: A study of western expatriates in Nigeria[END_REF]. [START_REF] Gertsen | Intercultural competence and expatriates[END_REF] argues that cross-cultural training can be classified into two major categories: [START_REF] Bean | Cross-Cultural Competence and Training in Australia[END_REF] conventional training, where the information is transmitted through a unidirectional communication, as is the case in colleges, universities and management development centers and (2) experimental training, where the trainer gets the trainees to participate by simulating real life and hands on situations. Gertsen (1990) also identified two other possible training orientations where the training emphasis is based on the notion of culture in general and aims at sensitizing participants to the notion of culture, or focuses on one specific culture and aims at making trainees more competent in that particular culture. [START_REF] Gertsen | Intercultural competence and expatriates[END_REF] argued that the combination of these two dimensions reveals four types of training [START_REF] Okpara | Cross-cultural training and expatriate adjustment: A study of western expatriates in Nigeria[END_REF], as shown in Figure 1. The purpose of the study reported here was to explore cross-cultural training programs and expatriate adjustment effectiveness that increase effective cross-cultural interaction. (d)Individual cultural competence -requires the maximization of knowledge, attitudes and behaviors within an organization that supports individuals to work with diverse colleagues and customers.

Cross-Cultural Training (CCT)

CCT is defined as that which increases the competence of individuals to function in cross cultural situations domestically and abroad. In broad terms, CCT programs focus on the following broad categories (Bean, 2006): (a)managing and working with culturally-diverse employees and colleagues; (b)working and living internationally; (c)designing and delivering products and services to culturally-diverse customers.

CCT is generally delivered in three models (Bean, 2006); (a)General awareness and communication training -focuses on developing generic cross cultural skills and sensitivity to assist with interactions in any culture the participant may encounter.

(b)Ethno-or country-specific training -focuses on a single ethnic group or country to increase participants' knowledge, understanding and ability to function effectively in that environment or with that group.

(c)Training in working with interpreters and translators -focuses on developing the technical skills involved and also includes those elements of cross-cultural communication that influence the process.

Pre-departure training is the traditional form for CCT and it is conducted apart from the actual experience of realities in the host culture. Traditionally, pre-departure CCT programs are administered about a month before departure. Such post-arrival training need not necessarily take place immediately upon the expatriate's arrival; some CCT may be more effective if it is delayed until the expatriate tries to cope with culture shock. Hence, such training could start about three to six months after arrival in the host country. Expatriate CCT aims to increase the applicability of new behaviors, which are more appropriate to the host culture. However, an individual's capacity for efficient learning ebbs and flows during the expatriate period. Therefore, CCT may preferably be sequential, progressing in steps starting at pre-departure and continuing to the post-arrival phases. Sequential CCT would provide continuous guidance for the incremental restructuring of the expatriate's frame of reference towards greater consistency with the host culture [START_REF] Selmer | Expatriate cross-cultural training for China: views and experience of ''China Hands[END_REF].

Through observation, interview, and material analysis, it looks at five essential and practical considerations in cross-cultural program adjustment -spoken communication, material translation, silent communication, local trainers, and empowerment and localization [START_REF] Chang | Cross-cultural adjustment in the multinational training programme[END_REF]. Furthermore, cultural adjustment is considered to be a prerequisite for expatriate success abroad. One way to enhance adjustment is to provide employees with knowledge and awareness of appropriate norms and behaviors of the host country through cross-cultural training [START_REF] Puck | Does it really work? Re-assessing the impact of pre-departure cross-cultural training on expatriate adjustment[END_REF].

Implementation steps

The steps of implementing cross-cultural training programs, as follows (Bean, 2006):

Step 1: Define the organizational context and training objectives Establish the relationship of cultural competence to the organizational, legal and people management contexts. Define the training needs and objectives. Ensure strong organizational support for the training program.

Step 2: Understand cultural competence and cross-cultural training Before embarking on a cross-cultural training program, be clear on the nature of cultural competence, the range of cross-cultural training approaches and the criteria for an effective cross-cultural training trainer.

Step 3: Promote the value of cross-cultural training to the organization Demonstrate the value of cross-cultural training to all stakeholders with the statistical evidence and qualitative comments.

Step 4: Design and conduct cross-cultural training effectively Study the range of options for cross-cultural training and resources that will ensure the training objectives are met. Select the appropriate trainers and work closely with them. Organize and conduct the program for maximum effectiveness.

Step 5: Evaluate and follow-up the cross-cultural training program Design and carry out a rigorous evaluation process. Identify and implement strategies to ensure that learning is applied to performance and enhancing the organization's cultural competence.

Discussion and conclusions

Effective cross-cultural training increases trainees' knowledge, encourages them to see the personal and organizational benefits of cultural diversity and cross-cultural competence, and increases their skill and capacity to work with cultural diversity. A recent review of Bennett's Developmental Model of Intercultural Sensitivity [START_REF] Hammer | Measuring Intercultural Sensitivity: The Intercultural Development Inventory[END_REF] suggests that a higher degree of acceptance/adaptation to cultural differences among employees would result in the following benefits (Bean, 2006) At the systemic and organizational levels, cultural competence must be closely linked to policy requirements and organizational values and service delivery objectives and expressed in high levels of political, leadership and managerial support for CCT. At the professional level, cultural competence must be integrated into the standards and competency and performance frameworks of professions and occupations. At the individual level, CCT is most effective when it addresses the concerns and motivations of participants and is provided within an organizational context that provides opportunities and incentives for applying acquired cross-cultural knowledge and skills to the workplace. To effectively facilitate the development of cultural competence, cross-cultural trainers need support in the areas of professional and resource development. Cross-cultural training is an effective strategy in the achievement of organizational performance targets and multicultural policy objectives. Addressing the identified limitations of current practice in CCT will increase its contribution to the development and enhancement of organizational and individual cultural competence (Bean, 2006). Moreover, developing cross-cultural training programs could add value to the firm and its people [START_REF] Qin | The impact of cross-cultural training for expatriates in a Chinese firm[END_REF]. Since expatriate training is essential, how to design effective training programs is an important issue for business managers. It suggests that an effective training program is contingent upon certain environmental factors. Among these factors, the fit between expatriate learning style and instructor learning mode, and the perceived cross cultural differences between host country and home country were regarded as the two main moderating (or contingency) factors to evaluate the influences of expatriate training on training effectiveness [START_REF] Lee | The moderating effects of teaching method, learning style and cross-cultural differences on the relationship between expatriate training and training effectiveness[END_REF].

Fig. 1 .

 1 Fig. 1. Dimensions of cross-cultural training methods. (Source: Adapted and modified from Gertsen (1990, p. 354).)

  : (a) Less stress. (b) More satisfaction with living/working in a foreign culture. (c) Greater job accomplishment in culturally-diverse environments. (d) Lower levels of prejudice and discrimination. (e) Less resistance to diversity initiatives.