From bd39@cornell.edu Mon Oct 7 17:27:46 2002 Received: from postoffice2.mail.cornell.edu (postoffice2.mail.cornell.edu [132.236.56.10]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g97LRjh14779 for ; Mon, 7 Oct 2002 17:27:45 -0400 (EDT) Received: from boweilaptop.cornell.edu (r102439.resnet.cornell.edu [128.253.163.42]) by postoffice2.mail.cornell.edu (8.9.3/8.9.3) with ESMTP id RAA17048 for ; Mon, 7 Oct 2002 17:27:44 -0400 (EDT) Message-Id: <5.1.0.14.2.20021007172139.00bbae90@postoffice2.mail.cornell.edu> X-Sender: bd39@postoffice2.mail.cornell.edu (Unverified) X-Mailer: QUALCOMM Windows Eudora Version 5.1 Date: Mon, 07 Oct 2002 17:26:24 -0400 To: egs@CS.Cornell.EDU From: Bowei Du Subject: 615 PAPER 30 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed Intentional Naming Services INS seeks to provide a way of naming devices based on attributes, rather than a known name, providing a requested service -> device mapping. This is a accomplished by: - Describing services in a query language composed of attributes and values, and using this language to add a level of indirection to device naming. - Integration of routing and name resolution, which enables requests for delivery to any optimal service providers (intentional anycast), or to all service providers that match a query. (intentional multicast) - Attribute name entries are cached with expiry times to ensure that entries are up to date INS naming resolution service providers form a dynamically adjusted tree of servers to which application service providers attach themselves and to which clients query. The paper was not too clear on how the tree was to be formed - configuration of all INS servers was to be performed through a centralized Domain Space Resolver. Selection of which nodes to spawn/kill INS seems to be a topic that could be discussed at much greater detail. (Perhaps a distributed scheme such as CEDAR can be used?) The centralization of management presents a bottleneck to a service that is distributed in nature. It seems rather expensive for INS to propagate information about all of the services into the entire network. Every INS nodes has to maintain at least O(n) amount of information, where n is the number of services attaching themselves to the network. Could there be a reactive analogue to INS query/response similar to the difference between DSDV and AODV? The query language for INS seems to be restrictive in what it can represent about the device. In the example query for "printer closest to my friend Alice", would require the user application to locate Alice, and then construct a query for the printer service, which has to have knowledge of location in order to be found. Also, it's not clear whether a service can advertise multiple metrics. I.e. someone might desire to print in the closest printer, another might want the least loaded. It would be nice to be able to combine different information sources (possible through something more intelligent such as an agent?) Also, accuracy of the results depends on the propagation time of the attributes of the services through the INS nodes, which is a periodic diffusion of information. INS implements a caching scheme to maintain information about the services available in the network, which works for their test examples. Cameras and printers don't have a tendency to move around and the dynamic property of the printer is slow in comparison to the updates of the INS network. Also, space is wasted because nodes must cache all possible services it knows about, rather than only services requested. From hs247@cornell.edu Tue Oct 8 00:20:35 2002 Received: from mailout5-0.nyroc.rr.com (mailout5-1.nyroc.rr.com [24.92.226.169]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g984KZh07479 for ; Tue, 8 Oct 2002 00:20:35 -0400 (EDT) Received: from hubby.cornell.edu (syr-24-58-42-130.twcny.rr.com [24.58.42.130]) by mailout5-0.nyroc.rr.com (8.11.6/RoadRunner 1.20) with ESMTP id g984KWp22487 for ; Tue, 8 Oct 2002 00:20:33 -0400 (EDT) Message-Id: <5.1.0.14.2.20021008002024.00b3a9c0@postoffice2.mail.cornell.edu> X-Sender: hs247@postoffice2.mail.cornell.edu (Unverified) X-Mailer: QUALCOMM Windows Eudora Version 5.1 Date: Tue, 08 Oct 2002 00:20:42 -0400 To: egs@CS.Cornell.EDU From: Hubert Sun Subject: 615 Paper 30 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed The Intentional Naming System was introduced in this paper. This allows services to advertise their services and allows clients to discover these services. Along with advertising their name, services advertise their service such as "printer" and also a bunch of attributes which could be "room 110" or "busy" or "low load". The idea is that Clients can then query the system given metrics such as "I want to a printer in room 510". There are 2 components to INS: The INR (the name resolvers) and the INS (clients or services). INRs make up a network which clients can query and services can register with. Each INR periodically floods information about its services to other INR's, and with that information, each INR can figure out routes to each service. How does an INR find out its neighbour INRs? It asks a central server called the DSR. I don't like this method as this relies on a centralised DSR. And when an INR joins the network, how does it know the name of the DSR and how to find it? Supposedly a DSR is well known. With the help of the DSR, the INRs form a spanning tree. As services register themselves with a bunch attributes, the attributes are organised into a hierarchical tree. So one could imagine looking for USA, then New York, then Ithaca. The attributes can then be linked to multiple services. So one could imagine looking for all the bus stops in Ithaca. Clients can then query INR's. If they don't know any attributes, it can request a list of names by sending a name discover request. There are two types of requests: Intentional anycast forwards a request to the best service matching the query (ie. Printer with greatest resolution). An intentional multicast returns a list of names satisfying the query. (Printer with resolution 1200). This paper is very high level. I would have like them to describe how the INR's form a spanning tree. Also, how do clients find the name of the closest INR? How this system fits for an ad-hoc network has to be explored. Is it easily scalable? As all data has to be propagated to all INR's, this can be very expensive. Also, the accuracy of the data is timeout dependent. What if the network is so large that data times out before it finished propagating? We could use the location information described last week as attributes in this naming system. So a printer could say, I am in room 415. As far as querying for the closest printer, the INR can return a bunch of printers with location information. The application on the client can then filter and figure out which location is closest. Otherwise the INS has to have the notion of closest and be able to figure that out that information from the attribute tree. As far as finding the printer closest to Alice, one would have to know where Alice is. Caching may help this, if we cache previous queries and location of clients Ie.) If alice recently made a request given her location, the INS could then infer her location from that. But again, this may only be accurate for a certain amount of time as Alice can move around. From mvp9@cornell.edu Tue Oct 8 00:59:19 2002 Received: from postoffice.mail.cornell.edu (postoffice.mail.cornell.edu [132.236.56.7]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g984xJh14914 for ; Tue, 8 Oct 2002 00:59:19 -0400 (EDT) Received: from zoopark.cornell.edu (syr-24-58-46-186.twcny.rr.com [24.58.46.186]) by postoffice.mail.cornell.edu (8.9.3/8.9.3) with ESMTP id AAA13625 for ; Tue, 8 Oct 2002 00:59:17 -0400 (EDT) Message-Id: <5.1.0.14.2.20021008005805.01aa3610@postoffice.mail.cornell.edu> X-Sender: mvp9@postoffice.mail.cornell.edu (Unverified) X-Mailer: QUALCOMM Windows Eudora Version 5.1 Date: Tue, 08 Oct 2002 00:59:18 -0400 To: egs@CS.Cornell.EDU From: mike polyakov Subject: 615 PAPER 30 Mime-Version: 1.0 Content-Type: text/html; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable The Adjie-Winoto paper presents an integrated resource discovery and location protocol INS.  The Intentional Naming System offers a way for clients to form very complicated queries to describing the type of destination, which can be forwarded to the best or all destinations that fit.  The other benefits of INS include the integration of resolution and routing  which allows for mobility and group communication; self-configurating of name resolvers which also perform load-balancing of the nodes offering services; and reasonable consistency between resolvers.  All transmissions are done with IP unicasts allowing the application thus to fully specify the metric by which a destination is chosen.  The possible late-binding mode offers a client a higher probability of a  smooth transition when a service changes its name-location mapping.  The performance analysis and testing show that the resolvers can handle big loads in reasonable time.
However there are problems with INS that are glossed over in the paper.  The DSR to which all the INS nodes have to refer is a glaring single point of failure/overload.  Furthermore, this is to a large extent a proactive protocol, since the service nodes advertise themselves.  While their analysis focuses on CPU cycles  which may be dominant in some scenarios  in larger networks the service broadcasts and INS updates (which create broadcast storms as described) can wreak havoc on the network.  Although the virtual spaces can alleviate the problem, its still not clear how well it actually scales.  It sounds like, at least for the multicast, routing is done in a form of link-state  how much state is being kept/sent around?
What are the most immediate uses to which we can apply INS?  Besides gathering data from cameras and querying arbitrary maps, it would be nice to combine this with a location service to gather local data.  This is not considered when Floorplan or Printer are discussed, but a simple extension to accommodate this would be to allow a hop/distance specification in the query  so for example the INS would only return the services it has direct knowledge of.  However this would be difficult to extend form a query like the =93printer near Alice=94 unless yo= u know Alice is in room 501.  In other words, the burden is on those nodes advertising services to describe themselves appropriately.  Also, network topology does not have to correspond to physical locations so queries such as that for a local printer could be far off base unless.  In fact, a map (such as Floorplan) would be necessary to say, that if you are in room 101, room 103, which contains a printer is close to you; this could be helped by catching and caching traffic of others, assuming a fairly dense local network and reasonable topology.
 From jsy6@postoffice2.mail.cornell.edu Tue Oct 8 01:02:17 2002 Received: from postoffice2.mail.cornell.edu (postoffice2.mail.cornell.edu [132.236.56.10]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g9852Hh15034 for ; Tue, 8 Oct 2002 01:02:17 -0400 (EDT) Received: from Janet.cornell.edu (syr-24-58-41-193.twcny.rr.com [24.58.41.193]) by postoffice2.mail.cornell.edu (8.9.3/8.9.3) with ESMTP id BAA02286 for ; Tue, 8 Oct 2002 01:02:15 -0400 (EDT) Message-Id: <5.1.0.14.2.20021008005301.00b4ba58@postoffice2.mail.cornell.edu> X-Sender: jsy6@postoffice2.mail.cornell.edu (Unverified) X-Mailer: QUALCOMM Windows Eudora Version 5.1 Date: Tue, 08 Oct 2002 00:53:29 -0400 To: egs@CS.Cornell.EDU From: Janet Suzie Yoon Subject: 615 PAPER 30 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed Intentional Naming System (INS) is a naming system designed for a dynamic and mobile network. INS is suited for applications that describe their intent and not where to find the data. The four main design goals for INS are expressiveness, responsiveness, robustness, and easy configuration. In order to handle a wide range of devices and services, INS uses an intentional name language to allow applications to describe what they are looking for using a hierarchy of attributes and values. The usage of intentional names also allows applications to communicate even during changes in the name to address mapping due to the integration of name resolution and message routing. There are three types of resolutions supported by INS: early binding and two forms of late binding (intentional anycasts and intentional multicast). Late binding maps intentional name and network locations at message delivery time and thus allow seamless communication during service mobility. Integrated resolution and routing is one of the three major contributions of the INS resolution architect. The other two are the self-configuration of resolvers which also incorporate load-balancing and the soft-state name dissemination protocols between replicated resolvers (which provide robustness). Suppose we wanted to find the printer closest to Alice. Since a printer is most likely a static device, one would use early binding with geographic distance as the metric for such a query (I am assuming that by location-independent, location is in reference to connectivity and network topology and not geographical topology. Thus geographical location can be one of the attributes assigned to a device.) The result of early binding would not be inaccurate unless the user is moving while presenting the request for the printer. One problem is that the location of the user (or Alice) along with its distance relative to other services must be known. Thus either a location-service system must be implemented and integrated or distances from one geographical location must be pre-computed and stored. One possibility is pre-computing and caching the relative distance of each room in the building. The user will have his (or Alice's) geographical location in his query. The room location of each device will be embedded in its name. From shafat@CS.Cornell.EDU Tue Oct 8 01:52:33 2002 Received: from exchange.cs.cornell.edu (exchange.cs.cornell.edu [128.84.97.8]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g985qXh24258 for ; Tue, 8 Oct 2002 01:52:33 -0400 (EDT) content-class: urn:content-classes:message MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" Subject: 615 PAPER 30 X-MimeOLE: Produced By Microsoft Exchange V6.0.5762.3 Date: Tue, 8 Oct 2002 01:52:33 -0400 Message-ID: <47BCBC2A65D1D5478176F5615EA7976D134F9F@opus.cs.cornell.edu> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: 615 PAPER 30 Thread-Index: AcJtC0srUuelEHWsSlmVY9JaH4rojg== From: "Syed Shafat Zaman" To: "Gun Sirer" Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from base64 to 8bit by sundial.cs.cornell.edu id g985qXh24258 This paper introduces the Intentional Naming System (INS) which is used for resource discovery and service location in mobile wireless networks. It uses a naming language with the help of which applications can specify what services they are looking for, and INS does the rest to make the connection between the client and service provider. When a client places a service request, Intentional Name Resolvers (INR), which can be any device or computer in the ad hoc network, correspond with each other to carry out a system-wide resource discovery service. Service providers, on the other hand, periodically advertise their services to the INRs that store them in name-trees for a limited time before updating them with new information. The advantages of INS are summarized in its main four design goals: expressiveness, responsiveness, robustness and easy configuration. While the paper does a strong job of describing the naming system, and the algorithms used for resolving names, it does not spend as much time on discussing the INR network. The question of when a device decides to participate as an INR in the network is answered very vaguely. The integrated routing protocol in INS also reminded me of the proactive wireless network protocols we discussed earlier. The initial proposal in the paper, about flooding the network with updated service advertisements is later scraped because of load-balancing and scalability issues. Instead, the virtual spaces concept adopted is quite similar to cluster-based or hybrid protocols. More work can be done on expanding this system to handle larger networks and to use network bandwidth more efficiently. Security also remains a concern in such services and the paper also identifies it as a potential drawback in the current version. The INS naming mechanism has already been successfully implemented in a number of applications that its developers wrote. For example, in the scenario where a user might be wandering around with a laptop connected to a wireless network looking for the nearest printer, she can make a service request to INS to locate an appropriate service. INS, however, has to rely on a secondary application like Floorplan to first learn the client's present location. Every service provider (eg. printers) also has to inform the INRs with an av-pair containing its physical location. If knowing the physical location is not supported in a system, number of route hops to the intended service can be used a criterion to determine the closest service. This however has the possibility of yielding inaccurate results. If a user wants to locate the printer nearest to her friend Alice, the same approach applies. However, Alice first needs to advertise herself in the network by the name of Alice. If she cannot be uniquely identified, it will not be possible for INS to accomplish the task. Also, if there are more than one Alice's on the network, INS will have to let the user have access to the announcerIDs (which is unique) of all Alice's on the network, and choose the one she's looking for. From mr228@cornell.edu Tue Oct 8 03:31:17 2002 Received: from cornell.edu (cornell.edu [132.236.56.6]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g987VGh11825 for ; Tue, 8 Oct 2002 03:31:16 -0400 (EDT) Received: from cornell.edu (pptp-032.cs.cornell.edu [128.84.227.32]) by cornell.edu (8.9.3/8.9.3) with ESMTP id DAA26315 for ; Tue, 8 Oct 2002 03:31:15 -0400 (EDT) Message-ID: <3DA289DA.83CAD4F0@cornell.edu> Date: Tue, 08 Oct 2002 03:31:38 -0400 From: Mark Robson X-Mailer: Mozilla 4.76 [en] (Windows NT 5.0; U) X-Accept-Language: en MIME-Version: 1.0 To: egs@CS.Cornell.EDU Subject: 615 PAPER 30 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit This paper presents the Intentional Naming System. The primary contribution is to demonstrate a system that allows for 'names' to not be bound to a particular host, but rather to a service that the host is providing. The idea being that many applications want to find a host with a certain service and care less about the source. This abstraction allows for several novel improvements over naming schemes where hosts have a more fixed name/address and then announce the services they provide. It allows for multiple hosts to offer equivalent services and the requestor can then seek out whichever it feels is best (with many possible definitions of 'best') Or it could even seek out ALL hosts providing a given service and split the job amongst them. This scheme also automatically gives redundancy and a high degree of tolerance for node failure (in the case that a service is replicated in many places across the network) This is not to say the requestor doesn't care at all about the source. When there some choice about who will service a request, it is probably useful for the requestor to obtain services on node that has the lowest latency to it. This is why the paper discusses integrating routing with INS. If they are integrated tightly enough, it may be possible to find the optimal host for a type of service. Finding the closest printer to my friend Alice may be difficult. INS can find A printer or even ALL the printers, but the problem is with the "closest to" part of the query. What does "closest to" mean? If it means physically (which it probably does) that may not be equivalent to the printer with the lowest latency. So even if INS can get enough information from the low layer routing protocol(s) (and I'm not sure they've demonstrated it can do this), it's not clear how this helps. What we really need to do is integrate this with some of the location-based technology from last time. If the user and the applicable devices both know where they are, the user could figure out which is the closest among the result set. From xz56@cornell.edu Tue Oct 8 04:57:35 2002 Received: from postoffice2.mail.cornell.edu (postoffice2.mail.cornell.edu [132.236.56.10]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g988vZh28106 for ; Tue, 8 Oct 2002 04:57:35 -0400 (EDT) Received: from XIN (ex120.dialup.cornell.edu [132.236.102.120]) by postoffice2.mail.cornell.edu (8.9.3/8.9.3) with SMTP id EAA16099 for ; Tue, 8 Oct 2002 04:57:33 -0400 (EDT) Message-ID: <004601c26ea8$bcf4b4f0$af66ec84@XIN> From: "Xin Zhang" To: "Emin Gun Sirer" Subject: 615 PAPER 30 Date: Tue, 8 Oct 2002 04:54:42 -0400 MIME-Version: 1.0 Content-Type: text/plain; charset="Windows-1252" Content-Transfer-Encoding: 7bit X-Priority: 3 X-MSMail-Priority: Normal X-Mailer: Microsoft Outlook Express 6.00.2600.0000 X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2600.0000 The paper introduced the Intentional Naming System (INS), which combines name resolution and routing and is very suitful for mobile networks. Quite naturally it uses attribute-value pair to name services. But instead of use early binding (INR returns IP addresses of servers. This is still an option), it uses late binding, i.e. INR forwards the packet directly to server. This makes the communication between client and server more reliable. INRs, maintained by DSRs organized into a connected network. Periodical propagation of naming info by all INRs insures the freshness of resource info. The automatically prawn and deletion of INR, introduction of virtual spaces among INRs make the load of INRs balanced and the system more scalable. In the scenario of location-aware, the early binding maybe more efficient than late binding, when INR knows the location of servers, because INR could choose the server nearest to the client, in stead of detour through itself (although it will choose the nearest server to itself). So the "nearest printer" may not be offered by INS working in late binding state. While "the nearest printer to Alice" should be correct assuming that the INR knows the location of both Alice and printers. Caching will only be helpful, as it is always, when the network is of low mobility. From vrg3@cornell.edu Tue Oct 8 09:58:50 2002 Received: from travelers.mail.cornell.edu (travelers.mail.cornell.edu [132.236.56.13]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g98Dwoh04863 for ; Tue, 8 Oct 2002 09:58:50 -0400 (EDT) Received: from travelers.mail.cornell.edu (travelers.mail.cornell.edu [132.236.56.13]) by travelers.mail.cornell.edu (8.9.3/8.9.3) with SMTP id JAA11993; Tue, 8 Oct 2002 09:58:47 -0400 (EDT) Date: Tue, 8 Oct 2002 09:58:47 -0400 (EDT) From: vrg3@cornell.edu X-Sender: vrg3@travelers.mail.cornell.edu To: egs@CS.Cornell.EDU Subject: 615 PAPER 30 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII This paper presents the Intentional Naming System, INS. INS is a way to refer to nodes in a network based on their attributes, such as their capabilities, types of services offered, or location. It has three modes of operation from a client's point of view: in one, the client can simply give a resolver a name and receive a network address of a node which satisfies the name request. Subsequent communication can be done directly with that node. This is called early binding. The remaining two options are late binding, meaning the resolver also behaves as a router, binding the name to a network address only when routing. Intentional anycast is a late-binding option where the resolver/router forwards the message to any node which satisfies the given name. Intentional multicast has the message forwarded to all nodes which satisfy the name. The resolver/routers maintain a network configuration overlayed on the existing IP network and communicate with a partially centralized Domain Space Resolver. The naming scheme used in INS is based on a hierarchical attribute-value tree. Orthogonal attributes are siblings on the tree, and in general attributes are only meaningful in the context of their ancestors' values. This scheme is amended a bit by the introduction of virtual spaces, which are used to allow the system to scale. It is unclear how the general tree and the list of virtual spaces are decided upon. The biggest limitation that I see immediately in INS is the restriction of names to attribute-value pairs. It seems to me that many times you would want to be able to impose an ordering on the values a particular attribute might have, so you could request minimal values or place bounds on acceptable values. Currently there is an implementation of a metric of some kind, which appears to be used only by the routers. The mixture between distributed and centralized management is also a little disconcerting. INS does not directly support a request like "the nearest printer" or "the printer nearest Alice." Even assuming you had a "location" attribute defined for every object, there is no notion of locations that are near other locations. The authors of the paper have implemented a Locator service for INS which allows a client to construct the necessary information at the application level. From mp98@cornell.edu Tue Oct 8 10:45:36 2002 Received: from postoffice.mail.cornell.edu (postoffice.mail.cornell.edu [132.236.56.7]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g98Ejah16002 for ; Tue, 8 Oct 2002 10:45:36 -0400 (EDT) Received: from cornell.edu (r109493.resnet.cornell.edu [128.253.240.252]) by postoffice.mail.cornell.edu (8.9.3/8.9.3) with ESMTP id KAA06407 for ; Tue, 8 Oct 2002 10:45:35 -0400 (EDT) From: mp98@cornell.edu Date: Tue, 8 Oct 2002 10:45:34 -0400 Mime-Version: 1.0 (Apple Message framework v546) Content-Type: text/plain; charset=US-ASCII; format=flowed Subject: 615 Paper 30 To: egs@CS.Cornell.EDU Content-Transfer-Encoding: 7bit Message-Id: <99D80E16-DACC-11D6-BD49-003065EE5F0A@cornell.edu> X-Mailer: Apple Mail (2.546) This paper describes an intentional naming system, a system in which services advertise their capabilities to resolvers, allowing clients to make queries for the items they want. The services are described as a name-specifier, which is a tree hierarchy of attribute-value pairs. All the name-specifiers joined together form a name-tree at an Intentional Naming Resolver (I suppose there must be some authority on the ordering of attributes in a name specification or else one could get loops when merging them into a name-tree). Clients can request from a router, name resolution (receives the location of a service corresponding to the user's request), intentional anycast (the user's message is sent to one service matching the request [useful for printing]), and intentional multi-cast (the routers disseminate the request to all matching services. New resolvers join the network by connecting to their nearest neighbor and new services are advertised to resolvers via flooding. Coupled with Cricket, such a system would allow one to use one's location for requests (i.e. Nearest ethernet jack to the beacon I am nearest) if one could have location attributes with Cricket beacon attributes. Coupled with a system such as radar, one could actually make requests concerning other wireless users (i.e. tell me which server is closest to the guy I want to send a file to). Caching here is only as useful as the mobility of the user. Another interesting application would be mobile nodes advertising services based on their location. Here, one needs to carefully time the periodic updates of INR to account for mobility while avoiding flooding (in the case of Radar names, searches of the name tree would need to use a range comparison.) From liuhz@CS.Cornell.EDU Tue Oct 8 10:53:59 2002 Received: from exchange.cs.cornell.edu (exchange.cs.cornell.edu [128.84.97.8]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g98Erxh17492 for ; Tue, 8 Oct 2002 10:53:59 -0400 (EDT) content-class: urn:content-classes:message MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" Subject: 615 PAPER 30 X-MimeOLE: Produced By Microsoft Exchange V6.0.5762.3 Date: Tue, 8 Oct 2002 10:53:44 -0400 Message-ID: <706871B20764CD449DB0E8E3D81C4D4302CEE65D@opus.cs.cornell.edu> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: 615 PAPER 30 Thread-Index: AcJu2n/zuOxO/VBqRXexUgPSsQe/6A== From: "Hongzhou Liu" To: "Gun Sirer" Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from base64 to 8bit by sundial.cs.cornell.edu id g98Erxh17492 This paper presents the design and implementation of the Intentional Naming System(INS), a resource discovery and service location system for dynamic and mobile networks. INS uses a simple language based on attriutes and values for its names. Applications use the language to specify what they are looking for, not where to find data. INS supports three kinds of resolutions: ealy binding and two forms of late binding. Ealy binding works just like traditional hostname-to-IP resolution and returns a list of IP address according to a name. Late binding has two forms: intentional anycast and intentional multicast. Intentional anycast forwards messages to the node that satifies a name query and is the best one according to some application-controlled metric, while intentional multicast routes messages to all the nodes that satisfies a query. Late binding mechanism integrates name resolution and message routing, enabling clients to continue to communicate with end-nodes even if the name-to-address mapping changes during a session. INS implements intentional names using expressions called name -specifiers. In INS, all the applications(clients and services) are connected by a overlay network consisting of INRs. A service is named by a name-specifier. A name-specifier is a hierachical arrangement of av-pairs such that an av-pair that is dependent on another is a descendant of it. Thus a name-specifier is a tree structure consisting of av-pairs. Each DSR maintains a name tree, which is a data structure used to store the correspondence between name-specifiers and name-records. When the DSR receives a request that contains the end-node's name-specifier, it lookups the tree and finds out the IP address of the end-node and other routing information which are all contained in the name-record. In INS, INRs rely on the application-level overlay network to propagate updates and forward data to services and clients. This overlay network is constructed in a distributed way by INRs self-configuring to form a spanning tree based on metrics that reflect INR-to-INR round-trip latency. A well-known entity in the system called the Domain Space Resolver(DSR) is used to maintain the list of all the active and candidate INRs. If an INR wants to join the network, it should notify the DSR and use DSR-ping to measure the latency between each node already in the network and itself. Then it finds the "nearest" node and constructs a link to it. An INR is able to spawn another INR to share its load and delete itself from the network if its load falls below some threshold. Thus the network is highly self-configured and eases administration. Services advertise their intentinal names periodically to the connected DSR. Name information is propapated through the DSR overlay network rapidly. Each DSR stores this name information in an cache entry with some expire time. This entry is refreshed periodically by the service advertisements. However once the service doesn't exist, the cache entry will expire very soon. Thus applications may join and leave the INS system freely, without any registration and de-registration. INS is suitable for mobile ad hoc network due to its self-configuration. However, the period advertisement caused packet flood may make some troubles in such network. Requests ike finding "the nearest printer" or "the printer closest to my friend Alice" can be satisfied easily in INS since the anycast metric is totally under applcation's control. However, this requires some help from localization system to find out the "my" location and Allice's location. Besides, metric like "distance to my friend Alice" seems quite odd in routing circumstance. To improve performance, we can cache data packets in INRs. Intentional names made the design of application-independent caching rather simple. The name-specifier itself is a very good handle for a cached object. However, we need to decide the expire time for the cached objects very carefully to optimize performance. From kwalsh@CS.Cornell.EDU Tue Oct 8 11:02:31 2002 Received: from duke.cs.duke.edu (duke.cs.duke.edu [152.3.140.1]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g98F2Vh19391 for ; Tue, 8 Oct 2002 11:02:31 -0400 (EDT) Received: from localhost (larry.cs.duke.edu [152.3.140.75]) by duke.cs.duke.edu (8.9.3/8.9.3) with ESMTP id LAA03145 for ; Tue, 8 Oct 2002 11:02:30 -0400 (EDT) From: kwalsh@CS.Cornell.EDU Received: from 132.236.29.70 ( [132.236.29.70]) as user walsh@imap.cs.duke.edu by login.cs.duke.edu with HTTP; Tue, 8 Oct 2002 11:02:30 -0400 Message-ID: <1034089350.3da2f38691fcd@login.cs.duke.edu> Date: Tue, 8 Oct 2002 11:02:30 -0400 To: egs@CS.Cornell.EDU Subject: 615 PAPER 30 MIME-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 8bit User-Agent: Internet Messaging Program (IMP) 3.0 X-Originating-IP: 132.236.29.70 The design and implementation of an intentional naming system. INS: The system attempts to be too many things at once, but presents several interesting ideas. The naming mechanism in INS is fairly general, but primitive. A name consists of a heirarchy of attribute-value pairs. A downfall of this approach is that it appears to need one-time global configuration. Once the heirarchy is chosen, it looks difficult to add new attributes, modify the meaning of existing attributes, or deprecate unused attributes. Currently the only matching permitted is '=', so it would be rather difficult to express a query such as "nearest printer". The paper gives an example using an attribute- value pair "room=311". This is clumsy, and fails if the printer is not found. One could use an expanding ring search: "room=311" followed by "floor=3", etc, but this has poor granularity (unless the names were extremely descriptive). A better match might be to augment the matching algorithm to use a "nearest" operator (possibly even using cartesian location coordinates): "floor=3 & location~=(10,5)". INS does not appear to benefit from caching of name resolution data, since names are expected to change frequently. Indeed, if names incorporate attributes such as current load, location, or error status, then name changes would be the rule rather than the exception. Caching becomes difficult in this situation. Despite its interesting approach, INS does not appear to be directly applicable to ad hoc networks (as described in this paper). A central node coordinates the overlay network, and very little thought is given to routing and connectivity changes, which are very common in ad hoc networks. Node "mobility" in this paper seems to mean "occational changes in ip address" rather than "frequent network topology changes". From yao@CS.Cornell.EDU Tue Oct 8 11:06:08 2002 Received: from exchange.cs.cornell.edu (exchange.cs.cornell.edu [128.84.97.8]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g98F68h20338 for ; Tue, 8 Oct 2002 11:06:08 -0400 (EDT) content-class: urn:content-classes:message MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" Subject: 615 PAPER 30 X-MimeOLE: Produced By Microsoft Exchange V6.0.5762.3 Date: Tue, 8 Oct 2002 11:06:08 -0400 Message-ID: <706871B20764CD449DB0E8E3D81C4D4302ED4C49@opus.cs.cornell.edu> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: 615 PAPER 30 Thread-Index: AcJu3DscYD7DdNgMSX62vDg7x6LMwA== From: "Yong Yao" To: "Gun Sirer" Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from base64 to 8bit by sundial.cs.cornell.edu id g98F68h20338 The INS paper presents how to design and implement a resource discovery and service location system for dynamic and mobile networks. Four design goals of such a system are expressiveness, responsiveness, roubstness, and easy configuration. The main contributation of the paper is to propose routing by name, instead of IP address. It is a resonable assumption in ad-hoc network, which consists of large amount of mobile nodes. What is interesting to a user is the resource or information available in the network, instead of the location of them. That is the reason why content-based routing matches more closely to the application requirements. The architecture of INS supports three different methords to resolve the destination name. Similar to DNS, early-binding will returns a list of IP addressed to the name directly from an INR; while there are also two late binding options. In intentional anycast scheme, the INR forwards the message directly to one of the end-point with the least metric, which is usually application dependant; while in intentional multicast, the INR forwards the message to all potential end-points. Names are expressed as name-specifiers, each of which has both the attribute and the value. Name specifiers are organized hierarchically, and can be represented as strings in a message header. A potential problem of INS is its overhead. Consider a scenario where data sizes are small but updates are frequent. Everytime the value or the attribute of an event changes, an update message is broadcast to every INS in the network. If user requests are less frequent than event updates, a better solution could be to broadcast user requests instead of the updates. How to scale INS to larger networks is another problem. To name objects like "the nearest printer" or "the printer closest to my friend Alice" in INS, the system can add an location attribute to the objects, including printers and people, then definet the metric of an end-point as the distance between the person and the printer. Yong From smw17@cornell.edu Tue Oct 8 11:13:34 2002 Received: from cornell.edu (cornell.edu [132.236.56.6]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g98FDXh21550 for ; Tue, 8 Oct 2002 11:13:33 -0400 (EDT) Received: from cornell.edu (syr-24-161-107-202.twcny.rr.com [24.161.107.202]) by cornell.edu (8.9.3/8.9.3) with ESMTP id LAA11576 for ; Tue, 8 Oct 2002 11:13:33 -0400 (EDT) Message-ID: <3DA2F544.1080901@cornell.edu> Date: Tue, 08 Oct 2002 11:09:56 -0400 From: Sean Welch User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.0; en-US; rv:0.9.4.1) Gecko/20020508 Netscape6/6.2.3 X-Accept-Language: en-us MIME-Version: 1.0 To: Emin Gun Sirer Subject: 615 PAPER 30 Content-Type: text/plain; charset=us-ascii; format=flowed Content-Transfer-Encoding: 7bit Intentional Naming System - The Intentional Naming System (INS) is a naming methodology intended to combine resource discovery and routing into a single service/system. The end system is similar in some respects to DNS, in that there is a pre-defined well-known server (the DSR) that coordinates the creation and matinence of the Intentional Naming Routers (INR) into a well-defined tree. Node attributes are application-specified attribute-value pairs (av pairs) arranged heirarchically into a tree structure layered above the IP layer in the network stack. The protocol operates in close conjunction with the application layer, with applications specifying av pairs, routing metrics, and providing the periodic service updates necessary to maintain freshness in the INS network. User applications provide the naming services with the intended service rather than a network address, and the INS makes its best effort to deliver the message to the optimal host or to the defined subset of nodes matching the naming criteria. INS operates in close conjunction with the application layer, which is responsible f.or defining attributes and metrics in a way that makes this system useful The INS implements a routing protocol based on the services requested and the advertised application metrics. While this may be reasonable in the average static case, the proactive, centralized network creation and matinence limits the applicability of the presented algorithm to more mobile situations. In addition, while it is undoubtedly easier to push the problem of metrics up to the application layer, it does not make the problem inherently simpler. A user looking for the nearest printer, for instance, would most likely prefer a printer two rooms down over a physically nearer printer on a lower floor. The examples presented are deciptions of largely static networks, such as a camera in the white house. Extending this mechanism to mobile nodes will likely require a more sophisticated routing and update algorithm to achieve reasonable performance. Active Names - Active Names is another mechanism for resource/service discovery and transport through naming control. In contrast to the INS system, the Active Names protocol achieves the routing by distributing the routing and processing throughout the network. Each routing path is comprised of (potentially) a series of name resolution steps at various resolver nodes throughout the network. These are distributed, location independent functions that, when applied in a series, provide the routing functionality. The advantages of an active naming scheme are that it allows for a very flexible, extensible system capable of encompassing many different types of services, it provides for distribution of various tasks throughout the network, potentially permitting better tradeoffs between processing required and transmission bandwidth, and allows the client to define after methods to apply to the returned data to make better use of available resources. Active names are an interesting concept. Distributing the load in a dynamic manner should allow the Active Names system to be more applicable in high-mobility situations than INS. In addition, the location independent functional behavior could also be advantageous in heterogeneous networks or highly congested networks by adjusting the load distribution based on actual or measured capacity. Unfortunately, dynamic distribution of executable code imparts a number of problems. First off, an active network system must be comprised of nodes capable of executing platform-independent code. While this may not be a problem for PC-type systems in wired networks, extending this to an ad-hoc PDA network may have a significant impact on the networked machines. Secondly, there are a number of security concerns inherent in allowing arbitrary code to be distributed as part of a routing protocol. Even with secure authentication, a single compromised system may be capable of infecting numerous other systems also running an active name system. Maintaining acceptable levels of system security becomes a more difficult problem when running active names schemes, especially in the case of a standardized routing architecture with a standard hardware and software configuration. Finally, there is the same problem in an active naming system as in the INS discussed above. While Active Names does provide a distributed mechanism to distribute the routing load for better performance, it does not solve the basic problem of how to convert traditional routing metrics into user expectations without explicit outside information. Semantic Filesystems - Semantic Filesystems are a filesystem interface that modifies the traditional file system tree to create a virtual filesystem. This virtual filesystem is composed of files combined with a collection of transducers, which are special programs that can extract the set of attributes from a given type of file. Examples presented include author for text files, imports and exports from various types of code files, and {from, to} attributes from mail files. Accessing the semantic file system includes a query implicit in the file reference that searches the transducer outputs for files matching the quieried attributes. Multiple conjunctive searches are permitted, but disjunctive searches had not yet been implemented. Recent searches are cached for improved performance, and only partial re-indexing is performed during operational updates and modifications, with scheduled full re-indexing. Semantic filesystems are an idea that may actually be better suited to network resource discovery than to filesystems as presented here. In networks, the larger latency for data transmission and lower bandwidth may make the implementation of query-based more attractive, especially in ad-hoc networks where the cost of at-node processing is less than that of transmission over a wireless link. This is similar to the intentional naming system, where the transducers have been replaced with application defined values and metrics, and where the filesystem has been replaced by a resource naming scheme. a) Rapid/Harsh Environment Sensor Networks - concept - Enable the rapid deployment of lightweight sensor nodes, potentially in hostile or remote locations that make conventional deployments unattractive (some similarities to smart dust systems). - Active networks may have some attractive implementations in heterogeneous systems by allowing more powerful nodes to take on more of the communications processing loads. INS does not appear particularly advantageous for this style of network. b) Appliance Networks - Concept - Enable intelligent appliances and industrial systems capable of inter- system coordination for better resource use - Intentional naming schemes may be a useful abstraction in these types of networks, as the name structure itself is conducive to specifying and locating different systems and classes of systems with minimal load to the devices themselves. This concept may permit better integration of low computational power devices into a heterogeneous network (such as a factory floor or home kitchen) at the cost of some initial setup or pre-defined discovery script. Active naming may also be useful, as it provides a mechanism both to offload processing from relatively dumb devices as well as a means to distill returned data into a more efficient form based on the desired return destination. c) Intelligent Resource Detection and Utilization - Concept - Provide meaningful interface to human users, such as 'print to closest printer' rather than 'print to device attached to node 172.22.5.233'. - Naming Systems - The naming systems suggested above can be used to support some degree of intelligent resource use. The critical issue in the case of the INS is that the quality of the results will depend heavily on the intelligence of the application layer controlling it. The command "find the nearest printer" is a fairly simple concept to a human, but defining its precise meaning in a heterogeneous computing environment is considerably more involved. Using the example of a hybrid wired/wireless network, any application implementing a hop count will see considerable variation in the number of hops per meter of 'real' distance, and may still return a printer that is physically close but inconvienient. The translation of simple user concepts and seperation of nodes into useful subdivisions (such as the set of nodes present in a room) without external sources of information is not provided by either scheme. Active Names suffers from a similar problem. It may be possible to do better than INS by delaying more precise determinations until you are closer to the destination (where persumably more, better information may be available), but there is still the exact issue mentioned above. Neither system provides an improved mechanism for resolving the translation of human language concepts into effective algorithms, but merely pushes the issue to higher level protocols and explicit knowledge. d) Movement Aware Routing - Concept - Use the location information to judge the movement rate, and to estimate when link breakage is probable. From here, schemes such as intelligent route invalidation and link forwarding/handoff can be implemented. - Pseudo-static routes - From the network information, provide a mechanism for nodes to identify and make efficient use of relatively stationary, stable routes. - More a network connectivity issue below the IP layer, with little interplay with these naming schemes. e) Adaptive Link Adjustment - Concept - Use geographic feedback and either directional or adjustible power systems to improve link coverage in sparse areas - Again, more an issue of network connectivity (PHY/DLC/MAC), sitting well below the area affected by these naming protocols. Caching - Both systems can potentially benefit from caching to improve overall system performance. The INS structure makes caching relatively simple to implement, as the data streams are referenced in a relatively clear, unambigious manner. The basic cache here is not particularly different from a standard cache with regards to data content, but the naming structure inherent in INS may well provide more efficient use of the cache for popular repeating or often updated data sources. Active names can also benefit from caching, and additionally includes the possibility to utilize downstream caches as a simplistic form of a dynamic server. By caching not only the data, but enough program functionality to implement some basic functions, the authors suggest that cache performance may improve significantly over simple static caches. They suggest that implementing an active cache through their active naming system may increase the utility of web caches, traditionally of limited effectiveness, by also caching and offloading some limited functional complexity (for instance - an ad determination function for banner ads). From tmroeder@CS.Cornell.EDU Tue Oct 8 11:46:33 2002 Received: from dhcp99-233.cs.cornell.edu (dhcp99-233.cs.cornell.edu [128.84.99.233]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g98FkXh29522 for ; Tue, 8 Oct 2002 11:46:33 -0400 (EDT) Received: (from tmroeder@localhost) by dhcp99-233.cs.cornell.edu (8.11.6/8.11.6) id g98Fin002510; Tue, 8 Oct 2002 11:44:49 -0400 From: Thomas Roeder MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Message-ID: <15778.64881.192463.459326@dhcp99-233.cs.cornell.edu> Date: Tue, 8 Oct 2002 11:44:49 -0400 To: Emin Gun Sirer Subject: 615 PAPER #30 X-Mailer: VM 7.07 under Emacs 21.2.1 The intentional naming system seeks to provide access to services dynamically, and with respect to the users' intent rather than the network location of the service. They allow both early and late binding of the names to more standard addresses, and, most interesting to our commentary, allow what they call "intentional anycast" to send a request to the machine which satisfies some metric specified by the user, whether application load, geographical proximity, or some other metric, which must, nonetheless, be known to the service in question. They use Distributed Bellman Ford to make the connections between the INS resolvers at runtime, which has its own particular set of problems, and the security issues are worrisome, as is the question of convergence. Nonetheless, these are not the questions we are to address here. Assuming some knowledge of geography, (for instance using the localization services considered last week, although if the user is familiar with the environment, the "localization" could consist simply of well-known strings, like "Upson 4158", if there happened to be printers there) the specification of the "nearest" printer is fine...one can simply say, "I know that I am in room blah, and that the nearest printer is in room foo, so I'll request my job printed there". These results could be quite inaccurate for a couple reasons. For one, it sometimes relies on user knowledge (even in the localization schemes considered above, if there are no servers of the type we want in our known area, there is no way to find the nearest one outside our area), and further, it does not allow us to discover other, perhaps nearer servers of the same type. The INS could be extended to compute geographical nearness as one of the metrics, but it would require complicity from a localization protocol. To specify "the printer nearest Tom", we would further need to have a way to know where the users are. In some of the systems last week, there was no explicit way to do this, and the users must be complicit in allowing their peers to know their locations (personally, this is my preferred environment anyways). There is no clear way to specify this query in INS, unless "Tom" tells the printer to say that it's near him. Furthermore, if the servers move (which is a strange thought in the case of printers, but more common if it were applied to, say robots), then the results might have been correct a moment ago, but are not anymore. Caching would serve us well here to prevent the continued rediscovery of services; the INS resolvers could initiate discovery on-demand, and get information from the caches of INR's closer to the service, which have already discovered this service. The main case in which this would buy us performance is with services like printers, where they are unlikely to move significantly. From ag75@cornell.edu Tue Oct 8 12:11:03 2002 Received: from travelers.mail.cornell.edu (travelers.mail.cornell.edu [132.236.56.13]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g98GB2h05370 for ; Tue, 8 Oct 2002 12:11:02 -0400 (EDT) Received: from travelers.mail.cornell.edu (travelers.mail.cornell.edu [132.236.56.13]) by travelers.mail.cornell.edu (8.9.3/8.9.3) with SMTP id LAA22520 for ; Tue, 8 Oct 2002 11:43:36 -0400 (EDT) Date: Tue, 8 Oct 2002 11:43:36 -0400 (EDT) From: ag75@cornell.edu X-Sender: ag75@travelers.mail.cornell.edu To: egs@CS.Cornell.EDU Subject: 615 PAPER 30 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII In this paper we are introduced to Intentional Naming System (INS), a resource discovery and service location system. INS allows applications to describe what they are looking for, not where to find things. In order to do this applications have to use the system's query language, which is simple and has a small set of commonly used operators. Based on the application's request, INS selects services that satisfy it and picks the one (or all if we have a multicast) with the best metric, which is also specified by the application. INS then forwards the message to the service that the application wanted to use. This late binding mechanism that integrates name resolution and message routing, enables applications to communicate with services even if the name-to-address mappings change while a session is in progress. In order to do all this, INS uses Intentional Name Resolvers (INRs). The description of how the INR network works is fairly high level, but we do know that periodic and triggered updates are used to keep the entries up to date, which makes update scalability a serious concern. Additionally, the name lookup also suffers from scalability problems as the algorithm is exponential. While INS allows the applications to specify what they want, it will not work for all applications discussed last week. One can easily imagine it work for such things as providing a floor map or finding a book. However, when you want to locate a specific service INS is not flexible enough. It will allow you to specify absolute position of the service that you want (room 510 (by specifying this attribute) or printer closest to me (by making the metric be smallest distance)), but it will not allow you to specify a position relative to something (printer to my right). From pj39@CS.Cornell.EDU Tue Oct 8 12:50:06 2002 Received: from postoffice2.mail.cornell.edu (postoffice2.mail.cornell.edu [132.236.56.10]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g98Go6h14954 for ; Tue, 8 Oct 2002 12:50:06 -0400 (EDT) Received: from cornell-yb3go20.cornell.edu (syr-24-59-67-50.twcny.rr.com [24.59.67.50]) by postoffice2.mail.cornell.edu (8.9.3/8.9.3) with ESMTP id MAA14105 for ; Tue, 8 Oct 2002 12:50:04 -0400 (EDT) Message-Id: <5.1.0.14.2.20021008124825.02462c80@postoffice2.mail.cornell.edu> X-Sender: pj39@postoffice2.mail.cornell.edu (Unverified) X-Mailer: QUALCOMM Windows Eudora Version 5.1 Date: Tue, 08 Oct 2002 12:50:11 -0400 To: egs@CS.Cornell.EDU From: Piyoosh Jalan Subject: 615 PAPER 30 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed The design and implementation of an intentional naming system. This paper on intentional naming system (INS) describes a naming system for mobile wireless networks consisting of devices and computers. It is used for locating services and resource discovery. The four goals of INS are expressiveness, responsiveness, robustness and easy configurability. In an INS network a few nodes are designated Intentional Name Resolvers (INRs) whose work is to route client requests to appropriate services. INRs form an overlay network to exchange service descriptions and construct a local cache based on these advertisements. INRs uses two schemes for routing client requests namely early binding and late binding. In early binding the INR returns a list of IP addresses corresponding to the name of the service requested, the client may select a node based on some least metric. In the late binding scheme INR has two approach, intentional anycast and intentional multicast. Here instead of returning the IP addresses, INR forwards the application payload directly to the services. For anycast the INR tunnels the message to one of the service nodes and for the multicast scheme INR forwards it to all next hop INRs associated with the service name and thus message is forwarded to all the final destination nodes using the INR overlay network. The INRs self configure's into a spanning-tree overlay network topology using INR-to-INR round trip time (RTT) measurements. In INS clients use name-specifiers to query an INR for a service location. Name specifiers are attribute value (av) pairs. Services advertises their names with the INRs. One problem with this approach is how will a new client which joins the network know the service name without a default conventions. One solution mentioned in the paper is the client would send a name discovery message to an INR specifying an intentional name for the INR to match with all the names it knows. In the INS overlay network INRs periodically beacons name information for each other. Apart from this INRs also initiates a triggered update when it receives an update from one of its neighbor containing new information. INRs resolve name-specifiers to corresponding network locations with the help of name trees. The lookup returns name record consisting of IP address of the service provider as well as routes to next-hop INRs. One of the drawbacks of this paper is it does not describe how the INRs are chosen and whether they are one of the clients or service providers or dedicated nodes like routers in a subnet. Security issues are not addressed properly. INR nodes are heavily loaded nodes, hence the issue of load balancing related to this needs to be discusses. Scalability issue also needs a mention like when the network is scaled to a very large size whether its performance degrades and if yes to what level. Locate "the nearest printer" or "the printer closest to my friend Alice" The nearest printer could be located with the existing protocol. The INRs already maintains the metric of the routes and hence for a particular service like nearest printer it can first get records corresponding to attributes type printer and than choose the record with lowest metric for routes. For querying "the printer closes to Alice" the protocol will fail and produce inaccurate results. However the protocol could be modified so that all the client too periodically advertises themselves with their names to INRs and INRs maintain metrics for these clients and during periodic/triggered this information is also shared with other INRs and hence based on this information the INRs can route the request to the nearest printer to a particular client in this case "Alice". From ashieh@CS.Cornell.EDU Tue Oct 8 12:52:44 2002 Received: from zinger.cs.cornell.edu (zinger.cs.cornell.edu [128.84.96.55]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g98Gqih15265 for ; Tue, 8 Oct 2002 12:52:44 -0400 (EDT) Received: from localhost (ashieh@localhost) by zinger.cs.cornell.edu (8.11.3/8.11.3/C-3.2) with ESMTP id g98Gqia27795 for ; Tue, 8 Oct 2002 12:52:44 -0400 (EDT) Date: Tue, 8 Oct 2002 12:52:44 -0400 (EDT) From: Alan Shieh To: Subject: 615 PAPER 30 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Answers to posted question: INS Last week's applications: * Location-indexed information retrieval - These service discovery systems allow information (such as goals) to be specified generically. When a user approaches an area with services that match a generically specified goal (such as take a picture of a particular thing while on vacation, restock office supplies), then the appropriate entry can be recalled from a PIM. Some care must be taken with the implementation, since the naming systems are pull-only, which may require either constant broadcast of queries from the client, or transmitting a huge chunk of naming information at once. Alternatively, the naming systems could be adapted to support pushing of service information that is interesting to the client. * Dynamic collaboration groups - Everyone willing to participate in a discussion about a particular topic can advertise their interests and location to a service-discovery system. * Inventory/personnel management - INS allows each pallet or employee to be categorized in several ways simultaneously, e.g. location, availability, knowledge or contents. * Shopping agent - Works very naturally, since INS supports hierarchical information. A shopping area is naturally arranged in a hierarchical manner, with shopping center->stores->departments->aisles. INS provides an indirect mechanism for answering queries about services close to the querying node without help from the naming schema, since services advertise themselves to the closest INR. However, this is unreliable because it is sensitive to network load. A more effective approach would be to encode the positions of static services such as printers in their name. To support expanding ring search, this positional information must be encoded hierarchically (e.g. room, corner of floor, floor). As described in the paper, INS does not provide direct mechanisms for nearest match, and so using coordinate tuples would require client-side filtering. If a client wished to know the location of a service relative to another client, the other client would need to advertise its location. The temporal accuracy of all searches is contingent on the latency of service advertisement propagation. Given that the correct information is returned, then accuracy is dependent on the schema used to encode the position information. SFS In terms of expressive power of queries and names, INS is reducible to SFS: for names, encode the tree position of an attribute in the name of a key; for queries, strip off wildcards and flatten the search structure as stated above. This reduction works correctly because INS patterns are simple. SFS is trivially reducible to INS. The difference between the two systems is their relative performance. Since the reduction can be performed server-side, there is no packet size increase with converting an INS query to SFS. Moreover, the conversion is single-pass and fast. However, the index lookup would likely take longer for SFS because it does not directly exploit the tree structure. A higher-level difference are the caching models. SFS maintains hard state, while INS retains soft state. Hence, SFS is more likely to have stale information. Replication would work for SFS, since updates can be performed using NFS operations; modulo the staleness of the hard state and query time, the two systems should have similar performance (in terms of accuracy and speed) under replication. ** Contributions The INS paper contributes a self-configuring naming system with flexible semantics. While control is centralized in DSRs to allow services, INRs, and clients to find their closest INR, this is a mostly stateless, read-only operation (except when more INRs are allocated, or load-balancing is attempted), and so DSRs are easily replicable. More importantly, INS provides a flexible naming system which supports hierarchical, domain-specific service descriptions. Although its wildcard matching in queries is somewhat primitive (limited tree matching capabilities), with a properly defined schema one is able to find different sets of matches (categorized along different axes) from the same dataset, e.g. all cameras in a building, or all devices in a given room of a building. Both permanent and transient device attributes may be transparently encoded in either the name or the discovery metric, allowing the client application to use naming information choose between otherwise identical services without needing to directly query the service. Lazy binding between query and service allows for long-running or highly mobile applications to transparently receive a certain type of service; however, see below for possible shortcomings. ** Shortcomings The performance analysis does not provide information about how well the system scales in the presence of heavy lazy binding. Lazy binding seems to be too transparent in their processing model: since their pattern matcher is not particularly sophisticated, it is likely that a client will need to check the results before conducting an anycast or multicast. A redefined multicast group may need to be rechecked. Moreover, they do not point out that lazy binding imposes significant restrictions on the application. There is no mechanism provided for propagating state between services when the binding changes. Service advertised are flooded proactively through the network, instead of being propagated on-demand. ** Future work - Allow client to specify more exact matches for lazy binding; e.g., use a second pattern matcher over the results of the simple pattern matcher. The resulting multicast can be cached within the INR network for performance. - Investigate naming schemas for services; these will likely have to be defined carefully to avoid problems with the simple pattern matcher. Detailed description: INS (Intentional Naming System) is a self-configuring naming system for service discovery. A centralized (easily replicatable) DSR (Domain Space Resolver) maintains a list of all name servers (INR - Intentional Name Resolvers). A simple distributed algorithm constructs an overlay spanning-tree network of INRs, which is used for control and application data multicast. A node with an attached service uses the DSR to find the closest INR, and sends the service advertisement to the INR. The INR multicasts this information to all other INRs. To improve scalability, the paper proposes defining a domain-specific partitioning of services into "virtual spaces"; this reduces the cost of naming updates and provides loadbalancing for application-directed multicast. Since all state is automatically expired from the INR naming caches, advertisements must be made periodically. Services are hierarchically named by trees of attribute-value (av) pairs. Av pairs are children of the pairs upon which they depend, and siblings of those with which they are orthogonal. Name queries are performed using patterns that may contain wildcards. For efficiency, a simple tree-matching algorithm is used. It treats wildcards as matching complete subtrees; patterns cannot be constructed with wildcards in the middle of a path. Queries are returned in an order imposed by an application-defined metric (e.g. spool length). The returned bindings may be lazy, in which case application packets are routed through the INR network to the most current set of matches. From sc329@cornell.edu Tue Oct 8 13:01:12 2002 Received: from postoffice2.mail.cornell.edu (postoffice2.mail.cornell.edu [132.236.56.10]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g98H12h17386 for ; Tue, 8 Oct 2002 13:01:12 -0400 (EDT) Received: from sangeeth.cornell.edu (syr-24-58-36-135.twcny.rr.com [24.58.36.135]) by postoffice2.mail.cornell.edu (8.9.3/8.9.3) with ESMTP id NAA26893 for ; Tue, 8 Oct 2002 13:01:01 -0400 (EDT) Message-Id: <5.1.0.14.2.20021008125827.030bd060@postoffice2.mail.cornell.edu> X-Sender: sc329@postoffice2.mail.cornell.edu (Unverified) X-Mailer: QUALCOMM Windows Eudora Version 5.1 Date: Tue, 08 Oct 2002 13:01:05 -0400 To: egs@CS.Cornell.EDU From: Sangeeth Chandrakumar Subject: 615 PAPER 30 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed Submitted by : Sangeeth Chandrakumar Intentional Naming System: INS is a resource discovery and service location system for dynamic and mobile networks of devices. INS applications make use of late bindings, where the binding between the intentional name and its location is made at message delivery time rather than at request time. Name resolving is done with the aid of Intentional name resolvers(INR), which are situated at appropriate locations maintaining the map between service descriptors and their network locations. The name-specifier is a heirarchical arrangement of av-pair and an intentional name is a combination of some of these descendant and orthogonal av-pairs. So by setting the av pairs like [location=room615], [load=low], applications could discover and use services without having to worry having a-priori knowledge of how to connect to that network. INS uses a decentralized network of resolvers to discover names and route packets. INS resolvers self-configure into an application-level overlay network, into which clients can attach to request services. The use of soft states to amp services helps in purging non-existent services after a period of time. INS allows applications to advertise arbitrary application-specific numeric metrics such as average load. Each INR listens to these periodic announcements on a well defined port to discover as weel as learn about services. INS also display good scaling and load balancing capabilities. In case of excessive lookup loads, an INR can spawn instances of other candidate INRs and kill them later when they are not needed. Also by partitioning the namespace into virtual spaces, a resolver need only route for a subset of all the active virtual spaces in the system. Caching of resolvers of some of these virtual spaces can be done to make the look up more effective, and would necessitate a request to DSR only if the entry is missing from the cache. One of the limitations of this scheme is the notion of attribute value pairs. An attribute should have a definite meaning since it is defined by an application. So a request like "print to the nearest printer", can not be implemented in this scheme as it doesn't support the notion of "nearest", as this would warrant you to know your current location. From linga@CS.Cornell.EDU Tue Oct 8 14:04:23 2002 Received: from snoball.cs.cornell.edu (snoball.cs.cornell.edu [128.84.96.54]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g98I4Nh02920 for ; Tue, 8 Oct 2002 14:04:23 -0400 (EDT) Received: from localhost (linga@localhost) by snoball.cs.cornell.edu (8.11.3/8.11.3/C-3.2) with ESMTP id g98I4M617292 for ; Tue, 8 Oct 2002 14:04:23 -0400 (EDT) Date: Tue, 8 Oct 2002 14:04:22 -0400 (EDT) From: Prakash Linga To: Emin Gun Sirer Subject: 615 PAPER 30 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII The design and implementation of an intentional naming system ------------------------------------------------------------- An intentional (wherein applications describe what they are looking for rather than where to find it) naming system which does the job of resource discovery and service location in a dynamic and mobile network has been proposed in this paper. Design goals include: Expressiveness, adaptability (to end-node or service mobility), robustness and easy configuration. A simple query language based on pairs has been used to express queries. INS resolution architecture is independent of the query language used and hence the design is modular. Adaptability is achieved by integrating message routing and name resolution. This enables late binding wherein the binding between intentional name and network location(s) happens at message delivery time rather than at name resolution time. Intentional name thus serves the dual purpose of helping in location of services and routing of messages. Two kinds of message delivery services possible: anycast- send to "optimal" (application dictates the metric) node that satisfies a given intentional name; multicast - send to all nodes that satisfy a given intentional name. INS resolvers form a self-configurable overlay network. Clients can attach to any of these resolvers to advertise their services and resolve their requests. If early-binding flag is set, resolvers return a list of IP addresses associated with the name to the client initiating the request. Otherwise late binding (anycast or multicast) is used. Name specifiers are used to implement intentional names. Names specifier is a hierarchical arrangement of attribute-value pairs wherein an av-pair dependent on another av-pair is a descendant of the latter. A name tree is a data strcture storing correspondence between name-specifiers and name-records (which contain the list of IP addresses of potential destinations) and is used to resolve name-specifiers. Three interesting applications (Floorplan, Camera, Printer) have been implemented on top of INS. Pros: Proposed and implemented an intentional naming scheme. This scheme has nice features - routing clubbed with resolving names, INS architecture is independent of the query language used, late binding to make the protocol responsive etc. Three interesting applications have been implemented on top of INS. Cons: Not applicable to wide-area internet. Query language not very expressive. Expressiveness and Robustness which are design goals are not strictly achieved. Comments: Here it is easy to express queries like nearest printer or printer closest to my friend Alice. Nearest printer: [service=printer]. Set delivery flag to any and use closest distance as the performance metric. The system should yield satisfactory results in a not so dynamic environment. Caching could improve performance but at the same time could lead to inconsistencies and inaccurate results. From ks238@cornell.edu Tue Oct 8 14:28:17 2002 Received: from travelers.mail.cornell.edu (travelers.mail.cornell.edu [132.236.56.13]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g98ISHh08496 for ; Tue, 8 Oct 2002 14:28:17 -0400 (EDT) Received: by travelers.mail.cornell.edu (8.9.3/8.9.3) id OAA00710; Tue, 8 Oct 2002 14:28:15 -0400 (EDT) Date: Tue, 8 Oct 2002 14:28:15 -0400 (EDT) From: ks238@cornell.edu Message-Id: <200210081828.OAA00710@travelers.mail.cornell.edu> To: egs@CS.Cornell.EDU Errors-To: ks238@cornell.edu Reply-To: ks238@cornell.edu MIME-Version: 1.0 Content-Type: text/plain Content-Transfer-Encoding: 7bit X-Mailer: IMP/PHP3 Imap webMail Program 2.0.9 Sender: ks238@cornell.edu X-Originating-IP: 128.84.99.8 Subject: 615 Paper #30 The Intentional Naming System is a naming convention applied to ad hoc networks which facilitates resource and service discovery. Due to the fact that this naming convention is implemented in ad hoc networks, INS focuses on being expressive, responsive, robust, and easily configurable. The primary contribution of INS is its use of a naming scheme that relies on attributes and values which devices tend to “describe” based on the service they are looking for or the service they may provide. The naming of devices is under application control making resource discovery robust and easily configurable. Resolution in INS is handled by Intentional Name Resolvers (INR) which use early binding, intentional anycast or intentional multicast to route packets to nodes that can satisfy their specific request. Name discovery is conducted through a series of periodic updtaes in the network when devices indicate the services that they provide. Name lookup and extraction is facilitated through the use of name trees in which a hierarchy is created in the network and attributes and value nodes alternate at each level. Each INR will receive a service request from name- specifiers and by conducting name lookup it will provide name-records containing the IP addresses for the devices with the appropriate names. In addition, partitioning of virtual spaces improves the networks ability to scale and reduces the overall network load. In addition, caching of popular virtual spaces can also help reduce overall network load by limiting the number of times that a particular resource is rediscovered. The biggest issue that I see with this naming convention goes back to the same problems we saw with our first few routing protocols study. It seems that the memory and bandwidth use is quite high. INS supports frequent service updates in order to keep the attributes and values stored for different devices up to date and hence the system robust. Obviously scalability becomes an issue here. This however is addressed in the later half of the paper when discussing scalability and the solution of virtual partitioning. I also think that by mentioning record caching the authors touch on a critical facet that could help reduce overall network congestion, however, this is not drawn upon extensively. Now, should a service request be made by Alice for a printer, then the request will be transferred to an INR. Hopefully, this INR either has a suitable printer already stored in its cache, through which Alice can print, or the closest printer with the least amount of load should have updated the INR with the appropriate information. The INR will then conduct a name search through the name tree and will search for the printer with the appropriate attributes as the original request. The problem with finding the “closest printer” however is that the attribute must specify that it is actually the closest printer. INS does not rely on finding the resource with a given location rather it relies on finding the resource with a given attribute or value. So, this wouldn’t be the most effective naming convention to use when finding proximity to the requester. From vivi@CS.Cornell.EDU Tue Oct 8 14:54:33 2002 Received: from exchange.cs.cornell.edu (exchange.cs.cornell.edu [128.84.97.8]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g98IsXh15181 for ; Tue, 8 Oct 2002 14:54:33 -0400 (EDT) content-class: urn:content-classes:message MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Subject: 615paper30 X-MimeOLE: Produced By Microsoft Exchange V6.0.5762.3 Date: Tue, 8 Oct 2002 14:54:33 -0400 Message-ID: <47BCBC2A65D1D5478176F5615EA7976D11AF89@opus.cs.cornell.edu> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: 615paper30 Thread-Index: AcJu/BachyDa6snrSuWcdGkaoOGxog== From: "Vivek Vishnumurthy" To: "Gun Sirer" Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from quoted-printable to 8bit by sundial.cs.cornell.edu id g98IsXh15181 The Intentional Naming System(INS) is a resource discovery and service location system for mobile networks.In INS, every service is categorized by the kind of service it provides (the Intentional Name), and clients that wish to access any services issue requests that have the intentional names corresponding to these services. INS has Intentional Name Resolvers (INRs) that handle client requests: INRs either return a list of addresses that correspond to the referenced intentional name in the client's request, or directly routes the request to one or all of the appropriate services. INRs configure themselves to form an overlaying spanning tree. INS seems to be very effective in handling mobile users' queries. The users need not be aware of the location of the services, and hence the view presented to the user remains constant wherever the user moves. Thus a user who wishes to get a file printed can issue a request setting the name-specifier to "printer", and he/she will get a complete list of printers from the INR network. But whether the user can then choose the one closest to him/her is not very clear. The paper says that when "intentional anycast" option is chosen, the INRs directly route the request to the "most optimal" service. By having this metric equal to the distance, we could build an INS system where anytime a request is sent with the "intentional anycast" option, the request is sent to the appropriate service closest to the user. But it would definitely be more preferable (and flexible) if the metric too could be specified as part of the query. The user then has the option of say opting for the closest printer or the least loaded printer. INRs could return inaccurate results when information stores in the INRs is stale, and the request arrives before the corresponding updates occur. INRs use caching in responding to user queries. (The information stored at an INR is, in a sense, a local cache). This caching is effective when there are not many changes to the cache(ie., the services are not temporally or geographically highly mobile), or when a small number of services are frequently accessed.