with an intelligence-gathering mission on a Russian merchant vessel in Canadian waters, escorting her to the entrance of Juan de Fuca Strait. In December, Algonquin prepared for a refit with scheduled completion of April 1998. Algonquin began her refit costing $25 million in mid-January 2007. The ship returned to service in May 1998. On 24 August 1999, the ship was doing trials with a private MiG-21 aircraft when the aircraft crashed into the ocean. A fuel slick and debris was found in the search area but nothing more and after 24 hours the search was terminated. Later that week Algonquin, in consort with the Canadian Coast Guard, was tasked to intercept, track and board an illegal Chinese migrant vessel. The vessel was escorted to Gold River, British Columbia where 159 migrants were received by the Royal Canadian Mounted Police for medical and legal processing. 2000s The ship deployed for WESTPLOY 00 in April 2000. On departing Qingdao, Algonquin and Winnipeg conducted the first military exercise by a Western nation with China. In June, the ship participated in RIMPAC 00 with 54 ships and over 20,000 sailors from Australia, Canada, Chile, Japan, Korea and the United States. In 2001, Algonquin continued the duties of flagship for the Commander Canadian Fleet Pacific. As such, Algonquin took part in naval exercises and work-ups in a busy preparation period for Operation Apollo and conducted joint exercises with the Australian, New Zealand and United States navies. Algonquin continued the duties of flagship for the Commander Canadian Fleet Pacific. As such, Algonquin took part in Operation Apollo and completed a highly successful mission in the Gulf of Oman. She made port visits in Hawaii, Saipan, Guam, Malaysia, Thailand, Hong Kong and United Arab Emirates. On 4 March, the destroyer deployed for the Gulf of Oman, in support of Operation Apollo, conducting her mission on 1 May through 4 September. On 14 October, the ship returned to Esquimalt, having been away for almost seven months in the Persian Gulf and logging . During the operation Algonquin hailed over 1,700 vessels and boarded 55. She carried out 96 inspections of 'go-fast vessels', and discovered and apprehended several suspected terrorists. Algonquin conducted a short port visit to Peddar Bay on 21 November, and returned to Esquimlat Harbour for a short refit period. From March to August 2003 Algonquin was under refit by Victoria Shipyards. She rejoined the Pacific Fleet