Why GCP Cloud NAT needs BGP/Cloud Router?
Cloud Router enables you to dynamically exchange routes between your Virtual Private Cloud (VPC) and on-premises networks by using Border Gateway Protocol (BGP)
You configure a NAT gateway on a Cloud Router, which provides the control plane for NAT, holding configuration parameters that you specify.
Each Cloud NAT gateway is associated with a single VPC network, region, and Cloud Router.
In my understanding, NAT maps between private address/port to public ip/port, and forward the mapped packet to the Internet Gateway (to get out to the Internet). Where and why does BGP (Cloud Router) come into play in this picture?
There is a structural difference between typical NAT and Google Cloud NAT. Typical NATs use NAT proxy instances between cloud instances and their destination, but in Google Cloud NAT, there’s no proxy, rather, it uses software defined networking where a unique set of NAT IPs and port-ranges are assigned to each of the internal instances. Cloud Router is used as the abstraction to which the NAT configuration is attached. Note that it does not require BGP configuration when being used to support Cloud NAT. Also, Cloud NAT does not use ASN information. Cloud NAT gateways can be connected to Cloud Routers that have any ASN or that have no ASN at all.
Check here for more information.
Cloud NAT uses Cloud Router only to group NAT configuration information (control plane). Cloud NAT does not direct a Cloud Router to use BGP or to add routes. NAT traffic does not pass through a Cloud Router (data plane).
https://cloud.google.com/nat/docs/set-up-network-address-translation
It is because Cloud Router provides the control plane for NAT and holds the configuration parameters that you specify.
It is clearly mentioned here.