Bettina Migge

Greeting and social change *

Keywords: greeting, structure of greetings, social relations, social change, Eastern Maroon community

This paper discusses greeting routines in the Eastern Maroon community of Suriname and French Guiana. The paper argues that there are two broad sets of greeting routines. They have different origins, linguistic structures and distinct social meanings (e.g. setting, social groups, social relationship). As a result of social changes in the community, their social distribution, frequency and their social meanings are currently changing. The 'urban' greetings are being extended to all kinds of new social spheres and are increasingly losing their negative or subculture connotations while the 'village' greetings are becoming restricted to a relatively small set of situations and kinds of interactions. Moreover, new kinds of greeting practices emerge to symbolically assert existing social distinctions and to mark newly emerging social realities.

Introduction

Greetings have been a recurrent object of inquiry in several disciplines such as ethnology, linguistics, anthropology and sociology (see Duranti 1997, 2001 for an overview). While in ethnological research greetings were "studied as a means to uncovering some of the evolutionary bases of human behavior" (Duranti 1997: 64), linguistic research has mainly concentrated on the sequential nature of greetings (Schegloff 1968, 1979, 1986; Schegloff and Sacks 1973; Sacks 1975). Ethnographic studies (Goody 1972; Irvine 1974; Salmond 1974; Youssouf, Grimshaw & Bird 1976; Caton 1986, Duranti 1992) provide thorough formal descriptions of greetings in different societies. They focus on their structure, their verbal content, sometimes also their nonverbal acts (cf. Duranti 1992), the contexts of their use, and their interactional meanings. They reveal that greetings play an important role in defining the nature of social relationships, interlocutors' social status or rank and their social identities. Irvine's (1974) study of greeting among the Wolof of Senegal (cf. Goody 1972), for instance, shows that the way people participate in a greeting activity (e.g. as initiator or as respondent of a sequence) defines their social status or identities. In situations in which the two parties "do not readily fall into a tacit agreement on their relative positions" (Irvine 1974: 175), they will try to negotiate their status by manipulating their participation in the greeting activity.

For example, the most important strategy to claim a "lower" social position, possibly to ward off financial obligations, is to try to initiate the various adjacency pairs that make up the greeting activity.

Other ethnographic studies discuss how greetings define or rather reflect the nature of the social relationship between interlocutors. Discussing greeting among the sayyid 'descendants of the prophet Mohamed' and qabili 'tribesmen' of the Highlands of Yemen, Cato (1986) shows that the two groups employ different kinds of greetings that iconically index the differences in the nature of the relationship and the social ideology between the two groups. While the former employ asymmetrical greetings to highlight the honor, piety and elevated status of the interlocutor, the greeting exchanges among the latter are symmetrical -"the balance in the giveand-take of communication being an icon of the balance and equality of social relationships" (302).

Finally, Duranti's (1992) highly insightful discussion of ceremonial greetings in formal events such as a fono 'council meeting' in Western Samoa illustrates two other important aspects about greetings. First, they are not just verbal activities but also crucially involve non-verbal aspects (e.g. eye-gaze, movement). Second, greetings perform important social functions. They initiate and index a formal interaction and function "as relatively short but complex activities whereby participants can communicate and bystanders find out information about someone's social status or expected role in a particular setting" (683).

Although greetings provide important insights into the social structure and linguistic practices of a community, there are not, to my knowledge, any studies that deal with greeting exchanges in creole communities (but see Fenigsen, Tessonneau, this volume). In this paper I investigate the linguistic structure, social distribution, meanings and functions of greeting exchanges in the Eastern Maroon (EM) community of Suriname and French Guiana (Guyane) based on data from audio-recordings, long-term observation and participation in the community and focused discussions with selected members. The data come mostly from the Pamaka community.

The investigation of the general features of these greetings is based on Duranti (1997) and the analysis of their interactional meanings draws on Goffman's (1967) theory of social face.

Goffman argues that an individual's social face is an image of a person pieced together from the expressive implications of events s/he engages in. It is the positive social value a person effectively claims for him/herself or attributes to another person by the line others assume s/he has taken during a particular contact. To maintain or defend this positive social image, interlocutors engage in face-work, i.e., actions (e.g. avoidance of face-threats) taken by a person to make what s/he or another person is doing consistent with their face.

The study is divided into six parts. Part One briefly presents the EM community. Part Two discusses some of the general aspects of greetings. Parts Three and Four investigate the structure and the social meanings of greetings, respectively. Part Five looks at greetings in the urban context and the last part summarizes the findings and discusses their implications.

The Eastern Maroon Community

The EM community consists of three autonomous groups, the Aluku or Boni, the Ndyuka or Okanisi, and the Pamaka. Their traditional villages (konde) are mostly located in the interior of the tropical rain forest of Suriname and Guyane along the Marowijne river (Pamaka) and its tributaries, the Lawa river (Aluku) and the Tapanahoni river (Ndyuka). There are also significant Ndyuka settlements along the upper and lower Marowijne River, the Cottica River, and the Sara Creek. The latter two communities are partially autonomous and are locally referred to as the Saakiiki and the Kotika, respectively. Due to migratory movements from the interior toward the coastal region and from Suriname to Guyane, the (French) lower Marowijne region, including the two Aluku villages in that area, has in the last decades become rather multiethnic in nature. It holds important settlements (kampu) from all three communities and several mixed settlements in which members from these communities and other maroon groups (e.g. Saamaka and Kotika) live together. *put Map from Huttar and Huttar here.* These migrations also brought mostly young maroons to the coastal urban centers of the region.

Initially, the capital of Suriname, Paramaribo, the border town of Albina and the areas around them were the main center of attraction. However, following the civil war in Suriname and the country's economic decline in the late 1980s and 1990s, a significant number of EMs has moved to towns in the French overseas department, and particularly to the border town of St. Laurent du Maroni, but also to Mana, Kourou and Cayenne.

The mother tongue and primary community language of the EM communities is the Eastern Maroon Creole (EMC). It is classified as a conservative English-lexified Creole. The community recognizes three major EMC varieties that coincide with the three existing EM groups (Aluku, Ndyuka, Pamaka). 1 They are direct descendants of the creole varieties that emerged on the plantations of Suriname between 1680 and 1720 (cf. Migge 2002a, 2003). The three varieties are mutually intelligible but differ slightly on the phonological and the lexical level (cf. Bilby 2002, Goury & Migge 2003). These differences largely function as ethnic markers. The community also recognizes at least three styles of speaking, lesipeki taki 'respect speech,' yunkuman or wakaman taki 'young man's or traveller's speech,' and kowounu taki 'common speech.' They are associated with different greeting practices.

Despite contacts with local and increasingly also European urban centers (e.g. Amsterdam, Paris), in the everyday life of EM villagers stratification still plays an important role in what is still a 'traditional' type of social organization. Adults are divided into three broad groups: titled persons, elders and "regular" adults. Titled persons are the members of a maroon government.

The official head of an EM community is the gaaman 'paramount chief.' The kabiten head the different (sub)lineages or villages and the male and female basia assist the kabiten and the gaaman. 2 The kabiten (and gaaman) carry out the ritual and official business of the community, represent it to the outside and are responsible for keeping it together. Male elders are essentially men above the age of 40 or 45 who lead a respectable life. They aid the titled persons in their work and critically overlook it. Some of them head the extended family groups that make up the different (sub)lineages, lead the organization and carry out minor ritual ceremonies and arbitrate minor disputes. Female elders often serve as medium for avenging spirits and/or organize and overlook the actions of the women of their sublineage or village.

"Regular" adults are women and men roughly above the age of 16. However, adulthood seems to be much more closely tied to certain "social achievements" rather than age. A woman is, for example, said to be an adult when she has children, even if she is only 15 years old. Her status increases with her age but also with the number of children she has at her charge and by the way she maintains her family and household. 3 Men are considered to be of age when they take on responsibility, i.e., when they take a wife and have children, and obtain the necessary means for being self-sufficienttraditionally, a boat and an outboard motor, a house, tools for preparing fields, building houses etc. Their social standing increases with their age, their achievements, and their relative participation in the socio-political life of the community. 4 The latter is, however, crucially dependent on the knowledge of local traditions, which are acquired gradually throughout one's life. As a result of their young age, young men are generally not considered to be very knowledgeable and therefore tend to be assigned a relatively low social status in the traditional hierarchy.

In the EM community all adults are due respect, but titled persons, elders and older "regular" adults are due special respect. When interacting with them, it is customary to apply or approximate norms of formal or respectful conduct (cf. Migge 2004).

When to greet

EM greetings (odi), like greetings in other societies, function to identify "a group of people as members of the class of individuals with whom we communicate in public or public arenas" (Duranti 1997: 71). They are obligatorily employed to initiate a focused interaction (Goffman 1967: 7) with an adult who does not belong to one's household or to acknowledge such a person; 5 the greeting of children and youngsters appears to be optional. In the village setting where people generally know each other, mere co-presence or "unfocused interaction" that do not require greetings is rare. It is, however, found in the urban context. Here, members from different communities (e.g. Amerindians, Haitians, Hmongs, Saamaka, Aluku, Ndyuka, local creoles, Europeans) who do not know each other may come to occupy the same space or pass closely by each other without greeting. With members from other communities, EMs generally employ the greetings from the dominant European language, e.g. bonjour in Guyane and daag in Suriname.

An adult who does not greet another adult they know is usually considered to lack proper manners (án sabi kiyo). When it recurs, it is taken as an indication that there is a "problem" and/or that the person lacks proper respect for the other because they treat them as if they are non-proper conversationalists and "not worth the attention implied by the use of greetings" (Duranti 1997: 71). This is an offence that disrupts the social harmony. The wronged person usually complains to the elders of the other person and less commonly to the person her-or himself in an effort to work out the problem and to receive the proper recognition they are due. 6 However, if the "wronged" person has reasons to believe that the other (younger) person does not know them, they introduce themselves by giving their name and explaining the nature of their family relationship. Greetings in the EM community "are [also] constitutive of the interactants' public recognition of each other's presence in the same perceptual field" (Duranti 1997: 68) since they occur as soon as two people come into close proximity, roughly within one or two meters of each other. They are typically the first words that interlocutors exchange when they become aware of each other. Usually, it is the person arriving at some location, e.g. house, riverside, who initiates a greeting. However, if they cannot see the person in the location, the latter may also initiate the greeting. When passing by a location in which another (adult) person is visibly located, e.g. when they can be seen sitting in the shade or heard doing things in their house, people feel obliged to greet (bali odi). The passing person typically briefly comes to meet the other person in their location, i.e., makes a detour or minimally pauses "in their tracks" during the greeting. Simply calling out a greeting in passing is interpreted as a sign of lack of respect. However, if time constraints do not allow otherwise, it is necessary to either apologize, e.g. give a reason for one's rush, or to try to pass by unseen. When both parties are in motion or meet in the public areas of the village, e.g. the paths, the riverside, the part of the village where "ritual" matters are carried out, the person who first sees the other initiates a greeting procedure and both persons minimally pause for a few moments. If there is a difference in social status between the two people, however, it is the person with lower social rank who is expected to initiate the greeting. Elders, for instance, often "pretend" not to see younger people until they are being greeted by them.

In the case that several people are gathered in the same location, such as a group of women who sit around a cassava roasting pan, or elders gathered for a meeting, the person arriving or passing by generally greets everybody collectively and receives a collective or chorus reply from them. Following a collective greeting, they may then also move to address a greeting at one of the persons present to show them special respect, e.g. in the case of high-ranking persons, or to initiate a focused interaction with that person.

Upon initiation of a greeting sequence, previous verbal interactions, e.g. discussions between several persons, cease but are usually continued once the greeting is over. If the visiting person is of higher social status than the persons present in the location and/or is not familiar with them, talk usually does not resume (quickly). Non-verbal activities (e.g. food processing, boatbuilding etc.) are often continued during greetings or resumed immediately thereafter, particularly if the persons greeting know each other well. The people greeting only enter into physical contact, e.g. embrace or shake hands, if they know each other well and had not met for a while. The person(s) being greeted also do not usually get up and/or move towards the arriving person(s) but typically remain in their space. Finally, it is considered disrespectful to directly look at a person when greeting them, particularly if they are of higher social status.

The structural properties of greetings in the EM community

In the EM community, as among the Wolof (Irvine 1974: 168), the behavior that may fill the greeting slot is clearly defined. There are two broad sets of greetings in use in the community that differ from each other on structural and socio-pragmatic grounds. This section explores their structural properties.

EM greetings constitute a separate type of exchange that consists of one or more adjacency pairs, "in which the first pair part by one party (A) invites, constraints, and creates the expectation for a particular type of reply by another party (B)" (Duranti 1997: 69). This format allows interlocutors to take part in a joint activity and thereby display "some evidence of mutual recognition and mutual understanding" (Duranti 1997: 69).

The greetings in the first set are quite formulaic in nature. They consist of one statementstatement adjacency pair followed by an acknowledgement (1). The formula uttered by the initiator of the greeting (A) has coupled with it a standard reply given by the addressee (B) that is followed by an acknowledgement also uttered by (A).

Although (A)'s and (B)'s utterances are essentially the same, they can still be distinguished from each other on the basis of peripheral features. (A)'s utterance is usually combined with a vocative phrase consisting of (B)'s official name (1a) or of their title of courtesy (1b) or function title (1c). It is either a summons (1a, e) and precedes the greeting or it functions as a form of address (1b-c) and follows the greeting. 7 Moreover, the emphatic marker oo generally (but optionally) also modifies the formula. oo is obligatory, however, if (A) greets several people at the same time (1d). B's statement is always preceded by the affirmation expressing word (i)ya 'yes,' and the assertion-marking particle yee or the politeness marker baa typically follows it. Moreover, it is also possible to alter the paralinguistic features, e.g. loudness, tempo, pitch, of (B)'s statement to convey one's feelings. The greetings in (1) are typically delivered at a relatively slow speaking speed but when (A) or (B) speaks in a very soft voice and very slowly, drawing out the vowel of the assertion marker, it is usually understood that they are suffering some discomfort. Finally, the acknowledgement is usually expressed by one of the words for 'yes' (eeya, (i)ya), or by the politeness marker (m)baa.

(1) a. A: Sa Moiboto, a booko u (baka) oo.

'Sa M., it dawned on us (again).' B: Iya, a booko u (baka) yee/baa.

' When someone returns after having been away for a long time, one of the persons in the location, (A), initiates the semantically opaque greeting in (2) as (B) is approaching.

(2) A: Wada oo! B: Fiiman baa/yee/oo '???free person!' Upon arrival, (A) and (B) hug calling out atuu at the same time. (A) then initiates the greeting in

(3). EMs argue that this greeting dates from the time of their ancestors' flight where it was used as a "password" for allowing access to the runaway's villages. Before admitting someone to their village, the runaway slaves would first try to establish the person's identity by checking their knowledge of maroon traditions such as greetings.

The second set of greetings consists of question-answer adjacency pairs. Some of these greetings, the indigenous EM ones, involve two adjacency pairs and an acknowledgment. As illustrated in (3) and (4), they are "complicated" chains (cf. Goffman 1981; Caton 1986: 297) because (B)'s first turn consists of the second pair part of the first adjacency pair initiated by (A) and a first pair part of the second exchange. Note that (3) is sometimes preceded by an embrace.

( The question parts have the linear order of a declarative sentence but a question intonation is applied. The question part of the first adjacency pair, (A 1 ), usually involves a vocative form as in the case of the greetings in (1) while the question part of the second adjacency pair, to my knowledge, never includes such a form. Both also contain a personal address form, the pronoun u. It is the first and second person plural pronoun, which is also employed in formal contexts to politely address only one person (Huttar & Huttar 1994: 462), as in (3 & 4). 9 The answer parts, (B 1 ) and (A 2 ), are syntactically identical to the question part but have a statement intonation. As in the case of the examples in (1), they are always preceded by the affirmation-expressing word (i)ya 'yes' and are also typically followed by the assertion-marking particle yee or the politeness marker baa. Like the greetings in (1-2), (3-4) are generally delivered in a relatively slow tempo.

As indicated by the brackets in (3) and (4), it is possible to emphasize a positive attitude by modifying the question and/or the answer part of the adjacency pair with the property item mooi 'nice.' The second part of the adjacency pairs, (B 1 ) and (A 2 ), can also be modified by the property item masimasi 'weak, bad' or in the case of (3) by the phrase a wan ana 'at one hand' to overtly convey some discomfort. However, in line with the preference for agreement (Sacks 1987), people normally just use the positive reply in (3) and express discomfort using paralinguistic features, if at all.

The greetings in (1-4) may also be linked to make up a ("mixed") discourse chain (cf. Goffman 1981; Caton 1986: 298). The greeting in (3) can be preceded by any of the greetings in

(1) while the greeting in (4) may only be preceded by (1a-c)see ( 5) for an illustration.

Moreover, (4), possibly preceded by (1a-c), may also be followed by (3).

(5) A 1 : Ba Aseengi, u miti oo. 'Mr. A., we meet.' B 1 : Iya, u miti yee, sisa.

'Yes, we meet, my female friend!' A 2 : (Iya.) ('Yes') Da u de?

'Then, are you well?' (lit. 'then we exist') B 2 : Iya, u de yee! 'Yes, I am well !' (lit. 'yes, we exist for sure') U seefi de?

'You are also well ?' (lit. 'we self exist') A 3 : Iya, u de baa.

'Yes, I am well. (lit. 'yes, we exist') B 3 : Iya/Eeya.

'yes'

The inquiry into each other's health (3) is usually initiated by (A) who may or may not officially acknowledge the end of the first greeting.

Finally, the "mixed" chains (5) may be even further extended by adding one or more adjacency pairs that are an inquiry into the well being of A's familymother, wife, father and/or children. They have the format in (6) and are typically heard if (A) and (B) (and their families)

had not seen each other for a long time. 10 (6) B: Fa fi i mma? (A de mooi?) 'How about your mother? (Is she well?)' or A mma fi i, a de mooi?

'Your mother, is she well?' A: A de (mooi yee).

'She is well (!)'

As in the case of the greetings (1-4), (B)'s reply is relatively standardized but other replies (e.g. a e siki 'he is (constantly) sick,' a go a pareis/holansi 'She left to go to Paris or France/Netherlands') are also possible and are often heard.

The other greetings in the second set involve a simple question-answer adjacency pair usually but are not obligatorily followed by an acknowledgment. The question part involves the question word fa 'how' and may also involve a vocative form. In contrast to the greetings in (1-4), the reply ( 8) is not a repetition of the question phrase (7). There are several possible replies available (8-9) although in actual practice (8a-b) are most frequently used in response to (7a-e).

content, they can be employed at any time of the day. (1d) acknowledges the mutual presence of the interlocutors. It used to be only employed in the period between midday and the fall of night; however, in recent years it is also increasingly used to greet people in the evening, after dusk, thus replacing (1e).

More importantly, however, "the occurrence of greetings and the ways in which they are carried out identify a particular [social] class of people" (Duranti 1997: 71) and index different kinds of social relationships between interlocutors. The greetings in (1) convey a relatively great social distance between the interlocutors and constitute the encounter being opened as formal. Second, (A) does not elicit (personal) information from (B) but just acknowledges (B)'s presence (1f) or states to (B) an obvious and uncontroversial fact that relates to both of them (1a-e), e.g. they both survived the night and that the next day is opening itself up to them (again). (B) supports (A)'s positive face and definition of the relationship when confirming (A)'s assertion and emphasizing its correctness.

In accordance with their emphasis on social distance, the greetings in (1) are used to open up encounters that require greater attention to participants' face. This includes formal events (e.g. appeals, council meetings) and interactions that involve a certain kind of social distance between the interlocutors and/or invoke positional identities, e.g. meetings between elders or between elders or titled persons and younger adults.

Young untitled persons typically address elders and titled persons using the greetings in (1)

or (3-4) to pay them respect and to stage themselves as respectful persons. Among young untitled men, these greetings are generally not used for two main reasons: first, their relationships tend to be relatively informal and solidarity-based. Moreover, from the point of view of the traditional ideology, they all have the same (low) social status. 12 Second, they consider them to be old fashioned because they are an integral part of the traditional EM way of life. Young maroons tend to aspire to a modern (urban) life-style and are eager to rid themselves of the stigma of what they consider "rural backwardness."

In everyday situations, e.g. daily greetings between neighbors or people who regularly meet each other and maintain a cordial relationship, only the three-part sequences in (1) are employed while, in more formal contexts the exchange is extended by (3) or (4), see ( 5). The extension of the greeting ritual indexes the exceptional or greater formal character of the encounter (cf.

Duranti 1997).

(A) may also further underscore their respect for (B) by selecting one of the greetings that are widely considered to be older (1a-b and possibly 1e). Younger people often direct such greetings at elders to display their knowledge of local traditions and their (temporary) alignment with the traditional system. In contrast, elders sometimes direct them at younger people to test their knowledge of local traditions.

Overall, the greetings in ( 3) and ( 4) convey somewhat less social distance between interlocutors than the greetings in (1). 13 There appear to be two reasons for this. First, (A)'s and (B)'s utterances are somewhat less formulaic. The question parts may be adverbially modified and the answer part may even overtly contradict the question part. Second, the verbal content of the adjacency pairs implies a greater degree of familiarity or a closer relationship between (A) and (B) than those in (1). In (3-4) interlocutors exchange personal information (e.g. about their state of health) and directly relate to each other using pronominal forms of address. The first or second person plural pronoun u is typically employed because it conveys greater respect, but people who know each other very well (e.g. siblings or close acquaintances) also employ the second person singular pronoun i. Employing these greetings, (A) and (B) pay respect to each other but they also convey that they maintain (at least overtly) a cordial relationship.

Like the greetings in (1), ( 3) and ( 4) are mainly used to initiate interactions between and with high-ranking persons and people who deserve special respect such as in-laws. Young untitled persons do not usually employ them among each other. While (4) can be employed every morning, (3) is usually employed after the interlocutors have not seen each other for a while or in situations involving a relatively great social distance.

According to EMs, including those who frequently use them, the greetings in (7-9) invoke very little respect. They are closely associated with young urban working class men of Afro-Surinamese descent, so-called fotonenge, who enjoy little prestige in the traditional EM ideology.

These young men are closely associated with the coastal cash-labor industry such as the building industry and the transportation industry and with hanging out on street-corners and in bars. 14 Moreover, they are said to have very little serious interest in local traditions and are closely associated with notions of positive politeness (Brown & Levinson 1989). This way of life is clearly at odds with the (traditional) EM social ideology, which strongly emphasizes social status, negative politeness, kinship relationships and a close commitment to the local community and its traditions. The world beyond the local community, particularly the public urban domain such as the street and bars, are considered to be vulgar and lacking in respect and are hence to be avoided.

The verbal content of these greetings also conveys an absence of proper respect from a traditional EM point of view. First, (A) employs a direct question, involving a question word in the case of (7a-e), to enquire about (B)'s health. In the traditional EM ideology, overt questions are considered to be an imposition. They are usually only directed at people of low social status and possibly those with whom one maintains a close relationship. Second, (A) usually does not employ status-indicating vocative forms or pronouns only the person's common name or the lowest titles of courtesy (baala) and the second person singular pronoun i are used or implied (7c-f). They invoke a solidarity-based relationship between (A) and (B). (B)'s response is typically positive but negative answers are also possible. Finally, these greetings are usually delivered in a relatively loud voice and in a much faster tempo than the greetings in (1-3).

Greetings (7-9) are generally not employed with and among elders and (elderly) titled persons. It would be taken to imply that the initiator of the greeting is disregarding the addressee's elevated social status and suggesting that (A) and (B) are social equals. 15 Even among elders and titled persons, this assumption bears a potential for conflict. Moreover, (A) would construct her/himself as impolite and ignorant.

The greetings in (7-9) are, however, commonly employed among young EM men (kiyo). The notions of positive politeness associated with them adequately symbolize the informal crew-like solidarity-based relationships that these men (claim to) maintain among each other. These notions and the greetings' close association with young urban working class men whose life-styles are closely aligned with norms and values that contrast with traditional EM ones also function to symbolize the young men's (partial) opposition to the (traditional) EM social ideology and lifestyle. They appropriate these greetings, just like other features associated with the modern or urban world (cf. Migge 2002b), to constitute a separate powerful "young EM (working) men" identity; in the traditional EM ideology young men depend on their elders for all socio-political matters even though they fill most of the financial needs of the community.

This group identity and the means to constitute it have their roots in the early migrations of EMs to the coastal region of Suriname. Starting in the 1950s, young EM men increasingly started spending part of the year in the coastal urban region, e.g. the capital Paramaribo or the border town of Albina, or in interior work camps, e.g. the construction of the Afobaka hydroelectric dam, the bauxite mining industry, to engage in cash labor work such as factory work, construction or mining jobs. As part of their acculturation to these multiethnic settings, they learned the various social practices of their urban peers who dominated these settings. This crucially involved learning Sranan Tongo, the related urban creole and main lingua franca of Suriname, and the various social practices associated with its urban varieties such as the greetings in (7-9). As in other bi-or multilingual settings, they eventually adopted linguistic features (e.g. intonational patterns, words) and interactional routines from Sranan Tongo when interacting among themselves as part of their everyday speech repertoire. These symbolized their common urban "working man" experience. 16 Later EM migrants, adopted them as part of their acculturation to the coastal EM community and thereby reinforced their social functions. Today, even young men living in the villages draw on these "urban-EM" practices to project a trendy (modo) urban identity and to convey their opposition to the EM establishment.

Greeting in the 21 st century

Since the end of the 20 th century the EM maroon communities have been undergoing significant social change. 17 The civil war in Suriname in the late 1980s and the country's economic decline in the years following it caused many maroons to migrate to the urban centers of French Guiana or to the emerging multiethnic settlements in the interior of French Guiana along the Marowijne River (Apatou, Gaan Santi/Gransanti) and the Lawa River (Maipasula/Maripasoula). These recent migratory movements differ from previous ones in several respects. First, most people leave their villages permanently and only return once in a while for a holiday or for ritual activities, e.g. burials, healings. Second, most of the recent migrants are women and their children who either follow their husband or family, or leave on their own in search of a "better life" through access to cash labor opportunities, French legal papers and schooling for their children. 18 This migration has left many interior villages depopulated,and due to changes in the daily activities of people and the overall setting in the urban context, extended family and lineage units and the traditional EM socio-political structure and its institutions are increasingly losing social significance.

In the village setting, people's daily activities are determined by social factors such as gender and age. Women are responsible for the domestic sphere and spend most of their time in the village (konde) or their horticultural camp (kampu). They take care of their own and their husband's house, the well being of their family members (children, elders) and the food production (farming) and preparation. The women from the same extended family unit or lineage typically carry out these tasks together and heavily rely on each other for most of their activities. 19 In contrast to women, (young) men are associated with heavy physical labor and the external public sphere. They build the houses, prepare fields using a slash-and-burn method, hunt, secure transportation, and engage in mostly temporary cash-labor outside of the local community to secure the financial needs of the community. They tend to frequently interact among themselves and with young men from other communities. Their relations with (male) elders tend to be somewhat strained. Finally, (male) elders and titled persons manage the sociopolitical matters of the community and spend most of their time in the local community. They head the community and its units, represent them to the outside, direct their overall development and keep them together by giving advice to their members, by arbitrating disputes and by organizing and carrying out of ritual ceremonies. As a result, they have a considerable amount of social power, enjoy a great amount of social prestige and are due special respect from the other two social groups.

On the coast, however, the traditional social and occupational differentiation is increasingly being eroded due to the changes in people's social and economic lives. While women, for instance, are usually still responsible for the domestic sphere, they typically also engage in various cash-labor activities to increase the household income. Women with no or very little formal schooling do domestic-type work, reselling and some farming while women with a formal education increasingly try to take up jobs in government offices and the educational system, the most important employers in the region. These work opportunities and/or the various social benefits that a good number of (young) maroon women nowadays receive from the French government often provide them with greater financial means than their partners or elders. This in turn is increasingly leading to an erosion of traditional status differences and dependencies between women and men/elders. As a result of their financial means, women are able to exercise greater social power over elders and their male partners. 20 Moreover, in the urban setting, where members of the same extended family often do not live in close proximity of each other, women tend to create new social networks with women from other ethnic groups and families who live nearby, and they thereby further decrease their reliance on traditional networks.

The situation is different for elders. In the urban setting, their traditional social functions and superior social standing are being slowly eroded and their life-styles are converging with those of the younger or lower status persons in the community. While at least some of the elders and titled persons are frequently called on to organize and to perform various ceremonies (e.g. burials, end of mourning periods, cleansings) and to help arbitrate disputes, a number of these and other traditional social functions are increasingly being taken over by the various institutions of the national governments (e.g. police, courts, social workers). Moreover, most elders and titled persons tend to be relatively isolated from their equals/peers, are dependent on their younger family members for their living or have to compete with them in the cash-labor market to make a living. As a result of these changes, their elevated social status is slowly being leveled. The other members of the community and most elders themselves, for the most part, no longer perceive as great a social distance between the members of the different traditional status groups. In everyday settings, younger persons therefore generally no longer feel the need to engage in a great number of special respect rituals towards elders and titled persons, and elders and titled persons, for their part, no longer feel the need to insist on such rituals. This new way of life, often referred to as bakaa libi 'European' life-style, is also spreading to the village setting, though not as rapidly partly because the living circumstances are changing at a much slower pace in that context.

Greeting practices in the community have, as a matter of course, also been affected by these changes. The most important change has taken place in the overall distribution of the different kinds of greetings. Among the urban EM population, greetings (7-9) are much more widely employed than the indigenous EM greetings (1-5). This is partly due to two things. First, there are more young and middle-aged EMs than elders living in the urban context. Second, these greetings are historically associated with the urban setting. However, in recent years greetings (7a-c) are also increasingly used by younger people to elders and sometimes also among the latter. This is somewhat surprising because, from a traditional point of view, by using these greetings, (A) suggests that they are socially equal to (B), maintain a solidarity-based relationship with (B) and construct themselves and (B) as persons with low social status. In the urban context, these overt social meanings are generally not considered to be face-threatening anymore, particularly by elders who have spent a considerable amount of time in the urban coastal centers.

In everyday interactions with young urban EMs, they commonly employ and "accept" particularly greetings (7-9) as the default greetings; these greetings convey their solidarity with young urban men and their membership in the currently prestigious young enterprising community rather than the subsistence-based rural village setting. The use of formal greetings automatically produces the expectation that the initiator of the greeting is intending to discuss official matters, e.g. local politics, making requests or appeals etc.

Although the greetings in (7-9) are generally associated with solidarity and equality among interlocutors, it is still possible to index social distinctions. Essentially, with elders (and among elders), some of their informal properties are exchanged with respect-inducing ones that are also characteristic of the indigenous greetings in (1-4). For example, the more familiarity-conveying second person singular pronoun i and the first person singular pronoun mi are replaced with the respect-conveying second person plural pronoun u. Names are combined with titles or the Dutch/Sranan Tongo-derived titles Omu 'uncle' and Tante 'aunt' are used in place of names.

Moreover, the greetings are delivered in a relatively slow tempo (10). I have also heard people adding the emphatic particle oo or the politeness marker baa to emphasize the respectful nature of the interaction. This blending effectively constructs the relative leveling of status differences.

(10) A: Papa A., fa u tan (oo)? 'Elder A., how are we doing?' B: Papa, u de (baa).

'Elder, we are well.'

The emerging mainstream character particularly of the greetings in (7a-c) and the resulting loss of their earlier 'subculture' association is also motivating young EM men to find new linguistic means for indexing their separate group identity. Among young men, the greetings in (7d-f) are currently more commonly used than (7a-c), for example. Moreover, young men also continuously invent or adopt new greetings for use among themselves to maintain and affirm their difference to both women and elders (11). These newly emerging greetings are very short sequences that either consist of one word (11) or just of a visual sign, such as thumbs up, when

The two (or three) sets of greeting routines that are in common usage in the EM community have clear social meanings and contextual associations that are partially constituted by their linguistic form. While the indigenous and highly formulaic ones (cf. 1) index a (great) social distance between interlocutors and invoke positional identities, the very "direct" urban ones (cf. 7-9) construct a great common ground between interlocutors and constitute them as social equals. The possible third set (cf. 3-4) is intermediate between these two sets. By drawing on their social meanings and contextual associations, greetings are habitually employed to negotiate social relationships and people's social image. They are being affirmed by picking a contextually appropriate greeting to open up an encounter, but they are being challenged or undermined by selecting one that does not conventionally fit the context or when omitting to greet.

In the migratory context, where "modern" or "urban" social norms and living circumstances exert pressure on the social relationships and identities of people, greeting routines are employed in different or new ways to constitute the newly emerging realities. For instance, the indigenous, formulaic greetings become restricted to a few exceptional contexts while the urban, direct greetings are adopted as the default greeting by most members of the community. Moreover, new greetings emerge, existing greeting routines are being modified, and the indigenous and "urban" greetings are combined. These new forms function to affirm existing social differences in the new context and to construct newly emerging differences, as well as symbolize people's critical distance to the traditional EM social hierarchy.

The investigation of greeting routines also provides important insights into the social structure of the community and its social and linguistic categories. In relation to the former, it reveals that the EM community is traditionally a relatively stratified society. Social group membership is based on gender, age, and social activity, achievements and knowledge of local traditions. With respect to the latter, the study suggests that the members of the community recognize two broad types of life-styles which I will call businenge libi 'maroon life' and bakaa libi 'European life,' respectively. While the businenge libi involves the use of the EMC and knowledge of and adherence to traditional EM traditions, the latter approximates Sranan Tongo practices and is associated with local urban norms and values. The businenge libi also emphasizes positional identities and social relationships that are based on social distance and mutual respect.

Bakaa libi, on the contrary, is locally perceived to stand for social norms such as informality, solidarity and directness. Moreover, the study provides further evidence of the existence of a focused formal style in the EMC (cf. Migge 2004).

Notes

* This paper has benefited from comments by George Huttar and Susanne Mühleisen. All remaining errors are, of course, my own responsibility.

1 Saakiiki, Kotika and the Ndyuka spoken on the lower Marowijne differ somewhat from the Ndyuka varieties spoken on the Tapanahoni but still share the main distinctive features with that variety.

2 Until recently, only men could hold a kabiten position. However, due to pressure from the government of Suriname, the Pamaka and Ndyuka recently also created separate women kabiten positions.

3 There is also a right of passage ceremony for women, gi pangi 'give wrap-around-skirt.' Girls take part in it when they are about 15 years old. The ceremony for boys, gi kamisa 'give a kind of loincloth,' is quite rare nowadays. 4 Note that the notions of 'to be old' and 'to be honorable/knowledgeable' are both expressed by the same word, gaandi.

5 Pamakas usually say that people who siibi a wan osu ná e gi odi 'people who sleep in the same house do not greet each other.' 6 Complaints about improper greeting behavior are quite frequent and tend to be indicative of more serious interpersonal problems. 7 There are three female (sa, tia/tante, mma) and male (ba, tii/omu, dda/ppa) titles of courtesy and several function titles (e.g. gaaman 'paramount chief,' kabiten '(sub)lineage head'). While sa is used with women of low social status, mma is employed with women of great social importance, and tia/tante is the title for women of intermediate rank (cf. Migge 2001). Note that participants' relative age and the nature of their relationship also play a role in the assignment of titles. For instance, a man who is in his thirties will address a man who is in his forties and with whom he is not very familiar using the title Omu/Tii or even Ppa/Dda if he wants to pay special respect.

easily result in their members' complete integration into local mainstream culture and thus a complete loss of these societies' current distinctive properties (cf. Price & Price 2003). 18 Most children, particularly older ones, in traditional villages do not have easy access to schools, and boarding opportunities are rare and expensive in both Guyane and Suriname. Note also that a great number of maroon children have a right to French citizenship because they are mostly born in the hospital of St. Laurent. Finally, French resident cards or citizenship do not only allow an easier access to the world but they also mean access to all kinds of social money which is a great help in an economically quite depressed region. 19 Not just blood relations but also in-laws tend to collaborate for all kinds of daily activities. The strength of either of these networks depends on residence patterns. 20 Among EMs living in St. Laurent, there is currently much talk about how women are dominating their male partners because of their financial means. 21 In recent years more and more elders have been "obliged" to move to the coast mainly because most or all of their children now reside on the coast.

(

  A) and (B) only establish a minimal common ground, pay each other respect and construct each other as respectable persons in two ways. First, they do not directly and personally address each other. (A) only employs a vocative form to get (B)'s attention and to identify them as the recipient of the greeting. The only permissible vocative forms are the formal forms of address that invoke (B)'s official or positional social identity. (B) does not use personal address forms.

It is also possible to say Iya, u doo en (mooi) yee baa mama/papa.

It is not really clear whether the polite usage of u is related to/derived from its first or second person plural usage. In (1c) it seems best to argue that u includes the speaker and the addressee. This inclusion possibly functions as a further device of indirectness to effect politeness (G.Huttar, p.c., August 2004). However, in examples (3-4) it does not appear to include the speaker but just the addressee and possibly by implication also her/his family. See alsoMühleisen (this volume) for a discussion of this issue.

It may also be employed if (B) does not know (A)'s family.

They are the descendants of slaves who remained on the plantations.

For young men it is generally much more difficult to gain social rank than for young women because for them social rank is tied to traditional knowledge (see above). They therefore tend to be much more opposed to the traditional system than young women. Moreover, as a result of their engagement in the cash labor industry, they are much more closely aligned with urban norms and values than young women.

An informant pointed out that (1c) conveys less respect than (4). This appears to be mainly due to the fact that (4) is considered to be older.

Earning money in itself is not a problem; however, when this becomes the only thing that someone is interested in, it is considered problematic because it tends to lead to jealousy and community problems.

I once observed a situation in which a young man used (7c) to greet a youngster who was arriving in a boat with several other people. One of the elders in the boat thought that he was being addressed and immediately protested this status-inappropriate greeting: Baala, piimisi, mi anga i, u ná biya. 'Brother, we are not persons of the same age group.'

Women still today make much more careful use of Sranan Tongo features because they carry (negative) associations that are much more difficult to sustain for women (cf. Migge 2002b?).

As has been made abundantly clear in[START_REF] Price | Maroon Arts: Cultural Vitality in the African Diaspora[END_REF] book on maroon art, the maroon societies of Suriname, just like any community, have never been static societies but have always been subject to change. However, it seems as if the current social changes are on a different scale compared with previous ones. They may

(B)'s response is usually positive (8) but indifference (9a-b) or discomfort (9c-d) may also be conveyed. These exchanges are usually not part of a discourse chain but see ( 12) for an exception.

(7a) A: (name/sisa/baala), fa i tan? 'Sister/brother, how are you?' (7b) A: (name), fa i du?

'How are you doing?' (7c) A: (name), fa a e go?

'How is it going?' (7d) A: (name), on fa? 'How?' ('What's up') (7e) A: (name While the greetings in (1-4) are considered to be proper native Eastern Maroon or Pamaka greetings, the greetings in (7-9) are said to belong to the coastal, non-maroon Afro-Surinamese population of Suriname, the so-called fotonenge lit. 'fort or Paramaribo people,' who generally speak Sranan Tongo, the related urban creole, as their mother tongue. 11 EMs, however, practice sociolinguistic erasure and associate these greetings most closely with young working class men of Afro-Surinamese descent. Today, with the emergence of Sranan Tongo as the main lingua franca in Suriname and parts of Guyane, these greetings are also used in interethnic and sometimes also intra-ethnic encounters by members of other local ethnic groups such as Surinamese-Chinese, Surinamese-Indonesian, Surinamese-Amerindian etc.

The social meaning and distribution of greetings in the EM community

On the most general level, the referential content of some of the EM greetings establishes specific temporal units (Duranti 1997: 70). They refer to activities (e.g. rise of sun/dawning, awaking, fall of night) that take place at specific times of the day and come to index these periods of the day.

Other greetings, e.g. ( 1f), ( 3), (7-9), do not refer to a specific time period. (1f) only acknowledges presence while (3) and (7-9) are an inquiry into health. Because of their "timeless" passing each other. They underscore this group's desire to distance themselves from what are often felt to be "time-consuming" and outdated politeness practices.

(11) A: Cool/orgi? 'Is everything cool/okay?' B: Cool/orgi! 'Everything is cool/okay!'

In the urban context, the greetings in (1-5) are generally considered very ritualistic and oldfashioned because they invoke traditional social hierarchies, positional social identities and identify the person using them as someone who is intimately associated with the traditional EM life-style. They have therefore come to be largely reserved for events and situations in which these matters are central to the interaction. They are obligatorily used among people gathering for formal events, e.g. kuutu 'council meeting' events and all kinds of ritual ceremonies, and by persons who want to initiate official business, e.g. make a formal appeal. They are also employed on a regular basis with and among elders and titled persons who are closely aligned with the upriver community, e.g. people who live there and/or who command a great amount of social power in the community, and among in-laws, e.g. son in-law to mother in-law and among sisters in-law. 21 It would still today be difficult to address these groups of people using anything other that the greetings in (1-4). However, persons of higher social status have the opportunity to change the footing of the interaction to a more informal one by addressing their interlocutors using one of the greetings in (7-9). Such informal greetings (12c) typically follow more formal ones (12a-b) initiated by the younger/lower status person (12).

(12) (a) A: U miti oo, gaaman. 'We meet, paramount chief!' (good afternoon) B: Ya, u miti yee, sisa.

'Yes, we meet, (madam)!' (b) Da u de?

'Are we well?' A: Ya u de yee! 'Yes, we are well!' U seefi de?

'How about yourself?' B: Ya, u de baa.

'Yes, we are well.' A: Iya.

'Yes' (c) B: Beti, on fa? 'What's up Beti?' A: Saaflio.

'(I am) okay.'

Conclusion


Thi-Minh Nguyen
email: thi-minh.nguyen@lip6.fr

Serge Fdida
email: serge.fdida@upmc.fr

Tuan-Minh Pham

A Comprehensive Resource Management and Placement for Network Function Virtualization

Keywords: NFV, Network Function Virtualization, resource allocation, optimization and migration

Network service providers have to cope with the growing on-demand need from end-users as well as the diversity of usage. The softwerization and cloudification of the network components offer an interesting solution to achieve the agility necessary to dynamically match the requirement with the level of resource consumption. This materializes with the deployment of Network Functions Virtualization (NFV) where Virtual Network Functions (VNFs) may be chained together to create network services. This paper explores important design and architectural issues related to this approach. We study the resource allocation problem in an NFV system for minimizing its cost under constraints on interconnectivity among VNFs, system resources, and service requirements. We formalize the problem in a comprehensive manner taking into account a broad set of relevant parameters. The static (offline) and dynamic (online) cases are considered. We propose and analyze three heuristic algorithms: two for handling large dimensions of the offline problem and one designed to address the online scenario.

The evaluation shows that our solutions outperform the state of the art [1] with respect to critical performance index. Finally, we focus on the online scenario, evaluate the impact of migrating a set of running demands, and propose a simple migration technique.

I. INTRODUCTION

Softwerization of network components is a candidate to provide the agility requested by the increasing on-demand need of customers as well as the ability to gently match those needs with the resource consumption. This trend is achieved by using a cloud approach where virtualization techniques are intensively exploited. Although this trend is prevalent, it is still necessary to better understand the right level of abstraction and hence performance that will be made possible with this approach. NFV relying upon virtualization techniques should support network operators to meet the growing customer requirements while controlling capital and operational expenditures.

In order to enable such an agile solution, a network service can be decomposed into an ordered sequence of VNFs (Virtual Network Functions), which can run on several standard physical nodes. Therefore, the resources allocated to a VNF instance will impact the capacity and performance of the network service as a whole. This raises important issues related to NFV deployment such as: 1) How and where to locate and chain VNFs? 2) How to distribute resources to VNFs? and 3) What is the cost of NFV deployment in a network? Such problems are different from the VM placement optimization in cloud computing as VNFs are associated with a single network service. In this paper, we consider a joint problem of VNFs allocation upon service requests from users and routing paths for chaining them. We develop a comprehensive solution addressing the static and dynamic scenario, when taking into account the execution order of VNFs in a service demand with regard to resource constraints for nodes and links.

The major contributions of this paper are as follows:

• We formulate the optimization problem of VNF placement as a quadratic program (QP) solving multiple objectives including optimal service location and optimal routing among VNF instances of a network service, under both resource and traffic cost constraints, simultaneously optimizing the acceptance ratio of new demands. Both the static and dynamic problems are considered. • We propose three efficient heuristics for large dimensions of the problem within an acceptable computation time. • We evaluate our proposed solutions in various scenarios and compare it against the ProvisionTraffic (PT) algorithm [START_REF] Bari | On orchestrating virtual network functions[END_REF] that illustrates the state of the art, as well as a Random Algorithm. • We provide a cost comparison between a network relying on NFV and a network that does not use NFV and discuss some architectural implications. • We also propose a simple migration technique for the dynamic problem. The result provides guidelines for the percentage of traffic to be migrated in order to achieve the best gain. The rest of this paper is organized as follows. Section II reviews the related work. In Section III, we model the NFV system under study and formalize the NFV placement problem. We present our solutions in Section IV. In Section V, we validate the algorithms and discuss the results. Section VI concludes the paper.

II. RELATED WORK

Managing complexity is the major challenge faced by ISPs who need to focus on network efficiency, performance, cost, and resource utilization. These issues relate directly to the resource sharing and scheduling problem. In recent years, this concern has received a lot of attention from the community and has also evolved with the emergence of the NFV concept [START_REF] Etsi | White paper on network functions virtualization[END_REF]. In this section, we will discuss some of the most important research works related to the network function placement and chaining problem. We start the section by reviewing recent efforts aimed at evaluating the technical feasibility of deploying network functions on virtual networks in both static and dynamic environments. Then we highlight open issues and emphasize the competitive contributions of our work.

The NFV placement problem is related to both the virtual network embedding (VNE) [START_REF] Fischer | Virtual network embedding: A survey[END_REF] and the virtual data center embedding (VDCE) [START_REF] Md | On tackling virtual data center embedding problem[END_REF]. The survey [START_REF] Li | A survey of network function placement[END_REF], [START_REF] Herrera | Resource allocation in nfv: A comprehensive survey[END_REF] provides a valuable reference for previous works related to the VNF placement problem. In [START_REF] Herrera | Resource allocation in nfv: A comprehensive survey[END_REF], Herrera and Botero present a comprehensive state of the art of NFV resource allocation (NFV-RA) problem. In their novel classification, the main approaches for solving NFV-RA are described as three stages: a, VNFs -Chain Composition (VNF-CC); b, VNF -Forwarding Graph Embedding (VNF-FGE) and c, VNFs -Scheduling (VNF-SCH). In this paper, we focus on the second stage.

Recently, Rasid Mijumbi et al. proposed an online mapping and scheduling problem in an Network Function Virtual Infrastructure (NFVI) [START_REF] Mijumbi | Design and evaluation of algorithms for mapping and scheduling of virtual network functions[END_REF]. However, they did not consider links between virtual nodes while the traffic cost among virtual nodes plays an important role in distributing resources to the required services.

For the NFV location problem, Rami Cohen et al. [START_REF] Cohen | Near optimal placement of virtual network functions[END_REF] presented a near optimal approximation algorithm guaranteeing a placement with theoretically proven performance. However, they did not consider the chaining of VNFs in requested services. The same concern is observed in other papers [START_REF] Bari | On orchestrating virtual network functions[END_REF], [START_REF] Luizelli | Piecing together the nfv provisioning puzzle: Efficient placement and chaining of virtual network functions[END_REF], [START_REF] Addis | Virtual network functions placement and routing optimization[END_REF] where the authors have considered a constraint on link capacity, but ignored the order of functions in a SFC request.

More recently, in 2016, Kuo et. al. [START_REF]Deploying chains of virtual network functions: On the relation between link and server usage[END_REF] studied the joint problem of VNF placement and path selection to better utilize the network. They considered the link bandwidth required by each demand, provided feasible solutions to support all the demands with the purpose to maximize the number of accepted demands. However, they ignored the issue of serving all the arriving demands with the minimum cost.

The publications mentioned above provide a static allocation strategy that pre-computes the resource allocation for each session. There are some disadvantages to this approach such as the resource utilization or the supplied capacity when handling fluctuating demands. Therefore, it is important to dynamically adjust the demand based on the current status. In [START_REF] Ihara | Many-objective virtual machine placement for dynamic environments[END_REF], [START_REF] Pires | Multi-objective virtual machine placement with service level agreement: A memetic algorithm approach[END_REF], authors proposed a multi-objective formulation of the Virtual Machine Placement considering Service Level Agreement.

In [START_REF] Lukovszki | Online admission control and embedding of service chains[END_REF], Lukovszki et al. formulated the offline (SCEP: Service Chain Embedding Problem) and online problem (OSCEP: Online SCEP). They assumed that all potential paths that can be routed through VNFs chaining for each demand are known. In addition they did not consider the resources price when deploying the network functions. PACE [START_REF] Li | PACE: policy-aware application cloud embedding[END_REF] addressed the VNF placement for unordered service chains in cloud, with the objective to satisfy as many tenant's requests as possible. However, in their model, they have to decide about the placement of middleboxes before receiving the request. In other words, the placement of middleboxes are fixed. Also, Elias et al. [START_REF] Elias | Efficient orchestration mechanisms for congestion mitigation in nfv: Models and algorithms[END_REF] formulated the centralized version of VNF-FGE as a non-linear integer optimization model and assume that the placement of functions is fixed. Recently, Sun et. al. investigated the offline and online solutions for the VNF placement problem with the aim of minimizing the deployment cost [START_REF] Sun | Forecast-assisted NFV service chain deployment based on afliation-aware vnf placement[END_REF]. They took into account the chaining of VNFs, but they only considered a pre-defined set of service chaining.

In contrast, our work explicitly considers the execution order of VNFs in each requested service, integrating resource constraints for nodes and links. We solve VNFs allocation and routing in a coordinated way, that is VNFs in each customer demand are placed and routed simultaneously. Our model consists of both the OFFLINE and ONLINE case. We compare our solution with the PT algorithm to prove its efficiency for the resource cost. We also provide an evaluation of the cost efficiency of NFV deployment by comparing the overhead of an NFV system with the one of a non-NFV system. Furthermore, we propose a simple migration technique for the ONLINE case.

III. PRELIMINARIES

We first describe a resource allocation problem in a system implementing NFV. Then, we formulate the problem as a quadratic program (QP) dealing with both optimal service location and optimal routing under constraints on service function chaining and system resources.

A. System Description

In this section, we introduce two scenarios: the static problem (OFFLINE case) and the dynamic problem (ONLINE case).

1) OFFLINE case: We study a NFV system where a network function is offered as a service. The system is composed of three components, including a set of VNFs, a set of customer demands and a virtual network that provides resources to the VNFs. VNF is a software implementation of a Network Function (NF) deployed on an NFVI. Each demand requests access to a network service (NS) that requires special functionalities. It can be composed of several VNFs in order to support advanced network connectivity, e.g. deep packet inspection, firewall, load balancer. In a NS, VNFs will need diverse resources such as CPU, memory, storage, bandwidth, etc. It is recognized that virtualized solutions are quite costly in resource consumption. Resources are distributed anywhere on the NFVI. A customer demand materializes as a packet flow from a source to a destination visiting a set of nodes where the required VNFs are deployed.

How to efficiently share resources for all demands with delay constraints or limited capacity is an important challenge for NFV providers. It is likely that the solution achieved will trade-off agility with efficiency. For instance, a NFV solution Minimum and maximum number of demands may take a longer path than the likely shortest path followed by a non-NFV system. However, it is still applicable if the delay lies within an acceptable range.

A virtual network is represented as an edge-weighted undirected graph denoted by G = (V, E, w) where V is a set of virtual nodes, E is a set of links, and w is the bandwidth capacity assigned to each link. Each node v ∈ V is associated with two components: 1) c r v that denotes a set of resource capacities with r ∈ R, where R denotes the set of resources (CPU, STORAGE, and MEMORY, etc.) and 2)

p v (λ d ) that is the price of resource charged per hour ($/hour) according to a Service Level Agreement (SLA) coefficient λ d of the customer d. We denote D n as a set of l customer demands. A demand d ∈ D n is represented by a set of parameters (s d , t d , b d , F d , ∆ d ) where s d is a source, t d is a destination, b d is a required bandwidth, F d = {f i1 , ..., f i k } is
an ordered chaining of sub-set VNFs and ∆ d is an average total processing time of demand d. We assume that each VNF f i ∈ F d only appears once in each demand d ∈ D n . We define F = {f i |i = {1, ..., m}} as a set of m VNFs. Each function f i ∈ F has a vector µ r fi representing its resource requirement (r ∈ R). In the OFFLINE model, we minimize both the computing-resource cost and the bandwidth cost under constraints on resource and bandwidth capacity with respect to VNFs chaining.

2) ONLINE case: We consider a scenario where an operational network is serving a set of customer demands D o (called old demands) . At this stage, a set of VNFs are already deployed and the routing paths for the demands in D o are also provisioned. Consider new demands D n are incoming and the network operator needs to provision the required VNFs and routing paths for them. Maximizing the number of served demands and minimizing the system resource cost are the research challenges addressed in the sequel.

We consider an interval τ (according to the system configuration) where we will update the status of all demands running in the system. Upon completion, the system releases the resources allocated to a demand. At time t, we collect new demands D n that arrived during the period (t -τ ) to t.

We propose a method to select the subset of old demands to be migrated in Section-IV-B2.

The ONLINE model addresses the multiple objectives:

• Minimize resource cost on nodes to satisfy the demands • Minimize bandwidth cost on links from source to destination passing through VNFs • Maximize the number of accepted demands • Minimize the penalty cost for VNF migration

B. Formal Problem Statement

We aggregate both cases and formulate the above system as a quadratic problem with the following inputs: We aim to:

• Set of m functions F = {f i |i = {1, ..., m}}. -µ r f : a resource requirement of function f ∈ F • Set of old demands D o = {(s d , t d , b d , F d , ∆ d ,
1) Minimize nodes resource cost allocated for demands

U n (t) = ∆ d -t + a d s d∈Dm∪Dn z d x d f v p v (λ d ) + ∆ d -t + a d s d∈Do\Dm xd f v p v (λ d ) (1)
2) Minimize bandwidth cost on links from source to destination passing through VNFs

U l (t) = ∆ d -t + a d s d∈Dm∪Dn p b z d u,v∈V b d y d uv + ∆ d -t + a d s d∈Do\Dm p b u,v∈V b d ŷd uv (2)
3) Maximize the number of accepted demands

U accept = d∈Dn z d (3)
4) Minimize the penalty cost of VNF migration

U penalty = d∈Dm;u,v∈V ;f ∈F x d f u xd f v z d M (.) (4)
M (.) is a function of dist uv , where dist uv characterizes the length of the shortest path from u to v. It indicates the cost to migrate a function from node u to node v. In our simulation, we use two different cost functions to consider the migration penalty: a linear function and a square root function, discussed later in Section-V-C.

Constraints:

In order to guarantee that a node capacity is not oversubscribed by the allocation of VNFs to this node, we have:

d∈{Dm∪Dn} z d x d f v µ r v + d∈Do xd f v µ r v ≤ c r v ∀v ∈ V (5)
Similarly for the bandwidth capacity of a link.

d∈{Dm∪Dn} z d y d uv b d + d∈Do ŷd uv b d ≤ w uv ∀u, v ∈ V (6)
Constraint [START_REF] Mijumbi | Design and evaluation of algorithms for mapping and scheduling of virtual network functions[END_REF] guarantees that each VNF in a demand has to be processed in a given preference order.

x d f1u x d f2v -χ d uv ≤ 0 φ d f1 < φ d f2 (7)
Each VNF only appears exactly once in a demand. This constraint is expressed as follows:

v∈V x d f v = z d if f ∈ F d 0 otherwise (8)
Constraint [START_REF] Luizelli | Piecing together the nfv provisioning puzzle: Efficient placement and chaining of virtual network functions[END_REF] ensures that the variables y d uv are nonsymmetric.

y d uv + y d vu ≤ 1 ∀u, v ∈ V, d ∈ D m ∪ D n (9)
Equations [START_REF] Addis | Virtual network functions placement and routing optimization[END_REF] enforce that, for each computer path associated to a demand, it always begins at its source and terminates at its destination.

v∈V

y d uv - v∈V y d vu =        z d if u = s d -z d if u = t d 0 otherwise (10)
In addition, we need constraints [START_REF]Deploying chains of virtual network functions: On the relation between link and server usage[END_REF], ( 12) and ( 13) to guarantee the compatibility between variables as follows:

χ d uv - i∈V,i =v χ d ui y d iv ≥ 0 ∀d ∈ D m ∪ D n (11) x d f v i∈V y d iv = x d f v ∀d ∈ D m ∪ D n , v ∈ V \ {s d , t d } (12) (χ d uv -1)y d uv = 0 ∀d ∈ D m ∪ D n (13)
Now, for the OFFLINE case, we simply set D o = ∅.

Unfortunately, the joint problem of NFV placement and routing is harder than the integral multicommodity flow problem whose decision version is NP-complete. Indeed, our problem becomes the integral multicommodity flow problem when we consider each demand and assume that we know the location of required functions. Hence, we study heuristic that provides a solution close to the optimal with a reduced computation time. In the next section we introduce our practical solution to address this challenge.

IV. PROPOSED ALGORITHM

As our problem is NP-hard, we only apply exact algorithms to small size dimension of our system that runs within an acceptable time. So, we use the GUROBI Optimizer [18] to solve the quadratic model in order to obtain the optimal solution. In addition, we designed three heuristic algorithms to cope with large size dimensions ((Max-Min and Min-Min for the OFFLINE case, RBP for the ONLINE case). In Section-V, we compare these algorithms with the one produced by a Random Algorithm (OFFLINE case) and the PT algorithm (ONLINE case). Hence, we discuss a migration technique aiming at efficiently managing resources and balancing flows in a dynamic environment.

The three heuristics are introduced below.

A. OFFLINE case

Our heuristics (Max-Min and Min-Min algorithm) are composed of two phases: the node mapping phase and the link mapping phase. In the first phase, we rank nodes in the virtual network to order nodes able to host a VNF for a customer demand. The link mapping phase uses the result of the node mapping phase to find a path with minimum cost for each customer demand.

1) The node mapping phase: We introduce a polynomialtime heuristic finding an allocation of VNFs available on the virtual network to match customer demands. The main idea is to assign a virtual node, based on its rank in the virtual network, to a VNF. We propose two algorithms, namely the Max-Min algorithm and the Min-Min algorithm. The Max-Min algorithm allocates a "costly" function (i.e., a function whose resource requirement is large) to a cheap node that is a node whose rank is low. The Min-Min algorithm allocates a "cheap" function (i.e., a function whose resource requirement is small) to a cheap node.

We use the equation ( 14) of the rank for node v to find the cheapest or the best virtual node. This value is always updated after deploying a VNF on a virtual node. It accounts for the available resource capacity, the price for each resource unit and the ability to connect to other nodes. It also considers the benefit obtained by the situation where a given function is already hosted on one node and could be mutualized with another demand. We propose a formula for ranking the nodes based on the components as below:

rank v = α    p v i∈V p i + 1 f ∈F C(f, v) + 1    + β    i,j∈V w ij -y i∈V w iv -x v + d∈Dn T (s d , v) + d∈Dn T (t d , v) d∈D,i∈V T (s d , i) + d∈Dn,i∈V T (t d , i)    (14)
where α, β ∈ [0, 1] (α + β = 1) characterize the influence of the resource cost on nodes and the communication cost on links, respectively. In particular, these two parameters will determine the priority of our system according to the price of resources associated with nodes and communications in order to reach source and destination of customer demands. We will estimate thoroughly the impact of these parameters in Section-V. x v , y are the amount of bandwidth decreased for node v and other nodes after a function is selected to be hosted on node v. T (u, v) is the minimum distance between two nodes u, v ∈ V . C(f, v) specifies the number of occurrences of function f ∈ F in all demands that were assigned to node v ∈ V . x v = 0 ∀v, y = 0

3: while F = ∅ do 4:
f max ← arg max f ∈F {µ r f }

5:

while P (f max ) > 0 do 6:

v min ← arg min v∈V and v satisfies (5) {rank v } 7:

g(f max ) ← g(f max ) ∪ v min 8: max bw = max {d ∈ D n |f max ∈ F d } 9:
xo vmin ← x vmin + max bw 10:

y ← y + max bw 11:

P (f max ) ← P (f max ) -1 12:
Update rank v , c r vmin 13:

end while 14:

Remove f max 15:

end while 16:

Compute U n (t) using equation (1). 17:

return g.

18: end function

The Pseudo-code of the Max-Min algorithm is provided in Algorithm 1. The Max-Min algorithm first selects a function f ∈ F whose resource requirement is the highest, denoted by f max . It then finds a virtual node with the minimum rank in the virtual network, denoted by v min . Virtual node v min is selected to host function f max for a customer demand. The available resource capacity of virtual node v min is updated. Finally, the function f max is removed from F when f max required in all customer demands is satisfied. We repeat the process until all functions are allocated.

The Min-Min algorithm is similar to the Max-Min algorithm where, f max in the Max-Min algorithm is replaced by f min that is a function whose resource requirement is the lowest.

2) The link mapping phase: The second phase of the heuristic is to find a path from a source to a destination with the minimum cost for each demand. Its Pseudo-code is presented in Algorithm 2. Specifically, using the result of phase 1, for each f ∈ F , we have a set of virtual nodes g(f ) that can support function f . We denote the ith function of the customer demand d by F d (i). For each customer demand, the algorithm first finds the shortest path between the source and a node providing F d (0). Then, for adjacent functions (F d (i), F d (i + 1)), it finds the shortest path from a set of nodes g(F d (i)) to a set of nodes g(F d (i+1)). Finally, it finds the shortest path between the destination of the demand and a node that can provide the last function in the demand (i.e., a node in g(F d ( d -1)) where d is the number of functions for demand d).

Algorithm 2 Path Selection

F d (i): the i th VNF in demand d, i = 0.. d -1 5: F d (-1) ← s d , F d (l d ) ← t d 6:
for a pair F d (i), F d (i + 1),i = -1.. d -1 do 7:

U 1 ← g(F d (i)), U 2 ← g(F d (i + 1)) 8: p i ← shortest path(u 1 ∈ U 1 , u 2 ∈ U 2 ), satisfying (6) 9:
g(F d (i + 1)) = u 2 10:

p ← p ∪ p i 11:
end for

12:

Add p to p sol 13:

end for 14:

Compute U l (t) using equation (2). In contrast to the OFFLINE case, the RBP algorithm finds the routing path prior to locating VNFs on virtual nodes. RBP will consider each demand sequentially and decide whether and how to serve it. For each demand d, we find in graph G, a shortest path p from s d to t d . Then we allocate one by one VNF in F d on the path p, satisfying all resource constraints (5)→ [START_REF] Pires | Multi-objective virtual machine placement with service level agreement: A memetic algorithm approach[END_REF]. If this path does not satisfy all resource constraints, we try another shortest path p from s d to t d , and so on. If no such path exists, the demand d is rejected. The Pseudo-code of the RBP algorithm is provided in Algorithm 3.

2) Migration Technique: Another concern in the dynamic NFV problem is to decide if and how a set of old demands should be migrated. Selecting old demands to migrate will impact the current resources of our system as well as affect the system cost. Our goal is to move a flow of old demands including nodes and links to a new position to optimize the system resources. As mentioned earlier, there exist a penalty cost associated to the migration tasks [START_REF] Md | On tackling virtual data center embedding problem[END_REF]. In this section, we propose a simple method to select a set of old demands to be migrated. The main idea of the method is to identify old demands that have the largest wasted bandwidth cost for passing through nodes that do not provide resources for any required VNFs. It results in the computation of the wasted bandwidth cost of each old demand, as follows:

Γ d = f1 * f2=0;v1,v2∈V xd f1v1 xd f2v2 ŷd v1v2 w v1v2 (15)
Then we select η % number of old demands D o depending on the wasted resource as in [START_REF] Li | PACE: policy-aware application cloud embedding[END_REF], called D m and re-configure this set of demands. We release all resources provisioned in D m and find the solution for D m using Algorithm 3. Finally, we continue this algorithm until the set of all new demands D n has been processed.

V. EVALUATION

In this section, we evaluate the performance of our solutions according to a large set of parameters.

A. Parameter Setting

We defined the following scenario in order to evaluate the performance of our algorithms:

• Network Topology: In this paper, we use two types of topologies: random networks (R1, R2, R3, R4) and data center networks (B1, B2, F 1, F 2) as defined in Table II. We focused on two types of data center topologies, namely, Fat-Tree [START_REF] Al-Fares | A scalable, commodity data center network architecture[END_REF] and BCube [START_REF] Guo | Bcube: a high performance, server-centric network architecture for modular data centers[END_REF]. For Fat-Tree networks, we generated two topologies (F 1, F 2) with parameters k = 4 and k = 6, where k represents the number of ports in a switch. For BCube networks, we generated two topologies (B1, B2) with parameters n = 2, k = 2 and n = 4, k = 2, where n represents the number of ports in a switch and k stands for the number of hierarchy of switches.

Algorithm 3 Routing before Placement(RBP) Algorithm

1: function RBP(F, D m , D o , D n , G(V, E , w)) 2:
AcceptN o = 0;

3:

for demand d ∈ {D m ∪ D n } do 4:
{v subsol , f subsol , v sol , f sol } ← {∅, ∅, ∅, ∅}

while true do

7: p ← Shortest path(G, s d , t d ) 8: for f ∈ F d , v ∈ p do 9:
Locate f to v 10:

if satisfy constraints (5) then 11:

v subsol ← v subsol ∪ v 12:
f subsol ← f subsol ∪ f end for 25: end function • Customer demands: We evaluated each network topology, called a scenario, using eight different tests, varying the number of demands l in a test from min l in the first test to max l in the last one. Each customer demand including the source node, the destination node, a chain of VNFs, the resource requirement and the cost factor of SLA, is generated randomly for each individual test. • The price of resources (i.e. CPU, storage, memory) are collected from the Microsoft [21] and Amazon websites [22]. For example, the price of a virtual machine with 4 CPUs, 285GB storage and 7GB memory on the Microsoft cloud is 0.36 $/hour. We have simulated our proposed algorithms in Java.

• In the OFFLINE case, we evaluate the performance (the NFV cost) of our heuristics (Max-Min and Min-Min) with the optimal solution, and a Random algorithm (to be described later). • In the ONLINE case, we evaluate the performance (the average routing path length and the acceptance ratio) of our heuristic (RBP algorithm) against the PT algorithm. We also compare the gain obtained when applying our migration strategy as a function of the percentage of old demands considered for migration.

B. OFFLINE case

We first assess the influence of the parameters α, β in equation [START_REF] Lukovszki | Online admission control and embedding of service chains[END_REF]. We consider different values of α, β in [0, 1] and then compare the NFV cost produced by our two heuristics. Fig. NFV System Non-NFV System Fig. 3: (OFFLINE) Ratio between the bandwidth cost of a non-NFV system and that of a NFV system shows the influence of the NFV cost on data center networks when selecting different value of parameters (α, β). The NFV cost is computed by adding the resource cost U n (t) as defined in equation (1) to the bandwidth cost U l (t) as in equation [START_REF] Etsi | White paper on network functions virtualization[END_REF]. We observe that the best values for both algorithms (Max-Min, Min-Min) depend on the network topology. For instance, the best values for a BCube topology are α < β, whereas for a Fat Tree topology they are α > β. When α < β, the priority of nodes will mainly depend on the communication cost on links whilst if α > β, the priority of nodes will mostly depend on the resource cost on nodes. In fact, a BCube topology has more links connecting switches and servers than a Fat Tree topology. Therefore, in order to select a node that can host VNFs in a BCube topology, it is more important to consider the communication cost. In the reminder of the paper, we use (α = 0.6, β = 0.4) with Fat Tree topologies, and (α = 0.4, β = 0.6) with BCube topologies for the two heuristics.

Then, we use the GUROBI Optimizer [18] to find the optimal solution for small instances where (m = 4, l = 1), namely scenario 1 and introduce a simple Random algorithm to evaluate the efficiency of our solutions for larger dimensions. The Random algorithm is defined below. We first generate randomly locations for hosting all VNFs supporting all demands and satisfying constraints [START_REF] Li | A survey of network function placement[END_REF]. We then find a path satisfying constraints [START_REF] Herrera | Resource allocation in nfv: A comprehensive survey[END_REF] for each demand. Each path will be composed of nodes hosting the required VNFs in a given order. The obtained result constitutes a Random solution to our problem. Fig. 2 shows the NFV cost obtained by Max-Min, Min-Min, Random algorithms and the optimal solution (GUROBI ) for a small size system. All tests (x-axis) in the small size scenario consider the same demand for different network topologies that are generated randomly with the number of vertices equals to 7. It is obvious that the solutions produced by the heuristic algorithms (Max-Min and Min-Min) are far better than the one provided by the Random algorithm and close to the optimal solution. For larger scenarios (R2, R3, R4, B1, B2, F 1, F 2) in Table II (i.e. hundreds of virtual nodes, hundreds of demands), we run our heuristic algorithms and Random algorithm where the customer demand is generated randomly. Regarding the NFV cost (Fig. 4) on data center topologies (B1 and F 1), our heuristics (green line and red line) performs obviously better than Random algorithm (blue line) and become more effective when the number of demands grows. In addition, Min-Min algorithm (green line) is better than Max-Min algorithm (red line). As expected, allocating a "cheap" function (i.e. a function whose resource requirement is small) to a cheap node provides a more efficient resource management. We now consider a non-NFV system where a source node is able to host the all set of required functions. We simply use Dijkstra algorithm to find a shortest path for all pairs of demand from source to destination. We then sum the costs for all links on all the shortest paths to obtain a bandwidth cost. We use this solution to compare it against our NFV-based one and assess the overhead due to virtualizing the network functions. In Fig. 3, we compare the bandwidth required to transfer packets from a source to a destination in a NFV system and that in a non-NFV system. We use the bandwidth cost computed by equation [START_REF] Etsi | White paper on network functions virtualization[END_REF]. The result shows that a trade-off has to be found between efficiency and the agility provided by the virtualization of functions. It means that, in our scenario, an operator need to spend 60% more resources to be able to benefit from the agility and dynamicity of NFV. This confirms the importance for instrumenting an efficient deployment of service chaining.

We now want to evaluate the distribution of VNFs on a multi-tier network topology as illustrated in Fig. 5. We define three node categories: core nodes, aggregation nodes and access nodes. An access node is connected to an aggregation node, itself connected to core nodes, and core nodes are fully meshed. We assume that all nodes are NFVI nodes that can host VNFs. We compute the solution for the two heuristics and the PT algorithm in order to compare the distribution of VNFs among those algorithms. Fig. 6 shows that for the Max-Min and Min-Min algorithms, VNFs are almost similarly distributed on aggregation nodes (95%), a small part on core nodes (4%), and rarely (1%) on access nodes, while the PT algorithm distributes more equally VNFs to three node types including core nodes (21%), access nodes (17%), and aggregation nodes (62%). Finally and as expected, the Random algorithm distributes fairly VNFs to the three node types. It clearly suggests that the network functions should be located on the network edge rather than the network core. The best option will be to deploy all VNFs in every edge node but the cost might be excessive hence the importance to identify which VNFs can be mutualized and/or deployed only on some specific edge nodes whilst preserving performance constraints.

C. ONLINE case

We now evaluate our solution suited to the ONLINE case. We acknowledge the fact that there exist an abundant literature related to the NFV placement such as [START_REF] Cohen | Near optimal placement of virtual network functions[END_REF], [START_REF] Luizelli | Piecing together the nfv provisioning puzzle: Efficient placement and chaining of virtual network functions[END_REF], [START_REF]Deploying chains of virtual network functions: On the relation between link and server usage[END_REF]. However, we claim that our (RBT) model is comprehensive and it is therefore difficult to compare it against the existing ones. For instance, as mentioned earlier in Section II, the model in [START_REF] Luizelli | Piecing together the nfv provisioning puzzle: Efficient placement and chaining of virtual network functions[END_REF] does not consider the request or the customer demand as a flow from a source to a destination. Moreover, they evaluated their approaches with at most two chained network functions for each SFC request. Therefore, we decided to select the PT algorithm [START_REF] Bari | On orchestrating virtual network functions[END_REF] as a comparison as we found that this is the one that share the largest set of characteristics with ours. Fig. 7 and Fig. 8 show the acceptance ratio and the average routing path length obtained by our heuristic (RBP) compared to the PT one. It shows that our solution achieve higher acceptance ratio and shorter routing paths than PT. Fig. 9 showing the NFV cost as defined by ( 1) and ( 2) provide evidence of the efficiency of our solution when no migration exists. The idea of RBP is to implement routing before placing the VNFs. This guarantees that demands always use good paths. Indeed, in Fig 3 ,8, and 9, the solution obtained by RBP (red line) is obviously better than the one produced by the PT algorithm (green line). However, it has to pay the price for increasing the running time when trying all possible paths for each demand.

In addition, we also compare the acceptance ratio between RBP and PT applied on some data center network topologies (B1, B2, F 1, F 2). Fig. 11 shows the acceptance ratio as a function of the number of arriving demands, from 2 to 100. Fig. 11(a) depicts the results with a network of 32 servers (respectively BCube B1, FatTree F 1) and Fig. 11(b) shows the results with a network of 128 servers (respectively BCube B2, FatTree F 2). We observe that our heuristic performs better on a Bcube topology than on Fat-Tree topology. Indeed, a BCube topology provides much more links between server nodes and switch nodes than the Fat-Tree topology.

Finally, we evaluate the impact of migrating a set of old demands. We address the NFV cost using various migration percentages η from 0% (no migration) to 100% (all demands are migrated). As mentioned earlier, we select old demands eligible for migration according to the wasted bandwidth, defined in equation ( 15), of these demands. We also consider as a parameter, two cases for the migration penalty cost function M (.) in equation ( 4): one linear function and one square root function.

Fig. 10 provides a comparison of the NFV cost, as a function of the migration percentage, obtained by the RBP and PT algorithms. The NFV cost is computed as the sum of the resource cost U n (l) defined by equation (1), the bandwidth cost U l (t) equation ( 2) and the migration penalty cost U P enalty (4). We observe that RBP will benefit from migrating demands whilst it is not the case for PT. The best cost is obtained for RBP with 40% migration of old demands when using a linear penalty cost. This cost will always decrease as a function of the percentage of flows being migrated for a square root function penalty cost. In summary, the migration will bring a certain benefit when we select a proper migration percentage (as 40% in our experiment with a linear penalty cost). However, if we

Algorithm 1

 1 Max-Min Resource Heuristic 1: function MAX-MIN(P (f )) P (f )= number of occurrences of f in all demands 2:

1 :

 1 function PATHSELECTION(g : F → V ) 2:{p, p sol } ← {∅, ∅} 3: for demand d ∈ D n do 4:

1 )

 1 Routing before Placement (RBP) algorithm: We now present an algorithm solving the ONLINE case.

1

 1

Fig. 1 :

 1 Fig. 1: (OFFLINE) The NFV cost with different parameters (α, β) on a data center network

Fig. 2 :

 2 Fig. 2: (OFFLINE) The NFV cost of small scale scenarios

Fig. 4 :

 4 Fig. 4: (OFFLINE) The NFV cost of large scale scenarios

Fig. 5 :Fig. 6 :Fig. 7 :Fig. 8 :

 5678 Fig. 5: Multi-tier network topology

Fig. 9 :Fig. 10 :

 910 Fig. 9: (ONLINE) Comparison between the NFV cost of RBP and that of PT when no migrating

TABLE I :

 I Summary of Variables

	Variable	Meaning
	(n,m,l)	Number of virtual nodes, VNFs, and demands
	(V ,E)	Set of virtual nodes and links
	(Dn,Do)	Set of new demands and old demands
	Dm ⊆ Do	Set of old demands that will be migrated
	F	Set of VNFs
	R	Set of resources (CPU, STORAGE, MEMORY, etc.)
	F d	Set of ordered VNFs of demand d
	d	The number of VNFs in set F d
	φ d f	The order of function f in the chain of VNFs F d
	wv 1 v 2 c r v	Bandwidth capacity of link between v 1 , v 2 ∈ V Resource capacity r ∈ R of node v ∈ V
	λ d	SLA coefficient of demand d
	pv(λ d )	The price of resource charged per hour of node v, according to λ d
	µ r f	Required resource r ∈ R of function f ∈ F
	(s d ,t d )	Source node and destination node of demand d
	b d	Required bandwidth of demand d
	(a d s ,∆ d )	Starting and total processing time of demand d
	p b	Price of bandwidth charged per hour
	η	Migration percentage
	x d f v

A binary variable that equals to

[START_REF] Bari | On orchestrating virtual network functions[END_REF]

if and only if virtual node v hosts function f of demand d y d uv A binary variable that equals to 1 if and only if link (u, v) is used by demand d χ d uv A binary variable that equals to 1 if and only if node u is a ancestor node of v in the routing path of d z d An integer variable that equals to 1 if new demand d is served, -1 if old demand d is migrated and 0 otherwise xd f v A binary variable that equals to 1 if and only if virtual node v hosts function f of old demand d ŷd uv A binary variable that equals to 1 if and only if link (u, v) is used by old demand d (min l ,max l )

  We define the outputs of our problem as a set of decision variables. x d f v is a binary variable that equals to 1 if and only if node v hosts function f of demand d. Similarly, the binary variables y d uv equals to 1 if and only if demand d uses link (u, v). The binary variables χ d uv equals to 1 if and only if node u is an ancestor node of v in the routing path of demand d. Finally, z d is an binary variable that equals to 1 if a new demand d is served or an old demand d is migrated, and equals to 0 otherwise.

a d s , xd vf , ŷd uv )}. Each old demand d ∈ D o , we know a d s is the starting process time, xd vf and ŷd uv indicate their solution deployed on NFVI. • D m ⊆ D o is the set of old demands selected to be migrated. A migration percentage is denoted by η = |Dm| |Do| • Set of new demands D n = {(s d , t d , b d , F d , ∆ d )} • An edge-weighted undirected graph G = (V, E, w) is representing the virtual network.

The notations can be found in Table

I

.

TABLE II :

 II Scenarios

	Scenario	Number of virtual nodes n	Number of VNFs m	Number of new demands size (Dn) min l → max l	Number of old demands size (Do)
	R1	7	4	1 → 1	1
	R2	15	5	3 → 20	5
	R3	50	15	10 → 100	20
	R4	200	20	50 → 600	30
	B1	n=2,k=2	10	2 → 100	10
	B2	n=4,k=2	10	2 → 100	10
	F1	k=4	10	2 → 100	10
	F2	k=6	10	2 → 100	10

ACKNOWLEDGMENT

We are grateful to the anonymous reviewers for their constructive criticism. Tuan-Minh Pham was partially supported by project B2016-SPH-17 from the Vietnam Ministry of Education and Training.

only pay a smaller penalty cost for migrating (as square root function), we obtain more benefit when updating the system resource after an interval τ . It means we have to consider both the penalty cost to move a function to a new position and the distribution of system resources at present, when determining if and how a set of old demands should be migrated.

VI. CONCLUSION AND FUTURE WORK

In this paper, we addressed the resource allocation problem for NFV where a network service is composed of several VNF instances. Our model is generic, able to handle a large and diverse set of key parameters and can easily be customized. It takes into account the interconnectivity among VNFs, service requirements, and NFV costs (including both resource cost and traffic cost). We formulated the problem as a quadratic program for both optimal VNF location and optimal routing. We proposed two heuristic algorithms, called Max-Min and Min-Min, for the OFFLINE case and one heuristic, called RBP for the ONLINE. Our extensive evaluation shows that our heuristic algorithms always perform significantly better than the one produced by the PT solution in [START_REF] Bari | On orchestrating virtual network functions[END_REF] considering various performance metrics such as the NFV cost and the acceptance ratio of arriving demands. In addition, we computed the cost uncured by a network relying on NFV to capture the overhead introduced by a solution based on the virtualization of functions. To complete our study, we investigated a simple migration technique that can efficiently manage the dynamic situation produced by a continuous flow of arriving demands. Our future plan is to exploit the value of this model in practical scenarios where measurement will be made available to parametrize our solution. In addition, we started to study the congestion issue that can arise in such an environment.