Introduction osi reference Model via tcp/ip reference Model

1. 
   OSI Reference Model via TCP/IP Reference Model
   
   1. 
      OSI (Open System Interconnection) Reference Model.
      

Host A Router Router Host B

1. 
   Physical Layer
   

The data link layer takes a raw transmission facility and transforms it into a line that appears free of undetected transmission errors to the network layer. This task is accomplished by using data & acknowledgment frames and error detection algorithms (like code Humming).

3. 
   Network Layer
   

3. 
   Transport Layer
   

2. 
   TCP/IP Reference Model
   

1. 
   Internet Layer
   

2. 
   Transport Layer
   

Our major interest is in deference’s at the network layer, them we will focus on:

~ The OSI model supports both connectionless & connection-oriented communication in the network layer , but only connection-oriented communication in the transport layer.

~ The TCP\IP model has only one mode in the network layer – connectionless, but supports both modes in transport layer, giving the user a choice. This choice is especially important for simple request-response protocols.

2. 
   Routing
   

So far we have had a surface glance on two major reference models in network: OSI & TCP/IP. In this course we are mainly interested in one particular layer – the network layer, which is also divided into two approaches:

1. 
   connectionless type
   
2. 
   connection – oriented type
   

The connection – oriented type refers to such protocols as ATM, telephony and so on. This type of connection doesn’t fit the hardware described below (CISCO Router 2600/11), thus it will not be discussed here.

2. 
   Connectionless Routing (general).
   

The independent packets of connectionless organization are called datagrams (in analogy with telegrams). In that kind of organization the routing table telling which outgoing line to use for each possible destination router is build in every router. Each datagram must contain the full destination address. When the packet comes, the router looks up the outgoing line to use in the routing table and sends the packet on its way. Also , the establishment and release of network or transport layer connections do not require any special work on the part of the routers.

1. 
   Routing Algorithms.
   

The routing algorithm is that part of the network layer software responsible for deciding which output line an incoming packet should be transmitted on. If the subnet uses datagrams internally , this decision must be made anew for every arriving data packet since the best route may have changed since last time. In the subnet using virtual circuits such decision is made ones per session.

Routing algorithms can be grouped into two major classes: nonadaptive and adaptive.

1. 
   Nonadaptive algorithms do not base their routing decisions on measurements or estimates of the current traffic and topology. Instead , the choice of the route to use to get from I to J is computed in advance , of-line, and downloaded to the routers when the network is booted. This procedure is sometimes called static routing.
   
2. 
   Adaptive algorithms ,in contrast, change their routing decisions to reflect changes in the topology , and usually the traffic as well. Adaptive algorithms differ in where the get their information ,when they change the routes , and what metric is used for optimization . They are also called dynamic.
   

2. 
   The Optimality Principle
   

In the next three sections, we will look at three static routing algorithms, subsequently we will move to dynamic ones.

3. 
   Shortest Path Routing
   

There are several algorithms for computing shortest path between two nodes of a graph. One of them due to Dijkstra.

4. 
   Flooding
   

One such measure is to have a hop counter in the header of each packet, which is decremented at each hop, with the packet being discarded when the counter reaches zero. Ideally, the hop counter is initialized to the length of the path from source to destination. If the sender does not no the path length, it can initialize the counter to the worst case, the full diameter of the subnet.

An alternative technique is to keep track of which packets have been flooded, to avoid sending then out a second time. To achieve this goal the source router put a sequence number in each packet it receives from its hosts. Then each router needs a list per source router telling which sequence numbers originating at that source have already been seen. Any incoming packet that is on the list is not flooded. To prevent list form growing, each list should be augmented by a counter, k, meaning that all sequence numbers through k have been seen.

A variation of flooding named selective flooding is slightly more practical. In this algorithm the routers do not send every incoming packet out on every line, but only on those going approximately in the right direction.(there is usually little point in sending a westbound packet on an eastbound line unless the topology is extremely peculiar).

Flooding algorithms are rarely used, mostly with distributed systems or systems with tremendous robustness requirements at any instance.

5. 
   Flow-Based Routing
   

In some networks, the mean data flow between each pair of nodes is relatively stable and predictable. Under conditions in which the average traffic from i to j is known in advance and to a reasonable approximation ,constant in time, it is possible to analyze the flows mathematically to optimize the routing.

The idea behind the analysis is that for a given line, if the capacity and average flow are known, it is possible to compute the mean packet delay on that line from queuing theory. From the mean delays on all the lines , it is straightforward to calculate a flow-weighted average to get the mean packet delay for the whole subnet. The routing problem then reduces to finding the routing algorithm that produces the minimum average delay for the subnet.

This technology demands certain information in advance. First the subnet topology, second the traffic matrix, third the capacity matrix and finally a routing algorithm (further explanation look at the same reference as above).

6. 
   Distance Vector Routing
   

The distance vector routing algorithm is sometimes called by other names including Bellman-Ford or Ford-Fulkerson. It was the original ARPANET routing algorithm and was also used in the Internet under the name RIP and in early versions of DECnet and Novell’s IPX. AppleTalk & CISCO routers use improved distance vector protocols.

In that algorithm each router maintains a routing table indexed by and containing one entry for each router in the subnet. This entry contains two parts: the preferred outgoing line to use for that destination and an estimate of the time or distance to that destination. The metric used might be number of hops, time delay in milliseconds, total number of packets queued along the path or something similar.

The router is assumed to know the “distance” to each of its neighbors. In the hops metric the distance is one hop, for queue length metrics the router examines each queue, for the delay metric the route can measure it directly with special ECHO packets that the receiver just timestamps and sends back as fast as it can.

Distance vector routing works in theory, but has a serious drawback in practice: although it converges to the correct answer, it may be done slowly. Good news propagates at linear time through the subnet, while bad ones have the count-to-infinity problem: no router ever has a value more then one higher than the minimum of all its neighbors. Gradually, all the routers work their way up to infinity, but the number of exchanges required depends on the numerical value used for infinity. One of the solutions to this problem is split horizon algorithm that defines the distance to the X router is reported as infinity on the line that packets for X are sent on. Under that behavior bad news propagate also at linear speed through the subnet.

7. 
   Link State Routing
   

1. 
   Discover its neighbors and learn their network addresses.
   
2. 
   Measure the delay or cost to each of its neighbors.
   
3. 
   Construct a packet telling to all it has just learned.
   
4. 
   Send the packet to all other routers.
   
5. 
   Compute the shortest path to every other router.
   

8. 
   Hierarchical Routing
   

Unfortunately the gains in routing table size & CPU time are not free, the penalty of increasing path length has to be paid.

It has been discovered that the optimal number of nested levels for an N router subnet is ln N, requiring a total of eln N entries per router.

9. 
   Routing for Mobile Hosts
   

Each time any mobile host connects to the network it collects a foreign agent packet or generates a request for foreign agent, as a result they establish connection between them and the mobile host supplies the foreign agent with it’s home & some security information.

After that the foreign agent contacts the mobile host’s home agent and delivers the information about the mobile host.

Subsequently the home agent examines the received information and if it authorizes the security information of mobile host it allows the foreign agent to proceed. As the result the foreign agent enters the mobile host into it’s routing table.

When the packet for the mobile host arrive its home agent it encapsulates it and redirects to the foreign agent where the mobile host is hosting. Then it returns encapsulation data to the router that sent the packet so that all next packet would be directly sent to correspondent router (foreign agent).

10. 
    Broadcast Routing
    

1. 
   The source should send the packet to all the necessary destinations. One of the problems of this method is that the source has to have the complete list of destinations.
   
2. 
   Flooding routing. As it was discussed before the problem of that method is generating duplicate packets.
   
3. 
   Multidestination routing. In that method each packet includes list or a bitmap indicating desired destinations. When a packet arrives router checks all the destinations to determine the set of output lines that will be needed, generates a new copy of the packet for each output line to be used and includes in each packet only those destinations that are to use the line. In effect, the destination set is partitioned between the lines. After a sufficient number of hops, each packet will carry only one destination and can be treated as a normal packet.
   
4. 
   This routing method makes use of spanning tree of the subnet. If each router knows which of its lines belong to the panning tree, it can copy an incoming broadcast packet onto all the spanning tree lines except the one it arrived on. Problem: each router has to know the spanning tree.
   
5. 
   Reverse path-forwarding algorithm at the arrival of the packet checks if the line that packet arrived on is the same one through which the packets are send to the source, if yes it sends it through all other lines, otherwise discards it.
   

11. 
    Multicast Routing
    

To do multicast routing, each router computes a spanning tree covering all other routers in the subnet. When a process sends a multicast packet to a group, the first router examines its spanning tree ad prunes it, removing all lines that do not lead to hosts that are members of the group.

The simplest way of pruning the panning tree is under Link State routing when each router is aware of the complete subnet topology, including which hosts belong to which groups. Then the spanning tree can be pruned by staring at the end to each path and working toward the root, removing all routers that do not belong the group in question.

A different pruning strategy is followed with distance vector routing, reverse path forwarding algorithm. Whenever a router with no hosts interested in a particular group and no connections to other routers receives a multicast message for that group, it responds with a PRUNE message, telling the sender not to send it any more multicasts for that group. When a router with no group members among its own hosts has received such messages on all its lines, it, too, can respond with a PRUINE message. In this way, the subnet is recursively pruned.