2.1 Project Background
2.2 Dynamic Source Routing (DSR) Protocol
2.3 Destination-Sequenced Distance Vector (DSDV)
2.4 Optimized Link State Routing (OLSR) Protocol

2.1 PROJECT BACKGROUND

This project is part of the "Wireless Ad Hoc Messenger'' project sponsored by Microsoft. The goal of the project is to develop a Pocket PC Instant Messenger application that enables users to chat with one another in a wireless ad hoc and peer-to-peer (P2P) environment without the need for any pre-existing wireless LAN or WAN infrastructure. Whenever a user with a Pocket PC walks into the ad hoc environment, a "buddy" list similar to that in MSN Messenger's Instant Messaging pops up and the user can chat online with his/her buddies in the infrastructure-less ad hoc network. The report documents the design, implementation and testing of the Pocket PC P2P Instant Massager using Microsoft .Net Compact Framework® and C#® programming language, as well as Microsoft Smart Device Extension® for the .Net platform. The application demonstrates multiple hop communications based on UCP socket API from the .Net Compact Framework. There is no physical infrastructure. All Pocket PCs communicate with each other using Compaq® IEEE 802.11 wireless LAN cards.

Before C# implementation of Pocket PC P2P Instant Messenger, another student of Dr. Chen, Ms. Hongyang Tang, who also worked on this project during Spring semester 2002, designed the user interface of chatting based on the personal Java® running on Pocket PC's Jeode® runtime environment. The application is implemented on the PC and based on the TCP socket API. Since a significant difference exists between PC and Pocket PC platform, as well as the difference between LAN based TCP and 802.11b based UDP, the design and implementation are significantly different from the original interface design. Plus, the original design limited the scope to the interface design, while this report actually designs a working prototype based on the Dynamic Source Routing (DSR) protocol.

Forsberg (2001) described a peer-to-peer wireless Instant Messenger application that uses ViaXML® from Odyssey Software. ViaXML is a product that enables Pocket PCs to expose and call Web Services (including services that allow Pocket PCs to connect directly with each other) called ViaXML. ViaXML enables each Pocket PC to act like both a client and a server, even within the same application. Since ViaXML uses the HTTP protocol instead of IP-based UDP, it cannot broadcast packets to fulfill the requirement of multihop Ad Hoc routing.

Lam (2001) developed a Messenger application "WinChat For .NET" using C# and Microsoft .Net Framework. It is a simple peer-to-peer chatting program that functions very similarly to the WinChat program provided by Windows 2000. It provides all the functionalities that the original WinChat program provides. WinChat For .NET is based on many basic yet powerful techniques provided by the .NET platform, including Multi-Threading, Event-Driven, Windows Form Control and Socket Programming, etc. It uses UDP client/server for local notification, and uses TCP connections to deliver chatting functions. We use some ideas from Lam such as divide the module into "user Interface", "UDP client" and "UDP server" modules, while the projects still have many differences: In out project, we do not use TCP connections; instead, we use UDP class for socket programming. Because of the performance issue, we tried to reduce the thread numbers for the application. The platform base is Pocket PC with .Net Compact Framework, while Lam's project is based on full version of Microsoft .Net Framework and Windows Platform. Most importantly, we implement mutilhop and broadcasting functions.

Wireless Ad Hoc network is a wireless local area network without an infrastructure, in which some of the network devices are part of the network routes themselves. The term "Ad Hoc" has been applied to office or home networks, in which new devices can be quickly added, using, for example, the proposed Bluetooth technology or 802.11b in which devices communicate with the computer and perhaps other devices using wireless transmission.

For our project, we use 802.11b wireless technology for our network support. The 802.11 technology refers to a family of specifications developed by IEEE for wireless Local Area Network (LAN) technology. The 802.11 specifies an over-the-air interface between a wireless client and an access point (in infrastructure mode) or between two wireless clients (in ad hoc mode). We use the 802.11b (Wi-Fi) in ad hoc mode (or peer-to-peer) that provides 11 Mbps transmission (with a fallback to 5.5, 2 and 1 Mbps) between 2 wireless devices in the 2.4 GHz band. We use Compaq® Wireless LAN PC card as the hardware to support our 802.11b wireless Ad Hoc network.

There are many proposals for the mobile ad hoc network environment: Destination-Sequenced Distance Vector (DSDV) is a hop-by-hop distance vector routing protocol requiring each node to periodically to update routing updates; Temporally-Ordered. Routing Algorithm (TORA) is a distributed touting protocol to discover route on demand based on "link-reversal" algorithm; Dynamical Source Routing (DSR) protocol uses source routing with each routed packet carried path information on its header; Ad Hoc On-Demand Distance Vector (AODV) is the combination of DSR and DSDV, with DSR protocol's Route Discovery and Route Maintenance and periodic beacon from DSDV; The Optimized Link State Routing (OLSR) Protocol operates as a table-driven and proactive protocol, and exchanges topology information with other nodes of the network regularly. In this report, we survey three protocols in more detail; Dynamical Source Routing (DSR) protocol, Destination-Sequenced Distance Vector (DSDV) and Optimized Link State Routing (OLSR) protocol. Our design borrows some of the ideas from these existing protocols, although it is DSR-based.

2.2 DYNAMIC SOURCE ROUTING (DSR) PROTOCOL

Accord to Johnson et el. (2001), Dynamic Source Routing protocol (DSR) is a simple and efficient routing protocol designed specifically for use in multi-hop wireless ad hoc networks of mobile nodes. The protocol is composed of the two mechanisms of Route Discovery and Route Maintenance, which work together to allow nodes to discover and maintain source routes to arbitrary destinations in the ad hoc network. Broch et al (1998) ovulated the performance of DSR protocol and got the conclusion that DSR was very good at all mobility rates and movement speeds, although its use of source routing increases the number of routing overhead bytes required by the protocol.

Diagram 2.1 Network Topology Example

Route Maintenance is the mechanism by which a Node C detects changes of the network topology such that it can no longer use its route to Node A because of the network status of Nodes B or D has changed. Node C will be notified so that it will use alternative route in its cache or revoke another Route Discovery.

In this report, we implemented the Route Discovery mechanism of the DSR protocol. During route request phase, Node C broadcasts XML-based packet with the original path information stored in the packet as "<Path>C; </Path>" and destination node's ID information as "<DID>A</DID>". When this packet travels through Node B, B checks the destination ID information. Since it does not match with its own ID, Node B re-broadcasts the packet with the Path in the packet updated to "<Path>C; B; </Path>". Node A receives the Packet from B, thus completing the Route Discovery phase. Node A adds itself to the Path information in the packet's Path field "<Path>C; B; A; </Path>". In Route Reply phase, Node A uses the reverse Path information field "<Path>A; B; C; </Path>" and delivers the route path information to C, thus completing the Route Discovery process.

We do not implement Route Maintenance process in this report; instead, the design philosophy can also apply to the design of Route Maintenance. Also, in this report, since each Node does not store route cache information in each node, it has to revoke Route Discovery every time for a new session. We will leave Route Maintenance for future work.

2.3 DESTINATION-SEQUENCED DISTANCE VECTOR (DSDV)

Perkins et al. (1994) presented Destination-Sequenced Distance Vector (DSDV) protocol. It is based on the idea of the classical Bellman-Ford routing algorithm. In DSDV, each node maintains a routing table containing the next-hop information for each reachable destination. Each entry has a sequence number, and if a new entry is given, it prefers the one with the greatest sequence number, or if their sequence is the same, it chooses the metric with the lowest value. Each node advertises an increasing even sequence number for itself. According to Broch et al (1998), a performance evaluation shows that DSDV performs quite predictably, delivering virtually all data packets when node mobility rate and movement speed are low, and failing to converge as node mobility increases.

In this report, during the Nodes' "Awareness" stage, we implemented hop-to-hop routing and periodic beacons as in the DSDV protocol. As described in Diagram 2.1, when Node C joins the wireless Ad Hoc network, it broadcasts packets that carried its information and original Path information as "<Path>C; </Path>" in XML format. When the packet reaches B, B will add its own ID into the Path as "<Path>C; B; </Path>", also add Node C as its "Buddy List" and re-broadcasts the packet. When the packet from B reaches A, A adds C to its "Buddy List" and also adds A's ID into the Path "<Path>C;B;A;</Path>". In this project, all newly detected and reachable nodes are considered as buddies. Since B or D's ID already exists in the Path information of the packet, Nodes B and D will ignore re-broadcasted packets from A. In this way, we can prevent infinite broadcasting among nodes. After the establishment of "Buddy List", Node C will periodically broadcast beacon packets to other nodes to update the status. Because of the processing power of Pocket PC, we design the interval as 10 seconds or 20 seconds to prevent overflow the application with beacon packets.

2.4 OPTIMIZED LINK STATE ROUTING (OLSR) PROTOCOL

Jacquet (2001) proposed an Optimized Link State Routing protocol (OLSR) that is best suitable for large and dense wireless Ad Hoc networks. The protocol is based on the link state algorithm and it is proactive (or table-driven) in nature. It employs periodic exchange of messages to maintain topology information of the network at each node. The protocol uses multipoint relaying technique to efficiently and economically send its control messages. It provides the optimal route in terms of the number of hops, which is immediately available when needed. Laouiti et al (2001) presented a performance evaluation of OLSR mobile ad-hoc routing protocol by a random graph model and a random unit graph model. The random graph model is realistic for indoor or short-range outdoor networks where link fading mainly comes from random obstacles. The random unit graph model is realistic for long-range outdoor networks where link fading mainly comes from distance attenuation. Based on OLSR protocol, Calafate (2002) ported the OLSR implementation to Windows 2000 & Pocket PC.

In this report, we do not implement the OLSR protocol for the Pocket PC project. In the future, we can investigate the work performed by Calafate and investigate the possibility of implementing OLSR protocol for the Instant Messenger application. Based on the same application, we can evaluate the performance for each protocol.