Talk:Shortest path routing

SPF runs in small routing domains

We should not be suggesting that SPF is the Internet-wide routing algorithm, or, indeed, that there is any one algorithm. SPF is quite effective in networks, or hierarchical subareas of networks. Even real-world intradomain routing protocols such as OSPF use distance vector routing for their inter-area and external routes. The overall Internet (and large private system) Border Gateway Protocol uses path vector routing with a considerable number of policy extensions, the policy so dominating that BGP is not infrequently called a reachability protocol rather than a routing protocol. Howard C. Berkowitz 22:32, 24 December 2009 (UTC)

Good points. I can see there are some unintended suggestions in the second paragraph of the intro. How about "This article will explain a basic routing algorithm [1] commonly used in routing protocols for small to mid-sized networks." I'm still a little puzzled by what this means in real numbers. Peterson & Davie (p.267) say "fewer than a hundred nodes". The Python program in this article will compute a routing table of 3000 nodes in 1.2 seconds. In C, this would be more like 12 msec. Surely this is fast enough for a network where link costs change over a period of hours. --David MacQuigg 20:57, 25 December 2009 (UTC)

Small to medium sized networks, or small to medium sized subdomains of large networks.

The hundred node (specifically router nodes) is an old Cisco guideline, written for a time when the processor in a high-end router was a 68040. The issue isn't so much that node cost changes, but that a node is no longer reachable and the entire table has to be recomputed -- especially in routers where the same processor calculates and forwards. It is not at all unprecedented for forwarding to stop while the forwarding table and routing table (if separate) are recomputed. Remember, too, that a real routing protocol such as OSPF only uses the Dijkstra algorithm for intra-area routes, and still has to do distance vector for inter-area and external routes.

While the Dijkstra algorithm is running, processor utilization often spikes to near 100%, which is acceptable if the processor is just doing route calculation, but a problem if it's doing other real-time things.

I certainly know of real networks with 1500 router nodes in an area, but I don't necessarily reject the idea of keeping the number of routers in an area down to the low hundreds. The reason is less computation load than the operational difficulty of going through a link state data base with huge numbers of entries. Good routing architects also try to minimize the number of routers, topologically in an area, that actually run the SPF computation; edge/stub routers can get by perfectly well with static default routes.

Do consider the needs of real-time routing. It takes about 1.2 msec for a maximum length 802.3 frame, at 10 Mbps, to move across a serial interface. Scaling that up, in that same 1.2 msec, if the processor isn't forwarding, 10 Fast Ethernet, 100 Gigabet Ethernet, or 1000 10GE frames, per interface, can be dropped. For your 12 msec, multiply by 10, and then consider that the router might have 8-24 interfaces. 40 Gbps is now reasonably common in large ISP routers, with 100 Gbps starting to happen.Howard C. Berkowitz 22:40, 25 December 2009 (UTC)

Thinking about this a bit more, the long packet problem is actually the best case. One of the most frequent packet sizes is 42 bytes, which is the minimum of a TCP acknowledgement (without compression), which has to be padded to 64 bytes in 802.3. With more and more VoIP, short packets are even more common. If the TCP acks are lost, it may set off a retransmission storm. Howard C. Berkowitz 23:17, 25 December 2009 (UTC)