X

Download Secure Network Routing Ariadne and Skipchain PowerPoint Presentation

SlidesFinder-Advertising-Design.jpg

Login   OR  Register
X


Iframe embed code :



Presentation url :

Home / Computers & Web / Computers & Web Presentations / Secure Network Routing Ariadne and Skipchain PowerPoint Presentation

Secure Network Routing Ariadne and Skipchain PowerPoint Presentation

Ppt Presentation Embed Code   Zoom Ppt Presentation

PowerPoint is the world's most popular presentation software which can let you create professional Secure Network Routing Ariadne and Skipchain powerpoint presentation easily and in no time. This helps you give your presentation on Secure Network Routing Ariadne and Skipchain in a conference, a school lecture, a business proposal, in a webinar and business and professional representations.

The uploader spent his/her valuable time to create this Secure Network Routing Ariadne and Skipchain powerpoint presentation slides, to share his/her useful content with the world. This ppt presentation uploaded by worldwideweb in Computers & Web ppt presentation category is available for free download,and can be used according to your industries like finance, marketing, education, health and many more.

About This Presentation

Slide 1 - Self-Organizing Hierarchical Routing for Scalable Ad Hoc Networking David B. Johnson Department of Computer Science Rice University dbj@cs.rice.edu Monarch Project
Slide 2 - Self-Organizing Hierarchical Routing for Scalable Ad Hoc Networking David B. Johnson Department of Computer Science Rice University dbj@cs.rice.edu Monarch Project Introduction Safari project goals: Self-organizing, adaptive network hierarchy Scalable ad hoc network routing (10s of thousands of nodes) Self-organizing higher layer network services and applications Integrated with Internet infrastructure where it exists Safari leverages and tightly integrates two areas of research: Ad hoc networking Peer-to-peer networking Builds an adaptive, proximity-based hierarchy of cells and leverages this for scalable routing and higher layer services Funded by NSF Special Projects in Networking Research (January 2004)
Slide 3 - Self-Organizing Hierarchical Routing for Scalable Ad Hoc Networking David B. Johnson Department of Computer Science Rice University dbj@cs.rice.edu Monarch Project Introduction Safari project goals: Self-organizing, adaptive network hierarchy Scalable ad hoc network routing (10s of thousands of nodes) Self-organizing higher layer network services and applications Integrated with Internet infrastructure where it exists Safari leverages and tightly integrates two areas of research: Ad hoc networking Peer-to-peer networking Builds an adaptive, proximity-based hierarchy of cells and leverages this for scalable routing and higher layer services Funded by NSF Special Projects in Networking Research (January 2004) Safari Hierarchy Self-Organization All nodes are equivalent – no specialized nodes assumed:
Slide 4 - Self-Organizing Hierarchical Routing for Scalable Ad Hoc Networking David B. Johnson Department of Computer Science Rice University dbj@cs.rice.edu Monarch Project Introduction Safari project goals: Self-organizing, adaptive network hierarchy Scalable ad hoc network routing (10s of thousands of nodes) Self-organizing higher layer network services and applications Integrated with Internet infrastructure where it exists Safari leverages and tightly integrates two areas of research: Ad hoc networking Peer-to-peer networking Builds an adaptive, proximity-based hierarchy of cells and leverages this for scalable routing and higher layer services Funded by NSF Special Projects in Networking Research (January 2004) Safari Hierarchy Self-Organization All nodes are equivalent – no specialized nodes assumed: Safari Hierarchy Self-Organization Nodes self-elect to become a buoy:
Slide 5 - Self-Organizing Hierarchical Routing for Scalable Ad Hoc Networking David B. Johnson Department of Computer Science Rice University dbj@cs.rice.edu Monarch Project Introduction Safari project goals: Self-organizing, adaptive network hierarchy Scalable ad hoc network routing (10s of thousands of nodes) Self-organizing higher layer network services and applications Integrated with Internet infrastructure where it exists Safari leverages and tightly integrates two areas of research: Ad hoc networking Peer-to-peer networking Builds an adaptive, proximity-based hierarchy of cells and leverages this for scalable routing and higher layer services Funded by NSF Special Projects in Networking Research (January 2004) Safari Hierarchy Self-Organization All nodes are equivalent – no specialized nodes assumed: Safari Hierarchy Self-Organization Nodes self-elect to become a buoy: Safari Hierarchy Self-Organization Buoy nodes send limited propagation beacon floods:
Slide 6 - Self-Organizing Hierarchical Routing for Scalable Ad Hoc Networking David B. Johnson Department of Computer Science Rice University dbj@cs.rice.edu Monarch Project Introduction Safari project goals: Self-organizing, adaptive network hierarchy Scalable ad hoc network routing (10s of thousands of nodes) Self-organizing higher layer network services and applications Integrated with Internet infrastructure where it exists Safari leverages and tightly integrates two areas of research: Ad hoc networking Peer-to-peer networking Builds an adaptive, proximity-based hierarchy of cells and leverages this for scalable routing and higher layer services Funded by NSF Special Projects in Networking Research (January 2004) Safari Hierarchy Self-Organization All nodes are equivalent – no specialized nodes assumed: Safari Hierarchy Self-Organization Nodes self-elect to become a buoy: Safari Hierarchy Self-Organization Buoy nodes send limited propagation beacon floods: Safari Hierarchy Self-Organization Other nodes associate with a buoy to form cells:
Slide 7 - Self-Organizing Hierarchical Routing for Scalable Ad Hoc Networking David B. Johnson Department of Computer Science Rice University dbj@cs.rice.edu Monarch Project Introduction Safari project goals: Self-organizing, adaptive network hierarchy Scalable ad hoc network routing (10s of thousands of nodes) Self-organizing higher layer network services and applications Integrated with Internet infrastructure where it exists Safari leverages and tightly integrates two areas of research: Ad hoc networking Peer-to-peer networking Builds an adaptive, proximity-based hierarchy of cells and leverages this for scalable routing and higher layer services Funded by NSF Special Projects in Networking Research (January 2004) Safari Hierarchy Self-Organization All nodes are equivalent – no specialized nodes assumed: Safari Hierarchy Self-Organization Nodes self-elect to become a buoy: Safari Hierarchy Self-Organization Buoy nodes send limited propagation beacon floods: Safari Hierarchy Self-Organization Other nodes associate with a buoy to form cells: Safari Hierarchy Self-Organization Buoys at one level self-elect to become buoy at next higher level:
Slide 8 - Self-Organizing Hierarchical Routing for Scalable Ad Hoc Networking David B. Johnson Department of Computer Science Rice University dbj@cs.rice.edu Monarch Project Introduction Safari project goals: Self-organizing, adaptive network hierarchy Scalable ad hoc network routing (10s of thousands of nodes) Self-organizing higher layer network services and applications Integrated with Internet infrastructure where it exists Safari leverages and tightly integrates two areas of research: Ad hoc networking Peer-to-peer networking Builds an adaptive, proximity-based hierarchy of cells and leverages this for scalable routing and higher layer services Funded by NSF Special Projects in Networking Research (January 2004) Safari Hierarchy Self-Organization All nodes are equivalent – no specialized nodes assumed: Safari Hierarchy Self-Organization Nodes self-elect to become a buoy: Safari Hierarchy Self-Organization Buoy nodes send limited propagation beacon floods: Safari Hierarchy Self-Organization Other nodes associate with a buoy to form cells: Safari Hierarchy Self-Organization Buoys at one level self-elect to become buoy at next higher level: Safari Hierarchy Self-Organization Forming cells at each higher level too:
Slide 9 - Self-Organizing Hierarchical Routing for Scalable Ad Hoc Networking David B. Johnson Department of Computer Science Rice University dbj@cs.rice.edu Monarch Project Introduction Safari project goals: Self-organizing, adaptive network hierarchy Scalable ad hoc network routing (10s of thousands of nodes) Self-organizing higher layer network services and applications Integrated with Internet infrastructure where it exists Safari leverages and tightly integrates two areas of research: Ad hoc networking Peer-to-peer networking Builds an adaptive, proximity-based hierarchy of cells and leverages this for scalable routing and higher layer services Funded by NSF Special Projects in Networking Research (January 2004) Safari Hierarchy Self-Organization All nodes are equivalent – no specialized nodes assumed: Safari Hierarchy Self-Organization Nodes self-elect to become a buoy: Safari Hierarchy Self-Organization Buoy nodes send limited propagation beacon floods: Safari Hierarchy Self-Organization Other nodes associate with a buoy to form cells: Safari Hierarchy Self-Organization Buoys at one level self-elect to become buoy at next higher level: Safari Hierarchy Self-Organization Forming cells at each higher level too: Simulation Example
Slide 10 - Self-Organizing Hierarchical Routing for Scalable Ad Hoc Networking David B. Johnson Department of Computer Science Rice University dbj@cs.rice.edu Monarch Project Introduction Safari project goals: Self-organizing, adaptive network hierarchy Scalable ad hoc network routing (10s of thousands of nodes) Self-organizing higher layer network services and applications Integrated with Internet infrastructure where it exists Safari leverages and tightly integrates two areas of research: Ad hoc networking Peer-to-peer networking Builds an adaptive, proximity-based hierarchy of cells and leverages this for scalable routing and higher layer services Funded by NSF Special Projects in Networking Research (January 2004) Safari Hierarchy Self-Organization All nodes are equivalent – no specialized nodes assumed: Safari Hierarchy Self-Organization Nodes self-elect to become a buoy: Safari Hierarchy Self-Organization Buoy nodes send limited propagation beacon floods: Safari Hierarchy Self-Organization Other nodes associate with a buoy to form cells: Safari Hierarchy Self-Organization Buoys at one level self-elect to become buoy at next higher level: Safari Hierarchy Self-Organization Forming cells at each higher level too: Simulation Example Safari Coordinates A node’s coordinates = associated cell id at each hierarchy level a d c b e A C B A.b A.a A.c A.d A.e
Slide 11 - Self-Organizing Hierarchical Routing for Scalable Ad Hoc Networking David B. Johnson Department of Computer Science Rice University dbj@cs.rice.edu Monarch Project Introduction Safari project goals: Self-organizing, adaptive network hierarchy Scalable ad hoc network routing (10s of thousands of nodes) Self-organizing higher layer network services and applications Integrated with Internet infrastructure where it exists Safari leverages and tightly integrates two areas of research: Ad hoc networking Peer-to-peer networking Builds an adaptive, proximity-based hierarchy of cells and leverages this for scalable routing and higher layer services Funded by NSF Special Projects in Networking Research (January 2004) Safari Hierarchy Self-Organization All nodes are equivalent – no specialized nodes assumed: Safari Hierarchy Self-Organization Nodes self-elect to become a buoy: Safari Hierarchy Self-Organization Buoy nodes send limited propagation beacon floods: Safari Hierarchy Self-Organization Other nodes associate with a buoy to form cells: Safari Hierarchy Self-Organization Buoys at one level self-elect to become buoy at next higher level: Safari Hierarchy Self-Organization Forming cells at each higher level too: Simulation Example Safari Coordinates A node’s coordinates = associated cell id at each hierarchy level a d c b e A C B A.b A.a A.c A.d A.e Safari Routing Overview Destination node coordinates: Stored and looked up in Distributed Hash Table (DHT) using embedded peer-to-peer system Hybrid routing protocol components: Route to destination cell following beacons (proactive routing) Incremental local repair in this path (reactive routing) Route to destination node within final cell (reactive routing) Routing table at a node: Remembers information from beacons received: Coordinates of buoy sending beacon Previous hop node from which beacon received Hop count back to the buoy Sequence number of most recent beacon from that buoy
Slide 12 - Self-Organizing Hierarchical Routing for Scalable Ad Hoc Networking David B. Johnson Department of Computer Science Rice University dbj@cs.rice.edu Monarch Project Introduction Safari project goals: Self-organizing, adaptive network hierarchy Scalable ad hoc network routing (10s of thousands of nodes) Self-organizing higher layer network services and applications Integrated with Internet infrastructure where it exists Safari leverages and tightly integrates two areas of research: Ad hoc networking Peer-to-peer networking Builds an adaptive, proximity-based hierarchy of cells and leverages this for scalable routing and higher layer services Funded by NSF Special Projects in Networking Research (January 2004) Safari Hierarchy Self-Organization All nodes are equivalent – no specialized nodes assumed: Safari Hierarchy Self-Organization Nodes self-elect to become a buoy: Safari Hierarchy Self-Organization Buoy nodes send limited propagation beacon floods: Safari Hierarchy Self-Organization Other nodes associate with a buoy to form cells: Safari Hierarchy Self-Organization Buoys at one level self-elect to become buoy at next higher level: Safari Hierarchy Self-Organization Forming cells at each higher level too: Simulation Example Safari Coordinates A node’s coordinates = associated cell id at each hierarchy level a d c b e A C B A.b A.a A.c A.d A.e Safari Routing Overview Destination node coordinates: Stored and looked up in Distributed Hash Table (DHT) using embedded peer-to-peer system Hybrid routing protocol components: Route to destination cell following beacons (proactive routing) Incremental local repair in this path (reactive routing) Route to destination node within final cell (reactive routing) Routing table at a node: Remembers information from beacons received: Coordinates of buoy sending beacon Previous hop node from which beacon received Hop count back to the buoy Sequence number of most recent beacon from that buoy Proactive Inter-cell Routing Range of beacons from a buoy node: Nodes in the cell associated with that buoy Nodes a few hops away, giving them a chance to join that cell Nodes in the containing cell one level up in the hierarchy Routing table lookup algorithm: Nodes outside the cell hear the beacons: Reasons described above Wireless propagation allows nearby nodes to hear too Longest common prefix matching (similar to Internet !) : Compare your own coordinates to each entry in routing table As soon as packet comes to node with more detailed table entry, packet starts following lower in routing hierarchy Packets are routed toward buoys, not through buoys!
Slide 13 - Self-Organizing Hierarchical Routing for Scalable Ad Hoc Networking David B. Johnson Department of Computer Science Rice University dbj@cs.rice.edu Monarch Project Introduction Safari project goals: Self-organizing, adaptive network hierarchy Scalable ad hoc network routing (10s of thousands of nodes) Self-organizing higher layer network services and applications Integrated with Internet infrastructure where it exists Safari leverages and tightly integrates two areas of research: Ad hoc networking Peer-to-peer networking Builds an adaptive, proximity-based hierarchy of cells and leverages this for scalable routing and higher layer services Funded by NSF Special Projects in Networking Research (January 2004) Safari Hierarchy Self-Organization All nodes are equivalent – no specialized nodes assumed: Safari Hierarchy Self-Organization Nodes self-elect to become a buoy: Safari Hierarchy Self-Organization Buoy nodes send limited propagation beacon floods: Safari Hierarchy Self-Organization Other nodes associate with a buoy to form cells: Safari Hierarchy Self-Organization Buoys at one level self-elect to become buoy at next higher level: Safari Hierarchy Self-Organization Forming cells at each higher level too: Simulation Example Safari Coordinates A node’s coordinates = associated cell id at each hierarchy level a d c b e A C B A.b A.a A.c A.d A.e Safari Routing Overview Destination node coordinates: Stored and looked up in Distributed Hash Table (DHT) using embedded peer-to-peer system Hybrid routing protocol components: Route to destination cell following beacons (proactive routing) Incremental local repair in this path (reactive routing) Route to destination node within final cell (reactive routing) Routing table at a node: Remembers information from beacons received: Coordinates of buoy sending beacon Previous hop node from which beacon received Hop count back to the buoy Sequence number of most recent beacon from that buoy Proactive Inter-cell Routing Range of beacons from a buoy node: Nodes in the cell associated with that buoy Nodes a few hops away, giving them a chance to join that cell Nodes in the containing cell one level up in the hierarchy Routing table lookup algorithm: Nodes outside the cell hear the beacons: Reasons described above Wireless propagation allows nearby nodes to hear too Longest common prefix matching (similar to Internet !) : Compare your own coordinates to each entry in routing table As soon as packet comes to node with more detailed table entry, packet starts following lower in routing hierarchy Packets are routed toward buoys, not through buoys! Routing Example Source node S is sending a packet to destination node D: S D
Slide 14 - Self-Organizing Hierarchical Routing for Scalable Ad Hoc Networking David B. Johnson Department of Computer Science Rice University dbj@cs.rice.edu Monarch Project Introduction Safari project goals: Self-organizing, adaptive network hierarchy Scalable ad hoc network routing (10s of thousands of nodes) Self-organizing higher layer network services and applications Integrated with Internet infrastructure where it exists Safari leverages and tightly integrates two areas of research: Ad hoc networking Peer-to-peer networking Builds an adaptive, proximity-based hierarchy of cells and leverages this for scalable routing and higher layer services Funded by NSF Special Projects in Networking Research (January 2004) Safari Hierarchy Self-Organization All nodes are equivalent – no specialized nodes assumed: Safari Hierarchy Self-Organization Nodes self-elect to become a buoy: Safari Hierarchy Self-Organization Buoy nodes send limited propagation beacon floods: Safari Hierarchy Self-Organization Other nodes associate with a buoy to form cells: Safari Hierarchy Self-Organization Buoys at one level self-elect to become buoy at next higher level: Safari Hierarchy Self-Organization Forming cells at each higher level too: Simulation Example Safari Coordinates A node’s coordinates = associated cell id at each hierarchy level a d c b e A C B A.b A.a A.c A.d A.e Safari Routing Overview Destination node coordinates: Stored and looked up in Distributed Hash Table (DHT) using embedded peer-to-peer system Hybrid routing protocol components: Route to destination cell following beacons (proactive routing) Incremental local repair in this path (reactive routing) Route to destination node within final cell (reactive routing) Routing table at a node: Remembers information from beacons received: Coordinates of buoy sending beacon Previous hop node from which beacon received Hop count back to the buoy Sequence number of most recent beacon from that buoy Proactive Inter-cell Routing Range of beacons from a buoy node: Nodes in the cell associated with that buoy Nodes a few hops away, giving them a chance to join that cell Nodes in the containing cell one level up in the hierarchy Routing table lookup algorithm: Nodes outside the cell hear the beacons: Reasons described above Wireless propagation allows nearby nodes to hear too Longest common prefix matching (similar to Internet !) : Compare your own coordinates to each entry in routing table As soon as packet comes to node with more detailed table entry, packet starts following lower in routing hierarchy Packets are routed toward buoys, not through buoys! Routing Example Source node S is sending a packet to destination node D: S D Routing Example Follow beacon path toward level 3 cell in which D is located: S D
Slide 15 - Self-Organizing Hierarchical Routing for Scalable Ad Hoc Networking David B. Johnson Department of Computer Science Rice University dbj@cs.rice.edu Monarch Project Introduction Safari project goals: Self-organizing, adaptive network hierarchy Scalable ad hoc network routing (10s of thousands of nodes) Self-organizing higher layer network services and applications Integrated with Internet infrastructure where it exists Safari leverages and tightly integrates two areas of research: Ad hoc networking Peer-to-peer networking Builds an adaptive, proximity-based hierarchy of cells and leverages this for scalable routing and higher layer services Funded by NSF Special Projects in Networking Research (January 2004) Safari Hierarchy Self-Organization All nodes are equivalent – no specialized nodes assumed: Safari Hierarchy Self-Organization Nodes self-elect to become a buoy: Safari Hierarchy Self-Organization Buoy nodes send limited propagation beacon floods: Safari Hierarchy Self-Organization Other nodes associate with a buoy to form cells: Safari Hierarchy Self-Organization Buoys at one level self-elect to become buoy at next higher level: Safari Hierarchy Self-Organization Forming cells at each higher level too: Simulation Example Safari Coordinates A node’s coordinates = associated cell id at each hierarchy level a d c b e A C B A.b A.a A.c A.d A.e Safari Routing Overview Destination node coordinates: Stored and looked up in Distributed Hash Table (DHT) using embedded peer-to-peer system Hybrid routing protocol components: Route to destination cell following beacons (proactive routing) Incremental local repair in this path (reactive routing) Route to destination node within final cell (reactive routing) Routing table at a node: Remembers information from beacons received: Coordinates of buoy sending beacon Previous hop node from which beacon received Hop count back to the buoy Sequence number of most recent beacon from that buoy Proactive Inter-cell Routing Range of beacons from a buoy node: Nodes in the cell associated with that buoy Nodes a few hops away, giving them a chance to join that cell Nodes in the containing cell one level up in the hierarchy Routing table lookup algorithm: Nodes outside the cell hear the beacons: Reasons described above Wireless propagation allows nearby nodes to hear too Longest common prefix matching (similar to Internet !) : Compare your own coordinates to each entry in routing table As soon as packet comes to node with more detailed table entry, packet starts following lower in routing hierarchy Packets are routed toward buoys, not through buoys! Routing Example Source node S is sending a packet to destination node D: S D Routing Example Follow beacon path toward level 3 cell in which D is located: S D Routing Example Follow beacon path toward level 2 cell in which D is located: S D
Slide 16 - Self-Organizing Hierarchical Routing for Scalable Ad Hoc Networking David B. Johnson Department of Computer Science Rice University dbj@cs.rice.edu Monarch Project Introduction Safari project goals: Self-organizing, adaptive network hierarchy Scalable ad hoc network routing (10s of thousands of nodes) Self-organizing higher layer network services and applications Integrated with Internet infrastructure where it exists Safari leverages and tightly integrates two areas of research: Ad hoc networking Peer-to-peer networking Builds an adaptive, proximity-based hierarchy of cells and leverages this for scalable routing and higher layer services Funded by NSF Special Projects in Networking Research (January 2004) Safari Hierarchy Self-Organization All nodes are equivalent – no specialized nodes assumed: Safari Hierarchy Self-Organization Nodes self-elect to become a buoy: Safari Hierarchy Self-Organization Buoy nodes send limited propagation beacon floods: Safari Hierarchy Self-Organization Other nodes associate with a buoy to form cells: Safari Hierarchy Self-Organization Buoys at one level self-elect to become buoy at next higher level: Safari Hierarchy Self-Organization Forming cells at each higher level too: Simulation Example Safari Coordinates A node’s coordinates = associated cell id at each hierarchy level a d c b e A C B A.b A.a A.c A.d A.e Safari Routing Overview Destination node coordinates: Stored and looked up in Distributed Hash Table (DHT) using embedded peer-to-peer system Hybrid routing protocol components: Route to destination cell following beacons (proactive routing) Incremental local repair in this path (reactive routing) Route to destination node within final cell (reactive routing) Routing table at a node: Remembers information from beacons received: Coordinates of buoy sending beacon Previous hop node from which beacon received Hop count back to the buoy Sequence number of most recent beacon from that buoy Proactive Inter-cell Routing Range of beacons from a buoy node: Nodes in the cell associated with that buoy Nodes a few hops away, giving them a chance to join that cell Nodes in the containing cell one level up in the hierarchy Routing table lookup algorithm: Nodes outside the cell hear the beacons: Reasons described above Wireless propagation allows nearby nodes to hear too Longest common prefix matching (similar to Internet !) : Compare your own coordinates to each entry in routing table As soon as packet comes to node with more detailed table entry, packet starts following lower in routing hierarchy Packets are routed toward buoys, not through buoys! Routing Example Source node S is sending a packet to destination node D: S D Routing Example Follow beacon path toward level 3 cell in which D is located: S D Routing Example Follow beacon path toward level 2 cell in which D is located: S D Routing Example Follow beacon path toward level 1 cell in which D is located: S D
Slide 17 - Self-Organizing Hierarchical Routing for Scalable Ad Hoc Networking David B. Johnson Department of Computer Science Rice University dbj@cs.rice.edu Monarch Project Introduction Safari project goals: Self-organizing, adaptive network hierarchy Scalable ad hoc network routing (10s of thousands of nodes) Self-organizing higher layer network services and applications Integrated with Internet infrastructure where it exists Safari leverages and tightly integrates two areas of research: Ad hoc networking Peer-to-peer networking Builds an adaptive, proximity-based hierarchy of cells and leverages this for scalable routing and higher layer services Funded by NSF Special Projects in Networking Research (January 2004) Safari Hierarchy Self-Organization All nodes are equivalent – no specialized nodes assumed: Safari Hierarchy Self-Organization Nodes self-elect to become a buoy: Safari Hierarchy Self-Organization Buoy nodes send limited propagation beacon floods: Safari Hierarchy Self-Organization Other nodes associate with a buoy to form cells: Safari Hierarchy Self-Organization Buoys at one level self-elect to become buoy at next higher level: Safari Hierarchy Self-Organization Forming cells at each higher level too: Simulation Example Safari Coordinates A node’s coordinates = associated cell id at each hierarchy level a d c b e A C B A.b A.a A.c A.d A.e Safari Routing Overview Destination node coordinates: Stored and looked up in Distributed Hash Table (DHT) using embedded peer-to-peer system Hybrid routing protocol components: Route to destination cell following beacons (proactive routing) Incremental local repair in this path (reactive routing) Route to destination node within final cell (reactive routing) Routing table at a node: Remembers information from beacons received: Coordinates of buoy sending beacon Previous hop node from which beacon received Hop count back to the buoy Sequence number of most recent beacon from that buoy Proactive Inter-cell Routing Range of beacons from a buoy node: Nodes in the cell associated with that buoy Nodes a few hops away, giving them a chance to join that cell Nodes in the containing cell one level up in the hierarchy Routing table lookup algorithm: Nodes outside the cell hear the beacons: Reasons described above Wireless propagation allows nearby nodes to hear too Longest common prefix matching (similar to Internet !) : Compare your own coordinates to each entry in routing table As soon as packet comes to node with more detailed table entry, packet starts following lower in routing hierarchy Packets are routed toward buoys, not through buoys! Routing Example Source node S is sending a packet to destination node D: S D Routing Example Follow beacon path toward level 3 cell in which D is located: S D Routing Example Follow beacon path toward level 2 cell in which D is located: S D Routing Example Follow beacon path toward level 1 cell in which D is located: S D Reactive Intra-cell Routing Dynamic Source Routing protocol (DSR): Discovers routes only as needed, on demand (Route Discovery) Detects when links being used for routing are broken, on demand only as they are used (Route Maintenance) Very low overhead, scalable to mobility and traffic needs Zero overhead until new route is needed Using DSR in Safari routing: DSR originally designed for small or medium sized networks Safari intended to scale to much larger sizes Safari uses DSR only within destination fundamental cell Size of fundamental cells created by Safari balance two things: Small enough for very easy efficient reactive routing Large enough to minimize when nodes move to new cells
Slide 18 - Self-Organizing Hierarchical Routing for Scalable Ad Hoc Networking David B. Johnson Department of Computer Science Rice University dbj@cs.rice.edu Monarch Project Introduction Safari project goals: Self-organizing, adaptive network hierarchy Scalable ad hoc network routing (10s of thousands of nodes) Self-organizing higher layer network services and applications Integrated with Internet infrastructure where it exists Safari leverages and tightly integrates two areas of research: Ad hoc networking Peer-to-peer networking Builds an adaptive, proximity-based hierarchy of cells and leverages this for scalable routing and higher layer services Funded by NSF Special Projects in Networking Research (January 2004) Safari Hierarchy Self-Organization All nodes are equivalent – no specialized nodes assumed: Safari Hierarchy Self-Organization Nodes self-elect to become a buoy: Safari Hierarchy Self-Organization Buoy nodes send limited propagation beacon floods: Safari Hierarchy Self-Organization Other nodes associate with a buoy to form cells: Safari Hierarchy Self-Organization Buoys at one level self-elect to become buoy at next higher level: Safari Hierarchy Self-Organization Forming cells at each higher level too: Simulation Example Safari Coordinates A node’s coordinates = associated cell id at each hierarchy level a d c b e A C B A.b A.a A.c A.d A.e Safari Routing Overview Destination node coordinates: Stored and looked up in Distributed Hash Table (DHT) using embedded peer-to-peer system Hybrid routing protocol components: Route to destination cell following beacons (proactive routing) Incremental local repair in this path (reactive routing) Route to destination node within final cell (reactive routing) Routing table at a node: Remembers information from beacons received: Coordinates of buoy sending beacon Previous hop node from which beacon received Hop count back to the buoy Sequence number of most recent beacon from that buoy Proactive Inter-cell Routing Range of beacons from a buoy node: Nodes in the cell associated with that buoy Nodes a few hops away, giving them a chance to join that cell Nodes in the containing cell one level up in the hierarchy Routing table lookup algorithm: Nodes outside the cell hear the beacons: Reasons described above Wireless propagation allows nearby nodes to hear too Longest common prefix matching (similar to Internet !) : Compare your own coordinates to each entry in routing table As soon as packet comes to node with more detailed table entry, packet starts following lower in routing hierarchy Packets are routed toward buoys, not through buoys! Routing Example Source node S is sending a packet to destination node D: S D Routing Example Follow beacon path toward level 3 cell in which D is located: S D Routing Example Follow beacon path toward level 2 cell in which D is located: S D Routing Example Follow beacon path toward level 1 cell in which D is located: S D Reactive Intra-cell Routing Dynamic Source Routing protocol (DSR): Discovers routes only as needed, on demand (Route Discovery) Detects when links being used for routing are broken, on demand only as they are used (Route Maintenance) Very low overhead, scalable to mobility and traffic needs Zero overhead until new route is needed Using DSR in Safari routing: DSR originally designed for small or medium sized networks Safari intended to scale to much larger sizes Safari uses DSR only within destination fundamental cell Size of fundamental cells created by Safari balance two things: Small enough for very easy efficient reactive routing Large enough to minimize when nodes move to new cells Routing Example On-demand DSR routing to destination node D: S D
Slide 19 - Self-Organizing Hierarchical Routing for Scalable Ad Hoc Networking David B. Johnson Department of Computer Science Rice University dbj@cs.rice.edu Monarch Project Introduction Safari project goals: Self-organizing, adaptive network hierarchy Scalable ad hoc network routing (10s of thousands of nodes) Self-organizing higher layer network services and applications Integrated with Internet infrastructure where it exists Safari leverages and tightly integrates two areas of research: Ad hoc networking Peer-to-peer networking Builds an adaptive, proximity-based hierarchy of cells and leverages this for scalable routing and higher layer services Funded by NSF Special Projects in Networking Research (January 2004) Safari Hierarchy Self-Organization All nodes are equivalent – no specialized nodes assumed: Safari Hierarchy Self-Organization Nodes self-elect to become a buoy: Safari Hierarchy Self-Organization Buoy nodes send limited propagation beacon floods: Safari Hierarchy Self-Organization Other nodes associate with a buoy to form cells: Safari Hierarchy Self-Organization Buoys at one level self-elect to become buoy at next higher level: Safari Hierarchy Self-Organization Forming cells at each higher level too: Simulation Example Safari Coordinates A node’s coordinates = associated cell id at each hierarchy level a d c b e A C B A.b A.a A.c A.d A.e Safari Routing Overview Destination node coordinates: Stored and looked up in Distributed Hash Table (DHT) using embedded peer-to-peer system Hybrid routing protocol components: Route to destination cell following beacons (proactive routing) Incremental local repair in this path (reactive routing) Route to destination node within final cell (reactive routing) Routing table at a node: Remembers information from beacons received: Coordinates of buoy sending beacon Previous hop node from which beacon received Hop count back to the buoy Sequence number of most recent beacon from that buoy Proactive Inter-cell Routing Range of beacons from a buoy node: Nodes in the cell associated with that buoy Nodes a few hops away, giving them a chance to join that cell Nodes in the containing cell one level up in the hierarchy Routing table lookup algorithm: Nodes outside the cell hear the beacons: Reasons described above Wireless propagation allows nearby nodes to hear too Longest common prefix matching (similar to Internet !) : Compare your own coordinates to each entry in routing table As soon as packet comes to node with more detailed table entry, packet starts following lower in routing hierarchy Packets are routed toward buoys, not through buoys! Routing Example Source node S is sending a packet to destination node D: S D Routing Example Follow beacon path toward level 3 cell in which D is located: S D Routing Example Follow beacon path toward level 2 cell in which D is located: S D Routing Example Follow beacon path toward level 1 cell in which D is located: S D Reactive Intra-cell Routing Dynamic Source Routing protocol (DSR): Discovers routes only as needed, on demand (Route Discovery) Detects when links being used for routing are broken, on demand only as they are used (Route Maintenance) Very low overhead, scalable to mobility and traffic needs Zero overhead until new route is needed Using DSR in Safari routing: DSR originally designed for small or medium sized networks Safari intended to scale to much larger sizes Safari uses DSR only within destination fundamental cell Size of fundamental cells created by Safari balance two things: Small enough for very easy efficient reactive routing Large enough to minimize when nodes move to new cells Routing Example On-demand DSR routing to destination node D: S D Reactive Inter-cell Route Repair Beacons are sent only periodically: Long interval between beacons important for low overhead The higher the level in hierarchy, the less frequent the beacon Following beacon reverse path may fail if nodes have moved Safari local route repair in the beacon paths: Limited-hop on-demand Route Discovery Flood flows “downhill” with limited “uphill” allowed “Altitude” is  prefix length matched, sequence #, hop count  Result reestablishes new path as if original beacon path Buoy node Increasing “altitude” with hops away from buoy A node has moved away from buoy
Slide 20 - Self-Organizing Hierarchical Routing for Scalable Ad Hoc Networking David B. Johnson Department of Computer Science Rice University dbj@cs.rice.edu Monarch Project Introduction Safari project goals: Self-organizing, adaptive network hierarchy Scalable ad hoc network routing (10s of thousands of nodes) Self-organizing higher layer network services and applications Integrated with Internet infrastructure where it exists Safari leverages and tightly integrates two areas of research: Ad hoc networking Peer-to-peer networking Builds an adaptive, proximity-based hierarchy of cells and leverages this for scalable routing and higher layer services Funded by NSF Special Projects in Networking Research (January 2004) Safari Hierarchy Self-Organization All nodes are equivalent – no specialized nodes assumed: Safari Hierarchy Self-Organization Nodes self-elect to become a buoy: Safari Hierarchy Self-Organization Buoy nodes send limited propagation beacon floods: Safari Hierarchy Self-Organization Other nodes associate with a buoy to form cells: Safari Hierarchy Self-Organization Buoys at one level self-elect to become buoy at next higher level: Safari Hierarchy Self-Organization Forming cells at each higher level too: Simulation Example Safari Coordinates A node’s coordinates = associated cell id at each hierarchy level a d c b e A C B A.b A.a A.c A.d A.e Safari Routing Overview Destination node coordinates: Stored and looked up in Distributed Hash Table (DHT) using embedded peer-to-peer system Hybrid routing protocol components: Route to destination cell following beacons (proactive routing) Incremental local repair in this path (reactive routing) Route to destination node within final cell (reactive routing) Routing table at a node: Remembers information from beacons received: Coordinates of buoy sending beacon Previous hop node from which beacon received Hop count back to the buoy Sequence number of most recent beacon from that buoy Proactive Inter-cell Routing Range of beacons from a buoy node: Nodes in the cell associated with that buoy Nodes a few hops away, giving them a chance to join that cell Nodes in the containing cell one level up in the hierarchy Routing table lookup algorithm: Nodes outside the cell hear the beacons: Reasons described above Wireless propagation allows nearby nodes to hear too Longest common prefix matching (similar to Internet !) : Compare your own coordinates to each entry in routing table As soon as packet comes to node with more detailed table entry, packet starts following lower in routing hierarchy Packets are routed toward buoys, not through buoys! Routing Example Source node S is sending a packet to destination node D: S D Routing Example Follow beacon path toward level 3 cell in which D is located: S D Routing Example Follow beacon path toward level 2 cell in which D is located: S D Routing Example Follow beacon path toward level 1 cell in which D is located: S D Reactive Intra-cell Routing Dynamic Source Routing protocol (DSR): Discovers routes only as needed, on demand (Route Discovery) Detects when links being used for routing are broken, on demand only as they are used (Route Maintenance) Very low overhead, scalable to mobility and traffic needs Zero overhead until new route is needed Using DSR in Safari routing: DSR originally designed for small or medium sized networks Safari intended to scale to much larger sizes Safari uses DSR only within destination fundamental cell Size of fundamental cells created by Safari balance two things: Small enough for very easy efficient reactive routing Large enough to minimize when nodes move to new cells Routing Example On-demand DSR routing to destination node D: S D Reactive Inter-cell Route Repair Beacons are sent only periodically: Long interval between beacons important for low overhead The higher the level in hierarchy, the less frequent the beacon Following beacon reverse path may fail if nodes have moved Safari local route repair in the beacon paths: Limited-hop on-demand Route Discovery Flood flows “downhill” with limited “uphill” allowed “Altitude” is  prefix length matched, sequence #, hop count  Result reestablishes new path as if original beacon path Buoy node Increasing “altitude” with hops away from buoy A node has moved away from buoy Simulation Evaluation Simulated using ns-2, includes detailed physical model IEEE 802.11 at 2 Mbps, nominal range 250 m Studied scale from 50 to 1000 nodes: Randomly distributed in space Density maintained equivalent to 50 nodes in 10001000 m Studied percentage of nodes being mobile from 0% to 100% Moving with Random Waypoint model, average 5 m/s Data traffic is Constant Bit Rate (CBR): Flows with randomly chosen source and destination 4 packets/second, 64 bytes/packet Metrics shown: Packet Delivery Ratio: percentage of packets delivered Overhead: individual transmissions of routing packets
Slide 21 - Self-Organizing Hierarchical Routing for Scalable Ad Hoc Networking David B. Johnson Department of Computer Science Rice University dbj@cs.rice.edu Monarch Project Introduction Safari project goals: Self-organizing, adaptive network hierarchy Scalable ad hoc network routing (10s of thousands of nodes) Self-organizing higher layer network services and applications Integrated with Internet infrastructure where it exists Safari leverages and tightly integrates two areas of research: Ad hoc networking Peer-to-peer networking Builds an adaptive, proximity-based hierarchy of cells and leverages this for scalable routing and higher layer services Funded by NSF Special Projects in Networking Research (January 2004) Safari Hierarchy Self-Organization All nodes are equivalent – no specialized nodes assumed: Safari Hierarchy Self-Organization Nodes self-elect to become a buoy: Safari Hierarchy Self-Organization Buoy nodes send limited propagation beacon floods: Safari Hierarchy Self-Organization Other nodes associate with a buoy to form cells: Safari Hierarchy Self-Organization Buoys at one level self-elect to become buoy at next higher level: Safari Hierarchy Self-Organization Forming cells at each higher level too: Simulation Example Safari Coordinates A node’s coordinates = associated cell id at each hierarchy level a d c b e A C B A.b A.a A.c A.d A.e Safari Routing Overview Destination node coordinates: Stored and looked up in Distributed Hash Table (DHT) using embedded peer-to-peer system Hybrid routing protocol components: Route to destination cell following beacons (proactive routing) Incremental local repair in this path (reactive routing) Route to destination node within final cell (reactive routing) Routing table at a node: Remembers information from beacons received: Coordinates of buoy sending beacon Previous hop node from which beacon received Hop count back to the buoy Sequence number of most recent beacon from that buoy Proactive Inter-cell Routing Range of beacons from a buoy node: Nodes in the cell associated with that buoy Nodes a few hops away, giving them a chance to join that cell Nodes in the containing cell one level up in the hierarchy Routing table lookup algorithm: Nodes outside the cell hear the beacons: Reasons described above Wireless propagation allows nearby nodes to hear too Longest common prefix matching (similar to Internet !) : Compare your own coordinates to each entry in routing table As soon as packet comes to node with more detailed table entry, packet starts following lower in routing hierarchy Packets are routed toward buoys, not through buoys! Routing Example Source node S is sending a packet to destination node D: S D Routing Example Follow beacon path toward level 3 cell in which D is located: S D Routing Example Follow beacon path toward level 2 cell in which D is located: S D Routing Example Follow beacon path toward level 1 cell in which D is located: S D Reactive Intra-cell Routing Dynamic Source Routing protocol (DSR): Discovers routes only as needed, on demand (Route Discovery) Detects when links being used for routing are broken, on demand only as they are used (Route Maintenance) Very low overhead, scalable to mobility and traffic needs Zero overhead until new route is needed Using DSR in Safari routing: DSR originally designed for small or medium sized networks Safari intended to scale to much larger sizes Safari uses DSR only within destination fundamental cell Size of fundamental cells created by Safari balance two things: Small enough for very easy efficient reactive routing Large enough to minimize when nodes move to new cells Routing Example On-demand DSR routing to destination node D: S D Reactive Inter-cell Route Repair Beacons are sent only periodically: Long interval between beacons important for low overhead The higher the level in hierarchy, the less frequent the beacon Following beacon reverse path may fail if nodes have moved Safari local route repair in the beacon paths: Limited-hop on-demand Route Discovery Flood flows “downhill” with limited “uphill” allowed “Altitude” is  prefix length matched, sequence #, hop count  Result reestablishes new path as if original beacon path Buoy node Increasing “altitude” with hops away from buoy A node has moved away from buoy Simulation Evaluation Simulated using ns-2, includes detailed physical model IEEE 802.11 at 2 Mbps, nominal range 250 m Studied scale from 50 to 1000 nodes: Randomly distributed in space Density maintained equivalent to 50 nodes in 10001000 m Studied percentage of nodes being mobile from 0% to 100% Moving with Random Waypoint model, average 5 m/s Data traffic is Constant Bit Rate (CBR): Flows with randomly chosen source and destination 4 packets/second, 64 bytes/packet Metrics shown: Packet Delivery Ratio: percentage of packets delivered Overhead: individual transmissions of routing packets PDR vs. Number of Nodes
Slide 22 - Self-Organizing Hierarchical Routing for Scalable Ad Hoc Networking David B. Johnson Department of Computer Science Rice University dbj@cs.rice.edu Monarch Project Introduction Safari project goals: Self-organizing, adaptive network hierarchy Scalable ad hoc network routing (10s of thousands of nodes) Self-organizing higher layer network services and applications Integrated with Internet infrastructure where it exists Safari leverages and tightly integrates two areas of research: Ad hoc networking Peer-to-peer networking Builds an adaptive, proximity-based hierarchy of cells and leverages this for scalable routing and higher layer services Funded by NSF Special Projects in Networking Research (January 2004) Safari Hierarchy Self-Organization All nodes are equivalent – no specialized nodes assumed: Safari Hierarchy Self-Organization Nodes self-elect to become a buoy: Safari Hierarchy Self-Organization Buoy nodes send limited propagation beacon floods: Safari Hierarchy Self-Organization Other nodes associate with a buoy to form cells: Safari Hierarchy Self-Organization Buoys at one level self-elect to become buoy at next higher level: Safari Hierarchy Self-Organization Forming cells at each higher level too: Simulation Example Safari Coordinates A node’s coordinates = associated cell id at each hierarchy level a d c b e A C B A.b A.a A.c A.d A.e Safari Routing Overview Destination node coordinates: Stored and looked up in Distributed Hash Table (DHT) using embedded peer-to-peer system Hybrid routing protocol components: Route to destination cell following beacons (proactive routing) Incremental local repair in this path (reactive routing) Route to destination node within final cell (reactive routing) Routing table at a node: Remembers information from beacons received: Coordinates of buoy sending beacon Previous hop node from which beacon received Hop count back to the buoy Sequence number of most recent beacon from that buoy Proactive Inter-cell Routing Range of beacons from a buoy node: Nodes in the cell associated with that buoy Nodes a few hops away, giving them a chance to join that cell Nodes in the containing cell one level up in the hierarchy Routing table lookup algorithm: Nodes outside the cell hear the beacons: Reasons described above Wireless propagation allows nearby nodes to hear too Longest common prefix matching (similar to Internet !) : Compare your own coordinates to each entry in routing table As soon as packet comes to node with more detailed table entry, packet starts following lower in routing hierarchy Packets are routed toward buoys, not through buoys! Routing Example Source node S is sending a packet to destination node D: S D Routing Example Follow beacon path toward level 3 cell in which D is located: S D Routing Example Follow beacon path toward level 2 cell in which D is located: S D Routing Example Follow beacon path toward level 1 cell in which D is located: S D Reactive Intra-cell Routing Dynamic Source Routing protocol (DSR): Discovers routes only as needed, on demand (Route Discovery) Detects when links being used for routing are broken, on demand only as they are used (Route Maintenance) Very low overhead, scalable to mobility and traffic needs Zero overhead until new route is needed Using DSR in Safari routing: DSR originally designed for small or medium sized networks Safari intended to scale to much larger sizes Safari uses DSR only within destination fundamental cell Size of fundamental cells created by Safari balance two things: Small enough for very easy efficient reactive routing Large enough to minimize when nodes move to new cells Routing Example On-demand DSR routing to destination node D: S D Reactive Inter-cell Route Repair Beacons are sent only periodically: Long interval between beacons important for low overhead The higher the level in hierarchy, the less frequent the beacon Following beacon reverse path may fail if nodes have moved Safari local route repair in the beacon paths: Limited-hop on-demand Route Discovery Flood flows “downhill” with limited “uphill” allowed “Altitude” is  prefix length matched, sequence #, hop count  Result reestablishes new path as if original beacon path Buoy node Increasing “altitude” with hops away from buoy A node has moved away from buoy Simulation Evaluation Simulated using ns-2, includes detailed physical model IEEE 802.11 at 2 Mbps, nominal range 250 m Studied scale from 50 to 1000 nodes: Randomly distributed in space Density maintained equivalent to 50 nodes in 10001000 m Studied percentage of nodes being mobile from 0% to 100% Moving with Random Waypoint model, average 5 m/s Data traffic is Constant Bit Rate (CBR): Flows with randomly chosen source and destination 4 packets/second, 64 bytes/packet Metrics shown: Packet Delivery Ratio: percentage of packets delivered Overhead: individual transmissions of routing packets PDR vs. Number of Nodes PDR vs. Percentage of Mobile Nodes (1000 nodes total)
Slide 23 - Self-Organizing Hierarchical Routing for Scalable Ad Hoc Networking David B. Johnson Department of Computer Science Rice University dbj@cs.rice.edu Monarch Project Introduction Safari project goals: Self-organizing, adaptive network hierarchy Scalable ad hoc network routing (10s of thousands of nodes) Self-organizing higher layer network services and applications Integrated with Internet infrastructure where it exists Safari leverages and tightly integrates two areas of research: Ad hoc networking Peer-to-peer networking Builds an adaptive, proximity-based hierarchy of cells and leverages this for scalable routing and higher layer services Funded by NSF Special Projects in Networking Research (January 2004) Safari Hierarchy Self-Organization All nodes are equivalent – no specialized nodes assumed: Safari Hierarchy Self-Organization Nodes self-elect to become a buoy: Safari Hierarchy Self-Organization Buoy nodes send limited propagation beacon floods: Safari Hierarchy Self-Organization Other nodes associate with a buoy to form cells: Safari Hierarchy Self-Organization Buoys at one level self-elect to become buoy at next higher level: Safari Hierarchy Self-Organization Forming cells at each higher level too: Simulation Example Safari Coordinates A node’s coordinates = associated cell id at each hierarchy level a d c b e A C B A.b A.a A.c A.d A.e Safari Routing Overview Destination node coordinates: Stored and looked up in Distributed Hash Table (DHT) using embedded peer-to-peer system Hybrid routing protocol components: Route to destination cell following beacons (proactive routing) Incremental local repair in this path (reactive routing) Route to destination node within final cell (reactive routing) Routing table at a node: Remembers information from beacons received: Coordinates of buoy sending beacon Previous hop node from which beacon received Hop count back to the buoy Sequence number of most recent beacon from that buoy Proactive Inter-cell Routing Range of beacons from a buoy node: Nodes in the cell associated with that buoy Nodes a few hops away, giving them a chance to join that cell Nodes in the containing cell one level up in the hierarchy Routing table lookup algorithm: Nodes outside the cell hear the beacons: Reasons described above Wireless propagation allows nearby nodes to hear too Longest common prefix matching (similar to Internet !) : Compare your own coordinates to each entry in routing table As soon as packet comes to node with more detailed table entry, packet starts following lower in routing hierarchy Packets are routed toward buoys, not through buoys! Routing Example Source node S is sending a packet to destination node D: S D Routing Example Follow beacon path toward level 3 cell in which D is located: S D Routing Example Follow beacon path toward level 2 cell in which D is located: S D Routing Example Follow beacon path toward level 1 cell in which D is located: S D Reactive Intra-cell Routing Dynamic Source Routing protocol (DSR): Discovers routes only as needed, on demand (Route Discovery) Detects when links being used for routing are broken, on demand only as they are used (Route Maintenance) Very low overhead, scalable to mobility and traffic needs Zero overhead until new route is needed Using DSR in Safari routing: DSR originally designed for small or medium sized networks Safari intended to scale to much larger sizes Safari uses DSR only within destination fundamental cell Size of fundamental cells created by Safari balance two things: Small enough for very easy efficient reactive routing Large enough to minimize when nodes move to new cells Routing Example On-demand DSR routing to destination node D: S D Reactive Inter-cell Route Repair Beacons are sent only periodically: Long interval between beacons important for low overhead The higher the level in hierarchy, the less frequent the beacon Following beacon reverse path may fail if nodes have moved Safari local route repair in the beacon paths: Limited-hop on-demand Route Discovery Flood flows “downhill” with limited “uphill” allowed “Altitude” is  prefix length matched, sequence #, hop count  Result reestablishes new path as if original beacon path Buoy node Increasing “altitude” with hops away from buoy A node has moved away from buoy Simulation Evaluation Simulated using ns-2, includes detailed physical model IEEE 802.11 at 2 Mbps, nominal range 250 m Studied scale from 50 to 1000 nodes: Randomly distributed in space Density maintained equivalent to 50 nodes in 10001000 m Studied percentage of nodes being mobile from 0% to 100% Moving with Random Waypoint model, average 5 m/s Data traffic is Constant Bit Rate (CBR): Flows with randomly chosen source and destination 4 packets/second, 64 bytes/packet Metrics shown: Packet Delivery Ratio: percentage of packets delivered Overhead: individual transmissions of routing packets PDR vs. Number of Nodes PDR vs. Percentage of Mobile Nodes (1000 nodes total) Overhead vs. Number of Nodes
Slide 24 - Self-Organizing Hierarchical Routing for Scalable Ad Hoc Networking David B. Johnson Department of Computer Science Rice University dbj@cs.rice.edu Monarch Project Introduction Safari project goals: Self-organizing, adaptive network hierarchy Scalable ad hoc network routing (10s of thousands of nodes) Self-organizing higher layer network services and applications Integrated with Internet infrastructure where it exists Safari leverages and tightly integrates two areas of research: Ad hoc networking Peer-to-peer networking Builds an adaptive, proximity-based hierarchy of cells and leverages this for scalable routing and higher layer services Funded by NSF Special Projects in Networking Research (January 2004) Safari Hierarchy Self-Organization All nodes are equivalent – no specialized nodes assumed: Safari Hierarchy Self-Organization Nodes self-elect to become a buoy: Safari Hierarchy Self-Organization Buoy nodes send limited propagation beacon floods: Safari Hierarchy Self-Organization Other nodes associate with a buoy to form cells: Safari Hierarchy Self-Organization Buoys at one level self-elect to become buoy at next higher level: Safari Hierarchy Self-Organization Forming cells at each higher level too: Simulation Example Safari Coordinates A node’s coordinates = associated cell id at each hierarchy level a d c b e A C B A.b A.a A.c A.d A.e Safari Routing Overview Destination node coordinates: Stored and looked up in Distributed Hash Table (DHT) using embedded peer-to-peer system Hybrid routing protocol components: Route to destination cell following beacons (proactive routing) Incremental local repair in this path (reactive routing) Route to destination node within final cell (reactive routing) Routing table at a node: Remembers information from beacons received: Coordinates of buoy sending beacon Previous hop node from which beacon received Hop count back to the buoy Sequence number of most recent beacon from that buoy Proactive Inter-cell Routing Range of beacons from a buoy node: Nodes in the cell associated with that buoy Nodes a few hops away, giving them a chance to join that cell Nodes in the containing cell one level up in the hierarchy Routing table lookup algorithm: Nodes outside the cell hear the beacons: Reasons described above Wireless propagation allows nearby nodes to hear too Longest common prefix matching (similar to Internet !) : Compare your own coordinates to each entry in routing table As soon as packet comes to node with more detailed table entry, packet starts following lower in routing hierarchy Packets are routed toward buoys, not through buoys! Routing Example Source node S is sending a packet to destination node D: S D Routing Example Follow beacon path toward level 3 cell in which D is located: S D Routing Example Follow beacon path toward level 2 cell in which D is located: S D Routing Example Follow beacon path toward level 1 cell in which D is located: S D Reactive Intra-cell Routing Dynamic Source Routing protocol (DSR): Discovers routes only as needed, on demand (Route Discovery) Detects when links being used for routing are broken, on demand only as they are used (Route Maintenance) Very low overhead, scalable to mobility and traffic needs Zero overhead until new route is needed Using DSR in Safari routing: DSR originally designed for small or medium sized networks Safari intended to scale to much larger sizes Safari uses DSR only within destination fundamental cell Size of fundamental cells created by Safari balance two things: Small enough for very easy efficient reactive routing Large enough to minimize when nodes move to new cells Routing Example On-demand DSR routing to destination node D: S D Reactive Inter-cell Route Repair Beacons are sent only periodically: Long interval between beacons important for low overhead The higher the level in hierarchy, the less frequent the beacon Following beacon reverse path may fail if nodes have moved Safari local route repair in the beacon paths: Limited-hop on-demand Route Discovery Flood flows “downhill” with limited “uphill” allowed “Altitude” is  prefix length matched, sequence #, hop count  Result reestablishes new path as if original beacon path Buoy node Increasing “altitude” with hops away from buoy A node has moved away from buoy Simulation Evaluation Simulated using ns-2, includes detailed physical model IEEE 802.11 at 2 Mbps, nominal range 250 m Studied scale from 50 to 1000 nodes: Randomly distributed in space Density maintained equivalent to 50 nodes in 10001000 m Studied percentage of nodes being mobile from 0% to 100% Moving with Random Waypoint model, average 5 m/s Data traffic is Constant Bit Rate (CBR): Flows with randomly chosen source and destination 4 packets/second, 64 bytes/packet Metrics shown: Packet Delivery Ratio: percentage of packets delivered Overhead: individual transmissions of routing packets PDR vs. Number of Nodes PDR vs. Percentage of Mobile Nodes (1000 nodes total) Overhead vs. Number of Nodes Overhead vs. Percentage of Mobile Nodes (1000 nodes total)
Slide 25 - Self-Organizing Hierarchical Routing for Scalable Ad Hoc Networking David B. Johnson Department of Computer Science Rice University dbj@cs.rice.edu Monarch Project Introduction Safari project goals: Self-organizing, adaptive network hierarchy Scalable ad hoc network routing (10s of thousands of nodes) Self-organizing higher layer network services and applications Integrated with Internet infrastructure where it exists Safari leverages and tightly integrates two areas of research: Ad hoc networking Peer-to-peer networking Builds an adaptive, proximity-based hierarchy of cells and leverages this for scalable routing and higher layer services Funded by NSF Special Projects in Networking Research (January 2004) Safari Hierarchy Self-Organization All nodes are equivalent – no specialized nodes assumed: Safari Hierarchy Self-Organization Nodes self-elect to become a buoy: Safari Hierarchy Self-Organization Buoy nodes send limited propagation beacon floods: Safari Hierarchy Self-Organization Other nodes associate with a buoy to form cells: Safari Hierarchy Self-Organization Buoys at one level self-elect to become buoy at next higher level: Safari Hierarchy Self-Organization Forming cells at each higher level too: Simulation Example Safari Coordinates A node’s coordinates = associated cell id at each hierarchy level a d c b e A C B A.b A.a A.c A.d A.e Safari Routing Overview Destination node coordinates: Stored and looked up in Distributed Hash Table (DHT) using embedded peer-to-peer system Hybrid routing protocol components: Route to destination cell following beacons (proactive routing) Incremental local repair in this path (reactive routing) Route to destination node within final cell (reactive routing) Routing table at a node: Remembers information from beacons received: Coordinates of buoy sending beacon Previous hop node from which beacon received Hop count back to the buoy Sequence number of most recent beacon from that buoy Proactive Inter-cell Routing Range of beacons from a buoy node: Nodes in the cell associated with that buoy Nodes a few hops away, giving them a chance to join that cell Nodes in the containing cell one level up in the hierarchy Routing table lookup algorithm: Nodes outside the cell hear the beacons: Reasons described above Wireless propagation allows nearby nodes to hear too Longest common prefix matching (similar to Internet !) : Compare your own coordinates to each entry in routing table As soon as packet comes to node with more detailed table entry, packet starts following lower in routing hierarchy Packets are routed toward buoys, not through buoys! Routing Example Source node S is sending a packet to destination node D: S D Routing Example Follow beacon path toward level 3 cell in which D is located: S D Routing Example Follow beacon path toward level 2 cell in which D is located: S D Routing Example Follow beacon path toward level 1 cell in which D is located: S D Reactive Intra-cell Routing Dynamic Source Routing protocol (DSR): Discovers routes only as needed, on demand (Route Discovery) Detects when links being used for routing are broken, on demand only as they are used (Route Maintenance) Very low overhead, scalable to mobility and traffic needs Zero overhead until new route is needed Using DSR in Safari routing: DSR originally designed for small or medium sized networks Safari intended to scale to much larger sizes Safari uses DSR only within destination fundamental cell Size of fundamental cells created by Safari balance two things: Small enough for very easy efficient reactive routing Large enough to minimize when nodes move to new cells Routing Example On-demand DSR routing to destination node D: S D Reactive Inter-cell Route Repair Beacons are sent only periodically: Long interval between beacons important for low overhead The higher the level in hierarchy, the less frequent the beacon Following beacon reverse path may fail if nodes have moved Safari local route repair in the beacon paths: Limited-hop on-demand Route Discovery Flood flows “downhill” with limited “uphill” allowed “Altitude” is  prefix length matched, sequence #, hop count  Result reestablishes new path as if original beacon path Buoy node Increasing “altitude” with hops away from buoy A node has moved away from buoy Simulation Evaluation Simulated using ns-2, includes detailed physical model IEEE 802.11 at 2 Mbps, nominal range 250 m Studied scale from 50 to 1000 nodes: Randomly distributed in space Density maintained equivalent to 50 nodes in 10001000 m Studied percentage of nodes being mobile from 0% to 100% Moving with Random Waypoint model, average 5 m/s Data traffic is Constant Bit Rate (CBR): Flows with randomly chosen source and destination 4 packets/second, 64 bytes/packet Metrics shown: Packet Delivery Ratio: percentage of packets delivered Overhead: individual transmissions of routing packets PDR vs. Number of Nodes PDR vs. Percentage of Mobile Nodes (1000 nodes total) Overhead vs. Number of Nodes Overhead vs. Percentage of Mobile Nodes (1000 nodes total) Conclusion Safari is highly scalable and provides a basis for services: Forms an adaptive, proximity-based hierarchy of cells PDR and routing overhead change little with scale or mobility Performance studied through both simulation and analysis Ongoing and future work: Further optimization and evaluation of beaconing, cell membership, routing, local repair Interconnection to traditional Internet infrastructure Higher layer services exploiting the hierarchy and P2P Testbed and experimentation
 

Frequently Asked Questions

> About SlidesFinder?

Slidesfinder is a website that allows users to upload and share their PowerPoint presentations online. It provides a platform for individuals and businesses to share their ideas and knowledge through presentations, and for others to view and download these presentations for educational or professional purposes.
Slidesfinder offers a wide range of presentation topics and categories, including business, education, science, technology, health, and more. Users can also search for presentations using keywords, tags, or by category. The website provides tools to create professional presentations with rich media, animations, and graphics.



One of the key features of Slidesfinder is its user-friendly interface, which allows users to easily upload, view, and share presentations. Users can also embed their presentations in their websites or blogs using the website's embed code feature.
Slidesfinder also offers premium services, such as the ability to create private presentations and to download presentations in high-quality formats. However, the basic features of Slidesfinder are free to use, making it accessible to anyone who wants to share their ideas and knowledge through presentations.

> How do I register with SlidesFinder?

Go to registration page (you can see signup link on top of website page) https://www.slidesfinder.com/signup . If you have facebook/gmail account them just click on SIGN IN WITH FACEBOOK OR SIGN IN WITH GOOGLE button, by this you will be a registered member of slidesfinder without filling any form, required detail automatically will be fatch from your account. If you do not a Facebook account, then click on "Signup". Fill all required fields and you will be a registered member of slidesfinder.

> Is slidesfinder account confirmation is mandatory?

Yes it is mandetory to active your account to login.

> Do I need to signup/login on SlidesFinder before uploading a PowerPoint presentation?

Yes, you need to login with your account before uploading presentation. Your username will be displayed on your uploaded presentation. Your registered email id is needed for sending your stats of uploaded presentation.

Slidesfinder is a sharing website for PowerPoint presentations search and share. Find your interest in the form of powerpoint presentations on slidesfinder and save your valuable time . On Slidesfinder you get presentations from our huge library of professional ppt presentations. We believe in making your search INFORMATIVE and FUN. Find your best ppt presentation from a pool of PowerPoint presentations stacked under important industry categories like business & management, heath & Wellness,eduction & training etc. We provide unique informative PowerPoint presentation for marketers, presenters and educationists. These professional PowerPoint presentations are uploaded by professionals from across numerous industry segments.These ppt presentations are available for FREE download.

Not just finding your interest, but facilitate you broadcast your interest. We have created this platform for easy sharing of PowerPoint presentations, ensuring that these presentations get maximum exposure. Create your slidesfinder account and upload PowerPoint presentations for free, share on social media platforms and BUILD YOUR CROWD WITH PRESENTATION !!

The Great Buddha says, "Share your knowledge.It’s a way to achieve immortality"! So, start sharing knowledge and we are here to make that immortal !!

© 2013-2024 SlidesFinder. All rights reserved.

Re-productivity of content are not allowed. Without prior written permission from author, commercial use of any content is illegal.