Ehsan Narjes Soltani
email: narjes_soltani@comp.iust.ac.ir

Mousavi Khaneghah

Mohsen Sharifi
email: msharifi@iust.ac.ir

Seyedeh Leili Mirtaheri

A Dynamic Popularity-Aware Load Balancing Algorithm for Structured P2P Systems

Keywords: Structured P2P Systems, Load Balancing, Node Movement, Replication 1

Load balancing is one of the main challenges of structured P2P systems that use distributed hash tables (DHT) to map data items (objects) onto the nodes of the system. In a typical P2P system with N nodes, the use of random hash functions for distributing keys among peer nodes can lead to O(log N) imbalance. Most existing load balancing algorithms for structured P2Psystems are not proximity-aware, assume uniform distribution of objects in the system and often ignore node heterogeneity. In this paper we propose a load balancing algorithm that considers node heterogeneity, changes in object popularities, and link latencies between nodes. It also considers the load transfer time as an important factor in calculating the cost of load balancing. We present the algorithm using node movement and replication mechanisms. We also show via simulation how well the algorithm performs under different loads in a typical structured P2P system.

INTRODUCTION

In most structured Peer-to-Peer (P2P) systems distribution of objects among nodes is done through distributed hash tables (DHT) mechanisms that use consistent hashing to map objects onto nodes [START_REF] Stoica | Chord: a scalable peer-to-peer lookup service for internet applications[END_REF]. Using this mechanism, a unique identifier is associated with each data item (object) and each node in the system. The identifier space is partitioned among the nodes that form the P2P system and each node is responsible for storing all data items that are mapped to an identifier in its portion of the space.

If node identifiers are chosen at random (as in [START_REF] Stoica | Chord: a scalable peer-to-peer lookup service for internet applications[END_REF]), a random choice of item IDs result in O(log N) imbalance factor in the number of items stored at a node. Here N is the total number of nodes in the system. Furthermore imbalance may result due to non-uniform distribution of objects in the identifier space and a high degree of heterogeneity in object loads and node capacities, memories, and bandwidths.

Several solutions are offered to solve the load balancing problem like the one proposed in [START_REF] Rao | Load balancing in structured p2p systems[END_REF], but these solutions usually have some shortcomings. For instance lots of them do not consider system dynamicity, nodes and objects heterogeneity, link latency between nodes, and the popularity level of moved items. Our algorithm uses two mechanisms namely nodes moving and replication to balance the load between nodes with consideration of items popularities.

The rest of the paper is organized as follows. In Section 2, we formulate the load balancing problem more explicitly and in Section 3, we discuss the related work. In Section 4, we describe our algorithm and we evaluate it in Section 5. We discuss conclusion in Section 6.

DEFINITIONS AND PROBLEM FORMULATION

We define node load as the temporal average number of bytes which is transferred by that node in each unit of time. In the same way we define the node capacity as the maximum number of bytes that node can transfer per time unit. A node is overloaded if its load is more than an upper threshold which is defined relevant to node capacity.

Our load balancing algorithm aims to minimize the load imbalance factor in the system while also minimizing the moved load. Calculation of load destination cost in our algorithm is based on its load and uptime and also its proximity to the overloaded node. Since there is no global information in P2P systems, we do not claim to select the best node in the system to move load to, but our algorithm does this in a group of nodes. Later we explain how these groups are formed. So when we want to move some load from a node i to a node j the destination cost is formulated as below: DestinationCost=w 1 *load j /cap j +w 2 *(loc i -loc j )/distance max +w 3 *(uptime j /t) (

In (1) cap and loc denote the capacity and location of a node in order. To normalize the location parameter in the above formula, we divide subtract of locations by distance max which stands for the distance between i and the farthest node j in the mentioned group. In the above formula t is the period of time our experiment lasts and we divide uptime of node j by it to normalize the uptime parameter. Also w i (1<=i<=3) is the weight given to different cost function parameters and ∑ w i =1 is always held. These weights are application-defined.

The load of each node j is defined as the summation of its data items loads. The load of each object k is defined as follows:

Load k =size k *access_frequency k (2)
In the above formula we want to calculate the average amount of bytes that is transferred in each unit of time in relation with object k. We calculate frequency access periodically and in distinct intervals. This means that we consider r intervals each last for t' seconds, then divide the number of access in each interval by the subtract result of r*t' and t first . Starting intervals times from zero in each round of simulation, t first stands for the beginning time of each interval namely it is set to 0, t', 2t', … and (r-1)t' in order for each of the r intervals. These intervals can be stored in a cyclic queue with limited size in which the old intervals are replaced with the new ones in a cyclic manner. Next we sum the achieved values to calculate the access_frequency parameter. Defining a node n utility as load n /capacity n , the goal of our algorithm is to close nodes' utilities to each other as much as possible. However it is not always the case because our algorithm balances the load with considering its cost.

RELATED WORK

Generally load balancing protocols are divided to two main groups in structured P2P systems. The first group is based on uniform distribution of items in identifier space and the second group has no such assumption [START_REF] Ruhl | Efficient algorithms for new computational models[END_REF]. Suppose that there are N nodes in the system, load balancing is achieved in the first group if the fraction of address space covered by each node is O(1/N). Most of algorithms have used the notion of virtual servers, first introduced in [START_REF] Stoica | Chord: a scalable peer-to-peer lookup service for internet applications[END_REF] to achieve this goal. A virtual server is similar to a single pear to the underlying DHT and has its own routing table and successors list. Chord suggests each physical node hosts O(log N) virtual servers which leads to each node has some constant number of items with high probability [START_REF] Stoica | Chord: a scalable peer-to-peer lookup service for internet applications[END_REF]. CFS [START_REF] Dabek | Wide-area cooperative storage with CFS[END_REF] accounts for nodes heterogeneity by allocating to each node some number of virtual servers proportional to the node capacity. In [START_REF] Rao | Load balancing in structured p2p systems[END_REF] Rao et.al. have proposed three different mechanisms to balance the load using virtual servers, yet their mechanisms are static and ignore data items popularities.

Using virtual servers in any algorithm leads to some common disadvantages. The first is that it leads to churn increase. Another disadvantage about virtual servers is that using them causes a great increase in routing table entries. Considering the above problems about virtual servers, our algorithm does not use of virtual servers [START_REF] Sharifi | A Dynamic Framework for Inte-grated Management of All Types of Resources in P2P Systems[END_REF].

Protocols which do not assume uniform item distribution use two different mechanisms to achieve load balance, namely item movement [START_REF] Ruhl | Efficient algorithms for new computational models[END_REF] and node movement [START_REF] Rieche | A thermal-dissipation-based approach for balancing data load in distributed hash tables[END_REF]. Moving items break the DHT assignment of items to nodes, so that items cannot easily be found any more. Moving nodes by letting them to choose their own addresses arbitrarily increase the threat of Byzantine attack which can prevent some items from being found in the network.

Replicating data items is another way to achieve load balance. Although, some simple replication mechanisms have been proposed in structured P2P systems like chord [START_REF] Stoica | Chord: a scalable peer-to-peer lookup service for internet applications[END_REF], but none of them does this dynamically and with consideration of variant system loads.

Load balancing scheme 4.1 Nodes Load Information

When a node wants to join the system, a unique key is given to it using a hash function we call "First Hash". For the purpose of load balancing a set of load directories, each called LoadDir is designed in the system to which nodes send their loads, capacities, locations, and uptimes information periodically. A node's uptime is defined as the average of continuous time it stays in the system.

To prevent Byzantine attack we use the proposed way in [START_REF] Rieche | A thermal-dissipation-based approach for balancing data load in distributed hash tables[END_REF]. Each node connects to a central authority once, i.e. the first time it joins the system and obtains a directory identifier, we call IDdir that specifies to which LoadDir the node should send its information. The number of distinct directory identifiers is limited and determines the number of load directories in the system.

Grouping of nodes in our load balancing algorithm is done based on their directory identifiers. This means the nodes with the same value of IDdir send their information to the same LoadDir and in case of overloading, our algorithm first tries to move load between the nodes in the same group. A directory with the identifier d is stored in the first node whose identifier is equal to or follows d and when this node wants to leave system it has to send its stored load directory to its successor.

The central authority periodically sends the directory identifiers to the related nodes, so that each directory is aware of other directories.

Load Balancing Algorithm

A node starts load balancing algorithm when it notices its load more than its upper threshold. In the simulations it is proved that setting each node upper threshold to 95% of its capacity generates the best result. Every node checks its load periodically and in case of overloading; it puts its popular items in a list called popular-item-list. This list is stored separately in each node and in relation with its own items. In our algorithm an item is popular if more than a quarter of the node load is due to that item load.

Our algorithm uses two mechanisms namely nodes moving and replication to balance the load between nodes with consideration of items popularities. In the following parts we explain these mechanisms in detail.

Node Movement.

Node movement is done when one of the following cases arise:

1. A node gets overloaded due to the high popularity of more than one of its items. 2. A node gets overloaded because of high amount of data items put on it while none of them is highly popular. Considering the above conditions, if a node n is overloaded, it sends a request to its relevant directory asking it to find a proper underloaded node for moving load. The selected under-loaded node should leave its previous location in the overlay and join at a new location specified by the n's directory called "split point". The overloaded node's directory selects some of n's data items, starting from the item whose key has the most distance from node key and checks whether n load reaches to a normal level by moving this data item or not. If so, the split point is set to that data item key; Otherwise selection of data items continues in the same order until n load gets normal or the only remained data item be the one whose key is equal to overloaded node key, in this case the only remained data item is of course a very popular data item and by iterative execution of our algorithm, the next time this node is an eligible candidate for the second load balancing mechanism and its load is balanced by that way.

Finally the split point is set to the last selected item's key. In simulation we show setting normal load of any node to 75% of its capacity is an appropriate choice.

Selection of a proper under-loaded node is done in two steps and as follows. In the first step the overloaded node's directory searches in its stored information, calculates the destination cost function stated in section 2 for each of its entries and selects the one with the minimum cost. The selected node m should move to the specified split point, so all of its assigned keys should be reassigned to its successor. In the second step the directory checks two conditions. The first is that the reassignment process does not lead to the m's successor overloading and the second is moving selected items from n to m do not end up with m's overloading. If both of these conditions are held, m is the proper node we are searching for and it should leave and rejoin to system at the specified split point. If any of the conditions is not held, the selection process is repeated from the first step. If necessary, this directory can connect to other directories and selects a proper node from them.

Replication.

If a node is overloaded because of the high popularity of one of its items, it is probable that due to its increasing popularity rate, moving this item to another node causes that node to get overloaded too and it is better to replicate it.

For the purpose of replication, we use a second hash function called SecHash and also a set of replication directories each called RepDir. Each entry of these directories consists of two parts, namely the name of replicated data item and the destination of replication. Creation of replication directories is done dynamically throughout system operation. If a node wants to replicate one of its items named A, it should search for successor of SecHash(A) to find the RepDir where it should add an entry.

The replication destination is specified by the overloaded node's LoadDir. This directory calculates the destination cost function stated in section 2 for each of its entries and at last the one with the minimum cost is selected if by moving half of the A's load to it, it does not change to an overloaded node. If this condition is not held, the next minimum cost nodes are tested until an appropriate node is selected. Again this directory can connect to other directories if necessary. A is replicated in the found node in association with another field where FirstHash(A) is stored. This field is used during search process as we explain later.

The overloaded node can then refuse the replicated item's received requests until it reaches to a normal load state. By this way if a node is searching for a replicated item, it may receive no result after a period of time which means a timeout has occurred. If this is the case, the requester node uses the second hash function to find the relevant RepDir and reads the replication destination from it. The above process can be extended to include replicating on more than one node if necessary.

Search Mechanism

Every time a node receives a request with key k, it checks whether k falls in the interval it is responsible for or not. If it is the case, this node returns the requested item.

Otherwise the node should forward the request to another node with respect to its finger table [START_REF] Stoica | Chord: a scalable peer-to-peer lookup service for internet applications[END_REF], but in our algorithm this step delays with another step in which the node checks whether a replica of the searched item is stored in itself. Since intermediate nodes have no information about the name of requested items during search process and work only with hashed keys, the node checks the requested item key with the fields associated to replicated items on it. If no match is found, it forwards the request to another node with respect to its finger table, otherwise it response to the requester node. To make the system fault tolerant, we can backup replication directories in the l next successors of the nodes where they are stored. The value of l is defined with consideration of the fault tolerance level needed in system.

Simulation Results

To evaluate our algorithm, we have designed and implemented a simulator in java based on Chord structured P2P system. Throughout the simulation we have shown the way our algorithm balances the load and also the importance of proximity factor in bandwidth consumption.

Our simulated nodes are completely heterogeneous and with different capabilities, so Pareto node capacity distribution with parameters shape=2 and scale=100 is used. In our simulated environment, nods can leave or join the system at any time. As stated before our algorithm aims to close nodes' utilities to each other as much as possible. It is not however always the case, because our load balancing algorithm considers the imposed cost.

Fig. 1(a) shows nodes utilities in the system before applying any load balancing algorithm. It illustrates the large difference between nodes utilities. In this situation, lots of nodes are overloaded while there are also a lot of nodes with very low or even zero load. Applying our load balancing algorithm, the results change as in Fig. 1(b). To demonstrate the importance of proximity in our algorithm, Fig. 2 displays the bandwidth consumption of load transfer through the hops passed during load balancing process. As it is shown, when we have relaxed the proximity factor, the passed physical hops is much more than the case we have regarded this factor.

Fig. 2. Changing of links delay while load balancing

In Fig. 3 we show the effectiveness of our algorithm by comparing it with three other algorithms, namely Rao et.al. algorithm [START_REF] Rao | Load balancing in structured p2p systems[END_REF], CFS algorithm [START_REF] Dabek | Wide-area cooperative storage with CFS[END_REF] and log(N) virtual Server algorithm [START_REF] Stoica | Chord: a scalable peer-to-peer lookup service for internet applications[END_REF]. As we have mentioned previously Rao et.al. proposed three different schemes to balance the load using virtual servers. In this section we compare our algorithm with the "one-to-one" scheme in which one node contacts a single other node per unit time as two other schemes are said to utilize nodes similarly.

Fig. 3.

Percent of successfully routed queries for trace-driven simulation with varying load

The focus was put on the percentage of successfully routed queries for trace-driven simulations with varying loads. To this end we have used Zipf query distribution. This experiment examines how the load balancing algorithms responded to different degrees of applied workload. In almost all cases, we found our algorithm performs the same as or better than the other algorithms.

Conclusion

This paper presents a load balancing algorithm which considers items non-uniform distribution, heterogeneous nodes, system dynamicity, and objects different and variable popularities. Also two important factors namely the uptime and proximity are considered during load transfer process. For the purpose of load balancing we have used different mechanisms including moving node and replication. Simulation results show that running our algorithm causes node's utilities to close to each other in most cases.

Fig. 1 .

 1 Fig. 1. Load balancing performance (a)Before load balancing


Murray Saunders
email: m.saunders@lancaster.ac.uk

Bernadette Charlier

Joel Bonamy

Using evaluation to create 'provisional stabilities': bridging innovation in Higher Education change processes

This paper will report on the evaluation experience in two SOCRATES (European Union funding mechanism designed to support innovation in teaching and learning) projects focused on change in Higher Education. The projects were international in scope involving 6 countries and 10 institutions within the last four years. The paper reflects on change in institutions specifically, especially those introduced by the use of ICT (Information and Communication Technologies) and it suggests the hypothesis that in such a phase of transition, new rules are not yet established and a state of anomie can occur at the level of courses, departments and institutions. What happens in educational institutions in which rules and practices are well established and validated and a new event radically changes or challenges the traditional practices? Instead of the psycho-social notion of 'resistance to change', we think that the theory of Durkheim and followers which analyses human responses in times of social change may be of use to interpret situations in which change or the will to change creates conflicting systems of rules and practices. The paper will argue for a crucial role for evaluation in negotiating such periods of change.

Introduction

This paper will draw together the evaluation experience of participating in two SOCRATES projects. The work-packages in each of the projects had a brief to develop thinking about the role evaluation might play in supporting the change process. This paper synthesises aspects of both these experiences of evaluation development and offers a general role for evaluation that emphasises its potential as a support for positive change. It suggests that evaluations should be 'theory based' in two ways. First, an evaluation can be supported and framed by a theory of change in an organisational setting and second, the change process is shaped by the theories of change implicit in innovation strategies adopted by change agents [in our case, course innovators]. These implicit theories of change are an important focus for evaluation and form the basis of 'grounded theories' that, once made explicit, are useful in making sense of the change process. It is in the contribution to this sense making (see [START_REF] Weick | Sensemaking in Organsations[END_REF] process that evaluations have their value.

The two projects, which form the basis of this paper, are the LEARN-NETT and RECRE&SUP projects (See [START_REF] Charlier | Nouveaux dispositifs de formation pour l'enseignement supérieur, allier technologie et innovation[END_REF]. Both had an interest in the role ICTs had in supporting learning and in the change process. LEARN-NETT asked simply 'can learning be improved with use of ICT, and if so how? Its starting points were that the use of ICT is increasingly related to the design of and experimentation with innovative learning environments that support collaborative learning activities. LEARN-NETT was a quasi-experimental project designed to develop a collaborative learning environment in which higher education students in nine institutions in five European countries might work together on team based academic activities supported by tutors from any of the participating institutions.

Within the LEARN-NETT project, the role of the evaluation work-package was to build evaluation resources for use by the partners in the project and to establish a rationale for evaluation as a tool for innovative change. It is from this project that the idea of evaluation as a 'bridging tool' first emerged (see Bonamy, Charlier and Saunders 2001). The work-package was a free-standing area of research and development within the overall project

The RECRE&SUP project (which means in french "Réseau de Centres de Ressources pour l'Enseignement Supérieur") consisted of ten universities, 5 from the french speaking community of Belgium : the universities of Namur, Louvain, Mons, Liège and Brussels and the EM universitiy of Lyon, Geneva, Madrid and Lancaster. The universities were all different, had their own histories, strategies and structures. This diversity can also be found in each institution, in other words, the universities are heterogenous and loosely coupled (see Weick 1988). That means that the changes envisaged by university policy are likely to produce far more varied responses from the different departments (than in a tightly coupled system) or indeed, in some cases no changes at all and that in this type of organisation the actors conceptions of the organisational context for changes occurs relatively free from organisational determination.

Within RECRE&SUP, the role of the evaluation work-package was centred specifically on 20 innovative courses (two per institution)delivered by the partner institutions. The courses and the circumstances for innovation were all quite different but they all focused on the use of ICTs. The work-package evaluated the change process with particular reference to the way in which these innovations connected to wider institutional change through the perspective of the course innovators. The innovative impetus as understood by the course innovators was the specific focus. [See Bonamy, Charlier and Saunders 2002].

The courses from the RECRE&SUP project form the focus for the rest of this paper and provide the exemplars.

Toward a theory of evaluation as a bridging tool

The evaluation approach we advocate could be understood as an 'evaluation for knowledge' as Eleanor Chelimsky (1997, p100) would have it. This means that the evaluative dimension of the project is built into the design and can be justified as evaluative research in which the evaluation was primarily undertaken to obtain 'a deeper understanding in some specific area or policy field'. This approach can be distinguished from a developmental or accountability imperative. However, it would be wrong to see the evaluation activity as divorced from the development of the two projects; indeed we can see the way the evaluative evidence from the first year of the projects had a direct impact on the manner in which the collaborative activity was supported in the second year.

The evaluation dimension of the two projects was clearly identified as an independent workpackage. However, the evaluation was not an evaluation of the project but an exploratory development in which the role of evaluation within a change process was researched and reconfigured. We argue that it is necessary during the evolution of a change, embodied in an innovatory project, to give meaning to the process [evaluation as sense making] as a support for the actors, in the first instance the course innovators. By sharing their questions and observations a common frame of reference is enabled which might guide action in each experimental location while respecting the diversity of each of the participants' contexts for action. The ultimate aim of evaluative sense making is to help build common knowledge that could be shared by all the actors in a project network. In order to develop an approach, which addressed the issues of diversity, flexibility and complexity, we first developed a clear understanding of the general processes, which characterise a change from the course innovators' points of view.

In endeavouring to accomplish this task, we began to develop ideas on the role of evaluation in changing or transitional environments, which might have wider application. In order to develop these change strategies at the level of the course innovator, we have developed and adapted a 'Theories of Change' approach to our work in analysing the organisational context of change in our case study courses. Essentially it adopts the perspective of evaluation and institutional research in which key participants are asked to consider how the activities they are undertaking will produce intended outcomes. In other words, what theory do the key stakeholders have (often implicit) about the way change can be produced by certain types of action? It might be a learning theory or it might be a theory about how organisations change (e.g. pilots or experiments produce exemplars which are then adopted more widely in an organisation). The important thing is that key 'agents for change' are asked why they are doing what they are doing, on what basis. Initially, the evaluation approach could be identified in the following terms.

• the convergence of research and evaluation;

• an evaluation which distinguished between individual experience and institutional contexts;

An example of theory of change-based evaluation is that used by The Aspen Institute (Connell et al, 1995) in relation to the evaluation of comprehensive community initiatives.

Carol Weiss [95] suggests that all programmes have underlying 'theories of change' that have influenced decisions around programme design. Where programme design is not clearly specified or linked to the ultimate goals of the programme, the evaluators task is to clarify the premises, assumptions, hypotheses or theories that have guided decisions about the overall structure and specific components of the initiative. Once these have been elicited, they can drive the development of an evaluation plan that tests whether the programme theories hold up when the programme is implemented. Testing the programme's 'theories of change' is a means of assessing the progress and impact of a programme. RECRE@SUP falls into this category of change. There was another sense in which theory of change guided our evaluations. This was not quite in the sense offered by Connell or Weiss but in the use of theory to frame, set and orientate the focus of the evaluation. This is closer to the role of theory in evaluation outlined by Shwandt [2003] in which the 'rough ground' of the practical constitutes the proper and effective place for the use of theories of change. In other words, explanatory frameworks that make sense of practices that are changing, are appropriate resources for evaluation. Pawson [2003] makes a similar point in the same volume of Evaluation when he casts an analogous role for theory in evaluation. However, the differences in the evaluation activity reported here are that theory is held in the minds of course innovators and it is that which we are attempting to explore and we are doing it with the aid of 'ways of seeing' the change process that are derived from other more stable theoretical resources.

The meta-theoretical context

Our ideas were influenced by theory, which characterised the contemporary and fast moving environment at institutional (see Coombs 98, Saunders 98 and Fullan 98 and 2002), and societal levels (see for example Lash 95, Crouch 99 and Rotburg 2001), as complex, rapidly changing and uncertain. Equally, commentators have begun to consider the potential role for evaluation within such complex policy environments (see [START_REF] Sanderson | Evaluation in Complex Policy Systems in Evaluation[END_REF]. We have characterised a formative evaluation in these circumstances as a 'bridging tool'. Not only do the use of ICTs for learning involve significant challenges for single institutions, but its use in an international experiment, as in LEARN-NETT, has cross cultural system integration as an additional dimension. The way evaluation processes can aid the journey through this apparently over complex environment suggested to us the metaphor of a 'bridge'. The following discussion attempts to cohere the implications of structural modernist theory of social cohesion with ideas produced by the contemporary profile of society as chronically 'uncertain'. It is to the discussion of these concepts we will now turn.

Fullan's ideas (1999,2003) on change in complex educational environments suggest the need to accept complexity or diversity as a given in the design of a change process. His work, along with other commentators who have identified the rapidity of change and the creativity required to survive during these periods of chronic uncertainty (see Hann 94 and Hinchcliffe and Woodward 2000 for examples) suggests a move away from scientific-rational approaches toward those which are more sociologically informed. However, we also acknowledge that working effectively in these kinds of environments requires support: technical, social and educational. While we have attempted to demonstrate that to insist on conformity or to develop an over-prescriptive framework, particularly as Spencer-Mathews (2001) suggests in institutions of higher education, is a mistake, we have taken the view that we should look for the maximum opportunity for participating sites to express their own organisational stage of development in their participation in the project. This would however, be accompanied by some strong advice about the 'core' elements required and some tools which will enable progress to be made, including formative evaluations. This does suggest some difficult design challenges [START_REF] Trowler | Exploring the implementation gap: theory and practices in change interventions[END_REF]) from which we can take our thinking a little further. But why are 'bridging tools' derived from evaluation important in the contemporary environment of HE?

We have a concept of the kind of working environment, which will increasingly characterise the futures of the students participating in higher education institutions in Europe (See [START_REF] Saunders | Understanding Emerging Trends in Higher Education Curricula and Work Connections in Higher Education Policy[END_REF]. Along with the profile of contemporary working lives suggested by the writers cited above, characterised by risk, uncertainty and complexity, these requirements have become packaged and to some extent have 'washed back' through policy pronouncements on the nature of the higher education experience. We can adapt and develop what Brennan et al. (1996, p8) suggest are pressures for change emerging from the division of labour.

Learners in higher education institutions move across a 'boundary' between the traditional environment of higher education into the post-traditional, and from higher education into the world of work. We see a need for a wide range of bridging tools to help learners and those supporting them to navigate these transitions. We coin the term 'bridging' because we have a concept of a journey and a metaphorical connection between places in two senses: just as a bridge takes an individual or group from one point to another, it also joins one place to another. We have a strong vision of the world our students will move into, and of a learning environment in a period of rapid change. In this sense 'bridging' means:

• enabling students to experience elements of future practice while learning;

• enabling students to move from one kind of learning experience to another.

• enabling the facilitators of student learning to innovate and change Our understanding of the term 'bridging tool' is guided by a specific learning theory.

Involvement in a research or development project, funded or otherwise, produces learning through the development of new communities of practice, either of learners or of workers in the new work order [START_REF] Lave | Situated Learning: legitimate peripheral participation[END_REF][START_REF] Wenger | Communities of practice, learning, meaning, and identity[END_REF]. Individuals and groups learn through the adoption of new practices and this process is active, situated and context bound, but essentially reflective. How might this learning be made accessible and useful to others and how might learners (as course innovators or students) be enabled to work together in a 'rehearsal' of new working practices?

We argue here that an evaluation approach which provides captured rehearsals, examples, metaphors, typologies, vignettes, cases, accounts and platforms, ways of working, principles of procedures, routines, in other words, depictions and can both evoke and enable the experience of boundary crossing and provide provisional stability for change that is to say, act as bridges. We see our evaluation approach inhabiting this site in the overall process of development by providing precisely these 'bridging resources' for participants and other interested parties.

Examples of metaphors, captures and typologies

In the RECRE&SUP project we have generated a range of grounded categories from the data, which attempt to capture the essence of the change process from the point of view of the course innovator, which we have identified as 'change agents'. It is these models, which will help to understand the change process and provide the provisional stability, to which we refer below, along with an existing theory of change. Thus we engaged in a mixed analytical methodology of established and grounded theory.

Enclaves, bridgeheads and embedded practice

Unlike other research on the process of change and change in HE in particular, we have been interested in exploring the course innovators' conceptions of the change process, how they have 'visioned' change and the organisational context for their course. Therefore the focus for this work has been on the way the process of change is conceptualised, perceived and experienced by this particular group. As we establish above, we can see the way in which the courses are relatively 'loosely coupled' (see [START_REF] Horne | Organisation and change within educational systems: some implications of a loose-coupling model in[END_REF] to the host organisation, providing the circumstance in which many conceptions of the organisational context for changes can occur, relatively 'free' from organisational determination. By 'coupling' we mean the extent to which parts of a system or sub system are responsive to changes in other parts of the system. In a tightly coupled system for example, if intended changes at the level of policy were introduced from the centre, we would expect parts of the system to be responsive to these changes and changes might occur of the kind evoked by the policy. In a loosely coupled system, changes envisaged by the centre's policy are likely to produce far more varied responses from the sub parts of the system or, indeed, no changes at all. In the HE cases we studied, it is clear that HE is loosely coupled in terms of curricular innovation based on ICTs.

The reports from the course innovators identified several features or prompts for change which supported the perception of HE as heterogeneous and loosely coupled. However, both projects have been able to produce a typology of 'change conceptions' we think might be useful in understanding and planning innovation in this area.

We use the following categories to denote how the case 'connects' to the wider organisational context in which it has been developed and which will embody the positioning of the proposed innovation in relation to how it might impact on the wider case. We use 'military' metaphors to capture or conceptualise this process. A case might lie on the following continuum (see Saunders 88 for an earlier use of this approach)

Figure 1 Positioning in the organisation enclave bridgehead

An enclave is a set of practices which exist in a larger organisational setting but which has characteristics which are distinctive, individuals within it subscribe self consciously to a different culture (or way of doing things) to the organisational norm and there are clear organisational, temporal and sometimes spatial differences which distinguish it from its organisational setting.

As far as change is concerned, we are interested in the extent to which and under what conditions an enclave has an impact on the wider organisation. In other words it begins to challenge wider practices in the organisation and so transforming itself from an enclave to a 'bridgehead' or platform for wider developments. This is important because in the use of evaluation as a bridging tool, we are looking for theories or strategies for the way in which enclaves enable wider change to happen. All the courses in RECRE&SUP began life as an enclave.

Related concepts which help to explain the relationship between an enclave and the wider context are the ideas of 'emergent' culture' within a 'dominant' culture in an organisation (see [START_REF] Williams | Problems in Materialism and culture: selected essays[END_REF]. We might say that as long as the new culture remains in an enclave then there is not necessarily any change at wider organisational level. However, once an enclave begins to develop as a bridgehead, then it can emerge as an 'oppositional' culture to the dominant culture and challenge its dominant position in the organisation providing the resources for a 'paradigm shift in practices'.

We were interested to note the way in which and under what circumstances cases designated in the first round of interviews had evolved over time. Thus, we observed changes which remained as an enclave, mainly because they had no theory or strategy for change in the wider context. We observed changes which began to move from enclave to bridgehead by adopting strategies for change and were making a limited impact on the wider context. We were able to identify changes that moved through the enclave stage to developing 'bridgeheading' strategies and on to create changes in embedded or routine practice. Finally, we observed changes which were designed as bridgeheads from the outset as they moved to impact on routine practice. These configurations might be understood as possible 'evolutionary routes' for change.

Bridgehead embedded practice

Broadly speaking, we adopt an approach to the evaluation of change and the positioning of evaluation in the change process that places 'social practice' as central (see [START_REF] Trowler | Change thinking, change practices: A guide to change for heads of department, subject centres and others who work middle-out[END_REF]. At its core, changes are concerned with adaptations of routine, day to day, rule governed behaviour or, in other words it is practice that forms the focus for evaluation [START_REF] Giddens | Central problems in social theory[END_REF]). Some of this behaviour might be reified in the form of systems and supported by an organisational 'architecture' or structure, but practice is at the heart of our concerns. From an evaluative point of view, we were interested in constructing the ways in which changes in practice were emerging through the 'lens' of the course innovator reflecting these conceptions back and aiding the move from enclave to embedded practice.

Developing the grounded categories and authenticating the analysis

The analysis reported here is based on a series of semi structure interviews with the course innovators of 20 courses in our case study HE institutions. These interviews were analysed using a range of interrogatory concepts the use of which is described below by progressively focusing until we were working with a series of syntheses. We have outlined above the use of established theoretical categories, below we identify the grounded categories in Figure 3. Underlying the analytical framework was a concern to apply the key concepts to all the cases using a set of themes. In the case of a, d, e and f we have generated a grounded typology. In the case of b, c and g, we have applied the enclave framework outlined in the discussion above to categorise the material. For a, d, e and f, we categorically analysed all the cases and derived 'master types'. We then re-applied these types to all the cases and allocated each to a type, cross checking the authenticity of the categories.

A problem with this analysis is that an example might have traces of more than one type.

Because of that, allocation to a type is more a matter of emphasis than exclusivity. Another interesting methodological point is that the course innovators did not necessarily understand the process they were engaged in as a 'change strategy'. The categories that emerged were inferred from the interviews. However, part of the strategy of 'bridging' involved a second phase of interactions with the course innovator in which the expression of the individual cases in terms of the grounded categories and the 'enclave' framework were checked and authenticated. Each case was re-presented to its course innovator 'owner' and a discussion took place in which the categorization was problematised and debated with them [see below].

All these categories were used to present the cases and configure the change process undergone by the course leaders but in the context of this paper, we will identify just one of the categories as an example of a grounded theory that was re-presented to the course innovators.

Grounded Theories or ideas of change

The type of change theory embodied in the interview account is identified below. Following the procedure we identify above, the following types of change theory can be discerned in the evidence gathered from the course innovators.

Practice based exemplar

There were examples where the course innovators discussed ways in which change might be produced by providing examples of how ICTs are used to improve the teaching and learning in a particular environment. The theory in this instance was that 'practical' embodiments of useful, interesting or innovative teaching will produce changes in individuals who are interested in adapting their practice or who feel change is inevitable or have other pressures to change. The idea of 'contagion' or the metaphor of epidemiology is interesting and apt here.

The theory of change embedded in this conception is relatively weak in that how and under what conditions an interesting exemplar would create changes within the wider system was not made explicit or remained opaque. This has been known as the epidemiological model of change in that a 'beacon' or enclave becomes a bridgehead by osmosis. Another perspective on this process may be that having a practice based exemplar is a necessary condition for change but is often not sufficient. Resources, political will and other chronic and conjunctural feratures of the environment might also have to be in place in order for change on a wider front to take place. The great challenge without these other factors in place is how to move from interesting but marginal enclave to influential bridgehead

Resource driven/dependent

This category understands change in terms of the resourcing incentive. Change will occur when there is a financial or resource incentive i.e. resources are offered on the basis of specified changes. In addition, change will not occur or at least is dependent on resources being made available to enable change to occur. This is an interesting example of 'categorically driven funding change'. Usually and also in the examples we have in the project, this theory identifies the way a centre forms a policy of development. It establishes criteria against which it invites bids for developmental funding. Only those bids, which display the desired profile of characteristics, receive funds. Resource dependent change might be defined as that which defines adaptation as strategies to reach compliance with external constraints. Change resourcing implies an exchange with the environment to acquire resources, which might, in turn create dependencies (Sporn 1999). This model does imply relatively tight coupling between University Departments and their Centres. In many cases, change prompted by central rhetoric requires resourcing at the level of the department.

Institutional rhetorical support

This category has a theory of change which is based on the framework provided at the institutional level. It should involve resource allocations as we identify above but at its minimum, it provides for legitimation for the changes which are sanctioned by institutional policy, put another way, it refers to institutional legitimation. That is to say change occurs when there is institutional power behind it. In most of the cases, institutional rhetorical support is not sufficient to produce changes. In that instance it is a partial theory of change. However, in many cases, institutional rhetorical support was present at the same time as practice based exemplars were being developed to embody desired changes. The process of change is interesting here in that many bottom up exemplars run ahead of institutional rhetorical support. At some point though, institutional rhetorical support is required in order to promote wider adoption.

Professional imperative (enriching student experience)

This change theory is based on the idea of teaching professionalism. Because a 'good' teacher will be interested in providing up-to-date, interesting, well supported material and processes which aid and deepen intellectual development, often collaboratively, he/she will be interested in using, experimenting and developing courses which take advantage of possibilities offered by ICTs. Whereas resource dependency relies on the assumption of tight coupling between central resource allocators and those who will implement change 'on the ground' and is based upon the premise of the efficacy of sequential, hierarchical processes of 'top-down' change, other change theories stress the greater effectiveness of bottom-up approaches to the implementation of change. According to critics of top-down change strategies (see for example Hjern & Hull, 1982;Yanow, 1987), top-down models of change rely too heavily on the assumption of power and control exercised by those at the top of systems (such as central government policy-makers) or within organizations (such as university vice-chancellors and senior management teams). In contrast, advocates of a bottom-up approach to change argue that it is vital to take into account the importance of such characteristics of loosely coupled systems as:

power relations, conflicting interests and value systems between individuals and agencies responsible for making policy and those responsible for taking action (Barrett and Fudge, 1981: 4).

Trowler (1998) also emphasises the necessity of taking into account the far from passive role of those who are required to implement change on a day-to-day basis:

to fully understand processes of change in any social context, we need an understanding of the nature of the ground-level interpretations of, and response, to policy (p.103).

As loosely coupled organizations, universities are staffed by academics that, for the most part, enjoy high degrees of autonomy within their departments -that is, at ground level. The case studies analysed in this paper illustrate a number of instances of the power of individuals to interpret policies in ways, which were consistent with their own professional values and practices.

Technological Determinism

This category understands change in terms of the imperative embedded in ICTs themselves.

There are three variations in this category. First, the technology itself requires students, teachers and managers and teaching arrangements to change practices because of its nature once introduced. Secondly, the institutions, agencies or centres have an imperative to have ICTs at the core of their activities to gain commercial advantage, to gain access to the global 'learning market' and to deliver curricula and learning opportunities more effectively. Thirdly, there are changes in the expectations of the students in terms of learning support and ICT infrastructure, this imperative has produced or will produce changes in the institutions as they attempt to match these expectations. This imperative becomes more acute in the 'continuing education' environment. The theory here is that educational institutions are learner sensitive, particularly in a global market.

Creating evaluation based bridging tools for provisional stability

The categories presented above were one of a series used by the evaluation team to create provisional stability. Provisional stability is the central term we use to refer to circumstances, or even tools, which allow for a degree of stability necessary in order to move from what Emile Durkheim termed anomic (conditions of normlessness) to a new framework for action (Durkheim 52). Durkheim originally used the concept of anomie or normlessness to describe conditions of normative instability or uncertainty in periods of rapid change in which individuals have lost the taken-for-granted certainty of unacknowledged rules, which shape daily lives. Under these conditions he noted a statistical rise in the rate of suicides. To borrow the thrust of Durkheim's argument and following the theoretical implications of the discussion above, we can denote contemporary circumstances, at all levels in society, as those, which threaten 'chronic anomie'.

However, while it might be the case that we can depict contemporary society in this way, how might these ideas be relevant to change in institutions specifically, especially those introduced by the use of ICT? We suggest the hypothesis that in such a phase of transition or change, new rules are not yet established and a state of institutional anomie can occur. This relative instability is characteristic of any change process and is on a continuum from catastrophic uncertainty in which organisational life might be quite intolerable to the much more prosaic circumstances in which course changes or innovations are being attempted which challenge conventional or dominant practices. It is in the second of these circumstances we most often find ourselves and to which our remarks are directed.

What happens in educational institutions in which rules and practices are well established and validated, when a new event changes or challenges the traditional practices? (see Coffey 2001) Instead of the psycho-social notion of 'resistance to change', we think that the theory of Durkheim and followers which analyses human responses in times of social change may be of use to interpret situations in which change or the will to change creates challenges to existing practices (see also Greenwood 98).

We created depictions, vingettes or case studies which are examples of the kinds of resources it is possible to offer course innovators engaged in the change processes studied in this evaluation. They were used in a variety of contexts but each with the aim of increasing understanding of the change process in which they had been a part. Our hypothesis is that in the process of change uncertainties arise (a form of anomie) that can inhibit onward planning and development. By engaging course innovators in these evaluation products (depictions), increased understanding of the change occurs and course leaders have diagnostic resources

[bridging tools] available on which to create adjustments, strategies and future direction. In other words they have the provisional stability with which to plan.

To reiterate, there were several stages in which the depictions were used to create provisional stabilities. We have identified the stage in which initial depictions were discussed with course innovators. Each course innovator was shown the depiction of their course and also the enclave model and the grounded categories derived from the initial analysis. The accuracy, applicability and evocativeness of the framework and the depiction were authenticated with them. Interestingly, the categories had 'values' embedded in them that were unanticipated by the evaluators. For example, there were instances where the designation of 'enclave' was hotly disputed because the course leader imputed a negative rather than descriptive connotation to the term. Once the depictions were stabilised, a discussion began about the implications for the change strategy of the course innovator. Some remained intellectually interested but with no particular intention to act on the implications of their depiction. In some cases this was not a matter of individual decision-making, but there was a sense in which they felt unable to fully respond because of institutional factors such as a lack of resources or political will. Others had their change theory confirmed, others considered a gap between their expectations and the logic of the implicit change theory they were acting upon and considered changes. Others used the depictions in discussions with their course teams.

We have included below three examples of course depictions. They are all different but we have chosen each case on the basis of its relationship to categories in the enclave model [enclave, bridgehead, embedded] and highlighted the grounded 'theory of change' category that most typifies the case.

Case study 1: enclave

For more than ten years, Professor Novo has taught organisational analysis to the second year of his university. Each year he has about 60 students and over the years has tried to keep his subject matter up to date and to encourage his students to actively work in groups in case study analysis.

In 2000, he decided to suggest to the students to carry out their work partly by distance learning using discussion fora. This teaching and learning strategy addresses a double pedagogical concern. On the one hand, it sought primarily to stimulate student activity and to develop at home a capacity for meta-cognitive reflection on the students' exchanges (what are their spontaneous approaches to the case studies, how do they exploit group theory?), on the other hand, it was a response to the realities of life as a mature student, offering them the chance not to attend certain seminars and to carry out their activities at a distance.

This choice reflects the will of an individual even if some of his closest colleagues are sympathetic to it. The perception of change is clearly affirmed: 'It's about improving my method of teaching. About using what technology can bring to meet the specific needs of adult students.'

The change is perceived, in the first place, as a professional necessity i.e. a good teacher invests himself in the course and seeks to improve it. The dominant change theory for his individual action was professional imperative.

The institution allows this professor entrepreneurial freedom, without giving him any particular assistance, but without however, creating any particular obstacles. The teacher on his part has no particular desire to make his experience known other than informally so he does not have an implicit theory of change with respect to the institution other than a weak form of practice based exemplar. It follows, then, that this case study will remain an enclave unless his practice is taken up in an unplanned way. The teacher sees himself as a practitioner who likes to experiment, rather than to live according to a routine, he estimates however, that he spends a lot of time setting up his course and that he must tackle numerous technical problems alone. He is not driven by other 'institutional motives'. His reaction to this depiction was intellectual interest and confirming but it did not create provisional stability for onward planning for wider changes.

Case study 2: Bridge-head Two IT teachers respond to a call for pedagogical initiatives newly launched by the university. This call for projects essentially supports the development of multimedia-type pedagogical products and constitutes a resource driven change. They develop a distance learning platform and see this development as a chance to experiment. They understand change as an opportunity to show that using a particular distance education platform to support self-learning is possible so that others might learn from it. In this sense it was a practice based examplar. The institution appreciated this development but does not foresee at the start any strategy for dissemination or evaluation. In the course of its first year, this project remained an enclave, the teachers seeing themselves as expert experimenters. They would like recognition by the institution and to obtain support for evaluation and experimentation of their product on a larger scale. In the course of the second year, the university management team decided to encourage the development of distance learning practices within the institution and chose to buy the platform and to put in place training of teachers in each faculty; they decide to designate one of the two teachers as responsible for this training. In this way the enclave became a bridgehead bridgehead. Using the platform and associated practices begin to develop within the institution. The two teachers confirmed the depiction and discussed further ways of embedding the practices associated with the platform across the institution. They identified institutional rhetoric as crucial during the next phase of development.

Case study 3: embedded

A professor of physics (of Polish origin) has worked for several years with his colleague at the Polytechnic Institute of Warsaw. Having recently discovered an interest in the use of ICT in the course of an informal meeting with the director of the resource centre of his University, he decided to try a joint experiment with his colleague and to develop a doctoral distance seminar using videoconferencing and a web site as resources. The object of the change is two-fold: it aimed to experiment with a new practice and to develop a new programme such that it would be recognised at international level. This change was a form of practice based exemplar in which the qualities of this approach would become widely apparent .

In the beginning, the teacher "fought his way through the fog alone". He considered himself a reasonable handyman and preferred to learn by himself, even if he recognised that chance and the references supplied by the resource centre had been decisive. During its first two years of existence the project remained an enclave and had hardly any effect on the practice of his colleagues and more widely on the institution.

However, after two years, he was taken up by his dean and was named as the person responsible for these kinds of developments in his faculty. He considered that change can be achieved by demonstrating practical realisations such as his (practice based example) and invites certain colleagues who had themselves introduced ICT use into their courses, to come and present their experience at a half-day event. In parallel, he continued to develop tools used for his course and developed, in collaboration with Warsaw, an open-source platform. This platform was adopted by several colleagues and by the resource centre with which he is increasingly co-operating thus forming a bridgehead. These initiatives are recognised by the institution and are taken into account for his promotion. A year later, several teachers in the faculty of Sciences are using the tool for their courses; reflective sessions take place at faculty level to review the entire programme from a more active perspective emerging as embedded practice. The depictions were discussed with him and he acknowledged that they captured the process of change accurately. He became more aware of the strategic conditions necessary to sustain the embedded changes and to avoid slipping back to an enclave.

The final stage of the creation of provisional stabilities during the RECRE&SUP project was the discussion of all the grounded categories and the enclave framework with participants from all the institutions in the project in a dissemination event. The participants in this event were asked to work in groups to discuss the analyses. The idea was to support reflection on the change process by asking simple focusing questions which generate sensitive rehearsals and problem solving. They in effect created more generic knowledge based provisional stabilities. The questions were consistent with those asked of the individual course innovators, for example:

What do you think of this case? Does it make you think about situations you've already encountered?

What do you think about the roles of each of the actors?: professor, resource centre, institution (dean)?

What implications are there for on-going change strategies in your circumstances?

Feedback from this event suggested these depictions had acted as a resource for understanding the implications for change on the part of a group of innovators. It is this group who were particularly receptive to this kind of approach.

Overview

In this paper we have developed the argument that in a situation characterised by transition from one relatively stable environment to another, stakeholders involved in the change respond positively to evaluative tools of reference (bridging tools) that help create a framework for action. These tools are the products of evaluation composed of embodiments of the change process, grounded theories of change or depictions of change. We have termed this kind of resource and the role they might play as the creation of provisional stabilities.

The experience of evaluation in two SOCRATES projects helps to think of some of these tools that might support development. We argue that instead of trying to reduce complexity by searching for common solutions or systematised approaches, with the aim of creating a stable framework that could force change, we prefer a framework that helps participants in a change process to create situated provisional stabilities for change. In this way, the design of evaluation processes and practices will provide resources for 'sense making'.

In summary our argument is as follows. We are working and learning in circumstances that can continually produce periods of 'normlessness' and uncertainty and lead, in some extreme instances to destructive instability but more often discomfort, indecision and insecurity. Under these conditions it can be very difficult to act and plan. Learning changes in HE, often prompted by new ways of learning linked to the introduction of ICTs, can produce such instabilities as a transition is made across a boundary from one culture of practice to another and, for learners, from HE into new work practices.

Learners, teachers and course innovators in HE can be supported by constructing provisional stabilities as they seek creative solutions to problems created by change. These provisional stabilities are created by reflecting on and the understanding of change, enabling choices or decisions for future action. The experience reported here suggests formative evaluations can provide the resources for such reflections and act as a bridging tool for planning and innovation.

Figure 2

 2 Figure 2 The evolution of change

Figure 3

 3 Figure 3 The seven thematic areas of interest

Figure 4

 4 Figure 4 Course Innovators' theories of change Practice based exemplar Resource driven/dependent Institutional rhetorical support Professional imperative (enriching student experience) Technological Determinism


Sangyong Lee

Cheonshik Kim

Seongah Chin

An optimized sub-texture mapping technique for an arbitrary texture considering topology relations

In recent years, texture mapping techniques have become more advanced as providing real-time rendering tasks. However, few methods have been conducted in optimizing a sub-texture mapping for an arbitrary texture. In this paper, we present a method to optimize sub-texture mapping by reflecting topology relations in which an arbitrary sub-texture source has to be represented as minimizing distortions of the sub-texture source. We have defined a manipulating mechanism that helps a user control a texture source using a track ball interface in order to minimize loss of the texture source. And a sub-texture frame has to be aligned to dominant geometric structures of 3d model by employing some transformations. We have shown experimental results to verify the proposed method as well.

Introduction

In general, texture mapping is one of the fundamental techniques which are broadly used to enhance the final appearance of a 3d model by attaching a texture source into the 3d model. In recent years, 3d video games have extensively utilized some advanced texture mappings in real-time rendering such as normal mapping, parallax mapping and displacement mapping etc [START_REF] Sloan | Normal Mapping for Precomputed Radiance Transfer[END_REF][2] [START_REF] Szirmay-Kalos | Displacement Mapping on the GPU -State of the Art[END_REF]. Even in game industry it is becoming more and more important to create cinematic appearance of digital scenes. In certain applications, we need to attach sub-textures like face paintings, scars, wounds, and decorations. Texture parameterization between a set of object mesh and a subtexture source is critical to minimize texture stretch or texture deviation [START_REF] Sander | Texture Mapping Progressive Meshes[END_REF][5] [START_REF] Neyret | Pattern-based texturing revisited[END_REF]. However very few researches concerning sub-texture mapping techniques for an arbitrary sub-texture have been reported, which implies they do not seem to reflect topology relations between the geometric structures of a 3d model and a sub-texture source. This fact causes some loss of the texture source that has to be appeared when the sub-texture source is clapped or scaled. If the sub-texture is larger than the region of meshes where a user wants to attach it then the source has no choice but to lose the boundary area. In the case we reduce the source image so that some parts mostly around the boundary of meshes would be filled with background source. In fact, we have to make alignment of the sub-texture source corresponding to the geometric structures by employing interactive interface manipulated by a general user in order to keep the sub-texture source as closely as we really want. Hence, in this approach, we propose an optimized sub-texture mapping for an arbitrary texture by reflecting topology relations between a 3d models and a sub-texture source. The motivation of the approach is to avoid loss of the sub-texture source. At first, a trackball interface is defined to manipulate a 3d model, which helps a user control a texture source in order to minimize loss of the texture source. Rotation and scaling transformations are required to align the texture source to dominant geometric structures of 3d model. We have shown experimental results to verify the proposed method as well.

2

The proposed approach

The fundamental idea of the approach comes from how to attach a sub-texture image as is without losing any parts. A texture coordinate of a source image has to be accurately matched into a vertex on a 3d mesh model, where a user wishes to attach. However it is not easy to succeed in what we want since geometric structures of a 3d mesh model are not necessarily corresponding to a texture source frame. Hence, we have to seek a proper method to align a sub-texture source to suitable match of the vertices of a 3d model.

Trackball Interface

We have to keep in mind that a proper match between geometric structures of a 3d mesh and a sub-texture source needs to be solved when texture mapping is carried out. At first, we fix the sub-texture source on the screen then we have employed a trackball interface that makes us keep adjusting transformation of the 3d model until we acquire what we want to have with the sub-texture source. This trackball interface is suitable since it can provide flexible controls to let a user manipulate the 3d model. As shown in Fig. 1, there are several cases that we may expect when doing subtexture mapping. A user picks a specific mesh on a 3d model where he wants to represent a sub-texture. A sub-texture can be clipped as shown in (a). Reduction of a sub-texture source is shown in (b). A wanted mapping appears in (c) after rotations of the sub-texture source. A user can utilize a trackball interface in an interactive way that may provide flexible control to match what they want to represent with a subtexture by rotating the 3d model. In particular, it is critical to provide an accurate matching when a sub-texture source seems to be complex enough with sophisticated patterns since we do not want to expect lots of losing the sub-texture source. To realize a trackball interface, Eq. ( 1) is used.

                 y x y x y z x z y x z x z y x z y y y z y x y y z y x z y x x y y z z zyx R R R R                                
) ( ) ( ) ( , (1)
where the rotation angles with x, y, and z axis are θ x ,θ y and θ z . And R x (θ x ), R y (θ y ) and R z (θ z )indicate the transformations of rotations.

Texture Alignment

Let a center mesh that a user clicks and wants to attach a sub-texture source be f p source. This center mesh is composed of three line segments. Let the longest line segment be f q among three line segments. Then we can acquire the rotation angle θ using inner product of two vectors as shown in Fig. 2

Scaling Interface

If the mesh that a user selects is skewed and stretched along one direction and a subtexture source is like a square or round shaped, we require a scaling transformation in order to represent the sub-texture sources that we want to attach. If we do not deal with the surroundings, then some parts of the sub-texture source cannot be appeared since the mesh looks skewed. To solve this, we understand that 3d coordinates on the mesh model are projected onto the screen coordinates. In the processing this procedure, the normalization has to be done using the maximum and minimum coordinates which will be used as texture coordinates. In Fig. 3, we display the conceptual diagrams to help us comprehend the approach of scaling. The mesh is shown in Fig. 3(a). Horizontal scaled texture mapping and vertical scaled one appear in Fig. 3(b) and (c) respectively given the texture source in (d). The screen coordinates can be translated into texture coordinates using Eq (2).

) ) min( ) max( , ) min( ) max( ( ) , ( y y y x x x y x      , (2)
where (x, y) is the screen coordinates and (x' y') is the texture coordinate.

Results and Discussion

To verify the proposed methods, we have carried out experiments under Intel Core (TM) i5 CPU 750@2.67GHz, 2.99RAM, NVIDIA GeoFore GTS 250 (VGA) with Windows XP Professional. The proposed methods have been realized using Microsoft MFC and OpenGL API. The comparisons between the proposed methods and the general method that does not consider automatic transformations have been conducted.

In the experiments, we have made a number of texture samples that can be used in face paintings and decorations of the face. We have carried out the proposed texture mapping by attaching the sub-texture onto the 3d face model. The sub-textures are composed of face painting pictures shown in Fig. 4 on the first row. Face painting sub-texture mapping results have been created with scaling factors 1, 0.9, and 0.8 shown in the first, second and third respectively from the left in Fig. 4. The proposed method and mesh models are shown in the fourth and last column in Fig. 4. As we have shown here, the proposed method creates the sub-textures as good as the original ones comparing to the other results mostly showing loss of the sub-textures. In Fig. 5, we have shown loss rate (%) comparisons computed by the number of loss mesh in Fig. 4 indicating that the proposed method in the fourth column in Fig. 4, shows better loss rate than others created by scaling factors observed in the first, second and third column in Fig. 4.

Authors want to mention that mesh tagging tasks are skipped in this article, which will be reported in the other article, since mesh tagging tasks required for sub-texture mapping are beyond the scope of the proposed method.

Concluding Remarks

In this paper, we present a technique that makes it possible to automatically create an optimized sub-texture mapping. This basic idea is from matching topology relations between geometric structures of a 3d model and a sub-texture source. The approach starts with providing a trackball interface that utilize a convenient user control when texture mapping. Once a user gains a sub-texture source then a 3d model can be manipulated using the trackball functions until the user is satisfied with the texture appearance. This functionality makes the sub-textures be as good as the appearance the user wants to attach with keeping the sub-texture source as much as we represent.

Fig. 1 .

 1 Fig. 1. Variant occurrences of texture mapping

  (a). Once we have carried out the rotation then the sub-texture source is aligned to the mesh model. The final appearance looks as shown in Fig. 2 (b).

Fig. 2 .

 2 Fig. 2. Conceptual diagram of rotation

Fig. 3 .

 3 Fig. 3. Conceptual diagram of scaling.

Fig. 4 .

 4 Fig. 4. The first row shows the sub-texture sources. Face painting sub-texture mapping results are shown with scaling factors 1, 0.9, and 0.8 in the first three columns. The proposed method and mesh models are shown in the fourth and last from the left column.

Fig. 5 .

 5 Fig. 5. Loss rate comparisons

Acknowledgement

This work was partially supported by Korea Science and Engineering Foundation (NRF) grant funded by the Korean government (No. 2012-0002889).


Jia Jianbin
email: jiajianbin.nudt@gmail.com

Chen Yingwen

Ming Xu
email: xuming@nudt.edu.cn

An Empirical View on Opportunistic Forwarding Relay Selection Using Contact Records

Keywords: opportunistic networks, relay selection, residual expected delay, delay reduced ratio

Opportunistic routing schemes usually infer future contact time to select next hop relays. But the effect of relay selected in this way is uncertain. In order to get further understanding of the intrinsic uncertainty characteristic of relay efficiency, this paper makes an empirical investigation on opportunistic forwarding relay selection schemes using contact records. Based on the underlying opportunistic vehicular network extracted from large-scale realistic vehicle traces, we evaluated the efficiency of relay selection and got some intrinsic sight of opportunistic forwarding. The questions we investigated are: What is the probability that a selected relay can make the end-to-end delay reduced? How much the latency can be saved by a properly selected relay? Such an empirical study is meaningful for the protocol design and applications deployment in future opportunistic networks.

Introduction

In Delay Tolerant Networks (DTN) or Opportunistic Networks (ON), carry-andforward technique is the major method used for delivering messages. Direct Forwarding (DF) is the most basic scheme, in which messages are carried until the source node contacts with the destination directly. Relays may be involved to assist data exchange in order to obtain better delivery performance. In this case, a primary issue is how to select effective relays. A lot of schemes proposed in previous literatures make relay decision based on the predication of future contact opportunities from history information of connectivity between mobile nodes [START_REF] Lindgren | Probabilistic Routing in Intermittently Connected Networks[END_REF] [START_REF] Nelson | Encounter-Based Routing in DTNs[END_REF]. However, the inaccuracy of predication in practical leads to the selected relay(s) has only an incidental rather than intentional effect on delivery metrics such as endto-end delay [START_REF] Balasubramanian | DTN routing as a resource allocation problem[END_REF]. For example in Fig. 1, if we assume node is selected as relay, whether the delivery delay of relay assisted forwarding ( → → ) is really lower than that of direct forwarding ( → ) is questionable. In addition, whether the selected relay node has more time saved than other candidate nodes in , , ⋯, and is still unclear. For such "incidental" relay efficiency, this paper provides an empirical study in the background of vehicular DTN. In particular, we mainly focus on the following questions: How to select a proper node as relay? What is the probability that a relay can make the end-to-end delivery delay reduced? How much latency time can be saved by a properly selected relay?

The main contributions of this paper are: [START_REF] Lindgren | Probabilistic Routing in Intermittently Connected Networks[END_REF] We introduce an more effective opportunistic relay selection scheme based on Residual Expected Delay (RED), which utilizes local pairwise contact records and the elapsed time since last encounter to estimate residual encounter time. (2) Based on the underlying vehicular DTN, we investigate relay efficiency in terms of the ratio of delay time can be reduced and the number of possible relays can be selected. Empirical results reflect that the relay efficiency is related to the distribution of direct forwarding delay.

The structure of the paper is organized as follows: The next section presents related work, the third section introduces the RED based relay selection scheme and the estimation framework of RED value. Section IV gives the detailed evaluation results and analysis of relay efficiency in underlying vehicular DTN. The conclusion of this paper is made in Section V.

Related Works

The core issue of opportunistic messages forwarding is relay selection. Using the knowledge of history contact records between mobile nodes to assist forwarding decision is an important method. S. Jain et al. [START_REF] Jain | Routing in a delay-tolerant network[END_REF] proposed the Minimum Expected Delay (MED) algorithm in which the value of expected delay is defined as the average waiting time calculated from connectivity schedules of mobile nodes. Evan P. C. Jones et al. [START_REF] Jones | Practical routing in delay-tolerant networks[END_REF] improved MED and propose Minimum Estimated Expected Delay (MEED), where the expected delay is calculated using the observed contact history of a sliding history window. While H. Chen et al. in [START_REF] Chen | On Using Contact Expectation for Routing in Delay Tolerant Networks[END_REF] proposed a forwarding scheme that each node decides whether to forward the message to its current encounter by comparing their minimum expected meeting delays (MEMDs) to the destination. The MEMD is calculated based on the past inter-contact times between each pair of nodes and the elapsed time since their last contact. Our work also uses history contact records to predict residual encounter time with considering the elapsed time from last meeting time. The difference lies in that we focus on the direct forwarding residual delay time and employ a per-contact relay decision scheme. Particularly, we make an empirical investigation on the relay selection methods. Such a work provides some insight into the opportunistic forwarding scheme in practical.

RED based Forwarding Scheme

In this section, we describe the Residual Expected Delay (RED) based relay selection scheme. RED is the estimation value of residual meeting time for a pair of nodes.

Residual Expected Delay Estimation

Assume each node records the last + 1 meeting times with others. For a pair of nodes, the records are represented by time series , , ⋯ , , where is the most recent record and is the oldest record. If current time is , then ET is calculated as = -. Thus, the last inter contact time (ICT) series can be calculated as -, -, ⋯, -. To be described conveniently, we denote the ICT series with , , ⋯ , , in which the ICTs are sorted by length. Thereby, the residual encounter time for a node pair can be estimated as follow.

Given a set of ICT records of node pair -are , , ⋯ , , where ≤ ≤ ⋯ ≤ . If the elapsed time from last meeting between and to the relay decision moment is , and ≤ < , then the expectation of residual encounter time for -can be calculated by

[ ] = ∑ - (1)
Note, when the elapsed time is lower than the minimum value in { , , ⋯ , }, i.e.

< , the residual delay estimated according to Eq. 1 degrades to the mean inter contact time (MICT). While if is equal to or greater than the maximum value in { , , ⋯ , }, i.e. ≥ , Eq. 1 is invalid to estimate the residual delay. In this situation, we also use the mean inter contact time as the estimation value as well. Therefore, Eq. 1 is improved to be as the following

[ ] = ∑ -, ≤ < ∑ , < ≥ (2)

Residual Delay based Relay Selection Decision

Suppose from the time node injects a message (Msg), which is target to the destination node , to the time contact with directly, will meet a set of nodes, represented by = { , , ⋯ , } in chronological order. In order to reduce the delay time of direct forwarding, may choose a node from to assist the transmission of Msg. Therefore, can be regarded as potential candidate set of relay. Naturally, the central issue is how to find out an appropriate node from to be utilized as relay.

Residual delay is an effective metric for relay selection decision, which refers to the time from a relay decision moment to the time that the message arriving at destination successfully. Formally, the RED based relay selection strategy is described as following. Assume represents the residual delay of a message delivered from node to directly. , , ⋯, are the intermediate nodes that source node met before the target . The relay selection judgment is determined by comparing the residual expected delay values (calculated according to Eq. 2) of node pairs -and -.

RED Based Strategy:

For ∈ { , , ⋯ , }, if ≥ (3)
then is regarded to be fitting for carrying and forwarding Msg to .

Empirical Evaluation

In this section, we present the empirical investigation results of RED based relay selection strategy. The evaluation is carried out with Cabspotting [START_REF] Piorkowski | A Parsimonious Model of Mobile Partitioned Networks with Clustering[END_REF] taxi traces. These taxis operate in San Francisco city Bay area with a core driving coverage of about 11 × 13 . A Cabspotting trace dataset containing the trace records of 536 vehicles within 25 days can be found in CRAWDAD [START_REF]CRAWDAW[END_REF]. We randomly generate a test set composed by 8000 pairs of source-destination ( -) combination. To avoid the delivery time of -sessions being beyond the record time span in the trace dataset, the messages sending requests are randomly injected by node within the first three days of the records.

To investigate the RED based relay selection method, we design a two-hop opportunistic forwarding algorithm with single copy scheme, in which, only one relay node is needed, and there exists only one replication of message in the network, i.e., if the previous carrier forward the message to the next node, it will discard its own replica. The algorithm uses the per-contact relay decision paradigm, in which the message sender (or carrier) makes a judgment at each time when it meet with a potential relay node, until the message is hand over. Although the two-hop single relay forwarding algorithm is somewhat naive, it is able to generally reflect the relay efficiency of opportunistic forwarding scheme in practical. In addition, we compare RED based forwarding scheme with MICT based scheme [START_REF] Jain | Routing in a delay-tolerant network[END_REF] [START_REF] Jones | Practical routing in delay-tolerant networks[END_REF] in which the mean inter contact time value is used as a rough estimation of residual delay time.

Performance Metrics

We call the constraint conditions used for relay selection as Qualified Condition, such as Eq. 1. Nodes satisfying qualified condition are called Qualified Node. Generally, a qualified node is expected to have the ability of reducing delivery delay of messages, but whether it can achieve such a benefit is not sure. For distinguishing, we refer to the qualified node satisfying delay reduce expectation as Good Relay. Percentage of delay reduced and the ratio of good nodes in qualified nodes reflect the efficiency of the relay qualifying strategy. Assume the direct forwarding delay is denoted by , and the relay assisted delivery delay is denoted by . Then, the two metrics to investigate the performance of opportunistic relaying scheme are defined as follows.

 Delay Reduced Ratio (DRR): DRR is measured with the delivery time saved by relay forwarding compared to the delay of direct forwarding. Formally, =  Good Relay Ratio (GRR): GRR is defined as the ratio of good relay number to the qualified node number. Formally, =

Delay Reduced Ratio

First, let us look at the average delay reduced ratio of potential relays in different candidate sets. Three relay candidate sets are considered: (1) all potential relays without qualified condition filtering (all the nodes met by before it meets ); (2) MICT based qualified nodes according to Eq. 3; and (3) RED based qualified nodes according to Eq. 3. As displayed in Table I, The average DRRs for the three relay candidate sets are about 3.93%, 10.25% and 23.85% respectively. Meanwhile, when only considering good relays in those candidates, the average DRRs are about 27.79%, 32.00% and 44.88% respectively. Such result suggests that taking into account the elapsed time is effective when choosing relays in opportunistic forwarding. And it implies when properly selected a relay with RED based strategy, more than 40% of delay time could be reduced in a general view. Then, we investigate the distribution of average delay reduced ratio correlated with direct forwarding delay. Fig. 2 shows the average delay reduced ratio in different direct forwarding delay levels. DRR is represented by the vertical axis, while DF delay is represented by the horizontal axis. To reflect DRR under different DF delay levels, we divide the horizontal axis into the unit of a day's time, and then count the average DRR in each DF delay level. For example, the average DRR corresponding to 10 days in horizontal axis means the average DRR of those -pairs whose direct forwarding delay is larger than 10 days and lower than 11 days. Both of the figures show that the average DRR of MICT qualified nodes is a little better than the average of un-qualifying relays. In the same time, the average DRR of RED scheme is much better than others. Particularly, when DF delay is higher than 5 days, RED scheme is more advantageous.

For a determined single relay, if we consider the basic first meet relay (FMR), the average DRRs are exhibited in Table II and Fig. 3. The basic FMR uses the first met node as the single relay without judgment. MICT-FMT or RED-FMT respectively uses the first met node satisfying MICT or RED based qualified conditions as the single relay. It is apparently that the FMR result is mainly in accordance with the trend of general average situation introduced above. This proves a relay selected with RED is more effective in reducing opportunistic forwarding delay.

Discussion: From Fig. 2(a) and Fig. 3(a), we can also learn that, when the DF delay is lower than one day's time (corresponding to zero in horizontal axis), the average DRRs of all three schemes are lower than zero. This suggests that under this con-dition, direct forwarding is likely to be more effective than taking a relay. On the other hand, the corresponding DRRs of good relay showed in Fig. 2(b) and Fig. 3(b) perform quite well. This difference is resulted from that good relays are relatively less in the potential relay candidates, which is the paradigm examined in the next part.

Good Relay Ratio

Fig. 4 shows the average good relay ratio corresponding to different DF delay levels.

We can find that when DF delay is higher than one day, the good relay ratio of RED scheme is much better than that of MICT scheme and all potential one's. This indicates that a RED qualified relay has higher probability to make the delivery delay reduced. In other words, it proves the RED based relay selection decision is more accurate than MICT. Another noteworthy feature is that when DF delay time is less than one day, the good relay ratio is also very low. This confirms the observation that direct forwarding is likely more effective than using relay in low DF delay level, where the good relay ratio is only about 40%. Discussion: Considering DRR and GRR jointly, we can see that when DF delay is high, relaying schemes have better DRR and GRR at the same time. Therefore, relay forwarding is more effective than direct forwarding. Particularly, in the scenario of underlying vehicular DTN, when DF delay is larger than one day's time, it is prefer to use relay scheme. On the other hand, when DF delay is lower than one day, direct forwarding has better delivery performance. This can be confirmed in Fig. 5, in which the cumulative distribution of direct forwarding delay, average delivery delay of MICT qualified relay forwarding and average delivery delay of RED qualified relay forwarding are plotted. In fact, the CDF shows when DF delay is lower than 20 hours, direct forwarding is more promising in delivery ratio.

This insight of efficiency transition between direct forwarding and relay forwarding would like to maintain in other opportunistic network scenarios with specific critical DF delay value. From another point of view, this insight suggests it is more proper to use a hybrid multi-copy scheme which uses relay forwarding and also retains direct forwarding. It also reflects that the relay selection scheme only using contact records is inefficient when DF delay is low. More effective method or improvement should be proposed to remedy this drawback.

Fig. 1 .

 1 Fig. 1. Example of Relay Assisted Data Delivery

Fig. 2 .Fig. 3 .

 23 Fig. 2. Delay Reduced Ratio in Average

Fig. 4 . 5 .

 45 Fig. 4. Average Good Relay Ratio Fig. 5. The CDF of Delivery Delay

Table 1 .

 1 Overall Average Delay Reduced Ratio

		Potential Relays	MICT Qualified	RED Qualified
	All Relays	3.93%	10.25%	23.85%
	Good Relays	27.79%	32.00%	44.88

Table 2 .

 2 Average Delay Reduced Ratio for First Meet Relay

		Basic FMR	MICT based FMR RED based FMR
	First Relay	6.77%	11.50%	15.20%
	First Good Relay	35.60%	37.22%	53.75%

Acknowledgments. This research is partially supported by the National Science Foundation of China under Grant No. 61070211 and No. 61003304; and Hunan Provincial Natural Science Foundation of China under grants No. 09JJ4034.

Conclusions and Future Work

In this paper, we introduced a residual expected delay based relay selection scheme, and made an empirical investigation on the opportunistic relay efficiency. We demonstrated the relay efficiency in terms of delay reduced ratio and good relay ratio. Evaluation result shows that the RED based relay selection scheme taking into consider the elapsed time exhibits better performance than the mean inter-contact time based scheme. However, the correlation between relay efficiency and direct forwarding delay implies that when the direct forwarding delay is lower than some value, opportunistic single relay assisted delivery is likely to not obtain benefit in reducing end-toend delay. Therefore, the helpfulness and harmfulness of opportunistic relay forwarding should be reconsidered.

In the next step, we will look at the performance of multi-relay opportunistic forwarding schemes in different realistic scenarios. Another problem drawing our attention is to deal with the ineffective relay selection in low direct forwarding latency.