The internet is an incredibly intricate mesh of nodes with several central nervous centers that deliver media, knowledge, and communications around the world at nearly the speed of light. Complex algorithms are used to determine how to get from node A to node B quickly and efficiently, but this “giant network” is a compilation of non-standardized routing technologies that can in their attempt to streamline network operations, in fact, cause congestion. In Artur Czumaj’s paper Selfish Routing on the Internet he examines the results of internet routing protocols utilizing game theory and Nash Equillibria.

Czumaj argues that since the internet has developed so rapidly, grown to such an enormous size, and was founded upon non-standard, open architectures, the lack of central arbitration prevents system wide monitoring and control. Thus, the most logical way to get from point A to point B is to do so by maximizing one’s individual welfare. An analogy can be drawn between our study of network traffic in class and the routing protocols that decide which path a user’s packet should take based on a complex set of metrics. Contrary to the example in class, the roads will be represented by data paths (internet backbones, local loop connections, etc.), and packets will traverse the network as opposed to vehicles. Furthermore, the intelligence that governs which path a packet will take is established by algorithms rather than individuals deciding which way to go.

A commonly used protocol used between internet service providers (ISPs) is called the Border Gateway Protocol (BGP). BGP utilizes metrics such as bandwidth, uptime, administrative priority, and quality of service statistics (QoS) to determine the best path for an outgoing data packet to follow. This protocol chooses the best path available at each instant in time, therefore maximizing the welfare of each end-user (by minimizing the time for their information requests to be answered). However, as we discovered in class, this may not be the best case scenario when it comes to maximizing social welfare (minimizing the response time for all internet users).

By simplifying the scenario, Czumaj creates a model where each player (packet) is aware of all of the other player’s strategies and therefore each tries to minimize their respective costs. Thus each router will “selfishly” send packets down the least costing paths until those paths become congested, at which point they will begin forwarding packets down another, previously neglected path. The end result of this dynamic, lowest cost routing method is a Nash Equilibrium of the network that is generally slower and more congested than the ideal state.

A possible way to avoid this undesirable outcome would be to incorporate greater intelligence into routers and routing protocols. The ideal system would not only detect which paths are currently the least congested, but would also assess the ramifications of sending packets currently queued in the router’s memory buffer down these paths. The result of this “forward thinking” would enable routers to choose the paths that are not necessarily the fastest at a given juncture in time, but would increase overall social welfare, by decreasing the average packet transit times across the network.

Czumaj continues to support his claims with in depth mathematical and statistical proofs, which are certainly too complex for the casual onlooker. The outcomes of selfish routing, as discussed in the paper, will certainly need to be addressed and accounted for, as the internet continues to expand in size and capability at an exponential rate.

References:

Artur Czumaj

Selfish Routing on the Internet

http://www.cis.njit.edu/~czumaj/PUBLICATIONS/Selfish-Routing-Survey.pdf

Border Gateway Protocol (BGP)

http://www.techworld.com/networking/features/index.cfm?featureid=600