  In this paper we improve the approximation ratio for the problem of
scheduling packets on line networks with bounded buffers, where the aim is that
of maximizing the throughput. Each node in the network has a local buffer of
bounded size $B$, and each edge (or link) can transmit a limited number, $c$,
of packets in every time unit. The input to the problem consists of a set of
packet requests, each defined by a source node, a destination node, and a
release time. We denote by $n$ the size of the network. A solution for this
problem is a schedule that delivers (some of the) packets to their destinations
without violating the capacity constraints of the network (buffers or edges).
Our goal is to design an efficient algorithm that computes a schedule that
maximizes the number of packets that arrive to their respective destinations.
  We give a randomized approximation algorithm with constant approximation
ratio for the case where $B=\Theta(c)$. This improves over the previously best
result of $O(\log^* n)$ (R\"acke and Ros\'en, Theory Comput. Syst., 49(4),
2011). Our improvement is based on a new combinatorial lemma that we prove,
stating, roughly speaking, that if packets are allowed to stay put in buffers
only a limited number of time steps, $2d$, where $d$ is the longest
source-destination distance of any input packet, then the cardinality of the
optimal solution is decreased by only a constant factor. This claim was not
previously known in the directed integral (i.e., unsplittable, zero-one) case,
and may find additional applications for routing and scheduling algorithms.
