extfieldsofstudy:
Sociology
Computer Science

text:
Language Independent Sentence-Level Subjectivity Analysis with Feature Selection

Identifying and extracting subjective information from News, Blogs and other user generated content has lot of applications. Most of the earlier work concentrated on English data. But, recently subjectivity related research at sentence-level in other languages has increased. In this paper, we achieve sentence-level subjectivity classification using language independent feature weighing and selection methods which are consistent across languages. Experiments performed on 5 different languages including English and South Asian language Hindi show that Entropy based category coverage difference criterion (ECCD) feature selection method with language independent feature weighing methods outperforms other approaches for subjective classification.

Introduction
Subjective text expresses opinions, emotions, sentiment and beliefs, while objective text generally report facts. So the task of distinguishing subjective from objective text is useful for many natural language processing applications like mining opinions from product reviews (M. Hu and B. Liu, 2004), summarizing different opinions(K. Ganesan.et.al, 2010), question answering (A. Balahur.et.al, 2009) etc.
But research work performed earlier on subjectivity analysis has been applied only on English and mostly at document-level and word-level. Some methods (Wiebe and Riloff, 2005) which concentrated at sentence-level to learn subjective and ob-jective expressions are boot-strapping algorithms which lacks scalability. But, recently focus shifted to multilingual space (R. Mihalcea.et.al, 2007). Banea (C. Banea.et.al, 2008) worked on sentencelevel subjectivity analysis using machine translation approaches by leveraging resources and tools available for English . Another approach (C. Banea.et.al, 2010) used multilingual space and meta classifiers to build high precision classifiers for subjectivity classification.
However, aforementioned work (C. Banea.et.al, 2008) concentrated more on language specific attributes due to variation in expression of subjectivity in different languages. This create a problem of portability of methods to different languages. Other approach (C. Banea.et.al, 2010) which tried achieving language independence created large feature vectors for subjectivity classification. Different languages parallel sentences are taken into consideration to build high-precision classifier for each language. This approach not only increases the complexity and time for classification but also completely dependent on parallel corpus to get good accuracies. A weakly supervised method (C. Lin.et.al, 2011) for sentence-level subjectivity detection using subjLDA tried to reduce training data is available only for English. There are some experiments conducted for Japanese (H. Kanayama.et.al, 2006), Chinese (T. Zagibalov.et.al, 2008), Romanian (C. Banea.et.al, 2008;R. Mihalcea.et.al, 2007) languages data. But these approaches are performed at document level and not language independent.
In this paper, we try to address three major problems highlighted from earlier approaches. First, can language portability problem be eliminated by selecting language independent features. Second, can language specific tools like POS taggers, Named Entity recognizers dependency can be minimized as they vary with language. Third, can accuracy of subjective classification is maintained after feature reduction using feature selection methods which are consistent across languages.
Remainder of this paper is organized into following sections. Related work is mentioned in the Section 2. Next Section 3 discuss about our approach for feature weighing and selection methods. While the experimental setup Section 4 describes collection and evaluation metrics used to analyze the accuracy of approach. Experimental Section 5 explains experiments performed on different languages, while results and performance between SVM and NBM is analyzed in Section 6 and Section 7 respectively. Conclusion and future work is discussed in Section 8.

Related Work
We divide the subjective and objective classification task into unsupervised, multilingual and supervised methods.

Unsupervised
Sentiment classification and opinion analysis can be considered as a hierarchical task of subjectivity detection. Improvement of precision in subjectivity detection can benefit the later. Therefore, lot of work is done for subjective sentence detection to achieve later. (G. Murray.et.al, 2009) proposed to learn subjective expression patterns from both labeled and unlabeled data using n-gram word sequences. Their approach for learning subjective expression patterns is similar to (T. Wilson.et.al, 2008) which relies on n-grams, but goes beyond fixed sequences of words by varying levels of lexical instantiation.

Multilingual
In the multilingual space good amount of work is done in Asian and European languages. Several participants in the Chinese and Japanese Opinion Extraction tasks of NTCIR-6 (Y. Wu.et.al, 2007) performed subjectivity and sentiment analysis in languages other than English. (C. Banea.et.al, 2008;R. Mihalcea.et.al, 2007) performed subjectivity analysis in Romanian. While, (C. Banea.et.al, 2010) performed subjectivity analysis in French, Spanish, Arabic, German, Romanian languages.

Supervised
Furthermore, tools developed for English were used to determine sentiment or subjectivity labeling for a given target language by transferring the text to English and applying an English classifier on the resulting data. The labels were then transfered back into the target language (M. Bautin.et.al, 2008). These experiments are carried out in Arabic, Chinese, English, French, German, Italian, Japanese, Korean, Spanish, and Romanian. (X. Wan, 2009) who constructs a polarity co-training system by using the multi-lingual views obtained through the automatic translation of product-reviews into Chinese and English.

Approach
Subjective sentence classification is treated as a text classification task. (C. Banea.et.al, 2008) used unigrams at word level as features to classify the subjective and objective sentences in different languages. But, unigrams can occur in different categories (subjective and objective) with equal probability. This hampers the classification accuracy. Also, selecting all possible words in the sentences can create a large index size when considered as entire training set increasing the dimensionality of the feature vector for each sentence.
Feature selection can be applied to efficiently categorize the sentences. It is an important process which is followed for many text categorization tasks. Now to achieve our major objective of language independent subjective classification. We use feature extraction, weighing and selection methods that are language independent.

Feature Extraction and Weighing
Features are categorized into syntactic, semantic, link-based, and stylistic features (G. Forman, 2003) from the previous subjective and sentiment studies.
Here, we concentrate more on feature weighing methods based on syntactic and stylistic properties of the text to maintain language independence. Unigrams and Bigrams extracted as features are 172 weighed as given below.

Syntactic Feature Weighing
Syntactic features used in earlier works (M. Gamon, 2004) where word n-grams and part-of-speech (POS) tags. But, POS tagging create dependency on language specific tools. In order to eliminate the language specific dependencies we will use only word n-grams.

Sentence Representation with Unigram (UF.ISF)
This feature extraction is inspired from vector space model (G. Salton, 1975) used for flat documents. UF represents the unigram frequency at word level in a sentence. While ISF represent the inverse sentence frequency of the unigram. For a given collection S of subjective and objective sentences, an Index I = {u 1 , u 2 , ...., u |I| }, where |I| denotes the cardinal of I, gives the list of unigrams u encountered in the sentences S.
A sentence s i of S is then represented by a vector s → i = (w i,1 , w i,2 , ..., w i,I ) followed by the subjective or objective label. Here, w i,j represents the weight of unigram u j in the sentence s i . Now to calculate the weight w i,j we use the formula similar to TF.IDF.
where c i,j is the number of occurrences of u j in the sentence s i normalized by the number of occurrences of other unigrams in sentence s i , |S| is total number of sentences in the training set and |{s i : u j εs i }| is number of sentences in which the unigram u j occurs at-least once.

Sentence Representation with Bigram (BF.ISF)
This feature extraction is similar to UF.ISF mentioned in the earlier section, but we extract co-occurring words. BF represents the Bigrams frequency at word level in a sentence. While ISF represent the inverse sentence frequency of the Bigram. For a given collection S of subjective and objective sentences, an Bigram Index BI = {b 1 , b 2 , ...., b |BI| }, where |BI| denotes the cardinal of BI, gives the list of bigrams b encountered in the sentences S. A sentence s i of S is then represented by a vector s → i = (wb i,1 , wb i,2 , ..., wb i,BI ) followed by the subjective or objective label. Here, wb i,j represents the weight of bigram b j in the sentence s i . Now to calculate the weight wb i,j we use the formula similar to UF.ISF.
where c i,j is the number of occurrences of b j in the sentence s i normalized by the number of occurrences of other bigrams in sentence s i , |S| is total number of sentences in the training set and |{s i : b j εs i }| is number of sentences in which the bigram b j occurs at least once.

Stylistic Feature Weighing
Structural and lexical style markers can be considered as stylistic features which has shown good results in Web discourse (A. Abbasi.et.al, 2008). However, style markers have seen limited usage in sentiment analysis research. Some (M. Gamon, 2004) tried in this direction.

Sentence representation with Normalized Unigram Word Length (NUWL)
This feature extraction considers length of unique unigram words in the sentence. Length of unigram is calculated by the number of characters present in the word. For a given collection S of subjective and objective sentences, an Word Index W I = {uw 1 , uw 2 , ...., uw |W I| }, where |W I| denotes the cardinal of W I, gives the list of unigram words uw encountered in the sentences S. A sentence s i of S is then represented by a vector s → i = (lw i,1 , lw i,2 , ..., lw i,I ) followed by the subjective or objective label. Here, lw i,j represents the weight of unigram word uw j in the sentence s i . Now to calculate the weight lw i,j .
where L i,j is the character count in the uw j in the sentence s i normalized by length of all the unigram words in sentence s i . |S| is total number of sentences in the training set and |{s i : uw j εs i }| is number of sentences in which the unigram uw j occurs atleast once.

Feature Selection
Feature selection methods help in removing the features which may not be useful for categorization. To achieve it, feature selection techniques select subset of total features. But, it is important to reduce features without compromising on the accuracy of a classifier. Most methods like Information Gain(IG) (C. Lee.et.al, 2006), Correlation Feature Selection(CFS) (M.A. Hall, 1999), Chi-Squared (χ 2 ) (J. Bakus.et.al, 2006), Odds ratio (OR) (G. Forman, 2003) does not consider the frequency of the text or term between the categories which leads in reduction of accuracy of a classifier.
In-order to overcome this problem, we used Entropy based category coverage difference (ECCD) (C. Largeron.et.al, 2011) feature selection method which uses the entropy of the text or term. f j is used to represent the text feature extracted (unigram or bigram), c k for category of the class and c − k for the complement of the class. Where j represent number of features and k represents two classes either subjective or objective.
Entropy based category coverage Difference(ECCD) This feature selection method (C. Largeron.et.al, 2011) was proposed to mine INEX XML documents. We use this approach for improving the subjective and objective sentence classification. Let T k j be number of occurrences of text feature f j in the category c k sentence and, f q k j is the frequency of f j in that category c k given by Equation 4.
So Entropy Ent(f j ) of text feature f j is given by Equation 5 Ent Entropy equals 0, if the text feature f j appears only in one category. It means that feature has good discrimination ability to classify the sentences. Similarly, entropy of the text feature will be high if the feature is represented in two classes. If Ent m represent the maximum entropy of the feature f j , ECCD(f j , c k ) is given by following equation 6.
Where P (f j |c k ) and P (f j |c − k ) are probability of observing the text feature f j in a sentence belonging to category c k and c − k respectively. The advantage of ECCD is that higher the number of sentences of category c k containing feature f j and lower the number of sentences in other category containing f j , we get higher value for equation 6. It means f j becomes the characteristic feature of that category c k which helps in better feature selection. Feature selection method which is similar to ECCD is mentioned below.
Categorical Proportional Difference (CPD) CPD (M. Simeon.et.al, 2008) is a measure of the degree to which a text feature contributes to differentiating a particular category from other categories in a text corpus. We calculate the CPD for a text feature f j by taking a ratio that considers the number of sentences in subjective category c k in which the text feature occurs and the number of sentences in objective category c − k in which the text f j also occurs. Equation 7 shows the details. Certain threshold of CPD score is kept to reduce the number of features.

Contingency Table Representation of features
Feature selection methods mentioned in earlier section is estimated using a contingency table. Let A, be the number of sentences in the subjective category containing feature f j . B, be the number of sentences in the objective category containing f j . C, be the number of sentences of subjective category which do not contain feature f j given by f − j and D, be the number of sentences in objective category c − k which do not contain f j . Let (M = A + B + C + D) be the total possibilities.  Table   FS Representation  Table   4 Experimental Setup In-order to achieve subjective and objective classification at sentence level for different languages. We performed our experiments using different datasets.

Datasets
Translated MPQA corpus provided in (C. Banea.et.al, 2010) containing subjective and objective sentences 1 of French, Arabic, and Romanian languages were used for experiments. For English, MPQA corpus 2 containing subjective and objective sentences used for translation of above mentioned corpus is used. Hindi experiments were performed using sentences from the news corpus (A. Mogadala.et.al, 2012) tagged with positive, negative and objective sentences. Positive and negative sentences are further clubbed into subjective sentences to do subjectivity analysis.

Evaluation
To evaluate various feature selection methods, we use F-measure scores which combines precision and recall. Precision (P s ) measures the percentage of sentences correctly assigned to subjective category, and recall (R s ) measures the percentage of sentences that should have been assigned to subjective category but actually assigned to subjective category. Using P s and R s subjective F-measure F s is calculated. Similarly, Objective F-measure F o is cal-culated using P o and R o . After F-measure is determined for both subjective and objective class, the macro-average F-measure F macro−avg is determined by the following Equation 8.

Experiments
Initially, 1500 subjective and 1500 objective sentences of English, Romanian, French and Arabic languages are used to perform the experiments. While for Hindi, entire corpus constituting 786 subjective and 519 objective sentences was used. Different feature weighing and selection methods are evaluated with 2 different classifiers to obtain best combination for each language. Table 8 to Table 12 show the Macro-Average (F macro−avg ) scores obtained after 10 cross-validation using sequential minimal optimization algorithm (J. Platt, 1998) for training a support vector machine(SVM) using polynomial kernel and Naive Bayes Multinomial(NBM) classifiers. Feature space obtained after application of feature selection methods for each language are mentioned in Tables 3, 4, 5, 6, 7. Once the best combination is obtained for each language. It is compared with multilingual space classifier proposed in (C. Banea.et.al, 2010) 3 along with the baseline constituting simple Naive Bayes classifier with unigram features. Multilingual space constitutes words as features from all languages used for experiments except Hindi.
Scalability of feature selection methods is an issue. In-order to understand the performance of ECCD feature selection method with classifiers. In every iteration 500 sentences are added to each class of initial 1500 subjective and objective sentences limiting to maximum of 3500 to get average scores. Table 13 show the comparison of average scores obtained for each language. Figures 1, 2, 3, 4 show precision and recall for subjective sentences obtained using different methods for English, Romanian, French and Arabic respectively using different number of sentences.

Result Analysis
It is observed from the Table 8 to Table 12 that ECCD feature selection and BF.ISF feature weigh-ing method with NBM classifier performs consistently across languages. This behavior is observed due to capability of ECCD in efficiently discrimi-       nating the features belonging to a particular class. Although, UF.ISF and NUWL with ECCD and CPD using SVM classifier has more scores than BF.ISF, it is not significantly contrasting with the results of NBM classifier. So, NBM classifier with ECCD feature selection and BF.ISF feature weighing method which obtained high F macro−avg scores is selected for comparison with other approaches in Table 13. The proposed method not only outperforms on F macro−avg compared to other approaches but also on P macro−avg and R macro−avg in all languages. For English, proposed methods gains 23.8% over baseline in F macro−avg and 8.0% on P macro−avg on (Wiebe and Riloff, 2005). Similarly, from Table 13 it can be deducted that proposed method for Romanian attains 26.1% more F macro−avg than baseline and 155.4% more compared to Multilingual space classifier (C. Banea.et.al, 2010). Similar observations can be made for other languages. Even though (C. Banea.et.al, 2010) attains high recall for every language. It fails to attain high precision due to presence of large number of frivolous word features which are common for both classes. This being major drawback, ECCD feature selection method eliminates features which attains zero entropy. This reduces the randomness of features and leave only those features which are more eligible for discriminating the classes. Combining ECCD with BF.ISF, a language independent weighing method for Bi-gram features extracted from the sentences. We are able to attain a best classification accuracies which are consistent across languages. Figures 1, 2, 3, 4 also show that increase in number of sentences does not effect the precision of the proposed method, as it still outperforms other methods. But, scalability problem persists for ECCD with BF.ISF for larger datasets, as it may not eliminate less random features due to noise and other constraints. Also, feature selection methods ensure the performance of classifiers is maintained by reducing number of features. But, it does not ensure reduction in fixed percentage of features. As observed our best performing feature selection method ECCD reduces feature size by 10% only.

Performance Analysis between SVM and NBM
From the Table 8 to 12 it is observed that SVM with some feature selection and weighing methods performs equivalent to the NBM. However, as the number of documents increases the performance of SVM may degrade. It can be derived that, as the training data size increases, it is rare to see SVM performing better than NBM.

Training Time behavior
SVM is in a clear disadvantage compared to NBM when processing time is considered. The training time of the SVM is particularly high, especially for larger feature spaces. It is probably attributed to the time taken in finding the proper separating hyperplane.

Features behavior
Large feature spaces do not necessarily lead to best performance. So feature selection methods are used to create small feature spaces to build SVM and NBM classifiers. Sometimes, small feature space sizes make SVM perform equivalent to NBM as observed in Table 12. Thus, this would explain why SVM is outperformed for small training set sizes and for small feature spaces with large training sets.

Conclusion and Future Work
In this paper, subjective classification is achieved using combination of feature selection and weighing methods which are consistent across languages. We found that our proposed method which combines ECCD feature selection and BF.ISF feature weighing method used along with NBM classifier perform across languages. It not only outperforms other feature selection methods but also achieve better scores compared to other approaches. In future, we want to apply this approach on bigger datasets and also extend it to multiple class problems.


extfieldsofstudy:
Computer Science
Mathematics

text:
Capacity and Security of Heterogeneous Distributed Storage Systems

We study the capacity of heterogeneous distributed storage systems under repair dynamics. Examples of these systems include peer-to-peer storage clouds, wireless, and Internet caching systems. Nodes in a heterogeneous system can have different storage capacities and different repair bandwidths. We give lower and upper bounds on the system capacity. These bounds depend on either the average resources per node, or on a detailed knowledge of the node characteristics. Moreover, we study the case in which nodes may be compromised by an eavesdropper, and give bounds on the system secrecy capacity. One implication of our results is that symmetric repair maximizes the capacity of a homogeneous system, which justifies the model widely used in the literature.

I. INTRODUCTION
Cloud storage has emerged in recent years as an inexpensive and scalable solution for storing large amounts of data and making it pervasively available to users. The growing success of cloud storage has been accompanied by new advances in the theory of such systems, namely the application of network coding techniques for distributed data storage and the theory of regenerating codes introduced by Dimakis et al. [1], followed by a large body of further work in the literature.
Cloud storage systems are typically built using a large number of inexpensive commodity disks that fail frequently, making failures "the norm rather then the exception" [2]. Therefore, it is a prime concern to achieve fault-tolerance in these systems and minimize the probability of losing the stored data. The recent theoretical results uncovered fundamental tradeoffs among system resources (storage capacity, repair bandwidth, etc.) that are necessary to achieve faulttolerance. They also provided novel code constructions for data redundancy schemes that can achieve these tradeoffs in certain cases; see for example [3], [4] and [5].
The majority of the results in the literature of this field focus on a homogeneous model when studying the information theoretic limits on the performance of distributed storage systems. In a homogeneous system all the nodes (hard disks or other storage devices) have the same parameters (storage capacity, repair bandwidth, etc.). This model encompasses many real-world storage systems such as clusters in a data center, and has been instrumental in forming the engineering intuition for understanding these systems. Recent development have included the emergence of heterogeneous systems that pool together nodes from different sources and with different characteristics to form one big reliable cloud storage system. Examples include peer-to-peer (p2p), or hybrid (p2p-assisted) cloud storage systems [6], [7], Internet caching systems for video-on-demand applications [8], [9], and caching systems in heterogeneous wireless networks [10]. Motivated by these applications, we study the capacity of heterogeneous distributed storage systems (DSS) here under reliability and secrecy constraints.
Contributions: The capacity of a DSS is defined as the maximum amount of information that can be delivered to any user contacting k out of n nodes in the system. Intuitively, in a heterogeneous system, this capacity should be limited by the "weakest" nodes. However, nodes can have different storage capacities and different repair bandwidths. And the tension between these two set of parameters makes it challenging to identify which nodes are the "weakest".
Our first result establishes an upper bound on the capacity of a DSS that depends on the average resources in the system (average storage capacity and average repair bandwidth per node). We use this bound to prove that symmetric repair, i.e., downloading equal amount of data from each helper node, maximizes the capacity of a homogeneous DSS. While the optimality of symmetric repair is known for the special case of MDS codes [11], our results assert that symmetric repair is always optimal for any choice of system parameters. Further, our proof avoids the combinatorial cut-based arguments typically used this context.
In addition, we give an expression for the capacity when we know the characteristics of all the nodes in the system (not just the averages). This expression may be hard to compute, but we use it to derive additional bounds that are easy to evaluate. Our techniques generalize to the scenario in which the system is compromised by an eavesdropper 1 . We give bounds on the secrecy capacity when the system is supposed to leak no information to the eavesdropper (perfect secrecy). Here too, we show that symmetric repair maximizes the secrecy capacity of a homogeneous system. Related work: Wu proved the optimality of symmetric repair in [11] for the special case of a DSS using Maximum Distance Separable (MDS) codes. Coding schemes for a nonhomogeneous storage system with one super-node that is more reliable and has more storage capacity were studied in [12]. References [13] and [14] studied the problem of storage allocations in distributed systems under a total storage budget constraint. Pawar et al. [15], [16] studied the secure capacity of distributed storage systems under eavesdropping and malicious attacks.
Organization: Our paper is organized as follows. In Section II, we describe our model for heterogeneous DSS and set up the notation. In Section III, we summarize our main results. In Section IV, we prove our bounds on the capacity of a heterogeneous DSS. In Section V, we study the secrecy capacity in the presence of an eavesdropper. We conclude in Section VI and discuss some open problems. We postpone some of the proofs to the Appendix, where we also discuss the generalizability of our results from functional to exact repair.

II. MODEL
A heterogeneous distributed storage system is formed of n storage nodes v 1 , . . . , v n with storage capacities α 1 , . . . , α n respectively. Unless stated otherwise, we assume that the nodes are indexed in increasing order of capacity, i.e., α 1 ≤ α 2 ≤ · · · ≤ α n . In a homogeneous system all nodes have the same storage capacity α, i.e., α i = α, ∀i. As a reliability requirement, a user should be able to obtain a file by contacting any k < n nodes in the DSS. The nodes forming the system are unreliable and can fail. The system is repaired from a failure by replacing the failed node with a new node. Upon joining the system, the new node downloads its data from d, k ≤ d ≤ n − 1, helper nodes in the system.
The repair process can be either exact or functional. In the case of exact repair, the new node is required to store an exact copy of the data that was stored on the failed node. Whereas in the case of functional repair, the data stored on the new node does not have to be an exact copy of the lost data, but merely "functionally equivalent" in the sense that it preserves the property that contacting any k out of n nodes is sufficient to reconstruct a stored file. We focus on functional repair in this paper, although some of our results do generalize to the exact repair model (see the discussion in Appendix A).
An important system parameter is the repair bandwidth which refers to the total amount of data downloaded by the new node. In a homogeneous system, the repair bandwidth, denoted by γ, is the same for any new node joining the system. The typical model adopted in the literature assumes symmetric repair in which the total repair bandwidth γ is divided equally among the d helpers. Thus, the new node downloads β = γ/d amount of information from each helper. In a heterogeneous system the repair bandwidth can vary depending on which node has failed and which nodes are helping in the repair process. We denote by β ijS the amount of information that a new node replacing the failed node v j is downloading from helper node v i when the other helper node belong to the index set S (i ∈ S, |S| = d). An important special case is when the repair bandwidth per helper depends only on the identity of the helper node and not on the identity of the failed node or the other helpers. In this case, we say that helper node v i has repair bandwidth β i , i.e., β ijS = β i , ∀j, S. In the case of a homogeneous system with symmetric repair, we have We focus on repair from single node failures 2 . In this case, there are n−1 d possibilities for the set of helpers S. Therefore, the average repair bandwidth γ j of node v j is We denote by γ = 1 n n j=1 γ j and α = 1 n n j=1 α j the average total repair bandwidth and average node capacity in the DSS, respectively.
We are interested in finding the capacity C of a heterogeneous system. The capacity C represents the maximum amount of information that can be downloaded by any user contacting k out of the n nodes in the system. Recall from [1], that the capacity C ho of a homogeneous system implementing symmetric repair is given by We are also interested in characterizing the secrecy capacity of the system when some nodes are compromised by an eavesdropper. We follow the model in [15] and [16] and denote by , ≤ k, the number of compromised nodes. The eavesdropper is assumed to be passive. She can read the data downloaded during repair and stored on a compromised node. We are interested here in information theoretic secrecy which characterizes the fundamental ability of the system to provide data confidentiality independently of cryptographic methods. The secrecy capacity of the system, denoted by C s , is defined as the maximum amount of information that can be delivered to a user without revealing any information to the eavesdropper (perfect secrecy). We denote by C ho s the secrecy capacity of a homogeneous system with symmetric repair. Finding C ho s is still an open problem in general. The following upper bound was shown to hold in [15] and [16]:

III. MAIN RESULTS
We start by summarizing our results. Theorem 1 gives a general upper bound on the storage capacity of a heterogeneous DSS as a function of the average resources per node. x, y x 4 , y 4 x 5 , y 5 x 6 , y 6 (b) A DSS constructed by combining together n! = 6 copies of the original heterogeneous system corresponding to all possible node permutations. The obtained DSS is homogeneous with uniform storage per node α = 10 and repair bandwidth per helper β = 10. The capacity of this system is 20 as given by (2) [1]. Any code that stores a file of size C (C = 3 here) on the original DSS can be transformed into a scheme that stores a file of size n!C = 6C in the "bigger" system. This gives the upper bound in (14) C ≤ 20/6 = 10/3.

Theorem 1:
The capacity C of a heterogeneous distributed storage system, with node average capacityᾱ and average repair bandwidthγ, is upper bounded by The right-hand side term in (14) is the capacity of a homogeneous system in (2) in which all nodes have storage α =ᾱ and total repair bandwidth γ =γ . Th. 1 states that the capacity of a DSS cannot exceed that of a homogeneous system where the total system resources are split equally among all the nodes. Moreover, Th. 1 implies that symmetric repair is optimal in homogeneous systems in the sense that it maximizes the system capacity. This justifies the repair model adopted in the literature. This result is stated formally in Cor. 2.
While the optimality of symmetric repair is known for the special case of MDS codes [11], Cor. 2 asserts that symmetric repair is always optimal for any choice of system parameters. This result follows directly from Th. 1 and avoids the combinatorial cut-based arguments that may be needed in a more direct proof.
Corollary 2: In a homogeneous DSS with node capacity α and total repair bandwidth γ, symmetric repair maximizes the system capacity.
When we know the parameters of the nodes in the system beyond the averages, we can obtain possibly tighter bounds as described in Th. 3. To simplify the notation, let us order the repair bandwidth per helper β ijS into an increasing sequence β 1 , β 2 , . . . , β m , such that β l ≤ β l+1 and where m = nd n−1 d . Also, recall that α 1 ≤ α 2 ≤ · · · ≤ α n .
Theorem 3: The capacity C of heterogeneous DSS is bounded by When the system is compromised by an eavesdropper the system secrecy capacity can be upper bounded as follows.
Theorem 4: The secrecy capacity C s of a DSS when nodes in the system are compromised by an eavesdropper is upper bounded by This theorem implies that symmetric repair also maximizes the secrecy capacity of a homogeneous DSS.

A. Example & Proof of Theorem 1
We illustrate the proof of Th. 1 through an example for the special case in which the bandwidths depend only on identity of the helper node. We compute the capacity of the DSS for this specific example, and show that it is strictly less than the upper bound of Th. 1. That is, it does not achieve the capacity of a homogenous system with the same average characteristics. More specifically, consider the heterogeneous DSS depicted in Fig. 1(a) with (n, k, d) = (3, 2, 2) formed of 3 storage nodes v 1 , v 2 and v 3 with storage capacities (α 1 , α 2 , α 3 ) = (1, 2, 2) and repair bandwidths (β 1 , β 2 , β 3 ) = (1, 2, 2). The average node capacity α = 5/3 and repair bandwidth are β = 10/3. Th. 1 gives that the capacity of this DSS C ≤ 10/3 = 3.33.
For this example, it is easy to see that the DSS capacity is C = 3 ≤ 10/3. In fact, a user contacting nodes v 1 and v 2 cannot download more information then their total storage α 1 + α 2 = 3. This upper bound is achieved by the code in Fig. 1(a). The code stores a file of 3 units (x, y, z) in the system. During repair the new node downloads the whole file and stores the lost piece of the data (note that the repair bandwidth constraints allow this trivial repair).
To obtain the upper bound in (14), we use the original heterogeneous DSS to construct a "bigger" homogeneous system. We obtain this new system by "glueing" together n! = 3! = 6 copies of the original DSS as shown in Fig. 1(b). Each copy corresponds to a different permutation of the nodes. In the figure, the i th copy stores the file (x i , y i , z i ). For example in Fig. 1(b), the first copy is the original system itself, the second corresponds to node v 1 and node v 3 switching positions, and so on.
The "bigger" system is homogeneous because all its nodes have storage α = 10 and repair bandwidth per helper β = γ/d = 10. The capacity C of this system can be computed from (2): As seen in Fig. 1, any scheme that can store a file of size C in the original DSS can be transformed into a scheme that can store a file of size n!C in the "bigger" DSS. Therefore, we get n!C ≤ C and C ≤= 10/3. This argument can be directly generalized to arbitrary heterogeneous systems. The general proof follows the same steps explained above and can be found in Appendix B.
Theorem 1 implies that symmetric repair, i.e., downloading equal numbers of bits from each of the helpers, is optimal in a homogeneous system. To see this, consider a DSS with node storage capacity α, and a total repair bandwidth budget γ. A new node joining the system has the flexibility to arbitrarily split its repair bandwidth among the d helpers as long as the total amount of downloaded information does not exceed γ. In other words, we have i∈S β ijS = γ, ∀j, S. Now, irrespective of how each new node splits its bandwidth budget, the average repair bandwidth in the system is the same, γ = γ. If we apply Th. 1, we get an upper bound that matches exactly the capacity in (2) of a homogeneous DSS with symmetric repair. Hence, we obtain the result in Cor. 2.

B. Proof of Theorem 3
To avoid heavy notation, we focus on the case in which the repair bandwidth depends only on the helper node (β ijS = β i ). We give in Th. 5 lower and upper bounds specific to this case. These bounds are similar to the ones in Th. 3, but can be tighter. The proof of Th. 3 follows the exact steps of the proof below and will be omitted here. Again, we assume that the nodes are indexed in increasing order of node capacity, α 1 ≤ α 2 ≤ · · · ≤ α n . We also order the values of the repair bandwidths β to obtain the increasing sequence β 1 ≤ β 2 ≤ · · · ≤ β n . Theorem 5: The capacity C of a heterogeneous DSS, in which the repair bandwidth depends only on the identity of the helper node, is bounded as C min ≤ C ≤ C max , where and The second expressions for C min and C max highlight the analogy with the bounds in Th. 3. Before proving Th. 5, we give a couple of illustrative examples and discuss some special cases.
The upper and lower bounds can coincide (C min = C max ) in certain cases, which gives the exact expression of the capacity. For example: 1) A homogeneous DSS, where we recover the capacity expression in (2). 2) A DSS with uniform repair bandwidth, i.e., β i = β, ∀i. The To prove the upper and lower bounds in Th. 5, we first establish the following expression of the DSS capacity.
Theorem 8: The capacity C of a heterogeneous DSS is given by where for any S ⊆ {1, . . . , n}, β S = i∈S β i .
The proof of Th. 8 is a generalization of the proof in [1] of the capacity of a homogeneous system (2). We defer this proof to Appendix C and explain here the intuition behind it. Consider the scenario depicted in Fig. 2 where nodes v f1 , . . . , v f k fail and are repaired successively such that node v fi is repaired by downloading data from the previously Fig. 2. A series of k failures and repairs in the DSS that explains the capacity expression in (9). Nodes v f 1 , . . . , v f k fail successively and are repaired as depicted above. The amount of "new" information that node v f i can give the user is the minimum between his storage capacity α f i and downloaded data β S i . repaired nodes v f1 , . . . , v fi−1 and d − (i − 1) other helper nodes in the system. Consider now a user contacting nodes v f1 , . . . , v f k .
The amount of "non-redundant" information that node v fi can give to the user is evidently limited by its storage capacity α i on one hand, and on the other hand, by the amount of information β Si downloaded from the d − i + 1 helper nodes that are not connected to the user. Minimizing over all the choices of f 1 , . . . , f k gives the expression in (9).
It is not clear whether the capacity expression in (9) can be computed efficiently. For this reason we give upper and lower bounds that are easy to compute. To get the lower bound in (7), let (f 1 , . . . , f k ) = (f * 1 , . . . , f * k ) be the minimizer of (9). We have where l * , 0 ≤ l * ≤ k is the number of those cases where α f * i is smaller or equal than the corresponding sum of β's.

A. Secrecy Capacity
We now consider the case in which nodes in the system are compromised by a passive eavesdropper who can observe their downloaded and stored data, but cannot alter it. The secrecy capacity C s of the system is the maximum amount of information that can be delivered to any user without revealing any information to the eavesdropper (perfect secrecy).
Formally, let S be the information source that represents the file that is stored on the DSS. A user contacts the nodes in any set B ⊂ {v 1 , . . . , v n } of size k and downloads their stored data denoted by C B . The user should be able to decode the file, which implies H(S|C B ) = 0. Let E be the set of the compromised nodes, and D E be the data observed by the eavesdropper. The perfect secrecy condition implies that H(S|D E ) = H(S). Following the definition in [16], we write the secrecy capacity as Finding the secrecy capacity of a DSS is a hard problem and is still open in general, even for the class of homogeneous systems. Let C ho s (α, β, ) denote the secrecy capacity of a homogeneous DSS implementing symmetric repair and having compromised nodes. Following the same steps in the proof of Th. 1, we can show that the secrecy capacity C s of a heterogeneous DSS cannot exceed that of a homogeneous DSS having the same average resources.
Theorem 9: Consider a heterogeneous DSS with average storage capacity per node α, average repair bandwidth γ, and compromised nodes. The secrecy capacity of this system is upper bounded by Equations (12) and (3) imply the following upper bound stated in Th. 4: Using Th. 9, we easily deduce that symmetric repair is also optimal in terms of maximizing the secrecy capacity of a compromised DSS.
Corollary 10: Symmetric repair maximizes the secrecy capacity of a homogeneous system with a given budget on total repair bandwidth.

VI. CONCLUSION
We have studied distributed storage systems that are heterogeneous. Nodes in these systems can have different storage capacities and different repair bandwidths. We have focused on determining the information theoretic capacity of these systems, i.e., the maximum amount of information they can store, to achieve a required level of reliability (any k out of the n nodes should be able to give a stored file to a user). We have proved an upper bound on the capacity that depends on the average resources available per node. Moreover, we have given an expression for the system capacity when we know all the nodes' parameters. This expression may be hard to compute, but we use it to derive additional upper and lower bounds that are easy to evaluate. We have also studied the case in which the system is compromised by an eavesdropper, and have provided bounds on the system secrecy capacity under a perfect secrecy constraint. Our results imply that symmetric repair maximizes the capacity of a homogeneous system, which justifies the repair model used in the literature. Problems that remain open include finding an efficient algorithm to compute the capacity of a heterogeneous distributed storage system, as well as efficient code constructions.

A. Functional vs. Exact Repair
All of our results so far assumed a functional repair model. However, Theorems 1, 4 and 9 can be directly extended to the exact repair case. For instance, Th. 1 becomes: Theorem 11: The capacity C of a heterogeneous distributed storage system under exact repair, with node average capacitȳ α and average repair bandwidthγ, is upper bounded by where C ho exact (ᾱ,γ) is the capacity of a homogeneous DSS under exact repair.
In the proofs of Theorems 1, 4 and 9 we construct a new "big" storage system using the original one as a building block. Hence, if we had exact repair in the original system to start with, we will have exact repair in the new "big" system. The results can thus be straightforwardly generalized to the case of exact repair. Moreover, under an exact repair constraint, a homogeneous DSS with symmetric repair maximizes capacity under given average node storage and repair bandwidth budgets.
The other results, namely Theorems 3, 5, and 8, are proved using the analysis of the information flow graph. Therefore, It is not clear if there is an obvious extension of these results to the case of exact repair.

B. Proof of Theorem 1
We prove Th. 1 by making formal the argument of the example in Section IV-A. We start by describing the operation of adding, or combining, together multiple storage systems having same number of nodes. Let DSS 1 , DSS 2 be two storage systems with nodes v 1 1 , . . . , v 1 n and v 2 1 , . . . , v 2 n , respectively. The new system that we refer to as DSS obtained by combining DSS 1 and DSS 2 is comprised of n nodes, say u 1 , . . . , u n . Node u i has storage capacity α i = α 1 i + α 2 i (superscript j, j = 1, 2, denotes a parameter of system S j ). Moreover, when node u j fails in DSS, the new node downloads β ijS = β 1 ijS + β 2 ijS amount of information from helper node u i (recall that S is the set of indices of the d helper nodes). We write DSS = DSS 1 + DSS 2 . Now, let DSS be the given heterogeneous system for which we wish to compute its capacity C. For each permutation σ : {1, . . . , n} → {1, . . . , n}, we denote by DSS σ the storage system with nodes v σ 1 , . . . , v σ n such that v σ i = v σ(i) . Let P n denote the set of all n! permutations on the set {1, . . . , n}. We define a new "big" system by The new system DSS b is homogeneous with symmetric repair where the storage capacity per node α b is given by and the repair bandwidth per helper β b is given by Therefore, the capacity C b of DSS b as given by (2) is Any scheme achieving the capacity C of the original system can be naturally extended to store a file of size n!C in DSS b (see Fig. 1). Therefore, C b ≥ n!C. This inequality combined with (16) gives the result of the Th. 1.

C. Proof of Theorem 8 (sketch)
We use the definition of the flow graph in [1] to represent the DSS. The flow graph is a multicast network in which the multiple destinations correspond to the users requesting files from the DSS by contacting any k out of the n nodes. Therefore, the capacity of the DSS is the capacity of this multicast network which is equal to the minimum value of the min-cuts to the users, by the fundamental theorem of network coding. Note that in the flow graph, a storage node v i is represented by two vertices x i in and x i out connected by an edge of capacity α i (see Fig. 2).
Let C be the capacity of the DSS and define F to be We want to show that C = F . Let (f 1 , . . . , f k ) be fixed and consider the successive failures and repairs of nodes v f1 , . . . , v fn as seen in Fig. 2. Suppose node v f1 is repaired by contacting the helper nodes that minimize the sum β S1 with |S 1 | = d and {f 1 } ∩ S 1 = ∅, and node v f2 is repaired by contacting node v f1 and the d − 1 helper nodes that minimize the sum β S2 with |S 2 | = d−1 and {f 1 , f 2 } ∩ S 2 = ∅. We continue in this fashion and finish with node v f k being repaired by contacting nodes v f1 , . . . , v f k−1 and the d − k + 1 helper nodes that minimize β S k with |S k | = d + 1 − k and {f 1 , . . . , f k } ∩ S k = ∅. Now consider a user contacting nodes v f1 , . . . , v fn there is a cut to the user of value F . By the max-flow min-cut theorem, we get C ≤ F .
To prove the other direction, consider a user in the system and let E denote the edges in the min-cut that separates this user from the source in the flow graph. Also, let V be the set of vertices in the flow graph that have a path to the user. Since the flow graph is acyclic, we have a topological ordering of the vertices in V , which means that they can be indexed such that an edge from v i to v j implies i < j.
Let x 1 out be the first "out-node" in V (with respect to the ordering). If x 1 in / ∈ V , then x 1 in x 1 out ∈ E. On the other hand, if x 1 in ∈ V , then the set of incoming edges S 1 , |S 1 | = d, of x 1 in must be in E. Now similarly let x 2 out be the second "out-node" in V with respect to the ordering. If x 2 in / ∈ V , then x 1 in x 2 out ∈ E. If x 2 in ∈ V , then the set S 2 , |S 2 | ≥ d − 1, of edges incoming to x 2 in , not including a possible edge from x 1 out , must be in E. All k nodes adjacent to the user must be in V so continuing in the same fashion gives that the min-cut is at least where f i = f j for i = j, |S i | = d + 1 − i, and {f 1 , . . . , f i } ∩ S i = ∅. Hence C ≥ F .


INFLUENCE OF LIPSCHITZ BOUNDS ON THE SPEED OF GLOBAL OPTIMIZATION

Global optimization methods based on Lipschitz bounds have been analyzed and applied widely to solve various optimization problems. In this paper a bound for Lipschitz function is proposed, which is computed using function values at the vertices of a simplex and the radius of the circumscribed sphere. The efficiency of a branch and bound algorithm with proposed bound and combinations of bounds is evaluated experimentally while solving a number of multidimensional test problems for global optimization. The influence of different bounds on the performance of a branch and bound algorithm has been investigated.

Introduction
Global optimization is used in such fields as economics, operations research, biology, engineering design and management as well as other numerous engineering and applied sciences. For example, prediction methods in computational finance forecast various kinds of quantities related to stock markets, like stock prices, stock volatility and ranking measures. Prediction problem of building a multi-stock artificial trader (Björkman, Holmström 1999) can be used instead of the classical time series approach. The behavior of the trader is controlled by a parameter vector which is tuned for the best performance. Global optimization algorithm DIRECT (Jones et al. 1993) was applied to find optimal parameters. Extension of optimization to decision-making systems is a challenging topic of research (Sakalauskas, Zavadskas 2009).
One of the most investigated fields of global optimization is Lipschitz optimization (Strongin 1978;Strongin, Sergeyev 2000;Sergeyev, Kvasov 2008). In this paper we consider the problem of global optimization of a Lipschitz continuous objective function : → x differs from * f by no more than a specified accuracy ε can be found. There are at least four approaches to obtain an estimate of Lipschitz constant (Sergeyev, Kvasov 2009): 1) it can be given a priori; 2) its adaptive global estimate over the whole domain can be used; 3) local Lipschitz constants can be estimated adaptively using the local tuning technique (Sergeyev 1995(Sergeyev , 1998; 4) a set of possible estimates can be used (Jones et al. 1993).
The most studied case of problem (2) is the univariate one ( =1) n , for which numerous algorithms have been proposed, compared, and theoretically investigated. In the present paper, we are interested in the multivariate case ≥ ( 2) n . In Lipschitz optimization the upper bound for ( ) f x over a sub-region ⊆ I D is evaluated by exploiting Lipschitz condition (1). It follows from (1) that for all ∈ , If ∈ y I is fixed, then the convex function overestimates ( ) f x over I . The superscript q indicates the norm used for the upper bound calculation. Let T be a finite set of distinct points in I . Then, the Piyavskii-type upper bound over I , given the function values ∈ ( ), f y y T , and the Lipschitz constant L , is provided by In the univariate case, the function ∈ ( ) min q y y T F x is piecewise linear, and ϕ q can be determined in a simple straightforward way (Piyavskii 1972). For (n > 2), however, problem (4) constitutes a difficult optimization problem.
Therefore, branch and bound algorithms use considerably weaker bounds. In general, weaker bounds belong to the following two simple families µ 1 and µ 2 . Let x y x y denote the diameter of I . For example, if = { : , and if I is an n -simplex, then the diameter δ ( ) q I is the length of its longest edge. Afterwards a simple upper bound can be derived from (3): where ⊂ T I is a finite sample of points in I , where the function values of f have been evaluated. If I is a rectangle or a simplex, the set T often coincides with the vertex set ( ) V I . A tighter but computationally more expensive than (5) bound is Methods with the ϕ q type bounds (4) can hardly be used to solve typical test problems with relatively large Lipschitz constants and (n > 2). Branch and bound algorithms can almost always provide reasonable approximate optimal solutions for (n = 3) , although the methods usually involve more function evaluations (and thus are less suitable in case of very expensive functions), but much less auxiliary computational time than the methods with the ϕ q type bounds. Therefore, it is important to investigate possibilities of bounds tighter than (5) and (6), but computationally less expensive than (4). In this paper, we propose a bound based on the function values at the vertices and the circumradius of an n-circumsphere.

Branch and bound with simplicial partitions and Lipschitz bound
Branch and bound is a technique for implementation of covering global optimization methods as well as combinatorial optimization algorithms. An iteration of a classical branch and bound algorithm processes a node in the search tree representing a not yet explored subspace of the solution space. The iteration has three main components: selection of the node to process, branching of the search tree and bound calculation. Several selection strategies (Paulavičius et al. 2010) may be used: best-first, depth-first, breadth-first, statistical (Žilinskas, A., Žilinskas, J. 2010). Partitions may be hyper-rectangular, simplicial (Horst 1997;Gorodeckij 1999), hyper-conic or hyper-spherical. Bounds may be computed using envelopes of functions (Androulakis et al. 1995;Adjiman, Floudas 1996;Zlobec 2010), interval arithmetic (Moore 1966;Hansen, Walster 2003;Žilinskas 2005) as well as Lipschitz condition. Most of Lipschitz global optimization branch and bound algorithms use hyper-rectangular partitions. Simplicial partitions are preferable when the values of an objective function at the vertices of partitions are used to compute bounds. Another advantage of simplicial partitions is that they may be used to vertex-triangulate feasible regions of non-rectangular shape defined by linear inequality constraints (Žilinskas 2008), what allows the reduction of search space of problems with symmetric objective functions (Žilinskas 2007).
For simplicial branch and bound, the feasible region should be initially covered by simplices. The most preferable initial covering is face to face vertex triangulation -partitioning of the feasible region into finitely many n-dimensional simplices, whose vertices are also the vertices of the feasible region. We use a standard way of triangulation into n! simplices. All simplices share the diagonal of the feasible region and are of equal hyper-volume. It is also possible to over-cover the feasible region by one simplex (Žilinskas, A., Žilinskas, J. 2002). However, the objective function may be undefined outside the feasible region. Moreover, the hyper-volume of over-covering simplex is considerably larger than the feasible region. For example, one version of over-covering is to fit a hyper-rectangle into a simplex matching a vertex: one vertex of the hyper-rectangle and one vertex of the simplex are matched, the edges of the simplex from this vertex include edges of the hyper-rectangle from this vertex, and the opposite vertex of the hyper-rectangle is placed in the opposite face of the simplex. If a hyper-cube is over-covered using this strategy, the hyper-volume of the simplex is exponentially larger than the hyper-volume of the hyper-cube (approximately π / 2 n e n times). There are some possibilities to partition a simplex into smaller ones (Žilinskas, A., Žilinskas, J. 2002). Experiments have shown that the most preferable partitioning is a subdivision of the simplex into two by a hyper-plane passing through the middle point of the longest edge and the vertices which do not belong to the longest edge. The lower and upper bounds for the maximum of the function over a simplex are estimated using the function values at the vertices. At the beginning of the algorithm the rectangular feasible region is covered by simplices and some initial values are initialized. Then the loop is executed until the candidate list is not empty. The simplex with the best upper bounding function value is chosen. If the difference between the upper bound and the global lower bound is larger than the predefined precision ε the simplex is subdivided into two new simplices which are inserted into candidate list. Convergence of such a branch and bound algorithm for maximizing a Lipschitz functions over n-simplices by using bisection at the midpoint of one of the longest edges and the upper bounds µ 1 (5) q , µ 2 (6) q follows from exhaustiveness of the subdivision and continuity of the function f(x) .

Lipschitz bound over simplices based on the function values at the vertices and the radius of the circumscribed sphere
In this section a new Lipschitz bound over simplices is proposed. The bound is often stronger than usually used trivial bounds and still computationally cheap, especially for low-dimensional problems ≤ ( 3) n for which calculation of the radius of the circumscribed sphere is cheap. To find the radius, n + 2 determinants of (n + 1) ×(n + 1)-dimensionality matrices must be calculated.
be a Lipschitz continuous objective function, ⊂ I D is an n-simplex, 2 ( ) R I denotes the radius of circumscribed n-sphere and ( ) V I denotes the set of vertices. Then Proof. An n-simplex I is covered by n-balls Ο + , =1, , 1  i i n such that the radius 2 ( ) R I is the same for all n-balls and centers coincide with the vertices i v of the simplex I (two dimensional example is shown in Fig. 1 Fig. 1. Covering of a triangle (two-dimensional simplex) I by disks (2-balls) Ο + , =1, , 1  i i n of the same radius 2 ( ) R I
Completing the square for (9) gives: which is the n-circumsphere

Combination of bounds with various norms
Experiments have shown (Paulavičius, Žilinskas 2006(Paulavičius, Žilinskas , 2007 that no single norm and corresponding Lipschitz constant is the best for all problems and therefore a combination of the infinite, Euclidean and first norms is used for calculation of the upper bound The Piyavskii type (4) Lipschitz bound with the first norm ϕ 1 was proposed in (Paulavičius, Žilinskas 2008): However, the first norm does not always give the best bounds (Paulavičius, Žilinskas 2008). The further investigation (Paulavičius, Žilinskas 2009) has shown that an aggregate bound (AB) composed of ∞ µ 2, 2 and ϕ 1 bounds

Experimental investigation
In this section the results of computational experiments are presented and discussed. Various test problems ≥ ( 2) n for global optimization from (Hansen, Jaumard 1995;Jansson, Knüppel 1992;Madsen, Žilinskas 2000) have been used in our experiments. The list of all used test problems and their global minima from the literature are shown in Table 1. For the (n = 2, 3) test problems we use the same precision ε as used by Hansen and Jaumard (Hansen, Jaumard 1995). The proposed algorithm assumes that Lipschitz constants are given a priori. These constants have been evaluated in the same way, as in (Hansen, Jaumard 1995). A very fine grid search algorithm of 1000 n points for (n = 2, 3) and 100 n points for (n = 4, 5, 6) dimensional test functions have been used and the obtained estimates should be close to the best Lipschitz constants. The values are given in (Paulavičius, Žilinskas 2006(Paulavičius, Žilinskas , 2007. The speed of global optimization has been estimated using the number of function evaluations criterion.
The results of the simplicial branch and bound algorithm with the proposed bound ψ 2 (7) based on the Euclidean norm and with the bound µ 2 2 (5) based on the same norm are shown in Table 2. For all test problems the number of function evaluations is smaller when the proposed bound ψ 2 is used and on the average it is by 26% smaller than when the bound µ 2 2 is used. The rate ( ψ < µ 2 2 2 ) shows how often the proposed bound ψ 2 is better (more tight) than the bound µ 2 2 . For the used test functions it is better on average in 70% of simplices. However, the bound ψ 2 does not always give better bound comparing with µ 2 2 (the rate is not equal to 1). If function values at the vertices V(I) of the simplex I differ significantly: I , then µ 2 2 type bound is more tight comparing with the proposed ψ 2 bound. If the difference between the maximal and minimal functions values is smaller than ( ) δ − 2 2 2 ( ) ( ) L R I I , then the proposed ψ 2 type bound gives better results. Therefore, for computationally expensive functions it might be worthwhile to append the bound ψ 2 to the aggregate bound AB (13). Performance of simplicial branch and bound algorithm with the aggregate bound AB (13) is similar to that of the best branch-and-bound algorithm for Lipschitz optimization and it is often better (Paulavičius, Žilinskas 2009). The numbers of function evaluations on the average is by 23% smaller when the improved aggregate bound IAB (14) is used than when the aggregate bound AB (13) is used.
The value of objective function at the same point is required when computing bounds over neighbor sub-regions. If this value is evaluated for parent sub-region, it is not necessary to evaluate it again. However, in multidimensional case the same points may be involved in subdivision of different sub-regions. It is possible to maintain a list of all points where the objective function is evaluated and avoid evaluation of objective function at such points several times by verifying if the point is in the list before evaluation. In two-dimensional case after initial covering by simplices there are two simplices. When one of them is subdivided into two by a hyper-plane passing through the middle point of the longest edge the function value at this point should be evaluated. Sometime later in the optimization process subdivision of the other simplex may be performed, again requiring the function value at the same point. By verification of this point it is possible to avoid evaluation of the function again. Such vertex verification reduces the number of function evaluations essentially, but also increases 6,6 0 4L 2 computational time and therefore it is more suitable in the case of computationally expensive functions. The numbers of function evaluations of the algorithm with improved aggregate bound and verification of vertices are shown in Table 2 in the column IAB . These results using improved aggregate bound IAB significantly improve performance of the proposed Lipschitz optimization algorithm (Paulavičius, Žilinskas 2009), whose results were often better than that of the best branch and bound algorithm for Lipschitz optimization. It is interesting to compare the results with other type of bounds. αBB method (Androulakis et al. 1995) assumes that objective function is twice continuously differentiable and uses this feature to construct convex underestimators. Since the assumption on Lipschitz continuity is weaker, in general Lipschitz bounds should be worse than that of αBB, however, the difference is not known. We investigate IAB and a piecewise application of the αBB underestimator (Gounaris, Floudas 2008) to see the difference. Table 3 presents obtained upper bounds for the maximum value of test problem No. 2 after the same number of evaluations of objective function as results given in (Gounaris, Floudas 2008). Their method subdivides the feasible region into N1 × N2 rectangles which requires (N1 + 1) × (N2 + 1) function evaluations. Therefore, we investigate the upper bounds estimated after 4 (N1 = N2 = 1), 9 (N1 = N2 = 2), 25 (N1 = N2 = 3) and so on function evaluations. As expected, αBB overestimator provides better (more tight) upper bounds. In the beginning the difference is larger, but it becomes smaller when the numbers of partitions increase.

Conclusions
In this paper a new Lipschitz bound over simplices is proposed. It is based on the function values at the vertices and the radius of the circumscribed sphere of the simplex. The speed of simplicial branch and bound algorithm with the proposed Lipschitz bounds has been investigated and compared. Test problems of various dimensionalities (n = 2, 3, 4, 5, 6) from the literature have been used for experimental investigation of the algorithm. The experiments showed that the proposed bound is often better than a usually used bound. For the used test functions the rate ( ψ < µ 2 2 2 ) showed that proposed bound ψ 2 is better (more tight) than the bound µ 2 2 on average in 70% of simplices. Therefore, the use of the proposed bound in simplicial branch and bound reduces the number of function evaluations by 26% comparing to a usual bound. If the proposed bound is used in an aggregate bound with various norms performance improvement is 23% comparing to the aggregate bound without the proposed bound.
The proposed method appears to be inferior to the αBB method. This is to be expected because the latter method assumes that the objective function is twice continuously differentiable.


EFFICIENT MULTIPATH ROUTING AND WAVELENGTH ALLOCATION USING TRAFFIC GROOMING IN OPTICAL WAVELENGTH DIVISION MULTIPLEXING MESH NETWORKS

In optical WDM mesh networks, traffic grooming is e s ntial in order to utilize the bandwidth efficien tly to minimize the cost and meet the user service require ment. By grooming traffic, it is possible to reduce th total cost of all Add drop multiplexer needed. Also for the high processing capability in a WDM networ k, the path should be capable of carrying the traffic w thout any failure. In this study, we use a traffi c grooming algorithm to establish light paths between node pairs having the largest amounts of traffic. Among the established light paths, the risk-disjoin t paths are obtained using the large traffic first algorithm. After establishing light paths, the traf fic is routed from the source to the connection nod e and then traffic is transmitted from the connection nod e to the destination node. In addition to the effic ient routing, we propose a wavelength allocation technique to ens ur that the traffic is transferred to the destinat ion with efficient use of the network resources. From the si mulation results we show that this algorithm involv es additional capacity in the virtual topology to supp ort survivable routing of connections.

WDM Networks
Wavelength Division Multiplexing (WDM) provides huge amount of optical bandwidth for telecom operators to satisfy the increasing traffic demands and provide high speed connectivity for achieving faster transfer rate for the high speed communication. In WDM network, the optical transmission is thus divided into number of non overlapping wavelength bands where each of the wavelengths supports a particular single communication channel. WDM is further classified into two broad categories: (1) Coarse WDM with nearly 40 wavelengths per channel and (2) Dense WDM with nearly 160 wavelengths per fiber where each of the wavelengths can be viewed as a channel that provides optical connectivity between two nodes. WDM channels co-exist on single fiber where we can tap into huge fiber bandwidth with corresponding challenges of design and development of most appropriate network architecture, protocol and algorithms.
Each fiber can carry a large number of high-capacity channels. Dividing these channels into lower-bandwidth virtual connections between couples of nodes gives rise to technical difficulties: wavelengths are at most a few hundreds; therefore they need to be time-multiplexed to be shared among many couples of communicating nodes.
The key components to achieve time multiplexing, the Add-Drop Multiplexers (ADM), are needed each time a wavelength has to be processed electronically at a node in order to add or drop packets. Therefore they represent a significant fraction of the total cost of the infrastructure (Sinha et al., 2012).

Traffic Grooming
Traffic grooming is defined as the intelligent allocation of the demands onto available wavelengths such that the cost of the network is minimized. In Wavelength Division Multiplexing (WDM)-based networks the bandwidth of a wavelength channel is high when compared with the bandwidth of connection requests from higher layers, such as the Internet Protocol (IP) layer. In this case traffic grooming can lead to an efficient use of wavelength channel bandwidth. Traffic grooming describes how low speed connections are packed into high capacity connections, such as lightpaths, avoiding the waste of bandwidth that rises from the mismatch between a connection demand and the lightpath capacity. Traffic grooming is a key issue in optical WDM networks, which must be cost-effective (Patel et al., 2010).
Traffic grooming improves resource utilization for both unicast and multicast traffic. It consists of multiplexing traffic (usually statistically) from different demands in the same lightpath or light-tree, as well as to route one demand through several lightpaths and/or light-trees. Routing unicast and multicast traffic together in a network represents a challenge taking into account the limitations of the WDM technology. Traditionally, there are two schemes for performing this: (i) light-trees groom together unicast with multicast traffic; thus OEO conversions are reduced but, unicast traffic can arrive to undesired nodes (incurring in bandwidth wastage) and (ii) unicast traffic is routed using lightpaths through different wavelengths than those used by light-trees (Paul and Shrivastava, 2010).
In optical networks employing Wavelength Division Multiplexing (WDM) technology, the capacity of a fiber is divided into several non-overlapping wavelength channels that can transport data independently. These wavelength channels make up lightpaths, which are used to establish optical connections that may span several fiber links. With current commercial technology, each lightpath can be independently operated at a data rate ranging up to 100 Gb/s. However, traffic between a pair of nodes may not be able to fill up the available bandwidth of a lightpath. In order to efficiently utilize the available bandwidth, several independent traffic streams can be aggregated to share the capacity of a lightpath. This is known as traffic grooming (Chen et al., 2010).

Need for Traffic Grooming in WDM Networks
In an optical WDM Network, every node may have one SONET Add/Drop Multiplexer (ADM) for each wavelength. Instead, with traffic grooming it may be possible to have ADM for the wavelength used at that node; other wavelengths may be optically routed without electronic switching. To efficient utilize the bandwidth in a WDM system, traffic grooming can be used to combine lower rate traffic stream on to available wavelengths in order to minimize the cost and meet the user service requirement (Paul and Shrivastava, 2010).
In order to save network cost and to improve network performance, it is very important for the network operator to be able to "groom" the multiple lowspeed traffic connections onto high-capacity circuit pipes (Chen et al., 2010).
By intelligently grooming traffic, we can reduce the total cost of all Add drop multiplexer ADMs needed. The potential saving can be significant and grows with both the network size and inter nodal demand (Sinha et al., 2012).
The light-paths are assumed to be full-duplex and the forward and reverse direction signals use the same wavelength and path. Unless a wavelength carries traffic destined for a given node or needs regeneration, it passes through optically. Otherwise, the following take place: (1) the lightpath is terminated, (2) the traffic is processed electronically (and regenerated simultaneously), (3) traffic destined to the node is dropped and (4) the rest of the traffic, including locally added traffic, if any, is forwarded on other lightpaths through the transceivers. Thus traffic grooming is required (Beshir et al., 2011).
In Optical-Electrical-Optical (OEO) conversions are usually avoided by network operators because more network resources (e.g., transmitters and receivers) are needed to regenerate optical signals. Moreover, OEO conversions could delay traffic since traffic flowing must be processed and queued electronically. Therefore, the way in which traffic is groomed affects not only the performance of the network but also its throughput (Ramesh and Vadivelu, 2010).

Previous Work
In our previous paper (efficient multipath routing and wavelength allocation for optical WDM mesh networks), we have designed an efficient IP router for the WDM network in order to satisfy the optical constraints. We design a router for data transmission. The multiple paths toward each destination are set from the source node. Multiple routes can be discovered for data transmission using the router and the paths which satisfy the optical constraints are set for data transmission. The traffic routing is performed by choosing the connection node.
Along with routing, we also propose to allocate wavelength to every path such that complete bandwidth is effectively utilized. We have proposed a technique in which wavelength allocation is performed before transmission of the data in order to make the system efficient in terms of wavelength.
As an extension to this study, we use a traffic grooming algorithm in order to enhance the traffic. This algorithm tries to establish light paths between node Science Publications JCS pairs having the largest amounts of traffic. Depending upon the resources to be shared among the backup paths, the protection schemes are divided into dedicated protection and shared protection. We use two times Dijkstra's risk-disjoint path algorithm for dedicated protection in order to establish two lightpaths. For a shared protection, we use dijkstra algorithm in order to establish a lightpath. By this algorithm, additional capacity can be involved in the virtual topology to support survivable routing of connections.  have proposed and investigate the characteristics of survivable multipath traffic grooming with connection-level protection in telecom mesh networks.

Related Work
Their results indicate that (1) the network performance can be notably improved by exploiting the inversemultiplexing capability, (2) tight constraints have negative impact on performance and (3) use of a single primary path after multipath failure is helpful to reduce the impact.
Ab-Rahman (2012) developed a combined approach of Optical Add-Drop Multiplexer (OADM) and Optical Cross Connect (OXC). Their technique enhances increase the survivability in the ring network. With the 'Accumulation' feature and 'U' turn reflection enable the multiplex, linear and ring protection scheme activated to ensure the signal arrives at the customer although breakdown occurs in the line and optical node. They also performed topology migration without restructuring process due to randomly growth of new nodes. Saleh and Kamal (2009) have addressed the problem in both non-splitting networks where the nodes do not have optical splitting capabilities and in splitting networks where the nodes do have optical splitting capabilities. First, we formulate the problem in each of the two networks as a Mixed Integer Linear Programs (MILP). Afterwards, based on observations from optimal solutions, we develop a heuristic approach for each network by relaxing and simplifying its corresponding MILP. Ramesh et al. (2011) have proposed Distributed dynamic traffic grooming RWA algorithm (DTMR). Here optimal primary, secondary and backup paths are selected. The path selection is based upon minimal blocking probability. This algorithm is proactive, in the sense that we are minimizing blocking probability, maximizing the throughput and the number of requests processed at the source node at a given time. This approach is self regulating, it automatically adapts to various traffic conditions across the network. , have investigated the characteristics of survivable multipath traffic grooming with respect to typical constraints. Their grooming technqiue significantly outperforms single-path traffic grooming. Both typical constraints (DDC and IMF) impact the performance in the metrics of bandwidthblocking ratio and resource overbuild.

Proposed Work
In WDM networks, traffic grooming can be done efficiently by utilizing the bandwidth. Here we use Two Times Disjoint-Risk Disjoint Path (TTD-RDJP) algorithm for solving the two Survivable Traffic Grooming (STG) problems.
The two STG problems include: • Sub-Wavelength Connection Survivable Routing (SWCSR) problem and • Protection Aware Virtual Topology Design (PAVTD) problem Large Traffic First-(LTF-SWCSR) algorithm is used for SWCSR problem which uses TTD-RDJP algorithm to find the risk-disjoint paths in the virtual topology for connections.
Maximizing Single-Hop Traffic (MSHT-PAVTD) algorithm is used for PAVTD problem which uses TTD-RDJP algorithm to find risk-disjoint paths in the physical topology for light-paths.
We consider protection schemes in this work. Protection schemes are divided into dedicated protection and shared protection schemes depending on whether resources can be shared among backup paths or not.
• In dedicated protection, traffic is transmitted simultaneously over two disjoint paths and a switch is used at the receiving node to choose the better signal • In shared protection, the traffic is transmitted over the primary path at normal operation time and the backup paths can share common resources only if their primary paths are node (or link) disjoint. Shared protection offers better resource utilization at the cost of a longer recovery time

Two Times Disjoint-Risk Disjoint Path (TTD-RDJP) Algorithm
TTD-RDJP is an adaptive algorithm in that it updates the link weights of the network according to the current network state. Equation 1 defines the link weight function L(a,b) for a light-path (a,b). L(a,b) is used as a light-path metric while searching for primary paths of connections: where, η r is the bandwidth requirement of the connection, η f (a,b) is the free bandwidth on the lightpath (a, b).

JCS
When shared protection scheme is used, backup connections can share bandwidth within a lightpath if their primary connections are risk-disjoint. Generally, we can evenly divide the bandwidth of a lightpath into S channels. Each channel has a bandwidth equal to the smallest grooming granularity. Depending on the usage, the channels can be classified into three categories, namely dedicated, spare and free channels. A channel is dedicated if it is assigned to a primary connection. A channel is a spare channel if it is assigned to a backup connection. The channels not assigned to any connections are free channels. When a primary connection n is specified, a spare channel s can be further classified as a sharable spare channel or a nonsharable spare channel depending on whether n is riskdisjoint with all the primary connections whose backup connections share the spare channel s. If they are risk disjoint, then s is sharable to n; otherwise, s is not sharable to n. Note that for the dedicated protection scheme, all spare channels are not sharable.
To fully exploit the backup bandwidth sharing to reduce spare capacity consumption, a different link weight function is defined for lightpaths while searching for backup paths of connections. As shown in (2), the backup lightpath weight Bl(a,b,n) also depends on the primary connection n. With (2), the grooming algorithm tries to assign as many sharable spare channels to a backup connection as possible. Only if the amount of sharable spare channels is not enough, does it assign free channels to the backup connection Equation 2: where, η s (a, b, n) is the amount of sharable spare bandwidth on the light path (a,b) with respect to the primary connection n, θ =1-ηs (a, b, n) / ηr is the ratio of the newly reserved bandwidth (η r -η s (a, b, n)) to the bandwidth requirement (η r ), ψ (0 < ψ < 1) is a parameter to weight sharable bandwidth. By making ψ a number smaller than 1, we encourage the grooming algorithm to choose paths using sharable channels instead of free channels. On the other hand, ψ should not be set too small to avoid using too many sharable channels unnecessarily. Note that for dedicated protection, ηs(a,b,n) ≡ 0 regardless of the primary connection n, because all spare bandwidths are not sharable. The Algorithm 1 given below explains TTD-RDJP: Algorithm 1 1. Update the link weights of network N according to the current state of the network.
2. Run Dijkstra algorithm to select shortest path.
3. If shortest path is the primary path Delete any link in N that shares at least one risk with any link in primary path.
End if 4. For shared protection, the link weights of N are updated after the link is deleted. 5. Repeat step 2 on network N to select another shortest path for backup path.

Maximizing Single-Hop Traffic (MSHT-PAVTD) algorithm
We propose the maximizing Single-Hop Traffic (MSHT-PAVTD) heuristic grooming algorithm which tries to establish light-paths between node pairs having the largest amounts of traffic. In MSHT-PAVTD, TTD-RDJP is used to find two risk-disjoint paths and Dijkstra's algorithm is used to find the shortest path.
Initially the connection requests are set to form a traffic matrix. All the traffic matrices are gathered to form a single residual traffic matrix. Then the node pair with maximum residual bandwidth is selected to establish a light-path on risk-disjoint paths.
Algorithm 2 given below explains the MSHT-PAVTD. End if 4. If dedicated protection is concerned. Establish two light-paths from source to destination on risk disjoint paths A and B using algorithm 1.
Else if Shared protection is concerned Establish a light-path from source to destination on path A using Dijkstra algorithm End if In this Fig. 1, node m is the source node and node n is the destination node. For a dedicated protection, the source establishes two lightpaths (m-a-e-h-l-n) and (m-bf-k-n). According to TTD-RDJP the path A acts as a primary path and during failure of primary path, path B is chosen for traffic transmission.

Large Traffic First (LTF-SWCSR) Algorithm
Large Traffic First Algorithm (LTF-SWCSR) is used to find the risk-disjoint paths in the virtual topology for connections. When many connection requests enter the network, the connection requests are sorted in a nonincreasing traffic amount order. The connections are established from source to destination on one path and other path reserves the bandwidth.
Algorithm 3 1. Sort the connection requests in a list L in nonincreasing traffic amount order. 2. When list L is not empty, acquire and remove the connection request from head of L. 3. If dedicated protection is concerned 3.1 Establish primary connection on path A and backup connection on path B. else if shared protection is concerned 3.2 Establish path C for connection between source and destination.

Reserve Bandwidth on path D End if 4 Use algorithm 4 for transmission of traffic
End if (Wang and Ramamurthy, 2004) In this Fig. 2, the source node m establishes primary connection (m-a-e-h-l-n) and backup connection (m-b-fk-n) to the destination n. According to the shared protection path C (m-c-g-i-n) is established for connection between source and destination and path D (m-d-j-o-n) is established for bandwidth reservation.

Transmission Using Connection Node
We propose a technique in which the router placed at the source transfers the data to the connection node and from the connection node, the data is sent through the multiple paths towards the destination with wavelength allocation.
In phase 1, the traffic is routed from the source to the connection node by the router through the link disjoint path and in phase 2 the traffic is transmitted from the connection node to the destination through the link disjoint path set.
In Fig. 3, the source node is initially connected with the node b. Due to congestion at the node b along the path the router sends a warning message (indicated by red arrow) to the source m. Then source node sends connection request to the neighbors of node b (i.e.,) node a and b (indicated by blue arrow). According to the load traffic, the node a is selected as the connection node. Then the router establishes link disjoint path set from source node to connection node a. The router searches multiple paths from node a to node n for congestion control (indicated by black arrows).
Um: Link Disjoint Path from source node m to connection node a Vm: Link Disjoint Path from source node m to node c Ym: Link Disjoint Path set from connection node a to destination n Yt: Traffic associated with path set Ym Ut: Source node traffic Tq: Traffic request Cr: Connection from source m to node b Cw: Congestion warning

Phase 1
When the transmission is not efficient due to insufficient channel availability or congestion at a specific node along the path, then a warning message is sent to the router by the node.
If the routing of the traffic from source m requires j channels and if the maximum channel capacity of the node b is i then: • if j < i ; then there is sufficient channel availability and this node is selected for traffic • routing • if j > i ; then the channel availability is insufficient and congestion occurs at node b so It sends a congestion warning message, Cw to the router as shown in Fig. 1.
The router calculates the overloaded traffic at the congested node as: Overloaded traffic = total traffic-traffic handled L t h t U U = The router then sends a traffic request, Tq to the neighbor nodes; a and c of the congested node b using the routing table information in the router as shown in Fig. 1.
As a return to the traffic request Tq, the router receives information of the neighbor nodes which consist of node id, current load and channel capacity.
The total load on each node is the sum of the loads of the paths passing through that node.
Load on node a, a L and load on node c, C L is calculated as: A L = load on path Um C L = load on path Vm The router then checks the channel availability for the overloaded traffic in each of the neighbor nodes. If the overloaded traffic is t L then: • if t L <C L ; then node c does not get overloaded and can be used as the connection node • if t L >C L ; then node c is overloaded and hence cannot be used as the connection node

JCS
If the neighbor node c is fully loaded, then it cannot be selected as a connection node and so the router will start enquiring about other neighboring node; node a. If is the load on neighbor node a then: • if t L <a L ; then node a does not get overloaded and can be used as the connection node • if t L >a L ; then node a is overloaded and hence cannot be used as the connection node In this way, one of neighboring nodes is selected as the connection node. If node a has sufficient capacity, then node a is selected as the connection node.
The router establishes a Link Disjoint Path set (LDP), Um from source node m to the connection node a. (using algorithms 2 and 3).
For a unit traffic split ratio for connection node a, the traffic associated with path Um is Ut. In the first phase, the router calculates the bandwidth per unit split ratio Sr v for connection node a across link e, as: where, x(U m ) is the number of link disjoint path in U m .

Phase 2
For the congestion control, the router searches for multiple paths from a to n which are least loaded. The router establishes the link-disjoint path set Y m from a to n.
For a traffic split ratio of 1 for connection node a, the traffic associated with path set Y m is Y t .
The router calculates the bandwidth per unit split ratio Sr v , for the second phase as: where, x(Y m ) is the number of link disjoint path in Y m . After phase 2, the router computes the bandwidth, BW per unit split ratio Sr v for intermediate node a throughout the network path as: Then the router computes the maximum value Sr for the traffic split ratio for intermediate node, a that does not lead to violation of (original) link capacity constraints for the above required bandwidth as: where, η e is the maximum capacity constraint For this value Sr of the traffic split ratio for intermediate node a, the router sends SrUt amount of traffic from node m to node a along path set Um and SrYt amount of traffic has to be transmitted from node a to node n along path set Ym.

Wavelength Allocation
For the allocation of the efficient wavelength in the paths in the mesh network, we have selected the cost function as the main criteria.
Initially the cost function q k , which is the cost of assigning wavelength λ k is calculated. Based on the calculated cost function value, the wavelength is allocated in the path, from the connection node to the destination.
All the feasible wavelength in the network is given as a set η = {λ 1 , λ 2 ,…., λ w } and the cost assigned for every λ k ∈ η is indicated as a set, q = {q 1 , q 2 ,…q w }. For each λ k ∈ η.
A connected component G k = {V k , E k } is first derived from the original graph, G = {V, E} starting from the connection node, s such that if λ k is available in the link leading to the destination.
The cost function, q k is calculated based on the number of edges involved in every path of graph G k : The set of wavelengths that can be used to reach the destination is determined from the graph, G k . The subgraph indicates the entire wavelength supported by it.
The vertices in the subgraph may support many wavelengths w(v i ). But only one particular wavelength for each path will be selected, based on its efficiency.
For each vi ∈ V k : • Find the cost ratio = q i /SLi, where SLi is the number of links sharing the same wavelength λ k • Choose a wavelength λ k from w(V i ) to cover V i , where λ k has the minimum cost ratio in w(V i ) • The selected wavelength is allocated to that path end for Increment the split ratio Sr v associated with node a by Sr. Now the egress router collects all the traffic from the link disjoint path sets and then it cross checks the received traffic with the information in its routing table. If the received traffic and the routing table information coincide then the egress router transmits it towards the corresponding destination node.

Simulation Model and Parameters
We examine the performance of our Efficient Multipath Routing and Wavelength Allocation Using Traffic Grooming (MRWATG) technique with an extensive simulation study based upon the ns-2 network simulator. We use the Optical WDM network simulator (OWNs) patch in ns2. In our simulation, we simulate a 15-Node topology (as given in Fig. 1) which can be extended to any number of nodes. Various simulation parameters are given in Table 1.
In our experiments, we use a dynamic traffic model in which connection requests arrive at the network according to an exponential process with an arrival rate r (call/seconds). The session holding time is exponentially distributed with mean holding time s (sec). The connection requests are distributed randomly on all the network nodes.
In all the experiments, we compare the results of MRWATG with the existing "New Technique for Routing and Wavelength Assignment (NTRWA) technique for WDM mesh networks (Chaiwong et al., 2008). In the network can be preceded by accomplishing two processes: one is searching for the shortest main route and the second shortest alternative route and another is randomly choosing wavelength.

Performance Metrics
We measure the following metrics in all the simulation experiments: • Throughput in terms of packets received • Channel utilization • Blocking probability Science Publications

Based on Number of Traffic Flows
We classify the traffic flows as two types low load traffic with a load of 2Mb and high load traffic with a load of 8Mb.
In the initial experiment, we vary the number of high load traffic flows as 1, 2….4, keeping the other flows as low load traffic.

Case-1 (High)
Since the number of high load traffic increase, it will result in overloaded traffic. So the resulting blocking probability linearly increases whereas the throughput and utilization decreases linearly.

JCS
We can see this from the Fig. 5-7. From that figure it is evident that blocking probability of proposed MRWATG is slightly less than that of NTRWA and throughput and utilization are more. This is because of the Large Traffic First algorithm of MRWATG.

Case2 (Low)
In the second experiment, we vary the number of low load traffic flows as 1, 2….4, keeping the other flows as high load traffic.
Since the number of low load traffic increase, the number of high load traffic will decrease resulting in less number of rejected requests. So the blocking probability linearly decreases whereas the throughput and utilization increases linearly. We can see this from the Fig. 8-10. From that figure, it is also evident that blocking probability of proposed MRWATG is slightly less than that of NTRWA and throughput and utilization are more. This is because of the Large Traffic First algorithm of MRWATG.

Based on Number of Wavelengths
In the second experiment, we vary the number of wavelength per link as 4, 6, 8, 10….12 with number of 2 low load and 2 high load traffic flows and measure the throughput and channel utilization.
From Fig. 11, we can see that the Blocking Probability of our proposed MRWATG is less than the Normal method.
From Fig. 12, we can see that the Throughput of our proposed MRWATG is high than the Normal method.
From Fig. 13, we can see that the Channel Utilization of our proposed MRWATG is high than the Normal method.

CONCLUSION
In this study, we have proposed a traffic grooming algorithm in order to enhance the traffic. Here, Maximizing Single-Hop Traffic (MSHT-PAVTD) algorithm is used to establish light paths between node pairs having the largest amounts of traffic. Among the established light paths, the risk-disjoint paths are obtained using the Large Traffic First algorithm (LTF-SWCSR). The link weights of the network are updated according to the current network state. Here dijkstra algorithm is used to establish lightpath for shared protection and two times Dijkstra's risk-disjoint path algorithm are used for establishing lightpaths for dedicated protection. After establishing lightpaths, we propose a technique in which router placed at the source which transfers the traffic to the connection node and then the connection node transfers it to the destination. The router calculates the overloaded traffic at the congested node as the difference between the total traffic and the traffic handled. The wavelength allocation is processed based upon the ILP technique and selects cost function as the main criteria. From simulation results we show that this algorithm involves additional capacity in the virtual topology to support survivable routing of connections.