I want to add custom link to topnavigation bar, this link will be common through out sitecollections and it should appear as the first link in navigation bar. I tried to override PortalSiteMapProvider but it is not working for me. Any suggestion in this regard will be highlt appreciated.
As you might know already the Top-Navigation bar is not cross site collections (Collaborative or Publishing). One alternative is to make your own Portal site map provider and use it in a custom master page or by using the Delegate control with your own (e.g. deploy a SiteMap physically, or a any other more dynamic variant). Many variations are available, more or less complex. Find some here:
If you only want a simple link, than maybe directly change the master page and it manually.
One other quicker alternative is also the Portal URL which is site collection configurable but it does appear outside of the Top bar and it is static!