Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

SUM OF DISJOINT PRODUCT

No description
by

saurab dubey

on 15 May 2014

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of SUM OF DISJOINT PRODUCT

SUM OF DISJOINT PRODUCT METHOD
INTRODUCTION
Reliability

Network reliability is a measure of the ability of a network to carry out a desired network operation.

Network reliability is usually based on whether the nodes, or the links between nodes, operate successfully.
NETWORK RELIABILTY
INTRODUCTION
TYPE OF NETWORK
NETWORK RELIABILITY EVALUATION
MINPATH
MINCUTS
SUM OF DISJOINT PRODUCT
KDH88 ALGORITHM
CAREL ALGORITHM
RELIABILITY OF MULTICAST NETWORK
EVENT TREE
FAULT TREE
LITERATURE REVIEW
PROBLEM IDENTIFICATION
RESEARCH OBJECTIVE
REFERENCES





CONTENT
CAPACITY RELATED RELIABILITY EVALUATION FOR MULTI-CAST NETWORK
TYPES OF NETWORK
On the basis of reliability network is classified as
.

MIN PATH
Pathset
A set of components (edges) whose operation implies (guarantees) system operation.

Minpath
A minimal Pathset
Ex.K={v1,v4}
Saurabh Dubey (12/PIT/090)
SCHOOL OF INFORMATION AND COMMUNICATION TECHNOLGY GAUTAM BUDDHA UNIVERSITY
Dr. Rajesh Mishra
Supervised By:

Presentation on M Tech Dissertation Part 1 Progress Work
Presented By:
Undirected Networks
Directed Networks
Mixed Networks

K = set of nodes
V = all nodes

MINCUTS
Cutset
A set of components (edges) whose failure implies (guarantees) system failure
Mincut
A minimal Cutset
Ex.K={v1,v4}

SDP are used to find out the reliability of Mesh type network.
SDP based approach is used to find out the reliability expression in more efficient and compact manner.
SDP are used to calculate the reliability of K-terminal network.

SDP
Approach implemented by using Boolean algebra
Ex. Two terminal reliability between v1, v4

Minpath: ab, cd, ade, bce

Can be expressed with the following Boolean expression:
AB V CD V ADE V BCE


R(G) = Pr [AB V CD V ADE V BCE =1]

Probability for each ∨path which operates
correctly can be simply calculated as follows:
Pr[AB]=papb, Pr[CD]=pcpd, ...

However, R(G) can not be directly
calculated when there exists Pr of the
paths which are not disjoint event
(exclusive).

RELIABILITY
CLASSIFICATION OF SDP
SVI Approach
In SVI approach wherein variables are inverted sequentially one at a time
In SVI minimization of the expression has been achieved through the pathset or cutset.
MVI Approach

In MVI approach a group of variables are inverted at once.
In MVI not only the ordering of pathset or cutset but the simultaneous inversions of a group of variables are inverted at once.

KDH88
KDH88 is an MVI extension of SVI algorithm proposed by Abraham. Using the min path sets, it recursively generates the terms for each path set.

Path sets : {(1,6), (2,7), (4,8), (1,3,7), (2,3,6), (2,5,8), (4,5,7), (1,3,5,8), (4,5,3,6)}
Cut sets : {(1,2,4), (6,7,8), (1,2,5,8), (1,3,7,8), (2,3,4,6), (4,5,6,7), (1,3,4,5,7), (2,3,5,6,8)}

Let path number seven i.e. {4,5,7} be made disjoint with all its predecessors. KDH88 would be

{(1-P1)*(1-P2)*(1-P8)*P4*P 5*P8 + P1*(1-P2)*(1-P8)*(1-P3)*(1-P6) *P4*P5*P7 }

CAREL ALGORITHM AND MULTICAST NETWORK RELIABILITY
CAREL ALGORITHM
CAREL algorithm is proposed by (Soh& Rai-91), it uses the boolean algebraic manipulation.

It proposing 4 operators
COMpare
REDuce
CoMBine
GENerate




ALGORITHM
IS
For all the path sets Ti, i= 1, 2, 3, … m
Obtain conditional cube (CC) set by eliminating the common element present.
Obtain minimal conditional cube set (MCC) i.e. if conditional cube set then MCC divides into two group i.e. IG & DG
IG = 2nd and 3rd term
DG = 1st and 4th term

Compute TR (Terminal Reliability)

Path sets {(1,6), (2,7), (4,8), (1,3,7), (2,3,6), (2,5,8), (4,5,7), (1,3,5,8), (4,5,3,6)}

For path set number 7 CAREL would be
(1-P1)*(1-P2)*(1-P8)*P4* P5* P7 + P1 (1-P3)*(1-P6)*(1-P2)*(1-P8)*P4* P5* P7
 


EVENT TREE ANALYSIS
We can say that multicast network is a type of tree type network
So the reliability of multicast network would be calculated by
Event Tree
Fault Tree
MUTICAST NETWORK RELIABILITY
Event tree is an inductive analytical diagram in which an event is analyzed using Boolean logic to examine a chronological series of subsequent events or consequences. Example

FAULT TREE ANALYSIS
What ?
A structured team analysis of the possible underlying causes of a known equipment failure.
When ?
root cause analysis of a failure is needed
Why?
- (outcomes)
A better understanding of the root causes of a failure.
A better set of action plans to eliminate those root causes.

Fault tree analysis is an effect and cause diagram that uses standard symbols developed in the defense industry and is used heavily in safety engineering. FTA is a structured approach for analyzing the root causes of a failure mode not yet fully understood.

EXAMPLE OF FAULT TREE
LITERATURE SURVEY
PROBLEM IDENTIFICATION
According to above literature survey the following problems are identifies.

In multicast network replicate copy of data is saved at the sender, so the overhead (buffer) is increased at the source or intermediate nodes (router). It needs flow based reliability algorithms for avoiding the congestion in these nodes.
When a group is form in a multicast network simultaneously if a member joins or leaves the group every time access control and authentication will require. Finally, it is required an efficient reliable-flow-mobility based protocols.
In the multicast network the group is dynamic so rekeying is required, Further few factors i.e. energy consumption, security, congestion, and packet drop problems arises due to unreliable behavior of these networks . Here it is required to proper connectivity between all source, destination, and intermediate nodes for reducing these factors effects.
The approaches those are mention in the literature are not efficient for multicast network in the terms of delay, congestion, availability, reliability, security etc. So Qos based approaches may further enhanced.

RESEARCH OBJECTIVE
REFERENCES
[1] Chandrasheker T. and N.K. Goyal, An approach to evaluate multiple node pair reliability for simultaneous capacity requirements, International Journal of Performability Engineering, vol. 9, no. 4, pp. 340-350, 2013.

[2] Hassan M.R., Reliability evaluation of multi-source multi-sink stochastic-flow network under quickest path and system capacity constraints, SDIWC, vol. 12, no. 3, pp. 166-172, 2013.

[3] Mishra R. and S.K. Chaturvedi, A cutset based unified framework to evaluate network reliability measures, IEEE Transaction on Reliability, vol. 58, no. 4, pp. 658-666, 2009

[4] Aggarwal K.K., A fast flgorithm for the performance index of a telecommunication network, IEEE Trans. Reliability, vol.37, no. 1, pp. 65-69, 1988.

[5] Cook J.L. and J.E. Ramirez, Reliability of capacitated mobile ad hoc networks, Journal of risk and reliability, vol.221, no. 2 pp. 307-17, 2007.

Base paper- Chandrasheker T. and N.K. Goyal, An Approach to Evaluate Multiple Node Pair Reliability for Simultaneous Capacity Requirements, international journal of performability Engineering,Vol.9,month,2013.

In this paper author proposed a cut set based approach to evaluate reliability of multi node pair capacity related reliable (MNPCRR) network.
It helps network designers in assessing and optimizing network performance with effectiveness.
The reliability measure considering both connectivity and capacity as success criteria for a node pair is called capacity related reliability

Aggarwal K.K., A Fast Algorithm for the Performance Index of a Telecommunication Network. IEEE Trans. Reliability., apr. 1988; R-37(1):65-69.

In this paper author suggest a faster method for deriving the symbolic expression of performance index in a compact form, because the capacity of several sub networks must be computed, an efficient procedure for capacity determination is also suggested.

Hassan M.R., Reliability Evaluation of Multi-Source Multi-Sink Stochastic-flow Network under Quickest Path And, System Capacity constrains.

In this paper author present an algorithm to determine the probability called system reliability for source-sink pair.

RESEARCH GAPS

This approach is help full for finding the reliability of K terminal simultaneously. It will not applicable to find the reliability of multiple node or all node.
This approach is not use full for multicast network in the terms of Delay Congestion & Availability.

RESEARCH GAP

In this paper author does not discuss the issues of delay and congestion in network.

Based on above observations the following major objective are set:

To study the multicast network reliability.
To proposed an modified algorithm for evaluation of multicast network reliability.
Compare and validate the result by using event tree analysis

[
7] Huang N., Dong H., Chen H.Y., Xing L. and R. Kang, A network reliability evaluation method based on application and topological structure, Maintenance and Reliability, vol.54, no. 3, pp. 77-83, 2011

8] Cook J.L., Picatinny A. and J.E. Ramirez- Marquez, “Capacitated reliability for ad-hoc network”, under U.S. Government research work, 2007.

[9] Soh Siesteng and Suresh Rai, An efficient cutset approach for evaluating communication-network reliability with heterogeneous link-capacities, IEEE Transactions on Reliability, vol. 54, no. 1,pp. 133-144, 2005.

[10] Rai Suresh, Veerarghavan and K.S. Trivedi, A survey of efficient reliability computation using disjoint products approach Networks, John Wiley & Sons, Inc.,vol. 25, pp. 147-163, 1995.

[11] Soh S., Rai S. and R.R. Brooks, “Performance issues in wireless communication network”, issues Handbook of Performability Engineering, pp. 1047-1067, 2008.

[12] Villavarde B.C., Rea S. and D. Pesch, “In Route – A QoS aware route selection algorithm for industrial wireless sensor networks”, Journal of Ad Hoc Networks, pp. 1-25, 2011.

THANK YOU
k-terminal reliability
Probability that there exist operating paths between every pair of nodes in K

Two terminal reliability
Probability that there exist operating path between 2 nodes (|K| = 2)

All terminal reliability
Probability that there exist operating paths between all nodes (K=V)
Full transcript