From egs@cs.cornell.edu Mon Sep 1 14:47:36 2003 Return-Path: Received: from zinger.cs.cornell.edu (zinger.cs.cornell.edu [128.84.96.55]) by sundial.cs.cornell.edu (8.11.7/8.11.7/M-3.12a) with ESMTP id h81Ilaj24002 for ; Mon, 1 Sep 2003 14:47:36 -0400 (EDT) From: Emin Gun Sirer Received: (from egs@localhost) by zinger.cs.cornell.edu (8.11.7/8.11.7/C-3.4) id h81IlZg26090 for egs+615; Mon, 1 Sep 2003 14:47:35 -0400 (EDT) Date: Mon, 1 Sep 2003 14:47:35 -0400 (EDT) Message-Id: <200309011847.h81IlZg26090@zinger.cs.cornell.edu> To: egs+615@cs.cornell.edu Subject: 615 PAPER 1 This is where your review should appear. From egs@cs.cornell.edu Mon Sep 1 18:23:55 2003 Return-Path: Received: from exchfe1.cs.cornell.edu (exchfe1.cs.cornell.edu [128.84.97.27]) by sundial.cs.cornell.edu (8.11.7/8.11.7/M-3.12a) with ESMTP id h81MNtj15868 for ; Mon, 1 Sep 2003 18:23:55 -0400 (EDT) Received: from EXCHVS1.cs.cornell.edu ([128.84.97.23]) by exchfe1.cs.cornell.edu with Microsoft SMTPSVC(5.0.2195.6713); Mon, 1 Sep 2003 18:23:41 -0400 X-MimeOLE: Produced By Microsoft Exchange V6.0.6375.0 content-class: urn:content-classes:message MIME-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Subject: 615 PAPER 1 Date: Mon, 1 Sep 2003 18:23:40 -0400 Message-ID: <40E631F174C41E4DBE52727E137AF9278B32A3@EXCHVS1.cs.cornell.edu> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: 615 PAPER 1 Thread-Index: AcNw17JmPEPsKkzqSR6ABgdri87GhA== From: "Selcuk Aya" To: X-OriginalArrivalTime: 01 Sep 2003 22:23:41.0201 (UTC) FILETIME=[B2878010:01C370D7] Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from quoted-printable to 8bit by sundial.cs.cornell.edu id h81MNtj15868 This paper describes the Destination Sequenced Distance Vector Routing, which is an improvement over the classic Bellman-Ford Routing. The protocol tries to address some problems such as short and long term loops and poor convergence. Moreover it takes measures in order to use bandwidth more wisely and uses sequence numbers in order to prevent loops. In DSDV, every node maintains full routing table and broadcasts this to other nodes periodically. Between this full routing table advertisements, there are incremental routing table advertisements and in these, not the full routing table but the important changes are advertised. A link`s being broken or a node`s becoming available are considered to be important changes. A node changes a routing entry when it receives an update with a more recent sequence number or an update with the same sequence number and a better metric. However, it may wait a while before advertising the new update if it is not important. The mechanisms of incremental updates and holding off advertisements enable the protocol to use bandwith more wisely. The paper and the protocol have several weaknesses. There are not any simulation results. We do not see any information about how the protocol scales. It may well be the case that when network is large, a lot of redundant data is stored at each node (because full routing tables are stored) and although incremental advertisements are used the protocol may not scale well because of periodic updates. Moreover, the paper does not discuss convergence(although it says that it ackles the problems in classic routing algorithms) and acknowledgement mechanisms 2)DSR This paper describes a protocol,DSR, for dynamic source routing. In DSR, route discovery and route maintenance are reactive. By having reactive route discovery and route maintenance, DSR eliminates the need for periodic updates broadcast from the nodes. Moreover, DSR is designed to work both with symmetric and asymmetric links. Because route discovery is reactive, it is made only when a node wants to transmit a message to a destination for which the node does not have a route entry in its cache. The source node transmits a route request packet and the final destination or an intermediate node which has a route to the final destination replies with a route reply packet which includes the route to the destination. When a node transmits a data packet, the whole route should be included in the header. Route maintenance is also on demand, it is made only when a link breakage is discovered during a packet transmission. Link breakage can be discovered by hope by hop acknowledgements and link level protocols. In absence of these, higher level protocols may be used. Several improvements have been proposed to the basic protocol. For example route cache of intermediate routes may be used for route discovery. Moreover, unfiltered receival of packets may be used in updating route entries and detecting errors. When updating the cache not the full entry but part of it may be changed. This may decrease processing time.DSR results in loop free routes because during route discovery a host discards a route request if it is listed in the route record and checks if there is a loop whenever it is going to reply from its cache. There are some disadvantages associated with DSR. The route records which are carried in the discovery and data packets may pose a problem because they can be long. When the number of nodes in the network is large, reply, error packets and link level acknowledgements may dominate the network. So, reactive routing may shoot back and bandwidth shortage problems may occur. Moreover, I think that, there may be some problems because of this protocol with some applications. Some applications may require that nodes be aware of the new-comers whenever they pop up. However, if the network is stable ( nodes are stationary or they move very slowly), then nodes will not need route discovery. As a result they will not be aware of a new-comer because they will be merrily sending messages to each other. The new-comer may use promiscuious receiving and may learn others slowly but nothing can prevent him from not sending a message unless someone in the network says hello to him. Some multicasting mechanism may be a solution to this problem. The presented simulations in the network are unrealistic. At most 24 nodes are tested. There may be larger networks. So it can be said that, because of the problems presented above, this routing protocol does not scale good. Moreover, in the paper there is nothing about acquisition-latency. In large networks this latency may be high. In fact, because of a node`s holding off a reply waiting for a better reply, latency may be worse than what we would expect from the basic protocol. I do not think that holding off a reply is good for avoiding collisions given that link level protocols have techniques( such as carrier sending) to avoid collisions. 3)AODV This paper describes a protocol , AODV, for on demand routing. AODV enhances DSDV and seems to be influenced by DSR. Route discovery in AODV is on demand. There is no need for the nodes to keep full routing tables and global periodic update messages are not used for management. However, in AODV, local connectivity management is done in a proactive way. AODV requires that neighboring nodes can detect each other. Whenever a node wants to send a packet to a destination and it has not a route entry for that destination a route request packet is broadcast. To this request, an intermediate route or the destination replies with a route reply packet. During this request and reply process , reverse and forward paths are set up dynamically. This is important because this enables AODV packets not to carry the whole routing information in their headers. This may enable the protocol to scale better. For local connectivity management, link level mechanisms and periodic hello messages are used. When a node does not receive a hello message from one of its neighbors in allowed-hello-loss time or it does notice the link breakage through link level mechanisms, it transmits this information to the nodes which may be interested(to the active nodes described below).The paper assumes bidirectional links, but does not discuss whether providing this is always possible. For example if FDD is use, because different frequencies are affected differently by the environment, there can be a danger that not enough node can hear each others` messages. Besides using bandwidth wisely, AODV also aims at preventing unnecessary data storage and processing. First of all, nodes which do not lie on a active route do not have to maintain entry for that entry. Moreover, associated with each route entry is a route caching timeout and a list of active nodes which may be interested in that routes` destination. So when something important happens only those active routes are notified, and stale routes are not cached. Also, there is the route request expiration timer which prevents nodes that do not lie on a path from source to destination keep the reverse path for long. The paper does not discuss the possibility of changing these parameters dynamically. For future work I think that it would be interesting to try to not to broadcast the query message but somehow determine the nodes which will, with high probability, give an answer to the query and forward the query to only them. Combined with the elimination of hello messages, this would result in a more wise use of the bandwidth. AODV, like DSDV uses sequence numbers for keeping the route information up-to-date and for preventing loop formations. A node updates its route entry when an update with a newer sequence number arrives or when an update with the same sequence number but a better metric arrives. The simulation results are explained clearly except some points. First of all, what good-put means is not explained in the paper. Also, although values which are said to be optimal are given for rreq-retries and allowed_hello_loss parameter, it is not clear that these values are optimal for other situations. This may be a problem because there are some big changes in acquisition latency when these parameters are changed a little. From krzys@cs.cornell.edu Tue Sep 2 03:07:40 2003 Return-Path: Received: from dhcp98-182.cs.cornell.edu (dhcp98-182.cs.cornell.edu [128.84.98.182]) by sundial.cs.cornell.edu (8.11.7/8.11.7/M-3.12a) with ESMTP id h8277dj15958 for ; Tue, 2 Sep 2003 03:07:39 -0400 (EDT) Subject: 615 PAPER 1 From: Krzysztof Ostrowski Reply-To: krzys@cs.cornell.edu To: egs+615@cs.cornell.edu Content-Type: text/plain Organization: Cornell University Message-Id: <1062486460.4803.24.camel@dhcp98-182.cs.cornell.edu> Mime-Version: 1.0 X-Mailer: Ximian Evolution 1.2.2 (1.2.2-5) Date: 02 Sep 2003 03:07:40 -0400 Content-Transfer-Encoding: 7bit The Destination-Sequenced Distance-Vector (DSDV) routing algorithm is one of many algorithms based on the distributed version of Bellman-Ford shortest-path algorithm (DBF). Like in the RIP internet routing protocol, and unlike in "link-state" methods, each node maintains information only about the distance (number of "hops") and "next hop" on a way to every known destination and information about current network topology and current routes is distributed over the set of communicating nodes. Unlike in methods based on "source-routing", route for each individual data packet is being dynamically constructed while the packet is in transit. Formation of loops, a common issue with distance-vector algorithms, is avoided by introducing "route sequence numbers", generated by destination nodes when broadcasting route tables. Sequence numbers are associated with routes leading to a given destination by nodes receiving such broadcasted route tables, and such routes are further propagated to the rest of the ad-hoc network in the usual way. A restriction is placed on updates to routing tables that routes with higher sequence numbers are always preferred over routes with lower numbers. This ensures that stale information will never override fresh routing data. It can be proven that this restriction, combined with the usual DBF assumption that of every two equally fresh routes the one with smaller number of hops is preferred, makes it impossible even for short-term loops to emerge. This method of avoiding loops is not only much simpler, and therefore more likely to be applied than any earlier methods based on some sort of internodal coordination, but also likely to prove faster and less expensive, and therefore more suitable to apply in environments where changes in topology are very frequent. At the same time, the total size of routing tables is linear with the number of nodes, like in RIP and unlike in other routing algorithms known at that time. Another major contribution of DSDV is introducing dynamically computed "route settling time", representing an estimate of time required for new routing information arriving at a given node to stabilize. Re-broadcasts of updated routes are delayed, thus helping to avoid flooding of the network and rapid fluctuations in route tables. Other novel ideas include maintaining separate routing tables for data packet forwarding and for route re-broadcasting (so as to avoid situations where new routing information arriving to a given node from different directions triggers a burst of new route propagations). Broken links are handled in the usual way by propagating "negative" information. The way sequence numbers are chosen ensures that broken link data always overrides stale route data while always being overridden by newly discovered routes. The Dynamic Source Routing (DSR) algorithm is similar to link-state methods in that nodes attempt to acquire full information about the current state of network connectivity. Routes can then be calculated locally (using a traditional shortest path algorithm) and therefore are loop-free. Like in the source routing technique known from wired networks, packets have routes pre-determined at the time they are sent by the source and cannot change while packets are in transit. Unlike in DSDV, or in other distance-vector or link-state methods, however, routing information is not gathered and propagated periodically in a distributed fashion, but rather obtained on-demand, when it is needed by a node willing to send a data packet, which helps to reduce control overhead (a) in periods when changes in topology are less frequent, and (b) in situations where some of nodes do not need to communicate and therefore do not need routing information. Obtaining routing information is performed via a "route discovery" algorithm, essentially flooding the newtork with a request (in a way somewhat analogous to breadth-first search, with a list of visited nodes included in the request so as to avoid duplicates and loops) that is ultimately picked up by destination and results in a response sent back to the sender. When destination does not have the route to the sender, it performs its own route discovery, piggybacking response on its own route request (so that the source will ultimately receive the response, update its routing information and reply to the destination using its newly acquired routing data). All routes are cached, and hence an intermediate node may reply to route discovery request without the need for contacting the destination (as long as its route, combined with route from source stored in the request, does not form a loop). An interesting property of this algorithm is the ability to effectively use the "promiscuous mode" of some wireless networks interfaces. Since routing requests contain partial routing information, other nodes overhearing them may use it to update their own routing tables. Broken-link discovery in DSR (based on passive, hop-by-hop or timeout-driven, explicitly requested acknowledgement) is efficiently handled by propagation of error packets along the affected cached routes. A major issue with DSR arises when network becomes partitioned, resulting in repeated route requests. While DSR is superior to DSDV in periods of stability in that it does not involve any control overhead, in the situation described above it will keep consuming bandwidth while traditional DBF-based methods will quickly remove navailable nodes from their routing tables. As a solution, a back-off mechanism is used. Another issue with DSR is its space complexity, naturally limiting its scalability, and this includes cached routes, lists of of recently forwarded requests etc. as well as visited nodes in requests. The Ad-hoc On-Demand Distance Vector (AODV) algorithm combines ideas from DSDV and DSR. Like in DSR, routes are acquired on demand via flooding the network with route requests that eventually reach the destination, acquired information is cached, therefore there are no periodic network-wide broadcasts and nodes that do not need to send, receive or relay messages need not participate in the algorithm and the control overhead can be kept fairly low. Unlike in DSR, however, and somewhat like in distance-vector algorithms, no node maintains complete routing information, route table entries for paths from sources to destinations are dynamically established and kept in intermediate nodes in a distributed way (on a hop-by-hop basis). While intermediate nodes forward a route request sent by source, they build a distributed tree pointing backwards to the source. A response is traveling back to the source along a path in the tree, intermediate nodes forwarding it setup entries in their routing tables to form a distributed routing path pointing forward from the source to the destination and any nodes that are not lying on the path use timeout to remove the unnecessary data structures. In order to keep latency in reasonable limits, intermediate nodes are allowed to reply if they already contain routing information for a given destination. Since this might introduce loops, the idea of sequence numbers was borrowed from DSDV to guarantee that routes are loop-free. Every request or response sent gets a new sequence number and those numbers are recorded on path in the routing tables in all the intermediate nodes. Source node also includes last known destination sequence number in its routing request and intermediate nodes are not allowed to reply to this request if destination sequence numbers in their tables are smaller that the number requested by source. An argument similar to the one used in proving loop-free property of DSDV (using the fact that sequence numbers on a path to destination are non-decreasing) can then be applied to prove that no loops can emerge. Unlike DSDV and DSR, AODV has relatively small memory requirements since only information about actively used routes is stored. A route maintenance algorithm including locally broadcast hello messages (to monitor local connectivity), expiration timers for cached routes and route requests, measuring times since last packets were received from all neighboring nodes are used to keep track of active nodes, hops and routes. Stale routes are quickly deleted. Information about broken links is propagated along the active routes, routes are truncated and source nodes resend route request to re-establish connectivity. Also, any changes in routes to destinations resulting e.g. from node movements are propagated directly to sources along active paths. Simulations show that AODV can scale to hundreds of nodes while keeping goodput ratio of up to 80-90%, with only 10-30% bandwidth overhead and latencies within 200-500ms. From gennady_st@yahoo.com Tue Sep 2 03:08:33 2003 Return-Path: Received: from web13207.mail.yahoo.com (web13207.mail.yahoo.com [216.136.174.192]) by sundial.cs.cornell.edu (8.11.7/8.11.7/M-3.12a) with SMTP id h8278Wj16098 for ; Tue, 2 Sep 2003 03:08:32 -0400 (EDT) Message-ID: <20030902070831.55777.qmail@web13207.mail.yahoo.com> Received: from [141.149.239.238] by web13207.mail.yahoo.com via HTTP; Tue, 02 Sep 2003 00:08:31 PDT Date: Tue, 2 Sep 2003 00:08:31 -0700 (PDT) From: Gennady Subject: 615 PAPER 1 To: egs@cs.cornell.edu MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii This paper describes possibly the first self-organizing (although I'm not quite sure) ad-hock network. The need of a highly-mobile, robust, reliable and highly-efficient computer network in the field (for military applications) has initiated DARPA to sponsor research and development of Packet Radio Network (PRNET). The big advantage of PRNET is the mobility (wireless), quick deployment, and ease of reconfiguration. The self-configuration allows nodes to function as an autonomous group by joining/leaving the network due to changes in network topolgy. PRNET uses multi-hop for packet routing. On the down side, the inability to send and receive at the same time (an inherited property of broadcasting), therefore PRNET implemented a scheduling scheme, Carries Sense Multiple Access (CSMA). This paper is pointing out that performance will likely to suffer due to large neighborhoods but with out specifying on how big is "large" (my assumption is more then 50 PR nodes, since paper suggest the network size of about 50 PR nodes). Also this paper does not give the explanation of the limit of PR nodes is 138 (is it due to congestion, fast queue growth, etc...). This paper is lacking implementation detail how quality values being dammpred. The paper does not mention the scalability of this system (with a little exception of mentioning that there is a research in progress with algorithms that would allow thousands of nodes, again no specifics). Obviouslythis protocol could benefit by allowing more clients and better performance (assuming for more then 50 clients, most likely to congestion, or possibly an out-of bounds queue growth). This project would also benefit by increasing the limit to handle more then 16 neighbors. My personal thought that this research project was a major contribution to the wireless communications. - Gennady Staskevich __________________________________ Do you Yahoo!? Yahoo! SiteBuilder - Free, easy-to-use web site design software http://sitebuilder.yahoo.com From egs@cs.cornell.edu Tue Sep 2 09:38:08 2003 Return-Path: Received: from exchfe2.cs.cornell.edu (exchfe2.cs.cornell.edu [128.84.97.28]) by sundial.cs.cornell.edu (8.11.7/8.11.7/M-3.12a) with ESMTP id h82Dc7j25092 for ; Tue, 2 Sep 2003 09:38:07 -0400 (EDT) Received: from mail.cs.cornell.edu ([128.84.97.28]) by exchfe2.cs.cornell.edu with Microsoft SMTPSVC(5.0.2195.6713); Tue, 2 Sep 2003 09:37:48 -0400 Received: from dhcp98-166.cs.cornell.edu ([128.84.98.166]) by mail.cs.cornell.edu over TLS secured channel with Microsoft SMTPSVC(5.0.2195.6713); Tue, 2 Sep 2003 09:37:47 -0400 Subject: 615 PAPER 1 From: Hitesh Ballani To: egs+615@cs.cornell.edu Content-Type: text/plain Organization: Message-Id: <1062509878.5785.19.camel@dhcp98-166.cs.cornell.edu> Mime-Version: 1.0 X-Mailer: Ximian Evolution 1.2.2 (1.2.2-5) Date: 02 Sep 2003 09:37:58 -0400 Content-Transfer-Encoding: 7bit X-OriginalArrivalTime: 02 Sep 2003 13:37:47.0847 (UTC) FILETIME=[65AD8570:01C37157] The first paper discusses the DSDV Routing, a modification of the DV routing algorithm which ensures loop free routes and as far as I can infer, solves the count to infinity problem.While each node has a routing table giving the next hop for all the nodes in the network, the most important modification in this is the inclusion of sequence numbers issued by the destination itself( unless the link is broken in which case it is issued by the intermediate node and is odd). This allows a node to differentiate between old and new updates leading to avoidance of stale and loop free routes.Also, a node need not send out it's table ( full dump ) each time it advertises, an incremental dump of the changed sequence numbers and metrics suffices most of the time. Besides,the dynamic nature of the network necessitates a dampening of the fluctuations which is done by keeping information about settling times in the table and delaying sequence number change, etc. advertisements until after the delay time expires( although broken links are announced immediately). For loop freeness it uses the concept of the sink tree - formed using the next hop indicator's for a particular destination. In this tree, as we go up from the leaves to the root, the sequence number is non- decreasing. But for a loop to exist, a node must loop back to a node with lesser or equal sequence number, so the only common criteria is that the 2 nodes should have equal sequence number's, in which case the lower metric condition ensures that no loop is formed. While the concepts of sequence numbers and dampening seem to be very exciting but evidence for the same is needed. And I feel that despite all their efforts the algorithm will still have a convergence time on the higher side, especially if the network is very dynamic and is of a large size . A good idea during simulation would be to determine the actual effects of dampening on b/w utilization and convergence. And then there is the issue of scalability. The second paper discusses the DSR algorithm which is a source routing technique adapted for wireless networks. It scores over conventional routing protocols like DV as it is reactive and hence does not require periodic broadcasting of advertisements. Since it is the source that provides the path to the destination so each node maintains a route cache and if the desired route is not in the cache, it is obtained using a route discovery protocol - the reply for which may come from the destination or an intermediate node's cache. And since there are no periodic updates to monitor missing links, so it is the route maintenance procedure that monitor's the operation of the route and informs of routing errors. It also has a number of optimizations such as the replies from the cache, delays in the response to avoid congestion and sending non-propagating requests. There is also piggybacking, not only in route replies/errors but also route discoveries, and promiscuous mode pick up of errors. The loop avoidance in this case is simplified by the fact that it is a source routing protocol, so the source can check for loops in the route. And the formation of loops when hosts reply using their cache - i.e replies formed using the route record and the cache entry is checked for by the individual hosts sending the reply. One of the positive aspects of the protocol is that they have not assumed the bi-directionality of the links. However the simulations have been run for a small number of nodes and a small number of hosts (linearly scalable) and is full of variables whose values seem to have been chosen arbitrarily. Laying out these variables and defining their effect on the performance could be the next step. Besides, security is an aspect that has not been in both these papers- the fact that the piggybacked route discovery is spoofed by an intermediate node replying from it's cache could be dangerous. The third paper discusses the AODV, which could be termed as a hybrid routing protocol as it couples reactive features such as dynamically obtaining information for routes on demand with proactive features such as HELLO messages to get local information. It is a variation of the DV routing protocol - so each node knows just the next hop for a destination but the variation here is that this information is maintained only for active routes, i.e. routes that have been demanded. As in source routing, routes are obtained through path discovery only when a packet has to be sent, but the entire path is not specified by the source which could be a big plus in large networks. Summarily, the protocol has RREQ's (route requests) - to request for routes, RREP's ( route replies ) - as replies from intermediate/destination nodes and HELLO messages or local broadcasts for neighbour discovery. Hence, when a route is demanded, a RREQ is sent by the source to it's neighbours and so on, each of which maintains information about the reverse path while forwarding the request until some node with a higher sequence number for that destination replies which is sent along the remembered reverse route. Also, it uses the concept of sequence number's in order to maintain most recent routing information between nodes and ensure loop-freeness - as the sequence number's cannot decrease along an active path, so the existence of a loop would violate the property that for the same sequence number, the path with a shorter metric is preferred. And while the authors must be commended for the scalability and the fact that they have tried to determine the optimal value of the different parameters instead of some magic numbers, but the simulation scenario has a lot of randomness, not necessarily present in a real system. Besides, since the protocol seems to be a combination of the better halves of the DSDV and the DSR, figures comparing the three and bringing out empirical evidence for the superiority of the AODV would have been nice. From egs@cs.cornell.edu Tue Sep 2 10:24:29 2003 Return-Path: Received: from exchfe1.cs.cornell.edu (exchfe1.cs.cornell.edu [128.84.97.27]) by sundial.cs.cornell.edu (8.11.7/8.11.7/M-3.12a) with ESMTP id h82EOSj07029 for ; Tue, 2 Sep 2003 10:24:28 -0400 (EDT) Received: from EXCHVS1.cs.cornell.edu ([128.84.97.23]) by exchfe1.cs.cornell.edu with Microsoft SMTPSVC(5.0.2195.6713); Tue, 2 Sep 2003 10:24:11 -0400 X-MimeOLE: Produced By Microsoft Exchange V6.0.6375.0 content-class: urn:content-classes:message MIME-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Subject: 615 PAPER 1 Date: Tue, 2 Sep 2003 10:24:11 -0400 Message-ID: <40E631F174C41E4DBE52727E137AF9278C4B63@EXCHVS1.cs.cornell.edu> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: 615 PAPER 1 Thread-Index: AcNxXeeQ/lI7mPcuQyS5QJSASujEWw== From: "Bernard Wong" To: X-OriginalArrivalTime: 02 Sep 2003 14:24:11.0932 (UTC) FILETIME=[E11F2DC0:01C3715D] Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from quoted-printable to 8bit by sundial.cs.cornell.edu id h82EOSj07029 DSDV: The paper "Highly Dynamic Destination-Sequenced Distance-Vector Routing (DSDV) for Mobile Computers" introduces the use of sequence numbers to adapt the traditional Distributed Bellman-Ford (DBF) algorithm for use in an ad-hoc network. The problem of using DBF in an ad-hoc network is the formation of both short-lived and long-lived loops, both of which are possible due to stale routing information being present in the routing table of each node caused by movement of the nodes. DSDV introduces a monotonically increasing sequence number created for each of its routes by the destination node, which is used in determining whether a received update is fresh or stale. As DSDV will always choose the shortest path update from the set of updates that contain the largest sequence number, routing loops are avoided without the need for internodal coordination. DSDV works by requiring each node to broadcast to its current neighbors its routing table, which consists of the destination node, the next hop node, the distance metric, the sequence number, and other path related data. As each node receives this broadcast, it will update its own routing table given that the sequence number is larger or that the sequence number has not changed but the distance metric has been reduced. Transmitting packets is accomplished by having each of the next hop nodes on the route forward the packets along on behave of the source node. DSDV's main weakness is its high bandwidth usage. Periodic updates sent by each individual node might not be that bandwidth intensive given a reasonably large period and modest nodal movement. However, each time nodal movement is sufficiently large such that the path distances between nodes are changed, the channel may be flooded as updates are triggered due to the path length changes. Power usage is also significant as each node regardless of whether the network is being used sends the periodic updates. This can be especially damaging if the periodic updates interferes with the power management of the wireless devices (i.e. prevents the device from entering sleep mode). DSR: The Dynamic Source Routing (DSR) protocol was designed to eliminate the need for nodes to periodically send updates to other nodes. This greatly eliminates the bandwidth and power issues associated with Distributed Bellman-Ford (DBF) based protocols, as bandwidth and power is only consumed when there is actual network traffic. Furthermore, DBF based protocols require each node to know the distance to every other node, which is normally unnecessary and increases the size of the routing updates. In DSR, routes are discovered as they are needed. DSR works by having the sender include the complete sequence of nodes through which to forward the packet from the source to the destination inside the packet's header. If a route to the destination node is not known, a route discovery protocol is initiated. The route discovery protocol works by having a route request packet broadcasted by the sender. If a node other than the desired destination node receives this request for the first time, the request is modified by having the node sequence appended with the current host and the request is re-broadcasted. When the destination node receives the route request, a route reply is sent back with a copy of the route from the route request packet. Routing loops can be avoided by discarding route requests where the host's address is already listed in the route record, as this guarantees that no single copy of the request will propagate in a loop. A weakness in the DSR protocol is its dependence on including the entire node sequence in the packet header. This can lead to scaling issues as the size of the ad-hoc network increases, where the header size may become excessively large thereby reducing the efficiency of the channel. The is further accentuated by the fact that many wireless devices have a relatively small Maximum Transmission Unit (MTU) size compared with wired network devices in order to reduce latency. Another weakness is the increased route acquisition latency compared to DBF based protocols, as data packets can no longer be sent until the route discovery protocol completes. A result of using a node discovery protocol instead of using periodic update advertisement is the inability to know which nodes are currently operational on the network. Only by sending a packet to a targeted host or by promiscuously listening to packet traffic can DSR determine which hosts are currently in the network. This can become a problem if a user node enters a foreign network and do not know what other nodes are on this network. AODV: The paper "Ad-hoc On-Demand Distance Vector (AODV) Routing" introduces a distance vector routing algorithm that does not require global periodic advertisements of routing updates. Instead, a broadcast route discovery mechanism similar to the one found in Dynamic Source Routing (DSR) is used. However, unlike DSR, AODV relies on dynamically establishing route table entries at the forwarding nodes, which removes the need to store the entire sequence of nodes for a particular route in the packet header. In order to achieve loop-free routing while relying on routing information found in the forwarding nodes, the concept of the destination sequence number is borrowed from Destination-Sequenced Distance Vector (DSDV) routing. Therefore, similar to DSDV, route information of a forwarding node is only updated when it receives a route reply packet where either the destination sequence number is larger than the previously recorded number or the destination sequence number is the same as the recorded number but the path length is smaller. The operation of AODV is as follows: If a route from a source node to a destination node is unknown, a path discovery process is initiated. A route request packet is sent to its neighbors, where each neighbor either sends a route reply back to the source or rebroadcasts the route request. As the route request packet travels from source to destination, a reverse path route is created in the forwarding nodes, and similarly, a forward path route is created by the request reply. Once the route is known, then a data packet can simply be broadcasted from the source node with the desired destination node set in the header, and the packet should be routed correctly through the forwarding nodes to the destination node, given the nodes configuration has remained the same since the last path discovery. A potential weakness of AODV is the flooding of route requests that can occur during path discovery. Without the promiscuously snooping of packets and random reply delays as is done by DSR, a route request can be re-broadcasted over multiple hops even if a cached route was quickly found in the first hop from another node. Implementing either promiscuous snooping of packets or a multi-level and multi-try route request (i.e. first attempt allows for maximum of one hop, second attempt allows for two hops, etc.) can be used to overcome this weakness. Bernard Wong From egs@cs.cornell.edu Tue Sep 2 10:26:14 2003 Return-Path: Received: from exchfe1.cs.cornell.edu (exchfe1.cs.cornell.edu [128.84.97.27]) by sundial.cs.cornell.edu (8.11.7/8.11.7/M-3.12a) with ESMTP id h82EQDj07938 for ; Tue, 2 Sep 2003 10:26:13 -0400 (EDT) Received: from mail.cs.cornell.edu ([128.84.97.27]) by exchfe1.cs.cornell.edu with Microsoft SMTPSVC(5.0.2195.6713); Tue, 2 Sep 2003 10:25:56 -0400 Received: from dhcp98-136.cs.cornell.edu ([128.84.98.136]) by mail.cs.cornell.edu over TLS secured channel with Microsoft SMTPSVC(5.0.2195.6713); Tue, 2 Sep 2003 10:25:56 -0400 Subject: 615 Paper 1 From: Biswanath Panda To: egs@cs.cornell.edu Content-Type: text/plain Organization: Message-Id: <1062512773.25849.10.camel@dhcp98-136.cs.cornell.edu> Mime-Version: 1.0 X-Mailer: Ximian Evolution 1.2.2 (1.2.2-5) Date: 02 Sep 2003 10:26:13 -0400 Content-Transfer-Encoding: 7bit X-OriginalArrivalTime: 02 Sep 2003 14:25:56.0630 (UTC) FILETIME=[1F86D360:01C3715E] Summary on "Highly Dynamic Destination-Sequenced Distance-Vector Routing (DSDV) for Mobile Computers" This paper provides a new approach to the classic Distance Vector Routing Protocol and makes it suitable to use in a ad-hoc environment. This is a proactive routing protocol. Like in Distance Vector Routing each station of the network maintains a routing table which contains the path to each other station in the network. In order to take care of the dynamically varying topology of the ad-hoc network routing updates are transmitted periodically by all stations to their neighbours(This period is calculated based on a metric which takes into account the time difference between the first and best route arrivals for a station). Updates are also sent if there is substantial change in a route like a broken link(the "inf" metric symbolizes such change in the route) The updates contain the sequence number of the update from the sender, the destination address, number of hops, and the sequence number of this route as stamped by the destination. These updates enable stations to modify and keep their routing tables up-to-date. When station receives an update it sees if there are any routes with newer sequence numbers or better metrics. The policy of choosing paths with better metrics when seq number is same may cause route fluctuations at an alarming rate. Therefore the protocol takes extra care to damp these fluctuations. The protocol is loop free because the next node indicators to each destination induce a tree rooted at that destination. When a node i receives an update from k regarding the path to x, the path can be something like x........ki. Now x starts the broadcast with a seq no. 's'. This 's' increases as we go towards i. i chooses k as next hop only if current seq number is less than s. For i to form loop in the next hop it has to choose a node from x.....k, which is not possible as they have sequence numbers lower than current sequence number at i. The paper does not mention clearly how the sequence are created and incremented. This makes understanding the proof of the protocol being loop free difficult and unclear. The paper basically talks about a modified distance vector routing protocol but gives no idea as to why it works better in an ad-hoc environment. There are no results to show that the protocol works better in an adhoc environment as compared to the standard Dist Vector Algo. Future work is to simulate results based on this protocol. From de46@cornell.edu Tue Sep 2 10:37:22 2003 Return-Path: Received: from postoffice6.mail.cornell.edu (postoffice6.mail.cornell.edu [132.236.56.21]) by sundial.cs.cornell.edu (8.11.7/8.11.7/M-3.12a) with ESMTP id h82EbLj11478 for ; Tue, 2 Sep 2003 10:37:21 -0400 (EDT) Received: from uportal0 (uportal0.cit.cornell.edu [132.236.229.130]) by postoffice6.mail.cornell.edu (8.12.9/8.12.6) with ESMTP id h82EbJWf015378 for ; Tue, 2 Sep 2003 10:37:19 -0400 (EDT) Date: Tue, 2 Sep 2003 10:37:19 -0400 (EDT) Message-ID: <31344523.1062513439624.JavaMail.webber@uportal0> From: "Unrecognized person: de46" To: egs+615@cs.cornell.edu Subject: 615 PAPER 1 Mime-Version: 1.0 Content-Type: text/plain; charset=UTF-8 X-Mailer: uPortal WEB email client 2.10 Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from quoted-printable to 8bit by sundial.cs.cornell.edu id h82EbLj11478 # Highly Dynamic Destination-Sequenced Distance-Vector Routing (DSDV) for Mobile Computers # The DSDV is designed basically as a Distance Vector (DV) algorithm with some additions to make it more suitable for ad hoc networks. The most important addition is the usage of sequence numbers (published by "destination") to avoid loops. The main reason of loops in a DV protocol is updating routing tables based on incorrect (old) information. However, by giving a number to each update packet, hosts can determine which packets are up-to-date and which are not. These numbers are given in a sequence way. On every update advertisement for an active link, the sequence number is incremented and only even numbers can be used. If a broken link is occurred, the sequence number is incremented to make it an odd number. By using the sequence numbers routing tables can be updated in two situations: 1) Using update information with a newer (grater) number, which indicates that the new information is more up-to-date. 2) Using update information with the same sequence number but with a better metric. As a result, hosts use only the most up-to-date information and do not update their routing tables wrongly. Secondly, besides full dumps, routing information packages can also be broadcasted as incremental dumps, which decrease the amount of broadcasted packets in certain situations. Moreover, the DSDV allows immediate route advertisement to decrease the reaction time. On the other hand hosts can delay such advertisements to avoid fluctuations, which can occur because of multiple advertisements from its neighbors. Due to the above-mentioned properties DSDV can be considered as a simple, loop free protocol for ad hoc networks. However, distribution of route information to the whole network may produce unused route information. How DSDV ensures that routes are loop-free? Since DSDV is DV protocol every node has route information to other nodes in the network via its neighbors. >From this point of view the whole network can be seen as a directed tree. First, lets assume that the network is stable. At this point a change in the topology is required to form a loop. There are two possible situations, which can lead a change in routing tables. 1) By a broken link to a neighbor. It is obvious that a broken link cannot form a loop in a directed tree, because only the next hope will be set to nil. 2) By changing the next hope of an existing route to a different neighbor. As mentioned above, there are two possible situations that can lead an update in a routing table. -By receiving a packet with a grater sequence number. Lets assume that host i gets such an update information from its neighbor k about a route to host j. In this situation i will chose its next hope as k and sends its packets over k to reach j. In order to form a loop, the route from k to j has to include i, which implies that the k cannot has a greater (newer) sequence number without the knowledge of i. As a result, if k sends its packets over i, it cannot have a greater sequence number than i, which contradicts with the first assumption. -By receiving a packet with an equal sequence number but with a better metric. According to the theorem proved by Jaffe and Moss (A responsive distributed algorithm for computer networks) the paths do not form loops when weights changes. # Dynamic Source Routing (DSR) in Ad Hoc Wireless Networks # One weak side of the Distance Vector (DV) algorithms for Ad Hoc networks is the periodic broadcasts to update routing tables. These periodic broadcasts can have negative effects over the limited resources (power, memory, CPU, etc.) of the mobile hosts. Because of this reason DSR proposes a different route finding technique based on dynamic source routing. Here, the sender of a packet defines the destination in a dynamic way called “route discovery” or by using route cache. At the route discovery, a route is dynamically constructed using broadcast messages. When a broadcast message reaches to the destination a “route reply” message (containing the “record of the route”) is sent to the initiator. The route to the initiator can be obtained in three ways: 1)From the cache of the destination, 2)By reversing the route in the route discovery packet. However, this requires bi-directional communication, which may not be possible. 3)By sending the route reply attached to a route discovery packet targeting the initiator. Moreover, multiple route discovery messages are avoided using initiator address and request id. When the route information is obtained it is placed into the header of packets for the routing. This technique not only decreases the usage of resources but also propose a more flexible way compared to DV to adapt itself to possible topology changes. Besides the route discovery technique, “route maintenance” is used to detect the errors in a route without the usage of periodic broadcasts. When an error is detected the host sends a “route error” packet and the routes are truncated. The route error package can be sent using by the three above-mentioned techniques, which are used for route reply packets. Additionally, the error message can be buffered and then another route discovery can be implemented to send the route error packet. Some optimizations are implemented to develop the overall performance DSR. The most important one is the usage of caches to complete route information before the broadcast reaches to the target. If a host has an active route to the destination it can append the later part of the route from its cache instead of another broadcast. However, there can be more than one reply, which can cause problems like collision. In order to avoid this problem, hosts delay their replies and listen the network for a better route. If a better route cannot be found the route reply is transmitted. Another optimization for the caches is the usage of hop numbers. By these numbers the unnecessary propagation of route request packets can be avoided. There are other optimizations for error handling mechanisms, as well. First of all, route discovery messages are controlled to decrease the overhead that they can bring in a portioned network. Moreover, hosts can listen the network for error messages to update their route caches. Another optimization is used to inform relevant hosts about errors if the route error packet comes from a different way then the route discovery packet. How DSR ensures that routes are loop-free? Possible situations that can form a loop are analyzed below. 1) route request messages can create a loop. By the help of initiator address and requet_id information, hosts descards multiple route requests, which avoids the formation of a loop. 2) route reply messages can create a loop. These packets can form a loop if their route is completed using a route cache. However, this problem is avoided by an optimization. A host appends a route using its cache after checking whether it forms a loop or not. # Ad hoc On Demand Distance Vector Routing # AODV combines the dynamic source routing of the DSR and the sequence number technique of the DSDV. To find the route first the source node broadcasts a route request (RREQ) packet containing: broadcast_id, source sequence number, destination sequence number. Broadcast_id is used to avoid redundant broadcasts. Sequence numbers are used to indicate the freshness of the routes to the source and to the destination. During the travel of the packet to the destination the “reverse path” (route to source) information is gathered. When the broadcast packet reaches to the destination or to a node that can complete the path a route reply (RREP) message is sent back to the source. During the travel of RREP the route back to the destination is constructed. There may be other nodes, which are not in the path of the RREP. These nodes’ reverse pointer will be deleted after a certain period of time. If further RREPs come, these messages will be taken into consideration regarding their destination sequence number. The source host starts the communication as soon as it gets the first RREP, if other RREPs come, the route can be updated. AODV also checks the activeness of paths. A host can learn its neighbor’s situation from both broadcast messages and from hello messages, which are just sent to neighbors. If a broken link is detected a special RREP is sent to the related hosts. Then a new RREQ can be sent by the hosts, which want to communicate to the destination. In routing tables other information can also be stored to increase the efficiency of the AODV, like the list of active neighbors. As a result AODV uses bandwidth effectively and can adapt itself to topology changes quicker than the DSDV. Furthermore, since it is a DV algorithm, it uses the advantages of complete routing tables during route cache. Last, route information is only gathered when there is a demand, which avoids production of unnecessary route information. On the other hand it uses symmetric links between neighbors, which may not be possible in every situation. How AODV ensures that routes are loop-free? Since the routes have destination sequence numbers it is impossible to form loops in AODV. Lets assume that a loop is formed between the nodes X1 -> X2 -> .... -> XN -> X1... If we take Ti as the sequence number for the route of Xi, then we will come up with T1 <= T2 <= .... <= T(n - 1) <= Tn <= T1, which implies that all Ti values are equal. If the Ti values are equal then they must be all set with same PREP. And lets take Mi as the metric to the destination for host Xi. Because of the loop, the relation between the Mi values should be like Mi = M(i + 1) + 1, which implies that M1 = Mn + (n - 1) and Mn = M1 + 1. Therefore n must zero, which is impossible under the usage of same PREP. DOGAN FAMER ENGIN From fa33@cornell.edu Tue Sep 2 10:50:41 2003 Return-Path: Received: from postoffice2.mail.cornell.edu (postoffice2.mail.cornell.edu [132.236.56.10]) by sundial.cs.cornell.edu (8.11.7/8.11.7/M-3.12a) with ESMTP id h82Eoej15157 for ; Tue, 2 Sep 2003 10:50:41 -0400 (EDT) Received: from fawaz (dhcp-97-228.cs.cornell.edu [128.84.97.228]) by postoffice2.mail.cornell.edu (8.9.3p2/8.9.3) with ESMTP id KAA27164 for ; Tue, 2 Sep 2003 10:50:34 -0400 (EDT) From: "Fawaz Khalil Allahwala" To: Subject: 615 PAPER 1 Date: Tue, 2 Sep 2003 10:50:32 -0400 Message-ID: <000801c37161$8fa90110$e4615480@fawaz> MIME-Version: 1.0 X-Security: MIME headers sanitized on sundial.cs.cornell.edu See http://www.impsec.org/email-tools/sanitizer-intro.html for details. $Revision: 1.138 $Date: 2003-01-26 11:25:54-08 X-Security: The postmaster has not enabled quarantine of poisoned messages. Content-Type: multipart/alternative; boundary="----=_NextPart_000_0009_01C37140.08976110" X-Priority: 3 (Normal) X-MSMail-Priority: Normal X-Mailer: Microsoft Outlook, Build 10.0.2627 Importance: Normal X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2800.1165 This is a multi-part message in MIME format. ------=_NextPart_000_0009_01C37140.08976110 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit AODV Each host operates as a specialized router. Routes are obtained on demand with little or no reliance on periodic advertisement. Nodes do not discover or maintain the routes about the other unless they have to communicate with each other. It uses hello broadcast to be aware of its neighborhood. Instead of source routing the AODC relies on dynamically establishing route table entries at intermediate nodes. In order to maintain a loop free topology it makes uses of monotonically increasing sequence numbers which is a counter to supersede stale values so same node is never used twice in a route. The protocol depends on bidirectional links but the paper also mentions that its certain modifications to the algorithm can make this requirement unnecessary Algorithm: When a node needs to communicate to another node not directly in its neighborhood (neighborhood is discovered using broadcast hello so its trivial) its sends a RREQ message with a unique -->

AODV

Each host operates as a specialized router. Routes are obtained = on demand with little or no reliance on periodic advertisement. Nodes do = not discover or maintain the routes about the other unless they have to = communicate with each other. It uses hello broadcast to be aware of its = neighborhood. Instead of source routing the AODC relies on dynamically establishing = route table entries at intermediate nodes. In order to maintain a loop free = topology it makes uses of monotonically increasing sequence numbers which is a = counter to supersede stale values so same node is never used twice in a route. = The protocol depends on bidirectional links but the paper also mentions that = its certain modifications to the algorithm can make this requirement = unnecessary

 

Algorithm:

When a node needs to communicate to another node not directly in = its neighborhood (neighborhood is discovered using broadcast hello so its trivial) its sends a RREQ message with a unique <source_address, broadcast_id) pair. If a receiving node has = already received this pair then it drops the RREQ otherwise it broadcast it to = its own neighborhood after increasing its hop-count. The RREQ of best hop-count is sent only. = The receiving node also replies with a route reply packet. The interplay of = these messages (typical reverse path and forward path setup) results in the = route setup

 

 

 

 

 

 

DSDV

IT is based on periodic advertisement and it’s a = modification to the basic Bellman Ford routing mechanism. It requires the nodes to = broadcast its entire routing table fairly frequently to avoid an expired topology = to go undetected. Any new routing information received is delayed for a small duration to dampen any fluctuations in the = topology.

In case of a broken link the neighboring detecting host = immediately broadcast the link broken message with a new sequence number. This is = the only time that some other node and not the destination host generate the = sequence number. It also makes use of the sequence number to detect and avoid = loops. Each node maintains the full routing table which is periodically broadcast. Additionally important topological changes such as lost or new node are immediately broadcast (after the required damping time) so that everyone = is aware of the changes immediately.

 

Algorithm:

On receiving the broadcast the route is updated only if the = sequence number is better than the old one or the sequence number is same but the = metric is better.

 

Comment:

Periodic broadcast of the entire routing table seems to be a = waste of the bandwidth. The O(n2) time will not scale = for large networks.

 

 

 

 

 

 

Dynamic Source Routing

It uses no periodic advertisement. It does not require = bidirectional links between hosts.

On transmission of a data packet, the entire route is defined by = the source node in the packet header. The packet is then simply forwarded = according to the route specified in the header. The sender constructs the source = route according to the route cache it has constructed from all the information = it has gained from previous transmissions. If no route is found in the route = cache then the sender uses the route discovery protocol to discover the path. = It also uses the sender-sequence number pair to detect redundant route discovery messages.

 

Route Discovery Algorithm:

On receiving the route discovery message it checks in the packet = route whether its address already exist. If yes then this packet went through = a loop so it is discarded.

If the destination address is its own address then the packet = has reached its destination so return the route using the route reply = packet. In all other cases simply append the host address and = rebroadcast.

 

Comment:

The route discovery protocol is not dependent on bidirectional = links. However it does not seems to consider the cost of a link or cost of = alternate route as well. This can be added to the protocol by adding a cost-metric = field to the route discovery packet. Each node which receives this packet = updates this cost metric. When a node receives a discovery packet which it has = already seen then it dumps it only if the cost metric is higher. =

 

------=_NextPart_000_0009_01C37140.08976110-- From mw223@cornell.edu Tue Sep 2 11:29:18 2003 Return-Path: Received: from postoffice.mail.cornell.edu (postoffice.mail.cornell.edu [132.236.56.7]) by sundial.cs.cornell.edu (8.11.7/8.11.7/M-3.12a) with ESMTP id h82FTHj25753 for ; Tue, 2 Sep 2003 11:29:17 -0400 (EDT) Received: from [128.253.151.52] (r101192.resnet.cornell.edu [128.253.151.52]) by postoffice.mail.cornell.edu (8.9.3p2/8.9.3) with ESMTP id LAA29747 for ; Tue, 2 Sep 2003 11:29:09 -0400 (EDT) Mime-Version: 1.0 X-Sender: mw223@postoffice.mail.cornell.edu Message-Id: Date: Tue, 2 Sep 2003 11:29:14 -0400 To: egs+615@cs.cornell.edu From: "Matthew A. Wachs" Subject: 615 PAPER 1 Content-Type: text/plain; charset="us-ascii" ; format="flowed" DSDV is an improvement to prior distance vector algorithms that eliminates the possibility of both short- and long-term routing loops and is tailored for use in (possibly) rapidly changing ad-hoc networks. A routing table is kept by each node and is updated through both periodic and change-triggered broadcast messages. Every node is aware of the lowest recent "cost" (usually the measured by the number of hops) of routing a message to each other node, and through which of its neighbors it must send a packet destined for that node in order to realize that cost (that node will consult its own table when it needs handle the packet). A node broadcasts to its neighbors the cost, for each node in the network, of routing a message first through itself and then through its own best known route to that node. Its neighbors will then decide, on a destination-by-destination basis, if an advertised route they have received is preferable to the one (if any) that they already know, and replace the old route if necessary. Thus, the chain of events to form the routing tables begins by each node advertising that it can reach itself without any cost to its neighbors; followed by each of its neighbors telling each of their neighbors that they can reach the original node with, say, a cost of one (hop), and so on. Excessively rapid propagation of changing routes is mitigated by a delay at each node to smooth out transient fluctuations (by attempting to assure that a better route is not received shortly after a worse one has been broadcast); however, notification that a link to a node has been broken, and that packets can no longer be routed to or through it, is disseminated immediately. Loops are avoided by a special ordering of routes used in determining which of two routes is "better" (only the "best" route is kept). Each route was assigned a serial number, increasing with time, by the target node that advertised a route to itself (which began the chain of propagation), and that serial number is preserved as the information is propagated and modified by each node. Serial numbers are only interpreted in the context of their particular destination node and are only generated for that node by that node, so synchronization is unnecessary. The route with the highest sequence number (even if another is less costly) is always preferred, because the newest information reflects the latest topology; but in the event of a sequence number tie, the "cheapest" route wins (which occurs when the same broadcast was routed through two different paths, one of which was less costly). Loops cannot be completed for a route to destination D because a proposed link from node A to node B that would complete a loop would either need to have a higher sequence number or be cheaper than the previous link out of node A, to be accepted by A. However, since this would create a loop, B's route to D that it is advertising to A is already through A. Broadcasts pertaining to a route travel backwards along the route being discovered, starting at the source, and sequence numbers are not incremented as they are propagated. Thus, A must already have seen and propagated the broadcast being set back to it from B, and B must have received it as a consequence of A's forwarding. Therefore, its sequence number will be the same as or lesser than that of A's current route (because it has already been "seen" by A), but a greater cost (because its path is a concatenation of A's current path to D and a path from B to A). Thus it can have neither a greater sequence number, nor a lesser cost, than A's present route, and will never replace it to create a loop. DSR is an alternative ad-hoc network routing protocol that is quite different from DSDV. One difference is that DSDV maintains and discovers routes whether or not they are used, while DSR only attempts to discover a particular route when it is needed. Another difference is that DSR tolerates one-way links. A third contrast is that while DSDV relies on each node along a route to decide how next to forward a packet, the source in DSR affixes a predetermined route to each packet, and nodes examine this route to look up the next hop for that packet ("source routing"). When a host wishes to send a packet to a certain destination, it first checks to see if it has a recently cached route for that destination. If not, it broadcasts a route request packet to its neighbors for the target node. Its neighbors propagate the request, but only once per query (to avoid saturating the network unnecessarily); when they forward the request packet, they append their node identification to the packet. Thus, in the process of being propagated, each copy of the request packet accumulates the path it took to get to the node where it is stored at any particular moment. Once a copy arrives at the target node, it contains a complete and verified, working path from source to target. The target then labels the packet as a route reply packet and attempts to return it to the source, either by specifying an already-known route from target back to source and forwarding it to the first intermediate node, by assuming each link is bidirectional and reversing the route, or by performing a route discovery flood for the reverse route using a special packet that also contains a copy of the route reply. Routes can be invalidated by a cache timeout procedure. Alternatively, the kth node may promiscuously listen for the k+1st node in the chain to forward the packet on to the k+2th node, which passively acknowledges that the k+1st node has received the packet; if no such event is heard, then node k+1 is presumed to be unreachable. There are several optimizations which include intermediate nodes being able to answer a request directly from their caches using route concatenation, and nodes listening promiscuously for shortcuts (eliminating intermediate nodes when two nodes can hear each other). Once a route is found, it is prefixed to each data packet and each node along the path uses this information to forward the data packet appropriately. Loops cannot form because once a node has forwarded a particular route request once (and appended itself to the encapsulated route), it remembers that request and will not forward it again (thus it cannot add itself twice to the route). AODV combines the on-demand-only nature of DSR (i.e. routes are only found when they are needed, avoiding unneeded maintenance overhead) with the local-view-only nature of DSDV (i.e. each node needs only to maintain information about its neighbors, not a complete route or any other such global information about the network). When a route is needed in AODV, a route request packet is flooded across the network, as in DSR. However, the packet contains information (a sequence number) about the last known route to the destination, so that caching can be exploited (i.e. an intermediate node can respond immediately to advertise a route it already knows) without the source receiving out-of-date information it already has. Also unlike DSR, the packet is not annotated with a list of nodes it has travelled through (global information), but only by a incremented hop count; each node that forwards the request remembers the node from which it received the request, establishing local knowledge about the route in each node along the path. Thus, if the request succeeds, each node knows how to return the reply by unicast (by sending it to the node from which it received the route request broadcast and assuming two-way links). Requests can succeed when they arrive at the destination, or when they arrive at a node that has a newer route to the destination than the source does, in its cache (and can thus advertise that route without further investigation). When either of these events occurs, the node that has fulfilled the request stops propagating its copy and unicasts a reply via the reverse route. As the reply is forwarded, each node along the path stores the identity of the previous sender, establishing the next hop from that recipient in the forward route. Each node takes two steps to mitigate excessive packets: first, it only forwards a particular request once; and second, it only returns a reply if it is the first reply known to it, if it has a greater sequence number than previous replies to the same request known to it, or if it has the same sequence number as but a shorter number of hops than the other routes it has seen. Viable routes are used as soon as they are found, and better routes supplant them if they are discovered later. Another overhead-reducing optimization is the fact that request packets establish a route back to the source, thus finding a second route at the same time, for "free," that not only can be used to return the route reply packet, but also to send data packets. Each node also takes steps to maintain the on-demand properties of the algorithm. Specifically, nodes that are part of a route keep track of what neighbors are actively using the route; they notify only those nodes that have used a route recently if they become aware of a change in the route. For instance, when a link fails, they immediately create an unsolicited route reply with a higher sequence number and an infinite hop count, but only send this to active upstream neighbors; nodes not known to be interested in the route are not kept appraised of changes. Loops in AODV are avoided in exactly the same way by which they are avoided in DSDV: serial number and hop count ordering make it impossible for a node to prefer a route that already includes itself. From egs@cs.cornell.edu Tue Sep 2 11:34:00 2003 Return-Path: Received: from exchfe2.cs.cornell.edu (exchfe2.cs.cornell.edu [128.84.97.28]) by sundial.cs.cornell.edu (8.11.7/8.11.7/M-3.12a) with ESMTP id h82FXxj26940 for ; Tue, 2 Sep 2003 11:34:00 -0400 (EDT) Received: from EXCHVS1.cs.cornell.edu ([128.84.97.23]) by exchfe2.cs.cornell.edu with Microsoft SMTPSVC(5.0.2195.6713); Tue, 2 Sep 2003 11:33:42 -0400 X-MimeOLE: Produced By Microsoft Exchange V6.0.6375.0 content-class: urn:content-classes:message MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" Subject: 615 PAPER 1 Date: Tue, 2 Sep 2003 11:33:42 -0400 Message-ID: <40E631F174C41E4DBE52727E137AF9279061F9@EXCHVS1.cs.cornell.edu> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: 615 PAPER 1 Thread-Index: AcNxZ5cS1RQrcD21SNiOhJ87MIDFGQ== From: "Vidya Venkataraman" To: X-OriginalArrivalTime: 02 Sep 2003 15:33:42.0817 (UTC) FILETIME=[9729B910:01C37167] Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from base64 to 8bit by sundial.cs.cornell.edu id h82FXxj26940 Dynamic Source Routing (DSR) Operation: The paper describes a purely on-demand routing protocol for ad hoc wireless networks called the Dynamic Source Routing protocol. The protocol does not employ periodic updates for the nodes to keep track of routes, hence it saves on bandwidth and power. Route discovery process is initiated by the sender host when it needs to send packets to another host. Accordingly the sender initiating a route broadcasts a Route Request packet which may be received by nodes that are within the transmission range of the former. The Route Request packets contain apart from the addresses of the sender and the destination, a route record in which the sequence of hops traversed by the Route Request packet is stored. A node that receives the Route Request packet drops it if the node had previously received a Route Request with the same source address and request ID or if the node's address is already listed in the route record. Thus the route record is helpful in avoiding looping. After this check, the node sees whether it is the target node of the route request packet. If it is, then it sends the route obtained by the Route Request packet back to the sender node via a Route Reply packet. If the node is not the destination node, it appends its own address to the route record and rebroadcasts the packet. The Route Reply is sent through the same route as the Route Request packet had traversed if the network contains bidirectional links. Otherwise the Route Reply is piggybacked on to a Route Request packet (targeted to the source node) and broadcast by the destination node (this method has been adopted by the authors). Once the source node receives the Route Reply, it starts sending data via the route found. Nodes maintain a route cache to keep track of active routes. The cache is helpful in enhancing the performance of the protocol. If there is a link failure along an established route, the host that detects it propagates a Route Error packet back to the source node (of the route). The intermediate nodes (in the path) and the source node delete their cache entries and the source node reinitiates route discovery (if needed). The authors also assume that the network works in a promiscous mode. This means that the network layer of a node can view packets not addressed to them, without filtering at the lower layer. This mode is helpful in maintaining more route entries in the route cache and detecting shorter routes on the fly (the second optimization has however not been implemented by the authors). The authors have suggested some more methods in optimizing the performance of the protocol. Comments: The protocol works well in a small network and saves useful bandwidth and power by avoiding periodic exchanges. But it has nothing new to offer except that it has been implemented on a wireless medium and some optimization schemes have been employed. The simulations are not extensive. The protocol is tested only with varying mobility. The protocol could have been tested with varying network load. The protocol will suffer from huge route discovery delays if the network is large. The results also do not say anything about the performance of the protocol with respect to the number of calls dropped and the average end-to-end delays incurred. There is one optimization called "the expanding ring" suggested by the authors which has not been implemented. This method will increase the protocol overhead. The scheme could have rather not been mentioned by the authors! And there are some optimization methods which have not been implemented and just suggested. I hope they have been tested in subsequent works of the authors. Many of the optimizations assume the existence of promiscous mode. This is a threat to the security of the systems and of the data being sent. DSDV This paper presents a distance vector method for ad hoc routing. This paper has implemented an approach which is a very common routing method in wired networks. In this regard, the paper cannot boast of a novel approach. Operation: According to the protocol, routing is effected by the maintenance of routing tables (vectors) at each node. Each table entry denotes the preferred next hop node to each of the nodes in the network along with a metric (hop count in this case) that denotes the (expected) cost of the route. These tables are maintained through periodic advertisements (or through trigerred updates) by each nodes to its neighbours of its recent changes in the routing table (incremental) or of the entire table (full dump). Loops are avoided by using sequence numbers in each of the entries. Loops are potentially formed when there is a change in the next hop. A routing table entry is updated by a node only if it receives an entry for the same destination node that has a sequence number greater than the current sequence number or, if the received entry has a lower metric than that present in the current entry and the same sequence number as the current entry. Looping is avoided in the first case because of the fact that the node can propagate sequence numbers to its neighbours only after receiving it from the current next hop. Thus, the sequence number in the node's route entry is always less than or equal to the next hop's route entry. Looping is avoided in the second case too since in the presence of static or decreasing link weights, distance vector algorithms always maintain loop-free paths. All sequence numbers are generated by the destination node except when there is a link breakage (an infinity metric is advertised to the neighbouring nodes by those which have detected the link failure). Whenever a node wishes to send data to another node, it simply refers to the routing entry corresponding to the latter and sends the data to the preferred next hop. The paper has an illustration of the working of the protocol. The paper also suggests methods to counter routing fluctuations during high mobility and in large networks. Accordingly two routing tables are maintained. Newly altered routes are not advertised immediately until it is likely that they are stable. This is done through calculation of an average settling time. Comments: The protocol, as said before, has the overhead of maintaining the routing information of the entire network through periodic broadcasts leading to a wastage of bandwidth and power. Each node may not have the necessity to maintain the routing information of all the nodes in the network. Sometimes a node may not be involved in any data exchange at all but still is burdened to maintain its routing table. The paper does not present any simulation work and hence the effectiveness of the network cannot be determined. The paper suggests a mechanism for effecting convergence which is not optimal. This approach has not been clearly presented. AODV AODV is an on-demand routing protocol that also necessitates nodes to maintain active route information. But unlinke DSDV, the protocol does not require elaborate periodic advertisements. Instead nodes dynamically maintain route information. Local connectivity is however maintained through the exchange of Hello messages between neighbours. Hence we see that AODV is a blend of the distance vector and on-demand routing concepts. Operation: Path discovery is initiated by the source node when it needs to send data to another node. A RREQ packet is broadcast by the sender node. The RREQ packet contains two sequence numbers viz., the source sequence number and the destination sequence numbers. While the former is used to maintain the level of freshness of the reverse route to the source, the latter specifies how fresh a route to the destination should be before it can be accepted by the source. When RREQ propagates through intermediate nodes, the reverse path is set up (similar to the route record in DSR) and each node keeps track of it. A RREQ is rebroadcast by an intermediate node only if it has not received a similar RREQ (detected by the pair) before and the destination sequence number in the RREQ is greater than that of the route entry maintained by that node. If the destination sequence number of the RREQ is less than or equal to that of the route entry, then the destination node unicasts a RREP back through the reverse route (assuming the existence of bidirectional links). If the RREQ reaches the destination, it sends back a RREP to the source node through the reverse path. As the RREP propagates back, each node sets up a forward pointer to the next hop. The RREP can be used by each node in the path to update its routing information. The first RREP that a node receives for a particular source node is always propagated. If it receives further RREPs, it updates its routing information and propagates the RREP only if it contains a greater destination sequence number than the previous RREP or the same destination sequence number with a smaller hop count. It drops all other RREPs it receives. The source node starts data transmission as soon as it receives the first RREP and can later update its routing information if it subsequently receives RREPs with better routes. Each route table entry consists of the destination node, the next hop, the metric, destination sequence number and active neighbours of this route. Thus the route table contains only active routes (decided by a timeout for each entry). The destination sequence number (similar to the one used with DSDV) is useful in preventing routing loops even in extreme conditions. In fact a proof has been presented in the paper that is much similar to the one discussed above in DSDV. When there is a link failure, the node that detects it will send an unsolicited RREP back through the reverse route for the nodes in the route to update their routing information and for the source node to reinitiate path discovery (if necessary). The source node increments the destination sequence number (and then initiates the path discovery) so as to build a new viable route. Local connectivity information is maintained through periodic exchange of Hello messages between neighbours. These Hello messages are helpful in detecting link failures and in determining whether the links are bidirectional. Comments: The protocol as mentioned before is a hybrid between distance vector and on-demand routing protocols. The simulation results presented here are more elaborate than those presented in the previous two papers. They test the quickness and the accuracy of the routing protocol. But the reasons for choosing certain values for traffic parameters have not been mentioned. However the simulations do determine (near) optimal values for two timeouts used in the protocol. Since AODV has been proposed after the DSR and the DSDV protocols, it would have been wise to compare it with the two protocols. The simulations show that as the network size increases, the session drop rate increases drastically (about 4% with 100 nodes to about 33% for 100 nodes!) questioning the scalability of the protocol with respect to network size. According to the paper, an intermediate node always propagates the first RREP for a given source node towards that source. The node could have seen a better route between its sending of the RREQ packet (for the RREP that it had just received) and its receiving of the RREP packet. This point has either been overlooked or has not been mentioned in the paper. From vk66@cornell.edu Tue Sep 2 12:27:11 2003 Return-Path: Received: from postoffice9.mail.cornell.edu (postoffice9.mail.cornell.edu [132.236.56.39]) by sundial.cs.cornell.edu (8.11.7/8.11.7/M-3.12a) with ESMTP id h82GRAj11715 for ; Tue, 2 Sep 2003 12:27:10 -0400 (EDT) Received: from uportal0 (uportal0.cit.cornell.edu [132.236.229.130]) by postoffice9.mail.cornell.edu (8.12.9/8.12.6) with ESMTP id h82GR9qh012938 for ; Tue, 2 Sep 2003 12:27:10 -0400 (EDT) Date: Tue, 2 Sep 2003 12:27:09 -0400 (EDT) Message-ID: <7435386.1062520027911.JavaMail.webber@uportal0> From: Vijay Kumar To: egs+615@cs.cornell.edu Subject: 615 PAPER 1 Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit X-Mailer: uPortal WEB email client 2.10 DSDV --------------- The Destination Sequenced Distace-Vector (DSDV) uses the distance-vector routing(classic Bellman-Ford) to maintain connectivity information. DSDV improves on the class Bellman-Ford routing algorithm by eliminating loops. Every node is required to maintain route table entry for every destination, which consists of a sequence number, destination address, next hop(mobilie station) and number of hops to that destination(metric). Consistency of the route table is maintained by frequent broadcast and freshness of sequence numbers. Mobile stations are required to advertise to the network any signicant changes in their neighborhood. Fluctuations in the network are reduced by allowing for a settling time before route changes are announced, unless the change is as significant as the removal of a node. A node updates its route table entry only under the following circumstances o) The new entry has a newer sequence number. o) The new entry has a better metric and the sequence numbers are same. This ensures that the network is loop free and network bandwidth is conserved. pros:- o) New mobile stations are immediately discovered. cons:- o) The DSDV algorithm is not well suited for large network(large number of mobile stations) with frequent movement of mobile stations. The space required to maintain the route table entry is O(n^2) as each node has to maintain all possible routes to a destination and only choose the minimum in that set for routing. Also frequent movement means frequent updates and consumption of valuable bandwidth. This also means higher power consumption both of which are at premium in a mobile network. DSR --------------- The Dynamic Source Routing(DSR) improves on the DSDV by discovering routes to destination only on demand. This reduces the memory and bandwidth requirement which are at premium in a mobile station. Whenever a mobile station wants to communicate with another one it initiates a Route Discovery by sending a route request packet. Every route request packet contains . Each mobile station forwards the packet to the next neighbor if the packet was not meant for itself and adds itself to the route record of the packet. This also constructs the reverse path to the source. The DSR applies several optimizations to the basic algorithm o) Route cache and learning:- Mobile stations can learn about paths to the intermediate participating nodes while the packet completes the cirutous path from host to destination and back. Cached routes can reduce the time of route discovery. o) Promiscusous learning:- - Other mobile hosts not directly participating in the route discovery can also learn about the path since the medium of transmission is broadcast. - Promiscous listening can also help nodes discover shorter routes whenever they appear in the network. - Route errors discovered by one node can help other nodes remove unreacheable nodes from their cache entries. Loops are avoided by avoiding retransmits of route discovery packets if the id of the node is already present in route discvoery path contained in the packet. Pros:- o) Routes are discovered dynamically which saves network bandwidth, power, memory. o) Promiscuous mode helps reduce route discoveries. Cons:- o) New mobile stations are not immediately discovered. This can though be overcome by sending a Route discovery to a mobile host that is known not to exist. o) May not work well if the route paths are long as the route discovery packet has to accomodate all the nodes participating in the route discovery. AODV ---------------- Ad-hoc On-Demand Distance Vector Routing ( AODV ) combines the DSDV and DSR to obtain better bandwidht usage, local connectivity and memory usage of mobile network. AODV uses dynamic route discovery just like in DSR, although local connectivity information is readily available since nodes are required to send hello messages to one another. Whenever a node launches a route discvoery to an unknown host using Route Request packets( RREQ) the intermediate hosts retransmit a Route Reply Packet(RREP) back to the source. This helps setup forward and return paths dynamically. Also the packet sizes are significantly less when compared to DSR as the packets need not store the entire path in its header. The route tables store source sequence numbers, destinations sequence numbers and a route expiration timer. The expiration timer helps purge reverse paths whenever the nodes do not lie on the path from source to destination. The sequence numbers help maintain a loop free path. Pros:- o) Uses the least resources of the 3 algorithms - reduced packet size - reduced memory and network activity using 'route request expiration timer' o) local connectivity information readily available and link breakages can be immediately broadcast to interested nodes. Cons:- o) Assumes symmetric links From vk66@cornell.edu Tue Sep 2 12:30:08 2003 Return-Path: Received: from postoffice8.mail.cornell.edu (postoffice8.mail.cornell.edu [132.236.56.38]) by sundial.cs.cornell.edu (8.11.7/8.11.7/M-3.12a) with ESMTP id h82GU7j12099 for ; Tue, 2 Sep 2003 12:30:08 -0400 (EDT) Received: from uportal0 (uportal0.cit.cornell.edu [132.236.229.130]) by postoffice8.mail.cornell.edu (8.12.9/8.12.6) with ESMTP id h82GU7Xm025839 for ; Tue, 2 Sep 2003 12:30:07 -0400 (EDT) Date: Tue, 2 Sep 2003 12:30:07 -0400 (EDT) Message-ID: <12437310.1062520205426.JavaMail.webber@uportal0> From: Vijay Kumar To: egs@cs.cornell.edu Subject: 615 PAPER 1 Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit X-Mailer: uPortal WEB email client 2.10 DSDV --------------- The Destination Sequenced Distace-Vector (DSDV) uses the distance-vector routing(classic Bellman-Ford) to maintain connectivity information. DSDV improves on the class Bellman-Ford routing algorithm by eliminating loops. Every node is required to maintain route table entry for every destination, which consists of a sequence number, destination address, next hop(mobilie station) and number of hops to that destination(metric). Consistency of the route table is maintained by frequent broadcast and freshness of sequence numbers. Mobile stations are required to advertise to the network any signicant changes in their neighborhood. Fluctuations in the network are reduced by allowing for a settling time before route changes are announced, unless the change is as significant as the removal of a node. A node updates its route table entry only under the following circumstances o) The new entry has a newer sequence number. o) The new entry has a better metric and the sequence numbers are same. This ensures that the network is loop free and network bandwidth is conserved. pros:- o) New mobile stations are immediately discovered. cons:- o) The DSDV algorithm is not well suited for large network(large number of mobile stations) with frequent movement of mobile stations. The space required to maintain the route table entry is O(n^2) as each node has to maintain all possible routes to a destination and only choose the minimum in that set for routing. Also frequent movement means frequent updates and consumption of valuable bandwidth. This also means higher power consumption both of which are at premium in a mobile network. DSR --------------- The Dynamic Source Routing(DSR) improves on the DSDV by discovering routes to destination only on demand. This reduces the memory and bandwidth requirement which are at premium in a mobile station. Whenever a mobile station wants to communicate with another one it initiates a Route Discovery by sending a route request packet. Every route request packet contains . Each mobile station forwards the packet to the next neighbor if the packet was not meant for itself and adds itself to the route record of the packet. This also constructs the reverse path to the source. The DSR applies several optimizations to the basic algorithm o) Route cache and learning:- Mobile stations can learn about paths to the intermediate participating nodes while the packet completes the cirutous path from host to destination and back. Cached routes can reduce the time of route discovery. o) Promiscusous learning:- - Other mobile hosts not directly participating in the route discovery can also learn about the path since the medium of transmission is broadcast. - Promiscous listening can also help nodes discover shorter routes whenever they appear in the network. - Route errors discovered by one node can help other nodes remove unreacheable nodes from their cache entries. Loops are avoided by avoiding retransmits of route discovery packets if the id of the node is already present in route discvoery path contained in the packet. Pros:- o) Routes are discovered dynamically which saves network bandwidth, power, memory. o) Promiscuous mode helps reduce route discoveries. Cons:- o) New mobile stations are not immediately discovered. This can though be overcome by sending a Route discovery to a mobile host that is known not to exist. o) May not work well if the route paths are long as the route discovery packet has to accomodate all the nodes participating in the route discovery. AODV ---------------- Ad-hoc On-Demand Distance Vector Routing ( AODV ) combines the DSDV and DSR to obtain better bandwidht usage, local connectivity and memory usage of mobile network. AODV uses dynamic route discovery just like in DSR, although local connectivity information is readily available since nodes are required to send hello messages to one another. Whenever a node launches a route discvoery to an unknown host using Route Request packets( RREQ) the intermediate hosts retransmit a Route Reply Packet(RREP) back to the source. This helps setup forward and return paths dynamically. Also the packet sizes are significantly less when compared to DSR as the packets need not store the entire path in its header. The route tables store source sequence numbers, destinations sequence numbers and a route expiration timer. The expiration timer helps purge reverse paths whenever the nodes do not lie on the path from source to destination. The sequence numbers help maintain a loop free path. Pros:- o) Uses the least resources of the 3 algorithms - reduced packet size - reduced memory and network activity using 'route request expiration timer' o) local connectivity information readily available and link breakages can be immediately broadcast to interested nodes. Cons:- o) Assumes symmetric links From nsg7@cornell.edu Sun Mar 12 13:14:48 2006 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.0 (2005-09-13) on sundial.cs.cornell.edu X-Spam-Status: No, score=-1.3 required=5.0 tests=AWL,BAYES_00 autolearn=ham version=3.1.0 X-Spam-Level: Received: from authusersmtp.mail.cornell.edu (granite1.mail.cornell.edu [128.253.83.141]) by sundial.cs.cornell.edu (8.11.7-20031020/8.11.7/M-3.22) with ESMTP id k2CIEmt04607 for ; Sun, 12 Mar 2006 13:14:48 -0500 (EST) Received: from [127.0.0.1] (cpe-24-59-77-191.twcny.res.rr.com [24.59.77.191]) (authenticated bits=0) by authusersmtp.mail.cornell.edu (8.13.1/8.12.10) with ESMTP id k2CIEjW0001722 for ; Sun, 12 Mar 2006 13:14:48 -0500 (EST) Message-ID: <44146584.2000907@cornell.edu> Date: Sun, 12 Mar 2006 13:16:36 -0500 From: Nick Gerner User-Agent: Mozilla Thunderbird 1.0.6 (Windows/20050716) X-Accept-Language: en-us, en MIME-Version: 1.0 To: egs@cs.cornell.edu Subject: CS615 paper 1 Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Professor Sirer, For paper 1 I'm going to research distributed application deployment, specifically single image OSes or single image abstraction approaches. I'm using the following papers as my "seed set": Liu, H., et al. "Design and Implementation of a Single Image Operating System for Ad Hoc Networks" Mobisys 2005 Lo, V., et al. "Cluster Computing on the Fly..." IPTPS 2004 Tilevich, E. and Y. Smaragdakis, "J-Orchestra: Automatic Java Application Partitioning", ECOOP 2002 Also, I have two other papers due next week and a midterm. One of the papers is for VLDB and the other is involved with other students so I can't get extensions for those or the midterm. I was wondering if I could have until Saturday at the end of spring break to finish the paper for CS615 (5-25). Thanks. --Nick