AD hoc networks assignment

computer_science

chapter6bAdHocNetworks2.pdf

Home >Computer Science homework help >AD hoc networks assignment

Fund. Wireless & Mobile Protocol

COSC4301/5340 Ad Hoc Networks

Instructor: Dr. Xingya Liu Department of Computer Science

Lamar University

Office: MAES 86 Phone: 409-880-8677

Email: xliu@lamar.edu

Fund. Wireless & Mobile Protocol

Types of Routing Protocols

•  Reactive Protocols (seeks for routes only when required)

–  Maintain routes only if needed

•  Proactive Protocols (Actively seeks for routes)

–  Determine routes independent of traffic pattern

–  Traditional (link-state, distance-vector) routing protocols are proactive

•  Hybrid Protocols

Liu 2

Fund. Wireless & Mobile Protocol

Routing Protocols for Ad Hoc Networks

•  Reactive Routing Protocols –  DSR (Dynamic Source Routing)

–  AODV (Ad-Hoc on-Demand Distance Vector)

•  Proactive Routing Protocols –  DSDV (Destination Sequenced Distance Vector)

–  OLSR (Optimal Link State Routing)

•  Hybrid Routing Protocols –  ZRP (Zone Routing Protocol)

–  TORA (Temporally-Ordered Routing Algorithm)

–  CEDAR (Core Extraction Distributed Ad-hoc Routing)

3 Liu

Fund. Wireless & Mobile Protocol

Proactive Routing Protocols

•  Proactive schemes based on distance-vector and link- state mechanisms have been proposed

–  Link-State: •  Each node maintains a view of the network topology

–  Distance-Vector: •  Every node maintains the distance to each destination

•  Considerable overhead spent in maintaining “network state”

4 Liu

Fund. Wireless & Mobile Protocol

Destination-Sequenced Distance- Vector (DSDV)

•  C. Perkins, “Highly Dynamic Destination Sequenced Distance Vector Routing (DSDV) for Mobile Computers, ” Proceedings of ACM Sigcomm Conference, 1994

•  DSDV is destination-based

•  No global view of topology

•  DSDV is proactive (table-driven) –  Each node maintains routing information for all available destinations

–  Update routing information periodically

–  Maintain routing information for routes which are not used

–  Overhead even if no change in network topology

5 Liu

Fund. Wireless & Mobile Protocol

Destination-Sequenced Distance- Vector (DSDV)

•  Each node maintains a routing table which stores –  Next hop towards each destination –  A cost metric for the path to each destination –  All available destinations each with a destination sequence number that is

created by the destination itself –  Sequence numbers used to avoid formation of loops

•  Each node periodically forwards the routing table to its neighbors –  Each node increments its sequence number when sending its local routing

table –  This sequence number will be attached to route entries created for this

node

•  Bi-directional links are required 6 Liu

Fund. Wireless & Mobile Protocol

DSDV (Table Entries)

•  Sequence number originated from destination. Ensures loop freshness.

•  Install Time when entry was made (used to delete stale entries from table)

•  Stable Data Pointer to a table holding information on how stable a route is. Used to damp fluctuations in network.

Destination Next Metric Seq. Nr Install Time Stable Data

A A 0 A-550 001000 Ptr_A

B B 1 B-102 001200 Ptr_B

C B 2 C-588 001200 Ptr_C

D B 3 D-312 001200 Ptr_D

A B C D

Liu

Fund. Wireless & Mobile Protocol

DSDV (Route Advertisements)

•  Advertise to each neighbor own routing information –  Destination Address –  Metric = Number of Hops to Destination –  Destination Sequence Number

•  Rules to set sequence number information –  On each advertisement increase own destination sequence

number (use only even numbers)

–  If a node is no more reachable (timeout) increase sequence number of this node by 1 (odd sequence number) and set metric = ∞

8 Liu

Fund. Wireless & Mobile Protocol

DSDV (Route Selection)

•  Update information is compared to own routing table

–  1. Select route with higher destination sequence number (This ensure to use always newest information from destination)

–  2. Select the route with better metric when sequence numbers are equal.

9 Liu

Fund. Wireless & Mobile Protocol

DSDV (Tables)

C Dest. Next Metric Seq

A A 1 A-550 B B 0 B-100 C C 1 C-588

Dest. Next Metric Seq A A 0 A-550 B B 1 B-100 C B 2 C-588

Dest. Next Metric Seq. A B 2 A-550 B B 1 B-100 C C 0 C-588

B A 1 1

Liu

Fund. Wireless & Mobile Protocol

DSDV (Route Advertisement)

(A, 1, A-550) (B, 0, B-102) (C, 1, C-588)

C B A

B increases Seq. Nr from 100 -> 102 B broadcasts routing information to Neighbors A, C including destination sequence numbers

Dest. Next Metric Seq A A 0 A-550 B B 1 B-102 C B 2 C-588

Dest. Next Metric Seq A A 1 A-550 B B 0 B-102 C C 1 C-588

Dest. Next Metric Seq. A B 2 A-550 B B 1 B-102 C C 0 C-588

1 1

Liu

Fund. Wireless & Mobile Protocol

DSDV (Respond to Topology Changes)

•  Immediate advertisements

–  Information on new routes, broken links, metric change is immediately propagated to neighbors.

•  Full/Incremental Update:

–  Full Update: Send all routing information from own table.

–  Incremental Update: Send only entries that has changed. (Make it fit into one single packet)

12 Liu

Fund. Wireless & Mobile Protocol

DSDV (New Node)

(D, 0, D-000)

C B A D Dest. Next Metric Seq.

A A 0 A-550 B B 1 B-104 C B 2 C-590

Dest. Next Metric Seq. A A 1 A-550 B B 0 B-104 C C 1 C-590

Dest. Next Metric Seq. A B 2 A-550 B B 1 B-104 C C 0 C-590 D D 1 D-000

1. D broadcast for first time Send Sequence number D-000

2. Insert entry for D with sequence number D-000 Then immediately broadcast own table

Liu

Fund. Wireless & Mobile Protocol

DSDV (New Node)

(A, 2, A-550) (B, 1, B-104) (C, 0, C-592) (D, 1, D-000)

C B A D Dest. Next Metric Seq.

A A 1 A-550 B B 0 B-104 C C 1 C-592 D C 2 D-000

Dest. Next Metric Seq. A A 0 A-550 B B 1 B-104 C B 2 C-590

Dest. Next Metric Seq. A B 2 A-550 B B 1 B-104 C C 0 C-592 D D 1 D-000

……… ………

3. C increases its sequence number to C-592 then broadcasts its new table. 4. B gets this new information

and updates its table…….

Liu

Fund. Wireless & Mobile Protocol

DSDV (no loops)

(D, 2, D-100) (D, 2, D-100)

C B A D Dest. Next Metric Seq.

… … … D C 2 D-100

Dest. Next Metric Seq. … … … D B 3 D-100

Dest. Next Metric Seq. … … … D D ∞ D-101

1. Node C detects broken Link: -> Increase Seq. Nr. by 1 (only case where not the destination sets the sequence number -> odd number)

2. B does its broadcast -> no affect on C (C knows that B has stale information because C has higher seq. number for destination D) ⇒ no loop ⇒ no count to infinity

Liu

Fund. Wireless & Mobile Protocol

DSDV (Immediate Advertisement)

(D, ∞, D-101) (D, ∞, D-101)

C B A D Dest Next Metric Seq.

… … …

D C 3 D-100

Dest. Next Metric Seq.

… … …

D B 4 D-100

Dest. Next Metric Seq.

… … …

D B 1 D-100

Dest. Next Metric Seq. … … … D D 1 D-100 D D ∞ D-101

1. Node C detects broken Link: -> Increase Seq. Nr. by 1 (only case where not the destination sets the sequence number -> odd number)

3. Immediate propagation B to A: (update information has higher Seq. Nr. -> replace table entry)

2. Immediate propagation C to B: (update information has higher Seq. Nr. -> replace table entry)

Dest. Next Metric Seq. … … … ... D C 2 D-100 D C ∞ D-101

Dest. Next Metric Seq. … … … ... D B 3 D-100 D B ∞ D-101

Liu

Fund. Wireless & Mobile Protocol

DSDV (Problem of Fluctuations) •  What are Fluctuations

–  Entry for D in A: [D, Q, 14, D-100]

–  D makes Broadcast with Seq. Nr. D-102

–  A receives from P Update (D, 15, D-102) -> Entry for D in A: [D, P, 15, D-102] A must propagate this route immediately.

–  A receives from Q Update (D, 14, D-102) -> Entry for D in A: [D, Q, 14, D-102] A must propagate this route immediately.

•  This can happen every time D or any other node does its broadcast and lead to unnecessary route advertisements in the network, so called fluctuations.

Q P

12 Hops 13 Hops

(D,0,D-102)

Liu

Fund. Wireless & Mobile Protocol

DSDV (Damping Fluctuations)

•  How to damp fluctuations

–  Record last and avg. Settling Time of every Route in a separate table. (Stable Data) Settling Time = Time between arrival of first route and the best route with a given seq. #.

–  A still must update its routing table on the first arrival of a route with a newer seq. #., but it can wait to advertising it. Time to wait is proposed to be 2x (avg. Settling Time).

–  Like this fluctuations in larger networks can be damped to avoid un-necessary advertisement, thus saving bandwidth.

Q P

12 Hops 13 Hops

Liu

Fund. Wireless & Mobile Protocol

DSDV Summery •  Advantages

–  Simple –  Loop free through destination sequence numbers –  Allow fast reaction to topology changes. No latency caused by

route discovery •  Make immediate route advertisement on significant changes in

routing table

•  But wait with advertising of unstable routes (damping fluctuations)

•  Disadvantages –  No sleeping nodes –  Bi-directional links required –  Overhead: most routing information never used

19 Liu

Fund. Wireless & Mobile Protocol

Link State Routing

•  Each node periodically floods status of its links (edge weight)

•  Each node re-broadcasts link state information received from its neighbor

•  Each node keeps track of link state information received from other nodes

•  Each node uses above information to determine the shortest path (Dijkstraʼs algorithm) to each destination

20 Liu

Fund. Wireless & Mobile Protocol Liu/Spring 2020 21

Link State Routing

6 3

For Node A: One hop neighbors: U={A}, V={B,C,D,E} A-B:10, A-C:5, A-D: inf. A-E:7 U={A,C}, V={B,D,E} A-B:8(C), …, A-D:14(C), … U={A,C,E},V={B,D} …, …, A-D:13(E), … U={A,C,E,B},V={D} …, …., A-D:9(B), … B: A-C-B C: A-C D: A-C-B-D E: A-E

Fund. Wireless & Mobile Protocol

Optimized Link State Routing (OLSR)

•  P. Jacquet et.al., “OLSR for Ad Hoc Networks,” Internet Drafts, IETF, 2000

•  The overhead of flooding link state information is reduced by requiring fewer nodes to forward the information

•  A broadcast from node X is only forwarded by its multipoint relays

–  Multipoint relays of node X are its neighbors such that each two-hop neighbor of X is a one-hop neighbor of at least one multipoint relay of X

•  Each node broadcasts its neighbor list in periodic beacons, so that all nodes can know their 2-hop neighbors

•  From this list each node selects a subset of one hop neighbors as multipoint relays which covers all of its 2 hop neighbors.

22 Liu

Fund. Wireless & Mobile Protocol

Optimized Link State Routing (OLSR)

•  Nodes C and E are multipoint relays of node A

B F

E H

G K

Node that has broadcast state information from A

Liu

Fund. Wireless & Mobile Protocol

Optimized Link State Routing (OLSR)

•  Nodes C and E forward information received from A

B F

E H

G K

Node that has broadcast state information from A

Liu

Fund. Wireless & Mobile Protocol

Optimized Link State Routing (OLSR)

•  Nodes E and K are multipoint relays for node H

B F

E H

G K

Node that has broadcast state information from A

Liu

Fund. Wireless & Mobile Protocol

OLSR Summary

•  OLSR floods information through the multipoint relays

•  The flooding itself is for links connecting nodes to respective multipoint relays

•  Routes used by OLSR only include multipoint relays as intermediate nodes

26 Liu

Fund. Wireless & Mobile Protocol

Pro-active vs. Re-active --- Which One Is Best?

•  Depends upon the intended application/scenario…

•  Trade-off –  Latency of route discovery

•  Proactive protocols may have lower latency since routes are maintained at all times

•  Reactive protocols may have higher latency because a route from X to Y will be found only when X attempts to send to Y

–  Overhead of route discovery/maintenance •  Reactive protocols may have lower overhead since routes are determined

only if needed

•  Proactive protocols can (but not necessarily) result in higher overhead due to continuous route updating

–  Which approach achieves a better trade-off depends on the traffic and mobility patterns

27 Liu

Fund. Wireless & Mobile Protocol

Routing Protocols for Ad Hoc Networks

•  Reactive Routing Protocols –  DSR (Dynamic Source Routing)

–  AODV (Ad-Hoc on-Demand Distance Vector)

•  Proactive Routing Protocols –  DSDV (Destination Sequenced Distance Vector)

–  OLSR (Optimal Link State Routing)

•  Hybrid Routing Protocols –  ZRP (Zone Routing Protocol)

–  TORA (Temporally-Ordered Routing Algorithm)

–  CEDAR (Core Extraction Distributed Ad-hoc Routing)

28 Liu

Fund. Wireless & Mobile Protocol

Hybrid Protocols: Zone Routing Protocol (ZRP)

•  Z. J. Haas, M. R. Pearlman, P. Samar, “The Zone Routing Protocol (ZRP) for Ad Hoc Networks,” IETF Internet Draft, July 2002.

•  Zone routing protocol combines –  Proactive protocol: which pro-actively updates network state and

maintains route regardless of whether any data traffic exists or not –  Reactive protocol: which only determines route to a destination if

there is some data to be sent to the destination

•  All nodes within hop distance at most d from a node X are said to be in the routing zone of node X

•  All nodes at hop distance exactly d are said to be peripheral nodes of node X’s routing zone

29 Liu

Fund. Wireless & Mobile Protocol

ZRP

•  Intra-zone routing: Pro-actively maintain state information for links within a short distance from any given node

–  Routes to nodes within short distance are thus maintained proactively (using, say, link state or distance vector protocol)

•  Inter-zone routing: Use a route discovery protocol for determining routes too far away nodes. Route discovery is similar to DSR with the exception that route requests are propagated via peripheral nodes.

30 Liu

Fund. Wireless & Mobile Protocol

Temporally-Ordered Routing Algorithm (TORA)

•  V. D. Park and M. S. Corson, "A Highly Adaptive Distributed Routing Algorithm for Mobile Wireless Networks (TORA)," Proceedings of IEEE INFOCOM'97, vol. 3, pp. 1405-1413, 1997.

•  Water flowing downhill toward to a destination node through a network of tubes/pipes that models the routing state of the real network.

•  Tubes/pipes represent links between nodes in the network, junctions of tubes represent the nodes, and the water in the tubes represents the packets flowing toward the destination.

•  Each node has a height with respect to the destination that is computed by the routing protocol.

•  If a tube between nodes A and B becomes blocked such that water can no longer flow through it, the height of A is set to a height greater than that of any of is remaining neighbours, such that water fill now flows back out of A (and toward the other nodes that had been routing packet to the destination via A).

31 Liu

Fund. Wireless & Mobile Protocol

TORA Height Metric •  Simply the distance from the destination node

Destination

SOURCE H=3

H=2

H=0

H=1

Liu

Fund. Wireless & Mobile Protocol

TORA

•  Destination-oriented DAG (directed acyclic graph)

–  Destination is the only node with no downstream links

•  TORA performs 3 basic functions:

–  Route creation

–  Route maintenance

–  Route erasure

33 Liu

Fund. Wireless & Mobile Protocol

TORA – Route Creation

•  For each node in the network a separate directed acyclic graph (DAG) is maintained for each destination.

•  When a node needs a route to a destination, it broadcasts a QUERY packet containing the destination address.

•  This packet travels through the network until it reaches either the destination or an intermediate node which already has a path to that destination.

•  The recipient of the QUERY packet then broadcasts an UPDATE packet listing its height with respect to the destination.

•  Each node receiving this UPDATE packet sets is height to a value greater than the height of the neighbour from which the UPDATE packet has been received

34 Liu

Fund. Wireless & Mobile Protocol

Creating Routes •  Each node maintains a

Height Hi (τi, oidi, ri, δi, i)

•  τi: time tag; •  oidi: originator ID of

link failure; (the node which defines a new reference level

•  ri: distinguisher for original and reflected reference level;

•  δi: order nodes with respect to common reference level; (height)

•  i: node ID.

A B

F (dest)

E D

Liu

Fund. Wireless & Mobile Protocol

Creating Routes

A B

F (dest)

(-,-,-,-,C)

(-,-,-,-,E)

(0,0,0,0,F)

(-,-,-,-,H)

(-,-,-,-,D)

(-,-,-,-,B) (-,-,-,-,A)

(-,-,-,-,G)

D QRY

Liu

Fund. Wireless & Mobile Protocol

Creating Routes

A B

F (dest)

(-,-,-,-,C)

(-,-,-,-,E)

(0,0,0,0,F)

(-,-,-,-,H)

(-,-,-,-,D)

(-,-,-,-,B) (-,-,-,-,A)

(-,-,-,-,G)

QRY

Liu

Fund. Wireless & Mobile Protocol

Creating Routes

QRY C

A B

F (dest)

(-,-,-,-,C)

(-,-,-,-,E)

(0,0,0,0,F)

(-,-,-,-,H)

(-,-,-,-,D)

(-,-,-,-,B) (-,-,-,-,A)

(-,-,-,-,G)

QRY

Liu

I know a path

Fund. Wireless & Mobile Protocol

Creating Routes

(0,0,0,1,H)

A B

F (dest)

(-,-,-,-,C)

(-,-,-,-,E)

(0,0,0,0,F)

(-,-,-,-,D)

(-,-,-,-,B) (-,-,-,-,A)

(-,-,-,-,G)

UPD

Liu

I know a path

Fund. Wireless & Mobile Protocol

Creating Routes

(0,0,0,1,H)

UPD C

A B

F (dest)

(-,-,-,-,C)

(0,0,0,1,E)

(0,0,0,0,F)

(0,0,0,2,D)

(-,-,-,-,B) (-,-,-,-,A)

(0,0,0,2,G)

UPD

Liu

Fund. Wireless & Mobile Protocol

Creating Routes

(0,0,0,1,E)

UPD

(0,0,0,2,D)

(0,0,0,2,G)

(0,0,0,1,H)

A B

F (dest)

(0,0,0,3,C)

(0,0,0,0,F)

(0,0,0,2,B) (0,0,0,3,A)

Liu

UPD

Fund. Wireless & Mobile Protocol

Creating Routes

A B

F (dest)

(0,0,0,0,F)

(0,0,0,1,H)

(0,0,0,1,E)

(0,0,0,2,G)

(0,0,0,2,D) (0,0,0,3,C)

(0,0,0,3,A) (0,0,0,2,B)

Liu

Fund. Wireless & Mobile Protocol

TORA – Route Creation and Maintenance

•  During the route creation and maintenance phases, nodes use the “height” metric to establish a DAG rooted at the destination.

•  Links are assigned a direction (upstream or downstream) based on the relative height metric of neighbouring nodes.

•  For node mobility when the DAG route is broken, and route maintenance is necessary to re-establish a DAG rooted at the same destination.

–  Upon failure of the last downstream link, a node without any downstream links generates a new reference level.

–  Links are reversed to reflect the change.

43 Liu

Fund. Wireless & Mobile Protocol

Maintaining Routes

44 Liu

A B

F (dest)

(0,0,0,0,F)

(0,0,0,1,H)

(0,0,0,1,E)

(0,0,0,2,G)

(0,0,0,2,D) (0,0,0,3,C)

(0,0,0,3,A) (0,0,0,2,B)

Fund. Wireless & Mobile Protocol

Maintaining Routes

(0,0,0,2,D) C

A B

F (dest)

(0,0,0,0,F)

(1,H,0,0,H)

(0,0,0,1,E)

(0,0,0,2,G)

(0,0,0,2,B)

(0,0,0,3,C)

(0,0,0,3,A)

UPD

Liu

Fund. Wireless & Mobile Protocol

Maintaining Routes

46 Liu

(1,H,0,-1,D) C

A B

F (dest)

(0,0,0,0,F)

(0,0,0,1,E)

(1,H,0,-1,G)

(0,0,0,2,B)

(0,0,0,3,C)

(0,0,0,3,A)

UPD

(1,H,0,0,H)

UPD D

Fund. Wireless & Mobile Protocol

TORA Summary •  On-demand routing •  Each node keeps routing information about adjacent (one hop)

nodes

•  A DAG (Directed Acyclic Graph) describes all discovered paths to a node (multiple routes) –  When one link fails, its neighbours reverse direction in the DAG, and

utilize another path. –  Timing of failures is important, so TORA requires synchronized clocks

(i.e. GPS)

•  Designed for a dynamic environment •  TORA is partially proactive and partially reactive

–  Reactive ⇒ route creation is initiated on demand. –  Proactive ⇒ Route maintenance is done proactively such that multiple

routing options are available in case of link failures. 47 Liu

Fund. Wireless & Mobile Protocol

So far ...

•  All nodes had identical responsibilities

•  Some schemes propose giving special responsibilities to a subset of nodes

–  Even if all nodes are physically identical

•  Core-based schemes are examples of such schemes

48 Liu

Fund. Wireless & Mobile Protocol

Core-Extraction Distributed Ad Hoc Routing (CEDAR)

•  P. Sinha, R. Sivakumar, and V. Bharghavan, "CEDAR: A Core Extraction Distributed Ad Hoc Routing Algorithm," Proceedings of IEEE INFOCOM, March 1999.

•  A subset of nodes in the network is identified as the core •  Each node in the network must be adjacent to at least one node

in the core –  Each node picks one core node as its dominator (or leader)

•  Core is determined by periodic message exchanges between each node and its neighbors –  Attempt made to keep the number of nodes in the core small

•  Each core node determines paths to nearby core nodes by means of a localized broadcast –  Each core node guaranteed to reach another core node at <=3 hops

49 Liu

Fund. Wireless & Mobile Protocol

CEDAR

A core node

Node E is the dominator for nodes D, F and K

C E

J S K

Liu

Fund. Wireless & Mobile Protocol

CEDAR: Link State Propagation

•  The distance to which the state of a link is propagated in the network is a function of

–  whether the link is stable -- state of unstable links is not propagated very far

–  whether the link bandwidth is high or low -- only state of links with high bandwidth is propagated far

•  Each core node knows the state of local links and stable high bandwidth links far away

•  Link state propagation occurs among core nodes

–  Link state information includes dominators of link end-points

51 Liu

Fund. Wireless & Mobile Protocol

CEDAR: Route Discovery

•  When a node S wants to send packets to destination D

–  Node S informs its dominator core node B

–  Node B finds a route in the core network to the core node E which is the dominator for destination D

–  This is done by means of a DSR-like route discovery process among the core nodes

•  Core nodes on the above route then build a route from S to D using locally available link state information

•  Route from S to D may or may not include core nodes

52 Liu

Fund. Wireless & Mobile Protocol

CEDAR: Core Maintenance

C E

J S K

A core node

Liu

Fund. Wireless & Mobile Protocol

Link State at Core Nodes

C E

J S K

Links that node B is aware of

Liu

Fund. Wireless & Mobile Protocol

CEDAR: Route Discovery

C E

J S K

Partial route constructed by B

Links that node C is aware of

Liu

Fund. Wireless & Mobile Protocol

CEDAR: Route Discovery

C E

J S K

Complete route -- last two hops determined by node C

Liu

Fund. Wireless & Mobile Protocol

Properties of the Core

•  Each core node has knowledge about every core node in its 3 hop neighborhood and how to reach those nodes

•  Property 1: Every core node will have at least one more core node in its 3 hop neighborhood

•  Property 2: A virtual graph consisting of core nodes and links between each pair of core nodes that are within 3 hops of each other will be connected

•  Enhancing Ad hoc Routing Protocols using CEDAR –  DSRCEDAR & AODVCEDAR

•  Involve only core nodes •  Use core broadcast for flooding among core nodes

57 Liu

Fund. Wireless & Mobile Protocol

CEDAR

•  Advantages

–  Route discovery/maintenance duties limited to a small number of core nodes

–  Link state propagation a function of link stability/quality

•  Disadvantages

–  Core nodes have to handle additional traffic, associated with route discovery and maintenance

58 Liu

Fund. Wireless & Mobile Protocol

TORA – Height

•  Each node maintains a Height Hi (τi, oidi, ri, δi, i) –  τi: time tag;

–  oidi: originator ID; –  ri: distinguisher for original and reflected reference level; –  δi: order nodes with respect to common reference level; –  i: node ID.

Xie/Fall 2012 59

Fund. Wireless & Mobile Protocol

Creating Routes

Xie/Fall 2012 60

QRY UPD C

A B

F (dest)

(-,-,-,-,C)

(-,-,-,-,E)

(0,0,0,0,F)

(-,-,-,-,H)

(-,-,-,-,D)

(-,-,-,-,B) (-,-,-,-,A)

(-,-,-,-,G)

D QRY

QRY

QRY QRY

UPD

(0,0,0,1,H)

UPD

UPD (0,0,0,1,E)

(0,0,0,2,G)

(0,0,0,2,D)

Fund. Wireless & Mobile Protocol

Maintaining Routes

Xie/Fall 2012 61

A B

F (dest)

(0,0,0,0,F)

(0,0,0,1,H)

(0,0,0,1,E)

(0,0,0,2,G)

(0,0,0,2,D)

(0,0,0,2,B)

UPD (1,D,0,0,D)

(1,D,0,-1,B)

(0,0,0,3,C)

(0,0,0,3,A) (1,D,0,-2,A)

Fund. Wireless & Mobile Protocol

Implementation Issues •  Several implementations apparently exist (see IETF)

–  only a few available publicly •  Where to implement ad hoc routing?

–  Link layer, Network layer, Application layer •  Address assignment

–  Restrict all nodes to be on the same subnet •  Routing within the subnet using ad hoc routing protocol •  Routing to/from outside the subnet using standard internet routing

–  Nodes may be given random addresses •  Routing to/from outside world becomes difficult unless Mobile IP is used

–  How to assign addresses? •  Non-random address assignment: DHCP for ad hoc network ? •  Random assignment: What happens if two nodes get the same address ?

Duplicate address detection needed

Xie/Fall 2012 62

Fund. Wireless & Mobile Protocol

Implementation Issues •  Security

–  How can I trust you to forward my packets without tampering? •  Need to be able to detect tampering

–  How do I know you are what you claim to be ? •  Authentication issues •  Hard to guarantee access to a certification authority

•  Performance –  Can we make any guarantees on performance? –  When using a non-licensed band, difficult to provide hard guarantees,

since others may be using the same band •  Only some issues have been addresses in existing

implementations •  Security issues typically ignored •  Address assignment issue also has not received sufficient

attention Xie/Fall 2012 63