Other Protocols and Algorithms

In the preceding two chapters, the two main protocols Sliding Window and CSMA/CD, for which simulators have been created, were studied in great detail. Their implementation details were also observed. In this chapter, we study some other protocols/algorithms whose teaching tools have been developed, but the simulators of which are still in the process of being improvised, to make these tools more comprehensive, thereby enabling more effective teaching.

Routing of data packets is an important aspect of network design. With reference to the OSI model, it is the network layer that is responsible for routing packets from the source machine to the destination machine. Various algorithms have been developed for this purpose, each one using a different technique to route packets in the most efficient manner possible. Simply put, the routing algorithm decides which output link an incoming packet should be transmitted on. A good routing algorithm should possess the following properties – correctness, simplicity, robustness, stability, fairness, optimality and efficiency. Some of these may conflict, but a routing algorithm must try to achieve as many of these as possible.

Selection of a route is based on some performance criterion. This criterion can be hop count, traffic along a link, queueing delay at a node, bandwidth of a link or some other factor or a combination of a number of these properties. The metric to be used for routing decisions is decided beforehand.

There are two major classes of routing algorithms – adaptive and non-adaptive. Non- adaptive algorithms, also known as static algorithms, compute the best routes in advance. Once the router is running, no changes are made to the routes selected. Therefore this class of algorithms cannot adapt to changes in the network, though they are easy to implement. Adaptive algorithms, also known as dynamic algorithms, adapt continuously to changes in the network thus providing better performance. However these are difficult to implement and also increase the overhead since network information has to be exchanged between nodes.

Fixed Routing, also known as Shortest Path Routing, is a static routing algorithm which is simple and easy to understand. Here a route is selected for each source-destination pair of nodes in the network. Usually the Dijkstra’s algorithm or the Bellman-Ford algorithm is used to select the best routes. These routes remain fixed unless there is a change in the topology of the network. The selected algorithm is implemented on the network and the results are stored in a central routing directory. This directory is a two-dimensional structure mapping source nodes to destination nodes. The entry for each pair of such nodes contains the next node to take for a best route between source and destination. Once the directory has been created, it is sent out to all the nodes in the network. Each node stores the part of this directory in which it is the source node in a table known as routing table. After the network is functional, no more changes are made to these tables. When a packet arrives at a node, it reads the header of the packet to find out the destination. This destination value is used to index into the routing table to obtain the node to which the packet should be transmitted for best performance. The packet is then transferred to that node. This algorithm has the advantage of simplicity though it is not flexible and is not used in practice.

Flooding is another static routing algorithm. In its simplest form it works as follows – each packet received by a node is sent out to all its neighbours except the one from which it received the packet. It has the advantage that it requires no network information thus reducing the overhead. Also, it is very robust since all the routes are tried. This ensures that atleast one packet reaches the destination. In addition, it always selects the shortest path. However, the high number of packets generated adds to the network traffic which may result in an avalanche, causing the network performance to fall. To avoid this problem, each node keeps track of which packets it has flooded. When a duplicate packet arrives, it is discarded thus reducing the number of packets generated.

The simulation developed offers the option of two algorithms - Fixed Routing and Flooding. The same network is used for both, which cannot be changed. The applet interface consists of two parts – the first part forms a major part of the screen where the network is displayed, and the second part consists of four buttons which allow the user to control the applet. When the applet is loaded, the network is displayed and only one of the buttons, the "Options" button, is enabled. This button is not available when a simulation is in progress. By default no algorithm is selected. Therefore the user has to make use of this button, which on clicking displays a window with three menu items. One of these allows the user to control the speed of the simulation – the settings offered are slow, medium (default) and fast. The second menu item allows the user to select the algorithm. If the user is satisfied with the selections made, he can access the third menu item to save the changes. However if he wants to revert to the original settings, he can close the window without saving the settings. Once an algorithm has been selected, the "Start" button is enabled. The user can start the simulation by clicking on this button. If the fixed routing algorithm was selected, the "Routing Table" button is also enabled, which when clicked, displays the routing table for the network in a window.

When "Start" is clicked, a window pops up to prompt the user for the source and destination nodes. Once these parameters have been specified, the simulation begins. The colour of the source and destination nodes changes from blue to red to differentiate them from the remaining nodes. The caption on the "Start" button changes to "Stop". This button can now be clicked to stop the simulation at any time. The "Pause" button is enabled. It can be clicked to pause the simulation. The simulation can be resumed by clicking on this button which now bears the caption "Resume".

In the Fixed Routing simulation, the packet is shown to have a header containing the number of the destination node. This is read by each node to direct the packet along the shortest path by referring to the routing table. During the simulation the routing table window can be kept open so that the user can check if the correct path is being used.

In the simulation for the Flooding algorithm, each node sends out packets in a different colour so that it is easy for the user to understand the working of the algorithm. Another feature is that when a node discards a duplicate packet, a mark appears above it. This helps the user to keep track of the mechanism. The routing table option is disabled during flooding since it does not make use of the table.

A Local Area Network (LAN) having a ring topology consists of a number of repeaters joined by point-to-point links in a closed loop. Hence each repeater participates in two links on the ring. The repeater is a relatively simple device, capable of reception of data on one link and transmission of data (bit by bit) on the other link as fast as it is received, with no buffering at the repeater. Since the links are unidirectional, data is transmitted in one direction only, and all oriented in the same way. Hence, data circulates around the ring in one direction only, either clockwise or counter-clockwise. Each station attaches to the network at a repeater. The data is transmitted in the form of packets inserted onto the ring by the stations. The packet contains source and destination address fields as well as other control information and user data. As a packet circulates, the destination station copies the data into a local buffer. The packet continues to circulate until it returns to the source station, where it is absorbed, removing it from the ring. Since, multiple devices share the ring, some form of medium access logic is needed to control the order and timing of packet transmissions.

The Token Ring is one of the most widely used Medium Access Control (MAC) protocols for the ring topology. The Token Ring technique is based on the use of a small token packet that circulates around the ring. When all stations are idle, the token packet is labeled as a "free" token. A station wanting to transmit, waits until it detects a token passing by. It then seizes the token, inverts a single bit in the 3-byte token, which instantly changes it into the first 3 bytes of a normal data frame, following which the data packet is sent on its way. There is now no free token on the ring, so other stations wishing to transmit must wait. The data packet on the ring will make a round trip and be purged by the transmitting station. The transmitting station will insert a new free token on the ring when both of the following conditions have been met :

The station has completed transmission of its packet.

The busy token (i.e. the data packet) has returned to the station.

If the bit length of the ring is less than the packet length, the first condition implies the second. If not, a station could release a free token after it has finished transmitting but before it receives its own busy token. However, this might complicate error recovery, since several packets will be on the ring at the same time. When a transmitting station releases a new free token, the next station downstream with data to send will be able to seize the token and transmit. In any case, there is only one token, so only one station can transmit at a given instant, thus solving the channel access problem.

The simulation of the Token-Ring protocol has been done in Java with the help of the java.net package, which provides support for networking. The choice of Java over other programming languages is because all the classes required for networking are defined in the java.net package and can be easily made use of.

The working of the Token-Ring protocol has been simulated by concurrently running three different DOS sessions, representing the three stations (A, B & C) which are part of the ring network. These three DOS sessions which act as virtual terminals of the network, are in reality network sockets which map into three different port addresses. In this Java application, these network sockets are defined using the ‘DatagramSocket’ class which is a mechanism to send or receive datagrams. These datagrams in turn are defined using the ‘DatagramPacket’ class, whose objects act as data containers. The class file of the Token-Ring application runs with different command-line arguments (a/b/c), each representing the corresponding station and hence, we have three DOS based sessions.

The free token is initially in the possession of Station A. The token and data packets (using the ‘DatagramPacket’ class) are transmitted from A to B to C and back to A, in that order. Each time the free token arrives at a station, the station has the option of utilizing the token to transmit a data packet or to simply forward the free token to the next logical station in the ring. Both the token and data packets always follow the logical order of the ring. When the busy token (i.e. the data packet) comes back to the sender, the token is freed and the free token is sent on its way again around the ring.

The main function of the network layer is to guide packets from the source machine to the destination machine. In most subnets, the packets will require multiple hops to make the journey. The purpose of routing is to find a way to get datagrams to their ultimate destinations. A routing algorithm is employed to do just this, thereby deciding which output line an incoming packet should be transmitted on. Routing algorithms can be classified as adaptive and non-adaptive. Non-adaptive algorithms do not base their routing decisions on measurements or estimates of the current traffic and topology. The route is computed in advance, off-line, and is downloaded to the routers when the network is booted. This is also called 'static' routing. Adaptive algorithms, on the other hand, change their routing decisions to reflect changes in the topology, and usually the traffic as well. Adaptive algorithms differ in where they get their information, when they change the routes, and what metric is used for optimisation (e.g., distance, number of hops, or estimated transit time).

Distance Vector Algorithms belong to adaptive/dynamic class of routing algorithms and they operate by having each router maintain a table (i.e. a vector) giving the best route to every destination in the system and which outgoing line to use to get there. Of course, in order to define which route is best, we have to have some way of measuring goodness. This is referred to as the "metric". In simple networks, it is common to use a metric that simply counts how many routers a message must go through. In more complex networks, a metric is chosen to represent the total amount of delay (i.e. the Link Propagation Delay ) that the message suffers, the cost of sending it, or some other quantity which may be minimised. The main requirement is that it must be possible to represent the metric as a sum of "costs" for individual hops [U1]. So, each router maintains a routing table indexed by, and containing an entry for every other router in the subnet. This entry contains two parts: the preferred outgoing line to use for that destination, and an estimate of the cost to that destination, depending upon the metric.

Formally, if it is possible to get from station i to station j directly (i.e., without passing through another router in between), then a cost d(i,j), is associated with the hop between i and j, depending upon the metric chosen (in the implementation of the above algorithm, the metric chosen was the Link Propagation Delay between stations). To get the metric of a complete route, one just adds up the costs of the individual hops that make up the route. Let D(i,j) represent the metric of the best route from station i to station j. It should be defined for every pair of stations. d(i,j) represents the costs of the individual steps. Formally, let d(i,j) represent the cost of going directly from station i to station j. It is infinite if i and j are not immediate neighbours. (Note that d(i,i) is infinite. That is, we don't consider there to be a direct connection from a node/station to itself.) Since costs are additive, it can be shown that the ‘best metric’ must be described by

D(i,i) = 0, for all i

D(i,j) = min [d(i,k) + D(k,j)], otherwise k

and that the best routes start by going from i to those neighbours k for which d(i,k) + D(k,j) has the minimum value. (This can be shown by induction on the number of steps in the routes). The second equation is limited to k's that are immediate neighbors of i. For the others, d(i,k) is infinite, so the term involving them can never be the minimum.

The metric can be computed by a simple algorithm :-

Station i gets its neighbours k to send it their estimates of their distances to the destination j. When i gets the estimates from k, it adds d(i,k) to each of the numbers. This is simply the cost of traversing the network between i and k. Now and then i compares the values from all of its neighbours and picks the smallest.

The statement of the algorithm given above, assumes that each station keeps copies of the estimates that come from each of its neighbours, and now and then does a ‘min’ over all of the neighbours, when data is to be transmitted to the destination. This is precisely the principle employed in calculating the shortest path in the design & implementation of the Java application simulating the working of the Distance Vector Algorithm.

The simulation of the working of the Distance Vector Algorithm (which is used in the Routing Information Protocol (RIP)) has been done in Java, using the java.net package as was in the implementation of the Token-Ring protocol.

The working of the Distance Vector Algorithm in a networking environment employing RIP, has been simulated by means of a Java application which uses the ‘DatagramSocket’ class of the java.net package, to define and declare network sockets mapped onto different port addresses, acting as ‘virtual’ stations/terminals of the network in consideration. The ‘DatagramPacket’ class is used to declare objects acting as data containers. These objects are actually the data packets (datagrams) sent from the transmitting station to the receiving station.

The class file generated runs with different command-line arguments (a/b/c/d/r), where the first four options (i.e. a, b, c & d) start DOS sessions representing the corresponding stations. The fifth option ‘r’ opens a Routing Table Update session, where the link propagation delay between existing links can be changed, links can be deleted/restored and the routing tables at all the stations are kept informed of these changes. When the network is booted, the routing table is initialised with default values, as mentioned in the HELP file for the Java application. Whenever a station wants to transmit a data packet to another station, the Distance Vector Algorithm dynamically computes the shortest path to the destination (i.e. path with smallest overall link propagation delay), depending on the current values of the link propagation delay between stations, in the Routing Table. When a path to the destination does not exist (maybe because of deletion of intermediate links), then an appropriate message is flashed on the console and the user may have to wait until one of the deleted links comes up or has the option of choosing another destination. The total number of terminals/stations in the above implementation remains constant at four (i.e. stations A, B, C & D).