30-10-2012, 05:24 PM
Link Failure Monitoring via Network Coding
Link Failure Monitoring.pdf (Size: 688.33 KB / Downloads: 26)
Abstract
In network tomography, we seek to infer link status
parameters (delay, congestion, loss rates etc.) inside a network
through end-to-end measurements at (external) boundary nodes.
As can be expected, such approaches generically suffer from
identifiability problems; i.e., status of links in a large number of
network topologies is not identifiable.We introduce an innovative
approach based on linear network coding that overcomes this
problem. We provide sufficient conditions on network coding
coefficients and training sequence under which any logical
network is guaranteed to be identifiable. In addition, we show that
it is possible to locate any congested link inside a network during
an arbitrary amount of time by increasing size of transmitted
packets, leading to raise in complexity of the method. Further, a
probability of success is provided for a random network. OPNET
is used to implement the concept and confirm the validity of the
claims - simulation results confirm that LNC correctly detects
the congested link in situations where standard probing based
algorithm fails.
INTRODUCTION
The need for accurate and fast network monitoring method
has increased further in recent years due to the complexity of
new services (such as video-conferencing, Internet telephony,
and on-line games) that require high-level quality-of-service
(QoS) guarantees. This would help network engineers and
Internet Service Providers (ISP) to keep track of network utilization
and performance. The term network tomography was
coined by Vardi [1] to encompass these class of approaches
that seek to infer internal link parameters and identify link
congestion status.
TOMOGRAPHY WITH LINEAR NETWORK CODING
In principle, Linear Network Coding (LNC) is a block code
operating on IP layer frames, implemented by routers inside
the network. The coding is conducted over the finite field
F2q whereby each coded symbol can be represented by q-bits
within an IP layer frame[15]. For the sake of simplicity, we
initially consider a delay-free network as in [16], [17], [18]
in which information reaches every node instantaneously; our
method is readily adapted to a real network where links have
finite (non-zero) delay using the buffering method proposed in
[18]. LNC has been exploited in [19] and [20] to infer network
topology. Consistent with these approaches, we assume that in
addition to LNC coefficients at each node, destination nodes
are aware of the entire network topology.
SIMULATION RESULTS
In this Section we briefly describe our LNC simulator [24]
constructed within OPNETTM14.5 aided by Matlab 7.1 that is
used for finite field calculations necessary for network coding.
The simulation results from applying the proposed link failure
monitoring scheme to the network in Fig. 1 (which is not
identifiable by end-to-end measurements) is presented. Finally,
we apply the method to the network graph for the University
of Washington’s Electrical Engineering department network of
servers and present identifiability results.
Simulation Environment
Ours is the first known implementation of Network Coding
(NC) within OPNET. OPNET was selected because of its
wide acceptance as a network modeling tool within both the
academic and commercial communities [25].
We employed network coding at transport layer (instead of
IP layer) largely for convenience - it readily allows adding
hidden data within the TCP/UDP frame in OPNET, which is
invisible to the end-user and to the simulation statistics [24].
Any binary vector of length q, can be interpreted as an element
in F2q , the finite field with 2q elements. In our network coding
implementation, we assign a q-bit field called LNC field within
the TCP/UDP header, for linear network coding. Only the
contents in LNC field is used for network coding operation.
In addition, a 1-bit flag within TCP/UDP header determines if
the packet is a network coding packet. Once a router receives
a packet, it identifies the packet type by looking at the 1-bit
flag embedded in TCP/UDP header. If the packet is a networkcoded
packet, the data in LNC field is extracted and queued
at a buffer for a predetermined amount of time after which
they are combined and the router clears the buffer. The result
of linear combining is written in LNC field of the outgoing
packet which is forwarded on all of the outgoing links via
unidirectional broadcast.
CONCLUSION
This work has presented a novel approach to link status
monitoring based on a deterministic approach that exploits
LNC at the internal nodes in a network. The key problem
of identifiability for such approaches was highlighted and
various insights provided regarding this concept. New sufficient
conditions were derived for successfully identifying a
congested link in any logical network, and trade-offs between
length of training slots and size of the network coding alphabet
established.