May
14

Hi Everyone!

The Challenge
People tend to underestimate the important of IGP routing features in modern network. So here is a small challenge scenario for you to practice OSPF traffic engineering. Take a look at the diagram below for information on the topology and link bandwidth. You may assume that every router has a loopback interface for network testing and OSPF router-id selection.

ospf-traffic-engineering

There is a large cloud of media servers behind R4, and the users behind R1 need to use full 300Mbps of bandwidth when downloading files off the servers. The network is running single-area OSPF for IP routing. Ensure you can accomplish the above goal without using MPLS Traffic Engineering or Policy Based Routing. You are allowed to create additional logical interfaces, but the routing protocol, OSPF areas, physical links and their characteristics should remain unchanged. Keep the amount of changes to minimum and do not introduce new IP addresses.

The first person to provide a working solution will receive 100 rack rental tokens from our partner company GradedLabs. Please use your valid e-mail address when posting a comment, so we can locate your INE account.

UPD
OK I forgot to rule out the “route-via” option :) Try solving the task without relying on any “policy-based” routing decisions.

The winner is: Antonie Henning (http://21500.net). Ivan Pepelnjak helped finding a logical “loophole” in my scenario by pointing to the “route-via” option available with GRE tunnels and correctly stating there should be 6 end-to-end tunnels to implement proper load-balancing. Hans Verkerk was close in his idea, but used static routing which was slightly against the rules and not as elegant as Antonie’s solution. Chris Stos-Gale and Nitzan Tzelniker came with the correct solution as well, but Antonie completed the challenge ahead of them. Thanks to everyone for participating in the challenge, it’s been fun!

The Solution:

The problem is that there are three paths with varying minimum bandwidth values (50, 100 and 150, totaling to 300Mbps). Since OSPF does not support unequal-cost load-balancing, it is somewhat challenging to fully use the available bandwidth. There was a lot of ideas posted in the comments, and they mainly fall in three main categories:

1) Modify OSPF costs to create three equal cost paths from R4 to R1. This will result in slow (50Mbps) link oversaturation. Another variation was using three tunnel interfaces between R1/R4 with the same ECMP logic. This results in the same problem.
2) Create six tunnels between R4 and R1 and configure the network so that 3 tunnels go across the fastest path, 2 tunnels take the medium path and one tunnel take the slowest path. This is somewhat similar to MPLS TE. To steer the tunnels you may use either static routes or the “route-via” option (Thanks to Ivan Pepelnjak to pointing me that!!). This solution would work, but violate the “updated” requirement not to use any “policy-based” routing decision, relying purely on OSPF path selection.
3) The solution that I had on mind was splitting the links connecting R4 to it’s neighbors into “sub-channels” proportional to the bandwidth assigned to a given path:

ospf-traffic-engineering-solution

The link labels represent OSPF costs. You only need to split the links at R4, as this is the “source” of the traffic flows. Link splitting could be done in two ways: using logical virtual circuits (e.g. FR PVCs or Ethernet VLANs/VCs) or by using IP tunnels. You will only need to run the IP tunnels between R4 and the directly attached routers, disabling OSPF on the physical link and enabling it on the tunnels. Sample output at R4 for R1′s prefix:

R4#show ip route 10.0.1.1
Routing entry for 10.0.1.1/32
  Known via "ospf 1", distance 110, metric 4, type intra area
  Last update from 10.0.3.3 on Tunnel341, 00:46:50 ago
  Routing Descriptor Blocks:
  * 10.0.45.5, from 10.0.1.1, 00:46:50 ago, via Serial0/0/0.45
      Route metric is 4, traffic share count is 1
    10.0.3.3, from 10.0.1.1, 00:46:50 ago, via Tunnel340
      Route metric is 4, traffic share count is 1
    10.0.3.3, from 10.0.1.1, 00:46:50 ago, via Tunnel341
      Route metric is 4, traffic share count is 1
    10.0.1.1, from 10.0.1.1, 00:46:50 ago, via Tunnel142
      Route metric is 4, traffic share count is 1
    10.0.1.1, from 10.0.1.1, 00:46:50 ago, via Tunnel140
      Route metric is 4, traffic share count is 1
    10.0.1.1, from 10.0.1.1, 00:46:50 ago, via Tunnel141
      Route metric is 4, traffic share count is 1

Summary

I would like to thank everyone who participated in the “challenge”, I read all your responses but had to stop commenting when I found the right solution. I hope you enjoyed that little scenario as much as I did. Personally, I have some incline toward the “traditional” traffic engineering solutions based on pure IGP metric manipulation. Even though the solution presented does not scale in the real world, where you may resort to a different option (e.g. end-to-end route-via tunnels), it perfectly illustrates the little hacks you can do to a link-state IGP to break the default “ECMP paradigm”.

About Petr Lapukhov, 4xCCIE/CCDE:

Petr Lapukhov's career in IT begain in 1988 with a focus on computer programming, and progressed into networking with his first exposure to Novell NetWare in 1991. Initially involved with Kazan State University's campus network support and UNIX system administration, he went through the path of becoming a networking consultant, taking part in many network deployment projects. Petr currently has over 12 years of experience working in the Cisco networking field, and is the only person in the world to have obtained four CCIEs in under two years, passing each on his first attempt. Petr is an exceptional case in that he has been working with all of the technologies covered in his four CCIE tracks (R&S, Security, SP, and Voice) on a daily basis for many years. When not actively teaching classes, developing self-paced products, studying for the CCDE Practical & the CCIE Storage Lab Exam, and completing his PhD in Applied Mathematics.

Find all posts by Petr Lapukhov, 4xCCIE/CCDE | Visit Website


You can leave a response, or trackback from your own site.

39 Responses to “Traffic Engineering Challenge”

 
  1. Bill Brandt says:

    Maybe I’m missing something, but I would think that you can build 6 gre tunnels. Leave them all ip unnumbered since the requirement says to not add IPs. For three of the tunnels, the source and destination will make them traverse the 150M link; two will traverse the R1-R2-R3-R4 path; one will traverse the R1-R5-R6 path. This is achieved by setting the source and destination to make them take the right paths. The route are advertised over these paths with a low but equal cost and R1 & R4 are set to have a maximum-paths 6 setting. This should make those routes show up as equal across all six paths and allow 6-way balancing.

  2. Two GRE tunnels with tunnel route-via option.

  3. Maksim says:

    We need to set auto-cost reference bandwidth on R1 to 1 so that R1 calculate metric based on hop count to R4.
    Then on links beetwen R1-R4 and R5-R4 we change network type to point-to-multipoint . Then change cost on interface R1 to R4 to 3 and cost on interface R5 to R4 to 2.
    So metric on R1 to R4 loopback interface would be 4 through R2,R4 and R5.
    R1:
    auto-cost reference-bandwidth 1
    neighbor 10.0.14.4 cost 3
    R5:
    neighbor 10.0.45.4 cost 2

  4. IK says:

    Hi Petr,

    I’m not sure what do u mean under “users behind R1 need to use full 300Mbps of bandwidth when downloading files off the servers”, but in case I had to route traffic via 1-2-3-4 I would do something like this:

    0. auto-cost refference-bandwidth on all routers making cost of any 300mb to 1
    1. play with interface costs on R4 making route 1-2-3-4 more preferrable

    but it’s too simple to be an answer for Peter’s question…

  5. Karim says:

    Hi,

    First, I will modify the ospf cost on different interfaces.
    I will put “ip ospf cost 2″ command between R1-R2, R2-R3 and R3-R4, “ip ospf cost 6″ command between R1-R4 and “ip ospf cost 3″ command between R1-R5 and R5-R4.
    When you do “show ip route os”, you should see 3 routes for the same destination with a cost equal to 6.

    Secondly, I think that you need to put “ip cef distributed” command to activate the load-sharing between theses 3 routes and also you can use full 300Mbps bandwidth (from R1 to R4 : 100Mbps via R2 + 150M via R4 + 50M via R5 = 300M)

    Maybe it works…

    Karim

  6. Cristian says:

    Do you need the exact configs or just the idea?

    Create 3 unnumbered tunnel interfaces on each router
    Force each tunnel to take a separate path by adding a static route via the path you need.

    Tune up the OSPF cost for each tunnel to make the paths via tunnels of equal cost. OSPF will do the load balancing

  7. Hans Verkerk says:

    Hi,

    I have left the routing protocol intact, but I included several static routes in my solution. Let’s assume subnet 11.11.11.0/24 is terminated on R1 where clients resides which are downloading content from behind R4′s media servers.

    Seen from R4, traffic towards subnet where “clients” terminates to R1, must be distributed to R3, R1 and R5 in a 2:3:1 fashion towards 11.11.11.0/24 subnet.

    Let’s futher assume links from R1-R2 are numbered 12.12.12.0./24, from R2-R3 23.23.23.0/24, etc.Also loopback from R1 is numbered 1.1.1.1/32, from R2 2.2.2.2/32 , etc

    In order to meet the requirement I have created a GRE tunnel interface on R1 and R4 (thanks for the hint!). And after this I created static routes pointing to next-hops and interfaces to fullfill the loadbalancing requirement which was early mentinoned:

    ip route 11.11.11.0 255.255.255.0 34.34.34.3
    ip route 11.11.11.0 255.255.255.0 FastEthernet0/0.34
    ip route 11.11.11.0 255.255.255.0 14.14.14.1
    ip route 11.11.11.0 255.255.255.0 FastEthernet0/0.14
    ip route 11.11.11.0 255.255.255.0 Tunnel0
    ip route 11.11.11.0 255.255.255.0 45.45.45.5

    Regards,
    Hans

  8. [...] browsing blogs, when I should be labbing I came across INE’s OSPF challenge. I normally ignore these because I happen to see them when they usually already expired. Well this [...]

  9. Ahenning says:

    Read it again and adjusted the loadbalancing:

    Routing entry for 100.100.100.0/24
    Known via “ospf 1″, distance 110, metric 4, type intra area
    Last update from 3.3.3.3 on Serial1/0.1, 00:00:01 ago
    Routing Descriptor Blocks:
    * 5.5.5.5, from 1.1.1.1, 00:00:01 ago, via Serial1/3
    Route metric is 4, traffic share count is 1
    3.3.3.3, from 1.1.1.1, 00:00:01 ago, via Serial1/0.1
    Route metric is 4, traffic share count is 1
    3.3.3.3, from 1.1.1.1, 00:00:01 ago, via Serial1/0.2
    Route metric is 4, traffic share count is 1
    1.1.1.1, from 1.1.1.1, 00:00:01 ago, via Serial1/1.2
    Route metric is 4, traffic share count is 1
    1.1.1.1, from 1.1.1.1, 00:00:01 ago, via Serial1/1.1
    Route metric is 4, traffic share count is 1
    1.1.1.1, from 1.1.1.1, 00:00:01 ago, via Serial1/1.3
    Route metric is 4, traffic share count is 1

  10. Garth Bryden says:

    I would change the ospf costs on the interface.

    on R4 -> R3 -> R2 -> R1 I would set the ospf cost to 10 on all of those links manually using the “ip ospf cost” command under each of the interfaces this would make the metric look like it was 30 on R1

    Between R1 and R4 link would set the ip ospf cost on to 30

    Between R4 -> R5 -> R1 link I would set up the ip ospf cost of 15 which make the link look like it also had a cost of 30.

    Using the metrics R1 will place all three routes in the routing table, since it can equally load balance up to four routes by default and equally share the traffic among the three paths.

    Can’t do anything like unequal cost load balancing here because we are not using eigrp which is the only IGP that can support it.

  11. Kelvin Chia says:

    R1 to R2, R1 to R5 & R1 to R4 interfaces to equal “ip ospf cost” for equal load-balancing within 300Mbps.

  12. Kelvin Chia says:

    Sorry made a mistake.

    R4 to R3, R4 to R1 & R4 to R5 interfaces connected must to equal “ip ospf cost” for equal load-balancing within 300Mbps.

    Since R4 is the one distributing the data to R1. R4 have to do the decision making to how to send the data to optimized the load on the links.

  13. Alejandro says:

    !
    ! R4
    !
    !
    ip cef
    !
    !
    interface fa0/0
    !
    description R4-R3 link
    !
    ip load-sharing per-packet
    !
    exit
    !
    !
    !
    interface gi0/1
    !
    description R4-R1 link
    !
    ip load-sharing per-packet
    !
    ip ospf cost 3
    !
    exit
    !
    !
    !
    interface gi0/2
    !
    description R4-R5 link
    !
    ip load-sharing per-packet
    !
    exit
    !

  14. Tim says:

    1) Create a tunnel using the loopback IPs of R1 and R4 as the source and destination. Make sure that OSPF is routing across the tunnel between R1 and R4 and use a distribute-list for tunnel recursion issues.
    2) Make sure that these end-point IP’s have an equal cost in OSPF across all 3 paths to the tunnel destination from R1 and from R4. (Equal cost load balancing should be already active up to 4 links in OSPF by default).
    3) Have each physical interface on R1 and R4 traffic-shape to the lowest bandwidth link for each of the three paths between them.

  15. Garth Bryden says:

    Just had a re-think about this, doubt i’ll be coming in first now but o well ;-) I’d just change the cost on the R4 interface connected directly to R1 to 3.

    The links between R4 -> R5 – > R5 will already have a cost of 3…
    bandwidth of 50mbps = 2 and anything over 100mbps will be equal to 1

    The links between R4 R3 R2 and R1 will be at 3 because there are 3 hops, and all over 100mbps. :-)

  16. Gabor Ivanszky says:

    My proposal is to create six tunnels between R1 and R4. The idea is to have 50Mbps traffic on each tunnels, using equal cost load-balancing.

    We have to steer
    - tunnel 1 through R5
    - tunnels 2-4 through R1
    - tunnels 5-6 through R3-R2 path
    somehow.

    To accomplish this, we need to use the following tunnel source and destination addresses:
    tunnel 1: R4′s IP address on R4-R5 link, and R1′s IP address on R1-R5 link
    tunnels 2-4: R4′s IP address on R4-R1 link, and R1′s IP address on R1-R4 link
    tunnel 5-6: R4′s IP address on R4-R3 link, and R1′s IP address on R1-R2 link

    and set “max-metric router-lsa” on R1 and R4.

    (We need to use tunnel keys also, because we have multiple tunnels with the same source and destination IP addresses)

    regards,
    Gabor

  17. Chris Stos-Gale says:

    OSPF won’t do unequal cost load balancing. Therefore, you would need a number of links over the various routes proportionate to the bandwidth share.
    In order to do this, create a link for each 50 Mbps. that breaks down as:-
    R1-> R2 = 100M Min Bandwidth
    1 Physical
    1 Tunnel

    R1 -> R4 = 150 Mb/s Min Bandwidth
    1 Physical
    2 Tunnels (use tunnel key to identify which tunnel is which as you have to use the same source / dest addresses)

    R1 -> R5 = 50 Mb/s Min Bandwidth
    1 Physical

    Once you have also entered maximum-paths 6 under the OSPF process, this will cause OSPF to load balance accross 6 links equally causing it to use 300 Mb/s of total bandwidth between R1 and R4.

    In order to make the costs equal for all paths, set the ospf costs under each interface so that they are all equal between R1 and R4. In my lab, I set them all to 1, then incremented them to 3 between R1 and R4, and 2 between R1 and R5. This means each path totals up to a cost of 4.

    this will result in:-

    Routing entry for 4.4.4.4/32
    Known via “ospf 1″, distance 110, metric 4, type intra area
    Last update from 2.2.2.2 on Tunnel122, 00:00:04 ago
    Routing Descriptor Blocks:
    172.16.15.5, from 4.4.4.4, 00:03:00 ago, via FastEthernet0/1
    Route metric is 4, traffic share count is 1
    * 172.16.14.4, from 4.4.4.4, 00:03:00 ago, via FastEthernet1/0
    Route metric is 4, traffic share count is 1
    172.16.12.2, from 4.4.4.4, 00:00:04 ago, via FastEthernet0/0
    Route metric is 4, traffic share count is 1
    4.4.4.4, from 4.4.4.4, 00:03:00 ago, via Tunnel141
    Route metric is 4, traffic share count is 1
    4.4.4.4, from 4.4.4.4, 00:03:00 ago, via Tunnel142
    Route metric is 4, traffic share count is 1
    2.2.2.2, from 4.4.4.4, 00:00:04 ago, via Tunnel122
    Route metric is 4, traffic share count is 1

    All tunnels use physical addresses for source and destination, and are unnumbered to lo0 Threfore meeting the requirement of not adding any additional IP addresses.

  18. Chris Stos-Gale says:

    Sorry in correction to my previous comment, in order to have symmetric routing, you would also need to configure this similarly on R4, with:-

    R4->R3 = 100 MB/s Min Bandwidth
    1 Physical
    1 Tunnel

    R4->R1 = 150 Mb/s Min Bandwidth
    1 Physical
    2 tunnels (use tunnel key to identify which tunnel is which as you have to use the same source / dest addresses)

    R4 -> R5 = 50 Mb/s Min Bandwidth
    1 Physical

    This will allow traffic from R4 to R1 to be equally load balanced accross the 6 paths (50 Mb/s each) resulting in 300 Mb/s of total bandwidth.

  19. Nitzan Tzelniker says:

    Just create to sub interfaces between R1->R4 (Total 3)
    create another sub interface between R1->R2 and R3->R4 (Total 2)
    and leave only one interface between R1->R5 and R4->R5
    now equalize the metric between R1 and R4 so they will see 6 ECMP links

    R1->R2 10
    R2->R3 10
    R3->R4 10
    R1->R4 30
    R1->R5 15
    R5->R4 15

    don’t forget to enable max path of 6 in ospf

    Nitzan

  20. Nic says:

    Since the other two paths result in EQUAL costs, I would say that setting the bandwidth of the link between R1 and R4 to 42.86M will result in a cost of 23.33, equal to other costs and will result in 3 equal cost routes installed in the routing table for R4.

    so

    Interface
    bandwidth 43

  21. @Bill Brandt

    Bill, the idea would work “in general” but you cannot easily affect paths in single-area OSPF based the destination addresses, due to the problems of “global” cost manipuations.

  22. @Ivan Pepelnjak

    Ivan, I knew you would be the first one to come up with a “real-world” solution, similar to MPLS TE tunnel. I tried to rule out end-to-end tunnels as part of the solution, but to my shame I missed the “route-via” option. However, if that would be a real scenario, I would probably resort to the end-to-end tunnels due to their flexibility.

  23. @ Maksim

    You are trying to engineer paths from R1 to R4, while the task is looking for optimizing the reverse paths, from R1 to R1. Besides, relying on pure ECMP here will result in slower link overutilization. Maybe I’m missing something else from your solution though.

  24. @IK

    Correct, using just basic ECMP will not help here, as it will result in solution link overutilization.

  25. @Cristian

    Using tunnels between R1 and R4 could work, but static routes are not needed. You may simply use the “route-via” option. The more elegant solution would avoid using static routes though. Besides, using just 3 tunnels will result in equal-cost load-balancing and link oversubscription.

  26. @Karim

    Creating equal-cost multipath condition will result in slow link oversubscription as 300Mbps will be divided in three major flows.

  27. @Hans Verkerk

    Great, you correctly captured the idea of creating six equal-cost paths between R4 and R1 but the same could be achieved without use of any static routes, which significantly reduce the flexibility.

  28. @ http://21500.net/?p=969

    Even though you did not post a complete comment, I was amazed by the fact that you provide the exact solution I had on mind! Using logical subinterface has the benefit of solving the “MTU problem” inherent to every tunnel technology. This may not be applicable in a real network, but you can always replace local sub-interface with tunnels connecting two adjacent routers (which brings back the MTU issue though).

  29. Ahenning says:

    Yes, the asymmetrical mtu would complicate things.

    regards
    21500.net

  30. Shahid says:

    I still dont get it, if you want to utilize all 3 links from R1, then all 3 of them should be in the routing table. Why you are saying that creating 3 gre tunnels will over utilize the 50 mbps link ? can you define the traffic flow of the solution ?

    I really dont get it

    • @Shahid

      If you create 3 tunnels end-to-end between R4 and R1, you will have 3 equal-cost paths in R4. If you try transporting 300Mbps from behind R4, this flow will be split in 3x100Mbps flows equally across the three tunnels. The R4-R3-R2-R1 path is a bottleneck with 50Mbps, which will drop the exceeding 50Mbps of traffic. Thus, your effective utilization will be 250Mbps, with 50Mps underutilization across the fastest link (150Mps).

  31. Shahid says:

    Dear Petr, thanks for the feedback but i think i am still missing something.
    When you split the links from R4 to its neighbors, what R1 will be doing in that case ? will it not be sending the traffic to all 3 links ? how R1 is getting 300mbps throughput in your solution ?

    I am really confused pls explain

    • @Shahid,

      The key thing here is that we are only concerned with the traffic flow FROM R4 TO R1, but not the backwards. There are three paths from R4 to R1, with different minimum bandwidth values: 50M, 100M and 150M. To optimally utilize all three paths we need to load-balance FROM R4 to R1 in proportions 1:2:3. However, OSPF does not support unequal host load-balancing so we “fake” it by using additional equal-cost paths so that paths with more bandwidth receive more traffic than lower-bandwidth paths.

  32. Shahid says:

    Oh ok, now i get it. Thanks alot for the clarification :-)

  33. Boris says:

    Hey Petr,

    How come in your “show ip route” it says the metric is 4 and not 6

  34. Cristian says:

    Would you guys implement this in production?

    • @Cristian,

      Interesting question :) This approach does not scale at all plus in reality you dont have “bipolar” scenarios (one source one sink). In real networks there are multiple sources and sinks, described by the network traffic matrix. There are tolls to optimally adjust the IGP metric values to optimize *global* summary link utilization and those are pretty effective, sometimes competing with MPLS TE effectiveness.

  35. ob says:

    Could you explain the “route-via” option? It’s a bit hard to google for since you get all instances of people using the phrase “route via”

 

Leave a Reply

Categories

CCIE Bloggers