Basic Draft

2011-11-07T08:29:00.004+08:00

Misc 52

It's been such a long time since I've come up with an article that I find it hard to name this one. It seems miscellaneous anyway, so I'll name it that way.

This article is about using port-mirroring with Linux iptables for purposes such as Sniffing, IDS Monitoring and so on.

For this article, I'm going to show you how to capture DNS requests made by an application on an Android phone. Sounds difficult, but with sniffing, you can finish this task in less than 5 minutes!

First, you need to get on the Linux box (via Telnet or whatever) doing the routing. (Well, I'm technically on a WRT160NL running DD-WRT, so it is a Linux box)

We'll need to enter the following commands:
iptables -t mangle -A PREROUTING -s 172.16.1.139 -j ROUTE --tee --gw 172.16.1.150

In this case, 172.16.1.139 is the phone's IP address, while 172.16.1.150 is the IP of the system doing the sniffing. The above command redirects traffic coming FROM the phone.

In iptables, a packet goes through the following tables:
1) Filter
2) NAT
3) Mangle

Filter is for filtering of unwanted packets, NAT is for address translations, and Mangle is for final modification of packets (for things like QoS or mirroring).

Visit here to have a clearer idea of how the packet is routed.

The ROUTE target is an experimental target that performs routing in the mangle table. The -tee parameter specifies to MIRROR a packet, and the -gw parameter specifies the gateway to send it through.

Here is the documentation for the ROUTE target

Next, if we're interested in the return traffic, we can also enter the following commands:
iptables -t mangle -A POSTROUTING -d 172.16.1.139 -j ROUTE --tee --gw 172.16.1.150

If we are interested in ALL traffic, we can omit the -d and -s parameters.

Now we can fire up Wireshark and do some sniffing. First, we'll need to select the right interface for sniffing. Mine is quite obvious:

Now, as we are interested in DNS traffic in this scenario, we'll use the filter:
ip.addr == 172.16.1.139 && udp.port == 53

Go generate the request in your phone. Lo and behold, as if black magic, you now know the DNS names your phone applications are connecting to.

From here you can do what you want. Let's say you want to find out what port the phone is accessing and what type of traffic goes through. No problem, just scroll down and look for the line where the answer comes back in (usually one line after the request).

We'll then use the following filters:
ip.addr == 1.2.3.4 && tcp.flags.syn == 1

Of course, replace 1.2.3.4 with the response address. You'll get something like this:

In our case, it's port 8300 we're looking for!

Of course, this is not where we stop. Remember, the extra rule takes up extra CPU cycles. When you're done, remember to remove everything using:

iptables -t mangle -D PREROUTING -s 172.16.1.139 -j ROUTE --tee --gw 172.16.1.150
iptables -t mangle -D POSTROUTING -d 172.16.1.139 -j ROUTE --tee --gw 172.16.1.150

2011-02-26T16:17:00.002+08:00

NETSEC 10

Last chapter, then time for exam papers!

Identification is not the same as Authentication. Identification is concerned with "Who you are?", while Authentication is concerned with "Are you really who you are?"

An example of Identification is a username, and Authentication is a password.

Authentication can be done in three ways:
-What you have - Smart card, Token
-What you know - Passwords, secret answers, PIN
-What you are - Biometrics like fingerprint

2FA is simply a combination of any of these two.

The disadvantage of "What you have" is that it can be stolen or forged.

The disadvantage of "What you know" is that it can be brute-forced. Most of the time it is easily cracked via technical methods.

The most secure method thus far (the level of security depends on the accuracy of the system) is "What you are". Biometrics such as voice, fingerprint and iris are things that cannot be forgotten, lost or stolen and is extremely impractical to forge (with current technologies. Who knows, maybe you're from 2020 and they've forged people).

Biometric must be something that is completely unique to an individual. Biometrics that meet these requirements include fingerprints, finger scans, retinal scans, voice scans, handwriting recognition, face recognition, and hand scans.

Biometrics require a hardware infrastructure (scanners, etc) and a database to store these information in digital form. They must also be smart enough to be able to compare newly scanned biometric information with stored information (which are bound to be slightly different).

The biometric protocol is to (in case of Fingerprint):
1) Capture - The fingerprint of those permitted are scanned
2) Process - The fingerprint is processed and quantized into binary data
3) Store or Verify (First time only) - The data is stored, or in case of verification, the data is compared against the one stored in the database.

Advantages of Fingerprinting:
-Moderately Reliable
-Cheap to manufacture
-Little data needs to be stored (<1KByte)
-Easy to implement everywhere (e.g. Even in webpages)

Disadvantages:
-Requires close contact with scanner
-Dirt on finger can affect recognition
-Fingerprint readers have to be cleaned

Another way of scanning as mentioned is the Iris/Retinal scans. Advantages are:
-More accurate and have more characteristics to match
-Can scan through glasses and contact lenses (in case of Iris)
-Low error rate (one in 2 million)

Disadvantages
-Difficulty reading blind or cataract patients
-Cumbersome to use

And now we're done.

2011-02-26T14:44:00.002+08:00

NETSEC 09

Here comes my favorite chapter in the whole book. It's probably the final chapter since biometrics isn't important. Let's begin!

Oh did I mention, it's CRYPTOGRAPHY TIME!

Cryptography is the conversion of information into an form incomprehensible by people who do not have secret knowledge. In other words, creating the encryption/decryption system is the essence of cryptography.

Cryptanalysis is the opposite. Cryptanalysis is the breaking of the cryptography system by obtaining the secret through various means to break a code.

Plaintext (or less technically cleartext) is the original data. It is directly readable, or in case of data, useful.

Ciphertext is the plaintext that has gone through a cipher to make it unreadable.

Cipher is the encryption algorithm.

Key is the secret (typically a series of bits or a String which is later converted into bits) used by the cipher to encrypt/decrypt the plaintext into the ciphertext and vice versa.

Encryption is the conversion of plaintext into ciphertext using a cipher and key.

Decryption is the conversion of ciphertext into plaintext using a cipher and key.

cipherEncrypt(plainText,key) = cipherText;
cipherDecrypt(plaintext,key) = plainText;

In other words, the input of encryption is plaintext, and the output is ciphertext. The input of decryption is ciphertext, and the output is plaintext.

The goals of cryptography are slightly different, it now is:
C - Confidentiality
I - Integrity
A - Authentication
N - Non-Repudiation

Repudiation occurs when a user denies that he has sent something after he did. Non-repudiation ensures that he cannot do that, which we will see later in Asymmetric Encryption. It makes sure that NOBODY CAN PROVE that a transaction didn't take place if it did.

Private key encryption is known as symmetric cryptography, secret key, or single key.
Public key encryption is known as asymmetric cryptography.

The common symmetric key algorithms (ciphers) are:
-DES - Data Encryption Standard
-3DES - Triple DES
-AES - Advanced Encryption Standard
-IDEA - International Data Encryption Algorithm)
-RC[2,4,5] - Ron's Code, or Rivest Cipher

-Symmetric encryption is faster than asymmetric cryptography as the algorithm is computationally less complex
-Both side uses the same keys, therefore it must be private
-Shorter key length can be used to achieve the same level of security provided by an asymmetric system using longer key length

Both sides need to have the key before communication can take place. This is sent to the other side through various secure and insecure means (can be in-band and out-of-band).

The main disadvantage of symmetric encryption is the difficulty of sending the keys across securely. Keys may be lost/stolen/modified as it transits an insecure medium.

Assuming that 5 parties need to communicate, and they are NOT to be able to decipher each other's communication, then the number of keys required would be exponential according to the formula:
n(n-1)/2

2 parties would need 1 key, 3 parties would need 3 keys, 4 parties would need 6 keys, 5 parties would need 10 keys, and so on. 50 parties would need 1225 keys which is really impractical.

The problem with key distribution is solved through asymmetric encryption. Whitfield Diffie and Martin Hellman introduced the Diffie Hellman scheme in 1976. Another scheme, known as RSA (Rivest, Shamir and Adelman) was introduced later on.

Asymmetric encryption involves two mathematically related keys known as the public and private key. Either key can be public or private, as long as the private key is only owned by the owner.

Let k be the keys, p be the plaintext, c be the ciphertext, and f(x,y) be the encryption and g(x,y) be the decryption functions of the cipher. An asymmetric encryption would satisfy:

f(p1,k1) = c1;
g(c1,k2) = p1;

f(p2,k2) = c2;
g(c2,k1) = p2;

f'(c1,k1) = p1; DOES NOT EXIST
f'(c2,k1) = p2; DOES NOT EXIST
h(k1) = k2; DOES NOT EXIST

You may not encrypt and decrypt using the same key. You cannot derive the other key using the first key (you may only use bruteforce). The public key would be public and should be available for everyone. These are usually stored into key servers such as http://pgp.mit.edu/. You may also send public keys through email and websites. The private key, however, MUST be kept only to the owner.

Private keys are typically kept secure using a passphrase. The passphrase is used to encrypt/decrypt the private key, which is used to decrypt anything encrypted with the public key. (I love this chapter).

An example of asymmetric encryption would be:
I want to send YOU a mail
I obtain YOUR public key somehow (through online directories or otherwise)
I encrypt my mail with YOUR public key and send it to you
YOU decrypt the mail with YOUR private key

Two advantages of symmetric over asymmetric is:
-Less computationally complex, so symmetric is faster
-Symmetric key needs a shorter key length to have the same key strength

Two advantages of symmetric key over asymmetric are:
-It is difficult to transmit the key
-Difficult to manage keys (keys increase exponentially to the number of parties)

The number of keys required is simply: 2*n;

Remember, when referring to decryption and encryption, always use the keyword "corresponding". For example, use the "corresponding" public key to decrypt something encrypted with a private key.

If I want to send you something, and I encrypt with my public key instead, then you must have my private key to decrypt. Since only I have my private key, you will never be able to read that message unless you stole it from me.

Encryption with my private key is only done so that you can verify that I indeed AM the one that sent that message. This is not for confidentiality because anyone can get the public key for decryption. It's more for non-repudiation (i.e. If the message can be decrypted with the public key, then the owner of the public key definitely sent it, unless the private key was compromised).

The advantages of asymmetric keys are:
-Keys can be exchange easily without any special arrangement.
-Can be used to implement non-repudiation

The disadvantages are:
-Slow compared to symmetric key cryptography
-Computationally very complex, and programming is very difficult

As a review:
To send a confidential message - Use the receiver's public key to encrypt
To receive a confidential message - Decrypt with your own private key
To sign a message - Encrypt the message with your own private key
To verify a signature - Decrypt the message with signer's public key

If you use the wrong public key to sign, then the intended recipient would not be able to see the message. Certificates are used to store the public key for identification. We'll cover this later.

Let's now talk about hash functions. Hash functions are one way message-digest functions used to find the fingerprint of a particular object. It performs one-way transformation in a way where:

f(x) = y; Exists
f'(y) = x; Does not exist

Hash is not an encryption. The original document cannot be derived from the hash.

Hashes are typically used to check the integrity of the message. Message X has fingerprint x, but Modified Message X will have a fingerprint of y.

Properties of Hashes are:
A small change in input results in a big change in output - The Avalanche Effect
-As an example, if "An apple" gives abc1298fe, "An Apple" would give 1029defef

Input of different lengths always produce same length outputs
-If "Apple" gives abc1298fe, "An Apple" would give 1029defef

Two different inputs will not produce the same input (Anti-collision)
-By definition, since the hash output is 128-bits, then out of every 2^(128) input, only two would give the same output. That is a huge number.

It would take 128 bits * 2^(128) bits of space to store rainbow tables to defeat MD5. It is even more impractical to defeat SHA-1.

Same input always same output
-If "Apple" gives abc1298fe now, it will ALWAYS be abc1298fe.

These are the tested MD5 algorithms:
-MD4/MD5 (128-bits)
-SHA-1 (160-bits)
-SHA-2 (comprises of SHA-224, SHA-256, SHA-384, SHA-512)

Verification of the message Integrity through hash is as such:
I send you a message, and a hash of that message
You hash the received message, and compare it with the attached hash

A Digital Certificate is used to identify the owner. It is used in a Public Key Infrastructure and issued by Certificate Authorities. The Public Key is stored in the Digital Certificate, and the hash of a portion of the Digital Certificate is signed using the Certificate Authority's private key. This lets you:
-Verify and communicate with the owner
-Verify that the Digital Certificate came from a real CA

Digital certificates typically have a common name used in proving the identity of e-commerce sites (SSL/TLS). The most common digital certificate standard is the X.509. (There is a mistake in seminar, it's not a signature, it's a certificate).

A benefit of Asymmetric encryption is the use of Digital Signatures to implement non-repudiation and origin authenticity. It can also be used to verify that information is not lost in transit.

A digital signature is "a type of asymmetric cryptography used to simulate the security properties of a signature in digital form". It provides:
-Authentication - The signer is really who he is
-Non-repudiation - The signer cannot deny that he did not sign it
-Integrity - The data was sent and received without alteration

Signing is done in two simple steps:
-Hash the message
-Sign the has, then attach it with the message

The message sent is...
Plaintext+Sign(MD5(Plaintext))

The receiver then takes the hash, and decrypts it with the public key of the sender (If it can be decrypted, it verifies the sender and provides non-repudiation).

Now he hashes the message, and compares it with the decrypted hash (Verifies the Integrity of the message if it matches).

PGP is a software that makes use of asymmetric encryption to provide services such as signing and encryption for mainly email. In this case, event the sent message is encrypted, so a message to you looks like:
cipherEncrypt(plainText,yourPublic)+cipherEncrypt(md5(plainText),myPrivate)

Don't have funny ideas about "myPrivate" here. It's a key not a part.

2011-02-26T14:21:00.002+08:00

NETSEC 08

We now go into a short chapter of Wireless Security. The advantage of having wireless is that it is convenient, doesn't require extensive cabling and planning, has a high ROI and can increase productivity (mobile users). It can also be used for temporary deployments such as during a trade show.

Wireless operates on the 2.4GHz and the 5GHz radio frequency ranges. The NIC has a Radio transceiver attached to it to allow communication with the AP. Wireless can experience interference when communicating through heavy walls, large metal objects, etc.

Wireless can operate in two modes:
-Infrastructure - Indirectly through a central place, e.g. AP
-Ad-Hoc - Directly between two hosts

APs are typically used to connect wireless clients to a wired network.

Each wireless network is identified with an SSID (Service Set Identifier) and it can be configured as Infrastructure mode on the AP or Ad-Hob mode on the initial client. SSIDs are periodically advertised through beacons.

Ad-Hoc clients do not require an access point and is easier to set up temporarily. Infrastructure mode takes advantage of the high powered antennae to cover wide areas.

802.11 refers to the wireless standards established by the IEEE. Here's a simple breakdown:

802.11a
-Operates on 5GHz, less crowded, and less interference from other appliances
-Speed up to 54Mbps
-Incompatible with b/g

802.11b
-Operates on 2.4GHz, more crowded, likely to be interfered by microwaves, cordless phones, etc.
-Speed up to 11Mbps but can operate over further distances
-More susceptible to heavy walls and big metal objects

802.11g
-Operates on 2.4GHz
-Speed up to 54Mbps, same range as b
-Backwards compatible with b, but will operate at lower speeds

802.11n
-Operates on both 2.4GHz and 5GHz (or either)
-300Mbps through MIMO technology

All vulnerabilities of a wired ethernet applies to wireless, and in addition, it is especially prone to interception attacks, as well as interruption through jamming.

Frames are sent as far as the radio transmissions take it, and any device within range of an unprotected network can intercept every packet.

War Driving refers to the technique that involves driving through a neighborhood to map APs using a wireless-enabled laptop. The information can then be used to plan attacks on insecured networks, or badly secured ones. AirSnort and NetStumbler are two free wireless network detectors.

To combat insecurities, the WEP (Wired Equivalent Privacy) was developed. Ideally, only the receiver can comprehend the received data. It is designed to provide the same level fo security of a wired LAN, prevent malicious users from sniffing, and prevent malicious users from sending crafted frames. It uses the RC4 encryption with a 40- or 128-bit key (symmetric) for Confidentiality and the CRC32 checksum for Integrity. The keys need to be configured on both ends. It works no the Data Link and Physical Layers, so it does not offer end-to-end security (and it is not designed to).

All that being said, WEP is not very secure, and can be cracked under 5 minutes, but it should be the bare minimum.

Measures against sniffing (some more effective than others) include:
-Changing the default SSID
-Disable SSID broadcasting
-Use MAC filtering
-Use an encryption scheme
-Change WEP keys often (or make use of TKIP)
-Only share what is needed
-Disable access point administration over wireless

Short chapter eh?

2011-02-26T13:46:00.002+08:00

NETSEC 07

We now go into the topic of Malicious Code. Malicious Code can be any code that is capable of causing harm to a system. Malicious code include Viruses, Worms, Trojan Horses, and can include certain malicious Java Applets and ActiveX Controls.

It is sometimes not possible to classify a code under a specific class, so the general term "malware" is used. A malware is not necessarily a virus, but is a virus is definitely a malware.

Malicious code cause harm to the network by attacking the goals of network security (cause DoS, modify data, leak out confidential information). This would end up reducing productivity, causing bad reputation and loss of revenue.

A virus is a program that attaches itself into another program. It can be embedded at the start (similar to a launcher), or at the end of a program (similar to the use of a codecave).

For a virus to start working, the infected program must be executed. Some virus perform deadly operations immediately, while others remain inactive until conditions are met (e.g. A command is sent from the attacker, or a certain day and time).

Most viruses are written in assembly language, with the exception of macro viruses. Viruses can be playful or harmful (causing loss or corruption of data and/or services).

The life cycle of a virus is:
-Replication
-Activation

There are several kind of viruses. The most common of which are:

File Infector viruses - The most common virus class. It infects a file and hides within the code of another program. The infected program is an executable file which activates the virus and the program when run. The virus can then continue to run after the program is closed.

Viruses cannot exist in data/text files because the code within are not run. Instead, they are simply interpreted as ASCII characters. So even if a text file is infected, it would just appear to be a bunch of corrupted characters when open.

Boot sector viruses are stored in the boot sector of media (C/DVDs, diskettes, HDDs). It is executed when a computer first turns on, searches for the boot sector, and executes it. The virus is then loaded into the computer before, while or after the bootstrapper initializes the OS.

A boot sector virus can only be used to infect a machine if it is used to start it up. It cannot be used to infect a machine if it is introduced after bootup. A boot sector virus can then spread to other media while the OS is running.

A macro virus is a virus that makes use of powerful macro languages provided by certain programs (e.g. Word, Excel). These viruses execute each time the document is opened and may infect all future documents created with the application. The Melissa virus is an example of the macro virus, which causes the victim machine to mail out confidential documents with the Melissa virus attached to it.

A worm is a type of virus that can replicate itself but cannot attach itself to other programs. It is self-replicating and does not alter files but resides in active memory and duplicates itself. Mainly worms are used to use up objectives, but can also perform other tasks.

Viruses can spread through:
-Network
-Infected media
-Files from the internet
-Attachments
-ICQ/IRC
-P2P
-etc.

Antivirus softwares are used to remove malwares. They involve scanning and removing them. Anti-virus softwares can be:
-Virus scanning software
-Memory scanning software
-Integrity checkers
-Activity blockers

Virus scanning software can scan files and boot records. It may be able to notify the user, clean, delete, or quarantine the files/directories/disks affected. Virus scanners can look for known viruses, as well as new viruses.

Known viruses are found using signature scanning - a unique pattern of bits or binary data in the virus/program. The signature is like the fingerprint of a virus which is made as unique as possible for the identification of the virus.

Signature scanning may be able to find variants of existing viruses. False positives is relatively low. New viruses with different methods may not be detected as they may have different signatures.

Since antivirus softwares may not know the existence of new viruses, they make use of heuristic algorithms to scan. It is similar to signature scanning, but it looks for certain characteristics of the code (e.g. certain instructions that typically are not found in normal programs, such as modifiction of a driver, or modification of the registry).

If it finds a program that does unusual things, then it classifies it as a virus. However, it is more prone to false positives as legitimate programs (such as a Registry scanner) may be classified as malicious.

A Trojan Horse is a malicious, security breaking program that is disguised as something benign. An apparently useful program may have additional code to collect, exploit, falsify or destroy data.

A Trojan Horse is not a virus, in that although it does everything a virus can do, it does not attach itself to another program or attempt to replicate themselves. Trojans can be used for:
-Spying
-Relaying malicious connections (redirect connections to cause attacks to appear from another vector)
-Access restricted resources
-Launch a DDoS attack
-Capture keystrokes (Keylogger)

Trojans typically comprise of two parts:
-Server
-Client

The server is installed in the victim's machine, and the client is used by the attacker to connect to the victim's machine.

An example would be: Attacker makes the victim accept the Trojan server disguised as a game. The victim accepts and executes the file, causing the Trojan to be installed somewhere in the directory structure. The Trojan also modifies the Registry to cause it to be loaded automatically the next time the PC boots up. The attacker then connects to the Trojan to do work. The victim may also need to relay the IP of itself back to the attacker through means like DynDNS or email.

Defenses include:
-Do not download programs from dubious sites
-Do not open suspicious email attachments
-Prevent execution of ActiveX controls
-Don't accept programs in chatlines
-Check comments for files in P2P networks
-Use anti-spyware to detect and remove
-Configure a firewall to check for attempts to open ports
-Scan floppies and CDs before using

A Trojan may or may not be detected by Anti-Virus programs because they do things many other servers do, but famous ones like Sub Seven are definitely detected.

An example security policy for prevention of viruses can be:
1) All systems in the organization must be installed with firewalls and antivirus
2) Virus signatures must be updated
3) All media must be scanned for viruses before use
4) Programs downloaded from the Internet must be approved by the administrator before use

2011-02-26T13:08:00.003+08:00

NETSEC 06

Let's go back to the first chapter and discuss why LANs are connected to the internet. The most common reason is for company to sell goods or advertise products through their website. Companies may also better communicate with partners and employees. Employees would also be more productive due to the resources available in the Internet.

However, this exposes the company to dangers such as:
-Intrusions
-Port scanning
-DoS
-Undesired packets
-Connection to untrusted networks

A firewall is a device, or a system of devices, that is designed to prevent unauthorized access to or from a private network. It isolates the LAN from the Internet by implementing the company's security policy with respect to Internet connections.

Typically, a Router is needed to connect to the Internet. As it is the border of the network, a firewall is typically implemented in a router. The router is then known as a screening router (discussed later). The perimeter device (whether it is a dedicated firewall or a screening router) is the first line of defense, and typically provides logging functions as well.

There are three main types of firewalls:
-Packet filter
-Application gateway
-Proxy server

Packet filters look at each packet and checks it against the firewall rules (typically a table that is matched from top to bottom). If it matches a rule (either PERMIT or DENY), it is applied to the packet. Packet filtering is effective, fast, and transparent to users.

An application gateway provides the highest level of security. This involves inspection of the application layer data, such as in the case of NBAR, where it is able to defend against tunneled traffic (e.g. Port 80 but not HTTP inside).

A proxy server is an intermediate server that makes connections on behalf of users. It breaks the client-server model. Each connection would then need two handshakes: One between client and firewall, and one between firewall and target host.

Proxy servers conceal the internal addressing of the clients, and it allows inspection of the application layer data (i.e. able to inspect tunneled traffic), allowing them to filter viruses, malware and other malicious content. However, it adds latency and sometimes bandwidth problems as extra steps are required to establish connections.

How a firewall works depend on what its filters are based on and also the OSI layer it operates on. Firewalls typically work at Layers 2 and above (it is not possible, feasible or practical to filter based on Layer 1 characteristics).

A perimeter firewall, however, cannot defend against internal attacks or any other attack that doesn't go through the firewall such as social engineering. Clients can also bypass perimeter firewalls by dialing out through a modem or using a VPN tunnel (such as HotSpot Shield)

The most basic type of firewall is the packet filter firewall, which examines the headers and fields of the protocols to determine whether it is permitted or denied. The action to take is stored in an ACL (Access-Control List).

Ingress filtering and egress filtering denotes filtering of incoming and outgoing packets respectively. The direction is with respect to the LAN.

Packet filter can be placed on the network-level (router-based) or the host-level (host-based). Network-level firewalls are typically implemented in routers, making it a screening router. It protects against threats passing through it.

At Host-level, it is typically a personal firewall installed on each host to protect ONLY that host.

Information used in packet filtering include:
Source/Destination IP, MAC, Port, Direction of traffic, Protocol and fields/flags (such as TCP bits, and IP Fragments/DSCP options).

The information can be used to block access to specific websites (by IP, not domain name) and connection to specific ports (e.g. cannot use FTP). It can also be used to block certain hosts from entering. A lot of flexibility can be added by specifying the port.

The ACLs can be default allow or default deny. It is typically default deny, which means that traffic that doesn't match any policy is implicitly denied at the end.

Packet filtering has the advantage of being faster due to having low overhead. This results in higher throughput than other types of firewall. This is due to the fewer evaluations it needs to perform.

However, certain rules are complex to specify, test, and modify. Exceptions may be difficult to create and it is difficult to block services using dynamic ports. IP Spoofing attacks can also defeat this type of firewall to a certain extend (attacks that require one sided communication, for example, can use a spoofed source IP).

An IDS (Intrusion Detection System) is similar to a firewall in that it is used to monitor the network. However, it monitors based on things like signatures (specific pattern that indicate an attack) and anomalies (network activity deviation). An IDS does not typically prevent intrusions as it is not inline with the traffic (it works with mirrored traffic), so it would have to rely on a secondary device (such as a router) to block attacks. It is vulnerable also to single-packet attacks.

IPSs are IDS that are inline with the traffic, and can block attacks without the help of a secondary device.

Think of IDS as simply a burglar alarm and a security camera combined. It detects attacks, attempts to enforce policies, and provides an audit trail after the attack is done.

An IDS can detect if a worm is attacking the network, or if a system has been compromised. It can also alert the administrator in such a case. An IDS can be configured to detect activities that does not confirm to security policies. Finally, an IDS can provide an after-attack audit trail to see how far an attacker got and where it came from.

There are different ways to categorize detection:
False Positive - Test turns out positive (e.g. ALERT!) but it's false (there is no attack).
False Negative - Test turns out negative, but it's false (there is an attack).
True Positive - Test turns out positive, and indeed there is an attack.
True Negative - Test turns out negative, and there indeed is no attack.

Like firewalls, IDS can be host-based or network-based. If they are on a single host, they would have limited view of the entire network and cannot detect attacks (or can only detect to a certain extent) attacks targeted at another host.

A honeypot is a server that is used to attack hackers. They look like tempting targets like a database server but there is actually no service running there. It is used for distracting hackers away from real targets, and to study the attack methods. However, it may not be used to convict a hacker.

2011-02-26T11:46:00.002+08:00

NETSEC 05

Attacks can be classified into 4 types:
-Interruption (Availability)
-Modification (Integrity, Availability)
-Interception (Confidentiality)
-Fabrication (None, or Authentication/Authenticity)

Visually, the attacks look like this:
IMAGES OF THESE

These only categorizes Active Attacks, as at least one of the goals are harmed.

Attacks can be classified further. The most common class of attack is the MITM attack (Man-in-the-Middle). In MITM attacks, the attacker sits between the victim transparently. The attacker may then capture and/or modify the data before it reaches the victim. (As in a modification attack, or an interception attack).

Examples of MITM attacks are SSL Stripping and ARP Poison Routing (APR).

Another type of attack can be the Spoofing Attack. Spoofing attacks spoof a field in the protocol (such as source IP or MAC) to appear to be coming from a trusted vector. IP spoofing exists because certain services authenticate based on IP address. The existence itself is a vulnerability.

Defenses are to use 2FA, and to perform egress filtering to make sure that a router's originating LAN is not the source of spoofing. (e.g. Only allow source addresses that correspond to the company LAN to go out to the Internet).

Another type of spoofing can be web site spoofing, in case of a phishing attack. The attacker creates an authentic-looking page (such as a Bank Login Page) and lures the victim into the site by other means (e.g. Authentic-looking Email).

Finally we have the well-known ARP spoofing.

Another type of attack is the DoS attack (Denial of Service). DoS is primarily aimed at the Availability of the network/services. It is the simplest of attacks. Typically DoS attacks are done if the hacker fails to gain access to a computer (e.g. If he can't own it, no one else can).

DoS attacks are used to kill business competition. It is also used for revenge, for fun, or may be accidental (e.g. Janitor trips over a wire).

DoS attacks result in decreased productivity, lost revenue, and damaged reputation.

The types of DoS attacks are:
1) Consumption of network or computational resources
2) Disruption of configuration information
3) Physical damage

When it comes to consuming resources, typically a single attacker is not enough. It may sometimes take multiple attackers to bring a victim down. Therefore, we need to employ Distributed DoS or simply DDoS.

DoS relies on zombies or a botnet (infected hosts) which has either a server (listens for incoming commands) or a reverse client (connects to a server which it receives commands from) installed in it. It is difficult to trace who the real attacker is since the attack appears to be coming from multiple vectors, sometimes even from trusted hosts.

Session hijacking is the act of taking control of a session. Hackers get around sophisticated authentication schemes by taking over a victim's existing session AFTER it has been established and authenticated.

Password attacks are primarily brute force attacks. Brute-force attacks involve a systematic guessing of the password until a correct one is found. However, as most passwords contain common words, a dictionary brute-force attack (or simply, dictionary attack) can allow the attacker to resolve a password in a shorter time.

Passwords can be weak or strong. A strong password is one that is difficult to discover. Strong passwords are made up of:
1) Long strings
2) A large mix of character types in no apparent order (e.g. AbCd13!@ is bad, !A1C@b3e is good)
3) Words not found in dictionaries (Even H3ll0 may be bad, because of 1337 brute-force methods)

A weak password is the other way round:
1) Uses a word found in the dictionary, or a word
2) Uses very little mix of characters, such as all lowercase alphabets

The theory behind brute-force is that by definition, it is able to crack EVERY password encryption scheme EVENTUALLY. It is the feasibility of such an attack that makes it fail.

There are two types of brute-force targets. You can either brute-force the key (in case of encryption), or brute-force the plaintext (in case of hash).

Here's a practical example:
If a computer can try 72000 keys in a second, find the time it takes to brute-force...

The formula, by the way, is radix^characters/speed.

"test"

Since this is all in lower-case, then 26^4/72000 is the time-maximum (t-max) of the attack. On average, passwords are cracked in half the time-maximum (t-max).

"12345"

Since this only involves numbers, then it takes 10^5/72000.

"Passw0rd"

Since there is lower-case (26), upper-case (26) and numbers (10), the radix is 62. Therefore it takes 62^8/72000 to crack. Much longer.

"P@ssw0rd"

Now, there's the previous 62, AND all symbols. I don't know how many there are, but let's assume there's 16 symbols. You'll have 78^8/72000.

Sniffing is the easiest done in Token Ring networks, followed by Ethernet networks. Sniffing is the act of promiscuously inspecting every packet received by the NIC even if it is not intended for the computer. Sniffing can also be described as simply the act of intercepting packets traveling over a network. It is equivalent of eavesdropping.

A sniffer can be a program/device or the person using such a program. It can be used both for network management/troubleshooting (detect bottlenecks, programmers checking their program's packets, logging traffic) as well as malicious activities (stealing information off networks).

These three prerequisites must be met before sniffing can occur:
1) NIC must be in promiscuous mode
2) Hub is used to connect nodes (or ARP poisoning would be required)
3) Sniffer must be in the same LAN segment

By default, NICs are in non-promiscuous mode. That means that it will ignore packets not destined for its own MAC. However, NICs can capture and save packets not intended for itself when it is in promiscuous mode.

Information can be obtained through sniffing include: Email traffic, login usernames and passwords, and information useful for other attacks (including sequence numbers of TCP sessions). Any cleartext protocols such as HTTP, FTP, SMTP and POP3 can be sniffed.

Defenses for sniffing include:
-Replacing hubs with switches that can perform ARP snooping
-Physically check networks to ensure no unregistered hosts
-Use encryption to hide sensitive data

No matter how strong a password, once sniffed, is broken.

It is very difficult to detect sniffing because it is passive, but if the sniffing software makes use of the DNS for reverse-lookup, then it may be possible to identify suspicious hosts.

Phishing is a form of social engineering that makes use of fraudulent techniques to obtain sensitive information such as password and credit card details.

A web site phishing technique involves creating an authentic-looking site of a well-known company (such as a banking company). The phishers then create authentic-looking emails to trick recipients into accessing the phishing site. The victims would then divulge information as passwords, credit card numbers, usernames, and other things into a form on the website (e.g. When they try to log in).

Defenses for phishing include:
-Be skeptical of email with urgent requests
-Verify the emails with the company it "supposedly" came from
-Don't click on links in an email if it is suspicious
-Visit phishing guides like http://www.antiphishing.org

All the attacks described thus far are technical attacks. Technical attacks require the assailant to have good knowledge of computers, networking, programming and so on. His knowledge is used to identify vulnerabilities (he is the threat) and to carry out the attacks.

Non-technical attacks involve very little technical knowledge. These are the different non-technical attacks:

Dumpster diving - this involves digging into rubbish bins to look for sensitive data that has not been properly disposed off. Defenses include shredding of documents, credit cards and CDs.

Shoulder surfing - this involves looking over the victim's shoulders when he/she is inputting sensitive data into the computer (such as during logins).

Social Engineering is the most powerful attack in the world. It relies heavily on human interaction and is designed to exploit the natural helpfulness of humans. Social engineering works because people are not aware of the value of the information they hold, so they are careless in protecting it.

Social engineering can be performed through:
-appeal to Vanity (praises and such)
-appeal to Authority (appear to be an authoritative individual)
-eavesdropping (e.g. Shoulder Surfing, or eavesdropping for information to be used in the above two)

Social Engineering attacks can be classified under online and offline. (Or rather, technical or non-technical).

Emails containing tempting subject lines (e.g. "Nude XXX") but containing a trojan can be classified as an online social engineering attack. It can also cause damage by making people delete innocent operating-system critical files, such as the example given in the seminar where people are told to delete jdbgmgr.exe, claiming that it's a virus.

2011-02-25T20:51:00.003+08:00

NETSEC 04

We will now talk about the phases in an attack. Although the full attack process is done in 7 steps, the simplified one in the syllabus just involve:
1) Reconnaissance - Find out information about the network and gauge feasibility
2) Active Attack - Cause damage to the victim
3) Clearing Traces - Clear evidence of the attack

A simple way to find machines in a network is to do a ping (echo-request) scan. Replies typically mean a live host, while no reply may indicate a firewalled host or a down host.

We can also perform scans on specific hosts to find open ports, and also to find the network architecture and the operating systems involved.

A good utility is the Whois database which allows anyone to look up a domain. The contact information (name of authoritative figures) and various other information such as the registered DNS can be obtained.

The information found can then be used to perform social engineering attacks or phishing attacks. A good way to prevent this is to fill in only generic names, such as webmaster@domain.com.

We can also use search engines to find out information about the company network. We can also find the company website to see the different services they provide, and the different critical employees (to attack, or to impersonate).

Network scanning refers to the procedure for identifying active hosts on a network, either for attacking or assessment. This is the footprinting phase where the attacker creates a profile of the target organization such information such as DNS, email-servers and IP address range.

Tools, some free and some commercial, can be used to scan. The simplest, but the most inconvenient tool for scanning is the "ping". Ping stands for Packet Internet Groper and it works like a sonar, with a Echo-Request (ICMP 8) and a Echo-Reply (ICMP 0).

As mentioned, the lack of a reply may indicate a down host, or a firewalled host. Firewalls can be used to ignore Echo Requests, or to restrict Echo Replies.

We now go to the topic of Port Scanning. A port is a logical endpoint in a host, like a door to a house. As certain applications listen to specific port numbers, it can be used to identify the services running on a host. A host can have at most 65535 ports (excluding 0).

Services are referred to as daemons in Unix. Servers typically use a low port number >1024 while clients use port numbers <=1024.

Some common ports and services are:
FTP Active - 20
FTP Passive - 21
SSH - 22
Telnet - 23
SMTP - 25
DNS - 53
HTTP - 80
POP3 - 110

Port scanning is the systematic scanning of a host's ports to discover the services running on a target machine. Port scanning identifies the possible ways of connecting to a computer network. Port scanning can be legally used to manage a network, or maliciously used to look for vulnerabilities. Port scanning is usually one of the first things an attacker perform before penetration of a computer.

It gives an idea where to probe for weaknesses and is accomplished by sending certain crafted packets (such as a SYN packet) to each port and interpreting its reply (or its lack thereof).

In a SYN scan, if a port is open, the attacker would receive a SYN,ACK from the victim. If it's close, the victim will respond with a RST.

Port scanning itself is not illegal, and it's difficult to stop port scans (unless we employ an IDS or IPS). These are the different types of port scanning methods covered in lecture:

Vanilla - The scanner attempts to connect to all 65535 ports on the same machine.
Strobe - The scanner connects to only selected ports on the same machine.
Sweep - The scanner connects to the same port(s) on more than one computer.
Stealth - The scanner attempts to prevent the scanning from being recorded.
UDP - UDP variant of all the above methods.

Defenses for port-scanning can be to close all unnecessary ports. Firewalls and IDS can help block the scans. Changing the default port numbers can defend against Sweep scans (but Vanilla scans will still find it, though they wouldn't know what service is it). (To close ports, shut down the service using that port.)

2011-02-25T20:26:00.002+08:00

NETSEC 03

When TCP/IP was designed, there was no provision for security. Therefore, there was no automatic encryption, and neither was there encryption. The concern was only how to get data from one point to the other. The original Internet is small, and everyone trusted everyone else.

No automatic encryption means that data in packets are sent in cleartext. Anyone who captures this packet can see what's in it. It's like a postcard.

No authentication means that packets can have spoofed IP and MAC addresses and there is no way to verify them.

The designers did not implement security features because they did not expect that the mechanisms designed to handle service requests could also be used to expose servers to hijack attempts, compromise or mangling their data and services.

If asked, the vulnerability of TCP/IP is the lack of automatic encryption and authentication.

We'll now go through the different attacks starting from Layer 4. Layer 4 is vulnerable to things like SYN Flooding, Sequence Number Prediction and UDP Flooding.

A half-open connection is a three-way handshake with the missing third part. It lasts for a length of time (timeout) before it is torn down. Attackers may send many SYN requests to the victim using spoofed source IP addresses. The victim would reply to a spoofed location, and would allocate resources for each half-open connection until resources are exhausted.

Defense against SYN flooding can be to decrease the timeout, disable non-essential services, using IDS/IPS and to reduce the maximum number of half-open connections (thus using less RAM so it would not result in crashing).

Attackers can also hijack a connection through sequence number guessing. If they can predict the sequence number, then they can take over an existing TCP session. Packets from the victim would then be invalid as the sequence number would have been different by then. Sequence numbers can be predicted depending on the destination system.

The defense for sequence number prediction is to randomize the ISN.

Another attack is the UDP flooding in which millions of UDP packets are sent to the victim. The victim would not cope and would crash. As usual, the defense would be to implement IDS/IPS.

Now we move on to Layer 3 attacks. Layer 3 attacks focus mainly on the routing portion. Routers maintain a routing table to decide the route a packet goes to, and if we can attack that table, we can send packets to wrong destinations.

As RIP is not encrypted, hosts can sniff a router's routing updates as part of reconnaissance. RIPv1 also does not have an authentication mechanism, so hosts can query routers using RIP request packets. RIPv1 is also susceptible to forged routing updates and attackers can modify a network's routing table. This can be used to redirect an existing connection to somewhere else (for hijacking) or would be able to cause DoS due to wrong routing information. If the targeted system is a website, the victim may find themselves at a bogus site.

Defenses against RIP attacks may be to authenticate RIP packets, and to block updates about local networks. RIP packets can also be encrypted via an encryption suite such as IPSec.

ICMP's lack of authentication also makes it a candidate for abuse. ICMP messages such as forged redirects, unreachable or TTL-exceeded messages can cause a valid connection to be dropped. Using redirects, attackers can also cause hosts to use a bogus route to intercept or hijack a connection.

Redirects can be used to make unsolicited change to the host's routing tables, and the result is similar to a RIP attack. ICMP can also be used to perform DoS attacks either through the previously mentioned Unreachable and TTL-messages or even through sophisticated attacks like the Smurf attack.

A defense can be to disable processing of Redirects on hosts, disabling forwarding of Redirects on routers, and to check if ICMP messages from a host are consistent (ICMP-snooping).

Finally we go into the Layer 2 attacks. The most common Layer 2 attack is the ARP spoofing. The problem with ARP is that it allows Gratuitous ARPs which is essentially an ARP Reply sent without a ARP Request. Any system can create a Gratuitous ARP, and any system can spoof a reply to an ARP request.

If requested, the reply would overwrite an existing entry or add a new one if it does not exist. If not requested, an ARP Reply can only be used to modify an existing entry.

By providing a non-existent MAC address in the reply, or the wrong host, an attacker can perform a DoS or a MITM attack. The Gratuitous ARP must be sent continuously to make sure that the entry does not expire.

If Host A requests for Host B's MAC in an ARP reply, and no malice is involved, Host B would reply with his IP and MAC.

However, if Host B is offline, and Host C is up to mischief, then Host C would reply with Host B's IP but Host C's MAC. This would cause all packets for Host B to go to Host C as long as the ARP entry doesn't expire.

ARP Spoofing is simple and powerful, but it is limited to a local network. The attacker needs to be in the same LAN segment as the victim to perform this attack.

Defense for ARP can be to resolve through a centralized server, or to make switches perform ARP-snooping (verification of ARP requests/replies) and to enter the ARP entries manually.

Finally we go to the Physical attacks. Physical Attacks are usually tangible attacks such as cutting of a wire.

Defense for physical attacks would be to restrict access to important areas, to implement access schemes (e.g. card or PIN access), to lock up and hide equipment, and to implement surveillance (serves also as deterrence).

2011-02-25T19:50:00.002+08:00

NETSEC 02

We now go into the topic of Networking Protocols.

In the past, computers were standalone. They were not able to connect to the internet. All resources are only for a single computer. Data was transferred around in diskettes. However, this was not really productive.

A "node" refers to any entity that can access a network. A "node" can be referred to as a "device" or a "host". Clients, printers and servers are examples of such.

Back to the previous example, if a printer is connected to the computer, then only it can use it. However, if we connect the printer to a network through a hub or switch, we would be able to then share the printer among all computers connected to the network. This increases productivity and convenience.

There are many different types of network topologies such as Star, Ring, and Bus. The most common topology is the Star Topology, where all computers are connected to a physical hub or switch. Unlike the Ring topology where all nodes connect to each other in a closed ring, one malfunctioning node does not affect the network adversely. It is also easy to add and remove nodes. However, there exists a Single Point of Failure which is the hub connecting the rest of the devices.

If the connecting node is down, then availability would be affected. To defend against this, place the switch in a physical lockdown and add redundant switches linked together.

Networks can be classified with respect to size. From the smallest to biggest, they are:
-LAN - Typically in a building, or a level of a building, or a room.
-MAN - Typically a city or town
-WAN - Typically cross country

Note that there is a different between internet and Internet. An internet is simply a group of networks joined together. An Internet, however, is THE Internet. The Internet is actually an internetwork of internets.

An internetwork is a connection of 2 or more distinct (or probably dissimilar) networks. A router is typically used to connect these.

A hub/switch is used to connect nodes to form a network segment (a LAN), while a router is used to join LANs together.

We now look at Layer 4 of the OSI model where TCP and UDP resides. FTP, HTTP and Telnet use TCP, while DNS, TFTP and DHCP use UDP.

TCP is reliable because it is connection oriented. Its reliability is dependent on the handshakes and the need for acknowledgment. Before two hosts can communicate using TCP, they must establish the connection through a Three-Way Handshake like this:
Host 1 - SYN
Host 2 - SYN, ACK
Host 1 - ACK

Each TCP packet contains two sequence numbers: The Sequence Number and the Acknowledgment Number.

If a TCP packet has its SYN bit set, it is trying to establish a connection (or it is trying to synchronize with the remote/destination host).

ACK(b) = ISN(a)+1

A UDP packet has no such facility as it is connectionless.

Here's how the ISN would look like:
Client - SYN - ISN(c) = 500
Server - SYN, ACK - ISN(s) = 4237, ACK(s) = 501
Client - ACK - ACK(c) = 4238

Now let's talk about UDP. UDP is an unreliable service that provides no guarantees for delivery and no protection from duplication. The simplicity reduces overhead and may be adequate for certain services. Examples of services that use UDP are DNS and DHCP.

IP is used to route data between systems and across the network to ensure that data arrives at the correct destination. IP implements, among other features, addressing and fragmentation. IP is an unreliable and connectionless delivery service, so it would need to rely on the higher layer for these functions.

An IP address is a 32-bit number to determine the sender (source) and receiver (destination). Routing is the process of moving the packet from source to destination, usually done by a router. Routing is a key feature of the Internet because it allows the message to traverse networks eventually reach the target machine.

Routes keep changing so we need to have the latest routing information. The Routing Table is maintained through two main IGPs: RIP and OSPF.

ICMP is one of the core protocols of the TCP/IP suite. It is usually not used directly by end-users (with ping being the exception). ICMP is used for error reporting and control messages. Gateways and hosts use ICMP to inform a sender of certain problems, such as unreachables or, in the event that there is a better route, redirects. ICMP can also be used to test whether a destination is alive and reachable, and for reporting parameter problems in a datagram header.

The functions can be summarized into two things:
-Error Reporting
-Queries

Examples of Error Reporting:
-When a packet cannot reach its destination
-When a gateway does not have the buffering capacity to forward a packet
-When a gateway can direct a host to send traffic on a shorter route

Examples of Query
-Ping
-Traceroute (reliant on Ping)

The DNS is an essential part of the Internet because it is impossible for humans to remember millions of IP addresses. IP addresses are dynamic, so the DNS provides a dynamic directory of the usually the latest IP addresses. Certain services also rely on the DNS for resolution, such as the Windows Active Directory.

Internet is IP-based, and most operations end up using an IP address. The DNS is used for resolving a domain name into its corresponding IP address. DNS stands for Domain Name System and it is similar to a telephone book.

DNS keeps a list of domain names and their corresponding IP addresses. If a DNS does not know how to translate a domain name, it can perform either a Recursive or Iterative resolution.

In the recursive resolution, the DNS first asks the Root NS (usually have static IPs) which in turn asks the corresponding DNS servers responsible for the domain until an answer is found. The answer is then forwarded back the chain to the initial DNS which forwards to the user.

In Iterative, the DNS replies with the next possible DNS to ask, which the client continues to query until an answer is found. In this case, the client does all the work.

The Data Link layer defines the rules for sending and receiving information from one computer to another within a LAN. When we attempt to communicate with another host in the LAN, it must first know its MAC address. This is where ARP comes in.

IP is used for end-to-end communication, while MAC (a Layer 2 addressing) is used to communicate from point-to-point (i.e. Within the same LAN).

Each NIC has a burned in MAC address known as the physical address. ARP works by sending an ARP Request and getting the ARP Reply. Every host in the network receives the request, but only one host gets the reply.

If Host A of IP 10.0.0.1 and MAC A wishes to communicate with Host B of IP 10.0.0.2 and MAC B, it must first send out an ARP request (assuming ARP table is empty)

Host A sends out a broadcast request like this:
ETHERNET FRAME
Sender MAC (SMAC) - A
Destination MAC (DMAC) - FF-FF-FF-FF-FF-FF
ARP REQUEST
Sender Hardware Address (SHA) - A
Sender Protocol Address (SPA) - 10.0.0.1
Target Hardware Address (THA) - 00-00-00-00-00-00
Target Protocol Address (TPA) - 0.0.0.0

The reply then comes back as a unicast like this:
ETHERNET FRAME
SMAC - B
DMAC - A
SHA - B
SPA - 10.0.0.2
THA - A
TPA - 10.0.0.1

The physical layer is concerned with the transfer of information between devices in terms of bits, voltages, etc. A Hub is an example of a Layer 1 device, while a Switch is an example of a Layer 2 device. Router, of course, is a Layer 3 device. The layer here actually refers to the operation in that layer AND BELOW.

2011-02-25T19:16:00.003+08:00

NETSEC 01

Most companies have networks, and they connect their LANs to the WAN. These networks hold critical information about their businesses and provides the main means of transport for bulk and sensitive information.

Network security focuses to protect the company's assets. This can be either to gain competitive advantage or to retain customer confidence. A downtime in the network would result in negative publicity, loss of revenue and loss of productivity.

As mentioned, companies have to protect their assets. These assets range from trade secrets like scientific/chemical formulae, proprietary designs to financial information.

Companies place critical information in their networks even when they know hackers can steal this information because the benefits of networking outweighs the possible loss - It increases productivity and revenue among other things simply because it is convenient.

Network Security focuses on protecting three things:
Confidentiality
Integrity
Availability

Confidentiality ensures that information cannot be read or copied (if a person is ABLE to, but doesn't, it still is a confidentiality problem) by unauthorized parties. Confidentiality includes protecting data on a server or when it is travelling across the network. This data can be payrolls, passwords, or customer information.

Consequences of breach of confidentiality include loss of trade secrets and other data to competitors. May cause financial damage or embarrassment.

Integrity ensures that information cannot be modified by unauthorized people. Loss of integrity can be intentional or unintentional, and may even be due to human error. Improperly modified and inaccurate information can become useless or dangerous. Examples of breach of Integrity is the modification of your salary in the HR database, and hacking a website to add extra information.

Loss of integrity will result in customers or partners getting the wrong information, or may even lead to an availability problem (program cannot be run).

Availability focuses on preventing resources from becoming inaccessible. This applies not only to information, but also networking devices (such as routers). An attack against availability is called a "Denial of Service" attack.

Attacks against availability would cause loss of productivity, loss of customers and customer confidence.

From the seminar, we have the following scenario:
Lambda is a company that specializes in providing online financial services to its several thousand clients all over the world. It has more than 100 employees and has its own LAN with connections to the WAN. As a high-tech company, all its records, including customer information, economic data, its employee records are in electronic form and stored in several servers in its LAN.

First of all, they would need Confidentiality because only authorized people should have access to confidential data in the servers. They would also need Integrity because the records should not be modified without permission. Finally, availability is required to ensure the financial services among other things are accessible.

Attacks can happen from outside of the network (External Attack) or inside (Internal Attack). Internal attacks are more dangerous because the attacker has privileged information and usually more clearance that an external attacker probably would not have.

Security problems can be further classified into Threats, Attacks and Vulnerabilities.

Threats are activities or people that has the potential to cause harm to the system, whether intentional or not. A threat can be a nearby volcano, a virus, or a disgruntled employee.

A vulnerability is an inherent weakness in design, configuration or implementation of a system that makes it susceptible to threats. Locating an office near a volcano is a vulnerability (the volcano is the threat). A vulnerability can also be a software bug or a misconfigured firewall.

An attack is a vulnerability being exploited by a threat. There are two types of attacks: Passive and Active.

Passive attacks are usually used to collect information without anyone knowing it. It is very silent and difficult to detect and prevent. It is usually done in reconnaissance to be used for an active attack later.

Active attacks are the realization of the threats and involves active work done by the attacker. This involves changing transmitted or stored data, deleting corrupting or delaying transmissions. An active attack is much more destructive, but easier to detect. At least one goal is harmed in an active attack.

Direct lifting from the seminar: A security policy is a document that states in writing how a company plans to protect the company's physical and information technology. It is a "living" document, meaning that the document is never finished, but is continuously updated as technology and employee requirements change. An AUP is an example of a security policy which describes allowed vs disallowed behaviors.

There are two kinds of security policy:
Default-Allow - e.g. Everyone is permitted except Tom
This can be a Wiki site where everyone is permitted to visit and read except those banned.

Default-Deny - e.g. Only Tom is allowed
This can be an email account, where only a person is permitted to enter.

Examples of security policies are:
-No internet access for anyone except those authorized
-No installation of software on work computers without approval
-No downloading of software applications of any kind (including freeware)

Policies are useless if involved parties do not know and understand them, so it's important to publicize existing policies, changes, modifications and security alerts to the organization staff.

The Return on Investment is the consideration of how much is spent on protecting an asset vs the value of the asset itself. It is not advisable to spend a $10000 security suite to protect a $500 data. A general rule is to spend less than the value of the data being protected.

There are three types of backups:
1) Full backup - Perform a full backup of the system
2) Incremental Backup - Perform a full backup first, then backup things changed since the last backup
3) Differential - Backup things changed since the last FULL backup.

Security is a battle between convenience and security. Too much security means inconvenience, and too little security opens doors for attacks. A balance needs to be found.

There are three types of hackers:
1) Black hat - A hacker that break into networks with malicious intent (e.g. personal gain, money, fame).
2) White hat - A computer security analyst who specialize in penetration testing and other testing methodologies to ensure a company's security. Also known as "Ethical Hackers". Many white hats are former black hats.
3) Grey hat - A white hat hacker who sometimes acts illegally, and sometimes in good will. They do not hack for personal gain, but may commit crimes during the course of their contract.

Motivations to hack a network include:
1) Sheer pleasure, to overcome boredom
2) To command respect and admiration of fellow hackers
3) To kill off business competitors
4) To take revenge (as in the case of a disgruntled employee)

Script kiddies are someone who downloads programs to perform their hacking. They do not need much knowledge to execute attacks and generally do not have the capability to write such malicious programs themselves.

The Morris Worm was considered the first computer worm on the Internet. It exploded in November 1988, taking advantage of a vulnerability in UNIX. The program was written to gauge the size of the internet and did not do anything malicious.

The I Love You virus on the other hand sent mails with the subject of "I Love You" and an corresponding vbs attachment. The virus spread across the world over a 5 hour period. This, however, was malicious as it clogged web servers, overwrote personal files, and caused IT managers to shut down e-mail systems.

2011-02-25T18:30:00.002+08:00

NETINFRA 07

(Note that this is not an official Basic Draft article. It does not meet Basic Draft standards and will not be listed. If you've arrived through a search engine, please use the search function (top-left) to find a more suitable article).

Redundant network topologies are used to eliminate Single Points of Failure. In case of failure, a network is able to switch to a redundant link, making it more resilient and reliable.

Redundant links, however, lead to serious problems such as Broadcast Storms. A broadcast storm is when a broadcast packet loops around redundant links. As by definition, a switch forwards a broadcast Frame out of all links except the one it received it from, a broadcast frame received from one link will be forwarded back through the other, and it will come back again.

A broadcast storm is a result of a bridging loop.

As frames do not have TTL features unlike IP packets, it will continue to travel around indefinitely. As more broadcast packets are transmitted, more continue to loop and performance will continue to decrease.

A bridging loop may also cause multiple frame transmissions. In this case, if a switch's CAM table is empty, the first frame would be forwarded out of all ports except the one it came from. The second switch would do the same since its CAM table is empty. This problem is pertaining to Unknown Unicasts in bridging loops.

Another problem is the MAC address database instability. In case of multiple frame transmissions, as the second switch received the frame from the wrong port, it would record the source MAC at the wrong port as well. If the switches are connected by a hub, then it would receive the frame on two interfaces at the same time (one correct, and one due to the broadcast).

In large enterprises, redundancy is required, so switches are connected in switch blocks. In this case, a method of maintaining this redundancy, preferably automatic, is desired.

Spanning Tree is designed with the primary goal of maintaining a redundant - yet loop free - topology. It does this by placing redundant links in "blocking" state. Blocked ports can be changed to forwarding when required (e.g. The primary link goes down).

The first step of spanning tree is to elect a root bridge. Each bridge (from now on, switches will be referred to as bridges) possess a bridge-ID. This bridge-ID is formed by appending a priority and its MAC address. The default priority for all bridges is 32768, so by default, the bridge with the lowest MAC address will be the root bridge. This may not be desirable as a lower MAC address typically is assigned to an older bridge.

After the root bridge is elected, all switches calculate the best path back to the root bridge. This cost is a value assigned to links dependent on its media speed. The cost is a cumulative value specified in the BPDU received during the Listening stage. BPDUs also contain the BID and sending port of the originating bridge which is essential for the root bridge election.

This is the breakdown of the BPDU:
Root BID - Who does the originator think is the root bridge?
Root Path Cost - How far is it away from the root bridge?
Sender BID - What is the originator's BID?
Port ID - What port is the originator sending the BPDU out of?

The lowest cost path is the accumulated cost of all link on a specified path. Redundant Links not part of the lowest cost paths are blocked. (The bridge with the worse path back to the root bridge has the blocking port, or in other words, becomes non-designated). In the end, we would have a "tree" similar to an SPF tree with the root bridge as the root of the tree.

Here's a general guideline:
-One root bridge per network (or per VLAN in PVST+)
-One root port per non-bridge
-One designated port per segment

Some tips are:
-All connected ports on a root bridge is designated
-All non-bridge has a root port that is the closest to the root bridge
-On a blocking link, the bridge nearer to the root bridge is designated, while the bridge further away from the root bridge is non-designated.

These are the states a bridge transits when it boots up:
Blocking - All ports are blocking at first. When a switch first boots up, it would think that it is the root bridge and would attempt to switch all ports to designated. However, the ports still must go through the stages.

Listening (15 seconds) - The switch sends and receives BPDUs. This is the time where it finds out whether it is really the root or not. The information used here will be used to elect the root bridge, calculate the lowest cost paths, and so on. If the port is non-designated, it is put back to blocking state.

Learning (15 seconds) - If a port is designated, it will begin to listen out for MAC addresses to perform bindings in the MAC address table.

Forwarding - The port is ready and forwarding.

If a link goes down, the port stays at forwarding for another 20 seconds. This 20 seconds is known as the "max age" timer, which is a hold-down mechanism. This is the longest time a switch port can stay designated without a BPDU. Once this timer passes, the switch believes that there is a topology change and there will be a recalculation of the STP tree.

A new link will take 30 seconds to establish.

A dropped link will take 50 seconds to recover.

A converged STP topology is a topology where all ports are either blocking or forwarding.

2011-02-25T18:05:00.002+08:00

NETINFRA 06

(Note that this is not an official Basic Draft article. It does not meet Basic Draft standards and will not be listed. If you've arrived through a search engine, please use the search function (top-left) to find a more suitable article).

A trunk is a physical link that assumes the role of multiple logical links. In a VLAN switching environment, a trunk is a single point-to-point link that carries multiple VLANs. The purpose of a VLAN is to save ports between switches implementing VLANs.

Tagging protocols, such as 802.1Q and ISL, form an agreement to transmit different VLANs across a trunk link according to the available VLAN ports on both ends. A trunk link does not belong to a specific VLAN, though the native VLAN of a trunk determines where untagged traffic belong.

ISL is Cisco proprietary. 802.1Q is an IEEE standard that tags each frame with a VLAN ID as it crosses the trunk link. The tag is removed on the receiving end and forwarded accordingly.

End-user stations do not see tags as it is removed before they are forwarded out Access ports.

Trunk configuration must be done on both sides. The first step is to change it to a trunking mode. We would then have to choose a trunk encapsulation.

VTP is a Cisco proprietary protocol that is used to solve potential operational problems (due to human errors or otherwise). It ensures consistency of VLAN information across all switches and simplifies the complexity of managing and monitoring VLAN networks. (In other words, simplifies administration).

VTP is a messaging protocol (?) that makes use of trunk links for propagating addition, deletion and renaming of VLANs. VTP centralizes the administration of the VLAN. VTP messages are encapsulated in ISL or Dot1Q messages before it crosses the trunk link.

According to the seminar, VTP allows trunking of VLANs over mixed media (such as through FDDI). (But I believe this is not a VTP function, but rather a standard). VTP tracks, monitors and reports VLAN changes across the network. We would also have plug-and-play configuration when adding new VLANs, or adding new switches.

All switches must belong to the same VTP domain before they will exchange VTP information. A domain is made up of one or more interconnected switches that share the same domain name. Each switch can only be configured to be in one VTP domain. The domain name is stored in the VTP message as it is sent out of the trunk.

VTP operates in these three modes:
-Server
-Client
-Transparent

VTP servers can create, modify and delete VLANs. They are allowed to save the VLAN information. VTP servers are also able to propagate updates sent by other servers.

VTP clients cannot create, modify or delete VLAN information. VTP clients are not allowed to save VLAN information if they've made any changes (because they are not allowed to modify). VTP clients can receive, process and propagate incoming VTP messages.

VTP transparent switches do not synchronize its VLAN table with other switches. Transparent switches only forward VTP information to other trunk ports. It does not process the information. It maintains its own VLAN table and will not send out updates about its own table.

VTP advertisements are sent out via a multicast address so that all VTP capable switches receive it.

For some reason, the seminar notes go back to Inter-VLAN routing. So here goes:
InterVLAN routing traditionally require one physical link for each VLAN. So a switch with 4 VLANs would require 4 physical links, which is a wastage. Network designers begin to use trunking protocols such as ISL and Dot1Q to interconnect switches and routers. A subinterface is created on the link for each VLAN required. Each subinterface can be configured an IP address and a VLAN it represents.

2011-02-25T17:33:00.002+08:00

NETINFRA 05

(Note that this is not an official Basic Draft article. It does not meet Basic Draft standards and will not be listed. If you've arrived through a search engine, please use the search function (top-left) to find a more suitable article).

A VLAN is a LAN that may span multiple physical segments. This means that it is not restricted to a single switch.

VLANs are used to segment a network based on function, team grouping and applications without worry about the physical location of the devices.

Configuration and reconfiguration of switches are done through software and physical intervention (such as moving a cable from switch to switch) is not necessary.

If you have a three departments of 4 computers each, and a 16 port switch, you can simply segment the switch into 3 VLANs to connect them instead of having to allocate three switches. Routing between the VLANs can be done as per normal through a router (i.e. Three different interfaces of a router, each belonging in a different VLAN) or through a trunk link (discussed later).

A VLAN is like a LAN, in that it is a separate broadcast domain itself. Each VLAN also corresponds to a subnet (or network).

Using a router can actually allow you to implement security features such as ACLs on the interfaces (or subinterfaces). In the seminar, up to 255 VLANs can be supported on each switch. Some switches in real-life, however, can use up to 4096 non-extended VLANs.

Every switch port would be in the default VLAN of 1 when it is first taken out. According to the seminar, the management VLAN must be 1 and an IP address must be configured on VLAN 1. However, this is not true. Besides, it is best practice to use another VLAN as the management VLAN. Also, the default VLAN (1) may not be deleted or renamed. According to the seminar, VTP messages are sent on VLAN 1 (covered later).

The switch maintains a separate bridging table for each port. Learning, forwarding and filtering is done only against the table allocated to the VLAN.

Each port can be assigned to a different VLAN, and ports assigned the same VLAN shares a broadcast domain. VLANs can be statically assigned to a port or assigned based on the MAC address of the connected device (this can be done through AAA or VPMS).

Static VLAN assignments will cause any device connected to the port to belong to that configured VLAN. Static VLANs are easily Administered via GUIs. Security is easily enforced and VLAN traffic leakage is uncommon. It is also easily controlled across the entire network. This is used when switch ports cannot be switched by users, a good software can be used to manage the ports, and when the overhead of administration of Dynamic VLAN outweighs the benefits.

Dynamic VLAN by MAC addresses adds flexibility at the expense of administrative overhead, performance and scalability.

Another type of VLANs not discussed is the Protocol Based VLAN. According to the seminar, it is the same as Dynamic VLAN except that it works based on IP and it is not common anymore due to DHCP. (I am not convinced.)

Advantages of VLANs:
-Less expensive than routers for broadcast segmentation
-Allows nodes to move logically rather than physically
-Improves security
-Able to segment a switch into multiple switches

Limitations of VLANs:
-May require extensive planning and design
-VLANs are proprietary, single vendor solutions (What? For VLANs to cross, one simply requires the switches to support 802.1Q. It's only the extra features that are proprietary. Where did they get this text from?)

When a VLAN is deleted, ports associated to that VLAN becomes inactive. The port remains associated with the deleted VLAN until assigned to a new VLAN.

2011-02-25T16:45:00.002+08:00

NETINFRA 04

(Note that this is not an official Basic Draft article. It does not meet Basic Draft standards and will not be listed. If you've arrived through a search engine, please use the search function (top-left) to find a more suitable article).

In the past, all LANs are shared. There was the bus topology which is similar in behavior to the hub. In this case, every Unicast packet is sent out to all connected interfaces (except the one where it came from), as if it's a broadcast. (Of course, that's where the MAC address comes in to determine who it is for).

In a hub, there is only one collision domain. Which means to say, communications is half-duplex and only one device may communicate at one time. If two devices begin transmission at the same time, then there is a collision. That is why we need CSMA/CD to detect and resolve collisions. If two hosts attempt to communicate at the same time, then there would only be 50% bandwidth for each host on average.

When a collision is detected, a jam signal is generated, and both parties wait for a random amount of time before retransmission.

In a full-duplex environment, both hosts can communicate at 100% of the link's bandwidth. Which means to say, in Fast Ethernet full-duplex, hosts can send and receive at 100MBps, resulting in 200MBps gross throughput. There can be no collisions in a full-duplex environment.

Latency is the time it takes for a packet to travel from source to destination. Sometimes, Latency may be the SRTT (Source Round-Trip Time) which is the time taken from source to destination and back.

Segmentation of the collision domain can be performed through switches (or traditionally, bridges). Bridges connect to hubs which in turn connect to devices. Each port of the bridge (or switch) is a collision domain. As the number of users decrease in each collision domain, so will the collisions.

Switches work like bridges, in which they maintain a list of Layer 2 addresses called the CAM table. The CAM table is then used to determine whether a frame should be forwarded out of a particular port. Bridges are software based, however, so they increase the latency when sending across different segments.

The segmentation of collision domains by either bridge or switch (but only the switch was mentioned) is known as microsegmentation. In microsegmentation, the switch is seen to create point-to-point segments between two communicating hosts. In a switch, all stations are given dedicated bandwidth, and there is almost no collision.

Ethernet Switch latency is the time it takes for a frame to enter and exit a switch. This is said to be negligible as switches perform switching at "wire speed", but as traffic increase, the switch may need to buffer some of the request resulting in this latency. The latency may also be a result of the switch making decisions on which port to forward a frame out of.

Now, even though switches segment collision domains, they do not segment broadcast domains. That is to say, a broadcast will still reach everyone connected to the switch. A normal switch accounts for one LAN, so we would need to use Routers to separate hosts into multiple LANs. This is the segmentation of Broadcast Domains through the use of Routers.

As we recall, there are three modes of IPv4 communication:
Unicast - One to One communication
Broadcast - One to All communication (MAC address is filled with binary 1)
Multicast - One to Group communication

Frame Forwarding refers to a Frame being forwarded out of a particular port. Frame Filtering refers to a Frame being prevented from exiting a particular port. Switches and bridges performs both.

From this point onwards, switches and bridges will be used interchangeably unless specified.

Switches perform Frame Forwarding and Filtering only if it knows enough information to do so. This information, most importantly the MAC addresses associated to the ports, are stored in the CAM (Content Addressable Memory) table. The CAM table is actually the MAC Address Table being stored in the CAM. Switches can perform filtering based on any Layer 2 field.

Initially all MAC address tables are empty. The switches need to learn MAC addresses through the Source MAC address of each Frame. Frames are Forwarded out of all ports (except the one it came in from) if the Frame is a Broadcast, Multicast or an Unknown Unicast.

A switch would only Forward a Frame if it determines that the destination belongs to a different interface from which it came from. If the destination MAC belongs to the port it came in from, the Frame is said to be Filtered.

Let's look at an example CAM Table:
MAC - Port
A - 1
B - 3
C - 4

Assuming that A sends a packet to B. It does not need to learn A because it already knows it. The since it knows the destination, the Frame is forwarded out of port 3.

If A sends a packet to D, the switch would check its CAM table and realize that it doesn't know the destination. The Frame is forwarded out of all ports except the one it came in from.

When D replies, it learns D's MAC address from the interface the reply came in from. Since the destination of the reply is A and it is known, it is forwarded only out of port 1.

The end result would look like this:
Let's look at an example CAM Table:
MAC - Port
A - 1
B - 3
C - 4
D - 2

Switches can perform symmetric switching (switching between interfaces of the same speed) or asymmetric switching (switching between interfaces of different speeds). A real-life example of symmetric switching is through the use of the Gigabit link to connect to an uplink switch while all other computers are connected to Fast Ethernet ports. Asymmetric requires memory buffering.

Memory buffering can be port-based. Port-based buffering is done for the INCOMING port. Each incoming frame is queued. If the queuing mechanism is FIFO, it is possible for a single frame to cause blocking when the destination port is busy.

Another type of buffering is the shared buffering where all frames use a common memory buffer. Frames in the buffer are linked to the appropriate destination port. This helps balancing between ports of different speeds (In what way? Not explained?).

There are also two ways of forwarding frames. A cut-through switch forwards a Frame immediately after reading the destination MAC. This results in lower latency. However, there are no error checking.

The other way is the Store-and-Forward method, which requires a switch to fully receive a Frame before it is processed. This allows proper processing of the Frame, such us for CRC checks. The Frame is fully copied onboard, checked for CRC, determines the output interface (or interfaces), then forwards it. This is the most reliable method but it results in the highest latency.

Another type of switch is the Fragment Free switching which checks for the Source Address as well as the Length. It filters most errors and checks for collision. (This is the only thing explained about this method).

When we are determining bandwidth in shared environments, remember to count the switch as a device (i.e. If there are 10 computers, divide the bandwidth by 11).

2011-02-25T16:02:00.002+08:00

NETINFRA 03

(Note that this is not an official Basic Draft article. It does not meet Basic Draft standards and will not be listed. If you've arrived through a search engine, please use the search function (top-left) to find a more suitable article).

Load balancing is the act of balancing a stream of packets for a network over different paths. The paths can be derived statically or using a dynamic protocol.

Here's the decision in pseudocode:

if (sameNetwork())
{
    if (sameAD())
    {
        if (sameMetric())
        {
            loadBalance();
        }
        else
        {
            useBetterMetric();
        }
    }
    else
    {
        useBetterAd();
    }
}
else
{
    useRoute();
}

Load balancing can be done per-packet or per-host. Per-packet splits the stream of packets towards the same host over different paths. Per-host allocates each stream of packet to different hosts a different path.

Routing Loop problems such as the Count To Infinity occurs when neighbors are not immediately updated when a route goes down. The neighbors may then re-advertise the downed down back to the originator, resulting in the originator believing that there exists an alternate route through the neighbor. The neighbor still thinks that the route exists through the original router, therefore resulting in a loop. The original router then re-advertises back to the neighbor at a higher metric. The higher metric path replaces the previous one. The neighbor then re-advertises back to the originator, and it replaces the path. This will cause the hop-count to count up.

The crude solution to fixing Count to Infinity is the restriction of the hop-count to a maximum of 15. That way, if there really is a loop, it would only count to 15 and be dropped.

According to the seminar, these are the three conditions that may result in a routing loop:
-Alternate Routes
-Slow Convergence
-Inconsistent Routing Tables

Another way to solve the Count to Infinity is to prevent updates about a network from being sent to interfaces where you learned that network from. This means, if you learned about Network A from F0/0, you will not send information about Network A out of F0/0.

Split horizon would reduce incorrect information as well as bandwidth overhead.

Route Poisoning is the poisoning of routes by setting an originated route's Hop Count to 16 if the connected interface goes down. (This is done by the router originating the network).

Poison Reverse is another form of Split Horizon, but it does not reduce bandwidth overhead. This mechanism simply causes information going back to the originator to be marked with the hop count of 16. (e.g. If you learn of Network A through F0/0, then you would advertise Network A as Hop 16 out of F0/0).

Triggered update, as used in LS, can also be used in DV. This causes any information to be sent immediately after a topology change. These triggered updates are sent with poisoning (i.e. They are sent with a hop-count of 16) to cause the routes to be dropped immediately without waiting for the hold-down timer to expire.

Hold-down timers can also be a route-prevention mechanism. The hold-down timer is always activated and reset whenever an update is received. While the timer is counting down, an update from another neighbor with a poorer metric is ignored. An update from another neighbor with a better metric would cause the update to be installed in the routing table and the hold-down timer would reset.

RIP uses the following mechanisms to reduce/avoid Count-down to Infinity:
-Hold-down timers
-Triggered Updates
-Poison Reverse and Route Poisoning
-Split Horizon
-Maximum Hop-count

RIP performs round-robin load balancing only. Which means to say, RIP does per-packet load balancing for a particular destination.

Routing Protocols can be used to advertise and receive default routes as well. As like all Routing Protocols, dynamic routing can be overridden with static routes by adjusting the AD.

The Metric of IGRP is 10,000,000Kbps/(Smallest Bandwidth in Kbps)+(Sum of all Delays in microseconds/10).

IGRP uses Hold-down, Split Horizon and Poison-Reverse.

2011-02-25T15:07:00.002+08:00

NETINFRA 02

(Note that this is not an official Basic Draft article. It does not meet Basic Draft standards and will not be listed. If you've arrived through a search engine, please use the search function (top-left) to find a more suitable article).

Routing is the process a router goes through to forward a packet towards a destination network.

Switching is the process a switch goes through to switch a frame out of the correct interface (or interfaces in case of a broadcast).

A router determines the best path to take through the destination IP address (or any Layer 3 address) using the Routing Table.

An Ethernet switch determines the interface to forward frames out using the CAM Table.

For routers to make a proper decision, it must learn routes. These routes are stored in a routing table. Routes can be static (manually entered by an Administrator) or dynamic (learned through a Routing Protocol from other routers).

A Routed protocol is a protocol that is routed by a Routing protocol.

Here is a list of example Routed protocols:
-IP
-IPX
-DECNet
-AppleTalk

A routed protocol basically worries about only the encapsulation of the packets and the fields within the encapsulation. It is concerned with storing information used by routers to make decisions. A routed protocol is routed through the Routing Table.

A Routing protocol is a protocol that routes the Routed protocols.

Here is a list of example Routing protocols:
-RIP
-IGRP
-EIGRP
-OSPF
-IS-IS
-BGP

A routing protocol supports a routed protocol. It is concerned with populating, updating and maintaining the Routing Table with information to correctly move the routed protocols around.

Routers can support multiple routing and routed protocols. In this way, they are capable of supporting many different types of networks. Each routed protocol, of course, has its own Routing Table relevant to it.

From the seminar, a Static route is a programmed route that the Administrator enters into the router. A Dynamic route is a route that a routing protocol adjusts automatically for topology or traffic changes.

A Static Route is a fixed path from source to destination. It is manually entered and so therefore must be manually updated.

Static route can be used to reveal information about hidden networks without entering it into the routing protocol.

Static route can also be used to specify stub networks - Networks that can only be accessed via one path (this is to avoid overhead related to dynamic routing).

Static routes can be entered from Global Configuration context using:
ip route NETWORK_ADDRESS SUBNET_MASK [OUTGOING INTERFACE|NEXT-HOP ADDRESS] [ADMINISTRATIVE_DISTANCE]

When specifying static routes, the administrative distance is an optional parameter to specify how reliable a route is. The lower the administrative distance, the more reliable a route is perceived to be. If there are multiple paths to the same network, then the one with the lower administrative distance is chosen. A static route can have administrative distance of 0 or 1 depending on whether an outgoing interface or a next-hop address is specified, respectively.

As an administrative distance is an 8 bit value, it can range from 0 to 255.

Here's a list of the common Administrative Distances:
Connected - 0
Static Outgoing Interface - 0
Static Next-Hop - 1
EIGRP - 90
IGRP - 100
OSPF - 110
RIP - 120
Unknown - 255

Using this Administrative Distance concept, we can create backup routes using static routes by specifying a static route with a lower administrative distance for an existing route.

For example, if you have an existing RIP route of 120 AD, then we can create a static route of 121 AD. The static route will be taken if the RIP one fails.

A default route is a special route that is taken when the routing table does not contain an entry that matches the destination address requested. To declare a default route, simply use 0.0.0.0 for both the NETWORK_ADDRESS and SUBNET_MASK in the "ip route" command.

This is typically used by routers to forward Internet-bound traffic to the ISP Provider Edge routers.

Dynamic Routing Protocols are used to automatically create, update and maintain tables when there are network:
-failures
-reconfiguration
-growth

Dynamic Routing finds all possible routes, and puts the Best Route into the routing table. Routes are removed when they are no longer valid.

A network is said to have converged when all routers operate with the same knowledge, and routing updates have stabilized. Fast convergence is desirable.

If a Dynamic Routing protocol finds two equal paths, both paths would enter the routing table and they would perform load balancing over them. The Dynamic Routing protocol defines the set of rules routers follow when exchanging information.

The two goals of Dynamic Routing protocols are:
-Maintenance of a routing table
-Timely distribution of knowledge (routing updates)

There are three classes of Distance Vector routing protocols learned in the seminar.

RIP and IGRP are Distance Vector protocols. DV protocols determine the distance and direction to the networks. DV protocols typically send broadcast periodic updates (30 seconds RIP, 90 seconds IGRP) in the form of the entire routing table to neighbors (RIP version 2 uses multicasts instead; not tested). It accumulates distances found in the updates (e.g. If it's 5 hops away from the neighbor, it's 6 hops away from itself). It does not know the exact topology, and it only knows what its neighbors know. Typically DV are slow to converge. The updates are the only keepalives.

OSPF and IS-IS are Link State protocols. LS protocols learn the whole network topology, and find their way around by computing the cost to get to each network using the SPF algorithm. The lowest cost routes are used. LS uses triggered updates and send only the required updates in the form of LSAs (containing many LSPs, one for each route). Every time an update occurs, every router in the domain recomputes the SPF tree with itself as the root. It also uses Hello packets as a keepalive.

Link State requires more processor and memory, but is more bandwidth efficient in the end (the seminar says that Link State is bandwidth inefficient?).

Metric is what a router uses to determine what path is better. In case of the above examples, Hop Count and Cost are the metrics. Other metrics include Bandwidth, Delay, Load, Reliability and Ticks.

Advanced DV (referred to as Hybrid in the seminar) is a class of Routing Protocols that use DV metrics, but exhibit LS behaviors such as the maintenance of a Topology Database, the use of multicast Triggered Updates and Fast Convergence. As Advanced DV doesn't need to compute an SPF tree, but instead (in the case of EIGRP) uses more efficient algorithms such as DUAL, it is more processor efficient. It also does not need as much memory as the LS protocols. As with LS, other than the initial flooding, it is very bandwidth efficient. It uses the Hello as the keepalive mechanism.

Some characteristics of RIPv1 are: DV, Uses Hop Count, Broadcasts Updates every 30 seconds, Route Timeout 180 seconds, Hop Count cannot be more than 15, Classful.

Some characteristics of IGRP are: DV, Proprietary, handles Complex Topologies well, uses Bandwidth and Delay (can be configured to include Load and Reliability), Broadcasts Updates every 90 seconds, Classful.

Some characteristics of OSPF are: LS. (That's all?)

Some characteristics of EIGRP are: ADV (or "Hybrid"), Proprietary, keeps Successors and Feasible Successors for backup routes.

An AS is a group of networks under a common administration, and sharing a common routing strategy. IGRP, EIGRP and BGP requires AS numbers, and they must be the same for neighbors (applies to IGRP and EIGRP only) to exchange information.

IGPs are protocols used within an organization. Examples are RIP, OSPF, IGRP, EIGRP, IS-IS. The AS numbers for IGRP and EIGRP can be arbitrary as long as they are the same for devices meant to exchange information.

EGPs are protocols used to connect networks of different organizations together. Examples are EGP (a routing protocol succeeded by BGP, not referring to the class) and BGP. AS numbers for each organization in this case must be unique and assigned by an Internet authority.

2011-02-25T13:24:00.004+08:00

NETINFRA 01

(Note that this is not an official Basic Draft article. It does not meet Basic Draft standards and will not be listed. If you've arrived through a search engine, please use the search function (top-left) to find a more suitable article).

I know I shouldn't be doing this but I'll be doing it anyway. I'm Basic Drafting NETINFRA. This is so far the most badly polished subject I've ever encountered. I am already having a half time agreeing with certain things taught, let alone Basic Draft about it, but I'm doing it anyway, because I wish to get this subject over and done with.

It's weird that Basic Draft is now becoming a verb.

Alright let's all begin with IP Addressing. I'm sure I don't need this and neither should anyone else, but let's go! (I'll be brief)

An IP address is a 32-bit value that is represented in 4 dotted-octets (that is to say, 4 groups of numbers that are 255 each separated by dots). An example of an IP address is... Uh... 192.168.1.1.

Each IP address is combined with a subnet mask. A subnet mask is combined with the IP address to determine these two things:
1) What is the network or (in the case of classless addressing - subnet) address?
2) What type of address is it? (Network? Host? Broadcast?)

IP Addressing is used in Layer 3. Like anything else in the OSI layer, a higher layer abstracts the lower layers. In other words, it is independent of the actual physical device and standards being used in Layer 2 and 1.

IP Addressing is a logical and hierarchical addressing standard. Like hierarchical folder structures, IP addresses are arranged as a tree.

Here's a breakdown of the operations that you can perform on an IP Address and Subnet Mask:
Subnet Address = IP & Subnet Mask
Broadcast Address = Subnet Address + Increment - 1
Increment = Value of lowest set bit in Subnet Mask
Number of Hosts in that Subnet = Increment - 2
Number of Subnets = 2^(Classful CIDR - CIDR) - 2
Range of Host = (Subnet Address + 1) to (Subnet Address + Increment - 2)

Okay I think this is unnecessary so I'll skip faster from now on.

The class of the address depends on the highest order bits of the IP address:
Class A = 0 = 1-126 (127 is reserved for Localhost)
Class B = 10 = 128 - 191
Class C = 110 = 192 - 223
Class D = 1110 = 224 - 239
Class E = 1111 = 240 - 254

These are the various classful subnet masks and their CIDR:
Class A = 255.0.0.0 = /8
Class B = 255.255.0.0 = /16
Class C = 255.255.255.0 = /24

CIDR is simply the number of contiguous 1's in a subnet mask.

Each network/subnet represents a broadcast domain (the area of extent a broadcast can travel). Everything in a network/subnet would receive a broadcast from that subnet.

Among other things, networks can be broken into subnets to increase broadcast domains. Subnets also allow an organization to be better structured, e.g. 192.168.1.0/24 can be broken into 4 subnets (or traditionally 2) of 192.168.1.x/26. Each of these subnets can be assigned to a department.

Okay I'm too lazy to talk about subnetting anymore. I'll just go through one worked example and that's it.

Suppose that I have a network 172.16.0.0/16 and I have 50 subnets that I want to assign. Each subnet is expected to have only up to 500 hosts. Ensure minimal borrowing of subnet bits.

The minimum number of borrowed bits is roundUp(log2(50+2)), which is about 6.

6 subnet bits would give me (2^6)-2 = 62 subnets.

The default mask is /16, so the new mask is /22. The increment of /22 is 4, so subnet 5 would be:

172.16.(5*4).0/22 = 172.16.20.0/22

The host range would be 172.16.20.1 to 172.16.(20+4-1).254 = 172.16.23.254.

Each subnet would have 2^(32-22)-2 = 1022 hosts, so it satisfies the 500 hosts requirement.

Okay we don't need any more examples, let's move on to WAN and Routers.

We first classify network devices by DTE and DCE. As taken from Article CCNA 9:

DTE (Data Terminal Equipment):
-Computer
-Router

DCE (Data Communications Equipment):
-Switch
-Hub
-Modem or CSU/DSU

The different cable implementations can be found in CCNA 9.

Here's a quick summary:
DTE-to-DTE = Cross-over
DCE-to-DCE = Cross-over
DTE-to-DCE = Straight-through
Console Port = Rollover

LAN uses Cat5e UTP/STP while WAN uses Serial.

Here are the various WAN devices if the examinations ask for it:
-Router
-WAN Switch (such as for Frame Relay)
-Modem or CSU/DSU
-Communication Server (used for concentrating DIDO (dial-in/dial-out) connections, such as a RADIUS server with multiple modems)

As a NETFUND review, WANs operate over large geographical area, allows access through serial at lower speed, and provide full and part-time connections (always-on vs on-demand).

WANs are typically used to connect sites together. Exchange of information between these sites are done through WAN devices (listed above).

Routers are used to interconnect LANs. Typically routers also have Serial interfaces to connect to a WAN.

Unrelated, but stated in the text, the different roles a router in a OSPF domain can take are:
- Internal Routers
- Backbone Routers
- Area Border Routers
- Autonomous System Boundary Routers

This is definitely not tested because it is not supposed to be in the seminar in the first place.

If you want to learn about Link State protocols, visit CCNP BSCI 05.

WAN switches exist in a WAN cloud to provide switching at Layer 2 to provide transparent connectivity. They are operated by the ISP.

Modems (Modulator/Demodulator) are used for Digital to Analog conversion typically for transmission over a voice-grade line.

CSU/DSUs are used for connection to a Digital facility, such as a Frame Relay WAN switch, or a T1 leased line. The CSU (Channel Service Unit) is used for that connection, and the DSU (Data Service Unit) is used for diagnostic functions pertaining to the telecommunications line.

In a normal real-life WAN scenario, the Router is a DTE equipment, while the CSU/DSU is a DCE end.

WAN standards are scattered through OSI Layers 1 and 2.

The physical layer describes the WAN's Electrical, Mechanical, Operational and Functional aspects. Examples of physical layer WAN technologies are the various cable implementations and connection types. The DTE and DCE definitions are also WAN standards.

The DCE end of each serial connection sets the clock rate. The ISP's CSU/DSU is the demarcation point, where responsibilities of connectivity between the ISP and customer are separated.

If asked during the examination, these are the various Layer 1 WAN connection types:
-EIA/TIA-232
-EIA/TIA-449
-V.24
-V.35
-X.21
-HSSI
-G.703
-EIA-530

Also, if asked, here are the world's main WAN standards definers:
-IETF
-IEEE
-ITU-T
-ISO
-EIA

The Layer 2 WAN standard describes encapsulation protocols. These protocols are the language spoken between two connected devices. An example of a LAN protocol is the Ethernet.

If tested, Layer 2 WAN protocols provide services for these connection types:
-Multi-Access Switched
-Point-to-Point
-Point-to-Multipoint

(These three things are badly categorized anyway, since Multi-Access Switched is how a Point-to-Multipoint connection is implemented.)

The WAN Layer 2 encapsulation exists between the WAN interfaces of two connected routers.

If tested, here are the various WAN protocols:
-ISDN
-PPP
-Frame Relay
-HDLC

Here are the various (very incomplete and misleading) definitions to memorize in case tested:

HDLC - Default Cisco Encapsulation, Proprietary, supports Point-to-Point and Point-to-Multipoint, and uses minimal overhead

Frame Relay - Uses High Quality digital switching facilities, requires error checking at Data Link layer, uses Simplified Framing with no error correction, is Connectionless, and Routing and Switching is performed at the Data Link Layer (This whole chunk makes no sense. Please memorize it)

PPP - Developed by IETF to replace SLIP, can support Analog circuits (such as for Dial-Up), provides Error Correction, able to encapsulate several routed protocols, can check for Link Quality during establishment, supports PAP (Password Authentication Protocol) and CHAP (Challenge Handshake Authentication Protocol).

(In my opinion, if that's the way the school is going to teach the three encapsulations, I rather they not teach it.)

A dedicated line is a single line that is established end-to-end that is dedicated to only two sites. Examples of dedicated line technologies are T1/E1/T3/E3, xDSL and SONET. It is a point-to-point implementation. PPP and HDLC can be used over this.

A circuit switched connection is a connection routed over an analogue circuit such as a voice-grade telephone service. PPP, POTS Dial-Up and ISDN can be used over this.

A packet switched connection is a connection routed over digital facilities, such as a Frame Relay cloud (consisting of L1 Frame Relay switches). Frame Relay encapsulation is used over this.

A cell switched connection is a packet-switched connection that requires fixed-size padded cells to be transmitted. Examples are ATM and SMDS.

The above categorization was taken from the Lecture slides (with some extra explanation put in by me). Notice that ISDN can also be dedicated, and POTS is not an encapsulation. The whole slide is confusing and groups unrelated categories together. Right now, just know what technology is related to what type (e.g. Dedicated/Circuit/Packet Switched).

Dig up my CCNA articles to learn how the encapsulations can be used.

Now let's talk about Routers. Routers are Layer 3 devices designed to interconnect networks of different types (LANs/WANs/MANs). A router provides routing of packets (not switching of packets as described in the slides) and determines the best path (i.e. Path Determination).

Router needs a DCE device to connect to WANs (either an external DCE device or a built-in one like a CSU/DSU card). In a LAN environment, we can simulate WAN connections between two routers using a Cross-over Serial Cable (or professionally referred to as a NULL Modem Serial Connection). It is made using a special back-to-back serial cable with a DCE and DTE end. The DCE end requires the "clock rate" command to be issued (i.e. It issues/provides the clocking signal).

For a piece of data to be successfully transmitted, it must have two types of addresses: Layer 2 and Layer 3 addresses. The Layer 2 addresses changes point-to-point, it determines which is the next routing node the frame goes to. The Layer 3 address remains the same through the whole transfer, as it determines the initiating and receiving end.

Examples of Layer 2 addresses are:
MAC, Frame Relay DLCI, and HDLC LLC.

Examples of Layer 3 addresses are:
IP, IPX, DecNET, AppleTalk

Data is encapsulated as shown:
|Layer 2|Layer 3|Layer 4|Data|Layer 2 Trailer|

In the Layer 2, there typically exists protocol-dependent fields like Source/Destination MAC and Dot1Q header. The trailer is used for error detection and correction. If data is encapsulated at Layer 2, it is referred to as a Frame.

In the Layer 3 encapsulation, we would have things like IP address and IP Precedence (in case of IP). If data is encapsulated only up to Layer 3, it is referred to as a Packet.

There of course is a Layer 4 which contains typically TCP or UDP information such as Source and Destination Ports.

2011-02-24T11:14:00.006+08:00

CAOS 11

The purpose of Main Memory Management is to maximize the Degree of Multiprogramming without sacrificing stability. We previously dealt with execution of processes that are WHOLLY in memory. However, much of the process loaded in memory is actually not required at that point.

Recall that in the Segmentation example previously, parts of the program (such as Subroutine, Stack, Symbol Table, Functions, Main Program) are divided into segments to be stored in the memory. However, at any given point, would ALL of those segments be used? Unlikely.

There are wastage of memory space, especially in things like overallocation (integer allocated while only byte is required, 1000 index array allocated while only 5 indexes are actually used).

To allow a process that is larger than the available memory to be executed, we use a technique known as Overlay. Overlay only keeps in memory instructions and data that are needed at that given time. The overlaying method is handled by the Overlay driver. Using overlays would cause a program to load faster (because not all memory needs to be loaded at the same time) but would run slower (because I/O would be required to switch parts in and out).

Overlay is a type of Virtual Memory scheme. Virtual Memory allows execution of processes that may not be completely in memory. This means that programs would no longer be constrained by the amount of RAM and the Degree of Multiprogramming can be increased (Increase CPU utilization and throughput).

Virtual memory separates the user logical view from the actual physical memory. Does this sound familiar? Perhaps from the previous article? Well, yes, Paging and Segmentation supports this Virtual Memory scheme (swapping pages/segments into a secondary storage).

We look at a simple Virtual Memory management scheme known as Demand Paging. Recall that in the previous article I mentioned that the secondary storage is divided into fixed-sized frames, but I didn't talk about what is it used for. The secondary storage is actually used for swapping existing Frames in the physical memory into the backing store (backing store and secondary storage is used interchangeably in this article).

When a process needs to do something, it only swaps in the necessary frames, reducing the RAM needed and the time it takes to load up (faster response time).

Recall that the page table also contains a Valid/Invalid flag for each page. This Valid/Invalid flag can now be used to determine if a Page is already loaded in the physical memory.

From the seminar notes, here are the definitions:
Valid - The associated page is both legal AND in memory
Invalid - The associated page is illegal OR legal but not in memory

(Recall that in the previous example, Valid is just for legal, and Invalid is just for illegal. Also recall that Legal means that the page is in the process's address space.)

Here is how the paging table would look like:

(Taken from Recommended Text)

If a process tries to access an Invalid page, a Page Fault Trap occurs. We will be referring to this diagram for the elaboration:

Now let's go through the steps in sequence.

1) Whenever a logical memory is accessed, it is first checked for the Valid/Invalid bit. If it is Valid, operation continues as per normal.

2) However, if the Page being accessed is Invalid, a Page Fault Trap occurs to notify the OS.

3) The operating system schedules a Disk Read to find the missing frame.

4) A list of free Frames is consulted. If there is a free Frame, the Frame is loaded into the Physical Memory. If there is no free Frame, a Page Replacement occurs. This would be described in the next section.

5) The Paging Table is updated to reflect the Valid bit if the Page is successfully loaded.

Now we'll talk about the Page Replacement process. These are the steps outlined in the seminar:

if (Free Frame Exists)
{
}
else
{
Sacrifice a Frame according to Page Replacement Algorithm;
Write Sacrificed Frame to Backing Store;
Update Sacrificed Page Table to Invalid;
}
Load Desired Frame from Backing Store to Free Frame Location;
Update Desired Page Table to Valid;

The Page Replacement Algorithms are used to select a victim frame. The three algorithms we've learned are:
FIFO - Oldest frame is sacrificed
LRU - Least recently used frame is sacrificed
Optimal - Replace the page that will not be used for the longest period of time.

There exists an anomaly known as Belady's Anomaly where, usually in a FIFO environment, the number of page fault actually increases if the number of frames to work with increases. This disproves the assumption that more Frames equate to better performance. We'll discuss this if we have time.

Now we'll go through some examples on how to apply the algorithms. First of all, we'll define the page reference string:
1, 3, 4, 2, 3, 6, 4, 2, 1, 5, 2, 5, 6, 3, 4, 2, 1, 2, 1, 5

Now, suppose that the process has only 3 frames to work with. We'll now go through FIFO:

1 3 4 2 3 6 4 2 1 5 2 5 6 3 4 2 1 2 1 5

1 1 1 2 2 2 2 2 2 5 5 5 5 3 3 3 1 1 1 1
  3 3 3 3 6 6 6 6 6 2 2 2 2 4 4 4 4 4 5
    4 4 4 4 4 4 1 1 1 1 6 6 6 2 2 2 2 2
F F F F   F     F F F   F F F F F     F

In this case, there are 14 faults.

Now let's go through LRU:

1 3 4 2 3 6 4 2 1 5 2 5 6 3 4 2 1 2 1 5

1 1 1 2 2 2 4 4 4 5 5 5 5 5 4 4 4 4 4 5
  3 3 3 3 3 3 2 2 2 2 2 2 3 3 3 1 1 1 1
    4 4 4 6 6 6 1 1 1 1 6 6 6 2 2 2 2 2
F F F F   F F F F F     F F F F F     F

There are 15 faults when using LRU.

Finally, we'll see how Optimal performs:

1 3 4 2 3 6 4 2 1 5 2 5 6 3 4 2 1 2 1 5

1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
  3 3 3 3 6 6 6 6 6 6 6 6 3 4 4 1 1 1 1
    4 4 4 4 4 4 1 5 5 5 5 5 5 5 5 5 5 5
F F F F   F     F F       F F   F

We have a clear winner of 10 faults in Optimal.

However, in real life, the Optimal Page Replacement algorithm is not easy to implement and a practical solution does not exist for this as it requires future knowledge.

2011-02-23T20:23:00.004+08:00

CAOS 10

When a process is admitted into the system, it requires memory, so a memory management algorithm is needed to allocate space to it. When the processes no longer exists, the memory manager should also free up the memory.

When referring to addresses, we encounter two types of addresses:
Logical Addresses - Generated by the CPU, also known as the Virtual Address
Physical Addresses - An actual memory location seen by the RAM

There are three ways a program can be situated in memory is referred to as how the program is "bound" to the memory.

The first type of Address Binding is the Compile-Time address binding. Processes that always end up in the same spot uses Compile-Time. Compilers generate absolute addresses (e.g. 80h) during compilation.

Processes that appear at different locations everytime it is run uses Load-Time address binding. The compiler would generate relocatable (i.e. Relative) addresses (e.g. Fish.dll+5000) and the linkage editor/loader would generate the absolute address.

Processes that appear at different locations during execution uses Execution-Time address binding. The compiler would generate relocatable (i.e. Relative) addresses (e.g. Fish.dll+5000) and the linkage editor/loader would generate the absolute address. There are additional control schemes present which would not be discussed.

Access to the actual physical memory (i.e. Memory location 5638 on the RAM) is controlled by the MMU (Memory Management Unit). Whenever a context switch occurs, the new process's Memory Base (i.e. Where it is located on the RAM) is written to the Relocation Register on the MMU.

Whenever the program wants to access a memory location, it refers to its Virtual Address (e.g. Address location 638), and the MMU would translate this into the Physical Address by adding the base (If the base is 5000, then it would send a request to location 5638).

The program only deals with the logical address, that is, from 0 to limit where limit is the maximum size of the process.

Here's a diagram that shows the MMU:

(Taken from recommended text)

Now that we know WHERE to locate a process, we would need to go into HOW the program is allocated its memory. There are two types of allocation: Contiguous and non-contiguous.

In contiguous memory allocation, as its name suggests, a process can only be allocated into a contiguous location. If a memory location cannot fit memory requirements of the program, the program cannot be partially loaded there.

The text discusses three types of Contiguous Memory Allocation:
First Fit - Fit it in the first available space that can accommodate the program
Worst Fit - Fit it in the largest available space that can accommodate the program
Best Fit - Fit it in the smallest available space that can accommodate the program

The actual definition of Internal and External fragmentation is different from what we've been learning so I'll just show you the actual one (not in the seminar).

Internal Fragmentation is memory allocated that is not used AND CANNOT be used by other processes. Take for example a memory allocation scheme where memory is allocated only by blocks of 32KB. If a process requires 100KB, it would be allocated 128KB minimum. The extra 28KB is internal fragmentation because it is allocated, is not used, and cannot be used by another process.

Another Internal Fragmentation example is the use of MPS (Multiple Partition Allocation Scheme). In MPS, memory is broken into many partitions. The rule here is that each partition can only fit ONE PROCESS. After the process is fitted into a partition through a memory allocation algorithm, the extra space (i.e. 90KB process, but 95KB partition) is said to be Internal Fragmentation because a 3KB process cannot be put in there even though there is 5KB left. (Only one process per partition).

If a RAM has multiple partitions, and somehow each partition allows more than one process, then there is NO (or negligible) internal fragmentation.

Now comes External Fragmentation. External Fragmentation is fragmentation that is a result of the memory being broken by the creation and deletion of processes. Take this example of a single partition:

At first, A, B and C are loaded:
A: 10KB
B: 20KB
C: 30KB
Free: 40KB

Now, B is taken out, leaving a hole of 20KB there:
A: 10KB
Free: 20KB
C: 30KB
Free: 40KB

Process D wants to be loaded, and it requires 50KB of memory. The total free space is 60KB, but the space is suffering from External Fragmentation. The process must be contiguous so the process cannot be loaded in either hole. The External Fragmentation is said to be 60KB.

How much Internal Fragmentation is there? Notice that there exists no minimum allocation block. In this example, there is no space DENIED to be used (e.g. If there is a new 15KB process, it can use the 20KB free space, leaving 5KB for other processes) so Internal Fragmentation is negligible here.

If there are multiple partitions, and it is using the MPS scheme (only one process per partition) then the External Fragmentation is the sum of ALL empty partitions. If there are multiple partitions and more than one process can fit, then the External Fragmentation is the sum of ALL free space.

As there are some confusions about Compaction, I'll leave it out until it is confirmed.

Now we'll talk about Non-contiguous memory allocation. The first method we are going to discuss is Paging. Paging simplifies things by breaking everything into fixed-sized blocks. That is to say, Logical memory is broken into Pages of size x, Physical memory is broken into Frames of size x, and the backing store (secondary storage device) is broken into Frames of size x.

A Page Table keeps track of all pages. Think of the Page Table as an array:
pageTable[x];

x is the number of pages a program has. Each entry in the array contains a pointer to the base address of the page stored in the physical memory. This is to say, if we are looking for Page 5 (where the first page is 0), we look for &pageTable[5] (the value pointed to by the sixth index).

(Taken from recommended text)

Each memory location generated by the processor (i.e. A Virtual Address), is converted into a Page Number and an Offset. The Virtual Address is translated as such:
pageNumber = virtualAddress/blockSize;
offset = virtualAddress%blockSize;

The actual physical address accessed would be translated as such:
&(pageTable[pageNumber]+offset)

The advantage of Paging is that it gets rid of External Fragmentation totally. However, Internal Fragmentation still applies (recall the example above where a process is 100KB and the allocation size is 32KB).

At times when the page table is larger than the number of pages a process has, there is a Valid/Invalid bit set for each entry in the Page Table (e.g. If a process has pages 0 to 5, but is given a Page Table of 0 to 8, then indexes 0 to 5 are set to valid, while 6 to 8 is set to invalid). Access to invalid pages would result in a trap.

As you might have guessed, the page table is stored in none other than the PCB. Other than the Valid/Invalid bits, the system can also make use of a PTLR (Page-Table Length Register) to keep track of the length of the Page Table.

Another non-contiguous memory allocation method is Segmentation. Segmentation is similar to paging, except that it allocates memory based on segments instead of blocks and frames. This way, since the allocated memory is exact, there is no Internal fragmentation. In a segmentation system, there is only external fragmentation.

Instead of a Page Table, we have a Segmentation Table. It works similar to the Page Table, except that it now looks like an array like this:
segmentTable[numberOfSegments][2]

The first dimension correlates to the segment number, while the second dimension correlates to Limit and Base. Limit simply means the length of the segment, and base defines the physical address where the segment begins.

(Taken from recommended text)

The compiler first divides the process into its different parts. Each part (e.g. Subroutine, Stack, Symbol Table, Functions, Main Program) resides in a different segment. The user's access to the memory is now through:
physicalMemory = &segmentTable[segmentNumber]+offset;

2011-02-23T19:50:00.003+08:00

CAOS 09

This article will be focused on the Transition State Diagram. It is depicted below:

A process is a program in execution. This state transition diagram depicts the various states a process can transit in operation.

A process can be in 5 states:
New - The process is being created
Running - Instructions are being executed
Waiting - The process is waiting for some event to occur (I/O or reception of signal)
Ready - The process is waiting to be assigned to a processor
Terminated - The process has finished execution

Only one of these processes can be in the running state at one time.

The processes that enter a system are put in a job queue. This is a pool of all processes in a system. The long-term scheduler (or job scheduler) admits the job into the Ready Queue from the Job Queue. The long-term scheduler is rarely called.

The long-term scheduler controls the degree of multiprogramming - The number of processes in the Ready Queue.

The Ready Queue consists of all the processes that reside in the main memory. The short-term scheduler (or CPU scheduler) dispatches the processes with a Scheduling Algorithm for the CPU to process. The CPU scheduler also interrupts a running process into the Ready Queue for another process. The Ready Queue is called very frequently.

A process goes through an alternation of CPU bursts (doing processing) and I/O bursts (doing I/O).

An I/O bound process is a process that spends most of its life in I/O bursts. If the system is mostly comprised of I/O bound processes, than there would be a lot of processes in Device Queues and less processes in the Ready Queue (waiting for the CPU)

On the other hand, if there are more CPU bound processes, then there would be more processes in the Ready Queue and less in the Device Queues.

Each process is represented by a PCB (Process Control Block) which contains information associated with the specific process.

Although the long-term scheduler controls the degree of multiprogramming, its control is only one way: It can only increase it. The medium-term scheduler controls the degree of multiprogramming by temporarily removing it from the Ready Queue and putting it and its PCB in a secondary storage, thus reducing the Degree of Multiprogramming.

As processes switch in and out of the Running state, their PCBs are saved and reloaded as shown in this diagram:

PCBs store the context of the process. The switching is pure overhead as the system does no useful work while switching.

For a context switch to take place, the kernel saves the context of the old process in its PCB, then reloads the saved context of a new process scheduled to run. This process is repeated to switch the old process back.

2011-02-23T19:44:00.001+08:00

CAOS 08

Single-Processor Scheduling

Background

Before we begin, let's discuss why we would need Process Scheduling. We learned in lecture that a single-processor system can only execute a single process at any given time. Once the process has finished a certain task, it typically has to wait for some I/O before it further carry out tasks. In a non-Multiprogrammed system, the CPU is idle during this wait and precious clock cycles are wasted.

A Multiprogrammed Operating System ensures that the CPU is optimally utilized. This is done through Process Scheduling. A Multiprogrammed Operating System makes use of Process Scheduling to allow the queuing of multiple processes in memory. The basic idea is that once a process has to wait for further I/O, the CPU switches to another process in memory. This is repeated for all proceses. This way, multiple tasks can be completed quickly with minimal CPU idling.

A process switches between two states: CPU Burst, and I/O Burst. Generally, when a process is executing a task, it is said to be in CPU Burst. CPU Bursts are also known as Execution Cycles. When the process needs to wait for I/O, it is said to be in I/O Burst. An I/O-bound program such as a software calculator would have many short CPU Bursts and long I/O Bursts. A CPU-bound program such as a video converter would have longer CPU Bursts and shorter I/O Bursts. This categorization is important when selecting process Scheduling Algorithms.

Processes are lined up in a queue known as the Ready Queue for execution. When the CPU becomes idle, the next process to be executed is determined by the CPU Scheduler (also known as the Short-Term Scheduler). A Dispatcher is the module that stops a process and start a new one. In other words, it gives control to a process selected by the CPU Scheduler. The time it takes to switch processes is known as the Dispatcher Latency.

Scheduler Types

Schedulers can be categorized into two broad types: Cooperative and Preemptive. Cooperative Schedulers are schedulers that cooperates with the processes. It does not take the initiative to pause a running process for another task. It instead waits for the process to invoke either an I/O request switch to a wait state. Preemption in this case means to temporarily disrupt a certain task for one of a higher priority.

In a Preemptive Scheduler, the CPU responds to interrupts such as when a calculation is done, when a user clicks on a button or when a disk write is completed. Operating systems starting from Windows 95 and Mac OS X all make use of Preemptive Scheduling. Preemptive Scheduling, however, requires multiple mechanisms to ensure integrity of shared data and is thus harder to implement.

Scheduling Criterias

Scheduling Algorithms make use of Criterias to select the next process. Understanding these criterias allow selection of algorithms to fit the correct application. The criterias used include:

-CPU utilization - How loaded a CPU is. Higher is better.
-Throughput - Processes completed per time unit. Higher is better.
-Turnaround time - The time it takes to execute a process. Lower is better.
-Waiting time - The time a process spends waiting in the ready queue. Lower is better.
-Reponse time - The time between the request and the first response (need not be the complete response). Lower is better.

Scheduling Algorithms (Single Processor)

First-Come, First-Served Scheduling

Now we'll be ready to talk about the different Scheduling Algorithms. The first scheduling algorithm is the First-In-First-Out, First-Come-First-Served or the Best Effort algorithm. The first process requesting the CPU would be the first process served. The FCFS algorithm looks like this:

The FCFS algorithm is the simplest of all algorithms. However, as you can see, the larger processes may end up hogging the CPU for extended periods of time, resulting in the "Convoy Effect" where other small processes have to wait for a single big process to complete.

Shortest-Job-First Scheduling

The next scheduling algorithm we're going to talk about is the Shortest-Job-First or the WFQ (Weighted Fair Queuing) algorithm. Just like its name implies, the CPU first evaluates the jobs, then schedules the jobs based on the length of the next CPU burst:

A more appropriate name for this is actually the "Shortest-Next-CPU-Burst-First Scheduling" since the processes are evaluated based on the next CPU burst. The way the system predicts the length of the next CPU burst is through the use of the "Exponential Average" formula. The Shortest-Job-First Algorithm can be Preemptive or non-Preemptive. The Preemptive one would stop a job whenever a smaller one exists, and is called Shortest-Remaining-Time-First Scheduling.

Priority Scheduling

Priority Scheduling allows processes to be associated with a Priority. The highest priority ones are executed first. Those with equal Priority would be executed in a FCFS basis:

A major problem in priority scheduling is the existence of Indefinite Blocking or Starvation. A Blocked Program refers to a program ready to run but is unable to due to the execution of a higher priority process. A large high-priority process can indefinitely hog the CPU, leaving processes unable to run until the system is less loaded. The solution to this problem is the introduction of Aging, which gradually increases the Priority of processes waiting in a queue.

Round-Robin Scheduling

The Round-Robin Scheduling Algorithm is similar to the Time-Division Multiplexing used in telecommunication services. Whereas TDM allocates "Time Slices", Round-Robin scheduling allocates in units of CPU "Time Quantum". Time Quantum is simply a fixed length of time a CPU is allowed to process a task before it has to switch:

Round-Robin Scheduling is typically designed for Time-Sharing systems. It is similar to FCFS, but allows Preemption between processes after each Time Quantum. The ready queue becomes a circular queue where the CPU goes round and round until all processes are completed. This method, also known as Processor Sharing, creates the illusion that there are n processes concurrently running at 1/n the actual processor speed.

Multilevel Queue Scheduling

Finally, we have a Multilevel Queue Scheduling. If you are familiar with OSI Layer 2 and 3 queues, this would also be called CBWFQ (Class-Based Weighted-Fair-Queuing). In a Multilevel Queue Scheduling Algorithm, the ready queue is split into multiple queues. Each process is permanently assigned to one queue. There can be different scheduling algorithms employed for each queue. The queues can either be served on a Highest-Priority-Queue-First basis or on a Round Robin basis where the higher priority queue gets more Time Quantum over the lower priority queues. The Highest-Priority-Queue-First method looks like this:

In this example, the queues are named System Processes, Interactive Processes, Interactive Editing Processes, Batch Processes and Student Processes. It isn't necessarily classified as such on actual real life systems. The queues are classified according to Foreground (Interactive) and Background (Batch) processes, where Foreground processes get the most CPU cycles. In the Highest-Priority-Queue-First method, the lower queues will never be run if there is always data in the upper queues. This may lead to Starvation. The other approach is to use Time-Slicing among the queues as mentioned before.

Another type of queue known as the Multilevel Feedback-Queue is similar to the Multilevel Queue, but allows processes to move between queues according to the characteristics of their CPU bursts. Larger processes (in terms of CPU bursts) are moved to the lower priority queues while smaller processes are moved up. This eventually pushes Interactive processes to the higher priority queues.

Multiple-Processor Scheduling

Background

Multiple-processor systems allow Load Sharing of tasks between processors. However, with added benefits comes added complexity. Our syllabus focuses on Multiple-Processor Scheduling across Homogeneous processors. Homogeneity allows engineers to assume that the processors can all do the same type of tasks, which helps reduce complexity especially when it comes to Load Balancing.

There are two main approaches to Multiprocessor Scheduling. The first approach is Assymetric Multiprocessing (AMP) . In Asymmetric Multiprocessing, a single processor acts as the Master Server, while the other runs only User Code. The Master Server handles all scheduling decisions, I/O processing and other system activities. Since only the Master Server handles access of the system data structures, the mechanism for maintaining data sharing integrity is simplified.

The other method is the Symmetric Multiprocessing (SMP). Each processor acts as its own Master Server, and can share a common ready queue or support a ready queue each. The processors then pick processes from the queue for execution. However, this requires a more complex data sharing integrity mechanism as there is an increased chance for data corruption due to simultaneous access of the data structure. The processes can also be Load Balanced using either Push Migration or Pull Migration. In Push Migration, the load on processors are checked and if there is an imbalance, processes on the higher utilized processor will be pushed to the lower utilized one. Pull Migration is used when a processor pulls a task from another busy processor's waiting queue. Push and Pull Migration can be implemented together in the same Operating System.

Processor Affinity

If a process is to be migrated to another processor, the cached information in the first processor must be invalidated and the cache in the second processor must be repopulated. As this is inefficient, Symmetric Multiprocessing systems typically try not to migrate processes between processors. Instead, each process is associated with a Processor Affinity which keeps it running on a particular processor. If a process will only try to stay on a processor, it is called a Soft Affinity. If a process must stay on a processor, it is bound by a Hard Affinity.

Symmetric Multithreading

Hyperthreading Technology (HTT) on Intel processors is a type of processing known as Symmetric Multithreading. Symmetric Multithreading allows multiple logical processors on the same physical processors. Each logical processor has its own Architecture State, which includes general and machine-state registers. The Operating System would perceive the system as being a Multiprocessor system. As such, each logical processor will handle their own interrupts. However, each logical processor would share the same physical resources such as cache and buses.

Summary

Multiprogrammed Operating Systems use Process Scheduling to ensure maximum CPU usage.

A process toggles between CPU Bursts and I/O Bursts.

In a single processor system, only one process can be in CPU Burst at one time.

A CPU Scheduler retrieves processes from a Ready Queue and a Dispatcher switches the tasks. The time it takes to switch is called the Dispatcher Latency.

Cooperative Schedulers will wait for a program to go into a I/O Request or Wait State, while a Preemptive Scheduler can temporarily stop the execution of a program in favor of another.

Scheduling algorithms make use of these criterias: CPU Utilization, Throughput, Turnaround Time, Waiting Time, Reponse Time.

FCFS Scheduling runs the jobs in the order it is received.

SJF Scheduling runs the smallest job first. It can be preemptive, in which it will be called Shortest-Remaining-Time-First Scheduling.

Priority Scheduling runs the highest priority jobs first, then FCFS for those that are tied.

Round-Robin Scheduling quickly switches between all processes, each time for the time period known as the Time Quantum.

Multilevel Queue Scheduling allows multiple queues of different priorities, and each queue can run a different Scheduling Algorithm.

There are two ways to describe a process: Foreground (Interactive) or Background (Batch). Processes are permanently assigned to a queue and the queues can be run in a Priority or a Round-Robin fashion.

Multilevel Feedback-Queue Scheduling allows processes to move around queues, where the most resource hogging processes go to a lower queue.

Asymmetric Multiprocessing has one processor assigned as the Master Server while the others handle User Code.

Symmetric Multiprocessing are all Master Servers of their own, and can share a Ready Queue or have one each.

Push Migration shifts jobs to another processor to make the utilization balanced.

Pull Migration pulls jobs from another processor's waiting queue.

Processor Affinity can be set on a process to keep it from migrating.

Soft Affinity is not a guaranteed Affinity, while Hard Affinity ensures that a process stays on a processor.

Symmetric Multithreading allows running of multiple Logical Cores in a single Physical Core. They have their own registers, architectural state and handle their own interrupts, but share caches and buses.

2011-02-23T18:24:00.002+08:00

CAOS 07

Let's now talk about File System Organization. The file system first defines how the units are managed. The system identifies a physical block through the use of drive/cylinder/track/sector numbers. For example, a Block can be 4 sectors, while each sector is 4096 bytes.

Next, the File System performs I/O control to translate the high level physical commands "retrieve physical block 5" to a low level hardware specific commands.

Finally, the File Organization Module translates high level logical commands to physical commands, like "retrieve logical block 1 of file A" to "retrieve physical block 5" for the I/O control.

Files need to be allocated to the disk in some way. The main focus of the allocation methods is to make the best and efficient use of the disk space, and to allow the files to be accessed as quickly as possible.

In the recommended text, we discuss three ways of allocating files. The first is the contiguous file allocation. This allocation is the simplest. We simply need to specify the start of the file in block number, followed by the length in blocks as shown:

(From recommended text)

Like contiguous memory allocation, each file occupies a set of contiguous blocks on the disk. This supports fast sequential and direct access, but does not make good use of disk space, resulting in high external fragmentation. The system would have trouble finding space for a new or resized files, and we would not be able to determine size requirements of a file.

Another method is the Linked Allocation. In Linked Allocation, each file is stored as a Linked List of Blocks. Each Block belonging to the file would have a pointer to the next Block to be read. The Blocks may exist anywhere on the disk, like this:

(From recommended text)

This method solves the external fragmentation problem as well as the provision for disk space. This is also perfect for sequential access since the Blocks MUST be accessed in sequence. However, due to that very same reason, it does not support direct access efficiently.

As the overhead of pointers may get large, a solution is to allocate clusters of contiguous blocks instead of single blocks. There is also a possibility of link breakages. In this case, richer links should be used.

Notice that the last block has a pointer to -1. It signifies an EOF (End-of-File).

To allow non-contiguous allocation (to solve disk and file size allocation issues) as well as direct access, a method known as the Indexed Allocation is used. In Indexed Allocation, the blocks scattered through the disk is recorded in sequence in an Index block. In this case, you would not have to go through EVERY block to get to the next. We can simply skip ahead in the Index block. The ith entry in the Index points to the ith block of the file.

(From recommended text)

This method is great as it is the best of both worlds. However, it is wasteful if the file only takes up two blocks. The Index is allocated in blocks, so the unused space are flagged as -1. This causes great wastage.

2011-02-23T17:29:00.004+08:00

CAOS 06

Systems can store a lot of files. To cope with these files, disks are first split into partitions.

Partitions can be known as:
-Minidisks - IBM
-Volumes - PC

Each disk contains at least one partition. A file system (such as FAT32/NTFS/EXT4 is overlaid on it).

In partitions, another level of organization is the Device Directory. There are many different implementations of Device Directories which would be discussed later. The Device Directory records information for all files on that partition.

The Directory looks like this in a partition:

(Image courtesy of recommended text)

Like files, there are many operations that can be applied to a Directory. This is a summary:
Search for a file - Match files by a specified pattern
Create a file - Add a file to the directory listings
List a directory - List all files in a directory
Rename a file - Change the name representing a file in a directory
Traverse the file system - Perform a recursive operation, such as for a backup

As mentioned, directories can be implemented in many ways. The simplest way is the Single-Level directory. The advantage is that it is easy to support and understand.

However, when the number of files increases or when the system, has more than one user, these problems arise:
-Files must have unique names, and therefore if two users have the same file, they cannot name it the same
-Files become increasingly difficult to remember and manage

A Single-Level directory looks like this:

(Image taken from Recommended Text)

The Two-Level Directory on the other hand provisions a separate directory for each user. Each user has a UFD (User File Directory) which lists only the files belonging to one user. The UFD is obtained upon logon from the MFD (Master File Directory) which is indexed typically by User Name.

The good thing about a Two-Level Directory structure is that it solves the name collision problem, so all users can have a file named "Assignment5.txt".

However, as each user can only access their UFD, they cannot access the files located in another user's UFD. Depending on how strict a system is, it may totally prohibit cooperation. Access of the other user's files also must be absolute. For example, /user2/folder/file.txt, or C:\user2\folder\file.txt where C is the partition identifier.

Access of system files become a problem. One solution can be to copy all system files to each UFD. However that would be an administrative nightmare and results in inefficient use of space.

Another solution is to include the search paths. Search paths, such as the one implemented by windows using the PATH variable, allows the system to search for a particular file in the PATH variable if it is not found in the current directory. This allows a special directory to be put aside for special purposes such as storing system files.

This is how the Two-Level Directory looks like:

(Taken from Recommended Text)

A directory or subdirectory contains a set of files or subdirectories. A directory is simply a file flagged with the directory bit. A Tree-Structured Directory is similar to the Single- and Two-Level directory in that it has a root, but allows more than 2 levels of directories. This allows the users to create and organize their files accordingly.

The current directory is the directory that the user is currently at. When specifying a file or location, you can either use relative or absolute paths.

A relative path is a path that is relative to the current directory. For example, if you are in /etc/fish/ and you attempt to perform this command "nano toilet.txt", which specifies a relative path, you would be equivalent accessing the absolute:
nano /etc/fish/toilet.txt

Where /etc/fish is the value obtained in the "pwd" command.

In this case, this is equivalent:
nano `pwd`/toilet.txt

On the other hand, to access a file that is not relative to the current directory (e.g. we are currently in /etc/fish/ and we wish to access something in /etc/fish2/), we use an absolute path:
nano /etc/fish2/toilet.txt

If a directory is not empty, it cannot be deleted. To delete the directory, we must either manually delete all files and subdirectories (and all files within the subdirectories) before we can delete the directory.

In UNIX systems, we can use the -r parameter for the "rm" command to do a recursive deletion of a directory and all files/subdirectories in them.

We now come to the Acyclic Graph Directory. Like the Tree-Structured directory is a natural generalization to the Single- and Two-Level directory scheme, the Acyclic Graph Directory is a natural generalization of the Tree-Structured directory scheme.

In an Acyclic Graph Directory, files and folders can be shared. They can exist in multiple places at the same time. This is similar to the symbolic link (symlinks/softlinks/hardlinks) used in Linux. A Link is simply a pointer to another file.

Let's see how the Acyclic Graph looks like:

(Taken from the recommended textbook)

A good use of this is for cooperation. If a group of users wish to work on the same project, they can simply create symbolic links of the folder at other locations (such as in another user's UFD).

To prevent cycles, the OS ignores all Links when doing traversal operations so as not to end up cycling.

There are many ways to delete Links. Deleting a Link is like deleting a shortcut. Deleting the linked file would leave the Links dangling. This is the cheap method.

Upon deletion, the system can search for, and delete all Links. However, unless there exists a maintained list of Links associated with the file, the search can be expensive.

Finally, we can restrict deletion of the file until all references to it are deleted.

2011-02-23T15:40:00.002+08:00

CAOS 05

Information can be stored on hard disks, magnetic tapes, optical media and so on. So there is a need for a way to represent this information in a convenient, consistent, uniform and logical view. That is where the file system comes in.

The file system provides an abstraction layer to the physical properties of its storage devices to define a logical storage unit, known as a File. Each File has its associated attributes. The bare minimum are these:
Name
FID - The file's unique identifier
Type
Location
Size
Protection - In other words, permissions, such as who can RWX.
Time, date, and user identification - Timestamp, and owner/group information.

File operations are operations that work on files, such as:
Create - Find space for the file, then write the file and record it in the directory
Write - The OS provides the File Name and information to be written. Controlled by a write pointer.
Read - The OS provides the File Name, and the memory (RAM) location to read to. Controlled by a read pointer. (As a process only performs one of these at a given point, the same pointer may be used for read and write. This is now called the current-file-position pointer)
Seek - Reposition within a file
Delete - Delete the file's contents and attributes
Truncate - Deletes the file's contents only, leaving a zero-byte file with attributes intact.

These operations work on the files by viewing them as an abstract data type, such as bits/bytes/lines/records.

You can derive other operations as such:
Copy - Create (in new location), Read (from old file), Write (to new location)
Move - Create (in new location), Read (from old file), Write (to new location), Delete (the old file)
Move/Rename
Append
etc.

File Types allow the operation (or in some cases the user) to determine what operations can be performed on the file. For example, a binary file should not be printed, or else we would get garbage. Likewise, a text file should not be executed as a binary file.

The way the operation system identifies the Type of the File can be through various ways such as:
1) File name extensions - The type is appended to the file name, such as .exe, .com. Typically used in Windows.
2) Creator Attributes - The type is an attribute stored in the file to describe the program that created it. Typically used in Macintosh.
3) Magic Number - The type is a number stored in the beginning of a file. It is not compulsory. This is typically used in UNIX systems.

Now that we've established the basics of a file (there are much more, actually), we'll go into how the files are accessed. The simplest method is the Sequential Access method.

In Sequential Access, the information in a file is processed in order. That is to say, the file is accessed Record by Record. This is the most common and simplest file access method, and it is used by editors and compilers.

In Sequential Access, a read operation basically reads forward, with the Read Pointer automatically advancing to the end of the file. A write (or append) operation would write from a specified pointer to the end of the newly written material.

Some systems allow skipping forward or backward for n records, most commonly n=1. This is based on the tape model, and it works well on Sequential Access DEVICES (Tape) as well as Random Access DEVICES (Disk, Flash).

The sequential file access method looks like this:

(Image taken from the recommended text.)

Another method is the Direct Access (or Relative Access) method. Files are made up of fixed-length logical records. As its name suggests, it allows Direct Access to any record in no particular order. As its name also suggests, the way the Records are accessed is through a Seek function which is Relative to its current position (following the seminar notes. In the recommended text, it is relative to the beginning of the file so it's actually an absolute access).

For example, assuming we start from Record 0:
seek(5);
seek(10);
read();

This would result in a read of Record 15.

Finally we come to the non-native Access Methods. These methods, like the non-native File Operations, work on existing Access Methods. We will discuss a method known as the Indexed Access method.

In the Indexed Access method, the file is divided into different sections and pointers to the starting Block of the different sections are stored in an Index. The Index is then consulted whenever it requires a specific section, and the Direct access method is used to move directly to the required Block. The Index can be stored as a separate file or within the same file. (Seminar notes only specifies the Index within the same file).

The Index looks like this:

(Again, image taken from Recommended Text)

2011-02-22T20:45:00.004+08:00

CAOS 04

Now let's talk about the different methods we can use to handle deadlocks. In this case, we have three:

Deadlock Prevention
Deadlock Avoidance
Deadlock Detection and Recovery

We'll first look at Deadlock Prevention. Recall that a Deadlock requires four conditions to occur: Mutual Exclusion, Hold and Wait, No Preemption, and Circular Wait. The focus of Deadlock Prevention is to make sure that all of these conditions do not hold true at the same time.

In Mutual Exclusion, the protocol should try its best to make all resources sharable. Certain non-sharable resources, such as a printer, should still retain Mutual Exclusion.

In Hold and Wait, we make sure that a process can only make a request if it does not hold any other resource. What this means is that a process can only request for multiple resources in a single request. Every time it requests for another set, it must release them.

In No Preemption, we make sure that all resources held by a particular process is preempted if the resource it is requesting is not available. Alternatively, when a process requests for a resource, and it is free, it is given to it. If it is not available, and it is given to another waiting process, then that resource is preempted. If it is not available, and it is currently being used by a Running process, then the process waits.

In Circular Wait, each process is given a unique number. If the process does not currently hold any resource, it can request for any resource. However, if it already does, we need to make sure that the processes can only request for another resource with a higher number. For a process to use a lower resource, it must first release the higher resource.

To prove the above does handle Circular Wait problems, assume that a Deadlock has occurred in a system of 6 processes and 6 resources. Let's assume in this case P1 is waiting for P2 which holds R1. P2 is then waiting for P1 which holds R2.

If P2 is able to request for R1, that would mean that R1 < R2.

On the other hand, if P1 requests for R2, it would mean R2 < R1.

This would mean that R1 < R2 < R1, which transitively means R1 < R1 which is not possible.

R1 < R2
R2 < R1

Therefore

R1 < R2 < R1
R1 < R1

Now we'll move on to Deadlock Avoidance. In Deadlock Avoidance, the system attempts to arrive at a Safe State. A Safe State can only exist if there exists a Safe Sequence. A Safe Sequence is a sequence of execution whereby ALL the resource held by a PREVIOUS process can satisfy the NEEDS of a FOLLOWING process.

In a Safe State system, there can exist no Deadlock. In an Unsafe State system, there MAY be a Deadlock. A system in Deadlock is definitely in an Unsafe State.

Let us look at a single resource example taken from the textbook where 12 magnetic tape drives are shared among 3 processes:

 Maximum Needs  Current Allocated May Need
P0 10   5   5
P1 4   2   2
P2 9   2   7

At the time instant, 9 tapes are allocated to the three processes, leaving only 3 free. We should derive a safe sequence where:
CURRENT + P.i.ALLOCATED >= P.(i+1).NEED

In this case, the only thing that is able to use 3 tape drives is P1. Therefore, we give P1 the tapes first. When P1 is done, we assume that P1 releases ALL tapes, so we end up with (CURRENT-P1.NEED)+P1.MAX = CURRENT+P1.ALLOCATED = 5 tapes.

Now, at this point, we can only satisfy P0. Following the equation, we'll have CURRENT+P0.ALLOCATED = 5+5 = 10 tapes left.

Finally, we can satisfy P2, which requires 7 tapes. In the end, we'll have our CURRENT+P2.ALLOCATED = 10+2 = 12 tapes back.

The sequence we have derived is P1,P0,P2. Let's check if P.i.MAX+P.i.NEED > P.(i+1).NEED is true.

At first, CURRENT is 3.
CURRENT + P1.ALLOCATED >= P0.NEED
3 + 2 >= 5 (TRUE)
At the end of P1, CURRENT is 5.

At this point, CURRENT is 5.
CURRENT + P0.ALLOCATED >= P2.NEED
5 + 5 >= 7 (TRUE)
At the end of P0, CURRENT is 10.

At this point, CURRENT is 10.
CURRENT + P2.ALLOCATED == TOTAL
10 + 2 == 12
At the end, we have 12 tapes back.

What we just went through is a simple Banker's Algorithm example. Let us look at a complex Banker's Algorithm example with three resources and 5 processes (taken from the textbook).

 Allocation Max Need
 A B C  A B C A B C
P0 0 1 0  7 5 3 7 4 3
P1 2 0 0  3 2 2 1 2 2
P2 3 0 2  9 0 2 6 0 0
P3 2 1 1  2 2 2 0 1 1
P4 0 0 2  4 3 3 4 3 1

Each of these are arrays of int[numberOfProcesses][numberOfResources]. In other words, where n is the number of processes, and m is the number of resources, we have matrices of n*m.

Now, assume that at this point, we're still left with:

A B C
3 3 2

We would need to derive a Safe Sequence where the rule holds true. At this point, we can have P1 or P3 go first. We would use a table as such to derive the safe sequence:

Available = [3, 3, 2]

 Work Finished
P1 5  3 2 True
P3 7  4 3 True
P4 7  4 5 True
P2 10 4 7 True
P0 10 5 7 True

Sequence  satisfies the safety criteria
and the final state of the resources as above.

We finally move into detection and recovery. For Single Instance deadlock detection, a Wait-For graph is derived from a Resource-Allocation Graph. A Wait-For graph is simply a graph that omits all resources, with the arrow pointing to the process a process is waiting for.

Resource-Allocation Graph

Wait-For Graph

Detection for multiple instances of each resource type uses the Banker's algorithm. If the matrix has a False for any entry in the Finished matrix, then a deadlock has occurred.

The usage of the detection algorithm is dependent on how OFTEN a deadlock is likely to occur, and how MANY processes will be affected by deadlock when it happens.

Recovery from deadlock involves:
Process Termination - All deadlocked processes are terminated, or one at a time until a deadlock is resolved
Resource Preemption - A resource is PREEMPTED from a selected victim. The process is ROLLED BACK. We should also make sure that the preempted process is not STARVED.

2011-02-22T08:44:00.003+08:00

CAOS 03

As mentioned before, a deadlock occurs when all processes in a set are waiting for events that only another process can trigger. Another way of phrasing this is that a Waiting process cannot exit from Waiting because it is waiting for another resource held by another Waiting process.

A resource in a system can be anything from Memory, to CPU cycles, files and I/O devices. A resource can have multiple instances. For example, a multiple processor system has multiple instances of the CPU resource. Typically a process only needs to request for a resource TYPE, and it will be allocated any of those INSTANCES.

The usage of a process can be summarized as follows:
Request - The process request for the resource. If it is granted, the resource is locked. If it is not granted immediately, the process is put into Waiting state.

Use - The process operates and uses the resource.

Release - The process releases the resource.

The Request and Release can represent the requesting and releasing of devices, opening and closing of files and allocation and freeding of memory. These requests and releases can be accomplished using wait and signal of Semaphores.

A Deadlock requires four conditions to hold true simultaneously to occur:
Mutual Exclusion - At least one resource is held in a non-sharable mode. Another requesting process must wait for this resource to be released.

Hold and Wait - A process holding a resource is waiting for another resource held by another process.

No Preemption - Held resources cannot be preempted.

Circular Wait - In an example set of three processes, P0 waits for P1, while P1 wait for P2, and P2 wait for P0. This also implies the Hold and Wait condition.

A resource-allocation graph is defined by a set of vertices (dots) and a set of edges (lines).

An example of a resource-allocation graph is as follows (taken from Seminar Slide 5-36):

In this case, the Boxes represent Resource TYPEs, and the Dots (Vertices) in the Boxes represent INSTANCES of that resource. The Circles (Vertices) represent Processes. The edge P -> R is a request edge, and the edge R -> P is an assignment edge. A request edge is transformed into an assignment edge once the previous process has released it.

Notice that a request is always for a TYPE, so it points to the square. INSTANCES are always assigned, so it comes from a Dot instead of a Square.

In the diagram:

P1 has 1xR2, and needs 1xR1 held by P2. P1 is waiting for P2.
P2 has 1xR1, 1xR2, and needs 1xR3 held by P3. P2 is waiting for P3.
P3 has 1xR3. It does not need anything else.

From the definition of a deadlock, no processes are deadlocked because there is #1 Mutual Exclusion, #2 Hold and Wait, #3 No Preemption but there is no #4 Circular Wait. Therefore, it is only a matter of time before P3 releases R3 for P2, which allows P2 to complete its operations and release R2 for P1.

Note that a cycle may not mean that a Deadlock has occurred. If there are multiple instances of a resource and a cycle exists, there may not be a deadlock. Consider the following diagram:

We observe the following cycle:
P1 -> R1 -> P3 -> R2 -> P1

However, the cycle may be resolved through:
P1 -> R1 -> P2
P3 -> R2 -> P4

Deadlock only occurs when ALL processes in a set are under Circular Wait. In this case, even though P1 and P3 are under circular wait, P2 and P4 may release the resources. There is therefore no Deadlock.

2011-02-22T07:23:00.009+08:00

CAOS 02

We're now going to talk about a Process Synchronization tool known as Semaphores and how it relates to Deadlocks. The previous solutions require something known as the Busy Waiting, which means to continuously loop on a while() loop while the condition is not met. Even though it works, it is extremely processor-inefficient.

Another method is to allow the processes to share a common Semaphore struct. This Semaphore struct is defined as such:

typedef struct
{
int value;
struct process *L;
} semaphore;

In this case, each Semaphore has a value, typically representing the number of items in a List (representing a Queue) depending on its negative magnitude, and a list of processes.

The Semaphores can be modified only through two atomic operations: wait(semaphore S) and signal (semaphore S). These are the two functions:

void wait (semaphore S, process P)
{
S.value--;
if (S.value < 0)
{
S.L.add(P);
block(P);
}
}

void signal (semaphore S)
{
S.value++;
if (S.value <= 0)
{
P = S.L.remove();
wakeup(P);
}
}

Think of L as a stack and P is a process's PCB0. Think of "value" as whether there is Mutual Exclusion. When wait() is called and "value" is 1, the process can proceed after changing the value to 0. If a value is 0 or less, then the process will go into Waiting state through block(), add itself into the L stack associated with the Semaphore, and it will add its count into the value. This is called when a process wants to enter critical section (if you recall, it means that it's a Entry Section operation).

signal() simply allows a previously waiting program to be popped from the stack and be put into the Ready Queue. It is typically called after a process completes its Critical Section (it is a Exit Section operation).

The Achilles' Heel of Semaphores is also the existence of a condition that may cause indefinite waiting. Let us look at two processes, P0 and P1, which require two resources to complete an operation. These resources are represented by Semaphores S0 and S1.

The processes look like this:

P0          P1
wait(S0);   wait(S1);
wait(S1);   wait(S0);
signal(S0); signal(S1);
signal(S1); signal(S0);

In this case, P0 and P1 both execute wait(S0) and wait(S1) respectively, so the Semaphore's values would both change to 0. They both then execute wait(S1) and wait(S0). Because the Semaphores have a value of 0 at this point, both processes are blocked indefinitely.

If this sounds like a familiar problem, you may recall something like this in Algorithm 2 in the previous post. This is known as a Deadlock! A Deadlock is said to occur when every process in the set is waiting for an event that can only be caused by another process in the set. In this case, that process is the "signal" process. According to the textbook, the main cause of Deadlocks are "Resource Acquisition and Release" (though other events cause that too).

Starvation, or Indefinite Blocking, is when a process is never removed from the queue in which it is suspended. This can be caused when the programs are removed in a LIFO order.

We now deal with Semaphores which values can only be 0 or 1. This type of Semaphores are known as Binary Semaphores.

As you may recall in the previous Article, we spoke of a "fish" variable that was incremented or decremented by two processes. This is actually an Unbounded-Buffer Producer/Consumer problem, where P0 is the producer and P1 is the consumer. In the Producer/Consumer problem, a Producer produces data, such as a program producing characters to print, and a Consumer consumes data, such as a printer driver removing the characters and printing it. Unbounded-Buffer simply means that there exists no limits on how much data space is available for the Producer to produce.

We now look at the Bounded-Buffer problem, where there exists a cap on how much a producer can produce at one time. In this case, the producer must check to see if a buffer is empty. If it's empty, it will produce. If not, it will skip.

The same applies the other way round. The consumer checks to see if a buffer is full. If it's full, it will consume. If not, it will skip.

We can implement this by having three different Semaphores at work. An empty (init 1) semaphore, a full semaphore (init 0), and a mutex semaphore (init 1).

The Producer can then be implemented as such:

do
{
wait(empty);
wait(mutex);
//Write to buffer
criticalSection();
signal(mutex);
signal(full);
} while (1);

Similarly, the Consumer can be implemented as such:

do
{
wait(full);
wait(mutex);
//Read from buffer
criticalSection();
signal(mutex);
signal(empty);
} while (1);

We also look at another problem related to file reading and writing known as the Readers-Writers problem. If multiple readers read a file, there exists no adverse effects. However, if any reader or writer attempts to access a file while it's being written, it will have adverse consequences.

There are two basic ways to approach this problem. One is to give priority to readers (it may not be written while there is at least 1 reader), while one is to give priority to writers (writers are allowed to write as soon as possible).

The solution to the first process is as follows.

We have two semaphores, mutex (init 1) and wrt (init 1) and a readCount counter that counts the number of readers.

In this case, we have a simple Writer process:

do
{
wait(wrt);
criticalSection();
signal(wrt);
} while(1);

On the other hand, we have a complex Reader process:
do
{
//Mutual Exclusion for readCount variable
wait(mutex);
//Add itself to the number of readers
readCount++;
//If it is the first reader
if (readCount == 1)
{
//Restrict the writer from writing
wait(wrt);
}
signal(mutex);
read();
//Mutual Exclusion for readCount variable
wait(mutex);
//Subtract itself from the number of readers
readCount--;
//If it is the last reader
if (readCount==0)
{
//The writer may now write
signal(wrt);
}
signal(mutex);
} while (1);

2011-02-21T20:13:00.005+08:00

CAOS 01

This is the first time I'm going to write an article about a school subject. Why? I guess it's because I really need to pass this one. I'm first going to start from the middle, then work my way back to the earlier topics.

Let's first talk about Process Synchronization, and what it actually means. A cooperating process is a process that can affect or be affected by another process in the system. A cooperating process can share a logical address space (code and data in RAM), or only data through files. However, this concurrent access behavior would give rise to data inconsistencies. This problem is solved through various mechanisms to ensure orderly execution of cooperating processes.

Here is an example of a problem faced by improper process synchronization. Suppose that we have two processes that wishes to increment a variable "fish".

Process A:
fish++;

Process B:
fish--;

The operation "fish++" is typically implemented in Machine Language like this:

register1 = fish;
register1 = register1 + 1;
fish = register1;

And the operation "fish--" can be implemented like this:

register2 = fish;
register2 = register2 - 1;
fish = register2;

Now, if the two processes are allowed to execute this fish++ and fish-- at the same time, you may have the instructions interleave like this:

register1 = fish;
register2 = fish;
register1 = register1 + 1;
register2 = register2 - 1;
fish = register2;
fish = register1;

Suppose that "fish" has a value of 3 at first. In the end, "fish" may be either 2, if process 1 finishes first, or 4, if process 2 finishes first.

This problem is known as the Race Condition. In other words, the Race Condition is a problem whereby the final value of the shared data depends on which of the multiple processes accessing it finishes last.

To prevent the Race Condition, we need to make sure that only one process can modify "fish" at one time. In other words, we would have to make sure that processes are performed atomically - An atomic operation is an operation that completes in its entirety without interruption (taken from Seminar slide 5-8).

To solve the Race Condition problem, we would need to employ Process Synchronization and Coordination algorithms. In other words - The concurrent processes need to be Synchronized (taken from Seminar slide 5-12).

The first step to resolve the Race Condition is to implement a Critical Section in a process. The Critical Section is a section of a process code that is typically used for modifying shared data (such as changing common variables, updating a table, writing a file, etc.). The general rule to the Critical Section is that when one process is in its Critical Section, then no other processes can be in the Critical Section.

Thus, the most important rule in the Critical-Section system is that execution of the Critical Section of processes must be Mutually Exclusive.

Before a program can enter into its Critical Section, it must request for it. This code is implemented in the program's Entry Section. When the program is finished, it will go through the Exit Section. Finally, it goes into the Remainder Section typically to modify non-shared data and operations.

From the textbook, each program looks like this:

do
{
sectionEntry();
sectionCritical();
sectionExit();
sectionRemainder();
} while (1);

In total, a critical-section system must satisfy the following three requirements:
1) Mutual Exclusion: If a process is executing in its critical selection, then no other processes can be executing in their critical sections.

In other words, if a process is writing a shared data, then no other process can do that until it is done.

2) Progress: If no process is executing in its critical section, and some processes wish to enter their critical sections, then only those processes that are not executing in their remainder section can participate in the decision on which of those processes would enter its critical section next. This selection cannot be postponed indefinitely.

In other words, processes should be allowed to proceed into the Critical Section if it is ready and no other processes are in the Critical Section.

3) Bounded Waiting: There exists a bound on the number of times that other processes are allowed to enter their critical sections after a process has made a request to enter its critical section and before that request is granted.

In other words, a process cannot be permanently waiting for entry into its critical section.

We now look at how the three requirements are met by looking at algorithms designed for two processes.

Assume there are 2 processes, P0 and P1. In the first algorithm, a shared "turn" variable is used by both processes to check whether it is allowed to execute. In this case, the code looks like this:

P0:

do
{
//Entry: Stall while it is not its turn
while (turn=1);
sectionCritical();
//Exit: Change turn to the other side
turn = 1;
sectionRemainder();
} while (1);

P1:

do
{
//Entry: Stall while it is not its turn
while (turn=0);
sectionCritical();
//Exit: Change turn to the other side
turn = 0;
sectionRemainder();
} while (1);

As long as its not the process's turn, it will not execute its critical section, so there is Mutual Exclusion here. However, there is a problem here. If it is Turn 0, and P1 wants to enter its Critical Section, it must wait for P0 to complete its Critical Section before P1 can begin. In this case, both processes MUST execute Critical Sections in an alternating order. Progress is not met here.

The problem with Algorithm 1 is that it does not provide enough information as to whether the other processes are ready for their Critical Sections. So even if it is not ready, other processes would not know. The solution is to create a flag that stores each process's readiness. Now with a "boolean flag[2]", we have Algorithm 2:

P0:

do
{
//Entry: Signal that the process is ready for Critical Section
flag[0]=true;
//Entry: Stall while another process is ready for Critical Section
while (flag[1]);
sectionCritical();
//Exit: Signal that it is done
flag[0]=false;
sectionRemainder();
} while (1);

P1:

do
{
//Entry: Signal that the process is ready for Critical Section
flag[1]=true;
//Entry: Stall while another process is ready for Critical Section
while (flag[0]);
sectionCritical();
//Exit: Signal that it is done
flag[1]=false;
sectionRemainder();
} while (1);

In this case, even though processes now know that they can proceed if the other side is not ready, there exists a condition whereby an indefinite stalling occurs due to both processes having their flag set (flag[0]=flag[1]=true). This satisfies Mutual Exclusion, but Progress is not satisfied due to the Achilles' Heel of the stuck condition.

The third algorithm uses a combination of the first and second, with the "turn" variable being used differently. The third algorithm is as follows:

P0:

do
{
//Entry: Signal that it is ready
flag[0] = true;
//Entry: Race condition to set turn to the other process
turn = 1;
//Entry: Stall while it's not its own turn AND the other side is ready
while (flag[1]&&turn==1);
sectionCritical();
//Exit: Signal that it is done
flag[0] = false;
sectionRemainder();
} while (1);

P1:

do
{
//Entry: Signal that it is ready
flag[1] = true;
//Entry: Race condition to set turn to the other process
turn = 0;
//Entry: Stall while it's not its own turn AND the other side is ready
while (flag[0]&&turn==0);
sectionCritical();
//Exit: Signal that it is done
flag[1] = false;
sectionRemainder();
} while (1);

In this case, even if both processes set their flags to true, the turn variable would only be set to either 0 or 1. Whoever first executes that statement gets to go first. If only P0 is ready to enter, then flag[1]==false and turn==1 so the while statement evaluates to false, thus P0 enters critical section. In this case, only one process can enter so there is Mutual Exclusion.

P0 will enter the critical section if P1 is not ready, which satisfies progress.

Also, if both processes are ready, P0 will not indefinitely starve P1. If both processes are ready, P1 will execute after the most 1 critical section execution by P0, which satisfies Bounded Waiting.

2010-12-05T01:29:00.008+08:00

Misc 51

I've created a ARP Spoofing suite known as GARPS (Gratuitous Address Resolution Protocol Spoofer). I'm not going to go through how it works (or better yet how to program it) because I'll need to sleep soon, but I'll show you how the program can be used.

Here's a screenshot of the program without any parameters passed. As you can see, it lists the RPCAP device descriptions. I'll be using interface #3 for the attack.

I have a WRT54G Router with Tomato 1.28 firmware, a Windows Vista Host, and a Windows 7 Ultimate Attacker. First of all, I would like to poison my Router and a Host. The Router in this case would be 192.168.1.1, and the Host would be 192.168.1.151. I'll be spoofing ARPs with the MAC address of 1C-6F-65-3F-D4-F8. I programmed a wizard which you can use to quickly generate attack scripts.

Now the script can be run to quickly poison the two hosts to route through my system. The script looks like this:

After the script is run, the router's entry is immediately poisoned. Notice that the Host's MAC entry is replaced with my system's:

Now, a traceroute to the host from the router shows something weird. It's actually going THROUGH 192.168.1.150 to get to 192.168.1.151 even though it's in the same subnet.

Here on my sad host, we have some happy results. Notice that internet and normal routing still works, and the host wouldn't even notice until he does a traceroute and find out that there's an extra hop in between. There's probably ways to hide it as well (such as Layer 2 APR).

With that being said, I can now officially laugh at script kiddies. I'm probably going to write more from here on. Maybe one day I'll be a famous hacker (or if I'm more successful, then I'm never going to be famous).

2010-11-22T09:49:00.010+08:00

Misc 50

Today I'm in the mood for some protocol analysis. We'll take a look at the TCP protocol. I'm not going to tell you again that TCP stands for Transmission Control Protocol and it is connection-oriented and reliable, but I just did.

You're probably familiar by now with how a TCP connection initiates. The first three packet of a connection is used to synchronize the sequence numbers. This is also known as the Three-Way Handshake. The Three-Way Handshake goes like this:

Client                              Server
|                 ISNc=500, SYN --> |
| <-- ISNs=2000, ACKs=501, SYN, ACK |
|                ACKc=2001, ACK --> |

This is all we know, don't we? What happens after that? Now, here's where I fill you in. From this point onwards, all packets will have the ACK bit set. The initiator usually begins sending data now. For example, if we're connecting to a web server, than the initiator would be sending a GET request as the first packet.

This is how TCP works: Whenever TCP receives a packet, it does not immediately send it to the application. TCP actually buffers and reassembles the data while waiting for a packet with the PSH bit. The PSH bit, which stands for Push, actually tells the protocol to send the assembled data to the upper layers (which in this case, only means the application).

A GET request is pretty small, so a single TCP segment would suffice. Therefore, you would notice that the first GET request is actually flagged as ACK and PSH at the same time.

Source: 192.168.1.150
Destination: 209.85.132.104
TCP: ACK, PSH
SEQ: 1
ACK: 1
Total Size (including headers): 958 Bytes

After a PSH, the receiving end would send a blank ACK to signal that it has successfully received and reassembled the entire sequence.

Destination: 209.85.132.104
Source: 192.168.1.150
TCP: ACK
SEQ: 1
ACK: 959
Data: None
Total Size (including headers): 0 Bytes

Now, as a website cannot fit into a single TCP segment, here is where things get interesting. The data is actually sent by chunks, with the last chunk flagged with PSH:

Destination: 209.85.132.104
Source: 192.168.1.150
TCP: ACK
SEQ: 1
ACK: 959
Data: None
Total Size (including headers): 1430 Bytes

Destination: 209.85.132.104
Source: 192.168.1.150
TCP: ACK
SEQ: 1431
ACK: 959
Data: None
Total Size (including headers): 1430 Bytes

Destination: 209.85.132.104
Source: 192.168.1.150
TCP: ACK, PSH
SEQ: 2861
ACK: 959
Data: None
Total Size (including headers): 1008 Bytes

The last three packets actually represent the returned web page in gzip compressed format! Notice that the ACK number is the same through the three packet as the client hasn't communicated with the server. Guess what's the next packet? Well, if you said a blank ACK, you're right! And if you guessed that the ACK number is 3869 (2861+1008), you'd also be right!

Destination: 192.168.1.150
Source: 209.85.132.104
TCP: ACK
SEQ: 3869
ACK: 959
Data: None
Total Size (including headers): 0 Bytes

Now if you're wondering why it isn't 3870 instead, it is because the first byte sent is the 2861th byte, so the 1008th byte would be the 3868th byte sent, therefore the next sequence would be 3869.

When a server sends a packet with TCP Sequence 1 with a payload of 3 bytes, the first byte is the first sequence, so the third byte is third sequence, therefore the Acknowledgment would be 4. Therefore, Next ACK = Sequence + Payload Size in Bytes.

The volley continues in the same manner:
-ACKc Data
-ACKc Data
-ACKc Data
-ACKc PSHc Data
-ACKs
-ACKs Data
-ACKs Data
-ACKs PSHs Data
-ACKc
-...

TCP connections are terminated one way. This means that even if one side sends a FIN, the other side can continue to send data and the finished side can still receive until the sending side sends a FIN as well.

If one side has finished, while the other side has not, it is considered a half-open connection as well. Termination can be completed with a Four-Way Handshake:
1) FIN
2) ACK
3) FIN
4) ACK

Or, it can be completed with a Three-Way Handshake:
1) FIN
2) FIN ACK
3) ACK

2010-11-14T17:08:00.003+08:00

CCNP BSCI 23

We learned that Multicast allows one to send one data stream to multiple hosts. However, how a router handles such traffic is a mystery to us all. Recall that in IPv4, there are three ways to send data:
-Unicast - One to One
-Broadcast - One to All
-Multicast - One to Selected Group

An example of a Multicast application is Norton Ghost. In a normal Fast Ethernet switched network comprising of 20 computers, imaging each computer with Unicast would result in a gross bandwidth of 100Mbps/20=5Mbps for each system. For each computer, a unique traffic stream is required, so 20 identical streams would be sent out if one used Unicast.

Broadcast is much better when it comes to this. When imaging with Broadcast, a single stream is sent out which is received by all computers in the network. All computers would have a gross bandwidth of 100Mbps. However, even computers that didn't need the imaging would have their links clogged.

The good thing about Multicast is that it's the best of both worlds. It allows a single stream to be split into multiple streams destined for only selected hosts. In IPv6, there no longer is Broadcast. Multicast has completely replaced it.

All Multicast communication uses UDP. Multicast addresses lie in the Class D range (224.0.0.0 to 239.255.255.255). Systems would need to subscribe to a Multicast server before it can receive the streaming data. This is analogously similar to a user tuning their radio to receive sound from a particular frequency.

The entire 224.0.0.0/24 range is reserved by IANA. A list of current Multicast addresses can be viewed here. Here are a few well-known Multicast addresses:
-224.0.0.1: All Multicast-capable hosts in subnet (Replacement for Broadcast)
-224.0.0.2: All Multicast-capable routers in subnet
-224.0.0.5: OSPF
-224.0.0.5: OSPF DR/BDR
-224.0.0.9: RIPv2 Routers
-224.0.0.10: EIGRP

Multicast Global range is from 224.0.1.0 to 238.255.255.255. It is originally designed for the MBone (Multicast Backbone). MBone, however, is a dead concept. Global addresses are always assigned dynamically.

The Private Multicast range goes from 239.0.0.0 to 239.255.255.255. It is designed for private use within an organization and can be statically assigned.

We'll first talk about IGMP. There are three major versions of IGMP and IGMPv2 is the most popular. When a client wants to look for a Multicast server, it sends an IGMP message to the router. It's then the router's job to search for the best path to the server, then subscribe to it.

In IGMPv1, servers would occasionally send Query messages to clients to check if they are still listening to the stream. Once the clients stop responding to Query messages, it would send a Stop message to the upstream routers and so on. In IGMPv2, the clients have the ability to stop the stream if they no longer need it without waiting for the Query message to time the stream out. IGMPv3 allows the clients to choose the source of the stream with the Unicast address (e.g. I want 224.1.0.5 from 16.25.10.10).

By default, switches treat Multicast messages the same as Broadcast. Cisco uses the proprietary CGMP (Cisco Group Management Protocol) on their routers and switches. As the stream returns from the internet, it is accompanied with a CGMP message. The CGMP message tells the switch of the Multicast MAC address of the client. This is Cisco's way of making a switch Multicast-aware without being a full Layer 3 device.

The second method is IGMP snooping which allows the switch to interpret passing IGMP messages. This adds a processing load on the switch. IGMP snooping can only be enabled on a Layer 3 Switch.

Normal routing protocols do not work for Multicast. Multicast routing, however, is heavily reliant on the Unicast table. Multicast is routed with two types of protocols: Source Trees and Shared Trees. For Multicast, we're more concerned about the source than the destination.

There is a Loop prevention mechanism known as RPF (Reverse Path Forwarding). The router simply chooses the best interface to reach the server. Any multicast packets coming in from interfaces other than the RPF-tagged interface would be dropped.

In the source tree system, every router tracks every Multicast source. Every Multicast source is mapped with a Unicast address. Every single router along the path to the clients would map it like this. Every client would also be mapped. The routers would then be able to route the packets around according to the Unicast table.

Source tree configuration is very easy to set up, but becomes extremely large if it's used in the Internet.

In the Shared tree world, one router would be elected as the RP (Rendezvous Point). The servers would all stream towards the RP, and clients would all request the stream from the RP. The Shared tree design is efficient because not all routers need to keep track of every single Multicast source, but because of the RP location some hosts may not get the best path.

The two main Multicast routing protocols in use are: PIM Dense Mode, PIM Sparse Mode. Dense Mode uses a Source Tree algorithm, while Sparse Mode uses the Shared Tree algorithm. Dense Mode is like RIP: You simply turn it on and it works.

In Dense Mode, whenever a server starts streaming, the router would flood the entire stream through the network. The routers would then send back Prune messages towards the source if there are no clients in need of the stream. Typically only a few packets get flooded, so it's not as inefficient as one might think.

PIM Sparse Mode requires setting of a Rendezvous Point. There is a mechanism known as Auto-RP to automatically propagate the RP address.

To enable Multicasting on a router, we'll need to type:
ip multicast-routing

By default, Multicast packets are dropped. You'll need to turn it on before the packets get through. We'll now need to turn on Multicast routing under specific interfaces. Here I'll use Dense Mode:

in f0/0
ip pim dense

At the "ip pim" menu, you'll be able to also run Sparse-Dense-Mode which runs both modes (e.g. Bush out AND set RP).

If you're running Sparse Mode, we'll need to go back to Global Configuration and type:
ip pim rp-address ADDRESS

You can also automatically announce that the router is RP by using:
ip pim send-rp-announce

On other routers, you'll need to type:
ip pim send-rp-discovery scope 10

2010-11-11T21:17:00.002+08:00

CCNP BSCI 22

I'm going to go through BGP Attributes with the topology we used in the previous article:

I redrew the topology diagram to look a little neater. I also replaced all Serial links with straight lines so that it looks neater, but they're all still Serial links. Finally I've included the point-to-point subnet addresses for the various Serial links. The lower router number will get the first address of each point-to-point subnet. R4 and R6 are not neighbors so that you'll get two separate links. R2 and R3 are also not neighbors for the same reason.

We'll start from full configuration between AS 2, 3, and 4. R2 and R3 also has EBGP relationships with R3 and R6.

We'll begin configuration of the local Autonomous System (AS 1). Since the local AS only runs IBGP, you'll have to turn off Synchronization for all R1, R2 and R3:

no sync
end
clear ip bgp *

On all routers, we'll create a peer group as shown:

neighbor AS1 peer-group
neighbor AS1 remote-as 1
neighbor AS1 next-hop-self

On R1, we'll add R2 and R3 as neighbors:

neighbor 10.0.0.2 peer-group AS1
neighbor 10.0.0.6 peer-group AS1

We'll add R1 on R2:
neighbor 10.0.0.1 peer-group AS1

And finally, we'll add R1 on R3:
neighbor 10.0.0.5 peer-group AS1

You would have 8 routes, with 4 going to 30.0.x.0/24 and 4 going to 40.0.x.0/24.

At this point, the 30.0.x.0/24 networks would preferably be going through:
AS 2 3 4 ?
>AS 2 3 ?

The route to 40.0.x.0/24 would then be going through:
AS 2 4 3 i
>AS 2 4 i

Now we'll begin the first tuning of the BGP attributes. The first thing we can set is the Cisco proprietary Weight attribute. Weight is local to the router. Higher Weight routes are preferred, and the default Weight is 0.

To set the weight, we'll use:

neighbor 10.0.0.2 weight 500
end
clear ip bgp *

What the above command does is to prefer routes coming from R2. If you check the topology table (with "show ip bgp"), you'd see that the routes coming from R2 are now preferred with the > symbol.

The preferred path to the 40.0.x.0/24 networks is now:
AS 2 3 4 i

We'll now remove the Weight command:

no neighbor 10.0.0.2 weight 500
end
clear ip bgp *

Now, if we wish to temporarily disable a neighbor, we do not have to remove all the neighbor statements. We can simply type:
neighbor 10.0.0.2 shutdown

This would restrict the neighbor relationship but will still retain the configurations so that it can be quickly brought back up using:
no neighbor 10.0.0.2 shutdown

The origin is where a route came from. You can check the origin of a route using:
show ip bgp

Routes originated with the "network" command will be marked with "i". Routes originated with the "redistribute" command will be marked with "?".

We'll now talk about Local Preference. Local Preference is the industry standard method to modify route preferences in the AS. Local Preference is similar to Weight, but it's transitive within the AS.

If we wish all routes from R2 to be preferred Locally, we'll simply go into R2. From the BGP context, we'll type:

bgp default local-preference 101
end
clear ip bgp *

If we check back on R1, we'll see that the local preference for R2's routes are marked as 101 and the routes would be preferred.

You can change Local Preference for specific routes only. To do this, we'll need route-maps. We'll make R2 the preferred router for the 40.0.x.0/24 network and R3 the preferred router for the 30.0.x.0/24 network.

On R2, we'll make an access-list matching the 40.0.x.0/24 network:

ip access-l standard AS4
permit ip 40.0.0.0 0.0.1.255

We'll then create one for AS3's routes as well:

ip access-l standard AS3
permit ip 30.0.0.0 0.0.1.255

Now we'll make a route-map:

route-map LOCAL_PREFERENCE permit 10
match ip address AS4
set local-preference 101
route-map LOCAL_PREFERENCE permit 20
match ip address AS3
set local-preference 99
route-map LOCAL_PREFERENCE permit 30

We'll now apply the route-map on R2:
neighbor 10.0.0.10 route-map LOCAL_PREFERENCE in

10.0.0.10 is the IP of R4. At this point, R2 will automatically be preferred for 40.0.x.0/24 networks, while R3 will be the router for 30.0.x.0/24.

Now, notice that I made the incoming routes from R4 a higher local preference rather than outgoing routes to R1. This is so that R2 itself would be affected as well. If we actually change only the outgoing routes to R1, then R2's local preferences for those routes would still be default.

The Multi-Exit Discriminator or MED is also known as "Metric" in BGP. MED is used for "suggesting" which Exit to use if there are multiple entrances/exits into the same organization. The lowest MED is preferred. The way to remember this is to remember MED as a metric in a normal routing protocol, where lower is better.

The MED can be set with two methods as well. The first method is to go to the BGP context and type:
default-metric 100

This actually makes it less preferred than default. We'll also be able to set the MED for specific routes using route-maps just like how we did for Local Preference. For example, we can do a "match ip address ACCESS-LIST", then use a "set metric 100".

Don't you just love BGP?

2010-11-11T19:36:00.005+08:00

CCNP BSCI 21

Now we're finally going to talk about BGP Attributes. BGP is the biggest protocol in the world and BGP Attributes is how it finds its way around. BGP Attributes represents the mother of all metrics and it is very complicated.

BGP Attributes are ways you can "label" prefixes learned from BGP. You can modify both incoming and outgoing prefix attributes.

Some attributes are well-known, while some others are optional. Well-known means that every vendor must support it. Attributes can also be mandatory or discretionary. Mandatory attributes are well-known attributes that are compulsory. Finally, some attributes can be transitive while others are non-transitive. Transitive attributes are attributes that can travel through the routers distributing the prefixes.

The Major Well-Known Attributes (all vendors must support them) are:
-Autonomous System Path (AS-PATH) (Mandatory)
-Next Hop Address (Mandatory)
-Origin (Mandatory)
-Local Preference
-Atomic Aggregate

Cisco's Optional Attributes are:
-Aggregator
-Multi-Exit Discriminator (MED)

The Autonomous System Path is the attribute that contains a list of all the Autonomous Systems the particular prefix traversed. The lowest AS_PATH is preferred. As such, this behaves like Hop Counts.

The Next Hop Address is the "gateway" to get to the prefix. This qualifies or disqualifies a route depending on whether the Next Hop Address is reachable or not. (Recall that the routes are ignored when IBGP didn't change the next-hop to itself in the previous articles).

Origin is the Autonomous System where the prefix came from. Local Preference is how preferred the route is within the local Autonomous System.

Now, that's just 7 out of the countless Attributes a prefix can have. The BGP process actually decides on which route to keep based on the following:
0. Ignore routes with an inaccessible next hop address
1. Prefer the path with the highest WEIGHT.
2. Prefer the path with the highest LOCAL_PREF.
3. Prefer the path that is local to the router (via a "network", "redistribute" or "aggregate" command).
4. Prefer the path with the shortest AS_PATH.
5. Prefer the path with the lowest origin type.
6. Prefer the path with the lowest multi-exit discriminator.
7. Prefer eBGP over iBGP paths.
8. Prefer the path with the lowest IGP metric to the next hop address.
9. Determine if multiple paths require installation in the routing table for BGP Multipath.
11. Prefer the route that comes from the BGP router with the lowest router ID.
12. Prefer the path with minimum cluster list length if the originator is the same for multiple paths.
13. Prefer the path that comes from the lowest neighbor address.

WEIGHT is a Cisco proprietary attribute that is local to a router. Yes, it does not leave the router at all, so it can be seen as a ROUTER_PREFERENCE instead.

LOCAL_PREF is a Well-Known Mandatory attribute that is advertised to routers in the same AS. LOCAL_PREF and WEIGHT are tied by default so it must be set by an Administrator for it to work.

The BSCI examination focuses on the first 4 steps in the Best Path Selection Algorithm.

Lets begin a more detailed study of the BGP process using the following topology:

We'll be focusing on the 172.16.1.0/24 prefix as received on R1. After the network stabilizes, R1 will eventually receive two different paths to the 172.16.1.0/24 network. We can see this information using:
show ip bgp

Path 1 goes to R2 then to AS 2 3 4 i
Path 2 goes to R3 then to AS 3 4 i

Both paths have the Next Hop set to the respective routers due to the "next-hop-self" command. By default, Metric (0), LocPrf (100) and Weight (0) are all set to default so the path with the shortest AS_PATH gets selected. In this case, Path 2 is marked with the > symbol which means it's preferred.

All routers in the BGP process typically have the same routing table when it comes to routing to external routes. In this case, traffic originating from R1, R2 and R3 destined for the 172.16.1.0/24 network would always cross the link to R6.

As this would result in a full-blown discussion, I'll elaborate more on this topology in the next article where we'll play around with the attributes.

2010-11-10T11:14:00.004+08:00

Java 03

In this article, I'm going to talk about Power Management Event. Power Management Event is a PCI 2.2 standard that allows network cards to receive Wake-on-LAN packets without the need for a WOL cable.

NICs can receive these PME packets from any of the computer sleepstates. Recall that a computer can be in one of five main powered states, of which three are of interest:
S3 - Suspend to RAM. This refers to "Sleep"
S4 - Suspend to Harddisk. This refers to "Hibernate"
S5 - Soft Off. This refers to "Shut Down"

S5 is referred to as Soft Off because although most of the components are turned off, some components can still be powered to receive signal to turn it on. There is another similar mode known as G3 mode in which a power is Mechanically Off, leaving only the RTC powered by an onboard battery.

When the computer is fully turned on, it is said to be in S0 mode.

In all states, with the exception of G3, compliant NIC cards are capable of receiving Magic Packets. A Magic Packet is simply a formatted UDP packet that causes a computer to switch to S0 mode. Magic Packets are typically received on UDP ports 0, 7 or 9.

For a computer to successfully perform WOL, the following conditions must be satisfied:
-Computer in a non-G3 state
-BIOS configured for PME/WOL
-Routing/Switching equipment must forward to correct interface
-Payload must follow proper format

We'll first talk about configuring the BIOS for WOL. During bootup, you can access your BIOS with the DEL key on most motherboards. Once you're the BIOS configuration, you would have to go under the Power Management section. Make sure that WOL is turned on and allowed. Note that on certain motherboards like Gigabyte P55A-UD3, it is referred to as PME instead.

A typical home router is actually a router with one routed and multiple switched interfaces. This essentially makes it a layer 3 switch. For a switch to forward the packet to the correct interface, it must already learn the MAC of the host.

Typically people forward port 9 to the IP address of the WOL host. However, before the router can successfully send the packet to the host, it must first ARP for the host's MAC address. If the host is turned off, it does not have an IP address, and therefore the host would not reply to the ARP request. The packet would then be dropped.

The trick here is to actually send the WOL packet out of all the ports. To do this, a static host must be configured with the broadcast MAC address of FF:FF:FF:FF:FF:FF. Any packet going to that static host would be sent out of all interfaces.

To do this on a Linux-based router like a router belonging to the WRT54G/GS/GL series, you would type this command:
ip neigh add 192.168.1.254 lladdr ff:ff:ff:ff:ff:ff nud permanent dev br0

On a Cisco equipment, you should use this command instead:
arp 192.168.1.254 ffff.ffff.ffff arpa

Since this must be typed every single time the router starts up, you should put it in the Init scripts. Note that you would have to use an address that would never be occupied by a host, or strange things would start to happen whenever communication to the host is required.

Now you can forward UDP port 9 to the 192.168.1.254 address from the router's GUI. In this arrangement, anything sent to port 9 would be broadcasted out all interfaces.

We'll now talk about the Magic Packet. The Magic Packet is a UDP packet with a sync stream and a MAC portion. The sync stream is simply a series of 1's spanning 6 bytes. The MAC portion is simply the MAC address of the WOL host repeated 16 times. The resulting packet has a payload size of (6+16*6)=102-bytes.

This is a sample WOL packet:

0000   00 00 0c 07 ac 03 02 00 4c 4f 4f 50 08 00 45 00
0010   00 82 3d 8e 00 00 80 11 aa 8b 98 e2 98 4a de a4
0020   42 80 ee 91 00 09 00 6e 53 b0 ff ff ff ff ff ff
0030   1c 6f 65 3f d4 f8 1c 6f 65 3f d4 f8 1c 6f 65 3f
0040   d4 f8 1c 6f 65 3f d4 f8 1c 6f 65 3f d4 f8 1c 6f
0050   65 3f d4 f8 1c 6f 65 3f d4 f8 1c 6f 65 3f d4 f8
0060   1c 6f 65 3f d4 f8 1c 6f 65 3f d4 f8 1c 6f 65 3f
0070   d4 f8 1c 6f 65 3f d4 f8 1c 6f 65 3f d4 f8 1c 6f
0080   65 3f d4 f8 1c 6f 65 3f d4 f8 1c 6f 65 3f d4 f8

This is a 11 (UDP) packet sent from 98 e2 98 4a (152.226.152.74) to de a4 42 80 (222.164.64.128). The packet is directed at port 00 09 (9). The payload starts from "ff ff ff ff ff ff" till the end of the packet. If you count, you would see 16 repetitions of the MAC address after the sync stream.

We'll now work on the programming part. We'll start by importing the networking packages because we'll need to transmit it using UDP (DatagramPacket, DatagramSocket):
import java.net.*;

Now, we'll begin by creating the payload in a byte array. We can very quickly create it by first storing the MAC address in its own byte array, then replicating it with a for-loop into another byte array representing the payload.

We'll first create the MAC array:

String macString = "ab:cd:ef:gh:ij:kl";
String[] macStringArray = macString.split(":");
byte[] macArray = new byte[6];
for (int i=0; i<6; i++)
{
 macArray[i]=(byte)Integer.parseInt(macStringArray[i],16);
}

Next, we'll create a payload array and replicate the data through:

byte[] payload = new byte[102];
for (int i=0; i<payload.length; i++)
{
 if (i<6)
 {
  payload[i]=(byte)0xff;
 }
 else
 {
  payload[i]=macArray[i%6];
 }
}

From index 0 to 5, it would be filled with 1's. From 6 to 102, it would be filled with the MAC address of the target.

Now we'll create a Datagram packet with the payload array we have:

String inetAddressString = "syraxius.ath.cx";
InetAddress inetAddress = InetAddress.getByName(inetAddressString);
DatagramPacket datagramPacket = new DatagramPacket(payload, payload.length, inetAddress, port);

Now we can transmit by creating a DatagramSocket:

DatagramSocket datagramSocket = new DatagramSocket();
datagramSocket.send(datagramPacket);

Finally, we close the socket:
datagramSocket.close();

And there you have it!

2010-11-09T21:49:00.006+08:00

CCNP BSCI 20

If you look at the previous few articles, you'd notice that BGP actually requires a lot of commands for each neighbor. If you have multiple neighbors, you'd have to type the same commands over and over a lot of times. This is where BGP peer groups come in!

BGP peer groups allow you to quickly put multiple similar routers into the same group. This is very useful if you look at the previously used topology:

Suppose that we've decided to run IBGP on all routers in the local AS. However, this would mean that we must type the same commands used on R1 on R2 and R4 as well. The better approach is to actually create a group configuration. We'll then apply the group configuration to all IBGP neighbors.

To do this, we'll create a peer-group:

neighbor IBGPPEERGROUP peer-group
neighbor IBGPPEERGROUP remote-as 1000
neighbor IBGPPEERGROUP next-hop-self
neighbor IBGPPEERGROUP update-source lo0

We'll now add the neighbors as shown:

neighbor 10.0.1.1 peer-group IBGPPEERGROUP
neighbor 10.0.1.2 peer-group IBGPPEERGROUP
neighbor 10.0.1.4 peer-group IBGPPEERGROUP

Now, we would want to configure this into a full mesh topology. We cannot simply have R1 and R3 peer with R2 and R4. This is because of the IBGP split-horizon rule. The rule states that a route learned from IBGP would not be advertised to another IBGP neighbor. This would mean that if R2 or R4 learns of a route from R3, it would not pass it on to R1. To make them pass the routes, we would need to configure route reflectors, which is an advanced topic explained later on. For now, we'll need to configure all routers to have a full mesh neighborship with every other router.

Now, let's talk about how BGP neighbors form relationships. There are many steps and here's a summary:
1) Idle: Verifying route to neighbor
2) Active: Attempting to connect to neighbor
3) Open Sent: Open Message Sent to Neighbor
4) Open Confirm: Open Message Replied from Neighbor
5) Established

On step 4, if neighbor did not reply with a correct Open message, you would cycle back to Active instead. This is known as BGP Stuck-In-Active. (Of course, don't confuse this with EIGRP Stuck-In-Active where a broadcast storm is created while looking for backup routes.)

The first two steps take the longest time. We can actually view the neighbor forming process using the debug command:
debug ip bgp

We'll then clear the neighbor relationships using:
clear ip bgp *

This would be the typical output of a normal relationship forming process:

*Mar  1 00:05:27.971: BGP: 1.1.1.1 went from Idle to Active
*Mar  1 00:05:27.987: BGP: 1.1.1.1 open active, local address 1.1.1.2
*Mar  1 00:05:28.023: BGP: 1.1.1.1 open failed: Connection refused by remote host, open active delayed 362ms (850ms max, 87% jitter)
*Mar  1 00:05:28.387: BGP: 1.1.1.1 open active, local address 1.1.1.2
*Mar  1 00:05:28.443: BGP: 1.1.1.1 open failed: Connection refused by remote host, open active delayed 659ms (1000ms max, 87% jitter)
*Mar  1 00:05:29.107: BGP: 1.1.1.1 open active, local address 1.1.1.2
*Mar  1 00:05:29.151: BGP: 1.1.1.1 went from Active to OpenSent
*Mar  1 00:05:29.155: BGP: 1.1.1.1 sending OPEN, version 4, my as: 1, holdtime 180 seconds
*Mar  1 00:05:29.239: BGP: 1.1.1.1 rcv message type 1, length (excl. header) 26
*Mar  1 00:05:29.243: BGP: 1.1.1.1 rcv OPEN, version 4, holdtime 180 seconds
*Mar  1 00:05:29.247: BGP: 1.1.1.1 rcv OPEN w/ OPTION parameter len: 16
*Mar  1 00:05:29.247: BGP: 1.1.1.1 rcvd OPEN w/ optional parameter type 2 (Capability) len 6
*Mar  1 00:05:29.251: BGP: 1.1.1.1 OPEN has CAPABILITY code: 1, length 4
*Mar  1 00:05:29.251: BGP: 1.1.1.1 OPEN has MP_EXT CAP for afi/safi: 1/1
*Mar  1 00:05:29.255: BGP: 1.1.1.1 rcvd OPEN w/ optional parameter type 2 (Capability) len 2
*Mar  1 00:05:29.259: BGP: 1.1.1.1 OPEN has CAPABILITY code: 128, length 0
*Mar  1 00:05:29.259: BGP: 1.1.1.1 OPEN has ROUTE-REFRESH capability(old) for all address-families
*Mar  1 00:05:29.263: BGP: 1.1.1.1 rcvd OPEN w/ optional parameter type 2 (Capability) len 2
*Mar  1 00:05:29.263: BGP: 1.1.1.1 OPEN has CAPABILITY code: 2, length 0
*Mar  1 00:05:29.267: BGP: 1.1.1.1 OPEN has ROUTE-REFRESH capability(new) for all address-families
BGP: 1.1.1.1 rcvd OPEN w/ remote AS 1
*Mar  1 00:05:29.267: BGP: 1.1.1.1 went from OpenSent to OpenConfirm
*Mar  1 00:05:29.267: BGP: 1.1.1.1 went from OpenConfirm to Established
*Mar  1 00:05:29.271: %BGP-5-ADJCHANGE: neighbor 1.1.1.1 Up

Now we'll check out some BGP verification commands. The most commonly used one is:
show ip bgp

This command is used to check the BGP prefixes table. From here, you can see which routes are learned, and which of those learned routes are accepted. You can also derive information about a route to find out why it wasn't added to the topology table.

Another show command which shows more information in a summarized form is:
show ip bgp sum

The above command shows all the routes statistics (instead of actual routes) as well as neighbors relationships.

There is a very detailed way to display information about neighbors. This is typically not used unless you require the details. Most of the useful information are in the first two commands. To see detailed neighbor information, use:
show ip bgp nei

If there are routes not showing up in the routing table (a route with no caret), you can see the reason why it isn't added using:
show ip bgp rib-failure

RIB-Failure sounds disgusting, but it actually means Routing Information Base Failure.

This should be enough to get you prepared for the next few BGP articles. If you thought BGP up to this point sounds nightmarish, wait till you see the BGP Attributes.

2010-11-09T20:30:00.002+08:00

CCNP BSCI 19

BGP has auto-summarization capabilities. However, it does summarization like EIGRP and RIP, and sadly there is a bad reason why we usually type "no auto" when we get into the EIGRP or RIP process. We'll talk about how to turn auto-summarization off later in this article.

Right now I want to focus on adding networks into the BGP process. There are two ways we can do this:
-"network" command
-"redistribution" command

Now let's get back on the same topology we used in the previous article.

Suppose that R5, the ISP router, has networks at 20.0.0.0/24. and 20.0.1.0/24. If we type "network 20.0.0.0", we would actually advertise a whole class A network! We should instead use:

network 20.0.0.0 mask 255.255.255.0
network 20.0.1.0 mask 255.255.255.0

You can advertise with the network command only either the classful boundary or the exact subnet. You cannot do summarization with the "network" command. For example, "network 20.0.0.0 mask 255.254.0.0" will NOT work!

Typically IGP carries private network information, so it's not recommended to redistribute IGP routes into BGP. Redistribution should only be done when necessary and only the necessary routes should appear in the BGP process. How would we do this? If you've followed the previous articles, the first thing in your head would be Route-Maps and you would be right!

Now, let's assume that the ISP router has routes from its IGP going to 30.[0-7].0.0/16. We would only want 30.5.0.0/16 and 30.6.0.0/16 going out into BGP during redistribution. We'll create an access-list to permit those first:

ip access-l standard PERMIT_5_6
permit 30.5.0.0 0.0.255.255
permit 30.6.0.0 0.0.255.255

We can now permit using a Route-Map:

route-map REDISTRIBUTE_5_6
match ip address PERMIT_5_6

We can now redistribute OSPF with the Route-Map we created:
redistribute ospf 1 route-map REDISTRIBUTE_5_6

By default, 12.2(8)T and above have auto-summarization turned off by default. If you happen to be running an IOS below 12.2(8)T, you would have to type:
no auto

Now hop on over to R1 and check the BGP table:
show ip bgp

Notice that even though you've received the external routes from IBGP, they still may not be in the routing table. This is because of the BGP synchronization rule. BGP synchronization rule states that routes should not be used or advertised until its IGP has learnt it as well.

What this rule help prevent is the Networking Blackhole described in the previous article! BGP Synchronization is on by default in IOS versions 12.2(8)T and below. This is because Cisco assumed that if you're running IBGP, you would probably be running it contiguously, which you should!

To turn off synchronization, we should type (on all IBGP routers):
no sync

Now, even if you've disabled synchronization, it may still not be in the routing table. If we check the BGP table now ("show ip bgp"), we would notice that the route's next hop is set to R5's interface. R1 does not know how to get to R5!

By default, next-hop addresses would be changed to itself whenever a router advertises to an EBGP peer. However, next-hop addresses would remain the same if a router advertises to an IBGP peer! That explains why the next hop was still R5!

To fix this, we'll need to tell R3 to change the next-hop to itself when advertising all routes to R1. To do this, we'll go on R3 and type:
neighbor 10.0.1.3 next-hop-self

BGP has a lot of queer behaviors and you would need to know these off the top of your head if you're into both the examination or real world implementation.

2010-11-09T19:14:00.019+08:00

CCNP BSCI 18

BGP can be implemented in two different ways: IBGP and EBGP. The I and the E stands for Internal and External respectively. As how it sounds, Internal BGP refers to BGP neighbors running between the same Autonomous System. External, then, refers to BGP run between different Autonomous Systems.

Typically, an organization can obtain an Internet-legal AS number. Like IP addresses, you also have private AS numbers.

BGP redefines what we consider "neighbors". You can actually have BGP neighbors that are NOT directly connected. The routing to the other neighbors can then be done with IGPs like OSPF and RIP.

We'll do our first BGP configuration using this topology:

IBGP is commonly run on routers connected to multiple ISPs in the same AS. This is used to provide redundancy. Organizations with such redundant connections typically become a transit AS. Transit AS's become a "node" in the public routing network where public traffic goes through.

Beware, though, being a transit AS you may create Networking Blackholes if you run IBGP with non-directly-connected neighbors.

Suppose that the 12.23.34.0/24 network wants to communicate with the 23.34.45.0/24 network, and your AS is the transit AS that has the best metric, the packet would go through you.

However, remember that only the IBGP routers know about 12.23.34.0/24 and 23.34.45.0/24, so as it goes into your IGP domain, the router on the inside would not know where to route it. Therefore, the packet would be dropped! You have thus created a Networking Blackhole in the Internet where every packet in transit would be dropped!

There are three ways to solve this. The first is to simply redistribute BGP into your IGP. However, this is not recommended as IGP is not made to handle such traffic.

The second way is to have your IGP router also run IBGP. That way, they would all have the routes and would go through.

The final and recommended way is to actually have a direct link between both of your IBGP routers.

Now we'll begin some BGP basics. This will accomplish both IBGP and EBGP relationships:

For each link, the router with the lower router number will get the lower host address. All links are FastEthernet.

We'll begin configuration on the ISP router first. We'll put the ISP router in AS 2000 first:
router bgp 2000

The ISP router is 10.0.0.18/30, so R3 would be 10.0.0.17/30. We'll add R3 to the ISP's neighbors:
neighbor 10.0.0.17 remote-as 1000

There are many things you can do with a neighbor, but the first command you need to enter is the remote-as command. Other commands will not be accepted until this command is present. R5 is now attempting to connect to R3.

To see the configured neighbors, use:
show ip bgp sum

If you haven't configured the other side yet (hopefully, since you're following this), you would have the state of the neighbor written as "Active". Remember, "Active" is something bad. It means that the router is actively trying to establish the relationship.

We'll now hop over to R3 and put it in AS 1000:
router bgp 1000

The same way, we'll add R5 as a neighbor:
neighbor 10.0.0.18 remote-as 2000

You may have to wait some time for the neighborship to come up. If you check the neighbors, you'll see that the neighbor is "Idle". "Idle" means that it knows that the router is there, but it hasn't attempted to establish a connection yet.

EBGP should come up by now. We'll now configure IBGP. There's no difference in configuration, except that the remote-as of the neighbor is the same as its own. Now, assuming that OSPF is up and running, we'll add R1 to the neighbor table.

Now, for R1, there are two addresses we can use: 10.0.0.1 and 10.0.0.13. However, if we choose one and it goes down, the neighbor relationship would go down. We should use neither one of this, and instead peer with a Loopback address. The Loopback would be advertised into OSPF!

On R1, we have a Loopback address 10.0.1.1/32 advertised into OSPF. The other routers all have 10.0.1.x/32 Loopbacks advertised. We'll now peer with the Loopback from R3:
neighbor 10.0.1.1 remote-as 1000

At this point, the neighborship won't come up even if both sides are configured to use each other's Loopbacks. This is because the connection is established from a FastEthernet interface. The other side would not recognize it as a neighbor and so the relationship will not come up. The way to fix this is to change the update source:
neighbor 10.0.1.1 update-source lo0

Do this for R1 as well:

router bgp 1000
neighbor 10.0.1.3 remote-as 1000
neighbor 10.0.1.3 update-source lo0

Now they'll try to use their Loopbacks to establish the relationship with each other's Loopbacks.

Now, what if we have redundant ways to get to an ISP router? For example, what is R3 has two links to get to R4? The way to do this is to create two static route to the opposite router's Loopback interface (assuming you have another link at 10.0.0.20/30):

ip route 10.0.1.5 255.255.255.255 10.0.0.18
ip route 10.0.1.5 255.255.255.255 10.0.0.22

The ISP would also have to create two static routes back. After this is done, and even after adding each other's Loopback interfaces, and changing the update-source, the neighbor relationship would still not come up! This is because by default EBGP neighbors MUST be directly connected!

To change this, we'll need to make use of multihop. To do this, we'll need to type:
neighbor 10.0.1.5 ebgp-multihop 2

This is all the commands we'll need on R3 to peer with R5's Loopback:

ip route 10.0.1.5 255.255.255.255 10.0.0.18
ip route 10.0.1.5 255.255.255.255 10.0.0.22
router bgp 1000
neighbor 10.0.1.5 remote-as 2000
neighbor 10.0.1.5 update-source lo0
neighbor 10.0.1.5 ebgp-multihop 2

You would have to mirror the configuration for R5:

ip route 10.0.1.4 255.255.255.255 10.0.0.17
ip route 10.0.1.4 255.255.255.255 10.0.0.21
router bgp 2000
neighbor 10.0.1.4 remote-as 1000
neighbor 10.0.1.4 update-source lo0
neighbor 10.0.1.4 ebgp-multihop 2

This article focuses only on neighbor relationships. We'll talk about advertisements in future articles.

This sentence is here to test if Mr Soma would one day end up here through Google. Here's some keywords to help him out: L Somasundaram, IFC Alumni Advisor, 67805602, somasun@tp.edu.sg, Network Security, GreatSoma.

Network Security is my favorite subject! (<- I think Mr Soma came here to see this.)

On a side note, what does L stand for? I really couldn't find it in Google.

2010-11-07T20:22:00.005+08:00

CCNP BSCI 17

We'll now go into the final and biggest protocol in the world: The Border Gateway Protocol (BGP). Interior Gateway Protocols are the protocols we use to do routing internally. Exterior Gateway Protocols are protocols used to route the Internet. EGP used to be a protocol, but now it's become a category of protocols, and BGP is the only EGP protocol employed now.

BGP is used when you have multiple ISPs. When you run BGP, you're not so much concerned which direction you're going OUT. You're more concerned about how people get INTO your organization! Organizations want to make sure that they have a redundant connection for people to access their sites if ISPs go down. To do this, they'll need to advertise their public address block to the BGP domain. Such usage of more than 1 ISP is known as multi-homing.

BGP runs on top of TCP, unlike other protocols which have their own transport mechanism. TCP is used for reliability, and updates are incremental and triggered. The metric of BGP is the biggest metric in all routing protocols. The metric for BGP is the BGP Attributes. The protocol goes through 7 different attributes looking for an attribute to break the tie. It is the slowest routing protocol to converge, which is good for the Internet.

There are many styles of BGP implementation. CCNP focuses on using BGP from the perspective of the enterprise. The simplest outgoing access style is simply to have one ISP be the primary, and the other ISP be the backup, or do a simple per-conversation load-balance.

The second style of implementation is to have Partial Updates. You can selectively receive updates for blocks of addresses that are important to you. For example, you can selectively opt to receive addresses belonging to your offices in other countries.

The final style of implementation is the Full Updates. You will need to have a very powerful router to support this as you will be receiving all routes in the Internet.

BGP is technically a Distance Vector protocol, but most people call it a "Path Vector" protocol. Without tuning, BGP behaves just like RIP! The path chosen is based on the lowest number of AS they see in the AS_PATH.

BGP communicates with these types of packets:
-Open
-Keepalive
-Update
-Notification

Open packets start the session with another router. It is like the initial Hello packet.

Keepalive messages make sure that the neighbors are still around. It is like the subsequent Hello packets.

Update packets gives network reachability information. This is the bulk of messages. The messages contain "prefixes", which is another term for "routes".

Notification packets tells the neighbors of a bad event. There is no good notification. It is also used to close a session.

Below is the list of tables used by BGP:
-Neighbor Table
-BGP Table
-Routing Table

Neighbor Table keeps a list of configured neighbors. Neighbors in BGP are statically configured.

BGP Table is the list of ALL BGP routes. This is a huge table.

Routing Table keeps a list of the best routes.

2010-11-07T18:04:00.003+08:00

CCNP BSCI 16

By design, routing protocol send routes, and the protocols send the routes to all neighbors as best as they could. However, sometimes, we do not want all routes to go through. For example, if we're partnering with other organizations, we wouldn't want certain routes to go to them.

There are many ways we can manipulate route updates. We will start with the simplest of all: Distribute Lists.

Distribute Lists allow us to apply an Access-List to routing updates. It can be applied inbound or outbound under a routing process. If you do not want to see your neighbor's routes, use an inbound Distribute List. If you do not want to tell your neighbor about some routes you have, use an outbound Distribute List.

However, it works slightly differently with OSPF and IS-IS. Remember that Link State protocol needs to know about all routes in the topology table. You cannot not tell your neighbors about routes. However, you can use Distribute Lists to keep it from entering the Routing table. Therefore, you can only apply an inbound Distribute List to your Link State routing protocol process.

Suppose that we're again using the following topology:

Suppose that there are networks 10.0.[0-7].0/24 networks sitting behind R1. The network 10.0.3.0/24 is a secret lab, so it shouldn't be advertised to anyone else. Next, networks 10.0.6.0/24 and 10.0.7.0/24 should be kept within RIP domains only.

In this case, we'll need two access-lists. One is an Outbound Distribute List for R1 and another is a Redistribution Distribute List for R2.

On R1, we'll create a list that denies 10.0.3.0/24 and permits the rest. To do this, we'll type:

ip access-l standard DENY_3
deny 10.0.3.0 0.0.0.255
permit any

Now we'll need to add it into the routing process as shown:

router rip
distribute-list DENY_3 out f0/0

At this point, R2 will stop receiving 10.0.3.0/24 networks. However, you would have to wait a while for the routes to disappear from the list. If we want to clear the table, use:
clear ip route *

We'll now deny 10.0.6.0/24 and 10.0.7.0/24 from going over to the OSPF domain. To do this, we'll create a new list on R2:

ip access-l standard DENY_6_7
deny 10.0.6.0 0.0.1.255
permit any

Next, we'll filter the RIP protocol out of OSPF:

router ospf 1
distribute-list DENY_6_7 out rip
redistribute rip subnets metric 1

Another way to filter routes is through Route Maps. Route Maps operate similar to BASIC programming. Route Maps is essentially a compilation of multiple "If...Then" statements and is used heavily in BGP, Policy-Based Routing and Route Filtering.

In Route Maps, "match" correlates to "if", and "set" correlates to "then". Route Maps have sequence numbers, and it will go through the sequence numbers until a match occurs.

Here's how a Route Map looks like:

route-map ROUTE_MAP permit 10
match condition
set action
route-map ROUTE_MAP permit 20
match condition1 condition2
match condition3
set action1
set action2
route-map ROUTE_MAP deny 30
match condition
route-map ROUTE_MAP permit 40
set action

Route Maps are created in global configuration mode. The syntax is as follows:
route-map NAME <permit|deny> [SEQUENCE]

You can have many conditions in a match statement. When this happens, it's a logical-OR.

If you have multiple match statements, you have a logical-AND.

You can also have more than 1 set statements.

Anything matched by a deny entry would not be processed by the route-map.

If you do not specify a match statement, it matches everything.

Using the same scenario, we'll use a Distribute-List on R1 as usual, but on R2, we'll create a route-map to permit networks 6 and 7, then use a route-map to deny those networks:

ip access-l standard PERMIT_6_7
permit 10.0.6.0 0.0.1.255
route-map FILTER_6_7 deny 10
match ip address PERMIT_6_7
route-map FILTER_6_7 permit 20

Now we'll apply the route-map to the redistribution process:

router ospf 1
redistribute rip route-map FILTER_6_7

2010-11-07T16:49:00.002+08:00

CCNP BSCI 15

Most of the CCIE R+S examination focuses on Route Redistribution. Now, performing Route Redistribution already means that you're moving routes across different routing protocols (well, with the exception of static routes). Why would people use multiple routing protocols?

In the real world, most of the time it's due to political reasons. As companies get larger, more and more policies and politics would surface. Some divisions of organizations forbid the use of proprietary protocols. On the other hand, the rest of the division is alright with proprietary protocols. This leads to a split in network politics where different parts of a large organization use different protocols.

Other reasons include upgrading of routing protocols where parts of organizations convert in phases. Also, implementation of different vendors would lead to this, such as EIGRP for Cisco equipment and OSPF for the others.

Redistribution from a bird's eye view is very simple. You simply have to have a router running two protocols at once. That router then mixes the routes between the protocols (can be one or two ways).

However, it can become complicated when we talk about the characteristics of different protocols. What happens when we want to redistribute OSPF into RIP? What happens to the metric? In this case, we would have to translate the "cost" type of metric into a "hop count" type of metric. Typically people create a "seed" metric for all routes from the OSPF domain, which is done manually by estimation and proves to be unreliable.

Another problem we can get from this is routing loops. Refer to the following topology:

If we perform full redistribution at both links, the RIP routes would be sent to the OSPF domain then redistributed back into RIP.

We'll talk about fixing this in a future article. Right now, we'll deal with a very simple redistribution exercise:

R1 has 10.0.0-3.0/24 networks connected to it. R1 uses RIP for the link to R2, and the networks it's connected to. R2 uses RIP as well as OSPF on the link to R1 and R3. R3 and R4 are full OSPF routers.

The point-to-point links between routers use 172.16.0.0/30 networks from left to right.

Here's the configuration on R1:

router rip
no auto
ver 2
network 10.0.0.0

On R2, we have:

router rip
no auto
ver 2
network 172.16.0.0
router ospf 1
network 172.16.0.5 0.0.0.0 area 0

On R3, we have:

router ospf 1
network 172.16.0.6 0.0.0.0 area 0
network 172.16.0.9 0.0.0.0 area 0

Finally, on R4, we have:

router ospf 1
network 172.16.0.10 0.0.0.0 area 0

Now, R1 knows how to go up till the link between R2 and R3. R2 has full connectivity. R3 has only routes within OSPF.

Now, to redistribute OSPF into RIP, go to R2 and type:

router rip
redistribute ospf 1 metric 5

Now R1 would have all routes in both domains. It would appear as RIP routes. The direct RIP route from the link between R2 and R3 would be preferred to the redistributed one because of the metric. Pay attention to this as I would demonstrate how this would cause routing loops in future articles.

Now we'll redistribute RIP into OSPF from R2:

router ospf 1
redistribute rip subnets metric 1000

When redistributing into OSPF, we can also change the Metric Type to E1 by using the "metric-type" keyword. Recall that E1 routes will have the cost incremented through the OSPF domain, while E2 routes will not.

You can also tag routes using the "tag" keyword. This marks the route so that you would be able to check where it came from later on. This tag also allows you to manipulate the route later on using route filtering. This is what we'll use to prevent the routing loop described above.

When redistributing, you can also set a default-metric for all redistributed routes. This is done by typing:
default-metric 1800

This can be used in all protocols. The default-metric is overridden if you manually specify it in the redistribute statement.

2010-11-07T15:53:00.002+08:00

CCNP BSCI 14

All protocols have some conditions before they can put the routes in their databases in their routing tables. Here is how IS-IS does it:
1) L1 and L2 Intermediate Systems perform separate calculations
2) SPF Algorithm is run to determine best paths for NSAP routing
3) Best paths are added to the OSI routing table
4) PRC Algorithm is run to determine best path for IP routing
5) Best paths are added to the IP routing table

The only time when SPF has to run again is when a router is added or changed. PRC is run when IP networks are changed. Since PRC is very lightweight, it ends up more efficient than OSPF.

This is what we'll use to demonstrate basic IS-IS routing:

The Area ID would be in the format 49.00aa where "aa" stands for the Area ID
The System ID would be in the format 0000.0000.000s where "s" stands for the Router ID
Finally, the NSEL is always 00

We'll first configure R1. To do this, we'll go to global configuration and type:
router isis

You can actually enter a tag after the "isis" keyword, which is similar to an EIGRP's AS number. If you do not enter anything, the default "0" is used.

We'll now need to enter the NSAP address for R1. It would be:
net 49.0050.0000.0000.0001.00

By default, routers are L1/L2 routers, so we'll need to set it to L1:
is-type level-1

We'll then need to turn on IS-IS under the interface. In this case, I have Loopbacks to simulate networks:

in lo0
ip router isis
in lo1
ip router isis
in lo2
ip router isis
in lo3
ip router isis
in f0/0
ip router isis

Now we'll need to configure R2:

router isis
net 49.0050.0000.0000.0002.00

Then we'll configure R2's interfaces:

in f0/0
ip router isis
isis circuit-type level-1
in f0/1
ip router isis
isis circuit-type level-2

The circuit-type restricts L1 or L2 Hellos in the interfaces. At this point, we can do some verification:
show clns neighbors

To see the neighbor's IP, we can use:
show clns neighbors detail

To see the interface status, use:
show clns int

CLNS stands for Connectionless Network Service. It is connectionless and unreliable, requiring upper layer protocols for reliability. Sounds familiar? Yes, it's the equivalent of IP.

We'll enable R3 for IS-IS similarly:

router isis
net 49.0020.0000.0000.0003.00
is-type level-2

Here, we also configure the interfaces:

in f0/1
ip router isis
in f0/0
ip router isis

Finally, we'll configure R4:

router isis
net 49.0005.0000.0000.0004.00

And we'll configure its interfaces:

in lo0
ip router isis
in lo1
ip router isis
in lo2
ip router isis
in lo3
ip router isis
in f0/0
ip router isis
isis circuit-type level-2

At this point you should have full connectivity and routing across the domain. Another verification we can use is:
show clns

To do summarization, we'll hop on to R2, then type:

router isis
summary-address 192.168.0.0 255.255.252.0

What this does is that it summarizes that into the Level 2 database. You can also summarize into the L1 database from L2 by typing the "level-1" keyword behind the statement.

On R3, if we do a "show ip route" now, we would see IS-IS routes with a "i" marker. L2 routes will be marked with "L2" and L1 routes will be marked "L1". On R2, the summary route will be marked with "su" towards Null0.

We should also summarize on R4 by typing:

router isis
summary-address 10.0.0.0 255.255.252.0

To check the topology table, use:
show isis top

Finally, to change the metric, you go under the interface and type:
isis metric 1

Remember that the default is 10. They are treated as cost so lower is better.

2010-11-07T14:55:00.003+08:00

CCNP BSCI 13

Now it's time to go through the feared part of IS-IS: That is the NSAP address applied to the routers. OSI uses CLNP addresses, and when it's applied on a router, it's called a NSAP (Network Service Access Point) address.

You only need one address per node (per IS), not per interface. This address tells what area the router is in. It tells the Cisco router what IS-IS area it's in and what's it's System ID (which is equivalent to the Router ID).

The NSAP address can be up to 20-bytes in length, compared to OSPF's 4-bytes.

The original implementation of OSI defined more than 5 sections the NSAP address would represent, compared to the 2 which IP addresses have.

Cisco's implementation only uses three of those fields:
- Area address
- System ID
- NSEL (NSAP Selector)

An example NSAP address is:
49.1234.AA15.B322.1841.00

Every NSAP address assigned to a Cisco router will always have the last 2 bits set to 00. That is the NSEL. The NSEL of 00 shows that the address is assigned to an IS.

The System ID in this case is AA15.B322.1841. The System ID is always a fixed 6 bytes in length. As mentioned previously, the System ID is actually the equivalent of the Router ID.

Some Administrators like to put the MAC addresses as the System ID. Typically in lab environments, the System ID always ends up becoming the router's number.

Whatever is left represents the area. The best way to read the address is from right to left. In this case, the area is 49.1234. Areas starting from 49 represents a private address. These packets would theoretically be dropped by ISPs like how RFC 1918 packets would.

This example address is not the longest you can get. You can have up to 20 characters in an NSAP address.

IS-IS builds a topology of the OSI domain to find out how to reach various destinations based on the NSAP addresses. When routing, IS-IS checks the area address of the packet. If it's a different area, it would be routed based on Area ID. If it's in the same area, it would be routed based on the System ID.

If you are a L1 router, it would send it to the closest L1/L2 router. The L1/L2 router then sends the packet through the backbone to the other area.

For intra-area routing, L1 and L1/L2 routers simply route it based on the L1 database.

The term "packet" is a PDU, which is a Network Layer PDU. In OSI, a Network Layer Packet is simply referred to as a Network PDU. A Frame is known as a Data-Link PDU. Theses are the various packet types used by IS-IS:
-Hello
-Link State Packet (LSP)
-Partial Sequence Number PDU (PSNP)
-Complete Sequence Number PDU (CSNP)

The Hello message is the foundation that forms neighbor relationships and serves as a keepalive.

The LSP is similar to OSPF's LSU. In each IS-IS LSP, there can be information for one or more routes.

CSNP acts like the OSPF's DBD.

PSNPs are typically used to request for information like a LSQ. It is also an acknowledgment for an LSP.

A typical Network PDU has the following structure:
LSP Header|TLV|TLV|TLV|...

The LSP header contains the PDU type, length, sequence number and lifetime. The TLVs contain neighbors, authentication information and attached subnet information. They simply added a new TLV for IP routing to work!

The original IS-IS and the Integrated IS-IS is really not that different at all! Integrated IS-IS still reads NSAP and routes NSAP! It simply has an extra TLV which allows the IS to match NSAP with IP. IS-IS is one of the first routing protocol to be released for IPv6 because they simply need to add a new TLV. On the other hand, OSPFv3 had to be completely re-engineered for IPv6!

The IS-IS network types are simple:
-Broadcast
-Point-to-Point

Broadcast mode assumes full connectivity. The Broadcast Mode elects a Designated IS (DIS) which is the same as DR/BDR. Broadcast Mode uses Multicast.

When dealing with NBMA networks without a full mesh, IS-IS simply uses point-to-point (sub-interfaces) design. Point-to-Point mode uses Unicast.

To keep databases tightly synchronized, CSNPs are sent once every 10 seconds in Broadcast mode, while only once initially (when link comes up) in Point-to-Point networks.

2010-11-07T14:10:00.003+08:00

CCNP BSCI 12

There are only two Link-State routing protocols in the world that are considered mainstream and popular: OSPF and IS-IS. IS-IS was never designed to support TCP/IP, but it is widely employed by service providers to route TCP/IP traffic!

In the past, the OSI model was never meant to be just a model. OSI was actually a full-blown routing suite for the Internet. It was a competing standard to TCP/IP and in the end OSI lost to TCP/IP because it is simpler.

In the OSI protocol, the a router is known as an Intermediate System (IS). IS-IS stands for Intermediate System To Intermediate System! IS-IS was the routing protocol created for the OSI protocol.

The OSI was originally deployed by ISPs due to government regulations because it was a good contender. When the Internet first appeared, ISPs had to support both the TCP/IP protocol AND the OSI protocol.

After OSI protocol died out, some people saw the potential in the IS-IS protocol and so they modified it to carry TCP/IP protocol. IS-IS was not completely written, but rather it was tuned. This tuning led to a new protocol known as Integrated IS-IS!

For IS-IS to work properly, a CLNP (Connectionless Network Protocol) address still needs to be assigned to the router. IS-IS is very similar to OSPF in many ways. Here's a brief rundown of IS-IS:
-Link-State
-Uses SPF
-Uses Hello Messages
-More Tunable than OSPF
-More Efficient that OSPF
-More Flexible than OSPF
-Much more difficult to understand than OSPF!

Once you've understood the basics of OSPF, you pretty much understand IS-IS. The only reason why IS-IS is more difficult in some ways is because of the CLNS address still required to be assigned to the router.

In IS-IS, there are no ABRs. All routers belong fully in one area. There are two types of routers, L1, L2 and L1/L2 routers.

L1 routers are designed to maintain the topology tables of an entire area. This is similar to an Internal router.

The L2 routers are considered the backbone routers. The L2 routers are those that know about the backbone routers.

L1/L2 routers are those that interface between L1 and L2 routers.

Analogically, L1 are Internal routers, L2 are Internal Backbone routers, and L1/L2 are ABRs.

The L1 (Level One) databases are kept completely separate from L2 databases. L1/L2 routers have to keep two databases, but it can summarize the L1 database before putting it in the L2 database.

When a L1 router needs to go to another area, it sends a message to the closest L1/L2 router. The L1/L2 router sort of serves as a default gateway for an area.

The Metric of IS-IS is not based on bandwidth. It is a value between 0 to 63 with 10 being the default. By default, IS-IS metric behaves like RIP. IS-IS metric is typically written in an organizationally-unique policy and implemented by Network Administrators.

In OSI, the End Systems (ES) would participate in routing by finding their closest IS. This is known as ES-IS. In the OSI world, you wouldn't have a default-gateway. The ES would be smart enough to discover default-gateways. (This is a "new" feature implemented in IPv6 as well).

L1 and L2 routers form like relationships and separate databases. L1 and L2 have separate Hello messages, so L1/L2 would have to send two types of different Hello messages. Two L1/L2 routers can form 2 relationships between them.

A typical IS-IS network design looks like this:

In the backbone area, L2 routers only know the summary of the different areas. These summaries are sent in by L1/L2 routers. Notice that in the end the concept is still roughly the same as OSPF in terms of design.

Here are the different Level of Routing in IS-IS:
-Level 0 routing refers to ES-IS routing.
-Level 1 routing refers to IS-IS routing.
-Level 2 routing refers to IS-IS inter-area routing.
-Level 3 routing refers to routing to other autonomous systems.

Here's some OSPF vs IS-IS breakdown:
-Both are Link-State protocols
-Areas
-Topology, Neighbor and Routing Tables
-SPF Algorithm

OSPF: Interfaces belong to areas
IS-IS: Router belong to an area

OSPF: All areas tie to the backbone area (Area 0)
IS-IS: The backbone runs to all areas

OSPF supports more area types, supports a metric scaled by default, is supported by more vendors and is well understood by the majority of the industry.

IS-IS handles updates more efficiently, rarely runs the SPF algorithm, prefers using partial route calculation (PRC), is much faster (by default) to detect failures and converge, has less design constraints and is very easy to adapt to IPv6.

2010-11-07T13:01:00.002+08:00

CCNP BSCI 11

Authentication in EIGRP uses a key-chain during authentication to do auto-key-changing and so on. OSPF is much simpler, in which authentication is enabled on a per-interface basis.

OSPF supports two types of password authentication: Clear-text, or MD5. Every OSPF packet is keyed with the password. This includes Hellos, and so on. Neighbor relationships will be immediately severed if a packet has the wrong password.

The primary way to debug authentication in OSPF is:
debug ip ospf adj

To enable authentication, go under the interface pointing towards the neighbor, and type in:

ip ospf authentication message-digest
ip ospf message-digest-key 1 cisco md5

Beware. Using "ip ospf authentication-key" is actually for clear-text. No matter what you set for authentication-key, as long as both sides have no message-digest keys, authentication will go through if you have message-digest mode set.

When debugging, you would encounter a type 0, type 1 or a type 2 authentication method. Type 0 simply means no authentication, while type 1 is for clear-text and type 2 is for message-digest is set.

Recall that previously ASBR routes show up as E1 and E2 routes. E2 is the default type, in which the cost doesn't increment throughout the OSPF domain. If there is only 1 exit to that route, this makes sense.

The only time when E1 routes are useful is when there are multiple exits to that route. This helps the routers calculate which exit it would want to go out through.

To change a route to E1 when redistributing, you use the metric-type keyword. For example:
redistribute rip subnets metric 1 metric-type 1

The cost is actually calculated based on a reference speed. The default reference speed is FastEthernet which is 100Mbps. The formula to calculate the cost of a link is:
Reference/Link Speed

So anything faster than FastEthernet would give you a cost of 1. To change the refernce speed, you can use this under the OSPF context:
auto-cost reference-bandwidth 100000

The above is entered in Mbps. You need to make sure that all the routers have the same reference cost.

Now, if you wish to generate a warning after a number of LSAs a router receives per minute, you can use:
max-lsa 100 warning-only

OSPF can send a default route to the whole domain with the default-information command. There are two different ways you can use this. If you already have a default route, you can simply type this under the OSPF context:
default-information originate

Now, if you do not have a default-route, but still want to advertise a default-route to itself throughout the OSPF domain, you can use:
default-information originate always

The route will be propagated as an E2 route by default.

2010-11-06T19:51:00.003+08:00

CCNP BSCI 10

Virtual Links do not belong in a normal network, but serves as a band-aid to temporarily fix network problems introduced when companies acquire other companies. Virtual Links allows areas to be connected to an area other than Area 0. A typical Virtual Link scenario looks like this:

In this topology, R1 has the Router ID set to 1.0.0.1, R2 is 1.0.0.2 and R3 is 1.0.0.3. The Router ID is very important in Virtual Link because you'll have to define it in the command. In this topology, we'll have to establish a Virtual Link through Area 1.

We'll first go to the router that connects to the backbone in the area. That would be R2. On R2, we'll use the following command:
area 1 virtual-link 1.0.0.3

The command would be the same regardless of how many routers are between R2 and R3. Now, we'll do the same command on R3:
area 1 virtual-link 1.0.0.2

You simply have to remember that the area always specifies the area that you're going through.

A Virtual Link is a tunnel to trick the process to believe that it is really connected to the backbone area. You can check the virtual link using:
show ip ospf virtual

There are many ways this can fail, and most commonly it's a mistyped Router ID, a changed Router ID, or wrong Area ID.

If the situation presents itself, you can actually do Virtual Links within Virtual Links!

Now I'm going to go into different area types. This is the third time I'm using this image! But oh well, here goes!

Notice that in the image, I have Area 1 written as a possible Stub and Area 2 written as a possible Not-So-Stubby-Area.

Now, notice that no matter what external routes Area 1 receives, it only has one exit out of the network. It doesn't need to know about all the other routes and ways out of the network because it makes no difference!

In a Stubby area, all Type 5 LSAs are blocked. Recall that Type 5 LSAs are external routes sent in from ASBRs. So if an Area is Stubby, it has all the routes in the OSPF domain, and a default route to the ABR.

Now, to step it up further, you can configure an area as a Totally Stubby area. In a Totally Stubby Area, Type 3, 4 and 5 LSAs are blocked. And if we recall, Type 3 is an ABR summary and Type 4 and 5 refers to the ASBR's IP and ASBR External Routes respectively. A default route to the ABR is also flooded.

To configure an area as a Stub, you simply go on the ABR and all Internal routers and type:
area 1 stub

The ABR sees no change in the routing table, but if we hop on to an Internal router, we would see a new default Inter-Area route pointing to the ABR.

Totally Stubby Areas are Cisco proprietary. The only equipment that needs to be Cisco is the ABR. The Internal routers can still use the "area 1 stub" command. The Totally Stubby Area command to be used on the ABR is:
area 1 stub no-summary

The "No-Summary" keyword refers to Summary LSAs. Remember that Type 3 and 4 are both called Summary LSAs. These are now blocked as well. Now, the routers in Area 1 should only know about local prefixes, and a default route towards the ABR.

Now, what if a router in a Totally Stubby area becomes an ASBR? You end up with a Not-So-Stubby-Area, and that's a real technical term! NSSAs passes external routes using a Type 7 LSA, which gets read as a Type 5 once they reach the ABR. You can have a Not-So-Stubby-Area, and a Not-So-Totally-Stubby-Area.

To change Area 2 into an NSSA, type this on the ABR:
area 1 nssa

Likewise, the "no-summary" keyword can be put behind to denote a Totally Stubby area. The ASBR in the NSSA would receive a default route to the ABR in addition to all the RIP routes it knows and redistributes.

When any internal router in the Not-So-Stubby-Area wants to access the external routes from its area's own ASBR, it will first go to the ABR, then back through itself to the ASBR then out.

Like Virtual Links, NSSAs are band-aids to fix design goof-ups. It is not standard practice to design networks with NSSAs in mind.

2010-11-06T17:21:00.002+08:00

CCNP BSCI 09

Recall that OSPF has areas for efficiency. Every router in the area needs to know about all the routes and changes in the area. If you want to keep the topology database small, you'd have to implement areas to localize routes and updates.

Also recall that there are multiple router types which you can see from this diagram:

(Yes I'm not using Cisco logos because I used an old image I made previously)

From this point I'd need you to be familiar with the areas and router types because we'll be talking about LSA types.

WHAT!?

Yes, recall that after exchange of DBD, LSQs are used to request for LSUs which contain multiple LSAs. But there are many different types of LSAs!

Before we describe anything, we'll go through summarization in OSPF. We'll make use of this topology:

Now back on R1, I have links to the networks:
192.168.1.0/24
192.168.2.0/24
192.168.3.0/24
192.168.4.0/24
192.168.5.0/24
192.168.6.0/24
192.168.7.0/24

We can only summarize on ABRs or ASBRs, so we'll need to do this on R2. To summarize Area 1, we hop on over to R2 and type:
area 1 range 192.168.0.0 255.255.248.0

255.255.248.0 is the summary mask that summarizes 192.168.[1-7].0/24 to a 192.168.0.0/21. Once this is done, R2 will begin suppressing routes matching 192.168.0.0/21. Routers in Area 0 and other areas would only see 192.168.0.0/21 pointing towards R2. The "area 1 range" command can also be used to hide routes by adding the "not-advertise" keyword behind. The summarized range is suppressed and not advertised.

Now, assume that R4 has the routes:
10.0.0.0/16
10.1.0.0/16
10.2.0.0/16
10.3.0.0/16
10.4.0.0/16
10.5.0.0/16
10.6.0.0/16
10.7.0.0/16

R3 receives these routes as RIP routes. Now, remember that we can do summarization on ASBRs, so we should be able to summarize on R3, right? However, one thing comes in mind: Since the summarization command is "area x range", what area exactly do we use to specify an external AS?

We don't! Instead, we use the summary-address command! To summarize on R3, we use:

redistribute rip subnets
summary-address 10.0.0.0 255.248.0.0

What this does is that it advertises all RIP routes into OSPF as E2 routes, then suppress and apply the summary-address of 10.0.0.0/13 to every address matching it.

Now, we can talk about LSAs. LSA are the building blocks of OSPF, and below is a list of the 5 most common LSAs (there are 11 in total):
LSA Type 1: Router LSA
LSA Type 2: Network LSA
LSA Type 3: Summary LSA
LSA Type 4: Summary LSA
LSA Type 5: External LSA

The Type 1 LSA (Router) is generated by routers to talk about 1 specific network within the same area.

The Network LSA is generated by a DR to tell everyone about the other routers connected to the same network segment.

Type 3 LSAs are generated by ABRs to talk about routes and summaries from other areas.

Even though Type 4 LSAs are called Summary LSAs, they are just generated by ASBRs to point to the IP Address of the ASBR in the OSPF domain.

The real routes and summaries from external locations are advertised by ASBRs as Type 5 LSAs.

2010-11-06T15:22:00.005+08:00

CCNP BSCI 08

It has always been a nightmare to think about OSPF implementation over the different Non-Broadcast Multi-Access (NBMA) networks.

In this world, there are three types of networks:
-Broadcast, Multi-Access Networks
Ethernet, Token Ring
Single Operation Mode
DR/BDR Election, 10 second Hellos, Dual Multicast Address

-Point-to-Point Networks
T1 CAS, ISDN BRI/PRI
Single Operation Mode
No DR/DR, 10 second Hellos, Single Multicast Address

-Non-Broadcast Multi-Access Networks
X.25, Frame Relay, ATM
Five Modes of Operation (Two are Industry Standard)

OSPF has 5 modes of operation over NBMA networks. It depends on what Frame Relay Topology you're going to use. Let's review the topologies:

The most costly but the one with the highest performance and redundancy is the Full Mesh network:

If you only keep the links between important sites meshed, you'd have a Partial Mesh network:

Finally, if you employ a star topology, you'd have a Hub and Spoke network and this is the most common because it's the cheapest to maintain but may have delay problems when it comes to VoIP:

Because there are so many ways you can connect your routers together, you have the flexibility (or complexity) of 5 Frame Relay modes:
-NBMA - RFC Standard
-Point-to-Multipoint - RFC Standard
-Point-to-Point - Cisco Proprietary
-Broadcast - Cisco Proprietary
-Point-to-Multipoint, Non-Broadcast - Cisco Proprietary

You cannot mix modes because they all use different timers.

NBMA mode is the default for X.25, Frame Relay and ATM. NBMA mode is also known as Non-Broadcast Mode. It means that no broadcast and no multicast messages are allowed over the cloud. The neighbors are statically configured and you have to use one subnet over the whole cloud. In Non-Broadcast mode, it is treated as a LAN environment (it assumes Full Mesh which you would need to fix with maps) and DR/BDR is elected and must be the hub.

In NBMA mode, it assumes that all broadcast and multicasts are denied, so you have to manually type in the neighbors. It will use unicast to reach the other routers. The place you define other routers is at the Hub of the network. For this to work properly, any router other than the Hub must have their priority set to 0:
ip ospf priority 0

To add neighbors in OSPF, simply type:
neighbor 10.0.0.2 priority 0

Now we'll implement basic OSPF over NBMA in the following topology:

First of all we're going to set up basic connectivity. To do this, we'll first go on R1 and set:

in s0/0
encap frame
ip add 10.0.0.1 255.255.255.0
frame map ip 10.0.0.2 102 broadcast
frame map ip 10.0.0.3 103 broadcast
no shut

Next, on R2, we'll set:

in s0/0
encap frame
ip add 10.0.0.2 255.255.255.0
frame map ip 10.0.0.1 201 broadcast
frame map ip 10.0.0.3 201 broadcast
ip ospf pri 0
no shut

Finally, R3 will have:

in s0/0
encap frame
ip add 10.0.0.3 255.255.255.0
frame map ip 10.0.0.1 301 broadcast
frame map ip 10.0.0.2 301 broadcast
ip ospf pri 0
no shut

(Much thanks to Candie for spotting the mapping mistake =p That was a bad copy and paste there!)

Notice that for R2 and R3, we have two entries pointing to the same DLCI. This is because NBMA mode assumes full mesh, so you'll need to have connectivity to each other and it's only through R1 that R2 can reach R3.

The broadcast keyword is present to make sure that all broadcast messages destined to that interface will be transmitted to the IP Address and DLCI as a unicast packet.

Now we'll begin setting up the network statements. Only R1 needs to put the neighbor statements:

network 10.0.0.1 0.0.0.0 area 0
neighbor 10.0.0.2 priority 0
neighbor 10.0.0.3 priority 0

For R2, it would be:
network 10.0.0.2 0.0.0.0 area 0

Finally, for R3, we'll have:
network 10.0.0.3 0.0.0.0 area 0

It will take an extremely long time for the neighbors to come up, so be patient! When you type the verification command "show ip ospf nei", it will be stuck at ATTEMPT for a minute or two.

The Point-to-Multipoint mode fixes issues with NBMA networks. In Point-to-Multipoint mode, there is no DR/BDR elected even though it still requires a single subnet. Neighbors automatically form without the need for static configuration. Broadcast and Multicast messages must be allowed across the Frame Relay cloud.

In Point-to-Multipoint mode, you don't have to specify overlapping DLCIs to go to each other. Instead, this would be the configuration of R2:

in s0/0
encap frame
ip add 10.0.0.2 255.255.255.0
frame map ip 10.0.0.1 201 broadcast
ip ospf network point-to-multipoint
no shut

For R3:

in s0/0
encap frame
ip add 10.0.0.3 255.255.255.0
frame map ip 10.0.0.1 301 broadcast
ip ospf network point-to-multipoint
no shut

The timers are still the same as NBMA so you can mix these.

Next, on R1, you would have:

in s0/0
encap frame
ip add 10.0.0.2 255.255.255.0
frame map ip 10.0.0.2 102 broadcast
frame map ip 10.0.0.3 103 broadcast
ip ospf network point-to-multipoint
no shut

You no longer need to specify neighbors, so R1 just needs one statement in the OSPF context:
network 10.0.0.1 0.0.0.0 area 0

Now, on R3, you would have these routes:

10.0.0.0/8 is variably subnetted, 5 subnets, 2 masks
O       10.0.0.2/32 [110/128] via 10.0.0.1, 00:02:28, Serial0/0
C       10.0.3.0/24 is directly connected, Loopback0
O       10.0.2.1/32 [110/129] via 10.0.0.1, 00:02:28, Serial0/0
C       10.0.0.0/24 is directly connected, Serial0/0
O       10.0.0.1/32 [110/64] via 10.0.0.1, 00:02:28, Serial0/0

Notice that the routers are automatically discovered and advertised through the OSPF area. The next hop to get to R2 from R3 is now correctly recorded as R1! In a non-sub-interface environment, unless the ISP disallows broadcasts and multicasts, there is no reason why you should use NBMA over Point-to-Multipoint!

To configure Point-to-Multipoint Non-Broadcast mode, you simply have to use "ip ospf network point-to-multipoint non-broadcast". Neighbors will have to be statically specified.

Broadcast mode requires one subnet and full mesh connectivity. It treats the entire topology like a LAN. You would have a DR/BDR election and Multicast messages are used. It is exactly like the LAN environment. You set this with "ip ospf network broadcast".

The final and easiest (logically) mode to configure is the point-to-point mode. It makes the entire NBMA network act like a series of point-to-point links. Each DLCI gets its own sub-interface and requires one subnet each.

To configure this, we'll start on R1:

in s0/0
encap frame
no shut
in s0/0.102 point-to-p
frame interface-dlci 102
ip add 10.1.2.1 255.255.255.252
in s0/0.103 point-to-p
ip add 10.1.3.1 255.255.255.252
frame interface-dlci 103
router ospf 1
network 10.1.2.1 0.0.0.0 area 0
network 10.1.3.1 0.0.0.0 area 0

On R2, we have:

in s0/0
encap frame
no shut
in s0/0.201 point-to-p
frame interface-dlci 201
ip add 10.1.2.2 255.255.255.252
router ospf 1
network 10.1.2.2 0.0.0.0 area 0

Finally, R3 will have:

in s0/0
encap frame
no shut
in s0/0.301 point-to-p
frame interface-dlci 301
ip add 10.1.3.2 255.255.255.252
router ospf 1
network 10.1.3.2 0.0.0.0 area 0

This concludes the 5 modes of OSPF NBMA networks. You survived, really.

2010-11-06T14:00:00.004+08:00

CCNP BSCI 07

Now I'll walk through basic OSPF configuration. To do this, we'll use the following topology (notice I have new Cisco icons. The only other article I used these was at VPN Introduction!):

Now we'll assume that all IP addresses on interfaces are set and the interfaces are all up. We'll now begin configuration on R1.

First, we'll go into the OSPF process using:
router ospf 1

Next, we'll enable OSPF on its LAN interface:
network 172.16.1.0 0.0.0.255 area 0

This is similar to flicking an ON switch on any interface starting with 172.16.1.x.

Since R1's interface is 172.16.1.1, we can actually be more specific by using:
network 172.16.1.1 0.0.0.0 area 0

If you recall, typing "area 0" actually makes R1 a Backbone router. We'll now set up the Serial Link to be in Area 0 as well:
network 10.0.0.1 0.0.0.0 area 0

In newer routers, we can use the interface command to add the interface to the OSPF process like this:

in s0/0
ip ospf 1 area 0

This is the only way we can use to add IPv6 interface to OSPF.

To check the router's Router ID, use:
show ip ospf

Alternately, you can use:
show ip prot

Notice that R1 is the DR for the 172.16.1.0/24 network, and is the DR for the Serial interface as well.

Now, hop over to R2 and before we'll start configuration we can turn on the debugging for OSPF to see how the neighbors are formed:

debug ip ospf adj
debug ip ospf events

Now lets enable the process on the 172.16.0.0/24 network:

router ospf 1
network 172.16.0.2 0.0.0.0 area 0

You'll immediately start seeing a Hello packet being sent, and you'll continue seeing it every 10 seconds.

Now, for the good part, we'll enable OSPF on the Serial link as well. This will start the neighbor forming between R1 and R2 over the Serial Link:
network 10.0.0.2 0.0.0.0 area 0

Below is a typical output:

*Mar  1 00:12:22.083: OSPF: Interface Serial0/0 going Up
*Mar  1 00:12:22.087: OSPF: Send hello to 224.0.0.5 area 0 on Serial0/0 from 10.0.0.2
*Mar  1 00:12:22.299: OSPF: Rcv hello from 172.16.1.1 area 0 from Serial0/0 10.0.0.1
*Mar  1 00:12:22.303: OSPF: Send immediate hello to nbr 172.16.1.1, src address 10.0.0.1, on Serial0/0
*Mar  1 00:12:22.307: OSPF: Send hello to 224.0.0.5 area 0 on Serial0/0 from 10.0.0.2
*Mar  1 00:12:22.311: OSPF: End of hello processing
*Mar  1 00:12:22.335: OSPF: Rcv DBD from 172.16.1.1 on Serial0/0 seq 0x14E9 opt 0x52 flag 0x7 len 32  mtu 1500 state INIT
*Mar  1 00:12:22.335: OSPF: 2 Way Communication to 172.16.1.1 on Serial0/0, state 2WAY
*Mar  1 00:12:22.339: OSPF: Send DBD to 172.16.1.1 on Serial0/0 seq 0xA33 opt 0x52 flag 0x7 len 32
*Mar  1 00:12:22.343: OSPF: NBR Negotiation Done. We are the SLAVE
*Mar  1 00:12:22.347: OSPF: Send DBD to 172.16.1.1 on Serial0/0 seq 0x14E9 opt 0x52 flag 0x2 len 72
*Mar  1 00:12:22.363: OSPF: Rcv hello from 172.16.1.1 area 0 from Serial0/0 10.0.0.1
*Mar  1 00:12:22.367: OSPF: End of hello processing
*Mar  1 00:12:22.387: OSPF: Rcv DBD from 172.16.1.1 on Serial0/0 seq 0x14EA opt 0x52 flag 0x3 len 72  mtu 1500 state EXCHANGE
*Mar  1 00:12:22.395: OSPF: Send DBD to 172.16.1.1 on Serial0/0 seq 0x14EA opt 0x52 flag 0x0 len 32
*Mar  1 00:12:22.423: OSPF: Rcv DBD from 172.16.1.1 on Serial0/0 seq 0x14EB opt 0x52 flag 0x1 len 32  mtu 1500 state EXCHANGE
*Mar  1 00:12:22.423: OSPF: Exchange Done with 172.16.1.1 on Serial0/0
*Mar  1 00:12:22.423: OSPF: Send LS REQ to 172.16.1.1 length 12 LSA count 1
*Mar  1 00:12:22.427: OSPF: Send DBD to 172.16.1.1 on Serial0/0 seq 0x14EB opt 0x52 flag 0x0 len 32
*Mar  1 00:12:22.427: OSPF: Rcv LS REQ from 172.16.1.1 on Serial0/0 length 36 LSA count 1
*Mar  1 00:12:22.427: OSPF: Send UPD to 10.0.0.1 on Serial0/0 length 40 LSA count 1
*Mar  1 00:12:22.431: OSPF: Rcv LS UPD from 172.16.1.1 on Serial0/0 length 64 LSA count 1
*Mar  1 00:12:22.431: OSPF: Synchronized with 172.16.1.1 on Serial0/0, state FULL
*Mar  1 00:12:22.435: %OSPF-5-ADJCHG: Process 1, Nbr 172.16.1.1 on Serial0/0 from LOADING to FULL, Loading Done
*Mar  1 00:12:22.595: OSPF: Build router LSA for area 0, router ID 172.16.0.2, seq 0x80000006, process 1
*Mar  1 00:12:22.775: OSPF: Rcv LS UPD from 172.16.1.1 on Serial0/0 length 88 LSA count 1

Notice that the IP addresses shown are actually the Router ID. Now, to look inside the Neighbor Table, type:
show ip ospf nei

Notice that on the Serial Link, nobody's the DR or BDR, and it's denoted by a hyphen:

Neighbor ID     Pri   State           Dead Time   Address         Interface
172.16.1.1        0   FULL/  -        00:00:35    10.0.0.1        Serial0/0

Now, we'll begin setting up R3 and R4. Once we have all R3 and R4 running in the same fashion, without changing the priority or the Router ID, who do you think would be the DR and BDR for the 172.16.0.0/24 network?

If you guessed R4 and then R3, you are correct! Since Priority is the same, the highest Router ID would win. Since we have no Loopback interfaces, the Router ID would be the Fast Ethernet interface:

Neighbor ID     Pri   State           Dead Time   Address         Interface
172.16.1.1        0   FULL/  -        00:00:35    10.0.0.1        Serial0/0
172.16.0.4        0   FULL/  DR       00:00:35    172.16.0.4      FastEthernet0/0
172.16.0.3        0   FULL/  BDR      00:00:35    172.16.0.3      FastEthernet0/0

If you still have the debugging turned on, this is what you'll see in the flurry of messages:

*Mar  1 00:19:28.259: OSPF: DR/BDR election on FastEthernet0/0
*Mar  1 00:19:28.263: OSPF: Elect BDR 172.16.0.3
*Mar  1 00:19:28.263: OSPF: Elect DR 172.16.0.4
*Mar  1 00:19:28.267: OSPF: Elect BDR 0.0.0.3
*Mar  1 00:19:28.267: OSPF: Elect DR 172.16.0.4
*Mar  1 00:19:28.267:        DR: 172.16.0.4 (Id)   BDR: 172.16.0.3 (Id)

On the other routers, you would see R2 labeled as a DROTHER.

Now we'll go through two ways to change the Router ID. Back on R1, create a Loopback interface as shown:

in lo0
ip add 1.0.0.2 255.255.255.255

This is the official definition for the Router ID:
"The OSPF router ID is a 32-bit IP address selected at the start of the OSPF process. The highest IP address configured on the router is the router ID. If a loopback address is configured, it is the router ID. In the case of multiple loopback addresses, the highest loopback address is the router ID. Once the router ID is elected, it does not change until OSPF restarts or is manually changed with the [router-id] command under [the OSPF context]."

At this point, the Router ID would still not change if you check it with:
show ip ospf

To make the changes apply, you'll need to use:
clear ip ospf proc

If it doesn't change, you may have to reset the whole system:

wr
reload

Another way to change the Router ID is simply using the command:
router-id 1.0.0.2

The recommended way is the router-id command because it is important for advanced features like Virtual Link and you wouldn't want it to change by chance. As usual, you would have to clear the OSPF process.

Another way to influence DR/BDR election is to use the "priority" command under the interface:

in f0/0
ip ospf priority 2

A router with the priority of 0 will exempt it from election. You would have to clear the process of the existing DR and BDR after changing the priority of any router because it does not do preemption.

Now that we're done with the basic concepts, we'll go through some basic verification commands:

To check the timers being used, we can use:
show ip ospf int

To check the topology table, we can use:
show ip ospf database

In the topology table, we can check the age (in seconds) and the sequence number (a 4-byte-value) which increases every update. Once the sequence number reaches 0x8fffffff, it will notify neighbors with a special process and it starts from 0 again.

To check the neighbor table, we can use:
show ip ospf nei

2010-11-06T12:54:00.004+08:00

CCNP BSCI 06

The metric used in OSPF is the Cost. The Cost is calculated by 100/Bandwidth-In-MBPS or 100000/Bandwidth. A list of common costs is:
56k - 1785
64k - 1562
T1 - 65
E1 - 48
Ethernet - 10
Fast Ethernet - 1

Fast Ethernet and above are all considered the cost of 1, that's why networks with Gigabit and 10Gigabit Ethernet would need to have their Cost formula changed.

Paths are always calculated with the router being the center of the world. Routes are calculated by adding costs together. The route with the lowest cost is added to the Routing Table.

In this case, the best route would be 1+65+10=76 and would be added into the Routing Table.

The DR stands for the Designated Router, and the BDR is the Backup Designated Router. DR and BDRs play the role of controlling updates within a shared network segment.

Whenever a Link change is detected, the router that detects it will send the Update out of all links with neighbors. Whoever receives it will send it out to all neighbors except the one he received it from. In a shared segment, this can result in something similar to a broadcast storm!

To resolve this, the DR and BDR concept is added. This effectively turns things into a hub-and-spoke fashion. Whenever a change is detected, it is first sent to the 224.0.0.6 address which DR and BDRs listen to, then the DR then forwards these changes out to 224.0.0.5 where DROTHERS (non-DR and non-BDR routers) listen to.

Every shared segment (Ethernet and certain Frame Relay designs) has a DR. However, on Point-to-Point links, the only address used for communication is 224.0.0.5.

The DR/BDR election is influenced by the Hello field known as the Priority (the same field used for Master/Slave election in the previous article). Ties are broken with the higher Router ID.

Elections are only important in certain Frame Relay topologies. Typically any router regardless of processing power would do well as a DR or BDR. In a shared Ethernet segment, routers will only form full relationships with the DR and BDR. Relationships with other routers will be stuck in 2-WAY state.

There are many OSPF packet types in use in OSPF. Below is a general list:
1) Hello
2) DBD (Database Description)
3) LSR (LS Request)
4) LSA (LS Advertisement)
5) LSU (LS Update)
6) LSACK (LS Acknowledgment)

Hello is used as a neighbor-forming mechanism and keepalive.

After the DBD is exchanged, LSRs are used to request for routes which are sent through LSUs. In each LSU, there are multiple LSAs. Each LSA describe individual routes. Think of LSUs as envelopes and LSAs as documents inside.

Every packet sent (except for Hello and LSACK) is acknowledged with an LSACK.

2010-11-06T11:55:00.005+08:00

CCNP BSCI 05

There are only two Link-State routing protocols in this world: IS-IS and OSPF.

Link-State routing protocols maintain three tables:
-Neighbor Table
-Topology Table
-Routing Table

Like EIGRP, Link-State routing protocols maintain a Neighbor Table. They are similar in operation in that they keep track of their neighbors. But the biggest difference comes when we look at the Topology Table.

The Topology Table in a Link-State protocol has information about every single route in the area that the running router belongs to. The EIGRP Topology Table is just a list of routes that the neighbors passed on.

The best routes then appear in the Routing table.

Link-State routing protocol uses the SPF (Shortest Path First) protocols. The SPF protocol is also known as Dijkstra's Protocol. Compared to the DUAL algorithm which processes only information their neighbor tells them about, the SPF algorithm has to calculate through the entire area which uses a lot of resources. This is why in design we should keep areas small.

Triggered updates are also used. However, once every 30 minutes, a router will do a mass exchange known as a "Link State Refresh" to make sure that nothing gets missed by their neighbors.

OSPF Divides the area into multiple areas. Every single area contains a group of routers. All areas must connect to area 0. All routers in the same area have the same topology table. Areas localizes updates within an area which makes calculation more efficient. Areas forces network designers to create a hierarchical IP design.

Below is a diagram to depict the terminologies used to describe OSPF routers:

ABR stands for Area Border Router. A router that has multiple interfaces in different areas is an ABR. The ABR localizes a change in an area. It can do route summarization.

ASBR stands for Autonomous System Boundary Router. It refers to a router that has one or more interfaces in an OSPF domain, and one or more interfaces in another autonomous system such as the Internet or another routing protocol. It can also do route summarization.

An Internal Router is simply a router that only has interfaces in the same area

Finally, a Backbone Router is a router with one or more interfaces connected to Area 0.

Notice that I specified Stubby and Not So Stubby Areas in the diagram, but I'll not go into much detail now. It will be explained later.

Now let's take a look at how neighbors form. Each router has a Router ID. The Router ID is simply a name that a router is known by in the OSPF process. It can be anything and it does not affect the routing, although you would need to know your Router ID when doing Virtual Links which I'll describe later.

These are the major steps taken by routers to create neighbor relationships:
1) Determine neighbor's Router ID

The Router ID is simply the highest active interface IP address when OSPF starts. If you have a Loopback, it will take the Loopback's address. If you have multiple Loopbacks, it will take the highest loopback IP address (2.3.4.5 beats 1.2.3.4, regardless of lo0 or lo1).

It is dangerous to have an auto Router ID. Changes would not take effect immediately. It would only change when the router is rebooted or the OSPF process is cleared through "clear ip ospf proc". It is recommended that the Router ID be hard-coded using the Router-ID command in the OSPF context.

2) Add interfaces to the Link-State database
3) Send a Hello message on chosen interface(s)

At this point, the neighbor would be in **DOWN STATE**.

Hello messages are sent once every 10 seconds on broadcast/point-to-point networks. It is sent once every 30 seconds on NBMA networks. The Dead Timer is always 4 times the Hello interval.

Hello messages contain a lot of information including Router ID, Hello and Dead Timers*, Network Mask*, Area ID*, Neighbors, Router Priority, DR/BDR IP Address, Authentication Password*.

Anything marked with an asterisk (*) needs to be the same between neighbors for them to form.

Neighbors help tell if a relationship is old or new. If a router sees itself in the neighbors list, then it knows that that is an old relationship and no mass exchange is required.

4) Receive Hello

At this point, the neighbor would be in **INIT STATE**.

Check Hello/Dead Interval
Check Netmasks
Check Area ID
Check Authentication Passwords

If any of these fail, you will go back to **DOWN STATE**.

5) Send Reply Hello

At this point, they are in the **2-WAY STATE**.

This is the point, the routers will consider themselves neighbors. For every packet they receive, they will ask:

"Am I listed as a neighbor in your Hello packet?"
1) Yes - Reset dead timer
2) No - Add new neighbor, go to step 6

6) Master-Slave Relationship is Determined

The routers both go into **EXSTART STATE**.

This is when the routers begin exchanging. EXSTART simply stands for Exchange Start. The Master sends the DBD before the Slave. The relationship is determined by the Priority, and Router ID breaks the tie (the higher Router ID wins).

The summarized information sent is in the form of DBD (Database Description Packet). It is simply a cliff note of the Link-State database. The receiving router then replies with a list of whatever they need in the next step.

7) DBDs are acknowledged and reviewed

At this point, routers are in the **LOADING STATE**.

Slave requests Details (LSR - Link State Requests)
Master sends Updates (LSU - Link State Updates)
Master requests Details (LSR)
Slave sends Updates (LSU)

8) Neighbors are Synchronized

Routers are finally in **FULL STATE**.

2010-11-05T17:27:00.002+08:00

CCNP BSCI 04

EIGRP is simple to set up, but that can also be a bad thing. It's not uncommon for people to have EIGRP running without good design, which can end up destroying the network.

We can eavesdrop on EIGRP neighbors using the debug command:

debug eigrp packets query
debug eigrp packets reply

To see how the query messages work, we can make an interface go down. To do this, we can shut down the lo0 interface:

in lo0
shut

Immediately after the Line Protocol goes down, query messages are sent to all neighbors to look for alternate paths to the lo0 network. However, since no one else has it, you will quickly see negative replies from other routers.

Query messages will go to every neighbor on every interface. Whoever receives a Query will send it to other neighbors if it doesn't have the route. This results in something that looks like a broadcast storm if there are looped interfaces.

All replies must be received before the router can make a decision, even if one of the replies has a backup route. If the network is very big, it would be a long time before the queries would come back. This results in a symptom known as SIA (Stuck-in-Active). After 3 minutes, all neighbor relationships are reset, causing a downtime before operation is possible.

There are two ways to solve SIA:
1) Summary Routes
2) Stub Configuration

If you have a set of routes from 172.16.[0-7].0/24 and you've configured a summary of 172.16.0.0/21 and one of the 172.16.x.0/24 networks go down, the query would still go out, but routers would assume that the original path is the only way to the network and would give a negative reply instead of forwarding the query along.

You can also configure a network as a stub. A stub is simply a network with 1 exit only, so if a network is configured as a stub, it will assume that the link it has is the only one exit and would not query anything else.

To configure a stub, we'll use:

router eigrp 1
eigrp stub

If a router is configured as stub, no queries will be sent to it if a route goes down. A stub router simply means that the router will only have the routes it tells you about and nothing else.

To configure the router to not even advertise anything, similar to a passive-interface on RIP, use:
eigrp stub receive-only

By default, K1 and K3 is set to 1 for Bandwidth and Delay. If routers have different K Values set, neighbors will not come up properly. In 12.3(2)T, EIGRP has a new feature known as Graceful Shutdown. Whenever the neighbor wants to go down, it would send a Graceful Shutdown message to let the other routers remove it from the tables immediately. Graceful Shutdown (Goodbye Message) is simply a Hello message with all K Values set to 255. Older routers would log it as "K Value Mismatch" while the newer routers would see "Goodbye Message".

2010-11-05T16:43:00.003+08:00

CCNP BSCI 03

There are two main ways EIGRP can summarize networks. One is automated, while one is manual. In this article, I'm going to use the same topology as the one used in the previous article:

Now, if we make use of the auto-summarization feature on R1, it would tell the other routers that it has the route to 172.16.0.0/16. If there are any other 172.16.0.0 routes anywhere else, it would cause some problems. In some cases, it would also cause EIGRP to improperly load balance across wrong links. Auto-summarization happens on classful boundaries.

To turn off auto-summarization, type:
no auto

To manually summarize, we'll go under the interface, and use the "ip summary-address" command:

in s0/0
ip summary-address eigrp 1 172.30.0.0 255.255.248.0

Summary helps make routers more efficient, and also it prevents unnecessary recalculation for the DUAL algorithm if a network within a summary goes down. Keep in mind that "ip summary-address" would reset neighbors.

When summarizing, make sure that you summarize carefully. In our case, we need to summarize to both R2 and R3. If R3 does not have the summarized routes, it would advertise more specific routes to R2 and R2 would choose to route through R3 instead of directly to R1 to reach the routes behind.

in s0/1
ip summary-address eigrp 1 172.30.0.0 255.255.248.0

EIGRP can load-balance across 4 paths. By default, equal paths are load-balanced, but to load-balance across unequal paths, we can use the "variance" command:

router eigrp 1
variance 2

Variance 2 means that it would load-balance across links of up to 1/2 the metric of the best route. You may have to reset the router process for variance to take place. To do this, we can type:
clear ip eigrp nei

For EIGRP, the load is accurately and fairly load-balanced across the links.

Now we'll deal with EIGRP authentication. EIGRP authentication supports MD5 hashing. EIGRP makes use of a feature-packed and secure method known as the key chain. Key chain allows you to set the keys to use across time ranges. The time ranges of the keys should be overlapping so that it gives the routers some headroom for time differences. During the overlapping period, both keys are accepted. The keys, however, have to be manually entered on all routers. You can set the keys before activating authentication (you can also set the routers to begin authentication in a future time). To set the keys, we'll use:

key chain EIGRP_1
key 0
key-string cisco
accept-lifetime local 5:30:00 Nov 5 2010 5:30:00 Dec 5 2010
send-lifetime local 5:30:00 Nov 5 2010 5:30:00 Dec 5 2010
exit
key 1
key-string cisco2
accept-lifetime local 5:30:00 Dec 4 2010 5:30:00 Jan 5 2010
send-lifetime local 5:30:00 Dec 4 2010 5:30:00 Jan 5 2010
exit
key 2
key-string cisco3
accept-lifetime local 5:30:00 Jan 4 2010 5:30:00 Feb 5 2010
send-lifetime local 5:30:00 Jan 4 2010 5:30:00 Feb 5 2010

In the above example, I used a day of overlapping. To turn on authentication, we'll go under the interface:

in s0/0
ip authen mode eigrp 1 md5
ip authen key eigrp 1 EIGRP_1

We'll need to type this on R2 as well:

key chain EIGRP_1
key 0
key-string cisco
accept-lifetime local 5:30:00 Nov 5 2010 5:30:00 Dec 5 2010
send-lifetime local 5:30:00 Nov 5 2010 5:30:00 Dec 5 2010
exit
key 1
key-string cisco2
accept-lifetime local 5:30:00 Dec 4 2010 5:30:00 Jan 5 2010
send-lifetime local 5:30:00 Dec 4 2010 5:30:00 Jan 5 2010
exit
key 2
key-string cisco3
accept-lifetime local 5:30:00 Jan 4 2010 5:30:00 Feb 5 2010
send-lifetime local 5:30:00 Jan 4 2010 5:30:00 Feb 5 2010
in s0/0
ip authen mode eigrp 1 md5
ip authen key eigrp 1 EIGRP_1

2010-11-05T15:30:00.004+08:00

CCNP BSCI 02

In this article I'm going to walk through the implementation of basic EIGRP. We will accomplish basic routing, default-route advertising and verification. This is the topology we'll be using:

R1 is connected to the networks 192.168.[0-7].0/24.

Unlike OSPF, EIGRP AS numbers are significant throughout the organization.

Assuming all IP addresses are configured, we'll begin configuration on R2. To start the EIGRP process, we'll use:
router eigrp 1

We'll begin adding networks with the "network" statement. There are many ways you can enter networks in EIGRP. You can fall back to the RIP style, or use the OSPF style. By default, EIGRP acts like a classful routing protocol. We'll first disable classful routing through:
no auto

Now, we'll add the two networks to the routing process of R2:
network 10.0.0.0

EIGPR automatically summarizes across discontiguous networks to their classful boundaries. The "no auto" disables that behavior as it would cause some problems.

The "no auto" command should be started before the network command because it would reset any existing neighbor relationships when you type that in.

We'll do the same on R3:

router eigrp 1
no auto
network 10.0.0.0

Now back on R1, we'll start the links and advertise the routes connected at the back-end. We'll make use of wildcard masks:

router eigrp 1
no auto
network 10.0.0.0
network 192.168.0.0 0.0.7.255

Network statements does not influence the prefix that is being advertised. It only affects which interfaces that EIGRP is active on. To enable EIGRP on all interface, you can use:
network 0.0.0.0 255.255.255.255

To see what neighbors a router has, use:
sh ip eigrp nei

EIGRP sends Hello messages every 5 seconds. The Hold Down timer is the time it takes for the neighbor to expire. EIGRP default Hold Down timer is 15 seconds.

To check the routes known to the EIGRP process, use:
show ip eigrp top

Now we'll advertise some default route information. We'll assume that R1 is connected to the internet. There are many ways to advertise a default gateway. One of the ways is the "ip default-network" command. If we type this on R1, it does nothing for it, but it tells R2 and R3 to route packets towards a particular network by default.

The other way to advertise a default route is to first create a static default route like this:
ip route 0.0.0.0 0.0.0.0 192.168.0.2

Then we can advertise the route through:

router eigrp 1
network 0.0.0.0

We can also redistribute the route through:
redistribute static

2010-11-05T13:54:00.004+08:00

CCNP BSCI 01

EIGRP is considered one of the more user-friendly routing protocols in the IGP world. I'm going to walk through the basics and advanced configuration of EIGRP in the next few articles.

Unlike other protocols which only keeps the best route and throws the rest away (resulting in having to recalculate if the primary route goes down), EIGRP is able to quickly switch to one backup route if the primary link is down. EIGRP is the only protocol that supports backup routes.

OSPF is one of the most advanced routing protocols in the world, but it is more difficult to configure. EIGRP supports all of OSPF's features with the ease of configuration of traditional Distance Vector protocols.

Unlike OSPF's requirement to implement summarization on ABR or ASBR's, EIGRP can summarize wherever you want it. This makes EIGRP very flexible in summarization.

It is also difficult to effectively implement load-balancing across unequal-cost paths in other routing protocols. Typically, such an implementation results in having a reduction of throughput for the higher speed link. EIGRP, however, does this very quickly and easily.

Expandability is also one of the key factors designers kept in mind while creating the protocol. EIGRP is able to route multiple routed protocols without having to majorly rewrite the protocol like others.

Because EIGRP doesn't know the entire network topology, but only the networks their neighbors tell them about, the protocol is classified under Advanced Distance Vector protocol.

There are two terms to describe distance in EIGRP:
-Feasible Distance (FD)
-Advertised Distance (AD)

Feasible Distance is the distance for the router to reach the destination.

Advertised Distance is the distance for the router who told you about the destination (which is, the router's neighbor) to reach it.

Remember that I mentioned above that EIGRP keeps a backup route? These are the two terms you'll need to get familiar with:
-Successor
-Feasible Successor

The Successor refers to the primary route, while the Feasible Successor refers to the backup link. In order for a route to become a Feasible Successor, its Advertised Distance must be less than the Feasible Distance of your successor. In other words, your neighbor must have a better route to the destination than yourself for the route to be a backup.

This is a loop prevention mechanism. From the router's perspective, if your neighbor's advertised distance is higher than your feasible distance, there is a chance that your neighbor is routing through you.

Here's an example:

In this topology, R1 has two ways to get to the destination network: Through R2, and through R3.

It first looks for the successor by looking at the lowest cost path. Both R2 and R3 has an AD of 10. The path through R2 has a FD of 610, while the path through R3 has a FD of 1010.

The best path to the destination network (Successor) is through R2 as it has the lowest FD.

The path through R3 also becomes the backup (Feasible Successor) as it has the second lowest FD and the AD is lower than the FD of the successor.

However, this method sometimes block valid routes. If R3's route to the destination is 1500 instead of 10, then it wouldn't be chosen as the backup. Instead of instantaneously switching over to the route, R1 would take a longer time to switch over having to query R3 to make sure that it still has a real route.

However, let's look at what would happen if R3 didn't have the link to the destination to begin with:

R2 now has the Advertised Distance of 610 and R3 has the Advertised Distance of 1610.

The path through R2 becomes the primary because it has the best FD and AD is lower than FD.

However, the path through R3 will not be selected as the backup despite having the next best FD because the AD is higher than the FD of the successor.

There are two states a route can sit in:
-Active Route
-Passive Route

Contrary to first impressions, an active route is actually a bad thing. Active means that it is actively searching for a path to the route. Passive simply means that the path has been found.

You can see the state of the routes by looking at the topology table:
show ip eigrp topology

EIGRP has 5 different messages which they use to communicate and form neighborship:
-Hello
-Update
-Query
-Reply
-Ack

Hello forms relationships.

Update sends updates.

Query asks about routes.

Reply is a response to a query.

Ack is an acknowledgment to any of the messages above (except Hello).

Unlike RIP which sends the whole routing table constantly, EIGRP uses triggered updates. After the initial exchange, EIGRP only queries for, and receives routes it actually needs.

The EIGRP metric is (K1*BANDWIDTH+((K2*BANDWIDTH/(256-LOAD))+K3*DELAY)*(K5/RELIABILITY+K4)

The practical (default) metric is 256*(BANDWIDTH+DELAY)

BANDWIDTH = 10^7/Link Bandwidth
DELAY is expressed in Microseconds/10

Both the bandwidth and delay are statically entered values on a link. Each link has a predefined set of these. We can look at these by typing:
show int s0/0

To set the bandwidth, we can use:
bandwidth 1544

To set the delay, we can use:
delay 20000

Reliability and Load are the actual dynamic values. Cisco recommends never to use the full metric. Neighbors will only form if both routers have the same K Values.

The EIGRP routing process maintains three tables:
-Neighbor Table
-Topology Table
-Routing Table

We'll talk about these in upcoming articles.

2010-09-25T17:22:00.002+08:00

Debian 22

It's been a long time since I've written a Debian article. Well it's been a long time since I've written anything! Well, today I'm going to jump back onto the wagon with a quick tutorial to get your Linux system joined to an Active Directory Domain.

This article assumes that the Active Directory Domain is already fully functional. This is some background information for reference before we get started:
Domain Name: syraxius.ath.cx
Domain Controller Name: dc01.syraxius.ath.cx
Domain Controller IP: 192.168.1.2/24

We'll have to first synchronize our clocks with the Kerberos server. Like most authentication schemes, this is crucial. In this case, we'll make use of the already-installed NTP daemon which can function as both an NTP server and client. We'll modify the configuration file by typing:
nano /etc/ntp.conf

Scroll down to any of the servers section, and add your DC into the list:
server 192.168.1.2

Now, do a restart of the NTP server:
/etc/init.d/ntp restart

You should be able to see your DC listed when you type:
ntpq -p

We'll have to find some way to allow our Debian system to authenticate with an Active Directory server. This is accomplished through the Kerberos protocol. We'll install Kerberos through:
apt-get install krb5-config krb5-users

When prompted for the Kerberos server and the Administrative server for the realm, we'll use the FQDN of our Domain Controller, which is dc01.syraxius.ath.cx.

The settings are stored in the file called /etc/krb5 just in case things doesn't work out. The information you entered is under the "[realms]" section. The default realm can also be changed in the "[libdefaults]" section.

To test if our Kerberos implementation works, use the command:
kinit Administrator

kinit is a binary found in krb5-user package. This requests a logon for the user "Administrator". If no error messages occur, use the following command to check for a ticket:
klist

Now if everything's fine, you can move on. At this point we'll install Samba and Winbind:
apt-get install samba winbind

winbind is a component of samba which allows UNIX systems to be full members of an Active Directory domain. Winbind shares the configuration file of samba, which is /etc/samba/smb.conf.

After installing, we'll modify the /etc/samba/smb.conf file. The first thing we'll look out for is the workgroup. The workgroup is the Netbios name of the domain. So if I'm using syraxius.ath.cx for the domain, we'll type:
workgroup = SYRAXIUS

At this point we'll need to add a line to specify the realm. This is required when we attempt to join the domain. To do this, we'll simply type:
realm = SYRAXIUS.ATH.CX

Scroll down to the Authentication section and you'll find the line "# security = user". Add a new line to use ADS (Active Directory Service) like this:
security = ads

Directly below the domain master parameter is the UID mapping parameters. Simply uncomment them:

idmap uid = 10000-20000
idmap gid = 10000-20000
template shell = /bin/bash

We'll also have to allow winbind to enumerate the users and groups. Uncomment the below lines:

winbind enum groups = yes
winbind enum users = yes

You can also allow usershares by uncommenting the usershare section below. Usershares allow non-root users to create share definitions. We'll ignore this one for now.

Save the file and attempt to join the domain using the command:
net ads join -U Administrator

Restart winbind and samba and you should be able to use winbind to list the users and groups using:

wbinfo -u
wbinfo -g

You are still not able to do anything other than list users. If you want to log into the system with the accounts, you'll need to modify the /etc/nsswitch.conf file to look outside of the local databases. To do this, modify the file as shown:

passwd: files winbind
group: files winbind
shadow: files winbind

Next, we'll have to modify the AAA settings of the system to use winbind as well. The files to modify are:
/etc/pam.d/common-account
/etc/pam.d/common-auth
/etc/pam.d/common-session

For account, we'll add the line above the current rule:
account sufficient pam_winbind.so

Do the same for auth and session, changing the "account" keyword to "auth" and "session" accordingly. At this point you should be able to log into the system by using the domain\username convention. For example, to log into the Administrator account, simply use syraxius\Administrator as the username.

Notice that you're dumped to the root folder of the system once you're logged on. We'll now work on creating the user home folders. First, we'll modify the /etc/samba/smb.conf and add the following line below "template shell":
template homedir = /home/%D/%U

%D is substituted with the domain name (SYRAXIUS) and %U will become the user's name. However, the configuration isn't complete yet as you'll need the folder to exist first. This can be done automatically using pam_mkhomedir.so. We'll modify /etc/pam.d/common-session and add the following lines above all rules:
session required pam_mkhomedir.so skel=/etc/skel umask=022

Now you're done! But if of course, there is still some stuff that we can do. If you do not want to use the domain\name notation when logging in, simply add this line in /etc/samba/smb.conf below the "winbind enum" parameters:
winbind use default domain = yes

Now you have a domain-joined Linux computer!

2010-09-08T02:37:00.005+08:00

Psychology 02

Study the following optical illusion:

Now, if I were to tell you that the color of the tiles at A and B are the same, you wouldn't believe me.

However, once I add in a bridge to connect the two tiles, the fact is obvious:

However, if you look at the original picture again, the illusion comes back. Even though you consciously know that the shades are the same, your brain still tells you that they are different.

Vision is one of the best things human do. Vision takes up more of the brain's resources than anything else. Apart from necessary motor functions, vision is the most active skill we use daily.

Looking back at the optical illusion question raises a question: If we can make such predictable, consistent and reproducible mistakes even in vision, what about all the other processes that goes through our mind?

Optical illusions can be seen as a metaphor for human rationality. Can we be sure that we do not make the same revealing mistakes we do in vision when we make financial decisions? Like how optical illusions trick our vision, cognitive illusions can trick our thinking just as well.

However, cognitive illusions are more difficult to present. Refer to the following chart:

This is an actual data collected by a 2003 Science paper. What's presented here in the chart is the various percentage of people in different countries in Europe who opted to participate in an organ donation program.

From the diagram, we can clearly see that countries on the left and right are on opposite ends in terms of participation. The first thing we'd assume is that there must be some sort of cultural differences. However, upon further observation, you'll realize that Denmark is actually culturally similar to Sweden, but we have very different results. The same applies to Germany and Austria, Netherlands and Belgium, and UK and France.

A great concept is demonstrated here. What actually caused the great variation between the countries is the form used to gather the data. For the countries on the left, the form says:

"Check the box if you want to participate in an organ donation program",

on the other hand, countries on the right has:

"Check the box if you don't want to participate in an organ donation program".

In both cases, most of the boxes were not checked.

It is hard to believe that such "forms" can actually influence our decision making so much, because we feel like we have the driver seat of our lives. When you do things in your daily lives, you get to do things according to your own decisions. But are those truly your own decisions, or the decision of someone who designed your "form"?

Now, a standard rational economist would argue that most people do not care about their organs because it is something that takes place after they die. The cost of lifting the pencil to check the box is higher than the possible benefits that they can gain from it.

Dan Ariely, a behavioral economist, believes instead that people care too much. For most people, making the decision of donating your organs is so complex that they do not know what to do. Because they do not know what to do, they would pick whatever was chosen for them.

This effect not only applies to the general population, but it also applies to professionals as proven by a paper by Redelmeier and Schaefer. There are two groups of physicians and they are given a case study each. For the first group, the case study goes:

"There is an eighty-year-old patient suffering from pains in his right hip. You decided a few weeks ago that none of the medications are working, so you referred the patient for operation to have his hip replaced. Yesterday, you reviewed the case and you found out that you haven't tried ibuprofen. What do you do?"

Well, all of the physician suggested to delay the operation and try ibuprofen, which is good. Now, the second group is given the following case:

"There is an eighty-year-old patient suffering from pains in his right hip. You decided a few weeks ago that none of the medications are working, so you referred the patient for operation to have his hip replaced. Yesterday, you reviewed the case and you found out that you haven't tried ibuprofen and piroxicam. What do you do?"

Now, the problem suddenly becomes complex. Now you have two medications to try out - do you carry on with the planned operation, or do you pull the patient back? If you actually pull the patient back, which medication do you try first? Ibuprofen or Piroxicam? Suddenly, with just one extra decision to make, carrying on with the operation seemed to be a much simpler task. Most of the physicians then chose to let the patient go through hip replacement.

Now, no physician would tell you that: "Oh, I have three decisions to make: Ibuprofen, Piroxicam, and Hip Replacement. I choose Hip Replacement". However, once something is set as the default, it has a huge power on whatever people end up choosing.

Another example brought up by Dan Ariely is this: Suppose that you were given a choice of going to Rome, or going to Paris. All expenses paid. Both destinations have their own culture and so on, so they get almost equal amounts of votes.

However, once you add a third, inferior choice to the mix, things start to change. Suppose that the third choice would be a trip to Rome, all expenses paid except that breakfast is not served and you would have to pay for it yourself. At first, this may seem like it does nothing, but what this actually does is that the addition of the inferior choice actually makes Rome with all expenses paid a superior choice, even over Paris.

Dan Ariely also conducted another experiment in MIT involving subscription. Students were given this subscription form:

1) Web Subscription $59
2) Print Subscription $150
3) Print and Web Subscription $150

The results were that the Web Subscription is the least popular at 16% while the Print and Web Subscription took the other 84%. Nobody chose the standalone Print subscription.

Well we would think - If nobody chose the Print subscription, we can then eliminate it from the list. A second group of students were given this form:

1) Web Subscription $59
2) Print and Web Subscription $150

Now, results became radically different! The Web Subscription now gathered 68% of the students, while the Print and Web Subscription dropped to 32%. The option in the middle was useless in the sense where nobody chose it, but it's not useless in helping people make decisions. The presence of the middle option made the combo option a fantastic deal.

The general idea is that we do not know our preferences that well, and because of that, we are susceptible to external forces such as these. This force works not only in general decision-making, but also in our natural human instincts. A fine example is how we choose our partners.

Dan Ariely decided to use two CGI images of males: Tom and Jerry. Again, two groups were tested. The first group had an added uglier version of Tom, and the second group had an added uglier version of Jerry. In the first group, Tom became significantly more popular than Jerry, and in the second group it's the other way round.

In Standard Economics, humans are viewed as such:

"What a piece of work is a man! How noble in reason! How infinite in faculty! In form and moving how express and admirable! In action how like an angel! In apprehension how like a god!" - William Shakespeare (Act II. Scene 2 of Hamlet)

Now, in modern Behavioral Economics, the view of ourselves is not as generous. In fact, humans are viewed plainly as sheep which we can manipulate and herd. Humans are attracted to "Free Lunch", and we should build everything based on it.

In the physical world, we build everything based on our limits. For example, we can't fly, so we build steps to help us up. We can't reach the television from a distance, so we build remote controls. However, in the mental world, we tend to forget our limits. If we can better understand these limits, we can better shape our decisions.

I'll end this article by recommending this book if you would like to know more about Behavioral Economics: Predictably Irrational

2010-09-07T10:15:00.007+08:00

Psychology 01

There exists a problem known as the Candle Problem, proposed by Gestalt psychologist Karl Duncker to measure cognitive performance. Recognizing the potential of the Candle Problem, Sam Glucksberg used it as a means to test incentive-driven motivation. This led to one of the most robust, and ignored, findings in social science.

In the Candle Problem, participants are given a box of nails and a candle. The objective of the Candle Problem is to attach the Candle to the wall in a way that the wax would not drip to the table.

Many would nail the candles to the wall, and the rest would attempt to attach the candle to the wall horizontally by dripping wax - The correct solution to this problem is to nail the box holding the nails to the wall, then placing the candle on it.

When two large groups of subjects were given this task - one promised a large monetary reward, and the other a small one - the group promised the larger reward took an average of four minutes longer to come up with the correct solution. This is the exact opposite of what one would expect monetary incentives to do.

The Candle Problem was then modified so that the participants were presented with nails already out of the box. With the same incentives given, the group with the larger incentive did significantly better!

There is a mismatch in which what science knows, and what business does. What incentive does is that it narrows the vision. It causes the mind to focus on the goal. In the modified Candle Problem, the incentive allowed the participants to perform very well because the goal was very direct - to nail the box to the wall, and place the candle on it. In other words, when incentives are given, the left brain tends to be more dominant over the right, and critical thinking is discouraged.

However, the original Candle Problem required a peripheral perspective instead of the directed focus. In situations where thinking out of the box is required, incentive only shrouds and blinds. Every single one of us are dealing with our own Candle Problem, and the solution to our Candle Problem is often mystifying and hidden. What we truly need is to do Right Brain thinking, and incentives fail to motivate that.

The Massachusetts Institute of Technology led a series of test in which groups are given incentives for doing a set of games. As long as the games involved purely mechanical skills, incentives did as expected. However, once the games involved even rudimentary cognitive skills, the larger reward led to poorer performance.

This concludes that incentives lead to a NEGATIVE impact on overall performance.

Too many organizations are making decisions based on assumptions that are outdated and rooted more in folklore than science. If we really want performance, the solution is not to entice people with more money, or point a larger gun at them.

Dan Pink, an urban socialist, proposed a new operating system:

Autonomy: The urge to direct our own lives.
Mastery: The desire to get better and better at something that matters.
Purpose: The yearning to do what we do in the service for something larger than ourselves.

Management is the ancient and conventional way of handling people. Management is great traditionally if we want compliance. If we want engagement, self-direction works better.

Atlassian, an Australia-based software company, applies this concept flawlessly. For a few days each year, employees have to comply to Fedex Days. On a Fedex Day, they are given free time off to work on anything other than their projects. A large portion of the company's breakthrough came from this autonomy.

This worked so well that Google adopted it. In the 20 Percent Time scheme, Engineers are given autonomy for 20% of the day over their time and tasks. Things like GMail, Orkut, Google News are all birthed during 20 Percent Time. More than half of the company's productivity comes from the 20 Percent Time.

An even more radical example is the ROWE. ROWE stands for the Results Only Work Environment. In ROWE, people don't have schedules. They show up when they want, and they don't need to show up at the office at all as long as they get their work done. Meetings are optional. In a ROWE environment, productivity goes up, engagement goes up, morale goes up and turnover goes down.

In the mid-1990s, Microsoft came up with an encyclopedia known as Encarta. In Microsoft's model, writers are paid very good money to write and edit thousands and thousands of articles.

A few years later, an open-source encyclopedia with a completely different model surfaced. In this new model, you write articles because it is fun and because you like it. You don't get paid a single cent.

An economist in the 20th century would think that the second model is insane, but this was how Wikipedia was born.

There are two types of motivation: Intrinsic, and Extrinsic. Incentive is part of Extrinsic motivation. Extrinsic motivation is materialistic and short-term. True success comes from Intrinsic motivation. If you want to succeed, you must be given Autonomy, you must be motivated towards true Mastery, and your goal must be driven by Purpose.

2010-08-26T10:39:00.002+08:00

Misc 49
When talking about big commercial networks, there is always a need for reliability. This reliability comes in the form of redundant network devices: Redundant servers, redundant switches, and redundant routers.

Server farms and clustering are implemented to group servers, and Spanning-Tree Protocol allows for handling of redundant links in switched networks, but what about routers?

Today we'll look at three common redundancy protocols: HSRP, VRRP, and GLBP.

HSRP is one of the first redundancy protocols employed by the IOS. HSRP stands for Hot Standby Routing Protocol, and like what its name suggests, it allows routers to be "hot devices" (think of "hot sites") for each other and automatically come online once it detects that the active router is down. A virtual IP is used for each group, and a virtual MAC in the form of 0000.0c07.ac[groupID] is replied for ARPs. HSRP is Cisco proprietary.

VRRP is the Virtual Router Redundancy Protocol. It is the industry standard for redundancy between routers, featuring lower timers than the HSRP to ensure quicker detection of a failed active router.

GLBP is Cisco's response to the VRRP. GLBP stands for Gateway Load Balancing Protocol. GLBP allows for load balancing across all routers in the standby group. The concept works around a designated router known as the Active Virtual Gateway. All routers, including the gateway, are also known as Active Virtual Forwarders. Each AVF is assigned a forward number tied to a virtual MAC address which they are responsible for responding to. The AVG responds to ARP requests for the virtual IP with the virtual MAC of the AVFs in the group.

The same mechanism used in HSRP is applied if the active AVG goes down. If an AVF goes down, another AVF takes over and the AVG would stop redirecting it to the downed virtual MAC. There are two timers in an AVG, a redirect timer, and a secondary hold-down timer. The redirect timer is the time it takes for an AVG to decide to stop directing hosts to the downed AVF, and the secondary hold-down is the time it takes for the forward number to be freed for reassignment.

In all protocols, there are many ways to trigger a switch over. If the active forwarder becomes unreachable, the standby routers automatically take over. However, we can also set active routers to automatically trigger a switch over by tracking an object (such as a host), or an interface.

Today we'll look at all three protocols with this topology:

The network is split into two parts, the top network (1.1.1.0/24) and the bottom network (2.2.2.0/24). This is the addressing scheme used:

Top:
T1 - f0/0 - 1.1.1.1
L1 - f0/0 - 1.1.1.3
R1 - f0/0 - 1.1.1.4

Bottom:
B1 - f0/0 - 2.2.2.1
L1 - f0/1 - 2.2.2.3
R1 - f0/2 - 2.2.2.4

Assume that we want the virtual IP to be 1.1.1.2 for Top, and 2.2.2.2 for Bottom, we'll first configure HSRP.

On L1, add its f0/0 interface into group 0 of HSRP like this:

in f0/0
standby 0 ip 1.1.1.2

Similarly, on R1, add its f0/0 interface into group 0:

in f0/0
standby 0 ip 1.1.1.2

That is the complete configuration for a basic HSRP topology. Right now, pinging 1.1.1.2 will yield a response. To see who you're really connecting to, simply attempt to telnet in. To simulate a failure, simply administratively shut down the Top interface of the active router. Note the time it takes for the router to recognize the downed peer.

To verify HSRP operation, we can use:
show standby

Now, we'll attempt to change our protocol to VRRP. To do this, we'll type this on both the routers:
no standby 0 ip 1.1.1.2

Then we'll enable VRRP on both routers through:
vrrp 1 ip 1.1.1.2

Test for failure again and you'll realize that the routers recognize the downed peer much quicker. Verification information can be obtained through:
show vrrp

Now we'll switch over to GLBP. Disable VRRP, then enable GLBP using:
glbp 0 ip 1.1.1.2

The first thing I want you to type when the network converges is:
show glbp

On L1 you should see something similar to this:

FastEthernet0/0 - Group 0
  State is Active
    2 state changes, last state change 00:06:33
  Virtual IP address is 1.1.1.2
  Hello time 3 sec, hold time 10 sec
    Next hello sent in 2.104 secs
  Redirect time 600 sec, forwarder timeout 14400 sec
  Preemption disabled
  Active is local
  Standby is 1.1.1.4, priority 100 (expires in 7.128 sec)
  Priority 100 (default)
  Weighting 100 (default 100), thresholds: lower 1, upper 100
  Load balancing: round-robin
  Group members:
    c202.0410.0000 (1.1.1.3) local
    c203.0410.0000 (1.1.1.4)
  There are 2 forwarders (1 active)
  Forwarder 1
    State is Active
      1 state change, last state change 00:06:23
    MAC address is 0007.b400.0001 (default)
    Owner ID is c202.0410.0000
    Redirection enabled
    Preemption enabled, min delay 30 sec
    Active is local, weighting 100
  Forwarder 2
    State is Listen
    MAC address is 0007.b400.0002 (learnt)
    Owner ID is c203.0410.0000
    Redirection enabled, 599.568 sec remaining (maximum 600 sec)
    Time to live: 14399.568 sec (maximum 14400 sec)
    Preemption enabled, min delay 30 sec
    Active is 1.1.1.4 (primary), weighting 100 (expires in 9.564 sec)

At the top, there is FastEthernet 0/0 - Group 0 followed by "State is Active". This state refers to the AVG state. If the router is active, then it means that it is the AVG. On the other hand, if it says Listen, then that router is a standby AVG.

At the bottom, two forwarders are listed. This is the list of all forwarders on the list. At this point, my router is the forwarder for Forwarder 1 (it responds to the first MAC) while it listens for the status of Forwarder 2.

Telnet into 1.1.1.2 from T1, disconnect, and attempt to "show arp". You should see:

Protocol  Address          Age (min)  Hardware Addr   Type   Interface
Internet  1.1.1.1                 -   c200.0410.0000  ARPA   FastEthernet0/0
Internet  1.1.1.2                 3   0007.b400.0001  ARPA   FastEthernet0/0
Internet  1.1.1.3                 4   c202.0410.0000  ARPA   FastEthernet0/0
Internet  1.1.1.4                 4   c203.0410.0000  ARPA   FastEthernet0/0

Note that now 1.1.1.2 is associated to the MAC of forwarder 1, which is for L1. Now, shut L1 down and attempt to telnet back. At this point, L1 should not be able to respond for Forwarder 1's MAC, so it should not go through, right?

Miraculously, it does! R1 actually responds to Forwarder 1! Now, disconnect and attempt to "show arp", you should see:

Protocol  Address          Age (min)  Hardware Addr   Type   Interface
Internet  1.1.1.1                 -   c200.0410.0000  ARPA   FastEthernet0/0
Internet  1.1.1.2                 3   0007.b400.0001  ARPA   FastEthernet0/0
Internet  1.1.1.3                 4   c202.0410.0000  ARPA   FastEthernet0/0
Internet  1.1.1.4                 4   c203.0410.0000  ARPA   FastEthernet0/0

The MAC associated to 1.1.1.2 hasn't changed! This is evident that R1 has actually taken over the Forwarder of L1! To verify, type "show glbp" and you should see:

There are 2 forwarders (2 active)
  Forwarder 1
    State is Active
      3 state changes, last state change 00:00:04
    MAC address is 0007.b400.0001 (learnt)
    Owner ID is c202.0410.0000
    Redirection enabled, 585.960 sec remaining (maximum 600 sec)
    Time to live: 14385.956 sec (maximum 14400 sec)
    Preemption enabled, min delay 30 sec
    Active is local, weighting 100
  Forwarder 2
    State is Active
      1 state change, last state change 00:23:12
    MAC address is 0007.b400.0002 (default)
    Owner ID is c203.0410.0000
    Redirection enabled
    Preemption enabled, min delay 30 sec
    Active is local, weighting 100

R1 is now in charge of both forwarder 1 and 2! Now, notice the line that says "Load balancing: round-robin". This is the load-balancing policy, which simply makes to take turns. There is a weighted option which can be configured with:
glbp 0 load-balancing weighted

What this does is that it allows routers to be assigned a weight value. If L1 has a weight of 2 and R1 has a weight of 1, then L1 will receive 2 clients for every 1 client R1 receives. The weight can be configured using:
glbp 0 weight 2

Now we'll talk about priority and preempt. Notice that after your L1 came up, only the Forwarder was returned to it. The AVG is still R1. This is because by default routers have preempt set for AVFs, and no preempt set for AVGs. Preempt simply means that if the router comes back online, should the rights be given back to it. To enable preemption for AVG on L1, simply type:
glbp 0 preempt

Priority determines the next router that would be the standby for the active. The higher the priority number, the more likely it is to become the next active router when the current active goes down. Priority also determines if a router can be preempted. If a router has the priority of 150, and a router with the priority of 100 attempts to preempt, it will not succeed. The default priority is 100. The priority can be set using:
glbp 0 priority 150

The weight, in addition to load-balancing, can be used to determine if the router still serves as a AVF or not. The weight parameter allows you to set upper and lower thresholds. If you specify the lower threshold, then the router will be taken offline when its weight is at that threshold. If you also specify the upper threshold, then the router will not resume it role until it is higher than that amount. This is similar in operation to a schmitt trigger. Right now we'll use a simple system that specifies 1 = Offline, 2 = Online:
glbp 0 weighting 2 lower 1 upper 2

Now we'll need to specify an object to track. We'll track f0/1 (the other side's interface):
track 1 interface FastEthernet0/1 ip routing

Go back into the interface. From there, we'll enable tracking to specify that if track object 1 is down, the weight should be decremented by 1, effectively disallowing the router to be an AVF:
glbp 0 weighting track 1 decrement 1

On HSRP and VRRP, this can be done by using:

standby 0 track 1 dec 100
vrrp 1 track 1 dec 100

2010-08-05T14:30:00.006+08:00

Debian 21

Apart from allowing proxy access to subnets in Squid, you can actually specify an authentication scheme to be used with it. The authentication will come in the form of a HTTP - Basic Access Authentication window. We'll set up Squid to do just that in this article. We first of all install Squid:
apt-get install squid

The entire Squid system is controlled by the /etc/squid/squid.conf file, so let's open it up with:
nano /etc/squid/squid.conf

In this file, there are several things we'll need to change such as port number (optional) and allowed computers. First we'll change the port number, to do this, press F6 and type in "http_port". On about the fourth search, you should be able to find this line:
http_port 3128

Modify it to whatever you like and save your configuration. By default, Squid doesn't allow any proxy requests. To allow traffic, you'll need to use the "http_access" statement. The "http_access" statement specifies an "acl" each, and whether to permit or deny it. To begin, we'll press F6 and search for the keyword "localnet". You should end up with this:

acl localnet src 10.0.0.0/8
acl localnet src 172.16.0.0/12
acl localnet src 192.168.0.0 /16

Let us break down the format of the ACl declaration. The ACL declaration comes in the form:
acl aclname acltype argument

The available options in specifying an ACL can be found by searching (F6) for "TAG: acl". In this case, the above example shows the acl matching source address from RFC1918 subnets. Now, we'll want to use an ACL to specify or "match" an authentication method. Whether the ACL returns true or not depends on whether the authentication program (in this case, a supplied helper program) returns a true or false.

We'll first begin by setting up the authentication scheme, which would be NCSA Authentication. NCSA Authentication reads an NCSA-compatible password file made using the "htpasswd" command. To specify this method (we'll create the password file later), search (F6) for "passwd". You should end up at this line:
# auth_param basic program /usr/lib/squid/ncsa_auth /usr/etc/passwd

Obviously, /usr/etc/passwd doesn't exist because there is no such folder and Debian and because we haven't created a NCSA file yet. We'll uncomment the line and change the directory of the file to this:
auth_param basic program /usr/lib/squid/ncsa_auth /etc/squid/passwd

Now, we'll need to specify to use the authentication as a method. If you read the introduction to authentication a little higher (or by searching for "TAG: auth_param"), you would see that you need to specify an ACL of the type proxy_auth. To do this, we'll place this somewhere near our localnet ACLs:
acl authenticate proxy_auth REQUIRED

The REQUIRED keyword forces the server to accept only valid user names. Now, we'll apply the ACL by placing a http_access statement somewhere after "http_access allow localnet" (search for it):
http_access allow authenticate

Now finally, we'll need to create the NCSA password file. To do this, browse over to /etc/squid/ and type:
htpasswd -c passwd kelvin

The -c is to create a new file. To add more users in the future, omit the -c parameter. We'll now need to permit Squid to read it by allowing read permission for "others":
chmod o+r passwd

Coincidentally, the /etc/shadow file is NCSA-compatible, so you can actually use it instead of your own NCSA file to authenticate against existing Linux users. Remember to set the read permission in the server.

Now that we have everything in place, it's time to restart the proxy server through:
/etc/init.d/squid restart

Now after we set the browser to point to the proxy server, try to browse somewhere and you'll see a message similar to this:

In a future article we'll go through proxy authentication through Active Directory. Active Directory implements the LDAPv3 protocol and we'll be able to do this using squid's built-in ldapv3 helper.

2010-07-29T11:52:00.002+08:00

Misc 48

If you wish you use routing protocols on a Linux , you would need to install a routing software suite known as Quagga. Quagga supports OSPF (ospfd), OSPFv3 (ospf6d), RIP (ripd), RIPng (ripngd) and BGP (bgpd). All these run on a core daemon known as zebra (required to add static routes).

As evident from the routing protocols it supports, Quagga supports both IPv4 and IPv6 routing. These Daemons need to be run together with Zebra, which is used for specifying the interfaces, static routes and so on. Zebra is also essential for communicating with the routing daemons.

Right after we install Quagga, we'll need to specify the daemons that we want to run. These daemons can be specified by modifying:
nano /etc/quagga/daemons

In this example, I'm going to run OSPF. To do this, simply edit the configuration to reflect:

zebra=yes
bgpd=no
ospfd=yes
ripd=no
ripngd=no
isisd=no

Now, if you read a little up, there is a warning that says that you'll need to have a configuration file even if it's empty. Luckily for us, we have sample configuration files available for us. To find them, we simply type:

dpkg -L quagga | grep zebra.conf
dpkg -L quagga | grep ospfd.conf

Once we've got the paths, we'll need to copy them into the /etc/quagga/ folder:

cp /usr/share/doc/quagga/examples/zebra.conf.sample ./zebra.conf
cp /usr/share/doc/quagga/examples/ospfd.conf.sample ./ospfd.conf

At this point, we'll simply make a loopback interface on the Zebra so that we can see routes appear at the router side. To do this, modify zebra.conf and add:

interface lo
ip address 10.10.10.1/24

Now, we'll need to modify ospfd.conf. On my side, Quagga is sitting on 8.8.8.2, the router is in 8.8.8.3. The router has a loopback of 9.9.9.1 and Quagga has a loopback of 10.10.10.1. We'll now configure ospfd.conf to reflect routes:

router ospf
network 8.8.8.0/24 area 0
network 10.10.10.0/24 area 0

Back on the router, here's the configuration we have:

in f0/0
ip add 8.8.8.3 255.255.255.0
in lo0
ip add 9.9.9.1 255.255.255.0
router ospf 1
network 8.8.8.3 0.0.0.0 area 0
network 9.9.9.1 0.0.0.0 area 0

Now we'll restart all the daemons through:
/etc/init.d/quagga restart

If it all goes well, "show ip ospf nei" should show up as:

Neighbor ID     Pri   State           Dead Time   Address         Interface
8.8.8.2         1     FULL/BDR        00:00:34    8.8.8.2         FastEthernet0/0

Now to check the routes on Linux, you can either use the kernel command:
route -n

Another method is to go directly into the daemon's interactive context which is similar to IOS in many ways. To do this, we'll need to telnet to the localhost. The ports we'll be using are:
2601 - zebra
2602 - ripd
2603 - ripng
2604 - ospfd
2605 - bgpd
2606 - ospf6d

If you're in zebra, you can simply type:
show ip route

If you're on ospfd, you can use:
show ip ospf routes

The passwords are those stored in zebra.conf and ospfd.conf. It is "zebra" by default. Now you can try pinging and it should all go well!

2010-07-29T10:32:00.002+08:00

Misc 47

Now, if you've been following the previous articles, you would know that enrolling a certificate manually by copying and pasting requests is a chore. There is actually a simpler way to do this.

Introducing Microsoft's Network Device Enrollment Service, Microsoft's implementation of SCEP (Simple Certificate Enrollment Protocol) which they call MSCEP. This allows network devices, such as routers, to conveniently enroll for a certificate without needing to copy the entire certificate request over.

The NDES service can either be installed on a CA, or on a separate W2K8 machine. If you wish to get a certificate for SSL such as for WebVPN, then the Certificate Authority in this case must be a Standalone one. For some reason I was not able to enroll a Web Server certificate no matter what "usage" commands I used, the only certificate that the server sends during enrollment for an Enterprise CA is the IPSec Intermediate Offline certificate template, which is not usable as a SSL certificate.

Now, I'll assume that you know how to set up a Standalone CA. I have these roles installed, but you only need Certification Authority and the Network Device Enrollment Service:

During the installation, you can specify to use a user account to authorize the certificate. Before we can use that user account for this purpose, we'll need to add him/her to the IIS_IUSRS group. In this example, I'm going to add my Administrator account into that group. To do this, we'll open up MMC and add the Local Groups and Users snap-in:

Now you can add Administrator into IIS_IUSRS group:

Now you can complete the NDES installation. We'll now hop onto a Router to enroll the certificate. To do this, we'll first make sure that the device is server is reachable from your device, then configure a trustpoint like this:

crypto key gen rsa gen export label RSAKEYPAIR
crypto pki trust TRUSTPOINT
enroll url http://8.8.8.2/certsrv/mscep/mscep.dll
subject CN=8.8.8.3
rsakeypair RSAKEYPAIR

In this case, 8.8.8.2 is my CA/NDES and 8.8.8.3 is my router. Now we'll need to make sure that the router's clock is accurate (this is used for checking certificate validity):

conf t
clock time SGT +8
exit
clock set 11:03:00 July 29 2010

Now we'll add the CA certificate into the router:
crypto pki authenticate TRUSTPOINT

If it's all successful, you'll be asked to accept the certificate. Finally, we'll enroll the router's certificate through:
crypto pki enroll TRUSTPOINT

Now you'll get a message asking for a security code. This code can be obtained by visiting the mscep_admin page locally from the CA through:
http://localhost/certsrv/mscep_admin/

Now simply paste the code into your terminal twice and your certificate should enroll successfully! In some cases, you may need to manually issue the certificate. To do this, browse over to your Certification Authority console and down to Pending Certificates. Right-click on your certificate and click All Tasks - Issue:

You would have to wait for some time before the certificate reaches your router. When it does come in, this is the message you'll see:

Jul 29 03:17:49.271: %PKI-6-CERTRET: Certificate received from Certificate Authority

2010-07-27T19:18:00.005+08:00

Misc 46

Now this would actually be a pretty quick one. We'll build on the knowledge gained in this article to set up the WRT54G router, then we'll install a client on Windows separately.

Now before we go any further, I'll need you to flash your router to the TomatoVPN firmware. This will add OpenVPN capabilities into your router allowing it to act as a VPN terminator. TomatoVPN can be obtained here.

Note that you should be responsible for your own router and I will not be held liable for any damage resulting from anything. Now I had to say that to give myself some immunity.

Once you've got connectivity back up, it's time to hop on to your router. Browse on over to VPN Tunneling - Server:

This is the page where we set the basic parameters. If you feel that these settings are familiar, in fact they are! Those are the same settings found in the server.conf file. I changed my subnet address to 192.168.2.0/24 but it may not work for you depending on the addressing scheme used at your remote location. Now notice that if you attempt to click on Start Now, it will not work. This is because we still need to set the CA certificate, Server keypair, and the DH parameters. Now this is all coming together isn't it?

Now browse on over to the second page:

Notice that I included to push the route to the client. This is so that the clients can access each other. Finally we find ourselves at the Keys page. Is this going to be a nightmare? At first, it may seem so. But when you look again, you'll realize that you already have all the components. Hop on over to your Linux router and open the ca.crt with Notepad. We now PASTE the exact contents over. Do the same for your server keypair and the DH parameters:

Now that you have everything in place, simply save, then click on Start Now and you are done with the server part! Now it's time to set up the Windows side of things. For this, I'm going to grab a copy of openvpn-2.1.1-install.exe from the official OpenVPN website.

When it prompts to install a TAP/TUN driver, let it do so. This is the interface that will support the tunnel later on. Once installation is done, it's time to set up everything. First, copy the ca.crt and your client keypair to:

C:\Program Files\OpenVPN\config\

If you're on a x64 system, you may have to go to:

C:\Program Files (x86)\OpenVPN\config\

Now, go back one folder and move into the sample-config folder. Make a copy of client.ovpn and paste it into the config folder. Double-click on it, and guess what? It's exactly the same as client.conf in Linux! Now, simply edit it the same way as you would in this article and save the file.

To start the VPN client, simply open OpenVPN GUI and look at your System Tray for the logo. Right-click on it and click on Connect! Test your ping connectivity and it should be fine and dandy!

Now, if you wish to automatically connect to the router every time you boot up, simply go to Start - Run - Services.msc and set OpenVPN service to start up automatically!

2010-07-27T18:53:00.005+08:00

Misc 45

Now that we have a PKI set up, it's time to put it to good use. The most confusing thing about a Cisco router running HTTPS (such as one hosting WebVPN) is how it should obtain its certificate from a real CA. Now I'm going to show you the simplest way of obtaining a certificate (simplest in terms of technology, not necessary in terms of procedure).

First of we should have a CA set up in Linux, if not, you can refer to this article.

Now back on the router we want to run WebVPN on. What we want to do now is to create a trustpoint that we can enroll our certificates with. A trustpoint represents a CA, and the method we enroll our certificate is specified in there. But before we do that, we'll need to generate a keypair, which every RSA certificate needs:
crypto key gen rsa exportable label RSAKEYPAIR

Now that we have our RSA keypair, we can now create the trustpoint:

crypto pki trustpoint CA
rsakeypair RSAKEYPAIR

Now we'll specify our enrollment method, which is copying and pasting through the terminal. Now that's really low-tech. To do this, we'll specify:
enrollment terminal pem

Finally we'll specify the common name of the host. This common name needs to be the exact FQDN of the host. If the host does not have a domain name associated with it, you will need to specify the exact IP address it is going to use:
subject CN=1.1.1.2

Now you can actually specify a longer subject String with OU and all the extra stuff, but this will suffice for a very basic certificate. Now it's time to enroll the certificate:
crypto pki enroll CA

It will ask you if you want to display it on the terminal. Select YES and you should have something similar to this on your screen:

Now what you do with this information is that you need to copy the entire page from ----BEGIN CERTIFICATE REQUEST----- to -----END CERTIFICATE REQUEST----- and paste it into a file. What should you name the file? We'll, you've guessed it, you'll name it newreq.pem and place it into the /etc/ssl/ folder of your CA. Then we'll run the signature command with CA.pl. If you don't know what I'm talking about, you'll again need to refer to this article.

Now you should end up with a newcert.pem. Before we import the certificate, we'll need to import the certificate authority's root certificate. Why do we need to do that? This is because you don't have a button that says "Add Exception" in a Router, so you'll either have to have a CA certificate that you trust, or it's all not going to work at all.

Be sure that the system clock is set correctly! This is crucial as the certificates will be checked for both time and date to see if it's valid. To do this, we'll type:

conf t
clock timezone SGT +8
exit
clock set 19:11:00 July 27 2010

So we'll begin by invoking the command to allow importing of the root CA:
crypto pki authen CA

Next, we'll paste the contents of cacert.pem from -----BEGIN CERTIFICATE----- to -----END CERTIFICATE----- into the prompt. In case you're wondering, cacert.pem is actually found in /etc/ssl/demoCA/.

Now it's finally time to import your certificate. We do it the same way as we import the CA certificate, except that we'll use the command:
crypto pki import CA certificate

Now that you have a certificate, we'll set up our WebVPN but this time with the trust point set to the trustpoint which you imported your certificate into. If you want to set up WebVPN, you can follow along this article.

In the future I'll go into topics like using automatic enrollment and so on, so stay tuned! Before I go into those, it's time to set up OpenVPN on a WRT54G and connect using a Windows host!