§4.3 Frequent State Regeneration State Regeneration

(1)

§4.3 Frequent

§4.3 Frequent State Regeneration State Regeneration

Many NVEs cannot afford the communications and processor Many NVEs cannot afford the communications and processor overhead required to support absolute consistency through a overhead required to support absolute consistency through a centralized repository

centralized repository

Many NVEs do not require high level consistencyMany NVEs do not require high level consistency

Limited and temporary error is allowableLimited and temporary error is allowable

Smooth interface vs. absolute consistencySmooth interface vs. absolute consistency

Replace the distributed consistency protocol with a more Replace the distributed consistency protocol with a more aggressive state update notification system

aggressive state update notification system

Frequent State

Frequent State Regeneration (cont’d) Regeneration (cont’d)

Source host does not careSource host does not carewhat state information is cached or what state information is cached or available to other hosts

available to other hosts

Each update contains whole entity state, whether or not it has Each update contains whole entity state, whether or not it has changed

changed

The owner of information uses blind broadcastThe owner of information uses blind broadcast

asynchronously and unreliablyasynchronously and unreliably

at a regularat a regularintervalinterval

forward toforward toall participantsall participants

The receiver does not acknowledge packetsThe receiver does not acknowledge packets

Assumption: highAssumption: hightransmission rate will make inconsistencies transmission rate will make inconsistencies relatively unnoticeable

relatively unnoticeable

Even with moderate packet loss, blind broadcast can typically Even with moderate packet loss, blind broadcast can typically

(2)

Entity

Entity Ownership: Ownership: Background Background

Blind broadcasting sacrifices absolute consistency, and reduces Blind broadcasting sacrifices absolute consistency, and reduces some flexibility that centralized repositories offer

some flexibility that centralized repositories offer

In aIn acentralized repository systemcentralized repository system

any host can modify any entityany host can modify any entity

reliable and orderreliable and order--preserving updatespreserving updates

With frequent state regeneration systems, ensure that multiple With frequent state regeneration systems, ensure that multiple hosts

hostsdo not attempt to update ando not attempt to update anentity at the same timeentity at the same time

Problem: Who’s Got the Ball Now? (Part II) Problem: Who’s Got the Ball Now? (Part II)

A A B B

(3)

Explicit Entity Ownership Explicit Entity Ownership

Ensure that shared state can only be updated by one host at a Ensure that shared state can only be updated by one host at a time

time

exactlyexactlyone host has the ownershipone host has the ownershipof the stateof the state

the ownerthe ownerperiodicallyperiodicallybroadcasts broadcasts the value of the statethe value of the state

TypicallyTypicallyuser’s own user’s own representation (avatar)representation (avatar)is owned by is owned by thatthat useruser

Locks on other entities are managed by a lockLocks on other entities are managed by a lockmanager servermanager server

clientsclientsquery to obtain ownership and contact to release itquery to obtain ownership and contact to release it

thetheserver ensures that each entity has only one ownerserver ensures that each entity has only one owner

thetheserver owns the entity if no one else doesserver owns the entity if no one else does

failurefailurerecoveryrecovery

Lock Lock Manager: Example Manager: Example

A A B B

Lock Manager Lock Manager

Grant Grant LockLock Request Request LockLock

Request Request LockLock

Reject Reject LockLock

Update State Update State

(4)

Proxy Update Proxy Update

A A B B

Update Position (A) Update Position (A) Request Update Position Request Update Position

Update Position (B) Update Position (B)

Non-Non-ownerownersendssendsan update request to the owner of the statean update request to the owner of the state

The owner decides whether it acceptsThe owner decides whether it acceptsthetheupdateupdate

The owner serves as a proxyThe owner serves as a proxy

Generates anGenerates anextra message on each extra message on each nonnon--ownerownerupdateupdate

Suitable when nonSuitable when non--ownerownerupdates are rare or many hostsupdates are rare or many hostswantwantto update the to update the state

state

Ownership Transfer Ownership Transfer

A A B B

Lock Manager Lock Manager

Update Position (A) Update Position (A) Request Ownership Request Ownership Notify Lock

Notify Lock Transfer Transfer

Acknowledge Acknowledge Lock Transfer Lock Transfer

Grant Ownership Grant Ownership Update Position (B) Update Position (B)

(5)

Ownership Transfer

Ownership Transfer (cont’d) (cont’d)

The lock manager has the lock information at all timesThe lock manager has the lock information at all times

If the host fails, the lock manager defines the current lock If the host fails, the lock manager defines the current lock ownership state

ownership state

Lock ownership transfer incurs extra message overheadLock ownership transfer incurs extra message overhead

Suitable when a single host is going to make a series of Suitable when a single host is going to make a series of updates and there is little contention among hosts wishing to updates and there is little contention among hosts wishing to make updates

make updates

Reducing Broadcast Scope Reducing Broadcast Scope

In aIn afrequent state regeneration system, each host sends frequent state regeneration system, each host sends updates to all participants

updates to all participants

causescauseshosts to receive lots of extraneous informationhosts to receive lots of extraneous information

Multicast and areaMulticast and area--ofof--interestinteresttechniquestechniques

filterfilterthe updates before they get sent to inappropriate recipientsthe updates before they get sent to inappropriate recipients

Who should doWho should dothe the filtering?filtering?

the host itself?the host itself?

a server?a server?

We shall return to this in §6We shall return to this in §6

(6)

Frequent State Regeneration:

Advantages

Advantages and Drawbacks and Drawbacks

AddsAddsmultimulti--userusercapabilities to existing single-capabilities to existing single-user user applications

applications

Blind broadcasting does not require a serverBlind broadcasting does not require a server, consistency , consistency protocol nor

protocol nora lock manager (in most cases)a lock manager (in most cases)

Offers supportOffers supportfor a large number of usersfor a large number of users

Exhibits betterExhibits betterinteractive behaviourinteractive behaviour

Requires considerableRequires considerablenetwork bandwidthnetwork bandwidth

Susceptible to networkSusceptible to networklatencylatency

jitter = variationjitter = variationin network latency from one packet to the nextin network latency from one packet to the next

AssumesAssumesthat all hosts are broadcasting at the same ratethat all hosts are broadcasting at the same rate

Flashback: Maintaining

Flashback: Maintaining Dynamic Shared State Dynamic Shared State

Three basic approaches to maintain dynamic shared state:

sharedsharedrepositoriesrepositories

frequentfrequentbroadcastbroadcast

statestatepredictionprediction

Absolute Absolute consistency consistency

HighHigh update rate update rate

Dead Dead reckoning reckoning Centralized

Centralized information information repositories repositories

Frequent Frequent state state regeneration regeneration The TradeThe Trade--offoffSpectrumSpectrum

(7)

§4.4 Dead

§4.4 Dead Reckoning of Reckoning of Shared State Shared State

TransmitTransmitstate update packets less frequentlystate update packets less frequently

Use received information to approximate Use received information to approximate the true shared statethe true shared state

In between updates, each host predicts the state of the entitiesIn between updates, each host predicts the state of the entities

Dead Dead Reckoning: Example Reckoning: Example

Time 3.5:

Position ( Position (5.5, 65.5, 6))

Predicted Path Predicted Path

Time 3:

Position ( Position (4, 54, 5)) Velocity ( Velocity (3, 23, 2))

Transmit Transmit

Remote Prediction Remote Prediction

(8)

Dead Reckoning Protocol Dead Reckoning Protocol

DR protocol

DR protocolconsists of two elements:consists of two elements:

prediction techniqueprediction technique

how the entity’s current state is computed based on how the entity’s current state is computed based on previously received update packets

previously received update packets

convergence techniqueconvergence technique

how to correct the statehow to correct the stateinformation when an update is information when an update is received

received

Prediction and Convergence Prediction and Convergence

Time 4:

Position ( Position (7, 77, 7))

Current Predicted Path Current Predicted Path

Time 4:

New Predicted Path New Predicted Path Time 3:

Time 3:

(9)

Prediction Using Derivative Polynomials Prediction Using Derivative Polynomials

The most common DR protocols use derivative polynomialsThe most common DR protocols use derivative polynomials

Involves various derivatives of the entity’s current positionInvolves various derivatives of the entity’s current position

Derivatives of positionDerivatives of position

1.

1. velocityvelocity

2.2. accelerationacceleration

3.

3. jerkjerk

Zero Zero - - Order and First Order and First - - Order Polynomials Order Polynomials

Zero-Zero-order polynomialorder polynomial

position pposition p

thetheobject’s instantaneous position, no derivative informationobject’s instantaneous position, no derivative information

predicted position after tpredicted position after tseconds = pseconds = p

⇒The state regeneration technique⇒The state regeneration technique

First-First-order polynomialorder polynomial

velocity vvelocity v

predicted position after tpredicted position after tseconds = seconds = vt + pvt + p

(10)

Second

Second- - Order Polynomials Order Polynomials

We can usuallyWe can usuallyobtain better prediction by incorporating more obtain better prediction by incorporating more derivatives

derivatives

Second-Second-order polynomialorder polynomial

acceleration aacceleration a

predicted position after tpredicted position after tsecondsseconds

==½at½at²²+ vt+ vt+ p+ p

update packet: current position, velocity, and accelerationupdate packet: current position, velocity, and acceleration

popular and widely usedpopular and widely used

easy to understand and implementeasy to understand and implement

fast to computefast to compute

relatively good predictions of positionrelatively good predictions of position