We use palo-alto firewall as an internet gateway. We have 16 static ip-addresses. One is used for outbound traffic (users browse internet) . The rest is used for inbound traffic (mail server, webservers, etc). For redundant purposes we subscribe to second ISP. We buy 16 new static ip-addresses from new ISP. And here comes the hell with configuration. I've been reading for two days about BGP, PI addresses, AS numbers and other stuff. But I don't understand anything. Theory without practice and overall understanding is nothing. I call to these ISP's, and both providers say they won't configure any routes and won't sell AS numbers, try solve it by your selves. In our small asian country there is no LISP or any other cloud base routing solution. I don't know what to do next. Should I request AS number directly from APNIC? With policy based rules I may only configure outbound traffic redundancy. Is there any reliable solution to make redundant our small hosting? May it is possible to configure BGP without AS numbers and PI addresses?
Even if you could still get PI IPv4 addresses in Asia: if your ISPs don't want to route your IP addresses then there is nothing you can do. Tunnels and LISP could solve some of your problems (I use LISP here), but you already stated that this is not available in your region.
BGP is the protocol that is used to route your IP addresses from an AS. You need both to run BGP. Blocks of 16 addresses are too small to be routed with BGP anyway. Technically you could, but nobody will accept your routes.
If you want to have your own IP addresses and route them etc. you'll have to make some investments. Because APNIC ran out of IPv4 addresses for normal distribution you'll have to comply with some very strict rules. If I recall correctly the current rules are that you have to be multihomed already, must be able to justify 25% of the addresses (which would be 25% of 256 = 64) immediately and 50% (=128) within a year. Based on your current numbers that seems unlikely. If you could then you'd need to get an AS number from APNIC and you'll have to find ISPs that want to set up BGP sessions with you. This will probably be more expensive than your current contracts. And on top of that you'd have to study a lot to learn how internet routing and BGP works or you'll have to hire someone else to manage it for you. In addition to buying the equipment needed to do all of this.
In short: it's probably not worth it for your case.
You can configure a Palo Alto Networks firewall to fail over to the other ISP. You need to set up two sets of NATs -- one for one ISP and one for the other -- or set two DMZs, one for one ISP and one for the other (or overlay two subnets on one interface). It will use both for inbound and will fail over to the second for outbound when one fails.
You can start reading here.
There is some way to load balancing without AS and PI.
For outbound it achieved by policy routing
For failover inbound traffic, is good to use dynamic DNS. When primary ISP changed, DNS name (with short enough TTL) of site changed to new IP and clients keep access to site.
Setting DNS to two IP simultaneous can make round robin IP selection on clients.
Periodical changing (with period near to DNS record TTL) between two IP also can make balancing. Same effect is using DNS server that support giving different IP to different clients.