Seminar Ppt1

DIFFERENT APPROACHES IN ROUTERS FOR ROUTING METHODS.

SUBMITTED BY: S.PRAVEEN KUMAR

ROUTING • Routing is the act of moving information across an internetwork from a source to a destination. • Routing is often contrasted with bridging. • The primary difference between the two is that bridging occurs at Layer 2 (the link layer) of the OSI reference model. • Routing involves two basic activities: determining optimal routing paths and transporting information groups (typically called packets) through an internetwork.

• Although packet switching is relatively straightforward, path determination can be very complex. • Destination/next hop associations tell a router that a particular destination can be reached optimally by sending the packet to a particular router representing the “next hop” on the way to the final destination. • When a router receives an incoming packet, it checks the destination address and attempts to associate this address with a next hop.

Beacon Vector Routing: Scalable Point-to-Point Routing in Wireless Sensornets

• Most existing protocols only support basic many-toone or one-to-many routing primitives (e.g., Directed diffusion, TAG, …) • More point-to-point routing protocols have recently been proposed – Applications: Pursuer-evader game, spatial queries, reactive tasking, multi-dimensional range queries, data centric storage, …

Design Goals • Develop & implement a point-point routing protocol: – That is simple – minimal complexity – That makes minimal assumptions about radio quality, presence of GPS, … – Use TinyOS tree construction protocol

Packet Forwarding • Basic Algorithm: 1. Try Greedy Forwarding - Largest Distance 2. Else try fallback - Send towards destination’s closest beacon 3. Else Do Scoped Flood - Flood the packet using the distance from the beacon as scope

Greedy Forwarding

• Moving towards a beacon is better than moving away from one. • Object might be on the other side of a beacon • Head towards beacons that are closer than us first • If there is a tie, start moving away

Greedy Forwarding

Network Maintenance • Beacons periodically flood

the network • Use a Sequence Number • Nodes periodically check number of beacons • If there are too many, suppress yourself • If there are not enough, elect yourself

D-STAR Routing • Two Routing Methods • Site Routing • •Whereyou want to talk • –Specific System/Gateway/Cityand Port • User Routing • •Whoyou want to talk • –Specific User

GATEWAY SITE ROUTING •Connection over the Network •One way connection •Not a continuous connection •Local hams on both ends can hear conversation •Cannot join in until they program their radio

VIRTUAL RING ROUTING • Virtual Ring Routing (VRR), a new network routing protocol that occupies a unique point in the design space. • VRR is inspired by overlay routing algorithms in Distributed Hash Tables (DHTs) but it does not rely on an underlying network routing protocol. It is implemented directly on top of the link layer.

• VRR is also unique because it never floods the network and uses only location independent identifiers to route. • Nodes are organized into a virtual ring ordered by their identifiers and each node maintains a small number of routing paths to its neighbors in the ring. • The nodes along a path store the next hop towards each path endpoint in a routing table. • VRR uses random unsigned integers to identify nodes, and organizes the nodes into a virtual ring in order of increasing identifier (with wrapping around zero).

• To maintain the integrity of the virtual ring with node and link failures, each node maintains a virtual neighbor set (or vset). • Each node also maintains a physical neighbor set (or pset) with the identifiers of nodes that it can communicate with at the link layer. • VRR provides not only point-to-point network routing between two nodes but also a distributed hash table (DHT).

IP ROUTING • Once upon a time, there were three separate "physical" LANs, each with their own addressing scheme, protocol, and format. And host "A" was very sad,because it was unable to communicate with its dearest love in the world, host"iii" which was on a different LAN network

ROUTERS • The networks decided to connect with a couple routers. Each router is like a translator capable of participating in either of the two networks to which it is connected.

Introduce two routers. Each router is on two physical networks— each router has an address and can send and receive packets on both Networks. Need a consistent naming scheme to identify hosts on the various networks.

IP ADDRESS • The first step in allowing all the of the different hosts to communicate with each other is to introduce a uniform naming scheme so that every host can have a well defined name. • Give every host an IP address which identifies the network and host. Every host has a "physical" name, such as "A" which is used by its LAN, as 3 well as a global standard IP name such as "1.1". • The left part of the IP address identifies the network and the right part identifies the host on that network.

Give each host and router an IP address for each of its connections. The IP addresses are consistent across all the networks. Each IP address identifies the host and the network it is

IP Datagram

• Now define the "IP Datagram" — a standard packet format. The IP datagram is forwarded hop by hop inside the packets of each LAN. At each hop, the IP datagram is unpacked from the physical packet that transported it.

IP datagrams use IP addresses. The datagram always keeps the IP address of its ultimate destination. Hosts and routers forward the IP datagram one hop at a time towards its destination. On each hop, the datagram is encapuslated inside a physical network packet with a physical network address. The datagram may need to be “fragmented” if it is too big to fit in

Low Level • The IP datagram and IP addressing and routing

schemes are umbrella standards that all the hosts and routers use. At a small scale, hosts and routers use their physical networks to send packets hop by hop. IP is the overall, universal standard. • Hosts and routers use the IP address for everything, and mostly just the network part of the IP address. The physical address of the final destination is only computed on the very last hop.

• The original IP datagram may be fragmented along the

way, but it always keeps the IP address of its final destination. All routing decisions are in terms of IP addresses. • The datagram is defragmented only when it reaches the final destination (a design decision which helps keep the routers simple). • Each host and router is only concerned with what the "next hop" is for a particular IP address. The overall design tries to keep the hosts simple, leaving the complexity for the routers. So for example, the top-left 1.1 host would keep a "next hop" table which looked like..

Every host and router needs another (much smaller and simpler) table which maps IP addresses to physical address for things on its physical network

Routers have the same sort of "next hop" table, but theirs are typically more complex since they know about paths for farther away networks. The routing tables are partly determined by the administrator for the router, and partly the routers have their own complex protocol they use dynamically to exchange

TOPOLOGY ROUTING • Structured peer-to-peer (p2p) overlay networks like CAN, Chord, Pastry and provide a self-organizing substrate for large-scale p2p applications. • They can implement a scalable, fault-tolerant distributed hash table (DHT), in which any item can be located within a small number of routing hops using a small per-node routing table.

• In Pastry, keys and nodeIds are 128 bits in length and can be thought of as a sequence of digits in base 16. • Tapestry is very similar to Pastry but differs in its approach to mapping keys to nodes in the sparsely populated id space, and in how it manages replication. • In Tapestry, there is no leaf set and neighboring nodes in the namespace are not aware of each other. • Chord uses a circular 160 bit id space. Unlike Pastry, Chord forwards messages only clockwise in the circular id space.

• Instead of the prefix-based routing table in Pastry, Chord nodes maintain a finger table, consisting of nodeIds and IP addresses of up to 160 other live nodes

• proximity routing, the overlay is constructed without regard for the physical network topology. But when routing a message, there are potentially several nodes in the routing table closer to the message’s key in the id space. • Proximity neighbor selection constructs a topology-aware overlay. But instead of biasing the node Id assignment, the idea is to choose routing table entries to refer to the topologically closest node among all nodes with node Id in the desired portion of the id space.

THANK YOU