An appropriate call admission control in the next generation wireless networks is expected to make efficient use of scarce wireless resource and improve quality-of-service, while supporting multimedia services. On one hand, blocking handoff calls is normally more annoying than blocking new calls. On the other hand, blocking new calls reduces resource utilization. More importantly, handoff call arrival rate depends strongly on call holding time. A novel Call-Holding-Time-Based Random Early Blocking (CHTREB) scheme is proposed to achieve the aforesaid goals in a two-tier cellular voice/data network. With CHTREB, new calls are accepted according to some acceptance probability taking into account the call hloding time difference between voice and data calls. An iterative algorithm is developed to calculate performance measures of interest, i.e., new call blocking probability and forced termination probability. First, simulation results are shown to verify analytical results. Then, numerical results are presented to show the robustness of CHTREB. It is found that CHTREB outperforms TR and CHTREB-FAP under both stationary and nonstationary traffic scenarios. Last but not least, the studied 2-tier system is compared with 1-tier counterpart. It is shown that 2-tier system performs better in terms of average number of handoffs per data call.