--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/tools/python-PE/CompactRouting/CompactRouting.py	Sat Feb 16 13:18:02 2008 +0900
@@ -0,0 +1,370 @@
+from Routing import *
+import time
+
+ROUTING_COMMAND_UPDATE_LANDMARK_TABLE = 5
+LANDMARK_HOPLIMIT = 2
+
+class Landmark_TSInfo:
+    def __init__(self, landmark_tsid, landmark_dst):
+	self.landmark_tsid = landmark_tsid
+	self.landmark_dst = landmark_dst
+
+
+""" XML format is as follows    
+<RoutingTable name="localhost:10000">
+  <ts hopnum="1" tsid="localhost:10002" ttl="16"/>
+  <ts hopnum="1" tsid="localhost:10001" ttl="16"/>
+  <ts hopnum="0" tsid="localhost:10000" ttl="0"/>
+  <landmark dst="localhost:10000" tsid="localhost:10000"/>
+  </RoutingTable> 
+"""
+
+class CompactRoutingTable(RoutingTable):
+    def __init__(self, name):
+	RoutingTable.__init__(self, name)
+	self.landmark_tslist = {}
+
+    def landmark_register(self, tsid, dst):
+	if(self.landmark_tslist.has_key(tsid)):
+	    del self.landmark_tslist[tsid]
+	self.landmark_tslist[tsid] = Landmark_TSInfo(tsid, dst)
+
+    def landmark_deregister(self, tsid):
+	for t in self.landmark_tslist.keys():
+#	    if self.landmark_tslist[t].nexthop == tsid:
+	    del self.landmark_tslist[t]
+
+    def boundedcount_register(self, count):
+	self.boundedcount = count
+
+    def getNewLandmark(self):
+	flag = False
+	if(self.landmark_tslist.has_key(self.name)):
+	    return flag
+
+	for t in self.landmark_tslist.keys():
+	    landmark_tsid = self.landmark_tslist[t].landmark_tsid 
+	    if(self.tslist.has_key(landmark_tsid)):
+		if(self.tslist[landmark_tsid].hopnum == LANDMARK_HOPLIMIT+1):
+		    flag = True
+		else:
+		    flag = False
+
+	return flag
+
+    def update(self, xmldoc, ts):
+        rt = xml.dom.minidom.parseString(xmldoc).childNodes[0]
+        tslist = rt.childNodes
+        updateflag = False
+
+        tmplist = []
+
+        # append tuplespace                            
+	for t in tslist:
+            if t.nodeType == t.ELEMENT_NODE and t.localName == 'ts':
+                tsattr  = t.attributes
+                tsid    = tsattr['tsid'].nodeValue
+                hopnum  = int( tsattr['hopnum'].nodeValue )
+                ttl     = int( tsattr['ttl'].nodeValue )
+                nexthop = ts
+
+		tmplist.append(tsid)
+
+                if (((not self.tslist.has_key(tsid)) or (self.tslist[tsid].hopnum > hopnum+1)) 
+		    and (ttl-1 > 0)):
+                    self.register(tsid, hopnum+1, ttl-1, nexthop)
+                    updateflag = True
+
+        # delete tuplespace         
+	for t in self.tslist.values():
+            if (( not t.tsid in tmplist ) and (t.ttl-1 > 0)):
+                updateflag = True
+                if (t.nexthop == ts):
+                    del self.tslist[t.tsid]
+
+        return updateflag
+
+    def update_withLandmark(self, xmldoc, src_ts):
+	rt = xml.dom.minidom.parseString(xmldoc).childNodes[0]
+        tslist = rt.childNodes
+        updateflag = False
+	
+        tmplist = []
+	tmplandmarklist = []
+
+	for t in tslist:
+	    # append tuplespace  
+            if t.nodeType == t.ELEMENT_NODE and t.localName == 'ts':
+                tsattr  = t.attributes
+                tsid    = tsattr['tsid'].nodeValue
+                hopnum  = int( tsattr['hopnum'].nodeValue )
+                ttl     = int( tsattr['ttl'].nodeValue )
+                nexthop = src_ts
+
+                tmplist.append(tsid)
+		if (((not self.tslist.has_key(tsid)) or (self.tslist[tsid].hopnum > hopnum+1))
+                    and (ttl-1 > 0)):
+                #if ((not self.tslist.has_key(tsid)) or
+                #    (self.tslist[tsid].hopnum > hopnum+1)):
+		    self.register(tsid, hopnum+1, ttl-1, nexthop)
+                    updateflag = True
+    
+	    #parse landmark tsid/dst for register
+	    elif t.nodeType == t.ELEMENT_NODE and t.localName == 'landmark':
+		lkattr = t.attributes
+		landmark_tsid = lkattr['tsid'].nodeValue
+		landmark_dst  = lkattr['dst'].nodeValue
+
+		tmplandmarklist.append(landmark_tsid)
+
+		if (not self.landmark_tslist.has_key(landmark_tsid)):
+		    self.landmark_register(landmark_tsid, src_ts)
+		    updateflag = True
+
+	    #bounded count -1
+	    #elif t.nodeType == t.ELEMENT_NODE and t.localName == 'bound':
+		#boundattr = t.attributes
+		#if(int(boundattr['count'].nodeValue) > 0):
+		 #   count = int( boundattr['count'].nodeValue)-1
+		 #   self.boundedcount_register(count)
+		 #   updateflag = True
+		#elif(int(boundattr['count'].nodeValue) == 0):
+		 #   self.landmark_register(self.name, self.name)
+		 #   count = int( boundattr['count'].nodeValue)-1
+		 #   self.boundedcount_register(count)
+		 #   updateflag = True
+
+        # delete tuplespace                                                             
+	for t in self.tslist.values():
+	    if (( not t.tsid in tmplist ) and (t.ttl-1 > 0)):
+	    #if ( not t.tsid in tmplist ):
+                updateflag = True
+                if (t.nexthop == src_ts):
+                    del self.tslist[t.tsid]
+
+	for lt in self.landmark_tslist.values():
+	    if ( not lt.landmark_tsid in tmplandmarklist ):
+		updateflag = True
+
+	return updateflag
+
+    def getxmldoc_withLandmark(self):
+	doc = xml.dom.minidom.Document()
+	rt = doc.createElement('RoutingTable')
+        rt.setAttribute('name', self.name)
+        for tskey in self.tslist.keys():
+	    #bound limit
+	    #if(self.tslist[tskey].hopnum < LANDMARK_HOPLIMIT):
+	    elem = doc.createElement('ts')
+	    elem.setAttribute('tsid', self.tslist[tskey].tsid)
+	    elem.setAttribute('hopnum', str(self.tslist[tskey].hopnum))
+	    elem.setAttribute('ttl', str(self.tslist[tskey].ttl))
+	    rt.appendChild(elem)
+
+	for l_tskey in self.landmark_tslist.keys():
+	    l_elem = doc.createElement('landmark')
+	    l_elem.setAttribute('tsid', self.landmark_tslist[l_tskey].landmark_tsid)
+	    l_elem.setAttribute('dst', self.landmark_tslist[l_tskey].landmark_dst)
+	    rt.appendChild(l_elem)
+	    
+	#if(self.landmark_tslist.has_key()):
+	#bound_elem = doc.createElement('bound')
+	#bound_elem.setAttribute('count', str(self.boundedcount))
+	#rt.appendChild(bound_elem)
+
+	return rt
+
+    def getxml_withLandmark(self):
+	rt = self.getxmldoc_withLandmark()
+	return rt.toxml()
+
+    def getLandmarklist(self, xmltext):
+	rt = xml.dom.minidom.parseString(xmltext).childNodes[0]
+	landmark = rt.getElementsByTagName('landmark')
+	if(landmark.length != 0):
+	    i = 0
+	    while 1:
+		try:
+		    landmark_tsid = landmark[i].getAttribute('tsid')
+		    landmark_dst = landmark[i].getAttribute('dst')
+		    print "getLandmarklist",landmark_tsid,landmark_dst
+		    i = i + 1
+		except IndexError:
+		    break
+	pass
+
+    def regLandmarklist(self, xmltext):
+	rt = xml.dom.minidom.parseString(xmltext).childNodes[0]
+	landmark = rt.getElementsByTagName('landmark')
+	if(landmark.length != 0):
+	    i = 0
+	    while 1:
+		try:
+		    landmark_tsid = landmark[i].getAttribute('tsid')
+		    landmark_dst = landmark[i].getAttribute('dst')
+		    self.landmark_register(landmark_tsid, landmark_dst)
+		    i = i + 1
+		except IndexError:
+		    break
+	pass
+
+    def printxml_withLandmark(self):
+	rt = self.getxmldoc_withLandmark()
+	print rt.toprettyxml()
+	end = time.time()
+	print "passed time ", end
+
+class CompactRouting(Routing):
+    def __init__(self, hearderFormat = ROUTING_HEADER_FORMAT):
+	Routing.__init__(self, hearderFormat)
+	self.landmark_tsid = None
+	self.landmark_neighbors = {}
+
+    def __del__(self):
+	self.linda.close()
+	for ts in self.neighbors.values():
+	    ts.close()
+	for landmark_ts in self.landmark_neighbors.values():
+	    landmark_ts.close()
+
+    def addLandmark_Neighbor(self, landmark_ts, landmark_tsid):
+	self.landmark_neighbors[tsid] = landmark_ts
+	return landmark_ts
+
+    def delLandmark_Neighbor(self, landmark_ts, landmark_tsid):
+	del self.landmark_neighbors[landmark_tsid]
+
+    #def landmark_Str2List(self, str_tsidlist):
+	#return string.split(str_tsidlist,",")
+    
+    #def landmark_List2Str(self, landmark_tsidlist):
+	#return ",".join(landmark_tsidlist)
+
+#    def RoutingConnect(self, data):
+#        print "connect"
+#        if ( not self.neighbors.has_key(data) ):
+#	    print "connect2"
+#            ts = self.connect(data)
+#            ts.Out(TUPLE_ID_ROUTING, self.pack(self.tsid, ROUTING_COMMAND_CONNECT))
+
+#        self.rt.register(data, 1, 3, data)
+#	#if (self.rt.landmark_tslist.keys()):
+#	#    print self.rt.landmark_tslist.keys()
+#        upedxml = self.rt.getxml()
+#	print "Gen XML ",upedxml
+#	print "Neighbors ",self.neighbors
+#	for nts in self.neighbors.values():
+#            nts.Out(TUPLE_ID_ROUTING, self.pack(upedxml, ROUTING_COMMAND_UPDATE_TABLE))
+#        pass
+    def RoutingConnect(self, data):
+        print "connect"
+        if ( not self.neighbors.has_key(data) ):
+            ts = self.connect(data)
+            ts.Out(TUPLE_ID_ROUTING, self.pack(self.tsid, ROUTING_COMMAND_CONNECT))
+
+        self.rt.register(data, 1, LANDMARK_HOPLIMIT, data)
+        upedxml = self.rt.getxml()
+	#       print "Gen XML ",upedxml    
+	#       print "Neighbors ",self.neighbors
+	for nts in self.neighbors.values():
+            nts.Out(TUPLE_ID_ROUTING, self.pack(upedxml, ROUTING_COMMAND_UPDATE_TABLE))
+        pass
+
+    def RoutingTableUpdate(self,data):
+	print "update"
+        srcname = self.rt.getdstname(data)
+
+        #if ( self.rt.update_withLandmark(data, srcname) ):
+	if ( self.rt.update_withLandmark(data, srcname) ):
+	    #Landmark find
+	    if(self.rt.getNewLandmark()):
+	    	self.rt.landmark_register(self.rt.name, self.rt.name)
+	    	print "I got New Landmark!"
+            # Send Update Info to Neighbors                                                    	
+	    upedxml = self.rt.getxml_withLandmark()
+
+	    #split horizon
+	    tmp_neighbors = self.neighbors
+	    del tmp_neighbors[srcname]
+
+	    for n in tmp_neighbors.values():
+		n.Out(TUPLE_ID_ROUTING, self.pack(upedxml, ROUTING_COMMAND_UPDATE_TABLE))
+	pass
+
+    def run(self, mytsid, Landmark_flag):
+	self.tsid = mytsid
+	hostname, port = string.split(mytsid, ':', 1)
+	self.linda = self.flinda.open(hostname, int(port))
+	if not self.linda:
+	    return
+
+	self.rt = CompactRoutingTable(mytsid)
+	self.rt.register(self.rt.name, 0, LANDMARK_HOPLIMIT+1, None)
+	
+	if(Landmark_flag == True):
+	    self.rt.landmark_register(self.rt.name, self.rt.name)
+
+	self.linda.getid() # get client id from Tuple Space (ldserv)
+
+	linkConfigReply = self.linda.In(TUPLE_ID_LINKCONFIG)
+        routingReply = self.linda.In(TUPLE_ID_ROUTING)
+
+        self.flinda.sync()
+
+	while(True):	    
+	    # Link Configuration
+	    rep = linkConfigReply.reply()
+	    if(rep):
+		linkConfigReply = self.linda.In(TUPLE_ID_LINKCONFIG)
+
+		# Link Configuration main (use Routing class method) 
+		self.LinkConfig(self.tsid, rep)
+
+	    # Routing Protocol
+	    rep = routingReply.reply()
+	    if(rep):
+                routingReply = self.linda.In(TUPLE_ID_ROUTING)
+                cmd , data = self.unpack(rep)
+
+                # connect to other tuplespace
+                if (cmd == ROUTING_COMMAND_CONNECT):	    
+                    # connect main
+		    self.RoutingConnect(data)
+		
+                # disconnect other tuplespace
+		elif (cmd == ROUTING_COMMAND_DISCONNECT):
+		    # disconnect main
+		    self.RoutingDisconnect(data)
+
+                # update own routing table
+                elif (cmd == ROUTING_COMMAND_UPDATE_TABLE):
+		    #routing table main
+		    self.RoutingTableUpdate(data)
+
+                # transfer tuple
+                elif (cmd == ROUTING_COMMAND_TRANSFER):
+		    # transfer main
+		    self.RoutingTransfer(data)
+
+                else:
+                    pass
+
+                print self.rt.printxml_withLandmark()
+	    self.flinda.sync()	
+       #end while
+
+if __name__ == '__main__':
+    import sys
+
+    Landmark_flag = False
+    if (len(sys.argv) != 2) :
+	if (sys.argv[2] == "-L"):
+	    Landmark_flag = True
+	else:
+	    print "Usage : %s <hostname:portnum> or <hostname:portnum> -L" % sys.argv[0]
+	    sys.exit(1)
+
+    mytsid = sys.argv[1]
+
+    routing = CompactRouting()
+    routing.run(mytsid, Landmark_flag)