Improving latency for high priority data using QOSPF - a QoS extension to OSPF protocol
1. Congestion Reporter Module:
1)In order to calculate the utilization and available bandwidth on each link, we follow the below mentioned steps:
i) Keep track of the number of bytes of data transferred in each time interval
ii) Calculate the link utilization (transmission rate) and available bandwidth during each interval using:
Utilization = (No. of bytes transferred till time x - No. of bytes transferred till time y) /(Tx - Ty), where Tx and Ty are the time instants at which bytes are read from the /proc/net/dev
Available bandwidth = Bandwidth of the interface - Utilization
2) The link cost calculation of OSPF doesn’t take into account, the congestion present on the link. The original link cost is calculated based on the OSPF reference bandwidth and the interface bandwidth. We adapt it to include the available bandwidth during each interval in addition to the reference bandwidth of each interface.
Initial_cost = (OSPF reference bandwidth)/(bandwidth of the outgoing interface)
New_cost = (OSPF reference bandwidth)/(bandwidth of the outgoing interface) + (Used Bandwidth/ Bandwidth of the interface)
3) Available bandwidth and link cost is computed in regular intervals of 0.5 seconds. However, advertising an LSA each time it is calculated, is not advisable if the available bandwidth fluctuations are minor as bursty data will result in major fluctuations and crowd the network with LSAs. A moving average of available bandwidth over the last ten iterations is kept for this purpose. This gives a better view of persistent congestion rather than trivial data bursts.
4) Sending periodic LSAs even when there has been no change in bandwidth will lead to unnecessary traffic and recomputation of routes at each node. In order to determine when to trigger an LSA, the cost calculated for a link is associated with a window it falls into. 1l and 4u being the range of values the link cost can take, the cost associated with a link falls into one of the four windows at a time. Initially, the cost is 0. So it is associated with window 1. As long as the cost does not cross the upper threshold or lower threshold of its window, the window does not change and LSAs are not triggered. This can be summarised as:
i) If cost is greater than upper threshold of the current window, trigger an LSA and shift to the higher window.
ii) If cost is lower than lower threshold of the current window, trigger an LSA and shift to the lower window.
The extents of the windows are hardcoded. They are made overlapping so as to not trigger frequent LSAs if the cost happens to move around the threshold points.
Below is the algorithm used:
2. LSA Handler:
In order to communicate the information about the changing link cost, the links need to be uniquely identified. For this, each of the nodes is given a unique identifier to identify itself. The relevant information about the other nodes and links is specified in the topology file. The packet is standardised so that each routing node understands the LSA packet it receives from the other nodes. The fields in the packet include:
Source node Identifier, Destination Node Identifier: Identification of the end points on a link. The source node is the node that generates the LSA packet. The to uniquely identify a link
Sequence Number: A 32-bit sequence number to uniquely identify an LSA packet coming from a node, required for Controlled packet flooding
Link Cost: The cost associated with the link
The LSA handler receives packets from the local host as well as the other nodes. The following algorithm runs to handle the separate packets differently:
3. QoS Forwarding table creator:
Dijkstra’s algorithm is run to calculate the shortest path routes to each of the nodes. The algorithm operates again on a directed graph where vertices correspond to routers and end hosts. The metric associated with each edge in the graph is the cost associated with the corresponding edge, where b(n;m) is the available bandwidth on the edge between vertices n and m. The vertex corresponding to the router where the algorithm is being run is selected as the source node for the purpose of path selection, and the algorithm proceeds to compute paths to all other nodes (destinations).
In order to run Dijkstra’s algorithm, information about the entire topology is required. For this purpose, a file is present at each node that describes the entire topology. Each line in the file describes a link. It has four parameters, source node id, source address, destination node id, destination address. The node identifiers are unique identifiers associated with each node while forming the topology. The node identifiers are followed by the ip address of that node on that link. By parsing all the lines, each router becomes aware of the entire topology with the addresses on them. The default cost associated with each link is taken as 10.
Dijkstra’s Algorithm
Input:
Q = set of vertices, labeled by integers 1 to N.
L = set of edges, labeled by ordered pairs (n,m) of vertex labels.
s = source vertex (at which the algorithm is executed).
For all edges (n,m) in L:
* dist_between(n,m) = cost associated with the link (according to last.
The pseudocode for the algorithm is as follows
function Dijkstra(Graph,source): //Initialization
for each vertex v in Graph:
dist[v] := infinity // Initial distance set to infinite
previous[v] := undefined //Previous node in optimal path from source
Q := the set of all nodes in Graph
while Q is not empty:
u := node in Q with smallest dist[ ]
remove u from Q
for each neighbor v of u: // where v has not yet been removed from Q.
alt := dist[u] + dist_between(u, v)
if alt < dist[v] // Relax (u,v)
dist[v] := alt
previous[v] := u
return previous[ ]
4. QoS Lookup and Forwarding:
This module largely exploits the existing features of Linux kernel and basically just requires configuration of rules for the lookup and the entries. The utility used for the project is iproute2. It is a user space utility for controlling and monitoring various aspects of networking in the Linux kernel . A part of the iproute2 suite of tools for IP management, ip route provides management tools for manipulating any of the routing tables. Another part of the iproute2 software package, ip rule is the single tool for manipulating the routing policy database under linux (RPDB). It mediates access to the routing tables.
For the proper lookup and forwarding of QoS packets, following configurations are required:
i) Setup of multiple routing tables: Linux kernel supports multiple routing tables. This feature is exploited to create separate routing tables for the QoS levels. Two routing tables main, and QoSRT will be maintained in the kernel, one for each supported QoS type. The lookup table for the high priority packets, namely QoSRT, will be dynamically updated at the receipt of each LSA by the forwarding table creator. Entry for these tables will be made in the /etc/iproute2/rt_tables on each router using a bash script.
ii) Adding entries for the routing tables: The entries to the route tables are made by the Forwarding table creator. For this, ip route tool of the iproute2 package is used.
The following commands are called via program:
i)To add a route to the main table: ip route add <destination> via <gateway> table main
ii) To add a route to the QoS table: ip route add <destination> via <gateway> table QoSRT
iii) To flush the QoS table: ip route flush table QoSRT
iii) Adding rules for the table selection during lookup: To inform the Linux forwarding stack about the selection of routing table for a particular type, ip rules, a part of iproute2 package, is used. It enables users to modify the routing policy database of linux networking kernel. According to the requirement of this project, the next hop for every packet is decided depending on the destination address and the QoS type. The rule for the correct lookup that will direct the linux kernel to check the correct forwarding table for each type of the supported QoS type will be added to every router using bash script. The rule is as follows:
ip rule add tos 0X04 table QoSRT prio 2
If no next hop entry is found in the routing table of the QoS type , then the packet is forwarded to the next hop entry in the main lookup table.
