network

Roadmap 8: Network

In this roadmap we study the following issues associated with the network:

Layering structure;

Protocols;

Interfaces and synchronization between layers.

As before, we start with threads/main.cc. When we run two nachos in two separate windows:


	nachos -N -m 0
	nachos -N -m 1

In the first nachos, my net address is 0 (implying that the other machine's net address is 1). In the second nachos, my net address is 1 (the other machine's net address is 0). Both machines run kernel::NetworkTest() (threads/kernel.cc). What are the outputs? Let's check out NetworkTest().

The machine 0/1, composes a mail "Hello there!" from mbox 1 (out mail box) to machine 1/0 mbox 0 (in mail box), then it calls post office to send the mail. After the mail is sent, it waits on mbox 0 for incoming mails. When the mail arrives, it receives the mail and prints


	Got: Hello there! : from 1/0, box 1

then it sends an acknowledgement "Got it!" from mbox 1 to machine 1/0 mbox 1 from which the mail was sent. Then it waits on mbox 1 for the acknowledgement. When it receives the acknowledgement, it prints


	Got: Got it! : from 1/0, box 1

Now, can you explain the outputs?

The layering structure is depicted as follows:


		   user
	      ----------------
		post office
	      ----------------
		 network

User (Application) Level

See kernel::NetworkTest() in threads/kernel.cc

Structure of MailHeader (defined in network/post.h):


              -------------------------------------
  MailHeader     |    to   |     from    | length  |
              -------------------------------------

Structure of PacketHeader (defined in machine/network.h):


                   -----------------------------------
  PacketHeader     |    to   |    from    |  length  |
                   -----------------------------------

The maximal length of whole mail: MaxWireSize is 64 (machine/network.h)
MaxPacketSize = MaxWireSize - sizeof(PacketHeader) (machine/network.h)
MaxMailSize = MaxPacketSize - sizeof(MailHeader) (machine/network.h)

When sending a mail (kernel::NetworkTest() in threads/kernel.cc), the user fills in part of the PacketHeader:


                to      from  length
              -----------------------
  pktHdr      |farHost|      |      |
              -----------------------

(note that the user doesn't know my hostName) and the MailHeader


                to   from  length
              --------------------
  mailHdr     | 0  |  1   | xxx  |
              --------------------

and then calls post office to send the mail (see below PostOfficeOutput::Send). The user sends three pieces, packet header, mail header, and data, to post office. A mail consists of three parts (class Mail defined in network/post.h):


		---------------------------
		| pktHdr | mailHdr | data |
		---------------------------

When receiving a mail, the user calls post office (see below PostOfficeInput::Receive) specifying mbox. The user picks up a mail when a mail is put in the mbox (a synchlist).

Post Office Level

See network/post.*

The post office has a bunch of mail boxes (MailBox in network/post.*)

Structure of a MailBox: a synchlist of Mails

Operations on a MailBox:

Put(pktHdr, mailHdr, data), construct a mail object and atomically append a mail to the synchronous list.

Get(pktHdr, mailHdr, data), remove a mail object consisting of three parts from the list and partition it into three parts.

Construction of post office.

PostOfficeInput::PostOfficeInput(int nBoxes)

in network/post.*

It is a class derived from CallBackObj.

initialize a semaphore messageAvailable. It provides the synchronization between post office and network. It is used to block the postal helper until network sends a signal when a message arrives.

set up mail boxes;

construct a network for input. This establishes establish a connection with the network by passing an interrupt handler: PostOfficeInput::CallBack(). It tells the network what to do when a message arrives (V() the semaphore messageAvailable). This function provides synchronization between network and post office.

hire a postal helper whose sole job is described by

PostOfficeInput::PostalDelivery() in network/post.*

the first thing the postal helper does is to go to sleep (blocked on the semaphore messageAvailable).

when the postal helper is woken up by the network, it calls network to put the message in a buffer.

strip off mail header, get destination mbox from mail header and deliver the message to the mail box.

PostOfficeOutput::PostOfficeOutput(double reliability)

in network/post.*

It is a class derived from CallBackObj.

initialize a synchronization variable semaphore messageSent. It provides the synchronization between post office and network. It is used to block the sender until network says ok to send the next message.

initialize a lock sendLock so that only one message can be sent to the network at any time.

construct a network for output. This establishes a connection with the network specifying reliability (default 100%) and passing an interrupt handler: PostOfficeOutput::CallBack(). It tells the network what to do when it is ok to send the next message (V() the semaphore messageSent). This function provides synchronization between network and post office.

When sending a mail, after filling in mailHdr and pktHdr.to (the destination net address), the user (application) calls

PostOfficeOutput::Send(pktHdr, mailHdr, data)

in network/post.*

fill in pktHdr.from with my hostName (the user doesn't have to know the machine net address);
fill in pktHdr.length, which is mailHdr.length plus sizeof(MailHeader);
pack mail header and data together. The post office doesn't care what's in the mail header and data;
acquire sendLock so that only one message can be sent to the network at any one time;
call network to send the mail (see network below). It is then blocked on the semaphore messageSent until (when network output interrupt occurs) the network says ok to send the next mail. This is a synchronization between post office and network.
release the lock when woken up by the the network.

Note
PostOfficeOutput::Send provides a synchronous interface between user and post office which in turn calls network to send the mail. The lock sendLock ensures only one message is sent to the network at any one time (mutual exclusion). The semaphore messageSent provides the synchronization between post office and network.


		user (application)
	         |
		 | PostOfficeOutput::Send()
		 |
		 V
	     post office
		 |
		 | Network::Send()
		 |
		 V
	      network

To receive a mail, the user calls

PostOfficeInput::Receive(box, pktHdr, mailHdr, data)

in network/post.*

The user gets a mail from the mail box (a synchlist) when there are mails available. When a message arrives, the network wakes up the postal helper to pick up the message and then to deliver the mail to the destination mail box. The network delivers two pieces, packet header and mail, to post office. The post office delivers three pieces, packet header, mail header, and data, to the user.

Note
PostOfficeInput::Receive is another synchronous interface between user and post office.

Network

Construction of network input

NetworkInput::NetworkInput(callBackObj)

in machine/network.*

The callBackObj provides the network input interrupt handler: PostOfficeInput::CallBack(), which defines the network input interrupt handler, that is, what to do when a network input interrupt occurs.

Simulation of physical link using sockets. (see below for more about sockets).

open a socket, OpenSocket is defined in lib/sysdep;
bind the socket to a file named "SOCKET_x", AssignNameToSocket is defined in lib/sysdep;
start polling the socket by scheduling the first network input interrupt. The interrupt handler is NetworkInput::CallBack(), the time interval is NetworkTime (100) defined in machine/stats.h, and interrupt type is NetworkRecvInt.

NetworkOutput::NetworkOutput(reliability, callBackObj)

in machine/network.*

arguments:

reliability

The callBackObj provides the network output interrupt handler: PostOfficeOutput::CallBack() defines the network output interrupt handler, that is, what to do when a network output interrupt occurs.

Functions provided by network:

NetworkOutput::Send(pktHdr, data)

in machine/network.*

arguments: packet header and data (including mail header and mail body, this is a layering structure)

make sure: network is not busy; sizes of hdr and pkt are ok; packet is from this machine. (note. it doesn't care about mail header and mail body in data, this is layering structure).
schedule a network output interrupt. The interrupt handler is NetworkOutput::CallBack(), the time interval (send delay) is NetworkTime (100) defined in machine/stats.h, and interrupt type is NetworkSendInt. (This provides synchronization between network and post office.)
drop packets randomly.
concatenate pktHdr and pkt data.
send packet to socket, SendToSocket is defined in lib/sysdep.

NetworkInput::Receive()

in machine/network.*

argument: a buffer for a mail (mail header and data). This function is called by post office. So the buffer is in post office. It returns a packet header.

copy the mail (mail header and data) in inbox (part of NetworkInput) into the buffer (in post office) and return the packet header.

NetworkOutput::CallBack()

in machine/network.*

update statistics
call PostOfficeOutput::CallBack() in network/post.*, to tell post office that it is ok to send the next message.

NetworkInput::CallBack()

in machine/network.*

schedule the next poll;
if nothing in buffer and there is a packet, read a packet from the socket, ReadFromSocket is defined in lib/sysdep;
partition the packet into packet header and mail (mail header and data);
make sure: this packet is to this machine; the packet size is ok;
put the mail in inbox and the packet header in inHdr;
update statistics
call PostOfficeInput::CallBack(), in network/post.*, to tell the postal helper that a packet is available.

When sending a mail, the user calls postOffice and passed three pieces: packet header, mail header, and data to postOffice. The postOffice concatenates mail header and data and completes the packet header and then calls network to send the mail. To allow only one mail is sent to the network at any time, a lock is used for mutual exclusion. Upon receiving the packet header and mail, network schedules an interrupt for the completion of sending the mail. To synchronize the postOffice and network, a semaphore is used. After network->Send is called, the thread waits on the semaphore. The network interrupt handler calls the semaphore V() to signal the thread waiting for the mail to be sent to the network. Then network puts the packet header and the data together and sends the whole packet to the socket, which simulates the physical network. Here is a big picture:


                      pktHdr                   mailHdr
               ----------------------   ----------------------
               | to | from | length |   | to | from | length |
               ----------------------   ----------------------
  user         -----------------------------------------------
               |                    data                     |
               -----------------------------------------------

               postOfficeOutput->Send

----------------------------------------------------------------

                       pktHdr
               ----------------------
               | to | from | length |
               ----------------------
               ----------------------------------------------
  postOffice   |                     mail                   |
               ----------------------------------------------

               sendLock->Acquire
               networkOutput->Send
               messageSent->P()      ^
               sendLock->Release     |
                                     |
----------------------------------------------------------------
                                     |
               interrupt->Schedule(CallBack(), ...)
  network      SendToSocket

               ----------------------------------------------
               |                   packet                   |
               ----------------------------------------------
                                     |
----------------------------------------------------------------
                                     |
                                     V
                                   socket

How does the user receive a mail? When a networkInput is constructed, it opens a socket and schedules the first interrupt to poll on the socket. The interrupt handler is NetworkInput::CallBack(), which schedules the next poll, receives a packet and partitions it into two parts and puts the packet header in inHdr and the mail in inbox, and then calls PostOfficeInput::CallBack() to wake up the postal helper. When the postal helper is woken up (in PostOfficeInput::PostalDelivery), it copies the mail from inbox in network to a buffer in post office (Network::Receive), then it checks the mail header and deliver all three pieces (packet header, mail header, data) to the destination mail box (a synchlist). As soon as a mail is appended to the mail box, the user is signaled to get the mail. VOILA!


                socket
                  ^
                  | 
----------------------------------------------------------------
              CallBack()
                  interrupt->Schedule(this, ...)
  networkInput    ReadFromSocket

                  -----------------------------------
                  | pktHdr |                        |
                  -----------------------------------
                      |                     |
                  PostOfficeInput::CallBack |
                      messageAvailable->V() |
                          |          |      |
                          V          |      V
                      ---------      |    -----------
                      | inHdr |      |    |  inBox  |
                      ---------      |    -----------
----------------------------------------------------------------
                                     |      |
              PostalDelivery()       V      |
                  messageAvailable->P()     |
                  network->Receive          |
  post office                               V
                  -----------------------------------------
                  | pktHdr | mailHdr |      data          |
                  -----------------------------------------
                                      |
                  boxes[i].Put        |
                                      V
                  -----------------------------------------
           boxes  |                 |    |                |
                  -----------------------------------------  
                                      |
----------------------------------------------------------------
               postOffice->Receive    |
                   boxes[i].Get       |
  user                                V
                  ----------    -----------   ------------
                  | pktHdr |    | mailHdr |   |   data   |
                  ----------    -----------   ------------
----------------------------------------------------------------

Socket

lib/sysdep.*

OpenSocket

arguments:

AF_UNIX         address family UNIX dimain
SOCK_DGRAM      datagram socket (bidirectional unreliable)
0               protocol, choose a proper one

AssignNameToSocket

arguments:

path name
socket id, returned by socket()

initialize structure sockaddr_un, UNIX socket address; sun_family is AF_UNIX; copy path name to sun_path.
bind the above socket address to socket id

ReadFromSocket

arguments:

sockID, my socket for reading
buffer for data to be read
size of data to be read

system call recvfrom, arguments
sockID, my socket for receiving data
buffer for data to be received
size of date to be received
flag, 0 means no flags set, see man recvfrom for flags
socket address of the source on return
size of the socket address, initialized to the size of unix socket address structure and modified on return

SendToSocket

arguments:

sockID, my socket for sending data
buffer for data to be sent
size of data to be sent
path name of the destination socket

initializes a socket address (AF_UNIX and path name)
system call sendto, arguments
sockID, my socket for sending data
buffer for data to be sent
size of data to be sent
flag, 0 means no flags set, see man sendto for flags
destination socket address (must be known)
size of the socket address

Note
here recvfrom and sendto are used, so this is a connectionless protocol for connection-oriented protocol use listen, accept, connect system calls.

A good source of information about socket is

R. Stevens, "UNIX Network Programming", 2nd ed., Volume 1, Prentice-Hall, 1997.

We also provide a short description of the (Berkeley Sockets).