So for anyone who sees suspicious internet activity on his phone, here's how I figured it out:
I monitor my phone on random occasions (several times a day) using this amazing app called: SockStat (no conflict of interest).
When I just found this IP yesterday 18.104.22.168, I blocked everything on AFWall+ (Android open source firewall), this way, any app that tries to connect remotely will be logged (turn logging on if it's off).
In my case, I saw that WhatsApp+ tried to connect to the same IP that I'm investigating. Looked up the WhatsApp+ IP and yes, it's on SoftLayer network. Waited a bit, and finally captured what caused Root to connect! Same IP but this time, "(Kernel) - Linux kernel" is trying to connect to that IP.
From here, I'll email the developer* and ask how he got Root without requesting Root from Superuser app.
I still haven't figured out what is trying to connect to Baidu (22.214.171.124), but you get the idea from the first suspicious IP.
Hope this helps.
*WhatsApp+ is a third-party WhatsApp client. Not sure how it works under the hood though.