The Kuru king Pandu's (Pāṇḍu) second wife was from Madra kingdom and was called Madri (Sanskrit: माद्री; IAST: Mādrī; IPA/Sanskrit: [maːd̪ɽiː]).
According to the Vayu Purana, the Madra kingdom was founded by King Ushinara Shibi of the Anu race.
The name Bahlika is also used to denote a kingdom different from Madra, Sindhu, Kekeya, Gandhāra & Kamboja.
The Kuru king Shantanu, a forefather of Kauravas and Pandavas, had a brother who ruled the Bahlika kingdom.
Their horses and even horsemen were used in the wars between kings of Aryavarta (North Indian kingdoms where Vedic culture of the norm, prevailed).
Another collective name denoting the western kingdoms is Arashtra or Aratta, meaning a kingless country.
This raises the doubt, whether these countries were a republic ruled by elected chiefs, if we take the positive sense of the word.
The Yavanas, the Kiratas, the Chinas, the Savaras, the Barbaras, the Sakas, the Tusharas, the Kankas, the Pathavas, the Andhras, the Madrakas, the Paundras, the Pulindas, the Ramathas, the Kamvojas were mentioned together as tribes beyond the kingdoms of Aryavarta.
(12,64)[3][4] The Andrakas, Guhas, Pulindas, Savaras, Chuchukas, Madrakas, the Yamas, Kamvojas, Kiratas and Barbaras were mentioned as unknown tribes.
Upon which Shalya replies:- "There is a custom in our family observed by our ancestors, which, be it good or bad, I am incapable of transgressing it.
Pandava Sahadeva married Vijaya, the daughter of Dyutimat, the king of Madra, obtaining her in a self-choice ceremony and begat upon her a son named Suhotra.
Thus the royal line of Malavas originated from the Madra (Punjab province of Pakistan) king Aswapati (3,297).
He was the oldest spear-fighter battled in Kurukshetra War.Bhima had defeated Shalya in mace-fight without knowing each other during the self-choice ceremony of Draupadi (1,192).
And the mighty hero, proceeding thence to Sakala, the city of the Madras, made his uncle Shalya accept from affection the sway of the Pandavas.
His troops marched slowly on every day from Madra (Punjab province of Pakistan) to Upaplavya (somewhere on the border of Rajasthan and Haryana), the Matsya city, where the Pandavas were camped.
The Madra soldiers also received payment from Duryodhana's officers for taking part in the Kurukshetra War.
During the time of the Gupta Empire, the Indian emperor Samudragupta (ruled 350-375 CE) recorded Madraka as a "frontier kingdom" which paid an annual tribute.
"Samudragupta, whose formidable rule was propitiated with the payment of all tributes, execution of orders and visits (to his court) for obeisance by such frontier rulers as those of Samataṭa, Ḍavāka, Kāmarūpa, Nēpāla, and Kartṛipura, and, by the Mālavas, Ārjunāyanas, Yaudhēyas, Mādrakas, Ābhīras, Prārjunas, Sanakānīkas, Kākas, Kharaparikas , Karna and other nations"