Salsa - Networking

Topics

Nachos

Virtual Memory in Nachos

[ Source code in code/network | Quiz ]

Distribution of computation between several physical processors has become common in computer systems. This document discusses the networking component of operating systems. We first discuss networking in general terms and then explain the network implementation in Nachos.

Networking

Two schemes are in vogue for distributed computation. In a multiprocessor system, the processors share memory and a clock, and communication usually takes place through shared memory. In a distributed system, the processors do not share memory or a clock and communicate with one another through various communication networks, such as high-speed buses or telephone lines. From the point of view of a specific processor in a distributed system, the rest of the processors are remote, whereas its own resources are local. The processors in a distributed system may be called a host, site, or a node. When a process at site A wants to communicate with a process at site B, the message needs to routed properly to that site. This is the responsibility of a router. It can either be a host computer with routing software or a special-purpose device. Various routing protocols exist for determining the actual route on which a message will be sent.

The sites in a distributed network can be connected physically in a number of ways. We list the most common ones below:

Fully Connected Networks Each site is directly linked with all other sites in the system. The cost of this configuration is high since a direct communication line must be present between all the sites. Messages however, can be sent fast; only one link needs to be used. Reliability of such systems is also high since many links must fail for the system to become partitioned.
Partially Connected Networks Direct links exist between some, but not all pairs of sites. The cost of configuration is lower than that of the above scheme. However, a message from one site to another may have to be sent through several intermediate sites, resulting in slower communication.
Hierarchical Networks The sites are organized as a tree. Each site has a unique parent and possibly some children. The parent and the child communicate directly and the children communicate through the parent site. In general, the failure of any node (except a leaf) in this configuration partitions the network into several disjoint subtrees. This configuration is commonly used for corporate networks.
Star Networks One of the sites in the system is connected to all other sites. None of the other sites are connected to any other. The cost of this system is linear in the number of sites. The communication cost is also low, because a message requires at most two transfers.
Ring Networks Each site is connected to exactly two other sites. The ring can either be unidirectional or bidirectional. In the former, a site can send a message to only one of its neighbors and all the sites must send the messages in the same direction. A single site failure partitions the network in this case. In a bidirectional ring, a site can send a message to both of its neighbors. However, two links must fail before the network is partitioned.
Multiaccess Bus Networks There is a single shared link (the bus) to which all sites in the network are connected. The sites may be organized as a straight line or as a ring and communicate directly with each other through the shared link. The failure of one site does not affect communication along the link. However, if the link fails, the network is partitioned completely. The Ethernet network is based on this model.
Hybrid Networks Different types of networks are connected together. That is, each site in the network can have a different configuration. Communication between sites is complicated because multiple protocols must be followed.

The actual design (and implementation) of a network is specified by the International Standards Organization (ISO). In the ISO model, the network is organized as seven layers on each site. Each layer on a site communicates with the equivalent layer on the remote site. These are briefly listed below:

Physical Layer Concerned with transmitting raw bits over a communication channel.
Data-link Layer Responsible for handling the frames, or fixed-length parts of packets, including any error detection and recovery that occurred in the physical layer.
Network Layer Responsible for providing connections and for routing packets in the communication network. Routers work at this layer.
Transport Layer Responsible for low-level access to the network and for transfer of messages between the clients.
Session Layer Responsible for implementing sessions, or process-to-process communication protocols.
Presentation Layer Responsible for resolving the differences in formats among the various sites in the network, including character conversions.
Application Layer Interacts directly with the users of the network. Deals with file transfer, remote-login protocols, email etc.

Networking in Nachos

Nachos provides the abstraction of unreliable, ordered, fixed-size message delivery to mailboxes on other directly connected machines. Messages can be dropped by the network but are never corrupted. Any thread running on Nachos can send a message to a mailbox on a directly connected machine using the PostOffice object. The PostOffice delivers packets to a specific buffer (a MailBox), based on the mailbox number stored in the packet header. Mail waits in the mailbox until a thread asks for it; if the mailbox is empty, threads can wait for mail to arrive in it. Thus, the PostOffice de-multiplexes incoming packets, delivering them to the appropriate thread. Each message contains a return address which is the id of the machine that sent the message, and a from box which is the number of the mailbox on the sending machine to which the receiving thread can send an acknowledgement.

The PostOffice class

The PostOffice class is defined in the the files post.h and post.cc in the network directory. This class defines a post-office or a collection of mailboxes. It is a synchronized object that provides two main operations: Send - send a message to a remote machine, and Receive - wait until a message is in the mailbox, then remove and return it. Incoming messages are put by the PostOffice into the appropriate mailbox, waking up any threads waiting on Receive.

The file post.h also defines three other classes - Mail, MailHeader and MailBox. Mail defines the format of an incoming/outgoing message. The constructor function of this class initializes a single mail message, by concatenating the PacketHeader (explained below) and the MailHeader. The MailHeader is part of the message header. It is prepended to the message by the PostOffice before the message is sent to the Network and contains the the destination mailbox address, the source mailbox address and the number of bytes in the message data. Thus, the packet that is delivered to the remote machine contains the actual message, the MailHeader and the PacketHeader (the Mail object). Finally, the MailBox class defines a single mailbox for messages. Incoming messages are put by the PostOffice into the appropriate mailbox, and these messages can then be retrieved by threads on that machine. A mailbox is implemented simply as a list of messages using the SynchList object (synchlist.h(cc)).

The Network Device

The emulation of a physical network connection is implemented in the files network.h and network.cc in the machine directory. The abstraction is one of ordered, unreliable, fixed-size packet delivery to other machines on the network. The class PacketHeader defines a network packet header and contains the network address of the destination and source machine, and the number of bytes in the message (excluding the PacketHeader but including the MailHeader).

The actual network device is defined by the Network class. This class simulates a network interface, using UNIX sockets to deliver packets between multiple invocations of Nachos. It contains routines to send and receive a packet from a remote machine.

The following figure summarizes the above discussion.

Want to know more about Networking?
Source code in code/network
Quiz

Last modified on Thursday, 29-May-97 17:04:06 EDT