If the Chinese sources are not clear about ancient links, I recommend visiting the Maritime Experiential Museum in Sentosa Singapore. The museum outlines the ancient maritime trade routes with south India being the centre of the spice trade in ancient times where spices were transported from southern India/Ceylon to Rome, Greece in the west and to China in the east.
The Southern kingdom were ruled by three dynasties - Cholas, Pandyas and Cheras. These dynasties are very old, the oldest known inscription is by Emperor Ashoka in 250BC who refers to all three kingdoms who were apart from being the oldest continuing culture in India also refused to submit to emperor Ashoka's rule. Ashoka did however send his son Mahinda to Ceylon who introduced buddhism to the island.
Prior to buddhism the hindu kingdoms of the south had long contact with the east Asia through trade but also through settlement. Sanskrit and Tamil words have entered language of all South Eastern Asian languages from ancient times.
Europeans boast of having the world's first maritime empire but this is clearly not true, If you visit the Sentosa museum you will see the Tamils had the world's first maritime empire that stretched from India all the way to China. An interesting observation that supports this ancient connection is the number of coastal cities from Spain all the way to Phillipines that seem to start with letters "Ma"
One of the earliest kingdoms established by the ancient Tamils is Malaya. In Tamil the land of Malaya was so named because if you arrived by ship from the west the first thing you see are mountains which in Tamil is Melayu which is actually still the name the locals call themselves including the name of the country (Tamil - Land of mountains).
In ancient times the names of cities that traded with Tamils might be still retained in modern place names. For example in Spain you have Madrid then by ship you hit Malta, then if you keep going through the Suez canal you come to the island of Madagascar. A days journey north and you come to the islands of Maldives with it's capital Male. By sea you reach malaya. Interestingly the old name filipino people take is "Malagasy". The Javanese empire at the time was called Majapit.
