Virtual Private Network (VPN) is a logic network established on top of a public packet switched network. Previous research works on VPN mainly focused on security issues, such as tunneling, encryption/decryption and authentication. To guarantee that customers’ QoS requirements specified by customers can be met, the network service provider needs to reserve enough network resources on the network, and allocate/manage them in an optimal way. Traffic engineering algorithms can be used by the network service provider to establish multiple VPNs in an optimal way, while meeting customers’ QoS requirements. Previous works on VPN traffic engineering focus on meeting bandwidth guarantees, however, for some network applications, such as VOIP and IPTV, meeting delay requirement is one of another vital issue. To our knowledge until now, issues about traffic engineering for establishing VPNs meeting both bandwidth and delay requirements have not been investigated. In this paper, we proposed a novel VPN traffic engineering algorithm for establishing hose model VPNs with delay requirements. According to experimental simulations conducted our algorithm achieved better performance compared to previous ones.