  We identify a set of dynamical maps of open quantum system, and refer to them
as "$ \epsilon $-Markovian" maps. It is constituted of maps which, in a higher
dimensional system-environment Hilbert space, possibly violate Born
approximation but only a "little". We characterize the
"$\epsilon$-nonmarkovianity" of a general dynamical map by the minimum distance
of that map from the set of $\epsilon$-Markovian maps. We analytically derive
an inequality which gives a bound on the $ \epsilon$-nonmarkovianity of the
dynamical map, in terms of an entanglement-like resource generated between the
system and its "immediate" environment. In the special case of a vanishing
$\epsilon$, this inequality gives a relation between the
$\epsilon$-nonmarkovianity of the reduced dynamical map on the system and the
entanglement generated between the system and its immediate environment. We
numerically investigate the behavior of the similar distant based measures of
non-Markovianity for classes of amplitude damping and phase damping channels.
