Ford-Fulkerson Method

Facts

  • The Ford-Fulkerson method (G,S,t) is iterative
  • This method depends on three ideas:
    • Augmenting paths
    • Residual networks
    • Cuts
  • Simplified Pseudo-code:
    initialize flow f to 0
    while there exist an augmenting path p
        do augmented flow f along p
    return f

Augmenting Paths

  • An augmenting path p is a simple path from source S to sing t in the residual network
  • Each path have alternative free and matched edges in such way that begins and ends with free vertices.

Residual networks

  • Definition: Each edge (u,v) on an augmenting path admits some additional positive flow u to v without violating the capacity constrain on the edge.
    Ford_fulkerson_Residual_Flow
  • Example:
    Ford_Fulkerson_Transformation

Cuts

  • Minimum cut of a network: A cut whose capacity is minimum over all cuts on the network.
  • Max-flow min-cut theorem: A flow is maximum if and only if its residual network contains no augmenting path.
  • Example: cut(\{S, v_{1}, v_{2}\}), \{v_{3}, v_{4}, t\})
    Net-flow Across Cut (including net-flow between vertices): f(v_{1}, v_{3}) + f(v_{2},v_{3}) + f(v_{2}, v_{4}) = 14 + (-4) + 11 = 19
    Capacity (only edges going from source S to sink t): c(v_{1}, v_{3}) + c(v_{2}, v_{4}) = 12 + 14 = 26

 

Pseudocode

// Comments
Ford-Fulkerson (G,S,t)
for each edge (u,v)\epsilon E[G]
do f[u,v]\leftarrow 0 // f:flow
do f[v,u]\leftarrow 0
while there exist a path p from S to t in the residual network Gf
do cf(p)\leftarrow min\{cf(u,v): (u,v) is in p \} // cf: residual capacity
for each edge (u,v) in p
do f[u,v]\leftarrow f[u,v]+cf(p) // p: path
do f[v,u]\leftarrow -f[u,v]

 

Big O

Using either dept-first search or breadth-first search, the time to find a path in a residual network is O(V+E

Total running time is O(E|F*|) where f* is the maximum flow found

 

Note: If you find any mistake please let me know

Share

Notes: Operative Systems – Part 3

< Previous (Operative Systems – Part 2) | (Operative Systems – Part 4) Next >

NOTIFICATION: These notes are published for educational purposes. Using these notes is under your own responsibility and risk. These notes are given ‘as is’. I do not take responsibilities for how you use them.

PDF Content:

  • System call operation (syscall)
  • Intermediate Library
  • Implementing system calls
  • Kernel modules
  • SysEnter/SysExit method
  • Phony
  • Kernel modules
  • Module control
  • Generic module
  • Device classification
  • Character devices
  • Block devices
  • Network devices
  • Concurrency issues
  • Version numbering
  • GNU General Public Licence (GPL)
  • Memory management
  • Multiprogramming
  • Fixed partition
  • Relocation and protection

Operative_Systems_3

 

< Previous (Operative Systems – Part 2) | (Operative Systems – Part 4) Next >

Share

Introduction to Network Security – Part 11

NOTIFICATION: These examples are provided for educational purposes. The use of this code and/or information is under your own responsibility and risk. The information and/or code is given ‘as is’. I do not take responsibilities of how they are used. You are welcome to point out any mistakes in my posting and/or leave a comment.

Key Distribution Using Public-Key Cryptography

In the previous post, introduction to network security – part 10, we saw three main methods of public-key:

  1. Public announcement,
  2. Public-key authority, and
  3. Public-key certificates

These methods can be used for encryption and decryption of messages (secrecy) and/or authentication.

These methods the disadvantage of being slow; therefore, its common to use symmetric-key encryption for secrecy and distribute using public-key encryption session keys. In this way we use the advantage of the speed of symmetric-key encryption and the security of public-key encryption.

Simple Key Distribution

In 1979,  Ralph C. Merkle created his thesis entitled “Secrecy, authentication and public key systems” which let him receive his Ph. D. in Electrical Engineering at Stanford University <http://en.wikipedia.org/wiki/Ralph_Merkle>.

For a key distribution, Merkle proposed:

  1. User A will generate a new temporaty public key pair, PUa
  2. User A send the public key, PUa, to user B together with its identity, IDa
    PUa, IDa
  3. User B generate the session key K.
  4. User B uses the public key, PUa, supplied by user A to encrypt the session key K. Then user B send the encrypted session to user A
  5. User A decrypt the message to obtain the session key K.
  6. User A discards the public key PUa
  7. User B discards user A’s public key, PUa.
  8. After the exchange of information is complete, user A and B discard the session key K.

The Man-In-The-Middle Attack

This type of key distribution have a disadvantage.  Lets assume that we have an attacker that gets in the middle of the communication in a way that this attacker can intercept the messages and then replay this message, modify this message, or send another different message.

Lets analyse this problem:

  1. User A send a message to user B which holds the public key PUa, and user A’s identifier IDa
  2. The attacker T intercept this message and create its own pair keys, public key PUt and private key PRt:
    {PUt, PRt}

  3. The attacker T send to user B, its own public key PUt together with the user A’s identification IDa :
    PUt||IDa
  4. User B generate a session key Ks. Then user B send this session key Ks encrypted using the public-key PUt that he received thinking that it came from user A.
    Ciphertext = E(PUt, Ks)
  5. The attacker T intercept the message obtaining the session key Ks by decrypting the message with his private key PRt.
    Ks = D(PRt, Ciphertext) = D(PRt, E(PUt, Ks))
  6. Then attacker T send the key session Ks to the user A using user A’s public key PUa
  7. Without user A and B knowing, the attacket T obtained the session Ks successfully.

Solution to The Man-In-The-Middle Attack

  1. The process begins with user A. User A encrypt the message containing the user A identification IDa plus a nonce N1 using the user B’s public key PUb
  2. User B generate a new nonce N2 and encrypts the message containing user A’s nonce N1 plus a new nonce N2 using the user A’s public key.
  3. Since user B is the only one that could decrypted the first message coming from user A plus the new message send from user B to user A will contain the nonce N1 (given by  user A in the first message), user A will know the new message is coming from user B and not an attacker.
  4. User A will encrypt nonce N2 using the public key PUb of user B. Then user A will send then encrypted nonce N2 to user B. In this way, since nonce N2 was generated by user B, when user B find nonce N2, user B will known the message came from user A.
  5. User A generate a secret key Ks. User A will encrypt first the secret key Ks using the private key PUa of user A which would provide authentication, and then it will encrypt the output of the encryption with the public key PUb of user B to produce a new ciphertext M which provide confidentiality.
  6. User B decrypt the ciphertext M by decrypting the ciphertext M using the private key PUb of userB, and the result will be decrypted again using the public key PUa of user A. In this way the secret key Ks is obtained.

Hybrid Key Distribution

Public key encryption is an algorithm that require a lot of processing. In a system that require to distribute session keys thought many users and require a frequently change of session keys, the public key encryption can slow the performance of the system as the load on the system keep increasing. One solution to this problem is to use an hybrid of different key distribution.

In an hybrid key distribution, the key distribution center (KDC) will be in charge of distributing a master key MK to each user of the system plus perform the distribution of session keys. Before these session keys are distributed, they will be encrypted by using the master key MK. Also, the master key is encrypted using a public key encryption. Since the master key only update in few occasions then the load of the system is reduced.

Share