blog
Binary Math - Part I
16 September 08

# Binary Math - Part I

Posted byINE

As CCIE candidates, we are asked to do all sorts of things with access lists.  We have them in lots of different places, and use them in lots of different ways.  So many, sometimes, that it becomes very confusing to follow things!

Access-lists themselves aren't really that bad.  Or are they?  When we use them with route-maps, occasionally we see permits in an access-list that are really used to deny the packet/route/whatever.  What's up with that?

Remember that ACLs are simply a matching mechanism.  Something either DOES (permit) or DOES NOT (deny) match the list.  Now, what we do with that matching status depends on how we use the ACL.  As an interface-based packet filter, it truly is a permit or deny of the packet!  In a route-map, it would depend on whether the route-map clause is a permit one or a deny one, in which case anything MATCHING the ACL would follow that route-map permit or deny ability.

Now, within an access-list, we also have some difficult things to grasp.  I like to consider that lesson in binary math.  That may oversimplify it, because really all we are doing is counting a 0 or a 1.  How difficult can it be to count to one???  :)

All by itself, it's not that difficult.  But the we'll get some really obnoxious words thrown in like "in as few lines as possible" or "minimal configuration".  That means we have to start thinking about how the router sees things.

Let's start with some groupings or summaries, and get the ball rolling.

In as few lines as possible (which translates to "no overlap") summarize:

172.16.31.0/24
172.16.32.0/24
172.16.33.0/24
172.16.34.0/24

There's only four networks, so it should be a /22, right?  We learned that back in CCNA!  Well, not quite so fast, because there's a bit-boundary in our way.   The best way to start with any of these tasks is to work with the binary and start to see the patterns.

31    00011111
32    00100000
33    00100001
34    00100010

Now, we may have seen some documents about performing an XOR function between the different entries.  This is kinda-sorta true.  From a pure logical construct, XOR measures between two different things.  Here we have four.  So would it be an XXXOR  or an XOROROR?  Either way, the point is we are beyond the basic logical formula!

But it really isn't as bad as it may sound!  Think about it in very simplistic terms!  Next, we look at what things are the same and which are different.  Well, between 31 and 32 we see LOTS of things that are different.  6 bits, in particular, have different values.  When we create an ACL binary mask, the 0-bit means "stay the same" while a 1-bit means "different" or "don't care".

So just on two values with 6 bits of difference, we could come up with a mask of 00111111 and it would work.  The problem we create, though, is the over-matching.  If you take 2 to the power of the total number of 1-bits in your mask, you'll find the total number of matches for the mask.

In this case, 2^6 yields 64 matches to that mask.  We only have four things to group, so that's not cool.  So we won't be able to get our summary in one line!!  Leave 31 by itself then.  Look at 32, 33 and 34.

There are two bits (the 1-position and 2-position) that are different.  Here with a mask of 00000011 and two bits set to the 1-bit value, there will be a total of four matches to the mask (2^2).  Still more than we want, as there's only three lines left after setting aside "31"!

But, here's where we start to look at multiple ways to accomplish the task!

access-list 10 permit 172.16.31.0 0.0.0.255
access-list 10 permit 172.16.32.0 0.0.1.255
access-list 10 permit 172.16.34.0 0.0.0.255

or

access-list 10 permit 172.16.31.0 0.0.0.255
access-list 10 deny 172.16.35.0 0.0.0.255
access-list 10 permit 172.16.32.0 0.0.3.255

Both results give us a total of three lines as the tightest configuration we can get.  The difference is that one of them over-permits, but we deny those non-listed things first!  So if your lab task says there "must be at least one 'deny' statement" then this is it.

The bottom line is no more, no less though!   So let's add to that list.

In as few lines as possible (which translates to "no overlap") summarize:

172.16.31.0/24
172.16.32.0/24
172.16.33.0/24
172.16.34.0/24
172.16.35.0/24
172.16.36.0/24
172.16.37.0/24

We know we'll run into the same basic quandary with "31" and the others as we did before.  But what about the rest?  Back to binary.

31    00011111
32    00100000
33    00100001
34    00100010
35    00100011
36    00100100
37    00100101

Counting 31 off on its own, we notice there are three bits that have varying values from 32 through 37.  The 1-bit, 2-bit and 4-bit positions.  So if we used a mask of 00000111, that would cover all of those three bits.

2^3 to check the mask though tells us there would be eight matches.  There's only six values listed to match.  We want no more, no less!  Notice that 32 through 35 has two bits varying between them.  A mask of 00000011 would match ONLY those four.  And a mask of 00000001 would match ONLY the 36 and 37.

So we can use:

access-list 11 permit 172.16.31.0 0.0.0.255
access-list 11 permit 172.16.32.0 0.0.3.255
access-list 11 permit 172.16.36.0 0.0.1.255

What if we were told that we must have at least one DENY statement in the ACL?
Oh, those obnoxious requirements!  Think like we did with the first one with the over-permitting.  Let's go back to the 00000111 mask.  What extra values come into play there?

With a mask, we are saying we permit any and all of the variants with the bits.  No matter where they fall in the mask, we should substitute values in to see them!

With three bits, we need:

000
001
010
011
100
101
110
111

The "110" and "111" matches are not in our list.  That would be 38 and 39.

38    00100110
39    00100111

Those can be summarized as well, so here's a list with a deny:

access-list 11 permit 172.16.31.0 0.0.0.255
access-list 11 deny 172.16.38.0 0.0.1.255
access-list 11 permit 172.16.32.0 0.0.7.255

Exactly the same list is being permitted as before.  With no more or no less.

Now, let's start talking about non-contiguous matching!  Because that's where life becomes more interesting.  We're following the same rules though.

What if we are instructed to pick only the even /24 networks from 192.168.0.0/16?

As I said, the rules don't change here, it's just "different" than we may be used to building masks for.  We just aren't drawing a "line" to separate network from host.  That's the CCNA version of access-lists.  While it's technically true, it's not the entire truth!  As a CCIE we are expected to know more!

So we can go back and start breaking all the even  numbers up into binary to start to see our patterns.

0    00000000
2    00000010
4    00000100
6    00000110
8    00001000
10    00001010
12    00001100
14    00001110
16    00010000

Blah, blah, blah...  You get the idea.  Keep going if you want, but you should already get the pattern.  The ONLY bit that WILL NEVER change is the 1-bit position, which will always be a zero.

Our mask will consist of seven "don't care" bits and one "must be the same" bit. 11111110 will work perfectly fine.   Now, here's the catchy part.  What do you put as the 'network' portion of the ACL?

Well, let's expand on that "network" name....  Again, very CCNA explanation.  What really is happening is that your ACL has a "binary starting point" and a "binary mask" to go with it.

So we need to SET our values, then provide the rules for what can change or what cannot.

access-list 12 permit 192.168.0.0 0.0.254.0 will permit all of the EVEN /24's there.

Why did we put ".0" as the fourth octet?  Because the question asked for /24's, which implies this will be used in a routing protocol.  All /24 network advertisements must have ".0" as the fourth octet and it cannot change.  If it were a security question asking for hosts in the even numbered networks, then we would use a 0.0.254.255 mask.

What if we wanted the ODD networks out of the same range?

You can work out the binary if you want, but you will find that the mask will actually be the same thing.  The only difference here is that our STARTING POINT changes.

access-list 13 permit 192.168.1.0 0.0.254.0 will permit all of the ODD /24's!!!

So our big lessons here are:
- All bits are treated individually (no "line" to draw)
- The logical least number of lines may include over-permission with a deny first
- It's not a "network", but rather a binary starting point.
- Don't forget to check the mask using 2^(# of 1-bits in the mask) forumla!

Some extra ones to think about, and we'll see who gets the answers first.

1.  Allow packets from all hosts in every fourth /24 network from 131.102.0.0/16

2.  In as few lines as possible, permit only the following networks (assume it will be a distribute-list):

200.100.128.0/24
200.100.130.0/24
200.100.132.0/24
200.100.134.0/24
200.100.136.0/24
200.100.138.0/24

3. In as few lines as possible, allow access from all hosts in the 158.1.100.0/24 network except .93 through .106.  You are not allowed to use any "deny" statements.

Be sure to comment with your answers, no comments will show up until the contest ends.  The first person with all three answers correct will win 60 tokens!!! Whether you are renting racks of equipment for any track or working on graded Mock Labs, those tokens sure come in handy!

Stay tuned for the answers, and for Part II in a few days!  Good Luck!!!