Random ramblings

All | General | Motorbikes | Networking | Odds & Sods | Soapbox | Solaris
« Previous page | Main | Next page »
20070429 Sunday April 29, 2007

Quagga 0.99.7 released

Quagga 0.99.7 has been released, see the changelog for the full details. Users of ospfd with PtP links should be aware of bug #348. Users of Quagga on Solaris who rely on zebra to configure IP addresses on interfaces should be aware of bug #358. A summary of changes of interest to Quagga end-users:

( Apr 29 2007, 11:48:02 PM IST ) Permalink Comments [0]

20070423 Monday April 23, 2007

The difference a line makes

Quagga's SPF handling was tweaked recently, to deal with the possibility that nexthop-calculation could fail. The Dijkstra calculation never took that into consideration, so would always relax vertices if a lower cost path appeared. However, if nexthop calculation failed, relaxation would simply lose the costlier but valid route. Valid routes tend to be better than cheaper but invalid ones..

This wasn't a bug per se, as the sole reason for nexthop-calculation failing is due to disagreements between neighbours on contents of LSAs, i.e. while the routing protocol is converging, specifically where one router thinks it has a link to the other, but the other does not. However, improving that behaviour should significantly improve routing stability during convergence, and so it was fixed. The changeset included the following innocuous section (see here for full original code): 

@@ -647,11 +655,12 @@ ospf_nexthop_calculation (struct ospf_area *area, struct vertex *v,
 		  nh = vertex_nexthop_new ();
 		  nh->oi = vp->nexthop->oi;
 		  nh->router = l->link_data;
-                 ospf_spf_add_parent (v, w, nh);
+		  added = 1;
+                 ospf_spf_add_parent (v, w, nh, l);
                 }
-              return;
             }
         }
+      return added;
     }
 
   /* 16.1.1 para 4.  If there is at least one intervening router in the

The idea being to:

  1. Make the unconditional return able to indicate failure
  2. Allow the block of code above to find all the parents by moving the return out of the inner loop

Course, 2) introduced a not so subtle problem.

Not long after the above was introduced to CVS, and after one or two odious regressions were fixed, Andrew Schorr was brave enough to try out the above in production and found that it led to some routes being missed. Leading to a day-long, cross-atlantic, SPF debugging session..

After much collecting of and pouring over ospfd log files, with review of the SPF code, the changeset mentioned above particularly, we weren't much the wiser, other than this curious log snippet from a single run of SPF: 

2007/03/21 23:07:20 OSPF: ospf_vertex_new: Created Router vertex
192.168.21.24
2007/03/21 23:07:20 OSPF: ospf_nexthop_calculation(): Start
2007/03/21 23:07:20 OSPF: V (parent): Network vertex 192.168.170.77
distance 32 flags 0
....
2007/03/21 23:07:20 OSPF: ospf_vertex_new: Created Router vertex
192.168.21.24
2007/03/21 23:07:20 OSPF: ospf_nexthop_calculation(): Start
2007/03/21 23:07:20 OSPF: V (parent): Network vertex 192.168.169.77
distance 33 flags 0

Hmm, but a vertex should never be created twice. A vertex should only be created on the first path which reaches it, traversal thereafter should find it on the priority queue used to sort known vertices. I.e. the SPF code was forgetting it had previously found a vertex. But how did the changeset above cause this problem?

The next thing to do was to reconstruct from the logs the SPF tree calculated, to find the topological feature causing the problems. The problem tree looked like (A.B.C.D are router vertices, A.B.C.D/Y are network vertices. 192.168.130.100 is the root vertex. Indentation is used to show child vertices): 

192.168.130.100
        192.168.130.77/24
                192.168.130.3
                192.168.130.10
                192.168.130.57
                192.168.130.79
                        192.168.133.102/24
                        192.168.170.77/24
                        192.168.169.77/24
                192.168.130.78
                        192.168.133.102/24
                        192.168.170.77/24
                        192.168.169.77/24
                192.168.130.77
                        192.168.133.102/24
                        192.168.170.77/24
                        192.168.169.77/24
                192.168.130.11

The problem was the SPF code was somehow failing to search past the 2nd level of network vertices. Suddenly the bug became embarrassingly clear :(. The nexthop calculation consists of, for vertices of V (parent) and W (child): 

if (V is root vertex)
  .....
else if (V is network vertex) {
  for (every parent, p, of V) {
    if (p is root) {
        
        added = 1;
    }
    return added;
  }
}

/* Vertices not connected to the root vertex just use nexthops from parent */
for (every parent, p, of V) {
  
   added = 1;
}
return added;

Of course, the following obvious change was quickly commited to CVS: 

@@ -665,7 +673,8 @@ ospf_nexthop_calculation (struct ospf_area *area, struct
vertex *v,
                 }
             }
         }
-      return added;
+      if (added)
+        return added;
     }
 
   /* 16.1.1 para 4.  If there is at least one intervening router in the

One thing that is apparent is that we need a better, sorry, some way of testing and replicating SPF code given arbitrary LSA DB contents (bug #349). A regression suite of LSA DBs that could be fed through the SPF code would be very useful, as would ability to dump LSA DBs in the field to file.

All in all, a really, really, silly, little, one-liner bug, which still managed to take two people, custom logging and approx 12 hours of investigation to simply pin down. The difference a line makes.

( Apr 23 2007, 01:38:51 PM IST ) Permalink Comments [0]

20070412 Thursday April 12, 2007

Security: Quagga BGP Denial-of-Service (low impact)

Quagga's BGP component, bgpd, is vulnerable to a Denial-of-Service, peer of bgpd sends an UPDATE message with specially constructed MP_REACH_NLRI or MP_UNREACH_NLRI attributes, causing bgpd to attempt to read beyond the end of the packet buffer. Typically, this will cause the bounded-buffer library code in Quagga to raise an assert and terminate the bgpd process, where the code was compiled with assert() enabled - which is typically the case for most packaged versions of Quagga, and unconditionally the case for 0.99.6 and later releases. Where assert() was not enabled at compilation time, bgpd will attempt to read potentially invalid memory. Consequences of such are unknown, though it is not known to be exploitable at this time.

A proposed fix is available via the latest CVS snapshot. Further details, and a diff form of the proposed fix for 0.99, are available in bug #354. Bug #355 tracks resolution of this issue against the 0.98 tree, and contains a proposed backport of the 0.99 fix.

The DoS can only by triggered by hosts which have been explicitely configured, in bgpd.conf, to be able to establish BGP sessions. The impact of this bug therefore is limited somewhat to bgpd routers with sessions with untrustworthy peers - a reasonably rare set of routers hopefully (public route-servers perhaps).

Testing of CVS and 0.98.6+patch on lab setups would be greatly appreciated, in advance of the required releases.

( Apr 12 2007, 03:08:10 PM IST ) Permalink Comments [0]

20061209 Saturday December 09, 2006

Quagga 0.99.6 released and experimental 4-byte ASN patch

Quagga 0.99.6 has been released. See the release news entry for more information

On the 4-byte ASN support front, which I blogged about earlier this year, Juergen Kammer of Eurodata has announced availability of a patch to add support to Quagga. This is welcome news given that as of 2007 the RIRs will be allocating 4-byte ASNs on request. Testing of Juergen's work would be very welcome, to facilitate speedy inclusion of it into mainline Quagga.

I have to say though that, personally, I'm not all keen on the "asdot" notation for 4-byte ASNs. There's just no good reason I know of to burden users with having to care about the details of width, and lots of reasons against (ambiguity in commands, user confusion). I'm not, personally, keen on merging "asdot" functionality without some compelling reasoning being presented.

( Dec 09 2006, 01:42:29 PM GMT ) Permalink Comments [0]

20061021 Saturday October 21, 2006

Ethernet memo

Interesting and, with the hindsight available to us today, amusing: Comments on "Draft Ethernet Overview" (No idea if it's genuine).

( Oct 21 2006, 04:05:17 PM IST ) Permalink Comments [0]

20060828 Monday August 28, 2006

Quagga 0.99.5 released Quagga 0.99.5 release notes. [Read More] ( Aug 28 2006, 05:18:19 AM IST ) Permalink Comments [0]

20060508 Monday May 08, 2006

Quagga 0.98.6 released

Quagga 0.98.6 has been released, addressing 3 security issues in ripd and bgpd. Only one tiny additional change over last friday's pre-release, a small ripngd fix. Follow the link for further details. Corresponding 0.99 release still to follow.

( May 08 2006, 08:42:54 PM IST ) Permalink Comments [0]

20060504 Thursday May 04, 2006

Quagga 0.98.6 Release Candidate

A snapshot is available of the Quagga 0.98 stable branch, containing fixes for the recently reported RIPv1 vulnerabilities. This is a "Release Candidate" for 0.98.6, testing would be very much appreciated. All the fixes have been tested on their own and/or soaked in the unstable 0.99 series, however the fixes together in this tarball have not been fully tested - stress testing of OSPF virtual-link functionality in particular would be useful.

Changes in the snapshot:

Many thanks to the many users involved who have reported bugs, helped diagnose them and tested iterations of proposed fixes.

( May 04 2006, 05:41:19 PM IST ) Permalink Comments [0]

20060503 Wednesday May 03, 2006

Quagga RIP vulnerabilities

Konstantin V. Gavrilenko of Arhont reported two vulnerabilities in Quagga's ripd daemon.

Bug 262 has fixes for both issues for both 0.99 and 0.98, along with comment.

( May 03 2006, 07:14:37 PM IST ) Permalink Comments [1]

20060412 Wednesday April 12, 2006

Quagga OpenSolaris project

We've put up an OpenSolaris Quagga project page. The focus to be mostly Quagga-on-Solaris, but also some of the related ON work done by Alan Maguire on enhancing routeadm - bringing SMF to both the existing traditional SUNWroute daemons as well as Quagga.

We're also hoping to put up a mini-roadmap, of potential things that could be worked on to improve Quagga and userland side of routing on Solaris. E.g. improving configurability is one possibility. Input on this, when we have it posted, would be great! Or even before. ;)

( Apr 12 2006, 05:21:13 PM IST ) Permalink

Quagga added to Coveritys' scanner

Coverity have added Quagga to their list of open-source projects they scan for defects with their static analysis tools. 66 bugs found, one a false alarm so far, but mostly lots of dumb annoying bugs in (typically) infrequently used or strange-usage code paths. Look for the count to go down to 0 over the next while. :)

( Apr 12 2006, 04:40:20 PM IST ) Permalink

20060325 Saturday March 25, 2006

Why can't I filter OSPF

This is a bit of a FAQ, and comes up regularly enough that it's worthwhile putting up some google fodder for it:

Why can't I filter OSPF "announcements"?

Short answer: Because it would cause inconsistent and broken routing on all but trivial networks.

You may be asking the question because you have acquired lots of junk routes in OSPF. Cleaning up might be a better idea ;). Tips on keeping your OSPF clean:

The long answer: OSPF is not a distance-vector (D-V) protocol2.

In distance vector protocols (RIP, eBGP) there is (generally) a 1:1 correspondence between the path a route announcement takes to reach "you" and the path the announcement is describing1. I.e. if router R1 announces a route X to R2 using a distance-vector protocol, then that must imply that:

Hence, if R2 may use R1 to reach X no matter what, it follows that R2 must be quite free to ignore announcements for X received from any other routers, even if the other announcements were of lower distance. This property makes D-V protocols very amienable to filtering.

OSPF however is not D-V2. Rather, it works by having each router describe what links it has to the OSPF network, and the state of those links, in a message called a "Link State Advertisement" (LSA). Hence OSPF is called a "link-state" routing protocol.

These LSA messages are "flooded" throughout the OSPF network. Each router, on receiving an LSA from a neighbour, floods it out to all its other neighbours3, which do the same. The end result being that within a given OSPF link-state domain (i.e. "area"2) all the OSPF routers will, once flooding is complete, have a copy of every other router's LSA, describing each router and its links. From this, each router can construct a directed graph (i.e. a "tree") of the best paths in the OSPF network (using Dijkstra's SPF algorithm).

The important points to note here are that:

Hence, the core of OSPF routing information can not be filtered. Just because you receive LSAs from R1, that does not mean R1 won't forward to you for whatever destination those messages describe (as it does in D-V). Hence the receiving OSPF router can not just ignore those messages, for if R1 is depending on you for forwarding for those destination, you have to do so or break their routing.

Further, even if you ignore messages from R1, you may well still receive the same messages anyway from some other router. So filtering those messages would be pointless, unless you isolated yourself from OSPF.

E.g. Imagine a set of routers: 

A--B--C--D-E
 \        /
  \---F--/

E floods an LSA describing its link to D. D is configured to filter out this LSA from E, with the "desired" result being to prevent C from learning about E. However, it doesn't matter: As E will also flood to F, so that the LSA will get to C anyway, through flooding via F->A->B->C. With the end result that everyone gets the LSAs, everyone calculates the routes they're supposed to and whatever routing was going to take place takes place regardless of the filtering.

However, this OSPF network suddenly is a lot more fragile. Imagine someone configure B to also filter the E LSA if received from A. This will indeed cause the "desired" result of preventing E's LSA from reaching C. Unfortunately, it doesn't stop either A or F (or even B) from calculating the best path to E as being through C. Any packets hitting C destined to E will just get dropped.. (it doesn't stop D calculating best path to E as being through C either, note ;) ).

So you just can't filter OSPF (intra-area at least) without running into problems. Instead, keep it clean and carefully control what gets injected. Inter-area, you do have some scope for filtering and summarising (i.e. aggregating), as well as using stub or NSSA areas. But even then, cleanliness goes a long way.

Corrections as comments or as email to "paul dot jakma AT sun dot com" would be gratefully appreciated.

1. Sometimes though D-V protocols have provisions to tell 'white lies' and announce routes with 3rd parties as the nexthop, as an optimisation. E.g. R1 announces a path to R2, R2 announces this to R3. R2 sees that R3 is on the subnet as R1, and hence sets nexthop to R1 as a nexthop. This is obviously, given the nature of D-V protocols, fragile. R2 can't be /really/ sure that R3 actually is able to forward via R1.

Another way 1:1 correspondence can be broken is through route-aggregation features in some protocols, where several paths announced by a set of routers are replaced with a greater "covering" path by an intermediary router. In such a case the path the announcement has taken to a 3rd party will (should anyway) then be a subset of the path which packets take, however the initial (or closer) part path should still correspond, as far as any such 3rd parties are concerned.

2. Well, actually, OSPF is D-V, but only for inter-area routing. OSPF can be considered as being the superset of two types of routing: A collection of independent link-state "areas", with D-V routing between them, always through the "backbone" (0.0.0.0) area. OSPF routing therefore can (mostly) be filtered between areas (at the "Area Border Routers" or ABRs).

3. There are optimisations here obviously. E.g. on broadcast subnets, the routers agree on a "Designated Router" (DR) to take care of most flooding on that subnet, and reduce the overhead of having many routers on a common network all flooding to every other router. Routers can just flood to the DR, and the DR will take care of flooding the LSA to the other routers. Further, a "Backup" (BDR) is also agreed on, it is also flooded to.

( Mar 25 2006, 12:45:26 AM GMT ) Permalink Comments [4]

20060310 Friday March 10, 2006

Quagga and 4 byte ASNs

I've been asked a couple of times recently about support for the upcoming BGP 4 byte ASN RFC which, as anyone who has heard Geoff Huston's AS numbers presentation will know, needs to be implemented and deployed widely within the next few years.

The short answer is that Quagga is part-way towards 4-byte ASN support. The long answer follows..

Up to and including Quagga 0.98 the internal representation of AS_PATH was essentially directly congruent to the wire format. However, in 0.99, the AS_PATH parser and internal storage have been overhauled to represent AS_PATH in abstracted form, validated with extensive unit tests. So 0.99 is essentially a single typedef away from using 4-byte ASNs internally. That leaves the following (generally) as still to be implemented:

  1. The 4-byte-supported BGP capability
  2. Extending the unit tests with equivalent 4-byte forms and verifying the AS_PATH parser and transformational functions.
  3. Using the appropriate encoding for AS_PATH according to the remote peer
  4. Adding support for the 2<->4 byte transition mechanisms (unit tests implied)

1, 2 and 3 should be quite easy, 2 weeks about, including testing, and would get bgpd to the stage which the draft RFC calls a "NEW" speaker and interoperate fully with other "NEW" speakers. It would also be able to speak to "OLD" peers, provided no 4-byte wide ASNs are involved. Support for these items I hope to see in Quagga before the end of the year.

That leaves 4, which isn't as easy, further I am not very optimistic on its chances of working. I suspect the internet would be in trouble if we end up relying on the 4-byte transition mechanism to work. I really hope all deployed speakers of significance end up being upgraded to "NEW" (ie corresponding to at least 1,2 and 3 above) well before the first 4-byte ASNs are issued, so that we never have to find out how well the transition mechanisms might work..

( Mar 10 2006, 01:08:41 PM GMT ) Permalink Comments [2]

20060201 Wednesday February 01, 2006

Using quagga for intelligent static routes

Not many people know this, but Quagga can be useful even if you only need static routes. The 'zebra' daemon component, which maintains the composite RIB of all best protocol, kernel and connected routes and is responsible for installing the correct route (if needs be) with the kernel, is able to manage static routes and do so intelligently.

E.g. imagine you have a VPN tunnel, dynamically addressed, which sometimes is available and sometimes not. When it is, you want to use that as your default route, when it is not, you do not, but use some other gateway instead. The following line in zebra.conf: 

ip route 0.0.0.0 ip.tun0
ip route 0.0.0.0 192.168.0.1 10
ip route 0.0.0.0 172.16.0.1 10

would have zebra prefer the ip.tun0 as default, otherwise whichever (or both) of the latter two gateways are available (which zebra decides by seeing if there is an attached network in which the gateway falls). The 10 on the latter two routes is a 'weight' (administrative distance). The default is 0, the lowest distance.

With the above, you could hop between 192.168/16 and 172.16/12 networks, also turn on/off your VPN, and (mostly) have it work (as long as your VPN software is careful to install a host route via the existing default gateway when it brings up the VPN).

I often use a VPN. It actually takes care of default route switching for me, but I use the above as a backup in case it gets it wrong for whatever reason and leaves me without a default - zebra will just step in and install the best one possible.

( Feb 01 2006, 11:21:01 AM GMT ) Permalink

Van Jacobsen's network channels

Van Jacobson gave an interesting talk at a recent Linux conference on pushing networking complexity even further out to the edges, and the resulting performance benefits. LWN have an article on it, but it will be subscriber only for another week or so.

( Feb 01 2006, 11:06:58 AM GMT ) Permalink

Calendar

« December 2009
MonTueWedThuFriSatSun
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
   
       
Today

RSS Feeds

XML
All
/General
/Motorbikes
/Networking
/Odds & Sods
/Soapbox
/Solaris

Search

Links

Navigation

Referers

Today's Page Hits: 21