Differentiate Hardware and Micro-programmed control unit

Hardware Control Unit:
-----------------------------
There are two major types of control organization: hardwired control and micro programmed control. In the hardwired organization, the control logic is implemented with gates, flip-flops, decoders, and other digital circuits. It has the advantage that it can be optimized to produce a fast mode of operation. In the micro programmed organization, the control information is stored in a control memory. The control memory is programmed to initiate the required sequence of micro operations. A hardwired control, as the name implies, re­quires changes in the wiring among the various components if the design has to be modified or changed. In the micro programmed control, any required changes or modifications can be done by updating the microprogram in control memory.

Micro Programed Control Unit:
---------------------------------------
The control memory is assumed to be a ROM, within which all control information is permanently stored. The control memory address register specifies the address of the microinstruction, and d the control data register holds the microinstruction read from memory.

The microinstruction contains a control word that specifies one or more micro-operations for the data processor. Once these operations are executed, the control must determine the next address. The location of the next microinstruc­tion may be the one next in sequence, or it may be located somewhere else in the control memory. For this reason it is necessary to use some bits of the present microinstruction to control the generation of the address of the next microinstruction. The next address may also be a function of external input conditions. While the microoperations are being executed, the next address is computed in the next address generator circuit and then transferred into the control address register to read the next microinstruction. Thus a microinstruc­tion contains bits for initiating microoperations in the data processor part and bits that determine the address sequence for the control memory.
The next address generator is sometimes called a microprogram sequencer, as it determines the address sequence that is read from control memory. The address of the next microinstruction can be specified in several ways, depending on the sequencer inputs. Typical functions of a microprogram sequencer are incrementing the control address register by one, loading into the control address register an address from control memory, transferring an external address, or loading an initial address to start the control operations.

The control data register holds the present microinstruction while the next address is computed and read from memory. The data register is some-times called a pipeline register. It allows the execution of the microoperations specified by the control word simultaneously with the generation of the next microinstruction. This configuration requires a two-phase clock, with one clock applied to the address register and the other to the data register.
The system can operate without the control data register by applying a single-phase clock to the address register. The control word and next-address information are taken directly from the control memory. It must be realized that a ROM operates as a combinational circuit, with the address value as the input and the corresponding word as the output. The content of the specified word in ROM remains in the output wires as long as its address value remains in the address register. No read signal is needed as in a random-access memory. Each clock pulse will execute the microoperations specified by the control word and also transfer a new address to the control address register. In the example that follows we assume a single-phase clock and therefore we do not use a control data register. In this way the address register is the only component in the control system that receives clock pulses. The other two components: the sequencer and the control memory are combinational circuits and do not need a clock.
The main advantage of the microprogrammed control is the fact that once the hardware configuration is established, there should be no need for further hardware or wiring changes. If we want to establish a different control sequence for the system, all we need to do is specify a different set of microin­structions for control memory. The hardware configuration should not be changed for different operations; the only thing that must be changed is the microprogram residing in control memory.

Dekker's Algorithm (Mutual Exclusion)

This is the first correct solution proposed for the two-process case. Originally developed by Dekker in a different context, it was applied to the critical section problem by Dijkstra.
CONCEPT: Both the turn variable and the status flags are combined in a careful way. The entry protocol begins as in Algorithm 3; we (the requesting process) set our flag and then check our neighbor's flag. If that flag is also set, the turn variable is used. There is no progress problem now because we know the other process is in its CS or entry protocol. If the turn is ours we wait for the flag of the other process to clear. No process will wait indefinitely with its flag set. If the turn belongs to the other process we wait, but we clear our flag before waiting to avoid blocking the other process. When the turn is given to us we reset our flag and proceed.

INITIALIZATION:

typedef char boolean;
...
shared boolean flags[n -1];
shared int turn;
...
turn = i ;
...
flags[i ] = FREE;
...
flags[j ] = FREE;
...
ENTRY PROTOCOL (for Process i ):
/* claim the resource */
flags[i ] = BUSY;

/* wait if the other process is using the resource */
while (flags[j ] == BUSY) {

/* if waiting for the resource, also wait our turn */
if (turn != i ) {

/* but release the resource while waiting */
flags[i ] = FREE;
while (turn != i ) {
}
flags[i ] = BUSY;
}

}
EXIT PROTOCOL (for Process i ):
/* pass the turn on, and release the resource */
turn = j ;
flags[i ] = FREE;

Controlled Buffer/Inverter

The controlled buffer and inverter, often called three-state buffers/inverters, each have a one-bit "control" input pin on the south side. The value at this control pin affects how the component behaves:

When the value on this pin is 1, then the component behaves just like the respective component (a buffer or a inverter (NOT gate)).
When the value is 0 or unknown (i.e., floating), then the component's output is also floating.
When the value is an error value (such as would occur when two conflicting values are being fed into the input), then the output is an error value.
Controlled buffers can be useful when you have a wire (often called a bus) whose value should match the output of one of several components. By placing a controlled buffer between each component output and the bus, you can control whether that component's output is fed onto the bus or not.

C programming: Basic Operations on Text Files

The file I/O functions and types in the C language are straightforward and easy to understand. To make use of these functions and types you have to include the stdio library. (Like we already did in most of the tutorials).

The file I/O functions in the stdio library are:

fopen – opens a text file.
fclose – closes a text file.
feof – detects end-of-file marker in a file.
fscanf – reads formatted input from a file.
fprintf – prints formatted output to a file.
fgets – reads a string from a file.
fputs – prints a string to a file.
fgetc – reads a character from a file.
fputc – prints a character to a file.
File I/O: opening a text file

The fopen library function is used to open a text file. You also have to use a specified mode when you open a file. The three most common modes used are read (r), write (w), and append (a). Take a look at an example:

‪#‎include‬<stdio.h>

int main()
{
FILE *ptr_file;
int x;

ptr_file =fopen("output.txt", "w");

if (!ptr_file)
return 1;

for (x=1; x<=10; x++)
fprintf(ptr_file,"%d\n", x);

fclose(ptr_file);

return 0;
}

So let’s take a look at the example:

ptr_file =fopen(“output”, “w”);

The fopen statement opens a file “output.txt” in the write (w) mode. If the file does not exist it will be created. But you must be careful! If the file exists, it will be destroyed and a new file is created instead. The fopen command returns a pointer to the file, which is stored in the variable ptr_file. If the file cannot be opened (for some reason) the variable ptr_file will contain NULL.

if (!ptr_file)

The if statement after de fopen, will check if the fopen was successful. If the fopen was not successful, the program will return a one. (Indicating that something has gone wrong).

for (x=1; x<=10; x++)

This for loop will count to ten, starting from one.

fprintf(ptr_file,”%d\n”, x);

The fprintf statement should look very familiar to you. It can be almost used in the same way as printf. The only new thing is that it uses the file pointer as its first parameter.

fclose(ptr_file);

The fclose statement will close the file. This command must be given, especially when you are writing files. So don’t forget it. You have to be careful that you don’t type “close” instead of “fclose”, because the close function exists. But the close function does not close the files correctly. (If there are a lot of files open but not closed properly, the program will eventually run out of file handles and/or memory space and crash.)

File I/O: reading a text file

If you want to read a file you have to open it for reading in the read (r) mode. Then the fgets library functions can be used to read the contents of the file. (It is also possible to make use of the library function fscanf. But you have to be sure that the file is perfectly formatted or fscanf will not handle it correctly). Let’s take a look at an example:

#include<stdio.h>

int main()
{
FILE *ptr_file;
char buf[1000];

ptr_file =fopen("input.txt","r");
if (!ptr_file)
return 1;

while (fgets(buf,1000, ptr_file)!=NULL)
printf("%s",buf);

fclose(ptr_file);
return 0;
}

Note:The printf statement does not have the new-line (\n) in the format string. This is not necessary because the library function fgets adds the \n to the end of each line it reads.

A file “input.txt” is opened for reading using the function fopen en the mode read (r). The library function fgets will read each line (with a maximum of 1000 characters per line.) If the end-of-file (EOF) is reached the fgets function will return a NULL value. Each line will be printed on stdout (normally your screen) until the EOF is reached. The file is then closed and the program will end.

Boyce Codd's 12 rules on DBMS

Dr Edgar F. Codd, after his extensive research on the Relational Model of database systems, came up with twelve rules of his own, which according to him, a database must obey in order to be regarded as a true relational database.

These rules can be applied on any database system that manages stored data using only its relational capabilities. This is a foundation rule, which acts as a base for all the other rules.

Rule 1: Information Rule
The data stored in a database, may it be user data or metadata, must be a value of some table cell. Everything in a database must be stored in a table format.

Rule 2: Guaranteed Access Rule
Every single data element (value) is guaranteed to be accessible logically with a combination of table-name, primary-key (row value), and attribute-name (column value). No other means, such as pointers, can be used to access data.

Rule 3: Systematic Treatment of NULL Values
The NULL values in a database must be given a systematic and uniform treatment. This is a very important rule because a NULL can be interpreted as one the following − data is missing, data is not known, or data is not applicable.

Rule 4: Active Online Catalog
The structure description of the entire database must be stored in an online catalog, known as data dictionary, which can be accessed by authorized users. Users can use the same query language to access the catalog which they use to access the database itself.

Rule 5: Comprehensive Data Sub-Language Rule
A database can only be accessed using a language having linear syntax that supports data definition, data manipulation, and transaction management operations. This language can be used directly or by means of some application. If the database allows access to data without any help of this language, then it is considered as a violation.

Rule 6: View Updating Rule
All the views of a database, which can theoretically be updated, must also be updatable by the system.

Rule 7: High-Level Insert, Update, and Delete Rule
A database must support high-level insertion, updation, and deletion. This must not be limited to a single row, that is, it must also support union, intersection and minus operations to yield sets of data records.

Rule 8: Physical Data Independence
The data stored in a database must be independent of the applications that access the database. Any change in the physical structure of a database must not have any impact on how the data is being accessed by external applications.

Rule 9: Logical Data Independence
The logical data in a database must be independent of its user’s view (application). Any change in logical data must not affect the applications using it. For example, if two tables are merged or one is split into two different tables, there should be no impact or change on the user application. This is one of the most difficult rule to apply.

Rule 10: Integrity Independence
A database must be independent of the application that uses it. All its integrity constraints can be independently modified without the need of any change in the application. This rule makes a database independent of the front-end application and its interface.

Rule 11: Distribution Independence
The end-user must not be able to see that the data is distributed over various locations. Users should always get the impression that the data is located at one site only. This rule has been regarded as the foundation of distributed database systems.

Rule 12: Non-Subversion Rule
If a system has an interface that provides access to low-level records, then the interface must not be able to subvert the system and bypass security and integrity constraints.

C program to copy one file to another file

‪#‎include‬<stdio.h>
#include<process.h>

void main() {
FILE *fp1, *fp2;
char a;
clrscr();

fp1 = fopen("test.txt", "r");
if (fp1 == NULL) {
puts("cannot open this file");
exit(1);
}

fp2 = fopen("test1.txt", "w");
if (fp2 == NULL) {
puts("Not able to open this file");
fclose(fp1);
exit(1);
}

do {
a = fgetc(fp1);
fputc(a, fp2);
} while (a != EOF);

fcloseall();
getch();
}

Program of reversing a string using stack

‪#‎include‬<stdio.h>
#include<string.h>
#include<stdlib.h>
‪#‎define‬ MAX 20
int top = -1;
char stack[MAX];
char pop();
void push(char);
main()
{
char str[20];
unsigned int i;
printf(“Enter the string : ” );
gets(str);
/*Push characters of the string str on the stack */
for(i=0;i<strlen(str);i++)
push(str[i]);
/*Pop characters from the stack and store in string str */
for(i=0;i<strlen(str);i++)
{
str[i]=pop();
printf(“Reversed string is : “);
puts(str);
}/*End of main()*/
void push(char item)
{
if(top == (MAX-1))
{
printf(“Stack Overflow\n”);
return;
}
stack[++top] =item;
}/*End of push()*/
char pop()
{
if(top == -1)
{
printf(“Stack Underflow\n”);
exit(1);
}
return stack[top–];
}/*End of pop()*/

Work breakdown structure (WBS)

A work breakdown structure (WBS), in project management and systems engineering, is a deliverable-oriented decomposition of a project into smaller components. A work breakdown structure is a key project deliverable that organizes the team's work into manageable sections. The Project Management Body of Knowledge (PMBOK 5) defines the work breakdown structure as a "A hierarchical decomposition of the total scope of work to be carried out by the project team to accomplish the project objectives and create the required deliverables."

A work breakdown structure element may be a product, data, service, or any combination thereof. A WBS also provides the necessary framework for detailed cost estimating and control along with providing guidance for schedule development and control.

Who calls the main() function in C/C++?

a. You need either a definition or a prototype in order to properly call a function, but "main" must never be called from any other function, so it must not be declared.
b. Because the C standard says so. Operating systems pass the return value to the calling program (usually the shell). Some compilers will accept void main, but this is a non-standard extension (it usually means "always return zero to the OS")
c. By convention, a non-zero return value signals that an error occurred. Shell scripts and other programs can use this to find out if your program terminated successfully.

What are the roles of C/C++ runtime environment during the life cycle of C/C++ program?

Runtime environment is critical for your program. there is always a default environment whenever you run a program. which collects, links and uses static and dynamic libraries. If you set any environment variable in shell, you can change the path and give your own path linking and executing the latest libraries in the program. You can check out LIBPATH, which can give you an idea , how program links to latest library in the system and how it gets the other environment essentials through Shell defined variables.

Multiplication of two polynomials using Linked List (By C)

‪#‎include‬<stdio.h>
#include<stdlib.h>

typedef struct node
{
int coeff;
int exp;
struct node* next;
} node;

void get_data(node* head)
{
int ch;
do {
printf("\nEnter the coeff : ");
scanf("%d",&(head->coeff));
printf("\nEnter the exponent : ");
scanf("%d",&(head->exp));
head->next = NULL;
printf("\nWant to enter more data? (0/1) :");
scanf("%d",&ch);
if(ch) {
head->next = (node*)malloc(sizeof(node));
head = head->next;
head->next = NULL;
}
} while(ch);
}

void display(node* head)
{
while(head->next != NULL)
{
printf("(%d.x^%d)+",head->coeff,head->exp);
head = head->next;
}
printf("(%d.x^%d)\n",head->coeff, head->exp);
}

node* add(node* result, node* poly1, node* poly2)
{
node* temp,*temp1;
temp = result;
while(poly1 && poly2)
{
if(poly1->exp > poly2->exp)
{
result->exp = poly1->exp;
result->coeff = poly1->coeff;
poly1=poly1->next;
}
else if(poly1->exp < poly2->exp)
{
result->exp = poly2->exp;
result->coeff = poly2->coeff;
poly2=poly2->next;
}
else
{
result->exp = poly1->exp;
result->coeff = poly1->coeff + poly2->coeff;
poly1 = poly1->next;
poly2 = poly2->next;
}
if(poly1 || poly2)
{
result->next = (node*)malloc(sizeof(node));
result = result->next;
result->next = NULL;
}
}

while(poly1 || poly2)
{

if(poly1)
{
result->coeff = poly1->coeff;
result->exp = poly1->exp;
poly1 = poly1->next;
}

if(poly2)
{
result->coeff = poly2->coeff;
result->exp = poly2->exp;
poly2 = poly2->next;
}
if(~(poly1 || poly2))
{
break;
}
result->next = (node*)malloc(sizeof(node));
result = result->next;
result->next = NULL;
}
while(result)
{
temp1 = result;
result = result->next;
free(temp1);
}
return temp;
}

node* multiply(node* result, node* poly1, node* poly2)
{
node* ptr,*new,*result1;
node* temp = poly2;
node* temp1 = (node*)malloc(sizeof(node));
ptr = (node*)malloc(sizeof(node));
new = ptr ;
result1 = result;
ptr->next = NULL;
while(poly1 != NULL)
{
while(poly2 != NULL)
{
ptr->coeff = (poly1->coeff) * (poly2->coeff);
ptr->exp = poly1->exp + poly2->exp;
poly2 = poly2->next;

if(poly2)
{
ptr->next = (node*)malloc(sizeof(node));
ptr = ptr->next;
ptr->next = NULL;
}
}
poly2 = temp;

result = add(temp1,new,result1);

result1 = temp1;

poly1 = poly1->next;
ptr = new;
}
while(ptr)
{
new=ptr;
ptr=ptr->next;
free(new);
}
return(result);

}

int main()
{
node* poly1 = (node*)malloc(sizeof(node));
node* result = (node*)malloc(sizeof(node));
node* poly2 = (node*)malloc(sizeof(node));
node* temp;
result->next = NULL;
result->coeff = 0;
result->exp = 0;

get_data(poly1);
display(poly1);
get_data(poly2);
display(poly2);

//printf("\nThe sum is : ");
//add(result,poly1,poly2);
//display(result);

printf("\nThe product is : ");
result = multiply(result, poly1, poly2);
display(result);

while(result)
{
temp = result;
result = result->next;
free(temp);
}
while(poly1)
{
temp = poly1;
poly1 = poly1->next;
free(temp);
}
while(poly2)
{
temp = poly2;
poly2 = poly2->next;
free(temp);
}
return 0;
}

Explain user account control (UAC)

User Account Control (UAC) is a feature in Windows that can help you stay in control of your computer by informing you when a program makes a change that requires administrator-level permission. UAC works by adjusting the permission level of your user account. If you’re doing tasks that can be done as a standard user, such as reading e‑mail, listening to music, or creating documents, you have the permissions of a standard user—even if you’re logged on as an administrator.

When changes are going to be made to your computer that require administrator-level permission, UAC notifies you. If you are an administrator, you can click Yes to continue. If you are not an administrator, someone with an administrator account on the computer will have to enter their password for you to continue. If you give permission, you are temporarily given the rights of an administrator to complete the task and then your permissions are returned back to that of a standard user. This makes it so that even if you're using an administrator account, changes cannot be made to your computer without you knowing about it, which can help prevent malicious software (malware) and spyware from being installed on or making changes to your computer.

Advantage and Disadvantage of singly Linked list and Doubly Linked list:

SINGLY LINKED LIST:

===================
*ADVANTAGE :-
1) Insertions and Deletions can be done easily.
2) It does not need movement of elements for insertion and deletion.
3) It space is not wasted as we can get space according to our requirements.
4) Its size is not fixed.
5) It can be extended or reduced according to requirements.
6) Elements may or may not be stored in consecutive memory available,even then we can store the data in computer.
7) It is less expensive.

*DISADVANTAGE :-
1) It requires more space as pointers are also stored with information.
2) Different amount of time is required to access each element.
3) If we have to go to a particular element then we have to go through all those elements that come before that element.
4) we can not traverse it from last & only from the beginning.
5) It is not easy to sort the elements stored in the linear linked list.

DOUBLY LINKED LIST:
=====================

*ADVANTAGE :-

1) We can traverse in both direction i.e from starting to end & as well as from end to starting.
2) It is easy to reverse the linked list.
3) If we are at a node,the we can go at any node.But in linked list,it is not possible to reach the previous node.

*DISADVANTAGE :-

1) It requires more space per space per node because extra field is required for pointer to previous node.
20 Insertion and Deletion take more time than linear linked list because more pointer operations are required than linear linked list.

What is disadvantage of using linked lists over arrays?

--The main disadvantage of linked list over array is access time to individual elements.Array is random-access,which means it takes o(1) to access any element in the array.Linked list takes O(n) for access to an element in the list in the worst case.

--Another advantage of arrays in access time is special locality in memory.Arrays are defined as contiguous blocks of memory, and so any element will be physically near its neighbours.This greatly benifits from modern CPU caching methods.

--In linked list , Random access is not allowed. We have to access elements sequentially starting from the first node. So we cannot do binary search with linked lists.

--Extra memory space for a pointer is required with each element of the list.Hence Linked lists wastes memory in terms of extra reference points.

Differences between B.Sc. in Computer Sci. & BCA

IT (Information Technology) is a growing field in India, and is looked upon as one of the industries to provide jobs. A science student interested in joining the IT bandwagon is usually confused about the many courses on offer at the undergraduate level and might end up joining a course which might not be as beneficial as some other course.

For example, confusion may arise when choosing between BCA(Bachelor of Computer Applications) and B.SC (Computer Science). We have listed some of the difference in these courses to help you reach a decision.

B.Sc (Computer Science)

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

The B.Sc (CS) course mainly focuses on the mathematical and theoretical foundations of computing, rather than teaching specific technologies that may quickly become outdated. The course prepares you for higher education.

Eligibility: 10+ 2 Pass in Science stream with Physics, Chemistry & Maths.

Education after B.Sc: M.Sc, (provided that its recognised by the UGC or AIU) followed by an M.Tech, or an MCA, that’s what’s open to you after your B.Sc. M.Tech may be available to you after you sit of the GATE conducted by the IITs or the entrance examinations of individual universities offering the course.

Jobs after B.Sc: Students will usually go immediately for higher education after B.Sc, but jobs do exist; they can take on positions as software professionals (testers and developers) in IT companies. and it is suitable for those who are willing to teach.

BCA

----------

Another thing to consider when comparing BCA & B.Sc Computer Science is that BCA is more professionally oriented; it prepares you for post-graduate or research work and also creates professional manpower for problem solving through application of computer science at the interface of business and technology. It covers:

computer science,
programming,
database design,
software engineering,
networks
and information systems
Eligibility Criteria: 50+% at HSC with a Math background + an entrance test.

Education after BCA: MCA and M.Tech are usually the popular options.

Jobs after BCA: Software related jobs in testing and developing are common options made available to you.

Now some more from my point of view,

One more difference is B.Sc. is cheaper than BCA but job options are still better for BCA but scenarios are changing rapidly as leading Software firms like WIPRO, TCS, etc. are hiring huge number of students fromB.Sc.level also now a days.

What does Medium access sub layer

Some networks have a single channel that is used for all communication. In these networks, the key design issue is the allocation of this channel among the competing stations wishing to use it. FDM and TDM are simple, efficient allocation schemes when the number of stations is small and fixed and the traffic is continuous. Both are widely used under these circumstances, for example, for dividing up the bandwidth on telephone trunks. However, when the number of stations is large and variable or the traffic is fairly bursty—the common case in computer networks—FDM and TDM are poor choices.

Numerous dynamic channel allocation algorithms have been devised. The ALOHA protocol, with and without slotting, is used in many derivatives in real systems, for example, cable modems and RFID. As an improvement when the state of the channel can be sensed, stations can avoid starting a transmission while another station is transmitting. This technique, carrier sensing, has led to a variety of CSMA protocols for LANs and MANs. It is the basis for classic Ethernet and 802.11 networks.

A class of protocols that eliminates contention altogether, or at least reduces it considerably, is well known. The bitmap protocol, topologies such as rings, and the binary countdown protocol completely eliminate contention. The tree walk protocol reduces it by dynamically dividing the stations into two disjoint groups of different sizes and allowing contention only within one group; ideally that group is chosen so that only one station is ready to send when it is permitted to do so.

Wireless LANs have the added problems that it is difficult to sense colliding transmissions, and that the coverage regions of stations may differ. In the dominant wireless LAN, IEEE 802.11, stations use CSMA/CA to mitigate the first problem by leaving small gaps to avoid collisions. The stations can also use the RTS/CTS protocol to combat hidden terminals that arise because of the second problem. IEEE 802.11 is commonly used to connect laptops and other devices to wireless access points, but it can also be used between devices. Any of several physical layers can be used, including multichannel FDM with and without multiple antennas, and spread spectrum.

Like 802.11, RFID readers and tags use a random access protocol to communicate identifiers. Other wireless PANs and MANs have different designs. The Bluetooth system connects headsets and many kinds of peripherals to computers without wires. IEEE 802.16 provides a wide area wireless Internet data service for stationary and mobile computers. Both of these networks use a centralized, connection-oriented design in which the Bluetooth master and the WiMAX base station decide when each station may send or receive data. For 802.16, this design supports different quality of service for real-time traffic like telephone calls and interactive traffic like Web browsing. For Bluetooth, placing the complexity in the master leads to inexpensive slave devices.

Like 802.11, RFID readers and tags use a random access protocol to communicate identifiers. Other wireless PANs and MANs have different designs. The Bluetooth system connects headsets and many kinds of peripherals to computers without wires. IEEE 802.16 provides a wide area wireless Internet data service for stationary and mobile computers. Both of these networks use a centralized, connection-oriented design in which the Bluetooth master and the WiMAX base station decide when each station may send or receive data. For 802.16, this design supports different quality of service for real-time traffic like telephone calls and interactive traffic like Web browsing. For Bluetooth, placing the complexity in the master leads to inexpensive slave devices.

With buildings full of LANs, a way is needed to interconnect them all. Plugand-play bridges are used for this purpose. The bridges are built with a backward learning algorithm and a spanning tree algorithm. Since this functionality is built into modern switches, the terms ‘‘bridge’’ and ‘‘switch’’ are used interchangeably. To help with the management of bridged LANs, VLANs let the physical topology be divided into different logical topologies. The VLAN standard, IEEE 802.1Q, introduces a new format for Ethernet frames.

EPC Gen 2 Tag Identification Layer

To inventory the nearby tags, the reader needs to receive a message from each tag that gives the identifier for the tag. This situation is a multiple access problem for which the number of tags is unknown in the general case. The reader might broadcast a query to ask all tags to send their identifiers. However, tags that replied right away would then collide in much the same way as stations on a classic Ethernet.

We have seen many ways of tackling the multiple access problem in this chapter. The closest protocol for the current situation, in which the tags cannot hear each others’ transmissions, is slotted ALOHA, one of the earliest protocols we studied. This protocol is adapted for use in Gen 2 RFID.

The sequence of messages used to identify a tag is shown in figure. In the first slot (slot 0), the reader sends a Query message to start the process. Each QRepeat message advances to the next slot. The reader also tells the tags the range of slots over which to randomize transmissions. Using a range is necessary because the reader synchronizes tags when it starts the process; unlike stations on an Ethernet, tags do not wake up with a message at a time of their choosing.

Example message exchange to identify a tag.

Tags pick a random slot in which to reply. In figure, the tag replies in slot 2. However, tags do not send their identifiers when they first reply. Instead, a tag sends a short 16-bit random number in an RN16 message. If there is no collision, the reader receives this message and sends an ACK message of its own. At this stage, the tag has acquired the slot and sends its EPC identifier.

The reason for this exchange is that EPC identifiers are long, so collisions on these messages would be expensive. Instead, a short exchange is used to test whether the tag can safely use the slot to send its identifier. Once its identifier has been successfully transmitted, the tag temporarily stops responding to new Query messages so that all the remaining tags can be identified.

A key problem is for the reader to adjust the number of slots to avoid collisions, but without using so many slots that performance suffers. This adjustment is analogous to binary exponential backoff in Ethernet. If the reader sees too many slots with no responses or too many slots with collisions, it can send a QAdjust message to decrease or increase the range of slots over which the tags are responding.

The RFID reader can perform other operations on the tags. For example, it can select a subset of tags before running an inventory, allowing it to collect responses from, say, tagged jeans but not tagged shirts. The reader can also write data to tags as they are identified. This feature could be used to record the point of sale or other relevant information.

EPC Gen 2 Physical Layer

The physical layer defines how bits are sent between the RFID reader and tags. Much of it uses methods for sending wireless signals that we have seen previously. In the U.S., transmissions are sent in the unlicensed 902–928 MHz ISM band. This band falls in the UHF (Ultra High Frequency) range, so the tags are referred to as UHF RFID tags. The reader performs frequency hopping at least every 400 msec to spread its signal across the channel, to limit interference and satisfy regulatory requirements. The reader and tags use forms of ASK (Amplitude Shift Keying) modulation to encode bits. They take turns to send bits, so the link is half duplex.

There are two main differences from other physical layers that we have studied. The first is that the reader is always transmitting a signal, regardless of whether it is the reader or tag that is communicating. Naturally, the reader transmits a signal to send bits to tags. For the tags to send bits to the reader, the reader transmits a fixed carrier signal that carries no bits. The tags harvest this signal to get the power they need to run; otherwise, a tag would not be able to transmit in the first place. To send data, a tag changes whether it is reflecting the signal from the reader, like a radar signal bouncing off a target, or absorbing it.

This method is called backscatter. It differs from all the other wireless situations we have seen so far, in which the sender and receiver never both transmit at the same time. Backscatter is a low-energy way for the tag to create a weak signal of its own that shows up at the reader. For the reader to decode the incoming signal, it must filter out the outgoing signal that it is transmitting. Because the tag signal is weak, tags can only send bits to the reader at a low rate, and tags cannot receive or even sense transmissions from other tags.

The second difference is that very simple forms of modulation are used so that they can be implemented on a tag that runs on very little power and costs only a few cents to make. To send data to the tags, the reader uses two amplitude levels. Bits are determined to be either a 0 or a 1, depending on how long the reader waits before a low-power period. The tag measures the time between low-power periods and compares this time to a reference measured during a preamble. As shown in figure, 1s are longer than 0s.

Tag responses consist of the tag alternating its backscatter state at fixed intervals to create a series of pulses in the signal. Anywhere from one to eight pulse periods can be used to encode each 0 or 1, depending on the need for reliability. 1s have fewer transitions than 0s, as is shown with an example of two-pulse period coding in figure.

Reader and tag backscatter signals.

EPC Gen 2 Architecture

The architecture of an EPC Gen 2 RFID network is shown in figure. It has two key components: tags and readers. RFID tags are small, inexpensive devices that have a unique 96-bit EPC identifier and a small amount of memory that can be read and written by the RFID reader. The memory might be used to record the location history of an item, for example, as it moves through the supply chain.

Often, the tags look like stickers that can be placed on, for example, pairs of jeans on the shelves in a store. Most of the sticker is taken up by an antenna that is printed onto it. A tiny dot in the middle is the RFID integrated circuit. Alternatively, the RFID tags can be integrated into an object, such as a driver’s license. In both cases, the tags have no battery and they must gather power from the radio transmissions of a nearby RFID reader to run. This kind of tag is called a ‘‘Class 1’’ tag to distinguish it from more capable tags that have batteries.

RFID architecture

The readers are the intelligence in the system, analogous to base stations and access points in cellular and WiFi networks. Readers are much more powerful than tags. They have their own power sources, often have multiple antennas, and are in charge of when tags send and receive messages. As there will commonly be multiple tags within the reading range, the readers must solve the multiple access problem. There may be multiple readers that can contend with each other in the same area, too.

The main job of the reader is to inventory the tags in the neighborhood, that is, to discover the identifiers of the nearby tags. The inventory is accomplished with the physical layer protocol and the tag-identification protocol that are outlined in the following sections.

Comparison of 802.16 with 802.11 and 3G

At this point you may be thinking: why devise a new standard? Why not just use 802.11 or 3G? In fact, WiMAX combines aspects of both 802.11 and 3G, making it more like a 4G technology.

Like 802.11, WiMAX is all about wirelessly connecting devices to the Internet at megabit/sec speeds, instead of using cable or DSL. The devices may be mobile, or at least portable. WiMAX did not start by adding low-rate data on the side of voice-like cellular networks; 802.16 was designed to carry IP packets over the air and to connect to an IP-based wired network with a minimum of fuss. The packets may carry peer-to-peer traffic, VoIP calls, or streaming media to support a range of applications. Also like 802.11, it is based on OFDM technology to ensure good performance in spite of wireless signal degradations such as multipath fading, and on MIMO technology to achieve high levels of throughput.

However, WiMAX is more like 3G (and thus unlike 802.11) in several key respects. The key technical problem is to achieve high capacity by the efficient use of spectrum, so that a large number of subscribers in a coverage area can all get high throughput. The typical distances are at least 10 times larger than for an 802.11 network. Consequently, WiMAX base stations are more powerful than 802.11 Access Points (APs). To handle weaker signals over larger distances, the base station uses more power and better antennas, and it performs more processing to handle errors. To maximize throughput, transmissions are carefully scheduled by the base station for each particular subscriber; spectrum use is not left to chance with CSMA/CA, which may waste capacity with collisions.

Licensed spectrum is the expected case for WiMAX, typically around 2.5 GHz in the U.S. The whole system is substantially more optimized than 802.11. This complexity is worth it, considering the large amount of money involved for licensed spectrum. Unlike 802.11, the result is a managed and reliable service with good support for quality of service.

With all of these features, 802.16 most closely resembles the 4G cellular networks that are now being standardized under the name LTE (Long Term Evolution). While 3G cellular networks are based on CDMA and support voice and data, 4G cellular networks will be based on OFDM with MIMO, and they will target data, with voice as just one application. It looks like WiMAX and 4G are on a collision course in terms of technology and applications. Perhaps this convergence is unsurprising, given that the Internet is the killer application and OFDM and MIMO are the best-known technologies for efficiently using the spectrum.

Access Points Services/802.11 standard Services

The 802.11 standard defines the services that the clients, the access points, and the network connecting them must be a conformant wireless LAN. These services cluster into several groups.

The association service is used by mobile stations to connect themselves to APs. Typically, it is used just after a station moves within radio range of the AP. Upon arrival, the station learns the identity and capabilities of the AP, either from beacon frames or by directly asking the AP. The capabilities include the data rates supported, security arrangements, power-saving capabilities, quality of service support, and more. The station sends a request to associate with the AP. The AP may accept or reject the request.

Reassociation lets a station change its preferred AP. This facility is useful for mobile stations moving from one AP to another AP in the same extended 802.11 LAN, like a handover in the cellular network. If it is used correctly, no data will be lost as a consequence of the handover. (But 802.11, like Ethernet, is just a best-effort service.) Either the station or the AP may also disassociate, breaking their relationship. A station should use this service before shutting down or leaving the network. The AP may use it before going down for maintenance.

Stations must also authenticate before they can send frames via the AP, but authentication is handled in different ways depending on the choice of security scheme. If the 802.11 network is ‘‘open,’’ anyone is allowed to use it. Otherwise, credentials are needed to authenticate. The recommended scheme, called WPA2 (WiFi Protected Access 2), implements security as defined in the 802.11i standard. (Plain WPA is an interim scheme that implements a subset of 802.11i. We will skip it and go straight to the complete scheme.) With WPA2, the AP can talk to an authentication server that has a username and password database to determine if the station is allowed to access the network. Alternatively a pre-shared key, which is a fancy name for a network password, may be configured. Several frames are exchanged between the station and the AP with a challenge and response that lets the station prove it has the right credentials. This exchange happens after association.

The scheme that was used before WPA is called WEP (Wired Equivalent Privacy). For this scheme, authentication with a preshared key happens before association. However, its use is discouraged because of design flaws that make WEP easy to compromise. The first practical demonstration that WEP was broken came when Adam Stubblefield was a summer intern at AT&T (Stubblefield et al., 2002). He was able to code up and test an attack in one week, much of which was spent getting permission from management to buy the WiFi cards needed for experiments. Software to crack WEP passwords is now freely available.

Once frames reach the AP, the distribution service determines how to route them. If the destination is local to the AP, the frames can be sent out directly over the air. Otherwise, they will have to be forwarded over the wired network. The integration service handles any translation that is needed for a frame to be sent outside the 802.11 LAN, or to arrive from outside the 802.11 LAN. The common case here is connecting the wireless LAN to the Internet.

Data transmission is what it is all about, so 802.11 naturally provides a data delivery service. This service lets stations transmit and receive data using the protocols we described earlier in this chapter. Since 802.11 is modeled on Ethernet and transmission over Ethernet is not guaranteed to be 100% reliable, transmission over 802.11 is not guaranteed to be reliable either. Higher layers must deal with detecting and correcting errors.

Wireless is a broadcast signal. For information sent over a wireless LAN to be kept confidential, it must be encrypted. This goal is accomplished with a privacy service that manages the details of encryption and decryption. The encryption algorithm for WPA2 is based on AES (Advanced Encryption Standard), a U.S. government standard approved in 2002. The keys that are used for encryption are determined during the authentication procedure.

To handle traffic with different priorities, there is a QOS traffic scheduling service. It uses the protocols we described to give voice and video traffic preferential treatment compared to best-effort and background traffic. A companion service also provides higher-layer timer synchronization. This lets stations coordinate their actions, which may be useful for media processing.

Finally, there are two services that help stations manage their use of the spectrum. The transmit power control service gives stations the information they need to meet regulatory limits on transmit power that vary from region to region. The dynamic frequency selection service give stations the information they need to avoid transmitting on frequencies in the 5-GHz band that are being used for radar in the proximity.

With these services, 802.11 provides a rich set of functionality for connecting nearby mobile clients to the Internet. It has been a huge success, and the standard has repeatedly been amended to add more functionality. For a perspective on where the standard has been and where it is heading, see Hiertz et al. (2010).

The 802.11 Physical Layer

Each of the transmission techniques makes it possible to send a MAC frame over the air from one station to another. They differ, however, in the technology used and speeds achievable. A detailed discussion of these technologies is far beyond the scope of this book, but a few words on each one will relate the techniques to the material and will provide interested readers with the key terms to search for elsewhere for more information.

All of the 802.11 techniques use short-range radios to transmit signals in either the 2.4-GHz or the 5-GHz ISM frequency bands, both described in Sec. 2.3.3. These bands have the advantage of being unlicensed and hence freely available to any transmitter willing to meet some restrictions, such as radiated power of at most 1 W (though 50 mW is more typical for wireless LAN radios). Unfortunately, this fact is also known to the manufacturers of garage door openers, cordless phones, microwave ovens, and countless other devices, all of which compete with laptops for the same spectrum. The 2.4-GHz band tends to be more crowded than the 5-GHz band, so 5 GHz can be better for some applications even though it has shorter range due to the higher frequency.

All of the transmission methods also define multiple rates. The idea is that different rates can be used depending on the current conditions. If the wireless signal is weak, a low rate can be used. If the signal is clear, the highest rate can be used. This adjustment is called rate adaptation. Since the rates vary by a factor of 10 or more, good rate adaptation is important for good performance. Of course, since it is not needed for interoperability, the standards do not say how rate adaptation should be done.

The first transmission method we shall look at is 802.11b. It is a spread-spectrum method that supports rates of 1, 2, 5.5, and 11 Mbps, though in practice the operating rate is nearly always 11 Mbps. It is similar to the CDMA system we examined, except that there is only one spreading code that is shared by all users. Spreading is used to satisfy the FCC requirement that power be spread over the ISM band. The spreading sequence used by 201.11b is a Barker sequence. It has the property that its autocorrelation is low except when the sequences are aligned. This property allows a receiver to lock onto the start of a transmission. To send at a rate of 1 Mbps, the Barker sequence is used with BPSK modulation to send 1 bit per 11 chips. The chips are transmitted at a rate of 11 Mchips/sec. To send at 2 Mbps, it is used with QPSK modulation to send 2 bits per 11 chips. The higher rates are different. These rates use a technique called CCK (Complementary Code Keying) to construct codes instead of the Barker sequence. The 5.5-Mbps rate sends 4 bits in every 8-chip code, and the 11-Mbps rate sends 8 bits in every 8-chip code.

Next we come to 802.11a, which supports rates up to 54 Mbps in the 5-GHz ISM band. You might have expected that 802.11a to come before 802.11b, but that was not the case. Although the 802.11a group was set up first, the 802.11b standard was approved first and its product got to market well ahead of the 802.11a products, partly because of the difficulty of operating in the higher 5-GHz band.

The 802.11a method is based on OFDM (Orthogonal Frequency Division Multiplexing) because OFDM uses the spectrum efficiently and resists wireless signal degradations such as multipath. Bits are sent over 52 subcarriers in parallel, 48 carrying data and 4 used for synchronization. Each symbol lasts 4μs and sends 1, 2, 4, or 6 bits. The bits are coded for error correction with a binary convolutional code first, so only 1/2, 2/3, or 3/4 of the bits are not redundant. With different combinations, 802.11a can run at eight different rates, ranging from 6 to 54 Mbps. These rates are significantly faster than 802.11b rates, and there is less interference in the 5-GHz band. However, 802.11b has a range that is about seven times greater than that of 802.11a, which is more important in many situations.

Even with the greater range, the 802.11b people had no intention of letting this upstart win the speed championship. Fortunately, in May 2002, the FCC dropped its long-standing rule requiring all wireless communications equipment operating in the ISM bands in the U.S. to use spread spectrum, so it got to work on 802.11g, which was approved by IEEE in 2003. It copies the OFDM modulation methods of 802.11a but operates in the narrow 2.4-GHz ISM band along with 802.11b. It offers the same rates as 802.11a (6 to 54 Mbps) plus of course compatibility with any 802.11b devices that happen to be nearby. All of these different choices can be confusing for customers, so it is common for products to support 802.11a/b/g in a single NIC.

Not content to stop there, the IEEE committee began work on a high-throughput physical layer called 802.11n. It was ratified in 2009. The goal for 802.11n was throughput of at least 100 Mbps after all the wireless overheads were removed. This goal called for a raw speed increase of at least a factor of four. To make it happen, the committee doubled the channels from 20 MHz to 40 MHz and reduced framing overheads by allowing a group of frames to be sent together. More significantly, however, 802.11n uses up to four antennas to transmit up to four streams of information at the same time. The signals of the streams interfere at the receiver, but they can be separated using MIMO (Multiple Input Multiple Output) communications techniques. The use of multiple antennas gives a large speed boost, or better range and reliability instead. MIMO, like OFDM, is one of those clever communications ideas that is changing wireless designs and which we are all likely to hear a lot about in the future. For a brief introduction to multiple antennas in 802.11 see Halperin et al. (2010).

Retrospective on Ethernet

Ethernet has been around for over 30 years and has no serious competitors in sight, so it is likely to be around for many years to come. Few CPU architectures, operating systems, or programming languages have been king of the mountain for three decades going on strong. Clearly, Ethernet did something right. What?

Probably the main reason for its longevity is that Ethernet is simple and flexible. In practice, simple translates into reliable, cheap, and easy to maintain. Once the hub and switch architecture was adopted, failures became extremely rare. People hesitate to replace something that works perfectly all the time, especially when they know that an awful lot of things in the computer industry work very poorly, so that many so-called ‘‘upgrades’’ are worse than what they replaced.

Simple also translates into cheap. Twisted-pair wiring is relatively inexpensive as are the hardware components. They may start out expensive when there is a transition, for example, new gigabit Ethernet NICs or switches, but they are merely additions to a well established network (not a replacement of it) and the prices fall quickly as the sales volume picks up.

Ethernet is easy to maintain. There is no software to install (other than the drivers) and not much in the way of configuration tables to manage (and get wrong). Also, adding new hosts is as simple as just plugging them in.

Another point is that Ethernet interworks easily with TCP/IP, which has become dominant. IP is a connectionless protocol, so it fits perfectly with Ethernet, which is also connectionless. IP fits much less well with connection-oriented alternatives such as ATM. This mismatch definitely hurt ATM’s chances.

Lastly, and perhaps most importantly, Ethernet has been able to evolve in certain crucial ways. Speeds have gone up by several orders of magnitude and hubs and switches have been introduced, but these changes have not required changing the software and have often allowed the existing cabling to be reused for a time. When a network salesman shows up at a large installation and says ‘‘I have this fantastic new network for you. All you have to do is throw out all your hardware and rewrite all your software,’’ he has a problem.

Many alternative technologies that you have probably not even heard of were faster than Ethernet when they were introduced. As well as ATM, this list includes FDDI (Fiber Distributed Data Interface) and Fibre Channel,† two ringbased optical LANs. Both were incompatible with Ethernet. Neither one made it. They were too complicated, which led to complex chips and high prices. The lesson that should have been learned here was KISS (Keep It Simple, Stupid). Eventually, Ethernet caught up with them in terms of speed, often by borrowing some of their technology, for example, the 4B/5B coding from FDDI and the 8B/10B coding from Fibre Channel. Then they had no advantages left and quietly died off or fell into specialized roles.

It looks like Ethernet will continue to expand in its applications for some time. 10-gigabit Ethernet has freed it from the distance constraints of CSMA/CD. Much effort is being put into carrier-grade Ethernet to let network providers offer Ethernet-based services to their customers for metropolitan and wide area networks (Fouli and Maler, 2009). This application carries Ethernet frames long distances over fiber and calls for better management features to help operators offer reliable, high-quality services. Very high speed networks are also finding uses in backplanes connecting components in large routers or servers. Both of these uses are in addition to that of sending frames between computers in offices.

What does data link layer

The task of the data link layer is to convert the raw bit stream offered by the physical layer into a stream of frames for use by the network layer. The link layer can present this stream with varying levels of reliability, ranging from connectionless, unacknowledged service to reliable, connection-oriented service.

Various framing methods are used, including byte count, byte stuffing, and bit stuffing. Data link protocols can provide error control to detect or correct damaged frames and to retransmit lost frames. To prevent a fast sender from overrunning a slow receiver, the data link protocol can also provide flow control. The sliding window mechanism is widely used to integrate error control and flow control in a simple way. When the window size is 1 packet, the protocol is stop-and-wait.

Codes for error correction and detection add redundant information to messages by using a variety of mathematical techniques. Convolutional codes and Reed-Solomon codes are widely deployed for error correction, with low-density parity check codes increasing in popularity. The codes for error detection that are used in practice include cyclic redundancy checks and checksums. All these codes can be applied at the link layer, as well as at the physical layer and higher layers.

We examined a series of protocols that provide a reliable link layer using acknowledgements and retransmissions, or ARQ (Automatic Repeat reQuest), under more realistic assumptions. Starting from an error-free environment in which the receiver can handle any frame sent to it, we introduced flow control, followed by error control with sequence numbers and the stop-and-wait algorithm. Then we used the sliding window algorithm to allow bidirectional communication and introduce the concept of piggybacking. The last two protocols pipeline the transmission of multiple frames to prevent the sender from blocking on a link with a long propagation delay. The receiver can either discard all frames other than the next one in sequence, or buffer out-of-order frames and send negative acknowledgements for greater bandwidth efficiency. The former strategy is a go-back-n protocol, and the latter strategy is a selective repeat protocol.

The Internet uses PPP as the main data link protocol over point-to-point lines. It provides a connectionless unacknowledged service, using flag bytes to delimit frames and a CRC for error detection. It is used to carry packets across a range of links, including SONET links in wide-area networks and ADSL links for the home.

Reed-Solomon code

We will describe is the Reed-Solomon code. Like Hamming codes, Reed-Solomon codes are linear block codes, and they are often systematic too. Unlike Hamming codes, which operate on individual bits, Reed-Solomon codes operate on m bit symbols. Naturally, the mathematics are more involved, so we will describe their operation by analogy.

Reed-Solomon codes are based on the fact that every n degree polynomial is uniquely determined by n + 1 points. For example, a line having the form ax + b is determined by two points. Extra points on the same line are redundant, which is helpful for error correction. Imagine that we have two data points that represent a line and we send those two data points plus two check points chosen to lie on the same line. If one of the points is received in error, we can still recover the data points by fitting a line to the received points. Three of the points will lie on the line, and one point, the one in error, will not. By finding the line we have corrected the error.

Reed-Solomon codes are actually defined as polynomials that operate over finite fields, but they work in a similar manner. For m bit symbols, the codewords are 2m−1 symbols long. A popular choice is to make m = 8 so that symbols are bytes. A codeword is then 255 bytes long. The (255, 233) code is widely used; it adds 32 redundant symbols to 233 data symbols. Decoding with error correction is done with an algorithm developed by Berlekamp and Massey that can efficiently perform the fitting task for moderate-length codes (Massey, 1969).

Reed-Solomon codes are widely used in practice because of their strong error-correction properties, particularly for burst errors. They are used for DSL, data over cable, satellite communications, and perhaps most ubiquitously on CDs, DVDs, and Blu-ray discs. Because they are based on m bit symbols, a single-bit error and an m-bit burst error are both treated simply as one symbol error. When 2t redundant symbols are added, a Reed-Solomon code is able to correct up to t errors in any of the transmitted symbols. This means, for example, that the (255, 233) code, which has 32 redundant symbols, can correct up to 16 symbol errors. Since the symbols may be consecutive and they are each 8 bits, an error burst of up to 128 bits can be corrected. The situation is even better if the error model is one of erasures (e.g., a scratch on a CD that obliterates some symbols). In this case, up to 2t errors can be corrected.

Reed-Solomon codes are often used in combination with other codes such as a convolutional code. The thinking is as follows. Convolutional codes are effective at handling isolated bit errors, but they will fail, likely with a burst of errors, if there are too many errors in the received bit stream. By adding a Reed-Solomon code within the convolutional code, the Reed-Solomon decoding can mop up the error bursts, a task at which it is very good. The overall code then provides good protection against both single and burst errors.

The final error-correcting code we will cover is the LDPC (Low-Density Parity Check) code. LDPC codes are linear block codes that were invented by Robert Gallagher in his doctoral thesis (Gallagher, 1962). Like most theses, they were promptly forgotten, only to be reinvented in 1995 when advances in computing power had made them practical.

In an LDPC code, each output bit is formed from only a fraction of the input bits. This leads to a matrix representation of the code that has a low density of 1s, hence the name for the code. The received codewords are decoded with an approximation algorithm that iteratively improves on a best fit of the received data to a legal codeword. This corrects errors.

LDPC codes are practical for large block sizes and have excellent error-correction abilities that outperform many other codes (including the ones we have looked at) in practice. For this reason they are rapidly being included in new protocols. They are part of the standard for digital video broadcasting, 10 Gbps Ethernet, power-line networks, and the latest version of 802.11. Expect to see more of them in future networks.