“Service Based Routing in Mobile Ad Hoc Network”

Final Report

CMSC628 Introduction to Mobile Computing

- Meenakshi Bangad

- Dhiresh Rawal

- Poonam Munshi

  1. Abstract

The Service-based Routing Protocol (SRP) is intended for use by mobile nodes in an ad-hoc network. The routediscovery process in such a network is driven by the need for a node to discover services. SRP realizes this idea by including service description of the requested service as a part of theService request packet. SRP also implements the concept of service groupswhere every service in the environment can be classified to belong to one or more groups. These groups are used for selective broadcasting. Thus routing is done based on the service desired and no prior knowledge about the destination is required. The destination in this case is the node which can provide the desired service.

The Service-based Routing Protocol enables dynamic, multihop routing between participating mobile nodes wishing to establish and maintain an ad hoc network. SRP allows mobile nodes to obtain destinations where the service can be provided and simultaneously establishes a route to the destination. It does not require nodes to maintain routes to destinations that are not in active communication. SRP allows mobile nodes to respondto link breakages and changes in network topology in a timely manner.When links break, SRP allows following up of service up to a certain time after which the affected set of nodes are notified so that they are able to invalidate the routes using the broken link.

One distinguishing feature of SRP is its use of a destination sequence number for each route entry.The destination sequence number is created by the destination for any route information it sends to requesting nodes. Given the choicebetween two routes to a destination, a requesting node always selectsthe one with the greatest sequence number.

  1. Overview of the Protocol Design

Service protocol assumes that links in ad hoc networks are symmetric and nodes arecooperative enough. Every node(X) in the network keeps track of the services of its one-hopneighbors(Y) and the groups to which the services of one hop neighbors of Y belongs to(this information will be used in selective broadcasting). The rate at which the nodes join/exit the network is order of magnitude lessthan the rate at which services are processed in the ad-hoc network.The basic operation of the service based routing protocol will involve three componentsas given below:

  • Service Discovery
  • Routing based on services
  • Route Maintenance

Service Description:

Since routing will be done based on the service requested, there should be some means torepresent it. We are using DAML (DARPA Agent Markup Language)to explicitlydescribe the services that can be handled by the ad-hoc network. Every service belongs toa classwhich may or may not be a subclass of some of some generic classof services.This is needed for semantic matching of services during service discovery phase.

Here is the service ontology to be used with our protocol (Service Advertisements and Requests will be based on this ontology).

DAML Ontology for Service Description

<?xml version="1.0" encoding="UTF-8"?>

<rdf:RDF

xmlns:rdf ="

xmlns:rdfs ="

xmlns:daml ="

xmlns:thisFile ="file://service.daml#">

<daml:Ontology rdf:about="">

<rdfs:comment>This is an ontology that will be used to describe services in our ad hoc network</rdfs:comment>

<daml:imports rdf:resource="

</daml:Ontology>

<daml:Class rdf:ID="Service">

<rdfs:label>ServiceClass</rdfs:label>

<rdfs:comment>The Generic Class of all services that will be provided in our Ad Hoc Network. Every service in the ad hoc network will be directly or indirectly subclass of this group </rdfs:comment>

</daml:Class>

<daml:DataTypeProperty rdf:ID="Priority">

<rdfs:domain rdf:resource="#Service"/>

<rdfs:range rdf:resource="

</daml:DataTypeProperty>

<daml:Class rdf:ID="hardware">

<rdfs:subClassOf rdf:resource="#Service"/>

<rdfs:label>Hardware Service </rdfs:label>

<rdfs:comment> This is a group of all hardware services in the ad hoc network </rdfs:comment>

</daml:Class>

<daml:Class rdf:ID="software">

<rdfs:label>SoftwareService</rdfs:label>

<rdfs:subClassOf rdf:resource="#Service"/>

<rdfs:disjointFrom resource="#HardwareService"/>

<rdfs:comment>Software Types of services</rdfs:comment>

</daml:Class>

<daml:Class rdf:ID="deviceio">

<rdfs:subClassOf rdf:resource="#HardwareService"/>

<rdfs:label>Device IOService</rdfs:label>

<rdfs:comment>Device IO kind of services</rdfs:comment>

</daml:Class>

<daml:Class rdf:ID="printer">

<rdfs:subClassOf rdf:resource="#deviceio"/>

<rdfs:label>PrinterService</rdfs:label>

<rdfs:comment> An example Of The Printer Service</rdfs:comment>

</daml:Class>

<daml:Class rdf:ID="PrinterColorValues">

<daml:oneOf rdf:parseType="daml:collection">

<daml:Literal rdf:value="Black-and-White"/>

<daml:Literal rdf:value="All Color"/>

</daml:oneOf>

</daml:Class>

<daml:ObjectProperty rdf:ID="PrinterColor">

<rdfs:domain rdf:resource="#printer"/>

<rdfs:range rdf:resource="#PrinterColorValues"/>

<thisFile:Priority rdf:value="1"/>

</daml:ObjectProperty>

<daml:Class rdf:ID="PrinterSpeedValues">

<daml:oneOf rdf:parseType="daml:collection">

<daml:Literal rdf:value="640"/>

<daml:Literal rdf:value="800"/>

<daml:Literal rdf:value="1500"/>

</daml:oneOf>

</daml:Class>

<daml:ObjectProperty rdf:ID="PrinterSpeed">

<rdfs:domain rdf:resource="#PrinterService"/>

<rdfs:range rdf:resource="#PrinterSpeedValues"/>

<thisFile:Priority rdf:value="2"/>

</daml:ObjectProperty>

<daml:Class rdf:ID="PrinterModelValues">

<daml:oneOf rdf:parseType="daml:collection">

<daml:Literal rdf:value="LaserJet"/>

<daml:Literal rdf:value="InkJet"/>

<daml:Literal rdf:value="DotMatrix"/>

</daml:oneOf>

</daml:Class>

<daml:ObjectProperty rdf:ID="PrinterModel">

<rdfs:domain rdf:resource="#Printer"/>

<rdfs:range rdf:resource="#PrinterModelValues"/>

<thisFile:Priority rdf:value="3"/>

</daml:ObjectProperty>

</rdf:RDF>

In a similar way, we have defined other kind of services in our ad hoc network.Currently, we are assuming that all the nodes in the ad-hoc network will refer to the same ontology for their service description.

The description of the services is based on this ontology. When no match is found in service cache (cache used to keep track of one-hop available services) for the service specified in request, a semantic reasoner will be used. It will refer to this ontology to find a more generic class of service which can be used to satisfy the request.

Though the above ontology has been developed and a semantic reasoner has also been developed by us for the same, for our SRP simulation, simple pattern matching has been used. This was due to the lack of an interface between XSB and Parsec compiler used by GlomoSim.

In our SRP implementation, each node is initialized with a random service from a set of hard coded services. Each hard coded service also has a group (generic class) associated with it.

Also in our implementation, we don’t have an application which provides the service which it desires in the packets which are sent to the lower layers. Hence, for our implementation purposes, we are generating our own service requests at the network layer itself.

SRP Message Types and Their Description:

There are six types of messages used by SRP for service discovery process and routing. These message types undergo normal IP header processing. So, for instance, the requesting node is expected to use its IP address as the Originator IP address for the messages. For broadcast messages, the IP limited broadcast address (255.255.255.255) is used. This means that such messages are not blindly forwarded. However, SRP operation does provide means to constrain the flooding of packets throughout the ad hoc network.

M-1 : Service Advertisement Packet (SADV)

The Service Advertisement packet is sent by each node that advertises its own services and also the groups of services that are reachable from it. It contains the following information:

  • Node address for the advertising node
  • Sequence no of the advertising node
  • Broadcast-id of the packet
  • Service description
  • Groups of services in it’s one hop neighbors

The following two packets are needed in the service discovery phase:

M-2 : Service Request Packet (SREQ)

The Service Request packet contains the following information:

  • Maximum Hop count
  • Service description of the desired service
  • Originator Sequence Number (for duplicate requests)
  • Originator Address

M-3: Service Reply Packet (SREP)

The Service Reply packet contains the following information:

  • Maximum Hop count
  • Service description
  • Destination address (address of the node where the service is found)
  • Destination Sequence Number (for duplicate requests)
  • Originator Address
  • Address of the last node which handled the service reply

The following two packets are needed for the route maintenance and service follow-up whenever a route breaks:

M-4: Route Request Packet (RREQ)

The Route Request packet contains the following information:

  • Maximum Hop count
  • Broadcast id
  • Destination address (address of the node where the service was initially found)
  • Destination Sequence Number (for duplicate requests)
  • Originator Address
  • Originator Sequence number
  • Address of the last node which handled the service request

M-5: Route Reply Packet (RREP)

The Route Reply packet contains the following information:

  • Hop count
  • Destination address (address of the node where the data packets are buffered)
  • Destination Sequence Number
  • Originator Address
  • Lifetime

M-6: Route Error Packet (RERR)

The Route Error packet contains the following information:

  • No of unreachable destinations
  • Destination address (address of the node which has become unreachable)
  • Destination Sequence Number (for duplicate requests)
  1. Overview of SRP Operation

In SRP protocol, each node maintains the following data structures :

  1. Service cache (to keep track of services and groups reachable at its one-hop neighbors)
  2. Route table ( to keep track of the routes to various destinations )
  3. Neighbor table ( to maintain a list of active neighbors)
  4. Seen table ( to keep track of requests already seen by it )
  5. Sent table ( to keep track of requests sent by it )

Our designed protocol uses various types of packets for its proper operation along with the normal routing packets.

In our protocol design, each node maintains a ‘Service cache’. This service cache holds the information of all the services (service description) provided by the nodes in its one hop vicinity. Along with that particular service description provided by all the one hop nodes, the service cache also records all the generic groups (the immediate superclass) of the services available through its one-hop neighbors.

Service cache needs to be updated periodically so that it does not contain the stale information regarding the services present at the neighbors. For this every node broadcasts its local service(the services which it can provide) advertisements to all the one-hop neighbors atsome fixed intervals of time (passive caching). It also includes all the class groups ofservices that can be reached by it. The service cache is updated whenever a node receives a service advertisement from its one-hop neighbors. If the advertisements are not received at regular intervals, the neighbor is assumed to have left and the stale service cache entry is deleted. Thus, the idea of updating the service table at regular intervals of time guarantees that up-to-date information about the services available at its one hop neighbors is maintained by each node.

Service Discovery Phase:

When a node wants a service, it first finds out if it cansatisfy the service itself. If that is the case then it does not need to initiate any service discovery process.If this is not the case, it tries to find if any one of its neighbors can providethe service by looking up in the service cache. If it finds one, it starts the regular routing of the packet to this destination.

If this fails, then itselectively broadcastsa service discovery packet to all the neighbors that have services belonging tothe same generic class as the requested service. This generic class is the immediate superclass of the class of service requested. This information is inferred from the service ontology by the semantic reasoner. If no generic class is found then the service request is broadcasted.

The originator of the service discovery process also sets a maximum hop count of the packet so that after that the packet will not be forwarded infinitely. Each time a source node does selective broadcasting, it increments the sequence number as well as sets the hop count to 1 in the SREQ packet. The source also enters the service request into the ‘Sent table’ to prevent further requests for the same service to be sent until it receives a reply for that service (or times out). Whenever a node receives a packet with the same service description and with the same sequence number, it just ignores it.

Each intermediate node records the address of the node from which it received the request in its route table and also inserts into the ‘Seen table’, the details of the SREQ it just processed (thus noting that the service request was already seen). This helps it to discard the duplicates which may be received later by it.

When a node, which can provide the service, receives a service request, it updates its Route table and forms a service reply packet. Each forward route table entry will contain the following information:

  • Destination Address
  • Next hop address
  • Expiration time of the route (similar to that of the reverse route table)
  • Maximum hop count
  • Actual number of hops (from the source)

In the case of the destination node, the next hop address and the destination address will be the same. It then sends the reply back on the path on which it received the service request.

When an intermediate node receives a reply packet, it will update its route table for the forward path, with the information in the reply packet and then unicast the packet back to its previous hop neighbor from which it received the request.

When the source of the service request receives the service reply, it updates its route table and then sends the data packets it has for this service in its buffer to this destination (now known) which can provide the service for the data packets.

Semantic Reasoning Used For Selective Broadcasting:

These are some of the triples obtained from the service ontology for the use of semantic reasoning for selective broadcasting.

triples (hardware, subclassof, service).

triples (software, subclassof, service).

triples (deviceio, subclassof, hardware).

triples (printer, subclassof, service ).

When a node is unable to find a matching service for the request from the service cache, it goes for selective broadcasting.

E.g. when the printer service is not found in service cache, its immediate super-group is determined based on the triples shown above and only those nodes which have the matching group in the group entry of service cache will be send the request.

Routing Based On Service:

Once the service discovery phase is over and the forward paths and the reverse route havebeen established, thenode requesting that particular service records the destination node address (serviceproviders) and the next hop address in its routing table. The node will then route allpackets related to the service to the next hop address as recorded in its forward route table withthe destination now specified. Thus our protocol is a true service based routing protocolas we are first finding a node on the basis of the service and then using the same route forforwarding of the packets.Each time a node sees a packet for an active route, it resets the timer in its reverse route table.

Route Maintenance:

The route maintenance involves the issues related to nodes joining and leaving the ad hocnetwork.

Link Failure during an Active Session:

Whenever a path is established and packets are being routed along a route to the destination, we call that time frame as “Active Session”.

There are two approaches tried out by us to handle link failure. One solution is to transmit an error packet back and start the whole of the service discovery process again. This solution has a major drawback: all packets which were already successfully routed will have to be routed again.

Another approach we tried is to follow the service whenever the forwarding node detects a link failure for its one hop neighbor. Once the node knows that its neighbor (or next hop) is unreachable, it takes its address from the “next hop neighbor” entry in the forward route table and initiates a Route discovery for this particular destination by sending a RREQ packet on the network. Now, this node becomes the source and the disconnected node becomes the destination.