The CBorg
Mobile Agent Systems

An Overview

Werner Van Belle ; Karsten Verelst

Johan Fabry ; Theo D’Hondt

Programming Technology Lab (PROG)

Departement Computer Science (DINF)

Vrije Universiteit Brussel (VUB)

Overview

1 -- The Agent System

a -- infrastructure

c -- the language (pico)

d -- communication

e -- migration

2 -- Demonstration

3 -- Internals

4 -- Future Work

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

CBorg

Developed at PROG

Goal is to implement a light weight MMAS for research purposes

We try to achieve as much transparency as possible

Features

location transparency

strong migration

Based upon an interpreted language Pico

Infrastructure

Every agent system has a unique hierarchical name; eg. tecra and void.tecra

Hierarchical interconnection between agent systems forms a mobile multi agent infrastructure

Infrastructure

A CBorg Agent

Object Oriented

Own Code & Data Space

Single Threaded

Agents run concurrently

Can send messages to other agents

Can migrate to other agent systems

Written in PICO

PICO/Standard Stuff

Definition

a:900

a[10]:0

a(a,b,c):display(a+b+c)

Assignment

a:=90

a[67]:=89

PICO/Eval -Apply

a:b:20

ag:read(“a+b”)

eval(ag) -> 40

f(a,b)::a+b

f(1,2) -> 3

f@[1,2] -> 3

PICO/Variable Arguments

f@args::

{sum:0;

for(I:1,I<=size(args), I:=I+1,

sum:=sum+args[I]);

sum}

f(1,2,3) -> 6

f@[1,2,3,4] -> 10

PICO/Call by Name

a:50

delay(f())::f

delayed:delay(display(a))

a:=600

delayed()

: 600

PICO/Objects

{ makePoi(x,y)::

{move(X,Y) :: { x := X; y := Y };

area() :: 0;

makeSqu(w) ::

{widen(W) :: w := W;

area() :: w^2;

clone() };

clone() };

Point: makePoi(0,0);

Square: Point.makeSqu(2);

Square.area() --> 4

CBorg/ Creation/Killing

Interactive

Dynamic

createagent(<object>,<name>)

agentdie(agent)

>

- makes a deep copy of the <object>

- super will not be copied

CBorg/ Communication

“tecra.vub.ac.be/ses1”

a:agent(“void.tecra/disc”);

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

“void.tecra/disc”

calculate(matrix)::display(matrix)

- Automatic serialisation and deserialisation

- Transparant routering

- Connectionless

CBorg/ Callbacks

“tecra.vub.ac.be/ses1”

a:agent(“void.tecra/negate”);

a.calculate([[1,2]],agentself()) -> void

“void.tecra/negate”

calculate(matrix,resultto)::

resultto.display(negate(matrix))

- Asynchronous message passing

- Queued at receiver side

- Returns always void at sender side

CBORG/ Serialisation

“tecra/ses1”

makepoint(x,y)::

{show()::display(x+”:“+y);

clone()}

a:agent(“tecra/ses2”)

p:makepoint(10,20)

a.show(p) -> 10:20

“tecra/ses2”

show(p)::p.show()

- pass objects by reference

- pass primitives by value

Migration

Weak Migration

The agent can only migrate whenever the agent has stored its entire state in its objects

Cooperation from the agent is required

Code should be written in a special ‘state’-based manner

Migration

Strong Migration

At any moment an agent can migrate to another place without any special requirements towards the agent

The agent doesn’t need to take special precautions when executing

The agent doesn’t have to ‘cooperate’

Code mobility becomes useful

Use of Migration (I)

Use of Migration (II)

Use of Migration (III)

1

2

3

4

Use of Migration (III)

1

2

3

4

CBorg/ Migration

CBorg supports the notion of strong migration.

agentmove(place(“void.tecra”))

CBorg/ Migration

Fac(n)::

{

if(n\\1 = 0,

agentmove(place(“tecra/ses1”)),

agentmove(place(“void.tecra/ses1”)));

if(n=1,1,n*Fac(n-1))

}

Overview

1 -- The Agent System

2 -- Demonstration

3 -- Internals

a -- Naming and Routing

b -- Migration

4 -- Future Work

Naming and Routing

Routing 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

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

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

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

NS & Routing	t	t

1. Stop the execution of an agent

2. Gather its ‘state’

3. Remove the agent from memory

4. Send its entire ‘state’

5. Receive its entire state

6. Create an agent

7. Restore its entire state

8. Start running the agent

Strong Migration

Strong Migration

1. Stop the execution of an agent

2. Gather its ‘state’

3. Remove the agent from memory

4. Send its entire ‘state’

5. Receive its entire state

6. Create an agent

7. Restore its entire state

8. Start running the agent

Strong Migration

1. Stop the execution of an agent

2. Gather its ‘state’

3. Remove the agent from memory

4. Send its entire ‘state’

5. Receive its entire state

6. Create an agent

7. Restore its entire state

8. Start running the agent

Strong Migration

1. Stop the execution of an agent

2. Gather its ‘state’

3. Remove the agent from memory

4. Send its entire ‘state’

5. Receive its entire state

6. Create an agent

7. Restore its entire state

8. Start running the agent

Strong Migration

1. Stop the execution of an agent

2. Gather its ‘state’

3. Remove the agent from memory

4. Send its entire ‘state’

5. Receive its entire state

6. Create an agent

7. Restore its entire state

8. Start running the agent

Strong Migration

1. Stop the execution of an agent

2. Gather its ‘state’

3. Remove the agent from memory

4. Send its entire ‘state’

5. Receive its entire state

6. Create an agent

7. Restore its entire state

8. Start running the agent

Strong Migration

1. Stop the execution of an agent

2. Gather its ‘state’

3. Remove the agent from memory

4. Send its entire ‘state’

5. Receive its entire state

6. Create an agent

7. Restore its entire state

8. Start running the agent

Strong Migration

1. Stop the execution of an agent

2. Gather its ‘state’

3. Remove the agent from memory

4. Send its entire ‘state’

5. Receive its entire state

6. Create an agent

7. Restore its entire state

8. Start running the agent

Strong Migration

Problem: capturing the execution state of a running process

State consist of

Data Space

Code Space

Runtime Stack & IP

Non Interpreted Environment
memcpy of the process

Pointers to the operating system

Heterogeneous architectures

 we need an interpreted environment

Interpreted Environment
Serialisation

pointers to system dependent resources (user interface, disc access, etc...)

connections to other agents

globals in the evaluator

 platform independent serialization

 no fixed connections with system dependent resources

 abstrahate all system resources as agents which cannot migrate

 no connection oriented sockets

 the evaluator stores nothing in local or global variables

Runtime Stack

Runtime stack of the interpreter grows as the evaluation continues

public Object evaluate(Object ag)

{if (ag instanceof Applicable)

{Object closure=evaluate(ag.application()));

Object[] args=evalargs(ag.args());

return closure.apply(args);}

if (ag instanceof Identifier) return lookup(ag);

if (ag instanceof Integer) return ag;

...

Evaluator uses its own runtime stack to

simulate a stack for the evaluated program

Runtime Stack

These stack frames are almost impossible to serialize

Capturing the instruction pointer is almost	impossible

Deserializing is difficult because we have to create a new valid stack

Jumping to the new instruction pointer is difficult

 Explicit stack needed

 Write the evaluator in Continuation Passing Style

 Reify the stack in the evaluated language

Explicit Stack

2 stacks

continuation stack (what do I need to do in the future)

expression stack (the expressions accompaigning the continuations)

Before calling a continuation

the stack contains the arguments this continuation needs

Explicit Stack

2 stacks

continuation stack (what do I need to do in the future)

expression stack (the expressions accompaigning the continuations)

After calling a continuation

the top of the stack contains the result of the continuation

Explicit Stack

Pop_CNT, Pop_EXP

removes and returns value at top of expression/continuation stack

Push_CNT, Push_EXP

Pushes value at top of expression/continuation stack

Peek_CNT, Peek_EXP

returns value at top of continuation/expression stack

Poke_CNT, Poke_EXP

sets value at top of expression/continuation stack

Explicit Stack

Main-loop

while(1)

{CNT:POP_CNT();

CNT.invoke()}

Explicit Stack

evaluate

EXP

EXP

evaluate thunk

void evaluate()

{exp=PEEK_EXP();

if (exp instanceof Integer) return;

if (exp instanceof Identifier)

{POKE_EXP(lookup(exp));

return;}

...

Explicit Stack

evaluate

EXP

evaluate thunk

void evaluate()

...

if (exp instanceof Applicable)

{Object [] args=exp.args();

Object apl=exp.application();

POKE_EXP(apl);

PUSH_CNT(apply);

PUSH_CNT(evaluate);

PUSH_EXP(args);

PUSH_CNT(swap);

PUSH_CNT(evalargs);

}

}

apply

evaluate

evalargs

IDEN

EXP[]

Stack Trace

Program

Display(200+300)

evaluate

display(200+300)

Stack Trace

Program

Display(200+300)

apply

display

evaluate

[200+300]

swap

evalargs

Stack Trace

Program

Display(200+300)

apply

display

evaluate

[200+300]

swap

evalargs

Stack Trace

Program

Display(200+300)

apply

display

evaluate

[200+300]

swap

evalargs

Stack Trace

Program

Display(200+300)

apply

display

evaluate

[200+300]

swap

evalargs

Stack Trace

Program

Display(200+300)

apply

display

evaluate

[500]

swap

Stack Trace

Program

Display(200+300)

apply

evaluate

[500]

display

Stack Trace

Program

Display(200+300)

apply

[500]

native #83

Stack Trace

Program

Display(200+300)

“500”

Reification of the Runtime Stack

A snapshot of the complete execution state can be taken, just by serializing the runtime stack

Enables strong mobility

Concurrency can be managed within the evaluated language with primitives such as capture and restore

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