International Journal of Innovative Research in Computer and Communication Engineering

International Journal of Innovative Research in Computer and Communication Engineering

Menu

ISSN ONLINE(2320-9801) PRINT (2320-9798)

All submissions of the EM system will be redirected to Online Manuscript Submission System. Authors are requested to submit articles directly to Online Manuscript Submission System of respective journal.

Analyse the New Path Weight Using Hop By Hop Routing Mesh Networks

Sangeetha. C1 and Rajkumar. S2
  1. PG Scholar, Department of CSE, K.S.Rangasamy College of Technology, India
  2. Assistant Professor, Department of CSE, K.S.Rangasamy College of Technology, , India
Related article at Pubmed, Scholar Google

Visit for more related articles at International Journal of Innovative Research in Computer and Communication Engineering

International Journal of Innovative Research in Computer and Communication Engineering

Abstract

Wireless Mesh Network (WMN) has become an important edge network to provide Internet access to remote areas and wireless connections in a metropolitan scale .The problem of identifying the maximum available bandwidth path a fundamental issue in supporting quality-of-service in WMNs. Due to interference among links, bandwidth, a well-known bottleneck metric in wired networks, is neither concave nor additive in wireless networks. The proposed system a new path weight which captures the available path bandwidth information. Formally prove that our hop-by-hop routing protocol based on the new path weight satisfies the consistency and loop-freeness requirements. The consistency property guarantees that each node makes a proper packet forwarding decision, so that a data packet does traverse over the intended path. Our extensive simulation experiments also show that our proposed path weight outperforms existing path metrics in identifying high-throughput paths.

 

Keywords
Wireless meshes networks, QoS routing, proactive hop-by-hop routing, distributed algorithm.

INTRODUCTION
Wireless mesh network (WMN) consists of a large number of wireless nodes. The nodes form a wireless overlay to cover the service area while a few nodes are wired to the Internet. As part of the Internet, WMN has to support diversified multimedia applications for its users. It is essential to provide efficient Quality-of-Service (QoS) support in this kind of networks [1]. Seeking the path with the maximum available bandwidth is one of the fundamental issues for supporting QoS in the wireless mesh networks. The available path bandwidth is defined as the maximum additional rate a flow can push before saturating its path [2]. Therefore, the traffic rate of a new flow on a path is no greater than the available bandwidth of this path accepting the new traffic will not violate the bandwidth guaranteed of the existing flows. This paper focuses on the problem of identifying the maximum available bandwidth path from a source to a destination, which is also called the Maximum Bandwidth Problem (MBP). MBP is a sub problem of the Bandwidth-Constrained Routing Problem (BCRP).In amount of available bandwidth [3]. Routing algorithms can be deterministic or adaptive. With deterministic routing only one path is provided for every source-destination pair of nodes. On the other hand, adaptive routing is able to provide alternative paths to route messages. Usually, adaptive routing improves network performance, since it avoids congested regions in the network. Routing algorithms are carefully designed to avoid deadlocks. A deadlock occurs in an interconnection network when no message is able to advance toward its destination because they become involved in a cycle of resource requests that cannot be satisfied because these resources are held by other messages. A simple and effective approach to avoid deadlocks consists of restricting routing so that there are no cyclic dependencies between channels. Routing has significant impact on overall network's performance as it can enhance the capability of communication system. Further, it is known that ideal routing system follow optimum shortest path. For this purpose different algorithms were proposed and are still under research for more enhancements. Some of these algorithms are implemented at network layer where a selected cost is assigned to each link and a shortest path algorithm is used to find either minimal cost path or minimal length path.
Networks of workstations (NOWs) are being considered as a cost-effective alternative to small and medium scale parallel computing. This is mainly due to the increasing computing power of microprocessors and the high cost of parallel computers. The performance of NOWs is closely related to the advances in the interconnection network. Originally, the interconnection of NOWs was based on local area networks (LANs). LANs have rapidly progressed to high-speed networking by applying the technologies previously proposed for the interconnection networks of parallel computers. NOWs are usually arranged as switch-based networks, which consist of a set of switches, each having several ports. Some ports are either connected to different workstations or left open, whereas the remaining ports are connected to ports belonging to other switches. Switch design must be flexible enough to support any topology with degree bounded by the number of switch ports. This flexibility allows users to decide the network connectivity. The layout of the network can consist of regular or irregular topologies. Regular topologies are often used when performance is the primary concern. This is the case when we have to design a large cluster of workstations to run computation intensive programs. The network would fit in a single room and the switches would be in a cabinet. However, the layout of a LAN network is usually spread across entire buildings where the physical locations of the hosts do not follow any regular pattern. The resulting topologies are referred to as irregular topologies. Routing can be based on source routing or distributed routing. In the former case, routing tables are used at each host to obtain the port sequence for each message, which is placed in the message header. In the latter case, switches require routing tables.

NETWORK MODEL
A packet network, which sends data by dividing several blocks with specified length called a “packet”. The network consists of nodes, links, and buffers. Each packet is transmitted to the destination nodes through several nodes. Fig.1 illustrates a model of link selections. Each node can know only its state in run-time without delay, and previously knows a topology of the network. Each link has a corresponding buffer, and arrival packets wait in the buffer and are transmitted to the next node by first-in first-out (FIFO) control. Routing is done without establishing the connection, that is, the network is of a connectionless type.

FORMULATION
Each packet is classified into an agent group according to its destination. Each outgoing link is regarded as a resource. In each node, each packet selects a link. This model has conflicts among groups of packets (agents) over links which are common resources. Thus it is considered as a resource selection problem in a multi-agent system. Each arrived packet probabilistically selects a link at each node according to the selection rate, which is given by each group of packet. This routing is accomplished at each node independently. Each group of agents has a common value criterion (payoff function). In the network, packets have different value criteria about their link selection if their destination nodes are different. So there are several groups of agents corresponding to the destination.

NETWORK PERFORMANCE
The following methods are considered,

STATIC ROUTING
Each packet is transmitted to the destination node based on the shortest path about the minimum number of hops determined in advance. If a packet has some minimum hop routes, it selects a link among them at random.

ADAPTIVE ROUTING
A search of the shortest path is made based on the evaluation of the link length. Numerous adaptive routing algorithms which are common in traditional networking are being adapted for use in inter-processor communications. Although this method has numerous advantages, the overhead in terms of speed and node size has thus far been prohibitive in the approach’s success. Future system-on-chips as well as network-on-chips may implement a form of such a routing algorithm but not as a central feature.

DISTRIBUTED ROUTING
In distributed routing each node receives some information about the network from its adjacent nodes and uses the information to determine the manner in which it forwards its traffic. This thesis gives three examples of distributed routing in a data communication network. A routing algorithm is then given where a generalized distributed routing procedure proposes a flow change and a central node determines the optimal scale of the proposed change. The communication subsystem plays a key role in modern high-performance computing systems. This subsystem is usually based on a point-to-point switch-based technology, and should not only ensure high levels of performance, but must also be highly robust and easily available. In recent years, some different technologies have emerged, based on distributed routing or source routing or Advanced Switching Interconnect.
In these environments, after the occurrence of a topological change such as the failure or aggregation of a network component, a new routing function, which is appropriate to the resulting topology, must be obtained and uploaded in the routing elements. The change assimilation process is typically performed by a centralized management entity, which is called mapper or subnet manager or fabric manager. More specifically, once the manager detects the change, it first has to collect information about all active devices, endpoints and switches are physically connected to the fabric. After that, a new set of paths for packet delivery among endpoints must be established. The last phase involved in the change management process consists in replacing the old routing function by the new one. The problem of finding the shortest path (SP) from a single source to a single destination in a graph arises as a sub problem to many broader problems, including routing in computer networks.

CENTRALIZED ROUTING
Centralized routing model is a model of routing in which routing is done at the center using a centralized database. In other words, the routing table is kept to a single “central” node, which should be consulted when other nodes makes a routing decision. This central database has a global network view. Centralized routing is considered to be the most correct in the specific areas with systems providing DWDM (Dense Wavelength Division Multiplexing) transmission. This is because these DWDM systems contain OADM (the Optical Add-drop Multiplexer) that can be reconfigured in the beginning and the end point of the medium of communication. Proponents of centralized routing suggest that because most information such as details of SRLG (Shared Risk Link Group) and performance parameters do not change often (and these information can never be discovered or self-reported), they are ideal to be accumulated in a central database. In a centralized model, status information can easily be accessed. Thus, the dependency information (regarding routing) between the circuits (to ensure diversity exists) can be manipulated relatively easily when the terminal is not shared between the circuits and is ideal for a model of centralized routing. The centralized model uses global information public. Calculations that are done (like the pre-computer to restore trails) can be highly benefited from the global information and thus is suitable for a centralized model. Global centralized routing is sometimes called “God” routing; it is a special implementation that walks the simulation topology and runs a shortest path algorithm, and populates each node’s routing tables. No actual protocol overhead (on the simulated links) is incurred with this approach. It does have a few constraints:
• Wired only: It is not intended for use in wireless networks.
• Unicast only: It does not do multicast.
• Scalability: Some users of this on large topologies (e.g. 1000 nodes) have noticed that the current implementation is not very scalable. The global centralized routing will be modified in the future to reduce computations and runtime performance.
Presently, global centralized IPv4 unicast routing over both point-to-point and shared (CSMA) links is supported. By default, when using the ns-3 helper API and the default Internet Stack Helper, global routing capability will be added to the node, and global routing will be inserted as a routing protocol with lower priority than the static routes (i.e., users can insert routes via Ipv4StaticRouting API and they will take precedence over routes found by global routing). This section is for those readers who care about how this is implemented. A singleton object (Global Route Manager) is responsible for populating the static routes on each node, using the public Ipv4 API of that node. It queries each node in the topology for a “global Router” interface. If found, it uses the API of that interface to obtain a “link state advertisement (LSA)” for the router. Link State Advertisements are used in OSPF routing, and we follow their formatting. The Global Route Manager populates a link state database with LSAs gathered from the entire topology. Then, for each router in the topology, the Global Route Manager executes the OSPF shortest path first (SPF) computation on the database, and populates the routing tables on each node.

SOURCE ROUTING
Source routing is a method that can be used to specify the route that a packet should take through the network. In source routing the path through the network is set by the source or a device that tells the network source the desired path. It is assumed that the source of the packet knows about the layout of the network and can specify the best path for the packet. Usually network routing is used on the internet and most networks rather than source routing. With network routing the knowledge about the network layout is in the network routing devices. Source routing can produce some security problems which is discussed later. When the packet with source routing specified is going through the network, the network device that makes routing decisions such as a router will look at the path specific information in the network packet to determine where to forward the packet. When source routing is not used, the packet contains only the destination address and the router will automatically determine the best place to forward the packet. When network routing is used, as a packet travels through the network, each router will look at the destination IP address and determine the next hop to forward the packet to. The next hop is the next router or network switching location where a network routing decision will be made. When source routing is used, the sender of the data makes some or all of the routing decisions. When the sender determines the exact network route the data packets must take, strict source routing is used. Strict source routing is rarely used. A common form of source routing is called loose source record route (LSRR). When using LSRR the sender will provide one or more hops that the packet must go through. It may specify one or more intermediate routers that the data must go through.
Source routing can be used to do any of the following:
• Troubleshoot a network
• Map a network
• Increase network performance
• Hack a computer
Source routing can be used for hacking purposes by allowing an attacker to get data to a machine that would not normally be reachable. Some machines are on private internet addresses such as 192.168.1.1 and they are not normally accessible from the internet. If there is a machine on a private network that performs routing and traffic may be routed through it between two other networks, it may be possible for an attacker to specify their data to go through the machine on the private network. The attacker may also fool the machine on the private network into believing it is some other computer using IP spoofing. The best way to prevent this attack is to configure the router on the private network to ignore source routed packets.

QOS ROUTING PROTOCOL
This section, the first present our path selection mechanism. It is based on the distance-vector mechanism. The necessary and sufficient condition to determine whether a path is not worthwhile to be advertised. Then describe our new isotonic path weight. We show that the routing protocol based on this new path weight satisfies the optimality requirement [7], [8]. Afterward, present our hop-by-hop packet forwarding mechanism which satisfies the consistency requirement. The apply (3) to estimate the available bandwidth of a path. To simplify our discussion, in the rest of our paper, The use “available bandwidth” instead of “estimated available bandwidth” when the context is clear. On the other hand, “widest path” refers to the path that has the maximum estimated available bandwidth.

HOP-BY-HOP
This section introduces our hop-by-hop Interest shaping mechanism, which realizes Interest rate control at the output interfaces of every CCN router. The rationale behind an additional Interest control realized at every network node is (i) to anticipate congestion detection and (ii) to trigger rate reduction via Interest shaping, before the receiver can detect the congestion via timer expiration. Each virtual queue is associated a credit counter initialized to a maximum value B (in bytes), indicating the number of Data bytes are granted to transmit, with no additional delay. The counter is incremented at the estimated fair rate of the corresponding down-link and decremented by forwarded Interests.
The design objectives of Hop-by-Hop TCP for sensor networks are as follows:
• Minimizing end-to-end packet delivery time without too much throughput degradation;
• Minimizing the number of retransmissions;
• Minimizing the occurrence of network congestion;
• Providing fairness service.
Hop-by-Hop TCP consists of two parts: an End-to-End TCP working on the source and destination nodes, and a One-Hop TCP working on every node. The sender module of a One-Hop TCP is working at the sender end of a link, and the receiver module is working at the receiver end. Each link needs only one pair of One-Hop TCP for all End-to- End TCP sessions.

PATH SELECTION
They would like to develop a distance-vector based mechanism. In the traditional distance-vector mechanism, a node only has to advertise the information of its own best path to its neighbors. Each neighbor can then identify its own best path. The mentioned that if a node only advertises the widest path from its own perspective, it neighbors may not be able to find the widest path. To illustrate, consider the network in Fig. 1 where the number of each link is the available bandwidth on the link.

NETWORK RECONFIGURATION
The process of replacing a routing function with another one is traditionally referred to as network reconfiguration. It is well known that, even when both routing functions are by themselves deadlock-free, updating the routing paths in an uncontrolled way may lead to deadlock situations due to the introduction of temporary dependencies among network resources. This means packets that belong to one of the routing functions may take turns that are not allowed in another routing function. Traditional reconfiguration mechanisms solved this problem by emptying the network of packets before replacing the routing function. Such a simple approach is referred to as static reconfiguration, and has a negative impact on the network service availability, since for a period of time the network cannot accept packets. Several schemes have recently been proposed for distributed routing systems in order to increase network availability during the change over from one routing function to another. These mechanisms allow injection of data traffic while the routing function is being updated, and are known as dynamic reconfiguration techniques. As these dynamic schemes become more and more efficient, anyone may be used for other alternative situations, apart from topology changes, such as balancing dynamically the network traffic to avoid possible congestion situations.

NETWORK CODING
Wireless networked systems arise in various communication contexts, and are becoming a bigger and integral part of our everyday life. In today practical networked systems information delivery is accomplished through routing. Network nodes simply store and forward data and processing is accomplished only at the end nodes. Network Coding (NC) is a recent field in electrical engineering and computer science that breaks with this assumption, instead of simply forwarding data, intermediate network nodes may recombine several input packets into one or several output packets. NC offers the promise of improved performance over conventional network routing techniques. In particular, NC principles can significantly impact the next generation wireless and sensor networks, in terms of both energy efficiency and throughput.
Among the many advantages offered by NC, notable examples are as follows:
1. By allowing intermediate nodes in a network to combine information streams and extract the information at the receivers, the throughput of multicast connections can be increased. The “butterfly network” is the most famous example demonstrating this benefit.
2. In a wireless environment, NC can be used to offer benefits in terms of battery life, wireless bandwidth, and delay. A simple example showing these benefits is the so called two way relay channel.
3. Sending linear combinations of packets instead of un coded data offers a natural way to take advantage of multipath diversity for security against wiretapping attacks.
However, the theory of NC is still in its infancy, and little is known about practical algorithms for exploiting coding in real networks. For example, while most of the existing NC theory assumes error–free links, in practice these links are usually prone to errors arising from, e.g., noise, fading, and interference.
Moreover, employing NC introduces some challenges, like, e.g.: i) complexity, since it requires the nodes in the network to have additional functionalities, and ii) security concerns, since a sound deployment of NC would require to put in place mechanisms that allow NC operations without affecting the authenticity of the transmitted data. Furthermore, when applying NC to a wireless context we need to take into account that the wireless medium is highly unpredictable and inhospitable to applying the existing NC algorithms, which have been mostly designed by assuming wired networks as the blueprint.

CONCLUSION
The maximum available bandwidth path problem, which is a fundamental issue to support quality-of-service in wireless mesh networks. The main contribution of our work is a new left-isotonic path weight which captures the available path bandwidth information. The left-isotonicity property of our proposed path weight facilitates us to develop a proactive hop-by-hop routing protocol, and formally proved that our protocol satisfies the optimality and consistency requirements. Based on the available path bandwidth information, a source can immediately determine some infeasible connection requests with the high bandwidth requirement. They tested the performance of our protocol under different scenarios.
 

Tables at a glance
Table icon
Table 1
 

Figures at a glance
Figure 1
Figure 1
 

References