Re: ECMP/multipath support

2011-01-09 Thread Joakim Tjernlund 

   Something else, in calc_next_hop:
   don't you need to return all next hops for ptmp links now that you
   support ECMP?
  
  The same as in ptp or bcast - multiple next hops are created
  by compositing returns of calc_next_hop(). Look at the caller
  of calc_next_hop().
 
  Don't think it will work as intended(I am traveling and only have mail 
  access)
  but I think the find_neigh(ifa, rid);
  will always find the same neighbor so any additional links
  will be missed.

 Still think you need to do something like this:

This one doesn't require changes to originate_rt_lsa_body()
Just that the neighbour list doesn't change between originate_rt_lsa_body
and calc_next_hop.

From ee7096e741617292df5ea96f5f366b99a2bcd135 Mon Sep 17 00:00:00 2001
From: Joakim Tjernlund joakim.tjernl...@transmode.se
Date: Sun, 9 Jan 2011 15:45:18 +0100
Subject: [PATCH] find correct IP address for PTMP I/Fs in calc_next_hop

Currently calc_next_hop searches for the next hop IP
with RID as search key. This will not work when there
are multiple links with the same RID.

Signed-off-by: Joakim Tjernlund joakim.tjernl...@transmode.se
---
 proto/ospf/rt.c |   13 +++--
 1 files changed, 11 insertions(+), 2 deletions(-)

diff --git a/proto/ospf/rt.c b/proto/ospf/rt.c
index 2f9fe49..e136aa3 100644
--- a/proto/ospf/rt.c
+++ b/proto/ospf/rt.c
@@ -1360,6 +1360,9 @@ calc_next_hop(struct ospf_area *oa, struct top_hash_entry 
*en,
   /* The second case - ptp or ptmp neighbor */
   if ((en-lsa.type == LSA_T_RT)  (par == oa-rt))
   {
+struct ospf_neighbor *m;
+s16 n_pos;
+
 ifa = rt_pos_to_ifa(oa, pos);
 if (!ifa)
   return NULL;
@@ -1367,8 +1370,14 @@ calc_next_hop(struct ospf_area *oa, struct 
top_hash_entry *en,
 if (ifa-type == OSPF_IT_VLINK)
   return new_nexthop(po, IPA_NONE, NULL, 0);

-struct ospf_neighbor *m = find_neigh(ifa, rid);
-if (!m || (m-state != NEIGHBOR_FULL))
+n_pos = ifa-rt_pos_beg;
+WALK_LIST(m, ifa-neigh_list) {
+  if (m-state != NEIGHBOR_FULL)
+   continue;
+  if (n_pos++ == pos)
+   break;
+}
+if (!m || m-rid != rid) /* Check rid just to be sure */
   return NULL;

 return new_nexthop(po, m-ip, ifa-iface, ifa-ecmp_weight);
--
1.7.3.4

Re: ECMP/multipath support

2011-01-06 Thread Ondrej Zajicek 
On Mon, Jan 03, 2011 at 05:37:25PM +0100, Joakim Tjernlund wrote:
   Any plans to add support for Opaque LSAs/GMPLS in the near future?
 
  Nothing specific. Where (and how) is this feature used?
 
 We have an old zebra based GMPLS TE (using RSVP too) to allocate
 paths through our network. Don't know much about it(yet) but
 if we were to move to BIRD we would need support for this.

I don't know much about GMPLS. I wonder for what purpose,
in which cases and on what hardware (and software) is that used?

 Something else, in calc_next_hop:
 don't you need to return all next hops for ptmp links now that you
 support ECMP?

The same as in ptp or bcast - multiple next hops are created
by compositing returns of calc_next_hop(). Look at the caller
of calc_next_hop().

-- 
Elen sila lumenn' omentielvo

Ondrej 'SanTiago' Zajicek (email: santi...@crfreenet.org)
OpenPGP encrypted e-mails preferred (KeyID 0x11DEADC3, wwwkeys.pgp.net)
To err is human -- to blame it on a computer is even more so.


signature.asc
Description: Digital signature

Re: ECMP/multipath support

2011-01-06 Thread Joakim Tjernlund 
-Ondrej Zajicek santi...@crfreenet.org wrote: -


On Mon, Jan 03, 2011 at 05:37:25PM +0100, Joakim Tjernlund wrote:
   Any plans to add support for Opaque LSAs/GMPLS in the near future?
 
  Nothing specific. Where (and how) is this feature used?
 
 We have an old zebra based GMPLS TE (using RSVP too) to allocate
 paths through our network. Don't know much about it(yet) but
 if we were to move to BIRD we would need support for this.

I don't know much about GMPLS. I wonder for what purpose,
in which cases and on what hardware (and software) is that used?

I have to get back on that.


 Something else, in calc_next_hop:
 don't you need to return all next hops for ptmp links now that you
 support ECMP?

The same as in ptp or bcast - multiple next hops are created
by compositing returns of calc_next_hop(). Look at the caller
of calc_next_hop().

Don't think it will work as intended(I am traveling and only have mail access)
but I think the find_neigh(ifa, rid);
will always find the same neighbor so any additional links
will be missed.

 Jocke

Re: ECMP/multipath support

2011-01-03 Thread Joakim Tjernlund 
Ondrej Zajicek santi...@crfreenet.org wrote on 2011/01/01 10:51:03:

 On Thu, Dec 30, 2010 at 02:17:24AM +0100, Joakim Tjernlund wrote:
  Ah, good to hear.
 
  Any plans to add support for Opaque LSAs/GMPLS in the near future?

 Nothing specific. Where (and how) is this feature used?

We have an old zebra based GMPLS TE (using RSVP too) to allocate
paths through our network. Don't know much about it(yet) but
if we were to move to BIRD we would need support for this.

Something else, in calc_next_hop:
struct ospf_neighbor *m = find_neigh(ifa, rid);
if (!m || (m-state != NEIGHBOR_FULL))
   return NULL;

return new_nexthop(po, m-ip, ifa-iface, ifa-ecmp_weight);

don't you need to return all next hops for ptmp links now that you
support ECMP?

 Jocke

Re: ECMP/multipath support

2011-01-01 Thread Ondrej Zajicek 
On Thu, Dec 30, 2010 at 02:17:24AM +0100, Joakim Tjernlund wrote:
 Ah, good to hear.
 
 Any plans to add support for Opaque LSAs/GMPLS in the near future?

Nothing specific. Where (and how) is this feature used?

 BTW, I think the README could use an update:
  This software should be considered a beta version. It has undergone 
 extensive
   testing by the authors, but since it's the first public release, only a 
 limited
   amount of real life experience is known and there still might be problems
   with operation in unusual environments.
 
 I am sure BIRD has come a long way beyond beta :)

You are right.

-- 
Elen sila lumenn' omentielvo

Ondrej 'SanTiago' Zajicek (email: santi...@crfreenet.org)
OpenPGP encrypted e-mails preferred (KeyID 0x11DEADC3, wwwkeys.pgp.net)
To err is human -- to blame it on a computer is even more so.


signature.asc
Description: Digital signature

Re: ECMP/multipath support

2010-12-29 Thread Joakim Tjernlund 
 Ondrej Zajicek santi...@crfreenet.org wrote on 2010/12/28 10:00:03:
 
  On Tue, Dec 28, 2010 at 02:12:53AM +0100, Joakim Tjernlund wrote:
   Right, some comments:
  
   - px_pos* is redundant. Just use rt_pos* for both V4 and V6.
 
  rt_pos* is a position in Router-LSA, px_pos* is a position in
  Rt Prefix-LSA. In IPv6, we use both and they might be different.

 Ah, now I see. You took the concept one step further.

How does the lsa pos in add_network work for ac_stubnet_list?
Stubnet lists does not have en interface connected, perhaps ac_stubnet_list
isn't applicable for add_network?

 Jocke

Re: ECMP/multipath support

2010-12-29 Thread Ondrej Zajicek 
On Wed, Dec 29, 2010 at 10:21:58PM +0100, Joakim Tjernlund wrote:
  Ah, now I see. You took the concept one step further.
 
 How does the lsa pos in add_network work for ac_stubnet_list?
 Stubnet lists does not have en interface connected, perhaps ac_stubnet_list
 isn't applicable for add_network?

Local stubnet lists aren't back-propagated to main table. So the
behavior is the same as before, they got NULL iface in add_network
and are later eliminated.

-- 
Elen sila lumenn' omentielvo

Ondrej 'SanTiago' Zajicek (email: santi...@crfreenet.org)
OpenPGP encrypted e-mails preferred (KeyID 0x11DEADC3, wwwkeys.pgp.net)
To err is human -- to blame it on a computer is even more so.


signature.asc
Description: Digital signature

Re: ECMP/multipath support

2010-12-29 Thread Joakim Tjernlund 
Ondrej Zajicek santi...@crfreenet.org wrote on 2010/12/30 01:55:34:

 On Wed, Dec 29, 2010 at 10:21:58PM +0100, Joakim Tjernlund wrote:
   Ah, now I see. You took the concept one step further.
 
  How does the lsa pos in add_network work for ac_stubnet_list?
  Stubnet lists does not have en interface connected, perhaps ac_stubnet_list
  isn't applicable for add_network?

 Local stubnet lists aren't back-propagated to main table. So the
 behavior is the same as before, they got NULL iface in add_network
 and are later eliminated.

Ah, good to hear.

Any plans to add support for Opaque LSAs/GMPLS in the near future?

 Jocke

BTW, I think the README could use an update:
 This software should be considered a beta version. It has undergone extensive
  testing by the authors, but since it's the first public release, only a 
limited
  amount of real life experience is known and there still might be problems
  with operation in unusual environments.

I am sure BIRD has come a long way beyond beta :)

Re: ECMP/multipath support

2010-12-28 Thread Ondrej Zajicek 
On Tue, Dec 28, 2010 at 02:12:53AM +0100, Joakim Tjernlund wrote:
 Right, some comments:
 
 - px_pos* is redundant. Just use rt_pos* for both V4 and V6.

rt_pos* is a position in Router-LSA, px_pos* is a position in
Rt Prefix-LSA. In IPv6, we use both and they might be different.

 - You can use u16 instead of s16, just in case you get a lot of I/Fs :)
   (use ~0 instead of -1 were needed)

You cannot have that problem, because size of OSPF packet (and one LSA)
is limited by 64k.

-- 
Elen sila lumenn' omentielvo

Ondrej 'SanTiago' Zajicek (email: santi...@crfreenet.org)
OpenPGP encrypted e-mails preferred (KeyID 0x11DEADC3, wwwkeys.pgp.net)
To err is human -- to blame it on a computer is even more so.


signature.asc
Description: Digital signature

Re: ECMP/multipath support

2010-12-28 Thread Joakim Tjernlund 
Ondrej Zajicek santi...@crfreenet.org wrote on 2010/12/28 10:00:03:

 On Tue, Dec 28, 2010 at 02:12:53AM +0100, Joakim Tjernlund wrote:
  Right, some comments:
 
  - px_pos* is redundant. Just use rt_pos* for both V4 and V6.

 rt_pos* is a position in Router-LSA, px_pos* is a position in
 Rt Prefix-LSA. In IPv6, we use both and they might be different.

Ah, now I see. You took the concept one step further.


  - You can use u16 instead of s16, just in case you get a lot of I/Fs :)
(use ~0 instead of -1 were needed)

 You cannot have that problem, because size of OSPF packet (and one LSA)
 is limited by 64k.

Right, was half a joke.

 Jocke

Re: ECMP/multipath support

2010-12-27 Thread Joakim Tjernlund 
   Other packets are sent to the neighbor IP address, which is a slight
   diversion from RFC 2328, but should not cause any problems.
 
  But a stricter router may reject OSPF msg over an ptp links if
  they aren't addressed to AllSPFRouters.

 I just noticed you impl. a PTMP I/F type, nice :)

I updated to new nexhp calc. patch to match your latest
changes. I hope you like it.
From b2d4b0fc32df60f0ae0e5db1d18de647ea62ae3e Mon Sep 17 00:00:00 2001
From: Joakim Tjernlund joakim.tjernl...@transmode.se
Date: Fri, 17 Dec 2010 10:03:32 +0100
Subject: [PATCH 1/2] ospf: improve nexthop_calc

Record the lsa position in the router LSA and
use that to find the right interface in calc_next_hop()
Remove match_rtlink and match_dr too as these are not
needed anymore

Signed-off-by: Joakim Tjernlund joakim.tjernl...@transmode.se
---
 proto/ospf/iface.c|4 ++-
 proto/ospf/ospf.h |   21 
 proto/ospf/rt.c   |   63 ++---
 proto/ospf/topology.c |5 ++-
 4 files changed, 45 insertions(+), 48 deletions(-)

diff --git a/proto/ospf/iface.c b/proto/ospf/iface.c
index 05442df..6fc0136 100644
--- a/proto/ospf/iface.c
+++ b/proto/ospf/iface.c
@@ -197,6 +197,8 @@ ospf_iface_down(struct ospf_iface *ifa)
 ifa-cost = 0;
 ifa-vip = IPA_NONE;
   }
+  /* delete position in router LSA */
+  ospf_lsa_pos_set(0, 0, ifa);
 }


@@ -412,7 +414,7 @@ ospf_iface_new(struct proto_ospf *po, struct iface *iface, 
struct ifa *addr,
   ifa-iface = iface;
   ifa-addr = addr;
   ifa-pool = pool;
-
+  ospf_lsa_pos_set(0, 0, ifa);
   ifa-cost = ip-cost;
   ifa-rxmtint = ip-rxmtint;
   ifa-inftransdelay = ip-inftransdelay;
diff --git a/proto/ospf/ospf.h b/proto/ospf/ospf.h
index e260dc0..71071cd 100644
--- a/proto/ospf/ospf.h
+++ b/proto/ospf/ospf.h
@@ -190,6 +190,8 @@ struct ospf_iface
   u32 csn;  /* Last used crypt seq number */
   bird_clock_t csn_use; /* Last time when packet with that CSN was 
sent */
 #endif
+  u32 lsa_pos_beg; /* inclusive, = */
+  u32 lsa_pos_end; /* exclusive,   */

   ip_addr drip;/* Designated router */
   ip_addr bdrip;   /* Backup DR */
@@ -823,6 +825,25 @@ void ospf_sh_iface(struct proto *p, char *iff);
 void ospf_sh_state(struct proto *p, int verbose, int reachable);
 void ospf_sh_lsadb(struct proto *p);

+static inline struct ospf_iface *
+ospf_pos_to_ifa (struct ospf_area *oa, int lsa_pos)
+{
+struct proto_ospf *po = oa-po;
+struct ospf_iface *ifa;
+
+WALK_LIST(ifa, po-iface_list)
+   if (lsa_pos = ifa-lsa_pos_beg  lsa_pos  ifa-lsa_pos_end)
+   return ifa;
+return NULL;
+}
+
+static inline void
+ospf_lsa_pos_set(int beg, int end,
+struct ospf_iface * ifa)
+{
+ifa-lsa_pos_beg = beg;
+ifa-lsa_pos_end = end;
+}

 #define EA_OSPF_METRIC1EA_CODE(EAP_OSPF, 0)
 #define EA_OSPF_METRIC2EA_CODE(EAP_OSPF, 1)
diff --git a/proto/ospf/rt.c b/proto/ospf/rt.c
index 953a679..84fea16 100644
--- a/proto/ospf/rt.c
+++ b/proto/ospf/rt.c
@@ -10,7 +10,7 @@

 static void add_cand(list * l, struct top_hash_entry *en,
 struct top_hash_entry *par, u32 dist,
-struct ospf_area *oa, struct ospf_lsa_rt_link *rtl);
+struct ospf_area *oa, struct ospf_lsa_rt_link *rtl, u32 
pos);
 static void rt_sync(struct proto_ospf *po);

 /* In ospf_area-rtr we store paths to routers, but we use RID (and not IP 
address)
@@ -396,7 +396,7 @@ ospf_rt_spfa_rtlinks(struct ospf_area *oa, struct 
top_hash_entry *act, struct to
   if (tmp)
DBG(Going to add cand, Mydist: %u, Req: %u\n,
tmp-dist, act-dist + rtl-metric);
-  add_cand(oa-cand, tmp, act, act-dist + rtl-metric, oa, rtl);
+  add_cand(oa-cand, tmp, act, act-dist + rtl-metric, oa, rtl, i);
 }
 }

@@ -494,7 +494,7 @@ ospf_rt_spfa(struct ospf_area *oa)
  DBG(Found :-)\n);
else
  DBG(Not found!\n);
-   add_cand(oa-cand, tmp, act, act-dist, oa, NULL);
+   add_cand(oa-cand, tmp, act, act-dist, oa, NULL, i);
   }
   break;
 }
@@ -1325,32 +1325,6 @@ ospf_rt_spf(struct proto_ospf *po)
   po-calcrt = 0;
 }

-
-static inline int
-match_dr(struct ospf_iface *ifa, struct top_hash_entry *en)
-{
-#ifdef OSPFv2
-  return (ifa-drid == en-lsa.rt)  (ipa_to_u32(ifa-drip) == en-lsa.id);
-#else /* OSPFv3 */
-  return (ifa-drid == en-lsa.rt)  (ifa-dr_iface_id == en-lsa.id);
-#endif
-}
-
-
-static inline int
-match_rtlink(struct ospf_iface *ifa, struct ospf_lsa_rt_link *rtl)
-{
-#ifdef OSPFv2
-  return ((ifa-type == OSPF_IT_PTP) || (ifa-type == OSPF_IT_PTMP)) 
-(ifa-cost == rtl-metric) 
-(((ifa-addr-flags  IA_UNNUMBERED) ? ifa-iface-index :
-  ipa_to_u32(ifa-addr-ip)) == rtl-data);
-#else /* OSPFv3 */
-  return ((ifa-type == OSPF_IT_PTP) || (ifa-type == OSPF_IT_PTMP)) 
-(ifa-cost == rtl-metric)  (ifa-iface-index == rtl-lif);
-#endif
-}
-
 static inline int

Re: ECMP/multipath support

2010-12-27 Thread Ondrej Zajicek 
On Mon, Dec 27, 2010 at 08:06:17PM +0100, Joakim Tjernlund wrote:
Other packets are sent to the neighbor IP address, which is a slight
diversion from RFC 2328, but should not cause any problems.
  
   But a stricter router may reject OSPF msg over an ptp links if
   they aren't addressed to AllSPFRouters.
 
  I just noticed you impl. a PTMP I/F type, nice :)
 
 I updated to new nexhp calc. patch to match your latest
 changes. I hope you like it.

I already done that, just didn't commited it yet, sorry.
Now it is merged (after some rework and extending).

-- 
Elen sila lumenn' omentielvo

Ondrej 'SanTiago' Zajicek (email: santi...@crfreenet.org)
OpenPGP encrypted e-mails preferred (KeyID 0x11DEADC3, wwwkeys.pgp.net)
To err is human -- to blame it on a computer is even more so.


signature.asc
Description: Digital signature

Re: ECMP/multipath support

2010-12-27 Thread Ondrej Zajicek 
On Tue, Dec 28, 2010 at 01:15:28AM +0100, Joakim Tjernlund wrote:
 
 Other packets are sent to the neighbor IP address, which is a slight
 diversion from RFC 2328, but should not cause any problems.
   
But a stricter router may reject OSPF msg over an ptp links if
they aren't addressed to AllSPFRouters.
  
   I just noticed you impl. a PTMP I/F type, nice :)
 
  I updated to new nexhp calc. patch to match your latest
  changes. I hope you like it.
 
 Did some more spf improvements. Lets see if you like these too:

 +  /* The first case - local network */
 +  if (en-lsa.type == LSA_T_NET)
 +   return new_nexthop(po, IPA_NONE, ifa-iface, ifa-ecmp_weight);
 +
 +  /* The second case - ptp or ptmp neighbor */
 +  if (en-lsa.type == LSA_T_RT)
 +  {
 +   if (ifa-type == OSPF_IT_PTP)
 +   return new_nexthop(po, ifa-addr-opposite, ifa-iface,
 +  ifa-ecmp_weight);

As i wrote 21 Dec 2010 11:42:56, this is not correct, opposite might
be undefined.

-- 
Elen sila lumenn' omentielvo

Ondrej 'SanTiago' Zajicek (email: santi...@crfreenet.org)
OpenPGP encrypted e-mails preferred (KeyID 0x11DEADC3, wwwkeys.pgp.net)
To err is human -- to blame it on a computer is even more so.


signature.asc
Description: Digital signature

Re: ECMP/multipath support

2010-12-27 Thread Joakim Tjernlund 
Ondrej Zajicek santi...@crfreenet.org wrote on 2010/12/28 01:55:42:

 On Tue, Dec 28, 2010 at 01:15:28AM +0100, Joakim Tjernlund wrote:
  
  Other packets are sent to the neighbor IP address, which is a slight
  diversion from RFC 2328, but should not cause any problems.

 But a stricter router may reject OSPF msg over an ptp links if
 they aren't addressed to AllSPFRouters.
   
I just noticed you impl. a PTMP I/F type, nice :)
  
   I updated to new nexhp calc. patch to match your latest
   changes. I hope you like it.
 
  Did some more spf improvements. Lets see if you like these too:

  +  /* The first case - local network */
  +  if (en-lsa.type == LSA_T_NET)
  + return new_nexthop(po, IPA_NONE, ifa-iface, ifa-ecmp_weight);
  +
  +  /* The second case - ptp or ptmp neighbor */
  +  if (en-lsa.type == LSA_T_RT)
  +  {
  + if (ifa-type == OSPF_IT_PTP)
  + return new_nexthop(po, ifa-addr-opposite, ifa-iface,
  + ifa-ecmp_weight);

 As i wrote 21 Dec 2010 11:42:56, this is not correct, opposite might

Right, forgot about that. What do you think of the other changes?
especially the goto bad; changes and the if (par == oa-rt) { /* par is root ? 
*/
test to simplify the code?

 Jocke

Re: ECMP/multipath support

2010-12-21 Thread Joakim Tjernlund 
Ondrej Zajicek santi...@crfreenet.org wrote on 2010/12/21 03:24:23:

 On Tue, Dec 21, 2010 at 01:22:48AM +0100, Joakim Tjernlund wrote:
   For PTP iface, the list contains at most one entry (so the scan is fast
   :-) ) and you have to examine it anyways to know neighbor's IP address.
 
  Yes, it is a small improvement I guess and you would find the remote
  IP address, if there is one, by following the ifa ptr.

 You cannot get remote IP address just from ifa - you can have ethernet
 network with (e.g.) /24 IP prefix configured as ptp iface (which is OK
 if there is just two routers on that network).

Oh, so opposite in
struct ifa {
  ..
  ip_addr opposite; /* Opposite end of a point-to-point 
link */

does not contain an IP address in this case?

Jocke

Re: ECMP/multipath support

2010-12-21 Thread Joakim Tjernlund 
Ondrej Zajicek santi...@crfreenet.org wrote on 2010/12/21 00:27:44:

 On Fri, Dec 17, 2010 at 02:02:07PM +0100, Joakim Tjernlund wrote:
  
   Something like this. It is not tested at all and and very simple.
 
  Here is version 2, even simpler :)

 That is nice, makes several things simpler. I will merge that,
 with some minor modifications.

Found a bug, here is a fix:

---
 proto/ospf/topology.c |7 +--
 1 files changed, 5 insertions(+), 2 deletions(-)

diff --git a/proto/ospf/topology.c b/proto/ospf/topology.c
index 32fcc5e..94847f8 100644
--- a/proto/ospf/topology.c
+++ b/proto/ospf/topology.c
@@ -228,7 +228,7 @@ originate_rt_lsa_body(struct ospf_area *oa, u16 *length)

   WALK_LIST(ifa, po-iface_list)
   {
-int net_lsa = 0;
+int net_lsa = 0, rt_pos = ~0;

 if ((ifa-type == OSPF_IT_VLINK)  (ifa-voa == oa) 
(!EMPTY_LIST(ifa-neigh_list)))
@@ -254,6 +254,7 @@ originate_rt_lsa_body(struct ospf_area *oa, u16 *length)
ifa-iface-index : ipa_to_u32(ifa-addr-ip);
  ln-metric = ifa-cost;
  ln-padding = 0;
+ rt_pos = i;
  i++;
}
break;
@@ -268,6 +269,7 @@ originate_rt_lsa_body(struct ospf_area *oa, u16 *length)
ln-data = ipa_to_u32(ifa-addr-ip);
ln-metric = ifa-cost;
ln-padding = 0;
+   rt_pos = i;
i++;
net_lsa = 1;
  }
@@ -283,6 +285,7 @@ originate_rt_lsa_body(struct ospf_area *oa, u16 *length)
  ln-data = ipa_to_u32(ifa-addr-ip);
  ln-metric = ifa-cost;
  ln-padding = 0;
+ rt_pos = i;
  i++;
 }
 break;
@@ -291,7 +294,7 @@ originate_rt_lsa_body(struct ospf_area *oa, u16 *length)
 log(Unknown interface type %s, ifa-iface-name);
 break;
   }
-ospf_lsa_pos_set(i, ifa);
+ospf_lsa_pos_set(rt_pos, ifa);
 /* Now we will originate stub area if there is no primary */
 if (net_lsa ||
(ifa-type == OSPF_IT_VLINK) ||
--
1.7.2.5

Re: ECMP/multipath support

2010-12-20 Thread Ondrej Zajicek 
On Fri, Dec 17, 2010 at 09:03:01AM +0100, Joakim Tjernlund wrote:
 I don't remember all the details anymore but sharing IP address for numbered
 ptp I/Fs is not pathological.

Having two independent networks with the same IP prefix seems pretty
pathological to me.

 It should just work. Also any combination of
 numbered vs. unnumbered, IP address or no IP address(even pppd supports no IP 
 address
 on ptp links).

You can really use ptp link without any IP address (in Linux)?

-- 
Elen sila lumenn' omentielvo

Ondrej 'SanTiago' Zajicek (email: santi...@crfreenet.org)
OpenPGP encrypted e-mails preferred (KeyID 0x11DEADC3, wwwkeys.pgp.net)
To err is human -- to blame it on a computer is even more so.


signature.asc
Description: Digital signature

Re: ECMP/multipath support

2010-12-20 Thread Joakim Tjernlund 
Ondrej Zajicek santi...@crfreenet.org wrote on 2010/12/21 00:22:26:

 On Fri, Dec 17, 2010 at 09:03:01AM +0100, Joakim Tjernlund wrote:
  I don't remember all the details anymore but sharing IP address for numbered
  ptp I/Fs is not pathological.

 Having two independent networks with the same IP prefix seems pretty
 pathological to me.

No, it works fine when you don't have real unnumbered. The only difference in
the extra entry in the router LSA for numbered PtP links.

In any case, if someone does it should just work. I don't recall OSPF says
it should not work.


  It should just work. Also any combination of
  numbered vs. unnumbered, IP address or no IP address(even pppd supports no 
  IP address
  on ptp links).

 You can really use ptp link without any IP address (in Linux)?

not me(yet) but look at pppd commit log
http://git.ozlabs.org/?p=ppp.git;a=commit;h=eee67a89b6e5703a54a21ef835c383c139ef76c3

Re: ECMP/multipath support

2010-12-20 Thread Joakim Tjernlund 
Ondrej Zajicek santi...@crfreenet.org wrote on 2010/12/21 00:27:44:

 On Fri, Dec 17, 2010 at 02:02:07PM +0100, Joakim Tjernlund wrote:
  
   Something like this. It is not tested at all and and very simple.
 
  Here is version 2, even simpler :)

 That is nice, makes several things simpler. I will merge that,
 with some minor modifications.

Yes :) It will also always work and do the right thing.
There is an more advanced impl. that doesn't have to scan the IF list but
that is too much work for me.

Perhaps you can add PTP IF type too?

 Jocke

Re: ECMP/multipath support

2010-12-20 Thread Ondrej Zajicek 
On Tue, Dec 21, 2010 at 12:25:49AM +0100, Joakim Tjernlund wrote:
 Perhaps you can add PTP IF type too?

PTP is supported, do you mean PTMP?

-- 
Elen sila lumenn' omentielvo

Ondrej 'SanTiago' Zajicek (email: santi...@crfreenet.org)
OpenPGP encrypted e-mails preferred (KeyID 0x11DEADC3, wwwkeys.pgp.net)
To err is human -- to blame it on a computer is even more so.


signature.asc
Description: Digital signature

Re: ECMP/multipath support

2010-12-20 Thread Joakim Tjernlund 
Ondrej Zajicek santi...@crfreenet.org wrote on 2010/12/21 00:40:50:

 On Tue, Dec 21, 2010 at 12:25:49AM +0100, Joakim Tjernlund wrote:
  Perhaps you can add PTP IF type too?

 PTP is supported, do you mean PTMP?

I meant a #define OSPF_IT_MPTP xx so one knows
if it is a ptmp and ptp link. For ptp links you don't have to
scan the neighbour list in calc_next_hop

Re: ECMP/multipath support

2010-12-20 Thread Joakim Tjernlund 
Ondrej Zajicek santi...@crfreenet.org wrote on 2010/12/21 00:59:18:

 On Fri, Dec 17, 2010 at 02:36:50PM +0100, Joakim Tjernlund wrote:
  Question:
 
  in calc_next_hop() does this* match
   16.1.1 para 5. ...the parent vertex is a network that
   directly connects the calculating router to the destination
   router.  The list of next hops is then determined by
   examining the destination's router-LSA...

 ..

  Should not OSPF add a nexthop for ALL links that point back:
  ...For each link in the router-LSA that points back to the
  parent network, the link's Link Data field provides the IP
  address of a next hop router.  The outgoing interface to
  use can then be derived from the next hop IP address (or
  it can be inherited from the parent network).

 Not sure what you exactly mean. For a common scenario when
 there are two (or more) parallel links between two routers,
 multihop is used, because calc_next_hop() is called each time
 for each link and the results are merged.

Not this one.

 Or if you means case like: Router A having two interfaces (with IP1 and
 IP2)  connected to the same network N, router B also connected to
 network N may use multihop to IP1 and IP2 for routes that goes through
 router A. It is true that in that case BIRD does not use multihop (and
 there are some other corner cases, where multihop also is not used
 although it could be).

yes, this one. Seems like multihop only works for ptp links then ?
perhaps not a big deal? I would think users of ECMP would like this case
to work too though.

 Jocke

Re: ECMP/multipath support

2010-12-20 Thread Ondrej Zajicek 
On Tue, Dec 21, 2010 at 01:22:48AM +0100, Joakim Tjernlund wrote:
  For PTP iface, the list contains at most one entry (so the scan is fast
  :-) ) and you have to examine it anyways to know neighbor's IP address.
 
 Yes, it is a small improvement I guess and you would find the remote
 IP address, if there is one, by following the ifa ptr.

You cannot get remote IP address just from ifa - you can have ethernet
network with (e.g.) /24 IP prefix configured as ptp iface (which is OK
if there is just two routers on that network).

-- 
Elen sila lumenn' omentielvo

Ondrej 'SanTiago' Zajicek (email: santi...@crfreenet.org)
OpenPGP encrypted e-mails preferred (KeyID 0x11DEADC3, wwwkeys.pgp.net)
To err is human -- to blame it on a computer is even more so.


signature.asc
Description: Digital signature

Re: ECMP/multipath support

2010-12-17 Thread Joakim Tjernlund 
Ondrej Zajicek santi...@crfreenet.org wrote on 2010/12/17 00:50:41:

 On Thu, Dec 16, 2010 at 08:41:24PM +0100, Joakim Tjernlund wrote:
  This will find any ptp link that matches and several of them will match.

 Not really. For unnumbered ptp links (where sharing of IP addresses
 between several interfaces is common), the match is based on interface
 ID, which is unique. For numbered ptp links, the match is based on
 IP address, but in that case sharing IP addresses (and therefore
 network prefixes) is pathological and would cause other problems.

I don't remember all the details anymore but sharing IP address for numbered
ptp I/Fs is not pathological. It should just work. Also any combination of
numbered vs. unnumbered, IP address or no IP address(even pppd supports no IP 
address
on ptp links).
If you do it my way you can combine ptp links any way you want and it will 
scale better too.

   Jocke

Re: ECMP/multipath support

2010-12-17 Thread Joakim Tjernlund 


owner-bird-us...@atrey.karlin.mff.cuni.cz wrote on 2010/12/17 12:10:55:

 From: Joakim Tjernlund joakim.tjernl...@transmode.se
 To:
 Cc: Andrew Lemin andrew.le...@monitorsoft.com, Vincent Bernat 
 ber...@luffy.cx, bird-us...@trubka.network.cz, Ondrej Zajicek 
 santi...@crfreenet.org
 Date: 2010/12/17 12:11
 Subject: Re: ECMP/multipath support
 Sent by: owner-bird-us...@atrey.karlin.mff.cuni.cz

 
  Ondrej Zajicek santi...@crfreenet.org wrote on 2010/12/17 00:50:41:
  
   On Thu, Dec 16, 2010 at 08:41:24PM +0100, Joakim Tjernlund wrote:
This will find any ptp link that matches and several of them will match.
  
   Not really. For unnumbered ptp links (where sharing of IP addresses
   between several interfaces is common), the match is based on interface
   ID, which is unique. For numbered ptp links, the match is based on
   IP address, but in that case sharing IP addresses (and therefore
   network prefixes) is pathological and would cause other problems.
 
  I don't remember all the details anymore but sharing IP address for numbered
  ptp I/Fs is not pathological. It should just work. Also any combination of
  numbered vs. unnumbered, IP address or no IP address(even pppd supports no 
  IP address
  on ptp links).
  If you do it my way you can combine ptp links any way you want and it will 
  scale better too.
 

 Something like this. It is not tested at all and and very simple.

Here is version 2, even simpler :)

From d8b6396afe0e6eae255b8bd536de61c898569c40 Mon Sep 17 00:00:00 2001
From: Joakim Tjernlund joakim.tjernl...@transmode.se
Date: Fri, 17 Dec 2010 10:03:32 +0100
Subject: [PATCH] ospf: improve nexthop_calc, v2

This could be made more efficient if one added an
OSPF_IT_PTMP interface type. Then you don't have to look
for a neighbour in calc_next_hop()

Signed-off-by: Joakim Tjernlund joakim.tjernl...@transmode.se
---
 proto/ospf/iface.c|4 +++-
 proto/ospf/ospf.h |   18 ++
 proto/ospf/rt.c   |   38 ++
 proto/ospf/topology.c |2 +-
 4 files changed, 40 insertions(+), 22 deletions(-)

diff --git a/proto/ospf/iface.c b/proto/ospf/iface.c
index 8b21f94..b74418d 100644
--- a/proto/ospf/iface.c
+++ b/proto/ospf/iface.c
@@ -203,6 +203,8 @@ ospf_iface_down(struct ospf_iface *ifa)
 ifa-cost = 0;
 ifa-vip = IPA_NONE;
   }
+  /* delete position in router LSA */
+  ospf_lsa_pos_set(~0, ifa);
 }


@@ -422,7 +424,7 @@ ospf_iface_new(struct proto_ospf *po, struct iface *iface, 
struct ifa *addr,
   ifa-iface = iface;
   ifa-addr = addr;
   ifa-pool = pool;
-
+  ospf_lsa_pos_set(~0, ifa);
   ifa-cost = ip-cost;
   ifa-rxmtint = ip-rxmtint;
   ifa-inftransdelay = ip-inftransdelay;
diff --git a/proto/ospf/ospf.h b/proto/ospf/ospf.h
index 2ef0180..f785ee0 100644
--- a/proto/ospf/ospf.h
+++ b/proto/ospf/ospf.h
@@ -189,6 +189,7 @@ struct ospf_iface
   u32 csn;  /* Last used crypt seq number */
   bird_clock_t csn_use; /* Last time when packet with that CSN was 
sent */
 #endif
+  u32 rt_lsa_pos;   /* position in router lsa */

   ip_addr drip;/* Designated router */
   ip_addr bdrip;   /* Backup DR */
@@ -821,6 +822,23 @@ void ospf_sh_iface(struct proto *p, char *iff);
 void ospf_sh_state(struct proto *p, int verbose, int reachable);
 void ospf_sh_lsadb(struct proto *p);

+static inline struct ospf_iface *
+ospf_pos_to_ifa (struct ospf_area *oa, int lsa_pos)
+{
+struct proto_ospf *po = oa-po;
+struct ospf_iface *ifa;
+
+WALK_LIST(ifa, po-iface_list)
+   if (lsa_pos == ifa-rt_lsa_pos)
+   return ifa;
+return NULL;
+}
+
+static inline void
+ospf_lsa_pos_set(u32 rt_pos, struct ospf_iface * ifa)
+{
+ifa-rt_lsa_pos = rt_pos;
+}

 #define EA_OSPF_METRIC1EA_CODE(EAP_OSPF, 0)
 #define EA_OSPF_METRIC2EA_CODE(EAP_OSPF, 1)
diff --git a/proto/ospf/rt.c b/proto/ospf/rt.c
index 6b8886b..d2857dc 100644
--- a/proto/ospf/rt.c
+++ b/proto/ospf/rt.c
@@ -10,7 +10,7 @@

 static void add_cand(list * l, struct top_hash_entry *en,
 struct top_hash_entry *par, u32 dist,
-struct ospf_area *oa, struct ospf_lsa_rt_link *rtl);
+struct ospf_area *oa, struct ospf_lsa_rt_link *rtl, u32 
pos);
 static void rt_sync(struct proto_ospf *po);

 /* In ospf_area-rtr we store paths to routers, but we use RID (and not IP 
address)
@@ -396,7 +396,7 @@ ospf_rt_spfa_rtlinks(struct ospf_area *oa, struct 
top_hash_entry *act, struct to
   if (tmp)
DBG(Going to add cand, Mydist: %u, Req: %u\n,
tmp-dist, act-dist + rtl-metric);
-  add_cand(oa-cand, tmp, act, act-dist + rtl-metric, oa, rtl);
+  add_cand(oa-cand, tmp, act, act-dist + rtl-metric, oa, rtl, i);
 }
 }

@@ -494,7 +494,7 @@ ospf_rt_spfa(struct ospf_area *oa)
  DBG(Found :-)\n);
else
  DBG(Not found!\n);
-   add_cand(oa-cand, tmp, act, act-dist, oa, NULL);
+   add_cand(oa

RE: ECMP/multipath support

2010-12-15 Thread Andrew Lemin 
Hello.

How is development coming along for adding multi-path route support into BIRD?

Please let me know if there is anything we can do to help or test ECMP in RIP 
as this is something we sorely need.

Cheers, Andy.



-Original Message-
From: owner-bird-us...@atrey.karlin.mff.cuni.cz 
[mailto:owner-bird-us...@atrey.karlin.mff.cuni.cz] On Behalf Of Andrew Lemin
Sent: 13 November 2010 20:22
To: Ondrej Zajicek
Cc: Vincent Bernat; bird-us...@trubka.network.cz
Subject: RE: ECMP/multipath support

Hi Ondrej,

That really is wonderful news. Thank you very much :)
Please let me know if there is anything I can do to help.

Regards, Andy.


-Original Message-
From: owner-bird-us...@atrey.karlin.mff.cuni.cz 
[mailto:owner-bird-us...@atrey.karlin.mff.cuni.cz] On Behalf Of Ondrej Zajicek
Sent: 13 November 2010 00:21
To: Andrew Lemin
Cc: Vincent Bernat; bird-us...@trubka.network.cz
Subject: Re: ECMP/multipath support

On Thu, Nov 11, 2010 at 10:38:55AM +, Andrew Lemin wrote:
 Hi all,

 What does the BIRD dev team think? Is there anything more I can do to help 
 with adding this functionality.

Hello, currently i am finalizing link state detection for OSPF.
After that i would probably look at ECMP.

--
Elen sila lumenn' omentielvo

Ondrej 'SanTiago' Zajicek (email: santi...@crfreenet.org) OpenPGP encrypted 
e-mails preferred (KeyID 0x11DEADC3, wwwkeys.pgp.net) To err is human -- to 
blame it on a computer is even more so.

Monitor Computer Systems Limited
Company Registration Number: NI 17805
Registered Office: 3 Pine Crest, Holywood, North Down, Northern Ireland BT18 9ED




Monitor Computer Systems Limited
Company Registration Number: NI 17805
Registered Office: 3 Pine Crest, Holywood, North Down, Northern Ireland BT18 9ED

RE: ECMP/multipath support

2010-12-15 Thread Andrew Lemin 
Wow, great news.
What has been the challenge with adding ECMP support in the RIP protocol?

I understand you are making the changes on the protocols seeing as the bird 
table already supports multipath routes.
Is there anything we could do to help to get the ECMP RIP working?

Thank you for your time and hard work.
Regards, Andy.


-Original Message-
From: Ondrej Zajicek [mailto:santi...@crfreenet.org]
Sent: 15 December 2010 11:38
To: Andrew Lemin
Cc: Vincent Bernat; bird-us...@trubka.network.cz
Subject: Re: ECMP/multipath support

On Wed, Dec 15, 2010 at 10:03:08AM +, Andrew Lemin wrote:
 Hello.

 How is development coming along for adding multi-path route support into BIRD?

We already have BIRD multipath support for OSPF, static and Linux kernel 
protocols in our Git repository [*]. RIP will probably come soon, although it 
is a bit tricky.

[*] git://git.nic.cz/bird.git

--
Elen sila lumenn' omentielvo

Ondrej 'SanTiago' Zajicek (email: santi...@crfreenet.org) OpenPGP encrypted 
e-mails preferred (KeyID 0x11DEADC3, wwwkeys.pgp.net) To err is human -- to 
blame it on a computer is even more so.

Monitor Computer Systems Limited
Company Registration Number: NI 17805
Registered Office: 3 Pine Crest, Holywood, North Down, Northern Ireland BT18 9ED

Re: ECMP/multipath support

2010-12-15 Thread Joakim Tjernlund 

 On Wed, Dec 15, 2010 at 10:03:08AM +, Andrew Lemin wrote:
  Hello.
 
  How is development coming along for adding multi-path route support into 
  BIRD?

 We already have BIRD multipath support for OSPF, static and Linux kernel
 protocols in our Git repository [*]. RIP will probably come soon, although
 it is a bit tricky.

 [*] git://git.nic.cz/bird.git

I remember we had an discussion about multiple unnumbered ptp links between
two nodes. There was a potential problem in OSPF with asymmetric routing
but the conclusion was that it would not happen as BIRD didn't support ECMP.
Now that BIRD does support ECMP, has the above problem been fixed too?

 Jocke

Re: ECMP/multipath support

2010-12-15 Thread Ondrej Zajicek 
On Wed, Dec 15, 2010 at 02:27:31PM +0100, Joakim Tjernlund wrote:
 I remember we had an discussion about multiple unnumbered ptp links between
 two nodes. There was a potential problem in OSPF with asymmetric routing
 but the conclusion was that it would not happen as BIRD didn't support ECMP.
 Now that BIRD does support ECMP, has the above problem been fixed too?

Yes, the next hop computation was changed to handle that case.

-- 
Elen sila lumenn' omentielvo

Ondrej 'SanTiago' Zajicek (email: santi...@crfreenet.org)
OpenPGP encrypted e-mails preferred (KeyID 0x11DEADC3, wwwkeys.pgp.net)
To err is human -- to blame it on a computer is even more so.


signature.asc
Description: Digital signature

RE: ECMP/multipath support

2010-11-13 Thread Andrew Lemin 
Hi Ondrej,

That really is wonderful news. Thank you very much :)
Please let me know if there is anything I can do to help.

Regards, Andy.


-Original Message-
From: owner-bird-us...@atrey.karlin.mff.cuni.cz 
[mailto:owner-bird-us...@atrey.karlin.mff.cuni.cz] On Behalf Of Ondrej Zajicek
Sent: 13 November 2010 00:21
To: Andrew Lemin
Cc: Vincent Bernat; bird-us...@trubka.network.cz
Subject: Re: ECMP/multipath support

On Thu, Nov 11, 2010 at 10:38:55AM +, Andrew Lemin wrote:
 Hi all,

 What does the BIRD dev team think? Is there anything more I can do to help 
 with adding this functionality.

Hello, currently i am finalizing link state detection for OSPF.
After that i would probably look at ECMP.

--
Elen sila lumenn' omentielvo

Ondrej 'SanTiago' Zajicek (email: santi...@crfreenet.org) OpenPGP encrypted 
e-mails preferred (KeyID 0x11DEADC3, wwwkeys.pgp.net) To err is human -- to 
blame it on a computer is even more so.

Monitor Computer Systems Limited
Company Registration Number: NI 17805
Registered Office: 3 Pine Crest, Holywood, North Down, Northern Ireland BT18 9ED

Re: ECMP/multipath support

2010-11-12 Thread Ondrej Zajicek 
On Thu, Nov 11, 2010 at 10:38:55AM +, Andrew Lemin wrote:
 Hi all,
 
 What does the BIRD dev team think? Is there anything more I can do to help 
 with adding this functionality.

Hello, currently i am finalizing link state detection for OSPF.
After that i would probably look at ECMP.

-- 
Elen sila lumenn' omentielvo

Ondrej 'SanTiago' Zajicek (email: santi...@crfreenet.org)
OpenPGP encrypted e-mails preferred (KeyID 0x11DEADC3, wwwkeys.pgp.net)
To err is human -- to blame it on a computer is even more so.


signature.asc
Description: Digital signature

RE: ECMP/multipath support

2010-11-11 Thread Andrew Lemin 
Hi all,

I think all parties on the mailing list came to the conclusion that multipath 
support would be best implemented in the individual routing protocols instead 
of just in the kernel protocol.

What does the BIRD dev team think? Is there anything more I can do to help with 
adding this functionality.

We desperately need ECMP support in the RIP protocol. Thanks everyone :)
Regards, Andy.


-Original Message-
From: Andrew Lemin
Sent: 04 October 2010 16:55
To: 'Vincent Bernat'; Ondrej Zajicek
Cc: bird-us...@trubka.network.cz
Subject: RE: ECMP/multipath support

Hi,

 I see two possibilities how to implement ECMP in BIRD:

 1) adding special route type for a multipath route with multiple
 gw addresses. This wouldn't be hard, it is consistent with a way
 how Linux kernel handles multipath and works well with OSPF, but
 it will not allow to 'merge' routes from different protocols
 (a multipath route would have to be originated by one protocol).

I don't  see this  as a limitation.  To the  best of my  knowledge, each
protocol having a different administrative distance, this is also how it
works with  other routing solutions. A  route from BGP and  a route from
OSPF cannot be combined into a single ECMP route.

I agree. I didn't want to get into the conversation because I know you guys are 
fully aware of all this.
As you say, it is not really appropriate for routes provided by different 
routing protocols to have the same weight. It could be suggested that each 
protocol implementation could have a weight associated with it that is a 
function of the protocols administrative distance etc.


 2) allow BIRD kernel protocol to scan all equal-best routes to
 one destination and 'merge' these to a multipath route for kernel.
 This would be harder to implement, esp. because BIRD would not
 allow more routes to the same destination from one protocol in
 one routing table. But it is probably more natural way for a user.

I don't know any use case for this.

As long as multipath is implemented in the RIP protocol too, then go for the 
first method as it is the proper place for it. We NEED ECMP in RIP though. 
Please.. :)
The point I was trying to make is by adding the functionality to the kernel 
protocol you only have to update one segment of code instead of having to 
update all the protocols.
The vast majority of SMB firewalls and VPN concentrators etc only support RIP, 
hence our position..


 What protocols are you thinking about with regard to ECMP?
 ECMP in OSPF would work OK, ECMP in BGP probably would not work either,
 i am not sure about RIP.

We use ECMP with OSPF here.  Unlike Andrew, both routes are strictly the
same. We use this as  layer 3 redundancy and aggregation. Aggregation is
pretty  important too. With  two routers,  aggregation allows  to handle
temporary bursts  of traffic. You  cannot rely on aggregation  to handle
permanently more traffic because if one of them fails, you cannot handle
your  original traffic.  There is  also the  use case  of three  or more
routers. You can allow one to fail  but you still need the traffic to be
load balanced on the two remaining ones.

Agree :)

I have some knowledge on how ECMP routes work with netlink interface and
can offer to  try to implement this in  BIRD if we agree on  what is the
best  place to  implement this.  However, I  have no  knowledge  on BIRD
internals and on how ECMP work with OS other than Linux.

I am also happy to offer whatever I can to add multipath to BIRD.
Thanks for all your thoughts and time.
Cheers, Andy.

Monitor Computer Systems Limited
Company Registration Number: NI 17805
Registered Office: 3 Pine Crest, Holywood, North Down, Northern Ireland BT18 9ED

RE: ECMP/multipath support

2010-10-04 Thread Andrew Lemin 
Hi Martin,

Yes you are quite right, we are aware that for it to work we need links of 
roughly equal latency and bandwidth etc, which they are. I.e. both slow and not 
much.. ;)

Cheers, Andy.

-Original Message-
From: Martin Mares [mailto:m...@ucw.cz]
Sent: 01 October 2010 16:15
To: Andrew Lemin
Cc: Ondrej Zajicek; Vincent Bernat; bird-us...@trubka.network.cz
Subject: Re: ECMP/multipath support

Hello!

 For us ECMP is important as we load balance connections to remote customer
 sites across different ISPs for redundancy and performance.

When doing that, please keep in mind that whenever the characteristics
(delay and throughput) of the lines are different, TCP congestion control
algorithms tend to fail miserably. This greatly limits the usefulness
of any multipath routing.

Have a nice fortnight
--
Martin `MJ' Mares  m...@ucw.cz   http://mj.ucw.cz/
Faculty of Math and Physics, Charles University, Prague, Czech Rep., Earth
Even nostalgia isn't what it used to be.




Monitor Computer Systems Limited
Company Registration Number: NI 17805
Registered Office: 3 Pine Crest, Holywood, North Down, Northern Ireland BT18 9ED

Re: ECMP/multipath support

2010-10-04 Thread Ondrej Zajicek 
On Mon, Oct 04, 2010 at 04:55:12PM +0100, Andrew Lemin wrote:
 As long as multipath is implemented in the RIP protocol too, then go
 for the first method as it is the proper place for it. We NEED ECMP in
 RIP though. Please.. :)
 The point I was trying to make is by adding the functionality to the
 kernel protocol you only have to update one segment of code instead of
 having to update all the protocols.

But that would work only for RIP (and partially for BGP). You cannot use
the same trick (have one protocol per iface) in OSPF, because the
protocols would have separate LSA databases and the link-state graph
would be broken.

-- 
Elen sila lumenn' omentielvo

Ondrej 'SanTiago' Zajicek (email: santi...@crfreenet.org)
OpenPGP encrypted e-mails preferred (KeyID 0x11DEADC3, wwwkeys.pgp.net)
To err is human -- to blame it on a computer is even more so.


signature.asc
Description: Digital signature

RE: ECMP/multipath support

2010-10-01 Thread Andrew Lemin 
Hi Vincent,



This is something that we have also been after for some time too, and I know 
that Securepoint (a company who implement BIRD in their firewall/router product 
have also approached the bird team about), however there does not seem to be 
any resources available in the BIRD team at the moment willing to look into 
this despite how important it is.



Internally BIRD does support the ability to hold multiple routes for a single 
common remote subnet in its routing tables.

I do not believe a single instance of a Dynamic Routing 'Protocol' can insert 
multiple routes into the BIRD's routing tables, but multiple Protocol instances 
can.



A simple example 'bird.conf' with two RIP Protocol instances listening on 
different interfaces;

protocol rip EDGE2RIP { # Create RIP protocol instance called EDGE2RIP

debug all;

timeout time 65; # specifies how old route has to be to be considered 
unreachable. Default is 4*period (period default is 30)

garbage time 70; # specifies how old route has to be to be discarded. 
Default is 10*period (period default is 30)

export none;# Do not transmit BIRD table to RIP peers

import all; # Listen to RIP info from RIP peers and store in BIRD 
table

interface eth3;

}

protocol rip EDGE1RIP { # Create RIP protocol instance called EDGE1RIP

debug all;

timeout time 65; # specifies how old route has to be to be considered 
unreachable. Default is 4*period (period default is 30)

garbage time 70; # specifies how old route has to be to be discarded. 
Default is 10*period (period default is 30)

export none;# Do not transmit BIRD table to RIP peers

import all; # Listen to RIP info from RIP peers and store in BIRD 
table

interface eth2;

}



bird show route

192.168.100.0/24   via 192.168.214.1 on eth2 [EDGE1RIP 09:57] * (120/4)

   via 192.168.215.1 on eth3 [EDGE2RIP 09:57] (120/4)

10.131.0.0/16  via 192.168.214.1 on eth2 [EDGE1RIP 09:57] * (120/4)

   via 192.168.215.1 on eth3 [EDGE2RIP 09:57] (120/4)

10.0.0.0/24via 192.168.215.1 on eth3 [EDGE2RIP 09:57] * (120/4)

   via 192.168.214.1 on eth2 [EDGE1RIP 09:57] (120/4)

10.1.20.0/24   via 192.168.214.1 on eth2 [EDGE1RIP 09:57] * (120/4)

   via 192.168.215.1 on eth3 [EDGE2RIP 09:57] (120/4)

10.1.19.0/24   via 192.168.214.1 on eth2 [EDGE1RIP 09:57] * (120/4)

   via 192.168.215.1 on eth3 [EDGE2RIP 09:57] (120/4)

10.10.0.0/24   via 192.168.214.1 on eth2 [EDGE1RIP 09:57] * (120/4)

   via 192.168.215.1 on eth3 [EDGE2RIP 09:57] (120/4)

192.168.68.0/24via 192.168.214.1 on eth2 [EDGE1RIP 09:57] * (120/4)

   via 192.168.215.1 on eth3 [EDGE2RIP 09:57] (120/4)



You can see above that the internal routing table is capable of holding the 
routes.





The problem is with the process (BIRD's Kernel Protocol) which exports these 
routes into the Kernel routing tables.



To add an ECMP route using the 'ip' command set provided by the kernel package 
iproute2 requires all the route options to be defined in a single statement.



For example to export the first ECMP route shown in the example above requires 
the following statement;

ip route add 192.168.100.0/24 nexthop via 192.168.214.1 weight 1 nexthop via 
192.168.215.1 weight 1





However the Kernel Protocol is currently not capable of scanning the BIRD 
routing table for all route 'options' and forming a single statement, instead 
the 'Kernel Protocol' just recursively works its way through the BIRD routing 
table exporting each entry in single statements. E.g;

ip route add 192.168.100.0/24 via 192.168.214.1

ip route add 192.168.100.0/24 via 192.168.215.1

.



The first command will work fine. But the second command will NOT work and will 
be rejected (with error; 'RTNETLINK answers: File exists') resulting in only a 
single route in the kernel routing tables for 192.168.100.0/24 via 
192.168.214.1 in my example.





The solution could be provided in two places.

1)  Support could be added in iproute2 for the 'ip route add' command to update 
the existing route into an ECMP route if a second route add statement is 
provided for an existing subnet etc.

2)  Or support could be added in BIRD for the 'Kernel Protocol' to scan the 
BIRD routing tables for all the route 'options' and form a single 'ip route add 
.. nexthop' statement etc.



I believe support needs to be added to BIRD's 'Kernel Protocol' to scan BIRD's 
internal routing table for all route options.





Hope this helps provide some insight.



Regards, Andy.







-Original Message-
From: owner-bird-us...@atrey.karlin.mff.cuni.cz 
[mailto:owner-bird-us...@atrey.karlin.mff.cuni.cz] On Behalf Of Vincent Bernat
Sent: 24 September 2010 10:41
To: bird-us...@trubka.network.cz
Subject: ECMP/multipath support



Hi!



BIRD does not support EMCP

RE: ECMP/multipath support

2010-10-01 Thread Andrew Lemin 
Hi Ondrej,
Thanks for your quick response.

For us ECMP is important as we load balance connections to remote customer 
sites across different ISPs for redundancy and performance.

In many parts of the world, including here, cheap high speed WAN connections 
are simply not available and so we have to aggregate the bandwidth of many 
small links to achieve the overall required capacities etc.

Each of our edge firewalls, each hosting unique VPNs to all our customers, 
advertise their available VPNs to our core router performing multipath and 
running BIRD.

We would not mind if ECMP routes were restricted to a single protocol type (as 
in my previous example you can see we run two RIP instances, one on each 
outside interface), however I do believe that for a complete solution ECMP 
should be supported for all routes regardless of source.

   1) adding special route type for a multipath route with multiple gw 
 addresses. This wouldn't be hard, it is consistent with a way how Linux 
 kernel handles multipath and works well with OSPF, but it will not allow 
 to 'merge' routes from different protocols (a multipath route would have to 
 be originated by one protocol).

This sounds simpler to implement, but will probably be far too restrictive.

   2) allow BIRD kernel protocol to scan all equal-best routes to one 
 destination and 'merge' these to a multipath route for kernel.
   This would be harder to implement, esp. because BIRD would not allow 
 more routes to the same destination from one protocol in one routing table. 
 But it is probably more natural way for a user.

This is a much better solution :)

I am aware of the limitation that BIRD does not allow more routes to the same 
destination from one protocol 'instance' in one routing table, and it is for 
this reason that we run two instances of RIP on different interfaces instead of 
one instance on all outbound interfaces.

If you had two nexthop gateways on a common interface could you not just run 
two protocol instances each set to only listen for routes from each of the IP's 
of each nexthop gateway?


We are restricted to using RIP due to our edge firewalls being Draytek devices. 
With the exception of high end firewalls, most SMB firewall devices only 
support RIP.


Thanks for your time.
Regards, Andy.


-Original Message-
From: Ondrej Zajicek [mailto:santi...@crfreenet.org]
Sent: 01 October 2010 13:19
To: Andrew Lemin
Cc: Vincent Bernat; bird-us...@trubka.network.cz
Subject: Re: ECMP/multipath support

On Fri, Oct 01, 2010 at 10:40:58AM +0100, Andrew Lemin wrote:
Hi Vincent,

This is something that we have also been after for some time too, and I
know that Securepoint (a company who implement BIRD in their
firewall/router product have also approached the bird team about), however
there does not seem to be any resources available in the BIRD team at the
moment willing to look into this despite how important it is.

Is ECMP really much important? It seems to me that it is useful only in limited 
number of cases (like having two parallel lines with similar capacities in a 
network). I would expect that redundancy is usually solved by having generally 
denser network graph (where ECMP is more likey a random coincidence). But it 
seems that it is also a feature that is most often asked for.


I see two possibilities how to implement ECMP in BIRD:

1) adding special route type for a multipath route with multiple gw addresses. 
This wouldn't be hard, it is consistent with a way how Linux kernel handles 
multipath and works well with OSPF, but it will not allow to 'merge' routes 
from different protocols (a multipath route would have to be originated by one 
protocol).

2) allow BIRD kernel protocol to scan all equal-best routes to one destination 
and 'merge' these to a multipath route for kernel.
This would be harder to implement, esp. because BIRD would not allow more 
routes to the same destination from one protocol in one routing table. But it 
is probably more natural way for a user.


What protocols are you thinking about with regard to ECMP?
ECMP in OSPF would work OK, ECMP in BGP probably would not work either, i am 
not sure about RIP.


--
Elen sila lumenn' omentielvo

Ondrej 'SanTiago' Zajicek (email: santi...@crfreenet.org) OpenPGP encrypted 
e-mails preferred (KeyID 0x11DEADC3, wwwkeys.pgp.net) To err is human -- to 
blame it on a computer is even more so.

Monitor Computer Systems Limited
Company Registration Number: NI 17805
Registered Office: 3 Pine Crest, Holywood, North Down, Northern Ireland BT18 9ED

Re: ECMP/multipath support

2010-10-01 Thread Martin Mares 
Hello!

 For us ECMP is important as we load balance connections to remote customer
 sites across different ISPs for redundancy and performance.

When doing that, please keep in mind that whenever the characteristics
(delay and throughput) of the lines are different, TCP congestion control
algorithms tend to fail miserably. This greatly limits the usefulness
of any multipath routing.

Have a nice fortnight
-- 
Martin `MJ' Mares  m...@ucw.cz   http://mj.ucw.cz/
Faculty of Math and Physics, Charles University, Prague, Czech Rep., Earth
Even nostalgia isn't what it used to be.