MANET/OSPF Working Groups P. Spagnolo Internet-Draft T. Henderson Expires: September 30, 2004 G. Pei Boeing Phantom Works April 2004 Design Considerations for a Wireless OSPF Interface draft-spagnolo-manet-ospf-design Status of this Memo This document is an Internet-Draft and is NOT offered in accordance with Section 10 of RFC2026, and the author does not provide the IETF with any rights other than to publish as an Internet-Draft. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet-Drafts. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress." The list of current Internet-Drafts can be accessed at http:// www.ietf.org/ietf/1id-abstracts.txt. The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html. This Internet-Draft will expire on September 30, 2004. Abstract This document presents some analysis and simulation results intended to assist in the design of a wireless interface for the OSPF protocol. Our key findings are as follows: - in a MANET environment, LSA dissemination accounts for the overwhelming majority of overhead, - various techniques to reduce the overhead of LSA dissemination while maintaining reliability can improve the situation but not substantially (e.g., reduction no more than half), - the various reliable flooding proposals cannot approach, in highly mobile environments, the efficiency of unreliable flooding, which can achieve closer to order-of-magnitude reductions. Spagnolo, et al. Expires September 30, 2004 [Page 1] Internet-Draft Design Considerations Wireless OSPF April 2004 Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 2. Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . 4 3. Analysis of overhead contributions to OSPF . . . . . . . . . . 5 3.1 Neighbor Discovery . . . . . . . . . . . . . . . . . . . . . . 5 3.2 Adjacency Forming . . . . . . . . . . . . . . . . . . . . . . 6 3.3 Link State Flooding . . . . . . . . . . . . . . . . . . . . . 7 3.4 Reliability . . . . . . . . . . . . . . . . . . . . . . . . . 8 3.5 Summary of analysis . . . . . . . . . . . . . . . . . . . . . 8 4. Simulation results . . . . . . . . . . . . . . . . . . . . . . 10 4.1 Methodology . . . . . . . . . . . . . . . . . . . . . . . . . 10 4.2 Example Scenario . . . . . . . . . . . . . . . . . . . . . . . 11 4.3 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . 14 5. Flooding Optimizations . . . . . . . . . . . . . . . . . . . . 16 6. Ack Optimizations . . . . . . . . . . . . . . . . . . . . . . 18 6.1 Receiver Based Ack Suppression . . . . . . . . . . . . . . . . 18 6.2 Originator Based . . . . . . . . . . . . . . . . . . . . . . . 21 6.3 Retransmit Timer Back Off . . . . . . . . . . . . . . . . . . 22 6.4 Multicast Acks and the Ack Database . . . . . . . . . . . . . 23 6.5 Remove Acknowledgements . . . . . . . . . . . . . . . . . . . 24 7. Neighbor Discovery and Adjacency Forming . . . . . . . . . . . 25 8. Comparison with Unreliable Flooding . . . . . . . . . . . . . 26 9. Future Work . . . . . . . . . . . . . . . . . . . . . . . . . 29 9.1 Find Best Flooding Algorithm . . . . . . . . . . . . . . . . . 29 9.2 Adjacency Forming . . . . . . . . . . . . . . . . . . . . . . 29 9.3 Is optimized reilable flooding sufficient? . . . . . . . . . . 29 9.4 Adjust Packet Formats . . . . . . . . . . . . . . . . . . . . 29 9.5 Limit Links in LSAs . . . . . . . . . . . . . . . . . . . . . 30 References . . . . . . . . . . . . . . . . . . . . . . . . . . 31 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . 32 Spagnolo, et al. Expires September 30, 2004 [Page 2] Internet-Draft Design Considerations Wireless OSPF April 2004 1. Introduction A number of Internet Drafts have recently been proposed to design a wireless interface for OSPF: a problem statement, [3], which describes the reason a wireless interface is needed in OSPF, and three drafts that give solutions/ideas for a wireless interface: [4], [5], and [6]. We have performed simulation studies of our proposal [4] and aspects of the other two proposals [5] and [6]. This draft is intended to report some general performance trends that are evident in our simulation results. These trends should help prioritize the aspects of the OSPF wireless design that matter the most. Spagnolo, et al. Expires September 30, 2004 [Page 3] Internet-Draft Design Considerations Wireless OSPF April 2004 2. Motivation To briefly summarize the problem statement in [3], it has been repeatedly observed in experiments that OSPF does not have a suitable interface type for a wireless broadcast environment (which is characterized by a multicast-capable transmission medium that is not necessarily a full mesh, and which commonly has time-varying link availability and performance). One class of such networks has been called mobile ad hoc networks (MANETs), although there are other examples that are less ad hoc in nature. While a number of MANET routing protocols have been developed, their operation in large network deployments typically leads to the need to redistribute routing information between traditional IGPs and the MANET protocols, and hence a single, enhanced routing protocol would be operationally attractive. In particular, the operation of standard OSPF interface types over this type of technology typically leads to a lack of bandwidth scaling for network sizes as small as 10-20 nodes. All current drafts use the OSPF interface type as the basis for the extensions (rather than a new area type, which has been suggested on the mailing list). The point-to-multipoint (PTMP) interface is the baseline from which all results in this draft will be discussed. Our design goal in this study has been to evaluate the potential for the various proposals to reduce overhead while requiring each change to maintain a packet delivery ratio near legacy OSPF. All simulation was done using OSPFv2, but the trends should be applicable in OSPFv3. Spagnolo, et al. Expires September 30, 2004 [Page 4] Internet-Draft Design Considerations Wireless OSPF April 2004 3. Analysis of overhead contributions to OSPF This section will identify the main contributions to overhead caused by operating a Point-to-Multipoint (PTMP) interface in a MANET. We identify four main contributors to overhead. The network studied in this section is a MANET network with one interface in the same area on each router. In OSPFv2, a router with a single PTMP interface originates a single router LSA. After describing each overhead contributor and a representative example, we will order them from greatest to least amount of overhead. 3.1 Neighbor Discovery Neighbor discovery uses periodic Hellos to recognize neighboring routers. The total neighbor discovery overhead in a MANET is a factor of the Hello periodicity, the number of nodes, and the number of neighbors of each router. The amount of overhead, measured at the IP layer, due to neighbor discovery is well approximated by the following equation, where "avg-neighbors" is defined as the average number of neighbors of a router. overhead (bps) = =(#nodes)(bits/byte)(avg-hello-size)/(hello-interval) =(#nodes)(8)(IPheader + helloheader + IPaddress(avg-neighbors))/(hello interval) =(#nodes)(8)(20+44+4(avg-neighbors))/(hello interval) Figure 1 shows the Hello overhead (kbps) produced by a network with avg-neighbors = #nodes/2. The density of the network will define the ratio of neighboring routers to the number of routers in the network. | Hello interval (sec) #nodes | 2 5 10 15 -------------------------------------- 20 | 8.3 3.3 1.7 1.1 40 | 23.0 9.2 4.6 3.1 60 | 44.2 17.7 8.8 5.9 80 | 71.7 28.7 14.3 9.6 100 | 105.6 42.2 21.1 14.1 Figure 1: The Hello overhead (kbps) vs. number of nodes and Hello interval derived from equation. Spagnolo, et al. Expires September 30, 2004 [Page 5] Internet-Draft Design Considerations Wireless OSPF April 2004 3.2 Adjacency Forming On a point-to-multipoint interface, each time a 2-way neighbor adjacency is formed between routers, they must synchronize their databases. The overhead due to adjacency changes is high when a new router enters the network, or a partitioned network comes together. However, the majority of the new adjacencies do not produce significant overhead because databases already contain the same LSAs from other adjacencies. The overhead can be approximated by the following equation. overhead (bps) = =(#nodes)(bits/byte)((DD-poll-size + avg-DD-size)+ (avg-request-size ) )(new-adjacency-rate) =(#nodes)8(((IPheader+DDheader) + (IPheader + DDheader + LSAheader*avg-LSAsinDB))+ (IPheader + LSRheader + LSRentry *avg-LSAsOutSync)) (new-adjacency-rate) =(#nodes)8(((20+32)+(20+32+20*avg-LSAsinDB))+ (20+24+12*avg-LSAsOutSync ) )(new-adjacency-rate) The "avg-LSAsinDB" is defined as the average number of LSAs contained in the database. For the current example, it would be equal to the number of nodes in the network. But for a MANET linked to a wired network, outside LSAs could dwarf the number of LSAs from the MANET. The "avg-LSAsOutSync" is defined as the average number of LSAs that differ between newly neighboring routers. Again, this will be small for a MANET where nodes remain connected and large for a MANET that often partitions. The "new-adjacency-rate" is the rate at which new adjacencies are being formed, per node. In a point-to-multipoint network, neighbors that reach 2-way will form an adjacency, so the rate is highly dependent on the neighbor change rate. Figure 2 shows the approximate overhead (kbps) produced by adjacency forming. The left column lists the number of LSAs in the database, avg-LSAsinDB. At the top of the data columns, new-adjacency-rate/ avg-LSAsOutSync are listed. These values were chosen to match the example in Section 4.2. Spagnolo, et al. Expires September 30, 2004 [Page 6] Internet-Draft Design Considerations Wireless OSPF April 2004 | new-adjacency-rate/avg-LSAsOutSync | Low Medium High #LSAs | 0.02/0.2 0.05/0.19 0.07/0.38 -------------------------------------------------- 20 | 1.8 4.4 6.2 50 | 3.7 9.2 12.9 100 | 6.9 17.2 24.1 1000 | 64.5 161.2 225.7 2000 | 128.5 321.2 449.7 Figure 2: Database Description and LSR flooding overhead in kbps generated due to adjacency forming derived from equation. 3.3 Link State Flooding The PTMP interface uses standard broadcast flooding to propagate link state information to all routers. We define the Link State Flooding overhead to be the amount of overhead generated without any packet loss. In this ideal case, no acks would need to be sent, because of implicit acknowledgments. We consider acknowledgment traffic in the next subsection. The overhead generated due to link state flooding can be approximated by the following equation. overhead (bps) = =(#nodes)^2(bits/byte)(avg-LSU-size) (neighborchangerate) =(#nodes)^2(8)(IPheader + LSUheader + LSAheader + LSAlink(avg-neighbors))(neighborchangerate) =(#nodes)^2(8)(20+28+20+12(avg-neighbors)) (neighborchangerate) The intuition behind the equation is that each node will generate an LSU when its neighbor set changes. This LSU will be reflooded by every other node (standard broadcast flooding). Since each router has a single interface, only a router LSA is originated by each router; therefore, the LSU size can be fairly well approximated. Finally, the total network overhead is simply a single node's overhead times the number of nodes in the network. Figure 3 shows the overhead (kbps) produced by LSU traffic in the ideal case of no loss. The "neighborchangerate" is defined the rate for which neighbors enter and leave 2-way per node. The neighborchangerate and avg-neighbors are on the top of each column. These values were chosen to match the example in Section 4.2. Spagnolo, et al. Expires September 30, 2004 [Page 7] Internet-Draft Design Considerations Wireless OSPF April 2004 | neighborchangerate/avg-neighbors | Low Medium High nodes | 0.06/17.95 0.11/14.72 0.14/10.12 ----------------------------------------------------- 20 | 54.4 86.1 84.9 40 | 217.7 344.5 339.5 60 | 489.7 775.0 763.8 80 | 870.6 1377.8 1357.9 100 | 1360.3 2152.8 2121.7 Figure 3: LSU flooding overhead in kbps derived from equation (not including acks). 3.4 Reliability The point-to-multipoint interface uses acknowledgments to ensure that LSAs are delivered to their intended destination. Reliable flooding using acks requires each router to acknowledge each LSA it receives at least once. OSPF allows an LSA forwarded back out the received interface to act as an implicit acknowledgement. If an LSA is lost it is retransmitted after the LSA retransmit interval until either success or adjacency failure. It is difficult to develop a closed form solution for the overhead generated due to reliability requirement because of the complexity of the protocol and the dependency between neighbors. In some previous unpublished work, we developed a closed form under some simplified assumptions and ignoring some secondary orders of overhead. We determined that, with 10% packet loss rate per link, the reliability requirement can cause a 1/3 increase in the LSU retransmission overhead plus ACKs, which seems in line with the simulation results presented below in Section 4. In any final solution, it will be necessary to reliably flood LSAs originated outside the MANET ("outside LSAs"). These LSAs normally change at a much slower rate than those in the MANET and, there will be many more outside LSAs than internal LSAs. If they are not flooded reliably, they will swamp the network by having to be sent periodically. 3.5 Summary of analysis The above rough calculations indicate that LSU flooding, and acknowledgments, are by far the dominant contributors to overhead in a MANET environment. This is especially true in a MANET environment without many outside LSAs, but even if there are large numbers of LSAs from outside the MANET, the overhead due to database Spagnolo, et al. Expires September 30, 2004 [Page 8] Internet-Draft Design Considerations Wireless OSPF April 2004 synchronization should only be high if the network frequently partitions. Spagnolo, et al. Expires September 30, 2004 [Page 9] Internet-Draft Design Considerations Wireless OSPF April 2004 4. Simulation results 4.1 Methodology We used simulation to explore the performance trends due to the various OSPF proposals. Our simulations were performed with QualNet 3.7, using OSPFv2 and 2.4 GHz 802.11b models (Ricean fading) provided with the simulator. We have been using both of these models for two years, and have validated the basic operation of the OSPFv2 model against Linux routers running John Moy's ospfd implementation and against OPNET models. We have extended the OSPFv2 model to incorporate the wireless extension described in [4] and have validated these extensions against our implementation of [4]. We use startup techniques in our simulations to discourage synchronization effects. Finally, all simulation scenarios are averaged over 10 simulation seeds. Our simulations use classical MANET models such as random waypoint mobility on a square grid. Rather than present the gory details of the parameterization of our simulations, we instead believe that a set of statistics observable at the OSPF layer is sufficient to characterize what is going on and is more useful when comparing results obtained with different simulators and scenarios. These time-varying statistics include: 1. number of nodes 2. number of neighbors per node (averaged over all nodes) 3. number of neighbor state changes per unit time (averaged over all nodes) The first statistic indicates how well the simulations scale in size. The second statistic indicates how well the networks do with respect to differing node density. The third statistic indicates how much topological churn there is in the network. A fourth statistic might be the number of external LSAs handled by the topology, but we did not include external LSAs in these simulations. Our simulations introduced a light amount of user data, to study the performance of the routing. The main metric that we use to evaluate performance is the packet delivery ratio for user data. Other metrics such as routing stretch and frequency of transient routing loops were not studied. The main metric for which we are trying to optimize is OSPF overhead, both in terms of the number of packets of different types (unicast, multicast) and the total amount of data. Spagnolo, et al. Expires September 30, 2004 [Page 10] Internet-Draft Design Considerations Wireless OSPF April 2004 We note finally that simulations of wireless networks are inherently prone to oversimplification and should not be considered as definitive predictors of performance, but that simulations can yield insights as to what may likely occur in practice. Our results below should be interpreted in this light; we have used simulation as a tool to try to understand what is going on in the complex system. Our studies are ongoing but we believe that now is a good time in the discussion to raise some preliminary results. Again, in the following, we use the abbreviation PTMP for Point-to- Multipoint. 4.2 Example Scenario The scenario consists of 20 mobile nodes in a 500 by 500 meter square grid. Nodes move based on a random waypoint model where each selects a destination within the grid and a velocity between 0 and 10m/s, moves to the destination, pauses for 30 seconds, selects a new destination and velocity, and repeats the process. Each node is a router and has a wireless interface with an 802.11b radio at a carrier rate of 11Mbps. Each router also has a wired Ethernet interface connected to a host. Each host generates constant bit rate (CBR) traffic to every other node by sending periodic 40 byte packets. The interval between transmissions is such that the overall network CBR traffic is constant at approximately 16kbps. Each simulation trial was 60 minutes long, of which the first 30 minutes of data was discarded; each OSPF router was started at a random time in the first 30 minutes. The OSPF retransmit interval was set to 10 seconds, Hello interval to 10 seconds, dead interval to 40 seconds, and the LSA wait timer was set to 5 seconds. Again, this example is not meant to give precise estimates, but rather to identify what mechanisms account for the overhead being generated. We present three levels of mobility, labeled low, medium, and high. The following statistics (Figure 4) specify the level of network change due to each mobility level. Spagnolo, et al. Expires September 30, 2004 [Page 11] Internet-Draft Design Considerations Wireless OSPF April 2004 Mobility | Low Medium High ----------------------------------------------------- avg-neighbors | 17.95 14.72 10.12 neighbor-change-rate | 0.06 0.11 0.14 neighbor-life | 637.47 291.97 149.85 adjacency-rate | 0.02 0.05 0.07 LSAsOutSync | 0.20 0.19 0.38 Key: avg-neighbors = average number of neighbors per node neighbor-change-rate = the number of neighbors entering or leaving state 2-way per node per sec. neighbor-life = average number of seconds neighbors are in state 2-way adjacency-rate = the number of adjacencies being formed per node per second LSAsOutSync = average number LSAs different between two neighbors forming an adjacency Figure 4: Characterization of low, medium, and high mobility in the simulation runs. The following is the data gathered from simulating the 20 node network with the three mobility levels. All overhead values are given in total network overhead as opposed to per node overhead. The first block gives the total overhead resulting from each OSPF packet type. The LSU overhead has been subdivided into overhead from link state flooding and that from retransmissions. The second block gives the delivery ratio for data packets. The avg_hops is the average number hops traveled by the received packets, and the avg_failed_hops is the average number of hops a dropped packet traveled. Spagnolo, et al. Expires September 30, 2004 [Page 12] Internet-Draft Design Considerations Wireless OSPF April 2004 | Packets Bytes Kbps ---------------------------------------------------- Hello | 3600 491020 2.20 LSU | 30321 17812426 79.17 LSUfld| 21159 9798229 43.55 LSUrtx| 9161 8014197 35.62 LSAck | 10099 837301 3.70 LSR | 198 11094 0.04 D_DESC | 3037 603360 2.67 Total | 47256 19755204 87.8 Delivery Ratio: 0.98; Avg Hops: 3.1; Avg Failed Hops: 1.1 Figure 5: Low Mobility results. | Packets Bytes Kbps ---------------------------------------------------- Hello | 3600 447597 2.00 LSU | 48147 31137063 138.39 LSUfld| 31834 14923675 66.33 LSUrtx| 16313 16213388 72.04 LSAck | 18268 1637780 7.28 LSR | 329 18653 0.10 D_DESC | 5535 1104141 4.91 Total | 75880 34345236 152.7 Delivery Ratio: 0.93; Avg Hops: 3.2; Avg Failed Hops: 1.2 Figure 6: Medium Mobility results. Spagnolo, et al. Expires September 30, 2004 [Page 13] Internet-Draft Design Considerations Wireless OSPF April 2004 | Packets Bytes Kbps ---------------------------------------------------- Hello | 3600 384238 1.71 LSU | 54217 34845930 154.87 LSUfld| 35578 15209036 67.59 LSUrtx| 18639 19636893 87.28 LSAck | 20605 2060276 9.16 LSR | 675 41034 0.20 D_DESC | 7641 1528505 6.80 Total | 86740 38859983 172.7 Delivery Ratio: 0.80; Avg Hops: 3.5; Avg Failed Hops: 1.5 Figure 7: High Mobility results. 4.3 Discussion A couple of trends are evident in this data set, summarized in Figure 8. | Low Medium High ------------------------------------ Hello | 2.20 2.00 1.71 LSU-flood| 43.55 66.33 67.59 LSU-rxmt | 35.62 72.04 87.28 LSAck | 3.70 7.28 9.16 LSR | 0.04 0.10 0.20 DDESC | 2.67 4.91 6.80 Total | 87.80 152.70 172.70 Figure 8: Summary of overhead (kbps) at the three mobility levels. Flooding: The LSU-flood overhead indicates that the flooding overhead accounts for a dominant portion of the overhead. This result is intuitive because each router must retransmit the LSA originated from a single router, and it is what all optimized flooding algorithms work to avoid. Reliability: Depending on the mobility level, the greatest generator of overhead is due to reliably delivering LSAs. This can be seen by looking at the amount of overhead due to retransmissions of LSUs. In the high mobility case, the retransmission overhead accounts for over half the total overhead. The number of LSAcks are not significant because most acks are being accomplished implicitly. We will see in the next sections how optimized flooding changes this result. Spagnolo, et al. Expires September 30, 2004 [Page 14] Internet-Draft Design Considerations Wireless OSPF April 2004 Database Exchange: The overhead due to adjacency forming is minimal in this example. The reason for the small amount of overhead is because the routers are most often fully connected. The links change, but the network does not become partitioned. In addition, the current network does not contain LSAs from outside the MANET. If these LSAs existed, they would most likely dwarf the number of inside LSAs. But even in this case, increase of outside LSAs would most manifest itself in the flooding overhead before it shows in database exchange, unless one considers new nodes joining. Neighbor Discovery: The neighbor discovery protocol generates the least amount of overhead in this example. Since Hellos are generated periodically, the amount of overhead is well bounded. However, the overhead will grow as the Hello interval is lowered. In this example, the Hello interval was 10 seconds. These results suggest that techniques to optimize Hello traffic and database exchange may contribute only second-order effects to the overall overhead, and that making LSU flooding and retransmission more efficient should be the prime consideration. In the following sections, we present the optimization strategies according to the each of the overhead contribution source. Although these discussions are based on our simulation results that use IEEE 802.11 MAC protocol, it is worth mentioning that we also evaluated these strategies under TDMA based link layer. The preliminary results indicate that these strategies work equally well. Furthermore, due to more reliable broadcast, OSPF exhibits less overhead (about 20% less) because of less LSU retransmission needs under the TDMA based link layer. Spagnolo, et al. Expires September 30, 2004 [Page 15] Internet-Draft Design Considerations Wireless OSPF April 2004 5. Flooding Optimizations The results summarized in Section 4.3 suggest that overhead due to flooding and retransmission of LSUs is responsible for the largest portion of the overhead. If the flooding were optimized, then both categories of LSUs would be reduced. Ogier gives a good presentation of flooding optimization possibilities in Section 2 of [5]. Discussions on the MANET and OSPF mailing lists have debated using a source independent connected dominating set (SI-CDS) or a source dependent connected dominating set (SD-CDS) such as multipoint relays (MPRs). Two threads on this debate can be seen at [7] and [8]. We suggest the following criteria for selecting a flooding algorithm. - efficiency with respect to channel usage - compatibility with existing OSPF mechanisms - flexibility to define redundancy to increase robustness - complexity of the mechanism To explore this further, we implemented Lin's SI-CDS, Section III.D [9], to determine the influence that optimized flooding has on the unmodified point-to-multipoint interface. The optimization required modifying the Hello message for two reasons. First, the Hello message has to distinguish between 1-way and 2-way neighbors. Second, each node must determine if it should be on the CDS tree based on 2-hop information and then it must inform its neighbors of the decision. We modified the Hello message to pass CDS information. In this example, only this flooding optimization was added to the point-to-multipoint interface. The following data is for the high mobility case, which had characteristics as described in Figure 4. Spagnolo, et al. Expires September 30, 2004 [Page 16] Internet-Draft Design Considerations Wireless OSPF April 2004 | Packets Bytes Kbps ---------------------------------------------------- MHello | 3600 369093 1.64 LSU | 35550 21387807 95.06 LSUfld| 23022 9762499 43.38 LSUrtx| 12527 11625308 51.66 LSAck | 66697 6260619 27.84 LSR | 1601 104610 0.45 D_DESC | 9213 1833729 8.16 Total | 116661 29955860 133.1 Delivery Ratio: 0.79; Avg Hops: 3.6; Avg Failed Hops: 1.5 Figure 9: High Mobility results for Lin's SI-CDS. The most interesting result is that while optimized flooding decreased the LSU overhead by about 40%, it increased the LSAck overhead by three times. First, the LSUs are decreased since the originated LSAs are forwarded fewer times and the number of retransmissions are reduced. The flooding algorithm removes the redundant forwarding and improves the overall overhead. Second, optimized flooding increased the number of LSAcks by three times over the standard point-to-multipoint interface. Optimized flooding has an inverse effect on the number of acks sent in the network because every router that is designated as non-forwarding must send an ack for LSAs received. Previously, implicit acknowledgements were sent because each router must forward the LSAs. This identifies a fundamental tradeoff that is hard to avoid when using acks to maintain reliability: a more efficient flooding mechanism tends to increase the acknowledgment traffic when reliable flooding is employed. Finally, the overhead due to retransmissions is still a little over half of the total LSU overhead. Spagnolo, et al. Expires September 30, 2004 [Page 17] Internet-Draft Design Considerations Wireless OSPF April 2004 6. Ack Optimizations Ideally, an OSPF LSA is transmitted to each router once. To protect against losses and suppress retransmissions, the receiver somehow acknowledges the LSA. Acks are expensive in an environment where LSAs are changing rapidly with respect to timers. A number of optimizations have been suggested, and we will review these below. The first four subsections outline and analyze ideas to minimize the overhead due to acks without eliminating them. The last subsection looks at removing the need for LSAcks by using periodic database exchange messages. 6.1 Receiver Based Ack Suppression If a receiver guesses that it has received an LSA that will soon be updated, it might be best to suppress the ack. When a receiver guesses the LSA is relatively long-lived, it is best to ack since the absence of an ack leads to wasteful retransmissions. Ogier has proposed in [5] to suppress LSAcks when the topology is highly dynamic, and to ack using standard OSPF mechanisms when the topology is stable. In Section 5 of [5], a receiver-oriented approach is proposed to optimize the LSA flooding overhead. Each receiver suppresses LSAcks if it determines that the LSA update interval is much shorter than RxmtInterval. The proposal is intuitively attractive because it reduces the unnecessary LSAck overhead from frequent topology changes and reduces the unnecessary retransmissions of LSAs in unreliable LSA dissemination schemes, [4], for stable network topologies. The draft suggests determining the network stability by using a moving exponential average of the LSA interarrival times. The interarrival of the LSAs is suggested as a good measurement of topology dynamics due to various factors, not only mobility, but also channel and terrain. The following pseudocode shows the modifications that were made to OSPF to maintain an estimate of the LSA interarrival times, and how acks were suppressed in our simulations. We experimented with estimating the LSA interarrival times by using either an exponentially weighted or moving window average of LSA interarrival times. #define WIN_LEN //length of window to average #define RETRANSMIT //Sender side LSA Retransmit interval #define X // exponential average weight //global variables int T[WIN_LEN]; // window array initialized to zero int Tes = 0; // estimate of interarrival time Spagnolo, et al. Expires September 30, 2004 [Page 18] Internet-Draft Design Considerations Wireless OSPF April 2004 // between current and next LSA HandleReceivedLSA() { // maintain distinct Tes and T[] for each // LSA (type, LinkStateId, AdvertisingRouter) Calculate_Tes_for_this_LSA(); // should this LSA be Acked? if (Tes > RETRANSMIT) { SendAck(); } } Calcualte_Tes_for_this_LSA() { if (exp_average) { //if using exponential averaging Tes = X (current_time - T[0]) + (1-X) Tes; T[0] = current_time; } else if (win_average) { //if using a window average int avg_total = 1; int i; Tes = 0; for(i = (WIN_LEN - 1); i > 0; i--) { if (T[i-1] > 0 ) { T[i] = T[i-1]; Tes += T[i]; avg_total++; } } T[0] = current_time - T[0]; Tes += T[0]; Tes = Tes/avg_total; } } All simulations that we ran showed a consistent increase in the amount of overhead produced, compared with standard OSPF. We ran simulations for X = 0.2, 0.5, and 0.8 for the weighting and window sizes of 1, 3, and 5. Below is an example of running the exponential average with a weight = 0.8, and the mobility level at high. In order to have a significant number of acks, we used optimized flooding together with the SI-CDS. Spagnolo, et al. Expires September 30, 2004 [Page 19] Internet-Draft Design Considerations Wireless OSPF April 2004 | Packets Bytes Kbps ---------------------------------------------------- MHello | 3600 369062 1.65 LSU | 44460 31082080 138.14 LSUfld| 23152 9856310 43.81 LSUrtx| 21308 21225770 94.33 LSAck | 30984 2240812 9.95 LSR | 1577 104202 0.46 D_DESC | 9247 1841916 8.19 Total | 89871 35638074 158.4 Delivery Ratio: 0.79; Avg Hops: 3.6; Avg Failed Hops: 1.6 Figure 10: High Mobility results for Ogier's ack suppression. Compared to the SI-CDS results found in Figure 9, the data shows a reduction in ack overhead by about half; however, the ack reduction comes at the expense of transmitting about 45% more LSU overhead. Missing acks force the routers to retransmit when they should have received an ack. The reason the acks are not sent when they should be is discussed below. Although this scheme is intuitively attractive, the following bullets identify the weaknesses of this approach: - The approach adapts to the link changes passively by predicting the future LSA change based upon the LSA's history. In the MANET environment, it is difficult to predict future link changes based on the past. Looking at both fixed and exponentially weighted windows with different window sizes and weights, we could not predict when future LSAs would be created. In fact the distribution of interarrival times looked almost as if the interarrivals were exponentially distributed (modulo the MinLSInterval). - Not only was there a degree of unpredictability in the actual creation time of the LSAs, the practice of OSPF flooding further filters the interarrival process. A given forwarding node that may be multiple hops downstream of an originator must be able to predict if the originator is going to have link changes soon or if it is stable. - Even if each node suppresses the ACKs, the unstable LSAs are flooded throughout the network during rapid link changes around the originator. These LSAs generate much higher overhead than acks generated in response (overhead due to LSA transmissions dominates that of the acks). Spagnolo, et al. Expires September 30, 2004 [Page 20] Internet-Draft Design Considerations Wireless OSPF April 2004 - One problem not reflected in the output data is that the approach assumes all neighboring routers have the same RxmtInterval. This requirement may force the RxmtInterval to be interchanged between neighbors like the Hello and dead intervals, or to make it into an area parameter. 6.2 Originator Based From the study of receiver based ack suppression, we developed a new approach to try to reduce the overhead in a multihop wireless network. The approach is sender based in contrast to the proposal in [5]. In addition, Ogier proposed some changes to his approach found in [10] in which the originator can mark an LSA as non-ackable. These two originator approaches could be used in conjunction if shown to be useful. A router that originates an LSA has the ability to monitor the link change rates with all neighbors. If the router has layer-2 support it can predict link failures more accurately, but if it does not, it still knows that a link may fail soon based on how close the link is to reaching the Hello dead interval. The originator will transition into "periodic update" state if frequent link changes are predicted; otherwise, it will be in "event driven" state. The distinction between these two states is simply the amount of time the originator waits between originating new LSAs. The node in the periodic update state will not generate new LSAs within next PERIODIC_WAIT_TIME (> LSA_WAIT_TIME) seconds, while nodes in the event driven state will originate LSAs with the next LSA_WAIT_TIME. In contrast to the receiver-oriented approach in which unnecessary LSAs are flooded to the entire network, the sender-based approach suppresses them at the originator and eliminates all ACKs in the downstream for these unnecessary LSAs automatically. Therefore, the sender-based approach reduces much more overhead than that of the receiver-oriented approach since it reduces not only ACKs but also LSAs. The approach trades overhead for latency in disseminating LSAs. In addition, it allows hybrid periodic/event driven LSA dissemination. All simulations we ran with this approach showed a consistent decrease in the amount of overhead produced. Below we give an example of running with the mobility level at high. In order to have a significant number of acks, we used optimized flooding with the SI-CDS. Spagnolo, et al. Expires September 30, 2004 [Page 21] Internet-Draft Design Considerations Wireless OSPF April 2004 | Packets Bytes Kbps ---------------------------------------------------- MHello | 3600 369034 1.64 LSU | 34679 20209453 89.82 LSUfld| 20856 7977297 35.47 LSUrtx| 13823 12232155 54.36 LSAck | 61745 5583906 24.81 LSR | 1405 91817 0.40 D_DESC | 8971 1788616 7.95 Total | 110403 28042828 124.6 Delivery Ratio: 0.78; Avg Hops: 3.6; Avg Failed Hops: 1.7 Figure 11: High Mobility results for sender-based LSU suppression. There is a decrease in both LSU and LSAck overhead due to this approach. The LSU overhead decreased by 4% and LSAck by 10%. The total decrease in overhead is 6%. The decrease in overhead comes at the expense of 1% in the delivery ratio. After submitting [5], Ogier modified his receiver based ack suppression to a sender based approach. The idea is to have the LSA originator identify LSAs that change frequently, by maintaining an exponential moving average of the time between successive updates of its LSAs. The originator then identifies (via an option bit in the LSA) such frequently changing LSAs as "non-ackable". This approach again uses exponential averaging to predict future LSA changes. Our results suggest that this is not a good way to predict LSA change. However, the non-ackable bit would be useful if used with prediction based on layer-2 info, or Hello dead interval closeness. It would enable an LSA to enter a full periodic flooding state. This approach needs to be tested via simulation or implementation. 6.3 Retransmit Timer Back Off According to RFC 2328 [11], OSPF allows a different RxmtInterval for different interfaces (Section 13.6). A sender need not use the same fixed RxmtInterval to retransmit an LSA to a neighbor. This can be useful when a link is thought to be congested and/or bad. Instead of sending wasteful or damaging LSAs, a router can increase the retransmission interval adaptively. We suggest the possibility of backing off the retransmit timer after each successive transmission. The idea is that if no LSAck is received in a MANET then the link is probably going to go down, so we should not flood this link with useless retransmissions of LSAs. Spagnolo, et al. Expires September 30, 2004 [Page 22] Internet-Draft Design Considerations Wireless OSPF April 2004 All simulations we ran with this mechanism showed a consistent decrease in the amount of overhead produced. Below we give an example of running the mobility level at high. In order to have a significant number of acks, we used optimized flooding with the SI-CDS. | Packets Bytes Kbps ---------------------------------------------------- MHello | 3600 369316 1.65 LSU | 35725 21170624 94.09 LSUfld| 23120 9786621 43.50 LSUrtx| 12605 11384002 50.60 LSAck | 66571 6236427 27.73 LSR | 1606 106393 0.47 D_DESC | 9222 1833138 8.14 Total | 116725 29715899 132.1 Delivery Ratio: 0.79; Avg Hops: 3.6; Avg Failed Hops: 1.6 Figure 12: High Mobility results for retransmit timer backoff. Backing off the retransmit timer yields lower overhead, but the degree of reduction is insignificant compared to the total. If the retransmit timer were set to a lower value compared to the dead interval, the backoff may have a larger effect. 6.4 Multicast Acks and the Ack Database In [6], the authors suggest that all acks should be sent via multicast. This is similar to the broadcast interface in [11] Section 13.5. Sending the acks via multicast is advantageous because it enables a wireless interface to take advantage of the MANET's broadcast capability, and there is no additional overhead. On an 802.11 MAC, sending multicast acks when unicasts would normally be sent could increase collisions because only unicast packets use RTS/ CTS to avoid hidden node problems. In general, if acks are used to maintain reliability, acks should be multicast to limit the number of ack transmissions. Each router must ack each LSA that it receives; however, an optimal solution would enable each router to only ack each LSA once. In [6], the suggestion is made to have all neighbors keep a database of all acks that have been received. When a new LSA is received from any neighbor by multicast, the ack database must be checked to see if the LSA needs to be acked. If an ack has previously been received, then a new ack is suppressed; if not, an ack is multicast to all neighbors. This LSA will only be acked if a unicast retransmission of the LSA is seen. In addition, the senders of the LSAs must only Spagnolo, et al. Expires September 30, 2004 [Page 23] Internet-Draft Design Considerations Wireless OSPF April 2004 put the neighbors who have not previously acked the LSA on the retransmission list. If all neighbor have previously acked the LSA, it does not need to be flooded. The new mechanism trades memory and processing at each router for a reduction in the number of acks sent. All simulations we ran corresponding to this technique showed a consistent decrease in the amount of overhead produced. Here we give an example of running with the mobility level at high. In order to have a significant number of acks, we used optimized flooding with the SI-CDS. | Packets Bytes Kbps ---------------------------------------------------- MHello | 3600 369802 1.65 LSU | 35716 22197616 98.67 LSUfld| 22856 9675138 42.99 LSUrtx| 12860 12522478 55.66 LSAck | 13464 1889254 8.41 LSR | 1568 102339 0.45 D_DESC | 9096 1809478 8.06 Total | 63446 26368491 117.2 Delivery Ratio: 0.79; Avg Hops: 3.6; Avg Failed Hops: 1.5 Figure 13: High Mobility results for multicast acks. The results show a 70% decrease in the amount of overhead produced due to LSAcks as compared to Figure 9 where only the SI-CDS was used. This reduction in LSAcks is simply due to multicasting the acks and keeping memory of their reception before the LSA has arrived. In effect, we can approach the ideal of sending only one ack per LSA. Unexpectedly, we see a 7% increase in the overhead due to retransmitted LSUs. Our initial investigations suggest that the many duplicate acks sent without ack suppression increased the probability of at least one of them reaching the neighbor; therefore, an LSA had a greater chance of being acknowledged. In effect, we have more retransmissions because there are fewer acks. Overall, the overhead dropped by about 12%, which can be considered significant. 6.5 Remove Acknowledgements INRIA in [12] and Ogier in [5] present a mechanism derived from IS-IS [13], to use database exchange packets to maintain reliable flooding. The idea eliminates the need for acknowledgements, so it is a larger departure from legacy OSPF. However, if acks and retransmissions prove to create unacceptable overhead, these approaches need to be further investigated. Spagnolo, et al. Expires September 30, 2004 [Page 24] Internet-Draft Design Considerations Wireless OSPF April 2004 7. Neighbor Discovery and Adjacency Forming Differential Hellos, as described in [6], are a departure from the packet format of standard point-to-multipoint OSPF. In the scenarios examined herein, the overhead due to Hellos is minimal compared to the overhead from LSUs and LSAcks, so the effect of differential Hellos will be small. Nonetheless, they will reduce overhead from neighbor discovery especially if the Hello interval is short. Differential Hellos should be used if the working group judges that the departure from legacy OSPF is acceptable. The overhead due to adjacency forming is low compared to the overall overhead in the examples given. However, a large number of LSAs from outside networks could force large amounts of overhead to be generated when new nodes join the network. In [12], INRIA suggest a mechanism to decrease the size of database description packets. The idea is a significant departure from OSPF, and it needs to be tested further. Spagnolo, et al. Expires September 30, 2004 [Page 25] Internet-Draft Design Considerations Wireless OSPF April 2004 8. Comparison with Unreliable Flooding In [4], we described a wireless interface that uses unreliable flooding to distribute LSAs in the wireless network. We present results here to compare the overhead due to reliable flooding with that of unreliable flooding, using the same scenario. In addition, we consider the impact on MPR flooding when a flag is added to the duplicate table to determine if an LSF has previously been flooded. This flag was discussed on the MANET mailing list in [14], and the flag is defined in the OLSR RFC 3626, Section 3.4. The need for the flag occurs because MPRs are a SD-CDS. If an LSF is received by a node which is not an MPR of the sender, and then it is received by the same node from a different sender for which the receiver is an MPR, then the LSF will not be reflooded, since the LSF would be in the duplicate table. A flooded flag enables the LSF to be flooded even when the LSF is in the duplicate table. Ogier pointed out that this flag significantly reduces the efficiency of the MPR algorithm, and he suggested some changes to increase the efficiency in [14]. We simply use the flooded flag here, without such optimizations, to give an upper bound of the overhead in this example. We first present the overhead generated by WOSPF (wireless OSPF) without using the flooded flag in the duplicate table, then with the flooded flag, and then reliable flooding using the SI-CDS, source LSA suppression, backoff of the retransmit timer, multicast acks, and the ack database. We use the same high mobility level scenario in every example. | Packets Bytes Kbps ---------------------------------------------------- WHello | 3600 400460 1.79 LSF | 16533 3591222 15.97 Total | 20133 3991683 17.7 Delivery Ratio: 0.78; Avg Hops: 3.5; Avg Failed Hops: 1.8 Figure 14: WOSPF with Unreliable Flooding without the Duplicate Flooding Flag. Spagnolo, et al. Expires September 30, 2004 [Page 26] Internet-Draft Design Considerations Wireless OSPF April 2004 | Packets Bytes Kbps ---------------------------------------------------- WHello | 3600 400573 1.79 LSF | 27461 5993405 26.63 Total | 31061 6393979 28.4 Delivery Ratio: 0.78; Avg Hops: 3.5; Avg Failed Hops: 1.7 Figure 15: WOSPF with Unreliable Flooding with the Duplicate Flooding Flag. | Packets Bytes Kbps ---------------------------------------------------- MHello | 3600 369792 1.65 LSU | 34857 20716908 92.08 LSUfld| 20599 7862247 34.94 LSUrtx| 14257 12854660 57.13 LSAck | 13951 1815016 8.07 LSR | 1343 87632 0.39 D_DESC | 8817 1754470 7.81 Total | 62569 24743819 110.0 Delivery Ratio: 0.78; Avg Hops: 3.6; Avg Failed Hops: 1.7 Figure 16: WOSPF with Reliable Flooding. Figure 17 summarizes the comparison of the unreliable and reliable flooding results above. | SI-CDS MPR w/out flag MPR w/ flag | (reliable) (unreliable) (unreliable) ------------------------------------------------------ Total | 110.0 17.70 28.40 Hello | 1.65 1.79 1.79 LSA Flood | 34.94 15.97 26.63 LSA Rxmt | 57.13 - - LSAck | 8.07 - - LSR | 0.39 - - DDESC | 7.81 - - Deliv ratio | 0.78 0.78 0.78 Figure 17: Summary of overhead (kbps) for comparison of reliable and unreliable flooding. The overall overhead in both unreliable flooding cases are below that found in the reliable flooding case. In order to compare the unreliable and reliable flooding, we look at LSA flooding overhead Spagnolo, et al. Expires September 30, 2004 [Page 27] Internet-Draft Design Considerations Wireless OSPF April 2004 because LSA flooding is prior to any reliability mechanisms. Here we see that the amount of overhead produced with reliability is much higher than unreliable flooding. This does not give a good comparison of which flooding mechanism is more efficient (SI-CDS vs. MPR) because LSA flooding is periodic for unreliable flooding and event driven for reliable flooding. However, it does show that unreliable flooding overhead is not dependent on link change while reliable flooding overhead is highly dependent. If just the unreliable flooding cases are compared, the LSA overhead increases by 40% when the MPR flooding flag is added. In addition, we see that the delivery ratio is about the same in all cases. It may be interesting to point out that since WOSPF uses periodic unreliable flooding anyway and scenarios discussed in [14] are not common, it may not be worth turning on the flag to gain slightly in delivery ratio at the expense of doubling the overhead. Note, the delivery ratio is measured for light traffic in these experiments. For heavy traffic load, smaller routing overhead means higher possible user throughput. The large disadvantage to unreliable flooding occurs when the number of LSAs becomes large, specifically when many of those LSAs are long-lived (e.g., a wired network within the same flooding domain). In our study, the LSAs were limited to the nodes in the wireless network, but this will not be the case when outside networks are considered. Spagnolo, et al. Expires September 30, 2004 [Page 28] Internet-Draft Design Considerations Wireless OSPF April 2004 9. Future Work 9.1 Find Best Flooding Algorithm Our results suggest that LSU flooding and retransmissions are responsible for the largest portion of the overhead, and consequently should be the primary focus of the initial design. We have shown that optimized flooding reduces both of these overhead components. Put another way, an effort that tries to adapt OSPF for MANET environments *without* changing the flooding mechanism is likely only going to dance around the edges of the problem. 9.2 Adjacency Forming The large number of outside LSAs in a MANET will require large database exchange packets when adjacencies are being formed. A mechanism to reduce their size must be developed if the OSPF interface is going to scale to thousands of LSAs. The proposal by Clausen [12] is a start in this direction. We did not examine scenarios where this type of optimization will have the greatest effect. 9.3 Is optimized reilable flooding sufficient? One can envision making simple changes to OSPF such as implementing optimized flooding, delaying LSAs in some circumstances, and multicasting acks. The overhead from point-to-multipoint OSPF with these minor changes will consist of LSU flooding, acknowledgements, adjacency forming, and neighbor discovery. These optimizations may reduce the overhead by up to 50% if done correctly. Herein, we reduced the overhead by a maximum of 36%. Still, the question must be raised whether this level of overhead reduction is insufficient. If not, more substantial changes must be made to OSPF. We have already discussed the potential benefit of unreliable flooding in some scenarios. The next subsections point out where some additional changes might be possible. 9.4 Adjust Packet Formats A simple option to reducing overhead is to change packet formats, so that they carry less data. Examples of this are changing to differential Hellos as suggested in [6], or using differential LSAs as proposed in Section 6.4 of [5]. Our simulation results show that the Hello overhead is minimal compared to the total overhead, so changing Hello packet formats may only make a minor impact. Our simulation results also (e.g., for the high mobility scenario) indicate that even when the average link life Spagnolo, et al. Expires September 30, 2004 [Page 29] Internet-Draft Design Considerations Wireless OSPF April 2004 time is very long (e.g., 220 seconds), the LSA changing rate can be more than 20 times faster than the link change time. This is because of staggered effects from densely distributed neighbors. This means that a single LSA changes often, but each link changes slowly. Therefore, a differential LSA could potentially reduce the overhead drastically. 9.5 Limit Links in LSAs In a point-to-multipoint router LSA, there is a link to every adjacent neighbor. In a MANET, the number of links will be large when dealing with a dense network. It was proposed by Baker in [15] that neighbors might be limited so the number of links in LSAs would remain small. The problem with this solution is that packets cannot be routed to some direct neighbors. We suggest keeping the neighbors, but limiting the number of adjacencies. In addition, routes would be added to the routing table based on neighbor information. This would allow routing to continue at the local level, but the LSAs could remain small. The adjacency limiting approach was studied in [16]. Spagnolo, et al. Expires September 30, 2004 [Page 30] Internet-Draft Design Considerations Wireless OSPF April 2004 References [1] Bradner, S., "The Internet Standards Process -- Revision 3", BCP 9, RFC 2026, October 1996. [2] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997. [3] Baker, F., "Problem Statement for OSPF Extensions for Mobile Ad Hoc Routing", draft-baker-manet-ospf-problem-statement-00 (work in progress), October 2003. [4] Ahrenholz, J., "OSPFv2 Wireless Interface Type", draft-spagnolo-manet-ospf-wireless-interface-00 (work in progress), October 2003. [5] Ogier, R., "Alternative Designs for OSPF Extensions for Mobile Ad Hoc Networks", draft-ogier-manet-ospf-extension-00 (work in progress), November 2003. [6] Chandra, M., "Extensions to OSPF to Support Mobile Ad Hoc Networking", draft-chandra-ospf-manet-ext-00 (work in progress), March 2004. [7] "IETF MANET mailing list thread: http://www1.ietf.org/ mail-archive/working-groups/manet/current/msg04077.html". [8] "IETF MANET mailing list thread: http://www1.ietf.org/ mail-archive/working-groups/manet/current/msg04190.html". [9] Lin, T., "S.F. Midkiff, and J.S. Park, "A Framework for Wireless Ad Hoc Routing Protocols," IEEE WCNC", March 2003. [10] "IETF OSPF mailing list thread: http://peach.ease.lsoft.com/ scripts/wa.exe?A2=ind0402&L=ospf&T=0&O=D&P=11685". [11] Moy, J., "OSPF Version 2", STD 54, RFC 2328, April 1998. [12] Clausen, T., "DB Exchange for OSPFv2 Wireless Interface Type", draft-clausen-manet-ospf-dbx-00 (work in progress), February 2004. [13] Oran, D., "OSI IS-IS Intra-domain Routing Protocol", RFC 1142, February 1990. [14] "IETF MANET mailing list thread: http://www1.ietf.org/ mail-archive/working-groups/manet/current/msg04149.html". Spagnolo, et al. Expires September 30, 2004 [Page 31] Internet-Draft Design Considerations Wireless OSPF April 2004 [15] Baker, F., "An outsider's view of MANET", draft-baker-manet-review-01 (work in progress), March 2002. [16] Henderson, T., "P.A. Spagnolo, and J.H. Kim, "A Wireless Interface Type for OSPF, IEEE MILCOM 2003 Conference", October 2003. Authors' Addresses Phil Spagnolo Boeing Phantom Works P.O. Box 3707, MC 7L-49 Seattle, WA 98124 USA Phone: +1 425 865 6723 EMail: phillip.spagnolo@boeing.com Tom Henderson Boeing Phantom Works P.O. Box 3707, MC 7L-49 Seattle, WA 98124 USA Phone: +1 425 865 3609 EMail: thomas.r.henderson@boeing.com Guangyu Pei Boeing Phantom Works P.O. Box 3707, MC 7L-49 Seattle, WA 98124 USA Phone: +1 425 865 6720 EMail: guangyu.pei@boeing.com Spagnolo, et al. Expires September 30, 2004 [Page 32]