OSI (Open System Interconnection) Reference Model.
The OSI model is shown is figure below:
7 Application Application protocol Application
6 Presentation Presentation protocol Presentation
5 Session Session protocol Session
4 Transport Transport protocol Transport
Communication subnet boundary
3 Network Network Network Network
Internal subnet protocol
2 Data Link Data Link Data Link Data Link
1 Physical Physical Physical Physical
Host A Router Router Host B
Network layer host-router protocol
Data link layer host-router protocol
Physical layer host-router protocol
This model deals with connecting open systems – that is, systems that are open for communication with other systems. Note that the OSI model itself is not a network architecture because it does not specify the exact services & protocols to be used in each layer. However, common standards were produced by ISO (International Standards Organization) for each layer:
The physical layer is concerned with transmitting raw bits over communication channel under assumption , that it is 100% reliable.
1.1.2 Data Link 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).
The network layer is concerned with controlling the operation of the subnet. That is routing the packets from the source to destination. Routes can be based on static or dynamic routing tables as will be reviewed later. *(This layer is the one that we are actually interested in)*.
The transport layer basic function is to accept data from the session layer derive it into packet (if necessary) , pass these to the network layer and restore the data on the other end.
The session , presentation & application layers are less interesting for us, however you can find their reviews in “Computer Network” of Andrew Tanenbaum (3-d edition).
TCP/IP Reference Model
This model was developed on the base of first computer networks (like ARPANET) and has only 4 layers:
The internet layer is the linchpin that holds the whole architecture together. It allows hosts to inject their packets into any network and have them travel independently to their destination. This layer defines official protocol called IP.
The transport layer lies above the internet layer and it’s functionality is much alike to the same layer in OSI model – it allows peer entities on the source & destination hosts to carry on a conversation (2 end-to-end protocols were defined here: TCP & UDP).
There are tow more layers application & host-to-network that less interest us (the host-to-network layer plays minor part in TCP/IP protocol, steel being significant enough by itself) , you can find further information at the same reference as before.
1.3 OSI via TCP/IP
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.
Generally the OSI model has proven to be exceptionally useful for discussing computer networks, but OSI protocols did not become popular .The reverse is true of TCP/IP: the model is practically nonexistent , but the protocols are widely used.
2.1 Field of interest.
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:
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.
Connectionless Routing (general).
(any detailed information available at “Computer Networks” Andrew Tanenbaum, chap. 5).
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.
The main function of the network layer is routing packets from source to destination. The algorithms that chouse the routes and the data structures that they use area major area of network layer design.
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.
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.
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.
The Optimality Principle
To start with algorithm’s overview we should see some helpful theoretical explanations. The optimality principle states that if router J is on the optimal path from router I to router K, then the optimal path from J to K also falls along the same route. As a consequence of that principle, we can see that the set of optimal routes from all sources to a given destination form a tree rooted at the destination. Such tree is called a sink tree.
In the next three sections, we will look at three static routing algorithms, subsequently we will move to dynamic ones.
Shortest Path Routing
The following technique is widely used in many forms, because it is simple and easy to understand. The idea is to build a graph of the subnet, with each node of the graph representing a router and each arc representing a communication line (link).To choose a rout between a given pair of routers , the algorithm just finds the shortest path between them on the graph. The shortest path concept includes definition of the way of measuring path length. Deferent metrics like number of hops, geographical distance, the mean queuing and transmission delay of router can be used. In the most general case, the labels on the arcs could be computed as a function of the distance, bandwidth, average traffic, communication cost, mean queue length, measured delay, and other factors.
There are several algorithms for computing shortest path between two nodes of a graph. One of them due to Dijkstra.
That is another static algorithm, in witch every incoming packet is sent out on every outgoing line except the one it arrived on. Flooding generates infinite number of duplicate packets unless some measures are taken to damp the process.
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.
The algorithms seen above took only topology into account and did not consider the load. The following algorithm considers both and is called 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).
Distance Vector Routing
Modern computer networks generally use dynamic routing algorithms rather then static ones described above. Two dynamic algorithms in particular, distance vector & link state routing are the most popular. In this section we will look at the former algorithm. In the following one we will study the later one.
Distance vector routing algorithms operate by having each router maintain a table giving he best known distance to each destination and which line to use to get there. These table are updated by exchanging information with the neighbors.
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.
Link State Routing
The idea behind link state routing is simple and can be stated as five parts. Each router must:
Discover its neighbors and learn their network addresses.
Measure the delay or cost to each of its neighbors.
Construct a packet telling to all it has just learned.
Send the packet to all other routers.
Compute the shortest path to every other router.
In effect, the complete topology and all delays re experimentally measured and distributed to every router. Then Dijkstra’s algorithm can be used to find the shortest path to every other router.
As the network grows larger the amount of resources necessary to take care or routing table becomes enormous and makes routing impossible. Here appears the idea of hierarchical routing that suggests that routers should be divided into regions, with each router knowing all the details about how to route packets within its own region, but knowing nothing about the internal structure of other regions.
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.
Routing for Mobile Hosts
Through the last years more and more people purchase portable computer under natural assumption that they can be used all over the world. These mobile hosts introduce new complication: to route a packet to a mobile host the network first has to find it. Generally that requirement is implemented through creation of two new issues in LAN foreign agent and home agent.
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).
For some applications ,hosts need to send messages to many or all other hosts. Broadcast routing is used for that purpose. Some deferent methods where proposed for doing that.
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.
Flooding routing. As it was discussed before the problem of that method is generating duplicate packets.
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.
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.
Reverse path-forwardingalgorithm 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.
Sending messages to well-defined groups that are numerically large in size, but small compared to the network as a whole is called multicasting. To do multicasting, group management is required, but that is not concern of routers. What is of concern is that when a process joins a group, it informs its host of this fact. It is important that routers know which of their hosts belong to which group. Either hosts must inform their routers about changes in group membership, or routers must query their hosts periodically.
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.
One potential disadvantage of this algorithm is that it scales poorly to large networks.
An alternative design uses core-base trees. Here a single spanning tree per group is computed, with the root (the core) near the middle of the group. To send a multicast message, a host sends it to the core, which then does the multicast along the spanning tree. Although this tree will not be optimal for all sources, the reduction in storage costs from m trees to one tree per group is a major saving.