ABSTRACT
Communication networks have become ubiquitous today. The Internet, the global computer communication network that interconnects millions of computers, has become an indispensable part of our everyday life. This chapter discusses theoretical and algorithmic underpinnings of distributed communication networks focusing mainly on themes motivated by the Internet. The Internet is a distributed wide area communication network that connects a variety of end systems or hosts by a network of communication links and packet switches (e.g., routers). A packet switch takes a packet arriving on one of its incoming communication links and forwards that packet on one of its outgoing communication links. From the sending host to the receiving host, the sequence of communication links and packet switches is known as a route or a path through the network. Throughout we will use the term node to denote a host (processor) or a packet switch. The Internet is a complex system, but fortunately it has a layered architecture which is extremely
helpful in understanding and analyzing its functionality. This is called the network protocol stack and is organized as follows. The understanding of different layers of the stack allows us to tie the
theoretical and algorithmic results that will be discussed to specific functions and protocols in the Internet. Application layer: The application layer is closest to the end user. This layer interacts with software applications that implement a communicating component. The layered architecture allows one to create a variety of distributed application protocols running over multiple hosts. The application in one host uses the protocol to exchange packets of data with the application in another host. Some examples of application layer implementations include Telnet, File Transfer Protocol (FTP), Simple Mail Transfer Protocol (SMTP), and the Hypertext Transfer Protocol (HTTP). An application architecture determines how a network application is structured over the various hosts. The traditional application architecture paradigm has been the client-server paradigm. In a client-server architecture, there is an always-on host, called the server, which services requests from many other hosts, called clients. For example, all the above applications-Web, FTP, Telnet, and e-mail-are client-server based. The last few years has seen the emergence of a new paradigm called Peer-to-Peer (P2P) architecture. In P2P architecture, there is no concept of a dedicated, always-on, server. Instead hosts, called peers, communicate directly and a peer can act both as a client (while requesting information) or as a server (when servicing requests for other peers). Many of today’s most popular and traffic-intensive applications, such as file distribution (e.g., BitTorrent), file searching (e.g., Gnutella/LimeWire), and Internet telephony (e.g., Skype) are P2P based. A key application of P2P is the decentralized searching and sharing of data and resources. The P2P paradigm is inherently scalable as the peers serve the dual role of clients and servers.
