Apr 30 17:07:07 localhost kernel: [12265558.582378] r8169: eth0: link up
Apr 30 17:07:07 localhost NetworkManager: <info>  (eth0): carrier now ON (device state 1)
Apr 30 17:07:08 localhost kernel: [12265559.237961] r8169: eth0: link down
Apr 30 17:07:08 localhost NetworkManager: <info>  (eth0): carrier now OFF (device state 1)
Apr 30 17:07:11 localhost NetworkManager: <info>  (eth0): carrier now ON (device state 1)
Apr 30 17:07:11 localhost kernel: [12265562.162804] r8169: eth0: link up
Apr 30 17:07:11 localhost kernel: [12265562.577849] r8169: eth0: link down
Apr 30 17:07:12 localhost NetworkManager: <info>  (eth0): carrier now OFF (device state 1)
Apr 30 17:07:14 localhost kernel: [12265565.312582] r8169: eth0: link up
Apr 30 17:07:14 localhost NetworkManager: <info>  (eth0): carrier now ON (device state 1)

Apr 30 17:09:10 localhost kernel: [12265681.639307] r8169: eth0: link down
Apr 30 17:09:13 localhost kernel: [12265684.402984] r8169: eth0: link up
Apr 30 17:09:14 localhost kernel: [12265685.660805] r8169: eth0: link down
Apr 30 17:09:18 localhost kernel: [12265688.942400] r8169: eth0: link up
Apr 30 17:09:18 localhost kernel: [12265689.826486] r8169: eth0: link down
Apr 30 17:09:21 localhost kernel: [12265692.512789] r8169: eth0: link up
Apr 30 17:09:22 localhost kernel: [12265693.134914] r8169: eth0: link down
Apr 30 17:09:31 localhost kernel: [12265702.700430] r8169: eth0: link up
Apr 30 17:09:34 localhost kernel: [12265705.571668] r8169: eth0: link down
Apr 30 17:09:37 localhost kernel: [12265708.281532] r8169: eth0: link up

I was getting frustrated by when I checked the Cat5 cable it was a little bit loose on the NIC.  This is a case where any tug somewhere on the line knocked it loose.

So I would double check with your datacenter or if you can, physically check the server yourself to see if the NIC's RJ45 cable is actually plugged in snugly and fully seated.