From mtp22@cornell.edu Mon Sep 2 13:00:36 2002 Received: from postoffice2.mail.cornell.edu (postoffice2.mail.cornell.edu [132.236.56.10]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g82H0Zh19251 for ; Mon, 2 Sep 2002 13:00:35 -0400 (EDT) Received: from narnia (syr-24-58-57-15.twcny.rr.com [24.58.57.15]) by postoffice2.mail.cornell.edu (8.9.3/8.9.3) with SMTP id NAA08078 for ; Mon, 2 Sep 2002 13:00:35 -0400 (EDT) Content-Type: text/plain; charset="iso-8859-1" From: Matt Piotrowski Reply-To: mtp22@cornell.edu To: egs@CS.Cornell.EDU Subject: 615 PAPER 1 Date: Mon, 2 Sep 2002 13:01:32 -0400 X-Mailer: KMail [version 1.2] MIME-Version: 1.0 Message-Id: <02090213013201.00149@narnia> Content-Transfer-Encoding: 8bit The major contribution of this paper is a comprehensive overview of the DARPA PRNET, which appears to be one of the first self-organizing mobile networks. The paper gives an overview of how this network initializes, how it determines routing information, how it actually routes a packet, and how it shares the medium among the packet radios. One of the weaknesses of this paper is the lack of mobility analysis. By this I mean an analysis of how quickly the network adapts to a change of position of one or more nodes. The paper talks about one case where a packet radio is not responding and must be routed around, but does not look at any cases where packet radios change positions. Another weakness is the lack of a description of the processing power and memory requirements of the packet radios. It appears that a fair amount of smarts are inside the network, i.e. inside the packet radios, but there is little to no discussion of the processing power, memory requirements, or power consumption of the packet radios. One way to expand upon the work described in this paper is to attempt to scale the network to large numbers of packet radios. The paper describes how the PRNET is limited to less than 150 packet radios. This may be fine for many practical applications, but there are practical applications where a larger number of packet radios is necessary. Another way to expand upon the work is to analyze the difficulty in jamming the network. Military applications, among others, make this an important consideration. From shafat@CS.Cornell.EDU Mon Sep 2 20:15:42 2002 Received: from exchange.cs.cornell.edu (exchange.cs.cornell.edu [128.84.97.8]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g830Fgh15021 for ; Mon, 2 Sep 2002 20:15:42 -0400 (EDT) content-class: urn:content-classes:message Subject: 615 PAPER 1 MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" X-MimeOLE: Produced By Microsoft Exchange V6.0.5762.3 Date: Mon, 2 Sep 2002 20:15:41 -0400 Message-ID: <47BCBC2A65D1D5478176F5615EA7976D134F7A@opus.cs.cornell.edu> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: 615 PAPER 1 Thread-Index: AcJS3woK+q64uMeaQsC2ysEaWcb7Hw== From: "Syed Shafat Zaman" To: "Emin Gun Sirer" Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from base64 to 8bit by sundial.cs.cornell.edu id g830Fgh15021 The Jubin and Tornow paper focuses explicitly on the state of the DARPA PRNET system around the mid 80's, and discusses various protocols that were successfully used to make It work. Well, being no expert in wireless network research, I can only guess that this paper had quite an impact on concurrent research and guided it in a positive direction. It also undoubtedly encouraged the use of packet radios in a wide range of military and commercial applications, although the applications the authors decide to illustrate the PRNET system's usefulness with, do not do justice to the vast potential it holds. Despite the assurance from the authors that the system is functional, the lack of experimental data in the paper somewhat diminishes the strength of their argument. More numerical or graphical representations concerning, for example, actual performance, reliability of one of their network systems in varying conditions could be more useful. They also fail to sufficiently explain why the various algorithms used in the system were preferred in the first place. The paper could perhaps address this issue briefly before moving on to explaining how a particular protocol/algorithm was effective in the system. In terms of the actual system itself, having a neighbor table in addition to maintaining a tier table at each node seems redundant. The tier table could easily accommodate the extra information from the neighbor table - link qualities of nodes that are one hop away (or neighbors). This information, when passed along to all the other nodes in the network via PROPs, would give each node a much better picture of the network topology and, as a result, packets could be routed in a more efficient manner. Another issue that the system does not address properly is the acknowledgement of the delivery of a packet to the final destination. Since ACKs are only sent to the last node the packet arrives from, the source PR cannot be 100% certain of the packet's safe delivery to the destination PR (unless of course they are neighbors). So reliability is a major concern here and can be improved upon. Future research may also try to accommodate more than just sixteen neighbors in the "actual" neighborhood of a PR. Although the "logical" neighborhood algorithm is claimed to work well, allowing a larger group of "actual" neighbors could boost performance and serve a broader range of applications. It would also be interesting to incorporate some sort of security protocols to ensure secure transmissions between two PRs. Another suggestion for further research opportunity would be the use full-duplex PRs and observe how they affect the performance of the network. This, however, would necessitate major amendments to the algorithms and protocols used for half-duplex PRs. From mvp9@cornell.edu Mon Sep 2 20:21:31 2002 Received: from travelers.mail.cornell.edu (travelers.mail.cornell.edu [132.236.56.13]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g830LVh16075 for ; Mon, 2 Sep 2002 20:21:31 -0400 (EDT) Received: from travelers.mail.cornell.edu (travelers.mail.cornell.edu [132.236.56.13]) by travelers.mail.cornell.edu (8.9.3/8.9.3) with SMTP id UAA19212 for ; Mon, 2 Sep 2002 20:21:28 -0400 (EDT) Date: Mon, 2 Sep 2002 20:21:28 -0400 (EDT) From: mvp9@cornell.edu X-Sender: mvp9@travelers.mail.cornell.edu To: egs@CS.Cornell.EDU Subject: 615 PAPER 1 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII This paper gives a fairly detailed overview of the DARPA Packet Radio Network, a small scale system of nodes communicating over radio, whose primary advantages seem to be automatic start up, and dynamic routing, and the ease of adding/deleting nodes. The paper thoroughly examines the PRNet from transport down the physical layers of the protocol stack, describing its functionality and features. There are several noteworthy weaknesses in this paper. One is the lack of analysis of performance of the protocol. In the 10 years of use, a great body of performance data has surely been gathered, and its inclusion would greatly strengthen the evaluation of the protocol as a whole and of the chosen values of variables scattered throughout the protocol hierarchy, such as the # of retransmission before requesting alternate routing. In a similar vein, a good addition would be a comparison to similar protocols. Scalability analysis is also a noticeable omission. The limitations of the protocol that are stated are not discussed. The overall limit of 138 entities is not explained and more importantly the conclusion creates the impression that networks of over 50 nodes may not perform well. A good way to broaden the work in question would be to carry out an analysis (or case study) of network performance as number of nodes approaches the stated limit. An even more useful step would be to explore whether the protocol could be scaled to larger networks. Finally, the paper would likely be improved by addressing quite a few smaller questions: how are logical neighborhoods determined from actual ones in an efficient manner? How are default values currently chosen? Are different fairness queuing methods more amenable for different situations? How are FEC levels chosen? What is the cost and internal structure of the actual radios? From xz56@cornell.edu Mon Sep 2 23:04:09 2002 Received: from postoffice2.mail.cornell.edu (postoffice2.mail.cornell.edu [132.236.56.10]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g83349h17331 for ; Mon, 2 Sep 2002 23:04:09 -0400 (EDT) Received: from XIN (dhcp-128-84-87-159.ece.cornell.edu [128.84.87.159]) by postoffice2.mail.cornell.edu (8.9.3/8.9.3) with SMTP id XAA06252 for ; Mon, 2 Sep 2002 23:04:08 -0400 (EDT) Message-ID: <00ec01c252f6$9082aa30$9f575480@XIN> From: "Xin Zhang" To: Subject: 615 PAPER 1 Date: Mon, 2 Sep 2002 23:04:05 -0400 MIME-Version: 1.0 Content-Type: text/plain; charset="Windows-1252" Content-Transfer-Encoding: 7bit X-Priority: 3 X-MSMail-Priority: Normal X-Mailer: Microsoft Outlook Express 6.00.2600.0000 X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2600.0000 Dear Prof. Sirer, I missed the first class but wish to take this course. I am not sure about the requirement of this course either, so just follow the instructions from the website for this first time. Following is the summary for paper 1. Thank you. Xin ------Summary------ The paper described the implementation of DARPA packet radio network. Firstly, it introduced the features of (multi-hop) packet radio networks: broadcast (highly-mobile and easily deployed and reconfigured, but half-duplex and vulnerable to interference at the receivers), composed of PRNET subnet (PRs) and collection of devices (PRs for transmitting and receiving; devices - hosts/terminals running internet protocols for controls). Because of the mobile and multi-hop nature of the PRNET, a proactive routing is used which has lower delay compared with reactive and lower channel usage compared with simple flooding. The algorithm involves the maintaining of three tables for the choosing of the route, setting the headers and forwarding the packets. Also, CSMA is used to avoid collisions. Pacing protocol and "Fairness queuing" deal with retransmission, making it proper (both conservative against possible congestion and efficient) and fair for different sources. For reliable communication, FEC and ARQ (involved active/passive acknowledgement and CRC). The new ideas (to me) are active/passive acknowledgement, usage of alternative routing flag and pacing. The problems are: 1). the PENET is not completely mobile. There is still wire-connected devices needed, which is a major difference from the current studied Ad Hoc networks. 2). Using CSMA as the MAC layer protocol is not proper for wireless networks. Instead, those with RTC-CTC dialog are better. 3). For the routing, it's very similar as that in ARPANET, belonging to the type of distance vector, I think. I am expecting to learn more on this aspect in this course later. ------End------ From hs247@cornell.edu Mon Sep 2 23:23:42 2002 Received: from mailout5-0.nyroc.rr.com (mailout5-1.nyroc.rr.com [24.92.226.169]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g833Ngh21195 for ; Mon, 2 Sep 2002 23:23:42 -0400 (EDT) Received: from hubby.cornell.edu (syr-24-58-42-130.twcny.rr.com [24.58.42.130]) by mailout5-0.nyroc.rr.com (8.11.6/RoadRunner 1.20) with ESMTP id g833NcW01122 for ; Mon, 2 Sep 2002 23:23:38 -0400 (EDT) Message-Id: <5.1.0.14.2.20020902232148.00b62b30@postoffice2.mail.cornell.edu> X-Sender: hs247@postoffice2.mail.cornell.edu (Unverified) X-Mailer: QUALCOMM Windows Eudora Version 5.1 Date: Mon, 02 Sep 2002 23:24:00 -0400 To: egs@CS.Cornell.EDU From: Hubert Sun Subject: 615 PAPER 1 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed This paper is unique that it does not contribute anything new, but it describes in detail the state of the DARPA Packet Radio Network in 1987. The authors describe several algorithms used in the network such as network topology discovery at initialization, how packets are forwarded at runtime, how to optimally queue packets and how to prevent looping of packets. The reader of this paper really gets a good idea of what the issues are in building a distributed, mobile and ad-hoc network are. And from reading this paper, one gets a good flavour of practically how to attack issues such as routing, connection reliability and error checking in a system that is used by the army. Though many algorithms are discussed in the paper, there is lack experimental support to back up the ideas. For example, the 'fairness queuing' algorithm is suppose to prevent a device with an excellent connection to hog the sending queue of a packet radio. No evidence is in the paper to show that the algorithm actually works in reality. Other algorithms such as the pacing algorithm and carrier sense multiple access are unintuitive and need data to support them. (Perhaps this may be out of scope of the paper. When this paper was written, the DARPA network was well established, therefore probably not needing experimental data to back it up). One other weakness of the paper is that the authors fail to mention the weaknesses of the DARPA network system. They briefly mention the system is limited to 138 nodes, but do not explicitly say why. More discussion on things such as PROP and tier tables and how they affect the scalability of the system would make the paper stronger. Much work can be done to expand on the ideas discussed in this paper. A logical topic would be to discuss how to make the system more scalable. (One major bottle neck could be the limitation of a packet radio in that it is half duplex). Since the system is used in the army, it would be interesting to discuss the system from a security stand point; how to make the network secure from attacks and possible intruding packet radios. The paper also mentions how the Packet Radio Network can be used in the consumer world such as restaurants, and more ideas of how other useful applications can use the network could be nice research. Also experiments on how this network compares to other similar systems would be interesting. From bd39@cornell.edu Tue Sep 3 00:43:35 2002 Received: from postoffice2.mail.cornell.edu (postoffice2.mail.cornell.edu [132.236.56.10]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g834hYh06063 for ; Tue, 3 Sep 2002 00:43:34 -0400 (EDT) Received: from boweilaptop.cornell.edu (r102439.resnet.cornell.edu [128.253.163.42]) by postoffice2.mail.cornell.edu (8.9.3/8.9.3) with ESMTP id AAA12203 for ; Tue, 3 Sep 2002 00:43:35 -0400 (EDT) Message-Id: <5.1.0.14.2.20020902230901.00bc1bf0@postoffice2.mail.cornell.edu> X-Sender: bd39@postoffice2.mail.cornell.edu (Unverified) X-Mailer: QUALCOMM Windows Eudora Version 5.1 Date: Tue, 03 Sep 2002 00:37:43 -0400 To: egs@CS.Cornell.EDU From: Bowei Du Subject: 615 PAPER 1 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed This paper is a description of packet radio protocols at the time it was written. The main contribution of this paper is the highlighting of the idea of a dynamic mobile network, identification of the design issues inherent in such a system and how these issues were addressed in the implemented protocols. The article identifies key aspects of a mobile network: that the network will need to self configure through discovery of its environment and will need to respond to changes in the network. One weakness of this paper is that it is often not clear what motivated the design choices in the protocols. For instance, there are numerous constants (delay between PROP's, number of neighbors to retain in routing tables). The context for these choices is missing. What was the density, mobility, structure of the nodes for which this protocol was designed for? What was their communication pattern? It seems at some points the authors assumed constant rate of traffic from each node, whereas in practice, communication mostly occurs in bursts. In a similar vein, there is a lack of experimental evidence as to the tradeoffs of the protocols implemented. For example, it is clear that for slow moving nodes, the beaconing rate is acceptable. What about a network in which the topology changes much more rapidly than the beaconing rate? One area that could be examined would be whether the pacing function is really necessary in practice, or would a simple strategy involving CSMA result in a good approximation of fair access to the medium. The fair queuing algorithm could be investigated in the same manner, as pacing seems to interfere with "fair" network behavior. To what degree would queuing modifications be needed to ensure "fairness"? This paper was written at a time in which the applications of wireless networks was as of yet unknown. However, it would have improved the paper if it had some grounding as to the behavior of the nodes, which would have given the design choices of the protocols greater strength. From mr228@cornell.edu Tue Sep 3 01:04:32 2002 Received: from cornell.edu (cornell.edu [132.236.56.6]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g8354Wh09288 for ; Tue, 3 Sep 2002 01:04:32 -0400 (EDT) Received: from cornell.edu (syr-24-58-63-179.twcny.rr.com [24.58.63.179]) by cornell.edu (8.9.3/8.9.3) with ESMTP id BAA09651 for ; Tue, 3 Sep 2002 01:04:30 -0400 (EDT) Message-ID: <3D7442F1.3629E486@cornell.edu> Date: Tue, 03 Sep 2002 01:04:49 -0400 From: Mark Robson X-Mailer: Mozilla 4.76 [en]C-CCK-MCD MS4.76 V20001206.2 (Windows NT 5.0; U) X-Accept-Language: en,ja MIME-Version: 1.0 To: egs@CS.Cornell.EDU Subject: 615 PAPER 1 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit This paper introduces PRNET, a packet-based, self-organizing and distributed network of autonomous wireless nodes. The paper provides a high-level overview (and in many areas delves into considerable detail) of the network's protocol suite -- from physical layer up through the network layer. Route discovery and maintenance is done through "Organization Packets" broadcast at regular intervals. Each node is thus able to store optimal routes and quality of service measuremens locally. There is also a discussion of the hardware that is used as well as many of the physical parameters the radio's are configured with, however, I'm not certain enough information is provided for exact experimental replication. The system has several key features that provide the basis for wireless networks that are presently in use. Since there is only one actual channel for use by a neighborhood of nodes, they suggest a CSMA scheme that utilizes random backoffs to help prevent collisions. Their scheme also has the added benefit of eliminating the hidden node problem. Another powerful feature is the device table. Although only breifly mentioned, it abstracts away the "devices" or "services" from the wireless network. Not only does this allow for mobility of attached devices as they suggest, but also allows for easily replication of services and data throughout the network. There are also provisions in the protocols (primarily through "Organization Packets") for automatic node detection, mobility of nodes (physical movement w.r.t. the rest of the network), error detection, and optimal route calculation. The paper leaves several unanswered questions. First, will the system scale? They state that the current protocols allow each PR to support up to 16 neighbors, but there is no mention of why. They go on to discuss how to get around this limitation -- remove the neighbor with whom you have the most neighbors in common. Although the claim is that the algorithm used prevents the partitioning of the graph into cliques, there's no discussion of how. Second, there should be more justification for the heavy burden placed on interior nodes along a route. Each node along a path is responsible to not only ack all incoming packets, but also to store all outgoing packets and retransmit until successfully acked by the recipient. Given the other protocol layers and the hardware in use, does this really produce a performance increase? No concrete empirical results are presented in this paper. Although in many areas very detailed hardware parameters are specified, never do we see a performance analysis or comparison or a discussion regarding the scalability of the system. What is mentioned is that "the current network protocols are designed to support 138 entities..." They never discuss why 138 is the limit. Is this a physical limitation or is there some fundamental assumption regarding their protocols that enforces this limit? Although future research in this area has already occurred, I would suggest that the issue of scaling be investigated -- scaling not just w.r.t. total number of nodes in the network, but also looking at performance in a dense network, that is, as the average size of the "neighborhoods" grows. -- Mark Robson From ag75@cornell.edu Tue Sep 3 01:22:25 2002 Received: from travelers.mail.cornell.edu (travelers.mail.cornell.edu [132.236.56.13]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g835MPh12344 for ; Tue, 3 Sep 2002 01:22:25 -0400 (EDT) Received: from travelers.mail.cornell.edu (travelers.mail.cornell.edu [132.236.56.13]) by travelers.mail.cornell.edu (8.9.3/8.9.3) with SMTP id BAA02136 for ; Tue, 3 Sep 2002 01:22:19 -0400 (EDT) Date: Tue, 3 Sep 2002 01:22:19 -0400 (EDT) From: ag75@cornell.edu X-Sender: ag75@travelers.mail.cornell.edu To: egs@CS.Cornell.EDU Subject: 615 PAPER 1 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII The paper presents a protocol for having a packet radio network. The network would support a limited (138) number of nodes that can change their location, and enter and leave the network at any time. One of the interesting advantages of the protocol is that it uses passive acknowledgment. The fact that the protocol uses separate CRC for headers and data makes this even more efficient. Another advantage is that the protocol allows for automatic network management. The fact that PROPs are constantly broadcasted means that a lot of data is constantly being sent. There is also a lot of information being sent in the headers of data packets. Thus, the network becomes increasingly congested as the number of PRs increases. The fact that pacing is single-threaded seems inefficient. This protocol can be improved by allowing a larger number of nodes to be operational at the same time and by improving upon the weaknesses identified above. From jsy6@postoffice2.mail.cornell.edu Tue Sep 3 03:30:42 2002 Received: from postoffice2.mail.cornell.edu (postoffice2.mail.cornell.edu [132.236.56.10]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g837Ugh03382 for ; Tue, 3 Sep 2002 03:30:42 -0400 (EDT) Received: from JSY23.cornell.edu (syr-24-58-41-193.twcny.rr.com [24.58.41.193]) by postoffice2.mail.cornell.edu (8.9.3/8.9.3) with ESMTP id DAA22085 for ; Tue, 3 Sep 2002 03:30:42 -0400 (EDT) Message-Id: <5.1.0.14.2.20020903032900.00a15ec0@postoffice2.mail.cornell.edu> X-Sender: jsy6@postoffice2.mail.cornell.edu (Unverified) X-Mailer: QUALCOMM Windows Eudora Version 5.1 Date: Tue, 03 Sep 2002 03:30:34 -0400 To: egs@CS.Cornell.EDU From: Janet Suzie Yoon Subject: 615 PAPER1 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.132 $Date: 2001-12-05 20:20:17-08 X-Security: The postmaster has not enabled quarantine of poisoned messages. Content-Type: multipart/alternative; boundary="=====================_63168871==_.ALT" --=====================_63168871==_.ALT Content-Type: text/plain; charset="us-ascii"; format=flowed This paper provides a synopsis of the DARPA packet radio network (PRNET). PRNET is a self-organizing packet radio network whose main benefits are its mobility and its dynamic and automatic routing. After network initialization, the PRNET network manager self-reconfigures based on radio connectivity between packet radios. Despite the mobility of packet radios, sensing the existing connectivity is done in real time. The paper details algorithms used to gather information on network topology used for route calculation, optimally queuing packets, forwarding protocols, alternate routing, and transmission protocols. The paper's main weakness is its lack of performance analysis. For example, there is no comparative analysis on the performance of the forwarding protocols used. It would also be nice to know how PRNET stands in comparison to other communication networks. Including some actual case examples and results instead of just the concepts behind PRNET would improve this paper. There is also a tendency to make claims without evidence. Statements like "the algorithm is careful to prevent isolated cliques" and "Quality values are smoothed and hysteresis is applied when switching between good and bad ratings" are not followed by information on how these claims are accomplished. An expansion of this paper would be to expand the Network Size. The paper lists that the network protocols are designed to support 138 entities in a single network. The current protocol allows each packet radio to support up to 16 neighbors. In some applications of PRNET, it might be useful or even necessary to support more entities in a single network and more neighbors per packet radio. It would be interesting to see how PRNET scales, especially in a highly mobile environment. --=====================_63168871==_.ALT Content-Type: text/html; charset="us-ascii" This paper provides a synopsis of the DARPA packet radio network (PRNET).  PRNET is a self-organizing packet radio network whose main benefits are its mobility and its dynamic and automatic routing.  After network initialization, the PRNET network manager self-reconfigures based on radio connectivity between packet radios.  Despite the mobility of packet radios, sensing the existing connectivity is done in real time.  The paper details algorithms used to gather information on network topology used for route calculation, optimally queuing packets, forwarding protocols, alternate routing, and transmission protocols.      
The paper’s main weakness is its lack of performance analysis.  For example, there is no comparative analysis on the performance of the forwarding protocols used.  It would also be nice to know how PRNET stands in comparison to other communication networks.  Including some actual case examples and results instead of just the concepts behind PRNET would improve this paper.  There is also a tendency to make claims without evidence. Statements like “the algorithm is careful to prevent isolated cliques” and  “Quality values are smoothed and hysteresis is applied when switching between good and bad ratings” are not followed by information on how these claims are accomplished.    
An expansion of this paper would be to expand the Network Size.  The paper lists that the network protocols are designed to support 138 entities in a single network.  The current protocol allows each packet radio to support up to 16 neighbors.  In some applications of PRNET, it might be useful or even necessary to support more entities in a single network and more neighbors per packet radio. It would be interesting to see how PRNET scales, especially in a highly mobile environment. 


--=====================_63168871==_.ALT-- From ht48@cornell.edu Tue Sep 3 07:47:58 2002 Received: from postoffice.mail.cornell.edu (postoffice.mail.cornell.edu [132.236.56.7]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g83Blvh21464 for ; Tue, 3 Sep 2002 07:47:57 -0400 (EDT) Received: from Fira (syr-24-58-35-99.twcny.rr.com [24.58.35.99]) by postoffice.mail.cornell.edu (8.9.3/8.9.3) with SMTP id HAA17998 for ; Tue, 3 Sep 2002 07:47:52 -0400 (EDT) Message-ID: <001001c2533f$607b3ed0$0300a8c0@Fira> From: "Dylan Tong" To: Subject: 615 Paper 1 Date: Tue, 3 Sep 2002 07:45:15 -0400 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.132 $Date: 2001-12-05 20:20:17-08 X-Security: The postmaster has not enabled quarantine of poisoned messages. Content-Type: multipart/alternative; boundary="----=_NextPart_000_000D_01C2531D.D7CD05D0" X-Priority: 3 X-MSMail-Priority: Normal X-Mailer: Microsoft Outlook Express 6.00.2600.0000 X-MIMEOLE: Produced By Microsoft MimeOLE V6.00.2600.0000 This is a multi-part message in MIME format. ------=_NextPart_000_000D_01C2531D.D7CD05D0 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable Dylan Tong ht48 The DARPA Packet Radio Network Protocols =20 This paper describes the design along with some of the implementation = issues, limitations and uses of the DARPA's Packet Radio Network = (PRNET). The PRNET was of interest at the time (1987) because it = featured a mobile self configuring reliable wireless network, adjusting = to the gain or loss of low cost packet radios (PR). =20 The protocol algorithms involved at the transport layer down to the = physical layer were described in detail for the most part. The routing = system of PRNET is dynamic, and involves the pro-active sharing of = tables (neighbor, tier, and device tables) via broadcasting methods. = Acknowledgements are done passively as a result of the broadcast nature = of the protocol. The PRs use the table information available to them to = determine the best route to forward packets down a single path to the = destination. Nevertheless, as described in the paper, the neighborhood = broadcasting approach still has limitations. As discussed, the protocol = at the time was only desgned to support "138 entities," and up to = "sixteen neighbors." The paper describes that PRNET has some scaling = ability in the way that the PRs "employ an algorithm to determine their = "logical" neighborhood," which in effect "limits the actual neighbors = that congest the track." The paper also claims that the algorithm is = "careful to prevent isolated cliques," but unfortunately doesn't explain = how. Despite the algorithm, the paper admits that performance suffer = when "actual" neighborhoods are large. Some quantitative data on PRNET's = scalibility would have been nice here. Obviously scalable protocols for = PRNET would be a next step in the research, and the paper mentions this = briefly. =20 As described in the paper, PRNET also features fairness, congestion and = flow control along with error detection. The physical layer uses CSMA = protocol, which can easily be replaced with better protocols at least in = this day and age. On the other hand, perhaps the half-duplex = characteristic of PR's could be avoided altogether. =20 The paper describes ways that PRNET can complement the Internet, and = also concludes by giving some insight on military as well as some = non-military applications of this technology. Given that the authors are = not writing a textbook here, I thought the paper was quite informative = and succinct. The only other thing that I felt was lacking in addition = to the lack of performance measurements was no mentioning of security = issues or considerations. This is a major issue in networking today, = which was perhaps overlooked at the time, but because PRNET was = developed for military reasons, I'd be surprised if there weren't any = considerations made at all. This is also another area that could = probably have been explored further. ------=_NextPart_000_000D_01C2531D.D7CD05D0 Content-Type: text/html; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable

Dylan Tong

ht48

 

The DARPA Packet Radio = Network=20 Protocols

 

This paper describes the = design=20 along with some of the implementation issues, limitations and uses of = the=20 DARPA=92s Packet Radio Network (PRNET). The PRNET was of interest at the = time=20 (1987) because it featured a mobile self configuring reliable wireless = network,=20 adjusting to the gain or loss of low cost packet radios=20 (PR).

 

The protocol algorithms = involved at=20 the transport layer down to the physical layer were described in detail = for the=20 most part. The routing system of PRNET is dynamic, and involves the = pro-active=20 sharing of tables (neighbor, tier, and device tables) via broadcasting = methods.=20 Acknowledgements are done passively as a result of the broadcast nature = of the=20 protocol. The PRs use the table information available to them to = determine the=20 best route to forward packets down a single path to the destination.=20 Nevertheless, as described in the paper, the neighborhood broadcasting = approach=20 still has limitations. As discussed, the protocol at the time was only = desgned=20 to support =93138 entities,=94 and up to =93sixteen neighbors.=94 The = paper describes=20 that PRNET has some scaling ability in the way that the PRs =93employ an = algorithm=20 to determine their =93logical=94 neighborhood,=94 which in effect = =93limits the actual=20 neighbors that congest the track.=94 The paper also claims that the = algorithm is=20 =93careful to prevent isolated cliques,=94 but unfortunately doesn=92t = explain how.=20 Despite the algorithm, the paper admits that performance suffer when = =93actual=94=20 neighborhoods are large. Some quantitative data on PRNET=92s scalibility = would=20 have been nice here. Obviously scalable protocols for PRNET would be a = next step=20 in the research, and the paper mentions this = briefly.

 

As described in the paper, = PRNET=20 also features fairness, congestion and flow control along with error = detection.=20 The physical layer uses CSMA protocol, which can easily be replaced with = better=20 protocols at least in this day and age. On the other hand, perhaps the=20 half-duplex characteristic of PR=92s could be avoided=20 altogether.

 

The paper describes ways = that PRNET=20 can complement the Internet, and also concludes by giving some insight = on=20 military as well as some non-military applications of this technology. = Given=20 that the authors are not writing a textbook here, I thought the paper = was quite=20 informative and succinct. The only other thing that I felt was lacking = in=20 addition to the lack of performance measurements was no mentioning of = security=20 issues or considerations. This is a major issue in networking today, = which was=20 perhaps overlooked at the time, but because PRNET was developed for = military=20 reasons, I=92d be surprised if there weren=92t any considerations made = at all. This=20 is also another area that could probably have been explored = further.

 

 

------=_NextPart_000_000D_01C2531D.D7CD05D0-- From liuhz@CS.Cornell.EDU Tue Sep 3 09:31:05 2002 Received: from exchange.cs.cornell.edu (exchange.cs.cornell.edu [128.84.97.8]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g83DV5h13132 for ; Tue, 3 Sep 2002 09:31:05 -0400 (EDT) content-class: urn:content-classes:message MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" Subject: 615 PAPER 1 X-MimeOLE: Produced By Microsoft Exchange V6.0.5762.3 Date: Tue, 3 Sep 2002 09:31:05 -0400 Message-ID: <706871B20764CD449DB0E8E3D81C4D4302CEE5AF@opus.cs.cornell.edu> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: 615 PAPER 1 Thread-Index: AcJTTidzZW+r9ly1Q8qwLkLqPTGPDw== From: "Hongzhou Liu" To: "Emin Gun Sirer" Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from base64 to 8bit by sundial.cs.cornell.edu id g83DV5h13132 This paper gives a detailed introduction to the DARPA packet radio network, initiated in 1973 and usually thought to be the harbinger of nowaday ad-hoc network. The PRNET systerm comprises the PRNET subsut, which consists of the packet radios, and the collection of devices, each attached to a packet radio. The PRNET provides a dynamic addressing capability that maps devices to PRs logically. Fully automated algorithms and protocols to organize, control, maintain, and move traffic through the PRNET are given in this paper. And we can find that PRNET has been a quite robust and reliable packet-switched communications network by 1987. It providess end-to-end transportations with flow control, congestion control, duplicate suppression, error correction and detection. PRNET uses proactive routing to find the optimal routes before any data packets are transmitted. Control packets(PROP) are sent every 7.5s after a PR is powerred on, thus informatin about the network topology can be updated soon after it changes. A shortage of this routing protocol, common to most proactive algorithms, is that the periodic control packet wastes the bandwidth and power energy. PRNET also uses the headers of data packets to update the routing infomation, which, more or less, is a remedy of this waste. The acknowledgement mechenism in PRNET is very interesting. Two kinds of acknowledgement are used: passive and active. Passive TCP takes fully advantage of the broadcasting property the radio network and saves bandwidth greatly. The idea is similar to that of piggy-back ACKs of TCP in some way. The size of the sending window of PRNET is always 1, that is, no more packets can be transmitted to some PR before the packet transmitted to the same RP previously is acknowledged. IN PRNET system, this is called Single-Threading, which provides a form of flow control as well as congestin control naturally, but throughput is penalized as a result. And limited by the half-duplex property, I think it may be difficult to investigate any kind of sliding window protocol in PRNET, although this kind of protocol can improve the throughput dramatically. The author didn't explain why the PRNET protocols are designed to support only 138 entities. I suspect it's limited by the size of packet headers (because they contain severl PR IDs). Anyway, the scalability aspects of this system, as well as the energy consumption issues with a large amount of proactive overhead make it not so intriguing nowaday as in 1980's Hongzhou Liu From ks238@cornell.edu Tue Sep 3 09:38:20 2002 Received: from postoffice2.mail.cornell.edu (postoffice2.mail.cornell.edu [132.236.56.10]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g83DcKh14403 for ; Tue, 3 Sep 2002 09:38:20 -0400 (EDT) Received: from ks238.cornell.edu (syr-24-24-18-11.twcny.rr.com [24.24.18.11]) by postoffice2.mail.cornell.edu (8.9.3/8.9.3) with ESMTP id JAA13774 for ; Tue, 3 Sep 2002 09:38:20 -0400 (EDT) Message-Id: <5.1.0.14.2.20020903093705.01b32010@postoffice2.mail.cornell.edu> X-Sender: ks238@postoffice2.mail.cornell.edu (Unverified) X-Mailer: QUALCOMM Windows Eudora Version 5.1 Date: Tue, 03 Sep 2002 09:38:16 -0400 To: egs@CS.Cornell.EDU From: Karan Suri Subject: 615 PAPER #1 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed In this paper, Jubin and Tornow have provided a very comprehensive picture of the PRNET system, an early instance of a sophisticated, dynamically adjusting network. They begin by providing a high-level snapshot of the structure, components and organization of this PR Network. They then continue to delineate the mechanisms used by each of the mobile PR's within the network, by which they are able to dynamically adapt themselves to maintain a functioning network. To follow comes an explanation of data transmission through the network, which in addition to packet structure, includes an important discussion of primary and alternate routing protocols used by the PRs. The question of security within this network seems to be one area I am interested in which wasn't really directly addressed in the paper to the level that reliability was addressed. Obviously, security is a much graver concern today than it was in 1986. A discussion of security including prevention of unauthorized access to data transmissions in PRENET is a must as this is definitely an issue that is of concern for adaptive systems today. Furthermore, unauthenticated users joining the network at any time. I think an explanation outlining how to authenticate a valid PR in the network would have been helpful. I think overall many of the descriptions regarding forwarding protocols were rather terse. The author fails to address key issues regarding the efficiency of the chosen algorithms, specifically in regards to memory exhaustion. I think the authors did a stronger job in describing them rather than justifying them which brings into question what their objective for the paper was. In addition, as a smaller issue, I would have liked to see the authors draw more upon the conclusion of the paper. They touched upon possible applications of such a system but failed to expand. Perhaps this goes to shed light on one of the deficiencies of the PRNET system, specifically, scalability and robustness (i.e. "138 entities"). I think the paper would have been strengthened with additional insight into application. From smw17@cornell.edu Tue Sep 3 09:38:48 2002 Received: from cornell.edu (cornell.edu [132.236.56.6]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g83Dcmh14443 for ; Tue, 3 Sep 2002 09:38:48 -0400 (EDT) Received: from cornell.edu (syr-24-161-107-202.twcny.rr.com [24.161.107.202]) by cornell.edu (8.9.3/8.9.3) with ESMTP id JAA03345 for ; Tue, 3 Sep 2002 09:38:42 -0400 (EDT) Message-ID: <3D74BACD.9080304@cornell.edu> Date: Tue, 03 Sep 2002 09:36:13 -0400 From: Sean Welch User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.0; en-US; rv:0.9.4.1) Gecko/20020508 Netscape6/6.2.3 X-Accept-Language: en-us MIME-Version: 1.0 To: Emin Gun Sirer Subject: 615 PAPER 1 Content-Type: text/plain; charset=us-ascii; format=flowed Content-Transfer-Encoding: 7bit The DARPA Packet Radio Network Protocols The The DARPA Packet Radio Network Protocols paper describes the implementation of a basic packet-switched network system compatible with the emerging Internet (the DARPA Internet at the time). The system described is a self-configuring wireless network capable of bandwidth up to 400 kb/s. The PRNET employs a local table-based mechanism for packet routing, with the local table populated based on recieved broadcast control packets (PROP) and data packets. Dynamic routing (to account for topological changes, for instance) is achieved through re-evaluation of routing paths and link quality based on recieved data packets. A CSMA (Carrier Sense Multiple Access) scheme is used to help reduce the frequency of collisions during operation. For the time in which it was created, this set of protocols contains a number of interesting features. The system has the capability to account for varying topologies and mobile nodes based on the propagation of routing information in the PROP frames every 7.5 seconds. At the same time, it's behavior is such that for relatively fixed topologies, the chosen route should be relatively static. PRNET also makes repeated use of the broadcast nature of the transmission medium to reduce the network traffic due to packet acknowledgements. A DSS (Digital Spread Spectrum) transmission scheme improves the overall performance of the channel in noisy conditions. Combining the DSS scheme with a timestamp, PRNET has a limited ability to resolve a recieved signal even in the presence of a colliding transmission. The proposed scheme, however, scales very poorly with respect to the number of nodes in the network. Looking beyond the fact that this protocol is limited to 138 total network entities and 16 neighbors, the simple fact that each node stores a table of routing information to all other nodes, and must transmit this data in each PROP control frame leads to a linearly increasing table size as the number of nodes is scaled up. This results in increased network bandwidth for routing discovery (~n^2) and increased processing requirements at the local node. As implemented, the scheme also has little capability to account for a heterogeneous network, in which some nodes, while closer, may be less powerful (transmit power, stored energy, processing power, etc.) and less suitable as a routing path. I would suggest a few changes to the presented scheme. First, I would suggest building routing information more on a demand-basis rather than having every node build and maintain a complete routing table. Eliminating the data exchanges required to support a complete routing diagram should allow significantly improved scalability, albeit at an increased latency penalty. Second, the implementation of a number of different potential frequency channels for packet transmission would allow the system (at least under non-congested conditions) to operate as a full-duplex link by permitting transmit and recieve to take place at different frequencies. Upgrading the system to a full duplex link can potentially increase the net bandwidth of the system significantly. The final possibility I could see would be to adjust the protocol so that rather than spending bandwith to build and maintain a routing table, you could instead build and maintain a routing heirarchy. By implementing a heirarchical routing system such as that in the Internet, the routing can be much more efficient, since something of the network structure has been embedded in the device ID's themselves. /Sean From kfir.shay@cornell.edu Tue Sep 3 09:46:51 2002 Received: from postoffice2.mail.cornell.edu (postoffice2.mail.cornell.edu [132.236.56.10]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g83Dkoh16502 for ; Tue, 3 Sep 2002 09:46:50 -0400 (EDT) Received: from jigglypuff (syr-24-58-63-160.twcny.rr.com [24.58.63.160]) by postoffice2.mail.cornell.edu (8.9.3/8.9.3) with SMTP id JAA12475; Tue, 3 Sep 2002 09:46:50 -0400 (EDT) From: "Kfir Shay" To: Cc: Subject: 615 PAPER (1) Jubin and Tornow. The DARPA Packet Radio Network Protocols. Proceedings of the IEEE, Special Issue on Packet Radio Networks, vol. 75, pp. 21-32, January 1987 Date: Tue, 3 Sep 2002 09:46:49 -0400 Message-ID: MIME-Version: 1.0 Content-Type: text/plain; charset="windows-1255" Content-Transfer-Encoding: 7bit X-Priority: 3 (Normal) X-MSMail-Priority: Normal X-Mailer: Microsoft Outlook IMO, Build 9.0.2416 (9.0.2910.0) X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2600.0000 Importance: Normal In my opinion the paper main contribution is the fact that PRNET is a fully automated administrated network. A network that features self-configuring with initialization, reconfigure upon gain and loss of packets and has dynamic routing in real time and dynamic topology is corner stone of today's cell phone networks. Since the paper was published at 1987 and describe a network that has "been in daily operation for experimental purposes for ten years" one can only be impress with the level of sophistication achieved in those early days. Although in terms of network size; 138 entities and 50 packet radios; the paper seems absurd in today's terms there are references to work done on increasing the size of the network. In terms of the description of the algorithms, hardware and software the article is fairly straightforward. The paper rises a lot of the basic terms and concepts that now are part of mobile networks. The paper put emphasis on the fact that the main complexities with radio networks arise from the half duplex nature of the PR hardware. Scalability vs. performance issue is also mentioned in the paper as an active research area hinting that PRNET in the states described can't scale. Last the early date of publication of the paper is clear in the conclusion part where the author's vision of the potential uses of radio networks is very limited and can be easily expended. weak points: no elaboration on software. some crucial components are not described. no depth description of future research in terms of concepts that can be improved. conclusion in my opinion is a bit lacking-- but I wasn't around 87 too ;) Kfir S. kfir.shay@cornell.edu From linga@CS.Cornell.EDU Tue Sep 3 09:59:59 2002 Received: from snoball.cs.cornell.edu (snoball.cs.cornell.edu [128.84.96.54]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g83Dxxh19211 for ; Tue, 3 Sep 2002 09:59:59 -0400 (EDT) Received: from localhost (linga@localhost) by snoball.cs.cornell.edu (8.11.3/8.11.3/C-3.2) with ESMTP id g83Dxx121256 for ; Tue, 3 Sep 2002 09:59:59 -0400 (EDT) Date: Tue, 3 Sep 2002 09:59:59 -0400 (EDT) From: Prakash Linga To: Subject: 615 PAPER 1 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII DARPA PRNET PROTOCOLS This is a seminal paper on providing network communication in a mobile environment. This papers explores all the important aspects of designing such a system. The experimental network used here is a packet radio network. Devices and terminals can be attached to the PRs using a wired network. Routing algorithm is proactive with each PR sending its routing table info to its neighbors and eventually each PR knows the next hop PR (corresponding to the best route) for any destination PR. Neighbor table (list of neighbors), tier table (list of tuples) and device table (list of devices and the PRs they are attached to) are used for routing. Every packet traverses a single path and is also acknowledged by every PR along its path. Three component pacing protocol is used to provide flow and congestion control: Single-threading (packet transmitted to another PR is acknowledged before another packet is sent to the same PR), fair queueing discipline, CSMA to prevent interfering transmissions. Important contributions of this paper are: a first attempt to design a robust, reliable and scalable communication network in a mobile environment. Many of the ideas used in this paper and still used today (proactive routing, using a multiple-access channel etc). Some important drawbacks of this paper are: -no analysis or experimental results to show that the system works fine. -tested only for 138 entities. The solutions presented in the paper do not appear scalable (broadcast routing info to neighbors, maintain routing information about all PRs in the network etc). -radio transmission may not be the best option. -some details were skipped (for ex: algorithm to prevent isolated cliques) From tmroeder@CS.Cornell.EDU Tue Sep 3 10:01:30 2002 Received: from dhcp99-165.cs.cornell.edu (dhcp99-165.cs.cornell.edu [128.84.99.165]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g83E1Uh20033 for ; Tue, 3 Sep 2002 10:01:30 -0400 (EDT) Received: (from tmroeder@localhost) by dhcp99-165.cs.cornell.edu (8.11.6/8.11.6) id g83E1dF01681; Tue, 3 Sep 2002 10:01:39 -0400 From: Thomas Roeder MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Message-ID: <15732.49346.997031.458072@dhcp99-165.cs.cornell.edu> Date: Tue, 3 Sep 2002 10:01:38 -0400 To: egs@CS.Cornell.EDU Subject: 615 PAPER #1 X-Mailer: VM 7.05 under Emacs 21.2.1 The major contributions of the paper by Jubin and Turnow are clear: they are introducing an entirely new technology into the space of networking and network topology. The routing protocols are similar to some of the early ARPANET protocols, but they are clearly modified and new ones added to support the necessary changes in network topology which are caused by moving nodes which can have changes in their link quality. They deal with the (perhaps) new idea of transparent configuration of the networks, though it is hard to say if this "newness" is simply due to a deficiency in their references. They present large amounts of information on the exact functionality of their headers and the conditions under which the protocols work. This exposition of the state of the art laid a groundwork for further development outside of the military. A criticism which might be leveled at the same time, however, is that the wireless side of their research comes out of the void according to the paper, which is quite an unlikely scenario. There is no reference to work done before 1973 on the packet radio front, though likely it came out of amateur experiments or work at the universities. There is also a lack of clear analysis of the potential failure conditions of the network, and also little discussion of highly perturbed topologies, such as all the nodes moving from one place to another or several nodes moving all at once. It is not clear if these issues have been addressed and are not mentioned, or if they are simply avoiding the question for the moment. Equally, there are claims that the protocols always cause agreement about the topology over time, but no exact description of how it is done, for instance with respect to the methods of breaking the oscillation that can arrive when links go bad (bottom of pg. 24). It is difficult to describe ideas for expansion on a 15-year-old paper, especially as the work has been expanded upon greatly in those years. Yet some points do remain. In particular, their ideas in the conclusion have not commonly been acted on, even the simple idea of restaurants using packet radio to communicate orders (or at least I've never been to such a restaurant. At best they use a wired network from 1 or 2 fixed points in the dining area or just outside it). Another clear possibility for expansion is the scaling of their algorithms to thousands of nodes, though I believe that this has already been accomplished to some extent (I hope so, since they claim to have been working on it in 1986-7). Further, more advanced radio techniques could be used, avoiding the necessity of being in line of sight, for instance using bounce techniques that are common in the Amateur Radio community. Such a change would likely require changing to lower frequencies (and perhaps also slightly more "directed" radio communication, despite the claims in section IIA) to use some of the more simple bounce techniques. In general, however, the paper succeeds in introducing an apparently new way of looking at network routing and configuration, and gives a wealth of protocols to the interested reader. From wsl5@cornell.edu Tue Sep 3 10:12:08 2002 Received: from postoffice2.mail.cornell.edu (postoffice2.mail.cornell.edu [132.236.56.10]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g83EC8h22636 for ; Tue, 3 Sep 2002 10:12:08 -0400 (EDT) Received: from Shoga (syr-24-58-60-50.twcny.rr.com [24.58.60.50]) by postoffice2.mail.cornell.edu (8.9.3/8.9.3) with ESMTP id KAA10208 for ; Tue, 3 Sep 2002 10:12:08 -0400 (EDT) From: "William Liu" To: Subject: 615 PAPER 1 Date: Tue, 3 Sep 2002 10:11:58 -0400 Message-ID: <000001c25353$de2c6e80$0300a8c0@Shoga> MIME-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit X-Priority: 3 (Normal) X-MSMail-Priority: Normal X-Mailer: Microsoft Outlook, Build 10.0.2616 Importance: Normal X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2600.0000 The Jubin and Tornow paper gives a good overview into the DARPA Packet Radio Network. They discuss the advantages (highly mobile, low maintenance) and disadvantages (its half duplex and broadcast nature) of PRNET. Furthermore, Jubin and Tornow discuss the actual devices that are needed in the network and the routing protocols/algorithms which define PRNET. The protocols and algorithms give a good insight into the wireless networking space and the proactive approach to routing. Another strength of the paper is that they do seem to take a lot into consideration - they discuss error correction, a fairness algorithm to prevent a PR from hogging bandwidth, the network topology breaking into cliques and etc. However, on that same token, many of these topics are only covered in a cursory fashion. For example, they discuss how the network could be partitioned into cliques, and they merely mention that "the algorithm is careful to prevent isolated cliques." They never explain how the algorithm does this or any empirical data which shows that given some random network topology, their algorithm always guarantees a connected network. Another key issue that seems to go relatively untouched is security. One of the disadvantages mentioned in the paper is that "transmissions often reach unintended PRs." They describe this but do not go in-depth and talk about how they will a) prevent this from happening or b) have security mechanisms in place to prevent unauthorized access to the network. Another weakness of the paper would be that there was no real performance testing. I would have liked to seen some type of comparison between PRNET and say a wired approach. Also, they could have described what the performance of the network is like when the nodes are actually in movement (fluctuation). Furthermore, the paper never attacks the problem of scalability. Jubin and Tornow mention that there is an upper limit to the number of nodes connected to the network, but in real applications of a (useful) wireless network there are bound to be a large number of nodes which would be connected to the network. The PRNET paper could definitely be strengthened through a careful evaluation of some of the network issues such as scalability and performance. Also, I believe the paper could expand and delve deeper into certain topics like security and network topology (which could be important as the number of nodes increases). From nbs24@cornell.edu Tue Sep 3 10:16:48 2002 Received: from travelers.mail.cornell.edu (travelers.mail.cornell.edu [132.236.56.13]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g83EGmh23823 for ; Tue, 3 Sep 2002 10:16:48 -0400 (EDT) Received: by travelers.mail.cornell.edu (8.9.3/8.9.3) id KAA07568; Tue, 3 Sep 2002 10:16:47 -0400 (EDT) Date: Tue, 3 Sep 2002 10:16:47 -0400 (EDT) From: nbs24@cornell.edu Message-Id: <200209031416.KAA07568@travelers.mail.cornell.edu> To: egs@CS.Cornell.EDU Errors-To: nbs24@cornell.edu Reply-To: nbs24@cornell.edu MIME-Version: 1.0 Content-Type: text/plain Content-Transfer-Encoding: 7bit X-Mailer: IMP/PHP3 Imap webMail Program 2.0.9 Sender: nbs24@cornell.edu X-Originating-IP: 64.185.145.94 Subject: 615 PAPER 1 The paper provides an overview of the current state of the DARPA PRNET, after ten years of experimental operation. The paper discusses the various components of the first automatic flexible mobile network and touches on potential applications such as the provision of distributed access to distributed or centralized information or the use of single-hop PRN to improve commercial operations. The paper also provides future direction of their research, such as the design of better algorithms to enable a single network to organize and manage a much larger network and the enhancement of protocols to prevent degradation in large neighborhoods. A significant weakness in the paper is a measurement of performance of the network. It is mentioned that the network can handle heavy traffic. What amount of traffic are they looking at? How much power is required at each node? How often are packets and acknowledgments dropped? What is the recovery rate? How often are packets transmitted with errors? How quickly does the network know that a node has moved? To build on the research, the number of update tables per node could be reduced. Since updates are made on each topology change, rapid changes could be a problem. Thus the need for less updates will be ideal. A possible direction would be to merge the tier and neighborhood tables, since if a node is not a neighbor, the tier information becomes bad. Also, since the goal is to expand the network, another build to the research would be on congestion analysis and the development of algorithms that prevent congestion. From liuhz@CS.Cornell.EDU Tue Sep 3 10:31:56 2002 Received: from exchange.cs.cornell.edu (exchange.cs.cornell.edu [128.84.97.8]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g83EVth27115 for ; Tue, 3 Sep 2002 10:31:55 -0400 (EDT) content-class: urn:content-classes:message MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" Subject: 615 PAPER 1 X-MimeOLE: Produced By Microsoft Exchange V6.0.5762.3 Date: Tue, 3 Sep 2002 10:31:55 -0400 Message-ID: <706871B20764CD449DB0E8E3D81C4D4302CEE5B2@opus.cs.cornell.edu> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: 615 PAPER 1 Thread-Index: AcJTVqcqLMW+qneiRYCajKQ/P30Bhw== From: "Hongzhou Liu" To: "Emin Gun Sirer" Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from base64 to 8bit by sundial.cs.cornell.edu id g83EVth27115 This paper gives a detailed introduction to the DARPA packet radio network, initiated in 1973 and usually thought to be the harbinger of nowaday ad-hoc network. The PRNET systerm comprises the PRNET subsut, which consists of the packet radios, and the collection of devices, each attached to a packet radio. The PRNET provides a dynamic addressing capability that maps devices to PRs logically. Fully automated algorithms and protocols to organize, control, maintain, and move traffic through the PRNET are given in this paper. And we can find that PRNET has been a quite robust and reliable packet-switched communications network by 1987. It providess end-to-end transportations with flow control, congestion control, duplicate suppression, error correction and detection. PRNET uses proactive routing to find the optimal routes before any data packets are transmitted. Control packets(PROP) are sent every 7.5s after a PR is powerred on, thus informatin about the network topology can be updated soon after it changes. A shortage of this routing protocol, common to most proactive algorithms, is that the periodic control packet wastes the bandwidth and power energy. PRNET also uses the headers of data packets to update the routing infomation, which, more or less, is a remedy of this waste. The acknowledgement mechenism in PRNET is very interesting. Two kinds of acknowledgement are used: passive and active. Passive TCP takes fully advantage of the broadcasting property the radio network and saves bandwidth greatly. The idea is similar to that of piggy-back ACKs of TCP in some way. The size of the sending window of PRNET is always 1, that is, no more packets can be transmitted to some PR before the packet transmitted to the same RP previously is acknowledged. IN PRNET system, this is called Single-Threading, which provides a form of flow control as well as congestin control naturally, but throughput is penalized as a result. And limited by the half-duplex property, I think it may be difficult to investigate any kind of sliding window protocol in PRNET, although this kind of protocol can improve the throughput dramatically. The author didn't explain why the PRNET protocols are designed to support only 138 entities. I suspect it's limited by the size of packet headers (because they contain severl PR IDs). Anyway, the scalability aspects of this system, as well as the energy consumption issues with a large amount of proactive overhead make it not so intriguing nowaday as in 1980's From sc329@cornell.edu Tue Sep 3 11:22:13 2002 Received: from postoffice2.mail.cornell.edu (postoffice2.mail.cornell.edu [132.236.56.10]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g83FMDh09216 for ; Tue, 3 Sep 2002 11:22:13 -0400 (EDT) Received: from sangeeth.cornell.edu (syr-24-58-36-135.twcny.rr.com [24.58.36.135]) by postoffice2.mail.cornell.edu (8.9.3/8.9.3) with ESMTP id LAA24835 for ; Tue, 3 Sep 2002 11:22:12 -0400 (EDT) Message-Id: <5.1.0.14.2.20020903110651.00b0a3c0@postoffice2.mail.cornell.edu> X-Sender: sc329@postoffice2.mail.cornell.edu (Unverified) X-Mailer: QUALCOMM Windows Eudora Version 5.1 Date: Tue, 03 Sep 2002 11:22:14 -0400 To: egs@CS.Cornell.EDU From: Sangeeth Chandrakumar Subject: 615 PAPER 1 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed submitted by - Sangeeth Chandrakumar Jubin and Tornow - The DARPA Packet Radio Network Protocols. SUMMARY: This paper presents the state of the DARPA Packet Radio Network. It describes the algorithms and illustrates how the system provides a highly reliable network transport by dynamically determining effective routes, providing flow and congestion control in a mobile and variable load environment. This was one of the early works on the topic and provided a foundation for much of the research that has taken place in ad hoc networking. The PR system uses a digital subsystem to control the routing and flow of packets and an RF subsystem to transmit and receive packets over a radio channel. The system self-configures upon initialization and dynamically discovers the routing information by exchanging information with other host in the system. The protocols explained in the paper is designed to support up to 138 nodes and can maintain a maximum of 16 neighbors. Each node in the system has the complete information of the topology by maintaining the following tables: neighbor table - list of nodes one hop away and also the quality of the link tier table - notes the number of hops needed to reach any destination. device table - mapping of device-to-PR correspondence information. Packet headers provides the nodes with the information it needs to determine the action that needs to be taken upon receiving a packet. Passive and active acknowledgements are sent by the nodes, when it receives a packet. Re-transmission is controlled by pacing protocol to avoid congestion and to maintain an appropriate rate of flow. An alternate routing mechanism can be enabled by setting appropriate flags in the header. Fairness queuing prevents the monopolizing of the channel by a strong link. Collision of packets are avoided by adopting the CSMA protocol. A randomized delay is introduced while re-transmitting packets to decrease the degree of overlap. COMMENTS: - The system has been designed for a small no of nodes(138). So it doesn't scale well for the networking needs of current applications. - Discovery of topology by broadcast of PROP messages is not efficient as it wastes a lot of bandwidth and also it becomes ineffective when the network size becomes huge. - Maintaining 3 tables of information would increase the processing time at each node. - The paper doesn't mention anything about how the hosts could maintain a unique device identity. - None of the security aspects have been covered. - Doesn't provide any statistics on the performance of various aspects of the system. From pj39@cornell.edu Tue Sep 3 11:23:43 2002 Received: from travelers.mail.cornell.edu (travelers.mail.cornell.edu [132.236.56.13]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g83FNhh09326 for ; Tue, 3 Sep 2002 11:23:43 -0400 (EDT) Received: by travelers.mail.cornell.edu (8.9.3/8.9.3) id LAA21741; Tue, 3 Sep 2002 11:23:41 -0400 (EDT) Date: Tue, 3 Sep 2002 11:23:41 -0400 (EDT) From: pj39@cornell.edu Message-Id: <200209031523.LAA21741@travelers.mail.cornell.edu> To: egs@CS.Cornell.EDU Errors-To: pj39@cornell.edu Reply-To: pj39@cornell.edu MIME-Version: 1.0 Content-Type: text/plain Content-Transfer-Encoding: 7bit X-Mailer: IMP/PHP3 Imap webMail Program 2.0.9 Sender: pj39@cornell.edu X-Originating-IP: 128.84.99.29 Subject: 615 PAPER 1 This paper describes the DARPA PRNET system. It gives synopsis of the PRNET system concepts, its attributes and physical components. It explains the mechanism with which new nodes can easily join and leave the system. It describes how the packet routing takes place through PRNET subnet using broadcasting in a shared medium. PRNET uses broadcast radio via a common channel hence the communication is half duplex and for a node to transmit successfully it needs to know the status of other nodes. The PRNET system comprises of the PRNET subnet and the attached devices. As PRNET was basically designed for military purposes it is designed to support a maximum of 138 entities (a combination of devices and PRs). Thus a typical network would consist of about 50 PRs with attached devices. The current protocol allows each PR to support upto 16 neighbors. Each PR gathers and stores network information with the help of three tables i.e. neighbor table, tier table and device table. Every packet transmitted by contains the end-to-end (ETE) and routing headers. Both ETE and routing headers are created by the source PR and some of the fields are updated by the intermediate PRs. There a several weaknesses in the PRNET system. Firstly since it was basically designed for military purposes, it has an upper cap on the number of entities i.e. 138. Hence it is not useful when the size of a single network becomes too large eg thousands of PRs. Another weakness that I found was the possible creation of route loops. The paper says that mechanisms exist to break these route loops but it doesn't describe them in details. Another weakness is when a device moves and attaches itself to another PR all the packets destined to this device which have already started there journey and are in the subnet will be discarded at the destination PR since the destination PR is computed at the origin PR using the device table and this computation does not takes place in the subnet again. As the PRNET system was designed for military purposes, it has limits such as the no of neighbors limited to 16 and the number of allowed entities to 138. The system could be scaled to a bigger network thus allowing more than 16 neighbors and thousands of PR's. The paper could talk about specific examples and compare with similar other systems so that the readers have a better understanding of the system. It could talk in detail about the determination of logical neighborhood when the number of neighbors are greater than 16. It could talk in detail how the creation route loops can be avoided. It could talk in details about the algorithms used for fairness queuing. From vivi@CS.Cornell.EDU Tue Sep 3 11:35:35 2002 Received: from exchange.cs.cornell.edu (exchange.cs.cornell.edu [128.84.97.8]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g83FZZh12267 for ; Tue, 3 Sep 2002 11:35:35 -0400 (EDT) content-class: urn:content-classes:message MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Subject: 615paper1 X-MimeOLE: Produced By Microsoft Exchange V6.0.5762.3 Date: Tue, 3 Sep 2002 11:35:34 -0400 Message-ID: <47BCBC2A65D1D5478176F5615EA7976D14B4A4@opus.cs.cornell.edu> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: 615paper1 Thread-Index: AcJTX41r9BwgZuKDS6euZ0fnWVmoRA== From: "Vivek Vishnumurthy" To: "Emin Gun Sirer" Cc: "Vivek Vishnumurthy" Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from quoted-printable to 8bit by sundial.cs.cornell.edu id g83FZZh12267 The paper introduces the reader to the working of the DARPA Packet Radio Network. It describes the architecture of the setup and the methods used in the initialization and the functioning of the network in some detail. The project was initiated aiming to give birth to a distributed, robust network that could withstand the effects of a nuclear attack. So the project was of immense significance during its time. Though the paper is generally clear as to its intent, there are some instances where it is ambiguous. For example, in Section III B, Page 24, it says, "A necessary condition is that M be a bidirectionally good neighbor of N." Here the mechanism by which N decides if it (N) is a good neighbor of M has not been outlined. Another instance can be found in Section V B (Pg 29) where Fairness Queuing has been described. Again, how a PR decides if a link is a "monopolizing receive link" is not well defined. Also, according to the given description, in a situation where a PR M is receiving packets on two links: l1(more frequently) and l2(less frequently), the packets on l2 get preference over those on l1, since a newly arrived packet on l2 is placed ahead of the waiting packets that came over l1. This practice seems to go against the principle of fairness. The paper could have been improved if it had focused not just on the positive features of PRNET, but also on its weaknesses. We also do not see suggestions for enhancing the existing setup. The work can be extended by incorporating the above aspects. From ashieh@CS.Cornell.EDU Tue Sep 3 11:56:47 2002 Received: from zinger.cs.cornell.edu (zinger.cs.cornell.edu [128.84.96.55]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g83Fulh16996 for ; Tue, 3 Sep 2002 11:56:47 -0400 (EDT) Received: from localhost (ashieh@localhost) by zinger.cs.cornell.edu (8.11.3/8.11.3/C-3.2) with ESMTP id g83FukM11977 for ; Tue, 3 Sep 2002 11:56:46 -0400 (EDT) Date: Tue, 3 Sep 2002 11:56:46 -0400 (EDT) From: Alan Shieh To: Subject: 615 PAPER 1 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII The DARPA Packet Radio Network protocols This paper presented a self-organizing packet radio network. Multi-hop routing is achieved through a proactive algorithm in which routing information is exchanged both explicitly through control packets and implicitly through data packet headers. Bandwidth/volume considerations for scalability are also touched upon, both on the logical level ("logical" neighborhood) to save space in the routing control packets, and on the physical level (transmit power adjustment, although this was not implemented). The paper did not provide much information with which to evaluate the routing algorithm or to understand the design space. There were no measurements for the control overhead, or the time to propagate routing information and converge to a globally consistent view of the network topology (and whether this is necessary for optimal operation. The designers seemed preoccupied with adding features for correct operation). The conditions for tier table update were not explained (for instance, why the preference to route through the same node when the topology changes?), nor were the limits to scalability in their implmentation (link contention? breakdown in the routing algorithm? latency?) There also appears to be a tendency to bottlenecking in the routing algorithm. When choosing between two nodes with the same tier level relative to a given node, the path whose closest node first broadcasts a PROP is the one that is selected; the second route is not used except during alternate routing. Possible future directions: * Better load balancing mechanism to improve performance before congestion causes alternate routing to kick in * Measurement & analysis of optimizations described in paper - E.g. How gathering implicit routing information from data packets compares to dynamically varying the routing update interval * Measurements to provide a better feel of scalability, in terms of bandwidth usage, number of nodes, density of nodes, to guide further optimizations From aed13@cornell.edu Tue Sep 3 11:58:40 2002 Received: from postoffice.mail.cornell.edu (postoffice.mail.cornell.edu [132.236.56.7]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g83Fweh17273 for ; Tue, 3 Sep 2002 11:58:40 -0400 (EDT) Received: from andyd-laptop.cornell.edu (dhcp-576.rover.cornell.edu [128.84.26.64]) by postoffice.mail.cornell.edu (8.9.3/8.9.3) with ESMTP id LAA10768 for ; Tue, 3 Sep 2002 11:58:37 -0400 (EDT) Message-Id: <5.1.0.14.2.20020903111404.033fea00@postoffice.mail.cornell.edu> X-Sender: aed13@postoffice.mail.cornell.edu X-Mailer: QUALCOMM Windows Eudora Version 5.1 Date: Tue, 03 Sep 2002 11:58:39 -0400 To: egs@CS.Cornell.EDU From: "Andrew E. Davis" Subject: 615 PAPER 1 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed "The DARAPA Packet Radio Network Protocols" outlines the completed layered structure of a early but very complete switched packet radio network. The PRNET is structured to match OSI layering model, with datalink and routing layers. The datalink layer implements Carrier Sense Multiple Access in the RF component of the Low-cost Packet Radio, and the routing layer is implemented in digital controller layer as a series of three routing tables. Routing is performed by passing each message 1-hop closer to the destination, by computing the nearest neighbor. Routing state information is maintained pro-actively by transmitting a Packet Radio Organization message every 7.5 seconds broadcasting that PR's identity, neighbor table, tier table(number of hops to each remote node) and device table(a mapping of devices to PRs). The PRO messages enable dynamic and automatic configuration of the ad-hoc radio networks. This active transmission of PROs consumes bandwidth and power. The protocol is designed to work as an underlying network layer for TCP/IP, and to bridge through gateways onto existing Internet networks. Interesting properties that stand out in this early form of ad-hoc network included that each PR receiving the broadcast decides individually weather it should forward the packet. If the tables are not up to date this can lead to multiple path's in the network. This early ad-hoc network attempts to deal with packet duplication and cycles in the network with varying success. The broadcast nature of the wireless media enables PRNET to use Passive Acknowledgements, so that when a node forwards the packet to it's next nearest neighbor, this also functions as the acknowledgement back. The early PRNET did include all the necessary components of a truly adaptive network, especially by including Logical Addressing Layer to map devices to their changing PR and changing routes. Upon a device or PR moving, when the first connection fails the PRNET will update the logical addressing in time for the second TCP/IP re-transmission to map to the new known physical address. Andrew Davis aed13 From walsh@cs.duke.edu Tue Sep 3 12:30:46 2002 Received: from duke.cs.duke.edu (duke.cs.duke.edu [152.3.140.1]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g83GUjh25026 for ; Tue, 3 Sep 2002 12:30:45 -0400 (EDT) Received: from localhost (moe.cs.duke.edu [152.3.140.74]) by duke.cs.duke.edu (8.9.3/8.9.3) with ESMTP id MAA03625 for ; Tue, 3 Sep 2002 12:30:45 -0400 (EDT) Received: from 128.84.99.238 ( [128.84.99.238]) as user walsh@imap.cs.duke.edu by login.cs.duke.edu with HTTP; Tue, 3 Sep 2002 12:30:44 -0400 Message-ID: <1031070644.3d74e3b4e0304@login.cs.duke.edu> Date: Tue, 3 Sep 2002 12:30:44 -0400 From: walsh@cs.duke.edu To: egs@CS.Cornell.EDU Subject: 615 PAPER 1 MIME-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 8bit User-Agent: Internet Messaging Program (IMP) 3.0 X-Originating-IP: 128.84.99.238 The DARPA Packet Radio Network Protocols J. Jubin, J. D. Tornow. Provides a brief overview of most aspects of the DARPA packet radio network, including hardware, topology detection, routing, error correction and detection, naming and addressing, and CDMA. Routing is through a distance- vector approach, with accommodations for semi-mobile nodes, and link quality (“good” or “bad”). Routing information is proactively disseminated, as well as gleaned from data packets (mentioned, but not detailed). Other tables, maintained at each router, provide logical device naming and service naming. CSMA is used for local collision avoidance. Uses the classical end-to-end argument occasionally, but many functions are performed on a per-hop basis, such as error correction/detection, and retransmission. Main contributions: A comprehensive overview, touching on what seems to be the most important aspects of wireless radio networks. Uses a proactive distance-vector routing protocol, with accommodations for the “goodness” of neighbor links. Use of active and passive acknowledgements is clever, I thought. Weaknesses: Lacks discussion of the characteristics of the radio links themselves, such as transmission delays, typical error rates, power considerations, etc. This would have given some insight into the motivation for the approaches taken. Questions: Is the use of hop-by-hop error-checking/detection, acknowledgement, and retransmission justified? Probably, due to high end-to-end loss rates on the radio links. How is the potential for malicious remote (radio) firmware updates, jamming, and malicious packets handled? This is especially important in military situations. Are many “good” hops better than fewer “bad” hops? This is not mentioned, and not discussed. Overall, the main weakness is in providing motivation of the approaches, and in providing any evidence of their efficacy (or even that a problem exists). From walsh@cs.duke.edu Tue Sep 3 12:30:48 2002 Received: from duke.cs.duke.edu (duke.cs.duke.edu [152.3.140.1]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g83GUlh25036 for ; Tue, 3 Sep 2002 12:30:47 -0400 (EDT) Received: from localhost (moe.cs.duke.edu [152.3.140.74]) by duke.cs.duke.edu (8.9.3/8.9.3) with ESMTP id MAA03630 for ; Tue, 3 Sep 2002 12:30:46 -0400 (EDT) Received: from 128.84.99.238 ( [128.84.99.238]) as user walsh@imap.cs.duke.edu by login.cs.duke.edu with HTTP; Tue, 3 Sep 2002 12:30:46 -0400 Message-ID: <1031070646.3d74e3b6a0acf@login.cs.duke.edu> Date: Tue, 3 Sep 2002 12:30:46 -0400 From: walsh@cs.duke.edu To: egs@CS.Cornell.EDU Subject: 615 PAPER 1 MIME-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 8bit User-Agent: Internet Messaging Program (IMP) 3.0 X-Originating-IP: 128.84.99.238 The DARPA Packet Radio Network Protocols J. Jubin, J. D. Tornow. Provides a brief overview of most aspects of the DARPA packet radio network, including hardware, topology detection, routing, error correction and detection, naming and addressing, and CDMA. Routing is through a distance- vector approach, with accommodations for semi-mobile nodes, and link quality (“good” or “bad”). Routing information is proactively disseminated, as well as gleaned from data packets (mentioned, but not detailed). Other tables, maintained at each router, provide logical device naming and service naming. CSMA is used for local collision avoidance. Uses the classical end-to-end argument occasionally, but many functions are performed on a per-hop basis, such as error correction/detection, and retransmission. Main contributions: A comprehensive overview, touching on what seems to be the most important aspects of wireless radio networks. Uses a proactive distance-vector routing protocol, with accommodations for the “goodness” of neighbor links. Use of active and passive acknowledgements is clever, I thought. Weaknesses: Lacks discussion of the characteristics of the radio links themselves, such as transmission delays, typical error rates, power considerations, etc. This would have given some insight into the motivation for the approaches taken. Questions: Is the use of hop-by-hop error-checking/detection, acknowledgement, and retransmission justified? Probably, due to high end-to-end loss rates on the radio links. How is the potential for malicious remote (radio) firmware updates, jamming, and malicious packets handled? This is especially important in military situations. Are many “good” hops better than fewer “bad” hops? This is not mentioned, and not discussed. Overall, the main weakness is in providing motivation of the approaches, and in providing any evidence of their efficacy (or even that a problem exists). From egs@CS.Cornell.EDU Tue Sep 3 13:32:13 2002 Received: from zinger.cs.cornell.edu (zinger.cs.cornell.edu [128.84.96.55]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g83HWCh09483 for ; Tue, 3 Sep 2002 13:32:12 -0400 (EDT) From: Emin Gun Sirer Received: (from egs@localhost) by zinger.cs.cornell.edu (8.11.3/8.11.3/C-3.2) id g83HWCw00433 for egs; Tue, 3 Sep 2002 13:32:12 -0400 (EDT) Date: Tue, 3 Sep 2002 13:32:12 -0400 (EDT) Message-Id: <200209031732.g83HWCw00433@zinger.cs.cornell.edu> To: egs@CS.Cornell.EDU Subject: 615 PAPER 1 >From mp98@cornell.edu Tue Sep 3 12:00:00 2002 >Date: Tue, 3 Sep 2002 12:19:22 -0400 >Subject: DARPA Problems >From: Milo Polte >To: egs@CS.Cornell.EDU > >Fearless leader, > >Mark told me about Adaptive Systems, so I am going to attend today to >try it out. He also gave me a copy of the DARPA article and told me I >had to write an email to you detailing problems with the paper. I hope >this is what you had in mind, and I apologize if the contents are >somewhat sparse: > >One can level several trivial complaints against Jubin and Tornow's >paper, but the real difficulties seem to lie in their non-rigorous >treatment of their algorithms and numbers. For example, there is no >explanation as to why tier information ripples outward at an average >rate of 3.75s/hop (what hardware is doing this? How big is the network?). > >Some algorithms are mentioned but never explained. On page 24, for >example, they mention protocols to break routing loops but do not even >provide a reference. Forward Error Correction is mentioned, but not >referenced. > >The paper lacks real world measurements. How well does the network scale >and what is the possible data rate? On the other hand, some very >specific implementation details, like connecting a terminal via an >RS-232 interface or peer-to-peer propagation of new software versions, >seemed out of place. > >The entire treatment of the peer-to-peer aspect of the network is >sparse. There is no inquiry of how long it takes a new PR to assemble a >workable tier and neighbor table after joining a network. CSMA is >described in detail, but the particulars of how this changes in an >environment based on Line of Sight is not. Also, I couldn't find mention >of how the routing tables will handle the sudden disappearance of a node. > >-- >Milo > From egs@CS.Cornell.EDU Tue Sep 3 13:32:26 2002 Received: from zinger.cs.cornell.edu (zinger.cs.cornell.edu [128.84.96.55]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g83HWQh09514 for ; Tue, 3 Sep 2002 13:32:26 -0400 (EDT) From: Emin Gun Sirer Received: (from egs@localhost) by zinger.cs.cornell.edu (8.11.3/8.11.3/C-3.2) id g83HWPe00440 for egs; Tue, 3 Sep 2002 13:32:25 -0400 (EDT) Date: Tue, 3 Sep 2002 13:32:25 -0400 (EDT) Message-Id: <200209031732.g83HWPe00440@zinger.cs.cornell.edu> To: egs@CS.Cornell.EDU Subject: 615 PAPER 1 >From yao@CS.Cornell.EDU Tue Sep 3 11:13:32 2002 >content-class: urn:content-classes:message >Subject: 615 PAPER (The DARPA Packet Radio Network Protocols) >X-MimeOLE: Produced By Microsoft Exchange V6.0.5762.3 >Date: Tue, 3 Sep 2002 11:13:32 -0400 >X-MS-Has-Attach: >X-MS-TNEF-Correlator: >Thread-Topic: 615 PAPER (The DARPA Packet Radio Network Protocols) >Thread-Index: AcJTXHc0guyCIYUqRzGGoVeU1U1pTA== >From: "Yong Yao" >To: "Emin Gun Sirer" >X-MIME-Autoconverted: from base64 to 8bit by sundial.cs.cornell.edu id g83FDWh07198 > >This paper introduces the design principle and many implementation details of the first mobile wireless network, PRNET. It also covers many relevant problems common in mac and routing protocols, including how to recover after link or node failures, how to measure transmission delays, and how to synchronize different nodes, which are hot research problems discussed in many later papers. As I know, it is the first time these problems are proposed in mobile wireless network, or ad-hoc network. > > One weakness of the paper is it has no experiment results to compare their algorithms against alternatives. Some parameters are set up arbitrarily, such as a PROP packet will be broadcast every 7.5 seconds. The reader could be interested in the performance of the PRNET, but cannot find any relevant result in the paper. > > One possibility of the future work could be reliability. The paper has a short discussion about how to find an alternate route after topology changes, but it is not clear how efficient the protocol is, especially if a broken route cannot be recovered by neighboring nodes. Add a validation (experimental or analytical) of proposed algorithms is also an important expansion of the paper. >