Well, I have implemented OpenStreetMap with OsmDroid SDK, but having trouble to find open source routing SDK for Android. I would appreciate any help on that.
Note: I know OSRM-server implementation just works fine, but we have server problem. And OSRM public servers gets down frequently, hence not reliable for our use case.
P.S. how frequently OSRM public server gets down?
Any public/free server is probably 'best effort' without guarantees. Only when there is a commercial option with a paid tier that you may be able to get a service level agreement (SLA) about how frequently the service is unavailable.
In short: Create your own OSRM-server implementation on hardware you pay for and maintain to get the availability you want.