Performance Analysis of Feedback Suppression Schemes for ...

ISSN: 2277-3754

ISO 9001:2008 Certified International Journal of Engineering and Innovative Technology (IJEIT)

Volume 2, Issue 6, December 2012

Performance Analysis of Feedback Suppression

Schemes for Satellite Network

Thokchom Arvind, Dr. R. Gunasundari

Abstract-- In multicast satellite networks feedback implosion is a major problem. When the number of users transmitting their feedback messages increases it causes a major part of the system resources to be used up by the transmission of the feedback messages. This particular problem limits the scalability of the multicast satellite network. This paper studies an existing scheme for the suppression of feedback message namely the Poker Game based feedback suppression scheme and a new feedback suppression scheme using game theory. In this scheme the users decide independently if they should send a feedback message or not. The decision of the users is modeled using the concepts of game theory. A Bayesian equilibrium condition is studied for a two player game and its extension to N-players and the equilibrium point found out. Then, using simulations results it is proved that the new proposed game-theory based feedback suppression scheme is better in performance than the Poker-game based scheme.

Index Terms-- Bayesian Equilibrium, Feedback Suppression, Game Theory, Satellite Networks.

I. INTRODUCTION Multicast networking and its various applications have become increasingly popular solutions for new suites of Internet products and services. In multicast networking, data is transmitted from one sender to many recipients or from many senders to many recipients through a single transmission. Multicast applications offer many appealing benefits when trying to disseminate information to a large group of users. The most important benefit, perhaps, is the increased multicast bandwidth efficiency over its unicast and broadcast counterparts. It is gaining in importance with the use of multicast in Internet and with the increase in number of satellites. Satellite networks have a large coverage area, rapid network setup and abundant bandwidth especially at higher frequencies. As a result, satellite networks will have a very crucial role for global multicast services. Satellites in the geostationary orbits offer the advantage of multicasting data over large geographical areas without the need to traverse several congested hops with high packet delays. In order to provide reliability, any protocol need to identify any packets which failed to reach the destination. Missing packets are detected and this loss information is sent using a feedback packet to the source which will send a retransmission. This retransmission of lost packets is necessary to satisfy the quality of service (QoS) constraints for data transmission [1], [2], [3]. Like in terrestrial reliable multicast networks, feedback implosion is identified as one of the major problems in satellite multicast. This feedback implosion is a severe

problem which arises whenever a large number of satellite terminals (STs) transmit feedback messages (FBMs) to the satellite. The number of potential feedback messages increase linearly as the number of satellite terminals increase. This increase in the number of feedback messages may lead to a high traffic concentration at the sender, wasted bandwidth, and high processing requirements. Thus, feedback implosion imposes a high requirement to the mechanism for feedback implosion avoidance of feedback suppression. Generally, the proposed solutions to feedback implosion are classified as structure-based or timer-based approaches. Structure-based approaches depend on a designated site to process and filter feedback information. The members of the multicast groups are grouped into clusters and the amount of feedback generated from the groups is filtered. On the contrary, timer-based solutions depend on probabilistic schemes in order to suppress feedback at the source itself. The receivers delay their transmission for feedback for a random amount of time which is either uniformly, beta distributed or exponentially between the current time and the one-way trip to the source [1]. The goal in timer-based approaches is that the group members closer to the source send their feedback sooner which suppresses the feedback messages from members located further. Both the classes of solutions are not without disadvantages.

Game theory is the formal study of conflict and cooperation. Game theoretic concepts apply whenever the actions of several agents are interdependent. These agents may be individuals, groups, firms, or any combination of these. The concepts of game theory provide a language to formulate structure, analyze, and understand strategic scenarios. As a mathematical tool for the decision-maker the strength of game theory is the methodology it provides for structuring and analyzing problems of strategic choice. The process of formally modeling a situation as a game requires the decision-maker to enumerate explicitly the players and their strategic options, and to consider their preferences and reactions. The object of study in game theory is the game, which is a formal model of an interactive situation. It typically involves several players; a game with only one player is usually called a decision problem. The formal definition lays out the players, their preferences, their information, and the strategic actions available to them, and how these influence the outcome. Game can be described formally at various levels of details. Branches of game theory also differ in their assumptions. A central assumption in many variants of game theory is that the players are rational. A rational player is one who always chooses an action which gives the outcome he

405

ISSN: 2277-3754

ISO 9001:2008 Certified

International Journal of Engineering and Innovative Technology (IJEIT)

Volume 2, Issue 6, December 2012

most prefers, given what he expects his opponents to do. There are three major components of a game. They are the players which make the decisions, the strategies which each player follows and the payoff or utility which is a

with feedback priority not greater than ldb suppresses their

feedback and thus the total expected number of feedback

messages EFBM per poll round is given by

measurement function on the possible outcome determined by all the strategies of all the players [4]. Different types of games are used to model various cooperative or competitive situations between rational decision makers. Some of the most widely used game theoretic models are strategic game, repeated game, bargaining game etc. A Strategic Game is an event that occurs only once with each player being unaware of the other player's action. The players choose their action simultaneously and independently. One of the most

EFBM

m

EFBM j 1

(2)

jldb 1

Where ldb is the feedback priority at the dealer receiver; m

is the maximum feedback priority; and 1 represents the

dealer's feedback. Let RXi, j denote a receiver i in group j ,

and Rj be the number of receivers in the group j . The

expected number of feedbacks from group j per poll round

well-known strategic games is Prisoner's Dilemma. EFBM j is obtained as below

Prisoner's Dilemma models a situation in which there are two

Rj

suspects in a major crime held in separate cells.

EFBM j P RXi, j sends a FB

(3)

i 1

II. POKER-GAME-BASED FEEDBACK SUPPRESSION

The Poker-game based feedback suppression algorithm (PFS) was proposed to reduce the number of feedback messages .A point to-multipoint network between a satellite and R direct receivers where a reliable multicast protocol

Where FB represents a feedback.

On choosing exponentially distributed residual timer, the

probability density is given by the below function

fTi,j

ti, j

ei, j eT 1

ti, j

ti, j T

(4)

Where . is a unit step function. Thus, the probability that

operates is considered. We assume that the satellite multicast a packet to all the receivers and based on the channel

conditions, a receiver i is able to estimate the optimum

number of redundancy blocks denoted by li . This number of

redundancy blocks is needed to decode the received packet successfully. In this case, the satellite will want to transmit

lmax number of redundancy blocks in order to be able to

salvage the receiver in the worst channel scenarios. Here,

lmax is the maximum number of redundancy blocks

transmitted by all the receivers. Thus, we have

lmax maxili

(1)

In order for the satellites to obtain lmax , all the receivers

must report their optimum redundancy blocks through feedback message. These feedback messages cause the

the receiver RXi, j sends a feedback message is given by

P

RXi, j

sends a FB

eT 1

e P(T 2D t T ti,j m

Rl

0

k ,l

l j (i, j )( k ,l )

k 1

k,l i, j

l j

T )dti, j

(5)

and

P(Tk,l 2Dk,l

ti, j

l

j

T )dti, j

T eT 1 0

eti, j

1

FDk ,l

ti, j

l j 2

T

tk,l

dtk ,l

(6)

where FDk,l dk,l is the cumulative distribution function of

the one-way transmission delay Dk,l [7].

The

delay

distribution

F d Dk,l

k ,l

is

not

available

at

the

satellite in general; hence a scheme is needed to estimate the

delay distribution. The satellite measure RTTk,l which is

equal to Tk,l 2Dk,l m l T . The parameters m and T

feedback implosion as the number of receivers R increases.

The feedback of the larger number of redundancy blocks have precedence over that of the smaller number of redundancy blocks as the satellite is interested in the maximum

are known to the satellite, RXk,l informs the value of Tk,l and

l to the satellite, and the satellite is thus able to compute the value of Dk,l as given below.

redundancy block lmax . Thus, the feedback suppression

policy based on the priority is given below [7]. 1) The lower-priority feedback is suppressed by the

Dk ,l RTTk,l

ml 2

T Tk ,l

(7)

The satellite collects all the samples for Dk,l and estimates

higher-priority feedback. 2) A receiver will not be able to perceive other receivers'

feedback priority as it is assumed that there is not direct connection among the receivers. 3) The satellite considers only one of the highest-priority

the distribution FDk,l dk,l .The empirical estimate of the

distribution is obtained as

FDk ,l

dk ,l

dk ,l

(8)

feedbacks received. This behavior is observed in a poker game where the cards are dealt to the players but the players do not know the cards

The

distribution

F d Dk,l

k ,l

is

bounded

by

the

condition in Equation (9).

of the other players. An important metric for the PFS

algorithm is the number of feedback messages. The receivers

406

ISSN: 2277-3754

ISO 9001:2008 Certified

International Journal of Engineering and Innovative Technology (IJEIT)

Volume 2, Issue 6, December 2012

F d F d Dk ,l

k ,l

Dk ,l

k ,l

z 1/2

F d 1 F d Dk,l

k ,l

Dk ,l

k ,l

who have lost the same block. If a player does not send an FBM instantly, he has a normalized payoff equal to 1 and no

(9)

Where is the confidence parameter and z 1/2 is the

standard normal percentile [7].

delay, provided that the other player sends an FBM. If both players risk and delay the transmission of the FBM, they both

have a normalized payoff of1 (Di i ) . Here i and Di

are the respective normalized energy and delay costs

III. GAME-THEORY-BASED FEEDBACK SUPPRESSION

respectively. They are given by

i we dE i

(10a)

A star-based network of satellite terminals is Di wd RTTi

(10b)

considered. The STs do not have any direct interconnection and use the uplink channel to send FBMs to the satellite. Furthermore, the multicast information is separated into blocks of k packets and encoded using appropriate coding like Forward Error Correction Code (FEC). The key idea behind

Here dE is the energy consumption when a FBM is sent, i

is the residual battery power of the player i , i =1, 2 at the time

of decision and RTTi is the respective round trip time.

we and wd are the weighing factors which are related to the

the employed coding is that at the sending end k packets of information data are encoded to produce n packets of encoded data, so that any subset of k encoded packets

suffices to reconstruct the information data. Such a n, k

code allows the receivers to recover from up to n k losses

having occurred during the transmission of n encoded

packets. In this analysis, it is assumed that when a ST loses

respective costs of sending the feedback instantly or after a delay. On the other hand, due to the energy cost of sending an FBM, if a player sends an FBM instantly, his payoff is equal

to 1 i . The reason behind selecting the costs given in

Equation (10a) and Equation (10b) is that when a user has abundant energy, he has no incentive to risk his QoS by delaying the transmission of his FBM. On the other hand, if his residual energy is limited, he takes the risk not to send an

more than n k packets, it sends an FBM asking for FBM and wait wishing that another user would send a FBM in

retransmission. The above-mentioned coding scheme can order to prolong his lifetime in the multicast service.

reconstruct the transmitted information when the packet loss The battery power of the user satisfies the condition

ratio is low. However, in modern satellite networks operating at the Ka frequency band (20/30 GHz) and above, propagation conditions, especially rain attenuation, severely impair link performance. In this case, coding is not sufficient to guarantee reliable data transmission. Besides, due to rain

min i max

(11)

where min is the threshold power rendering a user out of

operation and max is the maximum battery power of the

user. We assume that min and max are common to both

attenuation, the satellite channel exhibits both spatial and temporal variations. Therefore, it is expected that a large number of STs simultaneously suffer from rain-induced attenuation. Under these conditions, the probability that a large number of STs send, an FBM is high, resulting in feedback implosion [1].

A. Two-Player Feedback Suppression Game

In the feedback suppression game, any player who has lost a block of packets would like to send an FBM asking for retransmission, because recovering from the lost or corrupted

users we get

min i max 1

i =1,2

(12)

where min we dE min and max we dE max denote

the minimum and the maximum normalized energy costs

respectively. The players know that i , i = 1, 2 are random

variables following the same distribution over (min ,max )

with known strictly increasing cumulative distribution

function P where

Pmin 0

and Pmax 1

(13)

block helps him to satisfy the quality-of-service (QoS) From Equation (13b), we observe that for each user i the cost

constraints for data transmission. However, no player wants to send an FBM because this action costs, either in consuming energy or in occupying resources. Since energy issues are of utmost importance with regard to satellite networks survivability, especially in mobile satellite systems, the cost

Di depends on RTTi . Users with smaller elevation angle

have higher delays so we assumed that the users are distributed over the served area such that their elevation

angles range from min to max , corresponding to the delays

of sending an FBM is related to the energy consumption due to FBM transmission. Also, the possibility that no player sends an FBM should be prevented since, then, the QoS of all players would severely deteriorate. Therefore, an appropriate backup mechanism must enforce the dispatch of FBMs after a certain time period. Inevitably, this backup mechanism introduces delay. Hence, each player has two options, either send an FBM instantly, or delay its transmission. Table 3.1 presents the feedback suppression game between two players

in the range Dmin , Dmax where Dmin wd RTTmin and

Dmax wd RTTmax . A pure strategy for this game is a two-valued function

Si i , Di i =1,2 which maps (min ,max ) into {0,1}

where 1 signifies FBM is sent instantly and 0 signifies FBM is sent after a delay. The payoffs of the two-player game is given from

407

ISSN: 2277-3754

ISO 9001:2008 Certified

International Journal of Engineering and Innovative Technology (IJEIT)

Volume 2, Issue 6, December 2012

i si , sj ,i , Di 1isi 1 si 1 sj i Di , i, j 1, 2,i j

-

(14)

A Bayesian equilibrium is a pair of strategies

probability that none of the other players except i sends an FBM, then payoff of player i sending FBM instantly is

1 i and payoff for sending FBM with delay is

S

* i

,

S*

j

such

that

for

each

player

and

every

pi 1 (Di i (1 pi ).1 .As in the case of the

possible

pair i , Di ,

the

strategy

S

* i

i , Di maximizes

the expected payoff of the player i over j and Dj . We

denote

pj Pr S* j j , Dj 0

(15)

two-player version of the game the probability that none of the

players except i sends an FBM is given by

N

pi

1 Pr

min

j

D

j

* j

j 1, j i

(19)

And

since

pi

* i

* i

D*i

* j

1

* j

,

the

as the equilibrium probability that player j delays the equilibrium cutoff value should satisfy

transmission on his FBM. Then, the payoff of player i in case he sends a FBM instantly is given by 1 i while in

N

* j

1

* j

1 Pr

min

j

Dj

* j

for all i N

j1, ji

case he sends a FBM with a delay is

1 i Di pj 11 pj . Therefore, player i will

send a FBM instantly if his relative cost i i Di takes

values below the threshold

pj

* i

* i

D*i

.Thus, the

probability that p j that a player j will delay the

(20)

If a unique equilibrium cutoff value exists, it is the unique

solution

Dmax

* 1 * 1

Dmin

D

j

* j

N 1

min

fD

D

f

dDd

(21)

transmission of his FBM is given by

Then, the average FM transmission probability is given by

pj Pr

Dj

* j

j

max

1 Pr

min j

Dj

* j

-

(16)

Thus from Equation (19) we can determine that

Dmax

D

j

* j

* j

* j

1

1

fD D f dDd

Dmin min

i 1, 2,i j (17)

where fD D and f are the distributions related to the

delay and energy cost respectively [1]. Then, the average

probability of instant FBM transmission is given by

PFB

1

* j

1

* j

(18)

B. N-Players Feedback Suppression Game

Let N = {1, 2,....N} and pi , i N, denote the probability that player i does not send an FBM instantly. In

the N-player version of the game, N players having lost the same block participate in the game. Usually, the numbers of users in feedback suppression problems are estimated through the number of FBMs that arrive at the source. In satellite networks operating above 10 GHz, the problem appears when the multicast system is under rain conditions. Then, the majority of users located within the served area suffer simultaneously from a high number of packet losses; therefore, the number of players is quite close to the total number of multicast receivers. Using the same rationale with

the two player game, if player i does not send an FBM, he

has a normalized payoff equal to 1 and no delay, provided that at least one of the other N - 1 players will send an FBM. If

player i sends an FBM instantly, he has a payoff equal

to1 i . If all players risk and delay the transmission of their FBM, he has a payoff 1 (Di i ) . Let pi be the

PFB

1

* j

1

* j

1

N

1

(22)

From Equation (22) it is deduced that if the number of

multicast receivers is low, the probability to send an FBM

instantly is high. On the other hand, as N increases, PFB is

reduced, the receivers risk that none of the receivers will send

an FBM [6].

C. Performance Metrics

Even though the feedback suppression problem may be

effectively modeled based on game theory, it may prove

inadequate, since when the population of the multicast group

is large, the multicast receivers become so indifferent that

none of them sends an FBM instantly. In the feedback

suppression game under consideration, the probability that

none of the receivers selects the strategy to send an FBM

instantly, is determined from Equation (23), that is

PNFB

1 PFB

N

* j

1

* j

N

N 1

(23)

Therefore, in this case, all users adopt the strategy to wait and

then send an FBM. In a practical scenario, this strategy may

be easily implemented using timers configured by the

multicast receivers to expire slightly after RTT. If the timer of

a receiver expires before the reception of the lost block, it

sends an FBM asking for retransmission. The timer duration

should be sufficient for retransmitted blocks to reach all

multicast receivers and suppress their FBMs. Hence, the

expected number of FBMs and the average feedback delay

are given from

EFBM

PFB PNFB

N

1

* j

1

* j

1

N

* j

1

* j

N

N 1

N

(24)

408

ISSN: 2277-3754

ISO 9001:2008 Certified

International Journal of Engineering and Innovative Technology (IJEIT)

Volume 2, Issue 6, December 2012

The average feedback delay transmitted by the receiver is suppression scheme. The simulation is performed using

determined from

MATLAB 2011 software.

Delay=PFB

PNFB

RTT

* j

1

* j

N

N 1RTT

(25)

where RTT is the average RTT .

The game-theoretic feedback suppression scheme has been

Here in Fig. 1, the expected number of feedback messages for the PFS scheme is plotted against the number of receivers

for two different timer durations for =10. Here is the

parameter for the exponentially distributed timer. As can be observed form the figure that for T=4RTT the expected

presented, along with appropriate performance metrics. It has number of feedback messages is much less than for T=2RTT.

been assumed that number of receivers that has failed to This is because as the timer duration is larger, the users wait

correctly receive a data segment is known or can be for longer duration before sending out their FBM. For as

estimated. Let E^ , D^ be the average number and the average

delay of the FBMs returned from the receivers, respectively, after RTT, measured at the sender. Based on Equation (24) and Equation (25), the number of receivers that have failed to correctly receive a data segment is determined at the sender

many as 104 receivers the T=4RTT has almost 10 times better performance than that of T=2RTT.

Fig. 2, shows the simulation result where the average normalized delay of the poker-game based feedback suppression scheme for different timer values are plotted

from the solution of the following system

N PFB 1 PFB N E^

(26a)

RTTPFB 2RTT 1 PFB N D^

(26b)

For large number of receivers PFB 1, the solution of the

above system can be simplified employing the

approximation 1 PFB N 1 NPFB .

To examine the performance of the proposed GTFS

scheme, the users' residual battery power i is assumed to

follow the uniform distribution over (min ,max ) as inferred

from the fact that all satellite terminals have the same

against the number of receivers for =10. Here is the

parameter for the exponentially distributed timer. We observed that the delay for the poker-game for T=4RTT is worse than that for the T=2RTT. This is self-explanatory, as the timer duration increase the delay in sending feedback messages increases.

The simulation is done for all possible battery power and for different number of receivers. In Fig. 3, expected number of FBM, EFBM which quantifies the suppression?

equipment and their battery is recharged at randomly selected

time instants. Also, it is assumed that RTT delays for all users

are uniformly distributed ranging from RTTmin to RTTmax .

Thus, under these assumptions, (21) may be written as

* j

1

* j

1

1 min

12 *

N 1

(27)

where 1 and 2 are parameters related to energy and

delay cost distributions. RTT delays are uniformly distributed

between 480ms and 540ms and the weighing factors we and

wd are taken to be equal to 1. The network is assumed to

operate at 40GHz where the dominant factor impairing the link performance is rain attenuation. It is assumed that when a receiver sends a FBM to the hub source through the satellite, all the other receivers will also be able to receive it and are refrained from transmitting their own FBM [1].

Fig. 1 Expected number of FBM versus N for different timer durations for the Poker game scheme.

Performance of the proposed scheme is plotted for

min 1010 and various values of max .It can be observed

that when max 101 , the GTFS performance is impressive

IV. SIMULATION RESULTS AND DISCUSSIONS as it limits the expected number of FBMs below 30 for as

The performance characteristics of the proposed many as 106 receivers. But, if max is reduced below104 ,

game-theory based feedback suppression scheme were the suppression performance of the GTFS scheme becomes

simulated. The various performance parameters like the expected number of feedback messages and the delay were simulated as the number of receivers increase. The expected number of FBM and the delay were simulated for different values of the residual power in the battery. These performance parameters were simulated and compared with that of the existing solution of poker-game based feedback

worse. This is because as the users have no incentive to send FBMs as their power has almost been exhausted. Here, the appearance of the Genovese Syndrome becomes high which triggers the backup mechanism that leads to a drastic increase in the number of FBMs. In Fig. 4, the average delay normalized with respect to RTT is plotted versus the number

of users for various values of max . The average normalized

409

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download