Earliest Deadline First (EDF) Algorithm

  • It is an Optimal dynamic Priority Scheduling Algorithm
  • Priorities are assigned based on the absolute deadlines of the task, earlier the deadline, higher the priority.
  • It is also called as Deadline Monotonic Scheduling (DM).
  • If two tasks have the same deadline, then EDF randomly select  one to execute next.
  • The Schedulability condition for EDF is edf

where U is the processor Utilisation Factor and it never be greater than 1.

In practical, no processor will be utilised for more than 100%.

Rate Monotonic Scheduling (RM)

Rate Monotonic Scheduling is the optimal static priority algorithm. Shortly it is referred as RM or RMA or RMS. To solve for the RM schedule, the following are the assumptions.

Assumptions:

  • All the tasks are assumed to be periodic
  • The relative deadline of the tasks are equal to its period.
  • No tasks has a non pre-emptible section.
  • The cost of preemption is negligible.

RMA

  1. Priorities are assigned based on the periods of the task.
    1. Lower the period, higher the priority
    2. As rate is the inverse of the period, higher the rate, higher the priority
  2. It is a static priority algorithm (priorities are assigned to tasks during their compilation time)

Schedulability Test for RMA

To find the schedulability Test of RM algorithm

  • the sufficient condition for schedulability test for RM is

  • The necessary and sufficient condition for testing the schedulability test is

Scheduling Hierarchies

Valid Schedule
A scheduler is responsible for managing the resource allocation to the tasks and it is based on the scheduling algorithms. A scheduler produces a valid schedules should obey these rules
  • Every process is assigned to atmost one job at a time
  • Every job is assigned to atmost one processor at a time
  • No job is scheduled before its release time
  • Depending on the scheduling algorithms used, the total amount of processor time assigned to every job is equal to its actual execution time
  • All the precedence and resource usage constraints are satisfied.
Feasible Schedule
All tasks of valid schedule meets deadlines, then the schedule is said to be feasible

Optimal Schedule
Every feasible schedule is said to be optimal, if there exists a scheduling algorithm which does not schedule a particular task set, then no other scheduling algorithm can schedule that task set feasibly.
Eg.
The optimal static scheduling policy is Rate Monotonic Algorithm (RMA)
The Optimal dynamic Scheduling Policy is Preemptive Earliest Deadline First (EDF)

Phishing and Pharming

Phishing is the term derived from "fishing". It leads to a criminal and a fraudulent method of acquiring confidential information relating to financial transactions, such as passwords, credit card/debit card information, PIN numbers etc. The most common targets are online banking, shopping portals, etc. The technique behind is to urge suspecting users to send sensitive information through emails, deceptive replication of reputed websites. Such data is used to take out money from one's account.

Pharming is a successor of phishing and it operates when a link is clicked on an email purporting from the bank, you are trapped. At this point, even if the key for URL is entered correctly, the malware manipulates the PC such that the browser will only lead to the fraudulent website.

Solution

  • Updated Anti Virus and anti spyware
  • Always check the url of the bank to be https:// and not http://
  • Always enter the URL of the bank manually in the address bar, never take it from any other websites or through email.
  • To guard against, fake websites, give the username correctly and enter the password wrongly, so that the original bank website will tell wrong and the fake website will give you a "Thank you Message"

Source: CHIP Magazine and online resource

DATA STRUCTURES – Q & A

Define Abstract Data Type (ADT).

Abstract data type is a collection of value definitions and the operations on those values.

    • Value definitions
    • Operator definitions

Define a sequence.

A sequence is an ordered set of elements.

S=<s0,s1,s2…….sn-1>

Write short notes on structures in C.

A basic data structure in C is called as the structure. A Structure is a group of items in which each item is identified by its own identifier.

Example:

struct nametype

{

char first[10];

int roll;

}sname, ename;

What is the difference between a structure and union in C.

  1. Same memory is used for all the members of union. At any time only one member can be accessed.
  2. Individual memory is used for structure members.

Define a Stack.

A stack is an ordered collection of items into which new items may be inserted and from which items may be deleted at one end called the top of the stack.

It is also called as Last In First Out (LIFO).

What are the primitive operations that are performed on a Stack?

The primitive operations are

Push- inserting an element at the top of the stack

Push(s,i);

Pop – removing an element at the top of the stack

i=pop(s);

How do you implement the Stack definition in C. Use array implementation?

#define STACKSIZE

struct stack

{

int top;

int items[STACKSIZE];

};

Write the steps for implementing the pop operation.

    • If the stack is empty, print a warning message and halt execution
    • Remove the top element from the stack.
    • Return this element to the calling program

What is recursive definition?

An object in terms of simpler case of itself is called recursive definition.

Examples:

· To find the factorial of a given number

· To print the Fibonacci series.

Define a queue.

A queue is a ordered collection of items from which itesm may be deleted at one end (called the front of the queue) and into which items may be inserted at the other end (called the rear of the queue). It is also called as First in First out (FIFO).

How the queue is represented in C?

#define MAXQUEUE 100

struct queue

{

int items[MAXQUEUE];

int front, rear;

}q;

Define priority queue. What are the types of Priority queue?

The priority queue is a data structure in which the intrinsic ordering of the elements does determine the results. There are two types

· ascending priority queue

is a collection of items into which items can be inserted arbitrarily and from which only the smallest item can be removed.

· descending priority queue

What is the purpose of header node?

Sometimes it is desirable to keep an extra node at the front of the list. Such a node does not represent an item in the list and is called the header node or a list header.

How to create and delete a dynamic variable in C?

malloc() is a function helpful for creating a dynamic variable.

free() is a function helpful for deleting a dynamic variable.

How to create a node of a singly linked list using dynamic variables?

struct node

{

int info;

struct node *next;

};

typedef struct node *NODEPTR;

16. How to create a node of a Doubly linked list using dynamic variables?

struct node

{

int info;

struct node *next, *previous;

};

typedef struct node *NODEPTR;

17. Define a binary tree.

A binary tree is a finite set of elements that is either empty or is partitioned into three disjoint subsets. One subset is the left and one subset of the right and the third subset is the root of the tree.

18. What is a strictly binary tree?

If every non leaf node in a binary tree has nonempty left and right subtrees, the tree is named as the strictly binary tree.

19. Define traversal in tree and what is the different type of traversals in tree?

To pass through the tree, enumerating each of its nodes once.

Three types of traversals

    • preorder traversal
      • visit the root
      • Traverse the left subtree in preorder.
      • Traverse the right subtree in preorder
    • inorder traversal
      • Traverse the left subtree in preorder.
      • visit the root
      • Traverse the right subtree in preorder
    • postorder traversal
      • Traverse the left subtree in preorder.
      • Traverse the right subtree in preorder
      • visit the root

20. How the binary tree node is represented dynamically?

struct nodetype

{

int info;

struct nodetype *left;

struct nodetype *right;

};

21. What are called leaf nodes?

The nodes which don’t have any sons are called as leaf nodes.

22. What are called internal and external nodes?

The leaf nodes are called as external nodes and the non leaf nodes are called as internal nodes.

23. Define O notation.

To capture the concept of one function becoming proportional to another as it grows, a notation is which is called as O notation.

24. Define a graph.

A graph consists of a set of nodes (or vertices) and set of arcs (or edges).

25. Define weighted graph.

A number is associated with each arc of a graph is called a weighted graph. The number associated with the arc is called the weight.

26. Define minimum spanning tree.

Given a connected weighted graph G, it is often desired to create a spanning tree T for G such that the sum of the weights of the tree edges in T is as small as possible. Such a tree is called minimum spanning tree.

27. Define Depth First Traversal.

Visits the successors of a visited node before visiting any of its brothers.

In DFT, each visited node is placed in the stack

28. Define Breadth First Traversal.

Visits all successors of a visited node before visiting any successors of any of those successors.

In BFT, each visited node is placed on the queue.

29. What are called Dynamic data structures?

Structures which grow or shrink as the data they hold changes.

Example: Lists

30. Define Binary Search.

A technique for searching an ordered list in which we first check the middle item and - based on that comparison - "discard" half the data. The same procedure is then applied to the remaining half until a match is found or there are no more items left.

31. What are the advantages of linked lists?

· Overflow can never occur unless the memory is actually full.

· Insertions and deletions are easier than for contiguous (array) lists.

· With large records, moving pointers is easier and faster than moving the items th

emselves.

32. What are the disadvantages of linked lists?

· The pointers require extra space.

· Linked lists do not allow random access.

· Time must be spent traversing and changing the pointers.

· Programming is typically trickier with pointers.

33. Define Binary Search Trees.

A binary search tree is a binary tree where each node contains a key such that:

· All keys in the left subtree lesser than the key in the root.

· All keys in the right subtree greater the key in the root.

· The left and right subtrees of the root are again binary search trees.

34. What is the difference Data types vs. Data Structures?

· A data type is a well-defined collection of data with a well-defined set of operations on it.

· A data structure is an actual implementation of a particular abstract data type.

Introduction to Real Time Systems

System
Set of one or more inputs entering the black box and a set of outputs exiting the black box is called a system.

Response Time
The time between the presentation of set of inputs and the appearance of the associated outputs.

Real time System
A System that must satisfy the response tine constraints or it will be a failure.

Embedded System
A software system that is completely encapsulated by the hardware that it controls.

Deadline
The instant of time at which the execution of task is required to be completed.
* absolute deadline
* relative deadline = absolute deadline – release time

Release time
The instant of time at which the task or job is ready for execution

Challenges or Issues in Real time Systems
  • Selection of hardware and Software (Hardware includes sensors, actuators, timers, controllers or processors)
  • Selection of the operating Systems (Real Time Operating System) (RTOS works under the preemption principle.)
  • Selection of Programming language. (C, C++, ADA, Java, etc)
  • Maximizing the fault tolerance
  • Testing of the systems
  • Prediction and measurement of response time (The system should predict and measure of the response time before the development of the application.)
  • Concurrent control
Temporal parameters of Real Time workload
Task – A set of related jobs that execute to support a function is called a task.
Periodic task
Aperiodic task
Sporadic task
Fixed, Jittered and sporadic release time
Jittered means the range of release time
(ri- , ri+) the release time is given range
Execution time
Depends on the complexity of job and speed of the processor
The MPEG compression will take long time to execute.

Functional Parameters of RTS
  • Preemption of jobs
  1. if one job is running, when the other job comes and want of the execution, the first job is suspended and then the second job will be executed, after the second job complete, the first again resumes. This is called preemption. Usually the RTOS are working under the preemptive scheduling mechanism.
  2. The disadvantage here is the overhead due to the context switching. Because switching between the tasks frequently is a over head.
  • Criticality of jobs
  1. Criticality means the urgency of a job. That is, if a job is a urgent job so that it should be completed soon, then the job is said to be critical and that job has to be given higher priority or weightage.
  2. Generally, if tasks are there, then we can say priority of the task and if jobs are there, then we can say weightage of the job.
  • Optional execution
  1. Some jobs may be partially done or not at all executed, we can simple neglect those jobs or in other words the jobs are optional one.
  • Laxity type
  1. Determines whether hard or soft deadlines
  2. Based on usefulness function
Scheduling Hierarchies
A scheduler is responsible for managing the resource allocation to the tasks and it is based on the scheduling algorithms. A scheduler produces a valid schedules should obey these rules
  • Every process is assigned to atmost one job at a time
  • Every job is assigned to atmost one processor at a time
  • No job is scheduled before its release time
  • Depending on the scheduling algorithms used, the total amount of processor time assigned to every job is equal to its actual execution time
  • All the precedence and resource usage constraints are satisfied.

Precedence constraints and data dependency
  • Precedence graph and task graph
  1. Ti <>
  2. Tj is constrained to be preceded by Ti
  • Data dependency
  1. A common pool of data is used by various tasks in the system. So it is said as the shared data, being the data shared, there may not be any precedence constraints.
  • Temporal dependency
  1. Jobs are said to have a temporal distance constraint if their temporal distance must be a finite value. For example, the synchronizing the video and audio should have a temporal distance of 160ms.
  • * AND/ OR precedence constraints
  1. One job will be waiting for all its immediate predecessor to be completed before its execution begins.
  2. Eg. Transmitting a message can be accomplished only after the following three conditions, so transmitting a message refers a AND job.
  3. Setting the connection
  4. Encrypt the data
  5. Checking users account

  • One or more of its immediate predecessors are completed, and then it starts its execution. This is called as OR precedence constraints.
  1. So, to draw the task graph one should note these things in mind
  2. AND job is represented by - unfilled circle - o
  3. OR job is represented by – square box
  4. Branching is by means of – filled circle
Examples
o o o o o -(each circle indicate one task) there are five tasks, all are independent and
one task does not depend on the other. So, No precedence constraints

o------->o------> o------->o------> o------> o Here there are five tasks with precedence
constraints and one task after the completion, then only the next task will run, this is a dependency relationship

Basic Networking Concepts

Basic Networking Concepts
Introduction
  • A network can be defined as a group of computers and other devices connected in some ways so as to be able to exchange data.
  • Each of the devices on the network can be thought of as a node; each node has a unique address.
  • Addresses are numeric quantities that are easy for computers to work with, but not for humans to remember.
    • Example: 204.160.241.98
  • Some networks also provide names that humans can more easily remember than numbers.
Network Hardware
So what is a computer network? A network is a collection (two or more) of computers that are connected together for sharing data and resources. Networks are commonly categorized by their geographical size.
A local area network (a LAN) is a group of computers and associated devices that share a common communication line and are typically located within a small geographic area, such as in your home or in an office building, or even a single department in a company. A local area network may connect as few as two or three users, as in a home network, or as many as several hundred users, as in a business.
A metropolitan area network (a MAN) is a bit more diverse, incorporating computers and LANs that are distributed over a few miles of area, as you would find between corporate buildings or on a college campus.
A wide area network (a WAN) is a widely geographically dispersed computer network that is composed of multiple LANs and MANs and can be spread across a country or around the globe. The Internet (sometimes simply referred to as “the Net”) is a worldwide network of many computer networks (LANs, MANs, and WANs) that is accessible to hundreds of millions of people worldwide.
Domain Name System (DNS)
The numerical version of the IP address is usually represented by a name or series of names called the domain name—for instance, www.someplace.com or ftp. filearchive.edu, which is mapped into a static IP address using the Domain Name System (DNS).
The DNS is a hierarchical database used for translating the domain name to an IP address. When your computer needs to translate a domain name into a numerical IP address, it asks a domain name server to provide this information.
Internet addresses
The Internet Address is also called an IP address or Host Address. It is a logical address assigned to the network interface card in your computer. An IP address (where IP means Internet Protocol) is how one computer can find another computer on a network. Each node must know its own address on the network and that of any other computer with which it will communicate. The IP address is a 32-bit binary number that identifies each packet of information sent across the network. The IP address is usually expressed as four decimal numbers, each representing eight bits, separated by periods. This is sometimes known as the “dot address” or as “dotted quad notation.” For instance, in the example network shown in Figure 2-2, address 192.168.27.16 is the IP address of one of the machines. This is internally stored and used as the integer 3,232,242,448 which is 11000000.10101000.00011011.00010000. This can be represented in decimal numbers as shown

Protocols
Discussions of network communications often center on what is known as a protocol stack. A protocol is the set of rules that computers (or other network devices) in a network use when they communicate. In essence, a protocol is the language the network devices use to talk to each other. A protocol stack is an abstract model that divides the network up into layers, based on functions and communication protocols used in those functions. Each layer in the stack only talks to the layer above or below it, using the protocols defined in those layers. As information is passed down the stack, it is encapsulated. Encapsulation is basically a process of adding a protocol specific header to the information received from the layer above. As information is passed up the stack, the header specific to the current layer is stripped off and the data is sent to the layer above. By adhering to this protocol stack concept, software and hardware can be designed without worrying about the details of what’s going on in all the layers, just the neighboring layers. Things become reusable, transportable, device independent.
Types of Networks
There are two principle kinds of networks: Wide Area Networks (WANs) and Local Area Networks (LANs).
WANs
  • Cover cities, countries, and continents.
  • Based on packet switching technology
  • Examples of WAN technology: Asynchronous Transfer Mode (ATM), Integrated Services Digital Network (ISDN)
LANs
  • Cover buildings or a set of closely related buildings.
  • Examples of LAN technology: Ethernet, Token Ring, and Fiber Distributed Data Interconnect (FDDI).
  • Ethernet LANs: based on a bus topology and broadcast communication
  • Token ring LANs: based on ring topology
  • FDDI LANs: use optical fibbers and an improved token ring mechanism based on two rings flowing in opposite directions.



According to the protocols involved, networks interconnection is achieved using one or several of the following devices: →Bridge: a computer or device that links two similar LANs based on the same protocol.

Router: a communication computer that connects different types of networks using different protocols.

B-router or Bridge/Router: a single device that combines both the functions of bridge and router.

Gateway: a network device that connects two different systems, using direct and systematic translation between protocols.
What Is an Internetwork?
An internetwork is a collection of individual networks, connected by intermediate networking devices, that functions as a single large network. Internetworking refers to the industry, products, and procedures that meet the challenge of creating and administering internetworks.
Open System Interconnection Reference Model
The Open System Interconnection (OSI) reference model describes how information from a software application in one computer moves through a network medium to a software application in another computer. The OSI reference model is a conceptual model composed of seven layers, each specifying particular network functions. The model was developed by the International Organization for Standardization (ISO) in 1984, and it is now considered the primary architectural model for intercomputer communications. The OSI model divides the tasks involved with moving information between networked computers into seven smaller, more manageable task groups. A task or group of tasks is then assigned to each of the seven OSI layers. Each layer is reasonably self-contained so that the tasks assigned to each layer can be implemented independently. This enables
the solutions offered by one layer to be updated without adversely affecting the other layers. The following list details the seven layers of the Open System Interconnection (OSI) reference model:
• Layer 7—Application
• Layer 6—Presentation
• Layer 5—Session
• Layer 4—Transport
• Layer 3—Network
• Layer 2—Data link
• Layer 1—Physical

Characteristics of the OSI Layers
The seven layers of the OSI reference model can be divided into two categories: upper layers and lower layers.
The upper layers of the OSI model deal with application issues and generally are implemented only in software. The highest layer, the application layer, is closest to the end user. Both users and application layer processes interact with software applications that contain a communications component. The term upper layer is sometimes used to refer to any layer above another layer in the OSI model.
The lower layers of the OSI model handle data transport issues. The physical layer and the data link layer are implemented in hardware and software. The lowest layer, the physical layer, is closest to the physical network medium (the network cabling, for example) and is responsible for actually placing information on the medium.
OSI Model and Communication Between Systems
Information being transferred from a software application in one computer system to a software application in another must pass through the OSI layers. For example, if a software application in System A has information to transmit to a software application in System B, the application program in System A will pass its information to the application layer (Layer 7) of System A. The application layer then passes the information to the presentation layer (Layer 6), which relays the data to the session layer
(Layer 5), and so on down to the physical layer (Layer 1). At the physical layer, the information is placed on the physical network medium and is sent across the medium to System B. The physical layer of System B removes the information from the physical medium, and then its physical layer passes the information up to the data link layer (Layer 2), which passes it to the network layer (Layer 3), and so on, until it reaches the application layer (Layer 7) of System B. Finally, the application layer of System B passes the information to the recipient application program to complete the communication process.
Interaction Between OSI Model Layers
A given layer in the OSI model generally communicates with three other OSI layers: the layer directly above it, the layer directly below it, and its peer layer in other networked computer systems. The data link layer in System A, for example, communicates with the network layer of System A, the physical layer of System A, and the data link layer in System B

OSI Model Physical Layer
The physical layer defines the electrical, mechanical, procedural, and functional specifications for activating, maintaining, and deactivating the physical link between communicating network systems.
Physical layer specifications define characteristics such as voltage levels, timing of voltage changes, physical data rates, maximum transmission distances, and physical connectors. Physical layer implementations can be categorized as either LAN or WAN specifications.
OSI Model Data Link Layer
The data link layer provides reliable transit of data across a physical network link. Different data link layer specifications define different network and protocol characteristics, including physical addressing, network topology, error notification, sequencing of frames, and flow control. Physical addressing (as opposed to network addressing) defines how devices are addressed at the data link layer.
Network topology consists of the data link layer specifications that often define how devices are to be physically connected, such as in a bus or a ring topology. Error notification alerts upper-layer protocols that a transmission error has occurred, and the sequencing of data frames reorders frames that are transmitted out of sequence. Finally, flow control moderates the transmission of data so that the receiving device is not overwhelmed with more traffic than it can handle at one time.
OSI Model Network Layer
The network layer defines the network address, which differs from the MAC address. Some network layer implementations, such as the Internet Protocol (IP), define network addresses in a way that route selection can be determined systematically by comparing the source network address with the destination network address and applying the subnet mask. Because this layer defines the logical network layout, routers can use this layer to determine how to forward packets. Because of this, much of the design and configuration work for internetworks happens at Layer 3, the network layer.
OSI Model Transport Layer
The transport layer accepts data from the session layer and segments the data for transport across the network. Generally, the transport layer is responsible for making sure that the data is delivered error-free and in the proper sequence. Flow control generally occurs at the transport layer. Flow control manages data transmission between devices so that the transmitting device does not send more data than the receiving device can process. Multiplexing enables data from several applications to be transmitted onto a single physical link. Virtual circuits are established, maintained, and terminated by the transport layer. Error checking involves creating various mechanisms for detecting transmission errors, while error recovery involves acting, such as requesting that data be retransmitted, to resolve any errors that occur.
The transport protocols used on the Internet are TCP and UDP.
OSI Model Session Layer
The session layer establishes, manages, and terminates communication sessions. Communication sessions consist of service requests and service responses that occur between applications located in different network devices. These requests and responses are coordinated by protocols implemented at the session layer. Some examples of session-layer implementations include Zone Information Protocol (ZIP), the AppleTalk protocol that coordinates the name binding process; and Session Control Protocol (SCP), the DECnet Phase IV session layer protocol.
OSI Model Presentation Layer
The presentation layer provides a variety of coding and conversion functions that are applied to application layer data. These functions ensure that information sent from the application layer of one system would be readable by the application layer of another system. Some examples of presentation layer coding and conversion schemes include common data representation formats, conversion of character representation formats, common data compression schemes, and common data encryption schemes. Common data representation formats, or the use of standard image, sound, and video formats, enable the interchange of application data between different types of computer systems. Conversion schemes are used to exchange information with systems by using different text and data representations, such as EBCDIC and ASCII. Standard data compression schemes enable data that is compressed at the source device to be properly decompressed at the destination. Standard data encryption schemes enable data encrypted at the source device to be properly deciphered at the destination.
Presentation layer implementations are not typically associated with a particular protocol stack. Some well-known standards for video include QuickTime and Motion Picture
Experts Group (MPEG). QuickTime is an Apple Computer specification for video and audio, and MPEG is a standard for video compression and coding. Among the well-known graphic image formats are Graphics Interchange Format (GIF), Joint Photographic Experts Group (JPEG), and Tagged Image File Format (TIFF). GIF is a standard for compressing and coding graphic images. JPEG is another compression and coding standard for graphic images, and TIFF is a standard coding format for graphic images.
OSI Model Application Layer
The application layer is the OSI layer closest to the end user, which means that both the OSI application layer and the user interact directly with the software application.
This layer interacts with software applications that implement a communicating component. Such application programs fall outside the scope of the OSI model. Application layer functions typically include identifying communication partners, determining resource availability, and synchronizing communication.
When identifying communication partners, the application layer determines the identity and availability of communication partners for an application with data to transmit. When determining resource availability, the application layer must decide whether sufficient network resources for the requested communication exist. In synchronizing communication, all communication between applications requires cooperation that is managed by the application layer. Some examples of application layer implementations include Telnet, File Transfer Protocol (FTP), and Simple Mail Transfer Protocol (SMTP).
What Is a LAN?
A LAN is a high-speed data network that covers a relatively small geographic area. It typically connects workstations, personal computers, printers, servers, and other devices. LANs offer computer users many advantages, including shared access to devices and applications, file exchange between connected users, and communication between users via electronic mail and other applications.
LAN Transmission Methods
LAN data transmissions fall into three classifications: unicast, multicast, and broadcast. In each type of transmission, a single packet is sent to one or more nodes. In a unicast transmission, a single packet is sent from the source to a destination on a network. First, the source node addresses the packet by using the address of the destination node. The package is then sent onto the network, and finally, the network passes the packet to its destination.
A multicast transmission consists of a single data packet that is copied and sent to a specific subset of nodes on the network. First, the source node addresses the packet by using a multicast address. The packet is then sent into the network, which makes copies of the packet and sends a copy to each node that is part of the multicast address.
A broadcast transmission consists of a single data packet that is copied and sent to all nodes on the network. In these types of transmissions, the source node addresses the packet by using the broadcast address. The packet is then sent on to the network, which makes copies of the packet and sends a copy to every node on the network.
LAN Topologies
LAN topologies define the manner in which network devices are organized. Four common LAN topologies exist: bus, ring, star, and tree. These topologies are logical architectures, but the actual devices need not be physically organized in these configurations. Logical bus and ring topologies, for example, are commonly organized physically as a star. A bus topology is a linear LAN architecture in which transmissions from network stations propagate the length of the medium and are received by all other stations.

A ring topology is a LAN architecture that consists of a series of devices connected to one another by unidirectional transmission links to form a single closed loop. Both Token Ring/IEEE 802.5 and FDDI networks implement a ring topology. Figure depicts a logical ring topology.
A star topology is a LAN architecture in which the endpoints on a network are connected to a common central hub, or switch, by dedicated links. Logical bus and ring topologies are often implemented physically in a star topology, which is illustrated in Figure. A tree topology is a LAN architecture that is identical to the bus topology, except that branches with multiple nodes are possible in this case. Figure 2-5 illustrates a logical tree topology.