Two-Tier Algorithm

CHAPTER VI

Two-Tier ALGORITHM

6.1 INTRODUCTION

The concept of physical layer module has been analyzed and designed from fiber span layout demand distribution, fiber network user service survivability, optical network demand bundling using DS3 forming and SONET Multi-Period capacity expansion integrated approach procedures in the previous chapters. Physical layer can be expanded further with logical connectivity, to enhance the multilayered service survivability such as Two-Tier fair Packet scheduling algorithm and the simulations are discussed in this chapter.

Nag T.S et.al. [33] introduced the problem of ad-hoc fair queuing. The focus was how to resolve the conflicts between fairness and maximal throughput. They suggested an ideal centralized model and also provided a tree-based distributed implementation as shown in Fig. 6.1. Their model consists of a simple channel, for transmission and reception of packets. This model cannot provide the multiple path connectivity and also cannot achieve the global fairness in packet scheduling.

The objective of the present work is to overcome the above problems. Hence the Two-Tier algorithm is introduced which guarantees the packet scheduling in optical ad-hoc network design [54]. This model deals with different packet scheduling procedures depending on network size and traffic patterns in optical ad-hoc networks. It also provides a single physical channel capacity C for multipath propagation of packets by means of transmission flow. It consists of two queues viz. slot queue i.e. unit of channel allocation and packet queue i.e. unit of transmission. Thus fair queuing can be achieved in terms of an efficient, scalable and localized manner in optical ad-hoc network architecture analysis.

6.2 OPTICAL AD-HOC NETWORK ARCHITECTURE ANALYSIS

In optical ad-hoc networks, the centralized distributed algorithms are implanted to assign max-min fair share for a data flow [42&43]. It achieves the fairness of packets scheduling in ad-hoc networks flow for N X N connectivity. Hence broadband connectivity and channel utilization is achieved.

The proposed Two - Tier algorithm, which is fully decentralized and localized, is as shown in Flow chart in Fig. 6.2, & Fig. 6.3 and the program is given in Appendix - E. The comparison table for various parameters is given in Table 6.1. It consists of three steps to maintain the packet scheduling procedures. Step 1 includes the fairness model and takes in to consideration of the parameters like Link Connectivity and Flow or Demands Connectivity. Step 2 applies the Two-Tier algorithm to achieve location-dependent contention, spatial channel reuse and also ensures fairness and maximizing channel utilization. Step 3 represents the Flow Information Propagation. Hence the throughput is expressed in terms of Link Connectivity and Flow Connectivity. The Spatial Channel reallocation is expressed by throughput connectivity.

(Step1) Local Fairness Model

The “global” nature of packet scheduling in multi-hop shared channel optical networks leads to a conflict between achieving fairness and maximizing aggregate channel utilization. This fairness model is local and topology-dependent because it provides a lower bound on channel allocation with respect to the present contention in the locality of the flow.

(Step2) Packetized Fair Queuing Algorithm

The packet scheduling algorithm achieves the local fairness model with complete knowledge of the network topology by assuming the information is at the packet scheduler and vice-versa.

(Step3) Flow Information Propagation

The local fairness model can be achieved by flow information propagation, which addresses the following practical issues. Propagation of transmission and reception flow is updated by its service tag. This information will be quite useful for packet scheduling messages to avoid the consequent collisions. An idealized packet-scheduling framework that addresses the design issues is identified in the sharing model in which each packet flow is treated as a fluid flow. In this fluid model the goal is to assign a minimum channel allocation to each flow, proportional to its weight and subject to its flow constraint and maximize the aggregate channel utilization.

A distributed achievement of the local fairness model within the optical layer must be used, where the flow information must be propagated among contending neighboring flows. The achievement seeks to address the following practical issues:

* Exchange of the propagation information between a flow's sender and its receiver: This algorithm requires to maintain flow within the transmission range of frequencies between sender and receiver.

* The sender has to retrieve the flow information that is maintained at the receiver to make scheduling decision.

* Propagation of transmission and reception flow is updated by its service tag. This information will be quite useful for packet scheduling messages to avoid the consequent collisions.

An idealized packet-scheduling framework that addresses the design issues is identified in the sharing model in which each packet flow is treated as a fluid flow.

6.2.1 PACKET DELIVERY VS. MAXIMUM SPEED

The maximum speed of the ad-hoc network nodes results in different phases depending on their location and as well as packet delivery procedures such as network greedy algorithm as shown in Fig. 6.4. These phases determine that the protocol achieves better packet delivery with a decreased variation in the number of packets received by both transmission and reception methods. At very low values of maximum speed gives near 100% packet delivery. At higher speeds, the data delivery varies from 80% to 90%. Hence overall performance of the system can be increased.

6.2.2 PACKET DELIVERY VS. NUMBER OF NODES

As the number of nodes in the network increases, the routing distance between the nodes goes up, and hence the frequency of link failures in the network also increases. Hence the variation of packet delivery increases in the number of nodes in multi-hop connectivity.

6.3 SELF-COORDINATING LOCALIZAED FAIR QUEUEING IN OPTICAL

AD-HOC NETWORKS

Distributed fair queuing in multihop, optical ad-hoc network is challenging for several reasons. First, the optical channel is shared among multiple nodes in a spatial locality. Second, the sender of a flow does not have explicit information regarding the flows originated from other nodes.

Providing packet-level Quality of Service (QoS) is critical to support both rate-sensitive and delay-sensitive applications in the bandwidth-constrained, shared-channel, multihop networks. Packet scheduling has been a very popular paradigm to ensure minimum throughput and bounded delay access for packet flows. It describes a packet scheduling approach to QoS provisioning in multihop networks by using minimum-degree greedy algorithm.

It proposes a new scheduling model which addresses the following additional features viz., (a) a Two-tier service model that provides a minimum “fair” allocation of the channel bandwidth for each packet flow and additionally maximizes spatial reuse of bandwidth, (b) an ideal centralized packet scheduling algorithm that realizes the above service model, and (c) a practical distributed back off based channel contention mechanism that approximates the ideal service within the framework of the ad-hoc network model [54]. Maximizing resource utilization is a critical parameter which supports effective communication-intensive applications, e.g., web browsing, video conferencing and remote transfer and etc.,

6.4 DESIGN

The design of Two-Tier Algorithm consists of two parts viz., a. Fairness and throughput in the basic channel and b. Implementation of the local fairness model.

6.4.1 FAIRNESS AND THROUGHPUT IN THE BASIC CHANNEL

Each backlogged flow will always receive a basic fair service by assuming that no spatial reuse was available. Hence each flow receives at least a fair share from the basic physical channel capacity C. Then both the long-term throughput and packet delay bounds are developed for a standard scheduler to hold the physical channel in ad-hoc networks connectivity.

6.4.2 IMPLEMENTATION OF THE LOCAL FAIRNESS MODEL

The major difference between the global fairness model and the local fairness model is the definition of basic fair share for each individual flow. Otherwise, both models can use identical algorithm to improve spatial channel reuse. For example simultaneous packet flow results in an independent set in ad-hoc networks, this can be done by using the back off-based approach ..

6.5 NUMERICAL RESULTS

The numerical results for Two-Tier Packet Scheduling Algorithm for 6 X 6 node connectivity is computed and presented in terms of input parameters like network connectivity, node connectivity and flow connectivity, are as shown in tables 6.2 and the output parameters like throughput ratio, spatial channel reuse are as shown in table 6.3. The node graph and corresponding flow graphs are illustrated in Fig. 6.6 and Fig. 6.7. By using network simulator (ns2) model the global fairness model of Two-Tier algorithm was achieved in terms of throughput and packet distribution in ad-hoc network connectivity as shown in Fig6.8.

In the previous work Nag T.S et.al. model resolved the simple transmission and reception of packets in terms of fair queuing. This model suffered from establishing multipath connectivity and also achieving the global fairness.

Hence the overall throughput is 95% as compared to 25% of the previous work.

6.6 DISCUSSIONS

The previous work by Nag T.S et.al. describes the simulations to Evaluate the performance of network layer connectivity with respect to Single period fair queuing. The present work TWO-Tier ALGORITHM Determines the connectivity for mutiperiod fairqueing and achieves the Global fairness model of optical ad-hoc networks.

In this network model maximum co-ordination of fair queuing in ad-hoc networks is achieved by the local and global parameters like node Connectivity, location - dependent and independent concepts, spatial Channel reuse, packet delivery system and local fairness and global Fairness. Network Architecture Logical Layer Survivability Parameters Module has been analyzed in this chapter. It can be extended further to evaluate the fair-queuing techniques by using Bounded Fair Multi-Level Queuing Packet scheduling algorithm discussed in the next chapter.

De: delay counter of a node

bn: back off value of node n

Transmitter

De = 0

bn = tree height

while bn > 0

bn ← bn - 1

else

De ← De + 1

Receiver

If collision occurs broadcast NO ACK

Table 6.1 Two-Tier Algorithm Parameters Comparison table

Algorithms

Issues

Two-Tier

Location-dependent

Contention

True

Spatial channel re use

True

Conflicts between

ensuring fairness & ensured

maximizing channel

utilization

True

Distributed nature n

True

Node mobility

False

Scalability

False

S: the set of nodes in the graph

V: a node in set G

N(v): adjacent node set of v

d(v): degree of node v

B: output set

B ß Ф

while S ≠ Ф

choose v such that d(v) = min d(ω), ω є s

B ß B υ v

S ß S - { { v} υ N (v)}

return B

bf : flow f's backoff value in mini slots

zf : allocated transmission slots for flow F

rf : flow f's weight

F : the flow set in flow contention graph

Kf: the number of packet transmission flow in present flow

d(f) : degree of flow in the graph

N(f) : neighborhood flow

global fairness

local fairness

Global fairness model zf ← sf (O)

Local fairness model zf ← random (tmp) and

Initializing time τ for flow f

Global fairness model zf ← sf kf

Local fairness model zf ← kf X tmp + random tmp

(1) Set D to NULL. For each flow, if the start tag of the head of line packet of a flow is not greater than

V (t) + LP,

then set the state of the flow to contend, else set the state of the flow to no-contend.

(2) If there is no flow in contend state, then add the flow with the minimum start tag to D and skip to the next step.Otherwise, while there are flows in the contend state,

select the flow f with the minimum finish tag of the head of line packet and add f to the set D.

Set all flows in the closed neighborhood of D, N [f], to no-contend.

(3) Update the virtual time V (t) to the maximum start tag of the head of line packets among flows in D. Update the start and finish tags of the flows in D.

(4) Select the maximum independent set S in the graph G - N [D].

(5) Schedule the flows in S D for transmission. Do not increment the start and finish tags of the flows in S.

6.2 Two Tier Packet Scheduling Algorithm

Table 6.2 Two-Tier Packet Scheduling Input Table

DEMAND CONNECTIVITY

LINK CONNECTIVITY

FLOW CONNECTIVITY

1

1-2

1-2,1-3,1-4,1-5

2

2-3

2-1,2-3,2-4,2-5

3

3-4

3-1,3-2,3-4,3-5

4

4-5

4-1,4-2,4-3,4-5

5

5-6

5-1,5-2,5-3,5-4

6

----

----

Table 6.3 Two-Tier Packet Scheduling Output Table

NODES

LOCATION DEPENDENT

THROUGHPUT (%)

200

SPATIAL CHANNEL REUSE (%)

100

FAIRNESS & MAXIMIZING CHANNEL

YES

NODE MOBILITY

NO

SCALABILITY

NO

Please be aware that the free essay that you were just reading was not written by us. This essay, and all of the others available to view on the website, were provided to us by students in exchange for services that we offer. This relationship helps our students to get an even better deal while also contributing to the biggest free essay resource in the UK!