Tibor Bartok
email: tibor.bartok@fumizol.hu

Laszlo Tolgyesi

Akos ; Mesterhazy

Mihaly ; Bartok

Arpad Szecsi

Kromat Ltd

Tibor Bartók

László Tölgyesi

Ákos Mesterházy

Mihály Bartók

Árpád Szécsi

Identification of the first fumonisin mycotoxins with three acyl groups by ESI-ITMS and ESI-TOFMS following RP-HPLC separation: palmitoyl, linoleoyl and oleoyl EFB 1 fumonisin isomers from a solid culture of Fusarium verticillioides

Keywords: Fusarium, mycotoxin, fumonisin isomers, EFB1, ITMS, TOFMS

published or not. The documents may come

Identification of the first fumonisin mycotoxins with three acyl groups by ESI-ITMS and ESI-TOFMS following RP-HPLC separation: palmitoyl, linoleoyl and oleoyl EFB1 fumonisin isomers from a solid culture of Fusarium verticillioides

INTRODUCTION

Fumonisins are structurally related toxic secondary metabolites of fungi, produced primarily by Fusarium species [START_REF] Rheeder | Production of fumonisin analogs by Fusarium species[END_REF], especially F. verticillioides and F. [START_REF] Seifert | The name Fusarium moniliforme should no longer be used[END_REF], which are worldwide pathogens of maize [START_REF] Shephard | Worldwide survey of fumonisin contamination of corn and corn-based products[END_REF]. However, in recent papers the production of some fumonisin B (FB) analogues by Aspergillus niger has also been reported [START_REF] Frisvad | Fumonisin B-2 production by Aspergillus niger[END_REF][START_REF] Noonim | Fumonisin B2 production by Aspergillus niger in Thai coffee beans[END_REF][START_REF] Logrieco | Fumonisin B2 production by Aspergillus niger from grapes and natural occurrence in must[END_REF][START_REF] Mogensen | Production of fumonisin B2 and B4 by Aspergillus niger on grapes and raisins[END_REF]. Fumonisins can cause severe diseases in animals, e.g. leucoencephalomalacia in horses [START_REF] Kellerman | Leukoencephalomalacia in 2 horses induced by oral dosing of fumonisin-B1[END_REF]) and pulmonary oedema and hydrothorax in pigs [START_REF] Colvin | Fumonisin-induced pulmonary-edema and hydrothorax in swine[END_REF][START_REF] Fazekas | Fumonisin B-1 contamination of maize and experimental acute fumonisin toxicosis in pigs[END_REF][START_REF] Zomborszky-Kovács | Investigations into the time-and dose-dependent effect of fumonisin B-1 in order to determine tolerable limit values in pigs[END_REF], and they can produce toxic effects in chickens [START_REF] Ledoux | Fumonisin toxicity in broiler chicks[END_REF] and turkeys [START_REF] Weibking | Fumonisin toxicity in turkey poults[END_REF]). Important data have also been published on the nephrotoxicity [START_REF] Riley | Dietary fumonisin B-1 induces disruption of sphingolipid metabolism in sparguedawley rats -a new mechanism of nephrotoxicity[END_REF], hepatotoxicity and hepatocarcinogenicity [START_REF] Gelderblom | Toxicity and carcinogenicity of the Fusarium moniliforme metabolite, fumonisin-B1, in rats[END_REF] of FB 1 toxin in laboratory experimental rodents.

Although not yet conclusively proved, the consumption of fumonisin-contaminated maize and maize-based foods (at levels of 1-10 mg kg -1 ) has been linked with the promotion of human primary liver cancer [START_REF] Ueno | Fumonisins as a possible contributory risk factor for primary liver cancer. A 3-year study of corn harvested in Haimen, China, by HPLC and ELISA[END_REF]) and statistically with human oesophageal cancer in rural areas in different countries [START_REF] Rheeder | Fusarium moniliforme and fumonisins in corn in relation to human esophageal cancer in Transkei[END_REF][START_REF] Yoshizawa | Fumonisin occurrence in corn from high-risk and low-risk areas for human esophageal cancer in China[END_REF][START_REF] Doko | Incidence and levels of fumonisin contamination in maize genotypes grown in Europe and Africa[END_REF][START_REF] Shephard | Natural occurrence of fumonisins in corn from Iran[END_REF]. Fumonisins are regarded by the International Agency for Research on Cancer (IARC) as group 2B carcinogens to humans (IARC 2002).

Fumonisins are characterized by a 19-20 carbon atom long amino-polyhydroxyalkyl chain, which is generally diesterified at the hydroxy groups on C-14 and C-15 with a terminal carboxyl group of propane-1,2,3-tricarboxylic acid (tricarballylic acid, TCA) [START_REF] Rheeder | Production of fumonisin analogs by Fusarium species[END_REF], but in some minor fumonisins the esterification involves other organic acids, such as cis-aconitic acid, oxalsuccinic acid and oxalfumaric acid [START_REF] Bartók | Detection of new fumonisin mycotoxins and fumonisin-like compounds by reversed-phase highperformance liquid chromatography/electrospray ionization ion trap mass spectrometry[END_REF][START_REF] Bartók | A new type of fumonisin series appeared on the scene of food and feed safety[END_REF]. Partially hydrolysed (e.g. PHFB 1 ) and fully hydrolysed fumonisins (e.g. HFB 1 ) have also been described [START_REF] Rheeder | Production of fumonisin analogs by Fusarium species[END_REF][START_REF] Bartók | Detection of new fumonisin mycotoxins and fumonisin-like compounds by reversed-phase highperformance liquid chromatography/electrospray ionization ion trap mass spectrometry[END_REF][START_REF] Bartók | A new type of fumonisin series appeared on the scene of food and feed safety[END_REF]. In partially hydrolysed fumonisins, the backbone is monoesterified, while in fully hydrolysed compounds (usually formed during nixtamalization of maize, baking and frying of food products or by alkaline hydrolysis in the laboratory) there is no esterifying agent on the backbone. Depending on their chemical structures, the fumonisins can be classified into four main groups (FA, FB, FC and FP); the toxicologically most important ones being the FB analogues [START_REF] Rheeder | Production of fumonisin analogs by Fusarium species[END_REF], primarily because the FB analogues, and especially FB 1 toxin (Fig. 1), can be found in the highest concentration in maize and maize-based food-and feedstuffs [START_REF] Stack | Analysis of fumonisin B-1 and its hydrolysis product in tortillas[END_REF], and the free primary amine group on C-2 contributes significantly to the toxicity of the FB analogues [START_REF] Bolger | in: Safety evaluation of certain mycotoxins in food, Edited by the Fifty-sixth meeting of the Joint 13 FAO/WHO Expert Committee on Food Additives (JECFA)[END_REF][START_REF] Lemke | Deamination of fumonisin B-1 and biological assessment of reaction product toxicity[END_REF]. The first fumonisins isolated and identified in 1988, were FB 1 and FB 2 toxin [START_REF] Bezuidenhout | Structure elucidation of the fumonisins, mycotoxins from Fusarium moniliforme[END_REF]). The amine group in the FA analogues is acetylated. The structure of the FC analogues is similar to that of the FB analogues, without the C-1 methyl group. The most recently described group of fumonisins comprises the FP analogues, in which a 3-hydroxypyridine moiety can be found on C-2 [START_REF] Musser | Identification of a new series of fumonisins containing 3-hydroxypyridine[END_REF].

HPLC/ESI

MATERIALS AND METHODS

Chemicals

The FB 1 standard and methanol (MeOH, gradient grade) were purchased from Sigma-Aldrich Ltd. (Budapest, Hungary). Acetonitrile (MeCN, hypergrade) was from Merck Ltd (Budapest, Hungary). Purified water with a resistivity of 18 MΩ was delivered with a Nanopure II (Barnstead/Thermolyne Co., Dubuque, IA, USA) water purification device.

Culturing of Fusarium verticillioides and extraction of fumonisins produced

A Fusarium verticillioides isolate acquired from maize stalk (isolate no. Fv 16) was identified via its macro-and micromorphological characteristics and grown on a solid rice culture as described earlier [START_REF] Bartók | Detection of new fumonisin mycotoxins and fumonisin-like compounds by reversed-phase highperformance liquid chromatography/electrospray ionization ion trap mass spectrometry[END_REF][START_REF] Bartók | Detection and characterization of twenty-eight isomers of fumonisin B1 (FB1) mycotoxin in a solid rice culture infected with Fusarium verticillioides by reversed-phase high-performance liquid chromatography/electrospray ionization timeof-flight and ion trap mass spectrometry[END_REF]. It was demonstrated in those reports that this isolate has a good fumonisin-producing capability, yielding 18.27 mg g -1 FB 1 toxin. The freeze-dried culture material containing fumonisins was extracted with a mixture of MeOH/H 2 O (75/25, v/v), using a high-speed homogenizer UltraTurrax T25 (IKA, Staufen, Germany) at 9500 rpm for 4 min. After extraction, and centrifugation (10000xg for 10 min), the supernatant was filtered through a PTFE membrane (0.2 µm) into an HPLC autosampler vial and was subsequently analysed with the instruments detailed below.

RP-HPLC/ESI-ITMS and RP-HPLC/ESI-TOFMS analyses of fumonisins

The instrumental parameters were described in detail recently [START_REF] Bartók | Detection and characterization of twenty-eight isomers of fumonisin B1 (FB1) mycotoxin in a solid rice culture infected with Fusarium verticillioides by reversed-phase high-performance liquid chromatography/electrospray ionization timeof-flight and ion trap mass spectrometry[END_REF].

Briefly, the fumonisins extracted from the solid rice culture material were analysed by 50/50 (v/v). The quantitative evaluation of the new compounds by using ESTD calibration of FB 1 provided only approximate data, because the polarities of the detected new fumonisins are very different from that of FB 1 ; naturally, the ionization of the new compounds is assumed, but is not known to be the same as that for FB 1 .

RESULTS AND DISCUSSION

Thanks to their outstanding sensitivity in full scan mode, mass spectrometers equipped with IT mass analysers are eminently suitable for the detection and partial identification of new secondary metabolites (e.g. mycotoxins) and their isomers [START_REF] Josephs | Detection and characterization of fumonisin mycotoxins by liquid chromatography electrospray ionization using ion trap and triple quadrupole mass spectrometry[END_REF] . 2006, 2008, 2010). As illustrated by the MS 2 spectrum of FB 1 toxin (Fig. 2), the product ion spectra of the molecular ions ([M+H] + ) of fumonisins are highly characteristic; in other words, it is easy to decide almost at a glance whether or not a given product ion spectrum is produced by a fumonisin. In most fumonisins, the backbone is esterified by two organic acid molecules (most often TCA), and accordingly the product ion spectra contain three groups of fragment ions (indicated by 1, 2 and 3 in Fig. 2). The first group of fragment ions consists of the dehydrated molecular ions, the second is the [M+H-TCA] + group and the third is the [M+H-2TCA] + group. It is characteristic of the product ion spectra of the fumonisins that, within a given product ion group, there is a difference of 18 Da between the masses of the neighboring ions, corresponding to the splitting-off of one H 2 O molecule from the larger molecular or fragment ion. The difference between the m/z values of the corresponding ions of the neighboring product ion groups yields the molar mass of the organic acid esterifying the backbone (TCA or, in the case of a few minor fumonisins, cis-aconitic acid, oxalfumaric acid or oxalsuccinic acid) [START_REF] Bartók | Detection of new fumonisin mycotoxins and fumonisin-like compounds by reversed-phase highperformance liquid chromatography/electrospray ionization ion trap mass spectrometry[END_REF][START_REF] Bartók | A new type of fumonisin series appeared on the scene of food and feed safety[END_REF]. In the course of our earlier HPLC/ESI-ITMS studies these characteristics indicated that isolates of Fusarium verticilliodes produce as yet unpublished fumonisins of higher molecular mass. Under the given experimental conditions, these fumonisins were eluted from the HPLC column at close to 100% MeCN, demonstrating that these components are considerably more apolar than other fumonisins so far described. The m/z values of the fragment ions in the MS 2 spectra, including the hydrocarbon backbone at m/z 299, revealed that the structures of these new fumonisins are highly similar to that of FB 1 toxin, except for the presence of additional functional groups. We assumed that the new substituents might be carboxylic acids esterifying the free OH groups of the fumonisin backbone, carboxylic acids that had not been identified on the fumonisin backbone. We were earlier unable to identify these Three research groups had previously mentioned application of the TOFMS technique in fumonisin research, but neither of them utilized the procedure for the analysis of fumonisin isomers [START_REF] Lemke | Deamination of fumonisin B-1 and biological assessment of reaction product toxicity[END_REF][START_REF] Senyuva | Identification of fumonisin B-2, HT-2 toxin, patulin and zearalenone in dried figs by liquid chromatography-time-of-flight mass spectrometry and liquid chromatography-mass spectrometry[END_REF][START_REF] Mogensen | Production of fumonisin B2 and B4 by Aspergillus niger on grapes and raisins[END_REF].

We recently verified the usefulness of exact mass measurement by TOFMS during the identification of new FB 1 isomers [START_REF] Bartók | Detection and characterization of twenty-eight isomers of fumonisin B1 (FB1) mycotoxin in a solid rice culture infected with Fusarium verticillioides by reversed-phase high-performance liquid chromatography/electrospray ionization timeof-flight and ion trap mass spectrometry[END_REF]. Since the HPLC equipment used in these TOFMS measurements was different from that used in earlier ITMS analyses, slightly different retention times were obtained for the same components. As shown in Tables 1 and2, however, the retention times (relative to FB 1 toxin) of the same components separated in the two different HPLC systems were highly similar. The differences between the retention times relative to FB 1 lay in the range 0.085-0.088. After full scan analysis by RP-HPLC/ESI-TOFMS, the data-processing software (Mass Hunter) of the equipment was asked to produce both the total ion and the extracted ion chromatograms (EICs) at m/z values of 960, 984 and 986 (Fig. 3). Nevertheless, similarly to RP-HPLC/ESI-ITMS, the total ion chromatogram obtained by RP-HPLC/ESI-TOFMS did not display these minor components in addition to the main components (FB 1 , FB 2 , FB 3 and FB 4 ). TOFMS EICs (Fig. 3 (oleic acid, OA). With regard to the currently accepted nomenclature (FB 1 , PHFB 1 (partially hydrolysed FB 1 ) and HFB 1 (fully hydrolysed FB 1 )), the new fumonisins were named esterified FB 1 (EFB 1 ) toxins. The abbreviation at the end of the name (PA, LA or OA) indicates the organic acid, esterifying the third OH group of the fumonisin backbone. Thus, the suggested names of the six new identified fumonisins are EFB 1 PA, iso-EFB 1 PA, EFB 1 LA, iso-EFB 1 LA, EFB 1 OA and iso-EFB 1 OA. The mass accuracy (based on the measured and the calculated mass values) of the new EFB 1 toxins was in the range between 0.1 and -1.1 ppm. Data relating to the RP-HPLC/ESI-TOFMS measurements are listed in Table 1.

Our TOFMS measurements confirmed that the signals of the new fragment ion groups (4, 5 and 6) in the MS 2 spectra obtained by ITMS are due to the presence of the third organic acid on the fumonisin backbone (Fig. 4). The experimental data obtained by ITMS allow conclusions that complement the fragmentation pathways published earlier [START_REF] Bartók | Detection of new fumonisin mycotoxins and fumonisin-like compounds by reversed-phase highperformance liquid chromatography/electrospray ionization ion trap mass spectrometry[END_REF][START_REF] Bartók | Detection and characterization of twenty-eight isomers of fumonisin B1 (FB1) mycotoxin in a solid rice culture infected with Fusarium verticillioides by reversed-phase high-performance liquid chromatography/electrospray ionization timeof-flight and ion trap mass spectrometry[END_REF]. Figure 5a-c spectra of the molecular ions of the newly detected fumonisins differ markedly from those of previously published fumonisins (Fig. 4): for the new fumonisins, there are six groups of fragment ions instead of the three characteristic of the MS 2 spectra of the molecular ions ([M+H] + ) of most fumonisins (Figs 2 and4). Secondly, from the six groups of fragment ions, the ions (m/z values) of groups 4, 5 and 6 are also present in the groups of fragment ions of the mass spectra of the FB 1 toxin and its isomers (1-3 in Fig. 2) [START_REF] Bartók | Detection and characterization of twenty-eight isomers of fumonisin B1 (FB1) mycotoxin in a solid rice culture infected with Fusarium verticillioides by reversed-phase high-performance liquid chromatography/electrospray ionization timeof-flight and ion trap mass spectrometry[END_REF]). The explanation seems obvious: in the MS fragmentation of EFB 1 -type fumonisins, the fatty acid or its ketene form is split off the molecule before either of the TCAs, and two of the ions characteristic of the MS 2 spectrum of FB 1 toxin, i.e. the ions at m/z 704 and m/z 722, are produced. From this step on, the theoretical MS fragmentation scheme of the EFB 1 components is identical with that of FB 1 toxin.

Thirdly, it is of diagnostic value that the m/z values of the hydrocarbon backbones detected at the end of the fragmentation in the MS 2 spectra of the molecular ions of the newly detected fumonisins (299 Da) are identical with the m/z value of the hydrocarbon backbone in the mass spectra of FB 1 toxin and its isomers. From the predominant directions of fragmentation, the example of a fragmentation previously unknown among fumonisins is shown in Fig. 6 for EFB 1 LA (C-10 is the presumed esterification site for the LA). The fragmentation patterns are similar for the other EFB 1 s and for the iso-EFB 1 components. It follows from the structures of the new esterified fumonisins that groups modifying the backbone are split off in the course of fragmentation, i.e. C-O and C-N bond scission leads to the elimination of H 2 O, organic acids (TCA, LA, OA or PA) and NH 3 . From the product ions formed as a result of fragmentation, it is clear that TCA can also be eliminated in a stepwise manner, while H 2 O is released with the concomitant 7). The splitting-off of TCA and the new fatty acids (LA, OA or PA) esterifying the backbone in the form of their ketene (TCAK 158 Da, LAK 262 Da, OAK 264 Da and PAK 238 Da, Fig. 7) was also observed, as can be seen in the theoretical fragmentation pathways (Fig. 5a-c) and the MS 2 spectra (Fig. 4). The MS 2 spectra permit, the following general observations: (i) the ions produced by the fragmentation of LA, OA or PA were most abundant; (ii) the product ions with the lowest abundance were those formed by the splitting-off of 2TCA;

(iii) the sequence of the groups of fragment ions according to abundances is 4>2>5>6≥1>3 for EFB 1 and 4>5>6>1≥2>3 for iso-EFB 1 . The characteristic data (retention time, retention time relative to FB 1 , quantity relative to FB 1 and MS 2 spectral information on the molecular ions) for the EFB 1 compounds, obtained by RP-HPLC/ESI-ITMS, are detailed in Table 2. The relative quantities (% of FB 1 ) of the new fumonisins were in the range 0.003-0.036%. Their total amount was 0.1% of the FB 1 concentration, which may be rated as significant when it is considered that these new components are much more apolar than earlier-described fumonisins, and their uptake into and toxicity elicited in the various tissues of living organisms may therefore also be significantly different from those of other fumonisins.

The experimental results presented in this article clearly revealed that the parallel use of two hyphenated techniques (RP-HPLC/ESI-ITMS and RP-HPLC/ESI-TOFMS) was essential for identification of new type of fumonisins with three acyl groups, i.e. there are situations when a single hyphenated technique is not sufficient for the identification of a new compound. Of course, neither procedure could determine the relative and absolute configurations of the new fumonisins. In order to elucidate the structures of these toxins, other spectroscopic techniques, such as NMR, XRD and ORD, must be used. However,

  -MS and MS/MS techniques with different types and different combinations of mass analysers have become popular in fumonisin analysis. The most significant advantages of these hyphenated procedures for the analysis of fumonisins are their selectivity and sensitivity, and the fact that, in contrast with UV or fluorescence detection, there is no need for derivatization (pre-or post-column) (Zöllner and Mayer-Helm 2006). The aim of this study was to apply reversed-phase high-performance liquid chromatography/electrospray ionization -ion trap and time-of-flight mass spectrometry (RP-HPLC/ESI-ITMS and RP-HPLC/ESI-TOFMS) to investigate and characterize six new, higher molecular weight FB analogues of fumonisins (three pairs of isomers with different m/z values) extracted from a Fusarium verticillioides-infected solid rice culture.

  first report on the detection of fumonisins in which, besides two TCA moieties, there is a third esterifying agent in the molecule.

  /ESI-ITMS and also RP-HPLC/ESI-TOFMS at two research locations, where different Agilent (Santa Clara, CA, USA) HPLC systems (1090 Series II with DR5 binary pump and 1200 Series with binary pump) were attached to the mass spectrometers. Since the dead volume of the flow path of the 1200 Series HPLC system applied is higher than that of the 1090 Series II HPLC, the pulse damper from the 1200 Series pump was removed in order to decrease the retention time differences for the fumonisins on the two HPLC systems. A YMC-Pack J'sphere ODS H80 (YMC Europe GmbH, Dinslaken, Germany) (250 mm x 2.1 mm, 4 µm) HPLC column and a flat (24% B to 40% B in 79 min, then increased to 100% B in 15 min) linear binary gradient of H 2 O (A) and MeCN (B) (each supplemented with 0.1% (v/v) formic acid) were applied at a flow rate of 0.2 ml min -1 for the separation of the compounds. Mass spectrometric detection was performed with a Varian (Palo Alto, CA, USA) 500MS IT, and on Agilent 6210 TOF mass spectrometers. Both mass spectrometers were equipped with ESI ion sources and operated in positive ion mode. Relative quantitation (% of FB 1 ) of the new compounds was performed by ESI-ITMS, using an external standard (ESTD) method in a 5 order of magnitude concentration range of an FB 1 calibration standard dissolved in MeCN/H 2 O

  ITMS (lack of exact mass measurement). However, component identification following RP-HPLC separation was achieved by using an ESI-MS instrument equipped with a TOF mass analyser suitable for exact mass measurement.

  ) and ITMS EICs (chromatogram not shown), however, unambiguously indicated six new fumonisins in the retention time range 90.623-91.928 min and 89.324-90.569 min, respectively, i.e. two components at each of three different m/z values. The leading suggestions of the Mass Hunter software for all six fumonisins were the following empirical formulae (unprotonated) and the corresponding exact mass values ([

  depicts theoretically possible pathways for the fragmentation of the newly detected fumonisins. Of these theoretically possible reaction pathways, dominant routes can be suggested by comparison of the m/z values of the MS 2 spectra shown in Figs 4 and5a-c. No experiments were performed to address fragmentations depending on the CID energy, and it is therefore not possible to distinguish the roles of kinetic and thermodynamic parameters at this point. It is currently assumed that, the main fragmentation pathways can be characterized by the abundances of the ions in the product ion spectra. The experimental data mentioned above draw features regarding the dominant fragmentation pathways. Firstly, it is immediately apparent that the fragmentation patterns (abundance systems) of the MS 2

  corresponding anhydride (TCAD 158 Da, Fig.

Figure 1 .Figure 2 .Figure 3 .Figure 4 .Figure 6 .Figure 7 .

 123467 Figure 1. Structure of FB1 toxin. 41x14mm (600 x 600 DPI)

  M+H] + ): C 50 H 89 NO 16 (960.62541); C 52 H 89 NO 16 (984.62541) and C 52 H 91 NO 16 (986.64106). Subtraction of the empirical formula of FB 1 C 34 H 59 NO 15 ) from these empirical formulae, followed by addition of the H 2 O removed from a OH group of the fumonisin backbone and the organic acid molecules in the course of esterification, yielded the empirical formulae of the organic (fatty) acids esterifying the third OH group of the backbone of the FB 1 toxin, i.e. C 16 H 32 O 2 (palmitic acid, PA), C 18 H 32 O 2 (linoleic acid, LA) and C 18 H 34 O 2

	toxin (
	F o
	r
	P
	e e r
	R e v i e w
	O n
	l y
	9

Table 1 .

 1 Characteristic data obtained by RP-HPLC/ESI-TOFMS on new esterified FB 1 (EFB 1 ) isomers.

	Compound name	Retention time (min)	Retention time relative to FB1	Empirical formula (unprotonated)	(calculated) Exact mass of [M+H] +	(measured) Exact mass of [M+H] +	Mass accuracy (ppm)
	EFB1 LA (1) 90.623 6.809 C52H89NO16 984.6254 984.6243 -1.1
	iso-EFB1 LA (2) 90.852 6.827 C52H89NO16 984.6254 984.6248 -0.6
	EFB1 PA (3) 91.482 6.875 C50H89NO16 960.6254 960.6259	0.5
	iso-EFB1 PA (4) 91.670 6.890 C50H89NO16 960.6254 960.6255	0.1
	EFB1 OA (5) 91.732 6.895 C52H91NO16 986.6411 986.6412	0.1
	iso-EFB1 OA (6) 91.928 6.909 C52H91NO16 986.6411 986.6412	0.1

http://mc.manuscriptcentral.com/tfac Email: fac@tandf.co.ukFood Additives and Contaminants

Acknowledgements

Financial support was provided by EC (KBBE-2007-22269-2 MYCORED) and Hungarian State Research (OTKA 77612) grants.


Roberto Cominetti

Cristóbal Guzmán
email: cguzman@gatech.edu

Network Congestion Control with Markovian Multipath Routing

In this paper we consider an integrated model for TCP/IP protocols with multipath routing. The model combines a Network Utility Maximization for rate control based on end-to-end queuing delays, with a Markovian Traffic Equilibrium for routing based on total expected delays. We prove the existence of a unique equilibrium state which is characterized as the solution of an unconstrained strictly convex program. A distributed algorithm for solving this optimization problem is proposed, with a brief discussion of how it can be implemented by adapting the current Internet protocols.

I. INTRODUCTION

Routing and congestion control are basic components of packet-switched communication networks. While routing is responsible for determining efficient paths along which the sources communicate to their corresponding receivers, congestion control manages the transmission rate of each source in order to keep network congestion within reasonable limits. In current practice both mechanisms belong to separate design layers that operate on different time-scales: the IP layer (Internet Protocol) determines single-path routings which are updated on a slow time-scale, while the TCP layer (Transmission Control Protocol) corresponds to end-to-end users that perform rate congestion control at a faster pace for which routing can be considered to be fixed. Scalability considerations impose that these protocols must operate in a decentralized manner.

Roughly speaking, TCP controls the rate of a source by managing a window size that bounds the maximum Partially supported by FONDECYT 1100046 and Instituto Milenio Sistemas Complejos de Ingeniería.

This research was done while the second author was a student of Departmento de Ingeniería Matemática, Universidad de Chile. number of outstanding packets that have been transmitted

but not yet acknowledged by the receiver. Once this window size is reached the source must wait for an acknowledgment before sending a new packet, so the rate is approximately one window of packets per roundtrip time. As the network gets congested, the round-trip time increases and the transmission rate is automatically slowed down. In addition, TCP dynamically adjusts the window size of a source in response to network congestion. To this end, links generate a scalar measure of their own congestion (e.g. packet loss probability, average queue length, queueing delay) and each source is fed back a congestion signal that reflects the aggregate congestion of the links along its route. This signal is used by the source to adjust its window size so that the higher the congestion the smaller the rate. The predominant TCP protocols in use are Tahoe and Reno which use packet loss as congestion measure, and Vegas which is based on queuing delay. We refer to [START_REF] Low | Internet congestion control[END_REF] for a description and comparison of current protocols and their models.

The interaction of many sources performing a decentralized congestion control based on feedback signals that are subject to estimation errors and communication delays, gives rise to complex dynamics that are difficult to analyze. However, assuming that the dynamics stabilize on a steady state, the equilibrium can be characterized as an optimal solution of a Network Utility Maximization (NUM) problem (see [START_REF] Kelly | Rate control for communication networks: shadow prices, proportional fairness and stability[END_REF], [START_REF] Yaïche | A game theoretic framework for rate allocation and charging of available bit rate (abr) connections in atm networks[END_REF], [START_REF] Low | A duality model of tcp and queue management algorithms[END_REF]). Thus, the TCP mechanism can be viewed as a decentralized algorithm that seeks to optimize an aggregate utility function subject to network constraints. The NUM approach also allows to compare different protocols in regard to their fairness and efficiency.

A second element of packet-switched networks is routing. This function is performed by routers in a decentralized manner using routing tables that determine the next hop for each destination. The routing tables are updated periodically by an asynchronous Dijkstra-type iteration that computes optimal paths according to some metric such as hop count, latency, delay, load, reliability, bandwidth, or a mixture of these. In current practice a single path that minimizes the number of hops is used for routing on each origin-destination pair. Research has also considered multipath routing strategies to improve performance by exploiting the available transmission capacity on a set of alternative paths. The first paper on multipath routing was [START_REF] Gallager | A minimum delay routing algorithm using distributed computation[END_REF] which developed a distributed routing algorithm minimizing total delay in the case of flow dependent latencies but with fixed source rates. For the case of TCP rates that depend on network congestion, the model presented in [START_REF] Kelly | Rate control for communication networks: shadow prices, proportional fairness and stability[END_REF] and further developed in [START_REF] Lin | Utility maximization for communication networks with multipath routing[END_REF], also considered a multipath routing but performed directly by sources. Since distributed routing has scalability advantages, a router-based approach to multipath routing with elastic demands was investigated in [START_REF] Paganini | Congestion control with adaptive multipath routing based on optimization[END_REF] and [START_REF] Mallada | Optimal congestion control with multipath routing using tcp-fast and a variant of rip[END_REF].

In addition to increased efficiency, a further argument in favor of multipath routing is stability. Indeed, when route choice is based on metrics that are affected by congestion, such as queuing delay or link latencies, routing and rate control become mutually inter-dependent and equilibrium can be achieved only if both aspects are considered jointly: routing affects the rate control through the induced congestion signals, while rate control induces flows that determine in turn which routes are optimal. If routing is restricted to a single path, congestion effects may lead to route flaps. A remedy for such unstable behavior is to allow flows to split over multiple paths in order to balance their loads. An appropriate tool to capture these interactions between rate control and routing is provided by Wardrop equilibrium. On the other hand, since congestion metrics are subject to estimation errors and random effects it is natural to model routing as a stochastic equilibrium assignment.

The goal of this paper is to propose an analytical framework that provides a theoretical support for crosslayer designs for rate control under a router-based multipath routing. Our model combines rate control modeled by NUM, with a routing strategy based on discrete choice distribution models that lead to a Markovian Traffic Equilibrium (MTE). The latter is a decentralized stochastic version of Wardrop's model. The combination of the NUM and MTE models leads to a system of equations that correspond to the optimality conditions of an equivalent Markovian Network Utility Maximization problem (MNUM), a strictly convex unconstrained program of low dimension where the variables are the link congestion prices. This characterization allows to establish the existence and uniqueness of an equilibrium, and provides a basis for designing decentralized protocols for congestion control with multipath routing.

The paper is structured as follows. Section §II reviews the basic components of our cross-layer approach: we recall the NUM framework for modeling the steady state of TCP protocols and we discuss the concepts of Wardrop equilibrium and Markovian routing. Section §III combines NUM and MTE, introducing the MNUM model for routing and rate control. In §III-A we reduce MNUM to a system of equations involving only the link congestion prices, and then in §III-B we show that these equations admit a variational characterization (D-MNUM) proving the existence of a unique equilibrium state. In §IV we briefly discuss how the model might lead to a cross-layer design of a distributed TCP/IP protocol. We close the paper with comparisons to previous work and some perspectives on future research.

II. NOTATIONS AND PRELIMINARIES

The communication network is modeled by a directed graph G = (N, A), where the nodes i ∈ N represent origins, destinations and intermediate routers, while the arcs a ∈ A represent the network links. Each link is characterized by a latency λ a = s a (w a ) = λ 0 a + ψ a (w a ) where λ 0 a ≥ 0 represents a constant propagation delay and p a = ψ a (w a ) is the expected queuing delay expressed as a continuous and strictly increasing function ψ a : [0, c a ) → [0, ∞) of the traffic w a on the link, with ψ a (0) = 0 and c a ∈ (0, ∞]. We also consider a finite set of sources k ∈ K each one generating a flow rate x k ≥ 0 from an origin s k ∈ N to a destination d k ∈ N .

A. Rate control and utility maximization under single path routing

Suppose that each source k ∈ K routes its flow along a fixed sequence of links (a 1 , . . . , a j k ), so that the total traffic on a link a is w a = k a x k where the summation is over all the sources k ∈ K whose route contains that link. Consider the queuing delay p a = ψ a (w a ) as a measure of link congestion and assume that each source k ∈ K adjusts its rate x k as a decreasing function of the aggregate queuing delay q k = a∈k p a on its route, namely x k = f k (q k ), where f k : (0, ∞) → (0, ∞) is continuous and strictly decreasing with f k (q k ) → 0 as q k → ∞. These equilibrium equations may be written as

f -1 k (x k ) = q k = a∈k p a = a∈k ψ a (w a ) = a∈k ψ a ( s a x s )
which correspond to the optimality conditions for the strictly convex minimization problem

(NUM) min x∈R K a∈A Ψ a ( s a x s ) - k∈K U k (x k )
where

Ψ a (•) denotes a primitive of ψ a (•) and U k (•) a primitive of f -1 k (•).
Alternatively, the equations may be stated in terms of the queuing delays as

ψ -1 a (p a ) = w a = k a x k = k a f k (q k ) = k a f k ( b∈k p b )
which correspond to the optimality conditions for the strictly convex dual problem

(D-NUM) min p∈R A a∈A pa 0 ψ -1 a (y) dy - k∈K F k ( b∈k p b )
where

F k (•) is a primitive of f k (•).
EXAMPLE. Consider the model for TCP Vegas proposed in [START_REF] Low | Understanding vegas: a duality model[END_REF], [START_REF] Low | A duality model of tcp and queue management algorithms[END_REF]. For each source k and time t, let W k t denote the size of the congestion window and T k t = D k + q k t the RTT expressed as the sum of the total propagation delay D k and the queueing delay q k t . A Vegas source estimates D k as the minimum observed RTT in a time window, and tries to keep the difference between the expected rate xk t = W k t /D k and the actual rate

x k t = W k t /T k t close to a given value α k > 0. To this end, the congestion window is increased if xk t -x k t < α k , and decreased when xk t -x k t > α k . At equilibrium we must have xk -x k = α k which yields the equilibrium rate functions x k = α k D k q k f k (q k ).
A simple model for the queuing delay can be obtained if we assume that each link has a service capacity c a > 0 and an infinite buffer, so that an M/M/1 model gives the expected queuing delay

p a = w a c a (c a -w a )
ψ a (w a ).

The (NUM) formalism can handle other congestion measures different from the queuing delay and has been used to model the steady state of different TCP protocols, each one characterized by specific maps f k and ψ a (see [START_REF] Low | Internet congestion control[END_REF], [START_REF] Kelly | Rate control for communication networks: shadow prices, proportional fairness and stability[END_REF], [START_REF] Gibbens | Resource pricing and the evolution of congestion control[END_REF], [START_REF] Padhye | Modeling tcp reno performance: a simple model and its empirical validation[END_REF], [START_REF] Dumas | A markovian analysis of additive-increase multiplicative-decrease (aimd) algorithms[END_REF], [START_REF] Kunniyur | End-to-end congestion control schemes: utility functions, random losses and ecn marks[END_REF]).

B. Routing and traffic equilibrium

We review next some equilibrium models for traffic in congested networks. In this setting the source flows x k are fixed but may be routed along a set of alternative paths R k connecting the origin s k to the destination d k .

The basic modeling principle introduced by Wardrop in [START_REF] Wardrop | Some theoretical aspects of road traffic research[END_REF] is that at equilibrium only paths that are optimal should be used to route flow. We stress that, in contrast with rate control which is based solely on the queuing delays p a = ψ a (w a ), route optimality will be measured using the total delays λ a = λ 0 a + ψ a (w a ). 1) Wardrop equilibrium: Suppose that the flow x k is split into non-negative path-flows h r ≥ 0 so that x k = r∈R k h r , and let w a = r a h r be the induced total link-flows. Let H denote the set of such feasible flows (h, w). An equilibrium [START_REF] Wardrop | Some theoretical aspects of road traffic research[END_REF] is characterized by the fact that only optimal paths are used, namely, for each destination k ∈ K and each route r ∈ R k one has

h r > 0 ⇒ c r = τ k (1)
where c r = a∈r λ a = a∈r s a (w a ) denotes the total delay of the route and τ k = min r∈R k c r is the minimum cost faced by source k. These equilibria were characterized in [START_REF] Beckman | Studies in Economics of Transportation[END_REF] as the optimal solutions of the convex program

(P-W) min (h,w)∈H a∈A wa 0 s a (z) dz.
Since the feasible set H is compact this problem has optimal solutions, while strict convexity implies that the optimal w is unique. Alternatively, the equilibrium delays λ a = s a (w a ) are the unique optimal solution of the strictly convex unconstrained dual problem where λ 0 a = s a (0) and τ k (λ) min r∈R k a∈r λ a is the minimum total delay for source k ∈ K.

(D-W) min λ∈R A a∈A λa λ 0 a s -1 a (z) dz - k∈K x k τ k (λ)
2) Markovian routing and equilibrium: When link delays are subject to stochastic variability, the route delays cr become random variables and the equilibrium conditions (1) are replaced by a stochastic assignment of the form h r = x k P(c r is optimal). For instance, if the costs cr are i.i.d. Gumbel variables with expected value c r = E(c r ), we get the Logit distribution rule common in the transportation literature

h r = x k exp(-βc r ) p∈R k exp(-βc p ) (∀ r ∈ R k )
which assigns flow to all the paths, favoring those with smaller expected cost c r . The parameter β controls how concentrated is the repartition: for β ∼ 0 every path receives an approximately equal share of the flow, while for β large the flow concentrates on paths with minimal cost. Unfortunately, such route-based distribution rules are not amenable to design decentralized scalable protocols. An alternative is to conceive routing as a stochastic dynamic programming process. Suppose that each packet experiences a random delay λa when traversing link a, and let τ k i be a random variable that represents the total delay from node i to destination d k . Denote λ a = E( λa ) and τ k i = E(τ k i ) their expected values. If a packet at node i is routed through the link a ∈ A + i we have τ k i = λa + τ k ja , so that a shortest path routing should choose the link with smallest λa + τ k ja . Unfortunately, while the link delays λa for a ∈ A + i might be observed at node i, this is not the case for the τ k ja 's which depend on future delays that will be experienced when traversing the downstream links. Suppose instead that only the expected values τ k ja are known and available at node i and that each packet from source k ∈ K observes the λa 's and is routed through the link a ∈ A + i that minimizes zk

a = λa + τ k ja i φ k i } { A + i A - i a∈A - i v k a a∈A + i v k a x k
P k ij = P(E k a ) if ij = a 0 otherwise (2)
for i = d k , while the destination d k is an absorbing state.

The expected flows correspond to the invariant measures of these Markov chains, leading to a flow distribution rule in which the throughput flow φ k i from source k that enters node i, splits among the links a ∈ A + i according to (see Figure 2)

v k a = φ k i P(E k a ). (3)
The throughputs

φ k = (φ k i ) i =d k can be computed from the stationary equations φ k = ∞ j=0 [( P k ) ] j δ k x k
, where P k = (P k ij ) i,j =d k is the reduced transition matrix on the non-absorbing states, and δ k i = 1 for i = s k and δ k i = 0 otherwise. This may also be written as φ k = x k δ k + ( P k ) φ k which corresponds to the standard flow conservation equations

φ k i = x k δ k i + a∈A - i v k a . (4)
These equations can be restated in compact form using expected utility theory. Namely, let us write zk a = z k a + k a as the sum of its expected value z k a = λ a + τ k ja plus a noise k a with E( k a ) = 0, and assume that the distribution of k a does not change with z k a (for a discussion of this assumption see §VI). Then, the transition probabilities in (2) can be expressed as

P(E k a ) = ∂ϕ k i ∂z k a (z k ) where ϕ k i
denote the expected utility functions

ϕ k i (z k ) = E( min a∈A + i {z k a + k a }) if i = d k 0 if i = d k (5)
which allow to rewrite the flow equations ( 3)-( 4) as

   v k a = φ k i ∂ϕ k i ∂z k a (z k ) ∀a ∈ A + i φ k i = x k δ k i + a∈A - i v k a ∀i = d k . (6)
On the other hand, assuming that the cost-to-go variables {τ k ja : a ∈ A + i } are independent from the local queueing times { λa : a ∈ A + i }, we may compute the expected value of τ k i by conditioning on the events E k a as

τ k i = E(τ k i ) = a∈A + i E( λa + τ k ja |E k a )P(E k a ) = a∈A + i E( λa + τ k ja |E k a )P(E k a ) = E( min a∈A + i { λa + τ k ja }) so that τ k i = ϕ k i (z k ) ∀i ∈ N z k a = λ a + τ k ja ∀a ∈ A. (7)
Under mild conditions it was proved in [START_REF] Baillon | Markovian traffic equilibrium[END_REF] that, given the λ a 's, system ( 6)-( 7) has a unique solution (v, φ, τ, z). It was also shown that these equations, together with the equilibrium conditions λ a = s a (w a ) where w a = k∈K v k a represents the total expected link load, have a unique solution (λ, w, v, φ, τ, z) called a Markovian Traffic Equilibrium (MTE). This equilibrium is characterized by a pair of dual optimization problems analog to (P-W) and (D-W). As a matter of fact, the dual problem has exactly the same form (D-MTE)

λ∈R A a∈A λa λ 0 a ψ -1 a (z) dz - k∈K x k τ k (λ)
where τ k (λ) τ k s k (λ) with τ k i (λ) the solution of [START_REF] Paganini | Congestion control with adaptive multipath routing based on optimization[END_REF]. The expected utility maps ϕ k i (•) convey all the information required to describe a Markovian routing and may be considered as the primary modeling objects. These maps are determined by the random variables k a which are ultimately tied to the arc random costs λa . However, the class E of maps that can be expressed in the form (5) admits an analytic characterization (see [START_REF] Baillon | Markovian traffic equilibrium[END_REF]): they are the C 1 maps ϕ : R n → R that are concave, componentwise non-decreasing, and which satisfy in addition (a) ϕ(x 1 + c, . . . , x n + c) = ϕ(x 1 , . . . , x n ) + c (b) ϕ(x) → x i when x j → ∞ for all j = i (c) for x i fixed, ∂ϕ ∂xi (x 1 , . . . , x n ) is a continuous distribution function on the remaining variables.

We remark also that ϕ(x) ≤ min{x 1 , . . . , x n }. In what follows we assume the model is specified directly in terms of a family of maps ϕ k i ∈ E with ϕ k d k ≡ 0, though they are not used explicitly by our distributed protocol in §IV.

REMARK. Since packet movements are governed by a

Markov chain, cycling may occur and additional conditions are required to ensure that packets reach the destination with probability one. A simple case is when at node i source k considers only the arcs in A + i that lead closer to destination d k (e.g. τ k ja < τ k ia ), so that the corresponding Markov chain is supported over an acyclic graph (N, A k ). To deal with this case it suffices to redefine

ϕ k i (z k ) E( min a∈A k+ i {z k a + k a }) so that P k ij = ∂ϕ k i ∂z k a (z k ) = 0 for all a = ij ∈ A k+ i .

III. RATE CONTROL WITH MARKOVIAN ROUTING

We proceed to develop a cross-layer model that combines a NUM approach for rate control based on queuing delays, with a Markovian multipath routing based on total delays. Each source k ∈ K is characterized by an origin s k , a destination d k , and a continuous decreasing rate function

f k : (0, ∞) → (0, ∞) such that f k (q k ) → 0 when q k → ∞, while every link a ∈ A has a continuous increasing latency function s a : [0, c a ) → [λ 0 a , ∞) with λ 0 a = s a (0) ≥ 0.
Packets are routed according to a Markovian strategy characterized by a family of maps ϕ k i ∈ E with ϕ k d k ≡ 0, and sources adjust their rates as a function x k = f k (q k ) of the total queuing delay q k = τ k (λ)τ 0 k , where τ k (λ) is the end-to-end expected delay as defined in the previous section and τ 0 k = τ k (λ 0 ) is the free-flow value of this end-to-end delay.

Informally, the source rates x k induce flows v k a and total link loads w a . These loads determine link expected delays λ a = s a (w a ) that yield end-to-end delays τ k (λ) for each source and corresponding queuing delays q k . At equilibrium, these queuing delays must induce the original rates x k = f k (q k ).

Definition 1: A pair (w, x) with w = (w a ) a∈A and x = (x k ) k∈K is called a Markovian Network Utility Maximization (MNUM) equilibrium iff w a = k∈K v k a where (v k , φ k ) solve the flow conservation constraints ( 6) with (τ k , z k ) satisfying ( 7), together with the link delay relations λ a = s a (w a ) and the rate equilibrium conditions

x k = f k (q k ) where q k = τ k (λ) -τ 0 k .

A. Reduced formulation of MNUM

In order to establish the existence and uniqueness of equilibria we begin by reducing MNUM to an equivalent set of equations that involves only the variables λ. To this end we need to extend the results in [START_REF] Baillon | Markovian traffic equilibrium[END_REF]. We omitted in this publication full proofs, but we refer to [START_REF] Cominetti | Network Congestion Control with Markovian Multipath Routing[END_REF] for them. Consider a fixed non-negative link delay vector (λ a ) a∈A . We first show that [START_REF] Paganini | Congestion control with adaptive multipath routing based on optimization[END_REF] uniquely defines z k and τ k as implicit functions of λ. This system can be equivalently stated solely in terms of the variables τ k as

τ k i = ϕ k i (λ a + τ k ja ) a∈A (8)
so it suffices to prove that the latter uniquely defines τ k as a function of λ. Proposition 1: Let k ∈ K and denote τ k i the cost of a shortest path from i to destination d k with link costs λ a . Suppose also that τ k ∈ R N is such that

τ k i ≤ ϕ k i ((λ a + τ k ja ) a∈A ) (∀ i ∈ N ). (9)
Then τ k ≤ τ k and moreover, starting from τ k,0 = τ k , the iterates computed by

τ k,n+1 i = ϕ k i ((λ a + τ k,n ja ) a∈A ) (10)
are non-increasing and converge for n → ∞ to a solution τ k of ( 8) with

τ k i ∈ [τ k i , τ k i ].
REMARK. Observe that if we know ϕ k i , the previous result gives a procedure to solve (8): compute the shortest path delays τ k and then iterate [START_REF] Gibbens | Resource pricing and the evolution of congestion control[END_REF]. Alternatively one may start from τ k,0 = τ k in which case the iterates increase and are bounded from above by τ k , hence these iterates also converge to a solution of [START_REF] Mallada | Optimal congestion control with multipath routing using tcp-fast and a variant of rip[END_REF].

We present next an extension of a result from [START_REF] Baillon | Markovian traffic equilibrium[END_REF] which is the basis to prove uniqueness. In what follows we denote P the open convex domain of all λ ∈ R A for which there exists τ k ∈ R K satisfying

τ k i < ϕ k i ((λ a + τ k ja ) a∈A ) for all i = d k . (11)
Note that if λ ∈ P then λ ∈ P for all λ ≥ λ. Lemma 1: Let λ ∈ P and suppose that (τ k , z k ) solves [START_REF] Paganini | Congestion control with adaptive multipath routing based on optimization[END_REF]. Let Qk (z k ) be the matrix with entries Qk ia (z k ) = 6) has a unique solution given by

∂ϕ k i ∂z k a (z k ) for i = d k and a ∈ A. Then (a) For each i = d k there exists j ∈ N such that P k ij > 0 and τ k j -τ k j > τ k i -τ k i . (b) The matrix [I -P k (z k )] is invertible. (c) Equation (
v k = Qk (z k ) φ k ≥ 0 with φ k = [I -P k (z k ) ] -1 δ k x k ≥ 0.
The next result is the key to reduce the MNUM equations to a system in the variables λ.

Proposition 2: If λ ∈ P then, for each source k ∈ K, the system (7) has a unique solution z k = z k (λ) > 0 and τ k = τ k (λ) > 0. Moreover, the functions λ → τ k i (λ) and λ → z k a (λ) are concave, smooth and component-wise non-decreasing.

The implicit maps τ k (λ) and z k (λ) defined by [START_REF] Paganini | Congestion control with adaptive multipath routing based on optimization[END_REF], allow to restate the MNUM equations solely in terms of the link delay vector λ. Indeed, let

q k (λ) = τ k s k (λ) -τ 0 k and define xk (λ) = f k (q k (λ)).
According to Lemma 1(c) the equations ( 6) have unique solutions

v k = v k (λ) and φ k = φ k (λ). Denoting wa (λ) = k∈K v k a (λ)
, the MNUM equations are equivalent to the reduced system of equations (R-MNUM) λ a = s a ( wa (λ)) ∀a ∈ A.

B. Variational characterization

We show that the reduced system (R-MNUM) corresponds to the optimality conditions of an optimization problem which is a combination of the variational characterizations (D-NUM) and (D-MTE).

Theorem 1: Assume that λ 0 ∈ P. Then (x * , w * ) is an MNUM equilibium iff x * = x(λ * ) and w * = w(λ * ) where λ * is the unique optimal solution of the strictly convex program (D-MNUM)

min λ∈P Φ(λ) a∈A λa λ 0 a s -1 a (z) dz - k∈K F k (q k (λ)) with F k (•) a primitive of f k (•).
This characterization allows us to prove the existence and uniqueness of an MNUM equilibrium.

Theorem 2: Problem (D-MNUM) is strictly convex and coercive, hence it has a unique optimal solution and therefore there exists a unique MNUM equilibrium.

IV. A DISTRIBUTED ALGORITHM FOR MNUM

This section describes how the MNUM framework can lead to a distributed protocol for rate congestion control under Markovian multipath routing. This protocol can be interpreted as a distributed algorithm that solves the variational problem (D-MNUM). The algorithm is based on a Markovian routing process for packets, with a slow update of the end-to-end expected delays τ k i 's. This process is combined with a fast TCP adaptation of user's rates by estimating the end-to-end queuing delays to reach the equilibrium rates xk (λ). A more detailed description and analysis of the distributed protocol will be the subject of a forthcoming paper [START_REF] Guzmán | Implementation of a distributed protocol for network congestion control with markovian multipath routing[END_REF].

A. Packet routing based on local queues

We adapt the ideas of §II-B2 in order to define a routing policy based on local information. To do this, router i needs to observe the values zk a = λa +τ k ja of each outgoing link a ∈ A + i by adding the link propagation delay λ 0 a , plus the current queueing delay pa of the link, plus the estimate of the expected delay τ k ja informed by the next hop.

Routers must periodically provide their neighboring routers with an estimate of the total expected delays τ k i . These estimates may be updated on a slow time-scale by averaging the observed delays min a∈A + i { λa + τ k ja } over all packets routed on a fixed time window or a fixed number of packets. The observed average τ k i is used to update the estimate of the expected delay as

τ k i ← (1 -α)τ k i + ατ k i .

B. TCP protocol

A TCP protocol for source rate control requires a consistent feedback congestion signal. Basically, we require a mechanism by which every source k can estimate q k (λ).

Here we rely on the two time-scales assumption: sources control their rates at a much faster pace than routers, so they see link delays as constant. For fixed expected delays λ, the expected forward time coincides with τ k s k (λ), thus using standard protocols for estimating the forward time, users can get an unbiased estimation T k t of this total expected delay.

Finally, we need to compute the free-flow total expected delay τ 0 k . Since the maps ϕ k i (•) are not known explicitly, it is not possible to solve the equations [START_REF] Paganini | Congestion control with adaptive multipath routing based on optimization[END_REF] directly. We propose to estimate τ 0 k by the minimum observed time for every packet, as in the single-path implementation of Vegas. This provides a biased lower bound estimate for τ 0 k . The free-flow times τ 0 k together with the unbiased estimators T k t of τ k s k for every packet t arriving to destination, can be used to adjust the rates by a stochastic approximation algorithm of the form

x k t+1 ← (1 -δ)x k t + δf k (Q k t ) (12)
where Q k t = T k t -τ 0 k . If we let sources adapt long enough so that Q k t ∼ q k and x k t ∼ f k (q k ), we can then proceed to update the router estimates of the end-to-end delays τ k i . Further considerations on how multipath routing affects buffering at the destination and other issues will be addressed in [START_REF] Guzmán | Implementation of a distributed protocol for network congestion control with markovian multipath routing[END_REF].

V. COMPARISON WITH PREVIOUS WORK

As mentioned in the Introduction there have been several proposals to develop multipath routing protocols, such as [START_REF] Gallager | A minimum delay routing algorithm using distributed computation[END_REF], [START_REF] Kelly | Rate control for communication networks: shadow prices, proportional fairness and stability[END_REF] and [START_REF] Lin | Utility maximization for communication networks with multipath routing[END_REF]. However, our work is more closely connected to [START_REF] Paganini | Congestion control with adaptive multipath routing based on optimization[END_REF], [START_REF] Mallada | Optimal congestion control with multipath routing using tcp-fast and a variant of rip[END_REF] which describes an approach for rate congestion control under a distributed multipath routing protocol based on routing proportions (α k a ) a∈A + i that control the routing of packets from source k at node i. These proportions are dynamically adjusted so that eventually the routing concentrates over the links a ∈ A + i that belong to shortest expected paths. From a conceptual point of view there are two main differences between this approach and ours. Firstly, the proportion-based approach makes routing decisions based on expected values, while our splitting of traffic evolves stochastically as it uses the current state of local queues to optimize the routing. A second difference is that [START_REF] Paganini | Congestion control with adaptive multipath routing based on optimization[END_REF], [START_REF] Mallada | Optimal congestion control with multipath routing using tcp-fast and a variant of rip[END_REF] optimize routing in terms of queuing delay only, while our routing optimization considers the total delay including queuing plus propagation delay. This choice makes sense if one cares about the total time that packets take to be transmitted, and not just the time spent in queues.

Further differences arise at the implementation level. The protocol in [START_REF] Paganini | Congestion control with adaptive multipath routing based on optimization[END_REF], [START_REF] Mallada | Optimal congestion control with multipath routing using tcp-fast and a variant of rip[END_REF] requires three time-scales: a fast TCP rate adaptation, a medium time-scale for route price updates, and a slow update for flow-splitting proportions. This time-scale separation is required to justify the convergence of the protocol. In our case we only need two time-scales: a slow one for estimating the total delays to destinations and a fast one for TCP rate control and routing.

Finally, in terms of information and communication overhead both implementations are similar, with the difference that in our case we require a fast interaction with local queues in order to choose the best route.

VI. CONCLUSIONS AND FUTURE WORK

We proposed a new cross-layering model for TCP/IP control under multipath routing. The motivation for our routing mechanism comes from using local information about queueing delays as well as the expected delays from the next hops to the destination, in order to exploit the available capacity by sending packets through several alternative routes. To achieve this purpose, we considered a Markovian routing combined with a Vegas-like TCP protocol for rate control. The routing process was characterized by studying the expected dynamic programming equations which lead to a Markovian Traffic Equilibrium, together with a standard Network Utility Maximization model for the TCP steady state. This led to a variational characterization of the equilibrium that allowed to prove its existence and uniqueness, and which inspired a distributed protocol for attaining the equilibrium.

There are several unsolved issues. Firstly, further research is required to provide a theoretical support for the convergence of these protocols. A detailed analysis should study the relation between the packet-level dynamics and our flow-level model. Our equilibrium model relies on this assumption: namely, we base our updates on aggregated flow information as well as in the two time-scales convergence of equilibrium flows. A complete analysis should explain to which extent the flow model captures the packet level dynamics, and how fast the equilibrium flows are attained by sources. Interesting recent results along this line can be found in [START_REF] Walton | Proportional fairness and its relationship with multi-class queueing networks[END_REF], [START_REF] Kelly | Resource pooling in congested networks: proportional fairness and product form[END_REF].

Another interesting question is related to the model of randomness assumed. We considered an additive structure zk a = z k a + k a which presumes the same variability of delays regardless of the average flow levels observed. A more realistic model should consider higher variability for higher expected delays, based either on a detailed analysis of the distribution of waiting times at queues, or at least using a simplified multiplicative randomness model of the form zk a = z k a (1 + k a ). These sophisticated models would justify the use of the minimum observed delay for τ 0 k , since when there is no congestion at all, we can safely assume zero variability of travel times.

A final line of research has to do with simulating this protocol in a realistic environment. A fair comparison with single-path routing requires the presence of uncertainty and delays in information transmission. Simulation may provide an idea on the effective increase in performance that one might expect from a Markovian multipath routing.

Fig. 1 .

 1 Fig. 1. Variables for dynamic programming equations

Fig. 2 .

 2 Fig. 2. Flow conservation diagram (here i s k


Maël Le Treust
email: mael.letreust@lss.supelec.fr

Samson Lasaulce
email: samson.lasaulce@lss.supelec.fr

Resilient Source Coding

This paper provides a source coding theorem for multi-dimensional information signals when, at a given instant, the distribution associated with one arbitrary component of the signal to be compressed is not known and a side information is available at the destination. This new framework appears to be both of information-theoretical and game-theoretical interest : it provides a new type of constraints to compress an information source; it is useful for designing certain types of mediators in games and characterize utility regions for games with signals.

Regarding the latter aspect, we apply the derived source coding theorem to the prisoner's dilemma and the battle of the sexes.

I. INTRODUCTION

Shannon has shown [START_REF] Shannon | A mathematical theory of communication[END_REF] that it is possible to describe without any loss a discrete random variable x ∈ X (representing an information source) provided that H(x) bits per information source sample are used, H(x) being the entropy of the random variable x. This result holds for a stationary source that is, the distribution of x, say P (•) ∈ ∆(X ), does not vary over time. In [START_REF] Dobrušin | Individual methods for transmission of information for discrete channels without memory and messages with independent components[END_REF], [START_REF] Dobrušin | Unified methods of optimal quantizing of messages[END_REF], Dobrušin introduced a generalized version of this problem where the source distribution can vary. In such a situation, the source distribution P (•|s) ∈ ∆(X ) can vary from sample to sample, depending on the parameter or state s ∈ S. This problem, which is referred to as the problem of arbitrary varying sources, has been solved in [START_REF] Berger | The source coding game[END_REF]. In [START_REF] Gallager | Source coding with side information and universal coding[END_REF] the author solve the problem of arbitrary varying sources when the sequence of states s n = (s 1 , s 2 , ..., s n ) is known to the destination (i.e., the decoder). The problem of arbitrarily varying source (AVS) is different to the one of universal source coding (USC), even if in both situations the encoder and decoder do not know the right distribution P (•) ∈ ∆(X ) of x. Indeed, the distribution probability of the symbols is constant for the USC problem but vary from stage to stage for the AVS problem. A further generalization of this work has been done in [START_REF] Ahlswede | Coloring hypergraphs: A new approach to multi-user source coding, part 1[END_REF] and [START_REF] Ahlswede | Coloring hypergraphs: A new approach to multi-user source coding, part 2[END_REF]. Indeed, the latter references deal with the scenario of two correlated sources either in the case where the destination is informed with the sequence of states or the case where it is not known. The work reported in this paper is precisely related to the scenario of two arbitrary varying correlated sources with an uninformed destination; this scenario is described by Fig. 1. For this scenario, which is motivated next, the achievable rate region in [START_REF] Ahlswede | Coloring hypergraphs: A new approach to multi-user source coding, part 1[END_REF] is characterized for the family of information sources satisfying an entropy positiveness condition: ∀s ∈ S, H(x(s)|y(s)) × H(y(s)|x(s)) > 0, [START_REF] Ahlswede | Coloring hypergraphs: A new approach to multi-user source coding, part 1[END_REF] where S is the set of possible states, x(s) and y(s) represent the two information sources to be encoded when the state is s ∈ S.

One of our contributions is to show that the condition (1) can be replaced with another mathematical condition which is fully relevant in dynamic games (at least in discrete-time dynamic games). The proposed condition is relevant in any game where an entity (a mediator typically) has to encode the action profiles of the game into messages intended for players having a certain observation structure. Considering that the relevant entity has to encode a sequence of action profiles, the proposed condition consists in assuming that at most one player can change his distribution in an arbitrary manner during the course of the game (single deviations) whereas the other do not change their strategy. One of the motivations for deriving coding schemes which are resilient [START_REF] Halpern | Beyond Nash equilibrium: Solution concepts for the 21st century[END_REF] to single deviations is therefore to consider the following class of relevant game-theoretic scenarios. This class consists of dynamic games with signals (the game is played several times and players do not observe the actions played perfectly) in which an exogenous entity (see Fig 2) sends an additive signal so that players obtain better observations. More motivations for considering this type of scenarios can be found in [START_REF] Treust | The price of re-establishing almost perfect monitoring in games with arbitrary monitoring structures[END_REF].

s n P C 1 C 2 D x n y n m 1 m 2 (x n , ŷn )

II. MAIN TECHNICAL RESULT

A. Definitions and closest existing result

In this section, we consider an information source, represented by Fig. 1, where the symbols are drawn with a distribution which may vary from one stage to another in an arbitrary manner. Denote by S the set of states, X , Y two sets of symbols and P (•|s) ∈ ∆(X × Y); s ∈ S the distribution of the pair of random variables (x, y) when the state is s ∈ S; the set ∆(E) denotes the set or probability distributions on the generic set E that is, the unit simplex associated with E. For every sequence of states s n ∈ S n , define the probability distribution of the source sequence (x n , y n ):

∀s n ∈ S n , P (x n , y n |s n ) = n t=1 P (x(t), y(t)|s(t)). (2)
The arbitrary varying correlated source (AVCS) is defined by the conditional probability P (x, y|s) and by the set of possible sequences {s n } of source states. The component x (resp. y) of the correlated source is received by the first (resp. second) encoder C 1 (resp. C 2 ). Both encoders want to transmit their source component to the receiver. Our goal is to construct a joint code for which the error probability is upper-bounded in every state sequence s n ∈ S n . Definition 1: Define an (n, M 1 , M 2 )-code as a triple of functions

f 1 : X n -→ M 1 , (3)
f 2 : Y n -→ M 2 , (4)
g 2 : M 1 × M 2 -→ X n × Y n (5)
where

M i = {1, 2, ..., M i }, i ∈ {1, 2}.
With each code is associated an error criterion which has to be minimized. Define the error probability P n e associated to each (n, M 1 , M 2 )-code as follows:

P n e = max s n ∈S n P ((x n , y n ) = (x n , ŷn )|s n ). ( 6
)
Definition 2: A rate pair (R 1 , R 2 ) is achievable if for all ε > 0, there exists an (n, M 1 , M 2 )-code such that :

log M 1 n ≤ R 1 + ε, (7)
log M 2 n ≤ R 2 + ε, (8)
P n e ≤ ε. (9)
Denote by R the set of achievable rates. Theorem 3 (Ahlswede [START_REF] Ahlswede | Coloring hypergraphs: A new approach to multi-user source coding, part 1[END_REF], [START_REF] Ahlswede | Coloring hypergraphs: A new approach to multi-user source coding, part 2[END_REF]): Assume that the arbitrary varying correlated source satisfies the entropy positiveness condition :

∈ S, H(x(s)|y(s)) × H(y(s)|x(s)) > 0. ( 10
)
Then the achievable rate region R equals the following rate region:

R 1 ≥ sup Ps∈∆(S) H(x(s)|y(s)), R 2 ≥ sup Ps∈∆(S) H(y(s)|x(s)), R 1 + R 2 ≥ sup Ps∈∆(S) H(x(s), y(s)),
where the supremum is taken over the probability distributions P s ∈ ∆(S). This characterization is not valid in general if we remove the entropy positiveness condition. In the following section, we consider a special but important class of information sources satisfying the orthogonal deviation condition presented in definition 5. We will see that this assumption allows us to get rid of the entropy positiveness condition.

B. A new result

We investigate a class of arbitrary varying sources as described in Fig. 2 for which the entropy positiveness condition [START_REF] Slepian | Noiseless coding of correlated information sources[END_REF] is replaced with the orthogonal deviation condition (12). The information source under investigation falls into the class of AVCS because the decoder observes a sequence y n of side information correlated with x n . Our main result concerns the source of vector of information x = (x 1 , . . . , x K ) ∈ X .

Theorem 4:

Let P k (•|s) ∈ ∆(X k ), k ∈ K, s ∈ S the family of source distributions of x k , k ∈ K and : ∆(X ) -→ ∆(Y)
R ⋆ = max k∈K max x k ∈X k H(x -k |y x k ) + log χ k , (11)
is achievable for the source x = (x 1 , . . . , x K ) and there is no lossless coding scheme providing a better rate. The proof of this theorem is not trivial and a sketch is provided in section III. The purpose of what follows is to explain the notations used in the above theorem and its meaning.

x n 1 D x n 2 x n 3 x n k . . . . . . x n K C x n = (x n 1 , . . . , x n K ) xn y n m Fig. 2. The information vector x = (x k ) k∈K ∈ X = k∈K X k is drawn with the family of probability distribution P k (•|s) ∈ ∆(X k ), k ∈ K, s ∈
S which depend on the state parameter s ∈ S. The decoder observes a side information y drawn from the transition probability (y|x). The encoder C encodes a sequence of symbols x n and send a message m of minimal cardinality M to the decoder D such as reconstruct the sequence of symbols xn with an error probability arbitrarily small.

Consider a family of sets (X k ) k∈K and a family of distributions P k ∈ ∆(X k ) over each component k ∈ K. Denote X = k∈K ∆(X k ) the product of sets; P ∈ ∆(X ) the product probability defined by P = k∈K P k and P -k ∈ ∆(X -k ) the probability defined by P -k = j =k P j where the k's component has been removed.

The information source x we consider is a vector x = (x 1 , . . . , x K ) of random variables. A sequence of state of the source s n ∈ S n is a sequence of probability distribution over one component j ∈ K of the vector x n = (x n 1 , . . . , x n K ). Definition 5: An arbitrarily varying source of information satisfies the orthogonal deviation condition if the source of information is vectorial x = (x 1 , . . . , x K ) and the set of sates S n is defined by the equation (12).

S n = ∪ k∈K ∆(X k ) ⊗n (12)
Consider for example, the sequence s n = (Q j (1), . . . , Q j (n)) ∈ S n of distributions over the component j ∈ K of the vector x n = (x n 1 , . . . , x n K ) of information. At stage 1 ≤ t ≤ n the symbol x j (t) is drawn according to Q j (t) ∈ ∆(X j ) whereas the other symbols x k (t) are drawn i.i.d. according to the probability distribution P k ∈ ∆(X k ).

Hence, the vector of information x(t) is drawn, at stage t ≥ 1, according to the following probability distribution:

P (x 1 , . . . , x j , . . . , x K |s) = [P 1 ⊗ . . . ⊗ Q j (t) ⊗ . . . ⊗ P K ](x).
We consider the situation where the decoder has a side information. It observes, through a transition probability : X -→ ∆(Y), a degraded version y of the source symbols x. The orthogonal deviation condition allow the transition probability to be deterministic. In such a case, the entropy positiveness condition is not satisfied. Then we conclude that conditions [START_REF] Slepian | Noiseless coding of correlated information sources[END_REF] and (12) are disjoint.

Definition 6: Define (n, M )-code as a triple of functions

f : X n -→ M, (13) g
: M × Y n -→ X n . ( 14
)
Each code is associated with an error criterion which aims at being minimized. Define the error probability P n e associated to each (n, M )-code as follows:

P n e = max s n ∈S n P ((x n , y n ) = (x n , ŷn )|s n ). ( 15
)
Definition 7: A rate R is achievable if for all ε > 0, there exists a (n, M )-code such that:

log M n ≤ R + ε, (16)
P n e ≤ ε. (17)
Denote R ⋆ the infimum of achievable rates R.

For each component k ∈ K, define the associated graph G k . Definition 8: The graph G k = (X k , E k ) is defined as follows. The source symbols x k ∈ X k are the vertex of the graph and there is an edges e = (x k , x ′ k ) ∈ E k between two vertices if and only if:

∃x -k ∈ Supp P -k , ∃y ∈ Y, ∃δ > 0, s.t. , min( (y|x k , x -k ), (y|x ′ k , x -k )) ≥ δ.
Let C be a set of colors. A coloring of the graph G k is a function φ k : X k -→ C that satisfies:

e = (x k , x ′ k ) ∈ E k , =⇒ φ k (x k ) = φ k (x ′ k ).
Definition 9: The chromatic number χ k of the graph G k is the cardinality of the minimal coloring of the graph G k . Denote x k : X -k -→ ∆(Y) the marginal transition probability of over the set of signal Y when fixing the symbol x k ∈ X k .

x k : X -k -→ ∆(Y), (18) x -k -→ x k (y|x -k ) = (y|x k , x -k ). (19
) Denote y x k the random signal drawn from the transition x k . The definitions of χ k and y x k are introduced to evaluate the optimal rate R ⋆ defined by the equation [START_REF] Treust | The price of re-establishing almost perfect monitoring in games with arbitrary monitoring structures[END_REF].

In the following sections, we provide a sketch of the proof of the theorem 4 (Sec. III) and we apply the derived results to two famous games (Sec. IV). Note that the theorem 4 holds for mixed strategies and when realizations of the game action profiles are i.i.d. The Shannon theory literature comprises tools [START_REF] Han | Information-spectrum methods in information theory[END_REF] to extend the theorem 4 to more general setups (e.g., sources with memory or strategies with recall).

III. SCKETCH OF PROOF OF THE THEOREM

In this section, we present a sketch of the proof of theorem 4 which will be completely detailed in a separate paper. This section is divided in two parts called the achievability and the converse.

A. Achievability

The achievability consists in providing codes that achieves the rate R ⋆ . We construct a coding scheme based on graph coloring and statistical tests. Two points should be considered carefully. First, it is possible that the sequence of side information y n provides relevant information to the decoder, for some sequence of state of the source. Second, the coding scheme of Slepian and Wolf [START_REF] Slepian | Noiseless coding of correlated information sources[END_REF] is not feasible. Indeed, the transition probability generating the side information is controlled by the symbols x k ∈ X k of each component k ∈ K whose probability distribution P k ∈ ∆(X k ) is not necessarily known.

The coding scheme. The encoder performs a statistical test to determine the component k ∈ K whose sequence of symbols x k ∈ X k is the least typical for the distribution P k ∈ ∆(X k ).

The sequence of symbols x n k ∈ X n k of the component k ∈ K will be encoded using the coloring of the corresponding graph G k . The coloring property of definition 8 implies that the sequence of side information y n and the sequence of colors c n characterize a unique sequence of symbols x n k ∈ X n k . Other components x n -k ∈ X n -k will be encoded according to the transition probability and the sequence x n k . We construct a partition ( X k , X c k ) of the set of symbols X k . If the symbol x k ∈ X k is often used (partition X k ), the sequence of signals s n

x k , driven by the marginal probability x k , is long enough to use a source coding with side information of Slepian and Wolf [START_REF] Slepian | Noiseless coding of correlated information sources[END_REF]. Otherwise (partition X c k ), the information x -k ∈ X -k must be encoded directly, without any compression. The result of [START_REF] Slepian | Noiseless coding of correlated information sources[END_REF] states that the sequence of components x -k ∈ X -k can be recovered by the decoder with an arbitrarily small error probability.

Evaluation of the rate of the code. For each ε > 0, there exists a n1 ∈ N such that the probability of error of the coding scheme of Slepian and Wolf [START_REF] Slepian | Noiseless coding of correlated information sources[END_REF]

is bounded by ε > 0. Let n2 > log |K|+ n1|Xk| log |A -k | ε
. We show that for all n ≥ n2 ∈ N, the rate of the code is bounded by the following quantity:

log M n = log |K| • χ n k • |X -k | x k ∈ X k nx k n + log x k ∈ X c k 2 nx k (H(x -k |y x k )+2ε) n ≤ log |K| n + log χ k + n1 | X k | n log |X -k | (20) + x k ∈ X c k n x k n (H(x -k |y x k ) + 2ε) ≤ max x k ∈X k H(x -k |y x k ) + log χ k (21) + log |K| + n1 |X k | log |X -k | n + 2ε ≤ max k∈K max x k ∈X k H(x -k |y x k ) + log χ k + 3ε = R ⋆ + 3ε. ( 22
)
We provide a sequence of such that the error probability can be made arbitrarily small and in the same time the rate of the code is upper bounded by R ⋆ + 3ε.

B. Converse

In the converse, we show that no code whose rate is less than R ⋆ is reliable (the error probability is lower bounded away from zero). To show the converse, we assume that the optimal rate R ⋆ is less than the following quantity:

R ⋆ < max k∈K max x k ∈X k H(x -k |y x k ) + log χ k . ( 23
)
Suppose the maximum in equation ( 11) is reached for the component k ∈ K and symbol xk ∈ X k . The probability distribution of the vector of actions x = (x 1 , . . . , x K ) is the product of marginal distributions of each component x k ∈ X k with k ∈ K. The optimum rate R ⋆ is then written as the sum of rates of the components R ⋆ = k∈K R ⋆ k . The converse is divided into two parts.

First, assume that the encoding scheme has a rate R ⋆ k < log χ k . By the property of the minimum coloring, the same color c k can be generated by two different actions xk ∈ X k and xk ′ ∈ X k . Then, the probability of error tends to 1 as n tends to infinity.

Second, suppose that the sequence x n k is fully reconstructed by the player that decodes but the rate R ⋆ -k satisfies:

R ⋆ -k < H sx k (x -k |y x k ) = max x k ∈X k H(x -k |y x k ). ( 24
)
In this case, the result of Slepian and Wolf [START_REF] Slepian | Noiseless coding of correlated information sources[END_REF] ensures that the probability of error tends to 1 when the sequence of states s n k = xn k and n tends to infinity.

IV. APPLICATION TO GAMES

The results provided so far can be applied to any discretetime dynamic game an arbitrary observation structure. We consider the cases of the prisoner's dilemma and the battle of sexes. The information source to be compressed/encoded (by a mediator) is the action profile of the game. The destination (i.e., the decoder) is given by the set of players who observe the played actions through a certain observation structure. So far, we have been assuming that the communication links between the mediator and the players is perfect. Here we assume that each link from the mediator to a given player has a certain capacity denoted by C 0 .

The strategic form of the prisoner's dilemma is defined by :

G = (K, (A k ) k∈K , (u k ) k∈K ) ( 25
)
where K is the set of players |K| = 2, A k is their discrete action sets A 1 = {T, B} and A 2 = {L, R} whereas u k is the utility function of player k ∈ K such that :

u k : A 1 × A 2 -→ R, k ∈ K. (26)
For the prisoner's dilemma, the utility function writes as the tale of Fig. 3. When player 1 plays B and player 2 plays L, the utility of player 1 is 4 and the one of player 2 is 0. Suppose that the player play according to a probability distribution P ∈ ∆(A 1 ) × ∆(A 2 ) (mixed strategies). The problem is to evaluate the rate associated with the information source (generating the action profiles) knowing that one of the players is potentially deviating using a different probability distribution. Also suppose that the destination of the communication system has a degraded version s n of the source sequence a n from a transition probability:

3, 3 0, 4 4, 0 1, 1 T B L R
: A -→ ∆(S), (27)
where

A = A 1 × A 2 .
Numerical results. In order to illustrate the above result, we need to fix a transition probability from the set of actions to a set of signals {s 1 , s 2 , s 3 , s 4 }. The transition probability is defined as follows. When the action (T, L) is played, the signal of the decoder is drawn from the probability distribution described by Fig. 5. More precisely, the probability of observing the right signal s 1 (which corresponds to the actions (T, L)) equals 1 -3 4 ε whereas the probability of observing another signal (s 2 , s 3 or s 4 ) is equal to 1 4 ε. The parameter ε ∈ [0, 1] allows us to compare both situations:

J 2 J 1 J 2 J 1 C 0 a n 2 a n 1 a n = (a n 1 , a n 2 ) ân = (â n 1 , ân 2 ) ân = (â n 1 , ân 2 ) s n s n v n z n
Fig. 4. Players J 1 and J 2 observe, through , a noisy version s n of the sequence of actions a n = (a n 1 , . . . , a n K ). The encoder C transmits, through the channel 0 , the sequence of encoded actions a n to the players J 1 and J 2 . The players recover the sequence of past actions ân = a n with an error probability arbitrarily small if and only if the rate R ⋆ of the source is less than the capacity C 0 of the channel 0 , fixed to 1.7 bit per second.

when ε = 0, the actions a = (a 1 , a 2 ) ∈ A are perfectly recovered and when ε = 1, the signal do not provide any relevant information. When the action profile (T, R) (resp. (B, L) or (B, R)) is played the corresponding signal s 2 (resp. s 3 or s 4 ) is also drawn with probability 1 -3 4 ε whereas the other signals are drawn with probability 4 ε.

1 -3 4 ε 1 4 ε 1 4 ε 1 4 ε s 1 s 2 s 3 s 4
T B L R G 1 G 2
Fig. 6. The graphs G 1 and G 2 of the players for ε > 0. When ε = 0, there is no edges in both graphs.

As soon as ε > 0 the graph the players are described in Fig. 6. Note that if ε > 0 the coloring of both graphs is of cardinality of 2 and thus log χ 1 = log χ 2 = 1. If ε = 0 the pair of graphs have no edges.

We evaluate the rate of such a source in order to transmit the sequence of actions. However, the transmission of the source of information over a channel is not always feasible. A natural question arises and is illustrated by figure 4. Is it possible to transmit the source of action profiles through a channel with fixed capacity C 0 ? Recall that the source of information a with side information s can be transmitted reliably over a channel 0 with capacity C 0 , if R ⋆ < C 0 . We evaluate the optimal compression rate thanks to theorem 4.

R ⋆ = max k∈K max a k ∈A k H(a -k |s a k ) + log χ k . (28)
Suppose that the capacity of channel 0 equals C 0 = 1.7 (in bit/symbol or bit/sample)and the parameter ε = 0.5, we will see that only a subset of the feasible utility region can be achieved, for the communication system of Fig. 4, by an i.i.d. strategy (see e.g., Fig. 7 for the game of the prisoner's dilemma). For each pair of mixed actions P 1 ∈ ∆(A 1 ) and P 2 ∈ ∆(A 2 ), we evaluate the rate R ⋆ of encoding the corresponding sequence of actions. If it satisfies the channel capacity condition R ⋆ < C 0 , the sequence of actions can be recovered even if one of the players deviates from P k ∈ ∆(A k ). The Fig. 7 represents the region of utility vectors whose corresponding mixed actions satisfy the channel condition R ⋆ < C 0 .

We consider also the game of the "battle of sexes" whose utility matrices are represented in Fig. 9. For the channel capacity of C 0 = 1.7 bit/symbol and the same transition probability with precision parameter ε = 0.5 (see Fig. 5), we obtain the achievable utility region of Fig. 9.

Remark that in both examples, we consider only mixed strategies. The problem of considering correlated strategies is much more complicated. Indeed, we need to define properly an arbitrary varying source where the actions and the deviations may be correlated. It would be also possible to achieve the same utility vector with various probability distributions. In that case, the optimal admissible rates may belong to an interval. Depending on the formulation of the problem, the capacity constraints may be defined with respect to the lowest or the largest optimal rate associated with a utility vector. In game theory, most of the player's strategy are not generated i.i.d. It should be of interest to extend our results to the case of a information source compatible with the game theoretical strategies using information spectrum methods [START_REF] Han | Information-spectrum methods in information theory[END_REF]. V. CONCLUSION

We have investigate the problem of encoding arbitrary varying correlated sources also considered by Ahlswede in 1980 [START_REF] Ahlswede | Coloring hypergraphs: A new approach to multi-user source coding, part 1[END_REF], [START_REF] Ahlswede | Coloring hypergraphs: A new approach to multi-user source coding, part 2[END_REF]. The "entropy positiveness condition" [START_REF] Slepian | Noiseless coding of correlated information sources[END_REF] is replaced by an "orthogonal deviation condition" (12) over the states of the source. Both conditions are disjoint because there exists some information sources that satisfies one condition without satisfying the other one. The main result characterizes the optimal rate of the source of information and a sketch of the proof is presented. We provide a game-theoretical application of our main result : a characterization of the rate of a source of player's actions in a long run game. Our coding scheme is resilient to any unilateral deviation of the player's strategies. In conclusion, the coding scheme cannot be manipulated along the duration of the game. The coloring techniques of Ahlswede are directly involved in the characterization of the optimal rate of an information source. Achievable utility region for the battle of sexes under capacity constraints.

Fig. 1 .

 1 Fig.1. The pair of source symbols (x, y) ∈ X × Y is drawn from the transition probability P (x, y|s) which depend on a state parameter s ∈ S. This parameter varies from stage to stages in an arbitrarily manner. The encoder C 1 takes a sequence of symbols x n and encode it into a message m 1 . The encoder C 2 takes a sequence of symbols y n and encode it into a message m 2 . The decoder observes the pair of messages m 1 , m 2 and decode a pair of sequence of symbols (x n , ŷn ).

  the transition probability corresponding to the AVS described by Fig 2. The rate :

Fig. 3 .

 3 Fig. 3. The utility matrix of the prisoner's dilemma.

Fig. 5 .

 5 Fig. 5. The transition probability of signals received by the decoder D when the joint action (T, L) is played.

Figure 6

 6 Figure 6 represents the graphs G 1 and G 2 over player's action which correspond to the above transition probability and the definition 8 of Sec. II.

Fig. 7 .

 7 Fig. 7. Achievable utility region for the prisoner's dilemma under capacity constraints.

Fig. 8 .

 8 Fig. 8. The utility matrix of the battle of sexes.

Fig. 9 .

 9 Fig. 9.Achievable utility region for the battle of sexes under capacity constraints.

ACKNOWLEDGMENT

The authors would like to thank Cagatay Dikici for constructive comments.