New User Special Price Expires in

Let's log you in.

Sign in with Facebook


Don't have a StudySoup account? Create one here!


Create a StudySoup account

Be part of our community, it's free to join!

Sign up with Facebook


Create your account
By creating an account you agree to StudySoup's terms and conditions and privacy policy

Already have a StudySoup account? Login here

Special Topics Algorithms

by: Melissa Metz

Special Topics Algorithms EECS 800

Marketplace > Kansas > Elect Engr & Computer Science > EECS 800 > Special Topics Algorithms
Melissa Metz
GPA 3.74


Almost Ready


These notes were just uploaded, and will be ready to view shortly.

Purchase these notes here, or revisit this page.

Either way, we'll remind you when they're ready :)

Preview These Notes for FREE

Get a free preview of these Notes, just enter your email below.

Unlock Preview
Unlock Preview

Preview these materials now for free

Why put in your email? Get access to more of this material and other relevant free materials for your school

View Preview

About this Document

Class Notes
25 ?




Popular in Course

Popular in Elect Engr & Computer Science

This 17 page Class Notes was uploaded by Melissa Metz on Monday September 7, 2015. The Class Notes belongs to EECS 800 at Kansas taught by Staff in Fall. Since its upload, it has received 23 views. For similar materials see /class/186794/eecs-800-kansas in Elect Engr & Computer Science at Kansas.

Similar to EECS 800 at KU

Popular in Elect Engr & Computer Science


Reviews for Special Topics Algorithms


Report this Material


What is Karma?


Karma is the currency of StudySoup.

You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 09/07/15
Mitigating Routing Misbehavior in Mobile Ad Hoc Networks S Marti T Giuli K Lai and M Baker Mitigating routing misbehavior in mobile ad hoc networks in The 6th ACM International Conference on Mobile Computing and Networking August 2000 Student Lecture by Rag39avendra Ananthapadmanabhan EECS 800 Survivable Networking Department of Electrical Engineering and Computer Science University of Kansas OUTLINE Introduction Ad hoc networks Routing in ad hoc networks Types of nodes in ad hoc network Misbehaving nodes and their solution Assumptions and DSR Techniques followed to mitigate the misbehavior Methodology and metrics Simulation results Conclusion and future work Satisfying quot R s in Survivability References Introduction Ad hoc networks Routing in ad hoc networks Maximize throughput by routing through all available nodes More participating nodes more aggregate bandwidth Shorter the routing path smaller the network partition Types of nodes in the network Overloaded lacks CPU cycles bufferspace available BW Selfish unwilling tospend CPU cycles battery life Malicious drops packets Broken software fault preventing fonvarding Misbehaving nodes and their solutions Decrease in throughput if 1040 of nodes misbehave Degradation of 1632 in throughput Solutions a priori trust relationships Trust relationships built outside of thecontext of the network Problems can happen due to authentication Anothersolution is to isolate these misbehaving nodes But this adds significant complexity to the routing protocol Techniques Watchdog identifies misbehaving nodes Path rater avoids routing through these nodes Assumptions and DSR Physical layer characteristics Bidirectional links between the node s ln accordancewith the 80211 and MACAW Interfaces supports promiscuous mode of operation Lucent Technologies WaveLAN have this capacity DSR Dynamic Source Routing Protocol OnDemand source routing protocol Route Discovery through ROUTE REQUEST packet Route Maintenance through ROUTE ERROR packet DSR Mechanism Techniques followed to mitigate the misbehavior Watchdog implementation A can overhear B and tell whether B has forwarded the packet Buffer is maintained for recently 39sent packets The overheard packet is compared with the sent packet If there is a match discard the packet If the packet stays till a timeout increment the failure tally for the node If tally exceeds a threshold declare the node as misbehaving Techniques followed to mitigate the misbehavior Weaknesses for Watchdog This will not detect the misbehaving node during Ambiguouscollisions Collusion Receiver collisions False misbehavior Techniques followed to mitigate the misbehavior Ambiguous collisions A packet collision can occur at A while listening to does not knowwhether B has fonlvarded the packet Due to this uncertainty should not immediately accuse B Instead watch B over a period of time and decide later Collusion Multiple nodes can collude and present sophisticated attack Problem currently studied in CMU Techniques folovved to mitigate the maisloehavor Receiver collision Node A cannot tell whether C receives the packet If collision occurs at cannot detect the collision B can leave A none the wiser doesn t retransmit selfishness B can wait to make a collision Misbehavin g node Not an Overloaded or selfish node Techniques folovved to mitigate the misbehavor False misbehavior Nodes falsely report other nodes as misbehaving Node A can report B as misbehaving when A isthe culprit This will be detected receives ACKs from through and wonders why it receivesACKs if B drops the packets If A drops ACKs to hide from B detects this and informs Techniques followed to mitigate the misbehavior 39 Path rater Combines knowledge of misbehaving nodes to pick the route Each node maintains a rating for every other node Calculate a path metric by averaging the node ratings This gives a comparison of overall reliability of different paths Ratings Algorithm A neutral rating of 05 is assigned to a node discovered Source rates itself with 10 to ensure shortest path Increment the rating 39of nodes in active path by 001 every 200ms Decrement the rating by 005 in case of broken link Assign quot100quot for misbehaving node When calculating metric negative value indicates misbehaving path Increase the negative rating to nonnegative value after long timeout Methodology and metrics NS 2 simulator 670 x 670 m 50 wireless nodes Movement patterns include random waypoint model Communication pattern includes CBR flow 10 to 40 misbehaving nodes were included Metrics Throughput Overhead due to RREQ RREP RERR Watchdog false positives Simulation results WD PR SRR everything on and everything off Network Throughput O and 60 sec pause time Same at 0 misbehaving nodes and diverges later Throughput increase of 27 in both scenarios Interdependency between WD and PR PD cannot function with no WD If either WDPD are off then it becomes a normal network E s i E E E E 5 E u m u r u 1 u Simulation results 39M39Jrii w Pi n E aila MEICH HtL39N SREICIFF I HMFFjF Rn ERv IQF I LIEAil ms kafRiEIF 39l u l1 Ci E4 Fliclu39 39J uilhl m39i ruin 0 sec pause time rhmxmmhjpsmranscn quotIra um 5an I39liDN S Re a a ALIGM F MN ERR3F l axisCHM quotN EMDF I zx rJFFmALFF RaEIFF a c i C4 leu39 l nilh im min 60 sec pause time Simulation results Routing Overhead again everything on and off Graph WD only curve to study the overhead due to notifications Greatest effect only when SRR is on Overhead increase of 123 when SRR is activated on PR WD incurs very small overhead This behavior is not affected even by adding misbehaving nodes Overhead generally corresponds to battery usage in PDAs But net increase of throughput helps the network


Buy Material

Are you sure you want to buy this material for

25 Karma

Buy Material

BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.


You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

Why people love StudySoup

Jim McGreen Ohio University

"Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

Janice Dongeun University of Washington

"I used the money I made selling my notes & study guides to pay for spring break in Olympia, Washington...which was Sweet!"

Steve Martinelli UC Los Angeles

"There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

Parker Thompson 500 Startups

"It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

Become an Elite Notetaker and start selling your notes online!

Refund Policy


All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email


StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here:

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.