Why do ICMP Redirect Host happen?

At first blush, it looks like Debian is stretching the boundaries for sending an ICMP redirect; quoting RFC 792 (Internet Protocol).

  The gateway sends a redirect message to a host in the following

  situation.  A gateway, G1, receives an internet datagram from a
  host on a network to which the gateway is attached.  The gateway,
  G1, checks its routing table and obtains the address of the next
  gateway, G2, on the route to the datagram's internet destination
  network, X.  If G2 and the host identified by the internet source
  address of the datagram are on the same network, a redirect
  message is sent to the host.  The redirect message advises the
  host to send its traffic for network X directly to gateway G2 as
  this is a shorter path to the destination.  The gateway forwards
  the original datagram's data to its internet destination.

In this case, G1 is 10.1.2.1 (eth1:0 above), X is 10.1.1.0/24 and G2 is 10.1.1.12, and the source is 10.1.2.20 (i.e. G2 and the host identified by the internet source address of the datagram are **NOT** on the same network). Maybe this has been historically interpreted differently in the case of interface aliases (or secondary addresses) on the same interface, but strictly speaking I'm not sure we should see Debian send that redirect.

Depending on your requirements, you might be able to solve this by making the subnet for eth1 something like 10.1.0.0/22 (host addresses from 10.1.0.1 - 10.1.3.254) instead of using interface aliases for individual /24 blocks (eth1, eth1:0, eth1:1, eth1:2); if you did this, you'll need to change the netmask of all hosts attached and you wouldn't be able to use 10.1.4.x unless you expanded to a /21.

EDIT

We're venturing a bit outside the scope of the original question, but I'll help work through the design/security issues mentioned in your comment.

If you want to isolate users in your office from each other, let's step back for a second and look at some security issues with what you have now:

You currently have four subnets in one ethernet broadcast domain. All users in one broadcast domain doesn't meet the security requirements you articulated in the comments (all machines will see broadcasts from other machines and could spontaneously send traffic to each other at Layer2, regardless of their default gateway being eth1, eth1:0, eth1:1 or eth1:2). There is nothing your Debian firewall can do to change this (or maybe I should say there is nothing your Debian firewall should do to change this :-).

• You need to assign users into Vlans, based on security policy stated in the comments. A properly-configured Vlan will go a long way to fixing the issues mentioned above. If your ethernet switch doesn't support Vlans, you should get one that does.
• With respect to multiple security domains accessing 10.1.1.12, you have a couple of options:
  • Option 1: Given the requirement for all users to access services on 10.1.1.12, you could put all users in one IP subnet and implement security policies with Private Vlans (RFC 5517), assuming your ethernet switch supports this. This option will not require iptables rules to limit intra-office traffic from crossing security boundaries (that is accomplished with private Vlans).
  • Option 2: You could put users into different subnets (corresponding to Vlans) and implement iptables rules to deploy your security policies
• After you have secured your network at the Vlan level, set up source-based routing policies to send different users out your multiple uplinks.

FYI, if you have a router that supports VRFs, some of this gets even easier; IIRC, you have a Cisco IOS machine onsite. Depending on the model and software image you already have, that Cisco could do a fantastic job isolating your users from each other and implement source-based routing policies.

It is not really clear what you are trying to do, but I can say the following.

These subnets are connected to the same physical interface. The Linux router will return ICMP redirect message when the received packet should be forwarded over the same physical interface.

I agree with Khaled's comments and would also add to end of his phrase:

"These subnets are connected to the same physical interface. The Linux router will return ICMP redirect message when the received packet should be forwarded over the same physical interface" to the same destination subnet then redirecting the request to the next hop. That happen to me today using a Mikrotik linux router and an F5 bigip LTM device.

root@(primaryadc)(cfg-sync In Sync)(Standby)(/Common)(tmos)# ping 8.8.8.8
PING 8.8.8.8 (8.8.8.8) 56(84) bytes of data.
From 192.168.153.20: icmp_seq=1 Redirect Host(New nexthop: 192.168.153.2)
64 bytes from 8.8.8.8: icmp_seq=1 ttl=128 time=82.8 ms
From 192.168.153.20: icmp_seq=2 Redirect Host(New nexthop: 192.168.153.2)
64 bytes from 8.8.8.8: icmp_seq=2 ttl=128 time=123 ms
**routing table**
0.0.0.0  192.168.153.20  0.0.0.0         UG        0 0          0 external