Cisco Support Community
cancel
Showing results for 
Search instead for 
Did you mean: 
New Member

Karn's algorithm

In a previous conversation, I had asked for a possible solution to a problem I was facing, which was to get a router to send packets back onto the LAN and route through a backup router if it turned out that it would be a quicker path (the conversation was entitled "Which routing protocol?" if you want a long winded explanation). Unfortunately, after asking over the forum, I didn't get a solution. Then after speaking to instructors and my Cisco Academy I got some puzzled looks, "it sounds like it could be done, but i don't know how" was a familiar cry.

I have recently stumbled upon something called "Karn's Algorithm" but am struggling to find a good resource to explain about it on the internet. Can anyone here explain if it will help me and how it is implemented or even point me in the direction of a good resource.

1 ACCEPTED SOLUTION

Accepted Solutions
New Member

Re: Karn's algorithm

Yes...we can do that! :-)

The good news is we have a solution or your problem, the not-so-good news is that it is not released yet (we're in the middle of pre-EFT right now).

Routing protocols don't do a good job in taking path changes into account...in general the metrics are pretty much static (unless we manually change the bandwidth or delay, for example). However, manual changes are not administratively viable all the time and you want the path to change when the conditions change, but go back to the default when the conditions change back...

We have a new solution called Optimized Edge Routing (OER), which takes delay (among other metrics) into account to "help" the routing protocols make informed decisions. I expect (not set in stone) that we will have a realeased version of OER sometime early next year. There's not a lot of public documentation available on OER, but I gave a presentation that covered it at Networkers this year...I posted the presentation at: ftp://ftp-eng.cisco.com/alvaro/4004.pdf

Regards, Alvaro.

5 REPLIES
Silver

Re: Karn's algorithm

Karn's algorithm tells TCP not to update the value of Round Trip Time (RTT) until you send a segment and receive an ACK for this segment without the need for retransmission.

Suppose you send a TCP packet which gets losts. So you send a second packet. After sending this second one, you receive an ACK. Now here is a problem, this ACK is for the first segment or the second one you sent? Karn simply ignores both of these packets for RTT calculations.

Hope this helps.

New Member

Re: Karn's algorithm

thanks for the reply.

helps? yes....and no.

Yes, it helps explain a bit about Karn's algorithm but tells me that it won't help with my original problem.

cheers

New Member

Re: Karn's algorithm

I don't think Karn's Algorithm (which applies to TCP) will help you solve the original need ("send packets back onto the LAN and route through a backup router if it turned out that it would be a quicker path").

In routing, a "quicker path" translates simply into a path with a better metric (for multiple meanings of "quick"). Two quick observations:

(1) In your LAN scenario, the reason a router would forward a packet "back onto the LAN" is because the sender thought it was the best path (vs the alternate "quicker path"). In general this results from the fact that the sender has no routing information (just a default gateway = host). If the router knows of the "quicker path" (it should if it's running a routing protocol w/the alternate router), then it should redirect the packet back out the LAN. All this is normal redirect operation.

(2) The other possible scenario that comes to mind is the case in which the sender is also a router (not a host)...which means that it should already know about the "quicker path" and not forward the packet in the wrong direction in the first place.

Note that I didn't mention any routing protocols because all that I described above works with all of them -- based on the individual metrics each of them uses.

I don't know the details of your setup, but what you're asking is definetly possible -- for my interpretation of a "quicker path". ;-)

Alvaro.

New Member

Re: Karn's algorithm

well, to give you a few more details...

the first router, we'll call it 'A' for this purpose, is the default gateway and connects to a remote office through an IP tunnel. Occasionally, the latency for this route jumps by about 10 times normal. When this happens, I want the router to recognise this jump and dynamically re-route the packets back on to the LAN and on to router 'B', which is only ever used as a backup for when router 'A' is out of use.

Any ideas?

New Member

Re: Karn's algorithm

Yes...we can do that! :-)

The good news is we have a solution or your problem, the not-so-good news is that it is not released yet (we're in the middle of pre-EFT right now).

Routing protocols don't do a good job in taking path changes into account...in general the metrics are pretty much static (unless we manually change the bandwidth or delay, for example). However, manual changes are not administratively viable all the time and you want the path to change when the conditions change, but go back to the default when the conditions change back...

We have a new solution called Optimized Edge Routing (OER), which takes delay (among other metrics) into account to "help" the routing protocols make informed decisions. I expect (not set in stone) that we will have a realeased version of OER sometime early next year. There's not a lot of public documentation available on OER, but I gave a presentation that covered it at Networkers this year...I posted the presentation at: ftp://ftp-eng.cisco.com/alvaro/4004.pdf

Regards, Alvaro.

499
Views
0
Helpful
5
Replies
CreatePlease to create content