Connection establishing management methods for traversing network address translation (NAT) routers and firewalls between network terminal devices to establish a connection channel therebetween for use in a network system including at least first, second and third network terminal devices and a traversal server are disclosed. First, when traversal server receives a call request of first and second network terminal devices, network topology levels of first and second network terminal devices are detected to detect whether first and second network terminal devices are located behind NAT router and/or firewall. Then, one of first and second network terminal devices or third network terminal device is selected according to the detection result such that selected network terminal device acted as proxy server for the traversal server to establish a connection channel corresponding to call request between first and second network terminal devices.