Moreover, new high-bandwidth applications arise (like "Web-TV") or will arise, imposing high "Quality of Service" demands on ISPs (Internet Service Providers).

Therefore, current and future strong demands for high baud (= throughput) rates per user, as Internet usage increases, require network technology to adapt quickly to the new needs. In this project, we are examining the factors which restrict or will restrict future required capacity of the network.

Those restrictions are based primarily on the bounded capability of future IP (Internet Protocol) routers, to forward "quickly enough" incoming packets to the proper destinations, due to several physical limitations, like finite (not zero) memory access time (needed for searching in the routing table the proper destination port) or switch time (needed to connect input and output ports) of the router. 

We are describing the current and future "bottlenecks" of IP routing technology and using fundamental quantum mechanics principles, we are estimating the ultimate, best achievable, future capacity of "The Internet"!

Bandwidth limitations are also considered. However, they are not so critical as the routing ones, as we will prove!

BANDWIDTH LIMITATIONS
A simple question: 
is bandwidth a current limiting factor on the expansion of Internet?

We can answer that question very easily:

Current available fiber point-to-point links have a capacity of Terabits/sec. This estimation comes from the following calculations:

Due to physical factors, light passes easily through fiber in only three parts of the optical spectrum. These bands are about 200 nm wide and are centered around 3 specific wavelengths:

At these specific wavebands, the absorption of light due to impurities in the glass core of the fiber, is minimal (at least, in large part). Using equations (1),(2) we obtain:

Given that standard signaling equipment can signal at least 1 bit/Hz, we can see estimate the fiber capacity in the Terabit/sec regime!

Shannon theorem, assuming a Gaussian channel, also gives the same estimate:

Modal, chromatic and material dispersion of the light pulse, impose an upper bound on the overall fiber capacity, however we can safely assume that Tbps rate is reachable.

However, available, commercial, state-of-the art IP routers, can work only at Gbps rate!

So, the most serious, CURRENT, limiting factor on the expansion of Internet is basically the routing capability of IP routers, not bw! 

Therefore, in order to understand the IP routers limitations, we will have to discuss basic IP routing principles:
 
 

ROUTING
Basic Principles
With the term "router" we mean the layer-3 ("network layer" according to O.S.I hierarchy) intermediate system, which is responsible for "packet switching". Every IP packet ‘travels’ from source endpoint to destination through a connectionless "best effort" layer-3 service. IP routers, within an autonomous network communicate with each other through Intra-domain Gateway protocols (like Routing Internet Protocol, Open Shortest Path Find). When they are used for connecting many autonomous networks, they interchange information through Inter-domain Gateway protocols (like Border Gateway Protocol).

In every case, an IP router is informed about the logical topology of the networks within it operates and updates its routing table, which associates every possible packet destination with one of the router ‘s physical ports. The routing table is used in forwarding every incoming datagram (= IP packet) to the proper output physical interface so as the packet can continue it’s travel to the next router or final destination.

So, the router must be able to:

     ..."read" incoming information at the physical layer, 
     ...remove data link layer header (data link decapsulation), extract the IP information,
     ...estimate the proper output link based on the IP destination, 
     ...encapsulate the new data link layer header and 
     ...forward the packet with the proper output physical format!

IP Routers Architecture
A generic router follows. We have skipped every connection between the modules, so as to provide the most general router, without sticking to any particular architecture.

The "INPUT proc" is responsible for operations a),b), "Internet proc" is responsible for the implementation of the routing protocols and the estimation of the routing table, "forward proc" uses the forwarding information from the routing table to estimate the output interface for every incoming packet and triggers the switch fabric to forward packet to proper output interface. "OUTPUT proc" is responsible for d),e). Queuing may be needed at input and output interfaces either because of ‘burst’ incoming traffic or because the router offers "class of service" packet prioritization, therefore forwards the packets not in a FIFO manner.

Note that Internet processor is a different module than forward processor. That is necessary, so as the timely update of the routing table does not block the forwarding functions of the router (and as a result decrease its efficiency).

{Some routers architecture combine separate input and output buffers for every physical port. Others, also incorporate separate forward table for every physical interface. In the following section, it will be clear that our analysis is architecture independent}

Packets are coming from several input interfaces, so the forward processor must find the proper output physical port and trigger accordingly the intermediate interface in order to connect input with output. That intermediate interface which connect N input physical interfaces to N outputs, is called ‘switch fabric’:

The switch fabric architecture differs from implementation to implementation:

IP Addresess and Routing Table

Before analyzing the scaling problems of an IP router, we must clarify the following:
 

1. IP routing is based on "longest match" IP prefixes. The routing table, at least at backbone level, mainly contains routing information between subnets, not between hosts. In that way, the hierarchical organization of the Internet is being considered and the routing tables are simplified. However, they can be quite large. The number of entries can exceed 80,000, and the increase is related to the overall expansion of Internet!
2. IP routers must support CIDR (Classless InterDomain Routing) addresses. Initially, IP version 4 addresses were confined to class A (1-byte mask), class B (2-byte mask) and class C (3-byte mask):

Therefore, network prefixes in Ipv4 have variable length, which can be found if we know the ‘subnet mask’. 

1. As a result, IPv4 addresses which have 4 bytes, may have a network prefix from 8-24 bits (for CIDR the network prefix can be 29 bits long)
2. IPv6 supports 16 byte addresses, with network prefixes up to 121 bits. Routers should be able to scale easily to IPv6 addresses. 

 

 
 
 

• Can the photo-detector (transformation from photons to electrons) at input interface impose physical restrictions at the router’s forwarding speed? 
• How quick can be a "longest match" (= therefore, searching string of variable length) in a big routing table?
• How quick can be the switch fabric of N inputs-outputs, knowing that incoming packets have variable length?

FINDING PHYSICAL CONSTRAINTS
Optoelectronics
The photoelectric detector response time is proportional to  where  is the mobility and L is the length of the semiconductor. So, we can fabricate photodetectors on thin films of high mobility materials like Cadmium sulfide (CdS).

There are commercially available photodetectors (InGaAs/Schottky) with response time at the order of psecs -> Terabits = baud rate of a fiber.

from the above calculations, we can safely infer that the photodetector cannot delay the overall forwarding capability of the router!
 

Memory access

As we have said, the router must make a match in a big lookup table of a string (destination IP subnet or whole IP) which does not have a fixed length (because subnets are described by different number of bits).

The problem of a table look-up can be addressed by several approaches:

Digital search techniques

One of the most common approaches for address table lookup is a Patricia tree, which is a special case of a digital search tree. The idea behind this data structure is basically a binary search tree. Depending on the value of a particular bit in the search string, the search will take a left or right subtree. 

With some modifications, the order of complexity may be slightly reduced, yet none of those modifications produce significant improvement from O(n), where n is number of bits in a search string, (32,128 at most for IPv4, IPv6 respectively). If N are the total number of entries in the table then O(logN/log2) is the required time for lookup.

Content-addressable memory-based searches

Content-addressable memory (CAM) is a perfect solution for a really small search space. These special-purpose chips are fast and reliable. However, this solution is very expensive and not at all scalable, which is why even IPv4 routers use different approaches. 

Because an IPv6 address is 128 bits wide, it will further reduce the number of entries per CAM chip. Clearly, this solution is not suitable for the purposes of IPv6 address lookup. 
 
 

• Assumption: Let’s assume that we are clever enough, with a very smart algorithm and a special hardware architecture to find the pair "destination IP"- "output physical interface", in a single memory cycle (that would be the case for fixed length string)

• Current memory speeds are in the order of 20nsecs.

1 packet/memory cycle = 1packet / 20nsecs = 50 Mpps. 

That is the current routing table look up speed of the best commercially available Giga-router.

So, if we assume that packet decapsulation, switching and encapsulation cost zero time, then the minimum throughput of the router can be

50 Mpps * minimum internet packet length = 50 * 64 * 8 Mbps = 25,6 Gbps !!!

note: 64 bytes are the length of an Ethernet frame!

Even though the decapsulation, switching and encapsulation of the packet take almost zero time because of the ASIC architecture used, the routing table lookup takes more than a memory cycle.

However, clever algorithmic and hardware approaches have reduced the total required time for a "longest match" to:

8 memory cycles for Ipv4, 16 memory cycles for Ipv6!

The cost for that improvement, is increased memory cycles, when we want to update the routing table:

64/72 (insertion/deletion) memory cycles for Ipv4, 352/368 memory cycles for Ipv6!

So, for memory speed 20 nsecs:

8*20 nsec=160 nsecs => 6.25 Mpps => 6.25 * 64 * 8 = 3.2 Gbps (maximum forwarding capacity for a "nearly" perfect table lookup!)

the insertion of a new entry in the routing table will require 64*20 nsecs=1280 nsec.

For an OC-24 = 24 * 51.84 Mbps= 1.25 Gbps) interface of a IPv4 router, the smallest packet that can be received is Ethernet frame, (64 bytes long) which requires 

64*8/1.25 =410 nsecs.

Therefore, after the search is done, there are 410-160= 250 ns for other tasks, such as insertion or deletion of an entry, collection of statistical data,

and so forth. 

So, for insertion, 1280/250 = 5 packet forwards (at most) are needed!

If we were able to create 1 memory cell/atom, then the memory speed would be 1 nsec (that is the required time).

So, every number would be improved by a factor of 20 -> maximum throughput= 1 Tbps!

All the above are summarized in the following table:
 

Speed memory	Minimum (ideal) lookup time / packet	Algorithmic achievable look up time / packet (Ipv4)	Algorithmic achievable look up time / packet (Ipv6)
20 nsec	20 nsec => 50 Mpps	160 nsec => 6.25 Mpps	320 nsec => 3.125 Mpps
10 nsec	10 nsec => 100 Mpps	80 nsec => 12.5 Mpps	160 nsec => 6.125 Mpps
1 nsec	1 nsec => 1 Gpps	8 nsec => 125 Mpps	16 nsec => 61.25 Mpps
1fsec	1fsec=>1 Ppps	8 fsec => 125 Tpps!	16 fsec => 250 Tpps!

Note: the packet per sec rate can be multiplied by the current average Internet packet length = 2000 bits, to give bits per sec rate. A better estimate would be the multiplication with the minimum packet length, which is 64 bytes (Ethernet packet).

Using the "Principal Uncertainty" theorem, we can estimate the quickest memory, ever will be made, using electrons:

Therefore, the fastest memory will have an access time of 1 fsec, so the maximum packet search will be 1packet /1fsec=1peta pps=1Ppps!
 

The memory requirements for the algorithmic search are 315 bytes/ route (when compared to the 8 bytes/ route for Ipv4 or 32 bytes/route for Ipv6 with a direct memory lookup).
 

Memory requirements (bytes) (Ipv4, Ipv6)	80,000 routes	160,000 routes	1 M routes
Direct search	0.64M , 2.56M	1.28M , 5.12M	8M, 32M
Algorithmic search	25.2M	50.4M	315M

SWITCHING BETWEEN INPUT-OUPUT
Again, the ultimate, best switching rate of the intermediate interface using electrons, given that we have found the proper output physical interface of the router, can be found through the principal uncertainty theorem:

Therefore, the delay at the bus from input to output will be in the order of fsecs!

We must also notice that time is required for preprocessing(like IP header extraction) and postprocessing (incapsulation of data link layer header before forwarding the datagram to output port). Those operations are handled by ASIC interfaces at current routers technologies and they are quite fast.

CONCLUSION

The overall delay needed, due to physical constraints, for the "transit pass" of an internet datagram through the best electronic router ever made is in the order of several fsecs:

Overall delay: time for electron to photons + time for preprocessing + time for routing table look up + time for switching + time for post processing + time for transformation from electrons to photons = several fsecs 10-100 fsecs.

So the overall throughput of the best electron router will be 1/100fsecs = 10 Tpps! 

Note that we have excluded the time needed for the update of the routing table. That was the only architecture-dependent decision we made, when we provided the general scheme of an IP router. If the update procedure of the routing table blocks the forwarding capability of the switch, the above throughput rate must be divided by 5 at least, as that is the number of packets needed for the routing table to be updated.

However, future architectures will keep separated the forwarding from the routing table, in order to acquire the best throughput, allowing some faulty forwarding decisions.

What about latency?
At the above analysis, we assumed that the routing table is kept updated, in a timely manner. The routing protocols can efficiently estimate the network topology and therefore estimate the optimal routes (through Bellman-Ford algorithm(RIP) or Dijkstra algorithm (OSFP) ) only if the overall latency on the Autonomous System is reasonably small. If that is not a fact, then we are talking about a highly distributed, dynamic and stochastic system where routing becomes problematic!

Given that we have the optimal network, with routers performing at their limits estimated above, the latency of a datagram traveling around the earth in a fiber, would be more than 

2pi r/c=6.28*6.378 10⁶/3*10⁸ =12 *10^-2sec = 1.2 msec >> several fsecs, which correspond to the delay due to device physics of intermediate systems (IS).

Therefore, the limiting factor of the expansion of Internet is, again, the speed of light!
 
 

REFERENCES
[1] Gershenfeld N. "The Physics of Information Technology", pre-publication notes.
[2] Perlman R. "Interconnections Second Edition: Bridges, Switches and Internetworking Protocols", Addison Wesley, September 1999
[3] Partridge C. "Gigabit Networking", Addison Wesley, October 1993
[4] Kuhn K. "Laser Engineering", Prentice-Hall 1998
[5] Minoli D. Schmidt A. "Internet Architectures", Wiley 1998
[6] Belenkiy A. "Deterministic IP Table Lookup at Wire Speed" http://www.isoc.org/inet99/proceedings/4j/4j_2.htm#introduction
[7] Newman P. Minshall G. Lyon T. Huston L. "IP Switching and Gigabit Routers", Ipsilon Networks
[8] "Internet Backbone Routers and Evolving Internet Design", Juniper Networks
[9] http://www.3com.com/nsc/501302.html
[10] http://info.ewha.ac.kr/~iclab/lab/Homepage/layer3switch.html
[11] http://www.infoworld.com/cgi-bin/displayStory.pl?/features/990510mids.htm
[12] http://www.isc.org/ds/defs.html
[13] http://www.mids.org

Internet Statistics
According to MIDS  the  growth in the number of Internet hosts -- computers reachable through DNS -- which has been doubling annually for almost a decade, has slowed significantly. In round numbers, the measured annual growth rate  of the number of Internet hosts has just dropped from 100 percent per year to 60 percent per year. 

Among its many other monitoring services, MIDS has since 1990 been analyzing raw host survey data collected by Network Wizards www.nw.com). For example, the number of Internet hosts increased 79 percent per year for the 30 years between 1969 and 1999. After the  deployment of TCP/IP, the number of hosts increased 109 percent (doubled) per year between 1985 and 1999.

But the host count growth rate is now declining. According to MIDS analysis of Network Wizards data, the growth rate since 1996 has been 68%  per year, and since last year, 46% per year.

Roughly, hosts number currently increases by a factor of 1.6 instead of 2 (previous years rates)! 

• The number of hosts (locatable through DNS) will exceed 100 M, very soon!
for a nice applet displaying network "latency", "pinging" in Europe, click here!