From eyh5@cornell.edu Wed Sep 12 18:07:42 2001 Return-Path: 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.7) with ESMTP id f8CM7gq09965 for ; Wed, 12 Sep 2001 18:07:42 -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 SAA09756 for ; Wed, 12 Sep 2001 18:07:39 -0400 (EDT) From: eyh5@cornell.edu Date: Wed, 12 Sep 2001 18:07:39 -0400 (EDT) X-Sender: eyh5@travelers.mail.cornell.edu To: egs@CS.Cornell.EDU Subject: 615 Paper # 7 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII This paper is intended to address the formation of routing loops often found in ad hoc networks when routes are created to deliver packets. In order to meet the loop-freedom requirement, the author provides and proves three conditions, namely, the distance increase condition, current successor condition, and the source node condition. Each of the three is sufficient to ensure loop freedom at any instant in a network of arbitrary topology. However, these conditions do not necessarily provide the shortest paths, in terms of minimal link-state costs, to reach the destination. In computing multiple diffusing computations, the author takes an approach different from the other proposals in that the proposed DUAL operation will allow a mobile node to conduct at most one diffusing computation per destination at any given time. A state diagram is used in illustrating how DUAL carries out multiple diffusing computations. The improvement provided by DUAL over the Jaffe-Moss algorithm and the Merlin-Segall algorithm is reflected in the reduced number of operation counts for DUAL to take to converge to a steady state. The author provides ample proof to demonstrate the validity of the three loop-freedom conditions and the correctness of DUAL. The results are comparable are better than those from the DBF and ILS. Be impressive as it may, the true effectiveness of the proposed scheme is not demonstrated in the performance evaluation. The tabulated results make a comparison between DUAL and the other two algorithms, DBF and ILS, on a number of metrics, node failure, node recovery, link failure, and link recovery. However, it does not say how well the packets are being handled with the improvement made in this paper. Additional metrics may be used to evaluate the successful delivery rate of packets and propagation delay time. From wbell@CS.Cornell.EDU Wed Sep 12 23:02:15 2001 Return-Path: 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.7) with ESMTP id f8D32Fq08080 for ; Wed, 12 Sep 2001 23:02:15 -0400 (EDT) Received: from [192.168.1.100] (syr-66-24-16-64.twcny.rr.com [66.24.16.64]) by postoffice.mail.cornell.edu (8.9.3/8.9.3) with ESMTP id XAA03057 for ; Wed, 12 Sep 2001 23:02:13 -0400 (EDT) Subject: 615 PAPER #7 From: Walter Bell To: egs@CS.Cornell.EDU Content-Type: text/plain Content-Transfer-Encoding: 7bit Message-Id: <1000350135.13766.17.camel@brute> Mime-Version: 1.0 X-Mailer: Evolution/0.13.99+cvs.2001.09.08.07.08 (Preview Release) Date: 12 Sep 2001 23:01:56 -0400 7) Loop-Free Routing Using Diffusing Computations This paper tackles the problem of creating loop free routing tables for distance vector routing approaches, which increases the efficiency of both discovery and route maintenance, as well as making data transfer more optimal. The key insight here is the use of diffusing computations for route updating, which is a computation that is started by a node via queries and completed by a matching number of replies. They propose a new family of routing algorithms called diffusing update algorithms [or DUALs], which propagate routing updates via diffusing computations. They present a proof of correctness, that the algorithm will not produce routing loops, and present simulation results as well as critiques on their algorithm as opposed to other link state algorithms. This paper is very different than the others we have seen thus far, being far more graph-theoretic than applied systems-centric. This made the paper incredibly difficult to read because of the dense notation at each step that actually corresponded to more understandable English statements. The entire statement of DIC [Distance increase condition] could have been described while completely omitting the notation. Although their algorithm does prevent routing loops, it seems to fail in the most common case, which is node disappearance or failure, where every node in the network becomes involved in a diffusing computation. They present an incredibly hand waving solution in the last section, but this not nearly given as rigorous a treatment of previous statements. We start to see here the first sign of heavy theoretical treatment to the problem of routing, which definitely can provide more solid statements about the network than some of the former simulation based assessments. From avneesh@csl.cornell.edu Wed Sep 12 23:28:24 2001 Return-Path: Received: from capricorn.ds.csl.cornell.edu (capricorn.csl.cornell.edu [132.236.71.92]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f8D3SOq10299 for ; Wed, 12 Sep 2001 23:28:24 -0400 (EDT) Content-Class: urn:content-classes:message Subject: 615 Paper #7 MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Date: Wed, 12 Sep 2001 23:32:47 -0400 X-MimeOLE: Produced By Microsoft Exchange V6.0.4712.0 Message-ID: <97C142C1212ED545B0023A177F5349C4053A73@capricorn.ds.csl.cornell.edu> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: 615 Paper #7 Thread-Index: AcE8BMHDy+D2OJoSTdeqaDlCYdYgIw== From: "Avneesh Bhatnagar" To: Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from quoted-printable to 8bit by sundial.cs.cornell.edu id f8D3SOq10299 Loop Free Routing Using Diffusing Computations Summary: This paper discusses the short comings of the distance vector and link state routing families of protocols and provides and focuses on the problem of relieving these from routing loops. A thorough analysis is done based upon three basic conditions: Distance Increase Condition: If the node detects a link cost decrease reported by a neighbor, then it can choose a new successor such that the change is no worse than before (Min (d(i,jx) (t) +l (i,x)(t)). There is no action doen on an increase, though a less restrictive version exists, which allows changing of successor in the case of an increase. Current Successor Condition: where alongwith the above conditions, the feasible distance from i to j is equal to the smallest value of successor (of i) to j as known by i at a particular instance of time t. Source node condition: where alongwith the first condition, the feasible distance from node i to j is equal to the smallest value of the current distance known by i to j at that time. Either of these conditions guarantee loop freedom, validity for SNC is proved by the author. However the author acknowledges that neither of these can guarantee the shortest path in the resulting graph. The author then defines diffusing computations, where a node that orginates a computation for either of the above conditions, coordinates with its successor nodes before making changes to its ASG. However the optmization as proposed is to provide a single computation for a given destination. This is contrary to that used in the Jaffe-Moss algorithm. Using the state machine as shown and following semantics for when a node is active and would participate in computations, the overall number of computations are compared to the Jaffe Moss algorithm and the Merlin-Segall algorithm are reduced, thus resulting in faster convergence. However, results highlight that after nodal failures, the number of messages and hence the CC value for DUAL increases. DBF suffers from the original count to infinity problem while ILS has higher CPU utilization in all cases. I think that paper provides a rigorous analysis of the sufficient conditions for loop free routing, but it was extremely hard to follow. Especially the notations that were used. Furthermore, the ananlysis could have been supported by a stronger simulation study, since there seem to be a number of factors and cases, including network density, rate of topology change etc, which have not been clearly specified. From daehyun@csl.cornell.edu Thu Sep 13 00:30:14 2001 Return-Path: Received: from wilkes.csl.cornell.edu (wilkes.csl.cornell.edu [132.236.71.69]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f8D4UDq16636 for ; Thu, 13 Sep 2001 00:30:13 -0400 (EDT) Received: (from daehyun@localhost) by wilkes.csl.cornell.edu (8.9.3/8.9.2) id AAA17242 for egs@cs.cornell.edu; Thu, 13 Sep 2001 00:30:07 -0400 (EDT) (envelope-from daehyun) From: Daehyun Kim Message-Id: <200109130430.AAA17242@wilkes.csl.cornell.edu> Subject: 615 PAPER 7 To: egs@CS.Cornell.EDU Date: Thu, 13 Sep 2001 00:30:07 -0400 (EDT) X-Mailer: ELM [version 2.4ME+ PL54 (25)] MIME-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit This paper proposes a new routing algorithm called diffusing Update Algorithm (DUAL), which is loop-free and converges in finite time. This paper shows three condition called Feasibility Conditions (FC) for loop freedom - Distance Increase Condition, Current Successor Condition and Source Node Condition. Any of the three conditions is sufficient to ensure loop freedom. But, the conditions do not guarantee the shortest paths. So this paper proposes a new algorithm. DUAL is based on FC for the loop freedom and adapts Diffusing Computations (DC) to Distance Vector Routing for the shortest paths. Section 3, 4, 5 and 6 explain the algorithm and proves the correctness in detail. But, actually, I couldn't understand those thoroughly. This paper shows the performance comparison between DUAL and other routing algorithms. Time Complexity and Communication Complexity are given and simulation results are also presented. This paper argues that DUAL is better than, or at least equal to, the others. In my opinion, main contribution of this paper is the adaptation of DC to solve shortest path routing problem. Using FC and DC, the proposed algorithm provides the loop free shortest path routing. In addition, this paper presents the proof of loop freedom of the algorithm. I think, there is not so much to criticize about this paper itself. But because we are discussing on Ad Hoc networks, I'd like to point out the followings; 1. Basically, this paper is published in 1993 and does not intend for ad hoc network. So, some of its assumptions such as reliable communication links are not relevant. And, as mentioned in the conclusion, DUAL requires that all network nodes have to be involved in diffusing computation. Therefore, I doubt that DUAL can be applied to Ad Hoc networks. 2. In the simulation results, ILS shows better performance than DUAL except for operation counts. This paper argues that low CPU utilization of DUAL is more suitable for large networks such as Internet. Though it might have been a valid argument in 90's, it does not seem to be valid any more, if considering the high performance of current CPUs and relative slow networks. From kewang@CS.Cornell.EDU Thu Sep 13 10:43:36 2001 Return-Path: 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.7) with ESMTP id f8DEhaq17801 for ; Thu, 13 Sep 2001 10:43:36 -0400 (EDT) X-MimeOLE: Produced By Microsoft Exchange V6.0.4712.0 content-class: urn:content-classes:message MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Subject: 615 PAPER 7 Date: Thu, 13 Sep 2001 10:43:36 -0400 Message-ID: <24C06C2959910949931A2337CB264DCB04BA92@opus.cs.cornell.edu> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: 615 PAPER 7 Thread-Index: AcE8YnctFlyRpcfrSIy8uOzoBvIbcA== From: "Ke Wang" To: "Emin Gun Sirer" Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from quoted-printable to 8bit by sundial.cs.cornell.edu id f8DEhaq17801 This is a quite theoretic paper. It focuses on designing algorithm to prevent loop in routing, which is a serious problem in routing protocols. The author first specifies three conditions for loop-free, any one of which can lead to loop-free. At the same time, the routing protocol needs to find the shortest paths. So the author introduces the DUAL algorithm. The key idea in this DUAL algorithm is using diffusing computations. The author uses state machine and semantics to do proof, which make this loop-free algorithm theoretically strong. This is quite different from previous papers we had read, all of which only describe the protocol and give simulation. Also this paper gives a complexity analysis of their algorithm. The weak part of this paper is its simulation. They did give the results, but I could not find the specified assumption for the simulation. Are their assumptions realistic? Also the simulation is not targeted for ah-hoc network for there is no nodes movement, no power range. From theoretic view, this is a good paper. But I doubt how well it will perform in real ad-hoc network, or even traditional network. From samar@ece.cornell.edu Thu Sep 13 11:59:34 2001 Return-Path: Received: from memphis.ece.cornell.edu (memphis.ece.cornell.edu [128.84.239.87]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f8DFxYq28054 for ; Thu, 13 Sep 2001 11:59:34 -0400 (EDT) Received: from ockham.ee.cornell.edu (ockham.ee.cornell.edu [128.84.236.58]) by memphis.ece.cornell.edu (8.11.6/8.11.2) with ESMTP id f8DFxXe09708 for ; Thu, 13 Sep 2001 11:59:34 -0400 Date: Thu, 13 Sep 2001 11:59:33 -0400 (EDT) From: Prince Samar X-Sender: samar@ockham.ee.cornell.edu To: egs@CS.Cornell.EDU Subject: 615 PAPER 7 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII 7) Loop-free Routing using Diffusing Computations This paper describes a family of proactive distributed algorithms for shortest path routing using distance vectors, called Diffusing Update Algorithms (DUAL). The paper claims to extend and improve upon the previous work in the area of distributed shortest path routing. They produce a proof for correct, loop-free operation of their algorithm and give some simulation results to demonstrate its performance. A node sends update messages to its neighbors which contain a distance vector specifying lengths of selected paths to network destinations along with flags to indicate the type of each such entry (update, query or reply). Three Feasibility Conditions are described, each of which is sufficient to ensure loop freedom at any time: - Distance Increase Condition (DIC) - Current Successor Condition (CSC) - Source Node Condition (SNC) The author present a complete proof of loop freedom for the family of algorithms that they describe, which is claimed to be free of other problems like count-to-infinity. One drawback of the paper is the convoluted notations that the author uses in his presentation. The algorithm has been designed for stable, not-so-dynamic systems like the internet. The algorithm also depend on some kind of synchronization in reception and processing of messages. Also the performance of the algorithms degrades considerably if node failures or network partitions occur. Only bidirectional links are assumed to be present in the network. These limitations make it difficult to imagine that the algorithm will perform equally well in dynamic systems like Ad hoc networks. The author provides a heuristic fix to the degradation in performance that may be caused due to node failures or network partitions. But no analysis or simulation results have been provided to support the claim. Also, the simulations could have been more extensive by running it for a few different representative parameter values. The author's claim that low CPU time needed for DUAL makes it suitable for large networks may not be very relevant today with tremendously increased computation speeds (as compared to early 90's). From c.tavoularis@utoronto.ca Thu Sep 13 12:01:38 2001 Return-Path: Received: from bureau6.utcc.utoronto.ca (bureau6.utcc.utoronto.ca [128.100.132.16]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f8DG1cq28176 for ; Thu, 13 Sep 2001 12:01:38 -0400 (EDT) Received: from webmail3.ns.utoronto.ca ([128.100.132.26] EHLO webmail3 ident: IDENT-NOT-QUERIED [port 44548]) by bureau6.utcc.utoronto.ca with ESMTP id <238763-27832>; Thu, 13 Sep 2001 12:00:29 -0400 Received: by webmail3.ns.utoronto.ca id <414676-5759>; Thu, 13 Sep 2001 11:56:13 -0400 To: COM S 615 Subject: 615 PAPER 7 Message-ID: <1000396562.3ba0d71216097@webmail.utoronto.ca> Date: Thu, 13 Sep 2001 11:56:02 -0400 (EDT) From: c.tavoularis@utoronto.ca MIME-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 8bit User-Agent: IMP/PHP IMAP webmail program 2.2.3 Garcia-Lunes-Aceves performs an in-depth analysis of the problem of loop formation that occurs in various network routing schemes. Two types of algorithms, distance-vector or link-state, ensure shortest path routing but do not eliminate the risk of loop formation, particularly in changing topologies. This paper proposes a new algorithm, diffusing update algorithm (DUAL), stemming from previous results on loop-free routing using distance vectors, and employing diffusing computations. This paper first examines three possible conditions for loop-free routing: DIC, CSC and SNC. The analysis and simulation employs DUAL with SNC, therefore there is a detailed proof of the validity of SNC. The general strategy of the proof is to assume that a loop has formed in the graph Sj(G) and prove by contradiction. In DUAL, each node maintains a routing table with information regarding paths to other nodes in the form of an acyclic successor graph, including link cost information. The algorithm employing diffusing computation is as follows: if a node, x, in the path to j detects a change in a link, it initiates a series of computations by sending queries to upstream nodes to determine a new successor in the shortest path to j that satisfies the feasibility condition (FC). Upstream nodes may propagate these queries if they in turn do not have a successor that satisfies FC. x updates it’s ASG only when it has received all replies from neighboring nodes; this is a necessary condition for loop freedom. An update message is sent once a node has altered its ASG. This algorithm also handles network partitions, for if a destination is not found, all replies will be returned with infinite distance. Through simulation, it is found that DUAL outperforms other routing algorithms, without increasing complexity. DUAL perform poorly in the case of node failure since this disrupts the diffusing computation. A solution is proposed to use a hold time to allow a node to receive update information before updating it’s own routing table. This paper addresses an issue that is a heavy risk in adhoc network routing. The analysis performed in this paper applies to adhoc networks since it takes into consideration the effects of changing topologies including changes in link cost, distance, and shortest path. Also, it makes a realistic assumption that there are two way links between nodes, but each direction may have a different weight. From teifel@csl.cornell.edu Thu Sep 13 12:17:22 2001 Return-Path: Received: from disney.csl.cornell.edu (disney.csl.cornell.edu [132.236.71.87]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f8DGHLq00091 for ; Thu, 13 Sep 2001 12:17:22 -0400 (EDT) Received: from localhost (teifel@localhost) by disney.csl.cornell.edu (8.11.3/8.9.2) with ESMTP id f8DGHGw41731 for ; Thu, 13 Sep 2001 12:17:16 -0400 (EDT) (envelope-from teifel@disney.csl.cornell.edu) X-Authentication-Warning: disney.csl.cornell.edu: teifel owned process doing -bs Date: Thu, 13 Sep 2001 12:17:16 -0400 (EDT) From: "John R. Teifel" To: Subject: 615 PAPER 7 Message-ID: <20010913121648.V37347-100000@disney.csl.cornell.edu> MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Loop-Free Routing: This paper discusses algorithms for loop-free routing when dynamic computation of the shortest path is used. It presents sufficient conditions for loop-free routing for arbitrary algorithms and introduces a new family of routing algorithms which use diffusing computations. The three conditions for loop freedom are the dinstance increase condition, the current successor condition, and the source node condition. The diffusing computation computes by sending queries and receiving replies along an acyclic graph rooted at the node doing the computation. A DUAL routing algorithm was proposed and compared to existing alorithms. This paper was rather dense, but otherwise nicely organized. Difficult to tell how complete the simulations were, given the papers advanced age. From gupta@CS.Cornell.EDU Thu Sep 13 12:20:56 2001 Return-Path: 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.7) with ESMTP id f8DGKuq00627 for ; Thu, 13 Sep 2001 12:20:56 -0400 (EDT) X-MimeOLE: Produced By Microsoft Exchange V6.0.4712.0 content-class: urn:content-classes:message MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Subject: 615 PAPER 7 Date: Thu, 13 Sep 2001 12:20:55 -0400 Message-ID: <404A3A4758DDCC4C8A5C9A537384F9D61BB811@opus.cs.cornell.edu> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: 615 PAPER 7 Thread-Index: AcE8cAVL99uiwKbwEdW1ugCgydyP2Q== From: "Indranil Gupta" To: "Emin Gun Sirer" Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from quoted-printable to 8bit by sundial.cs.cornell.edu id f8DGKuq00627 ---START----- Loop-free routing using diffusing computations, J.J.G.-L.-Aceves. Reviewer: Indranil Gupta Summary: Source routing avoids the count to infinity problem and routing loops as the entire route is seen by several nodes - distance vector protocols do not have this property, and it is not easy to solve these problems within their framework. This paper presents the first loop-free distance vector based routing algorithm for dynamic networks. The algorithm presented is effectively a link state routing algorithm, but preserves loop-freedom even if the link state at different nodes is out of date (i.e., is conservatively safe). The author first presents three conditions (DIC, CSC, SNC) each of which is sufficient to ensure loop-freedom (but not shortest routes) in routes to a destination node. These conditions all rely on the common fact that a (intermediate) node updates the "next hop" to a given destination only if it finds a shorter path to the destination than the one it already has. The author then uses Dijkstra and Scholten's diffusing computations to find shortest loop free paths. The algorithm assumes that all messages along a link are delivered, and in FIFO order, and that every node sends out beacons to its neighbors which estimate the cost of the link. When a node detects a cost change on a "next hop" link, it updates its next hop only if this decreases the cost of the route compared to the previous existing cost. If not, the source becomes active, and a route query is flooded out - intermediate noes receiving the query also become active and follow the same decision making in updating their routes. When a node (intermediate or source) that is active receives a reply for the query from all its neighbors, it resets the shortest path so far using these received readings, and treats this as the shortest path to the destination - the node then becomes passive. The author proves the loop-freedom of this algorithm, and also extends it to the case of multiple such computations. Link breakages are handled by propagating a cost of infinity for that link to upstream nodes. The flood of diffusing computation messages due to a network partition is handled by having each node wait for a longer time to receive all messages from the neighbors before updating its routing tables. The message complexity of a diffusing computation per node affected by the routing table update is proportional to the node's degree. Comments: - Loops in the path, as considered in the paper, primarily arise because of downstream nodes on an already-existing path believe, on link changes, that upstream nodes have a shorter route to the destination. Other loops such as those in a newly constructed path are simply eliminated since every node has at most one next hop for each destination. The author could have made this distinction clearer in the earlier part of the paper, esp for readers new to the topic. - The two conditions discussed by the author - existence of shortest routes, and loop-freedom in routes, are instances of the liveness and safety properties respectively (liveness = something good eventually happens,safety = nothing bad ever happens). In an asynchronous system, where messages can be lost, and clocks are not synchronized, both liveness and safety cannot be guaranteed ([FLP] result). Even though the author's model is not an asynchronous system (messages are never lost), it appears that safety is always guaranteed, but there may be attacks on the protocol that can never guarantee liveness (eg., constant updating of link costs). This is surprising. - As a general question, relating to the above, given any distance vector routing algorithm, can one always formulate an attack on the algorithm (in terms of quickly changing link costs, or topologies, even without messages losses) that ensures that both liveness *and* safety are never guaranteed simultaneously i.e., either shortest paths are never found (liveness never guaranteed), or the routes have loops ? In other words, is this a fundamental limitation of distance vector routing algorithms ? source routing algorithms ? - The author assumes that all messages are eventually delivered (as broadcasts). Can the loss of messages in the wireless medium lead to violations of the liveness property, i.e., all nodes are blocked up, and shortest routes are never found ? In such cases, it might be worth guaranteeing liveness in some manner (existence of *some* path), possibly violating safety in some of the paths. - The data presented Table 1 (pg. 140) does not put the author's DUAL algorithm in good light. DUAL always seems to have more message count, event count and step count than the ILS algorithm, beating in only operation count (CPU load). DUAL sends about twice as many messages as ILS, but has a (much) lower load on the CPU in terms of computation. The authors claim that this makes DUAL scalable - in world where wireless bandwidth is scarcer than CPU power, is this a correct conclusion ? ----END---- From jcb35@cornell.edu Thu Sep 13 12:45:56 2001 Return-Path: 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.7) with ESMTP id f8DGjtq03560 for ; Thu, 13 Sep 2001 12:45:55 -0400 (EDT) Received: from localhost.localdomain (syr-66-66-30-147.twcny.rr.com [66.66.30.147]) by postoffice.mail.cornell.edu (8.9.3/8.9.3) with ESMTP id MAA22891 for ; Thu, 13 Sep 2001 12:45:20 -0400 (EDT) Received: from localhost (john@localhost) by localhost.localdomain (8.11.0/8.11.0) with ESMTP id f8DGknj23096 for ; Thu, 13 Sep 2001 12:46:49 -0400 Date: Thu, 13 Sep 2001 12:46:49 -0400 (EDT) From: "John C. Bicket" To: egs@CS.Cornell.EDU Subject: 615 paper 7 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII This paper addresses the counting to infinity and routing-table looping problem present in many distributed algorithms for dynamic computation of shortest paths in a computer network. The paper attempts to improves on algorithms previously introduced and while proving that DUAL, the algorithm that they introduce, converges to the correct paths while remaining loop-free and outperform the other algorithms. First, the paper defines the problem and looks at the loop-free that is inherent in distance-vector protocols (dvp's). They define the network model and a seemingly tedious notation (which makes this paper rather dense). They then define conditions for loop free conditions which rely on neighbors updating the next-hop on their routing tables when they have a shorter path to a node. These conditions guarantee the graph is loop free, but they do not necessarily dictate the shortest path. Next the paper introduces their algorithm, a diffusing update algorithm (or DUAL) and provide a formal description of it along with a proof of correctness. These diffusing computations grow by sending queries and shrink by receiving replies along a acyclic graph rooted at the source node. The algorithm works by sending out queries to its neighbors, which will in turn send out queries to ensure they have an correct successor before they return the result back to the source node. Link breaks are handled by sending the value of infinity back through the successors. After proving the correctness of a single diffusing computation for a new route, the author further proves its correctness for multiple computations.l Finally, the simulation provides a performance comparison to DBF, and an ideal link-state algorithm (ILS). They provide graphs showing that DUAL either outperforms the other algorithms in case of node failure, node recovery, link failure, and link recovery. Comments: They seemed to pick simulations that would pick on where the other algorithms would not fair so well, but they assumed that processor time was a valuable resource in these networks, which I am not convinced. And in many cases, the algorithm did not seem to outperform ILS. Also, this paper did not address much regarding mobility and I would have liked to see how this algorithm held up in networks where nodes moved around a lot, maybe they did in the simulation, but they didn't provide information about them. In general, I felt like they could have provided less detail on the proofs (it was quite dense) and more convincing simulation on various network topologies. From andre@CS.Cornell.EDU Thu Sep 13 13:02:30 2001 Return-Path: Received: from sundown.cs.cornell.edu (sundown.cs.cornell.edu [128.84.96.20]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f8DH2Tq05469; Thu, 13 Sep 2001 13:02:29 -0400 (EDT) Received: from khaffy (mail@cs-annex-1-09.cs.cornell.edu [128.84.96.39]) by sundown.cs.cornell.edu (8.11.3/8.11.3/R-3.5) with ESMTP id f8DH2RC27558; Thu, 13 Sep 2001 13:02:28 -0400 (EDT) Received: from andre by khaffy with local (Exim 3.22 #1 (Debian)) id 15hTJp-0001qK-00; Thu, 13 Sep 2001 12:02:01 +0200 Date: Thu, 13 Sep 2001 12:02:01 +0200 From: =?iso-8859-1?Q?Andr=E9?= Allavena To: egs@CS.Cornell.EDU Cc: andre@CS.Cornell.EDU Subject: 615 PAPER 7 Message-ID: <20010913120201.A7074@khaffy> Mime-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Disposition: inline Content-Transfer-Encoding: 8bit User-Agent: Mutt/1.3.18i Sender: =?iso-8859-1?Q?Andr=E9_Allavena?= Loop Free Routing using Diffusing COmputations. This paper was extremly abstrait, and didn't give much insight of why what it said works. I'll try to add the "hands" but I might be wrong. We are dealing with dynamic routing. The paper presents a sufficient condition for avoiding loops. Considering route to node j, if a node detects a decrease in the cost of the link it used toward j, it is free to update its routes accordingly. If it detects an increase , then it has to keep the successor it had in its route to j. Less restrictively is to chose any other neigbour so that the distance to j is as small as the best distance seen up to now. (There were 3 different metrics for best). Basically you update the route if you are sure you are doing better than or as well as before. This means you cannot loop: either you don't update, or if you update when a cost increases, the route cannot loop since you have choosen a route as least as good as what you had (it cannot come back through you since the cost from your predecessor to you is strictly positive). Note: this is still somehow conservative, but loop free. Then the paper presents a routing alogorithm using the previous technique and diffuse computation. A node only computes one update at a time, and postpones this others (which means a kind of consistency: a link has increased, I have ask for a new route, the same (or other link) changes, I do as if it hasn't changed until a got all the anwsers to my route request, and then handle it. This means everybody sees the same topology (even if incorrect) thus loop free. The algorithm is said to converge, but there is no mention of how long it is going to take. Further more, postponing and doing one computation at a time limits the size in memory, but might take a long while to converge. Last, the paper sais their DUAL is doing as well as or better than ILS, but I am not so sure that the results they show prooves it, further more when they say computation is less in DUAL, how do they compare? -- André Allavena (local) 148 B Valentine Place École Centrale Paris (France) Ithaca NY 14850 USA Cornell University (NY) (permanent) 879 Route de Beausoleil PhD in Computer Science 06320 La Turbie FRANCE From egs@CS.Cornell.EDU Thu Sep 13 13:06:01 2001 Return-Path: Received: from hoho.cs.cornell.edu (hoho.cs.cornell.edu [128.84.96.89]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f8DH60q05999 for ; Thu, 13 Sep 2001 13:06:01 -0400 (EDT) From: Emin Gun Sirer Received: (from egs@localhost) by hoho.cs.cornell.edu (8.11.3/8.11.3/C-3.2) id f8DH60m08670 for egs; Thu, 13 Sep 2001 13:06:00 -0400 (EDT) Date: Thu, 13 Sep 2001 13:06:00 -0400 (EDT) Message-Id: <200109131706.f8DH60m08670@hoho.cs.cornell.edu> To: egs@CS.Cornell.EDU Subject: 615 PAPER 7 >From ramasv@CS.Cornell.EDU Thu Sep 13 11:37:49 2001 >X-MimeOLE: Produced By Microsoft Exchange V6.0.4712.0 >content-class: urn:content-classes:message >Subject: 615 PAPER 7 >Date: Thu, 13 Sep 2001 11:37:48 -0400 >X-MS-Has-Attach: >X-MS-TNEF-Correlator: >Thread-Topic: 615 PAPER 7 >Thread-Index: AcE8abJIIWtjLpUTEdWTbQCQJ5m7oA== >From: "Venu Ramasubramanian" >To: "Emin Gun Sirer" >X-MIME-Autoconverted: from quoted-printable to 8bit by sundial.cs.cornell.edu id f8DFbnq25238 > > Loop-Free Routing Using Diffusing Computations > > This paper presents a theoritical approach to loop-freedom in >distance vector based routing algorithms. The author identifies 3 >sufficient conditions for ensuring loop-freedom in establishing next >hops at each node for different destinations. The paper also presents a >routing algorithm called diffusing update algorithm (DUAL) based on a >new approach involving diffusing computations. The final sections of >the paper claim the superiority of this approach over standard link >state and distance vector algorithms by providing simulation results. > > For most parts, the paper is highly theoretical. Heavy use of >notations throughout the paper deters a clear comprehension of the >details at a first reading. Yet, the mathematics involved appears to be >sufficiently sound. Three sufficient conditions namely DIC (distance >increase condition), CSC (current successor condition), SNC (source node >condition) are introduced, of which the SNC is proved for the first >time. Such theoretical appraoches to routing make important >contributions. > > DUAL is a routing protocol based on diffusing computations that >ensures that atleast one of the sufficient conditions are always >satisfied. Certain optimizations are done in order to prevent >computational loops and enforce convergence. However, it also makes >several assumptions such as synchronous computations and reliable >channels that may not be true in real networks. Asynchronity is a >fundamental property of networks of nodes (especially ad hoc network) >and a routing protocol that assumes synchronous computations is not >practically deployable. Also congestion effects often prevent real life >channels from behaving reliably and hence may invoke several false link >break detections. The algorithm also assumes that the present >neighborhood is always known correctly to each node. This is not always >enforcable. > > Although this paper provides a comprehensive theoretical >analysis of DUAL, the simulations perfromed are insufficient to back all >the claims made in the paper. Further, this is a proactive approach to >routing attempting to calculate at each node the distances to all the >nodes in the network. As such this protocol is not very scalable >especially so in ad hoc networks. Nevertheless, it makes an important >contributions by identifying several sufficient conditions to enforce >loop freedom in routing algorithms. > From egs@CS.Cornell.EDU Thu Sep 13 13:06:11 2001 Return-Path: Received: from hoho.cs.cornell.edu (hoho.cs.cornell.edu [128.84.96.89]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f8DH6Bq06006 for ; Thu, 13 Sep 2001 13:06:11 -0400 (EDT) From: Emin Gun Sirer Received: (from egs@localhost) by hoho.cs.cornell.edu (8.11.3/8.11.3/C-3.2) id f8DH6AU08675 for egs; Thu, 13 Sep 2001 13:06:10 -0400 (EDT) Date: Thu, 13 Sep 2001 13:06:10 -0400 (EDT) Message-Id: <200109131706.f8DH6AU08675@hoho.cs.cornell.edu> To: egs@CS.Cornell.EDU Subject: 615 PAPER 7 >From clint@csl.cornell.edu Thu Sep 13 11:48:09 2001 >X-Authentication-Warning: eckert.csl.cornell.edu: clint owned process doing -bs >Date: Thu, 13 Sep 2001 11:48:03 -0400 (EDT) >From: Clint Kelly >To: egs@CS.Cornell.EDU >Subject: CS 615 PAPER #7 > >I think this paper is great. The algorithm looks damn good compared to >the others in the paper. My only complaint about the work in this paper >is that the algorithm seems to be a bit complicated. There was a bit much >math in here for me, but I assume that the typical audience for this work >has much more mathematical ability than I do. > From egs@CS.Cornell.EDU Thu Sep 13 13:06:23 2001 Return-Path: Received: from hoho.cs.cornell.edu (hoho.cs.cornell.edu [128.84.96.89]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f8DH6Nq06015 for ; Thu, 13 Sep 2001 13:06:23 -0400 (EDT) From: Emin Gun Sirer Received: (from egs@localhost) by hoho.cs.cornell.edu (8.11.3/8.11.3/C-3.2) id f8DH6Mt08679 for egs; Thu, 13 Sep 2001 13:06:23 -0400 (EDT) Date: Thu, 13 Sep 2001 13:06:23 -0400 (EDT) Message-Id: <200109131706.f8DH6Mt08679@hoho.cs.cornell.edu> To: egs@CS.Cornell.EDU Subject: 615 PAPER 7 >From papadp@ece.cornell.edu Thu Sep 13 11:52:08 2001 >Date: Thu, 13 Sep 2001 11:59:56 -0400 (EDT) >From: "Panagiotis (Panos) Papadimitratos" >X-Sender: papadp@photon >To: Emin Gun Sirer >cc: Panagiotis Papadimitratos >Subject: 615 PAPER 6 > >Review of: " Loop-free Routing using diffusing computations," by >J.J.Garcia-Lunes-Aceves > >Papadimitratos Panos papadp@ee.cornell.edu > >This paper provides an algorithmic framework for the calculation of >shortest, loop-free paths in a network that undergoes dynamic topology >changes. Its main goals are avoidance of temporary loops and fast >convergence. In principle, it improves Distance-Vector algorithms by >utilizing inter-nodal coordination over multiple hops, based on an >elaboration of the concepts of diffusing computation and feasibility >condition (and feasible successor accordingly). In short, it achieves the >above-stated goals by avoiding periodic advertisements and, to some >extent, unnecessary (re) computations. > >The DV problems, tackled by the proposed here diffusing update algorithm >(DUAL), had already been identified at the time of the paper publication, >with several solutions proposed. DV algorithms were known for loop >occurrences and slow convergence, especially due to topological changes. >Techniques (essentially, rules added to the Distributed Bellman-Ford (DBF) >algorithm), such as split-horizon (i.e., do not report routing information >to downstream nodes that already includes them) and poisoned-reversed >(i.e., report infinite distances to upstream nodes) solve the problem, but >not under any connectivity conditions. In general, for an arbitrary >topology and arbitrary topological changes, it is possible that nodes >update their routing tables based on stale topological information (i.e., >distances and next-hop nodes), and, do so depending on their downstream >nodes, without the latter ones having necessarily made the correct >decisions. Accordingly, 'bad news' will be given to the 'interested parts' >after arbitrary delays (e.g., counting to infinity problem, after the link >to or the downstream node fails) and (presumed short-lived) loops will >persist. > >The essence of the problem lies in that nodes implementing DBF react to >each update in a fully distributed, independent manner, by updating their >own view; but, as explained above this could lead to pathological >situations. In principle, for inter-nodal coordination it is necessary to >provide each node with the necessary criteria that allow them to determine >when to initiate such a process, and have a pre-described communication >pattern for such communication (which has to be asynchronous in nature). >The 'sufficient conditions' provided in Section III describe exactly this; >i.e., when a node should proceed with updating its topology view, >depending on the type of triggering event. Then, if the conditions are >satisfied, it is proven that local computation suffices for achieving >loop-freedom. Otherwise, the node must get involved in a coordinated >communication (i.e., the diffusing computation) with the rest of the >(upstream) nodes. > >More specifically, for DUAL which is based on the Source Node Condition >(SNC), a node that does not satisfy the feasibility condition (the cause >is apparently a link, and thus, distance increase) initiates a diffusing >computation. In other words, it becomes active and generates queries that >propagate along an acyclic graph rooted at the initiating node, with the >corresponding replies using the reverse paths. While the node is active, >it cannot change its successor, i.e., choose a different path before the >node is passive again (satisfies the feasibility condition), and when the >computation is terminated (w.r.t the node) and no further changes occur >the feasibility condition is set to infinity; this is exactly one feature >that differentiates DUAL from previous solutions that guaranteed >loop-freedom without (or, with very slow-converging) shortest path >calculation. In case of multiple changes, the same process is repeated, >with each event treated by a distinct diffusing operation (note that >previous solutions had to deal with such events concurrently, and thus, >facing increased complexity). > >In conclusion, DUAL is more responsive than other DV improvements, may >avoid redundant computations and achieve faster convergence in a highly >dynamic environment. However, very frequent topological changes may render >the algorithm inapplicable due to the substantial message complexity, >while such effects would be aggravated for large and dense networks. By >and large, the restrictions imposed by the requirement for route >optimality, in addition to loop freedom, appear to be creating an overhead >that limits the applicability of DUAL in a wireless, mobile setting. > > > From egs@CS.Cornell.EDU Thu Sep 13 13:06:34 2001 Return-Path: Received: from hoho.cs.cornell.edu (hoho.cs.cornell.edu [128.84.96.89]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f8DH6Xq06033 for ; Thu, 13 Sep 2001 13:06:33 -0400 (EDT) From: Emin Gun Sirer Received: (from egs@localhost) by hoho.cs.cornell.edu (8.11.3/8.11.3/C-3.2) id f8DH6Xc08683 for egs; Thu, 13 Sep 2001 13:06:33 -0400 (EDT) Date: Thu, 13 Sep 2001 13:06:33 -0400 (EDT) Message-Id: <200109131706.f8DH6Xc08683@hoho.cs.cornell.edu> To: egs@CS.Cornell.EDU Subject: 615 PAPER 7 >From teifel@csl.cornell.edu Thu Sep 13 11:34:40 2001 >X-Authentication-Warning: disney.csl.cornell.edu: teifel owned process doing -bs >Date: Thu, 13 Sep 2001 11:34:34 -0400 (EDT) >From: "John R. Teifel" >To: >Subject: 615 PAPER 7 > >Loop-Free Routing: > >This paper discusses algorithms for loop-free routing when >dynamic computation of the shortest path is used. It presents >sufficient conditions for loop-free routing for arbitrary algorithms >and introduces a new family of routing algorithms which use diffusing >computations. > >The three conditions for loop freedom are the dinstance increase >condition, the current successor condition, and the source node >condition. The diffusing computation computes by sending queries and >receiving replies along an acyclic graph rooted at the node doing the >computation. A DUAL routing algorithm was proposed and compared to >existing alorithms. > >This paper was rather dense, but otherwise nicely organized. >Difficult to tell how complete the simulations were, given the papers >advanced age. > From egs@CS.Cornell.EDU Thu Sep 13 13:06:47 2001 Return-Path: Received: from hoho.cs.cornell.edu (hoho.cs.cornell.edu [128.84.96.89]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f8DH6lq06053 for ; Thu, 13 Sep 2001 13:06:47 -0400 (EDT) From: Emin Gun Sirer Received: (from egs@localhost) by hoho.cs.cornell.edu (8.11.3/8.11.3/C-3.2) id f8DH6kV08690 for egs; Thu, 13 Sep 2001 13:06:46 -0400 (EDT) Date: Thu, 13 Sep 2001 13:06:46 -0400 (EDT) Message-Id: <200109131706.f8DH6kV08690@hoho.cs.cornell.edu> To: egs@CS.Cornell.EDU Subject: 615 PAPER 7 >From ranveer@CS.Cornell.EDU Thu Sep 13 11:21:37 2001 >X-MimeOLE: Produced By Microsoft Exchange V6.0.4712.0 >content-class: urn:content-classes:message >Subject: 615 PAPER 7 >Date: Thu, 13 Sep 2001 11:21:37 -0400 >X-MS-Has-Attach: >X-MS-TNEF-Correlator: >Thread-Topic: 615 PAPER 7 >Thread-Index: AcE8Z8eeJhhHduBHSOOMc1LX/1ulag== >From: "Ranveer Chandra" >To: "Emin Gun Sirer" >X-MIME-Autoconverted: from base64 to 8bit by sundial.cs.cornell.edu id f8DFLbq23491 > >Loop Free Routing Using Diffusing Computations > >This paper proposes a routing protocol for loop free routing. A well >known problem with Distributed Bellman Ford algorithm is the formation >of loops and counting to infinity. A number of protocols have been >proposed to get around this problem. Most notably BGP and OSPF propose >different techniques and are in common use today. This paper proposes a >new routing protocol: DUAL that uses diffusing computations to avoid >formation of loops. >DUAL is proved to provide loop free routing tables. The main >contribution of this paper is to provide a cheap algorithm for loop >freedom under different circumstances. As is proved, the complexity of >this algorithm approaches ILS in most cases. The essential idea of >diffusing computations to reduce the overhead of protocols is >interesting. >However, DUAL does not seem appropriate for most mobile systems. It has >been designed for the fixed internet for which it seems to give good >performance. A more detailed performance analysis would have confirmed >this belief and provided insights into the behavior of DUAL in the >actual internet. I believe that the more important question in routing >on the internet is the systems behavior: link load, congestion of nodes, >temporary failures and similar issues. From a theoretical viewpoint, I >think the message complexity should include the message length. An >analysis without this measure is misleading the readers about the >overhead of this protocol. Besides, DUAL takes time to stabilize: this >is one of the reasons that make it unstable for mobility. >Overall this paper was theoretically sound, but I think that a theory >paper is good as long as it is backed by more extensive systems results >to prove the practicality of the results. > From egs@CS.Cornell.EDU Thu Sep 13 13:07:01 2001 Return-Path: Received: from hoho.cs.cornell.edu (hoho.cs.cornell.edu [128.84.96.89]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f8DH70q06065 for ; Thu, 13 Sep 2001 13:07:00 -0400 (EDT) From: Emin Gun Sirer Received: (from egs@localhost) by hoho.cs.cornell.edu (8.11.3/8.11.3/C-3.2) id f8DH70R08694 for egs; Thu, 13 Sep 2001 13:07:00 -0400 (EDT) Date: Thu, 13 Sep 2001 13:07:00 -0400 (EDT) Message-Id: <200109131707.f8DH70R08694@hoho.cs.cornell.edu> To: egs@CS.Cornell.EDU Subject: 615 PAPER 7 >From gupta@CS.Cornell.EDU Thu Sep 13 11:10:52 2001 >X-MimeOLE: Produced By Microsoft Exchange V6.0.4712.0 >content-class: urn:content-classes:message >Subject: 615 PAPER 7 >Date: Thu, 13 Sep 2001 11:10:52 -0400 >X-MS-Has-Attach: >X-MS-TNEF-Correlator: >Thread-Topic: 615 PAPER 7 >Thread-Index: AcE8ZjuQ99uipqbwEdW1ugCgydyP2Q== >From: "Indranil Gupta" >To: "Emin Gun Sirer" >X-MIME-Autoconverted: from quoted-printable to 8bit by sundial.cs.cornell.edu id f8DFAqq22333 > >---START----- > >Loop-free routing using diffusing computations, J.J.G.-L.-Aceves. > >Reviewer: Indranil Gupta > >Summary: > >Source routing avoids the count to infinity problem and routing loops as >the >entire route is seen by several nodes - distance vector protocols do not > >have this property, and it is not easy to solve these problems within >their >framework. This paper presents the first loop-free distance vector based >routing >algorithm for dynamic networks. The algorithm presented is effectively a > >link state routing algorithm, but preserves loop-freedom even if the >link >state at different nodes is out of date (i.e., is conservatively safe). > >The author first presents three conditions (DIC, CSC, SNC) each of which >is >sufficient to ensure loop-freedom (but not shortest routes) in routes to >a >destination node. These conditions all rely on the common fact that a >(intermediate) > node updates the "next hop" to a given destination only if it finds a >shorter >path to the destination than the one it already has. The author then >uses >Dijkstra and Scholten's diffusing computations to find shortest loop >free >paths. The algorithm assumes that all messages along a link are >delivered, >and in FIFO order, and that every node sends out beacons to its >neighbors >which estimate the cost of the link. When a node detects a cost change >on a >"next hop" link, it updates its next hop only if this decreases the cost >of >the route compared to the previous existing cost. If not, the source >becomes >active, and a route query is flooded out - intermediate noes receiving >the >query also become active and follow the same decision making in updating > >their routes. When a node (intermediate or source) that is active >receives a >reply for the query from all its neighbors, it resets the shortest path >so >far using these received readings, and treats this as the shortest path >to >the destination - the node then becomes passive. The author proves the >loop-freedom of this algorithm, and also extends it to the case of >multiple >such computations. Link breakages are handled by propagating a cost of >infinity for that link to upstream nodes. The flood of diffusing >computation >messages due to a network partition is handled by having each node wait >for >a longer time to receive all messages from the neighbors before updating >its >routing tables. The message complexity of a diffusing computation per >node >affected by the routing table update is proportional to the node's >degree. > >Comments: > >- Loops in the path, as considered in the paper, primarily arise because >of >downstream nodes on an already-existing path believe, on link changes, >that >upstream nodes have a shorter route to the destination. Other loops such >as >those in a newly constructed path are simply eliminated since every node >has >at most one next hop for each destination. The author could have made >this >distinction clearer in the earlier part of the paper, esp for readers >new >to the topic. > >- The two conditions discussed by the author - existence of shortest >routes, >and loop-freedom in routes, are instances of the liveness and safety >properties respectively (liveness = something good eventually >happens,safety >= nothing bad ever happens). In an asynchronous system, where messages >can >be lost, and clocks are not synchronized, both liveness and safety >cannot be >guaranteed ([FLP] result). Even though the author's model is not an >asynchronous system (messages are never lost), it appears that safety is > >always guaranteed, but there may be attacks on the protocol that can >never >guarantee liveness (eg., constant updating of link costs). This is >surprising. > >- As a general question, relating to the above, given any distance >vector >routing algorithm, can one always formulate an attack on the algorithm >(in >terms of quickly changing link costs, or topologies, even without >messages >losses) that ensures that both liveness *and* safety are never >guaranteed >simultaneously i.e., either shortest paths are never found (liveness >never >guaranteed), or the routes have loops ? In other words, is this a >fundamental limitation of distance vector routing algorithms ? source >routing algorithms ? > >- The author assumes that all messages are eventually delivered (as >broadcasts). Can the loss of messages in the wireless medium lead to >violations of the liveness property, i.e., all nodes are blocked up, and > >shortest routes are never found ? In such cases, it might be worth >guaranteeing liveness in some manner (existence of *some* path), >possibly >violating safety in some of the paths. > >- The data presented Table 1 (pg. 140) does not put the author's DUAL >algorithm in good light. DUAL always seems to have more message count, >event >count and step count than the ILS algorithm, beating in only operation >count (CPU load). DUAL sends about twice as many messages as ILS, but >has a >(much) lower load on the CPU in terms of computation. The authors claim >that >this makes DUAL scalable - in world where wireless bandwidth is scarcer >than >CPU power, is this a correct conclusion ? > >----END---- > h From jcb35@cornell.edu Thu Sep 13 14:49:57 2001 Return-Path: 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.7) with ESMTP id f8DInvq19172 for ; Thu, 13 Sep 2001 14:49:57 -0400 (EDT) Received: from localhost.localdomain (syr-66-66-30-147.twcny.rr.com [66.66.30.147]) by postoffice.mail.cornell.edu (8.9.3/8.9.3) with ESMTP id OAA01624 for ; Thu, 13 Sep 2001 14:49:55 -0400 (EDT) Received: from localhost (john@localhost) by localhost.localdomain (8.11.0/8.11.0) with ESMTP id f8DGj9e23092 for ; Thu, 13 Sep 2001 12:45:11 -0400 Date: Thu, 13 Sep 2001 12:45:08 -0400 (EDT) From: "John C. Bicket" To: egs@CS.Cornell.EDU Subject: 615 paper #7 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII This paper addresses the counting to infinity and routing-table looping problem present in many distributed algorithms for dynamic computation of shortest paths in a computer network. The paper attempts to improves on algorithms previously introduced and while proving that DUAL, the algorithm that they introduce, converges to the correct paths while remaining loop-free and outperform the other algorithms. First, the paper defines the problem and looks at the loop-free that is inherent in distance-vector protocols (dvp's). They define the network model and a seemingly tedious notation (which makes this paper rather dense). They then define conditions for loop free conditions which rely on neighbors updating the next-hop on their routing tables when they have a shorter path to a node. These conditions guarantee the graph is loop free, but they do not necessarily dictate the shortest path. Next the paper introduces their algorithm, a diffusing update algorithm (or DUAL) and provide a formal description of it along with a proof of correctness. These diffusing computations grow by sending queries and shrink by receiving replies along a acyclic graph rooted at the source node. The algorithm works by sending out queries to its neighbors, which will in turn send out queries to ensure they have an correct successor before they return the result back to the source node. Link breaks are handled by sending the value of infinity back through the successors. After proving the correctness of a single diffusing computation for a new route, the author further proves its correctness for multiple computations.l Finally, the simulation provides a performance comparison to DBF, and an ideal link-state algorithm (ILS). They provide graphs showing that DUAL either outperforms the other algorithms in case of node failure, node recovery, link failure, and link recovery. Comments: They seemed to pick simulations that would pick on where the other algorithms would not fair so well, but they assumed that processor time was a valuable resource in these networks, which I am not convinced. And in many cases, the algorithm did not seem to outperform ILS. Also, this paper did not address much regarding mobility and I would have liked to see how this algorithm held up in networks where nodes moved around a lot, maybe they did in the simulation, but they didn't provide information about them. In general, I felt like they could have provided less detail on the proofs (it was quite dense) and more convincing simulation on various network topologies.