Defence is seeking to improve efficiency and to redirect gains to military capability and higher priority requirements.
The Regional Information and Communications Technology Market Testing Project released a request for tender (RFT) in July 2005.
Negotiations are expected to end in August 2007.
"Subject to a successful outcome, implementation of service delivery could begin in late 2007," a department spokesperson said.