No network information is needed

A packet is sent by a source node to every one of its neighbors

At each node and incoming packet is retransmitted on all outgoing links except for the link on which it arrived

Each packet has hop count field.  The count is set at the source to the longest minimum-hop path through the network.  At each node this count is decremented.  When the count reaches zero, the packet is discarded.  This prevents the number of copies of the packet from growing without bound

A number of copies will arrive at the destination.  Using the packet identity (source and sequence number), the destination discard all the copies except for one.

Even if a link breaks or nodes fail a packet will always get through if at least one path exists between the source and teh destination.

Used in military networks

To provide routing information

Disadvantage - High traffic load

Least Cost Routs

Source Independence

Next hop forwarding does not depend on the packet's orginial source or on the path the packet has taken

The next hop is determined mainly by the destination

Because forwarding does not use source information, only the destination address needs to be extracted from a packet.

Least Cost Route

Distributed route computation

Each packet switch computes its routing table locally.

A packet switch periodically sends routing information across the network to neighbors.

Each router shares its knowledge about the entire network with its neighbors.

Each router periodicall sends its knowledge about the network to its neighbors.

1.  If advertised destination is not in the routing table, the router should add the advertised information to the table.

2.  If the advertised destination is in the routing table

a) If the next-hop field is the same, the router replace the entry in the table with the advertised one.

b) If the next-hop field is not the same

i) If the advertised hop count is smaller than the one in the table, the router should replace the entry in the table with the new one adding one to the cost.

ii) If the advertised hop count is not smaller, the router should do nothing.

It is suitable for smaller internets

Each node(router or host that implements RIP) exchange information with its neighboring nodes

Algorithm:

Each node x maintains three vectors

Link cost

Distance Vector

Next-hop vector

Periodically (every 30 secs) each node exchanges its deistance vector with all of its neighbors.

RIP is designed to operate incremetally by updating its routing table after receipt of any individual distance vector.  The following rules are implemented:

If the incoming distance vector includes a new destination network, this information is added to the routing table.

If the node receives a route with a smaller delay metric to a destination, it replace the existing route.

If the node receives an update vector from router R and the node currently has one or more entries in its routing table for which R is the next hop, then all of these entries are updated to reflect the new information from R.

Least Cost Route

Dijkstra's Algorithm

For centralized configuration: the routing server obtains status information from all packet switches periodically, computes the best route and feeds this information back to the packet switches

For the Distributed configuration:

Each node periodically advertise its set of link costs to all other nodes of which it is aware, of.  Every node receiveing an update packet must acknowledge it to the sender.

The softwar to compute the entries for a routing table represent the netwrok as a graph.

Finds the distance along a shortest path from a single source node to each of the other nodes in the graph; a next-hop routing table is contructed.

Dijkstra's algorithm allows each edge (link) to be assigned a nonnegative value called weight, and defines the distance between two nodes to be the sum of the weights along a path between the nodes.

Link-State Routing:

Whenever there is a significant change:

a router is initatialized, it determines the link cost on each of its network interfaces

a link cost increases or decreases substantially

a new link is created

an existing link becomes unavailable

The router advertise its set of link costs to all other routers in the internet topology using flooding

Because each router receives the link costs of all routers in the configuration, each router can construct the topology of the entire configuration and then calculate the shortest path to each destination network using Dijkstra's algorithm.