September « 2011 « ShortestPathFirst

21Sep/114

What’s a Steiner Tree?

Any of you who have worked with VPLS or NG-MVPNs are likely already familiar with using Point-to-Multipoint (P2MP) LSPs to get traffic from a single ingress PE to multiple egress PEs. The reason that P2MP LSPs are desired in these cases is that it can reduce unnecessary replication by doing so only where absolutely required, for example where a given P2MP LSP must diverge in order to reach two different PEs.

However, typically the sub-LSPs which are part of a given P2MP LSP traverse the shortest-path from ingress to egress based on whatever user defined constraints have been configured. While this is fine for many applications, additional optimizations might be required such that additional bandwidth savings can be realized.

We will take a look at something called a Steiner-Tree which can help the network operator to realize these additional savings, when warranted, reducing the overall bandwidth used in the network and fundamentally changing the way in which paths are computed.

Let's start by taking a look at a simple example in which RSVP is used to signal a particular P2MP LSP, but no constraints are defined. All the links in this network have a metric of 10. In this case, the sub-LSPs will simply traverse along the shortest path in the network, as can be seen in the diagram below.

Here we see a P2MP LSP where PE1 is the ingress PE and PE2, PE3, and PE4 are all egress nodes. Since no constraints have been defined the calculated ERO for each of the sub-LSPs will follow along the shortest path where we can see one sub-LSP taking the PE-P1-P2-PE2 path, another is taking the PE1-P1-P3-PE3 path, and the third is taking the PE1-P1-P4-PE4 path. In this case, each sub-LSP has a total end-to-end cost of 30.

Shortest Tree

Under many circumstances this type of tree would be perfectly acceptable, especially when the end-goal is the minimize end-to-end latency, however there are other cases where we may want to introduce additional hops in an effort to reduce overall bandwidth utilization. This is where the concept of a minimum-cost tree, otherwise known as a Steiner Tree, comes into play.

This may seem counter-intuitive at first; after all, doesn't a shortest-path tree attempt to minimize costs? The answer is yes, but it usually only does so by looking at costs in terms of end-to-end metrics or hops through a network. Once you understand the mechanics of the Steiner Tree algorithm, and how it attempts to minimize the total number of interconnects, it starts to make more sense.

According to Wikipedia, "the Steiner tree problem, or the minimum Steiner tree problem, named after Jakob Steiner, is a problem in combinatorial optimization, which may be formulated in a number of settings, with the common part being that it is required to find the shortest interconnect for a given set of objects".

That's a pretty fancy way of saying it's attempting to optimize the path to be the shortest path possible while at the same time reducing the total number of interconnects between all devices to only those that are absolutely required.

Steiner Tree optimizations are very useful where an ingress PE must send large amounts of data to multiple PEs and it is preferable to ensure that overall bandwidth utilization is reduced, perhaps because of usage-based billing scenarios which require that overall circuit utilization be reduced as much as possible in order to save money.

Let's take a look at an example, once again using the same network as before, but this time performing a Steiner Tree optimization whereby cost is measured in terms of overall bandwidth utilization. In this case we still see that we have the requirement to build the P2MP LSP from PE1 to PE2, PE3, and PE4. However, this time we are going to compute an ERO such that replication will only take place where absolutely necessary in order to reduce the total number of interconnects and hence overall bandwidth utilization.

After performing a Steiner Tree path computation, we determine that PE3 is a more logical choice to perform the replication to PE2 and PE4, even though it increases the overall end-to-end metric cost to 40. The reason for this is we have now effectively eliminated the bandwidth utilization on the P1-P2, P2-PE2, P1-P4, and P4-PE4 links. In effect, we've gone from utilizing bandwidth across seven links to only five. If the P2MP LSP was servicing a 100 Mbps video stream, we have just effectively reduced overall bandwidth utilization on the network as a whole by 200 Mbps.

Steiner Tree

One of the interesting side-effects of this approach is that we now see that PE3 is not only an egress node, but it is now also a transit node as well (for the sub-LSPs terminating at PE2 and PE4). Due to this, we'll also see that in these types of scenarios the Penultimate Hop Popping (PHP) behavior is different on P3 in that we don't want it popping the outer label before sending frames to PE3 since PE3 may need to accommodate labeled packets heading to PE2 or PE3. We will cover some of this in a subsequent article on the signaling mechanisms inherent in P2MP LSPs and some of the changes to the behavior in MPLS forwarding state.

Path computation for P2MP LSPs can be complex, especially when the goal is create Steiner Trees. The reason for this added complexity when computing Steiner Trees is that sub-LSP placement has a direct correlation with other sub-LSPs, which is contrary to what happens when shortest-path trees are calculated where each sub-LSP may be signaled along their own unique path without regard to the placement of other sub-LSPs.

As with traditional LSPs, similar methods of determining the paths through the network and hence the ERO can be used, i.e. manual, offline computation.

The easiest approach would be to use constructs like Link Coloring (Affinity Groups for you Cisco wonks) to influence path selection, for example, by coloring the PE1-P1, P1-P3, P3-PE3, PE3-PE2, and PE3-PE4 links with an included color, or coloring the remaining links with a different color and excluding that color from the LSP configuration.

However, this approach is merely a trick. We are feeding elements into the CSPF algorithm such that the shortest path which is calculated essentially mimics that of a Steiner Tree. In other words, it's not a true Steiner Tree calculation because the goal was not to reduce the total number of interconnects, but rather to only utilize links of an included color.

Furthermore, such an approach doesn't easily accommodate failure scenarios in which PE3 may go down, because even though Fast Reroute or Link/Node Protection may be desired, if the remaining links do not have the included colors they may be unable to compute an ERO for signaling.

Workarounds to this approach are to configure your Fast Reroute Detours or your Link/Node Protection Bypass LSPs to have more relaxed constraints, such that any potential path might be used. However, more commonly what you'll see is that some type of additional computations might be performed using traditional offline approaches (using modeling tools such as those provided by vendors such as WANDL, OPNET, or Cariden) which factors both steady-state as well as failure scenarios to assist the operator in determining optimal placement of all elements.

An interesting side-note is that there are some pretty significant developments underway whereby online computation can be performed in such a way as to optimize all P2MP LSPs network-wide, using something known as Path Computation Elements (PCEs). These are essentially any entity which is capable of performing path computation for any set of paths throughout a network by applying various constraints. It is something that looks to be especially useful in large carrier networks consisting of many LSPs, and especially so in the case of Steiner Tree P2MP LSPs where the sub-LSP placement is highly dependent on others. See the charter of the PCE Working Group in the IETF for more information on this and other related developments.

As a side note, it should be fairly evident that in order to perform path optimizations on anything other than shortest-path trees (i.e. Steiner Trees or any other type of tree based on user-defined constraints), RSVP signaling must be used in order to signal a path along the computed ERO. LDP certainly can be used to build P2MP LSPs (aka mLDP), however much like traditional LSPs built via LDP, the path follows the traditional IGP path.

Stay tuned as we will cover more exciting articles on P2MP LSPs and some of the other underpinnings behind many of the next generation MPLS services being commonly deployed.

Filed under: MPLS, Multicast, Network Design, VPLS 4 Comments

12Sep/1116

Preparation Tips for the JNCIE-SEC Exam

Not a day that goes by since having passed the JNCIE-SEC exam that I don't receive an inquiry in one form or another regarding how I prepared for the exam. It seems that there is an incredible amount of interest in this exam, especially from all those die-hard ScreenOS folks that are now converting to Junos. So instead of constantly repeating myself, I figured I'd just put it up on the blog so others can benefit (leaving me more time to do other things, 'heh).

NOTE: For full disclosure, I must reveal that I am an Technical Trainer and Certification Proctor at Juniper Networks. As such, I take EXTRA responsibility towards protecting the content and integrity of the exam and I take the certification credentials very seriously. Not only that, I worked REALLY, REALLY hard to achieve my JNCIE certifications, and I believe everyone else should too! As such, I kindly ask that candidates refrain from asking me questions which would be considered a violation of the NDA. Also, I should add that although I work for Juniper, the viewpoints expressed in this article are my own and may not necessarily be shared by my employer.

Let's first start by looking at the exam objectives and then we will move on to the materials I used for preparation and the hardware requirements for building out a lab which would provide for sufficient preparation.

Exam Objectives

Detailed exam objectives are listed on Juniper's JNCIE-SEC Exam Objectives certification page. Familiarize yourself with these objectives and try to focus your study towards mastering all of these objectives. Learn to read between the lines to identify if additional subject matter might need to be explored for full preparation.

In Junos there are typically more than one way to accomplish a given task so you would be wise to learn all the different ways of accomplishing a goal to achieve complete mastery of the subject matter. For example, can you accomplish bidirectional address translation similar to Static NAT by instead using Source NAT and Destination NAT? What are the benefits and caveats of each approach?

The current Junos software release that is used throughout the exam is Junos 11.1. A quick glance through the release notes may be useful to familiarize yourself with some of the new features introduced in this version.

Study Materials

First and foremost, you are going to want to get your hands on the official Juniper courseware for all the requisite curriculum listed under the Junos Security track. Specifically the following:

If you are unable to attend all of these courses in person, one of the cool things is that Juniper now lets you purchase the course materials for self-study purposes. Basically you get access to everything that you would normally receive in the class, minus the instructor and access to the lab gear of course.

NOTE: While it is possible to order the materials for self-study, I strongly advocate taking the actual training if you can do so as the instructors tend to augment the subject matter with additional details, first-hand observations and experience not normally found in the materials. Furthermore, as is the case in classes I normally teach, we tend to reveal tips and techniques which might be useful in certification attempts.

To augment the above, I would highly advise reading the book 'Junos Security' by Rob Cameron, Brad Woodberg, Patricio Giecco, Tim Eberhard, and James Quinn. I'll be writing a review of this book in a subsequent post but for now I can't overemphasize how important this book was in my preparations. In fact, I would advise reading it twice for good measure. There is a lot of good coverage in this book. The majority of what you can expect to see in the exam is covered in this book, and what might be missing is adequately covered in the official courseware material.

I would also suggest making note of the links below. You would be well advised to make use of both of these links during your preparation. The first link is the JumpStation to a wide variety of SRX knowledge base articles and the second link provides detailed coverage on configuring High Availability across a number of different SRX platforms. Familiarize yourself with the subtle differences in HA configuration across all the different platforms as you don't want your first time to be exposed to these differences to be during an examination attempt.

Before moving on to the lab setup, I want to mention that we will be offering JNCIE-SEC bootcamps sometime in the future. Although there is currently no committed date for such an offering, when available you will get in-depth coverage of the types of topics you will expect to see on the exam in addition to a simulated lab on the final day of class. Stay tuned for more information regarding our bootcamp offerings on Juniper's Learning Portal.

Lab Buildout

A common question asked throughout the forums is what type of lab setup is required for adequate preparation. I can tell you that I personally prepared with only two SRX210s and single SRX100 device, but it slowed down my preparations immensely due to constantly having to rearrange and reconfigure the lab setup to accommodate different topologies (hub-and-spoke vs. full-mesh, clustered vs. non-clustered, etc.). If you can spring for it, I would say purchase as many devices as you possibly can so you can build out a clustered SRX while leaving others as standalone and build complex VPN topologies. This way you can spend more of your time learning new features rather than having to rearrange your lab setup.

amtrak_lab One of the benefits of having the smaller branch devices is that they are fairly portable. In fact, as seen in the picture to the left, I was able to set up my lab during a trip from DC to New York on an Amtrak train in business class (although others did give me funny looks). As you can see, even during a 3 hour trip, I was able to make use of this time for study preparations.

I would also strongly advise purchasing at least one device with the High Memory option as this will let you run the full gamut of IPS and UTM capabilities, assuming you've got the licenses. Speaking of licenses, you can acquire trial licenses from Juniper which are valid for a period of 4 weeks, so I would advise holding off on activating these until you are completely ready. Trial licenses are tied to a devices serial number, and although they are only valid for a period of 4 weeks, you can fetch a trial license once per year for each device serial number.

You can find SRX devices on eBay for as little as a few hundred dollars a piece, so building out a lab doesn't have to break the bank. And the cool thing is that when you are done you can resell them for a fair market value so in the long term you really shouldn't have to spend that much getting a decent lab built out.

Once you have your lab completely set up, I would strongly advise going through all the labs in the official courseware as these are indicative of the types of things you will likely see on the exam. Unlike JNCIE-ENT and JNCIE-SP, in this lab it really helps to have incorporated some type of client and server throughout the topology so that various features such as NAT and Stateful Firewall Policy can be properly tested. In lieu of this, and with a bit of creative license, you could actually use one of your SRX platforms with a few Virtual Routers configured to simulate both clients and servers, connected to the Trust ports on the other devices throughout your topology. This won't give you the same parity as having access to real Clients and Servers, but the idea is to be able to generate sufficient flows to properly trigger things like NAT rules or firewall policy. A lot can be simulated by simply using 'telnet' and specifying the destination-port required to trigger a particular rule on a downstream device.

Final Notes

A question most often asked is how long should it take to prepare. The answer to that question really depends on your Junos experience level and background. If you already have previous working experience with Junos or a JNCIE, I would expect about 4-6 months should be sufficient for adequate preparation. Otherwise if you are new to Junos or transitioning over from ScreenOS, I wouldn't even suggest starting exam preparations until you've had at least 1-2 years experience working with Junos and the SRX platforms.

Overall, this might seem like a long time but you'd be amazed at how quickly a few months can go by - if you can carve out even just an hour each day over the course of several months you will be infinitely better served than having to do a bunch of cramming in the last few weeks before your exam. Remember, slow and steady wins the race here... it's a marathon, not a 100-meter dash.

Last but not least, and this may seem a bit silly but it is really important to try to get to bed early on the night of the exam and get a decent nights rest. If you're not adequately prepared the night before the exam, cramming all night isn't going to do you any good. Also, wake up early enough to ensure you can get a good breakfast. Based on personal experience I can tell you that this makes a big difference. I strongly advise oatmeal since it's low on the Glycemic Index and will give you a slow steady release of energy throughout the morning - the perfect way to ensure your mind is focused and you don't have any of those mid-morning dips in energy levels or mental acuity.

A little tidbit that not many folks are aware of - you can bring your own keyboards when you sit the exam as you might find the keyboards we provide to be difficult to use. This is one of those little things that can really make a difference when you are used to running all those EMACS command sequences on a keyboard you are familiar with.

I will be proctoring this exam so for those of you attempting to sit the exam in our Herndon office, I look forward to meeting you and wish you the best in your upcoming attempt. With a little bit of luck and a lot of preparation, you may find success and achieve the highly sought-after JNCIE-SEC designation. Good luck and may the force be with you!