Denk-Uç Mimarisi Tabanlı Bir Süreç Eşleme Ortamı Gerçekleştirimi

Denk-Uç Mimarisi Tabanlı
Bir Süreç Eşleme Ortamı Gerçekleştirimi
Remzi Çelebi1, İbrahim Cereci2, Hüseyin Ellezer3, Cem Baylam4, Hürevren Kılıç5
1,2,3,5
Bilgisayar Mühendisliği Bölümü
Atılım Üniversitesi, İncek, Gölbaşı, Ankara
{rcelebi,icereci,hellezer,hurevren}@atilim.edu.tr
4
Cybersoft Enformasyon Teknolojileri Ltd.Şti.
Silikon Binaları 1. Kat, ODTÜ Teknokent, Ankara
[email protected]
Özetçe
Tek-girdili geçiş sistemi ve amaç durum kümesi ikilisinden
oluşan süreç (process) tanımlamasını takiben polinom zamanlı
bir süreç eşleme algoritması geliştirilmiştir. Geliştirilen
algoritma kullanılarak denk-uç (peer-to-peer) mimarisi ve
Gnutella protokolü temelli bir süreç eşleme ortamı
gerçekleştirilmiştir. Gerçekleştirimde orta-katman olarak Java
Agent Development Framework (JADE) kullanılmıştır.
Gerçekleştirilmiş ortam basit arayüz değişiklikleri ve ilgili
durum ontololojilerinin tanımlanması yoluyla herhangibir
uygulama alanı için kolaylıkla özelleştirilebilir.
1. Giriş
Denk-uç sistemlerinin (peer-to-peer systems) bireyler ve/veya
kuruluşlar arasındaki internet tabanlı ticareti geliştirme
potansiyeli vardır. Internetin dağıtık ve merkezi olmayan
yapısı denk-uç sistemlerinin şu ana kadar olduğu gibi sadece
içerik paylaşımı amacıyla değil süreç eşleme amacıyla da
kullanabilirliğini akla getirmektedir. Sahip olunan bireysel
veya kurumsal yetenekleri tanımlayan iş süreçlerinin yerel
gösterimi ve geliştirilecek eşleme algoritmaları sayesinde webtabanlı ortamlarda otomatik işbirliği mekanizmalarının
gerçekleştirimi mümkündür [1][2]. Sözkonusu merkezi
olmayan süreç eşleme ortamlarının gerçekleştirimlerinde
dikkate alınması gereken üç temel soru şunlardır:
1) İş yetenek ve hedeflerini süreç formunda nasıl
gösterimleyebiliriz (Gösterim problemi) ?
2) Tanımlanmış süreç ve amaç-durum tanımlamalarının
işbirliğini gerektirdiği ya da gerektirmediği hakkında karar
verecek otomatik eşleme mekanizması (veya algoritması) ne
olmalıdır (Eşleme problemi) ?
3) Süreçlerarası etkileşime olanak tanıyacak etkin mimari
ve protokol ne olabilir (Ortam problemi) ?
İlk sorunun cevabıyla ilgili olarak, UDDI [3] ve WSDL [4]
gibi ham dizgi gösterimi ve eşlemesine dayanan yaklaşımların
süreç durum ve dinamiklerini tanımlamada yetersiz kaldığı
görülmektedir. Alternatif bir gösterim şekli ise durum sistem
bilgisini de dikkate alan kontrol literatüründeki ayrık olay
sistemi tanımlamasına uyduğu düşünülen ayrık sonlu
özdevinir (automaton) gösterimidir. Örneğin, WSCL [5]
yaklaşımında, girdi/çıktı dizileri mesaj tipleri alfabesinin
oluşturduğu ayrık sonlu durum özdeviniri formunda
tanımlanmıştır. [6]’da ise iş süreçleri notlandırılmış
(annotated) ayrık sonlu durum özdeviniri şeklinde
tanımlanmıştır. İkinci soruya cevaben [6]’da, verilen iki Webservisinin eşlenebilirliği karşılık gelen iki özdevinirin
tanımladıkları dillerin kesişim kümesinin boş olup olmadığı ile
ilişkilendirilmiştir. Kesişimin boş küme olması eşlemenin
varolmadığı, boş küme olmaması ise eşlemenin mümkün
olduğu şeklinde yorumlanmıştır. Üçüncü sorunun cevabıyla
ilgili olarak [5] yaklaşımı herhangi bir mimari ya da protokol
önermemekle birlikte [7]’de önerilen mimari istemci/sunumcu
tabanlı sunumcu merkezli, dağıtık olmayan eşleme motoru
niteliğindedir. Bildiğimiz kadarıyla literatürde denk-uç tabanlı
protokol ve mimariye dayanan gerçekleştirilmiş bir süreç
eşleme gerçekleştirimi yoktur.
Bu makalede, [8]’de önerilmiş olan tek-girdili geçiş
sistemi modelini kullanan alternatif bir süreç gösterim şekli
tanımlanmıştır. Önerilen gösterim şeklinde, ayrık sonlu durum
özdeviniri yaklaşımlarından farklı olarak, verilen gösterimin
tam-olmamasına olanak tanınmaktadır. Diğer bir deyişle, süreç
tanımlamasını oluşturan tüm durumların erişilebilir olması şart
değildir. Eşleme operasyonu, verilen süreçlerin durum
düzeyinde bireştirimlerini takiben amaç durumlarının
erişilebilirliği testi şeklinde tanımlanmıştır. Önerilen
yaklaşımda amaç-durumlarının erişilebilirliği süreçler arası
eşlemenin varlığı şeklinde yorumlanmıştır. Makalenin ikinci
orjinal katkısı, sözkonusu süreç eşleme ortamı yazılımının
önerilen algoritma, denk-uç mimarisi ve Gnutella 0.4
protokolü baz alınarak gerçekleştirilmiş olmasıdır. Protokol
gerçekleştiriminde
orta-katman
olarak
Java
Agent
Development Framework (JADE) kullanılmıştır [9]. JADE
erkinleri (agents) farklı durum ontolojilerini kullanabilen ve
Gnutella 0.4 protokolüyle konuşan denk-uçlar şeklinde
tasarlanmışlardır.
Kısım 2’de, önerilen süreç gösterimi ve eşleme
algoritmasına ilişkin formal tanımlamalar verilmiştir. Kısım
3’te geliştirdiğimiz denk-uç mimarisi tabanlı süreç eşleme
sisteminin detayları anlatılmıştır. Son kısım, varılan sonuçları
içermektedir.
2. Süreç Gösterimi ve Eşleme
Tanım 1: Z sonlu sayıda elemandan oluşan durum kümesi; S
Z durum kümesi, V denk-ucun yeteneklerini
ise X

gösterimleyen sonlu küme, δ: X
V
→ X durum geçiş
fonksiyonu ve I X başlangıç durumundan oluşan (X, V, δ, I)
X olacak
şeklinde tanımlı tek-girdili geçiş sistemi olsun. PS
şekilde PS kümesi denk-ucun amaç durum kümesi olsun. Buna
göre (S, PS) ikilisine denk-ucun ilgili süreci denir.
Girdi değerinin varlığından dolayı tek-girdili geçiş sistemi
açık bir sistemdir. Şekil-1’de çizge-benzeri gösterim şekliyle
örnek süreç tanımlamaları görülmektedir. Gösterimdeki
X). Kalın
düğümler sistem durumlarını tanımlamaktadır (xi
kenarlı düğümler başlangıç durumu, kesikli düğümler amaç
durumlarıdır. Sürecini icra eden herhangi bir denk-ucun amacı
başlangıç durumundan başlamak üzere kendi amaç
durumlarından herhangi birine erişebilmektir. Şekil-1’i, Z =
{x1, x2, x3, x4}, S = (X, V, δ, I) öyle ki SX = {x1, x2, x3}, SV =
{v1S}, Sδ = {((x1, v1S) → x2)}, SI ={x1} ve PS = {x3} olacak
şekilde tekrar tanımlayabiliriz. Benzer şekilde, Q = (X, V, δ, I)
öyle ki QX = Z, QV = {v1Q, v2Q, v3Q}, Qδ = {((x1, v1Q) → x4),
((x2, v2Q) → x3), ((x3, v3Q) → x4)}, QI ={x3} ve PQ = {x2}’dir.
Şekildeki hem S hem de Q sistemleri için ilgili denk-uçların PS
ve PQ ile tanımlı kendi amaç durumlarına erişmeleri mümkün
değildir. Diğer bir deyişle, tek başına süreç (S, PS)’yi veya
süreç (Q, PQ)’yu icra edebilecek başarılı bir denk-uç yoktur.


v1S
X1
X2
X3
(a) Süreç (S, P S).
X2
X1
X1
v1Q
X4
Tanım 5: (Girdi ile çıkarımlanmış davranış).
S = (X, V, δ, I) sistemi ve ψ
V* girdi dizisi verilmiş olsun.
S sisteminin ψ dizisinin varlığında I’den başlayan davranışı


ξ (ψ) = ξ [0], ξ [1],
X*
şeklinde tanımlanır. Tanımlamada ξ[0] = I’dir ve herbir i indis
değeri için ξ[i+1] = δ(ξ[i], ψ[i])’dir.
Örneğin, Şekil-1(c)’deki sistem için, vlS, v2Q girdi dizisi Xl, X2,
X3 davranışını üretir ve aşağıdaki şekilde gösterimlenir:
v1 S
X1  X2
v2 Q

X3

X3
Aşağıdaki algoritma verilen bir tek-girdili geçiş sistemine
ait erişilebilir durumlar kümesini hesaplar.
v2Q
v3Q
δ(x) gösterimi, x durumunun ardışık takibeden durumları
kümesi olsun. Yani, δ(x) = {x': v δ(x, v) = x'}. Bu gösterim
δ(F) = {(δ(x) : x
F} şeklinde F durumlar kümesi için
genişletilebilir.

(b) Süreç (Q, PQ).
v1S
Bireşim işleminin kapalılık ve birleşme özellikleri vardır
ancak değişme özelliği yoktur. Bireşim işlemi basitçe,
düğümleri aynı tanım kümesinden durumlar olan çizgelerin
örtüşümüdür. Gerçekleştirilen yazılımda farklı tanım
kümeleriyle
tanımlı
durum
ontolojileri
dikkate
alınabilmektedir. Şekil-1(c) S ve Q sistemlerinin bireşimiyle
elde edilen T sistemini göstermektedir.
Tanım 6: (Açık sistemlerde erişilebilirlik).
X verilmiş olsun. Açık
S = (X, V, δ, I) sistemi ve P
sistemlerde erişilebilirlik problemi şu soruyla tanımlanır:
“Öyle bir ψ
V* girdi dizisi var mıdır ki ξ(ψ) davranışı P
durumuna erişsin ?”
v2Q
v3Q
X2
 Qδ ve TI = SI.

X4
v1Q
Tanım 4: Yetenek-ayrışık iki adet tek-girdili geçiş sistemi S ve
Q verilmiş olsun, bireşim(S, Q) işlemi T adlı tek-girdili geçiş
sistemini üretir öyle ki TX = SX  QX, TV = SV  QV, Tδ = Sδ
X3
(c) Süreç (T=Bireşim(S, Q), P S).
Şekil 1. Örnek süreç tanımlamaları ve bireşim işlemi
Tanım 2: İki adet tek girdili geçiş sistemi, S ve Q verilmiş
olsun. S ve Q sistemlerine SV  QV =  olması halinde
yetenek-ayrışık denir.
Tanım 3: Süreç (S, PS) ve süreç (Q, PQ) verilsin. PS = PQ
olması halinde bu süreçlere amaç-denk denir.
Şekil-1’deki S ve Q sistemleri yetenek-ayrışıktır. (S, PS) ve
(Q, PQ) süreçleri ise amaç-denk değildirler. Genel olarak,
herhangi bir tek-girdili geçiş sistemi kendisiyle yetenek-ayrışık
değildir. Herhangi bir süreç ise kendisiyle amaç-denk’tir.
Algoritma Erişilebilenler
Girdi: Tek-girdili geçiş sistemi, S = (X, V, δ, I).
Çıktı: I’den başlayıp erişilebilen tüm durumlar kümesi, F.
F0 := I
tekrarla
Fk+1:=Fk  δ(Fk)
k+1
F = Fk olana dek
F*:=Fk
dön F*
Algoritma polinom zamanlı basit bir çizge tarama
algoritması olup, karmaşıklığı O(|X|.log(|X|)*|V|)’dir [8].
Tarama şekli, herbir Fk kümesi en fazla k adet geçişten sonra
erişilmiş durumları içerecek şekilde enine-öncelikli (breadthfirst) özelliktedir.
Şekil-1’deki sistemler için Erişilebilenler(S), {X1, X2}
kümesini ve Erişilebilenler(Q) ise {X3, X4} kümesini döner.
Benzer şekilde, Erişilebilenler(T)’nin çıktısı {X1, X2, X3,
X4}’dir. Bireşim işlemi ve erişilebilenler algoritmasını
tanımlamamızı takiben her bir denk-uca gömülü olan ve uç
tarafından çalıştırılan eşleme algoritmasını tanımlayabiliriz.
Algoritma Eşleme
Girdi: Yetenek-ayrışık S ve Q sistemlerinden oluşan (S, PS) ve
(Q, PQ) süreçleri.
Çıktı: Eşleme sonucu.
T = bireşim(S, Q);
T’ = bireşim(Q, S);
yönlen eşleme sonucu
0 : ((PS  erişilebilenler(T)) = ) ve
((P Q  erişilebilenler(T’)) = );
1 : ((PS  erişilebilenler(T)) ≠ ) ve
((P Q  erişilebilenler(T’)) = );
2 : ((PS  erişilebilenler(T)) = ) ve
((P Q  erişilebilenler(T’)) ≠ );
3 : ((PS  erişilebilenler(T)) ≠ ) ve
((P Q  erişilebilenler(T’)) ≠ );
sonu;
dön eşleme sonucu;
gönderici (sender), -ile cevapla (reply-with), alıcı (receiver),
yayınla (broadcast) gibi yerleşik öznitelikleri (attribute) veya
kullanıcı tarafından tanımlanabilen özel öznitelikleri içerir.
Eşlenmek istenen süreç tanımları Şekil-3’te görülen genel
amaçlı kullanıcı arayüzü vasıtasıyla girilebilmektedir. Bu
arayüz kullanıcı ilgi alanına göre kolaylıkla amaca uygun
olacak şekle uyarlanabilir. Sistemde bulunan denk-uçların
komşularından haberdar olması Gnutella protokolünün temel
ping ve pong mesajlarını kullanmak suretiyle güncellenen
yerel bir arama (look-up) tablosu kullanılarak sağlanmıştır.
Protokolün sorgu tipindeki mesajları ise süreç tanımlamalarını
eşlenme potansiyeli olan komşu denk-uçlara geçirmek
amacıyla kullanılmıştır. Yukarıda tanımlanan eşleme
algoritması herbir denk-uca gömülmüş ve yerel çalıştırım
sonucuna göre ilgili Gnutella 0.4 eylemi (sorgu veya çarpansorgu) sorguyu alan denk-uç tarafından yerine getirilmektedir.
Aşağıdaki
örnekler
EKD
sözdizimi
kullanılarak
gerçekleştirilmiş mesajları içermektedir.
Ping gerçekleştirimi:
(QUERY-REF
:sender peer2
:receiver peer5
:reply-with ping1154566259531
:X-ttl 5
:X-originator "peer1" )
Algoritmada, denk-uç p tarafından tarafından sahip olunan
süreç (S, PS) ve denk-uç r tarafından tarafından sahip olunan
süreç (Q, PQ) olsun. Buna göre aşağıdaki şekilde kodlanmış
dört farklı eşleme sonucu elde etmek mümkündür.
0 – eşleme yok;
1 – sadece denk-uç p’nin süreci r’ninkiyle eşlenebilir;
2 – sadece denk-uç r’nin süreci p’ninkiyle eşlenebilir;
3 – karşılıklı eşleme, yani hem p hem de r’nin süreçleri
birbirleriyle eşlenebilir.
Şekil-1(c)’deki eşleme örneğinin sonucu eşleme((S,
PS),(Q, PQ)) = 1’dir.
3. Denk-Uç Tabanlı Süreç Eşleme Sistemi
Geliştirilen denk-uç tabanlı sistem JADE orta-katmanı
üzerinde yapılandırılmıştır. JADE kullanımındaki temel sebep
JADE’in denk-uç sisteminin gerçekleştirilmesine olanak
tanıyan zengin mesaj-kotarma altyapısıdır. Ayrıca JADE hem
kablolu hem de kablosuz ortamlarda birlikte-çalışabilirliği
(inter-operability) desteklemektedir. Çok-erkinli sistemlerin
kalıtsal olarak denk-uç sistemleri olduğu ve denk-uç erkin
(peer-to-peer agent) sistemlerindeki erkinlerin denk-uçlar
olarak modellenebileceği bilinmektedir [10]. Çok-erkinli
sistemler perspektifinden bakacak olursak gerçekleştirilen
denk-uç sistemi rekabet içinde olmayıp işbirliği içinde olan bir
erkin sistemidir. Şekil-2’de görüldüğü gibi sistem JADE orta
katmanı üzerine oturan bir yerpaylaşım (overlay) şeklinde
tasarlanmıştır.
Denk-uçlararası etkileşim protokolü olarak Gnutella 0.4
protokolü kullanılmıştır. Gerçekleştirilmiş Gnutella mesajları
ping, pong, sorgu (query) ve çarpan-sorgu (query-hit)’dur ve
bu mesajlar JADE tarafından desteklenen standart FIPA Erkin
Kontrol Dili - EKD (Agent Control Language- ACL)
sözdizimine gömülmüştür. EKD sözdiziminde her mesaj
alıcısı tarafından gerçekleştirilmesi amaçlanan eylemi (action)
tanımlayan performatif ile başlar. Mesajın kalan kısmı
Şekil 2. Gerçekleştirimin sistem-düzeyindeki görünümü
Ping mesajının kullanım amacı bir denk-ucun herhangi bir
andaki denk-uç komşuluk yapısından haberdar olabilmesidir.
Mesaj, mevcut ve hedeflenen denk-uçları tanımlayan gönderici
(sender) ve alıcı (receiver) yerleşik özelliklerinden oluşur.
Ping mesajları, Sorgu-Referans (Query-Ref) performatifinin –
ile cevapla kısmında tutulan bilgi kullanılarak cevaplanır.
Tanımladığımız X-kaynak (X-originator) özniteliği ping
mesajının orjinal kaynağını gösterir. Yine tanımladığımız X-ttl
özniteliği sürecin yaşam süresini belirleyen ve sekme (hop)
birimiyle tanımlı değeri barındırır.
Pong gerçekleştirimi:
(INFORM
:sender peer5
:receiver peer2
:in-reply-to ping1154566259531
:X-ttl 5
:X-originator "peer5"
:X-receiver "peer1")
Pong mesajı ping mesajına cevaptır. Pong mesajı, ping
çekilmiş denk-ucun mesajı gönderen orjinal kaynağa
kendisinin halen sisteme bağlı ve canlı halde olduğu hakkında
bilgi vermesini hedefler. Ayrıca, orjinal ping kimlik bilgisini
de barındırır. Örnekte görülen Alıcı (Receiver) ve X-alıcı (Xreceiver) öznitelikleri arasındaki fark, ilkinin o anki pong
mesajını alacak komşu denk-ucu belirtmesi, ikincisinin ise
mesajın hedeflenen nihai alıcısını tanımlıyor olmasıdır.
Geliştirilen sistemde DS erkini doğrudan denk-uç
sistemlerindeki ÖnYüklemeSunumcusu (BootStrapServer)
olarak kullanılmıştır. ÖnYüklemeSunumcusu’nun temel
görevi mevcut denk-uç ağının bir parçası olmak isteyen yeni
denk-uçlara, ağda bulunan denk-uçların listesini dönmektir.
4.
Sonuçlar
Tam-olmayan süreç tanımlamalarına olanak tanıyan bir süreç
gösterim şekli ve süreç eşleme işlemine olanak tanıyan eşleme
algoritması önerilmiştir. Bunu takiben, merkezi olmayan,
denk-uç tabanlı bir süreç eşleme sistemi geliştirilmiştir. Sistem
istenilen bir uygulama alanına, yapılacak kullanıcı arayüzü
değişiklikleri ve ilgili durum-ontolojilerinin tanımlanması
suretiyle kolaylıkla uyarlanabilir.
İleride, yeteneklere maliyet ve amaçlara fayda değerleri
atamak yoluyla mevcut süreç tanımlaması geliştirilebilir. Bu
sayede denk-uçlar arasında olası müzakere mekanizmaları için
açılım da sağlanabilir.
Sorgu gerçekleştirimi:
(CFP
:sender peer1
:receiver peer5
:content
"((Reachable
owner:peer1
process:a1))"
:language fipa-sl
:ontology Task-description-ontology
:X-ttl 5
:X-orginator "peer1" )
Sorgu mesajı süreç eşleme işleminin başlatıcısı olarak
kullanılmıştır. Öneri Çağrısı (Call For Proposal - CFP)
performatifinin göndericisi sistemde kendi süreç tanımını
eşleyebileceği bir denk-uç bulabilmeyi hedefler. Mesajın içerik
kısmı standart FIPA-SL dilinde yazılmıştır. Örnekteki mesajın
içeriği, a1 sürecinin sahibi olan peer1’in alıcı denk-ucun
süreciyle eşleme yapma amacında olduğunu göstermektedir.
Ontoloji (Ontology) yerleşik özniteliği mevcut sürecin ilgili
durum-ilgi alanı (state-domain)’nı tanımlamaktadır.
Çarpan-sorgu gerçekleştirimi:
(PROPOSE
:sender peer5
:receiver peer1
:content
"((Propose
:proposer
peer5
:matchresult 2 :process a3))"
:in-reply-to query1154566257093
:language fipa-sl
:ontology Task-description-ontology
:X-ttl 5
:X-orginator "peer5"
:X-receiver "peer1")
Çarpan-sorgu mesajı sorgu mesajına cevaptır. İçerik kısmı
bir eşleme olması durumunda önerenin (proposer/owner)
kimlik bilgisini, eşleme tipini ve önerenin süreç tanımını
içerir. Ontoloji özniteliği sorgu örneğinde olduğu gibi mevcut
sürecin ilgili durum-ilgi alanını tanımlamaktadır.
Tipik bir JADE kurulumunda, özel amaçlı bir sistem erkini
olan ve ana içerenin (container) içinde yaşayan Dizin
Sağlayıcı - DS (Directory Facilitator - DF) bulunur.
Şekil 3. Süreç tanımlama giriş ekranı arayüzü.
5. Kaynakça
[1] K. Sycara, J. Lu, M. Klusch, and S. Widoff,
“Matchmaking among heterogeneous agents on the
internet”, in Proceedings of the 1999 AAAI Spring
Symposium on Intelligent Agents in Cyberspace, Stanford
University, USA 22-24 March 1999.
[2] I. Constantinescu, and B. Faltings “Efficient
Matchmaking and Directory Services”, Proceedings of
the IEEE/WIC International Conference on Web
Intelligence, October 2003, pp. 75-81.
[3] I. Ariba, I. Corporation, and M. Corporation, “Universal
description, discovery and integration”, September 2000,
http://www.uddi.org/.
[4] E. Christensen, F. Curbera, G. Meredith, and S.
Weerawarana, “Web services description language
(WSDL) 1.1”, March 2001. http://www.w3.org/TR/wsdl.
[5] A. Banerji, C. Bartolini, D. Beringer, V. Chopella, K.
Govindarajan, A. Karp, H. Kuno, M. Lemon, G.
Pogossiants, S. Sharma, and S. Williams, “Web
services conversation language (WSCL) 1.0”, March
2002. http://www.w3.org/TR/wscl10/.
[6] A. Wombacher, P. Fankhauser, B. Mahleko, and E.
Neuhold, “Matchmaking for Business Processes Based
on Choreographies”, International Journal of Web
Services Research, 1(4), Oct-Dec 2004, pp. 14-32.
[7] A. Wombacher, B. Mahleko, and E. Neuhold, “IPSI-PF:
A business process matchmaking engine based on
annotated finite state automata”, Inf. Syst. E-Business
Management, 3(2), 2005, pp. 127-150.
[8] O. Maler, “Control from Computer Science”, Annual
Reviews in Control, 26, 2002, pp. 175-187.
[9] F. Bellifemine, A. Poggi, G. Rimassa, “JADE: A White
Paper”, 3 September 2003.
[10] O. Shehory, “Robustness challenges in peer-to-peer agent
systems”, Agents and Peer-to-Peer Computing, Second
Intl.Workshop, AP2PC 2003, LNAI 2872, pp. 13-22.