Breadth-first search (BFS)

BFS is one of simplest algorithms for searching graphs.

It is an uninformed search method that exhaustively searches the entire graph without considering the goal until it finds it.


Directed Graph G is described as pair (V,E) where V is finite set of nodes and E is binary relation in V.

E:(v1,v2) -> t; where v1, v2 are nodes in V, and t is arrow, in one direction, other direction or two directions, or no arrow at all.

This is read: relation E is function that associates value t from set of arrows to each of tuples: (v1,v2). Set of arrows consists of elements: arrow in one direction, arrow in other direction, arrow in two directions, no arrow at all.

E is called edge set. Graphically, nodes are pictured as circles, and edges are pictured as arrows. It is possible for loop to exist, connecting node to itself.

In oriented graph there are no arrows in two directions at once.

In Undirected Graph G = (V,E), edge set E is set of unordered pairs of nodes. There are no loops in undirected graphs.

If (u,v) is edge of directed graph G = (V,E), then edge (u,v) joins initial node (or tail) u, with destination node v. If (u,v) is edge of undirected graph G = (V,E), then edge (u,v) is incidental with u and v.

If (u,v) is edge of Graph G = (V,E), then we say, that node v is adjacent to node u. In undirected graph, adjacency relation is symmetrical (if u is adjacent to v, then v is adjacent to u).

Path in a graph is serie of nodes such as that for each of node pairs, there's an edge leading from first node to second - directed or not. First and last node in a path are called beginning and end of the path. About the edge that joins two nodes next to each other, we say that it belongs to a path.

Distance in a graph is the length of shortest path between two graph nodes.

Path is simple if there are no repeated nodes on it.

Cycle consists of a sequence of edges (arrows) starting and ending at the same edge, with each two consecutive edges in the sequence adjacent or incidental to each other in the graph. In a directed cycle, edges must have arrows pointing from previous edge to next, start and end up in first edge.

Graph is consistent if any two nodes can be connected by a path.

Graph Gs = (Vs, Es) is called subgraph, when there's a graph G = (V,E) and Vs is subset of V, and Es is subset of E.

We also take note of largest consistent subgraphs - any subgraph with maximum amount of nodes and edges that can belong to it is called such.

Source: [4], Wikipedia, [19].

Introduction to Network Management Framework

The Internet-Standard Management Framework consists of four major parts:

  • Definitions of network management objects, known as MIB objects,
  • A data definition language, known as SMI (Structure of Management Information),
  • A protocol, SNMP. For conveying information and commands between a managing entity and an agent executing on behalf of that entitity within management network device,
  • Security and administration capabilities.

SMI defines the data types, and object model, and rules for writing and revising management information. MIB objects are specified in this data definition language. SMI is based on ASN.1 (Abstract Syntax Notation One), abstraction over machine-dependent representation of data.

MIB, or Management Information Base, can be thought of as a virtual information store, holding management objects whose values collectively reflect the current "state" of the network. These values may be queried and/or set by a managing entity by sending SNMP messages to the agent that is executing in a managed device on behalf of managing entity.

SNMP, or Simple Network Management Protocol is used to convey MIB information among managing entities and agents executing on behalf of managing entities. The most common usage of SNMP is in a request-response mode. A second common usage of SNMP is for an agent to send unsolicited message, known as trap message, to a managing entity. Trap messages are used to notify a managing entity of an exceptional situation that has resulted in changes to MIB object values. Network administrator might want to receive a trap message, for example when an interface goes down, congestion reaches a predefined level on a link, or some other noteworthy event occurs.

Security : SNMPv3 (Simple Network Management Protocol version 3) security is known as user-based security in that there is traditional concept of user, identified by a username, with which security information such as a password, key value, or access privileges are associated. SNMPv3 provides for encryption, protection against playback attacks and access control.

Management Capabilities can be added by writing management application (or using existing software) that lets managing entity to "monitor, test, poll, configure, analyze, evaluate, and control the network and element resources to meet the real-time, operational performance and Quality of Service requriements at a reasonable cost".


Sieve of Eratosthenes.

In mathematics, the sieve of Eratosthenes, one of a number of prime number sieves, is a simple, ancient algorithm for finding all prime numbers up to any given limit.

Sieve of Eratosthenes in action., In mathematics, the sieve of Eratosthenes, one of a number of prime number sieves, is a simple, ancient algorithm for finding all prime numbers up to any given limit.


Stitie Machine Interface

Stitie Machine interface is available. (Java code).

Now with contract. (see javadoc comments).


Petersen's Algorithm

It's solution to problem of synchronizing two processess (running programs) wanting to enter critical section of code (section that cannot be accessed by more than one process at the same time). Using global variables (that indicate which process[-es] want to enter critical section, and which process waits) and simple programming instructions we can ensure that only one process enters critical section at given time.


Firewalls and Intrusion Detection Systems

Firewall is a combination of hardware and software (such as iptables) that isolates an organization's internal network from the Internet at large, allowing some packets (of information) to pass and blocking others. A firewall allows a network administrator to control access between the outside world and resources within the administered network by managing the traffic flow to and from these resources.

A firewall has three goals:

  • All traffic from outside to inside and vice versa, passess through firewall.
  • Only autorized traffic, as defined by the local security policy, will be allowed to pass.
  • The firewall itself is immune to penetration.

Firewalls can be classified in three categories: traditional packet filters, stateful filters, and application gateways.

Traditional packet filters examine each datagram in isolation, determining whether the datagram should be allowed to pass or should be dropped on administrator-specific rules.

Stateful packet filters track all ongoing TCP connections in a connection table, which is also used to when choosing whether packet should be allowed to pass or not.

Application Gateway is an application-specific server through which all application data (inbound and outbound) must pass. It allows for finer-level security (allowing specific users of specific applications to access outside world services).

Packet filters inspect header fields when deciding which packets to let pass through firewall. However to detect many attack types, we need to perform deep packet inspection, that is, look beyond the header fields and into the actual application data that the packets carry.

A device that generates alerts when it oserves potentially malicious traffic is called an Intrusion Detection System (IDS). A device that filters out suspicious traffic is called an Intrusion Prevention System (IPS).

IDS (IPS are also IDS) systems are broadly classified as either signature-based systems or anomaly-ased systems. (Snort is program that has become de facto standard among IPS / IDS software).

A signature-based IDS maitains an extensive database of attack signatures. Each signature is a set of rules pertaining to an intrusion activity. A signature may simply be a list of characteristics about a single packet (e.g., source and destination port numbers, protocol type, and specific string of bits in the packet payload), or may relate to series of packets. The signatures are normally created by skilled network security engineers who research known attacks.

Signature-based IDS systems, although widely deployed, have a number of limitations. Most importantly, they require previous knowledge of the attack to generate an accurate signature. They also can be resource-intensive.

An anomaly-based IDS creates traffic profile as it observes traffic in normal operation. It then looks for packet streams that are statistically unusual. (For example, an inordinate percentage of ICMP packets or a sudden exponential growth in port scans and ping sweeps.). The great thing about anomaly-based IDS systems is that they don't rely on previous knowledge about existing attacks - that is, they can potentially detect new, undocumented attacks. On the other hand, it is an extremely challenging problem to distinguish between normal traffic and statistically unusual traffic.

To date, most IDS deployments are primarily signature-based, although some include some anomaly-based features.