From: Mike Earnhart [mearnhart@gmail.com] Sent: Thursday, March 30, 2006 7:29 AM To: Indranil Gupta Subject: CS598 - late review submission Professor Gutpa, I will be unable to complete the reviews for metarouting etc ... this morning @ 9am I was wondering if I could request a 12 hour extension to complete them? pax, Michael Earnhart From: Vu Hai Long [longvuhai@yahoo.com] Sent: Thursday, March 30, 2006 7:00 AM To: Indranil Gupta Cc: Long Hai Vu Subject: cs598IG review 03/30/06 Dear Professor Gupta, I could not connect to CITES server to send the review by my UIUC mail; thus, I have to use this email address. I am sorry for any inconvenience, Thanks, -Long Name: Long Vu Class: CS598IG-Spring 2006 Date: 03/30/06 REVIEW PAPERS A Randomized ID Selection Algorithm for Peer-to-Peer Networks In this paper, author presents a low-cost, decentralized algorithm which is independent of the overlay routing topology, to select hostIDs in peer-to-peer systems, particularly in distributed hash tables. In this approach, they concentrate on both arrival and departure peers, at most one existing hostID is re-assigned, expected cost is Theta(R+logn) in which n is current number of peers and R is cost spent to round one message in the DHT. The proposed algorithm is design under high demand objectives such as simple, decentralized, low-cost, and minimal in term of partition size and re-assignment of existing hosts in response to arrival. To select a ID for itself upon arrival, new host is assumed to know at least one existing host in current DHT. A small partition balance ratios is also preserved so that xichma is equal or less than 4. The most important contribution of this paper is low-cost scheme with Theta(R + logn) which is cheaper than cost of current scheme (i.e. Theta(Rlogn)). Metarouting In this paper, authors present the idea of using high level and declarative language to define routing protocol, routers need only implement an interpreter or compiler for a routing meta-language in order to run any routing protocol. They also enforce the separation of protocol mechanism and routing policy. They propose a promising Routing Algebra Meta-Language (RAML) allowing user to define family of routing algebras. That means, the theoretical framework of metarouting is to be found in the long traditional of path algebras. RAML preserves monotonicity properties of any expressions and each algebraic operator is associated with specific rules. In essence, metarouting is proposed as a language which allows user to define routing protocol according to the syntax supported by this language. I can not see any special and specific relationships between this metarouting approach and distributed systems. This metarouting could be applied for many circumstances in different network conditions. ________________________________ Talk is cheap. Use Yahoo! Messenger to make PC-to-Phone calls. Great rates starting at 1¢/min. From: Ravi Sathyam [sathyam@uiuc.edu] Sent: Thursday, March 30, 2006 4:55 AM To: Indranil Gupta Subject: cs598ig review 3/30 Ravi Sathyam CS 598ig Randomized ID Selection for Peer-to-Peer Networks Summary: The paper presents a low-cost ID selection algorithm for DHTs. The algorithm presented is guaranteed to have handling of both node arrival and departures, low expected cost, a limit on the partition balance ratio and a limit on ID reassigning. In the first algorithm, the author treats the overlay as a black box with each host having an ID from [0,1) and having a manager. New nodes are assigned ID’s by performing a random walk from the root to reach a leaf node, and then inserting in the sub-tree that’s rooted at the active ancestor of r. After insertion, one then checks to see if the ancestor should continue to remain active or not based on a function Phi. In the following analysis, one sees the cost of sending messages and the partition balance ratio limit to be as highlighted before. The algorithm for Id reassigning under deletion of nodes is also shown, but however I was not able to grasp it properly. Comments: While this was a tedious paper to read, I was wondering about literature that has simpler schemes of ID assignments so that I could begin from there. Metarouting Summary: This paper presents an approach known as Metarouting that defines routing protocols using a high-level and declarative language. Basically, routers need to only implement an interpreter for a routing metalanguage. The paper describes routing algebra as a tuple of quantities – a set of signatures for describing paths, a preference relation over signatures, a set of labels, a label application function, and an origination set describing the signatures that can be associated with originated routes. Hence, a metarouting language should be able to define a routing protocol as another tuple consisting of a predefined routing algebra, a set of mechanisms that can be associated with a routing adjacency, and a set of label modalities. Specification of new routing algebras are done using the Routing Algebra Meta-Language (RAML). The paper then goes on to describe various methods to apply labels, and also extending labels to programmatic labels. The paper then uses RAML to define more suitable routing protocols for IGP as an alternative to BGP. From: Praveen Jayachandran [pjayach2@uiuc.edu] Sent: Thursday, March 30, 2006 12:09 AM To: Indranil Gupta Subject: cs598ig review 03/30 CS598IG Review 03/30 Praveen Jayachandran Metarouting ----------- The authors argue that the difficulty in developing, standardizing and deploying new routing protocols has led to the adoption of BGP as an intra-domain routing protocol. Although, BGP was developed as an inter-domain routing protocol, network operators use it for intra-domain routing, not because its ideal, but because it is available, supports several policy control mechanisms, it can be used to implement administrative boundaries, and it scales well. To ease the development of routing protocols, the authors develop Metarouting, which defines routing protocols using a high-level declarative language. Once an interpreter for a metarouting language is implemented on a router, the network operator can implement and use any routing mechanism definable in the language. A clean separation of protocol mechanisms, such as link-state, path-vector, and adjacency maintenance, is enforced. A Routing Algebra Meta-Language (RAML) based on the algebra framework of Sobrinho, which have the strict monotonicity property, is defined, with which large families of routing protocols can be constructed. Further, correctness conditions can be automatically derived for each expression defining a new algebra. Several open problems are described. Comments: 1. The learning curve is quite steep to learn the algebra and then the RAML, before a routing mechanism can be coded. Looking at the algebra, it looks quite complex, and a thorough understanding of the algebra would be required to implement a routing policy. 2. Metarouting shifts the coding of the routing mechanism to the network operator side. However, the network operator may be quite unwilling to implement a routing policy on the router, and would rather prefer a router that has the routing mechanism in-built. 3. Metarouting is yet to be implemented. It is unclear what the performance of a router based on metarouting would be, compared to a traditional router. The performance of metarouting in terms of execution speed should be comparable to traditional routers for feasibility. 4. Metarouting, if at all, only makes development of routing protocols easier. The problem of standardization and deployment still remain, which would hamper the widespread use of metarouting. A Randomized ID Selection Algorithm for Peer-to-Peer Networks ------------------------------------------------------------- An important problem in P2P systems is that of ID selection when nodes join the network. This paper presents a low-cost, distributed algorithm for ID selection in P2P systems. The algorithm has several desirable properties. It is independent of the nature of overlay used, as long as the cost of finding the manager of a randomly-chosen point is known to be R. The algorithm has low message cost, can handle host departures, has low number of reassignments of existing nodes, and permits a simple scheme to estimate the number of nodes currently in the system. The algorithm ensures a small partition balance ratio, which is the ratio of the largest and smallest partition sizes. Mathematical analysis is provided to show that the algorithm guarantees the above mentioned properties. The paper describes two ID selection algorithms using binary trees. Then the two-child requirement is relaxed in order to reduce the partition balance ratio. Comments: 1. The authors claim that the algorithms proposed are simpler than existing algorithms, but this claim is not backed by concrete studies. 2. Although analytical studies are provided to show the superior properties of the proposed algorithms, the proposed algorithms have not been compared with existing algorithms either in reality or in simulations. It is unclear what the performance and cost improvement due to the algorithm will be. 3. The paper does not clearly motivate the need for hosts to have absolutely unique IDs. In large P2P systems, if hosts rarely have the same ID but never come in contact with each other, then it might be unnecessary to expend valuable network resources in trying to ensure unique IDs. Can weaker semantics for node ID selection be defined, which with high probability ensures unique host IDs, at a significantly reduced cost? From: Raghu Kiran Ganti [rganti2@cs.uiuc.edu] Sent: Wednesday, March 29, 2006 11:10 PM To: Indranil Gupta Subject: 598ig review 03/30 Reviews for Design Methodologies, March 30, 2006 ------------------------------------------------ Paper title: Metarouting Summary/Main ideas: ------------------ This paper presents an approach that defines routing protocols using high-level and declarative languages. The development of such a language enables the network provider to implement any routing protocol, once an interpreter is developed. One of the observation in this paper is that BGP is being used as IGP (by hacking), when it is infact not ideal to use BGP. The reasons being that BGP has expressive policy control mechanisms, can be used to implement administrative boundaries, and it scales well. But, BGP does not have convergence guarantees, and routing policies have fewer constraints than inter-domain routing. To develop efficient methods to design network protocols, the authors take the following approach: separate mechanism from policy, present a routing algebra framework, develop a routing algebra meta-language (RAML) for defining protocols, and provide an automated method to check the correctness of the algebraic expression derived from RAML. A routing algebra is a 5-tuple, which is characterized by a set of signatures for describing paths, a preference relation over signatures, a set of labels, a label application function, and an origination set describing the signatures that can be associated with originated routes. The authors identify certain properties for routing algebras and then develop generic algorithms for any algebra. The properties identified are strict monotonicity (SM), monotonicity (M) and isotonicity (I). The correctness for various algebra and algorithm combinations is presented. A basic set of routing algebras are identified, examples include ADD, MULT, MAX, and MIN. But developing a new routing algebra by hand is tedious. To address this problem, a routing algebra meta language (RAML) is presented. All RAML expressions are routing algebras, but not vice versa. But, monotonicity conditions can be automatically derived for these specifications. Various operations on the routing algebras are specified in the paper, these include the lexical product, scoped product, disjunction, programmatic labels and monotonicity preservation. The authors use RAML to specify simple protocols. Comments: --------- 1. My first question would be- is this really going to be useful? The algebraic representations of routing protocols is complex and I would imagine that a network operator would not be interested in doing any Metarouting! It is a very good solution from a theoreticians viewpoint. 2. Also, what advantages does implementing new protocols on a BGP/IGP serve? Is the network operator going to change the protocol every now and then? I do not think that this is the case. 3. It is not clear why the requirements for the algebra's correctness are enough. 4. It would be more convincing if the authors had implemented an interpreter and shown in reality that this routing language has some advantages in reality! ************************************************************ Paper title: A Randomized ID Selection Algorithm for Peer-to-Peer Networks Summary/Main ideas: ------------------- This paper addresses the issue of selecting host IDs in peer-to-peer systems. The algorithm proposed in this paper has the following properties: 1. Arrival and departure of hosts are handled 2. Partition balance ratio is guaranteed to be at most 4 3. At most one existing ID is re-assigned in response to departures 4. The expected cost is theta(R+logn) messages, where n is the number of current participants and R is the cost of routing one message in the DHT Two ID selection algorithms are presented, where the first one handles host arrivals only, and the second one handles departures too. In the arrival only algorithm, a binary tree is considered, and node ID is added by adding a leaf to this binary tree. The ID of the new host is selected as follows: random walk down the tree to reach leaf node (r) and insert in a sub-tree rooted at node a, the active ancestor of r. Active nodes are identified by the algorithm through a marking process, such that for every leaf node (at all times), exactly one internal node along the path from that leaf node to the root is active. This algorithm is analyzed and several properties are derived. To handle host departures, the algorithm introduces a infinite length random bit string, which each host possesses when it joins and which it keeps swapping in the course of its life. A deletion algorithm similar to the B-tree deletion algorithm is presented in the paper to handle host departures. The features of the above algorithms are: 1. Generality - independence of algorithm from overlay routing 2. Number of messages sent are low 3. Host departures are handled 4. Small partition balance ratios 5. Scheme can be easily generalized 6. Enables overlay construction 7. Provides a way to estimate the number of hosts in the peer to peer system Comments: --------- 1. The algorithm presented is quite interesting, as it follows a simple textbook scheme 2. It would have been really impressive if simulation results were presented to backup the theoretical analysis, and if possible a real implementation. From: Hussam Abu-Libdeh [habulib2@uiuc.edu] Sent: Wednesday, March 29, 2006 9:01 PM To: Indranil Gupta Subject: 598ig review 03/30 Composition and Behaviors of Probabilistic I/O Automata: ------------------------------------------------------------- Summary: ----------- This paper presented a framework in which probability can be added to I/O automata. To capture the asymmetric treatment of input and output indigenous to I/O automata, a separate distribution is associated with each input action, in the reactive style, and a single distribution is associated with all locally controlled actions, in the generative style. No relative probabilities are de?ned among di?erent input actions nor between input and locally controlled actions. Moreover, the notion of I/O automaton asynchronous composition is retained, in part, through the introduction of state delay parameters. It also introduced a more abstract representation, probabilistic behavior maps , for the external behaviors of certain classes of probabilistic I/O automata. This representation maps ?nite action sequences to a set of expectation functionals which give information not only about the probabilities of action sequences but also delay sequences. This latter information is essential for achieving compositionally. That showed that probabilistic behavior maps are fully abstract with respect to a natural notion of probabilistic testing. Comments: ------------ Personally, i thought this paper was a bit too cumbersome to understand, although the underlying principles might have been clear and expressed in simpler terms. As far as open-ended questions, i actually agree with the questions that the authors proposed at the end of this paper about how realistic is this paper ? and how realistic is this idea of independence in delays ? ----------------------------------------------------- A Randomized ID Selection Algorithm for Peer-to-Peer Networks: --------------------------------------------------------------------- Summary: ----------- This paper presents a low-cost, decentralized algorithm to select host IDs in peer-to-peer systems. The problem arises in the context of distributed hash tables (DHTs). The author of the algorithm claims to be the ?rst one with the properties that: both arrivals and departures of hosts are handled, partition balance ratio is guaranteed to be at most 4, at most one existing ID is reassigned in response to departures, and the expected cost is ?(R + log n) messages, where n denotes the current number of participants, and R denotes the cost of routing one message in the DHT. This algorithm is independent of the overlay routing topology, making it applicable to all DHTs. The proposed algorithm improves upon existing algorithms which have one or more of the following drawbacks: they require ?(R log n) messages, do not handle host departures, or reassign the IDs of O(log n) existing hosts in response to a departure.This ID selection algorithm enables emulation of a variety of deterministic and randomized families of interconnection topologies, in a straightforward fashion. Comments: ------------ I have to say, i feel it is a very bold statement by the author to claim that his algorithm is the only algorithm to address all the issues that were mentioned above. In any case, the only comment that i would like to make here is the following: Is the law of diminishing returns apply here ? I guess an 8 byte node id can accommodate the largest p2p network known yet. So do we really need to dive into the complexity of this paper and the algorithm defined in it just to enhance the process of selecting peer ids ? I guess the answer depends on the application.