Location Transparent Routing in Mobile Agent Systems

Merging Name Lookups & Routing

Werner Van Belle

Karsten Verelst

Theo D’Hondt

Programming Technology Lab (PROG)

Departement Computer Science (DINF)

Vrije Universiteit Brussel (VUB)

Mobile Multi Agent Systems

A Mobile Agent is an Active Autonomous Component

Able to Communicate with others

Able to Migrate to other ‘Agent Systems’

The Agent system is the “Operating System” to support these components

Mobile Multi Agent Systems

Application: interconnection of agents

Wide Area Network

Fine grained component structure

Frequent migration of components

Example

Agent “tecra.vub.ac.be/ses1”

a:agent(“progpc20.vub.ac.be/disc”);

a.calculate([[1,2],[3,4]],agentself());

Agent “progpc20.vub.ac.be/disc”

calculate(matrix,callback)::

{<dosomething>;
callback.display(matrix);}

Problem

Whenever an agent migrates its name changes

Its name shouldn’t change
but
How do we route messages ?

Forwarding

Forward msg

Send msg

D

B

C

A

a

a

b

Forwarding

Forward msg

Send msg

Migrate

Send location
update

D

B

C

A

a

a

b

Forwarding

Pro:

easy implemented

logging is easy

Contra:

communication is slowed down

interacting agent clusters are slow when migrated

Forwarding

Message send: 2T

time over network to reach home location

time over network to reach real location

Agent move: T + t

time over network to inform home location

time over network to migrate to new (nearby) position

Notifying Partners

Send msg

D

B

C

A

a

a -> D

b
a->D

E

a -> D

Notifying Partners

Send msg

Migrate

Send
Location
Updates

D

B

C

A

a

a -> C

b
a->C

E

a -> C

Notifying Partners

Pro:

doesn’t require a special architecture

suitable for fine grained secure systems

Contra:

impossible to know all possible communication partners

enormous overhead with popular agents

Notifying Partners

Message send: t

Time over network to reach (nearby) communication partner

Agent move: (C+1)t + [T]

Time needed to update all communication partners

Time needed to migrate to new position

[Time needed to update name server]

Name Serving & Routing

Send msg

Fetch addr

D

C

A

a

b -> A
a -> C

b

Name Serving & Routing

Send msg

Fetch addr

Migrate

Send location
update

D

C

A

a

b -> A
a -> C

b

Name Serving & Routing

Pro:

easy implemented

routing mechanism is independent of naming system

Contra:

name updates are slow

name lookups are slow

Name Serving & routing

Message send: T + t

lookup name

send message

Agent move: T + t

update name

migrate agent

Name Serving/Caching

Send msg

D

B

A

b -> A
a -> B

b
a->B

a

Name Serving/Caching

Send msg

D

B

A

a

b -> A
a -> B

b
a->B

Send Location
Update

Migrate

Name Serving/Caching

Send msg

Send Location
Update

D

B

A

a

b -> A
a -> D

b
a->B

Migrate

Fetch addr

Forward

Invalid add

Name Serving/Caching

Pro:

doesn’t require special infrastructure

fault tolerant

Contra:

if agents migrate frequently this solution takes too much overhead

we need a nameserver

Name Serving/Caching

Message send: t + (T+2t)m/n

time to send message

in m/n of the cases

update nameserver

forward message

update sender

Agent move: T + t

time to migrate agent

update nameserver

Merging Nameserving & Routing

D

B.D

C.D

A.B.D

A.B.D:b

E.B.D

C.D:a

A.B.D:b -> E

A.B.D:b

Merging Nameserving & Routing

D

B.D

C.D

A.B.D

E.B.D

C.D:a

A.B.D:b -> E

A.B.D:b

Merging Nameserving & Routing

Pro:

sends messages in O(t)

sends agents in O(t)

Contra:

requires special ‘hierarchical’ architecture

Performance Estimations

Message Send	Agent Migration

Forwarding	2T	T + t

Notify partners	t	T + (C+1).t

NS & Caching	t + (T+2t).m/n	T + t

Notify con part	t + T.n/m	T + (C+1).t

NS & Routing	t	t

Future Work

Merge the emerald system with our system to obtain a more reliable architecture to route messages

Cborg

http://progwww.vub.ac.be/pools/cborg

werner.van.belle@vub.ac.be
karsten.verelst@vub.ac.be
tjdhondt@vub.ac.be

Location Transparent Routing in Mobile Agent Systems

Werner Van Belle

1999-12-10T14:12:40