Android wifi says "Connected, no internet" but internet works just fine This is a strange thing that started happening with the wifi network at my work.  Android devices connected to the network say "Connected, no internet" however the internet works perfectly well.  This has happened to devices running android 6 and 7.  This is a small business in the US and theres no proxy or captive portal that is blocking any DNS.  Windows and Ubuntu laptops connect and say everything is fine, seems to be something Android specific.  

Does anyone know how exactly Android determines weather a network has internet access?  This seems like the solution will end up in the router configuration, but knowing what could cause Android to behave this way would be helpful.  What steps could one take to troubleshoot this issue?
Perhaps this seems likely to be a problem connecting to Google servers (captive portal server) not the browser configured captive portal login you seem to be refering to in your post.

(Sometime since Lollipop (5.1+)) When connected to networks (especially Wi-Fi networks), android system  checks if there is an active internet connection by perfoming checks on certain pre-defined URLs belonging to Google servers. If it fails, there'll be an exclamation mark on the Wi-Fi signal icon and a  “Connected, no internet” notification is shown (even though you can access other websites and the internet is up an running) so it may be a temporary problem with connectivity to that specific URL:


  Android tries to reach a file named generate_204 on one of the Google
  servers and if there is no positive response, it means that there is
  no connection to the internet, and notification is generated also, the detection url differs between
  different Android versions.



clients3.google.com/generate_204 check (kitkat)
connectivitycheck.gstatic.com/generate_204 (marshmallow)


It seems that google has changed the captive portal 
detection on recent  versions of android e.g oreo. 

looks like google now checks for both a generate_204 on both 
connectivitycheck.gstatic.com and a gen_204 on 
www.google.com.

Again is a problem on its own esp in regions where access to google services is blocked. This answer however explains well how to bypass such and you make take a look at it.

A chunk of information has been extracted from this discussion.

Based on this you have some options to bypass this:


Changing captive portal server 


Install a terminal app alternatively these  commands can also be run via the adb shell.
Open the terminal app and run su. 
Run settings get global captive_portal_server. This will show the current captive portal server. A "null" reply is usually the default.
Run settings put global captive_portal_server YOUR_SERVER_ADDRESS. You can  add google.com as the captive portal server, i.e settings put global captive_portal_server google.com.
Run exit once to exit from su, then exit one more time to close the terminal.
Reboot the Android device. Will not work without a reboot.






Disabling captive portal 



  
  Since the culprit is a method isCaptivePortal() which access clients3.google.com/generate_204 to test if a connection is deemed
  "usable". The page, as its name suggest, is designed to always return
  a HTTP 204 status code. Based on this you have a couple options:
  


i. Kill isCaptivePortal() completely


with adb set, run adb shell su -c "settings put global captive_portal_detection_enabled 0" (Android 7.1+)
or using adb shell su -c "settings put global captive_portal_mode 0"


Note:  The down side is that isCaptivePortal() is actually useful to detect for example when a WiFi network requires login. If the request to the 204 page gets redirected to a login page (not a 204), the system will understand and display the exclamation mark as intended.

ii. Change the target of isCaptivePortal()


another workaround is replacing the Google host with a host that is accessible within the specific region. This host should also be returning 204 every time /generate_204 is accessed.

i.e adb shell su -c "settings put global captive_portal_server {alternate_host} "





Using hosts


You can edit hosts to block the captive portal detection url thus bypassing the sending of the requests to captive portal server.





Why Linux and Windows connect with no issues?

As you mentioned in your post that this seems to be Android specific, indeed the above discussion highlights that. The reason is that for those devices (Linux and Windows) the mechanism of connection is completely different.

These devices won't need to connect to Google servers to first detect if an internet is active.