Linked lists

Python has a rather handy list method. It allows you to add and remove items at will. How it actually does this is rather elaborate and you can read all about it over here.

C doesn’t give you the same flexibility. When you create an array, it is of X size. That size cannot change as there is no guarantee that memory on either side of the existing array space is even free for you. For this reason there is a handy data structure called the linked list.

Linked List

A linked list is essentially a struct node with a list item, and then a pointer to the next node. If you need to add an item to a list, you simply create another node in memory. As each item is created, it doesn’t matter where in memory it’s created, as the previous item has a pointer to the new node. A picture really helps here:
linked1
As we shall see, adding, inserting, and removing items are all very easy to do with linked lists. It’s not all roses though. Linked lists use more memory than an array of similar items. Each node has a pointer to the next item which takes up memory. The bigger issue is random access.

Let’s say we initialise an array with 1000 items. If I wanted to get to item 500, the computer would simply look at the address of item 0, work out the start address plus 500 of item size, and read that location.
linked2

You can’t do this with a linked list. Each node is in a separate location. They could be lined up next to each other, but they can just as easily be all over the place. The only way to get to item 500 in a linked list, is to start at node 0, read the pointer to the next node, then keep doing that until you reach node 500.

How do you know when you reach the end of the linked list? You could probably use any kind of escape character, but NULL tends to get used.

Basic implementation

So how do we create a linked list? Here I’ll create a struct called node that will hold an integer. The struct will also hold a pointer to the next node.

#include <stdio.h>

// Struct node with pointer to struct node
typedef struct node {
    int number;
    struct node* next;
}node;

int main(void) {

    // Create four nodes
    node node1;
    node node2;
    node node3;
    node node4;
    
    // Place numbers inside the four nodes we made
    node1.number = 10;
    node2.number = 20;
    node3.number = 30;
    node4.number = 40;
    
    // Each node will point to the next node
    node1.next = &node2;
    node2.next = &node3;
    node3.next = &node4;
    node4.next = NULL;
}

Here I have created four nodes. Each points to the next node, except for node 4. It has it’s next pointer assigned to NULL. If you fail to assign this NULL value, the pointer will have whatever value what in that memory location when you create it. That is going to point to some random value which is bad news. In order to traverse the list, we need a pointer to the root, or currently node1’s address. This is a pointer that should never change unless node1 is deleted or a node is inserted before it. We also need a cursor that will be updated with the current node’s address. I’ll create a function that prints out items in the list. The following is added to main()

    // Never lose the root position, otherwise you
    // lose access to your list!
    node* root = &node1;
    
    // Use cur as a cursor to move around
    node* cur;
    cur = root;

    // Print current list
    printList(cur); 

And the printList function is as so:

void printList(struct node* cur) {
    // Traverse through our linked list
    int i = 0;
    while (cur != NULL) {
        printf("Item %i is %i\n", i, cur->number);
        i++;
        
        // Move cursor to next node via pointer
        cur = cur->next;
    }
}

Running the program gives the following:

$ ./list 
Item 0 is 10
Item 1 is 20
Item 2 is 30
Item 3 is 40

Let’s change the print statement now to print out the memory locations of each of these items. Printing the value of node->next should give is the address of the next node. Let’s change the printList function like so:

void printList(struct node* cur) {
    // Traverse through our linked list
    while (cur != NULL) {
        printf("%i is is at position %p\n", cur->number, &cur->number);
        printf("Next node is at position %p\n\n", cur->next);
        
        // Move cursor to next node via pointer
        cur = cur->next;
    }
}

Printing this out gives us the following:

$ ./list 
10 is is at position 0xbff38e68
Next node is at position 0xbff38e60

20 is is at position 0xbff38e60
Next node is at position 0xbff38e58

30 is is at position 0xbff38e58
Next node is at position 0xbff38e50

40 is is at position 0xbff38e50
Next node is at position (nil)

Notice the memory address of each next value is the same as the address of the next value printed. Exactly what we would expect. Also notice that node4’s next value is NULL. I’ve used this very fact in the while loop to know when the list has ended and exit the loop.

Adding to the list

The previous program had me hard code four node values into the program. Let’s change this now so that the program will prompt to add values, and then print them out when needed:

#include <stdio.h>
#include <stdlib.h>

// Struct node with pointer to struct node
typedef struct node {
    int number;
    struct node* next;
}node;

void printList(node* cur) {

    // Traverse through our linked list
    while (cur != NULL) {
        printf("%i is is at position %p\n", cur->number, &cur->number);
        printf("Next node is at position %p\n\n", cur->next);
        
        // Move cursor to next node via pointer
        cur = cur->next;
    }
}

void addNode(node* cur) {

    // Traverse through our linked list
    // Need to get to end of list in order to append
    if (cur != NULL) {
        while (cur->next != NULL) {
            cur = cur->next;
        }
    }
    
    // Now at the the end of the list, ensure the current last node
    // points to a new node we create dynamically
    cur->next = (node*) malloc(sizeof(node));
    
    // Move to the new node
    cur = cur->next;
    
    // Get a value inside that node
    printf("Please enter node value: ");
    scanf("%i", &cur->number);  
}
        
int main(void) {

    // Create initial node
    node node1;
    
    // Get initial value from user
    printf("Please enter inital node value: ");
    scanf("%i", &node1.number);
    
    // Initial node's next should be end of list
    node1.next = NULL;
    
    // Root position of list
    node* root = &node1;
    
    // Use cur as a cursor to move around
    node* cur;
    
    // User controls what to do next
    int choice;
    do
    {
        printf("1 - Add new item to list\n");
        printf("2 - Print list\n");
        printf("3 - Exit\n# ");
        
        scanf("%i", &choice);
        
        switch (choice) {
            case 3:
                return 0;

            case 2:
                cur = root;
                printList(cur);
                break;
                
            case 1:
                cur = root;
                addNode(cur);
         }
                
    } while (choice != 3);
}

Let’s add a couple of values and then print them out:

: ./list
Please enter inital node value: 100
1 - Add new item to list
2 - Print list
3 - Exit
# 1
Please enter node value: 200
1 - Add new item to list
2 - Print list
3 - Exit
# 2
100 is is at position 0xbf97dc18
Next node is at position 0x875a008

200 is is at position 0x875a008
Next node is at position (nil)

1 - Add new item to list
2 - Print list
3 - Exit
# 1
Please enter node value: 300
1 - Add new item to list
2 - Print list
3 - Exit
# 1
Please enter node value: 400
1 - Add new item to list
2 - Print list
3 - Exit
# 2
100 is is at position 0xbf97dc18
Next node is at position 0x875a008

200 is is at position 0x875a008
Next node is at position 0x875a018

300 is is at position 0x875a018
Next node is at position 0x875a028

400 is is at position 0x875a028
Next node is at position (nil)

1 - Add new item to list
2 - Print list
3 - Exit
# 3

Inserting into the list

Inserting into a list is very simple too, but it comes with one risky part. Order of operations is quite important. If you get to the position where you want to insert, then create a new node, you need to be sure that you don’t lose the address to the original next node. If you do so, you could lose the rest of your list!

Once again, imagery helps to explain this. Here we have three nodes. We now want to add a new node in the position:
linked3
Here we malloc a new node, and then point the previous node to this new node:
linked4
Oops, how do we now reattach the rest of the list? It’s there in memory, but good luck finding it.
linked5
It’s essential to ensure you either link the new node to the old rest of list first, then change the old node:
linked6
linked7
Or simply save the pointer value that the original node was pointing to, and copy that back into our new node’s pointer value.

I’ve chose the latter in the following code. I’ll only post the changed parts. I’ll create a new function that will do the insertion and call it through main():

    do
    {
        printf("1 - Add new item to list\n");
        printf("2 - Print list\n");
        printf("3 - Insert node\n");
        printf("4 - Exit\n# ");
        
        scanf("%i", &choice);
        
        switch (choice) {
            case 4:
                return 0;
                
            case 3:
                cur = root;
                printf("After which value should I insert? ");
                int match;
                scanf("%i", &match);
                insertNode(cur, match);
                break;

            case 2:
                cur = root;
                printList(cur);
                break;
                
            case 1:
                cur = root;
                addNode(cur);
         }
                
    } while (choice != 4);


void insertNode(node* cur, int match) {

    // Traverse through linked list to find value
    while (cur->next != NULL) {
        
        // We've found the node we're looking for
        if (cur->number == match) {
        
            // save pointer to rest of list
            node* temp = cur->next;
            
            // Create a new node and get current node to point to it
            cur->next = (node*) malloc(sizeof(node));
        
            // Move to the new node
            cur = cur->next;
            
            // Get a value to insert
            printf("What value do you want to insert? ");
            int number;
            scanf("%i", &number);
            cur->number = number;
            
            // Finally ensure new node connects to the rest of the list
            cur->next = temp;
            
            return;
        }
        
        // Otherwise keep going through the list
        cur = cur->next;
    }
}

Let’s add some values and then insert one:

$ ./list 
Please enter inital node value: 10
1 - Add new item to list
2 - Print list
3 - Insert node
4 - Exit
# 1
Please enter node value: 20
1 - Add new item to list
2 - Print list
3 - Insert node
4 - Exit
# 1
Please enter node value: 30
1 - Add new item to list
2 - Print list
3 - Insert node
4 - Exit
# 3
After which value should I insert? 20
What value do you want to insert? 25
1 - Add new item to list
2 - Print list
3 - Insert node
4 - Exit
# 2
10 is is at position 0xbfd42938
Next node is at position 0x831e008

20 is is at position 0x831e008
Next node is at position 0x831e028

25 is is at position 0x831e028
Next node is at position 0x831e018

30 is is at position 0x831e018
Next node is at position (nil)

1 - Add new item to list
2 - Print list
3 - Insert node
4 - Exit
# 4

Deleting a node

Deleting is similar to inserting. Instead of getting a new value, we simply look for the node in question and unlink it from the chain. As per the inserting function, we need to take care that we don’t lose the address of the next node in the chain. It’s a little more tricky as well, as when we remove a node, we need to get back to the previous node so we can set it’s pointer to the next node we need:
linked8
Here I’ve deleted the second node. The first node’s pointer now points to a memory location with garbage data. We’ve also lost the address to the rest of the list!

In my function here, I’ll ensure I always keep the pointer address of the previous node. When we find the node we want to remove, we still have the previous pointer value that we can copy where we need it:

void deleteNode(node* cur, int match) {

    // We need to keep note of previous node
    // otherwise we cannot reconnect it!
    node* previous = cur;

    // Traverse through linked list to find value
    while (cur->next != NULL) {
        
        // We've found the node we're looking for
        if (cur->number == match) {
        
            // Set pointer of last node around this node to new node
            node* temp = cur->next;
            cur = previous;
            cur->next = temp;
            
            return;
            
            // Where to release the RAM?
        }
        
        // Otherwise keep going through the list
        previous = cur;
        cur = cur->next;
    }
}
: ./list 
Please enter inital node value: 10
1 - Add new item to list
2 - Print list
3 - Insert node
4 - Delete node
5 - Exit
# 1
Please enter node value: 20
1 - Add new item to list
2 - Print list
3 - Insert node
4 - Delete node
5 - Exit
# 3
After which value should I insert? 10
What value do you want to insert? 15
1 - Add new item to list
2 - Print list
3 - Insert node
4 - Delete node
5 - Exit
# 2
10 is is at position 0xbfa0b0c8
Next node is at position 0x8bda018

15 is is at position 0x8bda018
Next node is at position 0x8bda008

20 is is at position 0x8bda008
Next node is at position (nil)

1 - Add new item to list
2 - Print list
3 - Insert node
4 - Delete node
5 - Exit
# 4
Which value should I delete? 15
1 - Add new item to list
2 - Print list
3 - Insert node
4 - Delete node
5 - Exit
# 2
10 is is at position 0xbfa0b0c8
Next node is at position 0x8bda008

20 is is at position 0x8bda008
Next node is at position (nil)

1 - Add new item to list
2 - Print list
3 - Insert node
4 - Delete node
5 - Exit
#5

Freeing your nodes

It’s good practice to clean up once you’re done. Just before we exit, I want to ensure that all nodes are removed from memory. As noted in the delete section, we need to ensure that we save the location of the next node. There are a couple of ways to do this. One way is to keep a note of the next node’s address, then delete the current node. then off to the next node and repeat. I’ve done that here:

void deleteList(node* cur) {
    // Traverse through linked list
    while (cur != NULL) {
        node* temp = cur;
        cur = cur->next;
        free (temp);
    }
}

Extras

I’ve not covered all the different ways of manipulating a linked list. What if we want to delete the first or last node for example?
This is a good read if you want to take it further: https://www.cs.bu.edu/teaching/c/linked-list/delete/

You can find my working code for the above right here: https://github.com/mellowdrifter/C-Sandbox/blob/master/linked.c

BGP outbound route filtering

BGP ORF is a powerful feature that relieves both the ISP and their BGP customers from time wasting and headaches. It can also be used to do some pretty complicated MPLS L3VPN stuff, but let’s keep this post relatively simple.

Let’s us the following simple topology for this post:

Let’s say that R2 is a customer of R1. R1 is is a Tier 1 ISP with the full global routing table. R2 has bought IP transit from both R1 and another company. R2 has a choice of what BGP table to receive from the ISP. Should I take the full routing table? Should I take just a default?
Maybe a default and a few other prefixes? With the full table, I can do all kinds of load-sharing and I can ensure that my traffic will always take the shortest as-path.
On the other hand I could simple take defaults from both. That way my routers only need to hold a single default, but my routers don’t really know the best path for anything.
I can also ask both ISPs to send me a default plus a few more specifics.

Of course the problems with the first is that my edge routers need to hold the entire BGP table. The second option I am extremely limited in sending my outbound traffic via the best path. The final option seems the best, but what if I wanted to change which routes the ISP is sending me? I would have to submit a request for them to do so, and who knows how long until they make that change. Most ISPs will not even do this for you anyway.

You could take the entire BGP table and then run that through a filter blocking everything you didn’t want. That works but it’s a waste. Let’s say you want 100 prefixes. The ISP’s router will have to send all 500k IPv4 prefixes to you, only for you to filter out all but 10 of them. This is not efficient for both the ISPs and your own router. Sending the entire table also takes a few minutes.

Enter OutBound Route Filtering (ORF) – Effectively this allows you the customer to ‘configure’ the ISPs router to only send you what you want. At any time you can update the filter on your local box and that change is fed to the ISPs box. Let’s see this in action.

R1 has 9 loopbacks, 1.1.1.1 to 9.9.9.9. It’s also sending a default route. Standard config is like so:

R1
router bgp 1
 bgp log-neighbor-changes
 neighbor 10.0.0.1 remote-as 200
 !
 address-family ipv4
  network 1.1.1.0 mask 255.255.255.0
  network 2.2.2.0 mask 255.255.255.0
  network 3.3.3.0 mask 255.255.255.0
  network 4.4.4.0 mask 255.255.255.0
  network 5.5.5.0 mask 255.255.255.0
  network 6.6.6.0 mask 255.255.255.0
  network 7.7.7.0 mask 255.255.255.0
  network 8.8.8.0 mask 255.255.255.0
  network 9.9.9.0 mask 255.255.255.0
  neighbor 10.0.0.1 activate
  neighbor 10.0.0.1 default-originate
 exit-address-family
R2
router bgp 200
 bgp log-neighbor-changes
 neighbor 10.0.0.0 remote-as 1
 !
 address-family ipv4
  neighbor 10.0.0.0 activate
 exit-address-family


R2#sh ip bgp | begin Network
   Network          Next Hop            Metric LocPrf Weight Path
*> 0.0.0.0          10.0.0.0                               0 1 i
*> 1.1.1.0/24       10.0.0.0                 0             0 1 i
*> 2.2.2.0/24       10.0.0.0                 0             0 1 i
*> 3.3.3.0/24       10.0.0.0                 0             0 1 i
*> 4.4.4.0/24       10.0.0.0                 0             0 1 i
*> 5.5.5.0/24       10.0.0.0                 0             0 1 i
*> 6.6.6.0/24       10.0.0.0                 0             0 1 i
*> 7.7.7.0/24       10.0.0.0                 0             0 1 i
*> 8.8.8.0/24       10.0.0.0                 0             0 1 i
*> 9.9.9.0/24       10.0.0.0                 0             0 1 i

So far everything is expected. However I now want to receive the default route, but also 4.4.4.4/24 and 8.8.8.8/24 – nothing else. The first thing we need to do is enable ORF. Note that this can be set to ‘receive’, ‘send’, or ‘both’. This ensures that only certain routers control certain others. Note also that when you configure this, the BGP session resets.

R1
router bgp 1
 address-family ipv4
  neighbor 10.0.0.1 capability orf prefix-list receive
R2
router bgp 200
 address-family ipv4
  neighbor 10.0.0.0 capability orf prefix-list send

Note that ‘receive’ is for the router sending the routes while ‘send’ is for the router receiving the routes. The send and receive keywords are for sending and receiving the prefix-lists, not the routes themselves.

So now on R2 let’s create a prefix-list specifying what we want and apply that to our neighbour:

ip prefix-list ROUTES_WANTED seq 5 permit 0.0.0.0/0
ip prefix-list ROUTES_WANTED seq 10 permit 4.4.4.0/24
ip prefix-list ROUTES_WANTED seq 15 permit 8.8.8.0/24
!
router bgp 200
 address-family ipv4
  neighbor 10.0.0.0 prefix-list ROUTES_WANTED in

R2#sh ip bgp | begin Network
   Network          Next Hop            Metric LocPrf Weight Path
*> 0.0.0.0          10.0.0.0                               0 1 i
*> 4.4.4.0/24       10.0.0.0                 0             0 1 i
*> 8.8.8.0/24       10.0.0.0                 0             0 1 i

If you run a debug you’ll see that R2 is not receiving and then rejecting prefixes, it’ simply doesn’t see them. You can actually see this from R1’s perpective:

R1
R1#sh ip bgp neighbors 10.0.0.1 received prefix-filter 
Address family: IPv4 Unicast
ip prefix-list 10.0.0.1: 3 entries
   seq 5 permit 0.0.0.0/0
   seq 10 permit 4.4.4.0/24
   seq 15 permit 8.8.8.0/24

Now you want the 5.5.5.0/24 prefix? The customer only needs to update his prefix-filter:

R2
R2(config)#ip prefix-list ROUTES_WANTED seq 20 permit 5.5.5.0/24

R2#clear ip bgp * soft in prefix-filter 

R2#sh ip bgp | begin Network            
   Network          Next Hop            Metric LocPrf Weight Path
*> 0.0.0.0          10.0.0.0                               0 1 i
*> 4.4.4.0/24       10.0.0.0                 0             0 1 i
*> 5.5.5.0/24       10.0.0.0                 0             0 1 i
*> 8.8.8.0/24       10.0.0.0                 0             0 1 i
R1
R1#sh ip bgp neighbors 10.0.0.1 received prefix-filter 
Address family: IPv4 Unicast
ip prefix-list 10.0.0.1: 4 entries
   seq 5 permit 0.0.0.0/0
   seq 10 permit 4.4.4.0/24
   seq 15 permit 8.8.8.0/24
   seq 20 permit 5.5.5.0/24

You specify ORF filters and capability on a per address-family basis. So you can use the same technique to filter IPv6 unicast, IPv6 multicast, IPv4 multicast, etc

Of course JunOS can do the exact same thing. Let’s replicate the topology above and do the same thing. Note that when you set this up between IOS and JunOS, you need to tell JunOS to use the Cisco format:

JunOS
darren> show configuration protocols bgp
group EXTERNAL {
    neighbor 10.0.10.1 {
        peer-as 100;
        outbound-route-filter {
            bgp-orf-cisco-mode;
            prefix-based {
                accept {
                    inet;
                }
            }
        }
    }
}

darren> show bgp neighbor orf 10.0.10.1 detail
Peer: 10.0.10.1+179   Type: External
  Group: EXTERNAL

  inet-unicast
    Filter updates recv:          4 Immediate:          1
    Filter: prefix-based            receive
            Updates recv:          4
      Received filter entries:
        seq 5 /0 permit minlen 0 maxlen 0
        seq 10 4.4.4.0/24 permit minlen 0 maxlen 0
        seq 15 8.8.8.0/24 permit minlen 0 maxlen 0
        seq 20 5.5.5.0/24 permit minlen 0 maxlen 0

darren> show route advertising-protocol bgp 10.0.10.1

inet.0: 15 destinations, 16 routes (15 active, 0 holddown, 0 hidden)
  Prefix                  Nexthop              MED     Lclpref    AS path
* 4.4.4.0/24              Self                                    2 ?
* 5.5.5.0/24              Self                                    2 ?
* 8.8.8.0/24              Self                                    2 ?

This is an very powerful way to easily let one router tell another what routes to send it, instead of just dropping it. Great for regular and MPLS-based BGP

Using an extended ACL as a prefix-list

This will be a short post.

I’ve mentioned it before, but let’s say you have a task which requires you to filters updates through a route-map. For some reason the task states you’re only allowed to use an ACL, not a prefix-list.

You are able to use an extended ACL as a prefix list.

Let’s use this simple topology:

R1 has a bunch of loopbacks. R1 and R2 are running EIGRP with each other. I’ve configured R1 to redistribute all connected routes into EIGRP.

R1’s loopbacks:

interface Loopback2
 ip address 2.2.2.2 255.255.255.0
!
interface Loopback3
 ip address 3.3.3.3 255.255.255.248
!
interface Loopback4
 ip address 4.4.4.4 255.255.255.0
!
interface Loopback5
 ip address 5.5.5.5 255.255.255.255
!
interface Loopback6
 ip address 5.5.5.50 255.255.255.248

R2 sees all of these EIGRP routes in it’s RIB:

R2#show ip route eigrp
     2.0.0.0/24 is subnetted, 1 subnets
D EX    2.2.2.0 [170/2560002816] via 1.1.1.1, 00:00:06, FastEthernet0/0
     3.0.0.0/29 is subnetted, 1 subnets
D EX    3.3.3.0 [170/2560002816] via 1.1.1.1, 00:00:06, FastEthernet0/0
     4.0.0.0/24 is subnetted, 1 subnets
D EX    4.4.4.0 [170/2560002816] via 1.1.1.1, 00:00:06, FastEthernet0/0
     5.0.0.0/8 is variably subnetted, 2 subnets, 2 masks
D EX    5.5.5.5/32 [170/2560002816] via 1.1.1.1, 00:00:06, FastEthernet0/0
D EX    5.5.5.48/29 [170/2560002816] via 1.1.1.1, 00:00:06, FastEthernet0/0

Now the task states that I need to ensure 5.5.5.48/29 is redistributed, but not 5.5.5.5/32 – I’m not allowed to use a prefix-list and I’m not allowd to use a route-map that matches an interface.

If we then use a regular ACL, we’ll end up redistributing 5.5.5.5/32 as well if we’re not careful. What actually happens if the tasks says we need to redistribute all subnets that are /29 only. This would be 3.3.3.3/29 and 5.5.5.5.48/29

The simple answer is the extended list. Let’s do all /29s:

access-list 150 permit ip host 3.3.3.0 host 255.255.255.248
access-list 150 permit ip host 5.5.5.48 host 255.255.255.248
!
route-map SLASH29 permit 10
 match ip address 150
!
router eigrp 1
 redistribute connected metric 1 1 1 1 1 route-map SLASH29

Basically the ‘source’ becomes the IP address and the ‘destination’ becomes the subnet mask.

Does it work? Let’s take a look:
R2:

R2#sh ip route eigrp
     3.0.0.0/29 is subnetted, 1 subnets
D EX    3.3.3.0 [170/2560002816] via 1.1.1.1, 00:02:12, FastEthernet0/0
     5.0.0.0/29 is subnetted, 1 subnets
D EX    5.5.5.48 [170/2560002816] via 1.1.1.1, 00:01:30, FastEthernet0/0

So yes it works just fine. But really in the real world you would be using the far more powerful prefix-list…

MPLS VPN lab #4

The diagram is the same as my last VPN Lab. Also it uses my MPLs topology found over here: http://mellowd.co.uk/ccie/?p=522

This is the topology for this lab (click for a bigger image):

MPLS4 - small

  • Customer1 and Customer 2 both have MPLS vpn’s through the ISP core.
  • Customer1 is using OSPF and Customer2 is using EIGRP
  • Customers should have no access to each others networks
  • Customers should be able to reach all their sites from all their sites
  • The ISP wants to monitor the CPE routers via their monitoring server. Create another loopback on each CPE router and give them all a /32 loopback in the 172.16.1.1/24 range – i.e. 172.16.1.1/32 for CPE1, 172.16.1.2/32 for CPE2 and so on
  • Ensure the monitoring router can get to all these /32 routes (and ONLY these /32 routes) – It should not know about any customer routes – CPE routers should only see their OWN loopbacks in the routing table
  • Now enable CPE3 and CPE6 to see each others subnets. All other CPE routers should see no change in their routing tables

Timed access-lists

Timed access-lists can be handy for all sorts of things. Let’s say you have a few contractor PC’s in your office that are only allowed internet access from 17:00 to 19:00 each day. The rest of the day those PC’s are allowed to speak internally in the lan only.

I’ve got a very simple diagram here. PC’s 1-3 are allowed full access all the time. PC’s 4 and 5 are our contractor PC’s. Let’s say that DHCP is being used, but we are matching IP’s to MAC addresses (We’ll go over this in a new post sometime) – This is the topology (Click for larger image):

Timed access lists - small

On the router I’m going to create 2 access-lists. The first will be a timed access list that will prevent any traffic from 192.168.1.4 and .5 from leaving the Fa0/0 interface. The second access-list will only allow traffic with a source address of 192.168.1.1-5 to pass through interface Fa0/1. This will prevent the contractors changing their IP to 192.168.1.10 and so on to gain internet access. It might be better to just not give them admin rights to their PC’s, but sometimes they may be using their own computers.

First up is the time range in which I want the block to be active:

time-range CONTRACTOR_NO_INTERNET
 periodic daily 0:00 to 16:59
 periodic daily 19:00 to 23:59

Next I have to create an access-list, and I need to ensure the access-list is only active during my time range:

ip access-list extended CONTRACTORS
 deny   ip host 192.168.1.4 any time-range CONTRACTOR_NO_INTERNET
 deny   ip host 192.168.1.5 any time-range CONTRACTOR_NO_INTERNET
 permit ip any any

Always remember that ACL’s have an implicit deny at the end, so in this case I need to ensure I have an implicit permit any at the end. Also note that although I’ve blocked those hosts to any destination, they’ll still be able to traverse the local lan as it’ll only go through the switch. If you had a SOHO router with a switch-plane built into the router, you may need to create another entry allowing all local subnet traffic at the top of this access-list.

Now we need to apply this access-list to the Fa0/0 interface:

interface FastEthernet0/0
 ip address 10.1.1.1 255.255.255.0
 ip access-group CONTRACTORS out
 duplex auto
 speed auto
end

The last part I wanted to do was to ensure that only the IP’s in use on the network right now are allowed. This prevents the contractors from changing their IP’s to get around our access-list.

ACL:

access-list 1 permit 192.168.1.1
access-list 1 permit 192.168.1.3
access-list 1 permit 192.168.1.2
access-list 1 permit 192.168.1.5
access-list 1 permit 192.168.1.4
access-list 1 deny   any

On the interface:

interface FastEthernet0/1
 ip address 192.168.1.254 255.255.255.0
 ip access-group 1 in
 duplex auto
 speed auto
end

Very handy!

Edit: Just be sure that you’ve actually correctly set the clock on the router beforehand!